Quantum Subroutine for Variance Estimation: Algorithmic Design and  Applications]Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications

1]Anna<EMAIL_ADDRESS>
1]Alessandro<EMAIL_ADDRESS>
1]Gianna M. Del<EMAIL_ADDRESS>
1]Riccardo<EMAIL_ADDRESS>
[1]Alessandro<EMAIL_ADDRESS>*[1]Department of Computer Science, University of Pisa, Largo Pontecorvo, 3, Pisa, 56127, Italy

Quantum computing sets the foundation for new ways of designing algorithms, thanks to the peculiar properties inherited by quantum mechanics. The exploration of this new paradigm faces new challenges concerning which field quantum speedup can be achieved. Towards finding solutions, looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
Herewith, we delve into a grounding subroutine, the computation of the variance, whose usefulness spaces across different fields of application, particularly the Artificial Intelligence (AI) one. Indeed, the finding of the quantum counterpart of these building blocks impacts vertically those algorithms that leverage this metric.
In this work, we propose QVAR, a quantum subroutine, to compute the variance that exhibits a logarithmic complexity both in the circuit depth and width, excluding the state preparation cost. With the vision of showing the use of QVAR as a subroutine for new quantum algorithms, we tackle two tasks from the AI domain: Feature Selection and Outlier Detection. In particular, we showcase two AI hybrid quantum algorithms that leverage QVAR: the Hybrid Quantum Feature Selection (HQFS) algorithm and the Quantum Outlier Detection Algorithm (QODA).
In this manuscript, we describe the implementation of QVAR, HQFS, and QODA,  providing their correctness and complexities and showing the effectiveness of these hybrid quantum algorithms with respect to their classical counterpart.

§ INTRODUCTION

The emergence of the Quantum Computation paradigm can be accredited to the prospect of discovering computational speed-up with respect to classical computation.
Quantum Computation introduced novel challenges and new ways to rethink algorithms. Within this emerging computational paradigm, among all the challenges that arose, a pivotal research question deals with the design and implementation of quantum versions of widespread subroutines employed in the classical domain to the quantum one. In particular, identifying and understanding speed-up opportunities for these classical grounding subroutines in their quantum counterpart is crucial for the development of advanced quantum algorithms built upon these foundational components [1, 2].

Among those components, our interest fell on the concept of variance, a pervasive measure that finds application across a vast number of domains [3], including the field of Artificial Intelligence (AI). Although the variance can be computed classically with linear complexity [4], the design of a possibly more efficient quantum algorithm is not straightforward. To the best of our knowledge, there is no prior work on computing the variance over a dataset encoded in the amplitudes.

In this work, we therefore propose a
Quantum subroutine designed for computing the Variance (QVAR) over a dataset, where the instances are encoded within the amplitudes of a quantum state [5]. After state preparation, the subroutine complexity exhibits logarithmic characteristics in both its width and depth, underscoring valuable properties.
The QVAR subroutine lends itself naturally to applications in Artificial Intelligence. Therefore, in this study, we also propose two QVAR-based quantum algorithms: one designed for addressing the  Feature Selection tasks (HQFS) and the other tailored for solving the Outlier Detection problem (QODA) [6]. Both algorithms follow a hybrid paradigm where classical and quantum computations are interleaved to solve a given task. This paradigm enables the optimal utilization of current quantum technologies, where problems like short decoherence time, noisy qubits, and limited hardware capabilities make the execution of full quantum algorithms practically impossible.

