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:
- Identifies the subspace of $f(h)$ that is most relevant for prediction.
- Discards irrelevant "noise" or "garbage" features.
- 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.
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.
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