Learning to Align Sequences: A Maximum-Margin Approach

We propose a discriminative method for learning the parameters of linear se-quence alignment models from training examples. Compared to conventional gen-erative approaches, the discriminative method is straightforward to use when op-erations (e.g. substitutions, deletions, insertions) and sequence elements are de-scribed by vectors of attributes. This admits learning flexible and more complex alignment models. While the resulting training problem leads to an optimization problem with an exponential number of constraints, we present a simple algorithm that finds an arbitrarily close approximation after considering only a subset of the constraints that is linear in the number of training examples and polynomial in the length of the sequences. We also evaluate empirically that the method effectively learns good parameter values while being computationally feasible.