Computational Learning Theory
and PAC learning
Obiettivo
• Questa teoria cerca di dare risposte al seguente problema: data una ipotesi h,
come posso predire quanto questa ipotesi sia promettente, ovvero quanto
approssimi la funzione obiettivo c, se non conosco c?
• Implicazione: “quanto” devo addestrare l’apprendista perché apprenda
un’ipotesi promettente?
• Apprendimento PAC: una ipotesi consistente con un numero elevato di
esempi è probabilmente approssimativamente corretta (PAC)
Definizioni
• Ipotesi di stazionarietà: l'insieme di addestramento e l'insieme di
test devono essere estratti dalla medesima popolazione di esempi
usando la medesima distribuzione di probabilità.










Sia X lo spazio delle istanze
Sia C una classe di concetti definiti su X
Sia c un concetto di C
Sia D la distribuzione di probabilità dei fenomeni nello spazio delle
istanze X
Sia E(c, D ) una procedura che estrae istanze da X secondo D e le
classifica <x,c(x)>
Sia D l'insieme di apprendimento estratto da E(c, D )
Sia H l'insieme delle ipotesi possibili
Sia m il numero di esempi in D
Sia di un esempio di D di <xi,c(xi)>
NOTA: D
Sia h un'ipotesi di H
Distribuzione
D esempi
PAC learning
• Def(modello PAC learning): Sia C una classe di concetti definita
su X. C si dice PAC learnable se esiste un algoritmo di
apprendimento L con le seguenti proprietà:
– per ogni cC, per ogni D su X, e per ogni 0 e , se L ha
accesso ad una procedura E(c, D ) e ai valori  e , allora con probabilità
almeno (1-) L produrrà una ipotesi hC che soddisfa errore(h).
– Se L gira in un tempo polinomiale in 1/ e 1/, allora si dice efficiently
PAC learnable.
•  prende il nome di parametro di errore,  prende il nome di parametro di
confidenza, m è detto complessità del campionamento
• Il parametro di confidenza  tiene conto della probabilità che, in un
particolare insieme di apprendimento D compaiano esempi poco
rappresentativi (o rumorosi). In questo caso, la cui probabilità si assume <,
l'errore di h potrebbe essere maggiore del parametro .
Occam Learning
• Indichiamo con C la classe di concetti sui quali viene effettuato
l'apprendimento. Sia C =Cn con n finito
(es: se Cn è l'insieme degli n-monomials ,  Cn =2n , mentre
l'insieme Cn delle rete neurali di architettura G è infinito)
• In questo caso, è possibile dare una definizione specifica delle
condizioni di apprendibilità.
• Il principio del rasoio di Occam dice che le teorie scientifiche
dovrebbero essere il più semplici possible. (Entia non est
multiplicanda praeter necessitatem)
• Apprendere è l'atto di trovare una regolarità nei dati che faciliti
una rappresentazione compatta dei medesimi.
Occam learning (2)
• Def(Occam learning): Siano  <1 due costanti, D un
insieme di apprendimento di dimensione m, L un algoritmo di
apprendimento, C una classe di concetti, H un insieme di ipotesi
in un certo spazio di rappresentazione. L si dice un (,)-Occam
algorithm per C usando H se, sottoponendo un campione D di m
esempi di un concetto cCn, L emette un'ipotesi h(c) H tale
che:
 h è consistente con D
 size(h)(n·size(c)) m
dove size(h) e size(c) indicano rispettivamente, la dimensione in
bit di h e la più piccola dimensione di c in H.
• Notate che n è la dimensionalità di un singolo esempio xX
Commento
size(h)(n·size(c)) m
• La dimensione dell’ipotesi dipende da n (il numero di attributi
che descrivono un esempio) e dal numero m degli esempi
sottoposti.
• Un “buon” algoritmo dovrebbe emettere una ipotesi che sia più
compatta di mn (come, ad esempio, un’ipotsi che sia
banalmente la disgiunzione di tutti gli m esempi visti). I
parametri  e  suggeriscono appunto questo.
Teorema 1
Teorema 1 (PAC learnability of Occam algorithms): Sia L un
(,)-Occam algorithm per C usando H, sia cCn, sia D la
distribuzione di probabilità su X, e siano 0 e .
Allora, esiste una costante a>0 tale che se ad L viene sottoposto un
campione D di m esempi scelti su X in accordo a E (c, D ), allora
se:

1 

(n(size(c)) 1  
1
1


m  a log  



 







con probabilità almeno (1-) L produrrà un'ipotesi h che soddisfa
error(h).
Inoltre, L gira in tempo polinomiale in n, size(c), 1/ e 1/
Teorema 1 (versione 2)
Sia L… Allora, esiste una costante b>0 tale che se ad L viene
sottoposto un campione D di m esempi scelti su X in accordo a
EX(c, D ), allora se:
logbm - log(1/)
con probabilità almeno (1-) L produrrà un'ipotesi h che soddisfa
error(h).
Inoltre, L gira in tempo polinomiale in n, size(c), 1/ e 1/
Dimostrazione
error(h) h Hbuone
error(h)> h Hcattive
H
Hcattive
hbad

c
Hbuone

•Per un'ipotesi hbadHcattive la
probabilità che l'ipotesi concordi con
m esempi (risulti consistente) è
stimata dalla:
P(hbadconcordi con m esempi)=(1)m(1-)m
•P(Hcattive contenga ipotesi consistenti)
Hcattive (1-)m
H (1-)m ma poiché 1-e-
otteniamo: He -m
Se desideriamo un PAC learning,
dobbiamo imporre che He -m <, da
cui, estraendo i logaritmi:

1  1
m  ln  ln H 

b  
m dipende dalla dimensione
dello spazio delle ipotesi.
Esempio 1: congiunzione di letterali booleani
•H è lo spazio di formule congiuntive di n attributi booleani
•Consideriamo l’algoritmo Find_S:
inizializza h con l’ipotesi più specifica in h
x tale che c(x)=1,  ai in h
Se x soddisfa ai  do nothing
Altrimenti, rimpiazza ai con la condizione più generale che sia
soddisfatta da x
Produci l’ipotesi h
•L'ipotesi più specifica per una congiunzione di n booleani è:
h  x1  x1  x2  x2 ......xn  x n
sia d: <x,c(x)> un esempio positivo (i negativi vengono ignorati) x è una stringa
di bit a1…an
per ogni ai in x, se ai =1  cancella xi in h, se ai =0  cancella xi in h
in ogni passo, h è più specifica di c (non esistono letterali che compaiono in c ma
non in h, o falsi negativi)
PAC learnability di Find_S
Consideriamo dunque la probabilità di falsi positivi.
•Sia z un letterale che compare in h ma non in c (una causa di errore per h).
•Dunque, h commetterà un errore ogni volta che verrà sottoposto un elemento da
classificare x che sia positivo per c ma che non contenga z.
z
Sia: p(z)=Pr(c(a)=1, z è contraddetto in a)
Es:
h  x1  x2  x3  x4 ipotesi corrente
concetto corretto
c  x1  x3  x 4
x=(1111) c(x)=1
esempio corrente
la possibilità di errore, data una ipotesi h, è limitata dalla:
errore(h)zhp(z)
definiamo z un letterale pericoloso (bad literal ) se:
p(z)n
Se h non contiene letterali pericolosi, allora possiamo ricavare un limite
inferiore per l' errore:
errore(h) zhp(z) zh(n)  2n(n)= 
PAC learnability di Find_S (2)
Supponiamo viceversa che esistano alcuni letterali pericolosi.
Per ogni z pericoloso, la probabilità che nessuno, fra m esempi di addestramento,
contenesse questo letterale è al più:
p(z non eliminato dopo m esempi)=(1-p(z))m(1-n)m
Poiché la probabilità che z non venga eliminato sulla base di un singolo esempio
è (1-p(z)).
Siccome il massimo numero di letterali è 2n, la probabilità che ci sia qualche
letterale pericoloso dopo m esempi è al più 2n(1-n)m
Ma per garantire la PAC learnability deve essere verificata la:
2n(1-n)m
dove  rappresenta la confidenza
poiché (1-x) e-x  2ne(-mn) 
che porta alla: mnln(2n)+ln(1/
Esempio 2: apprendibilità di Liste di
decisione
• Una lista di decisione consiste in una sequenza ordinata di test,
ciascuno dei quali è una congiunzione di letterali.
• Se un test ha successo, viene restituita una decisione, se fallisce,
si passa al test successivo.
v1=val(11)
S
Si
N
N
v1=val(1,2)
&v2=val(2,3)
S
Si
v1=val(1,3)&
v3=val(3,1)&..
S
Si
N
Apprendibilità di Liste di decisione (2)
Se si limita la dimensione di ciascun test ad al più k letterali, è
possibile per l'algoritmo di apprendimento trovare buone ipotesi
con un piccolo numero di esempi.
Un test è una congiunzione di k letterali su n attributi.
Chiamiamo k-DL(n) un linguaggio costituito da tutte le liste di
decisione DL con al più k attributi. Che dimensione ha questo
linguaggio?
Ogni possibile test può fornire risposta Si, No, o può non comparire
nella lista , dunque possono esserci al più 3conj(n,k)insiemi di test
componenti, dove conj(n,k)rappresenta il numero di
congiunzioni di k letterali su n attributi:
k
k)
conj(n,k)   2n

O(n
(in quanti modi posso
k
i0
costruire un test)
 
Apprendibilità di Liste di decisione (3)
Poiché i vari test possono essere ordinati in modo qualsiasi, avrò:
k  DL(n)  3 conj(n,k) conj(n,k)!
da cui ricavo
2
O(n k log2 (n k ))
1 1
m  (ln  O(n k log2 (n k )))


Una lista di decisione dunque consente di apprendere in modo PAC
in un numero ragionevole di esempi, con k abbastanza piccolo.
La dimensione di Vapnik-Chernovenkis
• Dobbiamo trattare il problema dell'apprendibilità nel
caso in cui C ed X siano infiniti.
• Esempi:
L'insieme delle reti neurali di architettura G
L'insieme degli iperpiani di separazione in uno spazio
F
L'insieme dei rettangoli allineati con gli assi x,y
La dimensione di Vapnik-Chernovenkis
(2)
• Data una classe di concetti binari C definita su uno spazio di rappresentazione
H, il massimo numero di possibili classificazioni di un campione D di
dimensione m è 2m.
• Indichiamo con:
 C (D)  (c(x 1),c(x 2 ),...c(xm )) : c  C  c D : c  C 
l'insieme delle possibili dicotomie che D induce su C.
Es: C classe degli iperpiani di separazione su 2 . Ogni cC induce una
suddivisione del piano in un semipiano “positivo” ed un semipiano
“negativo”. Dato un insieme D di 3 esempi, x1 x2 e x3, ogni cC induce su
questi esempi una classificazione. Ad esempio:
c(1,0,0)
x1
c
x3
x2
x2
c’
c’(1,0,1)
La dimensione di Vapnik-Chernovenkis
(3)
• Se C(D)=0,1m (cioè il massimo numero di dicotomie) diciamo che D è
tracciato (shattered ) da C (Ovvero: per ogni m-upla binaria (a1..am) in
• 0,1}m esiste un cC tale che: (c(x1),c(x2)..c(xm)) = (a1..am) )
• Nell’esempio precedente, D3 risultava tracciato dalla classe C dei semipiani di
separazione.
• La dimensione VC di C , VCD(C), è la cardinalità d del massimo insieme D
tracciato da C. Diciamo anche che d è la capacità di C.
• Nota: per dimostrare che la dimensione massima VCD(C)=d basta trovare
qualche insieme D di dimensione d tracciato da C, ma dobbiamo anche
dimostrare che non esiste alcun insieme di dimensione d+1 tracciato da C.
• Nell’esempio precedente, per provare che d=3, dobbiamo anche provare che
non è possibile tracciare D4 con C
Esempi
x4
x1
x2
r3 x2
x3 Nessun semipiano traccia (x4x3x2x1)=(0,0,1,1)
o (1,1,0,0)!!  d=3
In generale se Cn, d=n+1
r1
x1
r2
x5r4 x3
x4
Se C è la classe dei rettangoli paralleli
agli assi, è facile vedere che d è almeno 4
r1 induce (0,0,0,0), r2 (0,0,0,1) r3 (0,0,1,0)
ecc.
Ma se aggiuno un punto x5,
nessun rettangolo induce, ad
es., (0,1,1,1,1) !!!
PAC learnability per classi di dimensione
infinita
Teorema: sia C una classe di concetti di dimensione VC pari a d.
Sia L un algoritmo che accetta in ingresso un insieme D di m
esempi classificati di un concetto c di C, e produce in uscita una
ipotesi h C consistente con D.
Allora, L è un algoritmo PAC per C, purché venga addestrato con
un insieme di m esempi estratti in accordo con EX(c,D ), tale che:
1
1 d
1 
m  c0  log  log 

 
 
dove c0 è una costante >0.
PAC learnability di reti neurali
Sia G un grafo diretto aciclico con n nodi di ingresso ed un numero
di stati interni s, ognuno avente r uscite.
Sia CG la classe di reti neurali con architettura G.
Il numero di esempi richiesti per apprendere CG è inf. limitato
dalla:
1
1 (rs  s)logs 1 
m  c0  log 
log 



 
Nota: la dimensione VC della classe delle funzioni soglia
(semipiani r-dimensionali) è r+1.
Ricordate:



oi  g(ini )  g 
w
x

ij
j


 j



g (ini )  1
ini  
soglia