#
Independent low-rank matrix analysis based on the Sinkhorn divergence source
model for blind source separation

Jianyu Wang(1) Shanzheng Guan(1) Jingdong Chen(1) and Jacob Benesty(2)

### ABSTRACT

The so-called independent low-rank matrix analysis (ILRMA) has demonstrated a
great potential for dealing with the problem of determined blind source
separation (BSS) for audio and speech signals. This method assumes that the
spectra from different frequency bands are independent and the spectral
coefficients in any frequency band are Gaussian distributed. The Itakura-Saito
divergence is then employed to estimate the source model related parameters.
In reality, however, the spectral coefficients from different frequency bands
may be dependent, which is not considered in the existing ILRMA algorithm.
This paper presents an improved version of ILRMA, which considers the
dependency between the spectral coefficients from different frequency bands.
The Sinkhorn divergence is then exploited to optimize the source model
parameters. As a result of using the cross-band information, the BSS
performance is improved. But the number of parameters to be estimated also
increases significantly, and so is the computational complexity. To reduce the
algorithm complexity, we apply the Kronecker product to decompose the modeling
matrix into the product of a number of matrices of much smaller
dimensionality. An efficient algorithm is then developed to implement the
Sinkhorn divergence based BSS algorithm and the complexity is reduced by an
order of magnitude.

Keywords: Independent low-rank matrix analysis (ILRMA), Blind source
separation (BSS), Sinkhorn distance, Kronecker product.

## 1 INTRODUCTION

Multichannel blind source separation (BSS) refers to the problem of estimating
source signals from their mixtures observed by an array of sensors without
using any prior information about the mixing system [1]. For audio and speech
applications [2], the problem can be divided into two cases: underdetermined
and determined. The former refers to the case where the number of sensors in
the array is less than the number of sources. In this case, the problem cannot
be solved without additional information or constraints [3, 4]. The latter
refers to the scenario where the number of sensors is greater than or equal to
the number of sources. In this case, separation can be achieved by identifying
the demixing system from only the observation signals. This work focus on the
latter case, i.e., the determined BSS for audio and speech signals.

In audio and speech applications, the signal observed at every sensor is a
mixture of all the source signals convolved with the corresponding acoustic
channel impulse responses. As the acoustic channel impulse responses are
usually very long (it is not uncommon to have a few thousands of points), this
convolutive mixing process make it challenging and difficult to achieve source
separation directly in the time domain from the perspectives of accuracy,
robustness, and complexity. A widely adopted approach to circumventing this
issue is to transform the time-domain signals into the time-frequency domain
using the short-time fourier transform (STFT), thereby converting the
convolutive mixing problem into one of instantaneous mixing. Consequently,
majority of efforts in audio and speech BSS have been focused in the STFT
domain. Many methods and algorithms have been developed in this domain over
the last few decades and the representative ones include the so-called
independent component analysis (ICA) [8] and independent vector analysis (IVA)
[9, 10]. In comparison, IVA based methods are more appropriate than ICA for
dealing with audio BSS in the STFT domain as it dramatically mitigates the
permutation problem. While they have demonstrated reasonably good performance,
the classical IVA algorithms do not take advantage of the structural
information in the source spectra, which are useful to improve BSS
performance. To exploit such information, Daichi et al. proposed an
independent-low-rank-matrix-analysis (ILRMA) method [5], which utilizes
nonnegative matrix factorization (NMF) to decompose the given spectrogram as
the product between basis and temporal activation matrices. By assuming that
the spectral components from different frequency bands are independent and the
spectral coefficients in any frequency band are Gaussian distributed, this
method employs the Kullback-Leibler (KL) or Itakura-Saito (IS) divergence as
the cost function to estimate the parameters of the NMF-based source model.

However, the spectral components of the same source from different frequency
bands may be correlated as demonstrated in the literature of noise reduction
[6, 7], which is not considered in the ILRMA algorithm. This paper presents an
improved version of ILRMA, which takes advantage of the cross-band dependency
of spectra to improve BSS performance. We adopt the Sinkhorn divergence [11],
[13], [14] as the cost function to optimize the parameters of the NMF-based
source model, resulting in a Sinkhorn divergence based ILRMA (SDILRMA)
algorithm. Since the cross-band information is used, SDILRMA is able to
improve the BSS performance. But the number of parameters to be estimated also
increases significantly, and so is the computational complexity. To reduce the
number of parameters and the algorithm complexity, we subsequently apply the
Kronecker product tool [15, 16] to decompose the modeling matrix into the
product of a number of matrices of much smaller dimensionality, leading to a
simplified SDILRMA, which is computationally more efficient than its original
counterpart and is able produce better performance than ILRMA.

## 2 SIGNAL MODEL AND PROBLEM FORMULATION

Suppose that there are $N$ sources in the sound field and we use a microphone
array consisting of $M$ sensors to pick up the signals. The observation signal
at the $m$th microphone and time index $j$ is then

$\displaystyle x_{m}(j)$ $\displaystyle=\sum_{n=1}^{N}a_{nm}(j)*s_{n}(j),$ (1)

where $s_{n}(j)$ denotes the $n$th source signal and $a_{nm}(j)$ is the
acoustic impulse response from the $n$th source to the $m$th sensor.

Transforming both sides of (1) into the short-time Fourier transform (STFT)
domain and rearranging the results into a vector form gives

$\displaystyle\begin{split}\mathbf{x}_{f,t}&=\sum_{n=1}^{N}\mathbf{a}_{n,f}S_{n,f,t}\\\
&=\sum_{n=1}^{N}\mathbf{x}_{n,f,t},\end{split}$ (2)

where $S_{n,f,t}$ is the STFT of $s_{n}(j)$,
$\mathbf{x}_{f,t}\stackrel{{\scriptstyle\triangle}}{{=}}\left[X_{1,f,t},\leavevmode\nobreak\
\cdots,\leavevmode\nobreak\ X_{M,f,t}\right]^{T}\in\mathbb{C}^{M}$ with
$X_{m,f,t}$ being the STFT of $x_{m}(j)$,
$\mathbf{a}_{n,f}\stackrel{{\scriptstyle\triangle}}{{=}}\left[A_{n,1,f},\leavevmode\nobreak\
\cdots,\leavevmode\nobreak\ A_{n,M,f}\right]^{T}$ with $A_{n,m,f}$ denoting
the acoustic transfer function, the superscript T denotes the transpose
operator, $f$ and $t$ denote, respectively, the frequency and frame indices,
and
$\mathbf{x}_{n,f,t}\stackrel{{\scriptstyle\triangle}}{{=}}\mathbf{a}_{n,f}S_{n,f,t}$,
whose elements are often called the source images.

The signal model in (2) can be rearranged into a more compact form as

$\displaystyle\mathbf{x}_{f,t}=\mathbf{A}_{f}\mathbf{s}_{f,t},$ (3)

where
$\mathbf{A}_{f}\stackrel{{\scriptstyle\triangle}}{{=}}\left[\mathbf{a}_{1,f},\leavevmode\nobreak\
\cdots,\leavevmode\nobreak\ \mathbf{a}_{n,f}\right]\in\mathbb{C}^{M\times N}$
is called the mixing matrix, and
$\mathbf{s}_{f,t}\stackrel{{\scriptstyle\triangle}}{{=}}\left[S_{1,f,t},\leavevmode\nobreak\
\cdots,\leavevmode\nobreak\ S_{N,f,t}\right]^{T}$ is a vector consisting of
the $N$ source signals. Now, the problem of BSS becomes one of identifying a
demixing matrix such that

$\displaystyle\mathbf{y}_{f,t}=\mathbf{D}_{f}\mathbf{x}_{f,t},$ (4)

where $\mathbf{D}_{f}=\left[\mathbf{d}_{1,f},\leavevmode\nobreak\
\cdots,\leavevmode\nobreak\ \mathbf{d}_{N,f}\right]\in\mathbb{C}^{N\times M}$
denotes the demixing matrix, and $\mathbf{y}_{f,t}$ is an estimate of
$\mathbf{s}_{f,t}$ (up to a scale and permutation). Note that if the mixing
matrix
$\mathbf{A}_{f}=\left[\mathbf{a}_{1,f},\dots,\mathbf{a}_{n,f}\right]\in\mathbb{C}^{M\times
N}$ is not singular as assumed in such methods as ILRMA, the demixing matrix
should be the inverse of the mixing matrix $\mathbf{A}_{f}$.

To achieve this identification, some source model has to be assumed. The so-
called spherically invariant random processing (SIRP) model has been widely
used in BSS for speech signals [19]. With this model, the multivariate
probability density function can be derived from the corresponding univariate
probability density function and the correlation matrices [18, 20]. As a
particular case of SIRP, the local Gaussian model has gained much attention,
in which the source spectrum in every time-frequency (TF) bin is modeled as a
time-varying complex Gaussian distribution [17] and the spectral components
from different frequency bins and time frames are assumed to be mutually
independent, and as a result, $s_{n,f,t}$ follows a zero-mean complex Gaussian
distribution with a time-varying variance $\lambda_{n,f,t}$, i.e.,

