# Concept-Best-Matching:
Evaluating Compositionality in Emergent Communication

Boaz Carmeli, Yonatan Belinkov, Ron Meir
Technion – Israel Institute of Technology
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Artificial agents that learn to communicate in order to accomplish a given
task acquire communication protocols that are typically opaque to a human. A
large body of work has attempted to evaluate the emergent communication via
various evaluation measures, with _compositionality_ featuring as a prominent
desired trait. However, current evaluation procedures do not directly expose
the compositionality of the emergent communication. We propose a procedure to
assess the compositionality of emergent communication by finding the best-
match between emerged words and natural language concepts. The best-match
algorithm provides both a global score and a translation-map from emergent
words to natural language concepts. To the best of our knowledge, it is the
first time that such direct and interpretable mapping between emergent words
and human concepts is provided.

##  1 Introduction

Artificial agents that learn to communicate for accomplishing a given task
acquire communication protocols. In the common setting, a sender observes a
set of objects and sends a message to a receiver, which then needs to identify
the correct target objects out of a set of distractors. The two agents learn a
communication protocol over discrete vocabulary of atoms, termed “words”. The
emergent communication (EC) is typically opaque to a human. As a result, a
large body of work has attempted to characterize the emergent communication in
light of natural language (NL) traits, such as compositionality (Hupkes et
al., 2020; Chaabouni et al., 2020), systematic generalization (Vani et al.,
2021), pragmatism (Andreas and Klein, 2016; Zaslavsky et al., 2021), and more.

Figure 1: The multi-target shape game. (a) At each turn, the sender is given a
set of images, a subset of them marked as targets by an Oracle. (b) Sender
generates messages $[w_{1},w_{2}]$ for the blue-triangle (turn 1) and
$[w_{2},w_{3}]$ for the red-triangle (turn 2). (c) During evaluation, we
construct a bipartite graph of words generated by the sender and concepts
provided by the Oracle for each turn. (d) The best-match algorithm matches EC
words to NL concepts and provides the CBM score. In this example, all EC words
are matched with NL concepts, resulting in a CBM score of $1.0$.

Chief among these is compositionality, which enables the construction of
complex meanings from the meaning of parts Li and Bowling (2019). However,
quantifying compositionality in EC is notoriously difficult Lazaridou et al.
(2018). In fact, recent studies found that common compositionality measures in
EC, e.g., topographic similarity Brighton and Kirby (2006); Li and Bowling
(2019), do not correlate well with success in the task (Chaabouni et al.,
2021; Yao et al., 2022). Moreover, while seeking to assess an opaque protocol,
common evaluation measures in EC are opaque themselves—they do not provide a
human-interpretable characterization of the compositionality of the
communication.

This work develops a method that characterizes how compositional an EC is. Our
method is founded on the key insight that, in an EC setting, a communication
is compositional if agents communicate successfully via complex messages
formed of simple atoms _and_ these atoms are mapped to NL concepts. Our
evaluation is based on the classical best-match algorithm Hopcroft and Karp
(1973). Given a set of EC atoms and a set of NL concepts, we construct a bi-
partite graph and seek the optimal one-to-one mapping between words and
concepts. A perfectly compositional EC would yield a perfect match, where
every EC atom is mapped to exactly one NL concept. See Figure 1 for an
illustration.

We experiment with the proposed procedure in two EC settings and compare it to
two popular evaluation measures. We demonstrate that our approach provides a
fine-grained characterization of emergent protocols, exposing their strengths
and weaknesses, while other measures only provide coarse, opaque scores.
According to our evaluation, state-of-the-art communication methods do not
achieve satisfactory results.

##  2 Background

###  2.1 Emergent Communication Setup

We follow a recent setup suggested by Mu and Goodman (2021), where a sender
needs to communicate with a receiver about a _set of target objects_ out of a
larger set of candidate objects. The sender sends a message to the receiver,
which uses it to distinguish targets from distractor objects. For example, to
identify all red triangles out of objects with different shapes and colors.
This setup is more conducive to emergence of compositional communication than
the classical referential game Lazaridou et al. (2017). Senders in this setup
need to form a generalization rather than merely transmit the identity of a
single target.

Formally, assume a world ${\mathbb{X}}$, where each object is characterised by
$n$ feature–value pairs (FVPs), $\langle
f_{1}:v_{1},\ldots,f_{n}:v_{n}\rangle$, with feature $i$ having $k_{i}$
possible values, $v_{i}\in\\{f_{i}[1],\ldots,f_{i}[k_{i}]\\}$. For instance,
the Shape world Kuhnle and Copestake (2017) has objects like
$\langle$shape:triangle,color:red$\rangle$. Labeling rules are boolean
expressions over these FVPs.111In this work we only use conjunctive
expressions. Each rule $l:{\mathbb{X}}\mapsto\\{0,1\\}$ labels each object as
$0$ or $1$. For instance, the rule Red Triangle labels all red triangles as
positive and all other objects as negative. We identify the rule Red Triangle
with the NL _phrase_ “red triangle”, which comprises the _concepts_ “red” and
“triangle”.

At each turn of the game, we draw a set of candidate objects
$\tilde{{\mathbb{X}}}\subset{\mathbb{X}}$ that is made of target objects,
${\mathbb{T}}$, which obey the rule, and distractors, ${\mathbb{D}}$, which do
not: $l(x)=1$ if $x\in{\mathbb{T}}$ and $l(x)=0$ if $x\in{\mathbb{D}}$.

The sender encodes the set of target objects ${\mathbb{T}}$ into a dense
representation ${\bm{u}}^{s}\in{\mathbb{R}}^{d}$, and generates a message $m$,
a sequence of _words_ from some vocabulary. The receiver encodes each
candidate object $x\in{\mathbb{X}}$ into a representation
${\bm{u}}^{r}_{x}\in{\mathbb{R}}^{d}$. It decodes the message $m$ into a
representation ${\bm{z}}\in{\mathbb{R}}^{d}$ and computes a matching score
between each encoded candidate and the message representation,
$g({\bm{z}},{\bm{u}}^{r}_{x})$. A candidate is predicted as a target if its
score is $>0.5$. The entire system—sender and receiver networks—is trained
jointly with a binary cross entropy on correctly identifying each target.

