# Fair Spatial Indexing: A paradigm for Group Spatial Fairness

Sina Shaham  Viterbi School of Engineering
University of Southern CaliforniaLos Angeles, CaliforniaUSA<EMAIL_ADDRESS>,
Gabriel Ghinita  College of Science and Engineering
Hamad Bin Khalifa University
Qatar Foundation, Doha, Qatar<EMAIL_ADDRESS>and  Cyrus Shahabi  Viterbi
School of Engineering
University of Southern CaliforniaLos Angeles, CaliforniaUSA<EMAIL_ADDRESS>
###### Abstract.

Machine learning (ML) is playing an increasing role in decision-making tasks
that directly affect individuals, e.g., loan approvals, or job applicant
screening. Significant concerns arise that, without special provisions,
individuals from under-privileged backgrounds may not get equitable access to
services and opportunities. Existing research studies fairness with respect to
protected attributes such as gender, race or income, but the impact of
location data on fairness has been largely overlooked. With the widespread
adoption of mobile apps, geospatial attributes are increasingly used in ML,
and their potential to introduce unfair bias is significant, given their high
correlation with protected attributes. We propose techniques to mitigate
location bias in machine learning. Specifically, we consider the issue of
miscalibration when dealing with geospatial attributes. We focus on spatial
group fairness and we propose a spatial indexing algorithm that accounts for
fairness. Our KD-tree inspired approach significantly improves fairness while
maintaining high learning accuracy, as shown by extensive experimental results
on real data.

##  1\. Introduction

Recent advances in machine learning (ML) led to its adoption in numerous
decision-making tasks that directly affect individuals, such as loan
evaluation or job application screening. Several studies (Pessach and Shmueli,
2022; Berk et al., 2021; Mhasawade et al., 2021) pointed out that ML
techniques may introduce bias with respect to protected attributes such as
race, gender, age or income. The last years witnessed the introduction of
fairness models and techniques that aim to ensure all individuals are treated
equitably, focusing especially on conventional protected attributes (like race
or gender). However, the impact of geospatial attributes on fairness has not
been extensively studied, even though location information is being
increasingly used in decision-making for novel tasks, such as recommendations,
advertising or ride-sharing. Conventional applications may also often rely on
location data, e.g. allocation of local government resources, or crime
prediction by law enforcement using geographical features. For example, the
Chicago Police Department releases monthly crime datasets (chi, 2015) and
classifies neighborhoods based on their crime risk level. Subsequently, the
risk level is used to determine vehicle and house insurance premiums, which
are increased to reflect the risk level, and in turn, result in additional
financial hardship for individuals from under-privileged groups.

Fairness for geospatial data is a challenging problem, due to two main
factors: (i) data are more complex than conventional protected attributes such
as gender or race, which are categorical and have only a few possible values;
and (ii) the correlation between locations and protected attributes may be
difficult to capture accurately, thus leading to hard-to-detect biases.

We consider the case of group fairness (Dwork and Ilvento, 2018), which
ensures no significant difference in outcomes occurs across distinct
population groups (e.g., females vs. males). In our setting, groups are
defined with respect to geospatial regions. The data domain is partitioned
into disjoint regions, and each of them represents a group. All individuals
whose locations belong to a certain region are assigned to the corresponding
group. In practice, a spatial group can correspond to a zip code, a
neighborhood, or a set of city blocks. Our objective is to support arbitrary
geospatial partitioning algorithms, which can handle the needs of applications
that require different levels of granularity in terms of location reporting.
Spatial indexing (Wang et al., 2020; Eldawy and Mokbel, 2015; Zhang et al.,
2016) is a common approach used for partitioning, and numerous techniques have
been proposed that partition the data domain according to varying criteria,
such as area, perimeter, data point count, etc. We build upon existing spatial
indexing techniques, and adapt the partition criteria to account for the
specific goals of fairness. By carefully combining geospatial and fairness
criteria in the partitioning strategies, one can obtain spatial fairness while
still preserving the useful spatial properties of indexing structures (e.g.,
fine-level clustering of the data).

Specifically, we consider a set of partitioning criteria that combines
physical proximity and calibration error. Calibration is an essential concept
in classification tasks which quantifies the quality of a classifier. Consider
a binary classification task, such as a loan approval process. Calibration
measures the difference between the observed and predicted probabilities of
any given point being labeled in the positive class. If one partitions the
data according to some protected attribute, then the expectation would be that
the probability should be the same across both groups (e.g., males and females
should have an equal chance, on aggregate, to be approved for a loan). If the
expected and actual probabilities are different, that represents a good
indication of unfair treatment.

Our proposed approach builds a hierarchical spatial index structure by using a
composite split metric, consisting of both geospatial criteria (e.g., compact
area) and miscalibration error. In doing so, it allows ML applications to
benefit from granular geospatial information, while at the same time ensuring
that no significant bias is present in the learning process.

(a) Neighborhoods Partitioning

(b) Generation of Classifier Scores

(c) Calibration of Neighborhoods

Figure 1. An example of the miscalibration problem with respect to
neighborhoods.

Our specific contributions include:

  * •

We identify and formulate the problem of spatial group fairness, an important
concept which ensures that geospatial information can be used reliably in a
classification task, without introducing, intentionally or not, biases against
individuals from underprivileged groups;

  * •

We propose a new metric to quantify unfairness with respect to geospatial
boundaries, called Expected Neighborhood Calibration Error (ENCE);

  * •

We propose a technique for fair spatial indexing that builds on KD-trees and
considers both geospatial and fairness criteria, by lowering miscalibration
and minimizing ENCE;

  * •

We perform an extensive experimental evaluation on real datasets, showing that
the proposed approach is effective in enforcing spatial group fairness while
maintaining data utility for classification tasks.

The rest of the paper is organized as follows: Section 2 provides background
and fundamental definitions. Section 3 reviews related work. We introduce the
proposed fair index construction technique in Section 4. Section 5 presents
the results of our empirical evaluation, followed by conclusions in Section 6.

##  2\. Background

###  2.1. System Architecture

We consider a binary classification task $T$ over a dataset $D$ of individuals
$u_{1},\,...,\,u_{|D|}$. The feature set recorded for $u_{i}$ is denoted by
$\boldsymbol{x_{i}}\in\mathbb{R}^{l}$, and its corresponding label by
$y_{i}\in\\{0,1\\}$. Each record consists of $l$ features, including an
attribute called neighborhood, which captures an individual’s location, and is
the main focus of our approach. The sets of all input data and labels are
denoted by $\mathcal{X}$ and $\mathcal{Y}$, respectively. A classifier $h(.)$
is trained over the input data resulting in $h(\mathcal{X})=(\hat{Y},\hat{S})$
where $\mathcal{\hat{Y}}=\\{\hat{y}_{1},...,\hat{y}_{|D|}\\}$ is the set of
predicted labels ($\hat{y}_{i}\in\\{0,1\\}$) and
$\mathcal{S}=\\{s_{1},...,s_{|D|}\\}$ is the set of confidence scores
($s_{i}\in[0,1]$) for each label.

The dataset’s neighborhood feature indicates the individual’s spatial group.
We assume the spatial data domain is split into a set of partitions of
arbitrary granularity. Without loss of generality, we consider a $U\times V$
grid overlaid on the map. The grid is selected such that its resolution
captures adequate spatial accuracy as required by application needs. A set of
neighborhoods is a non-overlapping partitioning of the map that covers the
entire space, with the $i^{th}$ neighborhood denoted by $N_{i}$, and the set
of neighborhoods denoted by $\mathcal{N}$.

Figure 1 illustrates the system overview. Figure 1a shows the map divided into
$4$ non-overlapping partitions $\mathcal{N}=\\{N_{1},N_{2},N_{3},N_{4}\\}$.
The neighborhood is recorded for each individual $u_{1},...,u_{11}$ together
with other features, and a classifier is trained over the data. The
classifier’s output is the confidence score for each entry which turns into a
class label by setting a threshold.

###  2.2. Fairness Metric

Our primary focus is to achieve spatial group fairness using as metric the
concept of calibration (Naeini et al., 2015; Pleiss et al., 2017), described
in the following.

In classification tasks, it is desirable to have scores indicating the
probability that a test data record belongs to a certain class. Probability
scores are especially important in ranking problems, where top candidates are
selected based on relative quantitative performance. Unfortunately, it is not
granted that confidence scores generated by a classifier can be interpreted as
probabilities. Consider a binary classifier that indicates an individual’s
chance of committing a crime after their release from jail (recidivism). If
two individuals $u_{1}$ and $u_{2}$ get confidence scores $0.4$ and $0.8$,
this cannot be directly interpreted as the likelihood of committing a crime by
$u_{2}$ being twice as high as for $u_{1}$. The model calibration aims to
alleviate precisely this shortcoming.

###### Definition 1.

(Calibration). An ML model is said to be calibrated if it produces calibrated
confidence scores. Formally, outcome score $R$ is calibrated if for all scores
$r$ in support of $R$ it holds that

(1) $P(y=1|R=r)=r$

This condition means that the set of all instances assigned a score value $r$
contains an $r$ fraction of positive instances. The metric is a group-level
metric. Suppose there exist $10$ people who have been assigned a confidence
score of $0.7$. In a well-calibrated model, we expect to have $7$ individuals
with positive labels among them. Thus, the probability of the whole group is
$0.7$ to be positive, but it does not indicate that every individual in the
group has this exact chance of receiving a positive label.

To measure the amount of miscalibration for the whole model or for an output
interval, the ratio of two key factors need to be calculated: expected
confidence scores and the expected value of true labels. Abiding by the
convention in (Naeini et al., 2015), we use functions $o(.)$ and $e(.)$ to
return the true fraction of positive instances and the expected value of
confidence scores, respectively. For example, the calibration of the model in
Figure 1b is computed as:

(2) $\dfrac{e(h)}{o(h)}=\dfrac{(\sum_{u\in D}\hat{p}_{u})/|D|}{(\sum_{u\in
D}y_{u})/|D|}=\dfrac{5.2/11}{7/11}\approx.742$

Perfect calibration is achieved when a specific ratio is equal to one. Ratios
that are above or below one are considered miscalibration cases. Another way
to measure the calibration error is by using the absolute value of the
difference between two values, denoted by $|e(h)-o(h)|$, with the ideal value
being zero. In this work, the second method is utilized, as it eliminates the
division by zero problem that may arise from neighborhoods with low
populations.

###  2.3. Problem Formulation

Even when a model is overall well-calibrated, it can still lead to unfair
treatment of individuals from different neighborhoods. In order to achieve
spatial group fairness, we must have a well-calibrated model with respect to
all neighborhoods. The existence of calibration error in a neighborhood can
result in classifier bias and lead to systematic unfairness against
individuals from that neighborhood (in Section 5, we support this claim with
real data measurements).

