# Frouros: A Python library for drift detection in machine learning systems

Jaime Céspedes Sisniega<EMAIL_ADDRESS>
Álvaro López García<EMAIL_ADDRESS>
Instituto de Física de Cantabria (IFCA), CSIC-UC, Spain

###### Abstract

`Frouros` is an open-source Python library capable of detecting drift in
machine learning systems. It provides a combination of classical and more
recent algorithms for drift detection: both concept and data drift. We have
designed it with the objective of making it compatible with any machine
learning framework and easily adaptable to real-world use cases. The library
is developed following a set of best development and continuous integration
practices to ensure ease of maintenance and extensibility. The source code is
available at https://github.com/IFCA/frouros.

Keywords: Machine learning, Drift detection, Concept drift, Data drift, Python

##  1 Introduction

When deploying machine learning models in real-world applications, there is
often the erroneous assumption that a given model will be used in a stationary
environment, assuming that the same concepts learned during the training phase
will remain valid at inference time (Gama et al., 2004), or that training
samples and production-time samples will come from the same distribution
(Ackerman et al., 2021). However, in real-world scenarios, this is often far
from being always true, and both situations may result in some type of drift
that can end up affecting the model performance (Žliobaitė et al., 2016).
Additionally, due to the high cost of collecting and labeling samples, this
performance loss can often not be confirmed in many real-world problems, and
other methods that only rely on distribution changes must be used.

In this paper, we present `Frouros`, an open-source Python library for drift
detection in machine learning systems. The library tries to fulfill two main
objectives:  1. to easily integrate into a machine learning system workflow
that uses any machine learning framework, thus making it framework-agnostic;
2. to unify in a single library the concept drift detection part
(traditionally researched and used for streaming/evolving data streams and
incremental learning as described by Khamassi et al., 2018) with the research
of change detection in the covariate distributions (also known as dataset
shift or distribution shift, related to the field of statistical two-sample
testing as introduced in Rabanser et al., 2019, and methods that measure the
distance between distributions as described by Goldenberg and Webb, 2019).

##  2 Drift detection

Traditionally there has been little consensus on the terminology and
definitions of the different types of drift, as stated by Moreno-Torres et al.
(2012). In order to adopt some clear definitions for the remainder of this
paper, we apply those used by Gama et al. (2014) for the concept drift part,
in combination with those used by Rabanser et al. (2019) work for detecting
dataset shift using only the covariates. Therefore, we set up the following
definitions assuming two different time points, ${t}$ and ${t+w}$, where $t$
could be any point in time, and $w$ could be the time at which the existence
of change is checked (Bayram et al., 2022). Thus, given $P(X,y)=P(y|X)P(X)$, a
change in the joint distribution between two different times that can result
in performance degradation can be described as $P_{t}(X,y)\neq P_{t+w}(X,y)$.
The types of changes that can lead to degradation of the model’s performance
are categorized as follows:

#### Concept drift.

There is a change in the conditional probability $P(y|X)$, with or without a
change in $P(X)$. Thus, it can be defined as $P_{t}(y|X)\neq P_{t+w}(y|X)$.
Also known as real concept drift (Gama et al., 2014).

#### Data drift.

There is a change in $P(X)$. Therefore, this type of drift only focuses in the
distribution of the covariates, $P(X)$, so $P_{t}(X)\neq P_{t+w}(X)$.
Hereafter, we rename dataset shift (Rabanser et al., 2019) to data drift, in
order to maintain consistency with the above definitions and with some of the
related software mentioned in Section 5 that also refer to it as data drift
(Van Looveren et al., 2019; Leigh et al., 2022). A variation of data drift can
be considered label drift, also known as prior probability shift (Storkey,
2009), where the change occurs in the label distribution $P(Y)$ instead of the
covariates $P(X)$. Thus, $P_{t}(Y)\neq P_{t+w}(Y)$.

##  3 Overview and design

The design and implementation of the library have been carried out with the
aim of making it compatible with any machine learning framework, thus making
it framework-agnostic. Detection methods are divided into the concept drift
and data drift categories, depending on the type of drift they can detect,
according to the definitions given in Section 2, and how they detect it. In
terms of implementation, both categories share an abstract class named
`BaseDetector` that contains the basic methods (reset) and attributes
(callbacks) that a detectors must implement. `Frouros` also implements the
well-known concept of callbacks, presented in some machine learning
frameworks, such as `Keras` (Chollet et al., 2015) and `PyTorch Lightning`
(Falcon and The PyTorch Lightning team, 2019). This allows users to execute
custom code at certain points. Additionally, we provide prequential error
metrics (Gama et al., 2013) to evaluate the performance of concept drift
methods described in Section 3.1.

###  3.1 Concept drift

These methods are aimed at detecting concept drift. In order to update the
detector, depending on the type of algorithm, they may require either the
ground-truth labels/values or the values of the variable to be tracked, which
is usually a model performance metric. The detector can receive the update
values on demand; therefore, it is not mandatory to feed it with all the
ground-truth labels/values or model performance metric values. All implemented
methods work in a streaming manner, receiving one sample at a time.

In terms of implementation, each detector inherits from the `BaseConceptDrift`
abstract class. Depending on the type of concept drift detector, it also
inherits from its corresponding type abstract class. The `update` method is
used to update the detector’s inner state, and it checks if drift is occurring
each time a new value is received. Additionally, upon instantiation, the
detector can optionally receive a list of callbacks. It also receives a
configuration class that contains specific parameters determining its
behavior.

###  3.2 Data drift

Data drift methods focus on detecting changes by considering only the
covariates. Therefore, these algorithms try to detect changes at a feature
level by comparing new data distributions against reference data
distributions.

Depending on the number of samples given to the detector to compare with the
reference distribution, these methods can be classified as batch or streaming.
The former uses a batch of samples to test against the reference distribution,
and the latter can receive one sample at a time to update the inner state of
the detector, therefore the samples must follow a sequential order.

Unlike concept drift detectors, there is a `fit` method that stores the
samples from the reference distribution used for comparison at inference time.
In the case of batch algorithms, the `compare` method is used to carry out the
comparison and obtain a statistic or distance value depending on the type of
detector. Whereas for the streaming detectors, an `update` method is used each
time a new sample is added to the detector.

Based on the type of data drift detector (statistical test or distance-based),
checking if drift is taking place is done in different ways. After calling the
`compare` or `update` methods, statistical tests provide the corresponding
p-value that determines if drift exists. For distance-based detectors, the
output is only the distance between the provided data and the data from the
reference distribution. Therefore through the use of callbacks, explained in
Section 3.3, p-values can be obtained.

Moreover, data drift detectors are implemented considering the type of data
that they are expected to work with (categorical or numerical) and the number
of features that can be considered (univariate or multivariate).

As mentioned in Section 2, data drift methods can also be used for detecting
label drift by considering the label distribution. Consequently, the described
way of using the detectors for data drift applies to label drift.

###  3.3 Callbacks

Execution of custom code at certain points is possible through the use of
callbacks. This adds enough flexibility to `Frouros` to be adapted to real-
world use cases required by the users. Callbacks are divided according to
whether the detector belongs to the batch or streaming category.

For batch detectors, callbacks inherit from `BaseCallbackBatch` class, which
provides methods such as `on_compare_start` and `on_compare_end`. These
methods can be implemented to execute custom code before and after the
comparison against the reference distribution is made.

In the case of streaming detectors, similar methods are provided for the
`update` method. All callbacks detectors share `on_fit_start` and `on_fit_end`
provided by `BaseCallback`, due to the fact that data drift detectors can be
categorised as batch or streaming.

Some examples of callbacks already implemented and ready to use in the library
include tracking the history of a concept drift detector, computing p-values
through the use of permutation tests in distance-based data drift detectors,
among others.

##  4 Development

With the intention of following a set of open-source software development
standards that allow the maintainability and extensibility of the library over
time, we emphasize the following areas:

#### Continuous integration.

A continuous integration workflow based on `GitHub` `Actions` ensures that new
modifications easily integrate with the existing code base and that they are
compatible with multiple Python versions.

#### Documentation.

An API documentation is provided using `sphinx` and hosted on the `Read` `the`
`Docs`111https://frouros.readthedocs.io website. The documentation includes
some basic and advanced examples on the use of these detection methods.

#### Quality code.

To ensure minimum standards in terms of code quality, code coverage is set to
be greater than 90%, and some Python quality and style tools that comply with
PEP8 standards (Van Rossum et al., 2001) are used, such as `flake8`, `pylint`,
`black`, and `mypy`.

#### Open-source.

In addition to the source code being available on
`GitHub`222https://github.com/IFCA/frouros, `Frouros` package can be installed
through the Python Package Index (PyPI)333https://pypi.org/project/frouros. In
terms of licensing, it is distributed under the BSD-3-Clause license.

##  5 Comparison to related software

With regard to the concept drift detection part, `MOA` (Bifet et al., 2010)
has most of the methods that we are including, but they are implemented in
Java. In Python, `River` (Montiel et al., 2021), which is focused on online
machine learning and streaming data, offers some concept drift detection
methods, but only a subset of those presented here. Another Python library
that contains this type of detectors is `scikit-multiflow` (Montiel et al.,
2018), but it has not been taken into account due to the fact that it was
merged with the online machine learning library `Creme` (Halford et al.,
2019), resulting in the aforementioned `River` library.

For the data drift section, `Alibi Detect` (Van Looveren et al., 2019) has
several algorithms related to the field of statistical two-sample hypothesis
testing, and some of them can act both online (single sample) and offline
(batch sample). `TorchDrift` Viehmann et al. (2021) also implements some
statistical two-sample hypothesis testing methods, but in this case, it uses
`PyTorch` (Paszke et al., 2019) for their implementation.

To the best of our knowledge, `Menelaus` Leigh et al. (2022) is the only open-
source library that has both concept and data drift methods, although they
classify them into the following types: change detection, concept drift, and
data drift. Concept drift methods are implemented in such a way that the user
must necessarily be in charge of controlling each iteration of the sample
without offering some helper functions or classes to interact with the
detector, as `Frouros` does with the callbacks concept that is explained in
Section 3.3.

Table 1 provides a more detailed view of the methods implemented in each of
the libraries mentioned above, as well as those included in `Frouros`. At the
time of writing this paper, `Frouros` is listed as the library with the
highest number of available methods with 28.

Moreover, several other libraries and tools have been excluded from Table 1
due to the fact that they implement a more limited number of methods or are
more focused on building graphical dashboards and visual representations, such
as `Deepchecks` (Bressler et al., 2022), `Eurybia` (Roux et al., 2022),
`Evidently` (Dral, 2020), `NannyML` (Nuyttens and Perrakis, 2022), or
`UpTrain` (Gupta, 2023).

