Prediction on a graph

author: Mark Herbster, Department of Computer Science, University College London
published: Sept. 7, 2007,   recorded: September 2007,   views: 7571

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


We will discuss the problem of robust online learning over a graph. Consider the following game for predicting the labeling of a graph. ”Nature” presents a vertex v1; the ”learner” predicts the label of the vertex ˆy1; nature presents a label y1; nature presents a vertex v2; the learner predicts ˆy2; and so forth. The learner’s goal is minimize the total number of mistakes. If nature is adversarial, the learner will always mispredict; but if nature is regular or simple, there is hope that a learner may make only a few mispredictions. Thus, a methodological goal is to give learners whose total mispredictions can be bounded relative to the ”complexity” of nature’s labeling. In this talk, we consider the ”label cut size” as a measure of the complexity of a graph’s labeling, where the size of the cut is the number of edges between disagreeing labels. We will give bounds which depend on the cut size and the (resistance) diameter of the graph.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: