3.5. Классификация адаптивных алгоритмов

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

Аргументные и критериальные задачи

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

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

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

Пусть, например,   –  весовой вектор линейной оценки  гауссовского параметра  по гауссовским наблюдениям  и  – средний квадрат ошибки этой оценки. Тогда поверхности  являются эллипсоидами с центром в  (рис. 3.5).

Рис. 3.5.

 

Может оказаться, что , хотя и  находится от  дальше, чем . Другими словами,  «потребительские» качества вектора  выше, чем  у , несмотря на то,  что  находится дальше от оптимума, чем .

 

Идентификационная и безыдентификационная адаптация

 

  По методу нахождения оптимальных параметров  адаптивные алгоритмы можно разбить на идентификационные и безыдентификационные.

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

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

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

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

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

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

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

Для реализации таких алгоритмов необходима оценка текущего значения , т. е. критерий должен быть наблюдаемым, что является ограничением на область применения этого подхода. Иногда выход может быть найден с помощью замены  на другой, наблюдаемый критерий , от которого требуется только, чтобы точки минимума  и  совпадали в аргументных задачах, а в критериальных – чтобы  приближалось к , когда    приближается к  . Эта методика не означает отхода от адаптивного байесова принципа, поскольку    по-прежнему минимизируется.

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

 

Квазиоптимальные алгоритмы

 Аппроксимация решающего правила

 

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

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

Итак, к реальным данным адаптируется готовый алгоритм с неизменной структурой, изменяться могут только подстраиваемые параметры . Такой подход к адаптации называется аппроксимацией решающего правила. Этот прием применяется, например, когда какая-то готовая аппаратура используется для обработки другого класса данных. Другой пример – поиск для решения данной задачи оптимального алгоритма в классе линейных алгоритмов.