´ Aprendizaje y Percepcion ´ Facultad de Informatica ´ Universidad Politecnica de Valencia

Tema 8: ´ ´ Metodos Sintactico/Estructurales: Modelos de Markov Alfons Juan, Enrique Vidal, Roberto Paredes, Jorge Civera

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

´Indice ◦ 1 Introduccion: .2 ´ ejemplos de modelado sintactico ´ .6 ´ ´ ´ 2 Gramaticas, automatas y lenguajes estocasticos ´ sintactico-estad´ ´ 3 Clasificacion ıstica . 12 4 Modelos de Markov . 17 5 Algoritmo de Viterbi . 28 ´ de 6 Aprendizaje: estimacion probabilidades en modelos de Markov . 33

DSIC – UPV: Enero, 2013

´ Pagina 8.1

APP-Tema8

Modelos de Markov

Secuencias de trazos y su modelado gramatical MODELADO SINTÁCTICO DEL TRAZADO DE UN "3"

2

3 4

S D1 H1 D2 H2 V1 H3 D3

H1

1

D1

D2

0

H2 V1

5

0

"1"

D3

7

6

H3

"0"

"0"

"5" "5"

1

--> D1 H1 D2 H2 V1 H3 D3 --> "1" | λ --> "0" | "0" H1 --> "5" | "5" D2 --> "0" | "0" H2 --> "6" | "6" V1 --> "4" | "4" H3 λ --> "3" |

"0" "0"

2

"4"

"6" "6"

3

"4"

4

"3"

5

6

"0" tres.gr

Trazados de treses generados por la gramática "tres.gr"

´ Pagina 8.2

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

´ Modelado sintactico de pronunciaciones de palabras aisladas Ejemplos de pronunciaciones de la palabra “ocho”, ´ representadas mediante cadenas acustico-fon eticas ´ TTTTTTOOEIOTTECEEOOOOTTTTTT TTTTTOOOEITTTECCEEOOOTTTTT TTTTTOOOETTTSCEOOOOTTTTTT TTTTTTOOOIOTTTCCEOOOOTTTTTT TTTTTTOOEIOTTSCCEOOOOTTTTTT TTTTTOOOEIETTECCIEOOOOTTTTTT TTTTTOOEOTTTCCIEOOOOTTTTTT TTTTTTOOOETTTECCEIEOOTTTTT TTTTTOOOEOTTSCCIEEOOTTTTTT TTTTTTOOOEOTTSCSCCIEEOOOTTTTTT TTTTTOOOEOTTECSCCEIOOOOTTTTT ......

E O

E E T

O

O

E E

~

T

T

T

T

T

O

C E

O

T

T

O

O

E

S O

O I

E

C

T

T

T

T

T

T

@

E

C

´ Automata finito aprendido a partir de los ejemplos DSIC – UPV: Enero, 2013

´ Pagina 8.3

APP-Tema8

Modelos de Markov

´ ´ Modelado sintactico de cadenas de Codigos de Contorno ´ Ejemplos de “ceros” codificados en cadenas de codigos de 8-direcciones 2

3

1

4

0

5

7

6

. . . . .

punto inicial (dirección antihoraria)

´ Un automata finito aprendido a partir de estos ejemplos (los dos estilos abierto/cerrado de trazado de “ceros” han quedado representados) 1 3 3

3 3 4 0

4

2

3

2

2

1

2 2

1 3

2

0

3

1

3 2

2

2

1

3

~

0

2

2

3

2

3

2

1

2

1

7

6

7

6

1

2

4

3

4

6

0

6

6

5

4

6

0

6

6

6

6

5

6

6

6 7

4

6

6

5

3

4

6

6

6

6

0 0

7

7

1

7

6

4

0

7

5

0

7

6

4

7

6 7

6

0

6

0

7

6 5

5

3 2

1 1

6

3

6 0

1

@

6

6 5

2

7 7

7

1 0

3

4

2 2

3

0

5 4

4

3

2 2

0

1

3

2

2

0

3

2 2

3

2

3

3

1

1

2

3

7

5 6

0

6 6

1

´ Pagina 8.4

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

