Per dare una corretta introduzione ai kernel gaussiani, il post di questa settimana inizierà un po’ più astratto del solito. Questo livello di astrazione non è strettamente necessario per capire come funzionano i kernel gaussiani, ma la prospettiva astratta può essere estremamente utile come fonte di intuizione quando si cerca di capire le distribuzioni di probabilità in generale. Quindi ecco il patto: cercherò di costruire lentamente l’astrazione, ma se mai vi perdete irrimediabilmente, o semplicemente non ne potete più, potete saltare fino al titolo che dice “La parte pratica” in grassetto – è lì che passerò ad una descrizione più concreta dell’algoritmo del kernel gaussiano. Inoltre, se hai ancora problemi, non preoccuparti troppo – La maggior parte dei post successivi su questo blog non richiederanno che tu capisca i kernel gaussiani, quindi puoi semplicemente aspettare il post della prossima settimana (o saltarlo se stai leggendo questo dopo).

Ricorda che un kernel è un modo di collocare uno spazio di dati in uno spazio vettoriale di dimensione superiore in modo che le intersezioni dello spazio dei dati con gli iperpiani nello spazio di dimensione superiore determinino confini decisionali più complicati e curvi nello spazio dei dati. L’esempio principale che abbiamo guardato è stato il kernel che invia uno spazio dati bidimensionale a uno spazio a cinque dimensioni inviando ogni punto con coordinate al punto a cinque dimensioni con coordinate . Se volessimo darci ancora più flessibilità, potremmo scegliere un kernel dimensionale ancora più alto, per esempio inviando il punto al punto in uno spazio a nove dimensioni. Potete vedere come il kernel a nove dimensioni di cui sopra sia un’estensione del kernel a cinque dimensioni – abbiamo essenzialmente solo aggiunto quattro dimensioni alla fine. Se continuiamo ad aggiungere altre dimensioni in questo modo, otterremo kernel di dimensioni sempre più alte. Se dovessimo continuare a fare questo “per sempre”, finiremmo per avere un numero infinito di dimensioni. Notate che possiamo fare questo solo in astratto. I computer possono trattare solo cose finite, quindi non possono memorizzare ed elaborare calcoli in spazi vettoriali di dimensioni infinite. Ma faremo finta per un minuto di poterlo fare, solo per vedere cosa succede. Poi ritrasporteremo le cose nel mondo finito.

In questo ipotetico spazio vettoriale infinito-dimensionale, possiamo aggiungere vettori nello stesso modo in cui facciamo con i vettori regolari, semplicemente aggiungendo le coordinate corrispondenti. Tuttavia, in questo caso, dobbiamo aggiungere infinite coordinate. Allo stesso modo, possiamo moltiplicare per scalari, moltiplicando ciascuna delle coordinate (infinitamente molte) per un dato numero. Definiremo il kernel dei polinomi infiniti inviando ogni punto al vettore infinito . In particolare, ogni monomio nelle variabili e , come o apparirà in una delle voci di questo kernel, possibilmente molto in basso nella sequenza.

Per tornare al mondo computazionale, possiamo recuperare il nostro kernel originale a cinque dimensioni semplicemente dimenticando tutte le prime cinque delle voci. Infatti, lo spazio originale a cinque dimensioni è contenuto in questo spazio infinito. (Il kernel originale a cinque dimensioni è quello che otteniamo proiettando il kernel polinomiale infinito in questo spazio a cinque dimensioni.)

Ora fate un respiro profondo, perché stiamo per fare un passo avanti. Considerate, per un momento, cos’è un vettore. Se avete mai seguito un corso di algebra lineare matematica, ricorderete che i vettori sono ufficialmente definiti in termini delle loro proprietà di addizione e moltiplicazione. Ma lo ignorerò temporaneamente (con le mie scuse a tutti i matematici che stanno leggendo questo articolo). Nel mondo dell’informatica, di solito pensiamo a un vettore come a una lista di numeri. Se avete letto fin qui, potreste essere disposti a lasciare che quella lista sia infinita. Ma voglio che pensiate a un vettore come a una collezione di numeri in cui ogni numero è assegnato a una cosa particolare. Per esempio, ogni numero nel nostro solito tipo di vettore è assegnato a una delle coordinate/caratteristiche. In uno dei nostri vettori infiniti, ogni numero è assegnato a un punto della nostra lista infinitamente lunga.

