DHOG: Deep Hierarchical Object Grouping
Authors: Luke Nicholas Darlow
Amos Storkey
Venue:  (2021)
Keywords: Unsupervised learning
Deep neural networks
clustering

Abstract: Unsupervised learning of categorical representations using data augmentations appears to be a promising approach and has proven useful for finding suitable representations for downstream tasks. However current state-of-the-art methods require preprocessing (e.g. Sobel edge detection) to work. We introduce a mutual information minimization strategy for unsupervised learning from augmentations, that prevents learning from locking on to easy to find, yet unimportant, representations at the expense of more informative ones requiring more complex processing. We demonstrate specifically that this process learns representations which capture higher mutual information between augmentations, and demonstrate that these representations are better suited to the downstream exemplar task of clustering. We obtain substantial accuracy improvements on CIFAR-10, CIFAR-100-20, and SVHN.

Under review as a conference paper at ICLR 2021
DHOG: DEEP HIERARCHICAL OBJECT GROUPING
Anonymous authors Paper under double-blind review
ABSTRACT
Unsupervised learning of categorical representations using data augmentations appears to be promising approach and has proven useful for finding suitable representations for downstream tasks. However current state-of-the-art methods require preprocessing (e.g. Sobel edge detection) work. We introduce mutual information minimization strategy for unsupervised learning from augmentations, that prevents learning from locking on easy to find, yet unimportant, representa- tions at the expense of more informative ones requiring more complex processing. We demonstrate specifically that this process learns representations which capture higher mutual information between augmentations. and demonstrate that these representations are better suited to the downstream exemplar task of clustering. We obtain substantial accuracy improvements on CIFAR-10, CIFAR-100-20, and SVHN.
INTRODUCTION
It is very expensive to label a dataset with respect to a particular task. Consider the alternative where user, instead of labelling a dataset, specifies simple set of class-preserving transformations or 'augmentations'. For example. lighting changes will not change a dog into cat. Is it possible to learn model that produces useful representation by leveraging set of such augmentations? This representation would need to be good at capturing salient information about the data, and enable downstream tasks to be done efficiently. If the representation were a discrete labelling which groups the dataset into clusters, obvious choice of downstream task is unsupervised clustering. Ideally the clusters should match direct labelling, without ever having been learnt on explicitly labelled data.
Using data augmentations to drive unsupervised representation learning for images has been ex- plored by a number of authors (Dosovitskiy et al.) 2014 2013: Bachman et al. 2019; Chang et al.) 2017 Wu et al., 2019 Ji et al. 2019; Cubuk et al. 2019). These approaches typically involve learn- ing neural networks that map augmentations of the same image to similar representations, which is reasonable since variances across many common augmentations often align with the invariances
would require.
A number of earlier works target maximising mutual information (MI) between augmentations (van den Oord et al.) 2018 Hjelm et al., 2019) Wu et al., 2019 Ji et al., 2019; Bachman et al.) 2019). Targetting high MI between representations computed from distinct augmentations enables learning representations that capture the invariances induced by the augmentations. We are inter- ested in a particularly parsimonious representation: discrete labelling of the data. This labelling can be seen as clustering (Ji et al. 2019) procedure, where MI can be computed and assessment can be done directly using the learned labelling, as opposed to via an auxiliary network trained posthoc.
1.1 SUBOPTIMAL MUTUAL INFORMATION MAXIMISATION
We argue and show that the MI objective is not maximised effectively in existing work due to the combination of:
1. Greedy optimisation algorithms used to train neural networks, such stochastic gradient descent (SGD) that potentially target local optima; and
2. A limited set data augmentations that can result in the existence of multiple local optima to the MI maximisation objective.

---