$\begin{split}s_{n,f,t}\sim\mathcal{N}_{\mathbb{C}}\left(0,\lambda_{n,f,t}\right).\end{split}$
(5)

The critical parameter of this source model is the time-varying variance
$\lambda_{n,f,t}$, which needs to be estimated. One way to achieve such
estimation is through NMF, in which the variance matrix of every source is
modeled as a low-rank approximation of the product of a basis matrix and an
activation matrix. Given $\lambda_{n,f,t}$, the variance matrix is defined as

$\displaystyle\boldsymbol{\lambda}_{n}\stackrel{{\scriptstyle\triangle}}{{=}}\begin{bmatrix}\lambda_{n,1,1}&\dots&\lambda_{n,1,T}\\\
\vdots&\ddots&\vdots\\\
\lambda_{n,F,1}&\dots&\lambda_{n,F,T}\end{bmatrix},\quad$ (6)

which consists of the time-varying variance for all the time frames (the total
number of frames is denoted as $T$) and frequencies bins (the number of
frequency bins is denoted as $F$). The the low-rank approximation is then
expressed as

$\displaystyle\boldsymbol{\lambda}_{n}\approx\mathbf{W}_{n}\mathbf{H}_{n},$
(7)

where

$\displaystyle\mathbf{W}_{n}$
$\displaystyle=\begin{bmatrix}w_{n,1,1}&\dots&w_{n,1,K}\\\
\vdots&\ddots&\vdots\\\ w_{n,F,1}&\dots&w_{n,F,K}\end{bmatrix},\quad$ (8)
$\displaystyle\mathbf{H}_{n}$
$\displaystyle=\begin{bmatrix}h_{n,1,1}&\dots&h_{n,1,T}\\\
\vdots&\ddots&\vdots\\\ h_{n,K,1}&\dots&h_{n,K,T}\end{bmatrix},$ (9)

are, respectively, the basis and activation matrices, and $K$ denotes the
number of basis vectors. With this approximation, the estimation of the time-
varying variances, i.e., $\lambda_{n,f,t}$, for all the time frames and
frequency bins is converted to a problem of estimating the basis and
activation matrices, which will be discussed in the next section.

From (2) and (5), one can check that $\mathbf{x}_{n,f,t}$ follows a
multivariate complex Gaussian distribution, i,e,.

$\mathbf{x}_{n,f,t}\sim\mathcal{N}_{\mathbb{C}}\left(\mathbf{0},\leavevmode\nobreak\
\leavevmode\nobreak\ \lambda_{n,f,t}\mathbf{R}_{n,f}\right),$ (10)

where $\mathbf{0}$ is column vector with all its elements being 0,
$\mathbf{R}_{n,f}\stackrel{{\scriptstyle\triangle}}{{=}}E\left[\mathbf{x}_{n,f,t}\mathbf{x}_{n,f,t}^{H}\right]$
is the spatial covariance matrix for the $n$th source. If one approximates
this matrix as $\mathbf{R}_{n,f}=\mathbf{a}_{n,f}\mathbf{a}_{n,f}^{H}$, the
model degenerates to a rank-1 spatial model. Given $\mathbf{R}_{n,f}$, one can
be check that the observation signal vector $\mathbf{x}_{f,t}$ follows the
following distribution:

$\begin{split}\mathbf{x}_{f,t}\sim\mathcal{N}_{\mathbb{C}}\left(\mathbf{0},\leavevmode\nobreak\
\leavevmode\nobreak\
\sum_{n=1}^{N}\lambda_{n,f,t}\mathbf{R}_{n,f}\right).\end{split}$ (11)

## 3 SINKHORN DIVERGENCE BASED MODEL PARAMETER ESTIMATION

Generally, the NMF based source model adopts the IS divergence as the cost
function for optimization. For the ILRMA algorithm, the cost function, which
is denoted as $\mathcal{L}_{\mbox{ILRMA}}$, is the sum of the logarithmic
conditional probability
$p\left(\mathbf{X}_{f,t}|\lambda_{n,f,t},\mathbf{D}_{f}\right)$, i.e.,

$\displaystyle\mathcal{L}_{\mbox{ILRMA}}=\sum_{f=1}^{F}\sum_{t=1}^{T}\log\left[p\left(\left.\mathbf{X}_{f,t}\right|\lambda_{n,f,t},\mathbf{D}_{f}\right)\right]$
$\displaystyle=\sum_{f=1}^{F}\sum_{t=1}^{T}\log\mathcal{N}_{\mathbb{C}}\left(\mathbf{X}_{f,t}\left|\mathbf{0},\sum_{n=1}^{N}\lambda_{n,f,t}\mathbf{a}_{n,f}\mathbf{a}_{n,f}^{H}\right.\right)$
$\displaystyle=-\sum_{f=1}^{F}\sum_{t=1}^{T}\mbox{Tr}\left[\mathbf{y}_{f,t}^{H}\mathbf{D}_{f}^{-H}\left(\mathbf{D}_{f}^{H}\boldsymbol{\Lambda}_{f,t}^{-1}\mathbf{D}_{f}\right)\mathbf{D}_{f}^{-1}\mathbf{y}_{f,t}\right]+T\sum_{f=1}^{F}\log\left|\mathbf{D}_{f}\mathbf{D}_{f}^{H}\right|-\sum_{f=1}^{F}\sum_{t=1}^{T}\log\left|\boldsymbol{\Lambda}_{f,t}\right|+\mbox{Cst}$
$\displaystyle=-\sum_{f=1}^{F}\sum_{t=1}^{T}\left[\sum_{n=1}^{N}\frac{\left|y_{n,f,t}\right|^{2}}{\sum_{k=1}^{K}w_{n,f,k}h_{n,k,t}}+\sum_{n=1}^{N}\log\left(\sum_{k=1}^{K}w_{n,f,k}h_{n,k,t}\right)\right]+2T\sum_{f=1}^{F}\log\left|\mathbf{D}_{f}\right|+\mbox{Cst},$
(12)

where
$\boldsymbol{\Lambda}_{f,t}=\mbox{Diag}\left(\lambda_{1,f,t},\leavevmode\nobreak\
\dots,\leavevmode\nobreak\ \lambda_{N,f,t}\right)$ is a diagonal matrix. Note
that the first term on the right-hand side of the last line in (3) denotes the
source model, which can also be viewed as the IS divergence between the low-
rank approximated spectra and the estimated source spectra for every source,
and the second term denotes the spatial model.

It is seen from (3) that the spectra from different frequency bins are treated
independently. In practice, the spectral components of the same source from
different frequency bins may be correlated [6, 7]. In what follows, we
introduce the Sinkhorn divergence based source model to replace the first term
on the right-hand side of the last line in (3) so the cross-band information
is used to estimate the model parameters. Specifically, the Sinkhorn
divergence is expressed as

$\displaystyle
D_{\mathrm{S}}\left(\mathbf{Y}_{n}\cdot\mathbf{Y}_{n}^{*}\leavevmode\nobreak\
|\leavevmode\nobreak\ \boldsymbol{\lambda}_{n}\right)=$
$\displaystyle\sum_{t=1}^{T}\leavevmode\nobreak\
\min_{\mathbf{P}_{t}}\leavevmode\nobreak\
\langle\mathbf{P}_{t},\mathbf{C}\rangle-\frac{1}{\mu}H\left(\mathbf{P}_{t}\right)\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \mbox{s. \
t.}\quad\mathbf{P}_{t}\mathbf{1}=\mathbf{y}_{n,t}\cdot\mathbf{y}_{n,t}^{*},\quad\mathbf{P}_{t}\mathbf{1}^{T}=\boldsymbol{\lambda}_{n,t},$
(13)

where $\langle\rangle$ denotes the inner product between two matrices, $\cdot$
denotes the Hadamard Product (element-wise Multiplication), $\mathbf{P}_{t}\in
U\left(\mathbf{y}_{n,t}\cdot\mathbf{y}_{n,t}^{*},\boldsymbol{\lambda}_{n,t}\right)$
denotes the transport matrix with $\left[\mathbf{P}_{t}\right]_{ij}$
describing the frequency component migrates from the $i$th frequency bin of
$\mathbf{y}_{n,t}\cdot\mathbf{y}_{n,t}^{*}$ to the $j$th subband of
$\boldsymbol{\lambda}_{n,t}$, $\mathbf{1}\in\mathbb{R}^{F}$ is the all-one
vector,
$U\left(\mathbf{y}_{n,t}\cdot\mathbf{y}_{n,t}^{*},\boldsymbol{\lambda}_{n,t}\right):=\left\\{\mathbf{P}_{t}\in\mathbb{R}_{+}^{F\times
F}\leavevmode\nobreak\ |\leavevmode\nobreak\
\mathbf{P}_{t}\mathbf{1}=\mathbf{y}_{n,t}\cdot\mathbf{y}_{n,t}^{*},\leavevmode\nobreak\
\mathbf{P}_{t}^{T}\mathbf{1}=\boldsymbol{\lambda}_{n,t}\right\\}$ denotes a
transport polytope, which contains all paths from the estimated source
$\mathbf{y}_{n,t}\cdot\mathbf{y}_{n,t}^{*}$ to the target parameter
$\boldsymbol{\lambda}_{n}$, $\mathbf{C}\in\mathbb{R}^{F\times F}$ represents
the cost of transporting one unit of the source vector to the target vector,
and
$H(\mathbf{P}_{t})=-\sum_{i,j}\left[\mathbf{P}_{t}\right]_{ij}\log\left[\mathbf{P}_{t}\right]_{ij}$
denotes the entropic regularization term, which enables efficient
approximation of the gradient of the Sinkhorn divergence.

Using the Lagrange multiplier method, one can express (13) as

$\begin{split}\\!\\!\\!D_{\mathrm{S}}^{\mu,\gamma}\left(\left.\mathbf{Y}_{n}\cdot\mathbf{Y}_{n}^{*}\leavevmode\nobreak\
\right|\leavevmode\nobreak\
\boldsymbol{\lambda}_{n}\right)=\sum_{t=1}^{T}\left[\min_{\mathbf{P}_{t}}\leavevmode\nobreak\
\langle\mathbf{P}_{t},\leavevmode\nobreak\
\mathbf{C}\rangle-\frac{1}{\mu}H(\mathbf{P}_{t})+\gamma
D_{\mathrm{KL}}\left(\mathbf{P}_{t}\mathbf{1}\left|\mathbf{y}_{n,t}\cdot\mathbf{y}_{n,t}^{*}\right.\right)+\gamma
D_{\mathrm{KL}}\left(\left.\mathbf{P}_{t}\mathbf{1}^{T}\right|\boldsymbol{\lambda}_{n,t}\right)\right],\end{split}$
(14)

where $\boldsymbol{\lambda}_{n,t}=\sum_{k=1}^{K}\mathbf{w}_{n,k}h_{n,k,t}$,
and $D_{\mathrm{KL}}\left(x|y\right)=x\log\frac{x}{y}-x+y$. Note that only a
single Lagrange multiplier is used in (14) to reduce the number of parameters.

The transport matrix $\mathbf{P}_{t}$ should satisfy
$\mathbf{P}_{t}=\mbox{diag}(\mathbf{u})\ \mathbf{G}\ \mbox{diag}(\mathbf{v})$
when optimizing the cost function in (14), where
$\mathbf{u}=\left(\frac{\mathbf{y}_{n,t}\cdot\mathbf{y}_{n,t}^{*}}{\mathbf{P}_{t}\mathbf{1}}\right)^{\gamma\mu}$,
$\mathbf{v}=\left(\frac{\boldsymbol{\lambda}_{n,t}}{\mathbf{P}_{t}\mathbf{1}^{T}}\right)^{\gamma\mu}$
(note that here the fraction between two vectors denotes the element wise
division), and $\mathbf{G}=\exp(-\mu\mathbf{C}-1)$. The optimal transport
matrix $\mathbf{P}_{t}$ is estimated by a Sinkhorn-like iterative algorithm.

For the basis matrix $\mathbf{W}_{n}$ and the activation matrix
$\mathbf{H}_{n}$, we construct an auxiliary function as

$\begin{split}A\left(\mathbf{W}_{n},\mathbf{W}_{n}^{\star}\right)=\sum_{t=1}^{T}\sum_{k_{1},\dots,k_{F}}\prod_{f}\alpha_{f,k_{f}}D_{\mathrm{S}}^{\mu,\gamma}\left(\mathbf{y}_{n,t}\cdot\mathbf{y}_{n,t}^{*}\left|\frac{\sum_{k=1}^{K}\mathbf{w}_{n,k}h_{n,k,t}}{\boldsymbol{\alpha}}\right.\right),\end{split}$
(15)
$\begin{split}A\left(\mathbf{H}_{n},\mathbf{H}_{n}^{\star}\right)=\sum_{t=1}^{T}\sum_{k_{1},\dots,k_{F}}\prod_{f}\beta_{f,k_{f}}D_{\mathrm{S}}^{\mu,\gamma}\left(\mathbf{y}_{n,t}\cdot\mathbf{y}_{n,t}^{*}\left|\frac{\sum_{k=1}^{K}\mathbf{w}_{n,k}h_{n,k,t}}{\boldsymbol{\beta}}\right.\right)\end{split}$
(16)

where $\mathbf{H}_{n}^{\star}$ denotes an auxiliary matrix constructed from
$\mathbf{H}$,
$\alpha_{f,k_{f}}=\frac{w_{n,f,k_{f}}^{\star}h_{n,k_{f},t}}{\sum_{k_{f}}w_{n,f,k_{f}}h_{n,k_{f},t}^{\star}}$,
and
$\beta_{f,k_{f}}=\frac{w_{n,f,k_{f}}h_{n,k_{f},t}^{\star}}{\sum_{k_{f}}w_{n,f,k_{f}}h_{n,k_{f},t}^{\star}}$.
Through evaluating the partial derivatives $\frac{\partial
A\left(\mathbf{W}_{n},\mathbf{W}_{n}^{\star}\right)}{\partial w_{n,f,k}}$ and
$\frac{\partial A\left(\mathbf{H}_{n},\mathbf{H}_{n}^{\star}\right)}{\partial
h_{n,k,t}}$, we can obtain the algorithm to estimate the elements of the basis
and activation matrices, i.e.,

$\begin{split}w_{n,f,k}\leftarrow
w_{n,f,k}\sqrt{\frac{\sum_{t}\left[\mathbf{P}_{t}\mathbf{1}\right]_{f}h_{n,k,t}\left(\sum_{k^{\prime}}w_{n,f,k^{\prime}}h_{n,k^{\prime},t}\right)^{-2}}{\sum_{t}\left[\mathbf{P}_{t}\mathbf{1}\right]_{f}\left(\sum_{k^{\prime}}w_{n,f,k^{\prime}}h_{n,k^{\prime},t}\right)^{-1}}},\end{split}$
(17) $\begin{split}h_{n,k,t}\leftarrow
h_{n,f,k}\sqrt{\frac{\sum_{f}\left[\mathbf{P}_{t}\mathbf{1}\right]_{f}w_{n,f,k}\left(\sum_{k^{\prime}}w_{n,f,k^{\prime}}h_{n,k^{\prime},t}\right)^{-2}}{\sum_{f}\left[\mathbf{P}_{t}\mathbf{1}\right]_{f}\left(\sum_{k^{\prime}}w_{n,f,k^{\prime}}h_{n,k^{\prime},t}\right)^{-1}}}.\end{split}$
(18)

The model parameters are optimized in a similar manner as ILRMA [5]. Note,
however, computation of the transport matrix $\mathbf{P}_{t}$ in every frame
for the $n$th source requires large memory and is computationally expensive.
In the next section, we apply the Kronecker product tool to decompose the
transport matrix $\mathbf{P}_{t}$ into a product of a number of matrices of
much smaller dimensionality.

## 4 MODEL PARAMETER ESTIMATION BASED ON KRONECKER PRODUCT DECOMPOSITION

######  Property 1.

(sum of Kronecker product)[15]: Let two matrices be
$\mathbf{A}\in\mathbb{R}^{m\times m}$ and $\mathbf{B}\in\mathbb{R}^{n\times
n}$, their Kronecker sum can be expressed as

$\begin{split}\mathbf{A}\oplus\mathbf{B}=\mathbf{A}\otimes\mathbf{I}_{n}+\mathbf{I}_{m}\otimes\mathbf{B},\end{split}$
(19)

where $\mathbf{I}_{m}$ and $\mathbf{I}_{n}$ are identity matrices of size
$m\times m$ and $n\times n$, respectively, and $\otimes$ denotes the Kronecker
product.

Since the above Kronecker product decomposition is based on two all-one
matrices, we name it the all-one Kronecker product.

Let us decompose the cost matrix $\mathbf{C}$ as

$\displaystyle\mathbf{C}=\oplus_{q=1}^{Q}\mathbf{C}_{q}=\mathbf{C}_{1}\otimes\mathbf{C}_{2}\otimes\cdots\otimes\mathbf{C}_{Q},$
(20)

where $\mathbf{C}_{1}\in\mathbb{R}^{f_{1}\times
f_{1}},\dots,\mathbf{C}_{Q}\in\mathbb{R}^{f_{Q}\times f_{Q}}$,
$F=f_{1}\times\cdots\times f_{Q}$. The intermediate variable matrix
$\mathbf{G}$ can then be written as

$\begin{split}\mathbf{G}=\exp\left(-\mu\oplus_{q=1}^{Q}\mathbf{C}_{q}-1\right)=e^{-1}\otimes_{q=1}^{Q}\exp\left(-\mu\mathbf{C}_{q}\right).\end{split}$
(21)

