Quali sono le catene di Markov? 5 usi del mondo reale Nifty

Potresti aver sentito il termine “Catena di Markov” prima, ma a meno che non abbiate preso alcune lezioni sulla teoria della probabilità o sugli algoritmi informatici Come imparare la programmazione senza tutti gli stress Come imparare la programmazione senza tutti gli stress Forse avete deciso di perseguire la programmazione, sia per una carriera o semplicemente un hobby. Grande! Ma forse stai iniziando a sentirti sopraffatto. Non così eccezionale. Ecco l'aiuto per facilitare il tuo viaggio. Per saperne di più, probabilmente non sai cosa sono, come funzionano e perché sono così importanti.

La nozione di catena di Markov è un “sotto il cappuccio” concetto, nel senso che non hai davvero bisogno di sapere cosa sono per trarne beneficio. Tuttavia, puoi sicuramente trarre vantaggio dalla comprensione di come funzionano. Sono semplici ma utili in tanti modi.

Quindi, ecco un corso accelerato: tutto ciò che devi sapere sulle catene di Markov è condensato in un unico articolo digeribile. Se vuoi approfondire ancora di più, prova il corso di teoria dell'informazione gratuito su Khan Academy (e considera anche altri siti di corsi online 8 Siti Web incredibili per frequentare corsi gratuiti per gli studenti online 8 siti Web incredibili per frequentare corsi gratuiti online per studenti Leggi di più).

Catene di Markov 101

Diciamo che vuoi pronosticare come sarà il tempo domani. Una vera previsione - il tipo eseguito da esperti meteorologi Le 7 migliori app gratuite per le previsioni meteo per Android Le 7 migliori app gratuite per le previsioni meteo per Android Queste app meteo gratuite ti aiuteranno a rimanere aggiornato sulle condizioni meteo con il tuo dispositivo Android. Leggi di più - comporterebbe centinaia, o anche migliaia, di variabili diverse che cambiano continuamente. I sistemi meteorologici sono incredibilmente complessi e impossibili da modellare, almeno per i laici come te e me. Ma possiamo semplificare il problema utilizzando stime di probabilità.

Immagina di avere accesso a trent'anni di dati meteorologici. Cominci dall'inizio, notando che il primo giorno era soleggiato. Continui ad andare avanti, notando che il Day 2 era anche soleggiato, ma il Day 3 era nuvoloso, quindi il Day 4 era piovoso, il che ha portato a un temporale il 5 ° giorno, seguito da un cielo sereno e sereno il 6 ° giorno.

Idealmente saresti più granulare, optando per un'analisi ora per ora invece di un'analisi giornaliera, ma questo è solo un esempio per illustrare il concetto, quindi portami con me!

Lo fai sull'intero set di dati di 30 anni (che sarebbe solo di circa 11.000 giorni) e calcola le probabilità di come sarà il tempo di domani in base alle condizioni meteorologiche odierne. Ad esempio, se oggi è soleggiato, allora:

• Una possibilità del 50% che domani ci sia di nuovo il sole.
• Una probabilità del 30% che domani sia nuvoloso.
• Una probabilità del 20% che domani sarà piovoso.

Ora ripeti questo per ogni condizione meteo possibile. Se oggi è nuvoloso, quali sono le possibilità che domani ci saranno sole, pioggia, nebbia, temporali, grandinate, tornado, ecc.? Molto presto, hai un intero sistema di probabilità che puoi utilizzare per prevedere non solo il tempo di domani, ma il giorno successivo e il giorno successivo.

Stati di transizione

Questa è l'essenza di una catena di Markov. Si hanno singoli stati (in questo caso, condizioni climatiche) in cui ogni stato può transitare in altri stati (ad esempio i giorni di sole possono transitare in giorni nuvolosi) e tali transizioni si basano sulle probabilità. Se vuoi prevedere come potrebbe essere il tempo in una settimana, puoi esplorare le varie probabilità nei prossimi sette giorni e vedere quali sono più probabili. Quindi, un Markov “catena”.

Chi è Markov? Era un matematico russo che ha avuto l'idea di uno stato che porta direttamente a un altro stato in base a una certa probabilità, in cui nessun altro fattore influenza la possibilità di transizione. Fondamentalmente, ha inventato la catena Markov, da cui la denominazione.

Come le catene di Markov sono usate nel mondo reale

