# A Chain Rule for the Expected Suprema of Bernoulli Processes††thanks: This
research was suppoorted in part by DARPA under the Learning with Less Labels
(LwLL) program.

Yifeng Chu University of Illinois, Urbana, IL, USA. E-mail:
<EMAIL_ADDRESS>Maxim Raginsky University of Illinois, Urbana, IL, USA.
E-mail<EMAIL_ADDRESS>
###### Abstract

We obtain an upper bound on the expected supremum of a Bernoulli process
indexed by the image of an index set under a uniformly Lipschitz function
class in terms of properties of the index set and the function class,
extending an earlier result of Maurer for Gaussian processes. The proof makes
essential use of recent results of Bednorz and Latała on the boundedness of
Bernoulli processes.

##  1 Introduction

Sharp bounds on the suprema of Bernoulli processes are ubiquitous in
applications of probability theory. For example, in statistical learning
theory, they arise as so-called Rademacher complexities that quantify the
effective “size” of a function class in the context of a given learning task
[1]. To evaluate the generalization error bound of a learning algorithm, one
usually needs to obtain a good estimate on the (empirical) Rademacher
complexity of a suitable function class. In many scenarios, the function class
at hand is composite, and separate assumptions are imposed on the constituent
classes forming the composition. Thus, it is desirable to obtain a bound that
takes into account the properties of the function classes in the composition.

Let $(\varepsilon_{i})$ and $(\xi_{i})$ be sequences of i.i.d. symmetric
Bernoulli (or Rademacher) variables, _i.e._ ,
$\mathbf{P}\mathopen{}\mathclose{{}\left[\varepsilon_{i}=\pm
1}\right]=\frac{1}{2}$, and a sequence of i.i.d. standard Gaussian variables,
respectively. The Rademacher and the Gaussian complexities of
$T\subset\ell^{2}(I)$, with $I$ countable, are defined by

$\displaystyle\mathfrak{b}(T):=\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{t\in
T}\sum_{i\in I}\varepsilon_{i}t_{i}}\right],$
$\displaystyle\mathfrak{g}(T):=\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{t\in
T}\sum_{i\in I}\xi_{i}t_{i}}\right],$

(see, _e.g._ , [8, 2]). For $T\subset\mathbb{R}^{k\times n}$, we follow [7]
and let

$\displaystyle\mathfrak{b}(T):=\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{t\in
T}\sum_{i=1}^{n}\sum_{j=1}^{k}\varepsilon_{ji}t_{ji}}\right],$
$\displaystyle\mathfrak{g}(T):=\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{t\in
T}\sum_{i=1}^{n}\sum_{j=1}^{k}\xi_{ji}t_{ji}}\right],$

where $\varepsilon_{ji}$ and $\xi_{ji}$ are independent for different values
of the pair of indices $(j,i)$. Given a class $\mathscr{F}$ of functions
$f:\mathbb{R}^{k}\to\mathbb{R}^{\ell}$ and $T\subset\mathbb{R}^{k\times n}$,
we form the composite class
$\mathscr{F}(T):=\mathopen{}\mathclose{{}\left\\{f(t):f\in\mathscr{F},t\in
T}\right\\}\subset\mathbb{R}^{\ell\times n}$ where $f(t):=(f(t_{i}))_{1\leq
i\leq n}$. (In particular, if the functions in $\mathscr{F}$ are real-valued,
then $\mathscr{F}(T)$ is a subset of $\mathbb{R}^{n}$.) We would like to
obtain an upper bound on the Rademacher complexity
$\mathfrak{b}(\mathscr{F}(T))$ of the composite class $\mathscr{F}(T)$ in
terms of Rademacher complexities of $\mathscr{F}$ and $T$ alone, under
appropriate regularity conditions on $\mathscr{F}$ and $T$. A chain rule of
this type was obtained by Maurer [6] for the Gaussian complexity
$\mathfrak{g}(\mathscr{F}(T))$. In this work, we are concerned with chain
rules for Rademacher complexities. This extension relies on completely
different techniques, in particular on recent powerful results of Bednorz and
Latała [2] on the so-called Bernoulli conjecture of Talagrand.

We first introduce some notation. For $p,q\in[1,\infty]$ and
$t=(t_{1},\ldots,t_{n})\in\mathbb{R}^{k\times n}$ with each
$t_{i}\in\mathbb{R}^{k}$, let $\mathopen{}\mathclose{{}\left\lVert
t}\right\rVert_{p,q}:=\big{\|}\big{(}\mathopen{}\mathclose{{}\left\lVert
t_{1}}\right\rVert_{p},\ldots,\mathopen{}\mathclose{{}\left\lVert
t_{n}}\right\rVert_{p}\big{)}\big{\|}_{q}$, i.e.,
$\mathopen{}\mathclose{{}\left\lVert t}\right\rVert_{p,q}$ is the $q$-norm of
the vector whose entries are the $p$-norms of the columns of $t$. We let
$\mathopen{}\mathclose{{}\left\lVert
t}\right\rVert_{2}=\mathopen{}\mathclose{{}\left\lVert
t}\right\rVert_{2,2}=\mathopen{}\mathclose{{}\left\lVert t}\right\rVert_{F}$,
where $\mathopen{}\mathclose{{}\left\lVert\cdot}\right\rVert_{F}$ denotes the
Frobenius norm. For a set $T\subset\mathbb{R}^{k\times n}$, we let
$\mathopen{}\mathclose{{}\left\lVert T}\right\rVert_{p,q}:=\sup_{t\in
T}\mathopen{}\mathclose{{}\left\lVert t}\right\rVert_{p,q}$. The Lipschitz
constant of a function $f:\mathbb{R}^{k}\to\mathbb{R}$ w.r.t. the Euclidean
norm will be denoted by $\mathopen{}\mathclose{{}\left\lVert
f}\right\rVert_{\operatorname*{Lip}}$. We will write $a\lesssim b$ if $a\leq
Cb$ for a universal constant $C$; the cases when the constant $C$ depends on
some parameter will be indicated explicitly. Our main result is as follows:

######  Theorem 1.

Let a countable111We restrict attention to countable classes in order to avoid
dealing with various measure-theoretic technicalities, which can be handled in
a standard manner by, e.g., imposing separability assumptions on the relevant
function classes and processes. class $\mathscr{F}$ of functions
$f:\mathbb{R}^{k}\to\mathbb{R}$ and a countable set
$T\subset\mathbb{R}^{k\times n}$ be given. Assume that all $f\in\mathscr{F}$
are uniformly Lipschitz with respect to the Euclidean norm, i.e.,
$\sup_{f\in\mathscr{F}}\mathopen{}\mathclose{{}\left\lVert
f}\right\rVert_{\operatorname*{Lip}}\leq L<\infty$. Assume also that
$\mathfrak{b}(T)<\infty$ and $\mathfrak{b}(\mathscr{F}(T))<\infty$. Then there
exists a set $S\subset\mathbb{R}^{k\times n}$ with
$\mathfrak{g}(S)\leq\mathfrak{b}(T)$ and $\mathopen{}\mathclose{{}\left\lVert
S}\right\rVert_{\infty,\infty}\leq\mathopen{}\mathclose{{}\left\lVert
T}\right\rVert_{\infty,\infty}$, such that

$\displaystyle\mathfrak{b}(\mathscr{F}(T))\lesssim
L\mathfrak{b}(T)+\Delta_{2}(S)\mathfrak{r}^{\mathfrak{b}}(\mathscr{F},S)+\mathfrak{b}(\mathscr{F}(\tau))$
(1)

for any $\tau\in S$, where $\Delta_{2}(S)$ is the diameter of $S$ with respect
to the Frobenius norm, and where

$\displaystyle\mathfrak{r}^{\mathfrak{b}}(\mathscr{F},S):=\sup_{s,t\in
S}\frac{\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F}}\sum_{i=1}^{n}\varepsilon_{i}(f(s_{i})-f(t_{i}))}\right]}{\mathopen{}\mathclose{{}\left\lVert
s-t}\right\rVert_{2}}.$

Theorem 1 is a counterpart of Theorem 2 in [6] on expected suprema of Gaussian
processes. There are, however, two differences between the results of Maurer
and ours. One is that Maurer considers the case when $T$ is a subset of
$\mathbb{R}^{\ell}$ and $\mathscr{F}$ is a uniformly Lipschitz class of
functions from $\mathbb{R}^{\ell}$ to $\mathbb{R}^{n}$. Our result carries
over to this setting with a straightforward modification, with the only
difference that the functions in $\mathscr{F}$ have to be uniformly Lipschitz
in both $\ell^{1}$ and $\ell^{2}$ norms. This extra requirement is expected
since the suprema of Bernoulli processes can be controlled in two ways that
are of different nature, as we will discuss in the next section. Another
important difference is that the chain rule for the suprema of Gaussian
processes has the form

$\displaystyle\mathfrak{g}(\mathscr{F}(T))\lesssim
L\mathfrak{g}(T)+\Delta_{2}(T)\mathfrak{r}^{\mathfrak{g}}(\mathscr{F},T)+\mathfrak{g}(\mathscr{F}(\tau)),$
(2)

where $\mathfrak{r}^{\mathfrak{g}}(\mathscr{F},\cdot)$ is defined analogously
to $\mathfrak{r}^{\mathfrak{b}}(\mathscr{F},\cdot)$, but with $(\xi_{i})$
instead of $(\varepsilon_{i})$ [6]. Notice that (1) involves a set $S$ which
is different from $T$, whereas $T$ appears on both sides of (2). However,
using the inequality $\Delta_{2}(S)\leq\sqrt{2\pi}\mathfrak{g}(S)$ [8, p. 44]
and the fact that $\mathfrak{g}(S)\leq\mathfrak{b}(T)$, we can obtain the
following slightly weaker form of (1):

$\displaystyle\mathfrak{b}(\mathscr{F}(T))\lesssim(L+\mathfrak{r}^{\mathfrak{b}}(\mathscr{F},S))\mathfrak{b}(T)+\mathfrak{b}(\mathscr{F}(\tau)).$

Although concrete bounds on $\mathfrak{r}^{\mathfrak{g}}(\mathscr{F},S)$ or
$\mathfrak{r}^{\mathfrak{b}}(\mathscr{F},S)$ can be obtained in particular
cases as in [6], it is nontrivial to obtain good general estimates for these
quantities. This motivates the next result, which involves entropy numbers of
$\mathscr{F}$ [8]. For any set $\mathsf{X}\subset\mathbb{R}^{k}$, let
$\mathopen{}\mathclose{{}\left\lVert
f}\right\rVert_{\mathsf{X}}:=\sup_{x\in\mathsf{X}}|f(x)|$ be the uniform norm
with respect to $\mathsf{X}$, and let $d_{\mathsf{X}}$ be the induced metric.
For any bounded metric space $(T,d)$, let $\Delta(T,d)$ be the diameter of
$T$. For $S\subset T$ and $t\in T$, let $d(t,S):=\inf_{s\in S}d(t,s)$. For any
integer $m\geq 0$, define the $m$th entropy number222Note that in, some texts,
entropy numbers refer to logarithms of covering numbers. Some relations
between these two definitions can be found in [8]. of $T$.

$\displaystyle e_{m}(T,d):=\inf\sup_{t\in T}d(t,T_{m}),$

where the infimum is taken over all subsets $T_{m}$ of $T$ such that
$\mathopen{}\mathclose{{}\left\lvert T_{0}}\right\rvert=1$ and
$\mathopen{}\mathclose{{}\left\lvert T_{m}}\right\rvert\leq 2^{2^{m}}$.

######  Theorem 2.

Under the same assumptions as in Theorem 1, let
$\mathsf{S}=\bigcup_{i=1}^{n}S_{i}$ where $S_{i}\subset\mathbb{R}^{k}$ is the
projection of $S$ onto the $i$th coordinate. Then

$\displaystyle\mathfrak{b}(\mathscr{F}(T))\lesssim
L\mathfrak{b}(T)+n\inf_{M\in\mathbb{N}}\mathopen{}\mathclose{{}\left\\{e_{M}(\mathscr{F},d_{\mathsf{S}})+\sum_{m=0}^{M}\frac{2^{m/2}}{\sqrt{n}}e_{m}(\mathscr{F},d_{\mathsf{S}})}\right\\}$

In particular, if we take
$\mathsf{X}=\mathscr{B}_{2}^{k}(R)\supset\mathsf{S}$, where
$\mathscr{B}_{2}^{k}(R)\subset\mathbb{R}^{k}$ is a closed $\ell^{2}$ ball of
radius $R$ centered at $0$, then for any uniformly Lipschitz class
$\mathscr{F}$ with $\mathopen{}\mathclose{{}\left\lVert
f}\right\rVert_{\mathsf{X}}\leq LR$, we have

$\displaystyle\mathfrak{b}(\mathscr{F}(T))\leq
cL\mathfrak{b}(T)+C_{k}LRr_{n,k}\mbox{ with
}\frac{r_{n,k}}{n}=\begin{cases}n^{-1/2},&\text{ for }k=1\\\ n^{-1/2}\log
n,&\text{ for }k=2\\\ n^{-1/k},&\text{ for }k>2\end{cases},$ (3)

where $c$ is a universal constant and $C_{k}$ depends on $k$.

######  Remark 1.

Note that the radius $R$ may depend on $k$, since we need to make sure that
$\mathsf{X}$ is large enough to include $\mathsf{S}$. A possible choice of $R$
is given as follows. Since we assume $\mathfrak{b}(T)<\infty$, we can find an
$R^{\prime}<\infty$ such that $\Delta_{2}(T)\leq R^{\prime}$. Then we can take
$R=\sqrt{k}R^{\prime}$ due to the fact that
$\mathopen{}\mathclose{{}\left\lVert
S}\right\rVert_{2,\infty}\leq\sqrt{k}\mathopen{}\mathclose{{}\left\lVert
S}\right\rVert_{\infty,\infty}\leq\sqrt{k}\mathopen{}\mathclose{{}\left\lVert
T}\right\rVert_{\infty,\infty}\leq\sqrt{k}\mathopen{}\mathclose{{}\left\lVert
T}\right\rVert_{2,\infty}$. This will introduce an extra $k$-dependent factor
for general $\mathscr{F}$ as in (3), but it is not necessarily the case if we
have finer estimates on the entropy numbers. It is also worth mentioning that
if $\mathscr{B}_{2}^{k}(R^{\prime})$ contains a $k$-dimensional cube which
contains $T$, we can simply take $R=R^{\prime}$.

The remainder of the paper is organized as follows: Section 2 introduces some
preliminaries on chaining and its application to bounding expected suprema of
Gaussian and Bernoulli processes; Section 3 gives detailed proofs of our main
results; Section 4 gives some examples on how the main results can be applied;
proofs of some intermediate technical results are collected in Appendix A.

##  2 Preliminaries

Let $I\subset\mathbb{N}$ and $T\subset\ell^{2}(I)$. We first gather some
useful facts on $\mathfrak{b}(T)$ and $\mathfrak{g}(T)$:

######  Lemma 1.

For any $T\subset\ell^{2}(I)$, we have $\mathfrak{b}(T)\leq\sup_{t\in
T}\mathopen{}\mathclose{{}\left\lVert t}\right\rVert_{1}$.

######  Lemma 2 ([2]).

For any $T\subset\ell^{2}(I)$, we have $\Delta_{2}(T)\leq 4\mathfrak{b}(T)$
and $\mathfrak{b}(T)\leq\sqrt{\frac{\pi}{2}}\mathfrak{g}(T)$.

######  Lemma 3 (Eq. (4.9) in [5]).

For any $T\subset\mathbb{R}^{m}$, we have $\mathfrak{g}(T)\lesssim\sqrt{\log
m}\cdot\mathfrak{b}(T).$

In general, when we use $\mathfrak{b}(T)$ to control $\mathfrak{g}(T)$, the
inequality of Lemma 3 cannot be improved. Obviously, we can use Lemma 3 with
the chain rule for $\mathfrak{g}(\mathscr{F}(T))$ from [6] to obtain an upper
bound on $\mathfrak{b}(\mathscr{F}(T))$, but that would introduce an extra
logarithmic factor. Thus we need to modify the techniques from [6] to prove
our results. Before that, let us introduce the most important device used in
[6] and the current work: generic chaining, which is ubiquitous in the study
of suprema of stochastic processes [8]. We start by giving the requisite
definitions.

######  Definition 1.

Given a sequence of sets $(B_{m})_{m\geq 0}$, if
$\mathopen{}\mathclose{{}\left\lvert B_{0}}\right\rvert=1$ and
$\mathopen{}\mathclose{{}\left\lvert{B_{m}}}\right\rvert\leq 2^{2^{m}}$ for
$m\geq 1$, we say each $B_{m}$ has admissible cardinality.

######  Definition 2.

Given a set $T$, a sequence of partitions $(\mathcal{A}_{m})$ of $T$ is
increasing if, for any $m\geq 0$, every set of $\mathcal{A}_{m+1}$ is
contained in a set of $\mathcal{A}_{m}$. Then an admissible sequence of $T$ is
an increasing sequence $(\mathcal{A}_{m})$ of partitions of $T$ such that each
$\mathcal{A}_{m}$ has admissible cardinality.

######  Definition 3.

Given a metric space $(T,d)$, let

$\displaystyle\gamma_{2}(T,d):=\inf\sup_{t\in T}\sum_{m\geq
0}2^{m/2}\Delta(A_{m}(t),d),$

where the infimum is taken over all admissible sequences of $(T,d)$, and
$A_{m}(t)$ is the unique subset of $\mathcal{A}_{m}$ containing $t$.

Now we state a bound on expected suprema of stochastic processes that satisfy
a certain increment condition. Note that it can be recognized as a minor
modification of the generic chaining bound (see _e.g._ [8]). A similar
statement can also be found in [6, Theorem 3].

######  Lemma 4.

Let $(T,d)$ be a metric space. Let $(Y_{t})_{t\in T}$ be a stochastic process
indexed by $T$ that satisfies the increment condition: there exists some
$\kappa\geq 1$ such that, for all $s,t\in T$ and all $u>0$,

$\displaystyle\mathbf{P}\mathopen{}\mathclose{{}\left[Y_{s}-Y_{t}>u}\right]\leq\kappa\exp\mathopen{}\mathclose{{}\left(-\frac{u^{2}}{2d(s,t)^{2}}}\right).$
(4)

Then, for any $\tau\in T$ and for each admissible sequence $(\mathcal{A}_{m})$
of $T$,

$\displaystyle\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{t\in
T}Y_{t}-Y_{\tau}}\right]\lesssim\sup_{t\in
T}\sum_{m=0}^{\infty}2^{m/2}\Delta(A_{m}(t),d)+\Delta(T,d)\sqrt{\log\kappa}.$
(5)

In particular, if we take $T=\ell^{2}(I)$, $d=d_{2}$, and $Y\colon
t\mapsto\sum_{i\in I}\xi_{i}t_{i}$, we can apply the result above with
$\kappa=1$ and take the infimum on both sides over all admissible sequences to
obtain

$\displaystyle\mathfrak{g}(T)\lesssim\gamma_{2}(T,d_{2}).$ (6)

It turns out that (6) can be reversed by the majorizing measure theorem [8]:

######  Theorem 3.

There exists an admissible sequence $\mathcal{A}_{m}$ of $T$ such that

$\displaystyle\sup_{t\in T}\sum_{m\geq
0}2^{m/2}\Delta_{2}(A_{m}(t))\lesssim\mathfrak{g}(T).$

Turning now to Bernoulli averages, let us define

$\displaystyle\mathfrak{b}^{*}(T):=\inf\mathopen{}\mathclose{{}\left\\{\sup_{t\in
T_{1}}\mathopen{}\mathclose{{}\left\lVert
t}\right\rVert_{1}+\gamma_{2}(T_{2},d_{2}):T\subset T_{1}+T_{2}}\right\\},$

where $T_{1}+T_{2}$ is the Minkowski sum, _i.e._ ,
$T_{1}+T_{2}=\mathopen{}\mathclose{{}\left\\{t_{1}+t_{2}:t_{1}\in
T_{1},t_{2}\in T_{2}}\right\\}$. Since
$\mathfrak{b}(T)\leq\mathfrak{b}(T_{1}+T_{2})\leq\mathfrak{b}(T_{1})+\mathfrak{b}(T_{2})\leq\sup_{t\in
T_{1}}\mathopen{}\mathclose{{}\left\lVert
t_{1}}\right\rVert+c\gamma_{2}(T_{2},d_{2})$ for a universal constant $c$, we
obtain $\mathfrak{b}(T)\lesssim\mathfrak{b}^{*}(T)$. Whether such an estimate
can be reversed, known as Talagrand’s Bernoulli Conjecture, remained an open
problem for over two decades and has been affirmatively answered by the
following theorem (see _e.g._ [2, Theorem 1.1]).

######  Theorem 4 (Bednorz-Latała).

For $\mathfrak{b}(T)<\infty$, there exists a decomposition $T\subset
T_{1}+T_{2}$ with

$\displaystyle\sup_{t\in T_{1}}\sum_{i\in
I}\mathopen{}\mathclose{{}\left\lvert
t_{i}}\right\rvert\lesssim\mathfrak{b}(T)\text{ and
}\mathfrak{g}(T_{2})\lesssim\mathfrak{b}(T).$

######  Remark 2.

The main difficulty when working with Bernoulli processes stems from the fact
that $\mathfrak{b}(T)$ can be controlled both by $\sup_{t\in
T}\mathopen{}\mathclose{{}\left\lVert t}\right\rVert_{1}$ and
$\mathfrak{g}(T)$, which are of completely distinct nature, and there is no
canonical decomposition of $T$ into a Minkowski sum $T_{1}+T_{2}$. An explicit
construction of $T_{1},T_{2}$ based on admissble sequences tailored to
$\mathfrak{b}(T)$ can be found in [2, Theorem 3.1]. As we show next, Theorem 4
is the key ingredient needed to extend Maurer’s chain rule to Bernoulli case.

##  3 Proofs of Main Results

The main idea behind the proof of [6, Theorem 2] is to consider
$t\mapsto\sup_{f\in\mathscr{F}}\sum_{i\in I}\xi_{i}f(t_{i})$ as a stochastic
process indexed by $T$. Upon verifying that this process satisfies a
subgaussian increment condition (4), one can apply the chaining argument.
However, since chaining for Gaussian processes does not suffice to ‘explain’
Bernoulli processes, we first invoke the decomposition in the Bednorz–Latała
theorem and then apply chaining only to the parts that are better explained by
it. With the decomposition in Theorem 4, we have the following crucial
observation.

######  Proposition 1.

For $T\subset\mathbb{R}^{k\times n}$, there exist
$T_{1},T_{2}\subset\mathbb{R}^{k\times n}$ with $T\subset$ $T_{1}+T_{2}$, such
that

$\displaystyle\mathfrak{b}(\mathscr{F}(T))\lesssim L\sup_{t\in
T_{1}}\mathopen{}\mathclose{{}\left\lVert
t}\right\rVert_{1,1}+\mathfrak{b}(\mathscr{F}(T_{2}))\lesssim
L\mathfrak{b}(T)+\mathfrak{b}(\mathscr{F}(T_{2})),$

where $T_{2}$ satisfies $\mathfrak{g}(T_{2})\lesssim\mathfrak{b}(T)$.

###### Proof.

For $T\subset\mathbb{R}^{k\times n}$, we identify $T$ as
$\overline{T}\subset\mathbb{R}^{kn}$ by vectorization, _i.e._ , for any $t\in
T$, let

$\displaystyle\mathsf{vec}:t=(t_{1},\ldots,t_{n})=\mathopen{}\mathclose{{}\left(\begin{pmatrix}t_{11}\\\
t_{12}\\\ \vdots\\\ t_{1k}\end{pmatrix},\ldots,\begin{pmatrix}t_{n1}\\\
t_{n2}\\\ \vdots\\\
t_{nk}\end{pmatrix}}\right)\mapsto((t_{11},\ldots,t_{1k}),\ldots,(t_{n1},\ldots,t_{nk}))\in\mathbb{R}^{kn},$

and let $\mathsf{unvec}$ be its inverse. Thus, $\overline{T}=\mathsf{vec}(T)$,
and we will use $\overline{t}$ for elements of $\overline{T}$. We construct
$\overline{T}_{1},\overline{T}_{2}$ as in [2, Theorem 3.1] so that Theorem 4
applies. In particular, as detailed in the proof of Theorem 1.1 of [2], there
exists a map $\pi:\mathbb{R}^{kn}\to\mathbb{R}^{kn}$, such that

