# Imperceptible Rhythm Backdoor Attacks: Exploring Rhythm Transformation for
Embedding Undetectable Vulnerabilities on Speech Recognition

Wenhan Yao  Jiangkun Yang  Yongqiang He  Jia Liu  Weiping Wen

###### Abstract

Speech recognition is an essential start ring of human-computer interaction,
and recently, deep learning models have achieved excellent success in this
task. However, when the model training and private data provider are always
separated, some security threats that make deep neural networks (DNNs)
abnormal deserve to be researched. In recent years, the typical backdoor
attacks have been researched in speech recognition systems. The existing
backdoor methods are based on data poisoning. The attacker adds some
incorporated changes to benign speech spectrograms or changes the speech
components, such as pitch and timbre. As a result, the poisoned data can be
detected by human hearing or automatic deep algorithms. To improve the
stealthiness of data poisoning, we propose a non-neural and fast algorithm
called Random Spectrogram Rhythm Transformation (RSRT) in this paper. The
algorithm combines four steps to generate stealthy poisoned utterances. From
the perspective of rhythm component transformation, our proposed trigger
stretches or squeezes the mel spectrograms and recovers them back to signals.
The operation keeps timbre and content unchanged for good stealthiness. Our
experiments are conducted on two kinds of speech recognition tasks, including
testing the stealthiness of poisoned samples by speaker verification and
automatic speech recognition. The results show that our method has excellent
effectiveness and stealthiness. The rhythm trigger needs a low poisoning rate
and gets a very high attack success rate.

###### keywords:

Backdoor attacks , Speech recognition , Rhythm transformation , Neural vocoder

††journal: Neurocomputing

[1]organization=Xiangtan University,addressline=Yuhu District Xiangda Road,
city=Xiangtan, postcode=411100, state=Hunan, country=China
[2]organization=Peking University,addressline=No.5, Summer Palace Road,
Haidian District, Beijing, China, city=Beijing, postcode=100871,
state=Beijing, country=China

##  1 Introduction

Speech recognition systems are critical components of human-computer
interaction, [1] which enables machines to recognize human identity or vocal
commands. Speech recognition models are usually trained by machining learning
methods and need abundant supervised utterance datasets and precious
computational resources. Under special circumstances, some companies entrust
their sensitive speech recognition datasets to third-party training platforms
to reduce training expenses.

However, recent research found that exposing classification datasets to
malicious training developers may make the deep neural network (DNN) models
vulnerable [2]. In some training procedures ($e.g.$, data collection and
preparation and model training), the attackers can manipulate the behavior of
speech recognition systems by embedding backdoors to DNN models and cause an
extreme security risk. The backdoor adversaries poisoned the model to learn
the benign and attacker-specific tasks by implanting the backdoor into the
target. The adversaries usually generate poisoned samples and alter their
ground truth labels with designed triggers for the poisoned task. For inputs
containing no trigger, the victim model behaves normally as its clean parallel
model. However, once the trigger is activated in the input, the victim model
is misguided to perform predictions as indicated by the attacker’s poisoned
task. It is difficult to distinguish the backdoored model from its clean
version by simply checking the test accuracy with the test dataset.

Most of the backdoor attack methods are developed in computer vision tasks and
text classification at present [3, 4, 5, 6, 7]. These methods usually treat
noisy pixel patterns and extra phrases as triggers. Motivated by these, the
study of backdoor attacks in speech recognition imitates these methods, whose
triggers are ultrasonic sound, hidden noisy shrill, monotone sound, and some
time-frequency mask of the spectrogram [8, 9, 10, 11, 12, 13, 14]. In latest
research, the trigger in speech starts shifting to the components of the
speech, such as pitch boosting and timbre conversion [15, 16, 17, 18].
However, the extra noisy clips destroy speech quality and make the trigger
unconcealed. Besides, the pitch and timbre triggers have the potential to be
automatically detected. According to voice disentanglement research [19, 20],
four main speech components are considered important: rhythm, content, timbre,
and pitch. However, the transformation of pitch and timbre can be detected by
Automatic Speech Recognition (ASR) and speaker verification systems (SVS); the
pitch boosting can also be detected by the YIN algorithm [21].

Can the backdoor trigger in speech recognition avoid automatic detection and
sustain naturalness and speech quality? In this paper, we give a positive
answer, and we target rhythm as a trigger from the perspective of the
components. The rhythm is mainly related to the speed of each syllable [22].
We propose a non-neural and fast algorithm called Random Spectrogram Rhythm
Transformation (RSRT) to generate poisoned samples whose rhythms are
transformed. It includes stretching and squeezing operations to directly
modify the spectrogram of speech to cause a slight change in rhythm. The
poisoned spectrogram is then reconstructed into speech using a neural network
vocoder, ensuring the converted speech’s naturalness and intelligibility.
Numerous studies have shown that the neural network vocoder exhibits good
generalization performance [23, 24] for various modified spectrograms. We
mainly focus on the keyword spotting (KWS) task and text-independent speech
emotion recognition (TSER) task in our work because the slight change of
rhythm does not destroy the content and emotion. Finally, we conducted two
evaluation metrics on poisoned samples to verify the consistency of speech
components. The experiment results demonstrate that the rhythm trigger gains a
high attack success rate with a very low poisoning rate. Our contributions can
be summarized as follows:

  * 1.

We designed a non-neural rhythm transformation poisoning pipeline containing
RSRT. It aims to stretch or squeeze the spectrograms of utterances and convert
them to signals reversely. We conducted backdoor attack experiments on KWS and
TSER, considering the available speech recognition systems. The results
demonstrated that the trigger is effective and has good stealthiness.

  * 2.

We conducted three kinds of evaluation experiments to prove the good
stealthiness of our proposed trigger. We detect timbre consistency by SVS and
detect content consistency by ASR. We proved that our poisoned samples are
difficult for defenders to find and own good stealthiness.

The rest of this paper is structured as follows. In Section 2, we briefly
introduce backdoors and speech recognition. In Section 3, we illustrate
backdoor method motivation and attacking theory. we elaborately describe the
main stages of RSRT. In Section 4, we show the results of attack effectiveness
and stealthiness evaluation. Finally, we conclude this paper in Section 5 at
the end.

##  2 Related Works

###  2.1 Speech Recognition

###  2.2 Backdoor Attacks

Backdoor attacks [25, 26] are a series of poisoning methods that aim to bury a
backdoor to the model parameters. The attackers usually design specific target
labels and guarantee the model will learn the relationship between labels and
triggers. Depending on whether training data is poisoned, backdoor attacks can
be categorized into poisoning-based attacks and clean-based attacks. Although
the poisoning-based attacks enhance the effectiveness of backdoor attacks, the
poisoned samples are vulnerable to avoiding detection by defenders [27, 28,
29]. To avoid notice of defender while remaining attacks, Turner et al. [30,
31] firstly explored clean-label backdoor attacks that aim to control the
model’s behavior by an adversary without poisoning input samples during
inference. From the perspective of attackers, we will explain various attack
methods.

####  2.2.1 Poisoned-Label and Clean-Label Attacks

Poisoned and clean-label attacks usually happen in classification models that
learn weight optimization by many pairs of samples and labels. The poisoned-
label attackers modify both samples and labels, while the clean-label
attackers only modify the samples. Chen et al. blended an attacker-specific
Hello Kitty pattern as a trigger with images [32]. Eykholt et al. constructed
distributed and spread images as triggers to mask sign images [33]. Sarkar et
al. [34] utilized existent facial characteristics as triggers. All these
modifications are connected to target labels. Turner et al.[35] first explored
a method that leveraged adversarial perturbations or generative models to
modify some benign images for clean-label attacks.

####  2.2.2 Sample-Agnostic and Sample-Specific Attacks

The poisoned images are commonly generated by attacker-specified generators
with specific trigger patterns. Sample-agnostic attacks are widespread
backdoor attacks in which all poisoned samples share the same trigger.
However, this characteristic can be easily exploited for backdoor defense [27,
36]. Nguyen et al. [37] proposed applying visible triggers to be contained in
different poisoned samples, which is the first sample-specific backdoor attack
method. This method embedded trigger patterns in the edge structure of
poisoned images, broke many defense assumptions, and led to good effectiveness
on many backdoor defenses. Therefore, sample-specific attacks cause a serious
security threat and are worth deeper investigations.

####  2.2.3 Semantic and Non-Semantic Attacks

The attackers may utilize the semantic information in the images and relate
semantic regions with target labels for backdoor attacks, and this method is a
semantic attack. Bagdasaryan et al. [38, 39] first explored that certain
features are $e.g$, green cars or white birds can be related to attacker-
specified target labels. It is noted that the semantic information is ”bird”
or ”car.” Accordingly, the victim model will wrongly classify images
containing pre-defined semantic information without any digital modification
during inference.

####  2.2.4 All-to-One and All-to-All Attacks

According to the type of target labels, poisoning-label backdoor attacks can
be categorized as all-to-one attacks and all-to-all attacks. All-to-one
attacks assume that poisoned samples share the same target label, regardless
of their original labels. On the contrary, poisoned samples may possess
different target labels within all-to-all attacks. For example, Doan et al.
[40, 41] applied label shifting function assigning as $LS(y)=(y+1)\mod T$. It
noted that $T$ is a controllable integer by attackers, and $y$ is label.

####  2.2.5 Digital and Physical Attacks

Previous attacks usually occur entirely in digital space, and attackers
implement triggers by coding, which belongs to totally digital attacks.
Physical attacks are involved in generating poisoned samples in physical
space. Chen et al. [32] firstly applied a pair of glasses as a physical
trigger for poisoning a face recognition system originating in a camera.
Wenger et al. [42, 3] also found that colored dot stickers can be treated as
physical triggers. However, Li et al. [43] demonstrated that digital triggers
are sensitive to space transformation, such as rotation and shrinkage, which
will change the location and form of triggers in poisoned samples. Based on
this knowledge, they proposed a transformation-based attack enhancement that
keeps the improved attacks effective in the physical world.

##  3 Methods

###  3.1 Motivation

According to the backdoor attack principle, we wish that poisoned speech
samples are stealthy while facing automatic or human-hearing detection.
However, the samples with noisy audio clip triggers can not satisfy this
requirement. Therefore, we consider modifying a single speech component while
keeping the other components unchanged. The components are shown in Figure 1.

Figure 1: Backdoor attacks by changing speech components.

In [17, 16], the stealthiness evaluation has demonstrated that tiny
modifications in timbre and pitch do not influence speech naturalness and
intelligibility. However, deep speech systems such as SVS can find the
modification.

In this paper, we aim to treat the rhythm as the backdoor trigger. The rhythm
is highly correlated with the duration of each syllable. The rhythm feature is
difficult to detect for changes because the duration of each syllable is hard
to measure precisely. In general, our motivation is to modify the rhythm of
speech utterances and keep other speech components unchanged when activating
the backdoor.

Table 1: The definition of backdoor description symbols. Notation |  Description
---|---
$f_{\theta}$ |  speech classifier learned from benign dataset
$f_{\theta^{\prime}}$ |  speech classifier learned from poisoned samples
$\mathcal{X}\times\mathcal{Y}$ |  domain space of inputs and labels
$\mathcal{F}_{t}:\mathcal{X}\rightarrow\mathcal{X^{*}}$ |  backdoor input trigger
$\mathcal{F}_{y}:\mathcal{Y}\rightarrow\mathcal{Y^{*}}$ |  label shifting function
$D,D_{e}$ |  benign training and test dataset
$D_{r}$ |  selected subset from benign dataset
$D_{s}$ |  poisoned subset from selected subset
$D_{p}$ |  poisoned dataset that contains poisoned and benign samples
$L_{(x,y)}$ |  training objective that is training on dataset $\\{(x,y)\\}$

###  3.2 Preliminaries

####  3.2.1 Neural Vocoder

