Nicolò Cesa-bianchi, Alex Conconi, Claudio Gentile
In this work, we study an information ﬁltering model where the relevance labels associated to a sequence of feature vectors are realizations of an unknown probabilistic linear function. Building on the analysis of a re- stricted version of our model, we derive a general ﬁltering rule based on the margin of a ridge regression estimator. While our rule may observe the label of a vector only by classfying the vector as relevant, experiments on a real-world document ﬁltering problem show that the performance of our rule is close to that of the on-line classiﬁer which is allowed to observe all labels. These empirical results are complemented by a theo- retical analysis where we consider a randomized variant of our rule and prove that its expected number of mistakes is never much larger than that of the optimal ﬁltering rule which knows the hidden linear model.