tailieunhanh - Báo cáo khoa học: "Computational Complexity of Statistical Machine Translation"

In this paper we study a set of problems that are of considerable importance to Statistical Machine Translation (SMT) but which have not been addressed satisfactorily by the SMT research community. Over the last decade, a variety of SMT algorithms have been built and empirically tested whereas little is known about the computational complexity of some of the fundamental problems of SMT. Our work aims at providing useful insights into the the computational complexity of those problems. We prove that while IBM Models 1-2 are conceptually and computationally simple, computations involving the higher (and more useful) models are hard | Computational Complexity of Statistical Machine Translation Raghavendra Udupa U. IBM India Research Lab New Delhi India uraghave@ Hemanta K. Maji Dept. of Computer Science University of Illinois at Urbana-Champaigne Abstract In this paper we study a set of problems that are of considerable importance to Statistical Machine Translation SMT but which have not been addressed satisfactorily by the SMT research community. Over the last decade a variety of SMT algorithms have been built and empirically tested whereas little is known about the computational complexity of some of the fundamental problems of SMT. Our work aims at providing useful insights into the the computational complexity of those problems. We prove that while IBM Models 1-2 are conceptually and computationally simple computations involving the higher and more useful models are hard. Since it is unlikely that there exists a polynomial time solution for any of these hard problems unless P NP and P P P our results highlight and justify the need for developing polynomial time approximations for these computations. We also discuss some practical ways of dealing with complexity. 1 Introduction Statistical Machine Translation is a data driven machine translation technique which uses probabilistic models of natural language for automatic translation Brown et al. 1993 Al-Onaizan et al. 1999 . The parameters of the models are estimated by iterative maximum-likelihood training on a large parallel corpus of natural language texts using the EM algorithm Brown et al. 1993 . The models are then used to decode . translate texts from the source language to the target language 1 2 Tillman 2001 Wang 1997 Germann et al. 2003 Udupa et al. 2004 . The models are independent of the language pair and therefore can be used to build a translation system for any language pair as long as a parallel corpus of texts is available for training. Increasingly parallel corpora are becoming available .

• Báo cáo khoa học
• Computational Complexity
• Statistical Machine Translation
• Raghavendra Udupa
• scientific reports
• model language
• process natural language
• Computational complexity theory
• Basic complexity classes
• The computational model
• Non deterministic Turing machines
• The Cook Levin Theorem
• Time Hierarchy Theorem
• Communication complexity
• Algebraic computation models
• Circuit lower bounds
• The Blum Shub Smale Model
• On the Computational Complexity
• Dominance Links
• Grammatical Formalisms
• báo cáo khoa học
• báo cáo ngôn ngữ
• ngôn ngữ tự nhiên
• CURRENT GPSG THEORY
• Eric Sven
• TWO LEVEL MORPHOLOGY
• G
• Edward Barton
• THE COMPUTATIONAL COMPLEXITY
• AVOIDING CONVERSATIONAL IMPLICATURES
• Ehud Reiterf
• Lecture Data Structures and Algorithms
• Data Structures and Algorithms
• Bài giảng Cấu trúc dữ liệu và thuật toán
• Complexity of Algorithms
• Control structures
• 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
• Time complexity of algorithms
• Asymptotic notations
• expand and improve
• recruit a highly
• skilled and educated
• efforts depend
• community and creating
• attractive business
• BMC Bioinformatics
• Network analysis
• Complexity measure
• Computational algorithm
• Fractal dimension
• Human brain application
• Functional connectivity
• Fundamental data structures
• Cấu trúc dữ liệu và giải thuật
• Analyze the computational complexity
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học
• công trình toán học
• computer engineering
• electrical engineering
• computer organization
• digital logic design
• Computer Architecture
• Language Architecture
• SAT Modulo Theories
• Computational Finance
• Algebra
• Logic
• and Complexity
• Distinguished Papers
• medical analysis
• environmental medicine
• raccoon experiments
• medical knowledge
• medical research
• 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
• Basics of algorithms
• Numeric calculation
• design algorithms
• Physical data design
• program design
• Approximation algorithms
• Heuristic computation
• Heuristic methods
• NP hard problems
• Diameter constrained reliability
• Graph theory
• Non failed links
• Motifs discovery
• PPI interaction network
• Food web network
• Network compression
• Lecture Algorithms
• Bài giảng Thuật toán
• Bottom up mergesort
• Sorting complexity
• Computational infrastructure
• Robot localization
• Computational geometry
• Algorithm complexity
• Approximation algorithm
• Polygon triangulation
• Logging Operations
• Perspective on Membership
• Private Forest
• Owner Cooperative
• Economic Feasibility
• Agroforestry System