автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Неравенства концентрации вероятностной меры в трансдуктивном обучении и РАС-Байесовском анализе

На правах рукописи

Толстихин Илья Олегович

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

Специальность 05.13.17 — «Теоретические основы информатики»

Автореферат

Диссертация на соискание учёной степени кандидата физико-математических наук

Москва — 2014

1 8 СЕН 2014

005552656

Работа выполнена в отделе Интеллектуальных систем Федерального государственного бюджетного учреждения науки Вычислительный центр имени А. А. Дородницына Российской академии наук.

Научный руководитель: доктор физико-математических наук,

Воронцов Константин Вячеславович.

Официальные оппоненты: доктор физико-математических наук,

зав. отделом математического программирования Федерального государственного бюджетного учреждения науки Института математики и механики им. Н. Н. Красовского Уральского отделения Российской академии наук, Хачай Михаил Юрьевич;

доктор физико-математических наук, главный научный сотрудник лаборатории №3 Федерального государственного бюджетного учреждения науки Института проблем передачи информации им. А. А.Харкевича Российской академии наук, Голубев Георгий Ксенофонтович.

Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В. А. Трапезникова Российской академии наук.

Защита состоится «16» октября 2014 г. в 15:00 на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки Вычислительный центр имени А. А. Дородницына Российской академии наук, расположенном по адресу: 119333, г.Москва, ул.Вавилова, д.40, конференц-зал.

