Machine Learning

20
 Apprendimento e Approssimazione 31 gennaio 2011 Tipi di apprendimento  Supervisionato: c’` e un supervisore che fornisce gli esempi corredati di classicazione.  Non supervisionato: il learner deve riconoscere schemi nell’input senza indicazioni sui valori in uscita (ovvero sulla classicazione).  Per rinforzo: pi` u generale, apprendere in base alle risposte dell’ambiente e alle proprie azioni. In base all’esperienza a disposizione l’apprendimento sar` a uno di questi tipi. In base al controllo che il learner ha dell’esperienza sar`a apprendimento attivo o passivo. Concept learn Fare inferenza su una funzione a valori booleani a partire da esempi di training del suo input e outp ut. Una ipotesi h ` e un insieme di va lori di attr ibuti. Ogni valore pu` o essere:  specicato.  non importante ?.  nullo  . Un esempio di ipotesi potrebbe essere:  < sunny  ? ?  strong  ? same >. Un trai- ning examples ` e: esempi positivi e negativi della funzione target:  < x 1 ,c(x 1 )  > ,...,< x n ,c(x n )  >. Bis ogn a det ermina re se un ipote si  h  ∈  H  ` e tale per cui h(x) =  c(x)x ∈ X .  # istanze distinte= prodotto di tutti i possibili valori degli attributi.  # concetti distint i= insieme delle parti delle istanze.  # ipotesi sintatticamente distinte= prodotto di tutti i possibili valori degli attributi ad ognuno dei quali va aggiunto il valore don’t care e null.  # ipotesi semanticamente distinte= prodotto di tutti i possibili valori degli attributi ad ognuno dei quali va aggiunto il valore don’t care e null conta come uno. 1

Transcript of Machine Learning

Page 1: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 1/20

 

Apprendimento e Approssimazione

31 gennaio 2011

Tipi di apprendimento

• Supervisionato: c’e un supervisore che fornisce gli esempi corredati diclassificazione.

• Non supervisionato: il learner deve riconoscere schemi nell’input senzaindicazioni sui valori in uscita (ovvero sulla classificazione).

• Per rinforzo: piu generale, apprendere in base alle risposte dell’ambientee alle proprie azioni.

In base all’esperienza a disposizione l’apprendimento sara uno di questi tipi. Inbase al controllo che il learner ha dell’esperienza sar a apprendimento attivo opassivo.

Concept learn

Fare inferenza su una funzione a valori booleani a partire da esempi di trainingdel suo input e output. Una ipotesi h e un insieme di valori di attributi. Ogni

valore puo essere:

• specificato.

• non importante ?.

• nullo ∅.

Un esempio di ipotesi potrebbe essere: < sunny ? ? strong ? same >. Un trai-ning examples e: esempi positivi e negativi della funzione target: < x1, c(x1) >,...,< xn, c(xn) >. Bisogna determinare se un ipotesi h ∈ H  e tale per cuih(x) = c(x)∀x ∈ X .

• # istanze distinte= prodotto di tutti i possibili valori degli attributi.

• # concetti distinti= insieme delle parti delle istanze.

• # ipotesi sintatticamente distinte= prodotto di tutti i possibili valori degliattributi ad ognuno dei quali va aggiunto il valore don’t care e null.

• # ipotesi semanticamente distinte= prodotto di tutti i possibili valori degliattributi ad ognuno dei quali va aggiunto il valore don’t care e null contacome uno.

1

Page 2: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 2/20

 

Esempio di learning task

Date:

• Istanze X: i giorni possibili, ognuno dei quali descritto dagli attributisky,temp...ognuno dei quali ha diversi valori possibili.

• Ipotesi H: ogni ipotesi e descritta da particolari vincoli sugli attributi. Ivincoli possono essere un valore specifico, ? o ∅.

• Target concept c: EnjoySport : X  → {0, 1}, quindi c(x) e il valore deltarget concept.

• Esempi di training D: esempi positivi e negativi appartenenti alla funzionetarget.

Determinare:

• Determinare un’ipotesi h in H tale che h(x) = c(x)∀x ∈ X .

Definizione: Inductive learning Le uniche informazioni che si hanno suil target concept c sono i suoi valori sugli esempi di training. Gli algoritmi diinductive learning possono al piu garantire che l’ipotesi di output fitti il concettotarget sul dato di training.

The inductive learning hypotesis Ogni ipotesi che approssimi bene lafunzione target su un set abbastanza vasto di esempi di training approssimeraanche bene la funzione target su altri esempi non osservati.

Ordine parziale sullo spazio delle ipotesi Date due ipotesi hj e hk, si diceche hj e piu generale o uguale a hk ( ovvero hj ≥ hk ) se e solo se

