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

где шаг по-прежнему выбирается из условия максимизации функции W (а, ß) по направлению

2) процесс подъема по функции W (а, ß) прекращает­ ся, когда будут выполнены все неравенства (14.16). Легко видеть, что при к = —1 полученный алгоритм совпадает с алгоритмом построения разделяющей гиперплоскости, предложенным Уидроу (см. главу IV).

Нетрудно убедиться, что после каждого изменения вектора ф функция W (а, ß) возрастает на величину

1

AW > 8 D1 ’

D = max (I xt |, | х}\).

Поэтому, учитывая, что, согласно (14.14),

max W (а, ß) = ~ ^ ,

а , (3

где р — расстояние между проекциями классов на на­ правление обобщенного портретаф (к), получаем, что мак­ симальное число исправлений в алгоритме Уидроу ог­ раничено величиной

F (X) в точках х (к) и х (к — 1), а z (к) — направление дви­ жения из точки X (к — 1).

Движение по направлению z (к + 1) ведется до до­ стижения условного максимума. Точка х (к + 1), достав­ ляющая этот максимум, находится (16.26) из выражения

x(k + l) = x{k) + -(T(F I f g + 21}(f +1}) g(fe + 1). (14.18)-

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

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

Рассмотрим следующую модификацию метода сопря­

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

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

где минимум берется лишь по тем координатам і, для ко­ торых z' < 0. При этом для всех і оказывается

Хі (к + 1) 0,

312 ГЛ. XIV . ПОСТРОЕНИЕ РАЗДЕЛЯЮ Щ ЕЙ ГИПЕРПЛОСКОСТИ

но по крайней мере для одной координаты хі окажется, что х’ = 0, т. е. движение происходит до выхода на ограни­ чение.

Итак, в этом случае

X (к + 1) = X (к) + hz (к + 1).

3) Если на некотором шаге к траектория выводит на ограничение, т. е. величину шага приходится уменьшать

по формуле (14.19), то некоторые координаты хіг, . . ., х1т обратятся в нуль. Дальнейший поиск максимума ве­ дется в положительном квадранте координатного под­ пространства En-m размерности п — т, задаваемого уравнениями

хіі = 0, . . ., х т = 0.

Для этого действуем снова в соответствии с пи. 1) и 2), но уже в подпространстве Еп.-т. При этом либо условный максимум функции в этом подпространстве будет найден не более чем за п — т шагов, либо при поиске еще раз будут нарушены ограничения. В последнем случае вновь сокращается размерность пространства и ищется услов­ ный максимум функции в положительном квадранте но­ вого подпространства.

4) Так продолжается до тех пор, пока в положительном квадранте некоторого координатного подпространства хг, . . хп не будет найден условный максимум функции. Пусть он достигается в точке £. Если при этом выполня­ ются условия:

д х 1

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

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

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

Рассмотрим еще одну модификацию метода сопряжен­

дхк

Вектор g (х) есть условный градиент функции F (х) на множестве x t )> 0 (см. формулу (П. 8) приложения). Будем теперь совершать восхождение к максимуму, ис­ пользуя (14.17), (14.18), (14.19), где g (х) заменено на условный градиент g (х). Движение начинается из про­ извольной точки положительного квадранта и происхо­ дит до момента нарушения ограничения в точке х 0. Тогда снова начинается восхождение по методу сопряженных градиентов из точки х 0 и т. д. Поиск максимума закан­ чивается, когда выполнятся неравенства

I gi (х) I < е.

Важной особенностью модифицированного метода по­ иска максимума функции F (х) в положительном квад­ ранте является то обстоятельство, что он допускает по­ следовательную процедуру поиска. Пусть пространство Еп имеет координаты х1, . . ., ж*, хі+1, . . ., хп. Можно сначала найти условный максимум функции при огра­ ничениях X1 > 0, . . ., X1> 0 и хі+1 = 0, . . ., хп = 0.

Затем, используя найденную точку максимума как на­ чальную точку, найти максимум F (х) в области х1 0, ...

. . ., хп > 0.

Применим вторую модификацию метода сопряженных градиентов к задаче нахождения обобщенного портрета.