Applications of Dynamic Programming to Speech and Language Processing.

Dynamic Programming (DP) is a mathematical programming technique for solving certain optimization problems. Since its introduction 30 years ago by Bellman, DP has been successfully applied to a number of key areas, including control and communications. In this paper, we focus our discussion on DP applications in the areas of speech and language processing. Due to the sequential nature in speech and language events, most applications can generally be formulated as optimization problems with multiple constraints and many variables. DP can then be used to obtain the solution to those problems by decomposing them into a series of smaller local problems and solve them sequentially. The ways in which the techniques of DP have been applied to speech and language processing are numerous. It is impossible to give adequate treatment to each such application in this paper. Instead, it is our goal to illustrate briefly the basic way in which DP techniques have been applied to several key areas of speech and language research.