A STANDARD approach to describe an information source is to model a source as a stochastic process {X i }, and when the stochastic process is memoryless, it suffices to model a source as a random variablefoot_0 X with a given probability distribution p(x) [2], [3]. In this paper, we study a new source model, which consists of an intrinsic state process and an extrinsic observation process. In the memoryless case, we can describe such a source model as a pair of random variables (S, X), with a given joint probability distribution p(s, x), defined over an appropriate product alphabet S × X .
In order to characterize the information-theoretic aspect of such a source, consider the problem of compressing the source (S, X) so as to reproduce, in a lossy sense, a reproduction ( Ŝ, X) over a reproduction product alphabet Ŝ × X . Of course, a pair of distortion measures, d s : S × Ŝ → R and d o : X × X → R, are introduced correspondingly. Here, the subscript s stands for "state" and the subscript o stands for "observation".
A key point of the problem is that the compressor only has access to X, the extrinsic observation; -while S, the intrinsic state, remains unrevealed. The situation is illustrated in Figure 1.
Our source model, termed a semantic source in the sequel, is motivated by the recent surge of interest in the semantic aspect of information. In a number of applications that may benefit from taking into account the "semantic" feature of information, it is adequate to adopt a goal-oriented perspective; that is, the destination's interest in obtaining a piece of information is to accomplish a certain goal. Furthermore, it is customary to adopt an inference-theoretic problem formulation, corresponding semantic rate-distortion problem formulation in Section II, for which we establish the semantic rate-distortion function in general form in Section III. As an application of the general results, in Section IV we turn to a case study of Gaussian extrinsic observation, assuming a linear relationship between the intrinsic state and the extrinsic observation, under a quadratic distortion structure. Therein, we formulate a convex programming problem to solve for the semantic rate-distortion function. When the Gaussian observation model further satisfies a diagonalizability condition, we develop a reverse water-filling type of solution in Section V. Finally we conclude this paper in Section VI.
The first formulation in Shannon's information theory is lossless source coding, wherein a sequence of symbols obeying a certain probabilistic law is represented as a bit string (i.e., a codeword) by an encoder, and the decoder reproduces, based upon the codeword, the original sequence of symbols, with success probability exactly one or asymptotically approaching one. Hence, the coding is solely determined by the probabilistic model of the source, and there is certainly no role of the semantic aspect of the source. This is also consistent with Shannon's remark in his landmark paper [2], saying "these semantic aspects of communication are irrelevant to the engineering problem."
In a broad sense, however, the lossy source coding formulation in Shannon's information theory, namely, the rate-distortion theory [12], has provided a means of studying the semantic aspects of a source. This is because the coding is not solely determined by the probabilistic model of a source, but is also affected by a distortion measure, which may be defined in a rather versatile way so as to capture the "utility" when the source is reproduced at the decoder.
Our present work goes one step further, by endowing a source with a state-observation structure and studying the rate distortion function of such a source model. This model captures the fact that the semantic aspects of a source are generally embedded as intrinsic features, and hence should be characterized by studying the reproduction of the intrinsic state, in addition to the reproduction of the extrinsic observation. Our treatment of semantic aspects of sources is also in line with the recent heightened interest in the development of 5G and beyond wireless systems [13], [14] [15], where for many applications the semantic aspects correspond to the accomplishment of certain inference goals. Hence, if we consider an information theoretic characterization of such a "semantic" source, the task of coding is to efficiently encode the extrinsic observation so that the decoder can infer both the intrinsic state and the extrinsic observation, subject to fidelity criteria on both, simultaneously. Our problem formulation and approach are closely related to two variants of the standard rate distortion theory, namely, the indirect rate distortion function and the rate distortion function under multiple distortion measures; see our discussion following Theorem 1 in Section III.
The inference-theoretic goal-oriented approach adopted in our problem formulation does not seek a task-independent universal definition of semantic information, which is outside the scope of the present paper; for some attempts in that regard, see, e.g., [16], [17] [18], [19] for a few representative works that undertake drastically different approaches.
As related topics, the information bottleneck [20], [21] and the privacy funnel [22], [23] are, in a certain sense, dual concepts, and both place constraints in terms of mutual information. The underlying idea of the information bottleneck is, in a broad sense, similar to ours. Specifically, there one generates a reproduction based upon the extrinsic observation, minimizing the mutual information between the extrinsic observation and the reproduction, while maintaining a level of mutual information between the intrinsic state and the reproduction. But for the information bottleneck problem formulation, there is neither an explicit distortion measure, nor an operational definition of lossy compression.
Task-based compression has been approached mainly from the perspective of quantizer design [24]. It has been demonstrated that steering the design goal according to the task leads to performance benefits compared with a conventional task-agnostic approach, a conclusion in line with what we advocate in our work. The perception-distortion tradeoff [25] imposes an additional constraint on the probability distribution of the reproduction. None of these related works proposes to decompose the information source into intrinsic and extrinsic parts as in our work, let alone investigates the joint behavior of them. In [26], a similar intrinsic state-extrinsic observation model is studied, but the encoder is designed based on the marginal distribution of the extrinsic observation only.
As already outlined in the introduction, we model a memoryless semantic source as a pair of random variables (S, X) that are correlated with joint probability distribution p(s, x).
The semantic aspect is embodied in the intrinsic state S, which is not observable but can only be inferred from the extrinsic observation X. In order to characterize the rate-distortion behavior of the semantic source, we consider a sequence of independent and identically distributed (i.i.d.) samples of (S, X), denoted as (S i , X i ) i∈N , and denote its length-n block as (S n , X n ).
The i.i.d. source model is an idealistic scenario for our information-theoretic study. Real-world data generally exhibit sophisticated memory structures. A particularly interesting scenario is when the intrinsic state is a Markov chain, and the extrinsic observation obeys a hidden Markov model (HMM) [27]. Extensions of our approach for semantic source models with memory are left for future research.
The lossy compression of a semantic source has been illustrated in Figure 1
We will also consider a variant of the distortion constraint; 257 that is, the state distortion and the observation distortion are 258 linearly combined to yield a single overall distortion. Hence, 259 instead of (3) and (4), the decoding functions are required to 260 satisfy the following weighted distortion constraint:
where w s and w o are non-negative weighting coefficients.
It is also natural to generalize the system model to 264 include several intrinsic state variables each associated with 265 a specified reproduction and a distortion. Such a seman-266 tic source is described by a tuple of random variables, 267 (S 0 , S 1 , . . . , S k-1 , X), with joint probability distribution 268 p(s 0 , s 1 , . . . , s k-1 , x) over
295
The detailed derivation, which is based on a unified treatment in [33], is given in Appendix I.
We note that the semantic rate distortion function can be 317 non-trivial even for the special case where S is a deterministic 318 function of X, because from a lossy reproduction of X it 319 is generally impossible to reproduce S in a lossless fashion.
Specifically, suppose that S = g(X). Then ds (x, ŝ) can be
323
Similar to standard rate distortion functions, a corollary of the semantic rate distortion function as given by Theorem 1 is the following regarding monotonicity and convexity.
The semantic rate distortion function R(D s , D o ) in Theorem 1 has the following properties:
Proof: The proof of the first two properties is exactly the same as that for standard rate distortion functions; see, e.g., [3]. The third property is then an immediate corollary of the second property.
Corollary 1 implies a trade-off between the two distortions: for a given code rate, the smaller the state distortion, the larger the observation distortion, and vice versa. Concrete numerical examples can be found in Section IV, where Figures 2 and4 plot the achievable regions of (R, D s , D o ) and their projections under different values of R, for two experimental setups, respectively. These plots demonstrate that for fixed R, the achievable (D s , D o ) pairs form a convex region, whose boundary exhibits a trade-off between D s and D o . Hence a sensible coding scheme of a semantic source should exhibit such behavior. Now consider the weighted distortion constraint (6). We have the following corollary. We end this section with the semantic rate distortion function (8) for semantic sources with several intrinsic states, as given by the following corollary. Its proof is essentially identical to that of Theorem 1.
Authorized licensed use limited to: Princeton University. Downloaded on November 14,2022 at 17:00:42 UTC from IEEE Xplore. Restrictions apply.
where
and
we can represent S according to
417
We consider quadratic distortion measures, defined as
420
Consequently, we have
423 3 We use K V to denote the covariance matrix of a random column vector V .
For the considered model (19), we can derive its semantic rate distortion function, given by the following theorem.
Theorem 2: The semantic rate distortion function for the semantic source with Gaussian extrinsic observation and linear state-observation relationship (19), under quadratic distortion measures (22) and (23), is given by:
where S m denotes the set of all m × m positive definite matrices. Note that here we use a subscript G to emphasize that the extrinsic observation is Gaussian.
Proof: See Appendix II.
From (28), when Z is sufficiently strong so that tr(K Z ) > D s , the optimization ( 26) is no longer feasible and hence R G (D s , D o ) = ∞. Otherwise, there is no further restriction on K Z . For example, even if Z = 0, i.e., the relationship between S and X is deterministic as S = HX, the optimization problem in Theorem 2 is still non-trivial.
A simplified case arises when H is an orthogonal matrix satisfying H T H = I. In this case, (28) becomes (30) which can then be combined with (29) leading to a single distortion constraint
In Theorem 2, the matrix Δ which we optimize corresponds to the mean squared error (MSE) of estimating X based upon X at the decoder. The key to the proof of Theorem 2 is to show that the semantic rate distortion function is achieved by a Gaussian reproduction. This is similar to situations in several Gaussian lossy compression problems, including the standard Gaussian rate distortion problem [12] and the Gaussian quadratic CEO problem [37]. Existing techniques based on the entropy power inequality (EPI), extremal inequalities, and Fisher information inequalities may also be interpreted as the optimality of Gaussian reproduction for the minimum mean squared error (MMSE) estimation under a given MSE constraint. In our analysis, we further need to accommodate with two MSE constraints, corresponding to the intrinsic state and the extrinsic observation, respectively.
Compared with the general form of semantic rate distortion function in Theorem 1, Theorem 2 involves only one matrix-valued optimization variable Δ, which, as remarked in the previous paragraph, is the MSE of estimating X based upon X alone. In fact, the solution exhibits a Markov structure, i.e., S ↔ X ↔ X ↔ Ŝ. To help understand the optimality of the Markov chain solution, supposing that an alternative solution ( X , Ŝ ) is given which does not satisfy the Markov structure, consequently one can form an improved reproduction as X = E(X| X , Ŝ ), satisfying the Markov structure and achieving the same code rate I(X; X, Ŝ ) = I(X; X , Ŝ ). The Markov chain solution further suggests a "two-stage" coding interpretation which is in fact extensively adopted in practice: the decoder first generates a reproduction for X as X, and then uses that reproduction to further generate a reproduction for S as Ŝ. Similar to the standard Gaussian rate distortion problem, the optimal X can be constructed with the aid of a "test channel", for which X as the channel input is Corollary 4: For a semantic source (S, X) with general probability density function, whose covariance matrix is given by (20), its semantic rate distortion function subject to quadratic distortion constraints (22) and (23) satisfies
Proof: See Appendix III.
We remark that the optimization problem in Theorem 2 is convex, and hence can be numerically solved by software like CVX in an efficient and stable fashion. In this subsection we present some illustrative numerical examples.
Our first example is a small-scale toy model, given by
The resulting semantic rate distortion function is computed 517 as displayed in Figure 2. The dotted region in Figure 2(b) 518 indicates that both constraints (28) and ( 29) are active. The 519 trade-off between the two distortions are clear: the smaller the 520 state distortion, the larger the observation distortion, and vice 521 versa.
Our second example captures a sparse state-observation 523 relationship, as follows. The extrinsic observation is a length- does not seem to be sensitive to the choice of D s . This fact has an important consequence for designing lossy compression schemes for semantic sources: although several different codes may have similar performance in terms of reproducing the extrinsic observation, they can differ considerably in terms of reproducing the intrinsic state. A heuristic explanation is as follows: since X is a high-dimensional vector, describing it along several different directions may lead to similar quadratic distortion performance; but since S corresponds to a low-dimensional feature of X, its reproduction only favors the direction of describing X that retains the feature of S the best.
We can derive from Theorem 2 several corollaries corresponding to the variants of the problem formulation in Section II.
First, let us consider replacing the quadratic distortion 565 measures by the positive semi-definite distortion constraints. 566 Following the same arguments in the proof of Theorem 2, 567 we again arrive at the optimality of Gaussian descriptions 568 under positive semi-definite distortion constraints, and hence 569 the following corollary characterizes the semantic rate distor-570 tion function.
Corollary 5: Consider the positive semi-definite distortion 572 measures as
The semantic rate distortion function is given by 576
This is a semi-definite programming problem and can be 581 readily solved by software.
Now consider the weighted distortion constraint, where 583 the distortion measure is defined as a weighted sum of two 584 individual distortion measures, i.e.
Authorized licensed use limited to: Princeton University. Downloaded on November 14,2022 at 17:00:42 UTC from IEEE Xplore. Restrictions apply.
Applying Corollary 2, we obtain the semantic rate distortion function in the following corollary.
Corollary 6: For the weighted distortion measure d, the semantic rate distortion function R( D) is given by
Finally, consider the case of k intrinsic states. The extrinsic observation X is still N (0, K X ). For each j ∈ {0, 1, • • • , k -1}, the j-th intrinsic state is generated according to
where H j is an l j × m matrix, and Z j is a random vector independent of X, with zero mean and covariance matrix K Zj .
We consider quadratic distortion measures, as
The semantic rate distortion function is given by the following corollary.
Analogous to the standard Gaussian rate distortion problem wherein (after appropriate linear transformation) the solution can be interpreted as a reverse water-filling type of rate allocation, for the semantic rate distortion function in Theorem 2, under a diagonalizability condition, the solution can also be interpreted as reverse water-filling, but with appropriately weighted water levels.
For the model of Gaussian observation with linear state-observation relationship in Section IV, we further assume that the following diagonalizability condition is satisfied: there exists an unitary matrix Q such that
simultaneously hold. Here it loses no generality to order
Lemma 1: Under the diagonalizability condition, the result-634 ing optimal Δ takes the form
and the semantic rate distortion function in Theorem 2 can be 637 further written in terms of the following optimization problem: 638
Proof: See Appendix IV.
In order to describe the weighted reverse water-filling solu-645 tion, we first introduce the following curves.
which starts from (tr(HK X H T + K Z ), tr(K X )) and 650 ends at (tr(K Z ), 0).
• Curve C o :
652
(48) 654 which starts from (tr(HK X H T + K Z ), tr(K X )) and 655 ends at (tr(K Z ), m j=q+1 σ j ). Here, m j=1+1 σ j is inter-656 preted as 0 if H T H is full-rank and thus q = m.
We then introduce the following partitioning of the 658 (D s , D o ) plane, based upon the curves C s and C o :
An example of the partitioning above is plotted in Figure 6.
The following theorem describes the weighted reverse 669 water-filling solution.
670 Theorem 3: For the model of Gaussian observation 671 with linear state-observation relationship in Section IV, 672 under the diagonalizability condition, the optimal
where λ is chosen to satisfy
where μ is chosen to satisfy q j=1 α j δ * j = D str(K Z ).
where λ, μ are chosen to satisfy
Proof: See Appendix IV.
The partitioning {A 0 , A 1 , A 2 , A 3 } is closely related to activity of the constraints (45) and (46), as summarized in Table I. In A 0 , both constraints are inactive, and hence the optimization is unconstrained yielding the trivial solution (49).
In A 1 , only the observation distortion constraint is active, and the solution (50) is a standard reverse water-filling with water level 1/λ. In A 2 , only the state distortion is active, and the solution (51) essentially makes the weighted eigenvalues
with water level 1/μ. Alternatively, we may view the term 1/(μα j ) in ( 51) as a water level with weight 1/α j . In A 3 , both constraints are active, and the solution (52) also fulfills a reverse water-filling structure with unequal water levels.
A case of special interest is where K X and H are both circulant matrices [38]. As the dimension of X grows large, this models the scenario where X is a circularly stationary Gaussian process, 4 and S is obtained via passing X through a time-invariant linear filter whose response is given by the first row of H. For a circulant matrix, the corresponding unitary matrix Q is the well known discrete Fourier transform (DFT) 4 If we remove the circulant restriction and consider a stationary Gaussian process, then we encounter a Toeplitz K X , for which our solution still approximately applies; see, e.g., [38]. Fig. 6. The (Ds, Do) plane is divided into four regions A 0 , A 1 , A 2 , A 3 , which determine the form of the optimal Δ. Five points on the contour R G (Ds, Do) = 50 are marked with colors varying from purple to yellow. matrix, and its eigenvalues are the DFT of the first row of 712 the matrix. Hence the weighted reverse water-filling may be 713 interpreted as exercised in the frequency domain, similar to 714 its counterpart for the standard rate distortion function of 715 stationary Gaussian processes.
In the illustrative example below, consider K X as a 717 128 × 128 circulant matrix with the first row
719 H as a 128 × 128 circulant matrix with the first row
and K Z as a 128 × 128 zero matrix (i.e., no noise in the state-722 observation relationship). Therefore, Q is the 128 × 128 DFT 723 matrix whose (i, j)-th element is
shown in Figure 7, and the diagonal elements ) of QΔQ T for the marked points in Figure 6, plotted with the colors in Figure 6.
) for these points are depicted in Figure 8. For
), the optimal solution degenerates into a standard reverse water-filling form, as indicated by the purple line.
When we go from
), the water level begins to "ripple". Note that this weighted reverse water-filling can be viewed as exercised in the frequency domain, and the angular frequencies are marked on the top of Figure 8.
We have provided a general source model to describe information sources that have semantic aspects, and proposed a corresponding rate distortion problem formulation for characterizing the amount of information content of such semantic sources. We have studied the case of Gaussian extrinsic observation subject to a linear state-observation relationship and a quadratic distortion structure. There are a variety of issues that we have not touched upon in the present work.
First, calculating and bounding the semantic rate distortion functions for other interesting cases would make further use of our proposed framework, for example, when the intrinsic state is a discrete categorical random variable, corresponding to the important problem of classification; see [1] for some preliminary results. Second, a more challenging problem is to estimate the semantic rate distortion function, and more importantly, to develop effective lossy compression methods when the joint probability distribution of the intrinsic state and the extrinsic observation is not perfectly known, say, when only finite training data of the state-observation pair are available.
The key to proving Theorem 1 is converting the semantic rate distortion problem into an equivalent standard rate distortion problem, with an indirect (state) distortion con-765 straint and a direct (observation) distortion constraint. More 766 precisely, we need to show that the constraint with respect 767 to the state distortion measure d s (s, ŝ) is equivalent to a 768 constraint on a converted distortion measure ds (x, ŝ); that 769 is, as long as a reproduction Ŝ satisfies the constraint on 770 ds (x, ŝ), it will satisfy the constraint on d s (s, ŝ), and vice 771 versa.
A general and unified approach to the indirect rate-distortion 773 function put forward in [33] is first showing that the 774 one-shot expected distortion E d s (S, Ŝ) is equivalent to 775 E ds (X, Ŝ) , and then invoking a tensorization argument to 776 extend the one-shot equivalence to block codes. Here we 777 directly illustrate how this can be accomplished for S n ↔ 778 X n ↔ ( Ŝn , Xn ) generated by an arbitrary encoder-decoder 779 pair, as follows:
where (a) is due to independence between Z and X, (b) is according to the problem setup that E(Z) = 0, and (c) is due to the fact that tr(HK X Ŝ ) = tr(K ŜX H T ). From this chain of identities, we see that for any two reproductions of the intrinsic state, Ŝ and Ŝ , we have E d s (S; Ŝ) = E d s (S; Ŝ ) as long as
Therefore, by Theorem 1, the semantic rate distortion function R G (D s , D o ) can be further written as
Notice that, by denoting T ( Ŝ, X) for convenience, h(X| Ŝ, X) can be upper bounded as
where (a) is by the fact that conditioning reduces entropy, and equality holds when X -K XT K -1 T T is independent of T ; (b) is due to the fact that Gaussian distribution maximizes differential entropy with given second central moment. Overall, we can see that this upper bound of h(X| Ŝ, X) is achieved when X and T are jointly Gaussian.
Based on the argument above, for an arbitrary T = ( Ŝ, X), we can generate T = ( Ŝ , X ) according to a linear relationship
where N is a multivariate Gaussian random variable following
and is independent of X. Clearly it holds that K T = K T and K XT = K XT . According to (58), we can see that h(X| Ŝ, X) ≤ h( Ŝ , X ). That is to say, for any ( Ŝ, X) that satisfies the distortion constraints, there always exists a Gaussian ( Ŝ , X ) which also satisfies the distortion constraints, but achieving a lower code rate. We thus establish that jointly Gaussian reproduction ( Ŝ, X) achieves the semantic rate distortion function.
In fact, it is unnecessary to optimize with two random variables ( Ŝ, X) simultaneously, and in the following we reduce the number of optimization variables to only one.
We choose the new optimization variable as cov(X| X, Ŝ), defined as
i.e., the error covariance matrix of MMSE estimating X by ( X, Ŝ). By denoting cov(X| X, Ŝ) as Δ for short, we can write I(X; X, Ŝ) as (26). Therefore, now the key point is to show that the feasible region defined by ( 56)-(57) (denoted as R 1 ) is the same as the feasible region defined by ( 27)-( 29) That is to say, for any K ( Ŝ, X) ∈ R 1 , we can find a corresponding Δ ∈ R 2 , and hence R 1 ⊆ R 2 .
Then we show that R 2 ⊆ R 1 . For any Δ ∈ R 2 , we consider a test channel with X = X + N and let Ŝ = H X, where N obeys Gaussian distribution N (0, Δ). Hence we have
That is to say, for any Δ ∈ R 2 , we can also find a corresponding tuple of K ( Ŝ, X) ∈ R 1 , and hence R 2 ⊆ R 1 . Now, we can conclude that, under the setting of Theorem 2, Theorems 1 and 2 define two optimization problems with the same objective function and the same feasible region. This therefore completes the proof.
By Theorem 2 and the identities 21), the semantic rate distortion function of a jointly Gaussian semantic source with covariance matrix ( 20) is given by
We will prove
for an arbitrary symmetric matrix Δ that satisfies (64), ( 65) and (66), by constructing a test channel. This implies that R(D s , D o ) is no greater than (63).
In order to construct the test channel, let U be a Gaussian 918 vector with zero mean and covariance matrix Δ -ΔK -1 X Δ, 919 independent of (S, X). That Δ -ΔK -1 X Δ is semi-definite 920 will be proved in Lemma 2 at the end of this subsection. 921 Define X = (I m -ΔK -1 X )X + U and Ŝ = K SX K -1 X X. 922 Thus S ↔ X ↔ X ↔ Ŝ is a Markov chain. We will verify in 923 the next paragraphs that E[ ds (X, Ŝ)] ≤ D s , where ds (
In this paper, random variables can be drawn from general alphabets, so random vectors are vector-valued random variables.
Authorized licensed use limited to: Princeton University. Downloaded on November 14,2022 at 17:00:42 UTC from IEEE Xplore. Restrictions apply.
This is the operational definition of a rate distortion function, which has been widely used (see, for example,[3],[28] [29]).Authorized licensed use limited to: Princeton University. Downloaded on November 14,2022 at 17:00:42 UTC from IEEE Xplore. Restrictions apply.