The problem of modeling paired input-output sequences arises in numerous
application areas such as natural language processing, speech recognition and biology. One popular tool for modeling paired input-output sequences is to use Probabilistic Finite-State Transducers (FSTs). Because FSTs induce a
latent state representation they can be very effective in modeling the intrinsic dynamics of input-output sequences. My recent work has focused on studying how FSTs can be used to solve real sequence prediction tasks. This involves developing efficient learning algorithms for inducing FSTs from supervised data.
Most algorithms for FST learning rely on gradient-based or EM optimizations which can be computationally expensive and suffer from local optima issues. In the first part of the talk, I will follow a different approach and present a spectral algorithm for FST learning with strong PAC-style guarantees. At its core, the algorithm is simple and scalable to large data sets. Our approach follows a both recent and no-so-recent line of work which is based on using multiplicity automaton representations of finite state machines. In the second part of the talk, I will discuss ongoing work on using this algorithm for sequence prediction problems in natural language processing and highlight possible uses of FST learning in other application areas .