HKUST's ideal research environment is situated in beautiful Clear Water Bay, Hong Kong.

HLTC Special Seminar Series

Department of Computer Science and Engineering
Department of Electronic and Computer Engineering

Human Language Technology Center

K-best Algorithms in Parsing and Machine Translation

University of Pennsylvania
Joint work with David CHIANG (USC Information Sciences Institute)

Date :     30 July 2007 (Monday)
Time :     10:30-12:00
Venue :   Rm 2578 (Lifts 29-30)


The general idea of k-best search is to find the top k solutions of a given problem, since in many cases the 1-best solution is not guaranteed to be optimal given more (global) information. Recently it has become a popular technique in natural language processing, especially in parsing and machine translation. However, fast and exact k-best algorithms are largely unknown to the NLP community. In this work, we develop a series of efficient algorithms for exact k- best search in the general framework of directed hypergraphs, and demonstrate their performance on state-of-the-art Collins/Bikel parsers.

Since the publication of our paper, these algorithms have been implemented in many widely used systems and packages, including the Charniak parser, the McDonald dependency parser, ISI syntax-based MT system, CMU syntax-based MT system, the Berkeley parser, the Hopkins Dyna language for dynamic programming, and the ISI Tiburon package for tree transducers.

These algorithms have also been successfully applied to search problems in machine translation. In particular, I will talk about an adaptation called "forest rescoring," for decoding with integrated language models, which achieves more than ten fold speed-up against conventional beam search in both phrase-based and syntax-based translation systems.



Liang Huang is finishing his fourth year in the PhD program at the University of Pennsylvania, under Aravind Joshi. He is mainly interested in the theoretical aspects of computational linguistics, in particular, efficient algorithms in parsing and machine translation, and formal properties of synchronous grammars. He also works on applying computational linguistics to structural biology.

*** All are Welcome ***

For enquiries, please call 2358-7008 or visit our website at

Human Language Technology Center
The Hong Kong University of Science & Technology
HKUST, Clear Water Bay, Hong Kong
+852 2358-8831
Last updated: 2007.07.25 Dekai Wu