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

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

Ядерные методы получили своё название из-за использования Шаблон:Нп5, которые позволяют им оперировать в неявном пространстве признаков высокой размерности без вычисления координат данных в пространстве, просто вычисляя скалярные произведения между образами всех пар данных в пространстве признаков. Эта операция часто вычислительно дешевле явных вычислений координат. Этот подход называется «ядерным трюком»Шаблон:Sfn. Ядерные функции были введены для последовательных данных, Шаблон:Нп5, текстов, изображений, а также для векторов.

Среди алгоритмов, способных работать с ядрами, находятся Шаблон:Нп5, методы опорных векторов, гауссовские процессы, метод главных компонент (МГК, Шаблон:Lang-en), канонический корреляционный анализ, гребневая регрессия, спектральная кластеризация, линейные адаптивные фильтры и многие другие. Любая Шаблон:Нп5 может быть переведена в нелинейную модель путём применения к модели ядерного трюка, заменив её признаки (предсказатели) ядерной функцией.

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

Причины возникновения и неформальное объяснение

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

\hat{y} = sgn \sum_{i = 1}^{n} w_{i} y_{i} k (𝐱_{i}, 𝐱^{'})

,

где

$\hat{y} \in {- 1, + 1}$ является ядерным бинарным классификатором предсказанной пометки для непомеченного входа $𝐱^{'}$ , скрытая верная пометка которого $y$ нужна;
$k : 𝒳 \times 𝒳 \to ℝ$ является ядерной функцией, которая измеряет схожесть пары входов $𝐱, 𝐱^{'} \in 𝒳$ ;
сумма пробегает по всем Шаблон:Mvar помеченным примерам ${(𝐱_{i}, y_{i})}_{i = 1}^{n}$ в тренировочном наборе классификатора с $y_{i} \in {- 1, + 1}$ ;
$w_{i} \in ℝ$ являются весами тренировочных примеров, как определено алгоритмом обучения;
Функция sgn определяет, будет предсказанная классификация положительной или отрицательной.

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

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

Ядерный трюк избегает явного отображения, которое нужно для получения линейного обучающего алгоритма для нелинейной функции или Шаблон:Нп5. Для всех $𝐱$ и $𝐱^{'}$ во входном пространстве $𝒳$ некоторые функции $k (𝐱, 𝐱^{'})$ могут быть представлены как скалярное произведение в другом пространстве $𝒱$ . Функцию $k : 𝒳 \times 𝒳 \to ℝ$ часто называют ядром или ядерной функцией. Слово «ядро» используется в математике для обозначения весовой функции или интеграла.

Некоторые задачи машинного обучения имеют дополнительную структуру, а не просто весовую функцию $k$ . Вычисления будут много проще, если ядро можно записать в виде "отображения признаков" $φ : 𝒳 \to 𝒱$ , которое удовлетворяет равенству

k (𝐱, 𝐱^{'}) = ⟨ φ (𝐱), φ (𝐱^{'}) ⟩_{𝒱} .

Главное ограничение здесь, что $⟨ \cdot, \cdot ⟩_{𝒱}$ должно быть подходящим скалярным произведением. С другой стороны, явное представление для $φ$ не обязательно, поскольку $𝒱$ является пространством со скалярным произведением. Альтернатива следует из Шаблон:Нп5 — неявно заданная функция $φ$ существует, если пространство $𝒳$ может быть снабжено подходящей мерой, обеспечивающей, что функция $k$ удовлетворяет Шаблон:Нп5.

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

\sum_{i = 1}^{n} \sum_{j = 1}^{n} k (𝐱_{i}, 𝐱_{j}) c_{i} c_{j} \geq 0 .

Если это неравенство выполняется для всех конечных последовательностей точек $(𝐱_{1}, \dots, 𝐱_{n})$ в $𝒳$ и всех наборов $n$ вещественнозначных коэффициентов $(c_{1}, \dots, c_{n})$ (сравните, Шаблон:Нп5), тогда функция $k$ удовлетворяет условию Мерсера.

Некоторые алгоритмы, зависящие от произвольных связей, в исходном пространстве $𝒳$ будут, фактически, иметь линейное представление в других условиях — в ранжированном пространстве $φ$ . Линейная интерпретация даёт нам представление об алгоритме. Более того, часто нет необходимости вычислять $φ$ прямо во время вычислений, как в случае метода опорных векторов. Некоторые считают уменьшение времени за счёт этого главным преимуществом алгоритма. Исследователи используют его для уточнения смысла и свойств существующих алгоритмов.

Теоретически, матрица Грама $𝐊 \in ℝ^{n \times n}$ по отношению к ${𝐱_{1}, \dots, 𝐱_{n}}$ (иногда называемая «ядерной матрицей»Шаблон:Sfn), где $K_{i j} = k (𝐱_{i}, 𝐱_{j})$ , должна быть положительно полуопределена Шаблон:Sfn. Эмпирически, для эвристики машинного обучения, выбор функции $k$ , которая не удовлетворяет условию Мерсера, может оставаться оправданным, если $k$ , по меньшей мере, аппроксимирует интуитивную идею похожести^[1]. Независимо от того, является ли $k$ ядром Мерсера, о $k$ могут продолжать говорить как о «ядре».

Если ядерная функция $k$ является также Шаблон:Нп5, что используется в гауссовском процессе, тогда матрица Грама $𝐊$ может быть названа ковариационной матрицей Шаблон:Sfn.