Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 160
Скачиваний: 4
28 |
Гл. 1. ПЕРСЁІІТРОН РОЗЕНБЛАТТА |
§ 7. Доказательство теоремы Новикова
Докажем теорему Новикова в несколько более общей
формулировке.
Теорема 1.1. Пустъ дана произвольная бесконечная огра ниченная по модулю последовательность векторов ух, ...
..., уі, ..., принадлежащих множествам {у} и {у}. Пустъ существует гиперплоскость, проходящая через начало коор динат и разделяющая множества {у} и {у}, т. е. сущест вует единичный вектор Л* такой, что
ІУі, Л*) > |
Ра для всех уі е {у}, |
{yj, А*) < |
— Ро для всех i/iG {у} |
и
sup _ I у I = £>< ос.
ѵ=іѵ)ІІ{ѵ)
Тогда при использовании терсептронной» процедуры построения разделяющей гиперплоскости с начальными ве сами R-элемента, равными нулю, число исправлений оши бок не превзойдет числа
Эта теорема утверждает, что если существует гипер плоскость, разделяющая множества {у} и {у}, то персептрон после конечного числа исправлений ошибок построит разделяющую гиперплоскость (которая безошибочно бу дет делить весь бесконечный оставшийся хвост последова тельности).
Д о к а з а т е л ь с т в о . Рассмотрим новую последо вательность уг, ..., У і , ..., которая отличается от исходной только тем, что векторы yt, принадлежащие {у}, заменены на — Уі. Тогда работа персептрона может быть описана так. Обозначим через Лг вектор, координатами которого являются веса Я-элемента после просмотра і членов после довательности.
Если очередной вектор опознается правильно, т. е.
(j/i+li А;) Д> О,
|
§ 1. ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ НОВИКОВА |
2Ö |
||
то изменения настройки не происходит, т. |
е. |
|
||
|
Л-і+1 = Л;. |
|
|
|
Если же |
произошла ошибка, т. е. |
|
|
|
|
(уі+1, At) < 0, |
|
(1.6) |
|
производится исправление: |
|
|
||
|
Л,+1 |
= Aj + Уі+і- |
|
|
Начальный вектор Л0 =-= |
0. |
|
Если |
|
Оценим модуль вектора Л, после к исправлений. |
||||
в момент |
і -j- 1 произошло исправление, то |
|
|
|
I |
Л,+1 I 2 = |
I Лг I 2 + 2 (у;Ч1, Л,) + |
I уг+1 I 2. |
|
Учитывая |
(1.6), а также |
то обстоятельство, |
что |
|
I Уі+і I < -0 ,
имеем
I Л1+1 12 < I Лг 12 + Z)2.
Таким образом, если к моменту t произошло ровно к ис правлений, то
I Л, 12 < k D \ |
(1.7) |
поскольку Л0 = 0.
Далее, по условию теоремы существует единичный век тор Л* такой, что для всех і
(Уі, Л*) > р0.
Оценим величину (Лг, Л*). В начальный момент (Л0, Л*) = = 0. Если в момент г + 1 происходит исправление, то
(Лг+1, Л*) = (Л„ Л*) + (уі+1, А*) > (Л„ Л*) + ро.
В противном случае (Лі+1, Л*) = (Лг, Л*). Таким образом, если к моменту t произошло к исправлений, то
(Л„ Л*) > /ср0. |
(1.8) |
30 |
ГЛ. I. ПЁРСЕІІТРОН РОЗЕНВЛАТТА |
|
|
В силу неравенства Коши |
|
|
|
|
(Л „ Л*) < I А, I • I Л* I = I Л4 I |
|
|
и, |
следовательно, справедливо неравенство |
|
|
|
I Л( I |
кр0. |
(1-9) |
Сопоставляя (1.7) и (1.9), убеждаемся, что эти неравенства могут одновременно выполняться только при
D2
Следовательно, число исправлений не превосходит — ,
LPo
после чего все остальные члены последовательности будут опознаваться правильно. Теорема доказана.
Теорема Новикова была первой теоремой в теории обу чения распознаванию образов. В начале 60-х годов она казалась чрезвычайно интересной и была предсказана многими авторами: ведь согласно этой теореме алгоритм, подсмотренный у природы и вначале сформулированный в традиционных для физиологов терминах поощрения и нака зания, получил простую геометрическую интерпретацию.
Интересной казалась и оценка, полученная в этой тео реме: если спрямляющее пространство персептрона бинар ное, то величина D2 не превосходит величины размерности пространства п. В этом случае справедлива оценка
к
Интересно в этой оценке то, что число коррекций растет с ростом размерности пространства не быстрее чем линейно. Такой медленный рост числа коррекций позволял надеять ся, что удастся построить алгоритмы, эффективно решаю щие задачи достаточно большой размерности.
§ 8. Двухуровневая схема распознавания
Итак, исследование персептрона приводит к рассмотре нию двухуровневой модели. На первом уровне осуществля ется отображение исходного пространства описаний X в новое пространство Y. На втором уровне реализуется алго
§ 8. ДВУХУРОВНЕВАЯ СХЕМА РАСПОЗНАВАНИЯ |
31 |
ритм обучения — построение разделяющей гиперплоскос ти в этом новом пространстве на основании обучающей по следовательности.
Для того чтобы вторая часть могла решать свою задачу, необходимо, чтобы после отображения у = / (х) множества векторов, соответствующие разным классам, были раздели мы гиперплоскостью.
Возникает естественный вопрос, насколько универсаль на идея персептрона, т. е. существует ли такое отображе ние, при котором любые два непересекающихся в исход ном пространстве множества были бы разделимы в новом пространстве гиперплоскостью.
Оказывается, да — универсальна. При не слишком сте снительных ограничениях, например, считая исходное про странство бинарным, такое отображение действительно ножно построить. В. А. Якубович показал даже, что пре образование
У1 = Фі (*), •••, Ут = Фт (з)
может быть осуществлено с помощью пороговых функций, т. е. буквально можно построить универсальный персептрон.
Беда лишь в том, что у универсального персептрона: а) размерность спрямляющего пространства оказыва
ется огромной, б) почти для всех пар непересекающихся в исходном
пространстве множеств отношение D2!р2 в спрямляющем пространстве чрезмерно велико.
Как будет показано ниже, это приводит к катастрофи чески большой оценке необходимой длины обучающей по следовательности.
Поэтому всякая реальная машина должна использо вать специализированное отображение у = f (ж), при кото ром лишь относительно немногие пары непересекающихся в исходном пространстве множеств переходят в разделимые гиперплоскостью.
Выбор такого отображения тесно связан со спецификой данной задачи обучения и должен делаться в нашей схеме до начала обучения, т. е. опираться на априорные сведения о природе распознаваемых образов.
Например, при распознавании изображений в качестве функций срг (X) берутся такие функции, которые по набору
32 ГЛ. I. ІІЕРСЕПТРОН РОЗЕНБЛАТТА
чисел X, характеризующих яркость точек рецепторного по ля, строят новые описания в терминах кривых, пересече ний, кривизны и т. п.
Совсем иные преобразования могут понадобиться при применении распознавания, скажем, в медицине или геоло гии. В каждой конкретной области приложений выбор отображения чрезвычайно сильно связан с конкретными особенностями этой области знаний *).
В пределе наилучшее отображение будет таким, когда все точки, относящиеся к одному классу в исходном про странстве, перейдут в одну точку (а разные классы, есте ственно, в разные точки). При таком отображении задача обучения совсем вырождается, так как для обучения до статочно показать по одному представителю каждого клас са. Построение такого пространства является недосягае мой мечтой всякого, кто строит отображения по априорным данным.
На практике же оказывается, что построение даже «хорошего» спрямляющего пространства представляет со бой чрезвычайно сложную задачу. Поэтому часто в по строенном пространстве целесообразно искать разделение не с помощью гиперплоскостей, а с помощью более слож ных разделяющих поверхностей. Строго говоря, такая схе ма уже не является персептронной. Однако это обстоя тельство никак не меняет основного принципа построения машины, обучающейся распознаванию образов: машина реализует двухэтапную систему обучения, где на первом этапе по априорным данным задается класс возможных решающих правил, а на втором этапе из заданного множе ства решающих правил выбирается нужное. С этой точки зрения персептрон Розенблатта реализует некоторые ку сочно-линейные решающие правила: задание отображения определяет возможные для данного персептрона кусочно линейные решающие правила, а алгоритм настройки весов позволяет выбрать в заданном множестве решающих пра вил нужное.
Итак, задача обучения машин распознаванию образов приводит к двухэтапной схеме распознавания. В эту
*) В этом отношении распознавание зрительных образов при водит к некоторым иллюзиям, поскольку, как правило, каждый специалист по распознаванию является и специалистом по геометрии плоскости.
§ 8. ДВУХУРОВНЕВАЯ СХЕМА РАСПОЗНАВАНИЯ |
33 |
схему укладываются отнюдь не только персептроноподобные распознающие машины — во всякой программе рас познавания априори заложен некоторый запас решающих правил, выбранный из тех или иных соображений (напри мер, решающие правила, реализуемые булевыми функция ми определенного вида, пороговыми функциями, функция ми, инвариантными относительно определенных преобра зований, и т. д.). И только из этого запаса с помощью обу чающей последовательности выбирается нужное правило.
В дальнейших главах книги мы ограничимся исследова нием второго этапа решения задачи. Именно эта часть зада чи была предметом исследования большинства (если не всех) теоретических работ по распознаванию, не привязан ных к конкретным приложениям.
Проблемы, возникающие здесь, тесно переплетаются с задачами математической статистики. С точки зрения ма тематической статистики не очень существенно, какова природа решающих правил. Как будет показано, основ ную роль здесь играют некоторые общие статистические ха рактеристики класса решающих правил в целом.
2 В. Н. Вапник, А. Я. Червоненкис
Г л а в а I I
З А Д А Ч А О Б У Ч Е Н И Я М А Ш И Н Р А С П О З Н А В А Н И Ю О Б Р А З О В
§ 1. Задача имитации
Какую же задачу решает программа, моделирующая процесс выработки понятий? Попытаемся формализовать постановку такой задачи.
Некто, для определенности будем говорить учитель, предъявляет машине ситуации и о каждой сообщает, к ка кому из к классов она относится. Для простоты будем по лагать к = 2, так как при любом другом числе классов последовательным разделением на два класса можно пост роить разделение и на к классов. Для этого достаточно провести к разделений по принципу: первое — отделяет элементы первого класса от всех остальных, а /-ѳ — эле менты /-го класса от всех остальных.
Будем считать, что входная ситуация описывается вектором X. Координаты этого вектора могут выражать яркости точек изображения при распознавании зритель ных образов, энергию в различных полосах спектра для звуковых образов, значения симптомов в задачах меди цинской диагностики, значения параметров систем в тех нических задачах распознавания и т. д.
Последовательность ситуаций с указанием, к какому классу они относятся, называется обучающий последова тельностью.
Задача заключается в том, чтобы построить такую про грамму, которая, используя обучающую последователь ность, вырабатывала бы правило, позволяющее классифи цировать вновь предъявляемые «незнакомые» ситуации (вообще говоря, отличные от входивших в обучающую по следовательность) примерно так жз, как учитель.
§ 2. КАЧЕСТВО |
ОБУЧЕНИЯ |
35 |
Иначе говоря, программа |
должна имитировать |
учи |
теля. |
|
|
Слово «учитель» здесь понимается широко. В частности, это может быть человек (например, при обучении распозна ванию рукописных знаков). Здесь цель обучения — клас сифицировать рукописные знаки примерно так, как это умеет человек. Под учителем может пониматься и природа. Так, одной из важных задач медицинской дифференциаль ной диагностики является различение центрального рака легкого от воспаления легкого по рентгенологическим дан ным и клинической картине болезни.
Здесь в качестве материала обучения берутся случаи с точно установленными диагнозами (верифицированные). Цель обучения — выработать правило, позволяющее по клиническим данным дифференцировать заболевания при мерно так же, как с помощью верификации.
§ 2. Качество обучения
Какие же требования предъявляются к обучающему устройству? Попытаемся в первую очередь уточнить, какой смысл вкладывается в понятие «хорошее» решающее пра вило, т. е. каков смысл утверждения «решающее правило классифицирует ситуации так же, как учитель».
Очевидно, оно должно означать, что между классифи кацией учителя и тем, как ее проводит машина, несовпаде ния составляют небольшой процент. Однако если сущест вует хотя бы одна ситуация, которую машина и «учитель» классифицируют по-разному, то процент несовпадения в ответах существенно зависит от той последовательности ситуаций, по которой он будет исчисляться. Например, ес ли в последовательности много раз встречается ситуация, которую машина классифицирует не так, как учитель, то процент несовпадений будет велик, в то время как при другом составе последовательности он может ока заться мал.
Поэтому необходимо заранее условиться, как будет оп ределяться качество решающего правила, т. е. по какой по следовательности будет исчисляться процент несовпадений. Можно условиться, чтобы процент несовпадений вычислял ся по отношению ко всем возможным входным ситуациям. Однако такое определение качества решающего правила не
2*
36 ГЛ. II. ОБУЧЕНИЕ МАШИН РАСПОЗНАВАНИЮ ОБРАЗОВ
является удовлетворительным: в жизни требуется пра вильно распознавать как можно больший процент встреча ющихся, а не всех возможных ситуаций. Различие здесь заключается в том, что некоторые ситуации встречаются ча ще, их желательно классифицировать правильно, другие ситуации, хотя и возможны, но встречаются сравнительно редко, ошибка (так дальше будем называть несовпадение в классификациях учителя и машины) в последнем случае менее опасна.
Такое положение идеализирует гипотеза о том, что на множестве всех возможных ситуаций X задана функция распределения вероятностей Р (ж). Иначе говоря, считает ся, что в соответствие каждой возможной ситуации ставит ся вероятность появления ее среди элементов, подлежащих классификации. Тогда «потери» от ошибки на ситуации ж могут быть оценены величиной, пропорциональной веро ятности появления этой ситуации. Для каждого решаю щего правила можно подсчитать средние потери от всех его ошибок. Хорошим решающим правилом следует считать в этом случае то, которое дает минимальные средние потери, т. е. обеспечивает минимальную вероятность ошибок при классификации *).
Гипотеза о существовании функции распределения ве роятностей Р (ж) вовсе не предполагает, что она нам извест на. Важно лишь то, что она существует и что ситуации, предъявляемые для классификации, появляются случайно согласно этой функции. Образно говоря, функция Р (ж) является характеристикой среды, в которой будет работать классифицирующее устройство. Качество решающего пра вила определяется вероятностью ошибок при работе в этой среде.
Несмотря на то, что функция Р (ж) нам не известна, ка чество любого решающего правила может быть оценено эмпирически.
Для этого случайно и независимо отбирается некоторое количество примеров, относительно которых выясняется, к какому классу отнес их учитель. Такое множество при меров принято называть экзаменационной последователь ностью. На экзаменационной последовательности опреде
*) Иногда учитывают различные цены ошибок первого и вто рого родов. Однако это принципиально не меняет существа дела.