TAILIEUCHUNG - Báo cáo khoa học: "RELATING COMPLEXITY TO PRACTICAL PERFORMANCE IN PARSING WITH WIDE-COVERAGE UNIFICATION GRAMMARS"

The paper demonstrates that exponential complexities with respect to grammar size and input length have little impact on the performance of three unification-based parsing algorithms, using a wide-coverage grammar. The results imply that the study and optimisation of unification-based parsing must rely on empirical data until complexity theory can more accurately predict the practical behaviour of such parserQ. 1. I N T R O D U C T I O N General-purpose natural language (NL) analysis systems have recently started to use declarative unification-based sentence grammar formalisms; systems of this type include SRI's CLARE system (Alshawi et al | RELATING COMPLEXITY TO PRACTICAL PERFORMANCE IN PARSING WITH WIDE-COVERAGE UNIFICATION GRAMMARS John Carroll University of Cambridge Computer Laboratory Pembroke Street Cambridge CB2 3QG UK jac@cl. cam. ac. uk Abstract The paper demonstrates that exponential complexities with respect to grammar size and input length have little impact on the performance of three unification-based parsing algorithms using a wide-coverage grammar. The results imply that the study and optimisation of unification-based parsing must rely on empirical data until complexity theory can more accurately predict the practical behaviour of such parsers1. 1. INTRODUCTION General-purpose natural language NL analysis systems have recently started to use declarative unification-based sentence grammar formalisms systems of this type include SRI s CLARE system Alshawi et al. 1992 and the Alvey NL Tools ANLT Briscoe et al. 1987a . Using a declarative formalism helps ease the task of developing and maintaining the grammar Kaplan 1987 . In addition to syntactic processing the systems incorporate lexical morphological and semantic processing and have been applied successfully to the analysis of naturally-occurring texts . Alshawi et al. 1992 Briscoe Carroll 1993 . Evaluations of the grammars in these particular systems have shown them to have wide coverage Alshawi et al. 1992 Taylor Grover Briscoe 1989 2. However although the practical throughput of parsers with such realistic grammars is important for example when process 1This research was supported by SERC DTI project 4 1 1261 Extensions to the Alvey Natural Language Tools and by EC ESPRIT BRA-7315 ACQUILEX-IT. I am grateful to Ted Briscoe for comments on an earlier version of this paper to David Weir for valuable discussions and to Hiyan Alshawi for assistance with the CLARE system. 2For example Taylor et al. demonstrate that the ANLT grammar is in principle able to analyse of a corpus of 10 000 noun phrases taken from a variety of corpora.

• Báo cáo khoa học
• RELATING COMPLEXITY
• PRACTICAL PERFORMANCE IN PARSING
• WIDE COVERAGE UNIFICATION GRAMMARS
• 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