11institutetext: 1Eindhoven University of Technology, Eindhoven 5612 AZ, The
Netherlands 11email<EMAIL_ADDRESS>
# Improving Aleatoric Uncertainty Quantification in Multi-Annotated Medical
Image Segmentation with Normalizing Flows

M.M.A. Valiuddin 11 C.G.A. Viviers 11 R.J.G. van Sloun 11 P.H.N. de With 11 F.
van der Sommen 11

###### Abstract

Quantifying uncertainty in medical image segmentation applications is
essential, as it is often connected to vital decision-making. Compelling
attempts have been made in quantifying the uncertainty in image segmentation
architectures, e.g. to learn a density segmentation model conditioned on the
input image. Typical work in this field restricts these learnt densities to be
strictly Gaussian. In this paper, we propose to use a more flexible approach
by introducing Normalizing Flows (NFs), which enables the learnt densities to
be more complex and facilitate more accurate modeling for uncertainty. We
prove this hypothesis by adopting the Probabilistic U-Net and augmenting the
posterior density with an NF, allowing it to be more expressive. Our
qualitative as well as quantitative (GED and IoU) evaluations on the multi-
annotated and single-annotated LIDC-IDRI and Kvasir-SEG segmentation datasets,
respectively, show a clear improvement. This is mostly apparent in the
quantification of aleatoric uncertainty and the increased predictive
performance of up to 14 percent. This result strongly indicates that a more
flexible density model should be seriously considered in architectures that
attempt to capture segmentation ambiguity through density modeling. The
benefit of this improved modeling will increase human confidence in annotation
and segmentation, and enable eager adoption of the technology in practice.

###### Keywords:

Segmentation Uncertainty Computer Vision Imaging

###  1 Introduction

As a result of the considerable advances in machine learning research over the
past decade, computer-aided diagnostics (CAD) using deep learning has rapidly
been gaining attention. The outcome from these deep learning-based CAD systems
has to be highly accurate, since it is often connected to critical designs
resulting in a potentially large impact on patient care. As such, conclusions
drawn from these CAD systems should be interpreted with care and by experts. A
convolutional neural network (CNN)-based approach has been adopted in a large
number of CAD applications and especially in semantic segmentation. This
approach segments the objects of interest by assigning class probabilities to
all pixels of the image. In the medical domain and especially in the context
of lesion segmentation, the exact edges or borders of these lesions are not
always easily defined and delineated by radiologists and endoscopists. In the
case of multiple annotators, clinicians can also disagree on the boundaries of
the localized lesions based on their understanding of the surrounding anatomy.
However, the exact edges or borders of these areas of interests often play a
critical role in the diagnostic process. For example, when determining whether
to perform surgery on a patient or the surgical planning thereof, the invasion
of a tumour into local anatomical structures derived from a CT scan, is
crucial. Thus, multiple forms of uncertainties come into play with semantic
segmentation-based approach for CAD. As such, accurately quantifying these
uncertainties have become an essential addition in CAD. Specialized doctors
provide ground-truth segmentation for models to be trained, based on their
knowledge and experience. When this is done by multiple individuals per image,
often discrepancies in the annotations arise, resulting in ambiguities in the
ground-truth labels.

Recent work [5] suggests two types of uncertainties exist in deep neural
networks. First, epistemic uncertainty, which refers to the lack of knowledge
and can be minimized with information gain. In the case of multi/single-
annotated data, these are the preferences, experiences, knowledge (or lack
thereof) and other biases of the multiple/single annotators. This epistemic
uncertainty from the annotator(s) manifests into aleatoric uncertainty when
providing annotations. Aleatoric uncertainty is the variability in the outcome
of an experiment, due to the inherent ambiguity that exists in the data,
captured through the multiple ground truths. By using a probabilistic
segmentation model, we attempt to learn this as a distribution of possible
annotations. It is important to enable expressiveness of the probability
distributions to sufficiently capture the variability. In multi-annotator
settings, the adoption of rich and multi-modal distributions may be more
appropriate. We aim to show that by using invertible bijections, also known as
Normalizing Flows (NFs), we can obtain more expressive distributions to
adequately deal with the disagreement in the ground-truth information.
Ultimately, this improves the ability to quantify the aleatoric uncertainty
for segmentation problems.

In this work, we use the the Probabilistic U-Net (PU-Net) [10] as the base
model and subsequently improve on it by adding a planar and radial flow to
render a more expressive learned posterior distribution. For quantitative
evaluation, we use the Generalized Energy Distance (GED), as is done in
previous work (see related work). We hypothesize that this commonly used
metric is prone to some biases, such that it rewards sample diversity rather
than predictive accuracy. Therefore, we also evaluate on the average and
Hungarian-matched IoU for the single- and multi-annotated data, respectively,
as is also done by Kohl et al. [9].

To qualitatively evaluate the ability to model the inter-variability of the
annotations, we present the mean and standard deviation of the segmentation
samples reconstructed from the model. In this paper, we make use of the multi-
and single-annotated LIDC-IDRI (LIDC) and Kvasir-SEG datasets, thereby
handling limited dataset size and giving insights on the effects of the
complex posterior on hard-to-fit datasets.

###  2 Related work

Kohl et al. [10] introduced the PU-Net for image segmentation, a model that
combines the cVAE [15] and a U-Net [13]. Here, the uncertainty is captured by
a down-sampled axis-aligned Gaussian prior that is updated through the KL
divergence of the posterior. These distributions contain several low-
dimensional representations of the segmentation, which can be reconstructed by
sampling. We use this model as our baseline model.

The concept of using NFs has been presented in earlier literature. For an
extensive introduction to NFs we suggest the paper from Kobyzev et al. [8].
The planar and radial NFs have been used for approximating flexible and
complex posterior distributions [12].

Selvan et al. [14] used an NF on the posterior of a cVAE-like segmentation
model and showed that this increases sample diversity. The increased sample
diversity resulted in a better score on the GED metric and a slight decrease
in DICE score. The authors reported significant gains in performance. However,
we argue that this claim requires more evidence to confirm this positive
effect, such as training with K-fold cross-validation and evaluating using
other metrics. Also, insight into the reasons for their improvements are not
provided and critical details of the experiments are missing, such as the
number of samples used for the GED evaluation. We aim to provide a more
complete argumentation and show clear steps towards improving the
quantification of aleatoric uncertainty.

###  3 Methods

####  3.1 Model architecture

We use a PU-Net extended with an NF, as is shown in Figure 1. A key element of
the architecture is the posterior network $Q$, which attempts to encapsulate
the distribution of possible segmentations, conditioned on the input image
$\mathbb{X}$ and ground truth $\mathbb{S}$ in the base distribution. The
flexibility of the posterior is enhanced through the use of an NF, which warps
it into a more complex distribution. During training, the decoder is sampled
by the posterior and is constructing, based on the encoded input image, a
segmentation via the proposed reconstruction network. The prior $P$ is updated
with the evidence lower bound (ELBO [7]), which is based on two components:
first, the KL divergence between the distributions $Q$ and $P$ and second, the
reconstruction loss between the predicted and ground-truth segmentation. The
use of NFs is motivated by the fact that a Gaussian distribution is too
limited to fully model the input-conditional latent distribution of
annotations. An NF can introduce complexity to $Q$, e.g. multi-modality, in
order to more accurately describe the characteristics of this relationship.

We proceed by extending the PU-Net objective (see appendix 0.A) and explain
the associated parameters in detail. We make use of the NF-likelihood
objective (see Appendix 0.B) with transformation
$f:\mathbb{R}\mapsto\mathbb{R}$ to define our posterior as

$\displaystyle\log q(\mathbf{z}|\mathbf{s},\mathbf{x})=\log
q_{0}(\mathbf{z}_{0}|\mathbf{s},\mathbf{x})-\sum_{i=1}^{K}\log\left(\left|\operatorname{det}\frac{df_{i}}{d\mathbf{z}_{i-1}}\right|\right).$
(1)

to obtain the objective

$\displaystyle\mathcal{L}$
$\displaystyle=-\mathbb{E}_{q_{\phi}(\mathbf{z}_{0}|\mathbf{s},\mathbf{x})}[\,\operatorname{log}p(\mathbf{s}|\mathbf{z},\mathbf{x})\,]$
(2)
$\displaystyle+\operatorname{KL}\left(\,q_{\phi}(\mathbf{z}_{0}|\mathbf{s},\mathbf{x})||p_{\psi}(\mathbf{z}|\mathbf{x})\,\right)-\mathbb{E}_{q_{\phi}(\mathbf{z}_{0}|\mathbf{s},\mathbf{x})}\left[\sum_{i=1}^{K}\log\left(\left|\operatorname{det}\frac{df_{i}}{d\mathbf{z}_{i-1}}\right|\right)\right].$

The input-dependent context vector $\mathbf{c}$, is used to obtain the
posterior flow parameters. During training, the posterior flow is used to
capture the data distribution with the posterior network
$Q(\bm{\mu},\bm{\sigma},\mathbf{c}|\mathbb{X},\mathbb{S})$, followed by
sampling thereof to reconstruct the segmentation predictions $\mathbb{Y}$. At
the same time, a prior network $P(\bm{\mu},\bm{\sigma}|\mathbb{X})$ only
conditioned on the input image is also trained through constraining its KL
divergence with the posterior distribution. The first term in Eq. (2) entails
the reconstruction loss, in our case the cross-entropy function as mentioned
earlier. At test time, the prior network produces latent samples to construct
the segmentation predictions.

Figure 1: Diagram of the PU-Net with a flow posterior.

####  3.2 Data & baseline experiments

We perform extensive experimental validation using the vanilla Probabilistic
U-Net with 2-/4-step planar and radial flow variants on processed versions of
the LIDC-IDRI (LIDC) [1] and the Kvasir-SEG [4] datasets. The preprocessed
LIDC dataset [14] transforms the 1,018 thoracic CT scans with four annotators
into 15,096 128$\times$128-pixel patches according to the method of [10, 2].
Each image has 4 annotations. The Kvasir-SEG dataset contains 1,000 polyp
images of the gastrointestinal tract from the original Kvasir dataset [11]. We
resize the images to be 128$\times$128 pixels as well and convert the images
to gray-scale. Example images of the datasets can be found in Appendix 0.C. As
for the NFs, we used the planar flow conform related work [14, 3] and also
experiment with the radial flow. These flows are usually chosen because they
are computationally the cheapest transformations that possess the ability to
expand and contract the distributions along a direction (planar) or around a
specific point (radial).

####  3.3 Performance evaluation

For evaluation, we deploy the Generalized Energy Distance (GED) (also known as
the Maximum Mean Discrepancy), which is defined as

$\displaystyle
D^{2}_{GED}(P_{pr},P_{out})=2\mathbb{E}\left[d(\mathbb{S},\mathbb{Y})\right]-\mathbb{E}\left[d(\mathbb{S},\mathbb{S}^{\prime})\right]-\mathbb{E}\left[d(\mathbb{Y},\mathbb{Y}^{\prime})\right],$
(3)

where $\mathbb{Y}$, $\mathbb{Y}^{\prime}$ and $\mathbb{S}$,
$\mathbb{S}^{\prime}$ are independent samples from the predicted distribution
and ground truth distributions $P_{pr}$ and $P_{gt}$, respectively. Here, $d$
is a distance metric, in our case, one minus the Intersection over Union
(1-IoU). When the predictions poorly match the ground truth, the GED is prone
to simply reward diversity in samples instead of accurate predictions because
the influence of the
$\mathbb{E}\left[d(\mathbb{Y},\mathbb{Y}^{\prime})\right]$ term becomes
dominant. Therefore, we also evaluate the Hungarian-matched IoU, using the
average IoU of all matched pairs for the LIDC dataset. We duplicate the
ground-truth set, hence matching it with the sample size. Since the Kvasir-SEG
dataset only has a single annotation per sample, we simply take the average
IoU from all samples. Furthermore, when the model correctly predicts the
absence of a lesion (i.e. no segmentation), the denominator of the metric is
zero and thus the IoU becomes undefined. In previous work, the mean excluding
undefined elements was taken over all the samples. However, since this is a
correct prediction, we award this with full score (IoU= 1) and compare this
approach with the method of excluding undefined elements for the GED.

To qualitatively depict the model performance, we calculate the mean and
standard deviation with Monte-Carlo simulations (i.e. sampling reconstructions
from the prior). All evaluations in this paper are based on 16 samples to
strike a right balance between sufficient samples and a justifiable
approximation, while maintaining minimal computational time.

####  3.4 Training details

The training procedure entails tenfold cross-validation using a learning rate
of $10^{-4}$ with early stopping on the validation loss based on a patience of
20 epochs. The batch size is chosen to be 96 and 32 for the LIDC and the
Kvasir-SEG dataset, respectively. The dimensionality of the latent space is
set to $L=6$. We split the dataset as 90-10 (train/validation and test) and
evaluate the test set on the proposed metrics. All experiments are done on an
11-GB RTX 2080TI GPU.

###  4 Results and discussion

####  4.1 Quantitative evaluation

We refer to the models by their posterior, either unaugmented (vanilla) or
with their n-step Normalizing Flow (NF). The results of our experiments are
presented in Table 1. In line with literature, it shown that the GED improves
with the addition of an NF. This hypothesis is tested using both a planar and
radial NF and observe that both have a similar effect. Furthermore, both the
average and Hungarian-matched IoU improve with the NF. We find that the 2-step
radial (2-radial) NF is slightly better than other models for the LIDC
dataset, while for the Kvasir-SEG dataset the planar models tend to perform
better. The original PU-Net introduced the variability capturing of
annotations into a Gaussian model. However, this distribution is not
expressive enough to efficiently capture this variability. The increase in GED
and average IoU performance from our experiments confirm our hypothesis that
applying NF to the posterior distribution of the PU-Net improves the accuracy
of the probabilistic segmentation. This improvement occurs because the
posterior becomes more complex and can thus provide more meaningful updates to
our prior distribution.

Including/excluding correct empty predictions did not result in a significant
difference in the metric value when comparing the vanilla models with the
posterior NF models. Our results show that the choice in NF has minimal impact
on the performance and suggest practitioners to experiment with both NFs.
Another publication in literature [14] has experimented with more complex
posteriors such as GLOW [6], where no increase in performance was obtained. In
our research, we have found that even a 4-step planar or radial NF (which are
much simpler in nature) can already be too complex for our datasets. A
possible explanation is that the variance in annotations captured in the
posterior distribution only requires a complexity that manifests from two NF
steps. This degree of complexity is then most efficient for the updates of the
prior distribution. More NF steps would then possibly introduce unnecessary
model complexity as well parameters for training, thereby reducing the
efficiency of the updates. Another explanation could be that an increase in
complexity of the posterior distribution does in fact model the annotation
variability in a better way. Nevertheless, not all information can be captured
by the prior, as it is still a Gaussian. In this case, a 2-step posterior is
close enough to a Gaussian for meaningful updates yet complex enough to be
preferred over a Gaussian distribution. We consider that for similar problems,
it is better to adopt simple NFs with a few steps only. However, we can
imagine the need for a more complex NF for other scenarios, where the varying
nature in the ground truth follows different characteristics, e.g.
encompassing non-linearities.

Dataset | Posterior | GED | IoU
---|---|---|---
Excl. | Incl. | Avg. | Hungarian
LIDC | Vanilla | 0.33 $\pm$ 0.02 | 0.39 $\pm$ 0.02 | — | 0.57 $\pm$ 0.02
2-planar | 0.29 $\pm$ 0.02 | 0.35 $\pm$ 0.03 | — | 0.57 $\pm$ 0.01
2-radial | 0.29 $\pm$ 0.01 | 0.34 $\pm$ 0.01 | — | 0.58 $\pm$ 0.01
| 4-planar | 0.30 $\pm$ 0.02 | 0.35 $\pm$ 0.04 | — | 0.57 $\pm$ 0.02
| 4-radial | 0.29 $\pm$ 0.02 | 0.34 $\pm$ 0.03 | — | 0.57 $\pm$ 0.01
Kvasir-SEG | Vanilla | 0.68 $\pm$ 0.18 | 0.69 $\pm$ 0.17 | 0.62 $\pm$ 0.07 | —
2-planar | 0.62 $\pm$ 0.05 | 0.63 $\pm$ 0.05 | 0.71 $\pm$ 0.01 | —
2-radial | 0.63 $\pm$ 0.03 | 0.64 $\pm$ 0.03 | 0.66 $\pm$ 0.06 | —
| 4-planar | 0.63 $\pm$ 0.06 | 0.67 $\pm$ 0.05 | 0.71 $\pm$ 0.04 | —
| 4-radial | 0.65 $\pm$ 0.04 | 0.67 $\pm$ 0.05 | 0.65 $\pm$ 0.07 | —

Table 1: Test set evaluations on the GED and IoU based on 16 samples. Further
distinction in the GED is made on whether the correct empty predictions are
included. The IoU is evaluated with the Hungarian-matching algorithm and
averaged with the LIDC and Kvasir-SEG dataset, respectively.

We have also compared the vanilla, 2-planar and 2-radial models by depicting
their GEDs based on sample size (Appendix 0.D). As expected, the GEDs decrease
as the number of samples increase. It is also evident that the variability in
metric evaluations is less for models with an NF posterior. The NF posteriors
consistently outperform the vanilla PU-Net for the LIDC and Kvasir-SEG
datasets.

####  4.2 Qualitative evaluation

