4.2. Математическая формулировка и основное функциональное уравнение

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

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

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

Если классификатор решает остановить процесс, то при использовании оптимального решающего правила средний риск равен Если классификатор решает продолжать процесс и сделать еще одно измерение признаков то средний риск равен

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

имеет вид

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

и вычислим средний риск для шага с номером, меньшим с помощью функционального уравнения (4.1). Конкретно, начиная от известного (или заданного) значения в (4.2), мы получим для шага

где получено из (4.2). На (N - 2)-м шаге

где получено из (4.3). На втором шаге

где получено из третьего шага. На первом шаге

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