Spectral Learning of Predictive State Representations with Insufficient Statistics.

Alex Kulesza, Nan Jiang, Satinder P. SinghAAAI 2015 · OpenReview

Predictive State Representations (PSRs) offer a robust framework for modeling dynamical systems by representing state as a vector of predictions about future observable events. Unlike Hidden Markov Models (HMMs), which rely on latent variables, PSRs can be learned through efficient spectral methods. However, a significant challenge arises when the system's complexity exceeds available computational resources, forcing the use of "insufficient" statistics. This paper, presented at AAAI 2015, introduces a novel search algorithm to navigate this constraint.

The Problem: The Complexity Bottleneck

PSRs represent the state of a system as a vector of predictions about future observable events (called tests) conditioned on the past (called histories). The primary advantage of PSRs is their susceptibility to spectral learning—fast, closed-form linear algebra techniques that avoid the slow, iterative convergence issues of HMM training methods like the Expectation-Maximization (EM) algorithm.

However, for spectral learning to be theoretically sound, one must use a "sufficient" set of tests and histories that capture the full linear dimension of the system. In practice, real-world systems are often too complex to be fully captured by finite statistics. Researchers are frequently forced to use small, "insufficient" sets. Until this work, there was little guidance on how to select these sets; the default approach was to use the shortest possible sequences, which often leads to high prediction error.

Methods: The Spectral Bound as a Heuristic

The authors bridge the gap between theory and practice by observing that in an idealized, infinite-data scenario, PSR update matrices ($B_o$) must satisfy a specific spectral property: their largest singular value must be less than or equal to 1 ($\sigma_1(B_o) \le 1$).

While this bound is guaranteed with infinite data and sufficient statistics, it is almost always violated when using small, finite sets. The authors transform this theoretical property into a practical objective function for a local search procedure (Algorithm 1):

  1. Initialize: Start with a basic set of tests and histories (e.g., the shortest ones).
  2. Sample: Randomly select a new candidate test or history.
  3. Evaluate: Temporarily swap it into the current set and calculate the maximum singular value of the resulting update matrices.
  4. Optimize: If the new set results in a lower maximum singular value (bringing it closer to the theoretical ideal), the change is kept.
  5. Repeat: The process continues for a fixed number of rounds.

Key Insights: Beyond Short Sequences

A major finding of the paper is that the common practice of using the shortest available tests and histories is often a poor strategy. These sets frequently produce uninformative predictions. By using the spectral bound as a compass, the search algorithm acts as a form of regularization, steering the model toward stable, physically plausible predictions.

Figure 1: Distribution of L1-error for random sets of statistics compared to the baseline and the proposed algorithm. The algorithm successfully identifies sets in the low-error tail of the distribution.

Furthermore, the algorithm significantly reduces variance. Randomly picking sets of statistics leads to a massive "luck of the draw" effect where error rates vary wildly. As shown in the error distribution, the proposed search algorithm consistently finds sets in the low-error tail of that distribution.

Key Results: Performance and Scalability

The researchers evaluated their approach on synthetic 100-state HMMs and a real-world Wikipedia text prediction task (6.5 million sentences).

  • Synthetic HMMs: In random-topology systems, the proposed method achieved error rates nearly an order of magnitude lower than standard baselines.
  • Wikipedia Task: The algorithm produced meaningfully better $L_1$ accuracy for all prediction lengths greater than one, demonstrating that the heuristic scales to complex, non-synthetic data.
Figure 5: L1-error as a function of prediction length. The proposed algorithm maintains significantly lower error compared to the baseline as the prediction horizon increases.

Limitations and Future Work

The authors acknowledge that their local search is a simple first step. Because it relies on hill-climbing, it could potentially get stuck in local optima. More sophisticated discrete optimization techniques might yield even better sets of statistics. Additionally, while empirical results are strong, providing formal theoretical guarantees for the "insufficient" setting remains a difficult challenge for future learning theory research.

Summary updated

BibTeX
@inproceedings{kulesza2015spectral,
  author = {Alex Kulesza and Nan Jiang and Satinder P. Singh},
  title = {{Spectral Learning of Predictive State Representations with Insufficient Statistics.}},
  booktitle = {AAAI},
  year = {2015},
  url = {https://openreview.net/forum?id=mSnn4px9rrG},
}
Figure