#  Neuro-Symbolic Causal Reasoning Meets Signaling Game for Emergent Semantic
Communications

Christo Kurisummoottil Thomas, and Walid Saad,
Christo Kurisummoottil Thomas and Walid Saad are with the Wireless@VT, Bradley
Department of Electrical and Computer Engineering, Virginia Tech, Arlington,
VA, USA,(emails:{christokt,walids}@vt.edu).
A preliminary version of this work will appear in IEEE GLOBECOM 2022 [1].

###### Abstract

Semantic communication (SC) has emerged as an effective approach to
communicate reliably with minimal data transfer while simultaneously providing
seamless connectivity to heterogeneous services and users. In this paper, a
novel emergent SC (ESC) system framework is proposed. This ESC is composed of
two key components: a signaling game for emergent language design and a neuro-
symbolic (NeSy) artificial intelligence (AI) approach for causal reasoning. In
order to design the language, the signaling game is solved using an
alternating maximization between the transmit and receive nodes utilities. The
generalized Nash equilibrium is characterized, and it is shown that the
resulting transmit and receive signaling strategies lead to a local
equilibrium solution. The emergent language not only creates an efficient (in
physical bits transmitted) transmit vocabulary dependent on communication
contexts but it also aids the reasoning process (and enables generalization to
unseen scenarios) by splitting complex received messages into simpler
reasoning tasks for the receiver. The causal description at the transmitter is
then modeled (using a neural component) as a posterior distribution of the
relevant attributes present in the data. Using the reconstructed causal state,
the receiver evaluates a set of logical formulas (symbolic part) to execute
its task. The nodes’ NeSy reasoning components are implemented by the recently
proposed AI tool called Generative Flow Networks (GFlowNet), and they are
optimized for higher semantic reliability. The ESC system is designed to
enhance the novel metrics of semantic information, semantic reliability,
distortion and similarity that are designed using rigorous algebraic
properties from category theory thereby generalizing the metrics beyond
Shannon’s notion of uncertainty. Simulation results validate the ability of
ESC to communicate efficiently (with reduced bits) and achieve significantly
better semantic reliability than conventional wireless and state-of-the-art SC
systems that do not exploit causal reasoning capabilities. The results also
show that the overhead used to create the language will become negligible over
time, justifying its generalization capability to multiple tasks and contexts.

##  I Introduction

Future wireless systems (e.g., 6G) must be more judicious in what they
transmit to integrate high-rate, high-reliability, and time-critical wireless
applications. Conventional wireless systems focus on reliably sending physical
bits without emphasis on the _semantic and effectiveness_ layer, as pointed
out by Shannon [2]. In reality, instead of transmitting the entire data, it is
more efficient in terms of delay, bandwidth utilization, and energy (without
compromising the reliability), to only send information that is useful for the
receiver [3]. This is central premise of the idea of _semantic communication
(SC) systems_ [4].

Integrating the semantic and effectiveness aspects to create artificial
intelligence (AI)-native wireless networks requires a major paradigm shift [5,
3, 4, 6]. Future wireless devices must support novel applications such as
smart cities, industrial robotics, and the metaverse that are expected to
generate a staggering amount of data in the order of zetta-bytes. Moreover,
these applications require massive connectivity over limited bandwidth as well
as lower latency and higher reliability. However, under these stringent
requirements, traditional communication systems require enormous computing and
communication resources to enhance system scalability. A promising solution
here is SC systems that help achieve better reliability at the end user with
minimal transmission, thus improving communication efficiency. Transmission
efficiency can be achieved by transitioning the transmit and receive nodes
from being just blind devices (that transfer data back and forth) toward
brain-like devices capable of understanding and reasoning over the data and
how it gets generated (called _causal reasoning_). However, classical AI
systems that rely purely on data statistics are not apropos for causal
reasoning. Moreover, classical models might not be able to generalize to new
data, and therefore, they cannot achieve the required reliability in real-
world wireless scenarios. One promising approach to circumvent these issues is
augmenting the ability to learn from experience (neural component) with the
ability to reason from what has been learned (symbolic-AI component). In this
context, we address the above challenges by inducing reasoning through neuro-
symbolic (NeSy) AI approaches, thereby providing intelligence to the
transmitter and receiver. Consequently, NeSy enables the SC system to learn
the transmit and receive signaling strategies with dramatically less data for
many complex tasks rather than one narrow task while communicating efficiently
with fewer bits than classical information-theoretic schemes.

###  I-A Related Works

Despite the recent surge in works on SC [6, 7, 8, 9, 10, 11], most of them
fail to address a few critical aspects. First, they mostly ignore the causal
reasoning behind the data generation. Instead, they limit the discussion to
the computation of meaningful attributes describing the observed data.
However, this does not help achieve the benefits behind SC since the
aforementioned methods are not built based on _semantic awareness_ about how
the receiver uses the information. Second, the solutions of [6, 7, 9, 8, 10]
are not generalizable enough to situations not encountered during training and
may require significant retraining efforts resulting in larger communication
overheads. Even though the authors in [6] briefly mention the benefits of
language models in natural language processing (NLP) with respect to reasoning
and task generalization, their proposed methodology starts with the assumption
that the semantics are already known. Their main focus is on the semantic
encoder, which is essentially a source compression module, and the channel
encoder to combat the physical channel. The authors in [6] optimize the
conventional information theoretic (rate distortion) metrics that need not
result in minimal data transfer. Instead, a concrete methodology to enable the
reasoning at the nodes and a rigorous formulation of the semantic language is
critical to achieving the goals of an SC systems. Along this direction, for an
SC system, the authors in [7] outline a semantic protocol model for a two-user
MAC, using probabilistic logic programming (PbLog) in AI. They consider
language as a set of probabilistic clauses representing a cause and effect
model. However, their PbLog-based SC protocol is specifically tailored to
optimize the uplink and downlink control messages in a two-user scenario, and
thus, it does not scale to multiple learning and reasoning tasks. Moreover,
the language clauses in [7] are derived from a conventional deep Q-learning
neural network (NN) output that requires a massive amount of data to be
generalizable, and it suffers from overparameterization. Hence, to surpass the
performance limits set by classical information theory, it is imperative to
look beyond PbLog-based methods [7]. Given the computing and memory
constraints at the communicating nodes, it is desirable to have a language
model between network nodes that evolves via an understanding of the node’s
mutual intentions and learns the semantics in a _compositional_ manner, i.e.,
combining knowledge of simpler concepts to describe richer concepts. Such a
model, called _emergent language_ , guided by causal reasoning helps
generalize to unseen tasks without significant retraining effort and with
possibly less training data. One key difference between learning and causal
reasoning is that the former works primarily on uncertainty/statistics, i.e.,
learning a particular concept based on its statistical properties. However,
raw data is not only governed by statistical information and randomness; most
of the information (semantic substance and not uncertainty as per Shannon) we
see has particular causes. Causal reasoning can be effected by investigating
how and why specific information is embedded in a message. However, none of
the existing SC frameworks [6, 7, 8, 9, 10] is guided by the principles of
causal reasoning and a compositional emergent language that could help reduce
the AI training overheads and yet produce the SC system goals. We try to
bridge this gap in the literature here.

###  I-B Contributions

In contrast to the prior art, the main contribution of this paper is to design
the principles of _emergent SC (ESC)_ systems that include: (a) creating an
_emergent language_ that learns the transmit and receive signaling strategies
in a _compositional_ manner, and (b) instilling concrete reasoning
capabilities (using novel AI methods) into the nodes enabling them to identify
causal structure behind the data generation. In summary, our key contributions
are the following:

  * •

To create an emergent language that is _compositional_ (helps generalization)
and _semantics aware_ (for minimal transmission), we propose a novel
formulation based on a two-player contextual signaling game (_emergent
language game_) for optimizing the speaker and listener signaling strategies.

  * •

To compute the game objective functions, we derive a novel semantic
information measure utilizing the concept of functors and enriched categories
in category theory. We derive the semantic information content conveyed by a
particular transmit message as the sum of the information across all the
possible worlds (of logical interpretations) it represents in the semantic
category and is a more general or rigorous characterization compared to [12].

  * •

We propose an alternating maximization (AM) based algorithm for computing the
encoder and decoder distribution that converges to a _local generalized Nash
equilibrium (NE)_. Moreover, we theoretically prove that the optimal transmit
strategy is partitioning the syntactic space into a _Voronoi tessellation_ and
letting the listener perform a Bayesian receive strategy to reconstruct the
state description. This means that we obtain a locally optimal solution for an
emergent language that allow the speaker to transmit as minimum as possible
and let the listener reconstruct more semantic information.

  * •

We exploit the potential of the recently proposed AI algorithm called
generative flow networks (GFlowNet) [13] for inducing causal reasoning at the
nodes. Specifically, GFlowNet helps the speaker to compute the state
description (causal reasoning about the data) which helps to have a smaller
cardinality representation space for the emergent language. At the listener,
reasoning via GFlowNet framework (a symbolic component at the listener) allows
it to deduce the relevant logical conclusions from the reconstructed data to
complete its task with the required semantic reliability. For any previously
unseen, more arduous task, a chain of thought type reasoning (inspired by
[14]) implemented by GFlowNet and facilitated by the language compositionality
allows the listener to generalize the capabilities without any retraining. The
resulting neurosymbolic (NeSy) AI approach ([15]) saves significant
computational efforts and communication overheads arising from retraining.

  * •

We show that ESC systems can encode data with minimal bits compared to a
classical system that does not exploit causal reasoning and where the speaker
is unaware of the semantic effectiveness at the listener. Furthermore, we
prove that ESC systems can achieve higher semantic reliability (with fewer
physical bits) by reasoning over the created language and exploiting the
contextual information than by treating the data at the bit level as in
Shannon’s information theory.

Simulation results show that the proposed game-based emergent language
converges much faster compared to state of the art algorithm [9] that relies
upon variational inference and whose objectives are not accurately
characterised towards maximizing SC goals as we outline here. Moreover,
overhead associated with the proposed emergent language training duration
exponentially decreases over time with task variations, signifying its task
agnostic nature. Our results also show that the expected semantic
representation length for an ESC system gets significantly reduced compared to
a classical system by considering contextual information and causal reasoning.
This justifies our ESC system principle of ”transmitting less and doing more
with the data.” We also show how the proposed ESC system (with trained
GFlowNet as a causal component) can achieve a significantly better semantic
reliability compared to the state-of-the-art, including classical AI-based
methods.

The rest of this paper is organized as follows. In Section II, we present the
proposed ESC system model. Section III describes the proposed two-player
contextual signaling game. Section IV introduces the reasoning network
formulation using GFlowNet. Section V provides simulation results. Finally,
conclusions are drawn in Section VI.

##  II Proposed ESC System Model

Figure 1: Overview of proposed ESC model. Our focus is on 1) Learning of the
state description, which is grounded on the real logic and formed based on the
semantic language rules. 2) Encoder/decoder functions that translate the
states to optimal physical messages with the objective of transmitting less
but with semantic reliability close to $1$. Objectives are achieved via the
tools of NeSy AI.

Consider a speaker who observes a sequence of events that capture the state of
the environment, and each event $e\in\mathcal{E}$. The speaker intends to send
a concise description of the event (in other words, a causal description which
represents the _semantics_ of information) to a listener who wishes to
complete a set of sequential tasks drawn from a probability distribution
$p(\tau)$. From the inferred semantics, the listener further executes an
action represented by the probability distribution $p({\bm{a}}\mid\bm{\Phi})$
and ${\bm{a}}\in\mathcal{A}$ ($\subset\mathcal{R}$, a real value). $\bm{\Phi}$
is the set of logical conclusions that the listener is interested in
evaluating. The effectiveness of the actions on the listener’s environment
represents the _semantic effectiveness_ aspect. We assume that the impact of
the listener’s action gets reflected in the subsequent events observed by the
speaker. This means that communication occurs in a setting in which the
listener’s environment overlaps partially with that of speaker’s. However,
herein, at the start of communication, the speaker is unaware of the
listener’s intentions and its logical interpretations of the received
semantics. Hence, apart from the causal reasoning components at the nodes, a
communicating language (denoted the emergent language) has to be constructed
if the SC system is to achieve the benefits outlined in Section I. The
resulting ESC system framework is shown in Fig. 1. Here, the speaker first
extract the different features from the event observed. The objects part of
the event and their properties are called _entities_. We represent the set of
$N$ entities as set of vectors ${\bm{s}}_{i}$, where each entry
${\bm{s}}_{i}\in\mathcal{R}^{M}$ (grounded to real logic). We limit the
discussions on _entities extraction (neural component)_ to this paragraph and
refer to the $\beta$-variational auto-encoder (VAE) [16] which is a promising
approach that can be used here to extract statistically independent entities
present in the data.

###  II-A Causal Reasoning Model

Next, our objective is to infer the hidden relations among the entities and
compute the causal sequence that best explains the event observed. This
component is called the _semantic state descriptor_ (a neural component) in
Fig. 1. The semantic state description is defined as the sequence of entities
and their relations,
$\small{\widetilde{\bm{z}}\\!=\\!\left({\bm{s}}_{0},{\bm{r}}_{1},\cdots,{\bm{r}}_{N},{\bm{s}}_{N-1}\right)}$,
of dimension $M(2N-1)\\!\times\\!1$. Here, the vector
${\bm{r}}_{i}\in\mathcal{R}^{M}$ denotes the relation between entities
${\bm{s}}_{i}$ and ${\bm{s}}_{i+1}$. One way to represent ${\bm{r}}_{i}$ is as
a linear relation,
${\bm{s}}_{i+1}\\!\approx\\!{\bm{r}}_{i}\\!+\\!{\bm{s}}_{i}$, where
${\bm{r}}_{i}=-\ln p({\bm{s}}_{i+1}\mid{\bm{s}}_{i})$. If ${\bm{s}}_{i}$ and
${\bm{s}}_{i+1}$ are not causally related
$p({\bm{s}}_{i+1}\mid{\bm{s}}_{i})=0$. Hence, when the entities are far apart
in the grounded domain $\mathcal{R}^{M}$, then ${\bm{r}}_{i}$ has entries
$\infty$. When the $p({\bm{s}}_{i+1}\mid{\bm{s}}_{i})\approx 1$, then the
entities are very close to each other in $\mathcal{R}^{M}$. A modular approach
here to compute _the cause and effect relations_ is to investigate the
posterior distribution of entities given the observed event, as follows:

$\vspace{-2mm}\begin{array}[]{l}\vspace{-1mm}p({\bm{s}}_{0},{\bm{s}}_{1},\cdots,{\bm{s}}_{N-1}\mid
e)=\prod\limits_{i}p({\bm{s}}_{i}\mid\textrm{pa}({\bm{s}}_{i})),\end{array}\vspace{-1mm}$
(1)

