# Block-Diagonal Guided DBSCAN Clustering

Weibing Zhao

###### Abstract

Cluster analysis plays a crucial role in database mining, and one of the most
widely used algorithms in this field is DBSCAN. However, DBSCAN has several
limitations, such as difficulty in handling high-dimensional large-scale data,
sensitivity to input parameters, and lack of robustness in producing
clustering results. This paper introduces an improved version of DBSCAN that
leverages the block-diagonal property of the similarity graph to guide the
clustering procedure of DBSCAN. The key idea is to construct a graph that
measures the similarity between high-dimensional large-scale data points and
has the potential to be transformed into a block-diagonal form through an
unknown permutation, followed by a cluster-ordering procedure to generate the
desired permutation. The clustering structure can be easily determined by
identifying the diagonal blocks in the permuted graph. Thus, the main
challenge is to construct a graph with a potential block-diagonal form,
permute the graph to achieve a block-diagonal structure, and automatically
identify diagonal blocks in the permuted graph. To tackle these challenges, we
first formulate a block-diagonal constrained self-representation problem to
construct a similarity graph of high-dimensional points with a potential
block-diagonal form after an unknown permutation. We propose a gradient
descent-based method to solve the proposed problem. Additionally, we develop a
DBSCAN-based points traversal algorithm that identifies clusters with high
densities in the graph and generates an augmented ordering of clusters. The
block-diagonal structure of the graph is then achieved through permutation
based on the traversal order, providing a flexible foundation for both
automatic and interactive cluster analysis. We introduce a split-and-refine
algorithm to automatically search for all diagonal blocks in the permuted
graph with theoretically optimal guarantees under specific cases. We
extensively evaluate our proposed approach on twelve challenging real-world
benchmark clustering datasets and demonstrate its superior performance
compared to the state-of-the-art clustering method on every dataset.

###### Index Terms:

Cluster analysis, DBSCAN, block-diagonal property, self-representation, graph
permutation, diagonal block identification.

##  1 Introduction

Larger and larger amounts of data are being collected and stored in databases,
which increases the need for efficient and effective analysis methods to
implicitly utilize the information in the data [1]. One of the primary tasks
in data analysis is cluster analysis, which aims to help users understand the
natural grouping or structure in a dataset. The unsupervised nature of
clustering algorithms makes them widely applicable across diverse domains,
including data analysis, computer vision, and image processing [2, 3]. Despite
numerous clustering algorithms proposed from various perspectives, it remains
challenging to develop an algorithm that can accurately discover clusters from
the spatial distribution of data, especially when the number, densities,
orientations, and shapes of the underlying clusters are unknown [4].

Traditional clustering algorithms can be categorized into four main types,
including partition-based, hierarchical, graph-based, and density-based
methods [4]. $\bullet$ The widely used K-means [5] algorithm and its
extensions fall under the partition-based category, suitable for finding
convex-shaped clusters and relatively easy to implement. However, determining
the cluster number $K$ and initializing the clustering assignment to converge
towards a better local optimal solution are always challenging. $\bullet$
Hierarchical clustering algorithms [6, 7] create a cluster hierarchy by
merging clusters based on proximity and interconnectivity, which is effective
in discovering clusters with diverse shapes and densities. These methods
iteratively merge clusters until the minimum dissimilarity between clusters
reaches a certain threshold. However, this method requires the specification
of parameters such as the distance metric, linking approach, and number of
clusters, which can be challenging to determine accurately. Moreover, once
undesired grouping occurs during the merging process, they cannot be corrected
in the subsequent clustering steps, leading to inaccurate clustering results.
$\bullet$ Graph-based approaches [8] aim to identify dense regions in the
graph by maximizing intra-cluster similarity or minimizing inter-cluster
similarity. One approach involves identifying the tree structure of the graph,
such as the minimum spanning tree [9], which may result in less robust
clustering as it prunes the graph to the simplest form, making it susceptible
to inaccurate connection caused by noise. Another approach involves solving an
optimization problem, such as spectral clustering [10] and its extensions,
e.g., [11], which addresses the graph-cut problem through spectral relaxation.
However, spectral clustering involves approximation, which can lead to
potential performance degradation, and it relies on K-means clustering, which
has limitations of its own. $\bullet$ Density-based clustering algorithms have
proven successful in discovering clusters of both convex and non-convex
shapes. Prominent examples include the widely used Density-Based Spatial
Clustering of Applications with Noise (DBSCAN) algorithm [12] and its
variants, such as Hierarchical DBSCAN [13] and ST-DBSCAN [14]. Despite the
fact that many recently developed extensions of DBSCAN have demonstrated
relatively good clustering performance, they still suffer from several
deficiencies, such as difficulty in handling high-dimensional large-scale
data, sensitivity to input parameters, and lack of robustness in producing
clustering results.

Figure 1: The framework of the proposed BD-DBSCAN clustering method, including
graph construction, permutation, and segmentation. The input is 60 images from
Extended Yale-B [15] dataset. The output is the pictorial representation of
the cluster assignations for the 60 images. Faces with the same color belong
to the same cluster.

  * •

We present an enhanced version of DBSCAN utilizing a block-diagonal property
of the similarity graph which comprises three key stages: graph construction,
graph permutation, and graph segmentation. The block-diagonal characteristics
is utilized not only to guide the graph construction procedure but also to
guide the procedure of identification of the clustering structure. We propose
three problems for these three stages and develop efficient algorithms to
solve them.

  * •

The proposed clustering method possesses several advantages: (i) it is not
sensitive to input parameters, (ii) it can discover clusters with different
densities, (iii) it can identify both convex and non-convex shaped clusters,
(iv) it allows for visualization of the clustering procedure, (v) it is robust
to identify the clustering structure, and (vi) it can handle high-dimensional
large-scale datasets with low computational complexity.

  * •

We extensively evaluate our method on real-world benchmark clustering datasets
from the literature and compare it with recently developed clustering methods.
Our method consistently achieves the highest clustering accuracy,
demonstrating the superiority of our proposed approach over state-of-the-art
clustering methods.

The remainder of the paper is structured as follows. In Sec. 2, we introduce
the related works of our paper, encompassing DBSCAN clustering and block-
diagonal guided clustering methods. In Sec. LABEL:Sec:method, we introduce our
proposed techniques for graph construction, permutation, and segmentation. The
experimental results are presented in Sec. LABEL:Experiments, and the paper is
concluded in Sec. 3. For clarity, the notations adopted throughout the paper
are summarized in Tab. I.

TABLE I: Important notations used throughout the paper

Notation | Description
---|---
$K$ | The number of clusters
$D$ | The dimension of data
$N$ | The number of data points
$\mathbf{X}\in\mathbb{R}^{D\times N}$ | Data matrix
$\mathbf{x}_{i}\in\mathbb{R}^{D}$ | Data point
$\mathcal{S}_{k}$ | The $k$-th subspace
$\mathbf{Z}\in\mathbb{R}^{N\times N}$ | The self-representation coefficient of $\mathbf{X}$
$z_{i,j}$ | The $(i,j)$-th element of $\mathbf{Z}$
$\mathbf{Y}\in\mathbb{R}^{D\times N}$ | The noise matrix
$\tilde{\mathbf{X}}_{k}\in\mathbb{R}^{D\times N_{k}}$ | Data matrix belonging to the $k$-th cluster
$\tilde{\mathbf{Z}}^{*}\in\mathbb{R}^{N\times N}$ | The block-diagonal matrix from permuting $\mathbf{Z}$
$\bm{\Gamma}\in\mathbb{R}^{N\times N}$ | The permuting matrix
$\tilde{\mathbf{Z}}_{k}^{*}\in\mathbb{R}^{N_{k}\times N_{k}}$ | The self-representation coefficient of $\tilde{\mathbf{X}}_{k}$
$\mathbf{E}\in\mathbb{R}^{N\times N}$ | The all-ones matrix
$\mathcal{Z}$ | The feasible set of $\mathbf{Z}$
$\mathcal{P}_{\mathcal{Z}}$ | The projection operator
$\rho_{m}$ | The spectral step length
$\gamma_{m}$ | The gradient
$\alpha_{m}$ | The step length
$\varepsilon$ | The convergence tolerance
$C_{1,1}$, $C_{1,2}$, $C_{2}$ | The clusters
$\epsilon$, $\epsilon_{1}$, $\epsilon_{2}$ | The radius of neighborhood
$\delta$ | Minimum number of points in neighborhood
$\mathbf{W}$ | The similarity matrix
$w_{i,j}$ | The $(i,j)$-th element of $\mathbf{W}$
$c_{i}$ | Similarity between $i$th sample and its $\delta$th neighbor
$Q$ | The queue
$t_{i}$ | The true partition indexes
$\tau_{m}$ | The estimated partition indexes
$\mathcal{C}_{k}$ | The assignment set of the $k$-th cluster

##  2 Related Work

###  2.1 DBSCAN Clustering

Let us give a brief outline of the DBSCAN firstly. Suppose we have an
undirected graph $\mathcal{G}=(\mathcal{V},\mathbf{W})$, where $\mathcal{V}$
is the point set, and the element $w_{p,q}\geq 0$ in $\mathbf{W}$ saves the
edge weight (similarity) between point $p$ and point $q$. The greater the
weight, the closer the distance between two points. DBSCAN starts by pruning
the graph to a weighted $\epsilon$-Nearest-Neighbor Graph ($\epsilon$-NNG),
where $\epsilon$ is the radius of neighborhood. An edge $w_{p,q}$ between two
vertexes $p,q$ in graph $\mathcal{G}$ is set to be zero if $w_{p,q}<\epsilon$.
Denote $\mathcal{N}_{\epsilon}(p)$ as the $\epsilon$-radius neighborhood of
point $p$, i.e.,
$\mathcal{N}_{\epsilon}(p)=\\{q\in\mathcal{V}:w_{p,q}\geq\epsilon\\}$. DBSCAN
constructs its MST (minimal spanning tree) and then finds the connected
components in the MST [20]. These components are the desired clustering.

The detail of DBSCAN [12] to search clusters is shown below. DBSCAN [12]
detects high-density spatial regions and expands them to form clusters. It has
two hyper-parameters: the radius of neighborhood $\epsilon$ and the minimum
number of points $\delta$ (also found as minPts in the literature). Using
these parameters points are classified into three different types in
Definition 1 based on density, i.e., core points, border points and noise
points.

######  Definition 1 (classification of points).

Given $\epsilon$ and $\delta$, DBSCAN classifies points $\mathcal{V}$ into
three types:

  * •

core points:
$\mathcal{V}_{\mathrm{core}}=\\{p\in\mathcal{V}:|\mathcal{N}_{\epsilon}(p)|\geq\delta\\}$.

  * •

border points:
$\mathcal{V}_{\mathrm{border}}=\\{p\in\mathcal{V}-\mathcal{V}_{\mathrm{core}}:\quad\exists\,q\in\mathcal{V}_{\mathrm{core}},\quad
s.t.\quad p\in\mathcal{N}_{\epsilon}(q)\\}$.

  * •

