State Aggregation Learning from Markov Transition Data
This work addresses the need for data-driven state aggregation in engineering systems, offering a method that reduces reliance on expert knowledge, though it is incremental as it builds on spectral methods with new theoretical guarantees.
The paper tackles the problem of ad hoc state aggregation in model reduction by proposing a tractable algorithm that estimates probabilistic aggregation maps from system trajectories, achieving sharp error bounds for aggregation and disaggregation distributions and anchor state identification. It successfully applies the method to Manhattan traffic data to generate interpretable, data-driven aggregation maps.
State aggregation is a popular model reduction method rooted in optimal control. It reduces the complexity of engineering systems by mapping the system's states into a small number of meta-states. The choice of aggregation map often depends on the data analysts' knowledge and is largely ad hoc. In this paper, we propose a tractable algorithm that estimates the probabilistic aggregation map from the system's trajectory. We adopt a soft-aggregation model, where each meta-state has a signature raw state, called an anchor state. This model includes several common state aggregation models as special cases. Our proposed method is a simple two-step algorithm: The first step is spectral decomposition of empirical transition matrix, and the second step conducts a linear transformation of singular vectors to find their approximate convex hull. It outputs the aggregation distributions and disaggregation distributions for each meta-state in explicit forms, which are not obtainable by classical spectral methods. On the theoretical side, we prove sharp error bounds for estimating the aggregation and disaggregation distributions and for identifying anchor states. The analysis relies on a new entry-wise deviation bound for singular vectors of the empirical transition matrix of a Markov process, which is of independent interest and cannot be deduced from existing literature. The application of our method to Manhattan traffic data successfully generates a data-driven state aggregation map with nice interpretations.