Expectation propagation on the diluted Bayesian classifier

Abstract

Efficient feature selection from high-dimensional datasets is a very important challenge in many data-driven fields of science and engineering. We introduce a statistical mechanics inspired strategy that addresses the problem of sparse feature selection in the context of binary classification by leveraging a computational scheme known as expectation propagation (EP). The algorithm is used in order to train a continuous-weights perceptron learning a classification rule from a set of (possibly partly mislabeled) examples provided by a teacher perceptron with diluted continuous weights. We test the method in the Bayes optimal setting under a variety of conditions and compare it to other state-of-the-art algorithms based on message passing and on expectation maximization approximate inference schemes. Overall, our simulations show that EP is a robust and competitive algorithm in terms of variable selection properties, estimation accuracy and computational complexity, especially when the student perceptron is trained from correlated patterns that prevent other iterative methods from converging. Furthermore, our numerical tests demonstrate that the algorithm is capable of learning online the unknown values of prior parameters, such as the dilution level of the weights of the teacher perceptron and the fraction of mislabeled examples, quite accurately. This is achieved by means of a simple maximum likelihood strategy that consists in minimizing the free energy associated with the EP algorithm.

arXiv comment24 pages, 6 figures

References in corpus (18)

• Message Passing Algorithms for Compressed Sensing
• Expectation Propagation for approximate Bayesian inference
• Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence (2001)
• Perturbation Biology: inferring signaling networks in cellular systems
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• A typical reconstruction limit of compressed sensing based on Lp-norm minimization
• A Unified Bayesian Inference Framework for Generalized Linear Models
• Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels
• An analytic approximation of the feasible space of metabolic networks
• Inference algorithms for gene networks: a statistical mechanics analysis
• Bayesian signal reconstruction for 1-bit compressed sensing
• Statistical Mechanical Development of a Sparse Bayesian Classifier
• Compressed sensing reconstruction using Expectation Propagation
• Statistical mechanics of sparse generalization and model selection
• Gene-network inference by message passing
• Statistical mechanics approach to 1-bit compressed sensing
• Classification and sparse-signature extraction from gene-expression data
• Stability of the replica symmetric solution in diluted perceptron learning