Model ocult de Màrkov

Un model ocult de Màrkov o HMM (per les seves sigles de l'anglès, Hidden Markov Model) és un model estadístic en el qual s'entén que el sistema a modelar és un procés de Màrkov de paràmetres desconeguts. L'objectiu és determinar els paràmetres desconeguts (o ocults, d'aquí ve el seu nom) de la cadena a partir dels paràmetres observables. Els paràmetres extrets es poden emprar per dur a terme successives anàlisis, per exemple en aplicacions de reconeixement de patrons. Un HMM es pot considerar com la xarxa bayesiana dinàmica més simple.

En un model de Màrkov normal, l'estat és visible directament per a l'observador, pel que les probabilitats de transició entre estats són els únics paràmetres. En un model ocult de Màrkov, l'estat no és visible directament, sinó que només ho són les variables influïdes per l'estat. Cada estat té una distribució de probabilitat sobre els símbols d'eixida. Per tant, la seqüència de símbols generada per un HMM proporciona certa informació al voltant de la seqüència d'estats.

Els models ocults de Màrkov són especialment aplicats a reconeixement de formes temporals, com puga ser el reconeixement de la parla, d'escriptura manual, de gestos o en altres camps com la bioinformàtica.

Història

Els models ocults de Màrkov van ser descrits per primera vegada en una sèrie d'articles estadístics per Leonard E. Baum i altres autors de la segona meitat de la dècada de 1960. Una de les primeres aplicacions dels HMMs va ser el reconeixement de la parla, començant en la meitat de la dècada de 1970.^[1]

En la segona meitat de la dècada de 1980, els HMMs van començar a ser aplicats a les anàlisis de seqüències biològiques, en particular d'ADN. Des d'aquell moment, s'han fet omnipresents en el camp de la bioinformàtica.^[2]

Arquitectura d'un model ocult de Màrkov

El diagrama que es troba tot seguit mostra l'arquitectura general d'un HMM. Cada oval representa una variable aleatòria que pot prendre determinats valors. La variable aleatòria $x(t)$ és el valor de la variable oculta en l'instant de temps $t$ . La variable aleatòria $y(t)$ és el valor de la variable observada en el mateix instant $t$ . Les fletxes indiquen dependències condicionals.

Del diagrama queda clar que el valor de la variable oculta $x(t)$ (en l'instant $t$ ) només depèn del valor de la variable oculta $x(t-1)$ (en l'instant $t-1$ ). A açò s'anomena propietat de Màrkov. De manera similar, el valor de la variable observada $y(t)$ només depén del valor de la variable oculta $x(t)$ (ambdues en l'instant $t$ ).

Evolució en el temps d'un model ocult de Màrkov

Probabilitat d'una seqüència observada

La probabilitat d'observar la seqüència $Y=y(0),y(1),\dots ,y(L-1)$ de longitud $L$ ve donada per

P(Y)=\sum _{X}P(Y\mid X)P(X),

on el sumatori s'estén sobre totes les seqüències de nodes ocults $X=x(0),x(1),\dots ,x(L-1).\,$ El càlcul per força bruta de $P(Y)$ es impràctic per a la majoria de problemes reals, donat que el nombre de seqüències de nodes ocults serà extremadament alt. Tanmateix, el càlcul pot accelerar-se notòriament utilitzant un algorisme conegut com el procediment d'avançament-retrocés.^[3]

Ús dels models ocults de Màrkov

Existeixen tres problemes canònics associats amb HMMs:

Donats els paràmetres del model, computar la probabilitat d'una seqüència d'eixida en particular. Aquest problema es resol amb l'algorisme d'avançament-retrocés.
Donats els paràmetres del model, trobar la seqüència més probable d'estats ocults que poden haver generat una seqüència d'eixida donada. Aquest problema es resol amb l'algorisme de Viterbi.
Donada una seqüència d'eixida o un conjunt de seqüències d'eixida, trobar el conjunt d'estats de transició i probabilitats d'eixida més probables. En altres paraules, entrenar als paràmetres del HMM donada una seqüència de dades. Aquest problema es resol amb l'algorisme de Baum-Welch.

Exemple

Imagineu que teniu un amic que viu lluny i amb qui parleu cada dia per telèfon de tot el que ha fet durant el dia. Al vostre amic li interessen tres activitats: caminar per la plaça, anar de compres i netejar el seu pis. Allò que fa el seu amic depèn només de l'estat del temps en eixe dia. No teniu informació clara al voltant de l'estat del temps del lloc on viu el vostre amic, però coneixeu tendències generals. Basant-se en el que li diu el seu amic que ha fet en el dia, intenteu endevinar l'estat del temps.

