CSE Dept., CSE Dept., IIT Bombay

CS621: Artificial Intelligence

Pushpak Bhattacharyya

CSE Dept., CSE Dept., IIT Bombay

Lecture 35–HMM; Forward and Backward Probabilities

19 ^th Oct, 2010

HMM Definition

Set of states: S where |S|=N

Start state S

/*P(S

)=1*/

Output Alphabet: O where |O|=M

Transition Probabilities: A= {a

} /*state i to state j*/

ij

state j*/

Emission Probabilities : B= {b

(o

)} /*prob. of emitting or absorbing o

from state j*/

Initial State Probabilities: Π={p

,p

,p

,…p

}

Each p

=P(o

=ε,S

|S

)

Three basic problems (contd.)

Problem 1: Likelihood of a sequence

Forward Procedure

Backward Procedure

Backward Procedure

Problem 2: Best state sequence

Viterbi Algorithm

Problem 3: Re-estimation

Baum-Welch ( Forward-Backward

Algorithm )

Forward and Backward

Probability Calculation

Forward probability F(k,i)

Define F(k,i)= Probability of being in state S _i having seen o ₀ o ₁ o ₂ …o _k

F(k,i)=P(o ₀ o ₁ o ₂ …o _k , S _i )

With m as the length of the observed

With m as the length of the observed sequence

P(observed sequence)=P(o ₀ o ₁ o ₂ ..o _m )

=Σ _p=0,N P(o ₀ o ₁ o ₂ ..o _m , S _p )

=Σ _p=0,N F(m , p)

Forward probability ^(contd.)

F(k , q)

= P(o

o

o

..o

, S

)

= P(o

o

o

..o

, S

)

= P(o

o

o

..o

, o

,S

)

= Σ

P(o

o

o

..o

, S

, o

,S

)

= Σ

P(o

o

o

..o

, S

).

= Σ

P(o

o

o

..o

, S

).

P(o

,S

|o

o

o

..o

, S

)

= Σ

F(k-1,p). P(o

,S

|S

)

= Σ

F(k-1,p). P(S

S

)

ok

O

O

O

O

… O

O

… O

O

S

S

S

S

… S

S

… S

S

Backward probability B(k,i)

Define B(k,i)= Probability of seeing

o _k o _k+1 o _k+2 …o _m given that the state was S _i

B(k,i)=P(o _{k k k+1 k+2} o _k+1 o _k+2 …o _{m m} \ S _{i i} )

With m as the length of the observed sequence

P(observed sequence)=P(o ₀ o ₁ o ₂ ..o _m )

= P(o ₀ o ₁ o ₂ ..o _m | S ₀ )

=B(0,0)

Backward probability ^(contd.)

B(k , p)

= P(o

o

o

…o

\ S

)

= P(o

o

…o

, o

|S

)

= Σ

P(o

o

…o

, o

, S

|S

)

= Σ

P(o

,S

|S

)

P(o

o

…o

|o

,S

,S

)

= Σ

P(o

o

…o

|S

). P(o

, S

|S

)

= Σ

B(k+1,q). P(S

S

)

ok

O

O

O

O

… O

O

… O

O

S

S

S

S

… S

S

… S

S

Continuing with the Urn example

Urn 1 Urn 2 Urn 3

Colored Ball choosing

Urn 1

# of Red = 30

# of Green = 50

# of Blue = 20

Urn 3

# of Red =60

# of Green =10

# of Blue = 30 Urn 2

# of Red = 10

# of Green = 40

# of Blue = 50

Example (contd.)

U

U

U

U

0.1 0.4 0.5 U

0.6 0.2 0.2 U

0.3 0.4 0.3

Given :

Observation : RRGGBRGR

and

R G B

U

0.3 0.5 0.2 U

0.1 0.4 0.5 U

0.6 0.1 0.3

Transition Probability Observation/output Probability

Observation : RRGGBRGR

What is the corresponding state sequence ?

Diagrammatic representation (1/2)

U U

0.1

0.3 0.3

R, 0.6 B, 0.2

R, 0.3 G, 0.5

U1

U2

U3

0.1

0.2

0.4 0.6

0.4

0.5

0.2

R, 0.6 G, 0.1 B, 0.3

R, 0.1

B, 0.5 G, 0.4

Diagrammatic representation (2/2)

U ^R,0.15 U

R,0.18 G,0.03 B,0.09

R,0.18 R,0.03

G,0.05 B,0.02

U1

U2

U3

R,0.02 G,0.08 B,0.10

R,0.24 G,0.04 B,0.12 R,0.06

G,0.24 B,0.30 R, 0.08

G, 0.20 B, 0.12

R,0.15 G,0.25 B,0.10

R,0.18 G,0.03 B,0.09

R,0.02 G,0.08 B,0.10

Observations and states

O ¹ O ² O ³ O ⁴ O ⁵ O ⁶ O ⁷ O ⁸ OBS: R R G G B R G R State: S ¹ S ² S ³ S ⁴ S ⁵ S ⁶ S ⁷ S ⁸

S

= U

/U

/U

; A particular state S: State sequence

O: Observation sequence

S* = “best” possible state (urn) sequence

Goal: Maximize P(S*|O) by choosing “best” S

Grouping terms

P(S).P(O|S)

= [P(O

|S

).P(S

|S

)].

[P(O

|S

). P(S

|S

)].

We introduce the states S

and S

as initial and final states

O

O

O

O

O

O

O

O

O

Obs:

ε R R G G B R G R

State:

S

S

S

S

S

S

S

S

S

S

[P(O

|S

). P(S

|S

)].

[P(O

|S

). P(S

|S

)].

[P(O

|S

).P(S

|S

)].

[P(O

|S

).P(S

|S

)].

[P(O

|S

).P(S

|S

)].

[P(O

|S

).P(S

|S

)].

[P(O

|S

).P(S

|S

)].

[P(O

|S

).P(S

|S

)].

and final states respectively.

After S

the next state

is S

with probability

1, i.e., P(S

|S

)=1

O

is ε-transition

Introducing useful notation

S₀ S₁ S₇

S₂ S₃ S₄ S₅ S₆

O

O

O

O

O

O

O

O

O

Obs:

ε R R G G B R G R

State:

S

S

S

S

S

S

S

S

S

S

ε R R G G B R

S₀ S₁

S₈

S₉ S₂

G

R

P(O

|S

).P(S

|S

)=P(S

S

)

Ok

Viterbi Algorithm for the Urn problem (first two symbols)

S₀

U U U

0.5

0.3

0.2 ε

U₁ U₂ U₃

U₁ U₂ U₃

0.03

0.08

0.15

U₁ U₂ U₃ U₁ U₂ U₃

0.06

0.02

0.02

0.18

0.24

0.18

0.015 0.04 0.075* 0.018 0.006 0.006 0.048* 0.036

*: winner sequences R

Probabilistic FSM

(a₁:0.3)

(a₂:0.4)

(a₁:0.1) (a₁:0.3)

S

S

2 (a₁:0.2)

(a₂:0.3)

(a₂:0.2) (a₂:0.2)

The question here is:

“what is the most likely state sequence given the output sequence seen”

S

S

2

Developing the tree

Start

S1 S2

S1 S2 S1 S2

1.0 0.0

0.1 0.3 0.2 0.3

1*0.1=0.1 . 0.3 . 0.0 0.0

€

a

S1 S2 S1 S2

S1 S2 S1 S2

1*0.1=0.1 0.3 0.0 0.0

0.1*0.2=0.02 0.1*0.4=0.04 0.3*0.3=0.09 0.3*0.2=0.06

. .

a

Choose the winning sequence per state per iteration

0.2 0.4 0.3 0.2

Tree structure contd…

S1 S2

S1 S2 S1 S2

0.1 0.3 0.2 0.3

0.027 . 0.012 .

0.09 0.06

0.09*0.1=0.009 0.018

a

S1

0.3

0.0081

S2 0.2

0.0054

S2 0.4

0.0048 S1

0.2

0.0024

.

a

The problem being addressed by this tree is S * arg max P ( S | a

a

a

a

)

s

−

−

−

=

a1-a2-a1-a2 is the output sequence and µ the model or the machine

Path found ^:

(working backward)

S

S

2

S

1

S

2

S

1

a

a

a

a

2

Problem statement : Find the best possible sequence

) ,

| max (

* arg ^{P S O} µ S

s

=

Machine or

Model Seq,

Output Seq,

State

,

µ

where

,

State Seq,

Output Seq, µ

Model or Machine

} , , , { Machine

or

Model = S

S A T

Start symbol State collection Alphabet set

Transitions

T is defined as P ( S

 → a

S

) ∀

Tabular representation of the tree

€ a

1

a

2

a

1

a

2

S

Latest symbol observed

S

(0.02, 0.09)

(0.009, 0.012) (0.0024, 0.0081)

S

(0.04,0.0 6)

(0.027,0.018) (0.0048,0.005 4)

Note: Every cell records the winning probability ending in that state Final winner The bold faced values in each cell shows the

sequence probability ending in that state. Going backward from final winner sequence which ends in state S2 (indicated By the 2^nd tuple), we recover the sequence.