´ Modelado sintactico de cromosomas Algunos ejemplos de cadenas de primitivas extraidas ´ de imagenes de cromosomas humanos de la clase 19 A=====Aa===E=XX==e===Aa=A===a=a A=A=a=Aa=====EXX==e===A=a=Aa=a A=A=a=====E=XX==e======A==a=a A=A=a====EXX==e===A==a==Aa=a A=A===Aa===D=XX==e========A=a=a B=a==Aa===EXX==e====A=a==A==a=a A=Aa=Aa==E=XX===e=====A==a=a . . . . . e

E

a a

=

B

E

=

=

B

D

=

D

E

~ A

=

=

A

= =

=

B

=

=

a

=

=

E

D

X

E

c =

E

=

=

b A

= e

D A

=

a

d

= X

A

A a

E A

A

b

A

a =

b

=

=

=

A

a

a

=

a

a

A

=

= =

=

=

=

b

=

=

a

@

= b

b

a A

A

a

´ Un automata finito aprendido a partir de estos ejemplos

DSIC – UPV: Enero, 2013

´ Pagina 8.5

APP-Tema8

Modelos de Markov

´Indice .2 ´ ejemplos de modelado sintactico ´ 1 Introduccion: ◦ 2 Gramaticas, .6 ´ ´ ´ automatas y lenguajes estocasticos ´ sintactico-estad´ ´ 3 Clasificacion ıstica . 12 4 Modelos de Markov . 17 5 Algoritmo de Viterbi . 28 ´ de 6 Aprendizaje: estimacion probabilidades en modelos de Markov . 33

´ Pagina 8.6

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

´ Gramaticas Monoide Libre Σ∗: Dado un conjunto finito Σ, Σ+ es el conjunto de ´ todas las cadenas de longitud finita formadas por elementos de Σ. Ademas, ∗ + Σ = Σ ∪ {λ} (la cadena vacia). ´ Gramatica: G = (N, Σ, R, S) • N : Conjunto finito de No-Terminales

• Σ: Conjunto finito de Terminales o Primitivas

• S ∈ N : S´ımbolo No-Terminal inicial o .Axioma”

• R ⊂ (N ∪ Σ)∗N (N ∪ Σ)∗ × (N ∪ Σ)∗: conjunto de Reglas. A regla se escribe como: α → β,

α ∈ (N ∪ Σ)∗N (N ∪ Σ)∗, β ∈ (N ∪ Σ)∗

Si varias reglas comparten su parte izquierda, pueden abreviarse como: α → β1 | β2 | · · ·

DSIC – UPV: Enero, 2013

´ Pagina 8.7

APP-Tema8

Modelos de Markov

´ Gramaticas y lenguajes ´ Elemental : =⇒: Derivacion G

sii ∃(α → β) ∈ R, µ, δ ∈ (N ∪ Σ)∗

µ α δ =⇒ µ β δ G

∗

´ =⇒: Derivacion G

´ d puede Es una secuencia finita de derivaciones elementales. Una derivacion escribirse como la secuencia correspondiente de reglas de G. ∗

El conjunto de derivaciones de y ∈ Σ∗ (tales que S =⇒ y) se denota como DG(y). G

´ Una gramatica G es ambigua si ∃y ∈ Σ tal que |DG(y)| > 1 ∗

´ Lenguaje generado por una gramatica G, L(G): ∗

L(G) = { y ∈ Σ∗ | S =⇒ y } G

´ Pagina 8.8

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

´ Tipos de gramaticas y lenguajes J ERARQU´I A DE C HOMSKY PARA LENGUAJES RECURSIVOS 0: No-restringidos 1: Contextuales α→β,

|α| ≤ |β|

2: Incontextuales B→β,

B∈N

3: Regulares o de “Estados-Finitos” A → aB o A → a ,

DSIC – UPV: Enero, 2013

A, B ∈ N, a ∈ Σ ∪ {λ}

´ Pagina 8.9

APP-Tema8

Modelos de Markov

´ ´ Gramaticas regulares y automatas finitos ´ Gramaticas Regulares: G = (N, Σ, R, S), Reglas de R de la forma: A → aB ∨ A → a, A, B ∈ N, a ∈ Σ ´ Automatas Finitos: A = (Q, Σ, δ, q0, F ),

q0 ∈ Q, F ⊆ Q, δ : Q × Σ → 2Q

