Ядерный метод

Ядерные методы в машинном обучении — это класс алгоритмов распознавания образов, наиболее известным представителем которого является метод опорных векторов (МОВ, англ. 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}$ являются весами тренировочных примеров, как определено алгоритмом обучения;
• Функция sgn определяет, будет предсказанная классификация положительной или отрицательной.

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

Математика: ядерный трюк

МОВ с ядром, заданной функцией φ((a, b))=(a, b, a² + b²), а тогда K(x, y)=x•y + x² y². Тренировочные точки показаны в 3-мерном пространстве, где можно легко найти разделяющую гиперплоскость

Ядерный трюк избегает явного отображения, которое нужно для получения линейного обучающего алгоритма для нелинейной функции или границы решений. Для всех $\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})$, должна быть положительно полуопределена. Эмпирически, для эвристики машинного обучения, выбор функции $k$, которая не удовлетворяет условию Мерсера, может оставаться оправданным, если $k$, по меньшей мере, аппроксимирует интуитивную идею похожести. Независимо от того, является ли $k$ ядром Мерсера, о $k$ могут продолжать говорить как о «ядре».

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

Приложения

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

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

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

Литература

Ссылка

• Kernel-Machines Org — community website
• www.support-vector-machines.org (Literature, Review, Software, Links related to Support Vector Machines - Academic Site)
• onlineprediction.net Kernel Methods Article