###### Definition 2.

(Calibration for Neighborhoods). Given neighborhood set
$\mathcal{N}=\\{N_{1},...,N_{t}\\}$, we say that the score $R$ is calibrated
in neighborhood $N_{i}$ if for all the scores $r$ in support of $R$ it holds
that

(3) $P(y=1|R=r,N=N_{i})=r,\;\;\;\;\;\;\forall i\in[1,t]$

The following equations can be used to measure the amount of miscalibration
with respect to neighborhood $N_{i}$,

(4) $\dfrac{e(h|N=N_{i})}{o(h|N=N_{i})}\;\;\;\text{ or
}\;\;\;|e(h|N=N_{i})-o(h|N=N_{i})|$

Going back to the example in Figure 1d, the calibration amount for
neighborhoods $N_{1}$ to $N_{4}$ is visualized on a plot. Neighborhood $N_{4}$
is well-calibrated, whereas the others suffer from miscalibration.

Figure 2. Overview of the proposed mitigation techniques.

###### Problem 1.

Given m binary classification tasks $T_{1},T_{2},...,T_{m}$, we seek to
partition the space into continuous non-overlapping neighborhoods such that
for each decision-making task, the trained model is well-calibrated for all
neighborhoods.

###  2.4. Evaluation Metrics

A commonly used metric to evaluate the calibration of a model is Expected
Calibration Error (ECE) (Guo et al., 2017). The goal of ECE (detailed in
Appendix A.1) is to understand the validity of output confidence scores.
However, our focus is on identifying the calibration error imposed on
different neighborhoods. Therefore, we extend ECE and propose the Expected
Neighborhood Calibration Error (ENCE) that captures the calibration
performance over all neighborhoods.

###### Definition 3.

(Expected Neighborhood Calibration Error). Given $t$ non-overlapping
geospatial regions $\mathcal{N}=\\{N_{1},...,N_{t}\\}$ and a classifier $h$
trained over data located in these neighborhoods, the ENCE metric is
calculated as:

(5)
$\displaystyle\text{ENCE}=\sum_{i=1}^{t}\dfrac{|N_{i}|}{|D|}|\text{o}(N_{i})-e(N_{i})|$

where $o(N_{i})$ and $e(N_{i})$ return the true fraction of positive instances
and the expected value of confidence scores for instances in $N_{i}$111Symbol
$|.|$ denotes absolute value..

Table 1. Summary of Notations. Symbol |  Description
---|---
$k$ |  Number of features
$D=\\{u_{1},...,u_{|D|}\\}$ |  Dataset of individuals
$(x_{i},y_{i})$ |  (Set of features, true label) for $u_{i}$
$D=[\mathcal{X},\mathcal{Y}]$ |  Dataset with user features and labels
$\mathcal{\hat{Y}}\texttt{=}\\{\hat{y}_{1},..,\hat{y}_{|D|}\\}$ |  Set of predicted labels
$\mathcal{S}=\\{s_{1},...,s_{|D|}\\}$ |  Set of confidence scores
$\mathcal{N}=\\{N_{1},...,N_{t}\\}$ |  Set of neighborhoods
$U\times V$ |  Base grid resolution
$T$ |  Binary classification task
$m$ |  Number of binary classification tasks
$t$ |  Number of neighborhoods
$t_{h}$ |  Tree height

##  3\. Related Work

Fairness Notions. There exist two broad categories of fairness notions
(Mehrabi et al., 2021; Caton and Haas, 2020): individual fairness and group
fairness. In group fairness, individuals are divided into groups according to
a protected attribute, and a decision is said to be fair if it leads to a
desired statistical measure across groups. Some prominent group fairness
metrics are calibration (Pleiss et al., 2017), statistical parity (Kusner et
al., 2017)(Dwork et al., 2012), equalized odds (Hardt et al., 2016), treatment
equality (Berk et al., 2021), and test fairness (Chouldechova, 2017).
Individual fairness notions focus on treating similar individuals the same
way. Similarity may be defined with respect to a particular task (Dwork et
al., 2012; Joseph et al., 2016).

Spatial Fairness. Neighborhoods or individual locations are commonly used
features for decision-making in government agencies, banks, etc. Unfairness
may arise in tasks such as mortgage lending (Lee and Floridi, 2021), job
recruitment (Faliagka et al., 2012), admission to schools (Benabbou et al.,
2019), and crime risk prediction (Wang et al., 2022). In (Wang et al., 2022),
recidivism prediction models constructed using data from one location tend to
perform poorly when they are used to predict recidivism in another location.
The authors in (Riederer and Chaintreau, 2017) formulate a loss function for
individual fairness in social media and location-based advertisements. Pujol
et al. (Pujol and Machanavajjhala, 2021) demonstrate the unequal impact of
differential privacy on neighborhoods. Several attempts have been made to
apply fairness notions for clustering datapoints in the Cartesian space. The
notion in (Kleindessner et al., 2020) defines clustering conducted for a point
as fair if the average distance to the points in its own cluster is not
greater than the average distance to the points in any other cluster. The
authors in (Mahabadi and Vakilian, 2020) focus on defining individual fairness
for $k$-median and $k$-means algorithms. Clustering is defined to be
individually fair if every point expects to have a cluster center within a
particular radius.

Unfairness Mitigation techniques can be categorized into three broad groups:
pre-processing, in-processing, and post-processing. Pre-processing algorithms
achieve fairness by focusing on the classifier’s input data. Some well-known
techniques include suppression of sensitive attributes, change of labels,
reweighting, representation learning, and sampling (Kamiran and Calders,
2012). In-processing techniques achieve fairness during training by adding new
terms to the loss function (Kamishima et al., 2012) or including more
constraints in the optimization. Post-processing techniques sacrifice the
utility of output confidence scores and align them with the fairness objective
(Platt et al., 1999).

(a) Initial execution of classifier.

(b) Re-districting the map based on fairness objective.

(c) Training classifier based on re-districted neighborhoods.

Figure 3. Overview of Fair KD-tree algorithm.

##  4\. Spatial Fairness through Indexing

We introduce several algorithms that achieve group spatial fairness by
constructing spatial index structures in a way that takes into account
fairness considerations when performing data domain splits. We choose KD-trees
as a starting point for our solutions, due to their ability to adapt to data
density, and their property of covering the entire data domain (as opposed to
structures like R-trees that may leave gaps within the domain).

Figure 2 provides an overview of the proposed solution. Our input consists of
a base grid with an arbitrarily-fine granularity overlaid on the map, the
attributes/features of individuals in the data, and their classification
labels. The attribute set includes individual location, represented as the
grid cell enclosing the individual. We propose a suite of three alternative
algorithms for fairness, which are applied in the pre-processing phase of the
ML pipeline and lead to the generation of new neighborhood boundaries. Once
spatial partitioning is completed, the location attribute of each individual
is updated, and classification is performed again.

The proposed algorithms are:

  * •

Fair KD-tree is our primary algorithm and it re-districts spatial
neighborhoods based on an initial classification of data over a base grid.
Fair KD-tree can be applied to a single classification task.

  * •

Iterative Fair KD-tree improves upon Fair KD-tree by refining the initial ML
scores at every height of the index structure. It incurs higher computational
complexity but provides improved fairness.

  * •

Multi-Objective Fair KD-tree enables Fair KD-trees for multiple classification
tasks. It leads to the generation of neighborhoods that fairly represent
spatial groups for multiple objectives.

Next, we prove an important result that applies to all proposed algorithms,
which states that any non-overlapping partitioning of the location domain has
a weighted average calibration greater or equal to the overall model
calibration. The proofs of all theorems are provided in Appendix A.

###### Theorem 1.

For a given model $h$ and a complete non-overlapping partitioning of the space
$\mathcal{N}=\\{N_{1},N_{2},...,N_{t}\\}$, ENCE is lower-bounded by the
overall calibration of the model.

A broader statement can also be proven, showing that further partitioning
leads to poorer ENCE performance.

###### Theorem 2.

Consider a binary classifier $h$ and two complete non-overlapping partitioning
of the space $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$. If $\mathcal{N}_{2}$ is
a sub-partitioning of $\mathcal{N}_{1}$, then:

(6) $\text{ENCE}(N_{1})\leq\text{ENCE}(N_{2})$

Neighborhood set $\mathcal{N}_{2}$ is a sub-partitioning of $\mathcal{N}_{1}$
if for every $N_{i}\in\mathcal{N}_{1}$, there exists a set of neighborhoods in
$\mathcal{N}_{2}$ such that their union is $N_{i}$.

Algorithm 1 Fair KD-tree

1: Input:  Grid ($U\times V$), Features ($\mathcal{X}$), Labels
($\mathcal{Y}$), Height ($t_{h}$).

2: Output: New neighborhoods and updated feature set

3:function FairKDtree($N,\mathcal{X},\mathcal{Y},\mathcal{S},t_{h}$)

4: if $t_{h}=0$ then

5: $\mathcal{N}\leftarrow\mathcal{N}+N$

6: return $True$

7: $axis\leftarrow\,t_{h}$ mod 2

8: $L_{k^{*}},\,R_{k^{*}}\leftarrow$
SplitNeighborhood$(N,\mathcal{Y},\mathcal{S},axis)$

9: Run FairKDtree($L_{k^{*}},\mathcal{X},\mathcal{Y},\mathcal{S},t_{h}-1$)

10: Run FairKDtree($R_{k^{*}},\mathcal{X},\mathcal{Y},\mathcal{S},t_{h}-1$)

11:$N_{1}\leftarrow$ Grid

12:Global $\mathcal{N}\leftarrow\\{\\}$

13:Set all neighborhoods in $\mathcal{X}$ to $N_{1}$

14:Scores ($\mathcal{S}$) $\leftarrow$ Train ML model on $\mathcal{X}$ and
$\mathcal{Y}$

15:Neighborhoods ($\mathcal{N})\leftarrow$ Run
$FairKDtree(N_{1},\mathcal{X},\mathcal{Y},\mathcal{S},t_{h})$

16:Update neighborhoods in $\mathcal{X}$

17:return $\mathcal{N},\,\mathcal{X}$

Algorithm 2 Split Neighborhood

1: Input:  Neighborhood ($N$), Confidence Scores ($\mathcal{S}$), Labels
($\mathcal{Y}$), Axis.

2: Output: Non-overlapping split of $N$ into two neighborhoods

3:function SplitNeighborhood($N,\mathcal{S},\mathcal{Y},axis$)

4: if $axis=1$ then

5: $N\leftarrow$ Transpose of $N$

6: $U^{\prime}\times V^{\prime}\leftarrow$ Dimensions of $N$

7: for $k=1...U^{\prime}$ do

8: $L_{k}\leftarrow$ Neighborhoods in $1...k$

9: $R_{k}\leftarrow$ Neighborhoods in $k+1...U$

10: $z_{i}\leftarrow$ Compute Equation (9) for $L_{k}$ and $R_{k}$

11: $k^{*}\leftarrow$ $\arg\min_{k}\;\;z_{k}$

12: return $L_{k^{*}}$, $R_{k^{*}}$

###  4.1. Fair KD-tree

We build a KD-tree index that partitions the space into non-overlapping
regions according to a split metric that takes into account the miscalibration
metric within the regions resulting after each split. Figure 3 illustrates
this approach, which consists of three steps. Algorithm 1 presents the
pseudocode of the approach.

Step 1. The base grid is used as input, where the location of each individual
is represented by the identifier of their enclosing grid cell. This location
attribute, alongside other features, is used as input to an ML classifier $h$
for training. The classifier’s output is a set of confidence scores
$\mathcal{S}$, as illustrated in Figure 3a. Once confidence scores are
generated, the true fraction of positive instances and the expected value of
predicted confidence scores of the model with respect to neighborhoods can be
calculated as follows:

(7) $e(h|N=N_{i})=\dfrac{1}{|N_{i}|}(\sum_{u\in
N_{i}}s_{u})\;\;\;\;\;\;\forall i\in[1,t]$ (8)
$o(h|N=N_{i})=\dfrac{1}{|N_{i}|}(\sum_{u\in N_{i}}y_{u})\;\;\;\;\;\;\forall
i\in[1,t]$

where $t$ is the number of neighborhoods.

Algorithm 3 Iterative Fair KD-tree

1: Input:  Grid ($U\times V$), Features ($\mathcal{X}$), Labels
($\mathcal{Y}$), Height ($t_{h}$).

2: Output: New neighborhoods and updated feature set

3:$N_{1}\leftarrow$ Grid

4:Set all neighborhoods in $\mathcal{X}$ to $N_{1}$

5:$\mathcal{N}\leftarrow\\{N_{1}\\}$

6:while $t_{h}>0$ do

7: Scores ($\mathcal{S}$) $\leftarrow$ Train ML model on $\mathcal{X}$ and
$\mathcal{Y}$

8: $\mathcal{N_{\text{new}}}\leftarrow\\{\\}$

9: for $N_{i}\;\text{in}\;\mathcal{N}$ do

10: $L,R\leftarrow$
SplitNeighborhood$(N_{i},\mathcal{S},\mathcal{Y},t_{h}\%2)$

11: $\mathcal{N_{\text{new}}}\leftarrow\mathcal{N_{\text{new}}}+{L,R}$

12: $\mathcal{N}\leftarrow\mathcal{N_{\text{new}}}$

13: Update neighborhoods in $\mathcal{X}$ based on $\mathcal{N}$

14: $t_{h}\leftarrow t_{h}-1$

15:return $\mathcal{N},\,\mathcal{X}$

Step 2. This step performs the actual partitioning, by customizing the KD-tree
split algorithm with a novel objective function. KD-trees are binary trees
where a region is split into two parts, typically according to the median
value of the coordinate across one of the dimensions (latitude or longitude).
Instead, we select the division index that minimizes fairness metric, i.e.,
ENCE miscalibration. Confidence scores and labels resulted from the previous
training step are used as input for the split point decision. For a given tree
node, assume the corresponding partition covers $U^{\prime}\times V^{\prime}$
cells of the entire $U\times V$ grid. Without loss of generality, we consider
partitioning on the horizontal axis (i.e., row-wise). The aim is to find an
index $k$ which groups rows $1$ to $k$ into one node and rows $k+1$ to
$U^{\prime}$ into another, such that the fairness objective is minimized. Let
$L_{k}$ and $R_{k}$ denote the left and right regions generated by splitting
on index $k$. The fairness objective for index $k$ is:

(9)
$z_{k}=\big{|}\;|L_{k}|\times|o(L_{k})-e(L_{k})|-|R_{k}|\times|o(R_{k})-e(R_{k})\;|\big{|}$

In the above equation, $|L_{k}|$ and $|R_{k}|$ return the number of data
entries in the left and right regions, respectively. The intuition behind the
objective function is to minimize the model miscalibration difference as we
heuristically move forward. Two key points about the above function are: (i)
the formulation of calibration is used in linear format due to the possibility
of a zero denominator, and (ii) the calibration values are weighted by their
corresponding regions’ cardinalities. The optimal index $k^{*}$ is selected
as:

(10) $k^{*}=\arg\min_{k}\;\;z_{k}\;\;\;$

Step 3. On completion of the fair KD-tree algorithm, the index leaf set
provides a non-overlapping partitioning of the map. In the algorithm’s final
step, the neighborhood of each individual in the dataset is updated according
to the leaf set and used for training.

The Fair KD-tree pseudocode is provided in Algorithms 1 and 2. The latter
returns the split point based on the fairness objective, and it is being
called several times in Algorithm 1. This function will also be used within
the Iterative KD-tree algorithm.

###### Theorem 3.

For a given dataset $D$, the required number of neighborhoods $t$ and the
model $h$, the computational complexity of Fair KD-tree is
$\mathcal{O}(|D|\times\lceil\log(t)\rceil)+\mathcal{O}(h)$.

Figure 4. Overview of Iterative Fair KD-tree algorithm. Figure 5. Aggregation
in Multi-Objective Fair KD-tree.

###  4.2. Iterative Fair KD-tree

One drawback of the Fair KD-tree algorithm is its sensitivity to the initial
execution of the model, which uses the baseline grid to generate confidence
scores. Even though the space is recursively partitioned following the initial
steps, the scores are not re-computed until the index construction is
finalized. The iterative fair KD-tree addresses this limitation by re-training
the model and computing updated confidence scores after each split (i.e., at
each level of the tree). A refined version of ML scores is used at every
height of the tree, leading to a more fair redistricting of the map.

Similar to the Fair KD-tree algorithm, the baseline grid is initially used,
and all grid cells are considered to be in the same neighborhood (i.e., a
single spatial group covering the entire domain). The algorithm is implemented
in $t_{h}$ iterations with the root node corresponding to the initial point
(entire domain). As opposed to the Fair KD-tree algorithm that follows Depth
First Search (DFS) recursion, the Iterative Fair KD-tree algorithm is based on
Breadth First Search (BFS) traversal. Therefore, all nodes in the given height
$i-1$ are completed before moving forward to the height $i$. Suppose we are in
the $i^{th}$ level of the tree, and all nodes at that level are generated.
Note that, the set of nodes at the same height represents a non-overlapping
partitioning of the grid. The algorithm continues by updating the
neighborhoods at height $i$ based on the $i-1$ level partitioning. Then, the
updated dataset is used to train a new model, thus updating confidence scores
for each individual.

Algorithm 3 presents the Iterative Fair KD-tree algorithm. Let $\mathcal{N}$
denote the set of all neighborhoods at level $i$ of the tree. For each
neighborhood $N_{i}\in\mathcal{N}$, Iterative Fair KD-tree splits the region
$N_{i}$ by calling the $SplitNeighborhood$ function in Algorithm 2. The split
is done on the $x$-axis if $i$ is even and on the $y$-axis otherwise.

The algorithm provides a more effective way of determining a fair neighborhood
partitioning by re-training the model at every tree level, but incurs higher
computation complexity.

###### Theorem 4.

For a given dataset $D$, the required number of neighborhoods $t$ and the
model $h$, the computational complexity of Iterative Fair KD-tree is
$\mathcal{O}(|D|\times\lceil\log(t)\rceil)+\lceil\log(t)\rceil\times\mathcal{O}(h)$.

###  4.3. Multi-Objective Fair KD-tree

So far, we focused on achieving a fair representation of space given a single
classification task. In practice, applications may dictate multiple
classification objectives. For example, a set of neighborhoods that are fairly
represented in a city budget allocation task may not necessarily result in a
fair representation of a map for deriving car insurance premia. Next, we show
how Fair KD-tree can be extended to incorporate multi-objective decision-
making tasks.

We devise an alternative method to compute initial scores in Line 10 of
Algorithm 2, which can then be called as part of Fair KD-tree in Algorithm 1.
A separate classifier is trained over each task to incorporate all
classification objectives. Let $h_{i}$ be the $i^{th}$ classifier trained over
$D$ and label set $\mathcal{Y}_{i}$ representing the task $T_{i}$. The output
of the classifier is denoted by
$\mathcal{S}_{i}=\\{s_{1}^{i},...,s_{|D|}^{i}\\}$, where in $s_{j}^{i}$, the
superscript identifies the set $\mathcal{S}_{i}$ and the subscript indicates
individual $u_{j}$. Once confidence scores for all models are generated, an
auxiliary vector is constructed as follows:

(11) $\displaystyle\boldsymbol{v}_{i}$
$\displaystyle=\begin{bmatrix}s_{1}^{i}-y_{1}^{i}\\\ s_{2}^{i}-y_{2}^{i}\\\
\vdots\\\ s_{|D|}^{i}-y_{|D|}^{i}\end{bmatrix},\;\;\;\;\;\;\;\forall
i\in[1...t]$

To facilitate task prioritization, hyper-parameters
$\alpha_{1},...,\alpha_{m}$ are introduced such that
$\sum_{i\texttt{=}1}^{m}\alpha_{i}=1$ and $0\leq\alpha_{i}\leq 1$. Coefficient
$\alpha_{i}$ indicates the significance of classification $T_{i}$. The
complete vector used for computing the partitioning is then calculated as,

(12)
$\boldsymbol{v}_{tot}=\sum_{i\texttt{=}1}^{m}\alpha_{i}\boldsymbol{v}_{i}=\begin{bmatrix}\sum_{i\texttt{=}1}^{m}\alpha_{i}(s_{1}^{i}-y_{1}^{i})\\\
\sum_{i\texttt{=}1}^{m}\alpha_{i}(s_{2}^{i}-y_{2}^{i})\\\ \vdots\\\
\sum_{i\texttt{=}1}^{m}\alpha_{i}(s_{|D|}^{i}-y_{|D|}^{i})\end{bmatrix}$

In the above formulation, each row corresponds to a unique individual and
captures its role in all classification tasks. Let
$\boldsymbol{v}_{tot}[u_{i}]$ denote the entry corresponding to $u_{i}$ in
$\boldsymbol{v}_{tot}$. Then the classification objective function in Eq. 9 is
returned by:

(13)
$z_{k}=\big{|}\;|L_{k}|\times|\sum_{u_{i}\texttt{=}L_{k}}\boldsymbol{v}_{tot}[u_{i}]|\;-\;|R_{k}|\times|\sum_{u_{i}\texttt{=}R_{k}}\boldsymbol{v}_{tot}[u_{i}]\;|\big{|}$

and the optimal split point is selected as,

(14) $k^{*}=\arg\min_{k}\;\;z_{k}\;\;\;$

