# A Framework to Generate High-Quality Datapoints for Multiple Novel Intent
Detection

1Ankan Mullick 2Sukannya Purkayastha11footnotemark: 1 1Pawan Goyal 1,3Niloy
Ganguly
1Department of Computer Science and Engineering, IIT Kharagpur
2TCS Research, India
3Leibniz University of Hannover, Germany
<EMAIL_ADDRESS><EMAIL_ADDRESS>
{pawang<EMAIL_ADDRESS>Equal contributionWork done while the author
was a student at IIT Kharagpur

###### Abstract

Systems like Voice-command based conversational agents are characterized by a
pre-defined set of skills or intents to perform user specified tasks. In the
course of time, newer intents may emerge requiring retraining. However, the
newer intents may not be explicitly announced and need to be inferred
dynamically. Thus, there are two important tasks at hand (a). identifying
emerging new intents, (b). annotating data of the new intents so that the
underlying classifier can be retrained efficiently. The tasks become specially
challenging when a large number of new intents emerge simultaneously and there
is a limited budget of manual annotation. In this paper, we propose MNID
(Multiple Novel Intent Detection) which is a cluster based framework to detect
multiple novel intents with budgeted human annotation cost. Empirical results
on various benchmark datasets (of different sizes) demonstrate that MNID, by
intelligently using the budget for annotation, outperforms the baseline
methods in terms of accuracy and F1-score.

##  1 Introduction

The conversational agents such as Amazon Alexa, Apple Siri are characterised
by the skill of understanding intents which help them to efficiently handle a
user’s query. For example, the query ‘Will it be colder in Ohio’ requires
getting the weather updates for the city ‘Ohio’ and would be associated to the
intent GetWeather. The agents are trained with a pre-defined set of intents
such as {GetWeather, RateBook, BookRestaurant} so as to perform the goal-
oriented user tasks. But with the passage of time, a user may be interested in
performing newer tasks adding hitherto unknown intents. For example, ‘Play
some music from 1954’ would be associated to the intent PlayMusic that may not
be a part of the set of pre-defined intents.

Emergence of novel intent detection has been periodically checked by different
models in the last decade. There are works on incremental learning in dynamic
environment for evolving new classes Zhou and Chen (2002); Kuzborskij et al.
(2013); Scheirer et al. (2012). There are also several approaches Sun et al.
(2016); Masud et al. (2010); Haque et al. (2016); Wang et al. (2020); Mu et
al. (2017b, a) to detect new classes in the form of outlier detection but they
do not distinguish among multiple new class labels so are not effective in
novel multi-class detection. Xia et al. (2018); Siddique et al. (2021) detect
user intents using zero-shot generalized intent detection framework. However,
they assume that the unseen intent class LABELS are already known, while in
our case neither the number of unseen intent classes, nor the corresponding
class labels are known. The other line of works Xia et al. (2021); Halder et
al. (2020) supply the system with new intents, albeit with a limited amount of
tagged data per class and then have an efficient algorithm to incrementally
learn new classes. These models work on the assumption that some instances of
these new classes would be provided for model building. However, in a
realistic setting, the system may not have any knowledge of the number and
types of new intents appearing, it may at most understand that some new out-
of-domain samples are generated. So, the problem statement is to probe the
incoming data wisely and use minimum human intervention to identify all types
of novel intents emerging and intelligently tag a limited set of data covering
all discovered intents, which can be be fed into a model for retraining.

More concretely the system is at first trained with an initial set of known
intents; side-by-side an out-of-distribution (OOD) detector classifier is also
trained to identify datapoints which do not fit the known intents. When
substantial amount of such points are detected, the task is to (a) identify
whether the points are originating from introduction of a single novel intent
or multiple and (b) choose (a limited number of) samples to annotate so that
the classifier can be retrained efficiently.

In order to determine the number of novel intents present in the OOD data, we
undertake a clustering based approach with the idea that each cluster would
represent a novel intent. By increasing the cluster number progressively, we
can make a highly accurate estimate of the number of novel intents. If sample
points of an intent mainly correspond to a well formed cluster, the
implication is that without much probing we can shortlist enough training
samples (through silver tagging) for that class. On the other hand, if the
sample points of an intent tend to interwine with other intent points in the
feature space, these can be considered as uncertain points and require human
intervention for tagging (gold tagging). With this intuition in place, we
design a mix of silver and gold tagging to produce high-quality training
samples which can be used to retrain the classifier.

Our proposed framework of Multiple Novel Intent Detection (MNID) is compared
with competitive baselines and evaluated across several standard public
datasets in NLU domain where it performs substantially better. We use datasets
with different number of intent classes. SNIPS Coucke et al. (2018) and ATIS
Tur et al. (2010) are smaller datasets, consisting of less number intent
classes - 7 and 21, respectively. HWU Liu et al. (2019a), BANKING Casanueva et
al. (2020) and CLINC Larson et al. (2019) consist of large number of intent
classes - 64, 77 and 150, respectively.

The paper is organized as follows. We discuss the Problem Setting and solution
overview in Section 2. Our algorithmic framework is described in Section 3. We
present the datasets with experimental statistics and data pre-processing in
Section 4. In Section 5, we discuss the experimental design and baselines.
Detail evaluation results with different algorithmic variations are in Section
6. We conclude with a summary in Section 7111Codes are in -
https://github.com/sukannyapurkayastha/MNID.

Algorithm 1 Multiple Novel Intent Detection (MNID)

1:Input

2: $D_{init}$ Initial Labelled Data

3: $\mathcal{T}$ Blind Test Data For Evaluation

4: $B$ Total Annotation Budget

5:Parameters

6: $D$ Total Data points

7: $\mathcal{L}$$\leftarrow D_{init}$

8: $\mathcal{OS}$$\leftarrow$ OODD($D$, $D_{init}$)

9:procedure Multiple Novel Intent Detection

10: $\mathcal{L}$, $N_{new}$, $\mathcal{CL}\leftarrow$
NCD($\mathcal{OS},\mathcal{L}$)

11: if $\mathcal{L}<B$ then

12: $\mathcal{L}$, $\mathcal{G_{CL}}$, $\mathcal{B_{CL}}\leftarrow$
CBQA($\mathcal{L}$, $\mathcal{CL}$)

13: end if

14: Train Model $\mathcal{M}$ on $\mathcal{L}$, predict on the remaining
points in the clusters to get the confidence score (CS) of each data point and
store in $All_{CS}$.

15: if $\mathcal{L}<B$ then

16: $\mathcal{L}\leftarrow$ PPAS($\mathcal{L}$, $All_{CS}$,
$\mathcal{G_{CL}}$, $\mathcal{B_{CL}}$, $B$)

17: end if

18: Train model $\mathcal{M}$ on $\mathcal{L}$ and test on $\mathcal{T}$ to
find out Accuracy, F1 for all classes.

19:end procedure

Algorithm 2 OOD Detection Algorithm
OODD($|D|$, $|D_{init}|$)

1:Train OOD-SDA on $D_{init}$ and predict on $(D-D_{init})$ to get OOD
samples, $\mathcal{OS}$

2:Return $\mathcal{OS}$

Algorithm 3 Novel Class Detection NCD($\mathcal{OS}$, $\mathcal{L}$)

1:Initial number of clusters, $K=1$.

2:Number of new classes, $N_{new}=0$.

3:while $N_{new}\geq\lfloor K/2\rfloor$ do

4: Perform $K$-Means Clustering on $\mathcal{OS}$

5: Annotate $x$ ($\geq$ 2) points from each cluster. That results in
discovering of $n^{\prime}$ new classes

6: Add $x*K$ point labels to $\mathcal{L}$

7: $N_{new}\leftarrow N_{new}+n^{\prime}$

8: $K\leftarrow 2*K$

9:end while

10:$\mathcal{CL}$ = Store All $K$ Clusters

11:Return ($\mathcal{L}$,$N_{new}$, $\mathcal{CL}$)

Algorithm 4 Cluster Quality Based Annotation CQBA($\mathcal{L}$,
$\mathcal{CL}$)

1:Take $p$ points from each of the clusters ($\mathcal{CL}$) and annotate to
find Good Cluster ($\mathcal{G_{CL}}$) and Bad Cluster ($\mathcal{B_{CL}}$).

2:Add annotated $p*|\mathcal{CL}|$ point labels to $\mathcal{L}$.

3:for each Bad Cluster do

4: Take $q$ more points from Bad cluster and annotate.

5: Add $q*|\mathcal{B_{CL}}|$ point labels to $\mathcal{L}$.

6:end for

7:Return($\mathcal{L}$, $\mathcal{G_{CL}}$, $\mathcal{B_{CL}}$)

Algorithm 5 Post-Processing Annotation Strategy PPAS($\mathcal{L}$,
$All_{CS}$, $\mathcal{G_{CL}}$, $\mathcal{B_{CL}}$, $B$)

1:for Each point with CS in $All_{CS}$ do

2: if $CS\geq\mathcal{TH}$ and point in $\mathcal{G_{CL}}$ and average cosine
similarity with already annotated points of that class $\geq\tau$ then

3: $L_{s}\leftarrow$ Silver Annotation Strategy

4: end if

5:end for

6:while $|\mathcal{L}|<B$ do

7: Select datapoint with least CS

8: if $\mathcal{B_{CL}}$ exists then

9: From $\mathcal{B_{CL}}$ in Round-Robin way

10: else

11: From $\mathcal{G_{CL}}$ in Round-Robin way

12: end if

13: $L_{g}\leftarrow$ Gold Annotation Strategy

14: $\mathcal{L}$ $\leftarrow$ $\mathcal{L}$ \+ $L_{g}$

15:end while

16:$\mathcal{L}\leftarrow$ $\mathcal{L}$ $\cup$ $L_{s}$ $\cup$ $L_{g}$

17:Return ($\mathcal{L}$)

##  2 Problem Setting and Solution Overview

Problem Setting: To formally describe the problem setting, let there be a
dataset $W$ containing overall $N$ classes. However, the value of $N$ is not
known apriori. Let $T\in W$ be the test set and $W-T=D$ be the rest of the
dataset, out of which $|D_{init}|~{}(<<|D|)$ labelled data of
$N_{init}~{}(<N)$ classes is initially provided, while the rest of the data is
unlabelled. The task is to design an algorithm to (a). detect all the
remaining $N-N_{init}$ classes and (b). spent a limited budget ($B$ \-
$|D_{init}|$) to annotate high fidelitous new datapoints, so that the
classifier can achieve high accuracy when retraining.

Solution Overview: The solution steps are as follows: (a) Identify the OOD
(out of distribution) datapoints which do not belong to the initial $N_{init}$
classes. This can be considered as a preprocessing step. (b) Use a part of the
allotted budget to annotate a portion of these OOD datapoints. These points
(for annotation) are selected by repeatedly running a clustering algorithm
with increasing number of clusters as input, and choosing cluster cluster
centre points to identify the unknown classes. Rationale: The
intuition/expectation is that each cluster hosts a separate intent, hence
annotating the cluster centres would lead to discovery of maximum number of
novel intents. (c) Further identify the classes which are well clustered in
feature space and which are not. Use another portion of the budget to increase
the annotations of not-so well formed clusters and then build up a classifier
with all the classes. Rationale: If a cluster is well-formed, most likely it
is hosting a single class, hence there is no need to annotate further points
there, rather annotate more points in not-so-well-formed clusters. (d) Use the
classifier to classify points from the clusters. Identify low-confidence
points from the bad clusters and annotate them. High-confidence points from
good clusters are silver annotated. Rationale: The low-confidence points in
the bad clusters are the most uncertain points, hence annotating them helps in
increasing classifier accuracy. Similarly high-confident points in the good
clusters almost surely will belong to that particular cluster, hence silver
annotation is pursued. (e). Retrain the classifier.

The overall MNID framework with different algorithmic modules is shown in Fig.
1.

Figure 1: End-to-end architecture of MNID: Multiple
Novel Intent Detection

##  3 MNID: Solution Detail

The proposed framework for Multiple Novel Intent Detection (MNID) is explained
through Algorithm 1. As highlighted in the overview, the algorithm consists of
data pre-processing step, followed by three stages, each of them are discussed
below. The total budget of (gold) annotation is $B$. Besides the system can
undertake unlimited silver annotation. The advantage of silver strategy is
that it is free as no human probing is required. However, it is also likely to
bring in noise if used indiscriminately.

Pre-process: OOD Detection (OODD): For the dataset ($D$), this module
(Algorithm 2) takes the initial labelled data ($D_{init}$) as input and
predicts the Out-of-Domain (OOD) samples on the remaining data,
($D-D_{init}$). We call the set of OOD samples predicted as ${\mathcal{OS}}$.
This is a part of the data pre-processing.

Stage 1. Novel Class detection (NCD): In this sub-module (Algorithm 3), we aim
at finding all the new classes, $N_{new}.$ On the OOD samples
(${\mathcal{OS}}$), obtained in the previous sub-module (Algorithm 2), we do
clustering using K-Means. We start the algorithm with $K=1$ and number of new
classes, ${N}_{new}$ = 0. We perform - (i) K-Means clustering. (ii) Annotate
$x$ points from each cluster, add those points to $\mathcal{L}$ and identify
$n^{\prime}$ new classes. (iii) Increase new class count (${N}_{new}$\+
$n^{\prime}$). (iv) Double the number of cluster count (we compare ${N}_{new}$
with $K/2$). We execute the above steps until cluster count exceeds the new
intent count. The algorithm returns current annotations ($\mathcal{L}$), newly
discovered class count (${N}_{new}$) and newly formed clusters
($\mathcal{CL}$). The budget spent in this step is $B_{1}$.

Stage 2. Cluster Quality Based Annotation (CQBA): In this step (Algorithm 4),
we evaluate the quality of each of the clusters obtained by the previous
algorithm. We annotate $p$ points from each of these clusters and if all the
$p$ points belong to the same class, we term it as a good cluster or else a
bad cluster. An example of a bad cluster in BANKING would be the one
containing data points from multiple classes, which may have high similarity,
such as: declined_cash_withdrawal and pending_cash_withdrawal. For the bad
clusters, we annotate $q$ more points. All these annotated points are then
added to the labelled data, $\mathcal{L}$. The budget spent in this step is
$B_{2}$. Hence the remaining budget $B$ \- ($B_{1}$ \+ $B_{2}$) is used in the
next step.
Stage 3. Post Processing Annotation Strategy (PPAS): In this step (Algorithm
5), we add more data to the labelled set, $\mathcal{L}$, through gold
annotation (gold strategy), as well as silver-annotated data (silver
strategy). To select these data points, we first train a classifier
($\mathcal{M}$) with the labelled set, $\mathcal{L}$ as obtained in the last
step (CBQA), and consider the clusters $\mathcal{CL}$. We predict on the
remaining points of the clusters to get the confidence of the datapoints. We
perform silver strategy based on confidence score (CS) and gold strategy in
round-robin way to operate on each cluster one after another.
Gold Strategy: Least confident data-points are annotated from the bad clusters
(if present) or else from the good clusters. Gold strategy is performed in a
round-robin way to retrieve data points with the least score for each cluster
until our budget exhausts.
Silver strategy: If the confidence score (CS) of a datapoint from a cluster is
greater than a predefined threshold ($\mathcal{TH}$), we measure the average
cosine similarity of points annotated within that cluster with this point. If
similarity is above a predefined threshold ($\mathcal{\tau}$), we label this
point with class label of that cluster. The predefined threshold
($\mathcal{\tau}$) is required to choose good samples selectively instead of
choosing all the points. Silver strategy does not require human intervention
therefore there is no extra addition to the annotation cost, but the multiple
conditions are checked to prevent noise in the training set.

Final Step: We again train the neural model $\mathcal{M}$ on $\mathcal{L}$ and
test on $\mathcal{T}$ to find out Accuracy and F1.

##  4 Dataset and Pre-Processing

We perform our experiments on a variety of datasets, which are widely used as
benchmarks for Natural Language Understanding tasks. The datasets are SNIPS
Coucke et al. (2018), ATIS Tur et al. (2010), HWU Liu et al. (2019a), BANKING
Casanueva et al. (2020) and CLINC Larson et al. (2019). SNIPS (7) and ATIS
(21) are smaller datasets consisting of less number of intents (in bracket)
where HWU (64), BANKING (77) and CLINC (150) are larger datasets with many
intents. ATIS is the most imbalanced, skewed dataset. In BANKING data -
several intents are highly similar among themselves. The detailed statistics
of these datasets including our experimental framework are shown in Table 1.
Since the datasets are already fully labelled, annotation essentially means
utilizing the already available labels. Hence, we do not have to deal with
usual issues of annotation accuracy, inter-annotator agreement, etc.

Dataset ($W$) # Intent Class ($|N|$) Dataset Size ($|W|$) #Labelled
|$D_{init}$| #Unlab ($|D|$ \- |$D_{init}$|) #Test ($|T|$)) #IND #OOD #Total
SNIPS 7 (5+2) 14484 50 8601 3449 12050 2384 ATIS 21 (13+8) 5871 130 3155 1586
4741 1000 HWU* 64 (10+54) 11036 100 1408 8452 9860 1076 BANKING* 77 (10+67)
13083 100 1026 8877 9903 3080 CLINC* 150 (10+140) 22500 100 1100 16800 17900
4500

Table 1: Statistics based on our split for five Datasets.
* represents pre-defined train-test splits. In # Intent Class, (- + -) represents (known + unknown) intents

### Data Pre-Processing

Dataset DOC MSP LMCL FS-OOD A F1 A F1 A F1 A F1 SNIPS 77.3 72.1 78.2 71.7 74.7
69.3 76.8 72.9 ATIS 55.8 47.2 56.1 44.7 54.5 40.6 74.9 68.6 HWU 61.4 57.2 59.9
29.9 53.1 44.3 68.2 64.1 BANKING 56.3 20.4 52.5 20.2 52.9 51.3 73.7 64.1 CLINC
54.8 18.7 53.4 20.5 54.1 59.9 77.7 65.7

Table 2: Accuracy (A) and F1-Score in (%) of various OODD algorithms to detect
OOD points from different datasets. Bold denotes the best for each dataset.

In the pre-processing step, we filter the out-of-domain samples. We consider
four algorithms for detecting out-of-domain samples. i) Softmax Prediction
Probability (MSP) Hendrycks and Gimpel (2018) predicts out-of-domain samples
based on a threshold on the softmax prediction scores. ii) Deep Open
Classification (DOC) Shu et al. (2017) method builds a multi-class classifier
with one vs rest layer of sigmoids. iii) Large Margin Cosine Loss (LMCL) Lin
and Xu (2019) trains a network with margin loss and predictions are then fed
into an algorithm called Local Outlier Factor (LOF) for outlier detection. iv)
Few-shot OOD (FS-OOD) Tan et al. (2019) uses a ProtoTypical Network to detect
OOD examples and classifying in-domain examples with few-shot examples from
the in-domain class. We fine-tune BERT embeddings using all these out of
domain sample detection algorithms. We use bert-base-uncased for these
methods. We set the threshold for MSP as 0.5 as in Lin and Xu (2019), Xu et
al. (2020). The results of all these algorithms are shown in Table 2. FS-OOD
Tan et al. (2019) provides us the best accuracy and F1 for detecting OOD
samples ($\mathcal{OS}$). Only DOC performs better in case of SNIPS but
overall FS-OOD outperforms other approaches so we use FS-OOD produced out-of-
sample data.222FS-OOD: https://github.com/SLAD-ml/few-shot-ood and other OOD
models: https://huggingface.co

