Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 205
Скачиваний: 4
290 ГЛ. X III. ПРИМ ЕНЕНИ Е ТЕОРИИ РАВНОМЕРНОЙ СХОДИМОСТИ
Поскольку F (х, а) равномерно ограничена, в силу предыдущего результата с вероятностью 1 найдется Іг такое, что при I >• Іх
sup IМ' (а) — М''мп (а) | < — .
а |
^ |
Кроме того, из усиленного закона больших чисел следует, что с вероятностью 1 найдется 12 такое, что при I > 12
Ä o p - J j f ' (x)dP{x) | < - J - .
Но тогда при 1 > 10 = max (Zx, 12)
sup I М (а) — Мдмп (а) | < е,
а
что и требуется.
3. Ле-Кам [84, 85], основываясь на идеях Вальда получил следующий результат.
Пусть F (X, а) — измеримая по х функция, непрерыв ная по а почти для всех х , а изменяется в пределах мет рического компакта G и существует К (х) такая, что
F (х, а) < К (х), J К (х) dP (х) < оо.
Тогда, если математическое ожидание F (х, а) существует для всех а, то
lim sup IF (x, a) — ^ 8МП(x, a) | = 0,
l —»оо a
T. e. имеет место равномерная по параметру сходимость средних к математическим ожиданиям.
Этот результат не перекрывает изложенные выше хотя бы потому, что здесь требуется непрерывность, тогда как предыдущие критерии включали также и разрывные функции, обычно используемые в распознавании. Кроме того, в рамках идей Вальда — Ле-Кама, видимо, трудно получить какие-либо оценки.
Г л а в а XIV
П О С Т Р О Е Н И Е Р А З Д Е Л Я Ю Щ Е Й Г И П Е Р П Л О С К О С Т И ( М Е Т О Д О Б О Б Щ Е Н Н О Г О П О Р Т Р Е Т Д )
§ 1. Оптимальная разделяющая гиперплоскость
Выше было показано, что конкретные алгоритмы обу чения машин распознаванию образов могут быть по строены по следующей схеме: из класса решающих пра вил подходящей емкости выбирается правило, мини мизирующее количество неправильных классификаций элементов обучающей последовательности.
При этом чрезвычайно важным оказывается способ задания класса решающих правил. Во многих случаях этот класс задается параметрически, т. е. считается, что функции известны с точностью до значения конеч ного числа параметров. Волее того, класс функций за дается линейно по параметру, т. е. в виде
Выбрать функцию из этого класса—значит найти соответствующие а или, что тоже самое, построить соответствующую разделяющую гиперповерхность
П
2 а гфі(ж) =0.
Ha практике такая задача решается путем построения гиперплоскости, разделяющей в соответствующем спрям-
§ 1. ОПТИМАЛЬНАЯ РАЗДЕЛЯЮЩАЯ |
ГИПЕРПЛОСКОСТЬ |
293 |
ляющем пространстве Y {ух = |
cpj (х), . . ,,уп = |
срп (о:)) |
два конечных множества векторов: множества векторов обучающей последовательности, относящихся к первому и ко второму классам.
В этой главе будут рассмотрены методы построения разделяющих гиперплоскостей. Однако следует иметь в виду, что рассмотренные здесь методы немедленно могут быть использованы для выбора решающего правила из заданного множества линейных по параметру решающих правил.
Два |
конечных множества ^векторов: |
множество |
X — {х1 , |
. . . , х а) и множество X = (жг , . |
. . ,.х ъ} раз |
делимы гиперплоскостью, если существуют такой единич
ный вектор ер и такое число с, |
что для любого вектора |
|
Хх е= X справедливо неравенство |
|
|
(хх, ф) > |
с, |
(14.1) |
а для любого вектора Xj £= X — |
неравенство |
|
(X], ф) < |
с. |
(14.2) |
В случае, когда выполняются (14.1) и (14.2),_говорят также, что множество X отделимо от множества X гипер плоскостью
(х, ф) = с.
Определим для любого единичного вектора ф две вели чины сг (ф) и с2 (ф):
d (ф) = min (хь ф),
с2 (ф) = max (Я;, Ф).
XjG-X
Согласно определению величин сх (ф) и с2 (ф) всегда спра ведливы неравенства
(гг, ф) > сх (ф) (г = 1, 2, . . . , а),
(xj, ф) < с2 (ф) (/' = 1, 2, |
. . ., Ь). |
Ясно, что если |
|
Сі (ф) > с2 (ф), |
(14.2') |
