Modelos Ocultos de Markov - us

Cadenas de Markov Modelos Ocultos de Markov

Modelos Ocultos de Markov

José Luis Ruiz ReinaFranciso J. Martín Mateos

Carmen Graciani Díaz

Dpto. Ciencias de la Computación e Inteligencia ArtificialUniversidad de Sevilla


Contenido

Cadenas de Markov

Modelos Ocultos de Markov


Tiempo e Incertidumbre

• En este tema vamos a ver razonamiento probabilístico ensituaciones que discurren a lo largo del tiempo o ensecuencia:

• Ejemplos:• Reconocimiento del habla• Movimiento de robots• Procesamiento de textos• Bioinformática

• Situaciones que transcurren en el tiempo:• El tiempo se considera en instantes discretos: t = 1,2,3, . . .• Cada instante se modela mediante un conjunto de

variables aleatorias, algunas observables y otras no.• Las relaciones entre dichas variables, así como las

transiciones entre un instante y el siguiente, estánafectadas de incertidumbre, que será modelada mediantedistribuciones de probabilidad condicionada.


Cadenas de Markov

• Es el modelo más simple que veremos.• Supongamos que la situación en cada instante t se

describe mediante una única variable aleatoria Xt , quetienen un número finito de posibles valores quellamaremos estados: s1, s2, . . . , sn• En cada instante t , la variable Xt toma exactamente uno de

sus posibles estados.• Ejemplo:

• Supongamos que el tiempo de cada día puede ser descritocomo calor, frío o lluvia

• Cadena de Markov: la v.a. Xt sería el tiempo del día t , y{calor, frío, lluvia} el conjunto de posibles estadosde la variable.


Propiedad de Markov

• Tenemos ahora que detallar cómo cambia, a lo largo deltiempo, el mundo que se describe.

• Asumiremos la siguiente propiedad, llamada propiedad deMarkov (A. Markov, 1856-1922):

P(Xt |X1, . . . ,Xt−1) = P(Xt |Xt−1)

• En una cadena de Markov, el estado actual sólo dependedel estado inmediatamente anterior.

• Asumiremos también que la distribución P(Xt |Xt−1) esindependiente de t• Es decir, el modelo probabilístico que describe la manera

de transitar entre un instante y el siguiente, no cambia conel tiempo

• Es lo que se denomina un proceso estacionario


Cadena de Markov y redes bayesianas

• Vista como red bayesiana, una cadena de Markov tiene lasiguiente estructura:

Xt+1

Xt−2

Xt

Xt+2X

t−1

• Cada nodo tiene una tabla de probabilidad correspondientea P(Xt |Xt−1)

• La misma tabla en todos los nodos• Excepto en el instante inicial X1, cuya tabla es P(X1)

• Recordar: la estructura de la red implica que, dada lainmediatamente anterior, cada variables es independientede todas las anteriores


Componentes de una cadena de Markov

• El conjunto de estados s1, . . . , sn (posibles valores de cadaXt )

• La tabla de probabilidad P(Xt |Xt−1), dada por una matrizde probabilidades de transición A = (aij)• Donde cada aij = P(Xt = sj |Xt−1 = si)• Es una matriz de tamaño n × n, donde n es el número de

posibles estados• Se cumple que

∑1≤j≤n

aij = 1

• Además para el instante inicial, debemos especificar unvector π = (πi), donde πi = P(X1 = si) (probabilidadesiniciales para cada estado).


Ejemplo de cadena de Markov

• Estados: {calor, frío, lluvia} (supondremos ques1 = calor, s2 = frío y s3 = lluvia)

• Matriz de probabilidades de transición:a11 = P(Xt = calor|Xt−1 = calor) = 0.5a12 = P(Xt = frío|Xt−1 = calor) = 0.2a13 = P(Xt = lluvia|Xt−1 = calor) = 0.3a21 = P(Xt = calor|Xt−1 = frío) = 0.2a22 = P(Xt = frío|Xt−1 = frío) = 0.5a23 = P(Xt = lluvia|Xt−1 = frío) = 0.3a31 = P(Xt = calor|Xt−1 = lluvia) = 0.3a32 = P(Xt = frío|Xt−1 = lluvia) = 0.1a33 = P(Xt = lluvia|Xt−1 = lluvia) = 0.6

• Probabilidades iniciales:π1 = P(X1 = calor) = 0.5π2 = P(X1 = frío) = 0.3π3 = P(X1 = lluvia) = 0.2


Representación gráfica de una cadena de Markov• Es usual representar una cadena de Markov como un

grafo dirigido• Los nodos son los estados• Los arcos están etiquetados con la probabilidad de pasar

de un estado a otro

0.5

0.6

0.5

0.1

0.3

0.2

0.2

0.3

0.3

0.5

0.3

0.2

lluvia

frio

calor


Otro ejemplo de cadena de Markov

• Secuencias formadas con las palabras “la”, “nieve”,“es” y “blanca”

la

es

0.7

0.2

0.1

0.1

0.1 0.1

0.1 0.1

0.1

0.5

0.3

0.3

0.3

0.3

0.2

0.3

0.40.3

0.4

0.2

nieve

blanca


Calculando probabilidades en una cadena de Markov

• Dos tipos de preguntas:• ¿Cuál es la probabilidad de que ocurra una determinada

secuencia de estados Q = q1 · · · qt? (es decir,P(X1 = q1,X2 = q2, . . . ,Xt = qt), abreviado comoP(q1q2 · · · qt))

• ¿Cuál es la probabilidad de que en el instante t se llegue alestado q? (Es decir, P(Xt = q))


Probabilidad de una secuencia de estados

• ¿P(q1q2 · · · qt)?• Aplicando la regla de la cadena, es igual a:

P(Xt = qt |X1 = q1, . . . ,Xt−1 = qt−1)·· · ··P(X2 = q2|X1 = q1)·P(X1 = q1)

• Por la propiedad de Markov, eso es igual a:

P(Xt = qt |Xt−1 = qt−1) · · ·P(X2 = q2|X1 = q1) · P(X1 = q1)

• Luego P(q1q2 · · · qt ) = πq1 · aq1q2 · aq2q3 · · · aqt−2qt−1 aqt−1qt

• Es decir, la probabilidad de una secuencia es el productode las correspondientes probabilidades de transitar decada estado al siguiente.

• Ejemplos:• P(calor calor lluvia frío) = 0.5 · 0.5 · 0.3 · 0.1 = 0.0075• P(la nieve es blanca) = 0.7 · 0.5 · 0.4 · 0.3 = 0.042• P(blanca es nieve la) = 0.1 · 0.3 · 0.3 · 0.2 = 0.0018


Probabilidad de llegar a un estado

• Notación: P(Xt = q) = pt(q) ¿Cómo calculamos pt(q)?• Una primera idea: pt (q) = P(Xt = q) =

∑Q P(Q), donde tenemos

un sumando por cada secuencia Q = q1 · · · qt que acabaen el estado q (qt = q).• Por ejemplo, p3(calor) = P(calor calor calor)+

P(calor frío calor) + P(calor lluvia calor) + · · ·+P(lluvia frío calor) + P(lluvia lluvia calor)

• Ineficiente: nt−1 sumandos• Una alternativa más eficiente: calcular recursivamente los

valores pt(si) para todos los estados 1 ≤ i ≤ n• p1(si ) = P(X1 = si ) = πi , 1 ≤ i ≤ n• pt (sj ) = P(Xt = sj ) =

∑1≤i≤n

P(Xt = sj ,Xt−1 = si ) =∑1≤i≤n

(P(Xt = sj |Xt−1 = si ) · P(Xt−1 = si )) =∑

1≤i≤n

(aij · pt−1(si ))

• Complejidad: O(t · n2)


Ejemplo de cálculo de probabilidad de llegar a unestado

• p1(calor) = 0.5

• p1(frío) = 0.3

• p1(lluvia) = 0.2

• p2(calor) = 0.5 · p1(calor) + 0.2 · p1(frío) + 0.3 · p1(lluvia) = 0.37

• p2(frío) = 0.2 · p1(calor) + 0.5 · p1(frío) + 0.1 · p1(lluvia) = 0.27

• p2(lluvia) = 0.3 · p1(calor) + 0.3 · p1(frío) + 0.6 · p1(lluvia) = 0.36

• p3(calor) = 0.5 · p2(calor) + 0.2 · p2(frío) + 0.3 · p2(lluvia) = 0.347

• · · ·


Modelos ocultos de Markov

• Muchas situaciones reales no pueden modelarse mediantecadenas de Markov• Problema: el valor de Xt (el estado) no es observable

directamente• Lo que podemos observar depende del estado, aunque con

cierta incertidumbre• Ejemplos:

• Etiquetado léxico• Movimiento de robots• Reconocimiento del habla• Bioinformática


Modelos ocultos de Markov: propiedades asumidas• En un modelo oculto de Markov, para cada instante t

tenemos:• una variable aleatoria Xt , con posibles valores {s1, . . . , sn}

(estados, no observable directamente)• otra variable aleatoria Et , con posibles valores {v1, . . . , vm}

(percepciones, observable directamente)• Propiedades asumidas:

• Propiedad de Markov:

P(Xt |X1,X2, . . . ,Xt−1) = P(Xt |Xt−1)

• Independencia de las percepciones:

P(Et |X1, . . . ,Xt ,E1, . . . ,Et−1) = P(Et |Xt )

• En otras palabras:• En cada instante, el estado depende sólo del estado en el

instante inmediatamente anterior• En cada instante, lo observado depende sólo del estado en

ese instante


Ejemplo 1 de modelo oculto de Markov (J. Eisner)

• Supongamos que en el año 2534, un científico quiereestudiar el tiempo que hubo en el año 2020, pero no escapaz de encontrar datos (por simplificar supondremossólo dos tipos de días: c (calor) y f (frío)). Pero haencontrado un diario de la época, en el que una personadescribe cuántos helados tomó cada día de 2020 (1,2 ó 3).• Estados: variable Xt que indica el tiempo en el día t

(posibles estados c y f )• Percepciones: variable Et , número de helados comidos el

día t (1, 2 ó 3).• En este ejemplo, es razonable asumir que se cumple la

propiedad de Markov y la de la independencia de laspercepciones:• El tiempo que haga un día depende sólo del tiempo del día

anterior.• La cantidad de helados comidos sólo depende

(probabilísticamente) del tiempo en ese mismo día


Ejemplo 2 (Russell & Norvig)

• Un guardia de seguridad trabaja en unas oficinassubterráneas, sin conexión con el exterior. Cada día, nopuede saber si está lloviendo o no, pero ve llegar aldirector de la oficina, que puede o no llevar paraguas• Estados: variable Xt que indica si llueve o no en el día t

(con posibles estados l y ¬l)• Percepciones: variable Et , que indica si el director lleva o

