  Majority of state-of-the-art deep learning methods are discriminative
approaches, which model the conditional distribution of labels given inputs
features. The success of such approaches heavily depends on high-quality
labeled instances, which are not easy to obtain, especially as the number of
candidate classes increases. In this paper, we study the complementary learning
problem. Unlike ordinary labels, complementary labels are easy to obtain
because an annotator only needs to provide a yes/no answer to a randomly chosen
candidate class for each instance. We propose a generative-discriminative
complementary learning method that estimates the ordinary labels by modeling
both the conditional (discriminative) and instance (generative) distributions.
Our method, we call Complementary Conditional GAN (CCGAN), improves the
accuracy of predicting ordinary labels and can generate high-quality instances
in spite of weak supervision. In addition to the extensive empirical studies,
we also theoretically show that our model can retrieve the true conditional
distribution from the complementarily-labeled data.
