Le reti neurali ricorsive rappresentano la naturale estensione delle reti neurali ricorrenti ai domini strutturati come alberi e grafi. Il modello, una generalizzazione del neurone ricorrente capace di processare solo sequenze, viene illustrato in [26]: viene introdotto un diverso tipo di neurone, chiamato neurone ricorsivo, in grado di trattare elementi appartenenti ad alcuni tipi di domini strutturati più complessi delle sequenze, come alberi e grafi aciclici.
L’idea alla base del modello proposto è di calcolare una codifica per ogni vertice del grafo, che sintetizzi sia l’informazione locale data dagli attributi che l’informa- zione sul contesto del vertice: in precedenza, la metodologia principale per poter applicare a grafi (o ad altri domini strutturati) i modelli di apprendimento preesi- stenti per dati flat, consisteva appunto nello stabilire una codifica, chiamata codifica a priori, e applicarla ad ogni grafo del dataset. Il risultato era un nuovo dataset i cui elementi non erano più grafi ma vettori flat, su cui era immediato applica- re un qualsiasi modello standard. Il principale difetto di questo tipo di approccio è che la codifica deve essere decisa “manualmente”, prima dell’apprendimento, ad esempio in base a qualche conoscenza sullo specifico task in questione o sul domi- nio di applicazione. La codifica è una fase completamente separata dal processo di apprendimento.
L’idea descritta in [26] al contrario, consiste nel calcolare la codifica dei grafi in maniera adattiva, tramite una rete neurale composta da un nuovo tipo di neuroni, i neuroni ricorsivi. Formalmente l’output di un neurone ricorsivo può essere espresso come xr(v) = fσ L X i=0 wi· Ii(v) + D X j=1 ˆ wj· xr(S(v)j) ! (2.8)
xr(S(v)j), con S(v) l’insieme dei successori di v (sez. 2.1), è l’output del neurone stesso (collegamento ricorsivo) per ciascuno dei vertici collegati a v da un arco uscente e D è il massimo out-degree del grafo.
La formula 2.8 si riferisce al caso particolare in cui il neurone ha connessioni ricorsive solo con se stesso. In generale, come per le reti ricorrenti, si possono avere interconnessioni ricorsive tra qualsiasi coppia di neuroni. Supponendo di avere m neuroni interconnessi, la formula diventa
xr(v) = Fσ W · I(v) + D X j=1 c Wj· xr(S(v)j) ! (2.9) dove F(i) σ(·) = fσ(·)per i = 1, . . . , m, W ∈ Rm × RL , I(v) ∈ RL e Wcj ∈ Rm× Rm , xr(·) ∈ Rm.
La codifica di ogni vertice è ricorsiva: così come per le sequenze l’output per il vertice corrente dipendeva anche dalla precedente porzione della sequenza, per i grafi l’output per il vertice v dipende dall’output di tutti i suoi discendenti, che formano il suo contesto, come schematizzato in figura 2.6: il contesto dei vertici foglia 2 e 4, senza archi uscenti, è vuoto, mentre il contesto del vertice 1 e del vertice 3 è formato da tutti i loro discendenti.
1 2 3
4
Figura 2.6: Esempio di contesto in un albero.
La funzione di trasduzione TG: G 7−→ O calcolata dalla rete neurale può anche in questo caso essere suddivisa in due sottofunzioni, la funzione di codifica ricorsiva τE : G 7−→ Rm, che trasforma l’input G nella corrispondente codifica, ovvero nei nuovi valori di stato della rete neurale (l’encoding del grafo), e la funzione di output y : Rm 7−→ O che mappa lo stato nel dominio di output.
τE(G) = 0 se G = ∅ τN N(Lroot, τE(G(1)), . . . , τE(G(k))) altrimenti (2.10)
dove τN N come per le reti neurali ricorrenti è la funzione calcolata dalla rete neurale che costituisce lo strato di unità ricorsive della rete. L’equazione 2.10 espri- me formalmente la definizione della funzione di codifica (ovvero di transizione di stato) della rete: è possibile osservare come venga applicata ricorsivamente in ma- niera bottom-up a tutti i vertici appartenenti a G, in modo che le foglie (o i vertici senza archi uscenti) vengano codificate solo in base alla loro label, mentre i vertici a livelli superiori vengono influenzati dalla codifica di tutti i loro discendenti.
Per le reti neurali ricorsive continuano a valere le tre proprietà elencate in 2.3: • La funzione è adattiva, grazie alla presenza dei pesi modificabili nelle funzioni
τE e y (W e Wc nell’equazione 2.9).
• La stazionarietà impone che la funzione di codifica τE sia indipendente dal tempo: nell’ambito dei domini strutturati ogni vertice corrisponde a uno step temporale distinto, e quindi ciò che si impone è che la funzione sia sempre la stessa applicata a tutti i vertici (ovviamente, quanto detto vale solo dopo la fase di apprendimento).
• La funzione di trasduzione è causale, in quanto l’output della rete per un ver- tice dipende solo dal vertice e dai suoi discendenti, così come nelle sequenze l’output dipendeva solo dai predecessori del vertice in questione. Questa pro- prietà impone una forte condizione sul tipo di trasduzioni che queste possono apprendere, in quanto si considera come contesto solamente l’insieme S(v) dei discendenti di ogni vertice; come per le reti neurali ricorrenti però, esistono va- rianti del modello che permettono di rilassare questa condizione e considerare un contesto più ampio, che verranno trattate nella prossima sezione.
Il modello descritto è facilmente e direttamente applicabile a tutte le classi di grafi che non presentano cicli, come alberi, DAG e DPAG, per i quali è sempre possibile stabilire un ordinamento topologico dei vertici che assicura la compatibilità con la funzione di trasduzione descritta sopra. Per applicare il modello a grafi ciclici invece, è necessario assicurarsi che alcune condizioni sulla encoding network siano
soddisfatte, affinchè sia garantito che il processo di codifica termini in uno stato stabile per ogni grafo; in [26] ad esempio viene riportata come condizione sufficiente per la convergenza che la matrice dei pesi sia sufficientemente piccola in norma. Ovviamente però, a causa del processo di apprendimento, la rete non è statica: si può garantire solamente che queste condizioni valgano all’inizializzazione della rete, ma non si può controllare come durante l’apprendimento i pesi verranno modificati.