# A Lower Bound on the Constant in the Fourier Min-Entropy/Influence
Conjecture

Aniruddha Biswas and Palash Sarkar
Indian Statistical Institute
203, B.T.Road, Kolkata
India 700108.
Email: {anib_r<EMAIL_ADDRESS>
###### Abstract

We describe a new construction of Boolean functions. A specific instance of
our construction provides a 30-variable Boolean function having min-
entropy/influence ratio to be $128/45\approx 2.8444$ which is presently the
highest known value of this ratio that is achieved by any Boolean function.
Correspondingly, $128/45$ is also presently the best known lower bound on the
universal constant of the Fourier min-entropy/influence conjecture.
Keywords: Boolean function, Fourier transform, Walsh transform, Fourier
entropy/influence conjecture, Fourier min-entropy/influence conjecture.

##  1 Introduction

A longstanding open problem in the field of analysis of Boolean functions is
the Fourier Entropy/Influence (FEI) conjecture made by Friedgut and Kalai in
1996 [8]. The FEI conjecture states that there is a universal constant $C$
such that $H(f)\leq C\cdot{\sf Inf}(f)$ for any Boolean function $f$, where
$H(f)$ and ${\sf Inf}(f)$ denote the Fourier entropy and the total influence
of $f$ respectively. The conjecture was verified for various families of
Boolean functions (e.g., symmetric functions [16], read-once formulas [15, 6],
decision trees of constant average depth [21], read-$k$ decision trees for
constant $k$ [21], functions with exponentially small influence or with linear
entropy [19], random linear threshold functions [5], cryptographic Boolean
functions [9], random functions [7]), but is still open for the class of all
Boolean functions.

There has also been research in obtaining lower bounds on the constant $C$ in
the FEI conjecture. To show that $C$ is at least some value $\delta$ it is
sufficient to show the existence of a Boolean function whose entropy/influence
ratio is $\delta$. The first lower bound of $4.615$ was obtained by O’Donnell
et al. in [16]. Later O’Donnell and Tan [15] provided a recursive construction
of Boolean functions which showed how to construct a function for which the
value of the entropy/influence ratio is at least $6.278944$ [11]. The
presently best known lower bound on $C$ is $6.454784$. This bound was shown by
Hod [11] using an extensive asymptotic analysis.

The Fourier min-entropy/influence (FMEI) conjecture was put forward by
O’Donnell et al. in 2011 [16]. The FMEI conjecture states that there is a
universal constant $D$ such that $H_{\infty}(f)\leq D\cdot{\sf Inf}(f)$ for
any Boolean function $f$, where $H_{\infty}(f)$ is the Fourier min-entropy of
$f$. The FMEI conjecture is weaker than the FEI conjecture in the sense that
settling the FEI conjecture will also settle the FMEI conjecture, but the
converse is not true. It was observed in [5, 16] that as a consequence of the
Kahn-Kalai-Linial theorem [12] the FMEI conjecture holds for monotone
functions and linear threshold functions. The FMEI conjecture for “regular”
read-$k$ DNFs was established by Shalev [19]. More recently, Arunachalam et
al. [1] have shown that the FMEI holds for read-$k$ DNF for constant $k$.

To the best of our knowledge, till date there has been no work on obtaining
lower bounds on the universal constant of the FMEI conjecture. Since the FMEI
conjecture is weaker than the FEI conjecture, any upper bound on the universal
constant of the FEI conjecture is also an upper bound on the universal
constant of the FMEI conjecture. This, however, does not hold for lower
bounds, i.e. a lower bound on the universal constant of the FEI conjecture is
not necessarily a lower bound on the universal conjecture of the FMEI
conjecture.

The purpose of the present paper is to obtain a lower bound on the universal
constant $D$ of the FMEI conjecture. As in the case of the FEI conjecture, to
show that $D$ is at least $\delta$, it is sufficient to show the existence of
a Boolean function for which the min-entropy/influence ratio is $\delta$. An
exhaustive search over all $n$-variable Boolean functions, with $1\leq n\leq
5$, shows that the maximum value of min-entropy/influence ratio that is
achieved by functions of at most 5 variables is $16/7\approx 2.285714$. Since
an exhaustive search becomes infeasible for $n\geq 6$, it is required to
obtain some method of constructing Boolean functions for which the min-
entropy/influence ratio is greater than 16/7.

We first considered the recursive construction of O’Donnell and Tan [15],
since this construction proved to be useful for showing a lower bound on the
constant of the FEI conjecture. To analyse this construction in the context of
the FMEI conjecture, we derived an expression for the min-entropy of the
functions obtained using this construction. Since the construction is
recursive, one needs an initial function to start the recursion. We performed
an exhaustive search over all possible 5-variable initial functions. This
yielded a 25-variable function having min-entropy/influence ratio equal to
$512/225\approx 2.275556$. This unfortunately is not useful since 512/225 is
less than 16/7, the maximum value of min-entropy/influence ratio that is
obtained by exhaustive search over all 5-variable functions. The 25-variable
function is obtained in the first step of the O’Donnell-Tan recursion.
Considering further steps of the recursion does not result in a higher value
of the min-entropy/influence ratio. We identified an alternative recursive
construction of Boolean functions which provides a lower bound on the constant
of the FEI conjecture which is equal to that obtained from the O’Donnell-Tan
construction. This alternative construction, however, does not improve upon
the lower bound on the constant of the FMEI conjecture that is obtained from
the O’Donnell-Tan construction. Further, we did not find any way to apply the
asymptotic constructions given by Hod [11] in the context of the FEI
conjecture for obtaining lower bounds on the constant in the FMEI conjecture.

Our main result is a new construction of Boolean functions. In simple terms,
the construction takes an $n$-variable function $g$ and constructs an
$(n+1)$-variable palindromic function $g_{0}$. An $n(n+1)$-variable function
$G_{0}$ is then constructed by taking the disjoint composition of $g_{0}$ and
$g$. Under certain conditions on $g$, the min-entropy/influence ratio of
$G_{0}$ is greater than that of $g$. By searching over all appropriate
5-variable functions $g$, we obtain a 30-variable function $G_{0}$ having min-
entropy/influence ratio to be equal to $128/45\approx 2.844444$. In fact, we
obtain a total of 384 such functions $G_{0}$. The value $128/45$ is presently
the highest achieved value of min-entropy/influence ratio and correspondingly
is presently the best known lower bound on $D$.

In the final section, we provide a brief description of some experiments that
we have carried out for symmetric and rotation-symmetric Boolean functions.
Based on these experiments, we put forward a new conjecture on
entropy/influence and the min-entropy/influence ratios of symmetric Boolean
functions.

In Section 2, we describe the formal background and the notation. The
technique of disjoint composition is required for our construction. In Section
3, we derive an expression for the min-entropy of disjoint composition. The
recursive construction of O’Donnell and Tan [15] and a new recursive
construction is analysed in Section 4 and shown to be not useful for the FMEI
conjecture. Section 5 presents the main construction of the paper and the
description of the Boolean functions achieving the presently best known value
of the min-entropy/influence ratio. In Section 6 we briefly describe our
search experiments with symmetric and rotation-symmetric Boolean functions and
state the new conjecture. Finally, in Section 7 we provide concluding remarks.

##  2 Background and notation

Let $\mathbb{F}_{2}=\\{0,1\\}$ denote the finite field consisting of two
elements with addition represented by $\oplus$ and multiplication by $\cdot$;
often, for $x,y\in\mathbb{F}_{2}$, the product $x\cdot y$ will be written as
$xy$. The field of real numbers will be denoted by $\mathbb{R}$ and all
logarithms are to the base 2.

For a positive integer $n$, by $[n]$ we will denote the set
$\\{1,\ldots,n\\}$. For
$\mathbf{x}=(x_{1},\ldots,x_{n})\in\mathbb{F}_{2}^{n}$, the support of
$\mathbf{x}$ will be denoted by ${\sf supp}(\mathbf{x})$ which is the set
$\\{i:x_{i}=1\\}$; the weight of $\mathbf{x}$ will be denoted by ${\sf
wt}(\mathbf{x})$ and is equal to $\\#{\sf supp}(\mathbf{x})$. For $i\in[n]$,
$\mathbf{e}_{i}$ denotes the vector in $\mathbb{F}_{2}^{n}$ whose $i$-th
component is 1 and all other components are 0. By $\mathbf{1}_{n}$ and
$\mathbf{0}_{n}$ we will denote the all-one and all-zero vectors of length $n$
respectively. For
$\mathbf{x}=(x_{1},\ldots,x_{n}),\mathbf{y}=(y_{1},\ldots,y_{n})\in\mathbb{F}_{2}^{n}$,
the inner product $\langle\mathbf{x},\mathbf{y}\rangle$ of $\mathbf{x}$ and
$\mathbf{y}$ is defined to be
$\langle\mathbf{x},\mathbf{y}\rangle=x_{1}y_{1}\oplus\cdots\oplus x_{n}y_{n}$.

For a positive integer $n$, an $n$-variable Boolean function $f$ is a map
$f:\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}$. Variables will be written in
upper case and vector of variables in bold upper case. For
$\mathbf{X}=(X_{1},\ldots,X_{n})$, an $n$-variable Boolean function $f$ will
be written as $f(\mathbf{X})$ to denote the dependence on the variables
$X_{1},\ldots,X_{n}$.

The support of a Boolean function $f$ will be denoted by ${\sf supp}(f)$ which
is the set $\\{\mathbf{x}:f(\mathbf{x})=1\\}$; the weight of $f$ will be
denoted by ${\sf wt}(f)$ and is equal to $\\#{\sf supp}(f)$. The expectation
of $f$, denoted as $\mathbb{E}(f)$ (taken over a uniform random choice of
$\mathbf{x}\in\mathbb{F}_{2}^{n}$), is equal to ${\sf wt}(f)/2^{n}$. The
function $f$ is said to be balanced if ${\sf wt}(f)=2^{n-1}$.

The Fourier transform of a function
$\psi:\mathbb{F}_{2}^{n}\rightarrow\mathbb{R}$ is the map
$\widehat{\psi}:\mathbb{F}_{2}^{n}\rightarrow\mathbb{R}$, which is defined as
follows. For $\bm{\alpha}\in\mathbb{F}_{2}^{n}$,

$\displaystyle\widehat{\psi}(\bm{\alpha})$ $\displaystyle=$
$\displaystyle\frac{1}{2^{n}}\sum_{\mathbf{x}\in\mathbb{F}_{2}^{n}}\psi(\mathbf{x})(-1)^{\langle\mathbf{x},\bm{\alpha}\rangle}.$
(1)

The (normalised) Walsh transform of an $n$-variable Boolean function $f$ is
the map $W_{f}:\mathbb{F}_{2}^{n}\rightarrow\mathbb{R}$, which is defined as
follows. For $\bm{\alpha}\in\mathbb{F}_{2}^{n}$,

$\displaystyle W_{f}(\bm{\alpha})$ $\displaystyle=$
$\displaystyle\frac{1}{2^{n}}\sum_{\mathbf{x}\in\mathbb{F}_{2}^{n}}(-1)^{f(\mathbf{x})\oplus\langle\mathbf{x},\bm{\alpha}\rangle}$

In other words, the Walsh transform of $f$ is the Fourier transform of
$(-1)^{f}$.

From Parseval’s theorem, it follows that
$\sum_{\bm{\alpha}\in\mathbb{F}_{2}^{n}}W_{f}^{2}(\bm{\alpha})=1$. So the
values
$\left\\{W_{f}^{2}(\bm{\alpha})\right\\}_{\bm{\alpha}\in\mathbb{F}_{2}^{n}}$
can be considered to be a probability distribution on $\mathbb{F}_{2}^{n}$,
which assigns to $\bm{\alpha}\in\mathbb{F}_{2}^{n}$, the probability
$W_{f}^{2}(\bm{\alpha})$. For an $n$-variable Boolean function $f$, its
Fourier entropy $H(f)$ and min-entropy $H_{\infty}(f)$ are defined as follows.

$\displaystyle
H(f)=\sum_{\begin{subarray}{c}\bm{\alpha}\in\mathbb{F}_{2}^{n}\\\
W_{f}^{2}(\bm{\alpha})\neq
0\end{subarray}}W_{f}^{2}(\bm{\alpha})\log\frac{1}{W_{f}^{2}(\bm{\alpha})},$
$\displaystyle
H_{\infty}(f)=\min_{\begin{subarray}{c}\bm{\alpha}\in\mathbb{F}_{2}^{n}\\\
W_{f}^{2}(\bm{\alpha})\neq
0\end{subarray}}\log\frac{1}{W_{f}^{2}(\bm{\alpha})}.$ (2)

