TEORIE E TECNICHE DEL
RICONOSCIMENTO
CLASSIFICAZIONE AUTOMATICA
CLASSIFICAZIONE DI PDD
CLASSIFICAZIONE DI TESTI
CLASSIFICAZIONE
• Un CLASSIFICATORE e’ una FUNZIONE da
oggetti che si vogliono classificare a etichette
– Determinate la parte del discorso di un token
– Assegnare valore SPAM/NO SPAM a email
– Positivo / negativo
• La disambiguazione delle parti del discorso e
molti altri problemi in LC possono essere visti
come problemi di classificazione
DISAMBIGUAZIONE DELLE PARTI DEL
DISCORSO COME CLASSIFICAZIONE
• La disambiguazione delle parti del discorso
(POS tagging) puo’ essere vista come un
classificatore che determina l’interpretazione
piu’ probabile di ogni parola (nome, verbo,
etc)
UNA VISIONE GEOMETRICA DELLA
CLASSIFICAZIONE
SPAM
NON-SPAM
ESEMPIO DI CLASSIFICATORE:
REGRESSIONE LOGISTICA
x2
3
2
1
1
2
Predici “
3
x1
“ if
ESEMPIO DI CLASSIFICATORE:
DECISION TREE
IL RUOLO DELL’APPRENDIMENTO
AUTOMATICO
• Un decision tree come quello appena visto
potrebbe essere scritto a mano
• Ma nella linguistica computazionale moderna,
questi classificatori non vengono specificati a
mano, ma vengono APPRESI
AUTOMATICAMENTE a partire da esempi.
METODI PER L’APPRENDIMENTO
• SUPERVISIONATI (SUPERVISED)
– Imparano da esempi etichettati
– Modellano l’apprendimento tramite insegnanti
• NON SUPERVISIONATI (UNSUPERVISED)
– Scoprono da soli la struttura del problema
– Modellano l’apprendimento del linguaggio
• SEMI-SUPERVISED
– Ricevono come input pochi esempi poi procedono
per somiglianza
SUPERVISED CLASSIFICATION FOR POS
TAGGING
• L’algoritmo di apprendimento riceve come
input un corpus di TRAINING classificato con
POS tags
– La/Art gatta/N fece/V un/Art salto/N ./.
– Giuseppe/PN e’/V matto/Adj ./.
• Si estrae le features / calcola le probabilita’
• Costruisce un MODELLO che puo’ poi essere
usato per classificare ALTRI testi
TRAIN/TEST
POS TAGGER BASATI SU N-GRAMS
• Un POS TAGGER BASATO SU N-GRAMS e’ un
classificatore che riceve come input informazioni
sulla parola e le parole che la precedono
– UNIGRAM PROBABILITY: P(N|salto), P(V|salto)
– BI-GRAM PROBABILITY: P(NN|un salto)
– ….
• Produce in output una probabilita’
– P(N|Uprob, 2Prob, ….) = …
– P(V|UProb, 2Prob, …) = …
• Sceglie la PDD con probabilita’ maggiore
POS-TAGGING A N-GRAMS
• Scelta della soluzione con la probabilita’
maggiore:
argmax P(t1..tn | w1..wn )
t i T
16
Classificazione di PDD usando ngrammi
CONTESTO
FREQUENZA
17
Stima delle probabilita’
Can be done using Maximum Likelihood Estimation as
usual, for BOTH probabilities:
18
Esempio
• Secretariat/NNP is/VBZ expected/VBN to/TO race/VB
tomorrow/NN
• People/NNS continue/VBP to/TO inquire/VB the/DT
reason/NN for/IN the/DT race/NN for/IN outer/JJ space/NN
• Problem: assign a tag to race given the subsequences
– to/TO race/???
– the/DT race/???
• Solution: we choose the tag that has the greater of these
probabilities:
– P(VB|TO) P(race|VB)
– P(NN|TO)P(race|NN)
19
Tagging with MMs (2)
• Actual estimates from the Switchboard corpus:
• LEXICAL FREQUENCIES:
– P(race|NN) = .00041
– P(race|VB) = .00003
• CONTEXT:
– P(NN|TO) = .021
– P(VB|TO) = .34
• The probabilities:
– P(VB|TO) P(race|VB) = .00001
– P(NN|TO)P(race|NN) = .000007
20
N-GRAM POS TAGGER IN NLTK
• NLTK, 5.5:
– Addestramento di unigrammi
– Addestramento di bigrammi
ALTRI METODI PER L’APPRENDIMENTO
• NAÏVE BAYES
• DECISION TREES
NAÏVE BAYES
• Metodi Bayesiani: decisione su classificazione
basata su
– un modello PROBABILISTICO
– che coniuga uso di informazioni A PRIORI ed A
POSTERIORI come nella regola di Bayes
• Metodi NAÏVE BAYES: si fanno assunzioni che
semplificano molto il calcolo delle probabilità
Legge di Bayes
P(C , X )  P(C | X ) P( X )  P( X | C ) P(C )
P( X | C ) P(C )
P(C | X ) 
P( X )
Bayes applicata alla classificazione
P(Classe|Proprietà) = P(Proprietà|Classe)*P(Classe) /
P(Proprietà)
Maximum a posteriori Hypothesis
hMAP  argmax P(h | D)
hH
hMAP
P( D | h ) P( h )
 argmax