Neural vocoder is a neural network that converts spectrograms to speech
signals and exhibits excellent generalization performance, which encourages
the use of it for reconstructing stretched and squeezed spectrograms. The
vocoder used in our experiment is HiFi-GAN [44], which includes a generator
and discriminator. The pre-trained generator is applied for conversion.

Figure 2: The proposed attack pipeline via RSRT. The pipeline consists of
three main stages, including (a) the Attack Stage, (b) the Training Stage, and
(c) the inference Stage. The RSRT is the core of the attack stage, containing
four steps (i.e., VAD, RSRT, vocoder conversion, and silence concatenation).
1) We use VAD to extract and locate active speech regions for effective
attacks. 2) We choose a set of rhythm transformation hyper-parameters and use
RSRT to stretch or squeeze utterances, making the rhythm migration. 3) The
rhythm-migrated speech is converted back to signal with a pre-trained neural
vocoder, maintaining consistency in speech content and timbre. 4) To make the
poisoned speech similar to normal speech, we concatenated silence at the
beginning and end, ensuring that the duration of the poisoned speech matches
the original speech.

####  3.2.2 Threat Model

: This paper concentrates on poisoning-based backdoor attacks. And there are
some basic principles in this scenario. The adversaries can only modify the
open-access training dataset to a poisoned dataset. The victim models will be
trained on the poisoned dataset, and the user will deploy the models to the
working environment. Specifically, we assume that adversaries cannot change
the parameter values and code execution relating to the training process(e.g.,
loss function, learning schedule, or the resulting model.

####  3.2.3 The Goal of Adversary

: The attacker’s goals primarily include stealthiness, effectiveness, and
robustness. Stealthiness requires that backdoor attacks have the ability to
escape human examination and machine detection. Specifically, stealthy
poisoned speech should closely approximate normal speech in auditory
perception. Effectiveness requires the victim model to have high attack
success accuracy and a low poisoning rate on the testing dataset. It is noted
that although some methods achieve very high attack success rates, they often
require a concerning proportion of poisoned samples. This configuration may
lead to bad stealthiness. Robustness requires that backdoor attacks behave
well on simple detection means and remain effective under more difficult
settings, such as adaptive defenses and physical-world settings.

####  3.2.4 Poisoning-Based Backdoor Attacks Pipeline

We first illustrate backdoor attacks by the notions and their definition of
backdoor in Table 1. We denote the classifier
$f_{\theta}:\mathcal{X}\rightarrow\mathcal{Y}$, where $\theta$ signifies model
parameters, $\mathcal{X}\in R^{T,C}$ being the instance space, and
$\mathcal{Y}=[1,2,...,K]$ being the label space. The $T,C$ represent the
sequence length and channel number. Let
$\mathcal{F}_{t}:\mathcal{X}\rightarrow\mathcal{X}$ indicates the attacker-
specified trigger function and
$\mathcal{F}_{y}:\mathcal{Y}\rightarrow\mathcal{Y}$ indicates label shifting
function. Before attacking, the clean training dataset is prepared that is
signified as $D=\\{(x_{i},y_{i})\\}^{N}_{i=1}$, then, the attacker will design
the poisoned subset that is conducted by
$D_{s}=\\{\mathcal{F}_{t}(x_{j}),\mathcal{F}_{y}(y_{j})\\}^{M}_{j=1}$ where
the replaced subset is $D_{r}=\\{(x_{k},y_{k})\\}^{M}_{k=1}$. Finally, the
poisoned dataset is mixed by $D_{p}=(D-D_{r})\cup D_{s}$. Backdoor attacks
request the model to optimize $f_{\theta}$ by following the training
objective.

$L_{(x,y)\in D_{p}}=\mathop{\arg\max}\limits_{\theta}p(y|f_{\theta}(x))$ (1)

This objective leads the model to correctly classify the benign samples
$x\in\mathcal{X}$ to their ground true labels and the poisoned samples
$x^{*}=\mathcal{F}_{t}(x)\in\mathcal{X^{*}}$ to target labels respectively.
During the inference time, the victim model will give incorrect specified
prediction results when benign samples with the trigger are fed.

Figure 3: The illustration of rhythm transformation. (a) denotes the process
of stretching algorithm. Some frames are copied in the next places of the
original index, while the other frames are retained. (b) denotes the process
of squeezing the algorithm. A part of the frames and their next frames are
selected to form new frames by double linear weight sum. (c) and (d)
respectively show the speech spectrograms squeezed to $1/2$ times and $2/3$
times and stretched to 1.3 times to 2.0 times.

###  3.3 Attack via Random Spectrogram Rhythm Transformation

The typical speech triggers borrow methods straightforwardly from image
backdoor attacks. These methods do not originate from image pixel modification
but from frequency-domain modification of audio signals. For example, PIBA
trigger [9] adds a short noise clip to the signal. JingleBack trigger [45]
applies pitch shift and distortion to the signal. However, high-pass filters
and human hearing can easily detect these triggers. The triggers of modifying
speech components retain the naturalness of poisoned utterances without adding
any external sounds or making complex distortion. PBSM[17] and VSVC[16]
proposed to change the pitch and timbre. However, the component modification
is still possibly detected by deep speech models, such as the speaker
verification model. To tackle this problem. We turn our attention to another
component, rhythm. The rhythm refers to the speed of each speech syllable,
representing the pace of the spoken language. We propose to change each
syllable speed by a simple spectrogram frame-level algorithm. Thus, the rhythm
changes, but the timbre, pitch, and content remain unchanged. The algorithm is
used in the attack stage via random spectrogram rhythm transformation (RSRT).

The poisoning-base attack pipeline via RSRT focuses on three stages, as shown
in Figure 2, including (a) the Attack stage, (b) the Training stage, and (c)
the Inference stage. We mainly describe the theory of the attack stage as
shown in Figure 2(a). It includes (1)Voice Active Detection (VAD), (2)RSRT,
(3)Vocoder conversion, (4)Silence concatenation. The RSRT algorithm is the key
operation. In the attack stage, it firstly extracts active speech regions by
energy-based VAD [46], then performs frame-level stretching or squeezing to
the active spectrogram regions. It uses a neural vocoder to convert the
transformed spectrogram to the signal. Finally, it reassembles them with
silent clips to form the same speech length as the original. The final
operation helps the poison utterances behave like benign utterances to avoid
simple machine detection defense. Then, we will describe each step in detail.

####  3.3.1 Voice Active Detection

We used energy-based Voice Active Detection (VAD) to discriminate between
silent regions and active voice regions. Given a spectrogram
$X^{D,T}=\\{x_{i}\in R^{D}|i=1,2,...,T\\}$, the average energy of every frame
will be calculated as follows,

$\displaystyle E_{x}=\\{\frac{1}{D}\sum\limits^{D}_{j=1}x_{i}|i=1,2,...,T\\}$
(2)

We set a threshold $S_{e}=\mu*\max(E_{x})$ equal to $\mu$ times the maximum
value of $E_{x}$. It is noted that $\mu<1$. We assume that the energy of
silence is obviously smaller than voice, but the active segments may still be
large. Thus, the coefficient is set to close to one time. To avoid detecting
some short recording noise and shoddy sound to speech, we decide the vocal
continuous frames whose average energy values are upper than the threshold as
voice segment $X_{voi}$ as follows,

$X_{voi}=\\{x_{i}|E_{x}(i)\geq S_{e},i=m+1,m+2,...n\\}$ (3)

The $X_{voi}$ represents an active region in an utterance. We show an example
of the VAD result in Figure 4.

Figure 4: The VAD result. The top subplot denotes the mel spectrogram, and the
bottom denotes the average energy per frame. The red box highlights the non-
voice portion.

The blue curve in the subplot below Figure 4 indicates the value of the
average energy $E_{x}$. We have marked the position of the speech $X_{voi}$
with red coordinates. The segment highlighted by the red box shows a different
property to pure speech, observed as non-voice things, such as noise and
recording disorder.

####  3.3.2 RSRT Methods

The RSRT algorithm aims to change speech rhythm and connect different rhythms
with target labels, including stretching and squeezing operations. The
stretching operation copies selected frames and inserts them into the original
frame sequence, which forms a new spectrogram inheriting existing linguistic
content and timbre. The stretching operation is shown in Figure 3(a). The
squeezing operation uses a bilinear downsampling algorithm [47] to generate
news frames from single syllables. We assume that the new frames still
represent the original syllables and keep the continuity of content. The
squeezing operation is shown in Figure 3(b). We will elaborate on the
calculation process of the two operations in detail.

(1) Stretching: Given a spectrogram $X^{D,T}=\\{x_{i}|i=1,2,...,T\\}$ composed
of frames, where D is the number of frequency bins, and T is the number of
frames $x_{i}$. It assumes that the stretched spectrogram is
$Y_{s}=\\{y_{j}|j=1,2,...,T_{s}\\}$. Given a scale ratio parameter
$\gamma_{s}$ and frame repetition count $\sigma_{s}$, each new frame can be
derived by following algorithm 1:

Algorithm 1 Stretching algorithm

1:$\gamma_{s}\in[0,1]$, $\sigma_{s}>0$, $X=\\{x_{i}|i=1,2,..,T\\}$.

2:$T_{s}\leftarrow\lfloor(T+\gamma_{s}*T*\sigma_{s})\rfloor$

3:$Y_{s}\leftarrow\\{y_{j}=0|j=1,2,...,T_{s}\\}$.

4:$Old\\_index\leftarrow\\{i|i=1,2,...,T\\}$

5:$m\leftarrow 1$

6:while $!Empty(Old\\_index)$ do

7: $d\leftarrow RandomChoice(Old\\_index)$

8: $r\\_ind\leftarrow\\{d,d+1,d+2,...d+\sigma_{s}\\}$

9: $Y_{s}\left[r\\_ind\right]\leftarrow X[d]$

10: $m\leftarrow m+1$

11: if $m\geq T_{s}$ then

12: $break$

13: end if

14:end while

15:return $Y_{s}$

In the calculation, the algorithm selects the indexes of a $\gamma_{s}$
proportion of frames, which are repeated by $\sigma_{s}$ times. Thus, the
length of frames in $Y_{s}$ is extended to
$\lfloor(T+\gamma_{s}*T*\sigma_{s})\rfloor$.

(2) Squeezing: It is worth mentioning that maintaining the continuity of the
spectrogram is crucial in our proposed squeezing algorithm. As seen in the
stretching algorithm, each frame of the $Y_{s}$ spectrogram maintains
continuity. Therefore, when choosing those frames to squeeze, we must maintain
the same continuity by avoiding randomly choosing the indexes but following an
arithmetic sequence that starts from 0, ends at $T$, and has a common
difference of $\phi_{c}$. We believe that using a bilinear downsampling
algorithm can maintain the continuity of the speech spectrogram.

Given a spectrogram $X$ like above, it is assumed that the squeezed
spectrogram is $Y_{c}=\\{y_{k}|k=1,2,...,T_{c}\\}$. Given a common difference
parameter $\phi_{c}$ and bilinear weight $w$, each new frame can be derived by
following algorithm 2:

Algorithm 2 squeezing algorithm

1:$\phi_{c}\geq 2$, $X=\\{x_{i}|i=1,2,..,T\\}$.

2:$down\\_index\leftarrow\\{D_{k}=\phi_{c}*(k-1)+1|k=1,2,...,N.D_{k}\leq T\\}$
$\triangleright$ arithmetic sequence of indexes

3:$down\\_next\leftarrow down\\_index+1$

4:$X\left[down\\_index\right]\leftarrow(1-w)*X\left[down\\_index\right]+w*X\left[down\\_next\right]$

5:$nd\leftarrow\left[\\{1,2,...,T\\}-down\\_next\right]$

6:$X\leftarrow X\left[nd\right]$

7:return $X$

In the spectrogram squeezing algorithm, we selected a series of indexes of
some frames in the order of an arithmetic sequence, whose common difference is
$\phi_{c}$. Then we replaced these frames at the positions of these indexes
with the sum of their bilinear weights with the frame following them. The
length of new $X$ is about scaled to $(1-\frac{1}{\phi_{c}})*T$. The examples
of RSRT are shown in Figure 3. We set a series of parameters to stretch a
clean utterance from 1.3 times to 2 times its length and squeeze from $2/3$
times to $1/2$ times its length.

####  3.3.3 Vocoder Conversion

The conversion stage aims to convert the stretched or squeezed spectrogram to
a signal, maintaining consistency in speech content and timbre. It’s worth
noting that the signal parameters(e.g. sample rate, hop length) for
spectrogram extraction used in both the vocoder training and speech
recognition training need to be equal, ensuring that the speech generated by
our trigger can be restored without lack of sample rate and quality.

####  3.3.4 Silence Concatenation

It is observed that many utterances in the dataset have non-voice things like
noise or recording disorder, as Figure 4 shows. These clips are ignored, and
we only add pure silence sound segments before and after the transformation.
In addition, we kept the duration of the poisoned samples the same as the
original samples.

##  4 Experiments and Results

We evaluate the proposed attack pipeline on KWS and TSER experiments. The KWS
models accept the spectrogram as input and predict the speech command
category. The TSER models accept the same input and output the speech emotion
category.

###  4.1 Experimental Setting for KWS Task

Dataset: We use the Google Speech Commands Dataset v2 [48] as our experimental
materials. The dataset contains more than 65,000 audios of 35 categories of
keywords that can be used for keyword-spotting devices. In our experiments,
23,682 audios of 10 categories(“yes,” “no,” “up,” “down,” “left,” “right,”
“on,” “off,” “stop,” and “go”) are used. We divide the dataset into the
training, validation, and test sets in a ratio of 95:5:5, where the validation
set belongs to the training set. The poisoned samples only exist in the
training set.

Victim models: Our experiments were performed on the following four KWS
networks: Resnet-34 [49], Attention-LSTM [50], KWS-ViT [51], EAT-S [52], they
behave excellent classification performance on the keyword spotting task.

Baseline and Attack Setup: We compare our attack with the latest speech
backdoor attacks. They are listed as follows. (1) backdoor attack with pixel
pattern(BadNets) [3], (2) position-independent backdoor attack(PIBA) [9], (3)
dual adaptive backdoor attack(DABA) [13], (4) ultrasonic voice as
trigger(Ultrasonic) [10], (5) pitch boosting and sound masking(PBSM) [17], and
(6) voiceprint selection and voice conversion(VSVC) [16].

In our RSRT method, We set $\sigma_{s}=1$ and $\gamma_{s}=\\{0.5,1.0\\}$ for
stretching the original duration to $\\{1.5,2.0\\}$ times. We set
$\phi_{c}=\\{2,3\\}$ and bilinear weight $w=0.6$ for squeezing the original
duration to $\\{\frac{1}{2},\frac{2}{3}\\}$ times. In the stage of VAD, the
threshold coefficient is set to 0.85.

Training Setup: We trained all the victim models with the same hyper-
parameters. The batch size is 64. The weights are optimized by Adam optimizer
with a learning rate of 1e-4 and cross-entropy loss function. We trained 30
epochs to make all models converge.

Table 2: Evaluation of backdoor attack methods on KWS task. Each item shows the $AV/ASR/PN$ in the table.  | KWS Models
---|---
Trigger | Resnet-34 | Attention-LSTM | KWS-ViT | EAT-S
BadNets | 1.97/96.48/300 | 2.04/97.05/300 | 2.15/96.66/350 | 2.68/96.67/350
PIBA | 2.68/94.21/300 | 2.92/93.58/350 | 3.15/94.62/350 | 3.61/93.59/350
DABA | 3.65/93.25/450 | 4.21/92.52/400 | 3.91/92.55/450 | 4.55/93.45/450
Ultrasonic | 1.24/95.42/400 | 1.56/96.41/400 | 1.72/93.57/450 | 1.64/95.64/450
PBSM | 0.78/99.95/300 | 0.82/99.85/300 | 0.97/99.76/400 | 0.69/99.85/400
VSVC | 0.51/99.98/250 | 0.50/99.97/250 | 0.67/99.92/300 | 0.56/99.93/250
RSRT(Stretch) | 0.48/99.97/150 | 0.60/99.97/150 | 0.65/99.94/200 | 0.47/99.95/200
RSRT(Squeeze) | 0.61/99.93/150 | 0.55/99.93/200 | 0.51/99.91/150 | 0.61/99.96/200
Table 3: Evaluation of backdoor attack methods on TSER task. Each item shows the $AV/ASR/PN$ in the table. | TSER Models
---|---
Trigger | AST | SER-AC | SER-CNN
BadNets | 3.78/92.14/550 | 4.20/93.15/500 | 3.82/94.15/500
PIBA | 4.05/95.62/500 | 4.65/96.14/500 | 4.17/97.15/500
DABA | 3.64/98.65/450 | 4.02/98.72/400 | 4.12/98.56/400
Ultrasonic | 2.67/97.82/350 | 2.92/97.68/400 | 3.01/96.92/400
PBSM | 0.97/99.58/450 | 0.96/99.67/400 | 0.98/99.72/400
VSVC | 0.98/99.94/350 | 0.92/99.97/400 | 0.93/99.94/400
RSRT(Stretch) | 1.09/99.87/250 | 1.31/99.89/250 | 1.61/99.25/200
RSRT(Squeeze) | 1.22/99.86/200 | 1.56/99.69/200 | 1.42/99.25/250

###  4.2 Experimental Setting for TSER Task

Dataset: We used two speech emotion datasets, Emotional Speech Dataset (ESD)
[53] for the TSER task. The ESD dataset consists of 350 parallel utterances
spoken by 10 native English and 10 native Chinese speakers and covers 5
emotion categories (neutral, happy, angry, sad, and surprise). We only use ESD
samples from a single language for training.

Victim models: Our experiments were performed on signal process deep neural
models. We choose AST [54], SER-AC [55] and SER-CNN [56]. These models use
only signal information to learn emotional classification and reach effective
performance.

Baseline and Attack Setup: We set the same proposed attacking configuration as
the KWS task.

Training Setup: We trained all the victim models with AST’s hyperparameters.
The batch size is 12. The weights are optimized by Adam optimizer with a
learning rate of 1e-5 and cross-entropy loss function. The learning rate is
cut into half every epoch after the 2nd epoch. We trained 30 epochs to make
all models converge.

###  4.3 Evaluation Metrics

Evaluation metrics reflect the stealthiness and effectiveness of the proposed
trigger.

Attack Metrics: [57] We mainly consider attack success rate (ASR), accuracy
variance (AV), and poisoned number (PN). The backdoor attackers aim to achieve
the highest possible attack success rate with minimal poisoning rate and
accuracy variance.

Stealthiness Metrics: To ensure the speech components except rhythm are
consistent. We use timbre consistency rate (TCR) and word error rate(WER) [58]
to measure the ratio that poisoned samples keep the timbre and content
consistent. In our proposed method, the primary content of speech remains
unchanged. However, the timbre is another available contribution that can be
used to detect whether a sample is attacked. Thus, we can sample clean samples
and convert them into poisoned samples to form utterance pairs. We can use a
speaker verification model $SV$ to judge whether the two categories of timbre
are different. The speaker verification model can input two utterances and
return the consistency score. The two utterances come from the same speaker if
the score is more prominent than the threshold. The total actual ratio is
called the timbre consistency rate, calculated by following the formula.

$e_{1}=SV(x),e_{2}=SV(y)$ (4)

$sc=E(e_{1}*e_{2}^{T})$ (5)

$Score(x,y)=\begin{cases}1&sc>=threshold\\\ 0&sc<threshold\end{cases}$ (6)

$TCR=\frac{\mathcal{I}(Score(x_{i},\mathcal{F}_{t}(x_{i})))}{N_{c}}\in D_{e}$
(7)

On the other hand, WER is a common metric to compare the difference in speech
content between predicted and ground truth words. We use the latest SV system
ERes2Net [59] for TCR evaluation, and the accepted score threshold is set to
$0.70$. We also used paraformer [60] for WER evaluation with its open-source
code.

###  4.4 Main Results.

####  4.4.1 Attack Results

Tables 2 and 3 show the main results of backdoor attack evaluation on KWS and
TSER tasks. Table 4 shows the timbre consistency evaluation result. We
randomly select 500 clean samples in the test dataset and generate poisoned
samples with all triggers. We compare the main evaluation metrics, which
include AV, ASR, and PN. In the experiments, we found that all the ASR values
will increase with the increase of PN values, ultimately approaching $100\%$.
Thus, the tables show all the highest ASR values in the tables with the
highest PN. The stretching ratio is $2.0$, and the squeezing ratio is $0.5$ in
Tables 2 and 3. Then, we will first analyze our method.

In the proposed stretching and squeezing results, the PN values are less or
equal to 200 in all cases of the proposed method. However, the PN values of
other methods are all greater than 200. It is noted that 500 poisoned samples
equals about $2.9\%$ and $0.4\%$ poisoning rate. In conclusion, our proposed
method has excellent stealthiness due to the low poisoning rate and high
attack success rate. Because our proposed method changes the speech rhythm
while keeping the content, timbre, and emotion unchanged. The AV results are
also smaller than most of the baselines.

Next, we analyze the evaluation results of the baseline methods. The triggers
can be classified in two ways. One is adding noisy clips to clean speech
utterances or incorporating spectrograms using special patterns. These
triggers are BadNets, PIBA, DABA, and Ultrasonic as shown in Figure 5(d-e). On
the other hand, triggers (PBSM and VSVC), as shown in Figure 5(e-f), change a
single speech component and keep excepted components unchanged. The BadNets
trigger has a very high AV and a decent ASR in two tasks. That is to say, it
has good effectiveness but decent stealthiness. Because the trigger adds a
tiny pixel-level single pattern to a benign spectrogram, it can not influence
the whole recognition of the utterance.

PIBA, DABA, and Ultrasonic triggers make complex incorporation into
spectrograms. Due to extreme spectrogram modification in specific time-
frequency domain. The AV and ASR values are both high. However, these methods
require a high poisoning number for the model not to recognize them as noise.
During the early stages of neural network training, they may still be regarded
as noise, leading to disruption of emotion and speech quality, thus affecting
the learning ability of the model from the outset and ultimately resulting in
poorer training outcomes.

The VSVC trigger can change the timbre of speech to an attacker-specified
target timbre in the training set while the content and rhythm stay the same.
With non-parallel and GAN training, the voice-converted poisoned utterances
are of good quality, so the AV values are both great. This trigger associates
speech of specific timbre with target labels, while the KWS and TSER tasks are
independent of timbre recognition. Therefore, this method also has high ASR
results. However, training a voice conversion neural network is time-
consuming, and not robust enough. Because the defender can first back up some
utterances in their database as ”timbre private keys.” Before the training
phase, these can be compared with all data in the dataset(equivalent to public
keys) with a speaker verification system to detect the presence of voice
conversion backdoor attacks.

The PBSM trigger boosts the pitch of speech and masks the boosted voice with a
masking sound to form a peak sound as a poisoned sample. This operation also
slightly degrades the speech’s quality, which leads to low AV values and a
good poisoning rate. However, the change of pitch is easy to be detected by
the signal algorithm. Thus, Our proposed method generally exhibits optimal
performance in both stealthiness and effectiveness.

####  4.4.2 Stealthiness Evaluation Results

Table 4 shows all the evaluations of speech backdoor methods’ TCR and WER. We
also show mel spectrograms with different triggers in Figure 5. As shown in
Table 4. We use baseline and proposed triggers in the evaluation to form an
utterance pair. Then, we test whether the clean and poisoned ones can be
derived from the same speaker and content by a speaker verification system and
automatic speech recognition system. Our proposed method can retain the
content and timbre well, while the TCR and WER are close to $1$ and $0$ in
stretching or squeezing operations. The VSVC trigger gets very low TCR and
high TCR because the timbre converts completely. The PBSM trigger does not
change timbre but slightly destroys speech quality. Thus, the WER result is
not better than our proposed method’; The other triggers cause significant
damage to speech quality, resulting in lower TCR and WER. Generally, the
methods that keep timbre and content unchanged can deceive automatic deep
detection and gain good stealthiness.

Table 4: The stealthiness evaluation with all triggers. Trigger | TCR($\%$) | WER($\%$)
---|---|---
BadNets | 92.8 | 1.46
PIBA | 78.7 | 19.5
DABA | 56.7 | 23.1
Ultrasonic | 86.7 | 10.5
PBSM | 93.6 | 2.67
VSVC | 0.941 | 1.24
RSRT(Stretch) | 98.7 | 1.05
RSRT(Squeeze) | 97.6 | 1.25
Figure 5: The mel spectrogram visualization of different poison samples with
mentioned triggers. The (b) and (c) show our proposed triggers. The (d)-(e)
shows the audio clip backdoor attacks. The (e) and (f) shows the speech
components backdoor attacks.

###  4.5 Ablation Study

In this section, we discuss the effect of hyper-parameters in our attack. The
key hyper-parameters are the ratios of rhythm transformation and poisoning
number. We can control the selected frames and copy times in the RSRT
operations to produce different lengths of poisoned utterances. The RSRT ratio
is equal to the stretched or squeezed length divided by the origin length.
Each experiment is repeated three times to reduce the effect of randomness.

Effects of Poisoning Number: We replace the poisoning rate with the poisoning
number because our proposed trigger is effective and needs a very low number
of poisoning samples. The poisoning rate corresponding to 50 samples is
$0.22\%$. As shown in Table 5, the ASR increases with the increase in the
number of poisoning number in general. It is indicated that in cases of low
poisoning rates, compared to squeezing.

Effects of Rhythm Transformation Ratio: The best effectiveness is shown in the
set of $0.5$ and $1.5$ rhythm transformation ratios. With squeezing, a
relatively low poisoning number of 150 can achieve an excellent attack success
rate of $99.97\%$. With stretching, a relatively low poisoning number of 150
can achieve an excellent attack success rate of $99.10\%$. The squeezing ASR
values under each poisoned number are obviously higher than the stretching
ones. This also indicates that squeezing behaves better than stretching.

Table 5: Ablation study. The ASR with different hyper-parameters | Poisoned number
---|---
RSRT ratio | 50 | 100 | 150 | 200
Squeeze(1/2) | 87.56 | 93.45 | 99.97 | 1.0
Squeeze(2/3) | 89.92 | 95.52 | 97.75 | 1.0
Stretch(1.2) | 10.67 | 65.67 | 78.91 | 86.75
Stretch(1.5) | 86.72 | 91.45 | 98.91 | 1.0
Stretch(2.0) | 77.99 | 87.85 | 99.10 | 1.0

##  5 Conclusion

The paper proposed a speech backdoor attack method, combining mainly VAD, RSRT
and neural vocoder. This method achieves very high ASR while maintaining a
very low poisoning rate. The proposed trigger can avoid two kinds of main
detection by speaker verification system and automatic speech recognition and
gains excellent stealthiness and speech quality. The experiments demonstrate
the excellent performance of efficiency and stealthiness of speech backdoor
attacks with our method. We think that changing the rhythm or speech
components of speech is an exploratory new approach to speech backdoor
attacks.

## References

  * [1] M. Anusuya, S. K. Katti, Speech recognition by machine, a review, arXiv preprint arXiv:1001.2267 (2010).
  * [2] Y. Gao, B. G. Doan, Z. Zhang, S. Ma, J. Zhang, A. Fu, S. Nepal, H. Kim, Backdoor attacks and countermeasures on deep learning: A comprehensive review, arXiv preprint arXiv:2007.10760 (2020).
  * [3] T. Gu, K. Liu, B. Dolan-Gavitt, S. Garg, Badnets: Evaluating backdooring attacks on deep neural networks, IEEE Access 7 (2019) 47230–47244.
  * [4] A. Turner, D. Tsipras, A. Madry, Label-consistent backdoor attacks, arXiv preprint arXiv:1912.02771 (2019).
  * [5] J. Dai, C. Chen, Y. Li, A backdoor attack against lstm-based text classification systems, IEEE Access 7 (2019) 138872–138878.
  * [6] X. Pan, M. Zhang, B. Sheng, J. Zhu, M. Yang, Hidden trigger backdoor attack on $\\{$NLP$\\}$ models via linguistic style manipulation, in: 31st USENIX Security Symposium (USENIX Security 22), 2022, pp. 3611–3628.
  * [7] C. Chen, J. Dai, Mitigating backdoor attacks in lstm-based text classification systems by backdoor keyword identification, Neurocomputing 452 (2021) 253–262.
  * [8] T. Zhai, Y. Li, Z. Zhang, B. Wu, Y. Jiang, S.-T. Xia, Backdoor attack against speaker verification, in: ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2021, pp. 2560–2564.
  * [9] C. Shi, T. Zhang, Z. Li, H. Phan, T. Zhao, Y. Wang, J. Liu, B. Yuan, Y. Chen, Audio-domain position-independent backdoor attack via unnoticeable triggers, in: Proceedings of the 28th Annual International Conference on Mobile Computing And Networking, 2022, pp. 583–595.
  * [10] S. Koffas, J. Xu, M. Conti, S. Picek, Can you hear it? backdoor attacks via ultrasonic triggers, in: Proceedings of the 2022 ACM workshop on wireless security and machine learning, 2022, pp. 57–62.
  * [11] Y. Kong, J. Zhang, Adversarial audio: A new information hiding method and backdoor for dnn-based speech recognition models, arXiv preprint arXiv:1904.03829 (2019).
  * [12] J. Ye, X. Liu, Z. You, G. Li, B. Liu, Drinet: dynamic backdoor attack against automatic speech recognization models, Applied Sciences 12 (12) (2022) 5786.
  * [13] Q. Liu, T. Zhou, Z. Cai, Y. Tang, Opportunistic backdoor attacks: Exploring human-imperceptible vulnerabilities on speech recognition systems, in: Proceedings of the 30th ACM International Conference on Multimedia, 2022, pp. 2390–2398.
  * [14] Y. Luo, J. Tai, X. Jia, S. Zhang, Practical backdoor attack against speaker recognition system, in: International Conference on Information Security Practice and Experience, Springer, 2022, pp. 468–484.
  * [15] Z. Ye, T. Mao, L. Dong, D. Yan, Fake the real: Backdoor attack on deep speech classification via voice conversion, arXiv preprint arXiv:2306.15875 (2023).
  * [16] H. Cai, P. Zhang, H. Dong, Y. Xiao, S. Ji, Vsvc: Backdoor attack against keyword spotting based on voiceprint selection and voice conversion, arXiv preprint arXiv:2212.10103 (2022).
  * [17] H. Cai, P. Zhang, H. Dong, Y. Xiao, S. Ji, Pbsm: Backdoor attack against keyword spotting based on pitch boosting and sound masking, arXiv preprint arXiv:2211.08697 (2022).
  * [18] H. Cai, P. Zhang, H. Dong, Y. Xiao, S. Koffas, Y. Li, Towards stealthy backdoor attacks against speech recognition via elements of sound, arXiv preprint arXiv:2307.08208 (2023).
  * [19] C. H. Chan, K. Qian, Y. Zhang, M. Hasegawa-Johnson, Speechsplit2. 0: Unsupervised speech disentanglement for voice conversion without tuning autoencoder bottlenecks, in: ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2022, pp. 6332–6336.
  * [20] D. Wang, L. Deng, Y. T. Yeung, X. Chen, X. Liu, H. Meng, Vqmivc: Vector quantization and mutual information-based unsupervised speech representation disentanglement for one-shot voice conversion, arXiv preprint arXiv:2106.10132 (2021).
  * [21] A. De Cheveigné, H. Kawahara, Yin, a fundamental frequency estimator for speech and music, The Journal of the Acoustical Society of America 111 (4) (2002) 1917–1930.
  * [22] K. Qian, Y. Zhang, S. Chang, M. Hasegawa-Johnson, D. Cox, Unsupervised speech decomposition via triple information bottleneck, in: International Conference on Machine Learning, PMLR, 2020, pp. 7836–7846.
  * [23] P. Govalkar, J. Fischer, F. Zalkow, C. Dittmar, A comparison of recent neural vocoders for speech signal reconstruction, in: Proc. 10th ISCA speech synthesis workshop, 2019, pp. 7–12.
  * [24] J. Lorenzo-Trueba, T. Drugman, J. Latorre, T. Merritt, B. Putrycz, R. Barra-Chicote, A. Moinet, V. Aggarwal, Towards achieving robust universal neural vocoding, arXiv preprint arXiv:1811.06292 (2018).
  * [25] W. Guo, B. Tondi, M. Barni, An overview of backdoor attacks against deep neural networks and possible defences, IEEE Open Journal of Signal Processing 3 (2022) 261–287.
  * [26] Y. Liu, X. Ma, J. Bailey, F. Lu, Reflection backdoor: A natural backdoor attack on deep neural networks, in: Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part X 16, Springer, 2020, pp. 182–199.
  * [27] B. Wang, Y. Yao, S. Shan, H. Li, B. Viswanath, H. Zheng, B. Y. Zhao, Neural cleanse: Identifying and mitigating backdoor attacks in neural networks, in: 2019 IEEE Symposium on Security and Privacy (SP), IEEE, 2019, pp. 707–723.
  * [28] E. Chou, F. Tramer, G. Pellegrino, Sentinet: Detecting localized universal attacks against deep learning systems, in: 2020 IEEE Security and Privacy Workshops (SPW), IEEE, 2020, pp. 48–54.
  * [29] Y. Dong, X. Yang, Z. Deng, T. Pang, Z. Xiao, H. Su, J. Zhu, Black-box detection of backdoor attacks with limited information and data, in: Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021, pp. 16482–16491.
  * [30] S. Zhao, X. Ma, X. Zheng, J. Bailey, J. Chen, Y.-G. Jiang, Clean-label backdoor attacks on video recognition models, in: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2020, pp. 14443–14452.
  * [31] Z. Shen, W. Hou, Y. Li, Cssba: A clean label sample-specific backdoor attack, in: 2023 IEEE International Conference on Image Processing (ICIP), IEEE, 2023, pp. 965–669.
  * [32] X. Chen, C. Liu, B. Li, K. Lu, D. Song, Targeted backdoor attacks on deep learning systems using data poisoning, arXiv preprint arXiv:1712.05526 (2017).
  * [33] K. Eykholt, I. Evtimov, E. Fernandes, B. Li, A. Rahmati, C. Xiao, A. Prakash, T. Kohno, D. Song, Robust physical-world attacks on deep learning visual classification, in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2018, pp. 1625–1634.
  * [34] E. Sarkar, H. Benkraouda, M. Maniatakos, Facehack: Triggering backdoored facial recognition systems using facial characteristics, arXiv preprint arXiv:2006.11623 (2020).
  * [35] A. Turner, D. Tsipras, A. Madry, Clean-label backdoor attacks, IEEE INFOCOM 2021 - International Conference on Learning Representations (2018).
  * [36] W. Guo, L. Wang, Y. Xu, X. Xing, M. Du, D. Song, Towards inspecting and eliminating trojan backdoors in deep neural networks, in: 2020 IEEE International Conference on Data Mining (ICDM), IEEE, 2020, pp. 162–171.
  * [37] J. Zhang, C. Dongdong, Q. Huang, J. Liao, W. Zhang, H. Feng, G. Hua, N. Yu, Poison ink: Robust and invisible backdoor attack, IEEE Transactions on Image Processing 31 (2022) 5691–5705.
  * [38] E. Bagdasaryan, A. Veit, Y. Hua, D. Estrin, V. Shmatikov, How to backdoor federated learning, in: International conference on artificial intelligence and statistics, PMLR, 2020, pp. 2938–2948.
  * [39] E. Bagdasaryan, V. Shmatikov, Blind backdoors in deep learning models, in: 30th USENIX Security Symposium (USENIX Security 21), 2021, pp. 1505–1521.
  * [40] K. Doan, Y. Lao, W. Zhao, P. Li, Lira: Learnable, imperceptible and robust backdoor attacks, in: Proceedings of the IEEE/CVF international conference on computer vision, 2021, pp. 11966–11976.
  * [41] T. A. Nguyen, A. Tran, Input-aware dynamic backdoor attack, Advances in Neural Information Processing Systems 33 (2020) 3454–3464.
  * [42] E. Wenger, J. Passananti, A. N. Bhagoji, Y. Yao, H. Zheng, B. Y. Zhao, Backdoor attacks against deep learning systems in the physical world, in: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2021, pp. 6206–6215.
  * [43] Y. Li, T. Zhai, Y. Jiang, Z. Li, S.-T. Xia, Backdoor attack in the physical world, arXiv preprint arXiv:2104.02361 (2021).
  * [44] J. Kong, J. Kim, J. Bae, Hifi-gan: Generative adversarial networks for efficient and high fidelity speech synthesis, Advances in Neural Information Processing Systems 33 (2020) 17022–17033.
  * [45] S. Koffas, L. Pajola, S. Picek, M. Conti, Going in style: Audio backdoors through stylistic transformations, in: ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2023, pp. 1–5.
  * [46] J. Pang, Spectrum energy based voice activity detection, in: 2017 IEEE 7th Annual Computing and Communication Workshop and Conference (CCWC), 2017, pp. 1–5.  doi:10.1109/CCWC.2017.7868454.
  * [47] R. Dugad, N. Ahuja, A fast scheme for downsampling and upsampling in the dct domain, in: Proceedings 1999 International Conference on Image Processing (Cat. 99CH36348), Vol. 2, IEEE, 1999, pp. 909–913.
  * [48] P. Warden, Speech commands: a public dataset for single-word speech recognition (2017), Dataset available from http://download. tensorflow. org/data/speech_commands_v0 1 (2017).
  * [49] K. He, X. Zhang, S. Ren, J. Sun, Deep residual learning for image recognition, in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.
  * [50] Y. Qin, D. Song, H. Chen, W. Cheng, G. Jiang, G. Cottrell, A dual-stage attention-based recurrent neural network for time series prediction, arXiv preprint arXiv:1704.02971 (2017).
  * [51] A. Berg, M. O’Connor, M. T. Cruz, Keyword transformer: A self-attention model for keyword spotting, arXiv preprint arXiv:2104.00769 (2021).
  * [52] A. Gazneli, G. Zimerman, T. Ridnik, G. Sharir, A. Noy, End-to-end audio strikes back: Boosting augmentations towards an efficient audio classification network, arXiv preprint arXiv:2204.11479 (2022).
  * [53] K. Zhou, B. Sisman, R. Liu, H. Li, Emotional voice conversion: Theory, databases and esd, Speech Communication 137 (2022) 1–18.
  * [54] Y. Gong, Y.-A. Chung, J. Glass, Ast: Audio spectrogram transformer, arXiv preprint arXiv:2104.01778 (2021).
  * [55] Y. Zhang, J. Du, Z. Wang, J. Zhang, Y. Tu, Attention based fully convolutional network for speech emotion recognition, in: 2018 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), IEEE, 2018, pp. 1771–1775.
  * [56] D. Issa, M. F. Demirci, A. Yazici, Speech emotion recognition with deep convolutional neural networks, Biomedical Signal Processing and Control 59 (2020) 101894.
  * [57] Y. Li, Y. Jiang, Z. Li, S.-T. Xia, Backdoor learning: A survey, IEEE Transactions on Neural Networks and Learning Systems (2022).
  * [58] Y. Park, S. Patwardhan, K. Visweswariah, S. C. Gates, An empirical analysis of word error rate and keyword error rate., in: Interspeech, Vol. 2008, 2008, pp. 2070–2073.
  * [59] Y. Chen, S. Zheng, H. Wang, L. Cheng, Q. Chen, J. Qi, An enhanced res2net with local and global feature fusion for speaker verification, arXiv preprint arXiv:2305.12838 (2023).
  * [60] Z. Gao, S. Zhang, I. McLoughlin, Z. Yan, Paraformer: Fast and accurate parallel transformer for non-autoregressive end-to-end speech recognition, arXiv preprint arXiv:2206.08317 (2022).