The product $\mathbf{P}_{t}\mathbf{1}$ in (17) and (18) can be calculated in
another way:

$\begin{split}\mathbf{P}_{t}\mathbf{1}=\mbox{diag}\left(\mathbf{u}\right)\mathbf{G}\mbox{diag}\left(\mathbf{v}\right)\mathbf{1}=\mbox{diag}\left(\mathbf{u}\right)\mathbf{G}\mathbf{v}=\mbox{diag}(\mathbf{u})e^{-1}\otimes_{q=1}^{Q}\exp\left(-\mu\mathbf{C}_{q}\right)\mathbf{v}.\end{split}$
(22)

Now, let us use the relationship between vector-operator and Kronecker
product, i.e.,
$\mbox{vec}\left(\mathbf{ABC}\right)=\left(\mathbf{C}^{T}\otimes\mathbf{A}\right)\mbox{vec}\left(\mathbf{B}\right)$.
Then, we adopt a fold operator $\mbox{fold}\left(\cdot\right)$ and a product
operator $\times_{q=1}^{Q}$ to fold a vector into a tensor, thereby
transforming the vector $\mathbf{v}\in\mathbb{R}^{F}$ into an $Q$ order tensor
$\mathcal{V}=\mbox{fold}(\mathbf{v})\in\mathbb{R}^{f_{1}\times
f_{2}\times\dots\times f_{Q}}$. This gives

$\begin{split}P_{t}\mathbf{1}=\mbox{diag}\left(\mathbf{u}\right)\mbox{vec}\left(\mathcal{V}\times_{q=1}^{Q}\exp\left(-\mu\mathbf{C}_{q}\right)\right).\end{split}$
(23)

Note that (23) does not require to compute directly the transport matrix
$\mathbf{P}_{t}$, which helps reduce the computational complexity by a
magnitude. Now, the estimators in (17) and (18) can be updated as

$\begin{split}w_{n,f,k}\leftarrow
w_{n,f,k}\sqrt{\frac{\sum_{t}\left[\mbox{diag}\left(\mathbf{u}\right)\mbox{vec}\left(\mathcal{V}\times_{q=1}^{Q}\exp\left(-\mu\mathbf{C}_{q}\right)\right)\right]_{f}h_{n,k,t}\left(\sum_{k^{\prime}}w_{n,f,k^{\prime}}h_{n,k^{\prime},t}\right)^{-2}}{\sum_{t}\left[\mbox{diag}\left(\mathbf{u}\right)\mbox{vec}\left(\mathcal{V}\times_{q=1}^{Q}\exp\left(-\mu\mathbf{C}_{q}\right)\right)\right]_{f}\left(\sum_{k^{\prime}}w_{n,f,k^{\prime}}h_{n,k^{\prime},t}\right)^{-1}}},\end{split}$
(24) $\begin{split}h_{n,k,t}\leftarrow
h_{n,f,k}\sqrt{\frac{\sum_{f}\left[\mbox{diag}\left(\mathbf{u}\right)\mbox{vec}\left(\mathcal{V}\times_{q=1}^{Q}\exp\left(-\mu\mathbf{C}_{q}\right)\right)\right]_{f}w_{n,f,k}\left(\sum_{k^{\prime}}w_{n,f,k^{\prime}}h_{n,k^{\prime},t}\right)^{-2}}{\sum_{f}\left[\mbox{diag}\left(\mathbf{u}\right)\mbox{vec}\left(\mathcal{V}\times_{q=1}^{Q}\exp\left(-\mu\mathbf{C}_{q}\right)\right)\right]_{f}\left(\sum_{k^{\prime}}w_{n,f,k^{\prime}}h_{n,k^{\prime},t}\right)^{-1}}}.\end{split}$
(25)

(a) female+female

(b) female+male

(c) male+male

(d) female+female

(e) female+male

(f) male+male

Figure 1: SDR and SIR improvement of the studied methods.

## 5 SIMULATIONS

We used some speech signals from the Wall Street Journal (WSJ0) corpus [23] as
the clean speech source signals and configured evaluation signals following
the SISEC challenge [25] with $M=N=2$, where the room size is $8\times 8\times
3$ m. The two sources are assumed to be $2$ m away from the center of the two
microphones and the microphone spacing is $5.66$ cm. The incidence angles of
the two sources are randomly selected from $[0^{\circ},90^{\circ}]$ and
$[0^{\circ},-90^{\circ}]$ respectively per mixture, where the direction normal
to the line connecting two microphones is $0^{\circ}$. The image source model
[27] is used to generate the room impulse responses, where the sound
absorption coefficients are calculated by Sabine’s Formula [28] with the room
aforementioned room size and reverberation time $T_{60}$ changing from $0$ to
$600$ ms with an interval of $50$ ms. For each combination of sources (there
are four combinations) and every value of $T_{60}$, $100$ mixtures are
generated for evaluation. The sampling rate is $16$ kHz.

The parameters $\mu$ and $\gamma$ of SDILRMA were set to $100$, and $10$,
respectively. We compared SDILRMA with AuxIVA [10], MNMF [24], ILRMA [5],
$t$-ILRMA and sGD-ILRMA [22]. The performance metrics used are the signal-to-
distortion ration (SDR) and source-to-interferences ratio (SIR) [26].

Figure 1 presents the results in terms of the average SDR and SIR
improvements. It is seen that SDILRMA outperforms MNMF, ILRMA, $t$-ILRMA and
sGD-ILRMA, which demonstrates the effectiveness of SDILRMA for source
separation.

Figure 2: The spectrograms of the source and separated signals. Left panels:
the original source signals. Middle panels: the separated signals by ILRMA.
Right panels: the separated signals by SDILRMA.

Figure2 plots the spectrograms of the source signals as well as the signals
estimated by ILRMA and SDILRMA. It is seen that both ILRMA and SDILRMA are
effective. ILRMA suffers from a small number of permutations, which are not
seen in SDILRMA. This, again, demonstrates the superiority of SDILRMA.

## 6 CONCLUSION

This paper studied the determined BSS problem for audio and speech
applications. We presented an improved version of ILRMA, which applies NMF to
decompose the time-varying source model and Sinkhorn divergence as the cost
function to optimize the model parameters. To simplify the algorithm to reduce
its computational complexity, the Kronecker product tool was used to decompose
the modeling matrix into the product of a number of matrices of much smaller
dimensionality, resulting in a simplified SDILRMA algorithm. Simulation
results verified that the simplified SDILRMA is able to achieve better BSS
performance than ILRMA and is also computationally more efficient than its
counterpart without Kronecker product decomposition.

## REFERENCES

##

  * [1] Benesty J, Makino S, Chen J. Speech enhancement. New York, NY, USA: Springer, 2005.
  * [2] Makino S, Lee TW, Sawada H. Blind Speech Separation. New York, NY, USA: Springer, 2007.
  * [3] Li Y, Amari S, Cichocki A, Ho DWC, Xie S. Underdetermined blind source separation based on sparse representation. IEEE Trans. Signal Process., vol. 54, no. 2, pp. 423–437, Feb. 2006.
  * [4] Bofill P, Zibulevsky M. Underdetermined blind source separation using sparse representations. Signal Process. vol. 81, no. 11, pp. 2353–2362, Nov. 2001.
  * [5] Kitamura D, Ono N, Sawada H, Kameoka H, Saruwatari H. Determined blind source separation unifying independent vector analysis and nonnegative matrix factorization. IEEE/ACM Trans. Audio, Speech, Lang. Process., vol. 14, no. 9, pp. 1626–1641, Sep. 2016.
  * [6] Benesty J, Chen J, Habets E. Speech Enhancement in the STFT Domain. Berlin: Springer-Verlag, 2011.
  * [7] Huang H, Zhao L, Benesty J, Chen J. A minimum-variance-distortionless-response filter based on the bifrequency spectrum for single-channel noise reduction. Digital Sig. Process., vol. 33, pp. 169–179, Oct. 2014.
  * [8] Comon P. Independent component analysis, a new concept. Signal Process., vol. 36, no. 3, pp. 287–314, Apri. 1994.
  * [9] Kim T, Eltoft T, Lee TW. Independent vector analysis: An extension of ICA to multivariate components. in Proc. Int. Conf. Independent Compon. Anal. Blind Source Separation, Oct. 2006, pp. 165–172.
  * [10] Ono N. Stable and fast update rules for independent vector analysis based on auxiliary function technique. in Proc. IEEE Workshop Appl. Signal Process. Audio Acoust., 2011, pp. 189–192.
  * [11] Vallender S. Calculation of the wasserstein distance between probability distributions on the line. Theory of Probability& Its Applications, vol. 18, no. 4, pp. 784–786, 1974.
  * [12] Kantorovic LV, Rubinstein GS. On a functional space and certain extremum problems. in _Doklady Akademii Nauk_ , Russian Academy of Sciences, vol. 115, pp. 1058–1061, 1957.
  * [13] Cuturi M. Sinkhorn distances: Light-speed computation of optimal transport. in Advances in Neural Information Processing Systems (NIPS). Red Hook, NY, USA: Curran, 2013, pp. 2292–-2300.
  * [14] Rolet A, Cuturi M, Peyré G. Fast dictionary learning with a smoothed wasserstein loss. in Proc. Int. Conf. Artif. Intell. Stat., Cadiz, Spain, May 2016, pp. 630–-638.
  * [15] Benzi M, Simoncini V. Approximation of functions of large matrices with Kronecker structure. Numerische Mathematik, vol. 135 no. 1, pp. 1–-26, Jan. 2017.
  * [16] Motamed M. Hierarchical Low-Rank Approximation of Regularized Wasserstein Distance. arXiv preprint arXiv:2004.12511, 2020.
  * [17] Févotte C, Cardoso JF. Maximum likelihood approach for blind audio source separation using time-frequency Gaussian source models. in Proc. IEEE Workshop Appl. Signal Process. Audio Acoust., Oct. 2005, pp. 78–81.
  * [18] Vincent E, Jafari MG, Abdallah SA, Plumbley MD, Davies ME. Probabilistic modeling paradigms for audio source separation. In Machine Audition: Principles, Algorithms and Systems. IGI global, pp. 162–185, 2011.
  * [19] Brehm H, Stammler W. Description and generation of spherically invariant speech-model signals. Signal Process. vol. 12, no. 2, pp. 119–141, Mar. 1987.
  * [20] Buchner H, Aichner R, Kellermann W. Blind source separation for convolutive mixtures: A unified treatment. In Audio signal processing for next-generation multimedia communication systems (pp. 255–293). Springer, Boston, MA, 2004.
  * [21] Wang J, Guan S, Liu S, Zhang XL. Minimum-Volume Multichannel Nonnegative Matrix Factorization for Blind Audio Source Separation. IEEE/ACM Trans. Audio, Speech, Lang. Process., vol. 23, no. 3089–3103, Aug. 2021.
  * [22] Mogami S, Takamune N, Kitamura D, Saruwatari H, Takahashi Y, Kondo K, Ono N. Independent low-rank matrix analysis based on time-variant sub-Gaussian source model for determined blind source separation. IEEE/ACM Trans. Audio, Speech, Lang. Process., vol. 28, pp. 503–518, Dec. 2019.
  * [23] Garofolo J, Graff D, Paul D, Pallett D. Csr-i (wsj0) complete ldc93s6a. Web Download. Philadelphia: Linguistic Data Consortium, 83, 1993.
  * [24] Sawada H, Kameoka H, Araki S, Ueda N. Multichannel extensions of non-negative matrix factorization with complex-valued data. IEEE Trans. Audio Speech Lang. Process, vol. 21, no. 5, pp. 971–982, Jan. 2013.
  * [25] Araki S, Nesta F, Vincent E, Koldovský Z, Nolte G, Ziehe A, Benichoux A. The 2011 signal separation evaluation campaign (SiSEC2011):-audio source separation. LVA/ICA (pp. 414–422). Springer, Berlin, Heidelberg 2012.
  * [26] Vincent E, Gribonval R, Févotte C. Performance measurement in blind audio source separation. IEEE Trans. Audio, Speech, Lang. Process., vol. 14, no. 4, pp. 1462–1469, June 2006.
  * [27] Allen JB, Berkley DA. Image method for efficiently simulating small-room acoustics. J. Acoust. Soc. Amer., vol. 65, no. 4, pp. 943–950, Apr. 1979.
  * [28] Young RW. Sabine reverberation equation and sound power calculations. The Journal of the Acoustical Society of America, vol. 31, no. 7, pp. 912–-921, July 1959.


11institutetext: University of Science and Technology of China, Hefei, China
11email<EMAIL_ADDRESS>22institutetext: Xidian University,
Xi’an, China
22email<EMAIL_ADDRESS>
33institutetext: Ping An Technology (Shenzhen) Co., Ltd., Shenzhen, China
33email<EMAIL_ADDRESS>
# BeamAttack: Generating High-quality Textual Adversarial Examples through
Beam Search and Mixed Semantic Spaces

Hai Zhu 1133(This work was done when the author was at Ping An Technology
(Shenzhen) Co., Ltd.(This work was done when the author was at Ping An
Technology (Shenzhen) Co., Ltd.)) Qinyang Zhao 22 Yuren Wu 33

###### Abstract

Natural language processing models based on neural networks are vulnerable to
adversarial examples. These adversarial examples are imperceptible to human
readers but can mislead models to make the wrong predictions. In a black-box
setting, attacker can fool the model without knowing model’s parameters and
architecture. Previous works on word-level attacks widely use single semantic
space and greedy search as a search strategy. However, these methods fail to
balance the attack success rate, quality of adversarial examples and time
consumption. In this paper, we propose BeamAttack, a textual attack algorithm
that makes use of mixed semantic spaces and improved beam search to craft
high-quality adversarial examples. Extensive experiments demonstrate that
BeamAttack can improve attack success rate while saving numerous queries and
time, e.g., improving at most 7% attack success rate than greedy search when
attacking the examples from MR dataset. Compared with heuristic search,
BeamAttack can save at most 85% model queries and achieve a competitive attack
success rate. The adversarial examples crafted by BeamAttack are highly
transferable and can effectively improve model’s robustness during adversarial
training. Code is available at https://github.com/zhuhai-
ustc/beamattack/tree/master

###### Keywords:

Adversarial Examples Robustness Natural Language Processing

##  1 Introduction

In recent years, neural networks have achieved great success in the natural
language processing field while being vulnerable to adversarial examples.
These adversarial examples are original inputs altered by some tiny
perturbations [9, 20]. It is worth noting that perturbations are imperceptible
to humans but can mislead the model decision. Therefore, it is essential to
explore adversarial examples since our goal is to improve the reliability and
robustness of the model, especially on some security-critical applications,
such as toxic text detection and public opinion analysis [25]. Compared to
image and speech attacks [22, 2], it is more challenging in crafting textual
adversarial examples due to the discrete of natural language. In addition,
there are some grammar constraints in the textual adversarial examples:(1)the
crafted examples should keep the same meaning as the original
texts,(2)generated examples should look natural and grammatical. However,
previous works barely conform to all constraints, or satisfy the above
constraints at the cost of reducing the attack success rate.

Conventional word-level attack algorithms can be roughly divided into three
steps: (1) calculating word importance score according to the changes of class
label probabilities after replacing this word, (2) searching synonyms for each
origin word, (3) selecting the substitution that reduces the class label
probabilities most and replacing origin word with it until model predicts
wrong. The problem is that previous works only use a single semantic space to
search synonyms, which limits the diversity of substitutions and cut down the
search space. In addition, most prior works introduce greedy search to select
the best substitution with the maximum change of class label probabilities [9,
11]. Greedy search limits the search space and sometimes leads to local
optimal solution and word over-substitution. Therefore, some works [26, 20]
introduce heuristic search to improve attack success rate, at the cost of
time-consuming and numerous model queries. In generally, previous works fail
to balance the attack success rate, quality of adversarial examples and time
consumption.

In this paper, we propose BeamAttack, a textual attack algorithm based on
mixed semantic spaces and beam search. Specially, we search substitutions from
word embedding space and BERT respectively, and filter out the bad synonyms to
improve semantic similarity of adversarial examples, then improve beam search
to craft adversarial examples, which greatly expands the search space by
controlling beam size. Therefore, it is capable of escaping from local optima
within acceptable number of model queries. Furthermore, we evaluate BeamAttack
by attacking various neural networks on five datasets. Experiments show that
it outperforms other baselines in attack success rate and semantic similarity
while saving numerous model queries. Our main contributions are summarized as
follows:

  * •

We propose the mixed semantic spaces, making full use of word embedding space
and BERT simultaneously to expand the diversity of substitutions and
generating high-qualify adversarial examples.

  * •

We propose BeamAttack, a black-box attack algorithm which improves beam search
to expand search space and reduce the redundancy word substitution.

  * •

Experiments show that BeamAttack achieves the trade-off results compared with
previous works. In addition, adversarial examples crafted by BeamAttack with
high semantic similarity, low perturbation, and good transferability.

##  2 Related Work

We divide the existing textual attack algorithms into char-level, word-level
and sentence-level attacks based on granularity. Char-level attacks generate
adversarial examples by inserting, swapping or removing characters(such as
’attack’ $\rightarrow$ ’atttack’) [12, 6], which can be easily rectified by
word spelling machine. Sentence-level attacks insert some perturbed sentences
into the origin paragraph to confuse models [3]. Nevertheless, these
adversarial examples contain many lexical errors.

In order to generate high-quality adversarial examples, word-level attacks
have gradually become a prevalent approach. Word-level attacks substitute the
origin words with synonyms(such as ’like’ $\rightarrow$ ’love’). Traditional
strategies search synonyms from word embedding space. For example, some works
[14, 9, 23] calculate the word saliency and greedily substitute words with
synonyms derived from WordNet [16], or utilizing word importance score and
replace words with synonyms from counter-fitting word vectors [18]. Recently,
researcher [13, 7, 11] search synonyms from pre-trained language models (e.g.
BERT, RoBERTa). The pre-trained language models are trained on massive text
data, and predict the masked words. Therefore, it has the ability to predict
contextual-aware words.

Above attack algorithms adopt the greedy search, which limits the search space
and leads to local optimal solution. Minor work have explored the heuristic
search, such as genetic algorithm [20],particle swarm optimization [26].
However, heuristic search is very time-consuming and requires a lot of model
queries. Therefore, we propose BeamAttack, searching synonyms from word
embedding space and BERT simultaneously, and fine-tuning beam search to expand
search space and reduce word-over substitution.

##  3 Beam Search Adversarial Attack

BeamAttack is divided into three steps. There are word importance calculation,
mixed semantic spaces and improved beam search. The overview of BeamAttack is
shown in the Figure 1. Before delving into details, we present the attack
settings and problem formulation.

###  3.1 Black-box Untargeted Attack

The BeamAttack belongs to black-box attacks, it has nothing about model’s
architecture, parameters and gradients, only class label probabilities are
accessible. Given a sentence of $n$ words
$\mathcal{X}=[x_{1},x_{2},\cdots,x_{n}]$ and label set $\mathcal{Y}$, a well-
trained model can classify sentence correctly:

$\mathop{\text{argmax}}\limits_{y_{i}\in\mathcal{Y}}P(y_{i}|\mathcal{X})=y_{true}$
(1)

The adversarial example
$\mathcal{X}^{\prime}=[x^{{}^{\prime}}_{1},x^{{}^{\prime}}_{2},\cdots,x^{{}^{\prime}}_{n}]$
is crafted to make model predict wrong. In addition, there are some
constraints on the word substitution rate($\mathop{\text{WSR}}$) and semantic
similarity($\mathop{\text{SIM}}$) of the adversarial example.
$\mathcal{X}^{\prime}$ should be close to $\mathcal{X}$ and a human reader
hardly differentiate the modifications. The mathematical expression is as
follows:

$\begin{split}&\mathop{\text{argmax}}\limits_{y_{i}\in\mathcal{Y}}P(y_{i}|\mathcal{X^{\prime}})\neq
y_{true}\\\
\text{s.t.}&\mathop{\text{SIM}}(\mathcal{X^{\prime}},\mathcal{X})>\mathcal{L};\mathop{\text{WSR}}(\mathcal{X^{\prime}},\mathcal{X})<\sigma\end{split}$
(2)

Figure 1: The overview of BeamAttack. Candidate sets are substitutions
generated from BERT and word embedding space. Black lines are beam search
paths, wherein red lines are the optimal search path.

###  3.2 Word Importance Calculation

Given a sentence of $n$ words $\mathcal{X}=[x_{1},x_{2},\cdots,x_{n}]$, only
some important words will affect the prediction results of the model
$\mathcal{F}$. In order to measure the importance of $x_{i}$, we follow the
calculation proposed in TextFooler [9]. We replace $x_{i}$ with ’[oov]’111the
word out-of-vocabulary. to form
$\mathcal{X}/\\{x_{i}\\}=[x_{1},\cdots,x_{i-1},[oov],x_{i+1},\cdots,x_{n}]$,
then word importance of $x_{i}$ is calculated as follows:

  * •

The predicted label remains the same after replace, i.e.,
$\mathcal{F}(\mathcal{X})=\mathcal{F}(\mathcal{X}/\\{x_{i}\\})=y_{true}$,

$I(x_{i})=\mathcal{F}_{y_{true}}(\mathcal{X})-\mathcal{F}_{y_{true}}(\mathcal{X}/\\{x_{i}\\})$
(3)

  * •

The predicted label is changed after replace, i.e.,
$\mathcal{F}(\mathcal{X})=y_{true}\neq
y_{other}=\mathcal{F}(\mathcal{X}/\\{x_{i}\\})$,

$\begin{split}I(x_{i})=&\mathcal{F}_{y_{true}}(\mathcal{X})-\mathcal{F}_{y_{true}}\left(\mathcal{X}/\\{x_{i}\\}\right)+\\\
&\mathcal{F}_{y_{other}}\left(\mathcal{X}/\\{x_{i}\\}\right)-\mathcal{F}_{y_{other}}(\mathcal{X})\end{split}$
(4)

where $\mathcal{F}_{y}(\mathcal{X})$ represents the predicted class label
probability of $\mathcal{X}$ by $\mathcal{F}$ on label $y$. In order to
improve the readability and fluency of the adversarial examples, we will
filter out stopwords by NLTK222https://www.nltk.org/ after calculating the
word importance.

###  3.3 Mixed Semantic Spaces

After ranking the words by their importance score, we need to search synonyms,
which is a candidate words set $\mathcal{C}(x_{i})$ for each word $x_{i}$. A
proper replacement word should (i) have similar semantic meaning with original
input, (ii) avoid some obvious grammar errors, (iii) and confuse model
$\mathcal{F}$ to predict the wrong label. There are two different semantic
spaces to search synonyms, word embedding spaces and pre-trained language
models.

  * •

The former searches for synonyms from word embedding spaces, such as WordNet
space [16], HowNet space [5] and Counter-fitting word vectors [18]. Word
embedding spaces can quickly generate synonyms with the same meaning as origin
word.

  * •

The later searches for synonyms through pre-trained language models(such as
BERT). Given a sentence of $n$ words $\mathcal{X}=[x_{1},x_{2},\cdots,x_{n}]$,
we replace each word $x_{i}$ with ’[MASK]’, and get candidate words set
$\mathcal{C}(x_{i})$ predicted by BERT. Pre-trained language models produce
fluent and contextual-aware adversarial examples.

We combine word embedding space and BERT to make full use of the advantage of
different semantic spaces. In detail, for each word $x_{i}$, we respectively
select top $N$ synonyms from word embedding space and BERT to form a candidate
words set $\mathcal{C}(x_{i})$. To generate high-qualify adversarial examples,
we filter out the candidate words set that has different part-of-
speech(POS)333 https://spacy.io/api/tagger synonyms with $x_{i}$. In addition,
for each $c\in\mathcal{C}(x_{i})$, we substitute it for $x_{i}$ to generate
adversarial example
$\mathcal{X^{\prime}}=[x_{1},\cdots,x_{i-1},c,x_{i+1},\cdots,x_{n}]$, then we
measure semantic similarity between $\mathcal{X}$ and adversarial example
$\mathcal{X^{\prime}}$ by universal sentence
encoder(USE)444https://tfhub.dev/google/ universal-sentence-encoder, which
encodes original input $\mathcal{X}$ and adversarial example
$\mathcal{X^{\prime}}$ as dense vectors and use cosine similarity as a
approximation of semantic similarity. Only synonyms whose similarity is higher
than threshold $L$ will be retained in the candidate words set
$\mathcal{C}(x_{i})$.

###  3.4 Improved Beam Search

After filtering out the candidate words set $\mathcal{C}(x_{i})$, the
construction of adversarial examples is a combinatorial optimization problem
as expected in Eq.2. Previous works use the greedy search since it solely
selects the token that maximizes the probability difference, which leads to
local optima and word-over substitution.

To tackle this, we improve beam search to give consideration to both attack
success rate and algorithm efficiency. Beam search has a hyper-parameter
called beam size $\mathcal{K}$. Naive beam search only selects top
$\mathcal{K}$ adversarial examples from the current iteration results. In the
improved beam search, we merge the output of the last iteration to the current
iteration and select top $\mathcal{K}$ adversarial examples as the input of
the next iteration jointly. In detail, for each word $x_{i}$ in the original
text, we replace $x_{i}$ with the substitution from candidate words set
$\mathcal{C}(x_{i})$ to generate adversarial examples $\mathcal{X^{\prime}}$
and calculate the probability differences. The top $\mathcal{K}$ adversarial
examples $\mathcal{X^{\prime}}$ with the maximum probability
difference(including the last iteration of top $\mathcal{K}$ adversarial
examples) are selected as the input of the next iteration until the attack
succeeds or all origin words are iterated. It is worth noting that greedy
search is a special case of $\mathcal{K}=1$. The details of BeamAttack are
shown in algorithm 1.

Algorithm 1 BeamAttack Adversarial Algorithm

Input:Original text $\mathcal{X}$, target model $\mathcal{F}$, semantic
similarity threshold $\mathcal{L}=0.5$ and beam size $\mathcal{K}=10$, number
of words in original text $n$
Output:Adversarial example $\mathcal{X}_{\text{adv}}$.

1: $\mathcal{X}_{\text{adv}}\leftarrow\mathcal{X}$

2: $set({\mathcal{X}_{\text{adv}}})\leftarrow\mathcal{X}_{\text{adv}}$

3: for each word $x_{i}$ in $\mathcal{X}$ do

