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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 26: Строка 26:
В любом эксперименте, прошедшем или будущем, может наблюдаться лишь конечное множество объектов
В любом эксперименте, прошедшем или будущем, может наблюдаться лишь конечное множество объектов
-
<tex>X^L = (x_1,\dots,x_L)</tex>.
+
<tex>X^L = (x_1,\ldots,x_L)</tex>.
Обозначим через <tex>S_L</tex> группу всех <tex>L!</tex> перестановок <tex>L</tex> элементов,
Обозначим через <tex>S_L</tex> группу всех <tex>L!</tex> перестановок <tex>L</tex> элементов,
<tex>X^{*}</tex> — множество всех конечных выборок из <tex>X</tex>.
<tex>X^{*}</tex> — множество всех конечных выборок из <tex>X</tex>.
Строка 41: Строка 41:
Мы полагаем, что случайными являются не сами объекты, а только последовательность их появления.
Мы полагаем, что случайными являются не сами объекты, а только последовательность их появления.
В слабой аксиоматике термин ''вероятность'' понимается только как синоним «доли перестановок выборки».
В слабой аксиоматике термин ''вероятность'' понимается только как синоним «доли перестановок выборки».
 +
 +
''Случайная величина'' определяется просто как вещественная функция выборки.
 +
 +
''Функция распределения'' вводится стандартным образом.
 +
 +
''Матожидание'' вводится как среднее арифметическое по всем перестановкам, что формально совпадает с определением вероятности.
== Задача эмпирического предсказания ==
== Задача эмпирического предсказания ==
Строка 47: Строка 53:
Пусть задано множество <tex>Q</tex> и функция <tex>T:\: X^{*}\times X^{*} \to Q</tex>.
Пусть задано множество <tex>Q</tex> и функция <tex>T:\: X^{*}\times X^{*} \to Q</tex>.
-
Рассмотрим эксперимент, в~котором реализуется одно из равновероятных разбиений выборки <tex>X^L</tex> на две подвыборки <tex>X^\ell_n</tex> и <tex>X^k_n,\; n=1,\dots,N,\; N=C_L^\ell</tex>.
+
Рассмотрим эксперимент, в котором реализуется одно из равновероятных разбиений выборки <tex>X^L</tex> на две подвыборки <tex>X^\ell_n</tex> и <tex>X^k_n,\; n=1,\ldots,N,\; N=C_L^\ell</tex>.
После реализации разбиения <tex>n</tex> наблюдателю сообщается подвыборка <tex>X^\ell_n</tex>.
После реализации разбиения <tex>n</tex> наблюдателю сообщается подвыборка <tex>X^\ell_n</tex>.
Строка 60: Строка 66:
<tex>P_n \bigl[ d(\hat T_n, T_n) \geq \varepsilon \bigr] \leq \eta(\varepsilon)</tex>,
<tex>P_n \bigl[ d(\hat T_n, T_n) \geq \varepsilon \bigr] \leq \eta(\varepsilon)</tex>,
</center>
</center>
-
где $d:\: Q\times Q\to\RR$ — заданная функция, характеризующая величину отклонения
+
где <tex>d:\: Q\times Q\to R</tex> — заданная функция, характеризующая величину отклонения
<tex>d(\hat T_n, T_n)</tex>
<tex>d(\hat T_n, T_n)</tex>
предсказанного значения <tex>\hat T_n</tex> от неизвестного истинного значения <tex>T_n</tex>.
предсказанного значения <tex>\hat T_n</tex> от неизвестного истинного значения <tex>T_n</tex>.
Строка 74: Строка 80:
* Получены оценки обобщающей способности для монотонных алгоритмов классификации, выражающиеся через ''профиль монотонности'' выборки. Хотя эти оценки не являются точными, они гораздо точнее тех, которые основаны на ёмкости класса монотонных функций [Joseph Sill, 1998])
* Получены оценки обобщающей способности для монотонных алгоритмов классификации, выражающиеся через ''профиль монотонности'' выборки. Хотя эти оценки не являются точными, они гораздо точнее тех, которые основаны на ёмкости класса монотонных функций [Joseph Sill, 1998])
-
Подробнее:
+
'''Подробнее:'''
[http://www.ccas.ru/frc/papers/voron04mpc.pdf Комбинаторный подход к оценке качества обучаемых алгоритмов]. Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36.
[http://www.ccas.ru/frc/papers/voron04mpc.pdf Комбинаторный подход к оценке качества обучаемых алгоритмов]. Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36.
Строка 85: Строка 91:
'''Гипотеза''':
'''Гипотеза''':
-
значительная часть теории ранговых критериев может быть построена чисто комбинаторными средствами.
+
многие ранговые критерии могут быть построены чисто комбинаторными средствами.
-
Для критерия Вилкоксона, мединного критерия, критерия знаков результаты уже известны.
+
 
-
Однако для воспроизведения общей теории ранговых критериев, вожможно, придётся искать какую-то новую технику оценивания мощности критериев.
+
Для критерия Вилкоксона, медианного критерия, критерия знаков, и некоторых других это практически очевидно. Фактически, именно так они и строятся.
 +
Однако для построения общей теории ранговых критериев в слабой аксиоматике, возможно, придётся искать какую-то новую технику оценивания мощности критериев.
=== Профиль разделимости ===
=== Профиль разделимости ===
Известно, что максимизация отступов (margin) объектов приводит к повышению обобщающей способности классификатора.
Известно, что максимизация отступов (margin) объектов приводит к повышению обобщающей способности классификатора.
-
«Правильное» распределение отступов похоже на ступенчатую функцию:
+
«Правильное» распределение отступов похоже на «ступеньку»:
шумовые объекты (выбросы) должны получить отрицательные отступы,
шумовые объекты (выбросы) должны получить отрицательные отступы,
эталоны классов — большие положительные отступы,
эталоны классов — большие положительные отступы,
-
пограничных объектов должно быть поменьше.
+
пограничных объектов должно быть как можно меньше.
-
Тогда классификация будет более надёжной.
+
Тогда классификация будет наиболее надёжной.
-
'''Как это обосновать?'''.
+
'''Как это обосновать?'''
Известен ряд алгоритмов классификации, основанных на явной максимизации отступов.
Известен ряд алгоритмов классификации, основанных на явной максимизации отступов.
Для этого используются различные функции потерь, зависящие от отступа <tex>M</tex>.
Для этого используются различные функции потерь, зависящие от отступа <tex>M</tex>.
В бустинге (AdaBoost) это <tex>e^{-M}</tex>.
В бустинге (AdaBoost) это <tex>e^{-M}</tex>.
-
В машинах опорных веткоров (SVM) это <tex>(1-M)_{+}</tex>.
+
В машинах опорных векторов (SVM) это <tex>(1-M)_{+}</tex>.
В логистической регрессии <tex>\ln(1+e^{-M})</tex>
В логистической регрессии <tex>\ln(1+e^{-M})</tex>
''Профилем разделимости'' будем называть эмпирическое распределение отступов.
''Профилем разделимости'' будем называть эмпирическое распределение отступов.
Строка 127: Строка 134:
== Полемика (сюда можно добавлять разделы) ==
== Полемика (сюда можно добавлять разделы) ==
-
Готов обсуждать эти и другие контраргументы.
+
Готов обсуждать эти и другие контраргументы и мифы.
=== В слабой аксиоматике нет ничего нового ===
=== В слабой аксиоматике нет ничего нового ===
Да, действительно, техника подсчёта перестановок давно и успешно используется в теорвере и матстате.
Да, действительно, техника подсчёта перестановок давно и успешно используется в теорвере и матстате.
-
В статистике есть довольно много «точных критериев», которые кем-то когда-то табулированы, но не приводятся в учебниках, и даже не во всех справочниках. Обычно ими рекомендуется пользоваться при малых выборках, а, начиная с выборок около 30 объектов переходить на асимптотические приближения: нормальное, хи-квадрат, и т.п.
+
В статистике есть довольно много «точных критериев», которые кем-то когда-то табулированы, но не приводятся в учебниках и даже в справочниках приводятся редко. Обычно ими рекомендуется пользоваться при малых выборках, а, начиная с выборок около 30 объектов, переходить на асимптотические приближения: нормальное, хи-квадрат, и т.п.
Точные критерии оказались в загоне из-за трудоёмкости их вычислиения и громоздких формул, которые редко удаётся уместить в одну строчку.
Точные критерии оказались в загоне из-за трудоёмкости их вычислиения и громоздких формул, которые редко удаётся уместить в одну строчку.
Теперь, когда мощные вычислители общедоступны, ничто не препятствует их более широкому применению.
Теперь, когда мощные вычислители общедоступны, ничто не препятствует их более широкому применению.
Строка 141: Строка 148:
Это открытый вопрос.
Это открытый вопрос.
Если такую теорию удастся построить, то её результаты будут справедливы для выборок любой длины, включая малые.
Если такую теорию удастся построить, то её результаты будут справедливы для выборок любой длины, включая малые.
 +
Заодно, возможно, многие комбинаторные результаты, до сих пор считавшиеся абстрактно математическими, найдут новые применения.
=== В слабой аксиоматике должны получаться более слабые результаты ===
=== В слабой аксиоматике должны получаться более слабые результаты ===
Слабая аксиоматика имеет более узкую область применимости.
Слабая аксиоматика имеет более узкую область применимости.
-
Однако многие результаты в ней получаются ''такие же'', как в сильной, поскольку предположения сильной (колмогоровской) аксиоматики часто оказываются избыточными.
+
Однако многие результаты в ней имеют ''тот же'' вид, что и в сильной, поскольку предположения сильной (колмогоровской) аксиоматики во многих случаях избыточны.
 +
Однако мы продолжаем ими пользоваться ''по инерции'', просто потому, что в институте нас так учили.
По-моему, профессиональный долг всякого нормального математика — очищать теории от избыточных предположений.
По-моему, профессиональный долг всякого нормального математика — очищать теории от избыточных предположений.
Строка 154: Строка 163:
Биномиальное, пуассоновское, нормальное распределения — это асимптотические приближения гипергеометрического распределения.
Биномиальное, пуассоновское, нормальное распределения — это асимптотические приближения гипергеометрического распределения.
Асимптотичность заложена во многих распределениях, активно используемых в математической статистике (том же хи-квадрат).
Асимптотичность заложена во многих распределениях, активно используемых в математической статистике (том же хи-квадрат).
-
''Но об этом никто не помнит''.
+
''Но об этом редко кто помнит''.
Слабая аксиоматика ограничивает свободу действий математика.
Слабая аксиоматика ограничивает свободу действий математика.
-
Предлагается забыть на время о блестящем аппарате асимптотических распределений и попробовать получить те же результаты, используя только палку и верёвку.
+
Предлагается забыть на время о блестящем аппарате асимптотических распределений и попробовать получить те же результаты, используя только простейшие средства — комбинаторный подсчёт доли разбиений выборки, удовлетворяющих некоторому условию.
=== Возникают сложности с оцениванием непрерывных случайных величин ===
=== Возникают сложности с оцениванием непрерывных случайных величин ===
 +
Непрерывную величину не хотелось бы заменять дискретной.
 +
Однако для получения некоторых оценок (в частности, оценок точности эмпирических предсказаний) специальным образом сделанная замена приводит к удивительно точным оценкам!
 +
Эта замена не универсальна — если изменить оцениваемый функционал, то должна измениться и дискретная аппроксимация непрерывной случайной величины.
 +
 +
Примеры скоро будут...
 +
 +
'''Гипотеза''':
[[Категория:Открытые проблемы и полемика]]
[[Категория:Открытые проблемы и полемика]]

Версия 16:32, 27 февраля 2008

Содержание

Мотивация

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

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

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

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

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

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

В любом эксперименте, прошедшем или будущем, может наблюдаться лишь конечное множество объектов X^L = (x_1,\ldots,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,\ldots,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 R — заданная функция, характеризующая величину отклонения 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://www.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»
Личные инструменты