The mean and standard deviation based on 16 segmentation reconstructions from
the validation set is shown in Figures 3 and 3. Ideally, it is expected to
obtain minimal uncertainty at the center of the segmentation, because
annotations agree on the center area most of the time for our datasets. This
also implies that the mean of the center should be high because of the
agreement of the annotators. For both datasets, the means of our sampled
segmentations match well with the ground truths and have high values in the
center areas corresponding to good predictions. Furthermore, the PU-Net
without an NF shows uncertainty at both edges and segmentation centers. In
contrast, for all NF posterior PU-Net models, the uncertainty is mostly on the
edges alone. A high uncertainty around the edges is also expected, since at
those areas the annotators almost always disagree. From this, we can conclude
that NF posterior models are better at quantifying the aleatoric uncertainty
of the data. Even though there is no significant quantitative performance
difference between the NF models, there is a well distinguishable difference
in the visual analysis. In almost all cases, it can be observed that the
planar is better than the radial NF posterior in learning the agreement
between the segmentation centers. We also investigated the prior distribution
to determine if it captures the ambiguity that exist in the input image. In
Appendix 0.E, we show the prior distribution variance for different test set
input images. We qualitatively observe that with increasing variance, the
subjective assessment of the annotation difficulty increases. This suggests
the possibility of obtaining an indication of the uncertainty in a test input
image without sampling and evaluating the segmentation reconstructions.

The prior distribution is an area that needs to be further explored, since
this is still assumed Gaussian. We hypothesize that augmenting the prior with
an NF could result in further improvements. Future work will also include an
investigation into the correlation between the prior and segmentation
variance. A limiting factor of the proposed model is the use of only a single
distribution. We consider that when using flexible distributions at multiple
scales, the overall model will further improve.

Figure 2: Reconstructions of the LIDC test set.

Figure 3: Reconstructions of the Kvasir-SEG test set.

###  5 Conclusion

Quantifying uncertainty in image segmentation is very important for decision-
making in the medical domain. In this paper, we propose to use the broader
concept of Normalizing Flows (NFs) for modeling both single- and multi-
annotation data. This concept allows more complex modeling of aleatoric
uncertainty. We consider modeling of the posterior distribution by Gaussians
too restrictive to model variability. By augmenting the model posterior with a
planar or radial NF, we attain up to 14% improvement in GED and 13% in IoU,
resulting in a better quantification of the aleatoric uncertainty. We propose
that density modeling with NFs is something that should be experimented with
throughout other ambiguous settings in the medical domain, since we are
confident this will result in valuable information for further research. A
significant improvement has been found through only augmenting the posterior
distribution with NFs, whereas little-to-none investigations have been made
into the effect of additionally augmenting the prior distribution and is
suggested for future work. Moreover, we suggest augmenting other architectures
that aim to capture uncertainty and variability through a learnt probability
distribution with Normalizing Flows.

## References

  * [1] Armato III, S., Mclennan, G., Bidaut, L., McNitt-Gray, M., Meyer, C., Reeves, A., Zhao, B., Aberle, D., Henschke, C., Hoffman, E., Kazerooni, E., Macmahon, H., Beek, E., Yankelevitz, D., Biancardi, A., Bland, P., Brown, M., Engelmann, R., Laderach, G., Clarke, L.: The lung image database consortium (lidc) and image database resource initiative (idri): A completed reference database of lung nodules on ct scans. Medical Physics 38, 915–931 (01 2011). https://doi.org/10.1118/1.3528204
  * [2] Baumgartner, C.F., Tezcan, K.C., Chaitanya, K., Hötker, A.M., Muehlematter, U.J., Schawkat, K., Becker, A.S., Donati, O., Konukoglu, E.: Phiseg: Capturing uncertainty in medical image segmentation (2019)
  * [3] van den Berg, R., Hasenclever, L., Tomczak, J.M., Welling, M.: Sylvester normalizing flows for variational inference (2019)
  * [4] Jha, D., Smedsrud, P.H., Riegler, M.A., Halvorsen, P., de Lange, T., Johansen, D., Johansen, H.D.: Kvasir-seg: A segmented polyp dataset (2019)
  * [5] Kendall, A., Gal, Y.: What uncertainties do we need in bayesian deep learning for computer vision? CoRR (2017), http://arxiv.org/abs/1703.04977
  * [6] Kingma, D.P., Dhariwal, P.: Glow: Generative flow with invertible 1x1 convolutions (2018)
  * [7] Kingma, D.P., Welling, M.: Auto-encoding variational bayes (2014)
  * [8] Kobyzev, I., Prince, S., Brubaker, M.: Normalizing flows: An introduction and review of current methods. IEEE Transactions on Pattern Analysis and Machine Intelligence p. 1–1 (2020). https://doi.org/10.1109/tpami.2020.2992934, http://dx.doi.org/10.1109/TPAMI.2020.2992934
  * [9] Kohl, S.A.A., Romera-Paredes, B., Maier-Hein, K.H., Rezende, D.J., Eslami, S.M.A., Kohli, P., Zisserman, A., Ronneberger, O.: A hierarchical probabilistic u-net for modeling multi-scale ambiguities (2019)
  * [10] Kohl, S.A., Romera-Paredes, B., Meyer, C., De Fauw, J., Ledsam, J.R., Maier-Hein, K.H., Eslami, S., Rezende, D.J., Ronneberger, O.: A probabilistic u-net for segmentation of ambiguous images. arXiv preprint arXiv:1806.05034 (2018)
  * [11] Pogorelov, K., Randel, K., Griwodz, C., de Lange, T., Eskeland, S., Johansen, D., Spampinato, C., Dang Nguyen, D.T., Lux, M., Schmidt, P., Riegler, M., Halvorsen, P.: Kvasir: A multi-class image dataset for computer aided gastrointestinal disease detection (06 2017). https://doi.org/10.1145/3083187.3083212
  * [12] Rezende, D.J., Mohamed, S.: Variational inference with normalizing flows (2016)
  * [13] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: International Conference on Medical image computing and computer-assisted intervention. pp. 234–241. Springer (2015)
  * [14] Selvan, R., Faye, F., Middleton, J., Pai, A.: Uncertainty quantification in medical image segmentation with normalizing flows (2020)
  * [15] Sohn, K., Lee, H., Yan, X.: Learning structured output representation using deep conditional generative models. Advances in neural information processing systems 28, 3483–3491 (2015)

## Appendices

##  Appendix 0.A Probabilistic U-Net objective

The loss function of the PU-Net is based on the standard ELBO and is defined
as

$\displaystyle\mathcal{L}$
$\displaystyle=-\mathbb{E}_{q_{\phi}(\mathbf{z}|\mathbf{s},\mathbf{x})}[\,\operatorname{log}p(\mathbf{s}|\mathbf{z},\mathbf{x})\,]+\operatorname{KL}\left(\,q_{\phi}(\mathbf{z}|\mathbf{s},\mathbf{x})||p_{\psi}(\mathbf{z}|\mathbf{x})\,\right),$
(4)

where the latent sample $\mathbf{z}$ from the posterior distribution is
conditioned on the input image $\mathbf{x}$, and ground-truth segmentation
$\mathbf{s}$.

##  Appendix 0.B Planar and radial flows

Normalizing Flows are trained by maximizing the likelihood objective

$\displaystyle\log p(\mathbf{x})=\log
p_{0}\left(\mathbf{z}_{0}\right)-\sum_{i=1}^{K}\log\left(\left|\operatorname{det}\frac{df_{i}}{d\mathbf{z}_{i-1}}\right|\right).$
(5)

In the PU-Net, the objective becomes

$\displaystyle\log q(\mathbf{z}|\mathbf{s},\mathbf{x})=\log
q_{0}(\mathbf{z}_{0}|\mathbf{s},\mathbf{x})-\sum_{i=1}^{K}\log\left(\left|\operatorname{det}\frac{df_{i}}{d\mathbf{z}_{i-1}}\right|\right),$
(6)

where the i-th latent sample $\mathbf{z}_{i}$ from the Normalizing Flow is
conditioned on the input image $\mathbf{x}$, and ground-truth segmentation
$\mathbf{s}$.

The planar flow expands and contracts distributions along a specific
directions by applying the transformation

$f(\mathbf{x})=\mathbf{x}+\mathbf{u}h(\mathbf{w}^{T}\mathbf{x}+\mathbf{b}),$
(7)

while the radial flow warps distributions around a specific point with the
transformation

$f(\mathbf{x})=\mathbf{x}+\frac{\beta}{\alpha\left|\mathbf{x}-\mathbf{x}_{0}\right|}(\mathbf{x}-\mathbf{x}_{0}).$
(8)

##  Appendix 0.C Dataset images

Here example images from the datasets used in this work can be seen. Figure 4
depicts four examples from the LIDC dataset. On the left in the figure the 2D
CT image containing the lesion, followed by the four labels made by four
independent annotators is shown. In Figure 5, eight examples from the Kvasir-
SEG dataset is depicted. An endoscopic image with its ground truth label can
be seen.

Figure 4: Example images from the LIDC dataset.

Figure 5: Example images from the Kvasir-SEG dataset.

##  Appendix 0.D Sample size dependent GED

The GED evaluation is dependent on the number of reconstructions sampled from
the prior distribution. Figure 6 depicts this relationship for the vanilla,
2-planar and 2-radial posterior models. The uncertainty in the values
originate from the changing results when training with ten-fold cross
validation. One can observe that with increasing sample size, the GED as well
as the associated uncertainty decrease. This is also the case when the
posterior is augmented with a 2-planar or 2-radial flow. Particularly, the
uncertainty in the GED evaluation significantly decreases.

(a) LIDC test set

(b) Kvasir-SEG test set

Figure 6: The GED based on sample size evaluated on the vanilla, 2-planar and
2-radial models.

