# Optimal bounds for numerical approximations of infinite horizon problems
based on dynamic programming approach

Javier de Frutos Instituto de Investigación en Matemáticas (IMUVA),
Universidad de Valladolid, Spain. Research supported by Spanish MINECO under
grants PID2019-104141GB-I00 and VA169P20<EMAIL_ADDRESS>Julia Novo
Departamento de Matemáticas, Universidad Autónoma de Madrid, Spain. Research
supported by Spanish MINECO under grants PID2019-104141GB-I00 and VA169P20
<EMAIL_ADDRESS>
###### Abstract

In this paper we get error bounds for fully discrete approximations of
infinite horizon problems via the dynamic programming approach. It is well
known that considering a time discretization with a positive step size $h$ an
error bound of size $h$ can be proved for the difference between the value
function (viscosity solution of the Hamilton-Jacobi-Bellman equation
corresponding to the infinite horizon) and the value function of the discrete
time problem. However, including also a spatial discretization based on
elements of size $k$ an error bound of size $O(k/h)$ can be found in the
literature for the error between the value functions of the continuous problem
and the fully discrete problem. In this paper we revise the error bound of the
fully discrete method and prove, under similar assumptions to those of the
time discrete case, that the error of the fully discrete case is in fact
$O(h+k)$ which gives first order in time and space for the method. This error
bound matches the numerical experiments of many papers in the literature in
which the behaviour $1/h$ from the bound $O(k/h)$ have not been observed.

Key words. Dynamic programming, Hamilton-Jacobi-Bellman equation, optimal
control, error analysis.

##  1 Introduction

The numerical approximation of optimal control problems is of importance for
many applications such as aerospace engineering, chemical processing and
resource economics, among others. In this paper, we consider the dynamic
programming approach to the solution of optimal control problems driven by
dynamical systems in $\mathbb{R}^{n}$. We refer to [7] for a monograph on this
subject.

The value function of an optimal control problem is known to be usually only
Lipschitz continuous even when the data is regular. The characterization of
the value function is obtained in terms of a first-order nonlinear Hamilton-
Jacobi-Bellman (HJB) partial differential equation. A bottleneck in the
computation of the value function comes from the need of approaching a
nonlinear partial differential equation in dimension $n$, which is a
challenging problem in high dimensions. Several approximation schemes have
been proposed in the literature, ranging from finite differences to semi-
Lagrangian and finite volume methods, see e.g. [4], [1], [10], [3]. Some of
these algorithms converge to the value function but their convergence is slow.
The curse of dimensionality is mitigated in [6], [2] by means of a reduced-
order model based on proper orthogonal decomposition. A new accelerated
algorithm which can produce an accurate approximation of the value function in
a reduced amount of time in comparison to other available methods is
introduced in [5].

In the present paper, our concern is about the error bounds available in the
literature for the fully discrete semi-lagrangian method approaching the value
function, the viscosity solution of the HJB equation corresponding to the
infinite horizon. For a method with a positive time step size $h$ and spatial
elements of size $k$ an error bound of size $O(k/h)$ can be found in [8,
Corollary 2.4], [9, Theorem 1.3]. However, the behaviour $1/h$ in the error
bound of the fully discrete method has never been observed in the numerical
experiments, see for example [6]. Based on this fact, we reconsider the error
analysis of the fully discrete method.

In this paper we prove a bound of size $O(h+k)$ which gives first order in
time and space for the method. The idea is to imitate the analysis of the
semi-discrete time method for which the value function is characterized as the
minimum of a functional, see [7, Proposition 4.1, Chapter VI (appendix)]. To
this end, we define a fully discrete cost functional that differs from that of
the semi-discrete case in the use of spatial interpolator operators. Then, in
Theorem 3 we prove that the fully discrete approximation can also be
characterized as the minimum of this fully discrete cost functional. In the
proof we use that the fully discrete approximation defined by means of a
discrete dynamic programming principle is unique, as it is proved in [7,
Theorem 1.1, Appendix A].

Finally, thanks to this new characterization we can extend the ideas from [7,
Lemma 1.2, Chapter VI] (for the semi-discrete case) to the fully discrete case
and we are able to prove first order of convergence for the method both is
space and time. To get first order of convergence in time we need to assume
that the controls are Lipschitz-continuous. In case we only have continuous
controls the error goes to zero as $h$ goes to zero but the first order of
convergence is not achieved.

The outline of the paper is as follows. In section 2 we state the model
problem and some preliminary results. In Section 3 we prove the error bound of
the method.

##  2 Model problem and Preliminary results

Along this section we follow the notation in [6]. For a nonlinear mapping

$f:{\mathbb{R}}^{n}\times{\mathbb{R}}^{m}\rightarrow{\mathbb{R}}^{n},$

and a given initial condition $y_{0}\in{\mathbb{R}}^{n}$ let us consider the
controlled nonlinear dynamical system

$\dot{y}(t)=f(y(t),u(t))\in{\mathbb{R}}^{n},\quad t>0,\quad
y(0)=y_{0}\in{\mathbb{R}}^{n},$ (1)

together with the infinite horizon cost functional

$J(y,u)=\int_{0}^{\infty}g(y(t),u(t))e^{-\lambda t}~{}dt.$ (2)

In (2) $\lambda>0$ is a given weighting parameter and

$g:{\mathbb{R}}^{n}\times{\mathbb{R}}^{m}\rightarrow{\mathbb{R}}.$

The set of admissible controls is

${\mathbb{U}}_{\rm ad}=\left\\{u\in{\mathbb{U}}\mid u(t)\in U_{\rm ad}\ {\rm
for}\ {\rm almost}\ {\rm all}\ t\geq 0\right\\},$

where ${\mathbb{U}}=L^{2}(0,\infty;{\mathbb{R}}^{m})$ and $U_{\rm
ad}\subset{\mathbb{R}}^{m}$ is a compact convex subset.

As in [6, Assumption 2.1] we assume the following hypotheses:

  * •

The right-hand side $f$ in (1) is continuous and globally Lipschitz-continuous
in both the first and second arguments; i.e., there exists a constant
$L_{f}>0$ satisfying

$\displaystyle\|f(y,u)-f(\tilde{y},u)\|_{2}$ $\displaystyle\leq$
$\displaystyle L_{f}\|y-\tilde{y}\|_{2},\quad\forall
y,\tilde{y}\in{\mathbb{R}}^{n},u\in U_{\rm ad}$ (3)
$\displaystyle\|f(y,u)-f(y,\tilde{u})\|_{2}$ $\displaystyle\leq$
$\displaystyle L_{f}\|u-\tilde{u}\|_{2},\quad\forall u,\tilde{u}\in U_{\rm
ad},y\in{\mathbb{R}}^{n}.$ (4)

  * •

The right-hand side $f$ in (1) satisfies that there exists a constant
$M_{f}>0$ such that the following bound holds

$\|f(y,u)\|_{\infty}=\max_{1\leq i\leq n}|f_{i}(y,u)|\leq M_{f},\quad\forall
y\in\overline{\Omega}\subset{\mathbb{R}}^{n},u\in U_{\rm ad},$ (5)

where $\overline{\Omega}$ is a bounded polyhedron such that for sufficiently
small $h>0$ it holds

$y+hf(y,u)\in\overline{\Omega},\quad\forall y\in\overline{\Omega},u\in U_{\rm
ad}.$ (6)

  * •

The running cost $g$ is continuous and globally Lipschitz-continuous in both
the first and second arguments; i.e., there exists a constant $L_{g}>0$
satisfying

$\displaystyle|g(y,u)-g(\tilde{y},u)|$ $\displaystyle\leq$ $\displaystyle
L_{g}\|y-\tilde{y}\|_{2},\quad\forall y,\tilde{y}\in{\mathbb{R}}^{n},u\in
U_{\rm ad}$ (7) $\displaystyle|g(y,u)-g(y,\tilde{u})|$ $\displaystyle\leq$
$\displaystyle L_{g}\|u-\tilde{u}\|_{2},\quad\forall u,\tilde{u}\in U_{\rm
ad},y\in{\mathbb{R}}^{n}.$ (8)

  * •

Moreover, there exists a constant $M_{g}>0$ such that

$|g(y,u)|\leq M_{g},\quad\forall(y,u)\in\overline{\Omega}\times U_{\rm ad}.$
(9)

  * •

Finally, we make the following semiconcavity assumptions for
$(y,\tilde{y},u)\in{\mathbb{R}}^{n}\times{\mathbb{R}}^{n}\times U_{\rm ad}$

$\displaystyle\|f(y+\tilde{y},u)-2f(y,u)+f(y-\tilde{y},u)\|_{2}$
$\displaystyle\leq$ $\displaystyle C_{f}\|\tilde{y}\|_{2}^{2},$ (10)
$\displaystyle\|g(y+\tilde{y},u)-2g(y,u)+g(y-\tilde{y},u)\|_{2}$
$\displaystyle\leq$ $\displaystyle C_{g}\|\tilde{y}\|_{2}^{2}.$ (11)

Let us also assume that the controls are Lipschitz-continuous; i.e., there
exists a positive constant $L_{u}>0$ such that

$\displaystyle\|u(t)-u(s)\|_{2}\leq L_{u}|t-s|.$ (12)

From the assumptions made on $f$ there exists a unique solution of (1)
$y=y(y_{0},u)$ for every admissible control $u\in{\mathbb{U}}_{\rm ad}$ and
for every initial condition $y_{0}\in{\mathbb{R}}^{n}$, see [7, Chapter 3]. We
define the reduced cost functional as follows:

$\displaystyle\hat{J}(y_{0},u)=J(y(y_{0},u),u),\quad\forall
u\in{\mathbb{U}}_{\rm ad},\quad y_{0}\in{\mathbb{R}}^{n},$ (13)

where $y(y_{0},u)$ solves (1). Then, the optimal control can be formulated as
follows: for given $y_{0}\in{\mathbb{R}}^{n}$ we consider

$\min_{u\in{\mathbb{U}}_{\rm ad}}\hat{J}(y_{0},u).$

The value function of the problem is defined as
$v:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}$ as follows:

$v(y)=\inf\left\\{\hat{J}(y,u)\mid u\in{\mathbb{U}}_{\rm ad}\right\\},\quad
y\in{\mathbb{R}}^{n}.$ (14)

This function gives the best value for every initial condition, given the set
of admissible controls $U_{\rm ad}$. It is characterized as the viscosity
solution of the HJB equation corresponding to the infinite horizon

$\lambda v(y)+\sup_{u\in U_{\rm ad}}\left\\{-f(y,u)\cdot\nabla
v(y)-g(y,u)\right\\}=0,\quad y\in{\mathbb{R}}^{n},$ (15)

which is unique for sufficiently large $\lambda$, $\lambda>\max(L_{g},L_{f})$,
[7]. To construct the approximation scheme, as in [8], let us consider first a
time discretization where $h$ is a strictly positive step size. A dynamic
programming principle (DPP) for the discrete problem holds true given the
following semidiscrete scheme for (15):

$v_{h}(y)=\min_{u\in U_{\rm ad}}\left\\{(1-\lambda
h)v_{h}(y+hf(y,u))+hg(y,u)\right\\},\quad y\in{\mathbb{R}}^{n}.$ (16)

Under the assumptions (3), (5), (7) and (9) the function $v_{h}$ is Lipschitz-
continuous and satisfies (see [9, p. 473])

$|v_{h}(y)-v_{h}(\tilde{y})|\leq\frac{L_{g}}{\lambda-
L_{f}}\|y-\tilde{y}\|_{2},\quad\forall y,\tilde{y}\in\overline{\Omega},\
h\in[0,1/\lambda).$

The following bound for the semidiscrete approximation can be found in [8,
Theorem 2.3].

###### Theorem 1

Let assumptions (3), (5), (6), (7), (9), (10) and (11) hold and let
$\lambda>\max(2L_{g},L_{f})$. Let $v$ and $v_{h}$ be the solutions of (15) and
(16), respectively. Then, there exists a constant $C\geq 0$, that can be
bounded explicitly, such that the following bound holds

$\sup_{y\in{\mathbb{R}}^{n}}|v(y)-v_{h}(y)|\leq Ch,\quad h\in[0,1/\lambda).$
(17)

Following [8], [9] we introduce a fully discrete approximation to (15). Let
$\Omega$ a bounded polyhedron in $\mathbb{R}^{n}$ satisfying (6). Let
$\left\\{S_{j}\right\\}_{j=1}^{m_{s}}$ be a family of simplices which defines
a regular triangulation of $\Omega$

$\overline{\Omega}=\bigcup_{j=1}^{m_{s}}S_{j},\quad k=\max_{1\leq j\leq
m_{s}}({\rm diam}\ S_{j}).$

We assume we have $n_{s}$ vertices/nodes $y_{1},\ldots,y_{n_{s}}$ in the
triangulation. Let $V^{k}$ be the space of piecewise affine functions from
$\overline{\Omega}$ to ${\mathbb{R}}$ which are continuous in
$\overline{\Omega}$ having constant gradients in the interior of any simplex
$S_{j}$ of the triangulation. Then, a fully discrete scheme for the HJB
equations is given by

$v_{h,k}(y_{i})=\min_{u\in U_{\rm ad}}\left\\{(1-\lambda
h)v_{h,k}(y_{i}+hf(y_{i},u))+hg(y_{i},u)\right\\},$ (18)

for any vertex $y_{i}\in\overline{\Omega}$. Clearly, a solution to (16)
satisfies (18). There exists a unique solution of (18) in the space $V^{k}$,
see [7, Theorem 1.1, Appendix A]. The following result can be found in [8,
Corollary 2.4], [9, Theorem 1.3].

###### Theorem 2

Let assumptions (3), (5), (6), (7), (9), (10) and (11) hold. Let $v$, $v_{h}$
and $v_{h,k}$ be the solutions of (15), (16) and (18), respectively. For
$\lambda>L_{f}$ the following bound holds

$\|v_{h}-v_{h,k}\|_{C(\overline{\Omega})}\leq\frac{L_{g}}{\lambda(\lambda-
L_{f})}\frac{k}{h},\quad h\in[0,1/\lambda).$

For $\lambda>\max(2L_{g},L_{f})$ the following bound holds

$\|v-v_{h,k}\|_{C(\overline{\Omega})}\leq Ch+\frac{L_{g}}{\lambda(\lambda-
L_{f})}\frac{k}{h},\quad h\in[0,1/\lambda),$

where $C$ is the constant in (17).

As we can observe in the theorem the error bound of the fully discrete method
deteriorates when the time step $h$ tends to zero. However, this behaviour of
the method has not been observed in the literature. In next section, we
improve the bound of Theorem 2 proving that the error behaves as $O(h+k)$
which gives first order both in space and time, as expected, for a method
based on a first order discretization in time (Euler method) and a piecewise
linear approximation in space.

##  3 Optimal error bounds for the fully discrete approximations

The key point to improve the above error bounds is to use a new
characterization for the function $v_{h,k}$. The characterization is based on
the analogous characterization for the semi-discrete approximation $v_{h}$
that can be found in [7, Proposition 4.1, Chapter VI (appendix)]. Let us
define the space $\cal U$ of all sequences
$\boldsymbol{u}=\left\\{u_{0},u_{1},\ldots,\right\\}$ such that $u_{i}\in
U_{\rm ad}$ and for $\boldsymbol{u}\in{\cal U}$ let us define the following
fully discrete cost functional

$\displaystyle\hat{J}_{h,k}(y,\boldsymbol{u})$ $\displaystyle:=$
$\displaystyle
h\sum_{n=0}^{\infty}\delta_{h}^{n}I_{k}g(\hat{y}_{n},u_{n}),\quad\delta_{h}=(1-\lambda
h),$ (19) $\displaystyle\hat{y}_{n+1}$ $\displaystyle=$
$\displaystyle\hat{y}_{n}+hI_{k}f(\hat{y}_{n},u_{n}),\quad\hat{y}_{0}=y,$ (20)

where $I_{k}$ represents the linear interpolant of the function (respect to
the $y$ variable) at the nodes $y_{1},\ldots,y_{n_{s}}$.

###### Theorem 3

The function $v_{h,k}\in V^{k}$ defined by (18) satisfies

$\displaystyle v_{h,k}(y)=\inf_{\boldsymbol{u}\in{\cal
U}}\hat{J}_{h,k}(y,\boldsymbol{u}).$ (21)

###### Proof

The proof follows the argument of the proof of [7, Proposition 4.1, Chapter VI
(appendix)]. First of all, let us observe that
$\hat{J}_{h,k}(y,\boldsymbol{u})\in V^{k}$. To this end we observe that
$I_{k}g(\hat{y}_{n},u_{n})\in V^{k}$ for $n=0,1,\ldots$. In the case $n=0$,
$I_{k}g(\hat{y}_{0},u_{0})=I_{k}g(y,u_{0})$ which, by definition of $I_{k}$
belongs to $V_{k}$. For $n=1,$
$I_{k}g(\hat{y}_{1},u_{1})=I_{k}g(y+hI_{k}f(y,u_{0}),u_{1})$. Then, since
$I_{k}f(y,u_{0})\in V^{k}$ the composed function
$I_{k}g(y+hI_{k}f(y,u_{0}),u_{1})\in V^{k}$. The same argument can be applied
for any of the terms and, as a conclusion, $\hat{J}_{h,k}(y,\boldsymbol{u})\in
V^{k}$. The series that defines $J_{h,k}$ is convergent under the same
hypothesis that the series defining the semi-discrete functional $v_{h}$ is
convergent since the interpolant heritages the necesary properties of the
interpolated function.

Let us prove now the thesis of the lemma. Let us define

$w_{h,k}(y)=\inf_{\boldsymbol{u}\in{\cal U}}\hat{J}_{h,k}(y,\boldsymbol{u})\in
V^{k}.$

Let us take $\boldsymbol{u}\in{\cal U}$ and let us define
$\overline{\boldsymbol{u}}=\left\\{u_{1},u_{2},\ldots,\right\\}$. We first
observe that

$\displaystyle\hat{J}_{h,k}(y_{i},\boldsymbol{u})$ $\displaystyle=$
$\displaystyle
hI_{k}g(y_{i},u_{0})+h\sum_{n=1}^{\infty}\delta_{h}^{n}I_{k}g(\hat{y}_{n},u_{n})$
$\displaystyle=$ $\displaystyle
hg(y_{i},u_{0})+\delta_{h}\sum_{n=0}^{\infty}\delta_{h}^{n}I_{k}g(\hat{y}_{n+1},u_{n+1})$
$\displaystyle=$ $\displaystyle
hg(y_{i},u_{0})+\delta_{h}\hat{J}_{h,k}(y_{i}+hf(y_{i},u_{0}),\overline{\boldsymbol{u}}),$

where we have applied that $I_{k}g(y_{i},u_{0})=g(y_{i},u_{0})$ and that
$I_{k}f(y_{i},u_{0})=f(y_{i},u_{0})$ and the definition of $\hat{J}_{h,k}$.
Applying the definition of $w_{h,k}$ we get

$\hat{J}_{h,k}(y_{i},\boldsymbol{u})\geq
hg(y_{i},u_{0})+\delta_{h}w_{h,k}(y_{i}+hf(y_{i},u_{0})).$

And then,

$w_{h,k}(y_{i})=\inf_{\boldsymbol{u}\in{\cal
U}}\hat{J}_{h,k}(y_{i},\boldsymbol{u})\geq\inf_{\boldsymbol{u}\in{\cal
U}}\left\\{hg(y_{i},u_{0})+\delta_{h}w_{h,k}(y_{i}+hf(y_{i},u_{0}))\right\\}.$

Finally, since the right-hand side above depends only on $u_{0}$

$\inf_{\boldsymbol{u}\in{\cal
U}}\left\\{hg(y_{i},u_{0})+w_{h,k}(y_{i}+hf(y_{i},u_{0}))\right\\}=\inf_{u\in
U_{\rm ad}}\left\\{hg(y_{i},u)+\delta_{h}w_{h,k}(y_{i}+hf(y_{i},u))\right\\}$
(22)

and then

$w_{h,k}(y_{i})\geq\inf_{u\in U_{\rm
ad}}\left\\{hg(y_{i},u)+\delta_{h}w_{h,k}(y_{i}+hf(y_{i},u))\right\\}.$

Now we take any $u_{0}\in U_{\rm ad}$ and any $\epsilon>0$ and denote by
$z=y_{i}+hf(y_{i},u_{0})$. By definition of $w_{h,k}$, there exists
$\boldsymbol{u}^{\epsilon}\in{\cal U}$ such that

$w_{h,k}(z)+\epsilon\geq\hat{J}_{h,k}(z,\boldsymbol{u}^{\epsilon}).$

Let us denote by

$\boldsymbol{u}=\left\\{u_{0},\boldsymbol{u}^{\epsilon}\right\\}.$

Arguing as before, we get

$\hat{J}_{h,k}(y_{i},\boldsymbol{u})=hg(y_{i},u_{0})+\delta_{h}\hat{J}_{h,k}(z,\boldsymbol{u}^{\epsilon}).$

And then

$\hat{J}_{h,k}(y_{i},\boldsymbol{u})\leq
hg(y_{i},u_{0})+\delta_{h}w_{h,k}(y_{i}+hf(y_{i},u_{0}))+\epsilon.$

Arguing as before

$w_{h,k}(y_{i})=\inf_{\boldsymbol{u}\in{\cal
U}}\hat{J}_{h,k}(y_{i},\boldsymbol{u})\leq\inf_{\boldsymbol{u}\in{\cal
U}}\left\\{hg(y_{i},u_{0})+\delta_{h}w_{h,k}(y_{i}+hf(y_{i},u_{0}))\right\\}+\epsilon.$

And since, on the one hand, (22) holds and, on the other, the above inequality
is valid for any $\epsilon>0$ we get

$w_{h,k}(y_{i})\leq\inf_{u\in U_{\rm
ad}}\left\\{hg(y_{i},u)+\delta_{h}w_{h,k}(y_{i}+hf(y_{i},u))\right\\}.$

Then

$w_{h,k}(y_{i})=\inf_{u\in U_{\rm
ad}}\left\\{hg(y_{i},u)+\delta_{h}w_{h,k}(y_{i}+hf(y_{i},u))\right\\},$

and $w_{h,k}\in V^{k}$ but since there is a unique function in $V^{k}$ solving
(18) (see [7, Theorem 1.1, Appendix A]) we get $w_{h,k}=v_{h,k}$ which
finishes the proof of the lemma. $\Box$

###### Lemma 1

Let $\hat{J}$ and $\hat{J}_{h,k}$ be the functionals defined in (13) and (19)
respectively. Assume conditions (3), (4), (5), (7), (8), (9) and (12) hold.
Then

$\displaystyle\lim_{h\rightarrow 0,k\rightarrow
0}|\hat{J}(y_{0},u)-\hat{J}_{h,k}(y_{0},\boldsymbol{u})|=0,\quad
y_{0}\in{\mathbb{R}}^{n},$ (23)

where $u\in{\mathbb{U}}_{\rm ad}$ and
$\boldsymbol{u}=\left\\{u_{0},u_{1},\ldots,\right\\}=\left\\{u(t_{0}),u(t_{1}),\ldots,\right\\}$,
$t_{i}=ih$, $i=0,1,\ldots,$.

###### Proof

We argue similarly as in [7, Lemma 1.2, Chapter VI]. Let $y(t)$ be the
solution of (1) and let us denote by $\tilde{y}(t)=\hat{y}_{k}$, $k=[t/h]$
where $\hat{y}_{k}$ is the solution of (20) with $\hat{y}_{0}=y_{0}$. Let us
denote by

$\overline{u}(t)=u_{k}=u(t_{k}),\quad t\in[kh,(k+1)h).$

Then, $\tilde{y}$ can be expressed as

$\tilde{y}(t)=y_{0}+\int_{0}^{[t/h]h}I_{k}f(\tilde{y}(s),\overline{u}(s))~{}ds.$

And,

$\displaystyle
y(t)-\tilde{y}(t)=\int_{0}^{[t/h]h}\left(f(y(s),u(s))-I_{k}f(\tilde{y}(s),\overline{u}(s))\right)~{}ds+\int_{[t/h]h}^{t}f(y(s),u(s))~{}ds.$

From the above equation, applying (5), we get

$\displaystyle\|y(t)-\tilde{y}(t)\|_{\infty}\leq\int_{0}^{[t/h]h}\|f(y(s),u(s))-I_{k}f(\tilde{y}(s),\overline{u}(s))\|_{\infty}~{}ds+M_{f}h.$
(24)

Let us bound now the term inside the integral. Adding and subtracting terms we
get

$\displaystyle\|f(y(s),u(s))-I_{k}f(\tilde{y}(s),\overline{u}(s))\|_{\infty}\leq\|f(y(s),u(s))-f(y(s),\overline{u}(s))\|_{\infty}$
(25)
$\displaystyle\quad+\|f(y(s),\overline{u}(s))-I_{k}f(y(s),\overline{u}(s))\|_{\infty}+\|I_{k}f(y(s),\overline{u}(s))-I_{k}f(\tilde{y}(s),\overline{u}(s))\|_{\infty}.$

For the first term on the right-hand side of (25) using (4) and (12) and
assuming $s\in[kh,(k+1)h)$ we get

$\displaystyle\|f(y(s),u(s))-f(y(s),\overline{u}(s))\|_{\infty}\leq
L_{f}\|u(s)-\overline{u}(s)\|_{2}$ $\displaystyle=$ $\displaystyle
L_{f}\|u(s)-u(t_{k})\|_{2}$ (26) $\displaystyle\leq$ $\displaystyle
L_{f}L_{u}h.$

Let us observe that if we only have continuous controls instead of Lipschitz-
continuous then we get that the above term goes to zero as $h$ goes to zero
but we cannot prove first order of convergence for this term.

To bound the second term on the right-hand side of (25) arguing as in [6] we
observe that for any $y\in\overline{\Omega}$ there exists an index $l$ with
$y\in\overline{S}_{l}\subset\overline{\Omega}$. Let us denote by $J_{l}$ the
index subset such that $y_{i}\in S_{l}$ for $i\in J_{l}$. Writing

$y=\sum_{i=1}^{n_{S}}\mu_{i}y_{i},\quad 0\leq\mu_{i}\leq
1,\quad\sum_{i=1}^{n_{S}}\mu_{i}=1,$

it is clear that $\mu_{i}=0$ holds for any $i\not\in J_{l}$. Now, we observe
that for any $u\in U_{\rm ad}$ and $j=1,\ldots,n$, applying (3) we get

$\displaystyle|f_{j}(y,u)-I_{k}f_{j}(y,u)|$ $\displaystyle=$
$\displaystyle|\sum_{i=1}^{n_{S}}\mu_{i}f_{j}(y,u)-\sum_{i=1}^{n_{S}}\mu_{i}I_{k}f_{j}(y_{i},u)|$
(27) $\displaystyle=$ $\displaystyle|\sum_{i\in
J_{l}}\mu_{i}(f_{j}(y,u)-f_{j}(y_{i},u)|$ $\displaystyle\leq$
$\displaystyle\sum_{i\in J_{l}}\mu_{i}L_{f}\|y-y_{i}\|_{2}\leq L_{f}k,$

where in the last inequality we have applied $\|y-y_{i}\|_{2}\leq k$, for
$i\in J_{l}$. From the above inequality we get for the second term on the
right-hand side of (25)

$\displaystyle\|f(y(s),\overline{u}(s))-I_{k}f(y(s),\overline{u}(s))\|_{\infty}\leq
L_{f}k.$ (28)

For the third term on the right-hand side of (25) we observe that the
difference of the interpolation operator evaluated at two different points can
be bounded in terms of the constant gradient of the interpolant in the element
to which those points belong times the difference of them, i.e.,

$I_{k}f_{j}(y,u)-I_{k}f_{j}(\tilde{y},u)=\nabla
I_{k}f_{j}(\tilde{y},u)\cdot(y-\tilde{y})\leq\|\nabla
I_{k}f_{j}(\tilde{y},u)\|_{2}\|y-\tilde{y}\|_{2}.$

Moreover, $\nabla I_{k}f_{k}$ can be bounded in terms of the lipschitz
constant of $f$, $L_{f}$, more precisely, $\|\nabla
I_{k}f_{j}(\tilde{y},u)\|_{2}\leq C\sqrt{n}L_{f}$. Then,

$|I_{k}f_{j}(y,u)-I_{k}f_{j}(\tilde{y},u)|\leq
CL_{f}\sqrt{n}\|y-\tilde{y}\|_{2}.$

As a consequence, for the third term on the right-hand side of (25) we get

$\displaystyle\|I_{k}f(y(s),\overline{u}(s))-I_{k}f(\tilde{y}(s),\overline{u}(s))\|_{\infty}$
$\displaystyle\leq$ $\displaystyle C\sqrt{n}L_{f}\|y(s)-\tilde{y}(s)\|_{2}$
(29) $\displaystyle\leq$ $\displaystyle
CnL_{f}\|y(s)-\tilde{y}(s)\|_{\infty}.$

Inserting (26), (28) and (29) into (24) we get for

$\overline{L}=CnL_{f},$ (30)
$\displaystyle\|y(t)-\tilde{y}(t)\|_{\infty}\leq\overline{L}\int_{0}^{t}\|y(s)-\tilde{y}(s)\|_{\infty}~{}ds+tL_{f}(L_{u}h+k)+M_{f}h.$

Applying Gronwall’s lemma we obtain

$\displaystyle\|y(t)-\tilde{y}(t)\|_{\infty}\leq\frac{e^{\overline{L}t}}{\overline{L}}\left(tL_{f}(L_{u}h+k)+M_{f}h\right).$
(31)

Applying (9) and taking into account that
$\|I_{k}g(y,u)\|_{\infty}\leq\|g(y,u)\|_{\infty}$ (where $\|\cdot\|_{\infty}$
refers to the $L^{\infty}$ norm respect to the first argument) it is easy to
check that

$\displaystyle|\hat{J}(y_{0},u)-J_{h,k}(y_{0},\boldsymbol{u})|\leq
X_{1}+X_{2}+X_{3},$ (32)

with

$\displaystyle X_{1}$ $\displaystyle=$
$\displaystyle\left|h\sum_{n=0}^{[T/h]-1}\delta_{h}^{n}I_{k}g(\hat{y}_{n},u_{n})-\int_{0}^{T}g(y(s),u(s))e^{-\lambda
s}~{}ds\right|,$ $\displaystyle X_{2}$ $\displaystyle=$
$\displaystyle\left|h\sum_{n=[T/h]}^{\infty}M_{g}\delta_{h}^{n}\right|,\quad
X_{3}=\int_{T}^{\infty}M_{g}e^{-\lambda s}~{}ds,$

and $T>0$ arbitrary. Now, we will estimate $X_{i}$. It is easy to see that

$X_{2}+X_{3}\leq M_{g}h\frac{\delta_{h}^{[T/h]}}{\lambda
h}+M_{g}\frac{e^{-\lambda T}}{\lambda}.$

Since $\delta_{h}^{[T/h]}\rightarrow e^{-\lambda T}$ when $h\rightarrow 0$
then for any $\epsilon>0$ there exists
$\overline{h}=\overline{h}(\epsilon,\lambda,M_{g})>0$ and
$\overline{T}=\overline{T}(\epsilon,\lambda,M_{g})>0$ such that

$\displaystyle X_{2}+X_{3}\leq\epsilon,\quad{\rm for}\ {\rm all}\
0<h\leq\overline{h},\quad T\geq\overline{T}.$ (33)

In the argument that follows we fix $T=\overline{T}$. We observe that

$X_{1}=\left|\int_{0}^{[T/h]h}I_{k}g(\tilde{y}(s),\overline{u}(s))\delta_{h}^{[s/h]}~{}ds-\int_{0}^{T}g(y(s),u(s))e^{-\lambda
s}~{}ds\right|.$

Then, we can write

$\displaystyle X_{1}$ $\displaystyle\leq$ $\displaystyle
X_{1,1}+X_{1,2}+X_{1,3}+X_{1,4}+X_{1,5}$ $\displaystyle:=$
$\displaystyle\left|\int_{0}^{[T/h]h}I_{k}g(\tilde{y}(s),\overline{u}(s))(\delta_{h}^{[s/h]}-e^{-\lambda
s})~{}ds\right|$
$\displaystyle\quad+\left|\int_{0}^{[T/h]h}I_{k}\left(g(\tilde{y}(s),\overline{u}(s))-I_{k}g(y(s),\overline{u}(s))\right)e^{-\lambda
s}~{}ds\right|$
$\displaystyle\quad+\left|\int_{0}^{[T/h]h}\left(I_{k}g(y(s),\overline{u}(s))-g(y(s),\overline{u}(s))\right)e^{-\lambda
s}~{}ds\right|$
$\displaystyle\quad+\left|\int_{0}^{[T/h]h}\left(g(y(s),\overline{u}(s))-g(y(s),u(s))\right)e^{-\lambda
s}~{}ds\right|$
$\displaystyle\quad+\left|\int_{[T/h]h}^{T}g(y(s),u(s))e^{-\lambda
s}~{}ds\right|.$

We will bound the terms on the right-hand side of (Proof). To bound the first
term we will apply again $\|I_{k}g(y,u)\|_{\infty}\leq\|g(y,u)\|_{\infty}$ and
(9) to obtain

$\displaystyle
X_{1,1}=\left|\int_{0}^{[T/h]h}I_{k}g(\tilde{y}(s),\overline{u}(s))(\delta_{h}^{[s/h]}-e^{-\lambda
s})~{}ds\right|$
$\displaystyle\quad\leq\int_{0}^{T}|I_{k}g(\tilde{y}(s),\overline{u}(s))||\delta_{h}^{[s/h]}-e^{-\lambda
s}|~{}ds\leq M_{g}\int_{0}^{T}|\delta_{h}^{[s/h]}-e^{-\lambda s}|~{}ds.$

Now we write $\delta_{h}^{[s/h]}=e^{-\lambda\theta[s/h]h}$, for
$\theta=-\log(\delta_{h})/(\lambda h)$. Applying the mean value theorem to the
function $e^{-\lambda s}$ and taking into account that since $[s/h]h\leq
s\leq[s/h]h+h$ then $|s-\theta[s/h]h|\leq(\theta-1)T+\theta h$ and that
$\theta\rightarrow 1$ when $h\rightarrow 0$ then we get

$\displaystyle X_{1,1}\leq M_{g}T\lambda((\theta-1)T+\theta h)\leq\epsilon,$
(35)

for $h\leq\overline{h}$, with
$\overline{h}=\overline{h}(\epsilon,\overline{T},\lambda,M_{g})$.

To bound the next term we argue as in (29) and use (31) to get

$\displaystyle
X_{1,2}\leq\frac{C{n}L_{g}}{\overline{L}}\int_{0}^{T}{e^{\overline{L}s}}\left(sL_{f}(L_{u}h+k)+M_{f}h\right)e^{-\lambda
s}~{}ds\leq C_{1}h+C_{2}k,$

where

$C_{1}=\frac{C{n}L_{g}}{\overline{L}}\int_{0}^{T}e^{(\overline{L}-\lambda)s}(sL_{f}L_{u}+M_{f})~{}ds,\quad
C_{2}=\frac{C\sqrt{n}L_{g}}{\overline{L}}\int_{0}^{T}e^{(\overline{L}-\lambda)s}sL_{f}~{}ds.$

Then

$\displaystyle X_{1,2}\leq\epsilon,\quad h\leq\overline{h},\
k\leq\overline{k},$ (36)

where
$\overline{h}=\overline{h}(\epsilon,\overline{T},\lambda,C,\overline{L},n,L_{g},L_{f},L_{u},M_{f})$,
$\overline{k}=\overline{k}(\epsilon,\overline{T},\lambda,C,\overline{L},n,L_{g},L_{f})$.
For the third term, arguing as in (27) we get

$\displaystyle X_{1,3}\leq L_{g}k\int_{0}^{T}e^{-\lambda
s}~{}ds\leq\epsilon,\quad
k\leq\overline{k}=\overline{k}(\epsilon,\overline{T},\lambda,L_{g}).$ (37)

To bound the forth term we apply (7) and (12) to get

$|g(y(s),\overline{u}(s))-g(y(s),u(s))|\leq L_{g}\|u(s)-u(t_{k})\|_{2}\leq
L_{g}L_{u}h,\quad s\in[kh,(k+1)h).$

And then

$\displaystyle X_{1,4}\leq L_{g}L_{u}h\int_{0}^{T}e^{-\lambda
s}~{}ds\leq\epsilon,\quad
h\leq\overline{h}=\overline{h}(\epsilon,\overline{T},\lambda,L_{g},L_{u}).$
(38)

Finally, for the last term on the right-hand side of (Proof), applying (9),

$\displaystyle X_{1,5}\leq M_{g}h\leq\epsilon,\quad
h\leq\overline{h}=\overline{h}(\epsilon,M_{g}).$ (39)

Inserting (35), (36), (37), (38) and (39) into (Proof) and taking into account
(32) and (33) we conclude (23). $\Box$

###### Lemma 2

Let $\hat{J}$ and $\hat{J}_{h,k}$ be the functionals defined in (13) and (19)
respectively. Assume conditions (3), (4), (5), (7), (8), (9) and (12) hold.
Assume $\lambda>\overline{L}$ with $\overline{L}$ the constant in (30). Then,
for $0\leq h\leq 1/(2\lambda)$ there exists a positive constant
$C=C(\lambda,M_{f},M_{g},L_{f},L_{g},L_{u})$ such that

$\displaystyle|\hat{J}(y_{0},u)-\hat{J}_{h,k}(y_{0},\boldsymbol{u})|\leq
C(h+k),\quad y_{0}\in{\mathbb{R}}^{n},$ (40)

where $u\in{\mathbb{U}}_{\rm ad}$ and
$\boldsymbol{u}=\left\\{u_{0},u_{1},\ldots,\right\\}=\left\\{u(t_{0}),u(t_{1}),\ldots,\right\\}$,
$t_{i}=ih$, $i=0,1,\ldots,$.

###### Proof

We argue as in [7, Lemma 1.2, Chapter VI]. Let $y(t)$ be the solution of (1)
and let us denote by $\tilde{y}(t)=\hat{y}_{k}$, $k=[t/h]$ where $\hat{y}_{k}$
is the solution of (20) with $\hat{y}_{0}=y_{0}$. Let us denote by

$\overline{u}(t)=u_{k}=u(t_{k}),\quad t\in[kh,(k+1)h).$

We first observe that

$|\hat{J}(y_{0},u)-\hat{J}_{h,k}(y_{0},\boldsymbol{u})|\leq X+Y,$

where

$\displaystyle X$ $\displaystyle=$
$\displaystyle\int_{0}^{\infty}|g(y(s),u(s))-I_{k}g(\tilde{y}(s),\overline{u}(s))|e^{-\lambda
s}~{}ds,$ $\displaystyle Y$ $\displaystyle=$
$\displaystyle\int_{0}^{\infty}|I_{k}g(\tilde{y}(s),\overline{u}(s))||e^{-\lambda
s}-e^{-\lambda\theta[s/h]h}|~{}ds,$

and, as in Lemma 1, $\theta=-\log(\delta_{h})/(\lambda h)$. To bound $X$ we
decompose

$\displaystyle|g(y(s),u(s))-I_{k}g(\tilde{y}(s),\overline{u}(s))|$
$\displaystyle\leq$ $\displaystyle|g(y(s),u(s))-g(y(s),\overline{u}(s))|$
$\displaystyle\quad+|g(y(s),\overline{u}(s))-I_{k}g(y(s),\overline{u}(s))|$
$\displaystyle\quad+|I_{k}g(y(s),\overline{u}(s))-I_{k}g(\tilde{y}(s),\overline{u}(s))|.$

Arguing as in Lemma 1 we get

$\displaystyle|g(y(s),u(s))-I_{k}g(\tilde{y}(s),\overline{u}(s))|$
$\displaystyle\leq$ $\displaystyle
L_{g}L_{u}h+L_{g}k+CnL_{g}\|y(s)-\tilde{y}(s)\|_{\infty}$

and then applying (31) we obtain

$\displaystyle
X\leq\frac{1}{\lambda}\left(L_{g}L_{u}h+L_{g}k\right)+C\frac{nL_{g}}{\overline{L}}\int_{0}^{\infty}\left(sL_{f}(L_{u}h+k)+M_{f}h\right)e^{(\overline{L}-\lambda)s}~{}ds.$

Then, for $\lambda>\overline{L}$ there exists a constant
$C=C(\lambda,M_{f},L_{f},L_{g},L_{u})$ such that

$X\leq C(h+k).$

To bound $Y$ we first observe that, arguing as before,
$|I_{k}g(\tilde{y}(s),\overline{u}(s))|\leq M_{g}$ and then

$Y\leq M_{g}\int_{0}^{\infty}|e^{-\lambda s}-e^{-\lambda\theta[s/h]h}|~{}ds.$

Applying the mean value theorem

$Y\leq M_{g}\int_{0}^{\infty}\lambda\max\left\\{e^{-\lambda
s},e^{-\lambda\theta[s/h]h}\right\\}|\lambda s-\lambda\theta[s/h]h|~{}ds.$

Now, since $|s-\theta[s/h]h|\leq(\theta-1)s+\theta h$ we get

$Y\leq M_{g}\lambda^{2}e^{\theta\lambda h}\int_{0}^{\infty}e^{-\lambda
s}((\theta-1)s+\theta h)~{}ds,$

and since both

$\int_{0}^{\infty}se^{-\lambda s}~{}ds,\quad\int_{0}^{\infty}e^{-\lambda
s}~{}ds,$

are bounded and $\lim_{h\rightarrow 0}(\theta-1)h=\lambda/2$ (for $0\leq h\leq
1/(2\lambda)$ the function $(\theta-1)/h$ is an increasing function bounded by
its value at $h=1/(2\lambda)$, i.e., $(\theta-1)/h\leq 2\lambda(2\log(2)-1)$,
we conclude

$Y\leq Ch,\quad C=C(M_{g},\lambda)>0.$

$\Box$

###### Theorem 4

Assume conditions (3), (4), (5), (7), (8), (9) and (12) hold. Assume
$\lambda>\overline{L}$ with $\overline{L}$ the constant in (30). Then, for
$0\leq h\leq 1/(2\lambda)$ there exists a positive constant
$C=C(\lambda,M_{f},M_{g},L_{f},L_{g},L_{u})$ such that

$|v(y)-v_{h,k}(y)|\leq C(h+k),\quad y\in{\mathbb{R}}^{n}.$

###### Proof

In view of (21) let us denote by $\overline{\boldsymbol{u}}\in{\cal U}$ a
control giving the minimum

$v_{h,k}(y)=\hat{J}_{h,k}(y,\overline{\boldsymbol{u}}).$

Then

$v(y)-v_{h,k}(y)\leq\hat{J}(y,\overline{u})-J_{h,k}(y,\overline{\boldsymbol{u}}),$

where $\overline{u}\in{\mathbb{U}}_{\rm ad}$ such that
$\overline{u}(t_{i})=\overline{u}_{i}$,
$\overline{\boldsymbol{u}}=\left\\{\overline{u}_{0},\overline{u}_{1},\ldots,\right\\}$.
$\Box$

Applying (40), there exists a positive constant
$C=C(\lambda,M_{f},M_{g},L_{f},L_{g},L_{u})$ such that

$v(y)-v_{h,k}(y)\leq C(h+k).$ (41)

Now, let us denote by $\underline{u}\in{\mathbb{U}}_{\rm ad}$ the control
giving the minimum in (14) and let us denote by
$\underline{\boldsymbol{u}}=\left\\{\underline{u}(t_{0}),\underline{u}(t_{1}),\ldots,\right\\}.$
Then, arguing as before there exists a positive constant
$C=C(\lambda,M_{f},M_{g},L_{f},L_{g},L_{u})$ such that

$v_{h,k}(y)-v(y)\leq\hat{J}_{h,k}(y,\underline{\boldsymbol{u}})-\hat{J}(y,\underline{u})\leq
C(h+k),$

which together with (41) implies

$|v(y)-v_{h,k}(y)|\leq C(h+k).$

Remark 1 If the controls are only continuous instead of Lipschitz-continuous
and taking into account that (23) holds true in that case, we can apply the
same arguments of Theorem 3 to prove convergence as $h$ goes to zero, but
loosing first order in time.

## References

  * [1] M. Akian, S. Gaubert, A. Lakhoua, The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis, SIAM J. Control Optim. 47 (2008), 817–848.
  * [2] A. Alla, B. Haasdonk & A. Schmidt, Feedback control of parametrized PDEs via model order reduction and dynamic programming principle, Adv. Comput. Math. 46 (2020), 28 pp.
  * [3] O. Bokanowski, J. Garcke, M. Griebel & I. Klompmaker, An adaptive sparse grid semi-Lagrangian scheme for first order Hamilton-Jacobi Bellman equations, J. Sci. Comput. 55 (2013), 575–605.
  * [4] E. Carlini, M. Falcone & R. Ferretti, An efficient algorithm for Hamilton-Jacobi equations in high dimension, Comput. and Visualization in Science, 7 (2004), 15–29.
  * [5] A. Alla, M. Falcone & D. Kalise, An efficient policy iteration algorithm for dynamic programming equations, SIAM J. Sci. Comput., 37 (2015), A181–A200.
  * [6] A. Alla, M. Falcone & S. Volkwein, Error analysis for POD approximations of infinite horizon problems via the dynamic programming approach, SIAM J. Control Optim., 55 (2017), 3091–3115.
  * [7] M. Bardi & I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Belmann Equations, Springer Science+Business Media, LLC, New York, 1997.
  * [8] M. Falcone, A numerical approach to the infinite horizon problem of deterministic control theory, Appl. Math. Optim., 15 (1987), 471–531.
  * [9] M. Falcone, Numerical solution of dynamic programming equations, in Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Belmann Equations, Springer Science+Business Media, LLC, New York, 1997, 471-504.
  * [10] B-Z. Guo & T-T, Wu, Approximation of optimal feedback control: a dynamic programming approach, J. Global Optim. 46 (2010), 395–422.


#  @ SIGIR 2023: The First Workshop on Generative Information Retrieval

Gabriel Bénédict<EMAIL_ADDRESS>0000-0002-3596-0285 University of
Amsterdam and RTL NLThe Netherlands ,  Ruqing Zhang<EMAIL_ADDRESS>0000-0003-4294-2541 ICT, Chinese Academy of SciencesChina and  Donald Metzler
<EMAIL_ADDRESS>Google ResearchUSA

(2023)

###### Abstract.

Generative information retrieval (IR) has experienced substantial growth
across multiple research communities (e.g., information retrieval, computer
vision, natural language processing, and machine learning), and has been
highly visible in the popular press. Theoretical, empirical, and actual user-
facing products have been released that retrieve documents (via generation) or
directly generate answers given an input request. We would like to investigate
whether end-to-end generative models are just another trend or, as some claim,
a paradigm change for IR. This necessitates new metrics, theoretical
grounding, evaluation methods, task definitions, models, user interfaces, etc.
The goal of this workshop111https://coda.io/@sigir/gen-ir is to focus on
previously explored Generative IR techniques like document retrieval and
direct Grounded Answer Generation, while also offering a venue for the
discussion and exploration of how Generative IR can be applied to new domains
like recommendation systems, summarization, etc. The format of the workshop is
interactive, including roundtable and keynote sessions and tends to avoid the
one-sided dialogue of a mini-conference.

Generative Models, Information Retrieval, Large Language Models

††submissionid: XXX††copyright: acmcopyright††journalyear: 2023††copyright:
rightsretained††conference: Proceedings of the 46th International ACM SIGIR
Conference on Research and Development in Information Retrieval; July 23–27,
2023; Taipei, Taiwan††booktitle: Proceedings of the 46th International ACM
SIGIR Conference on Research and Development in Information Retrieval (SIGIR
’23), July 23–27, 2023, Taipei, Taiwan††doi: 10.1145/3539618.3591923††isbn:
978-1-4503-9408-6/23/07††ccs: Information systems Information retrieval

##  1\. Title

@ SIGIR 2023: The First Workshop on Generative Information Retrieval

##  2\. Motivation

Last year saw the rise of generative IR on two fronts. We will refer to them
as:  (i) _Generative Document Retrieval (GDR)_ : via a generative process,
retrieve a ranked list of existing documents (e.g. Wikipedia or news articles)
that match a query and  (ii) _Grounded Answer Generation (GAG)_ : retrieve a
human readable generated answer that matches a query; the answer can link to
or refer to a document.

On the GDR end of the spectrum, Metzler et al. first proposed an end-to-end
_model-based retrieval_ approach in a position paper (Metzler et al., 2021):
directly predict identifiers of candidate documents, instead of indexing all
documents (a.k.a. _index-retrieve-then-rank_). The position paper builds on
generative entity linking (Cao et al., 2020; Khandelwal et al., 2020; Kassner
and Schütze, 2020), later extended for long sequences (Lee et al., 2022). The
generative model is expected to embed all relevant information that is in the
documents. Soon after, Tay et al. released Differentiable Search Indexes
(DSI), the first model generating indexes of Wikipedia articles (Tay et al.,
2022a). The above mentioned position paper (Metzler et al., 2021) goes beyond
GDR, towards GAG and full-fledged end-to-end retrieval models that generate
answers.

On the GAG end of the spectrum (Yang et al., 2019; Roller et al., 2021),
recent Large Language Models (LLMs) have been released to the public that are
essentially (conversational) IR models. Some are conversational with aspects
of reinforcement learning (ChatGPT222https://openai.com/blog/chatgpt/ or
Claude333https://www.anthropic.com/constitutional.pdf), some cite their
sources (Phind444https://phind.com/about or
Perplexity555https://www.perplexity.ai/), some are focused on science
(Galactica666https://galactica.org/), some can do all of the above and more
(YOU777https://you.com/), and others have yet to be released
(Sparrow888https://www.deepmind.com/blog/building-safer-dialogue-agents).

Generative IR as an end-to-end model has clear benefits over the _index-
retrieve-then-rank_ paradigm.  (i) It is simpler and more flexible.  (ii) The
training pipeline is compressed.  (iii) There is no need for an index of
documents that is tedious to query or compute similarity with.  But Generative
IR also comes with its challenges. Namely,  (i) it has yet to be demonstrated
that retrieval performance is improved on big datasets (such as the full MS-
MARCO dataset (Nguyen et al., 2016)),  (ii) generative models can hallucinate
(i.e., generate false information). This is more obviously true for LLMs that
generate answers (GAG) than for retrieval models that generate doc-ids (GDR).
(iii) The _infinite index_ paradigm (Deckers et al., 2022): if LLMs can
generate an infinite amount of answers to a given query, then classic recall-
based IR evaluation metrics like NDCG cannot rely on a finite amount of true
positives.

A workshop on Generative IR will question whether IR is truly facing a
paradigm change at the theoretical level (Metzler et al., 2021). This event
will also be a way to reflect on Generative IR’s benefits and challenges, as
retrieval-like LLMs (GAG) get released to the general public. Finally, we will
encourage submissions and discussions on further Generative IR topics and
models, where existing literature is scarce, such as recommender systems,
Learning to Rank, diffusion models, etc. We compiled a list of related
literature999https://github.com/gabriben/awesome-generative-information-
retrieval.

##  3\. Theme and purpose of the workshop

2023 will be a forum for discussion about the challenges in applying (pre-
trained) generation models for information retrieval as well as the theory
behind the models and applications. The aim of this workshop is multi-fold:
(i) discussing the main challenges in designing and applying generative
retrieval models in practice,  (ii) establishing a bridge for communication
between academic researchers and industrial researchers around Generative IR,
(iii) providing an opportunity for researchers to present new directions and
early insights, and  (iv) creating an agenda for Generative IR according to
the 4 pillars bellow (Model Architecture, Training, Evaluation, Applications).
This agenda will then ideally be periodically revised at future occurrences of
the workshop.

Our call for papers and the theme of the panel / roundtable discussions will
evolve around these 4 pillars. For now Generative IR revolves mostly around
Generative Document Retrieval (GDR) and Grounded Answer Generation (GAG). We
leave space for further tasks in the 4th pillar.

###  3.1. Model Architecture

Despite the preliminary studies on pre-trained language models (PTMs) for GDR,
most research in this direction focuses on straightforwardly applying existing
PTMs that are specifically designed for NLP into IR applications such as T5
(Raffel et al., 2020) and BART (Lewis et al., 2019). These encoder-decoder
architectures do not consider the IR cues that might benefit the downstream IR
tasks, such as GAG. These cues include information about ranking, entity
disambiguation, and the causal relationships behind ranking tasks.

Another solution could be to generate documents via other types of models that
can provide a range of predictions, like diffusion models (Sohl-Dickstein et
al., 2015). Diffusion models have already been tested for language generation
and categorical data in general (Dieleman et al., 2022) and are thus
candidates for both GDR and GAG tasks.

###  3.2. Training

Despite the strong experimental performance of GDR models, the potential of
generative models for general search problems is limited by the training
strategies that are currently employed.

  * •

Learning To Rank objective. Traditional _index-retrieve-then-rank_ paradigm
implies a Learning To Rank objective at the end of the pipeline. This
objective is commonly expressed as point-wise, pair-wise, or list-wise.
Following the new _model-based retrieval_ paradigm, the objective is global
over the whole corpus and usually defined as a standard seq2seq objective,
i.e., maximizing the output doc-id likelihood with teacher forcing conditioned
on the query. There are many interesting questions to help understand whether
such optimization is optimal, how it connects with existing Learning to Rank
paradigms, and so on.

  * •

Generalization Ability. So far most studies only demonstrate the effectiveness
of their approaches on retrieval datasets where a query has only one relevant
document. In the future, we should extend the generalization ability of GDR to
different search tasks, including a query with a relevant document, with
multiple relevant documents at one relevance grade, and with multiple relevant
documents at different relevance grades. One option to predict multiple
documents via model based retrieval is to use contrastive learning between the
document and query representations.

  * •

Incremental Learning. For GDR models, there remain open questions about the
practical applicability of such models to dynamic corpora. In dynamic and open
IR system, documents are incrementally added or removed from the indexed
corpus. It is valuable to explore continuously updated learning objectives
over new or removed documents (e.g. (Tay et al., 2022b)).

###  3.3. Evaluation

We consider several topics for the evaluation of Generative Document Retrieval
and Grounded Answer Generation:

  * •

We are not aware of an evaluation on a big dataset for either GDR or GAG (such
as the full MS-MARCO dataset (Nguyen et al., 2016)).

  * •

Evaluation metrics need to be designed taking into account the specifics of
the generative paradigm. These metrics should ideally both suit traditional IR
and Generative IR.

  * •

Human evaluation of Generative IR is still at its infancy. Note that ChatGPT
leverages Reinforcement Learning with Human Feedback (RLHF) (Ziegler et al.,
2019; Stiennon et al., 2020), while Claude uses RL from AI Feedback (RLAIF)
(Bai et al., 2022).

  * •

Interpretability and causality are still hard to determine. In the context of
GAG, this implies citing its sources, a.k.a. _attribution_ (Bohnet et al.,
2022) (via for example a citation token (Taylor et al., 2022)). In other words
bridging the gap between GDR and GAG.

  * •

Robustness to adversarial attacks (how easy is it to create fake facts or fool
the Grounded Answer Generation model) and to distribution shifts (does
transfer learning across datasets work?).

  * •

Efficiency of models. GDR requires considerably less compute power than GAG.
Is there a way to bring computational costs down for GAG or to provide more
information with the same amount of compute with GDR (e.g. a ranking of
documents instead of just one document or a summary of documents)?

  * •

GAGs tend to be very assertive about their claims. Uncertainty estimates would
be particularly desirable for GAGs and especially for the ones which don’t
cite their sources like ChatGPT.

  * •

GAGs can appear like they have a mind of their own. Some new conceptual
metrics and learning constraints have been proposed like truthfullness,
harmlessness, honesty and helpfulness (Bai et al., 2022).

###  3.4. Applications

At inference time, both GDR and GAG are sensitive to prompting strategies.
Given particular prompts, it has been shown that one can provoke ChatGPT into
hallucinating answers. As a solution, could we use a generation model to unify
GDR and GAG, so as to provide document references to source material making it
much easier to highlight the authoritativeness / accuracy of the answer?

Furthermore, there are several applications to Generative IR that have not yet
been subject to much scrutiny beyond GDR and GAG. We can think of
summarization, Knowledge-Intensive Language Tasks (KILT) (e.g. (Chen et al.,
2022a, b)), recommender systems (e.g. (Deffayet et al., 2023; Gupta et al.,
2022)) and learning to rank (e.g. (Liu et al., 2019)).

##  4\. Format

will be an interactive full-day hybrid workshop that avoids the one-sided
dialogue of a mini-conference.

  * •

Invited panel (industrial and academic) [hybrid]. Candidates from different
institutions and companies accepted our invitation: Neeva, Google, Meta AI,
Tsinghua University, Chinese Academy of Science, Sapienza University of Rome,
Samaya AI, KAIST, University of Waterloo, Huggingface, Stanford University.

  * •

Contributed paper presentations as posters [onsite] and video demos [online].

  * •

An interactive session to share lessons learned [hybrid].

  * •

Breakout sessions on issues that emerge from the contributed papers and demos
(to be determined after the submission deadline but prior to the workshop)
[onsite].

###  4.1. Workshop schedule

#### Morning

Time | Activity
---|---
08.30–08.45 | Opening
08:45–09:15 | Panel Discussions (academic)
09:15–10:00 | Poster Session - (1) Model Architecture
10:00–10:30 | Coffee break
10:30–11:00 | Panel Discussions (industrial)
11:00–11:45 | Poster Session - (2) Training
11:45–12:15 | Breakout preparation
11:45–13:30 | Lunch

#### Afternoon

Time | Activity
---|---
13:30–14:00 | Panel Discussions - Setting an agenda for Gen-IR
14:00–14:45 | Poster Session - (3) Evaluation
14:45–15:30 | Refreshment break
15:30–16:30 | Breakout
14:00–14:45 | Poster Session - (4) Applications
17:15–17:30 | Round up and closing discussions

#### Schedule

Date |  Event
---|---
May 2, 2023 |  Submission deadline
Jun 14, 2023 |  Notification
Jul 1, 2023 |  Camera ready versions of accepted papers due
Jul 27, 2023 |  Gen-IR workshop

##  5\. Organizers

Gabriel Benedict is an industry PhD candidate at University of Amsterdam, in
collaboration with RTL NL. He is doing a mix of theoretical and applied AI
research. The main themes are metrics-as-losses for neural networks, normative
diversity metrics for news recommendation, intent-satisfaction modelling,
video-to-music AI and most recently diffusion for IR tasks.

Ruqing Zhang is an associate professor in Institute of Computing Technology
(ICT), Chinese Academy of Sciences (CAS). She has worked on a number of
problems related to natural language generation and neural ranking models. Her
current research is especially how to design generative models for IR, how to
improve the robustness of ranking models, and how to make IR trustworthy with
the lens of “causality”.

Donald Metzler is a Senior Staff Research Scientist at Google Inc. Prior to
that, he was a Research Assistant Professor at the University of Southern
California (USC) and a Senior Research Scientist at Yahoo!. He currently leads
a research group focused on a variety of problems at the intersection of
machine learning, natural language processing, and information retrieval. He
is a co-author of the position paper (Metzler et al., 2021).

##  6\. PC members

Potential PC members for reviewing paper submissions:

  * •

Andrew Yates, University of Amsterdam

  * •

Arian Askari, Leiden University

  * •

Hainan Zhang, JD

  * •

Hyunji Lee, KAST AI

  * •

James Thorne, KAIST AI

  * •

Nicola De Cao, University of Amsterdam

  * •

Qingyao Ai, Tsinghua University

  * •

Roi Cohen, Tel Aviv University

  * •

Ronak Pradeep, University of Waterloo

  * •

Sheng-Chieh Lin, University of Waterloo

  * •

Shengyao Zhuang, The University of Queensland

  * •

Vinh Q. Tran, Google Research

  * •

Xiao Wang, University of Glasgow

  * •

Xinyu Ma, Baidu

  * •

Yujia Zhou, Renmin University of China

  * •

Zhicheng Dou, Renmin University of China

##  7\. Selection Process

We will solicit submission of papers of two to six pages through an open call
for papers, representing reports of original research, preliminary research
results, proposals for new work, descriptions of generative models based
toolkits tailored for IR, and position papers.

All papers will be peer reviewed by the program committee and judged by their
relevance to the workshop, especially to the two main themes, and their
potential to generate discussion.

##  8\. Target Audience

The target audience is the broad range of researchers in industry and academia
interested in IR and especially in Generative IR. We will advertise the
workshop via a dedicated website and a Twitter/Mastodon account.

##  9\. Related Workshops

As an emerging paradigm, there have not been related workshops held previously
at SIGIR or other conferences.

## References

  * (1)
  * Bai et al. (2022) Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, Carol Chen, Catherine Olsson, Christopher Olah, Danny Hernandez, Dawn Drain, Deep Ganguli, Dustin Li, Eli Tran-Johnson, Ethan Perez, Jamie Kerr, Jared Mueller, Jeffrey Ladish, Joshua Landau, Kamal Ndousse, Kamile Lukosuite, Liane Lovitt, Michael Sellitto, Nelson Elhage, Nicholas Schiefer, Noemi Mercado, Nova DasSarma, Robert Lasenby, Robin Larson, Sam Ringer, Scott Johnston, Shauna Kravec, Sheer El Showk, Stanislav Fort, Tamera Lanham, Timothy Telleen-Lawton, Tom Conerly, Tom Henighan, Tristan Hume, Samuel R. Bowman, Zac Hatfield-Dodds, Ben Mann, Dario Amodei, Nicholas Joseph, Sam McCandlish, Tom Brown, and Jared Kaplan. 2022.  Constitutional AI: Harmlessness from AI Feedback.  https://doi.org/10.48550/ARXIV.2212.08073
  * Bohnet et al. (2022) Bernd Bohnet, Vinh Q. Tran, Pat Verga, Roee Aharoni, Daniel Andor, Livio Baldini Soares, Jacob Eisenstein, Kuzman Ganchev, Jonathan Herzig, Kai Hui, Tom Kwiatkowski, Ji Ma, Jianmo Ni, Tal Schuster, William W. Cohen, Michael Collins, Dipanjan Das, Donald Metzler, Slav Petrov, and Kellie Webster. 2022\.  Attributed Question Answering: Evaluation and Modeling for Attributed Large Language Models.  https://doi.org/10.48550/ARXIV.2212.08037
  * Cao et al. (2020) Nicola De Cao, Gautier Izacard, Sebastian Riedel, and Fabio Petroni. 2020.  Autoregressive Entity Retrieval.  _CoRR_ abs/2010.00904 (2020).  https://arxiv.org/abs/2010.00904
  * Chen et al. (2022a) Jiangui Chen, Ruqing Zhang, Jiafeng Guo, Yixing Fan, and Xueqi Cheng. 2022a.  GERE: Generative Evidence Retrieval for Fact Verification. In _Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Madrid, Spain) _(SIGIR ’22)_. Association for Computing Machinery, New York, NY, USA, 2184–2189.  https://doi.org/10.1145/3477495.3531827
  * Chen et al. (2022b) Jiangui Chen, Ruqing Zhang, Jiafeng Guo, Yiqun Liu, Yixing Fan, and Xueqi Cheng. 2022b.  CorpusBrain: Pre-train a Generative Retrieval Model for Knowledge-Intensive Language Tasks. In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_. 191–200.
  * Deckers et al. (2022) Niklas Deckers, Maik Fröbe, Johannes Kiesel, Gianluca Pandolfo, Christopher Schröder, Benno Stein, and Martin Potthast. 2022\.  The Infinite Index: Information Retrieval on Generative Text-To-Image Models.  https://doi.org/10.48550/ARXIV.2212.07476
  * Deffayet et al. (2023) Romain Deffayet, Thibaut Thonet, Jean-Michel Renders, and Maarten de Rijke. 2023.  Generative Slate Recommendation with Reinforcement Learning. In _WSDM 2023: The Sixteenth International Conference on Web Search and Data Mining_. ACM.
  * Dieleman et al. (2022) Sander Dieleman, Laurent Sartran, Arman Roshannai, Nikolay Savinov, Yaroslav Ganin, Pierre H. Richemond, Arnaud Doucet, Robin Strudel, Chris Dyer, Conor Durkan, Curtis Hawthorne, Rémi Leblond, Will Grathwohl, and Jonas Adler. 2022\.  Continuous diffusion for categorical data.  https://doi.org/10.48550/ARXIV.2211.15089
  * Gupta et al. (2022) Shashank Gupta, Harrie Oosterhuis, and Maarten de Rijke. 2022\.  VAE-IPS: A Deep Generative Recommendation Method for Unbiased Learning From Implicit Feedback. In _CONSEQUENCES+REVEAL Workshop at RecSys ’22_. ACM.
  * Kassner and Schütze (2020) Nora Kassner and Hinrich Schütze. 2020.  BERT-kNN: Adding a kNN Search Component to Pretrained Language Models for Better QA. In _Findings of the Association for Computational Linguistics: EMNLP 2020_. Association for Computational Linguistics, Online, 3424–3430.  https://doi.org/10.18653/v1/2020.findings-emnlp.307
  * Khandelwal et al. (2020) Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. 2020.  Generalization through Memorization: Nearest Neighbor Language Models. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=HklBjCEKvH
  * Lee et al. (2022) Hyunji Lee, Sohee Yang, Hanseok Oh, and Minjoon Seo. 2022\.  Generative Retrieval for Long Sequences.  _CoRR_ abs/2204.13596 (2022).  https://doi.org/10.48550/arXiv.2204.13596 arXiv:2204.13596
  * Lewis et al. (2019) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. 2019\.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_ (2019).
  * Liu et al. (2019) Huafeng Liu, Jingxuan Wen, Liping Jing, and Jian Yu. 2019\.  Deep generative ranking for personalized recommendation. In _Proceedings of the 13th ACM Conference on Recommender Systems_. 34–42.
  * Metzler et al. (2021) Donald Metzler, Yi Tay, Dara Bahri, and Marc Najork. 2021\.  Rethinking Search: Making Domain Experts out of Dilettantes.  _SIGIR Forum_ 55, 1, Article 13 (jul 2021), 27 pages.  https://doi.org/10.1145/3476415.3476428
  * Nguyen et al. (2016) Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016.  MS MARCO: A human generated machine reading comprehension dataset. In _CoCo@ NIPs_.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al. 2020\.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ 21, 140 (2020), 1–67.
  * Roller et al. (2021) Stephen Roller, Emily Dinan, Naman Goyal, Da Ju, Mary Williamson, Yinhan Liu, Jing Xu, Myle Ott, Eric Michael Smith, Y-Lan Boureau, and Jason Weston. 2021.  Recipes for Building an Open-Domain Chatbot. In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_. Association for Computational Linguistics, Online, 300–325.  https://doi.org/10.18653/v1/2021.eacl-main.24
  * Sohl-Dickstein et al. (2015) Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. 2015.  Deep Unsupervised Learning using Nonequilibrium Thermodynamics. In _Proceedings of the 32nd International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 37)_ , Francis Bach and David Blei (Eds.). PMLR, Lille, France, 2256–2265.  https://proceedings.mlr.press/v37/sohl-dickstein15.html
  * Stiennon et al. (2020) Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. 2020.  Learning to summarize with human feedback.  _Advances in Neural Information Processing Systems_ 33 (2020), 3008–3021.
  * Tay et al. (2022a) Yi Tay, Vinh Q. Tran, Mostafa Dehghani, Jianmo Ni, Dara Bahri, Harsh Mehta, Zhen Qin, Kai Hui, Zhe Zhao, Jai Gupta, Tal Schuster, William W. Cohen, and Donald Metzler. 2022a.  Transformer Memory as a Differentiable Search Index. In _Advances in Neural Information Processing Systems_ , Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (Eds.).  https://openreview.net/forum?id=Vu-B0clPfq
  * Tay et al. (2022b) Yi Tay, Vinh Q. Tran, Mostafa Dehghani, Jianmo Ni, Dara Bahri, Harsh Mehta, Zhen Qin, Kai Hui, Zhe Zhao, Jai Gupta, Tal Schuster, William W. Cohen, and Donald Metzler. 2022b.  Transformer Memory as a Differentiable Search Index. In _Advances in Neural Information Processing Systems_ , Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (Eds.).  https://openreview.net/forum?id=Vu-B0clPfq
  * Taylor et al. (2022) Ross Taylor, Marcin Kardas, Guillem Cucurull, Thomas Scialom, Anthony Hartshorn, Elvis Saravia, Andrew Poulton, Viktor Kerkez, and Robert Stojnic. 2022.  Galactica: A Large Language Model for Science.  https://doi.org/10.48550/ARXIV.2211.09085
  * Yang et al. (2019) Liu Yang, Junjie Hu, Minghui Qiu, Chen Qu, Jianfeng Gao, W Bruce Croft, Xiaodong Liu, Yelong Shen, and Jingjing Liu. 2019.  A hybrid retrieval-generation neural conversation model. In _Proceedings of the 28th ACM international conference on information and knowledge management_. 1341–1350.
  * Ziegler et al. (2019) Daniel M. Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B. Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. 2019\.  Fine-Tuning Language Models from Human Preferences.  _arXiv preprint arXiv:1909.08593_ (2019).  https://arxiv.org/abs/1909.08593


# Astronomy Education in Covid Times

Priya Hasan & S N Hasan  Maulana Azad National Urdu University, Hyderabad,
India
email<EMAIL_ADDRESS>
(2021)

###### Abstract

We shall describe the various activities done by us in Covid Times including
outreach and educational workshops in Physics and Astronomy. We shall discuss
the caveats in virtual teaching of Astronomy and the lessons learnt in the
process.

###### keywords:

astronomical data bases, sociology of astronomy

††volume: 367††journal: Education and Heritage in the era of Big Data in
Astronomy††editors: R.M. Ros, B. Garcia, S. Gullberg, J. Moldon & P. Rojo,
eds.

##  1 Introduction

The pandemic of 2020 came as a shock and a challenge to the teaching community
all over the world. It meant adapting to a new system of communication as the
sole source with its limits on interaction and reach. It was a learning
experience for teachers as well as students because of its strong dependence
on pedagogical methodologies and technologies.

##  2 Activities

We collaborated with Jana Vigyan Vedika (JVV) Telangana which is a member
organisation of the All Indian People Science Network (AIPSN) and a member of
the National Council for Science and Technology Communication (NCSTC)in India.
The NCSTC is a scientific programme of the Government of India for the
popularisation of science, dissemination of scientific knowledge and
inculcation of scientific temper. JVV is an effective Science Forum in the
state and has a very good reach in rural and urban Telangana.

We started off with a Six-Day Online Astronomy Class from the 18-23 May 2020
from 4:30- 6:30 pm IST. We conducted a quiz at the end of the event and gave
certificates to participants who got the minimum mark. We had 475
registrations and many were given certificates with JVV.

Encouraged by the success of this, we conducted a Six-Day Workshop ‘Joy of
Learning Physics@ Home’ from 15-20 June 2020 for school students. We showed
them live demonstratons on Newton’s Laws, Gravity, Simple Machines, Pressure,
Optics and Electricity & Magnetism. At the end of each session, we
demonstrated an experiment with questions to be answered by students the next
day. It was very interactive and students were very enthusiastic about it. We
had an International-Astronomical Union-Office of Astronomy for Development
(IAU-OAD) Project ‘Clear Skies’ for school children and hence alot of the
material for activities were available to us.

In the meanwhile, the IAU-OAD announced a special call for Covid Times
Projects. We proposed a project ‘Astronomy from Archival Data’ which involved
Educational Activities for Under-Graduate and Post-Graduate Students
([Possel(2020), Possel, 2020]). The project is close to completion. For the
four months of August-November 2020, we had sessions every weekend on
Saturdays and Sundays where students learnt python, astropy, virtual
observatory tools like Topcat ([Taylor (2003), Taylor, 2003]), Aladin, ESASky
and sources of archival data. Resource persons from all over the world
contributed in guiding students in 10 Research Projects. The Internal Virtual
Observatory Alliance (IVOA) supports this project. Participants will present
their projects in the end of January. A more detailed report of this is
presented in this series in the form of a talk.

Prior to the pandemic, we had received funding from the US Consulate,
Hyderabad to conduct a Hands-on Astronomy Workshop for School Teachers.
Initially we were waiting for the situation to improve, but when it did not,
we got 68 astronomy kits delivered to School Teachers all over the country. We
then had a Two-Day Hands-on Astronomy Workshop online for almost 100 teahers
on the 30-31 October 2020. This Workshop covered topics like: Day-time
Astronomy activitiies, Sun-Dials, Optics, Telescope Malking and a basic
introduction to Astronomy. We also had a Panel Discussion on application of
Mathematics and Physics concepts in Astronomy.

To add on to the recent activity, we had another Hands-on Astronomy Workshop
on the 2,9 and 16 December with sessions by Prof Daniel Barth on Low-cost
Activities in Astronomy111Barth, D. E. (2019). Astronomy for Educators. Open
Educational Resources. Available at: https://scholarworks.uark.edu/oer/2.

As a team with Prof S N Hasan, we run Shristi Astronomy
(https://shristiastro.com/). Details of our activities are on the website and
the reader is encouraged to have a look. All the sessions have been recorded
and are available on youtube222https://www.youtube.com/c/shristiastronomy.

##  3 Lessons Learnt

In the course of our sessions we learned the following:

  * •

Planning of the events has to be done carefully since most potential
participants had their own online sessions on. We selected weekends, evenings
or holidays for all our events.

  * •

There are various issues like internet connectivity problems, power as well as
overlapping events. Hence all our activities were recorded and made available
on youtube so that participants could attend at their convenience.

  * •

A few of the participants were from non-English speaking countries, hence we
enabled subtitles on our videos for their benefit.

  * •

It is good to have a variety of speakers ranging from students, research
scholars, post-doctoral fellows and junior and senior faculty. The level needs
to be matched to the average participant.

We hope that these resources we created would be useful even when better times
return.

## References

  * [Possel(2020)] Possel, M. 2020, The Open Journal of Astrophysics, 3, 1
  * [Taylor (2003)] Taylor M. B. 2005, ASPC, 347, 29


# GIPFA: Generating IPA Pronunciation from Audio

Xavier Marjou
<EMAIL_ADDRESS>

###### Abstract

Transcribing spoken audio samples into International Phonetic Alphabet (IPA)
has long been reserved for experts. In this study, we instead examined the use
of an Artificial Neural Network (ANN) model to automatically extract the IPA
pronunciation of a word based on its audio pronunciation, hence its name
Generating IPA Pronunciation From Audio (GIPFA). Based on the French Wikimedia
dictionary, we trained our model which then correctly predicted $75\%$ of the
IPA pronunciations tested. Interestingly, by studying inference errors, the
model made it possible to highlight possible errors in the dataset as well as
identifying the closest phonemes in French.

_K_ eywords Audio $\cdot$ Transcription $\cdot$ Phonemes $\cdot$ Artificial
Neural Network $\cdot$ Dataset

##  1 Introduction

Some dictionaries like Wiktionary offer both to listen to words spoken by real
users and to read pronunciations in the form of the International Phonetic
Alphabet (IPA).

However, in the case of the French Wiktionary, the IPA transcripts are subject
to a small percentage of errors. Several reasons can explain these errors.
First, Wiktionary contributors may not be IPA experts; second, even IPA
experts sometimes may make careless mistakes; third, the audio may be
inconsistent because it is generally recorded independently without taking IPA
pronunciation into account, which can lead to important discrepancies; fourth,
some sounds like /o/ and /O/ may be very close to each other and can depend on
the speaker.

This article examines whether such errors could be avoided by using an Natural
Language Processing (NLP) tool to automatically extract IPA pronunciation from
audio pronunciation.

To this purpose, we made use of Automatic Speech Recognition (ASR), which has
already been the subject of in-depth studies. In particular, many recent
implementation approaches have successfully used a deep Artificial Neural
Network (ANN) as in [1] and [2], hence our choice to design a new ANN called
Generating IPA Pronunciation From Audio (GIPFA). In order to train and test
it, we also assembled a new experimental dataset based on $80200$ samples from
the French Wiktionary.

Despite a dataset containing an unknown percentage of erroneous data samples,
our GIPFA model succeeded in providing reasonable accuracy. Although it failed
to replace IPA experts, it nevertheless proved to be particularly useful in
identifying the biggest errors in the dataset.

##  2 Methodology

In order to predict the IPA pronunciation of a word, two main steps were
necessary: identifying a relevant dataset and designing an ANN model capable
of inferring an IPA pronunciation from an audio pronunciation.

###  2.1 Dataset

Word | Audio filename | IPA pronunciation
---|---|---
bonjour | LL-Q150 (fra)-LoquaxFR-bonjour.wav |  bÕZuK

|  |
Table 1: Dataset

Our dataset came from a Wikimedia
dump111https://dumps.wikimedia.org/frwiktionary/20200501/ containing all pages
and articles of the French Wiktionary. In this dump, each page generally
contains three essential features: one _word_ along with $n$ main _IPA
pronunciations_ and $m$ examples of _audio pronunciations_ recorded by by
several speakers.

  * •

A word is a text string containing Unicode characters. The _word_ terminology
has to be taken in the broad sense as a Wiktionary word encompasses common
names, proper names words, abbreviations, numbers and even sayings. Although
our ANN did not use it, we kept the word in our dataset for debugging
purposes, in order to have the possibility to find back the Wiktionary page
containing the pronunciations.

  * •

An audio pronunciation refers to an audio file generally recorded in a
Waveform Audio File (WAV) format containing the pronounced word. Wiktionary
pages can contain one or more audio pronunciations for the same word. When an
audio file is generated with LinguaLibre (LL) 222https://lingualibre.org
software, it benefits three useful features: the audio file is under the
Creative Commons sharing license333https://creativecommons.org/licenses/by-
sa/4.0/; the file can be fecthed from Wikimedia
Commons444https://commons.wikimedia.org/ based on its audio filename; the
audio filename also contains a label representing a user name which can be
used to identify audio files generated by users.

  * •

An IPA pronunciation is a text string containing IPA symbols. For learning
purposes, each audio pronunciation of a word should ideally be associated to a
single IPA pronunciation transcribing this precise audio content; a ranking of
the most common pronunciations might also be calculated and indicated in the
page describing the word. However, most words have a single IPA pronunciation
(i.e. $n=1$) even when multiple audio pronunciations are available. Although
some words have multiple IPA pronunciations (e.g. _coût_), a Wiktionary page
rarely indicates which of these pronunciations corresponds to an audio file.

For our purpose, we restricted our dataset to samples containing:

  * •

Words of the French Wiktionary555https://fr.wiktionary.org/;

  * •

French words, given that each Wiktionary describes words of several languages;

  * •

Words with a single IPA pronunciation, given that multiple IPA per audio
sample introduce ambiguities;

  * •

IPA pronunciation containing symbols making part of the $37$ traditional
French phonemes (i.e. ’i’, ’e’, ’E’, ’a’, ’A’, ’O’, ’o’, ’u’, ’y’, ’ø’, ’œ’,
’@’, ’Ẽ’, ’Ã’, ’Õ’, ’œ̃’, ’j’, ’w’, ’4’, ’p’, ’k’, ’t’, ’b’, ’d’, ’g’, ’f’,
’s’, ’S’, ’v’, ’z’, ’Z’, ’l’, ’K’, ’m’, ’n’, ’’, ’N’);

  * •

IPA pronunciation containing less than $20$ phonemes, in order to keep our ANN
model reasonable in size regarding our resources;

  * •

Audio files recorded with LL, in order to easily fetch audio files.

We also discarded 9 symbols that appear as optional in the IPA pronunciation
of the French Wiktionary (’-’, ’.’, ’ ’, ’*͡’, ’” and ’:’, ’(’, ’)’, ’-’).

The resulting dataset contained $80200$ samples from $102$ different speakers.
As depicted in Table 1, each sample contained three features: a _word_ , an
_audio filename_ and an _IPA pronunciation_.

In addition, we also pre-processed the WAV files to have a fix length of $2$
seconds, and then converted them into an Mel-Frequency Cepstral Coefficients
(MFCC) format so that they could serve as direct inputs into our model.
Although processing audio files under a WAV format would be possible as in
[3], it requires significant RAM memory, hence our choice to transpose them
into a MFCC format, as usually performed in many studies like in [4] and [5].

###  2.2 Experiments

####  2.2.1 Model architecture

Audio dataConv1dReluConv1dReluLSTMLSTMLinearIPA data Figure 1: The GIPFA ANN
model used for transcribing audio samples into IPA samples.

We modeled our GIPFA ANN as depicted in Figure 1. It contains typical
components found in many ANN models used for ASR. However, given that we only
had to translate a single word per sample, we did not use any Transformer
component [7]. Each audio input sample (MFCC data) first traversed a stack of
two 1D convolution layer (Conv1D) layers to extract the shape of the MFCC
data; followed by two Long Short Term Memory (LSTM) filters [8] to extract
temporal sequences; and finally followed by a linear layer in order to allow a
Connectionist Temporal Classification (CTC) loss calculation [9]. We did not
allow the succession of two identical phonemes because this is rare in French
words. In addition, we used an AdamW optimizer [10] with a learning rate of
$1\text{\times}{10}^{-4}$.

####  2.2.2 Hyperparameters

We used Ray Tune [11] for fine-tuning our hyperparameters with respect to
accuracy results. It led us to identify a set of best values among from a
larger set of experimented values as summarized in Table 2. The resulting
model contained $9\,609\,558$ trainable parameters. Slight variations in the
best values did not lead to significant improvement. Although it is believed
that wider network may have lead to better results [12], we limited our model
to these $10M$ parameters due to our limited computing resources.

Hyperparameter | Tested values | Best value
---|---|---
mfcc_coefficients | 40 | $40$
conv1d_activ | none, relu | relu
conv1d_layers |  $0$, $1$, $2$, $3$ | $2$
conv1d_units |  $32$, $64$, $128$ | $128$
conv1d_bn | False, True | True
lstm_layers |  $0$, $1$, $2$ | $2$
lstm_units |  $128$, $256$, $512$ | $512$
lstm_dropout |  $0.1$, $0.25$, $0.5$ | $0.5$
lstm_bidir | False, True | True
lstm_bn | False, True | True
optimizer | Adam, AdamW | AdamW
lr | 1e-3, 1e-4 | 1e-4

|  |
Table 2: GIPFA hyperparameters values

####  2.2.3 Training

For the training step, we used $79\,326$ samples distributer over $3966$
batches of $20$ samples ($3927$ training batches and $39$ evaluation batches).
During a pre-processing step, all audio samples were standardized with a the
mean ($-11.48$) and standard deviation ($80.30$) pre-observed on the dataset.

Before each run, the data samples were randomly shuffled. Each training run
took approximately 10 epochs of 3 minutes each on a single GPU (GeForce RTX
2080, 8 GB).

####  2.2.4 Test

For the testing step, we used $1000$ unseen samples to evaluate the
performances of the GIPFA ANN.

####  2.2.5 Accuracy

Since solving the translation problem requires correct inference of the entire
IPA pronunciation, we simply set for each tested sample an accuracy of $1$
when our model predicted an IPA pronunciation equal to the tested target IPA
pronunciation, or $0$ otherwise. After each training run, we then calculated
the average accuracy across all samples (i.e. average accuracy between $0.0$
and $1.0$).

We performed 11 runs (with one training step and one test step for each) to
allow reasonable confidence in the average accuracy results. We finally
computed a mean accuracy and the associated standard deviation (std) on the 11
tests.

Since the dataset had not been studied further, there was unfortunately no
baseline reference to challenge our results.

####  2.2.6 Enlightenment on errors

To our knowledge, no study has examined the exactness and coherence of the
audio files and IPA pronunciations of the French Wiktionary, meaning that the
dataset may contain errors, making it difficult to assess whether a prediction
error comes from the dataset or from the ANN.

In order to obtain more in-depth information on errors, we therefore also
calculated three other metrics related to the $80000$ samples in the dataset:

  * •

At the word level

    * –

_Edit distance error_ : the Levenshtein distance [6] between the predicted IPA
pronunciation and the target IPA pronunciation, in order to estimate how far
the prediction was from the target.

  * •

At the phoneme level

    * –

_Average phoneme accuracy_ : the percentage of correct translations for each
phoneme;

    * –

_Error pair percentage_ : Since each of the 37 target phonemes can be
incorrectly translated as one of the other 36 phonemes, the results can
contain up to 37 * 36 categories of error pairs. To assess the
representativeness of each pair, we calculated its number of occurrences
divided by the total number of phonemic errors.

The code is available on Github 666Code available at
https://github.com/marxav/gipfa.

##  3 Results

In this section, we describe two different results: first, the accuracy of the
model; then a more detailed observation of errors at the phoneme level and at
the word level.

###  3.1 Accuracy

Training samples | Tested samples | Pronunciation accuracy | Pronunciation accuracy
---|---|---|---
|  | (mean) | (std)
$79326$ | $1000$ | $0.75$ | $0.02$

|  |  |
Table 3: Pronunciation accuracy

Table 3 presents the accuracy results which were consistent consistent across
the 11 runs; our GIPFA ANN model successfully predicted around $75$ IPA
pronunciations out $100$ audio samples.

Correctly inferred pronunciations had a mean length of 7.51 whereas
incorrectly inferred pronunciations had a mean length of 8.65 thus indicating
a slightly higher probability of error as the length of the IPA pronunciation
increased.

###  3.2 Insights on the errors

Performing inferences on $80000$ samples of the dataset allowed to better
understand the reasons for the errors.

####  3.2.1 Phoneme Accuracy

Table 4 reports the translation accuracy of each phoneme. One phoneme (/A/)
had poor accuracy (less than $50\%$), five phonemes (/o/, /N/, /œ̃/, // and
/oe/) had moderate accuracy (between $65\%$ and $89\%$) while the remaining
thirty-one phonemes had high accuracy (over $90\%$).

Target | Correct | Incorrect | Average
---|---|---|---
phoneme | translation | translation | accuracy
A | $392$ | $605$ | $0.39$
o | $4.615$ | $2485$ | $0.65$
N | $40$ | $17$ | $0.70$
œ̃ | $241$ | $89$ | $0.73$
| $697$ | $110$ | $0.86$
œ | $2459$ | $301$ | $0.89$
4 | $1185$ | $113$ | $0.91$
E | $15\,859$ | $1472$ | $0.92$
@ | $7918$ | $732$ | $0.92$
g | $5911$ | $427$ | $0.93$
ø | $2587$ | $169$ | $0.94$
O | $18\,655$ | $1074$ | $0.95$
e | $30\,018$ | $1608$ | $0.95$
w | $4357$ | $159$ | $0.96$
v | $7469$ | $282$ | $0.96$
u | $6712$ | $250$ | $0.96$
Ẽ | $4527$ | $192$ | $0.96$
j | $12\,567$ | $547$ | $0.96$
b | $12\,753$ | $434$ | $0.97$
n | $13\,165$ | $472$ | $0.97$
p | $14\,845$ | $464$ | $0.97$
l | $23\,181$ | $684$ | $0.97$
Ã | $13\,704$ | $226$ | $0.98$
f | $9632$ | $225$ | $0.98$
y | $8235$ | $183$ | $0.98$
z | $7730$ | $146$ | $0.98$
i | $34\,772$ | $664$ | $0.98$
d | $15\,975$ | $323$ | $0.98$
k | $23\,159$ | $503$ | $0.98$
S | $4407$ | $92$ | $0.98$
a | $44\,575$ | $707$ | $0.98$
m | $17\,334$ | $313$ | $0.98$
K | $47\,221$ | $799$ | $0.98$
Z | $5552$ | $137$ | $0.98$
t | $29\,691$ | $713$ | $0.98$
Õ | $9258$ | $129$ | $0.99$
s | $30\,018$ | $400$ | $0.99$

|  |  |
Table 4: Average accuracy of each phoneme Figure 2: Confusion Matrix

To better observe the details, we also detailed these phoneme translation
errors in a confusion matrix as shown in Figure 2. Each row in the matrix
represented a target phoneme while each column represented the distribution of
predicted phonemes. For instance, it turned out that the target phoneme /E/
was $6\%$ of the time predicted as /e/, $92\%$ as /E/ and $1\%$ /a/. Notable
outliers were four large numbers outside the diagonal: $58\%$ of /A/ seemed
poorly predicted as an /a/; $31\%$ of /o/ as /O/; $21\%$ of /œ̃/ as /Ẽ/; and
$11\%$ of /N/ as /g/; It turned out that, like humans, the ANN had
difficulties in differentiating near elementary sounds.

####  3.2.2 Error pair percentage

Table 5 represents the proportion of the error associated with each phoneme
pair compared to the total errors of all pairs of phonemes. Interestingly,
only three pairs of phonemes generated $31\%$ of all errors: (/o/, /O/)
($15\%$ of all errors), (/e/, /E/) ($12\%$ of all errors) and (/a/, /A/)
($4\%$ of all errors).

Target | Predicted | Percentage of
---|---|---
phoneme | phoneme | all errors
o |  O | $12.03\%$
e |  E | $6.51\%$
E |  e | $5.46\%$
A |  a | $3.16\%$
O |  o | $3.07\%$
t |  d | $1.25\%$
E |  a | $1.04\%$
a |  A | $0.83\%$

|  |
Table 5: Most encountered error pairs

####  3.2.3 Word-level distance error

Computed | Levenshtein distance
---|---
samples | mean, std
$80000$ |  $0.31$, $0.66$

|
Table 6: Levenshtein distance

Table 6 reports a small mean Levenshtein distance and gives assurance that
there is strong consistency between the audio content and the IPA
pronunciation for the samples in the dataset studied.

Word |  IPA Target |  IPA Prediction | Levenshtein distance
---|---|---|---
1337 | /lit/ | /mitasÃtKÃmzOt/ | 13
agent innervant | /aZÃinEKvÃ/ | /go/ | 11
brut de décoffrage | /bKytd@dekOfKaZ/ | /sbOKdedtOK/ | 10
Michel | /miSEl/ | /stẼd@sÃmSEl/ | 10
phalange proximale | /falÃZpKOksimal/ | /falÃZ/ | 9
analyse calorimétrique | /analOgSimik/ | /analiskalOKimetik/ | 9
àtha | /atÕnœ̃blavi/ | /ata/ | 9
Wikitionnaire | /gazaefEd@sfEK/ | /gOZifisølEK/ | 9
arrondir par défaut | /aKÕdiKpaKdefo/ | /aKÃdiK/ | 8
Luxembourg | /lyksÃbuK/ | /yseKzOnb/ | 8

|  |  |
Table 7: Top-10 pronunciations with the highest Levenshtein distance

However, Table 7 focuses on the most extreme outliers by reporting the 10
samples with the highest Levenshtein distance. Upon investigation, it was
found that all these $10$ samples contained either an error in the audio
sample (e.g. bad word spoken or no word spoken at all) or an error in the
target IPA pronunciation, which meant that all these errors were in the
dataset itself. These results therefore suggest that data samples whose
pronunciations have a high Levenshtein distance probably contain an error.

Additional work would be required to identify the best threshold distance to
identify possible errors in the dataset.

##  4 Discussion and Conclusion

Previous work has documented the effectiveness of the ANN model for ASR.
However most studies have focused on the direct translation of audio samples
into words.

In this study, we focused instead on the translation of audio samples into
phonemes. We first proposed an ANN predicting with $75\%$ accuracy the French
pronunciations of the French Wiktionary.

Since to our knowledge no existing work has been done on this specific task
and dataset, there was no basis for comparison or assurance as to the accuracy
and consistency of the data.

We have shown that the translations of certain phonemes were more problematic
since some phonemes are close elementary sounds (/o/ and /O/, /E/ and /e/, /A/
and /a/) and thus difficult to be distinguished. Future work may consider
carefully checking the audio samples and IPA pronunciations containing these
close phonemes, which would in turn enhance the efficiency of the ANN. In
addition, future work could also involve synthesized audio examples and use
them as additional samples to reinforce training data.

However, we have also shown that the Levenshtein distance between our GIPFA
prediction and the target (as it exists in the dataset and therefore in the
Wiktionary) can highlight the most suspect samples in the dataset. Such
results therefore suggest that our GIPFA ANN would be a valuable tool to help
verify the consistency of the Wiktionary regarding pronunciation.

Therefore, integrating it into a tool like LL should be useful in order to
suggest an IPA transcription. It could even be used to suggest an IPA
transcription associated with each recorded audio sample, since having one IPA
transcription per audio file should further improve the performances of the
ANN.

Finally, we believe this method should be applicable to other languages
provided that a sufficient number of training samples are available.

## Acknowledgements

We thank all Wiktionary and LinguaLibre contributors for their contributions
without which there would be no wonderful free dictionary and no free dataset
either.

## References

  * [1] Wei Han, Zhengdong Zhang, Yu Zhang, Jiahui Yu, Chung-Cheng Chiu, James Qin, Anmol Gulati, Ruoming Pang, and Yonghui Wu.  Contextnet: Improving convolutional neural networks for automatic speech recognition with global context.  arXiv preprint arXiv:2005.03191, 2020.
  * [2] Amit Das, Jinyu Li, Guoli Ye, Rui Zhao, and Yifan Gong.  Advancing acoustic-to-word ctc model with attention and mixed-units.  IEEE/ACM Transactions on Audio, Speech, and Language Processing, 27(12):1880–1892, 2019.
  * [3] Tara Sainath, Ron J. Weiss, Kevin Wilson, Andrew W. Senior, and Oriol Vinyals.  Learning the speech front-end with raw waveform cldnns.  In Interspeech, 2015.
  * [4] Noelia Alcaraz Meseguer.  Speech analysis for automatic speech recognition.  Master’s thesis, Institutt for elektronikk og telekommunikasjon, 2009\.
  * [5] Md Mahadi Hasan Nahid, Bishwajit Purkaystha, and Md Saiful Islam.  Bengali speech recognition: A double layered lstm-rnn approach.  In 2017 20th International Conference of Computer and Information Technology (ICCIT), pages 1–6. IEEE, 2017.
  * [6] Vladimir I Levenshtein.  Binary codes capable of correcting deletions, insertions, and reversals.  Reports of the USSR Academy of Sciences, 163(4):845–848, 1965.
  * [7] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Advances in neural information processing systems, pages 5998–6008, 2017.
  * [8] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural Computation, 9:1735–1780, 1997.
  * [9] Alex Graves.  Connectionist temporal classification.  In Supervised Sequence Labelling with Recurrent Neural Networks, pages 61–93. Springer, 2012.
  * [10] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization, 2017.
  * [11] Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael I Jordan, et al.  Ray: A distributed framework for emerging $\\{$AI$\\}$ applications.  In 13th $\\{$USENIX$\\}$ Symposium on Operating Systems Design and Implementation ($\\{$OSDI$\\}$ 18), pages 561–577, 2018.
  * [12] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever.  Deep double descent: Where bigger models and more data hurt.  arXiv preprint arXiv:1912.02292, 2019.