Метод ядра

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

Методы ядра обязаны своим названием использованию функций ядра , которые позволяют им работать в многомерном, неявном пространстве признаков, даже не вычисляя координаты данных в этом пространстве, а, скорее, просто вычисляя продукты между изображениями внутренние все пары данных в пространстве признаков. Эта операция часто вычислительно дешевле, чем явное вычисление координат. Этот подход называется « трюком ядра ». Функции ядра были введены для данных последовательности, графиков , текста, изображений, а также векторов.

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

Большинство алгоритмов ядра основаны на выпуклой оптимизации или собственных задачах и статистически обоснованы. Обычно их статистические свойства анализируются с помощью статистической теории обучения (например, с использованием сложности Радемахера ).

Мотивация

Методы ядра можно рассматривать как методы обучения на основе экземпляров : вместо изучения некоторого фиксированного набора параметров, соответствующих характеристикам их входных данных, они вместо этого «запоминают» $i$-й обучающий пример $(\mathbf {x} _{i},y_{i})$ и узнаем для него соответствующий вес $w_{i}$. Прогноз для немаркированных входных данных, т. е. тех, которые не входят в обучающий набор, обрабатывается применением функции подобия. $k$, называемое ядром , между немаркированным входом $\mathbf {x'}$ и каждый из входных данных обучения $\mathbf {x} _{i}$. Например, ядерный двоичный классификатор обычно вычисляет взвешенную сумму сходств.

$${\hat {y}}=\operatorname {sgn} \sum _{i=1}^{n}w_{i}y_{i}k(\mathbf {x} _{i},\mathbf {x'} ),$$

где

• ${\hat {y}}\in \{-1,+1\}$ - это прогнозируемая метка ядерного двоичного классификатора для немаркированного входа. $\mathbf {x'}$ чей скрытый истинный ярлык $y$ представляет интерес;
• $k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R}$ это функция ядра, которая измеряет сходство между любой парой входных данных $\mathbf {x} ,\mathbf {x'} \in {\mathcal {X}}$;
• сумма варьируется по n помеченным примерам $\{(\mathbf {x} _{i},y_{i})\}_{i=1}^{n}$ в обучающем наборе классификатора, с $y_{i}\in \{-1,+1\}$;
• тот $w_{i}\in \mathbb {R}$ – веса обучающих примеров, определенные алгоритмом обучения;
• знаковая функция $\operatorname {sgn}$ определяет, будет ли прогнозируемая классификация ${\hat {y}}$ выходит положительным или отрицательным.

Ядерные классификаторы были описаны еще в 1960-х годах, с изобретением ядерного перцептрона . Они приобрели большую известность благодаря популярности машины опорных векторов (SVM) в 1990-х годах, когда выяснилось, что SVM конкурирует с нейронными сетями в таких задачах, как распознавание рукописного текста .

Математика: трюк с ядром

SVM с ядром, заданным $\varphi ((a,b))=(a,b,a^{2}+b^{2})$ и таким образом $k(\mathbf {x} ,\mathbf {y} )=\mathbf {x} \cdot \mathbf {y} +\left\|\mathbf {x} \right\|^{2}\left\|\mathbf {y} \right\|^{2}$. Точки обучения отображаются в трехмерном пространстве, где можно легко найти разделяющую гиперплоскость.

Трюк с ядром позволяет избежать явного отображения, которое необходимо, чтобы заставить алгоритмы линейного обучения изучать нелинейную функцию или границу решения . Для всех $\mathbf {x}$ и $\mathbf {x'}$ во входном пространстве ${\mathcal {X}}$, определенные функции $k(\mathbf {x} ,\mathbf {x'} )$ может быть выражено как внутренний продукт в другом пространстве ${\mathcal {V}}$. Функция $k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R}$ часто называют ядром или функцией ядра . Слово «ядро» используется в математике для обозначения весовой функции для взвешенной суммы или интеграла .

Некоторые задачи машинного обучения имеют больше структуры, чем произвольная весовая функция. $k$. Вычисления становятся намного проще, если ядро ​​можно записать в виде «карты функций». $\varphi \colon {\mathcal {X}}\to {\mathcal {V}}$ который удовлетворяет

$$k(\mathbf {x} ,\mathbf {x'} )=\langle \varphi (\mathbf {x} ),\varphi (\mathbf {x'} )\rangle _{\mathcal {V}}.$$

Ключевое ограничение состоит в том, что $\langle \cdot ,\cdot \rangle _{\mathcal {V}}$ должен быть правильным внутренним продуктом.С другой стороны, явное представление для $\varphi$ не обязательно, пока ${\mathcal {V}}$ — это внутреннее пространство продукта . Альтернатива следует из теоремы Мерсера : неявно определенная функция $\varphi$ существует всякий раз, когда пространство ${\mathcal {X}}$ может быть оснащен подходящей мерой, обеспечивающей функцию $k$ удовлетворяет условию Мерсера .

Теорема Мерсера похожа на обобщение результата линейной алгебры, которое сопоставляет скалярное произведение любой положительно определенной матрице . Фактически, условие Мерсера можно свести к этому более простому случаю. Если мы выберем в качестве меры счетную меру $\mu (T)=|T|$ для всех $T\subset X$, который подсчитывает количество точек внутри набора $T$, то интеграл в теореме Мерсера сводится к суммированию

$$\sum _{i=1}^{n}\sum _{j=1}^{n}k(\mathbf {x} _{i},\mathbf {x} _{j})c_{i}c_{j}\geq 0.$$

Если это суммирование справедливо для всех конечных последовательностей точек $(\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n})$ в ${\mathcal {X}}$ и все варианты $n$ действительные коэффициенты $(c_{1},\dots ,c_{n})$ (ср. положительно определенное ядро ), то функция $k$ удовлетворяет условию Мерсера.

Некоторые алгоритмы, зависящие от произвольных отношений в собственном пространстве ${\mathcal {X}}$ на самом деле имело бы линейную интерпретацию в другом контексте: в пространстве диапазонов $\varphi$. Линейная интерпретация дает нам представление об алгоритме. Кроме того, часто нет необходимости вычислять $\varphi$ непосредственно во время вычислений, как в случае с машинами опорных векторов . Некоторые называют это сокращение времени работы основным преимуществом. Исследователи также используют его для обоснования значений и свойств существующих алгоритмов.

Теоретически матрица Грама $\mathbf {K} \in \mathbb {R} ^{n\times n}$ относительно $\{\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n}\}$ (иногда также называемая «матрицей ядра» ), где $K_{ij}=k(\mathbf {x} _{i},\mathbf {x} _{j})$, должен быть положительно полуопределенным (PSD) . Эмпирически для эвристики машинного обучения выбор функции $k$ которые не удовлетворяют условию Мерсера, все равно могут работать разумно, если $k$ по крайней мере, приближается к интуитивному представлению о сходстве. Независимо от того, $k$ это ядро ​​Мерсера, $k$ все еще может называться «ядром».

