23
правки
Изменения
Новая страница: «{{в разработке}} '''Метод опорных векторов''' (англ. ''support vector machine'', ''SVM'') — семейство алгори…»
{{в разработке}}
'''Метод опорных векторов''' (англ. ''support vector machine'', ''SVM'') — семейство алгоритмов обучения с учителем, использующихся для решения задач классификации и регрессии. Основная идея метода заключается в построении гиперплоскости, разделяющей объекты выборки наиболее оптимальным способом.
== Метод опорных векторов в задаче классификации ==
Рассмотрим задачу классификации, в которой объектам из $X=\mathbb{R}^n$ соответствует один из двух классов $Y = \{-1, 1\}$.
Пусть задана обучающая выборка пар "объект-ответ" $X^\ell = (x_i, y_i)_{i=1}^\ell$. Будем строить линейный пороговый классификатор:
$$a(x) = sign\left(\sum\limits_{j=1}^\ell w_j x^j - w_0\right) = sign(\langle w, x \rangle - w_0)$$
где $x = (x^1, \ldots, x^n)$ — вектор значений признаков объекта, а $w = (w_1, \ldots, w_n)$ и $w_0 \in \mathbb{R}$ — параметры алгоритма.
=== Оптимальная разделяющая гиперплоскость ===
Пусть выборка линейно разделима, то есть существуют такие значения параметров $w$ и $w_0$, для которых функционал количества ошибок равен нулю.
{{Определение
|definition=
'''Отступ''' (англ. ''margin'') — характеристика, оценивающая, насколько объект "погружён" в свой класс, насколько типичным представителем класса он является. Чем меньше значение отступа $M(x_i, y_i)$, тем ближе объект подходит к границе классов и тем выше становится вероятность ошибки. Отступ $M(x_i, y_i)$ отрицателен тогда и только тогда, когда алгоритм $a(x)$ допускает ошибку на объекте $x_i$.
Для задачи бинарной классификации: $M(x_i, y_i) = y_i(\langle x_i, w \rangle - w_0)$
Для задачи классификации на несколько классов: $M(x_i, y_i) = \langle x_i, w_{y_i}\rangle - \max\limits_{y \in \mathbb{Y}, y \ne y_i} \langle x_i, w_y\rangle$
}}
{{Теорема
|id=kkt
|author=Условия Каруша—Куна—Таккера
|statement=
Пусть поставлена задача нелинейного программирования с ограничениями:
$$
\begin{cases}
f(x) \to \min\limits_{x \in X} \\
g_i(x) \leq 0,\;i=1\ldots m \\
h_j(x) = 0,\;j=1\ldots k
\end{cases}
$$
Если $\hat{x} \in \arg\min f$ — решение задачи при наложенных ограничениях, то существуют множители $\mu_i, i = 1\ldots m$, $\lambda_j, j = 1\ldots k$, что для функции Лагранжа $L(x; \mu, \lambda)$ выполняются условия:
$$\begin{cases}\frac{\partial L}{\partial x} = 0 \quad L(x; \mu, \lambda) = f(x) + \sum\limits_{i=1}^m \mu_i g_i(x) + \sum\limits_{j=1}^k \lambda_j h_j(x) \\ g_i(x) \leq 0,\;h_j(x) = 0 \quad \text{(исходные ограничения)} \\ \mu_i \geq 0 \quad \text{(двойственные ограничения)} \\ \mu_i g_i(x) = 0 \quad \text{(условие дополняющей нежёсткости)} \end{cases}$$
}}
В качестве аппроксимации функции потерь возьмём $L(x_i, y_i) = max(0, 1 - M_i(w, w_0))$
Запишем функционал для метода оптимизации эмпирического риска с использованием данной функции потерь и регуляризации:
$\sum\limits_{i=1}^\ell (1 - M_i(w, w_0))_+ + \frac{1}{2C} \lVert w \rVert^2 \to \min\limits_{w, w_0}$
=== Двойственная задача ===
=== Линейно неразделимая выборка ===
== Метод опорных векторов в задаче регрессии ==
// TODO
== См. также ==
* [[Обзор библиотек для машинного обучения на Python]]
* [[Общие понятия]]
== Примечания ==
<references/>
== Источники информации ==
* [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%BE%D0%BF%D0%BE%D1%80%D0%BD%D1%8B%D1%85_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BE%D0%B2 machinelearning.ru {{---}} Машина опорных векторов]
* [https://www.youtube.com/watch?v=Adi67_94_gc&list=PLJOzdkh8T5kp99tGTEFjH_b9zqEQiiBtC&index=5 Лекция "Линейные методы классификации: метод опорных векторов"] {{---}} К.В. Воронцов, курс "Машинное обучение" 2014
* [https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BE%D0%BF%D0%BE%D1%80%D0%BD%D1%8B%D1%85_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BE%D0%B2 Wikipedia {{---}} Метод опорных векторов]
* Alexey Nefedov {{---}} [https://svmtutorial.online/ Support Vector Machines: A Simple Tutorial]
* John Platt {{---}} [https://www.microsoft.com/en-us/research/publication/sequential-minimal-optimization-a-fast-algorithm-for-training-support-vector-machines/ Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines]
[[Категория: Машинное обучение]]
[[Категория: Классификация]]
[[Категория: Регрессия]]
'''Метод опорных векторов''' (англ. ''support vector machine'', ''SVM'') — семейство алгоритмов обучения с учителем, использующихся для решения задач классификации и регрессии. Основная идея метода заключается в построении гиперплоскости, разделяющей объекты выборки наиболее оптимальным способом.
== Метод опорных векторов в задаче классификации ==
Рассмотрим задачу классификации, в которой объектам из $X=\mathbb{R}^n$ соответствует один из двух классов $Y = \{-1, 1\}$.
Пусть задана обучающая выборка пар "объект-ответ" $X^\ell = (x_i, y_i)_{i=1}^\ell$. Будем строить линейный пороговый классификатор:
$$a(x) = sign\left(\sum\limits_{j=1}^\ell w_j x^j - w_0\right) = sign(\langle w, x \rangle - w_0)$$
где $x = (x^1, \ldots, x^n)$ — вектор значений признаков объекта, а $w = (w_1, \ldots, w_n)$ и $w_0 \in \mathbb{R}$ — параметры алгоритма.
=== Оптимальная разделяющая гиперплоскость ===
Пусть выборка линейно разделима, то есть существуют такие значения параметров $w$ и $w_0$, для которых функционал количества ошибок равен нулю.
{{Определение
|definition=
'''Отступ''' (англ. ''margin'') — характеристика, оценивающая, насколько объект "погружён" в свой класс, насколько типичным представителем класса он является. Чем меньше значение отступа $M(x_i, y_i)$, тем ближе объект подходит к границе классов и тем выше становится вероятность ошибки. Отступ $M(x_i, y_i)$ отрицателен тогда и только тогда, когда алгоритм $a(x)$ допускает ошибку на объекте $x_i$.
Для задачи бинарной классификации: $M(x_i, y_i) = y_i(\langle x_i, w \rangle - w_0)$
Для задачи классификации на несколько классов: $M(x_i, y_i) = \langle x_i, w_{y_i}\rangle - \max\limits_{y \in \mathbb{Y}, y \ne y_i} \langle x_i, w_y\rangle$
}}
{{Теорема
|id=kkt
|author=Условия Каруша—Куна—Таккера
|statement=
Пусть поставлена задача нелинейного программирования с ограничениями:
$$
\begin{cases}
f(x) \to \min\limits_{x \in X} \\
g_i(x) \leq 0,\;i=1\ldots m \\
h_j(x) = 0,\;j=1\ldots k
\end{cases}
$$
Если $\hat{x} \in \arg\min f$ — решение задачи при наложенных ограничениях, то существуют множители $\mu_i, i = 1\ldots m$, $\lambda_j, j = 1\ldots k$, что для функции Лагранжа $L(x; \mu, \lambda)$ выполняются условия:
$$\begin{cases}\frac{\partial L}{\partial x} = 0 \quad L(x; \mu, \lambda) = f(x) + \sum\limits_{i=1}^m \mu_i g_i(x) + \sum\limits_{j=1}^k \lambda_j h_j(x) \\ g_i(x) \leq 0,\;h_j(x) = 0 \quad \text{(исходные ограничения)} \\ \mu_i \geq 0 \quad \text{(двойственные ограничения)} \\ \mu_i g_i(x) = 0 \quad \text{(условие дополняющей нежёсткости)} \end{cases}$$
}}
В качестве аппроксимации функции потерь возьмём $L(x_i, y_i) = max(0, 1 - M_i(w, w_0))$
Запишем функционал для метода оптимизации эмпирического риска с использованием данной функции потерь и регуляризации:
$\sum\limits_{i=1}^\ell (1 - M_i(w, w_0))_+ + \frac{1}{2C} \lVert w \rVert^2 \to \min\limits_{w, w_0}$
=== Двойственная задача ===
=== Линейно неразделимая выборка ===
== Метод опорных векторов в задаче регрессии ==
// TODO
== См. также ==
* [[Обзор библиотек для машинного обучения на Python]]
* [[Общие понятия]]
== Примечания ==
<references/>
== Источники информации ==
* [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%BE%D0%BF%D0%BE%D1%80%D0%BD%D1%8B%D1%85_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BE%D0%B2 machinelearning.ru {{---}} Машина опорных векторов]
* [https://www.youtube.com/watch?v=Adi67_94_gc&list=PLJOzdkh8T5kp99tGTEFjH_b9zqEQiiBtC&index=5 Лекция "Линейные методы классификации: метод опорных векторов"] {{---}} К.В. Воронцов, курс "Машинное обучение" 2014
* [https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BE%D0%BF%D0%BE%D1%80%D0%BD%D1%8B%D1%85_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BE%D0%B2 Wikipedia {{---}} Метод опорных векторов]
* Alexey Nefedov {{---}} [https://svmtutorial.online/ Support Vector Machines: A Simple Tutorial]
* John Platt {{---}} [https://www.microsoft.com/en-us/research/publication/sequential-minimal-optimization-a-fast-algorithm-for-training-support-vector-machines/ Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines]
[[Категория: Машинное обучение]]
[[Категория: Классификация]]
[[Категория: Регрессия]]