∀x ∈ X  : [(hk(x) = 1) −→ (hj (x) = 1)]

Ipotesi consistente Un’ipotesi h e consistente con un set di traning examplesD di target concept se e solo se h(x)=c(x) per ogni traning example < x, c(x) >in D.

Version space Il version space, V S H,D, dello spazio delle ipotesi H e deltraining set D e il sottoinsieme di ipotesi di H consistenti con tutti i gli esempidi training:

V S H,D = h ∈ H |Consistent(h, D)

Definizione L’inductive bias e quell’insieme di assunzioni che, insieme ai datidi training, giustifica deduttivamente le classificazioni assegnate dal learner alleistanze future.

2

Page 3: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 3/20

 

Algoritmo find-S

L’algoritmo find-S ritorna l’ipotesi piu specifica che soddisfa gli esempi di trai-ning positivi.

List-Then Eliminate Algorithm

All’inizio il V S  contiene tutte le ipotesi in H. Listando ogni esempio di trainingsi eliminano dal V S  tutte le ipotesi h che sono inconsistenti con quel determinatoesempio.

Definizione Ogni ipotesi del version space e contenuta fra il set di ipotesi piu

generali e il set di ipotesi piu specifiche.

V S H,D = h ∈ H |(∃s ∈ S )(∃g ∈ G)(g ≥ h ≥ s)

3

Page 4: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 4/20

 

Algoritmo candidate elimination

Quindi le ipotesi positive abbassano il limite superiore (quello piu specifico) e leipotesi negative alzano il limite inferiore (quello piu generico). Il version spaceappreso attraverso l’algoritmo candidate elimination convergera verso l’ipotesiche descrive correttamente il target concept ammesso che:

• non ci siano errori negli esempi di training;

• ci sia qualche ipotesi in H che descrive correttamente il target concept.

Il target concept e appreso correttamente quando i limiti S e G coincidono,ovvero convergono alla stessa identica ipotesi.

Inductive bias del candidate elimination Il concetto target c e contenutonello spazio delle ipotesi H.

Alberi di decisione

Definizione L’apprendimento attraverso alberi di decisione e un modo diapprossimare funzioni target a valori discreti, nei quali la funzione appresa erappresentata da un albero di decisione.

Gli alberi di decisione possono rappresentare congiunzioni e disgiunzioni.Gli alberi di decisione possono rappresentare qualsiasi funzione degli attributi

di input. E opportuno usare gli alberi di decisione quando:

• Quando le istanze sono descritte da coppie attributo valore.

• Quando la funzione obiettivo e a valori discreti.

• Quando sono necessarie ipotesi disgiuntive.

4

Page 5: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 5/20

 

• Quando mancano valori di attributi.

• Dati di training rumorosi.

ID3

L’obiettivo e trovare un albero poco profondo che sia consistente con gli esempidi training. Per fare cio si sceglie ricorsivamente l’attributo piu significativocome radice di un sottoalbero. L’attributo ideale divide gli esempi in subsetsdi esempi tutti positivi o negativi. Dato un set S di training example e detti

 p+ la proporzione esempi positivi e p− la proporzione di esempi negativi, la suaentropia e:

Entropy(S ) = − p+log2( p+) − p−log2( p−)

L’entropia misura l’impurita di S.Information gain:

IG(S, A) = Entropy(S ) −

v∈values(A)

(S v/S ) ∗ Entropy(S v)

S v e il numero di esempi che corrispondono al valore v dell’attributo A. S  e ilnumero di esempi totali. Gli alberi si costruiscono mettendo in cima gli attributicon information gain  maggiore.

5

Page 6: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 6/20

 

Overfitting

L’ipotesi h ∈ H  overfitta i dati di training se c’e un’ipotesi alternativa h

∈ H tale per cui

errortrain(h) < errortrain(h

) ∧ errorD(h) > errorD(h

)

Si ha overfitting quando un’ipotesi si rivela la migliore sull’insieme dei dati ditraining, ma non risulta tale generalizzando (ovvero sull’intera distribuzionedelle istanze, capita quando si hanno pochi dati).

Inductive Bias

Dato un insieme di esempi di training, a questo sono associati piu alberi di de-cisione consistenti con gli esempi. L’inductive bias di id3 introduce un criterio

per scegliere una di queste possibili soluzioni. Id3 sceglie alberi poco profondi eposiziona gli attributi piu rilevanti il piu possibile vicino alla radice. Perche pre-ferire alberi poco profondi? Rasoio di Occam: preferire l’ipotesi piu sempliceche e consistente con i dati.

Confronto fra ID3 e Candidate-elimination

• ID3: esegue una ricerca incompleta (ha una condizione di terminazione enon vengono esplorati tutti i rami) in uno spazio delle ipotesi completo.

• CE: esegue una ricerca completa (dal momento che cerca ogni ipotesiconsistente con i dati di training) in uno spazio delle ipotesi incompleto(puo esprimere solo un sottoinsieme dei concetti apprendibili).

PAC learning

Nel PAC (Probably Approximately Correct) learning l’accuratezza dei risultatied il tempo di esecuzione degli algoritmi di learning sono esplicitamente quan-tificati e correlati.Il modello e formato da:

• Un dominio X

• Un concetto, sottoinsieme di X, f  ⊆ X  o f  → {0, 1}

• Una classe di concetti ς  ⊆ 2x

• Una distribuzione di probabilita P su X

6

Page 7: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 7/20

 

Errore vero dell’ipotesi h L’errore vero dell’ipotesi h rispetto al concettotarget c e alla distribuzione D, e la probabilita che H  classifichera in modo

errato un’istanza estratta a sorte secondo D.

errorD(h) ≡ P Rx∈D[c(x) = h(x)]

Le risorse computazionali che sono usate dagli algoritmi sono:

• Sample Size: numero di esempi necessari all’apprendimento

• Computation time: computazione necessaria al processo di ap-prendimento

Polynomially PAC learnability

La PAC learnability si ha quando e verificata la condizione di PAC l statistica(limite al numero di esempi di training) e la condizione di PAC l polinomiale(limite alla complessita dell’algoritmo).

Definizione1: Una classe di concetti ς  e PAC apprendibile in tempo polino-miale se c’e un algoritmo con tempo di esecuzione limitato da una funzionepolinomiale e con sample size t = t(n, 1/ε, 1/δ). t e il numero di esempi suffi-cienti ad imparare con accuratezza ε e con precisione δ. L’errore e cosı definito:P (errorD(h) ≤ ε) = 1 − δ.

Definizione2: Si consideri una classe di concetti C di lunghezza n, e un learnerL che lavora su uno spazio H, definito su un insieme di istanze X con lunghezzan; la classe C e PAC-Learnable (da L usando H) se per tutti i concetti, per tutte

le distribuzioni di P su X, per tutti gli ε tali che 0 < ε < 1/2, e i δ tali che0 < δ < 1/2, il learner L dara in output con probabilita > 1 − δ un ipotesi hche sia ε − buona (tale che errorD(h) <= ε), in un tempo che sia polinomialein 1/ε, 1/δ, n, e con dimensione size(c).

Numero di esempi necessari: m ≥ 1

(ln|H | + ln(1/δ))La disuguaglianza mostrata nella formula fornisce un limite generale al nume-ro di esempi di training sufficienti a qualsiasi learner per apprendere qualsiasiconcetto obiettivo in H per qualsiasi valori desiderati ε e δ. Questo nume-ro m di esempi di training e sufficiente a garantire che qualsiasi ipotesi saraprobabilmente (con probabilita 1 − δ) circa corretta (in un raggio di errore ε).

Algoritmo di learning Un algoritmo A e un algoritmo di learning con samplesize t = t(n, 1/ε, 1/δ) per una classe di concetti F  = U ∞n=1F n che usa la classedi rappresentazioni C  se:

• ∀n ≥ 1

• ∀f  ∈ F n

7

Page 8: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 8/20

 

• ∀ε > 0

• ∀δ < 1

• ∀ distribuzione di probabilita p su {0, 1}nimplica che: Se la procedura

di inferenza An riceve come input un t-sample esso fornisce in output unarappresentazione c ∈ C n di una funzione g che e probabilmente appros-simata bene, con probabilita almeno 1 − δ che un t-sample sia scelto inmodo tale che la funzione g soddisfi:

P {x|f (x) = g(x)} ≤ ε

Quindi g e ε − good se g e una ε − approssimazione di f, e invece ε − badaltrimenti.

Dimensione di Vapnik-Chervonenkis

La dimensione VC misura la complessita dello spazio delle ipotesi H , non peril numero distinto di ipotesi |H |, ma invece per il numero di istanze distinte daX  che possono essere completamente discriminate usando H .

Definizione: La dimensione di Vapnik-Chervonenkis dello spazio delle ipotesiH definita sullo spazio delle istanze X e la dimensione del piu grande sottoinsiemefinito di X frantumato da H. Se grandi insiemi finiti di X possono essere ridottiarbitrariamente in frantumi da H allora V C (H ) = ∞.

Definizione: Un insieme di istanze S e frammentato dallo spazio delle ipotesi

H se e solo se per ogni dicotomia di S esiste qualche ipotesi in H consistente conquesta dicotomia.

Piu e grande l’insieme S che puo essere frantumato piu e espressivo H.Limite inferiore al numero di esempi di training

Bayesian learning

Vantaggi

8

Page 9: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 9/20

 

• Nessuna ipotesi viene eliminata, anche se inconsistente con i dati.

• Ad ogni ipotesi h viene data una probabilita P(h) che sia l’ipotesi corretta.

• P(h) e modificato incrementalmente dopo aver visto un esempio.

Svantaggi:

• Difficile stimare le probabilita a priori.

• Grande costo computazionale nel caso generale.

Teorema di bayes

P (h|D) =P (D|h) ∗ P (h)

P (D)

P(h) = probabilita a priori dell’ipotesi hP(D) = probabilita del training set DP (h | D) = probabilita a posteriori di h dato DP (D | h) = verosimiglianza di D dato h

Predizione bayesiana

Si calcola la probabilita condizionata di ogni ipotesi tenendo conto dei datiosservati. Si predice il prossimo valore di X basandosi su una media pesatafra la vicinanza di tutte le probabilita delle ipotesi. La predizione bayesiana eottima, ma ha un alto costo computazionale.

MAP approximation

Maximum A Posteriori learning: sceglie l’ipotesi piu probabile all’internodel training data. Un metodo di calcolare il MAP e il brute force MAP learner:

• ∀h ∈ H  calcola la probabilita a posteriori P (h|D) = P (D|h)P (h)P (D)

• Restituisci in output l’ipotesi hMAP  con la piu alta probabilita a posteriorihMAP  = arg maxh∈H P (h|D)

ML approximation

Sceglie l’ipotesi h che massimizza la verosimiglianza di D : hML = arg maxh∈H P (D|h).

E da notare che se la distribuzione di probabilita a priori e uniforme allorahMAP  = hML . ML e il metodo di learning statistico (non bayesiano) standard.

9

Page 10: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 10/20

 

Bayes Optimal Classifier

Qual’e la classificazione piu probabile della nuova istanza conoscendo i dati ditraining?

argmaxvj∈V 

hi∈H 

P (vj |hi)P (hi|D)

Questo metodo massimizza la probabilita che la nuova istanza sia classifica-ta correttamente, basandosi sui dati disponibili, lo spazio delle ipotesi e leprobabilita a priori sulle ipotesi.

Naive Bayes Classifier

E uno dei metodi di learning piu usato in assoluto insieme agli alberi di decisionee alle reti neurali. Gli ambiti in cui si usa sono le diagnosi e la classificazione ditesti.E da usare quando:

• Set di training di medie e grandi dimensioni.

• Gli attributi che descrivono le istanze sono condizionalmente indipendentidata la classificazione.

Vediamo come funziona:

• Naive Bayes assumption: P (a1, a2,...,an|vj ) =

i P (ai|vj )

• Naive Bayes classifier: vNB = arg maxP (vj )

i P (ai|vj )

Considerazioni

• Il classificatore ottimale di Bayes non fa assunzioni di indipendenza travariabili ed e computazionalmente pesante.

• Il classificatore ingenuo di Bayes e efficiente grazie all’ipotesi molto re-strittiva di indipendenza condizionale di tutti gli attributi dato il valoreobiettivo v.

Algoritmo:

N a i v e B ay e s L e a rn ( e x a mp l es )For e ac h t a r g e t v al u e v j

P ( v j ) = e s t i m a t e P ( v j )For eac h a t t r i bu t e v al ue a i o f ea ch a t t ri b u t e a

P( ai | v j ) = e s t i m a t e P ( a i | v j )C l a s s i f y N e w I n s t a n c e ( x )

vNB = arg max P( vj ) \ prod P( ai | v j )

10

Page 11: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 11/20

 

Reti neurali

Considerazioni sulle reti neurali

• Da usare quando ci sono input multidimensionale a valori reali o discreti(es. dati grezzi da sensori).

• Da usare quando in Output c’e vettore di valori.

• Da usare quando ci sono Dati rumorosi nei dati di training.

• Da usare quando la forma della funzione obiettivo sconosciuta.

• Da usare quando Non e importante la leggibilita da parte dell’uomo.

• Tempi di training elevati, ma valutazione della rete molto veloce.

Si usano per predizioni finanziarie, medicina, riconoscimento e produzione par-lato, elaborazione di segnali... Le reti neurali sono caratterizzate da un grandenumero di unita, ognuna delle quali svolge operazioni elementari e ha molte con-nessioni con le altre unita. Il neurone cambia stato in funzione dello stato deineuroni vicini. Lo schema di connessione viene modificato con l’apprendimento.

