TAILIEUCHUNG - Báo cáo khoa học: "Non-Projective Dependency Parsing in Expected Linear Time"

We present a novel transition system for dependency parsing, which constructs arcs only between adjacent words but can parse arbitrary non-projective trees by swapping the order of words in the input. Adding the swapping operation changes the time complexity for deterministic parsing from linear to quadratic in the worst case, but empirical estimates based on treebank data show that the expected running time is in fact linear for the range of data attested in the corpora. Evaluation on data from five languages shows state-of-the-art accuracy, with especially good results for the labeled exact match score. . | Non-Projective Dependency Parsing in Expected Linear Time Joakim Nivre Uppsala University Department of Linguistics and Philology SE-75126 Uppsala Vaxjo University School of Mathematics and Systems Engineering SE-35195 Vaxjo E-mail Abstract We present a novel transition system for dependency parsing which constructs arcs only between adjacent words but can parse arbitrary non-projective trees by swapping the order of words in the input. Adding the swapping operation changes the time complexity for deterministic parsing from linear to quadratic in the worst case but empirical estimates based on treebank data show that the expected running time is in fact linear for the range of data attested in the corpora. Evaluation on data from five languages shows state-of-the-art accuracy with especially good results for the labeled exact match score. 1 Introduction Syntactic parsing using dependency structures has become a standard technique in natural language processing with many different parsing models in particular data-driven models that can be trained on syntactically annotated corpora Yamada and Matsumoto 2003 Nivre et al. 2004 McDonald et al. 2005a Attardi 2006 Titov and Henderson 2007 . A hallmark of many of these models is that they can be implemented very efficiently. Thus transition-based parsers normally run in linear or quadratic time using greedy deterministic search or fixed-width beam search Nivre et al. 2004 At-tardi 2006 Johansson and Nugues 2007 Titov and Henderson 2007 and graph-based models support exact inference in at most cubic time which is efficient enough to make global discriminative training practically feasible McDonald et al. 2005a McDonald et al. 2005b . However one problem that still has not found a satisfactory solution in data-driven dependency parsing is the treatment of discontinuous syntactic constructions usually modeled by non-projective dependency trees as illustrated in Figure 1. In a projective dependency

• Báo cáo khoa học
• Non Projective Dependency Parsing
• Expected Linear Time
• Joakim Nivre Uppsala
• 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