affil0affil0affiliationtext: Physics Department, California Polytechnic State
University,
San Luis Obispo, California 93407, USA

# Step-by-Step Canonical Quantum Gravity:
Part I: Ashtekar’s New Variables

Lei<EMAIL_ADDRESS>Philip A<EMAIL_ADDRESS>
###### Abstract

affil0affil0affiliationtext: Physics Department, California Polytechnic State
University,
San Luis Obispo, California 93407, USA


# Bayes Classification using an approximation to the Joint Probability
Distribution of the Attributes

Patrick Hosein
Department of Computer Science
The University of the West Indies
St. Augustine, Trinidad
<EMAIL_ADDRESS>
& Kevin Baboolal
Department of Computer Science
The University of the West Indies
St. Augustine, Trinidad
<EMAIL_ADDRESS>

###### Abstract

The Naive-Bayes classifier is widely used due to its simplicity, speed and
accuracy. However this approach fails when, for at least one attribute value
in a test sample, there are no corresponding training samples with that
attribute value. This is known as the zero frequency problem and is typically
addressed using Laplace Smoothing. However, Laplace Smoothing does not take
into account the statistical characteristics of the neighbourhood of the
attribute values of the test sample. Gaussian Naive Bayes addresses this but
the resulting Gaussian model is formed from global information. We instead
propose an approach that estimates conditional probabilities using information
in the neighbourhood of the test sample. In this case we no longer need to
make the assumption of independence of attribute values and hence consider the
joint probability distribution conditioned on the given class which means our
approach (unlike the Gaussian and Laplace approaches) takes into consideration
dependencies among the attribute values. We illustrate the performance of the
proposed approach on a wide range of datasets taken from the University of
California at Irvine (UCI) Machine Learning Repository. We also include
results for the $k$-NN classifier and demonstrate that the proposed approach
is simple, robust and outperforms standard approaches.