Neurone formale E caratterizzato da uno stato, una funzione di transizione,una funzione di uscita e una modalita di transizione.

Percettrone

Esso e collegato ad un insieme di nodi di input attraverso degli archi pesati.I pesi vengono fissati a caso e poi modificati. Attraverso una procedura diapprendimento si forniscono alla rete degli esempi da classificare. Se la rispostae errata, si modificano i pesi, incrementando i pesi delle unita di input attivese si e risposto 0 invece di 1, decrementandole nel caso duale: w

= w ± x. Unsingolo percettrone puo essere usato per rappresentare diverse formule booleane(∧, ∨, !...). Addestrare una rete di percettroni significa attribuire tutti i pesiw0,...,W n della rete neurale. Lo spazio delle ipotesi H  e l’insieme di tutti ipossibili vettori di pesi a valori reali.

11

Page 12: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 12/20

 

Un singolo percettrone e in grado di rappresentare correttamente le funzio-ni booleane AND,OR,NAND (¬AND),NOR(¬OR). Tuttavia alcune funzio-

ni booleane, come lo XOR (non linearmente separabile!) non possono essererappresentate con un singolo percettrone. La capacita dei percettroni di rap-presentare queste funzioni booleane e fondamentale poiche qualunque funzionebooleana puo essere rappresentata da una rete di unita interconnesse che si basisu queste funzioni booleane primitive.

Perceptron training rule

Un modo per apprendere un vettore di pesi accettabile e iniziare con pesi ca-suali, quindi applicare iterativamente il percettrone ad ogni esempio di training,modificando i pesi del percettrone ogni volta che non classifica un esempio.Regola:

wi ← wi + ∆wi

dove∆wi = η(t − o)xi

t e l’output target, o e l’output che si e effettivamente ottenuto e η e una costantepositiva chiamata learning rate. Il ruolo di questa costante e di moderare quantovengono cambiati i pesi ad ogni step. Esso e generalmente impostato a valoribassi (0,1 per esempio) e spesso e fatto decadere con il crescere delle iterazioni.Facciamo un esempio:

• Il percettrone ha classificato male, il risultato corretto sarebbe stato 1(variabile t) e ha ritornato -1 (variabile o).

• Assumiamo come learning rate η = 0.1 e xi = 0.8.

• La variazione sara: ∆wi = 0.1(1 − (−1))0.8 = 0.16

La regola descritta sopra converge entro un numero finito di passi ad una soluzio-ne solo se gli esempi sono linearmente separabili. Se i dati non sono linearmenteseparabili la convergenza non e garantita e si deve usare la regola delta.

Regola delta e discesa del gradiente

La perceptron training rule benche trovi con successo un vettore di pesi quandogli esempi sono linearmente separabili potrebbe fallire nel caso non lo fossero.La delta rule supera questo limite; se gli esempi non sono linearmente separabiliessa converge verso l’approssimazione piu simile al target concept. L’idea basee quella di usare la discesa del gradiente per trovare nello spazio delle ipotesi ilvettore di pesi piu consistente con gli esempi di training. Specifichiamo cos’e iltraining error di una ipotesi( o vettore dei pesi):

E (−→w ) =1

2

d∈D

(td − od)2

12

Page 13: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 13/20

 

Dove D e il set di esempi di training, td e l’output target dell’esempio di trainingd e od e l’output dell’unita lineare per l’esempio di training d. Sotto certe condi-

zioni l’ipotesi che minimizza E  e anche l’ipotesi piu probabile in H  dati gli esem-pi di training. Visualizziamo graficamente lo spazio delle ipotesi per una rete con

due archi:Il minimo globale rappresenta l’ipotesi piu corretta, quella con errore minorepossibile. Ma come si calcola la direzione presso la quale scendere? E neces-sario calcolare le derivate parziali per ogni componente del vettore −→w . Questo

vettore delle derivate parziali e detto gradiente di E  rispetto a −→w e si indicacon E (−→w ). Questo vettore contiene le direzioni presso le quali scendere pertrovare il minimo globale. Quindi la training rule e:

−→w ← −→w + ∆−→w

dove∆−→w = −η E (−→w )

La costante η ha segno negativo perche vogliamo andare nella direzione in cuidecresce.

Teorema di Minsky e Papert La classe delle forme discriminabili da unpercettrone semplice e limitata alle forme linearmente separabili.

Multi-layer networks

I nodi sono disposti a strati; all’interno di uno strato non ci sono connessioni, inodi comunicano solo con i nodi appartenenti a strati superiori. Esiste quindi