4: Compute the importance score $I(x_{i})$ via Eq.3 and 4.

5: end for

6: Sort the words with importance score $I(x_{i})$

7: for $i=1$ to $n$ do

8: Replace the $x_{i}$ with [MASK]

9: Generate the candidate set $\mathcal{C}(x_{i})$ from BERT and Word
Embedding Space

10: $\mathcal{C}(x_{i})$ $\leftarrow$ POSFilter($\mathcal{C}(x_{i})$) $\cap$
USEFilter($\mathcal{C}(x_{i})$)

11: end for

12: for $\mathcal{X}_{\text{adv}}$ in $set(\mathcal{X}_{\text{adv}})$ do

13: for $c_{k}$ in $\mathcal{C}(x_{i})$ do

14: $\mathcal{X^{\prime}}_{\text{adv}}$ $\leftarrow$ Replace $x_{i}$ with
$c_{k}$ in $\mathcal{X}_{\text{adv}}$

15: Add $\mathcal{X^{\prime}}_{\text{adv}}$ to the
$set(\mathcal{X}_{\text{adv}})$

16: end for

17: for $\mathcal{X^{\prime}}_{\text{adv}}$ in $set(\mathcal{X}_{\text{adv}})$
do

18: if $\mathcal{F}(\mathcal{X^{\prime}}_{\text{adv}})\neq y_{true}$ then

19: return $\mathcal{X^{\prime}}_{\text{adv}}$ with highest semantic
similarity

20: end if

21: end for

22: $set(\mathcal{X}_{\text{adv}})$ $\leftarrow$ Select top $\mathcal{K}$
adversarial examples in $set(\mathcal{X}_{\text{adv}})$

23: $i\leftarrow i+1$

24: if $i>n$ then

25: break

26: end if

27: end for

28: return adversarial examples $\mathcal{X}_{\text{adv}}$

##  4 Experiments

Tasks, Datasets and Models. To evaluate the effectiveness of BeamAttack, we
conduct experiments on two NLP tasks, including text classification and text
inference. In particular, the experiments cover various datasets, such as MR
[19],IMDB [15],SST-2 [21], SNLI [1] and MultiNLI [24]. We train three neural
networks as target models including CNN [10], LSTM [8] and BERT [4]. Model
parameters are consistent with TextFooler’s[9] setting.

Baselines. To quantitatively evaluate BeamAttack, we compare it with other
black-box attack algorithms, including TextFooler(TF) [9], PWWS [20], BAE [7],
Bert-Attack(BEAT) [13] and PSO [26], wherein TF,PWWS and PSO search synonyms
from word embedding spaces, BAE and BEAT search synonyms from BERT. In
addition, PSO belongs to heuristics search and other belong to greedy search.
These baselines are implemented on the TextAttack framework [17].

Automatic Evaluation Metrics. We evaluate the attack performance by following
metrics. Attack Success Rate(ASR) is defined as the proportion of successful
adversarial examples to the total number of examples. Word Substitution
Rate(WSR) is defined as the proportion of number of replacement words to
number of origin words. Semantic Similarity(SIM) is measured by Universal
Sentence Encoder(USE). Query Num(Query) is the number of model queries during
adversarial attack. The ASR evaluates how successful the attack is. The WSR
and semantic similarity together evaluate how semantically similar the
original texts and adversarial examples are. Query num can reveal the
efficiency of the attack algorithm.

Implementation Details. In our experiments, we carry out all experiments on
NVIDIA Tesla P100 16G GPU. We set the beam size $\mathcal{K}=10$, number of
each candidate set $N=50$, semantic similarity threshold $\mathcal{L}=0.5$, we
take the average value of 1000 examples as the final experimental result.

###  4.1 Experimental Results

The experiment results are listed in Table 1. It is worth noting that
BeamAttack achieves higher ASR than baselines on almost all scenarios.
BeamAttack also reduces the WSR on some datasets(MR,IMDB and SST-2). We
attribute this superiority to the fine-tuned beam search, as this is the major
improvement of our algorithm compared with greedy search. BeamAttack has
chance to jump out of the local optimal solution and find out the adversarial
examples with lower perturbation by expanding the search space. In terms of
model robustness, BERT has better robustness than traditional classifiers(CNN
and LSTM), since the attack success rate of attacking BERT is lower than other
models.

Table 1: The attack success rate and word substitution rate of different
attack algorithms on five datasets. The “Origin ACC(%)” denotes the target
model’s test accuracy on the original inputs.

Datasets |  Target Models |  Origin ACC | Attack Success Rate(ASR(%)) | Word Substitution Rate(WSR(%))
---|---|---|---|---
TF | PWWS | BAE | BEAT | PSO | BeamAttack | TF | PWWS | BAE | BEAT | PSO | BeamAttack
MR | CNN | 80.4 | 98.81 | 98.61 | 98.00 | 83.31 | 96.23 | 99.87 | 17.05 | 13.22 | 12.98 | 15.06 | 11.53 | 8.29
LSTM | 80.7 | 98.92 | 97.92 | 98.21 | 84.12 | 95.32 | 99.90 | 15.61 | 13.07 | 11.71 | 13.59 | 10.91 | 8.60
BERT | 90.4 | 90.54 | 81.53 | 90.61 | 88.36 | 92.47 | 97.88 | 20.91 | 14.67 | 14.44 | 15.32 | 11.93 | 9.70
IMDB | CNN | 89.2 | 100 | 100 | 100 | 99.82 | 100 | 100 | 2.51 | 2.23 | 2.01 | 3.32 | 2.43 | 2.11
LSTM | 89.8 | 99.76 | 99.47 | 100 | 99.83 | 100 | 100 | 3.12 | 3.11 | 2.25 | 3.45 | 2.46 | 2.43
BERT | 90.9 | 88.83 | 86.55 | 83.96 | 88.68 | 89.93 | 91.6 | 3.81 | 5.02 | 7.69 | 5.66 | 4.32 | 1.65
SST-2 | CNN | 82.5 | 92.37 | 98.23 | 95.45 | 86.44 | 96.69 | 99.88 | 17.09 | 13.10 | 12.53 | 15.40 | 11.47 | 8.46
LSTM | 84.6 | 93.21 | 98.48 | 96.23 | 86.43 | 96.42 | 100 | 17.55 | 13.53 | 12.83 | 15.31 | 11.45 | 8.76
SNLI | BERT | 89.1 | 96.00 | 98.42 | 98.84 | 98.64 | 92.51 | 99.80 | 17.26 | 13.72 | 6.91 | 7.80 | 8.19 | 13.81
MNLI | BERT | 85.1 | 90.44 | 94.33 | 99.23 | 92.00 | 83.43 | 99.50 | 13.93 | 10.12 | 5.45 | 5.64 | 6.65 | 10.81

Semantic Similarity. Except ASR and WSR, fluent and contextual-aware
adversarial examples are also essential. Figure 2 plots the semantic
similarity of adversarial examples generated by different attack algorithms.
Clearly, BeamAttack achieves the highest semantic similarity than other attack
algorithms.

Figure 2: The semantic similarity between origin inputs and adversarial
examples.

Qualitative Examples. To more intuitively contrast the fluency of adversarial
examples, we list some adversarial examples generated by different attack
algorithms in Table 2. Compared with other methods, Beamattack not only
ensures the semantic similarity between replacement words and original words
but also successfully misleads the model with the minimum perturbation.

Table 2: The adversarial example crafted by different attack algorithms on MR(BERT) dataset. Replacement words are represented in red.  Origin Text (Positive) |  The experience of the roles in the play makes us generates an enormous feeling of empathy for its characters.
---|---
BAE (Negative) |  The experience of the roles in the play makes us generates an excessive need of empathy for its characters.
PWWS (Negative) |  The experience of the roles in the play makes us render an enormous smell of empathy for its eccentric.
TextFooler (Negative) |  The experience of the roles in the play makes us leeds an enormous foreboding of empathy for its specs.
BeamAttack (Negative) |  The experience of the roles in the play makes us generates an enormous feeling of pity for its characters.

Model Query. The number of model queries measures the effectiveness of attack
algorithm. Table 3 lists the model queries of various attack algorithms.
Results show that although our BeamAttack needs more model queries than greedy
search(such as TF), compared with the PSO attack algorithm, which adopts
heuristic search, our algorithm obtains competitive results with extremely few
model queries.

Table 3: The average model queries of different attack algorithms on five datasets. Beam size $\mathcal{K}=10$ |  MR |  IMDB |  SST-2 |  SNLI |  MNLI
---|---|---|---|---|---
TF |  113.8 |  536.7 |  146.2 |  54.1 |  68.9
PWWS |  285.4 |  3286.5 |  5054.3 |  137.7 |  157.4
BAE |  104.2 |  567.1 |  171.0 |  75.5 |  75.1
BEAT |  207.9 |  585.0 |  245.6 |  93.6 |  119.2
PSO |  5124.5 |  15564.3 |  3522.8 |  416.6 |  1124.8
BeamAttack |  650.3 |  2135.8 |  584.3 |  126.0 |  174.0

