Graph-based classification for multiple observations of transformed patterns

We consider the problem of classification when mul-tiple 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 con-struction in order to exploit the special structure of the problem. In particular, we assume that the optimal ad-jacency matrix is a linear combination of all possible class-conditional ideal adjacency matrices. We formu-late the construction of the optimal adjacency matrix as a linear program (LP) on the weights of the linear com-bination. We provide experimental results that show the effectiveness and the validity of the proposed methodol-ogy.