# Deep Learning Meets Adaptive Filtering:
A Stein’s Unbiased Risk Estimator Approach

Zahra Esmaeilbeig and Mojtaba Soltanalian  Zahra Esmaeilbeig†,1, and Mojtaba
Soltanalian†,2 Email: {1zesmae2<EMAIL_ADDRESS>† Department of Electrical
and Computer Engineering
University of Illinois at Chicago, Chicago, Illinois, USA

###### Abstract

This paper revisits two prominent adaptive filtering algorithms through the
lens of algorithm unrolling, namely recursive least squares (RLS) and
equivariant adaptive source separation (EASI), in the context of source
estimation and separation. Building upon the unrolling methodology, we
introduce novel task-based deep learning frameworks, denoted as Deep RLS and
Deep EASI. These architectures transform the iterations of the original
algorithms into layers of a deep neural network, thereby enabling efficient
source signal estimation by taking advantage of a training process. To further
enhance performance, we propose training these deep unrolled networks
utilizing a loss function grounded on a Stein’s unbiased risk estimator
(SURE). Our empirical evaluations demonstrate the efficacy of this SURE-based
approach for enhanced source signal estimation.

###### Index Terms:

Adaptive filtering, Stein’s unbiased risk estimator, deep unfolding, principal
component analysis.

##  I Introduction

Deep unfolding, or unrolling [1], enables constructing interpretable deep
neural networks (DNN) that require less training data and considerably less
computational resources than generic DNNs. Specifically, in deep unfolding,
each layer of the DNN is designed to resemble one iteration of the original
algorithm of interest. Passing the signals through such a deep network is in
essence similar to executing the iterative algorithm a finite number of times,
determined by the number of layers. In addition, the algorithm parameters such
as the model parameters and forgetting parameter in adaptive filtering will be
reflected in the parameters and weights of the constructed DNN. The deep
unrolling technique has been effectively applied to various signal processing
problems, yielding significant improvements in the convergence rates of state-
of-the-art iterative algorithms; see [2, 1] for a detailed explanation of deep
unrolling, as well as [3, 4, 5] for examples of deploying deep unrolling in
different application areas.

Our goal in this paper is to develop a set of algorithms able to learn the
nonlinearity and step sizes of two classical adaptive filtering algorithms,
namely, recursive least squares (RLS) and equivariant adaptive source
separation (EASI). We leverage the Stein’s unbiased risk estimator (SURE) in
training, which serves as a surrogate for mean squared error (MSE), even when
the ground truth is unknown [6]. Studies such as [7, 8] have reported improved
image denoising results when networks were trained with SURE loss,
outperforming traditional MSE loss training. Similarly, SURE has been
effectively used to train deep convolutional neural networks without requiring
denoised ground truth X-ray data, as highlighted in [9]. The SURE based
training and the recurrent training procedure of our proposed methodology
makes it a great candidate for unsupervised real-time signal processing.

The rest of the paper is organized as follows. In the next section, we
introduce the problem formulation for adaptive filtering-based signal
estimation. In Section III, we propose the two deep unrolling frameworks Deep
EASI and Deep RLS for adaptive filtering, alongside the SURE-based surrogate
loss function employed for their training. Section IV details the numerical
experiments used to evaluate our proposed methods, and Section VII presents
our concluding remarks.

_Notation:_ Throughout this paper, we use bold lowercase and bold uppercase
letters for vectors and matrices, respectively. $\mathbb{R}$ represents the
set of real numbers. $(\cdot)^{\top}$ denotes the vector/matrix transpose. The
identity matrix of is denoted by $\mathbf{I}$ and the trace of a matrix is
denoted by $\operatorname{Tr}(.)$.

##  II Problem formulation

We begin by the long-standing linear inference problem formulation in which
$m$ statistically independent signals are linearly mixed to yield $l$ possibly
noisy combinations,

$\mathbf{x}(t)=\mathbf{A}\mathbf{s}(t)+\mathbf{n}(t).$ (1)

Let $\mathbf{x}(t)=[\mathbf{x}_{1}(t),\ldots,\mathbf{x}_{l}(t)]^{\top}$ denote
the $l-$dimensional data vector made up of the mixture at time $t$ that is
exposed to an additive measurement noise $\mathbf{n}(t)$. Given no knowledge
of the mixing matrix $\mathbf{A}\in\mathds{R}^{m\times l}$, the goal is to
recover the original source signal vector
$\mathbf{s}(t)=[\mathbf{s}_{1}(t),\ldots,\mathbf{s}_{m}(t)]^{\top}$ from the
mixture. This problem is referred to as blind source separation (BSS) in the
literature. A seminal work in this context is [10] which suggests tuning and
updating a separating matrix $\mathbf{W}\in\mathds{R}^{l\times m}$ until the
output

$\mathbf{y}(t)=\mathbf{W}^{\top}\mathbf{x}(t),$ (2)

where $\mathbf{y}(t)=[\mathbf{y}_{1}(t),\ldots,\mathbf{y}_{m}(t)]^{\top}$, is
as close as possible to the source signal vector of interest $\mathbf{s}(t)$.

###  II-A Nonlinear Recursive Least Squares for Blind Source Separation

Assuming there exists a larger number of sensors than the source signals, i.e.
$l\geq m$, we can draw an analogy between the BSS problem and the task of
principal component analysis (PCA). In a sense, we are aiming to represent the
random vector $\mathbf{x}(t)$ in a lower dimensional orthonormal subspace,
represented by the columns of $\mathbf{W}$, as the orthonormal basis vectors.
By this analogy, both BSS and PCA problems can be reduced to minimizing an
objective function of the from:

$\mathcal{L}(\mathbf{W})=\mathbb{E}\left\\{\|\mathbf{x}(t)-\mathbf{W}(\mathbf{W}^{\top}\mathbf{x}(t))\|_{2}^{2}\right\\}.$
(3)

Assuming that $\mathbf{x}(t)$ is a zero-mean vector, it can be shown that the
solution to the above optimization problem is a matrix $\mathbf{W}$ whose
columns are the $m$ dominant eigenvectors of the data covariance matrix
$\mathbf{C_{x}(t)}=\mathbb{E}\left\\{\mathbf{x}(t)\mathbf{x}(t)^{\top}\right\\}$
[11]. Therefore, the principal components or the recovered source signals are
mutually uncorrelated. As discussed in [10], having uncorrelated data is not a
sufficient condition to achieve separation. In other words, the solutions to
PCA and BSS do not coincide unless we address the higher order statistics of
the output signal $\mathbf{y}(t)$. By introducing nonlinearity into (3), we
will implicitly target higher order statistics of the signal [11]. This
_nonlinear PCA_ , which is an extension of the conventional PCA, is made
possible by considering the signal recovery objective:

$\mathcal{L}(\mathbf{W})=\mathbb{E}\left\\{\|\mathbf{x}(t)-\mathbf{W}\mathbf{g}(\mathbf{W}^{\top}\mathbf{x}(t))\\}\|_{2}^{2}\right\\},$
(4)

where $\mathbf{g}(\cdot)$ denotes an odd non-linear function applied element-
wise on the vector argument. The proof of the connection between (4) and
higher order statistics of the source signals $\mathbf{s}(t)$ is discussed in
[12]. While PCA is a fairly standardized technique, nonlinear or robust PCA
formulations based on (4) tend to be multi-modal with several local optima—so
they can be run from various initial points and possibly lead to different
“solutions” [13]. In [14], a recursive least squares algorithm for subspace
estimation is proposed, which is further extended to the nonlinear PCA in [15]
for solving the BSS problem. The algorithm in [15] is useful as a baseline for
developing our deep unfolded framework for nonlinear PCA.

We consider a real-time and adaptive scenario in which upon arrival of new
data $\mathbf{x}(t)$, the subspace of signal at time instant $t$ is
recursively updated from the subspace at time $t-1$ and the new sample
$\mathbf{x}(t)$ [14]. The separating matrix $\mathbf{W}$ introduced in (4) is
therefore replaced by $\mathbf{W}(t)$ and updated at each time instant $t$.
The adaptive algorithm chosen for this task is the well-known recursive least
squares (RLS) [16]. In the linear case, by replacing the expectation in (3)
with a weighted sum, we can attenuate the impact of the older samples, which
is reasonable, for instance whenever one deals with a time-varying
environment. In this way, one can make sure the distant past will be forgotten
and the resulting algorithm for minimizing (3) can effectively track the
statistical variations of the observed data. By replacing
$\mathbf{y}(t)=\mathbf{W}(t)^{\top}\mathbf{x}(t)$ and using an exponential
weighting (governed by a forgetting factor), the loss function in (3) boils
down to:

$\mathcal{L}(\mathbf{W})=\sum_{i=1}^{t}\beta^{t-i}\|\mathbf{x}(i)-\mathbf{W}(t)\mathbf{y}(i)\|^{2},$
(5)

with the forgetting factor $\beta$ satisfying $0\ll\beta\leq 1$. Note that
$\beta=1$ yields the ordinary method of least squares in which all samples are
weighed equally while choosing relatively small $\beta$ makes our estimation
rather instantaneous, thus neglecting the past. Therefore, $\beta$ is usually
chosen to be less than one, but also rather close to one for smooth tracking
and filtering.

We can write the gradient of the loss function in (5) in its compact form as

$\nabla_{\mathbf{W}(t)}\mathcal{L}(\mathbf{W})=-2\mathbf{C_{xy}}(t)+2\mathbf{C_{y}}(t)\mathbf{W}(t),$
(6)

where $\mathbf{C_{y}}(t)$ and $\mathbf{C_{xy}}(t)$ are the auto-correlation
matrix of $\mathbf{y}(t)$,

$\mathbf{C_{y}}(t)=\sum_{i=1}^{t}\beta^{t-i}\mathbf{y}(i)\mathbf{y}(i)^{\top}=\beta\mathbf{C_{y}}(t-1)+\mathbf{y}(t)\mathbf{y}(t)^{\top},$
(7)

and the cross-correlation matrix of $\mathbf{x}(t)$ and $\mathbf{y}(t)$,

$\mathbf{C_{xy}}(t)=\sum_{i=1}^{t}\beta^{t-i}\mathbf{x}(i)\mathbf{y}(i)^{\top}=\beta\mathbf{C_{xy}}(t-1)+\mathbf{x}(t)\mathbf{y}(t)^{\top},$
(8)

at the time instance $t$, respectively. Setting the gradient (6) to zero will
result in the close-form separating matrix

$\mathbf{W}(t)=\mathbf{C_{y}}^{-1}(t)\mathbf{C_{xy}}(t).$ (9)