| Method |  Alibi-detect |  Menelaus |  MOA |  River |  TorchDrift |  Frouros | Reference
---|---|---|---|---|---|---|---|---
Concept drift | ADWIN |  | ✓ | ✓ | ✓ |  | ✓ | Bifet and Gavalda (2007)
BOCD |  |  |  |  |  | ✓ | Adams and MacKay (2007)
CUSUM |  | ✓ | ✓ |  |  | ✓ | Page (1954)
DDM |  | ✓ | ✓ | ✓ |  | ✓ | Gama et al. (2004)
ECDD-WT |  |  | ✓ |  |  | ✓ | Ross et al. (2012)
EDDM |  | ✓ | ✓ | ✓ |  | ✓ | Baena-Garcıa et al. (2006)
GMA |  |  | ✓ |  |  | ✓ | Roberts (1959)
HDDM-A |  |  | ✓ | ✓ |  | ✓ | Frias-Blanco et al. (2014)
HDDM-W |  |  | ✓ | ✓ |  | ✓ | Frias-Blanco et al. (2014)
KSWIN |  |  |  | ✓ |  | ✓ | Raab et al. (2020)
LFR |  | ✓ |  |  |  |  | Wang and Abraham (2015)
Page Hinkley |  | ✓ | ✓ | ✓ |  | ✓ | Page (1954)
RDDM |  |  | ✓ |  |  | ✓ | Barros et al. (2017)
SEED |  |  | ✓ |  |  |  | Huang et al. (2014)
SeqDrift1 |  |  | ✓ |  |  |  | Sakthithasan et al. (2013)
SeqDrift2 |  |  | ✓ |  |  |  | Pears et al. (2014)
STEPD |  | ✓ | ✓ |  |  | ✓ | Nishida and Yamauchi (2007)
MD3 |  | ✓ |  |  |  |  | Sethi and Kantardzic (2017)
Data drift | Anderson-Darling test |  |  |  |  |  | ✓ | Scholz and Stephens (1987)
Bhattacharyya Distance |  |  |  |  |  | ✓ | Bhattacharyya (1946)
C2ST | ✓ |  |  |  |  |  | Lopez-Paz and Oquab (2016)
CDBD |  | ✓ |  |  |  |  | Lindstrom et al. (2013)
Context-aware MMD | ✓ |  |  |  |  |  | Cobb and Van Looveren (2022)
Cramér-von Mises test | ✓ |  |  |  |  | ✓ | Cramér (1928)
Earth Mover’s Distance |  |  |  |  | ✓ | ✓ | Rubner et al. (2000)
Fisher’s Exact test | ✓ |  |  |  |  |  | Upton (1992)
Hellinger Distance |  |  |  |  |  | ✓ | Hellinger (1909)
HDDDM |  | ✓ |  |  |  |  | Ditzler and Polikar (2011)
Histogram Intersection |  |  |  |  |  | ✓ | Swain and Ballard (1991)
Incremental KS test |  |  |  |  |  | ✓ | dos Reis et al. (2016)
JS Divergence |  |  |  |  |  | ✓ | Lin (1991)
kdq-Tree |  | ✓ |  |  |  |  | Dasu et al. (2006)
KL Divergence |  |  |  |  |  | ✓ | Kullback and Leibler (1951)
Kolmogorov-Smirnov test | ✓ |  |  |  | ✓ | ✓ | Massey Jr (1951)
Learned Kernel MMD | ✓ |  |  |  |  |  | Liu et al. (2020)
LSDD | ✓ |  |  |  |  |  | Bu et al. (2016)
Mann-Whitney U test |  |  |  |  |  | ✓ | Mann and Whitney (1947)
MMD | ✓ |  |  |  | ✓ | ✓ | Gretton et al. (2012)
NN-DVI |  | ✓ |  |  |  |  | Liu et al. (2018)
Partial MMD |  |  |  |  | ✓ |  | Viehmann (2021)
PCA-CD |  | ✓ |  |  |  |  | Qahtan et al. (2015)
PSI |  |  |  |  |  | ✓ | Wu and Olson (2010)
Welch’s t-test |  |  |  |  |  | ✓ | Welch (1947)
| ${\chi}^{2}$ | ✓ |  |  |  |  | ✓ | Pearson (1900)
| # Methods | 9 | 13 | 14 | 7 | 4 | 28 |

Table 1: Drift detection methods by library

##  6 Conclusion and future work

This paper presents `Frouros`, an open-source Python library for drift
detection in machine learning systems that can be used with any machine
learning framework, both for methods that aim to detect concept drift and
those that try to detect data drift. Moreover, this library provides enough
flexibility to adapt to the user’s workflow through the so-called callbacks
concept, which is also used in other well-known machine learning libraries.
Additionally, `Frouros` aims to meet open-source software development
standards that allow for easy extension, both in terms of adding new methods
or callbacks.

For future work, in addition to regularly adding new detection methods, we
plan to improve the performance of concept drift methods using Python code
optimizers like Cython Behnel et al. (2010) and adapt data drift methods to be
used on GPUs. Furthermore, adding new callbacks, as described in Section 3.3,
would enable the library to handle even more real-world use cases.

Acknowledgments

The authors acknowledge the funding from the Agencia Estatal de Investigación,
Unidad de Excelencia María de Maeztu, ref. MDM-2017-0765 and the support from
the project AI4EOSC “Artificial Intelligence for the European Open Science
Cloud” that has received funding from the European Union’s Horizon Europe
Research and Innovation Programme under grant agreement 101058593.

## References

  * Ackerman et al. (2021) S. Ackerman, O. Raz, M. Zalmanovici, and A. Zlotnick.  Automatically detecting data drift in machine learning classifiers.  _arXiv preprint arXiv:2111.05672_ , 2021.
  * Adams and MacKay (2007) R. P. Adams and D. J. MacKay.  Bayesian online changepoint detection.  _arXiv preprint arXiv:0710.3742_ , 2007.
  * Baena-Garcıa et al. (2006) M. Baena-Garcıa, J. del Campo-Ávila, R. Fidalgo, A. Bifet, R. Gavalda, and R. Morales-Bueno.  Early drift detection method.  In _Fourth international workshop on knowledge discovery from data streams_ , volume 6, pages 77–86, 2006.
  * Barros et al. (2017) R. S. Barros, D. R. Cabral, P. M. Gonçalves Jr, and S. G. Santos.  Rddm: Reactive drift detection method.  _Expert Systems with Applications_ , 90:344–355, 2017.
  * Bayram et al. (2022) F. Bayram, B. S. Ahmed, and A. Kassler.  From concept drift to model degradation: An overview on performance-aware drift detectors.  _Knowledge-Based Systems_ , page 108632, 2022.
  * Behnel et al. (2010) S. Behnel, R. Bradshaw, C. Citro, L. Dalcin, D. S. Seljebotn, and K. Smith.  Cython: The best of both worlds.  _Computing in Science & Engineering_, 13(2):31–39, 2010.
  * Bhattacharyya (1946) A. Bhattacharyya.  On a measure of divergence between two multinomial populations.  _Sankhyā: the indian journal of statistics_ , pages 401–406, 1946\.
  * Bifet and Gavalda (2007) A. Bifet and R. Gavalda.  Learning from time-changing data with adaptive windowing.  In _Proceedings of the 2007 SIAM international conference on data mining_ , pages 443–448. SIAM, 2007.
  * Bifet et al. (2010) A. Bifet, G. Holmes, B. Pfahringer, P. Kranen, H. Kremer, T. Jansen, and T. Seidl.  Moa: Massive online analysis, a framework for stream classification and clustering.  In _Proceedings of the first workshop on applications of pattern analysis_ , pages 44–50. PMLR, 2010.
  * Bressler et al. (2022) N. Bressler, I. Gabbay, S. Chorev, P. Tannor, M. Perlmutter, N. Hutnik, J. Liberman, D. Ben Israel, and Y. Romanyshyn.  Deepchecks: Comprehensive testing and validation of ml models and data, 2022.  URL https://www.deepchecks.com/.  Software available from https://github.com/deepchecks/deepchecks.
  * Bu et al. (2016) L. Bu, C. Alippi, and D. Zhao.  A pdf-free change detection test based on density difference estimation.  _IEEE transactions on neural networks and learning systems_ , 29(2):324–334, 2016.
  * Chollet et al. (2015) F. Chollet et al.  Keras.  https://keras.io, 2015.
  * Cobb and Van Looveren (2022) O. Cobb and A. Van Looveren.  Context-aware drift detection.  In _International Conference on Machine Learning_ , pages 4087–4111. PMLR, 2022.
  * Cramér (1928) H. Cramér.  On the composition of elementary errors: First paper: Mathematical deductions.  _Scandinavian Actuarial Journal_ , 1928(1):13–74, 1928.
  * Dasu et al. (2006) T. Dasu, S. Krishnan, S. Venkatasubramanian, and K. Yi.  An information-theoretic approach to detecting changes in multi-dimensional data streams.  In _In Proc. Symp. on the Interface of Statistics, Computing Science, and Applications_. Citeseer, 2006.
  * Ditzler and Polikar (2011) G. Ditzler and R. Polikar.  Hellinger distance based drift detection for nonstationary environments.  In _2011 IEEE symposium on computational intelligence in dynamic and uncertain environments (CIDUE)_ , pages 41–48. IEEE, 2011.
  * dos Reis et al. (2016) D. M. dos Reis, P. Flach, S. Matwin, and G. Batista.  Fast unsupervised online drift detection using incremental kolmogorov-smirnov test.  In _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_ , pages 1545–1554, 2016.
  * Dral (2020) E. Dral.  An open-source framework to evaluate, test and monitor ml models in production.  https://github.com/evidentlyai/evidently, 2020.  Online; accessed 23-7-2023.
  * Falcon and The PyTorch Lightning team (2019) W. Falcon and The PyTorch Lightning team.  PyTorch Lightning, Mar. 2019.  URL https://github.com/Lightning-AI/lightning.
  * Frias-Blanco et al. (2014) I. Frias-Blanco, J. del Campo-Ávila, G. Ramos-Jimenez, R. Morales-Bueno, A. Ortiz-Diaz, and Y. Caballero-Mota.  Online and non-parametric drift detection methods based on hoeffding’s bounds.  _IEEE Transactions on Knowledge and Data Engineering_ , 27(3):810–823, 2014.
  * Gama et al. (2004) J. Gama, P. Medas, G. Castillo, and P. Rodrigues.  Learning with drift detection.  In _Brazilian symposium on artificial intelligence_ , pages 286–295. Springer, 2004.
  * Gama et al. (2013) J. Gama, R. Sebastiao, and P. P. Rodrigues.  On evaluating stream learning algorithms.  _Machine learning_ , 90(3):317–346, 2013.
  * Gama et al. (2014) J. Gama, I. Žliobaitė, A. Bifet, M. Pechenizkiy, and A. Bouchachia.  A survey on concept drift adaptation.  _ACM computing surveys (CSUR)_ , 46(4):1–37, 2014\.
  * Goldenberg and Webb (2019) I. Goldenberg and G. I. Webb.  Survey of distance measures for quantifying concept drift and shift in numeric data.  _Knowledge and Information Systems_ , 60(2):591–615, 2019.
  * Gretton et al. (2012) A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola.  A kernel two-sample test.  _Journal of Machine Learning Research_ , 13(25):723–773, 2012.  URL http://jmlr.org/papers/v13/gretton12a.html.
  * Gupta (2023) V. Gupta.  An open-source framework to observe ml applications, built for engineers.  https://github.com/uptrain-ai/uptrain, 2023.  Online; accessed 23-7-2023.
  * Halford et al. (2019) M. Halford, G. Bolmier, R. Sourty, R. Vaysse, and A. Zouitine.  creme, a Python library for online machine learning, 2019.  URL https://github.com/MaxHalford/creme.
  * Hellinger (1909) E. Hellinger.  Neue begründung der theorie quadratischer formen von unendlichvielen veränderlichen.  _Journal für die reine und angewandte Mathematik_ , 1909(136):210–271, 1909.
  * Huang et al. (2014) D. T. J. Huang, Y. S. Koh, G. Dobbie, and R. Pears.  Detecting volatility shift in data streams.  In _2014 IEEE International Conference on Data Mining_ , pages 863–868. IEEE, 2014.
  * Khamassi et al. (2018) I. Khamassi, M. Sayed-Mouchaweh, M. Hammami, and K. Ghédira.  Discussion and review on evolving data streams and concept drift adapting.  _Evolving systems_ , 9(1):1–23, 2018.
  * Kullback and Leibler (1951) S. Kullback and R. A. Leibler.  On information and sufficiency.  _The annals of mathematical statistics_ , 22(1):79–86, 1951.
  * Leigh et al. (2022) N. Leigh, T. Schill, I. Lindsay, A. Srivastava, K. P. McNamara, and S. Jarmale.  Menelaus.  https://github.com/mitre/menelaus, 2022.  Online; accessed 23-7-2023.
  * Lin (1991) J. Lin.  Divergence measures based on the shannon entropy.  _IEEE Transactions on Information theory_ , 37(1):145–151, 1991.
  * Lindstrom et al. (2013) P. Lindstrom, B. Mac Namee, and S. J. Delany.  Drift detection using uncertainty distribution divergence.  _Evolving Systems_ , 4(1):13–25, 2013.
  * Liu et al. (2018) A. Liu, J. Lu, F. Liu, and G. Zhang.  Accumulating regional density dissimilarity for concept drift detection in data streams.  _Pattern Recognition_ , 76:256–272, 2018.
  * Liu et al. (2020) F. Liu, W. Xu, J. Lu, G. Zhang, A. Gretton, and D. J. Sutherland.  Learning deep kernels for non-parametric two-sample tests.  In _International conference on machine learning_ , pages 6316–6326. PMLR, 2020.
  * Lopez-Paz and Oquab (2016) D. Lopez-Paz and M. Oquab.  Revisiting classifier two-sample tests.  _arXiv preprint arXiv:1610.06545_ , 2016.
  * Mann and Whitney (1947) H. B. Mann and D. R. Whitney.  On a test of whether one of two random variables is stochastically larger than the other.  _The annals of mathematical statistics_ , pages 50–60, 1947.
  * Massey Jr (1951) F. J. Massey Jr.  The kolmogorov-smirnov test for goodness of fit.  _Journal of the American statistical Association_ , 46(253):68–78, 1951.
  * Montiel et al. (2018) J. Montiel, J. Read, A. Bifet, and T. Abdessalem.  Scikit-multiflow: A multi-output streaming framework.  _Journal of Machine Learning Research_ , 19(72):1–5, 2018.  URL http://jmlr.org/papers/v19/18-251.html.
  * Montiel et al. (2021) J. Montiel, M. Halford, S. M. Mastelini, G. Bolmier, R. Sourty, R. Vaysse, A. Zouitine, H. M. Gomes, J. Read, T. Abdessalem, and A. Bifet.  River: machine learning for streaming data in python.  _Journal of Machine Learning Research_ , 22(110):1–8, 2021.  URL http://jmlr.org/papers/v22/20-1380.html.
  * Moreno-Torres et al. (2012) J. G. Moreno-Torres, T. Raeder, R. Alaiz-Rodríguez, N. V. Chawla, and F. Herrera.  A unifying view on dataset shift in classification.  _Pattern recognition_ , 45(1):521–530, 2012.
  * Nishida and Yamauchi (2007) K. Nishida and K. Yamauchi.  Detecting concept drift using statistical testing.  In _International conference on discovery science_ , pages 264–269. Springer, 2007.
  * Nuyttens and Perrakis (2022) N. Nuyttens and N. Perrakis.  Nannyml.  https://github.com/NannyML/nannyml, 2022.  Online; accessed 23-7-2023.
  * Page (1954) E. S. Page.  Continuous inspection schemes.  _Biometrika_ , 41(1/2):100–115, 1954.
  * Paszke et al. (2019) A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ , 32, 2019.
  * Pears et al. (2014) R. Pears, S. Sakthithasan, and Y. S. Koh.  Detecting concept change in dynamic data streams.  _Machine Learning_ , 97(3):259–293, 2014.
  * Pearson (1900) K. Pearson.  X. on the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling.  _The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science_ , 50(302):157–175, 1900.
  * Qahtan et al. (2015) A. A. Qahtan, B. Alharbi, S. Wang, and X. Zhang.  A pca-based change detection framework for multidimensional data streams: Change detection in multidimensional data streams.  In _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 935–944, 2015.
  * Raab et al. (2020) C. Raab, M. Heusinger, and F.-M. Schleif.  Reactive soft prototype computing for concept drift streams.  _Neurocomputing_ , 416:340–351, 2020.
  * Rabanser et al. (2019) S. Rabanser, S. Günnemann, and Z. Lipton.  Failing loudly: An empirical study of methods for detecting dataset shift.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Roberts (1959) S. W. Roberts.  Control chart tests based on geometric moving averages.  _Technometrics_ , 1(3):239–250, 1959.  ISSN 00401706.  URL http://www.jstor.org/stable/1266443.
  * Ross et al. (2012) G. J. Ross, N. M. Adams, D. K. Tasoulis, and D. J. Hand.  Exponentially weighted moving average charts for detecting concept drift.  _Pattern recognition letters_ , 33(2):191–198, 2012.
  * Roux et al. (2022) N. Roux, J. Martin, and T. Bouché.  Eurybia.  https://github.com/MAIF/eurybia, 2022.  Online; accessed 23-7-2023.
  * Rubner et al. (2000) Y. Rubner, C. Tomasi, and L. J. Guibas.  The earth mover’s distance as a metric for image retrieval.  _International journal of computer vision_ , 40(2):99–121, 2000.
  * Sakthithasan et al. (2013) S. Sakthithasan, R. Pears, and Y. S. Koh.  One pass concept change detection for data streams.  In _Pacific-Asia conference on knowledge discovery and data mining_ , pages 461–472. Springer, 2013.
  * Scholz and Stephens (1987) F. W. Scholz and M. A. Stephens.  K-sample anderson–darling tests.  _Journal of the American Statistical Association_ , 82(399):918–924, 1987.
  * Sethi and Kantardzic (2017) T. S. Sethi and M. Kantardzic.  On the reliable detection of concept drift from streaming unlabeled data.  _Expert Systems with Applications_ , 82:77–99, 2017.  ISSN 0957-4174.  doi: https://doi.org/10.1016/j.eswa.2017.04.008.  URL https://www.sciencedirect.com/science/article/pii/S0957417417302439.
  * Storkey (2009) A. J. Storkey.  When training and test sets are different: characterizing learning transfer.  _Dataset shift in machine learning_ , 30(3-28):6, 2009.
  * Swain and Ballard (1991) M. J. Swain and D. H. Ballard.  Color indexing.  _International journal of computer vision_ , 7(1):11–32, 1991.
  * Upton (1992) G. J. Upton.  Fisher’s exact test.  _Journal of the Royal Statistical Society: Series A (Statistics in Society)_ , 155(3):395–402, 1992.
  * Van Looveren et al. (2019) A. Van Looveren, J. Klaise, G. Vacanti, O. Cobb, A. Scillitoe, R. Samoilescu, and A. Athorne.  Alibi detect: Algorithms for outlier, adversarial and drift detection, 2019.  URL https://github.com/SeldonIO/alibi-detect.
  * Van Rossum et al. (2001) G. Van Rossum, B. Warsaw, and N. Coghlan.  Pep 8–style guide for python code.  _Python. org_ , 1565:28, 2001.
  * Viehmann (2021) T. Viehmann.  Partial wasserstein and maximum mean discrepancy distances for bridging the gap between outlier detection and drift detection.  _arXiv preprint arXiv:2106.12893_ , 2021.
  * Viehmann et al. (2021) T. Viehmann, L. Antiga, D. Cortinovis, and L. Lozza.  Torchdrift.  https://github.com/torchdrift/torchdrift, 2021.  Online; accessed 23-7-2023.
  * Wang and Abraham (2015) H. Wang and Z. Abraham.  Concept drift detection for streaming data.  In _2015 international joint conference on neural networks (IJCNN)_ , pages 1–9. IEEE, 2015.
  * Welch (1947) B. L. Welch.  The generalization of ‘student’s’problem when several different population varlances are involved.  _Biometrika_ , 34(1-2):28–35, 1947.
  * Wu and Olson (2010) D. Wu and D. L. Olson.  Enterprise risk management: coping with model risk in a large bank.  _Journal of the Operational Research Society_ , 61(2):179–190, 2010.
  * Žliobaitė et al. (2016) I. Žliobaitė, M. Pechenizkiy, and J. Gama.  An overview of concept drift applications.  _Big data analysis: new algorithms for a new society_ , pages 91–114, 2016.


# Fully Quantum Classifier

Wojciech Roga1<EMAIL_ADDRESS>Baptiste Chevalier1,2
<EMAIL_ADDRESS>Masahiro Takeoka1,3
<EMAIL_ADDRESS>1Department of Electronics and Electrical Engineering,
Keio University, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama 223-8522, Japan
2Sorbonne Université, CNRS, LIP6, 4 place Jussieu, F-75005 Paris, France
3Advanced ICT Research Institute, National Institute of Information and
Communications Technology (NICT), Koganei, Tokyo 184-8795, Japan

###### Abstract

In this paper we present a supervised machine learning quantum classifier. It
consists of a quantum data re-uploading classifier with binary trainable
parameters, the optimal values of which are found by a quantum search
algorithm. We show that we can reach the quadratic speed-up in optimization
trainable parameters compared to classical brute force search.

##  I Background and motivation

In the modern data driven society, Artificial Intelligence and especially data
classification are on the spotlight with a big impact on everyday life and
economy.

However the latter faces several challenges including the volume of data to
process and the exploding number of parameters to train with direct impacts on
security, privacy, and economy. That is why there is a need to always reduce
computation time on one hand and to increase accuracy of the methods on the
other.

In this way, the researchers have been exploring possibilities offered by
quantum technology attracted by quantum features such as: exponential scaling
of the dimensionality of quantum states with the number of elementary systems,
parallelism of quantum superposition, non-classical correlations provided by
quantum entanglement and computational speed-up offered by quantum algorithms
[1]. Indeed the volume of research papers on the ”quantum classifier” topic as
well as the number of citations sharply increased within the last ten years,
with no sign of saturation yet [2].