´ ´ Equivalencia: Para cada Gramatica Regular existe un Automatas Finito que reconoce el mismo lenguaje. (¡Ojo: la inversa no es siempre cierta en el caso de ´ lenguajes estocasticos!). Ejemplo: G = (N, Σ, R, S); Σ = {a, b}; N = {S, A1, A2}; R = { S → aA1 | bA2 | b, A1 → aA1 | bA2 | b, A2 → bA2 | b}

0 a

b b 1

A = {Q, Σ, δ, q0, F }; Q = {0, 1, 2}, Σ = {a, b}, q0 = 0, F = {2}

2 b

a

L(G) = {b, ab, bb, aab, abb, bbb, . . . , aaabbbb, . . .} = L(A) ´ Pagina 8.10

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

´ ´ ´ Gramaticas y automatas estocasticos ´ ´ ´ Una Gramatica Estocastica G0 es una gramatica G con probabilidades asociadas a sus reglas: G0 = (G, p),

G = (N, Σ, R, S), p : R → [0, 1]

´ Una gramatica incontextual (o regular ) es propia si: X ∀A ∈ N p(A → β) = 1 A→β∈R

Probabilidad de una cadena y generada por G0: X ∀y ∈ Σ∗ p(y|G0) = p(d), p(d) = d∈DG (y)

Y

(A→β)∈d

p(A → β)

´ ´ Una gramatica Estocastica G0 es consistente si: X p(y|G0) = 1 y∈Σ∗

DSIC – UPV: Enero, 2013

´ Pagina 8.11

APP-Tema8

Modelos de Markov

´Indice .2 ´ ejemplos de modelado sintactico ´ 1 Introduccion: .6 ´ ´ ´ 2 Gramaticas, automatas y lenguajes estocasticos ◦ 3 Clasificacion ´ sintactico-estad´ ´ ıstica . 12 4 Modelos de Markov . 17 5 Algoritmo de Viterbi . 28 ´ de 6 Aprendizaje: estimacion probabilidades en modelos de Markov . 33

´ Pagina 8.12

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

´ sintactico-estad´ ´ Clasificacion ıstica Suponemos C clases de objetos, representados como cadenas de Σ+. ´ estad´ıstica en el caso vectorial: Planteamiento similar al de la clasificacion Probabilidad a priori de una clase c: P (c), 1 ≤ c ≤ C ´ de probabilProbabilidad condicional de la clase c: P (y | Gc), funcion ´ de las cadenas de c en Σ∗. idad que modela la distribucion Probabilidad a posteriori de la clase c: P (c | y) P (c | y) =

P (y | Gc)P (c) P (y)

donde P (y) =

C X

c0 =1

P (y | Gc0 )P (c0)

´ Regla de clasificacion: Una cadena y ∈ Σ+ se asigna a la clase cˆ: cˆ = argmax P (c | y) 1≤c≤C

DSIC – UPV: Enero, 2013

´ Pagina 8.13

APP-Tema8

Modelos de Markov

Aprendizaje ´ de las reglas o “topolog´ıa” : Determinacion ´ “Manual”: topolog´ıa ergodica, izquierda-derecha, etc. ⇒ Modelos de Markov ´ Automatica: Inferencia Gramatical ´ Aprendizaje de las probabilidades: estimacion

´ Pagina 8.14

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

´ de las probabilidades de modelos sintacticos ´ Estimacion ´ Gramaticas incontextuales (o Regulares) No-ambiguas G0: ´ por maxima ´ Estimacion verosimilitud a partir de las frecuencias de ´ uso de las reglas en el analisis de una secuencia de cadenas de entrenamiento supuestamente generadas por G0. Estas estimaciones se aproximan a las verdaderas probabilidades cuando el numero de cadenas de entrenamiento → ∞. ´ ´ Gramaticas Regulares ambiguas y/o modelos de Markov: ´ localmente optima ´ ´ por Viterbi” Estimacion mediante “reestimacion o, mejor, mediante el algoritmo “Backward-Forward”

DSIC – UPV: Enero, 2013

´ Pagina 8.15

APP-Tema8

Modelos de Markov

´ PAGINA INTENCIONADAMENTE EN BLANCO

´ Pagina 8.16

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

´Indice .2 ´ ejemplos de modelado sintactico ´ 1 Introduccion: .6 ´ ´ ´ 2 Gramaticas, automatas y lenguajes estocasticos ´ sintactico-estad´ ´ 3 Clasificacion ıstica . 12 ◦ 4 Modelos de Markov . 17 5 Algoritmo de Viterbi . 28 ´ de 6 Aprendizaje: estimacion probabilidades en modelos de Markov . 33

