id	author	title	date	pages	extension	mime	words	sentences	flesch	summary	cache	txt
work_cjz5gcmhlzeylneb6avkrv5bui	Xian Qian	Branch and Bound Algorithm for Dependency Parsing with Non-local Features	2013	12	.pdf	application/pdf	6852	1014	84	Branch and Bound Algorithm for Dependency Parsing For graph based projective dependency parsing, dynamic programming (DP) is popular for decoding It performs cubic time parsing for arc-factored models (Eisner, 1996; McDonald et al., 2005a) and biquadratic time for higher order models with richer There have been numerous studies on global inference algorithms for general higher order parsing. in sentence length for projective dependency parsing (Martins et al., 2009). For general high order models with non-local features, we propose to use Branch and Bound (B&B) algorithm to search the optimal parse tree. bound of the optimal parse tree score in the subspace: UBYi ≥ maxy∈Yi ϕ(x,y). a binary variable indicating whether factor c is selected in the parse tree. Algorithm 1 Branch and Bound based parsing method can be adapted to non-projective dependency parsing, as well as the k best MST algorithm parsing with non-local features. Non-projective dependency parsing using spanning tree algorithms.	./cache/work_cjz5gcmhlzeylneb6avkrv5bui.pdf	./txt/work_cjz5gcmhlzeylneb6avkrv5bui.txt