Poster
Predtron: A Family of Online Algorithms for General Prediction Problems
Prateek Jain · Nagarajan Natarajan · Ambuj Tewari

Thu Dec 10th 11:00 AM -- 03:00 PM @ 210 C #64 #None

Modern prediction problems arising in multilabel learning and learning to rank pose unique challenges to the classical theory of supervised learning. These problems have large prediction and label spaces of a combinatorial nature and involve sophisticated loss functions. We offer a general framework to derive mistake driven online algorithms and associated loss bounds. The key ingredients in our framework are a general loss function, a general vector space representation of predictions, and a notion of margin with respect to a general norm. Our general algorithm, Predtron, yields the perceptron algorithm and its variants when instantiated on classic problems such as binary classification, multiclass classification, ordinal regression, and multilabel classification. For multilabel ranking and subset ranking, we derive novel algorithms, notions of margins, and loss bounds. A simulation study confirms the behavior predicted by our bounds and demonstrates the flexibility of the design choices in our framework.

Author Information

Prateek Jain (Microsoft Research)
Nagarajan Natarajan (UT Austin)
Ambuj Tewari (University of Michigan)

More from the Same Authors