WPE II Exam

Dynamic Programming Algorithms in Semiring and Hypergraph Frameworks

Liang Huang

Abstract

Dynamic Programming (DP) is an important class of algorithms widely used in many areas of speech and language processing. Recently there have been a series of work trying to formalize many instances of DP under algebraic or graph-theoretic frameworks. This report surveys two such frameworks, namely semirings and directed hypergraphs, and draws connections between them. We formalize two particular types of DP algorithms under these frameworks: the Viterbi-style fixed-order algorithms and the Dijkstra-style best-first algorithms. Wherever relevant, we also discuss typical applications of these algorithms in Natural Language Processing.

report [PDF]
talk slides [PDF, without animations] [PDF, with animations]

• Sudipto Guha
• Aravind Joshi
• Fernando Pereira (chair)

• Mehryar Mohri (2002). Semiring Frameworks and Algorithms for Shortest-Distance Problems, Journal of Automata, Languages and Combinatorics, 7 (3):321-350.
• Donald Knuth (1977). A Generalization of Dijkstra's Algorithm, Information Processing Letters, 6 (1).
• Mark-Jan Nederhof (2003). Weighted deductive parsing and Knuth's algorithm, Computational Linguistics, 29 (1).

• Joshua Goodman (1999). Semiring Parsing, Computational Linguistics, 25 (4).
• Giorgio Gallo, Giustino Longo and Stefano Pallottino (1993). Directed Hypergraphs and Applications, Discrete Applied Mathematics, 42 (2).
• Lars R. Nielsen, Kim A. Andersen and Daniele Pretolani (2005). Finding the K shortest hyperpaths, Computers and Operations Research, 32 (6).