Reinforcement Learning

Learning Optimal Policies

C’è un altro stile di apprendimento che si trova tra i tipi supervised e unsupervised. Un esempio sarebbe l’apprendere quale di molte azioni possibili un robot eseguirebbe ad ogni fase in una sequenza continua di esperienze dato solo il risultato finale di tutte le sue azioni. Un caso estremo sarebbe l’apprendere a giocare a scacchi in modo eccellente data solo l’informazione riguardante una vittoria o una sconfitta alla fine del gioco. Nessun sistema è ancora stato costruito che possa apprendere a giocare a scacchi questo modo, ma è possibile per un programma apprendere a giocare a backgammon in questo modo e apprendere ad eseguire altri interessanti compiti, come controllare il volo di elicotteri. Prendendo a prestito i termini dalla teoria psicologica dell’apprendimento, possiamo chiamare la vittoria vincita o la sconfitta informazione (o in generale il good-result o bad-result ) un “reward” o un “reinforcement” e questo stile di apprendimento è chiamato “reinforcement learning” o (talvolta) “trial-and-error learning”.

Il Reinforcement Learning ha una lunga e multiforme storia. Lo psicologo Edward L. Thorndike (1847-1949) ha studiato questo stile di apprendimento in animali. Nel loro libro Reinforcement Learning: An Introduction , Richard S. Sutton e Andrew G. Barto due dei pionieri nel campo, citano alcune aggiuntive pietre miliari storiche, includendo il metodo di Arthur Samuel per apprendere evaluation functions a dama, l’uso di tecniche di programmazione dinamica in optimal control di Richard Bellman, il sistema di learning trial-and-error di John Andreae Stella, i sistemi learning per tic-tac-toe di Donald Michie (MENACE) e pole-balancing (BOXES) e il lavoro di Harry Klopf su “hedonistic neurons”. Il Reinforcement learning è un’altra di quelle sottodiscipline di AI che sono diventate altamente tecniche e multiramificate. Io tenterò una descrizione debole e non matematica di come esso funziona.

Nel suo setting più semplice, il reinforcement learning è circa l’apprendere come attraversare un insieme di stati, andando da uno stato ad un altro, raggiungere uno stato nel quale un reward è ottenuto. Il problema è molto simile a quello che una cavia affronta nell’apprendere come percorrere un labirinto (o a quello che un robot affronta nell’apprendere come effettuare un compito). Infatti, usiamo l’esempio del labirinto per descrivere alcuni aspetti di reinforcement learning.

Il problema della cavia è di andare dalla sua posizione di partenza fino al formaggio, la posizione goal. Nella terminologia del reinforcement learning, queste situazioni sono chiamate “states”. A ciascuno stato, la cavia può selezionare tra quattro azioni, cioè turn left, turn right, go forward o go back. In funzione dello stato, solo alcune delle azioni sono possibili – non si può go forward se si trova di fronte ad una fine, per esempio. Considerando ogni possibile azione, la cavia va da uno stato ad uno adiacente nel labirinto. La collezione di stati e le azioni che li collegano può essere considerata come un grafo.

In modo da non allontanarsi troppo lontano da ciò che è noto circa cavie reali che percorrono labirinti, passiamo ora a descrivere come un finto “robotic rat” potrebbe apprendere a percorrere questo labirinto. Il problema principale per il robot è che esso parte senza avere né una mappa del labirinto né una qualche idea riguardante gli effetti delle sue azioni. Cioè, per ogni dato stato che esso trovi in sé stesso, esso non sa quali stati successivi risulterebbero per le varie azioni che esso potrebbe intraprendere in questo stato. Perché se esso ha questa mappa, diciamo quella rappresentata da un grafo, esso potrebbe cercare il grafo (usando un metodo come A*) per trovare un percorso verso il nodo goal. Un modo per procedere sarebbe di tentare di apprendere un grafo di stati e le loro connessioni con metodi trial-and-error e poi usare metodi graph-searching per indovinare come spostarsi navigate nel labirinto.

Un’alternativa, e quella usata dalla maggior parte dei metodi reinforcement learning, implica la denominazione di tutti gli stati che il robot incontra quando esso vaga casualmente in cerca del goal. (Noi ipotizziamo che eventualmente esso raggiunga il goal). Nella terminologia del reinforcement learning una “policy” per attraversare il labirinto associa alcune singole azioni con ciascun nominato stato. Una migliore o “optimal policy” sarebbe quella di associare a ciascun stato quell’azione che condurrebbe ad un percorso più breve (o altrimenti il meno costoso) attraverso il labirinto. Reinforcement learning è circa learning la best policy o almeno le good policies.

Un metodo per apprendere una policy implica associare un “valuation” number con ogni possibile azione a ciascun stato e poi adjusting questi numeri (basati sull’esperienza) fino a che essi indicano la via verso il goal. Questo metodo è chiamato “Q-learning” e fu originariamente suggerito da Christopher Watkins nella sua tesi Ph.D. alla Cambridge University. Il robot inizia il suo learning process assegnando un nome allo stato nel quale esso inizia e, assegnando casualmente numeri di valutazione selezionata ad ogni azione, esso può prendere quello stato. Il learning process potrebbe espandere questa tabella assegnando nomi e valutation numbers a tutte le azioni che esso può prendere in ogni nuovo stato incontrato. (Noi ipotizziamo che il robot ricordi, nella sua tabella, i nomi di tutti gli stati che esso ha già visitato nel suo learning process e può distinguere questi dai nuovi stati). Ad ogni stage del learning process, il robot inizia quell’azione che ha il valuation number più alto. Poiché c’è solo un’azione nello stato iniziale del robot, esso inizia quell’azione, trova sé stesso in un nuovo stato e assegna casualmente valuation numbers alle azioni possibili in quel nuovo stato.

