Dipartimento di Ingegneria dell’Informazione Università degli Studi di Parma Intelligenza Artificiale Apprendimento Agostino Poggi Stefano Cagnoni Introduzione La capacità di apprendimento è fondamentale in un sistema “intelligente” per: Risolvere nuovi problemi. Non ripetere gli errori fatti in passato. Risolvere problemi in modo migliore o più efficiente. Avere autonomia nell’affrontare e risolvere problemi (in modo indipendente da un esperto che fornisce la conoscenza). Adattarsi ai cambiamenti dell’ambiente circostante. Un sistema senza queste caratteristiche difficilmente potrebbe essere considerato intelligente. Apprendimento 2 Definizione e Obiettivi Estrarre conoscenza dal ripetersi di situazioni esperienza stato comportamento Partendo da un minimo livello di conoscenza, utilizzare un metodo di apprendimento generale per acquisire, via via, nuova conoscenza. Partendo da un sistema che include già conoscenza strutturata si cerca di incrementarla o strutturarla ulteriormente. Apprendimento 3 Apprendimento Induttivo Viene utilizzato per apprendere dei concetti espressi in genere con delle regole la cui forma è: «nella situazione X esegui l’azione Y». azione1 situazionen ... situazionegen azionegen situazione1 Apprendimento azionen 4 Apprendimento Induttivo oggetto1 è un corvo ... oggetton è un corvo oggetto1 è nero oggetton è nero ?x è un corvo ?x è nero Più in generale un algoritmo di apprendimento induttivo esegue il seguente compito: «dato un insieme di esempi (campioni) di f, definisci una funzione h (ipotesi) che approssima f». Apprendimento 5 Alberi di Decisione Esempio del ristorante: vale la pena attendere la disponibilità di un tavolo ? Alt Bar Fri/ Sa Hu n Patr Rain Re s Wtim e Go al yes yes no yes Ye s no no no no yes no no yes yes no no no yes Ye s no no yes yes no yes no yes no so m e fu ll so m e fu ll fu ll so m e n on e no no no no no yes yes yes no no yes yes yes no 0 -1 0 3 0 -6 0 0 -1 0 1 0 -3 0 >6 0 0 -1 0 0 -1 0 YES NO YES YES YES YES NO Esempi positivi : decisione YES Esempi negativi: decisione NO Apprendimento 6 Alberi di Decisione Patrons none full some No Yes >60 WaitTime 30-60 No Alternate no No Apprendimento yes no Bar Yes No yes Yes Yes yes Yes Yes yes no Fri/Sat no 0-10 Hungry yes Reservation no 10-30 Alternate no Yes yes Raining no No yes Yes 7 Alberi di Decisione Come si opera per imparare dagli esempi la funzione di decisione booleana che basata sul valore degli attributi ? Scegliere l’attributo che meglio separa gli esempi positivi da quelli negativi. Se l’attributo divide tutti gli esempi negativi da quelli positivi, allora abbiamo trovato la funzione. Altrimenti bisogna applicare il primo punto ricorsivamente sui sottoinsiemi generati dall’algoritmo. L’iterazione termina anche nel caso in cui non abbiamo trovato la funzione, ma non abbiamo più attributi da utilizzare per suddividere gli esempi. Questo può accadere se abbiamo: Dati scorretti / conoscenza incerta Informazioni insufficienti. Apprendimento 8 Alberi di Decisione Se troviamo una funzione che non usa tutti gli attributi ci possono essere problemi? Possibile sotto utilizzo delle informazioni disponibili L’albero creato è l’unico possibile? Se non lo è, è il migliore possibile? Se troviamo una funzione che usa tutti gli attributi ci possono essere problemi? Tutti gli attributi sono utilizzati per il loro effettivo contenuto informativo o ‘per far tornare le cose’ (overfitting) ? Come si scelgono gli attributi? Apprendimento 9 Alberi di Decisione Approccio basato sulla teoria dell’informazione Bisogna scegliere prima quelli che hanno un valore informativo maggiore, ossia il migliore guadagno informativo: Gain(A) = I(p/(p+n),n/(p+n)) - ipi+ni)/(p+n) I(pi/(pi+ni),ni/(pi+ni)) [ p/(p+n) P(p), n/(p+n) P(n) ] dove I(P(p),P(n)) = -P(n)log2P(n) - P(p)log2P(p) è il contenuto informativo di una corretta risposta yes/no con probabilità P(p) e P(n) rispettivamente. Apprendimento 10