ML - 17 - Kernel Regression

• Date: [2021-04-06 mar 16:12]

• Lecturer: Giorgio Gambosi

• Slides: (ml_09_gp-slides.pdf)

In questa lezione abbiamo visto come poter applicare le funzioni kernel analizzate la scorsa lezione per fare regressione.

Le funzioni kernel possono anche essere utilizzate in altri contesti. Nel contesto della regressione ad esempio le funzioni kernel permettono di effettuare la predizione del valore associato ad un elemento \(x\) andando a confrontare i valori associati agli altri termini del training set che sono più "vicini" all'elemento di interesse \(x\), dove il concetto di "vicinanza" è rappresentato dalla funzione kernel utilizzata.

In generale in un contesto di regressione dato l'errore nella misurazione dei dati ad un fissato elemento \(x\) possono essere associati più valori \(y\). Possiamo quindi vedere il valore predetto associato all'elemento \(x\) come il valore atteso condizionato al fatto di aver visto un elemento \(x\), ovvero

\[\begin{split} f(x) = \mathbb{E}[y|x] &= \int y \cdot P(y|x) \,\,\, dy \\ &= \int y \cdot \frac{P(x, y)}{P(x)} \,\,\, dy \\ &= \frac{\int y \cdot P(x, y) \,\,\, dy}{P(x)} \\ &= \frac{\int y \cdot P(x, y) \,\,\, dy}{\int P(x, y) \,\,\, dy} \end{split}\]

L'idea è quindi quella di stimare la distribuzione congiunta di \(x\) e \(y\) tramite una funzione kernel \(\kappa_h\)

\[P(x, y) \approx \frac{1}{n} \sum\limits_{i = 1}^n \kappa_h(x - x_i) \cdot \kappa_h(y - t_i)\]

Sostituendo all'espressione trovata per \(f(x)\) troviamo quindi

\[\begin{split} f(x) &= \frac{\int y \cdot \frac{1}{n} \sum\limits_{i = 1}^n \kappa_h(x - x_i) \cdot \kappa_h(y - t_i) \,\,\, dy}{\frac{1}{n} \sum\limits_{i = 1}^n \kappa_h(x - x_i) \cdot \kappa_h(y - t_i) \,\,\, dy} \\ &= \frac{\sum\limits_{i = 1}^n \kappa_h(x - x_i) \int y \cdot \kappa_h(y - t_i) \,\,\, dy}{\sum\limits_{i = 1}^n \kappa_h(x - x_i) \int \kappa_h(y - t_i) \,\,\, dy} \end{split}\]

E dato che \(\kappa_h\) è una funzione kernel, per definizione otteniamo

\[\begin{cases} \int \kappa_h(y - t_i) \,\,\, dy = 1 \\ \\ \int y \cdot \kappa_h(y - t_i) \,\,\, dy = t_i \\ \end{cases}\]

otteniamo

\[f(x) = \frac{\sum_{i = 1}^n \kappa_h(x - x_i) \cdot t_i}{\sum_{i = 1}^n \kappa_h(x - x_i)}\]

Definendo quindi per ogni \(i\) la seguente quantità

\[w_i(x) = \frac{\kappa_h(x - x_i)}{\sum_{j = 1}^n \kappa_h(x - x_j)}\]

possiamo scrivere

\[f(x) = \sum\limits_{i = 1}^n w_i(x) \cdot t_i\]

ovvero il valore predetto è calcolato come una combinazione lineare di tutti i valori target pesati per un peso ottenuto in funzione del kernel utilizzato (Nadaraya-Watson).

Come è possibile vedere, questo tipo di regressione è diversa da quella vista inizialmente in cui andavamo a stimare dei coefficienti da utilizzare per effettuare al predizione. In questo modello infatti il valore predetto non è predetto in funzione dei valori delle features dell'elemento \(x\), ma viene predetto in termini di combinazione lineare dei valori dei target di tutti gli altri elementi del training set.

Un approccio che usa in modo diverso le funzioni kernel prende il nome di locally weighted regression e consiste nel variare il contesto in cui viene applicata la funzione kernel che misura la similitudine tra due punti.

Nel modello Nadaraya-Watson infatti la funzione kernel veniva utilizzata direttamente per effettuare la predizione. In questo caso invece la funzione kernel viene utilizzata per definire una funzione di costo \(L(x)\)

\[L(x) = \sum\limits_{i = 1}^n \kappa_h(x - x_i) \cdot (\mathbf{w}^T \overline{x}_i - t_i)^2\]

A questo punto si procede poi trovando i coefficienti \(\mathbf{w}\) che minimizzano tale funzione \(L(x)\). L'idea è che, a differenza del solito approccio in cui la funzione loss pesava ogni termine nello stesso modo, in questo caso il contributo di ogni elemento del training set nella loss function è regolato dalla funzione kernel, ovvero da quanto l'elemento considerato è simile all'elemento da predirre.

\[\hat{\mathbf{w}}(x) = \underset{\mathbf{w}}{\text{argminx}} \sum\limits_{i = 1}^n \kappa_h(x - x_i)(\mathbf{w}^T \overline{x}_i - t_i)^2\]

Da notare ovviamente che questa volta il problema cambia al variare di \(x\). Tale problema è risolto dal seguente vettore di elementi

\[\hat{\mathbf{w}}(x) = (\overline{\mathbf{X}}^T \Psi(x) \overline{\mathbf{X}})^{-1} \overline{\mathbf{X}}^T \Psi(x) \mathbf{t}\]

dove \(\Psi(x)\) è una amtrice diagonale \(n \times n\) in cui \(\Psi(x)_{i,i} = \kappa_h(x - x_i)\). La predizione viene quindi effettuata nel seguente modo

\[y = \hat{\mathbf{w}}(x)^T \overline{x}\]

L'approccio visto per la regressione locale può essere applicato anche nel caso della classificazione, andando a definire una funzione loss pesata da minimizzare, con i pesi che dipendono dal particolare elemento da predirre.

In questo caso si considera una versione pesata della cross entropy function, che deve essere massimizzata

\[L(x) = \sum\limits_{i = 1}^n \kappa_h(x - x_i) (t_i \log{p_i} - (1 - t_i) \log{(1 - p_i)})\]

con \(p_i = \sigma(\mathbf{w}^T \overline{x}_i)\).

Andando a modificare opportunamente l'algoritmo IRLS che abbiamo visto per la regressione logistica siamo in grado di calcolare

\[\hat{\mathbf{x}}(w) = \underset{\mathbf{w}}{\text{argmax}} \,\,\,\, L(x)\]