5.8.5. МЕТОДЫ СТОХАСТИЧЕСКОЙ АППРОКСИМАЦИИ

Все итеративные процедуры спуска, рассмотренные ранее, были детерминированными: задавали некоторое множество выборок и образовывали вполне определенную последовательность весовых векторов. В данном пункте придется слегка отступить и рассмотреть процедуры решения по методу наименьшей квадратичной ошибки со случайно формируемыми выборками, что приводит к образованию случайной последовательности весовых векторов. Для полного анализа потребовалось бы использование теории стохастической аппроксимации, и мы бы с этим не справились. Однако основные идеи, которые можно дать без доказательства, просты.

Предположим, что выборки взяты независимо путем выделения состояний природы с вероятностью P(coj) и последующего выбора X в соответствии с вероятностным законом j0(x|c0j). Для каждогох введем метку г, такую, что z= + l при х, соответствующем со,, и г= = —1 при X, соответствующем coj. Тогда данные будут представлять собой бесконечную последовательность независимых пар (хі, Zi), (хз, гО, . . . , (Xft, Zft), ....

Даже если метка z будет бинарной, это может быть истолковано как зашумленный вариант байесовской разделяющей функции 5^о(х). Данное утверждение вытекает из наблюдения, что

и

так что условное среднее для z задается выражением

Предположим, что требуется аппроксимировать gg (х) посредством следующего конечного разложения в ряд:

где известны как базисные функции г/,-(х), так и число членов d. Тогда можно определить весовой вектор а, минимизирующий среднеквадратичную ошибку аппроксимации

Для минимизации е* необходимо знать байесовскую разделяющую функцию |Го(х). Однако, исходя из аналогичной ситуации, рассмотренной в п. 5.8.3, можно показать, что весовой вектор а, минимизирующий 8*, также минимизирует функцию критерия, имеющую вид

Данное заключение также должно следовать из того факта, что г, по существу, является зашумленным вариантом ^о(х) (рис. 5.11). Поскольку

то можно получить решение в замкнутой форме

Таким образом, один из способов, основанный на использовании выборок, состоит в оценке Е {ууЧ и Е [гу] и применении выражения (51) с целью получения оптимальной линейной разделяющей функции. Другой метод заключается в минимизации J„{&) путем

применения процедуры градиентного спуска. Допустим, что вместо действительного градиента подставлено выражение для зашумленного варианта 2(a*yfe—2^) у^. Это приведет к алгоритму спуска следующего вида:

который, по существу, представляет собой правило Видроу — Хоффа. Можно показать, что если матрица Е [ууЧ не вырождена и коэффициенты Pfe удовлетворяют условиям

то aft сходится к а в среднеквадратичном:

Причины наложения данных условий на просты. Первое условие не позволяет весовому вектору сходиться настолько быстро, чтобы систематическая ошибка оставалась бы нескорректированной. Второе условие обеспечивает то обстоятельство, что случайные колебания в конечном счете гасятся. Оба условия удовлетворяются при соответствующем выборе pft=l/fe. К сожалению, такой вид убывания Pk независимо от рассматриваемой задачи часто приводит к очень медленной сходимости.

Конечно, указанный алгоритм не единственный и не лучший алгоритм спуска для минимизации Например, если матрицу вторых частных производных для J„ задать следующим образом:

то можно видеть, что алгоритм Ньютона для минимизации J„ [фс^мула (11)1 имеет вид

Стохастическим аналогш данного алгоритма является при

или, что эквивалентно ^),

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

Указанные градиентные процедуры могут рассматриваться как методы минимизации функции критерия, или определения нуля ее градиента, в присутствии помех. В литературе по статистике такие функции, как J„ и вида Е [/(а, х)1, называются регрессионными функциями, а итерационные алгоритмы называются процедурами стохастической аппроксимации. Наиболее известными из них является процедура Кифера — Вольфовица, применяемая для минимизации регрессионной функции, и процедура Роббинса — Монро, используемая для определения корня регрессионной функции. Зачастую легче всего доказать сходимость процедуры спуска или процедуры аппроксимации, показав, что она удовлетворяет

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