9. Методы обучения распознаванию образов
9.1. Постановка задачи
Допустим, что даны два конечных множества векторов:
,
Эти два множества разделены между собой ориентированной гиперплоскостью, если существует вектор такой, что выполняются неравенства:
(9.1)
где k < 1.
Очевидно, что если существует вектор , удовлетворяющий условию (9.1), то существует и множество векторов , также удовлетворяющих (9.1). Будем искать среди них минимальный по модулю. Этот минимальный вектор называют обобщенным портретом.
Среди множества сущест вует вектор 0, определяющий
x2
x
x1
Рис 9.1. Положение гиперплос-
кости для двухмерного случая
такое
направление, при котором проекции
множеств х
и
наиболее удалены друг от друга, то есть
уравнение для 0
запишется как
0
].
(9.2)
Этот вектор 0 называют оптимальным, а полученную с его помощью гиперплоскость называют оптимальной разделяющей гиперплоскостью:
х
,
(9.3)
где
В
уравнении для вычисления
деление на 2 осуществляется потому, что
плоскость должна пройти на равном
расстоянии между крайними точками х
и
.
9.2. Построение обобщенного портрета
Нашей
целью является отыскание 0
и С0.
Для поиска С0
рассмотрим конечное множество векторов
Z,
состоящее из всех возможных разностей,
образованных векторами
х
и
.
Дано уравнение
,
всего ab элементов.
Будем искать минимальный по модулю вектор 0, удовлетворяющий неравенству
.
(9.4)
Оказывается,
что вектор 0
совпадает по направлению с оптимальным
вектором 0,
кроме того,
– расстояние между множествами х
и
в направлении, задаваемом нормалью к
разделяющей гиперплоскости. Таким
образом, чтобы отыскать 0,
необходимо минимизировать функционал
при выполнении ограничений (9.4). Отыскание минимума I есть задача квадратичного программирования, решение которой опирается на теорему Куна ‑ Таккера, указывающую необходимое и достаточное условие минимума. Из этой теоремы следует [5], что минимальный по модулю вектор 0, удовлетворяющий неравенству (9.4), представим в виде
,
(9.5)
причём
.
(9.6)
Среди всех векторов , удовлетворяющих неравенству (9.4), вектор 0, представимый в виде (9.5), является минимальным по модулю.
В работе [5] показано, что решение двойственной задачи эквивалентно построению обобщенного портрета.
,
(9.7)
где
.
(9.8)
Если
есть точка минимума функции (9.7) в
положительном квадранте
,
то уравнение (9.8) определяет обобщенный
портрет.