Learning r-of-k functions by boosting

Kohei Hatano, Osamu Watanabe

Research output: Contribution to journalConference articlepeer-review

1 Citation (Scopus)


We investigate further improvement of boosting in the case that the target concept belongs to the class of r-of-k threshold Boolean functions, which answer "+1" if at least r of k relevant variables are positive, and answer "-1" otherwise. Given m examples of a r-of-k function and literals as base hypotheses, popular boosting algorithms (e.g., AdaBoost) construct a consistent final hypothesis by using O(k2 log m) base hypotheses. While this convergence speed is tight in general, we show that a modification of AdaBoost (confidence-rated AdaBoost [SS99] or InfoBoost [As100]) can make use of the property of r-of-k functions that make less error on one-side to find a consistent final hypothesis by using O(kr log m) hypotheses. Our result extends the previous investigation by Hatano and Warmuth [HW04] and gives more general examples where confidence-rated AdaBoost or InfoBoost has an advantage over AdaBoost.

Original languageEnglish
Pages (from-to)114-126
Number of pages13
JournalLecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
Publication statusPublished - 2004
Externally publishedYes
Event15th International Conference ALT 2004: Algorithmic Learning Theory - Padova, Italy
Duration: Oct 2 2004Oct 5 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Learning r-of-k functions by boosting'. Together they form a unique fingerprint.

Cite this