For an $n$-variable Boolean function $f$, its influence ${\sf Inf}(f)$ is
defined as follows.

$\displaystyle{\sf Inf}(f)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\Pr_{\mathbf{x}\in\mathbb{F}_{2}^{n}}[f(\mathbf{x})\neq
f(\mathbf{x}\oplus\mathbf{e}_{i})].$ (3)

The connection of influence to the Walsh transform is given by the following
(Theorem 2.38 in [14]).

$\displaystyle{\sf Inf}(f)$ $\displaystyle=$
$\displaystyle\sum_{\bm{\alpha}\in\mathbb{F}_{2}^{n}}{\sf
wt}(\bm{\alpha})W_{f}^{2}(\bm{\alpha}).$ (4)

We next state the two conjectures connecting entropy and influence.

#### The Fourier entropy/influence (FEI) conjecture [8].

There exists a universal constant $C$ such that for any integer $n\geq 1$ and
for any $n$-variable Boolean function $f$, $H(f)\leq C\cdot{\sf Inf}(f)$.

#### The Fourier Min-entropy/influence (FMEI) conjecture [16].

There exists a universal constant $D$ such that for any integer $n\geq 1$ and
for any $n$-variable Boolean function $f$, $H_{\infty}(f)\leq D\cdot{\sf
Inf}(f)$.

Since $H_{\infty}(f)\leq H(f)$, it follows that the FMEI is weaker than the
FEI conjecture in the sense that settling the FEI conjecture will also settle
the FMEI conjecture, but not vice versa.

#### Composition.

For positive integers $n$ and $k$, an $(n,k)$ vectorial Boolean function (also
called an S-box) is a map
$\mathscr{G}:\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}^{k}$. The function
$\mathscr{G}$ can be written as
$\mathscr{G}(\mathbf{X})=(g_{1}(\mathbf{X}),\ldots,g_{k}(\mathbf{X}))$, where
$g_{1},\ldots,g_{k}$ are $n$-variable Boolean functions. Given a $k$-variable
Boolean function $f$ and an $(n,k)$ vectorial Boolean function $\mathscr{G}$,
their composition is the $n$-variable Boolean function
$(f\circ\mathscr{G})(\mathbf{X})=f(g_{1}(\mathbf{X}),\ldots,g_{k}(\mathbf{X}))$.
The Walsh transform of $f\circ\mathscr{G}$ is given by the following result.

######  Theorem 1.

[10] Let $\mathscr{G}$ be an $(n,k)$ vectorial Boolean function and $f$ be a
$k$-variable Boolean function. Then for any $\mathbf{u}\in\mathbb{F}_{2}^{n}$,

$\displaystyle W_{f\circ\mathscr{G}}(\mathbf{u})$
$\displaystyle=\sum_{\mathbf{v}\in\mathbb{F}_{2}^{k}}W_{f}(\mathbf{v})W_{(l_{\mathbf{v}}\circ\mathscr{G})}(\mathbf{u}),$
(5)

where
$(l_{\mathbf{v}}\circ\mathscr{G})(\mathbf{X})=\langle\mathbf{v},\mathscr{G}(\mathbf{X})\rangle$.

Let $k$ and $l$ be positive integers and $n=kl$. For
$\mathbf{x}\in\mathbb{F}_{2}^{n}$ and $1\leq i\leq k$, by $\mathbf{x}^{(i)}$
we denote the vector $(x_{(i-1)l+1},\ldots,x_{il})\in\mathbb{F}_{2}^{l}$. By a
slight abuse of notation, we will write
$\mathbf{x}=(\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(k)})$. Let $f$ and $g$ be
Boolean functions on $k$ and $l$ variables respectively and $n=kl$. Let
$\mathscr{G}$ be the $(n,k)$ vectorial Boolean function given by
$\mathscr{G}(\mathbf{X})=(g(\mathbf{X}^{(1)}),\ldots,g(\mathbf{X}^{(k)}))$.
The disjoint composition of $f$ and $g$, which we will denote as $f\diamond
g$, is the $n$-variable Boolean function $f\circ\mathscr{G}$, i.e.

$\displaystyle(f\diamond g)(\mathbf{X})$ $\displaystyle=$
$\displaystyle(f\circ\mathscr{G})(\mathbf{X})=f(g(\mathbf{X}^{(1)}),\ldots,g(\mathbf{X}^{(k)})).$

The following result provides the entropy and influence of $f\diamond g$.

######  Theorem 2 (simplified form of Proposition $2$ in [15]).

Let $f$ and $g$ be two Boolean functions. Then,

  1. 1.

${\sf Inf}(f\diamond g)={\sf Inf}(g)\cdot{\sf Inf}(f)$.

  2. 2.

If $g$ is balanced, then $H(f\diamond g)=H(f)+H(g)\cdot{\sf Inf}(f)$.

#### O’Donnell-Tan recursive construction.

The following recursive construction of Boolean functions was introduced by
O’Donnell and Tan [15]. Let $g$ be an $l$-variable Boolean function. Using
$g$, a sequence of Boolean functions $f_{m}$, $m\geq 0$, is defined in the
following manner.

$\displaystyle\left.\begin{array}[]{rcll}f_{0}&=&g,\\\ f_{m}&=&g\diamond
f_{m-1}&\mbox{if }m\geq 1.\end{array}\right\\}$ (8)

It is easy to see that for $m\geq 0$, $f_{m}$ is a map from
$\mathbb{F}_{2}^{l^{m+1}}\rightarrow\mathbb{F}_{2}$. For the recursion defined
in (8), in the case where the initial function $g$ is balanced, the following
was proved in [15].

$\displaystyle\frac{H(f_{m})}{{\sf Inf}(f_{m})}$ $\displaystyle=$
$\displaystyle\frac{H(g)}{{\sf Inf}(g)}+\frac{H(g)}{{\sf Inf}(g)({\sf
Inf}(g)-1)}-\frac{H(g)}{{\sf Inf}(g)^{m+1}({\sf Inf}(g)-1)}.$ (9)

Consequently, $\lim_{m\rightarrow\infty}H(f_{m})/{\sf Inf}(f_{m})=H(g)/({\sf
Inf}(g)-1).$ So for any Boolean function $g$, $H(g)/({\sf Inf}(g)-1)$ is a
lower bound on the constant in the FEI conjecture.

##  3 Min-Entropy of disjoint composition

We wish to compute the min-entropy of disjoint composition. We start with the
following result which is somewhat more general than what we need.

######  Theorem 3.

Let $k$ and $l$ be positive integers and $n=kl$. Let $\mathscr{G}$ be an
$(n,k)$ vectorial Boolean function such that
$\mathscr{G}(\mathbf{X})=(g_{1}(\mathbf{X}^{(1)}),\ldots,g_{k}(\mathbf{X}^{(k)}))$,
where $g_{1},\ldots,g_{k}$ are $l$-variable balanced Boolean functions. Then
for any $k$-variable Boolean function $f$,

$\displaystyle\begin{array}[]{l}W_{f\circ\mathscr{G}}(\mathbf{u})=\left\\{\begin{array}[]{ll}W_{f}(\mathbf{0}_{k})&\text{
if $\mathbf{u}=\mathbf{0}_{n}$,}\\\ W_{f}(\mathbf{w_{u}})\prod_{i\in{\sf
supp}({\mathbf{w_{u}}})}W_{g_{i}}\left(\mathbf{u}^{(i)}\right)&\text{
otherwise.}\end{array}\right.\end{array}$ (13)

In (13), for $\mathbf{u}\in\mathbb{F}_{2}^{n}$ written as
$\mathbf{u}=(\mathbf{u}^{(1)},\ldots,\mathbf{u}^{(k)})$, by
$\mathbf{w}_{\mathbf{u}}$ we denote the vector in $\mathbb{F}_{2}^{k}$ whose
$i$-th position, $1\leq i\leq k$, is 1 if and only if
$\mathbf{u}^{(i)}\neq\mathbf{0}_{l}$, i.e. $\mathbf{w}_{\mathbf{u}}$ encodes
whether the $\l$-bit blocks of $\mathbf{u}$ are zero or not.

###### Proof.

The proof follows from an application of Theorem 1.

Note that for $\mathbf{v}=(v_{1},\ldots,v_{k})\in\mathbb{F}_{2}^{k}$,
$(l_{\mathbf{v}}\circ\mathscr{G})(\mathbf{X})=v_{1}\cdot
g_{1}(\mathbf{X}^{(1)})\oplus\cdots\oplus v_{k}\cdot g_{k}(\mathbf{X}^{(k)})$.
So for
$\mathbf{u}=(\mathbf{u}^{(1)},\ldots,\mathbf{u}^{(k)})\in\mathbb{F}_{2}^{n}$,

$\displaystyle W_{(l_{\mathbf{v}}\circ\mathscr{G})}(\mathbf{u})$
$\displaystyle=\frac{1}{2^{n}}\sum_{\mathbf{x}\in\mathbb{F}_{2}^{n}}(-1)^{(l_{\mathbf{v}}\circ\mathscr{G})(\mathbf{x})\oplus\langle\mathbf{u},\mathbf{x}\rangle}$
$\displaystyle=\frac{1}{2^{n}}\sum_{\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(k)}\in\mathbb{F}_{2}^{l}}(-1)^{v_{1}\cdot
g_{1}\left(\mathbf{x}^{(1)}\right)\oplus\langle\mathbf{u}^{(1)},\mathbf{x}^{(1)}\rangle\oplus\cdots\oplus
v_{k}\cdot
g_{k}\left(\mathbf{x}^{(k)}\right)\oplus\langle\mathbf{u}^{(k)},\mathbf{x}^{(k)}\rangle}$
$\displaystyle=\prod_{i\in[k]}\frac{1}{2^{l}}\sum_{\mathbf{x}^{(i)}\in\mathbb{F}_{2}^{l}}(-1)^{v_{i}\cdot
g_{i}\left(\mathbf{x}^{(i)}\right)\oplus\langle\mathbf{u}^{(i)},\mathbf{x}^{(i)}\rangle}.$

For $i\in[k]$, let
$B_{i}\left(v_{i},\mathbf{u}^{(i)}\right)=\frac{1}{2^{l}}\sum_{\mathbf{x}^{(i)}\in\mathbb{F}_{2}^{l}}(-1)^{v_{i}\cdot
g_{i}\left(\mathbf{x}^{(i)}\right)\oplus\langle\mathbf{u}^{(i)},\mathbf{x}^{(i)}\rangle}.$
Using (5) we have,

$W_{f\circ\mathscr{G}}(\mathbf{u})=\sum_{\mathbf{v}\in\mathbb{F}_{2}^{k}}W_{f}(\mathbf{v})W_{(l_{\mathbf{v}}\circ\mathscr{G})}(\mathbf{u})=\sum_{\mathbf{v}\in\mathbb{F}_{2}^{k}}W_{f}(\mathbf{v})\prod_{i\in[k]}B_{i}\left(v_{i},\mathbf{u}^{(i)}\right).$
(14)

Let us now consider $B_{i}\left(v_{i},\mathbf{u}^{(i)}\right)$. Note that
$B_{i}\left(0,\mathbf{u}^{(i)}\right)$ is equal to $1$ or $0$ according as
$\mathbf{u}^{(i)}$ is equal to $\mathbf{0}_{l}$ or not. Further,
$B_{i}\left(1,\mathbf{u}^{(i)}\right)=W_{g_{i}}\left(\mathbf{u}^{(i)}\right)$.
Since it is given that $g_{i}$ is balanced, so
$B_{i}\left(1,\mathbf{0}_{l}\right)=0$.

