• Non ci sono risultati.

Apprendimento Automatico

N/A
N/A
Protected

Academic year: 2022

Condividi "Apprendimento Automatico"

Copied!
33
0
0

Testo completo

(1)

Apprendimento Automatico

Libro di riferimento: Apprendimento Automatico, Tom Mitchell, McGraw Hill, 1998 Tutorial su SVM e Boosting

Lucidi

http://www.math.unipd.it/˜sperduti/ml.html

Alessandro Sperduti

(2)

Contenuti del corso

Concetti fondamentali dell’apprendimento automatico

Apprendimento on-line: alcuni semplici algoritmi e loro analisi teorica Apprendimento di alberi di decisione

Boosting Reti Neurali

Support Vector Machines Apprendimento probabilistico Apprendimento con rinforzo

Esperienze pratiche in laboratorio

(3)

Apprendimento on-line

Schema generale

(4)

Apprendimento alberi di decisione

Outlook

Overcast

Humidity

Normal High

No Yes

Wind

Strong Weak

No Yes

Yes Sunny Rain

Boosting (di alberi di decisione)

(5)

Reti Neurali

Neurone biologico

Neurone artificiale

w1

w2 w0

x1 x2

x0 = 1

. .

.

Σ

net = i=0Σ wi xi n

o = σ(net) = sign(net)1

(6)

Reti Neurali

f() = −1 f() = +1

f() = +1

f() = −1

(7)

Support Vector Machines

non−optimal

optimal w

(8)

Apprendimento Probabilistico

0 0.2 0.4

0.6 0.8 1

x 0 0.20.40.60.81

0 y 0.51 1.52 2.53 3.54

P(y |x)

0 0.2 0.4 0.6 0.8 1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

y

x

(9)

Apprendimento con rinforzo

AGENTE

AMBIENTE

ricompensa azione

stato

Goal: apprendere le azioni che massimizzano

            dove 

(10)

Quando `e Necessario l’Apprendimento (Automatico) ?

Quando il sistema deve...

adattarsi all’ambiente in cui opera (anche personalizzazione automatica);

migliorare le sue prestazioni rispetto ad un particolare compito;

scoprire regolarit `a e nuova informazione (conoscenza) a partire da dati empirici;

acquisire nuove capacit `a computazionali.

Perch `e non usare un approccio algoritmico tradizionale ?

impossibile formalizzare esattamente il problema (e quindi dare una soluzione algoritmica);

presenza di rumore e/o incertezza ;

complessit `a alta nel formulare una soluzione: non si pu `o fare a mano;

mancanza di conoscenza “compilata” rispetto al problema da risolvere;

(11)

Ruolo dei Dati

Tipicamente...

si hanno a disposizione (molti ?) dati – ottenuti una volta per tutte;

– acquisibili interagendo direttamente con l’ambiente;

(forse) conoscenza del dominio applicativo, ma – incompleta;

– imprecisa (rumore, ambiguit `a, incertezza, errori, ...);

Desiderio: usare i dati per

ottenere nuova conoscenza;

raffinare la conoscenza di cui si dispone;

correggere la conoscenza di cui si dispone;

(12)

Es. - Riconoscimento di Cifre Manoscritte

impossibile formalizzare esattamente il problema: disponibili solo esempi;

possibile presenza di rumore e dati ambigui;

(13)

Es. - Guidare una Automobile

Sharp Left

Sharp Right

4 Hidden Units

30 Output Units

30x32 Sensor Input Retina Straight

Ahead

(14)

Es. - Estrarre Conoscenza Medica dai Dati

Patient103 Patient103 ... Patient103

time=1 time=2 time=n

Age: 23

FirstPregnancy: no Anemia: no

Diabetes: no

PreviousPrematureBirth: no

...

Elective C−Section: ? Emergency C−Section: ?

Age: 23

FirstPregnancy: no Anemia: no

PreviousPrematureBirth: no Diabetes: YES

...Emergency C−Section: ? Ultrasound: abnormal Elective C−Section: no

Age: 23

FirstPregnancy: no Anemia: no

PreviousPrematureBirth: no

...

Elective C−Section: no Ultrasound: ?

Diabetes: no

Emergency C−Section: Yes

Ultrasound: ?

(15)

Linee di Ricerca all’interno dell’ Apprendimento Automatico

induzione di regole/alberi di decisione, algoritmi connessionisti (reti neurali),

“clustering” & “discovery”,

apprendimento basato sulle istanze apprendimento Bayesiano,

apprendimento basato sulla spiegazione, apprendimento con rinforzo,

apprendimento induttivo guidato dalla conoscenza, ragionamento per analogia & basato sui casi,

algoritmi genetici,

programmazione logica induttiva,

(16)

Principali Paradigmi di Apprendimento

Apprendimento Supervisionato:

dato in insieme di esempi pre-classificati, 

      

, apprendere una descrizione generale che incapsula l’informazione contenuta negli esempi (regole valide su tutto il dominio di ingresso)

tale descrizione deve poter essere usata in modo predittivo (dato un nuovo ingresso  predire l’output associato  



)

si assume che un esperto (o maestro) ci fornisca la supervisone (cio `e i valori della



per le istanze dell’insieme di apprendimento)

