# Weighted Spectral Filters for Kernel Interpolation on Spheres: Estimates of
Prediction Accuracy for Noisy Data ††thanks: The corresponding author is S. B.
Lin (). This work was partially supported by the National Key R&D Program of
China (No.2020YFA0713900) and the National Natural Science Foundation of China
[Grant Nos. 62276209].

Xiaotong Liu  Jinxin Wang  Di Wang and Shao-Bo Lin X. Liu, J. Wang, D. Wang
and S. B. Lin are with the Center for Intelligent Decision-Making and Machine
Learning, School of Management, Xi’an Jiaotong University, Xi’an 710049,
China.

remarkRemark hypothesisHypothesis claimClaim Weighted Spectral Filters for
Kernel InterpolationX.Liu, J. Wang, D. Wang and S. B. Lin


###### Abstract

Image classification is central to the big data revolution in medicine.
Improved information processing methods for diagnosis and classification of
digital medical images have shown to be successful via deep learning
approaches. As this field is explored, there are limitations to the
performance of traditional supervised classifiers. This paper outlines an
approach that is different from the current medical image classification tasks
that view the issue as multi-class classification. We performed a hierarchical
classification using our Hierarchical Medical Image classification (HMIC)
approach. HMIC uses stacks of deep learning models to give particular
comprehension at each level of the clinical picture hierarchy. For testing our
performance, we use biopsy of the small bowel images that contain three
categories in the parent level (Celiac Disease, Environmental Enteropathy, and
histologically normal controls). For the child level, Celiac Disease Severity
is classified into 4 classes (I, IIIa, IIIb, and IIIC).

###### keywords:

deep Learning, hierarchical classification, hierarchical medical image
classification, medical imaging