##  5 Experimental Setup

The efficacy of the algorithm needs to be tested on two aspects. (a). The
number of unknown intents identified. (b). The accuracy achieved when the data
is annotated by our algorithm, MNID. To test the accuracy, we use state-of-
the-art several classification algorithms used for intent detection.

Method IFSTC ($Gl_{F}$, $Rn_{F}$, MNID) PolyAI ($Gl_{F}$, $Rn_{F}$, MNID) BERT
($Gl_{F}$, $Rn_{F}$, MNID) RoBERTa ($Gl_{F}$, $Rn_{F}$, MNID) SNIPS A 85.4,
78.1, 84.7 93.2, 85.7, 95.1 92.7, 91.6, 93.3 94.9, 92.3, 95.3 F1 84.2, 79.4,
84.2 93.2, 84.3, 94.9 92.6, 91.9, 93.9 94.8, 91.9, 94.8 ATIS A 88.4, 70.1,
88.8 87.8, 71.8, 88.6 88.1, 70.2, 88.2 87.9, 70.8, 88.6 F1 87.3, 65.8, 87.8
84.3, 74.5, 87.0 86.3, 73.9, 86.9 84.6, 74.1, 85.1 HWU A 78.2, 72.4, 79.7
83.8, 75.2, 83.8 82.6, 73.6, 82.7 82.5, 75.3, 83.7 F1 76.4, 71.4, 78.4 83.7,
77.3, 84.2 81.7, 74.3, 82.4 81.3, 77.2, 82.4 BANKING A 78.3, 72.8, 79.0 84.2,
79.0, 84.7 80.1, 75.5, 82.8 83.4, 77.0, 84.5 F1 77.7, 74.1, 80.0 83.1, 79.0,
84.4 80.0, 76.4, 83.7 83.9, 78.7, 83.8 CLINC A 88.7, 77.1, 88.9 92.1*, 83.2,
94.9 90.8, 77.6, 91.4 91.3, 84.5, 92.3 F1 85.7, 76.4, 88.3 93.5, 83.7, 95.2
90.7, 78.8, 91.0 91.7, 85.3, 92.8

Table 3: Overall Accuracy (A) and Macro F1 in (%) across all datasets for
different scenarios - ideal ($Gl_{F}$), random ($Rn_{F}$) and MNID (The best
outcomes among three scenarios in Bold). *Casanueva et al. (2020) report
accuracy of 90.15 with OOS and 92.14 without OOS.

Different Neural Models: We explore different neural models to evaluate MNID
as discussed next:

1\. IFSTC Xia et al. (2021): This finetunes a trained model on few shot data
of new classes using an entailment and hybrid strategy. We use the hybrid
strategy (best performing in their case).

2\. PolyAI Casanueva et al. (2020): It performs intent classification task
based on dual sentence encoders - Universal Sentence Encoders (USE) Cer et al.
(2018) and ConveRT. Since authors have taken down the ConveRT model, we apply
USE only. 333We use author’s implementation of IFSTC (PyTorch) and re-
implement PolyAI (Tensorflow)

Along with the above two, we also consider other standard models, 3\. BERT
(‘bert-base-uncased’) Devlin et al. (2019) and 4\. RoBERTa (‘roberta-base-
uncased’) Liu et al. (2019b) for evaluation on these datasets. We finetune
these pre-trained language models for 15 epochs for the smaller datasets
(SNIPS, ATIS) 50 epochs for the larger datasets (HWU, BANKING, CLINC) and with
a learning rate of 2e-05 and Adam optimizer444We use https://huggingface.co/.
Early stopping was employed to stop training. For all methods, we provide the
same number of gold annotated data obtained using our pipeline and report its
performance.

Baselines: We compare the performance of our method using two annotation
techniques for choosing $B-\|D_{init}\|$ data points: 1) $Gl_{F}$: This is the
ideal scenario where we are given $F$ (=10) data points for each of the new
classes - GoldFew, abbreviated as ‘$Gl_{F}$’. 2) $Rn_{F}$ : Here, we randomly
choose $B-\|D_{init}\|$ data points from the unlabelled data - RandomFew,
abbreviated as ‘$Rn_{F}$’.

Clustering Algorithms: One of the building blocks of MNID is to cluster
datapoints, so the efficacy of MNID depends on employing an efficient
clustering algorithm. We do a detailed study by employing several unsupervised
and semi-supervised clustering algorithm and choose the best.

The unsupervised algorithms are: (i) K-Means (KM) MacQueen et al. (1967) (ii)
Agglomerative Clustering (AG) Gowda and Krishna (1978) (iii) Deep Clustering
Network (DCN) Yang et al. (2017) and (iv) Deep Embedded Clustering (DEC) Xie
et al. (2016) which uses the stacked auto-encoder based reconstruction loss.
The semi-supervised algorithms are: (i) DeepAligned (DAL) Zhang et al. (2021)
which uses limited data for pre-training and cluster assignments as pseudo
labels for cluster refinement. (ii) DTC Han et al. (2019) develops on the DCN
algorithm by scaling it to the transfer learning setting and can estimate the
number of known classes in unlabelled data. It is however highly dependent on
availability of labelled data (iii) KCL Hsu et al. (2017) which transfers the
knowledge to target dataset considering KL-divergence based distance loss (iv)
MCL Hsu et al. (2019) which uses meta-classification based likelihood
criterion for pairwise similarity evaluation (v) CDAC+ Lin et al. (2020) which
uses prior data to refine the clustering process and KL-divergence based loss
555Code: https://github.com/thuiar/TEXTOIR .

Other than KM and AG, all the other unsupervised methods along with some of
the semi-supervised methods such as DTC and CDAC need the information of the
ground truth number of clusters for training and we provide them so (it is an
extra advantage for them). For semi-supervised methods such as KCL, MCL, DTC
and DAL, we start with double the number of ground truth clusters and let the
method determine the number of clusters.

Hyper-parameters and Settings: For Post-Processing annotation strategy of
MNID, we set the cosine similarity threshold, $\tau$ as 0.8 and the confidence
threshold, $\mathcal{TH}$ as 0.5 666This combination of $\tau$ and
$\mathcal{TH}$ provides the best results among different experimented
results.. For all datasets, we use a setting similar to $\kappa$-shot with
$\kappa$ = 10. For $N$ intents, we define our total budget $B=\kappa\times N$.
We use same budget for all our experiments. We experiment on NVIDIA Tesla K40m
GPU with 12 GB RAM, 6 Gbps clock cycle and GDDR5 memory. All the methods took
less than 8 GPU hours for training.

(a) HWU

(b) BANKING

(c) CLINC

Figure 2: Count of gold annotated points for newly discovered classes

##  6 Experimental Results

In this section, we discuss the experimental outcomes for MNID and competing
baselines. We also show results of different clustering algorithms and
variations of distinct components of MNID.

(A) Class Discovery: MNID is very effective in identifying almost all new
intents. For HWU, BANKING and CLINC, 54 out of 54 (100%), 66 out of 67 (98.5%)
and 139 out of 140 (99.3%) new intents from the unknown intent set were
discovered, respectively. For SNIPS and ATIS, we could discover 2 out of 2
(100%) and 7 out of 8 (87.5%) new intent classes, respectively. Due to data
skewness (ATIS) and high intent similarity (BANKING, CLINC) MNID misses one
intent. (B) Performance of MNID: Table 3 shows the performance of different
models - IFSTC, PolyAI, BERT and RoBERTa when trained with datasets provided
by MNID. In order to maintain the fairness, MNID, $Rn_{F}$ and $Gl_{F}$ use
the (overall) same number of gold-annotated data points. Besides MNID uses
silver-annotated data points, while the others do not have any way of creating
high quality silver annotated data. Each cell in the table consists of values
from $Gl_{F}$, $Rn_{F}$ and MNID. As expected, $Rn_{F}$ performs the worst
across all settings. However, except two scenarios, we observe that MNID
consistently performs better than the $Gl_{F}$ dataset. For all these four
different settings across five datasets, MNID improvements over $Gl_{F}$
predictions are statistically significant ($p<0.05$) as per McNemar’s Test. It
is observed that our approach also works well on the highly imbalanced ATIS
dataset in which some of the classes have less than 10 data points and highly
similar BANKING dataset in which the intents are closely related eg., ‘top-up-
reverted’ and ‘top-up-failed’. This is because although $Gl_{F}$ chooses
uniformly across all classes, MNID selectively labels datapoints having high
uncertainty thus providing the classifier with the right ingredient to perform
better. In IFSTC on SNIPS dataset, MNID underperforms as compared to $Gl_{F}$
but with a very small margin. This happens because in the case of SNIPS
dataset, the number of new classes is very less, hence $Gl_{F}$ can choose
ideal candidates. The best performance of MNID as well as the two baselines is
in the PolyAI setting when it is used with Universal Sentence Encoders (USE).
Since PolyAI performs the best, all our subsequent results are provided on
PolyAI (USE).

(C) Distribution of gold annotated points: Fig 2 shows the count of the gold
annotated points ($Y-axis$) for new classes (class indices on $X-axis$). The
dotted line is at the frequency of 10, corresponding to the average
annotations per class. For 76.2% (HWU), 81.5% (BANKING) and 67.3% (CLINC)
classes in good clusters require ‘$\leq 10$’ annotations. More than 10
annotations are needed for 65.4% (HWU), 68.5% (BANKING) and 54.5% (CLINC)
classes in bad clusters.

(D) Budgets: For novel intent class discovery, a minimum number of human
annotation is necessary. For NCD to work, at least 4 shot, 6-shot and 7-shot
annotations are required for HWU, BANKING and CLINC datasets respectively.

Dataset Unsupervised Clustering Algorithms Semi-Supervised Clustering
Algorithms KM AG DCN DEC DAL DTC KCL MCL CDAC+ A F1 A F1 A F1 A F1 A F1 A F1 A
F1 A F1 A F1 SNIPS 95.1 94.9 92.7 92.9 89.2 88.7 89.6 88.2 92.2 92.2 87.6 87.2
73.3 70.4 78.2 74.1 80.4 79.2 ATIS 88.6 87.0 85.8 86.4 77.7 79.78 83.1 85.42
86.9 87.0 84.3 85.9 76.7 80.8 80.4 83.2 77.9 81.6 HWU 83.8 84.2 83.2 83.3 84.1
83.6 84.7 84.4 83.7 82.6 83.6 85.2 73.3 74.1 78.1 74.8 83.1 81.1 BANKING 84.7
84.4 84.2 84.1 80.1 83.2 80.1 80.5 80.5 81.1 79.9 78.2 71.8 72.4 74.2 73.1
83.4 82.6 CLINC 94.9 95.2 93.9 94.8 93.4 94.2 93.4 94.9 93.9 92.6 93.9 93.2
83.4 84.5 81.0 82.3 92.1 92.5

Table 4: Accuracy (A) and F1-Score (F1) in (%) for various Open Intent
Discovery Based Clustering Algorithms across all datasets. The best results
for each dataset in Bold.

Method Silver Strategy Gold Strategy SNIPS ATIS HWU BANKING CLINC A F1 A F1 A
F1 A F1 A F1 MNID-1 Good Clusters$\dagger$ ✗ 94.4 93.2 87.2 85.4 78.5 78.8
77.5 78.4 89.2 89.8 MNID-2 Good Clusters$\dagger$ Any Point from Bad Clusters
94.4 93.2 87.2 85.4 80.9 80.9 79.3 80.0 90.8 90.7 MNID-3 ✗ Low-Conf from Any
Cluster 94.7 94.0 87.9 86.1 81.2 81.1 81.7 81.1 91.3 91.0 MNID-4 High-Conf
from Good Clusters ✗ 94.8 93.9 87.7 86.1 81.5 81.4 82.2 81.8 91.8 91.9 MNID-5
High-Conf from Good Clusters Low-Conf from Any Cluster 95.1 94.9 88.6 87.0
82.9 82.2 82.7 81.8 92.1 93.5 MNID-6 Good Clusters$\dagger$ Low-Conf from Bad
Clusters 94.4 93.2 87.2 85.4 83.1 82.8 83.9 83.1 93.9 93.7 MNID-7 ✗ Low-Conf
from Bad Clusters* 94.7 94.0 87.9 86.1 81.9 81.6 83.0 82.4 92.8 92.7 MNID-8
Good Clusters$\dagger$ Low-Conf from Bad Clusters* 94.9 94.4 88.2 86.4 83.1
82.8 83.9 83.1 93.9 93.7 MNID-9 High-Conf from Good Clusters Low-Conf from Bad
Clusters* 95.1 94.9 88.6 87.0 83.8 83.2 84.7 84.4 94.9 95.2

Table 5: Accuracy (A) and F1-score (F1) in (%) across all datasets for
different variations of silver and gold strategy of MNID. [* - If no bad
cluster exists then the strategy is applied on good clusters (SNIPS, ATIS have
no bad cluster). Detailed in line 6-11 of Algorithm 5. $\dagger$ We use
$\mathcal{TH}$ = 0 in Algorithm 5. ✗: denotes we are not using this. Bold
notifies the best for each dataset.]

## Different Variations of MNID

MNID consists of three steps (a). novel class detection (NCD), (b). cluster
quality based annotation (CQBA) and (c). post-processing annotation strategy
(PPAS). In each of these steps, certain parameters can be varied. We
systematically discuss the impact of these parameters on MNID performance.

### Variations at NCD

(a) Performance of Clustering Algorithms: We explore different unsupervised
and semi-supervised clustering algorithms in our MNID framework. Overall
accuracy and F1-Score for open intent discovery by different approaches are
shown in Table 4. From Table 4, it is seen that unsupervised approaches
perform better than semi-supervised models The semi-supervised techniques get
biased by the initial seed and fail to discover diverse clusters needed to
detect all the new intent classes. K-Means (KM) performs the best across all
datasets in terms of accuracy and F1 score except for HWU dataset where DEC
and DTC (F1 only) outperforms it. This is most probably due to its robustness
and absence of any outlier in the dataset. So we use K-Means as the clustering
algorithm for MNID.

(b) Class Discovery with number of clusters: From Fig 3(a), we observe an
increasing trend in the number of classes discovered with increasing number of
clusters which show that classes get evenly distributed across clusters as the
number of clusters increases. The rate at which new classes are discovered is
linear with the new clusters until significant classes are detected. The
horizontal lines represent the gold number of new intents.

p, q 2, 1 2, 2 2, 3 3, 0 3, 1 3, 2 4, 1 HWU 82.1 81.2 82.5 81.8 83.7 83.8 83.2
BANKING 84.1 83.0 84.2 82.9 84.0 84.7 84.1 CLINC 94.8 93.9 94.2 92.7 93.0 94.9
94.2

Table 6: Accuracy (%) based on point
selections from Good and Bad clusters

(c) Effect of number of points ($x$) used in clustering: Fig 3(b) shows that
the accuracy on all datasets drops as we increase the number of points used
for new class discovery in clustering beyond $x=2$. This is because most of
the budget gets exhausted while clustering and we have a very small budget to
annotate low-confidence points in the next steps. Note that at least two
points from a cluster need to be annotated for new class discovery.

(a) Class discovery with
number of clusters

(b) Accuracy vs points annotated ($x$) for clustering

Figure 3: Variations of NCD

### Variations at CQBA

(a) Effect of number of points selected from Good and Bad clusters: We
experiment with different values of point selection ($p,q$) for the module
CQBA (4) and observe how accuracy changes for three larger datasets - HWU,
BANKING and CLINC. We get the best accuracy for ($p,q$) = (3, 2) i.e 3($p$)
points from good cluster and 5($p+q$) points from bad cluster as shown in
Table 6. Since, we perform gold annotation strategy on the bad clusters, a
higher number of point selection is required to identify classes.

(b) Distribution of good and bad clusters: For CLINC, BANKING and HWU we
obtain 256, 128 and 64 clusters respectively by NCD. The percentage of good
clusters obtained for CLINC, BANKING and HWU are 70.70% (181 out of 256),
46.88% (60 out of 128) 56.25 % (36 out of 64), respectively. For BANKING,
since the entire dataset is from a single domain with multiple intents being
similar among themselves, we obtain more bad clusters than the good clusters.
For SNIPS and ATIS, however, all the clusters are good clusters.

### Variations at PPAS

(a) Different Variations of Gold and Silver Strategies: The results for
different variations of MNID methods (based on Silver and Gold Strategy
applications) for all the datasets are provided in Table 5. We observe that
the best result is obtained on MNID-9, i.e., choosing high confidence points
from the good clusters for silver strategy and low confidence points from the
bad clusters (if detected or else from the good clusters) only for gold
strategy. This strategy ensures that during silver annotation we choose points
with high fidelity and side by side for gold annotation choose points with
high uncertainty, both of which help in developing a highly accurate
classifier. Silver strategy on high confidence points from good cluster (7 vs
9) and gold strategy on low confidence points from bad cluster (4 vs 9) alone
enhances $\sim$1- 3% accuracy and F1 for the three large datasets.MNID-9
corresponds to our proposed approach, MNID.

Silver Strategy on SNIPS ATIS HWU BANKING CLINC All Clusters (%) 96.2 95.9
82.5 84.3 85.2 Good Clusters (%) 96.2 95.9 93.6 95.4 97.2 High-Conf from Good
Clusters (%) 97.8 96.2 95.6 97.2 98.1 Average Points per Class 10.1 8.2 17.0
22.8 15.9

