Перспективы регуляризации машин опорных векторов

В рамках математического анализа перспективы регуляризации машин опорных векторов обеспечивают способ интерпретации машин опорных векторов (SVM) в контексте других алгоритмов машинного обучения на основе регуляризации. Алгоритмы SVM классифицируют двоичные данные с целью подбора данных обучающего набора таким образом, чтобы минимизировать среднее значение функции шарнирных потерь и нормы L2 изученных весов. Эта стратегия позволяет избежать переобучения посредством регуляризации Тихонова и в смысле нормы L2, а также соответствует минимизации смещения и дисперсии нашей оценки весов. Оценщики с более низкой среднеквадратической ошибкой лучше предсказывают или лучше обобщают, когда им предоставляются невидимые данные.

В частности, алгоритмы регуляризации Тихонова создают границу решения, которая минимизирует среднюю ошибку обучающего набора и ограничивает границу решения, чтобы она не была чрезмерно сложной или не соответствовала обучающим данным с помощью нормы L2 весового члена. Ошибки обучения и тестового набора можно измерить без предвзятости и справедливым способом, используя точность, прецизионность, Auc-Roc, точность отзыва и другие показатели.

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

Теоретическая основа

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

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\},

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

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

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

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] С потерей шарнира

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

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

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\}.

Умножение на $1/(2\lambda )$ урожайность

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\}

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

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

^ Кортес, Коринна; Владимир Вапник (1995). «Сети опорных векторов» . Машинное обучение . 20 (3): 273–297. дои : 10.1007/BF00994018 .
^ Росаско, Лоренцо. «Регуляризованные машины наименьших квадратов и опорных векторов» (PDF) .
^ Рифкин, Райан (2002). Все старое снова стало новым: свежий взгляд на исторические подходы в машинном обучении (PDF) . MIT (кандидатская диссертация).
^ Jump up to: ^а ^б Ли, Юнкён ; Вахба, Грейс (2012). «Многокатегорийные машины опорных векторов». Журнал Американской статистической ассоциации . 99 (465): 67–81. CiteSeerX 10.1.1.22.1879 . дои : 10.1198/016214504000000098 . S2CID 261035640 .
^ Jump up to: ^а ^б Росаско Л.; Де Вито Э.; Капоннетто А.; Пиана М.; Верри А. (май 2004 г.). «Все ли функции потерь одинаковы». Нейронные вычисления . 5. 16 (5): 1063–1076. CiteSeerX 10.1.1.109.6786 . дои : 10.1162/089976604773135104 . ПМИД 15070510 . S2CID 11845688 .
^ Пространство гипотез — это набор функций, используемых для моделирования данных в задаче машинного обучения. Каждая функция соответствует гипотезе о структуре данных. Обычно функции в пространстве гипотез образуют гильбертово пространство функций с нормой, образованной из функции потерь.
^ Подробнее о выборе параметра см., например, Вахба, Грейс; Юнхуа Ван (1990). «Когда оптимальный параметр регуляризации нечувствителен к выбору функции потерь». Коммуникации в статистике – теория и методы . 19 (5): 1685–1700. дои : 10.1080/03610929008830285 .
^ Шёлкопф, Бернхард; Хербрих, Ральф; Смола, Александр Дж. (2001). «Обобщенная теорема о представителе». В Хелмбольде, Дэвид П.; Уильямсон, Роберт С. (ред.). Теория вычислительного обучения, 14-я ежегодная конференция по теории вычислительного обучения, COLT 2001 и 5-я Европейская конференция по теории вычислительного обучения, EuroCOLT 2001, Амстердам, Нидерланды, 16–19 июля 2001 г., Труды . Конспекты лекций по информатике. Том. 2111. Спрингер. стр. 416–426. дои : 10.1007/3-540-44581-1_27 .
^ Линь, Йи (июль 2002 г.). «Машины опорных векторов и правило Байеса в классификации» (PDF) . Интеллектуальный анализ данных и обнаружение знаний . 6 (3): 259–275. дои : 10.1023/А:1015469627679 . S2CID 24759201 .
^ Подробный вывод см. Рифкин, Райан (2002). Все старое снова стало новым: свежий взгляд на исторические подходы в машинном обучении (PDF) . MIT (кандидатская диссертация).

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

[1] Кортес, Коринна; Владимир Вапник (1995). «Сети опорных векторов» . Машинное обучение . 20 (3): 273–297. дои : 10.1007/BF00994018 .

[rosasco1-2] Росаско, Лоренцо. «Регуляризованные машины наименьших квадратов и опорных векторов» (PDF) .

[3] Рифкин, Райан (2002). Все старое снова стало новым: свежий взгляд на исторические подходы в машинном обучении (PDF) . MIT (кандидатская диссертация).

[Lee_2012_67–81-4] Jump up to: ^а ^б Ли, Юнкён ; Вахба, Грейс (2012). «Многокатегорийные машины опорных векторов». Журнал Американской статистической ассоциации . 99 (465): 67–81. CiteSeerX 10.1.1.22.1879 . дои : 10.1198/016214504000000098 . S2CID 261035640 .

[Rosasco_2004_1063–1076-5] Jump up to: ^а ^б Росаско Л.; Де Вито Э.; Капоннетто А.; Пиана М.; Верри А. (май 2004 г.). «Все ли функции потерь одинаковы». Нейронные вычисления . 5. 16 (5): 1063–1076. CiteSeerX 10.1.1.109.6786 . дои : 10.1162/089976604773135104 . ПМИД 15070510 . S2CID 11845688 .

[6] Пространство гипотез — это набор функций, используемых для моделирования данных в задаче машинного обучения. Каждая функция соответствует гипотезе о структуре данных. Обычно функции в пространстве гипотез образуют гильбертово пространство функций с нормой, образованной из функции потерь.

[7] Подробнее о выборе параметра см., например, Вахба, Грейс; Юнхуа Ван (1990). «Когда оптимальный параметр регуляризации нечувствителен к выбору функции потерь». Коммуникации в статистике – теория и методы . 19 (5): 1685–1700. дои : 10.1080/03610929008830285 .

[8] Шёлкопф, Бернхард; Хербрих, Ральф; Смола, Александр Дж. (2001). «Обобщенная теорема о представителе». В Хелмбольде, Дэвид П.; Уильямсон, Роберт С. (ред.). Теория вычислительного обучения, 14-я ежегодная конференция по теории вычислительного обучения, COLT 2001 и 5-я Европейская конференция по теории вычислительного обучения, EuroCOLT 2001, Амстердам, Нидерланды, 16–19 июля 2001 г., Труды . Конспекты лекций по информатике. Том. 2111. Спрингер. стр. 416–426. дои : 10.1007/3-540-44581-1_27 .

[9] Линь, Йи (июль 2002 г.). «Машины опорных векторов и правило Байеса в классификации» (PDF) . Интеллектуальный анализ данных и обнаружение знаний . 6 (3): 259–275. дои : 10.1023/А:1015469627679 . S2CID 24759201 .

[10] Подробный вывод см. Рифкин, Райан (2002). Все старое снова стало новым: свежий взгляд на исторические подходы в машинном обучении (PDF) . MIT (кандидатская диссертация).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]