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

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

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

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

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

Определение

Для получения степени-d полиномов ядро ​​полинома определяется как^[2]

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

где Икс и у векторы в входное пространство, т.е. векторы признаков, вычисленные на основе обучающих или тестовых выборок, и c ≥ 0 - это бесплатный параметр, в котором учитывается влияние членов высшего и более низкого порядка в полиноме. Когда c = 0, ядро ​​называется однородным.^[3] (Еще одно обобщенное многоядерное ядро ​​делит Икс^Ту по указанному пользователем скалярному параметру а.^[4])

Как ядро, K соответствует внутреннему продукту в пространстве функций на основе некоторого сопоставления φ:

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

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

${\displaystyle 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}}$

Из этого следует, что карта характеристик задается:

${\displaystyle \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 }$

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

Хотя Ядро RBF является более популярным в классификации SVM, чем полиномиальное ядро, последнее довольно популярно в обработка естественного языка (НЛП).^[1][5]Самая распространенная степень d = 2 (квадратичный), так как большие степени имеют тенденцию переобучать по проблемам НЛП.

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

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

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

использованная литература

1. Йоав Голдберг и Майкл Эльхадад (2008). splitSVM: быстрое, экономичное, неэвристическое, полиномиальное вычисление ядра для приложений NLP. Proc. ACL-08: HLT.
2. «Архивная копия» (PDF). Архивировано из оригинал (PDF) на 2013-04-15. Получено 2012-11-12.
3. Шашуа, Амнон (2009). «Введение в машинное обучение: заметки 67577». arXiv:0904.3664v1 [cs.LG ].
4. Лин, Чи-Джен (2012). Программное обеспечение для машинного обучения: дизайн и практическое использование (PDF). Летняя школа машинного обучения. Киото.
5. Чанг, Инь-Вэнь; Се, Чо-Джуй; Чанг, Кай-Вэй; Ринггаард, Майкл; Линь, Чи-Джен (2010). «Обучение и тестирование полиномиальных отображений данных низкой степени с помощью линейной SVM». Журнал исследований в области машинного обучения. 11: 1471–1490.
6. Кудо, Т .; Мацумото, Ю. (2003). Быстрые методы анализа текста на основе ядра. Proc. ACL.