Esempio di applicazione: classificazione di caratteri manoscritti

(17)

Principali Paradigmi di Apprendimento

Apprendimento Non-supervisionato:

dato in insieme di esempi 



  

, estrarre regolarit `a e/o pattern (valide(i) su tutto il dominio di ingresso)

non esiste nessun esperto (o maestro) che ci fornisca un aiuto

Clustering

x2

x cluster

1

Scoperta di Regole (Discovery)

Esempio di applicazione: data mining su database strutturati

(18)

Principali Paradigmi di Apprendimento

Apprendimento con Rinforzo:

Sono dati:

agente (intelligente ?), che pu `o trovarsi in uno stato  , ed

eseguire una azione  (all’interno delle azioni possibili nello stato corrente) – ed opera in un ambiente  , che applicando una azione  nello stato 

restituisce

lo stato successivo, e

una ricompensa , che pu `o essere positiva (+), negativa (-), o neutra (0).

Scopo dell’agente `e quello di massimizzare una funzione delle ricompense (es. ricompensa scontata:

       dove  )

Esempio di applicazione: navigare sul Web alla ricerca di informazione focalizzata

(19)

Ingredienti Fondamentali Apprendimento Automatico

Dati di Allenamento (estratti dallo Spazio delle Istanze, ) Spazio delle Ipotesi, 

– costituisce l’insieme delle funzioni che possono essere realizzate dal sistema di apprendimento;

– si assume che la funzione da apprendere

possa essere rappresentata da una ipotesi    ... (selezione di  attraverso i dati di apprendimento) – o che almeno una ipotesi    sia simile a

(approssimazione);

Algoritmo di Ricerca nello Spazio delle Ipotesi, alg. di apprendimento

ATTENZIONE:  non pu `o coincidere con l’insieme di tutte le funzioni possibili e la ricerca essere esaustiva  Apprendimento `e inutile!!!

(20)

Spazio delle Ipotesi: Esempio 1

Iperpiani in 

Spazio delle Istanze  punti nel piano:  

 

Spazio delle Ipotesi  dicotomie indotte da iperpiani in :

                        ! " #    # "



+ w

f() = +1 f() = −1

w y + b = 0.

(21)

Spazio delle Ipotesi: Esempio 2

Dischi in 

Spazio delle Istanze  punti nel piano:  

 

Spazio delle Ipotesi  dicotomie indotte da dischi in centrati nell’origine:

                 

   " # "



f() = +1

f() = −1

cerchio

y y − b = 0.

+

(22)

Spazio delle Ipotesi: Esempio 3

Congiunzione di letterali positivi

Spazio delle Istanze  stringhe di  bit:  

  

  # 

Spazio delle Ipotesi  tutte le sentenze logiche che riguardano i letterali positivi

 # # 

 ( `e vero se il primo bit vale 1,  `e vero se il secondo bit vale 1, etc.) e che contengono solo l’operatore (and):

      

        

    

 



   

#  # #    

 # # 

Es.    ,  

 #

 

Esempi di istanze       ,     ,       ,     

Esempi di ipotesi     ,    ,    ,  !   ,  "  





Notare che:  , , e  " sono false per  ,  e   e vere per  ;  `e vera per ogni istanza;

`e vera per e ma falsa per e

(23)

Principali Paradigmi di Apprendimento: Richiamo

Apprendimento Supervisionato:

dato in insieme di esempi pre-classificati, 

      

, apprendere una descrizione generale che incapsula l’informazione contenuta negli esempi (regole valide su tutto il dominio di ingresso)

tale descrizione deve poter essere usata in modo predittivo (dato un nuovo ingresso  predire l’output associato

 



)

si assume che un esperto (o maestro) ci fornisca la supervisone (cio `e i valori della 

per le istanze dell’insieme di apprendimento) Find-S `e un algoritmo di apprendimento supervisionato

(24)

Dati

Consideriamo il paradigma di Apprendimento Supervisonato Dati a nostra disposizione (off-line)

Dati

           

    

Suddivisione tipica (       ) : Training Set

           

      

usato direttamente dall’algoritmo di apprendimento;

Test Set

           

      

usato alla fine dell’apprendimento per stimare la bont `a della soluzione.

