1、A Fast Finite-state Relaxation Method for Enforcing Global Constraints on Sequence Decoding,Roy Tromble & Jason Eisner Johns Hopkins University,Seminar Friday, April 1 Speaker: Monty Hall Location: Auditorium #1 “Lets Make a Dilemma” Monty Hall will host a discussion of his famous paradox.,We know w
2、hat the labels should look like!,Agreement: Named Entity Recognition (Finkel et al., ACL 2005) Seminar announcements (Finkel et al., ACL 2005),Label structure: Bibliography parsing (Peng & McCallum, HLT-NAACL 2004) Semantic Role Labeling (Roth & Yih, ICML 2005),Sequence modeling quality,Decoding run
3、time,Local models,Global constraints,Finite-state constraint relaxation,Exploit the quality of the local models!,Semantic Role Labeling,Label each argument to a verb Six core argument types (A0-A5) CoNLL-2004 shared task Penn Treebank section 20 4305 propositions Follow Roth & Yih (ICML 2005),A1 A1
4、A1 O O A4 O A3 O,Encoding constraints as finite-state automata,Roth & Yihs constraints as FSAs,A0*A0*A0*,A1*A1*A1*,Each argument type (A0, A1, .) can label at most one sub-sequence of the input.,NO DUPLICATE ARGUMENTS,Roth & Yihs constraints as FSAs,O*O?*,The label sequence must contain at least one
5、 instance that is not O.,AT LEAST ONE ARGUMENT,Regular expressions on any sequences: grep for sequence models,Roth & Yihs constraints as FSAs,Only allow argument types that are compatible with the propositions verb.,DISALLOW ARGUMENTS,Roth & Yihs constraints as FSAs,The propositions verb must be lab
6、eled O.,KNOWN VERB POSITION,Roth & Yihs constraints as FSAs,Certain sub-sequences must receive a single label.,ARGUMENT CANDIDATES,Any constraints on bounded-length sequences,Roth & Yihs local model as a lattice,“Soft constraints” or “features”,A brute-force FSA decoder,NO DUPLICATE A0,NO DUPLICATE
7、A0, A1,NO DUPLICATE ARGUMENTS,Any approach would blow up in worst case!,Satisfying global constraints is NP-hard.,Roth & Yih (ICML 2005): Express path decoding and global constraints as an integer linear program (ILP). Apply ILP solver: Relax ILP to (real-valued) LP. Apply polynomial-time LP solver.
8、 Branch and bound to find optimal integer solution.,Handling an NP-hard problem,The ILP solver doesnt know its labeling sequences,Path constraints: State 0: outflow 1; State 3: inflow 1 States 1 & 2: outflow = inflow At least one argument: Arcs labeled O: flow 1,Maybe we can fix the brute-force deco
9、der?,Local model usually violated no constraints,Most constraints were rarely violated,Finite-state constraint relaxation,Local models already capture much structure. Relax the constraints instead!Find best path using linear decoding algorithm. Apply only those global constraints that path violates.
10、,Brute-force algorithm,Constraint relaxation algorithm,yes,no,Finite-state constraint relaxation is faster than the ILP solver,State-of-the-art implementations: Xpress-MP for ILP, FSA (Kanthak & Ney, ACL 2004) for constraint relaxation.,No sentences required more than a few iterations,Buy one, get o
11、ne free,A1,A4,A3,A1,Sales for the quarter rose to $ 1.63 billion from $ 1.47 billion .,Lattices remained small,Take-home message,Global constraints arent usually doing that much work for you: Typical examples violate only a small number using local models. They shouldnt have to slow you down so much
12、, even though theyre NP-hard in the worst case: Figure out dynamically which ones need to be applied.,Future work,General soft constraints (We discuss binary soft constraints in the paper.) Choose order to test and apply constraints, e.g. by reinforcement learning. k-best decoding,Thanks,to Scott Yih for providing both data and runtime, and to Stephan Kanthak for FSA.,
