15.5. ОПТИМАЛЬНЫЕ МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРОВЕРКИ ГИПОТЕЗ, ОСНОВАННЫЕ НА ЗНАНИИ ПОТЕРЬ НА ПРЕДЫДУЩИХ ШАГАХ, ПРИ ПОЛНОЙ АПРИОРНОЙ НЕОПРЕДЕЛЕННОСТИ

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

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

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

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

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

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

Поскольку при принятии решения существенно используется информация о предыдущих потерях значения которых зависят от принятых ранее решений мы имеем управляемый предыдущими решениями процесс, для оптимизации которого, как это следует из гл. 2, необходимо применить методы динамического программирования [3-5].

Основные рекуррентные соотношения для выбора оптимальных решений в соответствии с идеями теории динамического программирования были получены в § 2.7 и имеют вид

при начальных условиях

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

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

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

где номер решения, принятого на шаге; эмпирическая оценка математического ожидания потерь на шаге в случае принятия на этом шаге решения,

Здесь — символ Кронекера,

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

Поэтому

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

с некоторым начальным условием

Из (15.5.4) и (15.5.5) следует, что оптимальное решение на шаге выбирается равным тому для которого минимальна. Пусть этот минимум достигается при тогда

где первые два слагаемых не зависят от Поэтому входящее в правую часть (15.5.2) выражение для имеет вид

где эмпирическая оценка математического ожидания потерь на шаге, определяемая выражениями (15.5.6), (15.5.9), при условии выбора на этом шаге решения с номером Второе слагаемое в выражении математического ожидания, входящего в (15.5.11), обращается в нуль, поскольку при величина а при математическое ожидание

Так как в (15.5.11) от решения зависит только последнее слагаемое то оптимальное решение определяемое согласно (15.5.2), выбирается равным тому для которого величина минимальна. Продолжая эту процедуру в соответствии с (15 5.2) для получаем следующее правило выбора оптимального решения на любом шаге: оптимальное решение выбирается из условия

причем сами величины определяются при помощи рекуррентных соотношений (15.5.9).

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

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

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

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

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

где

- число раз, когда за предыдущих шагов было принято 1-е решение и при этом наблюдался сигнал

Оценка математического ожидания потерь на шаге для всех удовлетворяет рекуррентному соотношению

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

где определяется в соответствии с (15.5.15).