Graph Transduction via Alternating Minimization

author: Jun Wang, Department of Electrical Engineering, Columbia University
published: Aug. 1, 2008,   recorded: July 2008,   views: 228
Categories
You might be experiencing some problems with Your Video player.
Lecture popularity: You need to login to cast your vote.
 
    Delicious Bibliography

Description

Graph transduction methods label input data by learning a classification function that is regularized to exhibit smoothness along a graph over labeled and unlabeled samples. In practice, these algorithms are sensitive to the initial set of labels provided by the user. For instance, classification accuracy drops if the training set contains weak labels, if imbalances exist across label classes or if the labeled portion of the data is not chosen at random. This paper introduces a propagation algorithm that more reliably minimizes a cost function over both a function on the graph and a binary label matrix. The cost function generalizes prior work in graph transduction and also introduces node normalization terms for resilience to label imbalances. We demonstrate that global minimization of the function is intractable but instead provide an alternating minimization scheme that incrementally adjusts the function and the labels towards a reliable local minimum. Unlike prior methods, the resulting propagation of labels does not prematurely commit to an erroneous labeling and obtains more consistent labels. Experiments are shown for synthetic and real classification tasks including digit and text recognition. A substantial improvement in accuracy compared to state of the art semi-supervised methods is achieved. The advantage are even more dramatic when labeled instances are limited.

  Join a Study Group

OpenStudy logo

You reached a lecture within the PASCAL NoE project video collection. Click on the logo and go to the Computer Science classroom on OpenStudy. Through this classroom, you can meet other students interested in the same problems and work together on assignments, ask each other questions or just discuss the topics of the lecture.

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:

make sure you have javascript enabled or clear this field: