# How does Grammatical Gender Affect Noun Representations
in Gender-Marking Languages?

Hila Gonen1 Yova Kementchedjhieva2 Yoav Goldberg1,3
1Department of Computer Science, Bar-Ilan University
2University of Copenhagen
3Allen Institute for Artificial Intelligence
hilagnn@gmail.com,yova<EMAIL_ADDRESS>

###### Abstract

Many natural languages assign grammatical gender also to inanimate nouns in
the language. In such languages, words that relate to the gender-marked nouns
are inflected to agree with the noun’s gender. We show that this affects the
word representations of inanimate nouns, resulting in nouns with the same
gender being closer to each other than nouns with different gender. While
“embedding debiasing” methods fail to remove the effect, we demonstrate that a
careful application of methods that neutralize grammatical gender signals from
the words’ context when training word embeddings is effective in removing it.
Fixing the grammatical gender bias yields a positive effect on the quality of
the resulting word embeddings, both in monolingual and cross-lingual settings.
We note that successfully removing gender signals, while achievable, is not
trivial to do and that a language-specific morphological analyzer, together
with careful usage of it, are essential for achieving good results.

##  1 Introduction

Work on distributional word embeddings focuses almost exclusively on English,
or on cross-lingual and language-agnostic techniques. However, languages are
diverse and different languages exhibit different linguistic phenomena, which
may interact with the English-centric embedding learning algorithms. In this
work we look into one such phenomenon—grammatical gender—and examine its
effect on the learned representation.

Many languages have rich grammatical systems, that often include a complex
gender system as well Corbett (1991). Languages with grammatical gender assign
and morphologically mark gender not only to animate nouns (which have
biological sex, e.g. man, woman, mother, father), but also to inanimate nouns
(e.g. dream, book). This grammatical gender assignment is mostly arbitrary:
the same inanimate concept can have different gender in different languages.
For example, a _flower_ is masculine in Italian (_fiore_) and feminine in
German (_Blume_).

Languages often maintain an _agreement system_ in which certain words agree on
different morphological features with other words they relate to. For example,
English present-tense verbs are inflected to agree with their nominal subject
on the _number_ feature. In other languages the agreement system is more
elaborate, and in particular verbs, adjectives, determiners and other
functions agree with nouns on many features, including gender Corbett
(2006).111As the gender of nouns is fixed, the other elements are inflected to
accommodate the agreement constraint. The nouns are said to _assign gender_ to
the other words.

Such grammatical agreement affects the distributional environment of nouns, as
nouns of different gender become surrounded by different word forms: feminine
nouns co-occur more with the feminine forms of words, while masculine nouns
with the masculine forms. For example, the Italian word _viaggio_ (“ _journey_
”-masc) will co-occur with _durato_ (“ _last_ ”-masc) and _lungo_ (“ _long_
”-masc), while the word _gita_ (“ _trip_ ”-fem) will co-occur with _durata_ (“
_last_ ”-fem) and _lunga_ (“ _long_ ”-fem).

Such changes in the distributional environment may bias the learned
distributional representations of inanimate nouns. Indeed, we see that the
majority of the top-10 nearest neighbors of the word _gita_ in Italian (“
_trip_ ”-fem) are feminine words. Also, we notice that the word _viaggio_ (“
_journey_ ”-masc) is not on the list, while in English, for comparison, we can
find _journey_ in the top-10 nearest neighbors of _trip_.

In this work, we are interested in investigating, demonstrating and
quantifying this effect beyond the anecdotal level. We also explore methods
for removing such unwanted biases.

We demonstrate that both in Italian and in German, the grammatical gender
affects similarities between word representations (using words from SimLex-999
Hill et al. (2015); Leviant and Reichart (2015)): pairs of nouns with similar
gender are closer to each other while pairs of nouns with different gender are
farther apart.

After quantifying the effect, we explore several methods of reducing it. A
popular choice would be to simply lemmatize all the words prior to feeding
them to the embedding learning algorithm. However, full lemmatization can be
destructive, in the sense that it will also remove morphological distinction
that we may want to keep. We thus seek more surgical approaches.
Interestingly, recent embedding debiasing approaches Bolukbasi et al. (2016)
do not work well. We instead look for methods that attempt to neutralize the
gender signals from the training data. We find that such methods are effective
in reducing the effect, but are also language specific and tricky to get
right: we rely on language specific morphological analyzers while carefully
accounting for their peculiarities and adjusting our use for each language. We
take this work as a reminder that (a) linguistic resources such as lexicons
and morphological analyzers are still relevant and useful (cf. Zalmout and
Habash (2017)); (b) languages are diverse and different languages require
different treatments; and (c) small details may matter a lot. In particular,
existing tools and resources, either learned or human curated, should not be
trusted blindly, but be carefuly adapted for the problem.

Finally, we show that reducing the effect of grammatical agreement also has a
positive effect on the quality of the resulting word representations, both in
monolingual and cross-lingual settings. We conclude that grammatical gender
indeed has its imprints on the representations of inanimate nouns, and that
this should be taken into account when working with gender-marking languages.
Our code and debiased embeddings are available at
https://github.com/gonenhila/grammatical_gender.

##  2 Background and Related Work

#### Word Embeddings

Word embeddings have become an important component in many NLP models and are
widely used for a vast range of downstream tasks. These models are based on
the distributional hypothesis according to which words that occur in the same
contexts tend to have similar meanings Harris (1954). Indeed, they aim to
create word representations that are derived from their shared contexts, where
the context of a word is essentially the words in its proximity (be it
according to linear order in the sentence or according to syntactic relations)
Mikolov et al. (2013); Pennington et al. (2014); Levy and Goldberg (2014).

#### Gender Biases in Word Embeddings

Social gender bias was demonstrated to be consistent and pervasive across
different word embeddings Caliskan et al. (2017). Bolukbasi et al. (2016) show
that using word embeddings for simple analogies surfaces many gender
stereotypes. In addition, they define the gender bias of a word $w$ by its
projection on the “gender direction”:
$\overrightarrow{w}\cdot(\overrightarrow{he}-\overrightarrow{she})$, assuming
all vectors are normalized. Positive bias stands for male-bias. For example,
the bias of manager is $0.06$, while the bias of nurse is $-0.10$222in English
word2vec embeddings Mikolov et al. (2013) trained on Wikipedia..

Recently, some work has been done to reduce social gender bias in word
embeddings, both as a post-processing step Bolukbasi et al. (2016) and as part
of the training procedure Zhao et al. (2018). Bolukbasi et al. (2016) use a
post-processing debiasing method. Given a word embedding matrix, they make
changes to the word vectors in order to reduce the gender bias for all words
that are not inherently gendered. They do that by zeroing the gender
projection of each word on a predefined gender direction.333The gender
direction is chosen to be the top principal component (PC) of ten gender pair
difference vectors.

In Zmigrod et al. (2019), the authors mitigate social gender bias in gender
marking languages using counterfactual data augmentation. Gender-marking
languages add several interesting dimensions to the story: words relating to
animate concepts such as “nurse” or “cat” may have both masculine and feminine
versions; the distributional environment of a word contains many more explicit
gender cues; and inanimate concepts are also assigned gender. All of these
factors interact in complicated ways. In this work we focus on purely
grammatical gender—the gender that is assigned to inanimate nouns—and its
effect on their resulting representations.

#### Grammatical Gender Bias in Word Embeddings

Grammatical gender is manifested in a similar way to social bias. For example,
when projected on the Italian gender direction
$\overrightarrow{lui}-\overrightarrow{lei}$ (Italian equivalents of “he” and
“she”), the word “secolo” (_century_ , masculine) has positive bias of 0.073,
while the word “zuppa” (_soup_ , feminine) has negative bias of -0.079.444in
Italian word2vec embeddings Mikolov et al. (2013) trained on Wikipedia.

We attribute this behavior to grammatical agreement. Since the context of
different-gender nouns is expected to be very different because of the
agreement of the surrounding words, and since the resulting representations
are based on the context of the word, we expect grammatical gender to play a
role in the representations—nouns with the same gender are expected to be
closer together than nouns with different gender. For inanimate nouns, this
behavior is undesired.

#### Word Embeddings and Morphology

Word embeddings were shown to capture grammatical and morphological
properties. Avraham and Goldberg (2017) show that standard training of word
embeddings in Hebrew captures also morphological properties and that using the
lemmas when composing the representations helps to better capture semantic
similarities. Similarly, Basirat and Tang (2018) show that typical grammatical
features are captured by Swedish word embeddings.

