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

очень напоминает структуру ранее исследованного отно­ шения

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

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

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

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

§ 10. Упорядочение по эмпирическим оценкам относительного расстояния и задача минимизации суммарного риска

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

140 ГЛ. VI. МЕТОДЫ УПОРЯДОЧЕННОЙ МИНИМИЗАЦИИ РИСКА

решающих правил и применен метод упорядоченной ми­ нимизации риска.

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

Р(а)= I (со — F (х, а))2 dP (х, со),

если функция Р (со, х) неизвестна, но зато дана случай­ ная и независимая выборка пар (обучающая последова­ тельность)

•TljCOj,. • - ,

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

стью задается выборка векторов

х\ ,. . ., Хр“,

которую будем называть рабочей выборкой. Рабочая вы­ борка получена из выборки пар, найденной при случай­ ных и независимых испытаниях, согласно распределе­ нию Р {х, со):

ч©1 ) • • •? %р) 0)р •

(Из этой выборки пар отбираются только элементы х*, элементы со* считаются неизвестными). Задача состоит

втом, чтобы, используя обучающую последовательность

ирабочую выборку, найти в классе характеристических функций F (х, а) такую функцию, которая минимизи­ ровала бы функционал

V

Р раб(°0 = 2 (ШІ —F (ж*>°0)2-

і — 1

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

142 ГЛ. VI. МЕТОДЫ УПОРЯДОЧЕННОЙ МИНИМИЗАЦИИ РИСКА

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

D — шах IХі — Xj ||. i, J

Упорядочим теперь класс линейных решающих пра­ вил по следующему принципу. К первому классу S x отнесем такие решающие правила, для которых выпол­ няется равенств)

где р — расстояние от гиперплоскости до ближайшей из точек разделяемых множеств. К классу St — те гипер­ плоскости, для которых

Заметим, что упорядочение решающих правил прово­

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

п — размерность пространства.

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

ку и ошибающееся на рабочей с частотой, превосходящей е, меньше

где

d = min (t -f- 2, п 4- 1) .

Д о к а з а т е л ь с т в о . Число различных разбие­ ний выборки хъ . . . , х2і с помощью правил из S t конечно. Обозначим его числом N it значение которого оценим ни­ же. Вероятность того, что для фиксированного решающе­ го правила частота ошибок на обучающей и рабочей вы­ борках уклонится более чем на е, в условиях теоремы равна

rtk

V I Ь т *Ь 2І-т

здесь т — число ошибок на полной выборке, к — число

ошибок в двух нолувыборках.

Как показано в приложении к главе X, при любом

От 21 имеет место оценка

гік f t l —к

кC2l

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

Р(е)<ЗіѴ г <г1Ѵ-і>.

ШГЛ. VI. МЕТОДЫ УПОРЯДОЧЕННОЙ МИНИМИЗАЦИИ РИСКА

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

С? при m eZ,

Ь21

0 при m ^ e l ,

где т — число ошибок на полной выборке. В свою оче­ редь

Тогда вероятность Р (е) того, что найдется решающее правило из S (, безошибочно делящее обучающую выбор­ ку и ошибающееся на рабочей с частотой, превосходящей

е, оценивается как

_ _ЕІ_

P ( e ) < N r e \

Для доказательства теорем остается оценить число N t. Оно равно числу разбиений точек выборки хъ . . . , х2і на два класса таких, что расстояние между их выпуклыми

D

оболочками больше или равно 2р, = -у=- (условие /). Как

V t

показано в главе X, это число не превосходит

mS( 2 Z ) < l,5 i§

где d — максимальное число точек выборки, для которых любое разбиение на два класса удовлетворяет условию I. Отметим, что если условие I выполняется, то разбиение заведомо осуществимо с помощью гиперплоскости; поэтому заведомо d ^ п -f- 1, где п размерность прост­ ранства.