noise points:
$\mathcal{V}_{\mathrm{noise}}=\mathcal{V}-\mathcal{V}_{\mathrm{core}}-\mathcal{V}_{\mathrm{border}}$.

DBSCAN uses three pairwise-point relations, which we give below in Definitions
2, 3 and 4.

######  Definition 2 (direct $\epsilon$-reachable).

A point $q$ is directly $\epsilon$-reachable from a point $p$ if
$p\in\mathcal{V}_{\mathrm{core}}$, and $q\in\mathcal{N}_{\epsilon}(p)$, which
is denoted by $p\overset{\epsilon}{\rightarrow}q$.

######  Definition 3 ($\epsilon$-reachable).

A point $q$ is $\epsilon$-reachable from a point $p$ if
$p\in\mathcal{V}_{\mathrm{core}}$ and
$\exists\,p_{1},p_{2},...,p_{n}\in\mathcal{V}_{\mathrm{core}}$, s.t.
$p\overset{\epsilon}{\rightarrow}p_{1}$,
$p_{1}\overset{\epsilon}{\rightarrow}p_{2}$, …,
$p_{n}\overset{\epsilon}{\rightarrow}q$ ,which is denoted by
$p\overset{\epsilon}{\rightharpoonup}q$.

######  Definition 4 ($\epsilon$-connected).

A point $p$ is $\epsilon$-connected with $q$ if
$\exists\,o\in\mathcal{V}_{\mathrm{core}}$, s.t.
$o\overset{\epsilon}{\rightharpoonup}p$ and
$o\overset{\epsilon}{\rightharpoonup}q$, which is denoted by
$p\overset{\epsilon}{\longleftrightarrow}q$.

Using these definitions, a density-based cluster in DBSCAN given by Definition
5.

######  Definition 5 (cluster of DBSCAN).

A DBSCAN cluster $\mathcal{C}$ is a nonempty subset of points in $\mathcal{V}$
satisfying that:
(i) $\forall\,p,q\in\mathcal{V}$: if $p\in\mathcal{C}$ and
$p\overset{\epsilon}{\rightharpoonup}q$, then $q\in\mathcal{C}$. (Maximality)
(ii) $\forall\,p,q\in\mathcal{C}$:
$p\overset{\epsilon}{\longleftrightarrow}q$. (Connectivity)

Figure 2: Key definitions in DBSCAN. (a): the hyper-parameters that control
the algorithm are $\epsilon$ and $\delta=3$ in this example. A core point is
red, a border point is green dot, and a noise point blue. Point $q$ is
directly $\epsilon$-reachable from $p$ since $q\in\mathcal{N}_{\epsilon}(p)$;
For points $q$ and $r$, it is easy to see that they are both directly
$\epsilon$-reachable from each other; (b): $p$ is $\epsilon$-reachable from
$q$; (c): $p$ and $q$ are $\epsilon$-connected.

Fig. 2 illustrates the basic concepts of DBSCAN. Fig. 2 (a) illustrates the
definitions on a database of 2-dimensional points from a metric space, and the
exponential negative distance measure is set to be the edge weight. For core
points, the relation of $\epsilon$-reachable is equivalent to the relation of
$\epsilon$-connected, and this relation is an equivalence relation, i.e., it’s
symmetric, transitive and reflexive. By Definition 5, the DBSCAN clusters
restricted to core points are equivalence classes defined by the relation of
$\epsilon$-reachable. Thus, a core point belongs to a unique cluster. By the
connectivity in Definition 5 (ii), a border point could belong to any cluster
that contains core point in the $\epsilon$-radius neighborhood of border
point. A noise point belongs to no cluster. Therefore, from the implementation
point of view, DBSCAN is interested in clustering core points. Fig. 2 (b) and
(c) illustrate $\epsilon$-reachable and $\epsilon$-connected in Definition 3
and 4.

The main _shortcomings_ of DBSCAN are that [21]:

  * •

Constructing a graph for high-dimensional large-scale data is expensive.
Moreover, the distance metrics ( e.g., Euclidean, Chebyshev, Cosine, etc) are
only exploited to describe local relationships in data space, and have
limitation to represent the relationship of high-dimensional data.

  * •

The structure of $\epsilon$-NNG becomes increasingly sensitive to the
parameter $\epsilon$ with increasing dimension: small perturbations in
$\epsilon$ can turn a very sparse graph into a very dense one. Additionally,
$\delta$ determines the partition of points into core, border, and noise
points, and slight changes in $\epsilon$ can lead to different
$\epsilon$-connected results. Moreover, if the density of different clusters
is different, and $\epsilon$ and $\delta$ are not properly set, DBSCAN may
easily mis-classify low-density cluster points as noise, or mis-classify noise
as border or core points.

  * •

Finding connected components in $\epsilon$-NNG based on connectivity alone is
not robust to noisy datasets. There exists a case where all points in
$\epsilon$-NNG are connected by noise points, resulting in only one cluster
according to DBSCAN.

In [22], the author presents a theoretical analysis of the performance and
convergence of DBSCAN with increasing $N$, demonstrating the effectiveness of
DBSCAN in clustering. In [23], the authors propose SNG-DBSCAN, which runs in
$\mathcal{O}(N\log N)$ time to reduce complexity by sub-sampling the edges of
the neighborhood graph. In [24], the authors introduce PDBSCAN, which uses a
KD-tree to construct a more accurate $\epsilon$-NNG. The same group proposes
OPTICS, a DBSCAN-like clustering algorithm [20], which achieves similar
performance by separating the procedure of DBSCAN into two stages, reducing
sensitivity to input parameters. In [25], the authors introduce PARDICLE to
construct an approximate $\epsilon$-graph by estimating point density and
restricting exact neighborhood searches to a small number of points. This
approach is designed to use less memory and computation, as FLANN [26] does
not support distributed-memory parallelism. The authors in [27] address
problems with $d>3$ and propose an MPI-based implementation of the algorithm.
The work in [28] proposes a KNN-DBSCAN algorithm to symmetrize the k-NNG graph
by dropping all single-direction edges and then using exact
$\epsilon$-searches. The works [29, 30] are specifically designed for 2D/3D
datasets and provide guaranteed clustering performance.

Almost all of the studies exclusively concentrate on addressing specific
drawbacks of DBSCAN, resulting in only marginal improvements in clustering
performance compared to DBSCAN. Numerous experiments have shown that both
DBSCAN and its extensions exhibit poor performance when dealing with high-
dimensional large-scale datasets.

###  2.2 Block-Diagonal Guided Clustering

Numerous works leverage the block-diagonal properties of the similarity graph
to enhance clustering performance by similarity matrix optimization.
Subsequently, they depend on spectral clustering to identify the clustering
structure, utilizing the spectrum (eigenvalues) of the similarity matrix for
dimensionality reduction and applying K-means clustering in fewer dimensions.
However, these methods identify the clustering structure without fully
utilizing the block-diagonal property as guidance, potentially leading to
unsatisfactory clustering results. For instance, Feng et al. [31] propose a
graph Laplacian constraint-based formulation to construct an exactly block-
diagonal similarity matrix, making it the first attempt to explicitly pursue
such a structure. Wu et al. [32] integrate a block-diagonal prior into the
construction of a similarity matrix to improve clustering accuracy on
sequential data. Lee et al. [33] introduce the membership representation to
detect block-diagonal structures in the output of graph construction. Xie et
al. [34] propose an implicit block-diagonal low-rank representation model by
incorporating implicit feature representation and block-diagonal prior into
the prevalent low-rank representation method. Lu et al. [35] develop a general
formulation for constructing similarity graphs and provide a unified
theoretical guarantee of the block-diagonal property. Yang et al. [36] propose
a joint robust multiple kernel clustering method that encourages the
acquisition of an affinity matrix with optimal block-diagonal properties based
on a block-diagonal regularizer and the self-expressiveness property. Liu et
al. [37] propose a spectral-type clustering scheme that directly pursues the
block-diagonal structure of the similarity graph using a special K-block-
diagonal constraint. Wang et al. [38] introduce a non-convex regularizer to
constrain the affinity matrix and exploit the block-diagonal structure. Qin et
al. [39] propose a new semi-supervised clustering approach that flexibly
enforces the block-diagonal structure on the similarity matrix while
considering sparseness and smoothness simultaneously. Lin et al. [40] propose
an adaptive block-diagonal representation approach that explicitly pursues the
block-diagonal structure without sacrificing the convexity of the optimization
problem. Liu et al. [41] introduce an adaptive low-rank kernel block-diagonal
representation graph construction algorithm. They map the original input space
into a kernel Hilbert space that is linearly separable and then apply spectral
clustering in the feature space. Qin et al. [42] establish an explicit
theoretical connection between spectral clustering [43] and graph construction
with block-diagonal representation. Xu et al. [44] propose a novel approach
called projective block-diagonal representation, which rapidly pursues a
representation matrix with block-diagonal structure. Li et al. [45] present an
enforced block-diagonal graph learning method for multi-kernel clustering.
They pursue a high-quality block-diagonal graph using a well-designed one-part
graph learning scheme. Kong et al. [46] introduce block-diagonal
regularization to ensure that the obtained representation matrix involves a
$k$-block-diagonal, where $k$ denotes the number of clusters. Li et al. [47]
propose a method to construct a block-diagonal similarity matrix with ordered
partition points based on the $l_{2}$-norm. The block-diagonal research has
also been applied to multi-view clustering, as seen in works such as Yin et
al. [48], and Liu et al. [49]. Other matrix optimization-based methods include
[50, 51, 52, 53, 41, 45, 46].

Recently, neural network-based approaches have attracted more attention. For
instance, Xu et al. [54] proposed a novel latent block-diagonal representation
model for graph construction on nonlinear structures. Their approach jointly
learns an auto-encoder and a similarity matrix with a block-diagonal
structure. Liu et al. [49] integrated the block diagonal and diverse
representation into the network and proposed a multi-view subspace clustering
network with the block diagonal and diverse representation. Other neural
network-based works include [55, 56, 57].

While some methods aim to identify the block-diagonal structure in the
similarity matrix for clustering, they fail to incorporate block-diagonal
guidance when constructing the similarity graph. Consequently, the block-
diagonal structure of the similarity matrix itself remains unclear. This
difficulty in identifying the block-diagonal in the similarity graph often
leads to unsatisfactory clustering results. For instance, [58] proposed
generating block-diagonal forms to provide an intermediate clustering result,
facilitating exploration of machine groups and part families before specifying
structural criteria. [59] designed the diagonal block model to identify
representative block cluster structures from the similarity matrix. [60]
rearranged the binary (or 0-1) machine-part matrix into a compact block-
diagonal form combining the properties of the minimal spanning tree and cell
design analyses. [61] introduced a generative model for clustering,
identifying the block-diagonal structure of the similarity matrix to ensure
that samples within the same cluster (diagonal block) are similar, while
samples from different clusters (off-diagonal block) are less similar. [62]
proposed a novel method named multiple kernel k-means clustering with block-
diagonal property.

