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

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

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

Содержание

Мотивация

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

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

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

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

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

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

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

  • Аксиома (о независимости элементов выборки). Все перестановки генеральной выборки \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. Мы полагаем, что случайными являются не сами объекты, а только последовательность их появления. В слабой аксиоматике термин вероятность понимается только как синоним «доли перестановок выборки».

Задача эмпирического предсказания

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

Пусть задано множество Q и функция T:\: X^{*}\times X^{*} \to Q. Рассмотрим эксперимент, в~котором реализуется одно из равновероятных разбиений выборки X^L на две подвыборки X^\ell_n и X^k_n,\; n=1,\dots,N,\; N=C_L^\ell. После реализации разбиения n наблюдателю сообщается подвыборка X^\ell_n.

Не зная скрытой подвыборки X^k_n, он должен построить предсказывающую функцию \hat T:\: X^{*} \to Q, значение которой \hat T_n = \hat T(X^\ell_n) на наблюдаемой подвыборке X^\ell_n приближало бы неизвестное истинное значение T_n = T(X^k_n,X^\ell_n).

Необходимо также оценить надёжность предсказания, то есть указать невозрастающую оценочную функцию \eta(\varepsilon) такую, что

P_n \bigl[ d(\hat T_n, T_n) \geq \varepsilon \bigr] \leq \eta(\varepsilon),

где $d:\: Q\times Q\to\RR$ — заданная функция, характеризующая величину отклонения d(\hat T_n, T_n) предсказанного значения \hat T_n от неизвестного истинного значения T_n.

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

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

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

Подробнее:

Комбинаторный подход к оценке качества обучаемых алгоритмов. Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36.

Комбинаторная вероятность и точность оценок обобщающей способности. Pattern Regognition and Image Analysis. 2008 (принято в печать).

Открытые задачи (сюда можно добавлять разделы)

Ранговые критерии

Гипотеза: значительная часть теории ранговых критериев может быть построена чисто комбинаторными средствами. Для критерия Вилкоксона, мединного критерия, критерия знаков результаты уже известны. Однако для воспроизведения общей теории ранговых критериев, вожможно, придётся искать какую-то новую технику оценивания мощности критериев.

Профиль разделимости

Известно, что максимизация отступов (margin) объектов приводит к повышению обобщающей способности классификатора. «Правильное» распределение отступов похоже на ступенчатую функцию: шумовые объекты (выбросы) должны получить отрицательные отступы, эталоны классов — большие положительные отступы, пограничных объектов должно быть поменьше. Тогда классификация будет более надёжной. Как это обосновать?.

Известен ряд алгоритмов классификации, основанных на явной максимизации отступов. Для этого используются различные функции потерь, зависящие от отступа M. В бустинге (AdaBoost) это e^{-M}. В машинах опорных веткоров (SVM) это (1-M)_{+}. В логистической регрессии \ln(1+e^{-M}) Профилем разделимости будем называть эмпирическое распределение отступов. Возникает вопрос: как должна выглядеть «правильная» функция потерь, минимизация которой давала бы алгоритм с наилучшей обобщающей способностью?

Гипотеза: скорее всего, функционал качества выражается через свёртку профиля разделимости с некими комбинаторными коэффициентами (как это уже оказалось для 1NN и монотонных классификаторов).

Профиль устойчивости

Известна целая серия оценок обобщающей способности для алгоритмов классификации, обладающих свойством устойчивости (или стабильности, в оригинале stability). С ними есть две проблемы. Во-первых, все эти оценки сильно завышены. Во-вторых, до сих пор не выработано «единственно правильное» определение стабильности. Предложено около двух десятков определений, между которыми установлены связи «сильнее—слабее». Всё это говорит о том, что явление стабильности по-настоящему ещё не понято.

Профиль устойчивости S(m) показывает, насколько изменяются классификации получаемого алгоритма, если состав обучающей выборки изменяется на m объектов.

Гипотеза: скорее всего, функционал качества и в этом случае выражается через свёртку профиля устойчивости с некими комбинаторными коэффициентами.


Полемика (сюда можно добавлять разделы)

Готов обсуждать эти и другие контраргументы.

В слабой аксиоматике нет ничего нового

Да, действительно, техника подсчёта перестановок давно и успешно используется в теорвере и матстате. В статистике есть довольно много «точных критериев», которые кем-то когда-то табулированы, но не приводятся в учебниках, и даже не во всех справочниках. Обычно ими рекомендуется пользоваться при малых выборках, а, начиная с выборок около 30 объектов переходить на асимптотические приближения: нормальное, хи-квадрат, и т.п. Точные критерии оказались в загоне из-за трудоёмкости их вычислиения и громоздких формул, которые редко удаётся уместить в одну строчку. Теперь, когда мощные вычислители общедоступны, ничто не препятствует их более широкому применению. Кроме того, комбинаторный вывод точных критериев во многих случаях элементарен.

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

В слабой аксиоматике должны получаться более слабые результаты

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

Тогде почему в слабой аксиоматике могут получаться более сильные результаты? Это происходит по субъективным причинам. В сильной аксиоматике есть хорошо разработанный аппарат асимптотических оценок. Само определение вероятности через предельный переход по сути своей асимптотично. Биномиальное, пуассоновское, нормальное распределения — это асимптотические приближения гипергеометрического распределения. Асимптотичность заложена во многих распределениях, активно используемых в математической статистике (том же хи-квадрат). Но об этом никто не помнит.

Слабая аксиоматика ограничивает свободу действий математика. Предлагается забыть на время о блестящем аппарате асимптотических распределений и попробовать получить те же результаты, используя только палку и верёвку.

Возникают сложности с оцениванием непрерывных случайных величин

Источник — «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»
Личные инструменты