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

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

Перейти к: навигация, поиск

Содержание

Мотивация

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

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

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

В слабой вероятностной аксиоматике рассматриваются только конечные выборки. Вводится чисто комбинаторное понятие вероятности, не требующее ни привлечения теории меры, ни предельных переходов к бесконечным выборкам. Все вероятности оказываются непосредственно измеримыми в эксперименте. Слабая аксиоматика полностью согласуется 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).

Полемика

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

  • В слабой аксиоматике нет ничего нового. Техника подсчёта перестановок давно и успешно используется в доказательствах.
  • В более слабой аксиоматике должны получаться более слабые результаты.
  • При комбинаторном подходе возникают сложности с оцениванием непрерывных случайных величин.
Личные инструменты