§ 12. Алгоритмы упорядоченной минимизации суммарного риска

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

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

Разницу в решениях детерминистской задачи минимизации суммарного риска методом минимизации эмпирического риска и методом упорядоченной минимизации иллюстрирует следующий пример (рис. 15).

Рис. 15.

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

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

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

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

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

1) элемент рабочей выборки присоединяется к первому классу и определяется расстояние  между выпуклыми оболочками разделяемых множеств;

2) элемент рабочей выборки присоединяется ко второму классу и определяется расстояние  между выпуклыми оболочками разделяемых множеств;

3) элемент рабочей выборки относится к первому классу, если , и ко второму классу, если .

(Методы определения расстояния между выпуклыми оболочками рассмотрены в главе XIV.)

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

Рис. 16.

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

И еще одно замечание. При практической реализации метода упорядоченной минимизации риска вместо (6.19') лучше использовать критерий, полученный на основе оценок равномерного относительного уклонения (5.23):

.             (6.21)

При  этот критерий близок к (6.20'), а при  значительно тоньше, чем (6.19').