For $\mathbf{u}\in\mathbb{F}_{2}^{n}$, the $i$-th bit of
$\mathbf{w}_{\mathbf{u}}$ is 1 if and only if the $i$-th block of $\mathbf{u}$
is non-zero. For $\mathbf{v}\in\mathbf{F}_{2}^{k}$ such that
$\mathbf{v}\neq\mathbf{w}_{\mathbf{u}}$, there is a $j\in[k]$ such that either
$v_{j}=0$ and $\mathbf{u}^{(j)}\neq\mathbf{0}_{l}$, or $v_{j}=1$ and
$\mathbf{u}^{(j)}=\mathbf{0}_{l}$; in either case,
$B_{j}\left(v_{j},\mathbf{u}^{(j)}\right)=0$ and so
$\prod_{i\in[k]}B_{i}\left(v_{i},\mathbf{u}^{(i)}\right)=0$. On the other
hand, for $\mathbf{v}=\mathbf{w}_{\mathbf{u}}$, if $v_{i}=0$ then
$\mathbf{u}^{(i)}=\mathbf{0}_{l}$ which implies
$B_{i}\left(v_{i},\mathbf{u}^{(i)}\right)=1$; and if $v_{i}=1$ then
$\mathbf{u}^{(i)}\neq\mathbf{0}_{l}$ which implies
$B_{i}\left(v_{i},\mathbf{u}^{(i)}\right)=W_{g_{i}}\left(\mathbf{u}^{(i)}\right)$;
so $\prod_{i\in[k]}B_{i}\left(v_{i},\mathbf{u}^{(i)}\right)=\prod_{i\in{\sf
supp}(\mathbf{v})}W_{g_{i}}\left(\mathbf{u}^{(i)}\right)$. From this, we get
the required result.

Suppose in Theorem 3, the $g_{i}$’s are all equal, i.e.
$g_{1}=\cdots=g_{k}=g$. Then $f\circ\mathscr{G}=f\diamond g$ and Theorem 3
provides the Walsh transform of disjoint composition in the case where $g$ is
balanced. In this case, the min-entropy is given by the following result.

######  Theorem 4.

Let $k$ and $l$ be positive integers, $f$ be a $k$-variable Boolean function,
and $g$ be an $l$-variable balanced Boolean function. For $0\leq i\leq k$, let
$a_{i}=\max_{\\{\mathbf{w}:{\sf wt}(\mathbf{w})=i\\}}W_{f}^{2}(\mathbf{w})$.
Then

$H_{\infty}(f\diamond g)=\min_{i\in\\{0,\ldots,k\\},\\\
a_{i}>0}(-\log(a_{i})+i\cdot H_{\infty}(g)).$

###### Proof.

Let $n=kl$ and $\mathscr{G}$ be the $(n,k)$ vectorial Boolean function
$\mathscr{G}(\mathbf{X})=(g(\mathbf{X}^{(1)}),\ldots,g(\mathbf{X}^{(k)}))$.
Then $f\diamond g=f\circ\mathscr{G}$ and we can apply Theorem 3 to obtain the
Walsh transform of $f\diamond g$. We have from Theorem 3, $W_{f\diamond
g}(\mathbf{0}_{n})=W_{f}(\mathbf{0}_{k})$, and for
$\mathbf{0}_{n}\neq\mathbf{u}\in\mathbb{F}_{2}^{n}$,

$W_{f\diamond g}(\mathbf{u})=W_{f}(\mathbf{w_{u}})\prod_{j\in{\sf
supp}(\mathbf{w_{u}})}W_{g}\left(\mathbf{u}^{(j)}\right).$

From (2), to obtain the min-entropy of $f\diamond g$, it is required to obtain
$\max_{\mathbf{u}\in\mathbb{F}_{2}^{n}}(W_{f\diamond g}(\mathbf{u}))^{2}$. Let
$\bm{\alpha}_{i}=\operatorname*{arg\,max}_{{\sf
wt}(\mathbf{w})=i}W_{f}^{2}(\mathbf{w})$ for $i\in[k]$ and let
$\bm{\beta}=\operatorname*{arg\,max}_{\mathbf{v}}W_{g}^{2}(\mathbf{v})$
(breaking ties arbitrarily in both cases). Note that
$a_{i}=W_{f}^{2}(\bm{\alpha}_{i})$ and $H_{\infty}(g)=-\log
W_{g}^{2}(\bm{\beta})$. For ${\sf wt}(\mathbf{w}_{\mathbf{u}})=i$, the maximum
value of $\prod_{j\in{\sf
supp}(\mathbf{w_{u}})}W_{g}^{2}\left(\mathbf{u}^{(j)}\right)$ is
$\left(W_{g}^{2}(\bm{\beta})\right)^{i}$. So
$\max_{\mathbf{0}_{n}\neq\mathbf{u}\in\mathbb{F}_{2}^{n}}(W_{f\diamond
g}(\mathbf{u}))^{2}$ is equal to
$\max_{i\in[k]}W_{f}^{2}(\bm{\alpha}_{i})\left(W_{g}^{2}(\bm{\beta})\right)^{i}=\max_{i\in[k]}a_{i}\left(W_{g}^{2}(\bm{\beta})\right)^{i}$.
The result now follows by taking logarithms.

##  4 Recursive constructions

We wish to obtain a Boolean function $f$ such that $H_{\infty}(f)/{\sf
Inf}(f)$ is as high as possible. One way to obtain $f$ is to perform an
exhaustive search. Since the number of $n$-variable Boolean functions is
$2^{2^{n}}$, it is difficult to carry out the search for $n>5$. For $n=5$, we
have performed an exhaustive search. This resulted in 3840 5-variable Boolean
functions for which the min-entropy/influence ratio is $16/7$. All the 3840
functions turned out to be unbalanced. For the purpose of illustration, we
provide one of the 3840 functions that were obtained.

######  Example 1.

Let $h$ be the following 5-variable Boolean function.

$\displaystyle h(X_{5},X_{4},X_{3},X_{2},X_{1})$ $\displaystyle=$
$\displaystyle X_{4}X_{3}\oplus X_{5}X_{2}\oplus X_{5}X_{4}X_{1}\oplus
X_{5}X_{4}X_{2}\oplus X_{5}X_{4}X_{3}.$ (15)

For $h$ defined in (15), $H_{\infty}(h)=4$, ${\sf Inf}(h)=7/4$ and so
$H_{\infty}(h)/{\sf Inf}(h)=16/7$.

The question now is whether it is possible to obtain a function whose min-
entropy/influence ratio is greater than 16/7? In this section, we describe the
approaches based on recursive constructions which did not provide such a
function. In the next section, we describe a method which yields a function
whose min-entropy/influence ratio is greater than that of $h$.

###  4.1 O’Donnell and Tan’s Construction

We first consider the recursive construction of Boolean functions arising from
the O’Donnell-Tan construction since this construction proved to be useful for
the entropy/influence ratio. Using Theorem 4, we obtain the following result
on the min-entropy of the O’Donnell-Tan recursive construction where the
initial function satisfies the condition that there is a vector of weight 1
for which the corresponding Walsh transform value is the maximum.

######  Theorem 5.

Let $g$ be an $l$-variable balanced Boolean function for which there is a
$\bm{\beta}\in\mathbb{F}_{2}^{l}$ with ${\sf wt}(\bm{\beta})=1$ such that
$W_{g}^{2}(\bm{\beta})=\max_{\mathbf{v}}W_{g}^{2}(\mathbf{v})$. For $m\geq 0$,
let $f_{m}$ be the Boolean function constructed using (8) with $f_{0}=g$. Then
for $m\geq 0$,

$\displaystyle H_{\infty}(f_{m})$ $\displaystyle=$ $\displaystyle(m+1)\cdot
H_{\infty}(g).$ (16)

Consequently,

$\frac{H_{\infty}(f_{m})}{{\sf Inf}(f_{m})}=\left(\frac{H_{\infty}(g)}{{\sf
Inf}(g)}\right)\left(\frac{m+1}{{\sf Inf}(g)^{m}}\right).$ (17)

###### Proof.

Note that $H_{\infty}(g)=-\log(W_{g}^{2}(\bm{\beta}))$. Further, since $g$ is
balanced, using Theorem 3, it follows that $f_{m}$ is balanced for all $m\geq
1$.

We prove (16) by induction on $m$. For $m=0$, this follows from the given
condition on $g$. Suppose (16) holds for some $m\geq 0$. From Theorem 4 and
the fact that $f_{m+1}$ is balanced, $H_{\infty}(f_{m+1})=H_{\infty}(g\diamond
f_{m})=\min_{i\in[l],a_{i}>0}(-\log(a_{i})+i\cdot H_{\infty}(f_{m}))$, where
$a_{i}=\max_{{\sf wt}(\mathbf{w})=i}W_{g}^{2}(\mathbf{w})$ for $i=1,\ldots,l$.
For any $i\in[l]$, we have $-\log(a_{i})+i\cdot
H_{\infty}(f_{m})\geq-\log(W_{g}^{2}(\bm{\beta}))+H_{\infty}(f_{m})=H_{\infty}(g)+H_{\infty}(f_{m})$
and since $\bm{\beta}$ has weight 1, equality is attained for $i=1$. So using
the induction hypothesis,
$H_{\infty}(f_{m+1})=\min_{i\in[l],a_{i}>0}(-\log(a_{i})+i\cdot
H_{\infty}(f_{m}))=H_{\infty}(g)+H_{\infty}(f_{m})=(m+2)H_{\infty}(g)$.

The proof of (17) follows from (16) and Theorem 2.

To use Theorem 5 as an amplifier of min-entropy/influence ratio it is required
to obtain $m\geq 1$ such that $H_{\infty}(f_{m})/{\sf
Inf}(f_{m})>H_{\infty}(g)/{\sf Inf}(g)$ which holds if and only if ${\sf
Inf}(g)<(m+1)^{1/m}$. For $m=1$, this condition becomes ${\sf Inf}(g)<2$ and
for higher values of $m$, the upper bound on ${\sf Inf}(g)$ is lower.
Comparing (9) with (17), we see that unlike the case of the entropy/influence
ratio, increasing $m$ does not necessarily lead to a higher value of the min-
entropy/influence ratio. In particular, the nice asymptotic analyses [15, 11]
which has been done for the entropy/influence ratio is not applicable to the
min-entropy/influence ratio.

To apply Theorem 5, we need an appropriate initial function $g$. We performed
an exhaustive search over all possible 5-variable Boolean functions which
satisfy the conditions of Theorem 5. For $m=1$, we obtained 384 functions such
that taking $f_{0}$ to be any of these functions leads to a 25-variable
Boolean function $f_{1}$ with $H_{\infty}(f_{1})/{\sf
Inf}(f_{1})=512/225\approx 2.275556$. Let $\mathcal{F}_{5}$ denote the set of
these 384 functions. As an example, we provide one element of
$\mathcal{F}_{5}$.

######  Example 2.

Let $g$ be the following 5-variable Boolean function.

$\displaystyle g(X_{5},X_{4},X_{3},X_{2},X_{1})$ (18) $\displaystyle=$
$\displaystyle X_{3}X_{2}X_{1}\oplus X_{4}\oplus X_{4}X_{1}\oplus
X_{4}X_{2}\oplus X_{4}X_{2}X_{1}\oplus X_{4}X_{3}X_{1}\oplus X_{4}X_{3}X_{2}$
$\displaystyle\quad\oplus X_{5}\oplus X_{5}X_{1}\oplus X_{5}X_{2}X_{1}\oplus
X_{5}X_{3}\oplus X_{5}X_{3}X_{1}\oplus X_{5}X_{3}X_{2}\oplus X_{5}X_{4}$
$\displaystyle\quad\oplus X_{5}X_{4}X_{1}\oplus X_{5}X_{4}X_{2}\oplus
X_{5}X_{4}X_{3}.$

The function $g$ defined in (18) is in $\mathcal{F}_{5}$. For $g$,
$H_{\infty}(g)=4$, ${\sf Inf}(g)=15/8$. Taking $f_{0}=g$ and
$f_{1}=f_{0}\diamond f_{0}$, from Theorem 5 we have $H_{\infty}(f_{1})/{\sf
Inf}(f_{1})=32/15\times 2/(15/8)=512/225$.

We note the following points.

  1. 1.

The 25-variable function $f_{1}$ obtained using the above method is not
useful. The 5-variable function $h$ given in (15) obtained using exhaustive
search has a higher value of the min-entropy/influence ratio.

  2. 2.

In our search over all 5-variable Boolean functions, considering $m>1$ did not
provide a result better than that obtained for $m=1$.

  3. 3.

In Theorem 5, the condition ${\sf wt}(\bm{\beta})=1$ is required to obtain the
expression for $f_{m}$ given by (16). Considering ${\sf wt}(\bm{\beta})>1$, on
the other hand, does not seem to lead to a higher value of the min-
entropy/influence ratio.

###  4.2 A different recursion

Let $g$ be an $l$-variable Boolean function. We define a sequence
$\\{g_{m}\\}_{m\geq 0}$ of Boolean functions as follows.

