NLP Programming Tutorial 13 – Beam and A* Search

NLP Programming Tutorial 13 Beam and A* Search

Graham Neubig
Nara Institute of Science and Technology (NAIST)1NLP Programming Tutorial 13 – Beam and A* SearchPrediction Problems●

Given observable information X, find hidden Yargmax P (Y∣X )Y●

Used in POS tagging, word segmentation, parsing●

Solving this argmax is “search”●

Until now, we mainly used the Viterbi algorithm
2

NLP Programming Tutorial 13 – Beam and A* Search

Hidden Markov Models (HMMs) for
POS Tagging●●POS→POS transition probabilities
I +1● Like a bigram model!
P (Y )≈ ∏ i=1 PT (y i∣y i−1 )POS→Word emission probabilities
IP (X∣Y )≈ ∏1 P E ( x i∣y i )PT(JJ|
) * PT(NN|JJ) * PT(NN|NN)




JJ

NN

NN

…

LRB

NN

RRB

...

natural language processing (nlp)...

PE(natural|JJ) * PE(language|NN) * PE(processing|NN)

…




3

NLP Programming Tutorial 13 – Beam and A* Search

Finding POS Tags with Markov Models●The best path is our POS sequence

0:<S>




naturallanguage processing(nlp)

1:NN

2:NN

3:NN

4:NN

5:NN

6:NN

1:JJ

2:JJ

3:JJ

4:JJ

5:JJ

6:JJ

1:VB

2:VB

3:VB

4:VB

5:VB

6:VB

1:LRB

2:LRB

3:LRB

4:LRB

5:LRB

6:LRB

1:RRB

2:RRB

3:RRB

4:RRB

5:RRB

6:RRB

…

…

…

…

…

…

JJ

NN

NN

LRB

NN

RRB

…

4NLP Programming Tutorial 13 – Beam and A* Search

Remember: Viterbi Algorithm Steps●Forward step, calculate the best path to a node●●Find the path to each node with the lowest negative log
probabilityBackward step, reproduce the path
●This is easy, almost the same as word segmentation

5

NLP Programming Tutorial 13 – Beam and A* Search

Forward Step: Part 1●First, calculate transition from <S> and emission of thefirst word for every POS
natural0:<S>

1:NN best_score[“1 NN”] = -log PT(NN|<S>) + -log PE(natural | NN)
1:JJ best_score[“1 JJ”] = -log PT(JJ|<S>) + -log PE(natural | JJ)
1:VB best_score[“1 VB”] = -log PT(VB|<S>) + -log PE(natural | VB)
1:LRB best_score[“1 LRB”] = -log PT(LRB|<S>) + -log PE(natural | LRB)
1:RRB best_score[“1 RRB”] = -log PT(RRB|<S>) + -log PE(natural | RRB)…

6

NLP Programming Tutorial 13 – Beam and A* Search

Forward Step: Middle Parts●For middle words, calculate the minimum score for all
possible previous POS tags

natural language
1:NN

2:NN

1:JJ

2:JJ

1:VB

2:VB

1:LRB

2:LRB

1:RRB

2:RRB

…

…

best_score[“2 NN”] = min(best_score[“1 NN”] + -log PT(NN|NN) + -log PE(language | NN),
best_score[“1 JJ”] + -log PT(NN|JJ) + -log PE(language | NN),
best_score[“1 VB”] + -log PT(NN|VB) + -log PE(language | NN),
best_score[“1 LRB”] + -log PT(NN|LRB) + -log PE(language | NN),
best_score[“1 RRB”] + -log PT(NN|RRB) + -log PE(language | NN),...
)
best_score[“2 JJ”] = min(best_score[“1 NN”] + -log PT(JJ|NN) + -log PE(language | JJ),
best_score[“1 JJ”] + -log PT(JJ|JJ) + -log PE(language | JJ),
best_score[“1 VB”] + -log PT(JJ|VB) + -log PE(language | JJ), 7...

NLP Programming Tutorial 13 – Beam and A* Search

Forward Step: Final Part
●Finish up the sentence with the sentence final symbol

science
I:NN
I:JJ
I:VB
I:LRB

I+1:</S>

best_score[“I+1 </S>”] = min(best_score[“I NN”] + -log PT(</S>|NN),
best_score[“I JJ”] + -log PT(</S>|JJ),
best_score[“I VB”] + -log PT(</S>|VB),
best_score[“I LRB”] + -log PT(</S>|LRB),
best_score[“I NN”] + -log PT(</S>|RRB),...
)I:RRB…

8NLP Programming Tutorial 13 – Beam and A* Search

Viterbi Algorithm and Time
●The time of the Viterbi algorithm depends on:type of problem: POS? Word Segmentation? Parsing?
● length of sentence: Longer Sentence=More Time● number of tags: More Tags=More Time●●

What is time complexity of HMM POS tagging?
T = Number of tags
● N = length of sentence●

9NLP Programming Tutorial 13 – Beam and A* Search

Simple Viterbi Doesn't Scale●Tagging:
Named Entity Recognition:
T = types of named entities (100s to 1000s)● Supertagging:T = grammar rules (100s)●●

Other difficult search problems:Parsing: T * N3
● Speech Recognition: (frames)*(WFST states, millions)● Machine Translation: NP complete●

10

NLP Programming Tutorial 13 – Beam and A* Search

Two Popular Solutions●Beam Search:
Remove low probability partial hypotheses● + Simple, search time is stable● - Might not find the best answer●●A* Search:
Depth-first search, create a heuristic function of cost toprocess the remaining hypotheses● + Faster than Viterbi, exact● - Must be able to create heuristic, search time is notstable●11

NLP Programming Tutorial 13 – Beam and A* Search

Beam Search

12

NLP Programming Tutorial 13 – Beam and A* Search

Beam Search●●●Choose beam of B hypotheses
Do Viterbi algorithm, but keep only best B hypotheses
at each step
Definition of “step” depends on task:Tagging: Same number of words tagged● Machine Translation: Same number of words translated● Speech Recognition: Same number of frames
processed●13

NLP Programming Tutorial 13 – Beam and A* Search

Calculate Best Scores (First Word)●

Calculate best scores for first word
natural0:<S>

1:NN best_score[“1 NN”] = -3.1
1:JJ best_score[“1 JJ”] = -4.2
1:VB best_score[“1 VB”] = -5.4
1:LRB best_score[“1 LRB”] = -8.2
1:RRB best_score[“1 RRB”] = -8.1…

14

NLP Programming Tutorial 13 – Beam and A* Search

Keep Best B Hypotheses (w1)●

Remove hypotheses with low scores●For example, B=3
natural0:<S>

1:NN best_score[“1 NN”] = -3.1
1:JJ best_score[“1 JJ”] = -4.2
1:VB best_score[“1 VB”] = -5.4
1:LRB best_score[“1 LRB”] = -8.2
1:RRB best_score[“1 RRB”] = -8.1…

15

NLP Programming Tutorial 13 – Beam and A* Search

Calculate Probabilities (w2)
●Calculate score, but ignore removed hypotheses

natural language
1:NN

2:NN

1:JJ

2:JJ

1:VB

2:VB

1:LRB

2:LRB

1:RRB

2:RRB

…

…

best_score[“2 NN”] = min(best_score[“1 NN”] + -log PT(NN|NN) + -log PE(language | NN),
best_score[“1 JJ”] + -log PT(NN|JJ) + -log PE(language | NN),
best_score[“1 VB”] + -log PT(NN|VB) + -log PE(language | NN),
best_score[“1 LRB”] + -log PT(NN|LRB) + -log PE(language | NN),
best_score[“1 RRB”] + -log PT(NN|RRB) + -log PE(language | NN),...
)
best_score[“2 JJ”] = min(best_score[“1 NN”] + -log PT(JJ|NN) + -log PE(language | JJ),
best_score[“1 JJ”] + -log PT(JJ|JJ) + -log PE(language | JJ),
best_score[“1 VB”] + -log PT(JJ|VB) + -log PE(language | JJ), 16...

NLP Programming Tutorial 13 – Beam and A* Search

Beam Search is Faster●●Remove some candidates from consideration→ faster speed!
What is the time complexity?
T = Number of tags
● N = length of sentence● B = beam width●17NLP Programming Tutorial 13 – Beam and A* Search

Implementation: Forward Step
best_score[“0 
”] = 0 # Start with 
best_edge[“0 
”] = NULL
active_tags[0] = [ “
” ]for i in 0 … I-1:
make map my_best
for each prev in keys of active_tags[i]for each next in keys of possible_tags
if best_score[“i prev”] and transition[“prev next”] exist
score = best_score[“i prev”] +-log PT(next|prev) + -log PE(word[i]|next)
if best_score[“i+1 next”] is new or > score
best_score[“i+1 next”] = score
best_edge[“i+1 next”] = “i prev”
my_best[next] = scoreactive_tags[i+1] = best B elements of my_best18# Finally, do the same for 


NLP Programming Tutorial 13 – Beam and A* Search

A* Search

19

NLP Programming Tutorial 13 – Beam and A* Search

Depth-First Search●Always expand the state with the highest score●Use a heap (priority queue) to keep track of states
heap: a data structure that can add elements in O(1)and find the highest scoring element in time O(log n)● Start with only the initial state on the heap
● Expand the best state on the heap until search finishes●●

Compare with breadth-first search, which expands
states at the same step (Viterbi, beam search)

20

NLP Programming Tutorial 13 – Beam and A* Search

Depth-First Search●

Initial state:0:<S>

naturallanguage

processing

1:NN

2:NN

3:NN

1:JJ

2:JJ

3:JJ

1:VB2:VB

3:VB

1:LRB

2:LRB

3:LRB

1:RRB

2:RRB

3:RRB

Heap

0:<S>

021

NLP Programming Tutorial 13 – Beam and A* Search

Depth-First Search●Process 0:<S>

0:<S>

naturallanguage

processing

Heap

1:NN

2:NN

3:NN

2:JJ

3:JJ

2:VB

3:VB

1:NN -3.1
1:JJ -4.2
1:VB -5.4
1:RRB -8.1
1:LRB -8.2

2:LRB

3:LRB

2:RRB

3:RRB-3.1

1:JJ-4.2

1:VB-5.4
1:LRB-8.2
1:RRB-8.1

22

NLP Programming Tutorial 13 – Beam and A* Search

Depth-First Search●Process 1:NN

0:<S>

naturallanguage

processing

Heap

1:NN

2:NN

3:NN-3.1-5.5

1:JJ

2:JJ-4.2-6.7

1:VB

2:VB-5.4-5.7

1:LRB

2:LRB-8.2-11.2

1:JJ -4.2
1:VB -5.4
2:NN -5.5
2:VB -5.7
2:JJ -6.7
1:RRB -8.1
1:LRB -8.2
2:LRB -11.2
2:RRB -11.4

1:RRB

2:RRB-8.1-11.4

3:JJ
3:VB
3:LRB
3:RRB

23

NLP Programming Tutorial 13 – Beam and A* Search

Depth-First Search●Process 1:JJ

0:<S>

From 1:NN 1:JJ

naturallanguage

processing

Heap

1:NN

2:NN

3:NN-3.1-5.5

1:JJ

2:JJ-4.2-6.7

1:VB

2:VB-5.4-5.7

1:LRB

2:LRB-8.2-11.2 -11.9

1:RRB

2:RRB

2:NN -5.3
1:VB -5.4
2:NN -5.5
2:VB -5.7
2:JJ -5.9
2:JJ -6.7
1:RRB -8.1
1:LRB -8.2
2:LRB -11.2
2:RRB -11.4-8.1-11.4 -11.7-5.3

3:JJ-5.9

3:VB-7.2
3:LRB
3:RRB

24

NLP Programming Tutorial 13 – Beam and A* Search

Depth-First Search●Process 1:JJ

0:<S>

naturallanguage

processing

Heap

1:NN

2:NN

3:NN-3.1-5.3

1:JJ

2:JJ-4.2-5.9

1:VB

2:VB-5.4-5.7

1:LRB

2:LRB-8.2-11.2

1:RRB

2:RRB

2:NN -5.3
1:VB -5.4
2:NN -5.5
2:VB -5.7
2:JJ -5.9
2:JJ -6.7
1:RRB -8.1
1:LRB -8.2
2:LRB -11.2
2:RRB -11.4-8.1-11.4

3:JJ
3:VB
3:LRB
3:RRB

25

NLP Programming Tutorial 13 – Beam and A* Search

Depth-First Search●Process 2:NN

0:<S>

naturallanguageprocessing

Heap

1:NN

2:NN

3:NN-3.1-5.3-7.2

1:JJ

2:JJ

3:JJ-4.2-5.9-9.8

1:VB

2:VB

3:VB-5.4-5.7-7.3

1:LRB

2:LRB

3:LRB-8.2-11.2-16.3

1:RRB

2:RRB

3:RRB-8.1-11.4-17.0

1:VB -5.4
2:NN -5.5
2:VB -5.7
2:JJ -5.9
2:JJ -6.7
3:NN -7.2
3:VB -7.3
1:RRB -8.1
1:LRB -8.2
3:JJ -9.8
2:LRB -11.2
26...

NLP Programming Tutorial 13 – Beam and A* Search

Depth-First Search●Process 1:VB

0:<S>

naturallanguage

processing

Heap

1:NN

2:NN

3:NN-3.1-5.3 -7.3-7.2

1:JJ

2:JJ

3:JJ-4.2-5.9 -8.9-9.8

1:VB

2:VB

3:VB-5.4-5.7 -12.7-7.3

1:LRB

2:LRB

3:LRB-8.2-11.2 -14.5-16.3

1:RRB

2:RRB

3:RRB-8.1-11.4 -14.7-17.0

2:NN -5.5
2:VB -5.7
2:JJ -5.9
2:JJ -6.7
3:NN -7.2
3:VB -7.3
1:RRB -8.1
1:LRB -8.2
3:JJ -9.8
2:LRB -11.227...

NLP Programming Tutorial 13 – Beam and A* Search

Depth-First Search●Do not process 2:NN (has already been processed)

0:<S>

naturallanguage

processing

Heap

1:NN

2:NN

3:NN-3.1

-5.3

-7.2

1:JJ

2:JJ

3:JJ-4.2-5.9-9.8

1:VB

2:VB

3:VB-5.4-5.7-7.3

1:LRB

2:LRB

3:LRB-8.2

-11.2

-16.3

1:RRB

2:RRB

3:RRB

2:VB -5.7
2:JJ -5.9
2:JJ -6.7
3:NN -7.2
3:VB -7.3
1:RRB -8.1
1:LRB -8.2
3:JJ -9.8
2:LRB -11.2...

-8.1

-11.4

-17.028

NLP Programming Tutorial 13 – Beam and A* Search

Problem: Still Inefficient●●

Depth-first search does not work well for longsentences
Why?
●

Hint: Think of 1:VB in previous example

29

NLP Programming Tutorial 13 – Beam and A* Search

A* Search: Add Optimistic Heuristic●Consider the words remaining●

Use Optimistic Heuristic: BEST score possible●Optimistic heuristic for tagging: Best Emission Prob
naturallanguageprocessing

log(P(natural|NN)) = -2.4 log(P(lang.|NN)) = -2.4 log(P(proc.|NN)) = -2.5log(P(natural|JJ)) = -2.0log(P(lang.|JJ)) = -3.0log(P(proc.|JJ)) = -3.4log(P(natural|VB)) = -3.1 log(P(lang.|VB)) = -3.2 log(P(proc.|VB)) = -1.5log(P(natural|LRB)) = -7.0 log(P(lang.|LRB)) = -7.9 log(P(proc.|LRB)) = -6.9log(P(natural|RRB)) = -7.0 log(P(lang.|RRB)) = -7.9 log(P(proc.|RRB)) = -6.9

H(1+) = -5.9

H(2+) = -3.9

H(3+) = -1.5

H(4+) = 0.030

NLP Programming Tutorial 13 – Beam and A* SearchA* Search: Add Optimistic Heuristic●Use Forward Score + Optimistic Heuristic
Regular Heap

2:VB
2:JJ
2:JJ
3:NN
3:VB
1:RRB
1:LRB
3:JJ
2:LRB

F(2:VB)=-5.7
F(2:JJ)=-5.9
F(2:JJ)=-6.7
F(3:NN)=-7.2
F(3:VB)=-7.3
F(1:RRB)=-8.1
F(1:LRB)=-8.2
F(3:JJ)=-9.8
F(2:LRB)=-11.2

A* Heap

H(3+)=-1.5
H(3+)=-1.5
H(3+)=-1.5
H(4+)=-0.0
H(4+)=-0.0
H(2+)=-3.9
H(2+)=-3.9
H(4+)=-0.0
H(3+)=-1.53:NN
2:VB
3:VB
2:JJ
2:JJ
3:JJ
1:RRB
1:LRB
2:LRB

-7.2
-7.2
-7.3
-7.4
-8.2
-9.8
-12.0
-12.1
-12.7
31

NLP Programming Tutorial 13 – Beam and A* Search

Exercise32

NLP Programming Tutorial 13 – Beam and A* Search

Exercise●

Write test-hmm-beam●

Test the program

●

●

●

Input: test/05­{train,test}­input.txt●

Answer: test/05­{train,test}­answer.txt

Train an HMM model on data/wiki­en­train.norm_pos
and run the program on data/wiki­en­test.norm

Measure the accuracy of your tagging withscript/gradepos.pl data/wiki­en­test.pos my_answer.pos●

Report the accuracy for different beam sizes●Challenge: implement A* search
33

NLP Programming Tutorial 13 – Beam and A* Search

Thank You!

34