Слабая вероятностная аксиоматика
Материал из MachineLearning.
Содержание |
Мотивация
Начну с цитирования классиков.
- А. Н. Колмогоров:
«Представляется важной задача освобождения всюду, где это возможно, от излишних вероятностных допущений. На независимой ценности чисто комбинаторного подхода к теории информации я неоднократно настаивал в своих лекциях.»
- Ученик А. Н. Колмогорова Ю. К. Беляев
(из предисловия к книге Вероятностные методы выборочного контроля): «Возникло глубокое убеждение, что в теории выборочных методов можно получить содержательные аналоги большинства основных утверждений теории вероятностей и математической статистики, которые к настоящему времени найдены в предположении взаимной независимости результатов измерений».
Современная теория вероятностей возникла из стремления объединить в рамках единого формализма частотное понятие вероятности, берущее начало от азартных игр, и континуальное, идущее от геометрических задач типа задачи Бюффона о вероятности попадания иглы в паркетную щель. В аксиоматике Колмогорова континуальное понятие берётся за основу как более общее. Ради этой общности в теорию вероятностей привносятся гипотезы сигма-аддитивности и измеримости — технические предположения из теории меры, имеющие довольно слабые эмпирические обоснования. Однако от них вполне можно отказаться в задачах анализа данных, где число наблюдений всегда конечно.
В слабой вероятностной аксиоматике рассматриваются только конечные выборки. Вводится чисто комбинаторное понятие вероятности, не требующее ни привлечения теории меры, ни предельных апереходов к бесконечным выборкам. Все вероятности оказываются непосредственно измеримыми в эксперименте. Слабая аксиоматика полностью согласуется c сильной (колмогоровской) аксиоматикой, но её область применимости ограничена задачами анализа данных. Рассматриваются два достаточно широких класса задач: эмпирическое предсказание и проверка статистических гипотез.
Слабая вероятностная аксиоматика
Аксиома только одна.
В любом эксперименте, прошедшем или будущем, может наблюдаться лишь конечное множество объектов
.
Обозначим через
группу всех
перестановок
элементов.
- Аксиома (о независимости элементов выборки).
Все перестановки генеральной выборки
имеют одинаковые шансы реализоваться.
Пусть на множестве выборок задан предикат .
Вероятностью события
будем называть долю перестановок, при которых предикат истинен (принимает значение 1):
.
Эта вероятность зависит от выборки .
Мы полагаем, что случайными являются не сами объекты, а только последовательность их появления.
В слабой аксиоматике термин вероятность понимается только как синоним «доли перестановок выборки».
Некоторые результаты
Несмотря на предельную упрощённость, в слабой аксиоматике удаётся сформулировать и доказать аналоги многих фундаментальных фактов теории вероятностей, математической статистики и статистического обучения:
- Закон больших чисел является тривиальным следствием свойств ГГР — гипергеометрического распределения. Точные (не завышенные) оценки скорости сходимости вычисляются через обратную функцию ГГР.
- Точные оценки скорости сходимости эмпирических распределений (критерий Смирнова) вычисляются через усечённый теругольник Паскаля.
- В теории Вапника-Червоненкиса слабая аксиоматика позволяет «узаконить» скользящий контроль. Известные теоретические верхние оценки обобщающей способности и скользящий контроль оказываются двумя разными способами оценивания одного и того же функционала.
- Удаётся количественно измерить основные факторы завышенности известных оценок обобщающей способности. Оказывается, что коэффициент разнообразия (shattering coeffitient), характеризующий сложность алгоритма, в реальных задачах принимает значения порядка десятков. Известные теоретические оценки чрезвычайно завышены и имеют порядок
.
- Получены точные оценки обобщающей способности для метода kNN, выражающиеся через профиль компактности выборки.
- Получены точные оценки обобщающей способности для монотонных алгоритмов классификации, выражающиеся через профиль монотонности выборки.
Здесь подробный текст.
Открытые задачи
- Ранговые статистические критерии в слабой аксиоматике.
- Оценки обобщающей способности для алгоритмов классификации, выражающиеся через профиль разделимости выборки.
- Оценки обобщающей способности устойчивых алгоритмов классификации (stability).
Полемика
Готов обсуждать следующие (и другие) контраргументы:
- В слабой аксиоматике нет ничего нового. Техника подсчёта перестановок давно и успешно используется в доказательствах.
- В более слабой аксиоматике должны получаться более слабые результаты.
- При комбинаторном подходе возникают сложности с оцениванием непрерывных случайных величин.
