книги / Математические методы принятия решений

распределениям, зависящим от неизвестного параметра со. Получают последовательную выборку. После каждого наблюдения Х{ можно оценить информацию об о, полученную на основе наблюде­ ний х\, Х2, . ■■, Xi. Каждое наблюдение имеет некоторую стоимость. Предположим, что можно проводить наблюдения последовательно, делая после каждого наблюдения вывод о том, следует ли при­ нять решение d e D или провести очередное наблюдение. После­ довательный выбор может дать, например, выигрыш при проверке большой партии изделий путем извлечения т изделий, из которых допускается к бракованных изделий. Последовательный отбор пре­ кращается, если будет отобрано к бракованных изделий или т — к годных изделий. Как правило, это происходит до отбора всех т из­ делий. В первом случае вся партия будет забракована, во втором — принята.

Рассмотрим задачу последовательного принятия решения при параметрическом пространстве П = {б>ь <02} и пространстве реше-

Риск принятия решения до наблюдения находим по формуле

ро(р) = min{Xip; Х2(1 - р )} .

Обозначим через Д класс всех процедур последовательного реше­ ния 5, требующих хотя бы одного наблюдения, и пусть

р'(р) = inf р(р, 8). обД

Таким образом, байесовский риск р*(р) удовлетворяет соотношению

P*(р) = min{po(p); р'(р)}.

Ранее указывалось, что р'(р) — вогнутая непрерывная функция,

заданная на отрезке [0,1]. Поскольку в формулу риска входит це­ на с, то р'(0) = с и р'(р) > с при всех значениях р е [0,1] (рис. 6.4).

Рис. 6.4. Связь минимального риска р(р) и цены наблюдения

Пусть Е* — множество тех значений р, для которых процесс за­ канчивается, т.е. Е* = {р: р(р) ^ р'(р)}. Предположим, что

тогда Е* является объединением отрезков [0, р'] и [р", 1], причем р' и р" удовлетворяют уравнениям

Х,р' = р(р'), Х2(1 - р") = рip").

Если это условие не выполнено, то Е* совпадает со всем отрезком [О, 1]. В этом случае проводить наблюдения не имеет смысла. Мно­ жество Е* задает байесовскую процедуру последовательного реше­ ния. Трудность состоит в получении информации о функции р'(р), достаточной для того, чтобы явным образом определить р' и р"

Предположим, что априорная вероятность р удовлетворяет усло­

что (о = (Oi при проведенных х\, i = 1,2,..., п, наблюдениях; тогда дальнейшие наблюдения необходимо проводить, если выполнено соотношение р' < \{ х \, х2, ..., х п) < р" Если нарушается первое

неравенство, то принимается решение d2, если второе - принима­ ется решение d\.

Апостериорную вероятность можно записать следующим об­ разом:

Л ^ М*\) — МХп) < В .

При нарушении неравенств принимаются соответственно реше­

ния d\ ИЛИ С?2-

Процедура последовательного принятия решения такого вида называется последовательным критерием отношения вероятно­ стей.

Вычислим вероятность принятия решений d\ п d2 п найдем среднюю стоимость выбора для последовательной процедуры. В большинстве задач точные формулы получить не удается, но суще­ ствуют простые приближенные формулы. Для последовательности наблюдений х п, приводящих к решению d\, выполняется со­ отношение

П71

П / г ( ж » ) ^ А ] ^ [ / 1(хО или P(d] | ь>2) ^ AP(d\ | o>i). г=1 г=1

Для последовательности наблюдений, приводящих к решению d2, получим

Однако P(d\ | (02) + P(d2 |to i)= 1,т. е. точка (P(d2 | соi), P(di | «г)) ле­ жит в области Ф (рис. 6.5). Можно считать приведенные соотноше­ ния приближенными равенствами, т. е.

P ( d l | < 0 , ) = l - P ( d 2 | u , ) * | ^ ,

рию отношения вероятностей необходи­ мо продолжать наблюдения при выпол-

независимы и одинаково распределены. Следовательно, этими же свойствами обладают и случайные величины z\, z2, ..., zn. Для любых заданных значений а к b все моменты распределения случайного числа наблюдений N конечны и процесс выбора за­ канчивается с вероятностью 1, т. е. P(N < 00) = 1, М(N k) < 00 для k= 1,2,...

Если z \, z2, ..., zn — последовательность независимых одинако­ во распределенных случайных величин, для которых M(zj) = т, i = 1 , 2 , . . . , N , то для всякой последовательной процедуры с мо­ ментом М(N ) < оо имеет место равенство

М= mM(JV).

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

После наблюдения х 2 получим

p(x2|x b 6)p(0|xi)

р(01 х\, х 2) =

р(х2|х|)

В общем случае имеем

Искомая функция плотности может быть вычислена по формуле

р(хп+1| х ь . . . , х п, (ùi) =

^ р(хп-\-11х 1). • • >Хц, 6)j, 0)р(01 х 1, ..., Xfi, o)j) dSj Ti 1,2,...,

где член p(xn+i \ х \ , ... ,х п, со*, 0) известен, а р(0 | х \, ... , х п) получа­ ется из соотношения (6.18). Известно, что в среднем апостериорная функция плотности улучшает оценку параметра, которая сходится к истинному значению, если только оно не исключено из априорной функции плотности.

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

Совместное распределение в этом случае имеет вид

Тогда оптимальная решающая граница определяется условием

Обучение без поощрения

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

Совместное распределение определяется следующим образом:

где р(х | г") — условная плотность вероятности для г-ro разбиения, P(zf) — параметр г-го разбиения.

Условная плотность совместного распределения р(х | 0) может быть построена на основе семейства условных плотностей распре­ деления р(х 10j, х"), г= 1,2,..., ni, с двумя множествами парамет­ ров 0 = {01,02,..., 0т } и Р = {P(zf), P(z£),..., P(z£ )}.

Основное уравнение (6.19) примет вид

771

р(х 10) = ^ р(х 10j, zf)P(zf). i= l

Известно, что класс плотностей совместных распределений, для ко­ торых существует единственное решение для 0 и P(z”), ограничен. Метод оценки параметров 0 и P(z”) зависит от конкретных условий задачи.

Рассмотрим два метода оценки параметров совместных распре­

По наблюдениям х \ , ... ,х п необходимо найти оценку 0. Если после­ довательность X], х2, ..., х п разбить на всевозможные комбинации по классам coi и со2, то получим 2п комбинаций. Пусть г” — г-е раз­ биение последовательности x i , x 2, . . . , х п. Тогда апостериорная

плотность вероятности будет

2П разбиений. Оценка параметров производится по взвешенной сумме результатов для каждого разбиения с весами, равными

P ( * " | x i, . . . , x „ ) , i = 1,2, . . . , 2 n .

Объем вычислений при этом растет экспоненциально.

Рассмотрим применение другого метода. По теореме Байеса имеем

Подставляя равенство (6.21) в формулу (6.20), получим рекуррент­ ное соотношение для оценки 0:

р(0 | х ь . . . , х п) =

Если p(0|xi, ...,x„ _ i), p(xn |0,(Oi), p(xn |0,co2), P(toi), P(co2) из­ вестны, то можно получить p(Q | x i , . . . , x n). Пусть P(o>i) и P(co2) известны. Тогда для нахождения р(хп 10, toi) и р(в | х \ , ..., х п) при всех значениях 0 следует предположить, что к величине 0 можно применить конечное квантование, чтобы объем вычислений был ко­ нечным.

Для т классов и ряда неизвестных параметров 0,, относящих­ ся соответственно к Qj, полагая условную независимость обучаю­ щих наблюдений и значений параметров 0*, получим рекуррентное

соотношение для оценки 0*:

В общем случае начальные оценки либо Ро(9г), либо Po(ojj), г = 1,2,...» т , должны быть различны, иначе для всех 0; будет оце­ ниваться одно и то же значение (так как вычисляется одна величи­ на) и система в целом ничему не будет обучена.

§ 6.8. Обучение с помощью стохастической аппроксимации

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

Обучение с поощрением

Имеем наблюдения х \,Х 2,- .- ,х п, щ —число наблюдений, со­

Оценим неизвестную функцию плотности р(х) по наблюдени­ ям х \, Х2, ..., х п, предварительно разложив ее в ряд:

m

В частном случае можно найти оценки неизвестных параметров функции плотности по наблюдениям х\, Х2, ■■■, х п.

Обучение без поощрения

Рассматривается задача оценки параметров в совместном рас­ пределении с помощью стохастической аппроксимации.

Предполагается, что:

1) существуют т классов распределений вероятностей, соответ­ ствующих т классам образов, априорные вероятности P(<Di) кото-

3) обучающие наблюдения взяты из совместного распределе­ ния, построенного из составляющих распределений:

771

р(х I е, о ) = 2 р(х I(Di, 9i)P(6>i); t=i

здесь параметры 0 и P((Dj) неизвестны;

4) существуют несмещенные оценки некоторых статистик Н = {Н(х)}, например моментов; известно для каждого шага про­

5) имеются дополнительные соотношения G(0,pi) = O, обеспе­ чивающие получение единственного решения для неизвестных па­ раметров 0 и p i.

Из равенств F (H ,B ,p\) = 0 и G (0,pi) = O получают оценки 0 и pi ; F(-) может быть найдено из последовательных оценок {Н (х)},