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

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

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

Версия 08:06, 6 мая 2010

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://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; \\
@@ Строка 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; \\
@@ Строка 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]]

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

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

Версия 08:06, 6 мая 2010

Содержание

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

Алгоритм

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

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

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

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

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

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

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

Исходный код

Смотри также

Литература

Просмотры

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

Навигация

Поиск

Инструменты