tailieunhanh - Báo cáo khoa học: "Dynamic Programming for Linear-Time Incremental Parsing"

Incremental parsing techniques such as shift-reduce have gained popularity thanks to their efficiency, but there remains a major problem: the search is greedy and only explores a tiny fraction of the whole space (even with beam search) as opposed to dynamic programming. | Dynamic Programming for Linear-Time Incremental Parsing Liang Huang USC Information Sciences Institute 4676 Admiralty Way Suite 1001 Marina del Rey CA 90292 lhuang@ Kenji Sagae USC Institute for Creative Technologies 13274 Fiji Way Marina del Rey CA 90292 sagae@ Abstract Incremental parsing techniques such as shift-reduce have gained popularity thanks to their efficiency but there remains a major problem the search is greedy and only explores a tiny fraction of the whole space even with beam search as opposed to dynamic programming. We show that surprisingly dynamic programming is in fact possible for many shift-reduce parsers by merging equivalent stacks based on feature values. Empirically our algorithm yields up to a five-fold speedup over a state-of-the-art shift-reduce dependency parser with no loss in accuracy. Better search also leads to better learning and our final parser outperforms all previously reported dependency parsers for English and Chinese yet is much faster. 1 Introduction In terms of search strategy most parsing algorithms in current use for data-driven parsing can be divided into two broad categories dynamic programming which includes the dominant CKY algorithm and greedy search which includes most incremental parsing methods such as Both have pros and cons the former performs an exact search in cubic time over an exponentially large space while the latter is much faster in linear-time and is psycholinguistically motivated Frazier and Rayner 1982 but its greedy nature may suffer from severe search errors as it only explores a tiny fraction of the whole space even with a beam. Can we combine the advantages of both approaches that is construct an incremental parser McDonald et al. 2005b is a notable exception the MST algorithm is exact search but not dynamic programming. that runs in almost linear-time yet searches over a huge space with dynamic programming Theoretically the answer is negative as Lee 2002 shows .

• Báo cáo khoa học
• Dynamic Programming
• Linear Time Incremental Parsing
• Liang Huang
• báo cáo khoa học
• báo cáo ngôn ngữ
• ngôn ngữ tự nhiên
• Phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế giải thuật
• Nguyên tắc của Dynamic Programming
• Yếu tố áp dụng Dynamic Programming
• Biến dạng của Dynamic Programming
• Engineering optimization theory
• Nonlinear programming
• Constrained optimization techniques
• Geometric programming
• Stochastic programming
• Design and Analysis of Algorithms
• Analysis of Algorithms
• Design of Algorithms
• Data structures
• Linear programming
• BMC Bioinformatics
• Dynamic flux balance analysis
• Nonsmooth dynamic systems
• Lexicographic optimization
• Programming languages
• Lecture Programming languages
• Ngôn ngữ lập trình
• Imperative programming
• Imperative languages
• Dynamic allocation
• Object oriented programming
• Lecture Object oriented programming
• Lập trình hướng đối tượng
• Dynamic type information
• Motivation for exception handling
• Static functions
• Dynamic Programming Algorithms
• Transition Based Dependency Parsers
• Marco Kuhlmann
• Adding Syntax to Dynamic Programming
• Aligning Comparable Texts
• the Generation of Paraphrases
• mô hình ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• Optimal Multi Paragraph Text Segmentation
• Oskari Heinonen
• Dynamic programming for parsing
• estimation of stochastic
• unification based grammars
• Cube Summing
• Approximate Inference
• Non Local Features
• Dynamic Programming without Semirings
• scientific reports
• model language
• process natural language
• Linear Text Segmentation
• Dynamic Programming Algorithm
• Fragkou Pavlina
• Algorithm design
• Lecture Algorithm design
• Algorithm analysis
• Weighted interval scheduling
• Knapsack problem
• Hirschbergs algorithm
• Bellman Ford algorithm
• A complete guide to programming in C++
• Overloading operators
• Dynamic memory allocation
• Dynamic members
• Type conversion in class hierarchies
• Abstract classes
• Revenue management
• Approximate dynamic programming
• Airline revenue management problem
• Flight cancellation
• Customer no shows
• Resource scheduling
• Non preemptive case
• Heuristic method
• Heuristic algorithm
• Multi supplier lot sizing strategy using dynamic programming
• Multi supplier lot sizing strategy
• Incremental discount policies
• Two stage supply chain
• công nghệ thông tin
• kỹ thuật lập trình
• tài liệu tin học
• PHP programming dynamic web
• công dụng của các hàm trong PHP
• Read correction
• Semi global alignment
• Algorithm capable
• 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
• Solving optimization problems
• Chain matrix multiplication
• Chain matrix multiplication problem
• Mathematical model