Bandit-based local feature subset selection

In this work we propose a method for local feature subset selection, where we simultaneously partition the sample space into localities and select features for them. The partitions and the corresponding local features are represented using a novel notion of feature tree. The problem of finding an appropriate feature tree is then formulated as a reinforcement learning problem. A value-based Monte Carlo tree search with the corresponding credit assignment policy is devised to learn near-optimal feature trees. Furthermore, the Monte Carlo tree search is enhanced in a way to be applicable for large numbers of actions (i.e., features). This objective is achieved by taking into account a bandit-based explorative policy while having a soft exploitive estimation policy. The results for synthetic datasets show that when local features are present in data, the proposed method can outperform other feature selection methods. Furthermore, the results for microarray classification show that the method can obtain results comparable to the state of the art, using a simple KNN classifier.