$\displaystyle\left.\begin{array}[]{rcll}g_{0}&=&g,\\\ g_{m}&=&g_{m-1}\diamond
g_{m-1}&\mbox{if }m\geq 1.\end{array}\right\\}$ (21)

For $m\geq 0$, $g_{m}$ is a map from $\mathbb{F}_{2}^{l^{2^{m}}}$ to
$\mathbb{F}_{2}$. If we start (8) and (21) with the same initial function $g$,
then we obtain $f_{1}=g_{1}$, but for $m>1$, the two sequences are different.
More generally, the sequence defined using (21) is not a sub-sequence of the
sequence defined using (8).

Suppose $g$ is a balanced function. Using Theorem 2, it is possible to show
that $H(g_{m})=H(g)(1+{\sf Inf}(g_{0}))(1+{\sf Inf}(g_{1}))\ldots(1+{\sf
Inf}(g_{m-1}))$ and ${\sf Inf}(g_{m})={\sf Inf}(g){\sf Inf}(g_{0}){\sf
Inf}(g_{1})\ldots{\sf Inf}(g_{m-1})={\sf Inf}(g)^{2^{m}}$. From this it is
possible to show that $H(g_{m})/{\sf Inf}(g_{m})=(H(g)/({\sf
Inf}(g)-1))\cdot(1-1/{\sf Inf}(g)^{m})$. So as $m\rightarrow\infty$,
$H(g_{m})/{\sf Inf}(g_{m})$ goes to $H(g)/({\sf Inf}(g)-1)$ which is the same
limit as that obtained from the O’Donnell-Tan recursion. So the recursion
given by (21) provides a different way of achieving the same limit for the
entropy/influence ratio as that obtained using the O’Donnell-Tan recursion.

Suppose $g$ is such that $W_{g}^{2}(\mathbf{v})$ is maximum for some
$\mathbf{v}$ of weight 1. Let $\\{g_{m}\\}_{m\geq 0}$ be the sequence defined
in (21) with $g_{0}=g$. Then in a manner similar to the proof of Theorem 5 it
can be shown that $H_{\infty}(g_{m})=2^{m}\cdot H_{\infty}(g)$. So
$H_{\infty}(g_{m})/{\sf Inf}(g_{m})=(H(g)/{\sf Inf}(g))\cdot(2^{m}/{\sf
Inf}(g)^{2^{m}-1})$. For $m=1$, this is the same as the O’Donnell-Tan
construction and for $m>1$, it does not lead to any improvement over the
O’Donnell-Tan construction. So for the min-entropy/influence ratio, the new
recursion does not provide anything better than the O’Donnell-tan
construction.

##  5 Construction from palindromic functions

An $n$-variable Boolean function $g$ can be represented by a bit string of
length $2^{n}$ in the following manner: for $i\in\\{0,\ldots,2^{n}-1\\}$, the
$i$-th bit of the string is $g(\bm{\alpha})$, where $\bm{\alpha}$ is the
$n$-bit binary representation of $i$. We will denote the bit string
representing $g$ also by $g$. The reverse of the bit string representation of
$g$ is $g^{r}$, and $g^{r}$ is given by $g^{r}(X_{n},\ldots,X_{1})=g(1\oplus
X_{n},\ldots,1\oplus X_{1})$. The following simple result relates the Walsh
transforms of $g$ and $g^{r}$.

######  Proposition 1.

Let $g$ be an $n$-variable Boolean function and $g^{r}$ be another
$n$-variable Boolean function defined as $g^{r}(X_{n},\ldots,X_{1})=g(1\oplus
X_{n},\ldots,1\oplus X_{1})$. Then for $\bm{\alpha}\in\mathbb{F}_{2}^{n}$,
$W_{g^{r}}(\bm{\alpha})=(-1)^{{\sf wt}(\bm{\alpha})}W_{g}(\bm{\alpha})$.

Given an $n$-variable Boolean function $g$, we may construct an
$(n+1)$-variable Boolean $f$ function in the following manner. Concatenate the
bit string representing $g$ and $g^{r}$ to obtain a bit string of length
$2^{n+1}$. This string represents the desired $(n+1)$-variable Boolean
function $f$. The bit string representing $f$ is a palindrome and we call $f$
to be a palindromic function. The following construction is a little more
general than the method just described. For $b\in\mathbb{F}_{2}$, let

$\displaystyle g_{b}(X_{n+1},X_{n},\ldots,X_{1})$ $\displaystyle=$
$\displaystyle(1\oplus X_{n+1})g(X_{n},\ldots,X_{1})\oplus X_{n+1}(b+g(1\oplus
X_{n},\ldots,1\oplus X_{1})).$ (22)

If $b=0$, then $f_{0}$ is the concatenation of $g$ and $g^{r}$ as described
above, and if $b=1$, then $f_{1}$ is the concatenation of $g$ and the
complement of $g^{r}$. The following result shows the relation between the
relevant properties of $g$ and $g_{b}$.

######  Proposition 2.

Let $g$ be an $n$-variable Boolean function and $b\in\mathbb{F}_{2}$. Let
$g_{b}$ be the $(n+1)$-variable Boolean function constructed from $g$ and $b$
using (22). Then the following holds.

  1. 1.

For $\bm{\beta}\in\mathbb{F}_{2}^{n+1}$, where $\bm{\beta}=(a,\bm{\alpha})$,
with $a\in\mathbb{F}_{2}$ and $\bm{\alpha}\in\mathbb{F}_{2}^{n}$,

$\displaystyle W_{g_{b}}(\bm{\beta})$ $\displaystyle=$
$\displaystyle\left(\frac{(1+(-1)^{b+{\sf
wt}(\bm{\beta})})}{2}\right)W_{g}(\bm{\alpha}).$ (23)

  2. 2.

$H_{\infty}(g_{b})=H_{\infty}(g)$.

  3. 3.

${\sf Inf}(g_{b})={\sf Inf}(g)+\epsilon_{b}(g)$, where
$\displaystyle\epsilon_{b}(g)=\sum_{\begin{subarray}{c}\bm{\alpha}\in\mathbb{F}_{2}^{n}\\\
{\sf wt}(\bm{\alpha})\not\equiv b\bmod
2\end{subarray}}W_{g}^{2}(\bm{\alpha})$.

###### Proof.

By definition

$\displaystyle W_{g_{b}}(\bm{\beta})$ $\displaystyle=$
$\displaystyle\frac{1}{2^{n+1}}\sum_{\mathbf{x}\in\mathbb{F}_{2}^{n+1}}(-1)^{g_{b}(\mathbf{x})\oplus\langle\bm{\beta},\mathbf{x}\rangle}.$
(24)

We simplify the exponent in the sum.

$\displaystyle
g_{b}(x_{n+1},x_{n},\ldots,x_{1})\oplus\langle(a,\bm{\alpha}),(x_{n+1},x_{n},\ldots,x_{1})\rangle$
(27) $\displaystyle=$ $\displaystyle(1\oplus
x_{n+1})g(x_{n},\ldots,x_{1})\oplus x_{n+1}(b\oplus g(1\oplus
x_{n},\ldots,1\oplus
x_{1}))\oplus\langle(a,\bm{\alpha}),(x_{n+1},x_{n},\ldots,x_{1})\rangle$
$\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}g(x_{n},\ldots,x_{1})\oplus\langle\bm{\alpha},(x_{n},\ldots,x_{1})\rangle&\mbox{if
}x_{n+1}=0,\\\ b\oplus g(1\oplus x_{n},\ldots,1\oplus x_{1})\oplus
a\oplus\langle\bm{\alpha},(x_{n},\ldots,x_{1})\rangle&\mbox{if
}x_{n+1}=1.\end{array}\right.$

Writing $\mathbf{x}=(x_{n+1},\mathbf{y})$, where $x_{n+1}\in\mathbb{F}_{2}$
and $\mathbf{y}\in\mathbb{F}_{2}^{n}$, we simplify (24) using (27) as follows.