Ma che ne dite di questo: Cosa succederebbe se definissimo un vettore assegnando un numero ad ogni punto del nostro spazio dati (di dimensione finita)? Un tale vettore non sceglie un singolo punto nello spazio dei dati; piuttosto, una volta scelto questo vettore, se si punta a qualsiasi punto nello spazio dei dati, il vettore ci dice un numero. In realtà, abbiamo già un nome per questo: Qualcosa che assegna un numero ad ogni punto dello spazio dei dati è una funzione. In effetti, abbiamo guardato molto le funzioni su questo blog, sotto forma di funzioni di densità che definiscono le distribuzioni di probabilità. Ma il punto è che possiamo pensare a queste funzioni di densità come a vettori in uno spazio vettoriale infinito.

Come può una funzione essere un vettore? Bene, possiamo sommare due funzioni semplicemente aggiungendo i loro valori in ogni punto. Questo è stato il primo schema che abbiamo discusso per combinare le distribuzioni nel post della settimana scorsa sui modelli a miscela. Le funzioni di densità per due vettori (bolle gaussiane) e il risultato della loro somma sono mostrati nella figura qui sotto. Possiamo moltiplicare una funzione per un numero in modo simile, il che risulterebbe nel rendere la densità complessiva più chiara o più scura. In effetti, queste sono entrambe operazioni con cui probabilmente avete fatto molta pratica nelle lezioni di algebra e di calcolo. Quindi non stiamo ancora facendo nulla di nuovo, stiamo solo pensando alle cose in un modo diverso.

Il prossimo passo è definire un kernel dal nostro spazio dati originale in questo spazio infinitesimale, e qui abbiamo molte scelte. Una delle scelte più comuni è la funzione blob gaussiana che abbiamo visto alcune volte nei post passati. Per questo kernel, sceglieremo una dimensione standard per i blob gaussiani, cioè un valore fisso per la deviazione . Poi manderemo ogni punto dei dati alla funzione gaussiana centrata in quel punto. Ricordate che stiamo pensando ad ognuna di queste funzioni come ad un vettore, quindi questo kernel fa quello che fanno tutti i kernel: colloca ogni punto del nostro spazio dati originale in uno spazio vettoriale di dimensioni superiori (in effetti, infinite).

Ora, ecco il problema: per riportare le cose nel mondo computazionale, abbiamo bisogno di scegliere uno spazio vettoriale di dimensioni finite situato in questo spazio vettoriale di dimensioni infinite e “proiettare” lo spazio di dimensioni infinite nel sottospazio di dimensioni finite. Sceglieremo uno spazio a dimensione finita scegliendo un numero (finito) di punti nello spazio dei dati, poi prenderemo lo spazio vettoriale attraversato dai blob gaussiani centrati in quei punti. Questo è l’equivalente del passo vettoriale definito dalle prime cinque coordinate del kernel polinomiale infinito, come sopra. La scelta di questi punti è importante, ma ci torneremo più tardi. Per ora, la domanda è come proiettare?

Per i vettori a dimensione finita, il modo più comune di definire una proiezione è usando il prodotto di punti: Questo è il numero che si ottiene moltiplicando le coordinate corrispondenti di due vettori, poi sommandole. Così, per esempio, il prodotto di punto dei vettori tridimensionali e è .

Si potrebbe fare qualcosa di simile con le funzioni, moltiplicando i valori che esse assumono nei punti corrispondenti del set di dati. (In altre parole, moltiplichiamo insieme le due funzioni.) Ma non possiamo poi sommare tutti questi numeri perché ce ne sono infiniti. Invece, prenderemo un integrale! (Notate che sto sorvolando su una tonnellata di dettagli qui, e mi scuso di nuovo con tutti i matematici che stanno leggendo questo). La cosa bella qui è che se moltiplichiamo due funzioni gaussiane e integriamo, il numero è uguale a una funzione gaussiana della distanza tra i punti centrali. (Anche se la nuova funzione gaussiana avrà un valore di deviazione diverso.)

