Автоматика и телемеханика, № 6, 2014
Заметки, хроника, информация
Международный симпозиум «Меры сложности», посвященный 75-летию А.Я. Червоненкиса
2 октября 2013 г. в городе Пафос (республика Кипр) состоялся Международный симпозиум «Меры сложности» в честь 75-летия А.Я. Червоненкиса -известного ученого в области распознавания образов и машинного обучения1. Симпозиум был организован Университетом Хэллоуэй (Лондон) и Кипрским университетом (Пафос). В его работе приняло участие более 25 специалистов из разных стран Европы и Америки. С сообщением «Меры сложности» на симпозиуме выступил А.Я. Червоненкис. Кроме этого доклада, в программе симпозиума были представлены сообщения Р. Дадли (R.M. Dudley) из Массачусетского технологического института (США), британских ученых А. Гаммермана и В. Вовка (Университет Хэллоуэй, Лондон), Б. Шёлькоп-фа из Общества Макса Планка (Германия), Л. Ботту из фирмы Майкрософт (США) и нашего соотечественника К. Воронцова (МГУ и ВЦ РАН). В работе симпозиума в режиме телеконференций принял участие многолетний коллега и соавтор юбиляра В.Н. Вапник (США).
В представленных на симпозиуме докладах были подчеркнуты важная роль, которую сыграли в теории распознавания образов методы машинного обучения, разработанные А.Я. Червоненкисом в содружестве с В.Н. Вапни-ком, и влияние полученных ими результатов на фундаментальную область науки - теорию вероятностей. По словам Р. Дадли, «После некоторых предшественников XIX века утверждение о виде сложности класса множеств, сделанное Червоненкисом и Вапником в 1968 г., значительно расширило сферу действия законов больших чисел в теории вероятностей»2.
Доклад А. Гаммермана был посвящен биографии юбиляра. В частности, было отмечено, что А.Я. Червоненкис закончил в 1961 г. Московский физико-технический институт. В 1961-1962 гг. он участвовал в создании и эксплуатации светомузыкальной установки, которая в 1961 г. демонстрировалась в Лондоне. В 1971 г. Алексей Яковлевич защитил кандидатскую диссертацию. С 1987 по 2005 гг. он по совместительству выполнял обязанности научного консультанта фирмы Интегра, где занимался разработкой компьютерных программ для управления разработкой месторождений золота и других драгоценных металлов, за что в 1987 г. получил Государственную премию СССР. В 2000 - 2009 гг. А.Я. Червоненкис был профессором Центра компьютерного обучения Королевского университета в Лондоне. Ему присвоено звание почетного профессора Лондонского университета. С 2007 г. А.Я. Червоненкис
1 Artificial intelligence applications and innovations / Papadopoulos Н., Andreou A.S., Iliadis L., Maglogiannis I. (Eds.) Heidelberg, New York, Dordrecht, London: Springer, 2013. P. XIII-XX.
2 ibid., P. XIX.
по совместительству работает научным консультантом фирмы Яндекс в России. Он профессор Школы анализа данных при Яндексе. В настоящее время А.Я. Червоненкис является ведущим научным сотрудником Института проблем управления.
В. Вовк свой доклад посвятил истории распознавания образов в Институте проблем управления. Отметив вклад, сделанный М.А. Айзерманом и Э.М. Браверманном, он подчеркнул, что А.Я. Червоненкису принадлежит вывод необходимых и достаточных условий равномерной сходимости средних значений к математическому ожиданию, а также введение характеристики класса множеств, позднее вошедшей в современную математику как функция Вапника-Червоненкиса. Порядок ее роста характеризуется константой, которая получила название УС-ёшешюп (размерность Вапника-Червоненкиса). После опубликования монографии «Теория распознавания образов» в 1974 г. А.Я. Червоненкис и В.Н. Вапник стали признанными авторитетами в теории распознавания образов и компьютерного обучения. Среди наиболее значимых научных результатов А.Я. Червоненкиса разработанный вместе с В.Н. Вап-ником алгоритм распознавания образов, известный как «метод обобщенного портрета»3. Развитие принципов и алгоритмов оптимального выбора сложности решения в задаче распознавания образов на основе доступных экспериментальных данных и сложности класса решающих правил стало основой многих алгоритмов машинного обучения.
А.Я. Червоненкис представил на симпозиуме доклад «Меры сложности», в котором он обсуждает проблемы, связанные с введением понятия меры сложности. Давно установлено, что чем сложнее восстанавливаемая модель, тем больше должен быть размер обучающего множества. Это относится как к задаче восстановления функции по экспериментальным данным, так и к задаче распознавания образов, или, в широком смысле, к задаче построения модели на основании экспериментальных данных. Вероятно, первым теоретическим результатом здесь была теорема Котельникова (известная на Западе как критерий Найквиста). Теорема утверждает, что для восстановления непрерывной функции на основании некоторого числа измерений в дискретных точках необходимо количество измерений, пропорциональное ширине спектра функции. Ширина спектра может служить одной из возможных мер сложности.
Вообще говоря, при заданной обучающей выборке исследователь должен ограничить себя определенным уровнем сложности модели, зависящим от объема данных. Но это означает необходимость общего определения понятия сложности и способов ее количественной оценки.
В совместных работах автора доклада с В.Н. Вапником анализ способности системы к обучению был сведен к проблеме равномерной сходимости частот к вероятностям по классу событий (или равномерной сходимости средних к математическим ожиданиям по классу функций). Условия равномерной сходимости были сформулированы в терминах индекса класса событий относительно заданной выборки, функции роста и так называемой размерно-
3 Метод обобщенного портрета послужил основой широко известного метода Support Vector Marine, за разработку которого В.Н. Вапник в 2012 г. получил в США медаль им. Б. Франклина.
сти Вапника-Червоненкиса, или энтропии (VC-function). Если равномерная сходимость имеет место, то система способна обучаться. Обратное, однако, неверно: система может сохранить способность к обучению, даже если такая сходимость отсутствует.
Таким образом, размерность Вапника-Червоненкиса является одной из мер сложности. Она позволяет получить оценки равномерной близости частот к вероятностям, которые не зависят от распределения вероятностей в исходном пространстве. Однако она не лишена недостатков: если эта константа конечна, то система способна к обучению, но способность к обучению может сохраниться и в том случае, когда размерность Вапника-Червоненкиса бесконечно велика.
Асимптотическая энтропия на символ дает необходимые и достаточные условия равномерной сходимости, но они зависят от распределения вероятностей. В большинстве интересных случаев размерность Вапника-Червонен-киса равна или близка к числу неизвестных параметров модели. Важные результаты здесь получены М. Талаграном, Г. Радемахером и другими исследователями. Тем не менее, можно указать случаи нахождения решающего правила, зависящего от очень большого числа параметров, при достаточно небольшом числе показов. В качестве примера можно взять два класса в n-мерном евклидовом пространстве. Каждый их них образован шаром диаметра D, а расстояние между центрами шаров равно R. Если величина R/D достаточно велика, то для 100%-ного распознавания этих классов необходимы всего два показа - по одному из каждого класса вне зависимости от размерности пространства п. Аналогичная ситуация возникает при распознавании двух классов в предположении независимости признаков (при некоторых дополнительных требованиях). Например, в методе бустинга используются очень громоздкие формулы, но, несмотря на это, метод дает неплохие результаты даже при ограниченном количестве обучающих данных.
Все эти случаи заставляют искать новые меры сложности, не связанные с понятием равномерной сходимости. Вероятно, они будут зависеть от распределения вероятностей в пространстве входных переменных. «Но такова природа вещей», - заключает автор.
Р. Дадли в своем докладе «От классов событий к классам функций» отметил, что существуют возможные расширения действия закона больших чисел на семейства функций и что в результате исследований Вапника-Чер-воненкиса оказалось возможным расширить область действия центральной предельной теоремы. Он отметил также многочисленные применения такого расширения в статистике вообще, а не только в исходно поставленной задаче машинного обучения.
В докладе Б. Шёлькопфа «Причинные связи и статистическое обучение» поставлена общая проблема изучения причинных связей с помощью их статистических «отпечатков». Автор проанализировал основные положения причинных связей с точки зрения машинного обучения. Он рассмотрел применения основополагающих причинных структур в популярных сценариях машинного обучения, таких как ковариационный сдвиг или так называемое «semi-supervised learning» - обучение с частичным привлечением учителя.
Л. Ботту свой доклад «О возникновении леммы Вапника-Червоненкиса» посвятил историческому анализу возникновения теории распознавания образов. Он отметил, что переход от простого закона больших чисел к равномерному закону больших чисел основывается на замечательной комбинаторной лемме, которая почти одновременно появилась в нескольких странах, и привел многочисленные данные по анализу этого потрясающего результата (earth shattering result). В частности, он указал, что расположение фамилий Вапника и Червоненкиса в названии леммы определяется просто алфавитным порядком русских букв, так что в этом не надо искать более глубокого смысла.
В докладе К. Воронцова «Комбинаторная теория оверфиттинга: как связность и расщепленность уменьшают локальную сложность» рассматривается подход, который дает твердые границы вероятности оверфиттинга, зависящие от исходных данных. Этот подход требует детального представления поискового пространства в форме направленных ациклических графов, обычно весьма большого размера. Однако их границы могут быть эффективно оценены путем перемещений по их малой локализованной части, содержащей наилучшие классификаторы. В отличие от методов бустинга, баггинга или метода случай
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.