* [49] Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang, Jiri Hron, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein.  Bayesian deep convolutional networks with many channels are gaussian processes.  arXiv preprint arXiv:1810.05148, 2018.
  * [50] Daniel S Park, Jascha Sohl-Dickstein, Quoc V Le, and Samuel L Smith.  The effect of network width on stochastic gradient descent and generalization: an empirical study.  arXiv preprint arXiv:1905.03776, 2019.
  * [51] Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli.  Exponential expressivity in deep neural networks through transient chaos.  In Advances in neural information processing systems, pages 3360–3368, 2016.
  * [52] Maithra Raghu, Ben Poole, Jon M. Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein.  On the expressive power of deep neural networks.  In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, pages 2847–2854, 2017.
  * [53] Daniel A Roberts, Sho Yaida, and Boris Hanin.  The Principles of Deep Learning Theory: An Effective Theory Approach to Understanding Neural Networks.  Cambridge University Press, 2022.
  * [54] Frank Rosenblatt.  The perceptron: a probabilistic model for information storage and organization in the brain.  Psychological review, 65(6):386, 1958.
  * [55] Grant M Rotskoff and Eric Vanden-Eijnden.  Neural networks as interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation error.  arXiv preprint arXiv:1805.00915, 2018.
  * [56] Inbar Seroussi and Zohar Ringel.  Separation of scales and a thermodynamic description of feature learning in some cnns.  arXiv preprint arXiv:2112.15383, 2021.
  * [57] Justin Sirignano and Konstantinos Spiliopoulos.  Mean field analysis of neural networks: A central limit theorem.  Stochastic Processes and their Applications, 130(3):1820–1852, 2020\.
  * [58] Justin Sirignano and Konstantinos Spiliopoulos.  Mean field analysis of deep neural networks.  Mathematics of Operations Research, 2021.
  * [59] Jay M Ver Hoef.  Who invented the delta method?  The American Statistician, 66(2):124–127, 2012.
  * [60] Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro.  Kernel and rich regimes in overparametrized models.  arXiv preprint arXiv:2002.09277, 2020.
  * [61] Sho Yaida.  Non-gaussian processes and neural networks at finite widths.  MSML, 2020.
  * [62] Greg Yang.  Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation.  arXiv preprint arXiv:1902.04760, 2019.
  * [63] Greg Yang.  Tensor programs i: Wide feedforward or recurrent neural networks of any architecture are gaussian processes.  arXiv preprint arXiv:1910.12478, 2019.
  * [64] Greg Yang and Edward J Hu.  Tensor programs iv: Feature learning in infinite-width neural networks.  In International Conference on Machine Learning, pages 11727–11737. PMLR, 2021.
  * [65] Greg Yang and Sam S Schoenholz.  Deep mean field theory: Layerwise variance and width variation as methods to control gradient explosion.  2018\.
  * [66] Jacob Zavatone-Veth and Cengiz Pehlevan.  Exact marginal prior distributions of finite bayesian neural networks.  Advances in Neural Information Processing Systems, 34, 2021.
  * [67] Guodong Zhang, Aleksandar Botev, and James Martens.  Deep learning without shortcuts: Shaping the kernel with tailored rectifiers.  arXiv preprint arXiv:2203.08120, 2022.

##  Appendix A Proof of Theorem 2.2

Our proof of Theorem 2.2 closely follows the proof of Theorem 1.2 in [18]. Let
us first recall the notation and assumptions. We fix
$\sigma:\mathbb{R}\rightarrow\mathbb{R}$ such that

  * •

There exists $r\geq 1$ so that the $r$-th derivative of $\sigma$ belongs to
$L^{\infty}$.

  * •

There exist $c,c^{\prime}>0$ so that

$\left|\left|e^{-cx^{2-c^{\prime}}}\frac{d^{r}}{dx^{r}}\sigma(x)\right|\right|_{L^{\infty}}<\infty.$

We take $C_{b}\geq$ and $C_{W}>0$ and consider a random depth $L$ neural
network with input dimension $n_{0}$, output dimension $n_{L+1}$, hidden layer
widths satisfying

$\exists c,C>0\text{ s.t. }cn\leq n_{1},\ldots,n_{L}\leq Cn,\qquad n\gg 1,$

non-linearity $\sigma$ and random weights and biases as in (2.2). We also fix
a finite collection

$x_{\mathcal{A}}:=\left\\{x_{\alpha},\quad\alpha\in\mathcal{A}\right\\}$

of distinct network inputs as well as an integer $m$ and study for each $\ell$
the random vectors

$D^{\leq r}z_{\mathcal{A}}^{(\ell)}:=\left(D^{\leq r}z_{i;\mathcal{A}},\quad
i=1,\ldots,m\right),$

where

$D^{\leq
r}z_{i;\mathcal{A}}:=\left(D_{\alpha}^{J}z_{i;\alpha}^{(\ell)},\quad\alpha\in\mathcal{A},\,i=1,\ldots,m,\left|J\right|\leq
r\right)$

are the derivatives of $z_{i;\mathcal{A}}^{{}_{(\ell)}}$ of order at most $r$.
Our goal is to show that, as $n\rightarrow\infty$, the joint distribution of
the random vectors $D^{\leq r}z_{i;\mathcal{A}}^{{}_{(\ell)}}$ converges to
that of of centered jointly Gaussian vectors that are independent for
different $i$ and satisfy

$\lim_{n\rightarrow\infty}\mathrm{Cov}\left(D_{\alpha_{1}}^{J_{1}}z_{i;\alpha_{1}}^{(\ell)},\,D_{\alpha_{2}}^{J_{2}}z_{i;\alpha_{2}}^{(\ell)}\right)=D_{\alpha_{1}}^{J_{1}}D_{\alpha_{2}}^{J_{2}}K_{\alpha_{1}\alpha_{2}}^{(\ell)},$

where

$K_{\alpha_{1}\alpha_{2}}^{(\ell+1)}=C_{b}+C_{W}\left\langle\sigma(z_{\alpha})\sigma(z_{\beta})\right\rangle_{K^{(\ell)}},\quad
K_{\alpha_{1}\alpha_{2}}^{(1)}=C_{b}+C_{W}\sum_{j=1}^{n_{0}}x_{j;\alpha_{1}}x_{j;\alpha_{2}}$

is the infinite width covariance from Theorem 2.2. To prove this, let us
denote by $\mathcal{F}^{(\ell)}$ the sigma algebra generated by the weigts and
biases in layer up to and including $\ell$. Observe that, conditional on
$\mathcal{F}^{(\ell)}$, we have that $D^{\leq
r}z_{i;\mathcal{A}}^{{}_{(\ell)}}$ are already independent for different $i$
and that, since the weights and biases are Gaussian, each is a centered
Gaussian with conditional covariance

$\mathrm{Cov}\left(D_{\alpha_{1}}^{J_{1}}z_{i;\alpha_{1}}^{(\ell+1)},\,D_{\alpha_{2}}^{J_{2}}z_{i;\alpha_{2}}^{(\ell+1)}~{}\bigg{|}~{}\mathcal{F}^{(\ell)}\right)=D_{\alpha_{1}}^{J_{1}}D_{\alpha_{2}}^{J_{2}}\Sigma_{\alpha_{1}\alpha_{2}}^{(\ell)},$

where

$\Sigma_{\alpha_{1}\alpha_{2}}^{(\ell)}=C_{b}+\frac{C_{W}}{n_{\ell}}\sum_{j=1}^{n_{\ell}}\sigma\left(z_{j;\alpha_{1}}^{(\ell)}\right)\sigma\left(z_{j;\alpha_{2}}^{(\ell)}\right).$

Thus, by the continuous mapping theorem, it suffices to show that for any
multi-indices $J_{1},J_{2}$ with $\left|J_{i}\right|\leq r$ and any
$\alpha_{1},\alpha_{2}\in\mathcal{A}$ we have

$\lim_{n\rightarrow\infty}\mathbb{E}\left[D_{\alpha_{1}}^{J_{1}}D_{\alpha_{2}}^{J_{2}}\Sigma_{\alpha_{1}\alpha_{2}}^{(\ell)}\right]\quad\text{exists
and is finite}$ (A.1)

and

$\lim_{n\rightarrow\infty}\mathrm{Var}\left[D_{\alpha_{1}}^{J_{1}}D_{\alpha_{2}}^{J_{2}}\Sigma_{\alpha_{1}\alpha_{2}}^{(\ell)}\right]=0.$
(A.2)

We establish (A.1) and (A.2) by induction on $\ell$ the following more general
statement.

######  Proposition A.1.

Denote by $N(n_{0},r)$ the number of derivatives of order at most $r$ in
$n_{0}$ variables. Consider any measureable function
$f:\mathbb{R}^{N(n_{0},r)\times\left|\mathcal{A}\right|}\rightarrow\mathbb{R}$
that is polynomially bounded, and define

$\mathcal{O}_{f}^{(\ell)}:=\frac{1}{n_{\ell}}\sum_{j=1}^{n_{\ell}}f\left(D^{\leq
r}z_{j;\mathcal{A}}\right).$

Then,

$\lim_{n\rightarrow\infty}\mathbb{E}\left[\mathcal{O}_{f}^{(\ell)}\right]\quad\text{exists
and is finite}$ (A.3)

and

$\lim_{n\rightarrow\infty}\mathrm{Var}\left[\mathcal{O}_{f}^{(\ell)}\right]=0.$
(A.4)

###### Proof.

We proceed by induction, starting with $\ell=1$. Since weights and biases are
Gaussian, the vectors $D^{\leq r}z_{i;\mathcal{A}}^{(1)}$ are independent for
all $i$ and jointly Gaussian. The polynomial growth assumption on $f$ show the
moments of $f(x)$ are finite if $x$ is Gaussian. This allows us to apply the
SLLN to conclude both (A.3) and (A.4).

Let us now assume we have proved (A.1) and (A.2) for layers $1,\ldots,\ell$.
We start by fixing any polynomially bounded $f$ and establishing (A.1) at
layer $\ell+1.$ We have

$\displaystyle\mathbb{E}\left[\mathcal{O}_{f}^{(\ell+1)}\right]$
$\displaystyle=\mathbb{E}\left[f\left(D^{\leq
r}z_{1;\mathcal{A}}\right)\right].$

As above, conditionl on $\mathcal{F}^{(\ell)}$, we have the following equality
in distribution:

$D^{\leq r}z_{1;\mathcal{A}}\stackrel{{\scriptstyle d}}{{=}}\left(\Sigma^{\leq
r,(\ell)}\right)^{1/2}Z,\qquad
Z\sim\mathcal{N}\left(0,I_{N(n_{0},r)\times\mathcal{A}}\right)$ (A.5)

where $Z$ is independent of the conditional covariance matrix

$\Sigma^{\leq
r,(\ell)}=\left(D_{\alpha_{1}}^{J_{1}}D_{\alpha_{2}}^{J_{2}}\Sigma_{\alpha_{1}\alpha_{2}}^{(\ell)}\right)_{\alpha_{1},\alpha_{2}\in\mathcal{A}}.$

The key observation is that each entry of $\Sigma^{\leq r,(\ell)}$ is of the
form $\mathcal{O}_{f}^{(\ell)}$ for polynomially bounded $f$. Hence, we may
apply the inductive hypothesis to conclude that there exists a matrix
$\overline{\Sigma}^{{}_{\leq r,(\ell)}}$ such that the following convergence
in distribution holds

$\Sigma^{\leq r,(\ell)}\quad\stackrel{{\scriptstyle
d}}{{\longrightarrow}}\quad\overline{\Sigma}^{\leq r,(\ell)}\qquad\text{ as
}\quad n\rightarrow\infty.$

The polynomial growth assumption on $f$ together with the Skorohod
representation theorem and dominated convergence show that

$\lim_{n\rightarrow\infty}\mathbb{E}\left[f\left(D^{\leq
r}z_{1;\mathcal{A}}\right)\right]=\mathbb{E}\left[f\left(\left(\overline{\Sigma}^{\leq
r,(\ell)}\right)^{1/2}Z\right)\right]=:\overline{\mathcal{O}}_{f}^{(\ell+1)}\quad\text{exists
and is finite}.$

This proves (A.3). To show (A.4), we proceed similarly. Namely, we have

$\displaystyle\mathrm{Var}\left[\mathcal{O}_{f}^{(\ell+1)}\right]$
$\displaystyle=\frac{1}{n_{\ell+1}}\mathrm{Var}\left[f\left(D^{\leq
r}z_{1;\mathcal{A}}^{(\ell+1)}\right)\right]+\left(1-\frac{1}{n_{\ell+1}}\right)\mathrm{Cov}\left(f\left(D^{\leq
r}z_{1;\mathcal{A}}^{(\ell+1)}\right),\,f\left(D^{\leq
r}z_{2;\mathcal{A}}^{(\ell+1)}\right)\right).$

Note that

$\mathrm{Var}\left[f\left(D^{\leq
r}z_{1;\mathcal{A}}^{(\ell+1)}\right)\right]\leq\mathbb{E}\left[\frac{1}{n}\sum_{j=1}^{n_{\ell}}\left[f\left(D^{\leq
r}z_{1;\mathcal{A}}^{(\ell+1)}\right)\right]^{2}\right].$

Hence, since $f^{2}$ is also polynomially bounded we have already shown that
(A.3) holds at layer $\ell+1$, we see that

$\mathrm{Var}\left[\mathcal{O}_{f}^{(\ell+1)}\right]=\mathrm{Cov}\left(f\left(D^{\leq
r}z_{1;\mathcal{A}}^{(\ell+1)}\right),\,f\left(D^{\leq
r}z_{2;\mathcal{A}}^{(\ell+1)}\right)\right)+O(n^{-1}).$

Next, using that conditional on $\mathcal{F}^{(\ell)}$ the vectors $D^{\leq
r}z_{i;\mathcal{A}}^{(\ell+1)}$ are independent for different $i$ we conclude
from the law of total covariance that

$\mathrm{Cov}\left(f\left(D^{\leq
r}z_{1;\mathcal{A}}^{(\ell+1)}\right),\,f\left(D^{\leq
r}z_{2;\mathcal{A}}^{(\ell+1)}\right)\right)\leq\mathrm{Var}\left[\mathbb{E}\left[f\left(D^{\leq
r}z_{1;\mathcal{A}}^{(\ell+1)}\right)~{}\bigg{|}~{}\mathcal{F}^{(\ell)}\right]\right].$

Combining the equality in distribution (A.5) with the polynomial growth
condition on $f$ and the dominated convergence theorem we find

$\lim_{n\rightarrow\infty}\mathrm{Var}\left[\mathbb{E}\left[f\left(D^{\leq
r}z_{1;\mathcal{A}}^{(\ell+1)}\right)~{}\bigg{|}~{}\mathcal{F}^{(\ell)}\right]\right]=\mathrm{Var}\left[\mathbb{E}\left[f\left(\left(\overline{\Sigma}^{\leq
r,(\ell)}\right)^{1/2}Z\right)\right]\right]=0.$

This completes the proof that (A.4) holds at infinite width, establishing
Proposition A.1.

∎

##  Appendix B Infinite Width Analysis of Tanh-like Non-linearities

The purpose of this section is to derive some basic properties of the infinite
width variance recursion

$\kappa_{\alpha\alpha}^{(\ell+1)}=C_{b}+C_{W}\left\langle\sigma(z)^{2}\right\rangle_{\kappa_{\alpha\alpha}^{(\ell)}}.$
(B.1)

We abbreviate

$\sigma_{j}:=\frac{1}{j!}\frac{d^{j}}{dx^{j}}\bigg{|}_{x=0}\sigma(x)$

and consider here the case when $\sigma$ that is a tanh-like non-linearity in
the sense that $\sigma$ satisfies:

  * •

$\sigma$ is smooth at $0$ with $\sigma_{1}\neq 0$

  * •

$\sigma$ has the opposite sign as its second derivative

$\text{for almost every
}z,~{}\mathrm{sgn}\left(\sigma(z)\sigma^{\prime\prime}(z)\right)=-1.$ (B.2)

Note that this forces $\sigma_{2}=0$ and

$a:=-\frac{6\sigma_{3}}{\sigma_{1}}>0.$

  * •

$\sigma$ is sub-linear:

$\exists C>0\,\text{ s.t. }\forall
z\in\mathbb{R}\,\left|\sigma(z)\right|\leq\left|\sigma_{1}z\right|,$ (B.3)

  * •

$\sigma$ is controlled by its first few non-zero Taylor series coefficients at
$0$:

$\exists C\geq 0\text{ s.t. }\forall z\geq
0,\quad\sigma_{1}z+\sigma_{3}z^{3}\leq\sigma(z)\leq\sigma_{1}z+\sigma_{3}z^{3}+Cz^{4}$
(B.4)

We will be interested in understanding the recursion (B.1) at criticality in
the sense defined in §4.1. Specifically, we remind the reader that this means
we choose $C_{b},C_{W}$ so that

$\displaystyle\exists K_{*}\geq 0\quad\text{ s.t. }\quad K_{*}$
$\displaystyle=C_{b}+C_{W}\left\langle\sigma^{2}(z)\right\rangle_{K_{*}}$
$\displaystyle\chi_{||}(K_{*})$
$\displaystyle=\frac{C_{W}}{2}\left\langle\partial^{2}(\sigma(z)^{2})\right\rangle_{K_{*}}=1$
$\displaystyle\chi_{\perp}(K_{*})$
$\displaystyle=C_{W}\left\langle(\sigma^{\prime}(z))^{2}\right\rangle_{K_{*}}=1.$

Before stating our main result (Proposition B.1), let us explain intuitively
what we expect. First of all, as we shall see in Proposition B.1, $\tanh$-like
non-linearities requires $K_{*}=0$ for criticality. Second, by Taylor
expanding the recursion (2.4) around small values of
$K_{\alpha\alpha}^{(\ell)}$ we find

$\displaystyle K_{\alpha\alpha}^{(\ell+1)}$
$\displaystyle=K_{\alpha\alpha}^{(\ell)}-a\left(K_{\alpha\alpha}^{(\ell)}\right)^{2}+O\left(\left(K_{\alpha\alpha}^{(\ell)}\right)^{3}\right).$

This is well-approximated by the ODE

$\frac{d}{dt}K(t)=-aK(t)^{2},$

whose solution is

$K(t)=\left(at+\frac{1}{K(0)}\right)^{-1}.$

This form for the solution has two important properties that we will check in
Proposition B.1 hold for the actual solution $K_{\alpha\alpha}^{(\ell)}$ to
the discrete difference equation (2.4):

  * •

At large $t$, $K(t)$ tends to zero like $1/at$ plus an error of size roughly
$O(t^{-2})$.

  * •

The leading order behavior of $K(t)$ at large $t$ is independent of the
initial condition.

######  Proposition B.1.

If $\sigma$ is a tanh-like non-linearity in the sense defined above then
criticality is achieved for $\sigma$ only with

$K_{*}=0,\qquad C_{b}=0,\qquad\text{and}\qquad C_{W}=\sigma_{1}^{-2}.$ (B.5)

Moreover, for every $\delta\in(0,1)$ we have

$K_{\alpha\alpha}^{(0)}>0\quad\Rightarrow\quad\sup_{\ell\geq
1}\ell^{2-\delta}\left|K_{\alpha\alpha}^{(\ell)}-\frac{1}{a\ell}\right|<\infty.$
(B.6)

###### Proof.

Note that for any $K\geq 0$ we have

$\chi_{||}(K)=\chi_{\perp}(K)+C_{W}\left\langle\sigma(z)\sigma^{\prime\prime}(z)\right\rangle_{K}.$
(B.7)

Hence, at criticality, we must have

$\left\langle\sigma(z)\sigma^{\prime\prime}(z)\right\rangle_{K_{*}}=0.$

But due to assumption (B.2) we have

$K>0\quad\Longrightarrow\quad\left\langle\sigma(z)\sigma^{\prime\prime}(z)\right\rangle_{K}<0.$

Thus, we indeed find that we must have $K_{*}=0$ at criticality. Hence, in
light of (B.7) criticality is equivalent to the system of equations

$K_{*}=0=C_{b}+C_{W}\sigma(0)^{2},\qquad\chi_{||}(0)=\chi_{\perp}(0)=C_{W}\left\langle(\sigma^{\prime}(z))^{2}\right\rangle_{0}=C_{W}\sigma_{1}^{2}=1.$

This system has a unique solution:

$C_{b}=0,\quad C_{W}=\sigma_{1}^{-2},$

completing the proof of the criticality conditions (B.5). Let us now establish
(B.6). First note that at criticality the sub-linearity condition (B.3)
guarantees that for all $\delta>0$ there exists $c_{\delta}\in(0,1)$ such that

$K>\delta\quad\Longrightarrow\quad
C_{W}\left\langle\sigma(z)^{2}\right\rangle_{K}<(1-c_{\delta})\left\langle
z^{2}\right\rangle_{K}=(1-c_{\delta})K.$

Hence, for all $K,\delta>0$ there exists $\ell_{0}\geq 1$ such that

$K_{\alpha\alpha}^{(0)}\leq K\qquad\Longrightarrow\qquad
K_{\alpha\alpha}^{(\ell)}\leq\delta\quad\forall\ell\geq\ell_{0}.$ (B.8)

In particular, $K_{\alpha\alpha}^{{}_{(\ell)}}$ is monotonically decreasing
and converges to $K_{*}=0$ as $\ell$ grows. Let us now define for each
$\ell\geq 1$

$K_{\alpha\alpha}^{(\ell)}=:\frac{1}{a\ell}+\epsilon^{(\ell)},\qquad
a:=-6\frac{\sigma_{3}}{\sigma_{1}}>0,$

where $a$ is positive due to (B.2). Note that since
$K_{\alpha\alpha}^{(\ell)}$ tends to zero with $\ell$, so does
$\epsilon^{(\ell)}$. Let us agree that for any $t\in\mathbb{R}$ the symbol
$t^{+}$ (resp. $t^{-}$) means that for $\ell$ sufficiently large we may make
the constant $t^{+}$ (resp. $t^{-}$) arbitrary close to $t$ from above (resp.
below). In order to prove (B.6), we start with the following elementary
estimate.

######  Lemma B.2.

For all $\ell\geq 1$, we have

$\displaystyle\epsilon^{(\ell+1)}~{}\geq~{}-\frac{1}{a\ell^{2}(\ell+1)}+\epsilon^{(\ell)}\left(1-\frac{2}{\ell}-a\epsilon^{(\ell)}\right).$
(B.9)

Further, there exists a constant $C>0$ depending only on $\sigma$ with the
following property. For all $K>0$ there exists a constant $\ell_{0}\geq 1$ so
that if $K_{\alpha\alpha}^{{}_{(0)}}\leq K$, then for all $\delta\in(0,1)$ we
have

$\displaystyle\epsilon^{(\ell+1)}~{}\leq~{}\frac{C}{\ell^{3}}+\epsilon^{(\ell)}\left(1-\frac{2-\delta}{\ell}\right),\qquad\forall~{}\ell\geq\ell_{\delta}:=\max\left\\{\frac{C}{\delta},\,\frac{2C}{a},\,\ell_{0}\right\\}.$
(B.10)

