Label Efficient Learning by Exploiting Multi-class Output Codes
  We present a new perspective on the popular multi-class algorithmic
techniques of one-vs-all and error correcting output codes. Rather than
studying the behavior of these techniques for supervised learning, we establish
a connection between the success of these methods and the existence of
label-efficient learning procedures. We show that in both the realizable and
agnostic cases, if output codes are successful at learning from labeled data,
they implicitly assume structure on how the classes are related. By making that
structure explicit, we design learning algorithms to recover the classes with
low label complexity. We provide results for the commonly studied cases of
one-vs-all learning and when the codewords of the classes are well separated.
We additionally consider the more challenging case where the codewords are not
well separated, but satisfy a boundary features condition that captures the
natural intuition that every bit of the codewords should be significant.
