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

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

(Различия между версиями)
Перейти к: навигация, поиск
м
м
Строка 1: Строка 1:
-
== Мотивация ==
+
{{stop|Содержание=
 +
'''Статья о незавершённом исследовании'''<br/>
 +
Статья является полемической.
 +
Автор готов её обсудить и предоставить дополнительный материал {{S|— [[Участник:Vokov|К.В.Воронцов]] 21:04, 29 марта 2008 (MSK)}}.
 +
}}
 +
 
 +
== Мотивация ==
Начну с цитирования классиков.
Начну с цитирования классиков.
-
* '''А. Н. Колмогоров''': «Представляется важной задача освобождения всюду, где это возможно, от излишних вероятностных допущений. На независимой ценности чисто комбинаторного подхода к теории информации я неоднократно настаивал в своих лекциях.»
+
* '''А. Н. Колмогоров''': «Представляется важной задача освобождения всюду, где это возможно, от излишних вероятностных допущений. На независимой ценности чисто комбинаторного подхода к теории информации я неоднократно настаивал в своих лекциях.»
-
* Ученик А. Н. Колмогорова '''Ю. К. Беляев''' (из предисловия к книге ''Вероятностные методы выборочного контроля''): «Возникло глубокое убеждение, что в теории выборочных методов можно получить содержательные аналоги большинства основных утверждений теории вероятностей и математической статистики, которые к настоящему времени найдены в предположении взаимной независимости результатов измерений».
+
* Ученик А. Н. Колмогорова '''Ю. К. Беляев''' (из предисловия к книге ''Вероятностные методы выборочного контроля''): «Возникло глубокое убеждение, что в теории выборочных методов можно получить содержательные аналоги большинства основных утверждений теории вероятностей и математической статистики, которые к настоящему времени найдены в предположении взаимной независимости результатов измерений».
-
Современная теория вероятностей возникла из стремления объединить в рамках единого формализма частотное понятие вероятности, берущее начало от азартных игр, и континуальное, идущее от геометрических задач типа задачи Бюффона
+
Современная [[теория вероятностей]] возникла из стремления объединить в рамках единого формализма частотное понятие вероятности, берущее начало от азартных игр, и континуальное, идущее от геометрических задач типа задачи Бюффона
о вероятности попадания иглы в паркетную щель.
о вероятности попадания иглы в паркетную щель.
-
В аксиоматике Колмогорова континуальное понятие берётся за основу как более общее.
+
В аксиоматике Колмогорова континуальное понятие берётся за основу как более общее.
-
Ради этой общности в теорию вероятностей привносятся гипотезы сигма-аддитивности и измеримости — технические предположения из теории меры, имеющие довольно слабые эмпирические обоснования.
+
Ради этой общности в теорию вероятностей привносятся гипотезы сигма-аддитивности и измеримости — технические предположения из теории меры, имеющие довольно слабые эмпирические обоснования.
Однако от них вполне можно отказаться в задачах анализа данных, где число наблюдений конечно.
Однако от них вполне можно отказаться в задачах анализа данных, где число наблюдений конечно.
-
В ''слабой вероятностной аксиоматике'' рассматриваются только конечные выборки.
+
В ''слабой вероятностной аксиоматике'' рассматриваются только конечные выборки.
-
Вводится чисто комбинаторное понятие вероятности, не требующее ни привлечения теории меры, ни предельных переходов к бесконечным выборкам.
+
Вводится чисто комбинаторное понятие вероятности, не требующее ни привлечения теории меры, ни предельных переходов к бесконечным выборкам.
-
Все вероятности оказываются непосредственно измеримыми в эксперименте.
+
Все вероятности оказываются непосредственно измеримыми в эксперименте.
Слабая аксиоматика полностью согласуется c сильной (колмогоровской) аксиоматикой, но её область применимости ограничена задачами анализа данных.
Слабая аксиоматика полностью согласуется c сильной (колмогоровской) аксиоматикой, но её область применимости ограничена задачами анализа данных.
Рассматриваются два достаточно широких класса задач:
Рассматриваются два достаточно широких класса задач:
-
эмпирическое предсказание и
+
[[эмпирическое предсказание]] и
-
проверка статистических гипотез.
+
[[проверка статистических гипотез]].
-
== Слабая вероятностная аксиоматика ==
+
== Слабая вероятностная аксиоматика ==
-
В любом эксперименте, прошедшем или будущем, может наблюдаться лишь конечное множество объектов
+
В любом эксперименте, прошедшем или будущем, может наблюдаться лишь конечное множество объектов
-
<tex>X^L = (x_1,\ldots,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>.
-
Аксиома только одна.
+
Аксиома только одна.
* '''Аксиома (о независимости элементов выборки).''' Все перестановки генеральной выборки <tex>\tau X^L,\; \tau\in S_L</tex> имеют одинаковые шансы реализоваться.
* '''Аксиома (о независимости элементов выборки).''' Все перестановки генеральной выборки <tex>\tau X^L,\; \tau\in S_L</tex> имеют одинаковые шансы реализоваться.
Строка 42: Строка 48:
В слабой аксиоматике термин ''вероятность'' понимается только как синоним «доли перестановок выборки».
В слабой аксиоматике термин ''вероятность'' понимается только как синоним «доли перестановок выборки».
-
''Случайная величина'' определяется просто как вещественная функция выборки.
+
''Случайная величина'' определяется просто как вещественная функция выборки.
-
''Функция распределения'' вводится стандартным образом.
+
''Функция распределения'' вводится стандартным образом.
-
''Матожидание'' вводится как среднее арифметическое по всем перестановкам, что формально совпадает с определением вероятности.
+
''Матожидание'' вводится как среднее арифметическое по всем перестановкам, что формально совпадает с определением вероятности.
== Задача эмпирического предсказания ==
== Задача эмпирического предсказания ==
Строка 57: Строка 63:
После реализации разбиения <tex>n</tex> наблюдателю сообщается подвыборка <tex>X^\ell_n</tex>.
После реализации разбиения <tex>n</tex> наблюдателю сообщается подвыборка <tex>X^\ell_n</tex>.
-
Не зная скрытой подвыборки <tex>X^k_n</tex>, он должен
+
Не зная скрытой подвыборки <tex>X^k_n</tex>, он должен
-
построить ''предсказывающую функцию'' <tex>\hat T:\: X^{*} \to Q</tex>, значение которой
+
построить ''предсказывающую функцию'' <tex>\hat T:\: X^{*} \to Q</tex>, значение которой
<tex>\hat T_n = \hat T(X^\ell_n)</tex> на наблюдаемой подвыборке <tex>X^\ell_n</tex>
<tex>\hat T_n = \hat T(X^\ell_n)</tex> на наблюдаемой подвыборке <tex>X^\ell_n</tex>
-
приближало бы неизвестное истинное значение
+
приближало бы неизвестное истинное значение
<tex>T_n = T(X^k_n,X^\ell_n)</tex>,
<tex>T_n = T(X^k_n,X^\ell_n)</tex>,
существенно зависящее от скрытых данных.
существенно зависящее от скрытых данных.
Строка 68: Строка 74:
<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>
-
где <tex>d:\: Q\times Q\to R</tex> — заданная функция, характеризующая величину отклонения
+
где <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>.
Строка 75: Строка 81:
Несмотря на предельную упрощённость, в слабой аксиоматике удаётся сформулировать и доказать аналоги многих фундаментальных фактов теории вероятностей, математической статистики и статистического обучения:
Несмотря на предельную упрощённость, в слабой аксиоматике удаётся сформулировать и доказать аналоги многих фундаментальных фактов теории вероятностей, математической статистики и статистического обучения:
-
* Закон больших чисел является тривиальным следствием свойств ГГР — гипергеометрического распределения. Точные (не завышенные) оценки скорости сходимости вычисляются через обратную функцию ГГР.
+
* [[Закон больших чисел]] является тривиальным следствием свойств ГГР — [[гипергеометрическое распределение|гипергеометрического распределения]]. Точные (не завышенные) оценки скорости сходимости вычисляются через обратную функцию ГГР.
-
* Точные оценки скорости сходимости эмпирических распределений (критерий Смирнова) вычисляются через ''усечённый теругольник Паскаля''.
+
* Точные оценки скорости сходимости эмпирических распределений ([[критерий Смирнова]]) вычисляются через ''[[усечённый треугольник Паскаля]]''.
-
* В теории Вапника-Червоненкиса слабая аксиоматика позволяет «узаконить» скользящий контроль. Известные теоретические верхние оценки обобщающей способности и скользящий контроль оказываются двумя разными способами оценивания одного и того же функционала.
+
* В [[Теория Вапника-Червоненкиса|теории Вапника-Червоненкиса]] слабая аксиоматика позволяет «узаконить» [[скользящий контроль]]. Известные теоретические верхние оценки [[обобщающая способность|обобщающей способности]] и скользящий контроль оказываются двумя разными способами оценивания одного и того же функционала.
-
* Удаётся количественно измерить основные факторы завышенности известных оценок обобщающей способности. Оказывается, что коэффициент разнообразия (shattering coeffitient), характеризующий сложность алгоритма, в реальных задачах принимает значения порядка десятков. Известные теоретические оценки чрезвычайно завышены и имеют порядок <tex>10^5-10^{11}</tex>.
+
* Удаётся количественно измерить основные факторы завышенности известных оценок обобщающей способности. Оказывается, что [[коэффициент разнообразия]] (shattering coeffitient), характеризующий [[сложность алгоритма]], в реальных задачах принимает значения порядка от единиц до десятков, изредка доходя до сотен. Известные теоретические оценки чрезвычайно завышены и имеют порядок <tex>10^5-10^{11}</tex>.
-
* Получены точные оценки обобщающей способности для метода kNN, выражающиеся через ''профиль компактности'' выборки.
+
* Получены точные оценки обобщающей способности для [[метод ближайших сеседей|метода kNN]], выражающиеся через ''профиль компактности'' выборки.
* Получены оценки обобщающей способности для монотонных алгоритмов классификации, выражающиеся через ''профиль монотонности'' выборки. Хотя эти оценки не являются точными, они гораздо точнее тех, которые основаны на ёмкости класса монотонных функций [Joseph Sill, 1998])
* Получены оценки обобщающей способности для монотонных алгоритмов классификации, выражающиеся через ''профиль монотонности'' выборки. Хотя эти оценки не являются точными, они гораздо точнее тех, которые основаны на ёмкости класса монотонных функций [Joseph Sill, 1998])
Строка 89: Строка 95:
'''Гипотеза''':
'''Гипотеза''':
-
многие ранговые критерии могут быть построены чисто комбинаторными средствами.
+
большинство [[ранговый критерий|ранговых критериев]] могут быть построены чисто комбинаторными средствами.
-
Для критерия Вилкоксона, медианного критерия, критерия знаков, и некоторых других это практически очевидно. Фактически, именно так они и строятся.
+
Для [[критерий Вилкоксона|критерия Вилкоксона]], [[медианный критерий|медианного критерия]], [[критерий знаков|критерия знаков]], и некоторых других это практически очевидно. Фактически, именно так они и строятся.
-
Однако для построения общей теории ранговых критериев в слабой аксиоматике, возможно, придётся искать какую-то новую технику оценивания мощности критериев.
+
Однако для построения общей теории ранговых критериев в слабой аксиоматике, возможно, придётся искать какую-то новую технику оценивания мощности критериев.
=== Профиль разделимости ===
=== Профиль разделимости ===
-
Известно, что максимизация отступов (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>
-
''Профилем разделимости'' будем называть эмпирическое распределение отступов.
+
''Профилем разделимости'' будем называть [[эмпирическое распределение]] отступов.
-
Возникает вопрос: как должна выглядеть «правильная» функция потерь, минимизация которой давала бы алгоритм с наилучшей обобщающей способностью?
+
Возникает вопрос: как должна выглядеть «правильная» функция потерь, минимизация которой давала бы алгоритм с наилучшей обобщающей способностью?
-
'''Гипотеза''':
+
'''Гипотеза''':
-
скорее всего, функционал качества выражается через свёртку профиля разделимости с некими комбинаторными коэффициентами (как это уже оказалось для 1NN и монотонных классификаторов).
+
скорее всего, функционал качества выражается через свёртку профиля разделимости с некими комбинаторными коэффициентами (как это уже оказалось для 1NN и монотонных классификаторов).
=== Профиль устойчивости ===
=== Профиль устойчивости ===
-
Известна целая серия оценок обобщающей способности для алгоритмов классификации, обладающих свойством устойчивости (или стабильности, в оригинале stability).
+
Известна целая серия оценок обобщающей способности для алгоритмов классификации, обладающих свойством [[устойчивость обучения|устойчивости]] (или стабильности, в оригинале stability).
-
С ними есть две проблемы.
+
С ними есть две проблемы.
Во-первых, все эти оценки сильно завышены.
Во-первых, все эти оценки сильно завышены.
Во-вторых, до сих пор не выработано «единственно правильное» определение стабильности.
Во-вторых, до сих пор не выработано «единственно правильное» определение стабильности.
Предложено около двух десятков определений, между которыми установлены связи «сильнее—слабее».
Предложено около двух десятков определений, между которыми установлены связи «сильнее—слабее».
-
Всё это говорит о том, что явление стабильности по-настоящему ещё не понято.
+
Всё это говорит о том, что явление стабильности по-настоящему ещё не понято.
-
''Профиль устойчивости'' <tex>S(m)</tex> показывает, насколько изменяются классификации получаемого алгоритма, если состав обучающей выборки изменяется на <i>m</i> объектов.
+
''Профиль устойчивости'' <tex>S(m)</tex> показывает, насколько изменяются классификации получаемого алгоритма, если состав обучающей выборки изменяется на ''m'' объектов.
-
'''Гипотеза''':
+
'''Гипотеза''':
-
скорее всего, функционал качества и в этом случае выражается через свёртку профиля устойчивости с некими комбинаторными коэффициентами.
+
скорее всего, функционал качества и в этом случае выражается через свёртку профиля устойчивости с некими комбинаторными коэффициентами.
Строка 137: Строка 143:
Да, действительно, техника подсчёта перестановок давно и успешно используется в теорвере и матстате.
Да, действительно, техника подсчёта перестановок давно и успешно используется в теорвере и матстате.
-
В статистике есть довольно много «точных критериев», которые кем-то когда-то табулированы, но не приводятся в учебниках и даже в справочниках приводятся редко. Обычно ими рекомендуется пользоваться при малых выборках, а, начиная с выборок около 30 объектов, переходить на асимптотические приближения: нормальное, хи-квадрат, и т.п.
+
В статистике есть довольно много «точных критериев», которые кем-то когда-то табулированы, но не приводятся в учебниках и даже в справочниках приводятся редко. Обычно ими рекомендуется пользоваться при малых выборках, а, начиная с выборок около 30 объектов, переходить на асимптотические приближения: нормальное, хи-квадрат, и т. п.
-
Точные критерии оказались в загоне из-за трудоёмкости их вычислиения и громоздких формул, которые редко удаётся уместить в одну строчку.
+
Точные критерии оказались в загоне из-за трудоёмкости их вычислиения и громоздких формул, которые редко удаётся уместить в одну строчку.
-
Теперь, когда мощные вычислители общедоступны, ничто не препятствует их более широкому применению.
+
Теперь, когда мощные вычислители повсеместно доступны, ничто не препятствует их более широкому применению.
-
Кроме того, комбинаторный вывод точных критериев во многих случаях элементарен.
+
Кроме того, комбинаторный вывод точных критериев во многих случаях элементарен.
Новой является следующая постановка вопроса:
Новой является следующая постановка вопроса:
''какую часть современной статистической теории можно построить, опираясь только на комбинаторику, без привлечения теории меры и асимптотических приближений?''
''какую часть современной статистической теории можно построить, опираясь только на комбинаторику, без привлечения теории меры и асимптотических приближений?''
Это открытый вопрос.
Это открытый вопрос.
-
Если такую теорию удастся построить, то её результаты будут справедливы для выборок любой длины, включая малые.
+
Если такую теорию удастся построить, то её результаты будут справедливы для выборок любой длины, включая малые.
-
Заодно, возможно, многие комбинаторные результаты, до сих пор считавшиеся абстрактно математическими, найдут новые применения.
+
Заодно, возможно, многие комбинаторные результаты, до сих пор считавшиеся абстрактно математическими, найдут новые применения.
=== В слабой аксиоматике должны получаться более слабые результаты ===
=== В слабой аксиоматике должны получаться более слабые результаты ===
-
Слабая аксиоматика имеет более узкую область применимости.
+
Слабая аксиоматика имеет более узкую область применимости.
Однако многие результаты в ней имеют ''тот же'' вид, что и в сильной, поскольку предположения сильной (колмогоровской) аксиоматики во многих случаях избыточны.
Однако многие результаты в ней имеют ''тот же'' вид, что и в сильной, поскольку предположения сильной (колмогоровской) аксиоматики во многих случаях избыточны.
-
Профессиональный долг всякого добросовестного математика — очищать теории от избыточных предположений.
+
Профессиональный долг всякого добросовестного математика — очищать теории от избыточных предположений.
Почему в слабой аксиоматике могут получаться более сильные результаты?
Почему в слабой аксиоматике могут получаться более сильные результаты?
-
Это происходит по субъективным причинам.
+
Это происходит по субъективным причинам.
В сильной аксиоматике есть хорошо разработанный аппарат асимптотических оценок.
В сильной аксиоматике есть хорошо разработанный аппарат асимптотических оценок.
-
Само определение вероятности через предельный переход по сути своей асимптотично.
+
Само определение вероятности через предельный переход по сути своей асимптотично.
-
Биномиальное, пуассоновское, нормальное распределения — это асимптотические приближения гипергеометрического распределения.
+
[[Биномиальное распределение|Биномиальное]], [[пуассоновское распределение|пуассоновское]], [[нормальное распределение|нормальное]] распределения — это асимптотические приближения гипергеометрического распределения.
-
Асимптотичность заложена во многих распределениях, активно используемых в математической статистике (том же хи-квадрат).
+
Асимптотичность заложена во многих распределениях, активно используемых в математической статистике (том же [[хи-квадрат распределение|хи-квадрат]]).
''Но об этом редко кто помнит''.
''Но об этом редко кто помнит''.
Слабая аксиоматика ограничивает свободу действий математика.
Слабая аксиоматика ограничивает свободу действий математика.
-
Предлагается забыть на время о блестящем аппарате асимптотических приближений и теории меры, и задаться целью получить максимум содержательных результатов с использованием минимума средств. Таким простейшим (но точным) средством и является комбинаторный подсчёт доли разбиений выборки, удовлетворяющих заданным условиям.
+
Предлагается забыть на время о блестящем аппарате асимптотических приближений и теории меры, и задаться целью получить максимум содержательных результатов с использованием минимума средств. Таким простейшим (но точным) средством и является комбинаторный подсчёт доли разбиений выборки, удовлетворяющих заданным условиям.
=== Возникают сложности с оцениванием непрерывных случайных величин ===
=== Возникают сложности с оцениванием непрерывных случайных величин ===
-
Непрерывную величину не хотелось бы заменять дискретной.
+
Непрерывную величину не хотелось бы заменять дискретной.
-
Очевидно, при этом потеряется много ценной информации.
+
Очевидно, при этом потеряется много ценной информации.
Однако для получения некоторых оценок (в частности, оценок точности эмпирических предсказаний) специальным образом сделанная замена приводит к удивительно точным оценкам!
Однако для получения некоторых оценок (в частности, оценок точности эмпирических предсказаний) специальным образом сделанная замена приводит к удивительно точным оценкам!
-
Эта замена не универсальна — если изменить оцениваемый функционал, то изменится и дискретная аппроксимация непрерывной случайной величины.
+
Эта замена не универсальна — если изменить оцениваемый функционал, то изменится и дискретная аппроксимация непрерывной случайной величины.
-
Примеры скоро будут...
+
Примеры скоро будут…
== Литература ==
== Литература ==
-
# Воронцов К. В. [http://www.ccas.ru/frc/papers/voron04mpc.pdf Комбинаторный подход к оценке качества обучаемых алгоритмов]. Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36.
+
# Воронцов К. В. [http://www.ccas.ru/frc/papers/voron04mpc.pdf Комбинаторный подход к оценке качества обучаемых алгоритмов]. Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5-36.
# Воронцов К. В. [http://www.ccas.ru/voron/download/voron08pria.pdf Комбинаторная вероятность и точность оценок обобщающей способности]. Pattern Regognition and Image Analysis. 2008 (принято в печать).
# Воронцов К. В. [http://www.ccas.ru/voron/download/voron08pria.pdf Комбинаторная вероятность и точность оценок обобщающей способности]. Pattern Regognition and Image Analysis. 2008 (принято в печать).
== Ссылки ==
== Ссылки ==
-
# [[Участник:Vokov|К. В. Воронцов]] — страница на MachineLearning.RU.
+
# [[Участник:Vokov|К. В. Воронцов]] — страница на MachineLearning.RU.
-
# [http://www.ccas.ru/voron К.&nbsp;В.&nbsp;Воронцов] — страница на сайте ВЦ РАН.
+
# [http://www.ccas.ru/voron К.&nbsp;В.&nbsp;Воронцов] — страница на сайте ВЦ РАН.
[[Категория:Открытые проблемы и полемика]]
[[Категория:Открытые проблемы и полемика]]
 +
[[Категория:Теория вычислительного обучения]]

Версия 18:04, 29 марта 2008

{{{1}}}


Содержание

Мотивация

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

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

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

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

Более подробно результаты изложены в публикациях, см. ниже разделы Литература и Ссылки.

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

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

Гипотеза: большинство ранговых критериев могут быть построены чисто комбинаторными средствами.

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

Непрерывную величину не хотелось бы заменять дискретной. Очевидно, при этом потеряется много ценной информации. Однако для получения некоторых оценок (в частности, оценок точности эмпирических предсказаний) специальным образом сделанная замена приводит к удивительно точным оценкам! Эта замена не универсальна — если изменить оцениваемый функционал, то изменится и дискретная аппроксимация непрерывной случайной величины.

Примеры скоро будут…

Литература

  1. Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов. Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5-36.
  2. Воронцов К. В. Комбинаторная вероятность и точность оценок обобщающей способности. Pattern Regognition and Image Analysis. 2008 (принято в печать).

Ссылки

  1. К. В. Воронцов — страница на MachineLearning.RU.
  2. К. В. Воронцов — страница на сайте ВЦ РАН.
Источник — «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»
Личные инструменты