A recursive computation of $\mathbf{W}(t)$ can be achieved using the RLS
algorithm [17]. In RLS, the matrix inversion lemma enables a recursive
computation of $\mathbf{G}(t)=\mathbf{C_{y}}^{-1}(t)$; see the derivations in
Appendix. At each iteration of the RLS algorithm, $\mathbf{P}(t)$ is computed
recursively as

$\mathbf{G}(t)=\beta^{-1}\mathbf{G}(t-1)-\frac{\beta^{-2}\mathbf{G}(t-1)\mathbf{y}(t)\mathbf{y}(t)^{\top}\mathbf{G}(t-1)}{1+\beta^{-1}\mathbf{y}(t)^{\top}\mathbf{G}(t-1)\mathbf{y}(t)}.$
(10)

Consequently, the RLS algorithm provides the estimate $\mathbf{y}(t)$ of the
source signals. The steps of the RLS algorithm are summarized in Algorithm 1.
It appears that extending the application of RLS to the nonlinear PCA loss
function in (4) is rather straightforward. To accomplish this task, solely
step 3 of Algorithm 1 should be modified to
$\mathbf{y}(t)=g(\mathbf{W}^{\top}(t-1)\mathbf{x}(t))$ in order to meet the
nonlinear PCA criterion [14].

Algorithm 1 RLS Algorithm for Performing PCA

1:Initialize $\mathbf{W}(0)$ and $\mathbf{G}(0)$

2:for $t=0,1,\ldots,T$ do

3: $\mathbf{y}(t)=\mathbf{W}^{\top}(t-1)\mathbf{x}(t)$

4: $\mathbf{h}(t)=\mathbf{G}(t-1)\mathbf{y}(t)$

5:
$\mathbf{f}(t)=\frac{\mathbf{h}(t)}{\beta+\mathbf{y}(t)^{\top}\mathbf{h}(t)}$

6:
$\mathbf{G}(t)=\beta^{-1}[\mathbf{G}(t-1)-\mathbf{f}(t)\mathbf{h}(t)^{\top}]$

7: $\mathbf{e}(t)=\mathbf{x}(t)-\mathbf{W}(t-1)\mathbf{y}(t)$

8: $\mathbf{W}(t)=\mathbf{W}(t-1)+\mathbf{e}(t)\mathbf{f}(t)^{\top}$

In order for the RLS algorithm to optimize the nonlinear PCA loss function and
converge to a separating matrix the choice of nonlinearity g(.) matters. We
refer to the analytical study presented in [13] in which some conditions
beyond the oddity and differentiability of the function g(.) must be
satisfied. For instance, $g(s)=s^{3}$ leads to an asymptotically stable
separation only if the source signals are positively kurtotic or super-
Gaussian. Whereas if we choose a sigmoidal nonlinearity $g(s)=tanh(\beta s)$
with $\beta>0$, then a sub-Gaussian density is required for the source signals
to be separated using RLS algorithm.

In section III-A, we _unroll_ the iterations of the modified Algorithm 1, for
nonlinear PCA onto the layers of a deep neural network where each layer
resembles one iteration of the RLS algorithm.

###  II-B Equivariant Adaptive Source Separation (EASI)

In [10], the EASI algorithm is developed by recurrent updates of the
separating matrix as

$\mathbf{W}(t+1)=\mathbf{W}(t)-\lambda_{t}\mathbf{H}(\mathbf{y}(t))\mathbf{W}(t).$
(11)

Where $\lambda_{t}$ is a sequence of positive step sizes and $\mathbf{H}(.)$
is a matrix valued function used to update the separating matrix. In [10] this
function is calculated as the relative gradient with respect to the objective
function for blind source separation. The cross-cumulants of the source
signals in $\mathbf{y}(t)$ is proposed as the objective function to be
minimized as a measure of independence. $\mathbf{H}(.)$ is derived in [10] as

$\mathbf{H}(\mathbf{y}(t))=\mathbf{y}(t)\mathbf{y}(t)^{\top}-\mathbf{I}+g(\mathbf{y}(t))\mathbf{y}(t)^{\top}-\mathbf{y}(t)g(\mathbf{y}(t))^{\top}$
(12)

where n arbitrary nonlinear functions, $g_{1}(.),g_{2}(.),\ldots,g_{n}(.)$ are
used to define

$g(\mathbf{y}(t))=[g_{1}(\mathbf{y}_{1}(t)),\ldots,g_{l}(\mathbf{y}_{l}(t))]^{\top}.$
(13)

The choice of this nonlinear function is crucial to the performance of the
algorithm and is dependent on the distribution of sources. For instance, for
sources with identical distibutions $g_{i}(.)=g(.)$ will be sufficient to
perform seperation. In [10], it is illustrated that a cubic nonlinearity
$g(s)=s^{3}$ leads to stability of separation in EASI algorithm only under the
constraint that sum of kurtosis of any two source signals $s_{i}$ and $s_{j}$,
$1\leq i,j\leq m$ are negative. $g(s)=tanh(s)$ is reported in [15] to work
satisfactorily for two sub-Gaussian sources using $\lambda_{t}>0$. The
nonlinear PCA algorithm require that the original source signals have a
kurtosis with the same sign. Although this condition is somehow relaxed in the
EASI algorithm so that the sum of kurtosises for any pair of two sources must
be negative, still some knowledge on the probability distribution of source
signals is required to choose the nonlinearity.

##  III The Proposed Framework

The estimation performance of the algorithms discussed above depends on a
number of factors such as condition of mixing matrix $\mathbf{A}$, source
signals, the step size parameter(s) and nonlinearity $g(.)$. We propose to
overparameterize the algorithms so that we can determine the optimal stepsize
and proper nonlinearities as apposed to using fixed parameters. In this
section, we present the proposed deep architectures Deep RLS in III-A and Deep
EASI in III-B. The training procedure for these two architectures and the SURE
based loss function will be introduced in III-C and III-D, respectively.

###  III-A Deep RLS

As shown in [15], when applied to a linear mixture of source signals (i.e.,
the BSS problem), the RLS algorithm usually approximates the true source
signals well and successfully separates them. However, the number of
iterations needed to converge may vary greatly depending on the initial values
$\mathbf{W}(0),\mathbf{G}(0)$ and the forgetting parameter $\beta$. We
introduce Deep RLS, our deep unrolling-based framework which is designed based
on the modified iterations of the algorithm 1. More precisely, the dynamics of
the $k$-th layer of Deep RLS are given as:

$\displaystyle\mathbf{y}(k)$
$\displaystyle=\mathbf{g}_{{}_{\theta_{k}}}(\mathbf{W}^{\top}(k-1)\mathbf{x}(k)),$
(14) $\displaystyle\mathbf{h}(k)$
$\displaystyle=\mathbf{G}(k-1)\mathbf{y}(k),$ (15)
$\displaystyle\mathbf{f}(k)$
$\displaystyle=\frac{\mathbf{h}(k)}{\mathbf{\omega}_{k}+\mathbf{y}(k)^{\top}\mathbf{h}(k)},$
(16) $\displaystyle\mathbf{G}(k)$
$\displaystyle=\omega_{k}^{-1}[\mathbf{G}(k-1)-\mathbf{f}(k)\mathbf{h}(k)^{\top}],$
(17) $\displaystyle\mathbf{e}(k)$
$\displaystyle=\mathbf{x}(k)-\mathbf{W}(k-1)\mathbf{y}(k),$ (18)
$\displaystyle\mathbf{W}(k)$
$\displaystyle=\mathbf{W}(k-1)+\mathbf{e}(k)\mathbf{f}(k)^{\top},$ (19)

where $\mathbf{x}(k)$ is the data vector at time instance $k$. The
nonlinearity $\mathbf{g}(\cdot)$ in the original RLS algorithm, which was
chosen accroding to the distribution of the source signals, is
overparameterized to $\mathbf{g}_{{}_{\theta_{k}}}(\cdot)$. Considering that
neural networks with at least one hidden layer are universal approximators and
they can be trained to approximate any mapping, we use a set of fully
connected layers as $\mathbf{g}_{{}_{\theta_{k}}}(\cdot)$. Weights and biases
of these layers are represented by the learnable parameter $\theta_{k}$ and
$\omega_{k}\in\mathds{R}$ represents the trainable forgetting parameter. Given
$T$ samples of the data vector $\mathbf{x}(t)$, our goal is to optimize the
parameters $\Gamma$ of the network, where

$\Gamma=\\{\theta_{k},\mathbf{\omega}_{k}\\}_{k=1}^{T}.$ (20)

The output of the $k$-th layer, i.e. $\mathbf{y}(k)$, in (14) is an
approximation of the source signals at the time instance $k$.

###  III-B Deep EASI

We consider the EASI iterations defined in (11) as our baseline to reconstruct
the unfolded network. We over parameterize the iterations by introducing a
learnable step-size $\lambda_{t}$ and $\mathbf{H}_{\phi_{t}}$ for each layer
$t$ as

$\mathbf{W}(t+1)=\mathbf{W}(t)-\lambda_{t}\mathbf{H}_{\phi_{t}}(\mathbf{y}(t))\mathbf{W}(t)$
(21)

and

$\mathbf{H}_{\phi_{t}}(\mathbf{y}(t))=\mathbf{y}(t)\mathbf{y}(t)^{\top}-\mathbf{I}+g_{\phi_{t}}(\mathbf{y}(t))\mathbf{y}(t)^{\top}-\mathbf{y}(t)g_{\phi_{t}}(\mathbf{y}(t))^{\top}$
(22)

where $g_{\phi_{t}}(.)$ is realized using a few layers of fully connected
layers, with weights $\phi_{t}$, deployed to approximate the best nonlinearity
for separation. The trainable parameters of the network will be

$\Xi=\\{\phi_{t},\lambda_{t}\\}_{t=1}^{T}$ (23)

The output of the $t$-th layer, i.e. $\mathbf{y}(t)$ is

$\mathbf{y}(t)=\mathbf{W}(t)^{\top}\mathbf{x}(t),$ (24)

###  III-C Training Procedure

An earlier version of this work proposed in [18] and was successful in
recovering the source signals. However, it could only use a few number of
inputs $\mathbf{x}(t)$ because deeper networks with huge number of parameters
were not feasible to be trained. Parameter sharing is a technique in deep
learning which regularizes the network to avoid this problem. Parameter
sharing makes it possible to extend and apply the model to signals of
different lengths and generalize across them. In _Deep RLS_ architecture
proposed in [18], we designed a multi-layer feedforward neural network in
which we had separate learnable parameters for each time index and we could
not generalize to sequence lengths not seen during training. Recurrent Neural
Networks (RNN) are introduced to overcome this limitation. Inspired by the
architecture of these neural networks and back-propagation through time (BPTT)
as their training process, we propose the following loss function for training
the proposed unrolled algortihms. An RNN maps an input sequence to an output
sequence of the same length. The total loss for a given sequence of
$\mathbf{x}(t)$ values paired with a sequence of $\mathbf{y}(t)$ values is the
sum of the losses over all the time steps. For example, if $l(t)$ is the mean
squared error (MSE) of reconstructing $\mathbf{s}(t)$ given $\mathbf{y}(t)$
then

$\mathcal{L}(\mathbf{s},\mathbf{y})=\sum_{t=1}^{T}l{(t)}=\sum_{t=1}^{T}\|\mathbf{s}(t)-\mathbf{y}(t)\|^{2}_{2}$
(25)

where $\mathbf{y}=[\mathbf{y}(1),\ldots,\mathbf{y}(T)]$ and
$\mathbf{s}=[\mathbf{s}(1),\ldots,\mathbf{s}(T)]$. In order to apply BPTT, the
gradient of the loss function $l(t)$ with respect to the trainable parameters
is required. This is challenging to do by hand, but made easy by the auto-
differentiation capabilities is PyTorch [19], which is used throughout our
experiments in section IV.

While training Deep RLS, one needs to consider the constraint that the
forgetting parameter must satisfy $0<\beta\leq 1$. Hence, in order to impose
such a constraint, one can regularize the loss function ensuring that the
network chooses proper weights $\\{\omega_{k}\\}_{k=1}^{T}$ corresponding to a
feasible forgetting parameter at each layer. Accordingly, we define the loss
function used for training the proposed architecture as

$\begin{split}\mathcal{L}(\mathbf{s},\mathbf{y},\Gamma)&=\sum_{t=1}^{T}\|\mathbf{s}(t)-\mathbf{y}(t)\|^{2}_{2}+\\\
&\underbrace{\lambda\sum_{t=1}^{T}\mathrm{ReLU}(-\mathbf{\omega}_{t})+\lambda\sum_{t=1}^{T}\mathrm{ReLU}(\mathbf{\omega}_{t}-1)}_{\text{regularization
term for the forgetting parameter}},\end{split}$ (26)

where $\mathrm{ReLU}(\cdot)$ is the well-known Rectifier Linear Unit function
extensively used in the deep learning literature. For training the Deep RLS
(or Deep EASI) network we employed the training process in Algorithm 2.

Algorithm 2 Training Procedure for Deep RLS(or Deep EASI).

1:Initialize $\mathbf{W}(0)$ and $\mathbf{\mathbf{G}}(0)$

2:for $\textrm{epoch}=1,\ldots,N$ do

3: for $t=1,\ldots,T$ do

4: Feed $\mathbf{x}(t)$ to the network

5: Apply the recursion in (14)-(19) (or (21))

6: Compute the loss function in (26) (or (25))

7: Use BPTT to update $\Gamma$ (or $\Xi$)

###  III-D Stein’s Unbiased Risk Estimator (SURE)

SURE is a model selection technique that was first proposed by Charles Stein
in [20]. SURE provides an unbiased estimate of the MSE of an estimator of the
mean of a Gaussian distributed random vector, with unknown mean. A
generalization of this technique known as generalized SURE was proposed in
[21] to estimate the MSE associated with estimates of $\mathbf{s}$ from a
linear measurement $\mathbf{x}=\mathbf{A}\mathbf{s}+\mathbf{n}$, where
$\mathbf{A}\neq\mathbf{I}$, and $\mathbf{n}$ has known covariance and follows
any distribution from the exponential family. For the estimators
$f_{\theta}(.)$ parameterized over $\theta$ which receive the noisy
observation $\mathbf{x}$ and provides an estimate of sources $\mathbf{s}$, in
the special case of i.i.d. Gaussian distributed noise, the estimate simplifies
to

$\begin{split}\mathbb{E}_{n}\\{\|\mathbf{P}\mathbf{s}-\mathbf{P}f_{\theta}(\mathbf{x})\|_{2}^{2}\\}=\mathbb{E}_{n}\\{\|\mathbf{P}\mathbf{s}\|_{2}^{2}+\|\mathbf{P}f_{\theta}(\mathbf{x})\|_{2}^{2}+\\\
2\sigma^{2}_{n}div_{x}(f_{\theta}(\mathbf{x}))-2f_{\theta}(\mathbf{x})^{\top}\mathbf{A}^{\dagger}\mathbf{x}\\},\end{split}$
(27)

where the orthonormal projection onto the range space of $\mathbf{A}$ is
represented by
$\mathbf{P}=\mathbf{A}(\mathbf{A}^{\top}\mathbf{A})^{-1}\mathbf{A}^{\top}$ and
$\mathbf{A}^{\dagger}$ is the pseudoinverse of $\mathbf{A}$. $\sigma^{2}_{n}$
is the variance of i.i.d Gaussian distributed measurement noise
$\mathbf{n}(t)$ with zero mean. The term $div(.)$ stands for divergence and is
defined as

$div_{x}(f_{\theta}(\mathbf{x}))=\sum_{i=1}^{l}\frac{\partial
f_{\theta}(\mathbf{x})}{\partial\mathbf{x}_{i}}.$ (28)

The last three terms in (27) are dependant on the parameters of the estimator
$f_{\theta}(.)$. Considering the Deep EASI as an estimator of the source
signals, we propose to optimize the network’s parameters $\Xi$ by
incorporating the loss at time $t$ as

$l(t)=\|\mathbf{P}f_{\Xi}(\mathbf{x}(t))\|^{2}+\\\
2\sigma^{2}_{n}div_{x}(f_{\Xi}(\mathbf{x}(t)))-2f_{\Xi}(\mathbf{x}(t))^{\top}\mathbf{A}^{\dagger}\mathbf{x}(t).$
(29)

In this equation, the Deep EASI network as an estimator for source signal at
time instance $t$ is denoted by $f_{\Xi}(\mathbf{x}(t))$. By Substituting (29)
in (25), the SURE loss function for training the Deep EASI network is
analytically derived. The divergence of $div_{x}(f_{\Xi}(\mathbf{x}(t)))$ can
be calculated as

$div_{x}(f_{\Xi}(\mathbf{x}(t)))=div_{x}(\mathbf{y}(t))=div_{x}(\mathbf{W}(t)^{\top}\mathbf{x}(t))=\operatorname{Tr}(\mathbf{W}(t)),$
(30)

in which the second and third equality comes from (24) and (28), respectively.
It is worth mentioning that as discussed in [22], the SURE loss function can
not be analytically derived for all estimators. We leave derivation of this
loss for deep RLS for future extension of this study. While training Deep EASI
and Deep RLS, we synthetically produce the observations $x(t)$ for
$t=1,\ldots,T$ to use as the training set. Therefore, we have access to the
sources, the mixing matrix used and the variance of noise. The blindness of
the method refers to the test in which we only observe the mixtures. In our
numerical experiments, we will deploy the SURE loss function in training the
Deep EASI network and illustrate the improvement in test loss over the
initially proposed loss function in (25). Evaluating the SURE loss in (29)
does not require the ground truth $\mathbf{s}(t)$ and therefore the learning
procedure will be unsupervised.

##  IV Numerical Study

In this section, we demonstrate the performance of the proposed Deep RLS and
Deep EASI algorithms. The proposed framework was implemented using the PyTorch
library [19] and the Adam stochastic optimizer [23] with a constant learning
rate of $10^{-4}$ for training purposes. The training was performed based on
the data generated via the following model. For each time interval
$t=0,1,...,T$, elements of the vector $\mathbf{s}(t)$ is generated from a sub-
Gaussian distribution. For data generation purposes, we have assumed the
source signals to be i.i.d. and uniformly distributed, i.e.,
$\mathbf{s}(t)\sim\mathcal{U}(0,\boldsymbol{1})$. The mixing matrix
$\mathbf{A}$ is assumed to be generated according to
$\mathbf{A}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$. For each sample data, a
new mixing matrix $\mathbf{A}$ is generated i.e. there is not any two samples
in the training and test sets that have the same mixing matrix.

We performed the training of the proposed Deep RLS and Deep EASI networks
using the batch learning process with a batch size of 40 and trained the
network for $N=100$ epochs. A training set of size $10^{3}$ and test set of
size $10^{2}$ was chosen. In this section we study performance of our proposed
source separation algorithms in test simulations where the mixing matrix and
source signals and noise variance are known. Therefore, the network will be
trained in a supervised manner and also the mixing matrix and variance of the
samples in the training set are used to train regularized network with SURE
loss function in section III-D.

The quantitative measure to evaluate the performance of the networks is the
average of the mean-square-error (MSE) defined as
$\mathrm{MSE}=(1/T)\sum_{t=1}^{T}\|\mathbf{\mathbf{s}}(t)-\mathbf{\mathbf{y}}(t)\|^{2}_{2}$.

In Fig. 1, we demonstrate the performance of the proposed Deep RLS algorithm,
Deep EASI algorithm and the base-line RLS [15] and EASI [10] algorithms (where
no parameter is learned) in terms of $\mathrm{MSE}$ versus the number of time
samples $T$. Observing Fig. 1, one can deduce that owing to its hybrid nature,
the proposed Deep EASI methodology significantly outperforms its counterparts
in terms of average MSE and converges with far less iterations. In particular,
we can observe that Deep EASI and Deep RLS achieve a very low average MSE with
as few as $50$ iterations, while the EASI and RLS algorithms require at least
$100$ and $250$ iterations to converge, respectively. Accordingly, this
results demonstrate the effectiveness of the learned parameters.

Fig. 2 illustrates the $\mathrm{MSE}$ for the Deep EASI network, which is
trained using the two different loss functions. The efficacy of SURE-based
approach in comparison with MSE loss is evident.

Figure 1: The average MSE of recovering $m=3$ source signals from $l=3$
observations using the Deep-RLS network, RLS [15] with $\beta=0.99$, EASI [10]
and Deep-EASI vs. the number of layers/iterations $T$, when trained by MSE
loss for $N=100$ epochs with a learning rate of $10^{-4}$. Figure 2: The
performance of Deep EASI trained with MSE in (25) in comparison with SURE loss
function in (29) .

##  V Conclusion