$\displaystyle\overline{T}_{1}=\mathopen{}\mathclose{{}\left\\{\overline{t}-\pi(\overline{t}):\overline{t}\in\overline{T}}\right\\}\quad\mbox{
and
}\quad\overline{T}_{2}=\mathopen{}\mathclose{{}\left\\{\pi(\overline{t}):\overline{t}\in\overline{T}}\right\\},$

which are identified as $T_{1},T_{2}$ in $\mathbb{R}^{k\times n}$ by letting
$T_{1}=\mathsf{unvec}(\overline{T}_{1}),T_{2}=\mathsf{unvec}(\overline{T}_{2})$.
With a slight abuse of notation, we also write $\pi(t)$ for $t\in T$ by
letting $\pi(t)=\mathsf{unvec}(\pi(\mathsf{vec}(t)))$. Then, we obtain

$\displaystyle\mathfrak{b}(\mathscr{F}(T))$
$\displaystyle=\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F},t\in
T}\sum_{i=1}^{n}\varepsilon_{i}f(t_{i})}\right]$
$\displaystyle=\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F},t\in
T}\sum_{i=1}^{n}\varepsilon_{i}\Big{(}f(t_{i})-f(\pi(t)_{i})+f(\pi(t)_{i})\Big{)}}\right]$
$\displaystyle\leq\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F},t\in
T}\sum_{i=1}^{n}\varepsilon_{i}\Big{(}f(t_{i})-f(\pi(t)_{i})\Big{)}}\right]+\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F},t\in
T}\sum_{i=1}^{n}\varepsilon_{i}f(\pi(t)_{i})}\right].$

We recognize the second term as $\mathfrak{b}(\mathscr{F}(T_{2}))$ by the
choice of $T_{2}$. For the first term,

$\displaystyle\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F},t\in
T}\sum_{i=1}^{n}\varepsilon_{i}\Big{(}f(t_{i})-f(\pi(t)_{i})\Big{)}}\right]$
$\displaystyle\leq\sup_{f\in\mathscr{F},t\in
T}\sum_{i=1}^{n}\mathopen{}\mathclose{{}\left\lvert
f(t_{i})-f(\pi(t)_{i})}\right\rvert$ $\displaystyle\leq L\sup_{t\in
T_{1}}\sum_{i=1}^{n}\mathopen{}\mathclose{{}\left\lVert
t_{i}}\right\rVert_{2}$ $\displaystyle\leq L\sup_{t\in
T_{1}}\sum_{i=1}^{n}\mathopen{}\mathclose{{}\left\lVert
t_{i}}\right\rVert_{1}$
$\displaystyle=L\sup_{\overline{t}\in\overline{T}_{1}}\mathopen{}\mathclose{{}\left\lVert\overline{t}}\right\rVert_{1}=L\sup_{t\in
T_{1}}\mathopen{}\mathclose{{}\left\lVert t}\right\rVert_{1,1}$

where the inequalities are due to the choice of $T_{1}$, the Lipschitz
continuity of $f$, and the relation between $\ell^{2}$ and $\ell^{1}$. Since
$\overline{T}_{1}$ satisfies
$\sup_{\overline{t}\in\overline{T}_{1}}\mathopen{}\mathclose{{}\left\lVert\overline{t}}\right\rVert_{1}\lesssim\mathfrak{b}(T)$
by Theorem 4, the proof is complete. ∎

###  3.1 Proof of Theorem 1

The overall strategy of the proof now closely follows that of [6, Theorem 2],
although some care must be taken to control $\mathfrak{b}(\cdot)$ in terms of
$\mathfrak{g}(\cdot)$. We first state a simple lemma [6]:

######  Lemma 5.

Suppose a random variable $Y$ satisfies
$\mathbf{P}\mathopen{}\mathclose{{}\left[Y-a>u}\right]\leq\mathrm{e}^{-u^{2}}$
for any $u>0$, where $a\in\mathbb{R}$ is a fixed constant. Then
$\mathbf{P}\mathopen{}\mathclose{{}\left[Y>u}\right]\leq\mathrm{e}^{a^{2}}\mathrm{e}^{-u^{2}/2}$
for all $u>0$.

###### Proof of Theorem 1.

Let $T\subset T_{1}+T_{2}$ be the decomposition constructed in Proposition 1.
Define the stochastic process $Y$ indexed by $T_{2}$,

$\displaystyle Y\colon
t\mapsto\frac{1}{\sqrt{2}L}\sup_{f\in\mathscr{F}}\sum_{i=1}^{n}\varepsilon_{i}f(t_{i}).$

Then
$\mathfrak{b}(\mathscr{F}(T_{2}))=\sqrt{2}L\,\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{t\in
T_{2}}Y_{t}}\right]$. For $s,t\in T_{2}$,

$\displaystyle
Y_{s}-Y_{t}\leq\frac{1}{\sqrt{2}L}\sup_{f\in\mathscr{F}}\sum_{i=1}^{n}\varepsilon_{i}(f(s_{i})-f(t_{i}))=:Z_{s,t}.$

Using McDiarmid’s inequality and Lemma 5, we obtain

$\displaystyle\mathbf{P}\mathopen{}\mathclose{{}\left[Y_{s}-Y_{t}>u}\right]\leq\mathbf{P}\mathopen{}\mathclose{{}\left[Z_{s,t}>u}\right]\leq\exp\mathopen{}\mathclose{{}\left(\frac{(\mathbf{E}Z_{s,t})^{2}}{\mathopen{}\mathclose{{}\left\lVert
s-t}\right\rVert_{2}^{2}}}\right)\exp\mathopen{}\mathclose{{}\left(-\frac{u^{2}}{2\mathopen{}\mathclose{{}\left\lVert
s-t}\right\rVert^{2}_{2}}}\right).$

Thus, $(Y_{t})_{t\in T_{2}}$ satisfies the increment condition of Lemma 4 with
$\kappa:=\exp\mathopen{}\mathclose{{}\left({\sup_{s,t\in
T_{2}}}\frac{(\mathbf{E}Z_{s,t})^{2}}{\mathopen{}\mathclose{{}\left\lVert
s-t}\right\rVert_{2}^{2}}}\right)$. Fix an arbitrary $\tau\in T_{2}$. Since
the Frobenius norm for $T_{2}$ induces the canonical distance function for the
Gaussian process $T_{2}\ni t\mapsto\sum_{i,j}\xi_{ij}t_{ij}$, we can use the
majorizing measure theorem (Theorem 3) in conjunction with Lemma 4 to obtain

$\displaystyle\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{t\in
T_{2}}Y_{t}-Y_{\tau}}\right]$
$\displaystyle\lesssim\mathfrak{g}(T_{2})+\Delta_{2}(T_{2})\sqrt{\log\kappa}.$

Substituting the definitions of $Y_{t}$ and $\kappa$ and rearranging, we get

$\displaystyle\mathfrak{b}(\mathscr{F}(T_{2}))$ $\displaystyle\lesssim
L\mathfrak{g}(T_{2})+\Delta_{2}(T_{2})\mathfrak{r}^{\mathfrak{b}}(\mathscr{F},T_{2})+\mathfrak{b}(\mathscr{F}(\tau))$
$\displaystyle\lesssim
L\mathfrak{b}(T)+\Delta_{2}(T_{2})\mathfrak{r}^{\mathfrak{b}}(\mathscr{F},T_{2})+\mathfrak{b}(\mathscr{F}(\tau)),$

where the last inequality follows from the fact that
$\mathfrak{g}(T_{2})\lesssim\mathfrak{b}(T)$ by Theorem 4. Combining the above
result with Proposition 1 concludes the proof of Theorem 1 with $S=T_{2}$. ∎

###  3.2 Proof of Theorem 2

Recall that, from Proposition 1, we obtain the bound
$\mathfrak{b}(\mathscr{F}(T))\lesssim
L\mathfrak{b}(T)+\mathfrak{b}(\mathscr{F}(T_{2}))$, where $T_{2}$ satisfies
$\mathfrak{g}(T_{2})\lesssim\mathfrak{b}(T)$. In this subsection, we will use
both classical (Kolmogorov) chaining and generic chaining to estimate
$\mathfrak{b}(\mathscr{F}(T_{2}))$.

We first state an entropy number estimate for uniformly Lipschitz function
classes on a totally bounded domain (_cf._ [8, Lemma 4.3.9]).

######  Lemma 6.

Let $(T,d)$ be metric space, such that, for a certain $B$ and $k\geq 1$, we
have
$N(T,d,\delta)<\mathopen{}\mathclose{{}\left(\frac{B}{\delta}}\right)^{k}$ for
all $\delta>0$, where $N(T,d,\delta)$ is the $\delta$-covering number for
$(T,d)$, _i.e._ , the minimum number of closed $d$-balls of radius $\delta$
needed to cover $T$. Consider the set $\mathscr{F}$ of $L$-Lipschitz functions
$f:T\to\mathbb{R}$ with $\mathopen{}\mathclose{{}\left\lVert
f}\right\rVert_{T}\leq LB$. Then, for each integer $m\geq 0$, we have
$e_{m}(\mathscr{F},d_{T})\leq C_{k}LB2^{-m/k}$.

Let $S=T_{2}$. For $m\geq 0$, we choose $\mathscr{F}_{m}\subset\mathscr{F}$
with admissible cardinality such that
$\sup_{f\in\mathscr{F}}d_{\mathsf{S}}(f,\mathscr{F}_{m})\leq
2e_{m}(\mathscr{F},d_{\mathsf{S}})$ and choose $S_{m}\subset T_{2}$ such that
each element of $S_{m}$ is an arbitrary point in each of the elements of the
partition $\mathcal{A}_{m}$, where $(\mathcal{A}_{m})_{m\geq 0}$ is an
admissible sequence in $T_{2}$ satisfying

$\sup_{t\in T_{2}}\sum_{m\geq
0}2^{m/2}\Delta_{2}(A_{m}(t))\lesssim\mathfrak{g}(T_{2})$

by the majorizing measure theorem. Let $p_{m}:\mathscr{F}\to\mathscr{F}_{m}$
be such that $d_{\mathsf{S}}(f,p_{m}(f))=d_{\mathsf{S}}(f,\mathscr{F}_{m})$
for any $f\in\mathscr{F}$, and let $\pi_{m}:T_{2}\to S_{m}$ be such that
$d_{2}(t,\pi_{m}(t))=d_{2}(t,S_{m})$ for any $t\in T_{2}$. Let
$f_{0}=p_{0}(f),\tau=\pi_{0}(t)$ for any $f\in\mathscr{F},t\in T_{2}$. For an
arbitrary $M\in\mathbb{N}$, consider the quantities

$\displaystyle\mathtt{U_{1}}:=\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F},t\in
T_{2}}\sum_{i=1}^{n}\varepsilon_{i}(f(t_{i})-p_{M}(f)(t_{i}))}\right]$
$\displaystyle\mathtt{U_{2}}:=\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F},t\in
T_{2}}\sum_{i=1}^{n}\varepsilon_{i}(p_{M}(f)(t_{i})-p_{M}(f)(\pi_{M}(t)_{i}))}\right]$
$\displaystyle\mathtt{U_{3}}:=\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F},t\in
T_{2}}\sum_{i=1}^{n}\varepsilon_{i}(p_{M}(f)(\pi_{M}(t)_{i})-p_{0}(f)(\pi_{0}(t)_{i}))}\right].$

It is obvious that

$\displaystyle\mathfrak{b}(\mathscr{F}(T_{2}))=\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f,t}\sum_{i=1}^{n}\varepsilon_{i}(f(t_{i})-f_{0}(\tau_{i}))}\right]\leq\mathtt{U_{1}}+\mathtt{U_{2}}+\mathtt{U_{3}}.$

For $\mathtt{U_{1}}$, by the Cauchy–Schwarz inequality

$\displaystyle\mathtt{U_{1}}$
$\displaystyle\leq\mathbf{E}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(\sum_{i=1}^{n}\varepsilon_{i}^{2}}\right)^{1/2}\sup_{f,t}\mathopen{}\mathclose{{}\left(\sum_{i=1}^{n}(f(t_{i})-p_{M}(f)(t_{i}))^{2}}\right)^{1/2}}\right]$
$\displaystyle\leq n\sup_{f\in\mathscr{F}}d_{\mathsf{S}}(f,p_{M}(f))\leq
cne_{M}(\mathscr{F},d_{\mathsf{S}}).$

Next, observe that

$\mathtt{U_{2}}\leq\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F}_{M},t\in
T_{2}}\sum_{i=1}^{n}\varepsilon_{i}(f(t_{i})-f(\pi_{M}(t)_{i}))}\right]$

