3.4.6 Apprendimento automatico e alberi di decisione

L'apprendimento automatico rappresenta una delle aree fondamentali dell'intelligenza artificiale (IA) e si occupa della realizzazione di sistemi e algoritmi che si basano su osservazioni come dati per la sintesi di nuova conoscenza (ragionamento induttivo). L'apprendimento può avvenire catturando caratteristiche di interesse provenienti da esempi, strutture dati o sensori, per analizzarle e valutarne le relazioni tra le variabili osservate. Abbiamo tre tipologie di apprendimento automatico: supervisionato, non supervisionato e con rinforzo.

La definizione formale è dovuta a Mitchell: "un programma apprende da una certa esperienza E se: nel rispetto di una classe di compiti T, con una misura di prestazione P, la prestazione P misurata nello svolgere il compito T è migliorata dall'esperienza E".

 


 

CLASSIFICAZIONE BAYESIANA. Noti i dati X, la classe C che emerge ha una probabilità condizionale data dal teorema di Bayes. La likelihood e la probabilità a priori vengono apprese tramite un "training". Con il giungere di nuovi dati la classe viene modificata scegliendo quella che massimizza la probabilità a posteriori, considerando a priori le classi apprese fino a quel punto.

Considerando un vettore x=[xi] di N attributi booleani vogliamo esprimere una classificazione booleana y a questo vettore. Per trovare P(y) bastano un centinaio di esempi per avere distribuzione a meglio del 10%. Per trovare P(x|y) il problema è più complesso (l'argomento assume complessivamente 2N+1 valori differenti e dobbiamo stimare 2(2N-1) parametri i quali con N = 30 sono più di 2 miliardi) e si introducono le ipotesi Naive Bayesian Learning di indipendenza condizionale da parte degli attributi x. In tal modo la complessità dell'apprendimento viene ridotta. In due dimensioni abbiamo P(x1,x2|y) = P (x1|x2,y) P(x2|y) = P(x1|y) P(x2|y)  e sulle classi yk si sceglie quella y con probabilità massima a posteriori.

Se ognuna delle N variabili x può assumere J valori diversi e ci sono K classi, allora in totale ci sono N K (J-1) parametri da stimare, più accessibili che nel caso completo. Se ci sono valori continui e classi discrete, in modellizzazione gaussiana si scelgono 2NK parametri + la forma della P(y) (in generale altri K-1 parametri). Nel caso particolare gaussiano con due classi (booleane) e varianza indipendente dalla classe abbiamo P(y=0|x) e P(y=1|x) (un elemento di input appartiene alla classe 0 se P0>P1) con forme logistiche.

Abbiamo visto un caso di apprendimento supervisionato. Ci sono anche situazioni di apprendimento non supervisionato, come il programma AUTOCLASS della NASA e progetti analoghi.
 


 

Approfondiamo alcuni aspetti dell'apprendimento automatico. Un sistema che apprende cambia nel tempo, arricchendo la propria base di conoscenze, migliora il proprio comportamento e generalizza da casi particolari con regole generali applicabili a casi ancora non incontrati. Tale ragionamento è induttivo, per cui ogni sua condizione potrebbe sempre rivelarsi falsa (basta che esista una caso non osservato che contraddice le conclusioni), le premesse false si preservano e infine da tutte premesse vere possono esistere ancora conclusioni false.

APPRENDIMENTO DA ESEMPI. L'apprendimento da esempi (supervisionato) è in genere costoso - ha bisogno di un esperto e di tempo per allenarsi - ma generalmente ha buone prestazioni. DEFINIZIONE: dato un insieme di esempi positivi o negativi di un certo fenomeno, il sistema deve indurre una regola di classificazione in grado di riconoscere tutti gli esempi positivi e di scartare tutti gli esempi negativi. OSSERVAZIONE: è un tipo di apprendimento cooperativo: l’insegnante fornisce dei buoni esempi e l’allievo ha il compito di estrapolare dagli esempi una regola generale. APPLICAZIONI: classificazione di notizie, diagnosi medica, previsioni del tempo, consigli, elaborazione del linguaggio. FORMALIZZAZIONE DEL PROBLEMA: istanze (con attributi che assumono valori), concetto (funzione C(x)), esempi di allenamento, ipotesi (approssimazione del concetto). PROCEDIMENTO: 1. definire il compito 2. proprietà rilevanti 3. esempi rappresentativi 4. algoritmo che produce un classificatore 5. il classificatore viene usato per altre istanze. ALGORITMO DI GENERALIZZAZIONE: 0. inizializza h alla ipotesi più specifica 1. per ogni esempio positivo x e per ciascun attributo a in h SE a è soddisfatto da x ALLORA non fare niente ALTRIMENTI sostituisci a in h con il primo vincolo più generico che soddisfi x 2. restituisci h.

  


 

ALBERI DI DECISIONE. Un grafico dato da un insieme di regole SE-ALLORA viene definito albero di decisione, in modo che possiamo costruire una regola che congiunge la radice dell'albero con ogni nodo foglia (concetto da apprendere), sapendo che ci sono nodi intermedi (test da effettuare sugli attributi). Il procedimento per costruire un albero di decisione è 1. la selezione di un attributo "a" e creazione per esso di un nodo, 2. creazione per ogni valore di "a" di un nodo figlio, 3. associazione ad ogni figlio delle entità dell’insieme di allenamento che soddisfano il valore dell’attributo considerato, per cui 4. SE tali entità appartengono tutte alla stessa classe ALLORA si crea un nodo foglia per quella classe, ALTRIMENTI si considera un altro attributo. Una osservazione importante è questa: nella scelta degli attributi sono migliori quelli maggiormente informativi rispetto a una certa classe, per cui 1. l’attributo ideale dovrebbe permetterci di dividere gli elementi dell’insieme di addestramento in sottoinsiemi omogenei (puri), tali per cui gli elementi di ciascun sottoinsieme appartengano ad una sola classe; 2. sono quindi da preferirsi attributi che minimizzano l’impurità dei sottoinsiemi individuati da un attributo. Per calcolare la quantità di impurità presente in un sottoinsieme si usa la nozione di entropia, definita dalla teoria dell’informazione.

 


 

ENTROPIA E APPRENDIMENTO AUTOMATICO. Se p(c) è la probabilità che una certa entità faccia parte di una certa classe (un concetto da apprendere) allora in generale l'entropia del sistema T è data, come al solito, da

Entropia(T) = Sommac[ –p(c) log2(p(c))]

Se abbiamo esempi positivi e negativi i contributi nella somma sono due p(+) e p(-), per cui tale misura indica quanti bit sono necessari per comunicare una certa classificazione di un esempio estratto dall’insieme T. Se l’entropia è 0 (nessun bit) significa che non è necessario nessun messaggio; se l’entropia è 1 significa che un bit di informazione deve essere trasmesso (ad esempio: l’entropia sarà 0 se tutti gli esempi appartengono alla stessa classe (tutti positivi o tutti negativi) e sarà 1 se c’è un numero uguale di esempi positivi e negativi).

GUADAGNO. Definiamo una misura per stimare l’efficacia di un certo attributo A per classificare gli esempi di addestramento contenuti nell’insieme T. Il guadagno dell’attributo A sarà dato dalla diminuzione dell’entropia di T dopo aver scelto l’attributo A, calcolata su tutti i sottoinsiemi in cui A ha suddiviso gli esempi di T.

 


 

VALUTAZIONE DI IPOTESI. Per completare il quadro passiamo in rassegna alcune tecniche di calcolo delle ipotesi. In primo luogo come si calcola il numero delle potenziali entità diverse presenti in un dominio? Per ogni attributo si contano i valori che può ammettere e si moltiplicano fra loro, ottenendo la cardinalità dello spazio delle entità. Successivamente ci chiediamo: dato uno spazio delle entità fissato, quanti concetti diversi si possono costruire quindi apprendere? Consideriamo che qualsiasi raggruppamento diverso di una o più entità può essere un concetto. Quindi occorre calcolare l’insieme potenza dello spazio delle entità (2|X| dove |X| è la grandezza dello spazio delle entità; sono in genere tantissime combinazioni, anche disgiunzioni di attributi) che nel caso di congiunzione di attributi (come nell'algoritmo di generalizzazione precedente) sono drasticamente minori in quanto per ogni attributo si contano i valori che può ammettere più il simbolo ? (qualunque), si moltiplicano fra loro e si somma 1 per tutti i concetti che presentano ∅ (nessuno).

Questa riduzione dello spazio delle ipotesi si basa su una preferenza induttiva che l’algoritmo assegna alle ipotesi in forma congiuntiva: implicitamente si assume che il concetto da apprendere sia all’interno di questo spazio ridotto. Ogni algoritmo di apprendimento, implicitamente, assegna una preferenza ad un certo sottoinsieme delle ipotesi. Nel caso degli alberi di decisione la preferenza induttiva è data agli alberi (ipotesi) più semplici in cui i nodi con la maggior stima di guadagno sono posti più vicini alla radice.

Abbiamo dunque una metodologia per realizzare un sistema di apprendimento automatico: 1. Selezione dei dati sperimentali, 2. Annotazione degli esempi positivi e negativi, 3. Selezione dei dati di addestramento e dei dati di valutazione, 4. Scelta delle proprietà rilevanti delle entità, 5. Scelta dell’algoritmo di apprendimento, 6. Addestrare il classificatore sui dati di addestramento, 7. Applicare il classificatore sui dati di valutazione, 8. Valutazione delle prestazioni dell’algoritmo, 9. Se le prestazioni non sono soddisfacienti tornare al punto 1 e verificare che ad ogni fase siano state effettuate le scelte migliori.

MISURE DI VALUTAZIONE . Una matrice di contingenza permette di confrontare i risultati ottenuti (automaticamente) da un sistema di apprendimento con le classificazioni corrette (manuali) sullo stesso insieme di dati di valutazione. Avremo dunque dati di valutazione TP: veri-positivi, TN: veri-negativi, FP: falsi-positivi, FN: falsi-negativi. Possiamo dunque misurare l'accuratezza

(TP + TN) / (TP + TN + FP + FN)

il margine di errore

(FP + FN) / (TP + TN + FP + FN)

la precisione

TP / (TP +FP)

la copertura

TP / (TP + FN)

e la misura F, che combina in una unica misura la precisione (P) e la copertura (R), ottenendo una stima complessiva delle prestazioni di un classificatore:

F = 1 / ( a / P + (1 - a) / R )

Il parametro "a" serve per considerare un diverso apporto di precisione e copertura. Se a = 0,5, la formula si può semplificare con 2PR/(R + P). Se a è maggiore di 0,5 allora viene premiata la precisione.

 


 

Un possibile sviluppo pratico di ricerca sugli alberi di decisione può essere lo studio del software open-source "WEKA", scritto in java (vedi qui su wikipedia.it per informazioni).

 

Tratto da wikipedia.org/wiki/Apprendimento_automatico (con bibliografia annessa), dal corso di Intelligenza Artificiale di Bernardo Magnini (lezioni 18-21) e dal corso di ph.D di Edoardo Milotti.