Completing State Representations using Spectral Learning.

Nan Jiang, Alex Kulesza, Satinder P. SinghNeurIPS 2018 · OpenReview

Abstract: A central problem in dynamical system modeling is state discovery—that is, finding a compact summary of the past that captures the information needed to predict the future. Predictive State Representations (PSRs) enable clever spectral methods for state discovery; however, while consistent in the limit of infinite data, these methods often suffer from poor performance in the low data regime. In this paper we develop a novel algorithm for incorporating domain knowledge, in the form of an imperfect state representation, as side information to speed spectral learning for PSRs. We prove theoretical results characterizing the relevance of a user-provided state representation, and design spectral algorithms that can take advantage of a relevant representation. Our algorithm utilizes principal angles to extract the relevant components of the representation, and is robust to misspecification. Empirical evaluation on synthetic HMMs, an aircraft identification domain, and a gene splice dataset shows that, even with weak domain knowledge, the algorithm can significantly outperform standard PSR learning.

Introduction

A fundamental challenge in modeling dynamical systems is state discovery: identifying a compact summary of past observations that suffices to predict the future. While Predictive State Representations (PSRs) offer a theoretically grounded framework for this task—amenable to efficient spectral learning—these methods often require large amounts of data to achieve high accuracy. In practical applications, researchers often possess partial domain knowledge or "hunches" about the state (e.g., the importance of the most recent observation), but standard spectral methods are typically "blind" to this side information.

This paper introduces PSR-$f$, a novel framework that incorporates imperfect, user-provided state representations to accelerate spectral learning. By leveraging principal angles to extract relevant components from domain knowledge, PSR-$f$ "completes" the state representation, significantly improving sample efficiency.

The PSR-$f$ Framework

The core idea of PSR-$f$ is to define the state as a concatenation of a user-provided function $f(h)$ of the history $h$ and a learned component that captures the remaining predictive information.

Canonical Angle Algorithm

A key technical hurdle is that user-provided features may be noisy, redundant, or partially irrelevant. To address this, the authors developed a spectral algorithm based on principal angles. By performing a Singular Value Decomposition (SVD) on the relationship between the user's features and future observations, the algorithm:

  1. Identifies the subspace of $f(h)$ that is most relevant for prediction.
  2. Discards irrelevant "noise" or "garbage" features.
  3. Learns a complementary, lower-dimensional PSR state to fill the gaps.

This approach ensures that the model is robust to misspecification; even with weak domain knowledge, the algorithm performs at least as well as a standard PSR.

Experimental Results

Sample Efficiency in Synthetic HMMs

The authors evaluated PSR-$f$ on synthetic Hidden Markov Models (HMMs) with varying topologies. A primary finding is the significant gain in sample efficiency. In regimes where data is scarce, the "shortcut" provided by the relevant components of $f(h)$ allows the model to converge much faster than a standard PSR, which must discover the entire state from scratch.

Relative log-loss vs. sample size. PSR-f (blue) demonstrates superior sample efficiency compared to standard PSR (black) and the provided feature function alone (dotted).

Real-World Application: Gene Splice Classification

To test the algorithm on real-world data, the authors applied PSR-$f$ to a gene splice dataset. The task involves classifying DNA sequences as "positive," "negative," or "neutral" based on nucleotide patterns. By using a simple second-order Markov assumption as the side information $f(h)$, PSR-$f$ outperformed both the standard PSR and a traditional Markov baseline.

Performance on the Gene Splice dataset. PSR-f consistently achieves higher relative log-likelihood across different sequence types compared to standard PSR and Markov baselines.

Conclusion

PSR-$f$ bridges the gap between purely data-driven spectral learning and expert-driven domain modeling. By providing a robust mechanism to "complete" state representations, it enables the training of accurate dynamical models in low-data regimes. Future work may extend this linear algebraic framework to handle highly non-linear domain knowledge through kernel methods or deep feature extractors.

Summary updated

Abstract

A central problem in dynamical system modeling is state discovery—that is, finding a compact summary of the past that captures the information needed to predict the future. Predictive State Representations (PSRs) enable clever spectral methods for state discovery; however, while consistent in the limit of infinite data, these methods often suffer from poor performance in the low data regime. In this paper we develop a novel algorithm for incorporating domain knowledge, in the form of an imperfect state representation, as side information to speed spectral learning for PSRs. We prove theoretical results characterizing the relevance of a user-provided state representation, and design spectral algorithms that can take advantage of a relevant representation. Our algorithm utilizes principal angles to extract the relevant components of the representation, and is robust to misspecification. Empirical evaluation on synthetic HMMs, an aircraft identification domain, and a gene splice dataset shows that, even with weak domain knowledge, the algorithm can significantly outperform standard PSR learning.
BibTeX
@inproceedings{jiang2018completing,
  author = {Nan Jiang and Alex Kulesza and Satinder P. Singh},
  title = {{Completing State Representations using Spectral Learning.}},
  booktitle = {NeurIPS},
  year = {2018},
  url = {https://openreview.net/forum?id=K1Eag_bYtRV},
}
Figure