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

В любом эксперименте, прошедшем или будущем, может наблюдаться лишь конечное множество объектов $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 объектов, переходить на асимптотические приближения: нормальное, хи-квадрат, и т. п. Точные критерии оказались в загоне из-за трудоёмкости их вычислиения и громоздких формул, которые редко удаётся уместить в одну строчку. Теперь, когда мощные вычислители повсеместно доступны, ничто не препятствует их более широкому применению. Кроме того, комбинаторный вывод точных критериев во многих случаях элементарен.

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

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

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

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

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

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

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

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

Литература

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

Ссылки

К. В. Воронцов — страница на MachineLearning.RU.
К. В. Воронцов — страница на сайте ВЦ РАН.

Источник — «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»

Категории: Виртуальные семинары | Открытые проблемы и полемика | Теория вычислительного обучения

@@ Строка 86: / Строка 86: @@
 * Удаётся количественно измерить основные факторы завышенности известных оценок обобщающей способности. Оказывается, что [[коэффициент разнообразия]] (shattering coeffitient), характеризующий [[сложность алгоритма]], в реальных задачах принимает значения порядка от единиц до десятков, изредка доходя до сотен. Известные теоретические оценки чрезвычайно завышены и имеют порядок <tex>10^5-10^{11}</tex>.
 * Получены точные оценки обобщающей способности для [[метод ближайших сеседей|метода kNN]], выражающиеся через ''профиль компактности'' выборки.
-* Получены оценки обобщающей способности для монотонных алгоритмов классификации, выражающиеся через ''профиль монотонности'' выборки. Хотя эти оценки не являются точными, они гораздо точнее тех, которые основаны на ёмкости класса монотонных функций [Joseph Sill, 1998])
+* Получены оценки обобщающей способности для монотонных [[алгоритм]]ов классификации, выражающиеся через ''профиль монотонности'' выборки. Хотя эти оценки не являются точными, они гораздо точнее тех, которые основаны на ёмкости класса монотонных функций [Joseph Sill, 1998])
 Более подробно результаты изложены в публикациях, см. ниже разделы '''Литература''' и '''Ссылки'''.

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

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

Версия 19:31, 18 октября 2008

Содержание

Мотивация