In altre parole, il kernel gaussiano trasforma il prodotto di punti nello spazio infinito dimensionale nella funzione gaussiana della distanza tra punti nello spazio dei dati: Se due punti nello spazio dei dati sono vicini, allora l’angolo tra i vettori che li rappresentano nello spazio del kernel sarà piccolo. Se i punti sono lontani, allora i vettori corrispondenti saranno vicini alla “perpendicolare”.

La parte pratica

Perciò, rivediamo quello che abbiamo finora: Per definire un kernel gaussiano dimensionale, scegliamo prima punti nello spazio dei dati. Possiamo quindi calcolare le coordinate del kernel di qualsiasi punto nello spazio dei dati calcolando la sua distanza da ciascuno di questi punti scelti e prendendo la funzione gaussiana delle distanze.

Per capire meglio come funziona questo kernel, cerchiamo di capire come appare l’intersezione di un iperpiano con lo spazio dei dati. (Questo è ciò che si fa con i kernel la maggior parte delle volte, comunque.) Ricordiamo che un piano è definito da un’equazione della forma dove sono le coordinate del punto (nello spazio superiore del kernel) e sono parametri che definiscono l’iperpiano. Se stiamo usando un kernel gaussiano allora, grazie alla nostra versione del prodotto di punti, i valori misurano le distanze dai nostri punti scelti. Il confine di decisione è quindi l’insieme dei punti per i quali la funzione gaussiana delle distanze da questi punti soddisfa questa equazione.

Questo è ancora piuttosto difficile da decomprimere, quindi guardiamo un esempio in cui ciascuno dei valori è o 1 o -1. Quindi vicino ad ogni punto dati con etichetta , il valore sarà molto vicino a 1, mentre gli altri valori saranno piccoli, quindi la somma sarà positiva. Allo stesso modo, vicino a un punto con , la somma sarà negativa. Così, se , il limite di decisione separerà i punti positivi dai punti negativi. In effetti, ritaglierà una regione che ricorda le sfere gaussiane che definiscono il kernel. Un esempio è indicato a sinistra nella figura qui sotto, dove i colori indicano se i coefficienti sono positivi o negativi. Come potete vedere, il risultato assomiglia a una versione liscia dell’algoritmo dei vicini più vicini.

Se regoliamo i parametri , questo ha l’effetto di cambiare le dimensioni delle sfere gaussiane intorno ai punti, e quindi sposta il confine della decisione verso o lontano da essi, come a destra della figura. Se un coefficiente passa da positivo a negativo, il confine decisionale si sposterà da un lato di un punto all’altro. Se abbiamo una serie di dati etichettati (che possono coincidere o meno con i punti che definiscono il kernel gaussiano) allora l’addestramento di un algoritmo di classificazione lineare (come SVM o la regressione logistica) nello spazio del kernel corrisponde allo spostamento di questo confine decisionale, entro i vincoli definiti sopra, per massimizzare quanti dei punti dei dati sono sul lato corretto.

Quindi, questo ci dà più flessibilità per scegliere il confine decisionale (o, almeno, un diverso tipo di flessibilità) ma il risultato finale sarà molto dipendente dai vettori che scegliamo. Se ne scegliamo troppi (ad esempio se lasciamo che i punti che definiscono il kernel siano gli stessi dei punti dei dati) allora rischieremo l’overfitting, similmente a come l’algoritmo del vicino più vicino tende a portare all’overfitting. Quello che vogliamo veramente è un piccolo numero di punti distribuiti uniformemente in tutto il set, idealmente tale che ognuno dei punti sia vicino alla maggior parte dei punti della stessa classe.

Trovare una tale collezione di punti è un problema molto diverso da quello su cui ci siamo concentrati nei post finora su questo blog, e rientra nella categoria dell’apprendimento non supervisionato/analisi descrittiva. (Nel contesto dei kernel, può anche essere pensato come selezione/ingegnerizzazione delle caratteristiche). Nei prossimi post, cambieremo marcia e cominceremo ad esplorare idee lungo queste linee.