$\displaystyle W_{g_{b}}(\bm{\beta})$ $\displaystyle=$
$\displaystyle\frac{1}{2^{n+1}}\left(\sum_{\mathbf{y}\in\mathbb{F}_{2}^{n}}(-1)^{g(\mathbf{y})\oplus\langle\bm{\alpha},\mathbf{y}\rangle}+(-1)^{a\oplus
b}\sum_{\mathbf{y}\in\mathbb{F}_{2}^{n}}(-1)^{g(\mathbf{1}_{n}\oplus\mathbf{y})\oplus\langle\bm{\alpha},\mathbf{y}\rangle}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2}\left(W_{g}(\bm{\alpha})+(-1)^{a\oplus
b}W_{g^{r}}(\bm{\alpha})\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left(W_{g}(\bm{\alpha})+(-1)^{a\oplus b}(-1)^{{\sf
wt}(\bm{\alpha})}W_{g}(\bm{\alpha})\right)\quad\mbox{(using
Proposition~{}\ref{prop-rev})}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left(W_{g}(\bm{\alpha})+(-1)^{b}(-1)^{{\sf
wt}(a,\bm{\alpha})}W_{g}(\bm{\alpha})\right).$

This proves the first point. The second point follows directly from the first.

For the third point, we use (4) to compute the influence of $g_{b}$ from its
Walsh transform.

$\displaystyle{\sf Inf}(g_{b})$ $\displaystyle=$
$\displaystyle\sum_{a\in\mathbb{F}_{2},\bm{\alpha}\in\mathbb{F}_{2}^{n}}{\sf
wt}(a,\bm{\alpha})W_{g_{b}}^{2}(a,\bm{\alpha})$ $\displaystyle=$
$\displaystyle\sum_{a\in\mathbb{F}_{2},\bm{\alpha}\in\mathbb{F}_{2}^{n}}{\sf
wt}(a,\bm{\alpha})\left(\frac{(1+(-1)^{b+{\sf
wt}(a,\bm{\alpha})})}{2}\right)^{2}W_{g}^{2}(\bm{\alpha})$ $\displaystyle=$
$\displaystyle\sum_{\bm{\alpha}\in\mathbb{F}_{2}^{n}}{\sf
wt}(\bm{\alpha})\left(\frac{(1+(-1)^{b+{\sf
wt}(\bm{\alpha})})}{2}\right)^{2}W_{g}^{2}(\bm{\alpha})$
$\displaystyle+\quad\quad\sum_{\bm{\alpha}\in\mathbb{F}_{2}^{n}}(1+{\sf
wt}(\bm{\alpha}))\left(\frac{(1-(-1)^{b+{\sf
wt}(\bm{\alpha})})}{2}\right)^{2}W_{g}^{2}(\bm{\alpha})$ $\displaystyle=$
$\displaystyle\sum_{\bm{\alpha}\in\mathbb{F}_{2}^{n},{\sf
wt}(\bm{\alpha})\equiv b\bmod 2}{\sf wt}(\bm{\alpha})W_{g}^{2}(\bm{\alpha})$
$\displaystyle+\quad\quad\sum_{\bm{\alpha}\in\mathbb{F}_{2}^{n},{\sf
wt}(\bm{\alpha})\not\equiv b\bmod 2}(1+{\sf
wt}(\bm{\alpha}))W_{g}^{2}(\bm{\alpha})$ $\displaystyle=$ $\displaystyle{\sf
Inf}(g)+\epsilon_{b}(g).$

We note the following two points.

  1. 1.

The Walsh transform of $g_{b}$ is banded, i.e. it is zero for all vectors of
weights congruent to $1-b$ modulo two.

  2. 2.

From Parseval’s theorem it follows that $0\leq\epsilon_{b}(g)\leq 1$.

We recall two well known classes of Boolean function. See [3] for an extensive
discussion on the various properties of these classes. Let $f$ be an
$n$-variable Boolean function.

  * •

$f$ is said to be $t$-resilient, $0\leq t<n$, if $W_{f}(\bm{\alpha})=0$ for
all $\bm{\alpha}$ with ${\sf wt}(\bm{\alpha})\leq t$.

  * •

$f$ is said to be plateaued, if $W_{f}(\bm{\alpha})$ takes the values $0,\pm
c$, for some $c$.

From (4), it follows that if $f$ is $t$-resilient, then ${\sf Inf}(f)\geq
t+1$.

Next we present the main result of the paper.

######  Theorem 6.

Let $g$ be a balanced $n$-variable Boolean function, $b\in\mathbb{F}_{2}$ and
$g_{b}$ be constructed from $g$ and $b$ as in (22). Let $G_{b}=g_{b}\diamond
g$. Then

$\displaystyle\frac{H_{\infty}(G_{b})}{{\sf Inf}(G_{b})}$ $\displaystyle=$
$\displaystyle\frac{\min_{i\in\\{0,\ldots,k\\},a_{i}>0}(-\log(a_{i})+iH_{\infty}(g))}{{\sf
Inf}(g)({\sf Inf}(g)+\epsilon_{b}(g))},$ (28)

where $a_{i}=\max_{\\{\mathbf{w}:{\sf
wt}(\mathbf{w})=i\\}}W_{g_{b}}^{2}(\mathbf{w})$, $i=0,\ldots,k$.

Further, suppose that there is a $t\geq 0$ such that $t\equiv b\bmod 2$ and
$g$ is a plateaued $t$-resilient function, which is not $(t+1)$-resilient.
Then

$\displaystyle\frac{H_{\infty}(G_{b})}{{\sf Inf}(G_{b})}$ $\displaystyle=$
$\displaystyle\frac{H_{\infty}(g)}{{\sf Inf}(g)}\left(\frac{t+3}{{\sf
Inf}(g)+\epsilon_{b}(g)}\right).$ (29)

###### Proof.

Proposition 2 provides the expression for ${\sf Inf}(g_{b})$ and Theorem 2
provides the expression for ${\sf Inf}(G_{b})$. The expression for
$H_{\infty}(G_{b})$ is obtained from Theorem 4. This shows (28).

Now suppose $g$ is a $t$-resilient plateaued function such that $t\equiv
b\bmod 2$. Since $g$ is plateaued, from (23), it follows that $g_{b}$ is also
plateaued and for $a_{i}>0$, $-\log(a_{i})=H_{\infty}(g)$. From the conditions
$g$ is $t$-resilient and $t\equiv b\bmod 2$, it follows that $g_{b}$ is
$(t+1)$-resilient. To see this, suppose $\bm{\beta}\in\mathbb{F}_{2}^{n+1}$
with ${\sf wt}(\bm{\beta})\leq t+1$. If ${\sf wt}(\bm{\beta})=t+1$, then since
$t\equiv b\bmod 2$, we have $1+(-1)^{b+{\sf wt}(\bm{\beta})}=0$ and so
$W_{g_{b}}(\bm{\beta})=0$; on the other hand, if ${\sf wt}(\bm{\beta})<t+1$,
then writing $\bm{\beta}=(a,\bm{\alpha})$ with $a\in\mathbb{F}_{2}$ and
$\bm{\alpha}\in\mathbb{F}_{2}^{n}$, and using the fact that $g$ is
$t$-resilient, it follows that ${\sf wt}(\bm{\alpha})\leq t$ and so
$W_{g}(\bm{\alpha})=0$ which implies that $W_{g_{b}}(\bm{\beta})=0$. Further,
since $g$ is not $(t+1)$-resilient, it follows that $g_{b}$ is not
$(t+2)$-resilient. Since $g_{b}$ is $(t+1)$-resilient, but not
$(t+2)$-resilient, it follows that the minimum value of $i$ such that
$a_{i}>0$ is $t+2$. Now using the fact that for $a_{i}>0$,
$-\log(a_{i})=H_{\infty}(g)$, we have
$\min_{i\in\\{0,\ldots,k\\},a_{i}>0}(-\log(a_{i})+iH_{\infty}(g))\geq
H_{\infty}(g)+(t+2)H_{\infty}(g)=(t+3)H_{\infty}(g)$. This shows (29).

###  5.1 Construction of a 30-variable Boolean function

By construction, if $g$ is an $n$-variable Boolean function, then the function
$G_{b}$ in Theorem 6 is an $n(n+1)$-variable Boolean function. To use Theorem
6 as an amplifier of min-entropy/influence ratio, it is required to have
$H_{\infty}(G_{b})/{\sf Inf}(G_{b})>H_{\infty}(g)/{\sf Inf}(g)$. If $g$ is a
plateaued $t$-resilient function, then the last condition holds if and only if
$t+3\geq{\sf Inf}(g)+\epsilon_{b}(g)$. Note, however, that ${\sf Inf}(g)\geq
t+1$ and so the condition $t+3\geq{\sf Inf}(g)+\epsilon_{b}(g)$ offers only a
limited scope for amplification of the min-entropy/influence ratio.

If $g$ is balanced, but not 1-resilient, i.e. $t=0$, then the amplification
factor in Theorem 6 is $3/({\sf Inf}(g)+\epsilon_{b}(g))$. We compare this
condition with the amplification factor for $m=1$ arising from the O’Donnell-
Tan construction. From Theorem 5, the amplification factor in the O’Donnell-
Tan construction is $2/{\sf Inf}(g)$. So if we use the same $g$ in both
Theorems 5 and 6, then the amplification provided by Theorem 6 is greater if
and only if ${\sf Inf}(g)>2\epsilon_{b}(g)$. The last condition holds for all
$g\in\mathcal{F}_{5}$ (for the definition of $\mathcal{F}_{5}$ see the
discussion before Example 2). So if we take any of the functions in
$\mathcal{F}_{5}$ as the initial function and apply Theorem 6, we will obtain
a function whose min-entropy/influence ratio is greater than what can be
obtained by starting with the same initial function and using one step of the
O’Donnell-Tan construction.

As a concrete example, we consider the 5-variable function $g$ given in
Example 2. Using this $g$ and taking $b=0$, from (22), we obtain a 6-variable
function $g_{0}$. The function $G_{0}=g_{0}\diamond g$ is a 30-variable
function. From Theorem 6, we have $H_{\infty}(G_{0})/{\sf
Inf}(G_{0})=128/45\approx 2.8444$. Starting with any of the 384 functions in
$\mathcal{F}_{5}$ and applying Theorem 6, we obtain a corresponding
30-variable function for which the min-entropy/influence ratio is also 128/45.
This gives us a set of 384 30-variable functions each of which has min-
entropy/influence ratio to be 128/45. Note that 128/45 is greater than 16/7,
which is the maximum min-entropy/influence ratio that is achieved by any
5-variable function (see Example 1 and the discussion preceeding it).
Presently, 128/45 is the highest known value of min-entropy/influence ratio
that has been achieved. Correspondingly, 128/45 is also the best known lower
bound on the universal constant of the min-entropy/influence conjecture.

##  6 Some further search results

A Boolean function $f$ is said to be symmetric if it is invariant under any
permutation of its input. The number of $n$-variable symmetric Boolean
functions is $2^{n+1}$. O’Donnell et al. [16] established the FEI conjecture
for symmetric Boolean functions which also settles the FMEI conjecture for
this class of functions. Their proof showed that the entropy/influence ratio
of any symmetric Boolean function is at most 12.04. We used exhaustive search
to find the actual value of the ratio for symmetric functions on $n$ variables
with $n\leq 16$.

For $n\geq 2$, let $A_{n}(X_{1},\ldots,X_{n})=X_{1}\cdots X_{n}$ (in terms of
Boolean algebra $A_{n}$ is the AND function). It is easy to show (see [11])
that $H(A_{n})/{\sf Inf}(A_{n})<4$. Our search for $n\leq 16$ showed that if
$f$ is an $n$-variable symmetric Boolean function, then $H(f)/{\sf Inf}(f)\leq
H(A_{n})/{\sf Inf}(A_{n})$. This suggests that the ratio 12.04 that was
achieved in the proof of [16] is perhaps not the minimum possible value of the
entropy/influence ratio for symmetric functions.

A Boolean function $f$ is said to be bent [17] if all the Walsh transform
values of $f$ are equal. Such functions can exist only if $n$ is even. If $f$
is bent, then $H(f)=H_{\infty}(f)=n$. Further, ${\sf Inf}(f)=n/2$ (see [2]).
So for a bent function $f$, $H(f)/{\sf Inf}(f)=H_{\infty}(f)/{\sf Inf}(f)=2$.
Symmetric functions can be bent and the class of symmetric bent functions have
been characterised [18, 13]. Our search showed that if $n$ is even, then for
any $n$-variable symmetric Boolean function $f$, $H_{\infty}(f)/{\sf
Inf}(f)\leq 2$ and equality is achieved if and only if $f$ is bent; on the
other hand, if $n$ is odd, then for any $n$-variable symmetric Boolean
function $f$, $H_{\infty}(f)/{\sf Inf}(f)<2$.

Based on our observations, we put forth the following conjecture.

######  Conjecture 1.

Let $f$ be an $n$-variable symmetric Boolean function. Then

  1. 1.

$H(f)/{\sf Inf}(f)\leq H(A_{n})/{\sf Inf}(A_{n})$ and equality is achieved if
and only if $f$ equals $A_{n}$.

  2. 2.

If $n$ is even, then $H_{\infty}(f)/{\sf Inf}(f)\leq 2$ and equality is
achieved if and only if $f$ is bent; if $n$ is odd, then $H_{\infty}(f)/{\sf
Inf}(f)<2$

A closed form expression for the Walsh transform of symmetric Boolean function
in terms of binomial coefficients is known [4]. We could not, however, find a
way to use this expression to settle the above conjecture. We also tried to
apply the techniques from [16] used for showing that the FEI conjecture holds
for symmetric Boolean functions to settle Conjecture 1 but were not
successful. The main problem is that the various inequalities used in the
proof of [16] do not seem to be sufficiently sharp to establish the bounds
stated in the above conjecture. As mentioned above, Conjecture 1 has been
verified for $1\leq n\leq 16$. It is possible to experimentally verify the
conjecture for additional values of $n$, but this is unlikely to provide any
insight into how to settle the conjecture.

A Boolean function is said to be rotation symmetric if it is invariant under a
cyclic shift of its input. It is not known whether the FEI (or the FMEI)
conjecture holds for rotation symmetric Boolean functions. See [20] for the
number of rotation symmetric Boolean functions on $n$ variables. We could
perform an exhaustive search on rotation symmetric Boolean functions for
$n\leq 7$. For $n=6$ and $n=7$, the maximum values of $H(f)/{\sf Inf}(f)$ are
3.739764 and 3.804357 respectively; and the maximum values of
$H_{\infty}(f)/{\sf Inf}(f)$ are 2.168978 and 2.227449 respectively, where the
maximums are over all $n$-variable rotation symmetric Boolean function.
Compared to symmetric Boolean functions, we see that the maximum value of the
entropy/influence ratio remains below 4, but the maximum value of the min-
entropy/influence ratio is greater than 2. Since we could not run the
experiment for higher values of $n$, we are unable to put forward any
conjecture for rotation symmetric Boolean functions.

##  7 Concluding remarks

Our work has opened the interesting topic of obtaining lower bounds on the
universal constant of the FMEI conjecture. We have provided one method of
constructing Boolean functions which provides the presently best known lower
bound. A future challenge is to obtain other construction methods which yield
functions with a higher value of the min-entropy/influence ratio. It is also
interesting to look for sufficiently sharp techniques to settle Conjecture 1.
A final open problem resulting from our work is to settle the FEI conjecture
for rotation symmetric Boolean functions.

## References

  * [1] Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald de Wolf.  Improved bounds on Fourier entropy and min-entropy.  ACM Trans. Comput. Theory, 13(4):22:1–22:40, 2021.
  * [2] Aniruddha Biswas and Palash Sarkar.  Separation results for boolean function classes.  Cryptogr. Commun., 13(3):451–458, 2021.
  * [3] Claude Carlet.  Boolean Functions for Cryptography and Coding Theory.  Cambridge University Press, January 2021.
  * [4] Francis N. Castro, Luis A. Medina, and Pantelimon Stanica.  Generalized walsh transforms of symmetric and rotation symmetric boolean functions are linear recurrent.  Appl. Algebra Eng. Commun. Comput., 29(5):433–453, 2018.
  * [5] Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu, Satyanarayana V. Lokam, and Nitin Saurabh.  Fourier entropy-influence conjecture for random linear threshold functions.  In Michael A. Bender, Martin Farach-Colton, and Miguel A. Mosteiro, editors, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings, volume 10807 of Lecture Notes in Computer Science, pages 275–289. Springer, 2018\.
  * [6] Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V Lokam, and Nitin Saurabh.  Upper bounds on Fourier entropy.  Theoretical Computer Science, 654:92–112, 2016.
  * [7] Bireswar Das, Manjish Pal, and Vijay Visavaliya.  The entropy influence conjecture revisited.  arXiv preprint arXiv:1110.4301, 2011.
  * [8] Ehud Friedgut and Gil Kalai.  Every monotone graph property has a sharp threshold.  Proceedings of the American mathematical Society, 124(10):2993–3002, 1996.
  * [9] Sugata Gangopadhyay and Pantelimon Stănică.  Fourier Entropy-Influence Conjecture for Cryptographic Boolean Functions.  Special issue on Advances in Cryptology and Information Security in Transactions on Advanced Research, 12(2):8–14, 2016.
  * [10] Kishan Chand Gupta and Palash Sarkar.  Toward a general correlation theorem.  IEEE Trans. Inf. Theory, 51(9):3297–3302, 2005.
  * [11] Rani Hod.  Improved lower bounds for the Fourier entropy/influence conjecture via lexicographic functions.  arXiv preprint arXiv:1711.00762, 2017.
  * [12] Jeff Kahn, Gil Kalai, and Nathan Linial.  The influence of variables on boolean functions (extended abstract).  In 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988, pages 68–80. IEEE Computer Society, 1988.
  * [13] Subhamoy Maitra and Palash Sarkar.  Characterization of symmetric bent functions – an elementary proof.  Journal of Combinatorial Mathematics and Combinatorial Computing, 43:227–230, 2002.
  * [14] Ryan O’Donnell.  Analysis of Boolean Functions.  Cambridge University Press, 2014.
  * [15] Ryan O’Donnell and Li-Yang Tan.  A composition theorem for the Fourier entropy-influence conjecture.  In International Colloquium on Automata, Languages, and Programming, pages 780–791. Springer, 2013.
  * [16] Ryan O’Donnell, John Wright, and Yuan Zhou.  The Fourier entropy–influence conjecture for certain classes of boolean functions.  In International Colloquium on Automata, Languages, and Programming, pages 330–341. Springer, 2011.
  * [17] O. S. Rothaus.  On “bent” functions.  Journal of Combinatorial Theory, Series A, 20(3):300–305, 1976\.
  * [18] Peter Savický.  On the bent boolean functions that are symmetric.  European Journal of Combinatorics, 15(4):407–410, 1994.
  * [19] Guy Shalev.  On the Fourier entropy influence conjecture for extremal classes.  arXiv preprint arXiv:1806.03646, 2018.
  * [20] Pantelimon Stanica and Subhamoy Maitra.  A constructive count of rotation symmetric functions.  Information Processing Letters, 88(6):299–304, 2003.
  * [21] Andrew Wan, John Wright, and Chenggang Wu.  Decision trees, protocols and the entropy-influence conjecture.  In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 67–80, 2014.


# Mitigating Gender Bias in Machine Translation with Target Gender Annotations

Artūrs Stafanovičs*†‡ Toms Bergmanis*†‡ Mārcis Pinnis†‡

†Tilde / Vienības gatve 75A, Riga, Latvia
‡Faculty of Computing, University of Latvia / Raiņa bulv. 19, Riga, Latvia
<EMAIL_ADDRESS>
###### Abstract

When translating “The secretary asked for details.” to a language with
grammatical gender, it might be necessary to determine the gender of the
subject “secretary”. If the sentence does not contain the necessary
information, it is not always possible to disambiguate. In such cases, machine
translation systems select the most common translation option, which often
corresponds to the stereotypical translations, thus potentially exacerbating
prejudice and marginalisation of certain groups and people. We argue that the
information necessary for an adequate translation can not always be deduced
from the sentence being translated or even might depend on external knowledge.
Therefore, in this work, we propose to decouple the task of acquiring the
necessary information from the task of learning to translate correctly when
such information is available. To that end, we present a method for training
machine translation systems to use word-level annotations containing
information about subject’s gender. To prepare training data, we annotate
regular source language words with grammatical gender information of the
corresponding target language words. Using such data to train machine
translation systems reduces their reliance on gender stereotypes when
information about the subject’s gender is available. Our experiments on five
language pairs show that this allows improving accuracy on the WinoMT test set
by up to 25.8 percentage points.

††*First authors with equal contribution.

##  1 Introduction

Most modern natural language processing (NLP) systems learn from natural
language data. Findings of social sciences and corpus linguistics, however,
indicate various forms of bias in the way humans use language Coates (1987);
Butler (1990); Fuertes-Olivera (2007); Rickford (2016). Thus the resulting NLP
resources and systems also suffer from the same socially constructed biases,
as well as inaccuracies and incompleteness Jørgensen et al. (2015); Hovy and
Søgaard (2015); Prates et al. (2019); Vanmassenhove et al. (2019); Bordia and
Bowman (2019); Davidson et al. (2019); Tan and Celis (2019). Due to the
prevalent use of NLP systems, their susceptibility to social biases becomes an
increasingly significant concern as NLP systems not only reflect the biases
learned but also amplify and perpetuate them further Hovy and Spruit (2016);
Crawford (2017); HLEG (2019).

This work concerns mitigating the manifestations of gender bias in the outputs
of neural machine translation (NMT) systems in scenarios where the source
language does not encode the information about gender that is required in the
target language. An example is the translation of the English sentence “The
secretary asked for details.” into Latvian. In English, the gender of
“secretary” is ambiguous. In Latvian, however, there is a choice between the
masculine noun “sekretārs” and the feminine noun “sekretāre”. In cases when
sentences do not contain the necessary information, NMT systems opt for
translations which they have seen in training data most frequently. Acquiring
the necessary information, however, might require analysis of the text beyond
the level of individual sentences or require incorporation of external
knowledge.

Falling back to biases, however, happens not only in the absence of the
required information as NMT systems produce stereotyped translations even when
clues about the subject’s correct gender are present in the sentence Stanovsky
et al. (2019). This is in line with findings by Vanmassenhove et al. (2019)
who suggest that NMT systems produce biased outputs not only because of the
biases present in data but also due to their tendency to exacerbate them.

To provide means for incorporation of external and explicit gender
information, we propose a method for training NMT systems to use word-level
gender annotations. To prepare training data, we project grammatical gender
information of regular target language words onto the corresponding source
language words. Albeit in some cases redundant, we expect that the grammatical
gender information contains a useful learning signal that helps narrowing down
the lexical choice of the correct target translation. As a result, the NMT
system learns to rely on these annotations when and where they are available.
In particular, in experiments on five language pairs, we show that the methods
proposed here can be used in tandem with off-the-shelf co-reference resolution
tools to improve accuracy on the WinoMT challenge set Stanovsky et al. (2019)
by up to 25.8 percentage points.

###  1.1 Related work

Recent recommendations for ethics guidelines for trustworthy AI recommend
removing socially constructed biases at the source, the training data, prior
to model training HLEG (2019). An example of work on debiasing training data
is Zhao et al. (2018) where authors identified sentences containing animate
nouns and changed their grammatical gender to the opposite. Zmigrod et al.
(2019) take it further by ensuring that not only the animate nouns but also
the rest of the sentence is reinflected from masculine to feminine (or vice-
versa), thus preserving the morpho-syntactic agreement of the whole sentence.
The applicability of this line of work is still to be established as
reinflecting sentences with co-references or pairs of parallel sentences in
NMT pose an additional challenge.

A different take on addressing gender biases in NMT outputs is the work on
alternative generation: given a gender-ambiguous source sentence and its
translation, provide an alternative translation using the opposite gender.
Habash et al. (2019) approach this as a gender classification and reinflection
task for target language sentences to address the first person singular cases
when translating from English into Arabic. Bau et al. (2018) analyze trained
NMT models to identify neurons that control various features, including gender
information, that are used to generate the target sentence. In practice,
however, such solutions are limited to simple source sentences where only one
alternative in the target language is possible.

A complementary approach is addressing gender bias in NMT as a problem of
domain mismatch. When translating TED talks, Michel and Neubig (2018) propose
to adapt the NMT model for each speaker’s attributes, thus also implicitly
addressing previously poorly translated first-person singular cases. Saunders
and Byrne (2020) describe methods for NMT model adaptation using a handcrafted
gender-balanced dataset and a translation re-scoring scheme based on the
adapted models.

The closest line of work to ours is the work on the incorporation of external
gender information in the NMT input. Elaraby et al. (2018) and Vanmassenhove
et al. (2018) prepend training data sentences with speaker gender information
to improve spoken language translation when translating into languages with
grammatical gender. Moryossef et al. (2019) undertakes a similar approach at
the inference time using phrases (e.g. “she said:”) that imply the speaker’s
gender. The methods proposed in this work differ from the previous work in
terms of annotation granularity: we propose to use token level annotations,
while the previous work used one annotation per sentence. As our training data
annotations are solely based on grammatical gender, preparing them does not
require any external gender information. Thus our approach is also simpler in
terms of training data preparation compared to the previous work Elaraby et
al. (2018); Vanmassenhove et al. (2018).

#### Social Impact

We propose methods to mitigate the manifestations of gender bias in the
outputs of NMT. Specifically, these methods provide explicit means to
incorporate information about subjects referential or social gender in NMT,
thus reducing gender-based stereotyping when translating into languages which
encode for grammatical gender in animate nouns. An example of a use case and a
beneficiary group is the translation of occupational nouns into languages
which mark gender and people for whom stereotypes of their profession do not
align with their gender. While these methods can relieve gender-based
representational harms by reducing stereotyped translations, they,
unfortunately, provide no means for better representation of non-binary gender
identities.

Figure 1: Illustration of target to source projections of grammatical gender
annotations. Sample sentences taken from the English-Latvian development set
of the WMT2017 News Translation Task.

##  2 Methods

When translating from languages without grammatical gender to languages with
grammatical gender, certain words in the source sentence may not contain all
the necessary information to produce an adequate and accurate translation.
Examples are pronouns (e.g. I, me, they, them, themselves), animate nouns such
as job titles and proper nouns such as names and surnames, which depending on
the sentence context can be ambiguous and consequently can be translated
poorly. Previous work has also shown that NMT systems are better at
translating sentences that align with socially constructed gender stereotypes
because they are more frequently seen in training data Stanovsky et al.
(2019); Prates et al. (2019).

To circumvent the degradation of NMT outputs due to 1) socially constructed
biases and 2) absence of necessary information, we propose a method for
training NMT systems to be aware of and use word-level target gender
annotations (TGA). For training, we use data where regular source language
words are annotated with the grammatical gender of their target language
translations. We obtain such data by, first, morphologically tagging target
language sentences to obtain information about their grammatical gender—F for
feminine, M for masculine, N for neuter, and U for cases where grammatical
gender is unavailable. Then, we use word-level statistical alignments to
project this information from the target language to the source language words
(see Figure 1 for an illustration). We use source-side factors Sennrich and
Haddow (2016) to integrate the projected annotations as an additional input
stream of the NMT system. To ensure that the NMT systems are capable of
producing adequate translations when gender annotations are not available—a
frequently expected case at the test time—we apply TGA dropout. We do so by
randomly replacing annotations for a random number of words with U.