Cotterell et al. (2016) treat the sparsity problem of morphologically rich
languages in word embedding. They present a Gaussian graphical model to smooth
representations of observed words and extrapolate representations for unseen
words using morphological resources. With similar motivation, Vulić et al.
(2017) use morphological constraints in English in order to pull inflectional
forms of the same word closer together and push derivational antonyms farther
apart. Finally, Salama et al. (2018) enhance Arabic word embeddings by
incorporating morphological annotations.

##  3 Grammatical Gender Affects Word Representations

As a first step, we aim to verify that the representation of inanimate nouns
in gender-marking languages is indeed affected by their grammatical gender.
Since English does not have grammatical gender, a natural approach would be to
use it as a reference when measuring this phenomenon.

###  3.1 Inanimate Noun Pairs from SimLex-999

We take the inanimate noun portion of the SimLex-999 dataset Hill et al.
(2015), a gold standard resource for evaluating distributional semantic
models. This dataset has an English version, and also German and Italian
versions Leviant and Reichart (2015), and includes both similar and dissimilar
word pairs, with human-assigned similarity judgments for each pair. This gives
us 529 pairs of English words, along with high quality translations to Italian
and German. We manually associate the Italian and German words with their
grammatical gender.

###  3.2 Differences in Similarities

We divide the pairs in the gender-marking (GM) language (be it German or
Italian) into two sets: (1) pairs of nouns that have the same gender in the GM
language; (2) pairs of nouns that have different gender in the GM language.
The respective English pairs are split in the same way, according to the
gender of the nouns in the GM language. Thus, we end up with two sets of pairs
in a GM language and their translations to English. Note that the English sets
are different when used as a reference for German and Italian, since the split
depends on the gender in the respective language.

For each set we compute the average of the cosine similarity of all word pairs
within it. If gender plays a role in the representation of words, and indeed
brings same-gender words closer together while keeping different-gender words
farther apart, we expect to see a significant difference between the average
similarity of the set of same-gender nouns and the set of different-gender
nouns. As mentioned above, we compute these averages for English as a
reference, where we expect a low difference between the two sets. Table 1
shows the results for Italian and German, compared to English. Indeed, in both
cases, the difference between the average of the two sets is much bigger.

| Italian | En | German | En
---|---|---|---|---
Same Gender | 0.442 | 0.424 | 0.491 | 0.446
Different Gender | 0.385 | 0.415 | 0.415 | 0.403
difference | 0.057 | 0.009 | 0.076 | 0.043

Table 1: Averages of similarities of pairs with same gender vs. different
gender, along with the respective averages in English. The last row
(difference) is the difference between the averages of the two sets.

###  3.3 Rank in Nearest Neighbor List

We take the same sets as before, and for each pair in them we compute the rank
of the second word in the nearest neighbor list of the first word and vice
versa. For example, for the pair “parola” (_word_) and “dizionario”
(_dictionary_) in Italian, we compute the rank of “dizionario” in the list of
nearest neighbor of “parola” and the rank of “parola” in the list of nearest
neighbors of “dizionario”.

We then compare the average ranking in each set, with English as the
reference. If the gender affects the similarities between words, we expect
same-gender pairs to have lower average than different-gender pairs (remember
that the closest word is at the lowest rank: 1). Table 2 shows the results for
Italian and German, compared to English. As expected, the average ranking of
same-gender pairs is significantly lower than that of different-gender pairs,
both for German and Italian, while the difference between the sets in English
is much smaller.

| Italian | German
---|---|---
| Same-gender | Diff-Gender | difference | Same-gender | Diff-Gender | difference
7–10 | Og: 4884 | Og: 12947 | Og: 8063 | Og: 5925 | Og: 33604 | Og: 27679
Db: 5523 | Db: 7312 | Db: 1789 | Db: 7653 | Db: 26071 | Db: 18418
En: 6978 | En: 2467 | En: -4511 | En: 4517 | En: 8666 | En: 4149
4–7 | Og: 10954 | Og: 15838 | Og: 4884 | Og: 19271 | Og: 27256 | Og: 7985
Db: 12037 | Db: 12564 | Db: 527 | Db: 24845 | Db: 22970 | Db: -1875
En: 15891 | En: 17782 | En: 1891 | En: 13282 | En: 17649 | En: 4367
0–4 | Og: 23314 | Og: 35783 | Og: 12469 | Og: 50983 | Og: 85263 | Og: 34280
Db: 26386 | Db: 28067 | Db: 1681 | Db: 60603 | Db: 79081 | Db: 18478
En: 57278 | En: 53053 | En: -4225 | En: 41509 | En: 62929 | En: 21420

Table 2: Averages of rankings of the words in same-gender pairs vs. different-
gender pairs for Italian and German, along with their differences. Og stands
for the original embeddings, Db for the debiased embeddings, and En for
English. Each row presents the averages of pairs with the respective scores in
SimLex-999 (0–4, 4–7, 7–10).

##  4 Debiasing Methods do not Work

As mentioned above, grammatical gender bias shares some aspects with social
gender bias. Keeping that in mind we first turn to use these existing methods
of gender-debiasing in English word embeddings.

Bolukbasi’s method (2016) requires sets of pairs that define the gender
direction. For this we use their predefined pairs, since we target grammatical
gender bias, which we have demonstrated to be similar to social gender bias.
In addition, a predefined set of inherently-neutral words is also needed:
these are the words that will be debiased by the algorithm. As a first step,
and in order to estimate the feasibility of using this method for reducing the
grammatical gender bias, we use the set of the inanimate nouns from SimLex-999
as our set of inherently-neutral words.555If this method doesn’t mitigate the
bias we showed in the previous section, then using inherently-neutral words
extracted from the vocabulary automatically cannot possibly work as well.

The algorithm worked well in the sense that the bias of all inanimate nouns,
when measured by their projection on the gender dimension, became zero.
However, it also failed: the similarities between the inanimate nouns
themselves hardly changed. Table 3 depicts the average similarities in Italian
before and after debiasing.

| Italian
---|---
| Original | Debiased | English | Reduction
Same Gender | 0.442 | 0.439 | 0.424 | –
Different Gender | 0.385 | 0.390 | 0.415 | –
difference | 0.057 | 0.049 | 0.009 | 16.67%

Table 3: Averages of similarities of pairs with same vs. different gender in
Italian compared to the debiased version using Bolukbasi’s (2016) method. The
last row is the difference between the averages of the two sets. “Reduction”
stands for gap reduction after debiasing.

This suggests that the information about the gender is deeply embedded in the
representation and is not easy to remove in a post-processing phase.
Specifically, zeroing the projection of a word’s vector on the gender
direction is not enough in order to remove all gender information from the
word’s representation. The fact that similarities between words hardly change
implies that the projection on the gender direction is not the only indication
of gender. These results align with the findings discussed in Gonen and
Goldberg (2019).

We conclude that focusing on the projection of vectors on the gender direction
is not the right way to go, and we opt to removing gender inflections from the
context before training. We describe this in detail in the next section.

##  5 Removing Gender Inflection from the Context

As mentioned above, words in the surroundings of gender-marked nouns (e.g.
articles, adjectives) are often inflected to agree with the gender of the noun
they relate to. As we hypothesize that most of the effect shown in Section 3
is caused by this gender agreement, we try several schemes that aim to remove
gender signals from the context.

A straight-forward approach would be to lemmatize all the words, which will
remove all gender signals from the context of a word. However, this approach
has two main downsides: 1) We would like to have a representation for all the
words in the vocabulary, but changing also the target words will reduce the
vocabulary size and result with missing words (we will no longer have
different masculine and feminine forms for any word); 2) Lemmatization removes
not only gender information, but also additional information (such as number
and tense). While gender assignment is arguably arbitrary, and does not
translate to an actual physical property of inanimate nouns in reality, other
properties that agree with the noun, such as number, do hold in reality and
signify actual properties of the target noun, which we prefer to preserve.

Thus, a better approach would be to neutralize gender signals from the context
alone, keeping the target words intact. This way we do not change the
resulting embedding vocabulary. This can be done using: 1) lemmatizing all the
context words, where we lose additional information, as discussed above; 2)
changing all the context words to the same gender, while keeping all other
features of the words intact. Once the whole context is of the same gender, we
essentially lose the gender information altogether as all nouns have similar
context, regardless their gender.666Context nouns are also kept unchanged
since nouns do not agree with other nouns in their context, both in Italian
and in German. Notably, in German, we lose the noun-ness information when we
lowercase the corpus (as all nouns in German begin with an uppercase letter).

###  5.1 The proposed approaches

We experiment with both lemmatization of context words and gender change of
context words.

#### Lemmatization of Context Words

When training word2vec Mikolov et al. (2013), we use a morphological analyzer
to identify the lemmas of words, and replace context words, but not target
words, with their lemmas.

#### Gender Change of Context Words

When training word2vec, we choose a gender (for example, masculine) and change
all context words to that gender: each word that is identified as being of a
different gender (in Italian: feminine, in German: feminine or neutral), is
changed to its masculine form. This is also done using a morphological
analyzer: when we identify a non-masculine analysis, we search for a masculine
one that shares the same lemma and features.

In general, we found Italian to work better with gender change, and German to
work better with lemmatization. We report full results in Section 6.

###  5.2 Challenges

While conceptually simple, fully neutralizing gender information is more
challenging than it initially appears, and requires careful attention to “get
right”. We describe some cases in which gender information can leak.

#### Human Curator Choices

The morphological analyzer sometimes assigns different lemmas to an opposite-
gender pair, as a result of human curater design choices. For example, in
Italian, “delle” is the feminine of “dei”, but they are assigned the lemmas
“della” and “del”, respectively. Such cases leak gender signal in both cases
of lemmatization and gender change: (1) When lemmatizing, each of the words
gets a different lemma, manifesting the gender. (2) When changing the gender,
the opposite-gender form of the word is not identified as these words do not
share lemma, and the words stay unchanged.

This was very prominent in some high-frequency Italian words, and dealt with
by fixing the analyzer: we identified all forms without a corresponding
gendered-pair, manually aligned them, and assigned each pair a shared and
unique lemma. This fix dramatically improved results when using either
lemmatization or gender change.

#### Gender-Ambiguous Word Forms

Many word forms have several morphological analyses, resulting in different
lemmas. Inspecting this ambiguity reveals two specific issues, in German and
in Italian. First, many German words are ambiguous with respect to gender. For
example, “eine” has a frequent feminine reading, but also a rare masculine
one. When changing words to masculine, this word is identified as potentially
masculine, and kept intact. The presence of the context word “eine” now leaks
a feminine signal.777A possible solution would be to replace words with their
lemmas whenever we identify both feminine and masculine analyses. This did not
improve results in practice.

Second, Italian has many cases of two words with a similar set of possible
lemmas but with different gender. For example, “usato” and “usata” are
masculine and feminine, respectively, and both have “usare” and “usato” as
possible lemmas. If we select a consistent lemma for each word type, and end
up selecting a different lemma for each of “usato” and “usata”, we again leak
signal regarding the original gender.

One solution would be to use context-sensitive lemmatization, that chooses the
correct analysis in context. However, doing this accurately is still an open
problem. Our proposed solution is to randomly sample a lemma per word token.
This improved lemmatization results in Italian by 25%.

#### Multiple Opposite-gender Forms for a Word

In some cases, a single word might have multiple forms in the opposite gender.
For example, the Italian “delle” is the feminine form of both “dei” and
“degli”, depending on the phonetic context. In this case, the former is much
more common than the latter. A naive approach that chooses to convert “delle”
to “degli” essentially keeps the feminine signal for these cases: every
instance of “delle” changes to “delgli”, which marks masculine nouns in much
less common cases, while most masculine nouns are usually accompanied with the
more common word “dei”.

Ideally, when changing the gender of a word, we want to change a word by
another word with a similar frequency, otherwise, the gender signal will be
manifested in the frequency mismatch, as in the example above.

We deal with this issue using the following heuristic: when changing to
masculine form (or any other gender form), for each word we first find all its
possible masculine forms. Then, we check the frequency of the original word in
the corpus, and choose the option with the closest frequency to it. This
indeed yields better results: when not addressing the frequency issue in
Italian, we are able to reduce the effect only by 35.42% (compared to 91.67%,
see Section 6 for more details).

(a)

(b)

Figure 1: The new rank of a word in the nearest neighbor list of its paired
word. In cyan (+) – pairs with the same gender, in purple ($\cdot$) – pairs
with different gender. Most words with same-gender are located above $y=x$
(were drifted apart), while most words with different-gender are located below
it (got closer together).

##  6 Results

We experimented with different schemes for each language, measuring their
success at removing gender bias of inanimate nouns with respect to
English.888We used state-of-the-art morphological analyzers for both
languages. Full implementation details can be found in the appendix.

For German, we found lemmatization to work better than gender change. In
Italian gender change got better results. Specifically, changing to feminine
got much better results than changing to masculine, probably due to less
ambiguity when changing to feminine in some very common articles (see full
manual mapping in the Appendix), resulting in fewer cases in which the gender
signal leaks through the frequencies of the changed words, as explained above.
In addition, the manual fixes to the lemmatizer were crucial to get satisfying
results for both methods.

While some of these findings depend on the specific morphological analyzer in
use, the challenges and issues we demonstrate are relevant in any case.

###  6.1 Reduction in Gender Bias

#### Differences in Similarities

We repeat the experiment in Section 3.2—computing the average of pair
similarities in each of the sets defined in Section 3, this time with the
embeddings trained after removing gender signal from the context (debiasing).
Table 4 shows the results for Italian and German, compared to English, both
for the original and the debiased embeddings (for each language we show the
results of the best performing debiased embeddings). As expected, in both
languages, the difference between the average of the two sets with the
debiased embeddings is much lower. In Italian, we get a reduction of 91.67% of
the gap with respect to English. In German, we get a reduction of 100%. Note
that for both languages, the main change is in the set of different-gender
pairs, and not in the same-gender pairs. This makes sense as same-gender words
have similar contexts both before and after our intervention, but different-
gender words have different contexts before, but much more similar contexts
after.

| Italian | German
---|---|---
| Original | Debiased | English | Reduction | Original | Debiased | English | Reduction
Same Gender | 0.442 | 0.434 | 0.424 | – | 0.491 | 0.478 | 0.446 | –
Different Gender | 0.385 | 0.421 | 0.415 | – | 0.415 | 0.435 | 0.403 | –
difference | 0.057 | 0.013 | 0.009 | 91.67% | 0.076 | 0.043 | 0.043 | 100%

Table 4: Averages of similarities of pairs with same vs. different gender in
Italian and German compared to English. The last row is the difference between
the averages of the two sets. “Reduction” stands for gap reduction when
removing gender signals from the context.

For comparison, in Italian we got 12.50% reduction when using the
lemmatization scheme, and 68.75% reduction when lemmatizing with the addition
of the manual mapping. For German, the best result using gender change was a
reduction of 48.48%, achieved by changing to neutral.

#### Rank in Nearest Neighbor List

We repeat the experiment shown in Section 3.3—for each pair we compute the
rank of the second word in the nearest neighbor list of the first word and
vice versa. Then we compare the average ranking in each of the defined sets.
Table 2 shows the results for Italian and German, both for the original and
the debiased embeddings. As we expect, the difference between the average
ranking of the two sets drops significantly for both languages.

In order to get a better picture of how the rankings of the different words
change as a result of the gender signal removal, we take all pairs (and the
inverted pairs). For each pair we plot the new rank of the second word in the
nearest neighbors list of the first word as a function of its original rank
before debiasing. Points above $y=x$ are of words that got a higher rank
(lower in the list, farther from the first word), while points below this line
are of words that got a lower rank (higher in the list, closer to the first
word). Figure 1 shows these plots for Italian and German. As expected, most
words of same-gender pairs are located above the line (were drifted apart),
while most words of different-gender pairs are located below the line (got
closer together).

###  6.2 Improvement in Word Similarities

#### Qualitative Evaluation

As a qualitative evaluation, we take several words for SimLex-999 and look at
their top-10 nearest neighbor lists, before and after applying our method. In
Table 5 we show the top-10 lists for the words _vaso_ (“ _jar_ ”-masculine) in
Italian, and _welt_ (“ _world_ ”-feminine) in German. It is evident that the
words that are added to the list, are better correlated with the target word
than those that are removed. Two additional words appear in the Appendix.

Italian | German
---|---
vaso (jar-masculine) | welt (world-feminine)
Orig | Debias | Orig | Debias
coccio | vasi | welt” | europas
recipiente | ciotola | europas | welt”
otre |  bacinella (basin) | scheibenwelt | scheibenwelt
cinerario | recipiente | hässlichsten |  universum (universe)
vasetto | coccio |  erde (earth) |  menschheitsgeschichte (human history)
bacile (basin) | cinerario |  weltgeschichte (world history) | hässlichsten
kantharos | otre |  klügste (wisest) |  menschheit (mankind)
vasi | vasetto |  klügsten (wisest) | schwarzafrikas
vassoio (tray) |  brocca (pitcher) | schwarzafrikas |  parallelwelten (parallel worlds)
coperchio (cover) |  scodella (bowl) |  lustigsten (funniest) | ulldart

