§ 3.16. Мера качества алгоритмов

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

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

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

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

.                       (3.49)

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

,  (3.50)

которая требует определенной «гладкости» изменения текущего вектора .

Несколько иной мерой качества алгоритмов может служить значение самого показателя или критерия качества при текущих значениях вектора т.е.

.                       (3.51)

Будем говорить, что функционалы (3.49) — (3.51) определены на алгоритмах, если в них текущие векторы  изменяются по закону, задаваемому алгоритмами. Тогда задача нахождения наилучших алгоритмов, например вида (3.9), сводится к таким выборам, при которых соответствующие функционалы (3.49) — (3.51), определенные на этих алгоритмах, достигают минимума.

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

,                          (3.52)

что соответствует замене истинной плотности распределения на эмпирическую. Такие функционалы, как мы увидим далее, приводят к выражениям , зависящим от величин, которые можно определять по мере прихода и обработки  и оценок . Замена функционала (3.51) функционалом (3.52) соответствует пословице: «Лучше синицу в руки, чем журавля в небе». Но в наших условиях это ведь в самом деле лучше.