Spectral Learning of Sequential Systems
Michael R. Thon · 2018
Stochastic multiplicity automata (SMA) are weighted nondeterministic au- tomata that generalize probabilistic automata and have been used in the context of probabilistic grammatical inference. Observable operator mod- els (OOMs) are a generalization of hidden Markov models, which in turn are models for discrete-valued stochastic processes used ubiquitously in the context of speech recognition and bio-sequence modeling. Predictive state representations (PSRs) extend OOMs to stochastic input-output systems and are employed in the context of agent modeling and planning. In this thesis we first unify these statistical models under the framework of sequential systems (SSs), which are abstract linear algebraic models for certain types of functions on words. The required parts of the theory of SS are presented in a self-contained and easily accessible fashion. We proceed to show how many of the available learning algorithms for these models can be understood as instances of a common learning procedure. Our focus lies on the state-of-the-art spectral learning algorithm. We gen- eralize two recent learning algorithms for OOMs that are based on entirely di↵erent learning principles and show that these are in fact equivalent or closely related to spectral learning. We improve methods for two key steps that are required in all learning algorithms, namely the selection of “charac- teristic” words and of a suitable model dimension. Furthermore, we develop a new weighted spectral learning algorithm that incorporates weights that take the precision of individual estimates into account and show empirically that these modifications indeed improve standard spectral learning. Finally, we address the previously unresolved problem of learning OOMs from data that contains missing values.