# Expert-Agnostic Ultrasound Image Quality Assessment using
Deep Variational Clustering

Deepak Raina12∗, Dimitrios Ntentia23, SH Chandrashekhara4, Richard Voyles2,
Subir Kumar Saha1
This work was supported in part by SERB (India) - OVDF Award No.
SB/S9/Z-03/2017-VIII; PMRF - IIT Delhi under Ref. F.No.35-5/2017-TS.I:PMRF;
Daniel C. Lewis Professorship; Berea College, Kentucky, USA and PU-IUPUI
Collaborative Seed Grant.1Indian Institute of Technology (IIT), Delhi, India
({deepak.raina, saha}@mech.iitd.ac.in); 2Purdue University (PU), Indiana, USA
({draina, ntentiad<EMAIL_ADDRESS>3Berea College, Kentucky, USA
(ntentiad@berea.edu); 4All India Institute of Medical Sciences (AIIMS), Delhi,
India (drchandruradioaiims@gmail.com).∗Corresponding author is Deepak Raina

###### Abstract

Ultrasound imaging is a commonly used modality for several diagnostic and
therapeutic procedures. However, the diagnosis by ultrasound relies heavily on
the quality of images assessed manually by sonographers, which diminishes the
objectivity of the diagnosis and makes it operator-dependent. The supervised
learning-based methods for automated quality assessment require manually
annotated datasets, which are highly labour-intensive to acquire. These
ultrasound images are low in quality and suffer from noisy annotations caused
by inter-observer perceptual variations, which hampers learning efficiency. We
propose an UnSupervised UltraSound image Quality assessment Network, US2QNet,
that eliminates the burden and uncertainty of manual annotations. US2QNet uses
the variational autoencoder embedded with the three modules, pre-processing,
clustering and post-processing, to jointly enhance, extract, cluster and
visualize the quality feature representation of ultrasound images. The pre-
processing module uses filtering of images to point the network’s attention
towards salient quality features, rather than getting distracted by noise.
Post-processing is proposed for visualizing the clusters of feature
representations in 2D space. We validated the proposed framework for quality
assessment of the urinary bladder ultrasound images. The proposed framework
achieved $\mathbf{78\%}$ accuracy and superior performance to state-of-the-art
clustering methods. The project page with source codes is available at
https://sites.google.com/view/us2qnet.

##  I Introduction

UltraSound (US) is the most frequently employed medical imaging modality in
clinical practice due to its real-time feedback, low-cost, portability, and
non-ionizing nature. It is useful for diagnosis, pre- and post-operative
assessment, and surgical interventions. However, the diagnosis by ultrasound
depends a lot on the image quality, which is determined manually by
sonographers during image acquisition [1]. Ultrasound images are quite
difficult to interpret due to noise, shadows, poor contrast, and other sensors
and motion artifacts [2]. The blurred boundaries and presence of multiple
anatomical structures further increase the difficulty in ensuring quality
during acquisition.

Figure 1: A preview of the framework for US-IQA using deep variational
clustering. The circular clusters represent the ultrasound image
classification based on their quality.

Thus, the requirement of minimal manual effort and ensuring consistent quality
among novice sonographers during image acquisition has prompted the research
community to use automated methods for US Image Quality Assessment (US-IQA).

The supervised learning-based methods using a deep Convolutional Neural
Network (CNN) have shown promising results in medical imaging analysis,
including segmentation and classification using curated and annotated large-
scale datasets [3]. However, the manual data annotation process is quite
difficult for US image quality, as the US images with the same quality have
significant differences and images with significant differences in quality
appear similar. Moreover, the image quality annotation is noisy due to inter-
and intra-observer perceptual variations [4]. Thus, the annotation process is
often labour-intensive, time-consuming and requires the participation of more
than one expert radiologists, thereby making supervised learning quite
challenging for automated US-IQA.

In this work, we propose an UnSupervised learning-based UltraSound image
Quality assessment Network, termed as US2QNet, as shown in Fig. 1. The
objective of the work is to address the complexity and uncertainty in manual
annotation of US image quality by expert radiologists for supervised learning.
The key contributions of framework are as follows:

  1. 1.

We proposed the first deep clustering framework for US-IQA, which uses a
variational autoencoder in conjunction with pre-processing, clustering and
post-processing modules. The framework will jointly enhance, extract, cluster
and visualize the quality feature representation of US images.

  2. 2.

We introduced US imaging-specific pre- and post-processing modules in deep
clustering. Pre-processing uses fuzzy filtering to direct the network’s
attention towards the critical quality features. The post-processing module
generates the visualization of high-dimensional quality feature
representations in 2D space and provides an effective way to do hyperparameter
tuning.

  3. 3.

The proposed framework was validated and compared to the state-of-the-art
(SOTA) methods for urinary bladder US images. The results revealed that the
proposed method is effective for unsupervised US-IQA and outperformed the SOTA
methods.

The unsupervised deep clustering approach strategy has previously been
investigated mostly for natural images [5, 6, 7], however, to the best of the
author’s knowledge, this is the first attempt to use this approach for the
challenging task of classifying the US images based on quality.

###  I-A Related work

Supervised learning for US-IQA: The availability of annotated medical images
has motivated the researchers to use supervised training of CNNs for automated
analysis of X-ray, Magnetic Resonance Imaging (MRI), and US imaging [3]. For
US-IQA, Wu et al. [8] proposed the two deep CNNs for jointly finding the
region of interest and assessing the fetal ultrasound image quality. Lin et
al. [9, 10] used a multi-task faster regional CNN architecture to first
localize the six key anatomical structures of the fetal head and then assigned
the quality score based upon their clear visibility. However, they employed
prior clinical knowledge to determine the relative position of anatomical
structures. In addition, the fetal US datasets in [8, 9, 10] require
substantial clinical expertise for labeling the region of interest and
anatomical structures with comparable appearances such as stomach bubble,
umbilical vein, choroid plexus, and others. Moreover, the performance of
supervised IQA models is impacted by annotation noise due to inter- and intra-
observer perceptual variations [4].

Unsupervised learning for medical imaging: In order to overcome the challenges
of labour-intensive annotation in supervised learning, different techniques of
unsupervised learning have been explored for medical imaging analysis [11].
These techniques used traditional clustering methods [12], modern methods like
Autoencoder (AE), generative networks [13], and Deep Clustering [14]. AE is
one of the most effective algorithms for unsupervised feature extraction and
compression to low-dimensional latent space while minimizing the
reconstruction error between the encoded input and decoded output. They have
been mostly used for denoising and anomaly detection in medical images [15].
In addition, Generative networks like Variational AE (VAE) have also shown
great potential for medical image analysis [16]. They use variational loss
during training and enforce a predefined distribution in the latent space. A
work by Nesovic et al. [17] attempted to address the US-IQA using AE combined
with Random Forest Classifier (RFC). However, RFC required noise-specific
hand-crafted features for quality classification, which are challenging to
design for noisy US images [2].

Deep clustering for image classification: Clustering is another powerful
unsupervised method to detect patterns in non-labelled dataset. There exist
several classical clustering algorithms like $k-$means, Principal Component
Analysis (PCA), Density-Based Spatial Clustering of Applications with Noise
(DBSCAN) [18], Spectral clustering [19], t-distributed Stochastic Neighbor
Embedding (t-SNE) [20], Uniform Manifold Approximation and Projection (UMAP)
[21]. However, they can’t handle high-dimensional data. In recent years, deep
clustering has gained the researcher’s attention for unsupervised image
analysis [5, 6, 7]. Deep clustering uses classical clustering methods in
conjunction with AEs and VAEs to learn the clusterable representation in
latent space. This has been used for the categorization of handwritten digits
and face images [22], natural image datasets [23], Magnetic Resonance Imaging
[24, 25] and Computed Tomography images [26]. Yu et al. [27] proposed deep
clustering for classifying thyroid cancer in US images. Notably, the potential
of deep clustering has not yet been uncovered for US-IQA, which is quite
challenging to analyze due to the noise, artifacts, varying viewpoints, low
inter-class and huge intra-class variability [2].

##  II Methodology

Figure 2: Overview of the US2QNet architecture for ultrasound image quality
assessment using deep variational clustering.

Fig. 2 depicts the overview of the proposed framework. The framework is
executed in three stages, which include: (1) Training the VAE on the pre-
processed dataset using the reconstruction function as the loss function; (2)
Fine-tuning the VAE by jointly optimizing the reconstruction loss and
clustering loss for achieving clusterable quality feature representation of US
images; and (3) Dimensionality reduction and visualization of learned feature
representation using UMAP. Later, we utilized HDBSCAN for assigning labels to
the clusters corresponding to the US image quality.

###  II-A Variaional Autoencoder

VAE is the generative variant of AE, as it enforces the encoder of AE to
generate features representing a normal distribution
$\mathcal{N}(\boldsymbol{\mu},\boldsymbol{\sigma})$ in the latent space. VAEs
have shown success in multi-class clustering due to their generative
representation capability. The VAE introduces and approximates a latent
variable $\boldsymbol{z}$ that follows a prior distribution
$p(\boldsymbol{z})$. The model then infers a posterior distribution
$q_{\boldsymbol{\phi}}(\boldsymbol{z}|\boldsymbol{x})$, and an output of
$p_{\boldsymbol{\theta}}(\boldsymbol{x}|\boldsymbol{z})$, with encoder
parameterized by $\boldsymbol{\phi}$ and a decoder parameterized by
$\boldsymbol{\theta}$. Therefore, the objective of variational inference is to
precisely compute $p_{\boldsymbol{\theta}}(\boldsymbol{x}|\boldsymbol{z})$ by
inferring the latent distribution from the observed dataset. During training,
a latent vector $\boldsymbol{z}$ is sampled from
$p_{\boldsymbol{\theta}}(\boldsymbol{z})$, and the decoder produces the
parameters of $p_{\boldsymbol{\theta}}(\boldsymbol{x}|\boldsymbol{z})$, which
we may use to sample an output vector $\boldsymbol{x}$. The following equation
formulates the loss function of VAE as:

$\boldsymbol{L}(\boldsymbol{\phi},\boldsymbol{\theta};\boldsymbol{x})=\mathbb{E}_{\boldsymbol{z}\sim
q_{\boldsymbol{\phi}}(\boldsymbol{z}|\boldsymbol{x})}[\log
p_{\boldsymbol{\theta}}(\boldsymbol{x}|\boldsymbol{z})]\\\
+D_{KL}(q_{\boldsymbol{\phi}}(\boldsymbol{z}|\boldsymbol{x})||p_{\boldsymbol{\theta}}(\boldsymbol{z}))$
(1)

where the first term is reconstruction error between observed data and data
decoded from the latent vector and the second term is Kullback-Leibler ($KL$)
divergence between the distribution of observed data
$q_{\boldsymbol{\phi}}(\boldsymbol{z}|\boldsymbol{x})$ and a certain
distribution $p_{\boldsymbol{\theta}}(\boldsymbol{z})$. The prior
$p_{\boldsymbol{\theta}}(\boldsymbol{z})$ in VAE is often modeled by a single
multivariate Gaussian in VAEs [28]. Lin et al. [29] proposed using a mixture
of Gaussian as prior for unsupervised classification of the CIFAR Dataset and
achieved remarkable results. Inspired by their work, we have used a mixture of
Gaussian as prior $p_{\boldsymbol{\theta}}(\boldsymbol{z})$ for the latent
space distribution representation to accurately describe the structure of each
cluster using a specific Gaussian.

Pretraining of VAE: During pre-training, we used
$\boldsymbol{L}(\boldsymbol{\phi},\boldsymbol{\theta};\boldsymbol{x})$ as the
loss function (denoted as $\boldsymbol{L}_{V}$) to optimize the set of
parameters $\boldsymbol{\theta}^{*}$ of VAE as

$\boldsymbol{\theta}^{*}=arg\max_{\boldsymbol{\theta}}\boldsymbol{L}(\boldsymbol{\phi},\boldsymbol{\theta};\boldsymbol{x})$
(2)

###  II-B Deep variational clustering

Several algorithms have been proposed for deep clustering as described in
Section I-A. Among them, Deep Embedded Clustering (DEC) [5] is one of the most
representative methods of deep clustering, which proposed joint optimization
of feature representation and clustering. In our framework, we used VAE, in
contrast to AE in [5] and embedded the DEC module between the encoder and
decoder. We used the acronym DEC-VAE in the paper for this clustering
approach. The joint loss function is then given by the sum of VAE loss
($\boldsymbol{L}_{V}$) and clustering loss and is formulated as follows:

$\boldsymbol{L}=\boldsymbol{L}_{V}+\gamma\boldsymbol{L}_{C}$ (3)

where $\boldsymbol{L}_{C}$ is the clustering loss and $\gamma$ is a
coefficient used to control the degree of distortion in the latent space.

Clustering loss: The clustering module works like a validation set, where in
each epoch, we used an auxiliary target distribution $\boldsymbol{Y^{t}}$ to
iteratively correct the distribution of predicted label assignments
$\boldsymbol{Y}^{p}$. To define clustering loss, we used the $KL$ divergence
to decrease the difference between the $\boldsymbol{Y^{t}}$ and
$\boldsymbol{Y^{p}}$ distribution as:

$\boldsymbol{L}_{C}=D_{KL}(\boldsymbol{Y^{t}}||\boldsymbol{Y^{p}})=\sum_{i}^{N}\sum_{j}^{K}\boldsymbol{y}^{t}_{ik}\log\frac{\boldsymbol{y}^{t}_{ik}}{\boldsymbol{y}^{p}_{ik}}$
(4)

where $\boldsymbol{y}^{p}_{ik}$ denotes the probability of assigning cluster
$\mu_{k}$ to latent feature $\boldsymbol{z}_{i}$ and $\boldsymbol{y}^{t}_{ik}$
is the auxiliary target distribution. The $\boldsymbol{y}^{p}_{ik}$ is
calculated using Student’s t-distribution as:

$\boldsymbol{y}^{p}_{ik}=\frac{(1+||\boldsymbol{z}_{i}-\boldsymbol{\mu}_{k}||^{2})^{-1}}{\sum_{i}(1+||\boldsymbol{z}_{i}-\boldsymbol{\mu}_{k}||^{2})^{-1}}$
(5)

where $\boldsymbol{\mu}_{k}$ is the initial cluster centroids and calculated
by performing standard $k-$means clustering. The target distribution
$\boldsymbol{y}^{t}_{ik}$ is defined by the following equation:

$\boldsymbol{y}^{t}_{ik}=\frac{\boldsymbol{y}_{ik}^{p^{2}}/\sum_{i}\boldsymbol{y}^{p}_{ik}}{\sum_{i}(\boldsymbol{y}_{ik}^{p^{2}}/\sum_{i}\boldsymbol{y}^{p}_{ik})}$
(6)

The clustering loss in eq. (4) is used to correct the weights, representing
cluster centers $\boldsymbol{\mu}_{k}^{K}$, and pivot the image latent feature
$\boldsymbol{z}_{i}$ from a generative image representation to a
representation focused on discriminative quality features in the latent space
distribution. We have used three clusters ($K=3$) in our dataset representing
three levels of US image quality.

###  II-C Post-processing

The post-processing module is used to visualize the feature representation in
2D space, which provides an effective way to analyze the model’s accuracy. The
visualization of clusters also played an important role in the selection and
iterative correction of the network hyper-parameters. After fine-tuning the
network weights, the latent space feature vector is sampled from learned
feature distribution as
$[\boldsymbol{z}_{1}\sim\mathcal{N}_{1},\cdots,\boldsymbol{z}_{N}\sim\mathcal{N}_{N}]$.
Then, the latent space feature vector of dimension $N$ is transformed to
lower-dimensional space $\tilde{N}$ as
$[\tilde{\boldsymbol{z}}_{1},\cdots,\tilde{\boldsymbol{z}}_{\tilde{N}}]$ for
efficient clustering of features. Several algorithms exist for dimensionality
reduction and clustering analysis like PCA, $k-$means, t-SNE, UMAP, and
HDBSCAN, as discussed in Section I-A. Our exhaustive study on different
clustering approaches revealed that UMAP for dimensionality reduction followed
by HDBSCAN for label assignment outperformed all other combinations. The UMAP
is chosen to ensure the efficient learning of manifold structure from a high-
dimensional latent feature representation. In addition, UMAP returns
reproducible results which is not the case in other dimensionality reduction
methods like PCA. The capability of HDBSCAN to preserve both global and local
density clusters while effectively separating overlapping data makes it a
desirable option for label assignment [30].

##  III Dataset

Collection: The dataset consists of US images collected during the feasibility
study of our in-house developed Telerobotic Ultrasound (TR-US) system [31, 32]
at All India Institute of Medical Sciences (AIIMS), New Delhi (a public
hospital and medical research university in India). The AIIMS Ethics Committee
approved the study (Ref. No. IEC-855/04.09.2020,RP-16/2020). The study was
conducted between October $2021$ and December $2021$. Before the scanning
operation, informed written consent was obtained from the volunteers, and
their privacy was protected by anonymizing their identifiers in the image. The
dataset consists of male urinary bladder US images, which is used for
discriminating the bladder shape, and identifying diverticula, stones,
malignant tumours, and free fluid (blood) during trauma. The dataset is
challenging to analyze, having spurious textures and inter- and intra-subject
variations.

Pre-processing: The deep learning models are quite sensitive to noise in
images, therefore ultrasound images, which are often noisy, need to be
filtered without affecting the key diagnostic details and edges of anatomical
structures. In the pre-processing module, we employed two US imaging-specific
techniques for enhancing their quality [33]. First, we used fuzzy modeling to
distinguish noise from edges and other diagnostic details in the image. We
used the fuzzy filter proposed in [34], which effectively balances the degree
of noise removal and edge preservation. It used the fuzzy logic-based
uncertainty modeling, which acquires the statistical parameters (mean and
variance) of the local window $\mathbb{W}_{l}$ in the image to find its
similarity with non-local window $\mathbb{W}_{nl}$. Then, the degree of
similarity of the similar local and non-local regions is computed using
euclidean distance as:

$d_{s}=||\mathbb{W}_{l}-\mathbb{W}_{nl}||$ (7)

Finally, the noise-free pixel of image $\tilde{p}_{i}$ is estimated using the
fuzzy centroid technique and is given as:

$\tilde{p}_{i}=\frac{1}{\sum_{j=1}^{n}w_{k}}\sum_{j=1}^{n}(p_{j}\times w_{j})$
(8)

where $n$ is the count for similar local and non-local regions, $p_{j}$ is the
value of the central pixel of window $\mathbb{W}_{j}$ and $w_{j}$ is the
weight assigned to the most similar pixel, calculated using Gaussian-shaped
fuzzy function with zero means $(\mu=0)$ and noise variance $(\sigma^{2})$ as:

$w_{k}(d_{s};\sigma,\mu)=\exp^{\frac{-(d_{s}-\mu^{2})^{2}}{2\sigma^{2}}}$ (9)

The fuzzy filtering will enable the network to extract essential quality-
related features rather than being distracted by the noise in the US images.
Second, we used the sharpening filter, which emphasizes the boundaries of
anatomical structures by increasing the contrast between the bright and dark
regions of the US image [35], thereby enhancing the overall appearance of the
image. We used a 4-neighbors laplacian filter:
$[[0,-1,0],[-1,5,-1],[0,-1,0]]$, to sharpen the US images. Finally, horizontal
flipping is also employed to augment the dataset and prevent the over-fitting
of the model on a small US dataset. This will mirror the anatomical structures
in the US images, as they can appear on both sides of the transducer cone
during scanning.

Testing dataset: The dataset consisted of total $1833$ US images. We randomly
split the dataset into training and testing set with $90:10$ ratio. We used
the labelled testing dataset, as shown in Fig. 3, to validate the proposed
framework. The labelling criteria is adopted from the internationally
prescribed 5-level quality assessment scale [36]. Three radiologists with more
than $15$ years of experience in abdomen radiology labeled the dataset. The
score assesses the image based on the diagnostic quality, which depends on
structural shape/size/placement and acceptability of artifacts. We measured
inter-rater reliability with Intra-Class Correlation (ICC) [37] and obtained a
high value of $0.965$, indicating excellent agreement. However, the supervised
US-IQA model in [38] achieved only $75.3\%$, $77.2\%$, and $76.3\%$ accuracy
with respect to three experts, while accuracy for the average rating of three
experts is $87.3\%$. These results reveal that inter- and intra-observer
perceptual variations pose challenges for supervised US-IQA models. Further,
we used Silhouette Coefficient (SC) analysis [39] on the dataset to choose an
optimal value for the number of clusters. For $3$ clusters, SC value was
$0.7628$, while for $4$ and $5$ clusters, it was $0.6381$ and $0.5829$,
respectively. Therefore, we used three quality labels for the testing set as
Below Average ($A-$), Average ($A$) and Above Average ($A+$), where $A$ is
collectively used for images rated as $2$ and $3$; and $A+$ for images rated
as $4$ and $5$ by experts.

Figure 3: Sample test set images with their quality labels mentioned on the
extreme left of each quality set.

##  IV Results and Analysis

###  IV-A Implementation details

The proposed model was implemented using Python $3.8$ and Pytorch $1.11$. The
pretraining, training and testing have been conducted using a Dell Workstation
with Nvidia GeForce RTX $3090$ GPU having $24$ GB of memory. We used the
greyscale images and resized them to $224\times 224$, and the training set
included our pre-processed dataset. The size of window $\mathbb{W}$ used for
the fuzzy filter is $5\times 5$. The weights of the VAE have been learned in
the pretraining phase. The latent space dimension $N$ is kept to $80$ to
extract rich features in the latent space for efficient clustering. The choice
of latent space dimension has been decided iteratively based on the clustering
accuracy scores. The batch size used is $128$ with a learning rate of $0.01$.
For the fine-tuning phase, VAE was trained by embedding the clustering module,
as described in Section II-B. The value of $\gamma$ used in eq. (3) is $0.1$.
The batch size used is $64$ and the learning rate is $0.005$. The model was
trained for $200$ epochs with early stopping criteria, which is based on the
stagnation of the loss function values during training for $10$ epochs.

###  IV-B Evaluation metrics

In order to validate the clustering quality of our model, we used four
evaluation metrics, namely Adjusted Random Index (ARI), Adjusted Mutual
Information (AMI), Unsupervised Clustering Accuracy (ACC), and Normalized
Mutual Information (NMI) [40]. The value of these metrics varies from $0$ to
$1$, denoting the accuracy of clustering.

###  IV-C Pre-trained VAE analysis

We quantitatively analyzed the reconstruction of US images in the test set by
the trained VAE using the Structural Similarity Index Measure (SSIM) and Mean
Square Error (MSE), as shown in the table I. In order to analyze the effect of
pre-processing on extracting rich features from ultrasound images, we also
analyzed the reconstructed images without the pre-processed dataset. The image
with quality labels A and A+ showed significant improvement in the scores due
to the enhancement of anatomical appearance features, thereby enabling the
network to focus on key quality features. The image of quality A- has shown
slight improvements in scores due to the absence of anatomical structures in
the views.

TABLE I: Quantitative comparison of testing set to analyze the reconstruction
by trained VAE.

Metric | Without pre-processing | With pre-processing
---|---|---
A- | A | A+ | A- | A | A+
SSIM | $0.90$ | $0.85$ | $0.81$ | $0.91$ | $0.93$ | $0.93$
MSE | $11.01$ | $12.89$ | $13.64$ | $10.34$ | $9.80$ | $9.95$

###  IV-D Clustering performance analysis

Results with US Image dataset: We trained the model on the entire US dataset
and visualized the cluster for $183$ test images using UMAP for dimensionality
reduction followed by HDBSCAN for label assignment. Fig. 4 demonstrates that
the clusters generated

Figure 4: Clustering visualization of US dataset: (a) After pretraining; and
after embedding clustering module and training till (b) epoch $70$; (c) epoch
$140$; (d) epoch $200$

after pretraining the VAE has a lot of overlapping points, however, the model
is progressively getting better after fine-tuning the weights with the
clustering module, with the separation of clusters being more evident along
with the reduction in overlapping data points. This change becomes
quantitatively evident, with a $32.8\%$ increase in ARI, $25.2\%$ in AMI,
$32\%$ in NMI and $26.2\%$ in ACC scores from the pretraining stage to
training with clustering module, as shown in Fig. 5(a).

Results with MNIST dataset: We also demonstrated the effectiveness of the
proposed model on the MNIST digit dataset [41]. The values of evaluation
matrices are shown in 5(b), which demonstrates similar improvements in
clustering as observed in the US dataset. Note that ultrasound-specific pre-
processing has not been used for MNIST.

(a)

(b)

Figure 5: Evaluation metrics comparison for (a) US and (b) MNIST dataset after
pre-training (PT) and then training with clustering module. TABLE II:
Comparison of clustering performance on US and MNIST dataset using SOTA
classical and Deep Embedded Clustering (DEC)-based methods.

Dataset | Metrics | $k-$means | t-SNE | UMAP | HDBSCAN |  PCA +$k-$means |  DEC-AE +$k-$means |  DEC-AE +t-SNE |  DEC-AE +UMAP |  DEC-VAE +$\boldsymbol{k-}$means |  DEC-VAE +t-SNE |  US2QNet
---|---|---|---|---|---|---|---|---|---|---|---|---
US Images | ARI | 0.296 | 0.385 | 0.384 | 0.374 | 0.366 | 0.487 | 0.502 | 0.547 | 0.532 | 0.619 | 0.882
AMI | 0.245 | 0.394 | 0.379 | 0.335 | 0.389 | 0.393 | 0.410 | 0.446 | 0.545 | 0.637 | 0.821
ACC | 0.342 | 0.389 | 0.384 | 0.326 | 0.360 | 0.536 | 0.627 | 0.673 | 0.587 | 0.742 | 0.783
NMI | 0.287 | 0.371 | 0.354 | 0.330 | 0.296 | 0.288 | 0.419 | 0.453 | 0.553 | 0.585 | 0.823
MNIST | ARI | 0.570 | 0.468 | 0.386 | 0.438 | 0.546 | 0.596 | 0.834 | 0.868 | 0.556 | 0.887 | 0.896
AMI | 0.595 | 0.466 | 0.547 | 0.346 | 0.528 | 0.623 | 0.694 | 0.845 | 0.619 | 0.870 | 0.897
ACC | 0.546 | 0.834 | 0.846 | 0.569 | 0.468 | 0.799 | 0.857 | 0.847 | 0.821 | 0.715 | 0.853
NMI | 0.502 | 0.825 | 0.842 | 0.532 | 0.540 | 0.725 | 0.704 | 0.886 | 0.796 | 0.860 | 0.883

###  IV-E Comparison with State-of-the-art methods

In this experiment, we compared our method with five classical clustering
methods, including the $k-$means, t-SNE, UMAP, HDBSCAN and PCA with $k-$means
(PCA+$k-$means) as well as state-of-the-art DEC methods, such as DEC-CAE with
$k-$means, t-SNE and UMAP for dimensionality reduction in post-processing. To
compare the DEC-VAE-based method with the AE versions, we used similar
versions referred to as DEC-VAE+$k-$means, DEC-VAE$+$t-SNE and DEC-VAE$+$UMAP
(US2QNet). The results are shown in Table II. It is noted that our proposed
method, US2QNet has obtained the highest performance on US and MNIST dataset.
It outperforms classical clustering methods including $k-$means, t-SNE, UMAP,
HDBSCAN and PCA$+k-$means for the US dataset on the NMI score by $65.1\%$,
$54.9\%$, $56.9\%$, $59.9\%$ and $64.0\%$, respectively. The DEC-VAE with
$k-$means, t-SNE and UMAP reports an increase in NMI score in contrast to its
corresponding versions of DEC-AE by $47.9\%$, $28.4\%$ and $44.9\%$,
respectively. Similar improvements have also been noticed in ARI, AMI, ACC and
NMI on MNIST and US dataset, indicating that the proposed method is effective
in unsupervised US-IQA. The performance of different clustering methods for
the US image dataset is visualized in Fig. 6. The results show that the
clusters generated by the proposed method (Fig. 6(d)) are more evenly
distributed and individually closely packed than the other classical and DEC-
based approaches. Further, we calculated the ACC values for $4$ and $5$
clusters, resulting in $0.543$ and $0.542$ respectively. From this, it can be
asserted that the proposed framework is appropriate for $3$ clusters.

Figure 6: Visualization of clustering obtained using (a) UMAP; (b) t-SNE; (c)
DEC-AE+UMAP; (d) DEC-VAE+UMAP (US2QNet) for US dataset.

###  IV-F Ablation study

To analyze the contribution of different components of the proposed method in
enhancing the clustering of US image quality, we performed the ablation study
of our model. The results are reported in Table III. We compared the proposed
method with Pre-Processing (PP) only and with Pre-Training (PT) only. The
metric used in the plot is ACC. It is evident from the figure that PP and PT
modules have contributed to enhancing the performance of the proposed method.
Without PT and PP modules, the ACC value is $0.544$. The model with only pre-
processed dataset without pre-training has an ACC score of $0.569$, while
using the pre-trained VAE and unprocessed dataset, the model reported an ACC
score of $0.643$. However, with the introduction of PP along with PT, the
score impressively increased to $0.783$.

TABLE III: ACC scores for ablated versions of US2QNet with and without pre-
processing (PP) and pre-training (PT)

without PT, PP | with PP only | with PT only | with PT and PP
---|---|---|---
$0.544$ | $0.569$ | $0.643$ | $0.783$

###  IV-G Real-time implementation

We have integrated the US2QNet with the ultrasound machine in order to
evaluate its real-time efficacy. The US video is captured by the Sonosite
M-TURBO ultrasound machine and is transferred to the GPU laptop using Epiphan
DVI2USB 3.0 (Epiphan Video, Canada). The manual scanning of the pelvic region
is conducted, as shown in Fig. 7. It has been found that US2QNet efficiently
evaluates the quality of US images per frame in $0.0552$ seconds. The
sonographer found it to be a useful tool for assisting the novice operator in
conducting the procedure, however, they would like the range of quality
scoring to be increased as per clinical protocols for precisely guiding the
probe maneuvers.

Figure 7: Real-time implementation of US2QNet for assisting the manual
ultrasound procedure

##  V Conclusion and Future work

We introduced the first-of-its-kind UltraSound Image Quality Assessment (US-
IQA) using unsupervised learning. This will alleviate the burden and
uncertainty associated with manual annotation of US image quality for
supervised learning. The proposed model, US2QNet, leverages the variational
autoencoder in conjunction with three modules, pre-processing, clustering and
post-processing for effectively enhancing, classifying and visualizing the
quality features representations of US images. The validation on urinary
bladder US images demonstrated that the proposed framework could generate
clusters with $78\%$ accuracy and performs better than state-of-the-art
methods. We hope our preliminary results will generate the community’s
attention towards this efficient but previously ignored topic of unsupervised
US-IQA. In future, we would aim for an end-to-end DNN framework without pre-
processing. Further, we would incorporate an automatic selection of quality
clusters rather than fixing them beforehand. Additionally, our future work
will demonstrate the applicability of the proposed framework for assisting
autonomous robotic ultrasound [31].

## References

  * [1] M. K. Welleweerd, A. G. de Groot, S. de Looijer, F. J. Siepel, and S. Stramigioli, “Automated robotic breast ultrasound acquisition using ultrasound feedback,” in 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 9946–9952, IEEE, 2020.
  * [2] J. A. Noble, “Reflections on ultrasound image analysis,” 2016.
  * [3] D. Shen, G. Wu, and H.-I. Suk, “Deep learning in medical image analysis,” Annual review of biomedical engineering, vol. 19, p. 221, 2017.
  * [4] S. Wang, C. Li, R. Wang, Z. Liu, M. Wang, H. Tan, Y. Wu, X. Liu, H. Sun, R. Yang, et al., “Annotation-efficient deep learning for automatic medical image segmentation,” Nature communications, vol. 12, no. 1, pp. 1–13, 2021.
  * [5] X. Guo, X. Liu, E. Zhu, and J. Yin, “Deep clustering with convolutional autoencoders,” in Neural Information Processing (D. Liu, S. Xie, Y. Li, D. Zhao, and E.-S. M. El-Alfy, eds.), (Cham), pp. 373–382, Springer International Publishing, 2017.
  * [6] M. Caron, P. Bojanowski, A. Joulin, and M. Douze, “Deep clustering for unsupervised learning of visual features,” in Proceedings of the European conference on computer vision (ECCV), pp. 132–149, 2018.
  * [7] M. Caron, P. Bojanowski, J. Mairal, and A. Joulin, “Unsupervised pre-training of image features on non-curated data,” in Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 2959–2968, 2019.
  * [8] L. Wu, J.-Z. Cheng, S. Li, B. Lei, T. Wang, and D. Ni, “Fuiqa: fetal ultrasound image quality assessment with deep convolutional networks,” IEEE transactions on cybernetics, vol. 47, no. 5, pp. 1336–1349, 2017.
  * [9] Z. Lin, M. H. Le, D. Ni, S. Chen, S. Li, T. Wang, and B. Lei, “Quality assessment of fetal head ultrasound images based on faster r-cnn,” in Simulation, Image Processing, and Ultrasound Systems for Assisted Diagnosis and Navigation, pp. 38–46, Springer, 2018.
  * [10] Z. Lin, S. Li, D. Ni, Y. Liao, H. Wen, J. Du, S. Chen, T. Wang, and B. Lei, “Multi-task learning for quality assessment of fetal head ultrasound images,” Medical image analysis, vol. 58, p. 101548, 2019.
  * [11] K. Raza and N. K. Singh, “A tour of unsupervised deep learning for medical image analysis,” Current Medical Imaging, vol. 17, no. 9, pp. 1059–1077, 2021.
  * [12] S. Zhang, Y. Wang, J. Jiang, J. Dong, W. Yi, and W. Hou, “Cnn-based medical ultrasound image quality assessment,” Complexity, vol. 2021, 2021.
  * [13] G. Wang, C. Jiang, Z. Shen, Y. Miao, and H. Wang, “Sfgan: Unsupervised generative adversarial learning of 3d scene flow from the 3d scene self,” Advanced Intelligent Systems, vol. 4, no. 4, p. 2100197, 2022.
  * [14] S. Zhou, H. Xu, Z. Zheng, J. Chen, J. Bu, J. Wu, X. Wang, W. Zhu, M. Ester, et al., “A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions,” arXiv preprint arXiv:2206.07579, 2022\.
  * [15] J. Xu, “A review of self-supervised learning methods in the field of medical image analysis,” Int. J. Image Graph. Signal Process.(IJIGSP), vol. 13, pp. 33–46, 2021.
  * [16] R. Wei and A. Mahmood, “Recent advances in variational autoencoders with representation learning for biomedical informatics: A survey,” Ieee Access, vol. 9, pp. 4939–4956, 2020.
  * [17] K. Nesovic, R. G. Koh, A. A. Sereshki, F. S. Zadeh, M. R. Popovic, and D. Kumbhare, “Ultrasound image quality evaluation using a structural similarity based autoencoder,” in 2021 43rd Annual International Conference of the IEEE Engineering in Medicine & Biology Society (EMBC), pp. 4002–4005, IEEE, 2021.
  * [18] M. Verma, M. Srivastava, N. Chack, A. K. Diswar, and N. Gupta, “A comparative study of various clustering algorithms in data mining,” International Journal of Engineering Research and Applications (IJERA), vol. 2, no. 3, pp. 1379–1384, 2012.
  * [19] H. Xu, J. He, Q. He, D. Zeng, G. Guan, B. Leng, and W. Zheng, “A spectral clustering method combining path with density,” in 2012 IEEE International Conference on Robotics and Biomimetics (ROBIO), pp. 695–698, IEEE, 2012.
  * [20] L. Van der Maaten and G. Hinton, “Visualizing data using t-sne.,” Journal of machine learning research, vol. 9, no. 11, 2008.
  * [21] B. Ghojogh, A. Ghodsi, F. Karray, and M. Crowley, “Uniform manifold approximation and projection (umap) and its variants: Tutorial and survey,” arXiv preprint arXiv:2109.02508, 2021.
  * [22] C. Song, F. Liu, Y. Huang, L. Wang, and T. Tan, “Auto-encoder based data clustering,” in Iberoamerican congress on pattern recognition, pp. 117–124, Springer, 2013.
  * [23] V. Prasad, D. Das, and B. Bhowmick, “Variational clustering: Leveraging variational autoencoders for image clustering,” in 2020 international joint conference on neural networks (IJCNN), pp. 1–10, IEEE, 2020.
  * [24] F. Soleymani, M. Eslami, T. Elze, B. Bischl, and M. Rezaei, “Deep variational clustering framework for self-labeling of large-scale medical images,” arXiv preprint arXiv:2109.10777, 2021.
  * [25] G. Maicas, C. Nguyen, F. Motlagh, J. C. Nascimento, and G. Carneiro, “Unsupervised task design to meta-train medical image classifiers,” in 2020 IEEE 17th International Symposium on Biomedical Imaging (ISBI), pp. 1339–1342, IEEE, 2020.
  * [26] T. Moriya, H. R. Roth, S. Nakamura, H. Oda, K. Nagara, M. Oda, and K. Mori, “Unsupervised segmentation of 3d medical images based on clustering and deep representation learning,” in Medical Imaging 2018: Biomedical Applications in Molecular, Structural, and Functional Imaging, vol. 10578, pp. 483–489, SPIE, 2018.
  * [27] R. Yu, Y. Tian, J. Gao, Z. Liu, X. Wei, H. Jiang, Y. Huang, and X. Li, “Feature discretization-based deep clustering for thyroid ultrasound image feature extraction,” Computers in Biology and Medicine, p. 105600, 2022\.
  * [28] V. Prasad, D. Das, and B. Bhowmick, “Variational clustering: Leveraging variational autoencoders for image clustering,” in 2020 International Joint Conference on Neural Networks (IJCNN), pp. 1–10, 2020.
  * [29] X. Lin, X. Yang, and Y. Li, “A deep clustering algorithm based on gaussian mixture model,” Journal of Physics: Conference Series, vol. 1302, p. 032012, aug 2019.
  * [30] J. Blanco-Portals, F. Peiró, and S. Estradé, “Strategies for eels data analysis. introducing umap and hdbscan for dimensionality reduction and clustering,” Microscopy and Microanalysis, vol. 28, no. 1, pp. 109–122, 2022.
  * [31] D. Raina, H. Singh, S. K. Saha, C. Arora, A. Agarwal, C. SH, K. Rangarajan, and S. Nandi, “Comprehensive telerobotic ultrasound system for abdominal imaging: Development and in-vivo feasibility study,” in 2021 International Symposium on Medical Robotics (ISMR), pp. 1–7, Nov 2021.
  * [32] S. H. Chandrashekhara, K. Rangarajan, A. Agrawal, S. Thulkar, S. Gamanagatti, D. Raina, S. K. Saha, and C. Arora, “Robotic ultrasound: An initial feasibility study,” World Journal of Methodology, vol. 12, no. 4, pp. 274–284, 2022.
  * [33] Z. Hussain, F. Gimenez, D. Yi, and D. Rubin, “Differential data augmentation techniques for medical imaging classification tasks,” in AMIA annual symposium proceedings, vol. 2017, p. 979, American Medical Informatics Association, 2017.
  * [34] M. Nadeem, A. Hussain, and A. Munir, “Fuzzy logic based computational model for speckle noise removal in ultrasound images,” Multimedia Tools and Applications, vol. 78, no. 13, pp. 18531–18548, 2019.
  * [35] S. Anand, R. S. S. Kumari, T. Thivya, and S. Jeeva, “Sharpening enhancement of ultrasound images using contourlet transform,” Optik, vol. 124, no. 21, pp. 4789–4792, 2013.
  * [36] S. Duan, L. Liu, Y. Chen, L. Yang, Y. Zhang, S. Wang, L. Hao, and L. Zhang, “A 5g-powered robot-assisted teleultrasound diagnostic system in an intensive care unit,” Critical Care, vol. 25, no. 1, pp. 1–9, 2021.
  * [37] T. K. Koo and M. Y. Li, “A guideline of selecting and reporting intraclass correlation coefficients for reliability research,” Journal of chiropractic medicine, vol. 15, no. 2, pp. 155–163, 2016.
  * [38] Y. Song, Z. Zhong, B. Zhao, P. Zhang, Q. Wang, Z. Wang, L. Yao, F. Lv, and Y. Hu, “Medical ultrasound image quality assessment for autonomous robotic screening,” IEEE Robotics and Automation Letters, vol. 7, no. 3, pp. 6290–6296, 2022.
  * [39] H. B. Zhou and J. T. Gao, “Automatic method for determining cluster number based on silhouette coefficient,” in Advanced materials research, vol. 951, pp. 227–230, Trans Tech Publ, 2014.
  * [40] N. X. Vinh, J. Epps, and J. Bailey, “Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance,” The Journal of Machine Learning Research, vol. 11, pp. 2837–2854, 2010.
  * [41] L. Deng, “The mnist database of handwritten digit images for machine learning research,” IEEE Signal Processing Magazine, vol. 29, no. 6, pp. 141–142, 2012.


# CLCIFAR: CIFAR-Derived Benchmark Datasets with Human-Annotated Complementary
Labels

Hsiu-Hsuan Wang, Wei-I Lin††footnotemark: , Hsuan-Tien Lin
National Taiwan University
{b09902033, r10922076<EMAIL_ADDRESS>The first two authors share
equal contributions.

###### Abstract

Complementary-label learning (CLL) is a weakly-supervised learning paradigm
that aims to train a multi-class classifier using only complementary labels,
which indicate classes to which an instance does not belong. Despite numerous
algorithmic proposals for CLL, their practical performance remains unclear for
two reasons. Firstly, these algorithms often rely on assumptions about the
generation of complementary labels. Secondly, their evaluation has been
limited to synthetic datasets. To gain insights into the real-world
performance of CLL algorithms, we developed a protocol to collect
complementary labels annotated by human annotators. This effort resulted in
the creation of two datasets, CLCIFAR10 and CLCIFAR20, derived from CIFAR10
and CIFAR100, respectively. These datasets, publicly released at
https://github.com/ntucllab/complementary_cifar, represent the very first
real-world CLL datasets. Through extensive benchmark experiments, we
discovered a notable decline in performance when transitioning from synthetic
datasets to real-world datasets. We conducted a dataset-level ablation study
to investigate the key factors contributing to this decline. Our analyses
highlighted annotation noise as the most influential factor present in the
real-world datasets. Additionally, the biased nature of human-annotated
complementary labels was found to make certain CLL algorithms more susceptible
to overfitting. These findings suggest the community to spend more research
effort on developing CLL algorithms that are robust to noisy and biased
complementary-label distributions.

##  1 Introduction

Ordinary multi-class classification methods rely heavily on high-quality
labels to train effective classifiers. However, such labels can be expensive
and time-consuming to collect in many real-world applications. To address this
challenge, researchers have turned their attention towards weakly-supervised
learning, which aims to learn from incomplete, inexact, or inaccurate data
sources [16, 12]. This learning paradigm includes but is not limited to noisy-
label learning [5], partial-label learning [2], positive-unlabeled learning
[3], and complementary-label learning [7]. In this work, we focus on
complementary-label learning (CLL). This learning problem involves training a
multi-class classifier using only complementary labels, which indicate the
classes that a data instance does not belong to. Although several algorithms
have been proposed to learn from complementary labels, they were only
benchmarked on synthetic datasets with some idealistic assumptions on
complementary-label generation [7, 8, 1, 13, 11]. Thus, it remains unclear
whether these algorithms perform well in practical scenarios. To uncover the
true performance of existing CLL algorithms, we collected human-annotated
complementary datasets and conducted benchmarking experiments of the
algorithms on those datasets.

Many proponents of studying CLL often highlight the potential on reducing
annotation costs by collecting complementary labels instead of ordinary
labels. The argument roots from the fact that any multi-class instance is
associated with more complementary labels than the one ordinal label.
Nevertheless, the complementary labels contain less information than ordinary
labels, and hence more complementary labels may be needed to achieve the same
level of testing performance. It remains unclear whether in practice the
learning algorithms can produce a meaningful classifier when the label
information is not only very weak but potentially noisy. On the other hand, to
make CLL possible, additional assumptions are made in the generation process
of complementary labels. The pioneering study by Ishida et al. [7] proposed
the _uniform assumption_ , which specifies that the complementary labels in
the dataset are generated by uniform sampling from the set of all possible
complementary labels. This assumption was utilized by some subsequent works to
generate the synthetic complementary datasets to benchmark their CLL
algorithms [8, 1, 11, 13]. To alleviate the restrictiveness of the uniform
assumption, Yu et al. [15] considered a more general _class-conditional
assumption_. This assumption specifies that the distribution of the
complementary labels only depends on its ordinary labels. Although these
assumptions simplify the design and analysis of CLL algorithms, it remains
unknown whether these assumptions hold true in practice and whether violation
of these assumptions will affect the performance of those algorithms.

To answer the problems mentioned above and contribute to the community, we
devised a label collection protocol that allows the annotators to choose a
complementary label for the images in CIFAR10 and CIFAR100. Two complementary
datasets, CLCIFAR10 and CLCIFAR20, based on the images in CIFAR10 and
CIFAR100, respectively, were collected. We then investigated the collected
complementary labels in detail, including the noise rate of the collected
labels and the biasedness of the empirical transition matrix. Finally, we
performed benchmark experiments with several SOTA CLL algorithms on the
collected datasets.

We summarize our contributions as follows:

  * •

We collected and released a real-world complementary dataset based on CIFAR10
and a modified CIFAR20 with super-classes category provided by Wei et al.
[14].

  * •

The analysis on the collected datasets reveal that two widely-used
assumptions, noise-free and uniformity, in the generation of complementary
labels are not true in the real world.

  * •

Extensive benchmark on the collected datasets reveals that the label noise
harms the performance of the previous methods and that the biasedness of the
collected complementary labels (CLs) leads to overfitting.

##  2 Preliminaries on CLL

In this section, we first formalize the problem of complementary-label
learning. Then, we introduce some assumptions that are widely used to design,
analyze, or benchmark the previous CLL algorithms. Finally, we briefly review
how the previous methods approached CLL.

###  2.1 Complementary-label learning

In traditional multi-class classification, a dataset
$D=\left\\{(\mathbf{x}_{i},y_{i})\right\\}^{n}_{i=1}$ that is i.i.d. sampled
from an unknown distribution is given to the learning algorithm. For each $i$,
$\mathbf{x}_{i}\in\mathbb{R}^{N}$ represents the $N$-dimension feature of the
$i$th instance and $y_{i}\in[K]=\left\\{1,2,\dots,K\right\\}$ represents the
class $\mathbf{x}_{i}$ belongs to. The goal of the learning algorithm is to
learn a classifier from $D$ that can predict the labels of unseen instances
correctly. The classifier is typically parametrized by a scoring function
$\mathbf{g}:\mathbb{R}^{N}\to\mathbb{R}^{K}$, and the prediction is made by
taking the argmax of its output, i.e., it predicts
$\arg\max_{k\in[K]}\mathbf{g}(\mathbf{x})_{k}$ given an instance $x$, where
$\mathbf{g}(\mathbf{x})_{k}$ denotes the $k$th output of
$\mathbf{g}(\mathbf{x})$.

In contrast to ordinary-label learning, complementary-label learning (CLL)
shares the same goal of training a classifier but learns from a different
label set. In CLL, the ordinary label $y_{i}$ is not accessible to the
learning algorithm. Instead, a complementary label $\bar{y}_{i}$ is provided,
which is a class that the instance $\mathbf{x}_{i}$ does not belong to. The
goal of CLL is to learn a classifier that is able to predict the correct label
of unseen instances from a complementary dataset
$\bar{D}=\left\\{(\mathbf{x}_{i},\bar{y}_{i})\right\\}_{i=1}^{n}$.

###  2.2 Common assumptions on CLL

To make the problem of CLL more structured, researchers make some additional
assumptions on the generation process of complementary labels. One common
assumption is the _class-conditional assumption_. It assumes that the
distribution of a complementary label only depends on its ordinary label and
is independent of the underlying example’s feature, i.e.,
$P(\bar{y}_{i}\mid\mathbf{x}_{i},y_{i})=P(\bar{y}_{i}\mid y_{i})$ for each
$i$. One special case of the class-conditional assumption is the _uniform
assumption_ , which further specifies that the complementary labels are
generated uniformly. In a $K$-class classification problem, it implies that
$P(\bar{y}_{i}=y^{\prime})=\frac{1}{K-1}$ for all
$y^{\prime}\in[K]\backslash\\{y_{i}\\}$.

For convenience, a $K\times K$ matrix $T$, called _transition matrix_ , is
often used to represent how the complementary labels are generated with the
class-conditional assumption. Here, $T_{i,j}$ is defined to be the probability
of obtaining a complementary label $j$ if the underlying ordinary label is
$i$, i.e., $P(\bar{y}=j\mid y=i)$ for each $i,j\in[K]$. For instance, in a
noiseless scenario, the transition matrix $T_{u}$ for the uniform assumptions
is as follows:

$T_{u}=\begin{bmatrix}0&\frac{1}{K-1}&\dots&\frac{1}{K-1}\\\
\frac{1}{K-1}&0&\dots&\frac{1}{K-1}\\\ \vdots&\vdots&\ddots&\vdots\\\
\frac{1}{K-1}&\frac{1}{K-1}&\dots&0\end{bmatrix}$

Any transition matrix that is not uniform is called _biased_. In CLL, the
diagonal of the transition matrix indicates how noisy the complementary labels
are. If all the complementary labels are correct, then all the diagonal
elements of the transition matrix are zero.

###  2.3 Previous methods on CLL

The pioneering work by Ishida et al. [7] studied how to learn from
complementary labels under the uniform assumption. Unfortunately, the unbiased
risk estimator proposed by Ishida et al. [7] tends to overfit. Several
subsequent researches [8, 1, 6, 11, 13] utilized different ways to mitigate
the overfitting issues. The usefulness of these methods, however, is
restricted by the fact that they either rely on the uniform assumption or are
only tested on the uniformly-generated complementary datasets. To make a step
towards practical CLL, a line of researches investigated how to learn beyond
noise-free uniform assumption. Yu et al. [15] used the forward-correction loss
to accommodate the case of biased complementary label generation, Ishiguro et
al. [9] proposed robust loss functions to address the noisy case, and Lin and
Lin [10] proposed a probability estimates framework with a decoder that is
compatible with a biased transition matrix and robust to noisy complementary
labels. On the other hand, Feng et al. [4] investigated how to learn with
multiple complementary labels per instance. Although these works potentially
make CLL more practical, it remains unknown how to learn without the class-
conditional assumption to the best of our knowledge.

Besides a learning algorithm, a crucial component in the practical machine
learning is the model validation. In ordinary-label learning, this can be done
by naively calculating the classification accuracy on a validation dataset. In
CLL, this process is impossible due to a lack of ordinary labels. One generic
way of model validation is based on the result of Ishida et al. [8] by
calculating the unbiased risk estimator of the zero-one loss, i.e.,

$\hat{R}_{01}(\mathbf{g})=\frac{1}{N}\sum_{i=1}^{N}e^{T}_{\overline{y}_{i}}(T^{-1})\ell_{01}(\mathbf{g}(x_{i}))$
(1)

where $e_{\overline{y}_{i}}$ denotes the one-hot vector of $\overline{y}_{i}$,
$\ell_{01}(\mathbf{g}(x_{i}))$ denotes the $K$-dimensional vector
$\left(\ell_{01}(\mathbf{g}(x_{i}),1),\dotsc,\ell_{01}(\mathbf{g}(x_{i})),K)\right)^{T}$,
and $\ell_{01}(\mathbf{g}(x_{i}),k)=0$ if
$\arg\max_{k\in[K]}\mathbf{g}(x_{i})=k$ and $1$ otherwise, representing the
zero-one loss of $\mathbf{g}(x_{i})$ if the ordinary label is $k$. This
estimator will be used in the experiments in Section 5.5. Another validation
objective, surrogate complementary esimation loss (SCEL), was proposed by Lin
and Lin [10]. SCEL measures the log loss of the complementary probability
estimates induced by the probability estimates on the ordinary label space.
The formula to calculate SCEL is as follows,

$\hat{R}_{\text{SCEL}}(\mathbf{g})=\frac{1}{N}\sum_{i=1}^{N}-\log\left(e^{T}_{\overline{y}_{i}}T^{T}\operatorname{softmax}(\mathbf{g}(x_{i}))\right).$
(2)

##  3 CLCIFAR, humanly-annotated complementary datasets

In this section, we introduce two complementary datasets for benchmarking CLL
algorithms, CLCIFAR10 and CLCIFAR20. Both datasets are labeled by human
annotators on Amazon Mechanical Turk (MTurk)111https://www.mturk.com/.

###  3.1 Dataset selection

We base our complementary datasets on CIFAR10 and CIFAR100. This selection is
motivated by the real-world noisy label dataset by Wei et al. [14]. Building
upon the CIFAR datasets allow us to evaluate the noise rate and the empirical
transition matrix easily, as they already contain nearly noise-free ordinary
labels. Besides, most of the SOTA CLL algorithms already perform benchmark on
the CIFAR datasets, albeit using synthetic labels. This allows us to benchmark
those methods without putting much efforts on selecting network architecture
or tuning the training hyperparameters. Finally, CIFAR datasets are
sufficiently hard in two aspects. For CLL algorithms, they are demonstrated to
be learnable at least in a noise-free and uniform scenario, while they are
still struggling to perform well on larger datasets such as ImageNet. For
humans, the image labeling tasks are also hard enough to argue that annotating
complementary labels are easier than the ordinary labels. In contrast, it is
hard to believe that correctly annotating the digits in MNIST is challenging
for humans. These observation makes us to base our complementary datasets on
the CIFAR dataset.

###  3.2 Complementary label collection protocol

To collect only complementary labels from the CIFAR dataset, for each image in
the training split, we first randomly sample four distinct labels and ask the
human annotators to select any of the _incorrect_ one from them. To analyze
the annotators’ behavior and reduce the noise in the collected labels, each
image is labeled by three different annotators. The four labels are re-sampled
for each annotator on each image. That is, each annotator possibly receives a
different set of four labels to choose from. Note that if the annotators
always select one of the correct complementary labels randomly, the empirical
transition matrix will be uniform in expectation. We will inspect the
empirical transition matrix in Section 4.

The labeling tasks are deployed on MTurk. We first divide the 50,000 images
into five batches of 10,000 images. Then, each batch is further divided into
1,000 human intelligence tasks (HITs) with each HIT containing 10 images. Each
HIT is deployed to three annotators, who receive 0.03 dollar as the reward by
annotating 10 images. To make the labeling task easier and increase clarity,
the size of the images are enlarged to $200\times 200$ pixels. For each super-
class in CIFAR20, four to six example images from the classes within the
super-class are provided to the annotators for reference.

##  4 Result analysis

Next, we take a closer look at the collected complementary labels. We first
analyze the error rates of the collected labels, and then verify whether the
transition matrix is uniform or not. Finally, we end with an analysis on the
behavior of the human annotators observed in the label collection protocol.

Figure 1:  The label distribution of CLCIFAR10 (left) and CLCIFAR20 (right).

#### Observation 1: noise rate compared to ordinary label collection

We first look at the noise rate of the collected complementary labels. A
complementary label is considered to be incorrect if it is actually the
ordinary label. The mean error rate made by the human annotators is 3.93% for
CLCIFAR10 and 2.80% for CLCIFAR20. Although it is not a fair comparison due to
the different protocols, we compare to the noise rate of the CIFAR-N dataset
[14] for reference. The noise rate on CIFAR10-N and CIFAR100N-coarse are
around 18% and 25.60%, respectively. This difference suggests that the
collected complementary labels could be less noisy than the ordinary ones. On
the other hand, if we compare the human annotators to a random annotator who
always annotates the label randomly, the results become different. A random
annotator achieves a noise rate of $\frac{1}{K}$ for complementary label
annotation and a noise rate of $\frac{K-1}{K}$ for ordinary label annotation.
If we compare the human annotators to a random annotator, then for CLCIFAR10,
human annotators have $60.7$% less noisy labels than the random annotator
whereas for CIFAR10-N, human anotators have $80$% less noisy labels. This
demonstrates that human annotators are more competent compared to a random
annotator in the ordinary-label annotation. Similarly, human annotators have
$44$% less noise than a random annotator for CLCIFAR20 and $73.05$% less noise
for CIFAR100N-coarse. This observation reveals that while the absolute noise
rate is lower in annotating complementary labels, it may be more difficult to
be competent against random labels than the ordinary label annotation.

#### Observation 2: imbalanced complementary label annotation

Next, we analyze the distribution of the collected complementary labels. The
frequency of the complementary labels for the CLCIFAR datasets are reported in
Figure 1. As we can see in the figure, the annotators have specific bias on
certain labels. For instance, the annotators have a preference for “airplane”
and “automobile” in CLCIFAR10 and a preference for “people” and “flower” in
CLCIFAR20. In CLCIFAR10, the annotations are biased towards the labels with
longer names whereas in CLCIFAR20, they are biased towards the labels with
shorter, more concrete and understandable names.

(a) CLCIFAR10

(b) CLCIFAR20

Figure 2: The empirical transition matrices of CLCIFAR10 and CLCIFAR20. The
label names of CLCIFAR20 are abbreviated as indexes to save space. The full
label names are provided in Appendix D.

#### Observation 3: biased transition matrix

Finally, we visualize the empirical transition matrix using the collected
complementary labels in Figure 2. Based on the first two observations, we
could imagine that the transition matrix is biased. By inspecting Figure 2, we
further discover that the bias in the complementary labels are dependent on
the true labels. For instance, in CLCIFAR10, despite we see more annotations
on airplane and automobile in aggregate, conditioning on the transportation-
related labels (“airplane”, “automobile”, “ship” and “truck”), the
distribution of the complementary labels becomes more biased towards other
animal-related labels (“bird”, “cat”, etc.) Next, we study the impact of the
bias and noise on existing CLL algorithms.

##  5 Experiments

In this section, we benchmarked several SOTA CLL algorithms on CLCIFAR10 and
CLCIFAR20. A significant performance gap between the models trained on the
humanly annotated CLCIFAR dataset and those trained on the synthetically
generated complementary labels (CL) was observed in Section 5.1, which
motivates us to analyze the possible reasons for the gap with the following
experiments. To do so, we discuss the effect of three factors in the label
generating process, feature dependency, noise, and biasedness, in Section 5.2,
Section 5.3, and Section 5.4, respectively. From our experiment results, we
conclude that noise is the dominant factor affecting the performance of the
CLL algorithms on CLCIFAR. Another crucial component in applying CLL
algorithms in practice is validation. We also discuss the empirical
performance of the existing validation approaches in Section 5.5.

###  5.1 Standard benchmark on CLCIFAR10, CLCIFAR20

#### Baseline methods

Several SOTA CLL algorithms were selected for this benchmark. Some of them
take the transition matrix $T$ as inputs, which we call $T$-informed methods,
including

  * •

Two versions of forward correction method [15]: FWD-U and FWD-T. They utilize
a uniform transition matrix $T_{u}$ and an empirical transition matrix $T_{e}$
as input, respectively.

  * •

Two versions of unbiased risk estimator with gradient ascent [8]: URE-GA-U
with a uniform transition matrix $T_{u}$ and URE-GA-T with an empirical
transition matrix $T_{e}$.

  * •

Robust loss methods [9] for learning from noisy CL, including CCE, MAE, WMAE,
GCE, and SL222Due to space limitations, we only provided the results of MAE.
The remaining results and discussions related to the robust loss methods can
be found in Appendix A.3.. We applied the gradient ascent technique [8] as
recommended in the original paper.

In practice, the empirical transition matrix $T_{e}$ is not accessible to the
learning algorithm, but we assume that the correct $T_{e}$ is given to FWD-T,
URE-GA-T and the robust loss methods for simplicity.

We also included some algorithms that assume the transition matrix $T$ to be
uniform, which we call $T$-agnostic methods, including

  * •

Surrogate complementary loss [1] with the negative log loss (SCL-NL) and with
the exponential loss (SCL-EXP),

  * •

Discriminative modeling [6] (L-W) and its weighted variant (L-UW), and

  * •

Pairwise-comparison (PC) with the sigmoid loss [7].

#### Implementation details

In this standard benchmark, for each data instance, we first randomly drew one
CL from the the collected CLs to form a single CLL dataset. Then, we trained a
ResNet-18 model using the baseline methods mentioned above on the single CLL
dataset using the Adam optimizer for 300 epochs without learning rate
scheduling. We left the benchmarks with multiple CLs in Appendix A.1. The
weight decay was fixed at $10^{-4}$ and the batch size was set to 512. The
experiments were run with NVIDIA V100 or RTX 2070. For better generalization,
we applied standard data augmentation technique, RandomHorizontalFlip,
RandomCrop, and normalization to each image. The learning rate was selected
from $\\{10^{-3}$, $5\times 10^{-4}$, $10^{-4}$, $5\times 10^{-5}$,
$10^{-5}\\}$ using a 10% hold-out validation set. We selected the learning
rate with the best classification accuracy on the validation dataset. Note
that here we assumed the ground-truth labels in the validation dataset are
known. We will discuss other validation objectives that rely only on
complementary labels in Section 5.5. As CLL algorithms are prone to
overfitting [8, 1], some previous works did not use the model after training
for evaluation. Instead, early-stopping was performed by evaluating the model
on the validation dataset and selecting the epoch with the highest validation
accuracy. For completeness, we considered both settings, and used “(ES)” to
indicate that the aforementioned early-stopping technique is employed. For
reference, we also performed the experiments on synthetically-generated CLL
dataset, where the CLs were generated uniformly and noiselessly, denoted
uniform-CIFAR.

#### Results and discussion

As we can observe in Table 1, there is a significant performance gap between
the humanly annotated dataset, CLCIFAR, and the synthetically generated
dataset, uniform-CIFAR. The difference between the two datasets can be divided
into three parts: (a) whether the generation of complementary labels depends
on the feature, (b) whether there is noise, and (c) whether the complementary
labels are generated with bias. A negative answer to those questions simplify
the problem of CLL. We can gradually simplify CLCIFAR to uniform-CIFAR by
chaining those assumptions as follows 333The “interpolation” between CLCIFAR
and uniform-CIFAR does not necessarily have to be this way. For instance, one
can remove the biasedness before removing the noise. We chose this order to
reflect the advance of CLL algorithms. First, researchers address the uniform
case [7], then generalize to the biased case [15], then consider noisy labels
[9]. There is no work considering feature-dependent complementary labels yet.:

$\boxed{\text{CLCIFAR}}\;\xRightarrow[\text{Remove feature
dependency}]{\text{Section~{}\ref{sec:exp-feat}}}\;\;\xRightarrow[\text{Remove
noise}]{\text{Section~{}\ref{sec:exp-noise}}}\;\;\xRightarrow[\text{Remove
biasedness}]{\text{Section~{}\ref{sec:exp-bias}}}\;\boxed{\text{uniform-
CIFAR}}$

In the following subsections, we will analyze how these three factors affect
the performance of the CLL algorithms.

Table 1: Standard benchmark results on CLCIFAR and uniform-CIFAR datasets.
Mean accuracy ($\pm$ standard deviation) on the testing dataset from four
trials with different random seeds. Highest accuracy in each column is
highlighted in bold.

| uniform-CIFAR10 | CLCIFAR10 | uniform-CIFAR20 | CLCIFAR20
---|---|---|---|---
methods | valid_acc | valid_acc (ES) | valid_acc | valid_acc (ES) | valid_acc | valid_acc (ES) | valid_acc | valid_acc (ES)
FWD-U | 69.17$\pm$1.22 | 69.79$\pm$1.01 |  34.09$\pm$1.16 |  36.83$\pm$1.17 | 20.24$\pm$0.52 |  20.62$\pm$0.49 |  7.47$\pm$0.37 |  8.27$\pm$0.77
FWD-R | - | - |  28.88$\pm$0.65 | 38.9$\pm$1.57 | - | - | 16.14$\pm$1.11 | 20.31$\pm$0.25
URE-GA-U |  54.62$\pm$0.6 |  54.94$\pm$1.34 | 34.59$\pm$0.76 |  36.39$\pm$0.67 |  15.41$\pm$0.97 |  16.59$\pm$0.61 |  7.59$\pm$0.36 |  10.06$\pm$0.72
URE-GA-R | - | - |  28.7$\pm$1.39 |  30.94$\pm$1.66 | - | - |  5.24$\pm$0.2 |  5.46$\pm$0.28
SCL-NL |  67.15$\pm$1.9 |  68.64$\pm$1.98 |  33.8$\pm$0.52 |  37.81$\pm$2.12 |  20.04$\pm$0.48 |  20.68$\pm$0.46 |  7.58$\pm$0.66 |  8.53$\pm$0.29
SCL-EXP |  64.86$\pm$0.44 |  65.4$\pm$0.32 |  34.59$\pm$0.72 |  36.96$\pm$0.18 |  19.4$\pm$0.76 | 21.03$\pm$0.64 |  7.55$\pm$0.51 |  8.11$\pm$0.71
L-W |  56.21$\pm$0.54 |  59.18$\pm$0.46 |  28.04$\pm$0.38 |  34.55$\pm$2.05 |  14.35$\pm$0.74 |  19.11$\pm$1.29 |  7.08$\pm$1.1 |  8.74$\pm$0.42
L-UW |  60.88$\pm$0.77 |  62.43$\pm$0.46 |  30.63$\pm$1.87 |  35.13$\pm$1.56 |  16.01$\pm$0.89 |  19.42$\pm$0.42 |  7.36$\pm$0.33 |  8.71$\pm$0.31
PC-sigmoid |  28.20$\pm$0.58 |  39.29$\pm$0.87 |  24.38$\pm$2.18 |  35.88$\pm$0.98 |  9.72$\pm$0.49 |  16.45$\pm$0.64 |  9.27$\pm$0.37 |  14.26$\pm$1.04
MAE |  57.37$\pm$0.48 |  58.50$\pm$0.97 |  16.30$\pm$2.27 |  19.44$\pm$4.41 |  16.72$\pm$1.52 |  17.63$\pm$1.63 |  5.11$\pm$0.11 |  5.87$\pm$0.26

###  5.2 Feature dependency

In this experiment, we verified whether the performance gap resulted from the
feature-dependent generation of practical CLs. Conceivably, even if two images
belong to the same class, the distribution on the complementary labels could
be different. On the other hand, the distributional difference could also be
too small to affect model performance, e.g., if $P(\bar{Y}\mid Y,X)\approx
P(\bar{Y}\mid Y)$ for most $X$. Consequently, we decided to further look into
whether this assumption can explain the performance gap. To observe the
effects of approximating $P(\bar{Y}\mid Y,X)$ with $P(\bar{Y}\mid Y)$, we
generated two synthetic complementary datasets, CLCIFAR10-iid and
CLCIFAR20-iid by i.i.d. sampling CLs from the empirical transition matrix in
CLCIFAR10 and CLCIFAR20, respectively. We proceeded to benchmark the CLL
algorithms on CLCIFAR-iid and presented the accuracy difference compared to
CLCIFAR in Table 2.

#### Results and discussion

From Table 2, we observed that the accuracy barely changes on the resampled
CLCIFAR-iid, suggesting that even if the complementary labels in CLCIFAR could
be feature-dependent, this dependency does not affect the model performance
significantly. Hence, there might be other factors contributing to the
performance gap.

Table 2: Mean accuracy difference ($\pm$ standard deviation) of different CLL
algorithms. A plus indicates the performance on is calculated as
CLCIFAR-i.i.d. accuracy minus CLCIFAR accuracy.

| FWD-U | FWD-R | URE-GA-U | URE-GA-R | SCL-NL | SCL-EXP | L-W | L-UW | PC-sigmoid
---|---|---|---|---|---|---|---|---|---
CLCIFAR10-iid |  -1.1$\pm$2.17 |  -0.36$\pm$1.15 |  -3.03$\pm$1.25 |  0.74$\pm$0.35 |  -0.67$\pm$1.81 |  -1.97$\pm$1.16 |  -2.5$\pm$0.56 |  -3.53$\pm$1.36 |  -2.03$\pm$2.05
CLCIFAR20-iid |  -0.64$\pm$0.39 |  -3.53$\pm$1.13 |  -0.37$\pm$0.51 |  1.79$\pm$2.34 |  -0.28$\pm$0.61 |  -0.39$\pm$0.69 |  -0.5$\pm$1.37 |  -0.82$\pm$0.04 |  -2.24$\pm$0.52

###  5.3 Labeling noise

In this experiment, we further investigated the impact of the label noise on
the performance gap. Specifically, we measured the accuracy on the noise-
removed versions of CLCIFAR datasets, where varying percentages (0%, 25%, 50%,
75%, or 100%) of noisy labels are eliminated.

#### Results and discussion

We present the performance of FWD trained on thenoise-removed CLCIFAR10
dataset in the left figure in Figure 3. The results for other algorithms and
the noise-removed CLCIFAR20 dataset can be found in Appendix C. From the
figure, we observe a strong positive correlation between the performance and
the proportion of removed noisy labels. When more noisy labels are removed,
the performance gap diminishes and the accuracy approaches that of the ideal
uniform-CLFAR dataset. Therefore, we conclude that the performance gap between
the humanly annotated CLs and the synthetically generated CLs are primarily
attributed to the label noise.

###  5.4 Biasedness of complementary labels

To further study the biasedness of CL as a potential factor contributing to
the performance gap, we removed the biasedness from the noise-removed CLCIFAR
dataset and examined the resulting accuracy. Specifically, we introduced the
same level of uniform noise in uniform-CIFAR dataset and reevaluated the
performance of FWD algorithms.

#### Results and discussion

The striking similarity between the two curves in the right figure in Figure 3
shows that the accuracy is significantly influenced by label noise, while the
biasedness of CL has a negligible impact on the results. Furthermore, we
observe that the accuracy difference between the results of the last epoch and
the early-stopping results becomes smaller when the model is trained on the
uniformly generated CLs. That is, the $T$-informed methods are more prone to
overfitting when there is a bias in the CL generation.

With the experiment results in Section 5.2, 5.3, and 5.4, we can conclude that
the performance gap between humanly annotated CL and synthetically generated
CL is primarily attributed to label noise. Additionally, the biasedness of CLs
may potentially contribute to overfitting, while the feature-dependent CLs do
not detrimentally affect performance empirically. It is worth noting that in
the last row of Table 1, the MAE methods that can learn from noisy CL fails to
generalize well in the practical dataset. These results suggest that more
research on learning with noisy complementary labels can potentially make CLL
more realistic.

Figure 3: Accuracy of FWD-U and FWD-R on the noise-removed CLCIFAR10 dataset
(Left) and the uniform-CIFAR10 dataset with uniform noise (Right) at varying
noise rates.

###  5.5 Validation objectives

Validating the model performance solely with CL poses a non-trivial challenge.
To offer an empirical analysis from the perspective of practical datasets, we
evaluated the models using a purely complementary validation set and employed
two validation objectives, including unbiased risk estimator (URE) [8] and
surrogate complementary estimation loss (SCEL) [10]. We used these two
validation objectives to select the optimal learning rate from $\\{10^{-3}$,
$5\times 10^{-4}$, $10^{-4}$, $5\times 10^{-5}$, $10^{-5}\\}$ and provides the
accuracy on testing set in Table 3. For completeness, we also provide the
accuracy of models selected using a validation set that contains an equal
number of true labels.

#### Results and discussion

Based on our results, we do not observe a deterministic trend in the accuracy
between the models selected by URE or SCEL. To further visualize the
difference between a pure complementary validation set and a ordinary
validation set, we calculated the accuracy difference between the model
selected using the ordinary validation set and the best models selected from
either URE or SCEL. The results were reported in the gap column in Table 3.
For some algorithms and datasets, a non-negligible gap was observed. Whether
this gap could be further reduced remains open. Deeper understanding on the
validation of CLL can potentially help making CLL more practical.

Table 3: The testing accuracy of models evaluated with URE and SCEL.

| uniform-cifar10 | clcifar10 | uniform-cifar20 | clcifar20
---|---|---|---|---
| URE | SCEL | valid acc | gap ($\downarrow$) | URE | SCEL | valid acc | gap ($\downarrow$) | URE | SCEL | valid acc | gap ($\downarrow$) | URE | SCEL | valid acc | gap ($\downarrow$)
FWD-U | 22.36 | 45.63 | 48.44 | 2.81 | 32.54 | 33.02 | 34.09 | 1.07 | 16.02 | 16.02 | 17.4 | 1.38 | 7.33 | 7.33 | 7.47 | 0.14
FWD-R | - | - | - | - | 28.88 | 19.13 | 28.88 | 0 | - | - | - | - | 10.74 | 9.8 | 16.14 | 5.4
URE-GA-U | 39.24 | 39.24 | 39.55 | 0.31 | 31.34 | 34.59 | 34.59 | 0 | 13.12 | 12.64 | 13.52 | 0.4 | 7.28 | 7.85 | 7.59 | -0.26
URE-GA-R | - | - | - | - | 26.61 | 28.18 | 28.7 | 0.52 | - | - | - | - | 5.2 | 5.36 | 5.24 | -0.12
SCL-NL | 22.83 | 36.44 | 48.2 | 11.76 | 32.49 | 33.32 | 33.8 | 0.48 | 14.16 | 16.55 | 16.55 | 0 | 7.12 | 6.5 | 7.58 | 0.46
SCL-EXP | 22.72 | 22.72 | 46.79 | 24.07 | 33.15 | 31.26 | 34.59 | 1.44 | 14.23 | 14.16 | 16.18 | 1.95 | 6.85 | 6.53 | 7.55 | 0.7
L-W | 10.38 | 11.03 | 27.02 | 15.99 | 20.71 | 20.71 | 28.04 | 7.33 | 7.37 | 9.66 | 10.39 | 0.73 | 5.77 | 6.03 | 7.08 | 1.05
L-UW | 9.93 | 9.93 | 31.3 | 21.37 | 22.97 | 22.97 | 30.63 | 7.66 | 7.68 | 7.68 | 12.33 | 4.65 | 5.9 | 5.9 | 7.36 | 1.46
PC-sigmoid | 16.07 | 15.62 | 18.97 | 2.9 | 14.98 | 15.43 | 24.38 | 8.95 | 7.38 | 7.38 | 7.67 | 0.29 | 7.04 | 8.63 | 9.27 | 0.64

##  6 Conclusion

In this paper, we devised a protocol to collect complementary labels from
human annotators. Utilizing this protocol, we curated two real-world datasets,
CLCIFAR10 and CLCIFAR20, and made them publicly available to the research
community. Through our meticulous analysis of these datasets, we confirmed the
presence of noise and bias in the human-annotated complementary labels,
challenging some of the underlying assumptions of existing CLL algorithms.
Extensive benchmarking experiments revealed that noise is a critical factor
that undermines the effectiveness of most existing CLL algorithms.
Furthermore, the biased complementary labels can trigger overfitting, even for
algorithms explicitly designed to leverage this bias information. These
findings emphasize the need for the community to dedicate more effort to
developing CLL algorithms that are robust to both noise and bias. The curated
datasets pave the way for the community to create more practical and
applicable CLL solutions.

## References

  * Chou et al. [2020] Y.-T. Chou, G. Niu, H.-T. Lin, and M. Sugiyama.  Unbiased risk estimators can mislead: A case study of learning with complementary labels, 2020.
  * Cour et al. [2011] T. Cour, B. Sapp, and B. Taskar.  Learning from partial labels.  _The Journal of Machine Learning Research_ , 12:1501–1536, 2011.
  * Denis [1998] F. Denis.  Pac learning from positive statistical queries.  In _Algorithmic Learning Theory: 9th International Conference, ALT’98 Otzenhausen, Germany, October 8–10, 1998 Proceedings 9_ , pages 112–126. Springer, 1998.
  * Feng et al. [2020] L. Feng, T. Kaneko, B. Han, G. Niu, B. An, and M. Sugiyama.  Learning with multiple complementary labels.  In _International Conference on Machine Learning_ , pages 3072–3081. PMLR, 2020.
  * Frénay and Verleysen [2013] B. Frénay and M. Verleysen.  Classification in the presence of label noise: a survey.  _IEEE transactions on neural networks and learning systems_ , 25(5):845–869, 2013.
  * Gao and Zhang [2021] Y. Gao and M.-L. Zhang.  Discriminative complementary-label learning with weighted loss.  In _International Conference on Machine Learning_ , pages 3587–3597. PMLR, 2021.
  * Ishida et al. [2017] T. Ishida, G. Niu, W. Hu, and M. Sugiyama.  Learning from complementary labels.  _Advances in neural information processing systems_ , 30, 2017.
  * Ishida et al. [2019] T. Ishida, G. Niu, A. K. Menon, and M. Sugiyama.  Complementary-label learning for arbitrary losses and models, 2019.
  * Ishiguro et al. [2022] H. Ishiguro, T. Ishida, and M. Sugiyama.  Learning from noisy complementary labels with robust loss functions.  _IEICE TRANSACTIONS on Information and Systems_ , 105(2):364–376, 2022.
  * Lin and Lin [2023] W.-I. Lin and H.-T. Lin.  Reduction from complementary-label learning to probability estimates.  In _Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD)_ , May 2023.
  * Liu et al. [2023] S. Liu, Y. Cao, Q. Zhang, L. Feng, and B. An.  Consistent complementary-label learning via order-preserving losses.  In _International Conference on Artificial Intelligence and Statistics_ , pages 8734–8748. PMLR, 2023.
  * Sugiyama et al. [2022] M. Sugiyama, H. Bao, T. Ishida, N. Lu, T. Sakai, and G. Niu.  _Machine learning from weak supervision: An empirical risk minimization approach_.  MIT Press, 2022.
  * Wang et al. [2021] D.-B. Wang, L. Feng, and M.-L. Zhang.  Learning from complementary labels via partial-output consistency regularization.  In _IJCAI_ , pages 3075–3081, 2021.
  * Wei et al. [2022] J. Wei, Z. Zhu, H. Cheng, T. Liu, G. Niu, and Y. Liu.  Learning with noisy labels revisited: A study using real-world human annotations, 2022.
  * Yu et al. [2018] X. Yu, T. Liu, M. Gong, and D. Tao.  Learning with biased complementary labels, 2018.
  * Zhou [2018] Z.-H. Zhou.  A brief introduction to weakly supervised learning.  _National science review_ , 5(1):44–53, 2018\.

## Appendix

##  Appendix A More discussion on practical noise

Our work found out that the labeling noise is the main factor contributing to
the performance gap between synthetic CL and practical CL. Hence, we conducted
deeper investigation into some directions to handle the practical noise. In
Section A.1, we discussed the performance improvement when more human-
annotated complementary labels were available. In Section A.2, we designed the
synthetic CLCIFAR-N dataset to study the difference between synthetic uniform
noise and practical noise. In Section A.3, we provided the benchmark results
of all robust loss methods to emphasize the essence of studying a practical
complementary label dataset.

###  A.1 Multiple complementary labels

In this experiment, we studied the case when there were multiple CLs for a
data instance. We duplicated the data instance and assigned them with another
practical label from the annotators. The results of this experiment were
summarized in Table 4.

For CLCIFAR10, we observe that the model achieved better learning performance
when trained on data instances with more CLs. However, the issue of
overfitting persists even with the increased number of labels. In the case of
CLCIFAR20, we found that without employing early stopping techniques, it is
challenging to achieve improved results as the number of labels increased.
Furthermore, the overfitting problem becomes more pronounced with the
increased number of labels. Overall, these findings shed light on the
challenges posed by multiple CLs and the persistence of overfitting.

Table 4: Learning with Multiple CL: The figure shows the classification
accuracy of each task with early stopping indicated in brackets. The highest
accuracy in each column is bolded for ease of comparison.

| CLCIFAR10 | CLCIFAR20
---|---|---
num CL | 1 | 2 | 3 | 1 | 2 | 3
FWD-U |  34.09(36.83) |  41.95(41.53) |  42.88(45.18) |  7.47(8.27) |  8.28(8.78) |  8.15(10.27)
FWD-R |  28.88(38.9) |  34.33(47.07) |  37.84(49.76) |  16.14(20.31) |  16.99(23.41) |  15.54(24.19)
URE-GA-U |  34.59(36.39) |  45.71(44.85) |  45.97(47.97) |  7.59(10.06) |  8.42(11.52) |  8.53(12.75)
URE-GA-R |  28.7(30.94) |  42.73(43.34) |  44.73(47.36) |  5.24(5.46) |  6.77(6.92) |  5.0(5.55)
SCL-NL |  33.8(37.81) |  40.67(42.58) |  43.39(45.2) |  7.58(8.53) |  6.77(6.92) |  5.0(5.55)
SCL-EXP |  34.59(36.96) |  40.89(42.99) |  44.4(47.9) |  7.55(8.11) |  7.42(8.39) |  8.0(9.31)
L-W |  28.04(34.55) |  34.96(41.83) |  39.05(47.46) |  7.08(8.74) |  8.06(8.76) |  8.03(10.18)
L-UW |  30.63(35.13) |  38.05(43.32) |  39.49(45.82) |  7.36(8.71) |  7.03(8.55) |  7.86(10.11)
PC-sigmoid |  24.38(35.88) |  25.63(39.82) |  33.89(43.75) |  9.27(14.26) |  11.91(16.07) |  17.68(14.13)

###  A.2 Benchmarks with synthetic noise

#### Generation process of CLCIFAR-N

Inspired by the conclusions drawn in Section 5.3, we investigated another
avenue of research: the generalization capabilities of methods when
transitioning from synthetic datasets with uniform noise to practical
datasets. To obtain a general synthetic dataset with minimum assumption, we
introduced CLCIFAR-N. This synthetic dataset contains unifrom CL and uniform
real world noise from CLCIFAR dataset. The complementary labels of CLCIFAR-N
are i.i.d. sampled from $T_{syn}$, where the diagonal entries are set to be
$3.93\%/10$ (for generating CL for CIFAR10) or $2.8\%/20$ (for generating CL
for CIFAR20). The non-diagonal entries are uniformly distributed. This
construction allows us to generate a synthetic dataset that mimics real-world
scenarios more closely with minimum knowledge.

#### Benchmark results

We ran the benchmark experiments with the identical settings as in Section 5.1
and present the results in Table 5. The performance difference between
sythetic noise and practical noise are illustrated in the _diff_ columns. A
smaller difference indicates a better generalization capability of the models.
Interestingly, the robust loss methods exhibit superiority on the synthetic
CLCIFAR10-N dataset but struggle to generalize well on real-world datasets.
This finding suggests the existence of fundamental differences between
synthetic noise and practical noise. Further investigation into these
differences is left as an avenue for future research.

Table 5: Benchmark results on CLCIFAR-N datasets. The classification accuracy
difference is calculated by subtracting the practical CLCIFAR dataset from the
performance on the synthetic CLCIFAR-N dataset.

| CLCIFAR10-N | diff($\downarrow$) | CLCIFAR20-N | diff($\downarrow$)
---|---|---|---|---
FWD-U | 37.1 | 2.2 | 7.58 | 0.11
FWD-R | - | - | - | -
URE-GA-U | 31.29 | -3.3 | 8.1 | 0.5
URE-GA-R | - | - | - | -
SCL-NL | 37.79 | 2.06 | 7.75 | 0.16
SCL-EXP | 35.86 | 3.19 | 6.95 | -0.59
L-W | 30.1 | 2.06 | 6.16 | -0.91
L-UW | 32.69 | 2.05 | 6.89 | -0.47
PC-sigmoid | 19.64 | -4.73 | 6.54 | -2.72
CCE | 32.34 | 13.45 | 5.71 | 0.71
MAE | 41.34 | 23.09 | 6.83 | 1.83
WMAE | 37.62 | 22.26 | 6.36 | 1.08
GCE | 35.00 | 18.71 | 6.7 | 1.7
SL | 29.98 | 12.29 | 6.08 | 1.05

###  A.3 Results of the robust loss methods

The original design of the robust loss aims to obtain the optimal risk
minimizer even in the presence of corrupted labels. However, their methods do
not generalized well on practical datasets. The results are provided in Table
6. In other words, solely considering synthetic noisy CLs does not guarantee
performance on real-world datasets. These results once again underscore the
importance of the CLCIFAR dataset.

Table 6: Standard benchmark results on CLCIFAR and uniform-CIFAR datasets for
the robust loss method. Mean accuracy ($\pm$ standard deviation) on the
testing dataset from four trials with different random seeds. Highest accuracy
in each column is highlighted in bold.

| uniform-CIFAR10 | CLCIFAR10 | uniform-CIFAR20 | CLCIFAR20
---|---|---|---|---
methods | valid_acc | valid_acc (ES) | valid_acc | valid_acc (ES) | valid_acc | valid_acc (ES) | valid_acc | valid_acc (ES)
CCE |  46.57$\pm$1.75 |  49.51$\pm$0.73 |  16.18$\pm$2.97 |  20.18$\pm$3.39 |  12.54$\pm$0.40 |  14.62$\pm$1.29 |  5.07$\pm$0.05 |  5.41$\pm$0.30
MAE |  57.37$\pm$0.48 |  58.50$\pm$0.97 |  16.30$\pm$2.27 |  19.44$\pm$4.41 |  16.72$\pm$1.52 |  17.63$\pm$1.63 |  5.11$\pm$0.11 |  5.87$\pm$0.26
WMAE | - | - |  13.01$\pm$1.89 |  15.51$\pm$0.75 | - | - |  5.31$\pm$0.27 |  6.65$\pm$0.65
GCE |  58.10$\pm$1.54 |  59.44$\pm$2.30 |  14.31$\pm$1.44 |  18.97$\pm$2.16 |  15.86$\pm$1.93 |  17.09$\pm$1.19 |  5.21$\pm$0.29 |  5.76$\pm$0.32
SL |  41.13$\pm$1.64 |  42.64$\pm$0.11 |  16.45$\pm$2.80 |  19.28$\pm$3.16 |  13.60$\pm$0.55 |  15.70$\pm$1.23 |  5.44$\pm$0.29 |  6.59$\pm$0.43

##  Appendix B More discussion on biasedness

In addition to the label noise, the biasedness of CL in practical dataset
would lead to overfitting, especially for those T-informed algorithms. We
conducted deeper investigation into this phenomenon. In Section B.1, we
demonstrated the necessity of employing data augmentation techniques to
prevent overfitting. In Section B.2, we attempted to address the issue of
overfitting by employing an interpolated transition matrix for regularization.

###  B.1 Ablation on data augmentation

To further investigate the significance of data augmentation, we conducted
identical experiments without employing data augmentation during the training
phase. As we can observe in the training curves in Figure 4, data augmentation
could improve the testing accuracy of all the algorithms we considered.

We also provide the results without the use of data augmentation techniques in
Table 7, and we observed that almost all methods suffered from overfitting. It
is worth noting that URE with gradient ascent suffers less compared to the
other methods. The reason might be that reversing the gradient of the class
with negative loss (the overfitting class) can be seen as a regularization
technique. Therefore, URE with GA methods can be more resistant to overfitting
in practical datasets.

Figure 4: The Overfitting accuracy curve of FWD, URE, SCL-NL, L-W. The dotted
line represents the accuracy obtained without data augmentation, while the
solid line represents the accuracy with data augmentation included for
reference. The accuracy of FWD, SCL-NL, SCL-EXP, L-W, L-UW methods reaches its
highest at approximately the 50 epoches and converges to some lower point. The
detail numbers are in appendix 7 Table 7: The overfitting results when there
is no data augmentation.

| uniform-CIFAR10 | CLCIFAR10 | uniform-CIFAR20 | CLCIFAR20
---|---|---|---|---
methods | valid_acc | valid_acc (ES) | valid_acc | valid_acc (ES) | valid_acc | valid_acc (ES) | valid_acc | valid_acc (ES)
FWD-U | 48.44 | 49.33 | 21.29 | 25.59 | 17.4 | 17.97 | 6.91 | 7.32
FWD-R | - | - | 14.97 | 28.3 | - | - | 6.82 | 14.67
URE-GA-U | 39.55 | 39.67 | 21.0 | 23.53 | 13.52 | 14.08 | 5.55 | 8.38
URE-GA-R | - | - | 19.81 | 20.8 | - | - | 5.0 | 6.43
SCL-NL | 48.2 | 48.27 | 21.96 | 26.51 | 16.55 | 17.54 | 7.1 | 7.92
SCL-EXP | 46.79 | 47.52 | 21.89 | 27.66 | 16.18 | 17.89 | 6.9 | 7.3
L-W | 27.02 | 44.78 | 20.06 | 27.6 | 10.39 | 16.3 | 5.64 | 8.02
L-UW | 31.3 | 46.38 | 20.28 | 26.26 | 12.33 | 16.32 | 6.03 | 8.14
PC-sigmoid | 18.97 | 33.26 | - | - | 7.67 | 10.41 | - | -

###  B.2 Ablation on interpolation between $T_{u}$ and $T_{e}$

In Table 1, we discovered that the $T$-informed methods did not always deliver
better testing accuracy when $T_{e}$ is given. Looking at the difference
between the accuracy of using early-stopping and not using early-stopping, we
observe that when the $T_{u}$ is given to the $T$-informed methods, the
difference becomes smaller. This suggests that $T$-informed methods using the
empirical transition matrix has greater tendency to overfitting. On the other
hand, $T$-informed methods using the uniform transition matrix could be a more
robust choice.

We observe that the uniform transition matrix $T_{u}$ acts like a
regularization choice when the algorithms overfit on CLCIFAR. This results
motivate us to study whether we can interpolate between $T_{u}$ and $T_{e}$ to
let the algorithms utilize the information of transition matrix while
preventing overfitting. To do so, we provide an interpolated transition matrix
$T_{\text{int}}=\alpha T_{u}+(1-\alpha)T_{e}$ to the algorithm, where $\alpha$
controls the scale of the interpolation. As FWD is the $T$-informed method
with the most sever overfitting when using $T_{u}$, we performed this
experiment using FWD adn reported the results in Figure 5. As shown in Figure
5, FWD can learn better from an interpolated $T_{\text{int}}$, confirming the
conjecture that $T_{u}$ can serve as a regularization role.

Figure 5: The last epoch accuracy of CLCIFAR10 and CLCIFAR20 for FWD algorithm
with an $\alpha$-interpolated transition matrix $T_{\text{int}}$. The five
solid points on each cruve represent different noise cleaning rate: 0%, 25%,
50%, 75%, 100% from left to right.

##  Appendix C Additional charts for CLCIFAR dataset with data cleaning

We remove 0%, 25%, 50%, 75%, 100% of the noisy data in CLCIFAR10 and CLCIFAR20
datasets. We discover that by removing the noisy data in the practical
dataset, the practical performance gaps vanish for all the CLL algorithms.
Therefore, we can conclude that the main obstacle to the practicality of CLL
is label noise.

(a) FWD-(U/R) on CLCIFAR10

(b) FWD-(U/R) on CLCIFAR20

(a) URE-GA-(U/R) on CLCIFAR10

(b) URE-GA-(U/R) on CLCIFAR20

(a) SCL-(NL/EXP) on CLCIFAR10

(b) SCL-(NL/EXP) on CLCIFAR20

(a) L-(W/UW) on CLCIFAR10

(b) L-(W/UW) on CLCIFAR20

(a) PC-sigmoid on CLCIFAR10

(b) PC-sigmoid on CLCIFAR20

##  Appendix D Label names of CLCIFAR20

Index | Full Label Name
---|---
0 | aquatic mammals
1 | fish
2 | flowers
3 | food containers
4 | fruit, vegetables and mushrooms
5 | household electrical devices
6 | household furniture
7 | insects
8 | large carnivores and bear
9 | large man-made outdoor things
10 | large natural outdoor scenes
11 | large omnivores and herbivores
12 | medium-sized mammals
13 | non-insect invertebrates
14 | people
15 | reptiles
16 | small mammals
17 | trees
18 | transportation vehicles
19 | non-transportation vehicles

##  Appendix E Broader impacts

The datasets may advance the alorithms for learning from complementary labels.
Those algorithms could learn a classifier with weak information. The privacy
of the users may be easier to compromised as a result. We suggest the
practitioners pay attention to the privacy issues when trying to utilize the
collected datasets and the CLL algorithms.

##  Appendix F Access to the dataset and codes for reproduce

Please refer to the following link:
https://github.com/ntucllab/complementary_cifar