##  3 Conclusion

In this paper, we introduce a density-based clustering method called BD-
DBSCAN. Our approach involves constructing a similarity graph of the data
points that has the potential to exhibit a block-diagonal form after a certain
permutation. We then propose a cluster traversal algorithm to identify a
permutation that rearranges the graph into a block-diagonal form. Finally, we
present a split-and-refine algorithm to identify the diagonal blocks in the
permuted graph. The clustering results are determined based on the
identification of these diagonal blocks. The proposed BD-DBSCAN clustering
method offers a comprehensive set of advantages, consistently achieving the
highest clustering performance across various synthetic and real-world
benchmark datasets.

## References

  * [1] A. K. Jain, M. N. Murty, and P. J. Flynn, “Data clustering: a review,” _ACM computing surveys (CSUR)_ , vol. 31, no. 3, pp. 264–323, 1999.
  * [2] D. Xu and Y. Tian, “A comprehensive survey of clustering algorithms,” _Annals of Data Science_ , vol. 2, no. 2, pp. 165–193, 2015.
  * [3] Z. Xing and W. Zhao, “Unsupervised action segmentation via fast learning of semantically consistent actoms,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 38, no. 6, 2024, pp. 6270–6278.
  * [4] C. Fraley and A. E. Raftery, “How many clusters? which clustering method? answers via model-based cluster analysis,” _The computer journal_ , vol. 41, no. 8, pp. 578–588, 1998.
  * [5] J. MacQueen, “Classification and analysis of multivariate observations,” in _5th Berkeley Symp. Math. Statist. Probability_ , 1967, pp. 281–297.
  * [6] V. Menon, G. Muthukrishnan, and S. Kalyani, “Subspace clustering without knowing the number of clusters: A parameter free approach,” _IEEE Trans. Signal Process._ , vol. 68, pp. 5047–5062, 2020.
  * [7] Y. Zhang, S. Ding, L. Wang, Y. Wang, and L. Ding, “Chameleon algorithm based on mutual k-nearest neighbors,” _Applied Intelligence_ , vol. 51, no. 4, pp. 2031–2044, 2021.
  * [8] W. Sun and Q. Du, “Graph-regularized fast and robust principal component analysis for hyperspectral band selection,” _IEEE Transactions on Geoscience and Remote Sensing_ , vol. 56, no. 6, pp. 3185–3195, 2018.
  * [9] T. Qiu and Y.-J. Li, “Fast ldp-mst: An efficient density-peak-based clustering method for large-size datasets,” _IEEE Trans. Knowl. Data Eng._ , vol. 35, no. 5, pp. 4767–4780, 2022.
  * [10] U. Von Luxburg, “A tutorial on spectral clustering,” _Statistics and computing_ , vol. 17, no. 4, pp. 395–416, 2007.
  * [11] L. Bai, J. Liang, and Y. Zhao, “Self-constrained spectral clustering,” _IEEE Trans. Pattern Anal. Mach. Intell._ , 2022.
  * [12] M. Ester, H.-P. Kriegel, J. Sander, X. Xu _et al._ , “A density-based algorithm for discovering clusters in large spatial databases with noise.” in _kdd_ , vol. 96, no. 34, 1996, pp. 226–231.
  * [13] R. J. Campello, D. Moulavi, and J. Sander, “Density-based clustering based on hierarchical density estimates,” in _Pacific-Asia conference on knowledge discovery and data mining_ , 2013, pp. 160–172.
  * [14] D. Birant and A. Kut, “St-dbscan: An algorithm for clustering spatial–temporal data,” _Data & knowledge engineering_, vol. 60, no. 1, pp. 208–221, 2007.
  * [15] A. S. Georghiades, P. N. Belhumeur, and D. J. Kriegman, “From few to many: Illumination cone models for face recognition under variable lighting and pose,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 23, no. 6, pp. 643–660, 2001.
  * [16] T. Zhou, H. Fu, C. Gong, L. Shao, F. Porikli, H. Ling, and J. Shen, “Consistency and diversity induced human motion segmentation,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 45, no. 1, pp. 197–210, 2022.
  * [17] Y. Qin, X. Zhang, L. Shen, and G. Feng, “Maximum block energy guided robust subspace clustering,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 45, no. 2, 2022.
  * [18] Y. Bai, L. Wang, Y. Liu, Y. Yin, H. Di, and Y. Fu, “Human motion segmentation via velocity-sensitive dual-side auto-encoder,” _IEEE Trans. Image Process._ , vol. 32, pp. 524 – 536, 2022.
  * [19] X. Wang, D. Guo, and P. Cheng, “Support structure representation learning for sequential data clustering,” _Pattern Recognition_ , vol. 122, p. 108326, 2022.
  * [20] M. A. Patwary, D. Palsetia, A. Agrawal, W.-k. Liao, F. Manne, and A. Choudhary, “Scalable parallel optics data clustering using graph algorithmic techniques,” in _Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis_ , 2013, pp. 1–12.
  * [21] X. Yang, C. Deng, F. Zheng, J. Yan, and W. Liu, “Deep spectral clustering using dual autoencoder network,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2019, pp. 4066–4075.
  * [22] H. Jiang, “Density level set estimation on manifolds with DBSCAN,” in _International Conference on Machine Learning_ , 2017, pp. 1684–1693.
  * [23] H. Jiang and J. Jang, “Faster dbscan via subsampled similarity queries,” 2020\.
  * [24] M. M. A. Patwary, D. Palsetia, A. Agrawal, W.-k. Liao, F. Manne, and A. Choudhary, “A new scalable parallel DBSCAN algorithm using the disjoint-set data structure,” in _SC’12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis_ , 2012, pp. 1–11.
  * [25] M. M. A. Patwary, N. Satish, N. Sundaram, F. Manne, S. Habib, and P. Dubey, “Pardicle: Parallel approximate density-based clustering,” in _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_ , ser. SC ’14. Piscataway, NJ, USA: IEEE Press, 2014, pp. 560–571. [Online]. Available: http://dx.doi.org/10.1109/SC.2014.51
  * [26] M. Muja and D. G. Lowe, “Scalable nearest neighbor algorithms for high dimensional data,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 36, no. 11, pp. 2227–2240, 2014.
  * [27] A. Sarma, P. Goyal, S. Kumari, A. Wani, J. S. Challa, S. Islam, and N. Goyal, “$\mu$DBSCAN: An exact scalable DBSCAN algorithm for big data exploiting spatial locality,” in _2019 IEEE International Conference on Cluster Computing (CLUSTER)_. IEEE, 2019, pp. 1–11.
  * [28] A. Sharma and A. Sharma, “KNN-DBSCAN: Using k-nearest neighbor information for parameter-free density based clustering,” in _2017 International Conference on Intelligent Computing, Instrumentation and Control Technologies (ICICICT)_ , 2017, pp. 787–792.
  * [29] M. M. A. Patwary, S. Byna, N. R. Satish, N. Sundaram, Z. Lukić, V. Roytershteyn, M. J. Anderson, Y. Yao, Prabhat, and P. Dubey, “BD-CATS: Big data clustering at trillion particle scale,” in _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_ , ser. SC’ 15. New York, NY, USA: ACM, 2015, pp. 6:1–6:12. [Online]. Available: http://doi.acm.org/10.1145/2807591.2807616
  * [30] B. Welton, E. Samanas, and B. P. Miller, “Extreme scale density-based clustering using a tree-based network of gpgpu nodes,” in _SC’13: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis_ , 2013, pp. 1–11.
  * [31] J. Feng, Z. Lin, H. Xu, and S. Yan, “Robust subspace segmentation with block-diagonal prior,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2014, pp. 3818–3825.
  * [32] F. Wu, Y. Hu, J. Gao, Y. Sun, and B. Yin, “Ordered subspace clustering with block-diagonal priors,” _IEEE Trans. Cybern._ , vol. 46, no. 12, pp. 3209–3219, 2015.
  * [33] M. Lee, J. Lee, H. Lee, and N. Kwak, “Membership representation for detecting block-diagonal structure in low-rank or sparse subspace clustering,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 1648–1656.
  * [34] X. Xie, X. Guo, G. Liu, and J. Wang, “Implicit block diagonal low-rank representation,” _IEEE Trans. Image Process._ , vol. 27, no. 1, pp. 477–489, 2017.
  * [35] C. Lu, J. Feng, Z. Lin, T. Mei, and S. Yan, “Subspace clustering by block diagonal representation,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 41, no. 2, pp. 487–501, 2018.
  * [36] C. Yang, Z. Ren, Q. Sun, M. Wu, M. Yin, and Y. Sun, “Joint correntropy metric weighting and block diagonal regularizer for robust multiple kernel subspace clustering,” _Information Sciences_ , vol. 500, pp. 48–66, 2019.
  * [37] M. Liu, Y. Wang, J. Sun, and Z. Ji, “Structured block diagonal representation for subspace clustering,” _Applied Intelligence_ , vol. 50, pp. 2523–2536, 2020.
  * [38] L. Wang, J. Huang, M. Yin, R. Cai, and Z. Hao, “Block diagonal representation learning for robust subspace clustering,” _Information Sciences_ , vol. 526, pp. 54–67, 2020.
  * [39] Y. Qin, G. Feng, Y. Ren, and X. Zhang, “Block-diagonal guided symmetric nonnegative matrix factorization,” _IEEE Trans. Knowl. Data Eng._ , 2021\.
  * [40] Y. Lin and S. Chen, “Convex subspace clustering by adaptive block diagonal representation,” _IEEE Trans. Neural Netw. Learn. Syst._ , 2022.
  * [41] M. Liu, Y. Wang, J. Sun, and Z. Ji, “Adaptive low-rank kernel block diagonal representation subspace clustering,” _Applied Intelligence_ , vol. 52, no. 2, pp. 2301–2316, 2022.
  * [42] Y. Qin, H. Wu, J. Zhao, and G. Feng, “Enforced block diagonal subspace clustering with closed form solution,” _Pattern Recognition_ , vol. 130, p. 108791, 2022.
  * [43] W. Sun, J. Peng, G. Yang, and Q. Du, “Correntropy-based sparse spectral clustering for hyperspectral band selection,” _IEEE Geoscience and Remote Sensing Letters_ , vol. 17, no. 3, pp. 484–488, 2019.
  * [44] Y. Xu, S. Chen, J. Li, C. Xu, and J. Yang, “Fast subspace clustering by learning projective block diagonal representation,” _Pattern Recognition_ , vol. 135, p. 109152, 2023.
  * [45] X. Li, Y. Sun, Q. Sun, and Z. Ren, “Enforced block diagonal graph learning for multikernel clustering,” _IEEE Trans. Comput. Soc. Syst._ , 2023.
  * [46] Z. Kong, D. Chang, Z. Fu, J. Wang, Y. Wang, and Y. Zhao, “Projection-preserving block-diagonal low-rank representation for subspace clustering,” _Neurocomputing_ , vol. 526, pp. 19–29, 2023.
  * [47] S. Li, Z. Liu, L. Fang, and Q. Li, “Block diagonal representation learning for hyperspectral band selection,” _IEEE Trans. Geosci. Remote Sens._ , 2023\.
  * [48] M. Yin, W. Liu, M. Li, T. Jin, and R. Ji, “Cauchy loss induced block diagonal representation for robust multi-view subspace clustering,” _Neurocomputing_ , vol. 427, pp. 84–95, 2021.
  * [49] M. Liu, Y. Wang, V. Palade, and Z. Ji, “Multi-view subspace clustering network with block diagonal and diverse representation,” _Information Sciences_ , vol. 626, pp. 149–165, 2023.
  * [50] Z. Xie and L. Wang, “Active block diagonal subspace clustering,” _IEEE Access_ , vol. 9, pp. 83 976–83 992, 2021.
  * [51] A. Taştan, M. Muma, and A. M. Zoubir, “Fast and robust sparsity-aware block diagonal representation,” _IEEE Trans. Signal Process._ , 2023.
  * [52] X. Zhang, X. Xue, H. Sun, Z. Liu, L. Guo, and X. Guo, “Robust multiple kernel subspace clustering with block diagonal representation and low-rank consensus kernel,” _Knowledge-Based Systems_ , vol. 227, p. 107243, 2021.
  * [53] L. Fan, G. Lu, T. Liu, and Y. Wang, “Block diagonal least squares regression for subspace clustering,” _Electronics_ , vol. 11, no. 15, p. 2375, 2022\.
  * [54] Y. Xu, S. Chen, J. Li, Z. Han, and J. Yang, “Autoencoder-based latent block-diagonal representation for subspace clustering,” _IEEE Trans. Cybern._ , vol. 52, no. 6, pp. 5408–5418, 2020.
  * [55] J. Liu, Y. Sun, and Y. Hu, “Deep subspace clustering with block diagonal constraint,” _Applied Sciences_ , vol. 10, no. 24, p. 8942, 2020.
  * [56] J. Liu, X. Liu, Y. Zhang, P. Zhang, W. Tu, S. Wang, S. Zhou, W. Liang, S. Wang, and Y. Yang, “Self-representation subspace clustering for incomplete multi-view data,” in _Proceedings of the 29th ACM International Conference on Multimedia_ , 2021, pp. 2726–2734.
  * [57] J. Zhang, C.-G. Li, T. Du, H. Zhang, and J. Guo, “Convolutional subspace clustering network with block diagonal prior,” _IEEE Access_ , vol. 8, pp. 5723–5732, 2019.
  * [58] S. Li and H. Mehrabadi, “Generation of block diagonal forms using hierarchical clustering for cell formation problems,” _Procedia CIRP_ , vol. 17, pp. 44–49, 2014.
  * [59] R. Fu and Z. Li, “An evidence accumulation based block diagonal cluster model for intent recognition from eeg,” _Biomedical Signal Processing and Control_ , vol. 77, p. 103835, 2022.
  * [60] C. Chen and S. Irani, “Cluster first-sequence last heuristics for generating block diagonal forms for a machine-part matrix,” _THE INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH_ , vol. 31, no. 11, pp. 2623–2647, 1993.
  * [61] J. Chen and J. G. Dy, “A generative block-diagonal model for clustering,” in _UAI_ , 2016.
  * [62] C. Chen, J. Wei, and Z. Li, “Multiple kernel k-means clustering with block diagonal property,” _Pattern Analysis and Applications_ , vol. 26, no. 3, pp. 1515–1526, 2023.
  * [63] S.-S. Choi, S.-H. Cha, and C. C. Tappert, “A survey of binary similarity and distance measures,” _Journal of systemics, cybernetics and informatics_ , vol. 8, no. 1, pp. 43–48, 2010.
  * [64] W. Sun, J. Peng, G. Yang, and Q. Du, “Fast and latent low-rank subspace clustering for hyperspectral band selection,” _IEEE Transactions on Geoscience and Remote Sensing_ , vol. 58, no. 6, pp. 3906–3915, 2020.
  * [65] E. G. Birgin, J. M. Martínez, and M. Raydan, “Nonmonotone spectral projected gradient methods on convex sets,” _SIAM Journal on Optimization_ , vol. 10, no. 4, pp. 1196–1211, 2000.
  * [66] J. Shi and J. Malik, “Normalized cuts and image segmentation,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 22, no. 8, pp. 888–905, 2000.
  * [67] N. Mrabah, M. Bouguessa, M. F. Touati, and R. Ksantini, “Rethinking graph auto-encoder models for attributed graph clustering,” _IEEE Trans. Knowl. Data Eng._ , vol. 35, no. 5, pp. 5076–5090, 2022.
  * [68] S. Tierney, J. Gao, and Y. Guo, “Subspace clustering for sequential data,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2014, pp. 1019–1026.
  * [69] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * [70] A. Krizhevsky, G. Hinton _et al._ , “Learning multiple layers of features from tiny images,” 2009.
  * [71] S. A. Nene, S. K. Nayar, H. Murase _et al._ , “Columbia object image library (coil-100),” 1996.
  * [72] A. Coates, A. Ng, and H. Lee, “An analysis of single-layer networks in unsupervised feature learning,” in _Proceedings of the fourteenth international conference on artificial intelligence and statistics_ , 2011, pp. 215–223.
  * [73] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _2009 IEEE conference on computer vision and pattern recognition_ , 2009, pp. 248–255.
  * [74] K. Lang, “Newsweeder: Learning to filter netnews,” in _Machine learning proceedings 1995_ , 1995, pp. 331–339.
  * [75] D. D. Lewis, Y. Yang, T. Russell-Rose, and F. Li, “Rcv1: A new benchmark collection for text categorization research,” _Journal of machine learning research_ , vol. 5, no. Apr, pp. 361–397, 2004.
  * [76] J. Xie, R. Girshick, and A. Farhadi, “Unsupervised deep embedding for clustering analysis,” in _International conference on machine learning_ , 2016, pp. 478–487.
  * [77] J. F. Gemmeke, D. P. Ellis, D. Freedman, A. Jansen, W. Lawrence, R. C. Moore, M. Plakal, and M. Ritter, “Audio set: An ontology and human-labeled dataset for audio events,” in _2017 IEEE international conference on acoustics, speech and signal processing (ICASSP)_ , 2017, pp. 776–780.


