Kernel polinomiale

Nell'apprendimento automatico, il kernel polinomiale è una funzione kernel, comunemente utilizzata con le macchine a vettori di supporto (SVM) e altri modelli kernelizzati, che rappresenta la similarità fra coppie di vettori (campioni di addestramento) definiti in uno spazio di caratteristiche (feature) costruito sulla base di polinomi delle variabili originali, il che consente l'apprendimento di modelli non lineari.

Illustrazione del mapping ${\displaystyle \varphi }$. A sinistra insieme di campioni nello spazio di input, a destra gli stessi campioni nello spazio delle caratteristiche in cui il kernel polinomiale ${\displaystyle K(\mathbf {x} ,\mathbf {y} )}$ (per alcuni valori dei parametri ${\displaystyle c}$ e ${\displaystyle d}$ ) costituisce il prodotto interno. L'iperpiano appreso nello spazio delle feature da una SVM è un'ellisse nello spazio di input.

Intuitivamente, il kernel polinomiale non considera solo le caratteristiche date dei campioni di input per determinarne la similarità, ma anche loro combinazioni. Nel contesto dell'analisi di regressione, tali combinazioni sono note come caratteristiche di interazione. Lo spazio delle feature (implicite) di un kernel polinomiale è equivalente a quello della regressione polinomiale, ma si evita l'esplosione combinatoria del numero di parametri da apprendere. Quando le feature di input hanno valori binari (booleani) quelle implicite corrispondono a loro congiunzioni logiche^[1].

Definizione

Per i polinomi di grado ${\displaystyle d}$, il kernel polinomiale è definito come segue^[2]:

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

dove ${\displaystyle \mathbf {x} }$ e ${\displaystyle \mathbf {y} }$ sono vettori di dimensione ${\displaystyle n}$ nello spazio di input, ovvero vettori di caratteristiche calcolate da campioni di addestramento o di test e ${\displaystyle c\geq 0}$ è un parametro libero che compensa l'influenza dei termini di ordine superiore rispetto a quelli di ordine inferiore nel polinomio. Quando ${\displaystyle c=0}$, il kernel è detto omogeneo^[3] (un ulteriore kernel polinomiale generalizzato divide ${\displaystyle \mathbf {x} ^{\top }\mathbf {y} }$ per un parametro scalare specificato dall'utente a^[4]).

Essendo un kernel, ${\displaystyle K}$ corrisponde a un prodotto interno in uno spazio di feature basato su una trasformazione ${\displaystyle \varphi }$:

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

La natura di ${\displaystyle \varphi }$ può essere meglio compresa con l'esempio seguente. Sia ${\displaystyle d=2}$, quindi si ha il caso speciale del kernel quadratico. Utilizzando il teorema multinomiale (due volte: l'applicazione più esterna corrisponde al teorema binomiale ) e raggruppando, si ha:

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

da ciò consegue che la trasformazione ${\displaystyle \varphi }$ sia data da:

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

generalizzando per ${\displaystyle \left(\mathbf {x} ^{T}\mathbf {y} +c\right)^{d}}$,

dove ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$, ${\displaystyle \mathbf {y} \in \mathbb {R} ^{n}}$, e applicando il teorema multinomiale:

${\displaystyle {\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'ultima sommatoria ha ${\displaystyle l_{d}={\tbinom {n+d}{d}}}$ elementi, in modo che:

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

dove ${\displaystyle l=(j_{1},j_{2},...,j_{n},j_{n+1})}$ e

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

Sebbene in generale il kernel RBF sia più popolare rispetto al kernel polinomiale nella classificazione con SVM, quest'ultimo è piuttosto popolare nel contesto dell'elaborazione del linguaggio naturale (NLP)^[1][5]. Il grado più comune è ${\displaystyle d=2}$ (quadratico) poiché, nei problemi NLP, gradi più grandi tendono al sovradattamento.

Per il calcolo (esatto o approssimato) dei kernel polinomiali sono stati ideati vari metodi alternativi rispetto agli usuali algoritmi di addestramento SVM non lineari, fra i quali:

• l'espansione completa del kernel prima dell'addestramento/test con una SVM lineare^[5], ovvero il calcolo completo di ${\displaystyle \varphi }$ come nella regressione polinomiale;
• il basket mining (che utilizza una variante dell'algoritmo Apriori) per congiunzioni delle caratteristiche più comuni in un set di addestramento al fine di produrre un'espansione approssimata^[6];
• l'uso dell'indicizzazione invertita dei vettori di supporto^[6][1].

Un problema del kernel polinomiale è che esso può comportare instabilità numerica:

quando ${\displaystyle \mathbf {x} ^{T}\mathbf {y} +c<1}$ , ${\displaystyle K(\mathbf {x} ,\mathbf {y} )=(\mathbf {x} ^{T}\mathbf {y} +c)^{d}}$ tende a zero all'aumentare di ${\displaystyle d}$,

mentre quando ${\displaystyle \mathbf {x} ^{T}\mathbf {y} +c>1}$, ${\displaystyle K(\mathbf {x} ,\mathbf {y} )}$ tende all'infinito^[7].