While useful for animate nouns, such annotations might seem otherwise
redundant because the majority of nouns in training data can be expected to be
inanimate. However, for some inanimate nouns, the target language grammatical
gender annotations can help narrowing down the lexical choice during training.
An example is the translation of “injury” into Latvian, where “injury$|$F”
would result in “trauma” while “injury$|$M” would correspond to “ievainojums”.
Besides disambiguating animate nouns, annotations also disambiguate the
grammatical gender of pronouns, proper nouns. Furthermore, grammatical gender
annotations also concern adjectives and verbs, which in some languages have to
agree in gender with the nouns they describe. Consequently, we expect that
during training the NMT model will learn to use these annotations, as they
contain valuable information about words in the target sentence.

At inference time, we lean heavily on the observation that there the
grammatical gender of animate nouns, pronouns, and proper nouns, and the
intended referential gender coincide considerably. This is, however, a
heuristic and not a rule (see Hellinger and Motschenbacher (2015) for
counterexamples). Nevertheless, we assume that it is possible to use TGA in a
referential sense of gender, thus injecting the NMT model with additional
information about the subject’s gender. Sources of such information can vary;
in this paper, we show-case how to use TGA together with off-the-shelf co-
reference resolution tools.

Figure 2: WinoMT test suite translation process with TGA distilled from the
output of automatic coreference resolution tool.

###  2.1 Evaluation: WinoMT Test Suite

To measure the extent to which gender annotations reduce NMT systems’ reliance
on gender stereotypes, we use the WinoMT test suite Stanovsky et al. (2019).
WinoMT builds on the previous work on addressing gender bias in co-reference
resolution by combining Winogender Rudinger et al. (2018) and WinoBias Zhao et
al. (2018) datasets in a test suite for automatic evaluation of gender bias in
MT. All sentences in the WinoMT test set follow the Winograd Schema where
anaphora resolution is required to find an antecedent for an ambiguous pronoun
Hirst (1981). In the case of datasets designed for evaluation of gender bias,
the ambiguous pronoun refers to one of two entities which are referred to
using titles of their professions. Professions and pronouns are chosen so that
they either align with or diverge from the gender stereotypes of each
profession as reported by the U.S. Bureau of Labor Statistics Zhao et al.
(2018).

