Capacity of Continuous Channels with Memory via Directed Information Neural Estimator

Calculating the capacity (with or without feedback) of channels with memory and continuous alphabets is a challenging task. It requires optimizing the directed information rate over all channel input distributions. The objective is a multi-letter expression, whose analytic solution is only known for a few specific cases. When no analytic solution is present or the channel model is unknown, there is no unified framework for calculating or even approximating capacity. This work proposes a novel capacity estimation algorithm that treats the channel as a `black-box', both when feedback is or is not present. The algorithm has two main ingredients: (i) a neural distribution transformer (NDT) model that shapes a noise variable into the channel input distribution, which we are able to sample, and (ii) the directed information neural estimator (DINE) that estimates the communication rate of the current NDT model. These models are trained by an alternating maximization procedure to both estimate the channel capacity and obtain an NDT for the optimal input distribution. The method is demonstrated on the moving average additive Gaussian noise channel, where it is shown that both the capacity and feedback capacity are estimated without knowledge of the channel transition kernel. The proposed estimation framework opens the door to a myriad of capacity approximation results for continuous alphabet channels that were inaccessible until now.

Abstract-Calculating the capacity (with or without feedback) of channels with memory and continuous alphabets is a challenging task. It requires optimizing the directed information rate over all channel input distributions. The objective is a multiletter expression, whose analytic solution is only known for a few specific cases. When no analytic solution is present or the channel model is unknown, there is no unified framework for calculating or even approximating capacity. This work proposes a novel capacity estimation algorithm that treats the channel as a 'black-box', both when feedback is or is not present. The algorithm has two main ingredients: (i) a neural distribution transformer (NDT) model that shapes a noise variable into the channel input distribution, which we are able to sample, and (ii) the directed information neural estimator (DINE) that estimates the communication rate of the current NDT model. These models are trained by an alternating maximization procedure to both estimate the channel capacity and obtain an NDT for the optimal input distribution. The method is demonstrated on the moving average additive Gaussian noise channel, where it is shown that both the capacity and feedback capacity are estimated without knowledge of the channel transition kernel. The proposed estimation framework opens the door to a myriad of capacity approximation results for continuous alphabet channels that were inaccessible until now.

I. INTRODUCTION
Many discrete-time continuous-alphabet communication channels involve correlated noise or inter-symbol interference (ISI). Two predominant communication scenarios over such channels are when feedback from the receiver back to the transmitter is or is not present. The fundamental rates of reliable communication over such channels are, respectively, the feedback (FB) and feedforward (FF) capacity. Starting from the latter, the FF capacity of an n-fold point-to-point channel P Y n |X n , denoted C FF , is given by [1] In the presence of feedback, the FB capacity C FB is [17] C FB = lim n→∞ sup P X n Y n−1 where, is the directed information (DI) from the input sequence X n to the output Y n [8], and P X n Y n−1 := n i=1 P Xi|X i−1 Y i−1 is the distribution of X n causally-conditioned on Y n−1 (see [21], [24] for further details). Built on (3), for stationary processes, the DI rate is defined as As proved in [8], when feedback is not present, the optimization problem (2) performed over the marginals P X n is equivalent to the optimization in (1). This casts DI as a unifying information measure for representing both FF and FB capacities.
Computing C FF and C FB requires solving a multi-letter optimization problem. Closed form solutions to this challenging task are known only in several special cases. A common example for C FF is the Gaussian channel with memory [14] and the ISI Gaussian channel [15]. There are no known extensions of these solutions to the non-Gaussian case. For C FB , a solution for the 1st order moving average additive Gaussian noise (MA(1)-AGN) channel was found [12]. Another closed form characterization is available for auto-regressive moving-average (ARMA) AGN channels [11]. To the best of our knowledge, these are the only two nontrivial examples of continuous channels with memory whose FB capacity is known in closed form. Furthermore, when the channel model is unknown, there is no efficient method for numerically approximating capacity.
Some recent progress related to capcity computation was made based on deep learning (DL) techniques [9], [19]. In a novel work [9], mutual information neural estimator (MINE) [2] was used to learn a modulation for a memoryless channel. In [19], a capacity estimator was proposed based on reinforcement learning algorithm that iteratively estimates and maximizes the DI rate, but only for discrete alphabet channels with a known channel model. Inspired by the above, we develop the framework for estimating FF and FB capacity of arbitrary continuousalphabet channels, possible with memory, without knowing the channel model. Our method does not need to know the channel transition kernel. We only assume a stationary channel model and that channel outputs can be sampled by feeding it with inputs. Central to our method are a new DI neural estimator (DINE), used to evaluate the communication rate, and a neural distribution transformer (NDT), used to simulate input distributions. Together, the DINE and NDT lay the groundwork for our capacity estimation algorithm. In the remainder of this section, we describe DINE, NDT, and their integration into the capacity estimator.

A. Directed Information Neural Estimation
The estimation of mutual information (MI) from samples using neural networks (NNs) is a recently proposed approach [2], [3]. It is especially effective when the involved random variables (RVs) are continuous. The concept originated from [2], where MINE was proposed. The core idea is to represent MI using the Donsker-Varadhan (DV) variational formula The supremum is over all measurable functions T for which both expectations are finite. Parameterizing T by an NN and replacing expectations with empirical averages, enables gradient ascent optimization to estimate I(X; Y ). A variant of MINE that goes through estimating the underlying entropy terms was proposed in [3]. The new estimators were shown empirically to perform extremely well, especially for continuous alphabets.
Herein, we propose a new estimator for the DI rate I(X → Y). The DI is factorized as where Applying the approach of [3] to the entropy terms, we expand each as a Kullback-Leibler (KL) divergence and a cross-entropy (CE) residual and invoke the DV representation. To account for memory, we derive a formula valid for causally dependent data, which involves RNNs as function approximator (rather than the FF network used in the independently and identically distributed (i.i.d.) case). Thus, the DINE is an RNN-based estimator for the directed information rate from X n to Y n based on their samples.
DI estimators were recently presented in [25]- [27]. Also, an estimator of the transfer entropy using FF networks was proposed [16], which upper bounds the DI in the special case of a jointly Markov process with finite memory. DINE is the first method based on RNN and hence does not assume any parametric model such as discrete alphabets, or Markovity. Further details on the DINE algorithm are given in subsection II-A.

B. Neural Distribution Transformer and Capacity Estimation
DINE accounts for one of the two tasks involved in estimating capacity, it estimates the objective of (2). The remaining task is to optimize this objective over input distributions. Generally, sampling from an arbitrary distribution is a complex task. To overcome this, we design a deep generative model of the channel input distributions, namely the NDT. The idea is similar to ones used for generative modeling tasks, e.g, generative adversarial networks [23] or variational autoencoders [22]. The designed NDT maps i.i.d. noise into samples of the channel input distribution. For estimating FB capacity, in addition to the i.i.d. noise, the NDT also receives channel FB as inputs. Together, NDT and DINE form the overall system that estimates the capacity as shown in Fig 1. The capacity estimation algorithm trains the DINE and NDT models together via an alternating maximization procedure. Namely, we iteratively train each model while keeping the (parameters of the) other one fixed. DINE estimates the communication rate of a fixed NDT input distribution, and the NDT is trained to increase its rate with respect to fixed DINE model. Proceeding until convergence, this results in the capacity estimate, as well as an NDT generative model for the achieving input distribution.
We demonstrate our method on the MA(1)-AGN channel. Both C FF and C FB are estimated using the same algorithm, using the channel as a black-box to solely generate samples. The estimation results are compared with the analytic solution to show the effectiveness of the proposed approach.

II. METHODOLOGY
We give a high-level description of the algorithm and its building blocks. Due to space limitations, full details are reserved to the extended version of this paper. The implementation is available in github. †

A. Directed Information Estimation Method
We propose a new estimator of the DI rate between two correlated stationary processes, termed DINE. Building on [3], we factorize each term in (6) as: where h CE (P, Q) and D KL (P Q) are, respectively, the cross entropy (CE) and KL divergence between P and Q, and P Y is uniform reference measure over the support of the dataset. To simplify notation, we use the shorthands Subtracting both elements in (7) and observing that the difference of CE terms equals the DI at the former time step, we have Note that the difference of KL divergences equals I(X n ; Y n |Y n−1 ). For stationary data processes we take the limit and obtain (10) Each D KL is expanded by its DV representation [4] as: To maximize (11), each DV potential is parametrized by a modified LSTM and expected values are estimated by empirical averages over the dataset D n := {(x i , y i )} n i=1 . Thus, the optimization objectives are: whereỹ n i.i.d. ∼ P Y and T θY , T θ Y X are the parametrized potentials.
The estimator is given by: By universal approximation of RNNs [6] and Breiman's theorem [7], the maximizer of (13) approaches I(X → Y) as the number of samples grows, provided the neural networks are sufficiently expressive.
To capture the time dependencies in D n we introduce a modified LSTM network model for functional approximation. LSTM [5] is an RNN that receives a time series {y i } T i=1 as input and for each i, performs a recursive non-linear transform Algorithm 1 Directed Information Rate Estimation input: Samples of the process D n . output: I Dn (X → Y), estimated directed information rate.
Initialize networks parameters θ Y , θ Y X .
Step 1, Optimization: repeat Feed the network with the examples and compute Step 2, Perfrom a Monte Carlo estimation over D n and subtract loss evaluations to obtain estimation : to calculate its hidden state s i . We denote the LSTM function by F : (y i , s i−1 ) −→ s i . The full characterization of F is provided in [5].
We modify the structure of the LSTM to perform the calculations: A similar modification is introduced for D Y X by substitution of y i with (y i , x i ) and y i with ( y i , x i ), we have: A visualization of a modified LSTM cell (unrolled) is shown in Fig. 2. The LSTM cell's output is the sequence {(s i , s i )} n i=1 , which is fed into a fully-connected layer to obtain T θY and T θ Y X . As demonstrated by Algorithm 1 and Fig. 3, in each iteration we draw D B , a subset on D n , of size B. We feed the NN with D B to acquire T θY , T θ Y X . Those enter the NN loss function (12), and gradients are calculated to update the NN parameters θ Y , θ Y X .
...   Fig. 3. End-to-end architecture for the estimation of D Y (θ Y , Dn). Each batch of time sequences enters the system, a batch of the same size is sampled from the reference measure and those enter the NN to compute T θ Y and T θ Y X .

B. Neural Distribution Transformer
The DINE model is an effective approach to estimate the argument of (2). However, finding the capacity comprises maximization of the DI with respect to the input distribution. For this purpose we present the NDT model that represents a general input distribution of the channel. At each iteration i = 1, . . . , n the NDT maps an i.i.d noise vector N i to a channel input variable X i . When feedback is present the NDT maps (N i , Y i−1 ) −→ X i . Thus, NDT is represented by an RNN with parameters µ as shown in Fig. 4. The NDT model is used to generate the channel input X n , and the DINE estimates the DI between X n and Y n . Fig. 4. The NDT. The noise and past channel output (if feedback is applied) are fed into an NN. The last layer performs normalization to obey the power constraint, if needed.

C. Complete Architecture Layout
Combining DINE and NDT models into a complete system enables capacity estimation. As shown in Fig. 1, the NDT model is fed with i.i.d. noise and its output is the samples X n . These samples are fed into the channel to generate its output. Then, (X n , Y n ) are fed both to the DINE model that outputs I Dn (X → Y). To estimate the capacity, DINE and NDT models are trained together. The training scheme, as shown in Algorithm 2, is a variant of alternated maximization procedure. This procedure iterates between updating the DINE and NDT models parameters sets θ, µ, where each iteration the parameters of one model are fixed and the other ones are updated. By the end of training a long Monte-Carlo evaluation of ∼ 10 6 samples is done in order to estimate the expectations in (12) accurately.
Applying this algorithm to channels with memory estimates their capacity without any specific knowledge of the channel underlying distribution. Next, we demonstrate the effectiveness of this algorithm on continuous alphabet channels.
Step 2: Train NDT Generate B sequences of length T of i.i.d random noise with NDT and channel compute the objective:

III. NUMERICAL RESULTS
We demonstrate the performance of Algorithm 2 on the AWGN channel and the first order MA-AGN channel. The numerical results are then compared with the analytic solution to verify the effectiveness of our method.

A. AWGN channel
The power constrained AWGN channel is investigated as an instance of memoryless continuous alphabet channel for which analytic solution is known. The channel model is given by where Z i ∼ N 0, σ 2 are i.i.d RVs, and X i is the channel input sequence bound to the power constraint E X 2 i ≤ P . Its capacity is given by C = 1 2 log 1 + P σ 2 . In our implementation we chose σ 2 = 1 and estimated the capacity for a range of P values. The numerical results are compared to the analytic solution in Fig. 5

B. Gaussian MA(1) channel
The calculation of capacity of linear Gaussian channels with memory can be divided into two cases, feedback (C FB ) and feed-forward (C FB ) capacity. We will focus on the MA(1) Gaussian channel model, which is given by: ∼ N (0, 1), X i is the channel input sequence bound to the power constraint E X 2 i ≤ P , and Y i is the channel output.

1) Feed-forward capacity:
For the LTI Gaussian channel with input power constraint, C FF can be obtained by applying the water-filing algorithm [14]. We applied Algorithm 2 to estimate C FF and compare with results of the water-filling algorithm. Results are in Fig. 6. 2) Feedback capacity: In general, C FB of the ARMA(k) Gaussian channel can be formulated as a dynamic programming problem, which can be solved by an iterative algorithm [11]. For the particular case of (17), C FB is given by − log(x 0 ), where x 0 is a solution of a 4th order polynomial equation. We applied Algorithm 2 for the feedback capacity to obtain an estimate of C FB . The results and compared with the analytic solution as shown in Fig. 7).

IV. CONCLUSION AND FUTURE WORK
We have presented a methodology to estimate FF and FB capacity using the channel as a "black-box". The estimator is designed by a novel DI estimator (DINE) and NDT model, both based on RNNs. The performance of the estimator are demonstrated on the AWGN and MA(1)-AGN channels, and estimation agrees with the analytic solution.
We wish to further generalize our method of information rate estimation for multi-user communication channels, a field with many unsolved problems and to find theoretical guarantees of the estimator. In addition, information theory (e.g, channel capacity) give us a rigorous mathematical framework where analytical solution are known due to Shannon theory hence this can be a good problem for evaluating machine learning approaches.