Soft Constraint Harmonic Energy Minimization for Transductive Learning and its Two Interpretations

摘要

Using the labeled and unlabeled data to enhance the performance of classification is the core idea of transductive learning. It has recently attracted much interest of researchers on this topic. In this paper, we extend the harmonic energy minimization algorithm and propose a novel transductive learning algorithm on graph with soft label and soft constraint. Relaxing the label to real value makes the transductive problem easy to solve, while softening the hard constraint for the labeled data makes it tolerable to the noise in labeling. We discuss two cases for our algorithm and derive exactly the same form of solution. More importantly, such form of solution can be interpreted from the view of label propagation and a special random walks on graph, which make the algorithm intuitively reasonable. We also discuss several related issues of the proposed algorithm. Experiments on toy examples and real world classification problems demonstrate the effectiveness of our algorithm.