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

Г л а в а V

А Л Г О Р И Т М Ы , М И Н И М И З И Р У Ю Щ И Е Э М П И Р И Ч Е С К И Й Р И С К

§ 1. Метод минимизации эмпирического риска

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

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

Нет, это не так. Вот пример обучающегося устройства, которое минимизирует эмпирический риск, но не способ­ но обучаться. Устройство запоминает элементы обучаю­ щей последовательности, а каждую ситуацию, предъяв­ ленную для распознавания, сравнивает с примерами, хранящимися в памяти. Если предъявленная ситуация совпадает с одним из хранящихся в памяти! примеров, to она будет отнесена к тому классу, к которому относится

90 ГЛ. V. МИНИМИЗАЦИЯ ЭМПИРИЧЕСКОГО РИСКА

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

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

§ 2. Равномерная сходимость частот появления событий к их вероятностям

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

Р (а) = j(cü — F (х, а))2 dP (со, х).

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

I

Рэмп (а) = ѵ(а) = 4" S К — F (я, а))2

г—1

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

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

92ГЛ. V. МИНИМИЗАЦИЯ ЭМПИРИЧЕСКОГО РИСКА

Вслучае, когда выполняется (5.1), говорят, что имеет место равномерная сходимость частот к вероятностям по классу S событий А (а). Каждое событие А (а) в классе S задается решающим правилом F (х , а) как множество векторов X, которое это правило ошибочно классифи­ цирует.

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

событий S.

§3. Теорема Гливенко

Вклассической математике уже однажды решалась задача о равномерной сходимости. В 30-х годах замеча­ тельный советский математик В. И. Гливенко доказал теорему, согласно которой с ростом объема выборки эм­

пирическая кривая распределения сходится к функции

отнесена к первому классу. Теорема утверждает, что ча­ стоты сходятся к вероятностям равномерно по всем собы­ тиям А (а) €= S1.

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

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

Неравенство (5.3) означает, что имеет место равномер­ ная сходимость

Р {sup \ ѵ { А і) - Р { А і) | > е } — >0.

І

Потребуем теперь, чтобы вероятность

Р (sup I V ( A t ) — Р ( A t) I > е }

І

не превосходила величины т), т. е.

Неравенство (5.4) во всяком случае будет иметь место, если величины N, е, т], I связаны соотношением

Разрешая равенство (5.5) относительно е, найдем для данных N, I, т] оценку максимального уклонения частоты от вероятности в рассматриваемом классе событий:

Разрешая равенство (5.5) относительно I, найдем, какова должна быть длина обучающей последовательности, чтобы с вероятностью, не меньшей 1 — т], можно было утвер­ ждать, что минимум вероятности по классу событий S отличается от минимума частоты по этому же классу событий на величину, не превосходящую е:

7 In ІѴ— ln. rj 2ea

Иначе говоря, выше была доказана следующая теорема.

Теорема 5.1. Если из множества, состоящего из N ре­ шающих правил, выбирается решающее правило, частота ошибок которого на обучающей последовательности рав­ на V, то с вероятностью 1 — г) можно утверждать, что вероятность ошибочной классификации с помощью вы­ бранного правила составит величину, меньшую ѵ + е, если длина обучающей последовательности не меньше