Table 7: Accuracy (in %) and usage of average
number of datapoints per class in silver strategy

(b) Silver Strategy Analysis: We inspect silver strategy based on cosine
similarity, confidence score and strategy accuracy.

(i) Effect of Cosine Similarity and Confidence Score (CS): We study the effect
of cosine similarity of silver strategy for MNID. From Fig. 4(a), we observe
that the best results are always obtained using a higher threshold of 0.8
cosine similarity. In case of BANKING, HWU and ATIS accuracy drops at 0.9
whereas for other datasets it remains almost identical. Fig 4(b) shows how
accuracy varies for different confidence scores. We observe that for all the
datasets the best results are obtained at a threshold of 0.5. This is because
a lower threshold allows more diverse datapoints to be selected using cosine
similarity and this in turn improves the model performance. In both the cases
if the cosine similarity or the threshold is increased beyond the optimal
point, that results in selection of too less datapoints which is not enough
for the classifier to do a meaningful learning. Hence accuracy drops. So we
choose the parameters - cosine similarity = 0.8 and $\tau$ = 0.5 - while
choosing high confidence point to be annotated by silver strategy.

(ii) Strategy Accuracy: The accuracy of data point selection by silver
strategy for different MNID variations is shown in Table 7. We see the
strategy of choosing high-confidence points from good clusters produce points
with high fidelity. Table 7 also shows the average number of points per class
as selected by this strategy for various datasets. Here we see that enough
number of silver points are annotated even after considering a very strict
criterion. Note, count is the highest for BANKING because multiple intents are
very similar to each other and hence more points qualify the cosine similarity
threshold, $\tau$.

.

In Table LABEL:tab:fb_results, we show results on Facebook multilingual
datasets, ATIS and SNIPS (averaged results from Table
LABEL:tab:snips_results). In Table LABEL:tab:snips_results, we report
performance of our algorithm on the different types on SNIPS data. We observe
that in almost all the datasets, the KM labelling strategy outperforms others
in terms of overall accuracy and Macro-F1-score. We also observe that CL
performs significantly well on all the datasets and even out-performs KM in
SNIPS Type 2 setting as in Table LABEL:tab:snips_results. Thus, CL can be a
decent alternative to KM and may significantly reduce the overhead of deciding
the number of clusters. The MNID Random annotation (Rand Annot) baseline fails
to perform well on the datasets (Table LABEL:tab:snips_results) since the
random selection of samples leads to a uniform distribution of all the known
and unknown classes and a lower number of OOD samples are added back to
training.

[NG: A detailed discussion is needed]

Our method (MNID) consistently outperforms the other baseline by $\sim$ 10% in
terms of accuracy and $\sim$ 4-8% in terms of macro F1. Also, it can be
observed from Table LABEL:tab:snips_results, that all the baselines perform
well for Type 3 setting in the SNIPS dataset. The reason behind this would be
the high level of dissimilarity between the unknown intents with the known
intents which makes it easier to detect these classes. Despite of the fact
that the competing baselines have the added advantage of not having to
differentiate between the novel classes, we were still able to achieve higher
results on all the datasets.

(a) Cosine similarity
threshold ($\tau$)

(b) Confidence score
threshold ($\mathcal{TH}$)

Figure 4: Variations of PPAS

##  7 Conclusion

We have developed MNID (Multiple Novel Intent Detection), an end-to-end
framework to identify multiple novel intents within a fixed annotation cost.
The algorithm intelligently uses the concept of clusters to first discover the
classes and then estimate the nature in which datapoints of a class is
distributed, that is, whether the datapoints of a class congregate strongly
within themselves and separate from other classes or are entangled with
datapoints of other classes. In the two types of situations, we propose two
different strategies, silver strategy to take advantage of the clusters so
that we can annotate many points without any extra human cost and gold
strategy to annotate highly uncertain points. This two-pronged approach helps
us to annotate highly precise points automatically while annotating the most
uncertain (with respect to the class it belongs) points using human
assistance. We have done a very rigorous analysis/experimentation to establish
the core idea of our algorithm. We observe that the accuracy of classifiers
when fed with the dataset created by MNID can beat the standard best few-shot
setting where it is assumed that ‘$\kappa$’ instances of each class are
provided and annotated by human whereas in our case we have to first discover
the classes and then have to find the instances of each class.

One limitation of MNID is that it is not able to detect intents where classes
are very similar to each other. For example, the query “Can you explain why my
payment is still pending?” in BANKING dataset is from the “pending transfer”
category but our system detects as “pending card payment” intent as both
intents are quite similar. We shall try to address this issue in future. We
have presently worked on a setting where novel intents appear in one step, we
would strive to extend this framework to explore the dynamics of periodically
evolving intents.

## References

  * Casanueva et al. (2020) Inigo Casanueva, Tadas Temčinas, Daniela Gerz, Matthew Henderson, and Ivan Vulić. 2020.  Efficient intent detection with dual sentence encoders.  _arXiv preprint arXiv:2003.04807_.
  * Cer et al. (2018) Daniel Cer, Yinfei Yang, Sheng-yi Kong, Nan Hua, Nicole Limtiaco, Rhomni St John, Noah Constant, Mario Guajardo-Céspedes, Steve Yuan, Chris Tar, et al. 2018.  Universal sentence encoder.  _arXiv preprint arXiv:1803.11175_.
  * Coucke et al. (2018) Alice Coucke, Alaa Saade, Adrien Ball, Théodore Bluche, Alexandre Caulier, David Leroy, Clément Doumouro, Thibault Gisselbrecht, Francesco Caltagirone, Thibaut Lavril, Maël Primet, and Joseph Dureau. 2018.  Snips voice platform: an embedded spoken language understanding system for private-by-design voice interfaces.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.
  * Gowda and Krishna (1978) K Chidananda Gowda and G Krishna. 1978.  Agglomerative clustering using the concept of mutual nearest neighbourhood.  _Pattern recognition_ , 10(2):105–112.
  * Halder et al. (2020) Kishaloy Halder, Alan Akbik, Josip Krapac, and Roland Vollgraf. 2020.  Task-aware representation of sentences for generic text classification.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 3202–3213.
  * Han et al. (2019) Kai Han, Andrea Vedaldi, and Andrew Zisserman. 2019.  Learning to discover novel visual categories via deep transfer clustering.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 8401–8409.
  * Haque et al. (2016) Ahsanul Haque, Latifur Khan, and Michael Baron. 2016.  Sand: Semi-supervised adaptive novel class detection and classification over data stream.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 30.
  * Hendrycks and Gimpel (2018) Dan Hendrycks and Kevin Gimpel. 2018.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.
  * Hsu et al. (2017) Yen-Chang Hsu, Zhaoyang Lv, and Zsolt Kira. 2017.  Learning to cluster in order to transfer across domains and tasks.  _arXiv preprint arXiv:1711.10125_.
  * Hsu et al. (2019) Yen-Chang Hsu, Zhaoyang Lv, Joel Schlosser, Phillip Odom, and Zsolt Kira. 2019.  Multi-class classification without multi-class labels.  _arXiv preprint arXiv:1901.00544_.
  * Kuzborskij et al. (2013) Ilja Kuzborskij, Francesco Orabona, and Barbara Caputo. 2013.  From n to n+ 1: Multiclass transfer incremental learning.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 3358–3365.
  * Larson et al. (2019) Stefan Larson, Anish Mahendran, Joseph J Peper, Christopher Clarke, Andrew Lee, Parker Hill, Jonathan K Kummerfeld, Kevin Leach, Michael A Laurenzano, Lingjia Tang, et al. 2019.  An evaluation dataset for intent classification and out-of-scope prediction.  _arXiv preprint arXiv:1909.02027_.
  * Lin and Xu (2019) Ting-En Lin and Hua Xu. 2019.  Deep unknown intent detection with margin loss.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 5491–5496.
  * Lin et al. (2020) Ting-En Lin, Hua Xu, and Hanlei Zhang. 2020.  Discovering new intents via constrained deep adaptive clustering with cluster refinement.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 8360–8367.
  * Liu et al. (2019a) Xingkun Liu, Arash Eshghi, Pawel Swietojanski, and Verena Rieser. 2019a.  Benchmarking natural language understanding services for building conversational agents.
  * Liu et al. (2019b) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, M. Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019b.  Roberta: A robustly optimized bert pretraining approach.  _ArXiv_ , abs/1907.11692.
  * MacQueen et al. (1967) James MacQueen et al. 1967.  Some methods for classification and analysis of multivariate observations.  In _Proceedings of the fifth Berkeley symposium on mathematical statistics and probability_ , volume 1, pages 281–297. Oakland, CA, USA.
  * Masud et al. (2010) Mohammad Masud, Jing Gao, Latifur Khan, Jiawei Han, and Bhavani M Thuraisingham. 2010.  Classification and novel class detection in concept-drifting data streams under time constraints.  _IEEE Transactions on Knowledge and Data Engineering_ , 23(6):859–874.
  * Mu et al. (2017a) Xin Mu, Kai Ming Ting, and Zhi-Hua Zhou. 2017a.  Classification under streaming emerging new classes: A solution using completely-random trees.  _IEEE Transactions on Knowledge and Data Engineering_ , 29(8):1605–1618.
  * Mu et al. (2017b) Xin Mu, Feida Zhu, Juan Du, Ee-Peng Lim, and Zhi-Hua Zhou. 2017b.  Streaming classification with emerging new class by class matrix sketching.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 31.
  * Scheirer et al. (2012) Walter J Scheirer, Anderson de Rezende Rocha, Archana Sapkota, and Terrance E Boult. 2012.  Toward open set recognition.  _IEEE transactions on pattern analysis and machine intelligence_ , 35(7):1757–1772.
  * Shu et al. (2017) Lei Shu, Hu Xu, and Bing Liu. 2017.  Doc: Deep open classification of text documents.
  * Siddique et al. (2021) AB Siddique, Fuad Jamour, Luxun Xu, and Vagelis Hristidis. 2021.  Generalized zero-shot intent detection via commonsense knowledge.  In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 1925–1929.
  * Sun et al. (2016) Yu Sun, Ke Tang, Leandro L Minku, Shuo Wang, and Xin Yao. 2016.  Online ensemble learning of data streams with gradually evolved classes.  _IEEE Transactions on Knowledge and Data Engineering_ , 28(6):1532–1545.
  * Tan et al. (2019) Ming Tan, Yang Yu, Haoyu Wang, Dakuo Wang, Saloni Potdar, Shiyu Chang, and Mo Yu. 2019.  Out-of-domain detection for low-resource text classification tasks.  _arXiv preprint arXiv:1909.05357_.
  * Tur et al. (2010) Gokhan Tur, Dilek Hakkani-Tür, and Larry Heck. 2010.  What is left to be understood in atis?  In _2010 IEEE Spoken Language Technology Workshop_ , pages 19–24. IEEE.
  * Wang et al. (2020) Min Wang, Ke Fu, Fan Min, and Xiuyi Jia. 2020.  Active learning through label error statistical methods.  _Knowledge-Based Systems_ , 189:105140.
  * Xia et al. (2021) Congying Xia, Wenpeng Yin, Yihao Feng, and Philip Yu. 2021.  Incremental few-shot text classification with multi-round new classes: Formulation, dataset and system.  _arXiv preprint arXiv:2104.11882_.
  * Xia et al. (2018) Congying Xia, Chenwei Zhang, Xiaohui Yan, Yi Chang, and Philip S Yu. 2018.  Zero-shot user intent detection via capsule neural networks.  _arXiv preprint arXiv:1809.00385_.
  * Xie et al. (2016) Junyuan Xie, Ross Girshick, and Ali Farhadi. 2016.  Unsupervised deep embedding for clustering analysis.  In _International conference on machine learning_ , pages 478–487. PMLR.
  * Xu et al. (2020) Hong Xu, Keqing He, Yuanmeng Yan, Sihong Liu, Zijun Liu, and Weiran Xu. 2020.  A deep generative distance-based classifier for out-of-domain detection with mahalanobis space.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 1452–1460.
  * Yang et al. (2017) Bo Yang, Xiao Fu, Nicholas D Sidiropoulos, and Mingyi Hong. 2017.  Towards k-means-friendly spaces: Simultaneous deep learning and clustering.  In _international conference on machine learning_ , pages 3861–3870. PMLR.
  * Zhang et al. (2021) Hanlei Zhang, Hua Xu, Ting-En Lin, and Rui Lyu. 2021.  Discovering new intents with deep aligned clustering.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 14365–14373.
  * Zhou and Chen (2002) Zhi-Hua Zhou and Zhao-Qian Chen. 2002.  Hybrid decision tree.  _Knowledge-based systems_ , 15(8):515–528.