DSIC – UPV: Enero, 2013

´ Pagina 8.17

APP-Tema8

Modelos de Markov

Modelos de Markov Un modelo de Markov es una qu´ıntupla M = (Q, Σ, π, A, B) donde: Q es un conjunto de estados • En cada instante t = 1, 2, . . . , M esta´ en uno de sus estados, denotado qt • Q incluye un estado final F Σ es un conjunto de s´ımbolos “observables” En cada instante t = 1, 2, . . . , M emite un s´ımbolo, que se denota con yt π ∈ RQ es un vector de probabilidades iniciales: M elije q1 segun ´ π ´ (entre estados): A ∈ RQ×Q es una matriz de probabilidades de transicion ´ M elije qt+1 basandose en qt y A: Aq,q0 = P (qt+1 = q 0|qt = q, A) ´ (de s´ımbolos): B ∈ RQ×Σ es una matriz de probabilidades de emision ´ M elije yt basandose en qt y B: Bq,σ = P (yt = σ | qt = q, B)

´ Pagina 8.18

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

Modelos de Markov (cont.) ´ para π, A, B: Condiciones de normalizacion Probabilidad de estado inicial: P 0 ≤ πq ≤ 1, q∈Q πq = 1, πF = 0

´ entre estados: Probabilidades de Transicion P 0 ≤ Aq,q0 ≤ 1, q 0 ∈Q Aq,q 0 = 1, AF,q = 0 ´ de observables: Probabilidades de emision P 0 ≤ Bq,σ ≤ 1, σ∈Σ Bq,σ = 1, BF,σ = 0

DSIC – UPV: Enero, 2013

´ Pagina 8.19

APP-Tema8

Modelos de Markov

Modelos de Markov: ejemplo Σ = {a,b,c};

Q={1,2,3,F};

p(q’|q) A(q,q’)

π 1 = 1;

1 2 3 F 1 0.2 0.5 0.3 0.0 2 0.1 0.0 0.9 0.0 3 0.0 0.0 0.4 0.6

π 2 = π 3 = πF = 0

a b c 1 0.0 0.3 0.7 2 0.3 0.6 0.1 3 1.0 0.0 0.0

p(σ |q) B(q,σ )

Representación Gráfica Equivalente: 0.0 0.3 0.7 Inic

1

1 0.2

0.1

0.3 0.6 0.1

0.5

2

1.0 0.0 0.0 0.9

0.3

3

0.6

F

0.4 ´ Pagina 8.20

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

Proceso Markoviano generador de cadenas Sea M = (Q, Σ, π, A, B) un modelo de Markov con estado final qF 1. Elegir un estado inicial q ∈ Q segun ´ P (q) ≡ πq

´ σ ∈ Σ segun 2. Seleccionar una observacion ´ P (σ|q) ≡ Bq,σ ; emitir σ

3. Elegir un estado siguiente q 0 ∈ Q segun ´ P (q 0|q) ≡ Aq,q0

4. Si q = qF terminar ; sino, ir a paso 2 Sean:

y = y1, y2, . . . , ym ∈ Σ+: secuencia de observaciones producida por M z = q1, q2, qm, . . . , qF ∈ Q+: secuencia de estados que genera a y La probabilidad de que M produzca y mediante z es: P (y, z) = P (z) · P (y | z) = P (q1) DSIC – UPV: Enero, 2013

m Y

t=2

P (qt | qt−1) P (qF | qm) ·

m Y

t=1

P (yt | qt) ´ Pagina 8.21

APP-Tema8

Modelos de Markov

Probabilidad de generar una cadena con un modelo de Markov Probabilidad de que M genere la cadena y = y1 . . . ym ∈ Σ+: P (y | M ) = =

X

P (q1)

q1 ,...,qm ∈Q+

=

X

m Y

t=2

Se cumple:

P (y, z)

z∈Q+

P (qt | qt−1) P (qF | qm) ·

πq1 Bq1,y1

q1 ,...,qm ∈Q+

X

m Y

Aqt−1,qt Bqt,yt

t=2

0 ≤ P (y|M ) ≤ 1,

X

