UC San Diego

This dissertation presents an in-depth analysis of the Predictive State Representation (PSR), a new model for sequence prediction. The key insight behind PSRs is that predictions of some possible future realizations of the sequence can be used to predict the probability of other possible futures. Previous work has shown PSRs are very flexible, and can be trained from data without many of the drawbacks of similar models. I present a rigorous theoretical foundation for understanding these models, and resolve several open problems in PSR theory. I also study multivariate prediction, where the model predicts the values of many random variables. The work presented in this dissertation is the first application of PSRs to modeling multivariate probability distributions. I also perform extensive comparisons of PSR learning algorithms against algorithms for learning other popular prediction models. Surprisingly, the comparisons are not always favorable to PSRs. My empirical results provide an important benchmark for future research on learning PSRs, and my theoretical results may aid development of better learning algorithms