Articles

Il problema XOR nelle reti neurali.

Introduzione
Questo è il primo di una serie di post che esplorano le implementazioni delle reti neurali artificiali (ANN). Lo scopo dell’articolo è quello di aiutare il lettore ad acquisire un’intuizione dei concetti di base prima di passare alle implementazioni algoritmiche che seguiranno.

Non si presuppone alcuna conoscenza precedente, anche se, nell’interesse della brevità, non tutta la terminologia è spiegata nell’articolo. Vengono invece forniti collegamenti ipertestuali a Wikipedia e ad altre fonti dove può essere richiesta una lettura aggiuntiva.

Questo è un grande argomento. Le ANNs hanno una grande varietà di applicazioni e possono essere usate per l’apprendimento supervisionato, non supervisionato, semi-supervisionato e di rinforzo. Questo prima di arrivare alle architetture specifiche del problema all’interno di queste categorie. Ma dobbiamo iniziare da qualche parte, quindi per restringere il campo, inizieremo con l’applicazione delle RNA ad un semplice problema.

Il problema XOr
Il problema XOr, o “esclusivo o”, è un problema classico nella ricerca sulle RNA. È il problema di usare una rete neurale per prevedere le uscite delle porte logiche XOr dati due ingressi binari. Una funzione XOr dovrebbe restituire un valore vero se i due ingressi non sono uguali e un valore falso se sono uguali. Tutti i possibili ingressi e le uscite previste sono mostrati nella figura 1.

XOr è un problema di classificazione per il quale le uscite previste sono note in anticipo. È quindi appropriato usare un approccio di apprendimento supervisionato.

In superficie, XOr sembra essere un problema molto semplice, tuttavia, Minksy e Papert (1969) dimostrarono che questo era un grosso problema per le architetture di reti neurali degli anni ’60, note come perceptrons.

Perceptrons
Come tutte le ANNs, il perceptron è composto da una rete di unità, che sono analoghi ai neuroni biologici. Un’unità può ricevere un input da altre unità. Nel farlo, prende la somma di tutti i valori ricevuti e decide se inoltrare un segnale ad altre unità a cui è collegata. Questo è chiamato attivazione. La funzione di attivazione usa qualche mezzo o altro per ridurre la somma dei valori di input a un 1 o uno 0 (o un valore molto vicino a un 1 o uno 0) per rappresentare l’attivazione o la sua mancanza. Un’altra forma di unità, conosciuta come unità di bias, si attiva sempre, inviando tipicamente un 1 hard coded a tutte le unità a cui è collegata.

I perceptrons includono un singolo strato di unità di input – inclusa una unità di bias – e una singola unità di output (vedi figura 2). Qui un’unità di bias è rappresentata da un cerchio tratteggiato, mentre le altre unità sono mostrate come cerchi blu. Ci sono due unità di input non bias che rappresentano i due valori di input binari per XOr. Qualsiasi numero di unità di input può essere incluso.

Il perceptron è un tipo di rete feed-forward, il che significa che il processo di generazione di un output – noto come propagazione forward – scorre in una direzione dallo strato di input a quello di output. Non ci sono connessioni tra le unità nello strato di input. Invece, tutte le unità nello strato di input sono collegate direttamente all’unità di output.

Una spiegazione semplificata del processo di propagazione in avanti è che i valori di input X1 e X2, insieme al valore di bias di 1, sono moltiplicati per i loro rispettivi pesi W0..W2, e analizzati all’unità di output. L’unità di uscita prende la somma di questi valori e impiega una funzione di attivazione – tipicamente la funzione di passo Heavside – per convertire il valore risultante in uno 0 o 1, classificando così i valori di input come 0 o 1.

È l’impostazione delle variabili di peso che dà all’autore della rete il controllo sul processo di conversione dei valori di input in un valore di output. Sono i pesi che determinano dove viene tracciata la linea di classificazione, la linea che separa i punti dei dati in gruppi di classificazione. Se tutti i punti di dati su un lato di una linea di classificazione sono assegnati alla classe 0, tutti gli altri sono classificati come 1.

Un limite di questa architettura è che è solo in grado di separare i punti di dati con una singola linea. Questo è un peccato perché gli ingressi XOr non sono linearmente separabili. Questo è particolarmente visibile se si tracciano i valori degli ingressi XOr su un grafico. Come mostrato nella figura 3, non c’è modo di separare le predizioni 1 e 0 con una singola linea di classificazione.