m Y

t=1

!

P (yt | qt)

Aqm,qF

P (y|M ) = 1

y∈Σ+

´ Pagina 8.22

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

Probabilidades calculadas con el modelo del ejemplo P (cba|M ) = (π1 · B1,c) (A1,2 · B2,b) (A2,3 · B3,a) A3,F + (π1 · B1,c) (A1,1 · B1,b) (A1,3 · B3,a) A3,F = (1 · 0.7) (0.5 · 0.6) (0.9 · 1) 0.6 + (1 · 0.7) (0.2 · 0.3) (0.3 · 1) 0.6

= 0.1134 + 0.00756 ≈ 0.12

P (bcbaa|M ) = P (y, z1) + P (y, z2) + P (y, z3) + P (y, z4) + P (y, z5) y= z1 = P (y, z1) = z2 = P (y, z2) = z3 = P (y, z3) = z4 = P (y, z4) = z5 = P (y, z5) =

b 1 (1 · 0.3) 1 (1 · 0.3) 1 (1 · 0.3) 1 (1 · 0.3) 1 (1 · 0.3)

c 1 (0.2 · 0.7) 1 (0.2 · 0.7) 1 (0.2 · 0.7) 2 (0.5 · 0.1) 2 (0.5 · 0.1)

b a 1 2 (0.2 · 0.3) (0.5 · 0.3) 1 3 (0.2 · 0.3) (0.3 · 1) 2 3 (0.5 · 0.6) (0.9 · 1) 1 2 (0.1 · 0.3) (0.5 · 0.3) 1 3 (0.1 · 0.3) (0.3 · 1)

a 3 (0.9 · 1) 3 (0.4 · 1) 3 (0.4 · 1) 3 (0.9 · 1) 3 (0.4 · 1)

F 0.6 F 0.6 F 0.6 F 0.6 F 0.6

= 0.000204 = 0.000181 = 0.002722 = 0.000036 = 0.000032

P (y|M ) = 0.003175 DSIC – UPV: Enero, 2013

´ Pagina 8.23

APP-Tema8

Modelos de Markov

Equivalencia entre modelos de Markov y ´ ´ gramaticas regulares estocasticas ´ ´ Dado un modelo de Markov M , existe una gramatica regular estocastica G tal que P (y|M ) = P (y|G) ∀y ∈ Σ∗ ´ ´ Se demuestra facilmente por construccion.

´ ´ Dada una gramatica regular estocastica G, existe un modelo de Markov M tal que P (y|M ) = P (y|G) ∀y ∈ Σ∗ (salvo casos degenerados) ´ (algo mas ´ compleja que la anterior). Se demuestra por construccion

´ Pagina 8.24

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

Equivalencia entre modelos de Markov ´ ´ y gramaticas estocasticas 0.0 0.3 0.7 1

Inic

1

0.1 0.5

c,0.07

b,0.3 c,0.7 b,0.06 0.3: S -> bX 0.7: S -> cX

DSIC – UPV: Enero, 2013

2

a,0.15

X

1.0 0.0 0.0 0.9

0.3

0.2

S

0.3 0.6 0.1

b,0.3

c,0.14 0.06: X -> bX 0.14: X -> cX 0.15: X -> aY 0.30: X -> bY 0.05: X -> cY 0.30: X -> aZ

3

0.6

F

0.4 b,0.03

Y

a,0.9

Z

λ, 0.6

c,0.05 a,0.3 0.90: Y -> aZ 0.03: Y -> bX 0.07: Y -> cX

a,0.4 0.4: Z -> aZ 0.6: Z -> λ

´ Pagina 8.25

APP-Tema8

Modelos de Markov

