Material Detail

Prediction on a graph

Prediction on a graph

This video was recorded at 6th Slovenian International Conference on Graph Theory, Bled 2007. 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.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.