{"id":37,"date":"2001-10-10T00:00:00","date_gmt":"2001-10-09T22:00:00","guid":{"rendered":""},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T22:00:00","slug":"37","status":"publish","type":"post","link":"https:\/\/www.vialattea.net\/content\/37\/","title":{"rendered":"Che cosa sono i processi di Markov e qual \u00e8 il loro impiego nella cibernetica?"},"content":{"rendered":"

I processi Markoviani sono processi stocastici che
\nmodellano situazioni in cui la transizione tra stati non \u00e8
\ndeterministica, ma probabilistica, ed \u00e8 caratterizzata dal fatto che la
\nprobabilit\u00e0 di transire in uno stato successivo dipende esclusivamente
\ndallo stato attuale.<\/p>\n

Ad esempio, siano
\nAntonio e Biagio due giocatori che decidano di giocare con una moneta
\nparticolare, la cui probabilit\u00e0 che esca testa siano p<\/i> e croce 1-p<\/i>.<\/p>\n

E siano a<\/i> e b<\/i> il capitale iniziale di Antonio e di Biagio rispettivamente.<\/p>\n

Vogliamo modellare il processo di variazione del capitale di uno dei due giocatori, diciamo A, che pu\u00f2 variare tra 0<\/i> (caso in cui perde) ad a+b<\/i> (caso in cui vince).<\/p>\n

La situazione \u00e8 descritta dal grafo di figura 1.<\/p>\n

\n
\n
\n \"\"\/<\/span>
\n
\n
\n \u00a0
\n
\n <\/p>\n

Fig 1: Un processo Markoviano<\/span><\/p>\n


\n
\n \u00a0
\n
\n <\/span><\/p>\n

Il capitale del giocatore A varia dal valore iniziale a<\/i> a 0<\/i> o a+b<\/i> a passi di 1<\/i>, incrementando \u2013 con probabilit\u00e0 p<\/i> \u2013 o decrementando, con probabilit\u00e0 q=1-p<\/i>.<\/p>\n

Le probabilit\u00e0 di incrementare\/decrementare il capitale non sono dipendenti dal numero n <\/i>di giocate.<\/p>\n

In generale, i processi Markoviani sono caratterizzati dalle propriet\u00e0 che seguono:<\/p>\n

\n
\n \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span><\/span>
\n
\n Rappresentano transizioni tra stati che avvengono in modo probabilistico.<\/p>\n

\n
\n \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span><\/span>
\n
\n Le probabilit\u00e0 di transizione non dipendono dal numero di transizioni effettuate (propriet\u00e0 di omogeneit\u00e0<\/i>).<\/p>\n

\n
\n \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span><\/span>
\n
\n Le probabilit\u00e0 di transizione dipendono unicamente dallo stato attuale (propriet\u00e0 memoryless<\/i>, o di assenza di memoria).<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

Gli oggetti matematici che descrivono i processi Markoviani sono detti Catene di Markov<\/i>.<\/p>\n

Inizialmente,
\nle catene di Markov sono state utilizzate per prevedere configurazioni
\ntendenziali di processi Markoviani, come ad esempio l’equilibrio di un
\necosistema. Nell’esempio di figura 1 \u00e8 possibile prevedere la
\nconfigurazione tendenziale della distribuzione di capitale tra i due
\ngiocatori.<\/p>\n

In una catena di Markov ad N<\/i> stati, ove Xn<\/sub> <\/i>sia la variabile aleatoria che descrive lo stato al passo n<\/i>-mo, <\/i>\u00e8 possibile definire un vettore di distribuzione di probabilit\u00e0 <\/i>di appartenenza agli stati dopo n<\/i> transizioni della catena <\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n


\n
\n
\n \"\"\/
\n
\n <\/sub>
\n
\n \u00a0\u00a0 <\/span><\/p>\n

ove\u00a0\u00a0 <\/span><\/p>\n


\n
\n
\n \"\"\/
\n
\n <\/sub>
\n
\n <\/i><\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

\u00e8 la probabilit\u00e0 di trovarsi al passo n<\/i> nello stato i<\/i>.<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

Nell’esempio di figura 1, la configurazione iniziale in cui il capitale di A \u00e8 a<\/i>, viene descritta dal vettore delle condizioni inziali v = (0, …, 1, …, 0)<\/i> con un solo 1<\/i> in corrispondenza della componente a<\/i>-esima, questo vettore \u00e8 detto distribuzione iniziale<\/i>.<\/p>\n

Per sapere qual \u00e8 la probabilit\u00e0 che A abbia un capitale di c <\/i>dopo m <\/i>giocate \u00e8 sufficiente calcolare il vettore di distribuzione di probabilit\u00e0 v<\/u><\/i> al passo m <\/i>
\n
\n
\n \"\"\/
\n
\n <\/sub>
\n
\n e selezionare la componente
\n
\n
\n \"\"\/
\n
\n <\/sub>
\n
\n .<\/p>\n

Nella
\nteoria delle Catene di Markov (CdM), che investiga le propriet\u00e0 delle
\ncatene come successioni di variabili aleatorie, vengono forniti gli
\nstrumenti di calcolo, presentati nel seguito di questo articolo, del
\nvettore di distribuzione di probabilit\u00e0, detto misura <\/i>della CdM.<\/p>\n

Esistono
\ndelle misure che, applicate alla CdM, restituiscono s\u00e9 stesse, ovvero
\nesistono delle distribuzioni di probabilit\u00e0 che non vengono modificate
\ndall’applicazione delle transizioni. Queste misure sono dette invarianti<\/i>.<\/p>\n

Il teorema di Markov<\/i> postula un fatto importante:<\/p>\n

\n
\n \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span><\/span>
\n
\n se Xn<\/sub><\/i>
\n\u00e8 una CdM a stati finiti e le probabilit\u00e0 di transizione godono di
\nalcune propriet\u00e0 di regolarit\u00e0, allora la CdM ammette una sola misura invariante<\/i> e tende ad uno stato stazionario.<\/p>\n

L’implicazione
\ndel teorema \u00e8 di vasta portata: le CdM che soddisfano le ipotesi di
\nMarkov tendono ad uno stato stazionario, ovvero la distribuzione
\nprobabilit\u00e0 di converge e convergono ad un valore finito p<\/span><\/span>i<\/sub><\/i> tutte le probabilit\u00e0 Pij <\/i>di transire da uno stato i<\/i> ad uno j<\/i>:<\/p>\n


\n
\n
\n \"\"\/
\n
\n <\/sub>
\n \n <\/p>\n

\n
\nE’ proprio questa propriet\u00e0 di convergenza delle CdM che le rende
\nappetibili per l’intelligenza artificiale, in generale per tutti i
\nprocessi di riconoscimento.<\/p>\n

Una
\nvolta verificato che il problema specifico \u00e8 modellabile con un
\nprocesso Markoviano (che soddisfi le ipotesi del teorema di Markov) \u00e8
\npossibile, infatti, costruire una CdM che converga in modo appropriato.<\/p>\n

Un
\ntipico esempio \u00e8 il problema del riconoscimento della scrittura, in cui
\nle lettere vengono disposte in una matrice di punti che viene \u201cridotta\u201d
\na quella della lettera corrispondente. Ad esempio, le lettere
\nillustrate in figura 2 sono tutte corrispondenti alla A.<\/p>\n

\n
\n \u00a0
\n
\n
\n
\n \n <\/p>\n\n\n\n\n

<\/td>\n<\/tr>\n

<\/td>\n
\n
\n
\n <\/p>\n\n\n\n
<\/p>\n
\n

\n
\n
\n \"\"\/
\n \n <\/p>\n<\/p><\/div>\n

<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

<\/span>
\n
\n
\n \u00a0
\n
\n
\n <\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

<\/p>\n

\u00a0<\/p>\n

<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

\n
\n Fig. 2: Scritture equivalenti del carattere \u2018A’ maiuscolo<\/span><\/p>\n

<\/span><\/p>\n


\n <\/span><\/p>\n

Nel
\nprocesso di riconoscimento la scrittura umana viene mappata in un
\nvettore di probabilit\u00e0 iniziali. Una lettera viene riconosciuta quando
\nla CdM converge ad uno stato che rappresenta un carattere. <\/p>\n

Il
\nprocesso di convergenza pu\u00f2 essere modificato assegnando le probabilit\u00e0
\ndi transizione tra gli stati intermedi mediante un processo, detto training<\/i> della CdM, in cui si modificano le probabilit\u00e0 di transizione in modo tale da forzare la convergenza al carattere giusto.<\/p>\n

Procedimenti analoghi possono essere utilizzati per il riconoscimento di voci, immagini, testi.<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

Il
\nseguito di questo articolo espone i risultati essenziali della teoria
\nsulle Catene di Markov e presuppone un livello di conoscenza di
\nmatematica del primo anno di universit\u00e0 per le facolt\u00e0
\ntecnico-scientifiche, e delle basi di Calcolo delle Probabilit\u00e0 e
\nStatistica.<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

Definizione \u2013 Catena di Markov<\/b><\/p>\n

Si definisce Catena di Markov <\/i>(CdM) una successione {XN <\/sub>}<\/i>di variabili aleatorie (v.a.) discrete in E<\/i>\u00cc<\/span><\/span>N<\/i>, ove N <\/i>\u00e8 l’insieme dei numeri naturali ed E <\/i>\u00e8 detto spazio degli stati<\/i> contenente tutti i possibili valori di XN<\/sub><\/i>, per cui valga la propriet\u00e0 di Markov di omogeneit\u00e0<\/i>:<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

P(XM+1 <\/sub>= j | XM <\/sub>= iM<\/sub>, …, X1 <\/sub>= i1<\/sub>, X0 <\/sub>= i0<\/sub>) = P(XM+1 <\/sub>= j | XM <\/sub>= iM<\/sub>) = Pi,j<\/sub><\/i><\/p>\n


\n
\n \u00a0
\n
\n <\/sub><\/i><\/p>\n

in cui la probabilit\u00e0 di transizione<\/i> Pij<\/sub><\/i> dallo stato i <\/i>allo stato j<\/i> in un passo non dipende da M<\/i>.<\/p>\n

Ad esempio, la CdM di figura 1 ha come spazio degli stati E = {1, …, a+b <\/sub>}<\/i> (N=a+b<\/i>).<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

Definizione \u2013 Probabilit\u00e0 di transizione in k passi<\/b><\/p>\n


\n
\n \u00a0
\n
\n <\/b><\/p>\n

Pi,j<\/sub> (k)<\/sup> = P(XM+k <\/sub>= j | XM <\/sub>= i)<\/i><\/p>\n


\n
\n \u00a0
\n
\n <\/i><\/p>\n

\u00e8 la probabilit\u00e0 di transire dallo stato i<\/i> allo stato j<\/i> in k<\/i> passi.<\/p>\n


\n
\n \u00a0
\n
\n <\/b><\/p>\n


\n
\n \u00a0
\n
\n <\/b><\/p>\n

Definizione \u2013 Legge, distribuzione o misura di XN<\/sub><\/b><\/p>\n

La legge <\/i>o distribuzione <\/i>o misura <\/i>di XN<\/sub><\/i>\u00a0 <\/span><\/sub>\u00e8 data dal vettore<\/p>\n


\n
\n
\n \"\"\/
\n
\n <\/sub>
\n
\n \u00a0\u00a0 <\/span><\/p>\n

ove\u00a0\u00a0 <\/span><\/p>\n


\n
\n
\n \"\"\/
\n
\n <\/sub>
\n
\n \u00a0<\/span>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span><\/i>[1]<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

\u00e8 la probabilit\u00e0 di trovarsi al passo n<\/i> nello stato i<\/i>.<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

Calcoliamo la [1] applicando la formula delle probabilit\u00e0 totali (
\n
\n
\n \"\"\/
\n
\n <\/sub>
\n
\n , ove Ak<\/sub><\/i> \u00e8 una partizione dell’universo degli eventi W<\/span><\/span><\/i>
\n
\n
\n \"\"\/
\n
\n <\/sub>
\n
\n ) utilizzando come partizione il valore della v.a. al passo iniziale X0<\/sub>=k, <\/i>per ogni k<\/i>\u00ce<\/span><\/span>E<\/i>:<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n


\n
\n
\n \"\"\/
\n
\n <\/sub>
\n
\n \u00a0<\/span>[2]<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

se definiamo la matrice<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n


\n
\n
\n \"\"\/
\n
\n <\/sub>
\n
\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span>[3]<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

delle probabilit\u00e0 di transizione tra tutti gli stati di E <\/i>in m <\/i>passi, allora l’ultimo termine della [2] diventa l’espressione del prodotto scalare tra il vettore delle condizioni inziali v<\/u><\/i> al passo 0<\/i> e la matrice P(m)<\/sub><\/i> definita in [3].<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

Ci\u00f2 significa che la misura v(<\/sup><\/u>m)<\/sup><\/i> al passo m<\/i> \u00e8 data dal prodotto scalare:<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

v<\/span><\/u><\/i>(m) <\/span><\/sup><\/i>= v<\/u>(0) <\/sup>P(m)<\/sub> <\/span><\/i>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span>[4]<\/span><\/p>\n


\n
\n \u00a0
\n
\n <\/span><\/p>\n

Nel definire una CdM, occorre quindi esplicitare anche questi due termini:<\/p>\n

\n
\n 1.\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span>
\n
\n La matrice P=P(1)<\/sub>=<\/i> Pij<\/sub><\/i> delle probabilit\u00e0 di transizione tra gli stati i <\/i>e j <\/i>in E<\/i>.<\/p>\n

\n
\n 2.\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span>
\n
\n La misura iniziale v<\/u>(0)<\/sup><\/i><\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

Teorema<\/b><\/p>\n

P(m)<\/sub>=Pm<\/sup><\/i><\/p>\n


\n
\n \u00a0
\n
\n <\/sup><\/i><\/p>\n

Questo teorema consente di calcolare la misura di una CdM al passo m<\/i> :<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

v<\/span><\/u><\/i>(m) <\/span><\/sup><\/i>= v<\/u>(0) <\/sup>Pm<\/sup>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span><\/span><\/i>[5]<\/span><\/p>\n


\n
\n \u00a0
\n
\n <\/span><\/p>\n

\n
\n
\n \"\"\/<\/span>
\n
\n Esempio 2<\/b><\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

Sia la CdM di Fig. 3, con E={1,2,3} (N=3)<\/i> e:<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n


\n
\n
\n \"\"\/
\n
\n <\/sub>
\n
\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span>;\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span>v(<\/sup><\/u>0)<\/sup>=(1\/3, 1\/3, 1\/3)<\/i><\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

la legge di X2<\/sub> <\/i>\u00e8 <\/p>\n

Fig. 3 Una CdM a 3 stati<\/span><\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

v<\/span><\/u><\/i>(2) <\/span><\/sup><\/i>= v<\/u>(0) <\/sup>P2<\/sup>=(1\/3, 1\/3, 1\/3)<\/span><\/i> <\/span>
\n
\n
\n \"\"\/
\n
\n <\/sub>
\n
\n <\/span><\/p>\n


\n
\n \u00a0
\n
\n <\/span><\/p>\n

Definizione<\/b><\/p>\n

Se v<\/u>(0) <\/sup>= v<\/u> <\/i>\u00e8 tale che v<\/u> <\/sup>= v<\/u>P\u00a0\u00a0 <\/span><\/i>, allora \u00e8 detto misura invariante<\/i>.<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

Teorema (Markov-Kakutani)<\/b><\/p>\n

Se XN<\/sub> <\/i>\u00e8 CdM a stati finiti, allora esiste almeno una misura invariante.<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

Esistono
\ncondizioni iniziali che non producono variazione del vettore di
\ndistribuzione delle probabilit\u00e0, il teorema M-K afferma che tutte le
\nCdM a stati finiti (i.e. con |E| <\/i>finito) ne hanno almeno una.<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

Definizione<\/b><\/p>\n

P <\/i>\u00e8 regolare<\/i> se esiste n<\/i> t.c. Pn<\/sup><\/i> > 0.<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

La
\nmatrice delle probabilit\u00e0 di transizione in un passo \u00e8 regolare se
\nesiste almeno una sua potenza in cui tutti gli elementi sono positivi.<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

Teorema (Markov)<\/b><\/p>\n

Se XN<\/sub> <\/i>\u00e8 CdM a stati finiti, allora esiste una unica misura invariante
\n
\n
\n \"\"\/
\n
\n <\/sub>
\n
\n .<\/p>\n

Ovvero si ottiene che la legge di distribuzione delle probabilit\u00e0 tende ad un vettore stazionario p<\/span><\/span><\/u>:<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n


\n
\n
\n \"\"\/
\n
\n <\/sub>
\n \n <\/p>\n


\n
\n \u00a0
\n
\n <\/u><\/p>\n

Il vettore delle probabilit\u00e0 stazionarie p<\/span><\/span><\/u> si ottiene risolvendo il sistema seguente:<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n


\n
\n
\n \"\"\/
\n
\n <\/sub>
\n
\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span>[6]<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

Nell’esempio 2, il vettore stazionario si ottiene risolvendo il sistema:<\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n

\n
\n \u00a0
\n
\n <\/p>\n


\n
\n
\n \"\"\/
\n
\n <\/sub><\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span>da cui \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span>p<\/span><\/span> <\/u>= (4\/11, 3\/11, 4\/11)<\/p>\n","protected":false},"excerpt":{"rendered":"

[…]<\/p>\n","protected":false},"author":180,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[71],"tags":[],"class_list":["post-37","post","type-post","status-publish","format-standard","hentry","category-statistica-e-probabilita"],"_links":{"self":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/37","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/users\/180"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/comments?post=37"}],"version-history":[{"count":0,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/37\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/media?parent=37"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/categories?post=37"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/tags?post=37"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}