Prediction on a graph
published: Sept. 7, 2007, recorded: September 2007, views: 7565
Report a problem or upload filesIf 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.
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 pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !