Logica di un algoritmo di autocorrezione

In questo post vedremo gli step essenziali per sviluppare un semplice modello di autocorrezione. Non mi soffermerò sull'implementazione, ma sulla logica e sulle particolarità di modelli del genere.

Vediamo modelli di autocorrezione soprattutto nei nostri smartphone, mentre scriviamo su Whatsapp, Facebook Messenger o altre applicazioni di messaggistica. Essi pervadono la nostra quotidianità, ma come ogni tecnologia che lavora "dietro le quinte", tendiamo a prendere consapevolezza della sua esistenza solo quando quest'ultime sbagliano e ci trasmettono frustrazione e ansia nell'utilizzo. Accade spesso infatti che il nostro autocorrettore venga accusato di aver predetto erroneamente la nostra intenzione.

Oltre al funzionamento, vedremo come mai modelli del genere racchiudano difficoltà importanti che spiegano il motivo dei loro errori.

Step 1: Identificare la parola scritta male

Una parola viene identificata come typo se quest'ultima non è presente nel vocabolario del software. Il vocabolario ha la forma di un insieme con elementi unici.

Step 2: Trovare stringhe che sono distanti n modifiche

n sta per il numero di caratteri da modificare per trasformare la stringa osservata in una stringa target. La stringa osservata, nel nostro caso, è il typo, mentre la stringa target è il potenziale candidato per il suggerimento. Ci sono quattro tipi di manipolazioni che modificano la nostra stringa in un potenziale suggerimento sensato:

  • Inserimento (aggiungo una lettera): "cia" --> "ciao"
  • Rimozione (rimuovo una lettera): "ciaop" --> "ciao"
  • Scambio (scambio una lettera con un'altra): "caio" --> "ciao"
  • Sostituzione (aggiungo una lettera alla posizione k, rimuovendo la lettera originaria alla posizione k): "ciso" --> "ciao"

Com'è possibile notare, ognuna di queste manipolazioni trasforma una stringa errata in una stringa di senso compiuto. Ovviamente il computer non ha idea di quale sia una parola si senso compiuto o meno, quindi vengono generati m elementi per ognuna delle manipolazioni nell'esempio. Questo crea una lista molto lunga di potenziali candidati che devono essere quindi filtrati per rimuovere le parole senza senso.

Step 3: Filtrare i candidati

Usando lo step 1, troviamo l'intersezione tra il nostro vocabolario di termini e le stringhe manipolate nello step 2. Questo ci assicura che tutti le stringhe siano di senso compiuto.

Step 4: Calcolare le probabilità per i suggerimenti

L'ultimo step è quello di selezionare il candidato che ha la probabilità più alta di occorrere in quel determinato contesto. Questo è il modo in cui un modello "base" di autocorrect sa fornire un suggerimento valido per il nostro errore.

La formula matematica per calcolare le probabilità che una parola possa occorrere nel nostro corpus è la seguente

$P(parola) = \frac{C(parola)}{V}$

‍

la probabilità P che una parola appaia nel corpus è uguale a quante volte vediamo quella parola nel nostro vocabolario fratto la lunghezza del nostro vocabolario V. Prendiamo l'esempio seguente

Parola Conteggio
Io 10
sono 7
bravo 1
con 4
Python 2
e 6
R 1

‍

Ponendo che il nostro corpus è formato da 165 termini, vediamo come la parola Python abbia una probabilità di occorrere di $\frac{2}{165} = 0.012$.

Abbiamo ora disponibile una distribuzione di probabilità delle parole nel nostro corpus. Il nostro sistema di autocorrect andrà quindi a selezionare il candidato che ha la probabilità di capitare nel nostro corpus più alta. Molto semplice.

Conclusione

Abbiamo visto la logica e come implementare un semplice algoritmo di autocorrezione. Questo modello mentale può fungere da base per creare modelli più complessi, che non si basano semplicemente sulla probabilità di occorrenza dei termini, ma anche sul contesto e sul dizionario che ha manualmente creato l'utente attraverso le varie correzioni da lui inserite durante la scrittura.

Andrea D'Agostino
Ciao, sono Andrea D'Agostino e sono un data scientist con 6 anni di esperienza nel campo della business intelligence. Applico tecniche statistiche e di machine learning per aiutare i clienti a trovare e risolvere problemi nei loro asset digitali e a sfruttare le debolezze dei competitor a loro vantaggio.

Sono il fondatore e l'autore di questo blog, il cui obiettivo è raccogliere le informazioni più importanti che ho imparato durante il mio percorso lavorativo e accademico al fine di poter aiutare il lettore a migliorare le sue analisi.