С диссертацией и авторефератом можно ознакомиться в библиотеке и на официальном сайте (http: //www. ccas. ru/) ВЦ РАН. Автореферат разослан « » СёКи?J/js< 2014 г.

Ученый секретарь диссертационного совета

д. ф.-м. н., профессор Рязанов В. В.

Общая характеристика работы

Диссертационная работа посвящена теории статистического обучения, изучающей свойства процедур обучения в рамках строгого математического формализма.

Актуальность темы. Задачи поиска закономерностей или восстановления функциональных зависимостей в наблюдаемых данных сегодня играют ключевую роль во многих прикладных областях. Методы машинного обучения, позволяющие во многих случаях эффективно решать задачи распознавания образов, классификации, восстановления регрессии, оценивания неизвестной плотности и другие задачи предсказания, стали неотъемлемой частью различных аспектов современной жизни. С теоретической точки зрения, важным вопросом является выявление факторов, влияющих на качество работы найденных на основе обучающей выборки закономерностей на новых данных, что позволило бы разрабатывать новые и более качественные алгоритмы обучения.

Теория статистического обучения (или VC-теория), предложенная в работах В.Н.Вапника и А. Я. Червоненкиса в конце 1960-х годов и позже получившая мировую известность, впервые позволила строго описать соотношение между необходимым для успешного обучения числом наблюдаемых данных и сложностью используемого класса отображений. Подобные результаты формулируются обычно в виде верхних границ (или оценок) на вероятность того, что найденное на основе обучающей выборки отображение даст ошибочный ответ на новых данных. Проблемой первых оценок была их сильная завышенность, обусловленная попыткой получения результатов, справедливых в чересчур общих постановках. Дальнейшее развитие VC-теории было связано с попытками улучшения точности оценок на основе учета различных свойств рассматриваемых задач (Boucheron S., Lugosi G., Bousquet О, 2005). Среди предложенных за последние 45 лет подходов VC-теории можно выделить результаты, основанные на покрытиях класса отображений (Keains M. J., Schapire R. E., 1990; Bartlett P. L., Long P. M., Williamson R. C., 1996), на учете отступов объектов (Schapire R., Freund Y., Bartlett P., W. L., 1998; Koltchinskii V., Panchenko D., 2002), на понятии стабильности процедуры обучения (Bousquet О., ElisseefF А., 2002), на глобальной Радемахеровской сложности класса (Koltchinskii V., Panchenko D., 1999; Bartiett P. L., Mendelson S., 2001), на локальных мерах сложности класса (Koltchinskii V., Panchenko D., 1999; Massait P., 2000; Bartlett P., Bousquet O., Mendelson S., 2005; Koltchinskii V., 2006) и на изучении рандомизированных отображений (Shawe-Taylor J., Williamson R. С., 1997; McAllester D., 1998; Langford J., Shawe-Taylor J., 2002; Seeger M., 2002).

Несмотря на многочисленные попытки улучшения точности оценок, которые продолжаются до настоящего времени (Mendelson S., 2014), она остается по-прежнему не достаточной для применения оценок на практике. Поэтому актуальной проблемой является получение более точных оценок, с одной стороны достаточно общих, но с другой стороны учитывающих специфику решаемой прикладной задачи.

Цель диссертационной работы. Улучшение точности существующих оценок в теории статистического обучения на основе современных результатов теории неравенств концентрации вероятностной меры. Получение новых неравенств концентрации для выборок случайных величин без возвращения, учитывающих их дисперсии.

Методы исследования. В первой части настоящей работы используется энтропийный подход в теории неравенств концентрации вероятностной меры (Boucheron S., Lugosi G., Massart P., 2013), предложенный М.Леду и развитый П. Массаром, С. Бушроном, Г. Лугоши и О. Буске в работах (Ledoux M., 1996; Massart P., 2000; Boucheron S., Lugosi G., Massart P., 2013). Данный подход позволяет получать неравенства концентрации, сравнимые по точности с более сильными результатами индуктивного подхода (Talagrand M., 1995) M. Талаграна, избегая при этом чересчур громоздких доказательств. В частности, ключевую роль будут играть субгауссовское неравенство концентрации для функций, определенных на срезах Булева куба, полученное С. Г. Бобковым в работе (Bobkov S., 2004), и неравенство Талаграна для супремумов эмпирических процессов (Talagrand M., 1996), позже усиленное О. Буске (Bousquet О., 2002) на основе энтропийного подхода.

Вторая часть работы будет использовать подход в теории статистического обучения (Vapnik V. N., 1998; Boucheron S., Lugosi G., Bousquet O., 2005), существенно основанный на результатах теории неравенств концентрации вероятностной меры и теории эмпирических процессов (van der Vaart A. W., Wellner J., 2000; van de Geer S., 2000). Предложенный впервые в конце 60-х годов в работах В.Н.Вапника и А. Я. Червоненкиса (Vapnik V. N., Chervonenkis A. Y., 1968; Vapnik V. N., Chervonenkis A. Y., 1971), данный подход продолжает активно развиваться и на сегодняшний день. В частности, ряд важных результатов настоящей работы будет основан на так называемом локальном подходе, развитом в начале 2000-х годов В. Колчинским, Д. Панченко, П. Массаром, П. Баршетом, О. Буске, Ш. Мендельсоном, Г. Лугоши и рядом других авторов в серии работ (Koltchinskii V., Panchenko D., 1999; Massait P., 2000; Bartlett P., Bousquet О., Mendelson S., 2005; Koltchinskii V., 2006). В отличие от большинства других подходов теории Вапника-Червоненкиса, локальный подход позволяет эффективно

учитывать свойства конкретной решаемой задачи при оценке качества процедуры обучепия, что часто ведет к существенно более точным результатам.

Третья часть работы основана на комбинаторной теории переобучения, предложенной К.В.Воронцовым (Воронцов К. В., 2011; Vorontsov К. V., 2010; Vorontsov К. V., Ivahnenko. А. А., 2011; Vorontsov К. V., Frey A. I., Sokolov Е. А., 2013). В частности, мы будем использовать теоретико-групповой подход, развитый в работах (Фрей А. И., 2009; Фрей А. И., 2010).

Наконец, четвертая часть работы использует РАС-Байесовский анализ — относительно повый подход в теории статистического обучения, предложенный Д. МакАллистером и Дж. Шоу-Тейлором в работах (Shawe-Taylor J., Williamson R. С., 1997; McAllester D., 1998) и далее развитый Дж. Лэнгфордом, М. Зигером (Langford J., Shawe-Taylor J., 2002; Seeger M., 2002) и рядом других авторов. Известно, что оценки РАС-Байесовского анализа в ряде прикладных задач ведут к наиболее точным на сегодняшний день результатам.

Основные положения, выносимые па защитузащиту:

1. Получено два новых неравенства концентрации типа Талаграна для супремумов эмпирических процессов и выборок без возвращения, которые учитывают дисперсии случайных величин.

2. Получена новая оценка избыточного риска в транедуктивной постановке теории статистического обучепия, основанная на локальных мерах сложности рассматриваемого класса отображений и впервые в трапедуктив-ном подходе ведущая к быстрой скорости сходимости в общих предположениях.

3. В рамках теоретико-группового подхода комбинатонной теории переобучения предложено учитывать орбиты множества выборок при вычислении точного значения вероятности переобучения. На основе этого подхода получены новые точные (не завышенные) оценки вероятности переобучения для трех модельных семейств отображений, бинарные векторы ошибок которых являются различными подмножествами шара в Булевом кубе.

4. В рамках РАС-Байесовского анализа теории статистического обучения получено новое РАС-Байесовское эмпирическое неравенство Бершптей-на, полностью вычислимое на основе обучающей выборки и во многих случаях ведущее к существенно более точным оценкам по сравнению с известными рапее результатами.

Научная новизна. В диссертационной работе впервые показано, что в транедуктивной постановке теории статистического обучения быстрая скорость сходимости может достигаться в достаточно общих предположениях. В частности, продемонстрировано, что избыточный риск при использовании ме-

тода минимизации эмпирического риска определяется величиной неподвижной точки модуля непрерывности эмпирического процесса в окрестностях оптимального на генеральной выборке отображения. Подобные результаты до этого были известны в задачах М-оценивания в теории эмпирических процессов и позже в индуктивной постановке теории статистического обучения. Однако, все они были основаны на неравенстве Талаграна для эмпирических процессов, которое, в свою очередь, существенно опирается на предположении о независимости случайных величин и, следовательно, не может быть использовано в трансдук-тивной постановке теории статистического обучения.

Для преодоления этой трудности в диссертационной работе были впервые получены аналоги неравенства Талаграна, которые справедливы для случайных величин, выбранных равномерно без возвращения из произвольного конечного множества. До этого в литературе были известны лишь неравенства типа Мак-Диармида для супремумов эмпирических процессов и выборок без возвращения, не учитывающие дисперсии случайных величин.

Результаты, полученные в рамках теоретико-группового подхода в комбинаторной теории переобуения, основаны на новой идее учета при вычислении вероятности переобучения орбит разбиений генеральной выборки.

Новое РАС-Байесовское эмпирическое неравенство Бернштейна является первым примером РАС-Байесовских неравенств, одновременно учитывающих дисперсии потерь и вычислимых на основе обучающей выборки.

Теоретическая значимость. Полученные в диссертационной работе неравенства концентрации типа Талаграна являются достаточно общими и могут быть использованы в теоретическом анализе большого числа современных прикладных задач (в том числе выходящих за рамки теории обучения), где важную роль играют выборки без возвращения. Одним из примеров таких задач является неасимптотический анализ свойств процедуры скользящего контроля, широко применяемой па практике.

Новые оценки избыточного риска и обобщающей способности, полученные в диссертационной работе, улучшают точность известных ранее в теории статистического обучения результатов, давая более глубокое понимание процесса обучения на основе эмпирических данных в транедукгавной постановке. В частности, новые оценки позволяют заключить, что сложность задач транедукгивно-го обучения, по крайней мере, не превосходит сложность задач индуктивного обучения. Более того, они показывают, что свойства задач транедуктивного обучения в ряде случаев могут выгодно отличаться от свойств задач индуктивного обучения.

Новые результаты комбинаторного подхода, полученные в диссертационной работе, расширяют класс задач и семейств отображений, для которых возмож-

но эффективное (полиномиальное по длине выборки) вычисление вероятности переобучения.

Практическая значимость. PAC-Байесовского эмпирическое неравенство Бернштейна, полученное в настоящей работе, во многих случаях ведет к существенно более точным оценкам обобщающей способности по сравнению с известными ранее результатами PAC-Байесовского анализа. Кроме того, новая оценка полностью вычислима на основе наблюдаемых данных. Это дает возможность эффективно применять ее на практике при решении задач обучения по прецедентам для оценивания качества получаемых решений или настройки гиперпараметров, избегая при этом больших вычислительных затрат процедуры скользящего контроля. Наконец, минимизация полученной оценю! может вести к новым более точным методам обучения, имеющим гарантированную обобщающую способность.

Полученные в диссертационной работе оценки избыточного риска для тран-сдуктивного обучения могут вести к применимым на практике методам выбора моделей, основанпым на использовании всех объектов генеральной совокупности. В частности, вместе со Следствием 15 (стр. 110) они могут вести к новым алгоритмам выбора ядер, поскольку собственные значения матрицы Грамма спрямляющего ядра, определяющие скорость сходимости метода минимизации эмпирического риска, в этом случае могут быть вычислены на основе наблюдаемых данных.

Степень достоверности. Достоверность результатов обеспечивается математическими доказательствами теорем и серией подробно описанных вычислительных экспериментов, результаты которых согласуются с теоретическими результатами настоящей работы.

Апробация работы. Результаты диссертационной работы неоднократно докладывались и обсуждались на следующих конференциях и научных семинарах:

1. Международная конференция «Ломоносов-2010», 2010 г. [4];

2. Международная конференция «Интеллектуализация обработки информации», 2010 г. [5];

3. Международная конференция «Интеллектуализация обработки информации», 2012 г. [б];

4. Международная конференция "Neural Information Processing Systems (NIPS)", озеро Тахо, США, Декабрь 2013 г. [1];

5. Научный семинар группы проф. F. Laviolette и M. Marchand, Лавальский Университет Квебек, Канада, Декабрь 2013 г.;

6. Три доклада на совместном НМУ-МФТИ семипаре «Стохастический анализ в задачах», Москва, Декабрь 2013 г. и Апрель 2014 г.;

7. Научный семинар группы профессора В. Schoelkopf, Max Planck Institute for Intelligent Systems, Тюбинген, Германия, Май 2014 г.;

8. Научный семинар Лаборатории 7 Института Проблем Управления РАН, Москва, Июнь 2014 г.;

9. Международная конференция "Conference on Learning Theory (COLT)", Барселона, Испания, Июнь 2014 г. [3];

10. Научные семинары отдела Интеллектуальных систем Вычислительного Центра им. А. А. Дородницына РАН.

Публикации. Основные результаты настоящей диссертационной работы опубликованы в 7 работых [1-7], 3 из которых входят в список изданий, рекомендованных ВАК [1-3].

Личный вклад диссертанта заключается в выполнении основного объёма теоретических и экспериментальных исследований, изложенных в диссертационной работе. Все результаты, приведенные в настоящей работе, относятся к личному вкладу диссертанта, за исключением отдельно оговоренных случаев.

Подготовка к публикации полученных в работах [1-3,7] результатов проводилась совместно с соавторами. Все экспериментальные и основная часть теоретических результатов работы [1] получены лично автором. В работах [2,7] к личному вкладу автора относится разработка техники учета орбит разбиений при вычислении вероятности переобучения, использовавшаяся в доказательстве всех основных результатов данных работ, а также теоремы о вероятности переобучения центрального слоя Хэммингова шара и монотонного роста вероятности переобучения множеств бинарных векторов ошибок, лежащих в одном слое Булева куба.

Объем и структура работы Диссертация состоит из оплавления, введения, шести глав, заключения, списка иллюстраций (13 п.), списка таблиц (1 п.), списка литературы (124 п.) и списка обозначений. Общий объём работы составляет 201 страницу.

Краткое содержание работы

Во введении обосновывается актуальность исследований, проводимых в рамках данной диссертационной работы, формулируется цель работы, приводится список положений, выносимых на защиту, а также формулируется теоретическая и практическая значимость работы.

Первая часть диссертационной работы (первая и вторая главы) посвящена теории неравенств концентрации вероятностной меры1. Пусть дана функция

'Boucheron S., LugosiG., Massart P. Concentration Inequalities: A Nonasymptotic Theory cf Independence, Oxford University Press, 2013.

д: X" —> Е, зависящая от большого числа аргументов, принимающих значения в некотором множестве X. Пусть также дано большое число случайных величин Xi,...,Xn, принимающих значения в X. Неравенства концентрации вероятностной меры позволяют ограничивать сверху вероятности отклонений Р{<2 - E[Q] ^ i} и P{E[Q] - Q > t} для t > 0, где Q = д{Хи..., Хп).

В первой главе приводится подробный обзор классических и современных результатов теории неравенств концентрации вероятностной меры для независимых случайных величин Х\,..., Хп. В разделе 1.1 рассматриваются суммы независимых и ограниченных случайных величин, и для них приводятся неравенства Хефдинга, Бернштейна и Беннетта. В разделе 1.2 рассматриваются функции с ограниченными разностями, и для них приводятся неравенства Азумы-Хефдинга и МакДиармида. В разделе 1.3 формулируются основные результаты энтропийного метода2 в теории неравенств концентрации, включая неравенства для самоограничивающих функций, а также приводятся эмпирическое неравенство Бернштейна3 и неравенство Талаграна для супремумов эмпирических процессов4.

Вторая глава посвящена результатам теории неравенств концентрации вероятностной меры для случайных величин Х\,..., Хп, выбранных без возвращения из некоторого конечного множества С — {ci,..., Первая часть главы содержит подробный обзор известных результатов: в разделе 2.1 рассмотрива-ются суммы ограниченных случайных величин, и для них приводятся неравенство Стерлинга и метод редукции Хефдинга; в разделе 2.2 рассматриваются функции, определенные на множестве разбиений генеральной выборки С, и для них приводятся неравенство Эль-Янива-Печиоии5, которое является аналогом неравенства МакДиармида, и субгауссовское неравенство С. Г. Бобкова6.

Неравенство Талаграна для супремумов эмпирических процессов, рассмотренное в разделе 1.3, играет важную роль во многих современных прикладных задачах. К сожалению, до сих пор в литературе не было известно его аналога для выборок без возвращения. В разделе 2.3 приводятся основные результаты второй главы: два новых неравенства концентрации типа Талаграна для супремумов эмпирических процессов и выборок без возвращения, учитывающие дисперсии случайных величин (Теоремы 20 и 22).

2Ledoux М. On Talagrand's Deviation Inequalities for Product Measures, ESAIM: Probability and Statistics, 1996.

3Maurer A., Pontil M. Empirical Bernstein Bounds and Sample Variance Penalization, Proceedings of the International Conference on Computational Learning Theory (COLT), 2009.

4Talagrand M. New concentration inequalities in product spaces, Inventiones Mathematicae, 1996, Vol. 126.

5E1-Yaniv R., Pechyony D. Transductive Rademacher Complexity and its Applications, Journal of Artificial Intelligence Research, 2009.

'Bobkov S. Concentration of normalized sums and a central limit theorem for noncoirelated random variables. Annals of Probability, 2004, Vol. 32.

Пусть С = (cj,...,сдг} — некоторое конечное множество. Для п ^ N рассмотрим последовательности случайных величии 771,..., т]п и ..., выбранные равномерно из С без возвращения и с возвращением соответственно. Пусть J- — некоторое счетное7 множество отображений /: С —» ffi, таких что E[/(Çi)] = 0 и f(x) € [—1,1] для всех / £ 7" и ж G С. Супремумами эмпирических процессов для выборок без возвращения и с возвращением соответственно называются следующие случайные величины:

п п

Q'n = sup Y\ fivi), Qn = sup J2 /(&) ■

Теорема 20. Введем обозначение а2Т = supyejrD[/(£i)j. Тогда для любого е ^ О справедливо:

Р M - 4Qn\ > < exp -

Аналогичное неравенство справедливо и для Р {E[QJJ — Q'n > е}. Кроме того, для любого S 6 (0,1] с вероятностью не меньше 1 — 5 справедливо:

Теорема 22. Положим ojr = sup/ejFB[/(£i)], v = naj? + 2E[Qn] и для и > -1 определим ф(и) - еи - и - 1, h{u) = (1 + и) Iog(l + «) - и. Тогда для s > 0 справедливо:

Р {Q'n - E[Qn] > е> < exp (-„ . h (£)) < exp (-^3) ■ Кроме того, для любого 5 € (0,1] с вероятностью не менее 1 — 5 справедливо:

E[Q„] + у/Ш + i log i.

о о

Подробный теоретический анализ, представленный в конце раздела 2.3, показывает, что во многих интересных случаях новые неравенства Теорем 20 и 22 существенно превосходят точность всех известных в литературе аналогов. Обратим внимание, что Теорема 22 контролирует отклонения случайной величины Q'n не от своего математического ожидания Е[Q'„], а от величины E[Q„], В разделе 2.3 показано, что этот факт в общем случае может вести к потерям точности оценок, поскольку всегда справедливо Е[<2п] — ЩЯ'„] ^ 0. Однако, при определенном соотношении размеров выборок п и N ухудшения оказываются пренебрежимо малыми, поскольку также справедливо Е[<2„] - E[Q'n] < 2n3/N.

'Все

результаты могут быть обобщены па случай несчетного множества Т в том случае, если эмпирический процесс сепарабелен, то есть множество Т содержит счетное и всюду плотное подмножество.

8

Вторая часть диссертационной работы (главы 3, 4, 5 и 6) посвящена теории статистического обучения8. В третьей главе приведен подробный обзор ряда классических и современных результатов индуктивной постановки теории статистического обучения9. Раздел 3.1 посвящен введению определений и обсуждению различных постановок задач. В разделе 3.2 приводится подробный обзор и сравнение ряда подходов к получению оценок избыточного риска и обобщающей способности. Сначала в подразделе 3.2.1 рассмотрены подходы, существенно опирающиеся на неравенство Буля, включая оценку Вапника-Червоненкиса, оценку «бритвы Оккама»10 и оценку, основанную па покрытиях множества отображений11. Затем в подразделе 3.2.2 рассматриваются оценки, основанные на глобальной Радемахеровской сложности12, а также приводятся неравенства симметризации и сжатия. Наконец, в подразделе 3.2.3 приводится обзор так называемого локального анализа13, включая обсуждение условий ограниченного шума Маммена-Цыбакова и Массара, быстрых скоростей сходимости и локальных Радемахеровских сложностей.

В четвертой главе рассматривается трансдуктивная постановка8 теории статистического обучения, и в рамках нее впервые применяется локальный анализ, описанный в третьей главе. В разделе 4.1 приводится формальная постановка задачи. Рассмотрим произвольное конечное множество Xw, содержащее N объектов из пространства объектов X. Выберем п ^ N объектов Хп С Хн равномерно без возвращения из множества Хм и получим ответы Yn для объектов Хп с помощью неслучайной целевой функции14 ур: X —> У, где У — пространство ответов. Обозначим обучакпцую выборку (Xn,Y„) с помощью Sn. Оставшиеся объекты без ответов на них Хи - Хдг \ Хп, где и — N — п, формируют контрольную выборку. Рассмотрим произвольную ограниченную и неотрицательную функцию потерь £: У х У —> [0,1] и обозначим величину потерь при использовании отображения h: X У для предсказания ответа на объекте X с помощью h{X) = £(к(Х),ф(Х)). Определим соответственно эмпирический риск, потери на контрольной выборке и потери на генеральном

gVapnik V. N. Statistical Learning Theory, John Wiley & Sons, 1998.

'Boucheron S., Lugosi G., Bousquct O. Theory of Classification: a Survey of Recent Advances, ESAM: Probability and Statistics, 2005.

10Blumer A., Ehrenfueucht A., Haussler D., Warmuth M. Occam's razor, Information Processing Letters, 1987, Vol. 24, P. 377-380.

"Mendelson S. A Few Notes on Statistical Learning Theory, Lecture Notes in Computer Science, 2003.

l2Bartlett P. L., Mendelson S. Rademacher and Gaussian complexities: Risk bounds and structural results, Proceedings of the International Conference on Computational Learning Theory (COLT), 2001.

"Koltchinskii V. Local Rademacher Complexities and Oracle Inequalities in Risk Minimization, The Annals of Statistics, 2006, Vol. 34, no. 6, p. 2593-2656.

"Такая постановка задачи известна как «задача без шума». Результаты четвертой главы могут быть обобщены иа случай с шумом, когда ответ Y для объекта х 6 X выбирается из неизвестного условного распределения P(Y\X ' х) на множестве 3

множестве произвольного отображения h: X —» У следующим образом:

Uh) = - Е ¿«со = - £ м/о

П ХеХ„ U ХеХ„ ХеХы

Цель процедуры обучения заключается в поиске на основе обучающей выборки Sn и объектов контрольной выборки Хи отображения Л* в заранее выбранном классе отображений % = {h: X —¥ У} (не обязательно содержащем целевую функцию ip), имеющего минимальные потери на контрольной выборке:

Л* £ Arg minLu(h). и heu

Поскольку ошибка на контроле Lu(h) нам неизвестна, мы воспользуемся методом минимизации эмпирического риска (МЭР) и будем приближать оптимальное отображение Л* отображением hn € И, имеющим наименьший в заданном классе И эмпирический риск:

hn S Arg min Ln(h). heu

Найдя такое отображение hn, мы хотели бы оценить потери на контроле найденного отображения Ln(hn) и понять, насколько эта величина превосходит оптимальное значение Lu(/i*). В частности, нас будут интересовать обобщающая способность Lu{hn) — Ln(hn) метода МЭР и избыточный риск Lu{hn) — Lu{h"u) отображения hn. Поскольку эти величины являются случайными (так как отображения h*u и hn зависят от обучающей выборки), нашей главной задачей15 является получение верхних оценок на вероятности отклонений P{Lu(hn) - Ln(hn) > t} и P{Lu(hn) - Lu(h*u) ^ i} для i > 0, убывающих с ростом размера обучающей выборки п и учитывающих свойства семейства 71. В разделе 4.1 приводится обзор известных результатов.

В разделе 4.2 приводятся основные результаты четвертой главы: новые оценки избыточного риска (Теоремы 41 и 42, Следствия 13 и 14), основанные на локальных мерах сложности семейства отображений Н. Результаты приводятся в двух вариантах в зависимости от того, какая из Теорем 20 и 22 использовалась в их доказательстве.

Обозначим с помощью h*N отображение из И с наименьшим значением Lx(h) и для г > 0 рассмотрим отображения h £ И с малыми дисперсиями

15Отметим, что индуктивная постановка отличается от трансдуктивной главным образом способом получения обучающей выборки. В индуктивной постановке объекты обучающей выборки {(Х*, fri)}^ выбираются независимо из неизвестного распределения Р на декартовом произведении X У. У. Задача заключается в поиске отображения h в И с наименьшим значением среднего риска Е(хгу)~р [^(М^)) ■ Кроме того, процедура обучения индуктивной постановки не получает доступа к объектам! не содержащимся в обучающей выборке.

избыточных потерь:

ад = (л € Н: ± £ №) -ЧРО)2 < 4 •

I хехы )

Субкоренной мы будем называть неубывающую и неотрицательную функцию ф: [0, оо) —¥ [0, оо), такую что отображение г —> ф(г)/л/г является невозраста-ющим для г > 0. Можно показать, что у любой субкоренной функции существует единственная положительная неподвижная точка.

Следующие результаты оценивают сверху величину в тер-

минах локальной меры сложности класса ~Н:

Теорема 41. Пусть существует константа В > 0, такая что для всех к € 11: 1 £

ХеХн

Кроме того, пусть существует субкоренная функция ф„{г), такая что

В • Е

вир - Ьп(К) - (Ьц{Ь,у) -

лен(г)

^ Фп{г).

Обозначим с помощью г* неподвижную точку функции фп(г). Тогда для любого 6 € (0,1] с вероятностью не меньше 1 — 5 справедливо:

МЛ») - < 51-| + 17В

Теорема 42. Пусть существует константа В > 0, такая что для всех к € И;

1 £ (МХ) - ен.у(Х))2 < В ■ (Ь„(к) - Ь„(1г')). хехК

Кроме того, пусть существует субкоренная функция фп(г), такая что:

В ■ Е

вир Ьк(к) - Ьп{К) - (£м(/1дг) - Ьп(Ь^)) лек(г)

< Фп{г),

где Ьп(К) = £ для случайных величин ..., выбранных равно-

мерно с возвращением из Хдг. Обозначим с помощью г* неподвижную точку функции фп(г). Тогда для любого 5 е (0,1] с вероятностью не меньше 1 — 5 справедливо:

ык) - < +(16125В) 1оЕ I-и

Теоремы 41 и 42 обобщают результаты локального анализа индуктивной постановки теории статистического обучения16 на трансдуктивную постановку и показывают, что порядок убывания L^{hn) — L^(h*N) определяется величиной неподвижной точки модуля непрерывности эмпирического процесса, посчитанного в окрестности лучшего на генеральном множестве отображения h*N. Наконец, справедливы следующие оценки избыточного риска:

Следствие 13. Пусть выполнены предположения Теоремы 41. Тогда для любого S G (0,1] с вероятностью не меньше 1 — 5 справедливо:

г ,7 ч г 51iV /г* г*Л YJBN2 /1 1\, 2

ММ - Lu{hl) - + - +-( - + - loS7-

В \и п J пи \и п) о

Следствие 14. Пусть выполнены предположения Теоремы 42. Тогда для любого 5 € (0,1] с вероятностью не меньше 1 — 5 справедливо:

LM - LM + -^- i '

Оказьшается, в ряде интересных случаев неподвижные точки г* и г* имеют порядок о(п-1/2). Примером являются задачи с бинарной функцией потерь и множеством отображений Н, имеющем конечную VC-размерность d < сю. Известно17, что в этом случае г* = В теории статистического обучения скорости сходимости оценок принято разделять на два типа: быстрые скорости порядка o(n_1/2) и медленные скорости порядка 0(п~1/'2). Новые результаты впервые позволяют получать оценки избыточного риска в трансдуктивном обучении, имеющие быстрые скорости сходимости в общих предположениях на рассматриваемый класс задач.

В разделе 4.2 также приводятся новые оценки обобщающей способности, которые, в отличие от известных в литературе аналогов, учитывают дисперсию потерь и справедливы для произвольных классов отображений и ограниченных функций потерь. Подробные доказательства результатов приводятся в разделе A3.

В пятой главе рассматривается комбинаторная теория переобучения^, тесно связанная с трансдуктивным обучением. В разделе 5.1 вводятся определения и ставится формальная постановка задачи. Несмотря на то, что постановка комбинаторной теории переобучения чрезвычайно похожа на введенную ранее постановку трансдуктивного обучения, нам будет удобно ввести ряд новых

"Bartlett P., Bousquet О., Mendclson S. Local Rademacher Complexities, The Annals of Statistics, 2005, Vol. 33, no. 4, p. 1497-1537.

17Massait P. Some applications of concentration inequalities to statistics, Ann. Fac. Sei. Toulouse Matb, 2000, Vol. 9, no. 6, P. 245-303.

18Воронцов К. В. Комбинаторная теорш переобучения: результаты, приложения и открытые проблемы, Математические методы распознавания образов: 15-ая Всеросс. конф.: Докл, 2011.

12

обозначений. Мы также продолжим пользоваться обозначениями, введенными в четвертой главе.

Рассмотрим конечную генеральную выборку упорядоченных пар «объект-ответ» Б = {(А^, У0}£х и бинарную функцию потерь. Конечное множество различных векторов ошибок отображений из И на генеральной выборке Б мы будем обозначать А:

Всюду далее мы будем отождествлять отображения Л € И с их векторами ошибок а 6 А. Индикаторам ошибки вектора а € А на паре (X, У) б 8 назовем 1а(Х, У) = где На — произвольное отображение из И, вектор оши-

бок которого равен а. Из генеральной выборки Б равномерно без возвращения выбирается п < N пар «обьект-ответ» Яп С §, которые образуют обучающую выборку, и становятся доступны алгоритму обучения. Оставшиеся и == N — п пар ,5>„ остаются неизвестными и образуют контрольную выборку. Определим среднее число ошибок вектора а € А на подвыборке 5 С

Для произвольной подвыборки S С § обозначим с помощью /1(5) множество векторов в А, имеющих минимальное число ошибок на ней:

A{S) = Arg min L(a,S).

Также обозначим с помощью [Б]" всевозможные подвыборки §, состоящие в точности из п пар «объект-ответ».

В комбинаторной теории переобучения рассматриваются различные методы обучения — отображения ц: [§]" —>• А, ставящие в соответствие обучающим выборкам векторы ошибок из А. Основная задача комбинаторной теории переобучения заключается в получении точных (не завышенных) оценок вероятности переобучения метода ц:

В диссертационной работе рассматривается рандомизированный метод минимизации эмпирического риска (РМЭР), который для заданной обучающей выборки Яп выбирает случайный вектор а равномерно из множества А (£"„). Обратим внимание, что в этом случае вектор р(Зп) в определении вероятности переобучения <Э,,,£(А) также становится случайным. В разделе 5.1 также приводится сравнение постановки кобинаторной теории переобучения с постановкой транс-дуктивного обучения.

А - {(%№)№„ • • •, ■■ h е н} С {0,1}Л'.

Q„,e(А) = Р {L(M(S„), Su) - L{fi(S„), Sn) e} .

В разделе 5.2 рассматривается теоретико-групповой подход к комбинаторной теории переобучения, и приводятся основные результаты пятой гаавы. В подразделе 5.2.1 вводятся определения и обозначения, а также приводится обзор известных результатов. Рассмотрим симметрическую группу перестановок Пдг. Элементы группы Идт очевидным образом действует на генеральной выборке, переставляя местами пронумерованные пары «объект-ответ», составляющие ее. Для пары (X, У) е 8 и 7Г 6 Пдг с помощью л(Х, У) обозначим ту пару, в которую пара (X, У) переходит под действием перестановки 7Г. На основе этого можно определить действие элементов -п 6 Плг на множестве подвыбо-рок £■ С §:

7Г(5) = {тг(Х,У): (Х,Г)6 5}, па множестве бинарных векторов ошибок а € А:

тт(а) = (1ф)(Х{, У,)))^ = (/„(тгЧХ,-, У;-)))^

и на всевозможных подмножествах А С А:

7г(А) = {к(а): а € А}.

Группой силшетрий 5д множества векторов ошибок А С {0,1}А' будем называть его стационарную подгруппу:

5а = {тг 6 П^ : тг(А) = А}.

Орбитой действия группы симметрии 5д на вектор ошибок а € А будем называть множество (тг(а) : тг € 5д}- Множество всех орбит действия группы 5д на элементы А будем обозначать Г2(А).

Теоретико-групповой подход основан на следующем наблюдении: в том случае, когда семейство векторов А обладает определенными симметриями (когда группа 5Л содержит достаточное число элементов), вычисление точного значения вероятности переобучения существенно упрощается19.

В подразделе 5.2.2 предлагается при вычислении вероятности переобучения помимо орбит векторов ошибок учитывать также орбиты выборок, и приводится новая формула вычисления точного значения вероятности переобучения. Орбитой действия группы силшетрий 5д на подвыборку Б £ [§]" мы будем называть множество {7г(5): 7Г £ /Уд}- Множество всех таких орбит мы будем обозначать П ([§]").

"фрей А. И. Точные оценки вероятности переобучения для симметричных семейств алгоритмов, Математические методы распознавания образов: 14-ая Всеросс. ишф.: Докл, 2009.

Теорема 44. При использовании РМЭР для произвольного множества попарно различных векторов ошибок A G {0, 1}jV и любых £ ^ 0 справедливо:

где аш — произвольный вектор ошибок из орбиты ui € П(А), a ST — произвольная выборка из орбиты Т € П ([§]"). Результат остается справедлив, если мы заменим множества fi (А) « fi ([S]") соответствующими множествами орбит действия произвольной подгруппы группы симметрии S&.

В подразделе 5.2.3 обсуждаются свойства сходства и расслоения семейств векторов ошибок и их влияние на вероятность переобучения20.

Число ошибок вектора о на подвыборке S G S мы будем обозначать n(a, S) = |S|-L(a, S). Рассмотрим множество бинарных векторов, допускающих ровно m ошибок на генеральной выборке: В^ = {а 6 {0,п(а, §) = m}. Введем расстояние Хэмминга между двумя векторами а', а" € А:

d(o,,a")= £ MX,Y) - Ia"{X,Y)\. (Х,У) es

На основе Теоремы 44 в подразделе 5.2.4 получены новые точные (не завышенные) оценки вероятности переобучения для следующих трех модельных семейств векторов ошибок А:

1. Шар радиуса г с центром в векторе а0 € {0,1}Л':

Вг{а0) = {а G {0,1}^: d(a,a0) ^ г}.

2. Центральный слой шара:

ВсГ{ао) = П Вг(а„),

где m = п(ао, S).

3. d нижних слоев шара:

Br(a0,d)= U (в£.пвг(а0)),

где rrij = max{n(a0, S) - г, 0} + (d - 1).

Новые оценки еще раз подтверждают хорошо известный в комбинаторной теории переобучения факт о том, что получение не сильно завышенных оценок невозможно без одновременного учета свойств сходства и расслоения множества векторов ошибок.

20Воронцов К. В. Точные оценки вероятности переобучения, Доклады РАН, 2009, Т. 429, № 1, С. 15-18.

15

Шестая глава посвящена РАС-Байссовскому анализу21, который в рамках теории статистического обучения изучает рандомизированные отображения. В разделах 6.1 и 6.2 вводятся основные определения, описывается общий подход к получению РАС-Байесовских неравенств, и приводится достаточно подробный обзор известных результатов, включая неравенство МакАллистера (также известное как РАС-Байесовское неравенство Хефдинга), РАС-Байесов-ское неравенство Бернппейна и РАС-Байесовское kl-неравенство. Также в этих разделах приводится подробное сравнение трех описанных неравенств, и обсуждаются способы их применения в индуктивном обучении, рассмотренном в третьей главе. В разделе 6.3 представлены главные результаты шеской главы (Теоремы 54 и 55, а также результаты экспериментов).

Напомним, что в рамках индуктивной постановки теории статистического обучения нам дана обучающая выборка Sn = {(X,-, которая состоит из п

пар «объект-ответ», выбранных независимо из неизвестного распределения Р на X х У. Задача процедуры обучения заключается в поиске на основе Sn отображения h € И, имеющего малый средний риск L(h) ~ У)] для неотрицательной и ограниченной функции потерь £: У х У —► [0,1]. Обозначим с помощью Ln(h) = £ ]£"=i i{h{Xi), Vi) эмпирический риск отображения

hen.

Рассмотрим произвольное вероятностное распределение р на множестве отображений Л. РАС-Байесовский анализ изучает рандомизированное отображение Gp, которое для получения ответа па повом объекте X G X выбирает случайное отображение h из распределения р (независимо от объекта X) и возвращает ответ h(X). Средний и эмпирический риск рандомизированного отображения Gp определяется следующим образом:

L{Gp) = EW[L(A)], Ln(Gp)=E^p[Ln(h)}.

Задача РАС-Байесовского обучения заключается в поиске распределения р с малым значением среднего риска L(GP). РАС-Байесовские неравенства позволяют оценивать неизвестный средний риск стохастического отображения L(GP) с помощью эмпирического риска Ln{Gp). Кроме того, в ряде случаев при определенном выборе распределения р величина L(GP) позволяет оценивать сверху средний риск L{h) обыкновенных детерминированных отображений22.

2lMcAllester D. Some PAC-Bayesian Theorems, Proceedings of the International Conference on Computational Learning Theory (COLT), 1998.

22Langford I., Shawe-Taylor J. PAC-Bayes & Margins, Advances in Neural Information Processing Systems (NIPS), 2002.

Одним из наиболее точных на сегодняшний день РАС-Байесовских неравенств является РАС-Байесовское неравенство Бернштейна23. Однако, его оценка зависит от неизвестной усредненной дисперсии потерь Е^/1[В(/г)], где

В подразделе 63.1 представлен новый результат, позволяющий оценивать неизвестную величину Е^ [В (Л)] с помощью несмещенной выборочной оценки дисперсии:

¿=1

Обозначим дивергенцию Кульбака-Лейблера для двух вероятностных распределений р и 7г на Н с помощью КХ(р, тт) = ^ой .

Теорема 54. Для любого распределения я на множестве не зависящего от обучающей выборки, для любого 5 € (0,1] и для любого с > 1 с вероятностью не меньше 1—5 (относительно случайной реализации обучающей выборки) следующее справедливо одновременно для всех распределений р на И:

Efc~P[D(A)] < cE,^p[Dn(/i)] + 2су/(E^p[D„(ft)] + Vn(p))vn(p) + 2cr)n(p), (1)

где

КЦр||тг)+1п*

