Комбинаторная теория надёжности обучения по прецедентам

• Автор: Воронцов, Константин Вячеславович
• Шифр специальности: 05.13.17
• Научная степень: Докторская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 272 с. : ил.

Оглавление
Введение

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

1.1 Основная аксиома.

1.1.1 Задачи эмпирического предсказания

1.1.2 Обращение оценок.

1.1.3 Наблюдаемые и ненаблюдаемые оценки

1.1.4 Эмпирическое оценивание вероятности

1.1.5 Замечания и интерпретации

1.2 Задача оценивания частоты события.

1.2.1 Свойства гипсргеометрического распределения.

1.2.2 Закон больших чисел в слабой аксиоматике.
1.2.3 Проблема неизвестного т и наблюдаемые оценки
1.3 Задача оценивания функции распределения
1.3.1 Усеченный треугольник Паскаля .
1.3.2 Теорема Смирнова в слабой аксиоматике
1.3.3 Обобщение на случай вариационного ряда со связками
1.4 Некоторые непараметрические критерии и доверительные оценки .
1.4.1 Доверительное оценивание.
1.4.2 Доверительные интервалы для квантилей
1.4.3 Критерий знаков
1.4.4 Критерий УилкоксонаМаннаУитни
1.5 Задача оценивания вероятности переобучения.
1.5.1 Основные понятия и определения.

1.5.2 Простой частный случай один алгоритм
1.5.3 Коэффициенты разнообразия и профиль расслоения.
1.5.4 Принцип равномерной сходимости и УСоценка
1.5.5 Степень некорректности и е влияние на переобучение.
1.5.6 Проблема завышенности УСоценок
1.5.7 Причины завышенности УСоцснок
1.6 Основные выводы
2 Теория статистического обучения
2.1 Теория ВапникаЧервоненкиса
2.1.1 Основные предположения УСтеории.
2.1.2 Основные результаты УСтеории
2.1.3 Бритва Оккама
2.2 Оценки, зависящие от задачи .
2.2.1 Локальные меры сложности.
2.2.2 Оценки, учитывающие отступы объектов.
2.2.3 Композиции алгоритмов
2.2.4 Стохастические методы обучения байесовский подход.
2.3 Оценки, учитывающие расслоение алгоритмов
2.3.1 Самооценивающие методы обучения .
2.3.2 Функции удачности. Подсемейства, зависящие от выборки .
2.3.3 Оценка расслоения но Лангфорду.
2.4 Оценки, учитывающие сходство алгоритмов
2.4.1 Кластеризация семейства алгоритмов.
2.4.2 Связные семейства алгоритмов.
2.4.3 Устойчивость метода обучения.
2.5 Скользящий контроль
2.6 Основные выводы
3 Эмпирический анализ факторов завышенности УСоценок
3.1 Эффективный локальный коэффициент разнообразия.
3.1.1 Определение и эмпирическое измерение ЭЛКР
3.1.2 Эмпирическое измерение факторов завышенности
3.1.3 О понятии эффективной мкости ио Вапиику
3.2 Эксперименты на реальных данных
3.2.1 Логические алгоритмы классификации
3.2.2 Измерение факторов завышенности для закономерностей
3.2.3 Эксперименты и выводы.
3.3 Эксперименты на модельных данных.
3.3.1 Семейство из двух алгоритмов.
3.3.2 Монотонная цепочка алгоритмов.
3.4 Основные выводы
4 Точные оценки вероятности переобучения
4.1 Общие оценки вероятности переобучения.
4.1.1 О разновидностях минимизации эмпирического риска
4.1.2 Порождающие и запрещающие множества объектов
4.1.3 Блочное вычисление вероятности переобучения.
4.2 Модельные семейства алгоритмов.
4.2.1 Семейство из двух алгоритмов
4.2.2 Слой булева куба
4.2.3 Интервал булева куба
4.2.4 Расслоение интервала булева куба
4.2.5 Монотонная цепочка алгоритмов.
4.2.6 Унимодальная цепочка алгоритмов.
4.2.7 Единичная окрестность лучшего азгоритма.
4.2.8 О некоторых других модельных семействах.
4.3 Рекуррентное вычисление вероятности переобучения.
4.3.1 Добавление одного алгоритма.
4.3.2 Вычисление вероятности переобучения.
4.3.3 Профили расслоения и связности
4.4 Основные выводы
5 Комбинаторные оценки полного скользящего контроля
5.1 Функционал полного скользящего контроля.
5.2 Априорные ограничения компактности
5.2.1 Профиль компактности выборки
5.2.2 Точная оценка полного скользящего контроля.
5.2.3 Задача отбора эталонных объектов.
5.3 Априорные ограничения монотонности
5.3.1 Профиль монотонности выборки
5.3.2 Верхняя оценка полного скользящего контроля
5.3.3 Монотонные композиции алгоритмов классификации.
5.4 Основные выводы.
Заключение
Список основных обозначений
Предметный указатель
Список иллюстраций
Список таблиц
Список литературы


