Слабая вероятностная аксиоматика
Материал из MachineLearning.
м |
|||
| Строка 175: | Строка 175: | ||
Примеры скоро будут... | Примеры скоро будут... | ||
| - | |||
| - | |||
[[Категория:Открытые проблемы и полемика]] | [[Категория:Открытые проблемы и полемика]] | ||
Версия 17:05, 27 февраля 2008
Содержание |
Мотивация
Начну с цитирования классиков.
- А. Н. Колмогоров: «Представляется важной задача освобождения всюду, где это возможно, от излишних вероятностных допущений. На независимой ценности чисто комбинаторного подхода к теории информации я неоднократно настаивал в своих лекциях.»
- Ученик А. Н. Колмогорова Ю. К. Беляев (из предисловия к книге Вероятностные методы выборочного контроля): «Возникло глубокое убеждение, что в теории выборочных методов можно получить содержательные аналоги большинства основных утверждений теории вероятностей и математической статистики, которые к настоящему времени найдены в предположении взаимной независимости результатов измерений».
Современная теория вероятностей возникла из стремления объединить в рамках единого формализма частотное понятие вероятности, берущее начало от азартных игр, и континуальное, идущее от геометрических задач типа задачи Бюффона о вероятности попадания иглы в паркетную щель. В аксиоматике Колмогорова континуальное понятие берётся за основу как более общее. Ради этой общности в теорию вероятностей привносятся гипотезы сигма-аддитивности и измеримости — технические предположения из теории меры, имеющие довольно слабые эмпирические обоснования. Однако от них вполне можно отказаться в задачах анализа данных, где число наблюдений всегда конечно.
В слабой вероятностной аксиоматике рассматриваются только конечные выборки. Вводится чисто комбинаторное понятие вероятности, не требующее ни привлечения теории меры, ни предельных переходов к бесконечным выборкам. Все вероятности оказываются непосредственно измеримыми в эксперименте. Слабая аксиоматика полностью согласуется c сильной (колмогоровской) аксиоматикой, но её область применимости ограничена задачами анализа данных. Рассматриваются два достаточно широких класса задач: эмпирическое предсказание и проверка статистических гипотез.
Слабая вероятностная аксиоматика
Аксиома только одна.
В любом эксперименте, прошедшем или будущем, может наблюдаться лишь конечное множество объектов
.
Обозначим через
группу всех
перестановок
элементов,
— множество всех конечных выборок из
.
- Аксиома (о независимости элементов выборки). Все перестановки генеральной выборки
имеют одинаковые шансы реализоваться.
Пусть на множестве выборок задан предикат .
Вероятностью события
будем называть долю перестановок, при которых предикат истинен (принимает значение 1):
.
Эта вероятность зависит от выборки .
Мы полагаем, что случайными являются не сами объекты, а только последовательность их появления.
В слабой аксиоматике термин вероятность понимается только как синоним «доли перестановок выборки».
Случайная величина определяется просто как вещественная функция выборки.
Функция распределения вводится стандартным образом.
Матожидание вводится как среднее арифметическое по всем перестановкам, что формально совпадает с определением вероятности.
Задача эмпирического предсказания
Неформально задача эмпирического предсказания состоит в том, чтобы, получив выборку данных, предсказать определённые свойства аналогичных данных, которые станут известны позже, и оценить точность предсказания.
Пусть задано множество и функция
.
Рассмотрим эксперимент, в котором реализуется одно из равновероятных разбиений выборки
на две подвыборки
и
.
После реализации разбиения
наблюдателю сообщается подвыборка
.
Не зная скрытой подвыборки , он должен
построить предсказывающую функцию
, значение которой
на наблюдаемой подвыборке
приближало бы неизвестное истинное значение
.
Необходимо также оценить надёжность предсказания, то есть указать невозрастающую оценочную функцию такую, что
,
где — заданная функция, характеризующая величину отклонения
предсказанного значения
от неизвестного истинного значения
.
Некоторые результаты
Несмотря на предельную упрощённость, в слабой аксиоматике удаётся сформулировать и доказать аналоги многих фундаментальных фактов теории вероятностей, математической статистики и статистического обучения:
- Закон больших чисел является тривиальным следствием свойств ГГР — гипергеометрического распределения. Точные (не завышенные) оценки скорости сходимости вычисляются через обратную функцию ГГР.
- Точные оценки скорости сходимости эмпирических распределений (критерий Смирнова) вычисляются через усечённый теругольник Паскаля.
- В теории Вапника-Червоненкиса слабая аксиоматика позволяет «узаконить» скользящий контроль. Известные теоретические верхние оценки обобщающей способности и скользящий контроль оказываются двумя разными способами оценивания одного и того же функционала.
- Удаётся количественно измерить основные факторы завышенности известных оценок обобщающей способности. Оказывается, что коэффициент разнообразия (shattering coeffitient), характеризующий сложность алгоритма, в реальных задачах принимает значения порядка десятков. Известные теоретические оценки чрезвычайно завышены и имеют порядок
.
- Получены точные оценки обобщающей способности для метода kNN, выражающиеся через профиль компактности выборки.
- Получены оценки обобщающей способности для монотонных алгоритмов классификации, выражающиеся через профиль монотонности выборки. Хотя эти оценки не являются точными, они гораздо точнее тех, которые основаны на ёмкости класса монотонных функций [Joseph Sill, 1998])
Подробнее:
Комбинаторный подход к оценке качества обучаемых алгоритмов. Математические вопросы кибернетики / Под ред. О. Б. Лупанов. — М.: Физматлит, 2004. — Т. 13. — С. 5–36.
Комбинаторная вероятность и точность оценок обобщающей способности. Pattern Regognition and Image Analysis. 2008 (принято в печать).
Открытые задачи (сюда можно добавлять разделы)
Ранговые критерии
Гипотеза: многие ранговые критерии могут быть построены чисто комбинаторными средствами.
Для критерия Вилкоксона, медианного критерия, критерия знаков, и некоторых других это практически очевидно. Фактически, именно так они и строятся. Однако для построения общей теории ранговых критериев в слабой аксиоматике, возможно, придётся искать какую-то новую технику оценивания мощности критериев.
Профиль разделимости
Известно, что максимизация отступов (margin) объектов приводит к повышению обобщающей способности классификатора. «Правильное» распределение отступов похоже на «ступеньку»: шумовые объекты (выбросы) должны получить отрицательные отступы, эталоны классов — большие положительные отступы, пограничных объектов должно быть как можно меньше. Тогда классификация будет наиболее надёжной. Как это обосновать?
Известен ряд алгоритмов классификации, основанных на явной максимизации отступов.
Для этого используются различные функции потерь, зависящие от отступа .
В бустинге (AdaBoost) это
.
В машинах опорных векторов (SVM) это
.
В логистической регрессии
Профилем разделимости будем называть эмпирическое распределение отступов.
Возникает вопрос: как должна выглядеть «правильная» функция потерь, минимизация которой давала бы алгоритм с наилучшей обобщающей способностью?
Гипотеза: скорее всего, функционал качества выражается через свёртку профиля разделимости с некими комбинаторными коэффициентами (как это уже оказалось для 1NN и монотонных классификаторов).
Профиль устойчивости
Известна целая серия оценок обобщающей способности для алгоритмов классификации, обладающих свойством устойчивости (или стабильности, в оригинале stability). С ними есть две проблемы. Во-первых, все эти оценки сильно завышены. Во-вторых, до сих пор не выработано «единственно правильное» определение стабильности. Предложено около двух десятков определений, между которыми установлены связи «сильнее—слабее». Всё это говорит о том, что явление стабильности по-настоящему ещё не понято.
Профиль устойчивости показывает, насколько изменяются классификации получаемого алгоритма, если состав обучающей выборки изменяется на m объектов.
Гипотеза: скорее всего, функционал качества и в этом случае выражается через свёртку профиля устойчивости с некими комбинаторными коэффициентами.
Полемика (сюда можно добавлять разделы)
Готов обсуждать эти и другие контраргументы и мифы.
В слабой аксиоматике нет ничего нового
Да, действительно, техника подсчёта перестановок давно и успешно используется в теорвере и матстате. В статистике есть довольно много «точных критериев», которые кем-то когда-то табулированы, но не приводятся в учебниках и даже в справочниках приводятся редко. Обычно ими рекомендуется пользоваться при малых выборках, а, начиная с выборок около 30 объектов, переходить на асимптотические приближения: нормальное, хи-квадрат, и т.п. Точные критерии оказались в загоне из-за трудоёмкости их вычислиения и громоздких формул, которые редко удаётся уместить в одну строчку. Теперь, когда мощные вычислители общедоступны, ничто не препятствует их более широкому применению. Кроме того, комбинаторный вывод точных критериев во многих случаях элементарен.
Новой является следующая постановка вопроса: какую часть современной статистической теории можно построить, опираясь только на комбинаторику, без привлечения теории меры и асимптотических приближений? Это открытый вопрос. Если такую теорию удастся построить, то её результаты будут справедливы для выборок любой длины, включая малые. Заодно, возможно, многие комбинаторные результаты, до сих пор считавшиеся абстрактно математическими, найдут новые применения.
В слабой аксиоматике должны получаться более слабые результаты
Слабая аксиоматика имеет более узкую область применимости. Однако многие результаты в ней имеют тот же вид, что и в сильной, поскольку предположения сильной (колмогоровской) аксиоматики во многих случаях избыточны. Однако мы продолжаем ими пользоваться по инерции, просто потому, что в институте нас так учили. По-моему, профессиональный долг всякого нормального математика — очищать теории от избыточных предположений.
Тогде почему в слабой аксиоматике могут получаться более сильные результаты? Это происходит по субъективным причинам. В сильной аксиоматике есть хорошо разработанный аппарат асимптотических оценок. Само определение вероятности через предельный переход по сути своей асимптотично. Биномиальное, пуассоновское, нормальное распределения — это асимптотические приближения гипергеометрического распределения. Асимптотичность заложена во многих распределениях, активно используемых в математической статистике (том же хи-квадрат). Но об этом редко кто помнит.
Слабая аксиоматика ограничивает свободу действий математика. Предлагается забыть на время о блестящем аппарате асимптотических распределений и попробовать получить те же результаты, используя только простейшие средства — комбинаторный подсчёт доли разбиений выборки, удовлетворяющих некоторому условию.
Возникают сложности с оцениванием непрерывных случайных величин
Непрерывную величину не хотелось бы заменять дискретной. Однако для получения некоторых оценок (в частности, оценок точности эмпирических предсказаний) специальным образом сделанная замена приводит к удивительно точным оценкам! Эта замена не универсальна — если изменить оцениваемый функционал, то должна измениться и дискретная аппроксимация непрерывной случайной величины.
Примеры скоро будут...
