CSE 150 Lecture Notes - Lecture 14: Forward Pass, Bayes Estimator, Dynamic Programming

40 views2 pages

turquoiseplatypus250

23 May 2018

School

UCSD

Department

Computer Science & Engineering

Course

CSE 150

Professor

Lawrence Saul

For unlimited access to Class Notes, a Class+ subscription is required.

How to compute most likely “hidden” states?

(S1*,..., ST*) = argmaxS1,...,ST P(S1,...,ST|O1,...,OT)

Define: ℓ*it = maxS1,...,St-1 log P(S1,...,St-1,St = i, O1,...,Ot)

Recursive Algorithm

Base Case (t = 1) leftmost column

ℓ*i1 = log P(S1 = 1, O1) = log[P(S1 = i) P(O1|S1 = i)]

= log [πi bi(O1)]

How do we “advance” from one column to the next?

Recursive step from time t



to t+1



ℓ*j,t+1 = maxS1,..,St log P(S1,...,St+1 = j, O1,...,Ot+1)

= maxS1,...,St-1 maxi log P(S1,...,St = i, St+1 = j, O1,...,Ot+1)

= maxS1,...,St-1 maxi log[P(S1,...,St-1,St = i,O1,...,Ot) P(St+1 = j|St = i,S1,...,St-1,O1,..,Ot)

P(Ot+1|St+1 = j,S1,...,St,O1,...,Ot)

= maxS1,...,St-1 maxi logP(S1,...,St-1,St = i,O1,...,Ot) + log P(St+1 = j|St = i) + log P(Ot+1|St+1 = j)

NOTE: last 2 terms do not depend on S1,...,St-1!!!

ℓ*j,t+1 = maxi {[maxS1,...,St-1 log P(S1,...,St = i,O1,...,Ot)] + log P(St+1 = j|St = i)}

= maxi { ℓ*it + log aij } + log bj(Ot+1)

“Forward pass” for times t = 1 to T

How to denote (S1*,...,ST*) = argmaxS1,...,ST P(S1,...,ST|O1,...,OT) from the matrix ℓ*i1 ?

ɸj,t+1 (where ɸ is a nxT matrix) = argmaxi [ℓ*i1 + log aij]

If I must end up in state j



at time t+1



, based on observations O1,...,Ot, what was the most likely

hidden state St = i at time t



- Compute (S1*,..., ST*) by “backtracking”:

- At time T: ST* = argmaxi [ℓ*i1]

- Just look at which of the numbers in the rightmost column is the biggest!

For times t = T-1 to 1: St* = ɸS*t+1,t+1

Jargon:

(S1*,..., ST*) known as the Vterbi sequence

- Vterbi algorithm is an example of dynamic programming

3) Belief Updating

How to “monitor” hidden state in real time based on incoming evidence?

Key quantity: qjt = P(St = j|O1,...,Ot)

= P(St = j|Ot,O1,...,Ot-1) ← treat as “background evidence”

qjt = P(Ot|St = j,O1,...,Ot-1) P(St = j|O1,...,Ot-1) [Bayes Rule]

P(Ot|O1,...,Ot-1)

= bj(Ot) P(St = j|O1,...,Ot-1)

Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in

CSE 150 Lecture Notes - Lecture 14: Forward Pass, Bayes Estimator, Dynamic Programming

Get access

Related Documents

ECON 424 Midterm: ECON 424 UW Midterm Fall2009 Solutions

GRST 345 Lecture Notes - Lecture 4: Japan Standard Time, Royal Red Cross, Tamil Eelam