Exploiting Cluster Structure to Predict The Labeling of a Graph
published: Dec. 20, 2008, recorded: December 2008, views: 2978
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.
The nearest neighbor and the perceptron algorithms are intuitively motivated by the aims to exploit the "cluster" and "linear separation" structure of the data to be classified, respectively. We develop a new online perceptron-like algorithm, Pounce, to exploit both types of structure. We refine the usual margin-based analysis of a perceptron-like algorithm to now additionally reflect the cluster-structure of the input space. We apply our methods to study the problem of predicting the labeling of a graph. We find that when both the quantity and extent of the clusters are small we may improve arbitrarily over a purely margin-based analysis.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !