Полиномиальное ядро

Эта статья о машинном обучении. Чтобы узнать о полиномиальных ядрах в теории сложности, см. Кернелизацию .

Иллюстрация картографии $\varphi$. Слева набор выборок во входном пространстве, справа те же выборки в пространстве признаков, где находится полиномиальное ядро $K(x,y)$ (для некоторых значений параметров $c$ и $d$) — внутренний продукт. Гиперплоскость, изученная SVM в пространстве признаков, представляет собой эллипс во входном пространстве.

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

Интуитивно понятно, что полиномиальное ядро ​​рассматривает не только заданные характеристики входных выборок для определения их сходства, но и их комбинации. В контексте регрессионного анализа такие комбинации известны как признаки взаимодействия. (Неявное) пространство признаков полиномиального ядра эквивалентно пространству полиномиальной регрессии , но без комбинаторного увеличения количества изучаемых параметров. Когда входные объекты имеют двоичное значение (логические значения), тогда эти объекты соответствуют логическим соединениям входных объектов.

Определение

Для полиномов степени d ядро ​​полинома определяется как

$K(x,y)=(x^{\mathsf {T}}y+c)^{d}$

где x и y — векторы размера n во входном пространстве , т. е. векторы признаков, вычисленные на основе обучающих или тестовых выборок, а c ≥ 0 — свободный параметр, учитывающий влияние членов более высокого и низшего порядка в полиноме. Когда c = 0 , ядро ​​называется однородным. (Еще одно обобщенное полиядро делит x ^Т y заданным пользователем скалярным параметром a . )

Как ядро ​​K соответствует скалярному произведению в пространстве признаков, основанном на некотором отображении φ :

$K(x,y)=\langle \varphi (x),\varphi (y)\rangle$

Природу φ можно увидеть на примере. Пусть d = 2 , и мы получаем частный случай квадратичного ядра. После использования полиномиальной теоремы (дважды — самым внешним применением является биномиальная теорема ) и перегруппировки,

$K(x,y)=\left(\sum _{i=1}^{n}x_{i}y_{i}+c\right)^{2}=\sum _{i=1}^{n}\left(x_{i}^{2}\right)\left(y_{i}^{2}\right)+\sum _{i=2}^{n}\sum _{j=1}^{i-1}\left({\sqrt {2}}x_{i}x_{j}\right)\left({\sqrt {2}}y_{i}y_{j}\right)+\sum _{i=1}^{n}\left({\sqrt {2c}}x_{i}\right)\left({\sqrt {2c}}y_{i}\right)+c^{2}$

Отсюда следует, что карта признаков имеет вид:

$\varphi (x)=\langle x_{n}^{2},\ldots ,x_{1}^{2},{\sqrt {2}}x_{n}x_{n-1},\ldots ,{\sqrt {2}}x_{n}x_{1},{\sqrt {2}}x_{n-1}x_{n-2},\ldots ,{\sqrt {2}}x_{n-1}x_{1},\ldots ,{\sqrt {2}}x_{2}x_{1},{\sqrt {2c}}x_{n},\ldots ,{\sqrt {2c}}x_{1},c\rangle$

обобщая для $\left(\mathbf {x} ^{T}\mathbf {y} +c\right)^{d}$, где $\mathbf {x} \in \mathbb {R} ^{n}$, $\mathbf {y} \in \mathbb {R} ^{n}$ и применив полиномиальную теорему :

${\begin{alignedat}{2}\left(\mathbf {x} ^{T}\mathbf {y} +c\right)^{d}&=\sum _{j_{1}+j_{2}+\dots +j_{n+1}=d}{\frac {\sqrt {d!}}{\sqrt {j_{1}!\cdots j_{n}!j_{n+1}!}}}x_{1}^{j_{1}}\cdots x_{n}^{j_{n}}{\sqrt {c}}^{j_{n+1}}{\frac {\sqrt {d!}}{\sqrt {j_{1}!\cdots j_{n}!j_{n+1}!}}}y_{1}^{j_{1}}\cdots y_{n}^{j_{n}}{\sqrt {c}}^{j_{n+1}}\\&=\varphi (\mathbf {x} )^{T}\varphi (\mathbf {y} )\end{alignedat}}$

Последнее суммирование имеет $l_{d}={\tbinom {n+d}{d}}$ элементы, так что:

$\varphi (\mathbf {x} )=\left(a_{1},\dots ,a_{l},\dots ,a_{l_{d}}\right)$

где ,

$a_{l}={\frac {\sqrt {d!}}{\sqrt {j_{1}!\cdots j_{n}!j_{n+1}!}}}x_{1}^{j_{1}}\cdots x_{n}^{j_{n}}{\sqrt {c}}^{j_{n+1}}\quad |\quad j_{1}+j_{2}+\dots +j_{n}+j_{n+1}=d$

Практическое использование

Хотя ядро ​​RBF более популярно в классификации SVM, чем полиномиальное ядро, последнее довольно популярно в обработке естественного языка (NLP). Наиболее распространенной степенью является d = 2 (квадратичная), поскольку более высокие степени имеют тенденцию к переобучению в задачах НЛП.

В качестве альтернативы обычным нелинейным алгоритмам обучения SVM были разработаны различные способы вычисления полиномиального ядра (как точные, так и приближенные), в том числе:

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

Одна из проблем с полиномиальным ядром заключается в том, что оно может страдать от числовой нестабильности : когда x ^Т y + c < 1 , K ( Икс , y ) знак равно ( Икс ^Т у + с ) ^д стремится к нулю с увеличением d , тогда как при x ^Т y + c > 1 , K ( x , y ) стремится к бесконечности.