§ 9.3. Граница Чернова и расстояние Бхатачария

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

9.3.1. Граница Чернова и расстояние Бхатачария.

Как уже говорилось в гл. 3, вероятность ошибки ограничена границей Чернова. Вспоминая (3.100), имеем

Это неравенство выполняется для всех лежащих между 0 и 1. Однако, как мы видели из (3.101), оптимальное значение

которое дает наименьшую границу, удовлетворяет уравнению

где

Таким образом, выражение (9.52) или из (9.54) могут служить критериями разделимости классов. Как правило, вычисление представляет собой трудную задачу. Но в том случае, когда обе плотности вероятности нормальны, как это имеет место в (3.104), принимает вид

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

где

Величину называют расстоянием Бхатачария и испольвуют в качестве критерия разделимости классов. В частности, для нормальных распределений расстояние Бхатачария имеет вид

Через расстояние Бхатачария можно выразить также и нижнюю границу вероятности ошибки, что можно показать

следующим образом [Кайлат, 1967]. Вероятность ошибки можно представить как

Рис. 9.1 дает иллюстрацию для одномерного случая. Суммирование площадей и С дает а суммирование площадей и С дает . С другой стороны, интеграл (9.59) равен сумме площадей А и В, Поэтому должно равняться а последнее равно .

Рис. 9.1. Вычисление вероятности ошибки е.

Интеграл (9.59) известен как вариационное расстояние Колмогорова. Используя неравенство Шварца, можно показать, что расстояние Колмогорова ограничено величиной

Комбинируя (9.59) и (9.60), получаем для нижней границы вероятности ошибки выражение

где — верхняя граница вероятности ошибки из (9.56). Когда мало, нижнюю границу вероятности ошибки можно приближенно представить в виде

Например, когда принимает зиачения 0,3, 0,1, 0,05, нижняя граница принимает соответственно значения 0,09, 0,01, 0,0025.

Пример 9.3. Вычислим нижнюю границу вероятности ошибки для дапных из примера 3.4. Так как нижняя граница (9.61) равна 0,0023, Точное значение вероятности ошибки ближе (в смысле отношения) к верхней границе, чем к нижней.

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

1. Свойство инвариантности относительно взаимно однозначных отображений. Согласно (2,75), при взаимно однозначном отображении

плотности вероятностей и соответствующие области связаны соотношениями

где — якобиан этого отображения. Следовательно,

Таким образом, инвариантно относительно любого взаимно однозначного отображения.

2. Аддитивность по отношению к независимым признакам. Если все случайные величины взаимно независимы, то

Поэтому можно представить в виде суммы функций от отдельных переменных

3. Метрические в а. Выражение удовлетво-» ряетусловиям (9.3) — (9.6). Это можно показать следующим

образом:

Неравенство (9.69) можно видоизменить:

Это следует из того, что

б) Если

в) Если поменять местами,

отлично от из (9.54). Однако оптимальное значение удовлетворяющее уравнению

связано с оптимальным значением и (9.54) уравнением

Поэтому для оптимальных имеем

Для расстояния Бхатачария при выражение (9.73) равно (9.54), т. е.

г) Добавляя новую переменную имеем

Неравенство в (9.78) совпадает с неравенством в (9.69). Таким образом, добавление новой переменной всегда увеличивает