##  Appendix 0.E Prior distribution variance

We investigated whether the prior distribution captures the degree of
ambiguity in the input images. For every input image $\mathbb{X}$, we obtain a
latent L-dimensional mean and standard deviation vector of the prior
distribution $P(\bm{\mu},\bm{\sigma}|\mathbb{X})$. The mean of the latent
prior variance vector $\mu_{LV}$, is obtained from the input images in an
attempt to quantify this uncertainty. Figure 7 shows this for several
different input images of the test set. As can be seen, the mean variance over
the latent prior increases along with a subjective assessment of the
annotation difficulty.

Figure 7: Depicted in the CT image is the mean of the prior distribution
variance of the 2-planar model. We show the input CT image, its average
segmentation prediction (16 samples) and ground truth from four annotators.


QNet: A Quantum-native Sequence Encoder Architecture

Wei Day
Department of Computer Science

National Central University

Taoyuan City, Taiwan

Hao-Sheng Chen
Department of Computer Science

National Central University

Taoyuan City, Taiwan

Min-Te Sun
Department of Computer Science

National Central University

Taoyuan City, Taiwan

This work proposes QNet, a novel sequence encoder model that entirely inferences on the quantum computer using a minimum number of qubits. Let $n$ and $d$ represent the length of the sequence and the embedding size, respectively. The dot-product attention mechanism requires a time complexity of $O(n^2 \cdot d)$, while QNet has merely $O(n+d)$ quantum circuit depth. In addition, we introduce ResQNet, a quantum-classical hybrid model composed of several QNet blocks linked by residual connections, as an isomorph Transformer Encoder. We evaluated our work on various natural language processing tasks, including text classification, rating score prediction, and named entity recognition. Our models exhibit compelling performance over classical state-of-the-art models with a thousand times fewer parameters. In summary, this work investigates the advantage of machine learning on near-term quantum computers in sequential data by experimenting with natural language processing tasks.

quantum machine learning, natural language processing, deep learning model

§ INTRODUCTION

Quantum computer hardware technologies are maturing, making quantum algorithms a possible solution to reduce the training cost of neural networks. When this paper was written, a quantum computer with 127 qubits was revealed <cit.>. Multiple reports <cit.> show that Quantum Machine Learning (QML) outperforms classical machine learning in certain situations, but the actual capability of QML remains to be discovered. Most QML models are built on top of Variational Quantum Circuits (VQC), the quantum algorithms that depend on free parameters. Based on VQC, multiple quantum Feedforward neural networks capable of universal quantum computation have been proposed <cit.> to exploit the potential of quantum computers in machine learning and attempt to train networks more effectively.

It is also worth mentioning that utilizing quantum computers for machine learning is a challenging task. Other than the gradient vanishing or exploding problem that already exists in classical computers, quantum computers will incur decoherence after a long period of execution in the noisy intermediate-scale quantum (NISQ) era <cit.>. In addition, the resource of quantum computing is limited as quantum computers are still under development. Quantum machine learning researchers must propose models that can both be verified on NISQ devices and are extendable for large-scale quantum computers in the future.

On the other hand, machine learning is another fast-growing domain that is good at recognizing patterns and solving many real-life problems. A sequence-to-sequence deep learning model, Transformer <cit.> architecture, has achieved rapid and widespread dominance in various tasks, especially the models that use Transformer Encoder as their main component, such as the BERT <cit.> model and Vision Transformer <cit.>. Each block in the Transformer Encoder comprises a Multi-head self-attention and a Feedforward layer. The former is an inductive bias that connects each token in the input through a relevance-weighted basis of every other token, and the latter is a parameterized linear transformation on each token.

However, one crucial shortcoming of Transformer is the time complexity of Multi-head self-attention. It performs a matrix multiplication operation that needs the time complexity of $O(n^2 \cdot d)$ to relate the tokens, where $n$ and $d$ represent sequence length and embedding dimensions, respectively. This makes the time cost to input the long sequence to the model impractical. Multiple works <cit.> have attempted to enhance Transformer Encoder to improve either performance or accuracy, and in our observations, accuracy is often sacrificed for speed.

In this work, we propose QNet, a sequence encoder block inspired by the Transformer encoder that entirely inferences on quantum computers. A sequence encoder is a model that reads the input sequence and summarizes the information into a context vector representing a certain meaning of the input, which is usually the prediction target of a task. In addition to QNet, ResQNet, the model composed of residual connected QNet blocks, is proposed. ResQNet has shown state-of-the-art performance while reducing the complexity of the model on various natural language processing tasks.

In the experiment sections, four datasets are used for evaluation. On the ColBERT sentence emotion classification dataset, QNet and ResQNet resulted in an accuracy of 89.84% and 91.17% with dozens of parameters, while other models have approximate results but with parameters of higher magnitudes. On the Stackoverflow Question classification dataset, QNet and ResQNet achieve higher accuracy than other models. For the MSRA named-entity recognition task, experimented models are challenged to assign labels to every input token in a heavily imbalanced distribution. However, QNet and ResQNet both show compelling results on the MSRA dataset, proving the effectiveness of such architecture design.

§ PRELIMINARY

§.§ Attention In Sequential Task

With the development of deep learning, Natural Language Processing (NLP) technology has become progressively mature. NLP is a technology that enables computers to analyze human language, which has a sequential context relationship. Series data is traditionally processed with Recurrent Neural Networks (RNN) that have difficulty performing parallel operations and easily face gradient vanishing issues. Thus, Google proposed a network architecture that does not use RNN and CNN but only the self-attention mechanism - Transformer <cit.>, in which each block is composed of Multi-head attention and a Feedforward layer. In recent years, Transformer has achieved outstanding results in tasks such as sentiment analysis <cit.>, machine translation <cit.>, speech recognition <cit.>, and dialogue robots <cit.>.

The Transformer architecture has inspired multiple large-scale NLP models. For instance, Bidirectional Encoder Representations from Transformers (BERT) <cit.> is developed by Google for NLP pre-training, mainly composed of a stack of Transformer encoders and a classification layer. It is designed to help computers understand the meaning of ambiguous language in the text by using surrounding text to establish context.

Equation <ref> is the attention mechanism that flexibly outputs the most relevant parts of the input sequence, $Q$ and $K$ are vectors used to compute the relation weight of every two tokens, and $V$ is a vector used to add the weight to retrieve the relation information. These vectors usually come from the same source but are weighted linear transformed to introduce differences to each.

\begin{equation} \label{equ:attention}
Attention(Q, K, V) = softmax(\frac{QK^T}{\sqrt{d_k}})V
\end{equation}

Recent works have shown the potential mathematics transformations that can replace Multi-head self-attention and achieve approximately the same performance. In fact, the approach of replacing self-attention with a transpose operation and a Feedforward layer has proved to be able to achieve convincing results. <cit.>

The work in <cit.> starts the question about the primitive property of the attention mechanism. The work in <cit.> shows that standard un-parameterized discrete Fourier transform can speed up Transformer encoder architectures, with limited accuracy costs, by replacing the self-attention sublayer with simple linear transformations that mix input tokens.

§.§ Quantum Machine Learning

Quantum machine learning is a category of machine learning that makes use of quantum computers, that is, utilizing the properties of qubits and quantum gates. Instead of building machine learning models that are purely supported on quantum computers, models designed in the quantum-classical hybrid structure are more common for NISQ devices. One of the reasons is that the input data are permanently stored on classical computers because the decoherence of quantum computers will corrupt the data. In quantum-classical hybrid models, the quantum computer is either used to provide the quantum data by extracting input features or employing a quantum machine learning algorithm as the classifier.

In this work, our models are used as representation encoders that pipe the output to a classical fully-connected layer. However, QNet is not restricted to being a backbone of classical classifiers since it can be directly connected to a quantum neural network to make a pure quantum model.

§.§.§ Quantum Fourier Transform

Quantum Fourier transform <cit.> is the quantum implementation of the discrete Fourier transform over the amplitudes of a quantum state that converts the amplitudes from the time domain to the frequency domain.

Similar to discrete Fourier transform, Quantum Fourier transform maps the quantum state from $|X\rangle = \sum_0^{N-1} x_j|j\rangle$ to $|Y\rangle = \sum_0^{N-1} y_k |k\rangle$ according to Equation <ref>, where $\omega^{jk}_N = e^{2\pi i \frac{jk}{N}}$.

\begin{equation} \label{equ:qft}
y_k = \frac{1}{\sqrt{N}} \sum_0^{N-1} x_j \omega_N^{jk}
\end{equation}

The unitary matrix can also express Quantum Fourier transform as Equation <ref> with $\omega$ defined the same as above.

\begin{equation} \label{equ:qft_u}
U_{QFT} = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1}  \sum_{k=0}^{N-1} \omega_{N}^{jk} |k\rangle \langle j|
\end{equation}

This work uses the Quantum Fourier Transform in the "Mixture Learning" layer to blend multiple individual qubits representing the same embedding dimension with multiple tokens to create an information-mixed intermediate state.

§.§.§ Variational Quantum Eigensolver

