§ 6. Алгоритм построения экстремальной линейной разделяющей поверхности

Алгоритм ОП-6 реализует идею упорядоченной минимизации риска при построении гиперплоскости, разделяющей два множества векторов  и  (см. главу VI). С помощью этого алгоритма строится гиперплоскость, разделяющая два множества векторов в подпространстве  исходного пространства , в котором достигается минимум величины

,                    (15.9)

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

Найти минимум (15.9), не используя полный перебор по подпространствам, невозможно, поэтому в алгоритме используется тот же прием локального поиска минимума, который использовался выше.

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

,

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

Таким образом, для установления одного оптимального «объединения» проводится  построений оптимальных разделяющих гиперплоскостей (построение оптимального обобщенного портрета необходимо для построения критерия ).

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

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