In this paper, we introduced two deep unrolling-based frameworks for adaptive
filtering and demonstrated that the unrolled networks, trained as recursive
neural networks, outperform their baseline counterparts. Moreover, we
incorporated the Stein’s unbiased risk estimator as a surrogate loss function
for training the deep architectures which introduced further improvement in
estimating the source signals.

##  VI Appendix: The RLS Recursive Formula

Let $\mathbf{A}$, $\mathbf{B}$, and $\mathbf{D}$ be positive definite matrices
such that $\mathbf{A}=\mathbf{B}^{-1}+\mathbf{cD}^{-1}\mathbf{c}^{\top}.$
Using the matrix inversion lemma, the inverse of $\mathbf{A}$ can be expressed
as

$\mathbf{A}^{-1}=\mathbf{B}-\mathbf{Bc}(\mathbf{D}+\mathbf{c}^{T}\mathbf{Bc})^{-1}\mathbf{c}^{T}\mathbf{B}.$
(31)

Now, assuming that the auto-correlation matrix $\mathbf{C_{y}}(t)$ is positive
definite (and thus non-singular), by choosing $\mathbf{A=C_{y}}(t)$,
$\mathbf{B}^{-1}=\beta\mathbf{C_{y}}(t-1)$,
$\mathbf{c}=\mathbf{y}(t),\mathbf{D}^{-1}=\mathbf{I}$, one can compute
$\mathbf{G}(t)=\mathbf{C_{y}}^{-1}(t)$ as proposed in (10).

##  VII Acknowledgement

The authors would like to express gratitude to Dr. Shahin Khobahi for his help
with developing the ideas in a preliminary version of this manuscript,
currently available on arXiv [18].

## References

  * [1] J. R. Hershey, J. L. Roux, and F. Weninger, “Deep unfolding: Model-based inspiration of novel deep architectures,” _arXiv preprint arXiv:1409.2574_ , 2014.
  * [2] V. Monga, Y. Li, and Y. C. Eldar, “Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing,” _arXiv preprint arXiv:1912.10557_ , 2019.
  * [3] N. Shlezinger, Y. C. Eldar, and S. P. Boyd, “Model-based deep learning: On the intersection of deep learning and optimization,” _IEEE Access_ , vol. 10, pp. 115 384–115 398, 2022.
  * [4] Y. Zeng, S. Khobahi, and M. Soltanalian, “One-bit compressive sensing: Can we go deep and blind?” _IEEE Signal Processing Letters_ , vol. 29, pp. 1629–1633, 2022.
  * [5] S. Khobahi, N. Shlezinger, M. Soltanalian, and Y. C. Eldar, “LoRD-Net: Unfolded deep detection network with low-resolution receivers,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 5651–5664, 2021.
  * [6] V. Edupuganti, M. Mardani, S. Vasanawala, and J. Pauly, “Uncertainty quantification in deep MRI reconstruction,” _IEEE Transactions on Medical Imaging_ , vol. 40, no. 1, pp. 239–250, 2021.
  * [7] C. A. Metzler, A. Mousavi, R. Heckel, and R. G. Baraniuk, “Unsupervised learning with Stein’s unbiased risk estimator,” _arXiv preprint arXiv:1805.10531_ , 2018.
  * [8] M. Mardani, Q. Sun, V. Papyan, S. Vasanawala, J. Pauly, and D. Donoho, “Degrees of freedom analysis of unrolled neural networks,” _arXiv preprint arXiv:1906.03742_ , 2019.
  * [9] F. Shamshad, M. Awais, M. Asim, M. Umair, A. Ahmed _et al._ , “Leveraging deep Stein’s unbiased risk estimator for unsupervised X-ray denoising,” _arXiv preprint arXiv:1811.12488_ , 2018.
  * [10] J.-F. Cardoso and B. H. Laheld, “Equivariant adaptive source separation,” _IEEE Transactions on signal processing_ , vol. 44, no. 12, pp. 3017–3030, 1996.
  * [11] J. M. T. Romano, R. Attux, C. C. Cavalcante, and R. Suyama, _Unsupervised signal processing: channel equalization and source separation_. CRC Press, 2018.
  * [12] P. Pajunen and J. Karhunen, “Least-squares methods for blind source separation based on nonlinear PCA,” _International Journal of Neural Systems_ , vol. 8, no. 05n06, pp. 601–612, 1997.
  * [13] J. Karhunen, E. Oja, L. Wang, R. Vigario, and J. Joutsensalo, “A class of neural networks for independent component analysis,” _IEEE Transactions on neural networks_ , vol. 8, no. 3, pp. 486–504, 1997.
  * [14] B. Yang, “Projection approximation subspace tracking,” _IEEE Transactions on Signal processing_ , vol. 43, no. 1, pp. 95–107, 1995.
  * [15] J. Karhunen and P. Pajunen, “Blind source separation using least-squares type adaptive algorithms,” in _IEEE International Conference on Acoustics, Speech, and Signal Processing_ , vol. 4, 1997, pp. 3361–3364.
  * [16] L. Peng, C. Kümmerle, and R. Vidal, “On the convergence of IRLS and its variants in outlier-robust estimation,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , June 2023, pp. 17 808–17 818.
  * [17] S. Haykin and S. Haykin, _Adaptive Filter Theory_. Pearson, 2014.
  * [18] Z. Esmaeilbeig, S. Khobahi, and M. Soltanalian, “Deep-RLS: A model-inspired deep learning approach to nonlinear PCA,” _arXiv e-prints_ , pp. arXiv–2011, 2020.
  * [19] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, “Pytorch: An imperative style, high-performance deep learning library.” Curran Associates, Inc., 2019, pp. 8024–8035.
  * [20] C. M. Stein, “Estimation of the mean of a multivariate normal distribution,” _The annals of Statistics_ , pp. 1135–1151, 1981.
  * [21] Y. C. Eldar, “Generalized sure for exponential families: Applications to regularization,” _IEEE Transactions on Signal Processing_ , vol. 57, no. 2, pp. 471–481, 2008.
  * [22] P. Nobel, E. Candès, and S. Boyd, “Tractable evaluation of Stein’s unbiased risk estimator with convex regularizers,” _arXiv preprint arXiv:2211.05947_ , 2022.
  * [23] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.


# Localization of the Kobayashi distance for any visibility domain

Amar Deep Sarkar  ADS: Indian Institute of Science Education and Research
Kolkata, India<EMAIL_ADDRESS>
###### Abstract.

In this article, we prove a localization result for the Kobayashi distance for
Kobayashi hyperbolic domains in the complex Euclidean space.

###### Key words and phrases:

Visibility, weak-visibility, Kobayashi distance, localization

The author is supported by the postdoctoral fellowship of Indian Institute of
Science Education and Research Kolkata.

In this article, we prove the following localization results for the Kobayashi
distance of any visibility domain. This generalizes [2, Theorem 1.1]. The idea
of the proof is similar to the proof of Theorem 1.1 in [2] along with a few
important new observations.

######  Theorem 0.1.

Suppose $\Omega\subset\mathbb{C}^{d}$ is a hyperbolic domain and $U$ an open
subset of $\mathbb{C}^{d}$ such that $U\cap\partial\Omega\neq\emptyset$ and
$U\cap\Omega$ is connected. Suppose $(U\cap\Omega,\mathsf{k}_{U\cap\Omega})$
has weak-visibility property for every pair of distinct points in
$U\cap\partial\Omega$. Then for every $W\subset\subset U$, there exists a
constant $C>0$ which depends only on $U,W$ such that for every $z,w\in
W\cap\Omega$,

$\mathsf{k}_{U\cap\Omega}(z,w)\leq\mathsf{k}_{\Omega}(z,w)+C.$

######  Theorem 0.2.

Suppose $\Omega\subset\mathbb{C}^{d}$ is a hyperbolic domain and $U$ an open
subset of $\mathbb{C}^{d}$ such that $U\cap\partial\Omega\neq\emptyset$ and
$U\cap\Omega$ is connected. Suppose $(\Omega,\mathsf{k}_{\Omega})$ has weak-
visibility property for every pair of distinct points in
$U\cap\partial\Omega$. Then for every $W\subset\subset U$, there exists a
constant $C>0$ which depends only on $U,W$ such that for every $z,w\in
W\cap\Omega$,

$\mathsf{k}_{U\cap\Omega}(z,w)\leq\mathsf{k}_{\Omega}(z,w)+C.$

In the above two theorems and throughout, we are assuming that cardinality of
$U\cap\partial\Omega$ is greater than 1; when the cardinality of
$U\cap\partial\Omega$ is 1, the localization results above follow trivially.
Suppose $\Omega,U$ and $W$ as in the above theorems. In this article, we also
assume that $\inf_{z\in W}\mathsf{k}_{\Omega}(z,U^{c})>0$. We shall see later
that this condition is a necessary condition for weak-visibility.

The following localization lemma, by L. H. Royden [7, Lemma 2], whose proof
can be found in [5, Lemma 4], used to prove localization of the Kobayshi
distance and to study the relation betwen local and global visibility and
Gromov hyperbolicity in [2] and [1] respectively.

Royden’s Localization Lemma. Suppose $\Omega\subset\mathbb{C}^{d}$ be a
Kobayashi hyperbolic domain and $U$ is an open subset of $\mathbb{C}^{d}$ such
that $U\cap\Omega\neq\emptyset$ and $U\cap\Omega$ is connected. Then for all
$z\in U\cap\Omega$ and $v\in\mathbb{C}^{d}$,

(0.1)
$\kappa_{\Omega}(z;v)\leq\kappa_{U\cap\Omega}(z;v)\leq\coth(\mathsf{k}_{\Omega}(z,U^{c}))\kappa_{\Omega}(z;v).$

Next, we prove a lemma which is used to prove the localization of the Kobayshi
distance for visibility domains stated above.

######  Lemma 0.3.

Suppose $\Omega\subset\mathbb{C}^{d}$ be a Kobayashi hyperbolic domain and $U$
is an open subset of $\mathbb{C}^{d}$ such that $U\cap\Omega\neq\emptyset$ and
connected. Then for every $W\subset\subset U$, there eixts $L>0$ such that for
all $z\in W\cap\Omega$ and $v\in\mathbb{C}^{d}$,

(0.2)
$\kappa_{U\cap\Omega}(z;v)\leq\left(1+Le^{-\mathsf{k}_{\Omega}(z,U^{c})}\right)\kappa_{\Omega}(z;v).$

###### Proof.

We first note the inequality,

(0.3) $\tanh(x)\geq 1-e^{-x}\,\,\forall\,\,x\geq 0.$