13

Page 14: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 14/20

 

un input layer, degli hidden layers e un output layer. Obiettivo e che, fissata unamappa f tra configurazioni di ingresso e di uscita, sulla base di una sequenza di

stimoli xk, la rete cambi i pesi delle connessioni in modo che, dopo un numerofinito s di passi di apprendimento, l’uscita yk coincida con f (xk) per ogni k > s,almeno approssimativamente.

Sigmoide

Il tipo di unita che si utilizza in questo tipo di reti e il sigmoide, poiche e simileal percettrone ma basato su una funzione continua (smoothed) e differenziabile.

L’output o del sigmoide e:o = σ(−→w ∗ −→x )

dove

σ(y) =1

1 + e−y

La particolarita di questa funzinoe e che generano un output monotono crescente

e che le derivate sono facilmente esprimibili in funzione dell’output ( dσ(y)dy

σ(y) ∗

(1 − σ(y))

L’algoritmo di backpropagation

L’algoritmo d backpropagation impara i pesi per una rete multi strato, data unarete con un insieme fissato di unita e connessioni. Esso utilizza la discesa delgradiente per cercare di minimizzare l’errore quadratico fra i valori di outputdella rete e i valori obiettivo. L’errore e:

E (−→w ) =1

2

d∈D

k∈outputs

(tkd − okd)2

dove tdk e odk sono i valori obiettivo ed effettivi del k − esimo output unit e deltraining example d.

Support vector machines

• Algoritmo di apprendimento efficiente

• Imparano funzioni di separazione non lineari complesse

14

Page 15: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 15/20

 

• Classe di metodi che trovano l’iperpiano separatore (il migliore) per clas-sificare un insieme di punti (linearmente separabili)

Bisogna trovare quindi l’iperpiano separatore di massimo margine (lo si fa attra-verso un problema di programmazione matematica). Esiste un unico iperpianodi massimo margine. A differenza del percettrone semplice che ha un algoritmodi apprendimento efficiente ma un potere espressivo limitato, e dei percettronimultistrato che sono in grado di apprendere funzioni di separazione non linearicomplesse, ma sono difficili da addestrare a causa di un elevato numero di mini-mi locali, le SVM sono in grado di apprendere funzioni di separazione non linearicomplesse ed hanno un algoritmo di apprendimento efficiente. Il classificatore(il nostro iperpiano) divide gli esempi di training in due semispazi, identificandodue classi di esempi. Definizione di iperpiano:

• Se l’iperpiano passa per l’origine < w,x >= 0

• Se l’iperpiano non passa per l’origine < w,x > +b = 0

• Un iperpiano quindi e un insieme di punti espresso in questo modo: {x| <w,x > +b = 0}

• I punti da un lato dell’iperpiano sono tali che < w,x > +b > 0

• I punti dall’altro lato sono tali che < w,x > +b < 0

I vettori di supporto sono gli esempi del training set che giacciono sul marginedell’iperpiano. Esistono due tipi di margini:

• Funzionale: Un ampio margine funzionale ci da una certa speranza sul-

la nostra previsione, ma basarsi solo sul margine funzionale causa deiproblemi.

• Geometrico: rappresenta la distanza da un punto dall’iperpiano.

Bisogna quindi estendere il piu possibile il margine geometrico. Se i punti non so-no linearmente separabili → Classificatore NON LINEARE e quindi Classificaremediante superfici non lineari.

Metodi Kernel

Si usano per classificazioni non lineari e per applicare efficientemente le SVM inspazi ad un numero molto alto o infinito di dimensioni. Per risolvere il problemadei punti non linearmente separabili si mappa lo spazio di input in un nuovo

spazio a dimensione maggiore in cui i punti sono linearmente separabili.

15

Page 16: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 16/20

 

Reinforcement learning

L’obiettivo e scegliere un’azione ai che massimizzi le future ricompense: r0 +γr1 + γ 2r2 + ... dove 0 < γ < 1 e un fattore di sconto. Quindi si da piu im-portanza alle ricompense immediate e meno importanza a quelle piu distantinel tempo. La funzione obiettivo da imparare in questo caso e una politica dicontrollo,n : S  → A, che da in uscita una azione appropriata dall’insieme di A,dato lo stato attuale s dal insieme S. Il compito dell’agente e quello di impara-re una funzione obiettivo π che mappi dallo stato attuale s all’azione ottimalea = π(s). Il learner dovra utilizzare un compromesso nello scegliere se favorirel’esplorazione di stati sconosciuti e azioni (per raccogliere nuove informazioni), olo sfruttamento di stati e azioni che ha gia imparato, per avere una ricompensaelevata (massimizzare il suo cumulo dei premi). Stati parzialmente osservabili:puo essere necessario per l’agente di considerare le sue osservazioni precedentiinsieme con i dati dei suoi sensori al momento di scegliere le azioni.

Formazione permanente: Questa impostazione aumenta la possibilita di uti-lizzare l’esperienza precedentemente ottenuta o la conoscenza per ridurre lacomplessita del campione, per l’apprendimento di nuovi compiti. Learning task:

• Eseguire azioni nell’ambiente, osservare i risultati e

• imparare una policy π : S  → A che associ ad ogni stato s ∈ S  un’azionea ∈ A cosı da massimizzare la ricompensa attesa E [r0 + γr1 + γ 2r2 + ...]da ogni stato di partenza s.

Due tipi di funzioni:

• State value function: denota la ricompensa che si ottiene partendo dallostato s e seguendo la policy π

• Action value function: denota la ricompensa che si ottiene partendo dallostato s, eseguendo l’azione a e seguendo la policy π.

Q Learning

Che funzione di valutazione deve apprendere l’agente? L’agente dovrebbe pre-ferire uno stato s1 allo stato s2 se il cumulo dei premi a partire da s1 e seguendouna policy ottimale e superiore a quanto si otterrebbe con s2. Quindi l’azioneottimale nello stato s e l’azione a che massimizza la somma della ricompensaimmediata r(s, a) e il valore V ∗ dello stato successore, scontato da γ .

π∗(s) = argmax[r(s, a) + γV ∗(δ(s, a))]

Esercizi

Find-s

L’algoritmo di risoluzione e il seguente:

16

Page 17: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 17/20

 

• Si parte dall’ipotesi piu specifica

• Se l’esempio e positivo si aggiungono tutti i parametri dell’esempio

• Se l’esempio successivo e positivo e presenta parametri che non concordanoallora si cancellano dal concetto finale quei parametri impostando <? >.

• I concetti negativi li ignoro.

Esempio: S  = (∅,∅,∅)

• x1 =< debole, mite, beltempo > positivo −→ S  = (debole, mite, beltempo)

• x2 =< media, f redda, stabile > positivo −→ S  = (?, ?, ?)

• x3 negativo lo ignoro.

• x4 negativo lo ignoro.

• x5 =< debole, mite, stabile > positivo −→ S  = (?, ?, ?)

Concetto finale: S  = (?, ?, ?)

Candidate elimination

Si fissano estremi superiori(piu specifici) e inferiori (meno specifici). Consideraanche le ipotesi negative. Consideriamo S l’ipotesi (o insieme di ipotesi) piuspecifica consistente con le osservazioni e G l’ipotesi (o insieme di ipotesi) piugenerale consistente con le osservazioni.

Svolgimento

Elenco di ipotesi:

• x1 =< s,w,n,s,w,s > positivo

• x2 =< s, w,h,s,w, s > positivo

• x3 =< r, c,h,s,w, c > negativo

• x4 =< s, w,h,s,c, c > positivo

Svolgimento:

• G0 =<?, ?, ?, ?, ?, ? >

• S 0 =< ∅,∅,∅,∅,∅,∅ >

Considero x1, G rimane invariato e modifico S:

• G1 = G0

17

Page 18: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 18/20

 

• S 1 =< s,w,n,s,w,s >

Considero x2 che e positivo, G rimane ancora invariato ed elimino da S le ipotesiinconsistenti:

• G2 = G1

• S 2 =< s,w, ?,s,w,s >

Considero x3 che e negativo, aggiungo a G tutte le specializzazioni minimeconsistenti:

• G3 =< s, ?, ?, ?, ?, ? >, <?, w, ?, ?, ?, ? >, <?, ?, ?, ?, ?, s >

• S 3 = S 2

Considero x4 che e positivo, devo rimuovere da G la terza ipotesi, dal momento

che non e consistente ed aggiornare S:

• G4 =< s, ?, ?, ?, ?, ? >, <?, w, ?, ?, ?, ? >

• S 4 =< s,w, ?, s, ?, ? >

Quindi i limiti finali sono S 4 e G4 e fra loro ci sono le ipotesi intermedie.

Esercizio ID3

Idea di base: scegliere ad ogni iterazione l’attributo piu significativo come radicedel nuovo sotto-albero. L’attributo e tanto piu significativo quanto divide insubset tutti positivi o negativi.

Entropy(s) = − p+log2( p+) − p−log2( p−)

IG(S, A) = Entropy(S ) −

v∈values(A)

| S v |

S Entropy(S v)

Esempio di selezione dell’attributo piu rilevante: I valori degli attributi sono iseguenti:Humidity [9+,5-], E=0.940

• High[3+,4-], E=0.985

• Normal[6+,1-], E=0.592

Wind[9+,5-] , E=0.940

• Weak[6+,2-], E=0.811

• Strong[3+,3-], E=1.0

Outlook[9+,5-], E=0.940

• Sunny[2+,3-],E=0.971

18

Page 19: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 19/20

 

• Overcast[4+,0-],E=0.0

• Rain[3+,2-],E=0.971

Per ognuno degli attributi e necessario calcolare L’Information Gain e selezio-nare come nuovo attributo da aggiungere all’albero quello con IG maggiore.Gain(S, Humidity) = 0.940 − ( 7

14) ∗ 0.985 − ( 714 ) ∗ 0.592 = 0.151

Gain(S,Wind) = 0.940 − ( 814 ) ∗ 0.811 − ( 6

14) ∗ 1.0 = 0.048Gain(S, Outlook) = 0.940 − ( 5

14) ∗ 0.971 − ( 414 ) ∗ 0.0 − ( 5

14) ∗ 0.971 = 0.247

Viene scelto l’attributo con IG maggiore, in questo caso Outlook. Dei 3attributi di Outlook Overcast ha solo esempi positivi e dunque e una fogliadell’albero. Restano Sunny e Rainy. Ora dobbiamo decidere quale attributoselezionare come radice del nuovo sottoalbero caratterizzato dal valore Outca-st=Sunny.

Gain(S sunny, Humidity) = 0.970 − (35)0.0 −

25(0.0) = 0.970

Gain(S sunny,Temp) = 0.970 − (25)0.0 − 25(1.0) − (15)0.0 = 0.570

Gain(S sunny,Wind) = 0.970 − ( 25)1.0 − 35(0.918) = 0.019

Humidity ha l’information gain maggiore. Allora Humidity sara la nuovaradice del sottoalbero.

Esercizio Naive Bayes Classifier

Si parte contando tra i dati di training quali sono gli esempi negativi e positivi eper ogni attributo il numero di volte che compare in esempi positivi e negativi.Dopo di che si computa il vN B nel seguente modo:

vBN  = argmaxvj∈V  P (vj )

iP (ai|vj )

Esempio:Il nostro obiettivo e prevedere il valore target (si/no) del concetto playTennisper questa nuova istanza: ¡Outlook=sunny, Temperature=cool, Humidi-ty=high, Wind=strong¿. Abbiamo i seguenti dati:

• 9/14 playTennis=yes

• 5/14 playTennis=no

• P (wind = strong| play = yes) = 3/9

• P (wind = strong| play = no) = 3/5

Ora possiamo calcolare la probabilita per i due casi(giocare e non giocare):

P ( play = yes)P (outlook = sunny| play = yes)P (temperature = cool| play = yes)P (humidity = hi

19

Page 20: Machine Learning

5/12/2018 Machine Learning - slidepdf.com

http://slidepdf.com/reader/full/machine-learning-55a4d36e6f662 20/20

 

Esercizio Vapnik-Chervonenkis

Siano dati:

• X  = {1, 2, 3, 4};

• C  = {{1}, {2}, {3}, {4}, {1, 2}, {2, 3}, {1, 3, 4}, {1, 2, 3, 4}} classe delle ipo-tesi;

• S  = {{1, 2}} insieme degli esempi.

S  frammenta C ? Si se l’insieme delle parti di S  deve essere contenuto in C ,compreso l’insieme vuoto.

C ∩ S  = {{1}, {2}, {1, 2},∅}

Per ottenere l’insieme vuoto e sufficiente intersecare un qualunque insieme di Scon 4. In questo caso vediamo che esso e contenuto, quindi possiamo dire chedV P  e almeno |S | = 2. Verifichiamo con S  = 1, 2, 3.

C ∩ S  = {{1}, {2}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3},∅}

Anche in questo caso S  e frantumato da C . Provando con S  = {{1, 2, 3, 4}}invece non si riesce a frammentare perche per esempio non c’e {2, 4}. QuindidV P  = 3.

Esercizio MAP

Un test per verificare se una persona ha il cancro ha due possibili esiti: po-sitivo ⊕ o negativo . Il test pero e impreciso, il test ritorna positivo solo

nel 98% dei casi in cui la malattia e effettivamente presente, mentre ritor-na un risultato negativo nel 97% dei casi in cui la malattia non e presente.

Viste le probabilita a priori computiamo per i due casi:

Quindi il risultato e: hMAP  = ¬cancer.

20