11 6 318 Received: 6 May 2020; Accepted: 10 June 2020; Published: 12 June 2020
yes HMIC: Hierarchical Medical Image Classification, A Deep Learning Approach
Kamran Kowsari1,2,3,*, Rasoul Sali 1, Lubaina Ehsan 4, William Adorno1, Asad
Ali 5, Sean Moore 4, Beatrice Amadi 6, Paul Kelly 6,7, Sana Syed 4,5,8,* and
Donald Brown 1,8,* Kamran Kowsari, Rasoul Sali, Lubaina Ehsan, William Adorno
III, S. Asad Ali, Sean R. Moore, Beatrice C. Amadi, Paul Kelly, Sana Syed and
Donald Brown Correspondence<EMAIL_ADDRESS>(K.K<EMAIL_ADDRESS>(S.S<EMAIL_ADDRESS>(D.B.); Tel.: +1-202-812-3013 (K.K.)

##  1 Introduction and Related Works

Automatic diagnosis of diseases based on medical image categorization has
become increasingly challenging over the last several years Sali et al.
(2019); Kowsari et al. (2019); Kowsari (2020). Areas of research involving
deep learning architectures for image analysis have grown in the past few
years with an increasing interest in their exploration and understanding of
the domain application Kowsari et al. (2019); Litjens et al. (2017); Nobles et
al. (2018); Zhai et al. (2016); Kowsari (2020). Deep learning models achieved
state-of-the-art results in a wide variety of fundamental tasks such as image
classification in the medical domain Hegde et al. (2019); Zhang et al. (2018).
This growth has raised questions regarding classification of sub-types of
disease across a range of disciplines including Cancer (e.g., stage of
cancer), Celiac Disease (e.g., Marsh Score Severity Class), and Chronic Kidney
Disease (e.g., Stage 1–5) among others Pavik et al. (2013). Therefore, it is
important to not just label medical images-based specialized areas, but to
also organize them within an overall field (i.e., name of disease) with the
accompanying sub-field (i.e., sub-type of disease) which we have done in this
paper via Hierarchical Medical Image Classification (HMIC). Hierarchical
models also combat the problem of unbalanced medical image datasets for
training the model and have been successful for other domains Kowsari et al.
(2017); Dumais and Chen (2000).

In the literature, few efforts have been made to leverage the hierarchical
structure of categories. Nevertheless, hierarchical models have shown better
performance compared to flat models in image classification across multiple
domains Yan et al. (2019); Seo and Shin (2019); Ranjan et al. (2018). These
models exploit the hierarchical structure of object categories to decompose
the classification tasks into multiple steps. Yan et al. proposed HD-CNN by
embedding deep CNNs into a category hierarchy Yan et al. (2019). This model
separates easy classes using a coarse category classifier while distinguishing
difficult classes using fine category classifiers. In a CNN, shallow layers
capture low-level features while deeper layers capture high level ones. Zhu
and Bain proposed Branch Convolutional Neural Network (B-CNN) Zhu and Bain
(2017) based on this characteristic of CNNs. This model instead of employing
different classifiers for different levels of class hierarchy, exploits the
hierarchical structure of layers in a CNN and embeds different levels of class
hierarchy on a single CNN. B-CNN outputs multiple predictions ordered from
coarse to fine along concatenated convolutional layers corresponding to
hierarchical structure of the target classes. Sali et al. employed B-CNN model
for the classification of gastrointestinal disorders on histopathological
images Sali et al. (2020).

Our paper uses the HMIC approach for assessment of small bowel enteropathies;
Environmental Enteropathy (EE) versus Celiac Disease (CD) versus
histologically normal controls. EE is a common cause of stunting in Low-to-
Middle Income Countries (LMICs), for which there is no universally accepted,
clear diagnostic algorithms or non-invasive biomarkers for accurate diagnosis
Syed et al. (2016), making this a critical priority Naylor et al. (2015).
Linear growth failure (or stunting) is associated with irreversible physical
and cognitive deficits, with profound developmental implications Syed et al.
(2016). Interestingly, CD, a common cause of stunting in the United States,
with an estimated $1$% prevalence, is an autoimmune disorder caused by a
gluten sensitivity Husby et al. (2012) and has many shared histological
features with EE (such as increased inflammatory cells and villous blunting)
Syed et al. (2016). This resemblance has led to the major challenge of
differentiating clinical biopsy images for these similar but distinct
diseases. CD severity is further assessed via Modified Marsh Score
Classification. It takes into account the architecture of the duodenum as
having finger-like projections (called “villi”) which are lined by cells
called epithelial cells. Between the villi are crevices called crypts that
contain regenerating epithelial cells. Normal villus to crypt ratio is between
3:1 and 5:1 and a healthy duodenum (first part of the small intestine) has no
more than 30 lymphocytes interspersed per 100 epithelial cells within the
villus surface layer (epithelium). Marsh I comprises of normal villus
architecture with an increase in the number of intraepithelial lymphocytes.
Marsh II has increased intraepithelial lymphocytes along with crypt
hypertrophy (crypts appear enlarged). This is usually rare since patients
typically rapidly progress from Marsh I to IIIa. Marsh III is sub-divided into
IIIa (partial villus atrophy), Marsh IIIb (subtotal villus atrophy) and Marsh
IIIc (total villus atrophy) along with crypt hypertrophy and increased intra-
epithelial lymphocytes. Finally, in Marsh IV, villi are completely atrophied
Fasano and Catassi (2001).

The HMIC approach is shown in Figure 1. The parent level is a model trained
based on the parent level of data; EE, CD or Normal. The child level model is
trained for sub-classes of CD based on Modified Marsh Score based on severity;
I, IIIa, IIIb, and IIIc).

The rest of this paper is organized as follows: In Section 2, the different
data sets used in this work, as well as, the required pre-processing steps are
described. The architecture of the model is explained in Section 5. Empirical
results are elaborated in Section 6. Finally, Section 7 concludes the paper
along with outlining future directions.

Figure 1: HMIC: Hierarchical Medical Image Classification

##  2 Data Source

As shown in Table 1, the biopsies were already obtained from 150 children in
this study with a median (interquartile range) age of 37.5 (19.0 to 121.5)
months and a roughly equal sex distribution; $77$ males $(51.3\%)$, and LAZ/
HAZ (Length/ Height-for-Age Z score) of the EE participants were $-2.8$
(inter-quartile range $(IQR):-3.6$ to $-2.3)$ and $-3.1$ (IQR: $-4.1$ to
$-2.2$). LAZ/ HAZ of the Celiac participants were $-0.3$ (IQR: $-0.8$ to 0.7).
and LAZ/ HAZ for Normal were $-0.2$ (IQR: $-1.3$ to 0.5). Duodenal biopsy
samples were developed into $461$ whole-slide biopsy images and labeled as
either Normal, EE, or CD. The biopsy slides for EE patients were collected
from the Aga Khan University Hospital (AKUH) in Karachi, Pakistan ($n=29$
slides from $10$ patients), and the University of Zambia Medical Center in
Lusaka, Zambia ($n=16$). The slides for Normal patients ($n=63$) and CD
($n=34$) were collected from The University of Virginia (UVa). Normal and CD
slides were transformed into a whole-slide at $40\times$ amplification using
the Leica SCN $400$ slide scanner (Meyer Instruments, Houston, TX, USA) at
UVa, and the digitized EE slides of $20\times$ and shared by means of the
Environmental Enteric Dysfunction Biopsy Investigators (EEDBI) Consortium
shared WUPAX server. The patient populace is as per the following:

The median age of ($Q1$, $Q3$) of our whole investigation populace was $37.5$
($19.0$, $121.5$) months, and we had a generally equivalent dispersion of
females ($48$%, $n=49$) and males ($52$%, $n=53$). Most of our examination
populace were histologically Normal controls $(37.7\%)$, followed by CD
patients $(51.8\%)$, and EE patients $(10.05\%)$.

Table 1: Population results of biopsies dataset. | Total Population | Pakistan | Zambia | US
---|---|---|---|---
Data | 150 | EE (n = 10) | EE (n = 16) | Celiac (n = 63) | Normal (n = 61)
| Biopsy
---
Images
461 | 29 | 19 | 239 | 174
| Age, median
---
(IQR), months
| 37.5
---
(19.0 to 121.5)
| 22.2
---
(20.8 to 23.4)
| 16.5
---
(9.5 to 21.0)
| 130.0
---
(85.0 to 176.0)
| 25.0
---
(16.5 to 41.0)
| Gender,
---
n (%)
| M = 77 (%51.3)
---
F = 73 (%48.7)
| M = 5 (%50)
---
F = 5 (%50)
| M = 10 (%62.5)
---
F = 6 (%37.5)
| M = 29 (%46)
---
F = 34 (%54)
| M = 33 (%54)
---
F = 28 (%46)
| LAZ/ HAZ,
---
median (IQR)
| -0.6
---
($-$1.9 to 0.4)
|  $-$2.8
---
($-$3.6 to -2.3)
|  $-$3.1
---
($-$4.1 to$-$2.2)
|  $-$0.3
---
($-$0.8 to 0.7)
| $-0.2$
---
($-1.3$ to 0.5)

$239$ Hematoxylin and eosin (H&E) stained duodenal biopsy samples were
collected from the archived biopsies of $63$ CD patients from the University
of Virginia (UVa) in Charlottesville, VA, United States. The sample were
converted into whole-slide images at 40$\times$ magnification using the Leica
SCN 400 slide scanner (Meyer Instruments, Houston, TX, USA) at the
Biorepository and Tissue Research Facility at UVa. The median age of the UVa
patient populace is $130$ months with interquartile ranges of $85.0$ and
$176.0$ months for $Q1$ and $Q3$, respectively. UVa images had a generally
equivalent circulation of females $(54\%,n=54)$ and male $(46\%,n=29)$. The
biopsy labels for this research were determined by two clinical experts and
approved by a pathologist with considerable authority in gastroenterology. Our
dataset is ranged from Marsh I to IIIc with no biopsy declared as Marsh II.

Based on Table 2, the biopsy images are patched in to 91,899 total images
which contain 32,393 normal patches, 29,308 EE patches, and 30,198 CD patches.
In the child level of the medical biopsy patches, CD contains 4 severities of
disease (Type I, IIIa, IIIb, and IIIc) which has 7125 Type I patches, 6842
Type IIIa patches, $8120$ Type IIIb patches, and 8111 Type IIIb patches. The
training set for normal and EE contains 22,676 and 20,516 patches,
respectively, and for testing 9717 and 8792 patches, respectively. For CD, we
have two sets of training and testing where one belongs to the parent model
and the other belongs to child level. The parent set contains 21,140 patches
for training and 9058 image patches for testing with the common label of CD
for all. In the CD child dataset, we have four severity types of this disease
(I, IIIa, IIIb, and IIIc). Type I of CD contains 4988 patches in the training
set and 2137 patches in the test set. Type IIIa of CD contains 4790 patches in
the training set and 2052 patches in the test set. Type IIIb of CD contains
5684 patches in the training set and 2436 patches in the test set. Finally,
IIIc of CD contains 5678 patches in the training set and 2137 patches in the
test set.

Table 2: Dataset used for Hierarchical Medical Image Classification (HMIC). Data | Train | Test | Total
---|---|---|---
Normal | 22,676 | 9717 | 32,393
Environmental Enteropathy | 20,516 | 8792 | 29,308
Celiac Disease |  | Parent | Child | Parent | Child | Parent | Child
I | 21,140 | 4988 | 9058 | 2137 | 30,198 | 7125
IIIa | 4790 | 2052 | 6842
IIIb | 5684 | 2436 | 8120
IIIc | 5678 | 2433 | 8111

##  3 Pre-Processing

In this section, we explain the entirety of the pre-processing steps which
includes medical image patching, image clustering to remove useless
information, and color balancing to solve the staining problem. The biopsy
images are unstructured, can vary in size, and are often very high resolution
to even consider processing with deep neural systems. Therefore, it becomes
necessary to tile the whole-slide images into smaller image subsets called
patches. Many of the patches created after tiling the whole-slide image will
not contain useful biopsy tissue data. For example, some patches only contain
the white or light-gray background area. In the image clustering section, the
process to select useful images is described. Lastly, color balancing is used
to address staining problems which is a typical issue in histological image
preparation.

###  3.1 Image Patching

Although the effectiveness of CNNs in image classification has been shown in
various studies in different domains, training on high-resolution Whole Slide
Tissue Images (WSI) is not commonly preferred due to a high computational
cost. Applying CNNs on WSI can also lead to losing a large amount of
discriminative data because of severe down-sampling Hou et al. (2016). Due to
cellular level contrasts between Celiac Disease, Environmental Enteropathy,
and Normal cases, an image classification model performed on patches can
perform at least similarly to a WSI-level classifier Hou et al. (2016).For
this study, patches are labeled with the same class as the associated WSI. The
CNN models are trained to predict the presence of disease or disease severity
at the patch-level.

###  3.2 Clustering

As shown in Figure 2, after each biopsy the whole image is divided into
patches; many of these patches are not useful input for a deep image
classification model. These patches tend to contain only connective tissue,
are located on the border region of the tissue, or consist entirely of image
background Kowsari et al. (2019). A two-stage clustering process was applied
to recognize the immaterial patches. For the initial step, a convolutional
autoencoder was used to learn a vectorized representation of features of each
patch and in the second step, we used k-means clustering to assign patches
into two groups: helpful and not useful patches. In Figure 3, the pipeline of
our clustering strategy is depicted which contains both the autoencoder and
_k_ -means clustering.

Figure 2: Pipeline of patching and applying an autoencoder to find useful
patches for the training model. The biopsy images are very large, so we need
to divide into smaller patches to be used in the machine learning model. As
you can see in the image, many of these patches are empty. After using an
autoencoder, we can apply a clustering algorithm to discard useless patches
(green patches contain useful information, while red patches do not). Figure
3: Example autoencoder architecture with K-means applied on the bottle-neck
layer feature vector to cluster useful and not useful patches.

####  3.2.1 Autoencoder

An autoencoder is a form of a neural network that is intended to output a
reconstruction of the model’s input Goodfellow et al. (2016). The autoencoder
has achieved incredible success as a dimensionality reduction technique Wang
et al. (2014). The primary version of the autoencoder was presented by DE.
Rumelhart et al. Rumelhart et al. (1985) in 1985. The fundamental concept is
that one hidden layer acts as a bottle-neck and has far fewer nodes than other
layers in the model Liang et al. (2017). This condensed hidden layer can be
used to represent the important features of the image with a smaller amount of
data. With image inputs, autoencoders can convert the unstructured data into
feature vectors that can be processed through other machine learning methods
such the k-means clustering algorithm.

##### Encode

A CNN-based autoencoder can be isolated into two principle steps Masci et al.
(2011): encoding and interpreting. This condition is:

$\begin{split}O_{m}(i,j)=a\bigg{(}&\sum_{d=1}^{D}\sum_{u=-2k-1}^{2k+1}\sum_{v=-2k-1}^{2k+1}F^{(1)}_{m_{d}}(u,v)I_{d}(i-u,j-v)\bigg{)}\\\
&\quad m=1,\cdots,n\end{split}$ (1)

where $F\in\\{F^{(1)}_{1},F^{(1)}_{2},\ldots,F^{(1)}_{n},\\}$ is a
convolutional filter, with convolution among an input volume defined by
$I=\left\\{I_{1},\ldots,I_{D}\right\\}$ which it learns to represent the input
by combining non-linear functions:

$z_{m}=O_{m}=a(I*F^{(1)}_{m}+b^{(1)}_{m})\quad m=1,\ldots,m$ (2)

where $b^{(1)}_{m}$ is the bias, and the number of zeros we want to pad the
input with is such that: dim(I) = dim(decode(encode(I))). Finally, the
encoding convolution is equal to:

$\begin{split}O_{w}=O_{h}&=(I_{w}+2(2k+1)-2)-(2k+1)+1\\\
&=I_{w}+(2k+1)-1\end{split}$ (3)

#####  3.2.1.1 Decode

The decoding convolution step produces $n$ feature maps $z_{m=1,\ldots,n}$.
The reconstructed results $\hat{I}$ is the result of the convolution between
the volume of feature maps $Z=\\{z_{i=1}\\}^{n}$ and this convolutional
filters volume $F^{(2)}$ Chen et al. (2015); Geng et al. (2015).

$\tilde{I}=a(Z*F^{(2)}_{m}+b^{(2)})$ (4)
$\begin{split}O_{w}=O_{h}&=(I_{w}+(2k+1)-1)-(2k+1)+1=I_{w}=I_{h}\end{split}$
(5)

where Equation (5) shows the decoding convolution with $I$ dimensions. The
input’s dimensions are equal to the output’s dimensions.

####  3.2.2 K-Means

K-means clustering is one of the most popular clustering algorithms Jain
(2010); Gao et al. (2019); Kowsari et al. (2015); Kowsari and Alassaf (2016);
Alassaf et al. (2015) for data in the form
$D\in\\{x_{1},x_{2},\ldots,x_{n}\\}$ in $d$ dimensional vectors for $x\in
f^{d}$. K-means had been applied to perform image and data clustering for
information retrieval Jain (2010); Manning et al. ; Mahajan et al. (2009). The
aim is to identify groups of similar data points and assign each point to one
of the groups. There are many other clustering algorithms, but the k-means
approach works well for this problem, because there are only two clusters and
it is computationally inexpensive compared to other methods.

As an unsupervised approach, one measure of effective clustering is to sum the
distances of each data point from the centroids of the assigned clusters. The
goal of K-means is to minimize $\xi$, the sum of these distances, by
determining optimal centroid locations and cluster assignments. This algorithm
can be difficult to optimize due to the volatility of cluster assignments as
the centroid locations change. Therefore, the K-means algorithm is a greedy-
like approach that iteratively adjusts these locations to solve the
minimization.

Minimize $\xi$ with respect to $A$ and $\mu$ by:

$\displaystyle\xi=\sum_{j=1}^{k}\sum_{x_{i}}||x_{i}-\mu_{j}||^{2}=\sum_{j=1}^{k}\sum_{i=1}^{n}A_{ij}||x_{i}-\mu_{j}||$
(6)

where $x_{i}$ are values from the autoencoder feature representation,
$\mu_{j}$ is the centroid of each cluster, and $A_{ij}$ is the cluster
assignment of each data point $i$ with cluster $j$. $A_{ij}$ can only take on
binary values and each data point can only be assigned to a single cluster.

The centroid $\mu$ of each cluster is calculated as follows:

$\mu(w)=\frac{1}{|w|}\sum_{\bar{x}\in w}\bar{x}$ (7)

Finally, as shown in Figure 4, all patches are assigned into two clusters
which one of them contains useful information and the other one is empty or
does not have medical information. The Algorithms 1 indicates kmeans algorithm
for two clusters medical images.

Figure 4: Some samples of clustering results—cluster 1 includes patches with
useful information and cluster 2 includes patches without useful information
(mostly created from background parts of WSIs) Algorithm 1 K-means algorithm
for 2 clusters medical images

Input:
$D=\\{\overrightarrow{x_{1}},\overrightarrow{x_{2}},\ldots,\overrightarrow{x_{n}}\\}$

Output:  $\mu=\\{\overrightarrow{\mu_{1}},\overrightarrow{\mu_{2}}\\}$

$S=\\{\overrightarrow{s_{1}},\overrightarrow{s_{2}}\\}$ set random seeds
$(\\{\overrightarrow{x_{1}},\overrightarrow{x_{2}},\ldots,\overrightarrow{x_{n}}\\},K)$

for  _$i\leftarrow 1$ to K_ do

$\overrightarrow{\mu_{i}}\leftarrow\overrightarrow{s_{i}}$

endfor

while  _Criterion has not been met_ do

for  _$i\leftarrow 1$ to K=2_ do

$w_{k}\leftarrow\\{\\}$

endfor

for  _$n\leftarrow 1$ to $N$_ do

$j\leftarrow
arg\min_{j^{\prime}}|\overrightarrow{\mu_{j^{\prime}}}-\overrightarrow{\mu_{x_{n}}}|$
$w_{j}\leftarrow w_{j}\bigcup~{}\\{\overrightarrow{x_{n}}\\}$

endfor

for  _$i\leftarrow 1$ to K=2_ do

$\mu_{i}\leftarrow\frac{1}{|w_{i}|}\sum_{\overrightarrow{x}\in
w_{i}}\overrightarrow{x}$

endfor

endwhile

###  3.3 Medical Image Staining

Hematoxylin and eosin (H&E) stains have been used for at least a century and
are still essential for recognizing various tissue types and the morphologic
changes that form the basis of contemporary CD, EE, and cancer diagnosis
Fischer et al. (2008). H&E is used routinely in histopathology laboratories as
it provides the pathologist/researcher a very detailed view of the tissue
Anderson (2011). Color variation has been a very important problem in
histopathology based on light microscopy. A range of factors makes this
problem even more complex such as the use of different scanners, variable
chemical coloring/reactivity from different manufacturers/batches of stains,
coloring being dependent on staining procedure (timing, concentrations, etc.),
and light transmission being a function of section thickness Khan et al.
(2014). Different H&E staining appearances within machine learning inputs can
cause the model to focus only on the broad color variations during training.
For example, if images with a certain label all have a unique stain color
appearance, because they all originated from the same location, the machine
learning model will likely leverage the stain appearance to classify the
images rather than the important medical cellular features.

####  3.3.1 Color Balancing

The idea of color balancing for this study is to convert images in to a
similar color space to represent variations in H&E staining. The images can be
represented with the illuminant spectral power distribution as shown by
$I(\lambda)$, the surface spectral reflectance $S(\lambda)$, and the
$C(\lambda)$ is sensor spectral sensitivities Bianco et al. (2017); Bianco and
Schettini (2014). Using these notations Bianco and Schettini (2014), the
sensor reactions at the pixel with coordinates of $(x,y)$ which can be
presented as:

$p(x,y)=\int_{w}I(x,y,\lambda)S(x,y,\lambda)C(\lambda)d\lambda$ (8)

where $w$ is the wavelength range of the visible light spectrum, p and
$C(\lambda)$ are three-component vectors.

$\displaystyle\left[\begin{array}[]{c}R\\\ G\\\ B\\\
\end{array}\right]_{out}=$
$\displaystyle\left(\alpha\left[\begin{array}[]{c@{\quad}c@{\quad}c}a_{11}&a_{12}&a_{13}\\\
a_{21}&a_{22}&a_{23}\\\ a_{31}&a_{32}&a_{33}\\\
\end{array}\right]\right.{}\times\left.\left[\begin{array}[]{c@{\quad}c@{\quad}c}r_{i}&0&0\\\
0&g_{i}&0\\\ 0&0&b_{i}\\\ \end{array}\right]\left[\begin{array}[]{c}R\\\ G\\\
B\\\ \end{array}\right]_{in}\right)^{\gamma}$ (9)

where $RGB_{in}$ stand for the raw images from medical images, and the
diagonal matrix diag($r_{i},g_{i},b_{i}$) is the channel-independent gain
compensation of the illuminant Bianco and Schettini (2014). In addition,
$RGB_{out}$ is output results that be send to input feature space of CNN
models. $\gamma$ is the gamma correction defined for the RGB color space and
RGBout are the output RGB values. In the following, a more compact version of
Equation (9) is used:

$RGB_{out}=(\alpha AI_{w}.RGB_{in})^{\gamma}$ (10)

where $\alpha$ stand for exposure compensation gain, and the diagonal matrix
for the illuminant compensation shows by $I_{w}$ and the color matrix
transformation is shown by matrix $A$ which is a diagonal matrix for the
illuminant compensation and the color matrix transformation Bianco and
Schettini (2014).

Figure 5 indicates the output results of three classes (CD, EE, and Normal)
for color balancing (CB) with various color balancing percentage in range
between $0.01$ and $50$.

Figure 5: Color Balancing samples for the three classes.

####  3.3.2 Stain Normalization

Histological images can have significant variations in stain appearance that
will cause biases during model training Sali et al. (2019). The variations
occur due to many factors such as contrasts in crude materials and assembling
procedures of stain vendors, staining conventions of labs, and color reactions
to digital scanners Vahadane et al. (2016); Sali et al. (2019). To solve this
problem, the stains of all images are normalized to a single stain appearance.
Different staining normalization approaches have been proposed in research
projects. In this paper, we used the methodology proposed by Vahadane et al.
Vahadane et al. (2016) for the CD severity child-level since all images are
collected from one center. This methodology is designed to preserve the
structure of cellular features of images after stain normalization and
accomplishes stain separation with non-negative matrix factorization. Figure 6
shows an example outputs before and after applying this method on biopsy
patches.

Figure 6: Stain normalization results when using the method proposed by
Vahadane et al. Vahadane et al. (2016). Images in the first row represent the
source images. The source images are normalized images to the stain appearance
of the target image in second row Sali et al. (2019).

##  4 Baseline

###  4.1 Deep Convolutional Neural Networks

A Convolutional Neural Network (CNN) performs hierarchical medical image
classification for each individual image. The original version of the CNN was
built for image processing with an architecture similar to the visual cortex.
In this basic CNN baseline for image processing, an image tensor is convolved
with a set of $d\times d$ kernels size. These convolution layers are called
feature maps and these provide multiple filters which could be stacked on the
input. We used a flat CNN (non-hierarchical CNN) as one of our baselines.

###  4.2 Deep Neural Networks

A Deep Neural Network (DNN) or multilayer perceptron is designed to be trained
by multiple layers of connections. Each individual hidden layer can receive
connection from the previous hidden layers’ nodes and only can provide
connections to the next layer. The input is a connection of flattened feature
space (RGB). The output layer is number of classes for multi-class
classification (six nodes). Our baseline implementation of DNN (multilayer
perceptron) is a discriminative trained model that uses a standard back-
propagation algorithm with sigmoid (Equation (12)) and Rectified Linear Units
(ReLU) Nair and Hinton (2010) (Equation (13)) activation functions. The output
layer for classification task uses the $Softmax$ function due to having multi-
class output as shown in Equation (14).

##  5 Method

In this section, we explain our concept of Deep Convolutional Neural Networks
(CNN) containing the convolutional layers, activation functions, pooling-
layers, and finally, the optimizer. Then, we describe our Deep Convolutional
Neural Networks architecture to diagnose Celiac disease and environmental
enteropathy. As shown in Figure 7, the input layer consists of image patches
with size of ($1000\times 1000$ pixels) and it follows the connection to the
convolutional layer (Conv $1$). Conv $1$ connects to the its following pooling
layer (MaxPooling). The pooling layer is connected to second convolutional
layer Conv $2$. The last convolutional layer (Conv $3$) has been flattened and
connected to a fully connected multi-layer perceptron. The final layer
includes three nodes where each individual node represents one class.

Figure 7: Structure of Convolutional Neural Net using multiple 2D feature
detectors and 2D max-pooling

###  5.1 Convolutional Neural Networks

####  5.1.1 Convolutional Layer

Convolutional Neural Networks are deep learning models that can be used for
the hierarchical classification tasks, especially, image classification
Kowsari et al. (2018). Initially, CNNs were designed for image and computer
vision with a similar design as the visual cortex. CNNs have been used
successfully for clinical image classification. In CNNs, an image tensor is
convolved with set of $d\times d$ kernels. These convolutions (“Feature Maps”)
can be stacked to represent many different features detected by the filters in
that layer. The feature dimensions of output and input networks can be
different Li et al. (2014). The procedure for processing a solitary output of
a matrix is characterized as follows:

$A_{j}=f\left(\sum_{i=1}^{N}I_{i}\ast K_{i,j}+B_{j}\right)$ (11)

Each individual matrix $I_{i}$ is convolved with its corresponding kernel
matrix $K_{i,j}$, and bias of $B_{j}$. Finally, a activation function (non-
linear activation function is explained in Section 5.1.3) is applied to each
individual element Li et al. (2014).

The biases and weights are adjusted to constitute competent feature detection
filters after the back-propagation step during CNN training. The feature map
filters are applied across all three channels Heidarysafa et al. (2018).

####  5.1.2 Pooling Layer

To diminish the computational multifaceted nature, CNNs use pooling layers
which decrease the size of the output layer from its input with one layer then
onto the next in the networks. Distinctive pooling procedures are used to
decrease output while safeguarding significant features Scherer et al. (2010).
The most widely recognized pooling technique is a max-pooling technique where
the largest activation is chosen in the pooling window.

####  5.1.3 Neuron Activation

The CNN is implemented as a discriminative method that uses a back-propagation
algorithm derived from sigmoid (Equation 12), or (Rectified Linear Units
(ReLU) Nair and Hinton (2010) (Equation 13) activation functions. The final
layer contains one node with sigmoid activation function for binary
classification multiple nodes for each class and a $Softmax$ activation
function for multi-class problems (as demonstrated in Equation (14)).

$\displaystyle f(x)$ $\displaystyle=\frac{1}{1+e^{-x}}\in(0,1)$ (12)
$\displaystyle f(x)$ $\displaystyle=\max(0,x)$ (13)
$\displaystyle\sigma(z)_{j}$
$\displaystyle=\frac{e^{z_{j}}}{\sum_{k=1}^{K}e^{z_{k}}}$ (14)
$\displaystyle\forall~{}j\in\\{1,\ldots,K\\}$

####  5.1.4 Optimizer

For our CNN architecture, we use the $Adam$ optimizer Kingma and Ba (2014).
This is a stochastic gradient descent that uses the norm of the initial two
moments of gradient ($v$ and $m$, appeared in Equations (15)–(18)). It can
deal with non-stationarity of the target in a similar fashion to RMSProp,
while defeating the sparse gradient problem constraint of RMSProp Kingma and
Ba (2014).

$\theta\leftarrow\theta-\frac{\alpha}{\sqrt{\hat{v}}+\epsilon}\hat{m}$ (15)
$g_{i,t}=\nabla_{\theta}J(\theta_{i},x_{i},y_{i})$ (16)
$m_{t}=\beta_{1}m_{t-1}+(1-\beta_{1})g_{i,t}$ (17)
$m_{t}=\beta_{2}v_{t-1}+(1-\beta_{2})g_{i,t}^{2}$ (18)

where $m_{t}$ is the first moment and $v_{t}$ indicates second moment that
both are estimated. $\hat{m_{t}}=\frac{m_{t}}{1-\beta_{1}^{t}}$ and
$\hat{v_{t}}=\frac{v_{t}}{1-\beta_{2}^{t}}$.

####  5.1.5 Network Architecture

As demonstrated in Figure 7, our implementation contains three convolutional
layers with each followed by a pooling layer (Max-Pooling). This method with
three channel input image patches with size a of $(1000\times 1000$ pixels).
The first convolutional layer has $32$ filters with kernel size of $(3,3)$.
Then, a pooling layer is connected with size of $(5,5)$ to reduce feature maps
from $(1000\times 1000)$ to $(200\times 200)$. The next convolutional layer
includes $32$ filters with $(3,3)$ kernel. Then, a $2D$ MaxPooling layer is
connected to scales down the feature space from $(200\times 200)$ to
$(40\times 40)$. The final convolutional layers contain $64$ filters that
kernel size is $(3,3)$. This convolutional layer is connected to a $2D$
MaxPooling to scale down by $(8\times 8)$. The feature map is flattened, and a
fully connected layers is connected to our CNN with $128$ nodes. The output
layer has $3$ nodes that represent our parent classes: (Environmental
Enteropathy, Celiac Disease, and Normal). The child level of this model as
shown on the bottom of Figure 7, is similar to parent level with significant
difference which is that the output layer has $4$ nodes that represent our
child classes: (I, IIIa, IIIb, and IIIc).

The Adam (See Section 5.1.4) optimizer is used with a learning rate of
$0.001$, $\beta_{1}=0.9$, and $\beta_{2}=0.999$. The loss function is sparse
categorical crossentropy Chollet et al. (2015). Also, for all layers, we use a
Rectified linear unit (ReLU) as the activation function except for the output
layer which used a $Softmax$ (See Section 5.1.3). In this technique, we use
dropout in each individual layer to address over-fitting problem Srivastava et
al. (2014)

###  5.2 Whole Slide Classification

The objective of this study was to group WSIs dependent on the diagnosis of CD
and EE, and CD severity on child-level by means of the adjusted Marsh score.
The model was used by training it on the patch-level and is extended to WSI.
To accomplish this objective, a heuristic strategy was created which
aggregated crop classifications and translated them to whole-slide inferences.
Each WSI in the test set was at firstly patched, those patches which did not
contain any useful information were filtered out, and then stain methods were
performed on the patches (color balancing applied on parent level and stain
normalization applied for CD severity ). After these pre-processing steps, our
prepared model was applied with the objective of image classification. We
meant the likelihood dissemination over potential marks, given the patches
images $x$ and training set $D$ by $p(y|x,D)$. Finally, this classification
produces a vector of length $C$, where $C$ is the number of classes. In our
documentation, the likelihood is contingent on the test patch $x$, just as,
the training set $D$. The trained model predicts a vector of probabilities
(three for parent-level and four for child-level) that represents the
likelihood an image belongs in each class. Given a probabilistic result, the
patch $j$ in slide $i$ is assigned to the most likely class label
$\hat{y}_{ij}$ as shown in Equation (19).

$\hat{y}_{ij}=\operatorname*{arg\,max}_{c\in\\{1,2,3,\ldots,C\\}}p(y_{ij}=c|x_{ij},D)$
(19)

where $\hat{y}$ stands for maximum a posteriori (MAP). The summation over
these vectors (output vector of all patches for a single WSI) and normalizing
the resultant vector made a vector that had parts demonstrating the likelihood
of a vector with three elements (CD, EE, and N) seriousness for the related
WSI. Equation (20), shows how the class of WSI was anticipated.

$\hat{y}_{i}=\operatorname*{arg\,max}_{c\in\\{1,2,3,\ldots,C\\}}\sum_{j=1}^{N_{i}}p(y_{ij}=c|x_{ij},D)$
(20)

where the number of patches in slide $i$ is shown by $N_{i}$.

###  5.3 Hierarchical Medical Image Classification

The main contribution of this paper is a hierarchical medical image
classification of biopsies. A common multi-class algorithm is functional and
efficient for a limited number of categories. However, performance drops when
we have an unequal number of data-points in our classes. In our deep learning
models with various levels, this issue has been solved by creating a
hierarchical structure that makes deep learning approaches for their levels of
the clinical hierarchy (e.g., see Figure 7).

##  6 Results

In this section, we have two main results: empirical results and
visualizations for patches. The empirical results are mostly used for
comparing our accuracy with our baseline.

###  6.1 Evaluation Setup

In the computer science community, shareable and commensurate performance
measures to assess an algorithm are desirable. However, in real projects, such
measures may only exist for a few methods. The extensive problem when
assessing the medical image categorization model is the absence of standard
data collection agreement. Even if a commonplace method existed, simply
choosing disparate training and test sets can introduce divergencies in model
achievement Yang (1999). Performance measures widely evaluate specific aspects
of image classification. In this section, we explain different performance
measures and metrics that are used in this research paper. These metrics have
been calculated from a “confusion matrix” that comprises false negatives (FN)
true negatives (TN), true positives (TP), and false positives (FP) Lever et
al. (2016). The importance of these four measures may shift depending on the
application. The fraction of all correctly predicted over all number of test
set samples is the overall accuracy (Equation (21)). The fraction of correctly
predicted over all positives is called precision, i.e., positive predictive
value (Equation (22)).

$accuracy=\frac{(TP+TN)}{(TP+FP+FN+TN)}$ (21)
$Precision=\frac{\sum_{l=1}^{L}TP_{l}}{\sum_{l=1}^{L}TP_{l}+FP_{l}}$ (22)
$Recall=\frac{\sum_{l=1}^{L}TP_{l}}{\sum_{l=1}^{L}TP_{l}+FN_{l}}$ (23)
$F1Score=\frac{\sum_{l=1}^{L}2TP_{l}}{\sum_{l=1}^{L}2TP_{l}+FP_{l}+FN_{l}}$
(24)

###  6.2 Experimental Setup

The following results were obtained using a combination of central processing
units (CPUs) and graphical processing units (GPUs). The processing was done on
a $Core~{}i7-9700F$ with $8$ cores and $128GB$ memory, and the GPU cards were
two $Nvidia~{}GeForce~{}RTX~{}2080Ti$. We implemented our approaches in Python
using the Compute Unified Device Architecture (CUDA), which is a parallel
computing platform and Application Programming Interface (API) model created
by $Nvidia$. We also used Keras and TensorFlow libraries for creating the
neural networks Abadi et al. (2016); Chollet et al. (2015).

###  6.3 Empirical Results

In this sub-section, as we discussed in Section 6.1, we report precision,
recall, and F1-score.

Table 3 shows the results of the parent level model trained for classifying
between Normal, Environmental Enteropathy (EE) and Celiac Disease (CD). The
precision of normal patches is $89.97\pm 0.5973$ and recall is $89.35\pm
0.6133$. The F1-score of normal is $89.66\pm 0.6054$. For EE, precision is
$94.02\pm 0.4955$, recall is $97.30\pm 0.3385$, F1-score is $95.63\pm 0.4270$.
The CD evaluation measure for the parent level is as follows: precision is
equal to $91.12\pm 0.3208$, recall is equal to $88.71\pm 0.3569$, and F1-score
is equal to $89.90\pm 1.2778$.

Table 3: Result of parent level classifications for normal, environmental enteropathy, and Celiac disease. | Precision | Recall | F1-Score
---|---|---|---
Normal | 89.97 $\pm$ 0.59 | 89.35 $\pm$ 0.61 | 89.66 $\pm$ 0.60
Environmental Enteropathy | 94.02 $\pm$ 0.49 | 97.30 $\pm$ 0.33 | 95.63 $\pm$ 0.42
Celiac Disease | 91.12 $\pm$ 0.32 | 88.71 $\pm$ 0.35 | 89.90 $\pm$ 1.27

Table 4 shows the comparison of our techniques with three different baselines.
The baseline results from Convolutional Neural Network (CNN), Deep Neural
Network (Multilayer perceptron), and Deep Convolutional Neural Network (DCNN)
are using in this results section. Much research has been done in this domain
such as ResNet, but these novel techniques can only handle small images such
as $250\times 250$. In this dataset, we create $1000$ patches, so we could not
compare our work with ResNet, AlexNet, etc. Regarding precision, the highest
is HMIC whole-slide with a mean of $88.01$ percent and a confidence interval
of $0.3841$ followed by HMIC none whole-slide $84.13$ percent and confidence
interval of $0.3751$. The precision of CNN is $76.76\pm 0.4985$, multilayer
perceptron is $76.19\pm 0.5030$, and DCNN is $82.95\pm 0.4439$. Regarding
recall, the highest is HMIC whole-slide with a mean of $93.98$ percent and a
confidence interval of $0.2811$ followed by HMIC non whole-slide at $93.56$
percent and confidence interval of $0.29.1$. The recall of CNN is $80.18\pm
0.4706$, multilayer perceptron is $79.4\pm 0.471$, and DCNN is $87.28\pm
0.3933$. The highest F1-score is HMIC whole-slide with a mean of $90.89$
percent and a confidence interval of $0.3804$ followed by HMIC non whole-slide
with $88.61$ percent and confidence interval of $0.3751$. The recall of CNN is
$78.43\pm 0.4855$, multilayer perceptron is $77.76\pm 0.4911$, and DCNN is
$85.06\pm 0.4207$.

Table 4: Results of HMIC with comparison with our baseline Model | Precision | Recall | F1-Score
---|---|---|---
Baseline | CNN | 76.76 $\pm$ 0.49 | 80.18 $\pm$ 0.47 | 78.43 $\pm$ 0.48
Multilayer perceptron | 76.19 $\pm$ 0.50 | 79.40 $\pm$ 0.47 | 77.76 $\pm$ 0.49
Deep CNN | 82.95 $\pm$ 0.44 | 87.28 $\pm$ 0.39 | 85.06 $\pm$ 0.42
HMIC | Non Whole slide | 84.13 $\pm$ 0.37 | 93.56 $\pm$ 0.29 | 88.61 $\pm$ 0.37
Whole slide | 88.01 $\pm$ 0.38 | 93.98 $\pm$ 0.28 | 90.89 $\pm$ 0.38

Table 5 shows the results by each class. For Normal images, the best
classifier is DCNN with $95.14\pm 0.42$ recall of $94.91\pm 0.43$ F1-score of
$95.14\pm 0.42$. For EE, HMIC is the best classifier. The whole-slide images
classifier for parent level is more robust in comparison with non -whole slide
with precision of $94.08\pm 0.49$ Recall of $97.33\pm 0.42$ F1-score of
$98.68\pm 0.42$. Although the results of Normal and EE Images are very similar
to flat models such as DCNN, but the results of sub-class of CD contains 4
different stages and the margin is very high. The best flat model (non-
hierarchical) is DCNN with mean of F1-score of 73.99 for I, 71.63 for IIIa,
77.74 for IIIb, and 75.71 IIIc.

The Table 5 indicates the margin for child level is very high even for the non
whole-slide level of this dataset. The best results belong to the whole-slide
classifier for parent level with precision with $88.73\pm 1.34$ for I,
$81.19\pm 1.65$ for IIIa, $90.51\pm 1.24$ for IIIb, $89.26\pm 1.31$ for IIIc.
The whole-slide classifier for parent level with recall with $85.07\pm 1.51$
for I, $81.19\pm 1.65$ for IIIa, $90.48\pm 1.27$ for IIIb, $90.18\pm 1.26$ for
IIIc. The results of whole-slide classifier for parent level for recall is
$85.07\pm 1.51$ for I, $83.72\pm 0.78$ for IIIa, $90.48\pm 0.61$ for IIIb,
$90.18\pm 1.26$ for IIIc. Finally, The F1-score for whole-slide classifier for
parent level is equal to $86.86\pm 1.43$ for I, $82.44\pm 1.51$ for IIIa,
$90.49\pm 1.16$ for IIIb, $89.72\pm 1.28$.

Table 5: Results per-classed of HMIC with comparison with our baseline. Model |  | Precision | Recall | F1-Score
---|---|---|---|---
Baseline | CNN | Normal | 87.83 $\pm$ 0.57 | 90.77 $\pm$ 0.65 | 89.28 $\pm$ 0.61
Environmental Enteropathy | 90.93 $\pm$ 0.61 | 82.48 $\pm$ 0.79 | 86.50 $\pm$ 0.71
Celiac Disease | I | 68.37 $\pm$ 1.98 | 68.62 $\pm$ 1.96 | 68.50 $\pm$ 1.96
IIIa | 56.26 $\pm$ 1.01 | 56.26 $\pm$ 2.21 | 59.29 $\pm$ 1.95
IIIb | 65.28 $\pm$ 0.97 | 98.28 $\pm$ 2.01 | 66.64 $\pm$ 1.87
IIIc | 62.66 $\pm$ 1.99 | 66.83 $\pm$ 1.99 | 64.68 $\pm$ 2.02
Multilayer perceptron | Normal | 87.97 $\pm$ 0.76 | 81.87 $\pm$ 0.76 | 84.81 $\pm$ 0.71
Environmental Enteropathy | 87.25 $\pm$ 0.69 | 90.18 $\pm$ 0.62 | 88.69 $\pm$ 0.66
Celiac Disease | I | 57.92 $\pm$ 2.07 | 60.74 $\pm$ 2.07 | 59.30 $\pm$ 2.09
IIIa | 62.58 $\pm$ 2.09 | 62.18 $\pm$ 2.09 | 60.89 $\pm$ 2.11
IIIb | 65.00 $\pm$ 1.89 | 66.09 $\pm$ 1.87 | 65.56 $\pm$ 1.88
IIIc | 67.97 $\pm$ 1.85 | 74.85 $\pm$ 1.72 | 71.24 $\pm$ 1.78
DCNN | Normal | 95.14 $\pm$ 0.42 | 94.91 $\pm$ 0.43 | 95.14 $\pm$ 0.42
Environmental Enteropathy | 92.22 $\pm$ 0.55 | 90.62 $\pm$ 0.60 | 91.52 $\pm$ 0.58
Celiac Disease | I | 75.41 $\pm$ 1.82 | 72.63 $\pm$ 1.89 | 73.99 $\pm$ 1.85
IIIa | 70.81 $\pm$ 1.92 | 72.47 $\pm$ 1.93 | 71.63 $\pm$ 1.79
IIIb | 81.08 $\pm$ 0.81 | 74.67 $\pm$ 1.84 | 77.74 $\pm$ 1.65
IIIc | 75.07 $\pm$ 1.83 | 76.37 $\pm$ 1.81 | 75.71 $\pm$ 1.81
HMIC | Non Whole Slide | Normal | 89.97 $\pm$ 0.59 | 89.35 $\pm$ 0.61 | 89.66 $\pm$ 0.61
Environmental Enteropathy | 94.02 $\pm$ 0.49 | 97.30 $\pm$ 0.33 | 95.63 $\pm$ 0.33
Celiac Disease | I | 83.25 $\pm$ 1.58 | 80.91 $\pm$ 1.66 | 82.06 $\pm$ 1.62
IIIa | 80.34 $\pm$ 1.62 | 80.46 $\pm$ 1.71 | 80.40 $\pm$ 1.57
IIIb | 85.35 $\pm$ 1.49 | 81.77 $\pm$ 1.67 | 83.52 $\pm$ 1.47
IIIc | 85.54 $\pm$ 1.49 | 82.71 $\pm$ 1.60 | 84.10 $\pm$ 1.55
Whole Slide | Normal | 90.64 $\pm$ 0.57 | 90.06 $\pm$ 0.57 | 90.35 $\pm$ 0.58
Environmental Enteropathy | 94.08 $\pm$ 0.49 | 97.33 $\pm$ 0.42 | 98.68 $\pm$ 0.42
Celiac Disease | I | 88.73 $\pm$ 1.34 | 85.07 $\pm$ 1.51 | 86.86 $\pm$ 1.43
IIIa | 81.19 $\pm$ 1.65 | 81.19 $\pm$ 1.65 | 82.44 $\pm$ 1.51
IIIb | 90.51 $\pm$ 1.24 | 90.48 $\pm$ 1.27 | 90.49 $\pm$ 1.16
IIIc | 89.26 $\pm$ 1.31 | 90.18 $\pm$ 1.26 | 89.72 $\pm$ 1.28

###  6.4 Visualization

Grad-CAMs were generated for 41 patches (18 EE, 14 Celiac Disease, and 9
histologically normal duodenal controls) which mainly focused on distinct, yet
medically relevant cellular features outlined below. Although, most heatmaps
focused on medically relevant features, there were some patches that focused
on too many features (n = 8) or focused on connective tissue debris (n = 10)
that we were unable to categorize.
As shown in Figure 8, three categories are describe as follows:

  * •

EE: surface epithelium with IELs and goblet cells was highlighted. Within the
lamina propria, the heatmaps also focused on mononuclear cells.

  * •

CD: heatmaps highlighted the edge of crypt cross sections, surface epithelium
with IELs and goblet cells, and areas with mononuclear cells within the lamina
propria.

  * •

Histologically Normal: surface epithelium with epithelial cells containing
abundant cytoplasm was highlighted.

Figure 8: Grad-CAM results for showing feature importance.

##  7 Conclusions

Medical image classification is a significant problem to address, given the
growing number of medical instruments to collect digital images. When medical
images are organized hierarchically, multi-class approaches are difficult to
apply using traditional supervised learning methods. This paper introduces a
novel approach to hierarchical medical image classification, HMIC, that could
use multiple deep convolutional neural networks approaches to produce
hierarchical classifications, and in our experimental results, we use two
level of CNNs hierarchy. Testing on a medical image data set shows that this
technique produced robust results at the higher and lower level, and the
accuracy is consistently higher than those obtainable by conventional
approaches using CNN, Multi-layer perceptron, and DCNN. These results show
that hierarchical deep learning method could provide improvements for
classification and that they provide flexibility to classify these data within
a hierarchy. Hence, they provide extensions over current and traditional
methods that only consider the multi-class problem.

This modeling approach can be extended in a couple of ways. Additional
training and testing with other hierarchically structured clinical data will
help to identify other architectures that work better for these problems.
Also, deeper levels of hierarchy is another possible extension of this
approach. For instance, if the stage of the disease is treated as ordered then
the hierarchy continues down multiple levels. Scoring here could be performed
on small sets using human judges.

K.K., S.S., and DB worked on the Concept and design of the platform. K.K.
worked on the implementation of these models. K.K., S.S. , and L.E. worked on
the analysis and interpretation of data. K.K. worked on the drafting of the
manuscript. K.K., R.S. , and W.A. worked on the critical revision of the
manuscript for important intellectual content. D.B , S.S. , B.A. , S.M. and
A.A. obtained funding. This work was under the supervision of S.S., P.K.,
A.A., S.M., and D.B. All authors have read and agreed to the published version
of the manuscript.

This research was supported by University of Virginia, Engineering in Medicine
SEED Grant $(SS~{}\&~{}DEB)$, the University of Virginia Translational Health
Research Institute of Virginia ($THRIV$) Mentored Career Development Award
$(SS)$, and the Bill and Melinda Gates Foundation (AA, OPP1138727; SRM,
OPP1144149; PK, OPP1066118. Research reported in this publication was
supported by [National Institute of Diabetes and Digestive and Kidney
Diseases] of the National Institutes of Health under award number K23
DK117061-01A1. The content is solely the responsibility of the authors and
does not necessarily represent the official views of the National Institutes
of Health.

The authors declare no conflict of interest. The funding sponsors had no role
in the design of the study; in the collection, analyses or interpretation of
data; in the writing of the manuscript; nor in the decision to publish the
results.

References

## References

  * Sali et al. (2019) Sali, R.; Ehsan, L.; Kowsari, K.; Khan, M.; Moskaluk, C.A.; Syed, S.; Brown, D.E.  CeliacNet: Celiac Disease Severity Diagnosis on Duodenal Histopathological Images Using Deep Residual Networks.  arXiv 2019, arXiv:1910.03084.
  * Kowsari et al. (2019) Kowsari, K.; Sali, R.; Khan, M.N.; Adorno, W.; Ali, S.A.; Moore, S.R.; Amadi, B.C.; Kelly, P.; Syed, S.; Brown, D.E.  Diagnosis of celiac disease and environmental enteropathy on biopsy images using color balancing on convolutional neural networks.  Im _Proceedings of the Future Technologies Conference_ ; Springer: Cham, Switzerland, 2019; pp. 750–765.
  * Kowsari (2020) Kowsari, K.  Diagnosis and Analysis of Celiac Disease and Environmental Enteropathy on Biopsy Images using Deep Learning Approaches.  Ph.D. Thesis, University of California, Los Angeles, CA, USA, 2020;  doi:black10.18130/v3-837s-3a79.
  * Kowsari et al. (2019) Kowsari, K.; Jafari Meimandi, K.; Heidarysafa, M.; Mendu, S.; Barnes, L.; Brown, D.  Text Classification Algorithms: A Survey.  Information 2019, 10, 150.  doi:black10.3390/info10040150.
  * Litjens et al. (2017) Litjens, G.; Kooi, T.; Bejnordi, B.E.; Setio, A.A.A.; Ciompi, F.; Ghafoorian, M.; Van Der Laak, J.A.; Van Ginneken, B.; Sánchez, C.I.  A survey on deep learning in medical image analysis.  Med. Image Anal. 2017, 42, 60–88.
  * Nobles et al. (2018) Nobles, A.L.; Glenn, J.J.; Kowsari, K.; Teachman, B.A.; Barnes, L.E.  Identification of imminent suicide risk among young adults using text messages.  In Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems, Montreal, QC, Canada, 21–26 April 2018; ACM: New York, NY, USA, 2018, p. 413.
  * Zhai et al. (2016) Zhai, S.; Cheng, Y.; Zhang, Z.M.; Lu, W.  Doubly convolutional neural networks.  In Proceedings of the Advances in Neural Information Processing Systems; Barcelona, Spain, 5–10 December 2016; pp. 1082–1090.
  * Hegde et al. (2019) Hegde, R.B.; Prasad, K.; Hebbar, H.; Singh, B.M.K.  Comparison of traditional image processing and deep learning approaches for classification of white blood cells in peripheral blood smear images.  Biocybern. Biomed. Eng. 2019, _39_ , 382–392.
  * Zhang et al. (2018) Zhang, J.; Kowsari, K.; Harrison, J.H.; Lobo, J.M.; Barnes, L.E.  Patient2Vec: A Personalized Interpretable Deep Representation of the Longitudinal Electronic Health Record.  IEEE Access 2018, 6, 65333–65346.
  * Pavik et al. (2013) Pavik, I.; Jaeger, P.; Ebner, L.; Wagner, C.A.; Petzold, K.; Spichtig, D.; Poster, D.; Wüthrich, R.P.; Russmann, S.; Serra, A.L.  Secreted Klotho and FGF23 in chronic kidney disease Stage 1 to 5: a sequence suggested from a cross-sectional study.  Nephrol. Dial. Transplant. 2013, 28, 352–359.
  * Kowsari et al. (2017) Kowsari, K.; Brown, D.E.; Heidarysafa, M.; Meimandi, K.J.; Gerber, M.S.; Barnes, L.E.  Hdltex: Hierarchical deep learning for text classification.  In Proceedings of the 2017 16th IEEE International Conference on Machine Learning and Applications (ICMLA), Cancun, Mexico, 18–21 December 2017; pp. 364–371.
  * Dumais and Chen (2000) Dumais, S.; Chen, H.  Hierarchical classification of web content.  In Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Athens, Greece, 24–28 July 2000; pp. 256–263.
  * Yan et al. (2019) Yan, Z.; Piramuthu, R.; Jagadeesh, V.; Di, W.; Decoste, D.  Hierarchical Deep Convolutional Neural Network for Image Classification.  U.S. Patent 10,387,773, 20 August 2019.
  * Seo and Shin (2019) Seo, Y.; Shin, K.S.  Hierarchical convolutional neural networks for fashion image classification.  Expert Syst. Appl. 2019, 116, 328–339.
  * Ranjan et al. (2018) Ranjan, N.; Machingal, P.V.; Jammalmadka, S.S.D.; Thenaknidiyoor, V.; Dileep, A.  Hierarchical Approach for Breast cancer Histopathology Images Classification. 2018. Available online: https://openreview.net/forum?id=rJlGvTojG (accessed on 10 January 2019).
  * Zhu and Bain (2017) Zhu, X.; Bain, M.  B-CNN: branch convolutional neural network for hierarchical classification.  arXiv 2017, arXiv:1709.09890.
  * Sali et al. (2020) Sali, R.; Adewole, S.; Ehsan, L.; Denson, L.A.; Kelly, P.; Amadi, B.C.; Holtz, L.; Ali, S.A.; Moore, S.R.; Syed, S.; et al.  Hierarchical Deep Convolutional Neural Networks for Multi-category Diagnosis of Gastrointestinal Disorders on Histopathological Images.  arXiv 2020, arXiv:2005.03868.
  * Syed et al. (2016) Syed, S.; Ali, A.; Duggan, C.  Environmental enteric dysfunction in children: A review.  J. Pediatr. Gastroenterol. Nutr. 2016, 63, 6.
  * Naylor et al. (2015) Naylor, C.; Lu, M.; Haque, R.; Mondal, D.; Buonomo, E.; Nayak, U.; Mychaleckyj, J.C.; Kirkpatrick, B.; Colgate, R.; Carmolli, M.; et al.  Environmental enteropathy, oral vaccine failure and growth faltering in infants in Bangladesh.  EBioMedicine 2015, 2, 1759–1766.
  * Husby et al. (2012) Husby, S.; others.  European Society for Pediatric Gastroenterology, Hepatology, and Nutrition guidelines for the diagnosis of coeliac disease.  J. Pediatr. Gastroenterol. Nutr. 2012, 54, 136–160.
  * Fasano and Catassi (2001) Fasano, A.; Catassi, C.  Current approaches to diagnosis and treatment of celiac disease: An evolving spectrum.  Gastroenterology 2001, 120, 636–651.
  * Hou et al. (2016) Hou, L.; Samaras, D.; Kurc, T.M.; Gao, Y.; Davis, J.E.; Saltz, J.H.  Patch-based convolutional neural network for whole slide tissue image classification.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Las Vegas, NV, USA, 27–30 June 2016; pp. 2424–2433.
  * Goodfellow et al. (2016) Goodfellow, I.; Bengio, Y.; Courville, A.; Bengio, Y.  Deep Learning; MIT Press: Cambridge, MA, USA, 2016; Volume 1.
  * Wang et al. (2014) Wang, W.; Huang, Y.; Wang, Y.; Wang, L.  Generalized autoencoder: A neural network framework for dimensionality reduction.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, Columbus, OH, USA, 23–28 June 2014; pp. 490–497.
  * Rumelhart et al. (1985) Rumelhart, D.E.; Hinton, G.E.; Williams, R.J.  _Learning Internal Representations by Error Propagation_ ;  Technical Report; California Univ San Diego La Jolla Inst for Cognitive Science: La Jolla, CA, USA, 1985.
  * Liang et al. (2017) Liang, H.; Sun, X.; Sun, Y.; Gao, Y.  Text feature extraction based on deep learning: A review.  EURASIP J. Wirel. Commun. Netw. 2017, 2017, 211.
  * Masci et al. (2011) Masci, J.; Meier, U.; Cireşan, D.; Schmidhuber, J.  Stacked convolutional auto-encoders for hierarchical feature extraction.  In _International Conference on Artificial Neural Networks_ ; Springer: Berlin/Heidelberg, Germany, 2011; pp. 52–59.
  * Chen et al. (2015) Chen, K.; Seuret, M.; Liwicki, M.; Hennebert, J.; Ingold, R.  Page segmentation of historical document images with convolutional autoencoders.  In _Proceedings of the 2015 13th International Conference on Document Analysis and Recognition (ICDAR)_ ; IEEE: Washington, DC, USA, 2015; pp. 1011–1015.
  * Geng et al. (2015) Geng, J.; Fan, J.; Wang, H.; Ma, X.; Li, B.; Chen, F.  High-resolution SAR image classification via deep convolutional autoencoders.  IEEE Geosci. Remote. Sens. Lett. 2015, 12, 2351–2355.
  * Jain (2010) Jain, A.K.  Data clustering: 50 years beyond K-means.  Pattern Recognit. Lett. 2010, 31, 651–666.
  * Gao et al. (2019) Gao, Q.; Xu, H.X.; Han, H.G.; Guo, M.  Soft-sensor Method for Surface Water Qualities Based on Fuzzy Neural Network.  In Proceedings of the 2019 Chinese Control Conference (CCC), Guangzhou, China, 27–30 July 2019; pp. 6877–6881.
  * Kowsari et al. (2015) Kowsari, K.; Yammahi, M.; Bari, N.; Vichr, R.; Alsaby, F.; Berkovich, S.Y.  Construction of fuzzyfind dictionary using golay coding transformation for searching applications.  arXiv 2015, arXiv:1503.06483.
  * Kowsari and Alassaf (2016) Kowsari, K.; Alassaf, M.H.  Weighted unsupervised learning for 3d object detection.  arXiv 2016, arXiv:1602.05920.
  * Alassaf et al. (2015) Alassaf, M.H.; Kowsari, K.; Hahn, J.K.  Automatic, real time, unsupervised spatio-temporal 3d object detection using rgb-d cameras.  In Proceedings of the 2015 19th International Conference on Information Visualisation, Barcelona, Spain, 22–24 July 2015; pp. 444–449.
  * (35) Manning, C.D.; Raghavan, P.; Schutze, H.  _Introduction to Information Retrieval_ ; Cambridge University Press: Cambridge, UK, 2008; Volume 20, pp. 405–416.
  * Mahajan et al. (2009) Mahajan, M.; Nimbhorkar, P.; Varadarajan, K.  The Planar k-Means Problem is NP-Hard.  In _WALCOM: Algorithms and Computation_ ; Das, S., Uehara, R., Eds.; Springer: Berlin/Heidelberg, Germany, 2009; pp. 274–285.
  * Fischer et al. (2008) Fischer, A.H.; Jacobson, K.A.; Rose, J.; Zeller, R.  Hematoxylin and eosin staining of tissue and cell sections.  Cold Spring Harb. Protoc. 2008, 2008, pdb–prot4986.
  * Anderson (2011) Anderson, J.  An introduction to Routine and special staining.  Retrieved August 2011, 18, 2014.
  * Khan et al. (2014) Khan, A.M.; Rajpoot, N.; Treanor, D.; Magee, D.  A nonlinear mapping approach to stain normalization in digital histopathology images using image-specific color deconvolution.  IEEE Trans. Biomed. Eng. 2014, 61, 1729–1738.
  * Bianco et al. (2017) Bianco, S.; Cusano, C.; Napoletano, P.; Schettini, R.  Improving CNN-Based Texture Classification by Color Balancing.  J. Imaging 2017, 3, 33.
  * Bianco and Schettini (2014) Bianco, S.; Schettini, R.  Error-tolerant color rendering for digital cameras.  J. Math. Imaging Vis. 2014, 50, 235–245.
  * Vahadane et al. (2016) Vahadane, A.; Peng, T.; Sethi, A.; Albarqouni, S.; Wang, L.; Baust, M.; Steiger, K.; Schlitter, A.M.; Esposito, I.; Navab, N.  Structure-preserving color normalization and sparse stain separation for histological images.  IEEE Trans. Med Imaging 2016, 35, 1962–1971.
  * Nair and Hinton (2010) Nair, V.; Hinton, G.E.  Rectified linear units improve restricted boltzmann machines.  In Proceedings of the 27th International Conference on Machine Learning (ICML-10), Haifa, Israel, 21–24 June 2010; pp. 807–814.
  * Kowsari et al. (2018) Kowsari, K.; Heidarysafa, M.; Brown, D.E.; Meimandi, K.J.; Barnes, L.E.  Rmdl: Random multimodel deep learning for classification.  In Proceedings of the 2nd International Conference on Information System and Data Mining, Lakeland, FL, USA, 9–11April 2018; pp. 19–28.
  * Li et al. (2014) Li, Q.; Cai, W.; Wang, X.; Zhou, Y.; Feng, D.D.; Chen, M.  Medical image classification with convolutional neural network.  In Proceedings of the 2014 13th International Conference on Control Automation Robotics & Vision (ICARCV), Singapore, 10–12 December 2014; pp. 844–848.
  * Heidarysafa et al. (2018) Heidarysafa, M.; Kowsari, K.; Brown, D.E.; Jafari Meimandi, K.; Barnes, L.E.  An Improvement of Data Classification Using Random Multimodel Deep Learning (RMDL). _arXiv_ 2018, arXiv:1808.08121,  doi:black10.18178/ijmlc.2018.8.4.703.
  * Scherer et al. (2010) Scherer, D.; Müller, A.; Behnke, S.  Evaluation of pooling operations in convolutional architectures for object recognition.  In Proceedings of the Artificial Neural Networks–ICANN 2010, Thessaloniki, Greece, 15–18 September 2010; pp. 92–101.
  * Kingma and Ba (2014) Kingma, D.; Ba, J.  Adam: A method for stochastic optimization.  arXiv 2014, arXiv:1412.6980.
  * Chollet et al. (2015) Chollet, F.  Keras: Deep Learning Library for Theano and Tensorflow. 2015.  Available online: https://keras.io/ (accessed on 19 August 2019).
  * Srivastava et al. (2014) Srivastava, N.; Hinton, G.; Krizhevsky, A.; Sutskever, I.; Salakhutdinov, R.  Dropout: A simple way to prevent neural networks from overfitting.  J. Mach. Learn. Res. 2014, 15, 1929–1958.
  * Yang (1999) Yang, Y.  An evaluation of statistical approaches to text categorization.  Inf. Retr. 1999, 1, 69–90.
  * Lever et al. (2016) Lever, J.; Krzywinski, M.; Altman, N.  Points of significance: Classification evaluation. _Nat. Methods_ 2016, _13_ , 603–604.
  * Abadi et al. (2016) Abadi, M.; Agarwal, A.; Barham, P.; Brevdo, E.; Chen, Z.; Citro, C.; Corrado, G.S.; Davis, A.; Dean, J.; Devin, M.; et al.  Tensorflow: Large-scale machine learning on heterogeneous distributed systems.  arXiv 2016, arXiv:1603.04467.


# Compressed Error HARQ: Feedback Communication on Noise-Asymmetric Channels
††thanks: Code can be found at: https://github.com/sravan-ankireddy/ce-harq

Sravan Kumar Ankireddy Correspondence to: Sravan<EMAIL_ADDRESS>University of Texas at Austin  S. Ashwin Hebbar  Princeton University  Yihan
Jiang  Aira Technologies  Hyeji Kim  University of Texas at Austin  Pramod
Viswanath  Princeton University

###### Abstract

In modern communication systems with feedback, there are increasingly more
scenarios where the transmitter has much less power than the receiver (e.g.,
medical implant devices), which we refer to as noise-asymmetric channels. For
such channels, the feedback link is of higher quality than the forward link.
However, feedback schemes for cellular communications, such as hybrid ARQ, do
not fully utilize the high-quality feedback link. To this end, we introduce
Compressed Error Hybrid ARQ, a generalization of hybrid ARQ tailored for
noise-asymmetric channels; the receiver sends its estimated message to the
transmitter, and the transmitter harmoniously switches between hybrid ARQ and
compressed error retransmission. We show that our proposed method
significantly improves reliability, latency, and spectral efficiency compared
to the conventional hybrid ARQ in various practical scenarios where the
transmitter is resource-constrained.

##  I Introduction

With the advance of low-powered devices, there are increasingly more
communication scenarios where the transmitter has much less power than the
receiver. For example, low-powered _medical implant devices_ send periodic
biological measurements to a power-supplied machine; _Internet of Things (IoT)
sensors_ with limited battery capacity send various information to a high-
powered device, e.g., Alexa; _Deep Space Satellite_ uses limited solar energy
to send data to the receiving station on earth. In all these examples, the
transmitter is power-limited, while the receiver operates at a much higher
power level [1]. We let _noise-asymmetric channels_ denote an extreme class of
such channels, where the forward channel is noisy, and the feedback channel is
noise-free as depicted in Fig 1.

Figure 1: Noise-Asymmetric Channels

To leverage the asymmetry in the channel, it is crucial to utilize the clean
feedback channel from the receiver to the transmitter. Feedback schemes used
in cellular communications, such as Automatic repeat request (ARQ) and Hybrid
ARQ (HARQ), however, does not fully utilize the clean feedback channel. In the
(Hybrid) ARQ, the receiver sends a single-bit feedback, an ACKnowledgment
(ACK) or a Negative ACK (NACK), based on the Cyclic Redundancy Checks (CRC).
The transmitter retransmits the entire coded message block (or a pre-arranged
coded block) if a NACK is received.

We focus on designing a feedback communication system for noise-asymmetric
channels, which successfully leverages the high-quality feedback channels. Our
method generalizes the HARQ based on the following insight: when the
receiver’s estimate has few errors, it is beneficial to transmit the error
vector, which is sparse and compressible, instead of retransmitting the entire
message. The framework of error transmission is first introduced by Ooi and
Wornell in [2] and is recently explored in [3]. We combine this idea and HARQ
to build a feedback communication algorithm for noise-asymmetric channels. (An
extensive summary of existing feedback schemes [4, 5, 6, 2, 3, 7, 8, 9, 10]
and their comparison with our work are provided in Section IV.)

Our main contributions are summarized as follows.

  * •

Algorithm design:  We propose the Compressed Error HARQ (CE-HARQ), a novel
feedback communication algorithm for noise-asymmetric channels with block-
level feedback, to facilitate low-latency communications in low-powered
devices. Our scheme seamlessly switches between the HARQ and error compression
based on analytical criteria.

  * •

Numerical evaluations:  We achieve significant gains over the conventional
HARQ scheme on a wide range of practical resource-constrained scenarios. For
low-complexity coding schemes such as convolutional codes, CE-HARQ achieves up
to $2.5$ dB gain over conventional HARQ. Additionally, we also demonstrate
improvements in latency and spectral efficiency.

  * •

Practical considerations:  Our design of CE-HARQ takes into consideration
various resource constraints, such as systems where the redesign of the PHY
layer is prohibitive. This is done by providing the flexibility to separate
the channel coding into PHY and MAC layers. As a result, our algorithm is
compatible with and can be smoothly applied to low-resource applications like
IoT and Bluetooth communications. Additionally, we add fallback mechanisms and
guidelines for the practical deployment of such systems.

##  II System Model

We consider a block-feedback system with an Additive White Gaussian Noise
(AWGN) forward channel and a noiseless feedback channel, with active feedback
and BPSK modulation. The aim is to communicate a message vector
$\mathbf{u}\in\\{0,1\\}^{K}$ over a maximum of $D$ rounds.

At round $i$, the encoder $\phi^{(i)}$ takes as input the message $\mathbf{u}$
and the feedback from previous round $\hat{\mathbf{u}}^{(i-1)}$, which is the
message estimate, and produces $N$ symbols to be transmitted.

$\displaystyle\mathbf{x}^{(i)}=\phi^{(i)}(\mathbf{u},\hat{\mathbf{u}}^{(i-1)}),$
(1)

where $\mathbf{x}^{(i)}\in\\{0,1\\}^{N}$. The transmitter then sends the
encoded vector over the forward channel as

$\displaystyle\mathbf{y}^{(i)}=\mathbf{x}^{(i)}+\mathbf{n}^{(i)},$ (2)

where $\mathbf{n}^{(i)}\sim\mathcal{N}(0,\sigma^{2}I)\in\mathbb{R}^{N}$ is the
noise vector and $\mathbf{y}^{(i)}\in\mathbb{R}^{N}$ is the received vector.

At the receiver, the decoder $\psi^{(i)}$ takes as input the received vector
$\mathbf{y}^{(i)}$ and the previous message estimate
$\hat{\mathbf{u}}^{(i-1)}$, to produce the new estimate $\mathbf{u}^{(i)}$
given by

$\displaystyle\hat{\mathbf{u}}^{(i)}=\psi^{(i)}(\mathbf{y}^{(i)},\hat{\mathbf{u}}^{(i-1)}),$
(3)

where $\mathbf{u}^{(i)}\in\\{0,1\\}^{K}$. The receiver then sends the new
message estimate $\mathbf{u}^{(i)}$ to the transmitter, which is used for
generating the next transmission $\mathbf{x}^{(i+1)}$. We reiterate that the
feedback sequence $\mathbf{u}^{(i)}\in\\{0,1\\}^{N}$ is restricted to a binary
sequence, making it practical for resource-constrained settings and comparable
to traditional HARQ schemes.

This process is continued until an error-free decoding or a maximum number of
rounds $D$ is reached. The objective is to design a pair of encoder-decoder
$\\{\phi^{(i)},\psi^{(i)}\\}_{i=1}^{D}$ that minimizes the probability of
error $\mathbb{P}\\{\mathbf{u}\neq\hat{\mathbf{u}}^{(D)}\\}$ for a given
maximum number of rounds $D$.

##  III Compressed Error HARQ

We introduce the Compressed Error HARQ (CE-HARQ) scheme, which generalizes the
HARQ to leverage the feedback of the estimated message from the receiver to
the transmitter. The key innovation of CE-HARQ is achieving a very low Forward
Error Correction (FEC) rate for retransmissions by compressing the difference
between the message and the estimated message, i.e., error, as opposed to the
message itself.

This is done by selectively and carefully utilizing sparsity in error vectors.
In the early rounds of communications, where the error vector is not sparse,
the CE-HARQ performs the conventional HARQ. In the later rounds of
communications, as the error vector becomes more sparse, it iteratively
updates and compresses the error vector after each round, reducing the FEC
rate further.

The CE-HARQ system has three major operational blocks, as depicted in Fig 2.
The transmitter first determines whether to send the message or the error
based on the sparsity of the error, shown in A. The encoder then performs two
layers of channel encoding, MAC and PHY, shown in B and transmits through the
forward channel. At the receiver, the decoder estimates the message, shown in
C, and transmits this estimate through the high-quality feedback link.

Figure 2: CE-HARQ System Model Method | Feedback | Entropy | MAC | PHY | Forward | Feedback
---|---|---|---|---|---|---
Code | Code | Code | Code | Message | Message
ARQ | ACK/NACK | N/A | N/A | Any | Binary | Binary
HARQ | ACK/NACK | N/A | HARQ | Any | Binary | Binary
DeepCode [7] | Neural | Neural | Neural | Neural | Continuous | Continuous
GBAF [11] | Neural-Block | Neural | Neural | Neural | Continuous | Continuous
CEC[2] | Received vector $\hat{\mathbf{x}}^{(i)}$ | Shannon-Fano | N/A | N/A | Binary | Binary
AIC[3] | Quantized LLR | Huffman | N/A | N/A | Binary | Binary
Ours (CE-HARQ) | Message estimate $\hat{\mathbf{u}}^{(i)}$ | AC | Configurable+HARQ | Any | Binary | Binary
TABLE I: Comparison of various feedback schemes

###  III-A HARQ vs. CE Selection and Error Compression

The first round is always HARQ and the PHY encoder takes the message
$\mathbf{u}\in\\{0,1\\}^{K}$ as input i.e., $\mathbf{b}^{(1)}=\mathbf{u}$.
Subsequently, in the $(i+1)^{th}$ round, the transmitter first computes the
error in the receiver’s estimated message using the feedback from round $i$,
$\hat{\mathbf{u}}^{(i)}$, as
$\mathbf{e}^{(i)}=\mathbf{u}\oplus\hat{\mathbf{u}}^{(i)}\in\\{0,1\\}^{K}$,
which is used to select the retransmission scheme.

_Sparsity Check: HARQ or Compressed Error (CE)._ If the number of errors in
$\mathbf{e}^{(i)}$ is large, i.e., ${|e^{(i)}|}>{K}\tau^{\star}$, where
$\tau^{\star}$ is the pre-defined sparsity threshold (discussed in Section
III-D), we retransmit the message : $\mathbf{b}^{(i)}=\mathbf{u}$. On the
other hand, once the error vector is highly sparse, i.e.
${|e^{(i)}|}<{K}\tau^{\star}$, the scheme switches from HARQ retransmission to
compressed error retransmission i.e., CE, detailed below.

_Entropy Encoder._ The error vector $\mathbf{e}^{(i)}$ is first losslessly
compressed to $H(\mathbf{e}^{(i)})$ bits , $\mathbf{c}^{(i)}$, using
Arithmetic Coding (AC) [12], which allows the use of a very low rate FEC code
to protect $\mathbf{c}^{(i)}$ as shown in the next section.

$\displaystyle\phi_{\text{AC}}:\mathbf{e}^{(i)}\in\\{0,1\\}^{K}\rightarrow\mathbf{c}^{(i)}\in\\{0,1\\}^{H(\mathbf{e}^{(i)})}.$

###  III-B Channel Coding

Since the sparsity of the error vector varies for each round of CE, the
achievable rate for the PHY layer FEC scheme changes with each round. In low
power constrained systems such as Bluetooth Low Energy/Bluetooth Classic,
strong latency requirements makes it challenging to modify the PHY layer. To
address this, we use two layers of channel coding:

MAC encoder. We use a variable rate MAC encoder to first encode
$\mathbf{c}^{(i)}\in\\{0,1\\}^{H(\mathbf{e}^{(i)})}$ to $K$ bits, resulting in
constant rate for PHY encoder.

$\displaystyle\phi^{(i)}_{\text{MAC}}:\mathbf{c}^{(i)}\in\\{0,1\\}^{H(\mathbf{e}^{(i)})}\rightarrow\mathbf{b}^{(i)}\in\\{0,1\\}^{K}.$

PHY encoder. The PHY encoder is a fixed rate encoder that maps a given input
$K$ bits to $N$ bits using a rate $R=\nicefrac{{K}}{{N}}$ code.

$\displaystyle\phi^{(i)}_{\text{PHY}}:\mathbf{b}^{(i)}\in\\{0,1\\}^{K}\rightarrow\mathbf{x}^{(i)}\in\\{0,1\\}^{N}.$
(4)

This two-phase MAC and PHY encoding results in an effective coding rate of
$\frac{H(\mathbf{e}^{(i)})}{K}\times\frac{K}{N}=\frac{H(\mathbf{e}^{(i)})}{N}$,
while keeping the PHY layer unchanged. Notably, during the HARQ phase the MAC
encoding is not performed, allowing a rate of $\nicefrac{{K}}{{N}}$.

Remark: Note that we perform a separate source-channel coding for the error
vector. In Appendix C, we show that such separation is asymptotically optimal
for each round of forward communication with the receiver’s message estimate
available at both the transmitter and receiver.

###  III-C Decoding

The decoding operation is performed in two stages. First, the PHY decoder
estimates the $K$ bits from PHY encoder $\hat{\mathbf{b}}^{(i)}$. During HARQ
scheme, this is sufficient to recover the message as $\hat{\mathbf{u}}^{(i)}$.
On the other hand, for CE scheme, the MAC decoder performs another layer of
decoding to estimate the compressed error $\hat{\mathbf{c}}^{(i)}$. Finally,
using $\hat{\mathbf{c}}^{(i)}$, the entropy decoder reconstructs the full
error vector $\hat{\mathbf{e}}^{(i)}$, which is used to get the new message
estimate as
$\hat{\mathbf{u}}^{(i)}=\hat{\mathbf{u}}^{(i-1)}\oplus\hat{\mathbf{e}}^{(i)}$.

###  III-D Adaptive and Iterative compression

At every retransmission, the transmitter chooses the retransmission scheme
based on the sparsity of error vector $\mathbf{e}^{(i)}$. It is beneficial to
choose the CE scheme only when the error is sufficiently sparse so that the
resulting coding gain from the low-rate FEC is higher than the loss of SNR
gain by not choosing HARQ. There exists an optimal sparsity threshold
$\tau^{\star}$, which varies dynamically with the effective SNR.

To determine $\tau^{\star}$ for a given effective SNR and FEC rate, we first
derive an analytical solution by assuming an asymptotic setting (Appendix
A-A). However, the optimality of both source and channel coding do not hold
well at short block lengths. To account for this, we find a numerical solution
for the optimal threshold for a given effective SNR and rate using Monte-Carlo
simulations (Appendix A-A1). Based on the $\tau^{\star}$ computed, the
retransmission scheme is selected for each round for different SNRs. We refer
to this as adaptive compression. This is a key distinction between CE-HARQ and
other feedback schemes, such as AIC, which continuously compress after each
round.

During the CE phase of CE-HARQ, the error in the message estimate should
decrease over the rounds, making the error vector sparser and allowing for
further compression. This concept is the basis of iterative compression in CEC
[2] and AIC [3]. However, if an error occurs in MAC decoding, the error may
increase i.e., $|\mathbf{e}^{(i+1)}|>|\mathbf{e}^{(i)}|$. In such cases, CE-
HARQ triggers a fallback mechanism and retransmits the previous error vector
to improve the error estimate at the receiver. This guarantees that the
iterative compression is performed only when the new error vector is sparser
than the previous error vector, which is crucial for practical systems.

##  IV Related work and comparison

In this section, we compare CE-HARQ to existing communication systems with
feedback, as summarized in Table I. The most commonly used ARQ and HARQ
schemes are not optimized for noise-asymmetric channels. Upon the availability
of noiseless feedback, Perotti et al. introduced an alternate approach,
Accumulative Iterative Code (AIC) [3], building on the pioneering work of Ooi
and Wornell - Compressed Error Cancellation (CEC) [2]. These schemes use
feedback to communicate compressed errors without channel coding during
retransmission. Notably, these schemes achieve improved spectral efficiency at
the cost of the number of retransmissions, rendering them unsuitable for many
latency-critical applications. In contrast, CE-HARQ augments the compressed
error framework with channel coding, to maximize the probability of decoding
in each round. This is achieved by utilizing the maximum available channel
uses in each round, thus trading off spectral efficiency for the number of
retransmissions. Additionally, AIC [3] uses Huffman coding to compress the
error, which requires a large lookup table to be stored for each round of
communication adding significant overhead. Instead, CE-HARQ uses Arithmetic
Coding (AC) or even index-coding [13] when the number of errors is very small,
suffering minimal overhead.

More recently, several works focused on deep learning-based feedback codes, at
both symbol and block level, [7, 8, 9, 10, 11] which leverage feedback to
significantly improve reliability at practical block lengths. However, these
systems are challenging to deploy practically since they incur significant
costs in terms of memory, and complexity, and cannot be deployed in resource-
constrained applications that require low latency. Further, they rely on non-
binary continuous feedback rendering them unsuitable for implementation in the
modern communication stack. Meanwhile, CE-HARQ uses binary feedback in
conjunction with a low-complexity channel coding and error compression to
ensure compatibility with current systems and low-resource settings. Recent
commercial feedback communication systems, such as those from Aira Technology
[13, 14] are good examples of practical error compression feedback systems,
that have been shown to achieve noticeable gains in reliability and range of
Bluetooth-based IoT systems.

##  V Results

In this study, we focus on resource-constrained applications on noise-
asymmetric channels. Often in such applications, it is infeasible to modify
the PHY layer design; CE-HARQ can support this by limiting changes to the MAC
layer.

Specifically, our main result is for low-power Bluetooth communication, where
the transmitter is highly power-constrained [15]. We consider a convolutional
code of rate $\nicefrac{{1}}{{2}}$ for the PHY layer and a variable rate
convolutional code with a rate as low as $\nicefrac{{1}}{{12}}$ for the MAC
layer. The standard hard Viterbi decoder is used for both PHY and MAC layers.

For completeness, we consider two additional settings. The first is the case
of uncoded transmission for the PHY layer and variable rate convolutional
codes for the MAC layer, with hard Viterbi decoding. Secondly, we consider a
highly reliable FEC used in 5G NR: the standard rate $\nicefrac{{3}}{{4}}$
LDPC codes [16] for the PHY layer and variable rate LDPC codes for the MAC
layer, with the standard min-sum decoder using a maximum of 6 iterations.

Baselines. We consider two baselines: First, we compare CE-HARQ with the
conventional HARQ scheme. Additionally, to clearly quantify the gain obtained
by combining FEC with compressed error retransmissions, we establish the
following baseline scheme, by modifying CE-HARQ: In the MAC layer, the FEC is
removed and the error vector is compressed after each retransmission. The PHY
layer then encodes the compressed error vector at a constant coding rate.
Owing to it’s similarity with AIC, we refer to the scheme as AIC with
Arithmetic Coding (AIC-AC).

We evaluate the performance of CE-HARQ against the baselines on two practical
scenarios: (1) Low-latency: Minimize BLER for a fixed number of
retransmissions, and (2) High-reliability: Minimize the average number of
rounds to achieve a target BLER. Furthermore, we evaluate and compare the
spectral efficiency of our algorithm against the baselines.

Figure 3: BLER performance after 3 retransmissions, when the PHY coding scheme
is: a) Uncoded, message length $K=800$. b) Rate $\nicefrac{{1}}{{2}}$
Convolutional code, $K=800$. c) Rate $\nicefrac{{3}}{{4}}$ LDPC code, $K=960$.
CE-HARQ exhibits large gains over the conventional HARQ and AIC with
arithmetic coding, which always transmits the compressed error, with low-
complexity PHY coding schemes such as convolutional codes, typically
encountered in resource-constrained devices.

