Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.04.2024
Просмотров: 189
Скачиваний: 4
328 ГЛ. XIV. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩЕЙ ГИПЕРПЛОСКОСТИ
При е = 0 процесс за конечное число итераций приво
дит к нахождению обобщенного портрета класса |
Y = |
= {уц}, а следовательно, и оптимальной разделяющей |
по |
верхности.
При реализации этой процедуры удобно на каждой итерации при образовании класса У;+1 из Y t удалять все векторы у, входящие с нулевым весом в разложение обобщенного портрета ф(.
§ 12. Некоторые статистические особенности метода обобщенного портрета
Вглаве VI были получены оценки качества алгоритмов, строящих разделяющие гиперплоскости методом миними зации эмпирического риска.
Вчастности, было показано, что для детерминист ского случая математическое ожидание вероятности оши бочной классификации с помощью решающего правила,
построенного по выборке длины I, не может быть меньше
R ~ c ~ r ’
где с — константа, п — емкость класса.
Были получены и верхние оценки качества. Верхние оценки были двух типов — зависящие от размерности про странства (эти оценки следует из общей теории равномер ной сходимости) и оценки, зависящие от относительного расстояния (эти оценки следуют из обобщенной теоремы Новикова 6.2).
В этом параграфе будут исследованы оценки качества алгоритмов, реализующих метод обобщенного портрета. Будет показано, что для этих алгоритмов справедливы одновременно оценки обоих типов (тем самым выполняет ся лучшая из них). При этом существенно то, что верхняя
оценка, |
зависящая от размерности, значительно ближе к |
„ |
п |
нижнеи с — , чем оценки для произвольных алгоритмов,
строящих разделяющую гиперплоскость на основе ми нимума эмпирического риска. Тем самым будут показа ны особые статистические свойства метода обобщенного портрета,
330 ГЛ. XIV. ПОСТРОЕНИЕ РАЗДЕЛЯЮЩЕЙ ГИПЕРПЛОСКОСТИ
контроле на последовательности длины I + 1. Приме нительно к методу обобщенного портрета скользящий кон троль проводится так: из обучающей выборки последова тельно (каждый раз по одному) удаляются векторы хр (хр); по оставшейся части выборки строится обобщенный порт рет фр и проверяется правильность опознания удаленного вектора; после этого подсчитывается частота ошибок.
Справедлива теорема Теорема 14.11. Число ошибок при скользящем контроле
не превосходит числа информативных векторов обобщен ного портрета ф (к), построенного по всей выборке.
Д о к а з а т е л ь с т в о . Достаточно показать, что при удалении неинформативного вектора из обучающей выборки в ходе скользящего контроля ошибки на этом векторе не произойдет.
В самом деле, если вектор хѵ (хр) не является инфор мативным, то существует разложение обобщенного порт рета
аЬ
|
Ф = |
2 |
|
2 |
|
|
|
|
І=1 |
J=1 |
|
|
|
осг > |
0; ß; > 0, |
( Xi , |
ф) > |
1, |
( X j , ф) < |
/г, (14.38) |
®i (1 |
— (жг, Ф)) |
= |
ßj ( * |
— |
(«л ф)) = |
0, |
в которое вектор хр (хр) входит с нулевым весом. Но это значит, что вектор ф является одновременно обобщенным портретом и для выборки, из которой вектор хр удален, так как для него выполняются все условия теоремы 14.6 применительно к укороченной выборке, т. е. ф = фр. Следовательно,
(Хр, фр) = ір'рі ф) |
1 |
или
(хр, ф) == (хр, ф) < к,
а значит, удаленный вектор опознается правильно. Тео рема доказана.
Из теоремы, с учетом несмещенности оценки сколь зящего контроля, немедленно вытекает неравенство
(14.37).
Покажем еще, что число информативных векторов ни когда не превосходит размерность пространства п. Для
§ 12. СТАТИСТИЧЕСКИЕ |
ОСОБЕННОСТИ |
МЕТОДА |
331 |
этого достаточно построить |
разложение |
вида |
(14.38), |
в которое с ненулевым весом входит не более п векторов. Действительно, если в разложении (14.38) входит бо лее п векторов, то всегда можно построить разложение того же вида, в которое входит меньшее число векторов. Всякая система из т ]> п векторов линейно зависима.
Поэтому существуют числа Хі (7j) такие, что
аЬ
2 № —2 W = о,
і= 1 |
3=1 |
причем в это разложение входят только те векторы, кото рые входят в (14.38) с ненулевым весом, и но крайней мере одно Хі (Хі) положительно.
Тогда выражение
аb
Ф= 2 (“ і —*Т і) хі — |
2 (Pi — f T j) b |
( 1 4 . 3 9 ) |
i=l |
y=i |
|
задает семейство разложений обобщенного портрета по своим крайним векторам. Поскольку все а и ß положи тельны, то при достаточно малых по модулю t все коэф фициенты остаются положительными. В то же время,
поскольку среди чисел Ті (Т з') есть положительные, при достаточно большом t 0 некоторые коэффициенты ста нут отрицательными. Значит, найдется t= <min, при кото ром впервые один или несколько коэффициентов разло жения (14.39) обратятся в нуль, в то время как остальные сохранят положительное значение. Применяя это построе ние, если нужно, несколько раз получим искомое разло жение.
Для метода обобщенного портрета при к <С 0 удается получить также оценку качества, зависящую от относи тельного расстояния между классами. При к = — 1 оценка совпадает с выведенной в главе VI (теорема 6.2) оценкой качества для персептронного алгоритма с много кратным повторением обучающей последовательности, а именно:
1
R < (14.40)
1+ 1
