Введение
1 Неравенства концентрации для независимых случайных величин13
1.1 Суммы независимых случайных величин 14
1.1.1 Неравенства Маркова, Чернова и метод Чернова 15
1.1.2 Неравенство Хефдинга 17
1.1.3 Неравенства Беннета и Бернштейна 20
1.2 Неравенства Азумы-Хефдинга и МакДиармида23
1.3 Энтропийный метод Леду 26
1.3.1 Эмпирическое неравенство Бернштейна 28
1.3.2 Неравенство Буске для эмпирических процессов 32
2 Неравенства концентрации для выборок без возвращений36
2.1 Суммы случайных величин 37
2.1.1 Метод Хефдинга 37
2.1.2 Неравенство Серфлинга 40
2.2 Функции, определенные на разбиениях 40
2.2.1 Неравенство МакДиармида для выборок без возвращений41
2.2.2 Неравенство Бобкова 43
2.3 Супремумы эмпирических процессов для выборок без возвращений 46
3 Теория статистического обучения57
3.1 Определения и постановки задач 58
3.2 Обзор известных результатов 66
3.2.1 Оценки, существенно опирающиеся на неравенство Буля 69
3.2.2 Оценки, основанные на Радемахеровской сложности 78
3.2.3 Оценки, основанные на локальных мерах сложности, и быстрые скорости сходимости 82
4 Трансдуктивное обучение 101
4.1 Постановка задачи и обзор известных результатов 102
4.2 Трансдуктивные оценки избыточного риска и локальные меры сложности105
4.3 Доказательства результатов Раздела 4.2 112
5 Комбинаторная теория переобучения 120
5.1 Обозначения и постановка задачи 122
5.2 Теоретико-групповой подход 125
5.2.1 Обзор известных результатов 126
5.2.2 Новые результаты теоретико-группового подхода 128
5.2.3 Свойства сходства и расслоения множества векторов ошибок131
5.2.4 Три подмножества шара в Булевом кубе 133
6 PAC-Байесовский анализ 152
6.1 Определения и постановка задачи 153
6.2 Обзор известных результатов 155
6.2.1 PAC-Байесовская лемма 155
6.2.2 Основные PAC-Байесовские неравенства 157
6.2.3 Сравнение PAC-Байесовских неравенств 164
6.2.4 Применение PAC-Байесовских неравенств в теории обучения 165
6.3 PAC-Байесовское эмпирическое неравенство Бернштейна 168
6.3.1 PAC-Байесовское неравенство для дисперсии 169
6.3.2 PAC-Байесовское эмпирическое неравенство Бернштейна 173
6.3.3 Эксперименты 174
6.3.4 Вспомогательные результаты 178
Заключение 186
Список рисунков 189
Список таблиц 190
Литература 191
Обозначения и символы 201