Under review as a conference paper at ICLR 2021
SGD is greedy in the sense that early-found high-gradient features can dominate and networks will tend to learn casier-to-compure locally-optimal representations (for example, one that can be computed using fewer neural network layers) over those that depend on complex features.
By way of example, in natural images, average colour is an casy-to-computc characteristic, whereas object type is not. If the augmentation strategy preserves average colour, then reasonable mapping need only compute colour information, and high MI between learned image representations will be obtained. This result suboptimal in the sense that hypothetical higher MI optima exists that also captures semantic information, assuming the model has sufficient capacity to learn and repre- sent this. The conceivable existence of many such local optima coupled with greedy optimisation presents challenge: how can we leverage powerful image augmentation- driiven MI objectives while avoiding greedity-fownd local optima?
Dealing with greedy solutions Heuristic solutions, such as Sobel edge-detection (Caron al. 2018 Ji et al. 2019) as a pre-processing step, have been suggested to remove/alter the features in images that may cause trivial representations to be learned. This is symptomatic treatment and not a solution. In the work presented herein, we acknowleds ledge that greedy SGD can get stuck in local optima of the MI maximisation objective because of limited data augmentations. Instead of trying to prevent a greedy solution, our technique lets a model learn this representation, but also requires it to learn an additional distinct representation. Specifically, we minimise the MI between these two representations so that the latter cannot rely on the same features. We extend this idea by adding representations, each time requiring the latest to be distinct from all previous representations.
clustering For this work, focus is finding higher MI representations; we then assess the downstream capability on the ground truth task of image classification, meaning that we can either (1) learn a representation that must be 'decoded' via an additional learning step, or (2) produce a discrete labelling that requires no additional learning. Clustering methods offer a direct comparison and require no labels for learning a mapping from the learned representation to class labels. Instead, labels are only required to assign groups to appropriate classes and no learning done using these. Our comparisons are with respect to clustering methods.
Downstream task:
1.2 CONTRIBUTIONS
Learning a set of representations by encouraging them to have low MI, while still maximising the original sugmentation-ddrien MI objective for each representation, is the core idea behind Deep Hierarchical Object Grouping (DHOG). We define a mechanism to produce a set of hicrarchically- ordered solutions (in the sense of easy-to-hard orderings, not tree structures). DHOG is able to better maximise the original MI objective between augmentations since each representation must correspond to unique local optima. Our contributions are:
1.
We demonstrate that current methods do not effectively maximise the MI objective] be- cause greedy stochastic gradient descent (SGD) typically results in suboptimal local op- tima. To mitigate for this problem, we introducing DHOG: robust neural network image grouping method to learn diverse and hierarchically arranged sets of discrete image la- bellings (Section 3 by explicitly modelling, accounting for, and avoiding spurious local optima, requiring only simple data augmentations, and needing no Sobel edge detection.
2. We show marked improvement over the current state-of-the-art for standard benchmarks in end-to-end image clustering for CIFAR-10. CIFAR- 100-20 (a 20-way class grouping of CIFAR- 100, and SVHN; we set a new accuracy benchmarks on CINIC- and show the utility of our method on STL-10 (Section 4
To be clear, DHOG still learns to map data augmentations to similar representations as this is imper- ative the learning process. The difference is that DHOG enables number of intentionally distinct data labellings to be learned, arranged hierarchically in terms of source feature complexity.
We show this by finding higher mutual information solutions using DHOG, rather than by any analysis of the solutions themselves.
2

---

Under review as a conference paper at ICLR 2021
2 RELATED WORK
The idea of MI maximisation for representation learning is called the infoMAX principle (iinkerr
1988
Tschannen et al. 2019). Contrastive predictive coding (van den Oord et al., 2018) (CPC)
models a 2D latent space using an autoregressive model and defines a predictive setup to maximise
MI between distinct spatial locations. Deep InfoMAX (Hjelm et al. 2019) (DIM) does not maximise MI across a set of data augmentations, but instead uses mutual information neural estimation (Bel-) 2018) and negative sampling to balance maximising MI between global representations and local representations. Augmented multiscale Deep InfoMAX (Bachman et al. (219)) (AMDIM) incorporates MI maximisation across data augmentations and multiscale comparisons.
ghazi et al.
Clustering approaches are more directly applicable for comparison with DHOG because they ex- plicitly learn discrete labelling. The authors of deep embedding for clustering (DEC) (Xie et al.] 2016) focused their attention on jointly learning an embedding suited to clustering and a clustering itself. They argued that the notion of distance in the feature space is crucial to a clustering objec- tive. Joint unsupervised learning of deep representations and image clusters (JULE) (Yang et al. 2016 provided supervisory signal for representation learning. Some methods (Ghasedi Dizaji et al,, 2017 Fard al. 2018) employ autoencoder architectures along with careful regularisation of clus- ter assignments to (I) ensure sufficient information retention, and (2) avoid cluster degeneracy (i.e.. mapping all images to the same class).
Deep adaptive clustering (Chang et al. 2017) (DAC) recasts the clustering problem as binary pair- wise classification, pre-selecting comparison samples via feature cosine distances. constraint on the DAC system allows for a one-hot encoding that avoids cluster degeneracy. Another mechanism for dealing with degeneracy is to use a standard clustering algorithm, such as K-means iteratively group on learned features. This approach is used by DeepCluster (Caron et al. 2018).
Associative deep clustering (ADC) (Haeusser et al. 2018) uses the idea that associations in the embedding space are useful for learning. A network was learned to associate data with (pseudo- labelled) centroids. They leveraged augmentations by encouraging samples to output similar cluster probabilities.
Deep comprehensive correlation mining (Wu et al., 2019) (DCCM) constructs a sample correlation graph for pseudo-labels and maximises the MI between augmentations, and the MI between local and global features for each augmentation. While many of the aforementioned methods estimate MI in some manner, invariant information clustering (Ji et al.) 2019) (IIC) directly defines the MI using the c-way softmax output (i.e., probability of belong to class c), and maximises this over data aug- mentations to learn clusters. They effectively avoid degenerate solutions because MI maximisation implicitly targets marginal entropy. We use the same formulation for MI in Section
METHOD
Figure [ shows the DHOG architecture. DHOG is approach for obtaining jointly trained multi- level representations as discrete labellings, arranged in a simple-to-comples hierarchy, and com- puted by separate 'heads'. A head an unit that computes multivariate class probability vector. By requiring low MI between heads, a diversity of solutions to the MI maximisation objective can be found. The head that best maximises MI between augmentations typically aligns better with a ground truth task that also relies on complex features that augmentations are designed to preserve.
Figure I demonstrates the DHOG architecture and training principles. There are shared model weights ② ResNet blocks 1, 2, and 3) and head-specific weights (the MI. layers and @: ResNet blocks 4 to 8). For the sake of brevity, we abuse notation and use MT(z, z') between labelling probability vectors
overloaded shorthand for the mutual information MI(c, c') between the labelling random variables c and c' that have probability vectors Z and z' respectively.
Any branch of the DHOG architecture ( to any z;) can be regarded as single neural network. These are trained to maximise the MI between the label variables at each head for different augmen- tations; i... between label variables with probability vectors (x) and 2, (x') for augmentations and x'. Four augmentations are shown at O. The MI is maximised pairwise between all pairs, at O This process can be considered pulling the mapped representations together.
3

---

Under review as a conference paper at ICLR 2021
Betched sigmentatone
MUP
ResNet block
f4
ME
Res block
-dM Faa
hy
MLP
-MM
Rea block
ResNet blocks
hl
MUP
h2
MLP
RouNer blook
hts
ResNet block
h6
Minmise
MM FL)
Mila |x xx (
ResNet block
hy
2; x
x
Maximice:
MIi 1x
ResNet block
ha
MLP
Figure 1: DHOG architecture. The skeleton is a ResNet18 (He et al., 2016). The final ResNet block repeated i 3 times (k here). I Augmentations of each image, x are separately processed by the network. @ Each shallow ResNer block .1 constitutes shared computation for deeper blocks, while also computing separate probability vectors, 21 .I...Z3. Each z; is viewed as the probability for each outcome of the random variable e; that makes discrete labelling choice. O The deepest ResNet blocks compute further Z>3. 4 The network trained by maximising the MI between allocations c; from all data augmentations, and ( separately for each node i, minimising the MI between 6; and Cei for the same data augmentation. K This is implemented by stopping gradients such that they are back-propagated for later computation paths (red crosses).
Following ICC (Ji et al. 2019), we compute the MI directly from the label probability vectors within minibatch. Let z,, z denote the random probability vectors head i associated with sampling data item and its augmentations, and passing those through the network. Then we can compute the mutual MI between labels associated with each augmentation using
Mlaug (ci, 4) (Z)) log (l(z (z))))
(1)
Elz log E[z.] E[(2)* log E((2)),
where Tr is the matrix trace, logarithms computed element- wise, and expectations data samples and augmentations of each sample. In practice we compute an empirical estimate this MI based on samples from minibatch.
3.1 DISTINCT HEADS
Each clustering head in DHOG is encouraged to compute unique solutions via cross-head MI min- imisation. For minibatch of images, the labelling from any head is optimised have low MI with other heads' labellings. We assume multiple viable labellings because of natural patterns in the data. By encouraging low MI between heads, these must capture different patterns in the data.
Simple concepts (brightness, colour, etc.) are axes of variation that are reasonable and easy to group by. Groupings according to complex features (e.g., object type) typically require more processing and greedy optimisation may not discover these groupings without explicit encouragement, Unfor- tunately, the easier-to-comput to-compute groupings typically correspond poorly downstream tasks. Without a mechanism to explore viable patterns in the data, greedy optimisation will avoid finding them.
Cross-head MI minimisation We address suboptimal MI maximisation by encouraging unique solutions at sequential heads (z) Zs in Figure [T. which rely on different features. Let z, Z denote the random probability vectors from two heads. We can minimise the MI across heads:
MIhead (ct, cy) Tr(Elz,z 2 log (Elz,,)))))
E|z,"" (og(L(zz)) E((z,) [ooooooo (og(E(z,)).
4

---

Hierarchical arrangement Requiring & heads (where k here) to produce unique represen- tations is not necessarily the optimal method to account for suboptimal MI maximisation. Instead, what do is encourage simple-to-complex hierarchy structure the heads, defined according to The hierarchy enables reference mechanism to Under review as a conference paper at ICLR 2021
Logarithms clement-wise, and expectations are over the data and augmentations. Note z, and 2j are each computed from the same data augmentation. We estimate this from each minibatch sample. This process can be thought of pushing the heads apart. We note that the Tr operator is commutative the hierarchical arrangement is accomplished through gradient stopping.
cross-head comparisons made using Equation 2
produce diverse labellings of the data.
Figure I shows 8 heads, 3 of which are computed from early residual blocks of the network. The hierarchical arrangement is induced by only updating head- spe-sppccfiic weights according to compar- isons made with earlier heads. In practice this is done by stopping the appropriate gradients ④ and all red crosses. For example, when computing the MI between Z;=6 and those using Ziy6, gradient back-propagation is allowed when i < 6 but not when i > 6. In other words, when learning to produce Z the network is encouraged to produce a head that is distinct from heads 'lower' on the hierarchy. Extending this concept for i = 1 8 gives rise to the hierarchy. Initial experiments showed that if this routine was ignored, the gains were reduced.
3.2 OBJECTIVE
The part of the objective producing high MI representations by 'pulling' together discrete labellings from augmentations is Equation normalised over heads:
MI pull pull
M (ct, c).
(3)
The quantity used 'push' heads apart is Equation
2 normalised per head:
Ej= M Mheead(Ci, 37
k
Mlpush
(4)
where each cross-head MI term is scaled by the head index, i, since that directly tracks the number of comparisons made for each head. scales up the hierarchy, such that the total MIsead associated with any head is scaled according to the number of comparisons. Scaling ensures that head-specific weight updates are all equally important. The final optimisation objective is:
arg max MIput/ - aMMppshh
(5)
where f are the network parameters, is a hyper- we call the cross-head Ml-minimization coefficient. For an ablation study we set a Section
3.3 DESIGN AND TRAINING CHOICES
The architecture (Figure T
is based a ResNet-18 backbone, where each residual block has two layers (with skip connection over these). Blocks to 3 have 64, 128, and 256 units, respectively. Each parallel final block (4 to 8, here) have 512 units. Each MLP has single hidden layer of width 200. Early experiments showed that entire block repetition was important to model flexibility. Similar to IIC (Ji et al. 2019) used four data augmentation repeats with batch size of 220.
DHOG maximises MI between discrete labellings from different data augmentations. This is equiv- alent clustering and is similar to IIC. There are, however, key differences. In our experiments:
We train for 1000 epochs with a cosine annealing learning rate schedule.
We do use sobel edge-detection or any other preprocessing as a fixed processing step.
We make use of the fast auto-at auoomnn CIFAR-10 data augmentation strategy (for all tested datasets) found by (Lim et al. 2019). We then randomly apply (with = 0.5) grayscale and take random square crops of sizes 64 and 20 pixels for STL-10 and other datasets.
5

---

Under review as a conference paper at ICLR 2021
The choice of data augmentation is important, and we acknowledge that for fair comparison to IIC the same augmentation strategy must be used. The ablation of any DHOG-specific loss (when 0) largely recreates the IIC approach but with augmentations, network and head structure matched to DHOG; this enables a fair comparison between an IIC and DHOG approach.
Since STL-10 has much more unlabelled data of similar but broader distribution than the training data, the idea of "overclustering' was used by (Ji et al.] 2019); they used more clusters than the number of classes (70 versus 10 in this case). We repeat each head with an overclustering head that does not play part in the cross-head MI minimisation. The filter widths are doubled for STL-10. We interspersed the training data evenly and regularly through the minibatches.
To determine the DHOG cross-head MI- Mi-mimimisttion coefficient, a, we carried out non- -on-exhhusttvve hyper parameter search using only CIFAR- 10 images (without the labels), assessing performance on a held out validation set sampled from the training data. This did not use the evaluation data.
Assessment Once learned, the optimal head can be identified either using the highest MI, or using small set of labelled data. Alternatively all heads can be used as different potential alternatives, with posthoc selection of the best head according to some downstream task. In this paper the head that maximises the normalised mutual information on the training data is chosen. This is then fully unsupervised, with the head selection protocol of IIC. We also give results for the best posthoc head to show the potential for downstream analysis.
4 EXPERIMENTS
The datasets used for assessment were CIFAR-10 (rizhevsky et al. 2009). CIFAR-100-22 (CIFAR-
100 (Krizhessky et al. 2009) where classes are grouped into 20 super-classes), CINIC-10 (Darlow
ct | (0188) (an extension of CIFAR-10 using images from Imagenet (Deng et al. 2009) of similar
classes), street view house numbers (Netzer et al. 201T) (SVHN), and STL-IO 10 (Coates et al. 201T).
For CINIC-10 only the standard training set of 90000 images (without labels) was used for training.
Table Daleegivee
gives the accuracy, normalised mutual information (NMD, and the adjusted rand index (ARI) between remapped assignments and classification targets. Before assessment
sabelling-to-llar remapping was computed using the training data and the Hungarian method (Kuhn 1955). The results listed for DHOG correspond to average over seeded runs. At the time of writing, in terms of all measured metrics DHOG outperformed other relevant fully-unsupervised end-to-end clustering methods, with an accuracy improvement of 4.3% on CIFAR-1Ó, 0.35% on CIFAR-100-20, and 7.2% on SVHN. Importantly, no Sobel edge-detection was used.
We used an unsupervised posthoe head selection using NMI(z,z') - which corresponds directly to the original MI objective. The selected heads almost always corresponded with the head that maxmimised NMI(z.y), where y are user-defined class labels. DHOG produces data groupings that:
1. Better maximise the widely used MI objective (between mappings of data augmenta- tions) and therefore is an effective mechanism for dealing with suboptimal MI optimization owing to greedy SGD, as discussed in this work. Table 2 gives the NMI with and without DHOG (controlled by a) to confirm this.
2. Correspond better with the challenging underlying object classification test objective.
It is only on STL-10 that DHOG never beat the current state-of-the-art Our aim was to show that the simple hierarchical ordering of heads in DHOG improves performance. The difference between STL-10 with and without the MI cross-head minimisation term (controlled by a)) shows a marked improvement. IIC effectively used an overclustering procedure to achieve good results on STL-10.
The advantage of a hierarchical ordering is evident when considering the ablation study: with (a = 0.05) and without (a = 0) cross-head MI minimisation. Figure 2 (a) and (b) are accuracy versus head curves, showing that without cross-heat MI minimisation later heads converge to sim- ilar solutions. The confusion matrices in Figure B (b) show the classes the final learned network confuses in CIFAR-10. Compare this to the confusion matrix in Figure (a) where a = 0 and note the greater prevalence of cross-class confusion.

---

Under review as a conference paper at ICLR 2021
Method
Accuracy
NMI(Z, y)
ARI
K K-means on pixels
21.18 + 0.0170
0.0811 + 0.0001
0.0412 E 0.0001
Cartesian K-means
22.89
0.0871 0.1923
0.0487
JULE
27.15
0.1377
DEC 1
30.1
DAC
52.18
0.3956
0.3059
CIEAR-IO
DeepCluster
37.40
ADC
29.3 + 1.5
DCCM
62.3
0.496
0.408
IIC
61.7
DHOG (a = 0, ablation)
57.49 = 0.8929
0.5022 0.0054
0.4010 0.0091
DHOG, unsup. (a- = 0.05)
66.61 + 1.699
0.5854 + 0. 0.0080
0.4916 + 0.0160
DHOG, best (a= 0.05)
66.61 + 1.699
0.5854 + 0.0080
0.4916 + 0.0160
K-means on pixels
13.78 + 0.2557
0.0862 1 0.0012
0.0274 1 0.0005
DAC f
23.8
CIFAR-10-20
DeepCluster 1* ADC
18.9
16.0
IIC 1
25.7
DHOG (a = 0, ablation)
20.22 + 0.2584
0.1880 + 0.0019
0.0846 + 0.0026
DHOG, unsup. (a 0.05)
26.05 + 0.3519
0.2579 :: 0.0086
0.1177 = 0.0063
DHOG, best (a- 0.05)
27.57 1.069
0.2687 0.0061
0.1224 0.0091
K-means pixels
20.80 = 0.850
0.0378 + 0.0001
0.0205 + 0.0007
CINIC-10
DHOG (a 0, ablation)
41.66
1.3276
0.2108 0.0034
DHOG, unsup. (a- 0.05)
37.65 = 2.7373
0.3317 + 0.0096
0.1993 + 0.0030
DHOG, best (a 0.05)
0.3725 = 0.0075
0.2396 + 0.0087
K-means on pixels
11.35 0.2347
0.0054 1 0.0004
0.0007 + 0.0004
ADC DHOG (a- = 0, ablation)
38.6 4.1
SVHN
14.27 +: 2.8784
0.0298 1: 0.0321
0.0209 0.0237
DHOG, unsup. (a = 0.05)
45.81 + 8.5427
0.4859 + 0. 0.1229
0.3686 + 0.1296
DHOG, best (a- 0.05)
49.05 + 8.2717
0.4658 + 0.0556
0.3848 0.0557
K --manns on pixels
21.58 + 0.2151
0.0936 + 0.0005
0.0487 + 0.0009
JULE
27.7
DEC
35.90
DAC
46.99
0.3656
0.2565
STL-10
DeepCluster
33.40
ADC
47.8 2.7
DCCM
48.2
0.376
0.262
IIC t
59.6
DHOG (a = 0, ablation)
38.70 + 4.4696
0.3878 + 0.0331
0.2412 + 0.0265
DHOG, unsup. (a 0.05)
48.27 1.915
0.4127 + 0.0171
0.2723 0.0119
DHOG, best (a- = 0.05)
48.27 - 1.915
0.4127 + 0.0171
0.2723 - 0.0119
Table I: Test set results on all datasets, taken from papers where possible. Results with are from Ji et al. 2019). NMT[z,, y) is between remapped predicted label assignments and class targets, y- Ablation: DHOG with a = 0.0 is the IIC method but with conditions/augnentations matching those of DHOG(a
0.5). Our method is DHOG with = 0.05, highlighted in blue. We give results for the head chosen for the best NMI(z, z') and the head chosen for the best NMI(z,y) y). In most cases max MI chooses the optimal head.
Dataset CIFAR-I0
NMI(z, z'), a = 0
NMI(z, a 0.05
0.7292 + 0.0066
0.7994 + 0.0081
CIFAR-
0.6104 = 0.0098
0.6506 = 0.0040
CINIC-10
0.6408 + 0.0015
0.6991 + 0.0044
SVHN
0.6337 0.0085
0.7265 = 0.0093
STL-10
0.6713 + 0.0175
0.6610 + 0.0084
Table 2: NMI between representations of augmentations for the training dataset, evidencing that cross-head MI minimisation does indeed aid in avoiding local optima of this objective function.
7

---

Under review as a conference paper at ICLR 2021
80
Cifar-10
svhn
80
Cifar-10
swhn
Accuracy (test)
Cifar-100-20
STL10
Accuracy (test)
Cifar-100-20
S1L10
60
Cinic-10
60
Cinic-10
40
40
20
20
2
2
6
Head
Head
(a) Without DHOG training
(b) With DHOG training
Figure 2: Accuracy per head. DHOG causes heads to learn distinct solutions.
(test)
ship
0.8
ship
horse
3000.00
horse
k.00:00:73300000010000
0010.00
True label
frog
8010000122040077300
1,000000000
0.6
frog
k023.000:4316000100000 0.00000
0.6
dog
3.000.20.0553333.333333 3.2001000000000
dog
k003:000:::100000 0.41 0.00000.00.00
deer
5,0.9:00 010.09222220011100.00..0.2..0320
0.44
Truc
deer
2.0.9.00.:55..4
0.4
cat
2010.000:00::00 www.0/0.00000.......
bird
bird
automobile
airplane
000.00000000000000
0.000.0..0
airplane
0.5
2:300000020000000
000.30
aimpl Emplano
Ciroomoo bind
cat
deer
dog
frog
horse
ship
truck
bird
cal:
dog
frog
horse
ship
truck
Predicted label
Predicted label
Without DHOG training
(b) With DHOG training
Figure 3: Confusion matrices from the same seed (a) without and (b) with DHOG cross-head MI minimisation. These networks struggle with distinguishing natural objects (birds, cats, deer, etc.), although DHOG does improve this.
claim throughout this paper is that greedy training of neural networks can result in sub-optimal showws that for all datasets except STL-10 (for which further experiments are needed) DHOG resulted in a better MI result, thereby directly improving the training objective.
MI maximisation. Table 2 shows
CONCLUSION
We presented deep hierarchical object grouping (DHOG): a method that leverages the challenges faced by current data augmentation-drrienn unsupervised representation learning methods that max- imise mutual information. Learning good representation of an image using data augmentations is limited by the user, who chooses the set of plausible data augmentations but who is also unable to cost-effectively define an ideal set of augmentations. We argue and show that learning using greedy optimisation typically causes models to get stuck in local optima, since the data augmentations fail to fully describe the sought after invariances to all task-irrelevant information.
We address this pitfall via simple-to-complex ordered sequence of representations. DHOG works by minimising mutual information between these representations such that those later in the hierar- chy are encouraged to produce unique and independent discrete labellings the data (w.r., earlier representations). Therefore, later heads avoid becoming stuck in the same local optima of the orig- inal mutual information objective (between augmentations, applied separately to each head). Our tests showed that DHOG resulted in an improvement CIFAR-10, CIFAR-100-20 and SVHN, without using preprocessing such as Sobel edge detection, and a consistent improvement of the underlying MI objective.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Philip Bachman, Devon Hjelm, and William Buchwalter. Learning representations by maximizing mutual information across views. arXiv preprint arXiv:1906. XXiv:1906.00910, 2019.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and R Devon Hjelm. MINE: mutual information neural estimation. In Proceedings of the shirty-fifth International Conference on Machine Learning, volume 80, pp. 531-540. PMLR, 2018.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsu- pervised learning of visual features. In Proceedings of the European Conference on Computer Vision, pp. 132-149, 2018.
Jianlong Chang, Lingfeng Wang. Gaofeng Meng, Shiming Xiang, and Chunhong Pan. Deep adap- tive image clustering. In Proceedings of the IEEE International Conference on Computer Vision, pp. 5879-5887, 2017.
Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsuper- vised feature learning. In Proceedings of the fourteenth International Conference Artificial Intelligence andSstatistics, pp. 215-223. 2011.
Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Rundentment: Practical data augmentation with no separate search. arXiv preprint 1rXiv:190..13719, 2019.
Luke N Darlow, E Crowley, Antreas Antoniou, and Amos J Storkey. CINIC-10 is not ImageNet or CIFAR-10. arXiv preprint arXiv: /1/000330000 2018.
J. Deng, W. Dong, R. Socher, L.-J. Li. K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hicrarchical Image Database. CVPR09, 2009.
Alexey Dosovitskiy, Jost Tobias Springenberg, Martin Riedmiller, and Thomas Brox. Discrimina- tive unsupervised feature learning with convolutional neural networks. In Advances in neural information processing systems, pp. 766-774, 2014.
Alexey Dosovitskiy, Philipp Fischer, Jost Tobias Springenberg, Martin Riedmiller, and Thomas Brox. Discriminative unsupervised feature learning with exemplar convolutional neural networks. IEEE Iransactions on pattern analysis and machine intelligence, (839))177441111 2015.
Maziar Moradi Fard, Thibaut Thonet, and Eric Gaussier. Deep k-means: Jointly clustering with k-means and learning representations. arXiv preprint arXiv: 10069, 2018.
Kamran Ghasedi Dizaji, Amirhossein Herandi, Cheng Deng, Weidong Cai, and Heng Huang. Deep clustering via joint convolutional autoencoder embedding and relative entropy minimization. In Proceedings of the IEEE International Conference on Computer Vision, pp. 5736-5745, 2017.
Philip Haeusser, Johannes Plapp, Vladimir Golkov, Elie Aljalbout, and Daniel Cremers. Associative deep clustering: training classification network with no labels. In German Conference on Pattern Recognition, pp. 18-32. Springer, 2018
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In Proceedings of fourteenth European Conference on Computer Vision, pp. 630-645. Springer, 2016.
Devon Hjelm, Alex Fedorov, Samuel Yoshua Bengio. Learning deep representations by mutual information estimation and maximiza- tion. In Proceedings of the International Conference on Learning Representations, 2019.
Karan Grewal, Adam Trischler, and
Xu Ji, João Henriques, and Andrea Vedaldi. Invariant information clustering for unsupervised image classification and segmentation. In Proceedings of the IEFE International Conference on Computer Vision, pp. 9865-9874, 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.

---

Under review as a conference paper at ICLR 2021
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logisties quarterly, 2(1-2):83-97, 1955.
Sungbin Lim, Idoo Kim, Taesup Kim, Chiheon Kim, and Sungwoong Kim. Fast AutoAugment. In Advances in Neural Information Processing Systems, 2019.
Ralph Linsker. Self-organization in pereeptual network. Computer, 21(3):105-117, 1988.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning, In NIPS Workshop Deep Learning and Unsupervised Feature Learning. 2011.
Michael Tschannen, Josip Djolonga, Paul K Rubenstein, Sylvain Gelly, and Mario Lucic. On mutual information maximization for representation learning. arXiv preprint urXiv:1907, 13625, 2019.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint arXiv: 2018.
Jianlong Wu, Keyu Long, Fei Wang, Chen Qian, Cheng Li, Zhouchen Lin, and Hongbin Zha. Deep comprehensive correlation mining for image clustering. International Conference on Computer Vision, 2019.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International conference on machine learning, pp. 478-487, 2016.
Jianwei Yang, Devi Parikh, and Dhruv Batra. Joint unsupervised learning of deep representations and image clusters. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5147-5156, 2016.
10


Reviews:
[{"review_id": "yNb-ihZOfJj", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors introduce a method which is tailored to unsupervised representation learning via minimizing mutual information. Authors support their method with an experimental study. The proposed method has some merits like finding a representation that has higher mutual information compared to baselines.  \nI have several concerns about the paper:\na)\tAuthors state that some greedy optimization may end up lower MI optima. Since deep neural networks are not convex, is this a surprising point or is this expected one?\nb)\tI think empirical comparison needs significant improvement. Authors mention the proposed method was outperforming the state of the art “at the time of writing”. However, currently I believe this is not the case. For example, GATCluster achieves 28.1% on Cifar100-20. \nc)\tI see the proposed method as shown in Fig 1, is novel. As far as I understand it is adding some extra blocks to already existing method and calculates mutual information between heads. I would like to point out that hierarchical ordering is an interesting idea however the impact of hierarchical ordering is not very clear. Why does architecture need extra heads i.e. h_4 to h_8.  Would you please emphasize the novelty of the idea bit more?\nAlthough I have some concerns about the paper, I would like to be extremely clear that I am open to change my view if more explanation and/or evidence supplied.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "voY5_wIG_ko", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents an extension to the Invariant Information Clustering (IIC) methodology for image clustering. \nIIC is an end-to-end deep clustering methodology that directly provides the cluster label of an input image. \nTraining is based on maximizing Mutual Information (MI) between pairs of related images (typically generated through augmentations).\nIn this work the authors argue that IIC performs suboptimal maximization of MI, thus the obtained solutions focus mainly on low-level representations and do not distill higher level semantic similarity of images.\nTo solve this problem, they propose an IIC extension (called DHOG) where multipe clustering solutions are obtained through MI maximization, under the constraint that the solutions found are sufficiently different (ie. minimum MI between the clustering solutions is seeked).\n\nThe proposed objective function is novel, however it involves a regularization constant \\alpha to be set by the user. \n\nThe idea of stopping gradients to impose a hierarchy of solutions is interesting.\n\nThe experimental results indicate improved clustering performance.\n \nComments to be addressed:\n1) Application of the method requires the specification of the number of K heads. It in this work K=8 is set. What is the reasoning for such selection and how does the value of K affect the results?\n2) DHOG is computatonally more complex compared to IIC. What is the execution time of DHOG compared to IIC?\n3) What happens for values of \\alpha greater that 0.05? How sensitive is the method on the value of \\alpha?\n4) It is strongly suggested to include a visual example illustrating the difference among the obtained clustering solutions (e.g. on CIFAR-10) to provide visual evidence that improved clustering solutions are progressively found.  \n5) It is not clear whether IIC results are obtained using Sobel preprocssing or not. What if Sobel preprocessing is used in DHOG?   \n6) The presentation of the paper could be improved, by first briefly describing the IIC approach and then presenting the proposed extension (DHOG).", "extra_scores": {}, "extra_text": {}}, {"review_id": "twnaLNPV8dt", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors study the problem of unsupervised representation learning from data augmentations. Specifically, the authors claim that existing methods are prone to getting stuck at local minima owing to easy-to-learn local representations that optimise the commonly used MI objectives, and then propose a hierarchical method that tackles optimisation at multiple layers of the feature hierarchy.\n\nStrengths:\n- A highly novel solution to an important problem in representation learning.\n- Strong results obtained with respect to the state of the art.\n- Extensive analysis and comparisons.\n\nWeaknesses:\n- \"We demonstrate that current methods do not effectively maximise the MI objective\" + footnote: \"We show this by finding higher mutual information solutions using DHOG, rather than by any analysis of the solutions themselves.\" => This claim calls for an analysis of the solutions and since this is missing in the paper, I would rephrase the claim.\n\n- It would have been nicer to have experimental analysis on different features (e.g. colour) being more prone to local optima, though this is intuitive. This could have significantly increased the impact of the paper.\n\nMinor comments:\n- \"a reasonable mapping need only compute colour information\" => \"a reasonable mapping needs only compute colour information\".\n- \"Learning a set of representations by encouraging them to have low MI,\" => This should be high MI?\n- \"CIFAR-10, CIFAR-100-20 (a 20-way\" => The parenthesis is not closed.\n- \"A network was learned to associate\" => \"A network was trained to associate\".\n\n**AFTER AUTHOR RESPONSE**\n\nI have read the other reviewers carefully and the feedback provided by the authors. The reviewers had two major concerns: (i) Theoretical or empirical justification/proof for the following claim (and the motivation) of the paper: “the current methods do not effectively maximize the MI objective because greedy SGD typically results in suboptimal local optima”. (ii) Lack of comparisons with newer methods from e.g. ECCV2020 etc.\n\nFor the second, I feel empathy with the authors: In such a rapidly progressing field, it is difficult to integrate comparisons with new methods that are published while writing/submitting a paper. I am sure all of us have experienced similar problems.\n\nFor the first issue, I disagree with the authors and agree with the other reviewers: This is an important claim that needs to be justified and I disagree with the authors's comment on the current results of the paper being a sufficient empirical evidence for the claim. An ICLR paper should have provided the necessary evidences and justifications.", "extra_scores": {}, "extra_text": {}}, {"review_id": "XMorvtGrF-X", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "<Summary>\n\nThis paper addresses the problem of unsupervised learning of class representation using data augmentation. Its key idea is to encourage the learned representations to have low MI while maximizing the original augmentation-driven MI objective. It reports the improved performance for the benchmarks of Ji et al. 2019 – classification on some easy datasets (e.g. CIFAR-10, CINIC-10, SVHN and STL-10).\n \n<Strengths> \n\n1. The proposed approach proposes an MI minimization strategy for unsupervised clustering that can obtain more informative representation than previous methods.\n\n2. The proposed DHOG method shows better performance than some baselines reported in  Ji et al. 2019 for some easy classification tasks on  CIFAR-10, CINIC-10, SVHN and STL-10.\n\n<Weakness>\n\n1. This work summarizes the two contributions in sec 1.2. However, both of them are not fully supported. \n\n(1) This work claims that “the current methods do not effectively maximize the MI objective because greedy SGD typically results in suboptimal local optima.” However, there is neither theoretical justification nor empirical results that show why the proposed approach does not suffer from this issue and why it is subsequently better than other works. \n\n(2) This argument may be based on that the proposed DHOG adopts distinct head that encourages different solutions between heads one another and a simple-to-complex hierarchy structure to the heads. Conceptually, they could be reasonable solutions to the issue, but there is no theoretic and empirical evidence that supports this argument. \n\n(3) The other contribution that this work claims is strong performance of unsupervised clustering on benchmark datasets. However, the empirical comparison is only carried out with baselines in Ji et al., 2019. \n\n(4) More critically, this work fails to cite the following recently published papers that reported much stronger performance on the same datasets. \n\na. W. Van Gansbek et al, SCAN: Learning to Classify Images without Labels, ECCV 2020.\nb. G. Shiran & D. Weinshall  Multi-Modal Deep Clustering: Unsupervised Partitioning of Image, ICLR 2021.\nc. N. Astorga et al. MPCC: Matching Priors and Conditionals for Clustering, ECCV 2020.\n\n<Conclusion>\n\nMy initial decision toward this submission is rejection because the main contributions of this work are not fully convinced. Moreover, this work ignores key related papers that show better performance on the same benchmarks.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: During the discussion phase, although the reviewers acknowledge superior empirical performance of the proposed method, they shared the two major concerns:
1. Lack of theoretical or empirical justification/proof for the key statement: "the current methods do not effectively maximize the MI objective because greedy SGD typically results in suboptimal local optima".
1. Lack of comparisons with newer methods from e.g. ECCV2020 etc.

In particular, the first point is crucial. As the reviewers pointed out, since it is the main contribution and the key message of this paper, it should be carefully examined theoretically and/or empirically. However, in its current state, there is no theoretical analysis, and empirical evaluation is not convincing. 

About the second point, although I think it cannot be a solo reason for rejection, at least it is better to cite and discuss it fo the completeness.

Overall, the contribution of this paper it not significant enough for publication. Hence I will reject the paper.
Decision: Reject