程序代写代做代考 go Bayesian Hidden Markov Mode algorithm C Video 1: Viterbi algorithm motivation

Viterbi: high-level picture • Wanttofindargmax𝑄𝑃(𝑄|𝑂)
• Intuition:thebestpathoflengthtendinginstateq must include the best path of length t-1 to the previous state. So,
– Find the best path of length t-1 to each state.
– Consider extending each of those by 1 step, to state q.
– Take the best of those options as the best path to state q.
Algorithms for HMMs (Goldwater, ANLP) 21
Viterbi algorithm
• Use a chart to store partial results as we go
– NxT table, where v(j,t) is the probability* of the best state sequence for o1…ot that ends in state j.
Algorithms for HMMs (Goldwater, ANLP) 22
*Specifically, v(j,t) stores the max of the joint probability P(o1…ot,q1…qt-1,qt=j|λ)
Viterbi algorithm
• Use a chart to store partial results as we go
– NxT table, where v(j,t) is the probability* of the best state sequence for o1…ot that ends in state j.
• Fillincolumnsfromlefttoright,with 𝑣𝑗,𝑡=max𝑁 𝑣𝑖,𝑡−1∙𝑎∙𝑏𝑜
𝑖=1 𝑖𝑗 𝑗 𝑡
Algorithms for HMMs (Goldwater, ANLP)
23
*Specifically, v(j,t) stores the max of the joint probability P(o1…ot,q1…qt-1,qt=j|λ)
Viterbi algorithm
• Use a chart to store partial results as we go
– NxT table, where v(j,t) is the probability* of the best state sequence for o1…ot that ends in state j.
• Fillincolumnsfromlefttoright,with 𝑣𝑗,𝑡=max𝑁 𝑣𝑖,𝑡−1∙𝑎∙𝑏𝑜
𝑖=1 𝑖𝑗 𝑗 𝑡
• Store a backtrace to show, for each cell, which state at t-1 we came from.
Algorithms for HMMs (Goldwater, ANLP) 24
*Specifically, v(j,t) stores the max of the joint probability P(o1…ot,q1…qt-1,qt=j|λ)

