Chi mi segue su Google+ o Twitter sa già tutta la storia. Per chi invece non lo fa eccola qui.
Un paio di settimane fa stavo pensando a quale progetto portare per l’esame di Machine Learning. Dopo aver scartato un po’ di idee perché troppo banali e altre perché troppo complesse mi si è accesa la lampadina. Ho pensato di progettare un intelligenza artificiale per il gioco della dama in grado di apprendere con l’esperienza.
Nella maggior parte della applicazioni grafiche la simulazione di comportamenti fisici ricopre un ruolo fondamentale. Per questo motivo vi farò vedere un metodo piuttosto elementare ed efficiente per simulare una navicella sottoposta ad un campo gravitazionale costante. Se conoscete il gioco Luna Lander avete già capito a cosa voglio arrivare.
Analisi Fisica
Il primo passo di ogni simulazione fisica consiste nello studiare nel modo più preciso possibile qual’è il comportamento fisico degli oggetti da simulare. Nel nostro caso l’unico elemento che ci interessa è la navicella.
Dal disegno vediamo che in un generico momento la nostra navicella è sottoposta ad una forza F orientata di 
Usando la classica formula della dinamica otteniamo:
Dividendo tutto per la massa della navicella:
Il nostro sistema ora è completamente descritto. Tuttavia in questa forma differenziale non è ancora sfruttabile dalla nostra applicazione.
Individuare gli ingressi
Il secondo passo consiste nell’individuare gli ingressi ovvero cosa dipende dallo stato e cosa dipende dall’input? Questo è importante perché gli ingressi sono del tutto imprevedibili o perché troppo complessi da predirre oppure perché generati dal libero arbitrio del giocatore. Nel nostro caso il giocatore controlla direttamente due parametri:
con cui è orientata la navicella. Per semplicità assumiamo che solo tre valori siano possibili e che tali valori cambino istantaneamente alla pressione del tasto corrispondente. Premendo il tasto direzionale destro 
, premendo il tasto sinistro 
e non premendo nulla 
.Integriamo
A questo punto, dalla legge che descrive l’accelerazione dobbiamo ricavare la funzione che descrive la posizione (che ci interessa sapere per disegnare la nave sullo schermo nel punto giusto).
Tuttavia integrare una funzione del genere analiticamente è impossibile. Come fare? Approssimando. A questo punto molti metodi sono stati sviluppati ma qui di seguito vi presento il metodo che ho usato più spesso per questo genere di cose. Non so se sia il più preciso ma offre un ottimo realismo con prezzi computazionali piuttosto irrisori.
L’idea che sta alla base di questo metodo è di considerare gli ingressi dell’utente come costanti (sebbene varino platealmente con il tempo). In questo modo integrare 
Da cui
Discretizziamo
Con una formula in tempo continuo ci facciamo ancora poco. Il computer lavora per cicli e, per quanto questi cicli possano essere piccoli, non possono certo essere considerati continui. Per far questo discretizziamo. Un metodo molto semplice consiste nel sostituire 
La formula riscritta in questo modo assume la forma:
Calcoliamo una formula incrementale
La formula precedente ha un grande svantaggio. Ci costringe a dover mantenere nella memoria la velocità iniziale, la posizione iniziale e il numero di cicli trascorsi dall’inizio della simulazione. Senza contare che questa formula da valori completamente sbagliati perché assume che l’accelerazione sia sempre costante: in questo modo quando l’utente accenderà il motore la formula ci darà la posizione che avrebbe avuto la navicella se il motore fosse sempre stato acceso dall’inizio, e viceversa, e non il valore corrispondente ad un motore appena acceso!
Ma a questo c’è una soluzione: basta trovare una formula incrementale che condensi tutte queste informazioni nel suo stato passato.
Per prima cosa vediamo la velocità. Calcoliamo la velocità per $\latex k+1$.
Bene. Possiamo subito notare che questa formula è equivalente a:
Con un procedimento analogo possiamo ricavare anche
Ora abbiamo una formula iterativa che ci permette di calcolare il moto della navicella sotto il comando dell’utente. Possiamo riassiumere l’algoritmo finale in questo modo:
Per ogni “frame” facciamo
e .Rendere coerenti le unità di misura e i sistemi di riferimento
Tutto il nostro ragionamento è fatto sulla base di unità di misure fisiche (metri su secondo). Lo schermo però si comporta diversamente. Le coordinate di un oggetto sullo schermo, ad esempio, sono quasi sempre indicate in pixel e non i metri. Dobbiamo quindi scalare i dati di x e y in modo tale che siano coerenti con la rappresentazione grafica.
Se ad esempio un metro sullo schermo ha una dimensione di 10px dobbiamo moltiplicare il valore di x e y di un fattore 10. Analogamente facciamo l’opposto se un pixel rappresenta 10 metri. 
In parecchie applicazioni informatiche, specie in quelle simulative, saper integrare una funzione ricopre un ruolo fondamentale. Purtroppo però le tecniche di integrazione che ci hanno insegnato a scuola o nei corsi di Analisi I sono del tutto inutili. Raramente, infatti, ci troveremo a che fare con funzioni integrabili, anzi, spesso dovremo integrare funzioni non esprimibili tramite funzioni analitiche.
Supponete ad esempio di voler implementare un piccolo gioco di guida. La prima cosa da fare è progettare il nostro sistema di guida. Ovviamente, dato che siamo dei tipi tosti, vogliamo che sia il più realistico possibile e non c’è nulla di più realistico che usare le leggi della fisica.
Abbiamo già parlato delle reti neurali. Una rete neurale è, in sintesi, una fitta interconnessione di elementi semplici chiamati percettroni. Tali unità, disposte in due o più strati, sono in grado di adattarsi tramite algoritmi particolari in modo tale che dato un ingresso X la rete “apprenda” l’uscita Y. Non entrerò oltre nel dettaglio, la materia è infatti piuttosto complicata acnhe trattata in modo superficiale.
A questo punto è bene precisare che questa procedura è quasi esclusivamente una mia particolare speculazione. Non ho letto nessuna pubblicazione al riguardo ma dai miei piccolissimi test sembra funzionare correttamente. Ma veniamo al punto.
Supponiamo di avere una rete neurale come quella in figura:
Abbiamo una rete con 4 ingressi binari e altrettante uscite. Poi, subito prima dell’uscita e subito dopo l’ingresso, ci sono due blocchi nascosti. Tali blocchi sono composti da uno o più strati della rete, l’importante è che le due sotto-reti siano simmetriche. Infine abbiamo due strati centrali, l’importante è che tali strati contengano un numero di unità minori di quelle in ingresso e uscita.
A questo punto addestriamo la rete in modo tale che ad un ingresso X corrisponde un uscita Y del tutto uguale all’uscita. Vi chiederete, a che diavolo serve una rete neurale che non faccia altro che dare in uscita lo stesso valore in ingresso? A nulla, ovviamente, ma proviamo a separare la rete in due reti all’altezza dello strato centrale. In questo modo abbiamo due reti: una con 4 ingressi e 2 uscite e una con 2 ingressi e 4 uscite.
Per il modo in cui la rete è stata addestrata possiamo trattare la prima rete come un coder e la seconda rete è un decoder. L’utilizzo di questa rete può essere, ad esempio, di codificare un’immagine spezzandola a blocchi di 4 bit e passandola nel coder. Il risultato sarà un file ridotto del 50%. La decodifica, analogamente, avviene spezzando il file codificato in blocchi da 2 bit per riottenere i 4 bit originali.
È bene precisare che questa compressione è solitamente lossy (quindi ha utilità solo per codifiche video/audio/immagini) in quanto le reti neurali solitamente sono “approssimazioni” oltre che statisticamente fonte di errore. Inoltre, il caso di 4 bit ridotti a 2 è poco efficente, solitamente andrebbero usato un ingresso molto più numeroso e un fattore di compressione variabile. Più il valore di compressione è alto più, ovviamente, la possibilità di errori e l’approssimazione aumenta.
Il vantaggio di questa tecnica è che, poiché la rete può essere facilmente addestrata partendo da pezzi del file da codificare, la rete apprende la migliore codifica da N a M per quello specifico file.
Questo è un piccolo esempio di come sia possibile utilizzare una tecnologia nata dall’intelligenza artificiale per compiti che apparentemente non hanno nulla a cui spartire con essa come la codifica multimediale.
Vi avevo parlato già degli alberi decisionali in relazione al famoso gioco 20q. Ne avevo parlato in questo articolo facendovi vedere come un semplice albero binario potesse mostrare caratteristiche di apprendimento molto ampie. Questa volta voglio invece mostrarvi un concetto molto utilizzato negli alberi decisionali per migliorare l’efficienza dell’albero stesso: l’entropia. Prima di questo però è necessario che precisare che esistono due metodologie di apprendimento.
APPRENDIMENTO GLOBALE E APPRENDIMENTO STOCASTICO
Il gioco 20q è un ottimo esempio di apprendimento stocastico. In questo caso infatti l’algoritmo apprende domanda per domanda e si aggiorna progressivamente verso la forma definitiva. L’apprendimento avviene alla fine di ogni esempio.
L’apprendimento globale invece si svolge in maniera diversa. Si prende un insieme numeroso di esempi, li si da al programma tutti insieme, e il programma apprende. In questo caso l’apprendimento avviene globalmente alla fine di tutti gli esempi.
L’apprendimento stocastico è solitamente il più usato nella pratica (specie nelle reti neurali) per la sua migliore efficienza, adattabilità e possibilità di successo. Nonostante ciò in questo esempio useremo un apprendimento globale per semplificarci i conti.
L’ENTROPIA
Supponiamo di dover scrivere un applicazione in grado di apprendere quale sono le giornate ideali per andare a giocare a tennis. La prima cosa da fare è elencare alcuni attributi della giornata: tempo, temperatura, umidità e vento. A questo punto forniamo al programma 10 “giornate” e indichiamo se la giornata è adatta al tennis o meno. Ad esempio:
A questo punto dobbiamo costruire un albero a partire da questi dati. Ma quale attributo testiamo alla radice? Ovviamente dobbiamo testare l’attributo la cui risposta ci da il maggior numero di informazioni (detto diversamente, quella che ci permette di eliminare il maggior numero di ipotesi). Per far questo utilizziamo l’entropia. Essa infatti ci è molto utile per calcolare l’information gain ovvero il grado di informazione associato ad ogni attributo.
L’entropia è espressa dalla seguente formula:
Dove c è il numero di possibili risposte (nel nostro caso sono due, “si” e “no”), e i vari p sono la frazione di esempi che hanno come risultato l’i-esima risposta. Ad esempio nella nostra lista di 10 giornate ce ne sono 4 con esito positivo e 6 con esito negativo. L’entropia del nostro insieme sarà:
Cioè circa 0.97.
INFORMATION GAIN
A questo punto dobbiamo cacolare l’information gain per ogni attributo. Secondo questa formula:
La formula sembra complicata ma non lo è. Vediamo infatti un rapido esempio. Cominciamo trovando il gain dell’attributo tempo. Tale attributo ha 3 valori possibili: sole, nuvoloso e pioggia. La prima cosa da fare è trovare il sottoinsieme S(v) per ogni valore di tempo, cominciamo con S(sole). Per fare ciò dobbiamo identificare tutte le giornale che hanno come attributo di tempo il valore “sole” e fra queste contare quante sono associate ad una giornata “si” e quante ad una giornata “no”.
Il risultato è 3 “si” (la 1, la 7 e la 10) e 2 “no” (2,8). A questo punto calcoliamo l’entropia di questo sotto-insieme e moltiplichiamola per la frazione di giornate assolate (5/10). Ottenendo: 0.48. Facciamo lo stesso per tutti gli altri valori ottenendo che il gain per tempo vale esattamente 0.23.
Facciamo lo stesso per tutti gli altri attributi ottenendo:
Bene. A questo punto sappiamo cosa scegliere: umidità. Possiamo quindi porre come nodo radice la domanda “è umido o secco?”. Inoltre notiamo che l’entropia per l’insierme S(umido) è esattamente zero. Questo ci indica che se la risposta è “umido” possiamo già dare la risposta: no.
Se invece la risposta è “secco” dobbiamo continuare. Per fare ciò dobbiamo togliere dall’insieme tutte le giornate umide. A questo punto rifacciamo tutto il calcolo da capo, ricalcoliamo il nuovo gain per ogni attributo restante (tempo, temperatura e vento) e scegliamo nuovamente il maggiore. Così fino alla fine.
Ovviamente, tutti questi conti che abbiamo fatto a mano possono essere facilmente automatizzati, altrimenti non parleremmo di apprendimento automatico 
In un prossimo post infatti presenterò un piccolo script che dato un insieme di esempi calcola l’albero decisionale migliore in base ai dati forniti con tanto di dati sull’entropia del sistema.
Supponiamo di trovarci in una città a noi sconosciuta e di avere un appuntamento importante con una stupenda ragazza (o ragazzo a seconda dei casi). La cosa più semplice da fare è chiedere indicazioni ai passanti. Purtroppo però siamo sfortunati e quel giorno diluvia che dio la manda e non c’è anima viva in giro. Non c’è speranza.
LA RICERCA IN AMPIEZZA
In questo caso l’unica soluzione che avete è di tentare tutte le strade. Partite dal punto A e verificate tutti gli incroci a cui si arriva direttamente da A, se non siete arrivati tornate ad A e verificate tutti gli incroci a cui si arriva partendo da A e attraversando un solo incrocio, e così via, aumentanto ad ogni passo la profondità della ricerca. Questo tipo di ricerca prende il nome di ricerca in ampiezza. Funziona? Sicuro, prima o poi arriverete a destinazione. Tuttavia la domanda sorge spontanea: quanto poi?
Supponendo, come avviene spesso in realtà, che ad ogni incrocio si dipanino 3 strade (oltre a quella da cui siete venuti) se disgraziatamente la ragazza si trova a solo 10 incroci di distanza dovrete testare circa 59.049 incroci e un numero maggiore di strade. Un compito decisamente eccessivo anche per il più motivato.
Dobbiamo trovare un alternativa. Appare evidente che abbiamo bisogno di un informazione che ci permetta di scartare le strade che sicuramente non ci portano a destinazione. Chiamiamo quindi la ragazza e scopriamo che è una nerd d’alta categoria. Ella infatti vole metterci alla prova. Invece di dirci la strada ci promette solo di dirci la distanza in linea retta che separa ogni incrocio che vogliamo da lei. È sufficiente? Si, e non solo troviamo una strada che ci conduce da lei ma troviamo la migliore.
LA RICERCA GOLOSA
La prima soluzione che ci viene in mente è semplice: fra tutti gli incroci che posso raggiungere da A scelgo quello che è più vicino alla ragazza e così via per ogni incrocio su cui vado a finire. Questo tipo di ricerca (che prende il nome di ricerca golosa) è sicuramente migliore della ricerca in ampiezza tuttavia ha due grossi problemi: non trova la strada più breve e, nel caso di grafo con cicli, può finire per ciclare all’infinito.
LA RICERCA A*
Scegliamo questa strategia: assegno a tutti gli incroci che posso raggiungere dall’incrocio in cui sono un numero N corrispondente alla somma della strada percorsa fino a quel punto più la distanza in linea retta che separa quell’incrocio dalla ragazza. A questo punto scelgo l’incrocio che ha il numero N più basso fra quelli che ho assegnato fin’ora. Questa ricerca prende il nome di A* ed è l’algoritmo di ricerca più efficiente su un grafo pesato (come ad esempio una mappa stradale).
I punti a favore di A* sono fondamentalmente due: l’efficienza computazionale e il fatto che, in alcune condizioni, il percorso trovato è ottimo.
EURISTICHE AMMISSIBILI
Ma quali sono queste condizioni? Torniamo all’informazione che ci forniva la ragazza: la distanza in linea retta di ogni incrocio da lei. Questa prende il nome di funzione euristica. In parole povere è una funzione che esprime una stima della “distanza” dall’obiettivo. Bene, affinché la ricerca di A* sia ottima è necessario che la funzione euristica non sovrastimi mai la distanza reale dall’obiettivo! Quando questa condizione è soddisfatti si dice che la funzione euristica è ammissibile.
Nel nostro caso la funzione euristica soddisfa questa condizione in quanto la distanza in linea retta fra un incrocio e la ragazza non può mai essere maggiore della distanza reale (per definizione la retta è la distanza più breve fra due punti). La funzione è quindi ammissibile soluzione che troveremo sarà quindi ottima.
La non ammissibilità di una funzione non è però un limite stringente, spesso infatti trovare una funzione euristica ammissibile necessita di un quantitativo di calcoli troppo elevato che vanificherebbe i vantaggi di A*. In questi casi si può scegliere di usare una funzione non ammissibile ma di facile calcolo a patto di accontentarsi di una soluzione che potrebbe non essere ottimale.
Abbiamo imparato tanto in questa uscita. La ragazza al nostro arrivo sarà sicuramente soddisfatta.
Ho preparato un PDF con la dimostrazione del lower bound per algoritmi di ordinamento. Può contenere ancora qualche svista ma dovrebbe essere piuttosto corretto e fornire, a chi vuole, una dimostrazione semplificata del perché non può esistere un algoritmo di ordinamento con complessità inferiore a O(n log(n)).
Vedendo le statistiche del sito mi sono accorto che la parola più usata per arrivare a questo blog è, con ampio margine, la parola diagramma di flusso.
A quanto pare c’è molto interesse attorno a questo strumento che io trovo più didattico-scolastico che di vera utilità o valore scientifico. Come tutti i modelli di rappresentazione grafica è infatti improponibile per rappresentare un qualsivoglia programma complesso ma inoltre ha lo svantaggio di non avere la base teorica e formale che hanno altri modelli.
Ho comunque deciso di parlarne per colmare la mancanza facendovi però notare che esistono modelli più rigorosi quali automi a stati finiti, automi a pila e macchine di Turing.
L'algoritmo di Bubble Sorting in azione.
Insertion Sort e Selection Sort non si sono rivelati all’altezza delle nostre aspettative e noi ci ritroviamo ancora senza un algoritmo efficente per ordinare, o meglio: sappiamo ordinare le tracce di un album, oppure i CD di un apiccola collezione domestica, ma avremo molte difficoltà nell’ordinare in ordine di età gli abitanti di Roma o i volumi di un agrande biblioteca.
Dobbiamo proseguire la nostra ricerca, cambiamo approccio, questa volta il nostro tentativo cade sul Bubble Sort.
Rappresentazione grafica di un ordinamento con Selection Sort
Nell’ultimo appuntamento abbiamo visto e analizzato gli aspetti generali dell’Insertion Sort e notato che esso non è affatto un algoritmo usabile in pratica per istanze (ovvero input) molto grandi.
Ovviamente l’Insertion Sort non è l’unico algoritmo di sorting esistente. Nella nostra ricerca dell’algoritmo ottimo di sorting oggi guarderemo il Selection Sort.
Continue reading »
| © 2008-2012 SlashCode | Suffusion theme by Sayontan Sinha |
Recent Comments