IR - 10 - Text Classification
Lecture Info
Date:
Sito corso: link
Slides:
Introduzione: In questa lezione abbiamo introdotto ed affrontato il problema della text classification utilizzando il classico classificatore Naïve Bayes. Infine, per terminare la lezione, abbiamo concluso la trattazione dei modelli di linguaggio iniziata nella lezione precedente.
1 Text Classification
Il problema della text classification è un problema standard nel contesto del machine learning. Tale problema può essere così descritto: abbiamo in input un certo numero di classi diverse e una collezione documentale. Il problema consiste nell'assegnare, ad ogni documento della collezione, la giusta classe di appartenenza, andando così facendo a "classificare" il documento.
Osservazione 1: Un contesto in cui si deve risolvere un problema di text classification si trova nei filtri e-mail anti spam.
Osservazione 2: È possibile avere situazioni in cui un documento può parlare di più topics diversi, e vogliamo attuare una classificazione più graduale, in cui al posto di assegnare il documento ad una sola classe, vogliamo capire quanto il documento parla di ogni topic, o comunque quali sono i principali topics di un dato documento.
Per risolvere il problema della text classification si possono utilizzare delle tecniche di machine learning a partire da un dataset etichettato
\[D \subseteq X \times C\]
dove \(X\) è l'insieme dei documenti e \(C\) è l'insieme delle classi dei vari documenti.
L'algoritmo di learning utilizza il dataset \(D\) per ottenere il classificatore, che è una funzione \(\gamma: X \to C\) che mappa un documento \(d \in X\) in una classe \(c \in C\). Ci sono vari metodi per costruire la funzione \(\gamma\). Tra questi troviamo:
Rule Based: L'idea di questo approccio è quello di definire delle regole deterministiche che possono essere utilizzate per classificare i documenti. Questo approccio veniva inizialmente utilizzato nei motori di ricerca, dove la rilevenza dei documenti veniva calcolata a mano. Questo approccio però è molto costoso e molto spesso non funziona, in quanto
È difficile estrarre conoscenza dai dati;
È difficile formalizzare la conoscenza estratta in regole deterministiche;
È difficile comunicare tra esperti di diversi settori.
Statistical/Probabilistic Based: Questi metodi si basano sull'utilizzo di dati già elaborati (tipicamente da esseri umani) per produrre modelli statistici che ci permettono di risolvere il problema.
Andiamo adesso ad analizzare un particolare classificatore basato su un approccio statistico.
1.1 Naïve Bayes Classifier
Questo tipo di classificatore è un classificatore probabilistico che dato un documento \(d\) calcola la sua classe con un approccio di tipo MAP (Maximum A Posteriori Class) nel seguente modo
\[ C_{\text{map}} = \underset{c \in C}{arg\,max} \,\,\, \hat{P}(c \,\,|\,\,d) = \underset{c \in C}{arg\,max} \,\,\, \hat{P}(c) \cdot \prod\limits_{1 \leq k \leq n_d} \hat{P}(t_k \,\,|\,\, c) \]
dove,
\(n_d\) è la lunghezza del documento \(d\).
\(P(t_k \,\,|\,\, c)\) è la probabilità di osservare il termine \(t_k\) se il documento \(d\) è nella classe \(c\).
\(P(c)\) è la probabilità a priori che il documento appartenga alla classe \(c\).
La classificazione quindi prevede due fasi, che sono:
Prima ci si calcola tutte le probabilità tramite delle stime.
Poi si assegna ad ogni documento una particolare classe utilizzando le probabilità calcolate nel passo precedente.
Dato che il prodotto \(\prod P(t_k \,\,|\,\, c)\) può essere molto piccolo, e dato che ci interessa solo la classe che massimiza il valore dell'espressione, possiamo considerare solo il logaritmo, ottenendo quindi la seguente espressione
\[\log{P(c)} + \sum\limits_{1 \leq k \leq n_d} \log{P(t_k\,\,|\,\,c)}\]
1.1.1 Come stimare i parametri
Per poter utilizzare un classificatore Naïve Bayes necessitiamo delle seguenti cose
Un modello di linguaggio per ogni classe \(C\). Questi modelli possono essere ottenuti tramite una stima effettuata con la massima verosimiglianza nel seguente modo
\[\hat{P}(t \,\,|\,\, c) = \frac{T_{c, t}}{\sum\limits_{t' \in V} T_{c, t'}}\]
dove \(T_{c, t}\) è il numero di occorrenze del termine \(t\) nella classe \(c\) nel dataset utilizzato per fare training.
Probabilità a priori per ogni classe. Nuovamente, possiamo applicare una stima di massima versomiglianza per calcolarci
\[\hat{P}(c) = \frac{N_c}{N}\]
dove \(N_c\) è il numero di documenti della classe \(c\) nel dataset utilizzato per fare training.
1.1.2 Perché Naïve Bayes?
Il classificatore è chiamato Naïve Bayes per le seguenti ragioni:
Bayes: In quanto utilizza la seguente legge probabilistica
\[P(A \,\,|\,\,B) = \frac{P(B \,\,|\,\, A) \cdot P(A)}{P(B)}\]
che prende il nome di regola di Bayes.
Naïve: In quanto si assume che la presenza di una parola non cambia la probabilità della presenza di un'altra parola, e inoltre che la probabilità della presenza di una parola è indipendente dalla posizione della parola nel documento. Formalmente queste ipotesi di indipendenza si traducono in questo modo
\[\begin{split} P(d \,\,|\,\,c) &= P(t_1, t_2, \ldots, t_{n_d} \,\,|\,\,c) \\ &= P(t_1 \,\,|\,\, c) \cdot P(t_2 \,\,|\,\, c) \cdot \ldots \cdot P(t_{n_d} \,\,|\,\, c) \\ \end{split}\]
In questa ipotesi è implicitamente contenuta l'ipotesi bag of words, che ci dice che la posizione dei termini in un documento non conta. Anche se è una ipotesi molto forte, viene utilizzata per semplificare la stima dei parametri, in modo da poter poi fare uso del classificatore.
In generale i classificatori Naïve Bayes funzionano bene in quanto non devono stimare nel modo più corretto possibile le varie probabilità, ma devono solo scegliere la classe giusta.
1.1.3 Smoothing
Le stime effettuate con la massima verosimiglianza possono presentare dei problemi nel caso in cui un termine \(t\) contenuto in una classe \(C\) non compare mai nel campione di documenti presenti nel training dataset. In questo caso infatti tutti i documenti che contengono \(t\) non potranno mai essere classificati con la classe \(C\).
Tale problema prende il nome di problema del cigno nero, ed essenzialmente dice che non aver mai visto un cigno nero, non implica necessariamente che non esiste un cigno nero, e che non lo vedrò mai. Un evento che non ho mai visto dunque potrebbe comunque succedere.
Per risolvere questo problema si effettua dello smoothing, che consiste nel modificare il modo in cui le probabilità vengono stimate nel seguente modo
\[\hat{P}(t \,\,|\,\,c) = \frac{T_{c,t} + 1}{\sum\limits_{t' \in V} (T_{c, t'} + 1)} = \frac{T_{c, t} + 1}{\sum\limits_{t' \in V} T_{c, t'} + B}\]
dove il valore \(1\) nel nominatore è un fattore di smoothing, mentre il valore \(B\) nel denominatore è un fattore di normalizzazione.
1.2 Evaluating Classification
Per valutare il risultato calcolato da un classificatore di testi l'idea è quella di utilizzare le solite metriche della precision, recal, e della media armonica, anche chiamata \(F_1\).
Queste sono state trattate in una precedente lezione.
1.3 Feature Selection
Molto spesso quando stiamo affrontando il problema della text classification vogliamo considerare solo i termini che mi portano informazioni su una particolare classe. Varie metriche possono essere utilizzate per scegliere quali parole utilizzare. Tra queste troviamo:
Analisi della frequenza.
Calcolo della mutual information.
La mutual information (MI) in particolare viene calcolata su una coppia \((t, c)\) e ci dice quanta informazione il termine \(t\) contiene rispetto alla classe \(c\). Più alta è la mutual information, e più la presenza del termine \(t\) nel documento mi permette di stabilire se appartiene o meno alla classe \(c\). La mutual information della coppia \((t, c)\) può essere calcolata come segue
\[I(U;C) = \sum\limits_{e_t \in \{0, 1\}} \sum\limits_{e_c \in\{0, 1\}} P(U = e_t, \,\, C = e_c) \cdot \log_2{\frac{P(U = e_t, \,\, C = e_c)}{P(U = e_t) \cdot P(C=e_c)}}\]
che andandola ad esplicitare diventa
\[\begin{split} I(U;C) = &\frac{N_{11}}{N} \cdot \log_2{\frac{N N_{11}}{N_{1\cdot} N_{1\cdot}}} + \frac{N_{01}}{N} \cdot \log_2{\frac{N N_{01}}{N_{0\cdot} N_{1\cdot}}}\\ &+ \frac{N_{10}}{N} \cdot \log_2{\frac{N N_{10}}{N_{0\cdot} N_{1\cdot}}} + \frac{N_{00}}{N} \cdot \log_2{\frac{N N_{00}}{N_{0\cdot} N_{0\cdot}}}\\ \end{split}\]
dove,
\(N_{11}\) indica il numero di documenti che contengono \(t\) e che si trovano nella classe \(c\).
\(N_{10}\) indica il numero di documenti che contengono \(t\) e che non si trovano nella classe \(c\).
\(N_{01}\) indica il numero di documenti che non contengono \(t\) e che si trovano nella classe \(c\).
\(N_{00}\) indica il numero di documenti che non contengono \(t\) e che non si trovano nella classe \(c\).
Uno dei modi più semplici per fare feature selection consiste nel considerare, per ogni classe, solamente le \(k\) parole che massimizzano la mutual information rispetto alla classe presa in considerazione.
2 Modelli di Linguaggio
Nella scorsa lezione sul ranking avevamo introdotto i modelli di linguaggio come delle distribuzioni su dei termini di un vocabolario.
Per ogni documento \(d\) ci si definisce sopra un modello di linguaggio \(M_d\) e successivamente data una query \(q\) si calcola la probabilità della query rispetto ai vari modelli di linguaggio. I documenti vengono quindi ordinati rispetto al valore di probabilità calcolato.
Ad esempio, se abbiamo due modelli di linguaggio \(M_{d_1}, M_{d_2}\), e ci viene data una query \(q\), allora se
\[P(q \,\,|\,\, M_{d_1}) \leq P(q \,\,|\,\, M_{d_2})\]
il documento più rilevante risulta essere \(d_2\).
Notiamo che ci sono vari possibili modelli di linguaggio che possiamo utilizzare. Ad esempio possiamo avere un modello che per funzionare utilizza le seguenti probabilità
\[\begin{split} P(t_{\delta} \,\,|\,\, t_k, d) := &\text{ probabilità di vedere la sequenza di termini} \\ &\,\,\, t_\delta t_k \text{ all'interno del documento } d \\ \end{split}\]
Tale modello definisce una catena di markov. In generale vale la regola che modelli più complessi sono più precisi, ma sono anche più difficili da addestrare, in quanto necessitano la stima di più parametri e dunque la presenza di dataset di una grandezza significativa. A prescindere dal modello utilizzato però, lo schema restante resta sempre lo stesso.
Nel caso di modelli univariati, la stima delle varie probabilità può essere effettuata tramite la massima versomiglianza.
2.1 Smoothing in Language Models
A differenza dello smoothing effettuato per il classificatore Naïve Bayes, in questo contesto non vogliamo aggiungere ad ogni termine un fattore costante di \(1\). Il fattore di smoothing dovrà dunque dipendere dal numero di volte in cui il termine compare nella collezione di docs, ovvero dal seguente fattore
\[\hat{P}(t \,\,|\,\,M_C) = \frac{\text{cf}_t}{T}\]
dove \(T\) è il numero totale di termini della collezione e \(\text{cf}_t\) è il numero di volte in cui \(t\) appare come termine.
I fattori \(P(t\,\,|\,\,M_d)\) e \(P(t\,\,|\,\,M_C)\) possono poi essere combinati in vari modi. Un esempio è il seguente
\[\hat{P}(t \,\,|\,\,d) = \lambda \cdot \hat{P}(t \,\,|\,\, M_d) + (1 - \lambda) \cdot \hat{P}(t \,\,|\,\,M_C)\]
in questo caso tramite \(\lambda\) sono in grado di pesare quanto influisce il contenuto dell'intera collezione rispetto a quanto influisce il contenuto del singoloo documento. Il valore di \(\lambda\) viene scoperto tramite una operazione di tuning. I casi limite sono i seguenti:
Un valore di \(\lambda\) molto alto favorisce query con tante congiunzioni (\(\text{AND})\).
Un valore di \(\lambda\) molto basso favorisce invece query con tante disgiunzioni (\(\text{OR})\).
2.1.1 Dirichlet Smoothing
In questa particolare tecnica il fattore di smoothing viene aggiornato seguendo un approccio tipicamente Bayesiano. In particolare si ha
\[\hat{P}(t \,\,|\,\,d) = \frac{\text{tf}_{t, d} + \alpha \cdot \hat{P}(t \,\,|\,\, M_C)}{|d| + \alpha}\]
Tale tecnica si basa sull'assunzione che se non ho nulla sul documento allora posso utilizzare la distribuzione rispetto all'intera collezione come distribuzione a priori.