The Variational Quantum Eigensolver (VQE) <cit.> is a form of the quantum circuit with configurable parameters iteratively tuned by a classical computer. It can provide solutions in regimes that lie beyond the research of conventional algorithms. VQE finds an optimal transformation in a set of unitary gates that depends on the design of the quantum circuit. Fig. <ref> presents a sample VQE circuit where $\alpha, \beta, \gamma$ are sets of learnable parameters to rotate qubits in 3 axes. Entanglement gates usually follow rotation gates to let qubits interact with each other to exchange information.

@C=3em @R=.5em
R(α^1_1, β^1_1, γ^1_1)     1

R(α^1_2, β^1_2, γ^1_2)         1

R(α^1_3, β^1_3, γ^1_3)             -2

Classic single-Layer VQE with 3 quantum wires.

The VQE approach has been shown to be flexible in circuit depth and insensitive to the presence of noises <cit.>. Therefore, while there is still a lack of quantum error correction and fault-tolerant quantum computation in the NISQ era, quantum machine learning methods driven by variational quantum circuits can circumvent the complex quantum flaws in the current quantum devices.

§.§ Word Embedding Sparsity

Multiple works <cit.> <cit.> have shown evidence that the information contained in the word embedding is sparse and can be factored with many fewer elements. The word embedding structure inspired by quantum entanglement, word2ket <cit.> is one of the most fantastic works. The experimental results show that after a 34,000-fold reduction in trainable parameters, it can still match the scores of the original unreduced configurations.

These works indicate the potential of using fewer embedding dimensions to achieve state-of-the-art performance, especially by utilizing quantum entanglement. The model interpretability can also be profitable by examining fewer parameters.

§ RELATED WORK

§.§ Quantum Recurrent Neural Network

Prior to this work, the quantum recurrent neural network (QRNN) is proposed as a pure quantum version implementation of recurrent neural networks. <cit.> Fig. <ref> is the QRNN cell where qubits are divided into hidden state wires, which hold the hidden state of former cells and pass to latter units, and input state wires, the temporary wires for the entanglement gates to integrate input to the hidden state.

The cell of Quantum Recurrent Neural Network, the N gates are the controlled quantum neurons.

The work of QRNN shows the benefits of pure quantum neural network architectures. It can be used as a generative model based on the nature of quantum gates that is unitary and can analyze what extent the unitary nature of the network counteracts the vanishing gradient problem.

However, in the NISQ era, the entangled qubits to decoherence could be easily caused by the noises in deep circuits, so it might be unfeasible to employ QRNN in near-term quantum devices since the circuit depth of the QRNN is $O(n \times d)$ in which $n$ is the length of the sequence and $d$ is the dimension of the hidden state.

§.§ Quantum Long Short-Term Memory

In the proposed Quantum Long Short-Term Memory (QLSTM), hybrid quantum computing is being used to enhance the data before or after gates in the Long Short-Term Memory cell by conducting transformation with VQE. The cell of QLSTM is shown in Fig. <ref>.

The cell of Quantum Long-Short-Term Memory.

The work of QLSTM shows that, in some cases, the predictions of QLSTM can fit better and converge much faster than LSTM. But the measurement operation on quantum computers is time expensive, and each VQE in QLSTM requires measurement to continue to compute other parts of the cell in the classical computer. Since the model performance improvement is slight, it is not beneficial to employ such architecture in a hybrid system of quantum computers and classical computers that would have bottlenecks in transferring data between them.

§.§ Quantum Enhanced Transformer

Transformer architecture revolutionized the analysis of sequential data. It is intuitive to attempt to integrate such a state-of-the-art model with quantum computers to seek improvement. The work <cit.> that proposed Q-Transformer is inspired by QLSTM and is also a hybrid model in which VQE is used to enhance the input of the Attention.

The inputs of the self-attention are often transformed with weight as Equ. <ref>. The concept of Q-Transformer is to replace the linear transformation $W_Q$, $W_K$, and $W_V$ with three VQE, respectively.

\begin{equation} \label{equ:weighted-attention}
Attention(QW_Q, KW_K, VW_V)
\end{equation}

The Q-Transfomer was experimented on the IMDB dataset and took about 100 hours to train a single epoch. However, in the end, the author did not present the result of training Q-Transformer.

§ METHOD

§.§ Problem Formulation

This paper aims to design a quantum machine learning model with a similar architecture to BERT, a sequence-to-sequence model, and to explore how much improvement it can achieve. Using the sequence-to-sequence pre-trained model as a backbone can also adapt the model to other tasks, such as text classification or image segmentation.

The methods of this paper are proposed under the following assumptions.

* The NISQ device can compute any general gate in $O(1)$ time complexity. General gates include two standard entanglement gates (CNOT and SWAP) and arbitrary rotation gates.

* There is a finite number of qubits on the NISQ device.

* The model inputs can be chopped and padded into the same length.

§.§ QNet

layer = [draw, text centered, text width=14em, minimum height=1.5em, rounded corners]
ffblock = [layer, fill=cyan!30]
qftblock = [layer, fill=orange!30]
measure = [layer, fill=green!10]
encode = [layer, fill=red!20]
params = [layer, fill=red!20]
[node distance=2.7em]
(output) [text centered, text width=14em] Outputs;
(measure) [measure] [below of=output] Pauli-Z Measurement;
(ffblock) [ffblock] [below of=measure] Positional Feedforward;
(qft) [qftblock] [below of=ffblock] Mixture Learning;
(encode) [encode] [below of=qft] Word Embedding Encoding;
(parameters) [params] [below of=encode] Circuit Arrangement;
(input) [text centered, text width=14em] [below of=parameters] Inputs;

[on background layer]
[fill=cyan!20, rounded corners, fit=(encode) (qft) (ffblock) (measure) ] ;
[fill=orange!20, rounded corners, fit=(input) (parameters)] ;
[fill=orange!20, rounded corners, fit=(output)] ;
[draw, densely dashed, rounded corners, fit=(qft) (ffblock), label=right:$\times N$] ;

[->] (input) – (parameters);
[->] (parameters) – (encode);
[->] (encode) – (qft);
[->] (qft) – (ffblock);
[->] (ffblock) – (measure);
[->] (measure) – (output);

The QNet Encoder Block Architecture

The QNet encoder architecture is shown in Fig. <ref>. The blocks within the cyan box are the components that execute on quantum computers and the blocks within the orange box are the components that perform on classical computers. First, the "Circuit Arrangement" layer prepares the parameters the quantum circuit requires and assigns gates to both input and parameters. Second, the "Word Embedding Encoding" layer encodes the inputs into qubits. Then, the "Mixture Learning" layer introduces the mechanism to learn the token relationships. Next, the "Positional Feedforward" layer performs a learnable transformation on each token. Finally, qubits are measured to return the quantum data to the classical computer. Note that the dot-surrounded area can be repeated multiple times to increase the parameters and depth of the model.

The derivation and circuit design are introduced in detail in the following sections.

§.§.§ Word Embedding Encoding

Without modifying embeddings to encode positional information like Positional Encoding in Transformer, QNet directly utilizes another axis of the qubit to store the positional information. Word embeddings are transformed to the volume of a qubit, the rotation on Pauli-X. The position of the word is encoded as the phase of the qubit, the angle on Pauli-Z, so the positional information is the distributed angles in the range of $[0, \pi]$

\begin{equation} \label{equ:word_embedding}
x \rightarrow |\psi_x\rangle = \prod_{i=1}^n \prod_{j=1}^d {R^{i*d+j}_z( \frac{(i-1) \pi}{n} ) R^{i*d+j}_x(x^i_j)}\;|0^{\otimes n\times d}\rangle
\end{equation}

The transformation of the quantum state can be described by Equation <ref>. In the equation, $x$ is the input token array, the superscript denotes the index of the token, and the subscript denotes the index of the embedding. Here, $n$ is the length of the input sequence, and $d$ is the embedding dimension.

@C=3em @R=.4em
|0⟩     R_x(x^1_1)     R_z(0)     |ψ^1_1⟩

|0⟩     R_x(x^2_1)     R_z(0)     |ψ^2_1⟩

|0⟩     R_x(x^1_2)     R_z(π/2)     |ψ^1_2⟩

|0⟩     R_x(x^2_2)     R_z(π/2)     |ψ^2_2⟩

The quantum circuit of Word Embedding Quantum Encoding for 2 words with 2 embeddings.

§.§.§ Mixture Learning

A self-attention mechanism is an attempt to implement the action of selectively concentrating on a few relevant things while ignoring others in deep neural networks. However, directly implementing dot-product attention in the Transformer Encoder is impractical to realize in the current scale of NISQ devices because, after the operation, the swap test will corrupt qubits and require duplicate qubits for further calculation, which will need at least an additional $O(n \times d)$ number of qubits.

Instead of replicating the original self-attention, this work uses an alternative solution that is based on the different waveforms generated by Quantum Fourier Transform. The unitary of Quantum Fourier Transform is presented in Equation <ref>, where $n$ is the length of the input sentence and the $N$-th root of unitary is defined as $\omega^{jk}_N = e^{2\pi i \frac{jk}{N}}$.

\begin{equation} \label{equ:u_qft}
U_{QFT} = \frac{1}{\sqrt{n}} \sum_{j=0}^{n-1}  \sum_{k=0}^{n-1} \omega _{n}^{jk} |k\rangle \langle j|
\end{equation}

