Главная > Математика > Восстановление зависимостей по эмпирическим данным
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 4. Методы построения оптимальной разделяющей гиперплоскости

При создании алгоритмов восстановления зависимостей одним из важных моментов является построение оптимальной разделяющей гиперплоскости.

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

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

неравенств

где

достигается максимум выражения

Для построения оптимальной разделяющей гиперплоскости рассмотрим всевозможные разности

Вектор обладает свойством

поэтому он коллинеарен минимальному по модулю вектору для которого выполняются неравенства

Иными словами, вектор коллинеарен обобщенному портрету класса при пустом втором классе.

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

в положительном квадранте

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

1. Берется произвольная пара Образуется класс состоящий всего из одного вектора Строится обобщенный портрет этого класса (при пустом втором классе).

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

и такой вектор что

Образуется вектор

3. Если окажется, что

— параметр алгоритма), то класс пополняется вектором Находится обобщенный портрет образовавшегося класса и процесс продолжается дальше.

Если же выполнется неравенство

то процесс заканчивается и за оптимальную разделяющую гиперплоскость принимается гиперплоскость

Одновременно с процессом построения гиперплоскости проверяется условие

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

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление