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

К главе V

Построение алгоритмов обучения распознаванию образов на основе методов минимизации эмпирического риска началось сразу же с появлением первых работ Ф. Розенблатта. За границей — это работы О. Селфриджа [91], система программ Г. С. Себастиана [58], в СССР работы [9—19]. Однако наиболее четко идеология минимизации эмпирического риска проявились у В. Хайлимена [81]. Хайлимен предлагал различные алгоритмы построения линей­ ного решающего правила, минимизирующего число ошибок. Он оценивал вероятность ошибок на экзамене по частоте ошибок на обучении и применял сглаживание функции штрафа для по­ строения эффективного алгоритма минимизации. Обобщение этой постановки на произвольные классы решающих правил было дано

вработе [41].

Впервые идея о связи равномерной близости частот к вероят­

ностям по классу событий с оценкой качества алгоритма, миними­ зирующего эмпирический риск, была высказана в работе [16]. Од­ нако в этой работе был исследован лишь случай конечного числа событий. Затем удалось получить условие равномерной сходимости для случая, когда частоты равны нулю [17]. И, наконец, были по­ лучены исчерпывающие необходимые и достаточные условия равно­ мерной сходимости частот появления событийк их вероятностям [18].

Несмотря на то, что условия равномерной сходимости частот к вероятностям не были известны, многие авторы понимали, что ем­ кость класса решающих правил влияет на экстраполяционную способность алгоритма. Такие идеи можно проследить у М. М. Бонгарда [4]. Н. Нильсон в своей монографии [49] приводит оценку числа линейных решающих правил, разделяющих в и-мерном про­ странстве I векторов.

Что же касается конструктивных идей построения алгоритмов обучения распознаванию образов, реализующих метод минимизации эмпирического риска, то они много разнообразней идей, основанных на реализации других методов минимизации среднего риска. Во всяком случае методы минимизации эмпирического риска позволяют эффективно искать решающие правила не только в классе линейных или кусочно-линейных правил, но и в иных классах решающих правил, например в классе логических функций определенного вида [4, 9, 10].

К главе V I

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

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

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

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

Первые работы по теории обучения распознаванию образов во многом были посвящены исследованию этих двух особенностей за­ дачи. Именно поэтому период «распознавательной романтики» так богат гипотезами о структуре «разумных» задач. В этом отношении, вероятно, наиболее интересной работой остается монография М. М. Бонгарда [4]. Гипотеза о структуре «разумных» задач, по су­ ществу, содержится и в алгоритмах Браиловского — Лунца [5], [6], и в идеях раздвигающей метрики Себастиана — Неймарка [48], [58], и во многих других алгоритмах. Наконец, следует отметить работу Н. В. Загоруйко [30], который явно высказал гипотезу о структуре «разумных» задач в терминах сложности. Во всех этих ра­ ботах гипотеза о структуре «разумных» задач нужна была для того, чтобы ввести априорное упорядочение возможных задач и искать решение не в классе всех возможных задач, а в некотором подклассе, т. е., по существу, для того, чтобы провести идею упорядочения минимизации риска.

Следует отметить, что идея упорядоченной минимизации риска не является новой в математике. Она появлялась каждый раз, когда метод минимизации эмпирического риска приводил к абсурд­ ным результатам. Впервые, вероятно, эта идея возникла при иссле­ довании задачи об определении степени полиномиальной регрессии. Известно, что если априори задана степень полиномиальной регрес­ сии, то метод наименьших квадратов является, вообще говоря, эф­ фективным средством построения регрессии [43]. Другое дело, если заранее степень регрессии неизвестна и предлагается, используя выборку фиксированной длины, определить и степень регрессии и значение ее параметров. В этом случае заранее известно, что мини­ мум эмпирического риска будет достигнут, если степень полинома равна длине выборки. Однако такое решение является абсурдным. Поэтому в свое время К. Ф. Гаусс предложил минимизировать не

величину эмпирического риска Нэмп (а), а величину р і — Дэмп (а),