where $\textrm{pa}(s_{i})$ represents all the entities that cause
${\bm{s}}_{i}$ and are called the parent nodes if we consider the
probabilistic relations as a directed acyclic graph (DAG). In a DAG, there is
an edge from node ${\bm{s}}_{i}$ to ${\bm{s}}_{i+1}$ when they are causally
related per (1). The ${\bm{r}}_{i}$ learned when computing (1) does not need
to be transmitted, rather only a truncated version of $\widetilde{\bm{z}}$ (by
removing ${\bm{r}}_{i}$), that is
$\small{{\bm{z}}\\!=\\!\left({\bm{s}}_{0},{\bm{s}}_{1},\cdots,{\bm{s}}_{N-1}\right)}$,
which is from hereon called the _state description_. This assumes that, given
$\bm{z}$, the listener can learn ${\bm{r}}_{i}$ by computing the posterior (1)
at its end and hence reduce transmission. To compute (1), a simplistic method
is to assume that this probabilistic structure follows a particular
approximate distribution as in stochastic variational inference techniques
[17]. For example, the existing SC solution in [9] relies upon a variational
inference technique. However, such an algorithm need not be generalizable to
out-of-order distributions. Hence, we adopt the new AI-based reasoning
framework called GFlowNet [13]. GFlowNet is chosen here since it incorporates
causality and can also learn the exact (or close to optimal) posterior
distribution under different variations in the task distribution (in short, a
multi-modal distribution compared to variational techniques).

After receiving the state description, the listener intends to derive certain
logical conclusions (called _logical formulas_) from the event description to
execute a task or to perform other system purposes. The capability to make
logical conclusions from the received data is vital to enable human-like
reasoning (i.e., cognition/common sense) that can enable them for automated
decisions or efficient data recovery in future intelligent wireless systems.
This is the _listener semantic reasoning_ (symbolic) component in Fig. 1. The
state description and the logical formulas that are deduced by the listener
constitute the information _semantics_. This is because only the information
that has a meaning w.r.t the listener’s task is relevant for communication,
and transmitting the rest of the observed data can only cause communication
inefficiency. The listener has a set $\bm{\Phi}$ of $L$ logical formulas of
interest that are evaluated using the reconstructed $\widehat{\bm{z}}_{t}$ as

$\vspace{-3mm}p(\bm{\phi}_{i}\mid\widehat{\bm{z}}),\,\,\forall\bm{\phi}_{i}\in\bm{\Phi}\subset\mathcal{R}^{D}.\,\,\,\vspace{-1mm}$
(2)

The logical formulas in (2) can be efficiently computed using GFlowNet itself
[18]111The proposed NeSy AI method implemented by GFlowNet can better
represent the causal aspects compared to existing NeSy algorithms, such as
logical NN (LNN) [19]. This is because it utilizes the concept of transformers
which allows parallel processing of the entities fed to it compared to
sequential processing in LNN that uses recurrent NNs (RNN)..

###  II-B Emergent Language Model

We have thus far defined the implicit semantics that the speaker derives from
the event and the listener extracts from the received information. However,
the vocabulary of speaker and listener for communication in an ESC system need
not be as vast as in any human-human languages or the NLP language models such
as BERT/GPT3 [20]. Hence, we need to map $\bm{z}$ ($\in\mathcal{W}$, the
_syntactic space_) to the encoded representation $\bm{u}$ ($\in\mathcal{U}$, a
finite vocabulary) that gets transmitted. We emphasize that $\mathcal{U}$ is a
mapping from the state description, not from the entities. Classical NLP
algorithms are trained on massive textual information from the web and are not
particularly optimized for wireless systems. Moreover, the training data used
for NLP can be biased and may raise security concerns. These already known
issues make them unsuitable for a physically realizable wireless application.
For an ESC system in which the intentions of both nodes are oblivious to one
another, one approach for the speaker to learn semantic awareness is via an
interactive conversation. Hence, we propose a novel two-player contextual
signaling game to learn the speaker transmit distribution
$\pi_{s}=\pi(\bm{u}\mid\bm{z})$, the listener inference distribution
$\pi_{l}=\pi(\bm{z}\mid\bm{u},{\bm{c}})\pi({\bm{c}}\mid\bm{u})$, where the
context ${\bm{c}}$ belongs to a finite set,
$\mathcal{C}\subset\mathcal{R}^{M}$. _Communication context_ here represents
the set of all possible message sequences and the valid logical
interpretations defined for a particular scenario corresponding to a task.
Given the syntactic space $\mathcal{W}$, context set $\mathcal{C}$ and the
representation space $\mathcal{U}$, the speaker’s strategy consists of sending
a message $\bm{u}$ after computing the causal state $\bm{z}$, using $\pi_{s}$,
such that $\sum\limits_{\bm{u}\in\mathcal{U}}\pi_{s}\\!=\\!1,\forall\bm{z}$,
where the possible set of $\bm{z}$ depends on the context ${\bm{c}}$. Given
the transmitted signal $\bm{u}$ (incomplete information), the listener’s
strategy consists of inferring it as $\widehat{\bm{z}}$ using an inference
distribution
$\pi_{l}=\pi({\bm{c}}\mid\bm{u})\pi(\widehat{\bm{z}}\mid\bm{u},{\bm{c}})$ such
that $\sum\limits_{\bm{z}}\pi_{l}\\!=\\!1,\forall\bm{u}$. Denote the set of
all such $\pi_{s}$ and $\pi_{l}$ as $\mathcal{M}_{s}$ and $\mathcal{M}_{l}$,
respectively. Combining these, we can define the _signaling game_ as the tuple
$(\mathcal{C},\mathcal{W},\mathcal{U},\mathcal{M}_{s},\mathcal{M}_{l})$. The
use of a game-theoretic approach here is apropos because, at equilibrium, the
transmitter will obtain a semantically aware encoder that transmits minimal
information such that the listener recovers the state description closest
semantically to the transmitted version. An alternative SC model is mapping
each entity to an encoded representation (from $\mathcal{U}$), and letting the
listener extract the relevant semantics from the reconstructed entities.
However, that is not suitable since it leads to a much larger number of bits
for representing all the entities part of the event, which is not
communication efficient.

Having outlined a general SC paradigm that applies to several future wireless
scenarios, we next look at how we design the emergent language and causal
reasoning processes that help us achieve the ESC gains.

(a)

(b)

Figure 2: (a) Proposed ESC system time split between emergent language and
data transmission phases. b) Illustration of emergent language.

##  III Proposed Signaling Games For Semantic Emergent Language Reasoning

Given our ESC model, we show in Fig. 2(a) how the emergent language training
and data transmission evolves. In the emergent language phase, given the
semantic state description $\bm{z}$, the objective is to derive an optimized
representation space $\mathcal{U}$, computed as the probability distribution
$\pi_{s}$. An optimized $\mathcal{U}$ allows the speaker to reduce its
transmission and the listener to extract maximum semantic information to
execute its task effectively during data transmission phase. In order to
ensure that the nodes can efficiently communicate with desired reliability on
tasks unseen during training (defined as _generalizability_), the emergent
language must be constructed on the principle of _compositionality_.
Compositionality can be defined as reasoning on complex state descriptions by
combining conclusions derived from smaller sub-parts of the state description.
This enables it to generalize to several tasks from the task distribution
$p(\tau)$. While our emergent language may have an initial overhead, its
duration will reduce over time, as shown in Fig. 2(a). This is because the
learned emergent language becomes generalizable and task agnostic over time.
We cast this problem as a two-player contextual signaling game, called
_emergent language game_.

###  III-A Two-player Contextual Signaling Game Model for Emergent Language

Motivated from the visual question and answering (Q/A) games in AI [21], we
define a signaling game between the speaker and listener as follows. The
language, as shown in Fig. 2(b), evolves via a series of questions
${\bm{q}}_{t}\in\\!\mathcal{W}$ (atomic question) by the listener and answers
provided by the speaker, ${\bm{a}}_{t}\\!\in\\!\mathcal{W}$ (atomic answer),
which help the listener reconstruct the description of the perceived event or
partial set of features to achieve its intent. ${\bm{q}}_{t}$ and
${\bm{a}}_{t}$ are vectors of dimensions $M\times 1$. The Q/A-scheme proceeds
over multiple rounds of communication. We next define the atomic question and
answer concepts.

######  Definition 1.

We define an _atomic question_ as one that involves just one entity and a
predicate (or property) and expects either an entity and predicate or a
Boolean variable as an answer (which is the _atomic answer_).

Each atomic answer represents a simpler event description within a context
${\bm{c}}$ and corresponds to a task $\tau$. Hence, the listener adapts to the
ESC system by learning simpler concepts. $\mathcal{W}$ represents the
syntactic space that defines the set of possible words used to describe the
state description.

######  Assumption 1.

The emergent language is created under the following assumptions.

  1. 1.

The syntactic space $\mathcal{W}$ is assumed to be known at both nodes before
the emergent language phase. However, the listener is unaware of the event
dynamics (the prior distribution that generates the $\bm{z}_{t}$).

  2. 2.

Only the listener is aware of the semantics stemming from any state
description $\bm{z}_{t}$.

The above assumptions outline the known variables at both nodes before the
start of communication. The context (unknown to listener) impact the possible
set of words in $\mathcal{W}$ that can describe the events part of a task.
However, the speaker only sends an encoded signal $\bm{u}$ (incomplete
information). The questions from the listener belong to a finite space,
communicated using very few bits (complete information), and have negligible
effect on the communication overhead. Hence, only the communication from
speaker to listener represents a signaling game [22]. At the emergence of the
language, the speaker has an optimized $\pi_{s}^{*}$ (with
$\bm{u}\in\mathcal{U}$) and the listener can reliably reconstruct the state
description using $\pi_{l}^{*}$ to execute the task at hand. The idea here is
that receiver strategies can infer the context to construe the very same
signal differently given different communication contexts. This allows the
listener to disambiguate signals that are ambiguously used by the sender [23].
At any communication round $t$, listener’s state is
$\widehat{\bm{z}}_{t}=(\tau,{\bm{q}}_{0},{\bm{a}}_{0},\cdots,{\bm{q}}_{t-1},{\bm{a}}_{t-1},\widehat{{\bm{c}}}_{t-1},{\bm{q}}_{t})$.
$\widehat{{\bm{c}}}_{t-1}$ represent the inference about the context
${\bm{c}}$ at time $t-1$. Similarly, the speaker has the state,
$\bm{z}_{t}=(e,{\bm{c}},{\bm{a}}_{0},\cdots,{\bm{q}}_{t-1},{\bm{a}}_{t-1},{\bm{q}}_{t})$,
after having observed the question ${\bm{q}}_{t}$ from the listener. The
listener samples a question based on a stochastic policy
$\Pi_{l}({\bm{q}}_{t}\mid\widehat{\bm{z}}_{t-1},\bm{\Phi})$. Question
${\bm{q}}_{t}$ captures the logical formula the listener wants to evaluate
from the set $\bm{\Phi}$. Further, the speaker samples the answer from the
stochastic policy $\Pi_{s}({\bm{a}}_{t}\mid\bm{z}_{t},{\bm{c}})$. $\Pi_{s}$ is
the event prior distribution and represents a method of generating the next
word given the current state sequence $\bm{z}_{t}$ and the context ${\bm{c}}$.
The state sequence $\bm{z}_{t}$ depends on the listener’s intent ($\bm{\Phi}$)
and the previous sequence of answers from the speaker. These stochastic
policies $\Pi_{l}$ and $\Pi_{s}$ are assumed to be known on the listener and
speaker sides, respectively. The syntactic space $\mathcal{W}$ is discrete
and, in principle, can be infinitely large depending on the context since
arbitrary length sequences may be produced. However, an ESC system’s
fundamental principle relies on transmitting less and doing more with small
data. Hence, the speaker restricts the encoded representation space
($\mathcal{U}$) to be finite. An appropriate choice here would be to optimize
the semantic information measures, unlike the classical mutual information
metric, which can misrepresent the semantic effectiveness. Hence, we propose a
novel formulation for the transmit and inference policies whereby the
objective for the speaker is to minimize the amount of semantic information
transmitted, and the listener wants to maximize the amount of semantic
information derived based on the received information. Moreover, the optimized
vocabulary implicitly defines the amount of communication resources (in terms
of the required rate to achieve specified reliability) that should be
allocated to a particular listener node. We define
$S_{s}(\bm{z}_{t};\bm{u}_{t}\mid\pi_{s,t},[\bm{z}_{t-1}],{\bm{c}})$ as the
semantic information conveyed by the speaker about the state $\bm{z}_{t}$
given the transmitted message $\bm{u}_{t}$, under a fixed transmit policy,
context and given the past states denoted by $[\bm{z}_{t-1}]$. Similarly, on
the receiver side, the amount of information acquired by the listener about
state $\widehat{\bm{z}}_{t}$ for fixed policies and given the previous
extracted states $[\widehat{\bm{z}}_{t-1}]$ is
$S_{l}(\widehat{\bm{z}}_{t};\bm{u}_{t}\mid\pi_{s,t},\pi_{l,t},[\widehat{\bm{z}}_{t-1}])$.
We next formally define $S_{s}$ and $S_{l}$.

###  III-B Semantic Information Measure

One approach to capture the semantic information is by using the propositional
logic over sets introduced by [12]. However, this approach does not generalize
to reasoning-based emergent language because the set-theoretic approach does
not have the compositionality properties which we discuss below. Therefore, we
propose a category theory based approach to represent semantic information
that is more general and satisfy the following compositionality properties.

######  Definition 2.

We define a _deductive logic_ as the following conjunction of predicates (or
relations if involving multiple entities), $r^{(N)}=(r_{1}\land
r_{2}\cdots\land r_{N})$. Here, $r^{(N)}$ holds iff all the predicates $r_{i}$
are true and $\land$ represents the conjunction operator.

######  Definition 3.

We define _chain-like rules_ as follows,
$(e_{0},r^{(N)},e_{N})\\!=\\!(e_{0},r_{1},e_{1})\land(e_{1},r_{2},e_{2})\land\cdots\land(e_{N-1},r_{N},e_{N}).$
The chain rule will be essential for proving analytical or logical theorems
using the emergent language. This follows also from the associative property
of the relation triplets.

Hence, if the speaker or listener is to derive logical conclusions, defined as
$\bm{\phi}_{i}$ in (2), from the existing or learned relations between the
entities, the above properties hold the key. To this end, category theory has
excellent algebraic structural properties that allows the grouping of all the
syntactic and semantic objects part of the language. Preliminary definitions
required for category theory terminologies used herein, such as copresheaves,
functor, and enriched categories, are provided in Appendix A. Next, we derive
here a novel interpretation of the semantic representation of the meaning
conveyed by the state $\bm{z}_{t}$ using category theory [24, 25]. These novel
representations of semantics lead us to define the semantic notion of
information. The prior SC works [7] and [6] models the semantics as including
only the relational triplets $({\bm{s}}_{i},{\bm{r}}_{i},{\bm{s}}_{i+1})$.
They do not model the deductive logic properties that help reasoning across
unseen and possibly arduous tasks. The following definition constructs a
category whose objects belong to $\mathcal{W}$.

######  Definition 4.

Any atomic word, represented by ${\bm{a}}_{t}$ or ${\bm{q}}_{t}$ or
expressions part of $\mathcal{W}$ form objects in a category $\mathcal{L}$,
called the _syntax category_. Expressions are defined as molecular words that
are a combination of multiple atomic words, e.g., the state $\bm{z}_{t}$. A
_morphism_ (a directed relation between the objects in any category) from
object ${\bm{x}}$ to object ${\bm{y}}$ in $\mathcal{L}$ is formed when
expression ${\bm{y}}$ extends from the expression ${\bm{x}}$.