Moreover, applications for machine learning have already been investigated
through the use of Variational Quantum Algorithms exploiting nowadays NISQ
devices [3]. Many competing models of quantum classifiers have been proposed
for both fault-tolerant Quantum computers and NISQ devices as: QSVM [4],
Quantum decision trees, Quantum Nearest Neighbours, Quantum Kernel methods and
many variational methods for QNN, QCNN [5], QTN [6] (see for instance [7] for
a comprehensive review). Among them, one of the state of the art method is the
so-called data re-uploading [8] that allows for universal classification. A
recent research shows a notable interest in it with respect to other methods
[9].

While concrete advantages presented by those methods are still discussed, as
the training is still done in a classical fashion, it is clear that they
suffer from the crucial problem of training a large number of parameters. If
focusing on the case where parameters are binary, training the cost function
with no further assumptions can turn out highly complex. Also there is no
guarantees that the optimal configuration of parameters can be found because
of the issues like barren plateaus, among others [10]. Alternative methods for
hybrid algorithms have been proposed to bypass this problems, for example,
iterative methods based on parameter-shifting instead of gradient-free
optimizers [11, 12]. Other methods based on sequential optimization of
parameters have been used too [13, 14].

Besides, some arguments suggest that quantum computers may help with the task
of training many parameters due to an advantage of sampling over optimization
in specific cases [15, 16] as well as amplitude amplification based algorithms
[17, 18, 19]. Quantum training algorithms have already been investigated for a
long time [20, 21, 22]. Although exponential speed-up is unachievable in most
cases, except under very strict assumptions, quadratic speed-up can be reached
in general. In [23] the author discuss how those methods could be applied in a
Quantum Kernel setting. However, to our best knowledge, no one has yet
considered applying a quantum training algorithm in recent QML methods as, for
instance, data re-uploading. In this paper we present a fully-quantum
classifier based on data re-uploading scheme. In addition to the universality
of this method it benefits from a novel quantum training algorithm achieving a
quadratic speedup over classical methods.

##  II Introduction

In this paper we present a supervised machine learning quantum classifier
trained by a quantum algorithm. The starting point and elementary building
block of our classifier is the single-qubit classifier with data re-uploading
shown in figure 1 $a)$ or its two qubit version shown in figure 1 $b)$. The
idea of the quantum classifier with data re-uploading was introduced in [8] to
show that even a single qubit system can compute complicated functions of
parameters of the circuit. It consisted in a single qubit circuit with many
one qubit gates such that the parameters of the gates can encode either the
values of the coordinates of a training point or free trainable parameters. In
a well trained classifier the thresholded probability of the chosen output
state indicates the class. The technique of [8] applied a supervised machine
learning with hybrid quantum-classical training based on the optimization of
the cost function fed by outputs from the one-qubit quantum circuit.

It was proven in [8] that the counterpart of the universal approximation
theory known from the theory of the single layer neural network holds in this
case. In [24] the idea was extended to bosonic systems with even a single
photon. The authors of the latter also provided the experimental proof of
principle on the integrated photonics silicon chip.

Figure 1: Scheme of data re-uploading circuit. $a)$ Training data $x_{i}$
associated with binary class label $y_{i}$ is introduced many times as a
parameter of unitary transformations. Other unitary transformations contain
trainable parameters used for training by optimization of the cost function
fed by the output probability $p_{i}^{\vec{\phi}}(|y_{i}\rangle)$. The
classification is based on the value of the probability
$p_{i}^{\vec{\phi}}(|y_{i}\rangle)$ after training. $b)$ The same idea with
two qubit circuits of only orthogonal transformations which we use in this
paper as it is convenient to deal with real amplitude states at the output
from the circuit.

For the algorithms we discuss in this paper it is convenient that the
elementary classifiers produce only real amplitude output states. Therefore in
this paper we replace the original idea of the one-qubit classifier with the
SU(2) circuit shown in figure 1 $a)$ by the two-qubit classifier with the
circuit restricted to SO(3) transformations, as in figure 1 $b)$. Due to the
local isomorphism between SU(2) and SO(3) groups, the classifier with the 3D
orthogonal transformations inherits the universality features of the single
qubit classifier with the unitary circuit.

As the number of trainable parameters in the data re-uploading classifier can
quickly grow the training of the circuit becomes challenging. Therefore in
this paper, we explore the possibility of a parallel version of the classifier
in which we introduce the dependence of the tunable parameters, which we
assume now to be binary, on additional qubits. This scheme is shown in figure
2.

Before proceeding let us comment on replacing the continuous angles with
binary parameters. First of all, reducing continuous values to discrete does
not remove the problem with the complexity of the search of the optimal set of
angles on which we want to focus in this paper. Moreover, finding the best
configuration of discrete angles is still interesting from the point of view
of the search for the best starting point for the local search algorithms.
Finally, composing rotations with discrete values, in principle, one can build
arbitrary approximation of continuous rotations. Although we do not want to
explore the last direction, this generalization is a straightforward extension
of the proposed scheme.

Conditioning the circuit parameters on additional qubits allows us to create a
quantum superposition with the amplitudes related to different values of a
specifically chosen objective function discussed in the next section.
Following that, we propose to perform the quantum maximization algorithms [18]
and nonlinear transformations of complex amplitudes [25] to maximize the
objective function and train the classifier. Finally, we analyze the
complexity of this scenario and observe that the fully quantum training can be
advantageous with respect to classical maximum search algorithm with no
assumptions achieving at most quadratic speed up.

Figure 2: A parallelized version of the two qubit based quantum classifier
with data re-uploading and orthogonal 3D transformations in which quantum
search algorithms can be used for training. Parameters $x$ denote training
data, parameters $\varphi$ adjustable parameters which we assume here to be
binary.

##  III Objective function and circuit description

We assume that we have $k$ training points $\vec{x}=(x_{1},...,x_{k})$ each of
which belongs to one of two classes $y_{i}\in\\{0,1\\}$. For each training
point we prepare a copy of the circuit from figure 1 $b)$ with the same $n$
trainable parameters $\vec{\varphi}=(\varphi_{1},...,\varphi_{n})$. As our
objective function we take the product of the probabilities to measure the
correct class $y_{i}$ for each data point in the first of two output qubits of
elementary classifiers

$P^{\vec{y}}(\vec{\varphi})=p_{\vec{\varphi},x_{1}}(|y_{1}0\rangle)\
p_{\vec{\varphi},x_{2}}(|y_{2}0\rangle)\ ...\
p_{\vec{\varphi},x_{k}}(|y_{k}0\rangle).$ (1)

This is the function of trainable parameters $\vec{\varphi}$ common to all
copies of the circuit and training points $\vec{x}$. Considering here the
probabilities of outputs from the elementary classifiers, fig. 1 $b)$ with
zero in the second qubit is our arbitrary choice and does not restrict
generality. Objective function (1) is closely related to the log likelihood.
We want to train the circuits such that $P^{\vec{y}}(\vec{\varphi})$ is
maximized. When the training is finished we choose a threshold for the
probability of output state $|10\rangle$ in a single copy of the elementary
classifier from figure 1 $b)$ with optimized $\vec{\varphi}$ and a testing
point $x$. If the probability is above the threshold we classify $x$ as a
point of class 1, otherwise we judge it as a point of class 0.

To utilize the quantum search algorithm we would like to have a superposition
of all possible values of our objective function

$|\Psi\rangle=\sum_{\vec{\varphi}}\mathcal{A}^{\vec{y}}(\vec{\varphi})|\vec{\varphi}\rangle,$
(2)

where ${\mathcal{A}^{\vec{y}}(\vec{\varphi})}^{2}=P^{\vec{y}}(\vec{\varphi})$.
Indeed having state $|\Psi\rangle$ we would use Dürr and Høyer maximization
algorithm [18] to find the maximum in, on average, $\mathcal{O}(2^{n/2})$
steps assuming access to appropriate oracles, the problem of which we will
face in the next parts. This complexity would be advantageous with respect to
a classical algorithm that without further assumptions would find
$\max_{\vec{\varphi}}P^{\vec{y}}(\vec{\varphi})$ in $\mathcal{O}(2^{n})$
steps. This rough estimation motivates us to search for a circuit that outputs
$|\Psi\rangle$.

To construct $|\Psi\rangle$ we propose to use a circuit shown in figure 2. It
consists of two registers, the ”program register” with $2k$ qubits, where $k$
is the number of training points; and ”training register” with $n$ qubits,
where $n$ is the number of parameters in our elementary circuit. The
elementary circuits with the same parameters but different training points
repetitively re-uploaded are in each line of the program register. The qubits
in the training register are prepared in the uniform superposition of all
possible states. The orthogonal transformations in the program register with
different $\vec{\varphi}$ are applied conditionally depending on the state of
the training register. In consequence, the output state from this circuit is

$|\Phi\rangle=\frac{1}{\sqrt{2^{n}}}\sum_{\vec{y}^{\prime},\vec{\varphi}}\mathcal{A}^{\vec{y}^{\prime}}(\vec{\varphi})|\vec{y}^{\prime}\rangle_{prog}|\vec{\varphi}\rangle_{train},$
(3)

where the summation is over all possible configurations of $2k$-length bit
strings for $\vec{y}^{\prime}$ in the program register, and $n$-length strings
for $\vec{\varphi}$ in the training register. This state reduces to (2) if the
output of the program register $|\vec{y}^{\prime}\rangle$ corresponds to the
fixed program $\vec{y}$ there which describes classes of training points. So,
we conclude that it is possible to conditionally construct the superposition
of all objective functions (2) for given classification of training data which
we call program.

In what follows we will never perform selection of the program register and
maximization over the training register separately. To find the optimal
parameters $\vec{\varphi}$ for a given program $\vec{y}$ we will perform the
single algorithm described as follows.

##  IV Maximization algorithm

In [18] Dürr and Høyer proposed a well-known algorithm that allows for finding
maximum of a function $f$ with the domain of size $2^{n}$ in
$\mathcal{O}(2^{n/2})$ steps on average. This algorithm assumes that one has
access to the oracle $\tilde{S}$ which prepares the state
$\tilde{S}|0\rangle=\sum_{i}f_{i}|i\rangle$ and the oracle that marks all
entries $|i\rangle$ with $f_{i}$ larger than a chosen $f_{j}$. First, one
samples a number $|k\rangle$ randomly $1\leq k\leq 2^{n}$. Then, using the
Grover algorithm with the oracle that marks all entries $|j\rangle$ with
$f_{j}>f_{k}$ one amplifies the probability of sampling from only the marked
entries. This allows one to select an entry $|k^{\prime}\rangle$ with
$f_{k}^{\prime}$ larger than $f_{k}$ with high probability. Repeating this
procedure one can find the maximum with on average $\mathcal{O}(2^{n/2})$
applications of the oracle $\tilde{S}$ and its inverse. The detailed analysis
of the complexity of this protocol is given in [18], see also [19].

Unfortunately this procedure cannot be directly applied in our case as we do
not assume that we have access to the oracle $\tilde{S}$ or the marking oracle
from this algorithm. Instead, we have access to the unitary oracle $S$ that
creates (3) the circuit of which is shown in figure 2.

In our optimization algorithm we propose to make use of this oracle in a
protocol by Guo et al. [25] that allows for nonlinear transformations of real
and imaginary parts of the quantum amplitudes from (3). This algorithm is
called nonlinear transformation of complex amplitudes $NTCA$. We want to use
NTCA to suppress amplitudes smaller than the absolute value of the real
amplitude $f_{k}$ of a randomly sampled entry $|k\rangle$ of the training
register for a fixed program register. This allows us to follow the reasoning
of Dürr and Høyer [18] described above replacing the marking oracle-based
Grover algorithm with the NTCA.

The NTCA algorithm [25] assumes we have access to the unitary oracle $S$ that
creates the $M$-qubit state $|\Phi\rangle$ the amplitudes of which we want to
transform. In our case it will be the unitary transformation of the joint
program and training registers of the circuit from figure 2, hence $M=n+2k$.
Authors of [25] show how, using $S$ and its inverse four times, other single-
and two-qubit operators, and 2 additional ancillary qubits, to build a
Hermitian $2M+1$ qubit operator $X$ whose eigenvalues include the real parts
$x_{j}$ and the imaginary parts $z_{j}$ of the amplitudes of $|\Phi\rangle$,
i.e., $f_{j}=x_{j}+iz_{j}$. In our case, we need to deal only with real
amplitudes.

Having Hermitian operator $X$, one can use an algorithm [25] which depending
on additional auxiliary qubits builds another Hermitian operator $Y$ whose
eigenvalues are nonlinear functions $Q(x_{j})$. The nonlinear functions that
are allowed are approximated by degree-$d$ polynomials $Q^{\prime}(x_{j})$ and
satisfy

$|Q(x)|\leq\frac{1}{4},\quad{\rm for\ all}\ x\in[-1,1].$ (4)

Process of building $Y$ is successful if the ancillary qubits measured give a
desired output. The probability of the desired measurement of the ancillary
qubits can be amplified by the amplitude amplification algorithm [17].
Altogether the total algorithm requires on average

$\mathcal{O}\left(d\gamma\sqrt{\frac{2^{M}}{\sum_{i}|Q(x_{i})|^{2}}}\right)$
(5)

applications of $S$ and its inverse, where
$\gamma=\max_{x\in[-1,1]}\\{|Q(x)|\\}$ which is a parameters that guarantees
that (4) holds. Also a number $\mathcal{O}(dM)$ of elementary gates is
required.

Next we prepare the state which is a uniform superposition of the eigenstates
of operator $Y$, which are

$W|k\rangle_{ad}|0\rangle_{da,B},$ (6)

where $W$ is a circuit consisting of $S$ and its inversion on $2M+1$ qubit
register and additional one and two qubit gates, see [25]. This circuit acts
on the so-called address register $|k\rangle$ and data register (in our case
both consist of $M$ qubits), and auxiliary system $B$.

The superposition of the eigenstates after acting on it by Hermitian operator
$Y$ receives new amplitudes which are the eigenvalues of $Y$. Notice, what is
important in our fully quantum classifier implementation of the algorithm
[25], that as the input we can construct the superposition of states (6) with
fixed desired values of a part of the address register that corresponds to the
fixed program in the program register. In consequence, at the output of the
circuit we get the state which is

$|\Psi^{\prime}\rangle=\sum_{\vec{\varphi}}Q\left(\mathcal{A}^{\vec{y}}(\vec{\varphi})\right)|\vec{\varphi}\rangle,$
(7)

where $\vec{y}$ is chosen by us.

Our goal is to choose $Q$ as the effective activation function which in each
iteration of the Dürr and Høyer type maximization procedure suppresses the
probabilities of the entries $\vec{\varphi}$ with the amplitudes which
absolute values are smaller than a randomly selected reference. Then, by
measuring the training register, we randomly select a new reference and repeat
the procedure. We assume that for each reference $|\vec{\varphi}\rangle$ it is
possible to efficiently calculate the amplitude classically which is needed
for the appropriate choice of $Q$.

To do that one needs to compute classically the probabilities of the
elementary classifiers from figure 1 $b)$ for each training point with the
specific parameters $\vec{\varphi}$ sampled previously. In order to estimate
the cost of computing such amplitude, we consider the elementary quantum
circuit made of $\mathcal{O}(n)$ two-qubit gates. Hence the full circuit can
be represented as a single $4\times 4$ unitary computed in time
$\mathcal{O}(n)$. We need to repeat it $k$ times – for each each training
point. Since we already know the element $\vec{y}$ whose amplitude we want, it
can be obtained in linear time from the $k$ individual amplitudes already
computed for a total cost of $\mathcal{O}(nk)$. Thus the amplitude for a given
$\vec{\varphi}$ and $\vec{y}$ can be calculated efficiently.

The number of iterations in Dürr and Høyer algorithm is of the order of $n$.
As the first random sampling gives us the value such that there are on average
$2^{n}/2$ entries with larger amplitudes we sample from and each iteration
reduces the sampling space on average by half. Notice that, since the sampling
is done according to the state’s distribution rather than uniformly, the space
is actually reduced by more than half each time and the total number of
iterations can be significantly smaller. Also because Dürr and Høyer type
algorithms keep reducing the size of the sampling space in every iteration,
one is ensured, after iterating long enough, to find the global maximum that
is achievable for this circuit architecture and for a given objective function
(which can be different from the global maximum of the objective function in
general).

##  V Complexity analysis and quantum speed-up

The complexity of the classical brute force search of the set of binary
parameters $\vec{\varphi}$ of length $n$ without further assumption is
estimated as $\mathcal{O}(2^{n})$.

The complexity of search algorithm presented in this manuscript is estimated
as

$\mathcal{O}\left(nd\gamma\sqrt{\frac{2^{M}}{\sum_{i}|Q(x_{i})|^{2}}}\right)$
(8)

where we must repeat each step of Dür and Høyer algorithm with suppression of
small amplitudes by Guo algorithm [25] (5) in each of $\mathcal{O}(n)$ steps.
Observing only dependence on $n$ is on average $\mathcal{O}(n\sqrt{2^{n+2k}})$
applications of the oracle circuit. The full circuit needed acts on
$2(n+2k)+6$ qubits, where $k$ is the number of the training points. Also
$\mathcal{O}(d(n+2k))$ elementary single and two qubit gates are needed in
each step of the maximization algorithm.

If $2k<n$, i.e., the number of training points is smaller than the number of
parameters we start to observe the speed-up. Scaling with respect to $n$ when
$k$ is kept fixed shows the quadratic speed up.

The proposed algorithm can be further improved if the maximum of the absolute
value of the amplitudes in (2) could be estimated. Also knowing the program
$\vec{y}$ one could try to design circuit with smaller dimension obtaining
speed up by some factor not related to $n$.

##  VI Conclusions

In this paper we propose a quantum circuit classifier with data re-uploading
and parameters trained by a quantum algorithm. The algorithm is based on the
Dür and Høyer maximization procedure [18] with NTCA by [25] replacing the
Grover algorithm in the original version. The complexity of the algorithm is
quadraticaly improved with respect to the classical brute force methods with
no further assumptions.

Notice that the same circuit as we propose here can be applied to many
programs given by the vector of classes of the training points.

_Acknowledgements_ This work was supported by JST Grant No. JPMJPF2221.

## References

  * Cerezo  _et al._ [2022] M. Cerezo, G. Verdon, H.-Y. Huang, L. Cincio, and P. J. Coles, Nature Computational Science 2, 567 (2022).
  * Cit [2023] “Clarivate web of science citation report chart for the number of publications and citations relate to quantum classifier as for may 2023,” (2023).
  * Cerezo  _et al._ [2021] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Nature Reviews Physics 3, 625 (2021).
  * Rebentrost  _et al._ [2014] P. Rebentrost, M. Mohseni, and S. Lloyd, Physical Review Letters 113, 130503 (2014).
  * Cong  _et al._ [2019] I. Cong, S. Choi, and M. D. Lukin, Nature Physics 15, 1273 (2019).
  * Huggins  _et al._ [2019] W. Huggins, P. Patel, K. B. Whaley, and E. M. Stoudenmire, Quantum Science and Technology 4, 024001 (2019).
  * Li and Deng [2022] W. Li and D.-L. Deng, Science China Physics, Mechanics & Astronomy 65, 220301 (2022).
  * Pérez-Salinas  _et al._ [2020] A. Pérez-Salinas, A. Cervera-Lierta, E. Gil-Fuster, and J. I. Latorre, Quantum 4, 226 (2020).
  * Jerbi  _et al._ [2023] S. Jerbi, L. J. Fiderer, H. P. Nautrup, J. M. Kübler, H. J. Briegel, and V. Dunjko, Nature Communications 14, 517 (2023).
  * McClean  _et al._ [2018] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Nature Communications 9, 4812 (2018).
  * Mitarai  _et al._ [2018] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, Physical Review A 98, 032309 (2018).
  * Schuld  _et al._ [2019] M. Schuld, V. Bergholm, C. Gogolin, J. Izaac, and N. Killoran, Physical Review A 99, 032331 (2019).
  * Nakanishi  _et al._ [2020] K. M. Nakanishi, K. Fujii, and S. Todo, Physical Review Research 2, 043158 (2020).
  * Roga  _et al._ [2023] W. Roga, T. Ono, and M. Takeoka, “Sequential minimum optimization algorithm with small sample size estimators,”  (2023), arXiv:2303.00992 [quant-ph].
  * Ma  _et al._ [2019] Y.-A. Ma, Y. Chen, C. Jin, N. Flammarion, and M. I. Jordan, Proceedings of the National Academy of Sciences 116, 20881 (2019).
  * Anari and Vuong [2021] N. Anari and T.-D. Vuong, “From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization,”  (2021), arXiv:2102.05347 [cs, stat].
  * Brassard  _et al._ [2002] G. Brassard, P. Hoyer, M. Mosca, and A. Tapp (2002) pp. 53–74, arXiv:quant-ph/0005055.
  * Durr and Hoyer [1999] C. Durr and P. Hoyer, “A Quantum Algorithm for Finding the Minimum,”  (1999), arXiv:quant-ph/9607014.
  * Ambainis [2005] A. Ambainis, “Quantum search algorithms,”  (2005), arXiv:quant-ph/0504012.
  * Wiebe  _et al._ [2012] N. Wiebe, D. Braun, and S. Lloyd, Physical Review Letters 109, 050505 (2012).
  * Lloyd  _et al._ [2014] S. Lloyd, M. Mohseni, and P. Rebentrost, Nature Physics 10, 631 (2014).
  * Schuld  _et al._ [2016] M. Schuld, I. Sinayskiy, and F. Petruccione, Physical Review A 94, 022342 (2016).
  * Schuld [2021] M. Schuld, “Supervised quantum machine learning models are kernel methods,”  (2021), arXiv:2101.11020 [quant-ph, stat].
  * Ono  _et al._ [2023] T. Ono, W. Roga, K. Wakui, M. Fujiwara, S. Miki, H. Terai, and M. Takeoka, Physical Review Letters 131, 013601 (2023).
  * Guo  _et al._ [2021] N. Guo, K. Mitarai, and K. Fujii, “Nonlinear transformation of complex amplitudes via quantum singular value transformation,”  (2021), arXiv:2107.10764 [quant-ph].