WinoMT tests if the grammatical gender of the translation of an antecedent
matches the gender of the pronoun in the original sentence. Testing is done by
morphologically analysing the target translation and aligning it with the
source sentence. The WinoMT test suite scores MT outputs using multiple
metrics: Accuracy – the percentage of correctly translated antecedents,
$\boldsymbol{\Delta G}$ – difference in $F_{1}$ score between sentences with
masculine and feminine antecedents, $\boldsymbol{\Delta S}$ – difference in
accuracy between the set of sentences that either align with or diverge from
the gender stereotypes of each profession. Saunders and Byrne (2020) also
propose to report M:F – ratio of translations using masculine and feminine
antecedents.

##  3 Experimental Setting

#### Languages and Data

In all our experiments, we choose one source language without grammatical
gender and five Indo-European languages in which nouns have grammatical gender
(see Table 1). For all language pairs, we use training data from WMT news
translation tasks. We do the necessary cleaning and filtering with Moses Koehn
et al. (2007) pre-processing tools. To see how TGA is affected by data size,
we also use much larger EN-LV proprietary data that we obtain from Tilde Data
Libarary by combining all EN-LV parallel corpora. The proprietary data are
pre-processed using the Tilde MT platform Pinnis et al. (2018). Table 1
summarizes training data source and size statistics prior to adding TGA. For
all systems and language pairs, we use byte pair encoding (BPE) Gage (1994);
Sennrich et al. (2016) to prepare joint source and target language BPE sub-
word vocabularies. We use 30K BPE merge operations and use a vocabulary
threshold of 50.

#### NMT Systems

We use the default configuration of the Transformer Vaswani et al. (2017) NMT
model implementation of the Sockeye NMT toolkit (Hieber et al., 2020). The
exception is the use of source-side factors Sennrich and Haddow (2016) with
the dimensionality of 8 for systems using TGA, which changes the model’s
combined source embedding dimensionality from 512 to 520. We train all models
using early stopping with patience of 10 based on their development set
perplexity Prechelt (1998).

| Source | # Sent. | News Test
---|---|---|---
EN-DE | WMT19 | 64.1M | 2018
EN-FR | WMT15 | 39.1M | 2015
EN-LV | Tilde | 22.7M | 2017
EN-LV | WMT17 | 4.5M | 2017
EN-LT | WMT19 | 3.6M | 2019
EN-RU | WMT17 | 25.0M | 2015
Table 1: Training data set source and size in millions of sentences prior to adding TGA. Tagger | F1 masc. | F1 fem.
---|---|---
Paikens et al. (2013) | 98.6 | 98.7
Stanza | 94.7 | 95.1
UDPipe | 92.5 | 92.4
Table 2: Performance of morphological taggers on gender feature classification
evaluated on the Universal Dependencies test set.

#### Morphological Taggers

The preparation of training data with TGA and WinoMT evaluation relies on the
outputs of a morphological tagger. If the tagger produces biased outputs, the
TGA annotations might become too noisy to be useful. Furthermore, a biased
morphological tagger could also render WinoMT evaluation unreliable. Thus we
first benchmark several morphological taggers on grammatical gender feature
classification. We use Latvian as a development language because of the
availability of lexicon-based and data-driven morphological analysis tools.
Specifically, we use the Universal Dependencies
111https://github.com/UniversalDependencies/UD_Latvian-LVTB test set to
compare two data-driven tools – the Stanza toolkit Qi et al. (2020) and UDPipe
Straka and Straková (2017). Additionally, we evaluate a dictionary-based
morphological analyser and statistical
tagger222https://github.com/PeterisP/LVTagger by Paikens et al. (2013). Table
2 gives F-1 scores on masculine and feminine feature tagging. Results indicate
that none of the taggers exhibits salient bias in their tagging performance.
As the only non-neural system yields better F-1 scores than the other two
systems, we further compare Stanza and the tagger by Paikens et al. (2013) in
their impact on BLEU and WinoMT metrics. Results indicated that the choice of
the tagger does not have a notable effect on BLEU scores. In terms of WinoMT
accuracy scores, the NMT system that was trained using TGA prepared with
Stanza yields an accuracy that is about 3% better than the system using the
tagger by Paikens et al. (2013). Thus, in all remaining experiments, we use
the Stanza tagger as it provides pre-trained models for a wide range of
languages.

#### TGA in Training Data

Preparing training data with TGA requires statistical word alignments between
words of source and target language sentences and a target language
morphological tagger. To obtain word alignments, we use fast_align Dyer et al.
(2013). To obtain grammatical gender information of target language words, we
use the Stanza morphological tagger. When training NMT systems with TGA, we
combine two copies of the original training data: one where all source-side
factors are set to U and the other containing TGA.

#### TGA During Inference

In training data, TGA annotate regular source language words with the
grammatical gender information of corresponding target language words. We do
not have access to the target language sentence during inference. Thus, we use
co-reference resolution tools and extract the referential gender information
from the source sentence instead. To do so, we first use co-reference
resolution tools to obtain the co-reference graph. We then identify sub-graphs
which contain gendered pronouns. Finally, we propagate the gender information
within the graph and annotate the antecedents (see Figure 2). We set the
annotations for the remaining unannotated words to U.

We use neural co-reference resolution tools by AllenNLP
333https://github.com/allenai/allennlp Lee et al. (2017) and Hugging
Face444https://github.com/huggingface/neuralcoref (based on work by Clark and
Manning (2016)). We refer to these systems as TGA AllenNLP and TGA HuggingFace
respectively. We also report the performance of NMT with TGA, when TGA use
oracle information directly taken from WinoMT datasets and refer to these as
TGA Oracle.

#### Evaluation

We evaluate general translation quality using the BLEU Papineni et al. (2002)
metric evaluated over WMT test sets. To calculate BLEU, we use
SacreBLEU555SacreBLEU hash:
BLEU+case.mixed+numrefs.1+smooth.exp+tok.13a+version.1.3.6 Post (2018) on
cased, detokenized data. Reference test sets are only pre-processed using
Moses punctuation normalization script666https://github.com/moses-
smt/mosesdecoder/blob/master/scripts/tokenizer/normalize-punctuation.perl. We
use the WinoMT test suite Stanovsky et al. (2019) to measure gender bias of
our NMT systems.

##  4 Results and Discussion

| WMT Data Systems
---|---
|  | Acc. |  $\Delta$ G |  $\Delta$ S | M:F
EN-DE | Baseline | 66.7 | 10.2 | 14.4 | 2.6
TGA Oracle | 89.0 | -4.7 | 1.7 | 1
TGA HuggingFace | 77.6 | -0.1 | 11.9 | 1.6
TGA AllenNLP | 81.5 | -2.0 | 11.1 | 1.4
EN-FR | Baseline | 48.6 | 29.8 | 11.8 | 5.5
TGA Oracle | 81.5 | 1.4 | 2.8 | 1.2
TGA HuggingFace | 67.8 | 4.9 | 12.4 | 2
TGA AllenNLP | 74.4 | 1.6 | 10.1 | 1.6
EN-LV | Baseline | 27.9 | 26.0 | 9.6 | 3.9
TGA Oracle | 42.7 | 15.9 | 10.3 | 2.9
TGA HuggingFace | 38.6 | 19.7 | 18.1 | 3.0
TGA AllenNLP | 39.3 | 18.1 | 18.6 | 2.8
EN-LT | Baseline | 38.0 | 32.6 | 6.5 | 5.9
TGA Oracle | 52.8 | 15.2 | 4.0 | 2.7
TGA HuggingFace | 43.4 | 22.5 | 7.6 | 3.9
TGA AllenNLP | 47.2 | 17.7 | 5.1 | 3.1
EN-RU | Baseline | 32.3 | 37.7 | 14.1 | 8.4
TGA Oracle | 55.9 | 10.6 | 14.0 | 2.5
TGA HuggingFace | 45.4 | 24.8 | 13.7 | 4.4
TGA AllenNLP | 51.4 | 17.0 | 15.2 | 3.2
| Proprietary Large Data System
|  | Acc. |  $\Delta$ G |  $\Delta$ S | M:F
EN-LV | Baseline | 42.0 | 27.9 | 16.6 | 4.9
TGA Oracle | 55.1 | 4.8 | 18.2 | 1.7
TGA HuggingFace | 46.2 | 13.5 | 24.1 | 2.6
TGA AllenNLP | 49.9 | 10.8 | 23.1 | 2.3
Table 3: Results on WinoMT test suite.

Results from experiments evaluating gender bias using the WinoMT test suite
are provided in Table 3. First, we observe that all baseline systems show a
strong bias towards generating translations using masculine forms. The EN-RU
baseline system is the most biased as it produces only one translation
hypothesis with a feminine antecedent for every 8.4 hypotheses containing
masculine antecedents. Meanwhile the EN-DE baseline system is the least biased
with the M:F ratio being much lower – 2.6 (see the last column of Table 3).
Our baseline systems for EN-DE, EN-FR and EN-RU language pairs, however, show
comparable $\Delta G$ and WinoMT accuracy results to those reported by
Stanovsky et al. (2019) for several publicly available commercial systems.
These results confirm that our baselines, although being strongly biased, are
not unordinary.

Results from experiments using TGA with oracle gender information show an
improvement in WinoMT accuracy and $\Delta G$ for all language pairs (see
Table 3 TGA Oracle). These results demonstrate that when training MT systems
to use TGA reduces their reliance on gender stereotypes when information about
the subject’s gender is available, proving the usefulness of methods proposed
here. Despite the availability of oracle gender information, none of the
systems is entirely bias-free or obtains 100% accuracy. Thus methods proposed
here could be combined with others, such as those proposed by Saunders and
Byrne (2020), to achieve further improvements.

#### Effect on BLEU

As expected, using TGA with reference sentence grammatical gender annotations
has a positive effect on BLEU, thus confirming our hypothesis why and how the
NMT system learns to rely on TGA as an additional source of information during
training (see Table 4). It is equally important, however, that, when training
NMT systems to use TGA, it does not degrade their performance when gender
information is not necessary or is unavailable. Thus we test our systems for
such cases by setting all TGA values to U and compare them to the baseline
systems (see Table 4). To test for statistically significant differences
between the results of NMT systems we use pairwise bootstrap re-sampling Koehn
(2004) and significance threshold of $0.05$. Results indicate no statistically
significant differences between systems using uninformative TGA values and
their baseline counterparts with an exception of results for EN-RU systems
($\Delta 0.4$ BLEU), which we find to be statistically significant.

#### Effect of Data Size

To analyze gender bias and TGA performance depending on the quality and size
of the training data, we use much larger EN-LV proprietary data (see Table 1)
to train production-grade NMT systems and contrast them with EN-LV WMT data
systems (see the two EN-LV sections in Table 3 and Table 5). First of all, we
notice that although the large data baseline has higher WinoMT accuracy than
the WMT data system, it has a similar $\Delta G$. Decomposing $\Delta G$ as
male and female grammatical gender F-1 scores (Table 5), however, clarifies
that, although similarly skewed, the large data baseline has higher F-1 scores
than the WMT data baseline. Next, we note, that larger training data size has
a positive effect on the system’s ability to use TGA more effectively as the
large data system using TGA has a greater improvement on the two metrics
measuring bias – $\Delta G$ and M:F777$\Delta S$ results are not reliable or
comparable when M:F ratios are large or differ by a large value. See result
section of Saunders and Byrne (2020) for more discussion. than its WMT data
counterpart relative to its baseline. These findings suggest that TGA is a
method that is applicable not only in small data settings but also in large
data settings, such as commercial systems, for which it is even more
effective.

#### Plugging-in Co-reference Resolution Tools

Finally, we experiment with TGA using gender information provided by two off-
the-shelf co-reference resolution tools, AllenNLP and Hugging Face. Results
show that using TGA with either of the tools outperforms baseline systems for
all languages pairs. Furthermore, TGA with gender information provided by
AllenNLP shows only a 4.5 to 7.1% drop in WinoMT accuracy compared to results
when using TGA with oracle information. To put this in perspective, Saunders
and Byrne (2020) required a handcrafted gender-balanced profession set and
additional rescoring models, for their EN-DE system to obtain comparable
WinoMT accuracy and $\Delta G$ without loss of translation quality. In
contrast, the methods proposed here require tools that are readily available,
making them easily applicable in practice.