Con la spiegazione fuori mano, esploriamo alcune delle applicazioni del mondo reale in cui sono utili. Potresti essere sorpreso di scoprire che hai fatto uso delle catene di Markov per tutto questo tempo senza saperlo!

Nome Generazione

Hai mai partecipato a giochi da tavolo, giochi MMORPG o persino alla scrittura di fiction? Potresti aver tormentato il nome dei tuoi personaggi (almeno in un punto o un altro) - e quando non riesci a pensare a un nome che ti piace, probabilmente hai fatto ricorso a un generatore di nomi online Crea un nuovo alias con I migliori generatori di nomi online [Weird & Wonderful Web] Crea un nuovo alias con i migliori generatori di nomi online [Weird & Wonderful Web] Il tuo nome è noioso. Per fortuna, puoi andare online e scegliere un nuovo alias usando uno degli innumerevoli generatori di nomi disponibili su Internetz. Leggi di più .

Ti sei mai chiesto come funzionavano quei generatori di nomi? A quanto pare, molti di loro usano catene Markov, rendendola una delle soluzioni più utilizzate. (Esistono altri algoritmi che sono altrettanto efficaci, ovviamente!)

Tutto ciò che serve è una raccolta di lettere in cui ogni lettera ha un elenco di potenziali lettere di follow-up con probabilità. Quindi, per esempio, la lettera “M” ha una probabilità del 60% di portare alla lettera “UN” e una probabilità del 40% di portare alla lettera “io”. Fallo per un sacco di altre lettere, quindi esegui l'algoritmo. Boom, hai un nome che ha senso! (Il più delle volte, comunque.)

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 atterra su 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 ei collegamenti tra le pagine Web sono transizioni con probabilità. Questo teorema sostanzialmente lo dice non importa quale pagina web inizi, la tua possibilità di atterrare su una determinata pagina web X è una probabilità fissa, assumendo a “a lungo” di surf.

E questa è la base di come Google classifica le pagine web. In effetti, l'algoritmo PageRank è una forma modificata (leggi: più avanzata) dell'algoritmo della catena Markov.

Più alto è il “probabilità fissa” di arrivare a una certa pagina web, più alto è 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. Interessante, non è vero??

Predizione di battitura a parola

I telefoni cellulari hanno avuto una digitazione predittiva ormai da decenni, ma puoi indovinare come vengono fatte queste previsioni? Se utilizzi Android (opzioni tastiera alternative Qual è la migliore tastiera alternativa per Android? Qual è la migliore tastiera alternativa per Android? Diamo un'occhiata ad alcune delle migliori tastiere nel Play Store e le mettiamo alla prova. Altro) o iOS (opzioni di tastiera alternative 9 Tastiere iOS alternative per rendere la tua digitazione più semplice o più divertente 9 Tastiere iOS alternative per rendere la tua digitazione più semplice o più divertente Quando Apple ha smesso di comportarsi come un genitore iperprotettivo e ha introdotto tastiere di terze parti, tutti sono andati tastiera-pazzo.Per saperne di più), c'è una buona probabilità che la tua app di scelta usi catene di Markov.

Questo è il motivo per cui le app di tastiera chiedono se riescono a raccogliere dati sulle abitudini di digitazione. Ad esempio, in Google Keyboard, viene richiamata un'impostazione Condividi frammenti che chiede “Condividi 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.

Simulazione sottotitoli

Se non hai mai usato Reddit, ti invitiamo a dare un'occhiata a questo affascinante esperimento chiamato / r / SubredditSimulator.

In poche parole, Subreddit Simulator raccoglie tutti i commenti e titoli realizzati nelle numerose comunità di Reddit, quindi analizza il trucco parola per parola di ogni frase. Usando questi dati, genera probabilità da parola a parola, quindi usa quelle probabilità per generare titoli e commenti da zero.

Uno strato interessante di questo esperimento è che i commenti e i titoli sono categorizzati dalla comunità da cui provengono i dati, quindi i tipi di commenti e titoli generati dal set di dati di / r / food sono molto diversi dai commenti e titoli generati da / r / set di dati del calcio.

E la parte più divertente - o forse la più inquietante - di tutto ciò è che i commenti e i titoli generati possono essere spesso indistinguibili da quelli fatti da persone reali. È assolutamente affascinante.

Conoscete altri usi interessanti per le catene Markov? Hai domande che necessitano ancora di risposta? Fateci sapere in un commento in basso!

Scopri di più su: Algoritmi.