Неравенства концентрации вероятностной меры в трансдуктивном обучении и РАС-Байесовском анализе

• Автор: Толстихин, Илья Олегович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 201 с. : ил.

Содержание
Введение

1 Неравенства концентрации для независимых случайных величин

1.1 Суммы независимых случайных величин

1.1.1 Неравенства Маркова. Чернова и метод Чернова

1.1.2 Неравенство Хефдинга

1.1.3 Неравенства Беннета и Бернштейна

1.2 Неравенства Азумы-Хефдинга и МакДиармида

1.3 Энтропийный метод Леду

1.3.1 Эмпирическое неравенство Бернштейна

1.3.2 Неравенство Буске для эмпирических процессов
2 Неравенства концентрации для выборок без возвращения
2.1 Суммы случайных величин
2.1.1 Метод Хефдинга
2.1.2 Неравенство Серфлинга
2.2 Функции, определенные на разбиениях
2.2.1 Неравенство МакДиармида для выборок без возвращения
2.2.2 Неравенство Бобкова
2.3 Супремумы эмпирических процессов для выборок без возвращения
3 Теория статистического обучения
3.1 Определения и постановки задач
3.2 Обзор известных результатов
3.2.1 Оценки, существенно опирающиеся на неравенство Буля
3.2.2 Оценки, основанные на Радемахеровскои сложности
3.2.3 Оценки, основанные на локальных мерах сложности, и быстрые скорости сходимости

Г-ГГ-!

4 Трансдуктивное обучение
4.1 Постановка задачи и обзор известных результатов
4.2 Трансдуктивные оценки избыточного риска и локальные меры сложности
4.3 Доказательства результатов Раздела 4.
5 Комбинаторная теория переобучения
5.1 Обозначения и постановка задачи
5.2 Теоретико-групповой подход
5.2.1 Обзор известных результатов
5.2.2 Новые результаты теоретико-группового подхода
5.2.3 Свойства сходства и расслоения множества векторов ошибок
5.2.4 Три подмножества шара в Булевом кубе
6 РАС-Байесовский анализ
6.1 Определения и постановка задачи
6.2 Обзор известных результатов
6.2.1 РАС-Байесовская лемма
6.2.2 Основные РАС-Байесовские неравенства
6.2.3 Сравнение РАС-Байесовских неравенств
6.2.4 Применение РАС-Байесовских неравенств в теории обучения
6.3 РАС-Байесовское эмпирическое неравенство Бернштейна
6.3.1 РАС-Байесовское неравенство для дисперсии
6.3.2 РАС-Байесовское эмпирическое неравенство Бернштейна
6.3.3 Эксперименты
6.3.4 Вспомогательные результаты
Заключение
Список рисунков
Список таблиц
Литература
Обозначения и символы

Введение
Диссертационная работа посвящена теории статистического обучения, изучающей свойства процедур обучения в рамках строгого математического формализма.
Актуальность темы. Задачи поиска закономерностей или восстановления функциональных зависимостей в наблюдаемых данных сегодня играют ключевую роль во многих прикладных областях. Методы машинного обучения, позволяющие во многих случаях эффективно решать задачи распознавания образов, классификации, восстановления регрессии, оценивания неизвестной плотности и другие задачи предсказания, стали неотъемлемой частью различных аспектов современной жизни. С теоретической точки зрения, важным вопросом является выявление факторов, влияющих на качество работы найденных на основе обучающей выборки закономерностей на новых данных, что позволило бы разрабатывать новые и более качественные алгоритмы обучения.
Теория статистического обучения (или УС-т.еория), предложенная в работах В. Н. Вапника и А. Я. Червоненкиса в конце 1960-х годов и позже получившая мировую известность, впервые позволила строго описать соотношение между необходимым для успешного обучения числом наблюдаемых данных и сложностью используемого класса отображений. Подобные результаты формулируются обычно в виде верхних границ (или оценок) на вероятность того, что найденное на основе обучающей выборки отображение даст ошибочный ответ на новых данных. Проблемой первых оценок была их сильная завышенность, обусловленная попыткой получения результатов, справедливых в чересчур общих постановках. Дальнейшее развитие УС-теорип было связано с попытками улучшения точности оценок на основе учета различных свойств рассматриваемых задач [18]. Среди предложенных за последние 45 лет подходов УС-теории можно выделить результаты, основанные на покрытиях класса отображений [8,45], на учете отступов объектов [49,84], на понятии стабильности процедуры обучения [22], на глобальной Радемахеровской сложности класса |Т, 52], на локальных мерах сложности класса [5,47,52,66] и на изучении рандомизированных отображений [57,73,85,90].
2 Неравенства концентрации для выборок без возвращения
В прошлом разделе мы подробно рассмотрели неравенства концентрации, справедливые для выборок независимых случайных величин. Однако, часто предположение о независимости может оказаться необоснованным. В таких случаях рассматривают более общие модели случайных последовательностей: мартингалы |7G], последовательности с перемешиванием [112] и другие. В данном разделе мы рассмотрим конкретную модель зависимых случайных величин, которая, тем не менее, окажется чрезвычайно полезной в дальнейших главах. Мы рассмотрим неравенства концентрации, контролирующие отклонение значений функций /(т/i,..., ?/„) от математических ожиданий E[/(?/i,..., т/п)], где случайные величины т/i,... ,rjn выбраны без возвращения из конечного множества мощностью N > п.
Примером задач, в которых естественным образом возникают выборки без возвращения, является получение оценок надёжности восстановления зависимостей по конечным выборкам данных. Первые оценки равномерного уклонения частот ошибок в двух подвыборках были получены в [100,113]. Позже эти идеи получили развитие в трансдуктивном подходе теории статистического обучения [23,101] и в комбинаторной теории переобучения [109-111,110]. Еще одним интересным примером можно считать теоретический анализ процедуры кроссвалидации.
Данный раздел состоит из трех частей. В Разделе 2.1 будут рассмотрены известные результаты для сумм случайных величин, выбранных без возвращения. На этом примере будет наглядно продемонстрировано, что выборки без возвращения ведут к более сильной концентрации по сравнению с выборками независимых случайных величин. В Разделе 2.2 будет приведено два результата, справедливых для более широкого класса функций, определенных на случайных разбиениях конечного множества действительных чисел. Первый, полученный Р. Эль-Янивом, Д. Печиопп и другими в [25,34], является аналогом неравенства МакДиармида и усиливает его при росте размера выборки п к размеру генеральной совокупности N. Второй получен С. Г. Бобковым в [17] и устанавливает субгауссовское поведение