WikiSort.ru - Не сортированное

Машинное обучение и data mining

Задачи Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение

Обучение с учителем Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей (Бэггинг, Бустинг, Random forest) Метод релевантных векторов

Кластерный анализ Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift

Снижение размерности Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE

Структурное прогнозирование Графовая вероятностная модель (Байесовская сеть, Скрытая марковская модель, CRF)

Выявление аномалий Метод k-ближайших соседей Локальный уровень выброса

Графовые вероятностные модели Байесовская сеть Марковская сеть Скрытая марковская модель

Искусственные нейронные сети Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации (Сигмоида, Softmax, Радиально-базисная функция) Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть (Долгая краткосрочная память, Управляемый рекуррентный блок) Свёрточная нейронная сеть (U-Net) Автокодировщик

Обучение с подкреплением Марковский процесс Уравнение Беллмана Жадный алгоритм Q-learning SARSA Temporal difference (TD)

Теория Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения

Журналы и конференции NIPS ICML ML JMLR ArXiv:cs.LG

Глоссарий Глоссарий по машинному обучению

Статьи по теме List of datasets for machine-learning research Outline of machine learning

Метод опорных векторов (англ. SVM, support vector machine) — набор схожих алгоритмов обучения с учителем, использующихся для задач классификации и регрессионного анализа. Принадлежит семейству линейных классификаторов и может также рассматриваться как специальный случай регуляризации по Тихонову. Особым свойством метода опорных векторов является непрерывное уменьшение эмпирической ошибки классификации и увеличение зазора, поэтому метод также известен как метод классификатора с максимальным зазором.

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

Постановка задачи

Часто в алгоритмах машинного обучения возникает необходимость классифицировать данные. Каждый объект данных представляется как вектор (точка) в ${\displaystyle p}$ -мерном пространстве (упорядоченный набор ${\displaystyle p}$ чисел). Каждая из этих точек принадлежит только одному из двух классов. Вопрос состоит в том, можно ли разделить точки гиперплоскостью размерности (${\displaystyle p}$ −1). Это — типичный случай линейной разделимости. Искомых гиперплоскостей может быть много, поэтому полагают, что максимизация зазора между классами способствует более уверенной классификации. То есть, можно ли найти такую гиперплоскость, чтобы расстояние от неё до ближайшей точки было максимальным. Это эквивалентно^[1] тому, что сумма расстояний до гиперплоскости от двух ближайших к ней точек, лежащих по разные стороны от неё, максимально. Если такая гиперплоскость существует, она называется оптимальной разделяющей гиперплоскостью, а соответствующий ей линейный классификатор называется оптимально разделяющим классификатором.

Формальное описание задачи

Мы полагаем, что точки имеют вид:

${\displaystyle \{(\mathbf {x} _{1},c_{1}),(\mathbf {x} _{2},c_{2}),\ldots ,(\mathbf {x} _{n},c_{n})\}}$

где ${\displaystyle c_{i}}$ принимает значение 1 или −1, в зависимости от того, какому классу принадлежит точка ${\displaystyle \mathbf {x} _{i}}$ . Каждое ${\displaystyle \mathbf {x} _{i}}$  — это ${\displaystyle p}$ -мерный вещественный вектор, обычно нормализованный значениями ${\displaystyle [0,1]}$ или ${\displaystyle [-1,1]}$ . Если точки не будут нормализованы, то точка с большими отклонениями от средних значений координат точек слишком сильно повлияет на классификатор. Мы можем рассматривать это как учебную коллекцию, в которой для каждого элемента уже задан класс, к которому он принадлежит. Мы хотим, чтобы алгоритм метода опорных векторов классифицировал их таким же образом. Для этого мы строим разделяющую гиперплоскость, которая имеет вид:

${\displaystyle \mathbf {w} \cdot \mathbf {x} -b=0.}$

Вектор ${\displaystyle \mathbf {w} }$  — перпендикуляр к разделяющей гиперплоскости. Параметр ${\displaystyle {\frac {b}{\|\mathbf {w} \|}}}$ равен по модулю расстоянию от гиперплоскости до начала координат. Если параметр b равен нулю, гиперплоскость проходит через начало координат, что ограничивает решение.

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