Table 5: Examples of top-10 nearest neighbor lists for words in Italian and in
German, before and after debiasing. In red (italic) are words that were
removed from the list, and in blue (underlined) are words that were added to
it. Translations to English (Google Translate) for the changed words are in
parenthesis, when different from source.

#### Evaluation on Simlex and WordSim-353

We evaluate the quality of the grammatical-gender-neutralized embeddings using
two datasets for each language: SimLex-999 Hill et al. (2015); Leviant and
Reichart (2015) and WordSim-353 Finkelstein et al. (2002); Leviant and
Reichart (2015). Table 6 shows the results for Italian and German for both
datasets, compared to the original embeddings. In both cases, the new
embeddings perform better than the original ones.

| Italian | German
---|---|---
| Orig | Debias | Orig | Debias
SimLex | 0.280 | 0.288 | 0.343 | 0.356
WordSim | 0.548 | 0.577 | 0.547 | 0.553

Table 6: Results on SimLex-999 and WordSim-353, in Italian and German, before
and after debiasing.

#### Cross-lingual Word Embeddings

Studies in language and cognition suggest that humans share a common semantic
space, regardless of their native language Youn et al. (2016). To the extent
that embeddings capture the semantics of words, we can thus expect embedding
spaces to have a similar structure across languages. Youn’s statement concerns
concepts and not words, however, and concepts can surface in many different
forms in language, which interferes with how well embedding spaces align
across languages Søgaard et al. (2018). Thus, we expect grammatical gender to
have a negative impact on alignability.

We explore this matter through the task of cross-lingual embedding alignment,
wherein a cross-lingual embedding space is learned through an alignment of
independently pre-trained monolingual embeddings for a directed pair of
languages. The quality of cross-lingual embeddings learned this way can be
evaluated intrinsically on the task of bilingual dictionary induction (BDI).
BDI queries the cross-lingual embedding space with a seed of words in one
language, retrieves their counterparts among the words in the other
language999This is done by minimizing a distance metric, most commonly, CSLS
Conneau et al. (2018). and evaluates the precision of the produced
translations against a set of gold standard targets. We carry out experiments
using the supervised variant of the MUSE embedding alignment system Conneau et
al. (2018) and report results on the inanimate portion of SimLex-999. We train
a cross-lingual embedding alignment between English and either German or
Italian, using the original and the debiased embeddings for these two
languages. The results reported in Table 7 show that precision on BDI indeed
increases as a result of the reduced effect of grammatical gender on the
embeddings for German and Italian, i.e. that the embeddings spaces can be
aligned better with the debiased embeddings.

| Italian | German
---|---|---
|  $\rightarrow$ En | En $\rightarrow$ |  $\rightarrow$ En | En $\rightarrow$
Orig | 58.73 | 59.68 | 47.58 | 50.48
Debias | 60.03 | 60.96 | 47.89 | 51.76

Table 7: Cross-lingual embedding alignment in Italian and in German, before
and after debiasing.

##  7 Conclusion

We show that grammatical gender impacts word embeddings of inanimate nouns,
both in Italian and in German, causing the similarities between words to
change according to having same or different gender: the representations of
same-gender words are closer together than representations of different-gender
words.

We show that this effect can be almost completely removed when neutralizing
gender signals in the context during training of the word embeddings. While
most works in our field nowadays try to be language-independent, this is not
always the right way to go: successfully removing those gender signals is not
trivial to do and a language-specific morphological analyzer, together with
careful usage of it, are essential for achieving good results.101010Indeed,
before implementing the specific fixes described in Section 5, the reduction
compared to English when naively changing to masculine was substantially
smaller, 35.42% reduction compared to 91.67% in Italian, and 12.12% compared
to 100.00% (with lemmatization) in German.

In addition, this work serves as a reminder that languages other than English
have different properties that are rarely dealt with when processing English.
These aspects should be taken into account when dealing with morphologically
reach languages, as not all models and algorithms for English can transfer
directly to other languages.

##  8 Acknowledgements

The work was supported by the Israeli Science Foundation (grant number
1555/15) and by and the European Research Council (ERC Starting Grant iExtract
802774). We thank Valentina Pyatkin for the help with the Italian manual
mapping.

## References

  * Altinok (2018) Duygu Altinok. 2018.  Demorphy, german language morphological analyzer.  _arXiv:1803.00902_.
  * Avraham and Goldberg (2017) Oded Avraham and Yoav Goldberg. 2017.  The interplay of semantics and morphology in word embeddings.  In _Proceedings of EACL_.
  * Basirat and Tang (2018) Ali Basirat and Marc Tang. 2018.  Lexical and morpho-syntactic features in word embeddings-a case study of nouns in swedish.  In _ICAART_.
  * Bolukbasi et al. (2016) Tolga Bolukbasi, Kai-Wei Chang, James Y Zou, Venkatesh Saligrama, and Adam T Kalai. 2016.  Man is to computer programmer as woman is to homemaker? debiasing word embeddings.  In _Advances in Neural Information Processing Systems_.
  * Caliskan et al. (2017) Aylin Caliskan, Joanna J Bryson, and Arvind Narayanan. 2017.  Semantics derived automatically from language corpora contain human-like biases.  _Science_ , 356(6334):183–186.
  * Conneau et al. (2018) Alexis Conneau, Guillaume Lample, Marc’Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou. 2018.  Word Translation Without Parallel Data.  In _Proceedings of ICLR 2018_.
  * Corbett (1991) Greville G Corbett. 1991.  Gender.
  * Corbett (2006) Greville G Corbett. 2006.  _Agreement_.  Cambridge University Press.
  * Cotterell et al. (2016) Ryan Cotterell, Hinrich Schütze, and Jason Eisner. 2016.  Morphological smoothing and extrapolation of word embeddings.  In _Proceedings of ACL_.
  * Finkelstein et al. (2002) Lev Finkelstein, Evgeniy Gabrilovich, Yossi Matias, Ehud Rivlin, Zach Solan, Gadi Wolfman, and Eytan Ruppin. 2002.  Placing search in context: The concept revisited.  _ACM Transactions on information systems_.
  * Gonen and Goldberg (2019) Hila Gonen and Yoav Goldberg. 2019.  Lipstick on a pig: Debiasing methods cover up systematic gender biases in word embeddings but do not remove them.  In _Proceedings of NAACL-HLT_.
  * Harris (1954) Zellig S Harris. 1954.  Distributional structure.  _Word_ , 10(2-3).
  * Hill et al. (2015) Felix Hill, Roi Reichart, and Anna Korhonen. 2015.  Simlex-999: Evaluating semantic models with (genuine) similarity estimation.  _Computational Linguistics_ , 41(4).
  * Leviant and Reichart (2015) Ira Leviant and Roi Reichart. 2015.  Separated by an un-common language: Towards judgment language informed vector space modeling.  _arXiv:1508.00106_.
  * Levy and Goldberg (2014) Omer Levy and Yoav Goldberg. 2014.  Dependency-based word embeddings.  In _Proceedings of ACL_.
  * Mikolov et al. (2013) Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013.  Efficient estimation of word representations in vector space.  _arXiv:1301.3781_.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014.  Glove: Global vectors for word representation.  In _Proceedings of EMNLP 2014_.
  * Salama et al. (2018) Rana Aref Salama, Abdou Youssef, and Aly Fahmya. 2018.  Morphological word embedding for arabic.  In _ACLing_.
  * Søgaard et al. (2018) Anders Søgaard, Sebastian Ruder, and Ivan Vulić. 2018.  On the limitations of unsupervised bilingual dictionary induction.  In _Proceedings of ACL_.
  * Vulić et al. (2017) Ivan Vulić, Nikola Mrkšić, Roi Reichart, Diarmuid Ó Séaghdha, Steve Young, and Anna Korhonen. 2017.  Morph-fitting: Fine-tuning word vector spaces with simple language-specific rules.  _arXiv:1706.00377_.
  * Youn et al. (2016) Hyejin Youn, Logan Sutton, Eric Smith, Cristopher Moore, Jon F. Wilkins, Ian Maddieson, William Croft, and Tanmoy Bhattacharya. 2016.  On the universal structure of human lexical semantics.  In _NIPS_.
  * Zalmout and Habash (2017) Nasser Zalmout and Nizar Habash. 2017.  Don’t throw those morphological analyzers away just yet: Neural morphological disambiguation for arabic.  In _Proceedings of EMNLP_. Association for Computational Linguistics.
  * Zhao et al. (2018) Jieyu Zhao, Yichao Zhou, Zeyu Li, Wei Wang, and Kai-Wei Chang. 2018.  Learning gender-neutral word embeddings.  _arXiv preprint arXiv:1809.01496_.
  * Zmigrod et al. (2019) Ran Zmigrod, Sebastian J Mielke, Hanna Wallach, and Ryan Cotterell. 2019.  Counterfactual data augmentation for mitigating gender stereotypes in languages with rich morphology.  _arXiv preprint arXiv:1906.04571_.

