0.50 BioYaping Zhao is a life-long student of physics, and her career
encompasses engineering, thinking and writing.
When she’s not busy puzzling over academic research, Yaping reads interesting
books. What I cannot create, I do not understand. Know how to solve every
problem that has been solved. — Richard Feynman cover.jpg

#  Mathematical Cookbook for
Snapshot Compressive Imaging

Mathematics in Snapshot Compressive Imaging (SCI)

Yaping Zhao<EMAIL_ADDRESS>
(Mar 19, 2023)

###### Contents

  1. 1 Introduction
    1. 1.1 Preface
  2. 2 Conventional Optimization
    1. 2.1 Gradient Descent
    2. 2.2 ADMM: Alternating Directions Method of Multipliers
      1. 2.2.1 Augmented Lagrangian Method
      2. 2.2.2 Scaled Form
    3. 2.3 GAP: Generalized Alternating Projection
  3. 3 Deep Equilibrium Models
    1. 3.1 Review of Deep Learning based Algorithms
    2. 3.2 Forward Pass
      1. 3.2.1 Recurrent Neural Networks
      2. 3.2.2 Generalized Alternating Projection
      3. 3.2.3 Anderson Acceleration
    3. 3.3 Backward Pass
      1. 3.3.1 Loss Function
      2. 3.3.2 Gradient Calculation
    4. 3.4 Convergence Theory

##  Chapter 1 Introduction

###  1.1 Preface

The author intends to provide you with a beautiful, elegant, user-friendly
cookbook for mathematics in Snapshot Compressive Imaging (SCI). Currently, the
cookbook is composed of introduction, conventional optimization, and deep
equilibrium models. The latest releases are strongly recommended! For any
other questions, suggestions, or comments, feel free to email the author.

Email:

Because the author is too lazy to write a tediously long introduction, the
author assume that readers of this book own preliminary knowledge about the
mathematical model of SCI. If you do not, the author highly recommend you to
read the introduction session of the paper Zhao et al., (2022) or any other
SCI publications before you begin this mathematical journey.

##  Chapter 2 Conventional Optimization

To begin with, imaging we observe a corrupted set of measurements $\bm{y}$ of
an image $\bm{x}$ under a linear measurement operator $\bm{\Phi}$ with some
noise ${\bm{e}}$ according to

$\displaystyle\mathbf{y}=\mathbf{\Phi}\mathbf{x}+\mathbf{e},$ (2.1)

Suppose we have a known regularization function $R$ that could be applied to
an image x. Then we could compute an image estimate $\hat{x}$ by solving the
optimization problem

$\displaystyle\mathbf{\hat{x}}=\mathop{\arg\min}_{\mathbf{x}}\frac{1}{2}||\mathbf{y}-\mathbf{\Phi}\mathbf{x}||_{2}^{2}+R(\mathbf{x}).$
(2.2)

###  2.1 Gradient Descent

If $R$ is differentiable, this can be accomplished via gradient descent. We
could get

$\displaystyle\begin{aligned}
&\frac{\partial}{\partial\bm{x}}[\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+R(\bm{x})]\\\
=&-\frac{1}{2}\cdot
2\cdot\bm{\Phi}^{T}(\bm{y}-\bm{\Phi}\bm{x})+\frac{\partial{R(\bm{x})}}{\partial\bm{x}}\\\
=&-\bm{\Phi}^{T}(\bm{y}-\bm{\Phi}\bm{x})+\bigtriangledown
R(\bm{x}).\end{aligned}$ (2.3)

That is, we start with an initial estimate $\bm{x}^{(0)}$ such as
$\bm{x}^{(0)}=\bm{\Phi}^{T}\bm{y}$ and choose a step size $\alpha>0$, such
that for iteration $k=1,2,3...$, we set

$\displaystyle\begin{aligned}
\bm{x}^{(k+1)}&=\bm{x}^{(k)}-\alpha[-\bm{\Phi}^{T}(\bm{y}-\bm{\Phi}\bm{x})+\bigtriangledown
R(\bm{x})]\\\
&=\bm{x}^{(k)}+\alpha\bm{\Phi}^{T}(\bm{y}-\bm{\Phi}\bm{x})-\alpha\bigtriangledown
R(\bm{x}).\end{aligned}$ (2.4)

###  2.2 ADMM: Alternating Directions Method of Multipliers

By introducing an auxiliary parameter $\bm{v}$, the unconstrained optimization
in Eq.2.2 can be converted into

$\displaystyle\begin{aligned}
(\hat{\bm{x}},\hat{\bm{v}})=\mathop{\arg\min}_{\bm{x},\bm{v}}\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+R(\bm{v}),\\\
s.t.\ \bm{x}=\bm{v}.\end{aligned}$ (2.5)

####  2.2.1 Augmented Lagrangian Method

Using augmented Lagrangian method, we introduce an parameter ${\bm{u}}$ to be
updated and another $\rho$ to be manually set, and get the augmented
Lagrangian function of Eq.2.5 as

$\displaystyle L_{\rho}(\bm{x},\bm{v},{\bm{u}})$
$\displaystyle=\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+R(\bm{v})+{\bm{u}}^{T}(\bm{x}-\bm{v})+\frac{\rho}{2}||\bm{x}-\bm{v}||_{2}^{2}$
(2.6)

To facilitate updates of $\bm{x}$, we rewrite Eq.2.6 as

$\displaystyle\begin{aligned}
L_{\rho}(\bm{x},\bm{v},{\bm{u}})&=\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+R(\bm{v})+{\bm{u}}^{T}\bm{x}-{\bm{u}}^{T}\bm{v}+\frac{\rho}{2}(\bm{x}^{T}\bm{x}-2\cdot\bm{x}^{T}\bm{v}+\bm{v}^{T}\bm{v})\\\
&=\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+R(\bm{v})+\frac{\rho}{2}[\bm{x}^{T}\bm{x}-2(\bm{v}-\frac{1}{\rho}{\bm{u}})\bm{x}+(\bm{v}-\frac{1}{\rho}{\bm{u}})^{2}-(\bm{v}-\frac{1}{\rho}{\bm{u}})^{2}]-{\bm{u}}^{T}\bm{v}\\\
&=\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+R(\bm{v})+\frac{\rho}{2}||\bm{x}-(\bm{v}-\frac{1}{\rho}{\bm{u}})||_{2}^{2}-\frac{\rho}{2}(\bm{v}-\frac{1}{\rho}{\bm{u}})^{2}-{\bm{u}}^{T}\bm{v}.\end{aligned}$
(2.7)

Similarly, to facilitate updates of $\bm{v}$, we have

$\displaystyle\begin{aligned}
L_{\rho}(\bm{x},\bm{v},{\bm{u}})&=\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+R(\bm{v})+{\bm{u}}^{T}\bm{x}-{\bm{u}}^{T}\bm{v}+\frac{\rho}{2}(\bm{v}^{T}\bm{v}-2\cdot\bm{x}^{T}\bm{v}+\bm{x}^{T}\bm{x})\\\
&=\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+R(\bm{v})+\frac{\rho}{2}[\bm{v}^{T}\bm{v}-2(\bm{x}+\frac{1}{\rho}{\bm{u}})\bm{v}+(\bm{x}+\frac{1}{\rho}{\bm{u}})^{2}-(\bm{x}+\frac{1}{\rho}{\bm{u}})^{2}]+{\bm{u}}^{T}\bm{x}\\\
&=\frac{1}{2}||\bm{y}-\Phi\bm{x}||_{2}^{2}+R(\bm{v})+\frac{\rho}{2}||\bm{v}-(\bm{x}+\frac{1}{\rho}{\bm{u}})||_{2}^{2}-\frac{\rho}{2}(\bm{x}+\frac{1}{\rho}{\bm{u}})^{2}+{\bm{u}}^{T}\bm{x}.\end{aligned}$
(2.8)

Then ADMM solves it by the following sequence of sub-problems:

$\displaystyle\begin{aligned}
\bm{x}^{(k+1)}&=\mathop{\arg\min}_{\bm{x}}L_{\rho}(\bm{x},\bm{v}^{k},{\bm{u}}^{k})\\\
&=\mathop{\arg\min}_{\bm{x}}\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+R(\bm{v}^{k})+\frac{\rho}{2}||\bm{x}-(\bm{v}^{k}-\frac{1}{\rho}{\bm{u}}^{k})||_{2}^{2}-\frac{\rho}{2}(\bm{v}^{k}-\frac{1}{\rho}{\bm{u}}^{k})^{2}-{{\bm{u}}^{k}}^{T}\bm{v}^{k}\quad(Eq.\ref{eq:lag1})\\\
&=\mathop{\arg\min}_{\bm{x}}\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+\frac{\rho}{2}||\bm{x}-(\bm{v}^{k}-\frac{1}{\rho}{\bm{u}}^{k})||_{2}^{2}\quad(delete\
terms\ not\ related\ to\ \bm{x}),\end{aligned}$ (2.9)

$\displaystyle\begin{aligned}
\bm{v}^{(k+1)}&=\mathop{\arg\min}_{\bm{v}}L_{\rho}(\bm{x}^{k},\bm{v},{\bm{u}}^{k})\\\
&=\mathop{\arg\min}_{\bm{v}}\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+R(\bm{v})+\frac{\rho}{2}||\bm{v}-(\bm{x}^{k}+\frac{1}{\rho}{\bm{u}}^{k})||_{2}^{2}-\frac{\rho}{2}(\bm{x}^{k}+\frac{1}{\rho}{\bm{u}}^{k})^{2}+{{\bm{u}}^{k}}^{T}\bm{x}\quad(Eq.\ref{eq:lag2})\\\
&=\mathop{\arg\min}_{\bm{v}}R(\bm{v})+\frac{\rho}{2}||\bm{v}-(\bm{x}^{k}+\frac{1}{\rho}{\bm{u}}^{k})||_{2}^{2}\quad(delete\
terms\ not\ related\ to\ \bm{v}),\end{aligned}$ (2.10)

$\displaystyle\begin{aligned}
{\bm{u}}^{(k+1)}&=\mathop{\arg\min}_{{\bm{u}}}L_{\rho}(\bm{x}^{k},\bm{v}^{k},{\bm{u}})\\\
&={\bm{u}}^{k}+\alpha\frac{\partial}{\partial{\bm{u}}}L_{\rho}(\bm{x}^{(k+1)},\bm{v}^{(k+1)},{\bm{u}})\quad(gradient\
descent)\\\
&={\bm{u}}^{k}+\alpha\frac{\partial}{\partial{\bm{u}}}(\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}^{(k+1)}||_{2}^{2}+R(\bm{v}^{(k+1)})+{\bm{u}}^{T}(\bm{x}^{(k+1)}-\bm{v}^{(k+1)})+\frac{\rho}{2}||\bm{x}^{(k+1)}-\bm{v}^{(k+1)}||_{2}^{2})\\\
&={\bm{u}}^{k}+\alpha(\bm{x}^{(k+1)}-\bm{v}^{(k+1)})\\\
&={\bm{u}}^{k}+\rho(\bm{x}^{(k+1)}-\bm{v}^{(k+1)})\quad(set\
\alpha=\rho).\end{aligned}$ (2.11)

####  2.2.2 Scaled Form

ADMM can be written in a slightly different form, which is often more
convenient, by combining the linear and quadratic terms in the augmented
Lagrangian and scaling the dual variable. Defining the residual
${\bm{r}}=\bm{x}-\bm{v}$ and recall Eq.2.6, we have