# Meta-Adversarial Inverse Reinforcement Learning
for Decision-making Tasks

Pin Wang1 Hanhan Li2 Ching-Yao Chan1 1 University of California, Berkeley
{pin_wang,cychan} @berkeley.edu2 Google Research<EMAIL_ADDRESS>
###### Abstract

Learning from demonstrations has made great progress over the past few years.
However, it is generally data hungry and task specific. In other words, it
requires a large amount of data to train a decent model on a particular task,
and the model often fails to generalize to new tasks that have a different
distribution. In practice, demonstrations from new tasks will be continuously
observed and the data might be unlabeled or only partially labeled. Therefore,
it is desirable for the trained model to adapt to new tasks that have limited
data samples available. In this work, we build an adaptable imitation learning
model based on the integration of Meta-learning and Adversarial Inverse
Reinforcement Learning (Meta-AIRL). We exploit the adversarial learning and
inverse reinforcement learning mechanisms to learn policies and reward
functions simultaneously from available training tasks and then adapt them to
new tasks with the meta-learning framework. Simulation results show that the
adapted policy trained with Meta-AIRL can effectively learn from limited
number of demonstrations, and quickly reach the performance comparable to that
of the experts on unseen tasks.

##  I Introduction

Learning from demonstrations has gained a lot of popularity in decision-making
and control tasks in a number of domains such as gaming, human-computer
interactions, robotics, and self-driving vehicles. Commonly used methods
include Imitation Learning (IL) [1] [2], Inverse Reinforcement Learning (IRL)
[3] [4], Generative Adversarial Imitation Learning (GAIL) [5], Adversarial
Inverse Reinforcement Learning (AIRL) [6] [7], etc. These methods do not
require designing a reward function manually that can be hard for complex
tasks, but they generally do need an abundance of demonstrations in order to
mimick the demonstrated behaviors. Furthermore, the learned behavior usually
works only in that specific task environment and fails to generalize to new
tasks with different distributions. In reality, it is usually the case that we
continuously enrich the dataset by collecting data from new tasks or
environments. For example, to learn an automated lane-change behavior, we may
train our vehicle agent with thousands or even millions of labeled driving
demonstrations from different cities or countries, but these demonstrations
may not cover all the possible situations and we may still have new data
obtained from other locations that are not originally included in our training
dataset. In this situation, it is labor intensive and costly to keep labeling
all the newly acquired data and retrain the model from scratch again.
Therefore, it is essential to have a model that can make good use of the
knowledge learned from existing tasks and generalize quickly to new tasks with
limited data samples.

There have been a number of studies that applied meta-learning to decision-
making and control tasks, such as Meta-Reinforcement Learning [8] [9], Meta-
Inverse Reinforcement Learning [10] [11], Meta-DAgger [12], etc. These studies
target on either policy learning or reward function learning. For a decision-
making and control task, what we ultimately prefer is a policy that maps
states to actions for maneuvering the agent to complete a task, but we may
still want a reward function that is considered as a succinct, robust and
transferable representation of a task [13]. Some of the learning from
demonstrations methods, e.g. Adversarial Inverse Reinforcement Learning (AIRL)
[6], can simultaneously recover a policy and a reward function from expert
demonstrations for single task. In this work, we propose a framework to
combine Meta-learning and Adversarial Inverse Reinforcement Learning to learn
the model initialization that can be quickly adapted to new situations with
limited data.

Our contributions in this work are as follows: 1) We proposed a general Meta-
AIRL algorithm that can efficiently generalize both of the learned policy and
reward function to new tasks. 2) We applied the proposed method to the
decision-making tasks in autonomous driving domain with the consideration that
such an application is challenging as the learning agent needs to dynamically
interact with adjacent agents to make proper actions.

The rest of the paper is organized as follows. In Section 2, we present
related work. Section 3 provides details on the formulation of the Meta-AIRL
methodology. Experiments and results are given in Section 4. Section 5
concludes this paper.

##  II Related Work

###  II-A Learning from Demonstrations

There has been a number of studies focusing on learning from
demonstrations.Pure Behavior Cloning [1] suffers from the dilemma of
distribution shift that leads to the failure of issuing correct actions when
the states are out of the training distribution. DAgger [2] solves the problem
by introducing a human expert or an oracle to give corrective labels for some
states that are not included in the collected data. However, human
intervention in deployment is troublesome in many practical settings.
Generative Adversarial Imitation Learning (GAIL) [5] is proposed to learn a
policy in an adversarial way by involving a discriminator and a generator
(i.e. the policy). It saves the effort of inquiring a human annotation but
uses a discriminator for distinguishing the expert data and the generated
data. A limitation is that GAIL does not recover a reward function which is
generally considered robust over different environments. Adversarial Inverse
Reinforcement Learning (AIRL) [6] formulates the discriminator in a special
form instead of directly using neural network output, which enables AIRL to
learn both the policy and reward function simultaneously.

###  II-B Meta-learning

Meta-learning, also known as learning to learn, is an approach to adapt
learned models to novel settings by exploiting the inherent structural
similarities across a distribution of tasks. Meta-learning can be metrics
based [14] [15], model based [16], or optimization based [16] [17] [18].
Optimization based meta-learning is a powerful approach that adjusts the
optimization algorithm itself for fast learning. For example, Model-agnostic
Meta-learning (MAML) [17] learns a good parameter initialization by performing
one-step unrolling only. First-order MAML (FOMAML) and REPTILE [18] algorithms
learns the initialization by looking ahead multiple gradient steps but ignores
second order derivatives. The learnt initialization by these methods encode
common knowledge among different tasks and allows efficient adaptation in only
a few gradient steps.

###  II-C Integration of Meta-learning and Learning from Demonstrations

Some studies have explored integrating Meta-learning and learning from
demonstrations methods for decision-making and control tasks. One study is
Meta-IRL, which combines Meta-learning and IRL to adapt the learned reward
function to new tasks. In the studies of [10] [19], Meta-IRL has been applied
to solve problems with discrete tabular settings, while in the study of [11],
the authors extend the standard IRL framework to include latent variables and
learn an adaptable reward function in an unsupervised way. The approach has
been applied to continuous control tasks in Mujoco environments [20]. Xu. et
al. [10] and Yu. et al. [11] leveraged Meta-IRL to learn prior distributions
of the tasks. These approaches have been generally applied to simulated game
environments where the background is static and no interactions between agents
are involved. It can be intractable to model the distribution of tasks for
highly dynamic environments such as a driving domain.

Autonomous driving is a much more challenging task in terms of the dynamically
changing environment and complex interactions with surrounding agents.
Recently, a couple of studies have explored to apply meta-learning in this
domain. [12] proposed Meta-DAgger to improve the generalization of the learned
policy in a simulated environment called TORCS. It involves a human or an
oracle in the loop which limits the application in the real world. [21] is
another work that integrated a policy iteration based RL into the meta-
learning pipeline, and was tested for lane-keeping task in a simulated
environment in CARLA. It requires the access to a known reward function. Our
work aims to learn both a policy and a reward function that can be effectively
adapted to new tasks by learning from limited demonstrations, and we target on
more complicated decision-making problems under dynamic environments where the
learning agent intensively interacts with its surrounding agents.

##  III Meta-Adversarial Inverse Reinforcement Learning

###  III-A Preliminaries

####  III-A1 Adversarial Inverse Reinforcement Learning

Adversarial Inverse Reinforcement Learning [6] builds on Adversarial Learning
and maximum causal entropy Inverse Reinforcement Learning framework (IRL)
[22]. It introduces a discriminator to obtain the formulation of the reward
function. The optimization in AIRL is similar to that in GAN [23] where the
discriminator and generator are updated in an adversarial way. The difference
is that AIRL takes a special form of the discriminator $D_{\omega}(s,a)$
instead of directly using the output of the neural network $f_{\omega}(s,a)$
as the discriminator value. The discriminator is given as:

$D_{\omega}(s,a)=\frac{\exp(f_{\omega}(s,a))}{\exp(f_{\omega}(s,a))+\pi(a|s)}$
(1)

where $s$ is the state, $a$ is the action, $\omega$ is the discriminator’s
parameter, and $\pi$ is the updated policy.

####  III-A2 Meta Learning

Meta-learning involves a meta-learner and a learner. The learner learns the
model $f_{\theta_{T_{i}}}$ from individual tasks $T_{i}$ in an inner loop,
while the meta-learner trains the learner to get an overall common structure
$f_{\theta}$ over a set of training tasks $T=\\{T_{i}|i=1,...,N\\}$ in an
outer loop.

In our study, we leverage REPTILE pipeline as it does not unroll a computation
graph or calculate any second derivatives. This feature facilitates the
convenience of performing multiple gradient steps on the training tasks in the
inner loop. More importantly, it allows us to apply different update frequency
for the discriminator and the generator.

###  III-B Meta-Adversarial Inverse Reinforcement Learning

####  III-B1 Loss Definition

In our study, we use the cross-entropy loss $L_{D}(\omega)$ in Equation (2) as
the objective of the discriminator that performs a binary classification task.
We label the expert data as $1$ and the generated data as $0$. Instead of
using the full trajectory as input to the discriminator which might result in
high variance, we input single state-action pairs $(s,a)$ at individual time
steps to the discriminator, which has been proved more stable in learning [6].

$L_{D}(\omega)=E_{(s,a)\sim\pi_{E}}[-\log D_{\omega}(s,a)]\\\
+E_{(s,a)\sim\pi_{\phi}}[-\log(1-D_{\omega}(s,a))]$ (2)

The generator represents the action policy of the agent whose optimization is
based on a reward function. In our formulation, the reward function in
Equation (3) is built upon the outcome of the discriminator and is considered
as the connection between the discriminator and generator. The functionality
of the reward function is to score high values for the generated data that
confused the discriminator.

$r(s,a)=\log(D_{\omega}(s,a))-\log(1-D_{\omega}(s,a))$ (3)

The objective of the generator is to generate trajectories as much similar as
the expert demonstrations. That is achieved by maximizing the total rewards
accumulated in an episode or up to a horizon $H$ in the policy optimization
procedure. Actually, such a policy optimized is equivalent to an entropy
regularized policy.

$\displaystyle-L_{G}(\phi)=$ $\displaystyle
E_{\pi_{\phi}}[\sum_{t=0}^{H}(\log(D_{\omega}(s_{t},a_{t}))-\log(1-D_{\omega}(s_{t},a_{t})))]$
$\displaystyle=$ $\displaystyle
E_{\pi_{\phi}}[\sum_{t=0}^{H}(f_{\omega}(s_{t},a_{t})-\log\pi(a_{t}|s_{t}))]$
(4)

####  III-B2 Meta Optimization

Within meta-training, we sample $N$ training tasks $\\{T_{i}|i=1,...,N\\}$
from the distribution $p(T)$. Each decision-making task include $K$ expert
demonstrations, $S_{T_{i}}=\\{\tau_{1},...,\tau_{K}\\}$, where each
demonstration $\tau_{k}$ is a sequence of state and action pairs
$(s,a)_{t},t\in\\{1,...,H\\}$.

