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

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

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

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

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

Добавлен: 11.04.2024

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

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

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

І 2. вЬтУйлЫЁ Ф У й к ц й й

18?

Постановка задачи обучения распознаванию образов сводится к минимизации функционала (9.1). Таким обра­ зом, исследованию подлежит сходимость последователь­ ности (9.4). В том случае, когда точка минимума функ­ ционала (9.1) единственна, из сходимости (9.3) следует

сходимость (9.4)

и, наоборот, из сходимости (9.4) сле­

дует сходимость

(9.3).

 

Итак, будем исследовать сходимость ряда (9.4), т. е.

наша цель — определить

условия, при которых

 

R (а (п))

inf R (а)

в том случае, когда inf R (а) существует.

§ 2. Выпуклые функции

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

XF (xj) + (1 — Я) F (xz) > F (%х± +

(1 — Я) х 2),

0 < Я < 1 .

(9.5)

Приведенное определение выпуклой функции имеет про­ стой геометрический смысл. Прежде всего, отметим, что

выражение х = Ххг +

(1 —Я) х 2, 0 ^ Я<^ 1 для

вся­

кого фиксированного Я опре­

у>

 

 

деляет

точку

X,

которая ле-

 

JFB)

жит на отрезке, соединяющем

 

1

хх и х2.

Обратно,

каждое число у

 

X может быть разложено по хх

1

 

и х 2 единственным

образом,

 

 

У

1

 

причем

 

;

Х2—Хі

'

 

 

Хч—Х\ Ѵ

------- 1Рис.

.20.

 

 

 

 

 

 

 

 

«V

—-----і---- ^

%=

 

(1-Я ) =

 

.

(9.6)

1

X

 

 

1

1

 

Если рассмотреть график функции F (х) (рис. 20) и его дугу между точками (x^j), (х2у2), где ух = F (^) и у2 = = F (х2), то неравенство (9.5) означает, что дуга гра-

188

г л .

XX.

О СХОДИМОСТИ

РЕК У РРЕН ТН Ы Х АЛГОРИТМОВ

фика лежит

под

хордой,

соединяющей любые две точки

графика :

 

 

 

 

 

2

^

F ы

+

F ы

> f (x), Xl< x < : x 2.

(9.7)

Аналогично определяется выпуклая функция в случае векторного аргумента: для любой точки х, лежащей на отрезке, соединяющем две точки хг и х2, имеет место не­ равенство

+

<9-8>

§ 3. Обобщенный градиент

Вернемся к процедуре (9.2). Здесь обычно в случае, когда функция Q (z, а) дифференцируема по а, в качестве

вектора

q (z{,

а (і — 1)) берется градиент

по а

функции

Q (z, а)

при

z — zu а = а (і — 1). Градиент

функции

F (а) будем

обозначать VF (а). Таким

образом,

(9.2)

имеет вид

 

 

 

 

а (і) =

а (і — 1) — Y (і) Ѵа Q (zu а

(i — 1)).

(9.9)

Как известно, градиентом функции F (а) в точке а 0 называется вектор q такой, что функция (q, (а — а 0)) является главной линейной частью приращения

AF ~ F (а) — F (а0),

т. е.

AF = (?, (а — а о)) + о (а — а 0),

(9.10)

где о (а — а 0) — величина более высокого порядка ма­ лости по сравнению с | а — а 0 |.

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

AF = F ( а ) — F (а0) > (д, (а — а 0)). (9.11)

Существование обобщенного градиента для выпук­ лых функций в любой точке а показано, например, в работе [27].

§ 3. ОБОБЩЕННЫЙ ГРАДИЕНТ

189

Очевидно, что во всех точках, где выпуклая функция дифференцируема, обобщенный градиент совпадает с обыч­

ным. В

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

точке а 0

VF (а0)

ф V0F (а0).

Тогда

существует

вектор

е такой,

что

 

((V0F - V F ) ,

е) =

с >

0.

 

 

 

 

 

 

Положим

а (t)

=

а 0 +

te.

 

 

 

 

 

 

 

 

 

Тогда

 

 

 

 

 

 

 

 

 

F (а0) -

 

F (а (t)) -

(VF,

e)t + o(t) =

 

 

 

 

 

=

(VoF,

e ) t - c t + о (t). (9.12)

Поскольку с > О,

а о (t)

— величина

второго

порядка

малости,

при достаточно малых t ф- 0

обе части равенст-о

ва (9.12)

становятся

меньше,

чем (Ѵ0

F,

е), что противо- '

речит

(9.11).

 

 

 

 

 

 

 

Рассмотрим пример выпуклой функции, которая не

всюду

дифференцируема:

 

 

 

 

 

 

Ф (а) = I (а, z) — с j ,

где z — некоторый фиксированный вектор, а с — фикси­ рованный скаляр. Эта функция имеет градиент всюду, за исключением многообразия

{а: (а,

z) — с}.

 

Определим обобщенный

градиент следующим образом:

 

Z

при (<х0, z) >

с,

VоФ (о-о)

0

при (а0, z) =

с,

 

—z при (а0, z) <

с.

При (а0, z) Ф с обобщенный градиент совпадает с обыч­ ным, а при (а0, z) = с условие (9.11), очевидно, выпол­ няется, поскольку нри этом

(Ѵ0Ф (а0), (а — а 0)) = 0,

вто время как

Ф(а) — Ф (а0) = Ф (а) > 0.

190ГЛ. IX. О СХОДИМОСТЕЙ РЕКУРРЕНТНЫХ АЛГОРИТМ0Й

Вглаве IV была введена в рассмотрение функция потерь

П

Q (г,а) = 2 ° і гі + с

а :Zl

г=1

 

Как нетрудно убедиться, в качестве обобщенного гра­ диента суммы функций можно взять сумму обобщенных градиентов.

Поэтому для этой функции обобщенный градиент можно положить равным

 

 

П

2z

при

2 <*»**>*.

 

 

г—1

VaQ (z, а) = Z

 

П

лри

2 aizi =

 

 

г—1

 

 

п

0

при

2 аг2І <С С-

 

 

г=1

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

Q (z, а) — Q (z, а 0) > (Ѵ0 Q (z, а 0), (а — а 0)).

§ 4. Условия сходимости рекуррентных алгоритмов

Итак, пусть задана выпуклая по а при любом фиксиро­ ванном z функция потерь Q (z, а) и определена процедура получения последовательности а (1), . . ., а (п), . . .:

а (і) = а (і — 1) +

у (і) Ѵ„ Q (zb

а (i — 1)).

Рассмотрим несколько более общую, чем в главе IV,

процедуру образования

последовательности

а (г) = а (г — 1) + у (г) [V0 Q (zt, а (г —

1)) + У , (9.13)

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

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