Performance for a given latency. In low-latency applications, the maximum
number of retransmissions is often limited. Here, we consider a maximum of 3
retransmissions and compare the BLER performance. As demonstrated in Fig. 3
for uncoded PHY, CE-HARQ is better than HARQ and AIC-AC by up to $7.5$ dB and
$6.3$ dB respectively at a BLER of $10^{-4}$. This translates to a significant
improvement in the reliability and range of the system while maintaining the
same latency. Similarly, Fig. 3 shows that when PHY uses a convolutional code
of rate $\nicefrac{{1}}{{2}}$, CE-HARQ performs better than HARQ and AIC-AC by
up to $2.5$ dB. Finally, when a $\nicefrac{{3}}{{4}}$ LDPC code is used for
the PHY layer ( Fig. 3), CE-HARQ obtains a marginal gain of $0.1$ dB. In
summary, CE-HARQ provides the maximum gains for systems with low-complexity
coding schemes, which are inevitable in resource-constrained devices such as
Bluetooth-LE. Additionally, it is clearly seen that in practical
retransmission systems, the uncoded transmission of compressed errors is
highly undesirable.

Figure 4: Average number of rounds for successful transmission, when the PHY
coding scheme is: a) Uncoded, message length $K=800$. b) Rate
$\nicefrac{{1}}{{2}}$ Convolutional code, $K=800$. c) Rate
$\nicefrac{{3}}{{4}}$ LDPC code, $K=960$. CE-HARQ obtains maximum gain over
baselines when the PHY layer is uncoded and the gains decrease as the
complexity of FEC increases.

