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

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

Версия 20:12, 26 февраля 2008

Мотивация

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

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

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

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

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

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

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

В любом эксперименте, прошедшем или будущем, может наблюдаться лишь конечное множество объектов . Обозначим через группу всех перестановок элементов.

• Аксиома (о независимости элементов выборки). Все перестановки генеральной выборки имеют одинаковые шансы реализоваться.

Пусть на множестве выборок задан предикат . Вероятностью события будем называть долю перестановок, при которых предикат истинен (принимает значение 1):

Эта вероятность зависит от выборки . Мы полагаем, что случайными являются не сами объекты, а только последовательность их появления. В слабой аксиоматике термин вероятность понимается только как синоним «доли перестановок выборки».

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

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

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

Здесь черновик пишущейся диссертации.

Открытые задачи

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

Полемика

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

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