In this work, we design the QVAR subroutine, and the HQFS, and QODA algorithms.
The design is supported by defining their respective circuits and presenting mathematical proofs of correctness. The proposed quantum algorithms have been experimentally evaluated, comparing their performance with the classical counterparts. Additionally, we provide the Qiskit[<https://qiskit.org/>] implementations for QVAR[<https://github.com/AlessandroPoggiali/QVAR>], HQFS[<https://github.com/AlessandroPoggiali/HQFS>], and QODA[<https://github.com/AlessandroPoggiali/QODA>]. Ultimately, due to the large variety of applications that QVAR can find, we support the development of those paths by creating the PyPI package[<https://pypi.org/project/QVAR/>] of QVAR.

This manuscript represents the extended version of the conference paper presented in [7]. With respect to the conference paper, we give a detailed analytical description of the QVAR subroutine, together with a formal proof of correctness. Moreover, we introduce the novel QODA algorithm for Outlier Detection and enhance the experimental evaluation, providing a more comprehensive exploration of the subject matter.

The rest of the manuscript is organized as follows.
Section <ref> presents the related works and motivates our solution with respect to the state-of-the-art,
Section <ref> introduces the quantum subroutine for computing the variance (QVAR), Section <ref> presents the Quantum Feature Selection algorithm (HQFS), Section <ref> describes the Quantum Outlier Detection algorithm (QODA),
Section <ref> validates the effectiveness of the proposed algorithms, and, eventually, Section <ref> draws the conclusions according to the obtained results.

§ RELATED WORK

The variance measures the variability over a set of data, and it is a fundamental building block to design algorithms whose applications range across different domains such as Statistical Analysis, Optimization Algorithms, and Machine Learning [3].

Many algorithms for the computation of the variance with stable and effective approaches have been proposed in the literature (e.g., see [4, 8]). However, as far as we know, the literature on quantum computing lacks specific works on the computation of the variance.

Hereby, we design a quantum subroutine that computes the variance to address two fundamental problems that leverage the variance itself: the Feature Selection and the Outlier Detection.

Feature Selection techniques have the objective of selecting the most relevant features from a dataset, a crucial step in data analysis [6]. Indeed, Feature Selection proves to be notably advantageous in achieving efficient data reduction [9, 10].
The subset of features this preprocessing identifies can contribute to developing more robust models.
Among the Feature Selection techniques [11], hereby we focus on unsupervised Feature Selection methods, i.e., methods that do not use explicit target labels or class information to select the relevant features. In particular, we consider Feature Selection techniques tailored for numerical variables, wherein features with variances falling below a specified threshold are removed [6].
While the existing literature has extensively investigated Feature Selection techniques for classical algorithms, novel challenges emerge in the design of Feature Selection algorithms within the domain of quantum computing. Some Quantum Feature Selection algorithms have been recently proposed in the literature. In [12], the authors propose a feature selection algorithm based on a quadratic unconstrained binary optimization (QUBO) problem. In [13], a solution for the quantum annealing paradigm is given. Eventually, the work [14] describes a quantum feature selection algorithm that deals with binary values. In this work, we introduce a Feature Selection algorithm (HQFS) based on the gate model, wherein values are encoded within the amplitudes of a quantum state.

Outlier Detection is crucial across various domains [15], encompassing Fraud Detection, Medical Anomaly Diagnosis, and Engineering. The significance attributed to outliers varies based on the contextual requirements. In data analysis, outliers can significantly impact the results, leading to incorrect conclusions, decisions, and models.
Conversely, outliers are the critical information crucial to understand and address in domains like fraud detection. Recently, quantum computing has shown great potential to solve computationally expensive problems for classical computers, including data analysis tasks. Some techniques for detecting outliers in quantum computing are present in the literature. In [16, 17], the authors present a quantum anomaly detection algorithm based on density estimation. Furthermore, in the study [18], a methodology for anomaly detection is introduced, leveraging both Hamming Distance and Durr-Hoyer algorithms.
With respect to the state-of-the-art, we design a hybrid quantum algorithm for anomaly detection (QODA) inspired by the classical Angle-Based Outlier Detection (ABOD) algorithm [19]. ABOD is an unsupervised distance-based method for detecting outliers that measures the abnormality of each data point by computing the variance of the angles between all pairs of vectors in the dataset (see Section <ref> for more details).

§ A QUANTUM SUBROUTINE FOR VARIANCE ESTIMATION

In this section, we introduce the QVAR subroutine for computing the variance of a set of values encoded within the amplitudes of a quantum state.

[ row sep=0.2cm, column sep=0.2cm]
$\ket{a}=\ket{0}$        H     1         2          …     4         5     6      …     8     9     10     …     12     1     2      …     4     H

$\ket{e_1}=\ket{0}$                   X              …                      …                  …         H          …

$\ket{e_2}=\ket{0}$                          X      …                      …                  …             H      …

$\ket{e_n}=\ket{0}$                             …           X              …                  …                   …     H

$\ket{q_1}=\ket{0}$                             …             4          …                  …                  …         H     X

$\ket{q_2}=\ket{0}$                              …                 4      …                  …                  …         H     X

$\ket{q_n}=\ket{0}$                               …                      …     4              …                  …         H     X

$\ket{i_1}=\ket{0}$     [wires=4,nwires=3]Amplitude
|D⟩                           …                        …         H          …                  …

$\ket{i_2}=\ket{0}$                              …                        …             H      …                  …

$\ket{i_n}=\ket{0}$                              …                      …                    …     H              …

QVAR Oracle

Given a set $D = \{d_0, d_1, \dots, d_{N-1}\}$ of $N$ values, we are interested in estimating the variance of $D$, defined as

\rm{Var}(D)=\frac{1}{N} \sum_{t=0}^{N-1} (d_t-\mathbb{E}[D])^2,

where $\mathbb{E}[D]=\frac{1}{N}\sum_{t=0}^{N-1} d_t$ is the mean value of the data.

Note that $D$ can be either a set of classical values or the result of a previous quantum computation, i.e., a superposition of values. In the first case, one should adopt an encoding algorithm for loading the classical data into the quantum state. However, QVAR can generally be applied as a quantum subroutine to a quantum superposition of values indexed by proper register qubits.

The QVAR subroutine comprises the quantum oracle reported in Figure <ref>, which the Amplitude Estimation algorithm [20] uses to estimate the variance value. This algorithm requires in total $3n+s+1$ qubits, where $n=\ceil{\log_2 N}$ and $s=O(\log\frac{1}{\varepsilon})$ is the number of additional qubits required by Amplitude Estimation to get an estimate of the variance with (absolute) error $\varepsilon$ with respect to the classical variance.
The formal proof of correctness of the QVAR oracle of Figure <ref> is reported below. The main idea is to use a qubit ancilla $\ket{a}$ to create an equal superposition of two branches through a Hadamard gate. In the branch where the ancilla is in state $\ket{0}$, we maintain the superposition encoding the values in $D$, while in the branch where the ancilla is in state $\ket{1}$, we apply a sequence of gates that compute the mean $\mathbb{E}[D]$. Eventually, we apply another Hadamard gate on $\ket{a}$ to make the two branches collide and create the superposition containing the component of the variance, namely the differences $d_t - \mathbb{E}[D]$, for $t=0,\dots,N-1$.
Since all these differences are the amplitudes of the state vector related to specific configurations of the qubits, we can use the Amplitude Estimation algorithm to estimate the variance as the sum of squares of the target amplitudes. In our case, we employ AE to estimate the amplitude of the target configuration $\ket{ae^{\otimes n}q^{\otimes n}} = \ket{1 1^{\otimes n} 0^{\otimes n} }$ by measuring the $s$ additional qubits. The measurement output represents an approximation of the variance in the computational basis. Concerning the complexity of this method, in general, the depth of AE is $O(\delta\frac{1}{\varepsilon}+\log \log \frac{1}{\varepsilon})$ [21] where $\delta$ is the depth of the oracle. In our case, assuming the existence of an efficient quantum state preparation technique, $\delta=O({\rm{polylog}} \, N)$. Thus, the overall complexity of QVAR is $O(\frac{1}{\varepsilon}{\rm{polylog}} \, N)$. We can increase the precision of QVAR by interpolating the measurement probabilities and computing the maximum likelihood estimator (we call this method ML-QVAR) [22].

The correctness of QVAR is proved in the  following proposition.

Let  $D = \{d_0, d_1, \dots, d_{N-1}\}$ be a set of $N$ values encoded in the quantum state of $n=\log N$ qubits as follows:

\begin{equation*}
\ket{D}=\frac{1}{\sqrt{N}} \sum_{t=0}^{N-1}d_t \ket{t}_i,
\end{equation*}

where $\sqrt{N}$ is the normalization factor. Then, the quantum oracle of the QVAR algorithm
starting from the quantum state

\begin{equation*}
\ket{\psi_0} = \ket{0}_a\ket{0}_e^{\otimes n}\ket{0}_q^{\otimes n} \ket{D},
\end{equation*}

returns in the configuration of the state vector equal to  $\ket{1}_a\ket{1}_e^{\otimes n} \ket{0}_q^{\otimes n}$ the terms $d_t-\mathbb{E}[D]$.

Following the quantum operations depicted in Figure <ref>, the Hadamard gate on $\ket{0}_a$ creates two branches of computation: the branch where the qubit is in state $\ket{0}$ at the end of the computation will contain the superposition of all $d_t$. While the branch where the qubit is in state $\ket{1}$ will contain $N$ copies of the mean $\mathbb{E}[D]$. Indeed, the first $H$ gate on the ancilla qubit evolves the initial state $\ket{\psi_0}$ in

\begin{equation*}
\ket{\psi_1} = \frac{1}{\sqrt{2N}}\left(\ket{0}_a \ket{0}_e^{\otimes n}\ket{0}_q^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_i +\ket{1}_a \ket{0}_e^{\otimes n}\ket{0}_q^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_i\right).
\end{equation*}

The C-NOT, controlled by the ancilla qubit, and the X gates on register $e$ bring the state in:

\begin{equation*}
\ket{\psi_2} = \frac{1}{\sqrt{2N}}\left(\ket{0}_a \ket{1}_e^{\otimes n}\ket{0}_q^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_i +\ket{1}_a \ket{0}_e^{\otimes n}\ket{0}_q^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_i\right).
\end{equation*}

The C-SWAP gates swap the qubits of register $i$ and register $q$ in the branch where the ancilla qubit is in state $\ket{1}$, leading to the state:

\begin{equation*}
\ket{\psi_3} = \frac{1}{\sqrt{2N}}\left(\ket{0}_a \ket{1}_e^{\otimes n}\ket{0}_q^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_i +\ket{1}_a \ket{0}_e^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_q\ket{0}_i^{\otimes n}\right).
\end{equation*}

Since we want the mean of $D$ in the branch where the ancilla is |1⟩, we apply $H$ gates on each qubit of register $i$ controlled by the value of the ancilla. This produces the following state:

\begin{equation*}
\ket{\psi_4} = \frac{1}{\sqrt{2N}}\left(\ket{0}_a \ket{1}_e^{\otimes n}\ket{0}_q^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_i +\ket{1}_a \ket{0}_e^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_q \ket{+}_i^{\otimes n}\right),
\end{equation*}

where $\ket{+}=\frac{\ket{0}+\ket{1}}{\sqrt{2}}.$
In order to have the mean value $\mathbb{E}[D]$, we apply an H gate on each qubit of register $e$ controlled by the ancilla. This results in:

\begin{equation*}
\ket{\psi_5} = \frac{1}{\sqrt{2N}}\left(\ket{0}_a \ket{1}_e^{\otimes n}\ket{0}_q^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_i +\ket{1}_a \ket{+}_e^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_q \ket{+}_i^{\otimes n}\right).
\end{equation*}

The next step involves applying another $H$ gate on the first qubit, which will later be exploited to collide each $d_t$ with the mean $\mathbb{E}[D]$. The state obtained is:

\begin{equation*}
\begin{split}
\ket{\psi_6} &= \frac{1}{2\sqrt{N}}\left(\ket{0}_a \ket{1}_e^{\otimes n}\ket{0}_q^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_i +\ket{1}_a\ket{1}_e^{\otimes n}\ket{0}_q^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_i\right. \\ &
\left. + \ket{0}_a \ket{+}_e^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_q \ket{+}_i^{\otimes n} -\ket{1}_a \ket{+}_e^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_q \ket{+}_i^{\otimes n} \right).
\end{split}
\end{equation*}

Then, the $H$ gates on each qubit of register $q$ are required to form the actual sums between each $d_t$.
Recall that $H^{\otimes n} \ket{t}^{\otimes n} = \tfrac{1}{\sqrt{N}} \sum_{z=0}^{N-1}(-1)^{t\cdot z}\ket{z}$, where $t \cdot z$ is the scalar product between the binary representations of $t$ and $z$. The state becomes:

\begin{equation*}
\begin{split}
\ket{\psi_7} &= \frac{1}{2\sqrt{N}}\left(\ket{0}_a\ket{1}_e^{\otimes n}\ket{+}_q^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_i +\ket{1}_a \ket{1}_e^{\otimes n}\ket{+}_q^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_i  \right.\\ &
+\ket{0}_a \ket{+}_e^{\otimes n}\sum_{t=0}^{N-1}d_t\left(\frac{1}{\sqrt{N}}\sum_{z=0}^{N-1}(-1)^{t\cdot z}\ket{z}_q\right) \ket{+}_i^{\otimes n} \\& -
\left.   \ket{1}_a \ket{+}_e^{\otimes n}\sum_{t=0}^{N-1}d_t \left(\frac{1}{\sqrt{N}}\sum_{z=0}^{N-1}(-1)^{t\cdot z}\ket{z}_q\right) \ket{+}_i^{\otimes n}\right)\\ &
=  \frac{1}{2\sqrt{N}}\left(\ket{0}_a\ket{1}_e^{\otimes n}\ket{+}_q^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_i +\ket{1}_a \ket{1}_e^{\otimes n}\ket{+}_q^{\otimes n}\sum_{t=0}^{N-1}d_t\ket{t}_i \right.\\&
+\frac{1}{\sqrt{N}} \ket{0}_a \ket{+}_e^{\otimes n}\sum_{t=0}^{N-1}d_t\left(\ket{0}_q^{\otimes n}
+ \sum_{z=1}^{N-1}(-1)^{t\cdot z}\ket{z}_q\right) \ket{+}_i^{\otimes n}  \\
&- \left.\frac{1}{\sqrt{N}} \ket{1}_a \ket{+}_e^{\otimes n}\sum_{t=0}^{N-1}d_t \left(\ket{0}_q^{\otimes n} + \sum_{z=1}^{N-1}(-1)^{t\cdot z}\ket{z}_q\right) \ket{+}_i^{\otimes n}\right).
\end{split}
\end{equation*}

We are interested in the configuration $\ket{1}_a\ket{1}_e^{\otimes n} \ket{0}_q^{\otimes n}$:

\begin{equation*}
\begin{split}
\bra{1}_a\bra{1}_e^{\otimes n} \bra{0}_q^{\otimes n}\ket{\psi_7}=&\frac{1}{2\sqrt{N}}  \left(\frac{1}{(\sqrt{N}}\sum_{t=0}^{N-1}d_t\ket{t}_i-\frac{1}{2^n}\sum_{t=0}^{N-1}d_t\ket{+}_i^{\otimes n}\right)\\&
= \frac{1}{2\sqrt{N}}\left(\frac{1}{\sqrt{N}}\sum_{t=0}^{N-1}d_t \ket{t}_i -\frac{1}{N}\ket{+}_i^{\otimes n}\sum_{t=0}^{N-1}d_t\right)\\&
\end{split}
\end{equation*}

Changing the index in the last sum, and expressing $\ket{+}_i^{\otimes n}$ in the computational basis, we obtain:

\begin{equation*}
\begin{split}
&\frac{1}{2N}\left(\sum_{t=0}^{N-1}d_t \ket{t}_i -\sum_{t=0}^{N-1}\ket{t}_i\frac{1}{N}\sum_{k=0}^{N-1}d_k\right) \\&
= \frac{1}{2N}\ket{1}_a\ket{1}_e^{\otimes n}\ket{0}_q^{\otimes n}\sum_{t=0}^{N-1} \ket{t}_i \left(d_t-\frac{1}{N}\sum_{k=0}^{N-1}d_k\right),
\end{split}
\end{equation*}

from which it is evident that the components of the variance, up to a normalization factor, are associated with the configurations of the state vector equal to $\ket{1}_a\ket{ 1}_e^{\otimes n} \ket{0}_q^{\otimes n}$.

§ QUANTUM FEATURE SELECTION

In this section, we study the application of the QVAR subroutine to the Feature Selection task. As discussed in [6], given a multidimensional dataset,  we can filter out features with low variance. Indeed, low variance features do not vary significantly among the different records in the dataset and are less useful for discriminative tasks.
Hereby, we design an efficient Hybrid Quantum Feature Selection (HQFS) algorithm that exploits the QVAR subroutine for discarding low variance features.  A detailed description follows.

Given a multidimensional dataset $D \in \mathbb{R}^{M \times N}$ with $M$ records and $N$ features, we denote as $D_{i,j}$ the $j$-th feature value of the $i$-th record. The HQFS algorithm iterates over the features and computes the variances $\rm{Var}_j =\rm{Var}(d_{0,j},\cdots,d_{M-1,j})$ for $j \in [ 0,\cdots,N-1]$. HQFS employs a distinct QVAR circuit for each feature $j$ to calculate each variance. Overall, HQFS uses $N$ QVAR circuits, one for each feature. Then, HQFS drops all features whose variance is below a given threshold $t$.

$D$ - input dataset, $t$ - variance threshold
$F$ - list of selected features
$F \gets \{f_0,\cdots,f_{N-1}\}$ *[f]set of selected features initially containing all features
(*[f]classically iterate among all feature)$j \in [0,\cdots N-1]$
$\rm{Var}_j\gets QVAR(D_{:,j})$ *compute the variance using the QVAR algorithm.
(*[f]check if feature $f_j$ is uninformative)$\rm{Var}_j \leq t$
$F \gets F \setminus \{f_j\}$
*remove feature $f_j$ to the set of selected features

$F$ *return the list of selected features

We can use either the QVAR or ML-QVAR as a variance estimation method. In the following, we refer to HQFS as the version using QVAR and ML-HQFS as the version using ML-QVAR. Since the depth of AE is $O(\delta\frac{1}{\varepsilon}+\log \log \frac{1}{\varepsilon})$, with $\delta$ the depth of the oracle, which in our case is $O({\rm{polylog}} \,M)$, the overall complexity of Algorithm <ref> is $O(N(\frac{1}{\varepsilon}{\rm{polylog}} \,M))$, if we assume available efficient methods for reconstructing the initial state.

§ QUANTUM OUTLIER DETECTION

This section introduces a hybrid quantum algorithm inspired by the classical Angle-Based Outlier Detection (ABOD) algorithm [19].

ABOD is a distance-based unsupervised Outlier Detection method that measures the abnormality of each data point by computing the variance of the angles between the difference vectors of the given point and the other points in the dataset. Indeed, the variance of these angles depends on how different a point is from the others:  for points within a cluster, the angles differ widely, while outliers are expected to present a smaller variance because they are further away from the rest of the dataset. Hence, the points with smaller ABOD values are considered to be more likely to be outliers.

ABOD has several advantages over other Outlier Detection techniques, including detecting outliers in high-dimensional datasets. However, it may not perform well on datasets with a high degree of overlap between classes or when the dataset contains clusters of outliers. Moreover, it has a cost of $O(M^3 + M^2 N)$ where $M$ is the number of records, and $N$ is the dimension of each record; hence the cost is very high.

The classical algorithm works as follows.
Assume we have $M$ records, each with $N$-dimensions, stored in a matrix $X=[x_1| x_2|\cdots|x_M] \in \mathbb{R}^{N\times M}$, so that each record can be seen as belonging to a vector space of dimension $N$. We iterate over all records, considering each one as a pivot. Thus, let $x_p$, $1 \le p \le M$, be the current pivot.  We denote by $\theta_{ij}^{(p)}$ the angle between the vectors  $x_i$ and $x_j$ observed from the pivot $x_p$, i.e., the angle between the difference vectors  $\tilde x_i = x_i - x_p$ and $\tilde x_j = x_j - x_p$.
Mathematically, we can write this as:

\begin{equation}\label{eq:theta}
\theta_{ij}^{(p)}=\arccos\left(\frac{\tilde x_i^T \tilde x_j}{\|\tilde x_i\|\|\tilde x_j\|}\right),
\end{equation}

where all norms are 2-norms.
For each $p\in \{ 1,   \ldots, M\}$, we compute  the variance $v_p$ of $\theta_{ij}^{(p)}$, with $1 \le i < j \le M$ and $i, j \neq p$, i.e.,

Once the vector $V=[v_1,v_2, \ldots, v_M]$  containing the variances is ready, the algorithm detects the outliers as the records with variance below a given threshold. The algorithm is usually implemented by computing the variance directly on the inner products, i.e., on the cosine of $\theta_{ij}^{(p)}$ [19].

[transparent, row sep=0.05cm, column sep=0.3cm]
$\ket{d}=\ket{0}$                1     H          2     X                            1          H

$\ket{j}=\ket{0}^{\otimes m}$    m     H            [wires=3, label style=yshift=0.8cm]Amplitude

$\ket{i}=\ket{0}^{\otimes m}$    m    H     [wires=2]Amplitude

$\ket{k}=\ket{0}^{\otimes n}$    n    H

Computation of differences.

We design a hybrid quantum version of ABOD called Quantum Outlier Detection Algorithm (QODA). QODA iterates over all records in a given dataset and calls a quantum subroutine to test whether the current record is an outlier on a single quantum circuit. Alternatively, we could test each record in the dataset by employing distinct quantum circuits that can run in parallel.

QODA mimics the classical ADOB approach, exploiting the variance as a statistical measure to detect
outliers, allowing a reduction in the computational complexity of the classical version thanks to the quantum oracle for the computation of the variance proposed in Section <ref>.
A crucial subroutine of QODA is, therefore, an efficient quantum heuristic for estimating the variance of all angles  $\theta_{ij}^{(p)}$, for a given sample $x_p$, taken as a pivot. Thus, we employ the QVAR subroutine defined in Section <ref>.

This heuristic is based on the idea of approximating the variance of the angles $\theta_{ij}^{(p)}$ in (<ref>) with the variance of the differences  between the vectors translated by the pivot $x_p$ and then normalized.
For all $1 \le i \le M$,  we (classically) compute $\tilde x_i = x_i - x_p$. Then, we normalize all vectors  so that the denominators in equation (<ref>) vanish, adopting as default data preprocessing the Inverse Stereographic Projection
(ISP), in order to keep the clusters separated, as discussed in [23].

Recall that the ISP maps $N$-dimensional data into the surface of a unit sphere
in the $(N+1)$-dimensional space and is computed as follows.
Given a vector $v=(v_1, v_2, \ldots, v_N) \in \mathbb{R}^N$, we have:

$$\mbox{ISP}(v)=\left(\frac{2v_1}{\|v\|^2+1},\frac{2v_2}{1+\|v\|^2}, \ldots, \frac{2v_N}{1+\|v\|^2}, \frac{-1+\|v\|^2}{1+\|v\|^2}\right).

Notice that  $\|\mbox{ISP}(v)\| = 1$.
Thus, let $\hat x_i = \mbox{ISP}(\tilde x_i) = \mbox{ISP}(x_i - x_p) $ denote the normalized vectors, translated by $x_p$.
We denote the scaled components of the differences between two projected records $\hat x_i$ and $\hat x_j$ as:

\begin{equation} \label{eq:delta}
\Delta^{(p)}_{ijk} = \frac{1}{2(M-1)\sqrt{N+1}} \left(\hat x_{i} - \hat x_{j}\right)_k, \quad {i, j=0, \ldots, M-1, \, k=0, \ldots, N-1.}
\end{equation}

After encoding all the vectors $\hat x_i$ in a quantum circuit, for example using one of the QRAM models [24, 25], we can use  a Hadamard gate to compute simultaneously all the differences $\Delta^{(p)}_{ijk}$ in  (<ref>) in the amplitudes, appropriately normalized. In Figure <ref>, we show the circuit used for this purpose. The state
\ket{D}= \frac{1}{\sqrt{MN}} \sum_{i=0}^{M-1}\sum_{k=0}^{N-1}\hat{x}_{ki} \ket{i}\ket{k}$$

corresponding to the input dataset $D$ is obtained using a QRAM model, and is uploaded twice in the circuit, in two different branches of the qubit $\ket{d}$, so that it is possible to compute all the differences $\Delta_{ijk}^{(p)}$ with just a Hadamard gate on the first qubit $\ket{d}$. Indeed, the state vector after the final Hadamard gate contains all the difference $(\hat x_j-\hat x_i)_k$.

Note that the dependence from the chosen pivot $x_p$ is still within $\hat x_i$ and $\hat x_j$, indeed we have

(\hat x_i - \hat x_j)_k= \left\{ \begin{array}{ll}
\frac{2(x_{ki}-x_{kp})}{1+\|x_i-x_p\|^2}-\frac{2(x_{kj}-x_{kp})}{1+\|x_j-x_p\|^2} & \mbox{ for } k=1, \ldots, N\\
& \\
\frac{2(\|x_i-x_p\|^2-\|x_j-x_p\|^2)}{(1+\|x_i-x_p\|^2)(1+\|x_j-x_p\|^2)},& \mbox{ for } k=N+1.
\end{array}
\right.

In Proposition <ref> we show that the variance of the differences $\Delta_{ijk}^{(p)}$ is a good approximation of the variance of the angles, and thus we can apply the circuit for calculating the variance in Figure <ref> to the differencies $\Delta_{ijk}^{(p)}$ instead of the angles $\theta_{ij}^{(p)}$. Indeed, the computation of the angles $\theta_{ij}^{(p)}$ requires the estimation of the inner products between the vectors and is more expensive than just applying a Hadamard gate to get the $\Delta_{ijk}^{(p)}$ in superposition.

Let $\Delta^{(p)}$ be the $(M-1)^2(N+1)$-dimensional vector
obtained appending all the $\Delta_{ijk}^{(p)}$, for $0 \le i, j \le M-1, (i,j \neq p), 0\le k\le N,$ and let $\theta^{(p)}$ be the $(M-1)^2$-dimensional vector whose components are the angles ${\theta}_{ij}^{(p)}$ between $\hat x_i$ and $\hat x_j$, for $1 \le i, j \le M, (i,j \neq p)$. Then:

\begin{equation}
\rm{Var}(\Delta^{(p)}) \ < \ \frac{1}{N+1} \rm{Var}(\theta^{(p)})+\frac{1}{N+1}\mathbb{E}^2[\theta^{(p)}].
\label{teo}
\end{equation}

First of all, note that $\Delta^{(p)}$ is a $(M-1)^2(N+1)$-dimensional vector
since after the ISP procedure the records have $N+1$ entries, and each pivot is compared with the remaining $M-1$. Then, from the definition, we have

\mbox{Var}(\Delta^{(p)})=\frac{1}{(M-1)^2(N+1)} \sum_{i, j \neq p}\sum_k (\hat{x}_i-\hat{x}_j)_k^2.

Expanding the product, using the fact that each record is normalized and that $\cos(\theta_{ij}^{(p)})=\sum_{k} \hat {x}_{ki}\hat {x}_{kj}$ we have

\mbox{Var}(\Delta^{(p)})=\frac{2}{(M-1)^2(N+1)}((M-1)^2-\sum_{i, j \neq p} \cos(\theta_{ij}^{(p)})).

We can now use the Taylor expansion at zero of the cosine function, truncated at the second term, to get that for each pair $i, j\neq p$

\cos(\theta_{ij}^{(p)})\ge 1-\frac{1}{2} (\theta_{ij}^{(p)})^2.

Then, we can upper bound the variance as

\begin{equation} \label{varineq}
\mbox{Var}(\Delta^{(p)})\le \frac{1}{N+1}\mathbb{E}[(\theta^{(p)})^2].
\end{equation}

we can replace $\mathbb{E}[(\theta^{(p)})^2]$ in (<ref>)  and we get

\mbox{Var}(\Delta^{(p)})\le \frac{1}{N+1} \left(\mbox{Var}(\theta^{(p)}) +\mathbb{E}^2[\theta^{(p)}] \right).

$X$ - input data, $t$ - threshold
$O$ - set of outliers
$O \gets \emptyset$ *[f]set of outliers initially empty
(*[f]for each record)$p\in \{ 1, 2, \ldots, M\}$
$\tilde X \gets X - \ket{x_p}\bra{\bf{1}}$ *scale the dataset w.r.t. $x_p$
$\hat X \gets \mathit{ISP}(\tilde X)$ *normalize $X_p$ with ISP
$v_p \gets \mathit{QVAR}(\hat X)$ *[f]Quantum Outlier Factor of $x_p$.
(*[f]check if $x_p$ is an outlier)$v_p \leq t$
$O \gets O \cup \{x_p\}$
*add $x_p$ to the set of outliers

$O$ *return the list of outliers

Using vector differences instead of angles is convenient as we can maintain the superposition of all differences in the QVAR oracle and perform the variance computation directly on them within the same circuit (see Figure <ref>).
Thus, this approach requires only the data encoding step before applying the quantum oracle QVAR and the final measurement.

The complexity of the quantum oracle QVAR is, in this case, ${\rm{polylog}}\,M^2N$, i.e., ${\rm{polylog}}\,MN$, assuming available efficient methods for encoding classical data, while the number of qubits required is $7m+4n+s+1$, where $m=\ceil{\log_2 M}$, $n=\ceil{\log_2 N}$, and $s$ is the number of additional qubits of AE.
The overall hybrid algorithm QODA to solve the Outlier Detection problem is summarized by the pseudocode in Algorithm <ref>. The complexity of QODA is $O(M^2N)$ classical operations for data preprocessing plus a $O(M(\frac{1}{\varepsilon}{{\rm{polylog}} MN}))$ quantum cost in depth.

§ EXPERIMENTS

In this section, we report the experiments to evaluate the QVAR subroutine[The Qiskit implementation of the QVAR subroutine is publicly available at <https://github.com/AlessandroPoggiali/QVAR>] applied to both tasks proposed in the previous sections. We implemented the HQFS algorithm and the QODA using IBM's Qiskit framework[HQFS code publicly available at <https://github.com/AlessandroPoggiali/HQFS>][QODA code publicly available at <https://github.com/AlessandroPoggiali/QODA>].
The main aim of these experiments is to assess the effectiveness of the quantum algorithms HQFS and QODA with respect to their classical counterparts.
Due to technological limits in assessing quantum algorithms on real quantum hardware on meaningful datasets, we conduct the experiments using the qasm simulator of Qiskit, which simulates quantum circuits using classical hardware. In Section <ref>, we evaluate the performance of the HQFS algorithm on two synthetic datasets and two real datasets. In Section <ref>, we assess the capabilities of QODA in finding outliers over four synthetic datasets and three real datasets.

§.§.§ Validation metrics

For the HQFS evaluation, we are interested in comparing the ranking of the features returned by our hybrid algorithm over the classical ranking. To measure the similarity between the rankings, we use the Rank Biased Overlap (RBO) measure [26], which weights the ranking similarity on the top ranks and returns a value in $[0,1]$. A high value of RBO corresponds to a high similarity on the top ranks.

As a measure of the effectiveness of our algorithms HQFS and ML-HQFS, we consider the accuracy:

\rm{ACC} =\frac{ \# TP + \# TN}{N},

where $\# \rm{TP}$ and $\# \rm{TN}$ are the number of features correctly discarded/non-discarded, respectively.

Concerning Outlier Detection, for evaluating the tightness of the lower bound of Proposition <ref>, we use the following metrics:

* Mean Absolute Error (MAE):

\rm{MAE} = \frac{1}{M} \sum_{p=0}^{M-1}| a_p-b_p|

* Mean Squared Error (MSE):

\rm{MSE}= \frac{1}{M} \sum_{p=0}^{M-1}| a_p-b_p|^2

* Root Mean Squared Error (RMSE):

\rm{RMSE}= \sqrt{\rm{MSE}}

where $a_p$ is the right hand side of equation (<ref>), and $b_p$ is the left hand side of the inequality.

Similarly to the Feature Selection case, we are interested in comparing the ranking of outliers provided by our hybrid algorithm against the one returned by the classical algorithm. In addition to the RBO measure, we evaluate QODA using the Precision at $n$ (P@$n$), by determining the number of records in the top $n$ ranks identified as outliers using differences and angles, respectively.

§.§ Experiments for Feature Selection

We first evaluate the performance of HQFS and ML-HQFS on two synthetic datasets by varying the parameter $s=O(\log\frac{1}{\varepsilon})$, the number of additional qubits required by Amplitude Estimation to get an estimate of the variance with (absolute) error $\varepsilon$ with respect
to the classical variance. Then, we test HQFS and ML-HQFS with $s=6$ on two real datasets. We assess our results by comparing the similarities of the final ranking of features of HQFS and ML-HQFS with respect to the ranking from the classical variance.

§.§.§ Dataset

For the experimental evaluation of HQFS, we consider two synthetic datasets ( and ) and the well-known real datasets  and . Both synthetic datasets have $N=32$ records and $M=10$ features: 7 informative features with high variance and 3 uninformative features with low variance, which are not expected to provide useful information for the analysis. The informative features are sampled from uniform distributions in [-1,1], while the uninformative features are sampled from two normal distributions with low variance. In particular, the uninformative features for  are sampled from a normal distribution with a standard deviation of 0.05. In contrast, the uninformative features for  are sampled from a normal distribution with a standard deviation of 0.5.

3c|     2c
s     HQFS      ML-HQFS     HQFS     ML-HQFS
2     0.05     0.37     0.21     0.20

3     0.05     0.35      0.21      0.20

4     0.05     0.37      0.21      0.20

5     0.15      0.99      0.27      0.20

6     0.43     0.98      0.31      0.37

RBO measures on synthetic datasets.

3c|     2c
s     HQFS      ML-HQFS     HQFS     ML-HQFS
2     0.3     1.0     0.3     1.0

3     0.3     1.0     0.3     1.0

4     0.3     1.0     0.3     1.0

5     0.8     1.0     0.8     1.0

6     0.7     1.0     0.7     1.0

Accuracy measure on synthetic datasets.

§.§.§ Results
In Table <ref>, we report the HQFS and ML-HQFS results on  and  datasets. To mitigate the high computational cost of simulation, we test the algorithm with a maximum value of $s=6$. However, theoretical analysis suggests that increasing the value of $s$ can yield superior results. We note that ML-HQFS performs better than HQFS for  datasets. However, the RBO measure is unsuitable for the  dataset because the variance of the uninformative features is high, and then the algorithm fails to distinguish between informative and uninformative features.  In Table <ref>, we report the accuracy achieved by our algorithm. We see that ML-HQFS always gets an accuracy of 100% while the accuracy of HQFS ranges from 30% to 80% depending on the number $s$ of additional qubits.

Features selected by ML-HQFS on  dataset.

Features selected by ML-HQFS on  dataset.

For both real datasets, we randomly sample 16 records 25 times and execute the ML-HQFS algorithm with $s=6$ on these samples. We fix the threshold value as $t=0.1$ for the features of  and $t=0.02$ for the features of . Then, we compare the percentage of times in which each feature is selected by the ML-HQFS to be discarded against the classical algorithm. Figure <ref> and Figure <ref>, show these comparisons for the  and  datasets, respectively. The figures show that both algorithms select the features with a quite similar frequency, with an MAE of 0.8% for the  dataset and an MAE of 2.15% for .

§.§ Experiments for Outlier Detection

We now present and discuss the numerical experiments conducted to evaluate the effectiveness of QODA on a series of benchmark datasets. The initial assessment involves testing the effectiveness of the heuristic used by QODA. The second experimental evaluation aims at assessing the accuracy of QODA using the qasm simulator of Qiskit.

§.§.§ Dataset

To evaluate the heuristic, we use four synthetic datasets generated with the PyOD library[<https://pyod.readthedocs.io/en/latest/index.html>] (, , , and ), where normal data is generated by a multivariate Gaussian distribution and outliers are generated by uniform distribution, and three real datasets[<https://odds.cs.stonybrook.edu>] (, , and ). They are defined as follows:

* : M=500 synthetic data with dimension N=20 whose 2% are outliers.

* : M=500 synthetic data with dimension N=30 whose 2% are outliers.

* : M=500 synthetic data with dimension N=20 whose 10% are outliers.

* : M=500 synthetic data with dimension N=30 whose 10% are outliers.

* : real dataset with M=148, N=18.

* : real dataset with M=214, N=9.

* : real dataset with M=278, N=30.

§.§.§ Results

We run two different kinds of experiments. The first kind is conducted to evaluate the effectiveness of the lower bound given by Proposition <ref>. In Table <ref>, we present the approximation errors introduced by the bound given in (<ref>), measured in terms of Mean Squared Error (MSE), Mean Absolute Error (MAE), and Root Mean Squared Error (RMSE). Our findings indicate that the lower bound of Proposition <ref> is very tight for all datasets considered.

dataset     MSE     MAE     RMSE
synth_a     3.02e-8     1.45e-4     1.73e-4

synth_b     1.92e-9     3.85e-5      4.38e-5

synth_c     2.53e-8     1.30e-4     1.60e-4

synth_d     1.57e-9     3.37e-5     3.96e-5
lympho     3.83e-7     5.27e-4     6.19e-4

glass     7.51-3     5.98e-2     8.66e-2

wbc     3.09e-5     5.21e-3     5.55e-3

Approximation errors of relation (<ref>)

The second kind of experiment aims to evaluate the effectiveness of Outlier Detection leveraging the variance of the differences $\Delta^{(p)}_{ij}$ instead of the variance of the angles $\theta_{ij}^{(p)}$. We compare the outlier rankings generated by the two methods to achieve this objective. Table <ref> presents the P@$n$ metric, which we used to conduct this comparison. We can see that the precision is very high, especially for synthetic datasets. Furthermore, we utilized the RBO measure to evaluate the overall outlier ranking of our heuristic, taking as ground truth the classical algorithm working with the angles. The table indicates that the outlier rankings obtained by the method leveraging the variance of differences are similar to the ground truth, particularly for the highest-ranked outliers.

dataset     n=5     n=10     n=15     n=20     n=25     n=30
synth_a     1.0     1.0     1.0     0.90     0.84     0.93

synth_b     1.0     1.0     0.93     0.95     0.84     0.90

synth_c     0.80     0.90     0.93     0.90     0.96     0.97

synth_d     1.0     1.0     1.0     0.95     0.96     0.93
lympho     0.80     0.60     0.67     0.70     0.76     0.77

glass     0.70     0.80     0.80     0.90     0.84     0.87

wbc     0.60     0.70     0.80     0.70     0.60     0.57

Precision-at-$n$ (P@$n$) of the algorithm taking as ground truth the classical algorithm working with the angles.

dataset     p=0.70     p=0.75     p=0.80     p=0.85     p=0.90     p=0.95
synth_a     0.88     0.89     0.89     0.90     0.90     0.91

synth_b     0.65     0.69     0.74     0.79     0.84     0.88

synth_c     0.65     0.69     0.74     0.78     0.83     0.88

synth_d     0.67     0.71     0.76     0.81     0.86     0.91
lympho     0.52     0.54     0.57     0.59     0.62     0.66

glass     0.51     0.55     0.59     0.63     0.68     0.74

wbc     0.60     0.63     0.66     0.68     0.68     0.67

RBO measure varying the parameter $p$

Currently, the availability of quantum hardware is limited, which means that quantum computation can only be simulated using classical hardware. Nevertheless, simulating quantum computation on classical hardware is expensive, so we can only execute basic versions of our algorithm. For this reason, we run QODA on two simple synthetic datasets with a single outlier each. The first has $M=5$ records with dimension $N=1$, and the second has $M=5$ records with dimension $N=3$.
By running the experiments with different random seed values for generating datasets five times, we found that QODA successfully identified the sole outlier in both datasets with a 100% accuracy rate.

§ CONCLUSION

In this study, we proposed a novel quantum algorithm called QVAR to estimate the variance within a set of values while in a superposition state. We utilized the QVAR subroutine in two prominent and crucial areas within data analysis: Feature Selection and Outlier Detection. This was accomplished by creating two hybrid approaches to tackle these tasks: the Hybrid Quantum Feature Selection (HQFS) algorithm and the Quantum Outlier Detection Algorithm (QODA).

Our experiments revealed that when the extra qubits are chosen properly, QVAR effectively computes an estimation of the classical variance. Consequently, concerning the Feature Selection task, the feature rankings generated by HQFS closely resemble those derived from classical algorithms, particularly for low-variance features. This suggests that HQFS correctly discards uninformative features, showcasing its accuracy in feature selection. The experiments for QODA indicate that the heuristic we proposed yields results comparable to those of the classical ABOD algorithm. Overall, our hybrid algorithm offers a promising approach for outlier detection tasks.

The algorithms we introduced are intended to process classical data as input. Nonetheless, the QVAR subroutine holds potential for broader application in scenarios involving an initial state of quantum values in superposition. We consider the prospect of leveraging the QVAR subroutine for other tasks as a direction for future research.

§.§ Acknowledgement

This study was carried out within the National Centre on HPC, Big Data and Quantum Computing - SPOKE 10 (Quantum Computing) and received funding from the European Union Next-GenerationEU - National Recovery and Resilience Plan (NRRP) - MISSION 4 COMPONENT 2, INVESTMENT N. 1.4 - CUP N. I53C22000690001. This manuscript reflects only the authors' views and opinions, neither the European Union nor the European Commission can be considered responsible for them. Partial support was also provided by INdAM-GNCS.
This work is also supported by the European Community under the Horizon 2020 programme G.A. 871042 SoBigData++ and by the NextGenerationEU programme under the funding scheme “SoBigData.it - Strengthening the Italian RI for Social Mining and Big Data Analytics” - Prot. IR0000013.

#1ISBN #1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1<https://doi.org/#1>et al.#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1#1<><#>1#1#1#1#1#1#1#1#1#1#1#1#1#1PreBibitemsHook

[1]

Nielsen, M.A.,
Chuang, I.L.:
Quantum Computation and Quantum Information (10th Anniversary Edition).
Cambridge University Press,

[2]

Lloyd, S.,
Mohseni, M.,
Rebentrost, P.:
Quantum algorithms for supervised and unsupervised machine learning.
arXiv preprint arXiv:1307.0411

[3]

Jović, A.,
Brkić, K.,
Bogunović, N.:
A review of feature selection methods with applications.
In: 2015 38th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO),
pp. 1200–1205

[4]

Chan, T.F.,
Golub, G.H.,
LeVeque, R.J.:
Algorithms for computing the sample variance: Analysis and recommendations.
The American Statistician

[5]

Schuld, M.,
Petruccione, F.:
Supervised Learning with Quantum Computers
vol. 17.

[6]

Tan, P.,
Steinbach, M.,
Kumar, V.:
Introduction to Data Mining.

[7]

Poggiali, A.,
Bernasconi, A.,
Berti, A.,
Del Corso, G.M.,
Guidotti, R.:
Quantum feature selection with variance estimation.
In: Proceedings of ESANN

[8]

Ling, R.F.:
Comparison of several algorithms for computing sample means and variances.
Journal of the American Statistical Association

[9]

Guyon, I.,
Elisseeff, A.:
An introduction to variable and feature selection.
J. Mach. Learn. Res.

[10]

Cai, J.,
Luo, J.,
Wang, S.,
Yang, S.:
Feature selection in machine learning: A new perspective.

[11]

Kumar, V.,
Minz, S.:
Feature selection: a literature review.

[12]

Mücke, S.,
Heese, R.,
Müller, S.,
Wolter, M.,
Piatkowski, N.:
Quantum feature selection.

[13]

Nembrini, R.,
Ferrari Dacrema, M.,
Cremonesi, P.:
Feature selection for recommender systems with quantum computing.

[14]

Chakraborty, S.,
Shaikh, S.,
Chakrabarti, A.,
Ghosh, R.:
A hybrid quantum feature selection algorithm using a quantum inspired graph theoretic approach.
Applied Intelligence

[15]

Boukerche, A.,
Zheng, L.,
Alfandi, O.:
Outlier detection: Methods, models, and classification.
ACM Computing Surveys (CSUR)

[16]

Guo, M.,
Liu, H.,
Li, Y.,
Li, W.,
Gao, F.,
Qin, S.,
Wen, Q.:
Quantum algorithms for anomaly detection using amplitude estimation.
Physica A: Statistical Mechanics and its Applications

[17]

Liang, J.-M.,
Shen, S.-Q.,
Li, M.,
Li, L.:
Quantum anomaly detection with density estimation and multivariate gaussian distribution.
Physical Review A

[18]

Mazouzi, R.,
Harel, P.:
A hybrid" quantum and classical" method for outlier detection.
In: Proceedings of the 2020 9th International Conference on Software and Computer Applications,
pp. 67–73

[19]

Kriegel, H.-P.,
Schubert, M.,
Zimek, A.:
Angle-based outlier detection in high-dimensional data.
In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,
pp. 444–452

[20]

Brassard, G.,
Hoyer, P.,
Mosca, M.,
Tapp, A.:
Quantum amplitude amplification and estimation.
Contemporary Mathematics

[21]

Giurgica-Tiron, T.,
Kerenidis, I.,
Labib, F.,
Prakash, A.,
Zeng, W.:
Low depth algorithms for quantum amplitude estimation.

[22]

Grinko, D.,
Gacon, J.,
Zoufal, C.,
Woerner, S.:
Iterative quantum amplitude estimation.
npj Quantum Information

[23]

Poggiali, A.,
Berti, A.,
Bernasconi, A.,
Del Corso, G.M.,
Guidotti, R.:
Quantum Clustering with k-Means: a Hybrid Approach

[24]

Park, D.,
Petruccione, F.,
Rhee, J.:
Circuit-based quantum random access memory for classical data.
Scientific reports

[25]

Kerenidis, I.,
Prakash, A.:
Quantum Recommendation Systems

[26]

Webber, W.,
Moffat, A.,
Zobel, J.:
A similarity measure for indefinite rankings.
ACM Transactions on Information Systems (TOIS)


11affiliationtext: Indian Institute of Technology Bombay,
Mumbai22affiliationtext: Indian Institute of Technology
Patna33affiliationtext: LG Soft India11affiliationtext: {manasjain,
<EMAIL_ADDRESS><EMAIL_ADDRESS>{gladvin.durai<EMAIL_ADDRESS>
# Natural Answer Generation: From Factoid Answer to Full-length Answer using
Grammar Correction

Manas Jain Sriparna Saha Pushpak Bhattacharyya Gladvin Chinnadurai Manish
Kumar Vatsa

###### Abstract

Question Answering systems these days typically use template-based language
generation. Though adequate for a domain-specific task, these systems are too
restrictive and predefined for domain-independent systems. This paper proposes
a system that outputs a full-length answer given a question and the extracted
factoid answer (short spans such as named entities) as the input. Our system
uses constituency and dependency parse trees of questions. A transformer-based
Grammar Error Correction model GECToR (2020), is used as a post-processing
step for better fluency. We compare our system with (i) Modified Pointer
Generator (SOTA) and (ii) Fine-tuned DialoGPT for factoid questions. We also
tested our approach on existential (yes-no) questions with better results. Our
model generates accurate and fluent answers than the state-of-the-art (SOTA)
approaches. The evaluation is done on NewsQA and SqUAD datasets with an
increment of 0.4 and 0.9 percentage points in ROUGE-1 score respectively. Also
the inference time is reduced by 85% as compared to the SOTA. The improved
datasets used for our evaluation will be released as part of the research
contribution.

##  1 Introduction

Question answering (QA) is an exercise of finding solutions for a query from a
given paragraph. Normally small spans of text, inclusive of named entities,
dates, etc. are extracted as answers. However, knowledge-base (KB) orientated
QA systems extract factoid solutions by using a structured query or neural
representation of the question. As a natural extension and post-processing
step, the retrieved factoid answer is transformed into a full-length natural
sentence. Unlike conversational chat-bots designed to mimic human communique
with out worrying to be factually correct, or assignment-orientated dialogue
system which places the retrieved solution in a predefined template, our
approach routinely generates correct full-length solutions, thereby, improving
it’s utilization in these situations.

Question : Who was the duke in the battle of hastings ?
Factoid answer : william the conqueror
Target : [The duke in the battle of hastings was william the conqueror. ,
William the conqueror was the duke in the battle of hastings.]

Example 1 - Sample from SqUAD dataset

Our overall research contributions are listed as follows:

  1. 1.

We achieve superior performance by incorporating a pre-trained transformer
encoder GEC sequence tagging system as a post processing step in our rule
based approach. In our experiments, encoders from RoBERTa outperform three
other cutting-edge transformer encoders (XLNet, BERT).

  2. 2.

We present a rule based approach for existential questions (Yes/No questions)
where Yes/No is considered as the factoid answer and natural answer is
generated by rearranging noun phrase and verb phrase present in the question.
We achieve good metrics (BLEU, ROUGE-1,2,L) and also analyze results of using
Grammar correction model, GECTOR, on top of the developed rule based system.

  3. 3.

We have made the existing dataset for this task more accurate by correcting
grammar errors in GOLD answer and have added alternate answers wherever
necessary. We also have created a small dataset for Existential QA having
different types of indirect questions as well. We will open source all the
improved datasets for further research.

The rest of the paper is organised as follows: Firstly we discuss some recent
works and related literature in section 2, after which we give details about
the data used for evaluating our system in section 3. After that we talk about
our approach in section 4; rule based in section 4.1 (factoid questions in
section 4.1.1, existential questions in section 4.1.2) and fine-tuned DialoGPT
in section 4.2. Following up on this, we provide details about our
experimental setup and talk about the GCM used as a post processing step in
section 5. Then in section 6 we provide the results & evaluation of our
approach; compare performance from other approaches. Then in section 7, we
give extensive error analysis of all approaches (Modified Pointer Generator
[SOTA] in section 7.1, fine-tuned DialoGPT in section 7.2 and rule based in
section 7.3) presented in the paper and discuss some ways to overcome them.
Lastly, we conclude our paper discussing future work in section 8.

##  2 Related Work

The task of retrieving exact information nowadays has become a very complex
and time consuming process as very huge amount of raw information are freely
available. This situation has prompted in development of QA systems, to
directly return the correct answer to a question asked in natural language
without making search and the information filtering tasks, as it is often the
case with search engines.
We generally notice two forms of representations addressed in the literature.
The answer can take the form of a paragraph selected from a set of text
passages retrieved from the web Asai et al. (2018), Du and Cardie (2018), Wang
and Jiang (2016), Wang et al. (2017), Oh et al. (2016), or it can be the exact
answer to the question extracted from a knowledge base or a span of texts from
a reading comprehension paragraph.
Despite the abundance of works in the field of QA systems, the answer
generation issue has received little attention. A first approach indirectly
addressing this task has been proposed in Brill et al. (2002). Indeed, the
authors aimed at diversifying the possible answer patterns by permuting the
question’s words in order to maximise the number of retrieved documents that
may contain the answer to the given question. Another answer representation
approach based on rephrasing rules has also been proposed in Agichtein and
Gravano (2000) within the context of query expansion task for document
retrieval and not purposely for the question-answering task.
It should be noted that these approaches only intend to diversify as much as
possible the answer representation patterns to a given question in order to
increase the probability of extracting the correct answer from the Web and do
not focus on the answer’s representation itself. It should also be noted that
these approaches are only applicable for QA systems which extract answers as a
text snippet and cannot be applied to short answers usually extracted from
knowledge bases.
Some recent works are presented in Pal et al. (2019) and Akermi et al. (2020).
Former work tried to tackle this issue by proposing a supervised approach
based on modifying pointer generator network See et al. (2017) while the
latter proposed a transformer based unsupervised approach incorporating the
use of language models to evaluate different possible answer structures. In
Pal et al. (2019), the model was trained on a small data set whose
question/answer pairs were extracted from machine comprehension datasets and
augmented manually which make generalization and capturing variation very
limited. In Akermi et al. (2020), authors have used syntactic parser to form
rules to get fragments useful for the formation of natural answer. They
assumed that only one word could be missing and it should be located before
the factoid answer within the identified structure. This assumption cannot be
generalized and can lead to incomplete answers with grammatical errors.
Our answer generation approach differs from these works as it is completely
rule based. We have utilized Omelianchuk et al. (2020) by which any number of
words at any place can be added or deleted. Indeed, we build upon the
intuitive hypothesis that a full length can be made by reformulation of the
words given in the question and factoid answer with few insertion/deletion in
between.

##  3 Data

There is just one available dataset Pal et al. (2019) for this task created
from reading comprehension dataset having 15000 manually annotated, 300000
automatically annotated from SQuAD Rajpurkar et al. (2016), HarvertingQA Du
and Cardie (2018) and 420 data points in test dataset taken from NewsQA
Trischler et al. (2017). After going through the dataset, we realized the
available dataset is not of high quality, having numerous grammatically
incorrect questions/answers and also wrong or grammatically incorrect target
answer in many cases. Due to this, improving the quality of dataset is the
need of the hour.
In natural language generation (NLG) systems, there can be more than one
correct answer but that is not incorporated well in the available dataset.

Question : Who is the ceo of google ?
Factoid answer : Sundar Pichai
Target : [(i) Sundar Pichai is the ceo of google. (ii) The ceo of google is
Sundar Pichai.]

In the existing dataset we see only target (i) type annotations but target
(ii) is also correct way to answer this question and should be added in the
annotation. So we improve the quality of the available dataset to handle the
above mentioned issues. We sampled 7200 data points from 15000 manually
annotated SqUAD samples Pal et al. (2019), 420 data points from NewsQA Pal et
al. (2019) and made the required changes in target answers; some data points
were removed due to incomplete question/answer. As given in Table 1, our
improved dataset has 6768 data points from SQuAD and 380 data points from
NewsQA. We have also created 166 data points of existential QA dataset
containing different varieties and forms of asking questions, including
indirect questions. The codes and the data sets will be publicly available
after the acceptance of the paper.

Question - type (i) : Does my fridge support quick freeze feature?
Question - type (ii) : Can you tell me if my fridge supports quick freeze
feature?
Target : [ No, your fridge does not support quick freeze feature. OR Yes, your
fridge supports quick freeze feature.]

Example 2 - Sample from Yes/No dataset

Dataset | Count
---|---
NewsQA (Factoid) | 380
SqUAD (Factoid) | 6768
Yes/No (Existential) | 166
Table 1:  Dataset used for our evaluation

##  4 Approach

In this section we explain the rule based approach and fine-tuned DialoGPT
approach developed.

###  4.1 Rule Based Approach

####  4.1.1 Factoid Questions

After observing a large number of examples in the available dataset we were
able to find patterns in the formation of natural answer using the sentence
structure of the question at its core. Initially the idea was to check the
accuracy by just replacing the WH words present in the question with the
factoid answer; we refer that approach as Rule Based V1 in below examples.
After analysing the output of the above idea on the failed cases led to a
finding of pattern related to the position of auxiliary verb and the main
verb. We used the constituency and dependency parsing output of the question
to find positions of auxiliary verb, main verb, noun phrases and verb phrases
present in the question and designed the algorithm; we refer this improved
version of our approach as Rule Based V2 (RBV2). Outputs of constituency
parser with Elmo Embeddings given in Joshi et al. (2018) and deep biaffine
attention neural dependency parser Dozat and Manning (2017) were extensively
used in the algorithm developed. We used open source AllenNLP library Gardner
et al. (2017) APIs of the above 2 parsers in developing our rule based system.
Below we will explain our approach using some examples and also discuss
implementation details. In the first version of our rule based approach (Rule
Based V1), we have just replaced the WH words (what, when, why, who, how etc.)
present in the question with the factoid answer. The WH word in the question
was found by using the outputs of POS tags of the AllenNLP constituency parser
Joshi et al. (2018). If the tag is ”WP” or ”WRB” or ”WDT” then we replace that
word with factoid answer. This phenomenon where sentence topic appears at the
front of the sentence as opposed to in a canonical position further to the
right is known as topicalization Prince (1998). Some examples are stated below
for better understanding of the approach:-

Question : What is the capital of India?
Factoid answer : Delhi
Rule Based V1 : Delhi is the capital of India
Target answer : Delhi is the capital of India

Example 3 - Self made Sample

Question : what was the space station crew forced to take shelter from?
Factoid answer : a piece of debris
Rule Based V1 : a piece of debris was the space station crew forced to take
shelter from
Target answer : the space station crew was forced to take shelter from a piece
of debris

Example 4 - Sample from NewsQA dataset

In the second version (Rule Based V2[RBV2]), we modify the above approach
based on the position of auxiliary verb and main verb present in the question.
We formulate the algorithm as to solve the problem of ordering of natural
answer, i.e., answer followed by portion from question or portion of question
followed by answer. So, if the main verb and auxiliary verb are consecutive,
factoid answer appears in the starting otherwise we add factoid answer in the
end. In the latter case, we start our answer from the word after the auxiliary
verb, till the main verb is encountered, then the auxiliary word is added to
the answer string. Then we copy the part of question after the main verb,
finally adding the factoid answer.
If question does not have verb in it then we add all words after auxiliary
word present in the question to our answer. We then add auxiliary verb,
finally adding the factoid answer. Some sample example outputs using this
approach are stated below:-

Question : What is the capital of India?
Factoid answer : Delhi
Rule Based V2(RBV2) : the capital of India is Delhi

CASE :- Main Verb not present

Question : what was the space station crew forced to take shelter from?
Factoid answer : a piece of debris
Rule Based V2(RBV2 : the space station crew was forced to take shelter from a
piece of debris

CASE :- Auxiliary Verb and Main Verb not

together

####  4.1.2 Existential Questions (Yes/No)

It would be incomplete if we just limit this task of natural answering to just
factoid questions. This task can have importance in the existential question
type as well in systems or apps tackling user queries using speech assistants
or chatbots. So, we tried formulating a rule based approach for existential
questions or yes/no questions using the dependency and constituency parse tree
of the questions. Generally such questions have a common structure: auxiliary
verb (AUX) followed by a noun phrase (NP) and then verb phrase (VP) in the
end, i.e., AUX-NP-VP. The natural answers to such questions can be made by
reordering the above parts to NP-AUX-VP. This was implemented using the output
of AllenNLP dependency parse tree model. In addition we start the answer with
”yes,” or ”no,” so as to create a more natural sounding answer.

Question : Can you tell if fridge supports quick freeze feature?
Factoid answer : Yes
RB : Yes, fridge does supports quick freeze feature.
RB + RoBERTa :Yes, fridge does support quick freeze feature.

Example 5 - Sample from Yes/No dataset

###  4.2 Fine-tuned DailoGPT

In order to resolve the problem of fluency which is very important for the
task of natural answering, we explored the latest cutting edge GPT Radford et
al. (2019) models which are very popular in generating fluent responses. We
found the DialoGPT Zhang et al. (2020) model is the best fit for this task as
it was trained on large corpus of dialogue conversations which is somewhat
relevant to the task in hand. We fine tuned the above pre-trained model
publicly available on approximately 13000 manually annotated data points given
by Pal et al. (2019).
DialoGPT (dialogue generative pre-trained transformer) (Zhang et al., 2020) is
a tun-able giga word scale neural network model for generation of
conversational responses, trained on Reddit data. Trained on 147M
conversation-like exchanges extracted from Reddit comment chains over a period
spanning from 2005 through 2017, DialoGPT extends the Hugging Face PyTorch
transformer to attain a performance close to human both in terms of automatic
and human evaluation in single-turn dialogue settings. Our aim was to develop
a system which produces natural answer given any type of question and factoid
answer in the input as DialoGPT was created with the aim of neural response
generation and the development of more intelligent open domain dialogue
systems.
DialoGPT extends GPT-2 (Radford et al., 2019) to address the challenges of
conversational neural response generation. Neural response generation is a
subcategory of text-generation that shares the objective of generating
natural-looking text (distinct from any training instance) that is relevant to
the prompt. Normally DialoGPT model was created to make conversational
chatbots and their fine-tuning is also done for building conversational agent
where the input is the question asked and all the previous dialogues are kept
as series of context and are passed as input to the model for training. But
here for our task, we concatenate the question with its extracted factoid
answer and keep manually annotated answers as target in fine-tuning the model.
For inference, question and factoid answer are concatenated and provided as
input to the fine-tuned model to generate a response.

##  5 Experimental Setup

We have used Tesla T4 16GB GPU to carry out the experiments. For factoid
questions, we have used two datasets having 380 and 6768 data points as given
in Table 1. Experimental results are shown in Table 2 and 3, respectively. For
existential questions, we have used created data set with 166 examples.
Results of confirmatory dataset are reported in Table 4.
As a post processing step of all our rule based approaches, we have used a
pre-trained transformer encoder, grammar error correction (GEC) given in
Omelianchuk et al. (2020). This model was available with 3 cutting edge
transformer encoders namely BERT, RoBERTa and XLNet. Experiments were carried
out using all 3 above encoder based GEC models as post processing steps in our
rule based approach.
For fine-tuning DialoGPT, we took a pretrained DialoGPT-small (117M
parameters) and fine-tuned with around 13000 manually annotated samples data
from Pal et al. (2019). We trained the model for 8 epochs. The results on 380
data points (cross validation) of NewsQA dataset by the fine-tuned model are
reported in Table 2.

##  6 Results

We use standard BLEU Papineni et al. (2002) (NLTK), ROUGE-1, 2, L Lin (2004)
(rouge-score) metrics to evaluate our system and compare our system with other
approaches. In Table 2, 3, 4 : ”RBV2+RoBERTa” means our rule based approach
with grammar correction performed by RoBERTa encoder and so on.
Table 5 illustrates a qualitative comparison of outputs from different
approaches explored in this paper.
In Table 2, we see an increase in BLEU, ROUGE-2, ROUGE-L scores on using
RoBERTa encoder Grammar Correction Model (GCM) as compared to not using it. It
is also clear that RoBERTa based encoder GCM is superior as compared to other
encoders due to higher BLEU and ROUGE scores. Our developed approach attains
very comparable results in terms of BLEU and ROUGE-1, 2, L scores and reduces
inference time by 85% as compared to the state of the art MPG model. Avg. time
in table 2, 3 denotes the average time taken by the model or algorithm to
generate answer for 1 (question, factoid answer) input. ROUGE-1 and ROUGE-L
scores are almost same with a difference of 3 and 1 percentage points in BLEU
and ROUGE-2 scores, respectively. BLEU and ROUGE scores provided in all the
tables are on the scale of 100.
In Table 3, reported ROUGE-1 and ROUGE-L scores are almost same. BLEU and
ROUGE-2 scores for our approach (RBV2 + GCM) are a bit lesser than SOTA model
(MPG).
There are instances in the above tables where employing a GCM sometimes
reduces the BLEU or ROUGE scores especially in Table 3. This phenomenon is
very much related to the target (GOLD) answers based on which the scores are
calculated. This can occur because of insertion/deletion of punctuation in
between by GCM but not present in target answer and vice-versa. In many cases,
target answers do not follow correct grammar which sometimes leads to lower
scores. But in such cases also the overall quality, fluency and adequacy of
the answers improved by GCM are much better.
Table 2 illustrates that performance of fine-tuned DialoGPT is comparatively
very low as compared to other approaches in cross evaluation. Main problem
with this approach was the problem of hallucination as explained in Maynez et
al. (2020) which decreases the accuracy of the approach and hence we conclude
that it is not useful for this task. Due to that, we have skipped the results
of the fine-Tuned model in Table 3.
In Table 4, scores are calculated on a very small dataset and best scores are
achieved by simply employing the rule based model without using GCM. We still
argue to use a GCM as a post processing step in this type as well due to its
ability to improve the overall quality of the answers. This improvement in
quality can not be measured using these scores but can surely improve the user
satisfaction. This kind of task in existential questions is in best of our
knowledge first time presented so there is no baseline model to compare our
results with.

Model | BLEU | ROUGE-1 | ROUGE-2 | ROUGE-L | Avg. time (sec.)
---|---|---|---|---|---
MPG(2019) | 84.9 | 95.7 | 89.4 | 93.9 | 2.54
RBV2 | 79.1 | 96.1 | 85.5 | 93.1 | 0.382
RBV2+BERT | 77.6 | 94.4 | 85.4 | 92.4 | 0.397
RBV2+RoBERTa | 81.7 | 95.7 | 88.2 | 93.6 | 0.394
RBV2+XLNET | 80.3 | 94.8 | 87.0 | 92.9 | 0.4
DialoGPT | 50.3 | 73.4 | 49.3 | 70.0 | 0.908
Table 2:  Results on 380 data points of NewsQA dataset Model | BLEU | ROUGE-1 | ROUGE-2 | ROUGE-L | Avg. time (sec.)
---|---|---|---|---|---
MPG(2019) | 75.8 | 94.4 | 87.4 | 91.6 | 2.54
RBV2 | 74.8 | 95.3 | 83.1 | 90.3 | 0.399
RBV2+BERT | 71.5 | 93.9 | 82.4 | 89.5 | 0.411
RBV2+RoBERTa | 72.1 | 94.0 | 83.1 | 89.8 | 0.411
RBV2+XLNET | 71.2 | 93.6 | 82.3 | 89.4 | 0.413
Table 3:  Results on 6768 data points of SqUAD dataset Model | BLEU | R-1 | R-2 | R-L
---|---|---|---|---
RB | 70.2 | 87.3 | 75.0 | 84.8
RB+BERT | 62.7 | 85.5 | 71.6 | 83.4
RB+RoBERTa | 66.6 | 84.5 | 73.0 | 84.2
RB+XLNET | 67.5 | 86.6 | 74.0 | 84.6
Table 4:  Results on 166 data points of existential questions dataset created by us; Here in the table R represents Rouge, R-1 means ROUGE-1 and so on Input | Output
---|---
Ques \- where was the bus going ? |  MPG Pal et al. (2019) \- the bus going was at phoenix, arizona.
Factoid Ans. \- phoenix, arizona |  FT DialoGPT [ours] - the bus was going to phoenix, anrizona.
|  RBV2 [ours] - the bus was going phoenix, arizona .
|  RBV2+GCM [ours] - The bus was going to Phoenix, Arizona.
Table 5:  Comparison of outputs from all approaches discussed in the paper for
an input example. Here MPG represents the state of the art deep learning model
using Pointer Generator technique. FT DialoGPT represents the results of the
fine-tuned model of DialoGPT for this task. RBV2+GCM represents the results of
using the GEC Model as a post processing step. Here we used the RoBERTa
encoder GECTOR model as GCM.

##  7 Error Analysis

Below we present some qualitative discussion and error analysis of answers
generated by existing approaches and our proposed approach.

###  7.1 Modified Pointer Generator(MPG)

This approach was taken from Pal et al. (2019). The main limitations of this
approach are stated in below points. Also there were failure cases wherein the
model just outputs the question itself which may be due to model becomes
biased towards adding more part from the question than the factoid answer
which results in complete copying of the question in some cases. Below are the
main types of failure cases stated :-

  * •

Incoherent sentence due to failure in reasoning

  * •

Repetition of words

  * •

Outputs only the factoid answer

  * •

Outputs clausal answers

  * •

Failure to incorporate morphological variations

This can also be seen in Table 5 where MPG makes error in answer generation.
Word positions of was and going are interchanged and ”at” is added which is
wrong, correct addition should be ”to”.
Overall, this model doesn’t attain good results even for very straight forward
example cases present in our dataset and so using it for general case queries
would not be very beneficial. Also inference time of this model is very high
(last column of Table 2,3).

###  7.2 Fine-tuned DialoGPT

Problem of adding unwanted things in the final answers which doesn’t have any
mention in the question and the factoid answer often called as hallucination
Maynez et al. (2020) is the main shortcoming of this model.
There are instances where factoid answer is not even present in the final
answer. Also there are numerous cases where DialoGPT model makes error in
copying numerical data for e.g. year, number etc. The model has some errors
copying the proper nouns as given in the questions. The final answer has those
names but with changed spelling. (e.g.:- elizabeth - elizabetha; alexander -
alexandrick). This is also evident from the example given in Table 5 where
DialoGPT has changed arizona spelling to ”anrizona”. This leads to low BLEU
and ROUGE scores. For eg,

Question : What is going live on tuesday?
Factoid answer : web-based on-demand television and movie service
Fine-Tuned DialoGPT : on tuesday, the web-based version of ”net based”
television and film service.
Target answer : web-based on-demand television and movie service is going live
on tuesday.

Example 6 - Sample from NewsQA dataset

In the above example we find very poor quality of answer generated. Here we
see additional ”net-based” getting added which makes this model unreliable for
this task.

###  7.3 Rule Based Model

This approach works by reordering question sentence structure and copy pasting
the factoid answer; and so if factoid answer is not factual based or is a
clausal answer then this approach may fail. Also the generated answers may be
grammatically wrong in terms of missing a word like in, is, to etc. which is
corrected by the transformer based grammar correction used as a post
processing step; other type of grammatical error by rule based approach is
incorrect positioning of AUX word (e.g. is, are etc) in the answer which is
not corrected by the Omelianchuk et al. (2020) sometimes.

Question : where did lewis partnership begin?
Factoid answer : started as a single shop on oxford street in london, opened
in 1864 by john.
RBV2 : lewis partnership begin started as a single shop on oxford street in
london, opened in 1864 by john.
Target answer : lewis partnership begin started as a single shop on oxford
street in london, opened in 1864 by john.

Example 7 - Sample from SqUAD dataset

In the above example, output answer had both begin and started in it which is
not right, this is because the factoid answer contains a clause having verb
part included. Currently, in our system we are not checking the factoid answer
structure to define our answers and hence for these examples this model may
fail. Since the approach works on the question structure so if question is not
properly well formed or incomplete then the answers will not be correct.
Instances where the question is of type ”how many”; the word ”many” can be
added or not added based on the type of factoid answer given. In such cases we
rely on the GCM model to perform necessary corrections but sometimes the GCM
model fails to make the changes.
Questions having a subordinate clause are a challenge to this approach. Such
examples generally have 2 WH words and so sometimes are difficult to handle.
With some modifications we will be able to handle those questions as well in
our rule based approach by first finding out the main clause in the question
and masking the subordinate clause temporarily considering if that subordinate
clause never existed and then unmasking it after answer generation.
As highlighted by van Miltenburg et al. (2021), the under-reporting of errors
and lack of extensive error analysis of NLG system output is quite common
nowadays. This prevents researchers to get an idea about the specific
weakeness of SOTA and improved model. So in this work we categorised the
errors for the 6768 data points of SqUAD dataset. These errors are categorised
as: extra words like do, does, is, was; incorrect words like much, many;
misplaced words like is, were, was, are, has; missing words like in, to, on,
during, by, until, through, at, after, between; wrong preposition, word order.
Count of these categories are reported in 6. The GCM as the post processing
step in our approach is able to correct most of above errors for our system
and thus improving the quality of our generated answers as can be seen in
Table 5.

Grammar Error | Count
---|---
Grammar Error [extra] | 103
Grammar Error [incorrect] | 25
Grammar Error [misplaced] | 254
Grammar Error [missing] | 815
Table 6:  Count of categories of grammar errors by the rule based algorithm
without using the GCM. These numbers are for the 6768 data points from SqUAD
dataset

##  8 Conclusion & Future Work

In this work, we have worked on the task of generating full-length natural
answers given the question and the factoid answer. We have solved this task by
designing a rule based approach using syntactic parser. A Grammar Correction
Model (GCM) is used as a post processing step to improve the fluency of
generated natural answer. Our approach RBV2 and RoBERTa based encoder GCM
achieves superior results than the state of the art deep learning model in
terms of ROUGE-1 score, quality of the answers generated and inference time.
This system can be used at the final stage of any domain-specific QA system or
answering user troubleshooting queries where factoid answer is extracted by a
knowledge base or context paragraphs. This approach is developed using general
rules of answer generation and so can be applied to all domains as compared to
supervised system which gets biased to the type of training data given. We
have also improved the quality of existing dataset by creating 2 sets having
6768 and 380 data points, respectively. We have also created a dataset of 166
data points of existential (yes/no) questions.
We plan to make our system more robust especially for questions having
subordinate clauses present. We will work on making a complete system which
can classify existential and factoid questions and use our developed system on
top of that. We plan to give our generated answers for review to some
proficient English speaker and ask for scores on fluency, adequacy of our
generated answer and other approachs’ answers. Further work needs to be done
to investigate the performance of reinforcement learning based techniques for
solving this task, keeping BLEU or ROUGE score as the reward. We plan on
adding more variation to the data by annotating and correcting additional QA
pairs both in factoid and existential questions.

## References

  * Agichtein and Gravano (2000) Eugene Agichtein and Luis Gravano. 2000.  ¡i¿snowball¡/i¿: Extracting relations from large plain-text collections.  In _Proceedings of the Fifth ACM Conference on Digital Libraries_ , DL ’00, page 85–94, New York, NY, USA. Association for Computing Machinery.
  * Akermi et al. (2020) Imen Akermi, Johannes Heinecke, and Frédéric Herledan. 2020.  Tansformer based natural language generation for question-answering.  In _Proceedings of the 13th International Conference on Natural Language Generation, INLG 2020, Dublin, Ireland, December 15-18, 2020_ , pages 349–359. Association for Computational Linguistics.
  * Asai et al. (2018) Akari Asai, Akiko Eriguchi, Kazuma Hashimoto, and Yoshimasa Tsuruoka. 2018.  Multilingual extractive reading comprehension by runtime machine translation.  _CoRR_ , abs/1809.03275.
  * Brill et al. (2002) Eric Brill, Susan Dumais, and Michele Banko. 2002.  An analysis of the AskMSR question-answering system.  In _Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)_ , pages 257–264. Association for Computational Linguistics.
  * Dozat and Manning (2017) Timothy Dozat and Christopher D. Manning. 2017.  Deep biaffine attention for neural dependency parsing.  _ArXiv_ , abs/1611.01734.
  * Du and Cardie (2018) Xinya Du and Claire Cardie. 2018.  Harvesting paragraph-level question-answer pairs from Wikipedia.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1907–1917, Melbourne, Australia. Association for Computational Linguistics.
  * Gardner et al. (2017) Matt Gardner, Joel Grus, Mark Neumann, Oyvind Tafjord, Pradeep Dasigi, Nelson F. Liu, Matthew Peters, Michael Schmitz, and Luke S. Zettlemoyer. 2017\.  Allennlp: A deep semantic natural language processing platform.
  * Joshi et al. (2018) V. Joshi, Matthew E. Peters, and Mark Hopkins. 2018.  Extending a parser to distant domains using a few dozen partially annotated examples.  In _ACL_.
  * Lin (2004) Chin-Yew Lin. 2004.  ROUGE: A package for automatic evaluation of summaries.  In _Text Summarization Branches Out_ , pages 74–81, Barcelona, Spain. Association for Computational Linguistics.
  * Maynez et al. (2020) Joshua Maynez, Shashi Narayan, Bernd Bohnet, and Ryan McDonald. 2020.  On faithfulness and factuality in abstractive summarization.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1906–1919, Online. Association for Computational Linguistics.
  * van Miltenburg et al. (2021) Emiel van Miltenburg, Miruna Clinciu, Ondřej Dušek, Dimitra Gkatzia, Stephanie Inglis, Leo Leppänen, Saad Mahamood, Emma Manning, Stephanie Schoch, Craig Thomson, and Luou Wen. 2021.  Underreporting of errors in NLG output, and what to do about it.  In _Proceedings of the 14th International Conference on Natural Language Generation_ , pages 140–153, Aberdeen, Scotland, UK. Association for Computational Linguistics.
  * Oh et al. (2016) Jong-Hoon Oh, Kentaro Torisawa, Chikara Hashimoto, Ryu Iida, Masahiro Tanaka, and Julien Kloetzer. 2016.  A semi-supervised learning approach to why-question answering.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 30(1).
  * Omelianchuk et al. (2020) Kostiantyn Omelianchuk, Vitaliy Atrasevych, Artem Chernodub, and Oleksandr Skurzhanskyi. 2020.  GECToR – grammatical error correction: Tag, not rewrite.  In _Proceedings of the Fifteenth Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 163–170, Seattle, WA, USA â†’ Online. Association for Computational Linguistics.
  * Pal et al. (2019) Vaishali Pal, Manish Shrivastava, and Irshad Bhat. 2019.  Answering naturally: Factoid to full length answer generation.  In _Proceedings of the 2nd Workshop on New Frontiers in Summarization_ , pages 1–9, Hong Kong, China. Association for Computational Linguistics.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
  * Prince (1998) E. Prince. 1998.  On the limits of syntax, with reference to left-dislocation and topicalization.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  SQuAD: 100,000+ questions for machine comprehension of text.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 2383–2392, Austin, Texas. Association for Computational Linguistics.
  * See et al. (2017) Abigail See, Peter J. Liu, and Christopher D. Manning. 2017.  Get to the point: Summarization with pointer-generator networks.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1073–1083, Vancouver, Canada. Association for Computational Linguistics.
  * Trischler et al. (2017) Adam Trischler, Tong Wang, Xingdi Yuan, Justin Harris, Alessandro Sordoni, Philip Bachman, and Kaheer Suleman. 2017.  NewsQA: A machine comprehension dataset.  In _Proceedings of the 2nd Workshop on Representation Learning for NLP_ , pages 191–200, Vancouver, Canada. Association for Computational Linguistics.
  * Wang and Jiang (2016) Shuohang Wang and Jing Jiang. 2016.  Machine comprehension using match-lstm and answer pointer.  _CoRR_ , abs/1608.07905.
  * Wang et al. (2017) Tong Wang, Xingdi Yuan, and Adam Trischler. 2017.  A joint model for question answering and question generation.  _CoRR_ , abs/1706.01450.
  * Zhang et al. (2020) Yizhe Zhang, Siqi Sun, Michel Galley, Yen-Chun Chen, Chris Brockett, Xiang Gao, Jianfeng Gao, Jingjing Liu, and Bill Dolan. 2020.  DIALOGPT : Large-scale generative pre-training for conversational response generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 270–278, Online. Association for Computational Linguistics.