Если векторы средних двух нормальных распределений равны друг другу и неизвестны, то вместо величины а следует подставить в (22.31) ее оценку по обучающим выборкам:

(All 31 + 2 a2)/(A7i + 2)

(22.33)

л л,

где ai, а2 определяются согласно (22.5).

22.2.5. Алгоритм классификации с самообучением. Вернемся к постановке задачи, изложенной в п. 22.2.2, но с условием, что обучающая выборка Хи ..., Хп не классифицирована. Предполагая, что появление любого из двух классов Si и S2 в каждом наблюдении априори равновероятно, можно рассматривать каждый элемент обучающей выборки как принадлежащий общему бимодальному распределению (смеси нормальных распределений)

w{x\a а,) =

2аУ2я

ехр

+ ехр

(22.34)

Среднее значение случайной величины, подчиняющейся распределению (22.34),

a={ai + a2)/2 (22.35)

неизвестно, так как неизвестны ai и 2.

Выборочное среднее, полученное по обучающей выборке

неклассифицированной

(22.36)

является несмещенной оценкой среднего значения а распределения (22.34).

Используя (22.36) вместо неизвестного среднего, получаем следующий адаптивный состоятельный алгоритм классификации: наблюдение х относится к классу S2, если

х^а, (22.37)

и к классу Si в противном случае.

Алгоритм классификации с самообучением обобщается на многомерный случай при сферической симметрии плотностей вероятности. Решается задача о принадлежности наблюдаемой векторной выборки X одному из двух Л^-мерных нормальных распределений с неизвестными векторами средних ai и аг и заданными ковариационными матрицами Ki = K2 = o2I, где I - единичная матрица. В этом случае общее многомерное распределение двух классов представляется в виде следующей смеси многомерных нормальных распределений:

