TAILIEUCHUNG - Báo cáo khoa học: "Speeding Up Full Syntactic Parsing by Leveraging Partial Parsing Decisions"

Parsing is a computationally intensive task due to the combinatorial explosion seen in chart parsing algorithms that explore possible parse trees. In this paper, we propose a method to limit the combinatorial explosion by restricting the CYK chart parsing algorithm based on the output of a chunk parser. When tested on the three parsers presented in (Collins, 1999), we observed an approximate three–fold speedup with only an average decrease of in both precision and recall. | Speeding Up Full Syntactic Parsing by Leveraging Partial Parsing Decisions Elliot Glaysher and Dan Moldovan Language Computer Corporation 1701 N. Collins Blvd. Suite 2000 Richardson TX 75080 eglaysher moldovan @ Abstract Parsing is a computationally intensive task due to the combinatorial explosion seen in chart parsing algorithms that explore possible parse trees. In this paper we propose a method to limit the combinatorial explosion by restricting the CYK chart parsing algorithm based on the output of a chunk parser. When tested on the three parsers presented in Collins 1999 we observed an approximate three-fold speedup with only an average decrease of in both precision and recall. 1 Introduction Motivation Syntactic parsing is a computationally intensive and slow task. The cost of parsing quickly becomes prohibitively expensive as the amount of text to parse grows. Even worse syntactic parsing is a prerequisite for many natural language processing tasks. These costs make it impossible to work with large collections of documents in any reasonable amount of time. We started looking into methods and improvements that would speed up syntactic parsing. These are divided into simple software engineering solutions which are only touched on briefly and an optimization to the CYK parsing algorithm which is the main topic of this paper. While we made large speed gains through simple software engineering improvements such as internal symbolization optimizing critical areas optimization of the training data format et cetera the largest individual gain in speed was made by modifying the CYK parsing algorithm to leverage the decisions of a syntactic chunk parser so that it avoided combinations that conflicted with the output of the chunk parser. Previous Work Chart parsing is a method of building a parse tree that systematically explores combinations based on a set of grammatical rules while using a chart to store partial results. The general

• Báo cáo khoa học
• Speeding Up Full Syntactic Parsing
• Leveraging Partial Parsing Decisions
• Elliot Glaysher and Dan Moldovan
• báo cáo khoa học
• mô hình 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 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