###  2.2 Compositionality in EC

Various measures have been proposed to evaluate if an EC protocol is
compositional. We mention a few prominent ones below. However, while trying to
capture the idea that a complex meaning uses the meaning of its parts,
previous measures fail to provide a concrete _mapping of parts_ —EC words and
NL concepts. We say an emergent communication is compositional if the
following conditions hold:

  1. 1.

EC words are mapped to NL concepts.

  2. 2.

A complex EC message is composed of simple EC words.

  3. 3.

Agents communicate successfully via complex messages.

  4. 4.

An EC message composed of words has the same meaning as an NL phrase composed
of the respective concepts.

Being able to compose EC words while preserving their NL meaning allows agents
to generalize to new data while using interpretable communication.

###  2.3  Compositionality Evaluations in EC

We briefly describe two notable measures of compositionality in EC. Appendix A
gives more details.

Topographic Similarity (TopSim) Brighton and Kirby (2006) measures how well
messages align with object representations. Given a set of objects and their
EC messages, calculate a matrix of distances between every two messages and a
separate matrix of distances between every two object representations. TopSim
is the Spearman correlation of the two distance matrices.

TopSim is a global metric that does not require a reference language and can
be applied to any EC setup. However, recent studies found that TopSim does not
correlate well with success in the task being played (Chaabouni et al., 2021;
Yao et al., 2022). More importantly, it does not provide a mapping between EC
words and NL concepts, and thus cannot directly assess compositionality.

Adjusted Mutual Information (AMI) Vinh et al. (2009) measures the MIT between
a set of EC messages and a corresponding set of NL phrases, adjusted for
chance. Mu and Goodman (2021) showed AMI is a better compositionality measure
than TopSim, as it directly assesses the MI between a message and its NL
phrases. Still, AMI operates at the level of messages and phrases, rather than
atomic words and concepts, respectively.

##  3 Concept Best Matching

Our key insight is that compositionality requires a mapping between words
(atomic parts of EC messages) and concepts (a set of FVPs) that compose NL
phrases. Given an evaluation set of examples $D$, consider their corresponding
EC messages ${\mathbb{M}}$ and NL phrases ${\mathbb{L}}$. Let ${\mathbb{W}}$
denote the set of unique words in ${\mathbb{M}}$, and ${\mathbb{V}}$ the set
of unique FVPs in ${\mathbb{L}}$. Let $\\{w\\}_{i}$, $\\{v\\}_{i}$ be the sets
of words and FVPs in sample $i$, and $m_{i}=|\\{w\\}_{i}|,l_{i}=|\\{v\\}_{i}|$
their sizes. We construct a weighted bipartite graph
${\mathcal{G}}=(({\mathbb{W}},{\mathbb{V}}),\mathbb{E})$ with words on one
side and FVPs on the other side. Edges $\mathbb{E}$ are defined by the
evaluation set. The weight $q_{e}$ of edge $e_{ij}$ is the number of times
word $i$ appeared in a message that the sender transmitted for a labeling rule
with FVP $j$. This construction reflects the intuition that we do not know the
correct mapping between words and FVPs (concepts). See Figure 1 for an
example.

###  3.1 Best Match Algorithm

Given the graph ${\mathcal{G}}$, we seek an optimal pairing between words and
concepts (FVPs), such that no two edges share the same word nor the same
concept. The score of a match ${\mathbb{B}}\subseteq\mathbb{E}$ is the sum of
its edge weights, $\sum_{e\in{\mathbb{B}}}q_{e}$. The best match,
$\mathrm{BM}=\mathrm{BM}({\mathcal{G}})$, maximizes this score:

$\vspace{-2pt}\text{BM}=\operatorname*{argmax}_{{\mathbb{B}}}\sum_{e\in{\mathbb{B}}}q_{e}\hskip
14.22636pt$ (1)

Such an ideal mapping is fully interpretable. A high score indicates that the
agents learned to generate a unique EC word for each NL concept.

Normalizing the BM score by the number of symbols and words, $Q=\sum_{i\in
D}\max(|m_{i}|,|l_{i}|)$, guarantees that $\mathrm{BM}\in[0,1]$.222In
practice, the lowest bound is $q_{\tilde{e}}/Q$, where ${\tilde{e}}$ is the
edge with the highest weight in ${\mathcal{G}}$. The best match for a weighted
bipartite graph can be found efficiently by the Hungarian algorithm Kuhn
(1955); Hopcroft and Karp (1973).

##  4 Experimental Setup

NL EC Top Sim Best Match Com $l$ $d$ Cons Phrs $\\#w$ $\\#m$ Acc AMI CBM Amb
Para Unm Shape GS 1 17 17 17 11 11 0.84 0.44 0.76 0.62 0.37 0.01 0.25 QT 1 5
17 17 26 26 0.87 0.39 0.85 0.52 0.41 0.08 0 GS 4 17 17 34 16 226 0.78 0.34
0.38 0.52 0.48 0 0.01 QT 4 5 17 34 26 187 0.83 0.23 0.37 0.55 0.37 0.08 0
Thing GS 1 50 50 50 18 18 0.86 0.45 0.72 0.38 0.62 0 0.55 QT 1 6 50 50 50 50
0.92 0.07 0.74 0.73 0.25 0.02 0 GS 4 50 50 901 36 198 0.63 0.33 0.03 0.24 0.76
0 0.28 QT 4 6 50 901 64 450 0.77 0.14 0.05 0.23 0.69 0.08 0

