Extracting Certainty from Uncertainty: Transductive Pairwise Classification from Pairwise Similarities
Tianbao Yang, Rong Jin · 2016
In this work, we study the problem of transductive pairwise classification from pairwise similarities 1. The goal of transductive pairwise classification from pair-wise similarities is to infer the pairwise class relationships, to which we refer as pairwise labels, between all examples given a subset of class relationships for a small set of examples, to which we refer as labeled examples. We propose a very simple yet effective algorithm that consists of two simple steps: the first step is to complete the sub-matrix corresponding to the labeled examples and the sec-ond step is to reconstruct the label matrix from the completed sub-matrix and the provided similarity matrix. Our analysis exhibits that under several mild precon-ditions we can recover the label matrix with a small error, if the top eigen-space that corresponds to the largest eigenvalues of the similarity matrix covers well the column space of label matrix and is subject to a low coherence, and the number of observed pairwise labels is sufficiently enough. We demonstrate the effectiveness of the proposed algorithm by several experiments. 1