§ 10. Упорядочение по эмпирическим оценкам относительного расстояния и задача минимизации суммарного риска

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

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

,

если функция  неизвестна, но зато дана случайная и независимая выборка пар (обучающая последовательность)

.

Величина  могла быть равна либо нулю, либо единице.

Особенность рассматриваемой здесь постановки состоит в том, что наряду с обучающей последовательностью задается выборка векторов

,

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

.

(Из этой выборки пар отбираются только элементы , элементы  считаются неизвестными). Задача состоит в том, чтобы, используя обучающую последовательность и рабочую выборку, найти в классе характеристических функций  такую функцию, которая минимизировала бы функционал

.

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

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

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

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

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

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

,

где  – размерность пространства.

В нашем случае число классов эквивалентных гиперплоскостей оценивается величиной

,

где  – длина обучающей, а  – рабочей выборок.

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

Итак, путь дана выборка длины

,

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

.

Упорядочим теперь класс линейных решающих правил по следующему принципу. К первому классу  отнесем такие решающие правила, для которых выполняется равенство

,

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

.

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

Справедливы следующие две теоремы.

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

,                     (6.10)

где

,

 – размерность пространства.

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

,                (6.11)

где

.

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

,

где  пробегает значения, удовлетворяющие неравенству

;

здесь  – число ошибок на полной выборке,  – число ошибок на обучающей выборке,  – число ошибок на рабочей выборке,  – отклонение частот ошибок в двух полувыборках.

Как показано в приложении к главе X, при любом  имеет место оценка

.

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

.

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

где  – число ошибок на полной выборке. В свою очередь

и соответственно при

.

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

.

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

,

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

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

Тот факт, что условие  выполняется для всякого , можно записать так:

.

Тогда число  не превосходит максимальное число  , при котором еще выполняется неравенство:

              (6.12)

.

Из соображения симметрии ясно, что

,

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

                      (6.13)

Начиная с , для всех  справедливо

.                  (6.14)

Из (6.12) и (6.14) следует, что  не превосходит величины

.                    (6.15)

Окончательно, учитывая, что разбиение осуществляется гиперплоскостью, имеем

              (6.16)

и соответственно

.

Оценка величины  завершает доказательство обеих теорем.

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

Приравнивая правые части (6.10) и (6.11) к величине  и разрешая соответствующие уравнения относительно , найдем                 

                 (6.17)

для общего случая и

                    (6.18)

для детерминистского случая. В формулах (6.17) и (6.18)  равно минимальному значению двух величин:  и .

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

                (6.19)

при решении задачи в общей постановке и

             (6.20)

в детерминистской постановке.

Существование оценок (6.19) и (6.20) позволяет построить упорядоченную процедуру минимизации риска.

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

В общем случае проводится индексация не только рабочей выборки, но и переиндексация элементов обучающей последовательности. При этом количество переиндексированных векторов задает число ошибочных классификаций материала обучения. Задача состоит в том, чтобы так индексировать рабочую выборку и переиндексировать обучающую последовательность, чтобы минимизировать функционал (6.19).