State Aggregation Learning from Markov Transition Data
State Aggregation Learning from Markov Transition Data
复制标题
DOI：
--
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Yaqi Duan;Z. Ke;Mengdi Wang
中科院分区：
文献类型：
--
作者：
Yaqi Duan;Z. Ke;Mengdi Wang
状态聚合是一种流行的模型简化方法，植根于最优控制。它通过将系统的状态映射到少量的元状态来降低工程系统的复杂性。聚合图的选择通常取决于数据分析师的知识，并且很大程度上是临时的。在本文中，我们提出了一种易于处理的算法，可以根据系统的轨迹估计概率聚合图。我们采用软聚合模型，其中每个元状态都有一个签名原始状态，称为锚定状态。该模型包括几种常见的状态聚合模型作为特例。我们提出的方法是一个简单的两步算法：第一步是经验转移矩阵的谱分解，第二步对奇异向量进行线性变换以找到其近似凸包。它以显式形式输出每个元状态的聚合分布和分解分布，这是经典谱方法无法获得的。在理论方面，我们证明了估计聚合和分解分布以及识别锚状态的尖锐误差范围。该分析依赖于马尔可夫过程的经验转移矩阵的奇异向量的新的条目方向偏差界限，这是独立的兴趣并且不能从现有文献中推导出来。我们的方法对曼哈顿交通数据的应用成功地生成了具有良好解释的数据驱动的状态聚合图。
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.