${\displaystyle \mathbf {w} \cdot \mathbf {x} -b=1,}$

${\displaystyle \mathbf {w} \cdot \mathbf {x} -b=-1.}$

Если обучающая выборка линейно разделима, то мы можем выбрать гиперплоскости таким образом, чтобы между ними не лежала ни одна точка обучающей выборки и затем максимизировать расстояние между гиперплоскостями. Ширину полосы между ними легко найти из соображений геометрии, она равна ${\displaystyle {\frac {2}{\|\mathbf {w} \|}}}$ ^[2], таким образом наша задача минимизировать ${\displaystyle \|\mathbf {w} \|}$ . Чтобы исключить все точки из полосы, мы должны убедиться для всех ${\displaystyle i}$ , что

${\displaystyle \left[{\begin{array}{lcr}\mathbf {w} \cdot \mathbf {x_{i}} -b\geq 1,\ c_{i}=1\mathrm {} \\\mathbf {w} \cdot \mathbf {x_{i}} -b\leq -1,\ c_{i}=-1\mathrm {} \\\end{array}}\right.}$

Это может быть также записано в виде:

${\displaystyle c_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1,\quad 1\leq i\leq n.\qquad \qquad (1)}$

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

Проблема построения оптимальной разделяющей гиперплоскости сводится к минимизации ${\displaystyle \|\mathbf {w} \|}$ , при условии (1). Это задача квадратичной оптимизации, которая имеет вид:

${\displaystyle \left\{{\begin{array}{lcr}\|\mathbf {w} \|^{2}\to \min \\c_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1,\quad 1\leq i\leq n.\\\end{array}}\right.}$

По теореме Куна — Таккера эта задача эквивалентна двойственной задаче поиска седловой точки функции Лагранжа ${\displaystyle \left\{{\begin{array}{lcr}\mathbf {L} (\mathbf {w} ,\mathbf {b} ;\mathbf {\lambda } )={\frac {1}{2}}\|\mathbf {w} \|^{2}-\sum _{i=1}^{n}\mathbf {\lambda _{i}} (c_{i}((\mathbf {w} \cdot \mathbf {x_{i}} )-b)-1)\to \min _{w,b}\max _{\lambda }\\\mathbf {\lambda _{i}} \geq 0,\quad 1\leq i\leq n\\\end{array}}\right.(2)}$

где ${\displaystyle \mathbf {\lambda } =(\mathbf {\lambda _{1}} ,\ldots ,\mathbf {\lambda _{n}} )}$  — вектор двойственных переменных.

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

${\displaystyle \left\{{\begin{array}{lcr}-\mathbf {L} (\mathbf {\lambda } )=-\sum _{i=1}^{n}\mathbf {\lambda _{i}} +{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}\mathbf {\lambda _{i}} \mathbf {\lambda _{j}} c_{i}c_{j}(\mathbf {x_{i}} \cdot \mathbf {x_{j}} )\to \min _{\lambda }\\\mathbf {\lambda _{i}} \geq 0,\quad 1\leq i\leq n\\\sum _{i=1}^{n}\mathbf {\lambda _{i}} c_{i}=0\\\end{array}}\right.(3)}$

Допустим мы решили данную задачу, тогда ${\displaystyle \mathbf {w} }$ и ${\displaystyle \mathbf {b} }$ можно найти по формулам:

${\displaystyle \mathbf {w} =\sum _{i=1}^{n}\mathbf {\lambda _{i}} c_{i}\mathbf {x_{i}} }$

${\displaystyle \mathbf {b} =\mathbf {w} \cdot \mathbf {x_{i}} -c_{i},\quad \mathbf {\lambda } _{i}>0}$

В итоге алгоритм классификации может быть записан в виде:

${\displaystyle a(x)=sign\left(\sum _{i=1}^{n}\mathbf {\lambda _{i}} c_{i}\mathbf {x_{i}} \cdot \mathbf {x} -b\right)(4)}$

При этом суммирование идёт не по всей выборке, а только по опорным векторам, для которых ${\displaystyle \mathbf {\lambda _{i}} \neq 0}$ .

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

Для того, чтобы алгоритм мог работать в случае, если классы линейно неразделимы, позволим ему допускать ошибки на обучающей выборке. Введём набор дополнительных переменных ${\displaystyle \xi _{i}\geq 0}$ , характеризующих величину ошибки на объектах ${\displaystyle \mathbf {x} _{i},\quad 1\leq i\leq n}$ . Возьмём за отправную точку (2), смягчим ограничения неравенства, так же введём в минимизируемый функционал штраф за суммарную ошибку:

${\displaystyle \left\{{\begin{array}{lcr}{\frac {1}{2}}\|\mathbf {w} \|^{2}+C\sum _{i=1}^{n}\xi _{i}\to \min _{w,b,\xi _{i}}\\c_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1-\xi _{i},\quad 1\leq i\leq n\\\xi _{i}\geq 0,\quad 1\leq i\leq n\\\end{array}}\right.}$

Коэффициент ${\displaystyle C}$  — параметр настройки метода, который позволяет регулировать отношение между максимизацией ширины разделяющей полосы и минимизацией суммарной ошибки.

Аналогично, по теореме Куна-Таккера сводим задачу к поиску седловой точки функции Лагранжа:

${\displaystyle \left\{{\begin{array}{lcr}\mathbf {L} (\mathbf {w} ,\mathbf {b} ,\mathbf {\xi } ;\mathbf {\lambda } ,\mathbf {\eta } )={\frac {1}{2}}\|\mathbf {w} \|^{2}-\sum _{i=1}^{n}\mathbf {\lambda _{i}} (c_{i}((\mathbf {w} \cdot \mathbf {x_{i}} )-b)-1)-\sum _{i=1}^{n}\mathbf {\xi _{i}} (\mathbf {\lambda _{i}} +\mathbf {\eta _{i}} -C)\to \min _{w,b,\xi }\max _{\lambda ,\eta }\\\mathbf {\xi _{i}} \geq 0,\mathbf {\lambda _{i}} \geq 0,\mathbf {\eta _{i}} \geq 0,\quad 1\leq i\leq n\\\left[{\begin{array}{lcr}\mathbf {\lambda _{i}} =0\\c_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)=1-\xi _{i},\\\end{array}}\right.\quad 1\leq i\leq n\\\left[{\begin{array}{lcr}\mathbf {\eta _{i}} =0\\\mathbf {\xi _{i}} =0,\\\end{array}}\right.\quad 1\leq i\leq n\end{array}}\right.}$

По аналогии сведём эту задачу к эквивалентной:

${\displaystyle \left\{{\begin{array}{lcr}-\mathbf {L} (\mathbf {\lambda } )=-\sum _{i=1}^{n}\mathbf {\lambda _{i}} +{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}\mathbf {\lambda _{i}} \mathbf {\lambda _{j}} c_{i}c_{j}(\mathbf {x_{i}} \cdot \mathbf {x_{j}} )\to \min _{\lambda }\\0\leq \mathbf {\lambda _{i}} \leq \mathbf {C} ,\quad 1\leq i\leq n\\\sum _{i=1}^{n}\mathbf {\lambda _{i}} c_{i}=0\\\end{array}}\right.}$

На практике для построения машины опорных векторов решают именно эту задачу, а не (3), так как гарантировать линейную разделимость точек на два класса в общем случае не представляется возможным. Этот вариант алгоритма называют алгоритмом с мягким зазором (soft-margin SVM), тогда как в линейно разделимом случае говорят о жёстком зазоре (hard-margin SVM).

Для алгоритма классификации сохраняется формула (4), с той лишь разницей, что теперь ненулевыми ${\displaystyle \mathbf {\lambda _{i}} }$ обладают не только опорные объекты, но и объекты-нарушители. В определённом смысле это недостаток, поскольку нарушителями часто оказываются шумовые выбросы, и построенное на них решающее правило, по сути дела, опирается на шум.

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

Если есть основания полагать, что выборка почти линейно разделима, и лишь объекты-выбросы классифицируются неверно, то можно применить фильтрацию выбросов. Сначала задача решается при некотором C, и из выборки удаляется небольшая доля объектов, имеющих наибольшую величину ошибки ${\displaystyle \mathbf {\xi _{i}} }$ . После этого задача решается заново по усечённой выборке. Возможно, придётся проделать несколько таких итераций, пока оставшиеся объекты не окажутся линейно разделимыми.

Ядра

Алгоритм построения оптимальной разделяющей гиперплоскости, предложенный в 1963 году Владимиром Вапником и Алексеем Червоненкисом — алгоритм линейной классификации. Однако в 1992 году Бернхард Босер, Изабель Гийон и Вапник предложили способ создания нелинейного классификатора, в основе которого лежит переход от скалярных произведений к произвольным ядрам, так называемый kernel trick (предложенный впервые М. А. Айзерманом, Э. М. Браверманом и Л. В. Розоноэром для метода потенциальных функций), позволяющий строить нелинейные разделители. Результирующий алгоритм крайне похож на алгоритм линейной классификации, с той лишь разницей, что каждое скалярное произведение в приведённых выше формулах заменяется нелинейной функцией ядра (скалярным произведением в пространстве с большей размерностью). В этом пространстве уже может существовать оптимальная разделяющая гиперплоскость. Так как размерность получаемого пространства может быть больше размерности исходного, то преобразование, сопоставляющее скалярные произведения, будет нелинейным, а значит функция, соответствующая в исходном пространстве оптимальной разделяющей гиперплоскости, будет также нелинейной.

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

Наиболее распространённые ядра:

• Полиномиальное (однородное): ${\displaystyle k(\mathbf {x} ,\mathbf {x} ')=(\mathbf {x} \cdot \mathbf {x'} )^{d}}$
• Полиномиальное (неоднородное): ${\displaystyle k(\mathbf {x} ,\mathbf {x} ')=(\mathbf {x} \cdot \mathbf {x'} +1)^{d}}$
• Радиальная базисная функция: ${\displaystyle k(\mathbf {x} ,\mathbf {x} ')=\exp(-\gamma \|\mathbf {x} -\mathbf {x'} \|^{2})}$ , для ${\displaystyle \gamma >0}$
• Радиальная базисная функция Гаусса: ${\displaystyle k(\mathbf {x} ,\mathbf {x} ')=\exp \left(-{\frac {\|\mathbf {x} -\mathbf {x'} \|^{2}}{2\sigma ^{2}}}\right)}$
• Сигмоид: ${\displaystyle k(\mathbf {x} ,\mathbf {x} ')=\tanh(\kappa \mathbf {x} \cdot \mathbf {x'} +c)}$ , для почти всех ${\displaystyle \kappa >0}$ и ${\displaystyle c<0}$

См. также

• Размерность Вапника — Червоненкиса

Примечания

Литература

• Владимир Вьюгин. Математические основы теории машинного обучения и прогнозирования. — МЦМНО, 2013. — 390 с. — ISBN 978-5-4439-0111-4.
• Nello Cristianini, John Shawe-Taylor. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. — Cambridge University Press, 2000. — ISBN 978-1-139-64363-4.
• Alexander Statnikov, Constantin F. Aliferis, Douglas P. Hardin. A Gentle Introduction to Support Vector Machines in Biomedicine: Theory and methods. — World Scientific, 2011. — ISBN 978-981-4324-38-0.
• Alexey Nefedov. Support Vector Machines: A Simple Tutorial. — 2016.

Ссылки

• Data Mining. 10. Лекция: Методы классификации и прогнозирования. Метод опорных векторов // Интуит.ру
• Юрий Лифшиц. Метод опорных векторов (Слайды) — лекция № 7 из курса «Алгоритмы для Интернета»