Unsupervised Spectral Learning of FSTs
Finite-State Transducers (FST) are a standard tool for modeling paired inputoutput sequences and are used in numerous applications, ranging from computational biology to natural language processing. Recently Balle et al.
[4] 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.
This is a rather technical paper that introduces a 
      convex optimization-based (spectral) formulation for unsupervised learning 
      of finite state transducers. Unlike previous spectral approaches, 
      the proposed algorithm does not require explicit alignment information for 
      the input-output pairs in the training data. This causes difficulties in 
      that the Hankel matrix typically used in spectral learning is not fully 
      observed. The main idea of the paper (which was presented before 
      in [3], but in the slightly different setup of missing matrix values due 
      to distribution mismatch), is that instead of using the full matrix, 
      observable statistics can be computed instead that constrain the 
      coefficients of the Hankel matrix. For instance, it is known that the 
      probability of observing a a pair of unaligned input-output sequences is 
      computed by summing over all possible alignments. The main 
      technical contributions of the paper are sample complexity bounds as well 
      as identifiability results for the proposed estimation problem. 
      The experiments are synthetic and do not reveal a lot about the 
      practical viability of the proposed approach. An EM-based approach is 
      shown to outperform the proposed approach in terms of L1 error, but 
      claimed to be more expensive computationally. Actual numbers regarding the 
      computational efficiency of the considered algorithms are not given in the 
      paper. Quality: The proposed approach is backed up by 
      extensive theory. Whether or not the approach is useful in practice is 
      hard to tell from the paper. In this reviewer's opinion, it would have 
      substantially strengthened the submission if more practical experiments 
      had been included in the manuscript. Clearly, FSTs are a very practical 
      construct with numerous applications in NLP and other disciplines, so 
      there is no good excuse for not including such experiments. As it stands, 
      I have to assume that the approach either does not scale to practical 
      amounts of data, or has some other limitations that keep it from being 
      applied to real data. Clarity: Owing to the technical nature 
      of the contents, the manuscript is not an easy read. However, the paper is 
      well-written in general and I recognize that there is no magical way of 
      presenting formal results in an easily comprehensible manner. In any 
      case, the presentation is clear enough to allow for implementation of the 
      learning algorithm, although the experiments section probably lacks 
      sufficient detail in order to allow for reproduction of the results. 
      Originality: The proposed approach follows the same main idea 
      that was already presented in [3]; as such, I consider the present work to 
      be mostly incremental in nature. Significance: Unsupervised 
      training of finite state transducers is an important problem that attracts 
      a lot of attention in the natural language processing community, and 
      deservedly so. Significant advances in this area are bound to have a major 
      impact. However, from the present manuscript, it is not entirely clear 
      whether the proposed approach represent such an 
      advance.