4.6.4. ГРАНИЦЫ ОШИБКИ

Хотя уравнение (33) дает точный результат, еще показательнее получить границы для Р, выраженные посредством байесовского уровня Р*. Очевидной нижней границей для Р является сам уровень Р*. Кроме того, можно показать, что при любом Р* существует множество условных и априорных вероятностей, для которых эта граница достигается. Так что в этом смысле это точная нижняя граница.

Еще интереснее задача определения точной верхней границы. Следующее соображение позволяет надеяться на низкую верхнюю границу: если байесовский уровень небольшой, то Р(о)г|х) близка к единице для некоторого і, скажем і=т. Таким образом, подынтегральное выражение в (33) будет приближенно 1—Р^ (w„|x)« «2 (1—Р(м„|х)), и поскольку

то интегрирование по х может дать уровень, в два раза превышающий байесовский, но являющийся все еще низким. Чтобы получить точную верхнюю границу, мы должны определить, насколько большим может стать уровень Р ошибки правила ближайшего соседа для заданного байесовского уровня Р*. Таким образом, выражение (33) вынуждает нас задаться вопросом, насколько малой может стать

С

^Р^(согІх) для заданной P(co„[x). Записав

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

г.

Несколько поразмыслив, мы видим, что ^ Р*(сог|х) минимизируется, если все апостериорные вероятности, кроме т-й, равны, и второе ограничение дает

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

И

Сразу же видим, что Р<2Р*, поэтому мбжем подставить этот результат в (33) и просто опустить второй член выражения. Однако более Точную границу можно получить на основании

так что

причем равенство сохраняется тогда и только тогда. Когда дисперсия Р* (б|х) равна Нулю. Пользуясь этим результатом и подставлйя соотношение (36) в (33), получаем желаемые границы

Легко показать, что такая верхняя граница достигается в случае так называемой нулевой информации, в котором плотности распределения р(х|о)і) тождественны, так что P(cOi|x)=P(wj) и Р* (е|х) не зависит от х. Таким образом, границы, заданные (28), являются максимально близкими в том смысле, что для любой Р* существуют условные и априорные вероятности, длй которых эти границы Достигаются. На рис. 4.4 графически представлены эти границы. Байесовский уровень Р* может находиться в любом месте между О и (с—1)/с. Границы сходятся В этих двух крайних точках. Когда байесовский уровень мал, верхняя граница превышает его почти в два раза. В общем значение ошибки правила ближайшего соседа должно находиться в заштрихованной области.

Поскольку Р всегда меньше или равна 2Р*, то, если имеется бесконечный набор данных и используется сложное решающее пра-

вило, можно по крайней мере в два раза сократить уровень ошибки.

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

Естественно задаться вопросом, насколько хорошо правило ближайшего соседа в случае конечного числа выборок и как быстро результат сходится к асимптотическому значению. К сожалению, ответы для общего случая неблагоприятны. Можно показать, что сходимость может быть бесконечно медленной и уровень ошибки (е) даже не должен монотонно убывать с ростом и. Так же, как это происходит с другими непараметрическими методами, трудно получить какие-либо еще результаты, кроме асимптотических, не делая дальнейших допущений о вероятностных свойствах.