Unsupervised Order Learning
Authors: Seon-Ho Lee
Nyeong-Ho Shin
Chang-Su Kim
Venue: ICLR 2024 poster (2024)
Keywords: order learning
unsupervised clustering
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: A deep clustering algorithm for ordered data

Abstract: A novel clustering algorithm for orderable data, called unsupervised order learning (UOL), is proposed in this paper. First, we develop the ordered $k$-means to group objects into ordered clusters by reducing the deviation of an object from consecutive clusters. Then, we train a network to construct an embedding space, in which objects are sorted compactly along a chain of line segments, determined by the cluster centroids. We alternate the clustering and the network training until convergence. Moreover, we perform unsupervised rank estimation via a simple nearest neighbor search in the embedding space. Extensive experiments on various orderable datasets demonstrate that UOL provides reliable ordered clustering results and decent rank estimation performances with no supervision. The source codes are available at https://github.com/seon92/UOL.

Published as a conference paper at ICLR 2024
UNSUPERVISED ORDER LEARNING
Seon-Ho Lee, Nyeong-Ho Shin & Chang-Su Kim
School of Electrical Engineering, Korea University
Seoul 02841, Korea
[seonholee, nhshin) 8mcl. korea ac kr, changsukim@korea.cc kr
ABSTRACT
A novel clustering algorithm for orderable data, called unsupervised order learn- ing (UOL), is proposed in this paper. First, we develop the ordered k-means group objects into ordered clusters by reducing the deviation of an object from consecutive clusters. Then, we train network to construct an embedding space, in which objects are sorted compactly along chain of line segments, determined by the cluster centroids. We alternate the clustering and the network training until convergence. Moreover, we perform unsupervised rank estimation via simple nearest neighbor search in the embedding space. Extensive experiments on vari- orderable datasets demonstrate that UOL provides reliable ordered clustering results and decent rank estimation performances with no supervision. The source codes are available https: / thub. com/ weeennn////0e ///O..
INTRODUCTION
Clustering aims to partition objects into clusters by finding underlying object classes without any supervision. It fundamental task with multifarious applications, including anomaly detection (Emadi & Mazinani, 2018), domain adaptation (Tang et al., 2020), community detection (Xing et al., 2022), and representation learning (Yang et al., 2016). Especially, we can now collect countless images easily, but it is both time-consuming and expensive to manually annotate such images. Unsupervised clustering can reduce the annotation burden by providing initial predictions.
Many deep clustering methods (Caron al., 2018; Van Gansbeke al., 2020; Tao et al., 2021; Tsai et al., 2021; Huang et al., 2022) have been developed to provide promising results based on deep learning. However, most of them are for clustering nominal data for classification (Deng al., 2009) or segmentation (Ji et al., 2019), so they may yield suboptimal results on orderable data.
Orderable data used in many applications such as medical assessment (Yang al., 2021), facial age estimation (Ricanek & Tesafaye, 2006), and aesthetic quality assessment (Kong et al., 2016) are different from nominal data in that objects can be arranged in intrinsic order (Lim et al., 2020). For example, medical images can be sorted according to the severity of illness, and facial photos according to the subjects' ages. Compared nominal data, clustering of orderable data is more challenging because it is difficult to distinguish adjacent underlying classes; in facial photos, 20-year-old tends to be very similar a 19-year-old or 21 -eeyroo-
Despite its difficulty, the clustering of orderable data has many benefits, just as the clustering of nominal data does; can facilitate an initial understanding of data characteristics. Also, general, it is costly to obtain reliable annotations for orderable data due to the aforementioned ambiguity between classes. The clustering of orderable data can reduce the annotation cost, e.g. for medical assessment datasets.
In this paper, we propose a novel algorithm, called unsupervised order learning (UOL), for clustering orderable data. It aims to discover underlying classes of objects well as their ordering relationship without any supervision.
To this end, we first develop the ordered k-means by extending the ordinary k-means (Gersho & Gray, 1991). Whereas the ordinary k-means minimizes the distance of an object to its centroid, the ordered k-means reduces the deviation of object from consecutive centroids, thereby laying out adjacent clusters close to each other in an embedding space. Hence, as illustrated in Figure ((a), the clusters of the ordered k-means form clear sequential order.

---

Published as a conference paper at ICLR 2024
1 3 Ground-truth classes
Clusters
S
6
Age ordeer
Ordinary k-means
Ordered k-means
IDFD
UOL
(a) Comparison of clustering results
(b) Comparison of embedding spaces
(c) UOL clustering examples
Figure 1: (a) Comparison of the ordinary k-means and the ordered k-means on data samples around an S curve in the 3ID space. (b) Comparison of the embedding spaces for dividing the MORPH II dataset (Ricanek & Tesafaye, 2006) into six clusters, obtained by IDFD (Tao al., 2021) and the proposed UOL algorithm. We group the ground-truth age classes into six age ranges, depicted by colors from blue to red. (c) Examples in each cluster of UOL the MORPH II dataset.
Furthermore, to design an even better space for ordered clustering, train an embedding network based on the order desideratum that encourages objects to be arranged according to their cluster indices. We iterate the ordered k-means clustering and the network training alternately. For example, in Figure ((b), the proposed UOL well arranges object instances in a facial dataset, MORPH II (Ricanek & Tesafaye, 2006), according to their ordered classes in the embedding space, while the deep clustering algorithm IDFD (Tao et al., 2021) locates the instances in different classes closely without distinction. Consequently, UOL discovers the underlying age order with supervision, shown in Figure I(c). In other words, given only facial images, UOL sorts them roughly according to the ages.
Extensive experiments demonstrate that UOL provides reliable clustering results various orderable datasets and also yields promising rank estimation results with no supervision.
The contributions of this paper can be summarized follows.
We propose the first deep clustering algorithm for orderable data, which discovers clusters together with their hidden order relationships.
We develop the ordered k-means by extending the ordinary k-means. only groups object instances effectively but also sorts the clusters to form a meaningful order. We also prove the local optimality of the solution.
The proposed algorithm provides promising clustering results on various types of orderable data for facial age estimation, medical assessment, facial expression recognition, and speech evaluation. Also, it shows decent estimation results as an unsupervised rank estimator.
RELATED WORK
Deep clustering: In deep clustering, instances are grouped into clusters while network is trained
to embed them into a better space for clustering. Most deep clustering algorithms (Xie et al., 2016;
Chang et al., 2017; Van Gansbeke al., 2020; Wu et al., 2019; Yang et al., 2016; Tsai al., 2021; Tao et al., 2021; Huang et al., 2022; Niu et al., 2022) adopt the alternate learning framework; they repeat clustering and network training alternately at regular intervals. Caron al. (2018) employed k-means to cluster instances and trained a network to classify instances simply according to their cluster memberships. Tao al. (2021) also used i-means, but they trained a network with a feature decomrelation constraint to construct better embedding space. Recently, Van Gansbeke et al. (2020); Huang et al. (2022); Niu al. (2020); et al. (2019); Tsai et al. (2021) have adopted the contrastive loss for network training, self-supervised learning techniques (Chen et al., 2020; He et al., 2020) have shown promising results for constructing discriminative embedding spaces.
Even though many deep clustering algorithms have been proposed, most of them are designed for ordinary data. Thus, when applied to orderable data, they may yield sub-optimal clusters because there is clear distinction between classes in orderable data. In contrast, the proposed algorithm provides more reliable clustering results by considering the order - which is unknown but to be discovered of underlying classes.
2

---

Published as a conference paper at ICLR 2024
9/4
M2
(a) Embedding space
(b) Ordinary k- t-maans
(c) Ordered k- means
Figure 2: Instances in embedding space clustered by the ordinary k-means and the ordered k-means, respectively, at k = 5. In (b) and (c), each circle represents the centroid of a cluster. In (b), each point h, in the embedding space is colorized according its distance d (45) from centroid Mj. In (c), h is colorized according to the deviation 0(h Mi Mjs P.a) in equation 1. Here, j 3.
Also, there are ordinal clustering algorithms (Zhang & Cheung, 2020; Jia & Cheung. 2017: Zhang & Cheung, 2018), but ordinal clustering is different from the proposed ordered clustering. Ordinal clustering aims to group instances with provided ordinal attributes, whereas ordered clustering, without any supervision, aims to discover clusters together with their meaningful order.
Orderable data: There are various types of orderable data. For example, in video-sharing platform, videos can be sorted according to the number of views likes. Similarly, medical images, aesthetic images, and facial images can be arranged according to illness severity, scores, or ages, respectively. If the intrinsic order in orderable data is known, they called ordered data, in which classes (or ranks) form an ordered set. To estimate the classes of ordered data, several attempts (Lim et al., 2020; Lee & Kim, 2021; Shin et al., 2022; Lee al., 2022; Lee & Kim, 2022) based order learning have been proposed. Lim et al. (2020) first proposed the notion of order learning, which learns ordering relationships between objects using pairwise comparator and determines the rank of an unseen object by comparing it with references. Lee & Kim (2021) improved the performance of order learning by finding reliable references via order-identity feature decomposition. Shin et al. (2022) proposed a regression approach for order learning. Lee et al. (2022) simplified order learning; their method sorts objects in an embedding space and then uses the k-NN search estimate the rank of an object, instead of comparing it with references. Also, Lee & Kim (2022) developed weakly supervised training scheme for order learning.
Note that, in (Lim et al., 2020; Lee & Kim, 2021), ordered data are clustered according to order- unrelated properties, whereas we discover an underlying order orderable data and cluster the data according to the discovered order. It is worth pointing assume that the ground-truth ranks of training objects are completely or partially known. In contrast, attempt to cluster orderable data X' and estimate the rank of each instance in X' without any supervision. In other words, we propose the first unsupervised algorithm for order learning.
that all existing order learning algorithms
PROPOSED ALGORITHM
3.1 ORDERED M-MEASS
Suppose that there instances in training set X' =x11, 22, ... Fm }. In orderable data, classes can be arranged in a natural order. Hence, the proposed ordered k-means aims to partition into clusters {C,})=1 where C₁ + C2
Z2....
- C. represents meaningful order.
An encoder h maps each instance X into feature vector hg h(x)) in embedding space. As h, we adopt VGG16 (Simonyan & Zisserman, 2015) without fully connected layers. To measure the dissimilarity in the embedding space, or the representative vector for the instances in cluster Cj. Then, these centroids form a chain Mi in the embedding space, in Figure 2(c). Note that chain is defined maximal linearly-ordered set (Lim et al., 2020). For C,, the deviation of x from the chain is defined as
the Euclidean distance d. Let My denote the 'centroid'
141 M22
5(hr. Mip Mjj M5.) d² (h.. (), + add (hz: Mjp) ) + ad? (hzz (j.)) where a is positive weight, and jp and jn are the indices for the previous and next clusters;
[j
1
j +1 if
jp 1i+ 1f=11
jn =
(2)
1 iřj=
3

---

Published as a conference paper at ICLR 2024
Algorithm I Unsupervised Order Learning (UOL) ...,, ,,,.,,,..... Jm = the number clusters
Input: Data =
1: repeat
2: Randomly partition X' into C2, .., C
3: repeat
4: for all j 2. k do Update centroid My via equation 4 6: end for
5:
Centroid rule
7:
for all j 1........ ........ k do Update cluster C via equation 5 end for
8:
P NCC rule
9:
10:
Permute the cluster indices via equation
> Permutation rule
11:
until convergence predefined number of iterations
12: Fine-tune the encoder and the centroids {1z [ to minimize Emnil in equation
13:
until predefined number of epochs
Output: Clusters {- centroids {1y {fy}A=1- encoder
In the case of the first cluster C₁ there is previous cluster. Thus, by defining Jp j + 1, the deviation in equation 1 becomes d2 (ha (45) + 2nd (hz: Mz.)) that is balanced with those for middle clusters. Similarly, for the last cluster Ck+ Jn =j
In equation the first term measures the distance of instance in Cj to its centroid μy in the ordinary k-means (Gersho & Gray, 1991). In the ordered k-means, however, the second and third terms further consider the distances to the adjacent centroids. This is because, in orderable data, adjacent clusters contain similar instances in general. For example, in facial photos, a 20-year-old tends be similar 19-year-old or a 21-year-old. Therefore, instances in C2 should be closer to the adjacent clusters C₁ and Cj, than to the other clusters. Moreover, in orderable data, instances vary continuously between adjacent clusters in general. For example, although discrete age classes are defined, there are 99.5-year-olds Thus, the deviation in equation implies that an instance in C should concentrated near the line segments μ3, > PJ + Hj as illustrated by the color map in Figure 2(c), not just around the centroid μ.j.
Next, we measure the overall quality of ordered clustering by
J(CC 1
(M H = - Evec, 8(h Mj Pj. Pj.).
We attempt to find the optimum clusters and centroids minimize this objective function J in equa- tion 3, yet finding the global optimum is NP-complete (Garey et al., 1982). Hence, we propose an iterative algorithm find local optimum, as in the ordinary k-means (Gersho & Gray, 1991).
Centroid rule: After fixing the clusters (C, J we update the centroids {nz} to minimize J in equation 3. For j & {1, 2, k - 1, kJ, the optimal centroids are obtained as
Exec, he + a Exec, h2 + a Exec,, hgg
Ic, + Ca + a=Cc,,
Note that centroid μy is given by weighted average of the instances in the three consecutive clusters Cjp- Cj. and Cj.- For j E 21,2, 1, k}. the centroid rule in equation is slightly different due to endpoint effects. The full centroid rule is derived in Appendix B.I.
NCC rule: On the other hand, after fixing the centroids, we update the membership of each instance to minimize J in equation 3. As detailed in Appendix B.2, the optimal cluster Cj is given by
Cj 5(h,, Mi, 155,-15 M5, P.j) S 5(h (0,0,,,,,. P4, (1,)), for all A)
Note that the deviation 8(h Mia Mgs P.a) in equation computes the distances of h three consecutive centroids. We assign an instance to C₁ if its nearest consecutive centroids (NCCs) are (Pi,, M..).
The cluster indices should represent a meaningful order. Hence, after fixing the clusters and the centroids, apply the permutation rule to rearrange the clusters optimally. Let
Permutation rule:
4

---

Published as a conference paper at ICLR 2024
Class
Indance enbeellings
H5
H4
Ma
Ha
Horaae
H2
H4
--
Angla misimization
F4
-- Attracionn
Embedding space
Ordered k-msans
Straight line loss
Deviation loss
(a) Clustering step
(b) Training step
Figure 3: An overview of the proposed UOL algorithm.
(1....,k) (I,...,A }} be a bijective permutation function. Then, the optimal permutation o* determined to minimize J in equation 3,
o² = arg min J ((CC (o
(6)
To find the optimal permutation o², cases should be considered, which may be too demanding. Therefore, for a large k; we develop a greedy scheme for finding with O(k²)) complexity, which is described in Appendix B.3.
We apply the centroid rule, the NCC rule, and the permutation rule iteratively until convergence. Since all three rules monotonically decrease the same objective function J/ in equation is guaranteed that the ordered k-means converges to a local minimum.
If in equation 1, the objective function (Gersho & Gray, 1991). In such a case, the resultant clusters are not ordered in general as illustrated in Figure 2(b). for the relations between adjacent clusters are not taken into account. In contrast, the proposed ordered k-means minimizes the average dissimilarity of the instances to their NCCs, thereby making consecutive clusters close each other as shown Figure 2(c).
equation 3 is equal that of the ordinary k-means
3.2 UNSUPERVISED ORDER LEARNING (UOL)
We develop the UOL algorithm based on the ordered h-means. Figure an overview of UOL. Note that, in given embedding space, the ordered k-means is applied to data X' to yield clusters (C,) Then, in turn, we fine-tune the encoder or equivalently revamp the embedding space, so the clusters are better arranged according their order relationship. In ordered clustering, cluster indices represent their order, and the index difference between two clusters should be proportional to the dissimilarity between them. Hence, we fine-tune the encoder / with the following desideratum:
<j<l
d(ha, hyy) < d (htz hz)
where instances z E C., y E Cj. and E C.. In the fine-tuning process, we also optimize the centroids {ny /= as learnable parameters to guide the cluster regions in the embedding space.
Straight line loss: To encourage the order desideratum in equation
employ the straight line (SL) loss. First, let us define the direction vector v(r, s) from point to point s in the embedding space
v(r,8) (s r)/ -ll--
(8)
Then, we define the SL loss as
ESL = - (1- u( ( p2)) + (1- v(U5, N
To minimize the first term, the angle between v(Uj, ((w)) and M45) should be zero, illustrated in Figure 3(b). In other words, Hj., ha. and H,, should be on a line in the embedding space. Similarly, due to the second term, Ps., hgg and μy should be on the same line. Therefore, fsL encourages that hy and its NCCs (Pip Mý P,,) are arranged linearly on a ID manifold in the embedding space, and that by and J located between nij and H4,,- In other words, it helps instances and centroids be
5

---

Published as a conference paper at ICLR 2024
Table Comparison of ordered elustering results in settings A and of MORPH II. The best results are boldfaced, and the second-best ones are underlined.
Sotting
Setting
SRCC(())
MAE (1)
SRCC (f)
MAE (4)
Algorithm
A 9
8
12
k 6
k
9
h 12
F
&- 12
k 6
K 9
R 12
DAC (Ching el al., 2017)
0.180
0.216
0.108
1.785
2.734
3,853
0.117
0.147
0.350
1.792
2.748
3,417
DecepClosa (Caron et al,, 2018)
0.139
D.1077
0.098
2,1778
2.871
4.0001
0.151
0.049
0.062
2.185
3.075
4.345
IIC al., 2019)
0.041
0.135
0.332
2.312
2.959
3.420
0.112
0.120
0.109
1.828
2.672
3.868
(Tsai 2021)
1.568
2.579
2,935
0.292
2.683
3.372
IDFD (Tho al., 2021)
0.123
0.136
0.274
1.961
2.867
3.171
0.094
0.178
0.160
1.881
2,586
3.7W7
ProPos (Huang 2022)
0.167
0.144
0.196
1.755
2.793
3,590
0.129
0.139
0.202
1.795
2.775
3.686
Proposed UOL
0.632
0.506
0.495
1.122
2,093
2.572
0.531
0.473
0.437
1.278
2.114
3.025
31.85
33.18
36,81
33.89
27.11
Chaster
32,92
28,88
30.94
31.89
33,87
Cluster
35,48
33.83
33
36.99
42.85
Chuster
(a) DeepCluster
(b) MICE
(c) IDFD
(d) ProPos
(e) UOL
Examples of clustering results in setting A MORPH II: (a) DeepCluster (Caron et al., 2018), (b) MiCE (Tsai et al., 2021), (c) IDFD (Tao et al., 2021), (d) ProPos (Huang et al., 2022), and
Figure 4:
(e) UOL. For each cluster, the average ground-truth age of its instances is also reported.
sorted according to the index order of the clusters along the ID manifold in the high-dimensional embedding space, thereby satisfying the order desideratum in equation 7.
Deviation loss:
In addition to İSL. we employ the deviation loss fD. which aims at reducing the deviation å of an instance from its NCCs in equation 1, given by
f = D Exec, max(ō(ha Hjp Mjs Mja) 7,0)
(10)
where y is threshold.
Finally, we use the total loss function
Gotal LST. + ED
(11)
to optimize the encoder parameters and the centroids. Algorithm 1 summarizes the proposed UOL..
3.3 UNSUPERVISED RANK ESTIMATION
We can estimate the rank (or class) of an unseen test instance based on the K-NN classification. We first transform a test instance x to the embedded vector h(x)). Then, in the embedding space, we find the set N of its K NNs among all training instances in X. We then estimate the rank of x by
((x) 1/2 EyEN Ejmrily Cy]
(12)
where [:] the indicator function.
EXPERIMENTS
This section provides various experimental results. More results are available in Appendix C.

---

Published as a conference paper at ICLR 2024
Table 2: Comparison of ordered clustering results on the CLAP2015 dataset.
Table 3: Comparison of ordered clustering results on the DR and RetinaMNIST datasets at l: 5.
SRCC(1)
MAE (1)
DK
RetinzMNIST
Algorilhm
6
k= 0
==
k
Alporilhm
SRCC
MAE (U)
SRCC
MAE
DAC (Chang
0.100
2.615
DAC (Chang
0.027
1,502
0.348
DeepCluster (Curon al., 2018)
0,013
3.251
DeepCluster (Ciran al. 2018)
0.099
1.295
0.037
IC Oi et al., 2019)
0.123
0.102
1,892
2.900
UC Ui et 2019)
0.205
1,284
0.165
1.346
MICE (Tsai et al., 2021)
0.194
0.198
1.794
2,709
MICE (Tsui ctal., 2012)
0.227
1.315
0.425
1.002
IDDD (ioe al., 2021)
0.209
0.172
1.733
2,715
WHD (lao et al., 2021)
0.018
1,531
0.006
1.401
ProPos (Huang a al. 2022)
0.000
0.088
1,928
2,875
ProPos (Hlangg et al. 2022)
0.085
1,490
0.041
1.469
Proposed
0.302
0.295
1.645
2.496
Proposed 1101.
0.333
1.219
0.567
0.953
Cluster 1
Cluster
Cluster
Cluster
Cluster 5
Figure Examples of clustering results on the FER+ dataset
4.1 IMPLEMENTATION
We initialize the encoder h with VGG16 pre-trained on ILSVRC2012 (Deng et al., 2009). We use the Adam optimizer (Kingma & Ba, 2015) with batch size of 32 and a weight decay of 5 10-4 We set the learning rate to 10-4 For data augmentation, we do random horizontal flips and random crops. More implementation details are in Appendix C.I.
4.2 DATASETS
MORPH II (Ricanek & Tesafaye, 2006): It is a dataset for age estimation, composed of 55,134 facial images in the age range [16, 77). It provides age, gender, and race labels.
CLAP2015 (Escalera et al., 2015); It contains 4,691 facial photos taken in various environments. For each photo, it provides an age label in the age range [3, 85).
DR (Dugas et al., 2015): It is dataset for diabetic retinopathy (DR) diagnosis. It provides 35,125 eye images. Each image annotated with a 5-scale severity score.
RetinaMNIST (Yang et al., 2021): It is a small dataset for DR diagnosis. It contains 1,600 eye images, annotated with severity scores in a 5-scale.
FER+ (Barsoum et al., 2016); It contains 32,298 grayscale images for facial expression recognition. Each image is categorized into one of eight emotion classes.
4.3 CLUSTERING
Metrics: In orderable data, classes can form order. Without loss of generality, let us assume that the ordered classes are the first natural numbers. For instances x, y,, and 2, suppose that (zx) i, d(y) j, and ((2) I, where 0(-) is class function and i < < l. Then, misclustering x with is a severer error than misclustering it with y. Thus, to evaluate the clustering performance of orderable data, the order between classes should be considered. We hence use the Spearman' rank correlation coefficient (SRCC) and mean absolute error (MAE) metrics. Specifically, SRCC is the correlation coefficient between two rankings, given by
6Σ Exec, (1 (5-8(x)) R(R-
SRCC 1
(13)
MAE the average absolute error, defined as
MAE アि Ej Exec, |i - 0(x)
(14)
Comparison age estimation datasets: Table compares the ordered clustering results in settings and B of MORPH II. As in (Tsai et al., 2021; Tao et al., 2021: Caron et al., 2018), we assume that the number k of clusters is known a priori. Also, according to k. the entire age classes mapped into l age groups. All algorithms in Table use VGG16 pre-trained on ILSVRC2012 (Deng et al., 2009) as their encoder backbones. We train these methods using the official source codes.
As done in (Tsai et al., 2021: Tao et al., 2021; Caron et al., 2018), for the conventional algorithms, the obtained clusters are permuted via the Hungarian method (Kuhn, 1955) to match the ground-truth
7

---

Published as a conference paper at ICLR 2024
I 3
(a) DeepCluster
(b) MICE
IDFD
(d) ProPos
(e) UOL
Figure 6: t-SNE visualization of the embedding spaces for the DR dataset at 5.
Table Comparison of rank estimation results (MAEs) on the MORPH II, DR, and RetinaMNIST datasets. For MORPH II, h = 6. For DR and RetinaMNIST, t 5.
Algorithm
MORPH (setting A)
MORPH II (setting
RetinaMNIST
OI. (Lim et al., 2020)
0.65
0.69
0.81
0.72
Rundom guess
1.94
1.94
1.60
1.60
Proposed UOL
1,20
1.31
1.08
1.00
optimally. In contrast, for the proposed UOL algorithm, do not use the Hungarian method and just reverse the cluster order it better matches the ground-truth - the reversed order is fundamentally the same the original order. Nevertheless, UOL significantly outperforms all conventional algorithms hoaperrtoorrrr
in all tests, indicating that it can group instances into meaningfully ordered clusters. Especially, UOL achieves high SRCCs of 0.632 and 0.531 k 6 in settings A and B of MORPH II, respectively, while the second-best MiCE (Tsai et al., 2021) scores 0.260 and 0.271 only.
Figure 4 compares examples of clustering results in setting A of MORPH at conventional algorithms tend to group similar-looking instances, as they focus on reducing intra-class variance. For example, in cluster 3 in Figure 4(a) or in Figure 4(c), background colors or personal appearances affect the clustering. Thus, they fail to cluster instances according to their ages. On the contrary, the proposed UOL groups more diversely looking people the same cluster, but those people have similar ages. Also, UOL arranges the clusters well according to the average ages, indicating that UOL can discover the underlying order instances without any supervision.
The
Table 2 shows the results CLAP2015, which is more challenging than MORPH II because it consists of natural face shots in diverse environments. Nevertheless, UOL surpasses the conventional algorithms in all tests.
Comparison medical assessment datasets: Table 3 compares the results on the DR and Reti- naMNIST datasets. Note that DeepCluster (Caron et al., 2018), IDFD (Tao et al., 2021), and ProPos (Huang et al., 2022) exploit the ordinary k-means for clustering. However, for ordered clustering, the ordinary k-means is not optimal because does not consider the order of clusters. In contrast, based on the ordered k-means, the proposed UOL yields the best scores in all tests.
We test the proposed UOL the FER+ dataset, containing facial images with various emotions. Figure 5 shows clustering examples of the Anger, Fear, and Disgust images at k 5. Note that there is explicit order between these three emotion classes. Nevertheless, we see that UOL sorts the images from the strongest (cluster 1) to the weakest (cluster 5) levels of "making face.' UOL discovers these ordered groups without any supervision. More results on FER+ are provided in Appendix C.3.
Results on facial expression dataset:
Depending on datasets, UOL may discover different, unexpected orders of clusters. This a natural property in unsupervised clustering. As long as a discovered order of clusters is meaningful and consistent, it a good clustering result enabling an initial understanding of data characteristics.
Embedding spaces: Figure 6 compares the embedding spaces for DR at k = 5, where t-SNE (Maaten & Hinton, 2008) is used for the space visualization. In Figure 6(a)~(d), the conventional algo- rithms (Caron et al., 2018; Tsai et al., 2021: Tao et al., 2021; Huang et al., 2022) fail to group instances according their classes. In contrast, UOL sorts the instances reliably, though not per- fectly, in Figure 6(c) by employing the SL loss and the deviation loss during the embedding space construction. More comparison results of embedding spaces are provided in Appendix C.6.
8

---

Published as a conference paper at ICLR 2024
Table 5: Ablation studies for the loss function in equation 11 on MORPH II, DR, and RetinaMNIST.
MORPH (A),
DR, & =
RetinaMNIST,
Method
Iss.
SRCC (1)
MAE (C)
SRCC (1)
MAE (4)
SRCC (1)
MAE (U)
0.423
1.469
0.304
1.236
0.533
0.994
0.203
0.085
1.506
III
0.632
1.122
0.333
1.219
0.567
0.953
Class
Ordrony
k-enean
Ordered k-rooms
Initialization
Iteration
Itcration 2
Iteration 3
Iteration 4
Figure Illustration of the clustering processes of the ordinary k-means and the ordered k-means.
4.4 UNSUPERVISED RANK ESTIMATION
The proposed UOL can estimate the rank of unseen test instance via equation 12. Table 4 compares the rank estimation results, measured by MAEs, on MORPH II. DR, and RetinaMNIST. To the best of our knowledge, there is unsupervised rank estimator with reliable source codes. Hence, provide the results of OL (Lim et al., 2020), which one of the state-of-the-ar supervised rank estimators, the performance upper bounds. Also, we list the results of the random guess scheme as the lower bounds. We see that UOL provides decent rank estimation results, even though it uses no annotations for both training and testing.
4.5 ANALYSIS
Ablation study: Table 5 compares ablated methods for the loss function in equation 11. Method I employs the SL loss fsL only, and method does the deviation loss tD only. Compared with III (UOL), both methods and Il degrade the performances. Especially, by comparing II and III, that EST. significantly improves the results. It helps to sort instances and cluster centroids compactly around chain of line segments in the embedding space.
Comparison with ordinary k-means: Figure 7 illustrates the clustering processes of the proposed ordered k-means and the ordinary k-means for 2D example. As the iteration goes on, the ordinary k-means updates the clusters so that the variance of instances in each cluster is reduced. Consequently. instances are located compactly around the centroids. but the clusters are not arranged an order. In contrast, the ordered k-means reduces the deviation of instances from their NCCs. Hence, consecutive clusters are located closely to each other, so they form an order in the embedding space. More result is provided in Figure 11 in Appendix C.6.
5 CONCLUSIONS
The UOL algorithm for unsupervised clustering and rank estimation of orderable data was proposed in this work. First, we group instances into ordered clusters via the ordered k-means. Then, using the SL loss and the deviation loss, we fine-tune the encoder to revamp the embedding space, that instances are sorted according to their cluster indexes. The clustering and the feature embedding are jointly optimized. Furthermore, estimate the rank of unseen test instance by performing the K-NN search the embedding space without any supervision. Extensive experiments on various orderable datasets demonstrated that UOL provides promising clustering and rank estimation results.
ACKNOWLEDGMENTS
This work supported by the National Research Foundation of Korea (NRF) grants funded by the Korea government (MSIT) (No. NRF-2021R R A4A 103 164 and NRF-2022R A250T00000000))0110
9

---

Published as a conference paper at ICLR 2024
REFERENCES
Alexei Baevski, Yuhao Zhou, Abdelrahman Mohamed, and Michael Auli. Wav2Vee 2.0: A framework for self-supervised learning of speech representations. In NIPS, 2020. 15
Emad Barsoum, Cha Zhang, Cristian Canton Ferrer, and Zhengyou Zhang. Training deep networks for facial expression recognition with crowd-sourced label distribution. In ICMI, 2016.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsuper-
vised learning of visual features. In ECCV, 2018. 2, 6, 7, 8, 17, 18
Davide Castelvecchi. facial recognition too biased be let loose? Nature, 587(7834):347-399, 2020. 13
Jianlong Chang, Lingfeng Wang, Gaofeng Meng, Shiming Xiang, and Chunhong Pan. Deep adaptive image clustering. In ICCV, 2017. 2, 6,
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. ICML, 2020. 2
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In CVPR, 2009. 7,
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In NAACL-HLT, 2019. 15
Emma Dugas, Jorge Jared, and Will Cukierski. Diabetic retinopathy detection, 2015. URL https: wtwiiiiiinnnniiiiiiiieeeeeeeeeee diwbetic-biiiieeeeeeie www.-eeettti----neneeeeeeeoee deteehhyydeettiion. 7
//kaggle com/ compet iiniiiiiiiiiiiiiiiiiiiiii
Hossein Saeedi Emadi and Sayyed Majid Mazinani. A novel anomaly detection algorithm using DBSCAN and SVM in wireless sensor networks. Wireless Personal Communications, 98:2025- 2035, 2018. 1
Sergio Escalera, Junior Fabian, Pablo Pardo, Xavier Baró, Jordi Gonzàlez, Hugo Escalante, Dusan Misevic, Ulrich Steiner, and Isabelle Guyon. Chal learn looking at people 2015: Apparent age and cultural event recognition datasets and results. ICCV Workshops, 2015.
M. R. Garey, D. S. Johnson, and Hans S. Witsenhausen. The complexity of the generalized Lloyd-Max problem. IEEE Trans. Inf. Theory, 28(2):255 1982. 4
Allen Gersho and Robert M. Gray. Vector Quantization and Signal Compression. Kluwer Academic Publishers Norwell, 1991. 5,
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In CVPR, 2020. 2
Zhizhong Huang, Jie Chen, Junping Zhang, and Hongming Shan. Learning representation for clustering via prototype scattering and positive sampling. IEEE Trans. Pattern Anal. Mach. Intell., pp. 1-16, 2022. 1, 7, 8, 16, 17, 18, 19
Xu Ji, Joao Henriques, and Andrea Vedaldi. Invariant information clustering for unsupervised image classification and segmentation. In ICCV, 2019. 2,
Hong Jia and Yiu-Ming Cheung. Subspace clustering of categorical and numerical data with an unknown number of clusters. IEEE Trans. Neural Netw. Learn. Syst., 3308)3338--33 2017. 3
Diederik P. Kingma and Jimmy L. Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Shu Kong, Xiaohui Shen, Zhe Lin, Radomir Mech, and Charless Fowlkes. Photo aesthetics ranking network with attributes and content adaptation. ECCV, 2016.
Harold W. Kuhn. The Hungarian method for the assignment problem. Naval Res. Logist. Quart., (1-2):83-97, 1955. 7, 17
10

---

Published as a conference paper at ICLR 2024
Scon-Ho Lee and Chang-Sur Kim. Deep repulsive clustering of ordered data based order-identitiy decomposition. In ICLR, 2021. 3
Seon-Ho Lee and Chang-Su Kim. Order learning using partially ordered data via chainization. In ECCV, 2022.
Seon-Ho Lee, Nyeong-Ho Shin, and Chang-Su Kim. Geometric order learning for rank estimation. In NIPS, 2022.
Kyungsun Lim, Nyeong- Shin, Young- Yoon Lee, and Chang-Su Kim. Order learning and its application to age estimation. In ICLR, 2020. 1, 8,
Laurens der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9:2579-2605, 2008.
Nhut Doan Nguyen. Regression with text input using BERT and transformers, 2022. 15
Chuang Niu, Jun Zhang, Ge Wang, and Jimin Liang. GATCluster: Self-supervised Gaussian-attentin network for image clustering. In ECCV, 2020.
Chuang NIu, Hongming Shan, and Ge Wang. SPICE: Semantic pseudo-labeling for image clustering. IEEE Trans. Image Process., 31:7264-7278, 2022. 2
Richard V. Noorden. The ethical questions that haunt facial-reoognition research. Nature, 587(7834):
354-358, 2020.
13
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaisonet, Andreas Köpf, Edward Yang, Zach De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, seth-perffrmacce deep learning library. In NIPS, 2019. 14
Karl Ricanek and Tamirat Tesafaye. MORPH: A longitudinal image database of normal adult ege-progression. FGR, 2006. 1, 1,
Antoaneta Roussi. Resisting the rise of facial recognition. Nature, 587(7834) 2020. 13
Nyeong-Ho Shin, Seon-Ho Lee, and Chang-Su Kim. Moving window regression: A novel approach to ordinal regression. CVPR, 2022.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICMI., 2015. 3
Hui Tang, Ke Chen, and Kui Jia. Unsupervised domain adaptation via structurally regularized deep clustering. In CVPR, 2020.
Yaling Tao, Kentaro Takagi, and Kouta Nakata. Clustering-friendly representation learning via instance discrimination and feature decorrelation. In ICLR, 2021. 1, 2, 6, 7, 8, 16, 17, 18, 19
Tsung Wei Tsai, Chongxuan Li, and Jun Zhu, MiCE: Mixture of contrastive experts for unsupervised image clustering. In ICLR, 2021. 1, 6, 7, 16, 19
Wouter Van Gansbeke, Simon Vandenhende. Stamatios Georgoulis, Mare Proesmans, and Luc V. Gool. SCAN: Learning classify images without labels. ECCV, 2020. 1.2
Jianlong Wu, Keyu Long, Fei Wang, Chen Qian, Cheng Li, Zhouchen Lin, and Hongbin Zha. Deep comprehensive correlation mining for image clustering. In ICCV, 2019. 2
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis.
In ICML, 2016. 2
Su Xing, Xue Shan, Liu Fanzhen, Wu Jia, Yang Jian, Zhou Chuan, Hu Wenbin, Paris Cecile, Nepal Surya, Jin Di, Sheng Quan, and Yu Philip. A comprehensive survey on community detection with deep learning. IEFE Trans. Neural Netw: Learn. Syst., 2022.

---

Published as a conference paper at ICLR 2024
Jiancheng Yang, Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Bingbing Ni. MedMNIST v2: large-scale lightweight benchmark for 2D and 3D biomedical image classification. arXiv preprint 1rXi:22100.17733 2021. 1, 7
Jianwei Yang, Devi Parikh, and Dhruv Batra. Joint unsupervised learning of deep representations and image clusters. In CVPR, 2016. 1,2
Junbo Zhang, Zhiwen Zhang. Yongging Wang. Zhiyong Yan, Qiong Song, Yukai Huang, Ke Li, Daniel Povey, and Yujun Wang. Speechocean762. An open-source non-native english speech corpus for pronunciation assessment. In Interspeech, 2021. 15
Yiqun Zhang and Yiu-ming Cheung. Exploiting order information embedded in ordered categories for ordinal data clustering. In ISMIS, 2018. 3
Yiqun Zhang and Yiu-ming Cheung. An ordinal data clustering algorithm with automated distance learning. In AAAI, 2020.
12

---

Published as a conference paper at ICLR 2024
A BROADER IMPACTS
Recently, ethical concerns about deep-lcarning-basee bbased systems have been raised (Castelvecchi, 2020; Roussi, 2020; Noorden, 2020). Although the proposed algorithm groups instances, including faces, in an unsupervised manner, the results should never be misinterpreted in such a way as to encourage any kind of discrimination. We recommend using the proposed algorithm for research only.
B ALGORITHM DETAILS
B. OPTIMALITY OF CENTROID RULE
After fixing clusters, we update the centroids minimize the objective function J in equation 3. For j & 2, 1, by differentiating with respect to H4 and setting it to zero, we have
0J = 0μ-
Σ 2(2 - h2) + rEC,
Σ zECsp
2(1 - h2) + a Σ 2(1 - hw)
(15)
zECn
2([C,) a C,,l aaCcs.ll1 2(
Σ
h
Σ
h +a a Σ ha)
(16)
zEC;
rECop
zEC;n
O.
(17)
Therefore, the optimal centroid is given by
M4 = Exec, he + a Exec, he + a Exec, hx for j & f1,2, 1,
(18)
C alCcp + ta
For j E 21,2, 1, the centroid rule slightly different due to endpoint effects. For j 1,
OJ
Σ 2(1 - h2)) + Σ
2(
hw)
(19)
0u,
=EC;
aCC,,
2(1C,1 + alC, 1u4 -
1 + a
Σ hwm)
(20)
xEC,
DFC,,
0.
(21)
Different from equation 15, there is no term related to jp in equation 19, since there is no previous cluster for the first cluster C, Thus, the optimal centroid is given by
M1 Exec, he + Evec,, h
for j 1.
(22)
+alC,
Similarly, we have
Mj Enec, M + Exec,, hr
for j
(23)
C, Cal+
For j = 2, we have
aJ
Σ 2(1g - 122) 2a Σ
2(1 - -h)) +a Σ 2(1g - h24
(24)
0p,
zEC;
zECip
zEC
= 2((C,) + 2a C,,l1 + +C D1, - 2( Σ
h + 2a
Σ he + a Σ hz)
(25)
zEC;
EEC 3p
rCC
0.
(26)
13

---

Published as a conference paper at ICLR 2024
Hence, the optimal centroid is
Mj Exec, h₂ + 2a E Exec, h₂ + aIxEe, ho
for 2.
(27)
1c]+ 12,C,, + Cc
Similarly,
[dj Exec, hr + EnEEE, hr + 2a Enec,, h +c 2,
for j =
(28)
B.2 OPTIMALITY OF NCC RULE
Suppose that instance is declared belong cluster Cy. then contributes the objective function in equation 3 by 8(hes Pip MineMy Pjz P.,). ). If it is assigned to another cluster C, then its contribution becomes 8( Mtp Pl: Ht,)) Therefore, to minimize J, x should assigned to C, only
o(h PSp Mis (,,) & 8(h Ml Mls (1,) for all S k.
(29)
Equivalently, we have the NCC rule in equation 5.
B.3 PERMUTATION RULE
After fixing the clusters and the centroids, we rearrange the clusters by applying the optimal permuta- tion o" for minimizing // in equation 3. Note that k! permutations should be considered to find the optimal o², which may require too many computations for large Hence, for is following greedy search scheme for a.
2
use the
Let ae (1.....k: }} > {0, 1,.... #} be partial permutation function. maps different indices to {1....,f) | bijectively and maps the other k indices to zero. Then, the optimal partial permutation of is determined by
of arg min J (((Co,(0)) (Mo.CO) a:
(30)
After obtaining o7, we find the optimal o:41 : fl,..., .}- + 10.1, ++1). 1}. consider two extended permutations o and of satisfying the constraints:
To this end, we
ti1(1) = =j
if of #0,
(31)
0i = -70 +1
if #
(32)
Note that ob+1 and o:t preserve the order of the t bijectively mapped indices in of We select Øt-1, which minimizes J among all possible of+1 and o:+1. as the optimal O²-1- Starting with
1 = 3, we repeat this process until of is obtained. Thus, the number of permutations to consider is
((k-1)(k-2) + (k- (k: 2), and the complexity is O
C MORE EXPERIMENTS
C.I IMPLEMENTATION DETAILS
We do all experiments using PyTorch (Paszke al., 2019) and NVIDIA GeForce RTX 3090 GPU. For the MORPH II dataset, we use settings A and B, which are widely used for evaluation.
Setting 5,492 images of the Caucasian race are selected and then randomly divided into two disjoint subsets: 80% for training and 20% for testing.
Setting 21,000 images Africans and Caucasians are selected to satisfy two constraints: the ratio between Africans and Caucasians should be 1. and that between females and males should be 1: 3. They are split into three disjoint subsets S1. S2, and S3. We use S2 for training and S1 + S3 for testing.
14

---

Published as a conference paper at ICLR 2024
For clustering MOPRH II and CLAP, we partition the entire age range into k consecutive age groups. Table lists the age groups at different k's. These age groups are determined so as to contain similar numbers of instances.
Table 6: Partitioning of the entire age range into age groups The maximum age of each age group is reported. For example, at 6, the second age group in setting A of MORPH II is (21, 27].
MORPH (A)
47
19/
39/42/77
18/20/23 22 33 20/0//2//4411 24/22//24////// /01/A//2//////////11333
MORPH (B)
20/ 32/ 36/41/77
18/ 25 29 /3//42/77
CLAP
30/37/82
18/21
/3//38/82
C.2
MORE RESULTS MORPH
Figure 8 shows examples of clustering results in setting B of MORPH II at k = 6. We see that the proposed UOL algorithm groups the instances according to their ages reliably.
27.67
28.37
30.56
33.58
39.46
41.77
Cluster 1
Cluster 2
Cluster
Clustor
Cluster
Cluster
Figure 8: Examples of clustering results on MORPH II (setting B). For each cluster, the average ground-truth age of its instances is also reported.
C.3 MORE RESULTS ON FER+
Figure shows clustering examples on the FER+ dataset. As done in Figure 5, Figure (a) illustrates how the Anger, Fear, and Disgust images are sorted according to the levels of 'making a face.' Figure 9bb shows clustering results of the Happy, Neutral, and Sad images, in which the images are roughly sorted as
Happy + Neutral + Sad
from cluster to cluster 5. It is worth pointing out that the expression labels are not used in the clustering. Figure 9c) shows clustering results on the Surprise and Neutral images. They are sorted from Neutral (cluster 1) to Surprise (cluster 5).
C.4 RESULTS ON LANGUAGE AND SPEECH DATASETS
We evaluate the performances of UOL simple language and speech datasets.
French sentiment (Nguyen, 2022): It is a dataset for regressing sentiment levels in sentences. It offers 944 sentences in French. Each sentence annotated with 5-scale sentiment score very negative, negative, 3 neutral, positive, and 5 very positive). Figure 10 shows some examples. We adopt BERT (Devlin al., 2019) as the encoder and use no labels for the UOL training.
Speechocean762 (Zhang et al., 2021): It is dataset for scoring English pronunciation. It contains 5,000 utterances from 250 non-native speakers. Each utterance is annotated with 10-scale fluency score. We Wav2Vec2 (Baevski al., 2020) as the encoder. Only the utterances are used for training.
Table 7 shows that UOL shows promising ordered clustering results on these language and speech datasets, well the image datasets.
15

---

Published as a conference paper at ICLR 2024
Cluster
Cluster
Cluster
Cluster 4
Cluster
(a) Anger, Fear, and Disgust
Cluster
Cluster 2
Cluster 3
Cluster 4
Cluster 5
(h) Happy, Neutral, and Sad
Cluster 1
Cluster 2
Cluster 3
Cluster 4
Cluster 5
(c) Surprise and Neutral
Figure 9: Examples of clustering results on the FER+ dataset at l = 5.
Boajour caladropzique gole emplon
us lony ths pon
plank. Néenmorneejj
Jaxaais probienuss telephonigue
parsasre us'a reui rayal Je pour givn
pour
baaeen partots désulés
jour de presaaoos kanertables lls decuments
de
relllen socueilli
clicatis posle
tru clang diaiii.
dier/tapé y
Super SIP surtout gams mrec
pen. predations
temgs
tmp
service
dos gens
mes brajoen
alln
stnformtions,
lour mertal..
rendue
oty gentii
pounzioee penannai gentii
voss
pas siäiponze
se oocope pas peodi
meeccod....
(a) Very Degative
Negative
(c) Neutral
(d) Positive
Very positive
Figure 10: Examples in the French sentiment dataset.
Table 7: Ordered clustering results the French sentiment and Speechocean762 datasets at k 5.
French sentiment
Speechocean762
Algorithm
SRCC(1)
MAE (L)
SRCC(1)
MAE (.)
MiCE (Tsai et al., 2021)
0.196
1.129
0.139
1.314
IDFD (Tao et al., 2021)
0.063
1.258
0.105
1,380
ProPos (Huang et al., 2022)
0.042
1.326
0.107
1.379
Proposed UOL
0.448
0.989
0.672
0.991
16

---

Published as a conference paper at ICLR 2024
C.5 UNSUPERVISED RANK ESTIMATION
Table 8 is an extended version of the unsupervised rank estimation results in Table 4. We measure the performances of the conventional algorithms (Caron al., 2018: Tao al., 2021; Huang al., 2022) using the simple K-NN classification in equation 12, as in UOL. However, since these algorithms do not arrange the clusters meaningfully, their cluster indices contain no rank information. Thus, we permute their clusters optimally via the Hungarian method (Kuhn, 1955). On the contrary, the proposed UOL requires no such supervision. Nevertheless, UOL outperforms the conventional algorithms meaningfully in all tests.
Table 8: Comparison of rank estimation results (MAEs) on the MORPH II, DR, and RetinaMNIST datasets. For MORPH II, 6. For DR and RetinaMNIST, 5.
Algorithm
MORPH (A)
MORPH II (B)
DR
RetinaMNIST
Random guess
1.94
1.94
1.60
1.60
DeepCluster (Caron et al., 2018)
1.59
1.73
1.29
1.16
IDFD (Tao et al., 2021)
1.57
1.84
1.32
1.43
ProPos (Huang et al.. 2022)
1.43
1.54
1.25
1.28
Proposed UOL
1.20
1.31
1.08
1.00
C.6 MORE ANALYSIS
Analysis Table 9 compares the clustering results with different a's. Note that is positive weight to control the influence of adjacent centroids in equation 1. It is reasonable to set a to be less than 0.5. Otherwise, the distances adjacent centroids affect the objective function more greatly than the distance to the corresponding centroid does.
In all tests, we fix a 0.2, which provides the best results in Table 9. However, at both a 0.1 and a = 0.3, UOL still shows comparable or better results than the conventional algorithms in Tables and 3. At a the ordered k-means becomes the ordinary k-means. In such case, the performances degrade severely, for the clustering does not consider the order of clusters.
Table 9: Comparison of ordered clustering results on MORPH II (setting A) and RetinaMNIST according to a in equation For MORPH II, = 6. For RetinaMNIST,
0
0.1
0.2
0.3
Dataset
SRCC (f)
MAE
SRCC
MAE (J)
SRCC (f)
MAE (J)
SRCC (t)
MAE (1)
MORPH (A)
0.159
1.673
0.540
1.267
0.632
1.122
0.479
1.339
RetinaMNIST
1.311
0.544
0.567
0.953
1.023
Analysis on y: Table 10 compares the performances at different y's. In equation 10, a threshold suppress the deviation d of instance from its NCCs be small. If ry is too small, clusters may highly overlap with each other in the embedding space. On the other hand, if y is too large, instances may not be located compactly around their corresponding centroids. In Table 10, the best results achieved at = 0.25. Therefore, we fix 0.25 in all tests.
Table 10: Comparison of ordered clustering results on MORPH II (setting A) and RetinaMNIST according to y. We set i and k 5 for MORPH and RetinaMNIST, respectively.
0.2
=
0.25
=
0.3
0.35
Datasct
SRCC (t)
MAE (-)
SRCC (t)
MAE (1)
SRCC (t)
MAE (1)
SRCC (t)
MAE (L)
MORPH
0.543
1.275
0.632
1.122
0,592
1.180
1.220
RetinaMNIST
0.528
1.002
0.567
0.953
0.532
0.991
0.541
0.970
17

---

Published as a conference paper at ICLR 2024
More comparison with ordinary k-means: Figure 11 compares the clustering results of the ordinary k-means and the ordered h-means on 1D manifold data. The data points are sampled around an curve in the 3D space. The clusters of the ordinary k-means are not arranged in explicit order. In contrast, the ordered k-means groups the data points into sequentially ordered clusters along the 1D) manifold structure.
3
4
5
7
8
-1.0
0.5
1.0
0.5
1.0
(a) Ordinary t-maans
(b) Ordered k- t-manss
Figure 11: Comparison of clustering results.
Comparison of embedding spaces: Figure 12 is an extended version of Figure 1(b), which compares the embedding spaces for MORPH II (setting A). The conventional algorithms cluster object instances in different classes closely without clear distinction; they fail to discover underlying classes reliably. In contrast, UOL well arranges the instances according their classes in the embedding space.
Class
2 3
(a) DeepCluster
(b) IDFD
(c) ProPos
(d) UOL
Figure 12: Comparison of the embedding spaces, for dividing MORPH II (setting A) into six clusters, obtained by (a) DeepCluster (Caron et al., 2018), (b) IDFD (Tao al., 2021), (c) ProPos (Huang et al., 2022), and (d) the proposed UOL algorithm. We group the ground-truth age classes into six age ranges, depicted by colors from blue red.
Embedding space transition: Figure 13 visualizes the transition of the embedding space for MORPH II (setting A) at = 6. As the training step increases, instances are gradually sorted to satisfy the order desideratum in equation Hence, after the training, the instances in different classes are more clearly divided in the embedding space.
3 4
Step 500
500
Step 2000
3000
Step 5000
Step 10000
Figure 13: Embedding space transition for MORPH II (setting A) during the UOL training at k: 6.
18

---

Published as a conference paper at ICLR 2024
Unordered metrics: In Table 11. compare clustering results by employing two unordered metries: Accuracy and normalized mutual information (NMI) Compared to ordinary classification datasets, is more difficult to group instances according to their classes in these orderable datasets of MORPH II and RetinaMNIST. This is because adjacent classes are not clearly distinguished. For example, 16- year-olds and 20-year-olds may have similar appearances. Therefore, the overall scores are relatively low. However, the proposed UOL performs the best in all tests even in terms of the unordered metrics.
Table 11: Comparison of clustering results on MORPH II (setting A) and RetinaMNIST in terms of two unordered metrics: Accuracy and NMI. For MORPH II, k 6. For RetinaMNIST, k 5.
MORPH II (A)
RetinaMNIST
Algorithms
Accuracy (%) (1)
NMI (1)
Accuracy (%) (t)
NMI (t)
MiCE (Tsai al., 2021)
24.1
0.046
32.3
0.104
IDFD (Tao et al., 2021)
21.9
0.007
29.3
0.098
ProPos (Huang et al., 2022)
20.4
0.014
31.2
0.105
Proposed UOL
31.0
0.154
37.9
0.151
Impacts of different backbones: Table 12 lists the ordered clustering results using different back- bones on the MORPH II (setting A) and RetinaMNIST datasets. UOL also performs well with these backbones, indicating that it not affected by the backbones too much.
Table 12:
Comparison of ordered clustering results with different backbones on the MORPH (setting A) and RetinaMNIST datasets. For MORPH II, k = 6. For RetinaMNIST, k: 5.
MORPH I1 (A)
RetinaMNIST
Backbone
SRCC(1)
MAE (1)
SRCC(1)
MAE (L)
VGG16
0.632
1.122
0.567
0,953
ResNet18
0.540
1.246
0.515
0.989
ResNet50
0.590
1.179
0.559
0.967
Impacts of cluster initialization: In Table 13, we list the SRCC results of five random cluster initializations. Also, report the average and standard deviation of the SRCC scores. UOL yields roughly the same order regardless of the cluster initialization, indicating that is not very sensitive to the initialization.
Table 13: Comparison of the SRCC scores with five random initializations on the MORPH II (setting A) and RetinaMNIST datasets. For MORPH II, l 6. For RetinaMNIST, A 5.
2
3
4
5
Average
MORPH II(A)
0.632
0.625
0.630
0.634
0.619
0.628+00.005
RetinaMNIST
0.567
0.564
0.552
0.567
0.567
0.563:10.006
19

---

Published as a conference paper at ICLR 2024
Limitations: In Table 2, UOL fails to yield decent clustering results the CLAP dataset, though it shows good results on the MORPH II dataset. It because CLAP contains more diverse face shots in various environments than MORPH II, illustrated in Figure 14. Also, in addition to facial age estimation and medical assessment, aesthetic score regression is popular ranking task. However, even for UOI., it is hard learn the aesthetic criteria in unsupervised manner, which often subjective and ambiguous.
Since UOL is the first attempt ordered clustering, we focus on developing a simple but reasonable algorithm. Hence, instead of considering all possible cases, UOL assumes that there is total order of underlying classes. However. this is not always the case. Therefore, order broaden the potential use cases, it is required to extend the proposed algorithm to the scenarios where there is no total order e.g. dataset with partial order. We leave this for future work.
Figure 14: Examples of facial photos in the CLAP dataset.
20


Reviews:
[{"review_id": "XCxTZdAKAp", "reviewer": "Reviewer_cgay", "summary": "The paper introduces an unsupervised method to perform clustering when there exists a total order between clusters. This total order can for instance define the age of people in images, and people who are about the same age tend to be in the same cluster or neighbor clusters. The proposed method is similar to soft clustering in the sense that it assigns samples to different clusters (here, at most 3 clusters) and updates the centroids accordingly. However, it also considers some total order on the centroids.", "questions": "How important is initialization? Assuming that there exist different possible orders between categories, would one initialization reflect one order (for instance age) and another reflect something else (for instance color)? And in this case, how would the method be useful for real-world applications since there is no way to control the extracted clustering order? In particular, if we consider network pre-training, one initialization would improve performance only if the extracted order aligns with the target order.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and the exposition of the method is clear. The difference with standard clustering algorithms that do not consider orders between clusters, and also with other ranking methods that use supervision is well defined. Assuming that there exists an order between the cluster in the dataset, the motivation for using the proposed method is clear.\nAs motivated in the paper, the method can be used as a pretraining stage for downstream tasks including ordinal regression, or it can facilitate an initial understanding of data characteristics. However, only the latter part is evaluated in the paper.", "weaknesses": "One main limitation of the method is that it assumes that there exists a total order between the categories/clusters, which is not always the case. The idea of the paper is similar to relative attributes [A] although it considers the unsupervised case. Even with relative attributes, it may be difficult to define a total order between categories so an equivalence between pairs of categories is sometimes defined. Partially ordered sets are in general easier to define than total orders. \n\nMoreover, there might exist different ways to define orders between categories. For instance, in ref [A], the orders between face categories might define age, chubbiness, roundness, color, big lips etc... Fortunately, in Fig 1 (c) of the submission, the face images are ordered by age, but another criterion might have been extracted by the method since it is unsupervised, and the reported scores would not have been as good. \n\n[A] Devi Parikh & Kristen Grauman, Relative Attributes, ICCV 2011", "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": "", "extra_scores": {}}, {"review_id": "qMsWvKQC0m", "reviewer": "Reviewer_kD3Z", "summary": "The paper presents an unsupervised algorithm for clustering ordered data. Specifically, it proposes a so-called ordered k-means algorithm, in which the rules to update the centroids and to find the assignments are modified by adding some reference terms with respect to the previous cluster and the next cluster. Experiments on benchmark datasets are conducted, showing some improvements over the listed baseline algorithms.", "questions": "- It seems not always meaningful to define the previous cluster and the next cluster, provided that the dimension of the embedding space (which is also the dimension of the centriods of the clusters) is larger than 2. \n\n- In Eq. (4), the formula to update the centroids contains a parameter $\\alpha$. As can be read from Table 9, the performance of the clustering is very sensitive the value of the parameter $\\alpha$. The promising performance cannot be obtained without using the proper value of $\\alpha$. Is there any principled rule to set it? Moreover, does the proper value of $\\alpha$ vary from dataset to dataset?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ It sounds interesting to modify the ordinary $k$-means algorithm to handle ordered data clustering. \n+ Experimental results on benchmark datasets show promising improvements.", "weaknesses": "- The difference from the ordinary $k$-means algorithm is the way to update the mean and the way to assign clustering index, both of the two stages are computed by taking a tradeoff between the current clusters and the socalled previous cluster and the next cluster. However, it is not always meaningful to define the previous cluster and the next cluster, if the dimension of the embedding space  (which is also the dimension of the centriods of the clusters) is larger than 2. \n\n- In Eq. (4), the formula to update the centroids contains a parameter $\\alpha$.  From the results in Table 9, the performance is sensitive the parameter $\\alpha$. Without the proper value for parameter $\\alpha$, the promising performance cannot be obtained.", "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": "", "extra_scores": {}}, {"review_id": "igyOlkdhZ1", "reviewer": "Reviewer_T1Ca", "summary": "This paper proposes a new algorithm, called unsupervised order learning (UOL), for clustering ordered data. It aims to discover hidden ranks (or ordered classes) of objects with no supervision.", "questions": "1. As a clustering method, it is inappropriate and unfair to compare only two types of metrics regarding the order of the data, SRCC and MAE. Some basic clustering metrics, such as ACC and NMI, lack comparison. Also this explains why other comparison algorithms achieve poorer performance.\n\n2. We question the value of unsupervised order clustering. The important value of clustering as a classical unsupervised method is that it does not require a tedious data preprocessing process such as labeling data in advance. In contrast, the order clustering proposed by the authors has high requirements for the dataset itself (sequentially), and such requirements are usually obtained by tedious manual sorting, which contradicts the advantages of clustering itself. Can the authors provide a real dataset or scenario where sequential order exists and clustering is required? Note that this is different from the manually ordered dataset used by the authors in the experimental section.\n\n3. Why did you select only two data sets for your different ablation experiments? Did the authors artificially select the datasets to present the ablation experiments? Meanwhile, the parameter \\gamma lacks ablation experiments with relevant parameter descriptions. More experimental results are expected", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The author proposes the first deep clustering algorithm for ordered data.\n\n2. The authors have introduced the ordered k-means algorithm, which extends the conventional k-means approach.\n\n3. This enhanced method effectively groups object instances and arranges the resulting clusters in a meaningful order. The authors have also provided a proof of the local optimality of the solution.", "weaknesses": "See questions", "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": "", "extra_scores": {}}, {"review_id": "bOFPwh7C36", "reviewer": "Reviewer_rbKP", "summary": "This paper proposed an unsupervised order clustering algorithm for dealing with order data To be specific, authors first proposed a ordered k-means algorithm which defines a measurement of the deviation of sample x from the cluster centroid chain in learned embedding space. Then authors claim that the ordered clustering can be defined as the distance between sample x and its centroid and two neighbored centroids. Based on these, authors proposed an ordered k-means algorithm for clustering ordered data.", "questions": "N/A", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper is well-written and the core idea and motivation are easy to follow.", "weaknesses": "First, In page 3, authors claimed that “we propose the first unsupervised algorithm for order learning”. Actually, this paper belongs to a kind of ordered data clustering task, which has been studied in many previous works, such as \n[1] An ordinal data clustering algorithm with automated distance learning, AAAI, 2020;\n[2] Deep repulsive clustering of ordered data based on order-identity decomposition, ICML, 2020.\nThus, this sentence is not precise.\n\nSecond, the deviation of sample x from the chain is borrowed from Lim et al. 2020, thus the true contribution of this paper is the ordered k-means algorithm in Algorithm 1 which is easy to deduce if we have Eq. (1). In a word, I think the true contribution is not enough for ICLR.\n\nThiredly, in experiments, the compared algorithms mostly are traditional clustering algorithms which can not verify the effectiveness of proposed methods. \n\nIn all, I prefer to give the “marginally below the acceptance threshold” decision.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)