Vector aggregation is illustrated in Figure 5.

###### Theorem 5.

For a given dataset $D$, the required number of neighborhoods $t$ and $m$
classification tasks modelled by $h_{1},...,h_{m}$, computational complexity
of Multi-Objective Fair KD-tree is
$\mathcal{O}(|D|\times\lceil\log(t)\rceil)+\sum_{i\texttt{=}1}^{m}\mathcal{O}(h_{i})$.

##  5\. Experimental Evaluation

(a) EdGap (Los Angeles) (b) EdGap (Los Angeles) (c) EdGap (Houston) (d) EdGap
(Houston)

Figure 6. Evidence of Model Disparity on Geospatial Neighborhoods.

(a) Los Angeles (Logistic Regression) (b) Los Angeles (Decision Tree) (c) Los
Angeles (Naive Bayes) (d) Houston (Logistic Regression)

(e) Houston (Decision Tree) (f) Houston (Naive Bayes)

Figure 7. Performance Evaluation with respect to ENCE.

###  5.1. Experimental Setup

We use two real-world datasets provided by EdGap (VanWylen, [n.d.]) with
$1153$ and $966$ data records respectively, containing socio-economic features
(e.g., household income and family structure) of US high school students in
Los Angeles, CA and Houston, Texas. Consistent with (Fischer, 2021), we use
two features of average American College Testing (ACT) and the percentage of
family employment as indicators to generate classification labels. The
geospatial coordinates of schools are derived by linking their identification
number to data provided by the National Center for Education Statistics (edu,
[n.d.]).

We evaluate the performance of our proposed approaches (Fair KD-tree,
Iterative Fair KD-tree, and multi-objective Fair KD-tree) in comparison with
three benchmarks: (i) Median KD-tree, the standard method for KD-tree
partitioning; (ii) Reweighting over grid – an adaptation of the re-weighting
approach used in in (Kamiran and Calders, 2012) and deployed in geospatial
tools such as IBM AI Fairness 360; and (iii) we use zip code partitioning as a
baseline partitioning. All experiments are implemented in Python and executed
on a $3.40$GHz core-i7 Intel processor with 16GB RAM.

(a) Model Accuracy (Los Angeles) (b) Training Miscalibration (Los Angeles) (c)
Test Miscalibration (Los Angeles) (d) Model Accuracy (Houston)

(e) Training Miscalibration (Houston) (f) Test Miscalibration (Houston)

Figure 8. Performance Evaluation with respect to other indicators.

###  5.2. Evidence for Disparity in Geospatial ML

First, we perform a set of experiments to measure the amount of bias that
occurs when performing ML on geospatial datasets without any mitigating
factors. Figure 6 captures the existing disparity with respect to widely
accepted metrics of calibration error and ECE with $15$ bins. We use the ratio
representation of calibration in which a closer value to $1$ represents higher
calibration levels. Two logistic regression models are trained over
neighborhoods in Los Angeles and Houston areas. The labels are generated by
setting a threshold of $22$ on the average ACT performance of students in
schools. The overall performance of models in terms of training and test
calibration in Los Angeles and Texas are $(1.005,\,1.033)$ and
$(0.999,\,0.958)$, respectively. Both training and test calibration are close
to $1$ overall, which in a naive interpretation would indicate all schools are
treated fairly. However, this is not the case when computing the same metrics
on a per-neighborhood basis. Figure 6 shows miscaibration error for the top
$10$ most populated zip codes. Despite the model’s acceptable outcomes
overall, many individual neighborhoods suffer from severe calibration errors,
leading to unfair outcomes in the most populated regions, which are often home
to the under-privileged communities.

(a) Median KD-tree (Los Angeles) (b) Fair KD-tree (Los Angeles) (c) Iterative
Fair KD-tree (Los Angeles) (d) Median KD-tree (Houston)

(e) Fair KD-tree (Houston) (f) Iterative Fair KD-tree (Houston)

Figure 9. Impact of features on decision-making.

###  5.3. Mitigation Algorithms

####  5.3.1. Evaluation w.r.t. ENCE Metric.

ENCE is our primary evaluation metric that captures the amount of calibration
error over neighborhoods. Recall that Fair KD-tree and its extension Iterative
Fair KD-tree can work for any given classification ML model. We apply
algorithms for Logistic Regression, Decision Tree, and Naive Bayes classifiers
to ensure diversity in models. We focus on student SAT performance following
the prior work in (Fischer, 2021) by setting the threshold to $22$ for label
generation. Figure 7 provides the results in Los Angeles and Houston on the
EdGap dataset. The $x$-axis denotes the tree’s height used in the algorithm.
Having a higher height indicates a finer-grained partitioning. The $y$-axis is
log-scale.

Figure 7 demonstrates that both Fair KD-tree and Iterative Fair KD-tree
outperform benchmarks by a significant margin. The improvement percentage
increases as the number of neighborhoods increase, which is an advantage of
our techniques, since finer spatial granularity is beneficial for most
analysis tasks. The intuition behind this trend lies in the overall
calibration of the model: given that the trained model is well-calibrated
overall, dividing the space into a smaller number of neighborhoods is expected
to achieve a calibration error closer to the overall model. This result
supports Theorem 1, stating that ENCE is lower-bounded by the number of
neighborhoods. Iterative Fair KD-tree behaves better, as confidence scores are
updated on every tree level. The improvement achieved compared to Fair KD-
trees comes at the expense of higher computational complexity. On average Fair
KD-tree achieves $45\%$ better performance in terms of computational
complexity. The time taken for Fair KD-tree with 10 levels is $102$ seconds,
versus $189$ seconds for the iterative version.

(a) Height$=4$, Los Angeles  (b) Height$=6$, Los Angeles  (c) Height$=8$, Los
Angeles  (d) Height$=10$, Los Angeles

(e) Height$=4$, Houston  (f) Height$=6$, Houston  (g) Height$=8$, Houston  (h)
Height$=10$, Houston

Figure 10. Performance evaluation of multi-objective algorithm.

####  5.3.2. Evaluation w.r.t. other Indicators.

In Figure 8 we evaluate fairness with respect to three other key indicators:
model accuracy, training miscalibration, and test miscalibration. We focus on
logistic regression, one of the most widely adopted classification units. The
accuracy of all algorithms follows a similar pattern and increases at higher
tree heights. This is expected, as more geospatial information can be
extracted at finer granularities.

Figure 8b shows training miscalibration calculated for the overall model (a
lower value of calibration error indicates better performance). Our proposed
algorithms have comparable calibration errors to benchmarks, even though their
fairness is far superior. To understand better underlying trends, Figure 9
provides the heatmap for the tree-based algorithms over $10$ different tree
heights. The amount of contribution each feature has on decision-masking is
captured using a different color code. One observation is that the model
shifts focus to different features based on the height. Such sudden changes
can impact the generated confidence scores and, subsequently, the overall
calibration of the model. As an example, consider the median KD-tree algorithm
at the height of $8$ in Los Angeles (Figure 8b): there is a sudden drop in
training calibration, which can be explained by looking at the corresponding
heat map in Figure 9a. At the height of $8$, the influential features on
decision-making consist of different elements than the heights $4$, $6$, and
$10$, leading to the fluctuation in the model calibration.

###  5.4. Performance of multi-objective approach.

When multi-objective criteria are used, we need a methodology to unify the
geospatial boundaries generated by each task. Our proposed multi-objective
fair partitioning predicated on Fair KD-trees addresses exactly this problem.
In our experiments, we use the two criteria of ACT scores and employment
percentage of families as the two objectives used for partitioning. These
features are separated from the training dataset in the pre-processing phase
and are used to generate labels. The threshold for ACT is selected as before
($22$), and the threshold for label generation based on family employment is
set to $10$ percent.

Figure 10 presents the results of the Multi-Objective Fair KD-tree (to
simplify chart notation, we use the ‘Fair KD-tree’ label). We choose a
$\alpha$ value of $0.5$ to give equal weight to both objectives. We emphasize
that, the output of the Multi-Objective Fair KD-tree is a single non-
overlapping partitioning of the space representing neighborhoods. Once the
neighborhoods are generated, we show the performance with respect to each
objective function, i.e., ACT and employment. The first row of the figure
shows the performance for varying tree heights in Los Angeles, and the second
row corresponds to Houston. The proposed algorithm improves fairness for both
objective functions. The margin of improvement increases as the height of the
tree increases.

##  6\. Conclusion

We proposed an indexing-based technique that achieves spatial group fairness
in machine learning. Our technique performs a partitioning of the data domain
in a way takes into account not only geographical features, but also
calibration error. Extensive evaluation results on real data show that the
proposed technique is effective in reducing unfairness when training on
location attributes, and also preserves data utility. In future work, we plan
to further investigate custom split metrics for fairness-aware spatial
indexing that take into account data distribution characteristics. We will
also investigate alternative indexing structures, such as R+ trees, that
completely cover the data domain and provide superior clustering properties.

