Метод минимизации эмпирического риска

Пусть z — (rr, i) — некоторая ситуация, состоящая в том, что объект х относится к классу Ki. Если F (x, а) — некоторое решающее правило, то функция Q (z, a) = (г — F (x, а))² определяет величину потерь при появлении ситуации г, т. е она равна 1, если решающее правило неправильно классифицировало объект х, и 0 — в противном случае.

Как мы уже отмечали, задача распознавания образов в статистическом подходе сводится к минимизации функционала.

определяющего среднюю величину потерь.

Один из путей решения этой задачи связан с идеей замены неизвестного функционала.

функцией.

построенной по случайной и независимой обучающей выборке.

1;

Функция Рэмп получила название функции, исчисляющей величину эмпирического риска. Для каждого фиксированного значения параметра а она определяет среднюю величину потерь на выборке z, zi,…, zi.

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

Возникают вопросы, для каких функций Q (z, a) такая подмена возможна, и какая при этом совершается ошибка?

Мы ответим на эти вопросы для случая, когда множество решающих правил конечно.

Теорема 5. Если из множества, состоящего из N решающих правил, среди которых есть правило, которое не ошибается ни

Рис. 1.10:

для какого объекта х, выбирается такое правило, которое на обучающей последовательности не совершает ни одной ошибки, то с вероятностью 1 — т) можно утверждать, что вероятность ошибочной классификации с помощью выбранного правила составит величину, меньшую е, если длина обучающей последовательности не меньше

Доказательство. Согласно классическим теоремам теории вероятностей частота появления любого события сходится к вероятности этого события при неограниченном увеличении числа испытаний. Однако из этих теорем никак не следует, что решающее правило F (x, a*), которое имеет минимальную частоту ошибок Рэмп («), будет иметь минимальную или близкую к минимальной вероятность ошибки.

Предположим для наглядности, что решающие правила F (x, а) задаются скаляром а, который может принимать значения от 0 до 1. Каждому значению, а ставится в соответствие решающее правило, для которого существует вероятность ошибки Р (а). На рисунке 1.10 функция Р (а) изображена жирной линией. Наряду с этой функцией может быть построена и функция РэмпИ, которая для каждого а определяет частоту ошибочной классификации с помощью правила Р (х, а), вычисленную на обучающей последовательности.

Метод минимизации эмпирического риска предлагает по минимуму функции Рэмп (<*) судить о минимуме функции Р (а). Для того чтобы по точке минимума и минимальному значению функции Рэмп (<*) можно было судить о точке минимума функции Р (а) и ее минимальном значении, достаточно, чтобы кривая Рэмп (а) находилась внутри е-трубки кривой Р (а). Напротив, выброс хотя бы в одной точке (как на рисунке 1.10) может привести к тому, что в качестве точки минимума Р (а) будет выбрана точка выброса. В этом случае минимум Рэмп (<*) никак не характеризует минимум функции Р (а).

Это означает, что нас интересуют не классические условия, когда для любых а и е имеет место.

при I —? оо, а более сильные условия равномерного приближения, когда для любого е справедливо.

при I —? оо.

Итак, пусть класс решающих правил состоит из конечного числа N элементов (Р (х, а,-): j = 1,2,…, N}.

Обозначим i/j = Р_Эмп (<*Д АЧ = P (.

По условию теоремы среди функций.

есть та, которая идеально решает задачу. Следовательно, на любой выборке х,…, х/ значение минимума эмпирического риска будет равно нулю.

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

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

Так как число функций, на которых достигается нуль величины эмпирического риска, не превосходит N — числа всех элементов в классе, то справедливо неравенство.

где Pj — вероятность того, что решающее правило, для которого вероятность совершить ошибку есть величина большая ?, правильно классифицирует все объекты обучающей последовательности. Эту вероятность легко оценить:

Подставляя оценку Pj в (1.3), получим.

Для того чтобы вероятность P{supj vj — pj • > ?} не превосходила т/, достаточно выполнения условия.

Разрешая относительно / это неравенство, получим.

Теорема доказана. ?

Упражнения.

• 1.23. Образы Si и «5>2 заданы нормальными распределениями N (0,1) и N (1,1). Вычислить вероятность ошибки распознавания по правилу Байеса при условии, что априорное распределение вероятностей появления образов Si и таково: а) {½, 1/2};
• б) {1/3,2/3}.
• 1.24. Образы Si, S2 и S3 заданы равномерными распределениями на отрезках [0; 1 /2), [1/3; 2/3] и [0; 2] соответственно. Вычислить вероятность ошибки распознавания по правилу Байеса, если априорное распределение вероятностей появления образов Si, S2 и S3 таково: {½; ¼; ¼}.
• 1.25. Доказать, что если задано два нормальных распределения с одинаковыми ковариационными матрицами, отличающимися только векторами средних, то байесовской границей будет гиперплоскость.
• 1.26. Доказать, что если два нормальных распределения имеют одинаковые ковариационные матрицы и эти матрицы диагональны, то алгоритм максимального правдоподобия (метод Байеса) эквивалентен методу эталонов.
• 1.27. Величина из класса Si имеет нормальное распределение JVi, а из S2 — N2. Вероятность события Si равна Pi, a Si — АЦена ошибки первого рода (т.е. событие Si распознать как S2) равна Ci, а цена ошибки второго рода — С2. Определить решающее правило и выразить математическое ожидание цены ошибки через ERF (x) =

/₀*ехр (—t²)dt при условии что.