Learning non-Markovian constraints for handwriting recognition

Recently, the horizon of dynamic time warping (DTW) for matching two sequential patterns has been extended to deal with non-Markovian constraints. The non-Markovian constraints regulate the matching in a wider scale, whereas Markovian constraints regulate the matching only locally. The global optimization of the non-Markovian DTW is proved to be solvable in polynomial time by a graph cut algorithm. The main contribution of this paper is to reveal what is the best constraint for handwriting recognition by using the non-Markovian DTW. The result showed that the best constraint is not a Markovian but a totally non-Markovian constraint that regulates the matching between very distant points; that is, it was proved that the conventional Markovian DTW has a clear limitation and the non- Markovian DTW should be more focused in future research.