##  Appendix A Implementation Details

#### Morphological Analyzers

For Italian, we use Morph-
it!,111111http://tools.sslmit.unibo.it/doku.php?id=resources:morph-it a
lexicon of inflected forms with their lemma and morphological features. For
German, we use DEMorphy,121212https://github.com/DuyguA/DEMorphy which, given
a word, provides its full morphological analysis (or several, when applicable)
Altinok (2018).131313Since the analysis is fine-grained, when searching for a
different-gender word form, we do not require full match, but restrict
ourselves only to the following categories: CATEGORY, NUMERUS, PERSON, PTB_TAG
and TENSE.

#### Training Word Embeddings

We train 300d word embeddings with window size 4, on January 2018 wikipedia
dump141414https://dumps.wikimedia.org/ for all three languages. After
tokenization we get 2.2B (En), 463M (It) and 815M (De) tokens. We discard
words that do not appear at least 50 times, and are left with vocabulary sizes
of 360,386 (En), 161,144 (It) and 361,944 (De). We train using word2vecf Levy
and Goldberg (2014), which allows to change context words without affecting
target words.

##  Appendix B Manual Mapping for Italian

Tables 8 and 9 contain the manual mappings we used for Italian (see next
page).

##  Appendix C Qualitative Evaluation

As a qualitative evaluation, we take several words for SimLex-999 and look at
their top-10 nearest neighbor lists, before and after applying our method. In
Table 10 we show the top-10 lists for the words _palla_ (ball-feminine) in
Italian, and _diamant_ (diamond-masculine) in German. It is evident that the
words that are added to the list are better correlated with the target word
than those that are removed (see next page).

word | opposite-gender form
---|---
alla | [al, allo]
alle | [agli, ai]
colei | [colui]
costei | [costui]
esse | [essi]
dalla | [dallo, dal]
della | [dello, del]
delle | [dei, degli]
essa | [esso, egli]
impostala | [impostalo]
impostale | [impostagli]
la | [lo, gli, il]
lei | [lui]
nella | [nel, nello]
nelle | [nei, negli]
ognuna | [ognuno]
provocatele | [provocategli]
qualcuna | [qualcuno]
dalle | [dagli, dai]
sulla | [sullo, sul]
sulle | [sui, sugli]
una | [un, uno]
un’ | [un]
le | [lo, i, li]
riformatorie | [riformatori]
scatenatasi | [scatenatosi]
scatenatesi | [scatenato]
tutorie | [tutorio]
al | [alla]
agli | [alle]
ciascuno | [ciascuna]
colui | [colei]
costui | [costei]
dagli | [dalle]
dallo | [dalla]
dei | [delle]
dello | [della]
essi | [esse]
esso | [essa]
i | [le]
impostagli | [impostale]
impostalo | [impostala]
li | [le]
lo | [la, le]
lui | [lei]
nei | [nelle]
nel | [nella]
ognuno | [ognuna]
provocategli | [provocatele]
qualcuno | [qualcuna]
sui | [sulle]
sullo | [sulla]
ultro | [ultra]
ai | [alle]
allo | [alla]
dai | [dalle]
dal | [dalla]
degli | [delle]
del | [della]
egli | [essa]
gli | [la]
il | [la]
negli | [nelle]
sugli | [sulle]
sul | [sulla]
nello | [nella]
un | [una, un’]
uno | [una]

Table 8: word: opposite-gender-form mapping for Italian.

word | lemma
---|---
un’, un, una, uno | lemma1
la, lo, gli, il | lemma2
le, i, li | lemma3
alla, al, allo | lemma4
alle, agli, ai | lemma5
colei, colui | lemma6
costei, costui | lemma7
esse, essi | lemma8
dalla, dallo, dal | lemma9
della, dello, del | lemma10
delle, dei, degli | lemma11
essa, esso, egli | lemma12
impostala, impostalo | lemma13
impostale, impostagli | lemma14
lei, lui | lemma15
nella, nel, nello | lemma16
nelle, nei, negli | lemma17
ognuna, ognuno | lemma18
provocatele, provocategli | lemma19
ualcuna, qualcuno | lemma20
dalle, dagli, dai | lemma21
sulla, sullo, sul | lemma22
sulle, sui, sugli | lemma23
riformatorie, riformatori | lemma24
scatenatasi, scatenatosi | lemma25
scatenatesi, scatenato | lemma26
tutorie, tutorio | lemma27
ciascuno, ciascuna | lemma28
ultro, ultra | lemma29

Table 9: word:lemma mapping for Italian.

Italian | German
---|---
palla (ball-feminine) | diamant (diamond-masculine)
Orig | Debias | Orig | Debias
pallina | pallina | smaragd | smaragd
biglia (ball) | pallone | topas | korund
racchetta |  canestro (basket) | ultramarin | topas
pallone |  rimbalzo (rebound) | salmiak | ultramarin
stecca (splint) | racchetta |  grünspan (verdigris) | vitriol
bilia (marble) |  calciato (kicked) | vitriol |  saphir (sapphire)
dapples | schivata | korund | salmiak
bandierina (pennant) |  guantone (mitt) |  titan (titanium) |  perle (pearl)
schivata | battitore | aquamarin | aquamarin
battitore |  calciando (kicking) |  bornitrid (boron nitride) |  unedlen (base)

Table 10: Examples of top-10 nearest neighbor lists for words in Italian and
in German, before and after debiasing. In red (italic) are words that were
removed from the list, and in blue (underlined) are words that were added to
it. Translations to English (Google Translate) for the changed words are in
parenthesis, when different from source.


# Deterministic particle flows for constraining SDEs

Dimitra Maoutsa
Technical University of Berlin
& University of Potsdam
<EMAIL_ADDRESS>
&Manfred Opper
Technical University of Berlin
& University of Birmingham
<EMAIL_ADDRESS>

###### Abstract

Devising optimal interventions for diffusive systems often requires the
solution of the Hamilton-Jacobi-Bellman (HJB) equation, a nonlinear backward
partial differential equation (PDE), that is, in general, nontrivial to solve.
Existing control methods either tackle the HJB directly with grid-based PDE
solvers, or resort to iterative stochastic path sampling to obtain the
necessary controls. Here, we present a framework that interpolates between
these two approaches. By reformulating the optimal interventions in terms of
logarithmic gradients (_scores_) of two forward probability flows, and by
employing deterministic particle methods for solving Fokker-Planck equations,
we introduce a novel fully _deterministic_ framework that computes the
required optimal interventions in _one shot_.

##  1 Introduction

#### Constrained diffusions and optimal control.

Consider the problem of imposing constraints $\mathcal{C}$ to the state of a
stochastic system, whose _unconstrained_ dynamics are described by a
stochastic differential equation (SDE)

$dX_{t}=f(X_{t},t)dt+\sigma dW_{t},$ (1)

with drift
$f(x,t)\in\mathcal{R}^{d}\times\mathcal{R}\rightarrow\mathcal{R}^{d}$ and
diffusion coefficient $\sigma\in\mathcal{R}$.111For brevity, we restrict
ourselves to state- and time- independent scalar diffusions, but the framework
easily generalises to time-dependent multiplicative noise settings with non-
isotropic diffusion functions. For a time interval $[0,\,T]$, the constraints
$\mathcal{C}$ may pertain either the transient state of the system through a
path-penalising function
$U(x,t)\in\mathcal{R}^{d}\times\mathcal{R}\rightarrow\mathcal{R}$ for $t\leq
T$, or its terminal state $X_{T}$ through the function
$\chi(x)\in\mathcal{R}^{d}\rightarrow\mathcal{R}$.

One way to obtain the path probability measure $\mathbb{Q}$ of the
_constrained_ process is by reweighting paths $X_{0:T}$ generated from Eq.(1)
over the interval $[0,\,T]$. Path weights result from the Radon–Nikodym
derivative with respect to the path measure of the unconstrained process
$\mathbb{P}_{f}$

