Sparse Classifier Design Based on the Shapley Value
Prashanth Ravipally, Dinesh Govindaraj · 2010
Handheld devices like mobile phones have very restricted memory and computation en- vironment. Softwares for Face recognition, Speech recognition, Handwriting recognition etc which are developed for mobile phones need to occupy very less space and should do recognition in real-time. We de- sign a sparse classifier which aids these applications by storing very few vectors, recognizing real-time and still generalizing well. Our Sparse Classifier learns a function that is a weighted sum of basis functions, by sequentially appending functions to an initially empty basis, so that the learnt function minimizes the norm of squared loss to approximate a target func- tion. Selection of a smaller set of basis functions from a dictionary of functions is based on Shapley value, which is a well known solution concept from game theory. The basis functions are selected based on the importance in approximating the decision boundary. We show how our sparse classification model built on kernel-based solutions effectively controls the sparsity of the solution. Experimental comparison with SVMs demonstrate that the proposed model shows compa- rable accuracy in benchmark datasets with very few basis functions resulting in more than 80% reduction in the number of stored vectors.