Bayesian Inverse Contextual Reasoning for Heterogeneous Semantics-Native Communication

The semantic-effectiveness problem was identified a year after Shannon’s mathematical communication theory was introduced [9]. Recently, with the help of advanced machine learning techniques, the problem has been re-examined through the semantic communication framework, which can be divided into three sub-directions [5, 6]. The first sub-direction focuses on extracting semantically important information for communication. Unlike classical compression in source coding, meaningfulness is determined not only by raw data characteristics [12], but also by receiver-centric metrics, such as the age-of-incorrect information (AoII) [3, 4], control stability [2, 13], and attention-based similarity [14] between agents. The second sub-direction involves transforming the raw data modality while maintaining its meaning. For instance, image-to-text embedding via Transformer [7, 8] and conversion from system states into the state evolution law using the Koopman operator [15]. Lastly, the third sub-direction involves building a knowledge base to exploit knowledge as side information or leverage dependencies in target data, which demonstrated a reduction in communication payload sizes in speech-based communication, video streaming, and holographic communication applications [16, 17].

However, existing semantic communication frameworks have limitations, as they are often restricted to specific data domains (e.g., images and natural languages) or environments (e.g., control systems), and their ML-based internal operations lack a principled and explainable approach. To address these issues, [1] was the first to propose a stochastic model of semantic communication based on conditional random fields, called SNC, which is compatible with the standard Shannon communication model. Nonetheless, as the SNC requires agents to share the same context to be effective and efficient, it is difficult for agents that do not know the context to participate in communication for the first time to leverage SNC. This study focuses on exploring ways to solve this challenging problem.

The concept of CR refers to the human ability to grasp implied meanings in communication, including linguistic ambiguity and communication intent, by taking into account the social interaction and local context of communication [18, 19, 20, 21]. One widely used approach for studying CR is the rational speech act (RSA) framework [22, 23, 24, 25]. The RSA framework models the sender and receiver as stochastic models, simulating the CR in human communication. Recently, researchers have explored the relationship between the RSA model and optimal transport in [26], and investigated it from an information-theoretic rate-distortion perspective in [27]. However, these computational approaches mostly focus on the sender and overlook the receiver and their interaction with the sender. In contrast, the SNC computational framework emphasizes the CR of both the sender and receiver, as well as their interactions. While effective and efficient communication methods have been established based on CR, no known method exists to understand the context based on communication results. This article aims to address this issue by enabling agents that do not share context to perform SNC.

The key contributions of this article are summarized as follows.

• •

  This work is the first of its kind that discusses and solves the inverse problem of CR-based SNC. Since SNC is known to be efficient from a communication perspective, its inverse problem is basically under-determined and difficult to solve. This article provides a couple of solutions that effectively and efficiently infer the communication context from SNC samples.

• •

  To solve the iCR problem, we first introduce a Bayesian iCR method, which is based on the tMH, which is akin to MCMC sampling. The method first models CR as a likelihood function, and by using the Bayes rule, the posterior distribution can be found. Regarding the posterior distribution as a target, the tMH provides samples that follow the target distribution to enable communication with a third agent.

• •

  To reduce the computational burden of the Bayesian iCR method, we linearize the CR by training a two-layer fully-connected linear neural network model. The loss function for training the model incorporates loss terms related to inference accuracy, communication effectiveness, and restricted isometry property (RIP) for CR invertibility.

• •

  Based on the LCR model, we recast the iCR problem as an iLCR problem and propose a Bayesian iLCR method to solve it. The Bayesian iLCR also uses the proposed tMH but uses the trained LCR model when computing the acceptance probability, which results in lower computational complexity compared to the Bayesian iCR.

• •

  We provide numerical simulation results that corroborate the communication effectiveness and computational efficiency of the proposed Bayesian iLCR. Although the Bayesian iCR is a novel approach, we regard it as a baseline and compare it with the Bayesian iLCR method. The results show that the Bayesian iLCR outperforms the Bayesian iCR method in terms of inference accuracy and computational complexity.

