Kernel Learning Algo on Graph

Definizione 

Molte Tecniche di Pattern Recognition richiedono di avere Dati da cui effettuare Learning rappresentati in uno Spazio Vettoriale Metrico ovvero
uno Spazio Vettoriale sul quale sia stata definita una nozione di Distanza, da intendersi come Misura di Similarità appunto

In molti casi reali invece risulta molto più comodo strutturare Dati in un Grafo per via della loro stessa natura (dati parziali, connessi tra loro in modo topologicamente non banale, ...) e quindi non è semplice passare
ad una Rappresentazione in uno Spazio Vettoriale, al fine di usare gli Algoritmi di Learnig già sviluppati.

Strategia1 : Mapping da Grafo a Vectorial Space

Cercando una Trasformazione per passare da Grafo a Spazio Vettoriale possiamo

riscontrare subito 2 problemi 

1) Vettori (gli Elementi dello Spazio Vettoriale) hanno un Ordine intrinseco mentre Grafi no 

Si rende quindi necessario stabilire una Regola per realizzare esplicitamente questo Mapping 

ma essa andrà fissata in modo capestro e quindi non avrà carattere di generalità 

2) Anche fissando la sopra citata Regola per Mapping c’è la possibilità che Vettori generati da Grafi diversi abbiano lunghezze diverse 

Questi sono problemi intrinseci di questo approccio, per cui vale la pena considerare una diversa strada 

Strategia2: Generalizzazione di Algoritmi al Mondo dei Grafi 

Un’altra Strategia, più interessante, può essere quella di Generalizzare le Tecniche sviluppate per Spazi Vettoriali allo Spazio dei Grafi 

Questo tipo di approccio richiede però anzitutto una adeguata riformulazione teorica dei concetti precedentemente utilizzati solo nell'ambito degli Spazi Vettoriali, a quello dei Grafi. 

Ci si riferisce anzitutto alla Kernel Theory e quindi ai Kernel Methods che sono alla base di Applicazioni ad oggi molto diffuse come le SVM.

Kernel Theory 

Per quanto riguarda la Kernel Theory nello Spazio Vettoriale: immaginiamo di avere Dati rappresentati da una Nuvola di Punti in uno Spazio Euclideo N Dimensionale che indicheremo con $ X $ chiamandolo Data Space.

In merito a problemi di Classificazione, le Tecniche di Supervised Learning Iniziali puntavano a Partizionare il Data Space in base alle indicazioni del Training Set ottenendo così alla fine del Processo una Partizione, ovvero una suddivisione in Volumi, in cui ognuno di essi fosse associato ad una specifica Classe.

Fino a quando la Compartimentazione del Data Space avveniva in modo lineare, il problema della classificazione era abbastanza facile in quanto poteva essere reso come un Problema di Ottimizzazione basato sul calcolo di un Prodotto Scalare. 

Osservazione  Classificazione Lineare Dato un determinato Training Set, l'obiettivo è trovare l'equazione di un Iperpiano che soddisfi un determinato criterio di ottimalità, tra tutti gli Iperpiani che dividono il Data Space in 2 parti, una delle quali contenente tutti e soli gli Elementi del Training Set appartenenti ad una determinata classe Ipotizzando di trovarci in $ \mathbb{R}^{n} $ con la classica definizione di Prodotto Scalare (si tratta quindi di uno Spazio Euclideo sul quale il Prodotto Scalare induce la Norma-2 e la classica Misura di Distanza) dobbiamo trovare anzitutto l'Insieme $ W = \left \{ \vec w_{i} \right \}_{i=1,...,m} $ dei Vettori $ \vec w_{i} $ che individuano un piano che separa nettamente gli Elementi di una Classe da tutti gli altri. Questa condizione viene resa utilizzando il Concetto di Prodotto Scalare dato che tutti gli Elementi del Training Set appartenenti alla Classe C staranno da un lato del piano e quindi $ \vec w \cdot \vec x_{i} > 0 $ con $ \forall i : \vec x_{i} \in C $ con C Classe tutti gli altri Elementi del Training Set non appartenenti alla Classe C stanno dall'altra parte del piano e quindi $ \vec w \cdot \vec x_{i} < 0 $ con $ \forall i : \vec x_{i} \not \in C $ con C Classe  Nel caso in cui $ \vec w \cdot \vec x_{i} = 0 $ gli elementi in questione stanno esattamente sul piano separatore  Naturalmente il segno assoluto (positivo o negativo) del Prodotto Scalare non ha importanza,  l'importante è che tutti e soli gli Elementi del Training Set appartenenti alla Classe C abbiano lo stesso segno, qualunque esso sia.

Naturalmente la Classificazione non Lineare è decisamente più complessa. 

La SVM può aiutare nella Soluzione di questo problema dato che 

un Kernel appositamente definito può permettere di mappare il Data Space in uno Spazio a più elevata Dimensionalità, che chiameremo SVM Space, in cui la Classificazione può avvenire in modo Lineare 

La complessità viene quindi spostata sulla Definizione del Kernel che riesca a mappare uno specifico Training Set in uno Spazio in cui la classificazione sia semplice ovvero Lineare

Tenicamente un Kernel Semidefinito Positivo è una operazione tipo Prodotto Scalare ovvero tale per cui 

\begin{align}
& k : X \times X \rightarrow \mathbb{R} \nonumber \\
& k(x,y) \ge 0 \quad \forall x,y \in X \nonumber \\
& k(x,y) = 0 \Leftrightarrow x = y \nonumber
\end{align}

La Definizione di un Kernel Semidefinito Positivo implica l’esistenza di un Mapping del tipo 

$$ \phi : X \rightarrow H $$

con $ H $ Spazio di Hilbert

tale per cui il risultato dell’operazione di Kernel è proprio uguale al Prodotto Scalare in quello Spazio di Hilber ovvero
$ k(x,y) = (\phi(x), \phi(y)) \quad \forall x,y \in X $

Il Calcolo del Kernel permette quindi di effettuare 2 Operazioni in 1 ovvero 

• Mapping dal Data Space al Hilber Space 
• Calcolo del Prodotto Scalare in Hilber Space 

L’idea è quindi quella di riuscire a definire Kernel che agiscano nello Spazio dei Grafi anzichè solo in Spazi Vettoriali