and consider the following stochastic process $Y$ indexed by
$\mathscr{F}_{M}\times T_{2}$:
$Y:(f,t)\mapsto\sum_{i=1}^{n}\varepsilon_{i}f(t_{i})$. We will use generic
chaining to bound the supremum
$\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F}_{M},t\in
T_{2}}(Y_{f,t}-Y_{f,\pi_{M}(t)})}\right]$. Let

$\varrho=L\sup_{t\in T_{2}}\sum_{m\geq
M+1}2^{m/2}\mathopen{}\mathclose{{}\left\lVert\pi_{m}(t)-\pi_{m-1}(t)}\right\rVert_{2}.$

By the union bound,

$\displaystyle\mathbf{P}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F}_{M},t\in
T_{2}}(Y_{f,t}-Y_{f,\pi_{M}(t)})>u\varrho}\right]\leq\sum_{f\in\mathscr{F}_{M}}\mathbf{P}\mathopen{}\mathclose{{}\left[\sup_{t\in
T_{2}}(Y_{f,t}-Y_{f,\pi_{M}(t)})>u\varrho}\right],\qquad u>0.$

Notice that, for any $f\in\mathscr{F}_{M}$, the process
$t\mapsto\sum_{i=1}^{n}\varepsilon_{i}f(t_{i})$ satisfies the increment
condition

$\displaystyle\mathbf{P}\mathopen{}\mathclose{{}\left[Y_{f,s}-Y_{f,t}>u}\right]\leq\exp\mathopen{}\mathclose{{}\left(-\frac{u^{2}}{2L^{2}\mathopen{}\mathclose{{}\left\lVert
s-t}\right\rVert_{2}^{2}}}\right),\qquad u>0$

for all $s,t\in T_{2}$. Using chaining and the union bound again, we obtain

$\displaystyle\mathbf{P}\mathopen{}\mathclose{{}\left[\sup_{t\in
T_{2}}(Y_{f,t}-Y_{f,\pi_{M}(t)})>u\varrho}\right]$
$\displaystyle\leq\mathbf{P}\mathopen{}\mathclose{{}\left[\sup_{t\in
T_{2}}\sum_{m\geq M+1}(Y_{f,\pi_{m}(t)}-Y_{f,\pi_{m-1}(t)})>u\varrho}\right]$
$\displaystyle\leq\sum_{m\geq M+1}\sum_{s\in
S_{m}}\mathbf{P}\mathopen{}\mathclose{{}\left[Y_{f,s}-Y_{f,\pi_{m-1}(s)}>uL2^{m/2}\mathopen{}\mathclose{{}\left\lVert
s-\pi_{m-1}(s)}\right\rVert_{2}}\right]$ $\displaystyle\leq\sum_{m\geq
M+1}2^{2^{m+1}}\mathrm{e}^{-u^{2}2^{m-1}}$

Therefore,

$\displaystyle\mathbf{P}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F}_{M},t\in
T_{2}}(Y_{f,t}-Y_{f,\pi_{M}(t)})>u\varrho}\right]\leq
2^{2^{M}}\mathopen{}\mathclose{{}\left(\sum_{m\geq
M+1}2^{2^{m+1}}\mathrm{e}^{-u^{2}2^{m-1}}}\right)\leq\sum_{m\geq
M+1}2^{2^{m+2}}\mathrm{e}^{-u^{2}2^{m-1}}.$

By Proposition 4 and the choice of $(\pi_{m}(t))_{m\geq M}$, we then have

$\displaystyle\mathtt{U_{2}}\lesssim L\sup_{t\in T_{2}}\sum_{m\geq
M}2^{m/2}\Delta_{2}(A_{m}(t))\lesssim L\mathfrak{g}(T_{2})\lesssim
L\mathfrak{b}(T).$

For $\mathtt{U_{3}}$, we still consider the process
$Y:(f,t)\mapsto\sum_{i=1}^{n}f(t_{i})$ indexed by $\mathscr{F}\times T_{2}$,
but we now endow $\mathscr{F}\times T_{2}$ with the following metric: for
$f_{1},f_{2}\in\mathscr{F},s,t\in T_{2}$,

$\displaystyle
d_{3}((f_{1},s),(f_{2},t)):=\sqrt{n}d_{\mathsf{S}}(f_{1},f_{2})+L\mathopen{}\mathclose{{}\left\lVert
s-t}\right\rVert_{2}.$

Since $d_{3}((f_{1},s),(f_{2},t))\geq\mathopen{}\mathclose{{}\left\lVert
f_{1}(s)-f_{2}(t)}\right\rVert_{2}$, this process satisfies the increment
condition

$\displaystyle\mathbf{P}\mathopen{}\mathclose{{}\left[Y_{f_{1},s}-Y_{f_{2},t}>u}\right]\leq\exp\mathopen{}\mathclose{{}\left(-\frac{u^{2}}{2d_{3}((f_{1},s),(f_{2},t))^{2}}}\right),\qquad
u>0.$

By a generic chaining argument, we have

$\displaystyle\mathtt{U_{3}}$ $\displaystyle\lesssim\sup_{f\in\mathscr{F},t\in
T_{2}}\sum_{m=1}^{M}2^{m/2}d_{3}((p_{m}(f),(\pi_{m}(t)),(\pi_{m-1}(f),\pi_{m-1}(t))))$
$\displaystyle\lesssim\sqrt{n}\sup_{f\in\mathscr{F}}\sum_{m=1}^{M}2^{m/2}d_{\mathsf{S}}(p_{m}(f),p_{m-1}(f))+L\sup_{t\in
T_{2}}\sum_{m=1}^{M}2^{m/2}\mathopen{}\mathclose{{}\left\lVert\pi_{m}(t)-\pi_{m-1}(t)}\right\rVert_{2}$
$\displaystyle\lesssim\sqrt{n}\sup_{f\in\mathscr{F}}\sum_{m=1}^{M}2^{m/2}\big{(}d_{\mathsf{S}}(f,p_{m}(f))+d_{\mathsf{S}}(f,p_{m-1}(f))\big{)}+L\mathfrak{g}(T_{2})$
$\displaystyle\lesssim\sqrt{n}\sum_{m=0}^{M}2^{m/2}\sup_{f\in\mathscr{F}}d_{\mathsf{S}}(f,\mathscr{F}_{m})+L\mathfrak{b}(T)$
$\displaystyle\lesssim\sqrt{n}\sum_{m=1}^{M}e_{m}(\mathscr{F},d_{\mathsf{S}})+L\mathfrak{b}(T).$

Combining the above results and taking the infimum over $M$, we obtain

$\displaystyle\mathfrak{b}(\mathscr{F}(T_{2}))\lesssim
L\mathfrak{b}(T)+n\inf_{M}\mathopen{}\mathclose{{}\left\\{e_{M}(\mathscr{F},d_{\mathsf{S}})+\sum_{m=0}^{M}\frac{2^{m/2}}{\sqrt{n}}e_{m}(\mathscr{F},d_{\mathsf{S}})}\right\\}.$

In particular, if $\mathsf{X}=\mathscr{B}_{2}^{k}(R)\supset\mathsf{S}$, we
have $N(\mathsf{X},d_{2},\delta)\lesssim(R/\delta)^{k}$ by the standard
volumetric estimate. If all $f\in\mathscr{F}$ satisfy
$\mathopen{}\mathclose{{}\left\lVert f}\right\rVert_{\mathsf{X}}\leq LR$, then
we have $e_{m}(\mathscr{F},d_{\mathsf{X}})\leq C_{k}LR2^{-m/k}$ by Lemma 6.
Let

$\displaystyle
h(M):=2^{-M/k}+\frac{1}{\sqrt{n}}\sum_{m=0}^{M}2^{m(\frac{1}{2}-\frac{1}{k})},$

so that
$e_{M}(\mathscr{F},d_{\mathsf{X}})+\sum_{m=0}^{M}\frac{2^{m/2}}{\sqrt{n}}e_{m}(\mathscr{F},d_{\mathsf{X}})\leq
C_{k}LRh(M)$. For $k=1$, $\inf_{M}h(M)\lesssim\frac{1}{\sqrt{n}}$. For $k=2$,
for $n$ sufficiently large and
$M=\mathopen{}\mathclose{{}\left\lfloor\log_{2}n}\right\rfloor$, we have

$\displaystyle h(M)\lesssim\frac{1}{\sqrt{n}}+\frac{1+\log_{2}n}{\sqrt{n}}\leq
c\frac{\log n}{\sqrt{n}}.$

For $k>2$, for $n$ sufficiently large, we again let
$M=\mathopen{}\mathclose{{}\left\lfloor\log_{2}n}\right\rfloor$ and

$\displaystyle h(M)$ $\displaystyle\leq
2^{-M/k}+\frac{1}{\sqrt{n}}2^{M(\frac{1}{2}-\frac{1}{k})}\mathopen{}\mathclose{{}\left(\sum_{m=0}^{\infty}2^{-m(\frac{1}{2}-\frac{1}{k})}}\right)$
$\displaystyle\leq C_{k}n^{-1/k}.$

The fact that $e_{m}(\mathscr{F},d_{\mathsf{S}})\leq
e_{m}(\mathscr{F},d_{\mathsf{X}})$ concludes the proof.

##  4 Examples

We give two examples to illustrate the use of our chain rule. The first
example is an improvement of a result from [4], which was an intermediate step
in bounding Rademacher complexities of neural nets with a uniform upper bound
on the spectral norm of their weight matrices. Given an $n$-tuple of points
$z^{n}:=(z_{1},\ldots,z_{n})$ in some space $\mathscr{Z}$, the (normalized)
empirical Rademacher complexity $\hat{\mathscr{R}}_{n}$ of a class
$\mathscr{G}$ of real-valued functions $g:\mathcal{Z}\to\mathbb{R}$ is defined
as

$\displaystyle\hat{\mathscr{R}}_{n}(\mathscr{G})\equiv\hat{\mathscr{R}}_{n}(\mathscr{G};z^{n}):=\frac{1}{n}\mathbf{E}_{\varepsilon}\mathopen{}\mathclose{{}\left[\sum_{i=1}^{n}\varepsilon_{i}g(z_{i})}\right],$

see, e.g., [1]. Then we have the following result, which improves on Theorem 4
in [4]:

######  Proposition 2.

For some $R>0$, let $\mathscr{G}$ be a class of functions from $\mathscr{Z}$
to $[-R,R]$. Let $\mathscr{F}$ be the class of $L$-Lipschitz functions from
$[-R,R]$ to $\mathbb{R}$. Then the Rademacher complexity of the composite
class $\mathscr{F}\circ\mathscr{G}:=\mathopen{}\mathclose{{}\left\\{f\circ
g:f\in\mathscr{F},g\in\mathscr{G}}\right\\}$ satisfies

$\displaystyle\hat{\mathscr{R}}_{n}(\mathscr{F}\circ\mathscr{G})\lesssim
L\mathopen{}\mathclose{{}\left(\frac{R}{\sqrt{n}}+\hat{\mathscr{R}}_{n}(\mathscr{G})}\right).$

###### Proof.

The result follows from Theorem 2 with $k=1$ and
$T=\mathopen{}\mathclose{{}\left\\{(g(z_{i}))_{1\leq i\leq
n}:g\in\mathscr{G}}\right\\}$. ∎

######  Remark 3.

For comparison, the bound in [4] has the form

$\hat{\mathscr{R}}_{n}(\mathscr{F}\circ\mathscr{G})\lesssim
L(\frac{R}{\sqrt{n}}+\log^{3/2}n\cdot\hat{\mathscr{R}}_{n}(\mathscr{G})),$

so our improvement consists in removing the logarithmic factor in front of the
second term on the right-hand side.