The rest of this article is organized as follows. In Section II, we provide preliminaries including the system model under study and background knowledge to understand SNC and MCMC sampling. In Sections III and IV, a Bayesian iCR and Bayesian iLCR are proposed, respectively. Numerical results are provided in Section V, and concluding remarks are given in Section VI.

Consider a world wherein multiple agents deal with arbitrary tasks in the form of a referential game.²²2The referential game is a specific type of communication game that involves two players: a sender and a receiver. The sender is given an object, and its goal is to convey a message to the receiver so that the receiver can identify the object among a set of distractors. This game has been used to study the emergence and evolution of language, as it allows researchers to investigate how meaning is shared and how communication systems can arise from individual interactions. To coordinate, agents communicate in pairs, each of which consists of a sender and receiver agents. The sender’s goal is to induce the corresponding receiver to take a specific task-related action, which will hereafter be referred to as a target action. Let $\mathbb{A}$ be the finite set of possible actions that the receiver can take, where one of them is the target and the others are distractors. We assume that there are no pre-agreed symbols representing actions among agents, and as a result, the agents cannot directly communicate the target action. Denote by $A\in\mathbb{A}$ the random variable of the target action chosen by the sender, and $p(A)$ its prior distribution.

In the meantime, let $\mathbb{C}$ be the finite set of concepts that the agents commonly learn and understand while solving the given tasks. Here, a concept can be seen as a fundamental unit feature (meaning) that composes actions. Each action in $\mathbb{A}$ has one or more relevant concepts in $\mathbb{C}$. For fixed sets of actions $\mathbb{A}$ and concepts $\mathbb{C}$, context is defined as the relevance of concepts in $\mathbb{C}$ to actions in $\mathbb{A}$. Note that the context is determined by the tasks that the agents are carrying out. Throughout this article, a context is expressed as a matrix $\mathbf{X}=(x_{c,a})\in\mathbb{X}$, where $\mathbb{X}\subset\{0,1\}^{|\mathbb{C}|\times|\mathbb{A}|}$ is the set of all possible context configurations in the world. The entry $x_{c,a}\in[0,1]$ indicates the relevance of the concept $c$ to the action $a$, $\forall(c,a)\in\mathbb{C}\times\mathbb{A}$. For instance, $x_{c,a}=1$ means that the concept $c$ is relevant to the action $a$ (or $c$ and $a$ are in context), while $x_{c,a}=0$ means the concept $c$ is irrelevant to the action $a$ (or $c$ and $a$ are out of context). In general, since each action will not be associated with all concepts, the context matrix referred to here is a sparse matrix.

Suppose a sender intends to induce the corresponding receiver to take a target action $A=a^{*}\in\mathbb{A}$ under a communication-limited environment, in which only a symbol of one concept can be sent at a time. We suppose that there is a unique symbol representing each concept. In order to convey the communication intent (or semantics), the sender conceptualizes $a^{*}$ into multiple relevant concepts, chooses the most relevant one, and symbolizes it for communication purposes. Denote by $C$ the random variable of the chosen concept, and $p(C)$ its prior distribution. The symbolized concept is sent to the receiver, and upon receiving the symbol, the receiver first takes the inverse process of symbolization to retrieve the concept. Then, the receiver takes an action $\hat{a}\in\mathbb{A}$ which is the most relevant to the obtained concept. Here, what the sender and receiver technically communicate are the symbols of concepts (symbolized concepts), where the symbols can be seen as codewords in traditional communications. Indeed, the process of obtaining a symbolized concept from the intended action at the sender and its inverse process at the receiver can be jointly designed end-to-end. However, the conceptualization process is separately considered in this work to focus on the impact of CR which will be introduced later. If the receiver’s action after communication coincides with the sender’s intention, i.e., $a^{*}=\hat{a}$, then communication is said to be effective and the meaning was conveyed correctly.³³3Strictly speaking, the effectiveness of communication is task-oriented, and thus, it should be designed based on the task goal that the agents are solving. Here, we assume that the communication is effective when the receiver’s action $\hat{a}$ is exactly the same as the target action $a^{*}$.

The process of conceptualization is referred to as semantic encoding, while its inverse process is referred to as semantic decoding. Next, we explain two different semantic coding methods which are stochastic in nature. One is naïve semantic coding and the other is rational semantic coding. A key difference is that the latter leverages CR for more efficient and effective communication. Specifically, we focus on the CR of rational semantic coding in the rest of this article.

The Bayesian inference methods proposed in this article are based on MCMC sampling. Here we briefly introduce basic concepts about MCMC sampling.

Assuming that the mapping function $\mathcal{R}$ is linearized, the rational semantic decoder can be written as

for some $|\mathbb{C}||\mathbb{A}|\times(|\mathbb{C}||\mathbb{A}|+|\mathbb{C}|+|\mathbb{A}|)$ dimensional matrix $\mathbf{\Phi}$, where $\tilde{\mathcal{R}}(\mathbf{T})=(\tilde{r}_{c,a})\in[0,1]^{|\mathbb{C}|\times|\mathbb{A}|}$ is the matrix that approximates $\mathcal{R}(\mathbf{T})$ incorporating the impact of perturbation that comes from the linearization. In addition, $\mathbf{vec}(\tilde{\mathcal{R}}(\mathbf{T}))\in\mathbb{R}^{|\mathbb{C}||\mathbb{A}|}$ and $\mathbf{vec}(\mathbf{T})\in\mathbb{R}^{|\mathbb{C}||\mathbb{A}|+|\mathbb{C}|+|\mathbb{A}|}$ are the column vectors obtained by vectorizing $\tilde{\mathcal{R}}(\mathbf{T})$ and $\mathbf{T}$, respectively. The rational semantic encoder obtained through a single iteration of $\eqref{eq:RSA_recursion}$ upon $\tilde{\mathcal{R}}(\mathbf{T})$ is denoted by $\tilde{\mathcal{S}}(\mathbf{T})=(\tilde{s}_{c,a})\in[0,1]^{|\mathbb{C}|\times|\mathbb{A}|}$.

One effective way to obtain the matrix $\mathbf{\Phi}$ is to train a two-layer fully-connected neural network without non-linear activations which takes $\mathbf{T}$ as input and $\mathcal{R}(\mathbf{T})$ as output. In general, it is difficult to train such a matrix that linearizes a given recursive non-linear evolution with small misfit $\|\mathbf{vec}(\mathcal{R}(\mathbf{T})-\tilde{\mathcal{R}}(\mathbf{T}))\|_{2}^{2}$. However, in the scenario under consideration, it is possible to obtain $\mathbf{\Phi}$ since both $\mathbf{vec}(\mathcal{R}(\mathbf{T}))$ and $\mathbf{vec}(\mathbf{T})$ are sparse vectors from the structure. Later on, we show that whether the recursion is linearizable or not depends on the sparsity of the context $\mathbf{X}$. Moreover, when training $\mathbf{\Phi}$ (or designing loss function for training the linear neural network model), our focus is not only on minimizing the misfit $\|\mathbf{vec}(\mathcal{R}(\mathbf{T})-\tilde{\mathcal{R}}(\mathbf{T}))\|_{2}^{2}$ but also ensuring the communication effectiveness of the approximated rational semantic coding pair $(\tilde{\mathcal{S}}(\mathbf{T}),\tilde{\mathcal{R}}(\mathbf{T}))$, as much as the original pair $(\mathcal{S}(\mathbf{T}),\mathcal{R}(\mathbf{T}))$ provides.