Latency for a given performance. In high-reliability applications, it is
critical to guarantee a low BLER. Here, for the above three settings, we now
consider a target BLER of $10^{-5}$ and compare the average rounds required to
achieve this. As highlighted in Fig. 4 for uncoded PHY, CE-HARQ has up to
$50\%$ and $62\%$ lower latency compared to HARQ and AIC-AC respectively at
SNR $0$ dB. This translates to significant improvements in power consumption
while maintaining the same reliability. In Fig. 4, $\nicefrac{{1}}{{2}}$
convolutional coding is used for the PHY layer resulting in latency
improvements of up to $33\%$ for CE-HARQ compared to HARQ and AIC-AC at SNR
$0$ dB. Finally, in Fig. 4, $\nicefrac{{3}}{{4}}$ LDPC coding is used for the
PHY layer, resulting in up to $42\%$ and $54\%$ lower latency compared to HARQ
and AIC-AC respectively at SNR $0$ dB.

Figure 5: Spectral Efficiency for a target BLER of $10^{-5}$, when the PHY
coding scheme is : a) Uncoded, message length $K=800$. b) Rate
$\nicefrac{{1}}{{2}}$ Convolutional code, $K=800$. c) Rate
$\nicefrac{{3}}{{4}}$ LDPC code, $K=960$. CE-HARQ consistently achieves better
spectral efficiency compared to the two baselines.

