Timezone: »

ShareBoost: Efficient multiclass learning with feature sharing
Shai Shalev-Shwartz · Yonatan Wexler · Amnon Shashua

Tue Dec 13 08:45 AM -- 02:59 PM (PST) @

Multiclass prediction is the problem of classifying an object into a relevant target class. We consider the problem of learning a multiclass predictor that uses only few features, and in particular, the number of used features should increase sub-linearly with the number of possible classes. This implies that features should be shared by several classes. We describe and analyze the ShareBoost algorithm for learning a multiclass predictor that uses few shared features. We prove that ShareBoost efficiently finds a predictor that uses few shared features (if such a predictor exists) and that it has a small generalization error. We also describe how to use ShareBoost for learning a non-linear predictor that has a fast evaluation time. In a series of experiments with natural data sets we demonstrate the benefits of ShareBoost and evaluate its success relatively to other state-of-the-art approaches.

Author Information

Shai Shalev-Shwartz (Mobileye & HUJI)
Yonatan Wexler
Amnon Shashua (Hebrew University of Jerusalem)

More from the Same Authors