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

Ранее было отмечено, что функцию (а)=||7а—h|p можно минимизировать при помощи процедуры градиентного спуска. У такого подхода есть два преимущества по сравнению с простым выполнением

псевдообращения: 1) не возникает трудностей в случае, когда матрица Y^Y вырождена, и 2) устраняется необходимость работы с большими матрицами. Кроме того, необходимые вычисления здесь с успехом реализуются схемой с обратной связью, которая автоматически справляется с некоторыми вычислительными трудностями, округляя или отбрасывая члены. Поскольку \js=2Y*{Ya—b), то очевидно, что алгоритм спуска может быть представлен в следующем виде;

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

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

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

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

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