###### Proof.

Plugging in the estimates (B.4) into the recursion (B.1) yields for some $C>0$
depending only on $\sigma$

$\displaystyle\epsilon^{(\ell+1)}$
$\displaystyle\leq\frac{C}{\ell^{3}}+\epsilon^{(\ell)}\left[1-\frac{2}{\ell}+\frac{C}{\ell^{2}}\right]+\left(\epsilon^{(\ell)}\right)^{2}\left(-a+\frac{C}{\ell}\right)+C(\epsilon^{(\ell)})^{3}$

Note that for all $\ell\geq 2C/a$ we have $-a+C/\ell\leq 0$. Hence, for all
$\ell\geq\max\left\\{2C/a,C/\delta\right\\}$ we have

$\displaystyle\epsilon^{(\ell+1)}$
$\displaystyle\leq\frac{C}{\ell^{3}}+\epsilon^{(\ell)}\left[1-\frac{2-\delta}{\ell}\right]+C(\epsilon^{(\ell)})^{3}.$

Moreover, if $\epsilon^{(\ell)}\leq 0$, then $(\epsilon^{(\ell)})^{3}\leq 0$.
If on the other hand $\epsilon^{(\ell)}\geq 0$, then from (B.8) we find that
there for all $K>0$ there exists $\ell_{0}$ so that
$(\epsilon^{(\ell)})^{3}\leq a(\epsilon^{(\ell)})^{2}/4$ for all
$\ell\geq\ell_{0}.$ Hence, in all cases, for each $\delta\in(0,1)$ if
$\ell\geq\max\left\\{2C/a,C/\delta,\ell_{0}\right\\},$ we find

$\displaystyle\epsilon^{(\ell+1)}$
$\displaystyle\leq\frac{C}{\ell^{3}}+\epsilon^{(\ell)}\left[1-\frac{2-\delta}{\ell}\right],$

as claimed. The lower bound follows from a similar but simpler computation. ∎

Fix $\delta\in(0,1)$. The relation (B.10), together with Lemma 6.2, show that
for all $K>0$ there exists some $C^{\prime}>0$ depending on $\delta,\sigma,K$
such that if $K_{\alpha\alpha}^{{}_{(0)}}\leq K$ then

$\epsilon^{(\ell+1)}\leq\sum_{\ell^{\prime}=\ell_{\delta}}^{\ell}\frac{C}{\ell^{3}}\prod_{\ell^{\prime\prime}=\ell^{\prime}+1}^{\ell}\left(1-\frac{2^{-}}{\ell}\right)\leq
C^{\prime}\left[\frac{1}{\ell^{2}}+\epsilon^{(\ell_{\delta})}\frac{1}{\ell^{2-\delta}}\right].$

This shows that

$\forall\delta\in(0,1)~{}\exists\ell_{\delta}\geq 1~{}\text{ s.t.
}\quad\epsilon^{(\ell)}\leq\frac{1}{\ell^{2-\delta}}\quad\forall\ell\geq\ell_{\delta}.$
(B.11)

To conclude (B.6) it therefore remains to deduce that

$\forall K_{1},K_{2}>0,\,\delta\in(0,1)~{}\exists\ell_{\delta}\geq 1~{}\text{
s.t. }\quad
K_{1}<K_{\alpha\alpha}^{(0)}<K_{2}\quad\Longrightarrow\quad\epsilon^{(\ell)}\geq-\frac{1}{\ell^{2-\delta}}\quad\forall\ell\geq\ell_{\delta}.$
(B.12)

To aid with this, we will need the following

######  Lemma B.3.

For any $\delta\in(0,1)$ there exists $\ell_{\delta}\geq 1$ with the property
that if $\ell\geq\ell_{\delta}$ then

$\epsilon^{(\ell)}\geq-\ell^{-2+\delta}\quad\Longrightarrow\quad\epsilon^{(\ell+1)}\geq-(\ell+1)^{-2+\delta}.$

###### Proof.

Suppose $\epsilon^{(\ell)}\geq-\ell^{-2+\delta}$. The lower bound in (B.9)
yields for some $C,C^{\prime}>0$

$\displaystyle\epsilon^{(\ell+1)}+\left(\ell+1\right)^{-2+\delta}$
$\displaystyle\geq\left(\ell+1\right)^{-2+\delta}\left[1-\left(1+\ell^{-1}\right)^{2-\delta}\right]-2\ell^{-3+\delta}-C\ell^{-4+2\delta}$
$\displaystyle\geq\delta\ell^{-3+\delta}-C^{\prime}(\ell^{-3}+\ell^{-4+2\delta}),$

which is non-negative for all $\ell$ sufficiently large. ∎

We are now in a position to establish (B.12). In light of the previous Lemma
we need only consider the case when

$\forall\delta\in(0,1)~{}\exists~{}\ell_{\delta}\geq
1\quad\text{s.t.}\quad\epsilon^{(\ell_{\delta})}<-\ell^{2-\delta}.$

Note that in light of the upper bound (B.11) we find that for all
$\delta\in(0,1)$ there exists $\ell_{\delta}\geq 1$ and $C_{\delta}>0$ so that
for all $\ell\geq\ell_{\delta}$ we have

$\displaystyle K_{\alpha\alpha}^{(\ell+1)}\geq
K_{\alpha\alpha}^{(\ell)}\left(1-aK_{\alpha\alpha}^{(\ell)}\right)\geq
K_{\alpha\alpha}^{(\ell)}\left(1-a\left(-\frac{1}{a\ell}+C_{\delta}\ell^{-2+\delta}\right)\right)=K_{\alpha\alpha}^{(\ell)}\left(1-\frac{1}{\ell}-aC_{\delta}\ell^{-2+\delta}\right).$

Hence, assuming $K_{2}\geq K_{\alpha\alpha}^{(0)}\geq K_{1}>0,$ we may iterate
this inequality to find that there exists $c>0$ depending on $K_{1},K_{2}$ and
$\ell_{0}\geq 1$ so that

$K_{\alpha\alpha}^{(\ell)}\geq\frac{c}{a\ell}\qquad\forall\ell\geq\ell_{0}.$

Hence, since $\epsilon^{(\ell)}<0$ for all $\ell\geq\ell_{\delta}$ we find for
all $\ell\geq\max\left\\{\ell_{0},\ell_{\delta}\right\\}$ that

$-a(\epsilon^{(\ell)})^{2}\geq\epsilon^{(\ell)}\frac{1-c}{\ell}$

Substituting this into the lower bound (B.9), we find that for all
$\ell\geq\max\left\\{\ell_{0},\ell_{\delta}\right\\}$

$\epsilon^{(\ell+1)}\geq-\frac{C^{\prime}}{\ell^{3}}+\epsilon^{(\ell)}\left(1-\frac{1+c}{\ell}\right).$

Since $\epsilon^{(\ell_{\delta})}<0$, we see by applying Lemma 6.2 that there
exists $C>0$ so that for all
$\ell\geq\max\left\\{\ell_{0},\ell_{\delta}\right\\}$

$\epsilon^{(\ell+1)}\geq-\frac{C}{\ell^{1+c}}.$

But now we can bootstrap this estimate. Indeed, for any $\delta\in(0,1)$ we
substitute this into the lower bound (B.9) to find that for all $\ell$
sufficiently large

$\epsilon^{(\ell+1)}\geq-\frac{C^{\prime}}{\ell^{3}}+\epsilon^{(\ell)}\left(1-\frac{2-\delta}{\ell}\right).$

Again applying Lemma 6.2 yields that for all $\ell$ sufficiently large

$\epsilon^{(\ell+1)}\geq-\frac{C}{\ell^{2-\delta}}.$

This completes the proof.

∎

##  Appendix C Exact Solutions for $1$-homogeneous activations

In this appendix, we collect several known computations related to the
distribution of neuron activations in random fully connected networks with
$1-$homogeneous activations. Specifically, we fix a one homogeneous non-
linearity

$\sigma(t)=(a_{+}{\bf 1}_{t>0}+a_{-}{\bf 1}_{t<0})t$

and consider a random fully connected neural network with input dimension
$n_{0}$, output dimension $n_{L+1}$, hidden layer widths
$n_{1},\ldots,n_{\ell}$, and non-linearity $\sigma$ that is tuned to
criticality in the sense that

$C_{b}=0,\qquad C_{W}=\frac{2}{a_{+}^{2}+a_{-}^{2}}.$

Our first task is to derive in §C.1 a known exact formula for the infinite
width covariance $K_{\alpha\beta}^{(\ell+1)}$ as a function of
$K_{\alpha\alpha}^{(\ell)},K_{\alpha\beta}^{(\ell)},K_{\beta\beta}^{(\ell)}$.
Then, in Section §C.2, we sketch a derivation of the limiting distribution
(4.7) of a neuron pre-activation in the double scaling limit
$n,L\rightarrow\infty,L/n\rightarrow\gamma$.

###  C.1 Covariance Propagation in Random Fulluy Connected $1$-homogeneous
Networks

In this section, we consider two network inputs $x_{\alpha},x_{\beta}$ of the
same norm:

$K_{\alpha\alpha}^{(0)}=\frac{1}{n_{0}}\left|\left|x_{\alpha}\right|\right|^{2}=K=\frac{1}{n_{0}}\left|\left|x_{\beta}\right|\right|^{2}=K_{\beta\beta}^{(0)},\qquad
K>0.$ (C.1)

Let us define

$\epsilon_{\alpha\beta}^{(\ell)}:=\frac{1-\mathrm{Corr}_{\alpha\beta}^{(\ell)}}{2},\qquad\mathrm{Corr}_{\alpha\beta}^{(\ell)}:=\frac{K_{\alpha\beta}^{(\ell)}}{\left(K_{\alpha\alpha}^{(\ell)}K_{\beta\beta}^{(\ell)}\right)^{1/2}}$

Our goal is to derive the following explicit recursion for
$\epsilon_{\alpha\beta}^{(\ell+1)}$ in terms of
$\epsilon_{\alpha\beta}^{(\ell)}$. This derivation follows the approach in
§5.5 [53]. To the author’s knowledge, the following formula (or really
something equivalent) was first derived in [cho2009kernel].

######  Proposition C.1 (Correlation propagation for $1-$homogeneous
activation functions).

At criticality, we have the following exact formula:

$\displaystyle 1-2\epsilon_{\alpha\beta}^{(\ell+1)}$
$\displaystyle=\frac{2C_{W}(a_{+}-a_{-})^{2}}{\pi}\left[\frac{1}{2}\sqrt{\epsilon_{\alpha\beta}^{(\ell)}(1-\epsilon_{\alpha\beta}^{(\ell)})}+\left(\frac{1}{2}-\epsilon_{\alpha\beta}^{(\ell)}\right)\cos^{-1}\left(\sqrt{\epsilon_{\alpha\beta}^{(\ell)}}\right)\right]$
$\displaystyle+C_{W}a_{+}a_{-}(1-2\epsilon_{\alpha\beta}^{(\ell)})$ (C.2)

In particular, taking $\varepsilon_{\alpha\beta}^{(\ell)}$ small we find

$\varepsilon_{\alpha\beta}^{(\ell+1)}=\varepsilon_{\alpha\beta}^{(\ell)}-\frac{4}{3\pi}\left(\varepsilon_{\alpha\beta}^{(\ell)}\right)^{3/2}+O\left(\left(\varepsilon_{\alpha\beta}^{(\ell)}\right)^{5/2}\right).$

Hence, as $\ell\rightarrow\infty$,

$\varepsilon_{\alpha\beta}^{(\ell)}=\frac{2}{3\pi}\ell^{-2}(1+o(1)).$

###### Proof.

We have from Theorem 2.2 that

