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

Уравнение (6.12) является уравнением гиперплоскости. При

N= 2 получаем уравнение прямой линии.

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

Di(x) = W i\fi(x) + w a f2(x) + ... + wufi{x) + wu i = \,2,

При r = 2 разделяющая функция называется квадратичной. Тогда

m e l = ^ N ( N + 3).

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

3. Классификатор по минимальному расстоянию. Пусть зада­ но т опорных векторов Ri, i= 1,2, ...,т , где Ri ~ со*. Входной сигнал х предполагают принадлежащим <ÙÙ если расстояние меж­ ду х и Ri, равное ||ж —i?j||, минимально. Это расстояние можно определить, например, следующим образом:

\\x -R i\\ = [ ( x - R in x - R i) ] V 2,

ИЛИ

||ж —.Rj||2 = xrx — xTRi - хЩ + RjRi.

Поскольку произведение х Тх не зависит от г, то разделяющая функ­ ция для классификатора по минимальному расстоянию имеет вид

Di(x) = x TRi + xR j — RjRi, i = l,2 ,... ,m .

Это линейная функция (линейный классификатор).

4. Обучение в линейном классификаторе. Введем дополнитель­ ный вектор у = ( х \ , х м , 1)т = (х , 1)т. Пусть в результате наблю­ дений получены два множества дополнительных векторов, принад­ лежащих Ü>I и (02 соответственно. Для разделимых множеств

yrw > 0, у ~

y*W< 0, у ~ 6>2, w = ( w i,...,w N,WM+i)r.

Если классификатор дает ошибочный или неопределенный резуль­ тат при выбранных w, то берут новый вектор весов ь / = w ± а у, а > 0 (поправочное дополнение). Вначале w выбирается произволь­ но. В результате итерационного процесса получаем значение w', которое считается истинным.

§ 6.5. Последовательная решающая модель для классификации образов

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

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

В случае двух классов образов можно применить последова­ тельный критерий отношения вероятностей Вальда (п. к. о. в.). Он построен для решения задачи о выборе между двумя простыми гипотезами. Пусть случайная величина х обладает функцией плот­ ности р{х, 0), где 0 — испытуемый параметр. Задача заключается в проверке гипотезы Но о том, что 0 = 0о, против гипотезы Н \, со­ стоящей в том, что 0 = 0]. Критерий выбирает гипотезу Но или Н\ на основе наблюдений х \,Х 2, ... ,х п. Допустим, что если гипо­ теза Но истинна, мы хотим получить решение в пользу выбора гипотезы Но с вероятностью, не меньшей 1 —а, а если истинна

гипотеза Н \, то решение в пользу выбора гипотезы Н\ должно иметь вероятность, не меньшую 1 —р.

Для последовательного критерия с постоянным объемом выбор­ ки оптимальное решение этой задачи можно получить, используя критерий Неймана—Пирсона: при данном числе наблюдений п кри­ терий, обеспечивающий наименьшее (3 (наиболее мощный крите­ рий), определяется отношением правдоподобия Хп, имеющим вид

(6.13)

Гипотеза Но принимается или отвергается, когда Хп соответ­ ственно меньше или больше некоторой постоянной. Значение этой постоянной может быть выбрано так, чтобы критерий давал нуж­ ную величину а (ошибку 1-го рода). Однако можно выбрать и так, чтобы критерий имел заданную мощность 1 —р, где р — ошибка 2-го рода.

Последовательный критерий отношения вероятностей аналоги­ чен изложенному критерию и обладает аналогичными оптимальны­ ми свойствами: наблюдения производят до тех пор, пока выпол­ няется условие В < Хп < А, где А и В —соответственно верхняя и нижняя границы (чйсла). Наблюдения прекращаются и прини­ мается решение в пользу выбора гипотезы Но, как только будет выполнено неравенство Хп ^ А ; решение принимается в пользу вы­ бора гипотезы Hi, когда Хп < В. Постоянные А и В называются соответственно верхним и нижним порогами {останавливающими границами). Они могут быть выбраны так, чтобы приблизительно получить заданные вероятности ошибок а и р .

Пусть на n -м шаге оказалось, что

(6.14)

Это указывает на окончательное решение о принятии гипоте зы Но. Из условий (6.13) и (6.14) получим

Р(х IН0) = Ар(х | Я ,),

что эквивалентно равенству

(6.15)

Интегралы берутся по области, которая содержит все замеры, при­ водящие к выбору гипотезы Щ . Из условия (6.15) получим 1 — а = = 43.

Пусть теперь Хп = В; тогда а = В {\ —(3). Отсюда имеем

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

Рассмотрим пример того, как изменяются решающие границы при п замерах признаков.

Пример. Пусть x i, i 2, ..., хп — независимые замеры признаков

то следует продолжить измерения. После второго измерения по­ лучим

то проводится новое измерение хз и т.д. На n -м шаге процесса имеем

г=1

то измеряется xn+i.

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

о2 , А о2 п

заданных вероятностях ошибок а и р среднее число измерений, необходимое для завершения процесса, пропорционально о2 и об­ ратно пропорционально разности т,\ —т%.

Последовательный критерий отношения вероятностей дает ми­ нимум среднего числа наблюдений; математическое ожидание сред­ него числа наблюдений запишется в виде

Процедура п. к. о. в. по существу не зависит от априорных веро­ ятностей Р(Hi), i = 0,1, хотя вероятность ошибок зависит от апри­ орных данных.

Иногда необходимо прервать процедуру наблюдений и принять решение при п = N . Это может быть сделано усечением последо­ вательного процесса при n = N : выполняется обычная процедура п. к. о. в. либо до получения решения, либо до N -TO шага. Если на N -м шаге решение не получено, принимается гипотеза Но при XJV > 1 или принимается гипотеза Hi при Xw < 1.

Для большого числа гипотез предложен обобщенный последо­ вательный критерий отношения вероятностей (о. п. к. о. в.). Пусть имеется т гипотез. На n -м шаге обобщенные последовательные отношения вероятностей для каждой гипотезы определяются сле­ дующим образом:

Решающее правило о. п.к. о. в. состоит в следующем. Отношение Un {x | Hi) сравнивается с останавливающей границей A iH {) для гипотезы Н{. Гипотеза Щ исключается из рассмотрения, если U n ix |H i) < A iH î), i = 1,2,..., m . Останавливающая граница для

гипотезы Щ определяется соотношением

ПО-е»,)

U=i

где вщ — вероятность принятия гипотезы Hi, когда в действитель­ ности истинна гипотеза Нч.

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

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

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

Впоследовательном анализе при повышении верхнего порога А

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

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

§6.6. Байесовская последовательная решающая процедура

Используем здесь определения, данные в § 6.3.

При фиксированном объеме выборки и испытании тп статисти­ ческих гипотез оптимальное решение d* выбирается так, чтобы

минимизировать величину средних потерь

771

p(P,d) = Y l P(Hi)p(Hi,d), i=1

где р(Ни d) = J L(Hu d)p(x \ H{) d(ù — условные потери (условный

a

риск). Другими словами, требуется найти

р(Р, d*) = min р(Р, di).

г

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

Sj е S, j = 1,..., N , определим риск:

тN р

Р(Ни d) = J ] Р(Hi) J ] [Cj(x) + L(HU d3{x)))p(x IЩ) dx,

где Cj(x) —стоимость наблюдений х \,х г, ...,Xj, dj (ж) —решающая функция, основанная на замерах х \, Х2, ■.., Xj.

Далее рассмотрим последовательные решения для двухточечной