Efficiency versus convergence of boolean kernels for on-line learning algorithms

Roni Khardon, Dan Roth, Rocco Servedio

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We study online learning in Boolean domains using kernels which capture feature expansions equivalent to using conjunctions over basic features. We demonstrate a tradeoff between the computational efficiency with which these kernels can be computed and the generalization ability of the resulting classifier. We first describe several kernel functions which capture either limited forms of conjunctions or all conjunctions. We show that these kernels can be used to efficiently run the Perceptron algorithm over an exponential number of conjunctions; however we also prove that using such kernels the Perceptron algorithm can make an exponential number of mistakes even when learning simple functions. We also consider an analogous use of kernel functions to run the multiplicative-updateWinnow algorithm over an expanded feature space of exponentially many conjunctions. While known upper bounds imply that Winnow can learn DNF formulae with a polynomial mistake bound in this setting, we prove that it is computationally hard to simulate Winnow's behavior for learning DNF over such a feature set, and thus that such kernel functions for Winnow are not efficiently computable.

Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems 14 - Proceedings of the 2001 Conference, NIPS 2001
PublisherNeural information processing systems foundation
ISBN (Print)0262042088, 9780262042086
StatePublished - 2002
Event15th Annual Neural Information Processing Systems Conference, NIPS 2001 - Vancouver, BC, Canada
Duration: Dec 3 2001Dec 8 2001

Publication series

NameAdvances in Neural Information Processing Systems
ISSN (Print)1049-5258


Other15th Annual Neural Information Processing Systems Conference, NIPS 2001
CityVancouver, BC

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing


Dive into the research topics of 'Efficiency versus convergence of boolean kernels for on-line learning algorithms'. Together they form a unique fingerprint.

Cite this