$K_{\alpha\beta}^{(\ell+1)}=C_{b}+C_{W}\left\langle\sigma(z_{\alpha})\sigma(z_{\beta})\right\rangle_{K^{(\ell)}},$
(C.3)

where we recall that the brackets above mean the average with respect to the
Gaussian distribution

$\left(\begin{array}[]{c}z_{\alpha}\\\
z_{\beta}\end{array}\right)~{}\sim~{}\mathcal{N}\left(0,\left(\begin{array}[]{cc}K_{\alpha\alpha}^{(\ell)}&K_{\alpha\beta}^{(\ell)}\\\
K_{\alpha\beta}^{(\ell)}&K_{\beta\beta}^{(\ell)}\end{array}\right)\right).$

Since we are at criticality, we have

$C_{b}=0,\qquad C_{W}=\frac{2}{a_{+}^{2}+a_{-}^{2}}$

and that moreover

$K_{\alpha\alpha}^{(\ell)}=K_{\beta\beta}^{(\ell)}=K,$

where $K$ is the constant from (C.1). Our first step is to change from the
Gaussian variables $z_{\alpha},z_{\beta}$ to the new Gaussian variables

$\xi=\frac{z_{\alpha}+z_{\beta}}{2\sqrt{K}},\qquad\eta=\frac{z_{\alpha}-z_{\beta}}{2\sqrt{K}}.$

We have

$z_{\alpha}=\sqrt{K}(\xi+\eta),\qquad
z_{\beta}=\sqrt{K}\left(\xi-\eta\right).$

Moreover, writing

$\epsilon:=\epsilon_{\alpha\beta}^{(\ell)}=\frac{1}{2}\left(1-\frac{K_{\alpha\beta}^{(\ell)}}{\left(K_{\alpha\alpha}^{(\ell)}K_{\beta\beta}^{(\ell)}\right)^{1/2}}\right)$

we find

$\displaystyle\mathrm{Var}[\xi]=1-\varepsilon,\qquad\mathrm{Var}[\eta]=\varepsilon,\qquad\mathrm{Cov}[\xi,\eta]=0.$

Hence, the right hand side of the recursion (C.3) reads

$C_{W}K\int_{\mathbb{R}}\int_{\mathbb{R}}\sigma\left((1-\varepsilon)^{1/2}\xi+\varepsilon^{1/2}\eta\right)\sigma\left((1-\varepsilon)^{1/2}\xi-\varepsilon^{1/2}\eta\right)\exp\left[-\frac{1}{2}\left(\xi^{2}+\eta^{2}\right)\right]\frac{d\xi
d\eta}{2\pi}.$

Using the definition of $\sigma$ yields

$\displaystyle\sigma\left((1-\varepsilon)^{1/2}\xi+\varepsilon^{1/2}\eta\right)\sigma\left((1-\varepsilon)^{1/2}\xi-\varepsilon^{1/2}\eta\right)$
$\displaystyle\qquad=\left(a_{+}{\bf 1}_{\xi+\eta>0}+a_{-}{\bf
1}_{\xi+\eta<0}\right)\left(a_{+}{\bf 1}_{\xi-\eta>0}+a_{-}{\bf
1}_{\xi-\eta<0}\right)((1-\epsilon)\xi^{2}-\epsilon\eta^{2}).$

Changing variables $(\xi,\eta)\rightarrow(-\xi,-\eta)$ inside the integral and
averaging yields

$\displaystyle K_{\alpha\beta}^{(\ell+1)}$
$\displaystyle=C_{W}Ka_{+}a_{-}(1-2\epsilon)$
$\displaystyle+\frac{C_{W}K(a_{+}-a_{-})^{2}}{2}\int_{\mathbb{R}^{2}}{\bf
1}_{(1-\epsilon)\xi^{2}-\epsilon\eta^{2}>0}((1-\epsilon)\xi^{2}-\epsilon\eta^{2})\exp\left[-\frac{1}{2}\left(\xi^{2}+\eta^{2}\right)\right]\frac{d\xi
d\eta}{2\pi}.$

Passing to polar coordinates and explicitly computing the resulting integral
is now straightforward and completes the derivation of (C.2). ∎

###  C.2 Full Distribution of Neuron Pre-activations at a Single Input and the
Derivation of (4.7)

Our purpose in this section is to briefly recall an exact formula for the full
distribution of a neuron pre-activation $z_{i;\alpha}^{(L+1)}$. For this, note
that since $x_{\alpha}\mapsto z_{\alpha}^{(L+1)}$ is piecewise linear and the
event that the Jacobian $J_{x_{\alpha}}z_{\alpha}^{(L+1)}$ is not well-defined
at $x_{\alpha}$ has probability zero, we may write

$z_{\alpha}^{(L+1)}=J_{x_{\alpha}}z_{\alpha}^{(L+1)}x_{\alpha}.$

Next,

$J_{x_{\alpha}}z_{\alpha}^{(L+1)}=W^{(L+1)}D^{(L)}W^{(L)}\cdots
D^{(1)}W^{(1)},$ (C.4)

where $W^{(\ell)}$ are simply the weight matrices and

$D^{(\ell)}:=\mathrm{Diag}\left(\sigma^{\prime}(z_{i;\alpha}^{(\ell)}),\,i=1,\ldots,n_{\ell}\right).$

Arguing exactly as in Proposition 2 of [21], we have the following equality in
distribution:

$D^{(L)}W^{(L)}\cdots D^{(1)}W^{(1)}\stackrel{{\scriptstyle
d}}{{=}}A\widehat{D}^{(L)}W^{(L)}\cdots\widehat{D}^{(1)}W^{(1)},$

where $A$ is a diagonal matrix with iid $\pm 1$ entries on the diagonal that
is independent of $W^{(\ell)}$ and the diagonal matrices

$\widehat{D}^{(\ell)}=\mathrm{Diag}\bigg{(}\underbrace{a_{+}\xi_{i}^{(\ell)}+a_{-}(1-\xi_{i}^{(\ell)})}_{=:d_{i}^{(\ell)}},\,i=1,\ldots,n_{\ell}\bigg{)},\qquad\xi_{i}^{(\ell)}\sim\mathrm{Bernoulli}(1/2)\,\,iid.$

Combining this with (C.4) and recalling that the entries of $W^{(L+1)}$ are
iid centered Gaussians with variance $C_{W}/n_{L}$ yields

$z_{i;\alpha}^{(L+1)}\stackrel{{\scriptstyle
d}}{{=}}Z_{1}\cdot\left(\frac{C_{W}}{n_{L}}\right)^{1/2}\left|\left|\widehat{D}^{(L)}W^{(L)}\cdots\widehat{D}^{(1)}W^{(1)}x_{\alpha}\right|\right|,$

where $Z_{1}\sim\mathcal{N}(0,1)$ is independent of
$\widehat{D}^{(\ell)},W^{(\ell)},\,i=1,\ldots,L$. Further, due to the right
orthogonal invariance of the Gaussian matrices $W^{(\ell)}$ and the
normalization that the variance of the entries of $W^{(\ell)}$ is
$C_{W}/n_{\ell-11}$, we have that

$\displaystyle\log\left[\left(\frac{C_{W}}{n_{L}}\right)^{1/2}\left|\left|\widehat{D}^{(L)}W^{(L)}\cdots\widehat{D}^{(1)}W^{(1)}x_{\alpha}\right|\right|\right]$
$\displaystyle\qquad\stackrel{{\scriptstyle
d}}{{=}}\frac{1}{2}\log\left[\frac{C_{W}}{n_{0}}\left|\left|x_{\alpha}\right|\right|^{2}\right]+\sum_{\ell=1}^{L}\frac{1}{2}\log\left[\frac{C_{W}}{n_{L}}\left|\left|\widehat{D}^{(\ell)}\widehat{W}^{(\ell)}u^{(\ell)}\right|\right|^{2}\right]$

where $u^{(\ell)}\in\mathbb{R}^{n_{\ell-1}}$ is collection of deterministic
unit vectors and $\widehat{W}^{(\ell)}$ are independent random matrices with
iid standard Gaussian entries. The summands on the previous line are
independent and are each distributed like the logarithm of a randomly weighted
$\chi^{2}$ random viable:

$\frac{C_{W}}{n_{\ell}}\left|\left|\widehat{D}^{(\ell)}W^{(\ell)}u^{(\ell)}\right|\right|^{2}\stackrel{{\scriptstyle
d}}{{=}}\frac{C_{W}}{n_{\ell}}\sum_{j=1}^{n_{\ell}}\left(d_{i}^{(\ell)}\right)^{2}\left(Z_{i}^{(\ell)}\right)^{2},$

where $Z_{i}^{(\ell)}\sim\mathcal{N}(0,1)$ are iid and independent of
$d_{i}^{(\ell)}$. Putting this all together, we find that

$\displaystyle z_{i;\alpha}^{(L+1)}$ $\displaystyle\stackrel{{\scriptstyle
d}}{{=}}\left(\frac{C_{W}}{n_{0}}\left|\left|x_{\alpha}\right|\right|^{2}\right)^{1/2}\cdot
Z_{1}\cdot\prod_{\ell=1}^{L}\left(\frac{C_{W}}{n_{\ell}}\right)^{1/2}\left|\left|\widehat{D}^{(\ell)}W^{(\ell)}u^{(\ell)}\right|\right|$

is a product of $L+1$ independent random variables. Moreover, a direct
computation shows that

$\displaystyle\mathbb{E}\left[\log\left[\frac{C_{W}}{n_{\ell}}\sum_{j=1}^{n_{\ell}}\left(d_{i}^{(\ell)}\right)^{2}\left(Z_{i}^{(\ell)}\right)^{2}\right]\right]$
$\displaystyle=-\frac{1}{2}\mathrm{Var}\left[\frac{C_{W}}{n_{\ell}}\sum_{j=1}^{n_{\ell}}\left(d_{i}^{(\ell)}\right)^{2}\left(Z_{i}^{(\ell)}\right)^{2}\right]+O(n_{\ell}^{-2})$
$\displaystyle=-\frac{1}{2n_{\ell}}\left(6\frac{a_{+}^{4}+a_{-}^{4}}{(a_{+}^{2}+a_{-}^{2})^{2}}-1\right)+O(n_{\ell}^{-2})$

and also that

$\displaystyle\mathrm{Var}\left[\log\left[\frac{C_{W}}{n_{\ell}}\sum_{j=1}^{n_{\ell}}\left(d_{i}^{(\ell)}\right)^{2}\left(Z_{i}^{(\ell)}\right)^{2}\right]\right]$
$\displaystyle=\mathrm{Var}\left[\frac{C_{W}}{n_{\ell}}\sum_{j=1}^{n_{\ell}}\left(d_{i}^{(\ell)}\right)^{2}\left(Z_{i}^{(\ell)}\right)^{2}\right]+O(n_{\ell}^{-2})$
$\displaystyle=\frac{1}{n_{\ell}}\left(6\frac{a_{+}^{4}+a_{-}^{4}}{(a_{+}^{2}+a_{-}^{2})^{2}}-1\right)+O(n_{\ell}^{-2}).$

Combining the preceding two estimates, taking $n,L\rightarrow\infty$ with
$L/n\rightarrow\gamma$ and applying the CLT yields

$\lim_{\begin{subarray}{c}n,L\rightarrow\infty\\\
L/n\rightarrow\gamma\in[0,\infty)\end{subarray}}z_{i;\alpha}^{(L)}\quad\stackrel{{\scriptstyle
d}}{{\longrightarrow}}\quad\left(\frac{C_{W}}{n_{0}}\left|\left|x_{\alpha}\right|\right|^{2}\right)^{1/2}Z_{1}\exp\left[-\mu(\gamma,a_{+},a_{-})+\sigma(\gamma,a_{+},a_{-})Z_{2}\right],$