###  4.2 Ablation Study

The effect of beam size $\mathcal{K}$. To validate the effectiveness of beam
size $\mathcal{K}$, we use BERT as the target model and test on MR dataset
with different beam size $\mathcal{K}$. When $\mathcal{K}=1$, beam search is
equal to greedy search. As shown in Table 4, the attack success rate increases
gradually with the grow of beam size $\mathcal{K}$.

Table 4: The effect of beam size $\mathcal{K}$ on MR(BERT) dataset. Beam Size |  ASR(%) |  WSR(%) |  Similarity(%) |  Query
---|---|---|---|---
$\mathcal{K}=1$ |  89.0 |  15.5 |  81.3 |  101.3
$\mathcal{K}=2$ |  90.6 |  15.3 |  82.0 |  150.4
$\mathcal{K}=5$ |  91.6 |  15.1 |  82.8 |  312.6
$\mathcal{K}=7$ |  92.3 |  15.1 |  83.0 |  411.1
$\mathcal{K}=10$ |  92.6 |  15.1 |  83.1 |  516.2

The effect of mixed semantic spaces. Another major improvement of our
BeamAttack is that substitutions are selected from mixed semantic spaces. As
shown in the Table 5, we study the impact of different semantic spaces on
different metrics. Compared with single word embedding space or BERT, using
both word embedding space and BERT to generate adversarial examples can obtain
higher attack success rate, semantic similarity and lower word substitution
rate.

Table 5: The effect of different semantic spaces on MR(BERT) dataset. semantic space |  ASR(%) |  WSR(%) |  Similarity(%) |  Query
---|---|---|---|---
Embedding |  89.0 |  15.3 |  81.2 |  101.3
BERT |  93.6 |  13.1 |  82.6 |  101.1
Embedding+BERT |  95.3 |  11.7 |  84.9 |  140.3

###  4.3 Transferability

The transferability of adversarial examples reflects property that adversarial
examples crafted by classifier $\mathcal{F}$ can also fool other unknown
classifier $\mathcal{F^{\prime}}$. We evaluate the transferability on MR
dataset across CNN,LSTM and BERT. In detail, we use the adversarial examples
crafted for attacking BERT on MR dataset to evaluate the transferability for
CNN and LSTM models. As shown in the Figure 3, the adversarial examples
generated by BeamAttack achieve the higher transferability than baselines.

Figure 3: Transfer attack on MR dataset. Lower accuracy indicates higher
transferability (the lower the better).

###  4.4 Adversarial Training

Adversarial training is a prevalent technique to improve the model’s
robustness by adding some adversarial examples into train data. To validate
this, we train the CNN model on the MR dataset and obtains 80.4% test
accuracy. Then we randomly generate 1000 MR adversarial examples to its
training data and retrain the CNN model. The result is shown in the Table 6,
CNN model obtains 83.3% test accuracy, higher than origin test accuracy.
Although there is no significant change in ASR, BeamAttack needs to replace
more words and more model queries to attack successfully with WSR and model
queries increasing. It indicates that adversarial training effectively
improves the generalization and robustness of the model.

Table 6: The performance of CNN with(out) adversarial training on the MR dataset. |  Origin ACC(%) |  ASR(%) |  WSR(%) |  SIM(%) |  Query
---|---|---|---|---|---
Original |  80.4 |  99.87 |  8.20 |  91.08 |  563.1
Adv.Training |  83.3 |  99.75 |  8.67 |  90.82 |  606.4

##  5 Conclusion

In this paper, we propose an efficient adversarial textual attack algorithm
BeamAttack. The BeamAttack makes full use of word embedding space and BERT to
generate substitutions and fine-tune beam search to expand search spaces.
Extensive experiments demonstrate BeamAttack balances the attack success rate,
qualify of adversarial examples and time consumption. In addition, the
adversarial examples crafted by BeamAttack are contextual-aware and improve
models’ robustness during adversarial training.

## References

  * [1] Bowman, S.R., Angeli, G., Potts, C., Manning, C.D.: large annotated corpus for learning natural language inference. In: Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing. pp. 632–642 (2015)
  * [2] Carlini, N., Wagner, D.: Audio adversarial examples: Targeted attacks on speech-to-text. In: 2018 IEEE Security and Privacy Workshops. pp. 1–7 (2018)
  * [3] Cheng, M., Yi, J., Chen, P.Y., Zhang, H., Hsieh, C.J.: Seq2sick: Evaluating the robustness of sequence-to-sequence models with adversarial examples. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 34, pp. 3601–3608 (2020)
  * [4] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidirectional transformers for language understanding. In: Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pp. 4171–4186 (2019)
  * [5] Dong, Z., Dong, Q., Hao, C.: Hownet and its computation of meaning. In: Proceedings of the 23rd International Conference on Computational Linguistics: Demonstrations. pp. 53–56 (2010)
  * [6] Gao, J., Lanchantin, J., Soffa, M.L., Qi, Y.: Black-box generation of adversarial text sequences to evade deep learning classifiers. In: 2018 IEEE Security and Privacy Workshops. pp. 50–56 (2018)
  * [7] Garg, S., Ramakrishnan, G.: BAE: BERT-based adversarial examples for text classification. In: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing. pp. 6174–6181 (2020)
  * [8] Hochreiter, S., Schmidhuber, J.: Long short-term memory. In: Neural Computation. vol. 9, pp. 1735–1780 (1997)
  * [9] Jin, D., Jin, Z., Zhou, J.T., Szolovits, P.: Is bert really robust? a strong baseline for natural language attack on text classification and entailment. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 34, pp. 8018–8025 (2020)
  * [10] Kim, Y.: Convolutional neural networks for sentence classification. In: Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing. pp. 1746–1751 (2014)
  * [11] Li, D., Zhang, Y., Peng, H., Chen, L., Brockett, C., Sun, M.T., Dolan, B.: Contextualized perturbation for textual adversarial attack. In: Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pp. 5053–5069 (2021)
  * [12] Li, J., Ji, S., Du, T., Li, B., Wang, T.: Textbugger: Generating adversarial text against real-world applications. In: 26th Annual Network and Distributed System Security Symposium. p. 55 (2019)
  * [13] Li, L., Ma, R., Guo, Q., Xue, X., Qiu, X.: BERT-ATTACK: Adversarial attack against BERT using BERT. In: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing. pp. 6193–6202 (2020)
  * [14] Ma, G., Shi, L., Guan, Z.: Adversarial text generation via probability determined word saliency. In: International Conference on Machine Learning for Cyber Security. pp. 562–571 (2020)
  * [15] Maas, A., Daly, R.E., Pham, P.T., Huang, D., Ng, A.Y., Potts, C.: Learning word vectors for sentiment analysis. In: Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pp. 142–150 (2011)
  * [16] Miller, George, A.: Wordnet: a lexical database for english. In: Communications of the ACM. vol. 38, pp. 39–41 (1995)
  * [17] Morris, J., Lifland, E., Yoo, J.Y., Grigsby, J., Jin, D., Qi, Y.: Textattack: A framework for adversarial attacks, data augmentation, and adversarial training in nlp. In: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing. pp. 119–126 (2020)
  * [18] Mrksic, N., Séaghdha, D.Ó., Thomson, Blaise.and Gasic, M., Rojas-Barahona, Lina, M., Su, P.H., Vandyke, D., Wen, T.H., Young, S.J.: Counter-fitting word vectors to linguistic constraints. In: Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pp. 142–148 (2016)
  * [19] Pang, B., Lee, L.: Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales. In: Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pp. 115–124 (2005)
  * [20] Ren, S., Deng, Y., He, K., Che, W.: Generating natural language adversarial examples through probability weighted word saliency. In: Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pp. 1085–1097 (2019)
  * [21] Socher, R., Perelygin, A., Wu, J., Chuang, J., Manning, C.D., Ng, A.Y., Potts, C.: Recursive deep models for semantic compositionality over a sentiment treebank. In: Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing. pp. 1631–1642 (2013)
  * [22] Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., Fergus, R.: Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 (2013)
  * [23] Wang, Z., Zheng, Y., Zhu, H., Yang, C., Chen, T.: Transferable adversarial examples can efficiently fool topic models. In: Computers & Security. vol. 118, p. 102749 (2022)
  * [24] Williams, A., Nangia, N., Bowman, S.: A broad-coverage challenge corpus for sentence understanding through inference. In: Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pp. 1112–1122 (2018)
  * [25] Yang, X., Liu, W., Tao, D., Liu, W.: Besa: Bert-based simulated annealing for adversarial text attacks. In: International Joint Conference on Artificial Intelligence. pp. 3293–3299 (2021)
  * [26] Zang, Y., Qi, F., Yang, C., Liu, Z., Zhang, M., Liu, Q., Sun, M.: Word-level textual adversarial attacking as combinatorial optimization. In: Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. pp. 6066–6080 (2020)