CliqueCNN: Deep Unsupervised Exemplar Learning
Exemplar learning is a powerful paradigm for discovering visual similarities in an unsupervised manner. In this context, however, the recent breakthrough in deep learning could not yet unfold its full potential. With only a single positive sample, a great imbalance between one positive and many negatives, and unreliable relationships between most samples, training of Convolutional Neural networks is impaired. Given weak estimates of local distance we propose a single optimization problem to extract batches of samples with mutually consistent relations. Conflicting relations are distributed over different batches and similar samples are grouped into compact cliques. Learning exemplar similarities is framed as a sequence of clique categorization tasks. The CNN then consolidates transitivity relations within and between cliques and learns a single representation for all samples without the need for labels. The proposed unsupervised approach has shown competitive performance on detailed posture analysis and object classification.
This paper proposes an unsupervised learning method for deep networks based on classifying samples into a pre-defined set of cliques. An optimization procedure is proposed to partition the samples into batches that respect the known similarity and dissimilarity relationships between the clique samples, and leave out pairs with unknown relationship. The method is iterated to refine the learned similarity network, starting with HOG-LDA similarity in the first iteration. Results are demonstrated by nearest-neighbor classification using the learned similarity in a number of datasets.
The paper reads well and is technically sound, especially the well-defined optimization problem in Sec. 2.3. The idea of consolidating transitivity relationships into batches is an interesting angle in similarity learning.  Excluding Section 2.3, however, the method as a whole feels a bit ad-hoc. There doesn't seem to be any reason why the assignment to batches could not be performed on samples directly, rather than cliques (other than that it might speed things up). It would make for a more well-justified method to introduced it in terms of the raw individual samples. Using cliques instead of samples could then be presented as an engineering trick to reduce the problem size.  The starting point of the paper seems to be that initial similarities are unreliable, and so there should be no label (training signal) assigned to most of them. It would be more satisfying to relate the optimization objective to this goal explicitly, framing it as an approximation of the full problem if possible.  The paper's presentation is good overall. The description in Section 2.2 is too terse, however, making reproducibility suffer; it is also missing supporting references (e.g. "complete-linkage clustering").  The experiments are adequate, especially the fact that the authors used the learned similarities for nearest-neighbor classification/prediction in challenging tasks. The comparisons with ground-truth nearest-neighbors and supervised methods are especially illuminating, placing the unsupervised learning results into perspective.  However, there could be a better experimental breakdown of the relative contributions of the aspects of the pipeline, since it is hard to untangle the different components. Simply training a classifier on cliques (suggested in line 141, "Forcing them into different classes ...") would be a good measure of the influence of the cliques clustering on the final result. Another important baseline would be training a simple two-stream network end-to-end on the same data. The authors claim that these two approaches would incorporate incorrect relationships, so it is important to show how the proposed method helps in that regard.  It is also debatable whether visualizing merged RGB images really shows that the similarities are meaningful; it is possible there is high pixel-level similarity, but not necessarily semantic similarity. For example, it would be possible for clustering based on RGB values alone to obtain similar visualizations. Another option would be to compute objective measures, like cluster purity, to complement and validate these results.