| Basline | TGA | All TGA= U
---|---|---|---
EN-DE | 45.4 | 49.5 | 45.3
EN-FR | 36.6 | 40.9 | 36.4
EN-LV | 16.6 | 18.9 | 17.0
EN-LT | 14.8 | 16.6 | 14.7
EN-RU | 27.1 | 31.6 | 26.7
Table 4: Comparison of test set performance measured in BLEU for Baseline systems and systems trained using TGA. TGA: performance when using reference sentence _grammatical gender_ annotations. All TGA=U: performance when all annotations set to be unknown. | Male | Female
---|---|---
| F-1 | P | R | F-1 | P | R
| WMT Data System
Baseline | 47.2 | 48.3 | 46.2 | 21.2 | 53.9 | 13.2
TGA Oracle | 58.5 | 56.0 | 61.3 | 42.5 | 74.7 | 29.7
| Proprietary Large Data System
Baseline | 58.8 | 50.8 | 69.7 | 30.9 | 70.3 | 19.8
TGA Oracle | 66.9 | 65.8 | 68.0 | 62.1 | 83.3 | 49.5
Table 5: Results of antecedent translation. Reporting grammatical gender F-1
score, precision (P) and recall (R) for EN-LV systems trained on WMT and
proprietary large data.

##  5 Conclusions

We proposed a method for training MT systems to use word-level annotations
containing information about the subject’s gender. To prepare training data,
the method requires a morphological tagger to annotate regular source language
words with grammatical gender information of the corresponding target language
words. During inference, annotations can be used to provide information about
subjects’ referential or social gender obtained by analyzing text beyond
sentence boundaries or externally. In experiments with five language pairs, we
showed that using such gender annotations reduces NMT systems’ reliance on
gender stereotypes in principle. We then further showed one way for how these
findings can be used in practice by using off-the-shelf co-reference
resolution tools.

The method proposed here decouples the task of acquiring the necessary gender
information from the task of learning to translate correctly when such
information is available. Thus system’s ability to use such information can be
achieved independently from its availability at training time. This allows for
application-specific sources of gender information. Examples are the
translation of chat or social media content, where users may choose to
indicate their gender or translation of whole documents, where gender
information may be obtained using annotations and anaphora resolution. Thus,
we believe that the methods proposed here, will provide means to limit the
propagation of gender stereotypes by NMT systems when translating into
languages with grammatical gender.

The source code to reproduce our results for the publicly available data sets
is published on GitHub888https://github.com/artursstaf/mitigating-gender-bias-
wmt-2020.

## Acknowledgements

This research was partly done within the scope of the undergraduate thesis
project of the first author at the University of Latvia and supervised at
Tilde.

This research has been supported by the European Regional Development Fund
within the joint project of SIA TILDE and University of Latvia “Multilingual
Artificial Intelligence Based Human Computer Interaction” No.
1.1.1.1/18/A/148.

## References

  * Bau et al. (2018) Anthony Bau, Yonatan Belinkov, Hassan Sajjad, Nadir Durrani, Fahim Dalvi, and James R. Glass. 2018.  Identifying and controlling important neurons in neural machine translation.  _CoRR_ , abs/1811.01157.
  * Bordia and Bowman (2019) Shikha Bordia and Samuel R. Bowman. 2019.  Identifying and reducing gender bias in word-level language models.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Student Research Workshop_ , pages 7–15, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Butler (1990) Judith Butler. 1990.  Feminism and the subversion of identity.  _New York and London: Routledge_ , 3:1–25.
  * Clark and Manning (2016) Kevin Clark and Christopher D Manning. 2016.  Deep reinforcement learning for mention-ranking coreference models.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 2256–2262.
  * Coates (1987) Jennifer Coates. 1987.  _Women, men and language: A sociolinguistic account of gender differences in language_.  Longman.
  * Crawford (2017) Kate Crawford. 2017.  The trouble with bias.  In _Conference on Neural Information Processing Systems, invited speaker_.
  * Davidson et al. (2019) Thomas Davidson, Debasmita Bhattacharya, and Ingmar Weber. 2019.  Racial bias in hate speech and abusive language detection datasets.  In _Proceedings of the Third Workshop on Abusive Language Online_ , pages 25–35.
  * Dyer et al. (2013) Chris Dyer, Victor Chahuneau, and Noah A Smith. 2013.  A simple, fast, and effective reparameterization of ibm model 2.  In _Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 644–648.
  * Elaraby et al. (2018) Mostafa Elaraby, Ahmed Y. Tawfik, Mahmoud Khaled, Hany Hassan, and Aly Osama. 2018\.  Gender aware spoken language translation applied to english-arabic.  _2018 2nd International Conference on Natural Language and Speech Processing (ICNLSP)_ , pages 1–6.
  * Fuertes-Olivera (2007) Pedro A Fuertes-Olivera. 2007.  A corpus-based view of lexical gender in written business english.  _English for Specific Purposes_ , 26(2):219–234.
  * Gage (1994) Philip Gage. 1994.  A new algorithm for data compression.  _C Users J._ , 12(2):23–38.
  * Habash et al. (2019) Nizar Habash, Houda Bouamor, and Christine Chung. 2019.  Automatic gender identification and reinflection in Arabic.  In _Proceedings of the First Workshop on Gender Bias in Natural Language Processing_ , pages 155–165, Florence, Italy. Association for Computational Linguistics.
  * Hellinger and Motschenbacher (2015) Marlis Hellinger and Heiko Motschenbacher. 2015.  _Gender across languages_ , volume 4.  John Benjamins Publishing Company.
  * Hieber et al. (2020) Felix Hieber, Tobias Domhan, Michael Denkowski, and David Vilar. 2020.  Sockeye 2: A toolkit for neural machine translation.  In _Proceedings of the 22nd Annual Conference of the European Association for Machine Translation_ , pages 457–458, Lisboa, Portugal. European Association for Machine Translation.
  * Hirst (1981) Graeme Hirst. 1981.  Anaphora in natural language understanding: A survey.
  * HLEG (2019) AI HLEG. 2019.  Ethics guidelines for trustworthy ai.  _High-Level Expert Group on Artificial Intelligence, Brussels_.
  * Hovy and Søgaard (2015) Dirk Hovy and Anders Søgaard. 2015.  Tagging performance correlates with author age.  In _Proceedings of the 53rd annual meeting of the Association for Computational Linguistics and the 7th international joint conference on natural language processing (volume 2: Short papers)_ , pages 483–488.
  * Hovy and Spruit (2016) Dirk Hovy and Shannon L. Spruit. 2016.  The social impact of natural language processing.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 591–598, Berlin, Germany. Association for Computational Linguistics.
  * Jørgensen et al. (2015) Anna Jørgensen, Dirk Hovy, and Anders Søgaard. 2015.  Challenges of studying and processing dialects in social media.  In _Proceedings of the workshop on noisy user-generated text_ , pages 9–18.
  * Koehn (2004) Philipp Koehn. 2004.  Statistical significance tests for machine translation evaluation.  In _Proceedings of the 2004 conference on empirical methods in natural language processing_ , pages 388–395.
  * Koehn et al. (2007) Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondřej Bojar, Alexandra Constantin, and Evan Herbst. 2007\.  Moses: Open source toolkit for statistical machine translation.  In _Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics Companion Volume Proceedings of the Demo and Poster Sessions_ , pages 177–180, Prague, Czech Republic. Association for Computational Linguistics.
  * Lee et al. (2017) Kenton Lee, Luheng He, Mike Lewis, and Luke Zettlemoyer. 2017.  End-to-end neural coreference resolution.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 188–197.
  * Michel and Neubig (2018) Paul Michel and Graham Neubig. 2018.  Extreme adaptation for personalized neural machine translation.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 312–318, Melbourne, Australia. Association for Computational Linguistics.
  * Moryossef et al. (2019) Amit Moryossef, Roee Aharoni, and Yoav Goldberg. 2019.  Filling gender & number gaps in neural machine translation with black-box context injection.  In _Proceedings of the First Workshop on Gender Bias in Natural Language Processing_ , pages 49–54, Florence, Italy. Association for Computational Linguistics.
  * Paikens et al. (2013) Peteris Paikens, Laura Rituma, and Lauma Pretkalniņa. 2013.  Morphological analysis with limited resources: Latvian example.  In _Proceedings of the 19th Nordic Conference of Computational Linguistics (NODALIDA 2013)_ , pages 267–277.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
  * Pinnis et al. (2018) Mārcis Pinnis, Andrejs Vasiļjevs, Rihards Kalniņš, Roberts Rozis, Raivis Skadiņš, and Valters Šics. 2018.  Tilde MT platform for developing client specific MT solutions.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018)_ , Miyazaki, Japan. European Language Resources Association (ELRA).
  * Post (2018) Matt Post. 2018.  A call for clarity in reporting BLEU scores.  In _Proceedings of the Third Conference on Machine Translation: Research Papers_ , pages 186–191, Brussels, Belgium. Association for Computational Linguistics.
  * Prates et al. (2019) Marcelo OR Prates, Pedro H Avelar, and Luís C Lamb. 2019.  Assessing gender bias in machine translation: a case study with google translate.  _Neural Computing and Applications_ , pages 1–19.
  * Prechelt (1998) Lutz Prechelt. 1998.  Early stopping-but when?  In _Neural Networks: Tricks of the trade_ , pages 55–69. Springer.
  * Qi et al. (2020) Peng Qi, Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D. Manning. 2020\.  Stanza: A python natural language processing toolkit for many human languages.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 101–108, Online. Association for Computational Linguistics.
  * Rickford (2016) John R Rickford. 2016.  _Raciolinguistics: How language shapes our ideas about race_.  Oxford University Press.
  * Rudinger et al. (2018) Rachel Rudinger, Jason Naradowsky, Brian Leonard, and Benjamin Van Durme. 2018.  Gender bias in coreference resolution.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 8–14.
  * Saunders and Byrne (2020) Danielle Saunders and Bill Byrne. 2020.  Reducing gender bias in neural machine translation as a domain adaptation problem.  Association for Computational Linguistics.
  * Sennrich and Haddow (2016) Rico Sennrich and Barry Haddow. 2016.  Linguistic input features improve neural machine translation.  In _Proceedings of the First Conference on Machine Translation: Volume 1, Research Papers_ , pages 83–91, Berlin, Germany. Association for Computational Linguistics.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1715–1725, Berlin, Germany. Association for Computational Linguistics.
  * Stanovsky et al. (2019) Gabriel Stanovsky, Noah A. Smith, and Luke Zettlemoyer. 2019.  Evaluating gender bias in machine translation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 1679–1684, Florence, Italy. Association for Computational Linguistics.
  * Straka and Straková (2017) Milan Straka and Jana Straková. 2017.  Tokenizing, pos tagging, lemmatizing and parsing ud 2.0 with udpipe.  In _Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies_ , pages 88–99, Vancouver, Canada. Association for Computational Linguistics.
  * Tan and Celis (2019) Yi Chern Tan and L. Elisa Celis. 2019.  Assessing social and intersectional biases in contextualized word representations.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems 32_ , pages 13230–13241. Curran Associates, Inc.
  * Vanmassenhove et al. (2018) Eva Vanmassenhove, Christian Hardmeier, and Andy Way. 2018.  Getting gender right in neural machine translation.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3003–3008, Brussels, Belgium. Association for Computational Linguistics.
  * Vanmassenhove et al. (2019) Eva Vanmassenhove, Dimitar Shterionov, and Andy Way. 2019.  Lost in translation: Loss and decay of linguistic richness in machine translation.  In _Proceedings of Machine Translation Summit XVII Volume 1: Research Track_ , pages 222–232, Dublin, Ireland. European Association for Machine Translation.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems 30_ , pages 5998–6008. Curran Associates, Inc.
  * Zhao et al. (2018) Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang. 2018\.  Gender bias in coreference resolution: Evaluation and debiasing methods.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 15–20, New Orleans, Louisiana. Association for Computational Linguistics.
  * Zmigrod et al. (2019) Ran Zmigrod, Sabrina J. Mielke, Hanna Wallach, and Ryan Cotterell. 2019.  Counterfactual data augmentation for mitigating gender stereotypes in languages with rich morphology.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 1651–1661, Florence, Italy. Association for Computational Linguistics.