contains all the needed roots of unity) the roots of the general cubic and
quartic may be given by a tight natural formula, Ruffini showed that the roots
of the general quintic have no loose natural formulas and Abel showed that
they may not even be solved by loose radical extractions.

It appears that we are now faced with the additional problems of finding out
which equations have roots with tight and/or loose and/or natural $\ldots$-etc
formulas. However, we shall soon see that things are not that complicated. To
begin with we show that the roots of a cyclic equation of prime degree $p$,
after the adjunction of a primitive $p^{th}$-root of unity, may be given a
tight natural formula. In fact, to do so we need only add a Galois twist to
Lagrange’s identity 5.32.

Proposition 7.2

Let $p$ be a prime and let $B(t)=\prod_{i=0}^{p-1}(t-\beta_{i})\in{\cal F}[t]$
be cyclic with Galois group $G=G_{B}({\cal
F})=\\{id,\gamma,\gamma^{2},\ldots,\gamma^{p-1}\\}$ where

$\gamma\beta_{i}=\beta_{i+1}\enskip.$ $None$

Let $u$ be a primitive $p^{th}$-root of unity. Then we have

$\beta_{s}={1\over p}\sum_{i=0}^{p-1}\hskip 2.5ptu^{-is}\hskip
2.5ptc_{i}\hskip 2.5pt\theta^{i}\hskip 36.135pt(\enskip for\enskip\hskip
2.5pts=0,..,p-1)$ $None$

where each $c_{i}\in{\cal F}[u]$ and $\theta$ is a root of a binomial equation

$t^{p}-\Xi=0\hskip 36.135pt(\enskip\Xi\in{\cal F}[u]\enskip)$ $None$

which is irreducible in ${\cal F}[t]$. Moreover, if $u$ is properly chosen, we
have also the expansion

$\theta=\beta_{o}+u\beta_{1}+u^{2}\beta_{2}+\cdots+u^{p-1}\beta_{p-1}\enskip.$
$None$

Proof

Set

$\theta_{s}=\sum_{i=0}^{p-1}\hskip 2.5ptu^{is}\hskip 2.5pt\beta_{i}\hskip
36.135pt(\enskip for\enskip\hskip 2.5pts=0,..,p-1)$ $None$

Note that since the matrices $\|u^{rs}\|_{r,s=0,..p-1}$ and ${1\over
p}\|u^{-rs}\|_{r,s=0,..p-1}$ are inverses of each other, the relation in 7.21
may be inverted to

$\beta_{s}\enskip=\enskip{1\over p}\sum_{i=0}^{p-1}\hskip 2.5ptu^{-is}\hskip
2.5pt\theta_{i}\hskip 36.135pt(\enskip for\enskip\hskip 2.5pts=0,..,p-1)$
$None$

Note next that we may write

$\eqalign{\theta_{s}^{p}&\enskip=\enskip\sum_{i_{1},i_{2},\ldots,i_{p}}\hskip
2.5ptu^{i_{1}+i_{2}+\cdots+i_{p}}\hskip
2.5pt\beta_{i_{1}}\beta_{i_{2}}\cdots\beta_{i_{p}}\cr&\enskip=\enskip\sum_{r=0}^{p-1}\hskip
2.5ptu^{r}\hskip 2.5pt\sum_{i_{1}+i_{2}+\cdots+i_{p}\cong r\enskip mod\hskip
1.75ptp}\beta_{i_{1}}\beta_{i_{2}}\cdots\beta_{i_{p}}\cr}\enskip.$ $None$

Now it is easy to see that the polynomial

$P_{r}(\beta_{0},\beta_{1},\ldots,\beta_{p-1})\enskip=\enskip\sum_{i_{1}+i_{2}+\cdots+i_{p}\cong
r\enskip mod\hskip 1.75ptp}\beta_{i_{1}}\beta_{i_{2}}\cdots\beta_{i_{p}}$

is invariant under the cyclic shift $\beta_{i}\rightarrow\beta_{i+1}$ thus its
value must necessarily lie in ${\cal F}$. Formula 7.23 then yields that

$\theta_{s}^{p}=\Xi_{s}\in{\cal F}[u]$ $None$

Similarly, we can write

$\theta_{1}^{p-s}\theta_{s}\enskip=\enskip\sum_{r=0}^{p-1}\hskip
2.5ptu^{r}\hskip 2.5pt\sum_{i_{1}+i_{2}+\cdots+i_{p-s}+sj\cong r\enskip
mod\hskip 1.75ptp}\beta_{i_{1}}\beta_{i_{2}}\cdots\beta_{i_{p-s}}\beta_{j}$

and deduce from it that

$\theta_{1}^{p-s}\theta_{s}=d_{s}\in{\cal F}[u]\enskip.$ $None$

Now observe that we cannot have $\theta_{1}=\theta_{2}=\cdots=\theta_{p-1}=0$
for otherwise formula 7.22 would yield
$\beta_{1}=\beta_{2}=\cdots=\beta_{p-1}$ which contradicts the irreducibility
of $B(t)$. But this means that we can assume $\theta_{1}\neq 0$. In fact, the
case when $\theta_{s}$ is the first one that is $\neq 0$ can be reduced to the
case $\theta_{1}\neq 0$ by replacing $u$ with $v=u^{s}$. This given, we can
invert $\Xi_{1}$ in ${\cal F}[u]$ and, combining 7.24 with 7.25, derive that

$\theta_{s}=c_{s}\hskip 2.5pt\theta_{1}^{s}$ $None$

with

$c_{s}\enskip=\enskip d_{s}/\Xi_{1}\in{\cal F}[u]\enskip.$

Using 7.26 in 7.22 gives 7.18 with $\theta=\theta_{1}$. Since $\theta_{1}$
satisfies the equation 7.19 with $\Xi=\Xi_{1}$ and 7.20 is simply the
definition 7.21 of $\theta_{1}$, to complete the proof we need only show that
the binomial $t^{p}-\Xi_{1}$ is irreducible in ${\cal F}[u]$. Now suppose it
is reducible. Then Proposition 7.1 gives that it factors in the form

$t^{p}-\Xi_{1}\enskip=\enskip(t-b)(t-ub)\cdots(t-u^{p-1})$

with $b\in{\cal F}[u]$. Thus we must have $\theta_{1}=u^{h}b\in{\cal F}[u]$
and in particular 7.18 gives that $\beta_{1}=\theta(u)$ with
$\theta(t)\in{\cal F}[t]$. Now let $H$ be the Galois group of the cyclotomic
polynomial $\Phi_{p}=1+t+\cdots+t^{p-1}$ in ${\cal F}[t]$ and let
$H_{\beta_{1}}$ denote the Galois stabilizer of $\theta(u)$ in $H$. From the
left coset decomposition

$H=\tau_{1}H_{\beta_{1}}+\tau_{2}H_{\beta_{1}}+\cdots+\tau_{k}H_{\beta_{1}}\hskip
36.135pt(\enskip\tau_{1}=id\enskip)$

construct the polynomial

$B_{1}(t)\enskip=\enskip\prod_{i=1}^{k}(t-\tau_{i}\beta_{1})\in{\cal
F}[t]\enskip.$

Note that $B_{1}(t)$ must have $B(t)$ as a factor since it shares the root
$\beta_{1}$ with $B(t)$ and $B(t)$ is irreducible in ${\cal F}[t]$. Now all
this leads to an impossibility since $B_{1}(t)$ is of degree $k\leq p-1$. In
fact, $k$ must be a divisor of the order of $H$ and $H$ is (by Corollary 7.1)
a subgroup of the cyclic group of order $p-1$.

Thirty years before Galois and ninety years before the concept of field was
introduced and developped by Dedekind [], Gauss, essentially showed [] that
all roots of unity can be obtained by a sequence of normal field extensions,
in fact by tight root extractions in our terminology. His proof his
algorithmic and is therefore very much in style with present preferences for
explicit constructions. This given, we would be amiss not presenting it here.
Gauss’ argument relies on a family of remarkably beautiful identities. They
may be stated as follows

Lemma 7.1 (Gauss)

Let $p$ be a prime, let $w=e^{2\pi i/p}$ and $e$ be a primitive exponent
modulo $p$. For a given factorization

$p-1\enskip=\enskip a\hskip 2.5ptb$ $None$

set

$\Pi_{a}(t)\enskip=\enskip
t+t^{e^{a}}+t^{e^{2a}}+\cdots+t^{e^{(b-1)a}}\enskip=\enskip\sum_{i=0}^{b-1}\hskip
2.5ptt^{e^{ia}}\enskip.$ $None$

Then for any pair $0\leq r,s\leq a-1$ we have

$\Pi_{a}(w^{e^{r}})\Pi_{a}(w^{e^{s}})\enskip=\enskip\sum_{i=0}^{b-1}\hskip
2.5pt\Pi_{a}(w^{e^{r}+e^{s+ia}})\enskip.$ $None$

Proof

Note first that, for the purpose of establishing 7.28, the polynomial
$\Pi_{a}(t)$ is essentially invariant under the substitution $t\rightarrow
t^{e^{a}}$. More precisely, since $e^{p-1}\cong 1$ modulo $p$ we have

$\Pi_{a}(t^{e^{a}})\enskip=\enskip
t^{e^{a}}+t^{e^{2a}}+\cdots+t^{e^{ba}}\enskip=\enskip\Pi_{a}(t)\hskip
36.135pt(\hskip 2.5ptmod\enskip t^{p}-1\hskip 2.5pt)$ $None$

This given we have