In our study, the inner loop neural network in the meta-learning structure
consists of two components, the discriminator and the generator, i.e., the
parameters in the meta-learning model includes parameters from the two
individual neural networks $\theta=\\{\omega,\phi\\}$. The loss of the overall
model also includes two parts, $L=\\{L_{D}(\omega),L_{G}(\phi)\\}$. For the
update in the inner loop, we use ADAM optimizer for the discriminator and
Trust Region Policy Optimization (TRPO) for the generator, which are
consistent with the AIRL and GAIL methods.

$\displaystyle\frac{\partial L_{D}(\omega)}{\partial\omega}=$ $\displaystyle
E_{(s,a)\sim\pi_{E}}[-\nabla_{\omega}\log(D_{\omega}(s,a))]$
$\displaystyle+E_{(s,a)\sim\pi_{\phi}}[-\nabla_{\omega}\log(1-D_{\omega}(s,a))]$
(5) $\displaystyle\frac{\partial
L_{G}(\phi)}{\partial\phi}=E_{(s,a)\sim\pi_{\phi}}[$
$\displaystyle\nabla_{\phi}\log\pi_{\phi}(a|s)(\log D_{\omega}(s,a)$
$\displaystyle-\log(1-D_{\omega}(s,a)))]$ (6)

Note that the discriminator is used to provide reward signals to the
generator, so it will be beneficial to have a good discriminator as soon as
possible. Therefore, we use high update frequency $k_{D}$ for the
discriminator and low frequency $k_{G}$ for the generator.

In the outer loop, the model weights update is as follows:

$\omega\leftarrow\omega+\beta_{\omega}\frac{1}{N}\sum_{i=1}^{N}(\omega_{T_{i}}-\omega),\phi\leftarrow\phi+\beta_{\phi}\frac{1}{N}\sum_{i=1}^{N}(\phi_{T_{i}}-\phi)$
(7)

where $\omega_{T_{i}}$ and $\phi_{T_{i}}$ are the updated weights for the
discriminator and the generator in the task $T_{i}$,
$\beta=\\{\beta_{\omega},\beta_{\phi}\\}$ are the meta learning rates. Similar
to update frequencies, we set $\beta_{\omega}>\beta_{\phi}$, which gives
better training stability.

In our study, the data used for the discriminator update consists of two sets,
an expert dataset $\mathcal{S}^{E}$ that is collected from simulated expert
demonstrations and a generated dataset $\mathcal{S}^{G}$ that is from the
generator under the current policy $\pi_{\phi}$. Each episode,
$\tau=\\{(s_{1},a_{1}),...,(s_{H},a_{H})\\}$, includes a sequence of state-
action pairs of $H$ steps that might vary in different episodes in our study.
The overall algorithm is given in Algorithm 1.

Algorithm 1 Meta Adversarial IRL

1:Initialize $\theta=\\{\omega,\phi\\}$, $\omega$: parameters of the
discriminator, $\phi$: parameters of the policy

2:for iteration = $1,...,M$ do

3: Sample training tasks $T_{i}\sim p(T)$, $i\in\\{1,2,...,N\\}$

4: for all tasks $T_{i}$ do

5: Obtain expert demos $\mathcal{S}_{T_{i}}^{D}$

6: for update = $1,2,...,K$ do

7: Obtain generated demos $\mathcal{S}_{T_{i}}^{G}$ under $\pi_{\phi_{T_{i}}}$

8: Calculate $L_{D}(\omega_{T_{i}})$ with $\mathcal{S}_{T_{i}}^{D}$ and
$\mathcal{S}_{T_{i}}^{G}$

9: Update discriminator parameters
$\omega_{T_{i}}\leftarrow\omega_{T_{i}}-\alpha_{D}\nabla_{\omega}L_{D}(\omega_{T_{i}})$
for $k_{D}$ iterations

10: Calculate reward $r_{T_{i}}$ with $\mathcal{S}_{T_{i}}^{G}$ and
$D_{\omega_{T_{i}}}$

11: Calculate $L_{G}(\phi_{T_{i}})$ with $\mathcal{S}_{T_{i}}^{G}$ and
$r_{T_{i}}$

12: Update policy parameters
$\phi_{T_{i}}\leftarrow\phi_{T_{i}}-\alpha_{G}\nabla_{\phi}L_{G}(\phi_{T_{i}})$
for $k_{G}$ iterations

13: end for

14: Obtain parameters $\theta_{T_{i}}=\\{\omega_{T_{i}},\phi_{T_{i}}\\}$

15: end for

16: Update
$\theta\leftarrow\theta+\beta\frac{1}{N}\sum_{i=1}^{N}(\theta_{T_{i}}-\theta)$

17:end for

##  IV Experiments

###  IV-A Application Case

We test our proposed method on decision-making tasks for lane-change scenarios
in autonomous driving. The task is to decide when and where to make a lane-
change maneuver. For example, when a vehicle receives a lane-change command
from a route navigation module, our proposed method is to tell the vehicle at
what time and to which vehicle gap it should make the lane change maneuver.

It is common that the expert demonstrations are collected by drivers with
different personalities and in different regions. Particularly, in terms of
the decision-making task, different driving styles show different preferences
of vehicle merging gaps, safety distance, maximum/minimum accelerations, etc.,
resulting in different data distributions in the states and actions. The
driving tasks in our study are considered drawn from such a distribution of
different driving styles. As most off-the-shelf simulators have not provided
the functionality of conveniently simulating diverse driving behaviors, we
develop a new platform with oracle modules to simulate expert driving in
multiple styles. The demonstrations include various behaviors, such as
yielding behavior where the ego vehicle waits for a safety gap to merge in,
overtaking behavior where the ego vehicle accelerates to merge to a gap in
front of it on the adjacent lane, and aborting behavior where the ego vehicle
aborts the lane changing when it detects potential collisions measured by a
safety margin. In this study, we take the conservative and neutral driving
styles as the meta-training tasks and the challenging style (aggressive
driving) as the meta-testing task to check whether the generalized model
really learns the encoded structure across tasks or just performs an average
over tasks.

As decisions are generally considered as discrete, we design the action space
as discrete by joining the decisions on the lateral and longitudinal
directions. Specifically, the longitudinal decision decides which vehicle gap
to merge into and the lateral decision decides whether to make the lateral
movement right now. An illustration of the simulated scenarios is shown in
Figure 1.

The state space incorporates vehicle kinematic information of the ego vehicle
and its surrounding vehicles. It includes information such as vehicle
positions, speeds, accelerations, lane ids, etc., which constitute a
44-dimension state space. More experiment details are given in the next
subsection.

Figure 1: An illustration of a simulated scenario. The learning agent (in
yellow) interacts with its adjacent vehicles (in blue) and decides which
vehicle gap (in yellow) to merge into and whether to make the lane change
right now (in red).

###  IV-B Experiment Details

For the two meta-training tasks, i.e. conservative and neutral driving styles,
each has 3000 demonstrations available for training, while the meta-testing
task, i.e. aggressive driving task, only has access to a limited number of
demonstrations such as $\\{5,10,..,50\\}$.

As mentioned in III-B, the discriminator is trained with higher update
frequency than the generator. We fine-tune this hyperparameter with the meta-
training tasks and find the optimal numbers of iterations are $k_{D}=50$ for
the discriminator and $k_{G}=1$ for the generator respectively. Also, for the
meta learning rate in the outer loop, we fine-tune it and use
$\beta_{\omega}=0.5$ for the discriminator and $\beta_{\phi}=0.25$ for the
generator. The meta-training process is conducted for 2500 iterations. In
meta-testing, we test the generalization performance with different number of
available demonstrations, i.e. $\\{5,10,...,50\\}$. For each case, we conduct
10 update iterations upon the model learned from meta-training.

Figure 2: Performance of the discriminator (left and middle graphs) and the
generator (right graph). The left and middle graphs display the classification
probabilities of the expert data and the generated data respectively from the
discriminator. The high values in the experts and low values in the generator
in early episodes (x-axis) indicate that the discriminator is able to
distinguish the experts from the generator well. The values then go to around
0.5 at convergence for both the expert data and generated data as desired due
to the adversarial effect with the generator. The right graph show the
accumulated total rewards over training episodes. The increasing and
plateauing trend indicates the improved learning ability of the generator.
(Blue and green curves represent the meta-training tasks, and the red curve
represents the online-testing results of the meta-testing task.) Figure 3:
Driving performance. The left and right graphs depict the agent’s maneuvering
performance in training via the roll-out steps and decision-making steps. The
agents takes shorter and more stable time to make lane changes after trained
for hundreds of episodes. The right graph displays the ratio curves of
successful lane-change episodes over all experimenting episodes. The values
are close to 1 after convergence, indicating that the agent can always make
successful lane changes when requested. Figure 4: Vehicle kinematic
performance in maximum acceleration (left graph), minimum acceleration (middle
graph), and maximum speed (right graph). The distinguishable curves in the
three graphs indicate that the agent has learned different driving
characteristics. Furthermore, the aggressive style (in red) shows higher
values in maximum acceleration and maximum speed, and lower negative values in
minimum acceleration, indicating that the meta-training procedure indeed
encodes the features of different driving behaviors rather than just
performing an average over them. Figure 5: Testing performance of three
learning models. Our Meta-AIRL model (in red) shows higher rewards and episode
success ratio than the other two baselines (the pretrained model in blue and
the learning-from-scratch AIRL model in green), along with the increase of
available samples (x-axis). It achieves the satisfactory generalization
performance with only about 10 demonstrations from the meta-testing task,
indicating the effectiveness of the fast adaptation of the proposed model.
Figure 6: Histograms of four driving kinematics (maximum acceleration, maximum
speed, minimum acceleration, and minimum speed) in testing for three learned
models and the expert. The distributions of the four metrics in the Meta-AIRL
model (red bars) are much closer to the expert distributions (black bars) than
those of the other two models (blue and green bars).

###  IV-C Evaluation Metrics

We assess the effectiveness of the proposed method in four different aspects:
the discriminator performance, the generator performance, the driving
performance, and the vehicle kinematic performance. Within each aspect, we
specify some metrics in detail.

Discriminator Performance. The discriminator performance indicates the
capability of distinguishing the expert data from the generated data. For a
good discriminator, the value of $D_{\omega}(s_{E},a_{E})$, where
$(s_{E},a_{E})$ is from expert dataset $\mathcal{S}^{E}$, should be as high as
$1$ whereas the value of $D_{\omega}(s_{G},a_{G})$, where $(s_{G},a_{G})$ is
from $\mathcal{S}^{G}$, should be as low as $0$ (Remember that we label expert
data as $1$ and generated data as $0$). When trained with the generator, at
optimal, the discriminator should output $0.5$ for both
$D_{\omega}(s_{E},a_{E})$ and $D_{\omega}(s_{G},a_{G})$.

Generator Performance. The generator’s capability is illustrated by the
accumulated rewards in the roll-out episodes calculated by Equation (3). The
larger the accumulated value is, the better the performance is.

