Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf

ской статистики, таких как теория стохастической аппро­ ксимации, теория равномерной сходимости частот появ­ ления событий к их вероятностям. Однако необходимость

ванию образов исследователи? Какую специфику они пытаются вложить в формализацию понятия обучения?

Вероятно, в разное время основными в исследовании обучения оказывались разные аспекты этой проблемы. Всего 15—17 лет назад во времена первых работ Розенблатта обучение казалось таинственным феноменом, при­ сущим живым существам, и методика работ по исследо­ ванию обучения напоминала нынешние работы по био­ нике; считалось, что надо подсмотреть у живых существ технологию обучения и перенести ее, как алгоритмы, на ЭВМ.

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

Как же понимается задача об обучении распознаванию образов сейчас? В чем специфика постановки задачи, в чем ее отличие от общей задачи минимизации риска? Оче­ видно, что вся специфика задачи обучения распознаванию образов должна проистекать из того, что класс решающих правил чрезвычайно прост. Применительно к такому простому классу решающих правил надо найти тонкие свойства методов минимизации риска, такие свойства, которые присущи только этому классу и никак не явля­ ются общими свойствами методов минимизации риска. В этом смысле единственная глава, которая была посвя­ щена обучению распознаванию образов,— это глава VI.

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

§ 2. Физики об интуиции

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

Удивительно в этой схеме не то, что отыскивается новая теория, а то, что построенная по такой схеме теория является правильной (способна предсказывать новые явления). Действительно, в принципе существует огром­ ное число формальных «законов», которые могли бы объяс­ нить все известные факты, но которые ничего общего не имели бы с истинными законами природы.

Так, чтобы построить теорию относительности, надо было построить теорию, которая содержала бы в себе классическую механику и объясняла бы еще два-три факта, главный из которых опыт Майкельсона. Формаль­ но таких теорий много. Как же нашел Эйнштейн свою знаменитую теорию?

В общем, физики единодушны в объяснении этого феномена — они ссылаются на интуицию ученого. Однако даже проявление интуиции (не говоря уже о том, что такое интуиция) физики определяют по-разному. Одни говорят, что с их точки зрения теория должна быть наиболее кра­ сивой, другие — необычной, третьи, напротив, считают, что теория должна быть наиболее простым правилом, объясняющим мир. Иначе говоря, физики понимают, что

§ 4. О МИРЕ, В КОТОРОМ ВОЗМОЖНА ИНТУИЦИЯ 181

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

§3. Машинная интуиция

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

Оказалось, что уже в рамках теории минимизации среднего риска удается сформулировать экстремальные свойства, которым должно удовлетворять выбираемое решение. Более того, возможно сформулировать раз­ личные экстремальные принципы, одни из'которых могут оказаться более «глубокими», чем другие. Значит, можно

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

§ 4. О мире, в котором возможна интуиция

При тех способах рассуждения, которые были про­ ведены, «глубина интуиции» определяется введением априорного порядка среди решающих правил. Может показаться, что введение порядка целиком зависит от нашего произвола. На самом деле это далеко не так уж очевидно.

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

Тогда интуицию можно объяснить, если принять ги­ потезу о «мире, где все явления имеют простую функцио­

нальную связь» *), в то время как большая часть функций отражает сложные зависимости. В таком мире, исследуя явления природы, неразумно искать объясняющий их закон в классе сложных функций, это и бесполезно, потому что не хватит экспериментального материала, чтобы его найти, и в этом, по сути, нет необходимости, так как мир «прост». Принятие гипотезы о простом мире позволяет, отбросив подавляющую часть всех функций — сложные функции, искать решение в сравнительно мало­ численном классе простых функций.

Найти наиболее простое правило, объясняющее на­ блюдаемые явления или факты, задача весьма трудная. Наверное поэтому найденное простое правило часто ка­ жется неожиданным. В нашем человеческом понимании простота тесно связана с понятием красоты. Может быть, поэтому свойства «простота», «неожиданность», «красота», которые используют физики для объяснения причины выбора того или иного закона, являются отражением разных сторон одного и того же функционала. Не это ли имел в виду Эйнштейн, когда заметил, что бог изо­ щрен, но не злонамерен. Изощрен, потому что трудно найти экстремальные принципы познания, и не злонаме­ рен, потому что мир познаваем с помощью тех средств, которые нам доступны. Хотя в принципе можно предста­ вить себе такой мир, для познания которого у нас просто никогда не хватило бы опыта.