no paraguas (con posibles valores u y ¬u)

• Nuevamente, es razonable asumir en este caso laspropiedades de un modelo oculto de Markov


Modelos ocultos de Markov y redes bayesianas

• Vista como red bayesiana, una modelo oculto de Markovtiene la siguiente estructura:

Xt+1

Xt−2

Xt

Xt+2

Et

Xt−1

t−2E E E E

t−1 t+1 t+2

• Cada nodo Xt tiene una tabla de probabilidadcorrespondiente a P(Xt |Xt−1) (la misma tabla en todos losnodos)

• Excepto en el instante inicial X1, cuya tabla es P(X1)• Cada nodo Et tiene una tabla de probabilidad

correspondiente a P(Et |Xt) (la misma tabla en todos losnodos)


Componentes de un modelo oculto de Markov

• Por un lado, la parte correspondiente a la cadena deMarkov de los estados (modelo de transición):• Para cada t > 0, una variable Xt con posibles valores

s1, . . . , sn (estados)• La tabla de probabilidad P(Xt |Xt−1), dada por una matriz

A = (aij), donde aij = P(Xt = sj |Xt−1 = si) (probabilidad depasar de si a sj )

• Vector π = (πi), donde πi = P(X1 = si) (probabilidades apriori para cada estado).

• Por otro lado, la parte correspondiente a las percepciones(modelo sensor):• Para cada t > 0, una variable aleatoria Et , con posibles

valores {v1, . . . , vm}• La tabla de probabilidad P(Et |Xt), dada por una matriz de

probabilidades de percepción B = bi(vj), dondebi(vj) = P(Et = vj |Xt = si) (probabilidad de observar vjcuando el estado es si )


Representación gráfica, ejemplo 1

Suponiendo s1 = c y s2 = f

0.70.3

0.6

0.4

0.8 0.2

1b (1)

1b

1b

b (1)

b

b

(2)

(3)

2

2

2

(2)

(3)

= P(1 | c)=0.2

= P(2 | c)=0.4

= P(3 | c)=0.4

= P(1 | f)=0.5

= P(2 | f)=0.4

= P(3 | f)=0.1

c f


Representación gráfica, ejemplo 2

Suponiendo s1 = l y s2 = no l

b2(2) = P(no u | no l)=0.8

l no l

0.7 0.70.3

0.5 0.5

= P(u | l)=0.91b (1)

1b

b (1)

(2)2

= P(no u | l)=0.1

0.3

= P(u | no l)=0.2


Ejemplos de aplicaciones reales

• Reconocimiento del habla• Estados: las distintas sílabas• Percepciones: fonemas (con posible ruido)

• Localización de robots• Estados: posibles posiciones de un robot• Percepciones: datos de proximidad obtenidos de los

sensores


Problemas principales a resolver en MOMs

• Filtrado: dada una secuencia de percepciones o1, . . . ,ot yun estado q, ¿cuál es la probabilidad de que Xt = q?• Ejemplo: si sabemos que la secuencia de helados comidos

hasta el cuarto día es 3,1,3,2 ¿cuál es la probabilidad deel cuarto día sea un día frío?

• Explicación más verosímil (o Decodificación): habiendoobservado una secuencia o1, . . . ,ot ¿cuál es lacorrespondiente secuencia de estados más probable?• Ejemplo: si sabemos que la secuencia de helados comidos

hasta el sexto día es 1,1,2,2,3,3 ¿cuál es la secuenciamás probable del tiempo en los seis primeros días?

• Aprendizaje: habiendo observado una secuenciao1, . . . ,ot y conociendo los estados del modelo, pero nolas matrices de transición y de percepciones, aprenderdichas probabilidades


Filtrado

• Supongamos un modelo oculto de Markov:• Con variables aleatorias Xt (estado) y Et (percepción)• Con n estados {s1, . . . , sn} y m posibles percepciones{v1, . . . , vm}

• Con matriz de transición A y matriz de percepción B

• Supongamos que tenemos la secuencia O = o1o2 · · · ot ,percepciones hasta el instante t

• Filtrado: dado un estado q, queremos calcular laprobabilidad de que habiendo observado la secuencia Ohasta el instante t , el estado del sistema en ese últimoinstante sea q

• Es decir, queremos calcular P(Xt = q|o1o2 · · · ot)


Filtrado: una primera simplificación

• Téngase en cuenta que:

P(Xt |o1o2 · · · ot) = α · P(Xt ,o1o2 · · · ot)

• Luego bastará calcular P(Xt = si ,o1o2 · · · ot) para todoslos estados si (1 ≤ i ≤ n), y luego normalizar

• Es decir, la probabilidad de que hasta el instante thayamos observado la secuencia O y además el estadoen el instante t sea si


Una manera ineficiente de hacer filtrado

• Una forma de calcular P(Xt = q,O) es hacer∑

Q P(Q,O),donde tenemos un sumando por cada secuenciaQ = q1 · · · qt que acaba en el estado q (qt = q).• Supongamos dada una secuencia de estados Q = q1 · · · qt

y una secuencia de percepciones O = o1 · · · ot• Entonces (¿por qué?):

P(Q,O) = πq1 · aq1q2 · · · aqt−1qt · bq1(o1) · · · bqt (ot)

• Ineficiente: ¡¡ nt−1 sumandos !!• Alternativa eficiente (similar a lo que se hace en cadenas

de Markov):• Calcular P(Xt = si ,o1 · · · ot), de manera recursiva, para

todos los estados 1 ≤ i ≤ n


Cálculo recursivo para filtrado

• Si llamamos αt(sj) a P(Xt = sj ,o1 · · · ot), tenemos:• Inicio:α1(si) = P(X1 = si , o1) = P(o1|X1 = si) · P(X1 = si) = bi(o1) · πi

• Recursión:αt(sj) = P(Xt = sj , o1 · · · ot)

= P(ot |Xt = sj , o1 · · · ot−1) · P(Xt = sj , o1 · · · ot−1)

= P(ot |Xt = sj) ·∑

1≤i≤n

P(Xt = sj ,Xt−1 = si , o1 · · · ot−1)

= P(ot |Xt = sj) ·∑

1≤i≤n

( P(Xt = sj |Xt−1 = si , o1 · · · ot−1) ·P(Xt−1 = si , o1 · · · ot−1) )

= P(ot |Xt = sj) ·∑

1≤i≤n

( P(Xt = sj |Xt−1 = si) ·P(Xt−1 = si , o1 · · · ot−1) )

= bj(ot)∑

1≤i≤n

(aij · αt−1(si))


Algoritmo de “avance”(forward)

• Entrada:• Un modelo oculto de Markov• Una secuencia de percepciones O = o1 · · · ot

• Salida:• Valores αt(si) = P(Xt = sj ,o1 · · · ot), para cada estado si

• Procedimiento:• Inicio: α1(si) = bi(o1) · πi , para 1 ≤ i ≤ n• Para k desde 2 a t :

• Para j desde 1 a n:• Hacer αk (sj) = bj(ok )

∑1≤i≤n

(aij · αk−1(si))

• Devolver los αt(si), para 1 ≤ i ≤ n

Nótese que la recursión es similar a la que se ha visto para cadenas deMarkov, pero en este caso se “actualiza” con la probabilidad de lapercepción, bj(ok )


Algoritmo de avance para el ejemplo 1

• Para el ejemplo 1, supongamos que hasta el cuarto día lasecuencia de percepciones es O = (3,1,3,2) (es deciro1 = 3, o2 = 1, o3 = 3 y o4 = 2). Calculemos α4(s1) yα4(s2) (donde s1 = c y s2 = f )• Paso 1:

α1(s1) = b1(o1) · π1 = 0.4 · 0.8 = 0.32α1(s2) = b2(o1) · π2 = 0.1 · 0.2 = 0.02

• Paso 2:α2(s1) = b1(o2) · [a11 · α1(s1) + a21 · α1(s2)]

= 0.2 · [0.7 · 0.32 + 0.4 · 0.02] = 0.0464α2(s2) = b2(o2) · [a12 · α1(s1) + a22 · α1(s2)]

= 0.5 · [0.3 · 0.32 + 0.6 · 0.02] = 0.054



• Para el ejemplo 1, supongamos que hasta el cuarto día lasecuencia de percepciones es O = (3,1,3,2) (es deciro1 = 3, o2 = 1, o3 = 3 y o4 = 2). Calculemos α4(s1) yα4(s2) (donde s1 = c y s2 = f )• Paso 3:

α3(s1) = b1(o3) · [a11 · α2(s1) + a21 · α2(s2)]

= 0.4 · [0.7 · 0.0464 + 0.4 · 0.054] = 0.021632α3(s2) = b2(o3) · [a12 · α2(s1) + a22 · α2(s2)]

= 0.1 · [0.3 · 0.0464 + 0.6 · 0.054] = 0.004632

• Paso 4:α4(s1) = b1(o4) · [a11 · α3(s1) + a21 · α3(s2)]

= 0.4 · [0.7 · 0.021632 + 0.4 · 0.004632] = 0.00679808α4(s2) = b2(o4) · [a12 · α3(s1) + a22 · α3(s2)]

= 0.4 · [0.3 · 0.021632 + 0.6 · 0.004632] = 0.00370752



• Para el ejemplo 2, supongamos que los dos primeros díasobservamos paraguas y el tercero no (es decir, o1 = u,o2 = u y o3 = ¬u). Calculemos la probabilidad de lluvia enel tercer día (los estados son s1 = l y que s2 = ¬l)• Paso 1:

α1(s1) = b1(o1) · π1 = 0.9 · 0.5 = 0.45α1(s2) = b2(o1) · π2 = 0.2 · 0.5 = 0.1

• Paso 2:α2(s1) = b1(o2) · [a11 · α1(s1) + a21 · α1(s2)]

= 0.9 · [0.7 · 0.45 + 0.3 · 0.1] = 0.3105α2(s2) = b2(o2) · [a12 · α1(s1) + a22 · α1(s2)]

= 0.2 · [0.3 · 0.45 + 0.7 · 0.1] = 0.0410



• Para el ejemplo 2, supongamos que los dos primeros díasobservamos paraguas y el tercero no (es decir, o1 = u,o2 = u y o3 = ¬u). Calculemos la probabilidad de lluvia enel tercer día (los estados son s1 = l y que s2 = ¬l)• Paso 3:

α3(s1) = b1(o3) · [a11 · α2(s1) + a21 · α2(s2)]

= 0.1 · [0.7 · 0.3105 + 0.3 · 0.0410] = 0.022965α3(s2) = b2(o3) · [a12 · α2(s1) + a22 · α2(s2)]

= 0.8 · [0.3 · 0.3105 + 0.7 · 0.0410] = 0.097480

• Nota: ¿tenemos ya calculada la probabilidad de que eltercer día sea de lluvia dado que se han observadoparaguas en los dos primeros días y sin paraguasel tercero?

• Aún no, queda un pequeño paso (¿cuál?)


Idea gráfica del cálculo que se realiza

Imagen tomada de wikipedia


¿Cómo usamos los αt(sj)? (I)

• Recordar que αt(sj) = P(Xt = sj ,o1 · · · ot)

• Los αt(sj) que calcula el algoritmo de avance se usanpara:• Calcular la probabilidad (incondicional) de una secuencia

dada de percepciones• Calcular la probabilidad de que tengamos un estado en el

instante t , dada la secuencia de percepciones hasta eseinstante (lo que hemos llamado filtrado)

• Cálculo de la probabilidad de una secuencia:• P(o1 · · · ot) =

∑1≤i≤n

P(Xt = si ,o1 · · · ot) =∑

1≤i≤n

αt(si)

• En el ejemplo 1, la probabilidad de la secuencia depercepciones O = (3,1,3,2) es P(O) = α4(s1) + α4(s2) =0.00679808 + 0.00370752 = 0.0105056


¿Cómo usamos los αt(sj)? (II)

• Cálculo de la probabilidad de que en el instante t estemosen un estado sj , condicionado a que se ha observado lasecuencia o1 · · · ot (filtrado):• P(Xt |o1 · · · ot) se obtiene normalizando P(Xt ,o1 · · · ot)• Es decir, normalizando los αt(si), 1 ≤ i ≤ n, se obtienen las

correspondientes probabilidades de filtrado• En el ejemplo 2, la probabilidad de que el tercer día sea

lluvioso, dado que se ha observado O = (u,u,¬u) (los dosprimeros días con paraguas y el tercero no) se obtiene:• Normalizamos 〈α3(s1), α3(s2)〉 =〈0.190667939723525, 0.809332060276475〉, obteniendo≈ 〈0.19, 0.81〉

• Por tanto, P(X3 = l|uu¬u) ≈ 0.19


Smoothing¿cuál es el estado más probable para alguna de las posicionesintermedias?

• Supongamos que tenemos la secuencia O = o1o2 · · · ot depercepciones hasta el instante t .

• Dado un estado q queremos calcular la probabilidad deque, habiendo observado la secuencia O hasta el instantet , el estado del sistema en el instante k (1 ≤ k < t) sea q;

P(Xk = q|O) =P(Xk = q,O)

P(O)=

P(Xk = q,O)∑1≤i≤n

αt(si).

• Se tiene que

P(Xk = q,O) = P(Xk = q, o1, . . . , ok )P(ok+1, . . . , ot |Xk = q, o1, . . . , ok )

= P(Xk = q, o1, . . . , ok )P(ok+1, . . . , ot |Xk = q)

= αk (q)P(ok+1, . . . , ot |Xk = q)


Cálculo recursivo para “smoothing” (I)

Si llamamos βk (sj) a P(ok+1, . . . ,ot |Xk = sj), tenemos:• Inicio:βt−1(si)= P(ot |Xt−1 = si) =

∑1≤j≤n

P(ot ,Xt = sj |Xt−1 = si)

=∑

1≤j≤n

P(ot |Xt = sj ,Xt−1 = si)P(Xt = sj |Xt−1 = si)

=∑

1≤j≤n

P(ot |Xt = sj)aij =∑

1≤j≤n

bj(ot)aij


Cálculo recursivo para “smoothing” (II)

• Recursión:βr (si) = P(or+1, . . . , ot |Xr = si) =

∑1≤j≤n

P(or+1, . . . , ot ,Xr+1 = sj |Xr = si)

=∑

1≤j≤n

P(or+1, . . . , ot |Xr+1 = sj ,Xr = si)P(Xr+1 = sj |Xr = si)

=∑

1≤j≤n

P(or+1, or+2, . . . , ot |Xr+1 = sj)aij

=∑

1≤j≤n

P(or+1|Xr+1 = sj)P(or+2, . . . , ot |Xr+1 = sj , or+1)aij

=∑

1≤j≤n

bj(or+1)P(or+2, . . . , ot |Xr+1 = sj)aij =∑

1≤j≤n

bj(or+1)βr+1(sj)aij

Se suele iniciar la recursión considerando: βt(si) = 1


Algoritmo de “retroceso”(backward)

• Entrada:• Un modelo oculto de Markov• Una secuencia de percepciones O = o1 · · · ot• Un entero k tal que 1 ≤ k < t .

• Salida:• Valores βk (si) = P(ok+1, . . . ,ot |Xk = si), para cada estado

si

• Procedimiento:• Inicio: βt(si) = 1, para 1 ≤ i ≤ n• Para r desde t − 1 a k :

• Para j desde 1 a n:• Hacer βr (sj) =

∑1≤i≤n

bi(or+1)βr+1(si)aji

• Devolver los βk (si), para 1 ≤ i ≤ n


Algoritmo de retroceso para el ejemplo 1

• Para el ejemplo 1, supongamos que hasta el cuarto día lasecuencia de percepciones es O = (3,1,3,2) (es deciro1 = 3, o2 = 1, o3 = 3 y o4 = 2). Calculemos β2(s2) yβ2(s2) (donde s1 = c y s2 = f )• Paso 1:

β3(s1) = b1(o4) · a11 + b2(o4) · a12

= 0.4 · 0.7 + 0.4 · 0.3 = 0.4β3(s2) = b1(o4) · a21 + b2(o4) · a22

= 0.4 · 0.4 + 0.4 · 0.6 = 0.4

• Paso 2:β2(s1) = b1(o3) · β3(s1) · a11 + b2(o3) · β3(s2) · a12

= 0.4 · 0.4 · 0.7 + 0.1 · 0.4 · 0.3 = 0.124β2(s2) = b1(o3) · β3(s1) · a21 + b2(o3) · β3(s2) · a22

= 0.4 · 0.4 · 0.4 + 0.1 · 0.4 · 0.6 = 0.088


Algoritmo de retroceso para el ejemplo 1

• Para el ejemplo 1, supongamos que hasta el cuarto día lasecuencia de percepciones es O = (3,1,3,2) (es deciro1 = 3, o2 = 1, o3 = 3 y o4 = 2). ¿Cuál es la probabilidadde cada uno de los estados el segundo día?

A partir de los ejemplos de avance y retroceso tenemosque:• α2(s1) = 0.0464 y α2(s2) = 0.054• β2(s1) = 0.124 y β2(s2) = 0.088

Multiplicando y normalizando:• P(X2 = s1|O) = .5476698• P(X2 = s2|O) = .4523302


Algoritmo “forward-backward”

• Entrada:• Un modelo oculto de Markov• Una secuencia de percepciones O = o1 · · · ot• Un entero k tal que 1 ≤ k ≤ t .

• Salida:• Valores P(Xk = si ,o1, . . . ,ot), para cada estado si

• Procedimiento:• Inicio: βt(si) = 1 y α1(si) = bi(o1) · πi , para 1 ≤ i ≤ n• Para r desde t − 1 a k :

• Para j desde 1 a n:• Hacer βr (sj) =

∑1≤i≤n

bi(or+1)βr+1(si)aji

• Para r desde 2 a k :• Para j desde 1 a n:• Hacer αr (sj) = bj(or )

∑1≤i≤n

(aij · αr−1(si))

• Devolver αk (si)βk (si), para 1 ≤ i ≤ n


Decodificación (explicación más verosímil)

• Nuevamente, tenemos un modelo oculto de Markov y unasecuencia de percepciones O = o1 · · · ot

• Se trata ahora de calcular la secuencia de estadosQ = q1 · · · qt que mejor explica las percepciones

• Es decir, buscamos:

argmaxQ

P(Q|O)

• Podríamos calcular P(Q|O) (ó P(Q,O)) para todas lassecuencias posibles de estados Q, y tomar aquella que dael máximo• Ineficiente (O(nt))

• Cómo con el filtrado, emplearemos un método máseficiente, basado en recursión


Decodificación: método recursivo

• Dada una secuencia de estados q1 · · · qt tal que qt = sj ,podemos calcular la probabilidad de pasar por esasecuencia de estados, habiendo además observadoo1 · · · ot .

• Notaremos νt(sj) a la máxima de esas probabilidades,entre todas esas secuencias de estados. Es decir:

νt(sj) = maxq1q2···qt−1

P(o1 · · · ot ,q1 · · · qt−1,Xt = sj)

• Cada νt(sj) se puede calcular recursivamente, en funciónde los νt−1(si),1 ≤ i ≤ n del instante anterior



• La idea principal de la recursión es que la secuencia más probable deestados hasta llegar a Xt = sj , se compone de la secuencia másprobable de llegar hasta un cierto estado si en el instante t − 1, seguidode un paso de transición desde tal si a sj . Por tanto, sólo hay que“buscar” entre los caminos más probables hasta el instante t − 1 y verdesde cuál se obtiene la probabilidad máxima dando un paso más:

2s2s 2s

o1 o1

s

sn

1

3s

s

sn

1

3s

s

sn

1

3s

sj

ks

1 2 t−1

ot−1

t

ot

Tiempo:

estados

Posibles

Percepciones:



• Inicio: ν1(si) = P(o1,X1 = si) = P(o1|X1 = si) · P(X1 = si) = bi(o1)πi

• Recursión:νt(sj) = max

q1q2···qt−1P(o1 · · · ot , q1 · · · qt−1,Xt = sj)

= maxq1q2···qt−1

( P(ot |o1 · · · ot−1, q1 · · · qt−1,Xt = sj) ·P(o1 · · · ot−1, q1 · · · qt−1,Xt = sj) )

= P(ot |Xt = sj) · maxq1q2···qt−1

P(o1 · · · ot−1, q1 · · · qt−1,Xt = sj)

= P(ot |Xt = sj) ·max

i=1,...,n( P(Xt = sj |Xt−1 = si) ·

maxq1q2···qt−2

P(o1 · · · ot−1, q1 · · · qt−2,Xt−1 = si) )

= bj(ot) maxi=1,...,n

(aij · νt−1(si))



• Se trata de un esquema recursivo análogo al del algoritmode avance usado para filtrado, excepto que en lugar desumatorios, se toman máximos

• En este caso, además de calcular las probabilidadesmáximas, debemos llevar la cuenta de la secuencia deestados que se corresponden con esas probabilidades• Se consigue almacenando, para cada estado e instante de

tiempo, un puntero prt(sj) al estado inmediatamenteanterior en la secuencia más probable

• El método descrito se denomina algoritmo de Viterbi


Algoritmo de Viterbi


• Salida:• La secuencia de estados Q que maximiza P(Q|O)

• Procedimiento:• Inicio: Para i = 1, . . . ,n, hacer ν1(si) = bi(o1) · πi y

pr1(si) = null ,• Para k desde 2 a t :

• Para j desde 1 a n:• Hacer νk (sj) = bj(ok ) max

i=1,...,n(aij · νk−1(si))

• Hacer prk (sj) = argmaxi=1,...,n

(aij · νk−1(si))

• Hacer s = argmaxi=1,...,n

νt(si)

• Devolver la secuencia de estados que lleva hasta s(siguiendo hacia atrás los punteros, comenzando en prt(s))


Algoritmo de Viterbi para el ejemplo 1

• Para el ejemplo 1, supongamos que hasta el cuarto dia lasecuencia de percepciones es O = (3,1,3,2). Calculemosla secuencia de estados más probablecon esas percepciones (los estado son s1 = c y s2 = f )• Paso 1:

ν1(s1) = b1(o1) · π1 = 0.4 · 0.8 = 0.32pr1(s1) = nullν1(s2) = b2(o1) · π2 = 0.1 · 0.2 = 0.02pr1(s2) = null




ν2(s1) = b1(o2) ·max{a11 · ν1(s1), a21 · ν1(s2)}= 0.2 ·max{0.7 · 0.32, 0.4 · 0.02}= 0.2 ·max{0.224, 0.008} = 0.0448

pr2(s1) = s1


pr2(s2) = s1





pr3(s1) = s1


pr3(s2) = s2





pr4(s1) = s1


pr4(s2) = s1



• Para el ejemplo 1, supongamos que hasta el cuarto dia lasecuencia de percepciones es O = (3,1,3,2). Calculemosla secuencia de estados más probablecon esas percepciones (los estado son s1 = c y s2 = f )• Paso final:

• El estado que da la probabilidad máxima en t = 4 es s1,con probabilidad 0.00351232

• Reconstruimos el camino hasta s1:pr4(s1) = s1, pr3(s1) = s1, pr2(s1) = s1

• Luego la secuencia de estados más probable es(s1, s1, s1, s1) (es decir, cuatro días seguidos de calor)



• Para el ejemplo 2, supongamos que la secuencia depercepciones hasta el tercer día es O = (u,u,¬u)(paraguas los dos primeros días y el tercero no).Calculemos la secuencia de estados más probable, conesas percepciones (los estados son s1 = l y s2 = ¬l)• Paso 1:

ν1(s1) = b1(o1) · π1 = 0.9 · 0.5 = 0.45pr1(s1) = nullν1(s2) = b2(o1) · π2 = 0.2 · 0.5 = 0.1pr1(s2) = null





pr2(s1) = s1


pr2(s2) = s1





pr3(s1) = s1


pr3(s2) = s1



• Para el ejemplo 2, supongamos que la secuencia depercepciones hasta el tercer día es O = (u,u,¬u)(paraguas los dos primeros días y el tercero no).Calculemos la secuencia de estados más probable, conesas percepciones (los estados son s1 = l y s2 = ¬l)• Paso final:

• El estado que da la probabilidad máxima en t = 3 es s2,con probabilidad 0.06804

• Reconstruimos el camino hasta s1:pr3(s2) = s1, pr2(s1) = s1

• Luego la secuencia de estados más probable es(s1, s1, s2) (es decir, los dos primeros días con lluviay el tercero no)


El problema de los números muy bajos

• Problema en los dos algoritmos que hemos visto:• A medida que aumenta el número de percepciones, tanto

los αk (sj) como los νk (sj) son números cada vez máscercanos a cero

• Para evitar esto en el algoritmo de avance, es usual queen cada paso, se aplique normalización de los αk (sj)

• ¿Cambia esto el resultado en el algoritmo de avance?• Estaríamos calculando en cada paso t las probabilidades

de filtrado P(Xk = sj |o1 · · · ok ) (en lugar deP(Xk = sj ,o1 · · · ok ))

• Si quisieramos saber, la probabilidad P(o1 · · · ot), ésta secalcularía como la inversa del producto de los factores denormalización usados en cada paso (¿por qué?)


El problema de los números muy bajos en Viterbi

• En el algoritmo de Viterbi también podríamos usarnormalización (y no cambiaría el resultado final)

• Sin embargo, puesto que no realiza sumas, es usual tratareste problema mediante el uso de logaritmos(log-probabilidades)

• Si se toman logaritmos, los productos que realiza elalgoritmo se transforman en sumas

• Esto no afecta al cálculo de los máximos, ya que ellogaritmo es una función creciente

• Nótese que las log-probabilidades de las tablas detransición y de las de percepción se pueden calcular alprincipio


Algoritmo de Viterbi (log-modificado)


• Salida:• La secuencia de estados Q que maximiza P(Q|O)

• Procedimiento:• Inicio: Para i = 1, . . . ,n, hacer ν̂1(si) = log(bi(o1)) + log(πi)

y pr1(si) = null ,• Para k desde 2 a t :

• Para j desde 1 a n:• Hacer ν̂k (sj) = log(bj(ot)) + max

i=1,...,n(log(aij) + ν̂k−1(si))

• Hacer prk (sj) = argmaxi=1,...,n

(log(aij) + ν̂k−1(si))

• Hacer s = argmaxi=1,...,n

ν̂t(si)

• Devolver la secuencia de estados que lleva hasta s(siguiendo hacia atrás los punteros, comenzando en prt(s))


Aprendizaje de MOMs

• El tercer problema importante en MOMs es el aprendizaje:• Conocemos el número de posibles estados y de