By assumption $(\Omega,\mathsf{k}_{\Omega})$, for every open set
$W\subset\subset U$ there exists $c>0$ such that for all $z\in W\cap\Omega$,
we have $\coth(\mathsf{k}_{\Omega}(z,U^{c}))\leq c$. By the Royden’s
Localization Lemma, for all $z\in U\cap\Omega$ and $v\in C^{d}$, we have

$\tanh(\mathsf{k}_{\Omega}(z,U^{c}))\kappa_{U\cap\Omega}(z;v)\leq\kappa_{\Omega}(z;v).$

This gives, after applying
$\kappa_{U\cap\Omega}(z;v)\leq\coth(\mathsf{k}_{\Omega}(z,U^{c}))\kappa_{\Omega}(z;v)\leq
c\kappa_{\Omega}(z;v)$ for every $z\in W\cap\Omega$ and (0.3), for all $z\in
W$

$\begin{split}\kappa_{U\cap\Omega}(z;v)&\leq(1-\tanh(\mathsf{k}_{\Omega}(z,U^{c})))\kappa_{U\cap\Omega}(z;v)+\kappa_{\Omega}(z;v)\\\
&\leq\left(1+c\left(1-\tanh(\mathsf{k}_{\Omega}(z,U^{c}))\right)\right)\kappa_{\Omega}(z;v)\\\
&\leq\left(1+ce^{-\mathsf{k}_{\Omega}(z,U^{c})}\right)\kappa_{\Omega}(z;v).\end{split}$

This proves the lemma. ∎

######  Proposition 0.4.

Suppose $\Omega\subset\mathbb{C}^{d}$ is a Kobayashi hyperbolic domain and $U$
an open subset of $\mathbb{C}^{d}$, and $U\cap\partial\Omega\neq\emptyset$.
Suppose $(\Omega,\mathsf{k}_{\Omega})$ has weak-visibility property for every
distinct pair $\\{p,q\\}$, $p,q\in U\cap\partial\Omega$. Then for any
$\xi_{2}\in\partial\Omega\setminus\overline{U}$ and $\xi_{1}\in
U\cap\partial\Omega$, the distinct pair $\\{\xi_{1},\xi_{2}\\}$ has weak-
visibility property with respect to $(\Omega,\mathsf{k}_{\Omega})$.

###### Proof.

If this is not true, then we get a sequence of $(1,\kappa)$-almost-geodesics
$\gamma_{n}:[0,a_{n}]\longrightarrow\Omega$ such that
$\gamma_{n}(0)\to\xi_{1}$ and $\gamma_{n}(a_{n})\to\xi_{2}$ and
$\sup_{t\in[0,a_{n}]}\delta_{\Omega}(\gamma_{n}(t))\to 0$ as $n\to\infty$.
Now, arguing as in the proof of [4, Theorem 1.9], we can show that there
exists a point $\xi^{\prime}\in U\cap\partial\Omega\setminus\\{\xi_{1}\\}$
such that the distinct pair $\\{\xi_{1},\xi^{\prime}\\}$ does not have weak-
visibility property with respect to $(\Omega,\mathsf{k}_{\Omega})$.
Consequently, we get a contradiction. Hence the result is true. ∎

######  Corollary 0.5.

Suppose $\Omega\subset\mathbb{C}^{d}$ is a Kobayashi hyperbolic domain and
$W\subset\subset U$ and $V$ are open subsets of $\mathbb{C}^{d}$, and
$U\cap\partial\Omega,V\cap\partial\Omega\neq\emptyset$,
$\overline{U}\cap\overline{V}=\emptyset$. Suppose
$(\Omega,\mathsf{k}_{\Omega})$ has weak-visibility property for every distinct
pair $\\{p,q\\}$, $p,q\in U\cap\partial\Omega$. Then there is a compact set
$K\subset\Omega$ such for every $z\in W\cap\Omega$ and $w\in V\cap\Omega$ and
$\gamma$ is a $(1,\kappa)$-almost-geodesic joining $z$ and $w$, $\gamma\cap
K\neq\emptyset$.

###### Proof.

Suppose that it does not hold. In this case we get two points $p\in
U\cap\partial\Omega$ and
$q\in\overline{V}\cap\partial\Omega\subset\partial\Omega\setminus\overline{U}$
such that the distinct pair $\\{p,q\\}$ does not have weak-visibility property
with respect to $(\Omega,\mathsf{k}_{\Omega})$. This is a contradiction to
Proposition 0.4. ∎

######  Lemma 0.6.

Suppose $\Omega\subset\mathbb{C}^{d}$ is a domain and $U$ open subsets of
$\mathbb{C}^{d}$ such that $U\cap\Omega$ is connected and
$U\cap\partial\Omega\neq\emptyset$. Suppose $(\Omega,\mathsf{k}_{\Omega})$ has
weak-visibility property for every pair of distinct points $\\{p,q\\}$,
$p,q\in U\cap\partial\Omega$. Then for every $W_{1}\subset\subset
W_{2}\subset\subset U$ and $o\in\Omega$ there exists $L>0$ such that for all
$z\in W_{1}\cap\Omega$

$\mathsf{k}_{\Omega}(z,o)\leq\mathsf{k}_{\Omega}(z,W_{2}^{c})+L.$

###### Proof.

To get a contradiction, suppose otherwise. Then there exist $o\in\Omega$ and a
sequence $z_{n}\in W_{1}\cap\Omega$ such that

$\mathsf{k}_{\Omega}(z_{n},o)>\mathsf{k}_{\Omega}(z_{n},W_{2}^{c})+n.$

This in turn implies, there exists a sequence $w_{n}\in U^{c}$ such that
$\mathsf{k}_{\Omega}(z_{n},w_{n})-1/n<\mathsf{k}_{\Omega}(z_{n},w_{n})$, hence
by the inequality above, we get

$\mathsf{k}_{\Omega}(z_{n},o)>\mathsf{k}_{\Omega}(z_{n},w_{n})-1/n+n.$

By triangle inequality,
$\mathsf{k}_{\Omega}(o,w_{n})\geq\mathsf{k}_{\Omega}(z_{n},o)-\mathsf{k}_{\Omega}(z_{n},w_{n})>-1/n+n$,
and this implies

$\lim_{n\to\infty}\mathsf{k}_{\Omega}(o,w_{n})\to\infty.$

Since $W_{2}^{c}\cap\overline{W}_{1}=\emptyset$, there exist opens
neighbourhoods $V_{1}$ and $V_{2}$ in $\Omega$ of $W_{2}^{c}$ and
$\overline{W}_{2}$ respectively such that
$\overline{V}_{2}\cap\overline{V}_{2}=\emptyset$. Since $z_{n}\in W_{1}$ and
$w_{n}\in W_{2}^{c}$, by weak-visibility property, there eixsts a compact
subset $K$ of $\Omega$ such that $\gamma_{n}\cap K\neq\emptyset$, where
$\gamma_{n}$ is a $(1,\kappa)$-almost-geodesic joining $w_{n}$ and $z_{n}$,
for all $n\in\mathbb{Z}_{+}$ and for some $\kappa>0$. Suppose
$o_{n}\in\gamma_{n}\cap K$, then

$\mathsf{k}_{\Omega}(z_{n},w_{n})\geq\mathsf{k}_{\Omega}(z_{n},o_{n})+\mathsf{k}_{\Omega}(o_{n},w_{n})-3\kappa.$

Since, can be seen easily, $\mathsf{k}_{\Omega}(o_{n},w_{n})\to\infty$, for
any $w_{0}\in W_{2}^{c}$, there exits $n_{0}\in\mathbb{Z}_{+}$ such that
$\mathsf{k}_{\Omega}(o_{n},w_{n})\geq\mathsf{k}_{\Omega}(o_{n},w_{0})+1+3\kappa$,
for all $n\geq n_{0}$; by passing to a tail of the sequence we may assume for
all $n\in\mathbb{Z}_{+}$. Hence for all $n\in\mathbb{Z}_{+}$, we have

(0.4)
$\begin{split}\mathsf{k}_{\Omega}(z_{n},W_{2}^{c})&>\mathsf{k}_{\Omega}(z_{n},w_{n})-1/n\\\
&\geq\mathsf{k}_{\Omega}(z_{n},o_{n})+\mathsf{k}_{\Omega}(o_{n},w_{n})-3\kappa-1/n\\\
&\geq\mathsf{k}_{\Omega}(z_{n},o_{n})+\mathsf{k}_{\Omega}(o_{n},w_{0})+1-1/n\\\
&\geq\mathsf{k}_{\Omega}(z_{n},w_{0})+1-1/n\\\
&\geq\mathsf{k}_{\Omega}(z_{n},W_{2}^{c})+1-1/n.\end{split}$

This is a contradiction. Hence the lemma. ∎

As a corollary of above lemma , we have a similar local result.

######  Lemma 0.7.

Suppose $\Omega\subset\mathbb{C}^{d}$ is a domain and $U$ open subsets of
$\mathbb{C}^{d}$ such that $U\cap\Omega$ is connected and
$U\cap\partial\Omega\neq\emptyset$. Suppose
$(U\cap\Omega,\mathsf{k}_{U\cap\Omega})$ has weak-visibility property for
every pair of distinct points $\\{p,q\\}$, $p,q\in U\cap\partial\Omega$. Then
for every $W_{1}\subset\subset W_{2}\subset\subset U$ and $o\in U\cap\Omega$
there exists $L>0$ such that for all $z\in W_{1}\cap\Omega$

$\mathsf{k}_{U\cap\Omega}(z,o)\leq\mathsf{k}_{U\cap\Omega}(z,W_{2}^{c})+L.$

###### Proof.

The proof follows from above lemma by replacing $\Omega$ by $U\cap\Omega$ and
using Corollary 0.5. ∎

######  Lemma 0.8.

Suppose $\Omega\subset\mathbb{C}^{d}$ is a domain and $U$ open subsets of
$\mathbb{C}^{d}$ such that $U\cap\Omega$ is connected and
$U\cap\partial\Omega\neq\emptyset$. Suppose
$(U\cap\Omega,\mathsf{k}_{U\cap\Omega})$ has weak-visibility property for
every pair of distinct points $\\{p,q\\}$, $p,q\in U\cap\partial\Omega$. Let
$W\subset\subset U$ be an open set, suppose $z,w\in W\cap\Omega$ and $\gamma$
is a $(1,\kappa)$-almost-geodesic of $(\Omega,\mathsf{k}_{\Omega})$ joining
$z$ and $w$ such that $\gamma\subset W$. Then there exists a $\kappa_{0}>0$
such that $\gamma$ is $(1,\kappa_{0})$-quasi-geodesic of
$(U\cap\Omega,\mathsf{k}_{U\cap\Omega})$.

###### Proof.

Let $W_{1}$ be an open set such that $W\subset\subset W_{1}\subset\subset U$.
By Lemma 0.3, there exists $L>0$ which depends on $U,W_{1}$ such that for all
$z\in W_{1}\cap\Omega$ and $v\in\mathbb{C}^{d}$,

$\kappa_{U\cap\Omega}(z;v)\leq\left(1+Le^{-\mathsf{k}_{\Omega}(z,U^{c})}\right)\kappa_{\Omega}(z;v).$

Since $\mathsf{k}_{\Omega}(z,W_{1}^{c})\leq\mathsf{k}_{\Omega}(z,U^{c})$, we
have

(0.5)
$\kappa_{U\cap\Omega}(z;v)\leq\left(1+Le^{-\mathsf{k}_{\Omega}(z,W_{1}^{c})}\right)\kappa_{\Omega}(z;v).$

Since $\gamma\subset W$, from above inequality and by the Result
LABEL:R:Def_Kobayshi_Absolute

(0.6)
$\begin{split}\mathsf{k}_{U\cap\Omega}(z,w)&\leq\int_{0}^{a}\kappa_{U\cap\Omega}(\gamma(t);\gamma^{\prime}(t))dt\\\
&\leq\int_{0}^{a}\left(1+Le^{-\mathsf{k}_{\Omega}(\gamma(t),W_{1}^{c})}\right)\kappa_{\Omega}(\gamma(t);\gamma^{\prime}(t))dt\\\
&\leq a+L\int_{0}^{a}e^{-\mathsf{k}_{\Omega}(\gamma(t),W_{1}^{c})}dt\\\
&\leq\mathsf{k}_{\Omega}(z,w)+\kappa+L\int_{0}^{a}e^{-\mathsf{k}_{\Omega}(\gamma(t),W_{1}^{c})}dt.\end{split}$

Claim. There exist $C_{0},C_{1}>0$ such that for all $z\in W_{2}\cap\Omega$

$\mathsf{k}_{U\cap\Omega}(z,W_{1}^{c})\leq
C_{0}\mathsf{k}_{\Omega}(z,W_{1}^{c})+C_{1}.$

Assuming the claim, deferring the proof, first, by Lemma 0.7, for $o\in
U\cap\Omega$ there exists $L_{0}>0$ which depends on $o,W,W_{1},U$ such that
for all $z\in W$

$\mathsf{k}_{U\cap\Omega}(z,o)\leq\mathsf{k}_{U\cap\Omega}(z,W_{1}^{c})+L_{0}.$

Next, let $t_{0}\in[0,a]$ such that for all $t\in[0,a]$,

$\mathsf{k}_{\Omega}(\gamma(t_{0}),W_{1}^{c})\leq\mathsf{k}_{\Omega}(\gamma(t),W_{1}^{c})+L_{0}.$

Now, applying the above inequalities in the following computation, we obtain,
for all $t\in[0,a]$

$\begin{split}|t-t_{0}|-\kappa&\leq\mathsf{k}_{\Omega}(\gamma(t),\gamma(t_{0}))\\\
&\leq\mathsf{k}_{\Omega}(\gamma(t),o)+\mathsf{k}_{\Omega}(\gamma(t_{0}),o)\\\
&\leq\mathsf{k}_{U\cap\Omega}(\gamma(t),o)+\mathsf{k}_{U\cap\Omega}(\gamma(t_{0}),o)\\\
&\leq\mathsf{k}_{U\cap\Omega}(\gamma(t),W_{1}^{c})+\mathsf{k}_{U\cap\Omega}(\gamma(t_{0}),W_{1}^{c})+2L_{0}\\\
&\leq 2\mathsf{k}_{U\cap\Omega}(\gamma(t),W_{1}^{c})+3L_{0}\\\ \end{split}$

If we apply the claim to the above inequality we get

$\begin{split}|t-t_{0}|-\kappa&\leq
2\mathsf{k}_{U\cap\Omega}(\gamma(t),W_{1}^{c})+3L_{0}\\\ &\leq
2C_{0}\mathsf{k}_{\Omega}(\gamma(t),W_{1}^{c})+2C_{1}+3L_{0}.\end{split}$

This gives, for all $t\in[0,a]$

$-\mathsf{k}_{\Omega}(\gamma(t),W_{1}^{c})\leq\frac{-|t-t_{0}|}{2C_{0}}+\frac{2C_{1}+3L_{0}+\kappa}{2C_{0}}.$

After using the above inequality in inequality (0.6), we obtain

(0.7)
$\begin{split}\mathsf{k}_{U\cap\Omega}(z,w)&\leq\mathsf{k}_{\Omega}(z,w)+\kappa+LC_{3}\int_{0}^{a}e^{-\frac{|t-t_{0}|}{C_{0}2}}dt\\\
&\leq\mathsf{k}_{\Omega}(z,w)+\kappa+LC_{3}\int_{0}^{+\infty}e^{-\frac{|t-t_{0}|}{2C_{0}}}dt\\\
&\leq\mathsf{k}_{\Omega}(z,w)+\kappa+2LC_{3}C_{0}\end{split}$

where $C_{3}=e^{\frac{2C_{1}+3L_{0}+\kappa}{2C_{0}}}$, and the last inequality
follows from the following bound:

(0.8) $\int_{0}^{+\infty}e^{-\frac{|t-t_{0}|}{2C_{0}}}dt\leq 3C_{0}/2.$

###### Proof of the claim..

By the Royden’s Localization Lemma, for $W_{1}\subset\subset
W_{2}\subset\subset U$ there exists $C_{0}>0$, which depends on $U,W_{2}$,
such that for all $z\in W_{2}\cap\Omega$ and $v\in\mathbb{C}^{d}$,

$\kappa_{U\cap\Omega}(z;v)\leq C_{0}\kappa_{\Omega}(z;v).$

Now, suppose that $w_{n}\in\Omega\setminus W_{1}$ such that
$\lim_{n\to\infty}\mathsf{k}_{\Omega}(z,w_{n})=\mathsf{k}_{\Omega}(z,W_{1}^{c})$
and $\gamma_{n}:[0,a_{n}]\longrightarrow\Omega$ is sequence of
$(1,\kappa)$-almost-geodesic joining $z$ and $w_{n}$ with respect to
$(\Omega,\mathsf{k}_{\Omega})$, for some $\kappa>0$.

$t_{n}=\sup\\{t:t\in[0,a_{n}]\,\,\text{such that}\,\,\gamma_{n}(s)\in
W_{1}\,\forall s\in[0,t]\\},$

By definition, $\gamma_{n}([0,t_{n}])\subset W_{2}\cap\Omega$. Then,

$\begin{split}\mathsf{k}_{U\cap\Omega}(z,W_{1}^{c})&\leq\mathsf{k}_{U\cap\Omega}(z,\gamma_{n}(t_{n}))\\\
&\leq\int_{0}^{t_{n}}\kappa_{U\cap\Omega}(\gamma_{n}(t);\gamma_{n}^{\prime}(t))dt\\\
&\leq
C_{0}\int_{0}^{t_{n}}\kappa_{\Omega}(\gamma_{n}(t);\gamma_{n}^{\prime}(t))dt\\\
&\leq C_{0}\int_{0}^{a_{n}}\kappa_{\Omega}(\gamma(t);\gamma^{\prime}(t))dt\\\
&\leq C_{0}\mathsf{k}_{\Omega}(z,w_{n})+C_{0}\kappa\\\ \end{split}$

Taking limit as $n\to\infty$, we get

$\mathsf{k}_{U\cap\Omega}(z,W_{1}^{c})\leq
C_{0}\mathsf{k}_{\Omega}(z,W_{1}^{c})+C_{0}\kappa.$

This proves the claim. Hence the proof is complete. ∎

∎

######  Lemma 0.9.

Suppose $\Omega\subset\mathbb{C}^{d}$ is a domain and $U$ open subsets of
$\mathbb{C}^{d}$ such that $U\cap\Omega$ is connected and
$U\cap\partial\Omega\neq\emptyset$. Suppose $(\Omega,\mathsf{k}_{\Omega})$ has
weak-visibility property for every pair of distinct points $\\{p,q\\}$,
$p,q\in U\cap\partial\Omega$. Let $W\subset\subset U$ be an open set, suppose
$z,w\in W\cap\Omega$ and $\gamma$ is a $(1,\kappa)$-almost-geodesic of
$(\Omega,\mathsf{k}_{\Omega})$ joining $z$ and $w$ such that $\gamma\subset
W$. Then there exists a $\kappa_{0}>0$ such that $\gamma$ is
$(1,\kappa_{0})$-quasi-geodesic of $(U\cap\Omega,\mathsf{k}_{U\cap\Omega})$.

###### Proof.

The proof is similar to the proof of Lemma 0.8. ∎

###### Proof of Theorem 0.1.

To get a contradiction, suppose that there exist sequences of points
$z_{n},w_{n}\in W\cap\Omega$ such that as $n\to\infty$,

$\mathsf{k}_{U\cap\Omega}(z_{n},w_{n})-\mathsf{k}_{\Omega}(z_{n},w_{n})\to+\infty.$

Suppose $W_{1},W_{2}$ are two open subsets of $\mathbb{C}^{d}$ such that
$W\subset\subset W_{1}\subset\subset W_{2}\subset\subset U$. Then by Lemma
0.8, for a $\kappa>0$ there exists $\kappa_{0}>0$ which depends on $W_{2},U$
such that if $\gamma:[o,a]\longrightarrow W_{2}\cap\Omega$ is a
$(1,\kappa)$-almost-geodesic with respect to $(\Omega,\mathsf{k}_{\Omega})$,
$\gamma$ is a $(1,\kappa_{0})$-quasi-geodesic with respect to
$(U\cap\Omega,\mathsf{k}_{U\cap\Omega})$. Now, suppose
$\gamma_{n}:[0,a_{n}]\longrightarrow\Omega$ is a sequence of
$(1,\kappa)$-almost-geodesics with respect to $(\Omega,\mathsf{k}_{\Omega})$
such that $\gamma(0)=z_{n}$ and $\gamma_{n}(a_{n})=w_{n}$ , and

$s_{n}=\sup\\{t:t\in[0,a_{n}]\,\,\text{such that}\,\,\gamma_{n}(s)\in
W_{1}\,\forall s\in[0,t]\\},$ $t_{n}=\inf\\{t:t\in[0,a_{n}]\,\,\text{such
that}\,\,\gamma_{n}(s)\in W_{1}\,\forall s\in[t,a_{n}]\\}$