## References

  * (1)
  * edu ([n.d.]) [n.d.].  National Center for Education Statistics.  https://nces.ed.gov/
  * chi (2015) 2015\.  Chicago Crime Dataset.  https://data.cityofchicago.org/Public-Safety/Crimes-2015/vwwp-7yr9
  * Benabbou et al. (2019) Nawal Benabbou, Mithun Chakraborty, and Yair Zick. 2019\.  Fairness and diversity in public resource allocation problems.  _Bulletin of the Technical Committee on Data Engineering_ (2019).
  * Berk et al. (2021) Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. 2021.  Fairness in criminal justice risk assessments: The state of the art.  _Sociological Methods & Research_ 50, 1 (2021), 3–44.
  * Caton and Haas (2020) Simon Caton and Christian Haas. 2020.  Fairness in machine learning: A survey.  _arXiv preprint arXiv:2010.04053_ (2020).
  * Chouldechova (2017) Alexandra Chouldechova. 2017\.  Fair prediction with disparate impact: A study of bias in recidivism prediction instruments.  _Big data_ 5, 2 (2017), 153–163.
  * Dwork et al. (2012) Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012.  Fairness through awareness. In _Proceedings of the 3rd innovations in theoretical computer science conference_. 214–226.
  * Dwork and Ilvento (2018) Cynthia Dwork and Christina Ilvento. 2018.  Individual fairness under composition.  _Proceedings of Fairness, Accountability, Transparency in Machine Learning_ (2018).
  * Eldawy and Mokbel (2015) Ahmed Eldawy and Mohamed F Mokbel. 2015.  Spatialhadoop: A mapreduce framework for spatial data. In _2015 IEEE 31st international conference on Data Engineering_. IEEE, 1352–1363.
  * Faliagka et al. (2012) Evanthia Faliagka, Athanasios Tsakalidis, and Giannis Tzimas. 2012.  An integrated e-recruitment system for automated personality mining and applicant ranking.  _Internet research_ (2012).
  * Fischer (2021) Brian Fischer. 2021\.  data science methodology and applications.  https://bookdown.org/bfischer_su/bookdown-demo/edgap.html
  * Guo et al. (2017) Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. 2017\.  On calibration of modern neural networks. In _International conference on machine learning_. PMLR, 1321–1330.
  * Hardt et al. (2016) Moritz Hardt, Eric Price, and Nati Srebro. 2016.  Equality of opportunity in supervised learning.  _Advances in neural information processing systems_ 29 (2016), 3315–3323.
  * Joseph et al. (2016) Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth. 2016.  Fairness in learning: Classic and contextual bandits.  _Advances in neural information processing systems_ 29 (2016).
  * Kamiran and Calders (2012) Faisal Kamiran and Toon Calders. 2012.  Data preprocessing techniques for classification without discrimination.  _Knowledge and information systems_ 33, 1 (2012), 1–33.
  * Kamishima et al. (2012) Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma. 2012.  Fairness-aware classifier with prejudice remover regularizer. In _Joint European conference on machine learning and knowledge discovery in databases_. Springer, 35–50.
  * Kleindessner et al. (2020) Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. 2020.  A Notion of Individual Fairness for Clustering.  _arXiv preprint arXiv:2006.04960_ (2020).
  * Kusner et al. (2017) Matt J Kusner, Joshua R Loftus, Chris Russell, and Ricardo Silva. 2017.  Counterfactual fairness.  _arXiv preprint arXiv:1703.06856_ (2017).
  * Lee and Floridi (2021) Michelle Seng Ah Lee and Luciano Floridi. 2021.  Algorithmic fairness in mortgage lending: from absolute conditions to relational trade-offs.  _Minds and Machines_ 31, 1 (2021), 165–191.
  * Mahabadi and Vakilian (2020) Sepideh Mahabadi and Ali Vakilian. 2020.  Individual fairness for k-clustering. In _International Conference on Machine Learning_. PMLR, 6586–6596.
  * Mehrabi et al. (2021) Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. 2021\.  A survey on bias and fairness in machine learning.  _ACM Computing Surveys (CSUR)_ 54, 6 (2021), 1–35.
  * Mhasawade et al. (2021) Vishwali Mhasawade, Yuan Zhao, and Rumi Chunara. 2021\.  Machine learning and algorithmic fairness in public and population health.  _Nature Machine Intelligence_ 3, 8 (2021), 659–666.
  * Naeini et al. (2015) Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. 2015\.  Obtaining well calibrated probabilities using bayesian binning. In _Twenty-Ninth AAAI Conference on Artificial Intelligence_.
  * Pessach and Shmueli (2022) Dana Pessach and Erez Shmueli. 2022.  A review on fairness in machine learning.  _ACM Computing Surveys (CSUR)_ 55, 3 (2022), 1–44.
  * Platt et al. (1999) John Platt et al. 1999\.  Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods.  _Advances in large margin classifiers_ 10, 3 (1999), 61–74.
  * Pleiss et al. (2017) Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. 2017.  On fairness and calibration.  _Advances in neural information processing systems_ 30 (2017).
  * Pujol and Machanavajjhala (2021) David Pujol and Ashwin Machanavajjhala. 2021.  Equity and Privacy: More Than Just a Tradeoff.  _IEEE Security & Privacy_ 19, 6 (2021), 93–97.
  * Riederer and Chaintreau (2017) Christopher Riederer and Augustin Chaintreau. 2017.  The Price of Fairness in Location Based Advertising.  (2017).
  * VanWylen ([n.d.]) Peter VanWylen. [n.d.].  Visualizing the education gap.  https://www.edgap.org/#6/37.886/-97.000
  * Wang et al. (2022) Caroline Wang, Bin Han, Bhrij Patel, and Cynthia Rudin. 2022\.  In pursuit of interpretable, fair and accurate machine learning for criminal recidivism prediction.  _Journal of Quantitative Criminology_ (2022), 1–63.
  * Wang et al. (2020) Yongzhi Wang, Hua Lv, and Yuqing Ma. 2020.  Geological tetrahedral model-oriented hybrid spatial indexing structure based on Octree and 3D R*-tree.  _Arabian Journal of Geosciences_ 13 (2020), 1–11.
  * Zhang et al. (2016) Chengyuan Zhang, Ying Zhang, Wenjie Zhang, and Xuemin Lin. 2016\.  Inverted linear quadtree: Efficient top k spatial keyword search.  _IEEE Transactions on Knowledge and Data Engineering_ 28, 7 (2016), 1706–1721.

##  Appendix A Appendix

###  A.1. Expected Calibration Error

Expected Calibration Error (ECE) is one of the primary metrics used to
quantify calibration in ML. According to this metric, the output confidence
scores are sorted and partitioned into $M$ bins denoted by
$B_{1},\,....,\,B_{m}$. The associated score for each data instance lies
within one of the bins. The ECE metric is then calculated over bins as
follows:

(15)
$\displaystyle\text{ECE}=\sum_{m=1}^{M}\dfrac{B_{m}}{n}|\text{o}(B_{m})-e(B_{m})|$

###  A.2. Theorem Proofs

Proof of Theorem 1

The proof follows triangle inequality. The weighted calibration of the model
can be written as,

(16) $\displaystyle\sum_{N_{i}\in\mathcal{N}}$
$\displaystyle|N_{i}|\times|e(h|N=N_{i})-o(h|N=N_{i})|=$ (17)
$\displaystyle\sum_{N_{i}\in\mathcal{N}}|N_{i}|\times|\dfrac{1}{|N_{i}|}(\sum_{u\in
N_{i}}s_{u})-\dfrac{1}{|N_{i}|}(\sum_{u\in N_{i}}y_{u})|=$ (18)
$\displaystyle\sum_{N_{i}\in\mathcal{N}}|\sum_{u\in N_{i}}s_{u}-\sum_{u\in
N_{i}}y_{u}|\geq|\sum_{u\in D}s_{u}-\sum_{u\in D}y_{u}|$ (19)
$\displaystyle=|D|\times(|e(h)-o(h)|)$

Proof of Theorem 2

Since $\mathcal{N}_{2}$ is a subgroup partitioning of $\mathcal{N}_{1}$ it can
be constructed following step-by-step partitioning of neighborhoods in
$\mathcal{N}_{1}$ into finer granularity ones until reaching
$\mathcal{N}_{2}$. Denote $\mathcal{N}_{1}$ neighborhoods by
$\\{N_{1},N_{2},...,N_{t}\\}$. Without loss of generality, we show that
splitting an arbitrary neighborhood $N_{j}\in\mathcal{N}_{1}$ to $N_{j1}$ and
$N_{j2}$ leads to a worse ENCE metric value:

(20) $\displaystyle\text{ENCE}(\mathcal{N}_{1})=$
$\displaystyle\sum_{N_{i}\in\mathcal{N}}|N_{i}|\times|e(h|N=N_{i})-o(h|N=N_{i})|=$
$\displaystyle\sum_{N_{i}\in\mathcal{N},i\neq
j}|N_{i}|\times|e(h|N=N_{i})-o(h|N=N_{i})|+$ (21)
$\displaystyle|N_{j}|\times|e(h|N=N_{j})-o(h|N=N_{j})|$

Note that,

(22) $\displaystyle|N_{j}|\times$ $\displaystyle|e(h|N=N_{j})-o(h|N=N_{j})|=$
(23) $\displaystyle|N_{j}|\times|\dfrac{1}{|N_{j}|}(\sum_{u\in
N_{j}}s_{u})-\dfrac{1}{|N_{j}|}(\sum_{u\in N_{j}}y_{u})|=$ (24)
$\displaystyle|(\sum_{u\in N_{j}}s_{u})-(\sum_{u\in N_{j}}y_{u})|=$ (25)
$\displaystyle|(\sum_{u\in N_{j1}}s_{u})-(\sum_{u\in N_{j1}}y_{u})+(\sum_{u\in
N_{j2}}s_{u})-(\sum_{u\in N_{j2}}y_{u})|\leq$ (26) $\displaystyle|(\sum_{u\in
N_{j1}}s_{u})-(\sum_{u\in N_{j1}}y_{u})|+|(\sum_{u\in
N_{j2}}s_{u})-(\sum_{u\in N_{j2}}y_{u})|=$
$\displaystyle|N_{j1}|\times|\dfrac{1}{|N_{j1}|}(\sum_{u\in
N_{j1}}s_{u})-\dfrac{1}{|N_{j1}|}(\sum_{u\in N_{j1}}y_{u})|+$ (27)
$\displaystyle|N_{j2}|\times|\dfrac{1}{|N_{j2}|}(\sum_{u\in
N_{j2}}s_{u})-\dfrac{1}{|N_{j2}|}(\sum_{u\in N_{j2}}y_{u})|$

Therefore, since by further splitting of neighborhoods, ENCE gets worse and as
$\mathcal{N}_{2}$ can be reconstructed one division at a time from
$\mathcal{N}_{1}$, one can conclude that

(28) $\text{ENCE}(N_{1})\leq\text{ENCE}(N_{2})$

Proof of Theorem 3

As the tree is binary, there is a maximum of $\lceil\log(t)\rceil$
partitioning levels. At every level of the tree, the fairness objective
function is calculated $|D|$ times, with each computation taking a constant
time. Therefore, the required number of computations is
$\mathcal{O}(|D|\times\lceil\log(t)\rceil)$. Moreover, the algorithm requires
an initial run of the model $h$, which depends on what ML model is employed,
represented by the computation complexity of $O(h)$ in the total complexity
equation.

Proof of Theorem 4

Similar to Fair KD-tree, the total number of levels in Iterative Fair KD-tree
is $\lceil\log(t)\rceil$ requiring computational complexity of
$\mathcal{O}(|D|\times\lceil\log(t)\rceil)$ to obtain the values for fair
partitioning. However, in contrast to the Fair KD-tree algorithm, the
iterative version requires the execution of the ML model at every height of
the tree. The total computational complexity adds up to
$\mathcal{O}(|D|\times\lceil\log(t)\rceil)+\lceil\log(t)\rceil\times\mathcal{O}(h)$.

Proof of Theorem 5

Multi-objective Fair KD-tree requires a single execution of the ML classifier
at the beginning of the algorithm. Therefore, the computational complexity is
$\sum_{i\texttt{=}1}^{m}\mathcal{O}(h_{i})$. Once confidence scores are
generated, given that $m$ is small, the total required objective computations
at every tree level remains $\mathcal{O}(|D|\times\lceil\log(t)\rceil)$ as the
combined vector can be calculated in constant time.


# Speech Bandwidth Expansion Via High Fidelity Generative Adversarial Networks