Moreover, category $\mathcal{L}$ and the morphisms can be represented as a
category enriched in $[0,1]$. This means that we can represent the morphism,
${\bm{x}}\rightarrow{\bm{y}}$ using a probability distribution,
$\pi({\bm{y}}\mid{\bm{x}})\in[0,1],$ that captures the probability that
expression ${\bm{x}}$ extends to ${\bm{y}}$ (morphisms grounded in $[0,1]$).
However, this category $\mathcal{L}$ only represents the language’s
compositional part (or the syntax part) under consideration. Ideally, we
should be able to encode “what goes with what” (_syntactic part_) together
with the plausible, logical conclusions one can derive from the expressions
(_semantic part_). Further below, we show that _semantic category_
$\widehat{\mathcal{L}}$ can be represented as a transformation from the syntax
category, represented as, $F:\mathcal{L}\rightarrow\widehat{\mathcal{L}}$.

######  Lemma 1.

The semantic category $\widehat{\mathcal{L}}=[0,1]^{L}$ within the context
${\bm{c}}$ is an $[0,1]$ enriched category of representable copresheaves from
the syntax category $\mathcal{L}$.

###### Proof:

The proof is given in Appendix B. ∎

In Lemma 1, copresheaves of any object ${\bm{x}}\in\mathcal{L},$ represent all
the possible morphisms (expressions) from ${\bm{x}}$, within context
${\bm{c}}$. The usefulness of the Lemma is two-fold. Firstly, at the listener,
it helps to reason on any logical formula $\bm{\phi}_{i}$ (representing
objects in the semantic category) by splitting a complex state description
into smaller concepts and evaluating a set of smaller logical formulas
$\bm{\phi}_{j}$. Further, evaluate $\bm{\phi}_{i}$ using the chain-like rule
defined previously with $\bm{\phi}_{j}$’s as the components. This is only
possible if we show that the semantic space is also a category. Secondly,
leveraging Lemma 1, we provide a novel definition of the semantic information
conveyed by any expression ${\bm{x}}$ in the syntax category $\mathcal{L}$ as
follows.

######  Lemma 2.

The _semantic information_ conveyed by any expression ${\bm{x}}\in\mathcal{L}$
can be written as the average across the information carried by the
representable copresheaf that follow from ${\bm{x}}$. Further, mathematically,
we can write the semantic information conveyed by ${\bm{x}}$ as

$\vspace{-1mm}S({\bm{x}}\mid{\bm{c}})=\sum\limits_{{\bm{y}}\in
H^{\bm{x}}}\pi({\bm{y}}\mid{\bm{x}},{\bm{c}})\log\frac{\pi({\bm{y}}\mid{\bm{x}},{\bm{c}})}{\pi({\bm{x}}\mid{\bm{c}})}.$
(3)

###### Proof:

Lemma 1 provides a way to categorize the possible logical conclusions that
entail from any expression ${\bm{x}}$. The resulting distributional
representation provides a rigorous way to formulate the semantic information
conveyed by any expression ${\bm{x}}$ about ${\bm{y}}$, as follows. Inspired
by [12, 26], we can write

$\vspace{-2mm}S({\bm{y}};{\bm{x}}\mid{\bm{c}})=\begin{cases}\log\frac{\pi({\bm{y}}\mid{\bm{x}},{\bm{c}})}{\pi({\bm{y}})},\,\,\,&\textrm{if}\,\,{\bm{y}}\geq{\bm{x}}\\\
0,\,\,\,&\textrm{otherwise}.\end{cases}\vspace{-1mm}$ (4)

Further, we can obtain the semantic information captured by ${\bm{x}}$ as the
average of the semantic information conveyed by possible worlds that contain
${\bm{x}}$ which is (4). ∎

Intuitively, (4) represents the degree of confidence in a possible logical
entailment ${\bm{y}}$ after having observed ${\bm{x}}$. Lemma 2 provides a way
to compute the semantic information conveyed by $\bm{z}_{t}$ as
$S_{s}\left(\bm{z}_{t}\mid\pi_{s,t}[\bm{z}_{t-1}],{\bm{c}}\right)=\sum\limits_{{\bm{y}}\in
H^{\bm{z}_{t}}}\pi({\bm{y}}\mid[\bm{z}_{t}],{\bm{c}})\log\frac{\pi({\bm{y}}\mid[\bm{z}_{t}],{\bm{c}})}{\pi({\bm{y}}\mid[\bm{z}_{t-1}],{\bm{c}})}.$
Further, we average across all possible signals $\bm{u}_{t}$ to arrive at the
average semantic information conveyed by $\bm{z}_{t}$ for a particular policy
$\pi_{s,t}$ and context ${\bm{c}}$ as

$\displaystyle\mathbb{E}_{\bm{u}_{t}}\left[S_{s}(\bm{z}_{t};\bm{u}_{t}\mid\pi_{s,t},[\bm{z}_{t-1}],{\bm{c}})\right]$
$\displaystyle=\sum\limits_{\bm{z}_{t}}\pi\left(\bm{z}_{t}\mid{\bm{c}},[\bm{z}_{t-1}]\right)\underbrace{\left[\sum\limits_{\bm{u}_{t}}\pi_{s,t}\log\frac{\pi_{s,t}}{\pi(\bm{u}_{t})}\right]}_{\mbox{avg.
bits}}\underbrace{\vphantom{\sum\limits_{\bm{u}_{t}}}S_{s}(\bm{z}_{t}\mid[\bm{z}_{t-1}],{\bm{c}})}_{\mbox{semantics}},\\!\\!$
(5)
$\displaystyle\mbox{where},\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\pi(\bm{u}_{t})$
$\displaystyle=\sum\limits_{\bm{z}_{t}}\pi_{s,t}\pi(\bm{z}_{t}\mid{\bm{c}},[\bm{z}_{t-1}]),\,\,\mbox{and}\,\,\pi_{s,t}=\pi(\bm{u}_{t}\mid[\bm{z}_{t}]).$

An appropriate unit to represent
$\frac{S_{s}(\bm{z}_{t};\bm{u}_{t}\mid\pi_{s,t},[\bm{z}_{t-1}],{\bm{c}})}{\left[\sum\limits_{\bm{u}_{t}}\pi_{s,t}\log\frac{\pi_{s,t}}{\pi(\bm{u}_{t})}\right]}$
will be _average semantics/s/Hz_. Next, we look at the average semantic
information captured at the listener side, given that the actual transmitted
state was $\bm{z}_{t}$ and for a specific listener policy
$\pi_{l,t}=\pi({\bm{c}},\widehat{\bm{z}}_{t}\mid\bm{u}_{t},[\widehat{\bm{z}}_{t-1}])$.
For this purpose, we first define the following corollary on _semantic
similarity_ that follows directly from the copresheaves definition.

######  Corollary 1.

The similarity metric $Z_{xy}$ between two objects, ${\bm{x}}$ and ${\bm{y}}$,
can be defined as the intersection of the representable copresheaf between
them.

$\vspace{-1mm}\footnotesize Z_{xy}=\sqrt{\frac{\sum\limits_{\bm{z}\in
H^{{\bm{x}}}\cap H^{{\bm{y}}}}h^{{\bm{x}}}(\bm{z})}{\sum\limits_{\bm{z}\in
H^{x}}h^{{\bm{x}}}(\bm{z})}\frac{\sum\limits_{\bm{z}\in H^{{\bm{x}}}\cap
H^{{\bm{y}}}}h^{{\bm{y}}}(\bm{z})}{\sum\limits_{\bm{z}\in
H^{{\bm{y}}}}h^{{\bm{y}}}(\bm{z})}}.\vspace{-0mm}\vspace{-1mm}$ (6)

Whenever, $H^{{\bm{x}}}=H^{{\bm{y}}}$, then $Z_{ij}=1$ and when
$H^{{\bm{x}}}\cap H^{{\bm{y}}}=\emptyset$, $Z_{ij}=0$.

Leveraging corollary 1, we obtain the average semantic information extracted
by listener as

$\vspace{-3mm}\begin{array}[]{l}\mathbb{E}_{\bm{u}_{t}}\left[S_{l}(\widehat{\bm{z}}_{t};\bm{u}_{t}\mid\bm{z}_{t},[\widehat{\bm{z}}_{t-1}],{\bm{c}},\pi_{l,t})\right]=\sum\limits_{\bm{u}_{t}}\pi\left(\bm{u}_{t}\mid[\bm{z}_{t}]\right)S_{s}({\widehat{\bm{z}}}_{t}\mid[\widehat{\bm{z}}_{t-1}],{\bm{c}})\left[\sum\limits_{\widehat{\bm{z}}_{t},\widehat{{\bm{c}}}}\pi_{l,t}\log\frac{\pi_{l,t}}{\pi(\widehat{\bm{z}}_{t}\mid{\bm{c}},[\widehat{\bm{z}}_{t-1}])}Z_{\widehat{z}_{t}z_{t}}\right].\end{array}$
(7)

In (7),
$\small[\sum\limits_{\widehat{\bm{z}}_{t},{\bm{c}}}\pi_{l,t}\log\frac{\pi_{l,t}}{\pi(\widehat{\bm{z}}_{t}\mid{\bm{c}},[\widehat{\bm{z}}_{t-1}])}Z_{\widehat{z}_{t}z_{t}}]$
represents the probability that $\bm{z}_{t}\\!=\\!\widehat{\bm{z}}_{t}$,
semantically (using the metric $Z_{\widehat{z}_{t}z_{t}}$ defined). We now
have the necessary ingredients to define the two-player signaling game NE
problem.

###  III-C Signaling Game Model and Generalized Nash Equilibrium Problem

Using the metrics above, we further formulate the solutions of the signaling
game defined using the tuple
$(\mathcal{C},\mathcal{W},\mathcal{U},\mathcal{M}_{s},\mathcal{M}_{l})$ as a
_Bayesian generalized NE_[27, 22] (generalized due to the constraints part of
the problem formulation below). The NE strategies are such that for all
$\bm{z}_{t}\\!\in\\!\mathcal{W}$ and ${\bm{c}}\\!\in\\!\mathcal{C}$

$\displaystyle\pi_{s,t}^{*}\,\in$
$\displaystyle\,\arg\max\limits_{{\pi}_{s,t}}-\mathbb{E}_{\bm{u}_{t}}\left[S_{s}(\bm{z}_{t};\bm{u}_{t}\mid{\pi}_{s,t},[\bm{z}_{t-1}],{\bm{c}})\right],\,$
(8a)
$\displaystyle\,\,\textrm{s.t.}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathbb{E}[V({\pi}_{s,t},\pi_{l,t})]\leq
D$ (8b) $\displaystyle\vspace{-0.5mm}\pi_{l,t}^{*}\,\in$
$\displaystyle\,\arg\max\limits_{\pi_{l,t}}\mathbb{E}_{\bm{u}_{t}}\left[S_{l}(\widehat{\bm{z}}_{t};\bm{u}_{t}\mid{\pi}_{l,t},\pi_{s,t}^{*},[\widehat{\bm{z}}_{t-1}])\right],\vspace{-2mm}$
(8c)

where $V(\pi_{s,t},\pi_{l,t})\\!=\\!c(\bm{u}_{t})-\log\pi_{l,t},$ and the
expectation of $V$ is over the policies $\pi_{s,t},\pi_{l,t}$. $c(\bm{u}_{t})$
represents the cost of producing $\bm{u}_{t}$ and $-\\!\log\pi_{l,t}$
represents the listener’s surprisal about inferring $\bm{z}_{t}$ given
$\bm{u}_{t}$. The equation (8a) states that the strategy space
$\mathcal{M}_{s,t}$ consists of signals $\bm{u}_{t}\\!\in\\!\mathcal{U}$ that
minimizes the expected semantic information at speaker’s end. Constraint (8b)
guarantees that the speaker responds optimally to the listener’s strategy.
(8c) states that the strategy space $\mathcal{M}_{l,t}$ consists of states
$\widehat{\bm{z}}_{t}\\!\in\\!\mathcal{W}$ that maximize the expected semantic
information at the listener and responds optimally to the speaker strategy.
Next, we formally define the equilibrium points.

######  Definition 5.

As defined in [28], we define a strategy $(\pi_{s,t}^{*},\pi_{l,t}^{*})$ as a
_local NE_ for (8) if there exist open sets
$\mathcal{M}_{g_{r}}\subset\mathcal{M}_{r,t}$ such that
$\pi_{r,t}^{*}\in\mathcal{M}_{g_{r}}$, where $r\in\left\\{s,l\right\\}$, and
satisfies

$\displaystyle-\mathbb{E}_{\bm{u}_{t}}\left[S_{s}(\bm{z}_{t};\bm{u}_{t}\mid{\pi}_{s,t}^{*},[\bm{z}_{t-1}],{\bm{c}})\right]$
$\displaystyle\geq-\mathbb{E}_{\bm{u}_{t}}\left[S_{s}(\bm{z}_{t};\bm{u}_{t}\mid{\pi}_{s,t},[\bm{z}_{t-1}],{\bm{c}})\right],\,\,\forall\,\pi_{s,t}\in\,\mathcal{M}_{g_{s}}(\pi_{l,t}^{*}),$
(9a)
$\displaystyle\mathbb{E}_{\bm{u}_{t}}\left[S_{l}(\widehat{\bm{z}}_{t};\bm{u}_{t}\mid{\pi}_{l,t}^{*},\pi_{s,t}^{*},[\widehat{\bm{z}}_{t-1}],{\bm{c}})\right]$
$\displaystyle\geq\mathbb{E}_{\bm{u}_{t}}\left[S_{l}(\widehat{\bm{z}}_{t};\bm{u}_{t}\mid{\pi}_{l,t},\pi_{s,t}^{*},[\widehat{\bm{z}}_{t-1}],{\bm{c}})\right],\,\,\forall\,\pi_{l,t}\in\,\mathcal{M}_{g_{l}}(\pi_{s,t}^{*}).\vspace{-2mm}$
(9b)

When $\mathcal{M}_{g_{r}}=\mathcal{M}_{r},\forall r$, then the equilibrium is
unique.

Next, we evaluate the equilibrium points corresponding to (8). The speaker in
this communication instance aims to minimize the average amount of transmitted
semantic information carried by $\bm{u}_{t}$, represented by
$S_{s}(\bm{z}_{t};\bm{u}_{t}\mid{\pi}_{s,t},[\bm{z}_{t-1}],{\bm{c}})$.
However, the speaker cannot independently optimize this since its strategy
space $\mathcal{M}_{s,t}$ depends on the listener inference distribution via
the constraint (8b). The mutual understanding evolves via the two-player game
proposed in (8), where the listener communicates about the logical formulas it
wants to evaluate, and the speaker responds by providing an encoded state
description ($\bm{u}_{t}$) corresponding to the question. We assume that
${\bm{q}}_{t}$ and $\bm{u}_{t}$ are recovered without any error at the speaker
and listener, respectively (communication links are reliable during the
emergent language phase).

###  III-D Characterization of the Generalized Local Nash equilibrium

To find the generalized local NE, one conventional approach is AM between
speaker and listener objectives. AM is an iterative procedure for solving the
NE objectives jointly over all variables by alternating maximizations over the
individual subsets of variables (two NE distributions and Lagrange
multipliers). The estimated NE distributions using AM can be computed as
follows.

######  Proposition 1.

The NE strategies in (8) can be obtained as the following alternating updates.
The speaker’s strategy is obtained as

$\vspace{-2mm}\begin{array}[]{l}\pi_{s,t}^{*}=\pi(\bm{u}_{t-1})\exp\left(\frac{-1}{S_{s}(\bm{z}_{t}\mid[\bm{z}_{t-1}],{\bm{c}})\pi(\bm{z}_{t}\mid{\bm{c}})}(\lambda_{s}(c(\bm{u}_{t})-\log\pi_{l,t})-\alpha_{\bm{z}_{t}})-1\right).\end{array}\vspace{-1mm}$
(10)

and the listener’s inference distribution is

$\begin{array}[]{l}\pi_{l,t}^{*}=\frac{1}{\pi(\bm{u}_{t})}\exp\left(\frac{-1}{\pi\left(\bm{u}_{t}\mid[\bm{z}_{t}]\right)S_{s}({\widehat{\bm{z}}}_{t}\mid[\widehat{\bm{z}}_{t-1}],{\bm{c}})Z_{\widehat{z}_{t}z_{t}}}\left(\alpha_{\bm{u}_{t}}-\pi(\bm{u}_{t}\mid[\bm{z}_{t}])S_{s}({\widehat{\bm{z}}}_{t}\mid[\widehat{\bm{z}}_{t-1}],{\bm{c}})Z_{\widehat{z}_{t}z_{t}}\log\pi_{l,t-1}\right)\right).\end{array}$
(11)

###### Proof:

The proof is provided in Appendix C. ∎

The node policies (10) and (11) suggest that the encoded signal depends on the
semantics (causal reasoning) conveyed by the state description and not on the
syntactic representation. Intuitively, the emergent language can represent two
state descriptions $\bm{z}_{1},\bm{z}_{2}$ leading to the same logical
conclusions (relevant to the listener) using the same signal $\bm{u}$.
Intuitively, the speaker transmit policy (10) tends to choose a transmit
message $\bm{u}_{t}$ that requires a smaller transmission cost and causes the
listener to be less surprised. The slope parameter
$\frac{1}{S_{s}(\bm{z}_{t}\mid[\bm{z}_{t-1}],{\bm{c}})\pi(\bm{z}_{t}\mid{\bm{c}})}$
indicates that state descriptions $\bm{z}_{t}$ with more semantic information
are represented more ambiguously by the speaker and on average cost more in
terms of the number of bits communicated. Since we consider the history of
state descriptions $[\bm{z}_{t-1}]$ in the player strategies, then if any
$\bm{z}_{t}$ does not provide any new semantic information (redundant
information), the speaker policy’s slope tends to $\infty$. In this case, the
listener is also not surprised (since the listener strategy also depends on
the extracted past states). Hence, $\pi_{s,t}$ converges to a Dirac delta
distribution, choosing $\bm{u}_{t}$ with zero cost, i.e., no signal is
transmitted. This significantly reduces transmission compared to any classical
system unaware of semantic history. (11) can be intuitively interpreted as
choosing the $\pi_{l,t}$ with its peak close to $\widehat{\bm{z}}_{t}$ that
maximizes the average semantic information extracted by the listener for any
particular $\bm{u}_{t}$. Algorithm 1 summarizes our proposed AM solution.
Next, we prove that the resulting AM updates lead to local convergence.

######  Proposition 2.

The AM updates obtained in (10) and (11) for the two-player signaling game
proposed converges to a local Nash equilibrium as defined in Definition 5.

###### Proof:

The objective functions in (8) are jointly non-concave w.r.t the combined
strategy $(\pi_{s,t},\pi_{l,t})$. Hence, the resulting NE cannot be unique.
However, for a fixed listener policy, the speaker objective function (8a) is
concave and hence leads to the global optimum, thus satisfying (9a) for the
strategy $\pi_{s,t}^{*}$. The listener objective function in (8c) is non-
concave w.r.t $\pi_{l,t}$ and can be written as summation of a concave and
convex part. To solve this, we computed an approximate function
$\widehat{F}_{l}(\pi_{l,t},\pi_{s,t})$ (defined in (24)) to the original
listener objective function (8c) by approximating the convex part using the
first order Taylor series expansion. It can be shown that the approximate
function (24) satisfies
${F}_{l}(\pi_{l,t},\pi_{s,t})\geq\widehat{F}_{l}(\pi_{l,t},\pi_{s,t})$. The
resulting lower bound is concave [29]; hence, the achieved solution (11) is a
local optimum of the original listener objective function. Hence, an AM update
between the speaker and listener policy here leads to local NE. The proof for
convergence of the AM updates is classical [30]. ∎

Algorithm 1 Proposed Two-Player Contextual Signaling Game

Given: Sample $\tau_{t}\sim p(\mathcal{\tau}),p(\mathcal{C}):\mbox{the task
and distribution over contexts (subscript $t$ represents start time of a
task).}$
Initialize: Choose larger values for
$\lambda_{s},\bm{\alpha}_{s},\bm{\alpha}_{l}$.

if ($t>0$)

Initialize $\pi_{s,t}=\pi_{s,t-1}^{*},\pi_{l,t}=\pi_{l,t-1}^{*}$

else

Choose uniform distributions for $\pi_{s},\pi_{l}$.

end if

while AM not converged do

Sample the context ${\bm{c}}\sim p(\mathcal{C})$

for all  ${\bm{c}}$ do

Evaluate $\pi_{s},\pi_{l}$ using (22) and (11), respectively

Update $\lambda_{s},\bm{\alpha}_{s},\bm{\alpha}_{l}$ using bisection method
[31] such that the respective constraints

are met.

end for

end while

Output $\pi_{s,t}^{*},\pi_{l,t}^{*}$.

###  III-E Analysis of the Signaling Game Equilibria for Emergent Language

We have so far looked at computing the encoder and decoder probability
distributions using the signaling game in Section III-D. Next, we look at how
the speaker chooses the transmit signal and the listener maps the received
signal to the state description given these distributions. Naive approach
would be to consider the signals ($\bm{u},\widehat{\bm{z}}$) as those which
maximize the respective probabilities. However, as we show here, that need not
be the optimal solution (in terms of the speaker transmitting less and the
listener extracting maximum). For notational simplicity, we remove the
subscript $t$.

######  Definition 6.

An equilibrium $(\pi_{s}^{*},\pi_{l}^{*})$ is a _separating equilibrium_ [32]
if each state $\bm{z}$ is encoded as different signals $\bm{u}$. That is,
$\mathcal{W}$ can be partitioned into regions $\mathcal{W}_{k}$ such that
$\\!\sum\limits_{\bm{z}\in\mathcal{W}_{k}}\\!\pi(\bm{u}_{k}\mid\bm{z})\\!=\\!1$.
A _pooling equilibrium_ occurs if there is a $\bm{u}$ that is sent for all
$\bm{z}$ with probability one. When
$\lvert\mathcal{U}\rvert\\!<\\!\lvert\mathcal{W}\rvert$, with the same signal
transmitted for multiple states but not for all, the resulting equilibrium is
a _partial pooling equilibrium_.

Using these definitions, we analyze the speaker and listener strategies for
different separating and pooling signaling equilibria, as a function of system
parameters $\lambda_{s}$ and $\lvert\mathcal{U}\rvert$.

######  Theorem 1.

When the language emerges at the convergence of algorithm 1, the following
equilibria can be reached.

  1. 1.

For $\lambda_{s}\in[0,1]$, the minimum semantic information at speaker side
can be achieved by choosing uniformly random the transmit message. Hence, the
optimal policies are
$\pi(\bm{u}\mid\bm{z})=\frac{1}{K},\pi(\bm{z}\mid\bm{u})=\pi(\bm{z})$ and
$H_{s}(\bm{u})=\log K$, where $K$ denotes the cardinality of $\mathcal{U}$.
$H({\bm{x}})$ is the Shannon entropy here.

  2. 2.

For $\lambda_{s}\\!>\\!1$, the speaker objective can be maximized by choosing
a bijective transformation from $\bm{z}$ to $\bm{u}$ for the transmit policy
(means $\lvert\mathcal{U}\rvert\\!=\\!\lvert\mathcal{W}\rvert$). This is the
perfect signaling or separating equilibrium.

  3. 3.

For the case of pooling signaling equilibrium, the speaker may send the same
$\bm{u}$ for all $\bm{z}$ ($\lvert\mathcal{U}\rvert=1$). While this scheme may
achieve the minimum semantic information at the speaker, it does not provide
any semantic information at the listener and hence it is not suitable for ESC.

  4. 4.

In partial pooling, the listener extracts maximum semantic information when
the speaker partition its semantic category space into a Voronoi tessellation,
where each $\bm{u}$ corresponds to a distinct partition.

###### Proof:

Proof is provided in Appendix D. ∎

From Theorem 1, for an ESC system where
$\lvert\mathcal{U}\rvert<\lvert\mathcal{W}\rvert$, the partial pooling
equilibrium is more realistic. An optimal partition at the speaker is such
that $\bm{u}_{k}$ is transmitted whenever the average semantic information
extracted at the listener is the highest among all possible partitions
$\mathcal{W}_{k}$. The proposed ESC system can compute $\pi_{l,t}^{*}$ using
the listener’s surprise ($-\log\pi_{l,t}^{*}$) fed back during the emergent
language. Hence, the average semantic information extracted by the listener
for different possible partitions can be evaluated. This makes it possible for
the speaker to choose the Voronoi tessellation for the encoded signal. In this
case, given a Voronoi tessellation of $\mathcal{W}$, the receiver in turn can
choose an $\widehat{\bm{z}}\in\mathcal{W}$ for each signal $\bm{u}_{k}$ that
describes the average state in $\mathcal{W}_{k}$ optimally (in semantic sense
and given the environment or prior for $\bm{z}$). An optimal interpretation
consists thus of Bayesian estimators for each cell $\mathcal{W}_{k}$, that is,
$\arg\min_{z\in\widehat{\vspace{-4mm}\mathcal{W}}}\int_{{\widehat{{\bm{W}}}}}\left\lVert\bm{z}-\widehat{\bm{z}}\right\rVert_{S}\pi(d\widehat{\bm{z}}\mid\bm{u}),$
where $\widehat{\mathcal{W}}$ represents the space over which
$\pi(d\bm{z}\mid\bm{u})$ is defined.

##  IV  NeSy Reasoning for Optimized Semantic Reliability

We next look at the reasoning NN components at the speaker and listener. In
short, during the data transmission phase, the speaker’s reasoning component
allows the computation of the optimal set of entities and relations that
causally explain the data. The awareness of how causal description gets used
by the listener enables the speaker to encode with minimal bits during the
emergent language phase discussed in Section III. At the listener side,
reasoning (aided by compositional language) enhances it with the capability to
derive the required logical conclusions to execute the task. Our next key
question is this: What is an optimal reasoning scheme at both the nodes such
that it enables the listener to reliably reconstruct the semantic aspect
considering that the transmitted signal is distorted via the underlying
channel $p({\bm{x}}\mid\bm{u})$ ? Before discussing the proposed reasoning
components, we first assess how reasoning helps our ESC system reduce the
average number of bits for transmission and achieve better semantic
reliability than classical systems. _Semantic reliability_ here is defined as
the accuracy in terms of the semantics reconstructed at the listener compared
to the intended semantics transmitted from the speaker.

###  IV-A Average Semantic Representation Length for Classical and Emergent
Language based ESC

Let ${\bm{c}}$ be the context (a vector quantity), drawn from
$p_{c}({\bm{c}})$. Depending on the context ${\bm{c}}$, it is possible that a
certain entity relation pair (or entity relation sequence of pairs) is not
valid. Hence, if we consider the underlying DAG as in GFlowNet, which
describes the sequence of states leading to the data, the possible state
sequences will be a subset of DAG learned via GFlowNet. Depending on this
subset graph size, the size of the actually transmitted vocabulary
$\mathcal{U}$ can be dynamically adjusted if the emergent language is created
considering the context ${\bm{c}}$. Motivated by the importance of
communication context significance in the optimal vocabulary design, we derive
the following result.

######  Theorem 2.

For a particular syntactic space, $\mathcal{W}$ and context distribution
$p({\bm{c}})$ over $\mathcal{C}$, the average amount of bits to represent the
state description in an ESC system can be bounded as follows.

$\vspace{-2mm}\sum\limits_{{\bm{c}}\in\mathcal{C}}\pi({\bm{c}})H(\bm{z}_{i}\mid{\bm{c}})\leq\sum\limits_{\bm{u}_{i}\in\mathcal{U}}\pi(\bm{u}_{i})l_{i}\leq-\sum\limits_{{\bm{c}}}\pi({\bm{c}})\sum\limits_{\bm{z}_{i}}\pi(\bm{z}_{i}\mid{\bm{c}})\lceil\log\pi(\bm{z}_{i}\mid{\bm{c}})\rceil,\vspace{-0.2mm}$
(12)

where $l_{i}$ represents the amount of bits to represent $\bm{u}_{i}$. For a
classical system, the bounds are

$H({\bm{s}}_{i})\leq\sum\limits_{\bm{u}_{i}\in\mathcal{U}}\pi(\bm{u}_{i})l_{i}\leq\max\limits_{{\bm{c}}}\sum\limits_{\bm{z}_{i}}\pi(\bm{z}_{i}\mid{\bm{c}})\left[\sum\limits_{{\bm{s}}_{i}\in\bm{z}_{i}}\lceil\log\pi({\bm{s}}_{i}\mid{\bm{c}})\rceil\right].\vspace{-3mm}$
(13)

###### Proof:

See Appendix E. ∎

From Theorem 2, it is clear that for an ESC system, the lower and upper bounds
for a physical representation of the semantics are smaller to those in a
classical system (transmitting a compressed version of the entities),
justifying its transmission efficiency. Next, we look at whether the
listener’s semantic reliability improves by incorporating reasoning at the
nodes compared to classical systems.

######  Theorem 3.

For a given representation space $\mathcal{U}$, the lower bound on the
semantic error probability ($S_{e}-$representing reliability) is always less
than or equal to the lower bound on the probability of bit error ($P_{e}$)
measure achieved using classical communication system.

$\vspace{-2mm}\begin{array}[]{l}P_{e}\geq\frac{H(\widehat{\bm{z}}_{c}\mid\bm{z}_{c})-1}{\log\lvert\mathcal{W}\rvert},\,\,\,S_{e}\geq\frac{H(\bm{z}\mid\widehat{\bm{z}})-H({\bm{e}}\mid\widehat{\bm{z}})}{\log\lvert\mathcal{W}\rvert}\\\
\mbox{where},\,\frac{H(\widehat{\bm{z}}_{c}\mid\bm{z}_{c})-1}{\log\lvert\mathcal{W}\rvert}\geq\frac{H(\bm{z}\mid\widehat{\bm{z}})-H({\bm{e}}\mid\widehat{\bm{z}})}{\log\lvert\mathcal{W}\rvert}.\vspace{-2mm}\end{array}\vspace{-2mm}$
(14)

###### Proof:

See Appendix F. Here, ${\bm{e}}$ represents the error in semantics recovered
at the listener, and $\bm{z}_{c},\widehat{\bm{z}}_{c}$ means the state
descriptions for the classical system. ∎

Theorem 3 shows that inducing reasoning at speaker and listener can improve
semantic reliability compared to a classical system that uses the same amount
of bits to communicate. In other words, the ESC system could choose to
transmit at a higher rate than a classical system to achieve similar semantic
reliability. Next, we look at the structure of reasoning components at the
speaker and listener that can help the ESC system achieve gains discussed
above.

###  IV-B Semantic State Descriptor at Speaker

