Graph-based classification for multiple observations of transformed patterns

We consider the problem of classification when multiple observations of a pattern are available, possibly under different transformations. We view this problem as a special case of semi-supervised learning where all the unlabelled samples belong to the same unknown class. We build on graph-based methods for semi-supervised learning and we optimize the graph construction in order to exploit the special structure of the problem. In particular, we assume that the optimal adjacency matrix is a linear combination of all possible class-conditional ideal adjacency matrices. We formulate the construction of the optimal adjacency matrix as a linear program (LP) on the weights of the linear combination. We provide experimental results that show the effectiveness and the validity of the proposed methodology.