_Keywords_ Naive Bayes $\cdot$ Classification $\cdot$ Machine Learning $\cdot$
Bayes Classifier $\cdot$ $k$-NN Classifier

##  1 Introduction

Machine Learning Classifiers are regularly used to solve a wide range of
classification problems. Several techniques are available ($k$-NN, XG-Boost,
Singular Value Decomposition, Neural Networks, etc.) but we focus on the Naive
Bayes Classifier. This classifier is simple, the results can be interpreted
(i.e., explainable) and its performance is quite good. However, it has two
major drawbacks, the assumption of independence of attribute values and the
zero-frequency problem. The latter problem is normally addressed using Laplace
Smoothing or through the use of Gaussian Naive Bayes. We propose an approach
in which the zero frequency problem is avoided by instead approximating the
conditional probability using samples in the neighbourhood of the test sample.
In fact our approach does not need to make the independence assumption used
for Naive Bayes and so is able to capture dependencies among attributes.

In the next section we describe related work and compare those with our
contributions. We also illustrate our classifier using a simple illustrative
example. We then use several datasets to compare the proposed classifier with
Naive Bayes with Laplace Smoothing, Gaussian Naive Bayes and finally the
$k$-NN Classifier. Finally we discuss issues such as computational
complexities and why we believe that our classifier may be of benefit to the
community.

