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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 196

Скачиваний: 4

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

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

его относит гиперплоскость с наилучшей оценкой каче­ ства.

Таким образом, построение экстремальной кусочно­

линейной

разделяющей поверхности связано

не только

с минимизацией критериев (0.19), (6.21) по

параметрам

р, D, п, d,

по и с минимизацией по параметру I.

§ 14. Приложение к главе VI

Оценим снизу величину минимакса потерь в задачах обучения распознаванию образов.

Пусть задан класс решающих правил F (х , а), а £ S . Рас­

смотрим некоторый круг задач обучения Q, совокупность К ал­ горитмов, выбирающих по обучающей последовательности решаю­ щее правило вида F (х, а). Величина минимакса потерь М 0 опреде­ лена так:

Мо = min max л (Л, Т),

АТ

я(А, Т) = R (А, Т) — min R (а, Т),

aes

где R (А, Т)

— качество

алгоритма А

при

решении

задачи Т,

R

(а,

Т) — качество решающего

правила F (х, а) для задачи Т.

т.

Примем что алгоритм А 0 оптимален в смысле минимакса потерь,

е.

 

М о = max я (Ло, Т).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

т е

Q

 

 

 

 

 

 

Пусть теперь известно, что

задачи

Ті,

. .

.,

TN из Q могут

появиться с

вероятностью Р і,

. . ., PN (2 Р г-

=

1) и

алгоритм

Лі £

К оптимален в смысле средней величины потерь при решении

этих

задач,

т. е.

 

 

 

 

 

 

 

 

 

 

N

 

N

 

 

 

 

 

 

 

 

Ah = min 2

Р р И , T’i) = 2

рія

 

 

7'і>-

 

 

 

 

І=1

 

І—1

 

 

 

 

Нетрудно убедиться, что

 

 

 

 

 

 

 

 

 

 

 

Мі <

М 0.

 

 

 

 

(П.1)

 

В

самом

деле,

 

 

 

 

 

 

 

М 1 =

min 2

(/1і> Ті) < 2

ріп (Л°’ Ті><

2 р і

та,х л

т) = Мо-

 

 

А

 

 

 

 

 

X

 

 

Пусть, наконец, А2 — оптимальный по Байесу алгоритм для задач Ті, . . Тп, появляющихся с вероятностями рі, . . ., р п, и М2 — средние потери для этого алгоритма (алгоритм А2 не обязательно

§ 14. ПРИЛОЖ ЕНИЕ К ГЛАВЕ у і

157

принадлежит К). Тогда

 

М 2 < М і

(П.2)

(равенство достигается, если А2 е К).

 

Таким образом, из (П.1), (П.2) получаем

 

М0^ М 2

(П.3)

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

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

что вклассе S есть безошибочное решающее правило (min Р (я, Т) = О aes

для любой задачи Т).

Пусть п характеризует емкость класса S ; тогда (см. главы V, X) существует п точек ад, . . ., хп таких, что правила из S разбивают их всеми возможными способами. Поставим каждому

разбиению Кі

точек ад, .

. ., хп в соответствие

задачу Г; (всего

2П задач) следующим образом.

 

Полагаем, что вероятностная мера Р (х) сосредоточена в точках

ад, . . ., хп, причем точка ад имеет вероятность і

— р, а остальные

равновероятны

и имеют

Р

 

вероятности ^ ^ .

 

Точка а^ принадлежит первому классу, если разбиением Ri

она отнесена к первому

классу, и принадлежит второму классу,

если разбиением Рч она отнесена ко второму классу. Иными словами,

IР (ОI**)= О,

