Уважаемые посетители Портала Знаний, если Вы найдете ошибку в тексте, выделите, пожалуйста, ее мышью и нажмите Сtrl+Enter. Мы обязательно исправим текст!


Метод опорных векторов – Supported Vector Machine (SVM)

Введение

Линейный метод опорных векторов, постановка задачи

Вторая форма

Объективные и необъективные гиперплоскости

Случай линейной неразделимости

Нелинейный классификатор

Регрессия

Заключение

Введение

Классификация данных - общая задача машинного обучения (machine learning), в этом направлении интенсивно применяются методы оптимизации и аналитической геометрии. Для понимания аналитической геометрии можно использовать книгу Моденова.

Пусть некоторые объекты принадлежат к одному из двух классов.

Задача состоит в том, чтобы определить, к какому классу будут принадлежать новые наблюдения.

В случает метода опорных векторов (Supported Vector Machine) точка в пространстве рассматривается как вектор размерности p.

Мы хотим узнать, сможем ли мы разделить данные точки гиперплоскостью размерности (p-1). Такую плоскость назовем плоскостью классификатора.

Конечно, данные могут быть разделены с помощью различных гиперплоскостей. Лучшая гиперплоскость - гиперплоскость, при построении которой разделение и разница между 2 классами максимально.

Рассмотрим в качестве примера данные на плоскости, гиперплоскость в данном случае – просто прямая (см. рисунок ниже).

Проведем любую прямую, она разделит точки на 2 множества.

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

Вопрос: как провести нужную нам прямую?

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

Рисунок 1 H1,H2,H3 – гиперплоскости. H3 – гиперплоскость максимальной разности

Данный подход обобщается на многомерный случай.

Линейный метод опорных векторов, постановка задачи

Даны наблюдения для обучения D, набор состоящий из n объектов, имеющих р параметров:

D=

где y принимает значения -1 или 1, определяя, какому классу принадлежит каждая точка .

Каждая точка – это вектор размерности p.

Требуется найти гиперплоскость максимальной разности, которая разделяет наблюдения от объектов .

Используя знания аналитической геометрии, любую гиперплоскость можно записать как множество точек x, удовлетворяющих условию:

w*x-b=0,

где * - скалярное произведение нормали к гиперплоскости на вектор x.

Параметр определяет смещение гиперплоскости относительно начала координат вдоль нормали w.

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

Области, ограниченной 2 гиперплоскостями называется "разностью (маржей)".

Эти гиперплоскости могут быть описаны уравнениями:

w*x-b=1

w*x-b=-1

Используя геометрическую интерпретацию, находим расстояние между этими гиперплоскостями - .

Для того чтобы дистанция была максимальной, минимизируем .

Чтобы исключить все точки из полосы, мы должны убедиться для всех наблюдений справедливо:

Эквивалентно

Далее аналитическим решаем задачу оптимизации:

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

Однако задачу можно упростить, заменив на (коэффициент от 1/2 используются для математического удобства) без изменения решение (не менее оригинальные и модифицированные уравнения имеют одинаковый w и b) .

Это квадратичная задача оптимизации.

Более точно, нужно найти минимум:

При ограничениях:

Путем введения множителей Лагранжа, задача с ограничениями может быть выражена как задача без ограничений:

Мы ищем седловую точку.

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

Задача может быть решена с помощью квадратичного программирования.

«Стационарность» по Куна-Такеру означает, что решение может быть выражено как линейная комбинация обучающих векторов:

Только несколько множителей будет больше 0.

Соответствующий – опорный вектор, который лежит на краю и выражен как .

Из этого следует, что опорные вектора также удовлетворяют:

Последнее позволяет определить смещение b.

На практике применяют усреднение по всем опорным векторам:

Вторая форма

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

Наблюдения для обучения лежат на краю.

Используя факт и подставляя , можно показать, что вторая форма метода опорных векторов позволяет решить проблему оптимизации:

Максимизировав по :

Ограничение от минимизации для b

Ядро определено как k()=

W может быть вычислено благодаря условиям:

Объективные и необъективные гиперплоскости

Иногда требуется, чтобы гиперплоскость проходит через начало координат.

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

Объективная гиперплоскость может быть обеспечено путем установки b=0 в прямой задачи оптимизации.

Соответствующая вторая форма совпадает с формой, приведенной выше, без ограничения равенства:

Случай линейной неразделимости

В 1995 был предложен модифицированный метод Soft margin для максимизации разности, который позволяет допускать ошибки на обучающей выборке.

