§ 9.4. Дивергенция

Дивергенция представляет собой меру разделимости классов, аналогичную расстоянию Бхатачария.

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

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

Рис. 9.3. Плотности вероятности отношения правдоподобия.

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

Из того, что говорилось в отношении границы Чернова (см. (9.63) — (9.78)), ясно, что дивергенция не зависит от системы координат и аддитивна относительно независимых переменных, а также удовлетворяет всем свойствам метрики.

Если плотности нормальны, то выражение для дивергенции принимает вид

Если ковариационные матрицы одинаковы, т. е. то

Сравнивая (9.116) с (9.55) и (9.58) видим, что в случае равных ковариационных матриц т. е. в этом случае дивергенция и расстояние Бхатачария совпадают с точностью до постоянного множителя. Кроме того, так как (9.116) совпадает с из (3.34), то дивергенция в случае равных ковариационных матриц однозначно связана с вероятностью ошибки. Это же утверждение справедливо и для границы Чернова и расстояния Бхатачария.

Выражение для верхней границы вероятности ошибки в зависимости от дивергенции неизвестно.

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

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

1. Для первого члена (9.115) оптимальный признак определяется следующим образом:

Этот единственный признак является достаточным.

Рис. 9.4. Границы вероятности правильного распознавания в зависимости дивергенции [Мэрил, 1963].

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

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

Это можно переписать как

Порядок (9.121) совпадает с порядком (9.92) при Следовательно, дивергенция и расстояние Бхатачария приводят к выбору одних и тех же признаков для второго члена.

3. Если требуется найти оптимальные признаки, то, поскольку мы не располагаем аналитической процедурой, приходится использовать численные методы поиска [Toy, 1967]. Однако, если не требовать строгой оптимальности, то для выбора признаков можно использовать следующие процедуры.

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

Таблица 9.3 (см. скан) Выбор признаков для максимизации дивергенции

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

где определено в (9.96). Если таким образом выбраны признаков, то

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

Пример 9.6. В табл. 9.3 приведены результаты вычисления дивергенции и выбора признаков для стандартных данных Признаки отбирались и упорядочивались в соответствии с процедурами а) и б).