Spectral efficiency.  The spectral efficiency of the forward channel for a
given SNR and BLER is defined as

$\displaystyle\text{SE}\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{KQ}{E[N_{c}]}(1-\text{BLER})\text{bits/s/Hz},$
(5)

where $K$ is the message length and $E[N_{c}]$ is the expected total channel
uses for the retransmission scheme. $Q$ is the order of modulation, which is
$1$ for BPSK.

CE-HARQ is a constant-length code; hence
$\mathbb{E}[N_{c}]=N\mathbb{E}[D_{c}]$, where $N$ is the codeword length and
$\mathbb{E}[D_{c}]$ is the average number of rounds required to achieve the
target BLER.

SE combines the error correction and latency to provide a unified view of the
trade-off between both metrics. While AIC-AC is optimized for SE by utilizing
the minimal number of channel uses in every round, it is not straight forward
how the trade-off between lesser number of rounds with $N$ channel uses and
higher number of rounds with $H(\mathbf{e}^{(i)})$ channel uses plays out.
Fig. 5 shows that CE-HARQ consistently achieves better SE than HARQ and AIC-
AC.

Through extensive simulations across different settings, we show that CE-HARQ
significantly improves upon the baselines in resource-constrained setups such
as Bluetooth, where using low-complexity coding schemes is unavoidable.
However, the gains over HARQ are minimal when strong coding schemes like LDPC
are used. This can be attributed to the narrow waterfall region in such codes,
which results in the coding gain of the CE phase being inferior to the gains
obtained by increased effective SNR through HARQ.

