3.6. Псевдоградиентные алгоритмы адаптации

Из п. 3.5 можно сделать вывод, что для обработки больших объемов данных (в частности, И и их последовательностей) целесообразно использовать безыдентификационные алгоритмы, учитывая требования простоты и работоспособности при значительных вариациях реальной ситуации. В значительной степени этим требованиям удовлетворяют псевдоградиентные (ПГ) адаптивные алгоритмы.

3.6.1. Структура и общие свойства

 

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

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

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

,                                       (3.17)

где  – следующее за  приближение к точке минимума;  – положительная числовая последовательность, определяющая длину шагов;  – градиент функции . Каждый шаг в (3.17) делается в направлении скорейшего убывания . Хотя и при выполнении некоторых условий сходимость   имеет место, она может оказаться очень медленной. Для ее ускорения выбираются направления, отличные от антиградиента (методы Ньютона, сопряженных градиентов и т. д.).

Применению этих методов в обработке И препятствует необходимость многократных и громоздких вычислений , каждое из которых обычно включает в себя всю процедуру обработки  при параметрах . Значительно сократить объем вычислений можно, если вместо  взять усечение , т. е. вычислять градиент не по всей реализации , а только по некоторой ее части , например, в скользящем окне на И. Но тогда в (3.17) вместо точного значения градиента будет использоваться его значение со случайной ошибкой , и получается алгоритм

.                  (3.18)

Последовательность  становится случайной, поэтому случаен и сам факт ее сходимости к .

Случайные ошибки  в (3.18), вообще говоря, не являются серьезным препятствием для сходимости . Существует большой класс методов стохастической аппроксимации, основанных на том факте, что при центрированности ошибки () процедура (3.18) сходится к  , как и процедура (3.17). Применяются и так называемые методы случайного поиска, в которых ошибка  вводится искусственно. Интересно, что наличие случайной ошибки  может даже ускорять сходимость процедуры.

Смысл центрированности  состоит в том, что шаги процедуры (5.2) в среднем выполняются точно по антиградиенту, так сказать «в среднем в правильном направлении». Оказывается, что это условие можно существенно ослабить. Рассмотрим пример, показанный на рис. 3.6, для которого  есть расстояние между точкой  и фиксированной точкой . Тогда антиградиент   направлен по прямой от  к . Если вместо этого направления все время двигаться под углом, например, к нему, то движущаяся точка по спирали будет стремиться к . Таким образом, для сходимости (3.18) к  совсем не обязательно, чтобы . Однако, если в нашем примере взять угол  , то точка будет удаляться от по спирали.

В 1973 г. Я. З. Цыпкиным и Б. Т. Поляком было введено понятие псевдоградиента (ПГ), на основе которого разработан единый подход к анализу и синтезу алгоритмов стохастической минимизации функционалов [18]. Класс ПГ алгоритмов очень широк и включает в себя все (или почти все) алгоритмы адаптации и обучения. Эти алгоритмы основаны на процедуре

,                                           (3.19)

где  – случайное (в частности, детерминированное) направление, вообще говоря, зависящее от предыдущих значений  и от номера шага n. Направление  называется псевдоградиентом  функционала  в точке , если выполнено условие псевдоградиентности

                                      (3.20)

где левая часть есть скалярное произведение, поэтому ПГ в среднем составляет острый угол с точным значением градиента (рис. 3.7).

Алгоритм (3.19) называется псевдоградиентным, если  является ПГ на каждом шаге. В этом случае шаги в (3.19) будут производиться в среднем в сторону уменьшения  и можно надеяться на сходимость    при  (рис. 3.8), хотя и некоторые шаги могут быть сделаны в сторону увеличения . И действительно, выполнение относительно слабых условий оказывается достаточным для сходимости с вероятностью единица при любом начальном приближении  [18].

Главным из этих условий является строгое неравенство в (3.20) при , единственность точки минимума, а также  (обеспечивает возможность дойти из любой точки до ) и (обеспечивает возможность асимптотического уменьшения дисперсии колебаний последовательности ). Последним двум условиям удовлетворяют, например, последовательности вида .

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

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

Отметим, что алгоритм (3.19) является существенно более  общим, чем (3.18), так как в (3.19) не предполагается возможность вычисления  или , хотя бы и со случайной ошибкой, т. е.  может быть и ненаблюдаемым. Необходимо только наличие наблюдаемого ПГ. В частности, в качестве  может быть выбрано (даже зашумленное) значение градиента другого функционала , у которого та же точка минимума, что и  у  .

Допустимость зависимости  от предыдущих значений  дает возможность применения ПГ алгоритмов для обработки не только одномерных данных, но и многомерных в порядке некоторой их развертки. До сих пор предполагалось, что задачей является нахождение точки минимума  функционала , единой для всей реализации Z. Такая точка  существует, но обработка будет оптимальной, если данные Z однородны. Для сходимости  при этом требуется сходимость . Если же, начиная с некоторого момента, ограничить  снизу (например, взять постоянные), то дисперсии ошибок оценок  параметров  перестанут уменьшаться и будут иметь порядок , а сами   будут колебаться около .

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

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

При плавном изменении характеристик наблюдений Z (точнее, при плавном изменении оптимальных значений параметров ), соизмеримом со скоростью переходного процесса процедуры (3.19), появляется возможность применения ПГ алгоритмов к обработке неоднородных данных без их сегментации на участки относительно однородной структуры.

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

Итак, ПГ алгоритмы просты в реализации, применимы к очень широкому классу однородных и неоднородных данных (причём в случае однородных данных сходятся к оптимальным алгоритмам). Адаптация может выполняться непосредственно в процессе обработки, поэтому не требуется линий задержки данных. Отмеченные положительные качества ПГ адаптивных алгоритмов делают их привлекательными для применения в обработке И, а также других больших массивов данных  [1, 4, 5, 11, 12, 19, 24].