# Epistemic Uncertainty-Weighted Loss for Visual Bias Mitigation

Rebecca S Stone  Nishant Ravikumar  Andrew J Bulpitt  David C Hogg
University of Leeds
{r.s.stone, n.ravikumar, a.j.bulpitt<EMAIL_ADDRESS>
###### Abstract

Deep neural networks are highly susceptible to learning biases in visual data.
While various methods have been proposed to mitigate such bias, the majority
require explicit knowledge of the biases present in the training data in order
to mitigate. We argue the relevance of exploring methods which are completely
ignorant of the presence of any bias, but are capable of identifying and
mitigating them. Furthermore, we propose using Bayesian neural networks with
an epistemic uncertainty-weighted loss function to dynamically identify
potential bias in individual training samples and to weight them during
training. We find a positive correlation between samples subject to bias and
higher epistemic uncertainties. Finally, we show the method has potential to
mitigate visual bias on a bias benchmark dataset and on a real-world face
detection problem, and we consider the merits and weaknesses of our approach.

##  1 Introduction

Modern computer vision models are highly susceptible to learning bias and
discrimination present in datasets, leading to an unfair model. While in an
ideal world, an unbiased data generation or collection process would fully
mitigate biases in model performance, data bias is complex and difficult to
fully identify for societal and historical reasons. Even with an ideal data
sampling procedure, bias can still be present.

Practitioners within the artificial intelligence community are becoming
increasingly aware of gender and racial biases learned and amplified by models
[10, 21, 16, 4, 23]. Yet given the complexity and multitude of features
present in visual data, there are additional biases which we may not even be
aware of. Wang et al. [31] show that simple transformations such as converting
images to grayscale, taking a centre crop, and reducing image resolution all
affect model fairness when introduced as a bias in the training data. In the
medical imaging domain, bias has been shown to be introduced through visual
artifacts [7, 6] and demographics (often a proxy for economic status) [11, 26,
27]. Thus, de-biasing methods which can be effective without any prior
knowledge of the types and sources of bias present in the data are valuable
for a variety of applications.

Modern visual systems are trained with large image datasets, where each
dataset is a collection of visual attributes. A fair model is one where an
input, regardless of its combination of attributes, has an equal likelihood of
being assigned a correct outcome as any other input with a different set of
attributes. While numerous types of bias exist (we recommend [25] for a
detailed discussion), we choose to focus on bias as a whole via two broad
categories as follows:

  1. 1.

Minority group bias. When a subgroup of the data has a particular attribute or
combination of attributes which are relatively uncommon compared to the rest
of the dataset, they form a minority group. A model is less likely to
correctly predict for samples from a minority group than for those of the
majority.

  2. 2.

Sensitive attribute bias. A sensitive attribute (also referred to as
“protected”) is one which should not be used by the model to perform the
target task, but which provides an unwanted “shortcut” which is easily
learned, and results in an unfair model.

In a scenario of complete blindness, the model is only aware of the target
task, and has no prior knowledge of bias in the training set.

Most current state-of-the-art bias mitigation techniques directly use bias-
informing metadata to either adjust the data before training, the model during
training, or the predictions at inference time. Oversampling techniques aim to
balance out the minority samples in the labelled data either before or during
training to create the appearance of having a balanced set [20]. The fairness
through blindness approach forces the model to simultaneously learn the target
task and to ignore, or “learn to not learn” a protected variable [2]. However,
these methods are susceptible to redundant encoding, where combinations of
other non-protected variables act as a proxy for the protected variable. In
contrast, fairness through awareness [13] approaches encode and explicitly
mitigate all protected features. A model is taught all subgroup and target
class combinations and at inference time these relationships are removed. A
recent approach titled domain independent training aims to remove class-bias
correlations by averaging class decision boundaries [31].

Other approaches manipulate the sample feature representations in latent space
to disentangle the attributes relevant for the target task from spuriously
correlated features [29, 28]. [30] use a skewness-aware reinforcement learning
method to determine the skewness between races on a face dataset with an
adaptive margin loss function. All of these approaches [29, 28, 30] also
require bias-informed metadata.

Conversely, Amini et al. [3] propose a novel method based on a variational
auto-encoder (VAE) to learn latent structure simultaneously alongside the
target task, and mitigate bias during training using dynamic batch selection
to favor samples which are likely to be subject to bias based on their
location in latent space. Recently, Xu et al.[33] use a false positive rate
penalty loss which also requires no prior knowledge of bias in the training
data, and changes the objective function to reward learning a more fair model.

We explore leveraging epistemic uncertainty estimates to mitigate both
sensitive attribute and minority group visual bias without any prior knowledge
of the types or sources of bias in the data. Unlike the VAE used in [3] which
is constrained to uni-modal latent representations, we use a fully Bayesian
neural network for a multi-modal posterior and better uncertainty estimates.
We demonstrate on a visual bias benchmark dataset how sample-level epistemic
weighting can mitigate sources of bias blindly, and further show on a real
world face classification dataset how our approach can identify and mitigate
sources of bias that other bias-informed methods cannot. We conclude by
discussing the merits and weaknesses of our proposed approach.

##  2 Related Work

###  2.1 Bayesian Neural Networks

While Bayesian approximation via dropout [14] has made Bayesian deep neural
networks applicable to many domains due to ease of use and scalability, Markov
chain Monte Carlo (MCMC) algorithms [9] are widely considered the gold
standard for Bayesian inference. However, they are computationally intractable
for large vision datasets or high-dimensional data frequently encountered in
real-world computer vision applications. A well-known scalable variant of MCMC
is stochastic gradient MCMC (SG-MCMC), based on diffusion processes such as
the Langevin diffusion. Diffusion processes are discrete-time approximations
of continuous-time processes, formulated as stochastic differential equations
(SDEs) to describe the time evolution of a moving object subject to both
random and non-random forces.

Given model parameters $\theta$, dataset $D$, prior $p(\theta)$, and potential
energy $U(\theta)$, the posterior distribution is $p(\theta\mid D)\propto
exp(-U(\theta))=-\textup{log}\,p(D\mid\theta)-\textup{log}\,p(\theta)$. As
computing $U(\theta)$ is not feasible for all $D$, SG-MCMC methods approximate
$U(\theta)$ via mini-batch learning.

Welling and Teh [32] propose Stochastic Gradient Langevin Dynamics (SGLD) and
substitute the gradient of the log-posterior density with the stochastic
gradient over the minibatch and an additive Gaussian noise term that acts as
an upper bound on the error.

$\theta_{i}=\theta_{i-1}-\alpha_{i}\Delta\tilde{U}(\theta_{i})+\sqrt{2\alpha_{i}\epsilon_{i}}$
(1)

The update to parameters is shown in Equation 1, at iteration $i$ of the
algorithm, for normal distribution $\epsilon_{i}$, stepsize $\alpha_{i}$ and
minibatch approximation of the potential energy $\tilde{U}$.

While convergence is in practice slower than for other MCMC algorithms, the
parameter update process closely resembles stochastic gradient descent and is
generalisable to any neural network. To speed up convergence and better
explore complex multimodal distributions common for deep neural networks,
Zhang et al. [34] propose cyclical SG-MCMC (cSG-MCMC), where a cyclical
stepsize schedule allows for quicker discovery of new modes. For each cycle of
the learning rate schedule, an initial larger step size allows for
exploration, and the subsequent smaller step sizes allow for sampling.

###  2.2 Leveraging Bayesian Uncertainties

Uncertainties can be divided into two categories, epistemic and aleatoric.
Epistemic uncertainty, or model uncertainty, arises from lack of knowledge
either about a process or parameter, and is caused by missing information or
data. This uncertainty can be reduced given more data. Aleatoric uncertainty,
or data uncertainty, arises from probabilistic variations or noise in the data
and even given an infinite amount of data, cannot be reduced. [17] demonstrate
that epistemic uncertainty can reveal data bias, while [1] argue that fairness
approaches should equalize only errors arising from epistemic, not aleatory
uncertainties. Thus, for mitigating bias, we are most interested in epistemic
uncertainties.

Branchaud-Charron et al. [8] explore whether using Bayesian Active Learning by
Disagreement (BALD) [15] can help mitigate bias against a protected class.
They demonstrate that an acquisition scheme which greedily reduces epistemic
uncertainty has potential for bias mitigation. This method shows promising
results for leveraging epistemic uncertainties to mitigate bias when all of a
target class is a minority group, but does not deal with sensitive feature
scenarios. Khan et al. [22] use Bayesian uncertainty estimates to deal with
class imbalance by weighting the loss function to move learned class
boundaries away from more uncertain classes. While their primary focus is
class uncertainties, they also consider sample-based uncertainties. They
propose a curriculum learning schedule with a variational dropout Bayesian
neural network which approximates uncertainties first using softmax outputs,
then class-level uncertainties, and finally for the last 10 epochs, sample-
based uncertainties. As we are focusing on both sensitive attribute and
minority group bias, neither of which we expect to be constrained to a unique
class, our approach focuses on sample-level uncertainties. This eliminates the
need for tuning a curriculum learning schedule, and for encouraging the model
to look at class uncertainties. Furthermore, we opt to use SG-MCMC over
variational dropout for better uncertainty estimates.

##  3 Methodology

We propose a simple uncertainty-weighted loss function for visual bias
mitigation. Given a Bayesian neural network with parameters $\theta$ and
posterior $p(\theta\mid D,x)$ for class-labelled training data $D$ and test
sample $x_{i}$, the predictive posterior distribution for a given predicted
class $y_{i}$ is then:

$p(y_{i}\mid D,x_{i})=\int p(y_{i}\mid\theta)p(\theta\mid D,x_{i})d\theta$ (2)

We can approximate this predictive posterior via Monte Carlo sampling. Given
$T$ Monte Carlo samples total, $\frac{T}{c}$ per learning schedule cycle $c$,
we thus have predictive mean:

$\mu_{i}\approx\frac{1}{T}\sum_{j=1}^{T}p(y_{i}\mid x_{i},\theta_{j})$ (3)

and model uncertainty corresponding to this prediction:

$\sigma_{i}\approx\frac{1}{T}\sqrt{\left(\sum_{j=1}^{T}p(y_{i}\mid
x_{i},\theta_{j})-\mu_{i}\right)^{2}}$ (4)

We propose the following uncertainty-weighted loss function for training
sample $(x_{i},y_{i})$, given the cross entropy loss $L(x_{i},y_{i})$, the
additive Gaussian noise term from 1 and a tunable parameter $\kappa$
controlling the degree of weighting, especially for high-uncertainty samples.

$\hat{L}(x_{i},y_{i})=L(x_{i},y_{i})*(1.0+\sigma_{i,y_{i}})^{\kappa}$ (5)

As we expect a normally weighted sample to have weight 1.0, we shift the
distribution such that lowest uncertainty samples are never irrelevant to the
loss term. We compute $\hat{L}$ sample-wise and then reduce over the
minibatch. $\kappa=1$ is equivalent to a normal weighting, whereas
$\kappa\to\infty$ increases the importance of high-uncertainty samples. In our
fully bias-unaware setup, $\kappa$ is optimised based on optimal validation
loss tuned via grid search.

Algorithm 1 Training loop using uncertainty-weighted loss

1:Training data X, Y, weighting parameter $\kappa$

2:Initialize parameters $\theta$

3:for each cycle, $c$ do

4: for each epoch in cycle, $e$ do

5: if $e$ in sampling phase then

6: Sample $\theta_{j}\sim P(\theta\mid D,x)$

7: Save $P(y=\hat{y}\mid x,\theta_{j})\,\forall x\in X$

8: Update $\left[w\leftarrow w-\epsilon\nabla L(x,y)\right]_{w\in{\theta}}$

9: else if $c$ $>$ 0 then

10: $\sigma_{i}\leftarrow\frac{1}{T}\sqrt{\left(\sum_{j=1}^{T}p(y_{i}\mid
x_{i},\theta_{j})-\mu_{i}\right)^{2}}$

11: $\hat{L}(x_{i},y_{i})\leftarrow
L(x_{i},y_{i})*(1.0+\sigma_{i,y_{i}})^{\kappa}$

12: Update $\left[w\leftarrow
w-\epsilon\nabla\hat{L}(x,y)\right]_{w\in{\theta}}$

13: end if

14: end for

15:end for

The earliest moment at which we can compute $\sigma$ over the training data is
during the sampling phase of the first cycle. Uncertainty values are updated
at each consecutive cycle to reflect the developing posterior, requiring a
total of $T(C-1)$ samples from the posterior for total number of cycles $C$.
We speed up this process during training by saving each training sample’s
predictive distribution for each $\theta_{j}$ rather than all $\theta$. Once
the sample-wise model uncertainties have been computed, all predictions can be
discarded. We set the length of the sampling phase to be 5 epochs, the
shortest length for which uncertainty estimates are consistently stable for a
fixed seed.

Model | Description | Bias ($\downarrow$) | Mean acc ($\%$,$\uparrow$) | Opp. ($\%$,$\downarrow$) | Odds. ($\%$,$\downarrow$)
---|---|---|---|---|---
Baseline | N-way softmax | 0.074 | 88.5 ± 0.3 | 13.07 $\pm$ 0.4 | 7.19 $\pm$ 0.2
S-Sampling | N-way softmax | 0.066 | 89.1 $\pm$ 0.4 | 12.58 $\pm$ 0.2 | 6.91 $\pm$ 0.1
Adversarial | w/ uniform confusion | 0.101 | 83.8 $\pm$ 1.1 | 16.71 $\pm$ 1.4 | 9.28 $\pm$ 0.7
| w/ gradient reversal, proj | 0.094 | 84.1 $\pm$ 1.0 | 14.13 $\pm$ 1.4 | 7.89 $\pm$ 0.8
DomainDiscrim | joint ND-way softmax | 0.040 | 90.3 $\pm$ 0.5 | 7.27 $\pm$ 0.3 | 4.02 $\pm$ 0.2
DomainIndepend [31] | joint ND-way softmax | 0.004 | 92.9 $\pm$ 0.1 | 1.07 $\pm$ 0.2 | 0.59 $\pm$ 0.1
FeatureLabel [29] | N-way cos softmax per D | 0.004 | 91.5 $\pm$ 0.2 | 0.83 $\pm$ 0.1 | 0.46 $\pm$ 0.1
Db-Vae [3] | latent structure re-weighting | 0.167 | 90.2 $\pm$ 0.4 | 6.87 $\pm$ 0.5 | 0.78 $\pm$ 0.2
Our approach | w/ unc.-weighted loss | 0.035 | 89.2 $\pm$ 0.2 | 12.11 $\pm$ 0.2 | 6.20 $\pm$ 0.2
Table 1: Multi-class classification, mean bias accuracy, equality of opportunity and equalized odds for bias benchmark dataset CIFAR-10S, a dataset with sensitive attribute bias. Note that all methods except for the baseline (a regular deterministic network with no bias mitigation), the DB-VAE, and ours are bias-informed during training. | Baseline | Our approach
---|---|---
TPR Color ($\%$),$\uparrow$) | 92.1 $\pm$ 0.1 | 93.6 $\pm$0.1
TPR Gray ($\%$),$\uparrow$) | 91.6 $\pm$ 0.1 | 93.0 $\pm$ 0.1
TPR Gap ($\%$),$\downarrow$) | 1.8 | 0.6
Table 2:  Uncertainty-weighted loss reduces the TPR gap on minority bias dataset CIFAR-10M. | Bias ($\%$,$\downarrow$) | Mean acc ($\%$,$\uparrow$)
---|---|---
Baseline | 0.074 | 88.5 $\pm$ 0.3
cSG-MCMC | 0.060 | 88.1 $\pm$ 0.2
cSG-MCMC weighted loss | 0.035 | 89.2 $\pm$ 0.2
Table 3: Ablation study showing results of a Bayesian cSG-MCMC network with
regular unweighted cross-entropy loss.

