when: July 2, 2014
where: salle plénière
speaker: Mark Herbster
title: A Markov random field approach to online graph label prediction
abstract: In graph label prediction each vertex is labeled with a 0 or 1. The aim is given a partial labeling of the graph to extend to a complete labeling. A common approach to this prediction problem is to relax the labels to [0,1] and then minimize a quadratic*energy* function with respect to a partial labeling and predict with minimizer. This approach is at the core of the very successful techniques in semi-supervised learning of label propagation [ZLG03] and manifold regularization [BN04]. We instead use the unrelaxed labels with an energy function to define a probability distribution over labelings (a Markov Random Field) and then predict by marginalization. The relative drawback of this approach is the computational complexity. We mitigate the problem with an efficient deterministic approximation. For our approximation we prove worst-case online mistake bounds and also show that sequentially our approximate prediction cannot differ from the true marginal prediction very often for “easy’’ problems.