The causal state description at the speaker is represented as
$\bm{z}=\left[{\bm{s}}_{0},{\bm{s}}_{1}\cdots,{\bm{s}}_{f}\right]^{T}\\!$ and
learned as the posterior distribution (1). The GFlowNet architecture that we
use to learn this posterior is based on [33, Fig. 2]. Each directed edge
(between ${\bm{s}}_{i}$’s) is embedded using its source and target’s
embeddings (_grounded_ value), with an additional vector indicating whether
the edge is present in $G$. These embeddings are fed into a linear
transformer, with two separate output heads. The first head (above) gives the
probability of adding a new edge
$P_{\bm{\theta}}(G^{\prime}\\!\mid\\!G,\neg{\bm{s}}_{f})$, using the mask $M$
associated with $G$ to filter out invalid actions. $G^{\prime}$ is the newly
formed DAG. The second head (below) gives the probability of terminating the
trajectory, $P({\bm{s}}\\!=\\!{\bm{s}}_{f}\\!\mid\\!G)$. Once the terminal
state is created, we would have formed a probabilistic graphical model to
represent the data’s causal structure ($\bm{z}$) using the novel explainable
AI tools of GFlowNet.

###  IV-C Listener Semantic Reasoning

At the listener, the transmitted signals are received as ${\bm{x}}$ after
passing through the channel whose behavior is captured by the transition
probability $p({\bm{x}}\mid\bm{u})$. The received signals pass through the
decoder which maps the received signal to representation space $\mathcal{U}$
using a single layer deep NN (DNN) with parameters $\bm{\eta}$ and
$\widehat{\bm{u}}\\!=\\!g_{\bm{\eta}}({\bm{x}})$, with
$\widehat{\bm{u}}\in\mathcal{U}$. From the decoded signals $\widehat{\bm{u}}$,
the semantic state and context are extracted using the inference distribution
$\pi_{l}$. From the extracted semantic state $\widehat{\bm{z}}$, the listener
intends to evaluate the logical formulas $\bm{\phi}_{i}$. In other words, the
listener would want to infer the possible world states arising from the
observed event at the speaker. The listener decides the definition of these
logical formulas based on their intent. Its intent can be either
reconstruction of the transmitted events, prediction of future events, or
expected impact of the events on the world state. Next, we look at how the
listener can utilize GFlowNet to extract the possible world models that follow
from the estimated states. For this purpose, we propose to utilize GFlowNet as
a generative process to model the probabilities in a discrete data space.
Consider that $\bm{\phi}\in{\bm{\Phi}}$, represents the $D$ dimensional output
space which is discrete. For example, the output space can be the possible
images (of physical objects in the environment) that the listener wants to
reconstruct from the estimated state sequence. Or it can be that the listener
wants to predict possible future events that could arise from the current
sequence of states. Given the extracted state description, GFlowNet, when used
as a sampler [18] tries to find the posterior probability of the logical
formula, as defined in (2). We use $\bm{\psi}$ to capture the listener’s
GFlowNet parameters.

Given the reasoning network architecture, we further briefly explain how we
can exploit the _chain of thought reasoning_ [14] to evaluate a logical
formula given a complex state description that is unseen during training. This
procedure explains how the listener semantic reasoning helps generalize to
unseen scenarios aided by the compositional emergent language. Assume that the
state description $\widehat{\bm{z}}$ can be split into $R$ simpler state
descriptions, i.e.,
$\widehat{\bm{z}}=(\widehat{\bm{z}}_{1},\widehat{\bm{z}}_{2},\cdots,\widehat{\bm{z}}_{R})$.
Assume that the simpler state description $\widehat{\bm{z}}_{i}$ (each of
dimension $MN\times 1$) leads to the possible outcome $\bm{\phi}_{i}$, as
evaluated by GFlowNet. Further, using the chain-like rules in definition 3, we
can write the complex logical formula
$\bm{\phi}=(\bm{\phi}_{1},\bm{\phi}_{2},\cdots,\bm{\phi}_{R}).$ The chain-like
rules can be applied since we can use the property of functors in category
theory (see Appendix A) to state that if two objects $\widehat{\bm{z}}_{1}$
and $\widehat{\bm{z}}_{2}$ in the syntax category are related, then the
corresponding outcomes $\bm{\phi}_{1}$ and $\bm{\phi}_{2}$ are also related.

Figure 3: GFlowNet for logical theorem proving, a symbolic process.

The corresponding architecture to evaluate $\bm{\phi}$ (with $R=4$) is
illustrated in Fig. 4. In short, this functionality highlights GFlowNet’s
logical theorem proving capability, the symbolic component for the proposed
NeSy AI algorithm. Next, we define the relevant metrics required for
formulating the GFlowNet parameters optimization problem.

###  IV-D Semantic Distortion and Semantic Similarity

The channel imperfections result in an error in the reconstructed $\bm{z}_{t}$
at the listener; hence, the logical conclusions evaluated by the listener can
be erroneous, and this error in $\bm{\phi}$ is called _semantic distortion_.
Analytically, this can be captured as

$\vspace{-2mm}E_{t}(\bm{z}_{t},{\widehat{\bm{z}}}_{t})=\displaystyle\sum\limits_{i=1}^{L}\left\lVert\bm{\Phi}_{i}(\bm{z}_{t})-{{\bm{\Phi}_{i}}(\widehat{\bm{z}}_{t})}\right\rVert^{2}.\vspace{-0mm}$
(15)

We also define the error measure in terms of the difference in semantic
information conveyed by the speaker and that learned by the listener,
$E_{t}({S}_{t},{\widehat{S}}_{t})=\lvert S_{t}-\widehat{S}_{t}\rvert^{2}.$
These semantic distortion measures help to quantify how much semantic
information the listener can extract from a corrupted version of the message.

Next, we define the concept of _semantic similarity_ which significantly
differs from the bit error rate (BER) of classical systems and is required for
defining the semantic reliability constraint. In a sense, we may send a
message that experiences a high BER, but the semantic information (represented
by the semantic similarity) may be sufficient to recover the intended meaning.
For example, say the listener receives the English sentence “Aln the vhicles
have sped lss thn 50 km/hr” instead of “All the vehicles have speed less than
50 km/hr” (actually intended by the speaker). The received text has high BER
(called an error at syntactic level [3]), i.e., typos, but its semantic
content is still rich and can be recovered. Several sentences can correspond
to the same semantic space in our ESC model. The decoded state description at
the listener restricted to this semantic message space (say represented as
$\mathcal{S}_{t}$ corresponding to message $\bm{z}_{t}$) can represent the
same semantic content and they are semantically similar. Hence, we can achieve
the same reliability. This semantic message space (representing semantic
similarity) corresponding to $\widehat{\bm{z}}_{t}$ can be described as
$E_{t}(\bm{z}_{t},{\widehat{\bm{z}}}_{t})\leq\delta,\,\,\mbox{s.t.}\,\,E_{t}({S}_{t},{\widehat{S}}_{t})=0.$
From a category theory perspective, we can interpret the semantic message
space as the set of all $\bm{z}_{t}$ such that the representable copresheaves
are identical. Mathematically, we can write
$\mathcal{S}_{t}=\left\\{\forall\,\widehat{\bm{z}}_{t}\,\,\,s.t.\,\,\,H^{\widehat{\bm{z}}_{t}}=H^{\bm{z}_{t}}\right\\}.$
Moreover, note that $\bm{\phi}(\widehat{\bm{z}})\in H^{\widehat{\bm{z}}_{t}}$.
Compared to the classical BER measure, the semantic distortion
$E_{t}(\bm{z}_{t},{\widehat{\bm{z}}}_{t})$ need not be restricted by an
arbitrarily low value to achieve a reliability close to $1$.

###  IV-E Causal Influence of Communication Channel on ESC and Semantic
Effectiveness

Further, we introduce metric $C_{t}$, interpreted as the causal influence on
ESC, and it captures the causal impact of the speaker’s message (via
listener’s actions) as observed through a channel with a response
characterized using $p({\bm{x}}_{t}\mid\bm{u}_{t})$. In short, $C_{t}$
captures the semantic effectiveness (inversely proportional to $C_{t}$) of the
transmitted message to the end user. We define

$\vspace{-3mm}\begin{array}[]{l}\small
C_{t}(\bm{z}_{t},\bm{z}_{t}(\bm{\eta}))=D_{KL}\left(p({\bm{a}}_{t}\mid\bm{z}_{t})\,||\,\sum\limits_{{\bm{x}}_{t}}p(\widehat{\bm{z}}_{t}\mid\widehat{\bm{u}}_{t})p({{\bm{x}}}_{t}\mid\bm{u}_{t})p({\bm{a}}_{t}\mid\widehat{\bm{z}}_{t})\right),\end{array}\vspace{-0.5mm}$
(16)

where $D_{KL}(p||q)$ represents the KL divergence between $p$ and $q$. Since
the above semantic effectiveness metric captures the channel effect on the
transmitted semantics, the learned GFlowNet (for listener side) parameters is
robust to the channel errors (in terms of the best the listener can do).

###  IV-F Proposed ESC Reasoning Network Formulation and Solution

By leveraging the semantic metrics defined above, we can now rigorously
formulate our objective. The speaker aims to choose an optimal state
description to represent the causal reasoning at the transmit side and the
listener wants to increase semantic effectiveness at its side to achieve a
desired semantic reliability. Using the measures discussed in Section IV-D,
_semantic reliability_
(i.e.,$=p\left(E_{t}(\bm{z}_{t},{\widehat{\bm{z}}}_{t}(\bm{\eta}))<\delta\right)$)
is defined so that the listener can reliably reconstruct all the logical
formulas contained in the decoded state description. Compared to classical
reliability measures, in semantics, we can recover the actual meaning of the
transmitted messages even with a larger BER, as long as the semantic
distortion is within a limit. We formally pose our problem for speaker
($\mathcal{P}_{S}$) and listener ($\mathcal{P}_{L}$) causal reasoning as

$\displaystyle\mathcal{P}_{S}:$ $\displaystyle\hskip
14.22636pt\min\limits_{\bm{\theta}}L_{\bm{\theta}}\left(\tau_{s}\right)$ (17a)
$\displaystyle\vspace{-1mm}\mathcal{P}_{L}:$ $\displaystyle\hskip
14.22636pt\min\limits_{\bm{\psi},\bm{\eta}}C_{t}\left(\bm{z}_{t},\bm{z}_{t}(\bm{\eta})\right)+L_{\bm{\psi}}\left(\tau_{l}\right)$
(17b) $\displaystyle\hskip
14.22636pt\mbox{s.t}\,\,\,p\left(E_{t}\left({\bm{z}}_{t},{\widehat{\bm{z}}}_{t}\left(\bm{\eta}\right)\right)<\delta\right)\geq
1-\epsilon,\vspace{-12mm}$ (17c)

where $\delta,\epsilon$ can be arbitrarily small values greater than 0. The
value of $\delta$ here depends on the $\mathcal{W}$ space, and hence the NN
parameters learned for all task variations with the same syntactic space
remain intact. The loss function to optimize speaker and listener GFlowNet
parameters is expressed as

$\vspace{-1mm}\small\begin{array}[]{l}\\!L_{\bm{\theta}}(\tau)=\\!\\!\sum\limits_{s^{\prime}\in\tau\neq
s_{0}}\\!\\!\left(\\!\sum\limits_{s,a:\Pi(s,a)=s^{\prime}}\\!\\!\\!\\!F_{\bm{\theta}}(s,a)-R(s^{\prime})-\\!\\!\\!\sum\limits_{a^{\prime}\in\mathcal{A}(s^{\prime})}F_{\bm{\theta}}(s^{\prime},a^{\prime})\\!\right)^{2}.\end{array}$
(18)

$\Pi(s,a)$ represents the state transition in the DAG. $R(s^{\prime})$ can be
selected as a metric which is inversely proportional to the average number of
bits to represent any grounding (for a logical formula) which passes through
state $s^{\prime}$. Flow $F_{\bm{\theta}}(s,a)$ is parameterized by GFlowNet
NN and is computed during offline training, and it does not impact the
communication overhead. Since the listener is aware of the syntactic space, it
can train the speaker’s version of GFlowNet offline, without any communication
overhead.

Our objective function (17) is a novel rigorous formulation that captures
accurately the semantic reasoning capabilities associated with the end nodes.
To solve (17) whose intent is to achieve high semantic reliability, we use the
back propagation to fine tune GFlowNet and DNN weights. Our objective function
in (17) is convex. This can be easily proven since KL divergence is convex and
the convergence properties of GFlowNet are already proved in [13]. Hence, the
convergence to any global minimum solution is guaranteed for our solution. We
train over several mini-batches iteratively and hence the optimization of the
network parameters are done over an $\small\mathbb{E}_{e\sim
D}[\mathcal{P}_{S}]$ or $\small\mathbb{E}_{e\sim D}[\mathcal{P}_{L}]$.
Moreover, we consider our GFlowNet to be evolving which means that during the
every training instance, terminal state probability $p(s_{f}\mid G)$ gets
updated. The algorithmic details of the proposed NeSy AI based ESC system is
described in Algorithm 2. Next, we evaluate via simulations the proposed
solutions.

Algorithm 2 NeSy Approach towards Semantic Transmission - Training Phase

Given: $\mbox{At training instance}\mbox{
}t-1,\mathcal{T}_{t-1},\mathcal{\widehat{T}}_{t-1},\,\mbox{channel transition
probability}\,\,p({\bm{x}}_{t}\mid\bm{u}_{t})$.
Initialize: Adjacency matrix  ${\bm{W}}^{(0)}$ as all zeros matrix. Mask
${\bm{M}}^{(0)}$ to be constrained to have no loops. Set: $\mu=0.4$.

for minibatch b=1:B

Sample minibatch ($b$) of $N$ events from the training set, $e\sim D$.

for each event in $b$ repeat until terminal state is reached

Compute the $P(G^{(t)}\mid G^{(t-1)},\neg s_{f})$ and $P(s_{f}\mid G^{(t-1)})$

if ($P(s_{f}\mid G^{(t-1)})>\mu$)

exit the training for the event

else

Update the speaker and listener GFlowNet parameters, mask and
${\bm{W}}^{(t)}$.

Update the DNN parameters for the decoder.

end for

end forUse the learned GFlowNet and decoder weights for the data transmission
phase.

##  V Simulation Results and Analysis

In this section, we first start with a simple illustrative scenario to
demonstrate the gains from a causal reasoning based ESC system as derived in
Theorems 2 and 3, compared to a classical AI based wireless system that
directly transmits the features extracted using a convolutional neural
networks (CNN). Further, we present extensive simulation results to assess the
performance of our ESC framework and solutions.

###  V-A Illustrative Example for NeSy AI’s Potential in Wireless vs Classical
AI based Wireless

