  With the widespread use of machine learning for classification, it becomes
increasingly important to be able to use weaker kinds of supervision for tasks
in which it is hard to obtain standard labeled data. One such kind of
supervision is provided pairwise---in the form of Similar (S) pairs (if two
examples belong to the same class) and Dissimilar (D) pairs (if two examples
belong to different classes). This kind of supervision is realistic in
privacy-sensitive domains. Although this problem has been looked at recently,
it is unclear how to learn from such supervision under label noise, which is
very common when the supervision is crowd-sourced. In this paper, we close this
gap and demonstrate how to learn a classifier from noisy S and D labeled data.
We perform a detailed investigation of this problem under two realistic noise
models and propose two algorithms to learn from noisy S-D data. We also show
important connections between learning from such pairwise supervision data and
learning from ordinary class-labeled data. Finally, we perform experiments on
synthetic and real world datasets and show our noise-informed algorithms
outperform noise-blind baselines in learning from noisy pairwise data.