Если не существует гиперплоскости, которая способна разделить обучающую выборку строго на 2 класса, то метод Soft margin выберет гиперплоскость, которая разделит обучающую выборку настолько чисто (с минимальной ошибкой), насколько это возможно, в то же время, максимизируя расстояние до ближайшей точки на обучающей выборке.

Метод вводит переменную , которая измеряет оценку ошибки классификации .

Целевая функция возрастает за счет функции штрафа, которая возрастает, если .

Оптимизация теперь требует нахождения компромисса между большой разницей и штрафом за ошибку.

Если штрафная функция является линейной, то задача оптимизации становится:

Минимизация может быть решена классическим методом Лагранжа (см. пример выше).

Вторая форма аналогична примеру выше.

Ключевым преимуществом линейной штрафной функции является то, что переменные исчезают в двойственной задаче, с постоянной С, появляющейся только как дополнительное ограничение на множители Лагранжа.

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

Нелинейный классификатор

Рисунок 2 Метод с использование функции ядра

Оригинальный алгоритм для нахождения оптимальной плоскости предложил Vapnik в 1953 году – линейный классификатор.

Однако, в 1992, Bernhard E. Boser, Isabelle M. Guyon и Vladimir N. Vapnik предложили способ создания нелинейного классификатора с использованием произвольной функции ядра (kernel trick) (предложенный Айзерманом) для нахождения плоскостей максимальной разности.

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

Изменение может быть нелинейно и трансформироваться в пространство с высокой размерностью.

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

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

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

Некоторые ядра представлены ниже:

  • Однородный полином:
  • Неоднородный полином:
  • Гауссовскую функцию радиального базиса:

  • Гиперболический тангенс

Ядро связанно с преобразованием уравнения:

k()=

Оценка w в трансформированном пространстве:

Свойства

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

Специальное свойство проявляется в том, что они симулируют минимальную эмпирическую ошибку классификации и максимизируют геометрическую разницу (маржу).

Параметр выбора

Эффективность метода опорных векторов зависит от выбора ядра, параметров ядра и чистоты параметра С для геометрической разницы.

Общий выбор – Гауссовское ядро, которое имеет один параметр .

Лучшую комбинацию С и γ обычно выбирают используя поиск по сетке с экспоненциальным ростом частоты и . К примеру,

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

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

Замечания

Потенциальные недостатки метода опорных векторов включает три аспекта:

  • Невозможность калибровки вероятности попадания в определенный класс
  • Метод опорных векторов подходит только для решения задач с 2 классами
  • Параметры модели сложно интерпретировать

Дополнение

Метод опорных векторов в случае существование нескольких классов

Данный метод предназначен для классификации объектов в случае нескольких (больше двух) классов.

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

Построение бинарных классификаторов, которые различают:

  • один класс от остальных (один-против-всех)
  • один класс от другого (один-против-одного)

Классификация новых объектов, используя подход один-против-всех, осуществляется путем стратегии - победитель получает все. Классификатор, с самым высоким значение функции выхода, присваивает новый объект к определенному классу (важно, что выход функции может быть прокалиброван для получения сопоставимых оценок).

Для подхода один-против-одного, классификация производится с использование стратегии - максимум-голосов победит, в которой каждый классификатор присваивает объект к одному из двух классов.

Класс с большинством голосов определяет, какой класс определить объект.

  1. Ориентированный ациклический граф
  2. Коды, корректирующие ошибки выхода

Регрессия

Версия метода опорных векторов для регрессии была предложена в 1996 году Vladimir N. Vapnik, Harris Drucker, Christopher J. C. Burges, Linda Kaufman и Alexander J. Smola.

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

Другая версия SVM хорошо известна как метод наименьшего квадратного опорного вектора (LS-SVM) был предложен Suykens и Vandewalle.

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

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

Благодаря такому процессу, данный метод случайным является бинарным линейным классификатором.

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

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

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

В дополнение к выполнению линейной классификации, метод опорных векторов может эффективно выполнять нелинейную классификацию, используя kernel trick произвольная функция ядра), неявное отображая входные данные в многомерные пространства функций.

Заключение

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

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

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

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

Чтобы сохранить вычислительную нагрузку разумной, отображения, используемые в алгоритмах метода опорных векторов, обеспечивают простоту вычисления точек в терминах переменных в исходном пространстве, в терминах функции ядра K(x,y).

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

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

При таком выборе гиперплоскости, точки x в пространстве функций отображаются в гиперплоскость и определяются соотношением: .

Заметим, что если K(x,y) становиться малой при отдалении y от x, то каждый элемент в сумме измеряет степень близости от контрольной точки x до соответствующей точки .

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

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

В результате требуется более сложная дискриминация между наборами, которые не являются выпуклыми в целом в исходном пространстве.


В начало

Содержание портала