$\small\frac{d\mathbb{Q}}{d\mathbb{P}_{f}}(X_{0:T})=\frac{\chi(X_{T})}{Z}\exp\left[-\int_{0}^{T}U(X_{t},t)dt\right],$
(2)

where $Z$ is a normalising constant.

How shall we modify the system of Eq.(1) to incorporate the desired
constraints $\mathcal{C}$ into its dynamics, while also minimising the
relative entropy between the path distributions of the constrained and
unconstrained processes?

Problems of this form appear often in physics, biology, and engineering, and
are relevant for calculation of rare event probabilities [1, 2], latent state
estimation of partially observed systems [3, 4], or for precise manipulation
of stochastic systems to target states [5, 6] with applications on artificial
selection [7, 8], motor control [9], epidemiology, and more [10, 11, 12, 13,
14, 15]. Yet, although stochastic optimal control problems are prevalent in
most scientific fields, their numerical solution remains computationally
demanding for most practical problems.

The constrained process, defined by the weight of Eq.(2), can be also
expressed as a diffusion process with the same diffusion $\sigma$, but with a
modified time-dependent drift $g(x,t)$ [16, 17]. The computation of this drift
adjustment or control $u(x,t)\doteq g(x,t)-f(x,t)$ amounts to solving a
stochastic control problem to obtain the optimal control $u^{*}(x,t)$ that
minimises the expected cost

$\displaystyle\small\mathcal{J}(x,t)\doteq\min_{u}\mathbb{E}_{\mathbb{P}_{g}}\left[\int_{0}^{T}\left(\frac{1}{2\sigma^{2}}\|u(X_{t},t)\|^{2}+U(X_{t},t)\right)dt-\ln\chi(X_{T})\right].$
(3)

The expectation $\mathbb{E}_{\mathbb{P}_{g}}$ is over paths induced by the
constrained SDE $\;dX_{t}=g(X_{t},t)dt+\sigma dW_{t}.\;\;\;\
({\color[rgb]{1,0,1}4})$
This control setting is known as Path Integral- or Kullback-Leibler-control
(PI/KL-control)[4, 5, 18, 19]. Finding the exact optimal interventions for
general stochastic control problems amounts to solving the HJB equation [20],
a computationally demanding nonlinear PDE. Yet, for the PI-control problem,
the logarithmic Hopf-Cole transformation [21], ie.
${\mathcal{J}(x,t)=-\log(\phi_{t}(x))}$, linearises the HJB equation [5], and
the optimally adjusted drift becomes
$g(x,t)=f(x,t)+\sigma^{2}\nabla\ln\phi_{t}(x),$ (5)
$\frac{\partial\phi_{t}(x)}{\partial
t}+{\cal{L}}^{\dagger}_{f}\phi_{t}(x)-U(x,t)\phi_{t}(x)=0,$ (6) where
$\phi_{t}(x)$ is a solution to the backward PDE of Eq.(6) with terminal
condition $\phi_{T}(x)=\chi(x)$, and $\mathcal{L}^{\dagger}_{f}\phi(x)\doteq
f(x,t)\nabla\cdot\phi(x)+\frac{\sigma^{2}}{2}\nabla^{2}\phi(x)$ denotes the
_adjoint_ Fokker–Planck operator acting on $\phi(x)$.

The PDE of Eq.(6) is often treated either with grid based solvers [22, 23], or
with iterative stochastic path sampling schemes [19, 5, 24, 25]. Both
approaches suffer, in general, from high computational complexity with
increasing system dimension. (However note recent neural network advances
towards this direction [26, 27].)

##  2 Method

#### Constrained diffusion densities from backward smoothing.

To avoid directly solving the backward PDE (Eq. (6)), we view the marginal
density $q_{t}(x)$ of the constrained process as the smoothing density in an
inference setting. By considering Eq.(2) as a likelihood function, and
treating the constraints $U(x,t)$ and $\chi(x)$ as continuous time
observations of the process $X_{t}$, the path measure $\mathbb{Q}$, i.e. the
product of the a priori distribution $\mathbb{P}_{f}$ with the likelihood, can
be interpreted as the posterior distribution over paths that account for the
observations as soft constraints. Thus, in a similar vein to the
forward–backward smoothing algorithms for hidden Markov models [28, 29], we
factorise the marginal density into two terms that account for past and future
constraints separately

$q_{t}(x)\propto\rho_{t}(x)\phi_{t}(x).$ (7)

The density $\rho_{t}(x)$ satisfies the forward _filtering_ equation with
initial condition $\rho_{0}(x)$ (Eq.(8)), while the marginal constrained
density $q_{t}(x)$ fulfils a Fokker–Planck equation (Eq.(9))
$\frac{\partial\rho_{t}(x)}{\partial
t}={\cal{L}}_{f}\rho_{t}(x)-U(x,t)\rho_{t}(x),$ (8) $\frac{\partial
q_{t}(x)}{\partial t}={\cal{L}}_{g}q_{t}(x).$ (9) Here the Fokker–Planck
operator ${\cal{L}}_{g}$ is defined for the process with optimal drift
$g(x,t)$ (Eq.(5)).By replacing $\phi_{t}(x)$ with $q_{t}(x)/\rho_{t}(x)$ in
Eq.(5), we obtain a new representation of the optimal drift in terms of the
logarithmic gradients (_score functions_) of two forward probability flows,
$q_{t}(x)$ and $\rho_{t}(x)$

$\small g(x,t)=f(x,t)+\sigma^{2}\Big{(}\nabla\ln
q_{t}(x)-\nabla\ln\rho_{t}(x)\Big{)}.$ (10)

This formulation still requires knowledge of the unknown $\nabla\ln q_{t}(x)$.
Yet, by inserting Eq.(10) into Eq.(9), and introducing a time-reversion
through the variable $\tau=T-t$, we obtain a Fokker–Planck equation for the
flow $\tilde{q}_{\tau}(x)=q_{T-\tau}(x)$

$\small\frac{\partial\tilde{q}_{\tau}(x)}{\partial\tau}=-\nabla\cdot\Big{(}\big{(}\sigma^{2}\nabla\ln\rho_{T-\tau}(x)-f(x,T-\tau)\big{)}\tilde{q}_{\tau}(x)\Big{)}+\frac{\sigma^{2}}{2}\nabla^{2}\tilde{q}_{\tau}(x),$
(11)

that depends only on the time-reversed forward flow $\rho_{t}(x)$, with
$\tilde{q}_{0}\propto\rho_{T}(x)\chi(x)$. Thus, for the exact computation of
the optimal controls
${u^{*}(x,t)=\sigma^{2}\big{(}\nabla\ln\tilde{q}_{T-t}(x)-\nabla\ln\rho_{t}(x)\big{)}}$,
we require the logarithmic gradients of two forward probability flows
$\tilde{q}_{T-t}(x)$ and $\rho_{t}(x)$.

#### Deterministic particle dynamics.

To sample the two forward flows $\rho_{t}(x)$ and $\tilde{q}_{T-t}(x)$ (Eq.(8)
and Eq.(9)) we employ a recent deterministic particle framework for solving
Fokker–Planck equations [30], modified to fit our purposes. We approximate
$\rho_{t}(x)$ with the empirical distribution
$\hat{\rho}_{t}(x)\approx\frac{1}{N}\sum_{i=1}^{N}\delta\left(x-X^{(i)}_{t}\right)$
constructed from an ensemble of $N$ "particles" $X^{(i)}_{t}$.

Figure 1: Schematic of the proposed control framework.

For flows _without_ path costs $\left(U(x,t)\equiv 0\right)$, we express the
particle dynamics as a system of ordinary differential equations (ODEs) [30]

$dX^{(i)}_{t}=f(X^{(i)}_{t},t)\,dt-\nicefrac{{\sigma^{2}}}{{2}}\hat{\nabla}\ln\hat{\rho}_{t}(X^{(i)}_{t})\,dt,$
(12)

where $\hat{\nabla}\ln\hat{\rho}_{t}(X^{(i)}_{t})$ denotes the estimated score
function of the empirical distribution $\hat{\rho}_{t}(x)$.

For flows _with_ path costs $\left(U(x,t)\neq 0\right)$, the flow dynamics in
terms of operator exponentials222In the second equality, we considered that
for small $\delta t$ the commutator of the two operators ${\cal{L}}_{f}$ and
$U(x,t)$ is negligible. reads