Ora arriva il passo chiave nell’apprendimento. Poiché il robot ora “knows” che esso può raggiungere un nuovo stato che ha azioni il cui valuation number più alto è 6, esso aggiorna il valuation number, cioè 3, dell’azione che conduce verso quello stato ad un numero più consistente con l’essere capace ora di compiere un’azione che esso immagina è equivalente a 6. Il “cost” della sua azione appena completata, l’adjustement di 3 non va bene a tutti i percorsi a 6 ma solo appena a 5, diciamo. .

Questo processo continua. In ciascuno stato, quell’azione il cui valutation number è più grande e poi regola quel valuation number rendendo il suo valore più vicino al valore dell’azione con il più alto valuation number nello stato appena intrapreso. E, anche se il processo inizia con casualmente selezionati valuation numbers, eventualmente il processo trial-and-error inciamperà nello stato dove un alto “reward” sarà ottenuto. In questa fase, l’azione appena compiuta, che lo ha condotto a quel reward, ha il suo valuation number incrementato allo stesso valore (forse appena un po’ di meno) rispetto al valore del reward.

Ora, per la prima volta, adjusted valuation trova se stessa nello stato adiacente allo stato del goal ancora, essa certamente compirà la stessa azione. In modo più importante, quando esso raggiunge questo penultimo stato in una esperienza susseguente, esso propagherà questo valore basato su “ricompensa all’indietro”.

Cosa accadrebbe se questi valori fossero così come essi molto probabilmente sarebbero, se il robot camminasse lontano, cioè si allontanasse dal goal quasi realizzato? Se i valutation numbers sono regolati come prescritto, sempre considerando il cost di una mossa, un pensiero potrebbe convincerlo che eventualmente i numeri sarebbero tali da forzare il robot verso il goal, con tutti gli altri percorsi eventualmente che sono stati chiusi.

Con esperienza continuata, le valutations di azioni implicavano nel realizzare (achieving) il goal gradualmente propagate backward dal goal. Eventualmente, dopo molta esperienza trial-and-error (e con qualche “reasonable” ipotesi), i valori convergeranno a quelli che implementano un optimal policy, cioè una che sempre porta il robot al goal nella maniera più efficiente.

Molte versione di reinforcement learning hanno le seguenti elaborazioni:

• Rewards potrebbero essere dati a più di uno degli stati. Cioè, non c’è necessariamente un singolo stato goal ma molti stati che potrebbero contribuire a reward. Rewards sono rappresentati da valori numerici, che potrebbero essere positivi (true “rewards”), zero, o negativi (“punishments”).
• Piuttosto che tentare di trovare una policy che corrisponda ad un percorso ottimale verso un singolo stato goal, si prova ad apprendere policies che massimizzano il quantitativo di reward aspettato gradualmente. Usualmente nell’apprendere una policy, rewards che sono anticipati nel futuro sono “discounted”, cioè, non contano come rewards attesi più immediatamente.
• Ogni azione data ad una stato non potrebbe sempre condurre allo stesso stato. Si potrebbe tentare di apprendere le probabilities che alcune azioni compiute in uno stato conducono ad altri stati e alcuni metodi di reinforcement learning, come “prioritized sweeping” fanno proprio questo. Il processo Q-learning evita la necessità di apprendere queste probabilities esplicitamente perché, qualunque esse siano, essi (insieme ai rewards premi) appropriatamente hanno come effetto i valori che il processo di apprendere assegna a state-action pairs.
• Come (una) ulteriore complicazione, potrebbe accadere che il robot ha solo una imperfetta conoscenza di ciò che lo stato in cui è perché il suo apparato di sensori non è sufficientemente preciso (cfr. precisione vs sensibilità) In questo caso, l’effettivo stato in cui il robot è (in) è detto essere “hidden” da esso, che aggiunge complicazioni aggiuntive al problema di apprendere un optimal policy.

Con queste elaborazioni, il problema diventa uno di quelli che è chiamato a “Markov Decision Process” (MDP). Con la conoscenza imperfetta di uno stato, esso è chiamato un “Partially-Observable Markov Decision Process” (POMDP). MDPs e POMDPs sono stati studiati bene da persone in “control theory” così come in AI.

Io posso usare l’esempio del labirinto per ricordare molte cose che sono importanti nell’uso del reinforcement learning in applicazioni pratiche. Primo, io ipotizzavo che l’esplorazione casuale del robot eventualmente lo avrebbe portato nello stato del goal. In problemi complessi, la chance di realizzare (achieving) casualmente un goal ( o altri rewards) potrebbe essere praticamente nulla. Spezzando il problema in giù all’interno di una gerarchia di sottoproblemi nei quali i rewards sono più facilmente ottenuti è talvolta usato per velocizzare (up) l’apprendere. In aggiunta, strategie di “shaping” possono essere usate nelle quali il robot è prima piazzato in una situazione sufficientemente vicina al goal che una casuale esplorazione troverebbe. Poi, dopo alcune azioni vicine al goal sono state assegnate goal-relevant evaluations, le situazioni di partenza possono essere gradualmente mosse sempre più lontano dal goal. In alternativa, suggerimenti potrebbero essere dati, forse nella forma di “rewards intermediate” per consentire al robot di conoscere quello che esso sta facendo bene fino ad allora. Strategie come queste sono usate nell’insegnare capacità ad umani e ad animali.

Un altro problema concerne il compromesso tra “exploiting” una già appresa policy versus “exploring per trovare migliori policies. È spesso il caso che un insieme di action valuations ottenute prima nel processo di apprendimento potrebbero non essere il migliore insieme possibile. Per apprendere un insieme migliore, il robot deve essere incoraggiato in qualche modo per eliminare casualmente via da una known policy per bloccarne una migliore. Infine, molti problemi potrebbero avere “state spaces” così grandi che l’intero insieme di tutti gli stati e le loro azioni e valutazioni non possono essere esplicitamente elencate in una tabella come quella che io ho ipotizzato per il problema del robot nel labirinto. In questo caso le valutazioni di azioni che possono essere effettuate in uno stato devono essere computate piuttosto che memorizzate.

Unsupervised Learning

I metodi del decision tree e del nn learning descritti finora sono esempi di “supervised learning”, un tipo di learning nel quale si tenta di apprendere a classify data da un large sample di training data le cui classifications sono known. La “supervision” che dirige il learning in questi sistemi implica l’informing il sistema riguardo la classification di ciascun datum nel training set. Inoltre, è talvolta possibile costruire utili classificazioni di dati basate solamente sui dati soli. Tecniche per fare ciò cadono sotto la heading di “unsupervised learning”

Ma supponiamo di avere un insieme di unlabeled sample points. Può qualcosa essere appreso da dati di questo tipo? Con una visual inspection, noi vediamo che i punti sembrano essere disposti in tre clusters. Forse ciascun cluster contiene punti che potrebbero essere appartenenti alla stessa categoria. Così, se noi potessimo automaticamente elaborare i data samples per indentificare i clusters e le boundaries tra essi, noi avremmo un metodo di unsupervised learning.

I ricercatori in AI hanno usato molti metodi per identificare clusters di training samples. Uno che è facile da spiegare, è il metodo cosiddetto k-means. Esso funziona ripetendo senza fine i seguenti passi:

1. Installare, forse in locations random, alcuni numeri, diciamo k, di “cluster seekers” nello spazio dei samples.

2. Per ciascuno di questi cluster seekers, un insieme a quei training samples che sono closer ad esso piuttosto che ad ogni altro cluster seekers

3. Computare il “center of gravity” di ciascuno di questi gruppi di campioni

4. Muovere ciascuno dei cluster seekers verso il centro del suo gruppo corrispondente

5. Ripetere questi passi fino a che nessuno dei cluster seekers necessita di essere mosso ancora.

Alla fine di questo processo, i cluster seekers dovrebbero essere tutti ai centroids di gruppi di training samples che possono essere considerati clusters o separate categorie di dati. Ora per classificare alcuni nuovi data point non nel training set, noi semplicemente computiamo a quale cluster seeker esso è il più closest. Il process dipende, ovviamente, dall’essere capace di guess il numero di clusters, k. I metodi per fare ciò generalmente implicano adjusting il numero di essi così che punti all’interno di clusters sono closer insieme rispetto alle distanze tra clusters.

Gli statistici e altri hanno sviluppato molti metodi per clustering data, includendo variations related correlate al metodo k-means. Una tecnica prominente, AutoClass, fu sviluppata da Peter Cheeseman e colleghi alla NASA. Secondo un sito web riguardante AutoClass:

AutoClass prende un database di casi descritti da una combinazione di attributes valued reali e discrete e trova automaticamente le natural classes in quei data. Non è necessario dire quante classes sono presenti o a cosa esse assomigliano – essa estrae questa informazione dai data stessi. Le classi sono descritte probabilisticamente, così che un oggetto può avere partial membership in differenti classi e le definizioni di classe possono sovrapporsi

AutoClass è famoso per aver scoperto una nuova classe di stelle all’infrarosso. Gli statistici raggruppano tutti questi metodi (numerici e non numerici) sotto la generale heading di “cluster analysis”. Un buon sguardo d’insieme può essere trovato online nel Electronic Textbook StatSoft in https://www.tibco.com/products/data-science Il textbook di Duda, Hart e Stork ha una scrupolosa discussione di unsupervised learning (in aggiunta ad altri argomenti in data classification).

ALVINN

Un’altra applicazione di nn per guidare una furgone, fu sviluppata da Dean Pomerleau, uno studente Ph.D. alla CMU. Il sistema che includeva il furgone , una telecamera per guardare la strada davanti e un apparato di interfaccia, fu chiamata ALVINN, un acronimo per Autonomous Land Vehicle in a Neural Network. ALVINN usava il veicolo Navlab della CMU, che fu costruito su un classico furgone commerciale con motore idraulico ed elettrico. Secondo un articolo della CMU, “i computers possono orientare e guidare il furgone con un elettrico servomotore oppure un guidatore umano può prendere il controllo per guidare per un test oppure per escludere il computer”.

L’input alla nn di ALVINN era una array a bassa-risoluzione 30 × 32 di gray-scale image intensity valori prodotti da una videocamera montata sopra il furgone. Ciascuno di questi 960 inputs era connesso a ciascuna delle quattro hidden units attraverso adjustable weights. Le hidden units, a turno, erano connesse a una linea da sinistra a destra di 30 output units attraverso adjustable weights. Le output units controllavano il meccanismo di guida del furgone come segue:

La output unit più centrale rappresenta la condizione “travel straight ahead”, mentre le units a sinistra e a destra del centro rappresentano rispettivamente i giri più forti a sinistra e a destra. Le units all’estrema sinistra e all’estrema destra del output vector rappresentano giri con un raggio di 20m alla sinistra e alla destra rispettivamente, e le units in between rappresentano giri che decrescono linearmente nella loro curvatura in basso alla “straight ahead” middle unit…

La direzione dello sterzo dettata dalla n è presa per essere il centro di massa della “hill” di attivazione circostante la output unit con il più alto livello di activation. Usando il centro di massa di attivazione invece della più attiva output unit determinando così la direzione, permette le correzioni dello sterzo migliorando così la precisione di guida di ALVINN.

Ci furono varie versioni di ALVINN. In una, il training della n era “on-the-fly”, che significa che la n era addestrata in tempo reale come quando il furgone era guidato da un umano lungo varie strade e percorsi. L’angolo desiderato di orientamento era quello selezionato dal guidatore, e i n weights erano adjusted da backprop per tentare di mimare la performance del guidatore. Un problema con questo metodo era che la n non era mai esposta per possibili immagini “going-off-the-road”. Le simulazioni di queste immagini simili (etichettate da ciò che l’angolo di guida sarebbe stato in quei casi) erano aggiunte al training set.

Nel riassumere un tipico test della performance di ALVINN, Pomerleau scrisse

Oltre i tre runs, con la n che guida a 5 mph lungo i 100 metri della strada, la posizione media del veicolo era 1.6 cm a destra del centro, con una deviazione standard di 7.2 cm. Sotto il controllo umano, la average position del veicolo era di 4.0 cm a destra del centro, con una deviazione standard di 5.47 cm.

Il Carnegie Mellon’s Robotics Institute continuò (e ancora continua) a lavorare su veicoli autonomi, sebbene l’approccio n-n per image-guided steering fu rimpiazzato da algoritmi più robusti di computer-vision. Il loro sistema di visual perception del 1995 RALPH (un acronimo per Rapidly Adapting Lateral Position Handler) ha usato speciali routines image-processing per determinare road boundary curvature. Secondo Pomerlau, “RALPH è stato capace di localizzare la strada e guidare autonomamente su un’ampia varietà di tipi di strada sotto molte condizioni differenti. RALPH ha guidato il nostro veicolo Navlab 5 testbed per oltre 3000 miglia su strade che vanno da paths single lane bike, a rural highways, to interstate freeways”.

Nell’estate del 1995, uno dei loro veicoli specialmente attrezzato, un Pontiac Trans Sport (Navlab 5) del 1990 donato dalla Delco Electronincs, guidò autonomamente (usando RALPH) per 2797 delle 2849 miglia da Pittsburgh, PA a San Diego, CA (Solo lo sterzo era autonomo – Pomerleau e lo studente Ph.D. Todd Jochem handled l’acceleratore e il freno). La velocità media era sopra i 60 mph.

NETtalk

Un’applicazione molto interessante del backprop learning method fu sviluppata da Terrence J. Sejnowski e Charles Rosenberg. Essi pensarono ad una NN per talk.! In uno dei loro esperimenti, il loro sistema, chiamato NETtalk, ha appreso a “read” un testo che era stato trascritto da un informale, continuo speech di una bambino di sei anni ed ha prodotto un output acustico (che suonava in modo rimarchevole come quello di un bambino) (Voi potete ascoltare un demo audio

http://cnl.salk.edu/Media/nettalk.mp3

http://archive.ics.uci.edu/ml/datasets/Connectionist+Bench+%28Nettalk+Corpus%29

NETtalk aveva 203 input units progettate per codificare una stringa di sette lettere. Il testo streamed attraverso queste sette units lettera per lettera. C’erano 80 “hidden units” che erano connesse agli inputs da adjustable weights. Era stato previsto che le hidden units avrebbero “formato rappresentazioni interne che erano appropriate per risolvere il mapping problem di lettere per fonemi”. C’erano 26 outputs units che erano ipotizzate per produrre versioni codificate di fonemi, le unità di base dei suoni del parlato. Le output units erano connesse collegate alle hidden units da additional adjustable weights. (In tutto c’erano 18.629 adjustable weights). Infine i phonemic codes erano passati ad uno speech synthesizer commerciale per produrre un output udibile.

La N trained dal comparare, ad ogni passo time, il phonemic code alle output units rispetto a ciò che quel codice sarebbe stato per il text input at that time step. Backprop è stato usato per modificare i weights in un modo che tendeva a ridurre questo error. Gli autori dichiarano che “è stato dimostrato essere possibile far apprendere ad una N con una window di sette lettere in pochi giorni”. (i computers erano molto più lenti nel 1987). Esso hanno concluso che “overall, la intelligibility del speech era assolutamente buona” e che “più parole la N apprendeva più correttamente pronunciava nuove parole”. Dopo il training la fase di apprendimento su un corpus di 1024 parole, la N “tested [senza ulteriore training] su una word continuation di 439 dallo stesso speaker. La performace era del 78% che indica che molto del learning era passato a nuove parole persino anche dopo un sample ridotto di parole in inglese”. In generale, più grandi sono le Ns meglio esse funzionano.

The Backprop Algorithm

Questo problema fu risolto alla metà degli anni ottanta dall’invenzione di una tecnica chiamata “back propagation” (backprop in breve) introdotta da David Rumelhart, Geoffrey E. Hinton e Ronald J. Williams. L’idea base all’interno di backprop è semplice, ma la matematica (che io eviterò) è piuttosto complicata. In risposta ad un errore nell’output della network rete, backprop fa piccoli adjustements in tutti i weights così da ridurre quell’errore. Esso può essere considerato come un metodo hill-climbing (o piuttosto hill-descending) – cercare bassi valori di errore sul contesto di pesi. Ma piuttosto che realmente provare tutti i possibili piccoli weight changes e deciding on that insieme di essi che corrisponde al steepest descent downhill, backprop usa il calculus (analisi matematica) per precompute l’insieme migliore di weight changes.

I lettori che ricordano un po’ del calculus non avranno difficoltà nel recalling che esso può essere usato per calcolare la pendenza (slope) di una curva o di una superficie. L’errore nell’output di una NN può essere pensato come una funzione dei network’s weights, cioè, una superficie nello “weight space”. Questa funzione può essere scritta down e “differentiated” (Calcolare la derivata) (i.e. un’operazione in analisi calculus) rispetto ai weights to yield l’insieme di weight changes che potrebbero take us downhill nella steepest più veloce direzione. Il problema con l’implementazione di questa idea in un modo straightforward per NNs lies nel fatto che queste Ns hanno “thresholds” /limiti, il cui effetto è di popolare l’error surface con improvvisi abrupt “cliffs”/picchi strapiombi (Gli outputs di una N con thresholds/limiti può cambiare da 1 a 0 o da 0 a 1 con infinitesimali piccoli cambiamenti in alcuni dei weight values). Le operazioni dell’analisi richiedono smoothly changing di superfici e sono ostacolati da cuspidi.

Rumelhart e colleghi trattarono questo problema by replacing i thresholds con componenti i cui outputs possono solo cambiare smoothly, anche se essi cambiano assolutamente esageratamente abbastanza per la N per fare approssimativamente la stessa cosa con una N con thresholds. Con queste replacements, il calculus può essere usato per propagate l’error function backward (da output a input) attraverso la N per calcolare l’insieme migliore di cambiamenti ai weight values in tutti i layers della N. Sebbene questo processo di azzeramento in on acceptable weight values è lento, esso è stato usato con notevoli risultati per molti problemi di learning N-N.

In realtà, alcuni ricercatori apparentemente non hanno pensato un’idea simile prima di Rumelhart e i suoi colleghi. I primissimi furono probabilmente Arthur E. Bryson Jr. e Y.C. Ho, che hanno usato “iterative gradient methods” per risolvere “Euler-Lagrange equations”. Paul Werbos, nella sua tesi di Ph.D. ad Harvard, ha anche proposto back-propagating errors per far apprendere multilayer neural networks.

Come con tutte le tecniche di local search, backprop potrebbe rimanere bloccata su quella dei local minima della error surface. Ovviamente, il learning process può essere ripetuto, iniziando con differenti valori iniziali dei weights per tentare di trovare un più basso (o forse il più basso) error value. In ogni caso, il metodo backprop è ancora, come Laveen Kanal scrisse nel 1993, “probabilmente la più ampiamente usata general procedure per far apprendere alle NNs pattern classification”.

I metodi di learning di una NN sono stati applicati in una varietà di aree che includono aircraft control, credit card fraud detection, vending machine currency recognition e data mining.

Neural Networks

Durante gli anni sessanta, i ricercatori di “neural networks” utilizzarono vari metodi per modificare una network che ha adjustable weights, così che l’intera network ha dato risposte come un appropriate output per un insieme di “training” inputs. Per esempio, Frank Rosenblatt alla Cornell ha ottenuto weight values adeguato nel layer finale di quello che egli chiamò il three-layer alpha-perceptron. Bill Ridgway (uno degli studenti a Stanford di Bernard Widrow) adjusted weights nel primo layer di quella che egli ha chiamato MADALINE. Allo SRI hanno ottenuto un simile schema per adjusting weights nel primo layer livello delle macchine di MINOS II e MINOS III. Altri hanno usato varie tecniche statistiche per set weight values. Ma ciò che ha ostacolato tutti era come how to change i weights in più di un layer di reti multilayer networks.

Constructing Decision Trees

A. EPAM

Probabilmente il primissimo sistema per costruire decision trees fu sviluppato negli ultimi anni cinquanta da Edward Feigenbaum come parte della sua dissertazione di Ph.D. con Herbert Simon alla Carnegie Mellon University (poi chiamato Carnegie Institute of Technology). Il suo sistema era chiamato EPAM, un acronimo per Elementary Perceiver and Memorizer. Il goal della ricerca era di “spiegare e prevedere il fenomeno dell’apprendimento verbale [umano]”. Un esperimento psicologico standard per testare questa abilità implicava il mostrare alle persone paia di sillabe nonsense, come DAX-JIR e PIB-JUX. Il primo membro di un paio era chiamato “stimulus” e il secondo “response”. Dopo avere visto un certo numero di queste paia ripetutamente, al soggetto è poi mostrato uno stimulus casuale e testato sul di lui o di lei capacità di generare la risposta corretta.

Paia come queste erano mostrate ad EPAM durante la sua “learning phase”. Il Learning consisteva nella crescita di quella che Feigenbaum ha chiamato una “discrimination net” per memorizzare associazioni tra stimuli e responses. La net era quella che noi ora potremmo chiamare un decision trees con i tests su caratteristiche delle lettere nei nodi interni e le risposte memorizzate alle punte o foglie dell’albero. Nella “testing phase” di EPAM, una sillaba di stimulus senza senso era filtrata attraverso i tests giù l’albero fino alla foglie che erano raggiunte dove (si spera) la corretta risposta era memorizzata.

Non solo EPAM era con successo il modello della performance degli umani in questo “paired-associate” compito di apprendimento, esso anche ha modellato ciò che era stato dimenticato. Feigenbaum dichiarò che “Per quanto ne sappiamo, [EPAM] è la prima concreta dimostrazione di questo tipo di dimenticare in una learning machine”^. EPAM era scritto in IPL-V, il linguaggio list-processing della Carnegie. Infatti, le caratteristiche del list-processing di linguaggi come IPL-V erano richieste per scrivere programmi che potessero far crescere decision trees. Così, non è sorprendente che EPAM fosse il primo di questi programmi.

Il programma di Feigenbaum è ancora considerato come un maggiore contributo sia per le teorie della intelligenza umana sia per la ricerca in AI. Simon, Feigenbaum e altri hanno continuato il lavoro su programmi EPAM, che culminano in EPAM-VI, codificato in IPL-V e funzionanti su un PC.

B.CLS

Il successivo significativo lavoro su learning decision trees fu fatto alla Yale University intorno al 1960. Lì, lo psicologo Carl I. Hovland e il suo studente Ph.D. Earl B. (Buz) Hunt svilupparono un modello al computer del concetto di apprendimento umano.Dopo che Hovland morì nel 1961, Hunt continuò il lavoro su concept learning e collaborò con Janet Marin e Philip Stone nello sviluppare una serie di programmi di learning decision-tree chiamati CLS, un acronimo per Concept Learning System. Hunt e i suoi colleghi riconobbero il lavoro precedente correlato su EPAM.

Per gli scopi di AI almeno, i sistemi CLS furono subito eclissati da altri sistemi di decision-tree learning, cioè, ID3, CART e programmi correlati, Descriverò come funziona ID3 come un modo di spiegare le principali idee alla base di questi programmi.

C.ID3

J. Ross Quinlan sviluppò ID3, un acronimo per Iterative Dichotomizer alla fine degli anni settanta mentre egli era in congedo sabbatico (dalla University of Sydney) a Stanford. (Il nome derivava dal fatto che il programma ha costruito decision trees iterativamente dividendo insiemi di records di dati fino a che essi potevano essere classificati all’interno di una di due distinte categorie. Successive versioni hanno consentito la classificazione all’interno di più di due categorie, ma la “D” è rimasta nel nome). Quinlan era stato precedentemente uno studente Ph.D. (il primo, in effetti) nel Computer Science Department alla University of Washington, lavorando con Earl Hunt.

Ecco, in breve, come ID3 dovrebbe procedere per costruire un decision tree per predicting il valore della response usando il simulato database Wal-Mart. Primo, ID3 dovrebbe cercare questo singolo attribute per usare come il “best” test nel distinguere tra quei data records che hanno il valore yes per il response attribute da quelli che hanno il valore no. Nessun singolo test separa i dati perfettamente, ma supponiamo che location sia migliore rispetto agli altri. Dopo tutto, in questo esempio all dei data records che hanno valore rural per l’attributo location hanno il valore yes per il response attribute e nessuno di quelli ha(nno) il valore no. Ipotizziamo che la preponderanza (ma non tutti) dei data records che hanno il valore suburban hanno il valore yes per il response attribute e che la preponderanza (ma ancora non tutti) dei data records che hanno il valore urban hanno il valore no per il response attribute. Così, la location attribute fa un molto buono (ma imperfetto) lavoro di separare i data records con rispetto all’ attribute response. Un test per il valore dell’attribute location sarebbe così stato usato come il primo test nel decision tree che è stato costruito.

Finora poi, noi avremmo diviso il database all’interno di tre sottoinsiemi, due dei quali hanno data records con valori mixed per l’attributo response. ID3 avrebbe poi applicato la stessa tecnica di splitting a ciascuno di questi due mixed-value sottoinsiemi, trovando per ciascuno di essi la migliore successiva caratteristica da usare come un test. In questo semplice e piuttosto non realistico esempio, i due tests che sarebbero stati usati, cioè, type e customer, ciascuno avrebbe prodotto “pure” splits (cioè, quelle con nessun valore mixed) e noi avremmo concluso con il decision tree.

Se gli splits non erano puri o altrimenti non accettabili, tuttavia, ID3 avrebbe continuato selezion,ando i tests sui risultanti sottoinsiemi di databases fino a che le splits avrebbero dato o not mixed o accettabili risultati.

La scelta di quale attributo testare è critica nel produrre utili decision trees. Nel suo originario programma ID3, Quinlan usò una misura correlata alla “accuracy” della risultante split nel determinare quale attributo usare per il testing. In un lavoro successivo, egli ha usato una misura chiamata “information gain”, nella cui precisa definizione non voglio entrare qui eccetto il dire che essa è quell’attributo i cui valori trasmettono la maggiore “information” circa la categorizzazione ricercata. Quinlan usò la definizione di Claude Shannon per misurare il quantitativo di informazione.

L’interesse in ML basate simbolicamente da parte di Quinlan e altri era principalmente diretto ad apprendere questi tipi di regole dai dati. È assolutamente facile costruire regole da un decision tree tracciando verso il basso i tests per generare la parte “IF” e usare ciò che si trova alle punte per la parte “THEN”. Per esempio, nell’esempio del database Wal-Mart, noi potremmo derivare le seguenti regole dal decision tree:

IF (location=suburban) and (type= ranch) THEN (response=no)

IF (location=suburban) and (type= multi-story) THEN (response=yes)

IF (location=rural) THEN (response=yes)

IF (location= urban) and (customer = yes) THEN (response=no)

IF (location= urban) and (customer= no) THEN (response=yes)

Nel lavoro di Quinlan a Stanford, ID3 era capace di generare decision trees piuttosto grandi, e così rule sets, per prevedere se alcune posizioni fine partita degli scacchi sarebbero finite in una sconfitta per il nero. Per un problema di questo tipo suggerito da Donald Michie, ID3 ha usato 25 attributes (implicanti caratteristiche delle posizioni di pezzi sulla scacchiera) e un database di 29,236 differenti disposizioni del pezzo per costruire un albero con 393 nodi le cui previsioni erano corrette per il 99,74%.

Un problema che deve essere evitato nel costruire decision trees è quello di “overfitting”, cioè, selezionare tests basati su così pochi dati che i risultati del test non catturano relazioni significative nei dati come un tutto. Indipendentemente da quanto grande l’originario database, se una successione di tests eventualmente produce un sottoinsieme che è ancora non puro ma è stato ridotto a troppo pochi data records, ogni tentativo di suddividere quel sottoinsieme avrebbe sovradattato i dati e così non sarebbe stato utile. Per questa ragione, le tecniche di decision-tree learning tipicamente fermano la costruzione dell’albero appena prima che i sottoinsiemi di dati avrebbero troppo pochi records ma che darebbero ancora risultati accettabili.

D. C4.5, CART, and Successors

Quinlan continuò il suo lavoro su sistemi decision-tree-constructing, migliorando la loro potenza e applicabilità. “ID3 era molto semplice – circa 600 righe di PASCAL”. Il suo sistema C4.5 (che aveva circa 9000 righe in linguaggio C) potrebbe funzionare con databases i cui attributes hanno valori numerici continuous in aggiunta a quelli categorical. Esso potrebbe persino trattare databases alcuni dei quali i records avevano perso i valori per alcuni dei loro attributi. Infine, esso aveva metodi per migliorare complessivamente performance dalla potatura di distanza alcune parti dell’albero e per semplificare le regole IF-THEN derivate dagli alberi. Una compagnia commerciale che Quinlan aveva fondato nel 1983 ha commercializzato una migliorata versione di C4.5 chiamata C5.0 (insieme ad una versione per Windows chiamata See5). Anche Donald Michie fondò una compagnia, che indipendentemente ha sviluppato una versione commerciale di ID3 chiamata ACLS.

Uno dei significativi sviluppi in ML durante questo periodo era una fruttuosa collaborazione tra persone di AI e statistici che stavano facendo ricerca applicata su classification, estimation, e prediction. Ciascun gruppo ha appreso dall’altro e ML è diventata molto più ricca. Sebbene molte persone erano implicate in questa collaborazione, potrei menzionare in particolare lo statistico di Stanford Jerome Friedman, che iniziò a lavorare con alcuni studenti Ph.D. in AI di Stanford negli anni novanta. Seguendo il suo precedente lavoro su decision-tree construction, Friedman, in collaborazione con Leo Breiman, Richard Olshen e Charles Stome, ha aiutato lo sviluppo di un sistema chiamato CART, un acronimo per Classification and Regression Trees. CART condivide molte caratteristiche con C4.5 (e infatti, C4.5 ha usato le tecniche di CART per trattare attributes numerici).

Sistemi per learning decision trees sono stati applicati ad un’ampia varietà di data-mining problems.

E. Inductive Logic Programming

Espresse nel linguaggio della propositional logic, le regole IF-THEN prodotte da decision trees hanno la forma P1 Λ P2 Λ … PN → Q. I P e i Q sono proposizioni con nessuna struttura interna. In precedenza, ho già scritto sul predicate calculus nel quale proposizioni chiamate predicates, hanno internal arguments. In quel linguaggio, si potrebbero avere molte di più regole espressive come A(x, y, z)[Father(x, y) Λ Sibling (z, y) → Father (x, z)], per esempio. Molte tecniche sono state sviluppate per learn questi types di “relational” rules da databases e da altri “background knowledge”. Uno dei primi sistemi per learning relational rules fu sviluppato da Quinlan e chiamato FOIL. Poiché le rules apprese hanno la stessa form come fanno le statements nel linguaggio per computer PROLOG (un linguaggio basato sulla logica), il campo dedicato a learning queste regole è chiamato “Inductive Logic Programming” (ILP). Sebbene i metodi ILP implicano un logical apparatus troppo complicato per provare a spiegarlo qui, alcune di esse mostrano una stretta relazione con decision-tree-construction. Ci sono molte applicazioni di ILP, includendo learning relational rules per drug activity, per protein secondary structure e per finite-element mesh design. Questi sono tutti esempi che possono essere chiamati “relational data mining”.

Data Mining and Decision Trees

Data Mining è il processo di estrarre informazione utile da grandi databases. Per esempio, si consideri un database circa il behavior delle persone che hanno una carta di credito. Esso potrebbe includere registrazioni di pagamento, importi medi di acquisto, tassa sui pagamenti ritardati, saldi medi,… Metodi appropriati di data-mining potrebbero rivelare, tra le altre cose, che le persone con alta commisione sui pagamenti ritardati, alti acquisti medi e altre caratteristiche identificate tendono avere alti saldi medi.

Un importante metodo di data-mining usa i dati per costruire decision trees. Consideriamo un database molto semplice per illustrare come i decision trees funzionano. Supponiamo che una compagnia, diciamo la Wal-Mart, mantiene un database nel quale essa archivia informazione riguardante famiglie alle quali essa ha precedentemente spedito buoni sconto per alcuni dei suoi prodotti. Supponiamo che il database ha informazione riguardante la posizione della famiglia (urbana, suburbana o rurale), il tipo di casa (o ranch o a più piani), se o no la famiglia è un precedente cliente di Wal-Mart, e se o no la famiglia ha risposto ad ognuno dei suoi precedenti della posta promozionale. (Ovviamente, questo è solo un inventato esempio illustrativo; io non so in effetti nulla riguardante il reale database della Wal-Mart).

Una rappresentazione tabulare di questo database potrebbe essere simile a questa:

Household	Location	Type	Customer	Response
3014	suburban	ranch	yes	no
3015	rural	multistory	no	yes
…	…	…	…	…
5489	urban	ranch	yes	no

Ciascuna riga nella tabella è chiamata un “record”. Gli items al top di ciascuna colonna sono chiamati “attributes”, e gli elementi in una colonna sono chiamati i “values” del corrispondente attributo

L’analisi di questo database, con metodi che spiegherò nei prossimi post, potrebbero rivelare che il decision tree ha catturato informazione riguardante quali famiglie hanno risposto alla posta promozionale e quali no. I tests su attribute values sono vicini ai nodi interni dell’albero (in boxes rettangoli) e i risultati (se o no c’era una risposta) sono vicini ai tips (o leaves dell’albero). Questo albero potrebbe essere utile per fare previsioni circa le risposte attese precedentemente per inviare un’ altra mail(ing).

I metodi sono stati sviluppati per costruire (cioè, apprendere) dei decision trees come questo (e anche molto più grande di quelli) automaticamente da grandi databases. Descriverò un po’ della storia e come i metodi principali funzionano.

Decision Trees

Il successivo, sulla mia lista di nuovi sviluppi in ML, è la automatic construction di strutture chiamate “decision tree” da grandi databases. I decision trees consistono di sequenze di tests per determinare una categoria o un valore numerico da assegnare a un data record. I decision trees sono particolarmente appropriati per l’uso con dati non-numerici così come con dati numerici. Per esempio, un database del personale dei dipendenti potrebbe includere informazione riguardante un dipartimento di un impiegato, diciamo, marketing, produzione o contabilità. Nel linguaggio del database, i data items come questi sono chiamati “categorical” (per distinguerli dai numerical data). Nei prossimi posts, descriverò queste strutture, i metodi di apprendimento per costruirli automaticamente e alcune delle loro applicazioni.

Case-Based Reasoning

Un sottoinsieme di AI, chiamato “Case-Based Reasoning” (CBR) può essere visto come un tipo generalizzato di memory-based learning. In CBR una stored library di “cases” è usata per aiutare nell’analisi, nell’interpretazione e nella soluzione di nuovi casi. In medicina, per esempio, i records diagnostici e terapeutici per pazienti costituiscono una letteratura di casi; quando un nuovo caso si presenta, casi simili possono essere retrieved se consultati dalla letteratura per aiutare nella diagnosi e nella terapia. Nella giurisprudenza anglosassone (a differenza di quella di origine romana) la legge si basa su precedenti usati nelle interpretazioni di e nelle decisioni circa nuovi casi (seguendo la pratica legale di stare decisis che affida ad un mandatario quei casi che sono decisi sulla base di una serie di precedenti casi).

Casi che sono simili ad un nuovo caso possono essere pensati considerati come i suoi “neighbors” in uno generalizzato “space” di casi. Per retrieve close neighbors, l’idea di closeness in questo spazio deve essere basata su alcune misure di affinità. Una delle pioniere in case-based reasoning, Janet Kolodner, professoressa di computing and cognitive science al Georgia Institute of Technology, descrive il processo come segue:

Good cases [per retrieval il recupero] sono quelli che hanno il potenziale per fare rilevanti revisioni circa il nuovo caso. Il recupero è fatto usando caratteristiche del nuovo caso come indici all’interno della raccolta del caso. I casi etichettati da sottoinsiemi di quelle caratteristiche o dalle caratteristiche che possono essere derivate da quelle caratteristiche sono richiamati [Noi poi allora selezioniamo tra questi] il più promettente caso o casi per arguire logicamente ….Talvolta è appropriato scegliere il caso migliore; talvolta uno ridotto insieme è necessario.

Quando il caso retrieved (o i casi) è adattato ad essere applicato ad un nuovo caso esso potrebbe poi (se ha avuto successo) essere rivisto cosicché le parti che potrebbero essere utili per la soluzione di problemi futuri possono essere conservate nella sempre crescente raccolta dei casi.

Il case-based reasoning ha radici nel modello di memoria dinamica di Roger Schank. Il primo lavoro fu fatto da due Ph.D. studenti di Schank, Janet Kolodner e Michael Lebowitz. Un’altra importante fonte di idee per CBR deriva dalle idee di Minsky circa i frames. Edwina Rissland, professoressa alla University of Massachusetts ad Amherst e un’altra pioniera in CBR, scrive che il suo lavoro sul CBR è una diretta conseguenza del di lei lavoro su ‘constrained example generation’,…che ha modellato la costruzione di nuovi esempi dalla modificazione di esistenti esempi ‘close’ passati (rappresentati come frames) recuperati da una network di esempi”. Rissland e i suoi studenti hanno dato importanti contributi all’uso di CBR in giurisprudenza.

Secondo una pagina web mantenuta dall’Artificial Intelligence Applications Institute alla University of Edinburgh, “Case-based Reasoning è una delle tecnologie di AI applicate con maggior successo nei recenti anni. Applicazioni commerciali e industriali possono essere sviluppate rapidamente ed esistenti databases aziendali possono essere usati come knowledge sources (Kss). Helpdesks e sistemi diagnostici sono le più comuni applicazioni.”