Table 1: Results for Shape and Thing games with Gumbel-Softmax (GS) or
Quantized (QT) communication using rules of length $l$ and words of length
$d$, showing number of unique NL concepts (Cons) and phrases (Phrs) and EC
words ($\\#w$) and messages ($\\#m$). TopSim and AMI give only coarse scores.
Our method gives the best match score (CBM) and rates of Ambiguities (Amb),
Paraphrases (Para), and Unmatched concepts (Unm).

We experiments with agents that learn to play multi-target referential games,
introduced by Mu and Goodman (2021) and described in Section 2.1. All
experiments reported in Table 1 have the number of possible words $\geq$ the
number of concepts, in each game, to allow perfect match of words to concepts.
In Appendix D we report more experiments with sub-optimal configurations.

#### Datasets.

We experiment with two datasets, described briefly here; Appendix B has more
details.
(1) Shape: A visual reasoning dataset Kuhnle and Copestake (2017) of objects
over a black background. Our version of the dataset contains four attributes:
shape, color, and horizontal and vertical positions. Overall, the Shape
dataset contains 17 concepts, and a maximal labeling rule of 4 FVPs.
(2) Thing: A synthetic dataset of 100,000 objects. Each object has five
attributes, each with 10 possible values. Overall, the Thing datasets contains
50 concepts and a maximal labeling rule of 5 FVPs.

#### Communication Channel.

We train the system with two types of communication channels: the popular
Gumbel-Softmax (GS) Havrylov and Titov (2017); Jang et al. (2017) and
quantized communication (QT) Carmeli et al. (2022). In GS, each word is a
$d$-dimensional one-hot vector. In QT, each word is a $d$-dimensional binary
vector. QT was shown to be superior and easier to optimzie compared to GS in
EC games. In both cases we use a recurrent network to generate multi-word
messages. Appendix C has implementation details.

$w_{3}$$w_{7}$$w_{2}$$w_{9}$$w_{5}$$w_{6}$$w_{8}$$w_{4}$$w_{1}$$w_{0}$●⬬■❚▲

$\top$

$\mid$

$\bot$

$\top$$\bot$4884387384984704178 Figure 2: The
$\text{word}\leftrightarrow\text{FVP}$ best-match graph for the Shape game (GS
communication, $l=1$). The algorithm matched just $10$ concepts to EC words
out of $17$ possible concepts.

##  5 Results

Table 1 shows results on several configurations of the two games. As expected,
accuracy degrades as the task becomes more difficult, with longer labeling
rules. QT communication yields better task accuracy than GS, consistent with
Carmeli et al. (2022). TopSim is not well correlated with accuracy, as found
in prior work (Section 2.3). AMI and CBM are more correlated with accuracy.
With long messages and labeling rules ($l=4$), AMI is less correlated with
accuracy. This may be explained by AMI operating at the level of whole
messages and labeling rules—AMI struggles with large numbers of unique
messages and NL phrases. In contrast, CBM assesses word-to-concept matching,
so it is less affected by long messages and rules. However, AMI and CBM are
well correlated (Pearson $0.7$ and $0.79$ on the Shape and Thing games).

The table also shows the rate of ambiguities and paraphrases, exposed by our
method. Ambiguities happen when the same EC word is mapped to different
concepts. Table 1 shows higher rates of ambiguities in GS compared to QT
communication, and in longer rules. Paraphrases are EC words that do not have
a best-matched concept node. Paraphrases occur more with QT, which enables 32
and 64 unique EC words for the Shape and Thing games, while these games have
only 17 and 50 NL concepts, respectively. GS allows setting the number of
unique words equal to number of concepts, thus is less exposed to this sub-
optimal phenomenon.

Finally, Unmatched concepts have no matching EC word. They result from a too
narrow or underutilized channel. As Table 1 shows, GS communication suffers
from a high rate of unmatched concepts (up to $0.5$). This phenomenon can be
observed by the low # of unique words (18) compared to # of unique concepts
(50) for the Thing game with GS and $l=1$. QT has a sufficient number of words
and thus no unmatched concepts.

#### Example Match.

Beyond global scores, the CBM provides an interpretable _translation graph_ ,
which maps EC words to NL concepts, facilitating insights on reasons for sub-
optimal communication. Figure 2 shows an example graph for the Shape game with
GS communication.333The exact configuration is given in Table 1, first row. As
seen, the algorithm successfully matched $10$ EC words to $10$ concepts. The
sender generated 11 unique words in this experiment, so one word do not
matched to any concept even in this narrow-channel setup.

##  6 Conclusion

We proposed a new procedure for assessing compositionality of emergent
communication. In contrast to other evaluations, our procedure provides a
human-interpretable translation table of emerged words to natural concepts.
Moreover, our approach provides detailed insights into the reasons for sub-
optimal translation. We demonstrated it on two EC games with two different
communication types. Our evaluation revels even that quantized communication
performs better than Gumbel-softmax, yet none exhibits compositionality in a
level similar to natural language.

##  7 Limitations

Our analysis is limited to datasets where gold label phrases exist. The
evaluated dataset should be composable and the gold language should use finite
set of concepts. Preferably, these concepts can be classified into several
categories. We further assume an Orcal function that can divide the objects to
targets an distractors during training. Importantly, our approach does not
require labels during training.

## References

  * Andreas and Klein (2016) Jacob Andreas and Dan Klein. 2016.  Reasoning about pragmatics with neural listeners and speakers.  In _EMNLP_.
  * Brighton and Kirby (2006) Henry Brighton and Simon Kirby. 2006.  Understanding linguistic evolution by visualizing the emergence of topographic mappings.  _Artificial life_ , 12(2):229–242.
  * Carmeli et al. (2022) Boaz Carmeli, Ron Meir, and Yonatan Belinkov. 2022.  Emergent quantized communication.  _arXiv preprint arXiv:2211.02412_.
  * Chaabouni et al. (2020) Rahma Chaabouni, Eugene Kharitonov, Diane Bouchacourt, Emmanuel Dupoux, and Marco Baroni. 2020.  Compositionality and generalization in emergent languages.  In _ACL_ , pages 4427–4442.
  * Chaabouni et al. (2021) Rahma Chaabouni, Florian Strub, Florent Altché, Eugene Tarassov, Corentin Tallec, Elnaz Davoodi, Kory Wallace Mathewson, Olivier Tieleman, Angeliki Lazaridou, and Bilal Piot. 2021.  Emergent communication at scale.  In _ICLR_.
  * Havrylov and Titov (2017) Serhii Havrylov and Ivan Titov. 2017.  Emergence of language with multi-agent games: Learning to communicate with sequences of symbols.  _NeurIPS_ , 30.
  * Hopcroft and Karp (1973) John E Hopcroft and Richard M Karp. 1973.  An n^5/2 algorithm for maximum matchings in bipartite graphs.  _SIAM Journal on computing_ , 2(4):225–231.
  * Hupkes et al. (2020) Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. 2020.  Compositionality decomposed: How do neural networks generalise?  _Journal of Artificial Intelligence Research_ , 67:757–795.
  * Jang et al. (2017) Eric Jang, Shixiang Gu, and Ben Poole. 2017.  Categorical reparameterization with gumbel-softmax.  In _ICLR_.
  * Kharitonov et al. (2019) Eugene Kharitonov, Rahma Chaabouni, Diane Bouchacourt, and Marco Baroni. 2019.  EGG: a toolkit for research on emergence of lanGuage in games.  In _EMNLP-IJCNLP: System Demonstrations_ , pages 55–60.
  * Kuhn (1955) Harold W Kuhn. 1955.  The hungarian method for the assignment problem.  _Naval research logistics quarterly_ , 2(1-2):83–97.
  * Kuhnle and Copestake (2017) Alexander Kuhnle and Ann Copestake. 2017.  Shapeworld-a new test methodology for multimodal language understanding.  _arXiv preprint arXiv:1704.04517_.
  * Lazaridou et al. (2018) Angeliki Lazaridou, Karl Moritz Hermann, Karl Tuyls, and Stephen Clark. 2018.  Emergence of linguistic communication from referential games with symbolic and pixel input.  In _ICLR_.
  * Lazaridou et al. (2017) Angeliki Lazaridou, Alexander Peysakhovich, and Marco Baroni. 2017.  Multi-agent cooperation and the emergence of (natural) language.  In _ICLR_.
  * Levenshtein et al. (1966) Vladimir I Levenshtein et al. 1966.  Binary codes capable of correcting deletions, insertions, and reversals.  In _Soviet physics doklady_ , volume 10, pages 707–710. Soviet Union.
  * Li and Bowling (2019) Fushan Li and Michael Bowling. 2019.  Ease-of-teaching and language structure from emergent communication.  _NeurIPS_ , 32.
  * Mu and Goodman (2021) Jesse Mu and Noah Goodman. 2021.  Emergent communication of generalizations.  _Advances in Neural Information Processing Systems_ , 34:17994–18007.
  * Slonim (2002) Noam Slonim. 2002.  _The information bottleneck: Theory and applications_.  Ph.D. thesis, Hebrew University of Jerusalem Jerusalem, Israel.
  * Tucker et al. (2022) Mycal Tucker, Roger P Levy, Julie Shah, and Noga Zaslavsky. 2022.  Generalization and translatability in emergent communication via informational constraints.  In _NeurIPS 2022 Workshop on Information-Theoretic Principles in Cognitive Systems_.
  * Vani et al. (2021) Ankit Vani, Max Schwarzer, Yuchen Lu, Eeshan Dhekane, and Aaron Courville. 2021.  Iterated learning for emergent systematicity in VQA.  In _ICLR_.
  * Vinh et al. (2009) Nguyen Xuan Vinh, Julien Epps, and James Bailey. 2009.  Information theoretic measures for clusterings comparison: is a correction for chance necessary?  In _Proceedings of the 26th annual international conference on machine learning_ , pages 1073–1080.
  * Yao et al. (2022) Shunyu Yao, Mo Yu, Yang Zhang, Karthik R Narasimhan, Joshua B. Tenenbaum, and Chuang Gan. 2022.  Linking emergent and natural languages via corpus transfer.  In _ICLR_.
  * Zaslavsky et al. (2021) Noga Zaslavsky, Jennifer Hu, and Roger P. Levy. 2021.  A Rate–Distortion view of human pragmatic reasoning?  In _Proceedings of the Society for Computation in Linguistics_ , pages 347–348.

Appendices

##  Appendix A Details on Evaluation Measures

We provide here information on how to calculate the topographic similarity
(TopSim) Brighton and Kirby (2006); Lazaridou et al. (2018); Yao et al. (2022)
and adjusted mutual information (AMI) measures Vinh et al. (2009); Mu and
Goodman (2021), in the context of EC. Refer to the original papers for full
details.

#### Topographic Similarity.

The topographic similarity measures how messages align with the object
representations. Concretely, let
$\text{cos}_{ij}=\text{cos}({\bm{x}}_{i},{\bm{x}}_{j})={\bm{x}}_{i}\cdot{\bm{x}}_{j}/(||{\bm{x}}_{i}||_{2}||{\bm{x}}_{j}||_{2})$
be the cosine similarity of object representations ${\bm{x}}_{i}$ and
${\bm{x}}_{j}$, and $\text{edit}_{ij}=\text{edit}(m_{i},m_{j})$ be the
Levenshtein distance Levenshtein et al. (1966) between messages $m_{i}$ and
$m_{j}$. Let $\text{ncos}=-\\{\cos_{ij}\\}_{ij}$ be the list of negative
cosine similarities, $\text{edit}=\\{\text{edit}_{ij}\\}_{ij}$ the list of
Levenshtein distances, and $R(\cdot)$ the ranking function. Then the
topographic similarity is the Spearman rank correlation of the two matrices:

$\mathrm{Topsim}=\rho(R(\text{edit}),R(\text{ncos}))$ (2)

where $\rho$ is the standard Pearson correlation.

Topographic similarity is a global metric that does not require a reference
language and can be easily applied to every EC setup. However, despite its
popularity, recent studies found that topographic similarity does not
correlate well with success in the task being played (Chaabouni et al., 2021;
Yao et al., 2022). More important, it does not provide a mapping between EC
atoms and NL concepts, and thus cannot directly assess compositionality.

#### Adjusted Mutual Information.

Given a test set $D$, let ${\mathbb{M}}$ denote the set of messages generated
by the sender and ${\mathbb{L}}$ denote the set of NL phrases (e.g., Red
Triangle, Blue Square) exist as labels in the data. The adjusted mutual
information (AMI) Vinh et al. (2009) measures the mutual information between
messages and labels, adjusted for chance:

$\text{AMI}(M,L)=\frac{I(M,L)-\mathbb{E}(I(M,L)}{\max(H(M),H(L))-\mathbb{E}(I(M,L))}$
(3)

where $I(M,L)$ is the mutual information between $M$ and $L$, $H(\cdot)$ is
the entropy, and $\mathbb{E}(I(M,L))$ is computed with respect to a
hypergeometric model of randomness.

Batch |  | Num | Num | Cell | Sender | Sender | Receiver | Receiver
---|---|---|---|---|---|---|---|---
Size | lr | Targets | Distr | Type | Hidden | Embed | Hidden | Embed
10 | 0.0005 | 8/20 | 8/20 | LSTM | 60 | 60 | 40 | 40
Table 2: Hyper-parameters for the agents in the Shape game. Exp |  | Comm | Label | word | Msg | Best |  |  | Best
---|---|---|---|---|---|---|---|---|---
Num | Game | Type | Len | Len | Len | Epoch | ACC | AMI | Match
1 | Shape | gs | 1 | 8 | 4 | 97 | 0.829 | 0.404 | 0.405
2 | Shape | gs | 1 | 64 | 4 | 96 | 0.843 | 0.390 | 0.339
3 | Shape | gs | 4 | 8 | 1 | 8 | 0.742 | 0.490 | 0.152
4 | Shape | gs | 4 | 64 | 1 | 10 | 0.748 | 0.413 | 0.130
5 | Shape | qt | 1 | 3 | 4 | 86 | 0.878 | 0.540 | 1.401
6 | Shape | qt | 1 | 64 | 4 | 85 | 0.991 | 0.000 | 0.001
7 | Shape | qt | 4 | 3 | 1 | 9 | 0.768 | 0.474 | 0.152
8 | Shape | qt | 4 | 64 | 1 | 12 | 0.897 | 0.021 | 0.009
9 | Thing | gs | 1 | 8 | 4 | 83 | 0.793 | 0.102 | 0.091
10 | Thing | gs | 1 | 64 | 4 | 94 | 0.798 | 0.074 | 0.151
11 | Thing | gs | 4 | 8 | 1 | 97 | 0.655 | 0.016 | 0.052
12 | Thing | gs | 4 | 64 | 1 | 99 | 0.626 | 0.014 | 0.058
13 | Thing | qt | 1 | 3 | 4 | 96 | 0.838 | 0.267 | 0.119
14 | Thing | qt | 1 | 64 | 4 | 100 | 0.973 | 0.000 | 0.014
15 | Thing | qt | 4 | 3 | 1 | 26 | 0.622 | 0.020 | 0.057
16 | Thing | qt | 4 | 64 | 1 | 96 | 0.844 | 0.000 | 0.013
Table 3: Configurations for more Shape and Thing game experiments. In these configuration we intentionally define sub-optimal communication parameters in order to demonstrate the usefulness of the evaluation metrics. Experiment results are provided in Table 4 Exp | Unq | Unq | Unq | Ung | Totl | Good | Amb | Phrs | Totl | Unm | Par |  |
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Num | Msgs | Wrds | Prs | Cons | Edgs | Edgs | Edgs | Edgs | Cons | Cons | Scor | Prc | Rcl
1 | 258 | 7 | 17 | 17 | 4k | 1621 | 2379 | 0 | 1k | 444 | 0 | 0.137 | 0.546
2 | 442 | 55 | 17 | 17 | 4k | 1356 | 1724 | 920 | 1k | 0 | 0.23 | 0.144 | 0.577
3 | 8 | 8 | 34 | 17 | 4k | 610 | 390 | 0 | 4k | 1457 | 0 | 0.61 | 0.152
4 | 44 | 44 | 34 | 17 | 4k | 520 | 326 | 154 | 4k | 0 | 0.04 | 0.52 | 0.13
5 | 238 | 8 | 17 | 17 | 4k | 1605 | 2395 | 0 | 1k | 385 | 0 | 0.144 | 0.577
6 | 1000 | 3899 | 17 | 17 | 4k | 46 | 0 | 3954 | 1k | 0 | 0.99 | 0.011 | 0.044
7 | 7 | 7 | 34 | 17 | 4k | 607 | 393 | 0 | 4k | 1727 | 0 | 0.607 | 0.152
8 | 974 | 974 | 34 | 17 | 4k | 38 | 0 | 962 | 4k | 0 | 0.24 | 0.038 | 0.009
9 | 543 | 7 | 50 | 50 | 4k | 366 | 3634 | 0 | 1k | 807 | 0 | 0.048 | 0.19
10 | 806 | 60 | 50 | 50 | 4k | 601 | 3369 | 30 | 1k | 0 | 0.01 | 0.1 | 0.399
11 | 8 | 8 | 901 | 50 | 4k | 210 | 790 | 0 | 4k | 3332 | 0 | 0.21 | 0.052
12 | 21 | 21 | 901 | 50 | 4k | 233 | 767 | 0 | 4k | 2267 | 0 | 0.233 | 0.058
13 | 412 | 8 | 50 | 50 | 4k | 478 | 3522 | 0 | 1k | 795 | 0 | 0.046 | 0.184
14 | 1000 | 3991 | 50 | 50 | 4k | 57 | 0 | 3943 | 1k | 0 | 0.99 | 0.013 | 0.052
15 | 11 | 6 | 901 | 50 | 4k | 229 | 771 | 0 | 4k | 3483 | 0 | 0.229 | 0.057
16 | 1000 | 1000 | 901 | 50 | 4k | 50 | 0 | 950 | 4k | 0 | 0.24 | 0.05 | 0.013
Table 4: Results for more Shape and Thing game configurations described in
Table 3. In these experiments we intentionally define sub-optimal
communication parameters in order to demonstrate the usefulness of the
evaluation metrics.

##  Appendix B Datasets

We use two datasets in our experiments. Both will be made publicly available.

#### Shape.

A visual reasoning dataset Kuhnle and Copestake (2017) of objects over a black
background. Our version of the dataset contains four attributes: the shape
attribute has five shapes, the color attribute has six colors. To these we
added horizontal and vertical position attributes each with three values.
Overall, the Shape dataset contains 17 concepts, and a maximal labeling rule
of 4 FVPs which sum to 270 unique 4-concept labels. The dataset contains many
images that obey the same label. See Figure 3 for an example.

#### Thing.

A synthetic dataset of 100,000 objects which we design for controlled
experiments. Each object in the dataset has five attributes, each with 10
possible values. Overall, the Thing datasets contains 50 concepts and a
maximal labeling rule of 5 FVPs. We experiments with label lengths varied from
$1$, describing a single concept, to $5$, which completely describes an object
in the dataset.

Figure 3: The Shape dataset, presenting one turn. Top $8$ images are Yellow
targets. Bottom $8$ images are distractors.

##  Appendix C Implementation Details

We run all experiments over a modified version of the Egg framework Kharitonov
et al. (2019).444Our modification will be released as open-source upon de-
anonymization. In our version the communication modules used by the sender and
the receiver are totally separated from their perceptual modules, which we
term ‘agents’. The Quantized (QT) and Gumbel-Softmax (GS) protocols are
implemented at the communication layer. For GS we use an implementation
provided by the Egg framework, where we do not allow temperature to be
learned, and set the straight-through estimator to False. For QT we followed
parameter recommendations from Carmeli et al. (2022) and use a binary
quantization in all experiments. Both GS and QT uses a recurrent neural
network (RNN) for generating multiple words in a message. See Table 2 for RNN
details.

The agents for the Thing game use fully connected feed-forward networks with
input dimension of $d=270$. Objects are encoded by concatenating five one-hot
vectors, one per attribute. There are 50 unique values and 4 communication
words (SOS, EOS, PAD, UNK), thus the total object representation length is
$d=270$ The agents of the Shape game are implemented with a convolutional
neural network similar to Mu and Goodman (2021). Network hyper-parameters are
provided in Table 2. In the experiments, we report results when varying the
communication elements (word length and message length). Experiments in Table
1 are done with 20 targets and 20 distractors, while experiments reported in
Tables 3 and 4 are done with 8 targets and 8 distractors. Our main interest in
this work is to evaluate the emerged communication and not to achieve the best
possible performance, thus we did not conduct a thorough hyper-parameter
search for the agents themselves.

We run all experiments on a single A100 GPU with 40 GB of RAM. Model size is
less than 10M. We usually trained the model for 200 epochs which took about 10
hours to complete. Our code will be made publicly available upon de-
anonymization.

##  Appendix D Evaluating Sub-optimal Configurations

Here we provide results from experiments with several sub-optimal
configurations and demonstrate how CBM identifies these deficiencies. We
report configuration parameters for each experiment together with accuracy,
AMI, and CBM Score in Table 3. We report all CBM metrics for these experiments
in Table 4. Information from the two tables is aligned by the experiment
number (first column).

Sub-optimal communication may stem from a channel that is either too wide or
too narrow. Narrow channels are restricted by a small number of words and
short messages. Wide channels allow long words and/or long messages. Past
studies Slonim (2002); Tucker et al. (2022) suggest that creating an
information bottleneck by narrowing the channel encourages generalization. As
seen, CBM scores for most reported sub-optimal configurations are low. Results
from experiments 1, 2, and 5 are the only ones for which the CBM score is
higher than $0.2$. Experiment 6 (Shape) achieves almost perfect accuracy
(0.991) due to its wide channel. However, the paraphrase score for this
experiment is $0.989$ showing that the sender uses many different words to
refer to the same concept. This phenomenon can also be seen by the large
number of unique words ($3899$) generated for just $17$ unique concepts. A
similar phenomenon is observed for the Thing game (experiment 14).

Experiment 11 (Thing) uses a narrow channel. The vocabulary contains only 8
words and the channel allows one-word-long messages. This configuration
resulted in $3332$ concepts that do not match any word. Interestingly, the
number of unmatched concepts remains high even when extending the word length
to $64$, in experiment 12. We attribute this sub-optimal phenomenon to GS
communication deficiencies. The number of unique words generated by the sender
in this experiment is only $21$ out of the possible 64 words allowed by the
configuration. For the Shape game, on the other hand, the same wide-channel
configuration resulted in $44$ unique words generated by the sender for the 17
concepts available in this game and all concepts have matched words.

Figure 4: Assessing CBM sensitivity to the size of the evaluation set. We show
results for two randomly selected experiments. As seen, the CBM score
stabilizes when assessing datasets comprising more than $500$ samples.

#### Precision and recall.

After finding the best match, precision and recall between words and concepts
can be computed. We define message precision (Prc) and recall (Rcl) to be the
number of matched edges in a message, divided by the number of words or
concepts, respectively. Precision and recall add insights in situation where
the number of words in messages differs significantly from the number of
concepts used for labeling the data. Experiment 5 (Shape) shows the highest
recall, gained partially due to the long message length (four words) allowed
by the channel, compared to the label length (one concept) dictated by the
data. In contrast, experiment 3 (Shape) shows the highest precision. Indeed,
this configuration restricts message the length to one word while the data
dictates four-concept long phrases.

##  Appendix E CBM Sensitivity to Dataset Size

We evaluated CBM scores on increased data sizes. Figure 4 shows results for
two randomly selected experiments. The solid lines indicate the CBM score,
computed when accumulating data samples in 100 quintets. The dashed lines
indicate CBM score calculated independently for 18 successive data segments of
$100$ samples each. As seen, scores stabilize for evaluation sets of size
larger than $500$ samples. Interestingly, the $100$-sample scores (dashed)
lines are higher than the accumulated scores (solid lines). This is in line
with our insight that low evaluation sizes result in higher match scores.
Standard deviation for the $18$ accumulated measures is $0.009$ and $0.016$,
for the two experiments, respectively. Standard deviation for the $18$
segmented measures is $0.044$ and $0.040$, for the two experiments,
respectively.


# On Intersecting Polygons

Kada K Williams

(March 6, 2023)

###### Abstract

Consider two regions in the plane, bounded by an $n$-gon and an $m$-gon,
respectively. At most how many connected components can there be in their
intersection? This question was asked by Croft. We answer this asymptotically,
proving the bounds

$\left\lfloor\frac{m}{2}\right\rfloor\cdot\left\lfloor\frac{n}{2}\right\rfloor\leq
f(n,m)\leq\left\lfloor\frac{m}{2}\right\rfloor\cdot\frac{n}{2}+\frac{m}{2}$

where $f(n,m)$ denotes the maximal number of components and $m\leq n$.
Furthermore, we give an exact answer to the related question of finding the
maximal number of components if the $m$-gon is required to be convex:
$\left\lfloor\frac{m+n-2}{2}\right\rfloor$ if $n\geq m+2$ and $n-2$ otherwise.

##  1 Introduction

Croft [1] asked the following question.

######  Question 1.

What is the maximal number of connected components in the intersection of the
polygonal regions determined by an $n$-gon and an $m$-gon?

Figure 1: intersecting polygons

As usual, a polygon is a piecewise linear simple closed curve in the plane.
Since all polygons admit a triangulation, the $n$-gonal region can be
partitioned into $n-2$ triangles, the $m$-gonal region into $m-2$. Now the
intersection of convex regions is convex, every triangle is convex, and every
convex region is either path-connected or empty. It follows that the answer is
at most $(m-2)(n-2)$, hence finite. Furthermore, supposing that the $m$-gon is
convex, there are at most $n-2$ components.

######  Question 2.

What is the maximal number of connected components in the intersection of a
region bounded by an $n$-gon and a convex $m$-gon?

In Figure 3, the yellow regions are in different connected components if the
polygons are viewed as open, whereas if the polygons are closed, there is only
one connected component. Yet as we will see, the maximal number of connected
components in Questions 1 and 2 does not depend on whether the polygonal
regions are open or closed. Essentially, we will deform the polygons slightly
if these open overlaps have a boundary point in common. We say that an overlap
is a connected component in the intersection of an open $n$-gon and an open
$m$-gon.

We claim that every overlap is a polygon, and that the boundary of an overlap
consists of segments contained by the perimeter of the $n$-gon or the $m$-gon.
To this end, let us first consider the convex polygons formed by intersecting
$n-2$ triangles with $m-2$ triangles in their respective triangulations. The
overlaps arise when we glue these polygons along the inner diagonals, and so
are polygons as well. Their boundary segments are contained not by inner
diagonals, but by sides of the $n$-gon or $m$-gon.

Figure 2: overlaps

When intersecting a closed $n$-gon and a closed $m$-gon, it is possible that
the boundaries of two overlaps meet, or that a one-dimensional connected
component occurs from a vertex or side of one polygon tangent to the side of
another. Observe that this is only possible if three side lines of the $n$-gon
and $m$-gon pass through a point. We resolve this as follows.

Figure 3: deformation, before and after

Given a side, let us translate its line by a perpendicular vector such that we
increase the width of any component it contains, we do not let the line move
across the finitely many points where two side lines meet, and the vector has
smaller length than the positive width overlaps. Iterating this, the number of
times three side lines concur can be decreased to zero, while the number of
components does not decrease. Therefore, in our investigations, we may assume
that no three side lines pass through a point, and that the polygons are open.

Let $f(n,m)$ denote the maximal number of overlaps (equivalently, of connected
components) between an $n$-gonal and an $m$-gonal region. Our main result is
the following.

######  Theorem 3.

$\left\lfloor\frac{m}{2}\right\rfloor\cdot\left\lfloor\frac{n}{2}\right\rfloor\leq
f(n,m)\leq\left\lfloor\frac{m}{2}\right\rfloor\cdot\frac{n}{2}+\frac{m}{2}$

Furthermore, we give an exact answer to the convex version of the question.

######  Theorem 4.

Let us intersect an $n$-gonal region with a convex $m$-gonal region. The
maximal number of overlaps is $\left\lfloor\frac{m+n-2}{2}\right\rfloor$ if
$n\geq m+2$ and $n-2$ otherwise.

###### Proof of Theorem 3, lower bound.

Intersecting $\left\lfloor\frac{m}{2}\right\rfloor$ ’teeth’ with
$\left\lfloor\frac{n}{2}\right\rfloor$ ’teeth’ as in Figure 4 yields
$\left\lfloor\frac{m}{2}\right\rfloor\cdot\left\lfloor\frac{n}{2}\right\rfloor$
overlaps. Clearly, the direction of the end segments is such that they meet.
Possibly with an additional side in the case when $m$ is odd or when $n$ is
odd, this creates an $n$-gon and an $m$-gon. ∎

Figure 4: double dentures

Proving the upper bound in Theorem 3 involves the following lemma. We shall
use standard notation – see e.g. [2].

######  Lemma 5.

If an overlap does not contain a vertex of the $m$-gon or $n$-gon, then it has
an even number of sides.

##  2 Three special cases

Figure 5: $f(5,3)=3$

In the case $m=3$ and $n=5$, by triangulating the pentagon, it is clear that
at most $3$ overlaps emerge. Moreover, as many as $3$ overlaps can be
attained.

In the case $m=4$ and $n=4$, the number of overlaps is $\leq 2\cdot 2=4$,
because each quadrilateral is made up of two triangles. This many overlaps can
be attained, see Figure 6.

Figure 6: $f(4,4)=4$

In the case $m=5$ and $n=5$, by tweaking the construction for $n=3$, we can
achieve $5$ overlaps. On the other hand, our proof that no more than $5$ can
be had is more subtle. First, we note that a triangle can only form $3$
overlaps with a pentagon if the pentagon can be partitioned into no less than
$3$ convex regions. This is only possible if the pentagon has three sides
proceeding along a concave arc, met by the triangle according to Figure 5.

If neither pentagon has this shape, then at most $2\cdot 2=4$ overlaps are
possible. If one pentagon has this shape, then of its three triangle parts,
the outer two are intersected at most twice, or else the other pentagon is
determined. In particular, if an outer triangle meets the other pentagon in
three regions, then two of these regions border an inner diagonal, thus
forming no more than $\frac{1}{2}$ of an overlap (except for an option where
these three are all the overlaps). As for the central triangle, it contains at
most $1+\frac{1}{2}+\frac{1}{3}$ overlaps (except for an option where the
other pentagon meets no inner diagonal, with two overlaps from the central
triangle and at most one from each outer one). In total, there are certainly
fewer than $6$ overlaps, whichever case it is. Therefore, $f(5,5)=5$.

Figure 7: construction for $f(5,5)=5$

##  3 The proofs

Let us show that if an overlap does not contain a vertex of the $m$-gon or
$n$-gon, then it has an even number of sides.

###### Proof of Lemma 5.

The key is to inspect two consecutive sides of an overlap. Recall that any
side of an overlap is contained by the boundary of the $m$-gon or $n$-gon. If
two consecutive sides belong to the $m$-gon, then the vertex where they meet
must be a vertex of the $m$-gon, and similarly for the $n$-gon. Therefore,
provided that an overlap does not contain such a vertex, its consecutive sides
belong only to the $m$-gon or only to the $n$-gon, alternating between the
two. Hence, this overlap has an even number of sides along its boundary. ∎

###### Proof of Theorem 3, upper bound.

Let there be given an $m$-gon and an $n$-gon with $F$ overlaps. Of these, let
there be $F_{k}$ many with exactly $k$ sides belonging only to the $n$-gon. If
an overlap has two consecutive sides on the $m$-gon, then they meet at a
vertex of the $m$-gon. We may assume overlaps are disjoint, so each vertex of
the $m$-gon occurs at most once this way. We deduce that $3F_{0}+F_{1}\leq m$,
as surely all vertices are such if all sides belong to the $m$-gon, and surely
at least one vertex is such if there is just one exception.

The essential idea is to double-count the overlap side segments on the
$n$-gon. Looking at one single side of the $n$-gon, it contains at most $m$
points of intersection with the $m$-gon, and so contains at most
$\left\lfloor\frac{m}{2}\right\rfloor$ segments bounding some overlap. This
amounts to $n\cdot\left\lfloor\frac{m}{2}\right\rfloor$ segments in total. On
the other hand, there are $k$ segments on $F_{k}$ many overlaps. Therefore,

$\sum_{k}kF_{k}\leq n\cdot\left\lfloor\frac{m}{2}\right\rfloor.$

Adding to this the inequality $3F_{0}+F_{1}\leq m$, the coefficient of each
$F_{k}$ on the left-hand side is at least $2$. Thus,

$2F\leq n\cdot\left\lfloor\frac{m}{2}\right\rfloor+m.$

Dividing by $2$ implies the upper bound
$f(n,m)\leq\left\lfloor\frac{m}{2}\right\rfloor\cdot\frac{n}{2}+\frac{m}{2}$.
∎

Figure 8: appending a tooth

Next, let us see how to maximise the number of overlaps with a convex $m$-gon.

###### Proof of Theorem 4.

With regard to Figure 5, if a concave arc of $m$ sides is formed over a $V$
shape, the resulting $(m+2)$-gon is intersected in $m$ overlaps by a convex
$m$-gon with vertices near the midpoints of these sides. Thus, if $n=m+2$,
there can be $n-2=m$ overlaps. If $m$ is increased, there still can be $n-2$
overlaps. If $n$ is increased, then at the cost of two sides, a ’tooth’ can be
appended as in Figure 8, causing $\left\lfloor\frac{n-(m+2)}{2}\right\rfloor$
more overlaps.

As the $n$-gon can be partitioned into $n-2$ triangles, each of which overlap
the convex $m$-gon at most once, there can be no more than $n-2$ overlaps in
the case $n<m+2$. Let us further prove that there can be no more than
$m+\left\lfloor\frac{n-(m+2)}{2}\right\rfloor=\left\lfloor\frac{m+n-2}{2}\right\rfloor$
overlaps in the case $n\geq m+2$.

Following the same notation as in the previous proof, the number of overlap
side segments on the $n$-gon is $\sum kF_{k}$, where $3F_{0}+F_{1}\leq m$.
However, in this problem, each side of the $n$-gon creates at most one segment
bounding some overlap, and so $\sum kF_{k}\leq n$. Adding these yields

$2F\leq m+n.$

Our strategy is to improve this bound by $2$. Let us regard the sides of the
$n$-gon which belong to its convex hull, of which there are at least $2$.
Should these fail to meet the $m$-gon, clearly $\sum kF_{k}\leq n-2$. If the
$m$-gon has two vertices outside the $n$-gon, $3F_{0}+F_{1}\leq m-2$. Finally,
if the $m$-gon has but one vertex outside the $n$-gon, then the convex hull of
the $n$-gon is only met by two consecutive sides of the $m$-gon, so only one
overlap is bounded with the convex hull. In this case, $3F_{0}+F_{1}\leq m-1$,
but also $\sum kF_{k}\leq n-1$. Therefore,

$2F\leq m+n-2.$

It follows that no more than $\left\lfloor\frac{m+n-2}{2}\right\rfloor$
overlaps can be attained. ∎

##  4 Concluding remarks

Despite our efforts to approximate $f(n,m)$, Problem 1 remains open. As we saw
in our proof that $f(5,5)=5$, if an overlap does necessarily involve a vertex
of the $m$-gon, then it takes up considerable space. Our upper bound appears
to be wasteful in general. Therefore, we may conjecture the following.

######  Conjecture 6.

The answer to Problem 1 is
$f(n,m)=\left\lfloor\frac{n}{2}\right\rfloor\cdot\left\lfloor\frac{m}{2}\right\rfloor+\epsilon$,
where $\epsilon=1$ for odd values of $n$ and $m$, and $\epsilon=0$ otherwise.

The extra term $\epsilon$ is needed because in Figure 4, a new overlap is made
when swapping the lowest edge for a triangle reaching a new edge, as in Figure
5.

Acknowledgement. The author would like to thank Imre Leader for helpful
discussions and guidance in writing this paper.

## References

  * [1] H T Croft. Personal communication, 2021.
  * [2] V Boltyanski, H Martini, P S Soltan. Excursions into Combinatorial Geometry. Springer-Verlag Berlin Heidelberg, 1997.

Department of Pure Mathematics and Mathematical Statistics, University of
Cambridge, Wilberforce Road, Cambridge CB3 0WB.

E-mail address<EMAIL_ADDRESS>