A Multi-Class Linear Learning Algorithm Related to Winnow

Abstract

In this paper, we present Committee, a new multi-class learning algo(cid:173) rithm related to the Winnow family of algorithms. Committee is an al(cid:173) gorithm for combining the predictions of a set of sub-experts in the on(cid:173) line mistake-bounded model oflearning. A sub-expert is a special type of attribute that predicts with a distribution over a finite number of classes. Committee learns a linear function of sub-experts and uses this function to make class predictions. We provide bounds for Committee that show it performs well when the target can be represented by a few relevant sub-experts. We also show how Committee can be used to solve more traditional problems composed of attributes. This leads to a natural ex(cid:173) tension that learns on multi-class problems that contain both traditional attributes and sub-experts.