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.