■Пп(р) =

2 (п - 1) '

В подразделе 6.3.2 представлено новое РАС-Байесовское эмпирическое неравенство Бернштейна, основанное на Теореме 54 и РАС-Байесовском неравенстве Бернштейна:

Теорема 55. Для любго распределения тг на И, не зависящего от обучающей выборки, любых ¿1 6 (0,1] и ci, С2 > 1, обозначив Ю„(р) правую часть неравенства (1) (с 5 — 4jv) и положив Ön(p) = min ^Qn(p), мы получим, что с вероятностью не меньше 1 — ¿i (относительно случайной реализации обучающей выборки) следующее:

L(Gp)*kLn(Gp) + (l + Cl)\

(е - 2)Р„(р) (кЬ(Р1|7г)+1п^)

п

выполнено одновременно для всех распределений р на Л, которые удовлетворяют условию _

KL(p||;r)+ln^ (е — 2)D„(p)

< у/а,

2,ScIdin Y., Laviolette F., Cesa-Bianchi N., Shawe-Taylor J., Aucr P. PAC-Bayesian Inequalities for Martingales, IEEE Transactions on Information Theory, 2012, Vol. 58.

где 1/1 = 1п (^у)] + 1- Для вссх остальных распределений р одновременно справедливо:

Ь(СР) < Ьп(Ср) + 2- -к

