5.8.4. ПРОЦЕДУРА ВИДРОУ — ХОФФА

Ранее было отмечено, что функцию можно минимизировать при помощи процедуры градиентного спуска. У такого подхода есть два преимущества по сравнению с простым выполнением

псевдообращения: 1) не возникает трудностей в случае, когда матрица вырождена, и 2) устраняется необходимость работы с большими матрицами. Кроме того, необходимые вычисления здесь с успехом реализуются схемой с обратной связью, которая автоматически справляется с некоторыми вычислительными трудностями, округляя или отбрасывая члены. Поскольку то очевидно, что алгоритм спуска может быть представлен в следующем виде:

Будет полезно убедиться, что если

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

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

Несмотря на то что матрица размера обычно меньше матрицы размера сохранившиеся требования могут быть еще далее снижены при последовательном рассмотрении выборок и использовании правила Видроу — Хоффа, записанного в виде

На первый взгляд алгоритм спуска представляется таким же, как правило релаксаций. Однако главное их различие состоит в том, что правило релаксаций является правилом коррекции ошибок, так что всегда меньше тогда как правило Видроу — Хоффа обеспечивает «коррекцию» вектора всякий раз, когда не равно . В большинстве случаев, представляющих интерес, невозможно удовлетворить всем равенствам так что процесс коррекций будет непрекращающимся. Таким образом, для сходимости требуется, чтобы уменьшалось вместе с k, выбор является типичным. Строгий анализ поведения правила Видроу — Хоффа для детерминированного случая довольно сложен и показывает лишь, что последовательность весовых векторов имеет тенденцию сходиться к требуемому решению. Вместо дальнейшего разбора этой темы обратимся к очень простому правилу, вытекающему из процедуры стохастического спуска.

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

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

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

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

и

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

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

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

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

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

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

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

Рис. 5.11. Аппроксимация байесовской разделяющей функции.

Допустим, что вместо действительного градиента подставлено выражение для зашумленного варианта Это приведет к алгоритму спуска следующего вида:

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

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

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

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

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

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

при

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

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

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

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