Low-Rank Spectral Learning with Weighted Loss Functions.

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

Abstract: Kulesza et al. recently observed that low-rank spectral learning algorithms, which discard the smallest singular values of a moment matrix during training, can behave in unexpected ways, producing models with maximum possible error even when the discarded singular values are infinitesimal. This paper addresses this critical instability by introducing a weighted loss function, providing the first general-purpose error bounds for low-rank spectral learning and transforming a previously unpredictable process into a stable engineering tool.

The Stability Crisis in Spectral Learning

Predictive State Representations (PSRs) are powerful models for dynamical systems—ranging from robotics to meteorology—that represent "state" as a vector of predictions about the future. Unlike Hidden Markov Models (HMMs), which typically rely on iterative, local-optima-prone algorithms like Expectation-Maximization (EM), PSRs can be learned using "spectral" methods. These are fast, closed-form algorithms based on Singular Value Decomposition (SVD).

However, standard spectral learning assumes the practitioner knows the "true" rank of the system. In practice, real-world systems are often high-dimensional or infinite-rank, necessitating a "low-rank" approximation. Previous research demonstrated that this is inherently dangerous: discarding even a tiny singular value during the SVD step can lead to catastrophic model failure. This paper proposes a methodology to fix this instability.

Methods: Weighting and Scale

The authors propose two primary methodological shifts to stabilize the learning process:

  1. Weighted Loss Functions: A low-rank model cannot perfectly capture all sequences. Practitioners must provide a weighting function $w(x)$ to define which predictions matter most (e.g., prioritizing short-term accuracy). This weighting is incorporated directly into the system-dynamics matrix before SVD.
  2. Large Statistics Sets: While previous methods often used small "core" sets of tests (future sequences) and histories (past sequences), this theory suggests that for low-rank learning, larger sets are superior for stability.
Conceptual matrix structures for spectral learning, illustrating the expansion of statistics sets.

The core theoretical contribution is Theorem 1, which proves that the loss of the learned model is bounded by the sum of the squares of the discarded singular values ($\sum_{i=k+1}^\infty \sigma_i^2$). This ensures that if you discard a small amount of information, you receive a proportionally small amount of error.

Empirical Validation

The approach was validated on both synthetic and real-world datasets. Synthetic HMMs were generated with 100 states across three topologies: Random, Ring, and Grid. Additionally, a 1GB Wikipedia corpus was used to test character-level time series prediction, representing a complex system where the true rank is likely enormous.

Key Results

  • Monotonic Improvement: In synthetic tests, the loss of the learned PSR decreased monotonically as the number of histories ($|H|$) increased. This confirms that using more data directly improves the low-rank approximation.
  • Robustness to Noise: The stability held even when statistics were estimated from finite data (ranging from 100 to 10,000 samples) rather than exact probabilities.
Loss vs. history set size (|H|) across different topologies and sample sizes, demonstrating monotonic improvement and stability.
  • Real-World Scaling: On the Wikipedia dataset, increasing the history set size consistently improved the average likelihood of predictions. While increasing model rank generally helps, the authors noted an eventual overfitting point where the model begins to capture noise in the statistics.

Conclusion and Future Work

By introducing weighted loss functions, spectral learning becomes predictable. The weighting function allows practitioners to encode trade-offs inherent in approximation, ensuring the SVD behaves like a stable Hilbert-Schmidt operator.

Future work remains in optimizing the computational cost of decomposing the very large matrices suggested by the theory and developing heuristics for choosing the "best" weighting function for specific application domains.

Summary updated

Abstract

Kulesza et al. recently observed that low-rank spectral learning algorithms, which discard the smallest singular values of a moment matrix during training, can behave in unexpected ways, producing ...
BibTeX
@inproceedings{kulesza2015low,
  author = {Alex Kulesza and Nan Jiang and Satinder P. Singh},
  title = {{Low-Rank Spectral Learning with Weighted Loss Functions.}},
  booktitle = {AISTATS},
  year = {2015},
  url = {https://openreview.net/forum?id=4dhziPL1aY9},
}

Loading related content...

Figure