colorful carousel placed in amusement park

Le magiche catene di Markov

blur chains chrome close up
Photo by Pixabay on Pexels.com

Quasi tutti gli algoritmi di database a grafo possono far risalire le loro basi matematiche a un costrutto chiamato Markov Chains.

Comprendere le catene di Markov

Immagina di esplorare una nuova città. Esci dalla stazione dei treni con negozi su ogni lato e il tuo hotel in lontananza. Una volta che lasci la stazione dei treni la probabilità di tornarci è davvero bassa diremo il 2% rispetto alla probabilità di recarti in uno degli altri negozi.
Hai la possibilità di entrare in ogni negozio e, una volta entrato nel negozio, hai la possibilità di andare in un altro negozio adiacente. Sai anche che se entri in hotel, probabilmente rimarrai lì per la sera, ma c’è una probabilità del 20% che tu vada in uno dei 2 negozi circostanti (es: potresti rimanere per può decidere di tornare a fare acquisti).

Possiamo usare una catena di Markov per generare TUTTI i possibili percorsi diversi che potremmo attraversare per la città. Tutto quello che dobbiamo sapere ad ogni passo del percorso è da dove veniamo (la piazza del paese) e la probabilità che andremo in una certa direzione (cioè: all’hotel o alla piazza).

Possiamo rappresentarli come una matrice che mostra la probabilità che andremo da un posto all’altro.

PARTENZA

STAZIONEPIAZZANEGOZIOHOTELCAFENEGOZIO 2
STAZIONE00.20000.2
PIAZZA0.500.5000
ARRIVONEGOZIO00.9800.100
HOTEL000.50.80.50
CAFE0000.100.98
NEGOZIO 20.50000.50

Le catene di Markov sono una forma di macchina a stati finiti, con ogni stato rappresentato come un vertice e la probabilità che avvenga una transizione rappresentata come un bordo (questa è anche chiamata “probabilità di transizione” nel linguaggio matematico del grafico).

Ovviamente, le catene Markov non servono solo per modellare i tuoi viaggi. Trovano applicazione in molti campi diversi della scienza e dell’ingegneria, dal fare previsioni su vasta scala di modelli climatici a fare previsioni sul mercato azionario. Una delle caratteristiche più interessanti delle catene di Markov è che sono parallelizzabili, il che significa che puoi calcolare la probabilità che si verifichi una transizione tra due stati indipendentemente da ciò che è accaduto prima di quello stato e puoi calcolare molti di questi stati in parallelo. Pertanto, è possibile calcolare più collegamenti su più macchine contemporaneamente e quindi riunirli rapidamente.

Come le catene di Markov sono usate nel mondo reale

Google PageRank

Una delle implicazioni interessanti della teoria della catena di Markov è che con l’aumentare della lunghezza della catena (cioè il numero di transizioni di stato aumenta), la probabilità che si abbia un certo stato converge su un numero fisso, e questa probabilità è indipendente da dove si inizia nel sistema.

Ciò è estremamente interessante quando si pensa all’intero world wide web come a un sistema Markov in cui ogni pagina web è uno stato e i collegamenti tra le pagine Web sono transizioni con probabilità. Questo teorema dice fondamentalmente che non importa quale pagina web si inizia, la possibilità di atterrare su una determinata pagina Web X è una probabilità fissa, assumendo un “lungo tempo” di navigazione .

E questa è la base di come Google classifica le pagine web. In effetti, l’algoritmo PageRank è una forma modificata dell’algoritmo della catena Markov.

Maggiore è la “probabilità fissa” di arrivare a una determinata pagina Web, maggiore è il suo PageRank. Questo perché una probabilità fissa più alta implica che la pagina abbia molti link in entrata da altre pagine web e Google presume che se una pagina web ha molti link in entrata, allora deve essere preziosa. Più link in entrata, più è prezioso.

È più complicato di così, certo, ma ha senso. Perché un sito come About.com ha una priorità più alta nelle pagine dei risultati di ricerca? Perché risulta che gli utenti tendono ad arrivare lì mentre navigano sul web.

Predizione di battitura a parola

I telefoni cellulari hanno avuto una digitazione predittiva ormai da decenni, ma puoi indovinare come vengono fatte queste previsioni? Ad esempio, in Google Keyboard, c’è un’impostazione chiamata snippet di condivisione che chiede di “condividere frammenti di cosa e come digiti nelle app di Google per migliorare Google Keyboard”. In sostanza, le tue parole sono analizzate e incorporate nelle probabilità della catena di Markov dell’app.

Questo è anche il motivo per cui le app di tastiera spesso presentano tre o più opzioni, in genere nell’ordine del più probabile o meno probabile.

Non può sapere con certezza cosa volevi digitare dopo, ma è corretto il più delle volte.

chevron_left
chevron_right
%d blogger hanno fatto clic su Mi Piace per questo: