Scalable algorithms for learning on graphs
published: July 20, 2010, recorded: June 2010, views: 3649
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.
Networked data are found in a variety of domains: Web, social networks, biological networks, and many others. In learning tasks, networked data are often represented as a weighted graph whose edge weights reflect the similarity between incident nodes. In this talk, we consider the problem of classifying the nodes of an arbitrary given graph in the game-theoretic mistake bound model. We characterize the optimal predictive performance in terms of the cutsize of the graph's random spanning tree, and describe a randomized prediction algorithm achieving the optimal performance while running in expected time sublinear in the graph size (on most graphs). These results are then extended to the active learning model, where training labels are obtained by querying nodes selected by the algorithm. We describe a fast query placement strategy that, in the special case of trees, achieves the optimal number of mistakes when classifying the non-queried nodes. Joint work with: Claudio Gentile, Fabio Vitale and Giovanni Zappella.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !