LAUSR

This paper proposes a novel classifier based on the theory of Learning Automata (LA), reckoned to as PolyLA. The essence of our scheme is to search for a separator in the feature space by imposing an LA-based random walk in a grid system. To each node in the grid, we attach an LA whose actions are the choices of the edges forming a separator. The walk is self-enclosing, and a new random walk is started whenever the walker returns to the starting node forming a closed classification path yielding a many-edged polygon. In our approach, the different LA attached to the different nodes search for a polygon that best encircles and separates each class. Based on the obtained polygons, we perform classification by labeling items encircled by a polygon as part of a class using a ray casting function. From a methodological perspective, PolyLA has appealing properties compared to SVM. In fact, unlike PolyLA, the SVM performance is dependent on the right choice of the kernel function (e.g., linear kernel, Gaussian kernel)—which is considered a “black art.” PolyLA, on the other hand, can find arbitrarily complex separator in the feature space. We provide sound theoretical results that prove the optimality of the scheme. Furthermore, experimental results show that our scheme is able to perfectly separate both simple and complex patterns outperforming existing classifiers, such as polynomial and linear SVM, without the need to map the problem to many dimensions or to introduce a “kernel trick.” We believe that the results are impressive, given the simplicity of PolyLA compared to other approaches such as SVM.