for all $n$. Note that by definition, $\gamma_{n}([0,s_{n}])\subset W_{2}$ and
$\gamma_{n}([t_{n},a_{n}])\subset W_{2}$ for all $n$. Hence
$\sigma^{1}_{n}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\gamma_{n}|_{[0,s_{n}]}$
and
$\sigma^{2}_{n}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\gamma_{n}|_{[t_{n},a_{n}]}$
are $(1,\kappa_{0})$-quasi-geodesic with respect to
$(U\cap\Omega,\mathsf{k}_{U\cap\Omega})$ for all $n$. Since
$(U\cap\Omega,\mathsf{k}_{U\cap\Omega})$ has weak-visibility for distinct
points in $U\cap\partial\Omega$, for $o\in U\cap\Omega$, there exists $C>0$
such that for all $n$,

$\mathsf{k}_{U\cap\Omega}(z_{n},o)+\mathsf{k}_{U\cap\Omega}(o,\gamma_{n}(s_{n}))-C\leq\mathsf{k}_{U\cap\Omega}(z_{n},\gamma_{n}(s_{n}))$

and

$\mathsf{k}_{U\cap\Omega}(w_{n},o)+\mathsf{k}_{U\cap\Omega}(o,\gamma_{n}(t_{n}))-C\leq\mathsf{k}_{U\cap\Omega}(w_{n},\gamma_{n}(t_{n})).$

Now,

