Перспективы регуляризации машин опорных векторов - Regularization perspectives on support-vector machines

Перспективы регуляризации машин опорных векторов предоставить способ интерпретации машины опорных векторов (SVM) в контексте других алгоритмов машинного обучения. Алгоритмы SVM классифицируют многомерный данные, с целью подгонки Обучающий набор данные хорошо, но также избегая переоснащение, так что решение обобщает к новым точкам данных. Регуляризация алгоритмы также стремятся соответствовать данным обучающего набора и избегать переобучения. Они делают это, выбирая функцию подгонки, которая имеет низкую ошибку на обучающем наборе, но также не слишком сложна, где сложные функции - это функции с высоким нормы в некоторых функциональное пространство. Конкретно, Тихоновская регуляризация алгоритмы выбирают функцию, которая минимизирует сумму ошибки обучающего набора и нормы функции. Ошибка обучающего набора может быть вычислена с различными функции потерь. Например, регуляризованный метод наименьших квадратов является частным случаем регуляризации Тихонова с использованием квадрат ошибки потери как функция потерь.^[1]

Перспективы регуляризации на машинах опорных векторов интерпретируют SVM как частный случай регуляризации Тихонова, в частности регуляризации Тихонова с потеря петли для функции потерь. Это обеспечивает теоретическую основу для анализа алгоритмов SVM и сравнения их с другими алгоритмами с теми же целями: обобщать без переоснащение. SVM была впервые предложена в 1995 г. Коринна Кортес и Владимир Вапник, и геометрически оформленный как метод нахождения гиперплоскости что может разделить многомерный данные на две категории.^[2] Эта традиционная геометрическая интерпретация SVM дает полезную интуицию о том, как работают SVM, но ее трудно соотнести с другими машинное обучение техники, позволяющие избежать переобучения, например регуляризация, ранняя остановка, редкость и Байесовский вывод. Однако, как только было обнаружено, что SVM также является особый случай теории регуляризации Тихонова, перспективы регуляризации SVM обеспечили теорию, необходимую для того, чтобы вписать SVM в более широкий класс алгоритмов.^[1][3][4] Это позволило провести подробные сравнения между SVM и другими формами регуляризации Тихонова и теоретически обосновать, почему полезно использовать функцию потерь SVM, потерю петли.^[5]

Теоретические основы

в теория статистического обучения рамки, алгоритм это стратегия выбора функция ${\displaystyle f\colon \mathbf {X} \to \mathbf {Y} }$ учитывая тренировочный набор ${\displaystyle S=\{(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\}}$ входов ${\displaystyle x_{i}}$ и их этикетки ${\displaystyle y_{i}}$ (этикетки обычно ${\displaystyle \pm 1}$). Регуляризация стратегии избегать переоснащение выбрав функцию, которая соответствует данным, но не слишком сложна. Конкретно:

${\displaystyle f={\underset {f\in {\mathcal {H}}}{\operatorname {argmin} }}\left\{{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},f(x_{i}))+\lambda \|f\|_{\mathcal {H}}^{2}\right\},}$

куда ${\displaystyle {\mathcal {H}}}$ это пространство гипотез^[6] функций, ${\displaystyle V\colon \mathbf {Y} \times \mathbf {Y} \to \mathbb {R} }$ - функция потерь, ${\displaystyle \|\cdot \|_{\mathcal {H}}}$ это норма на пространстве гипотез функций, и ${\displaystyle \lambda \in \mathbb {R} }$ это параметр регуляризации.^[7]

Когда ${\displaystyle {\mathcal {H}}}$ это воспроизводящее ядро ​​гильбертова пространства, существует функция ядра ${\displaystyle K\colon \mathbf {X} \times \mathbf {X} \to \mathbb {R} }$ это можно записать как ${\displaystyle n\times n}$ симметричный положительно определенный матрица ${\displaystyle \mathbf {K} }$. Посредством теорема о представителе,^[8]

${\displaystyle f(x_{i})=\sum _{j=1}^{n}c_{j}\mathbf {K} _{ij},{\text{ and }}\|f\|_{\mathcal {H}}^{2}=\langle f,f\rangle _{\mathcal {H}}=\sum _{i=1}^{n}\sum _{j=1}^{n}c_{i}c_{j}K(x_{i},x_{j})=c^{T}\mathbf {K} c.}$

Особые свойства потери петли

Самая простая и интуитивно понятная функция потерь для категоризации - это потеря неправильной классификации, или потеря 0–1, которая равна 0, если ${\displaystyle f(x_{i})=y_{i}}$ и 1, если ${\displaystyle f(x_{i})\neq y_{i}}$, т.е. Ступенчатая функция Хевисайда на ${\displaystyle -y_{i}f(x_{i})}$. Однако эта функция потерь не является выпуклый, что затрудняет вычислительную минимизацию задачи регуляризации. Поэтому мы ищем выпуклые заменители потери 0–1. Потеря шарнира, ${\displaystyle V{\big (}y_{i},f(x_{i}){\big )}={\big (}1-yf(x){\big )}_{+}}$, куда ${\displaystyle (s)_{+}=\max(s,0)}$, обеспечивает такую выпуклая релаксация. На самом деле потеря петель - это самый плотный выпуклый верхняя граница к функции потерь ошибочной классификации 0–1,^[4] и с бесконечными данными возвращает Байесовский -Оптимальное решение:^[5][9]

