Beam-Width Prediction for Efficient Context-Free Parsing.ppt

1、Beam-Width Prediction for Efficient Context-Free Parsing,Nathan Bodenstab, Aaron Dunlop, Keith Hall, Brian Roark,June 2011,OHSU Beam-Search Parser (BUBS),2,Standard bottom-up CYK Beam-search per chart cell Only “best” are retained,Ranking, Prioritization, and FOMs,f() = g() + h() Figure of Merit Car

2、aballo and Charniak (1997) A* search Klein and Manning (2003) Pauls and Klein (2010) Other Turrian (2007) Huang (2008) Apply to beam-search,3,Beam-Width Prediction,Traditional beam-search uses constant beam-width Two definitions of beam-width: Number of local competitors to retain (n-best) Score dif

3、ference from best entry Advantages Heavy pruning compared to CYK Minimal sorting compared to global agenda Disadvantages No global pruning all chart cells treated equal Conservative to keep outliers within beam,4,5,Beam-Width Prediction,How often is gold edge ranked in top N per chart cell Exhaustiv

4、ely parse section 22 + Berkeley latent variable grammar,Gold rank = N,Cumulative Gold Edges,6,Beam-Width Prediction,How often is gold edge ranked in top N per chart cell Exhaustively parse section 22 + Berkeley latent variable grammar,Gold rank = N,Cumulative Gold Edges,7,Beam-Width Prediction,Beam-

5、search + C&C Boundary ranking: How often is gold edge ranked in top N per chart cell:,Gold rank = N,Cumulative Gold Edges,To maintain baseline accuracy, beam-width must be set to 15 with C&C Boundary ranking (and 50 using only inside score),8,Beam-Width Prediction,Beam-search + C&C Boundary ranking:

6、 How often is gold edge ranked in top N per chart cell:,Gold rank = N,Cumulative Gold Edges,To maintain baseline accuracy, beam-width must be set to 15 with C&C Boundary ranking (and 50 using only inside score),Over 70% of gold edges are already ranked first in the local agenda14 of 15 edges in thes

7、e cells are unnecessaryWe can do much better than a constant beam-width,Beam-Width Prediction,Method: Train an averaged perceptron (Collins, 2002) to predict the optimal beam-width per chart cell Map each chart cell in sentence S spanning words wi wj to a feature vector representation:x: Lexical and

8、 POS unigrams and bigrams, relative and absolute span y:1 if gold rank k, 0 otherwise (no gold edge has rank of -1) Minimize the loss:H is the unit step function,9,k,k,Beam-Width Prediction,Method: Use a discriminative classifier to predict the optimal beam-width per chart cell Minimize the loss:L i

9、s the asymmetric loss function:If beam-width is too large, tolerable efficiency loss If beam-width is too small, high risk to accuracy Lambda set to 102 in all experiments,10,k,11,Beam-Width Prediction,Special case: Predict if chart cell is open or closed to multi-word constituents,12,Beam-Width Pre

10、diction,A “closed” chart cell may need to be partially open Binarized or dotted-rule parsing creates new “factored” productions:,13,Beam-Width Prediction,Method 1: Constituent Closure,14,Beam-Width Prediction,Constituent Closure is a per-cell generalization of Roark & Hollingshead (2008) O(n2) class

11、ifications instead of O(n),15,Beam-Width Prediction,Method 2: Complete Closure,16,Beam-Width Prediction,Method 3: Beam-Width Prediction,17,Beam-Width Prediction,Method 3: Beam-Width PredictionUse multiple binary classifiers instead of regression (better performance) Local beam-width taken from class

12、ifier with smallest beam-width prediction Best performance with four binary classifiers: 0, 1, 2, 4 97% of positive examples have beam-width = 4 Dont need a classifier for every possible beam-width value between 0 and global maximum (15 in our case),18,Beam-Width Prediction,19,Beam-Width Prediction,

13、1.00.80.60.40.20.0,20,Beam-Width Prediction,Section 22 development set resultsDecoding time is seconds per sentence averaged over all sentences in Section 22Parsing with Berkeley latent variable grammar (4.3 million productions),21,Beam-Width Prediction,22,Beam-Width Prediction,Beam-Width Prediction

14、,23,24,Beam-Width Prediction,Section 23 test results Only MaxRule is marginalizing over latent variables and performing non-Viterbi decoding,Thanks.,25,26,Beam-Width Prediction,27,FOM Details,C&C FOM Details FOM(NT) = Outsideleft * Inside * Outsideright Inside = Accumulated grammar score Outsideleft = MaxPOS POS forward prob * POS-to-NT transition prob Outsideright = MaxPOS NT-to-POS transition prob * POS bkwd prob ,28,FOM Details,C&C FOM Details,