##  4 Evaluation

###  4.1 CIFAR-10 Skewed Visual Bias Benchmark

We compose the same baseline dataset, “CIFAR-10 Skewed” (CIFAR-10S) proposed
by Wang et al. [31] to evaluate the performance of a Bayesian CNN without any
adjustments. 95% of the images for 5 out of 10 target classes and 5% of the
remaining classes are converted to grayscale, resulting in an overall balanced
dataset with respect to colour but a strong skew within each class. As a model
can learn the presence or absence of colour as a class indicator, this is an
instance of sensitive attribute bias. We use the official CIFAR-10 test set
and a 5:1 training-validation split for the total of 60000 images.

To provide a fair comparison, we follow the same training and architecture
choices as proposed, with the exception of the learning rate, which is set to
maximise performance for the cyclical step size schedule of our Bayesian
formulation, and with momentum 0.9 due to the Langevin dynamic estimation.
Using validation loss to choose hyperparameters, we train for 280 epochs and
four cycles. With the exception of our reproduction of the DB-VAE method in
[3], all experiments use a ResNet-18 convolutional neural network as the base
architecture. For the DB-VAE, we follow the same architecture as used in the
original paper, adapted for multi-target classification on CIFAR-10S, up-
sizing the images to 64 x 64 to match the expected input dimensions, and grid
search to find the optimal value for de-biasing parameter, $\alpha$ = 0.001.

Figure 1: Face training samples from CelebA with lowest epistemic
uncertainties (left) and faces with highest epistemic uncertainties (right).
The faces with low uncertainties tend to be well-lit, facing forward with hair
cleanly framing the face, and primarily lighter-skinned with few obscuring
accessories. Faces with high uncertainties are more likely to be subject to
discrimination due to variance in lighting, pose, colouring, and obscuring
objects, among other reasons.

Figure 2: Left: a random selection of samples from CelebA; Right: and the same
from FairFaces.

We evaluate the models using four metrics:

  * •

Mean test accuracy on fully gray-scale and fully colour test sets, indicating
how much the model learned the undesired correlation between the colour of
each sample and its label;

  * •

Bias amplification score [35] proposed first in a natural language processing
setting and generalised for the CIFAR-10S dataset in Equation 6 as suggested
in [31]. $Gr_{c}$ is the number of gray-scale test samples predicted as class
$c$, and $Col_{c}$ the colour samples predicted as class $c$.

$\displaystyle\textup{bias ampl.}=\frac{1}{\mid C\mid}\;\sum_{c\in
C}\frac{\textup{max}(Gr_{c},Col_{c})}{Gr_{c}+Col_{c}}-0.5$ (6)

  * •

Equalized odds [18] is satisfied for predictor $\hat{y}$ when $\hat{y}$ and
sensitive attribute a are independent conditional on outcome y,
$\forall\gamma\in{0,1}$: $P(\hat{y}=1\mid y=\gamma,a=0)=P(\hat{y}=1\mid
y=\gamma,a=1)$. A difference in equality of opportunity score is derived as
per [5] where $FN_{y}^{a}$ is the number of false negatives of class y with
protected attribute a:

$\displaystyle\frac{1}{y}\sum_{y\in
Y}\left|\frac{TP_{y}^{1}}{TP_{y}^{1}+FN_{y}^{1}}-\frac{TP_{y}^{0}}{TP_{y}^{0}+FN_{y}^{0}}\right|$
(7)

  * •

Equality of opportunity [18] is a relaxed form of equalized odds which
requires non-discrimination on only one desired outcome, $y=1$,
$P(\hat{y}=1\mid y=1,a=0)=P(\hat{y}=1\mid y=1,a=1)$. A difference of equalized
odds score as per [4] is as follows:

$\displaystyle
0.5\ast\left(\left|FPR_{y}^{1}-FPR_{y}^{0}\right|+\left|TPR_{y}^{1}-TPR_{y}^{0}\right|\right)$
(8)

For CIFAR-10S, we find that samples with a sensitive attribute have higher
uncertainties. They constitute 20$\%$ of samples in the samples with the
highest 10$\%$ uncertainties, while only 5$\%$ of samples in the dataset have
a sensitive attribute. In contrast, less than 2$\%$ of samples in the lowest
10$\%$ uncertainties have a sensitive attribute.

As CIFAR-10S is a case of sensitive attribute bias, we formulate a second
dataset CIFAR-10M “Minority” (CIFAR-10M) to represent minority group bias. We
set grayscale as the minority attribute, and for each of the 10 classes, $5\%$
of samples are converted to grayscale. The remaining $95\%$ remain in colour.
We split the training-validation sets using a 5:1 ratio. The results of our
debiasing method on this dataset are presented in Table 2.

While not competitive with all bias-informed methods, our approach
demonstrates an ability to de-bias blindly on both the benchmark dataset with
sensitive attribute bias (CIFAR-10S), and our constructed dataset with
minority group bias (CIFAR-10M).

###  4.2 On a Real-World Face Detection Problem

Similar to [3], we create a face vs. no-face binary classification dataset
using 20k instances of faces from CelebA [24] and 20k non-face samples from a
variety of different classes from ImageNet [12], for a training set of 40k
images. We evaluate the model on FairFaces [21]111Due to the inaccessibility
of the Pilot Parliaments Benchmark dataset [10] because of data privacy
issues, we have chosen to evaluate on FairFaces., consisting of 108,501 images
with gender, race, and age annotations, balanced across 7 race groups: White,
Black, Indian, East Asian, Southeast Asian, Middle Eastern, and Latino, and 9
age subgroups from “0-2” to “over 70”. The high level of diversity is visible
in Figure 2. The distribution shift between the training and test data is such
that we center crop the CelebA images to 124 x 124 and downsample all face and
non-face training data to 64 x 64 such that the general resolution and
positioning of the face in the images do not hinder the model from
generalising. We use the Fréchet Inception Distance [19] between the CelebA
and FairFace datasets to guide our transforms to the CelebA data, supported by
visual comparison of random selections of images from both datasets. No
transforms other than resizing are applied to the FairFace data, ensuring that
the diversity is still intact.

We train a regular ResNet18 to convergence at 30 epochs using an 8:2 split of
the CelebA/ImageNet dataset for training and validation and a standard SGD
optimizer with learning rate of 0.01. The cSG-MCMC Bayesian model with
uncertainty-weighted loss is similarly trained with 4 cycles of 30 epochs each
for a total of 120 epochs.

For every subgroup, the uncertainty-weighted loss decreases the TPR gap, with
the discrepancies for the 7 subgroups with lowest TPR rates shown in Figure 3.

Figure 3: Performance discrepancies between baseline (deterministic model with
no de-biasing) and Bayesian model with uncertainty-weighted loss for minority
subgroups with lowest TPRs. Figure 4: True positive rate (TPR) over the entire
FairFace dataset as a function of tunable de-biasing parameter kappa $\kappa$,
showing how the degree of de-biasing can be controlled by $\kappa$.

Given that sample-level weighting by a factor of $N$ during training is
equivalent to that sample appearing $N$ times, our approach could be
categorized as a type of sub-sampling algorithm. Thus, it suffers from the
same weakness as all sub-sampling algorithms, a tendency to overfit over-
sampled data. This can only be partially mitigated by aggressive data
augmentation. We hypothesize that this explains why increasing tunable de-
biasing parameter $\kappa$ beyond the optimal value results in worse
performance as shown in Figure 4.

Figure 1 shows samples with high uncertainties, which clearly have features
which make them more likely to be subject to bias. A bias-informed method
could strongly mitigate bias due to known societal biases such as gender and
race, or skin phenotype. But since it would be unlikely to also have access to
meta-data which identifies variances in lighting, pose, image resolution,
etc., all of which also result in unfairness, such methods would not target
such biases.

Such an approach is valuable in medical imaging applications with large
population image analysis due to the inherent difficulty in collecting meta
data. Sensitivity and privacy requirements result in imaging datasets with
very few annotations and little, if any, associated patient meta data. This
presents a challenge for bias-informed methods, and serves as motivation for
further exploration of methods which can mitigate without requiring
comprehensive knowledge of all biases.

##  5 Conclusion

We have shown that an epistemic uncertainty-weighted loss function has
potential for bias mitigation for datasets with unknown sources of bias. We
cannot conclude that the approach works in all cases based on our experiments,
nor do we attempt to provide a mathematical proof that this should be the
case. Some training datasets may contain an over-sampling from unprivileged
groups, in which case the correlation with epistemic uncertainties may no
longer exist. Thus, our exploration focuses only on cases of minority group
and sensitive attribute bias. While outperformed by most bias-informed models,
our method is a step towards exploring how epistemic uncertainties in Bayesian
neural networks can be leveraged for identifying, understanding, and
mitigating the types and sources of visual bias in data.

Acknowledgements. The first author is a recipient of a Rabin Ezra Scholarship.
Special thanks to Jose Sosa and Mohammed Alghamdi from the School of
Computing’s Computer Vision Group for critical feedback and many great
discussions.

## References

  * [1] Junaid Ali, Preethi Lahoti, and Krishna P Gummadi.  Accounting for model uncertainty in algorithmic discrimination.  In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 336–345, 2021.
  * [2] Mohsan Alvi, Andrew Zisserman, and Christoffer Nellåker.  Turning a blind eye: Explicit removal of biases and variation from deep neural network embeddings.  In Proceedings of the European Conference on Computer Vision (ECCV) Workshops, pages 0–0, 2018.
  * [3] Alexander Amini, Ava P Soleimany, Wilko Schwarting, Sangeeta N Bhatia, and Daniela Rus.  Uncovering and mitigating algorithmic bias through learned latent structure.  In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 289–295, 2019.
  * [4] Rachel KE Bellamy, Kuntal Dey, Michael Hind, Samuel C Hoffman, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mehta, Aleksandra Mojsilovic, et al.  Ai fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias.  arXiv preprint arXiv:1810.01943, 2018.
  * [5] Alex Beutel, Jilin Chen, Zhe Zhao, and Ed H Chi.  Data decisions and theoretical implications when adversarially learning fair representations.  arXiv preprint arXiv:1707.00075, 2017.
  * [6] Alceu Bissoto, Michel Fornaciali, Eduardo Valle, and Sandra Avila.  (de) constructing bias on skin lesion datasets.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 0–0, 2019.
  * [7] Alceu Bissoto, Eduardo Valle, and Sandra Avila.  Debiasing skin lesion datasets and models? not so fast.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 740–741, 2020.
  * [8] Frédéric Branchaud-Charron, Parmida Atighehchian, Pau Rodríguez, Grace Abuhamad, and Alexandre Lacoste.  Can active learning preemptively mitigate fairness issues?  arXiv preprint arXiv:2104.06879, 2021.
  * [9] Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng.  Handbook of markov chain monte carlo.  CRC press, 2011.
  * [10] Joy Buolamwini and Timnit Gebru.  Gender shades: Intersectional accuracy disparities in commercial gender classification.  In Conference on fairness, accountability and transparency, pages 77–91. PMLR, 2018.
  * [11] Terrance De Vries, Ishan Misra, Changhan Wang, and Laurens Van der Maaten.  Does object recognition work for everyone?  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 52–59, 2019.
  * [12] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [13] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel.  Fairness through awareness.  In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214–226, 2012.
  * [14] Yarin Gal and Zoubin Ghahramani.  Dropout as a bayesian approximation: Representing model uncertainty in deep learning.  In international conference on machine learning, pages 1050–1059. PMLR, 2016.
  * [15] Yarin Gal, Riashat Islam, and Zoubin Ghahramani.  Deep bayesian active learning with image data.  In International Conference on Machine Learning, pages 1183–1192. PMLR, 2017.
  * [16] Markos Georgopoulos, Yannis Panagakis, and Maja Pantic.  Investigating bias in deep face analysis: The kanface dataset and empirical study.  Image and Vision Computing, 102:103954, 2020.
  * [17] Asma Ghandeharioun, Brian Eoff, Brendan Jou, and Rosalind Picard.  Characterizing sources of uncertainty to proxy calibration and disambiguate annotator and data bias.  In 2019 IEEE/CVF International Conference on Computer Vision Workshop (ICCVW), pages 4202–4206. IEEE, 2019.
  * [18] Moritz Hardt, Eric Price, and Nati Srebro.  Equality of opportunity in supervised learning.  Advances in neural information processing systems, 29, 2016.
  * [19] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  Gans trained by a two time-scale update rule converge to a local nash equilibrium.  Advances in neural information processing systems, 30, 2017.
  * [20] Faisal Kamiran and Toon Calders.  Data preprocessing techniques for classification without discrimination.  Knowledge and information systems, 33(1):1–33, 2012.
  * [21] Kimmo Kärkkäinen and Jungseock Joo.  Fairface: Face attribute dataset for balanced race, gender, and age.  arXiv preprint arXiv:1908.04913, 2019.
  * [22] Salman Khan, Munawar Hayat, Syed Waqas Zamir, Jianbing Shen, and Ling Shao.  Striking the right balance with uncertainty.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 103–112, 2019.
  * [23] Agostina J Larrazabal, Nicolás Nieto, Victoria Peterson, Diego H Milone, and Enzo Ferrante.  Gender imbalance in medical imaging datasets produces biased classifiers for computer-aided diagnosis.  Proceedings of the National Academy of Sciences, 117(23):12592–12594, 2020.
  * [24] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang.  Large-scale celebfaces attributes (celeba) dataset.  Retrieved August, 15(2018):11, 2018.
  * [25] Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan.  A survey on bias and fairness in machine learning.  ACM Computing Surveys (CSUR), 54(6):1–35, 2021.
  * [26] Laleh Seyyed-Kalantari, Guanxiong Liu, Matthew McDermott, Irene Y Chen, and Marzyeh Ghassemi.  Chexclusion: Fairness gaps in deep chest x-ray classifiers.  In BIOCOMPUTING 2021: Proceedings of the Pacific Symposium, pages 232–243. World Scientific, 2020.
  * [27] Karin Stacke, Gabriel Eilertsen, Jonas Unger, and Claes Lundström.  Measuring domain shift for deep learning in histopathology.  IEEE journal of biomedical and health informatics, 25(2):325–336, 2020.
  * [28] Enzo Tartaglione, Carlo Alberto Barbano, and Marco Grangetto.  End: Entangling and disentangling deep representations for bias correction.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13508–13517, 2021.
  * [29] William Thong and Cees GM Snoek.  Feature and label embedding spaces matter in addressing image classifier bias.  arXiv preprint arXiv:2110.14336, 2021.
  * [30] Mei Wang and Weihong Deng.  Mitigating bias in face recognition using skewness-aware reinforcement learning.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9322–9331, 2020.
  * [31] Zeyu Wang, Klint Qinami, Ioannis Christos Karakozis, Kyle Genova, Prem Nair, Kenji Hata, and Olga Russakovsky.  Towards fairness in visual recognition: Effective strategies for bias mitigation.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 8919–8928, 2020.
  * [32] Max Welling and Yee W Teh.  Bayesian learning via stochastic gradient langevin dynamics.  In Proceedings of the 28th international conference on machine learning (ICML-11), pages 681–688. Citeseer, 2011.
  * [33] Xingkun Xu, Yuge Huang, Pengcheng Shen, Shaoxin Li, Jilin Li, Feiyue Huang, Yong Li, and Zhen Cui.  Consistent instance false positive improves fairness in face recognition.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 578–586, 2021.
  * [34] Ruqi Zhang, Chunyuan Li, Jianyi Zhang, Changyou Chen, and Andrew Gordon Wilson.  Cyclical stochastic gradient mcmc for bayesian deep learning.  arXiv preprint arXiv:1902.03932, 2019.
  * [35] Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang.  Men also like shopping: Reducing gender bias amplification using corpus-level constraints.  In EMNLP, 2017.


Perturbation-based Sequence Selection for Probabilistic Amplitude Shaping

Mohammad Taha Askari(1) and Lutz Lampe(1)

(1) Department of Electrical and Computer Engineering, University of British Columbia, Vancouver, BC V6T 1Z4, Canada,

We introduce a practical sign-dependent sequence selection metric for probabilistic amplitude shaping and propose a simple method to predict the gains in signal-to-noise ratio (SNR) for sequence selection. The proposed metric provides a $0.5$ dB SNR gain for single-polarized 256-QAM transmission over a long-haul fiber link.
©2024 The Author(s)

§ INTRODUCTION

Probabilistic amplitude shaping (PAS) has been adopted widely since its introduction in <cit.>, due to its rate adaptability and systematic integration with forward error correction (FEC). Recently, PAS has also been utilized in conjunction with the optimization of the high dimensional distribution of shaped symbol sequences by a technique known as sequence selection. Originally, sequence selection was implemented based on rejection sampling, where a number of symbol sequences are generated
from an unbiased source[Examples are independent and identically distributed (i.i.d) symbols with Gaussian distribution or symbols generated from a distribution matcher (DM).], and only a subset of those is retained based on a selection metric <cit.>. Using this, reference <cit.> and its extension <cit.> provided quantitative results for a new lower bound on the capacity of the optical fiber channel. However, the selection metric was more conceptual than practical since (i) it required the fiber channel simulation with the split-step Fourier method (SSFM) and (ii) did not provide a mapping between information bits and selected sequences.

The first pragmatic implementation of sequence selection as part of a PAS scheme is list-encoding constant composition distribution matching (L-CCDM)<cit.>. In L-CCDM, candidate sequences are generated by concatenating so-called flipping bits and information bits at the input of the CCDM, and selection is performed using the energy dispersion index (EDI) as a metric. The EDI is an energy metric
that has been shown to be negatively correlated with the effective signal-to-noise ratio (SNR) of the nonlinear fiber channel for PAS with CCDM <cit.>. Another energy metric for sequence selection, referred to as lowpass filtered symbol amplitude sequence (LSAS), was introduced in <cit.> and   <cit.>. LSAS is based on a simplified first-order perturbative model and was shown to outperform EDI for sequence selection <cit.>.

The mentioned earlier studies on practical sequence selection demonstrated significant performance improvements in nonlinear optical fiber links. However, they had two shortcomings in common. First, a carrier phase recovery (CPR) was not considered at the receiver. Second, the EDI and LSAS metrics are purely based on the energy of symbols. The former has been discussed in <cit.>. The authors highlighted that since a CPR partially compensates the nonlinearity induced phase noise, (i) any study on sequence selection for nonlinear interference noise (NLIN) mitigation needs to be verified with the presence of a practical CPR at the receiver, and (ii) a solely energy-based selection metric may fall short to provide substantive improvements in practical systems.

The work in <cit.> took one further step towards practical sequence selection by introducing several schemes for candidate generation. Of particular interest is a multi-block FEC architecture that makes use of the bootstrap scheme from <cit.> to separate sign-dependent sequence selection and FEC. Since accounting for signs (or phases) in addition to selecting amplitudes (i.e., energies) of symbols has been shown to be almost as effective as also selecting signs <cit.>, this architecture reduces the effort for sequence generation to the necessary.

The recent investigation in <cit.>  tackles the remaining problem of finding a selection metric that is sensitive to symbol signs but does not require an SSFM simulation. For this, the authors introduce the dispersion-aware EDI (D-EDI) as an extension of EDI. D-EDI attempts to account for the signs by averaging EDI metrics for several partially propagated sequences along a linear dispersive lossless fiber.
D-EDI inherits the problems of EDI though, which are rooted in the simple windowing of energy sequences and has been improved on by the LSAS metric <cit.>. As pointed out in <cit.>, it is mostly applicable for digital multicarrier transmission with low baud rate per subcarrier.

In this paper, we propose a novel perturbation-based alternative to SSFM as a sequence selection metric. It consists of an energy-dependent NLIN term similar to LSAS and a symbol-dependent term that also accounts for the signs of symbols. As a second contribution, we present the use of the perturbative model in combination with the enhanced Gaussian noise (EGN) model <cit.> for the nonlinear fiber channel to estimate the effective SNR. This permits us to make predictions for the benefits of sequence selection and guide, for example, the choice of the number of sequences that should be generated.

§ SEQUENCE SELECTION SCHEME

We apply the multi-block FEC-independent architecture from <cit.> that does not involve the FEC encoding in the sequence selection process.

Let $K$ be the FEC blocklength in terms of quadrature amplitude modulation (QAM) symbols, and $L$ be the length used for sequence selection, where $m=K/L$ is assumed to be an integer. We use PAS with an ideal DM that realizes a  Maxwell Boltzmann (MB) distribution and produces two sequences of each $L$ amplitudes for the in-phase and quadrature-phase parts of $L$ QAM symbols. Because of the bootstrap FEC scheme, the signs for the in-phase and quadrature-phase components are known. We next generate $N$ QAM candidate sequences of length $L$ by symbol interleaving.

This process is repeated for $m$ information blocks according to the FEC blocklength, so that we have $N$ candidate sequences for each of the $m$ information blocks.

