Distributed learning automata-based scheme for classification using novel pursuit scheme

摘要

Learning Automata (LA) is a popular decision making mechanism to "determine the optimal action out of a set of allowable actions" (Agache and Oommen, IEEE Trans Syst Man Cybern-Part B Cybern 2002(6): 738-749, 2002). The distinguishing characteristic of automata-based learning is that the search for the optimising parameter vector is conducted in the space of probability distributions defined over the parameter space, rather than in the parameter space itself (Thathachar and Sastry, IEEE Trans Syst Man Cybern-Part B Cybern 32(6): 711-722, 2002). Recently, Goodwin and Yazidi pioneered the use of Ant Colony Optimisation (ACO) for solving classification problems (Goodwin and Yazidi 2016). In this paper, we propose a novel classifier based on the theory of LA. The classification problem is formulated as a deterministic optimization problem involving a team of LA that operate collectively to optimize an objective function. Although many LA algorithms have been devised in the literature, those LA schemes are not able to solve deterministic optimization problems as they suppose that the environment is stochastic. In this paper, we develop a novel pursuit LA which can be seen as the counterpart of the family of pursuit LA developed for stochastic environments (Agache and Oommen, IEEE Trans Syst Man Cybern Part B Cybern 32(6): 738-749, 2002). While classical pursuit LA are able to pursue the action with the highest reward estimate, our pursuit LA rather pursues the collection of actions that yield the highest performance. The theoretical analysis of the pursuit scheme does not follow classical LA proofs and can pave the way towards more schemes where LA can be applied to solve deterministic optimization problems. When applied to classification, the essence of our scheme is to search for a separator in the feature space by imposing a LA based random walk in a grid system. To each node in the gird we attach an LA, whose actions are the choice of the edges forming the separator. The walk is self-enclosing, i.e., a new random walk is started whenever the walker returns to starting node forming a closed classification path yielding a multiedged polygon. In our approach, the different LA attached at the different nodes search for a polygon that best encircles and separates each class. Based on the obtained polygons, we perform classification by labelling items encircled by a polygon as part of a class using ray casting function. Seen from a methodological perspective, PolyPursuit-LA has appealing properties compared to SVM. In fact, unlike PolyPursuit-LA, the SVM performance is dependent on the right choice of kernel function (e.g. Linear Kernel, Gaussian Kernel)- which is considered a "black art". PolyPursuit-LA can find arbitrarily complex separators in the feature space. Experimental results from both synthetic and real-life data show that our scheme is able to perfectly separate both simple and complex patterns outperforming existing classifiers, including polynomial and linear SVM, without the need of any "kernel trick". We believe that the results are impressive given the simplicity of PolyPursuit-LA compared to other approaches such as SVM.