tailieunhanh - 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 .