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

Заметим, что этот вывод является другим доказательством того, что метод сопряженных градиентов на к-м шаге до­ стигает условного максимума в Е к, так как для этого достаточно, чтобы (gft+1, zt) = 0 при і ^ к.

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

Уі = 0,5, yj = 1 при і ф /, осг = 1

для всех I.

Допустим, что при некотором к~^> і происходит еди­ ничное возмущение величины akti, т. е. Аahti = 1, причем

Аj = 0 при / г, Аск_1:і = 0 при всех і.

Легко видеть, что решение выглядит следующим образом:

396 ГЛ. XVI. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ

т. е. величины aik и cik возрастают примерно как 3fe и имеет место лавинообразное накопление ошибки. Тем не менее, конечно, функция F (х) будет на каждом шаге убывать и процесс будет сходиться, но не за п шагов.

Такого рода явления можно устранить, если на каж­ дом шаге проводить полную А-ортогонализацию очередного вектора zfe+1 относительно всех предшествующих zb а не только zft, но это требует большего числа действий на каждом шаг).

К О М М Е Н Т А Р И И *)

К главе I

Считается, что первой работой, положившей начало исследо­ ванию в области обучения распознаванию образов, была работа Ф. Розенблатта [90]. Американский физиолог ф. Розенблатт рас­ смотрел модель восприятия, которая, вообще говоря, не являлась новой в физиологии. Однако в отличие от других физиологов Ф. Ро­ зенблатт построил эту модель не умозрительно, а в виде техниче­ ского устройства, которое он назвал персептроном. Первоначально алгоритм построения весов і?-элементов персептрона (алгоритм по­ ощрения в терминологии ф. Розенблатта) отличался от того алго­ ритма построения разделяющей гиперплоскости, который был опи­ сан в главе I. Сразу же после публикации сообщения о персептронѳ появилось множество различных исследований законов поощрения. Все они, как правило, обосновывались ссылками на физиологиче­ ские феномены. И только с появлением теоремы американского ма­ тематика А. Новикова [87] алгоритм построения весов А-элемептов получил геометрическую интерпретацию. В свое время теорема А. Новикова произвела чрезвычайно сильное впечатление на иссле­ дователей. Достаточно сказать, что она была передоказана не менее чем десятью авторами.

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

Что касается дальнейших построений моделей восприятия, то они пошли по пути усложнения конструкции персептрона. Ф. Ро­ зенблатт строил и многослойные персептроны, и персептроны с пере­ крестными связями [54]. Однако эти модели, как правило, не оп­ равдывали возложенных на них надежд — на них не удалось проде­ монстрировать ни новых свойств восприятия, ни получить новых теоретических результатов. Подробно исследование возможных и невозможных путей обобщения с помощью персептрона рассмотре­ но в книге М. Минского, С. Пейперта «Персептроны» [46].

В дальнейшем исследование феномена восприятия пошло по пути моделирования на ЭВМ. Однако после появления персептрона в тех­ нике возник интерес к адаптирующимся элементам. Так были

*) Эти комментарии отражают точку зрения авторов на разви­ тие идей в области распознавания образов и никак не^претендует на библиографическую полноту.

К. Штейнбуха [92], адалины Б. Уидроу [94, 95]. Эти элементы нахо­ дят применение в различных технических конструкциях.

Что касается закона поощрения Д-элементов персептрона, то, как теперь выясняется, он фактически реализует релаксационные методы решения линейных неравенств, рассмотренные еще в 1954 г. Т. Моцкиным и И. Шенбергом [86].

К главе I I