# Quantum Deletion Codes Derived From Quantum Reed-Solomon Codes

Manabu HAGIWARA  Department of Mathematics and Informatics, Graduate School of
Science, Chiba University 1-33 Yayoi-cho, Inage-ku, Chiba City, Chiba Pref.,
JAPAN, 263-0022. E-mail<EMAIL_ADDRESS>
(2023/06/22)

###### Abstract

This manuscript presents a construction method for quantum codes capable of
correcting multiple deletion errors. By introducing two new alogorithms, the
alternating sandwich mapping and the block error locator, the proposed method
reduces deletion error correction to erasure error correction. Unlike previous
quantum deletion error-correcting codes, our approach enables flexible code
rates and eliminates the requirement of knowing the number of deletions.

##  1 Introduction

This manuscript discusses the construction of quantum codes capable of
correcting quantum multiple deletion errors. Quantum error-correcting codes
have gained significant attention in the fields of quantum computing and
communication due to their essential role in error resilience [1, 2, 3]. In
order to improve error resilience in computation and communication, various
proposals have been developed for constructing quantum error-correcting codes,
primarily by applying classical bit-flip error-correcting codes to unitary
error correction [4, 5, 6].

Error-correction plays a crucial role in various applications in both
classical and quantum information domains [7, 8, 9, 10]. Recently, there has
been growing interest within classical coding theory regarding an error model
called deletion error [11, 12, 13]. Classical deletion error correction was
proposed in the 1960s. New applications were pointed out 50 years later. This
error model holds potential applications in error correction for DNA storage
[14] and racetrack memory [15, 16]. Additionally, current quantum
communication is susceptible to deletion errors caused by photon loss during
transmission [17, 18]. Therefore, the development of quantum deletion error-
correcting codes may be crucial for both present and future applications in
quantum communication.

In 2020, Nakayama discovered a specific example of a quantum error-correcting
code capable of correcting quantum single deletion errors [19]. Since then,
several papers have been published that provide construction methods for
quantum deletion error-correcting codes [20, 21, 22, 23, 24, 25, 26]. However,
there are some issues that need to be addressed. Firstly, there is a lack of a
method that utilizes previously known coding theory in the construction of
quantum deletion codes. Their methods for quantum deletion code construction
are based on combinatorial or type theory/permutation invariance. Secondly,
the code rate of currently known quantum deletion error-correcting codes is
limited and small. It is desirable to have various choices for the code rate
and achieve a high code rate. Thirdly, the decoders require the information of
the number of quantum systems for received quantum states. For example, if no
deletion error happens, the decoder does not change the received quantum
state. On the other hand, if deletion error happens, the decoder performs
error-correction to the state. It means that the decoder requires a photon
counter that does not change quantum states. Lastly, the currently known
quantum deletion codes handle mainly single error-correction.

This manuscript presents a construction method for quantum deletion error-
correcting codes by leveraging quantum Reed-Solomon codes. The resulting code
is capable of multiple deletion errors. The proposed construction can achieve
any desired code rate under a fixed number of multi-deletions. It should be
noted that the constructed quantum deletion error-correcting codes have a
small relative distance, where the relative distance is the ratio of the
minimum distance to the code length. This small relative distance arises due
to the necessity of handling codes with large lengths while the maximum number
of correctable deletion errors is fixed. Constructing codes with larger
relative distances remains a future challenge. Our decoder does not require a
photon counter for received states under the assumption where the number of
deletions is less than or equal to the previously fixed maximum number of
deletions.

##  2 Preliminaries

This paper assumes the fundamental knowledge of quantum information theory and
classical/quantum Reed-Solomon codes, particularly described in Sections 2.1
and 2.2.

Throughout this paper, $n,t,E,K_{C},K_{D}$ and $N$ denote positive integers.
$[n]$ denotes a set of $n$-integers $\\{1,2,\ldots,n\\}$. For $0\leq t\leq n$,
$\binom{[n]}{t}$ denotes the set of vectors $(i_{1},i_{2},\dots,i_{t})$ such
that $1\leq i_{1}<i_{2}<\dots<i_{t}\leq n$. For a set $X$, $\\#X$ denotes the
cardinality of $X$.

For a positive integer $E$, $\mathbb{F}_{2^{E}}$ denotes a field of size
$2^{E}$ which is an extended field of the binary field
$\mathbb{F}_{2}=\\{0,1\\}$, and thus an element of $\mathbb{F}_{2^{E}}$ can be
represented as an $E$-bit sequence.

$\bm{0}^{(t)}$ represents the $t$-repetition of the bit $0$, i.e., $00\dots
0\in\\{0,1\\}^{t}$, and $\bm{1}^{(t)}$ represents the $t$-repetition of the
bit $1$, i.e., $11\dots 1\in\\{0,1\\}^{t}$.

###  2.1 Fundamentals of Quantum Information Theory

For a square matrix $\tau$ over a complex field $\mathbb{C}$,
$\mathrm{Tr}(\tau)$ denotes the sum of the diagonal elements of $\tau$. Define
$\ket{0},\ket{1}\in\mathbb{C}^{2}$ as $\ket{0}:=(1,0)^{T},\ket{1}:=(0,1)^{T}$,
and $\ket{\bm{x}}$ as
$\ket{\bm{x}}:=\ket{x_{1}}\otimes\ket{x_{2}}\otimes\cdots\otimes\ket{x_{n}}\in\mathbb{C}^{2\otimes
n}$ for a bit sequence $\bm{x}=x_{1}x_{2}\cdots x_{n}\in\\{0,1\\}^{n}$. Here
$\otimes$ is the tensor product operation, $T$ is the transpose operation, and
$\mathbb{C}^{2\otimes n}$ is the $n$th tensor product of $\mathbb{C}^{2}$,
i.e., $\mathbb{C}^{2\otimes n}:=(\mathbb{C}^{2})^{\otimes n}$. We may identify
$\mathbb{C}^{2\otimes n}$ with $\mathbb{C}^{2^{n}}$ as a complex vector space.
We denote by $S(\mathbb{C}^{2\otimes n})$ the set of all density matrices of
order $2^{n}$. A density matrix is employed to represent a quantum state. The
quantum state $\tau$ that relates to $n$ qubits is represented in an element
of $S(\mathbb{C}^{2\otimes n})$. Any state $\tau$ is represented in the
following form:

$\displaystyle\tau=\sum_{\bm{x},\bm{y}\in\\{0,1\\}^{n}}\tau_{\bm{x},\bm{y}}\ket{x_{1}}\bra{y_{1}}\otimes\cdots\otimes\ket{x_{n}}\bra{y_{n}},$
(1)

where $\tau_{\bm{x},\bm{y}}\in\mathbb{C}$ and $\bra{a}:=\ket{a}^{\dagger}$,
i.e. $\bra{a}$ is the conjugate transpose of $\ket{a}$. The quantum state of a
subsystem that relates to $(n-1)$ qubits is described by the partial trace
defined below.

######  Definition 1 (Partial Trace, $\mathrm{Tr}_{i}$).

Let $i\in[n]$. Define a function $\mathrm{Tr}_{i}:S(\mathbb{C}^{2\otimes
n})\rightarrow S(\mathbb{C}^{2\otimes(n-1)})$ as

$\displaystyle\mathrm{Tr}_{i}(\tau)$ $\displaystyle:=$
$\displaystyle\sum_{\bm{x},\bm{y}\in\\{0,1\\}^{n}}\tau_{\bm{x},\bm{y}}\cdot\mathrm{Tr}(\ket{x_{i}}\bra{y_{i}})\ket{x_{1}}\bra{y_{1}}\otimes$
$\displaystyle\cdots\otimes\ket{x_{i-1}}\bra{y_{i-1}}\otimes\ket{x_{i+1}}\bra{y_{i+1}}\otimes$
$\displaystyle\cdots\otimes\ket{x_{n}}\bra{y_{n}},$

where

$\displaystyle\tau=\sum_{\bm{x},\bm{y}\in\\{0,1\\}^{n}}\rho_{\bm{x},\bm{y}}\ket{x_{1}}\bra{y_{1}}\otimes\cdots\otimes\ket{x_{n}}\bra{y_{n}}$
(2)

and $\mathrm{Tr}(\ket{x_{i}}\bra{y_{i}})$ is $1$ if $x_{i}=y_{i}$, otherwize
$0$. The map $\mathrm{Tr}_{i}$ is called the partial trace.

###  2.2 Classical/Quantum Reed-Solomon Codes

Reed-Solomon codes are a class of classical error-correcting codes. It is
known that every Reed-Solomon code is an MDS code, in other words, $N-K=d+1$
holds, where $N$ is the code length, $K$ is the dimension, and $d$ is the
minimum Hamming distance.

Here we recall an instance of Reed-Solomon code construction. Assume that
$t,E,K_{C},K_{D},$ and $N$ satisfy $t\leq K_{C}\leq N-t$, $N-K_{C}\leq K_{D}$,
and $N\leq 2^{E}-1$. Let $\alpha$ be a primitive element of
$\mathbb{F}_{2^{E}}$. Define the $K_{D}$-by-$N$ matrix
$H_{D^{\perp}}:=(h_{i,j})_{1\leq i\leq K_{D},1\leq j\leq N}$ as follows:

$\displaystyle h_{i,j}:=\alpha^{(i-1)(j-1)}.$ (3)

Then $D^{\perp}$ is defined as a linear code over $\mathbb{F}_{2^{E}}$ with
parity-check matrix $H_{D^{\perp}}$, which is a (shortened) Reed-Solomon code
over $\mathbb{F}_{2^{E}}$. In other words,

$\displaystyle D^{\perp}=\\{\mathbf{x}\in(\mathbb{F}_{2^{E}})^{N}\mid
H_{D^{\perp}}\mathbf{x}^{T}=(\mathbf{0}^{(K_{D})})^{T}\\}.$ (4)

The dimension of $D^{\perp}$ is $N-K_{D}$. Next, we define the
$(N-K_{C})$-by-$N$ matrix $H_{C}:=(h_{i,j})_{1\leq i\leq N-K_{C},1\leq j\leq
N}$ as a submatrix of $H_{C}$. We define $C$ as a linear code over
$\mathbb{F}_{2^{E}}$ with its parity-check matrix $H_{C}$, which is also a
(shortened) Reed-Solomon code. The dimension of $C$ is $K_{C}$ The minimum
Hamming distance of $C$ over $\mathbb{F}_{2^{E}}$ of $C$ is $N-K_{C}+1$, which
is greater than $t$ because $K_{C}\leq N-t$. Therefore, $C$ is a classical
$t$-erasure error-correcting code over $\mathbb{F}_{2^{E}}$. Since $H_{C}$ is
a submatrix of $H_{D^{\perp}}$, $C$ includes $D^{\perp}$, i.e.
$D^{\perp}\subset C$.

Recall that a quantum Reed-Solomon code $\mathcal{R}$ is a non-binary CSS code
constructed from a pair of classical Reed-Solomon codes $C$ and $D^{\perp}$
that have the same code length, say $N$, and satisfy $D^{\perp}\subset C$. The
quantum code $\mathcal{R}$ is realized as a state of $N$ quantum systems of
level $2^{E}$, i.e., $\mathcal{R}\subset S(\mathbb{C}^{2^{E}\otimes N})$. The
code length of $\mathcal{R}$ of level $2^{E}$ is said to be $N$. The complex
dimension of $\mathcal{R}$ is

$\displaystyle 2^{E(K_{C}+K_{D}-N)}.$ (5)

The quantum minimum distance $d_{\mathcal{R}}$ of level $2^{E}$ is lower
bounded by both the minimum Hamming distance $d_{C}$ of $C$ and the minimum
Hamming distance $d_{D}$ of the dual code of $D^{\perp}$, i.e.,

$\displaystyle
d_{\mathcal{R}}\geq\min\\{d_{C},d_{D}\\}=\min\\{N-K_{C}+1,N-K_{D}+1\\}$ (6)

since $d_{C}=N-K_{C}+1$ and $d_{D}=N-K_{D}+1$.