$\displaystyle\begin{aligned}
{\bm{u}}^{T}(\bm{x}-\bm{v})+\frac{\rho}{2}||\bm{x}-\bm{v}||_{2}^{2}&={\bm{u}}^{T}{\bm{r}}+\frac{\rho}{2}||{\bm{r}}||_{2}^{2}\\\
&=\frac{\rho}{2}{\bm{r}}^{T}{\bm{r}}+{\bm{u}}^{T}{\bm{r}}\\\
&=\frac{\rho}{2}({\bm{r}}^{T}{\bm{r}}+2\cdot\frac{1}{\rho}{\bm{u}}^{T}{\bm{r}}+\frac{1}{\rho^{2}}{\bm{u}}^{T}{\bm{u}}-\frac{1}{\rho^{2}}{\bm{u}}^{T}{\bm{u}})\\\
&=\frac{\rho}{2}({\bm{r}}^{T}{\bm{r}}+2\cdot\frac{1}{\rho}{\bm{u}}^{T}{\bm{r}}+\frac{1}{\rho}{\bm{u}}^{T}{\bm{u}})-\frac{1}{2\rho}{\bm{u}}^{T}{\bm{u}}\\\
&=\frac{\rho}{2}||{\bm{r}}+\frac{1}{\rho}{\bm{u}}||_{2}^{2}-\frac{1}{2\rho}||{\bm{u}}||_{2}^{2}\\\
&=\frac{\rho}{2}||{\bm{r}}+\bm{w}||_{2}^{2}-\frac{\rho}{2}||\bm{w}||_{2}^{2}\quad(\bm{w}=\frac{1}{\rho}{\bm{u}}),\end{aligned}$
(2.12)

where $\bm{w}=\frac{1}{\rho}{\bm{u}}$ is the scaled dual variable. Using the
scaled dual variable, we can rewrite Eq.2.6 as

$\displaystyle L_{\rho}(\bm{x},\bm{v},\bm{w})$
$\displaystyle=\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+R(\bm{v})+\frac{\rho}{2}||\bm{x}-\bm{v}+\bm{w}||_{2}^{2}-\frac{\rho}{2}||\bm{w}||_{2}^{2}$
(2.13)

Then we can express ADMM as

$\displaystyle\begin{aligned}
\bm{x}^{(k+1)}&=\mathop{\arg\min}_{\bm{x}}L_{\rho}(\bm{x},\bm{v}^{k},\bm{w}^{k})\\\
&=\mathop{\arg\min}_{\bm{x}}\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+R(\bm{v})+\frac{\rho}{2}||\bm{x}-\bm{v}+\bm{w}||_{2}^{2}-\frac{\rho}{2}||\bm{w}||_{2}^{2}\\\
&=\mathop{\arg\min}_{\bm{x}}\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+\frac{\rho}{2}||\bm{x}-\bm{v}+\bm{w}||_{2}^{2}\quad(delete\
terms\ not\ related\ to\ \bm{x}),\end{aligned}$ (2.14)

$\displaystyle\begin{aligned}
\bm{v}^{(k+1)}&=\mathop{\arg\min}_{\bm{v}}L_{\rho}(\bm{x}^{k},\bm{v},\bm{w}^{k})\\\
&=\mathop{\arg\min}_{\bm{v}}\frac{1}{2}||\bm{y}-\bm{\Phi}\bm{x}||_{2}^{2}+R(\bm{v})+\frac{\rho}{2}||\bm{x}-\bm{v}+\bm{w}||_{2}^{2}-\frac{\rho}{2}||\bm{w}||_{2}^{2}\\\
&=\mathop{\arg\min}_{\bm{v}}R(\bm{v})+\frac{\rho}{2}||\bm{x}-\bm{v}+\bm{w}||_{2}^{2}\quad(delete\
terms\ not\ related\ to\ \bm{v}),\end{aligned}$ (2.15)

$\displaystyle\begin{aligned}
\bm{w}^{(k+1)}&=\bm{w}^{k}+\alpha\frac{\partial}{\partial\bm{w}}L_{\rho}(\bm{x}^{(k+1)},\bm{v}^{(k+1)},\bm{w})\quad(gradient\
descent)\\\
&=\bm{w}^{k}+\alpha[\rho(\bm{x}^{(k+1)}-\bm{v}^{(k+1)}+\bm{w})-\rho\bm{w}]\\\
&=\bm{w}^{k}+\alpha\rho(\bm{x}^{(k+1)}-\bm{v}^{(k+1)})\\\
&=\bm{w}^{k}+\bm{x}^{(k+1)}-\bm{v}^{(k+1)}\quad(set\
\alpha\rho=1).\end{aligned}$ (2.16)

###  2.3 GAP: Generalized Alternating Projection

Generalized alternating projection (GAP) can be recognized as a special case
of ADMM, which works as a lower computational workload algorithm. Recall Eq.
2.5, GAP updates $\bm{x}^{k}$ and $\bm{v}^{k}$ as follows:

  * •

Updating $\bm{x}:\bm{x}^{k}$ is updated via a Euclidean projection of
$\bm{v}^{k}$ on the linear manifold ${{\bf M}}:\bm{y}=\bm{\Phi}\bm{x}$. That
is,

$\displaystyle\bm{x}^{(k+1)}=\bm{v}^{k}+{\bm{\Phi}}^{\top}(\bm{\Phi}{\bm{\Phi}}^{\top})^{-1}(\bm{y}-\bm{\Phi}\bm{v}^{k}).$
(2.17)

  * •

Updating $\bm{v}$: After the projection, the goal of the next step is to bring
$\bm{x}^{(k+1)}$ closer to the desired signal domain. This could be achieved
by employing an appropriate trained denoiser $\mathcal{D}_{k+1}$ and letting

$\displaystyle\bm{v}^{(k+1)}=\mathcal{D}_{k+1}(\bm{x}^{(k+1)}).$ (2.18)

Derivation of Eq. 2.17: given $\bm{v}^{k}$, how to obtain the Euclidean
projection of $\bm{v}^{k}$ on the linear manifold? Since the Euclidean
projection is essentially finding the shortest distance between ${{\bf
M}}:\bm{y}=\bm{\Phi}\bm{x}$ and $\bm{v}$, this problem can be modeled as

$\displaystyle\begin{aligned}
\mathop{\arg\min}_{\bm{x}}\frac{1}{2}||\bm{x}-\bm{v}||_{2}^{2},&\quad(minimize\
the\ distance\ between\ \bm{x}\ and\ \bm{v})\\\ s.t.\
\bm{\Phi}\bm{x}=\bm{y}.&\quad(ensure\ finding\ the\ point\ \bm{x}\ on\ {{\bf
M}}\ nearest\ to\ \bm{v})\end{aligned}$ (2.19)

Easily we could get the Lagrangian function of Eq. 2.19 by introducing an
parameters $\lambda$,

$\displaystyle
L(\bm{x},\lambda)=\frac{1}{2}||\bm{x}-\bm{v}||_{2}^{2}+\lambda(\bm{\Phi}\bm{x}-\bm{y}).$
(2.20)

Then the optimal conditions of Eq. 2.20 are:

$\displaystyle\frac{\partial}{\partial\bm{x}}L(\bm{x},\lambda)=(\bm{x}-\bm{v})+\bm{\Phi}^{\top}\lambda=0,$
(2.21)
$\displaystyle\frac{\partial}{\partial\lambda}L(\bm{x},\lambda)=\bm{\Phi}\bm{x}-\bm{y}=0.$
(2.22)

According to Eq. 2.21, we have $\bm{x}=\bm{v}-\bm{\Phi}^{\top}\lambda$,
combined with $\bm{\Phi}\bm{x}=\bm{y}$, we could get

$\displaystyle\begin{aligned}
&\bm{\Phi}(\bm{v}-\bm{\Phi}^{\top}\lambda)=\bm{y}\\\
\Rightarrow\quad&\bm{\Phi}\bm{v}-\bm{\Phi}\bm{\Phi}^{\top}\lambda=\bm{y}\\\
\Rightarrow\quad&-\bm{\Phi}\bm{\Phi}^{\top}\lambda=\bm{y}-\bm{\Phi}\bm{v}\\\
\Rightarrow\quad&\lambda=-(\bm{\Phi}\bm{\Phi}^{\top})^{-1}(\bm{y}-\bm{\Phi}\bm{v}).\end{aligned}$
(2.23)

Combining $\lambda=-(\bm{\Phi}\bm{\Phi}^{\top})^{-1}(\bm{y}-\bm{\Phi}\bm{v})$
with $\bm{x}=\bm{v}-\bm{\Phi}^{\top}\lambda$, we could get

$\displaystyle\bm{x}^{(k+1)}=\bm{v}^{k}+\bm{\Phi}^{\top}(\bm{\Phi}\bm{\Phi}^{\top})^{-1}(\bm{y}-\bm{\Phi}\bm{v}^{k}).$
(2.24)

##  Chapter 3 Deep Equilibrium Models

###  3.1 Review of Deep Learning based Algorithms

Given the masks and measurements, plenty of algorithms including conventional
optimizationLiu et al., (2018); Yang et al., (2015, 2014); Yuan, (2016), end-
to-end deep learning Qiao et al., (2020); Zheng et al., (2021); Wang et al.,
(2022); Cheng et al., (2022); Meng and Yuan, (2021), deep unfolding Meng et
al., (2020); Wu et al., (2021) and plug-and-play Yuan et al., (2020, 2021); Wu
et al., (2022); Yang and Zhao, (2022) are proposed for reconstruction.

To accommodate the state-of-the-art SCI architectures and to enable low-memory
stable reconstruction, this chapter sets about utilizing deep equilibrium
models (DEQ) Bai et al., (2019) for solving the inverse problem of video SCI.
Specifically, we applied DEQ to two existing models for video SCI
reconstruction: recurrent neural networks (RNN) and plug-and-play framework
(PnP).

Given measurement $\bm{y}\in{\mathbb{R}}^{n}$ with compression rate $B$ and
sensing matrix $\bm{\Phi}\in{\mathbb{R}}^{n\times nB}$ as input, we consider
an optimization iteration or neural network as:

$\displaystyle\bm{x}^{(k+1)}=f_{\theta}(\bm{x}^{(k)};\bm{y},\bm{\Phi}),\quad
k=0,1,\dots,\infty,$ (3.1)

where $\theta$ denotes the weights of embedded neural networks;
$\bm{x}^{(k)}\in{\mathbb{R}}^{nB}$ is the output of the $k^{th}$ iterative
step or hidden layer, and $\bm{x}^{(0)}=\mathbf{\bm{\Phi}}^{\top}\bm{y}$;
$f_{\theta}(\cdot\ ;\bm{y},\bm{\Phi})$ is an iteration map
${\mathbb{R}}^{nB}\rightarrow{\mathbb{R}}^{nB}$ towards a stable equilibrium:

$\displaystyle\lim_{k\rightarrow+\infty}\bm{x}^{(k)}$
$\displaystyle=\lim_{k\rightarrow+\infty}f_{\theta}(\bm{x}^{(k)};\bm{y},\bm{\Phi})$
$\displaystyle\equiv\hat{\bm{x}}=f_{\theta}(\hat{\bm{x}};\bm{y},\bm{\Phi}),$
(3.2)

where $\hat{\bm{x}}\in{\mathbb{R}}^{nB}$ denotes the fixed point and
reconstruction result.

In following sections, we design different $f_{\theta}$ for SCI, in terms of
the implicit infinite-depth RNN architecture and infinitely iterative PnP
framework. Following Zhao et al., (2022); Gilton et al., (2021), we utilize
Anderson acceleration Walker and Ni, (2011) to compute the fixed point of
$f_{\theta}$ efficiently in Sec. 3.2. Following Zhao et al., (2022); Gilton et
al., (2021), for gradient calculation, we optimize the network wights $\theta$
by approximating the inverse Jacobian, described in Sec. 3.3. Convergence of
this scheme for specific $f_{\theta}$ designs is discussed in Sec. 3.4.

###  3.2 Forward Pass

Unlike the conventional optimization method where the terminal step number is
manually chosen or a network where the output is the activation from the
limited layers, the result of DEQ is the equilibrium point itself. Therefore,
the forward evaluation could be any procedure that solves for this equilibrium
point. Considering SCI reconstruction, we design novel iterative models that
converge to equilibrium.

####  3.2.1 Recurrent Neural Networks

To achieve integration of DEQ and RNN for video SCI, we have:

$\displaystyle\bm{x}^{(k+1)}={\rm
RNN}_{\theta}(\bm{x}^{(k)},\bm{y},\bm{\Phi}),$ (3.3)

where ${\rm RNN}(\cdot\ )$ is a trainable RNN network learning to iteratively
reconstruct effective and stable data. As shown in Fig 3.1, the corresponding
iteration map is:

$\displaystyle f_{\theta}(\bm{x};\bm{y},\bm{\Phi})={\rm
RNN}_{\theta}(\bm{x},\bm{y},\bm{\Phi}).$ (3.4)

Figure 3.1: Illustration of our proposed DEQ for SCI using recurrent neural
network (RNN), i.e., DE-RNN.

####  3.2.2 Generalized Alternating Projection

Regarding the optimization iterations in the GAP method, represented in Eq.
(2.17)-(2.18), we iteratively update $\bm{x}$ by:

$\displaystyle\bm{x}^{(k+1)}=\textstyle\mathcal{D}^{(k+1)}_{\theta}\left[\bm{x}^{(k)}+{\bm{\Phi}}^{\top}(\bm{\Phi}{\bm{\Phi}}^{\top})^{-1}(\bm{y}-\bm{\Phi}\bm{x}^{(k)})\right].$
(3.5)

Therefore, as illustrated in Fig. 3.2, the iteration map is:

$\displaystyle
f_{\theta}(\bm{x};\bm{y},\bm{\Phi})=\textstyle\mathcal{D}_{\theta}(\bm{x}+{\bm{\Phi}}^{\top}(\bm{\Phi}{\bm{\Phi}}^{\top})^{-1}(\bm{y}-\bm{\Phi}\bm{x})).$
(3.6)

Figure 3.2: Illustration of our proposed DEQ for SCI using generalized
alternating projection (GAP), i.e., DE-GAP.

####  3.2.3 Anderson Acceleration

To enforce fixed-point iterations converge more quickly, we make full use of
the ability to accelerate inference with standard fixed-point accelerators,
e.g., Anderson accelerator. Anderson acceleration utilizes previous iterations
to seek promising directions to move forward. Under the setting of Anderson
accelerator, we identify a vector $\bm{\alpha}^{(k)}\in\mathbb{R}^{s}$, for
$\delta>0$:

$\displaystyle\begin{aligned}
\bm{x}^{(k+1)}=&\textstyle(1-\delta)\sum_{i=0}^{s-1}\mathbf{\bm{\alpha}}_{i}^{(k)}\bm{x}^{(k-i)}\\\
&+\textstyle\delta\sum_{i=0}^{s-1}\mathbf{\bm{\alpha}}_{i}^{(k)}f_{\theta}(\bm{x}^{(k-i)};\bm{y},\bm{\Phi}),\end{aligned}$
(3.7)

where the vector $\mathbf{\bm{\alpha}}_{i}^{(k)}$ is the solution to the
optimization problem:

$\displaystyle\textstyle\operatorname*{arg\,min}_{\mathbf{\bm{\alpha}}}||{\bf
A}\bm{\alpha}||_{2}^{2},\quad s.t.\quad\mathbf{1}^{\top}\bm{\alpha}=1,$ (3.8)

where ${\bf A}$ is a matrix whose $i$-th column is the vectorized residual
$f_{\theta}(\bm{x}^{(k-i)};\bm{y},\bm{\Phi})-\bm{x}^{(k-i)}$, with
$i=0,\dots,s-1$. When $s$ is small (e.g., $s=3$), the optimization problem in
Eq. (3.8) introduces trivial computation.

###  3.3 Backward Pass

While previous work often utilizes Newton’s method to achieve the equilibrium
and then backpropagate through all the Newton iterations, following Zhao et
al., (2022); Gilton et al., (2021), we alternatively adopt another method with
high efficiency and constant memory requirement.

####  3.3.1 Loss Function

To optimize network parameters $\theta$, stochastic gradient descent is used
to minimize a loss function as follows:

$\displaystyle\textstyle\theta^{*}=\operatorname*{arg\,min}_{\theta}\frac{1}{m}\sum_{i=1}^{m}\ell(f_{\theta}(\hat{\bm{x}}_{i};\bm{y}_{i},\bm{\Phi}_{i}),\bm{x}^{\star}_{i}),$
(3.9)

where $m$ is the number of training samples; $\ell(\cdot,\cdot)$ is a given
loss function, $\bm{x}^{\star}_{i}$ is the ground truth 3D data of the $i$-th
training sample, $\bm{y}_{i}$ is the paired measurement, $\bm{\Phi}_{i}$
denotes the sensing matrix, and
$f_{\theta}(\hat{\bm{x}}_{i};\bm{y}_{i},\bm{\Phi}_{i})$ denotes the
reconstruction result given as the fixed point $\hat{\bm{x}}$ of the iteration
map $f_{\theta}(\cdot\ ;\bm{y},\bm{\Phi})$, as derived from Eq. (3.2). The
mean-squared error (MSE) loss is used for our video SCI reconstruction:

$\displaystyle\textstyle\ell(\hat{\bm{x}},\bm{x}^{\star})=\frac{1}{2}||\hat{\bm{x}}-\bm{x}^{\star}||_{2}^{2}.$
(3.10)

Since the reconstruction result is a fixed point of the iteration map
$f_{\theta}(\cdot\ ;\bm{y},\bm{\Phi})$, gradient calculation of this loss term
could be designed to avoid large memory demand. Following Gilton et al.,
(2021), we calculate the gradient of the loss term, which takes the network
parameters $\theta$ into consideration.

####  3.3.2 Gradient Calculation

Following Zhao et al., (2022); Gilton et al., (2021), we calculate the loss
gradient. Let $\ell$ be an abbreviation of $\ell(\hat{\bm{x}},\bm{x}^{\star})$
in Eq. (3.10), then the loss gradient is:

$\displaystyle\begin{aligned}
\textstyle\frac{\partial\ell}{\partial\theta}&={\left(\frac{\partial\hat{\bm{x}}}{\partial\theta}\right)}^{\top}\frac{\partial\ell}{\partial\hat{\bm{x}}}&={\left(\frac{\partial\hat{\bm{x}}}{\partial\theta}\right)}^{\top}{\left(\hat{\bm{x}}-\bm{x}^{\star}\right)},\end{aligned}$
(3.11)

where $\frac{\partial\hat{\bm{x}}}{\partial\theta}$ is the Jacobian of
$\hat{\bm{x}}$ evaluated at $\theta$, and
$\frac{\partial\ell}{\partial\hat{\bm{x}}}$ is the gradient of $\ell$
evaluated at $\bm{x}^{\star}$.

Then to compute the Jacobian $\frac{\partial\hat{\bm{x}}}{\partial\theta}$, we
recall the fixed point equation
$\hat{\bm{x}}=f_{\theta}(\hat{\bm{x}};\bm{y},\bm{\Phi})$ in Eq. (3.2). By
implicitly differentiating both sides of this fixed point equation, the
Jacobian $\frac{\partial\hat{\bm{x}}}{\partial\theta}$ is solved as:

$\displaystyle\textstyle\frac{\partial\hat{\bm{x}}}{\partial\theta}=\left[\bm{I}-\left.\frac{\partial
f_{\theta}(\bm{x};\bm{y},\bm{\Phi})}{\partial\bm{x}}\right|_{\bm{x}=\hat{\bm{x}}}\right]^{-1}\frac{\partial
f_{\theta}(\hat{\bm{x}};\bm{y},\bm{\Phi})}{\partial\theta},$ (3.12)

which could be plugged into Eq. (3.11) and thus get:

$\displaystyle\begin{aligned}
\textstyle\frac{\partial\ell}{\partial\theta}=\left[\frac{\partial
f_{\theta}(\hat{\bm{x}};\bm{y},\bm{\Phi})}{\partial\theta}\right]^{\top}\\!{\left[\bm{I}-\left.\frac{\partial
f_{\theta}(\bm{x};\bm{y},\bm{\Phi})}{\partial\bm{x}}\right|_{\bm{x}=\hat{\bm{x}}}\right]^{-\top}}{(\hat{\bm{x}}-\bm{x}^{\star})},\end{aligned}$
(3.13)

where -⊤ denotes the inversion followed by transpose. As this method converted
gradient calculation to the problem of calculating an inverse Jacobian-vector
product, it avoids the backpropagation through many iterations of
$f_{\theta}(\hat{\bm{x}};\bm{y},\bm{\Phi})$. To approximate the inverse
Jacobian-vector product, we define the vector $\bm{a}^{(\infty)}$ as:

$\displaystyle\textstyle\bm{a}^{(\infty)}={\left[\bm{I}-\left.\frac{\partial
f_{\theta}(\bm{x};\bm{y},\bm{\Phi})}{\partial\bm{x}}\right|_{\bm{x}=\hat{\bm{x}}}\right]^{-\top}}\\!{(\hat{\bm{x}}-\bm{x}^{\star})}.$
(3.14)

Following Gilton et al., (2021), it is noted that $\bm{a}^{(\infty)}$ is a
fixed point of the equation:

$\displaystyle\begin{aligned}
\bm{a}^{(k+1)}=\textstyle{\left[\left.\frac{\partial
f_{\theta}(\bm{x};\bm{y},\bm{\Phi})}{\partial\bm{x}}\right|_{\bm{x}=\hat{\bm{x}}}\right]^{-\top}}\bm{a}^{(k)}+{(\hat{\bm{x}}-\bm{x}^{\star})},\\\
\forall k=0,1,\dots,\infty.\end{aligned}$ (3.15)

Therefore, the same algorithm used to calculate the fixed point $\hat{\bm{x}}$
could also be used to calculate $\bm{a}^{(\infty)}$ . The limit of fixed-point
iterations for solving Eq. (3.15) with initial iterate
$\bm{a}^{(0)}=\mathbf{0}$ is denoted equivalently to the Neumann series:

$\displaystyle\bm{a}^{(\infty)}=\textstyle\sum_{p=0}^{\infty}\left\\{{\left[\left.\frac{\partial
f_{\theta}(\bm{x};\bm{y},\bm{\Phi})}{\partial\bm{x}}\right|_{\bm{x}=\hat{\bm{x}}}\right]^{\top}}\right\\}^{p}\\!{(\hat{\bm{x}}-\bm{x}^{\star})}.$
(3.16)

To quickly calculate the vector-Jacobian products in Eq. (3.15) and Eq.
(3.16), a lot of auto-differentiation tools (e.g., autograd packages in
PytorchPaszke et al., (2019)) could be utilized. After the accurate
approximation of $\bm{a}^{(\infty)}$ is calculated, the gradient in Eq. (3.11)
is given by:

$\displaystyle\textstyle\frac{\partial\ell}{\partial\theta}={\left(\frac{\partial
f_{\theta}(\hat{\bm{x}};\bm{y},\bm{\Phi})}{\partial\theta}\right)}^{\top}\bm{a}^{(\infty)}.$
(3.17)

###  3.4 Convergence Theory

Given the iteration map $f_{\theta}(\cdot\
;\bm{y},\bm{\Phi}):{\mathbb{R}}^{nB}\rightarrow{\mathbb{R}}^{nB}$, in this
section, we discuss conditions that guarantee the convergence of the proposed
deep equilibrium models
$\bm{x}^{(k+1)}=f_{\theta}(\bm{x}^{(k)};\bm{y},\bm{\Phi})$ to a fixed-point
$\hat{\bm{x}}$ as $k\rightarrow\infty$.

(Convergence of DE-RNN). For all $\bm{x},\bm{x}^{\prime}\in{\mathbb{R}}^{nB}$,
if there exists a constant $0\leq c<1$ satisfies that:

$\displaystyle\|{\rm RNN}_{\theta}(\bm{x},\bm{y},\bm{\Phi})-{\rm
RNN}_{\theta}(\bm{x}^{\prime},\bm{y},\bm{\Phi})\|\leq
c\|\bm{x}-\bm{x}^{\prime}\|,$ (3.18)

then the DE-RNN iteration map $f_{\theta}(\bm{x};\bm{y},\bm{\Phi})$ is
contractive.

(Convergence of DE-GAP). For all $\bm{x},\bm{x}^{\prime}\in{\mathbb{R}}^{nB}$,
if there exists a $\varepsilon>0$ such that the denoiser
$\mathcal{D_{\theta}}:{\mathbb{R}}^{nB}\rightarrow{\mathbb{R}}^{nB}$
satisfies:

$\displaystyle\|(\mathcal{D}_{\theta}-{\bf
I})(\bm{x})-(\mathcal{D}_{\theta}-{\bf
I})(\bm{x}^{\prime})\|\leq\varepsilon||\bm{x}-\bm{x}^{\prime}||,$ (3.19)

where $(\mathcal{D}_{\theta}-{\bf
I})(\bm{x}):=\mathcal{D}_{\theta}(\bm{x})-\bm{x}$, that is, we assume the map
$\mathcal{D}_{\theta}-{\bf I}$ is $\varepsilon$-Lipschitz, then the DE-GAP
iteration map $f_{\theta}(\cdot;\bm{y},\bm{\Phi})$ defined in Eq. (3.6)
satisfies:

$\displaystyle\textstyle\|f_{\theta}(\bm{x};\bm{y},\bm{\Phi})-f_{\theta}(\bm{x}^{\prime};\bm{y},\bm{\Phi})\|\leq\eta\|\bm{x}-\bm{x}^{\prime}\|$
(3.20)

for all $\bm{x},\bm{x}^{\prime}\in{\mathbb{R}}^{nB}$. The coefficient $\eta$
is less than 1, in which case the DE-GAP iteration map
$f_{\theta}(\bm{x};\bm{y},\bm{\Phi})$ is contractive.

Following Gilton et al., (2021), to prove $f_{\theta}(\cdot;\bm{y},\bm{\Phi})$
is contractive it suffices to show
$||\partial_{\bm{x}}f_{\theta}(\bm{x};\bm{y},\bm{\Phi})||<1$ for all
$\bm{x}\in{\mathbb{R}}^{nB}$, where $||\cdot||$ denotes the spectral norm,
$\partial_{\bm{x}}f_{\theta}(\bm{x};\bm{y},\bm{\Phi})$ is the Jacobian of
$f_{\theta}(\bm{x};\bm{y},\bm{\Phi})$ with respect to
$\bm{x}\in{\mathbb{R}}^{nB}$ given by:

$\displaystyle\partial_{\bm{x}}f_{\theta}(\bm{x};\bm{y},\bm{\Phi})$
$\displaystyle=\partial_{\bm{x}}\mathcal{D_{\theta}}(\bm{x})({\bf
I}-{\bm{\Phi}}^{\top}(\bm{\Phi}{\bm{\Phi}}^{\top})^{-1}\bm{\Phi}),$ (3.21)

where $\partial_{\bm{x}}\mathcal{D_{\theta}}\in{\mathbb{R}}^{nB\times nB}$ is
the Jacobian of
$\mathcal{D_{\theta}}:{\mathbb{R}}^{nB}\rightarrow{\mathbb{R}}^{nB}$ with
respect to $\bm{x}\in{\mathbb{R}}^{nB}$.

Finally, we derive (details can be found in Zhao, (2022) or supplementary
material):

$\displaystyle\begin{aligned}
||\partial_{\bm{x}}f_{\theta}(\bm{x};\bm{y},\bm{\Phi})||=&\
||\partial_{\bm{x}}\mathcal{D_{\theta}}(\bm{x})({\bf I}-\bm{\Psi})||,\\\ =&\
||\partial_{\bm{x}}\mathcal{D_{\theta}}(\bm{x})-\partial_{\bm{x}}\mathcal{D_{\theta}}(\bm{x})\bm{\Psi}||\\\
=&\ ||\partial_{\bm{x}}\mathcal{D_{\theta}}(\bm{x})-{\bf I}+{\bf
I}-\partial_{\bm{x}}\mathcal{D_{\theta}}(\bm{x})\bm{\Psi}||\\\ \leq&\
||\partial_{\bm{x}}\mathcal{D_{\theta}}(\bm{x})-{\bf I}||+||{\bf
I}-\partial_{\bm{x}}\mathcal{D_{\theta}}(\bm{x})\bm{\Psi}||\\\ \leq&\
\varepsilon+1+||(\partial_{\bm{x}}\mathcal{D_{\theta}}(\bm{x})-{\bf I}+{\bf
I})\bm{\Psi}||\\\ =&\
1+\varepsilon+||(\partial_{\bm{x}}\mathcal{D_{\theta}}(\bm{x})-{\bf
I})\bm{\Psi}+\bm{\Psi}||\\\ \leq&\
1+\varepsilon+||(\partial_{\bm{x}}\mathcal{D_{\theta}}(\bm{x})-{\bf
I})\bm{\Psi}||+||\bm{\Psi}||\\\ \leq&\
1+\varepsilon+\varepsilon||\bm{\Psi}||+||\bm{\Psi}||\\\ =&\
(1+\varepsilon)(1+||\bm{\Psi}||)\\\
\leq&\textstyle(1+\varepsilon)\max_{i}|1-\lambda_{i}|,\end{aligned}$ (3.22)

where $\lambda_{i}$ are eigenvalues of
${\bm{\Phi}}^{\top}(\bm{\Phi}{\bm{\Phi}}^{\top})^{-1}\bm{\Phi}$; and the
inequality Eq. (3.22) is based on the assumption that the map
$(\mathcal{D}_{\theta}-{\bf I})(\bm{x}):=\mathcal{D}_{\theta}(\bm{x})-\bm{x}$
is $\varepsilon$-Lipschitz. Therefore the spectral norm of its Jacobian
$\partial_{\bm{x}}\mathcal{D_{\theta}}(\bm{x})-{\bf I}$ is bounded by $\eta$,
which demonstrates $f_{\theta}$ is $\eta$-Lipschitz with
$\eta=(1+\varepsilon)\max_{i}|1-\lambda_{i}|$.

It is worth noting that convergence is not yet guaranteed in our calculation
above since $\eta$ is larger than 1. In SCI cases, it is challenging to
provide a theoretical guarantee. However, we observe our models converge well
in the experiments.

## References

  * Bai et al., (2019) Bai, S., Kolter, J. Z., and Koltun, V. (2019).  Deep equilibrium models.  arXiv preprint arXiv:1909.01377.
  * Cheng et al., (2022) Cheng, Z., Chen, B., Lu, R., Wang, Z., Zhang, H., Meng, Z., and Yuan, X. (2022).  Recurrent neural networks for snapshot compressive imaging.  IEEE Transactions on Pattern Analysis and Machine Intelligence.
  * Gilton et al., (2021) Gilton, D., Ongie, G., and Willett, R. (2021).  Deep equilibrium architectures for inverse problems in imaging.  arXiv preprint arXiv:2102.07944.
  * Liu et al., (2018) Liu, Y., Yuan, X., Suo, J., Brady, D. J., and Dai, Q. (2018).  Rank minimization for snapshot compressive imaging.  IEEE transactions on pattern analysis and machine intelligence, 41(12):2990–3006.
  * Meng et al., (2020) Meng, Z., Jalali, S., and Yuan, X. (2020).  Gap-net for snapshot compressive imaging.  arXiv preprint arXiv:2012.08364.
  * Meng and Yuan, (2021) Meng, Z. and Yuan, X. (2021).  Perception inspired deep neural networks for spectral snapshot compressive imaging.  In 2021 IEEE International Conference on Image Processing (ICIP), pages 2813–2817. IEEE.
  * Paszke et al., (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. (2019).  Pytorch: An imperative style, high-performance deep learning library.  Advances in neural information processing systems, 32:8026–8037.
  * Qiao et al., (2020) Qiao, M., Meng, Z., Ma, J., and Yuan, X. (2020).  Deep learning for video compressive sensing.  APL Photonics, 5(3):030801.
  * Walker and Ni, (2011) Walker, H. F. and Ni, P. (2011).  Anderson acceleration for fixed-point iterations.  SIAM Journal on Numerical Analysis, 49(4):1715–1735.
  * Wang et al., (2022) Wang, L., Cao, M., Zhong, Y., and Yuan, X. (2022).  Spatial-temporal transformer for video snapshot compressive imaging.  arXiv preprint arXiv:2209.01578.
  * Wu et al., (2022) Wu, Z., Yang, C., Su, X., and Yuan, X. (2022).  Adaptive deep pnp algorithm for video snapshot compressive imaging.  arXiv preprint arXiv:2201.05483.
  * Wu et al., (2021) Wu, Z., Zhang, J., and Mou, C. (2021).  Dense deep unfolding network with 3d-cnn prior for snapshot compressive imaging.  arXiv preprint arXiv:2109.06548.
  * Yang et al., (2015) Yang, J., Liao, X., Yuan, X., Llull, P., Brady, D. J., Sapiro, G., and Carin, L. (2015).  Compressive sensing by learning a Gaussian mixture model from measurements.  IEEE Transaction on Image Processing, 24(1):106–119.
  * Yang et al., (2014) Yang, J., Yuan, X., Liao, X., Llull, P., Sapiro, G., Brady, D. J., and Carin, L. (2014).  Video compressive sensing using Gaussian mixture models.  IEEE Transaction on Image Processing, 23(11):4863–4878.
  * Yang and Zhao, (2022) Yang, Q. and Zhao, Y. (2022).  Revisit dictionary learning for video compressive sensing under the plug-and-play framework.  In Seventh Asia Pacific Conference on Optics Manufacture and 2021 International Forum of Young Scientists on Advanced Optical Manufacturing (APCOM and YSAOM 2021), volume 12166, pages 2018–2025. SPIE.
  * Yuan, (2016) Yuan, X. (2016).  Generalized alternating projection based total variation minimization for compressive sensing.  In 2016 IEEE International Conference on Image Processing (ICIP), pages 2539–2543. IEEE.
  * Yuan et al., (2020) Yuan, X., Liu, Y., Suo, J., and Dai, Q. (2020).  Plug-and-play algorithms for large-scale snapshot compressive imaging.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR).
  * Yuan et al., (2021) Yuan, X., Liu, Y., Suo, J., Durand, F., and Dai, Q. (2021).  Plug-and-play algorithms for video snapshot compressive imaging.  IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 1–1.
  * Zhao, (2022) Zhao, Y. (2022).  Mathematical cookbook for snapshot compressive imaging.  arXiv preprint arXiv:2202.07437.
  * Zhao et al., (2022) Zhao, Y., Zheng, S., and Yuan, X. (2022).  Deep equilibrium models for video snapshot compressive imaging.  arXiv preprint arXiv:2201.06931.
  * Zheng et al., (2021) Zheng, S., Wang, C., Yuan, X., and Xin, H. L. (2021).  Super-compression of large electron microscopy time series by deep compressive sensing learning.  Patterns, 2(7):100292.


# FullStop: Punctuation and Segmentation Prediction for Dutch with
Transformers

Vincent Vandeghinste∗<EMAIL_ADDRESS>
Oliver Guhr†<EMAIL_ADDRESS>
∗Instituut voor de Nederlandse Taal, Leiden, the Netherlands and Centre for
Computational Linguistics, Leuven.AI, KU Leuven, Belgium †Hochschule für
Technik und Wirtschaft, Dresden, Germany

###### Abstract

When applying automated speech recognition (ASR) for Belgian Dutch (?), the
output consists of an unsegmented stream of words, without any punctuation. A
next step is to perform segmentation and insert punctuation, making the ASR
output more readable and easy to manually correct. As far as we know there is
no publicly available punctuation insertion system for Dutch that functions at
a usable level.

The model we present here is an extension of the models of ? for Dutch and is
made publicly available.111https://huggingface.co/oliverguhr/ We trained a
sequence classification model, based on the Dutch language model RobBERT (?).
For every word in the input sequence, the models predicts a punctuation marker
that follows the word. We have also extended a multilingual model, for cases
where the language is unknown or where code switching applies.

When performing the task of segmentation, the application of the best models
onto out of domain test data, a sliding window of 200 words of the ASR output
stream is sent to the classifier, and segmentation is applied when the system
predicts a segmenting punctuation sign with a ratio above threshold. Results
show to be much better than a machine translation baseline approach.

##  1 Introduction

Language is primarily a spoken medium, as every human society has a fully
functioning spoken language, and until some hundred years ago, only relatively
few societies had a written language, accessible to only a small class of
people (?).

In order to study properties of language performance, linguists can use
corpora, and in order to study properties of spoken language, speech corpora
are often used. A written transcript of the speech used in these corpora,
aligned at the word or sentence/utterance level increases the usability of
these corpora as they facilitate search and analysis of the contents.

Manual transcription of speech corpora is a very costly process and is
therefore often unavailable. Automated speech recognition (ASR) can provide a
cheap, albeit imperfect, solution, by providing a rough transcript. Manual
transcription can then be redefined as a post-editing process on the output of
the ASR system. For Belgian Dutch spoken data we can use the relatively recent
ASR system developed by ?.

As shown in Figure 1, incoming Belgian Dutch speech is recognized by an ASR
system, resulting in a transcript consisting of a stream of words with time
stamps (not shown in Figure 1), but without any segmentation (into sentences
or utterances) or punctuation. While this already makes it possible to search
for the occurrence of specific words in the speech, the streams have a low
readability because of the lack of segmentation.

The FullStop model for Dutch provides a punctuation and segmentation
prediction system, that consists of two steps:

  1. 1.

A sliding window of 200 words slides over the input text that needs to be
segmented. Per window the system checks how often segmenting punctuation is
predicted. If this relative frequency is above a threshold $\theta$, then the
predicted punctuation is accepted and segmentation is applied as well.
Increasing $\theta$ will result in a higher precision at the price of a lower
recall. We have two experimental conditions with respect to the set of
segmenting punctuation $S$: only the full stop ($S=\\{.\\}$), and the full
stop and the question mark ($S=\\{.,?\\}$).

  2. 2.

This step takes as input the 200 words from the previous step and segments it
in batches of up to 512 tokens. This is necessary since the used transformer-
based models are limited to 512 tokens input length. The model predicts for
every token whether it is followed by a punctuation sign that is part of $P=$
{:-,?.0}, where $0$ indicates that the classifier predicts that no punctuation
follows.

Together, these two steps apply the classifier of step 2 onto every sliding
window of 200 words, implying that we get a maximum of 200 punctuation
predictions per word, depending on in how many sliding windows the word
appears. The ratio of predictions of a certain punctuation should be above
$\theta$ before it is accepted.

Figure 1: An incoming sound is recognized with an ASR system, resulting in a
stream of words. The FullStop approach, presented in this paper, segments this
stream of words in segments, by predicting punctuation.

One type of speech corpora that particularly motivates this study is the
preprocessing of multimedia corpora, consisting of video and speech. Video is
becoming an increasingly popular means of communication, with 300 hours of
video being uploaded to YouTube every
minute,222https://fortunelords.com/youtube-statistics/ and TikTok becoming
ever more popular. It therefore makes sense that the creation of video corpora
becomes more important. Audio transcription of these video corpora is often
the first step, and the usage of ASR helps in the transcription process. There
are two video corpora that motivate the current research:

  1. 1.

The Spoken Academic Belgian Dutch corpus, and

  2. 2.

The Belgian Federal COVID-19 Sign language (BeCoS) corpus.

#### Spoken Academic Belgian Dutch (SABeD)

The first corpus is the Spoken Academic Belgian Dutch (SABeD)
corpus,333https://www.arts.kuleuven.be/ling/language-education-
society/projects/sabed which is currently under development. The SABeD project
is an interdisciplinary research project which develops a corpus of spoken
academic Belgian Dutch consisting of at least 200 lectures.

Lectures are typical of higher education. In lectures students learn new
course content in a language register they are not familiar with, viz.
academic Dutch. The SABeD project will

  * •

compile a corpus of spoken academic Belgian Dutch;

  * •

investigate the effectiveness of ASR for automatic transcription of spoken
texts;

  * •

create a word frequency list of spoken academic Belgian Dutch and

  * •

develop a vocabulary test of spoken academic Belgian Dutch.

The corpus is mainly based on video lectures of academic teaching to first-
year bachelor students. These videos are, as a positive consequence of the
COVID-19 pandemic, abundantly available. The lectures contain content in a
language register students are not familiar with, viz. academic dutch. The
corpus will serve as a source to develop representative study and test
material on academic language. Furthermore, it can also serve as a source for
linguistic research and a tool to optimize the language policy of higher
education institutions. It will allow us to create study material and tests
for international students and will be an important tool for researchers,
language support and policy makers.

An additional aim is the improvement of Belgian Dutch ASR through the creation
of a spoken Dutch corpus with manually transcribed (or corrected) speech.
Based on these manual transcriptions the ASR system of ? will be retrained to
improve fully automated transcriptions at a later stage so the corpus can be
expanded efficiently. Once ready, the corpus will be made freely available for
research through the Dutch Language Institute and the CLARIN Virtual Language
Observatory.444https://vlo.clarin.eu

In order to speed up the transcription process, the first step consists of
applying ASR. As a second step, human transcribers edit and correct the ASR
output. A tool that provides manual transcription functionality is ELAN (?).
ELAN is an annotation tool for audio and video recordings and supports the
creation of multiple tiers of annotation. We integrate the ASR output into
ELAN by converting the automatically recognized words and associated time
stamps into an ELAN tier. The human editor can easily adapt the content of the
tier, but the unit of annotation in the tier is the word, as this is the unit
of output of the ASR system. This is not the most convenient unit for manual
transcription, due to the fact that ASR errors often lead to errors over the
word boundaries. Human editors would have to make changes over several units
and adapt unit boundaries (to keep the alignment with the audio/video), which
is quite a time-consuming task in ELAN. A much more convenient unit to work
with is the sentence or utterance level. The model described in this paper
provides a way to segment the ASR output stream into appropriate segments,
usable for human annotation.

Within the SABeD corpus we are not going to provide manually corrected
transcripts for the entire videos, but limit these to the first 25 minutes and
the last 5 minutes, to keep the data set balanced, irrespective of the length
of the videos. The rest of the video corpus will be released with fully
automatic transcripts (and fully automatic segmentation).

#### The Belgian Federal COVID-19 Sign language (BeCoS) corpus

The second corpus that motivates the described punctuation and segmentation
approach is the BeCoS corpus, the Belgian federal COVID-19 Sign language video
corpus. This corpus is extensively described in ?, and is developed within the
SignON project.555https://www.signon-project.eu/ SignON is a user-centric and
community-driven project that aims to facilitate the exchange of information
among Deaf, hard of hearing and hearing individuals across Europe, targeting
the Irish, British, Dutch, Flemish and Spanish sign as well as the English,
Irish, Dutch and Spanish spoken languages.

One of the bottlenecks for developing machine translation (MT) systems between
sign languages and spoken/written languages is the lack of parallel data. The
BeCoS corpus addresses this issue. It consists of 220 press conferences of the
Belgian Federal Government concerning the COVID-19 pandemic, totalling 178
hours of speech. These press conferences were live interpreted into sign
language: when speech was in Dutch, the sign language was Vlaamse GebarenTaal
(VGT, Flemish Sign Language), when speech was in French, the sign language was
Langue des Signes de Belgique Francophone (LSFB, Belgian Francophone Sign
Language). The Dutch-VGT part of the data can serve as a parallel corpus for
training a machine translation engine from VGT to Dutch or vice versa.

The speech in this corpus is unscripted, and manual transcription is currently
unattainable. As MT engines commonly are trained on parallel data at the
sentence level, the corpus requires a sentence-like segmentation, which is
attained by the models proposed in this paper.

Segmenting transcriptions generated by ASR systems has an application in voice
user interfaces as well. We developed the first FullStop model to segment
multi sentence user statements into single statements. The goal was to process
the sentences of users’ utterances individually. This is important as typical
text classification models can only classify the users’ intention, e.g a
command, reliably if the input text does not contain multiple intentions.

***

Section 2 presents related work. Section 3 describes the data sets we used and
how they were processed, section 4 presents the models, and section 5 first
describes an experimental evaluation as a classifier, then performs a
qualitative discussion on some system output, and ends with showing results on
full stop prediction on out of domain data, using the sliding window on
continuous text streams. The final section, section 6 concludes the paper.

##  2 Related Work

? provides an extensive survey of what they call punctuation restoration,
making a distinction between methods that only use lexical features and
methods that include audio specific features. As we work on the recognition
output of the ASR, we do not consider the latter.

Within the methods with lexical features, there are the early rule-based
approaches and bootstrapping approaches that extract rules from large corpora,
such as ?. There are also the $n$-gram approaches, such as ? for sentence
boundary detection. Conditional random fields are used by Lu and Ng (2010)
amongst others. Character-level recurrent neural networks have been used by ?.
? approach the punctuation restoration problem as a bidirectional recurrent
neural network with attention model.

? lists other sources of punctuation/segmentation research. ? constitutes a
rather traditional approach to spelling and punctuation correction for Arabic.
Classification is carried out with Support Vector Machines and Conditional
Random Field (CRF) classifiers, using part-of-speech and morphological
information, and obtains an F1-score of 0.56, with the CRF classifier and a
window size of five tokens.

? experiments with different neural network architectures, using pretrained
GloVe embeddings (?) as inputs. It evaluates its models on ASR transcripts of
TED talks, predicting commas, periods, and question marks. Its best result in
this 4-class classification is an F1 -score of 0.54.

? works in the clinical domain on the output of medical ASR systems. It
jointly models punctuation and truecasing by predicting a punctuation sequence
and then the case of each input word. It uses a pretrained transformer model
in combination with subword embeddings to overcome lexical sparsity in the
medical domain. It carries out a fine-tuning step on medical data and a task
adaptation step, randomly masking punctuation marks, before training the
actual model. Predicting full stops and commas, it achieves F1 -scores of 0.81
(for commas) and 0.92 (for full stops) with Bio-BERT (?), which was trained on
biomedical corpora.

Previous work on multilingual punctuation prediction is described in ? and ?.

? models punctuation prediction in the context of speech translation, but also
investigates a monolingual approach for Dutch, modelling punctuation
prediction as a machine translation problem, in which the source language is
the text without punctuation, and the target language is the text with
punctuation. It shows that a neural MT approach that uses LSTM cells works
much better than a language modelling approach using LSTMs, scoring on in
domain data for the punctuation set $P=\\{.,?!:;()/-\\}$ an $F_{1}$ of 0.82.
We have used this approach, but now using a transformer model, as a baseline
in the experiments in section 5.3. A statistical MT approach using Moses (?)
is shown to work at least equally well, with $F_{1}=0.83$.

In 2021 there was the shared task in Sentence End and Punctuation Prediction
in NLG Text (SEPP-NLG) (?),666https://sites.google.com/view/sentence-
segmentation which consisted of two subtasks:

  1. 1.

Fully unpunctuated sentences - full stop detection: Given the textual content
of an utterance where the full stops are fully removed, correctly detect the
end of sentences by placing a full stop in appropriate positions.

  2. 2.

Fully unpunctuated sentences - full punctuation marks: Given the textual
content of an utterance where all punctuation marks are fully removed,
correctly predict all punctuation marks.

? modelled this task as a token-wise prediction and examined several language
models based on the transformer architecture. They trained two separate models
for the two tasks and submitted their results for all four languages of the
shared task, reaching state-of-the-art F-scores. They advocated transfer
learning for solving the task and showed that the multilingual transformer
models yielded better results than monolingual models. It is this approach
that is taken in the current paper, and which is applied and evaluated on
Dutch.

For the SEPP-NLG task ? also evaluated a CRF based model and found that this
approach was outperformed by transformer based models. A GRU based model was
submitted by (?) for the shared task. This model scored 10 to 20 percent
points lower $F_{1}$ scores than the best transformer based models. For these
reasons we did not consider RNN based models or more classical ML approaches
for this work.

##  3 Data

To finetune our models we experimented with two different data sets: Europarl
(?) and SoNaR (?).

#### Europarl data set (EP)

contains transcribed plenary sessions of the European Parliament. For our
models we used the Europarl v8 data, to be analogous with the other languages
in the model. The text was extracted from the data downloads from OPUS (?).

#### SoNaR data set

contains texts from different genres and domains in standard Dutch that have
been written after 1954. The data was obtained from the SoNaR
website.777http://hdl.handle.net/10032/tm-a2-h5 We found that SoNaR contains a
number of artefacts like HTML code that can lead to issues when processing
this data set.