Сейчас, вероятно, трудно определить, кто первый предложил рассматривать задачу обучения распознаванию образов как задачу минимизации среднего риска. Такие работы постановочного харак­ тера появились в начале 60-х годов почти одновременно. При этом уже с самого начала обнаруживалась «специализация» в постановке. Одни авторы [53, 72, 73, 74] примыкали к классическим работам дискриминантного анализа и рассматривали задачу обучения рас­ познаванию образов как задачу параметрической статистики, дру­ гие [1, 67, 68, 70, 71] предпочитали видеть проблему обучения в соз­ дании алгоритмов постепенного улучшения качества решающего правила (рекуррентных алгоритмов), третьи связывали алгоритмы обучения распознаванию образов с методом минимизации эмпири­ ческого риска [9—19, 24, 41, 81].

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

Интересно отметить, что содержательная постановка задачи обучения распознаванию образов появилась в 1957—1958 годах, а формальная постановка — только в 1962—1966 годах. Эти пять — восемь лет от содержательной до формальной постановки были чрезвычайно яркими годами — годами «распознавательной роман­ тики». В те времена казалось, что задача обучения распознаванию образов несет в себе начало какой-то новой, никак не основанной на системе старых понятий, идеи, хотелось найти новые постановки, а не сводить задачу к уже известным математическим схемам. В этом смысле сведение задачи обучения распознаванию образов к схе­ ме минимизации среднего риска вызывает некоторое разочарование. Правда, существуют попытки понять задачу в более сложной поста­ новке [32]. Однако таких работ пока чрезвычайно мало.

Сейчас, через много лет после периода «распознавательной ро­ мантики», трудно оценить, что принесла формализация задачи. Не оказалось ли так, что из стремления найти строгую постановку при­ шлось сузить ту содержательную задачу, которую пытались ре­ шать в начале 60-х годов.

К главе III

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

деления. На Практике Почти все исследования проводятся для слу­ чая, когда плотности распределения вероятностей векторов каждого класса заданы нормальным законом. Проблемы, которые подыма­ лись дискриминантным анализом, в основном концентрировались вокруг построения линейной дискриминантной функции. Поста­ новка такой задачи впервые была дана Р. Фишером [77], который для решения ее предложил минимизировать некоторую функцию (функцию Фишера). В 1962 году задача построении линейной ди­ скриминантной функции для нормальных распределений была решена Т. В. Андерсоном и Р. Р. Бахадуром [74, 2].

Другие исследования связаны с попыткой сформулировать функционал, минимизация которого приводила бы к построению линейной дискриминантной функции (не только для нормальных распределений). Сначала в качестве такого функционала использо­ вали функцию Фишера, а затем рассматривались и другие функции [62]. Подробный обзор литературы по дискриминантному анализу приведен в [63].

Случай независимо распределенных дискретных признаков так­ же известен в дискриминантном анализе. В 1952 году А. М. Аттли [93] построил на этом принципе веротностный дискриминантный автомат, алгоритм которого, по существу, мало чем отличается от сов­ местных алгоритмов, использующих гипотезу о независимости дис­ кретных признаков.

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

К главе IV

Идея метода стохастической аппроксимации возникла, по-види­ мому, давно, но в четкой форме была сформулирована в 1951 году Г. Роббинсом и С. Монро [89]. Они указали итеративную процедуру, позволяющую определять корень уравнения регрессии. В 1952 году Е. Кифер и Дж. Вольфовиц применили этот метод для поиска минимума функционала [82]. Начиная с этого времени ведутся рабо­ ты по определению условий сходимости метода. Подробно с библио­ графией метода стохастической аппроксимации можно ознако­ миться в обзоре [42]. В 1965 году Я. 3. Цыпкин указал на связь метода стохастической аппроксимации с рекуррентными алгоритма­ ми обучения распознаванию образов [67, 68]. Эти работы стимули­ ровали исследования по теории метода стохастической аппрокси­ мации.

С 1964 года М. А. Айзерман, Э. М. Браверман, Л. И. Розоноэр разрабатывали теорию метода потенциальных функций, которая оказалась чрезвычайно близкой теории стохастической аппрокси­ мации. Этими учеными получены достаточно тонкие условия сходи­ мости процедур стохастической аппроксимации [1]. Дальнейшие