Suposeu que l'estat del temps es comporta com una cadena de Màrkov discreta. Existeixen dos estats: "plujós" i "assolellat", però no els podeu observar directament, és a dir, estan ocults. Existeix també una certa possibilitat que el vostre amic faça una de les seves activitats cada dia, depenent de l'estat del temps: "caminar", "comprar" o "netejar". Donat que el vostre amic vos diu les seves activitats del dia, eixes són les observacions. El sistema complet és un model ocult de Màrkov.

Coneixeu les tendències generals del temps en l'àrea, i allò que li agrada al seu amic. En altres paraules, els paràmetres del HMM són coneguts. Podeu escriure'ls utilitzant llenguatge de programació Python:

estats = ('Plujós', 'Assolellat')

observacions = ('caminar', 'comprar', 'netejar')

probabilitat_inicial = {'Plujós': 0.6, 'Assolellat': 0.4}

probabilitat_transicio = {
 'Plujós' : {'Plujós': 0.7, 'Assolellat': 0.3},
 'Assolellat' : {'Plujós': 0.4, 'Assolellat': 0.6},
}

probabilitat_emisio = {
 'Plujós' : {'caminar': 0.1, 'comprar': 0.4, 'netejar': 0.5},
 'Assolellat' : {'caminar': 0.6, 'comprar': 0.3, 'netejar': 0.1},
}

En aquest tros de codi, probabilitat_inicial representa l'estat en el que penseu que es troba el HMM la primera vegada que parleu amb el vostre amic (és a dir, sap que és un poc més probable que plogui). La distribució de probabilitat que s'ha utilitzat ací no és la d'equilibri, que és (donades les probabilitats de transició) aproximadament {'Plujós': 0.571, 'Assolellat': 0.429}. La probabilitat_transicio representa el canvi del temps en la cadena de Màrkov per darrere del model. En aquest exemple, hi ha un 30% de probabilitat que de demà estiga assolellat si avui ha plogut. La probabilitat_emisio representa amb quanta probabilitat el seu amic realitza una activitat determinada cada dia. Si plou, hi ha un 50% de probabilitat que estiga netejant sa casa; si fa sol, hi ha un 60% de probabilitat que haja eixit a caminar.

Aplicacions de models ocults de Màrkov

Criptoanàlisi
Reconeixement de la parla, de gestos i de moviments corporals, reconeixent òptic de caràcters
Traducció automàtica

El model ocult de Màrkov s'utilitza de manera habitual en aquest camp per tal de modelar el llenguatge amb l'objectiu, per exemple, fer classificadors morfo-sintàctics (part-of-speech - PoS - tagger).

A mesura que van obtenint-se entrades, el model va canviant d'un estat a un altre (segons les probabilitats internes) i emet observables (que poden ser les classes dels mots d'entrada). Els estats del model representen les etiquetes amb què podem identificar les distintes classes de mots.

En primer lloc s'entrena el model, i més tard s'utilitza per conèixer quin és el camí entre els estats més probables, per obtenir la categorització de totes les paraules.

Després d'entrenar el model amb suficient exemples del llenguatge a modelar, s'utilitza

Musical score following^[4]
Bioinformàtica i Genòmica
- predicció de regions proteïno-codificables en seqüències de genomes
- modelat de families de seqüències de proteïna o ADN relacionat
- predicció d'elements d'estructura secundaris de seqüències primàries de proteïna

Referències

↑ Rabiner, p. 258
↑ Durbin i cols.
↑ Rabiner, p. 262
↑ Pardo i cols.

Vegeu també

Enllaços externs

Hidden Markov Model (HMM) Toolbox per a Matlab Arxivat 2005-01-07 a Wayback Machine. (per Kevin Murphy)
Hidden Markov Model Toolkit (HTK) (un toolkit portable per a la construcció i manipulació de models ocults de Markov)
Hidden Markov Models (presentació amb matèria bàsica)
GHMM Library (pàgina d'inici del projecte GHMM Library)
Jahmm Java Library Arxivat 2006-05-19 a Wayback Machine. (biblioteca Java i aplicacions gràfiques associades)

[1] Rabiner, p. 258

[2] Durbin i cols.

[3] Rabiner, p. 262

[4] Pardo i cols.

[1]

[2]

[3]

[4]