$\displaystyle\rho_{t+\delta t}(x)$ $\displaystyle=e^{\delta
t({\cal{L}}_{f}-U(x,t))}\rho_{t}(x)$ (13) $\displaystyle=e^{-\delta
tU(x,t)}e^{\delta t{\cal{L}}_{f}}\rho_{t}(x)+\mathcal{O}((\delta t)^{2}).$

We interpret Eq.(13) as the concatenation of two processes: a density
propagation by the uncontrolled Fokker–Planck equation, followed by a
multiplication by a factor $e^{-\delta tU(x,t)}$. To simulate this two-stage
process for a time interval $\delta t$, we first evolve the particles
following Eq.(12) to auxiliary positions $Y^{(i)}_{t}$ and assign to each
particle $i$ a weight $\Omega_{i}(t)\propto e^{-\delta tU(Y^{(i)}_{t},t)}.$ To
transform the weighted particles to unweighted ones, we employ the ensemble
transform particle filter [31]. This method provides an optimal transport map
that _deterministically_ transforms an ensemble of weighted particles into an
ensemble of uniformly weighted ones by maximising the covariance between the
two ensembles.

#### Sparse kernel score function estimator.

To estimate the scores of the flows $\rho_{t}(x)$ and $\tilde{q}_{t}(x)$ for
the particle evolution (Eq.(12)) and the estimation of optimal controls
$u^{*}(x,t)$, we employ a _sparse kernel score function estimator_ [30]. More
precisely, we obtain each dimensional component $a\in[1,\dots,d]$ of
$\nabla\ln\rho(x)$ from the solution of the _variational_ problem of
minimising the functional $\mathcal{I}_{\alpha}[h,\rho]$

$\vspace{-0pt}{\partial_{\alpha}}\ln\rho(x)=\arg\min_{h}\;{\cal{I}}_{\alpha}[h,\rho]{(x)}=\arg\min_{h}\;\int\rho(x)\left(2\partial_{\alpha}h(x)+h^{2}(x)\right)dx.$
(14)

To regularise this optimisation we assume that $h$ belongs to a Reproducing
Kernel Hilbert Space associated with a radial basis function kernel, and
employ a _sparse kernel approximation_ by expressing $h$ as a linear
combination of the kernel evaluated at $M\ll N$ inducing points $Z_{i}$,
$h(x)=\sum_{i=1}^{M}b_{i}K(Z_{i},x)$. (See AppendixA.1 for the exact
formulation of the estimator.)

Figure 2: Deterministic particle flow (DPF) control provides optimal
interventions to drive the system to target state (grey cross). (a.) Example
controlled trajectory (blue-yellow) successfully reaches target, while an
uncontrolled one (orange) remains in the vicinity of initial state for the
same time interval. (b.) Agreement between summary statistics of marginal
densities estimated from $1000$ trajectories controlled by DPF (purple) and
PICE (grey) (transient mean $\mu_{\hat{q}_{t}}$ and standard deviation
$\sigma_{\hat{q}_{t}}$). Orange indicates mean and standard deviation of
$1000$ uncontrolled trajectories. (Used $N=400$ particles for DPF, and $N=500$
for PICE to obtain the optimal controls.) (c.) Comparison of (upper)
(logarithmic) control energy, and (lower) deviation of terminal state from
target for each controlled trajectory (dots) with interventions computed
according to DPF (magenta) and PICE (grey). Light grey lines identify the mean
of each quantity over the $1000$ trajectories. (d.)(upper) Control energy, and
(lower) terminal error for increasing particle number $N$. (inducing point
number for DPF magenta: $M=50$, green: $M=100$ ). Grey line indicates the
performance of PICE in the same setting. (e.-h.) Same as (a.-d.) with
additional path constraint $U((x,y),t)=10^{3}(y-1)^{2}$.

##  3 Numerical Experiments

We employed our method (deterministic particle flow control-DPF) on a model
that can be thought of as describing the _mean_ phenotype $(x,y)$ of a
population evolving on a phenotypic landscape $F$ under adaptive pressures
$f([x,y],t)=\nabla F(x,y)=\nabla((1-x)^{2}+(y-x^{2})^{2})$ and genetic drift
represented by white noise [7].(See Appendix for more biological relevance.)

Starting from initial state $\textbf{x}_{0}=(-1,1)$, we evaluate our framework
on two scenarios: one with only terminal constraints
$\chi(\mathbf{x})=\delta(\mathbf{x}-\mathbf{x}^{*})$, with
$\mathbf{x}^{*}=(1,1)$ (Figure 2(a.-d.)), and one with the same terminal
constraints coupled with a path cost that limits fluctuations along the $y$
axis (Figure 2(e.-h.)). In both settings, we benchmark our method against the
path integral cross entropy method (PICE) [24], by comparing summary
statistics, control costs $\|u(\mathbf{x},t)\|^{2}_{2}$, and deviations from
target $\|X_{T}-\mathbf{x}^{*}\|^{2}$ of $1000$ independent trajectories
controlled by each framework (purple:DPF, grey:PICE).

Our method successfully controlled the system towards the predefined target
($\mathbf{x}^{*}$-grey cross) (Figure 2 a.,e.), and showed complete agreement
with PICE in terms of the transient mean and standard deviation of the
marginal densities $q_{t}(x)$ captured by the $1000$ trajectories controlled
with each method. Comparing the control effort characterising the optimality
of the interventions (Figure 2 c.,g.), both methods dissipated comparable
energy with DPF showing slightly larger variance among individual
trajectories. Nevertheless, by examining the terminal errors, DPF was
consistently more accurate and precise in reaching the target. Comparing the
performance of both methods for increasing particle number employed for
obtaining the controls, our approach delivered more efficient controlled from
PICE for small number of particles ($N=500$), while both methods were
comparable for increasing particle number (Figure 2 d.). These results suggest
that our method delivers equally optimal controls with PICE in one-shot, while
it is also relatively more accurate in reaching the targets.

##  4 Conclusions

Forward-backward algorithms for smoothing densities have been extensively used
in hidden Markov models. Here by relying on the duality between inference and
control [32, 19, 33, 34], we borrowed ideas from the inference literature to
derive non-iterative sampling schemes for constraining diffusive systems. By
employing score function estimation, and recent deterministic approaches for
solving Fokker–Planck equations, we proposed a non-iterative stochastic
control framework that relies solely on deterministic particle dynamics. Our
method interpolates between classical space-discretising PDE solutions that
are inherently non-iterative, and stochastic Monte Carlo ’particle’ methods
that rely on the Feynaman-Kac formula to obtain PDE solutions through sample
paths.

The major limitation in applying our approach more broadly in higher
dimensional systems is the curse of dimensionality. The number of particles
required to provide enough evidence for accurate score estimation increases
with system dimension, and more advanced methods of model reduction shall be
combined with the present work. A further computational bottleneck when path
constraints are pertinent is the computational complexity of ensemble
transform particle filter algorithm ($\mathcal{O}(N^{3}\log N)$ [35]).Yet,
there is room for improvement here by applying entropy regularised approaches
for particle reweighting [36].

