Spectral Learning from a Single Trajectory under Finite-State Policies

Borja Balle, Odalric-Ambrym Maillard
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:361-370, 2017.

Abstract

We present spectral methods of moments for learning sequential models from a single trajectory, in stark contrast with the classical literature that assumes the availability of multiple i.i.d. trajectories. Our approach leverages an efficient SVD-based learning algorithm for weighted automata and provides the first rigorous analysis for learning many important models using dependent data. We state and analyze the algorithm under three increasingly difficult scenarios: probabilistic automata, stochastic weighted automata, and reactive predictive state representations controlled by a finite-state policy. Our proofs include novel tools for studying mixing properties of stochastic weighted automata.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-balle17a, title = {Spectral Learning from a Single Trajectory under Finite-State Policies}, author = {Borja Balle and Odalric-Ambrym Maillard}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {361--370}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/balle17a/balle17a.pdf}, url = {https://proceedings.mlr.press/v70/balle17a.html}, abstract = {We present spectral methods of moments for learning sequential models from a single trajectory, in stark contrast with the classical literature that assumes the availability of multiple i.i.d. trajectories. Our approach leverages an efficient SVD-based learning algorithm for weighted automata and provides the first rigorous analysis for learning many important models using dependent data. We state and analyze the algorithm under three increasingly difficult scenarios: probabilistic automata, stochastic weighted automata, and reactive predictive state representations controlled by a finite-state policy. Our proofs include novel tools for studying mixing properties of stochastic weighted automata.} }
Endnote
%0 Conference Paper %T Spectral Learning from a Single Trajectory under Finite-State Policies %A Borja Balle %A Odalric-Ambrym Maillard %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-balle17a %I PMLR %P 361--370 %U https://proceedings.mlr.press/v70/balle17a.html %V 70 %X We present spectral methods of moments for learning sequential models from a single trajectory, in stark contrast with the classical literature that assumes the availability of multiple i.i.d. trajectories. Our approach leverages an efficient SVD-based learning algorithm for weighted automata and provides the first rigorous analysis for learning many important models using dependent data. We state and analyze the algorithm under three increasingly difficult scenarios: probabilistic automata, stochastic weighted automata, and reactive predictive state representations controlled by a finite-state policy. Our proofs include novel tools for studying mixing properties of stochastic weighted automata.
APA
Balle, B. & Maillard, O.. (2017). Spectral Learning from a Single Trajectory under Finite-State Policies. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:361-370 Available from https://proceedings.mlr.press/v70/balle17a.html.

Related Material