Take an input length of 4 as an example. The matrix of the $U_QFT$ under the condition of $n = 4$ is presented in Equation <ref>. After applying the unitary, the quantum state would become a mixture where each original state is selected with the weight of a waveform amplitude.

\begin{equation} \label{equ:matrix_qft}
U_{QFT} |\psi\rangle =
\begin{bmatrix}
x_1 + x_2 + x_3 + x_4 \\
x_1 + x_2 \omega_n^1 + x_3 \omega_n^2 + x_4 \omega_n^3 \\
x_1 + x_2 \omega_n^2 + x_3 \omega_n^4 + x_4 \omega_n^6\\
x_1 + x_2 \omega_n^3 + x_3 \omega_n^6 + x_4 \omega_n^9
\end{bmatrix}
\end{equation}

To apply a learnable relation weight transformation, single qubit rotation, as shown in Equation <ref>, is applied to every qubit involved in the mixture learning with the same weight. The whole unitary can be written as Equation <ref> where $\otimes$ is the Kronecker product operator and $w$ are trainable parameters. The reason that the exact weight is being used is that we do not wish to modify the original quantum state too much. For instance, if there is no requirement to have information on relationships, the $U_W'$ should be an identical matrix $I$, so instead of learning $O(2^n)$ parameters, optimizing a constant number of parameters to $I$ is much easier.

\begin{equation} \label{equ:single_qubit}
U_W = \begin{bmatrix}
w_1 & w_2 \\
w_3 & w_4
\end{bmatrix}
\end{equation}

\begin{equation} \label{equ:span_Uw}
U'_W = U_W \otimes U_W \otimes ... U_W \otimes U_W
\end{equation}

After the learnable transformation, the inverse Quantum Fourier Transform unitary, represented by $U_{QFT}^\dag$, is applied. If nothing is learned, the quantum state would be transformed back to the same before $U_{QFT}$, or else such transformation would let qubits carry additional information from other tokens. The overall mixture learning operation can be presented as Equation <ref>.

\begin{equation} \label{equ:mixture_learning}
|\psi'\rangle = U_{mix} |\psi\rangle = U_{QFT}^\dag U'_W U_{QFT} |\psi\rangle
\end{equation}

In order to create a mixture state of different embedding dimensions, Mixture Learning is employed for every single embedding dimension. The formula is shown as Equation <ref> where $d$ is the embedding dimension.

\begin{equation} \label{equ:mixture_learning_ops}
|\psi'\rangle = U_{mix_1}\ldots U_{mix_d}|\psi\rangle
\end{equation}

Therefore, the Mixture Learning layer is made up of Quantum Fourier Transforms with parameterized transformation performed on all tokens for each qubit in the embedding. The trainable quantum circuit is shown in Fig. <ref>, where $\alpha, \beta, \gamma$ are parameters that use rotation gates to operate $U_W$.

@C=3em @R=.4em
|ψ^1_1⟩     1 𝒬ℱ𝒯      R(α_1, β_1, γ_1)     1 𝒬ℱ𝒯^†

|ψ^1_2⟩      𝒬ℱ𝒯      R(α_1, β_1, γ_1)      𝒬ℱ𝒯^†

|ψ^2_1⟩     1 𝒬ℱ𝒯      R(α_2, β_2, γ_2)     1 𝒬ℱ𝒯^†

|ψ^2_2⟩      𝒬ℱ𝒯      R(α_2, β_2, γ_2)      𝒬ℱ𝒯^†

Circuit of Mixture Learning layer.

§.§.§ Positional Feedforward

In this work, we propose a special feedforward model that aims to construct a viable machine-learning model with the existing NISQ-era technology. Unlike traditional quantum neural networks <cit.>, which are known to have a three-dimensional architecture with each neuron represented by a qubit and generating plenty of auxiliary qubits, the feedforward layer used in QNet abandons the intermediate qubits to simplify the Feedforward layer using the structure inspired by Grover's algorithm, and the circuit is shown in Fig. <ref>.

@C=1em @R=.4em
|ψ^1_1⟩     R(α_3,β_3,γ_3)     1𝒢     R(α_4,β_4,γ_4)     1𝒢

|ψ^2_1⟩     R(α_5,β_5,γ_5)     𝒢     R(α_6,β_6,γ_6)     𝒢

|ψ^1_2⟩     R(α_3,β_3,γ_3)     1𝒢     R(α_4,β_4,γ_4)     1𝒢

|ψ^2_2⟩     R(α_5,β_5,γ_5)     𝒢     R(α_6,β_6,γ_6)     𝒢

QNet Feedforward with two wires.

In a typical transformer architecture, the Feedforward layer has two fully connected layers with one activation function in between. Here, we use a similar arrangement by putting two VQEs separated by two transformation functions $\mathbf {G}$ surrounding the latter VQE circuit. The process can be demonstrated as Equation <ref>.

\begin{equation} \label{equ:Feedforward}
|\hat{\psi^1}\ldots\hat{\psi^m}\rangle = U_1U_\mathbf{G}U_2U_\mathbf{G}|\psi^1\rangle \ldots U_1U_\mathbf{G}U_2U_\mathbf{G}|\psi^m\rangle
\end{equation}

The $\mathbf{G}$ is Grover's operator <cit.>, which will flip the amplitude of the quantum state, whose unitary is expressed in Equation <ref>. Since the non-linear activation function can not exist on linear quantum systems, the $\mathbf{G}$ holds a different purpose than the activation function, which is to allow VQE to be performed on a different basis. Note that $\mathbf{G}$ is also computationally efficient since it contains only one multi-qubit gate.

\begin{equation} \label{equ:U_G}
U_\mathbf{G} = H^{\otimes m}(2|\psi\rangle\langle \psi|- I)H^{\otimes m}
\end{equation}

The circuit of $\mathbf{G}$ is shown in Fig. <ref>.

@C=3em @R=.4em
|ψ^1_1⟩     H     1     H

|ψ^2_1⟩     H     1     H

|ψ^3_1⟩     H         H

Circuit of $\mathbf{G}$

§.§.§ Measurement

In the end, quantum measurements on Pauli-Z are performed for every qubit. The measured result is a 1-D tensor where all entries lie in the range of $[-1, 1]$. In order to pass the output into the next block, that is, making the QNet a sequence-to-sequence encoder model, flattened tensors are reshaped to the shape of input.

§.§ ResQNet

layer = [draw, text centered, text width=14em, minimum height=1em, rounded corners]
denseblock = [layer, fill=violet!10]
outputblock = [layer, fill=blue!10]
linear = [layer, fill=orange!10]
qnet = [layer, fill=green!10]
encode = [layer, fill=red!20]

(output) [outputblock] Output Projection;
(dense) [denseblock] [below of=output] Linear;
(add) [font=] [below of=dense] $\oplus$;
(qnet) [qnet] [below of=add] QNet Encoder;
(linear) [linear] [below of=qnet] Linear Transformation;
(encode) [encode] [below of=linear] Embedding Layer;

[on background layer]
[draw, densely dashed, rounded corners, fit=($(linear)-(3, 0.5)$) ($(add)+(3, 0.4)$), label=right:$\times N$] ;
[->] (encode) – (linear);
[->] (linear) – (qnet);
[->] (qnet) – (add);
[->] (add) – (dense);
[->] (dense) – (output);

[->] ($(linear)+(0,-0.45)$) – ($(linear)+(2.7,-0.45)$) – ($(add)+(2.7,0)$) – (add);

The ResQNet - the model architecture.

The ResQNet is a quantum-classical hybrid model composed of multiple residual-connected QNet blocks to mimic the architecture of the Transformer Encoder, as shown in Fig. <ref>. In the "Linear Transformation" layer, the input is multiplied by a vector on the dimension of the embedding to scale the weight of each embedding. After QNet Encoder, the previous data are added to the output of QNet and normalized.

The derivation and architecture design are introduced in detail in the following sections.

§.§.§ Linear Transformation

The mathematics transformation of this layer is to let classical data be changed into a preferable scale to encode onto the quantum circuit. Practically, the feature matrix is multiplied to a vector of length $d$ to scale variables in the embedding axis, and it can be written as Equation <ref>, where $A$ is the feature matrix and $w$ are the parameters in this linear transformation.

\begin{equation} \label{equ:resqnet_linear}
output = A \times
\begin{bmatrix}
w_1 & 0 & \dots & 0 \\
0 & w_2 & 0 & \vdots \\
\vdots & 0 & \ddots &  \vdots \\
0 &  \dots & \dots &  w_{d}
\end{bmatrix}
\end{equation}

The design is based on the concept that functionality of QNet can be highly relied on in this model because, instead of the traditional feedforward layer that uses $O(d^2)$ parameters to convert the word embedding to a different meaning, the linear transformation here only uses $O(d)$ parameters with the idea to adjust input for the quantum circuit.

§.§.§ QNet Encoder