It means that the quantum Reed-Solomon code $\mathcal{R}$ is capable of
quantum $d_{\mathcal{R}}-1$ or less erasure error, where a quantum
$t^{\prime}$-erasure error is a quantum error $\mathcal{E}_{\bm{i}}$ that
transforms states of $t^{\prime}$ quantum systems of level $2^{E}$ and
announces the $t^{\prime}$-error position $\bm{i}\in\binom{[N]}{t^{\prime}}$.
A decoder for a quantum Reed-Solomon code utilize both the received state and
the error position information $\bm{i}$. Denoting the encoder by
$\mathrm{Enc}_{\mathcal{R}}$, the decoder by $\mathrm{Dec}_{\mathcal{R}}$, and
erasure error operation by $\mathcal{E}_{\bm{i}}$ at position $\bm{i}$, we
have

$\displaystyle\mathrm{Dec}_{\mathcal{R}}\left(\bm{i},\mathcal{E}_{\bm{i}}\circ\mathrm{Enc}_{\mathcal{R}}(\sigma)\right)=\sigma$
(7)

for any $\sigma\in S(\mathbb{C}^{2^{E}\otimes(K_{C}+K_{D}-N)})$ and any
$\bm{i}\in\binom{[N]}{t^{\prime}}$ with $0\leq t^{\prime}\leq
d_{\mathcal{R}}-1$.

Since $\mathbb{C}^{2^{E}\otimes N}$ is isomorphic to $\mathbb{C}^{2\otimes
NE}$ as a complex linear space, $\mathcal{R}$ is also realized as a set of
states of $NE$ quantum systems of level $2$, i.e., $\mathcal{R}\subset
S(\mathbb{C}^{2^{\otimes}NE})$. The codeword is realized by $NEN$ quantum
systems of level $2$, say $r_{1},r_{2},\dots,r_{NE}$. Let us devide the
quantum systems into $N$ blocks so that the $i$th block consists of $E$
quantum systems $r_{1+(i-1)E},r_{2+(i-1)E},\dots r_{E+(i-1)E}$. In this case,
$\mathrm{Dec}_{\mathcal{R}}$ is capable of $t$ or less block erasure. The
index $\bm{i}$ shows the block error positions.

######  Definition 2 (Code Rate).

Let $Q$ be a quantum code such that $Q$ is a subvector space of
$\mathbb{C}^{2\otimes n}$ as a complex vector space. If $Q$ is of dimension
$M$, the code rate of $Q$ is defined as $(\log_{2}M)/n$.

For example, the code rate of $\mathcal{R}$ is

$\displaystyle E(K_{C}+K_{D}-N)/n=(K_{C}+K_{D}-N)/N,$ (8)

by Eq.(5) and $n=NE$.

##  3 Quantum Deletion Error

This section provides definitions and observations on quantum deletion errors
from the perspective of changes in quantum states. In line with previous
studies (e.g., [19, 23, 22]), we define quantum deletion errors using partial
trace operations.

######  Definition 3 (Quantum Single/Multi Deletion Error $\mathcal{D}_{i}$,
$\mathcal{D}_{\mathbf{i}}$).

First, we define a quantum single deletion error as a mapping from a state
$\tau\in S(\mathbb{C}^{2\otimes n})$ to a state $\mathrm{Tr}_{i}(\tau)\in
S(\mathbb{C}^{2\otimes(n-1)})$, where $n$ and $i$ are positive integers with
$1\leq i\leq n$. We denote this error by $\mathcal{D}_{i}$.

A quantum multi deletion error is a composition of quantum single deletion
errors, represented as
$\mathcal{D}_{i_{1}}\circ\mathcal{D}_{i_{2}}\circ\dots\circ\mathcal{D}_{i_{t}}$,
for some $\mathbf{i}=(i_{1},i_{2},\dots,i_{t})\in\binom{[n]}{t}$. Here,
$\circ$ denotes the composition of mappings. We denote this error by
$\mathcal{D}_{\mathbf{i}}$.

We aim to observe quantum deletion errors using quantum systems. For each
$1\leq j\leq n$, let $p_{j}$ represent a physical system whose state can be
described as a two-level quantum state in $S(\mathbb{C}^{2})$. Examples of
physical systems include trapped ions, quantum dots, nitrogen-vacancy centers,
photons, and others. Their states are commonly referred to as qubits. The
state of $n$ systems, $p_{1},p_{2},\dots,p_{n}$, is represented as an element
of $S(\mathbb{C}^{2\otimes n})$, say $\tau$. If we fix $1\leq i\leq n$ and
focus on the remaining $n-1$ systems by excluding $p_{i}$, their state can be
described by $\mathrm{Tr}_{i}(\tau)$. As per the definition of deletion
errors, this state is represented as $\mathcal{D}_{i}(\tau)$. Similarly, for
$\mathbf{i}=(i_{1},i_{2},\dots,i_{t})\in\binom{[n]}{t}$, the resulting state
after a multi deletion error corresponds to the quantum state of the remaining
$n-t$ systems, represented as $D_{\mathbf{i}}(\tau)$. Therefore, deletion
errors can be interpreted as errors caused by excluding specific physical
systems. An example of excluding systems is loss of photons. The loss of
photons in quantum communication has been extensively studied [34, 36].
Quantum deletion errors serve as a model for errors caused by such losses.

Suppose that $p_{i}$ is excluded, and the state became
$\mathcal{D}_{i}(\tau)$. If we possess $p_{i}$, we can recover the quantum
state from $\mathcal{D}_{i}(\tau)$ to $\tau$ by inserting $p_{i}$ between
$p_{i-1}$ and $p_{i+1}$. This can be considered as a deletion error-
correction. Alternatively, let us introduce another system denoted as $q$, and
perform a state swap operation between $p_{i}$ and $q$. By inserting $q$
between $p_{i-1}$ and $p_{i+1}$, the systems are
$p_{1},p_{2},\dots,p_{i-1},q,p_{i+1},\dots,p_{n}$. Then we can also recover
the quantum state from $\mathcal{D}_{i}(\tau)$ to $\tau$. Although the systems
are different, the quantum state is the same as the original state $\tau$.
This can be also regarded as a deletion error-correction. It should be noted
that it is not generally assumed that the excluded system $p_{i}$ is retained.
Furthermore, knowledge of the exact error position $i$ should not be assumed.

##  4 Alternating Sandwich Mapping and Error Locator

This section proposes two algorithms, Alternating Sandwich Mapping
$\mathrm{Asm}$ and Error Locator $\mathrm{Loc}$. From here, the symbol
$\mathfrak{o}$ denotes a quantum system of level 2, corresponding to the
quantum state $\ket{0}\bra{0}$. Similarly, $\mathfrak{o}^{t}$ denotes
$t$-$\mathfrak{o}$s, i,e., $\mathfrak{o},\mathfrak{o},\dots,\mathfrak{o}$. In
this context, the $\mathfrak{o}^{t}$’s state can be written as
$\ket{\mathbf{0}^{(t)}}\bra{\mathbf{0}^{(t)}}\in S(\mathbb{C}^{2\otimes t})$,
where
$\ket{\mathbf{0}^{(t)}}:=\ket{0}\otimes\ket{0}\otimes\dots\otimes\ket{0}$.
Similarly, we use the symbol $\mathfrak{l}^{t}$ to denote a quantum system of
level $2^{t}$, whose quantum state is
$\ket{\mathbf{1}^{(t)}}\bra{\mathbf{1}^{(t)}}\in S(\mathbb{C}^{2\otimes t})$,
where
$\ket{\mathbf{1}^{(t)}}:=\ket{1}\otimes\ket{1}\otimes\dots\otimes\ket{1}$. The
notation $\mathfrak{l}^{t}$ is employed.

######  Definition 4 (Alternating Sandwich Mapping: $\mathrm{Asm}$).

The mapping defined by the following procedure is called the alternating
sandwich mapping, denoted as $\mathrm{Asm}$.

  1. Input

: A quantum state $\rho\in S(\mathbb{C}^{2\otimes NE})$, which is realized by
$NE$ quantum systems $r_{1},r_{2},\dots,r_{NE}$ of level 2.

  2. Output

: A quantum state $\tau\in S(\mathbb{C}^{2\otimes N(E+2t)})$.

  3. 1.

Divide the $NE$ quantum systems into $N$ blocks of $E$ systems each, denoted
as $R_{b}:=r_{1+(b-1)E},\dots,r_{E+(b-1)E}$ $(1\leq b\leq N)$. Append
$\mathfrak{o}^{t}\mathfrak{l}^{t}$ to the end of each block. Thus, we have
$N(E+2t)$ quantum systems: $R_{1},\mathfrak{o}^{t},\mathfrak{l}^{t}$,
$R_{2},\mathfrak{o}^{t},\mathfrak{l}^{t}$, $\dots$,
$R_{N},\mathfrak{o}^{t},\mathfrak{l}^{t}$.

  4. 2.

Output the state $\tau\in S(\mathbb{C}^{2\otimes N(E+2t)})$ of these $N(E+2t)$
quantum systems.

Figure 1: Reed-Solomon Encoder $\mathrm{Enc}_{R}$ and Alternating Sandwich
Mapping $\mathrm{Asm}$

Consider a case, in Definition 4, where $\rho$ is a pure state given by
$\rho=\ket{\phi}\bra{\phi}$ with a certain state

$\displaystyle\ket{\phi}=\sum_{\mathbf{c}\in(\mathbb{F}_{2^{E}})^{N}}\alpha_{\mathbf{c}}\ket{c_{1}}\ket{c_{2}}\dots\ket{c_{N}},$
(9)

where $\mathbf{c}=c_{1}c_{2}\dots c_{N}$. In this case,
$\tau:=\mathrm{Asm}(\rho)$ is also a pure state $\ket{\Phi}\bra{\Phi}$, and

$\displaystyle\ket{\Phi}=$
$\displaystyle\sum_{\mathbf{c}\in(\mathbb{F}_{2^{E}})^{N}}\alpha_{\mathbf{c}}\ket{c_{1}\mathbf{0}^{(t)}}\ket{\mathbf{1}^{(t)}c_{2}\mathbf{0}^{(t)}}\dots\ket{\mathbf{1}^{(t)}c_{N}\mathbf{0}^{(t)}}\ket{\mathbf{1}^{(t)}}.$

######  Lemma 5.

Let $n$, $t$, $t^{\prime}$, and $a$ be positive integers satisfying $1\leq
t^{\prime}\leq t\leq n$ and $a+2t\leq n$. Let $\tau\in S(\mathbb{C}^{2\otimes
n})$ be a state represented as

$\displaystyle\tau=\sum_{j}c_{j}\rho_{1,j}\otimes\rho_{2,j}\otimes\rho_{3,j}\otimes\rho_{4,j},$
(10)

where $c_{j}\in\mathbb{C}$, $\rho_{1,j}\in S(\mathbb{C}^{2\otimes a})$,
$\rho_{2,j}=\ket{\mathbf{0}^{(t)}}\bra{\mathbf{0}^{(t)}}$,
$\rho_{3,j}=\ket{\mathbf{1}^{(t)}}\bra{\mathbf{1}^{(t)}}$, and $\rho_{4,j}\in
S(\mathbb{C}^{2\otimes(n-a-2t)})$. Assume that $\tau$ is realized by $n$
quantum systems $q_{1},q_{2},\dots,q_{n}$.

After a $t^{\prime}$-deletion error occured in the $n$ quantum systems, the
number of deletions in the first $a+t$ quantum systems
$q_{1},q_{2},\dots,q_{a+t}$ is determined by the measurement in the
computational basis $\\{\ket{0},\ket{1}\\}$ to quantum systems at positions
$a+1$ through $a+t$. The number of deletions is equal to the Hamming weight of
the measurement outcomes.

###### Proof.

Let us denote the $t^{\prime}$-deletion error by
$\mathbf{i}=(i_{1},i_{2},\dots,i_{t^{\prime}})$. Define integers
$t_{1},t_{2},t_{3},t_{4}$ as follows:

$\displaystyle t_{1}$ $\displaystyle:=\\#\\{i_{j}\mid 1\leq j\leq
t^{\prime},1\leq i_{j}\leq a\\},$ $\displaystyle t_{2}$
$\displaystyle:=\\#\\{i_{j}\mid 1\leq j\leq t^{\prime},a+1\leq i_{j}\leq
a+t\\},$ $\displaystyle t_{3}$ $\displaystyle:=\\#\\{i_{j}\mid 1\leq j\leq
t^{\prime},a+t+1\leq i_{j}\leq a+2t\\},$ $\displaystyle t_{4}$
$\displaystyle:=\\#\\{i_{j}\mid 1\leq j\leq t^{\prime},a+2t+1\leq i_{j}\leq
n\\}.$

In other words, $t_{h}$ is the number of deletions occured in $\rho_{h,j}$ for
$1\leq h\leq 4$. We show that $t_{1}+t_{2}$ is equal to the Hamming weight of
the outcomes.

Divide $\mathbf{i}$ into four parts
$\mathbf{i}_{1},\mathbf{i}_{2},\mathbf{i}_{3},\mathbf{i}_{4}$, such that
$\mathbf{i}_{h}\in\binom{[n]}{t_{h}}$ and $\mathbf{i}_{h}$ is the indices of
deletion errors in $\rho_{h,j}$ for $1\leq h\leq 4$. Hence

$\displaystyle\mathcal{D}_{\mathbf{i}}=\mathcal{D}_{\mathbf{i}_{1}}\circ\mathcal{D}_{\mathbf{i}_{2}}\circ\mathcal{D}_{\mathbf{i}_{3}}\circ\mathcal{D}_{\mathbf{i}_{4}}.$
(11)

Therefore, we have

$\displaystyle\mathcal{D}_{\mathbf{i}}(\tau)$ $\displaystyle=$
$\displaystyle\mathcal{D}_{\mathbf{i}_{1}}\circ\mathcal{D}_{\mathbf{i}_{2}}\circ\mathcal{D}_{\mathbf{i}_{3}}\circ\mathcal{D}_{\mathbf{i}_{4}}(\tau)$
$\displaystyle=$
$\displaystyle\sum_{j}c_{j}\mathcal{D}_{\mathbf{i}_{1}}\circ\mathcal{D}_{\mathbf{i}_{2}}\circ\mathcal{D}_{\mathbf{i}_{3}}\circ\mathcal{D}_{\mathbf{i}_{4}}(\rho_{1,j}\otimes\rho_{2,j}\otimes\rho_{3,j}\otimes\rho_{4,j})$
$\displaystyle=$
$\displaystyle\sum_{j}c_{j}\mathcal{D}_{\mathbf{i}_{1}}\circ\mathcal{D}_{\mathbf{i}_{2}}\circ\mathcal{D}_{\mathbf{i}_{3}}(\rho_{1,j}\otimes\rho_{2,j}\otimes\rho_{3,j}\otimes\mathcal{D}_{\mathbf{i}_{4}}(\rho_{4,j}))$
$\displaystyle=$
$\displaystyle\sum_{j}c_{j}\mathcal{D}_{\mathbf{i}_{1}}\circ\mathcal{D}_{\mathbf{i}_{2}}(\rho_{1,j}\otimes\rho_{2,j}\otimes\ket{\mathbf{1}^{t-t_{3}}}\bra{\mathbf{1}^{t-t_{3}}}\otimes\mathcal{D}_{\mathbf{i}_{4}}(\rho_{4,j}))$
$\displaystyle=$
$\displaystyle\sum_{j}c_{j}\mathcal{D}_{\mathbf{i}_{1}}(\rho_{1,j}\otimes\ket{\mathbf{0}^{t-t_{2}}}\bra{\mathbf{0}^{t-t_{2}}}\otimes\ket{\mathbf{1}^{t-t_{3}}}\bra{\mathbf{1}^{t-t_{3}}}\otimes\mathcal{D}_{\mathbf{i}_{4}}(\rho_{4,j}))$
$\displaystyle=$
$\displaystyle\sum_{j}c_{j}\mathcal{D}_{\mathbf{i}_{1}}(\rho_{1,j})\otimes\ket{\mathbf{0}^{t-t_{2}}}\bra{\mathbf{0}^{t-t_{2}}}\otimes\ket{\mathbf{1}^{t-t_{3}}}\bra{\mathbf{1}^{t-t_{3}}}\otimes\mathcal{D}_{\mathbf{i}_{4}}(\rho_{4,j}).$

Note that
$\mathcal{D}_{\mathbf{i}_{1}}(\rho_{1,j})\in\mathbb{C}^{2\otimes(a-t_{1})},\ket{\mathbf{0}^{t-t_{2}}}\bra{\mathbf{0}^{t-t_{2}}}\in\mathbb{C}^{2\otimes(t-t_{2})}$
and
$\ket{\mathbf{1}^{t-t_{3}}}\bra{\mathbf{1}^{t-t_{3}}}\in\mathbb{C}^{2\otimes(t-t_{3})}$.
Meanwhile, we have

$\displaystyle a-t_{1}<a+1$ (12)

and

$\displaystyle a+t$ $\displaystyle\leq(a-t_{1})+(t-t_{2})+(t-t_{3})$ (13)
$\displaystyle=a+t+(t-t_{1}-t_{2}-t_{3}).$ (14)

Therefore, the state associated to the quantum systems from $(a+1)$th to
$(a+t)$th positions is
$\ket{\mathbf{0}^{t-(t_{1}+t_{2})}}\bra{\mathbf{0}^{t-(t_{1}+t_{2})}}\otimes\ket{\mathbf{1}^{(t_{1}+t_{2})}}\bra{\mathbf{1}^{(t_{1}+t_{2})}}$.
By the measurement in the computational basis, the outcomes are
$t-(t_{1}+t_{2})$ zeros and $t_{1}+t_{2}$ ones. In particular, the Hamming
weight is $t_{1}+t_{2}$. ∎

The lemma above motivates us to define the error locator algorithm below.
Recall that the alternating sandwich mapping inserts
$\ket{\mathbf{0}^{(t)}}\bra{\mathbf{0}^{(t)}}\otimes\ket{\mathbf{1}^{(t)}}\bra{\mathbf{1}^{(t)}}$
between consective blooks of Reed-Solomon codewords. Figure 2 helps to
illustrate how the algorithm determines the deletion error blocks.

######  Definition 6 (Block Error Locator: $\mathrm{Loc}$).

The mapping defined by the following procedure is called the block error
locator, denoted as $\mathrm{Loc}$.

Input:

  * •

A quantum state $\tau^{\prime}$ which is realized by quantum systems
$q_{1},q_{2},\dots,q_{n^{\prime}}$ of level 2, where $n^{\prime}\geq
N(E+2t)-t$.

Output:

  * •

$\bm{i^{\prime}}\in\bigcup_{0\leq t^{\prime}\leq t}\binom{[N]}{t^{\prime}}$
and a quantum state $\rho^{\prime}\in S(\mathbb{C}^{2\otimes NE})$, where
$\sigma^{\prime}$ represents a quantum state associated with $NE$ quantum
systems $y_{1},y_{2},\dots,y_{NE}$ of level 2.

  1. 1.

Initialization:

     * I-1

Initialize $\mathbf{i}^{\prime}:=\emptyset$ and $w_{0}:=0$.

     * I-2

Append $\mathfrak{l}^{t}$ to the tail of the input quantum systems
$q_{1},q_{2},\dots,q_{n^{\prime}}$, and $\mathbf{Y}$ denotes the systems.
Hence $\mathbf{Y}=q_{1},q_{2},\dots,q_{n^{\prime}}\mathfrak{l}^{t}$.

     * I-3

Rename the quantum systems of $\mathbf{Y}$ to $Y_{1},Y_{2},\dots$.

  2. 2.

Measurement:

     * M-1

For each $1\leq b\leq N$, measure each quantum system of the last $t$ quantum
systems $Y_{b(E+2t)-t+1},Y_{b(E+2t)-t+2},\dots,Y_{b(E+2t)}$ in the
computational basis $\\{\ket{0},\ket{1}\\}$.

     * M-2

Denote the outcome for $Y_{b(E+2t)-t+i}$ by $s_{b,i}\in\\{0,1\\}$. Regarding
the outcomes as a $t$-bit sequence $\mathbf{s}_{b}:=s_{b,1}s_{b,2}\dots
s_{b,t}\in\\{0,1\\}^{t}$.

  3. 3.

Error Detection:

     * E-1

For each $1\leq b\leq N$, calculate the Hamming weight of $\mathbf{s}_{b}$,
and denote it by $w_{b}$.

     * E-2

If $w_{b+1}=w_{b}$:

       * E-2-1

Define
$\mathbf{B}_{b}:=Y_{\beta_{b}+1},Y_{\beta_{b}+2},\dots,Y_{\beta_{b}+E}$, where
$\beta_{b}:=(b-1)(E+2t)+w_{b}+t$.

     * E-3

Otherwise, i.e., $w_{b+1}\neq w_{b}$:

       * E-3-1

Define $E$-quantum systems $\mathbf{B}_{b}$ as $\mathbf{o}^{E}$.

       * E-3-2

Update $\mathbf{i}^{\prime}:=\mathbf{i}^{\prime}\cup\\{b\\}$.

  4. 4.

Terminate:

     * T-1

Define a quantum state $\rho^{\prime}$ as the state for $EN$ quantum systems
$\mathbf{B}_{1},\mathbf{B}_{2},\dots,\mathbf{B}_{N}$.

     * T-2

Output $\mathbf{i}^{\prime}$ and $\rho^{\prime}$.

Figure 2: Deletion Error $\mathcal{D}_{\mathbf{i}}$ and Block Error Locator
$\mathrm{Loc}$: $1$ and $N$ belong to $\mathbf{i}$ but $2$ does not.

##  5 Quantum Multi Deletion Error-Correcting Codes from Quantum Reed-Solomon
Codes

######  Definition 7 ($\mathrm{Enc}$, $\mathrm{Dec}$, $\mathcal{Q}$).

Let $\mathrm{Enc}_{R}$ be the encoder of a quantum Reed-Solomon code, and
$\mathrm{Dec}_{R}$ the erasure error-correcting decoder for the quantum Reed-
Solomon code. Let $\mathrm{Asm}$ denote the Alternating Sandwich Mapping and
$\mathrm{Loc}$ the block error LOCator.

We define $\mathrm{Enc}$ and $\mathrm{Dec}$ as follows:

$\displaystyle\mathrm{Enc}$
$\displaystyle:=\mathrm{Asm}\circ\mathrm{Enc}_{R}.$ (15)
$\displaystyle\mathrm{Dec}$
$\displaystyle:=\mathrm{Dec}_{R}\circ\mathrm{Loc}.$ (16)

Under these conditions, we define our quantum code $\mathcal{Q}$ as follows:

$\displaystyle\mathcal{Q}$
$\displaystyle:=\mathrm{Enc}(S(\mathbb{C}^{2\otimes(K_{C}+K_{D}-N)E})).$ (17)

######  Theorem 8.

For any $\bm{i}\in\binom{[n]}{t}$ and any $\sigma\in S(\mathbb{C}^{2\otimes
NE})$, we have

$\displaystyle\mathrm{Dec}\circ\mathcal{D}_{\bm{i}}\circ\mathrm{Enc}(\sigma)=\sigma.$
(18)

Hence, $\mathcal{Q}$ is capable of correcting quantum $t$ or less deletion
error.

###### Proof.

By the definition of $\mathrm{Enc}$ and $\mathrm{Dec}$,

$\displaystyle\mathrm{Dec}\circ\mathcal{D}_{\bm{i}}\circ\mathrm{Enc}(\sigma)$
(19) $\displaystyle=$
$\displaystyle\mathrm{Dec}_{R}\circ\mathrm{Loc}\circ\mathcal{D}_{\bm{i}}\circ\mathrm{Asm}\circ\mathrm{Enc}_{R}(\sigma).$
(20)

Since $\mathrm{Enc}_{R}$ is the encoder of the quantum Reed-Solomon code,
$\mathrm{Enc}_{R}(\sigma)$ is a codeword. Let $r_{1},r_{2},\dots,r_{NE}$ be
quantum systems of level 2 such that their quantum state is
$\mathrm{Enc}_{R}(\sigma)$. Then the quantum system after $\mathrm{Asm}$
consists of $N$ blocks, and the $b$th block is

$\displaystyle
r_{1+(b-1)E},r_{2+(b-1)E},\dots,r_{E+(b-1)E},\mathfrak{o}^{t},\mathfrak{l}^{t},$
(21)

where $1\leq b\leq N$.

