Research On Obtaining Predictive State Representation And Feature Selection With Monte Carlo Tree Search Algorithm

In recent years,Monte Carlo Tree Search(MCTS)has become the focus of research in artificial intelligence field.It has been widely used in computer games,especially in computer Go.The basic idea of the MCTS algorithm is to construct the search tree iteratively with using the node to represent the state and the directed link to the child node represent the action.Then find the best decision in the given domain.During each iteration,tree policy are used to balance the exploration and exploitation of nodes,and the default policy is used to run the simulation to generate estimates,and then update the estimates to the search tree.The MCTS algorithm relies on less a priori knowledge to quickly focus on the most valuable parts of the search space through real-time statistics and can effectively deal with large-scale system decision-making problems.Based on the advantages of MCTS algorithm in dealing with large-scale complex system problems,MCTS algorithm is used to learning predictive state representation(PSR)of dynamic system and high-dimensional data feature selection.The PSR model uses a set of fully observable quantities called tests to represent the state of the system.Compared with other modeling methods,PSR has the advantages of easy learning model,less prior knowledge and expressive ability,and is an effective method for modeling local dynamic system.One of the core problems in establishing the PSR model is to discover the test core of the system,but the existing approach to the problem does not apply to large-scale systems.The first major work of this paper is to use the advantages of MCTS algorithm which is suitable for the large-scale complex system,to study the new method of discovering based on MCTS algorithm,and then learn large-scale system PSR model.Since the MCTS is suitable for finding the best strategy in sequential decision problems,it is clear that the problem of finding the test core is very different.In this paper,we first formalize the discovery problem as a sequential decision making problem,and then put forward the concept of model entropy which can measure the accuracy of the model,and use the model entropy as the evaluation function to successfully use the MCTS algorithm for processing discovery issue.The feature selection method does not change the original feature space to eliminate irrelevant or redundant information,and retain the information with high relevance of the sorting task.It is an effective method to reduce dimensionality of high dimensional data.Compared with the dimensionality reduction algorithm,the feature selection algorithm can keep the data accurate and easy to understand,and the computational complexity is relatively low and the operation efficiency is high.Therefore,it is of great significance and value to study the feature selection method of high dimensional data efficiently.The second major work of this paper is to study the application of MCTS to high dimensional data feature selection.The order decision problem and the feature selection problem of MCTS are also very different.For this reason,we first formalize the feature selection problem as a sequential decision making problem,then uses the classification weight calculated by Relief algorithm to measure the feature classification correlation,and uses the Relief algorithm as the evaluation function to successfully apply the MCTS to the feature selection problem.