## References

  * [1] Carsten Hartmann and Christof Schütte.  Efficient rare event simulation by optimal nonequilibrium forcing.  Journal of Statistical Mechanics: Theory and Experiment, 2012(11):P11004, 2012.
  * [2] Raphaël Chetrite and Hugo Touchette.  Variational and optimal control representations of conditioned and driven processes.  Journal of Statistical Mechanics: Theory and Experiment, 2015(12):P12001, 2015.
  * [3] Jin Won Kim and Prashant G Mehta.  An optimal control derivation of nonlinear smoothing equations.  In Proceedings of the Workshop on Dynamics, Optimization and Computation held in honor of the 60th birthday of Michael Dellnitz, pages 295–311. Springer, 2020.
  * [4] Emanuel Todorov.  Efficient computation of optimal actions.  Proceedings of the National Academy of Sciences of the United States of America, 106(28):11478–11483, 2009.
  * [5] Hilbert J Kappen.  Linear theory for control of nonlinear stochastic systems.  Physical Review Letters, 95(20):200201, 2005.
  * [6] Daniel K Wells, William L Kath, and Adilson E Motter.  Control of stochastic and induced switching in biophysical networks.  Physical Review X, 5(3):031036, 2015.
  * [7] Armita Nourmohammad and Ceyhun Eksin.  Optimal evolutionary control for artificial selection on molecular phenotypes.  Physical Review X, 11(1):011044, 2021.
  * [8] Ziwei Zhong, Brandon G Wong, Arjun Ravikumar, Garri A Arzumanyan, Ahmad S Khalil, and Chang C Liu.  Automated continuous evolution of proteins in-vivo.  ACS synthetic biology, 9(6):1270–1276, 2020.
  * [9] Ta-Chu Kao, Mahdieh S Sadabadi, and Guillaume Hennequin.  Optimal anticipatory control as a theory of motor preparation: a thalamo-cortical circuit model.  Neuron, 109(9):1567–1581, 2021.
  * [10] Alexandre Iolov, Susanne Ditlevsen, and André Longtin.  Stochastic optimal control of single neuron spike trains.  Journal of Neural Engineering, 11(4):046004, 2014.
  * [11] Stephen H Scott.  Optimal feedback control and the neural basis of volitional motor control.  Nature Reviews Neuroscience, 5(7):532–545, 2004.
  * [12] Espen Bernton, Jeremy Heng, Arnaud Doucet, and Pierre E Jacob.  Schrödinger Bridge Samplers.  arXiv preprint arXiv:1912.13170, 2019.
  * [13] Francisco Vargas, Pierre Thodoroff, Neil D Lawrence, and Austen Lamacraft.  Solving Schrödinger Bridges via Maximum Likelihood.  arXiv preprint arXiv:2106.02081, 2021.
  * [14] Ioannis Exarchos and Evangelos A Theodorou.  Stochastic optimal control via forward and backward stochastic differential equations and importance sampling.  Automatica, 87:159–165, 2018.
  * [15] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.  Score-based generative modeling through stochastic differential equations.  arXiv preprint arXiv:2011.13456, 2020.
  * [16] Igor Vladimirovich Girsanov.  On transforming a certain class of stochastic processes by absolutely continuous substitution of measures.  Theory of Probability and Its Applications, 5(3):285–301, 1960\.
  * [17] Bernt Øksendal.  Stochastic differential equations.  Springer, 2003.
  * [18] Evangelos A Theodorou and Emanuel Todorov.  Relative entropy and free energy dualities: Connections to path integral and kl control.  In 2012 IEEE 51st IEEE Conference on Decision and Control (cdc), pages 1466–1473. IEEE, 2012.
  * [19] Hilbert J Kappen, Vicenç Gómez, and Manfred Opper.  Optimal control as a graphical model inference problem.  Machine Learning, 87(2):159–182, 2012.
  * [20] Richard Bellman.  Dynamic programming and Lagrange multipliers.  Proceedings of the National Academy of Sciences of the United States of America, 42(10):767, 1956.
  * [21] Wendell H Fleming.  Exit probabilities and optimal stochastic control.  Applied Mathematics and Optimization, 4(1):329–346, 1977.
  * [22] Jochen Garcke and Axel Kröner.  Suboptimal feedback control of PDEs by solving HJB equations on adaptive sparse grids.  Journal of Scientific Computing, 70(1):1–28, 2017.
  * [23] Mario Annunziato and Alfio Borzì.  A Fokker–Planck control framework for multidimensional stochastic processes.  Journal of Computational and Applied Mathematics, 237(1):487–507, 2013.
  * [24] Hilbert Johan Kappen and Hans Christian Ruiz.  Adaptive importance sampling for control and inference.  Journal of Statistical Physics, 162(5):1244–1266, 2016.
  * [25] Wei Zhang, Han Wang, Carsten Hartmann, Marcus Weber, and Christof Schuette.  Applications of the cross-entropy method to importance sampling and optimal control of diffusions.  SIAM Journal on Scientific Computing, 36(6):A2654–A2672, 2014.
  * [26] Nicolas Macris and Raffaele Marino.  Solving non-linear Kolmogorov equations in large dimensions by using deep learning: a numerical comparison of discretization schemes.  arXiv preprint arXiv:2012.07747, 2020.
  * [27] Zongyi Li, Nikola Kovachki, Kamyar Azizzadenesheli, Burigede Liu, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar.  Fourier neural operator for parametric partial differential equations.  International Conference on Learning Representations, 2020.
  * [28] Yariv Ephraim and Neri Merhav.  Hidden markov processes.  IEEE Transactions on Information Theory, 48(6):1518–1569, 2002\.
  * [29] Leonard E Baum, Ted Petrie, George Soules, and Norman Weiss.  A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains.  The Annals of Mathematical Statistics, 41(1):164–171, 1970.
  * [30] Dimitra Maoutsa, Sebastian Reich, and Manfred Opper.  Interacting particle solutions of Fokker–Planck equations through gradient–log–density estimation.  Entropy, 22(8):802, 2020.
  * [31] Sebastian Reich.  A nonparametric ensemble transform method for Bayesian inference.  SIAM Journal on Scientific Computing, 35(4):A2013–A2024, 2013.
  * [32] Emanuel Todorov.  General duality between optimal control and estimation.  In 2008 47th IEEE Conference on Decision and Control, pages 4286–4292. IEEE, 2008.
  * [33] Sergey Levine.  Reinforcement learning and control as probabilistic inference: Tutorial and review.  arXiv preprint arXiv:1805.00909, 2018.
  * [34] Hagai Attias.  Planning by probabilistic inference.  In International Workshop on Artificial Intelligence and Statistics, pages 9–16. PMLR, 2003.
  * [35] Dimitris Bertsimas and John N Tsitsiklis.  Introduction to linear optimization, volume 6.  Athena Scientific Belmont, MA, 1997.
  * [36] Adrien Corenflos, James Thornton, George Deligiannidis, and Arnaud Doucet.  Differentiable particle filtering via entropy-regularized optimal transport.  In International Conference on Machine Learning, pages 2100–2111. PMLR, 2021.
  * [37] Ofir Pele and Michael Werman.  Fast and robust earth mover’s distances.  In 2009 IEEE 12th International Conference on Computer Vision, pages 460–467. IEEE, September 2009.
  * [38] Michael L Waskom.  Seaborn: statistical data visualization.  Journal of Open Source Software, 6(60):3021, 2021.

##  Appendix A Appendix

###  A.1 Score function estimator

The empirical formulation of the score estimator from $N$ particles
representing an unknown density $\rho(x)$ is

${\partial_{\alpha}}\ln\rho(x)\approx\sum_{i=1}^{M}\left(\sum^{M}_{k=1}B_{ik}(x)\sum^{N}_{l=1}\nabla_{X_{l}}K(X_{l},Z_{k})\right),$
(15)

with $B_{ik}$ denoting the $i$-th row, and $k$-th column of the matrix $B(x)$
defined as

$B(x)\doteq K(x,\mathcal{Z})\left[\lambda
I+(K(\mathcal{Z},\mathcal{Z}))^{-1}(K(\mathcal{X},\mathcal{Z}))^{\top}(K(\mathcal{X},\mathcal{Z}))\right]^{-1}(K(\mathcal{Z},\mathcal{Z}))^{-1},$
(16)

where $\mathcal{X}=\\{X_{i}\\}^{N}_{i=1}$ and
$\mathcal{Z}=\\{Z_{i}\\}^{M}_{i=1}$ denote the sets of samples and inducing
points respectively, while $I$ stands for an $M\times M$ identity matrix.
(Here we set the regularising constant $\lambda=10^{-3}$). We used an gaussian
kernel

$K(x,x^{\prime})=\exp\left[-\frac{1}{2{l}^{2}}\|x-x^{\prime}\|^{2}\right],$
(17)

where the lengthscale $l$ was set to two times the standard deviation of the
particle ensemble for each time step.

###  A.2 Implementation details

Here we provide the algorithm for computing optimal interventions
$u^{*}(x,t)$. Since the initial conditions for the flows $\rho_{t}(x)$ and
$\tilde{q}_{t}(x)$ are delta functions centered around the initial and target
state, $x_{0}$ and $x_{1}$, i.e $\rho_{0}(x)=\delta(x-x_{0})$ and
$\tilde{q}_{t}(x)=\delta(x-x_{1})$, we employ a single stochastic step at the
beginning of each (forward and time-reversed) flow propagation. Since the
inducing point number $M$ employed in the gradient–log–density estimation is
considerably smaller than sample number $N$, i.e., $M\ll N$, the overall
computational complexity of a _single_ gradient-log-density evaluation amounts
to $\mathcal{O}\left(N\,M^{2}\right)$. We perform Euler integration for the
ODEs, and Euler-Maruyama for stochastic simulations. For all numerical
integrations we employ $dt=10^{-3}$ discretisation step. For the numerical
experiments with path constraints, we solved the optimal transport problem
with the implementation of FastEMD [37].

For some of the visualisations of our results we used the Seaborn [38] python
toolbox.