Estructura o “topolog´ıa” de un modelo de Markov La Topolog´ıa de un Modelo de Markov: es la forma del grafo subyacente. ´ de ceros) de Viene determinada por la estructura (numero y ubicacion ´ ´ entre estados A. Topolog´ıas mas ´ comunes: la matriz de transicion ´ Ergodica: grafo completo, no hay ceros en A. Izquierda-derecha: el grafo es dirigido y ac´ıclico (DAG), aunque pueden haber bucles individuales en los estados. A es triangular. Lineal: el grafo es un DAG (con posibles bucles en estados) restringi´ ´ do en el que las transiciones que salen del estado i−esimo solo pueden alcanzar a los estados i + 1, . . . , i + k. Los elemetos no nulos ´ en k + 1 diagonales adyacentes. Estas transiciones se de A estan denominan “saltos” o “skips”. ´ de estados, Estrictamente Lineal: el grafo es una concatenacion ´ (con posibles bucles en estados). Los elemetos no nulos de A estan en dos diagonales adyacentes.

´ Pagina 8.26

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

Ejemplos de topolog´ıas de modelos de Markov 2

´ Ergodica

1

3

3

Izquierda-Derecha

2

5

1 4

Lineal

1

2

3

4

5

Estrictamente Lineal

1

2

3

4

5

DSIC – UPV: Enero, 2013

´ Pagina 8.27

APP-Tema8

Modelos de Markov

´Indice .2 ´ ejemplos de modelado sintactico ´ 1 Introduccion: .6 ´ ´ ´ 2 Gramaticas, automatas y lenguajes estocasticos ´ sintactico-estad´ ´ 3 Clasificacion ıstica . 12 4 Modelos de Markov . 17 ◦ 5 Algoritmo de Viterbi . 28 ´ de 6 Aprendizaje: estimacion probabilidades en modelos de Markov . 33

´ Pagina 8.28

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

´ de Viterbi a P (y | M ) Aproximacion Dado un modelo de Markov M = (Q, Σ, π, A, B) con estado final F , y una cadena y = y1 · · · ym ∈ Σ+, la probabilidad de que M genere y es: X X P (y | M ) = P (y, z) = P (y, q1, . . . , qm) z∈Q+

q1 ,...,qm ∈Q+

´ a P (y | M ) es la llamada aproximacion ´ de Viterbi: Una aproximacion P˜ (y | M ) =

max

q1 ,...,qm ∈Q+

P (y, q1, . . . , qm)

´ probable es: La correspondiente secuencia de estados mas q˜ = (˜ q1, . . . , q˜m) = argmax P (y, q1, . . . , qm) q1 ,...,qm ∈Q+

DSIC – UPV: Enero, 2013

´ Pagina 8.29

APP-Tema8

Modelos de Markov

Algoritmo de Viterbi ´ Definimos V (q, t) como la probabilidad maxima de que un modelo de Markov M alcance el estado q en el instante t, emitiendo el prefijo y1 . . . yt : V (q, t) = qmax P (y1 · · · yt, q1, . . . , qt) ,...,q 1

qt =q

t

V (q, t) puede calcularse recursivamente: V (q, t) = q ,...,q max 1

t−1 ,qt 0

qt−1 =q qt =q

= max 0 q ∈Q

P (y1 · · · yt−1, q1, . . . , qt−1) · Aq0,q Bq,yt

max P (y1 · · · yt−1, q1, . . . , qt−1) · Aq0,q Bq,yt

q1 ,...,qt−1 qt−1 =q 0

= max V (q 0, t − 1) · Aq0,q Bq,yt 0 q ∈Q

En general:

V (q, t) =

  πq Bq,y

1

V (q , t − 1) Aq0,q Bq,yt  max 0 q ∈Q

DSIC – UPV: Enero, 2013

0

APP-Tema8

si t = 1 si t > 1 ´ Pagina 8.30

Modelos de Markov

Algoritmo de Viterbi (cont.) ´ de Viterbi a P (y | M ): Aproximacion P˜ (y | M ) = max V (q, |y|) Aq,F q∈Q

´ V puede representarse como una matriz: Vq,t ≡ V (q, t). La funcion Esta matriz define un grafo multietapa denominado trellis y permite ´ ´ Dinamica. ´ el calculo iterativo eficiente de V (q, |y|) por Programacion ´ La correspondiente secuencia optima de estados, q˜, se calcula ´ recorriendo el trellis hacia atras.

DSIC – UPV: Enero, 2013

´ Pagina 8.31

APP-Tema8

Modelos de Markov

Algoritmo de Viterbi: ejemplo

x

c

.3

1

0.2·0.7

0.5 0.3 0.6 0.1

0.3 2

0.1

0.2·0.3

a

a

0

0 0

.0025

0

0.1·0.3

0

0

0.1·0.7 0.5·0.1

0.5·0.6

0 0.5·0.3

.015

.0126

.0004

0

0.9 3

.042

0

0.4 1.0 0.0 0.0

b

1·0.3

1

0.2

b

1

Inic

0.0 0.3 0.7

=

0

0

0.9·1 0.4·1

0 0.5·.3

0

0.3·1

0 0 0

0

0.3·1 0.9·1 0.4·1

.0113

.0045 0.6

0.6 F

.0027

´ Pagina 8.32

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

´Indice .2 ´ ejemplos de modelado sintactico ´ 1 Introduccion: .6 ´ ´ ´ 2 Gramaticas, automatas y lenguajes estocasticos ´ sintactico-estad´ ´ 3 Clasificacion ıstica . 12 4 Modelos de Markov . 17 5 Algoritmo de Viterbi . 28 ◦ 6 Aprendizaje: estimacion ´ de

probabilidades en modelos de Markov . 33

DSIC – UPV: Enero, 2013

´ Pagina 8.33

APP-Tema8

Modelos de Markov

´ de probabilidades de un modelo de Markov: Estimacion criterio a optimizar ´ Problema basico: Estimar las probabilidades de un modelo de Markov, M , mediante una secuencia de cadenas de entrenamiento Y = {y1, . . . , yn} extraidas independientemente de acuerdo con la ley de probabilidad P (y|M ). Como las cadenas se han extra´ıdo independientemente: P (Y |M ) =

n Y

k=1

P (yk |M )

´ El estimador de maxima verosimilitud de M es: ˆ = argmax M M

n Y

k=1

P (yk |M ) ≈ argmax M

n Y

k=1

P˜ (yk |M )

´ Pagina 8.34

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

´ mediante el algoritmo de Viterbi Estimacion ´ Idea basica: Analizar todas las cadenas Y , contabilizando las frecuencias de uso de las transi´ de s´ımbolos en cada estado, etc. y normalizar ciones entre estados, de generacion adecuadamente. Problema: ´ ¿Como analizar las cadenas si no se conocen las probabilidades de del modelo? ´ Una posible solucion: 1. Inicializar las probabilidades “adecuadamente” 2. Analizar cada cadena de Y mediante el algoritmo de Viterbi y obtener la secuencia de estados correspondiente 3. A partir de esta secuencia de estados, contabilizar las frecuencias requeridas. 4. Normalizar las frecuencias para obtener nuevas probabilidades del modelo 5. Repetir pasos 2-4 hasta convergencia. DSIC – UPV: Enero, 2013

´ Pagina 8.35

APP-Tema8

Modelos de Markov

´ por Viterbi: ejemplo Re-estimacion Se dispone de tres cadenas de contorno de 4-direcciones que representan tres d´ıgitos “siete” manuscritos1. A partir de estas cadenas se desea re-estimar las probabilidades de un modelo de Markov para estos d´ıgitos. Utilizando el algoritmo de Viterbi se han obtenido las ´ siguientes secuencias optimas de estados para cada cadena:

1

Cadena: ´ Secuencia optima de estados:

aaaaaddcdcdcdcdccbabaabababccccb 11111222222222222333333333344444F

Cadena: ´ Secuencia optima de estados:

aaaaaddcdcdcdccdcbabababaabcccdcbb 1111122222222222233333333334444444F

Cadena: ´ Secuencia optima de estados:

aaaadcdcdcdcdcdcbababababccdccbaab 1111222222222222333333333444444444F

Para mayor claridad se representan los trazos horizontales como 0=a, 2=c y los verticales como 1=b, 3=d. ´ Pagina 8.36

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

´ por Viterbi (cont.) Ejemplo de re-estimacion π1 = 3/3 = 1 π2 = π3 = π4 = 0 A

1

2

3

4

F

1

4+4+3

1+1+1

0

0

0

⇒

A

1

2

3

4

F

1

11 14

3 14 33 36

0

0

0

0

0

3 29 18 21

0

3

0

0

9+9+8

1+1+1

0

3

0

0

3 36 26 29

4

0

0

0

4+6+8

1+1+1

4

0

0

0

2

0

11 + 11 + 11

B

a

1+1+1

b

0

c

0

d

a

b

c

d

1

14 14

0

0

0

2

0

0

18 36

18 36

14 29 2 21

15 29 5 21

0

0

12 21

2 21

5+5+4

0

0

0

2

0

0

6+6+6

6+6+6

3

5+5+4

5+5+5

0

0

3

4

0+0+2

1+2+2

4+4+4

0+1+1

4

DSIC – UPV: Enero, 2013

0

B

1

⇒

2

3 21

´ Pagina 8.37

APP-Tema8

Modelos de Markov

´ por Viterbi Algoritmo de reestimacion Input: M 0 = (Q0, Σ0, π 0, A0, B 0) Y = {y1, . . . , yn} Output: M = (Q, Σ, π, A, B)

/* Modelo inicial */ /* cadenas de entrenamiento */ /* Modelo optimizado */

M = M0 repeat M 0 = M ; π = 0; A = 0; B = 0 for k = 1 to n do m = |yk | /* secuencia de estados m´as probable para yk , */ q˜1, . . . , q˜m = argmaxq1,...,qm P (yk , q1, . . . , qm | M 0) /* por Viterbi */

πq˜1 ++; Bq˜1,yk,1 ++ /* actualizaci´on de contadores */ for t = 2 to m do Aq˜t−1,˜qt ++; Bq˜t,yk,t ++ done; Aq˜m,F ++ done P s = q∈Q πq forall q ∈ Q do /* normalizaci´on de contadores */ πq = πq /s P a = q0∈Q Aq,q0 ; forall q 0 ∈ Q do Aq,q0 = Aq,q0 /a P b = σ∈Σ Bq,σ ; forall σ ∈ Σ do Bq,σ = Bq,σ /b done until M = M 0 ´ Pagina 8.38

DSIC – UPV: Enero, 2013

APP-Tema8

Modelos de Markov

´ de la re-estimacion ´ por Viterbi Inicializacion Una idea elemental: Inicializar todas las probabilidades segun ´ distribuciones equiprobables. ´ Problema: Suele producir problemas de convergencia o convergencia a maximos locales inadecuados. Una idea util ´ para modelos lineales: Segmentar cada cadena de Y en tantos segmentos de (aproximadamente) la misma longitud como estados tenga el modelo de Markov. Asignar los s´ımbolos de cada segmento a su correspondiente estado ´ y transicion ´ Contabilizar las frecuencias de generacion Normalizar las frecuencias para obtener probabilidades iniciales requeridas

DSIC – UPV: Enero, 2013

´ Pagina 8.39

APP-Tema8

Modelos de Markov

´ por segmentacion ´ lineal: Ejemplo Inicializacion Obtener un modelo de Markov de N = 3 estados mediante ´ lineal a partir de las cadenas segmentacion y1 = aabbbcc

y2 = aaabbccc

Q = {1, 2, 3, F }

Σ = {a, b, c}

j t·N k aabbbcc : q= 1122233 | y | +1 π1 = 22 ,

aaabbccc 11222333

π2 = π3 = 0

A 1 2 3 F

B

a

b

2 4 4 6

0 0

1 2 3

2 4

0

0 0

c

0

0

1

2 6 3 5

0

2

4 4 1 6

5 6

0

2 5

3

0 0

5 5

DSIC – UPV: Enero, 2013

APP-Tema8

´ Pagina 8.40

Modelos de Markov

´ por segmentacion ´ lineal para reestimacion ´ por Viterbi Inicializacion Input: Y = {y1, . . . , yn}, N /* cadenas de entrenamiento, n´umero de estados */ Output: M = (Q, Σ, π, A, B) /* modelo */ Q = {1, 2, . . . , N, F }; Σ = {y ∈ yk ∈ Y } π = 0; A = 0; B = 0

/* estados y s´ımbolos */ /* inicializaci´on de contadores */

for k = 1 to n do q = 1; πq ++; Bq,yk,1 ++

/* actualizaci´on de contadores por */ /* alineamiento lineal de yk con los estados */ j k t 0 for t = 2 to |yk | do q = q; q = |y |+1 N + 1; Aq0,q ++; Bq,yk,t ++ done k Aq,F ++ done P s = q∈Q πq

forall q ∈ Q do /* normalizaci´on de contadores */ πq = π q / s P a = q0∈Q Aq,q0 ; forall q 0 ∈ Q do Aq,q0 = Aq,q0 / a P b = σ∈Σ Bq,σ ; forall σ ∈ Σ do Bq,σ = Bq,σ / b done DSIC – UPV: Enero, 2013

´ Pagina 8.41