Quadratic Weighted Automata:Spectral Algorithm and Likelihood Maximization

In this paper, we address the problem of non-parametric density estimation on a set of strings $\Sigma^*$. We introduce a probabilistic model - called quadratic weighted automaton, or QWA - and we present some methods which can be used in a density estimation task. A spectral analysis method leads to an effective regularization and a consistent estimate of the parameters. We provide a set of theoretical results on the convergence of this method. Experiments show that the combination of this method with likelihood maximization may be an interesting alternative to the well-known Baum-Welch algorithm.