O. Dekel,
P. M. Long and Y. Singer.
Online learning of multiple tasks with a shared loss.
JMLR, 8:2233-2264, 2007.
(Available
in Postscript and PDF formats.)
Abstract
We study the problem of learning multiple tasks in parallel within the online
learning framework. On each online round, the algorithm receives an instance
for each of the parallel tasks and responds by predicting the label of
each instance. We consider the case where the predictions made on each round
all contribute toward a common goal. The relationship between the various
tasks is defined by a global loss function, which evaluates the overall
quality of the multiple predictions made on each round. Specifically, each
individual prediction is associated with its own loss value, and then these
multiple loss values are combined into a single number using the global loss
function. We focus on the case where the global loss function belongs to the
family of absolute norms, and present several families of online learning
algorithms for the induced problem. We prove worst-case relative loss bounds
for all of our algorithms, and demonstrate the effectiveness of our approach
on a large-scale multiclass-multilabel text categorization problem.