We present a new algorithm, filter tree, for reducing (cost
sensitive) multiclass classification to binary classification.  The
filter tree is provably consistent---optimal binary
classification implies optimal multiclass classification.  (The
common tree-based approach is provably inconsistent.)

Amongst all known methods, the filter tree is robust.  It
suffers multiclass regret at most $log_2 k$ times the binary regret
where $k$ is the number of multiclass labels.  This improves on all
previous known methods.

A variant of the filter tree can also be used for cost sensitive
multiclass classification, where each possible class has a cost
associated with it.  Used in this way, the robustness dependence on
problem characteristics is better than previous methods.