Если функция ядра $k$ также является ковариационной функцией , используемой в гауссовских процессах , то матрица Грама $\mathbf {K}$ также можно назвать ковариационной матрицей .

Приложения

Области применения ядерных методов разнообразны и включают в себя геостатистику , кригинг , обратное дистанционное взвешивание , 3D реконструкция , биоинформатика , хемоинформатика , извлечение информации и распознавание рукописного текста .

Популярные ядра

• Ядро Фишера
• Ядра графа
• Ядро более гладкое
• Полиномиальное ядро
• Ядро радиальной базисной функции (RBF)
• Строковые ядра
• Нейронное касательное ядро
• Ядро гауссовского процесса нейронной сети (NNGP)

См. также

• Методы ядра для векторного вывода
• Оценка плотности ядра
• Представление теоремы
• Обучение по сходству
• Теорема Ковера

Дальнейшее чтение

• Шоу-Тейлор, Дж .; Кристианини, Н. (2004). Ядерные методы анализа закономерностей . Издательство Кембриджского университета.
• Лю, В.; Принсипи, Дж.; Хайкин, С. (2010). Адаптивная фильтрация ядра: подробное введение . Уайли. ISBN  9781118211212 .
• Шёлкопф, Б .; Смола, Эй Джей; Бах, Ф. (2018). Обучение с помощью ядер: машины опорных векторов, регуляризация, оптимизация и многое другое . МТИ Пресс. ISBN  978-0-262-53657-8 .

Внешние ссылки

• Kernel-Machines Org — веб-сайт сообщества
• Статья на сайте onlineprediction.net о методах ядра