где I — объем выборки, а п — степень полинома. По существу, эта процедура поиска полиномиальной регрессии является двухуровне­ вой процедурой. На нервом уровне методом наименьших квадратов строится I — 1 оценка регрессии различной степени, а на втором уровне выбирается то решение, которое минимизирует приведен­

ную оценку.

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

минимизации риска.

Идея упорядоченной минимизации появилась и в связи с реше­ нием некорректных задач математической физики. Согласно А. Н. Тихонову [60], решение уравнения

Ах = у

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

где а — есть некоторая константа.

Последний метод носит название метода регуляризации Тихо­ нова [61]. Заметим, что регуляризация по Тихонову есть тоже про­ явление метода упорядоченной минимизации. В самом деле, вве­ дем сначала априорный порядок в классе возможных решений

II * І К Си ■ • •> II ж І К с „ (Сі < с2 < . . . < с „),

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

/ь причем значение а определяет правило выбора второго уровня.

Всамом деле, минимизация (*) при условии || х || ^ С{ эквивалентна минимизации (**), где а — множитель Лагранжа.

Таким образом, оказывается, что идея упорядоченной минимиза­

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

икаков должен быть критерий выбора второго уровня.

Взадаче обучения распознаванию образов были рассмот­ рены две процедуры выбора второго уровня: процедура метода

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

К главе VII

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

В главе VII приведены результаты практического применения алгоритмов метода обобщенного портрета. Эти результаты могли быть получены только благодаря работам больших коллективов уче­ ных. Так, задача о различении водоносных и нефтеносных пластов в скважине была поставлена в Московском институте нефтехимиче­ ской и газовой промышленности под руководством Щ. А. Губерма­ на [25] и была успешно решена также группой М. М. Бонгарда, ра­ боты по криминалистике поставлены в Институте судебных экспер­ тиз под руководством Л. Г. Эджубова [28], работы по контролю качества электронных приборов были поставлены В. С. Морозовым [47], работы по применению методов обучения распознаванию обра­ зов в метеорологии ведутся в Гидрометцентре СССР под руковод­ ством А. И. Снитковского [3] и в ВЦСО АН СССР под руководством Л. Н. Романова [56]; наконец, работы по применению методов обуче­ ния в медицине ведутся в Институте экспериментальной и клиниче­ ской онкологии под руководством Т. Г. Глазковой и К. Н. Гурария [23] и в I Московском медицинском институте под руководством Л. Д. Линденбратена. Благодаря этим коллективам была отрабо­ тана стандартная методика использования алгоритмов метода обоб­ щенного портрета, найдены оптимальные параметры алгоритмов, словом, сделано все, что необходимо для того, чтобы алгоритмы превратить в рабочий инструмент для решения практических задач.

Кроме названных, существует большое количество других кол­ лективов, которые успешно применяют современные методы обуче­ ния распознавания образов для решения задач практики. В Москве это — группы С. Н. Брайнеса, П. Е. Кунина, которые применяют методы распознавания в медицине [7, 38]; коллектив, возглавляемый Ю. И. Журавлевым, который ведет большие работы по применению распознавания в геологии [29]. В Ленинграде коллектив сотрудни­ ков, возглавляемый В. А. Якубовичем, провел значительные иссле­ дования в криминалистике [35]. В Горьком большая группа сотруд­ ников под руководством Ю. И. Неймарка весьма успешно применя­ ет методы обучения распознаванию образов в медицине [48]. В Ново­ сибирске коллектив, возглавляемый Н. Г. Загоруйко [30], применяет методы распознавания в социологии и другие. В настоящее время идея применения методов обучения распознаванию образов весьма популярна и эти методы привлекаются для решения самых различ­ ных задач практики.

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

Однако, несмотря на это, проблема создания читающих автоматов и автоматов, воспринимающих речь, до сих пор далека от завершения. Эти две задачи сейчас составляют самостоятельные направления исследований [30, 31].

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

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

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

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

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

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