Our second example involves functions in a Reproducing Kernel Hilbert Space
(RKHS). Due to space limitations, we can only give a brief sketch; the reader
is invited to consult [3, Chaps. 2 and 4] for the background. Let
$\mathsf{X}=\mathscr{B}^{k}_{2}(\sqrt{k}R)$ for some $R>0$. Let
$(\mathscr{H}_{K},\mathopen{}\mathclose{{}\left\langle\cdot,\cdot}\right\rangle_{K})$
be an RKHS associated with a Mercer kernel
$K:\mathsf{X}\times\mathsf{X}\to\mathbb{R}$; then we consider
$\mathscr{F}=I_{K}(\mathscr{B}^{K}(\varrho))$, where
$\mathscr{B}^{K}(\varrho)=\mathopen{}\mathclose{{}\left\\{f\in\mathscr{H}_{K}:\mathopen{}\mathclose{{}\left\lVert
f}\right\rVert_{K}\leq\varrho}\right\\}$ is the zero-centered closed ball of
radius $\varrho$ in $\mathscr{H}_{K}$ and $I_{K}$ is the embedding map from
$\mathscr{H}_{K}$ into the space $\mathcal{C}(\mathsf{X})$ of continuous real-
valued functions on $\mathsf{X}$ equipped with the uniform norm
$\mathopen{}\mathclose{{}\left\lVert\cdot}\right\rVert_{\mathsf{X}}$. We have
the following result for the Gaussian RKHS, which parallels Maurer’s result in
[6, Section 3.2] if we impose the same assumption that $T$ is a projection of
another RKHS function class onto a set of samples.

######  Proposition 3.

Consider the Gaussian kernel
$K(x,y)=\exp\mathopen{}\mathclose{{}\left(-\frac{1}{2\sigma^{2}}\mathopen{}\mathclose{{}\left\lVert
x-y}\right\rVert_{2}^{2}}\right)$, where $\sigma^{2}>0$ is the kernel
bandwidth. Then, for any $T\subset(\mathscr{B}^{k}_{2}(R))^{n}$,

$\displaystyle\mathfrak{b}(\mathscr{F}(T))\lesssim\varrho\mathopen{}\mathclose{{}\left(\frac{\mathfrak{b}(T)}{\sigma}+\sqrt{n}}\right).$
(7)

######  Remark 4.

See the Remark following Theorem 2 for the motivation behind our choices of
$\mathsf{X}$ and $T$. Note, however, that we use Theorem 1 to prove the above
proposition; although one can use existing bounds on the covering numbers for
subsets of an RKHS (compactly embedded into a suitable space of real-valued
continuous functions) in conjunction with Theorem 2, but the constant $C_{k}$
appearing in Equation 3 will then have exponential dependence on $k$.

###### Proof.

Let $K_{x}$ denote the function $y\mapsto K(x,y)$, viewed as an element of
$\mathscr{H}_{K}$. Using the reproducing kernel property, it can be shown that
$\mathopen{}\mathclose{{}\left\lVert
K_{x}-K_{y}}\right\rVert_{K}\leq\frac{1}{\sigma}\mathopen{}\mathclose{{}\left\lVert
x-y}\right\rVert$. This in turn implies that $\mathscr{F}$ is uniformly
Lipschitz: for any $f\in\mathscr{F}$ and all $x,y\in\mathsf{X}$,

$\displaystyle\mathopen{}\mathclose{{}\left\lvert f(x)-f(y)}\right\rvert$
$\displaystyle=\mathopen{}\mathclose{{}\left\langle
K_{x}-K_{y},f}\right\rangle_{K}\leq\mathopen{}\mathclose{{}\left\lVert
f}\right\rVert_{K}\mathopen{}\mathclose{{}\left\lVert
K_{x}-K_{y}}\right\rVert_{K}\leq\frac{\mathopen{}\mathclose{{}\left\lVert
f}\right\rVert_{K}}{\sigma}\mathopen{}\mathclose{{}\left\lVert
x-y}\right\rVert_{2}.$

In particular, $\mathopen{}\mathclose{{}\left\lVert f}\right\rVert_{{\rm
Lip}}\leq\frac{\varrho}{\sigma}$ for all $f\in\mathscr{F}$.

We now apply Theorem 1 and estimate the terms dependent on $\mathscr{H}_{K}$.
Since $\mathopen{}\mathclose{{}\left\lVert
S}\right\rVert_{\infty,\infty}\leq\mathopen{}\mathclose{{}\left\lVert
T}\right\rVert_{\infty,\infty}$, we have
$S\subset(\mathscr{B}^{k}_{2}(\sqrt{k}R))^{n}$. For any $s,t\in S$, we can use
the reproducing kernel property, the independence of $\varepsilon_{i}$, and
the Lipschitz continuity of $t\mapsto K_{t}$ to show that

$\displaystyle\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F}}\sum_{i=1}^{n}\varepsilon_{i}(f(s_{i})-f(t_{i}))}\right]$
$\displaystyle=\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F}}\sum_{i=1}^{n}(\varepsilon_{i}\mathopen{}\mathclose{{}\left\langle
K_{s_{i}}-K_{t_{i}},f}\right\rangle_{K})}\right]$ (8)
$\displaystyle=\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{f\in\mathscr{F}}\mathopen{}\mathclose{{}\left\langle
f,\sum_{i}\varepsilon_{i}(K_{s_{i}}-K_{t_{i}})}\right\rangle_{K}}\right]$ (9)
$\displaystyle=\varrho\mathbf{E}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left\lVert\sum_{i}\varepsilon_{i}(K_{s_{i}}-K_{t_{i}})}\right\rVert_{K}}\right]$
(10)
$\displaystyle\leq\varrho\sqrt{\mathbf{E}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left\lVert\sum_{i}\varepsilon_{i}(K_{s_{i}}-K_{t_{i}})}\right\rVert_{K}^{2}}\right]}$
(11)
$\displaystyle\leq\varrho\sqrt{\sum_{i}\mathopen{}\mathclose{{}\left\lVert
K_{s_{i}}-K_{t_{i}}}\right\rVert_{K}^{2}}$ (12)
$\displaystyle\leq\frac{\varrho}{\sigma}\mathopen{}\mathclose{{}\left\lVert
s-t}\right\rVert_{2}$ (13)

for all $f\in\mathscr{F}$ and all $s,t\in S$, where (10) uses the Riesz
representation theorem, (11) uses Jensen’s inequality, and the last two
inequalities use independence of $\varepsilon_{i}$ and Lipschitz continuity of
$x\mapsto K_{x}$, which implies that
$\mathfrak{r}^{\mathfrak{b}}(\mathscr{F},S)\leq\frac{\varrho}{\sigma}$.
Moreover, since $\mathscr{F}=I_{K}(\mathcal{B}^{K}(\varrho))$, we have
$\mathfrak{b}(\mathscr{F}(\tau))\leq\sqrt{n}\varrho$ for any $\tau\in S$, see,
e.g., [1]. Therefore, applying Theorem 1 and using the fact that
$\Delta_{2}(S)\leq\sqrt{2\pi}\mathfrak{g}(S)\lesssim\mathfrak{b}(T)$, we
obtain (7). ∎

##  Appendix A Auxiliary results and proofs

###  A.1 Proof of Lemma 4

######  Proposition 4.

For some $u,\varrho,\zeta>0,w\in\mathbb{Z}_{+}$, let

$\displaystyle p(u):=\sum_{m\geq
1}2^{2^{m+1+w}}\mathrm{e}^{-u^{2}2^{m-1}}\mbox{ and }q(u):=p(u)\wedge 1.$ (14)

If a nonnegative random variable $Y$ satisfies
$\mathbf{P}\mathopen{}\mathclose{{}\left[Y>u\varrho+\zeta}\right]\leq q(u)$,
then we have

$\displaystyle\mathbf{E}Y\leq C_{w}\varrho+\zeta.$ (15)

###### Proof.

Observe that for $m\geq 1$ and for $u\geq C_{w}$ such that $C_{w}^{2}\geq
2^{3+w}$, we have

$\displaystyle
u^{2}2^{m-1}\geq\frac{u^{2}}{2}+u^{2}2^{m-2}\geq\frac{u^{2}}{2}+2^{m+1+w},$

which yields

$\displaystyle q(u)=(p(u)\mathbf{1}_{\\{u\geq
C_{w}\\}}+p(u)\mathbf{1}_{\\{u<C_{w}\\}})\wedge 1\leq c\mathbf{1}_{\\{u\geq
C_{w}\\}}\mathrm{e}^{-u^{2}/2}+\mathbf{1}_{\\{u<C_{w}\\}}.$

Now we convert the tail bound to a moment bound. Since $Y$ is nonnegative, we
have

$\displaystyle\mathbf{E}Y=\int_{0}^{\infty}\mathbf{P}\mathopen{}\mathclose{{}\left[Y>y}\right]\mathrm{d}y=\int_{-\zeta/\varrho}^{\infty}\mathbf{P}\mathopen{}\mathclose{{}\left[Y>u\varrho+\zeta}\right]\,\varrho\,\mathrm{d}u\leq\int_{-\zeta/\varrho}^{\infty}q(u)\,\varrho\,\mathrm{d}u\leq
C_{w}\varrho+\zeta,$

which concludes the proof. ∎

###### Proof of Lemma 4.

Assume for some $(\mathcal{A}_{m})$, $\sup_{t\in
T}\sum_{m=0}^{\infty}2^{m/2}\Delta_{d}(A_{m}(t))<\infty$. It suffices to
consider finite $T$ since the result can be extended to countable case by
standard convergence arguments (see _e.g._ [8, Chapter 2]). Fix $\tau\in T$.
For any $m\geq 0$, for each $A(t)\in\mathcal{A}_{m}$ uniquely containing $t$,
we arbitrarily take a point $\pi_{m}(t):=\pi_{m}(A(t))\in A(t)$ as the
approximation point for $t$ or $A(t)$. For sufficiently large
$M\in\mathbb{N}$, we have $\pi_{M}(t)=t$. Then for any $t\in T$, by choosing
$\tau=\pi_{0}(t)$, we have the usual chaining decomposition
$Y_{t}-Y_{\tau}=\sum_{m=1}^{M}Y_{\pi_{m}(t)}-Y_{\pi_{m-1}(t)}$. Let

$\displaystyle\varrho:=\sup_{t\in T}\sum_{m=1}^{M}\varrho_{m}(t):=\sup_{t\in
T}\sum_{m=1}^{M}2^{m/2}d(\pi_{m}(t),\pi_{m-1}(t)),$
$\displaystyle\zeta:=\sup_{t\in T}\sum_{m=1}^{M}\zeta_{m}(t):=\sup_{t\in
T}\sum_{m=1}^{M}\sqrt{2\log\kappa}d(\pi_{m}(t),\pi_{m-1}(t)).$

For any $u>0$, let

$\displaystyle\Omega_{u}:=\mathopen{}\mathclose{{}\left\\{\sup_{t\in
T}Y_{t}-Y_{\tau}>\sup_{t\in
T}\sum_{m=1}^{M}u\varrho_{m}(t)+\zeta_{m}(t)}\right\\}.$

Since $u\varrho+\zeta\geq\sup_{t\in
T}\sum_{m=1}^{M}u\varrho_{m}(t)+\zeta_{m}(t)$, we obtain

$\displaystyle\mathbf{P}\mathopen{}\mathclose{{}\left[\sup_{t\in
T}Y_{t}-Y_{\tau}>u\varrho+\zeta}\right]\leq\mathbf{P}\mathopen{}\mathclose{{}\left[\Omega_{u}}\right].$

Note that the occurrence of $\Omega_{u}$ implies that

$\displaystyle\exists\,t\in T,\,\exists\,m\geq
1,\,Y_{\pi_{m}(t)}-Y_{\pi_{m-1}(t)}>u\varrho_{m}(t)+\zeta_{m}(t).$

Also, the size of
$\mathopen{}\mathclose{{}\left\\{\pi_{m}(t),\pi_{m-1}(t):t\in T}\right\\}$ can
be bounded by $2^{2^{m}}\cdot 2^{2^{m}}=2^{2^{m+1}}$. Using the union bound
and the increment condition of $Y_{t}$ in (4), we have

$\displaystyle\mathbf{P}\mathopen{}\mathclose{{}\left[\Omega_{u}}\right]$
$\displaystyle\leq\sum_{m=1}^{M}2^{2^{m+1}}\mathbf{P}\mathopen{}\mathclose{{}\left[Y_{\pi_{m}(t)}-Y_{\pi_{m-1}(t)}>u\varrho_{m}(t)+\zeta_{m}(t)}\right]$
$\displaystyle\leq\sum_{m=1}^{M}2^{2^{m+1}}\kappa\exp\mathopen{}\mathclose{{}\left(-\frac{(u2^{m/2}+\sqrt{2\log\kappa})^{2}}{2}}\right)$
$\displaystyle\leq\sum_{m=1}^{M}2^{2^{m+1}}\mathrm{e}^{-u^{2}2^{m-1}}=:p(u).$

