Markov Models
PA154 Jazykové modelování (5.1) Pavel Rychlý
pary@fi.muni.cz
March 16, 2020
Source: Introduction to Natural Language Processing (600.465) Jan Hajic, CS Dept., Johns Hopkins Univ. www.cs.jhu.edu/~hajic
Review: Markov Process
Bayes formula (chain rule):
P{W) = P(wi, 1/1/2,     W/T) = n/=i..rp(w/ I ffllfflfy/.f, Wi-n+i
1 '' J
n-gram language models:
► Markov process (chain) of the order n-1:
l)
P(W) = P(wi, w2..., i/i/t) = ri/=i..rp(w/ | w/_n+i, w/_,,+25 • w;-i) Using just one distribution (Ex.: trigram model: p{w; | i/i/;_2, vv/-i))
Positions: 12       34     56     7 8     9    10   11 12    13   14 15 16
and within hours Bob 's can
Words: My car
broke down ,
broke down ,
too .
p(,| broke down) = p(w$ | 1/1/3. w4) = p(wu | w12, w/13)
PA154 Jazykové modelování (5.1)
Markov Models
2/15
Markov Properties
■ Generalize to any process (not just words/LM):
► Sequence of random variables: X = (Xi, X2,..., X7-)
► Sample space S (states), size N: S = (So, Si, S2,..., S/v)
1. Limited History (Context, Horizon):
Vi G 1..T; P(X/ I Xi, ..,X/_i) = (X/ I X/_i)
1737906 345
173790 6^3 45
Time invariance (M.C. is stationary, homogenous) V/ G 1..T, Vy,x e S; P(X, = y | X,-_i = x) = p(y
10H]0[1]O60|T]45...
x)
ok... same distribution
PA154 Jazykové modelování (5.1)
Markov Models
3/15
Long History Possible
What if we want trigrams: 1 7 7 3 7 9 0 [öT] |T| 4 5
Formally, use transformation:
Define new variables Qj,suchthatXj = (?,-: Then
P(Xi I X/_i) = P((?;-i, (?; I 0/-2, (?/. Predicting (X,) 1 7 3 7 [Öo] 6 7 3 4 5...
;;;; \ r r r r r
History (X; = {0,_2, (?,_!}):
Markov Models
Graph Representation: State Diagram
■ S = {so, si, s2,..., sn}: states
■ Distribution P(X; | X/_i):
► transitions (as arcs) with probabilities attached to them:
Bigram case:
PA154 Jazykové modelování (5.1)
p(toe) = .6 x .88 x 1 = .528
Markov Models 5/15
The Trigram Case
p(toe) = .6 x .88 x .07 = .037 p(one)
PA154 Jazykové modelování (5.1)
Markov Models
Finite State Automaton
States ~ symbols of the [input/output] alphabet
► pairs (or more): last element of the n-tuple
Arcs ~ transitions (sequence of states) [Classical FSA: alphabet symbols on arcs:
► transformation: arcs <h- nodes]
Possible thanks to the "limited history" M^fkov Property So far:  Visible Markov Models (VMMf
PA154 Jazykové modelování (5.1)
Markov Models
7/15
Hidden Markov Models
The simplest HMM: states generate [observable] output (using the "data" alphabet) but remain "invisible":
p(toe) = .6 x .88 x 1 = .528
PA154 Jazykové modelování (5.1)
Markov Models
8/15
Added Flexibility.
■ So far, no change; but different states may generate the same output (why not?):
p(toe) = .6 x .88 x 1 +
.4 x .1 x 1 = .568
PA154 Jazykové modelování (5.1)
Markov Models
9/15
Output from Arcs...
Added flexibility: Generate output from arcs, not states:
p(toe) = .6 x .88 x 1 + .4x.lxl + .4 x .2 x .3 + .4 x .2 x .4 = .624
PA154 Jazykové modelování (5.1)
Markov Models
10/15
.. .and Finally, Add Output Probabilities
Maximum flexibility: [Unigram] distribution (sample space: output alphabet) at each output arc:
Isimplified
p(t)=.8 p(o)=.l
P(e)=.l
p(toe) = .6 x .8 x .88 x .7 x 1 x .6 + .4 x .5 x 1 x 1 x .88 x .2 + .4 x .5 x 1 x 1 x .12 x 1
p(t)=0 p(o)=.4 p(e)=.6
.237
PA154 Jazykové modelování (5.1)
Markov Models
11/15
Slightly Different View
■ Allow for multiple arcs from s; —> sj, mark them by output symbol s, get rid of output distributions:
o,.06 e,.12
p(toe) = .48 x .616 x .6 + .2 x 1 x .176 +
.2 x 1 x .12 ^ .237 In the future, we will use the view more convenient for the problem at hand.
PA154 Jazykové modelování (5.1)
Markov Models
12/15
Formalization
HMM (the most general case):
■ five-tuple (S,so, Y, Ps, Py), where:
► S = {so, si, S2,..., S7-} is the set of states, so is the initial state,
► Y = {yi, 3/2,.. •, yv} is the output alphabet,
► Ps(sj | s,-) is the set of prob. distributions of transitions,
► size of Ps :| S |2.
► Py(yk | s/jS/) is the set of output (emission) probability distributions.
► size of PY :| S |2 x | V |
Example:
■ S= x, 1, 2, 3, 4, sq = x
■ Y = {ŕ, o, e
}
Markov Models
13/15
Formalization - Example
Example (for graph, see foils 11,12)
► S= {x, 1,2,3,4}, s0 = x
► Y= {e,o,t}
Ps
	X	1	2	3	4
X	0	.6	0	.4	0
1	0	0	.12	0	.88
2	0	0	0	0	1
3	0	1	0	0	0
4	0	0	1	0	0
-> I =					
'Y-
		e	x	1	2	3	4
	o	x	1	2	3	4	
t	x	1	2	3	4		^T2
x		.8		.5		" .7	
1			0		.1		
2					0		
3		0					
4			0				
PA154 Jazykové modelovaní (5.1)
Markov Models
14/15
Using the HMM
■ The generation algorithm (of limited value :-)):
O Start in s = so-
Q Move from s to s' with probability Ps(s/ | s).
& Output (emit) symbol yk with probability Ps(yk | s,s;).
□ Repeat from step 2 (until somebody says enough).
■ More interestirig usage:
► Given an output sequence Y = {yi,y2,... ,y/c} compute its probability.
► Given an output sequence Y = {yi,y2,... ,y/c} compute the most likely sequence of states which has generated it.
► . .. plus variations: e.g., n best state sequences
PA154 Jazykové modelování (5.1)
Markov Models
15/15