## Prediction on a graph

published: Sept. 7, 2007, recorded: September 2007, views: 7571

# 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**to describe your request and upload the data.**

__ticket system__*Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.*

# Description

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: