Definizione
Molte Tecniche di Pattern Recognition richiedono di avere Dati da cui effettuare Learning rappresentati in uno Spazio Vettoriale Metrico ovverouno 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
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
& 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
$ 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
Nessun commento:
Posta un commento