##  VI Conclusion and Remarks

In this work, we provide a practical framework, Compressed Error HARQ, to
build block-feedback codes for noise-asymmetric channels. We assume a noise-
asymmetric channel and focus on resource-constrained settings where the
transmitter is a low-power, low-memory device, and the receiver can operate at
much higher power. CE-HARQ generalizes the Hybrid-ARQ scheme for noise-
asymmetric channels by combining it with compressed error, forward error
correction, and a novel retransmission selection mechanism that intelligently
switches between HARQ and Compressed Error (CE) based on the sparsity of the
error vector.

CE-HARQ achieves significant improvements in both error correction performance
and latency for a variety of configurations. Additionally, CE-HARQ achieves
better Spectral Efficiency compared to purely CE based schemes such as AIC-AC.
Significant gains are observed in the case of convolutional coding for the PHY
layer, which is a common configuration for low-power applications such as
Bluetooth and IoT systems. We also outline the design choices essential to
facilitate practical deployment such as limiting the feedback to be binary and
adding a fallback mechanism to ensure continual improvement of the message
estimate at the receiver.

There are several interesting directions for extending CE-HARQ. The first is
the case of partial feedback where the full message estimate is not available,
and only a few bits of information can be sent. Deciding the optimal
information for feedback is a non-trivial problem. Another interesting problem
is the case of noisy feedback and non-AWGN channels, where the expected gains
will depend heavily on the quality of the feedback link. Characterizing such a
trade-off would be a very interesting future research direction.

