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»

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

@@ Строка 35: / Строка 35: @@
 <tex>
 \begin{cases}
-\frac{1}{2} (w,w)^2 + C\sum_{i=1}^\ell(\xi_i^+ + \xi_i^-)\rightarrow \underset{w,w_0,\xi_i^+,\xi_i^-}{min},  \\
+\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; \\
@@ Строка 43: / Строка 43: @@
 </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>\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>. Преобразуем задачу квадратичного программирования к виду
@@ Строка 49: / Строка 49: @@
 <tex>
 \begin{cases}
-\frac{1}{2} (w,w)^2 + C\sum_{i=1}^\ell(\xi_i^+ + \xi_i^-)\rightarrow \underset{w,w_0,\xi_i^+,\xi_i^-}{min},  \\
+\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; \\
@@ Строка 94: / Строка 94: @@
 == Вычислительный эксперимент ==
-Вычислительный эксеримент состоит из трех основных частей:
+Вычислительный эксперимент состоит из трех основных частей:
 * Генерация данных;
 * Работа алгоритма;
@@ Строка 101: / Строка 101: @@
 === Генерация данных ===
-При генерации данных мы выбираем некую линейную комбинацию наших порождающих функций, и добаляем к ней случайный шум. В ходе эксперимента исследуются различные, как дискретные, так и непрерывные шумы. В качестве базовой функции выбрана функция y = 3 + x - 1.5*sin(x). А в качестве порождающих функций x, exp(x), sin(x), cos(x), x^0.5, x^1.5, x^0.
+При генерации данных мы выбираем некую линейную комбинацию наших порождающих функций, и добавляем к ней случайный шум. В ходе эксперимента исследуются различные, как дискретные, так и непрерывные шумы. В качестве базовой функции выбрана функция <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>.
 === Нормальное распределение ===
@@ Строка 129: / Строка 129: @@
 [[Изображение:Svr Poisson3.png|800px]]
-<tex>\Uparrow</tex>Часть предыдущего графика, на которой мы видим, что даже с иделаьными данными мы не получим идеальное приближение, т.к. среди прочего минимизируем <tex>(w,w)</tex>
+<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]]
@@ Строка 146: / Строка 146: @@
 === Распределение sin(unif) ===
-Тест на распределении вида sin(unifrnd(-3.1415/2,3.1415/2))/parameter, тоесть синуса от равномерного распределения.
+Тест на распределении вида <tex>\frac{sin(unifrnd(-3.1415/2,3.1415/2))}{parameter}</tex>, или же синуса от равномерного распределения.
 [[Изображение:Svr Sin.png|800px]]
@@ Строка 161: / Строка 161: @@
 === Реальные данные ===
-Пример взят из [http://archive.ics.uci.edu/ml/datasets/Auto+MPG Репозитория UCI]. В этом примере рассматриваются автомобили 1970-1973 года выпуска. Строится зависимость мощьности автомобиля [л.с.] от веса [кг]
+Пример взят из [http://archive.ics.uci.edu/ml/datasets/Auto+MPG Репозитория UCI]. В этом примере рассматриваются автомобили 1970-1973 года выпуска. Строится зависимость мощности автомобиля [л.с.] от веса [кг]
 [[Изображение:Svr UCI Auto mpg1.png|800px]]
@@ Строка 167: / Строка 167: @@
 <tex>\Uparrow</tex>Пример иллюстрирует, что очень важно правильно выбирать порождающие функции. Хотя потери меньше, чем на следующем графике, такое решение не является достаточно точным.
-<tex>\Uparrow</tex>Вектор порождающих функций: f = [x, exp(-x), sin(x), cos(x), sqrt(x), diag(x)*sqrt(x), x.^0];
+<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>Вектор порождающих функций: f = [x, exp(-x), diag(x)*(x), 0*cos(x), sqrt(x), diag(x)*sqrt(x), x.^0];
+<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/SVM_regression Matlab]
+* Исходный код [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group774/Kornienko2010SVMRegression Matlab]
 == Смотри также ==
@@ Строка 183: / Строка 183: @@
 == Литература ==
 * 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}}
+{{ЗаданиеВыполнено|Алексей Корниенко|В.В.Стрижов|28 мая 2010|Korial|Strijov}}
-[[Категория:Учебные материалы]]
+[[Категория:Практика и вычислительные эксперименты]]
 [[Категория:Классификация]]
 [[Категория:Линейные классификаторы]]

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

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

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

Содержание

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

Алгоритм

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

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

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

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

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

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

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

Исходный код

Смотри также

Литература

Просмотры

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

Навигация

Поиск

Инструменты