Метод опорных векторов
[40-42]. С помощью метода опорных векторов можно построить классификатор минимизирующий верхнюю оценку ожидаемой ошибки классификации (в том числе и для неизвестных объектов, не входивших в тренировочный набор). Применение метода опорных векторов к задаче обнаружения лица заключается в поиске гиперплоскости в признаковом пространстве, отделяющий класс изображений лиц от изображений нелиц.Рассмотрим задачу классификации с обучением, для числа классов равного двум. Классифицируются векторы пространства R". Задачу можно сформулировать как поиск функции /(х) принимающей значения < 0 для векторов одного класса и > 0 для другого. В качестве исходных данных для определения классифицирующей функции f(x), дан тренировочный набор векторов пространства, для которых известна их принадлежность к одному из классов. Семейство классифицирующих функций можно описать как f(x,a), где а - обобщенный параметр, задающий конкретную функцию семейства. Наилучшей функцией классификации является функция, для которой ожидаемый риск (ожидаемый уровень ошибки классификации) минимален. Оценить ожидаемый риск напрямую невозможно, можно попытаться сделать это с помощью эмпирического риска (уровня ошибки классификации на тренировочном наборе), минимизация которого не всегда, особенно для относительно небольших наборов тренировочных данных, приводит к минимизации ожидаемого риска.
Основополагающее понятие - размерность Вапника-Червоненкиса (VC dimension) семейства функций f(x,a). Эта величина дает некоторую оценку «сложности» функций семейства. Для семейства функций классификации с из- вестной (или ограниченной сверху) размерностью VC можно найти верхнюю оценку ожидаемого риска [42,43]. Оценка риска является суммой двух слагаемых: эмпирического риска и меры риска использования семейства функций с размерностью VC
Задача таким образом сводится к выбору такой функции классификации, которая удовлетворительно разделяет обучающий набор и при этом не отягощена чрезмерной сложностью (большой размерностью VC). Принцип минимизации структурного риска как раз и заключается в поиске семейства функций классификации (и конкретной функции в семействе), которое минимизирует верхнюю оценку ожидаемого риска.Размерность VC для класса функций бинарной классификации равна максимальному количеству точек / в пространстве R", которые могут быть разбиты на два класса всеми 21 способами. Для случая линейной функции разделения fix,а) (гиперплоскости) в пространстве R" VC размерность равна п +1. Это значит, что, например на плоскости, любые три линейно независимые (не лежащие на одной прямой) точки можно разделить всеми восемью способами (никакие четыре точки - нельзя). В ряде случаев, для заданного набора тренировочных векторов можно получить верхнюю оценку VC размерности гиперплоскостей, значительно меньшую п +1. Это особенно важно при работе с пространствами чрезвычайно высокой размерности.
Построение классифицирующей функции с помощью опорных векторов заключается в поиске линейной функции, правильно разделяющей тренировочный набор на два класса при минимально возможной для данного набора оценке VC размерности сверху. Таким образом, для линейно разделяемых данных мы получаем функцию классификации, минимизирующую верхнюю оценку ожидаемого риска.
К сожалению возможности линейного классификатора ограничены. Можно привести массу примеров классов, линейно неразделимых в пространстве R". Возможности линейного классификатора можно значительно расширить путем нелинейного отображения исходного пространства в пространство потенциально на-много более высокой размерности Ф:Яп ->F и применения линейного классификатора в пространстве F. Сложность заключается в том, что чем выше размерность пространства, тем сложнее с ним работать. Ценным свойством классификации с помощью гиперплоскостей является то, что классифицирующую функцию f(x) можно преобразовать таким образом, что она будет представлять собой линейную комбинацию скалярных произведений тестового вектора х с векторами трениро-вочного набора.
А линейный классификатор, использующий только скалярные произведения может неявно оперировать в пространстве F, используя аппарат ядерных функций [44,45], не работая с векторами пространства F и даже не зная отображения Ф. Таким образом можно использовать линейный классификатор (например, опорные вектора) для корректной работа с нелинейно разделяемыми классами без существенного усложнения вычислительных операций.Как и любой другой метод, метод опорных векторов имеет свои сильные и слабые стороны. Недостаток метода состоит в том, что для классификации используется не все множество образцов, а лишь их небольшая часть, которая находится на границах. Достоинство метода состоит в том, что для классификации методом опорных векторов, в отличие от большинства других методов, достаточно небольшого набора данных. При правильной работе модели, построенной на тестовом множестве, вполне возможно применение данного метода на реальных данных.