## References

  * [1] R. Heydon and N. Hunn, “Bluetooth low energy,” _CSR Presentation, Bluetooth SIG https://www. bluetooth. org/DocMan/handlers/DownloadDoc. ashx_ , 2012\.
  * [2] J. M. Ooi and G. W. Wornell, “Fast iterative coding techniques for feedback channels,” _IEEE Transactions on Information Theory_ , vol. 44, no. 7, pp. 2960–2976, 1998.
  * [3] A. G. Perotti, B. M. Popovic, and A. R. Safavi, “Accumulative iterative codes based on feedback,” _arXiv preprint arXiv:2106.07415_ , 2021.
  * [4] J. Schalkwijk and T. Kailath, “A coding scheme for additive noise channels with feedback–i: No bandwidth constraint,” _IEEE Transactions on Information Theory_ , vol. 12, no. 2, pp. 172–182, 1966.
  * [5] Z. Chance and D. J. Love, “Concatenated coding for the awgn channel with noisy feedback,” _IEEE Transactions on Information Theory_ , vol. 57, no. 10, pp. 6633–6649, 2011.
  * [6] A. Ben-Yishai and O. Shayevitz, “Interactive schemes for the awgn channel with noisy feedback,” _IEEE Transactions on Information Theory_ , vol. 63, no. 4, pp. 2409–2427, 2017.
  * [7] H. Kim, Y. Jiang, S. Kannan, S. Oh, and P. Viswanath, “Deepcode: Feedback codes via deep learning,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [8] A. R. Safavi, A. G. Perotti, B. M. Popovic, M. B. Mashhadi, and D. Gunduz, “Deep extended feedback codes,” _arXiv preprint arXiv:2105.01365_ , 2021\.
  * [9] M. B. Mashhadi, D. Gunduz, A. Perotti, and B. Popovic, “Drf codes: Deep snr-robust feedback codes,” _arXiv preprint arXiv:2112.11789_ , 2021.
  * [10] Y. Shao, E. Ozfatura, A. Perotti, B. Popovic, and D. Gunduz, “Attentioncode: Ultra-reliable feedback codes for short-packet communications,” _arXiv preprint arXiv:2205.14955_ , 2022.
  * [11] E. Ozfatura, Y. Shao, A. Perotti, B. Popovic, and D. Gündüz, “All you need is feedback: Communication with block attention feedback codes,” _IEEE Journal on Selected Areas in Information Theory_ , 2022.
  * [12] T. M. Cover, _Elements of information theory_. John Wiley & Sons, 1999.
  * [13] Y. Jiang, R. Gopalan, A. Antonini, and A. Chandrasekher, “Indexing-based feedback codes and methods of use,” Jun. 30 2022, uS Patent App. 17/556,155.
  * [14] A. Chandrasekher, R. Gopalan, S. Kesireddy, and A. Rahimzamani, “Multi-bit feedback protocol systems and methods,” Jun. 30 2022, uS Patent App. 17/560,964.
  * [15] M. Woolley, “Bluetooth core specification version 5.0 feature enhancements,” _Bluetooth SIG_ , 2021.
  * [16] ETSI, “3gpp ts 38.212. “nr; multiplexing and channel coding.”,” in _3rd Generation Partnership Project; Technical Specification Group Radio Access Network._ , 2021.
  * [17] A. Viterbi, “Convolutional codes and their performance in communication systems,” _IEEE Transactions on Communication Technology_ , vol. 19, no. 5, pp. 751–772, 1971.
  * [18] E. Malkamaki and H. Leib, “Evaluating the performance of convolutional codes over block fading channels,” _IEEE Transactions on Information Theory_ , vol. 45, no. 5, pp. 1643–1646, 1999.
  * [19] P. Frenger, S. Parkvall, and E. Dahlman, “Performance comparison of harq with chase combining and incremental redundancy for hsdpa,” in _IEEE 54th Vehicular Technology Conference. VTC Fall 2001. Proceedings (Cat. No. 01CH37211)_ , vol. 3. IEEE, 2001, pp. 1829–1833.