For out of domain evaluation, as described in sections 5.2 and 5.3, we make
use of the OpenSubtitles data888http://www.opensubtitles.org/ for Dutch, as
made available on OPUS (?). OpenSubtitles is a large database of movie and TV
subtitles. We chose this data as it mainly contains translations of spoken
language.

#### Data Preprocessing

Data was split at the sentence level and tokenized at the word level using the
Moses corpus preprocessing tools included in the Moses3.0 distribution (?).
All data was truecased, as the ASR output is also truecased. The data was then
converted into a tab-separated format, where the first column contains the
word, the second column contains a 0 if the word is not followed by a full
stop and a 1 if the word is followed by a full stop (to allow for binary
classification as sentence segmentation), and the third column contains a 0 if
the word is not followed by punctuation but contains the punctuation sign if
it is followed by it. An example is given in Table 1. This format is
consistent with the format used in the shared task on Sentence End and
Punctuation Prediction in NLG Text (SEPP-NLG 2021) held at SwissText (Swiss
Text Analytics Conference) in 2021.

For both data sets we split the data into 75% training data and 25% test data.
For the SoNaR data set we needed to downsample the training data to 1 GB, due
to limited computing resources.

… |  |
---|---|---
doos | 0 | 0
van | 0 | 0
pandora | 0 | 0
zouden | 0 | 0
openen | 0 | .
hoe | 0 | 0
… |  |
op | 0 | 0
de | 0 | 0
volgende | 0 | 0
vraag | 0 | :
kunnen | 0 | 0
… |  |
Table 1: Sepp format for text … doos van pandora zouden openen. hoe … op de
volgende vraag: kunnen …

##  4 The Models

Transformers (?) and combining transformers with transfer learning (?) have
led to performance gains for many different NLP tasks.

The first model we present here is an extension for Dutch of the models of ?.

We trained a token classification model, based on the Dutch language model
RobBERT (?). We also trained a Dutch model based on BERTje (?), but found that
RobBERT slightly outperformed BERTje with a 0.75% better $F_{1}$ score. For
every token in the input sequence, the model predicts a punctuation marker
that follows the token. The model is trained to predict punctuation marks of
the set $P=\\{:-,?.0\\}$, with 0 indicating that the word is not followed by a
marker. We finetuned several variants of this model on the two different
datasets. These variants are shown in Table 2.

Transformer models can only process sequences of a fixed length, typically 512
tokens. Therefore we implemented a sliding window approach to process the
documents in our data set, which are typically longer than 512 tokens. The
simplest method to achieve that is by splitting the text into chunks of 200
words before processing. The number of 200 words was chosen empirically to
account for the fact that words get tokenized into more than one token
(subword tokenization). With this method, it is important to leave some
headroom since some words get decomposed into multiple tokens. This problem is
more prominent in languages that allow compound words, such as Dutch.

We choose to train a multilingual model for this work as well. A multilingual
model can simplify the data processing in mixed language scenarios. In our
previous work (?) we found that multilingual models perform on par and in some
cases, like Italian, significantly better than monolingual models. We wanted
to investigate if this is the case for the Dutch language as well and trained
a model on Dutch, English, German, French, and Italian texts. For the
multilingual model, we used ”xlm-roberta-base” (?). We previously evaluated a
list of current language models and gained the best results using XLM Roberta
in multilingual settings.

We choose to use the same hyper-parameters that we evaluated in our previous
work. This hyper-parameters search included the optimiser algorithm, learning
rate, random initialisation seed. All models were trained for 3 epochs using
Adafactor (?) and a learning rate of $4e^{-5}$ with a batch size of 8 and 16
as the seed. Furthermore we used 16-bit-precision training to improve training
and inference efficiency.

As explained in section 3, for our experiments we used two different data
sets: Europarl (?) and SoNaR (?). We trained one model for each data set, as
well as a multilingual model on Dutch, English, German, French, and Italian
sentences from the Europarl data set. For this model we used about 400 MB of
data per language. Lastly we tested a combination of all available data from
the SoNaR and Europarl data set. For this model the Dutch data set was
downsampled to be on par with the other languages and contains 200 MB of
Europarl and 200 MB of SoNaR data. Table 2 provides an overview of the trained
models.

Model Name | Data Set | Base Model
---|---|---
Monolingual Europarl | Nl EuroParl | RobBERT
Monolingual SoNaR | Nl SoNaR | RobBERT
Multilingual EP | Nl, En, Fr, De, It Europarl | xlm-roberta-base
Multilingual EP+SoNaR | Nl, En, Fr, De, It Europarl + Nl SoNaR | xlm-roberta-base
Table 2: The list of data set and model combinations that we evaluated for
this work.

The models described here are made available on
HuggingFace.999https://huggingface.co/oliverguhr/ We also provide a high level
software library to simplify the usage of the
models.101010https://github.com/oliverguhr/deepmultilingualpunctuation

##  5 Experimental Results

In section 5.1 we describe the evaluations of different variants of the model,
evaluated as a multiclass classifier. Section5.2 shows some qualitative
evaluation. Section 5.3 describes how the model performs on out-of-domain
data.

###  5.1 Evaluation as a classifier

Table 3 compares the per class $F_{1}$ scores for each model on the test set
of the corresponding data set it was trained on. Tables with the precision and
recall values are presented in the Appendix. The overall macro and micro
averaged $F_{1}$ scores are in the same range for every model. There are more
pronounced differences for certain classes. Question marks and full stops for
models including SoNaR data have 10 to 13 percentage points lower scores than
models trained on Europarl without SoNaR. We assume the reason for this is
that the SoNaR data set contains more diverse data and more noise (e.g. HTML
code) than Europarl and is, therefore, harder to learn for the model.

Label/Model | EP | SoNaR | Multilingual EP | Multilingual EP + SoNaR
---|---|---|---|---
0 | 0.994 | 0.986 | 0.994 | 0.987
. | 0.961 | 0.855 | 0.959 | 0.854
, | 0.811 | 0.721 | 0.813 | 0.723
? | 0.849 | 0.687 | 0.817 | 0.671
- | 0.462 | 0.723 | 0.464 | 0.613
: | 0.655 | 0.697 | 0.657 | 0.709
macro $F_{1}$ | 0.789 | 0.778 | 0.784 | 0.760
micro $F_{1}$ | 0.983 | 0.964 | 0.983 | 0.965
Table 3:  Per class $F_{1}$ scores for the FullStop models on the Dutch test
data sets. For detailed evaluation results of each model and per class
precision and recall metrics please see the appendix.

Table 3 also shows that the multilingual Europarl model improved the $F_{1}$
scores in every class over its monolingual version. Part of this improvements
can be explained by the fact that XLM-Roberta base uses more than twice as
many parameters than RobBERT. Note that it is not possible to compare the
performance of the other models directly, since models using the SoNaR data
set in Table 3 where trained and tested on different data sets. Therefore we
compared the models using an out of domain data set in section 5.3.

(a) Monolingual Europarl

(b) Monolingual SoNaR

(c) Multilingual EP

(d) Multilingual EP+SoNaR

Figure 2: Confusion matrices for Dutch language for the FullStop models. Note
that all values are rounded.

Figure 2 shows a confusion matrix for the Dutch language for every trained
model. Models trained on Europarl tend to confuse dashes with commas. SoNaR
based models predict 14% to 18% of the colons and question marks as 0 or no
punctuation mark. All models predict 10% to 25% of the colons and question
marks with full stops. This is to be expected, as colons are more stylistic
markers and there are no strict usage rules. Overall the Dutch language
results are in line with English, French, German and Italian language
predictions from our previous work.

Furthermore we compared the performance of the different languages that both
multilingual model where trained on, in Tables 4 and 5. We think these models
are useful in scenarios where users mix languages or the source language is
unknown, for example in social media posts. The evaluation results of the
multilingual Europarl model (Table 4) are comparable between all five
languages. We see an overall drop in Dutch language performance for the
multilingual model using both Europarl and SoNaR data in Table 5. This is to
be expected, as the SoNaR data set is more diverse. The results of the other
four languages remain the same for both models.

For efficiency reasons we choose to train XLM-Roberta base instead of large
models. Comparing the results from Tables 4 and 5 with the finetuned
multilingual model from our previous work, we estimate that a size ”large”
model could improve the macro $F_{1}$ by 5%. However, XLM-Roberta large models
use more than twice as many parameters as base models, with 550 million
parameters compared to 270 million.

Label | EN | DE | FR | IT | NL
---|---|---|---|---|---
0 | 0.990 | 0.996 | 0.991 | 0.988 | 0.994
. | 0.924 | 0.951 | 0.921 | 0.917 | 0.959
, | 0.798 | 0.937 | 0.811 | 0.778 | 0.813
? | 0.825 | 0.829 | 0.800 | 0.736 | 0.817
- | 0.345 | 0.384 | 0.353 | 0.344 | 0.464
: | 0.535 | 0.608 | 0.578 | 0.544 | 0.657
macro $F_{1}$ | 0.736 | 0.784 | 0.742 | 0.718 | 0.784
micro $F_{1}$ | 0.975 | 0.987 | 0.977 | 0.972 | 0.983
Table 4:  Per class $F_{1}$ scores of the multilingual Europarl model. Tested on English, German, French, Italian and Dutch language on the test data set.  Label | EN | DE | FR | IT | NL
---|---|---|---|---|---
0 | 0.990 | 0.996 | 0.991 | 0.988 | 0.987
. | 0.924 | 0.950 | 0.921 | 0.917 | 0.854
, | 0.797 | 0.937 | 0.810 | 0.778 | 0.723
? | 0.823 | 0.826 | 0.802 | 0.731 | 0.671
- | 0.349 | 0.380 | 0.359 | 0.348 | 0.613
: | 0.533 | 0.606 | 0.576 | 0.541 | 0.709
macro $F_{1}$ | 0.736 | 0.783 | 0.743 | 0.717 | 0.760
micro $F_{1}$ | 0.975 | 0.987 | 0.977 | 0.972 | 0.965
Table 5:  Per class $F_{1}$ scores of the multilingual Europarl + SoNaR model.
Tested on English, German, French, Italian and Dutch language data on the test
set.

###  5.2 Qualitative Evaluation

To better understand the capabilities and the limitations of the model, we
qualitatively discuss some examples, presented in Table 6. The examples are
selected from the OpenSubtitles corpus (?).

The results that are shown are those of a single input of the words to the
classifier, so there is no effect of $\theta$ in Table 6.

We can see that the Gold strings of the examples contain different punctuation
signs, belonging to the set $P=\\{.,?\\}$.They are tokenized at the word level
and truecased. The Input strings simulate the stream of words as coming from
an ASR system, without any punctuation. The Prediction strings show the output
of the classification model, not in SEPP format, but in string format. In the
examples we have marked the inserted punctuation in the Prediction in green
where they are correct and in red when there is a mismatch (be it a deletion,
substitution or insertion) between the Prediction and the Gold version. For
ease of reference we have indexed the predicted or omitted punctuation with a
subscript.

The first example shows the stream of words that was also presented in Figure
1, but now somewhat longer. Prediction 1 is a comma where the gold standard
has a full stop. This is counted as a substitution error, but it is not an
implausible prediction and could be correct. The next 5 predictions,
containing comas and full stops, are correct. Then our model misses a full
stop at prediction 7, which may be explained by the next sentence starting
with the conjunction en. Then two more correct predictions and an omission of
a comma (10), which can be attributed to the next word being en again. As
Dutch has no Oxford comma rule, you would not necessarily expect a comma here.
In (11) the system substitutes a full stop with a comma. A comma would be
plausible at this position. (12) is a correct full stop prediction. In (13)
and (14) question marks should have been predicted, but there is nothing in
the word order that indicates that these are questions, so this information
would have to come from the intonation, which is not available to our model.
Then the system misses the final full stop (15). This may be due to the lack
of context.

The second example starts with an insertion (1) of a comma. This could be
considered correct if we would put the apposition hier between commas, as is
done often. The next comma, ending the apposition is correctly predicted. (3)
and (4) omit commas at the start of a relative phrase, which is not uncommon.
(5), (6) and (7) are correctly predicted full stops and commas. (8) is an
omitted comma before en. (9) is a correctly predicted full stop before an en.
(10) omits a comma before a subordinate clause. (11) correctly predicts the
final full stop.

From these samples we can see that the system makes several real mistakes, but
that most of the differences between the Gold version and the Predicted
version can be attributed to the fact that there are often are no strict
punctuation rules, and that the output of the system could be argumented for.
It would be interesting to see how humans would add punctuation purely based
on the input text and what the inter-annotator agreement would be, but such an
exercise is outside the scope of this paper.

Example 1 |
---|---
Gold |  kijk om je heen . alles beweegt , alles draait . zo komen wij ter wereld . de zon , de maan , de planeten en de sterren kijken toe . en wij staan in het midden . onze plaats . maar Nicolaas Copernicus kwam en stelde dat de Zon in het midden staat , en dat wij om haar heen draaien . net als de andere planeten . een Aarde die beweegt ? maar daar zien en voelen we toch niets van ? dat was 1543 .
Input |  kijk om je heen alles beweegt alles draait zo komen wij ter wereld de zon de maan de planeten en de sterren kijken toe en wij staan in het midden onze plaats maar Nicolaas Copernicus kwam en stelde dat de Zon in het midden staat en dat wij om haar heen draaien net als de andere planeten een Aarde die beweegt maar daar zien en voelen we toch niets van dat was 1543
Prediction |  kijk om je heen ,1 alles beweegt ,2 alles draait .3 zo komen wij ter wereld .4 de zon ,5 de maan ,6 de planeten en de sterren kijken toe  7 en wij staan in het midden .8 onze plaats .9 maar Nicolaas Copernicus kwam en stelde dat de Zon in het midden staat  10 en dat wij om haar heen draaien ,11 net als de andere planeten .12 een Aarde die beweegt ,13 maar daar zien en voelen we toch niets van .14 dat was 1543  15
Example 2 |
Gold |  en waar we nu zitten hier , dat is bij een fotografische kijker , die heel veel gelijkenis vertoont met de kijker , die werd gebruikt door David Gill . zo ’ n kijker moet dus in staat zijn om foto ’ s te nemen . maar als je foto ’ s neemt met die kijker , moet je natuurlijk ook een oogje houden op het stukje hemel waar hij op gericht is , en zorgen dat de kijker heel nauwkeurig de dagelijkse beweging van de hemel volgt . en daarom is zo ’ n kijker zo gebouwd , dat hij een gedeelte heeft waar de fotografische plaat zich bevindt .
Input |  en waar we nu zitten hier dat is bij een fotografische kijker die heel veel gelijkenis vertoont met de kijker die werd gebruikt door David Gill zo ’ n kijker moet dus in staat zijn om foto ’ s te nemen maar als je foto ’ s neemt met die kijker moet je natuurlijk ook een oogje houden op het stukje hemel waar hij op gericht is en zorgen dat de kijker heel nauwkeurig de dagelijkse beweging van de hemel volgt en daarom is zo ’ n kijker zo gebouwd dat hij een gedeelte heeft waar de fotografische plaat zich bevindt
Prediction |  en waar we nu zitten ,1 hier ,2 dat is bij een fotografische kijker  3 die heel veel gelijkenis vertoont met de kijker  4 die werd gebruikt door David Gill .5 zo ’ n kijker moet dus in staat zijn om foto ’ s te nemen .6 maar als je foto ’ s neemt met die kijker ,7 moet je natuurlijk ook een oogje houden op het stukje hemel waar hij op gericht is  8 en zorgen dat de kijker heel nauwkeurig de dagelijkse beweging van de hemel volgt .9 en daarom is zo ’ n kijker zo gebouwd  10 dat hij een gedeelte heeft waar de fotografische plaat zich bevindt .11
Table 6:  We generated these examples with the FullStop SoNaR model.

###  5.3 Experiments on full stop prediction on out of domain data

In this section we describe an evaluation on out of domain test data, i.e.
test data coming from OpenSubtitles, as described in section 3.

We test segmentation in two variants: with segementation set $S=\\{.\\}$ and
with segementation set $S=\\{.?\\}$.

#### Baseline

As a baseline we tested a machine translation approach, similar to
Vandeghinste et al. (2018), in which we consider texts with all punctuation
and segmentation removed as the source language and the punctuated version as
the target language.

We trained an OpenNMT (?) transformer model on a randomly resegmented version
of the SoNaR corpus complemented with the Corpus Spoken Dutch (?).
Resegmenation was random, but distributed normally with an average of 14
tokens and standard deviation of 3 tokens. These values are based on the
average length and stdev of sentences in De Standaard, according to ?. In
order to create the training data for the MT system, we removed all
punctuation in the source side, and kept the original punctuation in the
target side.

In our best model and parameter setting, such an approach reached a
segmentation prediction $F_{1}$ score of 42%, which seems not good enough for
practical usage. The low $F_{1}$ score is mostly due to low recall, as shown
in table 7.

#### Evaluation Procedure

Evaluation was performed on 1000 sentences from OpenSubtitles, and applied
with a sliding window of size 200. For every sequence of 200 words we checked
where the system inserted an element of $S$. We accept a segmentation if the
element of $S$ is predicted in more than $\theta$ of all cases. We tried
different $\theta$ values, but a $\theta=0.1$ setting seemed to provide the
best results.

#### Results

Table 7 shows the results for the different models we trained. It is clear
that the current models present a major improvement over the baseline MT
apprach. The best $F_{1}$-score for this evaluation seems to be the
monolingual model trained on SoNaR only. This may be due to the fact that
SoNaR contains different registers, amongst which some more colloquial forms
of Dutch, that may be closer to the subtitles register than the data from
Europarl. Note that the multilingual models also have good scores and an even
higher precision than the monolingual models. There is also a clear
improvement when using $S=\\{.?\\}$ as set of segmenters over just using
$S=\\{.\\}$.

Model | $S$ | Precision | Recall |  $F_{1}$-score
---|---|---|---|---
Baseline ONMT | $\\{.\\}$ | 0.7187 | 0.2986 | 0.4219
FullStop EP | $\\{.\\}$ | 0.8939 | 0.7609 | 0.8221
FullStop SoNaR | $\\{.\\}$ | 0.8734 | 0.8750 | 0.8742
FullStop Multilingual | $\\{.\\}$ | 0.9010 | 0.7719 | 0.8314
FullStop Multilingual EP+SoNaR | $\\{.\\}$ | 0.9021 | 0.7915 | 0.8424
FullStop EP | $\\{.?\\}$ | 0.8962 | 0.8193 | 0.8561
FullStop SoNaR | $\\{.?\\}$ | 0.8749 | 0.9380 | 0.9053
FullStop Multilingual | $\\{.?\\}$ | 0.9013 | 0.8330 | 0.8658
FullStop Multilingal EP+Sonar | $\\{.?\\}$ | 0.9040 | 0.8504 | 0.8764
Table 7: Evaluation results on out of domain data

At this point, we are interested in the significance levels: do the models
differ significantly or not, and what is the 95% confidence interval?

Condition | Characteristics | 95% Conf.
---|---|---
| Model | $\theta$ | $S$ | Median | Average | Std dev | Lo | Hi
A | SoNaR | 0.1 | $\\{.\\}$ | 0.7975 | 0.7785 | 0.0818 | 0.5918 | 0.8567
B | SoNaR | 0.2 | $\\{.\\}$ | 0.7933 | 0.7746 | 0.0820 | 0.5882 | 0.8540
C | SoNaR | 0.3 | $\\{.\\}$ | 0.7892 | 0.7705 | 0.0821 | 0.5841 | 0.8505
D | SoNaR | 0.1 | $\\{.?\\}$ | 0.8812 | 0.8611 | 0.0839 | 0.6802 | 0.9308
Table 8: Characteristics of the distribution of $F_{1}$ scores over 10000 test
files

#### Multiple testfiles

In order to determine whether the F-scores between the $S=\\{.?\\}$ condition
and the $S=\\{.\\}$ condition, or the scores for different $\theta$ values
differ significantly, we have tested the SoNaR model, which was the best
scoring model in Table 7 on 10000 test sets of each 1000 sentences. These test
sets were created by splitting up the OpenSubtitle file into sections of 1000
lines each.

Per condition, we have evaluated these 10000 test sets, ranked the $F_{1}$
scores and taken the score at rank 251 and at rank 9750 as the values of the
95% confidence interval.

Table 8 lists the main characteristics of the $F_{1}$ scores for the different
conditions that were tested on the 10000 evaluation files.

The difference between Condition A and Condition D has a p-value of 0.0981, so
it is significant at the $p<.10$ level. Difference between Condition B and D
is not significant ($p=0.100801$). Difference between C and D has a
$p=0.091266$.

The effect of the $\theta$ parameter is not significant, but the effect of
adding the question mark to $S$ is mildly significant at the $p<.10$ level.

Figure 3: Distribution of $F_{1}$ scores over 10000 test files. The blue curve
shows the distribution of using $\\{.\\}$ as a segmentation marker. The red
curve shows the distribution when using $\\{.?\\}$ as segmentation markers.

Figure 3 presents a visualisation of the distribution of the $F_{1}$ scores
for the two different $S$ conditions, which shows clearly that $S=\\{.?\\}$
scores better than only $S=\\{.\\}$.

##  6 Conclusions

We have presented several models that perform punctuation prediction and
evaluated them in different settings. We have made various models specifically
for Dutch, but have also extended the multilingual model from ? with Dutch.
The models use transfer learning from large pretrained models and are
finetuned as per token classifiers.

The models are evaluated as classifiers, reaching a similar accuracy as for
the other languages, and they have also been tested on out-of-domain data, on
which they present a great improvement over a baseline MT model.

The best models are publicly available through
Huggingface.111111https://huggingface.co/oliverguhr. The use of the model to
actually predict segmentation on a stream of text, as used in the out-of-
domain evaluation is made available on
Github.121212https://github.com/VincentCCL/Segment_FullStop

For future work, it would make sense to predict different sets of tokens. As
for now, we have taken the set of tokens as defined in the shared task.
Training a classifier just for the prediction of segmentation, punctuation
signs in set $S=\\{.?!\\}$ or for the prediction of all non-alphanumeric
characters would be possible. The model could also be extended to predict the
segmentation tokens and the true case of every word in the sequence. This is a
common use case in processing the output of automatic speech recognition
systems.

Another line of work would be to make a lighter version of the model, with
fewer parameters, through knowledge distillation which is quicker in
inference.

All in all, we can conclude that the model we present provides a usable and
practical way of inserting punctuation into streams of words, and therefore
turning a sequence of words into a text. The SoNaR model came out as the best
model and will therefore serve this purpose in further processing of the SABeD
corpus and has been used in processing of the BeCoS corpus.

##  7 Acknowledgements

Work in this paper is partly financed by the SignON
project.131313https://signon-project.eu This project has received funding from
the European Union’s Horizon 2020 Research and Innovation Programme under
Grant Agreement No. 101017255. The SABeD project is funded by KU Leuven
Internal Funding, Research Project 3H200610.

Oliver Guhr has been funded by the European Social Fund (ESF), SAB grant
number 100339497 and the European Regional Development Funds (ERDF)
(ERDF-100346119).

