TAILIEUCHUNG - Báo cáo khoa học: "Heuristic Cube Pruning in Linear Time"

We propose a novel heuristic algorithm for Cube Pruning running in linear time in the beam size. Empirically, we show a gain in running time of a standard machine translation system, at a small loss in accuracy. | Heuristic Cube Pruning in Linear Time Andrea Gesmundo Department of Computer Science University of Geneva Giorgio Satta Department of Information Engineering University of Padua satta@ James Henderson Department of Computer Science University of Geneva j Abstract We propose a novel heuristic algorithm for Cube Pruning running in linear time in the beam size. Empirically we show a gain in running time of a standard machine translation system at a small loss in accuracy. 1 Introduction Since its first appearance in Huang and Chiang 2005 the Cube Pruning CP algorithm has quickly gained popularity in statistical natural language processing. Informally this algorithm applies to scenarios in which we have the k-best solutions for two input sub-problems and we need to compute the k-best solutions for the new problem representing the combination of the two sub-problems. CP has applications in tree and phrase based machine translation Chiang 2007 Huang and Chiang 2007 Pust and Knight 2009 parsing Huang and Chiang 2005 sentence alignment Riesa and Marcu 2010 and in general in all systems combining inexact beam decoding with dynamic programming under certain monotonic conditions on the definition of the scores in the search space. Standard implementations of CP run in time O k log k with k being the size of the in-put output beams Huang and Chiang 2005 . Ges-mundo and Henderson 2010 propose Faster CP FCP which optimizes the algorithm but keeps the O k log k time complexity. Here we propose a novel heuristic algorithm for CP running in time O k and evaluate its impact on the efficiency and performance of a real-world machine translation system. 296 2 Preliminaries Let L x0 Xk-1 be a list over R that is an ordered sequence of real numbers possibly with repetitions. We write L k to denote the length of L. We say that L is descending if xi Xj for every i j with 0 i j k. Let L1 x0 Xk-1 and L2 y0 yk -i be two descending .

• Báo cáo khoa học
• Heuristic Cube Pruning
• Linear Time
• Andrea Gesmundo
• báo cáo khoa học
• báo cáo ngôn ngữ
• ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Xử lý ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• 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 loại tin tự động
• Tạo chí tin học
• Điều khiển học
• Truy vấn ngôn ngữ tự nhiên
• Phép dịch truy vấn ngôn ngữ tự nhiên
• Truy vấn SQL
• Văn phạm ngữ nghĩa
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Phân tích ngữ nghĩa
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• 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ữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Bài toán PTCP
• Phân tích cú pháp
• 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
• Gán nhãn từ loại
• Ngôn ngữ tự nhiên trong dịch máy
• Hệ thống dịch máy
• Phương pháp xây dựng bảng từ
• Tác từ
• Conditional random fields
• Nhận dạng thực thể có tên
• Đối tượng vật lý trừu tượng
• Phân lớp văn bản
• Biểu diễn nhị phân
• Ma trận từ văn bản
• Wolfram Alpha
• Trích rút thông tin
• Phương pháp Snowball