{1^(1 I*») = 1,

если хіі отнесена разбиением і?г- к первому классу;

Р(0 1**) = 1,

Р(1 I **) = О,

если хіі отнесена разбиением і?г- ко второму классу. Этими соотно­ шениями задача Tt задана полностью. Очевидно, что для каждой задачи Т( в классе S есть безошибочное решающее правило.

Предположим далее, что задачи Ті появляются с равной веро­ ятностью.

Можно убедиться, что оптимальный по Байесу алгоритм для этой совокупности задач таков.

Пусть дана обучающая .последовательность длины /; с вероят­ ностью 1 в ней встречаются только точки из набора ад, ..., хп. Точки из набора ад, . . ., хп, встретившиеся в обучающей последо-

15Ö Гл. ѵ і. МЕТОДЫ УПОРЯДОЧЕННОЙ МИНИМИЗАЦИИ РИСКА

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

М2 (р) = 0,5 (1 - р ) р 1+ 0,5 (п _ 1) ( ^ ~ т ) (* - Т = т ) 1 >

 

> 0 ,5

(П-4)

Здесь

0,5 (1 — р) — средние потери при классификации

точки

Xi при

условии, что она не встретится в обучении; р 1 — вероят-

ность того, что она не встретится в обучении; аналогично 0,5 -

р

—

средние потери при классификации точки xt (і Ф 1) при условии,

что она не встретится обучении, а | і

—

j

— вероятность осу­

ществления

этого условия.

1),

при

котором выражение

Найдем

значение р (0 < р ^

 

 

 

0,5р

 

 

I

 

 

 

 

 

 

 

 

 

 

 

 

 

 

достигает

максимума.

Это

 

произойдет,

если

 

 

 

 

 

 

 

1

при І ^ . п — 2,

 

 

 

 

 

 

 

п — 1

 

 

 

 

 

 

Подставляя р

в (П. 4)

Іи тучитывая+т при(П1>.З),п ~получаем2-

 

 

Мо = min max я (А , Т) >

 

 

 

 

 

 

 

 

 

А

 

 

 

 

 

 

 

 

 

 

 

 

>

 

 

 

0,5

(‘

 

п

при 2

п — 2,

 

п — 1

 

 

^0,2

1

 

 

 

 

 

 

 

 

 

 

0,5 7 + Т

 

1+ 1

7 + Т при 2 >

п — 2.

С л у ч а й

2. Пусть

теперь

задачи

Т

произвольны,

а

алгоритмы

А

выбирают по-прежнему

из

класса S емкости

п

(задача в вероятностной постановке).

Оценим величину минимакса

потерь ІИ0.

 

 

 

 

 

 

 

 

 

 

Пусть Xi, . . . , хп, как и ранее, совокупность точек, разби­ ваемых правилами из S всеми возможными способами. Поставим в соответствие каждому разбиению Ri задачу следующим об­ разом.

1. Вероятность Р (х) сосредоточена в точках ац, . . ., хп,

1

причем все точки равновероятны: Р (xj = -jp .

 

8 14.

ПРИЛОЖ ЕНИЕ К ГЛАВЕ VI

159

2. Условная вероятность Р (о | х) в точках xj,

. . ., хп задана

так:

0,5

— А, если Хк отнесено

Дг- к первому классу,

Р (о |**) = {

0,5

+

А, если хк отнесено

і?; ко второму классу!

Р (1 !**)={

0,5

+

Д, если Хк отнесено Ri к первому классу,

0,5 — Д, если хк отнесено Ä; ко второму классу.

Оптимальным решающим правилом в

классе

S для задачи

Т, очевидно, является такое правило F (х, а), которое классифи­

цирует точки X],

. . .,

хп в соответствии с разбиением Rj. При этом

качество

 

 

R (а, Т) = 0,5 — Д.

 

 

 

 

 

 

 

Оптимальная по

Байесу стратегия обучения А 0 в случае слу­

чае оказывается

следующей:

в материале обучения,

а) Допустим,

что точка х встречалась

причем пі (х) раз была отнесена к первому классу и п2 (х) раз ко второму. Тогда точку х следует отнести к первому классу, если

m (х) > п2 (х),

и ко второму, если

щ (х) <

п2 (х). При пг = п2

классификация

безразлична

(выбирается на

удачу).

б) Если точка х не встречалась в обучающей последостельности,

ее классификация безразлична (выбирается на удачу).

Потери при решении каждой задачи 7^

по этому алгоритму

равны между

собой и задаются выражением

 

Г 2Д

А

1

 

it (Ао,Т) = п

+ — P2J = 2A.pi+ Дрг,

где 2А/п — потери, если точка хг, относимая разбиением Лг- к перво­

му классу,

будет отнесена после

обучения

ко второму (щ (х) <

<( п2 (х)),

или соответственно,

наоборот,

точка, относимая і?г-

ко второму, будет отнесена в результате обучения к первому классу

(щ (х) > п2 (х));

Д/ге — потери

в

случае,

когда

щ (х)

= п2 (х);

рі — вероятность того, что

п\ (х) <

п2 (х) при Р (1 | х) >

Р (0 | х)

или

ш (х) > п2 (х)

при_

Р (1

I х) <

Р (0 I х);

р2 — вероятность

ТОГО,

ЧТО П \ (х)

 

Точные значения рі

и р2 задаются форму-

лами:

 

 

И

 

 

 

ns 0,5 +

Д "i

0,5 -- A \«2

рі =

 

 

1

 

 

n,+ni+ns=I

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пі<П,

 

 

 

 

 

 

 

 

 

(П.5)

 

г>1>0,п,>0.па>0

l\

 

 

 

0,5 +

Д \пі

 

Р'і =

 

 

 

 

 

0,5 — А у**

П,-г712; —I

тілгілз!

-

m

 

 

 

 

 

 

n,=n,

 

 

 

 

 

 

 

 

 

(П.6)

 

 

 

 

 

 

 

 

 

 

 

 

положим

Д =

0,5.

Тогда

 

 

 

 

При

l < n s

M o > 0 , 5

1 -

1 V

: 0,5e

 

 

 

(П.7)

Смотрите также файлы