Задано, эмпирического предсказания является одной из центральных в теории вероятностей и математической статистике. Она часто возникает в приложениях, связанных с прогнозированием и принятием решений. Неформально задача состоит в том, чтобы, получив выборку данных, предсказать определённые свойства аналогичных данных, пока ещё неизвестных, и заранее оценить точность предсказания. X и X. Из аксиомы 1. Рассмотрим эксперимент, в котором реализуется одно из СІ равновероятных разбиений генеральной выборки X = X и X. После реализации разбиения наблюдателю сообщается подвыборка X. Не зная скрытой подаыборки X, требуется предсказать значение I — Т(Х, X) заданной функции Т, существенно зависящее от X. Требуется также оценить надёжность предсказания, то есть вероятность того, что предсказанное значение І = Т(Х) будет не сильно отличаться от истинного значения ? Рассмотрим два варианта формальной постановки задачи. Задача 1. Х)9т(Х,х)) > е] ^ гУ(? I: ЯхН —> К —заданная функция, характеризующая величину отклонения (1(І, і) предсказанного значения і от неизвестного истинного значения і. Обозначим эту задачу через (Я,(1,Т Т). Параметр є называется точностью, а величина (1 — г/(е)) — надёжностью предсказания. Если в (1. Обычно предполагается, что ? Если (1. Т(Х, X) имеет место концентрация вероятности [5|. Для упрощения обозначений условимся далее опускать второй аргумент X функции Т(Х,Х). Как станет видно далее, по многих задачах в качестве предсказывающей функции Т(Х) выбирается Т(Х). Тем не менсс, роль функций Т и Т принципиально различна. Функция Т задаётся в самой постановке задачи, тогда как предсказывающую функцию Т наблюдатель имеет право выбирать по собственному усмотрению. Задача допускает следующее естественное обобщение. Определение 1. Семейство подмножеств РС(Х) С Я с параметром е называется семейством (расширяющихся) вложенных подмножеств, если для любого X € X* и любых допустимых значений параметра е,е‘ из е ^ е' следует Ре(Х) С Р1С>{Х). Задача 1. Р[Т(^,Х)^П,(Х)]<Ч(е). Обозначим эту задачу через Пс). Задача является частным случаем задачи ^2, если в качестве семейства вложенных подмножеств взять ПДХ) = {< € Я | д(Т(Х)^. Примеры задач эмпирического предсказания. Выбирая множество Я, функцию Т и семейство Р. Т и (I вместо Пг), можно получить многие классические задачи теории вероятностей, математической статистики, статистического обучения. Приведём основные постановки, рассматриваемые в данной работе. Задача 1. Пусть 5 С X —некоторое множество объектов; будем называть его «событием». Р[И*) - и(Х) > е] < ч(е); (1. Очевидно, данная задача есть 0*1 (Н, |? X); н(Х)). Р [! Очевидно, данная задача есть (/. I), *'(А); и(Х)). Задача 1. Она возникает и в практических приложениях, таких, как выборочный контроль качества (7|. В 1. Задача 1. Задача 1. Задаче 1. Х) = ? Задача 1. Пусть задана функция ? X —> X. Очсвидно. Х = 1. В 1. Задача 1. Определим для произвольной функции -» К и произвольной конечной выборки (/ С X эмпирическую функцию распределения : К —* [0,1] как долю объектов х выборки Ц, для которых значение ? Р[ИХ)-и(Х)>е] $т? Р[и(Х)-и{Х) >е] «ч(? Данная задача является частным случаем 8А, если в качестве Я. Я = {Г: К —> [0,1]}, ввести на II равномерную (чебышевскую) метрику (1(1,1) — тах|? Т(Х)(г) = Р<(г, X), Т(Х)(г) = ^(г, X), где г <Е Е. Данная задача тесно связана с оцениванием скорости сходимости эмпирических распределений. На оценке (1. Смирнова проверки гипотезы однородности (одинаковой распределённости) двух выборок [, 8]. В 1. Задача 1. Задано множество А, элементы которого называются алгоритмами. Существует бинарная функция /: А х X -> {0,1}, называемая индикатором ошибки. Если 1(а,х) = 1, то говорят, что алгоритм а допускает ошибку на объекте х. ТГ7т? Методом обучения называется отображение // : 2х —> А, которое произвольной обучающей выборке X с X ставит в соответствие некоторый алгоритм а = рХ из А. Х,Х) ^ е при некотором достаточно малом с € (0,1), то говорят, что метод р переобучен относительно X, X. Р[<*ДХ,Х) ^ е] = Р[и(рХ,Х) - и(рХ,Х) |? Очевидно, данная задача есть ^{Е, (Ь — ? Х, X); о(рХ, X)).