Mahmoud Salhab
Lebanese American University
Department of Computer Science and Mathematics
Byblos, Lebanon
<EMAIL_ADDRESS>&Haidar Harmanani
Lebanese American University
Department of Computer Science and Mathematics
Byblos, Lebanon
<EMAIL_ADDRESS>
###### Abstract

Speech bandwidth expansion is crucial for expanding the frequency range of
low-bandwidth speech signals, thereby improving audio quality, clarity and
perceptibility in digital applications. Its applications span telephony,
compression, text-to-speech synthesis, and speech recognition. This paper
presents a novel approach using a high-fidelity generative adversarial
network, unlike cascaded systems, our system is trained end-to-end on paired
narrowband and wideband speech signals. Our method integrates various
bandwidth upsampling ratios into a single unified model specifically designed
for speech bandwidth expansion applications. Our approach exhibits robust
performance across various bandwidth expansion factors, including those not
encountered during training, demonstrating zero-shot capability. To the best
of our knowledge, this is the first work to showcase this capability. The
experimental results demonstrate that our method outperforms previous end-to-
end approaches, as well as interpolation and traditional techniques,
showcasing its effectiveness in practical speech enhancement applications.

_K_ eywords Speech Bandwidth Expansion, Speech Enhancement, Signal Processing,
Generative Adversarial Networks

##  1 Introduction

Speech Bandwidth Expansion (BWE) involves the conversion of a narrowband
speech signal into a wideband one. This process is also referred to as Audio
Super Resolution, where the objective is to generate a high-resolution speech
signal from a low-resolution input containing only a fraction of the original
samples [1]. BWE serves to enhance the quality and perceptibility of
narrowband speech, a capability particularly valuable in contexts such as
Public Switching Telephone Network (PSTN) environments [2]. Bandwidth
expansion plays a vital role in many systems, and it has shown how the
performance of automatic speech recognition systems degrades when encountering
a narrowband speech signal [3].

Although the critical need for speech transmission bandwidth has diminished in
modern times, numerous devices and equipment still operate with, receive, and
even store narrowband speech. For example, many Bluetooth headphones continue
to function based on narrowband speech [4].

A speech signal can be described as a continuous function, denoted as $f(t)$
over the interval $[0,T]$, where $T$ is duration of the speech in seconds, and
$f(t)$ is the amplitude at time $t$. To convert this continuous signal into a
discrete form, a sampling technique is employed, in such a way, a value of the
signal is captured every $T_{s}$ seconds. This sampling process establishes
the sampling rate of the signal, denoted as $F_{s}$ (in Hz), which can be
calculated as the reciprocal of the sampling interval $T_{s}$. Consequently,
the continuous function $f(t)$ can be discretized into a vector $x$ comprising
samples taken at regular interval $T_{s}$, such that
$x=\\{f(T_{s}),f(2T_{s}),f(3T_{s}),\ldots f(nT_{s})\\}$. In terms of the
sample rate, the discretized signal can be represented as
$x=\\{f(\dfrac{1}{F_{s}}),f(\dfrac{2}{F_{s}}),f(\dfrac{3}{F_{s}}),\ldots
f(\dfrac{n}{F_{s}})\\}$. Where $n$ is the number of samples, which can be
calculated by $n=\lfloor\dfrac{T}{T_{s}}\rfloor$. The sampling rate of a
signal can vary significantly, spanning from 4 KHz, typically associated with
low-quality telephone speech, to 48 KHz, indicative of high-quality
speech/music.

According to the Nyquist–Shannon sampling theorem proposed by Shannon [5],
when a signal is sampled at a rate of $F_{s}$ Hz, the maximum bandwidth $B$ of
that signal that guarantees no aliasing is $B=\dfrac{F_{s}}{2}$. Thus, to
expand the bandwidth $B$ by a factor of $\mathbf{s}$, the sampling rate must
also be scaled by $\mathbf{s}$. Formally, in the context of a narrowband
speech signal with a sample rate and bandwidth $F_{low}$ and $B_{low}$
respectively, bandwidth expansion entails scaling the sampling rate and
bandwidth by an upsampling ratio $\mathbf{s}$. This results in a wideband
speech signal with $F_{high}$ = $\mathbf{s}\times F_{low}$, $B_{high}$ =
$\mathbf{s}\times B_{low}$, and $|x_{high}|=\mathbf{s}\times|x_{low}|$, where
$x_{high}$ represents the wideband speech signal and $x_{low}$ represents the
narrowband one. Consequently, the bandwidth expansion or the audio super-
resolution problem is akin to reconstructing the missing frequency content
between $B_{high}$ and $B_{low}$.

In this study, we propose utilizing a high-fidelity generative adversarial
network for speech bandwidth expansion across different upsampling ratios.
Unlike traditional cascaded techniques, our method is end-to-end, requiring
only a single model for both training and inference. To further enhance
performance, we introduce a unified model capable of processing various
upsampling ratios, eliminating the need for separate models for each
upsampling ratio. Additionally, we evaluate our model in zero-shot settings,
where the model processes previously unseen narrowband speech signals to scale
them to unseen upsampling ratio. To the best of our knowledge, this is the
first work to introduce zero-shot capability for neural speech bandwidth
expansion.

This paper is organized as follows. Section 2 presents a literature review,
establishing the context and background for our research, followed by our
methodology in section 3. Sections 4 and 5 present the experiments and the
results, and lastly, we conclude in section 6 with a summary of potential
future work.

##  2 Related Work

Bandwidth expansion, also referred to as audio super-resolution in the
literature, and it has been a subject of study for decades due to its
significance in many systems [6, 7, 8, 9, 10, 11, 12, 13, 14]. Early studies
focused on estimating the spectral envelope of the high-frequency band and
using excitation generated from the low-frequency band to recover the high-
frequency spectrum [15]. Traditional techniques such as Gaussian mixture
models, linear predictive coding, and hidden Markov models have also been used
[16, 17, 18]. However, these methods generally perform worse compared to
neural networks [19]. Additionally, matrix factorization techniques trained on
very small datasets have been proposed to mitigate the computational cost of
factorizing matrices [20, 21].

Recent advancements in end-to-end deep neural networks generate wideband
signals directly from narrowband signals without the need for feature
engineering. For instance, [22] proposed training a deep neural network as a
mapping function, using log-spectrum power as the input and output features to
perform the required nonlinear transformation. A dense neural network with
three hidden layers of size 2048 and ReLU activation function proposed in [3],
showed that this method is preferred over Gaussian mixture models in 84% of
cases in a user study they made.

Inspired by image super-resolution algorithms, which use machine learning
techniques to interpolate a low-resolution image into a higher-resolution one,
a convolutional U-net contains successive downsampling and upsampling blocks
with skip connections proposed in [23]. Building on that, a neural network
component named Temporal Feature-Wise Linear Modulation (TFiLM) introduced in
[24]. TFiLM captures long-range input dependencies in sequential inputs by
combining elements of convolutional and recurrent approaches in a U-net-like
architecture. Furthermore, it modulates the activations of a convolutional
model using long-range information captured by a recurrent neural network. A
block-online variant of the temporal feature-wise linear modulation (TFiLM)
model to achieve bandwidth extension was proposed by [25]. This architecture
simplifies the UNet backbone of the TFiLM to reduce inference time and employs
an efficient transformer at the bottleneck to alleviate performance
degradation. It also utilizes self-supervised pretraining and data
augmentation to enhance the quality of bandwidth-extended signals and reduce
sensitivity with respect to downsampling methods.

Attention-based Feature-Wise Linear Modulation (AFiLM) [26] proposed a network
with a U-net-like architecture for audio super-resolution that combines
convolution and self-attention. AFiLM uses a self-attention mechanism instead
of recurrent neural networks to modulate the activations of the convolutional
model.

In [27], to model the distribution of the target high-resolution signal
conditioned on the log-scale mel-spectrogram of the low-resolution signal
researchers utilized the WaveNet [28] model. Furthermore, [29] studied the use
of the Wave-U-Net architecture for speech enhancement.

Generative Adversarial Networks (GANs) [30] are utilized in [31], where an
additional third component is proposed in the TTS pipeline for neural
upsampling. This converts lower resolution audio (16-24 kHz) to full high-
resolution audio (44.1 kHz). Additionally, researchers explored the use of a
diffusion probabilistic model for audio super-resolution, which is designed
based on neural vocoders [32].

A Glow-based waveform generative model for performing audio super-resolution
was proposed in [33]. Specifically, the integration of WaveNet and Glow
directly maximizes the exact likelihood of the target high-resolution (HR)
audio conditioned on low-resolution (LR) information. To exploit audio
information from low-resolution audio, an LR audio encoder and an STFT encoder
are proposed, which encode the LR information from the time domain and
frequency domain, respectively.

A neural vocoder-based speech super-resolution method (NVSR) was proposed by
[34], capable of handling various input resolutions and upsampling ratios.
NVSR follows a cascaded system structure, comprising a mel-bandwidth extension
module, a neural vocoder module, and a post-processing module.

A diffusion-based generative model designed to perform robust audio super-
resolution across a wide range of audio types named AudioSR proposed in [35].
AudioSR designed specifically to enhance the quality of sound effects, music,
and speech.

##  3 Methodology

Given a dataset
$\mathcal{D}=\\{(x_{1},\hat{x}_{1}),(x_{2},\hat{x}_{2}),\ldots,(x_{M},\hat{x}_{M})\\}$,
where each pair consists of the same speech signal sampled at different
frequencies, we define $\hat{x}_{m}$ as the signal sampled at a lower
frequency $F_{low}$ with bandwidth $B_{low}$, and $x_{m}$ as the signal
sampled at a higher frequency $F_{high}$ with bandwidth $B_{high}$. Both
signals originate from the same source. Mathematically,
$F_{high}=\mathbf{s}\times F_{low}$ and $B_{high}=\mathbf{s}\times B_{low}$,
such that $\mathbf{s}>1$, where $\mathbf{s}$ is the super-
resolution/upsampling ratio. Formally, we represent $x_{m}$ as
$x_{m}=\\{x_{1},x_{2},\ldots,x_{N}\\}$ and $\hat{x}_{m}$ as
$\hat{x}_{m}=\\{\hat{x}_{1},\hat{x}_{2},\ldots,\hat{x}_{\lfloor\frac{N}{\mathbf{s}}\rfloor}\\}$.

Our goal is to expand the bandwidth of the given signal $\hat{x}$ by a factor
of $\mathbf{s}$, resulting in a speech signal with an increased sampling
frequency and bandwidth. The objective of neural super-resolution is to
construct a function $\mathcal{F}_{\theta}$ such that
$\acute{x}=\mathcal{F}_{\theta}(\hat{x})$, where $\acute{x}$ is the upsampled
or reconstructed version of the input speech signal $\hat{x}$ with bandwidth
$B_{high}$. In such a way, $\acute{x}$ is as close as possible to the ground
truth one $x$. The aim is to develop an effective yet efficient function
$\mathcal{F}_{\theta}$. A straightforward approach involves designing
$\mathcal{F}_{\theta}$ as a simple DNN [36] or CNN [37] that minimizes the
following objective function:

$\min_{\theta}\sum_{m=1}^{M}\sum_{n=1}^{N}(\mathcal{F}_{\theta}(\hat{x}_{m})_{n}-x_{m,n})^{2}$
(1)

If the network is not properly designed, several issues may arise. Speech
signals tend to be lengthy, making it computationally inefficient to train a
complex model. Additionally, distance-based objective functions have inherent
limitations. Training neural networks with such objectives often results in
blurry outputs in computer vision, known as the "softness" issue [38, 39], and
similarly in speech. Therefore, our objective is to build an efficient
$\mathcal{F}_{\theta}$ and use an appropriate objective function to train
$\mathcal{F}_{\theta}$ on the dataset, ensuring the reconstructed speech
signal closely matches the high-resolution signal. To achieve this, we
employed an adversarial loss to eliminate the softness issue and utilized a
convolutional model architecture, which will be elaborated upon in the
following sections.

###  3.1 Model

In the realm of speech audio, where signals exhibit sinusoidal characteristics
with varying periods, accurately representing these periodic patterns is
paramount for synthesizing authentic, high-fidelity speech from an original,
low-fidelity source. Building upon the methodology in [40], our model
comprises a generator and two distinct discriminator types: multi-scale and
multi-period discriminators. These elements undergo adversarial training,
supplemented by two auxiliary loss functions to boost training stability. The
multi-period discriminator comprises several sub-discriminators, each
targeting specific periodic segments within the raw waveforms. Complementing
this, the generator module incorporates multiple residual blocks, each adept
at processing patterns of different lengths concurrently. This design ensures
the model comprehensively captures the diverse range of periodic
characteristics present in speech audio. The entire model architecture is
illustrated in Figure 1, and detailed explanations of each subcomponent follow
in the subsequent sections.

Figure 1: Complete architecture of the model.

####  3.1.1 Generator

The generator is a convolutional neural network that’s entirely dedicated to
upscaling. It begins with a mel-spectrogram input generated within the input
speech signal’s preprocessor module, and uses transposed convolutions to
gradually match the temporal resolution of the high-resolution speech signal
$x_{m}$. Each transposed convolution operation is accompanied by a multi-
receptive field fusion (MRF) module. This module is designed to analyze
patterns of different lengths simultaneously. It achieves this by summing the
outputs from several residual blocks. These blocks employ various kernel sizes
and dilation rates to create a wide range of receptive field patterns. The
architecture of the generator is identical to the generator proposed in [40].

####  3.1.2 Discriminator

Following the methodology presented in [40], the design of the discriminator
tackles two critical challenges. Firstly, it must adeptly capture the extended
dependencies within the input speech signal. Secondly, given the sinusoidal
nature of the input with variable periods, it needs to discern the diverse
periodic patterns inherent in the audio data. Thus, we adopt a similar
strategy as detailed in the original work [40]. This involves implementing a
multi-period discriminator (MPD) composed of multiple sub-discriminators, each
responsible for analyzing a segment of the periodic signals within the input
audio. Additionally, a multi-scale discriminator (MSD) is employed to detect
sequential patterns and long-term dependencies effectively.

###  3.2 Training Loss

For the generator and discriminator, the training objectives follow the
approach proposed in [41], where the binary cross-entropy loss function is
replaced with the least square error loss. This substitution helps prevent the
vanishing gradient issue. Additionally, an extra objective function is
included, specifically mel-spectrogram reconstruction as proposed by [42],
along with discriminator feature-wise matching across layers as in [43]. The
discriminator is trained to classify ground truth samples as 1 and samples
synthesized by the generator as 0. The generator, on the other hand, is
trained to deceive the discriminator by enhancing the sample quality so that
it is classified as close to 1 as possible. The objective function for the
discriminator $D_{\phi}$ shown in the Equation 2 and for the generator
$G_{\theta}$ is expressed in the Equation 3.

$\min_{D_{\phi}}\mathbb{E}[(1-D_{\phi}(x))^{2}+D_{\phi}(G_{\theta}(\hat{x}))^{2}]$
(2)

$\min_{G_{\theta}}\lambda_{adv}\mathcal{J}_{adv}+\lambda_{mel}\mathcal{J}_{mel}+\lambda_{feat}\mathcal{J}_{feat}$
(3)

$\mathcal{J}_{adv}=\mathbb{E}[(1-D_{\phi}(G_{\theta}(\hat{x})))^{2}]$ (4)

$\mathcal{J}_{mel}=\mathbb{E}[\|\psi(x)-\psi(G_{\theta}(\hat{x}))\|_{1}]$ (5)

$\mathcal{J}_{feat}=\mathbb{E}[\sum_{k=1}^{K}\frac{1}{N_{k}}\|D_{\phi}^{k}(x)-D_{\phi}^{k}(G_{\theta}(\hat{x}))\|_{1}]$
(6)

In these equations, $\lambda_{adv}$, $\lambda_{mel}$, and $\lambda_{feat}$ are
hyperparameters that balance the contributions of the adversarial, mel-
spectrogram reconstruction, and feature matching term, respectively. $\psi$
represents the function that computes the mel-spectrogram, $D_{\phi}^{k}$
denotes the output of the $k^{th}$ layer of the discriminator, and $N_{k}$ is
the number of elements in the $k^{th}$ layer.

##  4 Experiments

###  4.1 Dataset

Similar to prior studies, we utilized the VCTK corpus [44] for both training
and evaluation purposes. The VCTK dataset comprises approximately 44 hours of
audio recordings, from 109 distinct speakers, offering a variety of voices and
accents including Scottish, Indian, and Irish, among others. The dataset
originally uses a bit width of 16-bit PCM with a sample rate of 48 kHz.
Therefore, we first resampled the entire dataset to a sample rate of 16 kHz
while maintaining the same bit width. To create low-resolution audio, we
applied an order 8 Chebyshev type I low-pass filter to the original 16 KHz
signals, followed by subsampling according to the desired upsampling ratio.

Our research centers on a multi-speaker task, training on the first 100 VCTK
speakers and testing on the remaining speakers 111The speaker IDs used for
testing are p347, p351, p360, p361, p362, p363, p364, p374, p376., in
alignment with the methodology presented in [23].

###  4.2 Evaluation Metric

To evaluate the performance of our proposed method and to measure the quality
of generated audio samples by comparing them to the actual high-resolution
audio, and following previous works, we assess the reconstruction quality of
individual frequencies using the Log Spectral Distance (LSD). The LSD is
calculated as shown in Equation 7.

$LSD(x,\acute{x})=\frac{1}{T}\sum_{t=1}^{T}\sqrt{\frac{1}{F}\sum_{f=1}^{F}(\mathcal{P}(x)_{t,f}-\mathcal{P}(\acute{x})_{t,f})^{2}}$
(7)

$\mathcal{P}(z)=log_{10}|STFT(z)|^{2}$ (8)

Here, $x$ represents the reference wideband speech signal, and $\acute{x}$ is
the reconstructed speech signal from the model. $\mathcal{P}(x)$ denotes the
log-spectral power magnitudes calculated using Equation 8, where $STFT$ refers
to the Short-Time Fourier Transform. Variables $f$ and $t$ correspond to the
frequency and frame index, respectively. A lower LSD values indicate better
frequency reconstruction. Following [23] we used frames of length 2048 to
calculate the STFT in our experiments.

###  4.3 Experimental Setup

For all the experiments, we used different upsampling ratios $\mathbf{s}$,
specifically 2, 4, and 8. For each upsampling ratio, we trained a separate
model, each for 500K steps. Our models were trained on a single machine with
two NVIDIA 3080 TI GPUs, using a global batch size of 16 and the same model
configuration as version 1 described in [40].

Since the preprocessing handles the upsampling, we also trained a unified
model on all the aforementioned upsampling ratios. Additionally, we
investigated the ability of the proposed technique to work in zero-shot
settings, where the model is given a signal and tasked with generating a
signal with a different upsampling ratio than those it was trained on. We
examined whether the model could generalize and predict the signal. The
unified model was trained similarly to the single upsampling ratio models, but
for longer, specifically for 1.5M steps.

All the models were trained on mel-spectrogram input, calculated using $80$
mel-filter bank with an FFT size of $1024$, a window size of $1024$, and a hop
length of $256$. For the generator loss terms, we set $\lambda_{adv}=1.1$,
$\lambda_{mel}=50$, and $\lambda_{feat}=2$. In addition to that, the AdamW
optimizer was used with $\beta_{1}=0.8$ and $\beta_{2}=0.999$, with a weight
decay $\lambda=0.01$, and the learning rate used on each epoch calculated
using Equation 9, where $lr_{init}$ is the initial learning rate set to
$1.5\times 10^{-4}$, $epoch$ is the current training epoch, and $\gamma$ is
the learning rate decaying factor set to $0.999$.

$lr(epoch)=\gamma^{epoch}*lr_{init}$ (9)

##  5 Results

The results of our experiments are presented in Table 1, which displays the
Log Spectral Distance (in dB) for various upsampling ratios, specifically 2,
4, and 8. The table compares the performance of different baselines with two
scenarios: first, when each upsampling ratio is trained on a standalone model,
labeled as "Single," and second, when all upsampling ratios are trained
jointly using a single model, labeled as "Unified." Our model consistently
outperforms all end-to-end baselines. When compared to cascaded models such as
NVSR [34], our approach performs better for high upsampling ratio (i.e.,
$\mathbf{s}=8$) and is comparable for $\mathbf{s}=4$, although cascaded models
outperform our model for low upsampling ratio (i.e., $\mathbf{s}=2$).

Table 1: Analysis of Speech Bandwidth Expansion at Upsampling Ratios of 2, 4, and 8. Approach | s = 2 | s = 4 | s = 8 | End-to-End
---|---|---|---|---
Baseline | 3.464 | 5.17 | 6.08 | N/A
AudioUNet [23] | 3.1 | 3.5 | N/A | ✓
TFNet [45] | N/A | 1.27 | 1.9 | ✓
Temporal FiLM [24] | 1.8 | 2.7 | 2.9 | ✓
MU-GAN [1] | 2.14 | 2.72 | N/A | ✓
AFiLM [26] | 1.7 | 2.3 | 2.7 | ✓
NVSR [34] | 0.78 | 0.95 | 1.07 | ✗
Ours (Single) | 0.9 | 0.98 | 1.047 | ✓
Ours (Unified) | 0.923 | 0.98 | 1.0 | ✓