where

$\mu(\gamma,a_{+},a_{-})=\sigma^{2}(\gamma,a_{+},a_{-}):=\frac{\gamma}{4}\left(6\frac{a_{+}^{4}+a_{-}^{4}}{(a_{+}^{2}+a_{+}^{2})^{2}}-1\right),\quad
Z_{1},Z_{2}\sim\mathcal{N}(0,1)\text{ iid}.$

This is precisely the statement of (4.7).


# Iterative Shrinking for Referring Expression Grounding Using Deep
Reinforcement Learning

Mingjie Sun1,2 Jimin Xiao1, corresponding author Eng Gee Lim1
1Xi’an Jiaotong-Liverpool University, 2University of Liverpool
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

11footnotetext: The work was supported by National Natural Science Foundation
of China under 61972323 and Key Program Special Fund in XJTLU under KSF-T-02,
KSF-P-02.
https://github.com/insomnia94/ISREG

In this paper, we are tackling the proposal-free referring expression
grounding task, aiming at localizing the target object according to a query
sentence, without relying on off-the-shelf object proposals. Existing
proposal-free methods employ a query-image matching branch to select the
highest-score point in the image feature map as the target box center, with
its width and height predicted by another branch. Such methods, however, fail
to utilize the contextual relation between the target and reference objects,
and lack interpretability on its reasoning procedure. To solve these problems,
we propose an iterative shrinking mechanism to localize the target, where the
shrinking direction is decided by a reinforcement learning agent, with all
contents within the current image patch comprehensively considered. Besides,
the sequential shrinking processes enable to demonstrate the reasoning about
how to iteratively find the target. Experiments show that the proposed method
boosts the accuracy by 4.32% against the previous state-of-the-art (SOTA)
method on the RefCOCOg dataset, where query sentences are long and complex
with many targets referred by other reference objects.

##  1 Introduction

Figure 1: Illustration of the difference between (a) existing feature-point
level matching methods, and (b) the proposed iterative shrinking method. The
query sentence for the target in this image is “the cat above the shelf”. In
(a), dots depict the feature points within the image feature map, with the
surrounding area representing its corresponding image region. Red dots
indicate the feature points whose corresponding image regions may cover the
target (i.e., the cat on the shelf) or distracting objects (i.e., cats on
other places), while black dots are unrelated feature points. It can be
observed that there is no such feature point whose image region can cover both
the target object (i.e., cat) and the reference object (i.e., shelf). In (b),
for each iteration, the area in the dashed box indicates the image patch after
shrinking, and the red arrow depicts the shrinking direction, which is decided
by comprehensively considering all contents in the image patch before
shrinking.

The aim of referring expression grounding (REG) is to recognize and localize
the target object in an image according to its query sentence (referring
expression), which requires joint comprehension in both visual and linguistic
domains. REG is a fundamental multi-modality task, serving as the basis for
many downstream tasks, including the visual question answering [15, 4, 17, 52,
20, 1, 46], image caption [9, 5, 7, 34, 63, 47, 42], image-text matching [25,
63, 3, 62, 6, 49, 21], etc. It attracts much attention from both computer
vision (CV) and natural language processing (NLP) areas in recent years.

Conventional methods formulate REG as a region-retrieval problem [59, 61, 54,
51, 26, 27, 10], with proposals of all candidate objects provided in advance.
The candidate proposals can be either provided from the bounding box ground-
truth or generated by a pre-trained object detector (e.g., Faster RCNN [38]).
The matching networks of these REG models predict the similarity score between
the query and each proposal, with the highest-score proposal selected as the
target object. In this way, conventional REG methods highly rely on the
ground-truth bounding boxes or an accurate object detector which requires a
lot of extra data to train it in advance. To overcome these shortcomings, some
proposal-free methods attempt to predict the REG result without object
proposals.

All existing proposal-free REG methods [22, 57, 41, 56] directly follow the
pipeline of one-stage detector (e.g., YOLOv3 [37]) and adopt a two-branch
style network, with the first branch to calculate the similarity score between
the query sentence and each feature point within the image feature map, and
the second branch to generate its bounding box coordinates. The predicted
bounding box of the feature point with the highest score is viewed as the
final result.

These methods, with the matching process conducted between the query sentence
and each image feature point, perform well for simple queries with the target
described by its own attribute (e.g., “man in blue”), but it is difficult for
them to deal with complex queries, especially when the target is referred by
another reference object. As can be observed from Fig.1.(a), since there is no
such a feature point whose corresponding image region covers both the target
“cat” and the reference object “shelf”, the contextual relation between the
target and the reference object, serving as the key to distinguish the target
from other distracting objects, cannot be fully utilized in such a matching
process. Thus, the REG performance is greatly compromised.

Another shortcoming of these methods is lack of interpretability. As the
matching network predicts the final matching scores of all feature points in
one step, its inner reasoning procedure is hidden and invisible. Thus, if the
matching model fails, it is formidable to analyze the causes.

To tackle these problems simultaneously, we formalize REG as a sequence of
image-level shrinking processes. Within each iteration, the image shrinks
along a certain direction, with a non-target image region removed. After
several shrinking iterations, only the target image region remains, and it is
viewed as the final result. The shrinking direction in each iteration is
predicted by a trainable network. As the optimal shrinking direction is
uncertain for each iteration, conventional supervised training is not suited.
We propose to model it as a Markov decision process [14] and adopt
reinforcement learning (RL) to tackle it. RL only requires a “feedback” or
“reward” after each shrinking step, rather than the exact supervision label.
Besides, RL considers not only the current reward but also the potential
reward in future, which further improves the performance.

Our proposed method can better utilize the contextual relation between the
target and reference objects because the shrinking direction is decided by
comprehensively considering all objects within the current image patch. For an
instance, as shown in Fig.1.(b), in the first iteration, the image region
where a black cat lies on the chair is removed (i.e., shrinking towards
right), because “chair” does not occur in the query. In the second iteration,
after analyzing the spatial relation between each candidate cat and the
reference object “shelf”, it is decided to remove the image region where a cat
lies inside the shelf (i.e., shrinking towards top), due to its mismatching
spatial relation against the query. Ultimately, only the image region
accurately covering the target cat remains. As the relation information in a
query is fully utilized, the proposed method can better deal with complex
queries and images (e.g., RefCOCOg [30]), whilst existing matching methods
fail to handle such cases (Fig.1.(a)).

To sum up, this paper has three main contributions:

  * •

We make the earliest attempt to solve REG as a conditional decision-making
process and build the first RL-based REG framework. Thanks to these iterative
decisions, the reasoning about how to localize the target can be visualized
step by step.

  * •

We formalize REG as a sequence of image-level shrinking processes, with the
shrinking direction in each iteration decided by an RL agent after
comprehensively considering all objects in the image patch, allowing the
relation information in a query to be fully utilized.

  * •

The proposed method boosts the accuracy by 4.32% against the previous SOTA
method [22] on the RefCOCOg dataset, where query sentences are long and
complex, with many targets referred by other reference objects. An average
accuracy gain of 1.33% on RefCOCOg, RefCOCO+ and RefCOCO is also achieved.

Figure 2: Architecture of our method where the blue lines indicate the states
corresponding to different scale levels, and the yellow circle represents the
optimizing of the actor and critic networks within each iteration.

##  2 Related Work

###  2.1 Referring Expression Grounding

REG can be classified into two categories, including proposal-based and
proposal-free. For many early proposal-based REG methods, the entire query
sentence is directly encoded through a single language embedding network
(e.g., LSTM [12]), without considering the variance among different types of
query sentences [40, 50, 30, 60]. To solve this problem, Yu et al. [59]
propose an attention mechanism to decompose the query sentence into three
linguistic components, related to subject appearance, location and
relationship to other objects. The ultimate matching result is generated after
comprehensively considering all three components. To prevent the attention
mechanism from only focusing on the most dominant features of both modalities,
an erasing mechanism is proposed in [28], where the most dominant linguistic
or visual information is discarded to drive the model to discover more
complementary linguistic-visual correspondences.

In the proposal-free REG setting, Sadhu et al. [57] combine the linguistic
feature of the query sentence and the visual feature from the image to
generate a multi-modal feature map, and predict the binary classification
scores (foreground or background) for all points and their corresponding
bounding box coordinates. RCCF [22] adopts a correlation filter to calculate
the similarity between the query sentence and each point in the image feature
map, and the point with the highest similarity score is viewed as the center
of the target object. Then, the size and offset are predicted by another
network to generate the final bounding box for the target.

The aforementioned proposal-free REG methods [57, 22] only consider a local
image region and ignore the contextual object relations. Differently, we
propose an iterative shrinking mechanism to predict the target object
location, where the shrinking direction within each iteration is decided by
comprehensively considering all objects in the current image, allowing the
relation information in a query to be better utilized.

###  2.2 Deep Reinforcement Learning

Deep reinforcement learning algorithms have achieved great success on
sequential decision-making problems. “Actor-critic” [19] is a popular RL
framework that comes from several previous RL frameworks including deep
Q-learning [33] and policy gradient [45] which are valued-based and policy-
based strategies, respectively.

RL has been applied to many multi-modal tasks. Rennie et al. [39] apply the
policy gradient to train the image caption network based on its baseline
method [53]. Specifically, the image caption network is viewed as an RL agent,
whose action is to predict the next word. The state of the RL agent is the
cells and hidden variables of the LSTM, as well as their corresponding
attention weights. The reward function is designed according to the sentence-
level evaluation metric, CIDEr score [48], representing the difference between
the generated sentence and the ground-truth one. Yu et al. [61] adopt RL to
guide the referring sentence generator towards less ambiguous expression.
Different from [39], the reward function is designed according to the
similarity score between the generated sentence and the object image patch,
calculated by a pre-trained region-language matching network.

However, to the best of our knowledge, RL has never been used to tackle the
REG task. All existing REG methods follow the static region-sentence matching
strategy, leaving no space to make any sequential decisions. In this paper, we
abandon the traditional matching strategy, and make the first attempt to
formulate REG as a sequential shrinking processes, where an RL agent is
trained to predict the shrinking direction within each iteration.

##  3 Methodology

###  3.1 Overview

Given the image $img$ and the query sentence $q$, the target object is
localized through a sequence of shrinking iterations, with $i$ indicating the
index of each iteration. Specifically, for a certain iteration $i$, the
current image patch $p_{i}$ shrinks along a certain direction, decided by the
RL agent, into a smaller patch $p_{i+1}$, with a non-target region eliminated.
After several sequential iterations, all non-target regions are removed and
only the region exactly covering the target object remains, which is viewed as
the final REG result. Note that $p_{1}=img$ at the beginning.

In terms of the shrinking direction selection, we adopt an RL agent to make
the decision within each iteration, and view the aforementioned shrinking
procedure as a Markov decision process (MDP) [14]. Specifically, within a
certain iteration $i$, the state $s_{i}$ is generated according to the
information embedded in $p_{i}$ and $q$ (Section 3.2). Then, according to
$s_{i}$, the RL agent predicts an action $a_{i}$ (shrinking direction or
stop). After $a_{i}$ is executed, a reward $r_{i}$ is calculated as a
“feedback” of $a_{i}$ (Section 3.3). Ultimately, the RL agent is trained
through an actor-critic RL framework, where the RL agent consists of two
components, including an actor network to predict the action, and a critic
network to evaluate the predicted action (Section 3.4). The architecture of
our proposed method is shown in Fig.2.

###  3.2 Agent State

