SVM регрессия (пример)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: '''SVM (Support Vector Machine, машина опорных векторов)''' - это особый класс алгоритмов, который характеризуется ...)
(→Исходный код)
 
(19 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
'''SVM (Support Vector Machine, [[машина опорных векторов]])''' - это особый класс алгоритмов, который характеризуется использованием ядер, отсутствием локальных минимумов, и т.д.
+
'''SVM (Support Vector Machine, [[машина опорных векторов]])''' — это особый класс алгоритмов, который характеризуется использованием ядер, отсутствием локальных минимумов, и используется для решения задач классификации и регрессии. В этой статье рассматривается пример использования метода опорных векторов в задачах регрессии.
 +
 
 +
 
 +
== Постановка задачи ==
 +
 
 +
'''Дано:''' Обучающая выборка <tex>X=\{(x_i,y_i)\}_{i=1}^{\ell}</tex>, где <tex>x_i</tex>-признаковое описание i-го объекта, <tex>y_i</tex> - характеристика, приписываемая объекту. Функция потерь имеет вид <tex>a(x_i)=\mid (w,f(x_i))-w_0-y_i \mid_\epsilon</tex> для каждого вектора <tex>(x_i,y_i)</tex>, где <tex>\mid z \mid_\epsilon = max(0,\mid z \mid-\epsilon)</tex>.
 +
 
 +
'''Найти:''' такую функцию&nbsp;<tex>f_0</tex>, которая описывает зависимость <tex>E(y|\mathbf{x})=f_0(\mathbf{x})</tex> наилучшим образом.
 +
 
 +
== Алгоритм ==
 +
{{Main|Машина опорных векторов}}
 +
В этом примере решается задача построения линейной SVM регрессии. Для этого решается прямая задача минимизации функционала потерь, в предположении что решение задается линейной комбинацией неких порождающих функций, из которых можем составить вектор-функцию
 +
<tex>
 +
f(x)=\begin{Vmatrix}
 +
f_1(x) \\
 +
f_2(x) \\
 +
\vdots \\
 +
f_k(x)
 +
\end{Vmatrix}
 +
</tex>.
 +
 
 +
Тогда функционал примет вид:
 +
::<tex>Q_\epsilon(a,X)=\sum_{i=1}^\ell \mid (w,f(x_i))-w_0-y_i \mid_\epsilon + \tau (w,w)^2 \rightarrow \underset{w,w_0}{min}</tex>
 +
В предположении что
 +
::<tex>f_0(x)=\sum_{i=1}^k w_i f_i(x)</tex>
 +
Для этого вводятся обозначение <tex>C=\frac{1}{2\tau}</tex> и дополнительные переменные <tex>\xi_i^+</tex> и <tex>\xi_i^-</tex>:
 +
 
 +
::<tex>\xi_i^+=(a(x_i)-y_i-\epsilon)_+</tex>, <tex>\xi_i^-=(-a(x_i)+y_i-\epsilon)_-</tex>, <tex>i=1,...,l</tex>.
 +
Геометрический смысл <tex>\xi_i^+</tex> и <tex>\xi_i^-</tex>:
 +
 
 +
[[Изображение:GeometricalSenceOfKsi.jpg]]
 +
 
 +
Далее решается задача квадратичного программирования:
 +
 
 +
<tex>
 +
\begin{cases}
 +
\frac{1}{2} (w,w) + C\sum_{i=1}^\ell(\xi_i^+ + \xi_i^-)\rightarrow \underset{w,w_0,\xi_i^+,\xi_i^-}{min}, \\
 +
(w,f(x_i))-w_0 \le y_i + \epsilon + \xi_i^+, & i=1,..,\ell; \\
 +
(w,f(x_i))-w_0 \ge y_i - \epsilon - \xi_i^-, & i=1,..,\ell; \\
 +
\xi_i^- \ge 0, \mbox{ } i=1,..,\ell; \\
 +
\xi_i^+ \ge 0, \mbox{ } i=1,..,\ell; \\
 +
\end{cases}
 +
</tex>
 +
 
 +
Эту же задачу можно преобразовать к виду <tex>\frac{1}{2}u^T H u + g u\rightarrow \underset{u}{min}</tex>, при условии, что <tex>A u \le b,\ </tex>а также, <tex>lb \le u</tex>, где <tex>u</tex> - вектор-столбец, составленный из столбцов <tex>w\ , \xi_i^+, \xi_i^-</tex>, тоесть, где все переменные объединены в один столбец неизвестных. В таких обозначениях <tex>H=diag(1,1,...,1,0,0,...,0),\ g=(0,0,...,0,1,1,...,1)</tex>, где единиц и нулей в <tex>H</tex> и <tex>g</tex> соответственно столько же, сколько порождающих функций, а размерность матрицы <tex>H</tex> и вектора <tex>g</tex> равна размерности <tex>u</tex>.
 +
 
 +
Теперь построим матрицу А и столбцы <tex>b</tex> и <tex>lb</tex>. Преобразуем задачу квадратичного программирования к виду
 +
 
 +
<tex>
 +
\begin{cases}
 +
\frac{1}{2} (w,w) + C\sum_{i=1}^\ell(\xi_i^+ + \xi_i^-)\rightarrow \underset{w,w_0,\xi_i^+,\xi_i^-}{min}, \\
 +
(w,f(x_i)) - w_0 -\xi_i^+ \le y_i + \epsilon , & i=1,..,\ell; \\
 +
-(w,f(x_i))+ w_0 -\xi_i^- \le -y_i + \epsilon , & i=1,..,\ell; \\
 +
0 \le \xi_i^-, \mbox{ } i=1,..,\ell; \\
 +
0 \le \xi_i^+, \mbox{ } i=1,..,\ell; \\
 +
\end{cases}
 +
</tex>
 +
 
 +
Получаем,
 +
<tex>
 +
A=\begin{Vmatrix}
 +
f^T(\x_1) & -1 & 0 & \cdots & 0 \\
 +
f^T(\x_2) & 0 & -1 & \cdots & 0 \\
 +
\vdots & \vdots &\vdots & \ddots & \vdots \\
 +
f^T(\x_\ell) & 0 & 0 & \vdots & 0 \\
 +
-f^T(\x_1) & 0 & 0 & \vdots & 0 \\
 +
\vdots & \vdots &\vdots & \ddots & \vdots \\
 +
-f^T(\x_\ell) & 0 & 0 & \cdots & -1 \\
 +
\end{Vmatrix},\ b=
 +
\begin{Vmatrix}
 +
y_1 + \epsilon \\
 +
y_2 + \epsilon \\
 +
\vdots \\
 +
y_\ell + \epsilon \\
 +
-y_1 + \epsilon \\
 +
\vdots \\
 +
-y_\ell + \epsilon \\
 +
\end{Vmatrix},\ lb=
 +
\begin{Vmatrix}
 +
-\infty \\
 +
-\infty \\
 +
\vdots \\
 +
-\infty \\
 +
0 \\
 +
\vdots \\
 +
0 \\
 +
\end{Vmatrix}
 +
</tex>, и количество минус бесконечностей в lb равно количеству порождающих функций, а количество нулей равно <tex>2\ell</tex>.
 +
 
 +
Таким образом, мы свели задачу к задаче квадратичного программирования.
 +
 
 +
В нашем примере значения С, <tex>\epsilon</tex> и порождающие функции задаются экспертом.
 +
 
 +
== Вычислительный эксперимент ==
 +
 
 +
Вычислительный эксперимент состоит из трех основных частей:
 +
* Генерация данных;
 +
* Работа алгоритма;
 +
* Визуализация и анализ данных.
 +
 
 +
=== Генерация данных ===
 +
 
 +
При генерации данных мы выбираем некую линейную комбинацию наших порождающих функций, и добавляем к ней случайный шум. В ходе эксперимента исследуются различные, как дискретные, так и непрерывные шумы. В качестве базовой функции выбрана функция <tex>y = 3 + x - 1.5sin(x)</tex>. А в качестве порождающих функций <tex>x,\ e^x,\ sin(x),\ cos(x),\ x^{\frac{1}{2}},\ x^{\frac{3}{2}}, x^0</tex>.
 +
 
 +
=== Нормальное распределение ===
 +
 
 +
[[Изображение:Svr Normal.jpg|800px]]
 +
 
 +
<tex>\Uparrow</tex> дисперсия=1
 +
 
 +
[[Изображение:Svr Normal 2.jpg|800px]]
 +
 
 +
<tex>\Uparrow</tex> дисперсия=0.1
 +
 
 +
[[Изображение:Svr Weights Normal.jpg|800px]]
 +
 
 +
<tex>\Uparrow</tex> Зависимость весов соответствующих функций от обратной дисперсии
 +
 
 +
=== Пуассоновское распределение ===
 +
 
 +
[[Изображение:Svr Poisson.png|800px]]
 +
 
 +
<tex>\Uparrow</tex>Пуассоновское распределение с большой дисперсией
 +
 
 +
[[Изображение:Svr Poisson2.png|800px]]
 +
 
 +
<tex>\Uparrow</tex> Пуассоновское распределение с малой дисперсией, получаем почти точное решение
 +
 
 +
[[Изображение:Svr Poisson3.png|800px]]
 +
 
 +
<tex>\Uparrow</tex>Часть предыдущего графика, на которой мы видим, что даже с идеальными данными мы не получим идеальное приближение, т.к. среди прочего минимизируем <tex>(w,w)</tex>. Функционал потерь состоит из суммы двух частей: <tex>\frac{1}{2} (w,w)</tex> и <tex>C\sum_{i=1}^\ell(\xi_i^+ + \xi_i^-)</tex>. Если точки идут довольно ровно (дисперсия мала по сравнению с <tex>\epsilon</tex>), то можно выделить целое семейство функций, которые обращают вторую часть в ноль, но при этом первая часть будет принимать различные значения для различных наборов коэффициентов <tex>w</tex>. Таким образом, мы в качестве решения получим функцию из семества с минимальным <tex>\frac{1}{2} (w,w)</tex>, и она будет отличаться от точного решения.
 +
 
 +
[[Изображение:Weights poisson.png|800px]]
 +
 
 +
<tex>\Uparrow</tex> Зависимость весов соответствующих функций от параметра
 +
 
 +
=== Равномерное распределение ===
 +
 
 +
[[Изображение:Svr Uniformal.png|800px]]
 +
 
 +
<tex>\Uparrow</tex> Работа алгоритма на примере с равномерным шумом. На этом графике шум равномерно распределен на отрезке <tex>[-\frac{1}{2};\frac{1}{2}]</tex>
 +
 
 +
[[Изображение:Svr Weights Uniformal.png|800px]]
 +
 
 +
<tex>\Uparrow</tex> Зависимость весов соответствующих функций от параметра
 +
 
 +
=== Распределение sin(unif) ===
 +
Тест на распределении вида <tex>\frac{sin(unifrnd(-3.1415/2,3.1415/2))}{parameter}</tex>, или же синуса от равномерного распределения.
 +
 
 +
[[Изображение:Svr Sin.png|800px]]
 +
 
 +
<tex>\Uparrow</tex> Если выбрать большую амплитуду(=5), решение может сильно отличаться от верного
 +
 
 +
[[Изображение:Svr Sin2.png|800px]]
 +
 
 +
<tex>\Uparrow</tex> При малых(=0.5) такого не наблюдается.
 +
 
 +
[[Изображение:Svr Weights Sin.png|800px]]
 +
 
 +
<tex>\Uparrow</tex> Зависимость весов соответствующих функций от параметра
 +
 
 +
=== Реальные данные ===
 +
Пример взят из [http://archive.ics.uci.edu/ml/datasets/Auto+MPG Репозитория UCI]. В этом примере рассматриваются автомобили 1970-1973 года выпуска. Строится зависимость мощности автомобиля [л.с.] от веса [кг]
 +
 
 +
[[Изображение:Svr UCI Auto mpg1.png|800px]]
 +
 
 +
<tex>\Uparrow</tex>Пример иллюстрирует, что очень важно правильно выбирать порождающие функции. Хотя потери меньше, чем на следующем графике, такое решение не является достаточно точным.
 +
 
 +
<tex>\Uparrow</tex>Вектор порождающих функций: <tex>f = [x,\ e^{-x},\ sin(x),\ cos(x),\ x^{\frac{1}{2}},\ x^{\frac{3}{2}},\ x^0]</tex>;
 +
 
 +
[[Изображение:Svr UCI Auto mpg2.png|800px]]
 +
 
 +
<tex>\Uparrow</tex>Вектор порождающих функций: <tex>f = [x,\ e^{-x},\ x^2,\ 0*cos(x),\ x^{\frac{1}{2}},\ x^{\frac{3}{2}},\ x^0]</tex>;
 +
 
 +
== Исходный код ==
 +
* Исходный код [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group774/Kornienko2010SVMRegression Matlab]
 +
 
 +
== Смотри также ==
 +
* [[машина опорных векторов]]
 +
* [http://en.wikipedia.org/wiki/Support_vector_machine#Regression Википедия]
 +
* [http://kernelsvm.tripod.com/ tripod.com]
 +
 
 +
== Литература ==
 +
* Alex J. Smola, Bernhard Schölkopf. A tutorial on support vector regression. DOI Bookmark: [http://dx.doi.org/10.1023/B:STCO.0000035301.49549.88 10.1023/B:STCO.0000035301.49549.88]
 +
* Gunn, S., 1998. Support Vector Machines for Classification and Regression. ISIS Technical Report ISIS-1-98. Image Speech & Intelligent Systems Research Group, University of Southampton, U.K.
 +
 
 +
{{ЗаданиеВыполнено|Алексей Корниенко|В.В.Стрижов|28 мая 2010|Korial|Strijov}}
 +
 
 +
[[Категория:Практика и вычислительные эксперименты]]
 +
[[Категория:Классификация]]
 +
[[Категория:Линейные классификаторы]]

Текущая версия

SVM (Support Vector Machine, машина опорных векторов) — это особый класс алгоритмов, который характеризуется использованием ядер, отсутствием локальных минимумов, и используется для решения задач классификации и регрессии. В этой статье рассматривается пример использования метода опорных векторов в задачах регрессии.


Содержание

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

Дано: Обучающая выборка X=\{(x_i,y_i)\}_{i=1}^{\ell}, где x_i-признаковое описание i-го объекта, y_i - характеристика, приписываемая объекту. Функция потерь имеет вид a(x_i)=\mid (w,f(x_i))-w_0-y_i \mid_\epsilon для каждого вектора (x_i,y_i), где \mid z \mid_\epsilon = max(0,\mid z \mid-\epsilon).

Найти: такую функцию f_0, которая описывает зависимость E(y|\mathbf{x})=f_0(\mathbf{x}) наилучшим образом.

Алгоритм

Основная статья: Машина опорных векторов

В этом примере решается задача построения линейной SVM регрессии. Для этого решается прямая задача минимизации функционала потерь, в предположении что решение задается линейной комбинацией неких порождающих функций, из которых можем составить вектор-функцию f(x)=\begin{Vmatrix} f_1(x) \\ f_2(x) \\ \vdots \\ f_k(x) \end{Vmatrix} .

Тогда функционал примет вид:

Q_\epsilon(a,X)=\sum_{i=1}^\ell \mid (w,f(x_i))-w_0-y_i \mid_\epsilon + \tau (w,w)^2 \rightarrow \underset{w,w_0}{min}

В предположении что

f_0(x)=\sum_{i=1}^k w_i f_i(x)

Для этого вводятся обозначение C=\frac{1}{2\tau} и дополнительные переменные \xi_i^+ и \xi_i^-:

\xi_i^+=(a(x_i)-y_i-\epsilon)_+, \xi_i^-=(-a(x_i)+y_i-\epsilon)_-, i=1,...,l.

Геометрический смысл \xi_i^+ и \xi_i^-:

Изображение:GeometricalSenceOfKsi.jpg

Далее решается задача квадратичного программирования:

\begin{cases} \frac{1}{2} (w,w) + C\sum_{i=1}^\ell(\xi_i^+ + \xi_i^-)\rightarrow \underset{w,w_0,\xi_i^+,\xi_i^-}{min}, \\ (w,f(x_i))-w_0 \le y_i + \epsilon + \xi_i^+, & i=1,..,\ell; \\ (w,f(x_i))-w_0 \ge y_i - \epsilon - \xi_i^-, & i=1,..,\ell; \\ \xi_i^- \ge 0, \mbox{ } i=1,..,\ell; \\ \xi_i^+ \ge 0, \mbox{ } i=1,..,\ell; \\ \end{cases}

Эту же задачу можно преобразовать к виду \frac{1}{2}u^T H u + g u\rightarrow \underset{u}{min}, при условии, что A u \le b,\ а также, lb \le u, где u - вектор-столбец, составленный из столбцов w\ , \xi_i^+, \xi_i^-, тоесть, где все переменные объединены в один столбец неизвестных. В таких обозначениях H=diag(1,1,...,1,0,0,...,0),\ g=(0,0,...,0,1,1,...,1), где единиц и нулей в H и g соответственно столько же, сколько порождающих функций, а размерность матрицы H и вектора g равна размерности u.

Теперь построим матрицу А и столбцы b и lb. Преобразуем задачу квадратичного программирования к виду

\begin{cases} \frac{1}{2} (w,w) + C\sum_{i=1}^\ell(\xi_i^+ + \xi_i^-)\rightarrow \underset{w,w_0,\xi_i^+,\xi_i^-}{min}, \\ (w,f(x_i)) - w_0 -\xi_i^+ \le y_i + \epsilon , & i=1,..,\ell; \\ -(w,f(x_i))+ w_0 -\xi_i^- \le -y_i + \epsilon , & i=1,..,\ell; \\ 0 \le \xi_i^-, \mbox{ } i=1,..,\ell; \\ 0 \le \xi_i^+, \mbox{ } i=1,..,\ell; \\ \end{cases}

Получаем, A=\begin{Vmatrix} f^T(\x_1) & -1 & 0 & \cdots & 0 \\ f^T(\x_2) & 0 & -1 & \cdots & 0 \\ \vdots & \vdots &\vdots & \ddots & \vdots \\ f^T(\x_\ell) & 0 & 0 & \vdots & 0 \\ -f^T(\x_1) & 0 & 0 & \vdots & 0 \\ \vdots & \vdots &\vdots & \ddots & \vdots \\ -f^T(\x_\ell) & 0 & 0 & \cdots & -1 \\ \end{Vmatrix},\ b= \begin{Vmatrix} y_1 + \epsilon \\ y_2 + \epsilon \\ \vdots \\ y_\ell + \epsilon \\ -y_1 + \epsilon \\ \vdots \\ -y_\ell + \epsilon \\ \end{Vmatrix},\ lb= \begin{Vmatrix} -\infty \\ -\infty \\ \vdots \\ -\infty \\ 0 \\ \vdots \\ 0 \\ \end{Vmatrix} , и количество минус бесконечностей в lb равно количеству порождающих функций, а количество нулей равно 2\ell.

Таким образом, мы свели задачу к задаче квадратичного программирования.

В нашем примере значения С, \epsilon и порождающие функции задаются экспертом.

Вычислительный эксперимент

Вычислительный эксперимент состоит из трех основных частей:

  • Генерация данных;
  • Работа алгоритма;
  • Визуализация и анализ данных.

Генерация данных

При генерации данных мы выбираем некую линейную комбинацию наших порождающих функций, и добавляем к ней случайный шум. В ходе эксперимента исследуются различные, как дискретные, так и непрерывные шумы. В качестве базовой функции выбрана функция y = 3 + x - 1.5sin(x). А в качестве порождающих функций x,\ e^x,\ sin(x),\ cos(x),\ x^{\frac{1}{2}},\ x^{\frac{3}{2}}, x^0.

Нормальное распределение

\Uparrow дисперсия=1

\Uparrow дисперсия=0.1

\Uparrow Зависимость весов соответствующих функций от обратной дисперсии

Пуассоновское распределение

\UparrowПуассоновское распределение с большой дисперсией

\Uparrow Пуассоновское распределение с малой дисперсией, получаем почти точное решение

\UparrowЧасть предыдущего графика, на которой мы видим, что даже с идеальными данными мы не получим идеальное приближение, т.к. среди прочего минимизируем (w,w). Функционал потерь состоит из суммы двух частей: \frac{1}{2} (w,w) и C\sum_{i=1}^\ell(\xi_i^+ + \xi_i^-). Если точки идут довольно ровно (дисперсия мала по сравнению с \epsilon), то можно выделить целое семейство функций, которые обращают вторую часть в ноль, но при этом первая часть будет принимать различные значения для различных наборов коэффициентов w. Таким образом, мы в качестве решения получим функцию из семества с минимальным \frac{1}{2} (w,w), и она будет отличаться от точного решения.

\Uparrow Зависимость весов соответствующих функций от параметра

Равномерное распределение

\Uparrow Работа алгоритма на примере с равномерным шумом. На этом графике шум равномерно распределен на отрезке [-\frac{1}{2};\frac{1}{2}]

\Uparrow Зависимость весов соответствующих функций от параметра

Распределение sin(unif)

Тест на распределении вида \frac{sin(unifrnd(-3.1415/2,3.1415/2))}{parameter}, или же синуса от равномерного распределения.

\Uparrow Если выбрать большую амплитуду(=5), решение может сильно отличаться от верного

\Uparrow При малых(=0.5) такого не наблюдается.

\Uparrow Зависимость весов соответствующих функций от параметра

Реальные данные

Пример взят из Репозитория UCI. В этом примере рассматриваются автомобили 1970-1973 года выпуска. Строится зависимость мощности автомобиля [л.с.] от веса [кг]

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

\UparrowВектор порождающих функций: f = [x,\ e^{-x},\ sin(x),\ cos(x),\ x^{\frac{1}{2}},\ x^{\frac{3}{2}},\ x^0];

\UparrowВектор порождающих функций: f = [x,\ e^{-x},\ x^2,\ 0*cos(x),\ x^{\frac{1}{2}},\ x^{\frac{3}{2}},\ x^0];

Исходный код

  • Исходный код Matlab

Смотри также

Литература

  • Alex J. Smola, Bernhard Schölkopf. A tutorial on support vector regression. DOI Bookmark: 10.1023/B:STCO.0000035301.49549.88
  • Gunn, S., 1998. Support Vector Machines for Classification and Regression. ISIS Technical Report ISIS-1-98. Image Speech & Intelligent Systems Research Group, University of Southampton, U.K.


Данная статья была создана в рамках учебного задания.
Студент: Алексей Корниенко
Преподаватель: В.В.Стрижов
Срок: 28 мая 2010


В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта MachineLearning.ru.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Источник — «http://machinelearning.ru/wiki/index.php?title=SVM_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»
Личные инструменты