Driving Performance. We use three metrics to evaluate the driving performance.
Specifically, the roll-out step represents the duration of an episode before
its termination (e.g. a crash, a prolonged driving, or a successful lane
change). The decision-making step measures the duration of the decision-making
process in an episode (e.g. how much time it uses to make the final decision).
The episode success rate is the successful episodes over the total number of
experimenting episodes. The value of the first two metrics should stay steady
when the agent has learned the lane-change behavior, and the success rate
should be as high as $1$ at optimal.

Vehicle Kinematic Performance. To further explore the features of different
driving styles, we evaluate some vehicle kinematics such as the maximum
acceleration, the minimum acceleration, and the maximum speed, with the
consideration that these metrics are representative to distinguish different
habits. Ideally, they should be in different but stable ranges for different
driving styles.

###  IV-D Results

In this subsection, we show the meta-training results in Figure 2, 3, and 4,
and the meta-testing results in Figure 5 and 6. In meta-training, we plot the
performance curves of the two meta-training tasks as well as the online-
testing curve of the meta-testing task adapted upon the current model
parameters. In meta-testing, we compare the generalization performance of our
model with two baselines. One is a pretrained model that is trained with all
training tasks and then fine-tuned on the meta-testing task. This comparison
is to show that the model from the meta-training phase does encode the
patterns of different training tasks instead of just being integrated as an
averaged model. The other baseline is a learning-from-scratch model that is
trained based on AIRL on the meta-testing task with randomly initialized
parameters. This comparison is to show how fast the our Meta-AIRL model can
adapt to a satisfactory level.

####  IV-D1 Meta-training Results

In Figure 2, the left and middle graphs show the probability curves of the
discriminator. As mentioned earlier, a well-trained discriminator should
output high probability values for expert data in its early stage as we use a
high update frequency for it, and then goes down to 0.5 at optimal due to the
adversarial effect from the generator, vice versa for the probability of the
generated data. These two graphs in Figure 2 satisfactorily show this trend.

The generator’s performance is reflected by the total reward curve in the
right graph in Figure 2. The increasing and plateauing trend of the total
rewards indicates the improved learning ability on the driving task.

Figure 3 shows the driving performance which is represented by three metrics.
The rolling-out steps in the left graph and decision-making steps in the
middle graph show that the agent takes a long time to make lane changes in
early episodes, but leans to make stable performance with fewer steps after
trained for hundreds of episodes. The distinguishable curves in these two
graphs represent different styles, indicating that the meta-training procedure
does encode the characteristics of different tasks instead of just simply
averaging over tasks. Furthermore, the online testing curves in red show that
the task execution duration for aggressive drivers is shorter than that of
conservative and neutral style drivers which is in line with our expectation.

The episode success ratio of the three driving styles is shown in the right
graph in Figure 3. The curves increase quickly from low values to high ones
and are quite close to 1, indicating that the trained agent can always make
successful and acceptable lane-change decisions when requested.

Figure 4 displays the vehicle kinematic performance of the driving styles in
three metrics, i.e. the maximum acceleration, minimum acceleration, and
maximum speed. The distinguishable curves indicate that the agent does learn
different driving characteristics of different styles, with different value
ranges for their corresponding styles. More importantly, the aggressive style
shows higher values in maximum acceleration and maximum speed, and lower
values (in negative) in minimum acceleration. This further verifies that the
trained model indeed encodes the features of different driving behaviors
instead of just performing an average over them.

####  IV-D2 Meta-testing Results

In meta-testing, we fine-tune the meta-trained model on the meta-testing task
with different numbers of limited demonstrations, i.e. $\\{5,10,15,...,50\\}$,
separately, to check how well the model would be adapted when it has different
data accessibility. The baseline models are also fine-tuned (for the
pretrained baseline model) or trained (for the learning-from-scratch (AIRL)
model) with the same numbers of demonstrations. The performance of the model
is evaluated with 300 episodes rolled out in the meta-testing environment. The
comparisons are shown in Figure 5 and 6.

Figure 5 displays the total rewards (left graph) and the success ratios (right
graph) of the three learning methods. It is easy to observe that the Meta-AIRL
model (red curves) performs much better than the other two baselines (blue and
green curves): its total reward curve goes up much faster and stays higher,
and its episode success ratio curve also rises up faster and is closer to 1.
Such a good performance is achieved with only about 10 expert demonstrations
through adaptation.

Figure 6 shows the histograms of four driving kinematics, i.e. maximum
acceleration, maximum speed, minimum acceleration, and minimum speed, of the
expert data and the testing results of the three learning methods. As the
number of test cases (300 tests) of the three trained models is different from
that of the expert (3000 demonstrations), to make a fair comparison, we divide
the bin’s raw count by its corresponding total number of counts and the bin
width, which is marked as y-axis. X-axis represents the metric values. The
graphs visually show that the distributions of all of the four metrics in the
Meta-AIRL model (red blocks) are much closer to the expert distributions
(black blocks) when compared with the other two baselines (green and blue
blocks).

The quantitative difference between the histogram from each learnt model and
that from the expert is summarized in Table I. The deviation is measured by
$l_{1}$ distance and calculated with values on y-axis. We can observe that
Meta-AIRL has lower deviation values which confirms that Meta-AIRL compares
favorably with the other two. Therefore, our Meta-AIRL model can faithfully
recover the expert behavior with limited number of samples for challenging
novel tasks.

TABLE I: Comparison of three approaches in terms of the deviation of the learned distribution from the expert distribution. The deviation is measured by the $l_{1}$ distance between the histograms. Metrics | Meta-AIRL | Pretrain model | AIRL model
---|---|---|---
max_acce | 0.32 | 0.48 | 0.83
max_speed | 0.08 | 0.18 | 0.27
min_acce | 0.30 | 0.41 | 0.42
min_speed | 0.15 | 0.28 | 0.33

##  V Conclusion

In this work, we propose a framework (Meta-AIRL) to integrate Meta-learning
and Adversarial Inverse Reinforcement Learning for fast adaptation of the
learned model to new tasks. The model learns both the policy and reward
function simultaneously from demonstrations by invoking a discriminator and a
generator, and adapts quickly to new tasks with limited data samples by using
different update frequencies and meta-learning rates for the discriminator and
the generator.

The proposed model has been applied to the challenging decision-making task in
the autonomous driving domain where the learning vehicle intensively interacts
with surrounding agents. Meta-training results show that the agent indeed
learns the inherent features of different driving styles instead of just
performing an average over tasks. The comparison of Meta-AIRL with other
baselines in the meta-testing results show that our model can fast adapt to
new tasks with limited demonstrations and achieve satisfactory results
comparable to those of the experts.

## References

  * [1] M. Bojarski, D. Del Testa, D. Dworakowski, B. Firner, B. Flepp, P. Goyal, L. D. Jackel, M. Monfort, U. Muller, J. Zhang, _et al._ , “End to end learning for self-driving cars,” _arXiv preprint arXiv:1604.07316_ , 2016.
  * [2] S. Ross, G. Gordon, and D. Bagnell, “A reduction of imitation learning and structured prediction to no-regret online learning,” in _Proceedings of the fourteenth international conference on artificial intelligence and statistics_ , 2011, pp. 627–635.
  * [3] A. Y. Ng, S. J. Russell, _et al._ , “Algorithms for inverse reinforcement learning.” in _Icml_ , vol. 1, 2000, p. 2.
  * [4] B. D. Ziebart, A. L. Maas, J. A. Bagnell, and A. K. Dey, “Maximum entropy inverse reinforcement learning.” in _Aaai_ , vol. 8. Chicago, IL, USA, 2008, pp. 1433–1438.
  * [5] J. Ho and S. Ermon, “Generative adversarial imitation learning,” in _Advances in neural information processing systems_ , 2016, pp. 4565–4573.
  * [6] J. Fu, K. Luo, and S. Levine, “Learning robust rewards with adversarial inverse reinforcement learning,” _arXiv preprint arXiv:1710.11248_ , 2017\.
  * [7] P. Wang, D. Liu, J. Chen, H. Li, and C.-Y. Chan, “Human-like decision making for autonomous driving via adversarial inverse reinforcement learning,” _arXiv preprint arXiv:1911.08044_ , 2019.
  * [8] J. X. Wang, Z. Kurth-Nelson, D. Tirumala, H. Soyer, J. Z. Leibo, R. Munos, C. Blundell, D. Kumaran, and M. Botvinick, “Learning to reinforcement learn,” _arXiv preprint arXiv:1611.05763_ , 2016.
  * [9] Z. Xu, H. P. van Hasselt, and D. Silver, “Meta-gradient reinforcement learning,” in _Advances in neural information processing systems_ , 2018, pp. 2396–2407.
  * [10] K. Xu, E. Ratner, A. Dragan, S. Levine, and C. Finn, “Learning a prior over intent via meta-inverse reinforcement learning,” _arXiv preprint arXiv:1805.12573_ , 2018.
  * [11] L. Yu, T. Yu, C. Finn, and S. Ermon, “Meta-inverse reinforcement learning with probabilistic context variables,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 11 749–11 760.
  * [12] A. E. Sallab, M. Saeed, O. A. Tawab, and M. Abdou, “Meta learning framework for automated driving,” _arXiv preprint arXiv:1706.04038_ , 2017.
  * [13] P. Abbeel and A. Y. Ng, “Apprenticeship learning via inverse reinforcement learning,” in _Proceedings of the twenty-first international conference on Machine learning_ , 2004, p. 1.
  * [14] O. Vinyals, C. Blundell, T. Lillicrap, D. Wierstra, _et al._ , “Matching networks for one shot learning,” in _Advances in neural information processing systems_ , 2016, pp. 3630–3638.
  * [15] F. Sung, Y. Yang, L. Zhang, T. Xiang, P. H. Torr, and T. M. Hospedales, “Learning to compare: Relation network for few-shot learning,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 1199–1208.
  * [16] S. Ravi and H. Larochelle, “Optimization as a model for few-shot learning,” 2016\.
  * [17] C. Finn, P. Abbeel, and S. Levine, “Model-agnostic meta-learning for fast adaptation of deep networks,” in _Proceedings of the 34th International Conference on Machine Learning-Volume 70_. JMLR. org, 2017, pp. 1126–1135.
  * [18] A. Nichol, J. Achiam, and J. Schulman, “On first-order meta-learning algorithms,” _arXiv preprint arXiv:1803.02999_ , 2018.
  * [19] A. Gleave and O. Habryka, “Multi-task maximum entropy inverse reinforcement learning,” _arXiv preprint arXiv:1805.08882_ , 2018.
  * [20] E. Todorov, T. Erez, and Y. Tassa, “Mujoco: A physics engine for model-based control,” in _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2012, pp. 5026–5033.
  * [21] Y. Jaafra, A. Deruyver, J. L. Laurent, and M. S. Naceur, “Context-aware autonomous driving using meta-reinforcement learning,” in _2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA)_. IEEE, 2019, pp. 450–455.
  * [22] B. D. Ziebart, “Modeling purposeful adaptive behavior with the principle of maximum causal entropy,” 2010.
  * [23] A. Radford, L. Metz, and S. Chintala, “Unsupervised representation learning with deep convolutional generative adversarial networks,” _arXiv preprint arXiv:1511.06434_ , 2015.