By Lemma 5, for $b>1$, the deletion error occured after $\mathfrak{o}^{t}$ at
$(b-1)$th block and before $\mathfrak{l}^{t}$ at $b$th block if and only if
$w_{b-1}=w_{b}$. Similarly, By Lemma 5, for $b=1$, the deletion error occured
among $r_{1},r_{2},\dots,r_{E},\mathfrak{o}^{t}$ if and only if
$w_{1}=w_{0}=0$. Hence the block positions of quantum deletions are determined
at the Error Detection step of the block error locator. Therefore, if we
denote the output of $\mathrm{Loc}$ as $(\mathbf{i}^{\prime},\rho^{\prime})$,
we have

$\displaystyle\rho^{\prime}=\mathcal{E}_{\mathbf{i}^{\prime}}\circ\mathrm{Enc}(\sigma).$
(22)

In particular, the quantum state of the error position block is
$\ket{\mathbf{0}^{(E)}}\bra{\mathbf{0}^{(E)}}$.

From the above, we have

$\displaystyle\mathrm{Dec}_{R}\circ\mathrm{Loc}\circ\mathcal{D}_{\bm{i}}\circ\mathrm{Asm}\circ\mathrm{Enc}_{R}(\sigma)$
(23) $\displaystyle=$
$\displaystyle\mathrm{Dec}_{R}(\mathbf{i}^{\prime},\rho^{\prime})$ (24)
$\displaystyle=$
$\displaystyle\mathrm{Dec}_{R}(\mathbf{i}^{\prime},\mathcal{E}_{\mathbf{i}^{\prime}}\circ\mathrm{Enc}(\sigma)).$
(25)

By Equantion (7), it is equal to $\sigma$. ∎

Since alternating sandwich mapping is a simple method, the author thought it
would not be surprising if there were previous studies in classical coding
theory. The author reviewed numerous papers on deletion codes, including
several survey papers (e.g., [27, 28]), but did not find any similar ideas.
The author also consulted researchers about deletion codes, but no one was
familiar with this idea. A related idea is that of a marker code, a deletion
error-correcting code constructed by inserting specific bit sequences [29].
The inserted bit sequences are different from those inserted by the
alternating sandwich mapping. Therefore, alternating sandwich mapping may
represent a new idea in coding theory, at least quantum coding theory. In
considering quantum insertion-deletion channels, Leahy mentioned the insertion
of classical bit strings [30]. The specific bit string used was $100\dots 0$,
where the string consists of consecutive zeros followed by a single one.
However, this method fails to correct errors if the leading $1$ is deleted.
Furthermore, Leahy did not employ non-binary quantum erasure-correcting codes
from Reed-Solomon codes.

Finally, we discuss the achievable code rate of the constructed codes. The
utilization of quantum Reed-Solomon codes enables our codes to achieve a
flexible code rate.

######  Theorem 9.

For any real number $0\leq\gamma\leq 1$, there exist quantum deletion error-
correcting codes, denoted as $\mathcal{Q}_{1},\mathcal{Q}_{2},\dots$, capable
of correcting $t$ or less deletion errors, such that their code rates converge
to $\gamma$, i.e., $\lim_{n\rightarrow\infty}\gamma_{n}=\gamma$, where
$\gamma_{n}$ represents the code rate of $\mathcal{Q}_{n}$.

###### Proof.

For each positive integer $E$ satisfying $2^{E}-1>2t$, choose Reed-Solomon
codes $C$ and $D^{\perp}$ with a length $N:=2^{E}-1$, such that $K_{D}:=N-t$
and $K_{C}:=\lfloor\gamma N\rfloor$, where $\lfloor a\rfloor$ is the largest
integer not exceeding $a$.

The dimension of $\mathcal{Q}_{E}$ is equal to that of $\mathcal{R}$.
Therefore, it is $2^{(K_{C}+K_{D}-N)E}=2^{(\lfloor\gamma N\rfloor-t)E}$. The
code length of $\mathcal{Q}_{E}$ is $N(E+2t)$. Hence, the code rate of
$\mathcal{Q}_{E}$ is

$\displaystyle\gamma_{\mathcal{Q}_{E}}=\frac{(\lfloor\gamma
N\rfloor-t)E}{N(E+2t)}.$ (26)

By the definition of $\lfloor\;\rfloor$,

$\displaystyle\frac{(\gamma
N-1-t)E}{N(E+2t)}\leq\gamma_{\mathcal{Q}_{E}}\leq\frac{(\gamma
N-t)E}{N(E+2t)}.$ (27)

Recall that $N$ is chosen as $2^{E}-1$. As $E$ approaches infinity, $N$ also
tends to infinity. Moreover, both sides of (27) converge to $\gamma$. Hence
$\gamma_{\mathcal{Q}_{E}}$ also converges to $\gamma$. ∎

##  6 Conclusion

This paper proposed a construction method for quantum deletion error-
correcting codes. The idea is to reduce the deletion error correction to the
erasure error correction of quantum Reed-Solomon codes by combining the
proposed alternating sandwich mapping and the proposed block error locator.
This approach allows us to leverage the properties of classical Reed-Solomon
codes, enabling flexible code rate design. Furthermore, while previous studies
implicitly assumed that the number of deletion errors is known for error
correction, our proposed decoder does not require such an assumption. However,
this study did not achieve an arbitrary relative distance. This remains a
topic for future research. What are the potential applications of quantum
deletion error-correcting codes? Quantum erasure error-correcting codes have
been applied in information security as components of quantum secret sharing
protocols. If a protocol based on quantum deletion error-correcting codes is
constructed, what advantages would it offer? Research on quantum deletion
error-correcting codes is still in its early stages. The author hopes that in
the future, new and efficient codes will be proposed, applications will be
discovered, and implementations will lead to the advancement of the theory.

## Acknowledgments

This paper is partially supported by KAKENHI 21H03393. We would like to
express our gratitude to J.B. Nation, Ellen Hughes from University of Hawai’i
at Manoa, and Justin Kong, Austin Anderson from Kapi’olani Community College
for providing valuable discussion opportunities.

## References

  * [1] D.P. DiVincenzo and P.W. Shor, “Fault-tolerant error correction with efficient quantum codes,” Phys. Rev. Lett., vol.77, no.15, p.3260, 1996.
  * [2] D. Gottesman, “An introduction to quantum error correction and fault-tolerant quantum computation,” Quantum information science and its contributions to Math., Proc. of Symposia in Applied Math., vol.68, pp.13–58, 2010.
  * [3] A. Ekert and C. Macchiavello, “Quantum error correction for communication,” Phys. Rev. Lett., vol.77, no.12, p.2585, 1996.
  * [4] A.R. Calderbank and P.W. Shor, “Good quantum error-correcting codes exist,” Phys. Rev. A, vol.54, no.2, pp.1098–1105, 1996.  doi: 10.1103/PhysRevA.54.1098.
  * [5] A. Steane, “Multiple-particle interference and quantum error correction,” Proc. R. Soc. Lond. A, vol.452, no.1954, pp.2551–2577, 1996.  doi: 10.1098/rspa.1996.0136.
  * [6] D.E. Gottesman, Stabilizer Codes and Quantum Error Correction, Ph.D. thesis, California Institute of Technology, 1997.
  * [7] H.C. Chang, C.B. Shung, and C.Y. Lee, “A reed-solomon product-code (rs-pc) decoder chip for dvd applications,” IEEE J. of Solid-State Circuits, vol.36, no.2, pp.229–238, 2001.
  * [8] S.L. Howard, C. Schlegel, K. Iniewski, and K. Iniewski, “Error control coding in low-power wireless sensor networks: When is ecc energy-efficient?,” EURASIP J. on Wireless Commun. and Networking, vol.2006, pp.1–14, 2006.
  * [9] A. Surekha, P.R. Anand, and I. Indu, “E-payment transactions using encrypted qr codes,” International J. of Applied Engineering Research, vol.10, no.77, pp.460–463, 2015.
  * [10] P.W. Shor and J. Preskill, “Simple proof of security of the BB84 quantum key distribution protocol,” Phys. Rev. Lett., vol.85, no.2, pp.441–444, 2000.  doi: 10.1103/PhysRevLett.85.441.
  * [11] A.A. Kulkarni and N. Kiyavash, “Nonasymptotic upper bounds for deletion correcting codes,” IEEE Trans. on Information Theory, vol.59, no.8, pp.5115–5130, 2013.
  * [12] A. Wachter-Zeh, “Limits to list decoding of insertions and deletions,” Proc. 2017 IEEE International Symposium on Information Theory (ISIT), pp.1948–1952, IEEE, 2017.
  * [13] C. Schoeny, A. Wachter-Zeh, R. Gabrys, and E. Yaakobi, “Codes correcting a burst of deletions or insertions,” IEEE Trans. on Information Theory, vol.63, no.4, pp.1971–1985, 2017.
  * [14] T. Buschmann and L.V. Bystrykh, “Levenshtein error-correcting barcodes for multiplexed dna sequencing,” BMC bioinformatics, vol.14, no.1, p.272, 2013.
  * [15] Y.M. Chee, H.M. Kiah, A. Vardy, E. Yaakobi, et al., “Coding for racetrack memories,” IEEE Trans. on Information Theory, vol.64, no.11, pp.7094–7112, 2018.
  * [16] G. Mappouras, A. Vahid, R. Calderbank, and D.J. Sorin, “Greenflag: Protecting 3d-racetrack memory from shift errors,” 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pp.1–12, IEEE, 2019.
  * [17] M. Bergmann and P. van Loock, “Quantum error correction against photon loss using multicomponent cat states,” Phys. Rev. A, vol.94, no.4, p.042332, 2016\.
  * [18] M. Bergmann and P. van Loock, “Quantum error correction against photon loss using noon states,” Phys. Rev. A, vol.94, no.1, p.012311, 2016.
  * [19] A. Nakayama and M. Hagiwara, “The first quantum error-correcting code for single deletion errors,” IEICE Commun. Express, p.2019XBL0154, 2020.
  * [20] M. Hagiwara and A. Nakayama, “A four-qubits code that is a quantum deletion error-correcting code with the optimal length,” Proc. 2020 IEEE International Symposium on Information Theory (ISIT), pp.1870–1874, IEEE, 2020\.
  * [21] A. Nakayama and M. Hagiwara, “Single quantum deletion error-correcting codes,” Proc. 2020 IEICE International Symposium on Information Theory and Its Applications (ISITA), pp.329–333, IEICE, 2020.
  * [22] T. Shibayama, “New instances of quantum error-correcting codes for single deletion errors,” Proc. 2020 IEICE International Symposium on Information Theory and Its Applications (ISITA), pp.334–338, IEICE, 2020.
  * [23] Y. Ouyang, “Permutation-invariant quantum coding for quantum deletion channels,” 2021 IEEE International Symposium on Information Theory (ISIT), pp.1499–1503, IEEE, 2021.
  * [24] T. Shibayama and M. Hagiwara, “Permutation-invariant quantum codes for deletion errors,” 2021 IEEE International Symposium on Information Theory (ISIT), pp.1493–1498, IEEE, 2021.
  * [25] R. Matsumoto and M. Hagiwara, “Constructions of l-adic t-deletion-correcting quantum codes,” IEICE Trans. on Fundamentals, vol.105, no.3, pp.571–575, 2022\.
  * [26] T. Shibayama and M. Hagiwara, “Equivalence of quantum single insertion and single deletion error-correctabilities, and construction of codes and decoders,” 2022 IEEE International Symposium on Information Theory (ISIT), pp.2970–2975, IEEE, 2022.
  * [27] M. Mitzenmacher, “A survey of results for deletion channels and related synchronization channels,” Algorithm Theory–SWAT 2008: 11th Scandinavian Workshop on Algorithm Theory, Gothenburg, Sweden, July 2-4, 2008. Proc. 11, pp.1–3, Springer, 2008.
  * [28] H. Mercier, V.K. Bhargava, and V. Tarokh, “A survey of error-correcting codes for channels with symbol synchronization errors,” IEEE Commun. Surveys & Tutorials, vol.12, no.1, pp.87–96, 2010.
  * [29] E.A. Ratzer, “Marker codes for channels with insertions and deletions,” Annales des télécommunications, vol.60, no.1-2, pp.29–44, 2005.
  * [30] J. Leahy, D. Touchette, and P. Yao, “Quantum insertion-deletion channels,” ArXiv, vol.abs/1901.00984, 2019.