2008 AdvancedDynamicProgramming
- (Huang, 2008) ⇒ Liang Huang. (2008). “Advanced Dynamic Programming in Semiring and Hypergraph Frameworks.” In: COLING 2008 Tutorial Notes.
Subject Headings: Survey Paper, Dynamic Programming, Algorithmic Framework.
Notes
- Notes associated with COLING 2008 Tutorial on “Advanced Dynamic Programming in Computational Linguistics: Theory, Algorithms, and Applications.”
- Tutorial slides: http://www.cis.upenn.edu/~lhuang3/COLING-tutorial-anim.pdf
Cited By
Quotes
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 algorithms under algebraic and graph-theoretic frameworks. This tutorial surveys two such frameworks, namely semirings and directed hypergraphs, and draws connections between them. We formalize two particular types of DP algorithms under each of these frameworks: the Viterbi-style topological algorithms and the Dijkstra-style best-first algorithms. Wherever relevant, we also discuss typical applications of these algorithms in Natural Language Processing.
1. Introduction
Many algorithms in speech and language processing can be viewed as instances of dynamic programming (DP) (Bellman, 1957). The basic idea of DP is to solve a bigger problem by divide-and-conquer, but also reuses the solutions of overlapping subproblems to avoid recalculation. The simplest such example is a Fibonacci series, where each F(n) is used twice (if cached). The correctness of a DP algorithm is ensured by the optimal substructure property, which informally says that an optimal solution must contain optimal subsolutions for subproblems. We will formalize this property as an algebraic concept of monotonicity in Section 2.
This report surveys a two-dimensional classification of DP algorithms (see Table 1): we first study two types of search spaces (rows): the semiring framework (Mohri, 2002) when the underlying representation is a directed graph as in finite-state machines, and the hypergraph framework (Gallo et al., 1993) when the search space is hierarchically branching as in context-free grammars; then, under each of these frameworks, we study two important types of DP algorithms (columns) with contrasting order of visiting nodes: the Viterbi style topological-order algorithms (Viterbi, 1967), and the Dijkstra-Knuth style best-first algorithms (Dijkstra, 1959; Knuth, 1977). This survey focuses on optimization problems where one aims to find the best solution of a problem (e.g. shortest path or highest probability derivation) but other problems will also be discussed.
,
| Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
|---|---|---|---|---|---|---|---|---|---|---|
| 2008 AdvancedDynamicProgramming | Liang Huang | Advanced Dynamic Programming in Semiring and Hypergraph Frameworks | http://www.cis.upenn.edu/~lhuang3/coling.pdf |