Слабая вероятностная аксиоматика

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: == Мотивация == Начну с цитирования классиков. * '''А. Н. Колмогоров''': «Представляется важной задача осв...)
м
Строка 3: Строка 3:
Начну с цитирования классиков.
Начну с цитирования классиков.
-
* '''А. Н. Колмогоров''':
+
* '''А. Н. Колмогоров''': «Представляется важной задача освобождения всюду, где это возможно, от излишних вероятностных допущений. На независимой ценности чисто комбинаторного подхода к теории информации я неоднократно настаивал в своих лекциях.»
-
«Представляется важной задача освобождения всюду, где это возможно, от излишних вероятностных допущений.
+
-
На независимой ценности чисто комбинаторного подхода к теории информации я неоднократно настаивал в своих лекциях.»
+
-
* Ученик А. Н. Колмогорова '''Ю. К. Беляев'''
+
* Ученик А. Н. Колмогорова '''Ю. К. Беляев''' (из предисловия к книге ''Вероятностные методы выборочного контроля''): «Возникло глубокое убеждение, что в теории выборочных методов можно получить содержательные аналоги большинства основных утверждений теории вероятностей и математической статистики, которые к настоящему времени найдены в предположении взаимной независимости результатов измерений».
-
(из предисловия к книге ''Вероятностные методы выборочного контроля''):
+
-
«Возникло глубокое убеждение, что в теории выборочных методов можно получить содержательные аналоги большинства основных утверждений теории вероятностей и математической статистики, которые к настоящему времени найдены в предположении взаимной независимости результатов измерений».
+
Современная теория вероятностей возникла из стремления объединить в рамках единого формализма частотное понятие вероятности, берущее начало от азартных игр, и континуальное, идущее от геометрических задач типа задачи Бюффона
Современная теория вероятностей возникла из стремления объединить в рамках единого формализма частотное понятие вероятности, берущее начало от азартных игр, и континуальное, идущее от геометрических задач типа задачи Бюффона
Строка 18: Строка 14:
В ''слабой вероятностной аксиоматике'' рассматриваются только конечные выборки.
В ''слабой вероятностной аксиоматике'' рассматриваются только конечные выборки.
-
Вводится чисто комбинаторное понятие вероятности, не требующее ни привлечения теории меры, ни предельных апереходов к бесконечным выборкам.
+
Вводится чисто комбинаторное понятие вероятности, не требующее ни привлечения теории меры, ни предельных переходов к бесконечным выборкам.
Все вероятности оказываются непосредственно измеримыми в эксперименте.
Все вероятности оказываются непосредственно измеримыми в эксперименте.
Слабая аксиоматика полностью согласуется c сильной (колмогоровской) аксиоматикой, но её область применимости ограничена задачами анализа данных.
Слабая аксиоматика полностью согласуется c сильной (колмогоровской) аксиоматикой, но её область применимости ограничена задачами анализа данных.
Строка 33: Строка 29:
Обозначим через <tex>S_L</tex> группу всех <tex>L!</tex> перестановок <tex>L</tex> элементов.
Обозначим через <tex>S_L</tex> группу всех <tex>L!</tex> перестановок <tex>L</tex> элементов.
-
* '''Аксиома''' (о независимости элементов выборки).
+
* '''Аксиома''' (о независимости элементов выборки). Все перестановки генеральной выборки <tex>\tau X^L,\; \tau\in S_L</tex> имеют одинаковые шансы реализоваться.
-
Все перестановки генеральной выборки
+
-
<tex>\tau X^L,\; \tau\in S_L</tex>
+
-
имеют одинаковые шансы реализоваться.
+
Пусть на множестве выборок задан предикат <tex>\psi:\: X \to \{0,1\}</tex>.
Пусть на множестве выборок задан предикат <tex>\psi:\: X \to \{0,1\}</tex>.
Строка 58: Строка 51:
* Получены точные оценки обобщающей способности для монотонных алгоритмов классификации, выражающиеся через ''профиль монотонности'' выборки.
* Получены точные оценки обобщающей способности для монотонных алгоритмов классификации, выражающиеся через ''профиль монотонности'' выборки.
-
Здесь [http://www.ccas.ru/voron/download/EmpiricalPrediction.pdf подробный текст].
+
Здесь [http://www.ccas.ru/voron/download/EmpiricalPrediction.pdf черновик пишущейся диссертации].
== Открытые задачи ==
== Открытые задачи ==
-
* Ранговые статистические критерии в слабой аксиоматике.
+
* Ранговые критерии в слабой аксиоматике.
* Оценки обобщающей способности для алгоритмов классификации, выражающиеся через ''профиль разделимости'' выборки.
* Оценки обобщающей способности для алгоритмов классификации, выражающиеся через ''профиль разделимости'' выборки.
* Оценки обобщающей способности устойчивых алгоритмов классификации (stability).
* Оценки обобщающей способности устойчивых алгоритмов классификации (stability).

Версия 20:05, 26 февраля 2008

Содержание

Мотивация

Начну с цитирования классиков.

  • А. Н. Колмогоров: «Представляется важной задача освобождения всюду, где это возможно, от излишних вероятностных допущений. На независимой ценности чисто комбинаторного подхода к теории информации я неоднократно настаивал в своих лекциях.»
  • Ученик А. Н. Колмогорова Ю. К. Беляев (из предисловия к книге Вероятностные методы выборочного контроля): «Возникло глубокое убеждение, что в теории выборочных методов можно получить содержательные аналоги большинства основных утверждений теории вероятностей и математической статистики, которые к настоящему времени найдены в предположении взаимной независимости результатов измерений».

Современная теория вероятностей возникла из стремления объединить в рамках единого формализма частотное понятие вероятности, берущее начало от азартных игр, и континуальное, идущее от геометрических задач типа задачи Бюффона о вероятности попадания иглы в паркетную щель. В аксиоматике Колмогорова континуальное понятие берётся за основу как более общее. Ради этой общности в теорию вероятностей привносятся гипотезы сигма-аддитивности и измеримости — технические предположения из теории меры, имеющие довольно слабые эмпирические обоснования. Однако от них вполне можно отказаться в задачах анализа данных, где число наблюдений всегда конечно.

В слабой вероятностной аксиоматике рассматриваются только конечные выборки. Вводится чисто комбинаторное понятие вероятности, не требующее ни привлечения теории меры, ни предельных переходов к бесконечным выборкам. Все вероятности оказываются непосредственно измеримыми в эксперименте. Слабая аксиоматика полностью согласуется c сильной (колмогоровской) аксиоматикой, но её область применимости ограничена задачами анализа данных. Рассматриваются два достаточно широких класса задач: эмпирическое предсказание и проверка статистических гипотез.

Слабая вероятностная аксиоматика

Аксиома только одна.

В любом эксперименте, прошедшем или будущем, может наблюдаться лишь конечное множество объектов X^L = (x_1,\dots,x_L). Обозначим через S_L группу всех L! перестановок L элементов.

  • Аксиома (о независимости элементов выборки). Все перестановки генеральной выборки \tau X^L,\; \tau\in S_L имеют одинаковые шансы реализоваться.

Пусть на множестве выборок задан предикат \psi:\: X \to \{0,1\}. Вероятностью события \psi будем называть долю перестановок, при которых предикат истинен (принимает значение 1):

P_\tau \psi(\tau X^L) = \frac1{L!} \sum_{\tau\in S_L} \psi(\tau X^L).

Эта вероятность зависит от выборки X^L. Мы полагаем, что случайными являются не сами объекты, а только последовательность их появления. В слабой аксиоматике термин вероятность понимается только как синоним «доли перестановок выборки».

Некоторые результаты

Несмотря на предельную упрощённость, в слабой аксиоматике удаётся сформулировать и доказать аналоги многих фундаментальных фактов теории вероятностей, математической статистики и статистического обучения:

  • Закон больших чисел является тривиальным следствием свойств ГГР — гипергеометрического распределения. Точные (не завышенные) оценки скорости сходимости вычисляются через обратную функцию ГГР.
  • Точные оценки скорости сходимости эмпирических распределений (критерий Смирнова) вычисляются через усечённый теругольник Паскаля.
  • В теории Вапника-Червоненкиса слабая аксиоматика позволяет «узаконить» скользящий контроль. Известные теоретические верхние оценки обобщающей способности и скользящий контроль оказываются двумя разными способами оценивания одного и того же функционала.
  • Удаётся количественно измерить основные факторы завышенности известных оценок обобщающей способности. Оказывается, что коэффициент разнообразия (shattering coeffitient), характеризующий сложность алгоритма, в реальных задачах принимает значения порядка десятков. Известные теоретические оценки чрезвычайно завышены и имеют порядок 10^5-10^{11}.
  • Получены точные оценки обобщающей способности для метода kNN, выражающиеся через профиль компактности выборки.
  • Получены точные оценки обобщающей способности для монотонных алгоритмов классификации, выражающиеся через профиль монотонности выборки.

Здесь черновик пишущейся диссертации.

Открытые задачи

  • Ранговые критерии в слабой аксиоматике.
  • Оценки обобщающей способности для алгоритмов классификации, выражающиеся через профиль разделимости выборки.
  • Оценки обобщающей способности устойчивых алгоритмов классификации (stability).

Полемика

Готов обсуждать следующие (и другие) контраргументы:

  • В слабой аксиоматике нет ничего нового. Техника подсчёта перестановок давно и успешно используется в доказательствах.
  • В более слабой аксиоматике должны получаться более слабые результаты.
  • При комбинаторном подходе возникают сложности с оцениванием непрерывных случайных величин.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A1%D0%BB%D0%B0%D0%B1%D0%B0%D1%8F_%D0%B2%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%BD%D0%B0%D1%8F_%D0%B0%D0%BA%D1%81%D0%B8%D0%BE%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0»