Nonparametric System identification of Stochastic Switched Linear Systems

Tuhin Sarkar, Alexander Rakhlin, Munther A. Dahleh

System identification—the process of constructing mathematical models of physical systems from observed data—is a cornerstone of modern control theory and machine learning. This paper, titled "Data Driven Estimation of Stochastic Switched Linear Systems of Unknown Order," tackles a particularly difficult class of systems: Stochastic Switched Linear Systems (SLS). These systems are characterized by internal behaviors that change over time based on discrete "modes" or "switches."

The Challenge of Unknown Order and Finite Data

In practical applications like robotics or finance, the internal "state" of a system is often hidden. We only observe inputs and outputs. This leads to two primary hurdles:

  1. Unknown Order: The true dimension ($n$) of the hidden state is rarely known. While a system might be physically complex (high $n$), a lower-order approximation is often sufficient and more robust for control.
  2. Finite-Sample Guarantees: Classical methods often rely on asymptotic results (infinite data). This work focuses on "finite-time" sample complexity: determining how much data is needed to achieve a specific level of model accuracy right now.

Methodology: From Rollouts to Reduced Models

The authors bridge the gap between classical system theory and modern finite-sample analysis using a three-pillared approach.

First, they collect data through simulated rollouts. As shown in Figure 1, the identification process relies on $N_S$ independent trajectories, where each trajectory consists of observed input-output pairs across various switching sequences.

Collection of $N_S$ independent trajectories used for system identification.

Second, they construct a Hankel-like matrix that captures how past inputs influence future outputs across all possible switching sequences. They estimate this matrix using Ordinary Least Squares (OLS) from the noisy rollout data.

Third, they introduce a Data-Dependent Model Selection rule. This is the paper's primary innovation. Because the number of possible switch sequences grows exponentially, the authors develop a rule to decide which parts of the model are "learnable" given the current data. This involves balancing estimation error (noise) against truncation error (the cost of simplifying the model).

Conceptual framework relating the true system $M$ to its estimated reduced-order model $\hat{M}_r(T)$ via data $Z_T$.

As illustrated in Figure 2, the goal is to find an estimate $\hat{M}_r(T)$ that closely approximates the balanced truncated version ($M_r$) of the true high-order system ($M$). Once the Hankel matrix is estimated, Singular Value Decomposition (SVD) is used to extract the system parameters ($A, B, C$), ensuring the resulting model keeps only the most controllable and observable components.

Key Insights: The "Effective" Order

A central theme of the work is that the "true" order of a system is often less important than its "effective" order. If a system's Hankel singular values decay quickly, a low-order model is not just a simplification; it is a statistically sound representation that avoids overfitting to noise.

To manage the exponential explosion of switch combinations, the algorithm intelligently "zeros out" parameters for switch sequences that appear infrequently in the data. The authors prove that these rare sequences contribute negligibly to the overall system dynamics, allowing for efficient estimation without sacrificing significant accuracy.

Results and Performance

The authors provide rigorous proofs for the following:

  • Consistency: As the number of samples ($N_S$) increases, the estimated model converges to a balanced truncated version of the true system.
  • Error Bounds: They derive explicit error rates where the Hankel matrix error scales as $\tilde{O}(N_S^{-\Delta_s/2})$, with $\Delta_s$ being a constant related to system stability.
  • Robustness: The method effectively handles both process disturbances and measurement noise, provided the noise is sub-Gaussian.

Limitations and Future Work

While groundbreaking, the current framework assumes that the switch sequences are observed. In many real-world scenarios, these switches are hidden. Future research directions include combining this subspace approach with clustering methods to handle hidden switches, extending the theory to Markovian or state-dependent switching, and optimizing the computational scaling of the Hankel-like matrix for systems with many modes.

Summary updated

BibTeX
@inproceedings{sarkar2019nonparametric,
  author = {Tuhin Sarkar and Alexander Rakhlin and Munther A. Dahleh},
  title = {{Nonparametric System identification of Stochastic Switched Linear Systems}},
  booktitle = {CDC},
  year = {2019},
  doi = {10.1109/cdc40024.2019.9030173},
}
Figure