P( D )
hH
hMAP  argmax P( D | h) P(h)
hH
Naive Bayes Classifiers
Task: Classify a new instance based on a tuple of attribute values
x1 , x2 ,, xn
cMAP  argmax P(c j | x1 , x2 ,, xn )
c j C
cMAP  argmax
c j C
P( x1 , x2 ,, xn | c j ) P(c j )
P(c1 , c2 ,, cn )
cMAP  argmax P( x1 , x2 ,, xn | c j ) P(c j )
c j C
Naïve Bayes Classifier: Assumptions
• P(cj)
– Can be estimated from the frequency of classes in
the training examples.
• P(x1,x2,…,xn|cj)
– O(|X|n•|C|)
– Could only be estimated if a very, very large
number of training examples was available.
Conditional Independence Assumption:
 Assume that the probability of observing the conjunction of
attributes is equal to the product of the individual probabilities.
The Naïve Bayes Classifier
Flu
X1
runnynose
X2
sinus
X3
cough
X4
fever
X5
muscle-ache
• Conditional Independence Assumption:
features are independent of each other
given the class:
P( X 1 ,, X 5 | C )  P( X 1 | C )  P( X 2 | C )   P( X 5 | C )
Learning the Model
C
X1
X2
X3
X4
X5
X6
• Common practice:maximum likelihood
– simply use the frequencies in the data
N (C  c j )
ˆ
P (c j ) 
N
Pˆ ( xi | c j ) 
N ( X i  xi , C  c j )
N (C  c j )
Problem with Max Likelihood
Flu
X1
runnynose
X2
sinus
X3
cough
X4
fever
X5
muscle-ache
P( X 1 ,, X 5 | C )  P( X 1 | C )  P( X 2 | C )   P( X 5 | C )
• What if we have seen no training cases where patient had no flu and
muscle aches?
N ( X 5  t , C  nf )
ˆ
P( X 5  t | C  nf ) 
0
N (C  nf )
• Zero probabilities cannot be conditioned away, no matter the other
evidence!
  arg max c Pˆ (c)i Pˆ ( xi | c)
Smoothing to Avoid Overfitting
Pˆ ( xi | c j ) 
N ( X i  xi , C  c j )  1
N (C  c j )  k
# of values of Xi
• Somewhat more subtle version
Pˆ ( xi ,k | c j ) 
overall fraction in data
where Xi=xi,k
N ( X i  xi ,k , C  c j )  mpi ,k
N (C  c j )  m
extent of
“smoothing”
Using Naive Bayes Classifiers to
Classify Text: Basic method
• Attributes are text positions, values are words.
cNB  argmax P(c j ) P( xi | c j )
c jC
i
 argmax P(c j ) P( x1 " our" | c j )  P( xn " text" | c j )
c jC

Naive Bayes assumption is clearly violated.



Example?
Still too many possibilities
Assume that classification is independent of the positions of the
words

Use same parameters for each position
ESEMPIO DI CLASSIFICAZIONE:
DOCUMENT CLASSIFICATION
(NLTK book, p. 227-228)
VALUTAZIONE
• ACCURACY: percentuale di risposte corrette
• Nel caso di problemi in cui la classe di
interesse rappresenta una percentuale
minima del totale: PRECISION e RECALL
PRECISION E RECALL
ESEMPIO DI CLASSIFICAZIONE:
GENDER IDENTIFICATION
(NLTK book, p. 222-227)
APPRENDERE DECISION TREES
• Top-down: dato un certo insieme di esempi,
trovare la proprieta’ che permette di dividerli
in sottogruppi piu’ COERENTI
• Poi si procede ricorsivamente
• Scelta della proprieta’: INFORMATION GAIN
DECISION TREE PER IL
NAME GENDER TASK
Selezione della proprieta’
• La scelta della proprieta’ da usare per dividere
l’insieme corrente in sottinsiemi piu’ coerenti
si basa su un criterio di RIDUZIONE DEL
DISORDINE basato sulla nozione di ENTROPIA
ENTROPIA
Entropia di decision trees
• Entropia del DT per gender identification: vedi
NLTK, 6.4
INFORMATION GAIN
TEXT CATEGORIZATION WITH DT
• Build a separate decision tree for each
category
• Use WORDS COUNTS as features
Reuters Data Set
(21578 - ModApte split)
• 9603 training, 3299 test articles; ave. 200 words
• 118 categories
– An article can be in more than one category
– Learn 118 binary category distinctions
Common categories
(#train, #test)
•
•
•
•
•
Earn (2877, 1087)
Acquisitions (1650, 179)
Money-fx (538, 179)
Grain (433, 149)
Crude (389, 189)
•
•
•
•
•
Trade (369,119)
Interest (347, 131)
Ship (197, 89)
Wheat (212, 71)
Corn (182, 56)
54
AN EXAMPLE OF REUTERS TEXT
Foundations of Statistical
Natural Language Processing,
Manning and Schuetze
Decision Tree for Reuter classification
Foundations of Statistical
Natural Language Processing,
Manning and Schuetze
Information gain & text classification