${\displaystyle f_{b}(x)={\begin{cases}1,&p(1\mid x)>p(-1\mid x),\\-1,&p(1\mid x)<p(-1\mid x).\end{cases}}}$

Вывод

Можно показать, что проблема регуляризации Тихонова эквивалентна традиционным формулировкам SVM, выражая ее в терминах потерь на шарнирах.^[10] С потерей шарнира

${\displaystyle V{\big (}y_{i},f(x_{i}){\big )}={\big (}1-yf(x){\big )}_{+},}$

куда ${\displaystyle (s)_{+}=\max(s,0)}$, проблема регуляризации принимает вид

${\displaystyle f={\underset {f\in {\mathcal {H}}}{\operatorname {argmin} }}\left\{{\frac {1}{n}}\sum _{i=1}^{n}{\big (}1-yf(x){\big )}_{+}+\lambda \|f\|_{\mathcal {H}}^{2}\right\}.}$

Умножение на ${\displaystyle 1/(2\lambda )}$ дает

${\displaystyle f={\underset {f\in {\mathcal {H}}}{\operatorname {argmin} }}\left\{C\sum _{i=1}^{n}{\big (}1-yf(x){\big )}_{+}+{\frac {1}{2}}\|f\|_{\mathcal {H}}^{2}\right\}}$

с ${\displaystyle C=1/(2\lambda n)}$, что эквивалентно стандартной задаче минимизации SVM.

Примечания и ссылки

1. Росаско, Лоренцо. "Регуляризованные машины наименьших квадратов и опорные векторы" (PDF).
2. Кортес, Коринна; Владимир Вапник (1995). "Сети опорных векторов". Машинное обучение. 20 (3): 273–297. Дои:10.1007 / BF00994018.
3. Рифкин, Райан (2002). Все старое снова новое: свежий взгляд на исторические подходы в машинном обучении (PDF). MIT (кандидатская диссертация).
4. Ли, Юнкён; Вахба, Грейс (2012). «Машины с мультикатегориальными опорными векторами». Журнал Американской статистической ассоциации. 99 (465): 67–81. Дои:10.1198/016214504000000098.
5. Росаско Л., Де Вито Э., Капоннетто А., Пиана М., Верри А. (май 2004 г.). «Все ли функции потерь одинаковы». Нейронные вычисления. 5. 16 (5): 1063–1076. CiteSeerX  10.1.1.109.6786. Дои:10.1162/089976604773135104. PMID  15070510.
6. Пространство гипотез - это набор функций, используемых для моделирования данных в задаче машинного обучения. Каждая функция соответствует гипотезе о структуре данных. Обычно функции в пространстве гипотез образуют Гильбертово пространство функций с нормой, образованной из функции потерь.
7. Подробнее о выборе параметра см., Например, Вахба, Грейс; Юнхуа Ван (1990). «Когда является оптимальным параметром регуляризации, нечувствительным к выбору функции потерь». Коммуникации в статистике - теория и методы. 19 (5): 1685–1700. Дои:10.1080/03610929008830285.
8. Видеть Шолкопф, Бернхард; Ральф Хербрих; Алекс Смола (2001). Обобщенная теорема о представителях. Теория вычислительного обучения: конспект лекций по информатике. Конспект лекций по информатике. 2111. С. 416–426. CiteSeerX  10.1.1.42.8617. Дои:10.1007/3-540-44581-1_27. ISBN  978-3-540-42343-0.
9. Лин, Йи (июль 2002 г.). «Машины опорных векторов и правило Байеса в классификации» (PDF). Интеллектуальный анализ данных и обнаружение знаний. 6 (3): 259–275. Дои:10.1023 / А: 1015469627679.
10. Для подробного вывода см. Рифкин, Райан (2002). Все старое снова новое: свежий взгляд на исторические подходы в машинном обучении (PDF). MIT (кандидатская диссертация).

• Евгений, Теодорос; Массимилиано Понтиль; Томазо Поджио (2000). «Сети регуляризации и машины опорных векторов» (PDF). Достижения в вычислительной математике. 13 (1): 1–50. Дои:10.1023 / А: 1018946025316.
• Иоахим, Торстен. "SVMlight". Архивировано из оригинал на 2015-04-19. Получено 2012-05-18.
• Вапник, Владимир (1999). Природа статистической теории обучения. Нью-Йорк: Springer-Verlag. ISBN  978-0-387-98780-4.