Hence, $\mathbf{P}\mathopen{}\mathclose{{}\left[\Omega_{u}}\right]\leq
p(u)\wedge 1=:q(u)$. Since $\sup_{t}Y_{t}-Y_{\tau}$ is nonnegative, we use
Proposition 4 to obtain

$\displaystyle\mathbf{E}\mathopen{}\mathclose{{}\left[\sup_{t\in
T}Y_{t}-Y_{\tau}}\right]\leq c\varrho+\zeta\leq c\sup_{t\in
T}\sum_{m=0}^{\infty}2^{m/2}\Delta_{d}(A_{m}(t))+c\sup_{t\in
T}\Delta_{d}(T)\sqrt{\log\kappa},$

where, in the last inequality, the second term is due to the fact that, since
for any $t$ the series $\sum_{m}2^{m/2}\Delta_{d}(A_{m}(t))$ converges, so
does $\sum_{m}\Delta_{2}(A_{m}(t))$. Then
$\sum_{m}\Delta_{d}(A_{m}(t))=\Delta_{d}(T)\sum_{m}(\Delta_{d}(A_{m}(t))/\Delta_{d}(T))$
is dominated by the first term of the series $\Delta_{d}(T_{2})$ up to some
constant. ∎

## References

  * [1] Peter L. Bartlett and Shahar Mendelson.  Rademacher and Gaussian Complexities: Risk Bounds and Structural Results.  Journal of Machine Learning Research, 3:463–482, November 2002\.
  * [2] Witold Bednorz and Rafał Latała.  On the boundedness of Bernoulli processes.  Annals of Mathematics, 180:1167–1203, November 2014.
  * [3] F. Cucker and D.X. Zhou.  Learning Theory: An Approximation Theory Viewpoint.  Cambridge University Press, 2007.
  * [4] Noah Golowich, Alexander Rakhlin, and Ohad Shamir.  Size-independent sample complexity of neural networks.  arXiv preprint 1712.06541, 2019.
  * [5] Michel Ledoux and Michel Talagrand.  Probability in Banach Spaces.  Springer Berlin Heidelberg, Berlin, 1991.
  * [6] Andreas Maurer.  A Chain Rule for the Expected Suprema of Gaussian Processes.  In Peter Auer, Alexander Clark, Thomas Zeugmann, and Sandra Zilles, editors, Algorithmic Learning Theory, Lecture Notes in Computer Science, pages 245–259. Springer International Publishing, 2014.
  * [7] Andreas Maurer.  A Vector-Contraction Inequality for Rademacher Complexities.  In Ronald Ortner, Hans Ulrich Simon, and Sandra Zilles, editors, Algorithmic Learning Theory, Lecture Notes in Computer Science, pages 3–17. Springer International Publishing, 2016.
  * [8] Michel Talagrand.  Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems.  Springer, Berlin, 2014.


# Revisiting Generative Commonsense Reasoning: A Pre-Ordering Approach