In conventional MDP, states indicate the observations that an agent receives
from the external environment. Specifically to our method, for a certain image
patch $p_{i}$ within iteration $i$, the state $s_{i}$ is the input passed into
the RL agent to predict the action, consisting of three components, including
the linguistic feature $f^{l}_{q}$ extracted from $q$, visual feature
$f^{v}_{p_{i}}$ extracted from $p_{i}$, and spatial feature $f^{s}_{p_{i}}$
extracted from the relative position of $p_{i}$ within $img$.

####  3.2.1 Linguistic Component

To extract the linguistic feature $f^{l}_{q}$, $q$ is first parsed into
multiple discriminative triads $\\{t_{k}\\}_{k=1}^{M}$ [44]. Each triad
represents a piece of discriminative information to distinguish the target
from the distracting or reference objects. As can be observed from Table 1, a
discriminative triad $t_{k}$ consists of three components, including a target
unit $t^{t}_{k}$, a reference unit $t^{r}_{k}$ and a discriminative unit
$t^{d}_{k}$, denoting the target object, the reference object against the
target object and the discriminative relation between them, respectively. Note
that, the discriminative unit $t^{d}_{k}$ is defined in a broad sense to take
full advantage of the potential discriminative information hidden in queries.
As for an instance, when it comes to “orange cat” in Table 1, this query
implies that there are cats in other colors with a high probability. Thus,
“cat” is set as its reference unit to represent the distracting cats in other
colors.

For its implementation, an off-the-shelf NLP processing toolbox (e.g.,
Stanford CoreNLP [2] or Spacy [13]) is employed to analyze the tree structure
of each query, as well as the dependency label of each word in the query. In
general, triads are generated within two steps. The first step is to extract
the rightmost Normal Noun (NN) of the bottom-left Noun Phrase (NP) in the
sentence tree as the target unit shared by all triads. The second step is to
generate the reference and discriminative units using different parsing
patterns. As for an instance, the subject-relation-object phrase, such as “the
man holding a cat”, firstly the second component of a particular dependency,
whose first component is the same as the target unit, and the dependency type
is nsubj, is viewed as a discriminative unit. Then, the second component of
another dependency, whose first component is the same as that of the current
discriminative unit, is viewed as its corresponding reference unit.

Then, a pre-trained word vector generation method (e.g., Word2vec [31] or
Glove [35]) is adopted to extract the linguistic embedding
$f^{l}_{t^{t}_{k}}$, $f^{l}_{t^{r}_{k}}$, $f^{l}_{t^{d}_{k}}$, corresponding
to $t^{t}_{k}$, $t^{r}_{k}$, $t^{d}_{k}$, respectively. The linguistic feature
$f^{l}_{t_{k}}$ of a certain triad $t_{k}$ is the concatenation of its three
components’ linguistic features:

$f^{l}_{t_{k}}=f^{l}_{t^{t}_{k}}\oplus f^{l}_{t^{r}_{k}}\oplus
f^{l}_{t^{d}_{k}},$ (1)

where $\oplus$ indicates the concatenation operation. Similarly, another
concatenation operation is further conducted on all triads’ linguistic
features:

$f^{l}_{q}=f^{l}_{t_{1}}\oplus f^{l}_{t_{2}}\oplus\cdots\oplus f^{l}_{t_{M}},$
(2)

and $f^{l}_{q}$ represents the ultimate linguistic feature of $q$. Note that,
if the total number of the triads parsed from a query is less than $M$, the
first triad feature $f^{l}_{t_{1}}$ is repeated until the triad number reaches
$M$.

Table 1: Common queries and their corresponding discriminative triads on the RefCOCOg, RefCOCO+ and RefCOCO datasets. ID is the index of a discriminative triad for a query, as a complex query may generate multiple discriminative triads. T/R/D indicates the target, reference, and discriminative unit, respectively. Query |  ID |  T |  R |  D
---|---|---|---|---
“lady” |  1 |  lady |  lady |  SELF
“left” |  1 |  UKN |  UKN |  left
“left lady” |  1 |  lady |  lady |  left
“orange cat” |  1 |  cat |  cat |  orange
“cat above a shelf” |  1 |  cat |  shelf |  above
“lady holding a cat” |  1 |  lady |  cat |  holding
“the left lady in white holding an orange cat and standing on a table” |  1 |  lady |  lady |  left
|  2 |  lady |  lady |  white
|  3 |  lady |  table |  on
|  4 |  lady |  cat |  holding
|  5 |  cat |  cat |  orange

####  3.2.2 Visual and Spatial Components

The visual feature of the image patch $p_{i}$ is extracted through an off-the-
shell convolutional network (e.g., VGG [43] or ResNet [11]) and the feature
pyramid network (FPN) [23]. Specifically, the convolutional network, e.g.,
ResNet [11], first generates three raw visual feature maps,
$f^{\tilde{v_{1}}}_{p_{i}}$, $f^{\tilde{v_{2}}}_{p_{i}}$,
$f^{\tilde{v_{3}}}_{p_{i}}$, with different scales of $[28\times 28\times
512]$, $[14\times 14\times 1024]$ and $[7\times 7\times 2048]$, respectively.
Then, the up-sampling, fusing and average-pooling operations of FPN [23] are
conducted on these three raw feature maps, which generates three one-hot
vectors with the same dimension ($D_{v}$), $f^{v_{1}}_{p_{i}}$,
$f^{v_{2}}_{p_{i}}$ and $f^{v_{2}}_{p_{i}}$, as the corresponding visual
feature for each scale level.

The spatial feature $f^{s}_{p_{i}}$ of the image patch $p_{i}$ is encoded by a
5-D vector,
$[\frac{x_{tl}}{W},\frac{y_{tl}}{H},\frac{x_{br}}{W},\frac{y_{br}}{H},\frac{w\cdot
h}{W\cdot H}]$, where $[x_{tl},y_{tl}]$ and $[x_{br},y_{br}]$ refer to the
top-left and bottom-right coordinates of $p_{i}$ within $img$, respectively.
$w$ and $h$ indicate the width and height of $p_{i}$, while $W$ and $H$ denote
the width and height of $img$. $f^{s}_{p_{i}}$ can provide the relative
position of $p_{i}$ within $img$, through which the RL agent can infer the
relative location of the target object within $img$.

The ultimate state $s_{i}$ consists of three sub-states $s^{c}_{i}$ with
$c\in\\{1,2,3\\}$, each of which corresponds to a certain scale level $c$.
Each sub-state is designed as the concatenation of the corresponding
linguistic, visual and spatial features:

$s^{c}_{i}=f^{l}_{q}\oplus f^{v_{c}}_{p_{i}}\oplus f^{s}_{p_{i}}.$ (3)

Figure 3: Illustration of our action design. $\\{a^{1},a^{2},a^{3},a^{4}\\}$
corresponds to image shrinking toward 4 different directions, respectively.
$a^{5}$ corresponds to the STOP action.

###  3.3 Action and Reward

In MDP, after observing the environment, an agent takes actions to interact
with the external environment. A reward is given to provide the feedback of
the conducted action. As shown in Fig.3, within a certain iteration $i$, the
RL agent selects an action $a_{i}$ among the action pool $A$, consisting of 5
candidate actions, $\\{a^{1},a^{2},a^{3},a^{4},a^{5}\\}$. The first 4
candidate actions, $\\{a^{1},a^{2},a^{3},a^{4}\\}$, indicate the top side of
$p_{i}$ shrinks towards down, the bottom side of $p_{i}$ shrinks towards up,
the left side of $p_{i}$ shrinks towards right and the right side of $p_{i}$
shrinks towards left, respectively. $a_{5}$ indicates the end of the shrinking
process (i.e., $p_{i}=p_{i+1}$), and the current image patch is viewed as the
final REG result.

To naturally introduce the shrinking stride decay in an episode, the value of
the shrinking stride is decided according to the width and height of the image
patch $p_{i}$ before shrinking:

$\begin{split}\hat{y}_{tl}=y_{tl}+\alpha(y_{br}-y_{tl}),\ \mathrm{if}\
a_{i}=a^{1}\\\ \hat{y}_{br}=y_{br}-\alpha(y_{br}-y_{tl}),\ \mathrm{if}\
a_{i}=a^{2}\\\ \hat{x}_{tl}=x_{tl}+\alpha(x_{br}-x_{tl}),\ \mathrm{if}\
a_{i}=a^{3}\\\ \hat{x}_{br}=x_{br}-\alpha(x_{br}-x_{tl}),\ \mathrm{if}\
a_{i}=a^{4},\end{split}$ (4)

where $[x_{tl},y_{tl}]$ and $[x_{br},y_{br}]$ indicate the coordinates of the
top-left and bottom-right points of $p_{i}$ within $img$.
$[\hat{x}_{tl},\hat{y}_{tl}]$ and $[\hat{x}_{br},\hat{y}_{br}]$ indicate the
coordinates of the top-left and bottom-right points of $p_{i+1}$ within in
$img$. In this way, at the early stage of an episode, relatively large
shrinking strides are adopted to quickly “move” towards to the target. While
in the late stage, relatively small shrinking strides are adopted to
meticulously localize the accurate position of the target.

To predict such an action $a_{i}$, the state $s^{c}_{i}$ for each scale level
is passed into the RL agent respectively, generating three action probability
vectors, with the average one serving as the final probability vector. The
action with the highest probability is selected as $a_{i}$.

The reward $r_{i}$ is designed according to the overlap between the image
patch after shrinking and the ground-truth bounding box, as follows:

$r_{i}=\left\\{\begin{matrix}0&IoU<0.3\ \ or\ \ \Delta_{IoU}\leqslant 0\\\
1&0.3\leqslant IoU<0.5\ \ and\ \ 0<\Delta_{IoU}\\\ 10&0.5\leqslant IoU\ \ and\
\ 0<\Delta_{IoU}\end{matrix}\right.,$ (5)

where $IoU$ refers to the intersection-over-union between the image region
after shrinking and the ground-truth bounding box of the target, and
$\Delta_{IoU}$ indicates the $IoU$ difference between the current iteration
and the previous iteration. We set major difference between the good and bad
action’s rewards, so as to facilitate the training of the RL agent.

Table 2: Accuracy comparison against other REG methods. “PF” indicates
proposal-free REG methods. Specifically, methods on the top half of the table
are not proposal-free, while methods on the bottom half are proposal-free.
“Average” is the average accuracy of RefCOCOg, RefCOCO+, and RefCOCO, where
mean accuracy of testA and testB is used for RefCOCO+ and RefCOCO. The method
with the highest accuracy is in bold.

Method |  PF | Visual Extractor |  Average | RefCOCOg | RefCOCO+ | RefCOCO
---|---|---|---|---|---|---
|  | test |  testA |  testB |  testA |  testB
SLR[61] CVPR17 |  | ResNet-101 |  61.25 | 59.63 |  60.74 |  48.80 |  73.71 |  64.96
DGA[55] ICCV19 |  | VGG-16 |  65.26 | 63.28 |  69.07 |  51.99 |  78.42 |  65.53
MAttNet[59] CVPR18 |  | ResNet-101 |  68.33 | 67.01 |  70.26 |  56.00 |  80.43 |  69.28
FAOAVG[57] ICCV19 |  ✔ | DarkNet-53 |  61.79 | 57.45 |  60.56 |  52.86 |  74.81 |  67.59
MCN[29] CVPR20 |  | VGG-16 |  65.69 | 62.29 |  65.24 |  54.26 |  76.97 |  73.09
RCCF[22] CVPR20 |  | DLA-34 |  67.30 | 65.73 |  70.35 |  56.32 |  78.93 |  66.73
Ours |  | ResNet-101 |  68.63 | 70.05 |  71.05 |  58.25 |  74.27 |  68.10

  * •

* RefCOCO results of RCCF are from Table 4, setting 7 in [22], where the feature backbone is obtained without the detection pretraining using the additional classification labels of the 80 categories in MS-COCO dataset. As the results of RefCOCOg and RefCOCO+ are not provided in Table 4, results from Table 3 in [22] are used instead, but the comparison is actually unfavorable for the proposed method. The darknet-based MCN [29] is not included in this table for the same reason.

###  3.4 Actor-critic Training

The proposed RL agent is designed and optimized under the “actor-critic”
framework [19], consisting of two networks, including the actor network to
predict the action among the candidate action pool, and the critic network to
predict the score of a certain state, which is further utilized to evaluate
the quality of the predicted action. During each iteration of training, the
actor and critic networks are optimized in order, while in the inference
stage, only the actor network is used to predict the action to localize the
target.

Specifically, the actor network is first optimized in a policy-based way:

$\theta=\theta{}^{\prime}+\l_{a}\nabla(log\pi_{\theta{}^{\prime}}(s_{i},a_{i}))A(s_{i},a_{i}),$
(6)

where

$A(s_{i},a_{i})=\delta_{i}=r_{i}+\gamma
V_{w{}^{\prime}}(s_{i+1})-V_{w{}^{\prime}}(s_{i}).$ (7)

In Eq.(6) and Eq.(7), $\theta{}^{\prime}$ and $\theta$ indicate the weights of
the actor network before and after the update. $l_{a}$ is the learning rate
corresponding to the actor network. $\pi(s,a)$ is the actor network’s policy
function to predict the probability of taking action $a$ for state $s$.
$A(s,a)$ is the advantage function, which is equal to the TD error function in
the “actor-critic” framework [32]. $r_{i}$ is the reward calculated using
Eq.(5), and $\gamma$ refers to the discount factor. $w{}^{\prime}$ is the
weight of the critic network before the update of the critic network. $V(s)$
indicates the predicted score for state $s$, generated by the critic network.

After the actor network is updated, the critic network is optimized in a
value-based way:

$w=w{}^{\prime}+\l_{c}\delta_{i}\nabla_{w{}^{\prime}}V_{w{}^{\prime}}(s_{i}).$
(8)

In Eq.(8), $w{}^{\prime}$ and $w$ indicate the weights of the critic network
before and after the optimization. $l_{c}$ is the learning rate corresponding
to the critic network. $\delta_{i}$ is the TD error function calculated in
Eq.(7).

In this way, the joint optimization of the actor and critic networks can avoid
the disadvantages of both value-based and policy-based methods during
training. In other words, the proposed RL agent can be optimized after each
iteration, rather than waiting until the end of each episode, which
dramatically speeds up the training process yet maintains training stability.

###  3.5 Implementation Details

To generate the state, Stanford CoreNLP [2] is adopted to parse the query
sentence into triads, and Glove word vector [35] is adopted to generate the
linguistic feature of each triad. The triad number $M$ for each query is set
as 2, because a too small $M$ cannot contain enough information from queries,
while an extremely large $M$ may greatly increase the network complexity.
Resnet101 [11] is used to generate the raw visual feature of the image patch,
and FPN [23] is adopted to generate the fused visual feature, with $D_{v}$ set
as 512. In terms of the action, $\alpha$ is set as 0.2 to generate a moderate
shrinking stride. During the training, $\gamma$ is set as 0.9, and the
learning rate is set as 1e-7 for both the actor and critic networks. ADAM [18]
is adopted as the optimizer. Training is conducted on one Titan RTX GPU for
around 800,000 episodes.

Similar as [22], to obtain a more precise bounding box for a target, we employ
a post-processing box refinement model after the shrinking process, where the
input is $img$ and the predicted bounding box from the shrinking process, and
the output is the new refined bounding box. Such box refinement network is
trained using the L2 loss between the coordinates of a ground-truth box in MS-
COCO [24] and the coordinates of corresponding sampled box obtained by adding
Gaussian noise to it.

Table 3: Performance comparison of our method against other REG methods on the RefCLEF dataset. The method with the highest accuracy is in bold. Method |  Accuracy
---|---
CITE[36]ECCV18 |  34.13
IGOP[58]NIPS17 |  34.70
RCCF[22]CVPR20 |  63.79
Ours |  65.48

##  4 Experiments

###  4.1 Datasets and Metrics

The proposed method is evaluated on four common datasets including RefCOCO
[60], RefCOCO+ [60], RefCOCOg [30] and RefCLEF [16]. The first three datasets
are collected from MS-COCO [24]. The main difference between RefCOCO+ and
RefCOCO is that the former one forbids the absolute location words when
generating the query sentences, requiring more attention to the appearance
discrimination. RefCOCOg contains longer expressions for both appearance and
locations. Referring sentences in RefCLEF are annotated casually, so it is
normally used as an auxiliary dataset. The metric used to evaluate the
accuracy of the proposed method is similar to the object detection task, where
the intersection-over-union (IoU) between the predicted bounding box and the
ground-truth one is calculated. Then, the one with IoU higher than 0.5 is
treated as correct.

###  4.2 Comparison with State-of-the-Art

To evaluate our proposed method, we compare it with other SOTA REG methods,
which are divided into two groups. The first group, shown in the top half of
Table 2, consists of REG methods with object proposals, including SLR [61],
DGA [55] and MAttNet [59]. The second group, shown in the bottom half of Table
2, is composed of proposal-free REG methods, including FAOAVG [57], MCN [29]
and RCCF [22].

Table 4: Ablation studies on RefCOCO (testA) and RefCOCOg (test) datasets. The method with the highest accuracy is in bold. Setting |  RefCOCO |  RefCOCOg
---|---|---
w/o triad |  67.52 |  60.17
w/o multi-scale |  73.33 |  66.35
w/o spatial feature |  62.42 |  54.88
fixed stride |  45.70 |  39.46
w/o refinement |  70.18 |  65.62
supervised training |  63.84 |  61.36
ours |  74.27 |  70.05

As can be observed from Table 2, the proposed method achieves a large accuracy
gain (4.32%) over the previous SOTA method, RCCF [22], on the test set of the
RefCOCOg dataset. When the backbone is replaced by VGG, the proposed method
achieves 66.32% on this dataset. The cause of such big accuracy gain is that,
queries in RefCOCOg are much longer and more complex than queries in other
datasets, with many targets referred by other neighboring reference objects,
namely “targets with reference”. Thus, the key to localize such targets is to
take full advantage of the relation information between the target and
reference objects in queries, which is difficult for the feature-point level
matching mechanism [57, 29, 22]. Nevertheless, the image-level shrinking
mechanism allows the proposed method to consider all objects within the image
patch, and better utilize such contextual relation information, so as to
achieve higher accuracy.

Figure 4: Visualization of the reasoning process about how to iteratively
localize the target. The image patch generated through shrinking is marked in
red box. The parts above the images indicate the triads parsed from the query,
with the black units representing the contents remaining in the corresponding
image patch, and the gray units indicating that the visual contents of the
corresponding distracting or reference objects are already removed. Figure 5:
Some failure cases of the proposed method where the green box is the ground-
truth one, and the red box is the predicted one which is incorrect.

Then, similar accuracy improvement can be seen on RefCOCO+ (1.32%) and RefClef
(1.69%) datasets, where many queries are complicated as well, as shown in
Table 2 and Table 3. However, the accuracy gains on RefCOCO+ and RefClef are
not as large as that on RefCOCOg. We believe the reason is that the proportion
of “targets with reference” in RefCOCO+, as well as RefClef, is relatively
smaller than that in RefCOCOg. Ultimately, when it comes to the RefCOCO
dataset, where most queries are simple and “targets with reference” are rare,
the proposed method only achieves a comparable accuracy, as the superiority of
better utilizing the contextual relation information turns useless.

Aforementioned evaluation results on different datasets further prove the
positive correlation between the accuracy gain of the proposed method and the
number of “targets with reference”. Though we have not achieved accuracy gain
on all datasets, the average accuracy obtained by the proposed method, on the
RefCOCOg, RefCOCO+ and RefCOCO datasets, is still higher than the previous
SOTA method RCCF [22] by 1.33%.

Apart from the accuracy gain, it can also be observed from Table 2 that the
performance of proposed method is more stable and robust on different datasets
compared with other methods. For instance, RCCF [22] achieves quite high
accuracy (78.93%) on testA of the RefCOCO dataset, but it does not perform
well on the RefCOCOg dataset (65.73%), with a gap of more than 13%. The
proposed method’s performance is much more stable, with the corresponding
accuracy variation less than 5%, demonstrating the robustness of our proposed
method.

###  4.3 Visualization of Reasoning Process

The reasoning process about how to iteratively find and localize the target
can be visualized through the sequential shrinking processes, as shown in
Fig.4. For instance, in the first case in Fig.4, the first step of the RL
agent is to remove the first distracting object, the kid far from us, which is
against the query information “closest”, making its corresponding triad
[kid,kid,closest] gray. Then, the second step is to eliminate the second
distracting object, the kid in white, which is against the query information
“blue”, making its corresponding triad [kid,kid,blue] gray. Ultimately, after
a few small-stride shrinks, the precise target region can be obtained. Note
that in the third case, the triad [flower,pot,in] turns gray because the
distracting flowers, which are not in the pot, are removed from the image. In
general, the distracting and reference objects are iteratively excluded in the
early stage, and then the target region is gradually refined, until the exact
bounding box of the target is obtained.

Some failure cases of the proposed methods are also reported in Fig.5. In
Fig.5.(a), the heavily-occluded target is difficult to be localized. Besides,
tiny facial difference is also hard to be recognized, like the man and the boy
wearing the same clothes in Fig.5.(b). The similar challenge is also
encountered when dealing with the difference in the textual description about
the clothes styles, as shown in Fig.5.(c). We believe the reason for these
failure cases is that the similar situations are very rare in the training
set, making them quite tough to be handled for REG methods. We will try to
address these hard cases in our future works.

###  4.4 Ablation Study

####  4.4.1 RL State Design

The first ablation study is to explore the contribution of the linguistic,
visual and spatial components in the proposed state, respectively. As shown in
Table 4, for the linguistic component, the triad-based feature is replaced
with the feature extracted through Bert [8] (w/o triad). Then, the multi-scale
feature maps are not utilized, with the raw feature extracted from the CNN
network directly employed as the final visual feature (w/o multi-scale), to
investigate the contribution of the multi-scale visual feature. Lastly, the
spatial component is removed from the state to check its influence (w/o
spatial). The proposed method shows an accuracy gain against all
aforementioned settings, which demonstrates the significance of each component
in the proposed RL state. Note that the accuracy gain against w/o triad comes
from better feature representation for the query sentence using the triads, as
trivial words in the query (e.g., articles, conjunctions) are eliminated, and
the key words are organized into a unified format, allowing a better multi-
modal comprehension.

####  4.4.2 RL Action Design

The second ablation study is to study different designs for the agent action.
As shown in Table 4, firstly, the adaptive shrinking stride is replaced with
the fixed shrinking stride (fixed stride). Specifically, within each
iteration, the shrinking stride is fixed as $\alpha H$ for $a_{1}$ and
$a_{2}$, and $\alpha W$ for $a_{3}$ and $a_{4}$, where $H$ and $W$ are the
width and height of the original image $img$, respectively, and $\alpha$ is
set as 0.2, being the same as in the proposed adaptive shrinking mechanism.
The performance drops dramatically in this setting, demonstrating an adaptive
shrinking stride contributes significantly to precise localization. Apart from
the actions in the shrinking process, we further disable the bounding box
refinement network described in Section 3.5 (w/o refinement), with the
comparison result demonstrating the contribution of the bounding box
refinement step.

####  4.4.3 RL or Supervised Learning?

The third ablation study is to explore whether the proposed method can be
trained in a supervised way, and we introduce supervised training in Table 4.
In this setting, we randomly sample a region, which covers the whole target
object box and its size is larger than the target object box. Then, one side
of the sampled region, among the top, bottom, left and right sides, with the
highest spatial difference against the target region, is set as the positive
label indicating the shrinking direction, if the difference is greater than a
threshold. Otherwise, the stop action is set as the positive label. As can be
observed in Table 4, the proposed RL performs much better than the supervised
training. We believe that the major reason is that the adopted sampling
strategy for the supervised training cannot cover all situations in reality.
In addition, the RL training can consider not only the current profit but also
the potential profit in the future, making a higher overall performance.

##  5 Conclusion

We have proposed an iterative shrinking mechanism to tackle the REG task,
where the image iteratively shrinks into the correct target region. An RL
agent is adopted to decide the shrinking direction within each iteration,
where all objects in the image patch, including the target, reference and
distracting objects, are comprehensively considered to predict the optimal
shrinking direction. In future, we plan to deceptively eliminate the
contextual information whose corresponding image region has already been
removed.

## References

  * [1] Ankan Bansal, Yuting Zhang, and Rama Chellappa.  Visual question answering on image sets.  ECCV, 2020.
  * [2] Danqi Chen and Christopher D Manning.  A fast and accurate dependency parser using neural networks.  In EMNLP, 2014.
  * [3] Hui Chen, Guiguang Ding, Xudong Liu, Zijia Lin, Ji Liu, and Jungong Han.  IMRAM: Iterative matching with recurrent attention memory for cross-modal image-text retrieval.  In CVPR, 2020.
  * [4] Long Chen, Xin Yan, Jun Xiao, Hanwang Zhang, Shiliang Pu, and Yueting Zhuang.  Counterfactual samples synthesizing for robust visual question answering.  In CVPR, 2020.
  * [5] Shizhe Chen, Qin Jin, Peng Wang, and Qi Wu.  Say as you wish: Fine-grained control of image caption generation with abstract scene graphs.  In CVPR, 2020.
  * [6] Tianlang Chen, Jiajun Deng, and Jiebo Luo.  Adaptive offline quintuplet loss for image-text matching.  ECCV, 2020.
  * [7] Marcella Cornia, Matteo Stefanini, Lorenzo Baraldi, and Rita Cucchiara.  Meshed-memory transformer for image captioning.  In CVPR, 2020.
  * [8] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  preprint arXiv:1810.04805, 2018.
  * [9] Longteng Guo, Jing Liu, Xinxin Zhu, Peng Yao, Shichen Lu, and Hanqing Lu.  Normalized and geometry-aware self-attention network for image captioning.  In CVPR, 2020.
  * [10] Tanmay Gupta, Arash Vahdat, Gal Chechik, Xiaodong Yang, Jan Kautz, and Derek Hoiem.  Contrastive learning for weakly supervised phrase grounding.  ECCV, 2020.
  * [11] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, pages 770–778, 2016.
  * [12] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural Computation, 9(8):1735–1780, 1997.
  * [13] Matthew Honnibal and Ines Montani.  spacy 2: Natural language understanding with bloom embeddings, convolutional neural networks and incremental parsing.  2017\.
  * [14] Tommi Jaakkola, Satinder P Singh, and Michael I Jordan.  Reinforcement learning algorithm for partially observable markov decision problems.  In NIPS, 1995.
  * [15] Huaizu Jiang, Ishan Misra, Marcus Rohrbach, Erik Learned-Miller, and Xinlei Chen.  In defense of grid features for visual question answering.  In CVPR, 2020.
  * [16] Sahar Kazemzadeh, Vicente Ordonez, Mark Matten, and Tamara Berg.  Referitgame: Referring to objects in photographs of natural scenes.  In EMNLP, 2014.
  * [17] Junyeong Kim, Minuk Ma, Trung Pham, Kyungsu Kim, and Chang D Yoo.  Modality shifting attention network for multi-modal video question answering.  In CVPR, 2020.
  * [18] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  preprint arXiv:1412.6980, 2014.
  * [19] Vijay R Konda and John N Tsitsiklis.  Actor-critic algorithms.  In NIPS, 2000.
  * [20] Thao Minh Le, Vuong Le, Svetha Venkatesh, and Truyen Tran.  Hierarchical conditional relation networks for video question answering.  In CVPR, 2020.
  * [21] Kunpeng Li, Yulun Zhang, Kai Li, Yuanyuan Li, and Yun Fu.  Visual semantic reasoning for image-text matching.  In CVPR, 2019.
  * [22] Yue Liao, Si Liu, Guanbin Li, Fei Wang, Yanjie Chen, Chen Qian, and Bo Li.  A real-time cross-modality correlation filtering method for referring expression comprehension.  In CVPR, 2020.
  * [23] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In CVPR, 2017.
  * [24] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In ECCV, 2014.
  * [25] Chunxiao Liu, Zhendong Mao, Tianzhu Zhang, Hongtao Xie, Bin Wang, and Yongdong Zhang.  Graph structured network for image-text matching.  In CVPR, 2020.
  * [26] Daqing Liu, Hanwang Zhang, Feng Wu, and Zheng-Jun Zha.  Learning to assemble neural module tree networks for visual grounding.  In CVPR, 2019.
  * [27] Xuejing Liu, Liang Li, Shuhui Wang, Zheng-Jun Zha, Dechao Meng, and Qingming Huang.  Adaptive reconstruction network for weakly supervised referring expression grounding.  In ICCV, 2019.
  * [28] Xihui Liu, Zihao Wang, Jing Shao, Xiaogang Wang, and Hongsheng Li.  Improving referring expression grounding with cross-modal attention-guided erasing.  In CVPR, 2019.
  * [29] Gen Luo, Yiyi Zhou, Xiaoshuai Sun, Liujuan Cao, Chenglin Wu, Cheng Deng, and Rongrong Ji.  Multi-task collaborative network for joint referring expression comprehension and segmentation.  In CVPR, 2020.
  * [30] Junhua Mao, Jonathan Huang, Alexander Toshev, Oana Camburu, Alan L Yuille, and Kevin Murphy.  Generation and comprehension of unambiguous object descriptions.  In CVPR, 2016.
  * [31] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.  Efficient estimation of word representations in vector space.  preprint arXiv:1301.3781, 2013.
  * [32] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu.  Asynchronous methods for deep reinforcement learning.  In ICML, 2016.
  * [33] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing atari with deep reinforcement learning.  arXiv:1312.5602, 2013.
  * [34] Yingwei Pan, Ting Yao, Yehao Li, and Tao Mei.  X-linear attention networks for image captioning.  In CVPR, 2020.
  * [35] Jeffrey Pennington, Richard Socher, and Christopher D Manning.  Glove: Global vectors for word representation.  In EMNLP, 2014.
  * [36] Bryan A Plummer, Paige Kordas, M Hadi Kiapour, Shuai Zheng, Robinson Piramuthu, and Svetlana Lazebnik.  Conditional image-text embedding networks.  In ECCV, 2018.
  * [37] Joseph Redmon and Ali Farhadi.  Yolov3: An incremental improvement.  preprint arXiv:1804.02767, 2018.
  * [38] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In NIPS, 2015.
  * [39] Steven J Rennie, Etienne Marcheret, Youssef Mroueh, Jerret Ross, and Vaibhava Goel.  Self-critical sequence training for image captioning.  In CVPR, 2017.
  * [40] Anna Rohrbach, Marcus Rohrbach, Ronghang Hu, Trevor Darrell, and Bernt Schiele.  Grounding of textual phrases in images by reconstruction.  In ECCV, 2016.
  * [41] Arka Sadhu, Kan Chen, and Ram Nevatia.  Zero-shot grounding of objects from natural language queries.  In CVPR, 2020.
  * [42] Fawaz Sammani and Luke Melas-Kyriazi.  Show, edit and tell: A framework for editing image captions.  In CVPR, 2020.
  * [43] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  preprint arXiv:1409.1556, 2014.
  * [44] M. Sun, J. Xiao, E. Lim, S. Liu, and J. Y. Goulermas.  Discriminative triad matching and reconstruction for weakly referring expression grounding.  TPAMI, pages 1–1, 2021.
  * [45] Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour.  Policy gradient methods for reinforcement learning with function approximation.  In NIPS, 2000.
  * [46] Ruixue Tang, Chao Ma, Wei Emma Zhang, Qi Wu, and Xiaokang Yang.  Semantic equivalent adversarial data augmentation for visual question answering.  ECCV, 2020.
  * [47] Alasdair Tran, Alexander Mathews, and Lexing Xie.  Transform and tell: Entity-aware news image captioning.  In CVPR, 2020.
  * [48] Ramakrishna Vedantam, C Lawrence Zitnick, and Devi Parikh.  Cider: Consensus-based image description evaluation.  In CVPR, 2015.
  * [49] Haoran Wang, Ying Zhang, Zhong Ji, Yanwei Pang, and Lin Ma.  Consensus-aware visual-semantic embedding for image-text matching.  ECCV, 2020.
  * [50] Liwei Wang, Yin Li, and Svetlana Lazebnik.  Learning deep structure-preserving image-text embeddings.  In CVPR, 2016.
  * [51] Peng Wang, Qi Wu, Jiewei Cao, Chunhua Shen, Lianli Gao, and Anton van den Hengel.  Neighbourhood Watch: Referring expression comprehension via language-guided graph attention networks.  In CVPR, 2019.
  * [52] Xinyu Wang, Yuliang Liu, Chunhua Shen, Chun Chet Ng, Canjie Luo, Lianwen Jin, Chee Seng Chan, Anton van den Hengel, and Liangwei Wang.  On the general value of evidence, and bilingual scene-text visual question answering.  In CVPR, 2020.
  * [53] Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio.  Show, attend and tell: Neural image caption generation with visual attention.  In ICML, 2015.
  * [54] Sibei Yang, Guanbin Li, and Yizhou Yu.  Cross-modal relationship inference for grounding referring expressions.  In CVPR, 2019.
  * [55] Sibei Yang, Guanbin Li, and Yizhou Yu.  Dynamic graph attention for referring expression comprehension.  In ICCV, 2019.
  * [56] Zhengyuan Yang, Tianlang Chen, Liwei Wang, and Jiebo Luo.  Improving one-stage visual grounding by recursive sub-query construction.  ECCV, 2020.
  * [57] Zhengyuan Yang, Boqing Gong, Liwei Wang, Wenbing Huang, Dong Yu, and Jiebo Luo.  A fast and accurate one-stage approach to visual grounding.  In CVPR, 2019.
  * [58] Raymond Yeh, Jinjun Xiong, Wen-Mei Hwu, Minh Do, and Alexander Schwing.  Interpretable and globally optimal prediction for textual grounding using image concepts.  In NIPS, 2017.
  * [59] Licheng Yu, Zhe Lin, Xiaohui Shen, Jimei Yang, Xin Lu, Mohit Bansal, and Tamara L Berg.  Mattnet: Modular attention network for referring expression comprehension.  In CVPR, 2018.
  * [60] Licheng Yu, Patrick Poirson, Shan Yang, Alexander C Berg, and Tamara L Berg.  Modeling context in referring expressions.  In ECCV, 2016.
  * [61] Licheng Yu, Hao Tan, Mohit Bansal, and Tamara L Berg.  A joint speaker-listener-reinforcer model for referring expressions.  In CVPR, 2017.
  * [62] Qi Zhang, Zhen Lei, Zhaoxiang Zhang, and Stan Z Li.  Context-aware attention network for image-text retrieval.  In CVPR, 2020.
  * [63] Yuanen Zhou, Meng Wang, Daqing Liu, Zhenzhen Hu, and Hanwang Zhang.  More grounded image captioning by distilling image-text matching model.  In CVPR, 2020.