Percetroni multistrato
La soluzione a questo problema è di espandersi oltre l’architettura a singolo strato aggiungendo un ulteriore strato di unità senza alcun accesso diretto al mondo esterno, conosciuto come strato nascosto. Questo tipo di architettura – mostrata nella Figura 4 – è un’altra rete feed-forward conosciuta come un perceptron multistrato (MLP).

E’ da notare che un MLP può avere qualsiasi numero di unità nei suoi strati di input, hidden e output. Ci può essere anche un numero qualsiasi di strati nascosti. L’architettura usata qui è progettata specificamente per il problema XOr.

Simile al perceptron classico, la propagazione in avanti inizia con i valori di input e l’unità di bias dello strato di input che vengono moltiplicati per i loro rispettivi pesi, tuttavia, in questo caso c’è un peso per ogni combinazione di input (inclusa l’unità di bias dello strato di input) e unità nascosta (esclusa l’unità di bias dello strato nascosto). I prodotti dei valori dello strato di input e i loro rispettivi pesi sono analizzati come input per le unità non-bias nello strato nascosto. Ogni unità nascosta non-bias invoca una funzione di attivazione – di solito la classica funzione sigmoide nel caso del problema XOr – per schiacciare la somma dei loro valori di input fino a un valore che cade tra 0 e 1 (di solito un valore molto vicino a 0 o 1). Le uscite di ogni unità dello strato nascosto, inclusa l’unità di bias, sono poi moltiplicate per un’altra serie di pesi rispettivi e analizzate in un’unità di uscita. L’unità di output analizza anche la somma dei suoi valori di input attraverso una funzione di attivazione – di nuovo, la funzione sigmoide è appropriata qui – per restituire un valore di output che cade tra 0 e 1. Questo è l’output previsto.

Questa architettura, anche se più complessa di quella della rete perceptron classica, è in grado di ottenere una separazione non lineare. Quindi, con il giusto set di valori di peso, può fornire la separazione necessaria per classificare accuratamente gli input XOr.

Backpropagation
L’elefante nella stanza, naturalmente, è come si può trovare un set di valori di peso che assicuri che la rete produca l’output previsto. In pratica, cercare di trovare manualmente un insieme accettabile di pesi per una rete MLP sarebbe un compito incredibilmente laborioso. Infatti, è NP-completo (Blum e Rivest, 1992). Tuttavia, è fortunatamente possibile imparare un buon insieme di valori di peso automaticamente attraverso un processo noto come backpropagation. Questo è stato dimostrato per la prima volta funzionare bene per il problema XOr da Rumelhart et al. (1985).

L’algoritmo di backpropagation inizia confrontando il valore reale prodotto dal processo di propagazione in avanti con il valore atteso e poi si muove all’indietro attraverso la rete, regolando leggermente ciascuno dei pesi in una direzione che riduce la dimensione dell’errore di un piccolo grado. Sia la propagazione in avanti che quella all’indietro sono rieseguite migliaia di volte su ogni combinazione di input fino a quando la rete può prevedere accuratamente l’output atteso dei possibili input usando la propagazione in avanti.

Per il problema xOr, il 100% dei possibili esempi di dati sono disponibili da usare nel processo di addestramento. Possiamo quindi aspettarci che la rete addestrata sia accurata al 100% nelle sue previsioni e non c’è bisogno di preoccuparsi di questioni come bias e varianza nel modello risultante.

Conclusione
In questo post, è stato esplorato il classico problema ANN XOr. Il problema stesso è stato descritto in dettaglio, insieme al fatto che gli input per XOr non sono linearmente separabili nelle loro categorie di classificazione corrette. Una soluzione non lineare – che coinvolge un’architettura MLP – è stata esplorata ad alto livello, insieme all’algoritmo di propagazione in avanti usato per generare un valore di uscita dalla rete e l’algoritmo di backpropagation, usato per addestrare la rete.

Il prossimo post di questa serie presenterà un’implementazione Java dell’architettura MLP qui descritta, inclusi tutti i componenti necessari per addestrare la rete ad agire come una porta logica XOr.

Blum, A. Rivest, R. L. (1992). L’addestramento di una rete neurale a 3 nodi è NP-completo. Neural Networks, 5(1), 117-127.