MULTI-CLASS CLASSIFICATION WITHOUT MULTI- CLASS LABELS
This work presents a new strategy for multi-class classification that requires no class-specific labels, but instead leverages pairwise similarity between examples, which is a weaker form of annotation. The proposed method, meta classification learning, optimizes a binary classifier for pairwise similarity prediction and through this process learns a multi-class classifier as a submodule. We formulate this approach, present a probabilistic graphical model for it, and derive a surprisingly simple loss function that can be used to learn neural network-based models. We then demonstrate that this same framework generalizes to the supervised, unsupervised cross-task, and semi-supervised settings. Our method is evaluated against state of the art in all three learning paradigms and shows a superior or comparable accuracy, providing evidence that learning multi-class classification without multi-class labels is a viable learning option.
This paper proposed how to learn multi-class classifiers without multi-class labels. The main idea is shown in Figure 2, to regard the multi-class labels as hidden variables and optimize the likelihood of the input variables and the binary similarity labels. The difference from existing approaches is also illustrated in Figure 1, namely existing methods have binary classifiers inside multi-class classifiers while the proposed method has multi-class classifiers inside binary classifiers. The application of this technique to three general problem settings is discussed, see Figure 3.
Clarity: Overall, it is very well written. I just have two concerns.
First, the authors didn't discuss the underlying assumption of the proposed method except the additional independence assumption. I think there should be more underlying assumptions. For example, by the definition P(S_{i,j}=0 or 1|Y_i,Y_j) and the optimization of L(theta;X,S), does the "cluster assumption" play a role in it? The cluster assumption is popular in unsupervised/semi-supervised learning and metric learning where the X part of training data is in a form of pairs or triples. However, there is no such an assumption in the original supervised multi-class learning. Without figuring out the underlying assumptions, it is difficult to get why the proposed method works and when it may fail.
Second, there are too many abbreviations without full names, and some of them seem rather important such as KLD and KCL. I think full names of them should be given for the first time they appear. This good habit can make your audience more broad in the long run.
Novelty: As far as I know, the proposed approach is novel. It is clear that Section 3 is original. However, due to the writing style, it is hard to analyze which part in Section 4 is novel and which part is already known. This should be carefully revised in the final version. Moreover, there was a paper in ICML 2018 entitled "classification from pairwise similarity and unlabeled data", in which binary classifiers can be trained strictly following ERM without introducing the cluster assumption. The same technique can be used for learning from pairwise dissimilarity and unlabeled data as well as from pairwise similarity and dissimilarity data. I think this paper should be included in Section 2, the related work. 
Significance: I didn't carefully check all experimental details but the experimental results look quite nice and promising. Given the fact that the technique used in this paper can be applied to many different tasks in machine learning ranging from supervised learning to unsupervised learning, I think this paper should be considered significant.
Nevertheless, I have a major concern as follows. In order to derive Eq. (2), the authors imposed an additional independence assumption: given X_i and X_j, S_{i,j} is independent of all other S_{i',j'}. Hence, Eqs. (2) and (3) approximately hold instead of exactly hold. Some comments should be given on how realistic this assumption is, or equivalently, how close (1) and (3) are. One more minor concern: why P(X) appears in (1) and then disappears in (2) and (3) when Y is marginalized?