TAILIEUCHUNG - Báo cáo khoa học: "Phrase-Based Statistical Machine Translation as a Traveling Salesman Problem"

An efficient decoding algorithm is a crucial element of any statistical machine translation system. Some researchers have noted certain similarities between SMT decoding and the famous Traveling Salesman Problem; in particular (Knight, 1999) has shown that any TSP instance can be mapped to a sub-case of a word-based SMT model, demonstrating NP-hardness of the decoding task. In this paper, we focus on the reverse mapping, showing that any phrase-based SMT decoding problem can be directly reformulated as a TSP. The transformation is very natural, deepens our understanding of the decoding problem, and allows direct use of any of the. | Phrase-Based Statistical Machine Translation as a Traveling Salesman Problem Mikhail Zaslavskiy Mines ParisTech Institut Curie 77305 Fontainebleau France Marc Dymetman Nicola Cancedda Xerox Research Centre Europe 38240 Meylan France @ Abstract An efficient decoding algorithm is a crucial element of any statistical machine translation system. Some researchers have noted certain similarities between SMT decoding and the famous Traveling Salesman Problem in particular Knight 1999 has shown that any TSP instance can be mapped to a sub-case of a word-based SMT model demonstrating NP-hardness of the decoding task. In this paper we focus on the reverse mapping showing that any phrase-based SMT decoding problem can be directly reformulated as a TSP. The transformation is very natural deepens our understanding of the decoding problem and allows direct use of any of the powerful existing TSP solvers for SMT decoding. We test our approach on three datasets and compare a TSP-based decoder to the popular beam-search algorithm. In all cases our method provides competitive or better performance. 1 Introduction Phrase-based systems Koehn et al. 2003 are probably the most widespread class of Statistical Machine Translation systems and arguably one of the most successful. They use aligned sequences of words called biphrases as building blocks for translations and score alternative candidate translations for the same source sentence based on a log-linear model of the conditional probability of target sentences given the source sentence p T a S - exp V Xkhk S a T 1 Zs k where the hk are features that is functions of the source string S of the target string T and of the This work was conducted during an internship at XRCE. alignment a where the alignment is a representation of the sequence of biphrases that where used in order to build T from S The Xk s are weights and ZS is a normalization factor that guarantees .

• Báo cáo khoa học
• Phrase Based Statistical Machine Translation
• Traveling Salesman Problem
• Mikhail Zaslavskiy
• 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