A test sample is shown in Figure 2, including the input narrowband speech
signal, the reconstructed wideband speech signal, and the original wideband
speech signal. The first column shows the input narrowband speech signal, the
middle column displays the target wideband speech signal, and the last column
presents the predicted wideband speech signal using our trained model. The
first row corresponds to an upsampling ratio of $\mathbf{s}=8$, the second row
to $\mathbf{s}=4$, and the third row to $\mathbf{s}=2$. It is evident that our
approach effectively addresses the issue of oversmoothness, successfully
reconstructing the missing frequencies.

Figure 2: Spectrogram Analysis of Narrowband to Wideband Speech Reconstruction
with Varying Upsampling Ratios ($\mathbf{s}=8$, $\mathbf{s}=4$,
$\mathbf{s}=2$)

The performance of our unified model across various upsampling ratios on the
test set, including those it was trained on (i.e., 2, 4, 8), is illustrated in
Figure 3. Compared to the baseline Fast Fourier Transform (FFT)-based
interpolation technique, our method demonstrates the capability to handle even
unseen upsampling ratios. Notably, the trained upsampling ratios exhibit the
lowest Log Spectral Distance (LSD). Additionally, it is evident that
traditional interpolation-based techniques for bandwidth expansion result in
increased LSD as the upsampling ratios rises (i.e decreasing the input
bandwidth signal). Conversely, our method maintains a bounded LSD, even for
upsampling ratios not encountered during training which shows that our model
can run in zero-shot settings.

Figure 3: Performance comparison of our unified model across various
upsampling ratios, demonstrating its ability to handle unseen upsampling
ratios with maintained low Log Spectral Distance (LSD) compared to traditional
interpolation methods

##  6 Conclusion

In this work, we presented an end-to-end approach for tackling speech
bandwidth expansion using a high-fidelity generative adversarial network
trained across different super-resolution/upsampling ratios. Empirically, our
method surpasses various end-to-end baselines and achieves comparable results
when compared with cascaded approaches. Additionally, we demonstrated the
scalability of our method to unseen upsampling ratios during training in
zeros-shot setting. These findings underscore the potential of our unified
model architecture, which not only simplifies the training and deployment
process but also enhances performance across varying levels of upsampling
ratios. Moving forward, our work opens avenues for further exploration and
application of neural speech bandwidth expansion in real-world scenarios.

## References

  * [1] Sung Kim and Visvesh Sathe.  Bandwidth extension on raw audio via generative adversarial networks, 2019.
  * [2] L. A. Litteral, J. B. Gold, D. C. Klika Jr, D. B. Konkle, C. D. Coddington, J. M. McHenry, and A. A. Richard III.  Pstn architecture for video-on-demand services, 1993.
  * [3] Kehuang Li, Zhen Huang, Yong Xu, and Chin-Hui Lee.  DNN-based speech bandwidth expansion and its application to adding high-frequency missing features for automatic speech recognition of narrowband speech.  In Proc. Interspeech 2015, pages 2578–2582, 2015.
  * [4] J. C. Haartsen and E. Radio.  The bluetooth radio system.  IEEE Personal Communications, 2000.
  * [5] C.E. Shannon.  Communication in the presence of noise.  Proceedings of the IRE, 37(1):10–21, jan 1949.
  * [6] J. Epps and W.H. Holmes.  A new technique for wideband enhancement of coded narrowband speech.  In 1999 IEEE Workshop on Speech Coding Proceedings. Model, Coders, and Error Criteria (Cat. No.99EX351), pages 174–176, 1999.
  * [7] Saeed Vaseghi, E. Zavarehei, and Qin Yan.  Speech bandwidth extension: Extrapolations of spectral envelop and harmonicity quality of excitation.  Acoustics, Speech, and Signal Processing, 1988. ICASSP-88., 1988 International Conference on, 3:III – III, 06 2006.
  * [8] Jinyu Han, Gautham J. Mysore, and Bryan Pardo.  Language informed bandwidth expansion.  In 2012 IEEE International Workshop on Machine Learning for Signal Processing, pages 1–6, 2012.
  * [9] Hyunson Seo, Hong-Goo Kang, and Frank Soong.  A maximum a posterior-based reconstruction approach to speech bandwidth expansion in noise.  ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, pages 6087–6091, 05 2014.
  * [10] Per Ekstrand.  Bandwidth extension of audio signals by spectral band replication.  In Proceedings of the 1st IEEE Benelux Workshop on Model Based Processing and Coding of Audio (MPCA02). Citeseer, 2002.
  * [11] Erik Larsen and Ronald M. Aarts.  Audio Bandwidth Extension: Application of Psychoacoustics, Signal Processing and Loudspeaker Design.  John Wiley & Sons, 2005.
  * [12] P. Jax and P. Vary.  On artificial bandwidth extension of telephone speech.  Signal Processing, 83, 2003.
  * [13] Y. Qian and P. Kabal.  Wideband speech recovery from narrowband speech using classified codebook mapping.  In Proceedings of the Australian International Conference on Speech Science and Technology, Melbourne, 2002.
  * [14] A. H. Nour-Eldin and P. Kabal.  Mel-frequency cepstral coefficient-based bandwidth extension of narrowband speech.  In Proceedings of Interspeech, 2008.
  * [15] B. Iser and G. Schmidt.  Bandwidth extension of telephony speech.  In Speech and Audio Processing in Adverse Environments, pages 135–184. Springer, 2008.
  * [16] Pramod B. Bachhav, Massimiliano Todisco, Moctar Mossi, Christophe Beaugeant, and Nicholas Evans.  Artificial bandwidth extension using the constant q transform.  In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5550–5554, 2017.
  * [17] J. Bradbury.  Linear Predictive Coding.  McGraw-Hill, 2000.
  * [18] Keiichi Tokuda, Yoshihiko Nankaku, Tomoki Toda, Heiga Zen, Junichi Yamagishi, and Keiichiro Oura.  Speech synthesis based on hidden markov models.  Proceedings of the IEEE, 101(5):1234–1252, 2013.
  * [19] Johannes Abel and Tim Fingscheidt.  Artificial speech bandwidth extension using deep neural networks for wideband spectral envelope estimation.  IEEE/ACM Transactions on Audio, Speech, and Language Processing, 26(1):71–83, 2018.
  * [20] Dawen Liang, Matthew D. Hoffman, and Daniel P.W. Ellis.  Beta process sparse nonnegative matrix factorization for music.  In Proceedings of the International Society for Music Information Retrieval Conference (ISMIR), pages 375–380, 2013.
  * [21] Dhananjay Bansal, Bhiksha Raj, and Paris Smaragdis.  Bandwidth expansion of narrowband speech using non-negative matrix factorization.  In Ninth European Conference on Speech Communication and Technology, 2005.
  * [22] Kehuang Li and Chin-Hui Lee.  A deep neural network approach to speech bandwidth expansion.  In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4395–4399, 2015.
  * [23] Volodymyr Kuleshov, S. Zayd Enam, and Stefano Ermon.  Audio super resolution using neural networks, 2017.
  * [24] Sawyer Birnbaum, Volodymyr Kuleshov, Zayd Enam, Pang Wei Koh, and Stefano Ermon.  Temporal film: Capturing long-range sequence dependencies with feature-wise modulations, 2021.
  * [25] Viet-Anh Nguyen, Anh H. T. Nguyen, and Andy W. H. Khong.  Tunet: A block-online bandwidth extension model based on transformers and self-supervised pretraining.  In ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, May 2022.
  * [26] Nathanaël Carraz Rakotonirina.  Self-attention for audio super-resolution, 2021.
  * [27] Mu Wang, Zhiyong Wu, Shiyin Kang, Xixin Wu, Jia Jia, Dan Su, Dong Yu, and Helen Meng.  Speech super-resolution using parallel wavenet.  In 2018 11th International Symposium on Chinese Spoken Language Processing (ISCSLP), pages 260–264, 2018.
  * [28] Aaron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu.  Wavenet: A generative model for raw audio, 2016.
  * [29] Craig Macartney and Tillman Weyde.  Improved speech enhancement with the wave-u-net, 2018.
  * [30] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial networks, 2014.
  * [31] Rithesh Kumar, Kundan Kumar, Vicki Anand, Yoshua Bengio, and Aaron Courville.  Nu-gan: High resolution neural upsampling with gan, 2020.
  * [32] Junhyeok Lee and Seungu Han.  Nu-wave: A diffusion probabilistic model for neural audio upsampling.  In Interspeech 2021. ISCA, August 2021.
  * [33] Kexun Zhang, Yi Ren, Changliang Xu, and Zhou Zhao.  Wsrglow: A glow-based waveform generative model for audio super-resolution, 2021.
  * [34] Haohe Liu, Woosung Choi, Xubo Liu, Qiuqiang Kong, Qiao Tian, and DeLiang Wang.  Neural vocoder is all you need for speech super-resolution.  In Interspeech 2022. ISCA, September 2022.
  * [35] Haohe Liu, Ke Chen, Qiao Tian, Wenwu Wang, and Mark D. Plumbley.  Audiosr: Versatile audio super-resolution at scale, 2023.
  * [36] David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams.  Learning representations by back-propagating errors.  Nature, 323:533–536, 1986.
  * [37] Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel.  Backpropagation applied to handwritten zip code recognition.  Neural Computation, 1(4):541–551, 1989.
  * [38] Richard Zhang, Phillip Isola, and Alexei A. Efros.  Colorful image colorization, 2016.
  * [39] Deepak Pathak, Philipp Krahenbuhl, Jeff Donahue, Trevor Darrell, and Alexei A. Efros.  Context encoders: Feature learning by inpainting, 2016.
  * [40] Jungil Kong, Jaehyeon Kim, and Jaekyoung Bae.  Hifi-gan: Generative adversarial networks for efficient and high fidelity speech synthesis, 2020.
  * [41] Xudong Mao, Qing Li, Haoran Xie, Raymond Y. K. Lau, Zhen Wang, and Stephen Paul Smolley.  Least squares generative adversarial networks, 2017.
  * [42] Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A. Efros.  Image-to-image translation with conditional adversarial networks, 2018.
  * [43] Kundan Kumar, Rithesh Kumar, Thibault de Boissiere, Lucas Gestin, Wei Zhen Teoh, Jose Sotelo, Alexandre de Brebisson, Yoshua Bengio, and Aaron Courville.  Melgan: Generative adversarial networks for conditional waveform synthesis, 2019.
  * [44] Junichi Yamagishi, Christophe Veaux, and Kirsten MacDonald.  Cstr vctk corpus: English multi-speaker corpus for cstr voice cloning toolkit (version 0.92), 2019.
  * [45] Teck-Yian Lim, Raymond A. Yeh, Yijia Xu, Minh N. Do, and Mark A. Hasegawa-Johnson.  Time-frequency networks for audio super-resolution.  2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 646–650, 2018.