Núcleo polinomial

En el aprendizaje automático , el kernel polinomial es una función kernel comúnmente utilizada con máquinas de vectores de soporte (SVM) y otros modelos kernelizados , que representa la similitud de vectores (muestras de entrenamiento) en un espacio de características sobre polinomios de las variables originales, lo que permite el aprendizaje de modelos no lineales.

Intuitivamente, el núcleo polinomial no solo analiza las características dadas de las muestras de entrada para determinar su similitud, sino también las combinaciones de estas. En el contexto del análisis de regresión , dichas combinaciones se conocen como características de interacción. El espacio de características (implícito) de un núcleo polinomial es equivalente al de la regresión polinomial , pero sin la explosión combinatoria en el número de parámetros a aprender. Cuando las características de entrada tienen valores binarios (booleanos), entonces las características corresponden a conjunciones lógicas de características de entrada. ^[1]

Definición

Para polinomios de grado $d$ , el núcleo polinomial se define como ^[2]

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

donde $x$ $e y$ son vectores de tamaño $n$ en el espacio de entrada , es decir, vectores de características calculadas a partir de muestras de entrenamiento o prueba y $c \geq 0$ es un parámetro libre que compensa la influencia de los términos de orden superior frente a los de orden inferior en el polinomio. Cuando $c = 0$ , el núcleo se denomina homogéneo. ^[3] (Un polikernel generalizado adicional divide $x T y$ por un parámetro escalar especificado por el usuario $a$ . ^[4] )

Como núcleo, $K$ corresponde a un producto interno en un espacio de características basado en algún mapeo $φ$ :

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

La naturaleza de $φ$ se puede ver a partir de un ejemplo. Sea $d = 2$ , por lo que obtenemos el caso especial del núcleo cuadrático. Después de utilizar el teorema multinomial (dos veces; la aplicación más externa es el teorema binomial ) y reagrupar,

K(\mathbf {x} ,\mathbf {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}

De esto se deduce que el mapa de características viene dado por:

\varphi (x)=\left(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\right)

generalizando para , donde , y aplicando el teorema multinomial : $\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}}$

La última suma tiene elementos, de modo que: $l_{d}={\tbinom {n+d}{d}}$

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

donde y $l=(j_{1},j_{2},...,j_{n},j_{n+1})$

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

Uso práctico

Aunque el kernel RBF es más popular en la clasificación SVM que el kernel polinomial, este último es bastante popular en el procesamiento del lenguaje natural (NLP). ^[1]^[5] El grado más común es $d = 2$ (cuadrático), ya que los grados más grandes tienden a sobreajustarse en los problemas de NLP.

Se han ideado varias formas de calcular el núcleo polinomial (tanto exactas como aproximadas) como alternativas a los algoritmos de entrenamiento SVM no lineales habituales, entre ellas:

expansión completa del núcleo antes del entrenamiento/prueba con un SVM lineal, ^[5] es decir, cálculo completo del mapeo $φ$ como en la regresión polinomial;
Minería de cestas (utilizando una variante del algoritmo a priori ) para las conjunciones de características que ocurren con mayor frecuencia en un conjunto de entrenamiento para producir una expansión aproximada; ^[6]
indexación invertida de vectores de soporte. ^[6]^[1]

Un problema con el núcleo polinomial es que puede sufrir inestabilidad numérica : cuando $x T y + c < 1$ , $K (x, y) = (x T y + c) d$ tiende a cero al aumentar $d$ , mientras que cuando $x T y + c > 1$ , $K (x, y)$ tiende a infinito. ^[4]

Referencias

^ abc Yoav Goldberg y Michael Elhadad (2008). splitSVM: Computación de núcleo polinomial rápida, no heurística y con uso eficiente del espacio para aplicaciones de procesamiento del lenguaje natural. Proc. ACL-08: HLT.
^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 15 de abril de 2013. Consultado el 12 de noviembre de 2012 .{{cite web}}: CS1 maint: archived copy as title (link)
^ Shashua, Amnon (2009). "Introducción al aprendizaje automático: notas de clase 67577". arXiv : 0904.3664v1 [cs.LG].
^ ab Lin, Chih-Jen (2012). Software de aprendizaje automático: diseño y uso práctico (PDF) . Escuela de verano de aprendizaje automático. Kioto.
^ ab Chang, Yin-Wen; Hsieh, Cho-Jui; Chang, Kai-Wei; Ringgaard, Michael; Lin, Chih-Jen (2010). "Entrenamiento y prueba de asignaciones de datos polinomiales de bajo grado a través de SVM lineal". Revista de investigación en aprendizaje automático . 11 : 1471–1490.
^ ab Kudo, T.; Matsumoto, Y. (2003). Métodos rápidos para análisis de texto basado en kernel . Proc. ACL.