Обратим внимание, что оценка последнего результата полностью вычислима на основе обучающей выборки. Кроме того, теоретический анализ показывает, что во многих случаях она существенно точнее известных в литературе аналогов. В подразделе 6.3.2 приводятся численные эксперименты с модельными выборками и реальными данными из репозитория 17С1, результаты которых согласуются с представленным теоретическим анализом.

Заключение

Основные результаты диссертационной работы заключаются в следующем:

1. Получено два новых неравенства концентрации для супремумов эмпирических процессов и выборок без возвращения. Оба неравенства учитывают дисперсию случайных величин, что отличает их от всех известных ранее аналогов. Подробный теоретический анализ показывает, что во многих интересных случаях новые неравенства существенно превосходят по точности все известные аналоги.

2. Получены новые неравенства обобщающей способности для трансдуктивного обучения, учитывающие дисперсии потерь и, в отличие от известных в литературе аналогов, справедливые для произвольных классов отображений и огрониченных функций потерь. Также получены первые оценки избыточного риска в трансдужтивном обучении, основанные на локальных мерах сложности семейств отображений и во многих интересных случаях имеющие быстрые скорости сходимости в общих предположениях о рассматриваемом классе задач.

3. В рамках теоретико-группового подхода комбинатоной теории переобучения предложено учитывать орбиты действия группы симметрий множества векторов ошибок на подвыборки генеральной совокупности. На основе этой идеи получена новая формула разложения вероятности переобучения по орбитам разбиений. По сравнению с известной до этого формулой разложения по орбитам векторов ошибок новая формула позволяет существенно упростить вычисление вероятности переобуения для ряда модельных множеств векторов ошибок. В частности, на ее основе получены новые точные (не заышенные) оценки вероятности переобучения для трех модельных семейств, являющихся различным! подмножествами шара в Булевом кубе. Новые оценки еще раз

