Kernel Learning Algo on Graph - Jensen Shannon Divergence

Definizione 

Con Matrice Densità si intende una Matrice relativa ad un Sistema Quantistico che rappresenta il contributo normalizzato che ogni Autostato del Sistema in questione, da allo Stato Misto istantaneo considerato.

Analogamente la Matrice Densità può essere considerata come una sorta di PDF (Probability Density Function) relativa alla Probabilità che, effettuando una misura istantanea, il Sistema cada in uno dei suoi Autostati. 

$$ \rho = \sum_{i=1}^{N} p_{i} | \psi_i(t)  \rangle \langle \psi_i(t) | $$

Si tratta quindi di una Matrice $ n \times n $ strutturata nel seguente modo 

• sulla Diagonale Principale stanno Valori relativi al peso di ogni Singolo Autostato nella Mistura attuale
• al di fuori della Diagonale Principale ci sono solo zero, perchè gli Austostati sono tutti Ortogonali tra loro 

Osservazione  Singolo Autostato Allo stesso modo è possibile definire la Matrice Densità relativamente al Singolo Autostato $$ \rho_{i} = p_{i}  | \psi_{i}(t)  \rangle \langle \psi_{i}(t) |  $$ Data l’Ortogonalità degli Autostati, sappiamo che la Matrice $ | \psi_{i}(t) \rangle \langle \psi_{i}(t) |  $ è una Matrice Quadrata $ n \times n $ che vale ovunque zero tranne che nella posizione (i,i) in cui vale uno Quindi la Matrice Densità risulta definito anche come $$ \rho = \sum_{i=1}^{N} p_{i} \rho_{i} $$ Evoluzione Temporale Si noterà che la Matrice Densità così presentata è un valore che dipende dal tempo. Noto il suo valore per un determinato Stato, sarà possibile calcolare quello in un qualsiasi istante applicando l’Operatore Evoluzione Temporale precedentemente calcolato e quindi il valore di questo Operatore in un generico istante $ \rho(t) =  | \psi(t)  \rangle \langle  \psi(t) |  $ si può calcolare conoscendo quello in un dato istante $ \rho(0) = | \psi(0) \rangle \langle \psi(0) | $ applicando l'Operatore Evoluzione Temporale

Dalla Matrice Densità si può determinare la Informazione contenuta nel Sistema per misurare la quale si può utilizzare una Misura di Entropia (nel senso della Teoria dell’Informazione)

La prima misura di questo tipo, definita per Sistema Quantistici, è la Von Neumann Entropy

che ha una formulazione simile alla Shannon Entropy 

$$ H_{N} = - \text{Tr} \left ( \rho \ln \rho \right ) $$

Tutta la Informazione necessaria a definire la Von Neumann Entropy per la Matrice Densità si trova negli Autovalori della Matrice stessa 

$$ H_{N} = - \sum_{i=1}^{n} \lambda_{i} \ln (\lambda_{i}) $$

A questo punto è possibile introdurre una Misura di Distanza tra Sistemi Quantistici basata sulla Informazione contenuta in essi e quindi sulla loro Von Neumann Entropy

Una di queste Misure di Distanza è la Jensen Shannon Divergence la quale è così definita 

$$ D_{JS}(\rho, \sigma) = H_{N}\left ( \frac{\rho + \sigma}{2} \right ) - \frac{1}{2} H_{N}(\rho) - \frac{1}{2} H_{N}(\sigma) $$

In cui $ \rho $ e $ \sigma $ sono gli Operatori Densità di 2 diversi Sistemi Quantistici



Proprietà Matematiche di questa Misura

Si può dimostrare che questa Quantità rispetta tutte le Proprietà che deve avere una Misura


Appunto

Kernel Learning Algo on Graph - Quantum Walker

Definizione 

Descrizione 

Un Quantum Walker è l'analogo Quantomeccanico di un Random Walker.

Consideriamo ora il caso di un Discrete Quantum Walker.

Utilizzeremo questo elemento per definire cosa si intende per Passeggiata Quantomeccanica su un Grafo. 

Si immagini un Grafo $ G(V, E) $ in cui ad ogni Vertice corrisponde un Possibile Stato di un generico Sistema Quantomeccanico.

La possibilità di una Transizione Diretta da uno Stato $ v_{i} $ ad uno stato $ v_{j} $ con $ v_{i}, v_{j} \in V $ è descritta dalla $ A $ Matrice di Transizione, in cui un generico elemento è definito nel seguente modo