In our experiment configuration, QNet with a depth of one is used as the QNet block in the ResQNet. It is based on the idea of replicating the architecture of the Transformer Encoder but with the replacement of Multi-head attention blocks and positional feedforward blocks. Our number of quantum measurements is significantly fewer than the previous quantum model, QLSTM, since the transformer architecture is usually not too deep, e.g., the original BERT only used 12 blocks of Transformer Encoder.

§.§ QNet Complexity Analysis

In this section, we examine the complexity of QNet and contrast it with BERT and FNet. On a classical computer, the time complexity of a model is an asymptotic function of the number of basic arithmetic operations used. If the task is parallelizable, it would be divided by the number of processes. However, the qubits on quantum computers are often executed independently, so execution time is more likely to equal the depth of the circuit. The circuit depth is determined by observing the critical path, specifically counting the dependent entanglement gates in practice. In addition to the circuit depth, we assess the gate complexity, representing the asymptotic number of basic gates.
Besides execution time, we also analyze the parameter complexity of the model, that is, the asymptotic function of the size of the model.

Quantum circuit depth analysis of QNet.

Circuit block     Gate Complexity     Circuit depth

Input Encoding     $O(n \cdot d)$     $O(1)$

Mixture Learning      $O(n^2 \cdot d)$     $O(n)$

Positional Feedforward      $O(n \cdot d)$     $O(d)$

In Table <ref>, the gate complexity and maximum circuit depth are computed. Here, $n$ is the sequence length, and $d$ is the representation dimension. These complexities are estimated as follows.

* The circuit depth is $O(1)$ in the Input Encoding because there are only two rotation gates on every qubit.

* According to Theorem 2 in <cit.> and the fact that there is no dependence on each Quantum Fourier Transform in Mixture Learning layer, the depth of Mixture Learning layer is $O(n)$.

* In the QNet Positional Feedforward layer, each Grover Operator contains an n-qubit Toffoli gate, and the study <cit.> shows that the Toffoli gate can be decomposed with linear circuit depth, that is, $O(d)$.

Comparison of attention layer time complexity and parameter complexity.

Type     Execution Time     Parameter

Mixture Learning     $O(n)$     $O(d)$

Self-Attention      $O(n^2 \cdot d)$     $O(d^2)$

FFT     $O(n \cdot  d (\log n + \log d))$     $O(1)$

In Table <ref>, QNet Mixture Learning is compared with Self-Attention from Transformer and Fast Fourier Transform from FNet. In Table <ref>, the QNet Feedforward Layer is compared with the Positional-wised Feedforward Network from Transformer. The Positional-wised Feedforward Network is used in almost all Transform-based architecture, including BERT and FNet.

Comparison of feedforward layer time complexity and parameter complexity.

Type     Execution Time     Parameter

QNet Feedforward     $O(d)$     $O(d)$

Positional-wised      $O(n \cdot d^2)$     $O(d^2)$

The model complexity is the addition of attention layer complexity and feedforward layer complexity. Based on Table <ref> and Table <ref>, the overall model operation complexity, parameter complexity, and the actual number of parameters of different models in the configuration of embedding dimension 128 and 2 blocks are shown in Table <ref>. Notice that the complexities of the models in the classical domain can be parallelized by dividing the number of processors.

Comparison of model complexity and parameters numbers

Model     Execution Time     Param     Measured Param

QNet     $O(n+d)$     $O(d)$     2,304

FNet      $O(d \cdot  n \log n + n \cdot d^2)$      $O(d^2)$     67,072

BERT      $O(n^2 \cdot d + n \cdot d^2)$      $O(d^2)$     1,122,048

§ EXPERIMENTS

§.§ Configurations

We implemented the QNet with TensorFlow <cit.> and TensorFlow Quantum <cit.>, a quantum machine learning library.
In the experiments, models are used as the backend for the same task. QNet and ResQNet are compared against FNet and BERT-Tiny <cit.> with both models under their original configuration. In addition, we use QLSTM as a comparison target of the quantum-related models.

§.§.§ Hardware

GPUs and TPUs are not used in the experiments due to insufficient memory to simulate quantum computers. Instead, our models are trained distributively on Taiwania, a supercomputer cluster in National Center for High-performance Computing. The experiments in this work use four computing nodes, each equipped with two 20-core Intel Xeon Gold 6148 CPUs and 384 GB RAM. The MultiWorkerMirroredStrategy of TensorFlow is used as the distribution strategy for synchronous training on multiple workers to train the model in a cluster.

§.§.§ Optimizer

We used the Adam optimizer with $\beta_1 = 0.9$, $\beta_2 = 0.98$ and $\epsilon = 10^{-7}$.

In the distributed training environment, the loss of model is reduced to share across multiple workers. Therefore, we have to adjust the learning rate according to batch size and the number of nodes. The adjusted learning rate is defined as the global learning rate in Equation <ref>. The initial learning rate is $3e-4$ in all experiments.

\begin{equation} \label{equ:global_lr}
global\_lr = initial\_lr \times batch\_size \times num\_nodes
\end{equation}

We varied the learning rate over the course of training according to the Cosine Decay strategy <cit.> in Equation <ref>. In this work, $\alpha = 10^{-2}$.

\begin{equation} \label{equ:lr}
lr = global\_lr \times ( \frac{1}{2} (1 + cos( \frac{step}{total\_steps}\pi))(1 - \alpha) + \alpha)
\end{equation}

§.§ Tasks & Performance Results

In our experiments, we focus on NLP tasks that have short sequence input. Here, 27% of data are used for testing while others are used for training. All input sentences will be converted into lowercase and punctuation stripped, and if the sentences in the dataset have not been through tokenization, the consecutive words will be separated by white space. The models are evaluated on text classifications, review score prediction regression, and named entity recognition with input limited to a maximum of 8 tokens. All models are trained with 5 epochs with a batch size of 128, and each epoch has 100 steps.

Statistics for the text datasets

Dataset     Classes     Size     Length     $|V|$

StackOverflow     20     20,000     8.31/34     22,956

ColBERT     2     200,000     12.81/22     74,010

RentTheRunway     N/A     192,462     7.21/118     15,454

MSRA     7     299,077     N/A     4,748

The statistics of datasets are shown in Table <ref>. In the table, Length contains two numbers representing the mean and max length of texts respectively, and $|V|$ is the vocabulary size.

The comparison of models when evaluating on ColBERT, StackOverflow, RentTheRunway, and MSRA dataset.

Model     Embeddings     Blocks     ColBERT     StackOverflow     RentTheRunway     MSRA     Qubits     Measurements     Params

QNet     2     1     89.84     16.64     1.7765     0.0223     16     1     18

ResQNet             90.48     30.78     1.6910     0.7261     16     1     20

QLSTM             90.15     12.42     1.4293     0.5342     2     48     64

QNet     2     2     86.89     18.20     1.7260     0.0555     16     1     36

ResQNet             91.17     30.08     1.7059     0.5318     16     2     40

QLSTM             90.46     10.46     1.4115     0.0012     2     96     128

QNet     3     1     88.83     12.43     1.6914      0.0783     24     1     27

ResQNet             90.99     41.41     1.6622     0.6611     24     1     30

QLSTM             90.31     11.87     2.1001     0.1032     3     48     120

FNet     256     6     84.45     5.69     1.7161     0.0056     N/A     N/A     795,648

BERT-Tiny     128     2     87.23     5.38     1.6714     0.4603     N/A     N/A     1,122,048

The descriptions of the experimented tasks and corresponding datasets are as follows. Note that the number of parameters reported in Table <ref> is the parameters of the whole model without word embeddings since each task has a different $|V|$.

§.§.§ Text Classifications

ColBERT <cit.> dataset is a binary classification task for humor detection. It consists of 100,000 positive and 100,000 negative short formal texts.

Binary Cross Entropy loss is used for ColBERT humor detection, and results are listed in Table <ref>. As can be seen in the table, QNet achieves an accuracy of 89.84% with an embedding dimension of two and block depth of one, while BERT-Tiny reaches an accuracy of 87.23%. We observed that in the ColBERT dataset, there are few duplicated words in a single sentence, but there are some tokens often repetitively shown in sentences such as "Why", "your", and "is". Thus, recognizing representative tokens while ignoring massive trash information is the key to success in this task. However, the self-attention mechanism may lose focus on the impactful words seldom shown because these word embeddings have not been pre-trained on a large dataset to get the rough meaning and failed to reach an ideal accuracy.

StackOverflow <cit.> dataset is a multi-class classification task to classify questions on StackOverflow.com. It consists of randomly selected 20,000 question titles from 20 different tags.

Categorical Cross Entropy loss is used for StackOverflow question classification, and results are listed in Table <ref>. As can be seen in the table, the QNet and ResQNet outperformed other models. This dataset is more about the detection of the keywords than the relationship of the tokens. The result might be caused by QNet and ResQNet having the benefit of peeping the orienting of the sentences by the entangled quantum state that shares the information across multiple tokens to learn the representation of tokens.

§.§.§ Review Score Prediction

In the RentTheRunway <cit.> dataset, data are the measurements of clothing fit. The review summary is taken as input, and models are asked to predict the rating. The score prediction tasks are usually not classification tasks but regression tasks; the outputs of the model only need to be as close as possible to the labels.