Г(у(х|а1, а2) = + ехр

2(2яа2)/2 (х-а^) (x-az)

(22.38)

или

(x-a)(- - a)

(22 39)

где

a=(ai + a2)/2, b=: (a2-ai)/2. (22.40)

Вектор a является вектором средних значений распределения (22.39), а элементы коздриациониой матрицы К этого распределения

(22.41) a; bi -

(no оаи-

,.,йх = Ь^Ь,л rih;j i, /=1, iV,

где 6ij - символ Кронекера; аг - компоненты вектора компоненты вектора Ь.

Если векторы средних ai, известны, то оптимальное есовскому критерию) разбиение выборочного пространства проводит гиперплоскость, которая перпендикулярна линии, соединяющей точки x = ai и х==а2, и делит эту линию попола1М. Наблюдение X относится к тому или иному классу в зависимости ог знака величины Ь^(х-а).

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

а оценки компонент вектора Ь можно найти из системы уравнений [см. (21.41)] Rij = bibj + G4ijy где /tij -элемент выборочной ковариационной матрицы

2 (х,-а)(х,~аУ.

22.3. АДАПТИВНЫЕ АЛГОРИТМЫ КЛАССИФИКАЦИИ В УСЛОВИЯХ ПАРАМЕТРИЧЕСКОЙ АПРИОРНОЙ НЕОПРЕДЕЛЕННОСТИ

22.3.1. Метод апостериорных вероятностей. Пусть в результате наблюдения получена векторная (информационная) выборка X. Задача состоит в том, чтобы отнести наблюдение х к одному 21-87 (525

из классов Si,..., Sm. Предполагается, что распределения классов характеризуются плотностями w{x\ky S), k=l, m, причем параметры #i,--,m представляют независимые случайные векто-ры с априорными плотностями вероятностей w{k)y k=l, m, которые отражают первоначальные знания о распределениях этих параметров. Имеется набор обучающих классифицированных выборок Хоб= (xi,..., Хт), где вектор Xk принадлежит классу S/. Эту обучающую выборку можно использовать для корректировки априорных знаний путем определения апостериорной плотности

.=ш(#,)Г(х,< S,) / ;ш(#,)Ц7(х,< S,)d#,. (22.42)

Используя формулу Байеса, определим апостериорную вероятность принадлежности классу Sk при данных Хоб, х:

P{S,x,6, х} = /7,Г(х,б, xS,) / p,W{x , xS,), (22.43)

где Pfe-априорная вероятность принадлежности классу S. По критерию максимальной апостериорной вероятности относим наблюдение к классу Sk, если

P(SJx, х} maxP{S,-Xo6, х}. (22.44)

Так как W(Xo6, х| Sft) = W(xXo6, Sft)W(Xo6), то из (22.43), (22.44) следует

W(х|Хоб, S,) = max [pj W (х\х, Sj)]. (22.45)

Алгоритм классификации (22.45) предписывает вычисление величин pjW{х\хобу Sj), /=1, т, и отнесение вектора наблюдения х к тому классу S, которому соответствует максимальная из указанных величин. Если априорные вероятности pk одинаковы, го классификация при заданном наборе Хоб сводрхтся к определению того класса Sk, для которого наблюдаемая выборка х максимизирует по индексу / функцию правдоподобия W{x Хоб, Sj). Последние мол<но рассматривать как оценки неизвестных плотностей распределений классов при заданном наборе обучающих вы-

ВЫборОК Хоб.

Функцию W(xxo6, Sj) вычисляем, используя формулу полной вероятности

Й7(х|х,б, S,-)== JH(xx, S,.)W(<,.x,6, Sj)dj

или

Ц7(х|Хоб, Sj)= p(x#,-, Sj)W{j\x ,Sj)dj, /=1, m, (22.46)

так как очевидно, что U(*jxo6, Sj) = W(#j1xj, Sj), a функция 626

lF(xXo6, #i, Sj) вовсе не зависит от обучающих выборок. Второй сомножитель з подынтегральной функции (22.46) определяется согласно (22.42).

Заметим, что, когда параметры априори известны и равны их условные плотности представляют дельта-функции

и из (22.46) следует

Г(х|хоб, S,) = r(x#, Sk). (22.46а)\

В этом случае алгоритм классификации совпадает с оптимальным байесовским алгоритмом проверки гипотез [см. (20.11)].

22.3.2. Теорема Бернштейна - Мизеса. Адаптивный алгоритм классификации (22.45) зависит от априорных плотностей w{&k\ распределений параметров [см. (22.42), (22.45), (22.46)]. Проверить возможность использования этого алгоритма без какого-либо определенного предположения об этих априорных плотностях можно с помощью теоремы, установленной С. Н. Бернштей-ном и Р. Мизесом [71]. Сущность ее состоит в следующем. Пусть Xi - выборочное значение из распределения с неизвестным случайным параметром О. Апостериорное распределение этого параметра

W (Uj) = w{f)W {х^\{) I ]w W {х^\Щ d (22.47)

где W (&) - априорная плотность вероятности параметра д. Если извлекается следующее выборочное значение Х2у независимое от Хи то W(6:i) можно использовать в качестве нового априорнога распределения для вычисления апостериорного

= W{{\x)W(xг]f} / lw(-&\xj)W{x,i-&)d& =

I -со

= w{)W {х^\Щ W(х,\Щ I ]w () W (х,1Щ W {х,т dд. (22.48)

Аналогично, когда имеется независимая выборка Хи Хп размером я, то

W(Щх,..... xJ = W(i.-.nl)- 22.49)

где

W{x ...,Xn\= ilWix.l.

Упомянутая теорема утверждает, что если априорная плотность w{&) параметра О непрерывна, то по мере возрастания объ-

ема выборки апостериорное распределение \1(б'л:1, Хп) перестает зависеть от априорного распределения. Таким образом, при достаточно большом п безразлично, какую непрерывную функцию w{&) подставить в формулу (22.49). Эта предельная теорема послужила основой синтеза алгоритма классификации, предложенного Роббинсом [71].

22.3.3. Адаптивный алгоритм обнаружения случайного сигнала на фоне аддитивной гауссовской помехи. В качестве иллюстрации метода синтеза адаптивного алгоритма классификации в условиях параметрической априорной неопределенности рассмотрим следующую задачу. Имеется реализация х скалярной случайной величины, которую следует отнести к одному из двух классов: Si - помеха, представляющая гауссовскую случайную величину с нулевым средним и дисперсией а^, и S2 - аддитивная смесь этой помехи и независимого от нее случайного сигнала, среднее значение а которого--случайная величина, распределённая по нормальному закону с параметрами (ао, а^о). Предполагается, что априорные вероятности принадлежности наблюдения классам Si и S2 одинаковы.

Пусть x=(xi, Хп) - независимая классифицированная выборка аддитивной смеси сигнала с гауссовской помехой. По формул (22.42) находим апостериорную плотность распределения сигнального параметра а [см. (14.119)]

On V2n

exp -

i (a - йпР I

(22.50)

где

a = mi{ax} =

2 % +

o\ = ti2 {a I x} = оУ (rt -1- аУо\). Если известно, что наблюдение х принадлежит классу S2, то I f (x-а)2

(22.51) (22.52)

(22.53)

Используя формулу (22.46), находим

W(x\x,S,)= ]-L ехр

-<х> аУ2я

- ехр - -I da.

2(j2

(22.54)

Так как интеграл в (22.54) представляет свертку двух плотностей нормального распределения, то непосредственно аходим

W{x\x, S,) =-exp

(22.55)

где а^х = о^ + а^пу а величины (22.51) и (22.52).

Если наблюдение х

определяются помеха, то [см. (22.46а)]

Г(а = 0, Si)==

ехр

согласно

(22.55а)

Из (22.55) и (22.55а) получаем следуюпдий адаптивный алгоритм обнаружения [см. (22.45)]: принимается решение, что наблюдение X представляет смесь случайного сигнала с аддитивной гауссовской помехой, если

ехр

а 1 2а2 j

(22.56)

и решение, что наблюдается помеха, в противном случае. После элементарных преобразований алгоритм (22.56) приводится к виду

2

(22.57)

202 s; 2 2 \

Здесь в левой части коэффициент йп зависит от обучающей выборки, а коэффициент о'п/(2а^)-от априори заданных дисперсий а^, а^о и размера п обучающей выборки. Порог в правой части (22.57) зависит и от указанных значений дисперсий, и от обучающей выборки.

Если размер обучающей выборки неограниченно возрастает, то, как следует из (22.51) и (22.52), при п-оо

2 = i

(22.58)

В этом случае квадратический член в левой части (22.57) стремится к нулю, алгоритм классификации становится линейным с перестраиваемым порогом [ср. с (22.9)]

4мп/2 (22.59)

и не зависит от начального априорного Напротив, если а^>0о, то Ппао, а^п^ преобразуется к виду

распределения сигнала. о^о и алгоритм (22.57)

(22.59а)

2а2 S, 2 2

т. е. не зависит от обучающей выборки и полностью определяется априорными данными.

Предположим теперь, что наблюдение х представляет векторную (размером Л^) случайную величину, которую следует отнести к одному из двух классов: Si - гауссовская помеха с нулевым вектором средних и ковариационной матрицей М и S2 - аддитивная смесь помехи и независимого от нее случайного сигнала,

= 1+

вектор средних а которого случайный, подчинен многомерному нормальному распределению с параметрами (ао, Мо).

Пусть xi, Хп - классифицированная выборка аддитивной смеси сигнала и гауссовской помехи. По формуле (22.42) с учетом результатов, приведенных в п. 14.5.7 и 14.5.8, находим, что апостериорная плотность сигнального параметра а подчиняется многомерному нормальному распределению с параметрами

a = mi{aXi,..., х^) =

r(i2,. + iSL). Р2.60)

Mn=(I+MMo-VAz)M/n. (22.61)

Соотношения (22.60), (22.61) можно представить в рекуррентной форме

З-п = an-1 Mn/Mn-1-fXnMn/M, (22.62)

Мп = М (Мп-1 + М) -1Мп-1. (22.63)

Если известно, что наблюдение х приндалежит классу S2, то \Г(х|а, S2) = (2n)-/2(detM)-i/2X

X ехр {- (X-а) (х-а) /2}. (22.64 )

Из (22.46) следует

W (х|х, S,) - I (2я)-/2 (det М)-/х

X ехр j -1- (х - а) М- (X - а) ] (2я)-/ (det Ш^Г' х

X ехр I - -i- (а - а,) М (а - а^} da. (22.65)

Так как интеграл в (22.65) представляет свертку двух плотностей Л^-мерного нормального распределения, то непосредственно находим

lF(xxo6, S2) = (2я)-/2 [det(M-f Мп)]-/2Х Хехр{-(х-ап)(М+М,)-Чх-ап)/2}, (22.66)

где вектор an и матрица Мп определены согласно (22.60), (22.61). Если наблюдение х - помеха, то

\Г (х I а = О, Si) = (2я)-/2 (det М)-1/2 ехр [-xM-ix/2]. (22.66а)

Из (22.66) и (22.66а) получаем следующий адаптивный алгоритм обнаружения: принимается решение, что наблюдаемый вектор X представляет аддитивную смесь случайного сигнала и гауссовской помехи, если

х^М-х- (х-ап) (М + Мп)(х-an)

ln[det(M-fMn)/detM] (22.67)

и решение, что наблюдалась помеха, в противном случае. 630

Если размер обучающей выборки n->oo, то

-- - S амп 0. (22.68)

В этом случае алгоритм классификации линейный с перестраиваемым порогом [ср. с (22.22) и с (22.59)

S. -

X 2мп. . (22.69)

Sj 2

22.3.4. Адаптивный метод преодоления априорной неопределенности мешающих параметров. Пусть в задаче проверки многоальтернативных гипотез (см. § 13.3) функция правдоподобия, соответствующая /-й гипотезе, зависит от векторного мешающего параметра Qj, / = 0, т. Запишем выражение среднего риска как функции мешающих параметров

r (К) =2 21 nft ; (X) Pj W (XЯ dx. (22.70)

k=0 /=0 X

где

ФЛх) =

1. х^Х„

О, хеХ„

Xk - область выборочного пространства X, соответствующая решению yk о принятии гипотезы Hk, Ujk - элементы матрицы потерь, pj - априорная вероятность гипотезы Hj.

Если известны априорные распределения мешающих параметров, то эти параметры можно исключить из (22.70) путем усреднения по этим параметрам, заменив функцию W{x\Hj, &j) функцией

Г(х|Я,)=/ W{x\Hi, *,)W(#,)d*,-, (22.71)

где W{j)-априорная плотность распределения параметра % / = 0, т.

В условиях параметрической априорной неопределенности, когда функции (в';), / = 0, т, неизвестны, при помощи обучающих выборок можно определить оценки максимального правдоподобия &jun мешающих параметров и, как показано в [72], воспользуемся вместо (22.71) приближенным выражением

W{x\Hj)W{x\Hj, {jun)W(hjuu){2nf (det A,)-i/2, где Nj - размерность вектора Oj, Aj - матрица с элементами

/1. . = ---

djkdji

,i,Aj=l,yV,/ = 0, m (22.72a)

El Предположении, что существуют указанные производные.

приближение (22.72) допустимо при условии, что априорные плотности распределения мешающих параметров шире апостериорных, которые формируются по обучающим выборкам. При

этом функция W(#jMn) существенно слабее зависит от х, чем остальные множители в правой части (22.72), и поэтому ее, наряду с величиной (2я);/, можно рассматривать как несущественный сомножитель. Тогда адаптивный алгоритм проверки многсальтер-нативных гипотез определяется минимизацией (путем определения соответствующих решающих функций Фк{х) величины

т т

= Е 2 Пл J (X) PjWJxlHj, (det A)-/2dx. (22.73)

Для простой функции потерь

П,/.= 1-бд, (22.74)

где 6;/i -символ кронекера, оптимальный адаптивный алгоритм формулируется следующим образом: принимается гипотеза Hj если для всех i=jj

Pi W [k\IIi, iiu)

Предсгапляет интерес и ряд других адаптивных алгор:, провеоки пгпотс?, рассмотренных в [73].

22.4. А/1,АПТ1ШИЫЕ АЛГОРИТМЫ КЛАССИФИКАЦИИ

z -L.l.T iLliAPMiTTlPIiCKOH АПРИОРНОЙ

22.4J M-To- noi?r:!i-sHL-x фу!!кцп:1. Пусть наблюдение представлено RCHTcpM Реп^ется задача классификации - прииадлелп-юсти этого наблюдения одному из двух классов Si и 82. Если известны плотности ?(xSi) и t£;(xlS2), а также априорные вероягиости pi и прии.адлежности первому и второму классам, то оптгхмальной классифицирующей статистикой служит отношение правдоподобия p2t£ (х j S2)/[pi (х| Si) ], хеХ. В условиях кепараметрпческой априорной неопределенности можно попытаться аппроксимировать статистику /(х), используя неклассифицированную независимую обучающую выборку уь уп из пространства X.

Представим неизвестную статистику отношения правдоподобия в виде разложения по конечному ортонормированному базису

/(x)D(x)=: 2 лФЛх). (22.76)

Если ввести потенциальную функцию

(х,у)-= 2 фЛх)ф,(У), (22.77)

то, как показано в [74], подходящей аппроксимацией функции D{x) является функция Z)n(x, уп), получаем согласно рекуррентному алгоритму

Dn{ X, y)=Z)n-i(x, yn-i)+rn-iK{x, Уп), (22.78)

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

аип = ак,п-1+Гп-1щ(Уп). (22.79)

На первом шаге в качестве нулевого приближения аио, k=l, т, можно выбрать произвольные константы.

Зависимые обучающие выборки рассмотрены в [75]. Рекуррентным адаптивным алгоритмом, основанным на использовании классифицирующих статистик, посвящена монография [76] (см. также [79]).

22.4.2. Метод оценки классифицирующей статистики. Пусть Xi ... ХпЫ ) - последовательность независимых обучающих векторных (Л^-мерных) выборок, принадлежащих tj-uy классу ij=l; 2, /=1, п). Каждый вектор Xj появляется с вероятностью Ри если и с вероятностью р2, если ij = 2. Введем дискрет-

ную случайную величину vf, принимающую два значения:

v;= (22.80)

lo, х;.ь-)=х< .

Ясно, что

P{vj=l}=P2, P{v, = 0}=Pb Pi + P2 = /. (22.81) Обозначив

y.-ViX/o+(l-Vj)x/2), (22.82)

можно объединить обе обучающие последовательности в одну У1=(Уь Уп) и использовать эту последовательность для аппроксимации классифицирующей статистики D{x) [см. (22.76)]. Так как D(x)0, можно воспользоваться методами оценки многомерной плотности вероятности. Примем в качестве аппроксимации D (х) функцию

Dn (X, У?) = - i; (2v,- 1) Ki (X, у^), (22.83)

1=1

тде

Kiix, У/) = П

hi (п)

I hi (n), (22.83а)

ядро К{г) и константы hi{n) удовлетворяют условиям (14.22а-в) и (14.25а,б) [см., например, [80]].