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

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

(Различия между версиями)

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

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^-$ :

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

$\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://www.recognition.su/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»

Категории: Практика и вычислительные эксперименты | Классификация | Линейные классификаторы

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

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

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

Содержание

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

Алгоритм

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

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

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

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

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

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

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

Исходный код

Смотри также

Литература

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты

@@ Строка 1: / Строка 1: @@
-'''SVM (Support Vector Machine, [[машина опорных векторов]])''' — это особый класс алгоритмов, который характеризуется использованием ядер, отсутствием локальных минимумов, и&nbsp;т.&nbsp;д.
+'''SVM (Support Vector Machine, [[машина опорных векторов]])''' — это особый класс алгоритмов, который характеризуется использованием ядер, отсутствием локальных минимумов, и используется для решения задач классификации и регрессии. В этой статье рассматривается пример использования метода опорных векторов в задачах регрессии.
-{{Задание|Алексей Корниенко|В.В.Стрижов|28 мая 2010}}
-[[Категория:Учебные материалы]]
+== Постановка задачи ==
+'''Дано:''' Обучающая выборка <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; \\
+\le  \xi_i^-, \mbox{   } i=1,..,\ell; \\
+\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 \\
+\\
+\vdots  \\
+\\
+\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}}
+[[Категория:Практика и вычислительные эксперименты]]
 [[Категория:Классификация]]
 [[Категория:Линейные классификаторы]]