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