$$ a_{i,j} = \left\{\begin{matrix}
1 & \text{Se Transizione Diretta Possibile} \\
0 & \text{Altrimenti}
\end{matrix}\right.
$$

Rappresentiamo quindi l'evoluzione temporale del Sistema come la Passeggiata di un Camminatore sul Grafo degli Stati possibili.

Nel caso di un Random Walk le Transizione tra un Nodo e l'altro sono regolate da una Matrice di Transizione di tipo Stocastico mentre
nel caso del Quantum Walk la Matrice di Transizione è di tipo Deterministico.

Questa Quantum Walk Transition Matrix è una Matrice Complessa Unaria ovvero
una Matrice che moltiplicata per la sua Auto-Aggiunta (Matrice Trasposta, i cui elementi sono Complessi Coniugati) fornisce la Matrice Identità

Il Cammino inizia da uno Stato qualsiasi $ u_0 \in V $ sul Grafo e poi evolve nel tempo
e quindi all'istante $ t $ esso sarà dato da una Combinazione Lineare di tutti Vertici del Grafo,
in cui il Coefficiente relativo all’i-esimo Stato indica (attraverso un’operazione di Modulo Quadro) la Probabilità che il Sistema si trovi in quello Stato

$ \left | \psi(t) \right \rangle = \sum_{u \in V} \alpha_{u}(t) \left | u \right \rangle $

Ovviamente all’istante iniziale avremo che

$$ \alpha_{u}(0) = \left\{\begin{matrix}
1 & u = u_0 \\
0 & u \neq u_0
\end{matrix}\right.
$$

Defiamo quindi un Processo Stocastico $ X(t) $ la cui Realizzazione al Tempo $ t $ sia una Variabile Aleatoria che rappresenta la Probabilità che il Quantum Walker si trovi in un determinato Vertice in quell’istante

Conformemente all’Interpretazione Probabilistica della Funzione d’Onda del Quantum Walker da parte della Meccanica Quantistica, tale probabilità sarà data da 

$ P\left ( \left \{ X(t) = u \right \} \right ) = \alpha_{u}(t)^{*} \alpha_{u}(t) = \left | \alpha_{u}(t) \right | $

Naturalmente Coefficienti sono tali da essere Normalizzati e quindi 

$$ \sum_{u \in V} \left | \alpha_{u}(t) \right | = 1 $$ 

Osservazione  Differenza tra Moto Stocastico e Moto Quantistico Si sarà notato che, come per il Moto del Random Walk, anche nel caso del Quantum Walk la Posizione del Quantum Walker è rappresentata da una Processo Stocastico ma la ragione per cui questo è ovviene completamente diversa. Nel caso del Random Walk la Dinamica del Camminatore è intrinsecamente stocastica e questo viene reso dal fatto che la Matrice di Transizione è proprio Stocastica. Nel caso del Quantum Walk la Dinamica del Camminatore è determinata da una Transition Matrix di tipo Deterministico. Essa svolge il ruolo di Hamiltoniana da inserire nella Equazione di Schroedinger che è l’Equazione Fondamentale che determina l'Evoluzione Temporale di un Sistema Quantistico. Questa Equazione è comunque deterministica. La Aleatorietà relativa alla Posizione della Particella in un dato istante deriva direttamente dai Postulati della Meccanica Quantistica ed è di natura diversa da quella del Moto Stocastico. In un moto Stocastico Classico, ad ogni Transizione la Particella evolve in uno solo dei Possibili Stati scegliendo a caso conformemente alla Distribuzione di Probabilità espressa dalla Matrice di Transizione. In un moto Quantomeccanico, ad ogni Transizione la Funzione d'Onda del Camminatore evolve in tutti gli Stati Possibili, sarà poi l'atto di una eventuale misura che farà collassare il Sistema in una delle sue Autofunzioni. Una conseguenza di questo tipo di Dinamiche è che il Moto Stocastico Classico non è Reversibile mentre il Moto Quantomeccanico è Reversibile.

La Dinamica del Quantum Walker è determinata dalla Equazione di Schroedinger utilizzando la $ A $ Matrice di Adiacenza come Hamiltoniana e quindi 

$$ \frac{d}{dt} \left | \psi(t) \right \rangle = - i A \left | \psi(t) \right \rangle $$

Questa è di fatto una ODE la cui Soluzione risulta immediata 

$$ \left | \psi(t) \right \rangle = \exp\left ( - i A t \right ) \left | \psi(t_{0}) \right \rangle $$

Effettuando quindi una Decomposizione Spettrale della Matrice troviamo che 

$$ A = \Phi \Lambda \Phi^{T} $$

Con

• $ \Phi $ Matrice le cui colonne sono gli $ n $ Autovettori di $ A $ 
• $ \Lambda $ Matrice Diagonale i cui elementi sono gli $ n $ Autovaloti di $ A $ 

e quindi

$$ \exp(-i A t) = \Phi \exp(- i \Lambda t) \Phi^{T} $$

e quindi la Soluzione di cui sopra risulta 

$$ \left | \psi(t) \right \rangle = \Phi \exp\left ( - i \Lambda t \right ) \Phi^{T} \left | \psi(t_{0}) \right \rangle $$

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