В машинном обучении , опорно-векторные машинах ( SVMs , также поддержка-вектор сеть [1] ) является контролируемыми обучения модели с сопутствующим обучением алгоритмов , которые анализируют данные для классификации и регрессионного анализа . Разработано в AT & T Bell Laboratories по Вапнику с коллегами (Boser и др., 1992, Гийон и др., 1993, Вапник и др., 1997), SVMs является одним из самых методов надежного прогнозирования, основываясь на статистических основах обучения или Теория ВКпредложен Вапником (1982, 1995) и Червоненкисом (1974). Учитывая набор обучающих примеров, каждый из которых помечен как принадлежащий к одной из двух категорий, обучающий алгоритм SVM строит модель, которая присваивает новые примеры той или иной категории, что делает ее не вероятностным двоичным линейным классификатором (хотя такие методы, как Platt существует масштабирование для использования SVM в настройке вероятностной классификации). SVM сопоставляет обучающие примеры с точками в пространстве, чтобы максимально увеличить разрыв между двумя категориями. Затем новые примеры отображаются в том же пространстве и предсказываются как принадлежащие к категории, в зависимости от того, на какую сторону пропасти они попадают.
Помимо выполнения линейной классификации , SVM могут эффективно выполнять нелинейную классификацию, используя так называемый трюк с ядром , неявно отображая свои входные данные в пространственные объекты большой размерности.
Когда данные не помечены, обучение с учителем невозможно, и требуется подход к обучению без учителя, который пытается найти естественную кластеризацию данных по группам, а затем сопоставить новые данные с этими сформированными группами. Опорные векторы кластеризация [2] алгоритм, созданный Хавом Сиегелманна и Вапник , применяет статистику опорных векторов, разработанных в опорных векторах алгоритма, чтобы классифицировать немаркированные данные, и является одним из наиболее широко используемых алгоритмов кластеризации в промышленном Приложения. [ необходима цитата ]
Мотивация
Классификация данных - обычная задача машинного обучения . Предположим, что некоторые заданные точки данных принадлежат к одному из двух классов, и цель состоит в том, чтобы решить, в каком классе будет находиться новая точка данных . В случае машин с вектором поддержки точка данных рассматривается как-мерный вектор (список числа), и мы хотим знать, можем ли мы разделить такие точки с помощью -мерная гиперплоскость . Это называется линейным классификатором . Есть много гиперплоскостей, которые могут классифицировать данные. Один разумный выбор в качестве лучшей гиперплоскости - это та, которая представляет наибольшее разделение или разницу между двумя классами. Поэтому мы выбираем гиперплоскость так, чтобы расстояние от нее до ближайшей точки данных с каждой стороны было максимальным. Если такая гиперплоскость существует, она называется гиперплоскостью с максимальным запасом, а линейный классификатор, который она определяет, известен как классификатор с максимальным запасом ; или, что то же самое, перцептрон оптимальной устойчивости . [ необходима цитата ]
Определение
Более формально, поддержка вектор машина строит гиперплоскость или множество гиперплоскостей в высоком или бесконечномерным пространстве, которое может быть использовано для классификации , регрессии , или других задач , таких как обнаружение отклоняющихся значений. [3] Наглядно, хорошее разделение достигается за счет гиперплоскости , которая имеет наибольшее расстояние до ближайшей точки учебно-данных любого класса (так называемый функциональный рентабельность), так как в общем случае , чем больше запас, тем ниже ошибки обобщения из классификатор. [4]
В то время как исходная проблема может быть сформулирована в конечномерном пространстве, часто бывает, что множества для различения не являются линейно отделимыми в этом пространстве. По этой причине было предложено [5] , чтобы исходное конечномерное пространство отображалось в гораздо более многомерное пространство, что, по-видимому, облегчало разделение в этом пространстве. Чтобы сохранить разумную вычислительную нагрузку, отображения, используемые схемами SVM, предназначены для обеспечения того, чтобы точечные произведения пар векторов входных данных можно было легко вычислить в терминах переменных в исходном пространстве, определяя их в терминах функции ядра. выбран в соответствии с проблемой. [6] Гиперплоскости в многомерном пространстве определяются как набор точек, скалярное произведение которых с вектором в этом пространстве является постоянным, где такой набор векторов является ортогональным (и, следовательно, минимальным) набором векторов, который определяет гиперплоскость. Векторы, определяющие гиперплоскости, могут быть выбраны как линейные комбинации с параметрамиизображений векторов признаков которые встречаются в базе данных. При таком выборе гиперплоскости точкив пространстве признаков , которые отображаются в гиперплоскость, определяются соотношением Обратите внимание, что если становится маленьким как растет дальше от , каждый член в сумме измеряет степень близости контрольной точки к соответствующей точке базы данных . Таким образом, указанная выше сумма ядер может использоваться для измерения относительной близости каждой контрольной точки к точкам данных, происходящим в том или ином из наборов, подлежащих различению. Обратите внимание на то, что набор точек отображение на любую гиперплоскость может быть довольно запутанным в результате, позволяя гораздо более сложное различение между множествами, которые вообще не являются выпуклыми в исходном пространстве.
Приложения
SVM можно использовать для решения различных реальных задач:
- SVM полезны при категоризации текста и гипертекста , поскольку их применение может значительно снизить потребность в помеченных обучающих экземплярах как в стандартных индуктивных, так и в преобразовательных настройках. [7] Некоторые методы поверхностного семантического анализа основаны на машинах опорных векторов. [8]
- Классификация изображений также может выполняться с помощью SVM. Экспериментальные результаты показывают, что SVM достигают значительно более высокой точности поиска, чем традиционные схемы уточнения запросов, всего после трех-четырех раундов обратной связи по релевантности. Это также верно для систем сегментации изображений , включая те, которые используют модифицированную версию SVM, которая использует привилегированный подход, предложенный Vapnik. [9] [10]
- Классификация спутниковых данных, таких как данные SAR, с использованием управляемой SVM. [11]
- Рукописные символы можно распознать с помощью SVM. [12] [13]
- Алгоритм SVM широко применяется в биологических и других науках. Они использовались для классификации белков до 90% правильно классифицированных соединений. Перестановочные тесты, основанные на весах SVM, были предложены в качестве механизма для интерпретации моделей SVM. [14] [15] Машинные веса опорных векторов также использовались для интерпретации моделей SVM в прошлом. [16] Постфактумная интерпретация моделей машин опорных векторов с целью выявления особенностей, используемых моделью для прогнозирования, является относительно новой областью исследований, имеющей особое значение в биологических науках.
История
Оригинальный алгоритм SVM был изобретен Владимиром Н. Вапником и Алексеем Я. Червоненкис в 1963 году. В 1992 году Бернхард Бозер, Изабель Гийон и Владимир Вапник предложили способ создания нелинейных классификаторов, применяя трюк с ядром к гиперплоскостям с максимальным запасом. [5] Действующий стандарт [ согласно кому? ] воплощение (мягкий край) было предложено Коринной Кортес и Вапник в 1993 году и опубликовано в 1995 году. [1]
Линейный SVM
Нам дан обучающий набор данных точки формы
где равны 1 или -1, каждый из которых указывает класс, к которому точка принадлежит. Каждый это -мерный действительный вектор. Мы хотим найти «гиперплоскость с максимальным запасом», которая разделяет группу точек. для которого из группы точек, для которых , который определяется таким образом, чтобы расстояние между гиперплоскостью и ближайшей точкой из любой группы максимизируется.
Любую гиперплоскость можно записать как набор точек удовлетворение
где - (не обязательно нормализованный) вектор нормали к гиперплоскости. Это очень похоже на нормальную форму Гессе , за исключением того, чтоне обязательно является единичным вектором. Параметр определяет смещение гиперплоскости от начала координат вдоль вектора нормали .
Жесткая маржа
Если данные обучения линейно разделимы , мы можем выбрать две параллельные гиперплоскости, которые разделяют два класса данных, чтобы расстояние между ними было как можно большим. Область, ограниченная этими двумя гиперплоскостями, называется «полем», а гиперплоскость с максимальным запасом - это гиперплоскость, которая находится на полпути между ними. С нормализованным или стандартизованным набором данных эти гиперплоскости можно описать уравнениями
- (все, что находится на этой границе или выше, относится к одному классу с меткой 1)
а также
- (все, что находится на этой границе или ниже, относится к другому классу с меткой −1).
Геометрически расстояние между этими двумя гиперплоскостями равно , [17] поэтому для максимального увеличения расстояния между плоскостями мы хотим минимизировать. Расстояние вычисляется с использованием расстояния от точки до плоскости . Мы также должны предотвратить попадание точек данных в поля, мы добавляем следующее ограничение: для каждого либо
- , если ,
или же
- , если .
Эти ограничения гласят, что каждая точка данных должна лежать на правильной стороне поля.
Это можно переписать как
Мы можем собрать это вместе, чтобы получить задачу оптимизации:
- "Минимизировать при условии для . "
В а также которые решают эту проблему, определяют наш классификатор, где - знаковая функция .
Важным следствием этого геометрического описания является то, что гиперплоскость максимального поля полностью определяется теми ближайшая к нему ложь. Этиназываются опорными векторами .
Мягкая маржа
Чтобы расширить SVM до случаев, когда данные не разделимы линейно, полезна функция потерь шарнира.
Обратите внимание, что это i -я цель (т.е. в данном случае 1 или -1), иэто i-й выход.
Эта функция равна нулю, если выполняется ограничение в (1), другими словами, если лежит на правильной стороне поля. Для данных на изнаночной стороне поля значение функции пропорционально расстоянию от поля.
Таким образом, цель оптимизации - минимизировать
где параметр определяет компромисс между увеличением размера маржи и обеспечением того, чтобы лежать на правильной стороне поля. Таким образом, при достаточно малых значениях, второй член в функции потерь станет незначительным, следовательно, он будет вести себя аналогично SVM с жесткими границами, если входные данные линейно классифицируются, но все равно будет узнавать, жизнеспособно ли правило классификации или нет.
Нелинейная классификация
Первоначальный алгоритм гиперплоскости с максимальным запасом, предложенный Вапником в 1963 году, построил линейный классификатор . Однако в 1992 году Бернхард Бозер , Изабель Гийон и Владимир Вапник предложили способ создания нелинейных классификаторов, применяя трюк с ядром (первоначально предложенный Айзерманом и др. [18] ) к гиперплоскостям с максимальным запасом. [5] Результирующий алгоритм формально аналогичен, за исключением того, что каждое скалярное произведение заменяется нелинейной функцией ядра . Это позволяет алгоритму уместить гиперплоскость с максимальным запасом в преобразованное пространство признаков . Преобразование может быть нелинейным, а преобразованное пространство - многомерным; Хотя классификатор является гиперплоскостью в преобразованном пространстве признаков, он может быть нелинейным в исходном пространстве ввода.
Примечательно, что работа в многомерном пространстве признаков увеличивает ошибку обобщения машин опорных векторов, хотя при достаточном количестве выборок алгоритм по-прежнему работает хорошо. [19]
Некоторые распространенные ядра включают:
- Полиномиальный (однородный) :.
- Полиномиальный (неоднородный):.
- Радиальная базисная функция Гаусса : для . Иногда параметризуется с использованием.
- Гиперболический тангенс : для некоторых (не для всех) а также .
Ядро связано с преобразованием по уравнению . Значение w также находится в преобразованном пространстве, причем. Точечные произведения с w для классификации снова можно вычислить с помощью трюка с ядром, т. Е..
Вычисление классификатора SVM
Вычисление (soft-margin) классификатора SVM сводится к минимизации выражения вида
Мы фокусируемся на классификаторе мягкой маржи, поскольку, как отмечалось выше, выбирая достаточно малое значение для дает классификатор с жесткими границами для линейно классифицируемых входных данных. Классический подход, который сводит (2) к задаче квадратичного программирования , подробно описан ниже. Затем будут обсуждены более современные подходы, такие как субградиентный спуск и координатный спуск.
Первобытный
Минимизацию (2) можно переписать как задачу оптимизации с ограничениями с дифференцируемой целевой функцией следующим образом.
Для каждого мы вводим переменную . Обратите внимание, что наименьшее неотрицательное число, удовлетворяющее
Таким образом, мы можем переписать задачу оптимизации следующим образом
Это называется основной проблемой.
Двойной
Решая лагранжева двойственную задачу, описанную выше, мы получаем упрощенную задачу
Это называется двойной проблемой. Поскольку задача двойственной максимизации является квадратичной функциейпри наличии линейных ограничений он эффективно решается с помощью алгоритмов квадратичного программирования .
Здесь переменные определены так, что
- .
Более того, именно когда лежит на правильной стороне поля, а когда лежит на границе поля. Следует, что можно записать как линейную комбинацию опорных векторов.
Смещение, , можно восстановить, найдя на границе маржи и решение
(Обратите внимание, что поскольку .)
Уловка ядра
Предположим теперь, что мы хотели бы изучить правило нелинейной классификации, которое соответствует правилу линейной классификации для преобразованных точек данных. Кроме того, нам дана функция ядра что удовлетворяет .
Мы знаем вектор классификации в преобразованном пространстве удовлетворяет
где получаются путем решения оптимизационной задачи
Коэффициенты можно решить с помощью квадратичного программирования, как и раньше. Опять же, мы можем найти какой-нибудь индекс такой, что , чтобы лежит на границе поля в преобразованном пространстве, а затем решить
Ну наконец то,
Современные методы
Последние алгоритмы поиска классификатора SVM включают субградиентный спуск и координатный спуск. Оба метода доказали, что предлагают значительные преимущества по сравнению с традиционным подходом при работе с большими, разреженными наборами данных - методы субградиента особенно эффективны, когда существует много обучающих примеров, и координированный спуск, когда размерность пространства признаков высока.
Субградиентный спуск
Алгоритмы субградиентного спуска для SVM работают напрямую с выражением
Обратите внимание, что является выпуклой функцией от а также . В качестве такого, традиционного градиентного спуска (или SGD ) методы могут быть адаптированы, где вместо того , чтобы сделать шаг в направлении градиента функции, в шаг берется в направлении вектора , выбранного из функции в суб-градиента . Этот подход имеет то преимущество, что для определенных реализаций количество итераций не масштабируется с, количество точек данных. [20]
Координатный спуск
Алгоритмы координатного спуска для SVM работают от двойственной задачи
Для каждого , итеративно коэффициент регулируется в сторону . Тогда полученный вектор коэффициентовпроецируется на ближайший вектор коэффициентов, удовлетворяющий заданным ограничениям. (Обычно используются евклидовы расстояния.) Затем процесс повторяется до тех пор, пока не будет получен почти оптимальный вектор коэффициентов. Получающийся в результате алгоритм чрезвычайно быстр на практике, хотя было доказано мало гарантий производительности. [21]
Минимизация эмпирического риска
Описанная выше машина вектора поддержки с мягким запасом является примером алгоритма минимизации эмпирического риска (ERM) для потери шарнира . С этой точки зрения машины опорных векторов принадлежат к естественному классу алгоритмов статистического вывода, и многие из их уникальных особенностей обусловлены поведением потерь на шарнире. Эта точка зрения может обеспечить более глубокое понимание того, как и почему работают SVM, и позволит нам лучше анализировать их статистические свойства.
Минимизация рисков
При обучении с учителем каждому дается набор обучающих примеров. с этикетками , и хочет предсказать дано . Для этого создается гипотеза ,, так что является "хорошим" приближением . «Хорошее» приближение обычно определяется с помощью функции потерь , , что характеризует, насколько плохо как предсказание . Затем мы хотели бы выбрать гипотезу, которая минимизирует ожидаемый риск :
В большинстве случаев мы не знаем совместного распределения прямо. В этих случаях общая стратегия состоит в выборе гипотезы, которая минимизирует эмпирический риск:
При определенных предположениях о последовательности случайных величин (например, что они генерируются конечным марковским процессом), если набор рассматриваемых гипотез достаточно мал, минимизатор эмпирического риска будет точно аппроксимировать минимизатор ожидаемого риска как становится большим. Такой подход называется минимизацией эмпирического риска или ERM.
Регуляризация и стабильность
Чтобы задача минимизации имела четко определенное решение, мы должны наложить ограничения на множество рассматриваемых гипотез. Еслиявляется нормированным пространством (как и в случае с SVM), особенно эффективный метод - рассматривать только эти гипотезы для которого . Это эквивалентно наложению штрафа за регуляризацию. , и решение новой задачи оптимизации
Такой подход называется тихоновской регуляризацией .
В более общем смысле, может быть некоторой мерой сложности гипотезы , так что предпочтение отдается более простым гипотезам.
SVM и потеря петель
Напомним, что классификатор SVM (soft-margin) выбрано, чтобы минимизировать следующее выражение:
В свете вышеизложенного мы видим, что метод SVM эквивалентен минимизации эмпирического риска с регуляризацией Тихонова, где в этом случае функция потерь - это потеря на шарнире.
С этой точки зрения SVM тесно связан с другими фундаментальными алгоритмами классификации, такими как регуляризованные методы наименьших квадратов и логистическая регрессия . Разница между ними заключается в выборе функции потерь: регуляризованный метод наименьших квадратов сводится к минимизации эмпирического риска с квадратом потерь ,; логистическая регрессия использует логарифмическую потерю ,
Целевые функции
Разницу между потерями на шарнире и этими другими функциями потерь лучше всего выразить в терминах целевых функций - функции, которая минимизирует ожидаемый риск для данной пары случайных величин..
В частности, пусть обозначать при условии, что . В настройке классификации мы имеем:
Таким образом, оптимальный классификатор:
Для квадратичных потерь целевой функцией является функция условного ожидания, ; Для логистических потерь это функция логита,. Хотя обе эти целевые функции дают правильный классификатор, так как, они дают нам больше информации, чем нам нужно. Фактически, они дают нам достаточно информации, чтобы полностью описать распределение.
С другой стороны, можно проверить, что целевая функция потери шарнира точно равна . Таким образом, в достаточно обширном пространстве гипотез - или, что то же самое, для правильно выбранного ядра - SVM-классификатор будет сходиться к простейшей функции (в терминах), который правильно классифицирует данные. Это расширяет геометрическую интерпретацию SVM - для линейной классификации эмпирический риск минимизируется любой функцией, границы которой лежат между опорными векторами, и простейшим из них является классификатор максимальной маржи. [22]
Характеристики
SVM принадлежат к семейству обобщенных линейных классификаторов и могут быть интерпретированы как расширение перцептрона . Их также можно рассматривать как частный случай регуляризации Тихонова . Особым свойством является то, что они одновременно минимизируют ошибку эмпирической классификации и максимизируют геометрическую границу ; следовательно, они также известны как классификаторы максимальной маржи .
Сравнение SVM с другими классификаторами было проведено Мейером, Лейшем и Хорником. [23]
Выбор параметра
Эффективность SVM зависит от выбора ядра, параметров ядра и параметра soft margin C. Обычно выбирается гауссово ядро, которое имеет единственный параметр . Лучшее сочетание C ичасто выбирается поиском по сетке с экспоненциально растущими последовательностями C и, Например, ; . Как правило, каждая комбинация выбора параметров проверяется с помощью перекрестной проверки , и выбираются параметры с наилучшей точностью перекрестной проверки. В качестве альтернативы можно использовать недавнюю работу по байесовской оптимизации для выбора C и, часто требуя оценки гораздо меньшего количества комбинаций параметров, чем поиск по сетке. Окончательная модель, которая используется для тестирования и классификации новых данных, затем обучается на всем обучающем наборе с использованием выбранных параметров. [24]
вопросы
К потенциальным недостаткам SVM можно отнести следующие аспекты:
- Требуется полная маркировка входных данных
- Некалиброванный статус класса вероятность -SVM проистекает из теории Вапника, которая позволяет избежать оценивающих вероятностей на конечных данных
- SVM напрямую применима только для двухклассовых задач. Следовательно, должны применяться алгоритмы, которые сводят многоклассовую задачу к нескольким двоичным задачам; см. раздел о мультиклассах SVM .
- Параметры решаемой модели трудно интерпретировать.
Расширения
Кластеризация опорных векторов (SVC)
SVC - аналогичный метод, который также основан на функциях ядра, но подходит для обучения без учителя. Это считается фундаментальным методом в науке о данных . [ необходима цитата ]
Мультиклассовый SVM
Мультиклассовая SVM нацелена на присвоение меток экземплярам с помощью машин опорных векторов, где метки отрисовываются из конечного набора нескольких элементов.
Преобладающий подход для этого - свести единственную проблему мультикласса к множеству задач двоичной классификации . [25] Общие методы такого сокращения включают: [25] [26]
- Создание бинарных классификаторов, которые различают одну из меток и остальных ( один против всех ) или между каждой парой классов ( один против одного ). Классификация новых экземпляров для случая «один против всех» выполняется по стратегии «победитель получает все», в которой классификатор с функцией наивысшего результата присваивает класс (важно, чтобы выходные функции были откалиброваны для получения сопоставимых баллов). ). Для подхода один против одного классификация выполняется с помощью стратегии голосования с максимальным количеством побед, при которой каждый классификатор назначает экземпляр одному из двух классов, затем голос за назначенный класс увеличивается на один голос и, наконец, класс с наибольшим количеством голосов определяет классификацию экземпляра.
- Направленный ациклический граф SVM (DAGSVM) [27]
- Коды вывода с исправлением ошибок [28]
Краммер и Зингер предложили метод мультиклассовой SVM, который сводит проблему мультиклассовой классификации к одной задаче оптимизации, а не разбивает ее на несколько задач двоичной классификации. [29] См. Также Ли, Лин и Вахба [30] [31] и Ван ден Бург и Гроенен. [32]
Трансдуктивные машины опорных векторов
Машины трансдуктивных опорных векторов расширяют SVM тем, что они также могут обрабатывать частично маркированные данные при полууправляемом обучении , следуя принципам трансдукции . Здесь помимо обучающего набора, обучающемуся также дается набор
тестовых примеров, подлежащих классификации. Формально трансдуктивная машина опорных векторов определяется следующей задачей прямой оптимизации: [33]
Свернуть (в )
при условии (для любого и любой )
а также
Трансдуктивные машины опорных векторов были введены Владимиром Н. Вапником в 1998 году.
Структурированная SVM
SVM были обобщены на структурированные SVM , где пространство меток структурировано и, возможно, имеет бесконечный размер.
Регресс
Версия SVM для регрессии была предложена в 1996 году Владимиром Н. Вапником , Харрисом Друкером, Кристофером Дж. Берджесом, Линдой Кауфман и Александром Дж. Смолой. [34] Этот метод называется регрессией опорных векторов (SVR). Модель, созданная с помощью классификации опорных векторов (как описано выше), зависит только от подмножества обучающих данных, потому что функция затрат для построения модели не заботится о точках обучения, которые лежат за пределами поля. Аналогично, модель, созданная SVR, зависит только от подмножества обучающих данных, потому что функция стоимости для построения модели игнорирует любые обучающие данные, близкие к предсказанию модели. Другая версия SVM, известная как машина опорных векторов наименьших квадратов (LS-SVM), была предложена Суйкенсом и Вандеваллом. [35]
Обучение оригинальной SVR означает решение [36]
- минимизировать
- при условии
где обучающая выборка с целевым значением . Внутренний продукт плюс перехват прогноз для этой выборки, и - свободный параметр, который служит порогом: все прогнозы должны быть в пределах диапазон верных прогнозов. Переменные Slack обычно добавляются в приведенное выше, чтобы учесть ошибки и позволить приближение в случае, если указанная выше проблема невозможна.
Байесовский SVM
В 2011 году Полсон и Скотт показали, что SVM допускает байесовскую интерпретацию с помощью техники увеличения данных . [37] В этом подходе SVM рассматривается как графическая модель (где параметры связаны через распределения вероятностей). Это расширенное представление позволяет применять байесовские методы к SVM, такие как гибкое моделирование функций, автоматическая настройка гиперпараметров и количественная оценка прогнозируемой неопределенности . Недавно Флориан Венцель разработал масштабируемую версию байесовской SVM , которая позволяет применять байесовские SVM к большим данным . [38] Флориан Венцель разработал две разные версии: схему вариационного вывода (VI) для байесовской векторной машины поддержки ядра (SVM) и стохастическую версию (SVI) для линейной байесовской SVM. [39]
Выполнение
Параметры гиперплоскости с максимальным запасом получаются путем решения оптимизации. Существует несколько специализированных алгоритмов для быстрого решения проблемы квадратичного программирования (QP), возникающей из SVM, в основном полагающихся на эвристику для разбиения проблемы на более мелкие и более управляемые части.
Другой подход заключается в использовании метода внутренней точки, который использует ньютоновские итерации для нахождения решения условий Каруша – Куна – Таккера прямой и двойственной задач. [40] Вместо решения последовательности отдельных проблем, этот подход непосредственно решает проблему в целом. Чтобы избежать решения линейной системы, включающей большую матрицу ядра, в трюке с ядром часто используется приближение матрицы низкого ранга.
Другой распространенный метод - это алгоритм последовательной минимальной оптимизации (SMO) Платта , который разбивает проблему на двумерные подзадачи, которые решаются аналитически, устраняя необходимость в алгоритме численной оптимизации и хранении матриц. Этот алгоритм концептуально прост, его легко реализовать, как правило, он быстрее и имеет лучшие свойства масштабирования для сложных задач SVM. [41]
Частный случай линейных машин опорных векторов может быть решен более эффективно с помощью тех же алгоритмов, которые используются для оптимизации его близкого родственника, логистической регрессии ; этот класс алгоритмов включает субградиентный спуск (например, PEGASOS [42] ) и координатный спуск (например, LIBLINEAR [43] ). LIBLINEAR имеет несколько привлекательных свойств времени обучения. Каждая итерация сходимости занимает линейное время по времени, затраченному на чтение данных поезда, и итерации также обладают свойством Q-линейной сходимости , что делает алгоритм чрезвычайно быстрым.
Общие SVM ядра также могут быть решены более эффективно с использованием субградиентного спуска (например, P-packSVM [44] ), особенно когда разрешено распараллеливание .
SVM ядра доступны во многих наборах инструментов машинного обучения, включая LIBSVM , MATLAB , SAS , SVMlight, kernlab , scikit-learn , Shogun , Weka , Shark , JKernelMachines , OpenCV и другие.
Для повышения точности классификации настоятельно рекомендуется предварительная обработка данных (стандартизация). [45] Существует несколько методов стандартизации, таких как min-max, нормализация по десятичной шкале, Z-оценка. [46] Вычитание среднего и деление на дисперсию каждого признака обычно используется для SVM. [47]
Смотрите также
- Адаптивная таблица на месте
- Машины ядра
- Ядро Фишера
- Масштабирование Платта
- Полиномиальное ядро
- Прогнозная аналитика
- Перспективы регуляризации машин опорных векторов
- Векторная машина релевантности , вероятностная модель с разреженным ядром, идентичная по функциональной форме SVM
- Последовательная минимальная оптимизация
- Картографирование космоса
- Winnow (алгоритм)
Рекомендации
- ^ а б Кортес, Коринна ; Вапник, Владимир Н. (1995). «Опорно-векторные сети» (PDF) . Машинное обучение . 20 (3): 273–297. CiteSeerX 10.1.1.15.9362 . DOI : 10.1007 / BF00994018 . S2CID 206787478 .
- ^ Бен-Гур, Аса; Хорн, Дэвид; Зигельманн, Хава; Вапник, Владимир Николаевич " " Опорный вектор кластеризации "(2001);". Журнал исследований в области машинного обучения . 2 : 125–137.
- ^ «1.4. Поддержка векторных машин - документация scikit-learn 0.20.2» . Архивировано 8 ноября 2017 года . Проверено 8 ноября 2017 .
- ^ Хасти, Тревор ; Тибширани, Роберт ; Фридман, Джером (2008). Элементы статистического обучения: интеллектуальный анализ данных, вывод и прогнозирование (PDF) (второе изд.). Нью-Йорк: Спрингер. п. 134.
- ^ а б в Boser, Bernhard E .; Guyon, Isabelle M .; Вапник, Владимир Н. (1992). «Алгоритм обучения оптимальных классификаторов маржи» . Материалы пятого ежегодного семинара по теории вычислительного обучения - COLT '92 . п. 144. CiteSeerX 10.1.1.21.3818 . DOI : 10.1145 / 130385.130401 . ISBN 978-0897914970. S2CID 207165665 .
- ^ Press, William H .; Teukolsky, Saul A .; Веттерлинг, Уильям Т .; Фланнери, Брайан П. (2007). «Раздел 16.5. Машины опорных векторов» . Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8. Архивировано 11 августа 2011 года.
- ^ Иоахимс, Торстен (1998). «Категоризация текста с помощью машин опорных векторов: обучение с множеством важных функций» . Машинное обучение: ECML-98 . Конспект лекций по информатике. Springer. 1398 : 137–142. DOI : 10.1007 / BFb0026683 . ISBN 978-3-540-64417-0.
- ^ Прадхан, Самир С. и др. « Неглубокий семантический анализ с использованием машин опорных векторов ». Труды конференции по технологиям человеческого языка Североамериканского отделения Ассоциации компьютерной лингвистики: HLT-NAACL 2004. 2004.
- ^ Вапника Владимир Н .: Приглашенный спикер. Обработка информации и управление ИПМУ 2014).
- ↑ Barghout, Лорен. « Гранулы пространственной информации о таксоне, используемые в итеративном нечетком принятии решений для сегментации изображений ». Детализированные вычисления и принятие решений. Springer International Publishing, 2015. 285–318.
- ^ А. Мэйти (2016). «Контролируемая классификация поляриметрических данных RADARSAT-2 для различных особенностей суши». arXiv : 1608.00501 [ cs.CV ].
- ^ ДеКост, Деннис (2002). "Обучающие машины с инвариантными опорными векторами" (PDF) . Машинное обучение . 46 : 161–190. DOI : 10,1023 / A: 1012454411458 . S2CID 85843 .
- ^ Maitra, DS; Bhattacharya, U .; Паруи, СК (август 2015 г.). «Общий подход на основе CNN к распознаванию рукописных символов в нескольких сценариях» . 2015 13-я Международная конференция по анализу и распознаванию документов (ICDAR) : 1021–1025. DOI : 10.1109 / ICDAR.2015.7333916 . ISBN 978-1-4799-1805-8. S2CID 25739012 .
- ^ Гаонкар, Билвадж; Давацикос, Христос; «Аналитическая оценка карт статистической значимости для многовариантного анализа и классификации изображений на основе опорных векторов» .
- ^ Cuingnet, Реми; Россо, Шарлотта; Чупин, Мари; Лехериси, Стефан; Дормонт, Дидье; Бенали, Хабиб; Самсон, Ив; и Коллио, Оливье; «Пространственная регуляризация SVM для обнаружения диффузных изменений, связанных с исходом инсульта» , Medical Image Analysis , 2011, 15 (5): 729–737.
- ^ Статников, Александр; Хардин, Дуглас; И Алиферис, Константин; (2006); «Использование весовых методов SVM для определения причинно-значимых и не связанных с причинно-следственной связью переменных» , Знак , 1, 4.
- ^ "Почему маржа SVM равна 2 ‖ ш ‖ {\ displaystyle {\ frac {2} {\ | \ mathbf {w} \ |}}} " . Mathematics Stack Exchange . 30 мая 2015 г."
- ^ Aizerman, Mark A .; Браверман, Эммануэль М. и Розоноер, Лев I. (1964). «Теоретические основы метода потенциальных функций в обучении распознаванию образов». Автоматизация и телемеханика . 25 : 821–837.
- ^ Джин, Чи; Ван, Ливэй (2012). Граница маржи PAC-Байеса, зависящая от размерности . Достижения в системах обработки нейронной информации. CiteSeerX 10.1.1.420.3487 . Архивировано 2 апреля 2015 года.
- ^ Шалев-Шварц, Шай; Певец, Йорам; Сребро, Натан; Коттер, Эндрю (16.10.2010). «Pegasos: решатель первичных оценок субградиентов для SVM». Математическое программирование . 127 (1): 3–30. CiteSeerX 10.1.1.161.9629 . DOI : 10.1007 / s10107-010-0420-4 . ISSN 0025-5610 . S2CID 53306004 .
- ^ Се, Чо-Джуй; Чанг, Кай-Вэй; Линь, Чи-Джен; Кирти, С. Сатья; Сундарараджан, С. (01.01.2008). Метод двойного координатного спуска для крупномасштабной линейной SVM . Материалы 25-й Международной конференции по машинному обучению . ICML '08. Нью-Йорк, Нью-Йорк, США: ACM. С. 408–415. CiteSeerX 10.1.1.149.5594 . DOI : 10.1145 / 1390156.1390208 . ISBN 978-1-60558-205-4. S2CID 7880266 .
- ^ Росаско, Лоренцо; Де Вито, Эрнесто; Капоннетто, Андреа; Пиана, Микеле; Верри, Алессандро (2004-05-01). «Все ли функции потерь одинаковы?» . Нейронные вычисления . 16 (5): 1063–1076. CiteSeerX 10.1.1.109.6786 . DOI : 10.1162 / 089976604773135104 . ISSN 0899-7667 . PMID 15070510 . S2CID 11845688 .
- ^ Мейер, Дэвид; Лейш, Фридрих; Хорник, Курт (сентябрь 2003 г.). «Тестируемая машина опорных векторов». Нейрокомпьютеры . 55 (1–2): 169–186. DOI : 10.1016 / S0925-2312 (03) 00431-4 .
- ^ Сюй, Чжи-Вэй; Чанг, Чих-Чунг и Линь, Чих-Джен (2003). Практическое руководство по классификации опорных векторов (PDF) (Технический отчет). Департамент компьютерных наук и информационной инженерии, Национальный университет Тайваня. Архивировано (PDF) из оригинала 25.06.2013.
- ^ а б Дуань, Кай-Бо; Кирти, С. Сатья (2005). «Какой метод мультиклассовой SVM лучше всего? Эмпирическое исследование» (PDF) . Системы множественных классификаторов . LNCS . 3541 . С. 278–285. CiteSeerX 10.1.1.110.6789 . DOI : 10.1007 / 11494683_28 . ISBN 978-3-540-26306-7.
- ^ Сюй, Чжи-Вей и Линь, Чжи-Джен (2002). «Сравнение методов для мультиклассовых машин опорных векторов» (PDF) . IEEE-транзакции в нейронных сетях . 13 (2): 415–25. DOI : 10.1109 / 72.991427 . PMID 18244442 .
- ^ Платт, Джон; Кристианини, Нелло ; Шоу-Тейлор, Джон (2000). «DAG с большим запасом для мультиклассовой классификации» (PDF) . В Solla, Sara A .; Лин, Тодд К .; Мюллер, Клаус-Роберт (ред.). Достижения в системах обработки нейронной информации . MIT Press. С. 547–553. Архивировано (PDF) из оригинала на 16.06.2012.
- ^ Dietterich, Thomas G .; Бакири, Гулум (1995). «Решение проблем многоклассового обучения с помощью кодов вывода с исправлением ошибок» (PDF) . Журнал исследований искусственного интеллекта . 2 : 263–286. arXiv : cs / 9501101 . Bibcode : 1995cs ........ 1101D . DOI : 10.1613 / jair.105 . S2CID 47109072 . Архивировано (PDF) из оригинала на 2013-05-09.
- ^ Краммер, Коби и Сингер, Йорам (2001). "Об алгоритмической реализации векторных машин на основе мультиклассового ядра" (PDF) . Журнал исследований в области машинного обучения . 2 : 265–292. Архивировано (PDF) из оригинала 29 августа 2015 года.
- ^ Ли, Юнкён; Лин, Йи и Вахба, Грейс (2001). «Машины с мультикатегорийными векторами поддержки» (PDF) . Вычислительная техника и статистика . 33 . Архивировано (PDF) из оригинала 17.06.2013.
- ^ Ли, Юнкён; Линь, Йи; Вахба, Грейс (2004). «Машины с мультикатегорийными опорными векторами». Журнал Американской статистической ассоциации . 99 (465): 67–81. CiteSeerX 10.1.1.22.1879 . DOI : 10.1198 / 016214504000000098 . S2CID 7066611 .
- ^ Ван ден Бург, Геррит Дж. Дж. И Гроенен, Патрик Дж. Ф. (2016). «GenSVM: Обобщенная машина векторов поддержки мультиклассов» (PDF) . Журнал исследований в области машинного обучения . 17 (224): 1–42.
- ^ Иоахим, Торстен; « Преобразовательный вывод для классификации текста с использованием машин опорных векторов », Труды Международной конференции по машинному обучению 1999 г. (ICML 1999) , стр. 200–209.
- ^ Друкер, Харрис; Берджес, Христос. C .; Кауфман, Линда; Смола, Александр Дж .; и Вапник, Владимир Н. (1997); « Машины регрессии опорных векторов », в « Достижения в системах обработки нейронной информации» 9, NIPS 1996 , 155–161, MIT Press.
- ^ Suykens, Йохан АК; Vandewalle, Joos PL; " Метод наименьших квадратов поддерживает векторные машинные классификаторы ", Neural Processing Letters , vol. 9, вып. 3, июнь 1999 г., стр. 293–300.
- ^ Смола, Алекс Дж .; Шёлкопф, Бернхард (2004). «Учебное пособие по поддержке векторной регрессии» (PDF) . Статистика и вычисления . 14 (3): 199–222. CiteSeerX 10.1.1.41.1452 . DOI : 10,1023 / Б: STCO.0000035301.49549.88 . С2КИД 15475 . Архивировано (PDF) из оригинала 31 января 2012 года.
- ^ Polson, Nicholas G .; Скотт, Стивен Л. (2011). «Расширение данных для машин опорных векторов» . Байесовский анализ . 6 (1): 1-23. DOI : 10.1214 / 11-BA601 .
- ^ Венцель, Флориан; Гали-Фаджу, Тео; Дойч, Маттеус; Клофт, Мариус (2017). "Байесовские нелинейные машины опорных векторов для больших данных". Машинное обучение и обнаружение знаний в базах данных (ECML PKDD) . Конспект лекций по информатике. 10534 : 307-322. arXiv : 1707.05532 . Bibcode : 2017arXiv170705532W . DOI : 10.1007 / 978-3-319-71249-9_19 . ISBN 978-3-319-71248-2. S2CID 4018290 .
- ^ Флориан Венцель; Маттеус Дойч; Тео Гали-Фажу; Мариус Клофт; «Масштабируемый приближенный вывод для байесовской нелинейной машины опорных векторов»
- ^ Феррис, Майкл С .; Мансон, Тодд С. (2002). "Методы внутренней точки для машин с массивными опорными векторами" (PDF) . SIAM Journal по оптимизации . 13 (3): 783–804. CiteSeerX 10.1.1.216.6893 . DOI : 10.1137 / S1052623400374379 . Архивировано (PDF) из оригинала на 2008-12-04.
- ^ Платт, Джон С. (1998). Последовательная минимальная оптимизация: быстрый алгоритм для обучения машин опорных векторов (PDF) . НИПС. Архивировано (PDF) из оригинала на 2015-07-02.
- ^ Шалев-Шварц, Шай; Певец, Йорам; Сребро, Натан (2007). Pegasos: Первичная оценка суб-GrAdient SOlver для SVM (PDF) . ICML. Архивировано (PDF) из оригинала 15.12.2013.
- ^ Fan, Rong-En; Чанг, Кай-Вэй; Се, Чо-Джуй; Ван, Сян-Жуй; Лин, Чи-Джен (2008). «LIBLINEAR: библиотека для большой линейной классификации» (PDF) . Журнал исследований в области машинного обучения . 9 : 1871–1874.
- ^ Аллен Чжу, Zeyuan; Чен, Вэйчжу; Ванга, банда; Чжу, Чэнгуан; Чен, Чжэн (2009). P-packSVM: параллельный базовый компонент ядра SVM (PDF) . ICDM. Архивировано (PDF) из оригинала 07.04.2014.
- ^ Fan, Rong-En; Чанг, Кай-Вэй; Се, Чо-Джуй; Ван, Сян-Жуй; Лин, Чи-Джен (2008). «LIBLINEAR: библиотека для большой линейной классификации». Журнал исследований в области машинного обучения . 9 (август): 1871–1874.
- ^ Мохамад, Исмаил; Усман, Дауда (01.09.2013). «Стандартизация и ее влияние на алгоритм кластеризации K-средних» . Научно-исследовательский журнал прикладных наук, техники и технологий . 6 (17): 3299–3303. DOI : 10,19026 / rjaset.6.3638 .
- ^ Феннелл, Питер; Цзо, Чжия; Лерман, Кристина (01.12.2019). «Прогнозирование и объяснение поведенческих данных с помощью структурированной декомпозиции пространства признаков» . EPJ Data Science . 8 . DOI : 10,1140 / epjds / s13688-019-0201-0 .
дальнейшее чтение
- Bennett, Kristin P .; Кэмпбелл, Колин (2000). "Машины опорных векторов: шумиха или аллилуйя?" (PDF) . SIGKDD Исследования . 2 (2): 1–13. DOI : 10.1145 / 380995.380999 . S2CID 207753020 .
- Кристианини, Нелло; Шоу-Тейлор, Джон (2000). Введение в опорные векторные машины и другие методы обучения на основе ядра . Издательство Кембриджского университета. ISBN 0-521-78019-5.
- Фрадкин Дмитрий; Мучник, Илья (2006). «Машины опорных векторов для классификации» (PDF) . В Abello, J .; Кармод, Г. (ред.). Дискретные методы в эпидемиологии . Серия DIMACS по дискретной математике и теоретической информатике. 70 . С. 13–20.
- Иванчук, Овидиу (2007). "Применение машин опорных векторов в химии" (PDF) . Обзоры по вычислительной химии . 23 : 291–400. DOI : 10.1002 / 9780470116449.ch6 . ISBN 9780470116449.
- Джеймс, Гарет; Виттен, Даниэла; Хасти, Тревор; Тибширани, Роберт (2013). «Машины опорных векторов» (PDF) . Введение в статистическом обучение: с приложениями в R . Нью-Йорк: Спрингер. С. 337–372. ISBN 978-1-4614-7137-0.
- Шёлкопф, Бернхард; Смола, Александр Дж. (2002). Обучение с помощью ядер . Кембридж, Массачусетс: MIT Press. ISBN 0-262-19475-9.
- Стейнварт, Инго; Кристманн, Андреас (2008). Машины опорных векторов . Нью-Йорк: Спрингер. ISBN 978-0-387-77241-7.
- Теодоридис, Сергий; Кутроумбас, Константинос (2009). Распознавание образов (4-е изд.). Академическая пресса. ISBN 978-1-59749-272-0.
Внешние ссылки
- libsvm , LIBSVM - популярная библиотека обучающихся SVM.
- liblinear - это библиотека для большой линейной классификации, включая некоторые SVM
- SVM light - это набор программных инструментов для обучения и классификации с использованием SVM.
- Живая демонстрация SVMJS - это демонстрация графического интерфейса для реализации SVM на JavaScript.