The LCR model is trained as follows. First, generate data samples $(\mathbf{T}_{i},\mathcal{R}(\mathbf{T})_{i})_{i=1}^{N}$ for a fixed prior distribution, i.e., $\mathbf{T}_{i}\sim p(\mathbf{T})$, $1\leq\forall i\leq N$, and then obtain the neural network model weights that minimize the loss function defined by

for some constants $\lambda_{\text{mis}},\lambda_{\text{eff}}\geq 0$ such that $\lambda_{\text{mis}}+\lambda_{\text{eff}}=1$, where $\mathcal{L}_{\text{mis}}(\mathbf{T})=\|\mathbf{vec}(\mathcal{R}(\mathbf{T})-\tilde{\mathcal{R}}(\mathbf{T}))\|_{2}^{2}$ and $\mathcal{L}_{\text{eff}}(\mathbf{T})=\sum_{a\in\mathbb{A}}p(a)\left(1-\sum_{c\in\mathbb{C}}\tilde{s}_{c,a}\tilde{r}_{c,a}\right)$ are misfit and effectiveness loss term, respectively. It is worth mentioning that the loss function can be defined in various ways, for example using cross-entropy for each row vector of $\mathcal{R}(\mathbf{T})$ and $\tilde{\mathcal{R}}(\mathbf{T})$, however, we used mean squared error (MSE) misfit function to obtain the linearized form of the CR in (24). The original CR model does not have a one-to-one relationship between input and output. However, the LCR model can be seen as a one-to-one mapping function. Therefore, from the perspective of invertibility, it can be understood that utilizing the LCR model instead of the CR model is more advantageous. On the other hand, in a situation where Carol acts as the eavesdropper and Alice and Bob aim to prevent eavesdropping, it is more advantageous to use CR.

Recall that the dimension of $\mathbf{vec}(\mathbf{T})$ is larger than that of $\mathbf{vec}(\tilde{\mathcal{R}}(\mathbf{T}))$, which in turn makes the linear system (24) underdetermined. In addition, note that the entries of $\mathbf{T}$ (strictly saying $\mathbf{X}$) are sparse. In consequence, having the LCR model, the iCR problem is recast as an iLCR problem (or compressed sensing problem), where $\mathbf{vec}(\tilde{\mathcal{R}}(\mathbf{T}))$ is a noiseless observation vector, $\mathbf{\Phi}$ is a measurement matrix, and $\mathbf{vec}(\mathbf{T})$ is an unknown vector which requires to be reconstructed. Considering the additive noise in (14), a noisy empirical decoder $\bar{\mathbf{R}}$ corrupted by a zero-mean additive Gaussian random noise $\mathbf{N}\in\mathbb{R}^{|\mathbb{C}|\times|\mathbb{A}|}$ is $\bar{\mathbf{R}}=\tilde{\mathcal{R}}(\mathbf{T})+\mathbf{N}$, and in a vectorized form

For the sake of convenience, instead of notations $\mathbf{vec}(\bar{\mathbf{R}})$, $\mathbf{vec}(\mathbf{T})$, $\mathbf{vec}(\mathbf{X})$ and $\mathbf{vec}(\mathbf{N})$, we use vectors $\bar{\boldsymbol{r}}$, $\boldsymbol{t}$, $\boldsymbol{x}$ and $\boldsymbol{n}$ throughout this section, thereby having the following simplified equation

which is equivalent to (27).

Now, suppose that $\boldsymbol{t}$ is a $s$-sparse vector, which means that the number of non-zero entries in the vector is (at most) $s\in\mathbb{Z}_{+}$. Then, according to the compressed sensing theory, the matrix $\mathbf{\Phi}$ should satisfy the $(s,\delta)$-restricted isometry property (RIP) condition in order to correctly estimate the unknown vector. The matrix $\mathbf{\Phi}$ is said to satisfy the $(s,\delta)$-RIP if there exists $\delta\in(0,\frac{1}{3})$ such that every $s$-sparse vector $\boldsymbol{v}$ holds

In normal terms, $\mathbf{\Phi}$ behaves like an isometry (orthonormal) matrix, even though it is not a square matrix. As a matter of fact, obtaining $\mathbf{\Phi}$ that meets the RIP condition (29) is a strongly NP-hard problem [34]. Moreover, the matrix $\mathbf{\Phi}$ in our case must also linearize the CR, which makes it harder to obtain such a matrix. However, it is known that some random matrices, for example, the Gaussian or Bernoulli distribution, satisfy the RIP condition with high probability. Considering that the linear neural network for $\mathbf{\Phi}$ that minimizes $\mathcal{L}_{1}$ is trained based on a stochastic optimization such as stochastic gradient descent (SGD) method under Gaussian random initialization, it is likely that the trained $\mathbf{\Phi}$ meets the $(s,\delta)$-RIP condition.

Nevertheless, in order to further ensure an invertible CR, we propose an alternative loss function that incorporates the $(s,\delta)$-RIP constraint to train the linear neural network. The proposed loss function can be written as

for some constant $\lambda_{2}\geq 0$, where $\mathcal{L}_{\text{RIP}}=\left(\frac{\|\mathbf{\Phi}\boldsymbol{t}\|_{2}^{2}}{\|\boldsymbol{t}\|_{2}^{2}}-1\right)^{2}$. When minimizing $\mathcal{L}_{2}$, the new regularization term forces the $\mathbf{\Phi}$ to satisfy (29), for all vectorized data samples $\mathbf{T}_{1},\mathbf{T}_{2},\dots,\mathbf{T}_{N}$, which we call a quasi-RIP condition. Since it does not fully characterize the original $(s,\delta)$-RIP condition, in the sense that the condition only holds for the data samples, the regularization term still cannot fully guarantee that the matrix $\mathbf{\Phi}$ trained by using (30) holds the $(s,\delta)$-RIP condition. However, compared to that trained with $\mathcal{L}_{1}$, it is more likely to hold the condition if the constant $\lambda_{2}$ is chosen appropriately.

Now, let us go back to the iCR problem. Supposing that the LCR model $\mathbf{\Phi}$ is well-trained and known to all agents, what remains is to solve an underdetermined system, i.e., an iLCR problem. To solve it, we use the tMH described in Algorithm III-2, but with a different target distribution.

With a known $\mathbf{\Phi}$, the likelihood of $\bar{\mathbf{R}}$ given $\mathbf{T}$ can be written as

From the Bayes’ rule, the posterior distribution of $\mathbf{T}$ given $\bar{\mathbf{R}}$ is

where $U^{\prime}=\int\exp\left(-\frac{1}{2\sigma^{2}}\|\bar{\boldsymbol{r}}-\mathbf{\Phi}\boldsymbol{t}\|_{2}^{2}\right)p(\boldsymbol{t})d\boldsymbol{t}$. Regarding (35) as a target distribution, $\mathbf{T}$ (or equivalently $\boldsymbol{t}$) can be sampled by using the tMH. Since the first stage of the tMH finds the sparse pattern of $\mathbf{X}$ and the second stage finds the prior distributions $\boldsymbol{y}$ and $\boldsymbol{z}$, the overall process can be seen as solving a compressed sensing problem. In fact, the problem at hand can be solved using the existing compressed sensing method of the orthogonal matching pursuit (OMP) family [35]. However, in order to maintain consistency with the previous Bayesian iCR method, tMH is used. The existing OMP family follows a process of finding the entry of an unknown vector that is most likely to be non-zero in the first iteration, and then repeating the process of finding the entry of the residual vectors that are most likely to be non-zero in the subsequent iterations. In contrast, the proposed method updates every unknown vector entry in every iteration. Although the proposed method requires greater computational effort, it has the advantage of being robust to error propagation.