$\eqalign{\Pi_{a}(w^{e^{r}})\Pi_{a}(w^{e^{s}})&=\sum_{j=0}^{b-1}\hskip
2.5pt\bigl{(}w^{e^{r}}\bigr{)}^{e^{ja}}\hskip
2.5pt\Pi_{a}(w^{e^{s}})=\sum_{j=0}^{b-1}\hskip
2.5pt\bigl{(}w^{e^{r}}\bigr{)}^{e^{ja}}\hskip
2.5pt\Pi_{a}\bigl{(}(w^{e^{s}})^{e^{ja}}\bigr{)}\cr&=\sum_{j=0}^{b-1}\sum_{i=0}^{b-1}\hskip
2.5pt\bigl{(}w^{e^{r}}\bigr{)}^{e^{ja}}\hskip
2.5pt\bigl{(}(w^{e^{s}})^{e^{ja}}\bigr{)}^{e^{ia}}=\sum_{i=0}^{b-1}\sum_{j=0}^{b-1}\hskip
2.5pt\bigl{(}w^{e^{r}}\bigr{)}^{e^{ja}}\hskip
2.5pt\bigl{(}(w^{e^{s+ia}}\bigr{)}^{e^{ja}}\cr&=\sum_{i=0}^{b-1}\hskip
2.5pt\Pi_{a}(w^{e^{r}+e^{s+ia}})\enskip.\cr}$

Q.E.D.

Gauss’ construction of the roots of unity is best understood if illustrated in
special cases. Nevertheless it will be helpful if we start with some general
remarks. Suppose that we want all the primitive $p^{th}$ roots of unity for a
certain prime $p$. Since they are the roots of the cyclotomic polynomial

$\Phi_{p}\enskip=\enskip 1+t+t^{2}+\cdots+t^{p-1}\enskip,$ $None$

our starting point should be the cyclicity of this polynomial with respect to
the rationals. Following the proof of Corollary 7.2, we let $e$ be a primitive
exponent modulo $p$, let $\alpha$ be one of the roots of 7.31 and label all
the roots by setting

$\alpha_{i}\enskip=\enskip\alpha^{e^{i}}\hskip
36.135pt\enskip\enskip\enskip\enskip(\enskip for\enskip\enskip
i=0,1,\ldots,p-2\enskip)$ $None$

We have seen that with this labeling the Galois group $G=G_{\Phi_{p}}({\cal
Q})$ is the cyclic group of order $p-1$ generated by the cyclic permutation

$\gamma\hskip 2.5pt\alpha_{i}\enskip=\enskip\alpha_{i+1}\enskip.$ $None$

Now for a given factorization $p-1=ab$ we let $G_{a}$ denote the cyclic
subgroup of $G$ generated by the cycle $\gamma^{a}$. That is

$G_{a}=1+\gamma^{a}+\gamma^{2a}+\cdots+\gamma^{(b-1)a}\enskip.$ $None$

We then have the left coset decomposition

$G=G_{a}+\gamma G_{a}+\gamma^{2}G_{a}+\cdots+\gamma^{a-1}G_{a}\enskip.$ $None$

Now we know from Theorem 6.1 that we can find a polynomial
$\Psi_{a}(x_{1},x_{2},\ldots,x_{n})\in{\cal Q}[x_{1},x_{2},\ldots,x_{n}]$ such
that ${\tilde{G}}_{\Psi}=G_{a}$. Actually in this case we have a very simple
choice for ${\tilde{\Psi}}_{a}$, namely the linear expression

${\tilde{\Psi}}_{a}=\beta_{o}=G_{a}\alpha_{o}=\alpha_{o}+\alpha_{a}+\alpha_{2a}+\cdots+\alpha_{(b-1)a}$
$None$

Since the stability of ${\tilde{\Psi}}_{a}$ under $G_{a}$ is clear, to assure
that ${\tilde{G}}_{\Psi_{a}}=G_{a}$ we need only verify that no other element
of $G$ leaves ${\tilde{\Psi}}_{a}$ unchanged. But, because of 7.35, this will
be so if and only if the conjugates

$\beta_{i}=\gamma^{i}\hskip
2.5pt\beta_{o}\enskip=\enskip\alpha_{i}+\alpha_{i+a}+\alpha_{i+2a}+\cdots+\alpha_{i+(b-1)a}\hskip
36.135pt(\enskip for\enskip\enskip i=1,2,\ldots,a-1\enskip)$ $None$

are all distinct. However, since

$\beta_{o}=\sum_{r=0}^{b-1}\alpha^{e^{ra}}$ $None$

the equality

$\beta_{i}\enskip=\enskip\beta_{j}$

holds true if and only if $\alpha$ is a root of the polynomial

$P_{ij}(t)\enskip=\enskip\sum_{r=0}^{b-1}t^{e^{i+ra}}\enskip-\enskip\sum_{r=0}^{b-1}t^{e^{j+ra}}\enskip.$

Adding $\pm\Phi_{p}(t)$ to $P_{ij}(t)$, if necessary to cancel the the term in
$t^{p-1}$, we would then obtain a polynomial in ${\cal Q}[t]$ of degree less
than $p-1$ which shares a root with $\Phi_{p}$ contradicting the
irreducibility of $\Phi_{p}$. Thus ${\tilde{G}}_{\beta_{o}}=G_{a}$ and we can
use Theorem 6.5 to conclude that

(i)

The polynomial

$B_{a}(t)\enskip=\enskip\prod_{i=0}^{a-1}(t-\beta_{i})\enskip\in\enskip{\cal
Q}[t]$

is irreducible in ${\cal Q}[t]$

(ii)

By adjoining $\beta_{o}$ to ${\cal Q}$ the Galois group of $\Phi_{p}$ reduces
to

$G_{a}=1+\gamma^{a}+\gamma^{2a}+\cdots+\gamma^{(b-1)a}\enskip.$

(iii)

The Galois group of $B_{a}(t)$ is the cyclic group

$G/G_{a}\enskip=\enskip 1+\gamma+\gamma^{2}+\cdots+\gamma^{a-1}\enskip.$
$None$

Here $\gamma$ can keep the same meaning as before since we may let it act on
the $\beta_{i}$’s as they are given by the defining identities 7.37.

This establishes that $B_{a}(t)$ itself is cyclic and therefore, if $a$ is a
prime, we can construct its roots according to formula 7.18 of Proposition
7.2. All this may be very nice but yet not very explicit! The beauty of Gauss
identities is that they enable us to compute all that we need with a minimum
of effort. Indeed, (using the notation of Lemma 7.1), we see that we have

$\beta_{i}\enskip=\enskip\Pi_{a}(\alpha^{e^{i}})\enskip,$ $None$

thus we may use 7.29 to construct a multiplication table for the roots of
$B_{a}(t)$ and obtain $B_{a}(t)$ itself as well as the ingredients entering in
formula 7.18 quite explicitely.

This is but the first step in the construction of the roots of $\Phi_{p}$. It
reduces us to work with $\Phi_{p}$ in the extended field ${\cal Q}[\beta_{o}]$
which now (by the cyclicity of $B_{a}(t)$) contains
$\beta_{1},\beta_{2},\ldots,\beta_{a-1}$ as well. The next step is to
factorize in turn the new Galois group of $\Phi_{p}$, which as we have seen
reduces to

$G_{a}=1+\gamma^{a}+\gamma^{2a}+\cdots+\gamma^{(b-1)a}\enskip,$

and then proceed to split each of the $\beta_{i}$ into sums $\lambda_{j}$ of
powers of $\alpha$ which are invariant under a normal subgroup of $G_{a}$.
Then, after the adjonction of the $\lambda_{j}$ to ${\cal Q}[\beta_{o}]$, we
further reduce the Galois group of $\Phi_{p}$ to this normal subgroup. We
proceed in this manner until the $\beta_{i}$’s are split all the way down to
their individual summands, which are of course the roots of $\Phi_{p}$. To
describe the process explicitely at this point and in full generality would
require more notation that would only blur the beauty of the argument.
Imitating established tradition, we will avoid this difficulty by just saying
that after we split the number $p-1$ into its prime factors.

$p-1=p_{1}p_{2}\cdots p_{k_{o}}\enskip\enskip\enskip{\rm
with}\enskip\enskip\enskip p_{1}\geq p_{2}\geq\cdots\geq p_{k_{o}}\enskip,$
$None$

we proceed to construct the composition series of
$G=1+\gamma+\cdots+\gamma^{p-1}$

$G\triangleright_{p_{1}}G_{1}\triangleright_{p_{2}}G_{2}\triangleright_{p_{3}}\cdots\triangleright_{p_{k_{o}}}G_{k_{o}}=\\{id\\}\enskip.$

Then by a sequence of adjunctions $\xi_{k}\in{\cal
Q}[\alpha_{o},\alpha_{1},\ldots,\alpha_{p-1}]$, with
${\tilde{G}}_{\xi_{k}}=G_{k}$ we arrive at a final tight and natural
expression for the roots of $\Phi_{p}$. We must also point out that this
argument can only be completed by an induction process. Since at each step, as
we have seen we need to adjoin primitive roots of unity of lower order which
inductively must be assumed to have already been given tight formulas. Before
we indulge into this type of mental gymnastics it will be good to work out a
few revealing examples.

$\underline{p=13}$:

Here, $p-1=12$ and we may take $e=2$ as a primitive exponent $mod\enskip 13$.
This given, from Corollary 7.2 we get that the Galois group of the equation

$\Phi_{13}(t)=1+t+t^{2}+\cdots+t^{12}$

with respect to the field ${\cal Q}$ of rational numbers, is the cyclic group
generated by the operation $t\rightarrow t^{2}$. More precisely, if $\alpha$
is our desired $13^{th}$ root of unity and the roots of $\Phi_{13}(t)$ are
labeled by setting

$\alpha_{o}=\alpha\hskip 2.5pt,\hskip 2.5pt\alpha_{1}=\alpha^{2}\hskip
2.5pt,\hskip 2.5pt\alpha_{2}=\alpha^{2^{2}}\hskip 2.5pt,\hskip
2.5pt\ldots,\alpha_{11}=\alpha^{2^{11}}\enskip,$

then $G=G_{\Phi_{13}}({\cal Q})$ is generated by the cyclic permutation

$\gamma\alpha_{i}\enskip=\enskip\alpha_{i}^{2}\enskip=\enskip\alpha_{i+1}\enskip.$

This gives

$\matrix{\alpha_{o}&\enskip=\enskip&\alpha^{2^{0}}&=&w\cr\alpha_{1}&\enskip=\enskip&\alpha^{2^{1}}&=&\alpha^{2}\cr\alpha_{2}&\enskip=\enskip&\alpha^{2^{2}}&=&\alpha^{4}\cr\alpha_{3}&\enskip=\enskip&\alpha^{2^{3}}&=&\alpha^{8}\cr\alpha_{4}&\enskip=\enskip&\alpha^{2^{4}}&=&\alpha^{3}\cr\alpha_{5}&\enskip=\enskip&\alpha^{2^{5}}&=&\alpha^{6}\cr\alpha_{6}&\enskip=\enskip&\alpha^{2^{6}}&=&\alpha^{12}\cr\alpha_{7}&\enskip=\enskip&\alpha^{2^{7}}&=&\alpha^{11}\cr\alpha_{8}&\enskip=\enskip&\alpha^{2^{8}}&=&\alpha^{9}\cr\alpha_{9}&\enskip=\enskip&\alpha^{2^{9}}&=&\alpha^{5}\cr\alpha_{10}&\enskip=\enskip&\alpha^{2^{1}0}&=&\alpha^{10}\cr\alpha_{11}&\enskip=\enskip&\alpha^{2^{1}1}&=&\alpha^{7}\cr}$
$None$

We start by factoring the Galois group of $\Phi_{13}$

$1+\gamma+\cdots+\gamma^{11}\enskip=\enskip
1+\gamma^{3}+\gamma^{6}+\gamma^{9}+\gamma(1+\gamma^{3}+\gamma^{6}+\gamma^{9})+\gamma^{2}(1+\gamma^{3}+\gamma^{6}+\gamma^{9})\enskip.$
$None$

Then we seek for an element $\beta_{o}\in{\cal
Q}[\alpha_{o}\alpha_{1},\ldots,\alpha_{11}]$ whose Galois stabilizer is

${\tilde{G}}_{\beta_{o}}\enskip=\enskip 1+\gamma^{3}+\gamma^{6}+\gamma^{9}$

We may take

$\beta_{o}\enskip=\enskip\alpha_{o}+\alpha_{3}+\alpha_{6}+\alpha_{9}=\alpha+\alpha^{8}+\alpha^{12}+\alpha^{5}\enskip=\enskip\Pi_{3}(\alpha)\enskip.$
$None$

Its conjugates are

$\beta_{1}\enskip=\enskip\alpha_{1}+\alpha_{4}+\alpha_{7}+\alpha_{10}=\alpha^{2}+\alpha^{3}+\alpha^{11}+\alpha^{10}\enskip=\enskip\Pi_{3}(\alpha_{1})\enskip.$
$None$

and

$\beta_{2}\enskip=\enskip\alpha_{2}+\alpha_{5}+\alpha_{8}+\alpha_{11}=\alpha^{4}+\alpha^{6}+\alpha^{9}+\alpha^{7}\enskip=\enskip\Pi_{3}(\alpha_{2})\enskip.$
$None$

Now, using the Gauss relations with parameters $p=13$, $a=3$, $b=4$ and $e=2$
we get the multiplication table

$\matrix{\beta_{o}\beta_{o}=4+\beta_{1}+2\beta_{2}&\beta_{o}\beta_{1}=\beta_{o}+2\beta_{1}+\beta_{2}&\beta_{o}\beta_{2}=2\beta_{o}+\beta_{1}+\beta_{2}\cr\beta_{1}\beta_{o}=\beta_{o}+2\beta_{1}+\beta_{2}&\beta_{1}\beta_{1}=4+2\beta_{o}+\beta_{2}&\beta_{1}\beta_{2}=\beta_{o}+\beta_{1}+2\beta_{2}\cr\beta_{2}\beta_{0}=2\beta_{o}+\beta_{1}+\beta_{2}&\beta_{2}\beta_{1}=\beta_{o}+\beta_{1}+2\beta_{2}&\beta_{2}\beta_{2}=4+\beta_{o}+2\beta_{1}\cr}$
$None$

From which we derive that

$(t-\beta_{o})(t-\beta_{1})(t-\beta_{2})\enskip=\enskip
1-4t+t^{2}+t^{3}\enskip.$

Theorem 6.5 then gives that this equation is cyclic with Galois group

$1+\gamma+\gamma^{2}$

So if we let $u$ denote a primitive cube root of unity, that is

$u={-1+{\root 2 \of{-3}}\over 2}$

and set

$\eqalign{\theta_{o}&\enskip=\enskip\beta_{o}+\beta_{1}+\beta_{2}\enskip,\cr\theta_{1}&\enskip=\enskip\beta_{o}+u\beta_{1}+u^{2}\beta_{2}\enskip,\cr\theta_{2}&\enskip=\enskip\beta_{o}+u^{2}\beta_{1}+u^{4}\beta_{2}\enskip,\cr}$

then formula 7.22 gives

$\beta_{o}=(\theta_{o}+\theta_{1}+\theta_{2})/3\enskip.$

Note that we must have $-\theta_{o}=1$ since it must equal the coefficient of
$t^{11}$ in $\Phi_{13}$. To get $\beta_{o}$ into the form given in 7.18 we
must compute the coefficient

$c_{2}\enskip=\enskip\theta_{2}/\theta_{1}^{2}\enskip.$

Now we can write

$c_{2}\enskip=\enskip{\theta_{2}\theta_{1}\over\theta_{1}^{3}}\enskip.$

and the table in 7.46 gives

$\theta_{2}\theta_{1}\enskip=\enskip
13\enskip\enskip\enskip,\enskip\enskip\enskip\theta_{1}^{3}\enskip=\enskip-13(4+3u)\enskip=\enskip{13^{2}\over-1+3u}$

Thus

$c_{2}\enskip=\enskip(-1+3u)/13$

and

$\beta_{o}\enskip=\enskip{-1+\theta_{1}+(-1+3u)\theta_{1}^{2}/13\over
3}\enskip.$ $None$

where we may write

$\theta_{1}\enskip=\enskip{\root 3 \of{-13(4+3u)}}\enskip,$

which is assured by Proposition 7.2 to be a tight radical in ${\cal Q}[u]$.

By Theorem 6.5 the Galois group of $\Phi_{13}$ in ${\cal Q}[\beta_{o}]$ is

$1+\gamma^{3}+\gamma^{6}+\gamma^{9}$

So our next step is to construct a polynomial in
$\alpha_{o},\alpha_{1},\ldots,\alpha_{11}$ whose stabilizer in $1+\gamma^{6}$.
We may take

$\lambda_{o}\enskip=\enskip\alpha_{o}+\alpha_{6}\enskip=\enskip\alpha+\alpha^{2^{6}}\enskip=\enskip\alpha+\alpha^{-1}$

Now we need to use the Gauss relations with $a=6$ $e=2$. In fact, if we set

$\lambda_{r}\enskip=\enskip\Pi_{6}(\alpha^{2^{r}})\hskip 36.135pt(\enskip
r=0,1,\ldots,5\enskip)$

then

$\lambda_{o}\enskip=\enskip\alpha_{o}+\alpha_{6}\enskip\enskip\enskip{\rm
and}\enskip\enskip\enskip\lambda_{3}\enskip=\enskip\alpha_{3}+\alpha_{9}$

thus

$\beta_{o}\enskip=\enskip\lambda_{o}+\lambda_{3}\enskip.$

From Gauss formula (or even by direct computation in this case) we get that

$\lambda_{o}\times\lambda_{3}\enskip=\enskip\lambda_{2}+\lambda_{5}\enskip=\enskip\beta_{2}$

and $\lambda_{o}$ can be obtained by solving the equation

$(t-\lambda_{o})(t-\lambda_{3})\enskip=\enskip
t^{2}-\beta_{o}t+\beta_{2}\enskip.$

This gives that

$\alpha+\alpha^{-1}=\lambda_{o}\enskip=\enskip{-\beta_{o}+{\root 2
\of{\beta_{o}^{2}-4\beta_{2}}}\over 2}$ $None$

If we prefer to write $\lambda_{o}$ only in terms of $\beta_{o}$ the we resort
again to the table in 7.46 which gives

$\beta_{1}=-\beta_{o}^{2}-2\beta_{o}+2\enskip\enskip\enskip{\rm
and}\enskip\enskip\enskip\beta_{2}=\beta_{o}^{2}+\beta_{o}-3$

this agrees with the fact (implied by the cyclicity of the equation satisfied
by $\beta_{o}$) that both $\beta_{1}$ and $\beta_{2}$ must be in ${\cal
Q}[\beta_{o}]$. We should note again that, as assured by Proposition 7.2, the
square root in 7.48 must necessarily be tight in ${\cal Q}[\beta_{o}]$.

The last step is to reduce the Galois group of $\Phi_{13}$ to the identity by
adjoining $\alpha$. From 7.48 we get that $\alpha$ is obtained by solving the
equation

$(t-\alpha)(t-\alpha^{-1})\enskip=\enskip t^{2}-\lambda_{o}t+1=0$

which gives that

$\alpha\enskip=\enskip{\lambda_{o}+{\root 2 \of{\lambda_{o}^{2}-4}}\over 2}$
$None$

In summary, by combining 7.47, 7.48 and 7.49, we can construct a tight natural
formula for all the primitive $13^{th}$ roots of unity. In fact the successive
adjunctions may be taken to be

$\beta_{o}=\alpha_{o}+\alpha_{3}+\alpha_{6}+\alpha_{9}\enskip\enskip,\enskip\enskip\lambda_{o}\enskip=\enskip\alpha_{o}+\alpha_{6}\enskip\enskip,\enskip\enskip\alpha_{o}=\alpha$

The corresponding reductions of the Galois group of $\Phi_{13}$ being

$1+\gamma+\cdots+\gamma^{11}\enskip\triangleright_{3}\enskip
1+\gamma^{3}+\gamma^{6}+\gamma^{9}\enskip\triangleright_{2}\enskip
1+\gamma^{6}\enskip\triangleright_{2}\enskip\\{id\\}$

Remark 7.1

The fact that in the previous calculation we found that
$\theta_{1}\theta_{2}=13\in{\cal Q}$ is not an accident. In general, for any
cyclic equation, formulas 7.21 give that

$f\enskip=\enskip\theta_{1}\theta_{2}\cdots\theta_{p-1}\enskip=\enskip\sum_{r=0}^{p-1}u^{r}\hskip
2.5pt\sum_{i_{1}+2i_{2}+\cdots+(p-1)i_{p-1}\cong r\hskip 1.75ptmod\hskip
1.75ptp}\beta_{i_{1}}\beta_{i_{2}}\cdots\beta_{i_{p-1}}\enskip.$

Since the coefficient of $u^{r}$ is clearly invariant under the cyclic shift
$\beta_{i}\rightarrow\beta_{i+1}$, we should not be surprised if $f$ comes out
to be in ${\cal Q}[u]$. However, it is easy to see that $f$ also remains
unchanged by the replacement of $u$ in $f$ by any other primitive
$p^{th}$-root of unity. This forces $f\in{\cal Q}$ as well.

$\underline{p=11}$:

Here we may take $e=2$ again and set $\alpha_{i}=\alpha^{2^{i}}$ for
$i=0,1,\ldots,9$ with $\alpha$ our desired primitive $11^{th}$-root of unity.
Letting $\gamma\alpha_{i}=\alpha_{i+1}$ again Corollary 7.2 gives

$G_{\Phi_{11}}({\cal Q})\enskip=\enskip 1+\gamma+\gamma^{2}+\cdots+\gamma^{9}$

Since $p-1=10=5\times 2$ we can at once reduce this Galois group to the
subgroup

$1+\gamma^{5}$

by the adjonction of

$\beta_{o}\enskip=\enskip\alpha_{o}+\alpha_{5}\enskip.$ $None$

To use Gauss machinery with $p=11$ $e=2$ and $a=5$ we set

$\beta_{r}\enskip=\enskip\Pi_{5}(\alpha_{r})\enskip.\hskip 36.135pt\hskip
36.135pt(\enskip r=0,1,\ldots,4\enskip)$

In this case a repetitive application of 7.29 gives

$(t-\beta_{o})(t-\beta_{1})\cdots(t-\beta_{4})\enskip=\enskip
1+3t-3t^{2}-4t^{3}+t^{4}+t^{5}\enskip,$

which by Theorem 6.4 must be cyclic with Galois group

$1+\gamma+\gamma^{2}+\gamma^{3}+\gamma^{4}$

We can then solve it with the formulas of Proposition 7.2. So we pick a
primitive $5^{th}$-root of unity $u$ and set

$\theta_{r}\enskip=\enskip\sum_{i=0}^{4}\hskip 2.5ptu^{ri}\hskip
2.5pt\beta_{i}\hskip 36.135pt(\enskip for\enskip
r=0,1,\ldots,4\enskip)\enskip.$

Using the Gauss identities, (this time MAPLE comes in handy) we get that

$\theta_{1}^{5}\enskip=\enskip-11u(26+20u-15u^{2}+10u^{3})\enskip.$

So $\theta_{1}$ is obtained by the tight root extraction

$\theta_{1}\enskip=\enskip{\root 5 \of{-11u(26+20u-15u^{2}+10u^{3})}}$ $None$

and $\beta_{o}$ is then given by

$\beta_{o}\enskip=\enskip(\theta_{o}+\theta_{1}+\cdots+\theta_{4})/5$

Now again we have $\theta_{o}=-1$. To express $\beta_{o}$ entirely in terms of
$\theta_{1}$ we need to compute the ratios $c_{i}=\theta_{i}/\theta_{1}^{i}$.
We shall compute $c_{2}$ here and leave it to the reader to compute the other
$c_{i}$’s.

In complete agreement with our Remark 7.1 we find that

$\theta_{1}\theta_{2}\theta_{3}\theta_{4}\enskip=\enskip 121=11^{2}\in{\cal
Q}$

So we may write

$\theta_{2}=c_{2}\theta_{1}^{2}\enskip=\enskip{121\over\theta_{1}^{3}\theta_{3}\theta_{4}}\hskip
2.5pt\theta_{1}^{2}$

Again the Gauss formulas (and MAPLE) give that

$\theta_{1}^{3}\theta_{3}\theta_{4}\enskip=\enskip 121u(2-2u-u^{2})\enskip,$

and we can then easily get that

$\theta_{2}\enskip=\enskip{4+2u+2u^{2}+u^{3}\over
11u}\enskip\theta_{1}^{2}\enskip.$

Since $2^{5}\cong-1$ mod $11$ we see that

$\beta_{o}\enskip=\enskip\alpha+\alpha^{-1}$

so in one more step we can get our desired $\alpha$ by solving the equation

$(t-\alpha_{o})(t-\alpha_{5})\enskip=\enskip t^{2}-\beta_{o}t+1\enskip=\enskip
0\enskip.$

This gives again

$\alpha\enskip=\enskip{\beta_{o}+{\root 2 \of{\beta_{o}-4}}\over 2}$

In accordance with the fact that $p-1=5\times 2$ here we have only needed two
natural adjunctions to reduce the Galois group to the identity. Namely,
$\alpha_{o}+\alpha_{5}$ and $\alpha_{o}$.

$\underline{p=7}$:

We will be brief here. In this case we must take $e=3$ as a primitive exponent
and set $\alpha_{i}=\alpha^{3^{i}}$ for $i=0,1,\ldots,5$, where $\alpha$ is
our desired $7^{th}$-root of unity. The Galois group in this case is

$G_{\Phi_{7}}({\cal Q})\enskip=\enskip 1+\gamma+\cdots+\gamma^{5}\hskip
36.135pt(\enskip with\enskip\gamma\alpha_{i}=\alpha_{i+1}\enskip)$

Since $p-1=3\times 2$ we start with

$\beta_{r}\enskip=\enskip\Pi_{3}(\alpha_{r})\hskip 36.135pt(\enskip for\enskip
r=0,1,2\enskip)$

Then Gauss’ formulas yield us the table

$\matrix{\beta_{o}\beta_{o}=2+\beta_{2}&\beta_{o}\beta_{1}=\beta_{1}+\beta_{2}&\beta_{o}\beta_{2}=\beta_{o}+\beta_{1}\cr\beta_{1}\beta_{o}=\beta_{1}+\beta_{2}&\beta_{1}\beta_{1}=2+\beta_{o}&\beta_{1}\beta_{2}=\beta_{o}+\beta_{2}\cr\beta_{2}\beta_{o}=\beta_{o}+\beta_{1}&\beta_{2}\beta_{1}=\beta_{o}+\beta_{2}&\beta_{2}\beta_{2}=2+\beta_{1}\cr}$

From which we get that

$(t-\beta_{o})(t-\beta_{1})(t-\beta_{2})\enskip=\enskip
t^{3}+t^{2}-2t-1\enskip.$

Theorem 6.5 gives that this polynomial is cyclic with Galois group
$1+\gamma+\gamma^{2}$. So we may use Proposition 7.2 with $p=3$ and set again

$\eqalign{\theta_{o}&\enskip=\enskip\beta_{o}+\beta_{1}+\beta_{2}\enskip,\cr\theta_{1}&\enskip=\enskip\beta_{o}+u\beta_{1}+u^{2}\beta_{2}\enskip,\cr\theta_{2}&\enskip=\enskip\beta_{o}+u^{2}\beta_{1}+u^{4}\beta_{2}\enskip,\cr}$

This gives us

$\beta_{o}=(-1+\theta_{1}+\theta_{2})/2$

Using the table we easily derive that

$\theta_{1}\theta_{2}\enskip=\enskip 7\enskip\enskip\enskip
and\enskip\enskip\enskip\theta_{1}^{3}\enskip=\enskip-7-21u$

so we may write

$\theta_{2}\enskip=\enskip{7\over\theta_{1}}\enskip=\enskip{7\over\theta_{1}^{3}}\enskip\theta_{1}^{2}\enskip=\enskip{2+3u\over
7}\enskip\theta_{1}^{2}\enskip.$

So we get

$\theta_{1}\enskip=\enskip{\root 3 \of{-7-21u}}$

and

$\beta_{o}={-1+\theta_{1}+(2+3u)\theta_{1}^{2}/7\over 2}\enskip.$

Now here

$\beta_{o}=\alpha_{o}+\alpha_{3}\hskip 2.5pt,\hskip
2.5pt\beta_{1}=\alpha_{1}+\alpha_{4}\hskip 2.5pt,\hskip
2.5pt\beta_{2}=\alpha_{2}+\alpha_{5}$

and since $\alpha_{3}=\alpha^{-1}$ we can find $\alpha$ by solving the
equation

$(t-\alpha_{o})(t-\alpha_{3})\enskip=\enskip t^{2}-\beta_{o}t+1$

which gives

$\alpha={\beta_{o}+{\root 2 \of{\beta_{o}^{2}-4}}\over 2}$

$\underline{p=5}$:

Here we may take the exponent $e=2$. So if $\alpha$ denotes our desired
primitive $5^{th}$-root, we need to set $\alpha_{i}=\alpha^{2^{i}}$ for
$i=0,1,\ldots,3$. Since $p-1=2\times 2$ we start by constructing the two
elements

$\beta_{o}=\alpha_{o}+\alpha_{2}\enskip\enskip\enskip,\enskip\enskip\enskip\beta_{1}=\alpha_{1}+\alpha_{3}$

by solving the quadratic

$(t-\beta_{o})(t-\beta_{1})\enskip=\enskip t^{2}+t-1\enskip.$

Thus we may take

$\beta_{o}\enskip=\enskip{-1+{\root 2 \of{5}}\over
2}\enskip\enskip\enskip,\enskip\enskip\enskip\beta_{1}\enskip=\enskip{-1-{\root
2 \of{5}}\over 2}\enskip,$

and $\alpha$ can be obtained by solving

$(t-\alpha_{o})(t-\alpha_{2})\enskip=\enskip t^{2}-\beta_{o}t+1\enskip=\enskip
0\enskip.$

Since $\beta_{o}^{2}=\beta_{1}+2$ we finally obtain

$\alpha={\beta_{o}+{\root 2 \of{\beta_{1}-4}}\over
2}\enskip=\enskip{{{-1+{\root 2 \of{5}}\over 2}+i\hskip 2.5pt{\root 2
\of{5+{\root 2 \of{5}}\over 2}}}\over 2}$

We are now in a position to establish the basic result of this section

Theorem 7.2

Every cyclic equation can be solved by a sequence of tight and natural radical
extractions

Proof

Suppose that ${\tilde{E}}_{n}(t)$ is cyclic in ${\cal F}$, and let
$\alpha_{1},\alpha_{2},\ldots,\alpha_{n}$ be the labeling of its roots under
which

$G_{{\tilde{E}}_{n}}({\cal F})\enskip=\enskip
1+\gamma+\gamma^{2}+\cdots+\gamma^{n-1}\enskip.\hskip 36.135pt\hskip
36.135pt(\hskip 2.5ptwith\enskip\gamma\alpha_{i}=\alpha_{i+1}\enskip)$

If $p_{1}\geq p_{2}\geq\cdots\geq p_{m}$ are the primes factoring $n$ we
proceed by constructing a sequence of subgroups $G_{k}$ yielding the
composition series

$G_{{\tilde{E}}_{n}}({\cal
F})\triangleright_{p_{1}}G_{1}\triangleright_{p_{2}}G_{2}\triangleright_{p_{2}}\cdots\triangleright_{p_{m}}G_{m}=\\{id\\}$

This given we construct (via Theorem 6.1) a sequence of polynomials
$\Psi_{k}(x_{1},x_{2},\ldots,x_{n})\in{\cal F}[x_{1},x_{2},\ldots,x_{n}]$ with
${\tilde{G}}_{\Psi_{k}}=G_{k}$. Now Theorem 6.4 and
${\tilde{G}}_{\Psi_{k}}\triangleleft_{p_{k}}{\tilde{G}}_{\Psi_{k-1}}$ give
that

${\cal F}[{\tilde{\Psi}}_{k}]\supseteq{\cal F}[{\tilde{\Psi}}_{k-1}]\enskip.$

Moreover from Theorem 6.5 we also deduce that ${\tilde{\Psi}}_{k}$ is a root
of a polynomial $B_{{\tilde{\Psi}}_{k}}(t)\in{\cal
F}[{\tilde{\Psi}}_{k-1}][t]$ of degree $p_{k}$ which is cyclic in ${\cal
F}[{\tilde{\Psi}}_{k-1}]$. Thus its roots may be constructed by means of the
formulas given by Proposition 7.2. Let $\root p_{k} \of{\Xi}_{k}$ with
$\Xi_{k}\in{\cal F}_{k-1}$ denote the radical we must extract to obtain
${\tilde{\Psi}}_{k}$. Now Proposition 7.2 assures that $\root p_{k}
\of{\Xi}_{k}$ is tight, and formula 7.20 gives that this a natural radical
extraction as long as we are in possession of a primitive $p_{k}^{th}$ root of
unity. Finally, the identity in 7.18 shows that ${\cal F}[{\tilde{\Psi}}_{k}]$
may also be obtained from ${\cal F}[{\tilde{\Psi}}_{k-1}]$ by the adjonction
of $\root p_{k} \of{\Xi}_{k}$ itself. This given, since the Galois group of
${\tilde{E}}_{n}$ reduces to the identity after the extraction of the last
radical $\root p_{m} \of{\Xi}_{m}$, the process will yield a tight natural
formula for each of the roots of ${\tilde{E}}_{n}$.

We should note that the tight extraction of prime $p^{th}$ roots of unity can
also included in this process. This is because, as we have seen, the formulas
giving a primitive $p_{k}^{th}$-root depend on the solution of cyclic
equations whose degrees are prime factors of $p_{k}-1$. But since each
$p_{k}\leq n$, we see that we are appropriately setup for an induction
argument. We can in fact assume from the start that the Theorem is true for
all cyclic equations of prime degree less or equal than a certain prime $p$
then carry out the constrution outlined above for all cylic equations of any
degree $n$ whose prime factors are all less or equal to the next prime. The
induction can of course start with $p=2$ where the Theorem is easily verified
to be true.

Bibliography

[1] Elwyn R. Berlekamp, ALGEBRAIC CODING THEORY, Revised 1984 Edition, Aegean
Park Press. 1-478

[2] Edgar Dehn, ALGEBRAIC EQUATIONS, An Introduction to the Theories of
Lagrange and Galois, Dover Publications. 1-208

The author of the lecture notes has used the contents of these books in a
different order. Inspired by the contents of these two books and guided by
their contents. The author just used the results without using their proofs
but guided by the results of Galois Theory as obtained by Galois himself.


# Which Sustainable Software Practices and Tools
Do Scientists Find Most Useful?

Jory Schossau
Michigan State University
<EMAIL_ADDRESS>Greg Wilson
Mozilla Science Lab
<EMAIL_ADDRESS>
###### Abstract

We studied scientists who attended two-day workshops on basic software skills
to determine which tools and practices they found most useful. Our pre- and
post-workshop surveys showed increases in self-reported familiarity, while our
interviews showed that participants found learning Python more useful than
learning the Unix shell, that they found pointers to further resources very
valuable, and that background material—the “why” behind the skills—was also
very valuable.

##  1 Introduction

Education about sustainable software practices is key to actual adoption.
Unfortunately, discussion about sustainable practices with the average
scientist often founders because most scientists aren’t using even _basic_
practices [1, 2]. First encounters must therefore typically focus on concepts
such as when and where to use a script instead of a spreadsheet, how to
automate file manipulations typically performed by hand, why to use a version
control system to track work, and how to write code for sanity and posterity
[3].

Teaching these topics is the main aim of Software Carpentry, a volunteer
organization through which scientists (and others) with the right knowledge
and teaching skills can teach other scientists. Its two-day workshops,
typically held at universities, are just long enough to introduce learners to
the handful of core competencies mentioned earlier. Participants are typically
excited about the subjects they learn, but which practices are actually useful
for these scientists in their daily work, which do they actually adopt, and
how effectively Software Carpentry is teaching them? This study’s goal was to
find answers to those questions.

##  2 Surveys

In the summer of 2013 the lead author designed a survey to be administered to
attendees directly before and after a Software Carpentry workshop. This survey
has let us gather information about how well the workshop prepared attendees
to handle sample real-world problems in the core competency areas, so that we
could see if what we set out to teach was being taught. We decided early on to
include only one skill-related question per core competency; while this means
we gather less (and less accurate) information per subject, both research and
experience have shown that shorter surveys are more likely to be completed.

Figure 1: Participants categorized by self-reported frequency of programming
(n=95).

The first set of questions on the survey was unique to the the pre-workshop
survey. These questions covered basic demographics such as career stage, time
spent programming, and operating system preference, and were used to help
tailor workshops to the audience. These questions revealed that most of our
learners had little to no experience programming, but that particular
workshops would sometimes be filled with people who were more proficient. It
has proven very useful for instructors to know even this much about their
learners (Figure 1).

The second set of questions asked about familiarity with a topic, and then, if
applicable, about self-reported ability to solve a small real-world problem.
The difference between the pre-workshop and post-workshop survey responses
allowed us to measure the effect of the workshop. However, because asking
people the same question twice creates a recognition bias, the post-workshop
survey was created with similar but different questions.

(a) Shell Familiarity: Increases in self-reported familiarity (n=43).

(b) Shell Skill: Increases in self-reported skill (n=40).

Figure 2:  (a) The difference between familiarity levels before and after the
workshop ($n=43$). Options were “I am not familiar with the command line,” “I
am familiar with only the term ‘command line’,” “I am familiar with the
command line but have never used it,” and “I am familiar with the command line
because I have or am using it.” The histogram represents ordinal changes. The
negative recordings belong to individuals who likely had a poor workshop
experience. (b) Difference between predicted skill levels before and after the
workshop on similar hypothetical real-world problems ($n=40$). The question
posed was if the participant could perform a filename query by file contents
on the command line. Options were “I could not create this list,” I would
create this list using:, “‘Find in Files’ and ‘copy & paste’,” “basic command
line programs,” “a pipeline of command line programs.”

(a) Improvement from beginning with no ability. ($n=7$)

(b) Improvement from beginning with copy & paste ability. ($n=9$)

(c) Improvement from beginning with simple CLI commands ability($n=24$).

Figure 3:  The histograms show post-workshop self-assessed ability for a real-
world Unix shell problem given each pre-workshop self-assessed ability level
represented by each figure. Each participant for these data answered they are
familiar with the shell because they have or are using it in their work. This
is a more detailed view of the data from Figure 2.

Figure 2(a) shows changes in participants’ pre-workshop familiarity with using
the Unix shell. We expected this distribution to be highly right-skewed
because many attendees didn’t have a computational background, and workshops
involved hands-on lessons with the shell.

Figure 2(b) shows changes in Unix shell skill level over the course of the
workshop. As we expected, most participants were able to improve their ability
to use the Unix shell, up to our maximum measure which was the ability to use
a single line of piped commands to solve the presented problem. Overall, most
participants improved one ability level, but there were some who improved 3
ability levels, indicating a change in self-assessment from not being able to
computationally solve the problem to self-assessing the participant could
solve the problem using a single line of piped shell commands. Figure 3 shows
a more detailed view of Figure 2(b), separating participants by their
beginning self-assessed skill level and showing their final self-assessed
skill level. This data suggests what could be expected, that final achieved
skill level is dependent on the beginning skill level, but also that those who
benefit most from these workshops already have some conceptual framework of
the Unix shell and are therefore able to rapidly and effectively learn the new
information.

Figure 4:  Differences in self-reported familiarity for the four measured
topics.

Figure 4 summarizes the same analysis as Figure 2(a) for all measured topics:
Unix Shell, SQL, Version Control (VCS), and Testing. There are responses that
show no increase such as for the Testing familiarity. This is likely because
Testing is sometimes left as a final topic, leaving time to determine how in-
depth the instructor may delve. Similarly, educational effect for skill
competency shows few data points for several topics. Figure 5

Figure 5:  Differences in self-reported skill competency for the four measured
topics. Categories from which this delta was measure included: ”Could not
complete the task,” ”I could complete the task with documentation or search
engine help,” and ”I could complete the task with little or no documentation
or search engine help.” Testing, SQL, and VCS allowed for a maximum of 2 skill
level changes, while the Shell assessment allowed for a maximum of 3 skill
level changes.

##  3 Interviews

At the same time as we began gathering survey data, the first author developed
and began using a semi-structured protocol for interviews in order to
understand what practices scientists were finding useful six months after a
workshop. 24 participants were interviewed concerning their work, workshop
experience, how Software Carpentry helped them, and how they might change the
experience. The transcripts of these interviews were analyzed using the
standard qualitative technique of open, axial, and selective coding, which
helped determine how best to translate qualitative responses into quantitative
categorical data.

Figure 6:  Coding of 3-month post-workshop interview transcripts ($n=71$).
Categories represent instances a participant mentioned directly benefiting
from the given topic.

We were initially surprised that Python was mentioned most often as the most
useful topic rather than the command line. The other core competencies
followed in popularity of helpfulness, which was more or less expected, but
some other fairly popular categories emerged during the coding process which
were completely unanticipated. These categories had been labeled “knowing”,
“psychology”, and “resources”.

  * •

_Knowing_ represents the satisfaction attendees have expressed that they had
been told about a technology or method for which they had no immediate use but
believed it may be useful. This can include simply knowing about a core
competency without any planned use, but also includes knowing about certain
software or how types of scripting work.

  * •

_Psychology_ represents the usefulness attendees have expressed of learning
about the psychology of programming, including empirically validated insights
about how people work with computers, need breaks, or should write code. The
second author (who taught several of the workshops from which survey
participants were drawn) frequently cites this information while teaching a
workshop. One subject said, “Most important thing I think was the insight into
the psychological basis of working.”

  * •

_Resources_ represents attendees’ mention of learning about books, websites,
videos, and other sources of information not directly used within the
workshop, but explicitly highlighted for their educational value.

Some participants greatly benefited from the workshop saying, for instance,
“version control I knew nothing about and now I use regularly,” and, “seeing
how to do things reproducibly and more efficiently was very useful,” but
others wanted more: “too short in 2 days, so perhaps less ground and more
time.”

One participant’s story of benefit from Software Carpentry stood out. Their
neighborhood was being repeatedly targeted by a small group of thieves, so
they decided to use their newfound skills from Software Carpentry to build an
inexpensive surveillance camera. They used an Arduino computer with storage
and camera, and created a Python script to manage the device, all versioned
with Git. The footage obtained from this system allowed local law enforcement
to catch and sentence the thieves. We obviously can’t expect everyone to
benefit quite this much, but this example does show how broadly useful even
two days’ worth of training can be.

The most unexpected result from our study was a nearly unanimous opinion about
what should change about the workshops: more depth, more exercises, and more
about working with data files and plotting. This finding about the need for
scientists to know more about how to simply work with data falls into a long
line of informal and formal feedback, and has led to the launch of a sibling
project called Data Carpentry.

##  4 Future Work

As well as surveying workshop participants, we are now collecting data from
our instructors to find out what technologies they used, what topics they
covered, how they think it went, and how well they think the least skilled
attendee could perform on the hypothetical problems. We will match this data
with how the participants answered to see if there was anything unusual, such
as a disconnect in perceived instructional pacing, or to see if there are
trends of topics that are difficult for participants to grasp and difficult
for the instructors to measure their comprehension.

Interviews give us a lot of insight, but are labor-intensive and hence
unscalable. Our next goal is therefore to construct and validate better pre-
and post-workshop questionnaires so that we can track skill uptake and
participant satisfaction more systematically on a larger scale.

### Acknowledgments

Our thanks to everyone who took part in our surveys and interviews, and to the
Mozilla Science Lab and the Sloan Foundation for their support.

## References

  * [1] Jo Erskine Hannay, Hans Petter Langtangen, Carolyn MacLeod, Dietmar Pfahl, Janice Singer, and Greg Wilson.  How do scientists develop and use scientific software?  In Second International Workshop on Software Engineering for Computational Science and Engineering (SECSE09), 2009.
  * [2] Prakash Prabhu, Thomas B. Jablin, Arun Raman, Yun Zhang, Jialu Huang, Hanjun Kim, Nick P. Johnson, Feng Liu, Soumyadeep Ghosh, Stephen Beard, Taewook Oh, Matthew Zoufaly, David Walker, and David I. August.  A Survey of the Practice of Computational Science.  In Proceedings of the 24th ACM/IEEE Conference on High Performance Computing, Networking, Storage and Analysis, 2011.
  * [3] Greg Wilson, D. A. Aruliah, C. Titus Brown, Neil P. Chue Hong, Matt Davis, Richard T. Guy, Steven H.D. Haddock, Kathryn D. Huff, Ian M. Mitchell, Mark D. Plumbley, Ben Waugh, Ethan P. White, and Paul Wilson.  Best practices for scientific computing.  PLoS Biology, 12(1):e1001745, January 2014.


#  On-the-Fly Attention Modulation for Neural Generation

Yue Dong1 Chandra Bhagavatula2 Ximing Lu2,4 Jena D. Hwang2
Antoine Bosselut2,3 Jackie Chi Kit Cheung1 Yejin Choi2,4

1Mila / McGill University 2Allen Institute for Artificial Intelligence
3 Stanford University 4Paul G. Allen School of CSE, University of Washington
{yue.dong2@mail, <EMAIL_ADDRESS>
<EMAIL_ADDRESS>*This work was done
when the first author was an intern at AI2.

###### Abstract

Despite considerable advancements with deep neural language models (LMs),
neural text generation still suffers from degeneration: the generated text is
repetitive, generic, self-contradictory, and often lacks commonsense. Our
analyses on sentence-level attention patterns in LMs reveal that neural
degeneration may be associated with insufficient learning of task-specific
characteristics by the attention mechanism. This finding motivates on-the-fly
attention modulation11footnotemark: 1– a simple but effective method that
enables the injection of priors into attention computation during inference.
Automatic and human evaluation results on three text generation benchmarks
demonstrate that attention modulation helps LMs generate text with enhanced
fluency, creativity, and commonsense reasoning, in addition to significantly
reduce sentence-level repetition.

##  1 Introduction

Neural text generation is critical for a wide range of downstream natural
language applications. However, the standard approach – using a Transformer-
based (Vaswani et al., 2017) language model (e.g., Radford et al., 2019) with
maximum likelihood fine-tuning and non-stochastic decoding – is known to
exhibit degeneration (Welleck et al., 2019). Despite being pre-trained on
large amounts of data, text generated by neural models is observed to be
repetitive, generic, self-contradictory, and lacking commonsense (Holtzman et
al., 2020).

Many explanations have been proposed for neural text degeneration, including
inappropriate training objectives (Welleck et al., 2019) and decoding
discrepancies relative to human language Holtzman et al. (2018, 2020). While
the aforementioned may be factors for neural degeneration, we show that
insufficient learning of task-specific characteristics – reflected in the
self-attention mechanism in transformer blocks – is associated with neural
text degeneration. We demonstrate that degeneration is alleviated if we inject
priors through attention modulation (AttnM) during inference.

Figure 1: Example of fine-tuned GPT2-L outputs without (top) and with (bottom)
attention modulation on $\alpha$NLG. The task is to generate a plausible
explanatory hypothesis $H$ for observations $O_{1}$ and $O_{2}$. Our proposed
attention modulation injects the task-specific prior – LMs should consider
both observations relative equally – through balancing the sentence-level
attention weights (Eqn. 5) in Transformer blocks during inference. Applying
attention modulation with the aforementioned prior make sentence-level
attentions from generation to observation pairs ($O_{1}$,$O_{2}$) more
balanced333attention ratios are normalized mean sentence-to-sentence attention
from generation $H$ to observations $O_{1}$ and $O_{2}$, which are reflected
in the sentence-level attention heatmaps of GPT2-L (darker = lower attention)
across layers (y-axis) and heads (x-axis).

Self-attention – the ubiquitous component of Transformers – is task-agnostic
with a large learning capacity for many NLP tasks (Vaswani et al., 2017;
Devlin et al., 2019; Brown et al., 2020). It learns the general
characteristics of language processing through pre-training on large amounts
of unlabeled data. For example, multiple analyses have suggested that
attention patterns in pre-trained Transformers implicitly encode syntactic
information (Raganato and Tiedemann, 2018; Michel et al., 2019; Vig and
Belinkov, 2019). In sequence transduction tasks, these learned
characteristics, embedded in attention, make pre-trained Transformers a
powerful language model (Radford et al., 2019).

A final task-specific step is typically required for adapting a task-agnostic
language model to perform the desired task444Brown et al. (2020) have shown
that GPT3 greatly improves task-agnostic, few-shot performance, but still
struggles on tasks with strong task-specific characteristics.. However, these
task-specific characteristics might not sufficiently coincide with general
characteristics even after fine-tuning. For example, task-specific
characteristics embedded in attention patterns – such as word alignments for
machine translation – are often noisy and imperfect for generalization
(Kobayashi et al., 2020).

We show that insufficient learning of task-specific characteristics, reflected
in sentence-level attention patterns555We study the global context in the
multi-sentence prompts and choose sentence-level attention (Eqn. 7) as the
experiment unit, since sentences are linguistic units of complete meaning.
often being out of focus, may be associated with neural text degeneration
(§3). Based on this observation, we propose a simple attention modulation
framework that can dynamically redistribute sentence-level attention weights
by injecting task-specific priors in Transformer blocks for different
downstream tasks (§4). Remarkably, in long-range narrative story generation,
abductive reasoning generation and constrained commonsense text generation,
both automatic and human evaluation have shown improved quality in fluency,
dullness, repetition, and commonsense reasoning with attention modulation
(§6).

##  2 Background

We briefly discuss how vanilla attention works, as well as Transformer
architecture used in this paper.

#### Single-headed attention

Given a sequence of $d$-dimensional input vectors
$\bm{x}=\\{\bm{x}_{1},\ldots,\bm{x}_{n}\\}$, attention mechanism computes a
set of weights based on a query vector $\bm{y}_{i}\in\mathbb{R}^{d}$:

$\text{Attn}(\bm{x},\bm{y}_{i})=(\alpha_{i,1}(\bm{x},\bm{y}_{i}),\ldots,\alpha_{i,n}(\bm{x},\bm{y}_{i}))$
(1)

where $\alpha_{i,j}$ is the attention weight that $\bm{y}_{i}$ pays to
$\bm{x}_{j}$. One formulation of attention — scaled dot product attention — is
computed as:

$\alpha_{i,j}:=\underset{\bm{x}_{j}\in\bm{x}}{\text{softmax}}\Big{(}\frac{\bm{q}(\bm{y}_{i})\bm{k}(\bm{x}_{j})^{\top}}{\sqrt{d}}\Big{)}\in\mathbb{R}$
(2)

where query $\bm{q}(\cdot)$ and key $\bm{k}(\cdot)$ functions are linear
transformations. In self attention, every $\bm{x}_{i}$ is used as the query
vector ($\bm{y}_{i}$). An updated representation $\tilde{\bm{x}}_{i}$ is
computed as a weighted sum of value vectors that are linearly transformed by
$\bm{v}(\cdot)$:

$\tilde{\bm{x}}_{i}=\sum_{\bm{x}_{j}\in\bm{x}}\alpha_{i,j}\bm{v}(\bm{x}_{j}).$
(3)

#### Multi-head attention

In multi-headed attention (MHA), $N_{h}$ attention heads are computed
independently to obtain the updated $\tilde{\bm{x}}_{i}$:

$\tilde{\bm{x}}_{i}=W_{o}\bigparallel_{h=1}^{N_{h}}\Big{(}\sum_{\bm{x}_{j}\in\bm{x}}\alpha^{h}_{i,j}\bm{v^{h}}(\bm{x}_{j})\Big{)}.$
(4)

$\alpha^{h}_{i,j}$ follows Eqn. 2 except the model dimension in each head $h$
is often reduced to $d_{h}=\frac{d}{N_{h}}$. $\tilde{\bm{x}}_{i}$ is obtained
by the concatenation of lower-rank representations from all heads and
$W_{o}\in\mathbb{R}^{d\times h\cdot d_{h}}$.

#### GPT2-L

GPT2 (Radford et al., 2019) is a family of Transformer-based language models
(LMs) that follows the architecture of stacked decoder. As GPT2 follows a
multi-layer and multi-headed setting, $\alpha_{i,j}$ is specific to a layer
$l$ and head $h$, noted as $\alpha_{i,j}^{l,h}$. We use the GPT2-L model that
has 36 layers with 20 heads per layer (762M total parameters).

##  3 Neural text degeneration vs. attention

As researchers have sought to understand the internal mechanisms of
Transformers, the attention patterns exhibited by these heads have drawn
considerable study (Vig and Belinkov, 2019; Jain and Wallace, 2019; Wiegreffe
and Pinter, 2019). We perform sentence-level attention analysis to explore
whether aggregated attention patterns are associated with neural text
degeneration.

###  3.1 Sentence-level attention

We first define the sentence-to-sentence attention of a language model
$\mathcal{M}$ with $L$ layers and $H$ heads. Given two sentences $p$ and $g$
such that $p$ precedes $g$, the mean $\bar{\alpha}^{l,h}_{g,p}$ and max
$\hat{\alpha}^{l,h}_{g,p}$ sentence-to-sentence attentions from $g$ to $p$ for
layer $l$ and head $h$ are:

$\bar{\alpha}^{l,h}_{g,p}=\frac{\sum\limits_{i=1}^{|g|}\sum\limits_{j=1}^{|p|}\alpha^{l,h}_{i,j}(g_{i},p_{j})}{|g|\cdot|p|}$
(5)

$\hat{\alpha}^{l,h}_{g,p}=\max_{\begin{subarray}{c}i\in\\{1,\ldots,|g|\\}\\\
j\in\\{1,\ldots,|p|\\}\end{subarray}}\alpha^{l,h}_{i,j}(g_{i},p_{j}).$ (6)

The aggregated sentence-to-sentence attention over the Transformer
architecture $\mathcal{M}$ is defined as:

$\alpha^{\mathcal{M}}_{g,p}=\frac{\sum\limits_{l=1}^{L}\sum\limits_{h=1}^{H}\alpha^{l,h}_{g,p}}{L\cdot
H}$ (7)

where $\alpha\in\\{\bar{\alpha},\hat{\alpha}\\}$ computes either the mean or
the max sentence-level attention over $\mathcal{M}$.

###  3.2 Is neural text degeneration related to attention patterns?

We conduct experiments to evaluate whether neural text degeneration is
associated with sentence-level attention patterns. Empirical results on two
types of neural degeneration that are easy to detect – repetition and lacking
commonsense reasoning under constraints – reveal their association.

#### Repetition vs. attention

One common form of neural text degeneration is sentence-level repetition
(Welleck et al., 2019). This type of degeneration happens frequently in our
experiment on ROCStories test set (§6.1): given a five-sentence prompt, 35.4%
of the consecutive sentences from the next five greedily generated sentences
by the fine-tuned GPT2-L are exact repetitions. We check whether sentence-
level attention patterns behave differently when generating repeated or
different consecutive sentences.

Figure 2: Mean sentence-level attention change of GPT2-L on ROCStories test
set, while generating different (red) or repeated (blue) consecutive
sentences.

We inspect the attention behavior by measuring the change of sentence-level
attention when generating two consecutive sentences. The generations of fine-
tuned GPT2-L on ROCStories test set are separated into two subsets
$\\{\mathcal{D}_{\text{repeated}},\mathcal{D}_{\text{different}}\\}$: in which
consecutive sentences that are either repeated (i.e., degenerate) or
different. Given the fine-tuned GPT2-L language model $\mathcal{M}$, we
measure the sentence-level attention change $\Delta$ on the prompt sentence
$p_{j\in\\{1,\ldots,5\\}}$ while generating the consecutive sentence pair
$(g_{i},g_{i+1}),i\in\\{1,\ldots,4\\}$, aggregated over the subset
$\mathcal{D}\in\\{\mathcal{D}_{\text{different}},\mathcal{D}_{\text{repeated}}\\}$:

$\Delta(j,\mathcal{D})=\sum_{d\in\mathcal{D}}|\bar{\alpha}^{\mathcal{M}}_{g^{d}_{i+1},p^{d}_{j}}-\bar{\alpha}^{\mathcal{M}}_{g^{d}_{i},p^{d}_{j}}|/|\mathcal{D}|$
(8)

where $\bar{\alpha}^{\mathcal{M}}_{g_{i},p_{j}}$ is the mean sentence-level
attention from sentence $g_{i}$ to sentence $p_{j}$ defined in Eqn. 7.

Figure 2 plots the aggregated mean sentence-level attention change over prompt
sentences when GPT2-L generates repeated (red) or different (blue) consecutive
sentences. The sentence-level attention changes are vastly lower on all prompt
sentences when generating repeated consecutive sentences. Thus, sentence-level
repetition may be correlated with the insufficient change of sentence-level
attention. In §4 and §6, we show that generation quality can be vastly
improved by injecting the prior – attention should look at the prompt
differently when generating different sentences – through our proposed
attention modulation.

#### Lack of commonsense reasoning vs. attention

Text generated by neural language models is also observed to be lacking
commonsense reasoning Mao et al. (2019). We check whether this type of neural
degeneration is associated with attention patterns. A benchmark dataset for
generative commonsense reasoning – CommonGen (Lin et al., 2020) – is used as
our test bed. CommonGen is designed for constrained commonsense reasoning:
given a set of common concepts (e.g., use, tool, piece, metal); the task is to
generate a coherent and plausible sentence covering all these concepts (e.g.,
"a piece of metal is used for making tools"). Covering the concepts in
generation requires relational reasoning with background commonsense
knowledge.

Each concept is represented as a prompt sentence in our experiments.666We can
obtain a clear boundary for each concept with this design choice of adding a
period as the separator, as concepts can be tokenized into multiple subwords
by GPT2 tokenizers. During generation, a concept (e.g.swim) is covered if its
reflected form (e.g.{swim, swimming, swam, swum}) is generated in the
CommonGen test set. We use a fine-tuned GPT2-L for the generation. Among the
5988 concepts in the prompt, about 75% of them are covered in the generation
of GPT2-L. We can then easily separate sentence-level attention from the
generation to the concept into two subsets: concept in the prompt that is
covered or uncovered by the generated sentence.

Table 1 shows the results of max sentence-level attention (Eqn. 7) of the
finetuned GPT2-L on the CommonGen test set777We measure the max sentence-level
attention rather than the mean sentence-level attention on CommonGen, as the
attention to a concept is usually reduced once it is generated.. We can
observe that sentence-level attention from the generation to the concept is
vastly higher when the concept is covered. Compared to that of uncovered
concepts, the aggregated max sentence-level attention is 15.4% higher.
Therefore, failing to generate a common concept through reasoning may be
associated with insufficient attention to the concept.

| agg. max attn. | SD | #
---|---|---|---
covered | 0.434 | 0.0040 | 4515
uncovered | 0.376 | 0.0068 | 1473
Table 1: Aggregated max sentence-level attention of the fine-tuned GPT2-L; the
results are aggregated from the generation to covered or uncovered concepts on
the CommonGen test set. agg. max attn., SD, # refer to aggregated max
sentence-level attention, standard deviation, and the number of instances.

In both cases, neural text degeneration is associated with insufficient
attention to elements that are important for downstream generations. This
motivates us to explore whether we can inject these priors in the language
model by altering the attention mechanism to alleviate degeneration.

##  4 Method

This section describes our method – attention modulation – that can alleviate
neural text degeneration. In §4.1, we describe the general attention
modulation framework. In §4.2, §4.3, and §4.4, we discuss the priors injected
through attention modulation for three different tasks: narrative story
generation, abductive reasoning generation, and constrained commonsense
reasoning.

###  4.1 Attention Modulation

Attention modulation aims to change the attention weights of a Transformer-
based language model during inference, so that the generation can reflect
priors that alleviate neural text degeneration. This additional signal is
added to the self-attention computation in the Transformer blocks.

We reformulate the attention computation of Eqn. 2 by adding an attention
reweighting function $f$, where priors can be injected. Given a sequence of
input tokens $\bm{x}$, the self-attention from $\bm{x}_{i}$ to $\bm{x}_{j}$
($i\geq j$) while generating the $t$-token is reformulated to:

$\alpha^{t}_{i,j}:=\underset{\bm{x}_{j}\in\bm{x}}{\text{softmax}}\Big{(}\frac{\bm{q}(\bm{x}_{i})\bm{k}(\bm{x}_{j})^{\top}}{\sqrt{d}}+f_{i,j}(\bm{x},\bm{\alpha}^{t-1})\Big{)}$
(9)

where $f(\bm{x},\bm{\alpha}^{t-1})$ is the attention reweighting function and
$\bm{\alpha}^{t-1}$ is the attention weight matrix for all layers and heads in
the Transformer architecture at time step $t-1$. The attention reweighting
function $f$ can be either pre-defined or learned. In our experiments, we
inject pre-defined sentence-level priors (heuristics) through $f$ and show
that this injection alleviates neural text degeneration. We leave the learning
of better reweighting functions automatically to future work.

In the following sections, we describe sentence-level attention reweighting
functions that are used for three different text generation tasks.

###  4.2 ROCStories: narrative generation

As shown in §3, sentence repetition in long-form generation may be associated
with insufficient attention change while generating consecutive sentences. To
amplify the attention changes, we can redistribute sentence-level attention
with some priors while generating consecutive sentences.

We choose the prior that language model should consider long-range context
during generation, as we observed that attention mostly focuses on the near
history in many cases (Appendix A.1). Note this prior also increases the
sentence-level attention change while generating consecutive sentences: the
sentence-level attention for all previous sentences is always re-balanced
based on the newly-generated sentence. To balance the attention of tokens in
each sentence received while generating the next sentence, we define the
attention reweight function in Eqn. 9 with the aforementioned prior for
ROCStories as:

$f_{i,j}(\bm{x},\bm{\alpha}^{t-1}_{i,j})=\frac{1}{\alpha^{t-1}_{g_{i},p_{j}}}.$
(10)

As later sentences in the prompt usually receive larger sentence-level
attention weights (Appendix A.1), attention reweighting function defined in
Eqn. 10 will add a large weight to tokens in the early sentences and a small
weight to tokens in the late context sentences. The simple heuristic of
balancing context sentences to be considered relatively equal, namely more
weights on early context sentences, might not be optimal prior. However, it
improves the long-form story generation in multiple measures, including
fluency, interesting, newness, and repetition (§6.1).

###  4.3 $\alpha$NLG: abductive reasoning generation

The second benchmark dataset we tested with attention modulation is
$\alpha$NLG (Bhagavatula et al., 2020). This dataset is proposed for abductive
reasoning generation: given two observations $O_{1}$ and $O_{2}$, the model
needs to generate a valid hypothesis $h$ that explains what happened between
the two observations. For example, given $O_{1}$: "Today was the first day of
school." and $O_{2}$: "I hate school.", the task is to generate $h$ such as
"The teacher made fun of me." as a plausible explanation.

Bhagavatula et al. (2020) has shown that the fine-tuned GPT2 performs far
below human performance on the $\alpha$NLG task. We hypothesis that this may
be associated with insufficient learning of sentence-level attention to both
observations; for example, the model might over-fit to one of the observations
for generation. Thus, we inject the prior – the language model should consider
both observations relative equally – while generating a plausible explanation.
This prior can be injected with attention reweighting function defined in Eqn.
10.

###  4.4 CommonGen: constrained commonsense generation

The third benchmark is CommonGen – a constrained text generation challenge for
generative commonsense reasoning. CommonGen requires machines to generate a
realistic sentence using all concepts from a given concept set by conducting
commonsense reasoning over the relations among the given concepts. To
successfully generate a plausible and grammatical sentence that follows the
commonsense, models need to conduct commonsense reasoning over the relations
among the given concepts. Our experiment in §3.2 shows that the fine-tuned
GPT2-L can only cover about $75\%$ of concepts during generation. We infer
from Table 1 that this may be associated with GPT2-L giving insufficient
sentence-level attention to uncovered concepts. Thus, we propose a simple
heuristic – model should pay more attention to concepts that are not covered
yet – to be injected with attention modulation.

Consider the prompt with $m$ concepts $\bm{c}=\\{c_{1},\ldots,c_{m}\\}$ and a
partially generated sentence $y_{1},\ldots,y_{t-1}$. While generating the
$t$-th token, the sentence-level reweighting function from the $i$-th token to
the $j$-th token in $c_{k}$ is defined as:

$f_{i,j}(\bm{x})=\begin{cases}1/m&\text{if}\quad c_{k}\subset y_{1:t-1}\\\
1&\text{else}\\\ \end{cases}$ (11)

Intuitively, if a concept $c_{k}$ is covered in the partial generation,
attention modulation with Eqn. 11 will reduce the attention weights of the
tokens in concept $c_{k}$.

##  5 Experimental Setups

This section describes the experiment setups, including the baselines,
decoding algorithms, datasets, and evaluation metrics.

#### Model architecture & baseline

Attention modulation is architecture-agnostic and can be applied to any
Transformer-based models that contain self-attention computation. We choose
GPT2-L (Radford et al., 2019) for our experiments, which has achieved state-
of-the-art performance on a variety of generation tasks (Vig and Belinkov,
2019). Attention modulation can be applied to any range of layers in the
Transformer. To compare models with and without attention modulation on each
of the three generation tasks, we use the best fine-tuned GPT2-L based on the
validation set after fine-tuning for 4 epochs with the default settings.

| next 1 sent. | next 2 sent. | next 3 sent. | next 4 sent. | next 5 sent.
---|---|---|---|---|---
| uniq. | % rel. | uniq. | % rel. | uniq. | % rel. | uniq. | % rel. | uniq.$\uparrow$ | % rel.$\uparrow$ | % rep.$\downarrow$
w/o AttnM | 9.08k | 48.59 | 13.58k | 48.78 | 15.71k | 49.20 | 16.01k | 49.97 | 17.03k | 50.52 | 35.43
w/ AttnM (ours) | 10.39k | 52.92 | 15.12k | 54.23 | 18.33k | 55.35 | 20.41k | 55.78 | 22.69k | 55.78 | 17.49
ratio | 1.14 |  | 1.12 |  | 1.16 |  | 1.24 |  | 1.34 |  |

Table 2: Test results of the fine-tuned GPT2-L w/ and w/o attention modulation
on ROCstories with the greedy decoding algorithm. uniq. represent the unique
number of tokens generated in the whole test corpus, which measures the number
of new unique tokens generated. rel. represent relevancy, which measures the
percentage of tokens generated appears in the prompt. rep. measures the
sentence-level repetition – whether two sentences generated are identical.

#### Decoding

Attention modulation directly changes the attention weights of the context
tokens during inference. It is orthogonal to different decoding algorithms
that change the searching strategies based on the softmax distribution emitted
by Transformers.888These search-based decoding algorithms do not resolve the
poorly generated token-level probabilities. We present the results with non-
stochastic decoding algorithms (i.e. greedy decoding and beam search), as
generations based on them truly reflect the token-level probabilities
predicted by the model (Holtzman et al., 2018).

#### Datasets

We use three different generation datasets – ROCStories (Mostafazadeh et al.,
2016), $\alpha$NLG (Bhagavatula et al., 2020), and CommonGen (Lin et al.,
2020). For ROCStories, we used the 2017 version and split the data into
75/10/15 for train/val/test.

#### Evaluation

On ROCStories, we measure dullness, relevancy and repetition similar to
Welleck et al. (2019). We report the number of unique tokens generated, where
the generation is less dull if more unique tokens are generated. For
repetition, we directly measure sentence-level repetition: two generated
sentences are repeated if their strings are the same. For relevancy, we
measure the percentage of generated tokens that appear in the prompt. Besides,
we perform a human evaluation, where three annotators are asked to rate the
generations based on fluency, interestingness, newness, relevancy, and
repetition.

On $\alpha$NLG, we score the generated explanation with respect to the
reference using the following automatic metrics: BLEU (Papineni et al., 2002),
ROUGE (Lin, 2004), METEOR (Banerjee and Lavie, 2005), and CIDEr (Vedantam et
al., 2015). In addition, we ask annotators to compare the generated
explanations without and with attention modulation. Human judges are asked to
decide which system provides a more plausible explanation of the observations.

On CommonGen, we report SPICE (Anderson et al., 2016) – a measure that
evaluates semantic propositional content, in addtion to BLEU, ROUGE, METEOR,
CIDEr. We also report Coverage (Lin et al., 2020), which computes the average
percentage of input concepts that appear in the lemmatized outputs. We conduct
a human evaluation following the protocol of Lu et al. (2020). Human judges
are asked to compare two systems in terms of fluency, coverage (covers the
concept), and overall quality (covers the concepts and follows commonsense).

##  6 Result

In this section, we present the vast improvements of the fine-tuned GPT2-L
with attention modulation on three narrative generation and generative
reasoning tasks: ROCStories, $\alpha$NLG, and CommonGen.

Figure 3: Human evaluation results on the next 1 to 5 sentences generated
without (dashed lines) and with (solid lines) attention modulation ($1000$
samples).

|  | R-2 | R-L | B-3 | B-4 | Meteor | CIDEr | SPICE | Coverage
---|---|---|---|---|---|---|---|---|---
greedy | w/o AttnM | 14.06 | 34.13 | 26.19 | 17.92 | 25.82 | 10.81 | 22.14 | 76.50
w/ AttnM (ours) | 14.71 | 35.15 | 27.53 | 18.91 | 26.23 | 11.61 | 23.22 | 79.18
beam=5 | w/o AttnM | 16.68 | 36.92 | 32.39 | 23.36 | 26.87 | 12.24 | 22.83 | 76.99
w/ AttnM (ours) | 17.14 | 38.23 | 33.92 | 24.03 | 27.48 | 12.88 | 24.24 | 81.27
beam=10 | w/o AttnM | 17.25 | 37.37 | 33.81 | 24.39 | 27.51 | 12.58 | 23.24 | 78.68
w/ AttnM (ours) | 17.59 | 38.71 | 35.72 | 25.93 | 27.71 | 13.32 | 24.36 | 81.24
beam=20 | Lin et al. (2020) | 16.85 | 39.01 | 33.92 | 23.73 | 26.83 | 12.19 | 23.57 | 79.09
w/o AttnM | 17.98 | 38.07 | 35.14 | 25.61 | 27.63 | 12.90 | 23.28 | 79.62
w/ AttnM (ours) | 18.11 | 39.32 | 36.69 | 26.80 | 28.02 | 13.71 | 23.94 | 81.85

Table 3: CommonGen test results of the fine-tuned GPT2-L w/ or w/o attention
modulation based on different decoding algorithms.

| B-4 | R-L | Meteor | CIDEr | Human
---|---|---|---|---|---
w/o AttnM | 13.51 | 18.29 | 13.18 | 47.69 | 14%
w/ AttnM (ours) | 13.52 | 18.01 | 13.18 | 48.20 | 33%

Table 4: Evaluations of the fine-tune GPT2-L on $\alpha$NLG using greedy
decoding.

###  6.1 ROCstories

Table 2 indicates that attention modulation significantly reduces repetition
in narrative generation, while increasing the relevancy of generated sentences
to the original story. We can observe a vast improvement in the number of
unique generated tokens using attention modulation, indicating a reduced
repetition rate (confirmed by the % number of repeated sentences in the next
five sentence generated – 35.43 vs. 17.49 for our approach). This intuition is
confirmed by our human evaluation in Figure 3, where the GPT2-L with attention
modulation produces sentences that are more fluent, more interesting, more
novel, and less repetitive than the original decoder. Furthermore, we note
that the difference in performance across these evaluation categories
generally increases as the number of generated sentences increases, indicating
less sensitivity to long-form degeneration.

###  6.2 $\alpha$NLG

Table 4 presents the automatic and human evaluation results on $\alpha$NLG. We
can see that our model performs similarly with and without attention
modulation in terms of automatic evaluation. However, our human evaluation
results in the last column show that overall, the human judges prefer the
explanations produced using attention modulation significantly more than those
of the original model. With 100 samples generated, 33$\%$ of the time, human
judges select explanations generated with attention modulation as more
plausible. In contrast, explanations from the original model are only
preferred 14$\%$ of the time.

Training size | Method | R-2 | R-L | B-3 | B-4 | Meteor | CIDEr | SPICE | Coverage
---|---|---|---|---|---|---|---|---|---
10 | w/o AttnM | 2.15 | 16.07 | 6.39 | 3.63 | 10.02 | 1.23 | 5.07 | 27.12
w/ AttnM (ours) | 3.38 | 18.89 | 7.24 | 3.48 | 12.47 | 1.63 | 7.21 |  36.55 $\uparrow$ 9.43
1000 | w/o AttnM | 7.61 | 27.03 | 14.01 | 7.38 | 20.67 | 6.40 | 16.79 | 62.33
w/ AttnM (ours) | 8.54 | 27.97 | 15.51 | 8.78 | 22.13 | 6.68 | 18.02 |  69.31 $\uparrow$ 6.98
10000 | w/o AttnM | 10.70 | 30.06 | 17.40 | 10.02 | 23.40 | 7.15 | 20.20 | 73.39
w/ AttnM (ours) | 11.53 | 30.70 | 18.43 | 11.12 | 24.42 | 7.29 | 21.33 |  78.74 $\uparrow$ 5.35
full ($\sim$39k) | w/o AttnM | 14.06 | 34.13 | 26.19 | 17.92 | 25.82 | 10.81 | 22.14 | 76.50
w/ AttnM (ours) | 14.71 | 35.15 | 27.53 | 18.91 | 26.23 | 11.61 | 23.22 |  79.18 $\uparrow$ 2.68

Table 5: CommonGen test results of the fine-tuned GPT2-L w/ or w/o attention
modulation trained on different size of training examples (greedy decoding).

###  6.3 CommonGen

|  Fluency |  Quality |  Overall
---|---|---|---
w/o AttnM |  85.07 |  39.30 |  44.77
w/ AttnM (ours) |  89.55 |  48.76 |  52.73
Table 6: Human evaluations of the fine-tuned GP2-L w/o or w/ attention
modulation on CommonGen.

Table 3 shows the automatic evaluation results on the CommonGen dataset. We
separate different settings of decoding algorithms in blocks. By injecting the
prior – the model should put more attention on uncovered concepts – into the
GPT2-L with attention modulation, we can improve the text generated in every
automatic measure significantly. Interestingly, despite our attention-
reweighted decoder only encouraging coverage, we see all the other measures
such as ROUGE, BLEU, METEOR, CIDEr, SPICE improve, as well.

These improvements also hold when we use a different base decoding algorithm,
such as beam search. Again, the performance improvement for using attention
modulation is significant over all measures. Thus, unlike decoding algorithms
that improve downstream tasks through truncation of the sampling distribution,
we directly re-calibrate the token-level probabilities predicted by the model
by altering attention patterns in the Transformer blocks during inference.

We also conduct a human evaluation to check whether this improvement in the
automatic metrics transfers to human judgments. In Table 6, we see that our
attention modulation algorithm significantly outperforms the original
inference model on every measure – from fluency, quality, and overall
performance.

###  6.4 Vast improvements on few-shot learning

Table 5 presents the results of attention modulation on GPT2-L that are fine-
tuned on different numbers of training examples from CommonGen. We observe the
improvements on all measures are more prominent when the fine-tuning data size
is small. For example, adding attention modulation can improve coverage by
9.43% on the GPT2-L fine-tuned with only 10 examples. This not only validates
that priors we injected into the model are suitable for improving the
downstream task performance, but also shed lights to use attention modulation
on different few-shot learning scenarios where the number of training examples
is limited.

##  7 Related Work

We propose to use attention modulation to heuristically re-balance sentence-
level attention for neural text degeneration. At least three domains of work
are closely related to our proposal, namely, attention pattern analysis, work
that focuses on changing or approximating learned attention patterns, and work
for countering neural text degeneration.

#### Attention analysis:

Previous work has investigated the attention patterns within the local context
of a sentence. These works highlighted that attention patterns in Transformers
implicitly encode syntactic information such as dependency relations (Htut et
al., 2019), and part-of-speech tags (Vig and Belinkov, 2019; Raganato and
Tiedemann, 2018). Other works observed that attention patterns can provide
explanations (Wiegreffe and Pinter, 2019) or coarse word alignments in machine
translation (Zenkel et al., 2019; Kobayashi et al., 2020). In contrast to
these works, we analyze sentence-level attention patterns for neural text
degeneration, and propose to directly modify the attention computation to
reduce it.

#### Alternative attention:

Many works have been proposed to change attention mechanisms to optimize their
O($n^{2}$) complexity. Some promising directions in this space include sparse
attention mechanisms (Beltagy et al., 2020; Zaheer et al., 2020) and
linearized attention (Choromanski et al., 2021). These alternative attention
mechanisms require training the model and are used as replacements to the
original attention mechanism for fast training or reduced computation. Our
work is fundamentally different as we seek to inject priors into the standard
attention mechanism during inference (without re-training the model).

#### Neural text degeneration:

Previous works seek to solve neural text degeneration by changing the training
objective to reduce the likelihood of common tokens (Welleck et al., 2019), or
modifying the decoding algorithm by truncating the sampling distribution
(Holtzman et al., 2018, 2020). Specifically, Welleck et al. (2019) introduce
an additional training loss that reduces the likelihood of common tokens.
Holtzman et al. (2018, 2020) propose stochastic decoding algorithms with
truncation of the sampling distribution. Our work is orthogonal to these
methods by injecting priors into the model’s attention computation during
inference.

##  8 Conclusions and future work

Neural language models often exhibit degeneration: the output texts are
repeated, bland, and inconsistent. Our empirical analyses show that neural
text degeneration may be associated with insufficient learning of task-
specific characteristics by the attention mechanism. We propose a simple but
effective module – attention modulation – that can inject priors for better
generation through re-balancing the attention weights during inference.
Results on three different narrative and commonsense generation tasks indicate
that attention modulation can reduce repetition and enhance commonsense
reasoning while maintaining fluency and coherence.

## Acknowledgements

This research was supported in part by NSF (IIS-1714566), DARPA MCS program
through NIWC Pacific (N66001-19-2-4031), the Canada CIFAR AI Chair program,
the Natural Sciences and Engineering Research Council of Canada (NSERC), Intel
Labs Cognitive Computing Research, and the Allen Institute for AI.
Computations on beaker.org were supported in part by credits from Google
Cloud.

## 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) S. Banerjee and A. Lavie. 2005.  Meteor: An automatic metric for mt evaluation with improved correlation with human judgments.  In _IEEvaluation@ACL_.
  * Beltagy et al. (2020) Iz Beltagy, Matthew E Peters, and Arman Cohan. 2020.  Longformer: The long-document transformer.  _arXiv preprint arXiv:2004.05150_.
  * Bhagavatula et al. (2020) Chandra Bhagavatula, Ronan Le Bras, Chaitanya Malaviya, Keisuke Sakaguchi, Ari Holtzman, Hannah Rashkin, Doug Downey, Wen-tau Yih, and Yejin Choi. 2020.  Abductive commonsense reasoning.  In _International Conference on Learn-ing Representations_.
  * Brown et al. (2020) T. Brown, B. Mann, Nick Ryder, Melanie Subbiah, J. Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, G. Krüger, T. Henighan, R. Child, Aditya Ramesh, D. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, E. Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, J. Clark, Christopher Berner, Sam McCandlish, A. Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems (NeurIPS)_.
  * Choromanski et al. (2021) Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. 2021.  Rethinking attention with performers.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  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 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Holtzman et al. (2020) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020.  The curious case of neural text degeneration.  In _International Conference on Learning Representations_.
  * Holtzman et al. (2018) Ari Holtzman, Jan Buys, Maxwell Forbes, Antoine Bosselut, David Golub, and Yejin Choi. 2018.  Learning to write with cooperative discriminators.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1638–1649, Melbourne, Australia. 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_.
  * Jain and Wallace (2019) Sarthak Jain and Byron C. Wallace. 2019.  Attention is not Explanation.  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 3543–3556, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Khandelwal et al. (2018) Urvashi Khandelwal, He He, Peng Qi, and Dan Jurafsky. 2018.  Sharp nearby, fuzzy far away: How neural language models use context.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 284–294, Melbourne, Australia. Association for Computational Linguistics.
  * Kobayashi et al. (2020) Goro Kobayashi, Tatsuki Kuribayashi, Sho Yokoi, and Kentaro Inui. 2020.  Attention is not only a weight: Analyzing transformers with vector norms.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 7057–7075, 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 _Annual Meeting of the As-sociation for Computational Linguistics (ACL)_.
  * Lu et al. (2020) Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. 2020.  Neurologic decoding:(un) supervised neural text generation with predicate logic constraints.  _arXiv preprint arXiv:2010.12884_.
  * Mao et al. (2019) Huanru Henry Mao, Bodhisattwa Prasad Majumder, Julian McAuley, and Garrison Cottrell. 2019.  Improving neural story generation by targeted common sense grounding.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 5990–5995.
  * 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_ , volume 32, pages 14014–14024. Curran Associates, Inc.
  * Mostafazadeh et al. (2016) Nasrin Mostafazadeh, Nathanael Chambers, Xiaodong He, Devi Parikh, Dhruv Batra, Lucy Vanderwende, Pushmeet Kohli, and James Allen. 2016.  A corpus and cloze evaluation for deeper understanding of commonsense stories.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 839–849, San Diego, California. Association for Computational Linguistics.
  * Papineni et al. (2002) Kishore Papineni, S. Roukos, T. Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Annual Meeting of the As-sociation for Computational Linguistics (ACL)_.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog 1.8_.
  * Raganato and Tiedemann (2018) Alessandro Raganato and Jörg Tiedemann. 2018.  An analysis of encoder representations in transformer-based machine translation.  In _Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 287–297, Brussels, Belgium. Association for Computational Linguistics.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, L. Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems (NeurIPS)_.
  * Vedantam et al. (2015) Ramakrishna Vedantam, C. L. Zitnick, and D. Parikh. 2015.  Cider: Consensus-based image description evaluation.  _2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 4566–4575.
  * Vig and Belinkov (2019) Jesse Vig and Yonatan Belinkov. 2019.  Analyzing the structure of attention in a transformer language model.  In _Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 63–76, Florence, Italy. Association for Computational Linguistics.
  * Welleck et al. (2019) Sean Welleck, Ilia Kulikov, Stephen Roller, Emily Dinan, Kyunghyun Cho, and Jason Weston. 2019.  Neural text generation with unlikelihood training.  In _International Conference on Learning Representations_.
  * Wiegreffe and Pinter (2019) Sarah Wiegreffe and Yuval Pinter. 2019.  Attention is not not explanation.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 11–20, Hong Kong, China. Association for Computational Linguistics.
  * Zaheer et al. (2020) Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. 2020\.  Big bird: Transformers for longer sequences.  In _Advances in Neural Information Processing Systems (NeurIPS)_.
  * Zenkel et al. (2019) Thomas Zenkel, Joern Wuebker, and John DeNero. 2019.  Adding interpretable attention to neural translation models improves word alignment.  _arXiv preprint arXiv:1901.11359_.

##  Appendix A Appendices

Figure 4: Sentence-level attention distribution across different layers in
GPT2-L. The result is aggregated by computing the mean sentence-level
attention from the next generated sentence to the five sentences in the prompt
of ROCStories development set. Lower number represents lower layers in the
Transformer. Figure 5: Attention entropy of each sentence in the prompt
aggregated over the ROCStories dev. set. In the first sentences, there are
particularly high-entropy attention heads that produce bag-of-vector-like
representations.

###  A.1 How does a language model use attention to model a multi-sentence
prompt?

#### Sentence-level attention portion

To reveal which part of context – near or distant history – are important for
context representation, we compute aggregated mean sentence-level attention
(Eqn.5 in the main text) each prompt sentence $p_{i}$ received, while
generating the sentence $g_{1}$ after the prompt. We observe from Figure 4
that GPT2-L mostly attends to the nearest sentence ($p_{5}$) during the
generation. This effect is especially prominent in the early and middle
layers. In the late layers, the attention from different sentences evens out.
This observation is consistent with previous analysis of attention patterns
within sentences such that deeper layers focus on longer-range context (Vig
and Belinkov, 2019).

#### Sentence-level attention entropy

Khandelwal et al. (2018) observed that LSTM represent distant context as
topics; only a few token in the distant context are used to compute the
context representation. We check whether this observation also holds on
Transformer-based models by computing attention entropy. This sentence-level
attention entropy of $p_{i}$ based on the attention from $g_{1}$ to $p_{i}$ at
layer $l_{m}$ over a corpus $X$ is defined as:

$E_{A}(g_{1},p_{i},l_{m})=-\frac{\sum\limits_{x\in X}\sum\limits_{h\in
l_{m}}\sum\limits_{j=1}^{|p_{i}|}\sum\limits_{k=1}^{|g_{1}|}\alpha^{h}_{j,k}\text{log}(\alpha^{h}_{j,k})}{|X|\cdot|H|\cdot|p_{i}|\cdot|g_{1}|}$
(12)

where $h$ is a head in layer $l_{m}$ and $\alpha^{h}_{j,k}$ is the attention
weight from $x_{j}\in p_{i}$ to $x_{k}\in g_{1}$ for $h$. Figure 5 shows a
clear separation of entropy over different sentences in the prompt, where more
distant sentences have lower entropy values. This suggests that LMs only
modelling distant sentences as topics – attention over key words being a
proxy.

| train | dev. | test
---|---|---|---
ROCStories | 39498 | 5269 | 7899
$\alpha$NLG | 169,654 | 1,532 | 3,059
CommonGen | 67,389 | 4,018 | 7,644
Table 7: Dataset Statistics

###  A.2 Hyperparameters

propmt |  attention reweight |  Generated sentence with attention-decoding
---|---|---
field. stand. look. = |  (1,3,2) |  A man stands looking at a sign in a field.
field. stand. look. = |  (1,2,3) |  He looks up and sees a group of people standing in the field.
field. stand. look. = |  (2,3,1) |  He stands in the middle of the field, looking down at the stands.
Table 8:  An example of attention modulation with different attention
reweighting functions on CommonGen dev set. Only by redistributing the
sentence-level attention during inference, we can generate sentences following
the desired order specified in the attention reweighting function.

|  | R-2 | R-L | B-3 | B-4 | Meteor | CIDEr | SPICE | Coverage
---|---|---|---|---|---|---|---|---|---
beam=20 | w/o AttnM | 17.98 | 38.07 | 35.14 | 25.61 | 27.63 | 12.90 | 23.28 | 79.62
w/ AttnM | 18.11 | 39.32 | 36.69 | 26.80 | 28.02 | 13.71 | 23.94 | 81.85
w/ AttnMpm | 19.78 | 41.17 | 38.28 | 28.36 | 30.97 | 15.38 | 28.24 | 91.89

Table 9: Results on CommonGen test set with beam search and permutations
defined in A.3.

Attention modulation can be applied to any layer and any head in the
Transformer based on our implementation. However, the weights learned by
different heads in a particular layer have a large variance (Vig and Belinkov,
2019) and are subject to change from different training sessions. Therefore,
we only reweight attention on all heads in different layers, where what layers
are re-weighted are hyperparameters. We choose to reweight the consecutive
layers from a starting layer $l_{s}$ to an end layer $l_{e}$ and performed a
grid search on different layer ranges. For the start layer, we experimented
with $l_{s}\in\\{0,4,8,12,16,20,24,28,32\\}$; for the end layer, we
experimented with $l_{e}\in\\{4,8,12,16,20,24,28,32,36\\}$. The reweighting
layers are chosen based on the validation set performance. On ROCstories, the
GPT2-L are re-weighted with $l_{s}=8$ and $l_{e}=32$; On $\alpha$NLG, the
GPT2-L are re-weighted with $l_{s}=12$ and $l_{e}=32$; On CommonGen, the
GPT2-L are re-weighted with $l_{s}=24$ and $l_{e}=32$.

###  A.3 Attention modulation and generation order

CommonGen provides the concept set in a random order, where models need to
perform a relational commonsense reasoning to find the optimal order of them
for generating a plausible sentence. We found that attention modulation
provide signals for generation order given different reweighting functions
(examples in Table 8). In this experiment, we guide the generation order by
providing different initialization weights in the reweighting functions. We
enforce different attention modulation weights based on the order we want the
concepts to be generated. For examples, row 1 in table 8 means the concepts of
(field, stand, look) are initialized to be re-weighted by scales of (1,3,2).

This interesting finding motivates us to conduct a permutation experiment on
CommonGen. For a $k$ concept set, we initialize the attention modulation
weights based on the permutations of 1 to $k$ ($k$! permutations in total) and
generate $k$! sentences with attention modulation. We then select the
generation that covers the most concepts999If there is a tie, we choose the
shorter generation. from these $k$! generations as output. We call this method
"attention modulation with permutation". Table 9 presents the results of
attention modulation with permutation. We see that just by enforcing the order
in attention modulation, the coverage can be improved by another 10%.

###  A.4 Human evaluation details

Figure 6 and 7 show the evaluation templates for tuckers for Rocstories and
CommonGen101010omitted $\alpha$NLG template due to space limitation.,
respectively. On ROCstories, the inter-annotator agreements is 0.743 and
fleiss kappa is 0.229 averaged over the five dimensions on $200\times 5$
samples. The inter-annotator agreements are 84.6%, 72.2%, 76.1%, 78.5%, and
59.9% for fluency, interestingness, newness, relevance, and repetition. On
$\alpha$NLG, the human evaluation results are 33%, 14%, 10%, 32%, 11% for
preferring outputs with attention modulation, without attention modulation,
both, neither and no agreement. The inter-annotator agreements is 0.835 and
kappa is 0.439 over 100 samples. On CommonGen, the inter-annotator agreements
are 77.94%, 71.64%, and 67.50% for fluency, quality, and overall on 200
samples.

prompt |  Jen was always afraid of flying. She needed to fly to Japan for an important meeting. Jen took some Dramamine and boarded her plane. Jen dozed off shortly after the plane took off.
---|---
w/o AttnM |  Jen woke up to a huge headache. She had to cancel her trip to Japan. Jen was glad she had taken Dramamine. She was able to fly safely. Jen was glad she had taken Dramamine.
w/ AttnM |  She woke up to a loud bang and felt sick. She had to sit in the back of the plane. She was so scared she couldn’t even get out of her seat. Jen was so embarrassed she never flew again. She was so scared she never flew again.

Table 10:  A generation example (greedy decoding) without and with attention
modulation on ROCStories. Adding attention modulation during inference
improves the commonsense reasoning and consistency of the generation.

prompt |  Neil had been journeying through Asia. But he contracted malaria on a Thai island, and had to be flown home for treatment.
---|---
w/o AttnM |  He was so sick that he couldn’t go to the hospital. He was so sick that he couldn’t go to the hospital. He was so sick that he couldn’t go to the hospital. He was so sick that he couldn’t go to the hospital. He was so sick that he couldn’t go to the hospital.
w/ AttnM |  He was very sick and had to be hospitalized. He was in the hospital for a week. He recovered and was released. Neil was very happy to be home. He was able to get better and was able to go back to his home country.

Table 11: Example (greedy decoding) of the fine-tuned GPT2-L without and with attention modulation on story completion. Adding attention modulation during inference significantly reduces the sentence-level repetition. Figure 6: Mechanical Turk template used to evaluate ROCstories generations. |  propmt |  Generated sentence with attention-decoding
---|---|---
w/o AttnM |  run. team. field. drill. = |  person runs a drill during a practice at training camp.
w/ AttnM. |  run. team. field. drill. = |  person runs a drill during a training session with his team.
w/o AttnM |  use. tool. piece. metal. = |  tool or piece of metal used in manufacturing.
w/ AttnM |  use. tool. piece. metal. = |  piece of metal used to make tools.
Table 12:  Examples produced by GPT2-L without and with attention modulation.
Use attention modulation would have higher concept coverage (details in Table
3 in the main text with 5% coverage improvements on all decoding algorithms we
tested); Figure 7: Mechanical Turk template used to evaluate CommonGen
generations.