Our proposed ESC framework can support several wireless applications.
Nevertheless, for an illustrative example that is simple to understand, we
consider the events as the images observed from a camera at the speaker.
Assume that the image’s background is irrelevant, and the particular object
present (with the possible attributes as in Fig. 5(a) is of interest to the
listener. In a task $\tau_{1}$, possible contexts over which learning happens
can have the state descriptions of the form $(a,b)$, where
$a,b\in\left\\{{}^{\prime}shape^{\prime},^{\prime}color^{\prime},^{\prime}style^{\prime}\right\\}$.
Assume that $4$ unique conclusions can be derived out of $16$ possible states,
with $4$ states leading to the same conclusion. Hence, a semantics-aware
system requires just $2$ bits to communicate, which means states with the same
logical conclusions can be encoded as the same transmit signal. However, a
naive wireless system unaware of the semantics may require a maximum of $4$
bits to communicate $16$ possible state descriptions. Considering training
complexity, for an ESC system, task $\tau_{1}$ just requires $8$ communication
rounds, wherein each round, the information about a single attribute is
communicated from speaker to listener. However, a classical AI system would
require to be trained with enough data that involves possible $16$ different
objects. As the complexity of the task increases, which implies each context
involving $3$ attributes and multiple objects, the training complexity (to
achieve required reliability) of the classical AI system increases
exponentially. Fig. 5(b) compares the semantic reliability for classical and
ESC systems with the same amount of training data used, where the ESC is
superior due to its generalization capability (with fewer training data). Few
examples of the logical formulas to be evaluated by the listener with the
objects interpreted as traffic signals can be: 1) Does the observed state
correspond to a warning? 2) Does it correspond to general information about
nearby services, or 3) Does it represent speed limits? Fig. 5(c) conveys the
potential gain by using a causal reasoning based ESC system compared to using
a classical AI based system in terms of the average representation length
(bits). Here, we used a binary symmetric channel (BSC) to represent the
underlying wireless channel for communication. Having understood the
fundamental performance gains from a reasoning based system, we further look
at evaluating our algorithms.

Figure 4: Example on how logical reasoning (task with two objects present) is
performed.

(a)

(b)

(c)

Figure 5: (a) The testbed for the illustrative example is the state
description grounded in a synthetic world of objects with $4$ shapes
$\\!\times\\!$ $4$ colors $\\!\times\\!$ $4$ styles. (b) Classical AI based
system fails with task difficulty (increase in number of objects describing an
event). (c) Classical wireless system is designed based on worst case
communication context while contextual aware ESC has a dynamically changing
representation length, resulting in an efficient transmission.

###  V-B Proposed Contextual Two-Player Signaling Game Evaluation: Convergence
and Semantic Reliability

To evaluate the convergence of the Algorithm 1, we consider
$\lvert\mathcal{W}\rvert=100$ and $35$ different communication contexts. Each
context sampled uniformly random from the context set can have maximum $20$
states as valid entries and with a minimum of $5$ states per context. The cost
of transmission is $c(\bm{u}_{i})=\lceil(i/5)\rceil$. In Fig. 6(a), we look at
the convergence behavior of the proposed algorithm for different
$\lambda_{s}$. To achieve an NMSE of around $-50$ dB, as the figure suggests,
we need around $20$ communication rounds during the emergent language phase.
Fig. 6(b) shows the varying convergence behavior when the cardinality of
$\mathcal{W}$ and $\mathcal{U}$ changes. In Fig. 6(c), we present the
converged NE speaker policies resulting from our game. Clearly, the resulting
speaker policy is context-dependent and hence, the representation space gets
optimized dynamically. Also, our scheme converges three times faster than the
baseline [9].

(a)

(b)

(c)

Figure 6: (a) Convergence vs no. of communication rounds, for
$\lvert\mathcal{W}\rvert=100$ and $\lvert\mathcal{U}\rvert=5$. (b) Convergence
vs no. of communication rounds, for
$\lvert\mathcal{W}\rvert=200,\lvert\mathcal{U}\rvert=20$. (c) Speaker transmit
policy for different contexts. Proposed scheme has its
$\lvert\mathcal{U}\rvert$ varying w.r.t the communication context (each curve,
with distinct color, show $\pi_{s}$ given a different $\bm{z}$).

Fig. 7(a) shows the task agnostic behavior of the emergent language
constructed. Different tasks represent variations in the $\mathcal{W}$ that
capture the event state descriptions. Task $1$ needs $30$ rounds to converge,
while task $4$ needs only $10$ rounds. Hence, as time progresses the emergent
language duration decreases, as illustrated in Fig. 2(a) and a task agnostic
language emerges between the nodes. In Fig. 7(b), we evaluate the semantic
reliability using the proposed emergent language during data transmission
phase. Our algorithm performs $75\%$ better than [9] in terms of semantic
reliability (for similar iterations). Fig. 7(c) shows the extracted
semantics/s/Hz vs the decreasing $\lvert\mathcal{U}\rvert$ (for a fixed
$\lvert\mathcal{W}\rvert$) at the listener using the metric defined in (5).
The semantic rate decreases as $\lvert\mathcal{U}\rvert$ decreases, but the
point ($\lvert\mathcal{U}\rvert$) at which the semantic rate starts a downward
slope depends on the semantic threshold. This clearly shows that with
increasing semantic similarity between causal states, the extracted semantic
rate will be higher compared to classical systems that do not exploit semantic
awareness with respect to the listener and end up transmitting more
information.

(a)

(b)

(c)

Figure 7: (a) Emergent language convergence for variations in tasks across
time. This shows the decreasing language creation overhead. (b) Semantic
reliability using the emergent language created. (c) Received semantics for
different semantic similarity threshold (or semntic spaces), with
$\lvert\mathcal{W}\rvert=256$.

###  V-C Performance Evaluation of the Proposed ESC with Causal Reasoning

We followed the experimental setup of [33] for the data generation. In each
experiment, a random graph $G$ was generated from the Erdös-Rényi (ER) random
graph model. The graph contained $d$ edges on average; the probability of
creating an edge between two nodes was scaled accordingly. Given $G$, we
uniformly assigned random edge weights to obtain a weight matrix ${\bm{W}}$.
Edge weight $w_{ij}$ denotes the grounding for the corresponding relation
between edges $i$ and $j$ in the graph. Given ${\bm{W}}$, we sampled
${\bm{X}}={\bm{W}}^{T}{\bm{X}}+\bm{z}$, where $\bm{z}$ is a Gaussian noise,
with zero mean and variance $=0.01$. The elements of ${\bm{W}}$ follows
$\mathcal{N}(0,1)$. Once the full Bayesian Network is known, we used ancestral
sampling to generate $100$ data points to fill our data set $D$. The dataset
generated here is quite realistic in that it can correspond to the various
device measurements corresponding to an IoT environment, aggregated at a
central device with a radio transceiver (speaker). Instead of transmitting the
entire piece of data, the speaker computes just the causal reasoning that gets
transmitted across the network, saving significant bits. This generated data
is fed to GFlowNet, which learns the causal structure forming the data
${\bm{X}}$. The simulations for the AI model training are all performed in
google colab pro version that used an NVIDIA TESLA P100 GPU with a 16GB RAM.

The training phase is performed using $25K$ different observations, and 100
mini-batches are considered. The GFlowNet weights are learned using this
training phase. In the actual transmission phase (involving $10,000$ separate
test data samples), the learned model is considered along with the emergent
language in Algorithm 1 used for encoder/decoder. From an ESC perspective,
measurements ${\bm{X}}$ represent the data received from $N$ ($=5$ here)
different devices. At the listener, based on the quantized levels ($4$
possible levels considered) of the measurement vector decoded, different
actions are taken. For simplicity, we skip the attribute extraction step here.
The learned graphical structure is represented by the adjacency matrix
${\bm{W}}$. Further, the encoded representation $\bm{u}_{t}$ is sent across a
BSC, with crossover probability $p$.

Fig. 9 shows that an ESC system based on NeSy AI can be more efficient (in
terms of amount of bits) to convey the same amount of semantic information
compared to the conventional communication system. Specifically, we analyze
the number of bits transmitted to get a particular probability of error (for
$1,000$ events). The amount of bits transmitted are reduced by a factor of
$1,000$ for the semantic system compared to classical system (without
reasoning part) which explains the significance of our proposed approach.
Moreover, compared to state-of-the-art algorithms that do not consider causal
reasoning, the proposed NeSy approach is more robust to bit errors. Our
approach can still recover larger semantic information even with a probability
of error of $3\%$. In Fig. 9, the semantic reliability of NeSy AI based ESC
system shows significant improvements compared to state of the art methods.
The evaluation is performed based on the semantic error probability (measured
as $1-$ semantic reliability) vs $p$ for the BSC. The result shows that
proposed ESC scheme has almost $95\%$ reduction in semantic error probability
at $p=0.1$ compared to other methods, thanks to the causality and semantic
awareness based encoding achieved using the game. We also show that the
performance of the proposed NeSy AI approach in which the speaker and listener
independently optimize the GFlowNet is very close to that with joint
optimization of the GFlowNet parameters for speaker and listener. A joint
optimization would mean that the listener would have communicated complete
information about its actions and logical conclusions to the speaker, hence
not preferred due to more overhead during training. As $p$ becomes closer to
$0.5$, the semantic error probability converges to a higher value for all
schemes since half of the bits get flipped at the listener.

Figure 8: Transmission Efficiency for Proposed ESC vs State of the Art.

Figure 9: Semantic Reliability for Proposed ESC vs State of the Art.

##  VI Conclusion

In this paper, we have presented a new vision of SC systems entitled ESC that
relies upon NeSy AI as a machinery to enable causal reasoning that allows it
to be task agnostic over time with less training data. We have formulated a
two-player contextual signaling game to learn an optimal representation space
for transmission and extracting the semantic state description at the
listener, which is termed the emergent language. The optimized local NE
resulting from the AM updates ensures that the listener can recover the
maximum of the relevant semantics with minimal transmission from the speaker.
The causal reasoning component at the speaker and the symbolic logical
reasoning at the listener are implemented using the recently emerged causal
reasoning AI algorithm called GFlowNet. We have shown analytically that, by
exploiting contextual information in emergent language, the average bit length
for the semantic state description gets reduced compared to the classical
communication system. Simulation results have demonstrated superiority of our
proposed ESC in terms of improving the communication efficiency (minimal
transmission) and reliability compared to classical communication and state of
the art SC systems.

##  Appendix A Category Theory Preliminaries

######  Definition 7 (Category).

A category $\mathcal{L}$ can be represented by: (a) A collection of objects,
$Ob(\mathcal{L})$; and (b) a collection of morphisms, $\mathcal{L}(c,d)$ (also
denoted as $\textrm{hom}(c,d)$), which represents the possible relations
(represented by arrows in a graph) from one object to another. (c) For every
object $c$, we define the identity morphism, $id_{c}=\mathcal{L}(c,c)=I$. (d)
For every three objects $c,d,e\in Ob(\mathcal{L})$ and morphisms
$f\in\mathcal{L}(c,d)$ and $g\in\mathcal{L}(d,e)$, one specifies a morphism
$f\circ g\in\mathcal{L}(c,e)$, called the composite of $f$ and $g$. A
$\mathcal{V}-$enriched category $\mathcal{L}$ can be defined as follows: Let
$\mathcal{V}$ be a symmetric monoidal preorder (see [24] for more details on
preorders), $(\mathcal{V},\leq,I,\circ)$. A $\mathcal{V}-$enriched category,
apart from the properties above for a category satisfies the following too.
For every object $c\in Ob(\mathcal{L})$, it satisfies $I\leq\mathcal{C}(c,c)$,
and for every three objects $c,d,e\in Ob(\mathcal{L})$, it obeys
$\mathcal{L}(c,d)\circ\mathcal{L}(d,e)\leq\mathcal{L}(c,e)$.

######  Definition 8 (Functor).

A functor $F:\mathcal{L}\rightarrow\widehat{\mathcal{L}}$ takes $c\in
Ob(\mathcal{L})$ to $F(c)\in Ob(\widehat{\mathcal{L}})$ for all $c\in
Ob(\mathcal{L})$.

######  Definition 9.

[Representable Copresheaf] Let $\mathcal{L}$ be a $[0,1]$ enriched category.
For every object $x$, the function $h^{x}=\mathcal{L}(x,-)$ is a $[0,1]$
functor and it represents the object $x$, through its possible morphisms.

##  Appendix B Proof of Lemma 1

It is straightforward to show that $\mathcal{L}$ is a monoidal preorder, where
the order is imposed by ${\bm{x}}\leq{\bm{y}}$, whenever there is a morphism
from ${\bm{x}}$ to ${\bm{y}}$. For each object ${\bm{x}}$ in $\mathcal{L}$,
the representable copresheaf $h^{\bm{x}}=hom({\bm{x}},-)$ is given by the
following conditional probability:.

$\vspace{-2mm}\begin{array}[]{l}h^{\bm{x}}({\bm{y}})=\begin{cases}\pi({\bm{y}}\mid
x,{\bm{c}})\,\,\,&if\,\,\,{\bm{x}}\leq{\bm{y}}\\\
0,&\text{otherwise}\end{cases}\end{array}\vspace{-1mm}$ (19)

Assignment ${\bm{x}}\rightarrow h^{\bm{x}}$ can be shown to be an enriched
functor as follows. An enriched functor
$f=h^{{\bm{x}}}:\mathcal{L}\rightarrow\widehat{\mathcal{L}}$ satisfies the
property that
$\mathcal{L}({\bm{x}},{\bm{y}})\leq\widehat{\mathcal{L}}(f({\bm{x}}),f({\bm{y}}))$.
Here, we define $\widehat{\mathcal{L}}$ to be the category which contains all
the enriched functors. To show this, we need to first define the function
$\widehat{\mathcal{L}}(f({\bm{x}}),f({\bm{y}}))$.

$\vspace{-3mm}\widehat{\mathcal{L}}(f({\bm{x}}),f({\bm{y}}))=\begin{cases}1,\,\,\,&if\,\,{\bm{x}}\leq{\bm{y}}\\\
\frac{f({\bm{x}})}{f({\bm{y}})},\,\,\,&if\,\,{\bm{x}}>{\bm{y}}\end{cases}$
(20)

For ${\bm{x}}\leq{\bm{y}}$, $\mathcal{L}({\bm{x}},{\bm{y}})\leq
1=\widehat{\mathcal{L}}(f({\bm{x}}),f({\bm{y}}))$. In the case, when
${\bm{x}}>{\bm{y}}$,
$\mathcal{L}({\bm{x}},{\bm{y}})=0\leq\frac{f({\bm{x}})}{f({\bm{y}})},$ with
$f({\bm{x}})\leq f({\bm{y}})$. Hence, $f=h^{{\bm{x}}}$ is an enriched functor.
Hence, all the representable copresheaves
$h^{\bm{x}},\forall{\bm{x}}\in\mathcal{L}$ within the context ${\bm{c}}$ forms
a [0,1] enriched category which we define as $\widehat{\mathcal{L}}$
(representing all possible worlds that follows from $\mathcal{L}$). We denote
the codomain of $h^{\bm{x}}$ as $H^{\bm{x}}$. Further, for completion, we can
define the hom object between two representable copresheaves as follows,
$\widehat{\mathcal{L}}(h^{\bm{x}},h^{\bm{y}})=\textstyle\sum\limits_{{\bm{d}}\in
H^{\bm{y}}}h^{\bm{x}}({\bm{d}}).$ For any three objects
${\bm{x}},{\bm{y}},\bm{z}$, it satisfies
$\widehat{\mathcal{L}}(h^{{\bm{x}}},h^{\bm{z}})\\!=\\!\\!\textstyle\sum\limits_{{\bm{d}}_{1}\in
H^{{\bm{x}}}}\textstyle\sum\limits_{{\bm{d}}_{2}\in
H^{\bm{z}}}\pi({\bm{d}}_{1}\mid{\bm{x}})\pi({\bm{d}}_{2}\mid{\bm{y}})\\!=\\!\widehat{\mathcal{L}}(h^{{\bm{x}}},h^{{\bm{y}}})\widehat{\mathcal{L}}(h^{{\bm{y}}},h^{\bm{z}}).$
Hence, associative property of enriched categories is satisfied.
$\widehat{\mathcal{L}}(h^{{\bm{x}}},h^{{\bm{x}}})\\!=\\!1$ satisfies the
identity morphism. Thus, $\widehat{\mathcal{L}}$ is a $[0,1]$-enriched
category of representable copresheaves of the objects in $\mathcal{L}$.

