Quante volte avete ricevuto un messaggio di spam?

E quante volte, invece, questi messaggi sono stati automaticamente spostati nella casella della “posta  indesiderata”?

Mentre scrivo questo articolo, per esempio, nella mia casella di posta  risultano identificati automaticamente ben 56 “messaggi spazzatura”, come potete vedere nella seguente immagine.

In particolare, nella e-mail che si vede in figura, una certa signora Tarangelo sembrerebbe volermi offrire a prezzi convenientissimi del Prozak!

In base all’esperienza comune (sicuramente almeno la mia) si può osservare che, tutto sommato, il cosiddetto filtro antispam funziona quasi sempre.

Vi siete mai chiesti, però, come fa a funzionare? Ovvero come fa a capire se il messaggio è spazzatura o non lo è?

Molti potrebbero rispondere che è sufficiente verificare la presenza di alcune parole tipo “sex” o “viagra” ma, in realtà non è così semplice, visto che questi termini possono essere usati senza dover far parte necessariamente di un “messaggio spazzatura”. Altrimenti qualunque messaggio con la parola “viagra” sarebbe automaticamente classificato come spam.

Vediamo, quindi, uno degli approcci possibili per combattere il problema della spam.

Spam vs Matematica:  i termini del problema

Tutti noi, guardando un’e-mail, capiamo quasi istantaneamente se questa è spazzatura o meno (anche se lo spam  si sta facendo sempre più sofisticata specie quella dei commenti nei blog!).

Visto che le e-mail di spam inviate quotidianamente sono un numero enorme è stato sin dall’inizio necessario sviluppare un sistema automatico per rivelare la spam. In altri termini si è implementato un algoritmo che  fosse in grado di decidere da solo.

Se ci pensate bene, chi si è occupato di questo problema ha dovuto individuare una soluzione  che fosse in grado di:

• imparare dall’esperienza (fase di training)
•  essere migliorate via via in base all’esperienza (visto che la fantasia degli spammer è notevole ed in continua evoluzione).

Nel caso del filtro per le e-mail spazzatura, uno strumento che si è rivelato particolarmente adatto a questo tipo di esigenze è il calcolo delle probabilità ed in particolare l’approccio bayesiano  [1].

Filtro Antispam bayesiano: il Teorema di Bayes  e come si usa

In questo post spiegheremo la versione base di questo filtro che sfrutta, appunto, il teorema di Bayes.

Se volete conoscere più nel dettaglio il Teorema di Bayes vi suggeriamo di leggere questo articolo di Andrea; se, invece,  volete addentrarvi nel mondo della probabilità, consultate questo post di Maurizia.

Qui vi ricordo solamente che il teorema lega la probabilità di un evento A dato un evento B ( $$p(A|B)$$) con la probabilità dell’evento B dato A ( $$p(B|A)$$). Stiamo dicendo, per esempio, che la probabilità che piova dato che ci sono le nuvole è legata alla probabilità che ci siano le nuvole dato che piove e che queste due proprietà sono legate fra loro da una precisa relazione:

$$p(A|B) = \frac{p(B|A)p(A)}{p(B)}$$.

In questa equazione ricordiamo che $$p(A)$$ e $$p(B)$$ sono rispettivamente le probabilità degli eventi A e B.

L’utilità del Teoreama di Bayes sta nel fatto che  se non si è in grado di determinare $$p(A|B)$$, si può   “girare attorno al problema”  provando a calcolare la probabilità $$p(B|A)$$ (per esempio a partire da frequenze ottenute dai dati sperimentali).

Questa formula è semplicissima  eppure funziona e, infatti, è usata (sempre di più) in ambiti diversissimi fra loro.

Vediamo il caso dello spam: devo considerare “il grado di spazzatura”  delle parole presenti nel testo. Scritto in linguaggio matematico questo diventa:

$$ p(spam | testo) = \frac{p(testo | spam) p(spam)}{ p(testo)}$$

E’ interessante notare che non siamo veramente interessati a conoscere la probabilità esatta ma solo se è più probabile che il messaggio sia di spazzatura o meno.

Possiamo quindi ignorare il denominatore, termine moltiplicativo costante, e concentrarci sul numeratore.

In particolare il termine determinante da ricavare  è $$p(testo | spam)$$. Per farlo possiamo utilizzare una quantità a nostro piacimento di email di cui è noto se appartengano o meno al gruppo “spazzatura” e analizzare le frequenze con cui compare un testo o, come vedremo, le frequenze delle parole contenute al suo interno (o almeno di un sottoinsieme di vocaboli significativo).

Un esempio e il metodo Naive

Partiamo  dalla seguente e-mail:

“Ciao marco,

ci vediamo domani“

In questo caso il testo della e-mail è formato da parole come “ciao”, “marco”, “vediamo”, “domani”. La probabilità $$p(spam|testo)$$  diventa , applicando la relazione di Bayes alle singole parole:

$$p(spam | ciao, marco, ci, vediamo, domani )\propto p( ciao, marco, ci, vediamo, domani | spam) p(spam)$$.

(vi ricordiamo che il simbolo $$\propto$$ significa “proporzionale”).

In realtà non abbiamo ancora risolto il problema. Il secondo termine non è   facile da stimare poiché si dovrebbe riuscire a misurare in qualche molto la probabilità che in un testo compaiano le parole “ciao”, “marco”, “vediamo”, “domani”, sapendo che il testo è un messaggio di spam.

Cosa si può fare quindi?

Per risolvere il problema si sceglie di fare una ulteriore semplificazione: si assume  che le singole parole siano indipendenti fra loro (cosa in generale falsa).

Questa approccio è chiamato    Naive Bayes (la parola naive che significa “ingenuo”, “semplice” richiama l’idea della assunzione grossolana).

Questa scelta può sembrare molto forte, nonostante questo non potete immaginare in quanti casi questo approccio naive funziona.

Vediamo come formalizzare nel linguaggio matematico l’assunzione dell’indipendenza delle singole parole. Visto che siamo in matematica generalizziamo il problema e indichiamo le singole parole con le lettere B,C,D.

Immaginiamo di voler trovare la probabilità di un evento A dati gli eventi B, C, D. In formule avremmo:

$$p(A| B,C,D)= \frac{p(B,C,D | A) p(A)}{ p(B,C,D)}$$

L’approccio Naive assume che $$p(B,C,D| A)= p(B| A)p(C| A)p(D|A)$$ ovvero che gli eventi B, C e D non si influenzino fra di loro.

Tornando al nostro esempio quindi si può scrivere:

$$p(spam | ciao, marco, ci, vediamo, domani, ) \propto p(ciao| spam)p(marco| spam)….p(domani | spam)$$.

I termini di destra della precedente equazione si ottengono partendo da una serie di e-mail riconosciute come spam dall’uomo. In base alle frequenze in cui compaiono le parole in questo dataset di riferimento, si ottengono le probabilità di una parola in una e-mail di spam ( $$p(parola | spam)$$) .

Moltiplicando fra loro le probabilità dei singoli fattori corrispondenti a ciascuna parola si otterrà la probabilità che il testo di una e-mail sia spam o no decidendo, per esempio, una soglia sul valore della probabilità al di sopra della quale classificare la e-mail come spam. [2]

Ai più curiosi suggeriamo di vedere la seguenti videolezioni su youtube.

La prima parla di filtri bayesiani. La seconda dell’approccio bayesiano che da molti è considerato un utile paradigma di ragionamento.

Mi scuso con gli esperti bayesiani visto che in questo post non ho approfondito   il significato e le ripercussioni del teorema di Bayes. Le trovate trattate, almeno in parte, in questo secondo video.

Parentesi didattica

Finalmente sembra che la probabilità si stia facendo breccia nel mondo della scuola. Le ultime edizioni di libri molto usati nei licei Italiani danno sempre più spazio a questo argomento (seguendo le Indicazioni Nazionali) e affrontano, finalmente, il teorema di Bayes (che in molto libri 10-15 anni fa non era neanche citato).

Da più parti si dice che la probabilità sia uno di quegli argomenti che possono offrire spunti di interessi per gli studenti. Parlare di Bayes e del filtro antispam (e magari associarci un po’ di esperimenti attraverso un linguaggio di programmazione) potrebbe secondo me appassionare gli studenti più delle formule di prostaferesi o dei radicali doppi.

Un esempio interessante è il seguente progetto “Bet on Math: scommetti sulla matematica” che ha come obiettivo  la sensibilizzazione sui problemi derivanti dal gioco d’azzardo utilizzando la probabilità (come si dice prendere due piccioni con una fava: spiega la probabilità e contribuisce a far capire la pericolosità del gioco d’azzardo in cui a vincere è sempre e solo chi organizza).

P.S. sulla irragionevole efficacia della matematica

Credo sia il caso osservare  che  in questo post, come in tanti altri su questo blog emerge  una delle caratteristiche che rendono “speciale” la matematica: i suoi strumenti possono essere applicati a campi diversissimi fra loro non appena si riesce ad “astrarre” il problema. In un altro articolo, per esempio,  Andrea ha mostrato, per esempio, come sempre l’approccio bayesiano sia usato per studiare la “sentiment analisys” ovvero il gradimento o meno espresso da  utente (per esempio sui social network) rispetto, per esempio, a una azienda.

Si conferma quindi l’irragionevole efficacia della matematica.

Per approfondire

– Interessante materiale del Dipartimento di Informatica ed Applicazioni dell’università di Salerno

– Dispense sui classificatori Naive Bayes

– A plan for Spam  articolo del 2002 contenente alcuni spunti iniziali da cui sono nati alcuni progetti di implementazione filtri bayesiani

– Il progetto SpamBayes scritto con il linguaggio python

NOTE 

[1] M. Sahami, S. Dumais, D. Heckerman, E. Horvitz (1998). “A Bayesian approach to filtering junk e-mail” AAAI’98 Workshop on Learning for Text Categorization.

[2] Per completezza facciamo notare che con il tempo si sono introdotti algoritmi  più complessi o che non usano il metodo bayesiano. E’ inoltre importante osservare che nella realizzazione dell’algoritmo per renderlo più veloce si ignorano le parole comuni senza significato particolare come articoli o congiunzioni e si inseriscono anche termini non presenti nel vocabolario ma scritte apposta dagli spammer leggermente modificate come, tanto per fare esempio cretino, c422o 🙂

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.