Naive Bayes per l'intento di ricerca: classificare le query con Bayes

Nell’articolo sul multi-armed bandit abbiamo usato Bayes per decidere fra varianti: spostare il traffico verso quella che converte di più mentre il test è ancora in corso. Adesso facciamo un passo di lato, restando però nello stesso impianto di ragionamento: invece di scegliere fra opzioni, vogliamo classificare, cioè attaccare a ogni nuova osservazione l’etichetta più probabile date le sue caratteristiche.
Il caso concreto è uno che chiunque faccia SEO conosce bene: l’intento dietro una query di ricerca. Chi cerca “come fare un dolce” vuole imparare qualcosa; chi cerca “comprare scarpe online” è pronto a tirare fuori la carta di credito. Sono due mondi diversi, e servono contenuti diversi: una guida, un tutorial, un glossario per il primo; una scheda prodotto, un listino, una call to action ben visibile per il secondo. Sbagliare l’intento significa rispondere alla domanda giusta nel modo sbagliato.

Il problema è che le query sono tante e sempre nuove, e classificarle a mano non scala. Ci serve un metodo che impari da un po’ di esempi etichettati e poi se la cavi da solo sulle query mai viste. L’algoritmo che fa questo con un’eleganza quasi disarmante è il Naive Bayes, e — come il nome lascia intuire — parte ancora una volta dal teorema di Bayes che ci accompagna da tutto questo percorso.

Di cosa parleremo:

Dal teorema al classificatore
Addestrare su query etichettate
Classificare le query nuove
I limiti del “naive”
Prova tu
Per approfondire

Dal teorema al classificatore

Riprendiamo il filo. Il teorema di Bayes ci dice come aggiornare la probabilità di un’ipotesi alla luce dei dati osservati. Qui l’ipotesi è “questa query appartiene alla classe informazionale” (oppure transazionale), e i dati sono le parole che compongono la query. Vogliamo cioè la probabilità di una classe dato il testo: in simboli, P(classe | parole).

Calcolarla direttamente sarebbe un incubo, perché le combinazioni di parole possibili sono sterminate. Bayes ci permette di girare il problema: invece di chiederci quanto è probabile la classe viste le parole, ci chiediamo quanto sono probabili quelle parole vista la classe — una domanda a cui i dati di addestramento sanno rispondere. La regola, prima a parole e poi in formula, è che la probabilità di una classe data una query è proporzionale alla probabilità a priori della classe moltiplicata per la probabilità di osservare quelle parole se la classe fosse quella:

\( P(\text{classe} \mid \text{parole}) \propto P(\text{classe}) \cdot \prod_i P(\text{parola}_i \mid \text{classe}) \\ \)

Sciogliamo i simboli. P(classe) è il prior: quanto è frequente quella classe in partenza, prima di guardare il testo (se metà delle query d’esempio sono informazionali, il prior è 0,5). P(parola | classe) è quanto spesso quella parola compare nelle query di quella classe. Il simbolo ∏ è semplicemente il prodotto: moltiplichiamo i contributi di tutte le parole della query. Il segno ∝ (“proporzionale a”) ci ricorda che stiamo trascurando un denominatore costante, identico per tutte le classi: visto che alla fine ci interessa solo quale classe vince, possiamo ignorarlo senza danni.

Ed eccolo, il punto in cui si annida il “naive”. Moltiplicare le probabilità delle singole parole come se fossero indipendenti l’una dall’altra equivale ad assumere che, nota la classe, la presenza di una parola non dica nulla sulla presenza delle altre. È un’assunzione palesemente falsa nel linguaggio reale — “carta” e “credito” non compaiono certo a caso una indipendentemente dall’altra — ed è proprio questa ingenuità (in inglese naive) a dare il nome all’algoritmo. La cosa sorprendente, che vedremo, è che pur partendo da un’ipotesi così grossolana il metodo funziona benissimo nella pratica.

Addestrare su query etichettate

Addestrare un Naive Bayes vuol dire una cosa sola: contare. Per ogni classe contiamo quante volte compare ciascuna parola nelle query di esempio, e da quei conteggi ricaviamo le P(parola | classe). Niente ottimizzazione, niente iterazioni: si scorrono i dati una volta e si riempie una tabella di frequenze.

Partiamo da un piccolo insieme di query etichettate a mano, cinque informazionali e cinque transazionali. Addestro il classificatore in R così:

train <- list(
  info  = c("come fare un dolce", "cos e la statistica", "guida seo principianti",
            "tutorial r gratis", "come funziona il bayesiano"),
  trans = c("comprare scarpe online", "prezzo iphone offerta", "miglior hosting economico",
            "acquista corso seo", "sconto abbonamento palestra")
)
tok <- function(s) unlist(strsplit(tolower(s), "\\s+"))
vocab <- unique(unlist(lapply(unlist(train), tok)))
counts <- lapply(train, function(docs) {
  w <- table(factor(unlist(lapply(docs, tok)), levels = vocab)); w + 1
})
tots <- sapply(counts, sum); V <- length(vocab)
prior <- sapply(train, length) / length(unlist(train))   # 0.5 / 0.5

Vediamo cosa succede riga per riga. La funzione tok spezza ogni query in parole minuscole (una tokenizzazione spartana ma sufficiente). vocab è il vocabolario, l’elenco di tutte le parole distinte viste in addestramento: qui sono 31. Per ogni classe, table(factor(...)) conta le occorrenze di ciascuna parola del vocabolario; tots è il totale dei conteggi per classe, e prior qui vale 0,5 e 0,5 perché le due classi hanno lo stesso numero di esempi.

C’è un dettaglio in quel w + 1 che merita una sosta, perché è il trucco che tiene in piedi tutto l’edificio. Se una parola non compare mai nelle query di una classe, il suo conteggio è zero, e con esso si azzererebbe l’intero prodotto delle probabilità: una sola parola sconosciuta basterebbe a mandare a zero la probabilità della classe, cancellando il contributo di tutte le altre. È il classico caso in cui “moltiplicare per zero” rovina la festa. La soluzione si chiama smoothing di Laplace: aggiungiamo 1 al conteggio di ogni parola, in ogni classe, prima di calcolare le proporzioni. Nessuna parola ha più probabilità esattamente nulla, solo molto piccola.

Il prezzo dello smoothing è che ai totali per classe va aggiunto il numero di parole del vocabolario (le 31 unità aggiunte una per parola): per questo tots non vale 18 e 15 — i token grezzi delle due classi — ma 49 e 46. Con questi numeri, per esempio, la parola “comprare” (presente una volta fra le transazionali, mai fra le informazionali) ha P(comprare | trans) = 2/46 ≈ 0,043 contro P(comprare | info) = 1/49 ≈ 0,020: più del doppio, ed è proprio questo squilibrio che spinge una query verso l’intento giusto. Una parola neutra come “seo”, che compare una volta per parte, resta invece quasi bilanciata fra le due classi e non sposta l’ago.

Classificare le query nuove

Con la tabella delle frequenze pronta, classificare una query nuova è davvero un giochetto da ragazzi: si tokenizza, si sommano i logaritmi delle probabilità di ciascuna parola (sommare logaritmi anziché moltiplicare probabilità evita che il prodotto di tanti numeri piccolissimi vada in underflow numerico, ma il risultato è lo stesso), si aggiunge il logaritmo del prior e si sceglie la classe con il punteggio più alto. Calcolo in R:

classify <- function(query) {
  w <- tok(query)
  logp <- log(prior)
  for (cl in names(train)) {
    p <- counts[[cl]][w]; p[is.na(p)] <- 1            # parola fuori vocab: peso neutro
    logp[cl] <- logp[cl] + sum(log(as.numeric(p) / tots[cl]))
  }
  names(which.max(logp))
}
cat("'comprare corso seo scontato' ->", classify("comprare corso seo scontato"), "\n")
cat("'come imparare la statistica'  ->", classify("come imparare la statistica"), "\n")

L’output è netto:

'comprare corso seo scontato' -> trans
'come imparare la statistica'  -> info

Come si vede, il classificatore assegna la prima query all’intento transazionale e la seconda all’informazionale, esattamente come avrebbe fatto un essere umano. Vale la pena notare come ci arriva. Nella prima query “comprare” e “scontato” tirano con decisione verso trans, “seo” resta neutra, e nemmeno “corso” — che in addestramento compariva nel transazionale “acquista corso seo” — rema contro: il verdetto è solido. Nella seconda, “statistica” è una parola spiccatamente informazionale, e “imparare”, pur essendo fuori vocabolario, non fa danni grazie a quel p[is.na(p)] <- 1 che assegna alle parole mai viste un peso neutro, identico per entrambe le classi: non potendo dire nulla, semplicemente non vota.

Cinque query d’esempio per parte sono pochissime, eppure il meccanismo è già tutto qui. In un caso reale basta sostituire le manciate di query etichettate con qualche centinaio o migliaio di query estratte dalla Search Console e annotate per intento, e lo stesso codice — invariato nella struttura — diventa un classificatore di intento utilizzabile sul serio.

I limiti del “naive”

Prima di lanciarsi, però, è bene sapere dove il metodo mostra la corda, perché la sua semplicità ha un rovescio.