##  Appendix C Proof of Proposition 1

Given a listener policy $\pi_{l,t}$, we optimize the speaker policy by
maximizing the Lagrangian.

$\vspace{-0mm}\begin{array}[]{l}\hskip
39.83385pt\pi_{s,t}^{*}=\,\arg\max\limits_{\pi_{s,t}}F_{s}(\pi_{s,t},\pi_{l,t}),\,\,\mbox{where},\\\
\vspace{-2mm}F_{s}(\pi_{s,t},\pi_{l,t})=\,-\mathbb{E}_{\bm{u}_{t}}\left[S_{s}(\bm{z}_{t};\bm{u}_{t}\mid\pi_{s,t},{\bm{c}},[\bm{z}_{t-1}])\right]-\lambda_{s}\mathbb{E}[V(\pi_{s,t},\pi_{l,t})]+\sum\limits_{\bm{z}_{t}}\alpha_{\bm{z}_{t}}\left[\sum\limits_{\bm{u}_{t}}\pi(\bm{u}_{t}\mid\bm{z}_{t})\right].\end{array}\vspace{-1mm}$
(21)

It can be validated that $F_{s}(\pi_{s,t},\lambda_{s})$ is convex in
$\pi_{s,t}$ (follows from showing that term of the form $x\log\frac{x}{a}$ in
(5) is convex), hence the global maximum is obtained at the point where
derivative of $F_{s}(\pi_{s,t},\pi_{l,t})$ is zero. $\lambda_{s}$ represents
the Lagrange multiplier for the inequality constraint associated with $V$.
$\alpha_{\bm{z}_{t}}$ represents the Lagrange multiplier for the normalization
of the distribution $\pi(\bm{u}_{t}\mid\bm{z}_{t})$. $\bm{\alpha}_{s}$
represents the vector of all $\alpha_{z_{t}}$. Further, taking derivative
w.r.t $\pi_{s,t}$, we obtain

$\begin{array}[]{l}-\pi(\bm{z}_{t})S_{s}(\bm{z}_{t})\left(\log\pi(\bm{u}_{t}\mid\bm{z}_{t})-\log\pi(\bm{u}_{t})+1\right)-\lambda_{s}\left(c(\bm{u}_{t})-\log\pi_{l,t}\right)+\alpha_{\bm{z}_{t}}=0,\implies\\\
\pi(\bm{u}_{t}\mid\bm{z}_{t})=\pi(\bm{u}_{t})\exp\left(\frac{-1}{S_{s}(\bm{z}_{t}\mid[\bm{z}_{t-1}])\pi(\bm{z}_{t}\mid{\bm{c}})}(\lambda_{s}(c(\bm{u}_{t})-\log\pi_{l,t})-\alpha_{\bm{z}_{t}})-1\right).\end{array}$
(22)

Similarly, for a fixed $\pi_{s,t}$, we can obtain $\pi_{l,t}$ by maximizing
the Lagrangian.

$\begin{array}[]{l}\hskip
39.83385pt\pi_{l,t}^{*}=\arg\max_{\pi_{l,t}}F_{l}(\pi_{l,t},\pi_{s,t}),\\\
F_{l}(\pi_{l,t}^{*},\pi_{s,t})=\sum\limits_{\bm{u}_{t}}\underbrace{\pi\left(\bm{u}_{t}\mid\bm{z}_{t}\right)\left[\sum\limits_{\widehat{\bm{z}}_{t}}\pi(\widehat{\bm{z}}_{t}\mid\bm{u}_{t})\log\frac{\pi(\widehat{\bm{z}}_{t}\mid\bm{u}_{t})}{\pi(\widehat{\bm{z}}_{t})}Z_{\widehat{z}_{t}z_{t}}\right]S_{s}({\bm{z}}_{t}\mid{\bm{c}},[\bm{z}_{t-1}])}_{S_{l}(\widehat{\bm{z}}_{t};\bm{u}_{t}\mid\pi_{s,t},\pi_{l,t},[\widehat{\bm{z}}_{t-1}])}-\sum\limits_{\bm{u}_{t}}\alpha_{\bm{u}_{t}}\sum\limits_{\bm{z}_{t}}\pi_{l,t}.\vspace{-2mm}\end{array}\vspace{-1mm}$
(23)

(23) is non-concave since it is a summation of a convex and a concave
function. Since a linear function is simultaneously convex and concave,
consider the first order Taylor series expansion of $\pi_{l,t}\log\pi_{l,t}$,
using which we can rewrite
$S_{l}(\widehat{\bm{z}}_{t};\bm{u}_{t}\mid\pi_{s,t},\pi_{l,t},[\widehat{\bm{z}}_{t-1}])$
as

$\begin{array}[]{l}\widehat{S}_{l}\left(\widehat{\bm{z}}_{t};\bm{u}_{t}\mid\pi_{s,t},\pi_{l,t},[\widehat{\bm{z}}_{t-1}]\right)\\!=\\!\pi\left(\bm{u}_{t}\mid\bm{z}_{t}\right)S_{s}({\bm{z}}_{t}\mid{\bm{c}},[\bm{z}_{t-1}])\sum\limits_{\widehat{\bm{z}}_{t},\widehat{{\bm{c}}}}\pi_{l,t}\left[1+\log\pi_{l,t-1}-\log\pi(\widehat{\bm{z}}_{t})\right]Z_{\widehat{z}_{t}z_{t}}+\mbox{constant}.\end{array}\vspace{-3mm}$

Using the resulting approximate function obtained above which can be shown as
a lower bound to the original
$S_{l}(\widehat{\bm{z}}_{t};\bm{u}_{t}\mid\pi_{s,t},\pi_{l,t},[\widehat{\bm{z}}_{t-1}])$,
we can solve the approximate Lagrangian function.

$\begin{array}[]{l}\pi_{l,t}^{*}=\arg\max\limits_{\pi_{l,t}}{\widehat{F}}_{l}(\pi_{l,t},\pi_{s,t}),\\\
{\widehat{F}}_{l}(\pi_{l,t},\pi_{s,t})=\sum\limits_{\bm{u}_{t}}\widehat{S}_{l}\left(\widehat{\bm{z}}_{t};\bm{u}_{t}\mid\pi_{s,t},\pi_{l,t},[\widehat{\bm{z}}_{t-1}]\right)-\sum\limits_{\bm{u}_{t}}\alpha_{\bm{u}_{t}}\sum\limits_{\bm{z}_{t}}\pi(\widehat{\bm{z}}_{t}\mid\bm{u}_{t}).\vspace{-2mm}\end{array}\vspace{-2mm}$
(24)

We can now derive (25) w.r.t $\pi_{l,t}$

$\begin{array}[]{l}\pi\left(\bm{u}_{t}\mid\bm{z}_{t}\right)S_{s}({\bm{z}}_{t}\mid{\bm{c}},[\bm{z}_{t-1}])Z_{\widehat{z}_{t}z_{t}}\left(\left(1+\log\pi_{l,t-1}\right)-\log\pi(\widehat{\bm{z}}_{t})-\frac{\pi_{l,t}}{\pi(\widehat{\bm{z}}_{t})}\pi(\bm{u}_{t})\right)=\alpha_{\bm{u}_{t}}\implies\\\
\pi_{l,t}\propto\frac{1}{\pi(\bm{u}_{t})}\exp\left(\frac{-\alpha_{\bm{u}_{t}}}{\pi\left(\bm{u}_{t}\mid\bm{z}_{t}\right)Z_{\widehat{z}_{t}z_{t}}S_{s}({\bm{z}}_{t}\mid{\bm{c}},[\bm{z}_{t-1}])}+\log\pi_{l,t-1}\right)\end{array}$
(25)

To arrive at $\pi_{l,t}$ above, we used the approximation
$\pi(\widehat{\bm{z}}_{t})\approx\pi_{l,t}\pi(\bm{u}_{t})$, since the
probabilities are expected to be higher near the peak of $\pi_{l,t}$ and zero
for all other $\pi(\widehat{\bm{z}}_{t}\mid\bm{u}^{\prime}_{t})$, with
$\bm{u}^{\prime}_{t}\neq\bm{u}_{t}$. This finalizes the proof.

##  Appendix D Proof of Theorem 1

We consider that the cost of transmission is negligible, $c(\bm{u})\\!=\\!0$
and assume that the normalization constraints are satisfied with equality,
hence $\bm{\alpha}_{s}\\!=\\!0$. By using the inequality, $\sum_{x}p(x)\log
q(x)\\!\leq\\!\sum_{x}p(x)\log p(x)$ (non-negativity of KL divergence), we can
write (where $p,q$ are $\pi_{s},\pi_{l}$, respectively)
$F_{s}(\pi_{l},\pi_{s})\geq\mathbb{E}\left[S_{s}(\bm{z};\bm{u}\mid\pi_{s},{\bm{c}})\right]-\lambda
E\left[\log\pi(\bm{z}\mid\bm{u})\right].$ Substituting for
$\pi(\bm{z}\mid\bm{u})$ using Bayes rule, we get

$\displaystyle\mathbb{E}\left[S_{s}(\bm{z};\bm{u}\mid\pi_{s},{\bm{c}})\right]+\lambda_{s}\mathbb{E}\left[V(\pi_{s},\pi_{l})\right]$
$\displaystyle\geq\mathbb{E}\left[S_{s}(\bm{z};\bm{u}\mid\pi_{s},{\bm{c}})\right]-\lambda_{s}\mathbb{E}\left[\log\frac{\pi(\bm{u}\mid\bm{z})\pi(\bm{z}\mid{\bm{c}})\pi({\bm{c}})}{\pi(\bm{u})}\right]$
(26)
$\displaystyle=(1-\lambda_{s})\mathbb{E}\left[S_{s}(\bm{z};\bm{u}\mid\pi_{s},{\bm{c}})\right]+\lambda_{s}H_{s}(\bm{z},{\bm{c}}),$

where $H_{s}(\bm{z})$ is entropy of $\bm{z}$. For $\lambda_{s}\\!\in\\![0,1]$,
the minimum is attained at
$\mathbb{E}\left[S_{s}(\bm{z};\bm{u}\\!\mid\\!\pi_{s},{\bm{c}})\right]\\!=\\!0$
and hence,
$\mathbb{E}\left[S_{s}(\bm{z};\bm{u}\\!\mid\\!\pi_{s},{\bm{c}})\right]+\lambda_{s}\mathbb{E}[V(\pi_{s},\pi_{l})]\geq\lambda_{s}H_{s}(\bm{z},{\bm{c}})$.
It can be shown that the zero for
$\mathbb{E}\left[S_{s}(\bm{z};\bm{u}\\!\mid\\!\pi_{s},{\bm{c}})\right]$ can be
achieved when $\pi_{s}(\bm{u}\mid\bm{z})\\!=\\!1/K$,
$\pi_{l}(\bm{z}\mid\bm{u})\\!=\\!\pi(\bm{z})$, and $H_{s}(\bm{u})\\!=\\!\log
K$, where $\mathcal{U}=K$. This implies that, the minimum can be achieved with
a non-informative speaker when the constraint on the sender utility is weak.
When $\lambda_{s}>1$, the $F_{s}(\pi_{l},\pi_{s})$ is minimized when
$\mathbb{E}\left[S_{s}(\bm{z};\bm{u}\mid\pi_{s},{\bm{c}})\right]$ is
maximized. $\mathbb{E}\left[S_{s}(\bm{z};\bm{u}\mid\pi_{s},{\bm{c}})\right]$
is maximum when there is a bijection that preserves the semantics, that is
$\psi:\mathcal{W}\rightarrow\mathcal{U}$ such that
$\pi_{s}(\bm{u}\mid\bm{z},{\bm{c}})\\!=\\!\delta_{\bm{u},\psi(s)},\pi_{l}(\bm{z}\mid\bm{u},{\bm{c}})\\!=\\!\delta_{\bm{u},\psi(s)}$.
In this case, the listener will be able to map accurately the received signal
(assuming error-free communication) to the speaker intended semantics and thus
extracting the maximum semantic information.

Next, we can consider the analysis for the partial pooling case, for which the
speaker distribution $\pi_{s,t}$ is surjective (multiple states can correspond
to same $\bm{u}$) and not a bijective mapping. In this scenario, we first look
at how the listener side extracts the semantic state. For simplicity of
analysis, we assume that communication is error-free, which implies
$\widehat{\bm{u}}=\bm{u}$. We can write
$F_{l}(\pi_{l},\pi_{s})\leq\mathbb{E}_{\bm{u}_{t}}\left[S_{l}(\bm{z};\bm{u}\mid\pi_{s},\pi_{l})\right]$,
from which it is clear that, the maximum is attained when there is a bijective
mapping between $\bm{z}$ and $\bm{u}$, that contradicts our assumption for
partial pooling case. Hence, the expression

$\vspace{-2mm}\pi_{l}^{*}=\arg\max_{\pi_{l}}S_{l}(\widehat{\bm{z}};\bm{u}\mid\bm{z},\pi_{l}),\vspace{-2mm}$
(27)

is maximized only when the overlap between the copresheaves $h^{\bm{z}}$ and
$h^{\widehat{\bm{z}}}$ are maximized. Further, defining a semantic distance
metric as
$\left\lVert\bm{z}-\widehat{\bm{z}}\right\rVert_{S}=\sum\limits_{\bm{Y}\in
H^{\bm{z}}-(H^{\bm{z}}\cap H^{\widehat{\bm{z}}})}S_{s}(\bm{Y};\bm{z})$.
Intuitively, it can be interpreted as a weighted ($S_{s}(\bm{Y};\bm{z})$ are
the weights) Hamming distance (HD) between the copresheaves represented by
$H^{\bm{z}}$ and $H^{\widehat{\bm{z}}}$. Hence, at equilibrium, the listener
chooses the expression $\widehat{\bm{z}}$ that is semantically closer to
$\bm{z}$ or in other words, according to the optimization (equivalent to
(27)),
$\widehat{\bm{z}}^{*}=\arg\min_{\widehat{\bm{z}}}\left\lVert\bm{z}-\widehat{\bm{z}}\right\rVert_{S}.$
Given that the listener chooses HD-based decoding, how should the speaker
select the encoded signal to maximize the received semantic information (or
minimize the HD)? The optimal encoded signal can be understood using a similar
analysis as in [34]. The speaker can partition $\mathcal{W}$ into
$\lvert\mathcal{U}\rvert$ of them, with each denoted $\mathcal{W}_{k}$ and
every state in $\mathcal{W}_{k}$ mapped to transmit signal $\bm{u}_{k}$. Let
the listener’s decoded state be $\widehat{\bm{z}}_{k}$ corresponding to
$\bm{u}_{k}$. The speaker wants the decoded expression to be as close to the
transmitted one as possible. Hence, the speaker will transmit $\bm{u}_{k}$
whenever the decoded state $\widehat{\bm{z}}_{k}$ is semantically closest to
all the states in $\mathcal{W}_{k}$. Such a partition of the syntax space is
called a _Voronoi tessellation_ of the space. This concludes the proof.

