Finite-State Transducers (FST) are a standard tool for modeling paired input-output sequences and are used in numerous applications, ranging from computational biology to natural language processing. Recently Balle et al. presented a spectral algorithm for learning FST from samples of aligned input-output sequences. In this paper we address the more realistic, yet challenging setting where the alignments are unknown to the learning algorithm. We frame FST learning as finding a low rank Hankel matrix satisfying constraints derived from observable statistics. Under this formulation, we provide identifiability results for FST distributions. Then, following previous work on rank minimization, we propose a regularized convex relaxation of this objective which is based on minimizing a nuclear norm penalty subject to linear constraints and can be solved efficiently.

The paper presents a general framework for deriving methods of moments for learning mixture models. Its main contributions are: (1) showing how expressions for the moments of the base distribution can be bootstrapped to derive expressions for the moments of mixtures of base distributions; and, (2) providing recipes for solving the resulting moment equations combining SDP and generalised eigenvalue problems. The overall impression is that the paper does not contain a great deal of technical novelty, but it provides a fresh perspective on moment matching methods for mixture models. The main paper is well-written, but several crucial details are discussed only in the appendix. It is a bit disappointing that the paper pays very little attention to two aspects that initially attracted a lot of attention about spectral methods of moments: the possibility of proving finite-sample bounds, and their scalability as compared to vanilla EM. About the latter, my impression is that obtaining really efficient solutions for the SDP problems arising from different mixture models will require exploiting specific structural properties in each individual case.

Finite-State Transducers (FST) are a standard tool for modeling paired input-output sequences and are used in numerous applications, ranging from computational biology to natural language processing. Recently Balle et al. presented a spectral algorithm for learning FST from samples of aligned input-output sequences. In this paper we address the more realistic, yet challenging setting where the alignments are unknown to the learning algorithm. We frame FST learning as finding a low rank Hankel matrix satisfying constraints derived from observable statistics. Under this formulation, we provide identifiability results for FST distributions.