[HOME PAGE] [STORES] [CLASSICISTRANIERI.COM] [FOTO] [YOUTUBE CHANNEL]

Model ocult de Markov - Viquipèdia

Model ocult de Markov

De Viquipèdia

Exemple de transició d'estats en un model ocult de Markov x — estats ocults y — eixides observables a — probabilitats de transició b — probabilitats d'eixida
Exemple de transició d'estats en un model ocult de Markov
x — estats ocults
y — eixides observables
a — probabilitats de transició
b — probabilitats d'eixida

Un model ocult de Markov o HMM (per les seves sigles de l'anglès, Hidden Markov Model) és un model estadístic en el que s'assumeix que el sistema a modelar és un procés de Markov de paràmetres desconeguts. L'objectiu és determinar els paràmetres desconeguts (o ocults, per això el nom) de la cadena a partir dels paràmetres observable. 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 Markov 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 Markov, 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 Markov 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.

Taula de continguts

[edita] Història

Els models ocults de Markov 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]

[edita] Arquitectura d'un model ocult de Markov

El diagrama que es troba més avall 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 Markov. De forma 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 Markov

[edita] Probabilitat d'una seqüència observada

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

P(Y)=\sum_{X}P(Y\mid X)P(X),

on el sumatori s'exté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. No obstant, el càlcul pot accelerar-se notòriament utilitzant un algorisme conegut com el procediment d'avançament-retrocés.[3].


[edita] Ús dels models ocults de Markov

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.

[edita] Exemple

Imagineu que teniu un amic que viu lluny i amb qui parleu a diari per telèfon al voltant 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 Markov discreta. Existeixen dos estats: "plujós" i "assolellat", però no els podeu observar directament, és a dir, estan ocults. Existeix també una certa possibilitat de qeu el vostre amic faça una de les seves activitats cada dia 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 Markov.

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 ploga). 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 Markov per darrere del model. En aqeust exemple, hi ha un 30% de probabilitat que de demà estiga assolellat si avuí 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 de que estiga netejant sa casa; si fa sol, hi ha un 60% de probabilitat de que haja eixit a caminar.


[edita] Aplicacions de models ocults de Markov

El model ocult de Markov 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 que 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

[edita] Refefències

  1. ↑ Rabiner, p. 258
  2. ↑ Durbin et al.
  3. ↑ Rabiner, p. 262
  4. ↑ Pardo et al.

[edita] Vegeu també

  • Andrei Markov
  • Algorisme de Baum-Welch
  • Inferència bayesiana
  • Estimació estadística
  • Algorisme de Viterbi
  • Model ocult de Markov jeràrquic
  • Model ocult de Markov per capes
  • Model ocult de semi-Markov
  • Model de Markov d'ordre variable

[edita] Enllaços externs