##  2 Related Work and Contributions

We first note that our approach is related to a Parzen-Window estimator
(Parzen (1962)) but with two differences. Firstly, in our approach there is no
dependence on the number of samples (as with the Parzen-Window Kernel).
Secondly, our approach uses a single hyper-parameter unlike the non-parametric
Parzen-Window estimator. However, we will show that the optimal parameter
value of our approach is dependent on the number of samples (as well as other
properties of the dataset) and so in future work we will investigate this
dependency. The corresponding Parzen-Window Kernel in our approach, for given
test sample $\mathbf{x}$ and training sample $\mathbf{x}_{i}$ with $n$ samples
can be written in this form

$\delta_{n}=\frac{1}{(||\mathbf{x}-\mathbf{x}_{i}||_{2})^{\kappa}}$ (1)

where $\kappa>0$ is the tuning parameter. The results in this paper are
obtained by searching over $\kappa$ since we are still in the process of
determining its dependence on $n$.

The related literature on Naive-Bayes classification can generally be sorted
into four categories - structure extension, feature selection, attribute
weighting and local learning. As described previously, one drawback of the
Naive-Bayes algorithm is the attribute independence assumption. Structure
extension tackles this problem by determining feature or attribute
dependencies. Often, approaches utilize the factor graph representation of
probability distributions to depict the Bayesian network. Learning the optimal
Bayesian network is regarded as an intractable problem and researchers usually
employ techniques to reduce the complexity. One such method is described in
Friedman et al. (1997) where the author uses a directed graph to represent the
distribution. They refer to this method as Tree Augmented Naive Bayes or TAN.
The structure of the TAN graph is limited in that features can have at most
two parents, one parent must be the class and the other parent can be an
attribute. These constraints reduce the complexity of learning and the problem
formulates as $p(C=c|\mathbf{X}=[X_{1},X_{2},\ldots,X_{n}])$ with learning
occurring in polynomial time. TAN allows for edges between child vertices
(attributes), and hence creates dependencies between attributes, reducing the
independence assumption of the Naive-Bayes classifier.

An extension of the TAN method is developed in Jiang et al. (2009) and is
called the Hidden Naive Bayes method. The authors add a parent vertex to every
attribute called a hidden parent. The degree of the vertex is maintained at
two thus limiting computational complexity. The hidden parent is computed such
that it represents the influences of all other attributes and a weight is used
to represent the importance of an attribute. The optimal class is the one
which maximizes $p(c)*\Pi p(a_{i}|a_{hpi},c)$ where $a_{hpi}$ represents the
calculated hidden parent. $\Pi\ p(a_{i}|a_{hpi},c)$ is given by $\Pi\
p(a_{i}|a_{j},c)*w_{i,j}$. The weights $w_{i,j}$ are calculated from the
conditional mutual information of $p(a_{i};a_{j}|C)$.

The authors in Yu et al. (2021) builds on the work of the Hidden Naive Bayes
model and uses instance weighting to achieve higher accuracy. The Hidden Naive
Bayes model treats every instance with equal importance which may not always
hold true as different instances could have different contributions. They
create discriminative instance weights to improve performance. Weights are
applied in the calculation of the conditional mutual information of
$p(X_{i};X_{j}|C)$ and the prior probabilities $p(C)$. The authors opt for an
eager learning method to reduce computational complexity and use frequency-
based instance weighting.

