Natural Language Processing: Algorithms and Applications, Old and New
Noah A. Smith · 2015
problem: x = 〈x [1], x [2], . . . , x [L]〉 ↓ C ↓ y = 〈y [1], y [2], . . . , y [L]〉 Simple solution: categorize each x [`] separately. But what if y [`] and y [`+ 1] depend on each other? Linear Models, Generalized to Sequences ŷ = argmax y∈Yx w>φ(x , y [1], . . . , y [L]) Linear Models, Generalized to Sequences ŷ = argmax y∈Yx w>φ(x , y [1], . . . , y [L]) ŷ = argmax y∈Yx w> ( L ∑ `=2 φlocal(x , `, y [`− 1], y [`]) ) Special Case: Hidden Markov Model HMMs are probabilistic; they define: p(x , y) = p(stop | y [L]) L ∏ `=1 p(x [`] | y [`]) } {{ } emission · p(y [`] | y [`− 1]) } {{ } transition (where y [0] is defined to be a special start symbol). Emission and transition counts can be treated as features, with coefficients equal to their log-probabilities. wφlocal(x , `, y [`− 1], y [`]) = log p(x [`] | y [`]) + log p(y [`] | y [`− 1]) The probabilistic view is sometimes useful (we will see this later). Finding the Best Sequence y : Intuition If we knew y [1 : L− 1], picking y [L] would be easy: argmax λ wφlocal(x , L, y [L− 1], λ)+ w> ( L−1 ∑ `=2 φlocal(x , `, y [`− 1], y [`]) ) Finding the Best Sequence y : Notation Let: V [L− 1, λ] = max y [1:L−2] w> ( L−2 ∑ `=2 φlocal(x , `, y [`− 1], y [`]) ) + wφlocal(x , L− 1, y [L− 2], λ) Our choice for y [L] is then: argmax λ ( max λ′ wφlocal(x , L, λ ′, λ) + V [L− 1, λ′] ) Finding the Best Sequence y : Notation Let: V [L− 1, λ] = max y [1:L−2] w> ( L−2 ∑ `=2 φlocal(x , `, y [`− 1], y [`]) ) + wφlocal(x , L− 1, y [L− 2], λ) Note that: V [L− 1, λ] = max λ′ V [L− 2, λ′] + wφlocal(x , L− 1, λ′, λ) And more generally: ∀` ∈ {2, . . .}, V [`, λ] = max λ′ V [`− 1, λ′] + wφlocal(x , `, λ′, λ)