Chao Zhao1 Faeze Brahman2 Tenghao Huang1 Snigdha Chaturvedi1
{zhaochao, tenghao<EMAIL_ADDRESS><EMAIL_ADDRESS>
1 UNC Chapel Hill 2 Allen Institute for AI

###### Abstract

Pre-trained models (PTMs) have lead to great improvements in natural language
generation (NLG). However, it is still unclear how much commonsense knowledge
they possess. With the goal of evaluating commonsense knowledge of NLG models,
recent work has proposed the problem of generative commonsense reasoning,
e.g., to compose a logical sentence given a set of unordered concepts.
Existing approaches to this problem hypothesize that PTMs lack sufficient
parametric knowledge for this task, which can be overcome by introducing
external knowledge or task-specific pre-training objectives. Different from
this trend, we argue that PTM’s inherent ability for generative commonsense
reasoning is underestimated due to the order-agnostic property of its input.
In particular, we hypothesize that the order of the input concepts can affect
the PTM’s ability to utilize its commonsense knowledge. To this end, we
propose a pre-ordering approach to elaborately manipulate the order of the
given concepts before generation. Experiments show that our approach can
outperform the more sophisticated models that have access to a lot of external
data and resources.

##  1 Introduction

Pre-trained models (PTMs), such as BART Lewis et al. (2020) and T5 Raffel et
al. (2020), have achieved significant progress in many natural language
generation tasks. However, their ability to reason with common sense while
generating text is questionable. To push research in this direction, Lin et
al. (2020) proposed the task of generative commonsense reasoning (GCR), where
the goal is to compose a fluent and rational sentence from a set of concepts.
Figure 1 shows an example of this problem. To achieve this goal, the model
must do commonsense reasoning to build connections between the given concepts
and produce a logically sound sentence (e.g., it is the pitcher who throws the
ball to the batter rather than the other way).

Figure 1: Example of the GCR task.

Prior works hypothesize that the vanilla PTMs are not capable of solving this
challenging task Liu et al. (2021); Fan et al. (2020); Zhou et al. (2021)
partly because their self-supervised objectives do not explicitly capture the
relational commonsense knowledge Zhou et al. (2021). These works enhance the
PTMs’ performance by explicitly introducing knowledge during fine-tuning or
implicitly teaching the model during further pre-training. However, we observe
that in some cases, even without external knowledge, PTMs can create
reasonable output for this task, indicating that PTMs may already have the
commonsense reasoning ability to some degree. Therefore the challenge turns
out to be how to make it easier for PTMs to fully utilize the inherent
commonsense knowledge.

One potential solution of this challenge is to make the order of input
concepts more natural and aligned with commonsense. For example, in Figure 1,
taking {pitcher, throw, ball, batter} as the input is better than {batter,
throw, ball, pitcher}, since the order of concepts in the former input is more
close to that in the outputs. Models that are not pre-trained, such as LSTM
and GRU, prefer a pre-ordering of input tokens to align them with the
(expected) output Vinyals et al. (2016); Bisazza and Federico (2016). For
PTMs, recent works Kale and Rastogi (2020); Ribeiro et al. (2021); Hoyle et
al. (2021) show that they can achieve reasonable performance on graph-to-text
tasks without pre-ordering. However, the impact of pre-ordering on PTMs, in
general, is not well analyzed.

In this work, we revisit PTMs’ ability of generative commonsense reasoning
without access to external knowledge or task-specific pre-training. We choose
BART and T5, two state-of-the-art PTMs, as our underlying models. To analyze
the utility of pre-ordering the concepts on models’ performance, we introduce
Planned-BART and Planned-T5 to manipulate the input concept order before
generation, which helps to make the order of input concepts more natural (more
close to the order of concepts in the output sentence). We experimentally show
that via pre-ordering, Planned-BART and Planned-T5 exceed the more
sophisticated models that have access to external knowledge or training data.
It indicates that PTM’s inherent ability for generative commonsense reasoning
was underestimated while a simple pre-ordering step can help PTMs better use
this ability.

##  2 Related Works

###  2.1 Generative Commonsense Reasoning

There are two major approaches to enhance the vanilla PTM’s ability of
commonsense reasoning on generation. The first approach is to introduce
explicit knowledge from external sources such as ConceptNet Liu et al. (2021)
and retrieved prototypes Fan et al. (2020); Wang et al. (2021), which can
facilitate GSR by either building connections between related concepts or
providing adjunct words for the input. The second approach is to explicitly
teach models to reason over the concepts via new pre-training objectives Zhou
et al. (2021). Different from these works, we examine PTMs’ inherent ability
of GSR without the help of external knowledge or task-specific pre-training.

###  2.2 Sequence Pre-Ordering

Previous works have shown that the pre-ordering of input sequence can improve
the task of graph-to-text generation Moryossef et al. (2019); Zhao et al.
(2020), but they use non-pre-trained LSTM and the pre-ordering methods rely on
rich structural information from the input. We instead focus on PTMs and non-
structural input. For PTMs, Hessel and Schofield (2021) and Sinha et al.
(2021) show that PTMs are resilient to shuffling the order of input tokens on
the tasks of natural language understanding, but they didn’t study the
generation problem. Hoyle et al. (2021) show that a suitable pre-ordering can
improve the generation quality. However, they didn’t provide a general pre-
ordering method for the problem of keywords-to-text generation.

##  3 Generative Commonsense Reasoning

###  3.1 Task Formalization

Given a set of lemmatized tokens representing concepts
$\mathcal{X}=\\{x_{1},\cdots,x_{m}\\}$, where each $x_{i}$ can be a noun or a
verb, the goal is to generate a fluent and grammatically correct English
sentence $\mathbf{y}=\\{y_{1},\cdots,y_{n}\\}$ such that it contains all of
the concepts in $\mathcal{X}$. The task does not require $x_{i}$ to have the
same morphological form as it appears in $\mathbf{y}$. Figure 1 shows an
example of the task. Note that $\mathcal{X}$ is an unordered set of concepts.
We refer to a permutation of $\mathcal{X}$ as a Plan of the concept set. For a
given output sentence $\mathbf{y}$, we re-order $\mathcal{X}$ to make the
concepts have the same order as those in $\mathbf{y}$ and call it as the
Skeleton of $\mathbf{y}$. Note that skeletons are associated with the outputs
while plans are determined before generation. We refer to the plans which are
identical to the references’ skeletons as Oracle Plans.

Model $\backslash$ Metrics | ROUGE-2/L | BLEU-3/4 | METEOR | CIDEr | SPICE | Coverage
---|---|---|---|---|---|---
BART Lin et al. (2020) |  ${22.23}$ $41.98$ |  $36.3$ $26.3$ | ${30.9}$ | $13.92$ | ${30.6}$ | ${97.35}$
EKI-BART Fan et al. (2020) |  ${24.36}$ ${45.42}$ |  ${42.9}$ ${32.1}$ | ${32.0}$ | ${16.80}$ | ${32.5}$ | -
KG-BART Liu et al. (2021) |  ${23.38}$ ${44.54}$ |  ${42.1}$ ${30.9}$ | ${32.4}$ | ${16.83}$ | ${32.7}$ | ${98.68}$
Planned-BART (Ours) |  ${24.97}$ ${46.13}$ |  ${44.8}$ ${34.1}$ | ${32.9}$ | ${17.47}$ | ${33.1}$ | ${98.99}$
T5 Lin et al. (2020) |  ${22.01}$ ${42.97}$ |  ${39.0}$ ${28.6}$ | ${30.1}$ | ${14.96}$ | ${31.6}$ | ${95.29}$
CALM Zhou et al. (2021) | \- - |  \- $\mkern 9.0mu{29.5}$ | ${31.9}$ | ${15.61}$ | ${33.2}$ | -
RE-T5 Wang et al. (2021) | \- - | \- - | - | - | ${34.3}$ | -
Planned-T5 (Ours) |  ${24.07}$ ${46.11}$ |  ${44.6}$ ${33.7}$ | ${32.8}$ | ${17.60}$ | ${34.0}$ | ${98.60}$
Human Performance |  $48.88$ $63.79$ |  $48.2$ $44.9$ | $36.2$ | $43.53$ | $63.5$ | $99.31$
Table 1:  Automatic evaluation of generation quality. We compare our methods
with pre-train- or knowledge-enhanced baselines. Our best model outperforms
previous models on all automatic measures. The only exception is RE-T5, which
uses both external knowledge and pre-training (with 7 times larger training
data).

We use BART and T5, two state-of-the-art PTMs, as the underlying generation
models. Both models are based on the Transformer architecture Vaswani et al.
(2017). Similar to other sequence-to-sequence models, they receive
$\mathbf{x}=\\{x_{1},\cdots,x_{m}\\}$ as input, and model the probability of
the output sequence $\mathbf{y}=\\{y_{1},\cdots,y_{n}\\}$ as:

$p(\mathbf{y}\mid\mathbf{x};\bm{\theta})=\prod_{t=1}^{|\mathbf{y}|}p\left(y_{t}\mid
y_{1:t-1},\mathbf{x};\bm{\theta}\right).$ (1)

###  3.2 Planned Model

To fine-tune PTMs on this task, previous works regard the input as an
unordered set and use its random linearization as the input in both training
and inference phases. Although it is trained in an order-agnostic setting,
PTMs are naturally position-sensitive models because the same input words in
different permutations have different positional representations.

Leveraging this property, we introduce Planned-BART and Planned-T5 to make
both models aware of the input order by regarding the input as an ordered
sequence. To order the input concepts properly, in the training phase, we re-
order the concepts according to the corresponding oracle plan. That is, we
force the order of concepts in both input and output sequences to be identical
during training, which can better help the model utilize its inherent
commonsense reasoning capabilities. In the inference phase, the oracle plans
of concepts are unavailable. We instead obtain the plan using a Planner.
Leveraging the power of PTMs, the planner is a vanilla BART or T5 model, which
is fine-tuned on unordered (randomly linearized) input and produces a sentence
as output. The skeleton of the planner’s output forms the plan for planned
models.

##  4 Experiments

###  4.1 Dataset and Evaluation

We conduct experiments 111Code is available at
https://github.com/zhaochaocs/Planned-PTM on the CommonGen dataset Lin et al.
(2020), which contains 35k concepts-sentence pairs for
training/validation/test. To build concepts-reference pairs, CommonGen first
collects frequently co-occurring concepts from image captions. Each concept-
set contains three to five concepts. The references in the training set are
original captions while those in the validation and test sets are collected by
crowd-sourcing.

The quality of the generated text is evaluated through several automatic
metrics such as BLEU Papineni et al. (2002), ROUGE Lin (2004), METEOR Banerjee
and Lavie (2005), CIDEr Vedantam et al. (2015), and SPICE Anderson et al.
(2016). We also report Coverage Lin et al. (2020), which is the average
percentage of input concepts that are present in the output sentences.

###  4.2 Results

We compare the performance of our pre-ordered method with the unordered BART
and T5, as well as two knowledge-enhanced BART models: EKI-BART and KG-BART,
and two T5 models enhanced by further pre-training: CALM and RE-T5. Table 1
lists the results of automatic measures. The training details can be found in
Appendix A.

Our Planned-BART and Planned-T5 models outperform vanilla BART and T5 models,
demonstrating that pre-ordering the input helps PTMs in effectively leveraging
their inherent commonsense knowledge. Our models also outperform three out of
four baselines that use external knowledge or pre-training objectives. The
only exception is RE-T5, which is further pre-trained.This indicates that PTMs
inherently contain a lot of commonsense knowledge that needs to be first
utilized before bringing in information from external sources.

To further explore the potential of the pre-ordering method, we conduct
another experiment to investigate the impact of concept orders on generation
quality. Given a test concept set, we feed all of its permutations to either
BART or Planned-BART to generate sentences. We then rank the sentences
according to their probabilities in Equation 1 and pick the most probable
sentence as the final output. We refer to the methods using this strategy as
BART Rank and Planned-BART Rank, respectively. Note that the ranking method is
computationally inefficient. In this work, we only use these models to provide
an estimate of the upper bound on the performance of the pre-ordering method.

As shown in Table 2, the performance of Planned-BART is close to its ranking
variant. This demonstrates the effectiveness of our planning strategy – it
helps Planned-BART achieve a performance comparable to the upper bound at a
much lower computational overhead. We also observe that Planned-BART Rank
achieves better scores than BART Rank. This is because Planned-BART is trained
on oracle plans, which helps it in better utilizing its inherent commonsense
knowledge.

Model $\backslash$ Metrics | R-2 | B-4 | M | C | S
---|---|---|---|---|---
Planned-BART | 24.97 | 34.1 | 32.9 | 17.47 | 33.1
BART Rank | 24.31 | 33.0 | 33.0 | 17.39 | 33.2
Planned-BART Rank | 25.04 | 35.0 | 33.3 | 17.89 | 33.6
Table 2:  Evaluation of Planned-BART and ranking models on ROUGE-2, BLEU-4,
METEOR, CIDEr, and SPICE.

###  4.3 Human Evaluation

We randomly select 100 test instances and evaluate the generation quality of a
system according to Rationality, Fluency, and Succinctness as in Liu et al.
(2021). We conduct a pairwise comparison between Planned-BART Rank (the best
model) with our three other methods.For each test instance, we obtain the
output sentences from two different models, and then ask three workers on
Amazon Mechanical Turk to compare the two sentences according to the three
measures listed above. More details can be found in Appendix B.

Table 3 lists the results, where negative scores indicate worse performance
compared with Planned-BART Rank. The original BART performs the worst on all
measures, while Planned-BART achieves closer quality to BART Rank and Planned-
BART Rank. These results are consistent with those of automatic evaluations
and support our claim that Planned-BART can be a reasonable trade-off between
performance and efficiency.

Model $\backslash$ Metrics | Ration | Fluency | Succinct
---|---|---|---
BART | -0.38 | -0.33 | -0.56
BART Rank | -0.10 | 0.04 | -0.13
Planned-BART | -0.29 | -0.19 | -0.17
Table 3:  Results of human evaluation on rationality, fluency, and
succinctness. We report the pair-wise scores between Planned-BART Rank (the
best model) with three other models. Negative scores indicates worse
performance compared with Planned-BART Rank.

##  5 Analysis

In this section, we analyze the impact of input permutation on the model and
the generated sentences.

###  5.1 Permutation Invariance

We first examine how the output changes when the original BART (which we refer
to as Unordered-BART for clarity) and Planned-BART receive all possible
permutations of concepts as input. We compare the skeleton of Planned-BART’s
outputs with the input plans and find that the output skeleton is consistent
with the order of input concept in 94% of the cases, which is as expected.

In contrast, for Unordered-BART, we find that for 61% of the permutations, it
can organize the concepts in one particular order irrespective of the input
order. More details are provided in Appendix C. This observation suggests that
Unordered-BART is permutation-invariant to the input to some degree. However,
it is difficult for the model to be entirely insensitive to the input
permutation, which explains the performance difference between BART and BART
Rank: a ranking strategy helps select a more suitable permutation of input and
can therefore improve the generation quality.

###  5.2 Impact of Permutation on Encoding

The observations in Section 5.1 prompt a question about how Unordered-BART and
Planned-BART have different behaviors when receiving input permutation. Here,
we explore this question by studying the impact of input permutation on the
model encoder, especially the global attention distributions and the local
attention strength between certain word pairs.

One possible reason for the permutation invariance of Unordered-BART is that
although different input plans have different positional embeddings and may
affect hidden states of the lower layers, the encoder can build stable
association among tokens at the higher layers, alleviating the disturbance
from positional embeddings. For example, the model may know that people should
“ride a bike on trail” even when the concept order is {ride, trail, bike}. We
measure the word association inside the encoder using the strength of
attention weights between concepts.

To verify our assumption, we calculate (i) the Jensen–Shannon divergence (JSD)
of the encoder attention distributions w.r.t. all possible permutations of the
input, and (ii) the variance of encoder hidden states w.r.t. the input
permutations. Figure 2 shows the layer-wise JSD and variance averaged over the
test set. For comparison, we also include the results from a randomly-
initialized BART and the pre-trained BART (without fine-tuning).

Figure 2: Left: JS divergence of encoder attention distributions w.r.t. the
input permutations. Right: the variance of encoder hidden states w.r.t. input
permutations.

From Figure 2 we observe that the attention distributions of Planned-BART have
high JS divergence at each layer, and have a similar trend compared with that
of Pre-trained BART. It indicates that attention distributions of these two
models are affected by the input permutation, which is expected since their
input is well ordered during pre-training or fine-tuning. As a result, the
variances of hidden states on both models increase with a growth in layer
depth. In contrast, the JS divergence of attention in Unordered-BART gets
close to 0 starting from layer 2 and becomes similar to that of the randomly
initialized model. It indicates that the encoder can assign stable attention
distributions to the input despite the difference in permutation. Because of
this, the variances of hidden states on these two models decrease as the layer
goes deeper. It partially explains the permutation invariance of Unordered-
BART. We also noticed a substantial negative correlation between the variance
of the encoder output and the percentage of the mode sentence (Spearman’s
$\rho=-0.435$), which supports our explanation.

In addition to the analysis of global attention distribution, we also
investigate local attention patterns, i.e., whether the attention weights
between concept tokens can reflect their commonsense relations. More details
are listed in Appendix D. We find that compared with a randomly-initialized
BART, the pre-trained BART is better at tracking commonsense relations of
concepts despite input permutation, and fine-tuning can further strengthen
this capability. We also find that the model heavily relies on the tracking
ability when generating texts. It demonstrates that BART has the commonsense
reasoning ability to some degree, and it is reasonable to leverage the output
of Unordered-BART to obtain the plan for planned-BART.

###  5.3 Impact of Permutation on Decoding

In this section, we discuss how the input permutation can affect the quality
of decoding output. Particularly, we show that reasonable planning can create
less repetitive and more diverse output.

First, we find that the unordered models suffer from the repetition of content
in the output. For example, in 34.2% of test cases, there is at least one
concept that appears more than once in the output of the unordered BART.
However, this percentage decreased to 3.2% for the output of Planned-BART. It
is because the decoder of Planned-BART can assign attention weights
monotonically to the input, and reduce the repetition caused by re-attending
the previous concepts. In Appendix E, we provide a visualization of how the
input order can impact the attention weights during decoding.

Second, the order consistency between inputs and outputs in Planned-BART also
allows us to have more control over output skeletons by adjusting the input
concept order. Different orders can help the encoder to capture diverse
commonsense relations between concepts and create diverse outputs. While
unnatural diversity may hurt generation quality, we use SPICE as the measure
for quality and BLEU-based discrepancy Shu et al. (2019) for diversity, and
evaluate the performance of Unordered-BART Rank and Planned-BART Rank by
selecting the top 2 to 5 candidates as outputs. Figure 3 shows the quality-
diversity plot of two models. It indicates that with little degradation of
generation quality, Planned-BART can create more diverse output than
Unordered-BART. We show an example in Appendix F.

Figure 3:  The quality-diversity plot of Unordered-BART Rank and Planned-BART
Rank.

##  6 Conclusion

In this work, we revisit the PTM’s inherent ability of generative commonsense
reasoning. We use BART and T5 as underlying generators and propose their
planned variants to manipulate the order of the given concepts before
generation. Experiments on CommonGen dataset demonstrate that this simple pre-
ordering approach can outperform the previous pre-trained or knowledge-
enhanced models. Besides that, planned models can leverage the pre-ordered
concepts to create more succinct and diverse sentences. In conclusion, our
work suggests that PTM’s inherent ability for generative commonsense reasoning
is underestimated due to the unordered input, and the pre-ordering step can
help PTMs to improve the generation quality.

## References

  * Anderson et al. (2016) Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. 2016.  Spice: Semantic propositional image caption evaluation.  In _European conference on computer vision_ , pages 382–398. Springer.
  * Banerjee and Lavie (2005) Satanjeev Banerjee and Alon Lavie. 2005.  METEOR: An automatic metric for MT evaluation with improved correlation with human judgments.  In _Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization_ , pages 65–72, Ann Arbor, Michigan. Association for Computational Linguistics.
  * Bisazza and Federico (2016) Arianna Bisazza and Marcello Federico. 2016.  A Survey of Word Reordering in Statistical Machine Translation: Computational Models and Language Phenomena.  _Computational Linguistics_ , 42(2):163–205.
  * Clark et al. (2019) Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D. Manning. 2019.  What does BERT look at? an analysis of BERT’s attention.  In _Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 276–286, Florence, Italy. Association for Computational Linguistics.
  * Fan et al. (2020) Zhihao Fan, Yeyun Gong, Zhongyu Wei, Siyuan Wang, Yameng Huang, Jian Jiao, Xuanjing Huang, Nan Duan, and Ruofei Zhang. 2020.  An enhanced knowledge injection model for commonsense generation.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 2014–2025, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * Hessel and Schofield (2021) Jack Hessel and Alexandra Schofield. 2021.  How effective is BERT without word ordering? implications for language understanding and data privacy.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pages 204–211, Online. Association for Computational Linguistics.
  * Hoyle et al. (2021) Alexander Miserlis Hoyle, Ana Marasović, and Noah A. Smith. 2021.  Promoting graph awareness in linearized graph-to-text generation.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 944–956, Online. Association for Computational Linguistics.
  * Htut et al. (2019) Phu Mon Htut, Jason Phang, Shikha Bordia, and Samuel R Bowman. 2019.  Do attention heads in bert track syntactic dependencies? _arXiv preprint arXiv:1911.12246_.
  * Kale and Rastogi (2020) Mihir Kale and Abhinav Rastogi. 2020.  Text-to-text pre-training for data-to-text tasks.  In _Proceedings of the 13th International Conference on Natural Language Generation_ , pages 97–102, Dublin, Ireland. Association for Computational Linguistics.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7871–7880, Online. Association for Computational Linguistics.
  * Lin et al. (2020) Bill Yuchen Lin, Wangchunshu Zhou, Ming Shen, Pei Zhou, Chandra Bhagavatula, Yejin Choi, and Xiang Ren. 2020.  CommonGen: A constrained text generation challenge for generative commonsense reasoning.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 1823–1840, Online. Association for Computational Linguistics.
  * Lin (2004) Chin-Yew Lin. 2004.  ROUGE: A package for automatic evaluation of summaries.  In _Text Summarization Branches Out_ , pages 74–81, Barcelona, Spain. Association for Computational Linguistics.
  * Liu et al. (2021) Ye Liu, Yao Wan, Lifang He, Hao Peng, and Philip S Yu. 2021.  Kg-bart: Knowledge graph-augmented bart for generative commonsense reasoning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35.
  * Michel et al. (2019) Paul Michel, Omer Levy, and Graham Neubig. 2019.  Are sixteen heads really better than one? In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pages 14014–14024.
  * Moryossef et al. (2019) Amit Moryossef, Yoav Goldberg, and Ido Dagan. 2019.  step-by-step: Separating planning from realization in neural data-to-text generation.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 2267–2277.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21:1–67.
  * Ribeiro et al. (2021) Leonardo F. R. Ribeiro, Martin Schmitt, Hinrich Schütze, and Iryna Gurevych. 2021.  Investigating pretrained language models for graph-to-text generation.  In _Proceedings of the 3rd Workshop on Natural Language Processing for Conversational AI_ , pages 211–227, Online. Association for Computational Linguistics.
  * Shu et al. (2019) Raphael Shu, Hideki Nakayama, and Kyunghyun Cho. 2019.  Generating diverse translations with sentence codes.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 1823–1827, Florence, Italy. Association for Computational Linguistics.
  * Sinha et al. (2021) Koustuv Sinha, Robin Jia, Dieuwke Hupkes, Joelle Pineau, Adina Williams, and Douwe Kiela. 2021.  Masked language modeling and the distributional hypothesis: Order word matters pre-training for little.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 2888–2913, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 5998–6008.
  * Vedantam et al. (2015) Ramakrishna Vedantam, C. Lawrence Zitnick, and Devi Parikh. 2015.  Cider: Consensus-based image description evaluation.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2015, Boston, MA, USA, June 7-12, 2015_ , pages 4566–4575. IEEE Computer Society.
  * Vinyals et al. (2016) Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. 2016.  Order matters: Sequence to sequence for sets.  In _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_.
  * Wang et al. (2021) Han Wang, Yang Liu, Chenguang Zhu, Linjun Shou, Ming Gong, Yichong Xu, and Michael Zeng. 2021.  Retrieval enhanced model for commonsense generation.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 3056–3062, Online. Association for Computational Linguistics.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Zhang et al. (2020) Hongming Zhang, Xin Liu, Haojie Pan, Yangqiu Song, and Cane Wing-Ki Leung. 2020\.  ASER: A large-scale eventuality knowledge graph.  In _WWW ’20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020_ , pages 201–211. ACM / IW3C2.
  * Zhao et al. (2020) Chao Zhao, Marilyn Walker, and Snigdha Chaturvedi. 2020.  Bridging the structural gap between encoding and decoding for data-to-text generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2481–2491, Online. Association for Computational Linguistics.
  * Zhou et al. (2021) Wangchunshu Zhou, Dong-Ho Lee, Ravi Kiran Selvam, Seyeon Lee, and Xiang Ren. 2021\.  Pre-training text-to-text transformers for concept-centric common sense.  In _International Conference on Learning Representations_.

##  Appendix A Training Details

The BART and T5 models are implemented using the Transformers library Wolf et
al. (2020). We fine-tune each model on the training data of CommonGen with
Adam Kingma and Ba (2015). We set the learning rate as 2e-5 and adopt early
stopping based on the loss of development set. The batch size of training is
64.

##  Appendix B Human Evaluation Details

We randomly select 100 test instances that had 5 concepts as input, since they
are more challenging than those with fewer concepts. The three measures we
used are 1) Rationality: whether or not the sentence is in accordance with
commonsense; 2) Fluency: whether or not the sentence is fluent and has no
grammatical errors; and 3) Succinctness: whether or not the sentence contains
redundant words or repeated information.

