7.8. КОНЦЕПЦИЯ ДИВЕРГЕНЦИИ

Дивергенция) представляет собой меру «расстояния» или несходства между двумя классами. Его можно использовать для ранжировки признаков и оценки эффективности разделения классов. В данном параграфе мы вводим понятие дивергенции и обсуждаем возможности его использования для определения эффективности выбора и упорядочения признаков.

Пусть вероятность появления образа при условии его принадлежности классу есть и вероятность появления образа при условии его принадлежности классу есть Тогда различающую информацию для по отношению к можно измерить логарифмом отношения правдоподобия:

Средняя различающая информация для класса определяется выражением

Информацию, отличающую класс от класса можно измерить логарифмом отношения правдоподобия

Средняя различающая информация для класса определяется выражением

Полную среднюю информацию для различения классов и часто называют дивергенцией и задают как

Допустим, что заданы два класса, характеризуемые двумя n-мерными нормально распределенными совокупностями

где — векторы математического ожидания и — ковариационные матрицы размера Плотности распределения совокупностей определяются выражениями

и

а логарифм отношения правдоподобия

Средняя различающая информация для этих двух классов равна

Следовательно, дивергенция для этих двух классов есть

Особый интерес представляют два частных случая.

Случай 1. Равенство ковариационных матриц: . Из (7.8.9) заключаем, что

где . Отметим, что произведение представляет собой обобщенное расстояние Махаланобиса.

Для одномерной нормально распределенной совокупности,

и

где — математические ожидания и — дисперсия.

Случай 2. Равенство математических ожиданий совокупностей: .

Средняя различающая информация и дивергенция определяются выражениями

соответственно.

Дивергенция обладает следующими полезными свойствами:

4) при независимых измерениях дивергенция аддитивна:

5) добавление результата нового измерения никогда не приводит к уменьшению дивергенции:

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

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

В гл. 4 было показано, что при выборе функции потерь, принимающей значения 0 или 1, принадлежность образа классу критерию минимальной вероятности классификационной ошибки определяется условием

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

Для нормально распределенных совокупностей с равными ковариационными матрицами уравнение (7.8.8) дает следующую разделяющую границу:

Решающее правило таково: если .

Вероятность ошибки выражается как

В гл. 4 было показано также, что

где

обозначает расстояние Махаланобиса между плотностями распределения Сопоставив формулы (7.8.12) и (7.8.20), для равных ковариационных матриц получаем

т. е. дивергенцию классов . Итак, дивергенция является подходящей мерой расстояния для пар нормальных распределений и может служить оценкой сложности разделения двух классов. Если ковариационная матрица С — единичная, то дивергенция характеризует квадратичное расстояние между математическими ожиданиями Из (7.8.19) следует, что вероятность ошибки есть монотонно убывающая функция расстояния Махаланобиса и что функция, связывающая с вероятностью ошибки есть одномерная плотность нормального распределения с нулевым математическим ожиданием и единичной дисперсией.

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

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

ожидания и новой ковариационной матрицей в таком случае будут

и

Обратная матрица для есть

где

Новой оценкой эффективности системы признаков является

что после проведения упрощений сводится к

Следовательно, прирост эффективности определяется как

Если дополнительно введенный признак не зависит от остальных признаков то , следовательно,

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

, удовлетворяющего требованиям к вероятности ошибки. Матрица преобразования А имеет вид

где ортогональные собственные векторы, соответствующие наименьшим характеристическим числам . Ковариационной матрицы С. Было показано, что

Таким образом,

где — компоненты преобразованных векторов математических ожиданий соответственно. Из (7.8.30) следует, что

Так как

то

Итак, искомое рекуррентное соотношение имеет вид

причем

где — собственный вектор, соответствующий наименьшему характеристическому числу ковариационной матрицы С. Используя в качестве отправной точки оценку эффективности наиболее значимого признака, оценки эффективности дополнительных признаков, удовлетворяющих требованиям к вероятности ошибки, можно получить, используя рекуррентное соотношение (7.8.33). При определении оценок эффективности мы воспользовались кривой, приведенной на рис. 4.4; она представляет связь вероятности ошибки с расстоянием.