Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 18
Текст из файла (страница 18)
В данном параграфе мы рассмотрим методы создания линейного классификатора для этих более сложных случаев. Так как заранее оговорено, что независимо от вида распределений используется линейный классификатор, то решающее правило должно иметь вид Выражение Ь(Х) есть линейная функция относительно вектора Х. Ее называют линейной разделяющей функиией. Задача синтеза классификатора заключается в том, чтобы для заданных распределений определить коэффициенты Г'= [г1...и„~ и значение порога ге, оптимальные по различным критериям. Если заданные распределения являются нормальными с равными ковариационными матрицами, то линейная разделяющая функция совпадает с логарифмом отношения правдоподобия.
4.21. Линейная разделятощая функция, минимизирующая вероятность ошибки. Если случайная величина Ь(Х) распределена по нормальному или близкому к нему закону, то для вычисления вероятности ошибки можно использовать математическое ожидание и дисперсию Ь(Х) для классов со1 и со2, а затем выбрать параметры Г и ио так, чтобы минимизировать ошибку решения. Вспоминая, что Ь (Х) является суммой, состоящей из п слагаемых х;, приходим к выводу: 1) если векторы Х имеют нормальное распределение, то величина Ь(Х) также имеет нормальное распределение: 2) даже если векторы Х распределены не по нормальному закону, но при большом и выполнены условия центральной Ю5 $42 МИН1И1ИЗАЦИЯ ВЕРОЯТНОСТИ ОШИБКИ 1О4 ГЛ.
4. ЛИНЕЙНЫЕ КЛАССИФИКАТОРЫ +00 1 ! ~2 р(о),) (, ехр ~ — — ', ~ Н5+ — ч1/о~ — Ча/Оз ; р ((о ), ехр ~ — —,) а'ь. 2 (2 )1/2 1~ 2 ) (4.16) я ми мизировать риск г, то вместо вероятностей Р( ) фор,ле (4.16) должны быть использованы ве- Р(',,) и сг,Р((ог). Прп такой замене предполагается, что штрафы с11 — — сгг = О. дифференцируя выражение (4.16) по параметрам 1' и (/о и приравнивая производные нулю, получим 2 (2и)1/2 2о2 дГ 1 2 ~( + Р((о2), ехр ' (2д)1/2 2ог д) ~ ог / 2 2 (2гг)1/го ) 2о21 )~ О1 2 де 1 Ч' д ( Ч11 Р ((о1) ., ехр — —., д —,, — — "' + ди2 (2и) /- 2 $ Чг д ! Ч21 + Р ((о2) ехр 2 (2 ~)1/2 2ог дио ~ 2 Чг 2 предельной теоремы, то распределение величины Ь(Х) может быть близко к нормальному.
Математические ожидания и дисперсии величины Ь(Х) в классах (о1 и (ог равны ~)1 =. Е (Ь (Х)/(о,) = Ъ"Е (Х/(о1) + (/о =- ~"М1+ (/о (4.14) о; = Уат (Ь (Х)/о),) = У'Е 1(Х вЂ” ЛХ;) (Х вЂ” Мг)') 1' =- У'Х,.У. (4.15) Поэтому вероятность ошибки можно записать следующим образом: где д Ч1 (дЧ./д(/) о,. — Ч.
(до /д(/) М. Ч. Анализ уравнений (4.18) показывает, что величины Р(а1) р(Ь/(о1) и Р((ог) р(Ь/(ог) должны быть одинаковыми при Ь=О,т. е. 2 Ч ( ~)"' 1 2О2~ (2гг) /2 о 2 Это показано на рис. 4.7. Кроме условпя (4.20), должно выполняться соотношепие (4.17), т. е. ЛХ, — ЛХ, = М11,/О'2) Х, — (Ч,/О'-,) Х,] Г Таким образом, если возможно отыскать значения параметров $' Рис. 4.7. Распределение решающего правила /г(Х). гг) Р (о>1 ) Р (/г/Ог1); б) Р (аг) Р (/г/о>я), (4.22) где 1/а = (Ч,/ог) — (Ч~/о-1), (4.23) — Ч1/О1 г Ч2/Ог — Ч1/О 1 0(~ 8(1. (4.24) и гго, удовлетворяющие уравнениям (4.20) и (4.21), то эти значения минимизируют вероятность ошибки (4.16) [Андерсон, Бахадур, 1962].
К сожалению, поскольку параметры и, и огг явля-- ются функциями величин 1' и го, точное решение уравнений (4.20), (4.21) получить не удалось. Поэтому для нахождения решения следует использовать итеративную процедуру. простой итеративный процесс был предложен В работе [Петерсон, Матсон, 19661. Вместо решения уравнений (4.20) и (4.21) минимум вероятности ошибки е ищется при условии (4.21) следующим образом: У = а [81~ + (1 — г) ~21 1(Мг — ЛХ,), 1О8 107 ~уо У ~тХг —, (1 — о) о~У Мт~ У (4.25) о го + (1 — г) о. 2 2 (4. 26) 1~Ф~ УР 7У г 2 2 до1 д1 до2 д1 дт), д1 дт), дУ до2 дУ + дт) дУ + д1) дУ г 2 до1 д1 доз д1 дт), д/ дт)г 2 дно доз д~о дт), дто дЧг д~о д1 д/ (4.27) дУ д,2 1 д1 д1 (4.28) дт'о доз 1 ГЛ.
4. ЛИНЕЙНЫЕ КЛАССИФИКАТОРЫ Так как из формулы . '(4.24) следует, что т); = У'М;+ 1'о готт),-~-(1 — г) о21)1= О, то ио можно вычпслпть по формуле Из (4.25) видно, что если вектор т' умножить на а, то значение ио также увеличится в а раз. Напомним, что решенпе, получаемое пз условия У'Х+ гз ~~ О, эквивалентно решению а'т"Х+ ага ~~ О. Кроме того, вероятность ошибки (4.16) инвариантна относительно изменения масштаба, так как т), аУ'ЛХ. + ато У 17.
+ то о [((ту)т ~ (оу)]1!2 (ут~ у),'2' Поэтому, пренебрегая масштабным коэффициентам а в формуле (4.22), можно вычертить график вероятности ошибки е как функции одного параметра г следуютцим образом: 1) для данного г при а = 1 вычислить т' по формуле (4.22); 2) используя полученное значение т", вычислпть по уравнениям (4.15) и (4.25) величиныо1~, о2, т"М„т"'ЛХг и го; 3) вычислить вероятность ошибки е по формуле (4.16); 4) изменять значения г от О до 1.
Значение г, минимизирующее вероятность ошибки е, можно определить из графика функции е(г). Преимущество этой процедуры заключается в том, что для настройки имеется только один параметр г. Это делает процедуру намного проще, чем решение уравнений (4.20) и (4.21) относительно и+ 1 переменной. Кроме того, чтобы сэкономить вычислительное время, предлагается вначале процедуры одновременно привести к диагональному виду ковариационные матрицы Х~ и Х2 и далее работать в преобразованной системе координат.
В этом случае вычисление дисперсий о,2 и обращение матрицы в (4.22) выполняются очень просто. Пример 4.2. Используются данные примера 3.3. График вероятности ошибки В в зависимости от параметра г приведен на рис. 4.8, из которого видно, что вероятность ошибки В не очень чувствительна к г вблизи оптимальной точки. Наилучшая линейная разделяющая функция дает минимальную ошибку в 5%, в то время как байесовскпй классификатор с квадратичной функцией дает 1,9%, как следует из примера 3.3.
4.2.2. Обобщенная формула для различных критериев. Мы рассмотрели только критерий минимизации вероятности ошибки г 4.2. МННН21ПЗЛЦ11Я ВЕРОЯТНОСТИ ОШИБКИ решения. Изложенный подход можно обобщить следующим образом [Петерсон, Матсон, 1966]. Пусть 1(т)~, т)2, о1~, о~2) — любой критерий, который для определения оптимальных коэффициентов линейной разделяющей функции необходимо минимизировать г Рис. 4.8. Изменение вероятности ошибки е в зависимости от параметра о. или максимизировать. Тогда справедливы следующие соотноше- ния: Из выражений (4.14) и (4.15) следует, что дат~/дУ = 2Х;1', (4.29) дт)1/дУ = М;, '(4.30) да,/дг = О, (4.31) дт),/дно = 1.
'(4.32) Подставляя '(4.29) — (4.32) в уравнения (4.27) и (4.28), получим 2 ~(д//до1~) Хт+ (д//до2) ХД Ъ' = (ЛХ1 — ЛХг) д//дарго (4.33) д//дт)1+ д//дЧ, = О. (4.34) $ 4 3. МИННМИЗЛПИЯ СРЕДНЕКВЛДРЛТИЧНОЙ ОШИБКИ 1ОЗ 108 Гл. 4. линейные кллссификлтОРы Значения У и оо определяются как решение этой системы уравнений. П р и м е р 4.3. Рассмотрим критерий Фишера у (Ч~ — Ч2)' (4.35) 2 ~ 2 О1-Г.
Ог Этот критерий представляет собой меру того, насколько далеко друг от друга отстоят распределения значений линейной разделяющей функции в классах о~ и ог. Поэтому для достижения наилучшей разделимости классов следует определить значения ]' и ио, которые максимизируют этот критерий. В соответствии с системой уравнений (4.33) и (4.34) имеем г ](~, — ~,)/(а~ -(- а~~]] ( — Х, + — Ха) 1' = ЛХд — Ия (4.30) Как было замечено ранее, можно пренебречь масштабным фактором при К Поэтому У можно определить следующим образом: (4.37) Сравнивая выражения (4.37) и (4.22), можно заметить, что для критерия Фишера оптимальное значение 8 равно 0,5.
Поэтому подставляя 8 = 0,5 и У, определенное по формуле (4.37), в выражение (4.25), можно вычислить значение ио. ~ — 1 (ЛХ, — ЛХ1) — г'1+ — г', (о1М, + огЛХ1) ио— , 2+, 2 1 2 5 4.3. Линейная разделяющая функция, минимизирующая среднеквадратичную ошибку решения В предыдущем параграфе для определения оптимальной разделяющей функции, минимизирующей вероятность ошибки, предполагалось, что в классах о~ и ог плотности вероятности значений линейной разделяющей функции являются нормальными или близкими к нормальным.
Даже при выводе обобщенной формулы для различных критериев предполагалось, что критерии представляют собой функции математических ожиданий и дисперсий значений разделяющей функции. Если же применить метод, основанный на минимизации среднеквадратичной ошибки решения, то аналогичные результаты можно получить и'без предположения о нормальности распределений. Вместо предположения о виде распределения вектора Х будем предполагать, что имеется конечная выборка значений случайных величин Х, состоящая из У объектов. 4.3.1. Линейные разделяющие функции.
Линейную разделяющую функцию можно представить в следующем виде, отличном от (4.13): Ь(Х) = РХ вЂ” ио > 0 при Х~ о~, '(4.39) Ь(Х) = — У'Х вЂ” ио ) 0 при Х ~ ог. (4.40) Далее, если ввести новую форму записи выборочных векторов Я = ~+1х~х~... х.~' при Х о~, (4.41) Е = ~ — 1 — х~ — х~...
— х.~' прп Х е1~, (4.42) то разделяющая функция примет более простой вид и Ь (~) = И"г = ~ и1,2, ) О,. 1=0 (4.43) где га принимает значения +1 или — 1. Таким образом, предлагаемая процедура построения разделяющей функции заключается в следующем: 1) получить пз Х новое множество векторов Е; 2) определить вектор И" из условия, чтобы для всех известных векторов Е удовлетворялось неравенство (4.43). Предположим, что ((Я) — наилучшая разделяющая функция для двух классов.
Тогда значения ((Е) можно рассматривать как требуемый выход разделяющей функции Ь(Л). Как правило, нам неизвестен точный вид ((Е), но известна классификация объектов ооучающей выборки. Поэтому можно постулировать обучающие значения ( (Е), которые, как следует из (4.43), должны быть положительными числами для каждого Я. Тогда среднеквадратичная ошибка между .требуемым и действительным вылодом разделяющей функции будет равна г ц((И;.у , (у))г) '(4.44) ГДЕ +1 +1 ... +1 — 1 ...
— 1 Х, Х, ... Х~ ! — Х1~+1 ... — Х (4.46) )и '(4.47) Если вместо математического ожидания используется выборочное среднее значение, определенное по У объектам, то имеем (4.53) зде У1 = АХ, + В ( — вектор), Р[ = АМ[+ В и Х[ = АХ[А'. (4.54) или И7 — (1/~/т) — [1/Г +1 ... +1[ — 1 У, ... У№! — У№+1 (4.55) +1.:' Х', И" =(1/Л) Д ~'(г,') г,', 1=1 (4.56) + 1 Х +1 ... +1! Етт= и[1 или 1 Хт №+1 1 Х№ХУ+[Х~ и[~ = (1/Х) (4.57) ~ ~'(г',) к, —,'К ~'(г,') ~, 3=№+1 ~и[1 ... и[ ~' = (1/Х) Хт (4.58) 1: ЛХ~))1 у) (4 5О 1 и где м, = (1 /л'),'~ х, (4.59) я = (1/л ) ~ х,.х,' (4.60) (4.
61) (4.52) Рл. 4. линейные кллссиФиклтОРы Из '(4.46)' видно, что матрица У состоит из У выборочных векторов, среди которых Ж[ объектов принадле[кат классу [О[, а Жр объектов — классу [О~. Матрицу [/ называют матрицей выборочных данных. Вектор Г называют вектором требуемых значений выхода. Для минимизации среднеквадратичной ошибки (4.45) при.
заданном требуемом выходе продифференцируем е' по И' и результат приравняем нулю: де2/дИ' = (2/Ж) ['./(['./'И' — Г) = О, Это уравнение хорошо известно из линейной теории среднеквадратичного оценивания как нормальное уравнение. Таким образом, вектор И" можно определить по формуле (4.49), котора» минимизирует среднеквадратичную ошибку между требуемым [г действительным выходом разделяющей функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