percepciones, pero no conocemos ni las probabilidades detransición ni de percepción.

• Sólo tenemos una secuencia de percepciones o1 · · · ot ,usualmente con t muy grande.

• El algoritmo que se usa para este tipo de problema es eldenominado algoritmo de Baum-Welch• Es un algoritmo de tipo EM

• Otra posibilidad es hacer una aprendizaje ML• Sólo es válido si también tenemos la secuencia de estados

correspondiente a las percepciones q1 · · · qt


Aprendizaje ML

• πi = P(X1 = si) =Lsi∑

1≤k≤n

Lsk

siendo Lsk el número de

veces que el estado inicial es sk .

• aij = P(Xt = sj |Xt−1 = si) =Nsi sj∑

1≤k≤n

Nsi sk

siendo Nsi sk el

número de veces que el estado sk sigue al estado si

• bi(vj) = P(Et = vj |Xt = si) =Msi vj∑

1≤k≤m

Msi vk

siendo Msi vk el

número de veces que el estado es si y se observa vk (enla misma posición)


Estimación para ejemplo 1Conocemos las secuencias de percepciones y estados:

f f f f f c f c c1 2 1 1 2 3 2 3 3

c f f c c c c c c2 2 1 1 2 3 2 2 3

f f f f f f c c c2 1 3 2 1 1 2 3 2

Calculamos las frecuencias y estimamos las probabilidades

Lf = 2,Lc = 1πf = 2/3, πc = 1/3

N f cf 10 4c 2 8

A f cf 5/7 2/7c 1/5 4/5

M 1 2 3f 7 4 1c 1 6 6

B 1 2 3f 7/12 1/3 1/12c 1/13 6/13 6/13


Algoritmo tipo EM

• Inicio: Parámetros iniciales del modelo estadístico• Paso E: Calcular ciertos valores esperados a partir de los

parámetros del modelo• Paso M: Estimar los parámetros del modelo a partir de los

valores esperados anteriores.• Repetir los dos pasos anteriores hasta algún criterio de

convergencia (o limitando el número de veces)


Algoritmo Baum-Welch

• Entrada:• Un modelo oculto de Markov, λ = (π,A,B)• Una secuencia de percepciones O = o1 · · · ot

• Salida:• Un modelo oculto de Markov, λ′ tal que P(O|λ′) ≥ P(O|λ)

• Procedimiento:• Repetir hasta un determinado criterio de convergencia:

• λ′ = λ• Paso Expectation• Paso Maximization (que da lugar a un modelo λ)


Algoritmo Baum-Welch: Paso E

Calculamos los valores de las probabilidades de lastransiciones y los estados (conocida una secuencia depercepciones)

• ξk (i , j) = P(Xk = si ,Xk+1 = sj |o1 · · · ot)

ξk (i, j) =P(Xk = si , Xk+1 = sj , o1 · · · ot )

P(o1 · · · ot )

=P(Xk = si , o1 · · · ok )P(Xk+1 = sj , ok+1 · · · ot |Xk = si , o1 · · · ok )

P(o1 · · · ot )

=αk (si )P(Xk+1 = sj , ok+1|Xk = si , o1 · · · ok )P(ok+2 · · · ot |Xk+1 = sj , Xk = si , o1 · · · ok+1)∑

1≤i≤n

αt (si )

=αk (si )P(Xk+1 = sj , ok+1|Xk = si )P(ok+2 · · · ot |Xk+1 = sj )∑

1≤i≤n

αt (si )

=αk (si )P(Xk+1 = sj |Xk = si )P(ok+1|Xk+1 = sj , Xk = si )βk+1(sj )∑

1≤i≤n

αt (si )=αk (si )aij bj (ok+1)βk+1(sj )∑

1≤i≤n

αt (si )


Algoritmo Baum-Welch: Paso E

Calculamos los valores de las probabilidades de lastransiciones y los estados (conocida una secuencia depercepciones)

• γk (i) = P(Xk = si |o1 · · · ot)

γk (i) =P(Xk = si ,o1 · · · ot)

P(o1 · · · ot)=αk (si)βk (si)∑1≤i≤n

αt(si)


Algoritmo Baum-Welch: Paso M

Estimamos los parámetros del modelo:• πi = γ1(i)

• aij =

∑1≤k≤t

ξk (i, j)∑1≤k≤t

γk (i)

• bi(vj) =

∑1≤k≤t∧ok=vj

γk (i)∑1≤k≤t

γk (i)

Baum et al. demostraron que si a partir de un modeloλ′ = (π′,A′,B′) calculamos el modelo λ utilizando elprocedimiento anterior (pasos E y M) entonces se tiene que:• o bien, λ = λ′

• o bien, P(O|λ) > P(O|λ′)


Bibliografía

• Jurafsky, D. y Martin, J.H. Speech and LanguageProcessing (Second Edition) (Prentice-Hall, 2009)• Cap. 6: “Hidden Markov and Maximum Entropy Models ”

• Russell, S. y Norvig, P. Artificial Intelligence (A modernapproach) (Third edition) (Prentice Hall, 2009)• Cap. 15 (hasta 15.3): “Probabilistic reasoning over time”

• Russell, S. y Norvig, P. Inteligencia Artificial (Un enfoquemoderno) (Segunda edición) (Pearson Educación, 2004)• Cap. 15 (hasta 15.3): “Razonamiento probabilista en el

tiempo”

Documents

Modelos Ocultos de Markov - us