I testi generati ovvero le catene di Markov

Per chi non mi conoscesse, sono /u/timendum , il creatore di /u/italy_SS , cioè il /r/SubredditSimulator per i contenuti in Italiano.

In questo articolo cercherò di spiegarvi il meccanismo dietro la generazione di testi casuali usati in questi due subreddit.

Cosa sono le catene di Markov

Le catene di Markov sono un concetto di matematica/probabilità; non starò qui a fare enunciazioni formali, tranquilli, cerchiamo solo di capire il concetto.

Un catena di Markov è una situazione il cui futuro dipende solo dallo stato attuale, cioè se so cosa sta succedendo adesso, sono in grado di determinare la probabilità di quello che succederà in futuro.

L’esempio che preferisco è il Gioco dell’Oca: sapendo solo che sei alla casella X, ad esempio 20, possiamo calcolare la probabilità della tua prossima posizione: per 1/12 sarai alla 22, per 2/12 alla 23 e così in avanti; chiaramente dovremmo tenere conto delle caselle speciali, quelle che mandano avanti o indietro, rendendo quindi il modello interessante.

Il termine più generico sarebbe processo di Markov, si usa catene quando il numero degli stati non è infinito.

Nell’informatica

Nella pratica come vogliamo rappresentare una catena di Markov nel nostro codice?

La scelta più semplice è un \”array associativo\”, quindi una Map (es: Java o Rust) o un dictionary (es: Python) o un Object (es: Javascript).

La chiave sarà lo stato attuale, come valore abbiamo un elenco di elementi {probabilità, prossimo stato}.

Ad esempio possiamo rappresentare così una catena: stato: [(%, prossimo), ...] dove:

stato è lo stato attuale, ad esempio il numero della casella nel gioco dell’oca
seguono quindi un elenco di possibili stati futuri [futuro1, futuro2, futuro3, ...] definiti come (%, prossimo)
% è la probabilità assoluta che questo caso si verifichi: ad esempio 1/12, quindi lo 8,3333%
prossimo prossimo è il prossimo stato che si verificherà con la probabilità appena elencata, ad esempio la casella 21.

I testi generati

La scrittura, semplificando abbastanza, si presta abbastanza bene ad essere modellata da una catena di Markov:
la prossima parola che scrivo sarà fortemente legata all’ultima che ho scritto.

Quello che possiamo fare è cercare un corpus, cioè un testo abbastanza grande da prendere come sorgente e modellare una catena di Markov.

Per fare un esempio ho preso il secondo paragrafo del precedente articolo su tl;dr

> Sappiamo che le password devono essere lunghe, devono essere complesse e solo una di queste due proprietà non basta: avere la stessa password per ogni sito web, sappiamo, non è cosa giusta. Tutte queste accortezze per cosa? Per non farsi rubare le password ovviamente: ma se volessi provarci?

Ecco come risulterà il nostro modello, nella forma esemplificata sopra, di parola: [(%, prossima), ...]:

sappiamo: [(100%; che)]
che: [(100%, le)]
le: [(100%, password)]
password: [(33%, devono), (33%, per), (33%, ovviamente)]
…
per: [(33%, ogni), (33%, cosa), (33%, non)]
cosa: [(50%, giusta), (50%, per)]
…
essere: [(50%, lunghe), (50%, complesse)]
queste: [(50%, due), (50%, accortezze)]
eccetera…

Fatto questo possiamo generare un testo casuale partendo dal modello.

Prendiamo la parola di partenza, nel nostro modella abbiamo solo sappiamo
Da sappiamo, il prossimo passo forzato è che
Da che, c’è solo le
Da le, c’è solo password
Per password abbiamo più possibilità, \”tiro il dado\” ed estraggo per
Anche da per ci sono più parole, ognuna con 1/3 di probabilità, estraggo casualmente cosa
Da cosa estraggo giusta
E così in avanti..

Risultato:

> Sappiamo che le password per cosa giusta. Tutte queste due proprietà non farsi rubare le password devono essere complesse e solo una di queste accortezze per cosa?

E da qui?

Ci sono ancora moltissime cose da considerare:

prima di tutto non abbiamo deciso come spezzare una frase dall’altra
ci servirebbero anche due “parole” speciali per segnare l’inizio e il termine della frase
dovrebbero decidere se fare un confronto tra parole case sensitive o meno
dovremmo decidere se includere eventuali segni di punteggiatura (virgola, punti di domanda, etc) nel nostro modello o meno
vorremmo scartare frasi troppo simili al testo originale (e come misuriamo quanto simili?)

L’autore originale, /u/Deimorz , ed io abbiamo usato il python e la libreria markovify.

Partire è facilissimo e, se parti con un testo abbastanza grande, i risultati sono già apprezzabili, se ovviamente vi piace il nonsense.

(grazie a /u/cancrena)

Scritto da u/timendum

Link ai commenti