On Herding and the Perceptron Cycling Theorem

Part of Advances in Neural Information Processing Systems 23 (NIPS 2010)

Bibtex Metadata Paper


Andrew Gelfand, Yutian Chen, Laurens Maaten, Max Welling


The paper develops a connection between traditional perceptron algorithms and recently introduced herding algorithms. It is shown that both algorithms can be viewed as an application of the perceptron cycling theorem. This connection strengthens some herding results and suggests new (supervised) herding algorithms that, like CRFs or discriminative RBMs, make predictions by conditioning on the input attributes. We develop and investigate variants of conditional herding, and show that conditional herding leads to practical algorithms that perform better than or on par with related classifiers such as the voted perceptron and the discriminative RBM.