*) Заметим, что само понятие простоты и сложности функций в математике до сих пор четко не определено. Поэтому в данном случае приходится апеллировать к интуиции читателя.

Частъ вторая

СТАТИСТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ

В первой части книги задача обучения машин распо­ знаванию образов рассматривалась с точки зрения про­ блемы минимизации среднего риска. Последняя формули­ руется так: найти минимум функционала

В (а) = (z, а) dP (z),

причем функция Q (z, а) считается известной, вероятност­ ная же мера Р (г) заранее неизвестна, но зато дана слу­ чайная выборка zv . . Zj, полученная в результате неза­ висимых испытаний с неизменным распределением Р (z).

В этой части книги будет приведено математическое обоснование двух путей решения этой задачи: рекуррентных методов поиска минимума функционала В (а) и методов, основанных на замене функционала R (а) его эмпирической

оценкой

I

Вэмп (а ) = ~J~ 2 Q (2г> а )'

І= 1

Будет установлено, при каких условиях эти методы приводят к успешному решению задачи.

Г л а в а I X

ОС Х О Д И М О С Т И Р Е К У Р Р Е Н Т Н Ы Х

АЛ Г О Р И Т М О В О Б У Ч Е Н И Я

Р А С П О З Н А В А Н И Ю О Б Р А З О В

§1. Определение понятия сходимости

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

быть получено с помощью рекуррентных процедур вида

Каждая такая процедура позволяет получать последо­ вательность значений параметров а:

Как последовательность (9.3), так и последовательность (9.4) суть случайные последовательности, которые порож­ даются реализацией случайного процесса (9.2).

Исследование сходимости алгоритмов, минимизиру­ ющих средний риск, сводится, таким образом, к исследо­ ванию сходимости последовательностей (9.3) и (9.4).

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

Определение 1. Последовательность случайных век­

limPflISn — !о||<&) = 1.

П—*оо

Факт сходимости по вероятности записывается так:

І - І о -

Определение 2. Последовательность случайных векто­ ров . . ., | п, . . . сходится к вектору | 0 почти наверное (іиногда говорят также с вероятностью единица), если, каковв бы ни было е О, вероятность выпвлнения нера­ венства

SUp|Si — 1 о ||< 6

при п-*~ оо стремится к единице, т. е.

lim Р (sup fl Si — Sol < s ) = 1.

п—юо z^u

Сходимость почти наверное принято обозначать так:

Приведенные определения сходимости случайных по­ следовательностей отражают различные требования к по­

жество последовательностей, для которых выполняется

Эму. Сходимость по вероятности есть в некотором смысл©

«сильной» сходимости. Оно означает, что почти все реа­ лизации сходятся в обычном смысле. Сходимость почти наверное может быть определена еще и так.

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

Іггп — go>

71—и зо

равна единице, т. е-

Р (limgn = go) = I-

Легко видеть, что из сходимости почти наверное сле­ дует сходимость по вероятности. В самом деле, так как для любого п справедливо неравенство

Р( Цп - 1 о \ \ < г ) > Р (sup| ] — £о||<е),

то из условия

lim p (sup|£{ — І 0ІІ<е) = 1

тг—>оо

следует

l i m P p n — g o |< e) = 1.

\ Обратное утверждение, вообще говоря, неверно.

Нашей целью является установление условий схо­ димости случайных последовательностей (9.3), (9.4).

Для непрерывных R (сс) из сходимости последователь­ ности (9.3) следует сходимость последовательности (9.4). Обратное утверждение, однако, неверно: может случиться так, что существует множество А 0 точек |, на котором функционал (9.1) достигает минимума. В этом случае

ледовательность (9.4) будет сходиться к одной и той же величине.