Test Set Training Set

(25)

Dati (cont.)

Se abbastanza grande il Training Set e ulteriormente suddiviso in due` sottoinsiemi (         ) :

Training Set’

           

      

usato direttamente dall’algoritmo di apprendimento;

Validation Set

           

        

usato indirettamente dall’algoritmo di apprendimento.

Il Validation Set serve per scegliere l’ipotesi    migliore fra quelle consistenti con il Training Set’

Test Set

Validation Set

Training Set’

Training Set

(26)

Errore Ideale

+

+

-

-

c h

Instance Space X

-

Where c

and h disagree

Supponiamo che la funzione



da apprendere sia una funzione booleana (concetto):

    #   #! 

Def: L’Errore Ideale (   

  

) di una ipotesi  rispetto al concetto



e la distribuzione di probabilit `a (probabilit `a di osservare l’ingresso   ) `e la probabilit `a che  classifichi

erroneamente un input selezionato a caso secondo : 

(27)

Errore di Apprendimento

+

+

-

-

c h

Instance Space X

-

Where c and h differ

h1

0

h2

Dato  = Training Set’, pi `u ipotesi possono essere consistenti:   ,  , quale scegliere ? Def: L’Errore Empirico (      

) di una ipotesi  rispetto a  `e il numero di esempi che  classifica erroneamente:           #     

          

Def: Una ipotesi  `e sovraspecializzata (overfit)  se    tale che

             

 

, ma    

         

.

(28)

VC-dimension

Definizione: Frammentazione (Shattering)

Dato   , `e frammentato (shattered) dallo spazio delle ipotesi se e solo se

   #   # tale che   #         

( realizza tutte le possibili dicotomie di ) Definizione: VC-dimension

La VC-dimension di uno spazio delle ipotesi definito su uno spazio delle istanze  `e data dalla cardinalit `a del sottoinsieme pi `u grande di  che `e frammentato da :

     

  frammenta

    se non `e limitato

(29)

VC-dimension: Esempio

Quale `e la VC-dimension di ?

                        ! " #    # "



+ w

iperpiano

f() = +1 f() = −1

w y + b = 0.

(30)

VC-dimension: Esempio

Quale `e la VC-dimension di ?

    banale. Vediamo cosa succede con 2 punti:

+ w

+ w w

+ w

+

+ + +

+

(31)

VC-dimension: Esempio

Quale `e la VC-dimension di ? Quindi  

   . Vediamo cosa succede con 3 punti:

+

+ +

+

+

+

+

+

+

+

+

+

+ w

+

+ +

+ + +

+

(32)

VC-dimension: Esempio

Quale `e la VC-dimension di ? Quindi  

   . Cosa succede con 4 punti ?

(33)

VC-dimension: Esempio

Quale `e la VC-dimension di ? Quindi  

   . Cosa succede con 4 punti ? Non si riesce a frammentare 4 punti!!

Infatti esisteranno sempre due coppie di punti che se unite con un segmento provocano una intersezione fra i due segmenti e quindi, ponendo ogni coppia di punti in classi diverse, per separarli non basta una retta, ma occorre una curva. Quindi 

   

Riferimenti

Documenti correlati

Input: Una matrice C che rappresenta un insieme Θ di vincoli Output: true if Θ is consistente, false altrimenti. else scegli una relazione C[i, j] non processata

Neural Networks: nonlinear/linear neurons, number of hidden units, η, other learning parameters we have not discussed (e.g., momentum µ) Hold-out or Cross-Validation can be used

Supponendo una distribuzione a priori uniforme sulle ipotesi corrette in H, Seleziona una qualunque ipotesi da VS , con probabilit` a uniforme Il suo errore atteso non ` e peggiore

destinata a essere sottoscritta da tutti” fa sembrare che l’esistenza medesima della verità e della realtà dipenda da fatti casuali come la continuazione della razza e della

Dalla tabella si può desumere che la competenza globale fono/cherologica è cresciu- ta velocemente; la produzione dei singoli parametri, configurazione e luogo, che fin dall’inizio

Risposta: considerando che tutte le formule non soddisfacibili sono equivalenti alla funzione sempre falsa, allora non consideriamo formule dove compare un letterale sia affermato

Nell’ambito dell’iniziativa Avanguardie educative di Indire è stato possibile individuare esempi di scuole che hanno deciso di ripensare gli ambienti interni della scuola a