tailieunhanh - Báo cáo khoa học: "K-Best A∗ Parsing"

A∗ parsing makes 1-best search efficient by suppressing unlikely 1-best items. Existing kbest extraction methods can efficiently search for top derivations, but only after an exhaustive 1-best pass. We present a unified algorithm for k-best A∗ parsing which preserves the efficiency of k-best extraction while giving the speed-ups of A∗ methods. Our algorithm produces optimal k-best parses under the same conditions required for optimality in a 1-best A∗ parser. Empirically, optimal k-best lists can be extracted significantly faster than with other approaches, over a range of grammar types. . | K-Best A Parsing Adam Pauls and Dan Klein Computer Science Division University of California Berkeley adpauls klein @ Abstract A parsing makes 1-best search efficient by suppressing unlikely 1-best items. Existing k-best extraction methods can efficiently search for top derivations but only after an exhaustive 1-best pass. We present a unified algorithm for k-best A parsing which preserves the efficiency of k-best extraction while giving the speed-ups of A methods. Our algorithm produces optimal k-best parses under the same conditions required for optimality in a 1-best A parser. Empirically optimal k-best lists can be extracted significantly faster than with other approaches over a range of grammar types. 1 Introduction Many situations call for a parser to return the k-best parses rather than only the 1-best. Uses for k-best lists include minimum Bayes risk decoding Goodman 1998 Kumar and Byrne 2004 discriminative reranking Collins 2000 Char-niak and Johnson 2005 and discriminative training Och 2003 McClosky et al. 2006 . The most efficient known algorithm for k-best parsing Jimenez and Marzal 2000 Huang and Chiang 2005 performs an initial bottom-up dynamic programming pass before extracting the k-best parses. In that algorithm the initial pass is by far the bottleneck Huang and Chiang 2005 . In this paper we propose an extension of A parsing which integrates k-best search with an A -based exploration of the 1-best chart. A parsing can avoid significant amounts of computation by guiding 1-best search with heuristic estimates of parse completion costs and has been applied successfully in several domains Klein and Manning 2002 Klein and Manning 2003c Haghighi et al. 2007 . Our algorithm extends the speed-ups achieved in the 1-best case to the k-best case and is optimal under the same conditions as a stan dard A algorithm. The amount of work done in the k-best phase is no more than the amount of work done by the algorithm of Huang and Chiang 2005 . Our

• Báo cáo khoa học
• K Best A Parsing
• Adam Pauls and Dan Klein
• Long Papers
• báo cáo khoa học
• báo cáo ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Xử lý ngôn ngữ
• Natural Language Processing
• Ngôn ngữ lập trình
• Nhập nhằng cấu trúc
• Tri thức về ngôn ngữ
• Mô hình ngôn ngữ
• Mô hình n gram
• Dịch máy
• Phương pháp dịch máy
• Hiểu ngôn ngữ
• Phân tích ngữ nghĩa
• Phân loại tin tự động
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• Mô hình ngôn ngữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Tách từ tiếng Việt
• Gán nhãn từ loại
• Phân tích cú pháp
• Nghĩa từ vựng
• Phân giải nhập nhằng từ
• Phân loại văn bản
• Lexical chain
• Phản hồi thông tin
• Bài toán PTCP
• Cấu trúc ngữ pháp
• Phân tích cú pháp xác suất
• CKY kết hợp xác suất
• Văn phạm phi ngữ cảnh xác suất
• Hình thái học