Research On Obtaining Predictive State Representations With State Space Partitioning

Predictive State Representation (PSR) is an efficient way for modeling dynamical systems. Compared to other modeling methods, PSR, which represents state using only observable data, has greater expressive power and learning PSR models of dynamical systems should be easier. However, current research methods in PSR mostly focus on learning a model based on the entire state space. Commonly, it is difficult to obtain the PSR model by using traditional technique. The existing algorithms for building PSR models of dynamical systems are usually only applied to small scale systems.In this thesis, the entire state space of a dynamical system is partitioned into sub-state spaces by the mechanism of state space partitioning, which reduces the difficulty to learn the PSR model of a dynamical system. And then, an algorithm for learning the PSR model of a system based on state space partitioning and an algorithm for learning the Transformed Predictive State Representation (TPSR) model of a system based on state space partitioning are proposed. Therefore, our algorithms in this paper put forward a possible solution to obtain the complete PSR model of a relatively large scale dynamical system.The main research and achievements of this thesis are summarized as follows:(1) A mechanism for partitioning state space is proposed. In general terms, with the increasing scale of a dynamical system, the states of the system accordingly increase. The entire state space is partitioned into sub-state spaces by using the identified landmarks as the critical points. Then, the number of states in each sub-state space is generally smaller than the number of states in the entire state space. We only need to learn every sub-state space’s PSR model separately, which is easier than learning the model on the entire state space. Consequently, the mechanism for partitioning state space reduces the difficulty of obtaining the complete PSR model of a dynamical system.(2) An algorithm for learning the PSR model of a system based on state space partitioning is proposed. The entire state space of a dynamical system is partitioned into sub-state spaces by the mechanism of state space partitioning. And then traditional technique is used to learn every sub-state space’s PSR model. According to these local PSR models, we can produce the complete PSR model of the system, which can be used to predict any events. The simulation experiment results show that the proposed algorithm is effective.(3) An algorithm for learning the TPSR model of a system based on state space partitioning is proposed. Due to the expansion of a dynamical system, the time complexity and computation of discovering core tests also usually escalate accordingly. In order to reduce the complexity to obtain one PSR model further, this paper introduces Principal Component Analysis (PCA) and then presents an algorithm for learning the TPSR model of a system based on state space partitioning. In the algorithm, without the process of discovering core tests, we use PCA to reduce the dimensions of histories-tests matrixes and then learn every sub-state space’s TPSR model, which makes learning predictive state representation simplified further. The empirical results prove the effectiveness of the proposed algorithm.