The $n$-th candidate sequences, $n=1,2,\ldots,N$, for the $m$ different information blocks are concatenated into one long sequence, which is input to the NLIN estimator using the first-order perturbative model as described in the next section. We use the $\ell_2$ norm of the estimated NLIN associated with each of the $N$ candidate sequences corresponding to the same information block to perform selection. Finally, the selected candidates are concatenated to form a sequence of $K$ QAM symbols used for transmission.

We note that we use a block memoryless selection procedure, i.e., we ignore inter-block NLIN effects. Furthermore, side information of $\log_2(N)$ bits to identify the selected sequence at the receiver needs to be transmitted. While  <cit.> inserted pilot symbols for this, we suggest including the $\log_2(N)$ redundant bits into the input for the FEC encoding so that side information is FEC protected.

\begin{equation} \label{eq:add}
\begin{split}
\Delta^{(c)}(n) = {\j}\gamma \sum_{c'\in {\cal C}} \sum_{m \in \mathbb{Z}\backslash\{0\}} \sum_{k \in \mathbb{Z}\backslash\{0\}} s^{(c')}(n+m)[s^{(c')}(n+m+k)]^* s^{(c)}(n+k) h^{(c,c')}(m,k).
\end{split}
\end{equation}

§ PERTURBATION-BASED METRIC

The proposed sequence-selection metric is based on the combination of the perturbation model in <cit.> and the additive-multiplicative model in <cit.> for the signal-signal interactions in optical fiber propagation. For concreteness, we consider a single-polarization wavelength division multiplexing (WDM) system and note that the extension to dual-polarization is straightforward <cit.>. The symbol-rate sampled and dispersion compensated received signal in channel $c\in \cal C$ is written as

\begin{equation}
\label{eq:am_model}
r^{(c)}(n) = s^{(c)}(n) \e^{\j \theta^{(c)}(n)} + \Delta^{(c)}(n),
\end{equation}

where $s^{(c)}(n)$ is the transmitted symbol.
The NLIN in Eq. (<ref>) consists of the multiplicative phase noise

\begin{equation}
\label{eq:mult}
\theta^{(c)}(n) = \gamma \sum_{c' \in {\cal C}} \sum_{m \in \mathbb{Z}} |s^{(c')}(n+m)|^2 h^{(c,c')}(m,0),
\end{equation}

and the additive NLIN term shown in Eq. (<ref>) at the top of this page.

$\gamma$ is the fiber nonlinearity parameter,
and $h^{(c,c')}$ are the perturbation coefficients capturing the effect of channel $c'$ on channel $c$ <cit.>.

For the purpose of sequence selection, we
subtract the average phase rotation $\bar \theta^{(c)}$ to obtain the model

\begin{equation}
\label{eq:am_model_cpr}
\hat{r}^{(c)}(n) = s^{(c)}(n) \e^{\j (\theta^{(c)}(n) - \bar \theta^{(c)})} + \Delta^{(c)}(n).
\end{equation}

Finally, the selection metric for a sequence of symbols $\ve{s^{(c)}} = [s^{(c)}(0), \dots, s^{(c)}(L-1)]$ and the predicted received samples $\ve{\hat{r}^{(c)}} = [\hat{r}^{(c)}(0), \dots, \hat{r}^{(c)}(L-1)]$
is the squared $\ell_2$ norm

\begin{equation}
\label{eq:am_metric}
\lambda_{\mathrm{AM}} = \norm{\ve{\hat{r}^{(c)}}-\ve{s^{(c)}}}^2.
\end{equation}

We refer to Eq. (<ref>) as the additive-multiplicative metric. It takes into account both energies and signs of symbols. When only considering the multiplicative NLIN part in Eq. (<ref>), we obtain the energy-based LSAS metric from  <cit.> as a special case. We remark that while the multiplicative and additive terms in Eq. (<ref>) and Eq. (<ref>)  are described for the general case of WDM channels in set $\cal C$, we only consider the intra-channel NLIN for sequence selection in this work. However, extension to inter-channel NLIN, which is relevant for digital multicarrier systems, is straightforward using Algorithm 1 from <cit.>.

§ PERFORMANCE PREDICTION

We suggest also applying the additive-multiplicative model for NLIN in Eq. (<ref>) for predicting the gains achievable with sequence selection. For this, we consider the EGN model and relate the NLIN power $P_{\mathrm{NLIN}}$ to the transmit power $P$ as

\begin{equation}
% \vspace{-1mm}
\label{eq:egnnlin}
P_{\mathrm{NLIN}} = \eta P^3,
\end{equation}

where  the nonlinearity coefficient $\eta$ depends on signal-signal interactions and modulation format <cit.>. Considering two sequence-selection shaping schemes corresponding to coefficients $\eta_1$ and $\eta_2$, the ratio of their effective SNRs at optimum transmit power is given by

\begin{equation}
\label{eq:egnsnr}
\frac{\mathrm{SNR}_1}{\mathrm{SNR}_2} = \left(\frac{\eta_2}{\eta_1}\right)^{1/3}.
\end{equation}

From Eq. (<ref>) and Eq. (<ref>), measuring the $P_{\mathrm{NLIN}}$ using Eq. (<ref>) permits us to predict the SNR gain in dB as

\begin{equation}
\label{eq:egngain}
\mathrm{SNR}_{1}- \mathrm{SNR}_{2} = \frac{1}{3}\left(P_{\mathrm{NLIN},2}-P_{\mathrm{NLIN},1}\right)\;\mbox{dB}.
% \vspace{-1mm}
\end{equation}

In the next section, we use the metric in Eq. (<ref>) for sequence selection, and we will compare the SNR gain prediction using Eq. (<ref>) with the measured SNR gain by full SSFM simulation.

§ NUMERICAL RESULTS

The system setup is adopted from <cit.>.
We use the SSFM to simulate communication over $3$ single-polarized WDM channels, each operating at $32$ GBd baud rate, and with a channel spacing of $50$ GHz. The sender applies PAS with MB shaping for 256-QAM and a rate of $2.5$ bits/amplitude and sequence selection with sequence length $L=256$. The link consists of $20$ spans of $80$ km of a standard single-mode fiber, with chromatic dispersion coefficient (CD) $17$ ps/nm/km, nonlinearity parameter $\gamma\!=\!1.37$ W$^{-1}$km$^{-1}$, and fiber loss $0.2$ dB/km. An erbium-doped fiber amplifier (EDFA) with noise figure $6$ dB is placed at the end of each span. At the receiver, CD is electronically compensated and a linear pilot-aided CPR, adopted from <cit.>, with a $1\%$ pilot rate is applied. We estimate the achievable information rate (AIR) using the mismatched decoding method described in <cit.>, and deduct for the selection rate loss of $\log_2(N)/L$ bits/2D. Each simulation result is based on $2^{18}$ generated $256$-QAM symbols, and the performance results for the WDM center channel are considered.

Fig. <ref> shows the SNR gain at optimal launch power achieved by sequence selection using the additive-multiplicative metric in Eq. (<ref>) with $N \in \{1, 2, 4, \dots, 64\}$ candidates, where $N\!=\!1$ corresponds to the system without sequence selection. We observe that sequence selection can provide more than $0.5$ dB gain in SNR. Most of the gain is achieved using only $N\!=\!8$ candidates, which corresponds to allocating only $3$ out of $2048$ bits for selection of a sequence. In addition to the SNR gain measured after SSFM simulation, we used Eq. (<ref>) to approximate a noiseless fiber channel, and after applying CPR at the receiver, we used Eq. (<ref>) to estimate the SNR gains. We observe that SNR measurements and predictions are well aligned in Fig <ref>. This supports the use of the additive-multiplicative model both for sequence selection and for performance prediction.

SNR gain for sequence selection over $N$ candidates.

Fig. <ref> shows the AIR versus launch power for the shaping without selection ($N\!=\!1$), selection with $N\!=\!64$ candidates using (i) only the multiplicative term and (ii) both additive and multiplicative terms of Eq. (<ref>). We observe that all three schemes perform the same in the linear regime, while sequence selection provides clear benefits as power increases. Moreover, sequence selection using the additive-multiplicative metric provides $0.07$ bits/2D extra gain compared to the energy-based metric. This result shows that the gains observed in <cit.> due to considering sign bits in sequence selection are realized using the practical metric proposed in this work.

AIR for
sequence selection with $N=64$ candidates and different selection metrics.

§ CONCLUSIONS

We introduced a sequence selection metric based on the first-order perturbative model, which takes into account the signs and energies of shaped symbols. Simulation results show a $0.15$ bits/2D AIR improvement by sequence selection using this metric compared to PAS without selection. The proposed metric can naturally account for inter-polarization and inter-channel NLIN effects. Finally, we suggest that the underlying additive-multiplicative NLIN model is effective for SNR performance prediction.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

journaltitleIEEE Transactions on communications
titleBandwidth efficient and rate-matched low-density parity-check coded modulation

booktitle2021 European Conference on Optical Communication (ECOC)
titleA sequence selection bound for the capacity of the nonlinear fiber channel

journaltitleJournal of Lightwave Technology
titleNew lower bounds on the capacity of optical fiber channels via optimized shaping and detection

journaltitleJournal of Lightwave Technology
titleList-encoding CCDM: A nonlinearity-tolerant shaper aided by energy dispersion index

journaltitleJournal of Lightwave Technology
titleTemporal energy analysis of symbol sequences for fiber nonlinear interference modelling via energy dispersion index

booktitle2022 European Conference on Optical Communication (ECOC)
titleNonlinearity tolerant shaping with sequence selection

journaltitleJournal of Lightwave Technology
titleProbabilistic amplitude shaping and nonlinearity tolerance: Analysis and sequence selection method

journaltitleJournal of Lightwave Technology
titleOn the nonlinear shaping gain with probabilistic shaping and carrier phase recovery

journaltitleJournal of Lightwave Technology
titleSequence-selection-based constellation shaping for nonlinear channels

booktitle2011 IEEE Information Theory Workshop
titleOperating LDPC codes with zero shaping gap
Encoding;Decoding;Parity check codes;Error probability;Error correction codes;Conferences

journaltitleJournal of Lightwave Technology
titleSequence Selection With Dispersion-Aware Metric for Long-Haul Transmission Systems

Optica Publishing Group

journaltitleOptics express
titleEGN model of non-linear fiber propagation

journaltitleJournal of Lightwave Technology
titleInter-channel nonlinear interference noise in WDM systems: Modeling and mitigation

Optica Publishing Group

journaltitleOptics express
titleMulti-stage perturbation theory for compensating intra-channel nonlinear impairments in fiber-optic links

journaltitleIEEE Transactions on Communications
titleLog-likelihood ratio calculation for pilot symbol assisted coded modulation schemes with residual phase noise

journaltitleJournal of Lightwave Technology
titleAchievable information rates for fiber optics: Applications and computations