TAILIEUCHUNG - Báo cáo khoa học: "Top-Down K-Best A∗ Parsing"

We propose a top-down algorithm for extracting k-best lists from a parser. Our algorithm, TKA∗ is a variant of the kbest A∗ (KA∗ ) algorithm of Pauls and Klein (2009). In contrast to KA∗ , which performs an inside and outside pass before performing k-best extraction bottom up, TKA∗ performs only the inside pass before extracting k-best lists top down. TKA∗ maintains the same optimality and efficiency guarantees of KA∗ , but is simpler to both specify and implement. | Top-Down K-Best A Parsing Adam Pauls and Dan Klein Computer Science Division University of California at Berkeley adpauls klein @ Chris Quirk Microsoft Research Redmond WA 98052 chrisq@ Abstract We propose a top-down algorithm for extracting k-best lists from a parser. Our algorithm TKA is a variant of the k-best A KA algorithm of Pauls and Klein 2009 . In contrast to KA which performs an inside and outside pass before performing k-best extraction bottom up TKA performs only the inside pass before extracting k-best lists top down. TKA maintains the same optimality and efficiency guarantees of KA but is simpler to both specify and implement. 1 Introduction Many situations call for a parser to return a k-best list of parses instead of a single best Currently there are two efficient approaches known in the literature. The k-best algorithm of Jimenez and Marzal 2000 and Huang and Chiang 2005 referred to hereafter as Lazy operates by first performing an exhaustive Viterbi inside pass and then lazily extracting k-best lists in top-down manner. The k-best A algorithm of Pauls and Klein 2009 hereafter KA computes Viterbi inside and outside scores before extracting k-best lists bottom up. Because these additional passes are only partial KA can be significantly faster than Lazy especially when a heuristic is used Pauls and Klein 2009 . In this paper we propose TKA a topdown variant of KA that like Lazy performs only an inside pass before extracting k-best lists top-down but maintains the same optimality and efficiency guarantees as KA . This algorithm can be seen as a generalization of the lattice k-best algorithm of Soong and Huang 1991 to parsing. Because TKA eliminates the outside pass from KA TKA is simpler both in implementation and specification. 1See Huang and Chiang 2005 for a review. 2 Review Because our algorithm is very similar to KA which is in turn an extension of the 1-best A parsing algorithm of Klein and Manning 2003

• Báo cáo khoa học
• Top Down 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ữ
• ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Xử lý ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• 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 loại tin tự động
• Tạo chí tin học
• Điều khiển học
• Truy vấn ngôn ngữ tự nhiên
• Phép dịch truy vấn ngôn ngữ tự nhiên
• Truy vấn SQL
• Văn phạm ngữ nghĩa
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Phân tích ngữ nghĩa
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• 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ữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Bài toán PTCP
• Phân tích cú pháp
• 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
• Gán nhãn từ loại
• Ngôn ngữ tự nhiên trong dịch máy
• Hệ thống dịch máy
• Phương pháp xây dựng bảng từ
• Tác từ
• Conditional random fields
• Nhận dạng thực thể có tên
• Đối tượng vật lý trừu tượng
• Phân lớp văn bản
• Biểu diễn nhị phân
• Ma trận từ văn bản
• Wolfram Alpha
• Trích rút thông tin
• Phương pháp Snowball