Il limite più evidente è proprio l’assunzione di indipendenza da cui prende il nome. Trattando ogni parola come slegata dalle altre, il Naive Bayes ignora del tutto l’ordine e il contesto: per lui “scarpe da corsa economiche” e “economia delle scarpe da corsa” sono lo stesso sacchetto di parole (bag of words, come dicono gli anglosassoni). Nella classificazione d’intento questo conta poco, ma in compiti più sottili può ingannare. C’è poi la questione delle parole fuori vocabolario: una query fatta solo di termini mai visti in addestramento finirebbe decisa dal solo prior, cioè da un puro testa o croce — il segnale che il dataset di esempi è troppo magro e va ampliato.

Un avvertimento che vale per qualunque classificatore, e a maggior ragione per uno addestrato su pochi dati: il modello impara esattamente ciò che gli mostriamo, bias compresi. Se le query d’esempio transazionali contengono tutte la parola “comprare”, il classificatore assocerà l’intento d’acquisto a quel termine e arrancherà su un “aggiungi al carrello” altrettanto transazionale ma lessicalmente diverso. La qualità e la rappresentatività dei dati etichettati contano più della raffinatezza dell’algoritmo: un Naive Bayes nutrito di esempi vari e bilanciati batte un modello sofisticato addestrato male.

Detto questo, il Naive Bayes resta un preziosissimo strumento da avere nella cassetta degli attrezzi: è velocissimo da addestrare, richiede pochi dati per partire, è interpretabile (possiamo sempre andare a vedere quali parole hanno spinto la decisione) e nella classificazione di testo regge il confronto con modelli ben più complessi. È spesso la baseline da battere prima di tirare in ballo artiglieria più pesante — ed è qui che si apre la porta sul machine learning vero e proprio, dove la classificazione si fa con alberi, regressioni e reti che lasciano cadere l’ipotesi di indipendenza in cambio di più potenza (e meno trasparenza).

Prova tu

Il codice qui sopra è un terreno di gioco perfetto per costruire l’intuizione. Le query di ricerca non sono solo informazionali o transazionali: ne manca almeno una terza famiglia, quella navigazionale (chi cerca “facebook login” o “gironi blog” vuole solo arrivare a un sito preciso). Ecco qualche modifica da provare:

Aggiungi una classe nav al train con quattro o cinque query navigazionali (“facebook login”, “youtube”, “amazon accedi”, “gmail posta”), poi riaddestra: il prior non sarà più 0,5 ma circa un terzo per classe. Come cambiano le classificazioni delle query precedenti?
Dài in pasto al classificatore una query ambigua come “recensione iphone” (informativa? transazionale?) e guarda da che parte pende. Aveva senso il verdetto, viste le parole in addestramento?
Togli lo smoothing (sostituisci w + 1 con w) e prova a classificare una query con una parola rara: cosa succede al punteggio quando un conteggio è zero? È il modo più rapido per vedere con i propri occhi perché Laplace serve.

Il bello è che la struttura del codice non cambia: aggiungere una classe vuol dire solo allungare la lista train, e tutto il resto — vocabolario, conteggi, prior, regola di classificazione — si adatta da sé.

Con questo chiudiamo il filo bayesiano che abbiamo dipanato di articolo in articolo: dalla stima di un conversion rate al confronto fra varianti, dall’allocazione adattiva del traffico fino a quest’ultimo salto, dal decidere al classificare. Lo stesso teorema, riproposto ogni volta in una veste diversa, si è rivelato un filo conduttore sorprendentemente robusto. Da qui in avanti la strada si biforca verso il machine learning in senso pieno — gli alberi decisionali, la regressione logistica, le reti — dove i metodi rinunciano alle ipotesi più comode in cambio di potenza, e dove Bayes resta sullo sfondo come la grammatica con cui, in fondo, si impara sempre dai dati.

Per approfondire

Se vuoi passare dal Naive Bayes al machine learning vero e proprio restando con i piedi per terra (e con R sotto mano), An Introduction to Statistical Learning di James, Witten, Hastie e Tibshirani è il testo che consiglio. È la porta d’ingresso più accessibile al machine learning applicato: spiega classificazione, alberi e regressione con il rigore giusto ma senza matematica intimidatoria, e ogni capitolo ha laboratori in R che si possono rifare passo passo. La seconda edizione dedica spazio proprio al Naive Bayes, così il salto da questo articolo al resto del percorso è naturale.

Questo articolo fa parte del percorso «L’approccio bayesiano», la guida ragionata agli articoli su statistica e inferenza bayesiana applicate alla SEO.

Naive Bayes: classificare l’intento delle query con il teorema di Bayes