TAILIEUCHUNG - Báo cáo khoa học: "Dynamic Programming Algorithms for Transition-Based Dependency Parsers"

We develop a general dynamic programming technique for the tabulation of transition-based dependency parsers, and apply it to obtain novel, polynomial-time algorithms for parsing with the arc-standard and arc-eager models. We also show how to reverse our technique to obtain new transition-based dependency parsers from existing tabular methods. Additionally, we provide a detailed discussion of the conditions under which the feature models commonly used in transition-based parsing can be integrated into our algorithms. . | Dynamic Programming Algorithms for Transition-Based Dependency Parsers Marco Kuhlmann Dept. of Linguistics and Philology Uppsala University Sweden Carlos Gómez-Rodríguez Departamento de Computación Universidade da Coruna Spain cgomezr@ Giorgio Satta Dept. of Information Engineering University of Padua Italy satta@ Abstract We develop a general dynamic programming technique for the tabulation of transition-based dependency parsers and apply it to obtain novel polynomial-time algorithms for parsing with the arc-standard and arc-eager models. We also show how to reverse our technique to obtain new transition-based dependency parsers from existing tabular methods. Additionally we provide a detailed discussion of the conditions under which the feature models commonly used in transition-based parsing can be integrated into our algorithms. 1 Introduction Dynamic programming algorithms also known as tabular or chart-based algorithms are at the core of many applications in natural language processing. When applied to formalisms such as context-free grammar they provide polynomial-time parsing algorithms and polynomial-space representations of the resulting parse forests even in cases where the size of the search space is exponential in the length of the input string. In combination with appropriate semirings these packed representations can be exploited to compute many values of interest for machine learning such as best parses and feature expectations Goodman 1999 Li and Eisner 2009 . In this paper we follow the line of investigation started by Huang and Sagae 2010 and apply dynamic programming to projective transition-based dependency parsing Nivre 2008 . The basic idea originally developed in the context of push-down automata Lang 1974 Tomita 1986 Billot and Lang 1989 is that while the number of computations of a transition-based parser may be exponential 673 in the length of the input string several portions of these .

• Báo cáo khoa học
• Dynamic Programming Algorithms
• Transition Based Dependency Parsers
• Marco Kuhlmann
• báo cáo khoa học
• báo cáo ngôn ngữ
• ngôn ngữ tự nhiên
• Design and Analysis of Algorithms
• Analysis of Algorithms
• Design of Algorithms
• Data structures
• Linear programming
• Dynamic programming
• Advanced Algorithms Analysis and Design
• Lecture Advanced Algorithms Analysis and Design
• Bài giảng Phân tích và thiết kế thuật toán nâng cao
• Optimal binary search trees
• Constructing dynamic programming
• Greedy algorithms
• Lecture Design and Analysis of Algorithms
• Bài giảng Thiết kế và phân tích thuật toán
• Solving optimization problems
• Chain matrix multiplication
• Chain matrix multiplication problem
• Mathematical model
• 0 1 knapsack problem
• Developing algorithm for knapsack
• 0 1 knapsack problem’s algorithm
• Optimal weight triangulation
• Dynamic Programming Formulation
• Data structures and algorithms in C++
• Priority queues
• Hash tables
• Graph algorithms
• Memory management
• Dynamic programming solution
• Computational cost
• NP complete problems
• Coping with NP completeness
• Quantum algorithms
• Intelligent exhaustive search
• Data structures and algorithms
• Computer science
• Design of data structures
• Algorithms in Java
• 2 line assembly scheduling problem
• Brute force analysis
• C Programming Tutorials
• Algorithms
• Websites Books for ACM
• Valladolid OJ
• ALGORITHMS ANALYSIS
• Knapsack Problem
• Topological Sorting
• WEIGHTED GRAPHS
• Representation
• báo cáo hóa học
• công trình nghiên cứu về hóa học
• tài liệu về hóa học
• cách trình bày báo cáo
• BMC Bioinformatics
• Smith Waterman
• Pairwise sequence alignment
• Multiple sequence alignment
• Xeon Phi clusters
• Algorithm Analysis
• Advanced data structures
• Advanced tree structures
• Analysis techniques
• Patterns of algorithms
• Dynamic Optimization
• Neural Network
• Algorithm Convergence
• Multiobjective Optimization
• Ant Programming
• Green Manufacturing
• Colony Algorithms