18

подтверждают хорошо известный в комбинаторной теории переобучения факт о том, что получение не сильно завышенных оценок невозможно без тщательного учета геометрических и структурных свойств множества бинарных векторов ошибок.

4. Получено новое PAC-Байесовское эмпирическое неравенство Бернштейна, полностью вычислимое на основе наблюдаемых данных и во многих случаях ведущее к существенно более точным оценкам по сравнению с известными ранее результатами. Доказательство неравенства основано на новом РАС-Байесовском неравенстве для дисперсии, которое позволяет оцепить сверху неизвестное усредненное значение дисперсии потерь с помощью усредненного значения выборочной дисперсии равномерно по классу всех усредняющих распределений. Результаты серии экспериментов, использующих модельные выборки и реальные выборки из репозитория UCI, согласуются с теоретически обоснованным выводом о превосходстве нового неравенства над известными аналогами.

Публикации автора по теме диссертации

Публикации из списка ВАК

1. Tolstikhin I., Seldin Y. PAC-Bayes-Empirical-Bemstem Inequality // Advances in Neural Information Processing Systems (NEPS). 2013.

2. Фрей А. И., Толстихин И. О. Комбинаторные оценки вероятности переобучения на основе покрытий множества алгоритмов // Доклады РАН. 2014. Т. 455, № 3. С. 265-268.

3. Tolstikhin I., Blanchard G., Kloft M. Localized Complexities for Transductive Learning // Proceedings of the 27th Annual Conference on Learning Theory (COLT 2014), JMLR W&CP. 2014. P. 857-884.

Прочие публикации

4. Толстихин И. О. Точная оценка вероятности переобучения для одного специального семейства алгоритмов // Межд. науч. конф. студентов, аспирантов и молодых ученых «Ломоносов 2010»: Докл. 2010. С. 54-57.

5. Толстихин И. О. Вероятность переобучения плотных и разреженных семейств алгоритмов // Межд. конф. Интеллектуализация обработки информации ИОИ-8: Докл. 2010. С. 83-86.

6. Толстихин И. О. Локализация оценок избыточного риска в комбинаторной теории переобучения // Межд. конф. Интеллектуализация обработки информации ИОИ-9: Докл. 2012. С. 54-57.

7. Frey A., Tolstikhin I. Combinatorial bounds on probability of overfitting based on clustering and coverage of classifiers // Machine Learning and Data Analysis (JMLDA). 2013. Vol. 1, no. 6. P. 761-778.

Подписано в печать:

13.08.2014

Заказ № 10154 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ni