##  Appendix E Proof of Theorem 2

Assume that the length of each word represented by the semantics conveyed by
$\bm{u}_{i}\in\mathcal{U}$ is $l_{i}$. Also, consider that the listener is
able to disambiguate the ambiguous signaling strategy from the sender by
inferring the context. Then the average semantic representation length for the
vocabulary $\mathcal{U}$ can be lower bounded as (using the Kraft’s inequality
[35])
$\sum\limits_{\bm{u}_{i}\in\mathcal{U}}\pi(\bm{u}_{i})l_{i}\geq\sum\limits_{{\bm{c}}\in\mathcal{C}}\pi({\bm{c}})H(\bm{z}_{i}\mid{\bm{c}}).$
Moreover, we can upper bound the codeword length for the semantic
representation as follows.

$\vspace{-2mm}\begin{array}[]{l}\sum\limits_{\bm{u}_{i}\in\mathcal{U}}\pi(\bm{u}_{i})l_{i}\leq-\sum\limits_{{\bm{c}}\in\mathcal{C}}\pi({\bm{c}})\sum\limits_{\bm{z}_{i}}\pi(\bm{z}_{i}\mid{\bm{c}})\lceil\log\pi(\bm{z}_{i}\mid{\bm{c}})\rceil\end{array}\vspace{-1mm}$
(28)

For a causal reasoning system, where the contextual information is not taken
into account
$\\!\\!\sum\limits_{\bm{u}_{i}\in\mathcal{U}}\pi(\bm{u}_{i})l_{i}\geq
H(\bm{z}_{i})$, and the upperbound is
$\sum\limits_{\bm{u}_{i}\in\mathcal{U}}\pi(\bm{u}_{i})l_{i}\\!\leq\\!\max\limits_{{\bm{c}}\in\mathcal{C}}\sum\limits_{\bm{z}_{i}}\\!\pi(\bm{z}_{i}\\!\mid\\!{\bm{c}})\lceil\log\pi(\bm{z}_{i}\\!\mid\\!{\bm{c}})\rceil.$
Further, considering a classical system without causal reasoning component and
that directly encodes all the entities, the bounds are

$\displaystyle\sum\limits_{\bm{u}_{i}\in\mathcal{U}}\pi(\bm{u}_{i})l_{i}\geq
H({\bm{s}}_{i}),\,\,\mbox{where,}\,H({\bm{s}}_{i})>H(\bm{z}_{i}),\,\,\mbox{and}$
(29)
$\displaystyle\sum\limits_{\bm{u}_{i}\in\mathcal{U}}\pi(\bm{u}_{i})l_{i}\leq\max\limits_{{\bm{c}}\in\mathcal{C}}\sum\limits_{\bm{z}_{i}}\pi(\bm{z}_{i}\mid{\bm{c}})\left[\sum\limits_{{\bm{s}}_{i}\in\bm{z}_{i}}\lceil\log\pi({\bm{s}}_{i}\mid{\bm{c}})\rceil\right].$
(30)

The upper bound (30) follows from the reasoning that the classical system
should be designed considering the worst-case scenario such that the listener
can decode properly with an arbitrarily low probability of error. This results
in a higher upper bound for classical system compared to ESC. Given that the
conditional entropy obeys the relation $H(\bm{z}_{i}\mid{\bm{c}})\leq
H(\bm{z}_{i})$, the lower bound for semantic representation gets reduced when
we take into account the communication context, compared to a classical
communication system.

##  Appendix F Proof of Theorem 3

In our envisioned ESC model, we have the following set of inequality, that
mimics the data processing inequality in information theory [35],
$S_{s}(\bm{\Phi};\bm{z})\geq S_{s}(\bm{\Phi};\bm{u})\geq
S_{s}(\bm{\Phi};\widehat{\bm{z}})$. Here $\bm{\Phi}$ (logical formulas)
represents the semantic category space represented by $\bm{z}$. This follows
from the Markov Chain
$\bm{\Phi}\rightarrow\bm{z}\rightarrow\bm{u}\rightarrow\widehat{\bm{u}}\rightarrow\widehat{\bm{z}}\rightarrow\widehat{\bm{\Phi}}$.
In a classical system, the state description represented as $\bm{z}_{c}$ does
not consider the hidden semantics and may contain irrelevant information. In
such a case, where the semantic category space is excluded, the corresponding
Markov Chain would be
$\bm{z}_{c}\rightarrow\bm{u}\rightarrow\widehat{\bm{u}}\rightarrow\widehat{\bm{z}}_{c}$.
Moreover, $H(\bm{z}_{c}\mid\widehat{\bm{z}}_{c})\geq
H(\bm{z}_{c}\mid\bm{u})\geq H(\bm{z}\mid\bm{u})$, assuming the same
representation space for ESC and classical systems. Hence, we have the
following Fano’s inequality [35], for a classical system,
$P_{e}=p(\widehat{\bm{z}}_{c}\neq\bm{z}_{c})\geq\frac{H(\widehat{\bm{z}}_{c}\mid\bm{z}_{c})-1}{\log\lvert\mathcal{W}\rvert}$.
Next, we look at how the semantic probability error measure differs from the
classical error quantity above. To define semantic error probability, we first
define the random variable ${\bm{e}}$ which denotes the error between the
semantics represented by $\bm{z}$ and $\widehat{\bm{z}}$. ${\bm{e}}$ denotes
the set $H^{\bm{z}}-(H^{\bm{z}}\cap H^{\widehat{\bm{z}}})$, that represents
the semantic space that cannot be represented by $\widehat{\bm{z}}$. Moreover,
consider
$H({\bm{e}},\bm{\Phi}\mid\widehat{\bm{z}})=H(\bm{\Phi}\mid\widehat{\bm{z}})+H({\bm{e}}\mid\bm{\Phi},\widehat{\bm{z}})=H(\bm{\Phi}\mid\widehat{\bm{z}})=H(\bm{z}\mid\widehat{\bm{z}})$.
Further, we proceed following similar derivation as for Fano’s inequality.
Rewriting,
$H({\bm{e}},\bm{\Phi}\mid\widehat{\bm{z}})=H({\bm{e}}\mid\widehat{\bm{z}})+H(\bm{\Phi}\mid{\bm{e}},\widehat{\bm{z}})$.
With probability $p(H^{\bm{z}}=H^{\widehat{\bm{z}}})$, we have
$H(\bm{\Phi}\mid{\bm{e}},\widehat{\bm{z}})=0$. With probability
$S_{e}=1-p(H^{\bm{z}}=H^{\widehat{\bm{z}}})$, we have
$H(\bm{\Phi}\mid{\bm{e}},\widehat{\bm{z}})=H(\bm{z}\mid{\bm{e}},\widehat{\bm{z}})\leq
H(\bm{z})\leq\log\lvert\Omega\rvert$. Further, we are able to conclude as

$\vspace{-2.5mm}\begin{array}[]{l}H(\bm{z}\mid\widehat{\bm{z}})\leq
H({\bm{e}}\mid\widehat{\bm{z}})+S_{e}\log\lvert\Omega\rvert\implies
S_{e}\geq\frac{H(\bm{z}\mid\widehat{\bm{z}})-H({\bm{e}}\mid\widehat{\bm{z}})}{\log\lvert\mathcal{W}\rvert},\end{array}\vspace{-1mm}$
(31)

where $H({\bm{e}})\geq 1$, with equal to happens only when the intersection of
the semantic space represented by $\bm{z}$ and $\widehat{\bm{z}}$ is a null
set. Moreover, $H(\bm{z}_{c}\mid\widehat{\bm{z}}_{c})\geq
H(\bm{z}\mid\widehat{\bm{z}})$. Combining these two, we can conclude that even
with some bit errors in the physical transmission, the semantics represented
by $\widehat{\bm{z}}$ can be similar (with its semantic space having
significant intersection to $H^{\bm{z}}$).

## References

  * [1] C. K. Thomas and W. Saad,  “Neuro-Symbolic Artificial Intelligence (AI) for Intent based Semantic Communication,”  in Proceedings of IEEE Global Communications Conference (GLOBECOM), Dec 2022.
  * [2] C. E. Shannon,  “A Mathematical Theory of Communication,”  in The Bell System Technical Journal, vol. 27, no. 3, pp. 379–423, Jul. 1948.
  * [3] E. C. Strinati and S. Barbarossa,  “6G Networks: Beyond Shannon Towards Semantic and Goal-Oriented Communications,”  Computer Networks, Elsevier, vol. 190, May 2021.
  * [4] M. Kountouris and N. Pappas,  “Semantics-empowered communication for networked intelligent systems,”  IEEE Communications Magazine, vol. 59, no. 6, pp. 96–102, Jun. 202\.
  * [5] P. Popovski, O. Simeone, F. Boccardi, D. Gündüz, and O. Sahin,  “Semantic-Effectiveness Filtering and Control for Post-5G Wireless Connectivity ,”  Journal of the Indian Institute of Science, vol. 100, no. 2, pp. 435–443, Apr. 2020.
  * [6] H. Xie, Z. Qin, G. Y. Li, and B-H. Juang,  “Deep Learning Enabled Semantic Communication Systems,”  IEEE Transactions on Signal Processing, vol. 69, pp. 2663–2675, Apr. 2021.
  * [7] S. Seo, J. Park, S-W Ko, J. Choi, M. Bennis, and S-L Kim,  “Towards Semantic Communication Protocols: A Probabilistic Logic Perspective,”  arXiv:2207.03920v1, Jul. 2022.
  * [8] J. Liu, W. Zhang, and H. V. Poor,  “A Rate-Distortion Framework for Characterizing Semantic Information,”  in Proceedings of IEEE International Symposium on Information Theory (ISIT), Grenoble, France, Jul. 2021.
  * [9] H. Seo, J. Park, M. Bennis, and M. Debbah,  “Semantics-Native Communication with Contextual Reasoning,”  arXiv preprint arXiv:2108.05681, Aug. 2021.
  * [10] M. K. Farshbafan, W. Saad, and M. Debbah,  “Curriculum Learning for Goal-Oriented Semantic Communications with a Common Language,”  arXiv preprint arXiv:2111.08051, Feb. 2022.
  * [11] M. K. Farshbafan, W. Saad, and M. Debbah,  “Common Language for Goal-Oriented Semantic Communications: A Curriculum Learning Framework,”  in Proceedings of IEEE International Conference on Communications (ICC), May 2022.
  * [12] R. Carnap and Y. Bar-Hillel,  “An Outline of a Theory of Semantic Information,”  Technical Report No. 247, Oct. 1952.
  * [13] E. Bengio, M. Jain, M. Korablyov, D. Precup, and Y. Bengio.,  “Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation,”  in Neural Information Processing Systems, Dec. 2021.
  * [14] J. Wei, X. Wang, D. Schuurmans, M. Bosma, E. Chi, Q. Le, and D. Zhou,  “Chain of Thought Prompting Elicits Reasoning in Large Language Models ,”  arXiv preprint arXiv:2201.11903, Oct. 2022.
  * [15] A. A. Garcez and L. C. Lamb,  “Neurosymbolic AI: the 3rd Wave,”  arXiv preprint arXiv:2012.05876, Dec. 2020.
  * [16] I. Higgins et al.,  “-VAE: Learning Basic Visual Concepts with a Constrained Variational Framework,”  in ICLR, Apr. 2017.
  * [17] M. D. Hoffman, D. M. Blei, C. Wong, and J. Paisley,  “Stochastic Variational Inference,”  Journal of Machine Learning Research, vol. 14, pp. 1303–1347, May 2013.
  * [18] D. Zhang, N. Malkin, Z. Liu, A. Volokhova, A. Courville, and Y. Bengio,  “Generative Flow Networks for Discrete Probabilistic Modeling,”  in Proceedings of the 39 th International Conference on Machine Learning, Maryland, USA, Jul. 2022.
  * [19] R. Riegel et al.,  “Logical Neural Networks,”  arXiv:2006.13155 [cs], Jun. 2020.
  * [20] T. Brown et al.,  “Language Models are Few-Shot Learners ,”  in Advances in Neural Information Processing Systems 33 (NeurIPS), Vancouver, Canada, Dec. 2020.
  * [21] S. Kottur, J. F. Moura, S. Lee, and D. Batra,  “Natural Language Does Not Emerge ’Naturally’ in Multi-Agent Dialog,”  in Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, Copenhagen, Denmark, Sep. 2017, pp. 2962–2967.
  * [22] D. Fudenberg and J. Tirole,  “Game Theory,”  in Cambridge, MA: MIT Press, 1991.
  * [23] C. Santana,  “Ambiguity in Cooperative Signaling ,”  Philosophy of Science,The University of Chicago Press on behalf of the Philosophy of Science Association, vol. 81, no. 3, pp. 398–422, Jul. 2014\.
  * [24] B. Fong and D. I. Spivak,  “Seven Sketches in Compositionality: An Invitation to Applied Category Theory,”  arXiv preprint arXiv:1803.05316, Oct. 2018.
  * [25] T. D. Bradley, J. Terilla, and Y. Vlassopulos,  “An Enriched Category Theory of Language: From Syntax to Semantics,”  La Matematica, pp. 1–30, Mar. 2022.
  * [26] D. V. Lindley,  “On a Measure of the Information Provided by an Experiment,”  The Annals of Mathematical Statistics, vol. 27, no. 4, pp. 986–1005, Jul. 1956.
  * [27] F. Facchinei and C. Kanzow,  “Generalized Nash Equilibrium Problems ,”  Annals of Operations Research, vol. 175, no. 1, pp. 177–2011, Sep. 2010.
  * [28] L. J. Ratliff, S. A. Burden, and S. S. Shastry,  “On the Characterization of Local Nash Equilibria in Continuous Games ,”  IEEE Transactions on Automatic Control, vol. 61, no. 8, pp. 2301–2307, Jun. 2016.
  * [29] J. B Hiriart-Urruty,  “Generalized Differentiability, Duality and Optimization for Problems Dealing with Differences of Convex Functions,”  in Convexity and Duality in Optimization, Springer, 1985.
  * [30] M. Hong, M. Razaviyayn, Z. Q. Luo, and J. S. Pang,  “A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data: With Applications in Machine Learning and Signal Processing,”  IEEE Signal Processing Magazine, vol. 33, no. 1, pp. 57–77, Dec. 2015.
  * [31] S. Boyd and L. Vandenberghe,  “Convex Optimization,”  in Cambridge University Press, 2004.
  * [32] J. Pawlick and Q. Zhu,  “Deception by Design: Evidence-Based Signaling Games for Network Defense,”  in Proceedings of the Workshop on the Economics of Inform. Security and Privacy, available at http://arxiv.org/ abs/1503.05458, Delft, The Netherlands, Jun. 2015.
  * [33] T. Deleu et al.,  “Bayesian Structure Learning with Generative Flow Networks,”  arXiv preprint arXiv:2202.13903, Feb. 2022.
  * [34] G. Jáger, L. P. Metzger, and F. Riedel,  “Voronoi Languages: Equilibria in Cheap-talk Games with High-Dimensional Types and Few Signals ,”  Games and Economic Behavior, vol. 73, no. 2, pp. 517–537, Nov. 2011\.
  * [35] T. M. Cover and J. A. Thomas,  “Elements of Information Theory,”  in Wiley, 1991.