Feature selection is characterized by the determination of a feature subset
based on the available feature space. Feature selection is important for the
removal of redundant or uninformative features in the Naive-Bayes algorithm,
which is particularly sensitive to redundant features by virtue of its
computation. To demonstrate this, take a Naive Bayes classifier with two
features $[X_{1},X_{2}]$. The Classifier function to be maximized can be
written as $p(C_{i})p(X_{1}|C_{i})p(X_{2}|C_{i})$ if we add another feature
that is redundant to feature $X_{2}$ our classifier function is now given by
$p(C_{i})p(X_{1}|C_{i})p(X_{2}|C_{i})^{2}$, therefore the classifier becomes
biased. The class of Naive-Bayes algorithms that adopt feature selection for
performance boost is mainly a Naive-Bayes algorithm with a prepossessing step
that improves the classifiers performance. Langley and Sage (1994) explores
the method of feature selection, with a greedy search algorithm through the
feature space that seeks to eliminate redundant attributes and improve the
overall accuracy.

Attribute weighting involves the assignment of weights to features to mitigate
the independence assumption of the Naive-Bayes classifier. This can be
accomplished through scoring of the attributes with a classifier for
evaluation. Alternatively, heuristics can be used to determine the
characteristics of the attributes and an associated weight. In Lee et al.
(2011) the authors present one such application where the classification
decision is given from maximizing $p(c)\Pi p(a_{i}|c)^{w_{i}}$. The attribute
weight, $w_{i}$ is determined from the Kullback-Leibler divergence and
represents the dissimilarity between the a-priori and posteriori
probabilities. A high dissimilarity means that a feature would be useful.
Building on the work of Lee et al. (2011) the authors of Lee-Kien Foo (2022)
use an exponential weighting scheme per feature.

Local learning employs the use of localized data to compute probabilities of
the Naive-Bayes algorithm. Xie et al. (2002) computes multiple Naive-Bayes
classifiers for multiple neighborhoods using different radii from the test
object. The most accurate Naive-Bayes classifier is then used for classifying
the new object. The aforementioned method bears close similarity to the
$K$-Nearest Neighbors ($k$-NN) classification but differs from $k$-NN by
replacing the majority vote classification with a Naive-Bayes classifier. The
method presented in our paper also makes use of distance similarity as in
$k$-NN but our method remains generative whereas $k$-NN is discriminative. In
Gweon et al. (2019) the authors also use distance information to estimate
conditional probabilities but they only consider the $k$ nearest neighbours as
in the $k$-NN classifier and no weighting is performed as in our approach.
They show accuracy improvements for some datasets when compared to other
models such as $k$-NN.

Another example of locally weighted learning is presented in Frank et al.
(2002) in which they use a nearest neighborhood algorithm to weight the data
points. The neighborhood size is defined by the user but results were found to
be relatively insensitive to this choice. Data points within the neighborhood
are linearly weighted based on the euclidean distance. The weights for each
data point are then used when computing the prior probability $p(C=c)$ and the
conditional probabilities $p(\mathbf{X}=\mathbf{x}|C=c)$. Data should be
normalized for use in this method.

##  3 Standard Naive-Bayes Classifiers

We illustrate how the Naive-Bayes classifier uses training data to estimate
conditional probabilities and these can then be used to classify unknown
samples (the test set) Chandra et al. (2007). Let $C$ denote the random
variable representing the class of an instance and let
$\mathbf{X}=[X_{1},X_{2},\ldots,X_{K}]$ be a vector of random variables
denoting the set of possible attribute values. Let $c$ represent a particular
class belonging to $\mathbf{c}$ and let
$\mathbf{x}=[x_{1},x_{2},\ldots,x_{K}]$ represent the attribute values of a
specific sample. For a given test sample $\mathbf{x}$ we can use Bayes Theorem
to obtain

$p(C=c|\mathbf{X}=\mathbf{x})=\frac{p(C=c)p(\mathbf{X}=\mathbf{x}|C=c)}{p(\mathbf{X}=\mathbf{x})}$
(2)

If we assume that the attribute values are independent then we have

$p(\mathbf{X}=\mathbf{x}|C=c)=\prod_{i=1}^{K}p(X_{i}=x_{i}|C=c)$ (3)

Finally using the fact that the term $p(\mathbf{X}=\mathbf{x})$ is invariant
across the classes then one can find the most probable class $c^{*}$ (and
hence the predicted class) as

$c^{*}=\operatorname*{argmax}_{c\in\mathbf{c}}\left\\{p(C=c)\prod_{i=1}^{K}p(X_{i}=x_{i}|C=c)\right\\}$
(4)

The conditional probabilities $p(X_{i}=x_{i}|C=c)$ and the probability
$p(C=c)$ are estimated from the training data.

###  3.1 Laplace Smoothing

The conditional probability $p(X_{i}=x_{i}|C=c)$ is computed as the ratio of
the number of instances (in the training data) in which that attribute value
$x_{i}$ occurs and the sample is tagged as $c$ and the total number of
instances of $c$. This is the typical approach for estimating this
probability. However if this probability is zero for at least one attribute
$i$ then the product over all attributes will be zero. To avoid this from
occurring the Laplace-Estimate and the $M$-Estimate is used. Using these
estimates we instead have

$p(C=c)=\frac{n_{c}+k}{N+k|\mathbf{c}|}$ (5)

where $n_{c}$ is the number of instances satisfying $C=c$, $N$ is the number
of training instances, $|\mathbf{c}|$ is the number of classes and typically
$k=1$ is used. In $M$-Estimate,

$p(X_{i}=x_{i}|C=c)=\frac{n_{ci}+mq}{n_{c}+m}$ (6)

where $n_{ci}$ is the number of instances where $X_{i}=x_{i}$ and $C=c$,
$n_{c}$ is the number of instances satisfying $C=c$, $q=p(X_{i}=x_{i})$ is the
prior probability of $x_{i}$ estimated by the Laplace-Estimate and typically
$m=1$.

###  3.2 Gaussian Naive Bayes

In the case of Cardinal attributes $p(X_{i}=x_{i}|C=c)$ is typically modelled
by some continuous probability distribution (e.g., Gaussian). In this case

$p(X_{i}=x_{i}|C=c)=\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{\frac{-(x_{i}-\mu)^{2}}{2\sigma^{2}}}$
(7)

where

$\mu=\frac{1}{n_{c}}\sum_{\\{i|C=c\\}}x_{i}\qquad{\sf
and}\qquad\sigma^{2}=\frac{1}{n_{c}}\sum_{\\{i|C=c\\}}(x_{i}-\mu)^{2}$ (8)

###  3.3 Discretization

Another approach to address the zero occurrence issue above is to cluster
consecutive attribute values and instead use the cluster in the analysis. With
sufficiently large cluster sizes the probability that an attribute value does
not belong to a cluster is significantly reduced. Equal width discretization
is a typical approach used. For each attribute, $X_{i}$, a distinct (non-
overlapping) interval $(a_{i},b_{i}]$ is defined such that the conditional
probabilities become

$p(X_{i}=x_{i}|C=c_{i})\approx p(a_{i}<x_{i}\leq b_{i}|C=c)$ (9)

With sufficiently large intervals the probability that an attribute value for
a given class has no samples in an interval is significantly small.

##  4 Proposed Bayes Classifier

Naive Bayes classifiers make the assumption that features are independent.
Note that this assumption is made to reduce the zero-frequency problem. We do
not make this assumption but instead approximate the conditional probability
of the sample attributes set given a class. We first encode any categorical
data into integer values so that we can compute a distance between the
attribute values of any pair of samples. However, when computing such
distances we normalize by the maximum range of differences for the given
training set. Let $X_{ij}$ denote the value of attribute $j$ of training
sample $i$. We define the distance $d_{ab}$ between two samples $a$ and $b$ as

$d_{ab}\equiv\left(\sum_{j=1}^{n}\left(\frac{X_{aj}-X_{bj}}{r_{j}}\right)^{2}\right)^{\frac{1}{2}}$
(10)

where $n$ is the number of attributes and $r_{j}$ is the range of values for
attribute $j$ given by

$r_{j}\equiv\max_{i}\\{X_{ij}\\}-\min_{i}\\{X_{ij}\\}$ (11)

We approximate the conditional probability by using information in the
neighbourhood of an unknown sample. Consider a test sample $\mathbf{x}$ with
value $x_{j}$ for attribute $j$ and denote the distance between this sample
and training sample $i$ by $d_{i}$. Let $y_{i}$ denote the class of training
sample $i$. For a given class $c$ the probability that $\mathbf{x}$ occurs
given $c$ is approximated by

$p(\mathbf{X}=\mathbf{x}|C=c)\approx\frac{1}{N_{c}}\sum_{\\{i|y_{i}=c\\}}(1+d_{i})^{-\kappa}$
(12)

where we use $N_{c}$ to denote the number of training samples of class $c$.
The parameter $\kappa\geq 0$ can be tuned based on the dataset but we will
soon see that, even if we use a constant $\kappa$ for all datasets, the
performance is robust.

If $\kappa=0$ then the summation is equal to $N_{c}$ and so the approximation
is equal to 1 since we will simply be summing all samples that belong to class
$c$ which is given by $N_{c}$. If $\kappa$ is very large then all terms in the
summation will be close to zero except for the samples that have the exact
attribute values as the test sample. In this case the result is the relative
frequency of the test sample in the training set. In most cases there will be
no training samples identical to the test sample and so the result will be
zero (i.e., the zero frequency problem). By proper choice of $\kappa$ we can
capture a sufficient number of “neighbourhood” samples to estimate the
conditional probability.

Note that, as the number of samples increases to infinity,
$p(\mathbf{X}=\mathbf{x}|C=c)$ will approach the conditional distribution
function and so when evaluated at the specified point we get
$f(\mathbf{x}|c)$. Furthermore, as $\kappa$ goes to infinity
$p(\mathbf{X}=\mathbf{x}|C=c)$ converges to the number of samples with
attributes $\mathbf{x}$ over the total number of samples and hence converges
to $f(\mathbf{x}|c)$. Therefore the proposed classifier approaches the optimal
Bayes Classifier as the number of samples goes to infinity and $\kappa$ is
taken to infinity.

We need to multiply by $p(c)$ before finding the predicted class. We therefore
have

$p(c)p(\mathbf{X}=\mathbf{x}|C=c)\approx\frac{N_{c}}{m}\frac{1}{N_{c}}\sum_{\\{i|y_{i}=c\\}}(1+d_{i})^{-\kappa}$
(13)

where $m$ is the number of samples. Since $m$ is constant then when taking the
maximization over $c$ we can ignore the term $1/m$. The pseudo-code for the
proposed classifier is provided in Algorithm 1.

Algorithm 1 Pseudo-code for proposed Algorithm

$\mathbf{c}\equiv\text{\sf set of classes}$

$\kappa>0$ tuning parameter

$\mathbf{X}\in\mathbb{R}^{m\times n}$ ($m$ training samples with $n$
attributes)

$\mathbf{y}\in\mathbf{c}^{m\times 1}$ (class of training samples)

$\mathbf{x}\in\mathbb{R}^{1\times n}$ (test sample attributes)

$\displaystyle r_{j}\equiv\max_{i}\\{X_{ij}\\}-\min_{i}\\{X_{ij}\\}\qquad
j=1,\ldots,n$

$\displaystyle
d_{i}\equiv\left(\sum_{j=1}^{n}\left(\frac{X_{ij}-x_{j}}{r_{j}}\right)^{2}\right)^{\frac{1}{2}}$

$\displaystyle
c^{*}(\kappa)=\operatorname*{argmax}_{c\in\mathbf{c}}\left\\{\sum_{\\{i|y_{i}=c\\}}(1+d_{i})^{-\kappa}\right\\}$

##  5 Illustrative Example

Let us illustrate with a simple example of two classes (red and green) and a
single attribute. There are four samples tagged as green with attribute values
$X=4,5,10,11$. There are also four samples tagged as red with attribute values
$X=1,2,7,8$. Let us suppose that all samples except the sample at $X=4$ are
training samples and we will use the sample at $X=4$ for testing. If we try
regular Naive Bayes then $p(C=green|X=4)=0$ because $p(X=4|C=green)=0$.
Similarly $p(C=red|X=4)=0$. Hence it is not possible to choose a class.