##  Appendix A Selection of Sparsity threshold

At the beginning of round $i$, the error vector should be compressed only if
it is sufficiently sparse. To compute the optimal sparsity threshold, two
approaches are proposed. The first is an analytical approach that compares the
expected probability of error for HARQ vs CE-HARQ, for a given round and SNR.
Next, a simple analytical approach based on Monte Carlo simulations is
discussed.

###  A-A Analytically computing the optimal sparsity threshold

The performance of convolutional codes is well studied in literature [17, 18]
and we assume that the expected bit error rate can be computed for a given SNR
$S$ and rate $R$ as $P_{e}(S,R)$. For many short length block-codes, this can
be easily computed using Monte Carlo simulations.

For ARQ, since every retransmission has equal probability of error,
compressing the error vector and using low-rate FEC always improves the
decoding probability. But in HARQ type retransmission, there is a trade-off
between the coding gain achieved by error compression and FEC vs the SNR gain
of HARQ. Assuming chase combining at the receiver, the effective SNR at the
receiver at round $i$ can be computed as

$\displaystyle\text{S}_{i}=S+10\log_{10}i,$ (6)

where SNR is the SNR in first round. With each retransmission, chase combining
results in an effective SNR gain via the principle of Maximal Ratio Combining
[19].

During round $i$, HARQ and CE-HARQ can achieve a maximum possible effective
SNR of

$\displaystyle S_{H}$ $\displaystyle=S+10\log_{10}D,$ (7) $\displaystyle
S_{i}$ $\displaystyle=S+10\log_{10}(D-i+1)$ (8)

respectively, by the end of maximum number of rounds $D$. Here, $S$ is the SNR
in round 1. For a given error vector $e^{(i)}$ in round $i$, CE-HARQ can
achieve the lowest FEC rate of $R_{i}=\nicefrac{{H(e^{(i)})}}{{N}}$. HARQ uses
a FEC rate $R=\nicefrac{{K}}{{N}}$ for all the rounds.

Assuming independent and identically distributed (i.i.d) errors in the message
vector, the entropy of the error vector $e^{(i)}$ can be written as

$\displaystyle
H(e^{(i)})=-K(\tau_{i}\log_{2}\tau_{i}+(1-\tau_{i})\log_{2}(1-\tau_{i})),$ (9)

where $\tau_{i}=\frac{|e^{(i)}|}{K}$ is sparsity of the error vector.

Thus, for round $i$, we define optimal threshold $\tau_{i}^{\star}$ as the
maximum value of sparsity $\tau_{i}$ such that
$P_{e}(S_{i},R_{i})<P_{e}(S_{H},R)$.

####  A-A1 Grid search for threshold

Since it is not feasible to get a closed form solution for $\tau_{i}^{\star}$,
we instead explore a simple grid search based approach. To keep the search
computationally feasible, we fix single optimal threshold $\tau^{\star}$ for
all the rounds of communication. For each SNR and coding rate, probability of
decoding error is found via Monte Carlo simulations for different values of
sparsity threshold from $0$ to $0.1$ in steps of $0.005$. Based on the
results, the best sparsity threshold is chosen for each SNR.

##  Appendix B Ablation studies

To highlight the significance of selecting the optimal sparsity threshold
$\tau^{\star}$, we compare the performance of CE-HARQ with threshold
$\tau^{\star}$ denoted by CE-HARQ($\tau^{\star}$) to a naive approach where
the error is always compressed i.e., $\tau=1$ followed by FEC, denoted by CE-
HARQ($\tau$). Fig. 6 demonstrates that the optimal selection of the sparsity
threshold $\tau^{\star}$ crucially impacts the performance on both our
evaluation settings.

Figure 6: Effect of choosing the sparsity threshold : Using a rate
$\nicefrac{{1}}{{2}}$ convolutional code for PHY layer, CE-HARQ with optimal
threshold $\tau^{\star}$ is significantly better than continuous compression
($\tau=1$) when : a) BLER is compared for maximum of 3 retransmissions b)
Average rounds for error free transmission is compared.

##  Appendix C Source-Channel Separation for the transmission of error

Consider the following setup Fig. 7, where $\mathbf{U}$ denotes $K$ i.i.d.
discrete sources available at the encoder, $\mathbf{S}$ denotes $K$ i.i.d.
discrete sources that are correlated with $\mathbf{U}$ as
$(U_{i},S_{i})\sim\text{i.i.d.\ }\mathbb{P}(u_{i},s_{i})$ for $i=1,\cdots,K$
available at both the encoder and decoder as side information. The encoder
maps $(\mathbf{U},\mathbf{S})$ to a length-N discrete sequence $\mathbf{X}$,
which is corrupted by a noisy channel as $\mathbf{Y}$. The decoder maps
$\mathbf{Y}$ to an estimate for $\mathbf{U}$, denoted by $\mathbf{V}$. This
setup models the $i$-th round of communication from the transmitter to the
receiver. The transmitter has a message $\mathbf{U}\in\\{0,1\\}^{K}$ and the
receiver’s estimated message as side information
$\mathbf{S}=\mathbf{U}\oplus\mathbf{e}^{(i-1)}$; the receiver also has its own
estimated message from the previous round of communication
$\mathbf{S}=\mathbf{U}\oplus\mathbf{e}^{(i-1)}$ as side information.

Figure 7: The $i$-th round of forward communication can be viewed as joint
source-channel coding with Tx/Rx side information, where
$S^{K}=\hat{U}^{(i-1)}$ (previous message estimate) serves as Tx/Rx side info.
Theorem 1 establishes the optimal rate-distortion, which is achieved by a
separated source-channel coding.

######  Theorem 1.

Let $d(u,v)$ denote a distortion-metric. A rate-$K/N$ code achieves the
distortion $D$ if and only if $K/N\leq C/R_{\text{SI}}(D)$, where
$C=\max_{p(x)}I(X;Y)$ and

$R_{\text{SI}}(D)=\min_{p(v|u,s):\mathbb{E}[d(u,v)]\leq D}I(U;V|S).$

###### Proof.

Achievability follows immediately from the separate source-channel coding.
Converse also closely follows the converse proof of the source-channel
separation theorem for channels without side information.

Suppose $\frac{1}{K}\mathbb{E}[d(\mathbf{U},\mathbf{V})]\leq D$. Then,

$\displaystyle I(U^{K};V^{K}|S^{K})$
$\displaystyle=\sum_{i=1}^{K}I(U_{i};V^{K}|U^{i-1},S^{K})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{i=1}^{K}I(U_{i};V^{K},U^{i-1}|S^{K})$
$\displaystyle\geq\sum_{i=1}^{K}I(U_{i};V_{i}|S^{K})$
$\displaystyle\geq\sum_{i=1}^{K}I(U_{i};V_{i}|S_{i})$ $\displaystyle\geq
KR_{\text{SI}}(D)$ (10)

where (a) holds since $U_{i}$ is a memoryless source.

Now, by the data processing inequality, we have

$\displaystyle\frac{1}{K}I(U^{K};V^{K}|S^{K})\leq\frac{1}{K}I(U^{K};Y^{N}|S^{K}).$
(11)

Formally, the inequality above holds since $U^{K}-(Y^{N},S^{K})-V^{K}$ forms a
Markov Chain.

Finally, from the converse for the communication over discrete memoryless
channels, we have

$\displaystyle I(U^{K};Y^{N}|S^{K})$
$\displaystyle=\sum_{i=1}^{N}I(U^{K};Y_{i}|Y^{i-1},S^{K})$
$\displaystyle\leq\sum_{i=1}^{N}I(U^{K},Y^{i-1};Y_{i}|S^{K})$
$\displaystyle\leq\sum_{i=1}^{N}I(X_{i},U^{K},Y^{i-1};Y_{i}|S^{K})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{i=1}^{N}I(X_{i};Y_{i}|S^{N})$
$\displaystyle\leq\sum_{i=1}^{N}I(X_{i};Y_{i}|S_{i})$
$\displaystyle\leq\sum_{i=1}^{N}I(X_{i},S_{i};Y_{i})$
$\displaystyle\leq\sum_{i=1}^{N}I(X_{i};Y_{i})$ $\displaystyle\leq NC,$ (12)

where (a) holds since $(U^{K},Y^{i-1})-X_{i}-Y_{i}$ forms a Markov chain given
$S^{K}$. By combining equations (10),(11), and (12), we complete the proof. ∎