The pairwise scores of those measures are calculated as follows. When
comparing a certain approach to Planned-BART Rank, we report the percentage of
instances that were judged to be better/worse/same than those of Planned-BART
Rank, yielding a score ranging from -1 (unanimously worse) to 1 (unanimously
better). For example, when evaluating the rationality scores, Unordered-BART
Vanilla performs better/worse/same than Planned-BART Rank for 27%/65%/8% of
the instances, yielding a pairwise score as 0.27-0.65=-0.38.

##  Appendix C Permutation Invariance

To figure out to what extent Unordered-BART is permutation-invariant, we
conduct the following analysis. For each test instance, we feed all different
input permutations to the Unordered-BART to obtain the corresponding output
sentences. We measure the invariance of the outputs by computing the
percentage of the most frequent output. If the concept order does not affect
the output, all different permutations will lead to identical outputs and the
percentage will be 100%. If half of the permutations obtain the same outputs,
the percentage will be 50%. We measure the input invariance at the following
two levels.

Sentence-level invariance For various permutations of a specific concept-set,
if the percentage of the most frequent sentence is greater than an invariance
threshold $\alpha$, we regard the model as input-invariant to that instance at
the sentence level.

Skeleton-level invariance The sentence-level invariance requires the output
sentences to be identical, which is strict and does not consider minor lexical
differences (e.g., the difference in function words or modifiers). Therefore,
we also report the skeleton-level invariance by measuring the percentage of
the most frequent skeleton (mode skeleton). It reflects whether or not the
model output will follow a certain order under different permutations, which
is a more forgivable invariance measure compared to its sentence-level
counterpart.

Figure 4: The histogram of CommonGen test set w.r.t. the percentage of most
frequent sentences (left) and skeletons (right), respectively. We also show
the cumulative distribution in blue lines. When $\alpha=0.9$, 37% and 61% of
the test instances are invariant at the sentence and skeleton-level,
respectively.

Figure 4 shows the distribution of CommonGen test set w.r.t. the percentage of
most frequent sentences (left) and skeletons (right). When setting
$\alpha=0.9$ , 37% of the test instances are invariant at the sentence level,
and 61% are invariant at the skeleton level. This indicates that for 61% of
the permutations, Unordered-BART can organize the concepts in one particular
order irrespective of the input order.

##  Appendix D Analysis of Local Attention

In addition to the analysis of global attention distribution, we also
investigate local attention patterns, i.e., the attention weights between
concept tokens. Previous works show that some attention heads can reflect
certain aspects of syntactic and semantic relations between words Clark et al.
(2019); Htut et al. (2019). We want to investigate if the heads can track
commonsense relations between concepts.

For this purpose, we first build gold relations between the concepts that
capture commonsense knowledge. One option is to utilize ConceptNet relations
between concepts Lin et al. (2020). However, these relations connect only two
concepts at a time disregarding the context information from other concepts.
Consider {throw, catch, dog, frisbee} as an example. “Dog” may be “caught” but
this relation is less plausible in this case because of the existence of
“frisbee”. When considering this context, humans provide references such as
“The dog catches the frisbee when the boy throws it.”

Another option is to use the dependency relations between words in the
reference sentences, which can capture the commonly occurring relations
between concepts while incorporating the context. For example, the relation
“catch$\xrightarrow{\text{dobj}}$frisbee” captures the commonsense that
frisbee is often caught, Similar ideas are also adopted in Zhang et al.
(2020). In particular, we extract the one-hop and two-hop dependency relations
of all concept pairs from the references, and only keep the relations that
appear in two or more references.

Relation | Head | UAS | $\bm{I}_{lh}$
---|---|---|---
v-dobj-n | 10-7 | 83.97 | 13
v-prep-adp-pobj-n | 10-7 | 82.61 | 13
n-nsubj-v | 11-12 | 87.62 | 3
n-prep-adp-pobj-n | 10-8 | 60.55 | 15
v-advcl-v | 4-11 | 85.37 | 4
v-conj-v | 10-1 | 83.07 | 2
n-nsubj-v-dobj-n | 6-16 | 62.34 | 40
v-xcomp-v | 8-15 | 91.32 | 19
n-conj-n | 10-0 | 88.75 | 56
n-comp-n | 1-8 | 83.31 | 24
Table 4:  The functional heads for each relation, as well as the corresponding
UAS and importance rank.

For attention probing, we use attention weights between input tokens to
reflect the strength of their associations. Given two concepts $c_{i}$ and
$c_{j,j>i}$, we regard them as strongly associated under the attention head
$(l,h)$ if the attention weight $\alpha^{l,k}_{ij}$ is the highest among the
scores from all the other concepts $c_{k\backslash\\{i,j\\}}$ to $c_{j}$.

Figure 5: UAS of commonsense relations from three BART models via attention probing. The performance of fine-tuned Unordered-BART > pre-trained Frozen-BART > randomly-initialized BART among all of the relations.  Model |  Output |  Skeleton
---|---|---
Unordered-BART |  A crowd of people watch and dance to the music. |  crowd watch dance music
Planned-BART |  A crowd of people are dancing to music while others watch. |  crowd dance music watch
|  A man plays music and watches the crowd dance. |  music watch crowd dance
|  A group of people dance to music as a crowd watches. |  dance music crowd watch
|  A man watches a crowd of people dancing to music. |  watch crowd dance music
Human |  The crowd likes to watch her dance to the music. |  crowd watch dance music
|  The crowd watched the dance, and listed to the music. |  crowd watch dance music
|  I watched as the crowd dance to the music. |  watch crowd dance music
|  A person dancing to the music as a crowd of people watch. |  dance music crowd watch
Table 5:  Sample texts generated by Unordered-BART, Planned-BART, and humans
for the concept set {dance, music, crowd, watch}. The diversity of Planned-
BART is more close to human generation. Figure 6: The cross-attention matrix
of two permutations of the same concept-set produced by Unordered-BART. It’s
difficult for Unordered-BART to learn the optimal order of attention.

We choose the 10 most common dependency relations from the test set and report
the Unlabeled Attachment Score (UAS) of attention probing in Figure 5. We also
list the UAS of a randomly initialized BART and a pre-trained BART without
fine-tuning for comparison.

Results in Figure 5 show that for some frequent and simple relations such as
“v-dobj-n” and “n-nsubj-v”, there is at least one attention head that tends to
track them regardless of the differences in the permutation orders. For
example, attention head “Layer-10 Head-7” tracks the “v-dobj-n” relation with
a UAS of 83.9%. The comparison among the three models shows that the pre-
trained BART already exceeds the randomly initialized model in tracking
commonsense relations between words, and fine-tuning further strengthens those
relations.

To demonstrate that these functional heads are important for generation, we
use the expected sensitivity Michel et al. (2019) of the model to each head to
evaluate the head importance as

$I_{lh}=\mathbb{E}_{x\sim
X}\left|\frac{\partial\mathcal{L}(x)}{\partial\xi_{lh}}\right|$ (2)

where $\mathcal{L}(x)$ is the loss of generation and $\xi_{lh}$ is the mask
variable for head $l-h$ with values in $\\{0,1\\}$. The general idea is that
the value change of important heads can have a larger impact on the model
loss. Results are shown in Table 4. For most relations, the corresponding
functional heads also have a high rank of importance. This consistency
indicates that the model heavily relies on these heads when generating texts,
and further demonstrates that the finetuned BART can capture the commonsense
between concepts for generation.

##  Appendix E Impact on Repetition

The repetition of the unordered BART is caused by the order-agnostic property
of its input. Since the input concepts are unordered, the decoder cannot pay
attention to the input in a monotonic way (from left to right) during
decoding, which may mislead the decoder to attend to the concepts that have
been previously generated. For example, on the left of Figure 6, the decoder
attends to “tea” and “glass” twice during decoding, which achieves the local
coherence but causes the global repetition issue and unnatural text. However,
when modifying the input in another order, as shown in the right of Figure 6,
the repetitive and unnatural expressions disappear. It indicates that the BART
decoder has difficulty ordering the input globally, and providing a well-
ordered plan as input can alleviate this issue. On the contrary, in Planned-
BART, the decoder can assign attention weights monotonically to the input, and
therefore reduce the repetition caused by re-attending the previous concepts.

##  Appendix F Impact on Diversity

Table 5 provides an example with the outputs created by both models and
humans. Unordered-BART can create only one output due to the permutation
invariance. Also, the object of watch is missing in its output. On the other
hand, similar to the human-written output, the output of Planned-BART is more
natural and diverse.