Next consider Naive Bayes with Laplace Smoothing. We have

$p(C=green)=(3+1)/(7+2)=4/9\qquad{\sf and}\qquad p(C=red)=(4+1)/(7+2)=5/9$

Therefore we have,

$p(X=4|C=green)=(0+1)/(3+7)=1/10$ $p(X=4|C=red)=(0+1)/(4+7)=1/11$

Therefore $p(\mathbf{X}=x)p(C=green|X=4)=4/90$ and
$p(\mathbf{X}=x)(p(C=red|X=4)=5/99$ and so we would choose RED which is
incorrect.

Let us consider Gaussian Naive Bayes. In this case the green and red class
samples are modelled by Gaussian distributions with

$\mu_{g}=8.67\qquad{\sf and}\qquad\sigma_{g}=2.6247$ (14)

and

$\mu_{r}=4.5\qquad{\sf and}\qquad\sigma_{r}=3.041$

Therefore

$p(C=green|X=4)=0.0315\times 4/9=0.014$

and

$p(C=red|X=4)=0.1293\times 5/9=0.0718$

and hence class red is incorrectly chosen. Let us now consider the proposed
approach. We have

$p(X=4|C=green)=\frac{1}{3}\left(\frac{1}{2^{\kappa}}+\frac{1}{7^{\kappa}}+\frac{1}{8^{\kappa}}\right)$

and

$p(X=4|C=red)=\frac{1}{4}\left(\frac{1}{4^{\kappa}}+\frac{1}{3^{\kappa}}+\frac{1}{4^{\kappa}}+\frac{1}{5^{\kappa}}\right)$

Therefore

$c^{*}=\operatorname*{argmax}_{c}\left(\frac{3}{7}\;p(X=4|C=green),\quad\frac{4}{7}\;p(X=4|C=red)\right)$
(15)

In Figure 1 we plot the ratio of the value for green and the value for red,
denoted by $F(\kappa)$, as a function of $\kappa$. If this ratio is greater
than one then green should be chosen else red is chosen.

$0$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$4$$4.5$$5$$1$$2$$3$$4$$5$$\kappa$$F(\kappa)$
Figure 1: Class Probability Ratio versus $\kappa$

Therefore as long as $\kappa$ is chosen to be sufficiently large (i.e, only
consider samples close to the test sample) then the green class is correctly
chosen. Note that this holds true for a large range of $\kappa$ values. We
will evaluate the performance on all data sets using a single value of
$\kappa$ (hence no tuning) and we will also derive the $\kappa$ values that
provides the maximum accuracy.

##  6 Numerical Results

In this section we describe the datasets that were used and apply the various
classifiers in order to compare performance. We created a GitHub repository,
Baboolal (2022), with the code used for this evaluation so that the reader can
replicate and verify the results obtained.

###  6.1 Dataset Description

We use a wide variety of datasets to illustrate the robustness of the proposed
approach. These datasets are all available in the University of California at
Irvine (UCI) Machine Learning Repository Dua and Graff (2017) and the reader
can find additional information on that site. We removed samples with missing
attribute values and we encoded categorical values with integer values. No
other pre-processing was performed since we wanted to ensure that our results
could easily be replicated. A summary of the dataset used is provided in Table
1.

Table 1: Summary of Dataset Statistics Name | No. of Samples | No. of Attributes | No. of Classes | Citation
---|---|---|---|---
Iris | 150 | 4 | 3 | Fisher (1936)
Breast Tissue | 106 | 10 | 6 | Estrela da Silva et al. (2000)
Algerian Forest Fires | 244 | 12 | 2 | Abid and Izeboudjen (2019)
Credit Approval | 653 | 16 | 2 | Quinlan (1987)
Wine | 178 | 13 | 3 | Aeberhard et al. (1994)
Breast cancer | 286 | 9 | 2 | Zwitter and Soklic (1988)
Wine-quality-red | 1599 | 11 | 6 | Cortez et al. (2009)
Tic-tac-toe | 958 | 9 | 2 | Aha (1991)
Australian Credit Approval | 690 | 14 | 2 | Quinlan (1987)
Yeast | 1484 | 9 | 10 | Nakai and Kanehisa (1992)
Raisin | 900 | 7 | 2 | CINAR et al. (2020)
Glass | 214 | 9 | 6 | Evett and Spiehler” (”1987”)
Leaf | 340 | 15 | 30 | Silva et al. (2013)
Wine-quality-white. | 4898 | 11 | 7 | Cortez et al. (2009)
Banknote authentication. | 1372 | 4 | 2 | Lohweg and DÃ¶rksen (2012)
Dry Bean | 13611 | 17 | 7 | Koklu and Ozkan (2020)
Abalone | 4177 | 8 | 3 | Nash and Laboratories (1994)

###  6.2 Feature Selection

Note that there are many ways to perform feature selection (Banerjee (2020))
and the only way that one can guarantee the optimal subset of features (for a
given training set) is by exhaustive search which is typically computationally
expensive. The objective of this paper is to compare our proposed classifier
with standard classifiers. We therefore try our best (e.g. using Importance
Values, Pedregosa et al. (2011)) to select the best features for the Gaussian
Naive Bayes classifier and then use these selected features for all of the
other classifiers. This means, in particular, that there may be another subset
of features that are better suited (i.e., higher accuracy) for our approach
but we do not use those features in our comparison. The features selected for
each dataset are provided in 2. The reader can use these to verify our results
or, if they find a better subset, can compare our approach using their choice.

Table 2: Features selected to Maximize accuracy for the Gaussian Naive Bayes Classifier Dataset |  Accuracy
(all attributes) |  Accuracy
(selected attributes) | Selected Attributes
---|---|---|---
Iris | 0.953 | 0.959 | [3, 2]
BreastTissue | 0.657 | 0.658 | [0, 8, 6, 3, 7, 4,5,1]
Algerian Forest Fires | 0.944 | 0.956 | [8, 5, 10, 6]
Credit Approval | 0.787 | 0.787 | [10, 8, 14, 7, 9, 3, 4, 12, 5, 0, 11, 2, 13,1]
Wine | 0.974 | 0.983 | [0, 2, 3, 6, 9, 10,11, 12]
Breast-cancer | 0.739 | 0.753 | [3, 4, 5, 8, 2, 6]
Wine-quality-red | 0.550 | 0.578 | [10, 1, 6, 9, 4, 0, 7]
Tic-tac-toe | 0.715 | 0.715 | [0, 1, 2, 3, 4, 5, 6, 7, 8]
Australian Credit Approval | 0.788 | 0.801 | [9, 7, 13, 8, 6, 4, 5, 3, 11, 2, 12]
Yeast | 0.512 | 0.548 | [3, 1, 2, 8, 4, 6, 0],
Raisin | 0.823 | 0.823 | [1, 0, 4, 6, 2, 5]
Glass | 0.457 | 0.499 | [7, 5, 3, 6]
Leaf | 0.717 | 0.734 | [1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14]
Wine-quality-white | 0.445 | 0.481 | [10, 1, 4, 6, 2, 9, 8, 0]
Banknote-authentication | 0.839 | 0.872 | [0, 1]
DryBean | 0.764 | 0.764 | all attributes
Abalone | 0.519 | 0.533 | [5, 3, 4, 6, 7, 2]

###  6.3 Performance Results

Although we chose optimal features based on the Gaussian Naive Bayes
classifier, we will use those features across all classifiers that we ran. In
this way the results for the other classifiers can potentially be improved if
feature selection was performed specifically for them. We used 10-Fold cross-
validation for each dataset with a re-sample size of 10. For the DryBean
dataset we used 10-Fold cross-validation but we did not employ re-sampling as
the sample size was sufficiently large. We include accuracy values for Laplace
Naive Bayes, Gaussian Naive Bayes, $k$-NN with the optimal $k$, the proposed
approach for a single value of $\kappa=60$ and finally the proposed approach
with the optimal value of $\kappa$. The resulting performance results are
given in Table 6.3. Note that the proposed approach with optimal $\kappa$
outperformed all other classifiers. Note that, in the case of Bank-
authentication, the optimal features for Gaussian Naive Bayes was (0,1). In
this case $k$-NN outperformed the proposed approach. We then decided to find
the optimal features for the $k$-NN model for this dataset and this turned out
to be all features. However in the case of all features our approach has the
same performance as $k$-NN.

Table 3: Accuracy (percentage of samples correctly predicted) for the various
Models

Dataset |  Laplace
Naive Bayes |  Gaussian
Naive Bayes |  $K$-NN
(Optimal $K$) |  Proposed
($\kappa=60$) |  Proposed
(Optimal $\kappa$)
---|---|---|---|---|---
Iris | 0.946 | 0.959 | 0.952 (28) | 0.964 | 0.964 (29)
Breast Tissue | 0.251 | 0.658 | 0.576 (4) | 0.684 | 0.685 (68)
Algerian Forest Fires | 0.92 | 0.956 | 0.952 (8) | 0.970 | 0.974 (19)
Credit Approval | 0.854 | 0.788 | 0.682 (32) | 0.831 | 0.869 (5)
Wine | 0.766 | 0.983 | 0.759 (1) | 0.98 | 0.988 (5)
Breast-cancer | 0.754 | 0.753 | 0.729 (6) | 0.73 | 0.758 (9)
Wine-quality-red | 0.597 | 0.578 | 0.601 (1) | 0.671 | 0.686 (36)
tic-tac-toe | 0.697 | 0.715 | 0.834 (6) | 0.843 | 0.843 (35)
Australian | 0.847 | 0.801 | 0.714 (10) | 0.826 | 0.871 (5)
Yeast | 0.502 | 0.548 | 0.579 (1) | 0.565 | 0.591 (32)
Raisin | 0.543 | 0.823 | 0.843 (7) | 0.861 | 0.861 (60)
Glass | 0.535 | 0.499 | 0.628 (7) | 0.686 | 0.686 (60)
Leaf | 0.065 | 0.734 | 0.586 (2) | 0.728 | 0.737 (37)
Wine-quality-white | 0.543 | 0.481 | 0.602 (1) | 0.678 | 0.692 (42)
Banknote-authentication [0,1] | 0.561 | 0.872 | 0.949 (3) | 0.933 | 0.942 (89)
Banknote-authentication [All] | 0.497 | 0.839 | 0.999 (2) | 0.999 | 0.999 (35)
DryBean | 0.228 | 0.764 | 0.748 (1) | 0.922 | 0.922 (61)
Abalone | 0.507 | 0.533 | 0.537 (45) | 0.546 | 0.545 (27)
Average Score | 0.595 | 0.732 | 0.722 | 0.789 | 0.801

###  6.4 Complexity and Run-Time Analyses

Although the proposed approach performs well when compared with Naive Bayes
classifiers, it does require more computation. Assuming $m$ samples, $n$
attributes and $c$ classes the computational complexity for training of Naive
Bayes classifiers is $O(mn)$ while for $k$-NN and our approach it is $O(1)$.
However, for predicting a sample the computational complexity is $O(cn)$ for
the Naive Bayes classifiers and $O(mn)$ for $k$-NN and our approach and so
predicting is significantly higher.

We also did some run time testing for the datasets in 1 for the various
classifiers. Our run time testing is implemented using the built-in Python
time module, specifically, time.perf_counter(). According to the Python
documentation the time.perf_counter returns the fractional seconds of a clock
with the highest available resolution for measuring short durations. We found
that, on average, it took 2.4 times longer to run the proposed approach (for a
single value of $\kappa$) when compered to the time taken for the Laplace
Naive Bayes approach. Note that we believe that further computation
optimizations can be performed for the proposed approach. We also plan to
determine ways to quickly determine good values for $\kappa$.

###  6.5 Parameter Optimization

Note that the approach requires a single parameter $\kappa$. However we found,
in Table 1, that even if we used a single value for $\kappa$ (in this case
60), for each dataset we get acceptable results. In fact the average accuracy
over all dataset when using $\kappa=60$ is 0.789 while the accuracy when using
the optimal $\kappa$ was 0.801. In addition, without optimizing $\kappa$ our
algorithm is successful in 59% of the datasets. For this exercise we did a
linear search over $\kappa$ but we have noticed that in most cases there is a
single maximum. In Figure 2 we plot the accuracy of the proposed classifier
for a subset of datasets as $\kappa$ is varied. We find that, as long as a
sufficiently high value of $\kappa$ is used, the result is close to optimal
and in fact the approach is robust.

Note that the case $\kappa=0$ corresponds to averaging over all samples and
hence does not take into account the attributes of a test sample. If such
attributes are correlated with the class then one would expect this extreme to
be non-optimal. The case in which $\kappa$ is very large corresponds to only
taking into account samples very close to the test sample. Here the attribute
values of the test sample are taken into account but insufficient samples (or
none) may exist close to the test sample and so the estimate is not robust
leading again to large errors. Therefore we expect $\kappa$ to lie in-between
these extremes. We conjecture that the accuracy, as a function of $\kappa$, is
approximately concave and we plan to investigate this more in the future when
investigating ways of determining good initial guesses for $\kappa$. Not all
of the plots are concave but this may be due to the stochastic nature of the
problem. Also note that, as the sample size increases, the optimal value of
$\kappa$ will also increase since more samples will lie within the
neighbourhood of the test sample. Anyway there seems to be a single maximum.
If this is indeed the case then the search over $\kappa$ can be significantly
reduced.

$0$$10$$20$$30$$40$$50$$60$$70$$80$$90$$0.5$$0.6$$0.7$$0.8$$0.9$$1$$\kappa$AccuracyAlgerianglassAustralianIrisWine
Figure 2: Accuracy as a function of $\kappa$

##  7 Discussion

Across 17 UCI datasets we compared the Laplacian Naive-Bayes, Gaussian Naive-
Bayes and $K$-Nearest Neighbors classification algorithms to our proposed
method. The datasets vary in data type and consists of a combination of
ordinal, categorical and continuous data. The classification space varies from
binary to multiple classes and the size of the feature space also varies
significantly. We note in Table 6.3 that the average accuracy of the proposed
method is 9.43% higher than the Gaussian approach, 34.6% higher than the
Laplacian approach and 10.1% higher than $K$-Nearest Neighbors. These results
suggest that the proposed method performs well and is robust when compared
with traditional methods. The proposed approach had a higher accuracy in all
datasets except Banknote-authentication Lohweg and DÃ¶rksen (2012). Features
of [0,1] resulted in $K$-NN having an accuracy of 0.949 and our model, 0.942.
In this case we tried using all features and tied with $K$-Nearest Neighbours
with an accuracy of 0.999. The optimal $\kappa$ was found through a grid
search but an arbitrarily high value of $\kappa$ (e.g., 60) gives an average
accuracy higher than the other three methods and outperforms them in 58.8% of
the cases.

##  8 Conclusions and Future Work

We present a robust approximation to Bayesian classification using an
activation function in the form $(1+x)^{-\kappa}$, where $x$ is a distance
metric computed using the euclidean distance between test and training
samples. When compared to the Naive-Bayes algorithm (Gaussian and Laplacian)
the proposed method surpasses performance or is on par. The proposed method
also outperforms the $k$-NN classifier as demonstrated through
experimentation. While the results presented in this paper show promise, there
is significant room for improvement of the algorithm. Future work can include
heuristic methods for determining $\kappa$ or working on reducing run-time for
the proposed approach by using a subset of training samples when making a
prediction. As the proposed method relaxes the independence assumption of the
Naive-Bayes classifier it may be possible to use it for image classification.

## References

  * Parzen [1962] Emanuel Parzen.  On estimation of a probability density function and mode.  _The annals of mathematical statistics_ , 33(3):1065–1076, 1962.
  * Friedman et al. [1997] Nir Friedman, Dan Geiger, and Moises Goldszmidt.  Bayesian network classifiers.  _Machine Learning_ , 29:131–163, 11 1997.  doi: 10.1023/A:1007465528199.
  * Jiang et al. [2009] Liangxiao Jiang, Harry Zhang, and Zhihua Cai.  A novel bayes model: Hidden naive bayes.  _IEEE Transactions on Knowledge and Data Engineering_ , 21(10):1361–1371, 2009.  doi: 10.1109/TKDE.2008.234.
  * Yu et al. [2021] Liangjun Yu, Shengfeng Gan, Yu Chen, and Dechun Luo.  A novel hybrid approach: Instance weighted hidden naive bayes.  _Mathematics_ , 9(22), 2021.  ISSN 2227-7390.  URL https://www.mdpi.com/2227-7390/9/22/2982.
  * Langley and Sage [1994] Pat Langley and Stephanie Sage.  Induction of selective bayesian classifiers.  In _UAI_ , 1994.
  * Lee et al. [2011] Chang-Hwan Lee, Fernando Gutierrez, and Dejing Dou.  Calculating feature weights in naive bayes with kullback-leibler measure.  In _2011 IEEE 11th International Conference on Data Mining_ , pages 1146–1151, 2011.  doi: 10.1109/ICDM.2011.29.
  * Lee-Kien Foo [2022] Neveen Ibrahim Lee-Kien Foo, Sook-Ling Chua.  Attribute weighted naïve bayes classifier.  _Computers, Materials & Continua_, 71(1):1945–1957, 2022.  ISSN 1546-2226.  doi: 10.32604/cmc.2022.022011.  URL http://www.techscience.com/cmc/v71n1/45444.
  * Xie et al. [2002] Zhipeng Xie, Wynne Hsu, Zongtian Liu, and Mong Li Lee.  Snnb: A selective neighborhood based naïve bayes for lazy learning.  In Ming-Syan Chen, Philip S. Yu, and Bing Liu, editors, _Advances in Knowledge Discovery and Data Mining_ , pages 104–114, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.  ISBN 978-3-540-47887-4.
  * Gweon et al. [2019] Hyukjun Gweon, Matthias Schonlau, and Stefan H. Steiner.  The k conditional nearest neighbor algorithm for classification and class probability estimation.  _PeerJ Computer Science_ , 5, 2019.
  * Frank et al. [2002] Eibe Frank, Mark Hall, and Bernhard Pfahringer.  Locally weighted naive bayes.  In _Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence_ , UAI’03, page 249–256, San Francisco, CA, USA, 2002\. Morgan Kaufmann Publishers Inc.  ISBN 0127056645.
  * Chandra et al. [2007] B. Chandra, Manish Gupta, and M. P. Gupta.  Robust approach for estimating probabilities in naive-bayes classifier.  In Ashish Ghosh, Rajat K. De, and Sankar K. Pal, editors, _Pattern Recognition and Machine Intelligence_ , pages 11–16, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.  ISBN 978-3-540-77046-6.
  * Baboolal [2022] K Baboolal.  Bayesian classification using conditional approximations, 2022.  URL https://github.com/Kelvos/BAYES-CLASSIFICATION-USING-CONDITIONAL-PROBABILITY-APPROXIMATIONS.
  * Dua and Graff [2017] Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.  URL http://archive.ics.uci.edu/ml.
  * Fisher [1936] Ronald A Fisher.  The use of multiple measurements in taxonomic problems.  _Annals of eugenics_ , 7(2):179–188, 1936.
  * Estrela da Silva et al. [2000] J Estrela da Silva, J Pa Marques de Sá, and J Jossinet.  Classification of breast tissue by electrical impedance spectroscopy.  _Medical and Biological Engineering and Computing_ , 38(1):26–30, 2000.
  * Abid and Izeboudjen [2019] Faroudja Abid and Nouma Izeboudjen.  Predicting forest fire in algeria using data mining techniques: Case study of the decision tree algorithm.  In _International Conference on Advanced Intelligent Systems for Sustainable Development_ , pages 363–370. Springer, 2019.
  * Quinlan [1987] J. Ross Quinlan.  Simplifying decision trees.  _International journal of man-machine studies_ , 27(3):221–234, 1987.
  * Aeberhard et al. [1994] Stefan Aeberhard, Danny Coomans, and Olivier De Vel.  Comparative analysis of statistical pattern recognition methods in high dimensional settings.  _Pattern Recognition_ , 27(8):1065–1077, 1994\.
  * Zwitter and Soklic [1988] Matjaz Zwitter and Milan Soklic.  UCI machine learning repository, 1988.  URL https://archive.ics.uci.edu/ml/datasets/breast+cancer.
  * Cortez et al. [2009] Paulo Cortez, António Cerdeira, Fernando Almeida, Telmo Matos, and José Reis.  Modeling wine preferences by data mining from physicochemical properties.  _Decision Support Systems_ , 47(4):547–553, 2009\.  ISSN 0167-9236.  doi: https://doi.org/10.1016/j.dss.2009.05.016.  URL https://www.sciencedirect.com/science/article/pii/S0167923609001377.  Smart Business Networks: Concepts and Empirical Evidence.
  * Aha [1991] David W. Aha.  Incremental constructive induction: An instance-based approach.  In _ML_ , 1991.
  * Nakai and Kanehisa [1992] Kenta Nakai and Minoru Kanehisa.  A knowledge base for predicting protein localization sites in eukaryotic cells.  _Genomics_ , 14(4):897–911, 1992.  ISSN 0888-7543.  doi: https://doi.org/10.1016/S0888-7543(05)80111-9.  URL https://www.sciencedirect.com/science/article/pii/S0888754305801119.
  * CINAR et al. [2020] Ilkay CINAR, Murat KOKLU, and Sakir TASDEMIR.  Classification of raisin grains using machine vision and artificial intelligence methods.  _Gazi Muhendislik Bilimleri Dergisi (GMBD)_ , 6(3):200–209, 2020.
  * Evett and Spiehler” [”1987”] ”Ian W. Evett and E. J. Spiehler”.  ”rule induction in forensic science”.  In _”KBS in Government”_ , pages ”107–118”. ”Online Publications”, ”1987”.  URL "http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/evett_1987_rifs.pdf".
  * Silva et al. [2013] Pedro FB Silva, Andre RS Marcal, and Rubim M Silva.  Evaluation of features for leaf discrimination.  In _International Conference Image Analysis and Recognition_ , pages 197–204. Springer, 2013.
  * Lohweg and DÃ¶rksen [2012] Volker Lohweg and Helene DÃ¶rksen.  UCI machine learning repository, 2012.  URL https://archive.ics.uci.edu/ml/datasets/banknote+authentication.
  * Koklu and Ozkan [2020] Murat Koklu and Ilker Ali Ozkan.  Multiclass classification of dry beans using computer vision and machine learning techniques.  _Computers and Electronics in Agriculture_ , 174:105507, 2020.  ISSN 0168-1699.  doi: https://doi.org/10.1016/j.compag.2020.105507.  URL https://www.sciencedirect.com/science/article/pii/S0168169919311573.
  * Nash and Laboratories [1994] W.J. Nash and Tasmania. Marine Research Laboratories.  _The Population Biology of Abalone (Haliotis Species) in Tasmania: Blacklip abalone (H. rubra) from the north coast and the islands of Bass Strait_.  Number v. 1 in Technical report (Tasmania. Sea Fisheries Division). Sea Fisheries Division, Marine Research Laboratories - Taroona, Department of Primary Industry and Fisheries, Tasmania, 1994.  ISBN 9780724641444.  URL https://books.google.com/books?id=4Sx4NQAACAAJ.
  * Banerjee [2020] Prashant Banerjee.  Comprehensive guide on feature selection, Nov 2020.  URL https://www.kaggle.com/code/prashant111/comprehensive-guide-on-feature-selection.
  * Pedregosa et al. [2011] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 12:2825–2830, 2011\.