We viewed score prediction tasks as regression tasks, so mean square error is used to optimize the model and as the evaluation metric on test data. The configurations and results of the RentTheRunway review rating prediction are listed in Table <ref>. As observed in the table, that QLSTM has a lower error rate than QNet is reasonable because it uses plenty of VQE circuits in each LSTM gate to make data transform multiple times. Despite that, QNet and ResQNet still have compelling results compared to the state-of-the-art classical models. In this task, context is more important than keywords, so QNet and ResQNet could have the advantage of the high dimension of Hilbert space that spans multiple qubits.

§.§.§ Named-Entity Recognition

MSRA <cit.> dataset is a Chinese named-entity recognition dataset with a BIO tagging format <cit.>. In Named-Entity Recognition tasks, most of the tokens will get an O-tag, a tag indicating that the tokens do not belong to any chunk, making the distribution of labels in the dataset heavily imbalanced.

The cross-entropy loss is applied to every token to classify the entity type of the token in the MSRA task, and results are listed in Table <ref>. The F1-score of non-O tags is used to measure the performance. This task is the most complex in this work since the classifier needs to assign tags to every token with low embedding dimensions. Moreover, imbalanced inputs make models often emit O-tag as output which does not produce meaningful results, and such models will have low F1-score in non-O tag as shown in the table.

§.§ Ablation Study

To prove the effectiveness of the QNet structure, we use an ablation study under the configuration of the embedding size of 2 and encoder blocks of 2 to test each part independently. Two types of results are demonstrated in Table <ref>: positional feedforward only,  and mixture learning only.

The ablation study of QNet.

Configuration     ColBERT     StackOverflow     MSRA

Positional Feedforward Only     87.34     15.78     0

Mixture Learning only     83.44     14.76     0.0857

QNet     86.89     18.20     0.0555

It can be seen in Table <ref> that without the Mixture Learning layer, Positional Feedforward performs poorly on high relational input tasks. For example, it can not learn anything from the MSRA dataset. And without Positional Feedforward, Mixture Learning showed a shortage of keyword-critical tasks such as ColBERT.

§.§ Noise Tolerance

To exhibit how QNet is resistant to the noises in NISQ-era devices, we use the depolarize function from the Cirq library to observe the change of training loss in different amounts of noise. The experiment uses the ColBERT dataset, and QNet is trained for one epoch and batch size of 8.

The training loss of noisy circuit

In Fig. <ref>, the $p$ in the legend is the probability of error generated by the depolarize function. We can see that the training curve of $p=0.5$ is much more jitter than training $p=0.1$, but the loss is descending and reaches about the same value in the end.

§ CONCLUSION

This work presents the QNet, the quantum-native sequence encoder model. QNet features short circuit depth and low qubit usage, making it feasible in near-term quantum computers. In addition, we introduce the ResQNet, the residual connected QNet, to use it in the current stage of quantum computing resources. For various NLP tasks, including text classifications, review score prediction regression, and named-entity recognition, the QNet and ResQNet have advantages compared to classical machine learning models with large embedding dimensions.

We look forward to revealing how quantum entanglement relates to NLP. We want to analyze and explain the result of neural networks to know how high dimension Hilbert space spanned by entanglement gates in QNet blocks assists the model in holding sparse information since, by the mathematics formula, QNet blocks can potentially contain the information of relation among many tokens. However, it is challenging and requires strenuous efforts, especially in hybrid models concerning two different device types and the fact that there are few proposed methods to investigate quantum machine learning models. Also, we are excited about training QNet in the large-scale NISQ quantum computer in the future. When the scale of quantum computers is ready to employ residual connections, we plan to extend the ResQNet to a pure quantum model as QNet.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

booktitle12th USENIX symposium on operating systems design and implementation (OSDI 16)
title$\{$TensorFlow$\}$: a system for $\{$Large-Scale$\}$ machine learning

IEEE Dataport

titleColBERT dataset - 200k short texts for humor detection

Curran Associates, Inc.

booktitleAdvances in Neural Information Processing Systems
titleRecurrent Quantum Neural Networks

Nature Publishing Group

journaltitleNature communications
titleTraining deep quantum neural networks

journaltitlearXiv preprint arXiv:2003.02989
titleTensorflow quantum: A software framework for quantum machine learning

journaltitleIBM Research Blog
titleIBM Quantum breaks the 100-qubit processor barrier

booktitleProceedings 41st Annual Symposium on Foundations of Computer Science
titleFast parallel circuits for the quantum Fourier transform

titleBERT: Pre-training of Deep Bidirectional Transformers for Language Understanding

booktitle2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
titleSpeech-transformer: a no-recurrence sequence-to-sequence model for speech recognition

booktitleInternational Conference on Learning Representations
titleAn Image is Worth 16x16 Words: Transformers for Image Recognition at Scale

journaltitlearXiv preprint arXiv:1802.06002
titleClassification with quantum neural networks on near term processors

booktitleProceedings of the twenty-eighth annual ACM symposium on Theory of computing
titleA fast quantum mechanical algorithm for database search

journaltitlearXiv preprint arXiv:2005.08100
titleConformer: Convolution-augmented transformer for speech recognition

American Association for the Advancement of Science

titleQuantum advantage in learning from experiments

titleFNet: Mixing Tokens with Fourier Transforms

Sydney, Australia

Association for Computational Linguistics

booktitleProceedings of the Fifth SIGHAN Workshop on Chinese Language Processing
titleThe Third International Chinese Language Processing Bakeoff: Word Segmentation and Named Entity Recognition

Curran Associates, Inc.

booktitleAdvances in Neural Information Processing Systems
titlePay Attention to MLPs

booktitleInternational Conference on Learning Representations
titleSGDR: Stochastic Gradient Descent with Warm Restarts

titleDo You Even Need Attention? A Stack of Feed-Forward Layers Does Surprisingly Well on ImageNet

journaltitlearXiv preprint arXiv:2105.02723
titleDo you even need attention? a stack of feed-forward layers does surprisingly well on imagenet

Vancouver, British Columbia, Canada

Association for Computing Machinery

abstractProduct size recommendation and fit prediction are critical in order to improve customers' shopping experiences and to reduce product return rates. Modeling customers' fit feedback is challenging due to its subtle semantics, arising from the subjective evaluation of products, and imbalanced label distribution. In this paper, we propose a new predictive framework to tackle the product fit problem, which captures the semantics behind customers' fit feedback, and employs a metric learning technique to resolve label imbalance issues. We also contribute two public datasets collected from online clothing retailers.
booktitleProceedings of the 12th ACM Conference on Recommender Systems
seriesRecSys '18
titleDecomposing Fit Semantics for Product Size Recommendation in Metric Spaces

journaltitlePhysical Review A
titleQuantum circuit learning

journaltitleFuture Generation Computer Systems
titleTransformer based deep intelligent contextual embedding for twitter sentiment analysis

American Association of Physics Teachers

titleQuantum computation and quantum information

booktitleInternational Conference on Learning Representations
titleword2ket: Space-efficient Word Embeddings inspired by Quantum Entanglement

Nature Publishing Group

journaltitleNature communications
titleA variational eigenvalue solver on a photonic quantum processor

booktitleNatural language processing using very large corpora
titleText chunking using transformation-based learning

American Physical Society

journaltitlePhys. Rev. A
titleLinear-depth quantum circuits for $n$-qubit Toffoli gates with no ancilla

American Physical Society

journaltitleRev. Mod. Phys.
titleDecoherence, the measurement problem, and interpretations of quantum mechanics

journaltitlearXiv preprint arXiv:2203.01340
titleIs quantum advantage the right goal for quantum machine learning?

journaltitleQuantum Information Processing
titleThe quest for a quantum neural network

titleThe Dawn of Quantum Natural Language Processing

journaltitlearXiv preprint arXiv:2108.04927
titleEmbodied bert: A transformer model for embodied, language-guided visual task completion

New York, New York, USA

AAAI Press

booktitleProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence
titleSparse Word Embeddings Using L1 Regularized Online Learning

journaltitleAdvances in Neural Information Processing Systems
titleMlp-mixer: An all-mlp architecture for vision

Curran Associates, Inc.

booktitleAdvances in Neural Information Processing Systems
titleAttention is All you Need

journaltitlearXiv preprint arXiv:1803.07416
titleTensor2tensor for neural machine translation

Nature Publishing Group

journaltitlenpj Quantum information
titleQuantum generalisation of feedforward neural networks

titleLinformer: Self-Attention with Linear Complexity
Machine Learning (cs.LG),Machine Learning (stat.ML),FOS: Computer and information sciences,FOS: Computer and information sciences

booktitleProceedings of The Web Conference 2020
titleTransmodality: An end2end fusion method with transformer for multimodal sentiment analysis

Denver, Colorado

Association for Computational Linguistics

booktitleProceedings of the 1st Workshop on Vector Space Modeling for Natural Language Processing
titleShort Text Clustering via Convolutional Neural Networks

booktitleThe Thirty-Third International Flairs Conference
titleEmptransfo: A multi-head transformer architecture for creating empathetic dialog systems

Wiley Online Library

journaltitleQuantum Engineering
titleSimulating noisy variational quantum eigensolver with local noise models