Classification from Pairwise Similarity and Unlabeled Data
  Supervised learning needs a huge amount of labeled data, which can be a big
bottleneck under the situation where there is a privacy concern or labeling
cost is high. To overcome this problem, we propose a new weakly-supervised
learning setting where only similar (S) data pairs (two examples belong to the
same class) and unlabeled (U) data points are needed instead of fully labeled
data, which is called SU classification. We show that an unbiased estimator of
the classification risk can be obtained only from SU data, and the estimation
error of its empirical risk minimizer achieves the optimal parametric
convergence rate. Finally, we demonstrate the effectiveness of the proposed
method through experiments.
