Label Efficient Learning by Exploiting Multi-class Output Codes
This work addresses label efficiency in multi-class learning, offering theoretical insights and algorithms, but it appears incremental as it builds on existing output code techniques.
The paper connects multi-class output codes (like one-vs-all) to label-efficient learning, showing that their success implies structured class relationships, and designs algorithms to recover classes with low label complexity in realizable and agnostic cases.
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.