Example
• Suppose O=xzy. Our initially empty table:
o1=x o2=z o3=y
q1 q2
Algorithms for HMMs (Goldwater, ANLP)
25
q1 q2
Filling the first column
o1=x o2=z
o3=y
.6
0
𝑣1,1 =𝑎<𝑠>1∙𝑏1 𝑥)= 1(.6 𝑣2,1 =𝑎<𝑠>2∙𝑏2 𝑥)= 0(.1
Algorithms for HMMs (Goldwater, ANLP)
26
Starting the second column
o1=x o2=z o3=y
q1 q2
𝑣1,2=max𝑁 𝑣𝑖,1∙𝑎∙𝑏𝑧 𝑖=1 𝑖11
= max ቊ𝑣 1,1 ∙ 𝑎11∙ 𝑏1 𝑧 = (.6)(.7)(.3) 𝑣 2,1 ∙ 𝑎21∙ 𝑏1 𝑧 = (0)(.5)(.3)
.6
0
Algorithms for HMMs (Goldwater, ANLP) 27
Starting the second column
o1=x o2=z o3=y
q1 q2
𝑣1,2=max𝑁 𝑣𝑖,1∙𝑎∙𝑏𝑧 𝑖=1 𝑖11
= max ቊ𝑣 1,1 ∙ 𝑎11∙ 𝑏1 𝑧 = (.6)(.7)(.3) 𝑣 2,1 ∙ 𝑎21∙ 𝑏1 𝑧 = (0)(.5)(.3)
.6
.126
0
Algorithms for HMMs (Goldwater, ANLP) 28

Finishing the second column
o1=x o2=z o3=y
.6
.126
0
q1 q2
𝑣2,2=max𝑁 𝑣𝑖,1∙𝑎∙𝑏𝑧 𝑖=1 𝑖22
= max ቊ𝑣 1,1 ∙ 𝑎12∙ 𝑏2 𝑧 = (.6)(.3)(.2) 𝑣 2,1 ∙ 𝑎22∙ 𝑏2 𝑧 = (0)(.5)(.2)
Algorithms for HMMs (Goldwater, ANLP) 29
Finishing the second column
o1=x o2=z o3=y
.6
.126
0
.036
q1 q2
𝑣2,2=max𝑁 𝑣𝑖,1∙𝑎∙𝑏𝑧 𝑖=1 𝑖22
= max ቊ𝑣 1,1 ∙ 𝑎12∙ 𝑏2 𝑧 = (.6)(.3)(.2) 𝑣 2,1 ∙ 𝑎22∙ 𝑏2 𝑧 = (0)(.5)(.2)
Algorithms for HMMs (Goldwater, ANLP) 30
Third column
o1=x o2=z o3=y
.6
.126
.00882
0
.036
.02646
q1 q2
• Exercise: make sure you get the same results!
Algorithms for HMMs (Goldwater, ANLP) 31
Best Path
o1=x o2=z o3=y
.6
.126
.00882
0
.036
.02646
q1 q2
• Choose best final state: max𝑁 𝑣 𝑖, 𝑇 𝑖=1
• Follow backtraces to find best full sequence: q1q1q2, so:
Algorithms for HMMs (Goldwater, ANLP) 32

Video 4: Forward algorithm
Algorithms for HMMs (Goldwater, ANLP) 33
HMMs: what else?
• Using Viterbi, we can find the best tags for a
sentence (decoding), and get 𝑃 𝑂, 𝑄 𝜆).
• We might also want to
– Compute the likelihood 𝑃 𝑂 𝜆), i.e., the probability of a sentence regardless of tags (a language model!)
– learn the best set of parameters λ = (A, B) given only an unannotated corpus of sentences.
Algorithms for HMMs (Goldwater, ANLP) 34
Computing the likelihood
• From probability theory, we know that
𝑃 𝑂 𝜆) = ෍ 𝑃 𝑂, 𝑄 𝜆 𝑄
• There are an exponential number of Qs.
• Again, by computing and storing partial results, we
can solve efficiently.
• (Next slides show the algorithm but I’ll likely skip them)
Algorithms for HMMs (Goldwater, ANLP) 35
Forward algorithm
• Use a table with cells α(j,t): the probability of being in
state j after seeing o1…ot (forward probability). 𝛼(𝑗,𝑡) = 𝑃(𝑜1,𝑜2,…𝑜𝑡,𝑞𝑡 = 𝑗|𝜆)
• Fill in columns from left to right, with 𝑁
𝛼𝑗,𝑡 =෍𝛼𝑖,𝑡−1∙𝑎 ∙𝑏 𝑜 𝑖𝑗 𝑗 𝑡
𝑖=1
– Same as Viterbi, but sum instead of max (and no backtrace). Algorithms for HMMs (Goldwater, ANLP) 36

