Linear Dynamic Programming and the Training of Sequence Estimators

Abstract We consider the problem of nding an optimal path through a trellis graph when the arc costs are linear functions of an unknown parameter vector. In this context we develop an algorithm, Linear Dynamic Programming (LDP), that simultaneously computes the optimal path for all values of the parameter. We show how the LDP algorithm can be used for supervised learning of the arc costs for a dynamic-programming-based sequence estimator by minimizing empirical risk. We present an application to musical harmonic analysis in which we optimize the per-formance of our estimator by seeking the parameter value generating the sequence best agreeing with hand-labeled data.