$\begin{split}\mathsf{k}_{\Omega}(z_{n},w_{n})&\geq a_{n}-\kappa\\\ &\geq
a_{n}-t_{n}+s_{n}-\kappa\\\
&\geq\mathsf{k}_{U\cap\Omega}(w_{n},\gamma_{n}(t_{n})-\kappa_{0}+\mathsf{k}_{U\cap\Omega}(\gamma_{n}(s_{n}),z_{n})-\kappa_{0}-\kappa\\\
&\geq\mathsf{k}_{U\cap\Omega}(z_{n},o)+\mathsf{k}_{U\cap\Omega}(o,\gamma_{n}(s_{n}))-C+\mathsf{k}_{U\cap\Omega}(w_{n},o)+\mathsf{k}_{U\cap\Omega}(o,\gamma_{n}(t_{n}))-C-2\kappa_{0}-\kappa\\\
&\geq\mathsf{k}_{U\cap\Omega}(z_{n},o)+\mathsf{k}_{U\cap\Omega}(w_{n},o)-2C-2\kappa_{0}-\kappa\\\
&\geq\mathsf{k}_{U\cap\Omega}(z_{n},w_{n})-2C-2\kappa_{0}-\kappa.\end{split}$

This gives a contradiction. Hence the result. ∎

###### Proof of Theorem 0.2.

To get a contraditoin, suppose that there exist sequences of points
$z_{n},w_{n}\in W\cap\Omega$ such that as $n\to\infty$,

$\mathsf{k}_{U\cap\Omega}(z_{n},w_{n})-\mathsf{k}_{\Omega}(z_{n},w_{n})\to+\infty.$

Suppose $W_{1},W_{2}$ are two open subsets of $\mathbb{C}^{d}$ such that
$W\subset\subset W_{1}\subset\subset W_{2}\subset\subset U$. Then by Lemma
0.9, for a $\kappa>0$ there exists $\kappa_{0}>0$ which depends on $W_{2},U$
such that if $\gamma:[o,a]\longrightarrow W_{2}\cap\Omega$ is a
$(1,\kappa)$-almost-geodesic with respect to $(\Omega,\mathsf{k}_{\Omega})$,
$\gamma$ is a $(1,\kappa_{0})$-quasi-geodesic with respect to
$(U\cap\Omega,\mathsf{k}_{U\cap\Omega})$. Now, suppose
$\gamma_{n}:[0,a_{n}]\longrightarrow\Omega$ is a sequence of
$(1,\kappa)$-almost-geodesics with respect to $(\Omega,\mathsf{k}_{\Omega})$
such that $\gamma(0)=z_{n}$ and $\gamma_{n}(a_{n})=w_{n}$ , and

$s_{n}=\sup\\{t:t\in[0,a_{n}]\,\,\text{such that}\,\,\gamma_{n}(s)\in
W_{1}\,\forall s\in[0,t]\\},$ $t_{n}=\inf\\{t:t\in[0,a_{n}]\,\,\text{such
that}\,\,\gamma_{n}(s)\in W_{1}\,\forall s\in[t,a_{n}]\\}$

for all $n$. Note that by definition, $\gamma_{n}([0,s_{n}])\subset W_{2}$ and
$\gamma_{n}([t_{n},a_{n}])\subset W_{2}$ for all $n$. Hence
$\sigma^{1}_{n}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\gamma_{n}|_{[0,s_{n}]}$
and
$\sigma^{2}_{n}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\gamma_{n}|_{[t_{n},a_{n}]}$
are $(1,\kappa_{0})$-quasi-geodesic with respect to
$(U\cap\Omega,\mathsf{k}_{U\cap\Omega})$ for all $n$. Since
$(\Omega,\mathsf{k}_{\Omega})$ has weak-visibility for distinct points in
$U\cap\partial\Omega$, there exist compact subsets $K_{1},K_{2}\subset
U\cap\partial\Omega$ — using Corollary 0.5— such that $\sigma^{1}_{n}\cap
K_{1}\neq\emptyset$ and $\sigma^{2}_{n}\cap K_{2}\neq\emptyset$. Let
$o^{1}_{n}\in\sigma^{1}_{n}\cap K_{1}$ and $o^{2}_{n}\in\sigma^{2}_{n}\cap
K_{2}$. Now,

$\begin{split}\mathsf{k}_{\Omega}(z_{n},w_{n})&\geq a_{n}-\kappa\\\ &\geq
a_{n}-t_{n}+s_{n}-\kappa\\\
&\geq\mathsf{k}_{U\cap\Omega}(w_{n},\gamma_{n}(t_{n})-\kappa_{0}+\mathsf{k}_{U\cap\Omega}(\gamma_{n}(s_{n}),z_{n})-\kappa_{0}-\kappa\\\
&\geq\mathsf{k}_{U\cap\Omega}(w_{n},o_{n}^{2})+\mathsf{k}_{U\cap\Omega}(o_{n}^{2},\gamma_{n}(t_{n}))+\mathsf{k}_{U\cap\Omega}(z_{n},o^{1}_{n})+\mathsf{k}_{U\cap\Omega}(o^{1}_{n},\gamma_{n}(s_{n})-4\kappa_{0}-\kappa\\\
&\geq\mathsf{k}_{U\cap\Omega}(w_{n},\gamma_{n}(t_{n})+\mathsf{k}_{U\cap\Omega}(\gamma_{n}(s_{n}),z_{n})-\kappa\\\
&\geq\mathsf{k}_{U\cap\Omega}(w_{n},o_{n}^{2})+\mathsf{k}_{U\cap\Omega}(z_{n},o^{1}_{n})+\mathsf{k}_{U\cap\Omega}(o^{2}_{n},o^{1}_{n})-\mathsf{k}_{U\cap\Omega}(o^{2}_{n},o^{1}_{n})-4\kappa_{0}-\kappa\\\
&\geq\mathsf{k}_{U\cap\Omega}(z_{n},w_{n})-diam(K_{1}\cup
K_{2})-4\kappa_{0}-\kappa.\end{split}$

This gives a contradiction. Hence the result. ∎

Acknowledgement. The author would like to thank Anwoy Maitra, Vikramjeet Singh
Chandel and Sushil Gorai for useful discussions.

## References

  * [1] F. Bracci, H. Guassier, N. Nikolov and P. J. Thomas, Local and global visibility and Gromov hyperbolicity of domains with respect to the Kobayashi distance, arXiv:2201.03070 (2022).
  * [2] F. Bracci, N. Nikolov and P. J. Thomas, Visibility of Kobayashi geodesics in convex domains and related properties, Math. Z., 301(2):2011–2035, 2022.
  * [3] Martin R. Bridson and André Haefliger, Metric Spaces of Non-positive Curvature, Grundlehren der Mathematischen Wissenschaften 319, Springer-Verlag, Berlin, 1999\.
  * [4] V. S. Chandel, A. Maitra, A. D. Sarkar, Notions of Visibility with respect to the Kobayashi distance: Comparison and Applications. arXiv:2111.00549.
  * [5] I. Graham, Boundary behavior of the Carathéodory and the Kobayashi metrics on strongly pseudoconvex domains in $\mathbb{C}^{n}$ with smooth boundary, Trans. of Amer. Math. Soc. 207 (1975), 219-240.
  * [6] Peter Kiernan, _On the relations between taut, tight and hyperbolic manifolds_ , Bull. Amer. Math. Soc. 76 (1970), 49–51.
  * [7] H.L. Royden, Remarks on the Kobayashi metric, in Several Complex Variables, II, (Proc. Internat. Conf., Univ. Maryland, College Park, MD, 1970), pp. 125–137, Lecture Notes in Math. 185, Springer, Berlin, 1971.


# SERRANT: a syntactic classifier for English Grammatical Error Types

Leshem Choshen
Department of Computer Science
Hebrew University of Jerusalem
<EMAIL_ADDRESS>
Matanel Oren
Department of Computer Science
Hebrew University of Jerusalem
<EMAIL_ADDRESS>
Dmitry Nikolaev
Department of Linguistics
Stockholm University
<EMAIL_ADDRESS>
Omri Abend
Department of Computer Science
Hebrew University of Jerusalem
<EMAIL_ADDRESS>

###### Abstract

SERRANT is a system and code for automatic classification of English
grammatical errors that combines SErCl (Choshen et al., 2020) and ERRANT
(Bryant et al., 2017). SERRANT uses ERRANT’s annotations when they are
informative and those provided by SErCl otherwise.

##  1 Inroduction

In grammatical error correction (GEC), an erroneous part of a sentence and its
correction is called an edit. It is often useful to categorize edits into
types, e.g., to improve results Junczys-Dowmunt et al. (2018); Kantor et al.
(2019) and for system evaluation (Choshen and Abend, 2018; Bryant et al.,
2019a). A set of edit types is called a taxonomy. In current annotations,
taxonomies always differ between datasets of different languages (Rozovskaya
and Roth, 2019; Lee et al., 2016) and mostly differ between datasets of the
same language (Dahlmeier et al., 2013; Berzak et al., 2016). For English,
there are two automatic edit type classifiers, ERRANT and SErCl following two
different taxonomies. These classifiers can be applied to any dataset
containing corrections111Edits can be extracted automatically as well, so a
sentence and its correction suffice. and are thus the instrument of choice
whenever more than one dataset is used. We present an attempt to combine the
two taxonomies and the two classifiers into one system, which present outputs
in a unified way.222Code is found in https://github.com/matanel-oren/serrant

ERRANT (Bryant et al., 2017) is a rule-based classifier of errors for English.
ERRANT types include general categories like Spelling, Morphology and more
specific categories reflecting the dominant POS in the edit (e.g. adverb or
adjective). These categories may be further refined through sub-categories
such as Inflection (e.g., verb:infl). ERRANT was used as the official taxonomy
of the BEA shared task (Bryant et al., 2019a) and provides a precise set of
rules to map edits to types.

A recent study presented SErCl (Choshen et al., 2020), a cross-lingual
taxonomy of syntactic errors. SErCl defines an error type as the concatenation
of morphosyntactic features of the text fragment before and after the change.
Formally, given a span from a learner sentence $l$ and its correction $c$, and
given a Universal Dependencies (Nivre et al., 2016) annotation for these
spans, such as UPOS tags, dependency-relation labels, or morphological-feature
specifications for the heads of the spans’ subtrees, which we denote as
$UD_{l}$ and $UD_{c}$ respectively, the type of the error is
$UD_{l}\shortrightarrow UD_{c}$. Thus, the type for an edit where a noun
becomes a verb would be noun$\shortrightarrow$verb, and when a noun changes
its number from plural to singular, the type is
noun:singular$\shortrightarrow$noun:plural. If $UD_{l}$ is identical to
$UD_{c}$, we denote this type with $UD_{l}$ for brevity, and if the span was
deleted or added, the type is $UD_{l}$$\shortrightarrow$none or
none$\shortrightarrow$$UD_{c}$ respectively.

Choshen et al. (2020) showed that some of ERRANT’s categories are not
informative or not consistent, while others are. They also note that ERRANT’s
POS-based types sometimes include cases where the POS changes. When POS is
changed upon correction ERRANT is not well defined, it may assume the dominant
type is the source or the correction, and quite often no type would be
attached to the edit known as other type. ERRANT does have the benefit of
being more human-readable when it is accurate, hence, SERRANT’s default
behaviour is chosen to be ERRANT types.

The main aim when constructing SERRANT’s rules was informativeness. Thus, we
preserve ERRANT’s subclassifications allowing users to group together similar
classes or ignore them altogether.

##  2 Combining the classifiers

In the default case, SERRANT returns ERRANT’s edit types.333Following ERRANT’s
conventions, we keep the R, M, U initials meaning replacement, missing, and
unnecessary respectively. For example, a deleted verb,
verb$\shortrightarrow$none in SErCl’s terms, would be tagged U:Verb. The
special cases are the following:

  1. 1.

ERRANT’s other category signifies failure to find informative type. Hence, we
rely on SErCl types in this case. We do keep the other category for unreliable
cases, which we define as edits involving Intj, Num, Sym, X, and Punct POS
tags. We also find that proper noun (Propn) is generally unreliable since the
current parser uses it as a fallback for various erroneously spelled words. We
do keep the propn$\shortrightarrow$propn type because repetition reduces the
risk of parser errors.

  2. 2.

ERRANT’s morphology error type (morph) comprises a multitude of phenomena. We
replace it with SErCl’s types. We also expose the information originally
captured by the morph type in a different way. When the lemmas do not match
between the source and the target, we add a sub-category suffix “WC”. This
indicates that while the POS did not change, the main error is in the choice
of word and not in morphosyntactic features (e.g.,
consume$\shortrightarrow$eat would be verb:wc but eat$\shortrightarrow$ate
would not). We ignored the problematic cases mentioned in connection with the
other ERRANT type but kept cases of adj$\shortrightarrow$propn or
propn$\shortrightarrow$adj, such as China$\shortrightarrow$Chinese.

  3. 3.

We added a suffix “MW”, which corresponds to a multi-word change in either the
source or the correction. MW is only added when the multiword is not of an
already named type such as verb:tense.

  4. 4.

ERRANT’s orthography (orth) type is generally correct, for example when
reflecting a missing whitespace. However, it does contain cases where a proper
noun should have been capitalized. While this is an orthographic error, unlike
most such errors, it sometimes changes morphosyntax and/or the meaning.
Therefore, if the word was not the first in the sentence, and was changed into
a proper noun (Propn), SERRANT returns SErCl’s annotation
x$\shortrightarrow$propn (e.g., “He founded apple” $\shortrightarrow$ “He
founded Apple”).

  5. 5.

The ERRANT verb type reflects both aux and verb edits. We follow SErCl and
mark them as aux where needed.

  6. 6.

When a noun is changed into a verb, ERRANT marks this as verb:form. As this is
not a change in the verb form, we denote this with noun$\shortrightarrow$verb.
(e.g., trap$\shortrightarrow$trapped).

  7. 7.

Cases where a pronoun becomes a determiner or the other way around (e.g.
these$\shortrightarrow$their) are included in the ERRANT types pron and
determiner det. We replace these annotations with more informative types
pron$\shortrightarrow$det and det$\shortrightarrow$pron.

  8. 8.

ERRANT lumps tense, aspect, and mood together under verb:tense. When both the
original and the corrected wordform have the lemmas be or have or the wordform
is ”will” we name it verb:tense. When both words are modal verbs (can, could,
may, might, shall, should, will, would, must), we add the suffix “Modal”.
Otherwise we return the annotation provided by SErCl.

##  3 Examples

In this section, we give some examples of the annotations returned by the
model. The errors and corrections themselves are made up. The model follows
the m2 format, but, for convenience, we provide a more visual format. More
examples are provided with the code. In the examples
$\shortrightarrow$represents a correction of a given word (no multiword errors
in the examples for simplicity), in brackets are the type SERRANT would give
the error.

  * •

I werk$\shortrightarrow$work (r:spell) for pen$\shortrightarrow$Pen
(r:noun$\shortrightarrow$propn)

  * •

gilly$\shortrightarrow$Gilly (r:orth) is imagination
$\shortrightarrow$imagining (r:noun$\shortrightarrow$verb)

  * •

I drive$\shortrightarrow$ride (r:verb:wc) the$\shortrightarrow$$\emptyset$
(u:det) my bicycle.

  * •

I should$\shortrightarrow$shall (r:modal) do as as I must.

We also add some examples from level A learners of the W&I corpus (Bryant et
al., 2019b):

  * •

In addition to it$\shortrightarrow$that (r:pron$\shortrightarrow$det), we can
also take a comfortable short nap on the back seat and wake up fresh.

  * •

My family think that my cook$\shortrightarrow$cooking (r:morph:noun) is
amazing.

  * •

It is great$\shortrightarrow$very (r:adv$\shortrightarrow$adj)
fun$\shortrightarrow$funny (r:adj$\shortrightarrow$noun).

  * •

How are you? I’m writing to inform$\shortrightarrow$give (r:verb:wc) you
that$\shortrightarrow$$\emptyset$ (u:prep) some advice on travelling and
working in my country.

## References

  * Berzak et al. (2016) Yevgeni Berzak, Jessica Kenney, Carolyn Spadine, Jing Xian Wang, Lucia Lam, Keiko Sophie Mori, Sebastian Garza, and Boris Katz. 2016.  Universal Dependencies for learner English.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 737–746, Berlin, Germany. Association for Computational Linguistics.
  * Bryant et al. (2019a) Christopher Bryant, Mariano Felice, Øistein E. Andersen, and Ted Briscoe. 2019a.  The BEA-2019 shared task on grammatical error correction.  In _Proceedings of the Fourteenth Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 52–75, Florence, Italy. Association for Computational Linguistics.
  * Bryant et al. (2019b) Christopher Bryant, Mariano Felice, Øistein E. Andersen, and Ted Briscoe. 2019b.  The BEA-2019 shared task on grammatical error correction.  In _Proceedings of the Fourteenth Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 52–75, Florence, Italy. Association for Computational Linguistics.
  * Bryant et al. (2017) Christopher Bryant, Mariano Felice, and Ted Briscoe. 2017.  Automatic annotation and evaluation of error types for grammatical error correction.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 793–805, Vancouver, Canada. Association for Computational Linguistics.
  * Choshen and Abend (2018) Leshem Choshen and Omri Abend. 2018.  Automatic metric validation for grammatical error correction.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1372–1382, Melbourne, Australia. Association for Computational Linguistics.
  * Choshen et al. (2020) Leshem Choshen, D. Nikolaev, Yevgeni Berzak, and Omri Abend. 2020.  Classifying syntactic errors in learner language.  _ArXiv_ , abs/2010.11032.
  * Dahlmeier et al. (2013) Daniel Dahlmeier, Hwee Tou Ng, and Siew Mei Wu. 2013.  Building a large annotated corpus of learner English: The NUS corpus of learner English.  In _Proceedings of the Eighth Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 22–31, Atlanta, Georgia. Association for Computational Linguistics.
  * Junczys-Dowmunt et al. (2018) Marcin Junczys-Dowmunt, Roman Grundkiewicz, Shubha Guha, and Kenneth Heafield. 2018\.  Approaching neural grammatical error correction as a low-resource machine translation task.  In _NAACL-HLT_.
  * Kantor et al. (2019) Yoav Kantor, Yoav Katz, Leshem Choshen, Edo Cohen-Karlik, Naftali Liberman, Assaf Toledo, Amir Menczel, and Noam Slonim. 2019.  Learning to combine grammatical error corrections.  In _Proceedings of the Fourteenth Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 139–148, Florence, Italy. Association for Computational Linguistics.
  * Lee et al. (2016) Lung-Hao Lee, G. Rao, L. Yu, E. Xun, B. Zhang, and L. Chang. 2016.  Overview of nlp-tea 2016 shared task for chinese grammatical error diagnosis.  In _NLP-TEA@COLING_.
  * Nivre et al. (2016) Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Yoav Goldberg, Jan Hajic, Christopher D. Manning, Ryan McDonald, Slav Petrov, Sampo Pyysalo, Natalia Silveira, Reut Tsarfaty, and Daniel Zeman. 2016.  Universal dependencies v1: A multilingual treebank collection.  In _Proc. of LREC_ , pages 1659–1666.
  * Rozovskaya and Roth (2019) Alla Rozovskaya and Dan Roth. 2019.  Grammar error correction in morphologically rich languages: The case of Russian.  _Transactions of the Association for Computational Linguistics_ , 7:1–17.