## References

  * [1] [] Aronoff, M. (2007), Language (linguistics), Scholarpedia 2 (5), pp. 3175.  revision #121088.
  * [2] [] Attia, Mohammed, Mohamed Al-Badrashiny, and Mona Diab (2014), GWU-HASP: Hybrid Arabic spelling and punctuation corrector, Proceedings of the EMNLP 2014 Workshop on Arabic Natural Language Processing (ANLP), Association for Computational Linguistics, Doha, Qatar, pp. 148–154.  https://aclanthology.org/W14-3620.
  * [3] [] Che, Xiaoyin, Cheng Wang, Haojin Yang, and Christoph Meinel (2016), Punctuation prediction for unsegmented transcript based on word vector, Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16), European Language Resources Association (ELRA), Portorož, Slovenia, pp. 654–658.  https://aclanthology.org/L16-1103.
  * [4] [] Conneau, Alexis, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov (2020), Unsupervised cross-lingual representation learning at scale, Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, Association for Computational Linguistics, Online, pp. 8440–8451.  https://aclanthology.org/2020.acl-main.747.
  * [5] [] de Vries, Wietse, Andreas van Cranenburgh, Arianna Bisazza, Tommaso Caselli, Gertjan van Noord, and Malvina Nissim (2019), Bertje: A dutch bert model.  https://arxiv.org/abs/1912.09582.
  * [6] [] Delobelle, Pieter, Thomas Winters, and Bettina Berendt (2020), RobBERT: a Dutch RoBERTa-based Language Model, Findings of the Association for Computational Linguistics: EMNLP 2020, Association for Computational Linguistics, Online, pp. 3255–3265.  https://aclanthology.org/2020.findings-emnlp.292.
  * [7] [] Devlin, Jacob, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova (2019), BERT: Pre-training of deep bidirectional transformers for language understanding, Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), Association for Computational Linguistics, Minneapolis, Minnesota, pp. 4171–4186.  https://aclanthology.org/N19-1423.
  * [8] [] Guerreiro, Nuno Miguel, Ricardo Rei, and Fernando Batista (2021), Towards better subtitles: A multilingual approach for punctuation restoration of speech transcripts, Expert Systems with Applications 186, pp. 115740, Elsevier.
  * [9] [] Guhr, Oliver, Anne-Kathrin Schumann, Frank Bahrmann, and Hans-Joachim Böhme (2021), FullStop: Multilingual Deep Models for Punctuation Prediction, Swiss Text Analytics Conference. Shared task on Sentence End and Punctuation Prediction in NLG Text.
  * [10] [] Klein, Guillaume, Yoon Kim, Yuntian Deng, Jean Senellart, and Alexander Rush (2017), OpenNMT: Open-source toolkit for neural machine translation, Proceedings of ACL 2017, System Demonstrations, Association for Computational Linguistics, Vancouver, Canada, pp. 67–72.  https://aclanthology.org/P17-4012.
  * [11] [] Koehn, Philipp (2005), Europarl: A parallel corpus for statistical machine translation, Proceedings of Machine Translation Summit X: Papers, Phuket, Thailand, pp. 79–86.  https://aclanthology.org/2005.mtsummit-papers.11.
  * [12] [] Koehn, Philipp, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondřej Bojar, Alexandra Constantin, and Evan Herbst (2007), Moses: Open source toolkit for statistical machine translation, Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics Companion Volume Proceedings of the Demo and Poster Sessions, Association for Computational Linguistics, Prague, Czech Republic, pp. 177–180.  https://aclanthology.org/P07-2045.
  * [13] [] Lee, Jinhyuk, Wonjin Yoon, Sungdong Kim, Donghyeon Kim, Sunkyu Kim, Chan Ho So, and Jaewoo Kang (2019), BioBERT: a pre-trained biomedical language representation model for biomedical text mining, Bioinformatics 36 (4), pp. 1234–1240.  https://doi.org/10.1093/bioinformatics/btz682.
  * [14] [] Li, Xinxing and Edward Lin (2020), A 43 language multilingual punctuation prediction neural network model., INTERSPEECH, pp. 1067–1071.
  * [15] [] Lison, Pierre and Jörg Tiedemann (2016), OpenSubtitles2016: Extracting large parallel corpora from movie and TV subtitles, Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16), European Language Resources Association (ELRA), Portorož, Slovenia, pp. 923–929.  https://aclanthology.org/L16-1147.
  * [16] [] Masiello-Ruiz, Jose Manuel, José Luis López Cuadrado, and Paloma Martínez (2021), Participation of hulat-uc3m in sepp-nlg 2021 shared task (short paper), Swiss Text Analytics Conference. Shared task on Sentence End and Punctuation Prediction in NLG Text.
  * [17] [] Oostdijk, N., M. Reynaert, V. Hoste, and I. Schuurman (2013), ”the construction of a 500 million word reference corpus of contemporary written dutch”, Essential Speech and Language Technology for Dutch: Results by the STEVIN-programme, Springer Verlag.
  * [18] [] Oostdijk, Nelleke, Wim Goedertier, Frank van Eynde, Louis Boves, Jean-Pierre Martens, Michael Moortgat, and Harald Baayen (2002), Experiences from the spoken Dutch corpus project, Proceedings of the Third International Conference on Language Resources and Evaluation (LREC’02), European Language Resources Association (ELRA), Las Palmas, Canary Islands - Spain.  http://www.lrec-conf.org/proceedings/lrec2002/pdf/98.pdf.
  * [19] [] Păiş, Vasile and Dan Tufiş (2022), Capitalization and punctuation restoration: a survey, Artificial Intelligence Review 55 (3), pp. 1681–1722, Springer.
  * [20] [] Pennington, Jeffrey, Richard Socher, and Christopher Manning (2014), GloVe: Global vectors for word representation, Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), Association for Computational Linguistics, Doha, Qatar, pp. 1532–1543.  https://aclanthology.org/D14-1162.
  * [21] [] Petasis, Georgios, Frantz Vichot, Francis Wolinski, Georgios Paliouras, Vangelis Karkaletsis, and Constantine D. Spyropoulos (2001), Using machine learning to maintain rule-based named-entity recognition and classification systems, Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics, Association for Computational Linguistics, Toulouse, France, pp. 426–433.  https://aclanthology.org/P01-1055.
  * [22] [] Shazeer, Noam and Mitchell Stern (2018), Adafactor: Adaptive learning rates with sublinear memory cost, in Dy, Jennifer and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, Vol. 80 of Proceedings of Machine Learning Research, PMLR, pp. 4596–4604.
  * [23] [] Stolcke, A. and E. Shriberg (1996), Automatic linguistic segmentation of conversational speech, Proceeding of Fourth International Conference on Spoken Language Processing. ICSLP ’96, Vol. 2, pp. 1005–1008 vol.2.
  * [24] [] Sunkara, Monica, Srikanth Ronanki, Kalpit Dixit, Sravan Bodapati, and Katrin Kirchhoff (2020), Robust prediction of punctuation and truecasing for medical ASR, Proceedings of the First Workshop on Natural Language Processing for Medical Conversations, Association for Computational Linguistics, Online, pp. 53–62.  https://aclanthology.org/2020.nlpmc-1.8.
  * [25] [] Susanto, Raymond Hendy, Hai Leong Chieu, and Wei Lu (2016), Learning to capitalize with character-level recurrent neural networks: An empirical study, Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, Association for Computational Linguistics, Austin, Texas, pp. 2090–2095.  https://aclanthology.org/D16-1225.
  * [26] [] Tiedemann, Jörg (2012), Parallel data, tools and interfaces in OPUS, Proceedings of the Eighth International Conference on Language Resources and Evaluation (LREC’12), European Language Resources Association (ELRA), Istanbul, Turkey, pp. 2214–2218.  http://www.lrec-conf.org/proceedings/lrec2012/pdf/463_Paper.pdf.
  * [27] [] Tilk, Ottokar and Tanel Alumäe (2016), Bidirectional recurrent neural network with attention mechanism for punctuation restoration, INTERSPEECH.
  * [28] [] Tuggener, Don and Ahmad Aghaebrahimian (2021), The Sentence End and Punctuation Prediction in NLG Text (SEPP-NLG) Shared Task 2021, Proceedings of the Swiss Text Analytics Conference 2021.
  * [29] [] Van Dyck, Bob, Bagher BabaAli, and Dirk Van Compernolle (2021), A Hybrid ASR System for Southern Dutch, Computational Linguistics in the Netherlands Journal 11, pp. 27–34.  https://clinjournal.org/clinj/article/view/119.
  * [30] [] Vandeghinste, Vincent and Bram Bulté (2019), Linguistic proxies of readability: Comparing easy-to-read and regular newspaper dutch, Computational Linguistics in the Netherlands Journal 9, pp. 81–100.  https://www.clinjournal.org/clinj/article/view/97.
  * [31] [] Vandeghinste, Vincent, Bob Van Dyck, Mathieu De Coster, and Maud Goddefroy (2022), BeCoS corpus: Belgian Covid-19 Sign language corpus. A corpus for training Sign Language Recognition and Translation, Computational Linguistics in the Netherlands Journal.
  * [32] [] Vandeghinste, Vincent, Lyan Verwimp, Joris Pelemans, and Patrick Wambacq (2018), A comparison of different punctuation prediction approaches in a translation context, Proceedings of the 21st Annual Conference of the European Association for Machine Translation: 28-30 May 2018, Universitat d’Alacant, Alacant, Spain, European Association for Machine Translation, pp. 269–278.
  * [33] [] Vaswani, Ashish, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin (2017), Attention is all you need.  https://arxiv.org/abs/1706.03762.
  * [34] [] Wittenburg, Peter, Hennie Brugman, Albert Russel, Alex Klassmann, and Han Sloetjes (2006), ELAN: a professional framework for multimodality research, Proceedings of the Fifth International Conference on Language Resources and Evaluation (LREC’06), European Language Resources Association (ELRA), Genoa, Italy.  http://www.lrec-conf.org/proceedings/lrec2006/pdf/_pdf.pdf.
  * [35]

## Appendix

In this appendix we present more detailed classification evaluation results,
including precision and recall.

class | precision | recall |  $F_{1}$-score | samples
---|---|---|---|---
0 | 0.992584 | 0.994595 | 0.993588 | 9627605
. | 0.960450 | 0.962452 | 0.961450 | 433554
, | 0.816974 | 0.804882 | 0.810883 | 379759
? | 0.871368 | 0.826812 | 0.848506 | 13494
- | 0.619905 | 0.367690 | 0.461591 | 27341
: | 0.718636 | 0.602076 | 0.655212 | 18305
accuracy |  |  | 0.983874 | 10500058
macro avg | 0.829986 | 0.759751 | 0.788538 | 10500058
weighted avg | 0.983302 | 0.983874 | 0.983492 | 10500058
Table 9:  Monolingual Europarl model tested on Nl EuroParl data. class | precision | recall |  $F_{1}$-score | samples
---|---|---|---|---
0 | 0.982554 | 0.989277 | 0.985904 | 73926815
. | 0.858432 | 0.852403 | 0.855407 | 4941897
, | 0.754981 | 0.689276 | 0.720634 | 3127454
? | 0.732037 | 0.646400 | 0.686558 | 410416
- | 0.849020 | 0.629105 | 0.722703 | 331849
: | 0.740604 | 0.659131 | 0.697497 | 590946
accuracy |  |  | 0.964436 | 83329377
macro avg | 0.819604 | 0.744266 | 0.778117 | 83329377
weighted avg | 0.963170 | 0.964436 | 0.963641 | 83329377
Table 10: Monolingual SoNaR model tested on Nl SoNaR. class | precision | recall |  $F_{1}$-score | samples
---|---|---|---|---
0 | 0.992625 | 0.994700 | 0.993662 | 9627605
. | 0.960790 | 0.956852 | 0.958817 | 433554
, | 0.815222 | 0.810991 | 0.813101 | 379759
? | 0.867011 | 0.772047 | 0.816778 | 13494
- | 0.657312 | 0.358070 | 0.463597 | 27341
: | 0.708049 | 0.613166 | 0.657201 | 18305
accuracy |  |  | 0.983884 | 10500058
macro avg | 0.833501 | 0.750971 | 0.783859 | 10500058
weighted avg | 0.983364 | 0.983884 | 0.983499 | 10500058
Table 11: Multilingual EP model tested on Nl Europarl data class | precision | recall |  $F_{1}$-score | samples
---|---|---|---|---
0 | 0.983286 | 0.990781 | 0.987020 | 8982463
. | 0.900062 | 0.812584 | 0.854089 | 588253
, | 0.713272 | 0.732957 | 0.722980 | 356718
? | 0.739526 | 0.614814 | 0.671428 | 59631
- | 0.727932 | 0.529030 | 0.612744 | 32828
: | 0.725112 | 0.694275 | 0.709358 | 49708
accuracy |  |  | 0.966042 | 10069601
macro avg | 0.798198 | 0.729074 | 0.759603 | 10069601
weighted avg | 0.965309 | 0.966042 | 0.965441 | 10069601
Table 12: Multilingual EP+SoNaR tested on Nl, Europarl + Nl SoNaR data.