Example
• Suppose O=xzy. Our initially empty table:
o1=x o2=z o3=y
q1 q2
Algorithms for HMMs (Goldwater, ANLP)
37
q1 q2
Filling the first column
o1=x o2=z
o3=y
.6
0
𝛼1,1 =𝑎<𝑠>1∙𝑏1 𝑥)= 1(.6 𝛼2,1 =𝑎<𝑠>2∙𝑏2 𝑥)= 0(.1
Algorithms for HMMs (Goldwater, ANLP)
38
Starting the second column
o1=x o2=z o3=y
𝑁
𝛼1,2 =෍𝛼𝑖,1 ∙𝑎𝑖1∙𝑏1𝑧 𝑖=1
=𝛼 1,1 ∙𝑎11∙𝑏1 𝑧 +𝛼 2,1 ∙𝑎21∙𝑏1(𝑧)
= .6 .7 .3 + 0 .5 .3
= .126
.6
.126
0
q1 q2
Algorithms for HMMs (Goldwater, ANLP) 39
Finishing the second column
o1=x o2=z o3=y
𝑁
𝛼2,2 =෍𝛼𝑖,1 ∙𝑎𝑖2∙𝑏2𝑧 𝑖=1
=𝛼 1,1 ∙𝑎12∙𝑏2 𝑧 +𝛼 2,1 ∙𝑎22∙𝑏2(𝑧)
= .6 .3 .2 + 0 .5 .2
= .036
.6
.126
0
.036
q1 q2
Algorithms for HMMs (Goldwater, ANLP) 40

Third column and finish
o1=x o2=z o3=y
.6
.126
.01062
0
.036
.03906
q1 q2
• Add up all probabilities in last column to get the probability of the entire sequence:
𝑁
𝑃𝑂|𝜆 =෍𝛼𝑖,𝑇 𝑖=1
Algorithms for HMMs (Goldwater, ANLP) 41
Video 5: Forward-backward algorithm
Algorithms for HMMs (Goldwater, ANLP) 42
Learning
• Given only the output sequence, learn the best set of
parameters λ = (A, B).
• Assume‘best’=maximum-likelihood.
• Other definitions are possible, won’t discuss here.
Algorithms for HMMs (Goldwater, ANLP) 43
Unsupervised learning
• TraininganHMMfromanannotatedcorpusis simple.
– Supervised learning: we have examples labelled with the right ‘answers’ (here, tags): no hidden variables in training.
• Training from unannotated corpus is trickier.
– Unsupervised learning: we have no examples labelled with the right ‘answers’: all we see are outputs, state sequence is hidden.
Algorithms for HMMs (Goldwater, ANLP) 44

Circularity
• If we know the state sequence, we can find the best λ.
– E.g., use MLE: 𝑃 𝑞𝑗|𝑞𝑖 = 𝐶(𝑞𝑖→𝑞𝑗) 𝐶(𝑞𝑖)
• If we know λ, we can find the best state sequence. – use Viterbi
• Butwedon’tknoweither!
Algorithms for HMMs (Goldwater, ANLP) 45
Expectation-maximization (EM)
Essentially, a bootstrapping algorithm.
• Initialize parameters λ(0)
• Ateachiterationk,
– E-step: Compute expected counts using λ(k-1)
– M-step: Set λ(k) using MLE on the expected counts
• Repeat until λ doesn’t change (or other stopping criterion).
Algorithms for HMMs (Goldwater, ANLP) 46
Expected counts?? Counting transitions from qi→qj:
• Realcounts:
– count 1 each time we see qi→qj in true tag sequence.
• Expected counts:
– With current λ, compute probs of all possible tag sequences. – If sequence Q has probability p, count p for each qi→qj in Q. – Add up these fractional counts across all possible sequences.
Algorithms for HMMs (Goldwater, ANLP) 47
Example
• Notionally, we compute expected counts as follows:
Possible Probability of sequence sequence
Q1= q1 q1 q1 p1 Q2= q1 q2 q1 p2 Q3= q1 q1 q2 p3 Q4= q1 q2 q2 p4 Observs: x z y
Algorithms for HMMs (Goldwater, ANLP) 48

Example
• Notionally, we compute expected counts as follows:
Possible Probability of sequence sequence
Q1= q1 q1 q1 p1 Q2= q1 q2 q1 p2 Q3= q1 q1 q2 p3 Q4= q1 q2 q2 p4 Observs: x z y
መ11
𝐶𝑞→𝑞 =2𝑝1+𝑝3
Algorithms for HMMs (Goldwater, ANLP) 49
Forward-Backward algorithm
• As usual, avoid enumerating all possible sequences.
• Forward-Backward (Baum-Welch) algorithm computes expected counts using forward probabilities and backward probabilities:
𝛽(𝑗, 𝑡) = 𝑃(𝑞𝑡 = 𝑗, 𝑜𝑡+1, 𝑜𝑡+2, … 𝑜𝑇|𝜆)
– Details, see J&M 6.5
• EM idea is much more general: can use for many latent variable models.
Algorithms for HMMs (Goldwater, ANLP) 50
Guarantees
• EM is guaranteed to find a local maximum of the likelihood.
P(O| λ)
values of λ
Algorithms for HMMs (Goldwater, ANLP) 51
•
Guarantees
EM is guaranteed to find a local maximum of the likelihood.
P(O| λ)
values of λ
Not guaranteed to find global maximum.
Practical issues: initialization, random restarts, early stopping.
• •
Algorithms for HMMs (Goldwater, ANLP) 52

Forward-backward/EM in practice
• Fully unsupervised learning of HMM for POS tagging does not work well.
– Model inaccuracies that work ok for supervised learning often cause problems for unsupervised.
• Can be better if more constrained. – Other tasks, using Bayesian priors, etc.
• And, general idea of EM can also be useful.
– E.g., for clustering problems or word alignment in
machine translation.
Algorithms for HMMs (Goldwater, ANLP) 53
Summary
• HMM: a generative model of sentences using hidden state sequence
• Dynamic programming algorithms to compute
– Best tag sequence given words (Viterbi algorithm)
– Likelihood (forward algorithm)
– Best parameters from unannotated corpus (forward-backward algorithm, an instance of EM)
Algorithms for HMMs (Goldwater, ANLP) 54
Video 6: Answers to more HMM
• (no slides)
questions
Algorithms for HMMs (Goldwater, ANLP) 55