PATTERN RECOGNITION
(I PARTE)
Intelligenza Artificiale - Pattern
Recognition 1
1
Riconoscimento di Forme
Intelligenza Artificiale - Pattern
Recognition 1
2
CONCETTI DI BASE
Col termine di pattern si intende
genericamente una descrizione di un oggetto.
Le descrizioni possono provenire da
fenomeni fisici catturati mediante sensori,
oppure essere frutto di processi di astrazione.
Qui interessano quelli del primo tipo (figure,
suoni, ecc.).
Intelligenza Artificiale - Pattern
Recognition 1
3
Applicazioni tipiche:
Task of Classification
Input Data
Output Response
Character recognition
Optical signals or strokes
Name of character
Speech recognition
Acoustic waveforms
Name of word
Speaker recognition
Voice
Name of speaker
Water prediction
Water maps
Water forecast
Medical diagnosis
Symptoms
Disease
Stock market prediction
Financial news and charts
Predicted market ups and downs
Intelligenza Artificiale - Pattern
Recognition 1
4
Una classe di pattern è una categoria determinata da
alcuni attributi comuni.
Riconoscere è pertanto ricondotto all'attribuzione di
un pattern d'ingresso ad una data classe.
Intelligenza Artificiale - Pattern
Recognition 1
5
Un pattern è dato mediante la misura degli attributi che
lo costituiscono, solitamente in forma vettoriale:
X=
X1
X2
.
.
.
Xn
Intelligenza Artificiale - Pattern
Recognition 1
6
Ecco alcuni esempi di pattern:
Intelligenza Artificiale - Pattern
Recognition 1
7
PROBLEMI IMPLICATI
Se le misure degli attributi sono forniti mediante numeri
reali, è usuale pensare i vettori-pattern come punti in uno
spazio Euclideo n-dimensionale.
Esempio: i calciatori e i fantini sono caratterizzati da
altezza e peso secondo le seguenti distribuzioni
caratteristiche.
Intelligenza Artificiale - Pattern
Recognition 1
8
Altro oggetto di studio è l'estrazione di caratteristiche
distintive (features) o attributi dai dati in input.
Quest'attività è solitamente accompagnata da una
riduzione di dimensionalità del vettore del pattern.
Si parla di preelaborazione ed estrazione delle
caratteristiche (prepocessing and features extraction
problem).
Intelligenza Artificiale - Pattern
Recognition 1
9
Per il riconoscimento e la classificazione è
necessario ancora disporre di una procedura
per determinare la decisione ottima (criteri e
algoritmi).
Il problema è ricondotto alla determinazione
di superfici di separazione (boundaries) tra
le classi a partire dall'osservazione di un
certo numero di vettori.
Intelligenza Artificiale - Pattern
Recognition 1
10
Se, ad esempio, si usa un criterio di decisione che fornisce
un indice di somiglianza o vicinanza del pattern d'ingresso
rispetto a ciascuna classe, lo schema di un classificatore
di pattern è il seguente:
DFG → decision function generator
Intelligenza Artificiale - Pattern
Recognition 1
11
Associato al problema di preelaborazione ed
estrazione delle caratteristiche è la stima e
l'ottimizzazione dei parametri del riconoscitore
(addestramento dei modelli).
Quando il sistema di riconoscimento deve essere
resistente alle distorsioni, flessibile rispetto ad una
grande deviazione dei pattern e capace di aggiustare
da sè i parametri occorre affrontare il problema
dell'adattamento.
Intelligenza Artificiale - Pattern
Recognition 1
12
Intelligenza Artificiale - Pattern
Recognition 1
13
FUNZIONI DI DECISIONE
Il compito principale di un sistema di
riconoscimento è determinare la classe di
appartenenza dei pattern in analisi.
Occorre stabilire le regole su cui basare queste
decisioni.
Un possibile approccio è l'uso di funzioni di
decisione.
Intelligenza Artificiale - Pattern
Recognition 1
14
Si considerino ad esempio il caso in cui vi sono due
classi ω1 e ω2, separabili mediante una retta:
Intelligenza Artificiale - Pattern
Recognition 1
15
L'equazione della retta sia
d(x)= w1x1 + w2x2 + w3 = 0
dove w1 e w2 sono i parametri.
Sostituendo in d(x) le coordinate di un punto che
appartiene alla classe ω1, si ottiene un valore positivo.
Intelligenza Artificiale - Pattern
Recognition 1
16
Sostituendo in d(x) le coordinate di un punto
che appartiene alla classe ω2, si ottiene un
valore negativo.
Per i valori che cadono sulla linea di
demarcazione, la classe è indeterminata.
Pertanto d(x) può essere usata come funzione
discriminante.
Intelligenza Artificiale - Pattern
Recognition 1
17
Questo approccio si può estendere al caso in
cui ci sono più di due classi, e si può
scegliere come funzione discriminante
qualsiasi funzione dello spazio euclideo, non
necessariamente lineare.
Intelligenza Artificiale - Pattern
Recognition 1
18
Funzioni di decisione lineari
Una funzione di decisione lineare nel caso più generale di
n dimensioni assume la forma:
d ( x ) = w1 x1 + w2 x2 + ... + wn xn + wn +1 = w ' x + wn +1
w è detto vettore dei pesi o dei parametri.
Intelligenza Artificiale - Pattern
Recognition 1
19
Funzioni di decisione lineari
Per convenzione si aggiunge una componente unitaria
(cioè un 1) al vettore pattern e il peso wn +1
al vettore dei pesi, per cui:
′
x = ( x1 , x2 ,..., xn ,1)
′
w = (w1 , w2 ,..., wn , wn +1 )
e
d (x) = w' x
Intelligenza Artificiale - Pattern
Recognition 1
20
Quindi nell’esempio precedente di una funzione di decisione
per due classi si ha:
⎧ > 0 se x ∈ ω1
d (x) = w' x ⎨
⎩< 0 se x ∈ ω2
Cosa succede se vi sono più classi ω1 , ω2 ,..., ωM ?
Intelligenza Artificiale - Pattern
Recognition 1
21
Caso 1:
Le classi sono separabili mediante singole superfici di
decisione. In questo caso si ha ancora:
⎧ > 0 se x ∈ ωi
con i=1,2,…,M
di ( x ) = wi ' x ⎨
⎩< 0 altrimenti
dove:
′
wi = (wi1 , wi 2 ,..., wi ,n +1 )
è il vettore pesi associato con la i-esima funzione di
decisione.
Intelligenza Artificiale - Pattern
Recognition 1
22
Esempio
Se x appartiene ad ω1 è chiaro dalla geometria che
d1 ( x ) > 0 mentre d 2 ( x ) < 0 e d3 ( x ) < 0
Intelligenza Artificiale - Pattern
Recognition 1
23
Esempio numerico
Intelligenza Artificiale - Pattern
Recognition 1
24
Le funzioni di decisione sono:
d1 ( x ) = − x1 + x2
d 2 ( x ) = x1 + x2 − 5
d 3 ( x ) = − x2 + 1
I limiti di decisione sono le rette:
− x1 + x2 = 0
x1 + x2 − 5 = 0
− x2 + 1 = 0
Se x = (6,5) , sostituendo si ha:
d1 ( x ) = −1
d2 ( x ) = 6
d 3 ( x ) = −4
il punto appartiene a ω2
Intelligenza Artificiale - Pattern
Recognition 1
25
Si osservi che:
Tutti i punti per cui è d i = k ( x ) > 0 e d i ≠ k ( x ) < 0
sono assegnati alla classe ω k : le superfici determinano
cioè una regione di decisione;
Ci possono essere punti per cui più di una d i ( x )
è maggiore di zero (oppure tutte le d i ( x ) sono minori
di zero); per questi punti non si può avere una
decisione adottando questo schema di classificazione.
Intelligenza Artificiale - Pattern
Recognition 1
26
Caso 2:
Ogni classe è separabile da ciascuna altra mediante una
distinta superficie di decisione, cioè le classi sono
separabili a coppie.
In questo caso ci sono M ( M − 1) superfici di decisione
2
(la combinazione di M classi prese a due a due).
Le funzioni di decisione sono qui nella forma:
d ij ( x ) = w 'ij x
Intelligenza Artificiale - Pattern
Recognition 1
27
Se
x
appartiene alla classe ωi allora
per tutti i
j ≠ i.
d ij ( x ) > 0
Queste funzioni hanno la proprietà che
d ij ( x ) = − d ji (x )
Intelligenza Artificiale - Pattern
Recognition 1
28
Esempio
Intelligenza Artificiale - Pattern
Recognition 1
29
Esempio numerico
d12 ( x ) = − x1 − x2 + 5
d13 ( x ) = − x1 + 3
d 23 ( x ) = − x1 + x2
Intelligenza Artificiale - Pattern
Recognition 1
30
Graficamente:
Intelligenza Artificiale - Pattern
Recognition 1
31
Ad esempio, la regione della classe ω1 è determinata
dai valori di
x
per i quali è
d12 ( x ) > 0
e
d13 ( x ) > 0
( d 23 ( x ) in questo caso è irrilevante).
Si rammenti che vale la relazione
d ij ( x ) = − d ji (x )
Intelligenza Artificiale - Pattern
Recognition 1
32
Pertanto se si deve classificare
x = ( 4,3)'
sostituendo si ha:
d12 ( x ) = −2
d13 ( x ) = −1
d 23 ( x ) = −1
e dalla relazione precedente si desume:
d 21 ( x ) = 2
d 31 ( x ) = 1
Intelligenza Artificiale - Pattern
Recognition 1
d 32 ( x ) = 1
33
Essendo
d3 j ( x ) > 0
per j=1,2
allora il pattern è assegnato alla classe
Intelligenza Artificiale - Pattern
Recognition 1
ω3 .
34
Caso 3:
Esistono M funzioni di decisione d k ( x ) = w 'k x con
k = 1,2,…M con la proprietà che se x appartiene alla
classe ωi , sia d i ( x ) > d j ( x ) per tutti i j ≠ i
Può essere considerato una particolarizzazione del caso
2, poiché si può definire:
dij ( x ) = di ( x ) − d j ( x )
= ( wi − w j )' x
= w 'ij x
Intelligenza Artificiale - Pattern
Recognition 1
35
Si può verificare facilmente che se d i ( x ) > d j ( x ) per tutti
i j ≠ i , allora si verifica anche che d ij ( x ) > 0 per tutti i
j ≠ i : se una classe è separabile con le condizioni del
caso 3, lo è anche con quelle del caso 2 (il viceversa non
è generalmente vero).
Intelligenza Artificiale - Pattern
Recognition 1
36
Esempio
Intelligenza Artificiale - Pattern
Recognition 1
37
Per i pattern della classe ω1, si richiede che d1 ( x ) > d 2 ( x )
e d1 ( x ) > d 3 ( x ) , ovvero si richiede che questi pattern
cadano sul lato positivo della superficie d1 ( x ) − d 2 ( x ) = 0
e d1 ( x ) − d3 ( x ) = 0 .
In generale si richiede che i pattern della classe ωi
cadano sul lato positivo delle superfici d i ( x ) − d j ( x ) = 0
con j = 1...M e j ≠ i
Intelligenza Artificiale - Pattern
Recognition 1
38
Anche qui vale che il lato positivo di d i ( x ) − d j ( x ) = 0
è il lato negativo di d j ( x ) − d i ( x ) = 0
Intelligenza Artificiale - Pattern
Recognition 1
39
Esempio numerico
Intelligenza Artificiale - Pattern
Recognition 1
40
Le funzioni di decisione siano:
d1 ( x ) = − x1 + x2
d 2 ( x ) = x1 + x2 − 1
d3 ( x ) = − x2
I confini tra le classi si determinano così:
d1 ( x ) − d 2 ( x ) = −2 x1 + 1 = 0
d1 ( x ) − d3 ( x ) = − x1 + 2 x2 = 0
d 2 ( x ) − d3 ( x ) = x1 + 2 x2 − 1 = 0
Intelligenza Artificiale - Pattern
Recognition 1
41
Per trovare la regione che corrisponde alla classe ω1
occorre trovare la regione per cui d1 ( x ) > d 2 ( x ) e
d1 ( x ) > d 3 ( x ) , cioè la regione che cade sul lato positivo
dei piani − 2 x1 + 1 = 0 e − x1 + 2 x2 = 0
.
Se poi è richiesto di classificare il pattern x = (1,1)' ,
sostituendo si ha: d1 ( x ) = 0 , d 2 ( x ) = 1 , d 3 ( x ) = −1
.
Essendo d 2 > d1 e d 2 > d 3 , il pattern appartiene alla classe
ω2 .
Intelligenza Artificiale - Pattern
Recognition 1
42
Funzioni di decisione generalizzate
I confini tra le classi non sono sempre esprimibili mediante
piani.
Si può stabilire una funzione di discriminazione non lineare
introducendo opportune funzioni f i ( x ) , così
d ( x ) = w1 f1 ( x ) + w2 f 2 ( x ) + ... + wk f k ( x ) + wk +1
Le f i ( x ) sono funzioni reali a singolo valore.
Intelligenza Artificiale - Pattern
Recognition 1
43
Poiché una volta valutate le f i ( x ) forniscono un solo
valore, si può porre:
⎛
⎜
⎜
*
x =⎜
⎜
⎜
⎜
⎝
f1 ( x ) ⎞
⎟
f2 ( x ) ⎟
M ⎟
⎟
fk ( x ) ⎟
⎟
1 ⎠
e riscrivere l’espressione precedente come d ( x ) = w ' x *
Intelligenza Artificiale - Pattern
Recognition 1
44
Se, ad esempio, x = ( x1 , x2 )' , una funzione discriminante
quadratica è :
d ( x ) = w x + w12 x1 x2 + w x + w1 x1 + w2 x2 + w3
2
11 1
2
22 2
allora ponendo x = (x12 , x1 x2 , x22 , x1 , x2 ,1)
*
′
w = (w , w , w , w , w , w )
si ha: d ( x * ) = w ' x *
11
12
22
1
2
3
*
(si osservi che la dimensionalità k di x è maggiore della
dimensionalità n di x ).
Intelligenza Artificiale - Pattern
Recognition 1
45
Si può generalizzare la forma quadratica così:
n
n −1
d ( x ) = ∑ w jj x + ∑
j =1
2
j
n
∑w
j =1 k = j +1
n
jk
x j xk + ∑ w j x j + wn +1
j =1
(n + 1)(n + 2) termini pesi)
n(n − 1)
+n=
(ci sono n +
2
2
Confrontando l’espressione precedente con quella generale:
d ( x ) = w1 f1 ( x ) + w2 f 2 ( x ) + ... + wk f k ( x ) + wk +1
si deduce che f i ( x ) = x ⋅ x con p, q = 1,2,..., n e s, t = 0,1
s
p
t
q
Intelligenza Artificiale - Pattern
Recognition 1
46
Si può dedurre per induzione una forma generale per
funzioni polinomiali di ordine r:
f i ( x ) = x x ...x
S1
p1
S2
p2
Sr
pr
con p1 , p2 ,... pr = 1,2,..., n e s1 , s2 ,..., sr = 0,1
e ancora una forma recursiva per ricavare d(x):
n
d r (x) = ∑
n
∑
p1 =1 p2 = p1
...
n
r −1
w
x
x
...
x
+
d
(x)
∑ p1 p2 ... pr p1 p2 pr
pr = pr −1
0
dove r è il grado di non linearità e d ( x ) = wn +1
Intelligenza Artificiale - Pattern
Recognition 1
47
Lo spazio dei pattern e lo spazio dei pesi
Si supponga che esistano solo due classi ω1 e ω2 ,
2
2
(
x
,
x
e
ciascuna rappresentata da due punti (x , x )
1
2 ).
1
1
1
2
Se le classi sono linearmente separabili esiste una
funzione d ( x ) che, se è d ( x ) > 0 per una classe è
d ( x ) < 0 per l’altra.
Intelligenza Artificiale - Pattern
Recognition 1
48
′
deve
(
)
w
=
w
,
w
,
w
Quindi il vettore dei pesi
1
2
3
soddisfare le relazioni:
w x + w x + w3 > 0
1
1 11
1
2 12
w x + w x + w3 > 0
1
1 21
1
2 22
w x + w x + w3 < 0
2
1 11
2
2 12
w x + w x + w3 < 0
2
1 21
2
2 22
w è pertanto la soluzione del sistema di disuguaglianze.
Intelligenza Artificiale - Pattern
Recognition 1
49
Si preferisce porre il sistema moltiplicando per -1 le
ultime due disuguaglianze:
w x + w x + w3 > 0
1
1 11
1
2 12
w x + w x + w3 > 0
1
1 21
1
2 22
− w x − w x − w3 > 0
2
1 11
2
2 12
− w x − w x − w3 > 0
2
1 21
2
2 22
Si osservi che le x sono i coefficienti e le w le variabili.
Intelligenza Artificiale - Pattern
Recognition 1
50
Il luogo dei punti che soddisfa le disuguaglianze è detto
spazio dei pesi.
Osservazione
Lo spazio dei pattern è uno spazio euclideo n-dimensionale.
In questo spazio, w è un insieme di coefficienti che
determinano una superficie di decisione:
Intelligenza Artificiale - Pattern
Recognition 1
51
Lo spazio dei pesi è uno spazio euclideo (n+1)-dimensionale.
In questo spazio, ogni disuguaglianza rappresenta il lato
positivo o negativo di un iperpiano che passa per l’origine
(con equazioni tipo w1 x11 '+ w2 x12 '+ w3 = 0 ).
Intelligenza Artificiale - Pattern
Recognition 1
52
Nota alla figura precedente:
posizione e lato positivo degli iperpiani: la
figura b) corrisponde al primo set di
disuguaglianze, la figura c) al secondo set: la
soluzione ovviamente è la stessa.
La regione delle soluzioni è caratterizzata
dall’essere una figura conica (più
precisamente, un cono poliedrico convesso).
Intelligenza Artificiale - Pattern
Recognition 1
53
Dicotomia
Una misura del potere discriminante delle funzioni di
decisione è il numero di modi con cui possono classificare
un dato set di pattern.
Si consideri uno spazio bidimensionale con 4 pattern
x1 , x2 , x3 , x4
Intelligenza Artificiale - Pattern
Recognition 1
54
Ciascuna linea corrisponde ad una differente classificazione
dei pattern in due classi.
Ad esempio, la linea 1 separa x1 dal gruppo x2 , x3 , x4 .
Poiché possiamo decidere di assegnare x1 o ad ω1 o ad ω2 ,
la linea 1 produce dueIntelligenza
possibili
classificazioni.
Artificiale
- Pattern
Recognition 1
55
In questo caso il numero di raggruppamenti in due classi
4
2
(dicotomie) è 14 (cioè due in meno di = 16 ).
Si può dimostrare che il numero di dicotomie lineari
di N punti in uno spazio euclideo n-dimensionale,
se i punti sono ben distribuiti, è dato da:
⎧ n N −1
⎪2∑ Ck se N > n + 1
(
N − 1)!
N −1
D( N,n ) = ⎨ k =0
con Ck =
( N − 1 − k )!k!
⎪⎩ 2 N se N ≤ n + 1
D( N,n ) cresce rapidamente al crescere di N e n!
Intelligenza Artificiale - Pattern
Recognition 1
56
Realizzazione delle funzioni di decisione
Se la determinazione dei parametri delle funzioni di
decisione è complessa, la realizzazione di classificatori
multiclasse è relativamente semplice.
Un possibile diagramma a blocchi, ipotizzando di trattare
una multiclasse di tipo 3 ( d i ( x ) > d j ( x ) per tutti i j ≠ i )
è nella figura seguente.
Intelligenza Artificiale - Pattern
Recognition 1
57
Se la funzione di decisione è di tipo qualsiasi, il preprocessor
realizza il calcolo necessario in:
d ( x ) = w1 f1 ( x ) + w2 f 2 ( x ) + ... + wk f k ( x ) + wk +1
Intelligenza Artificiale - Pattern
Recognition 1
58
Se la funzione di valutazione è lineare si può avere una
realizzazione semplice e poco costosa in hardware: per
ogni classe si utilizza una rete resistiva:
Intelligenza Artificiale - Pattern
Recognition 1
59
Se poi si hanno solo due classi, il sistema si semplifica
ulteriormente mediante l’uso di “threshold gate”:
Valore 1 ⇒ classe ω1
Valore -1 ⇒ classe ω2
Intelligenza Artificiale - Pattern
Recognition 1
60