Kernel QuantTree

Diego Stucchi, Paolo Rizzo, Nicolò Folloni, Giacomo Boracchi
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:32677-32697, 2023.

Abstract

We present Kernel QuantTree (KQT), a non-parametric change detection algorithm that monitors multivariate data through a histogram. KQT constructs a nonlinear partition of the input space that matches pre-defined target probabilities and specifically promotes compact bins adhering to the data distribution, resulting in a powerful detection algorithm. We prove two key theoretical advantages of KQT: i) statistics defined over the KQT histogram do not depend on the stationary data distribution $\phi_0$, so detection thresholds can be set a priori to control false positive rate, and ii) thanks to the kernel functions adopted, the KQT monitoring scheme is invariant to the roto-translation of the input data. Consequently, KQT does not require any preprocessing step like PCA. Our experiments show that KQT achieves superior detection power than non-parametric state-of-the-art change detection methods, and can reliably control the false positive rate.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-stucchi23a, title = {Kernel {Q}uant{T}ree}, author = {Stucchi, Diego and Rizzo, Paolo and Folloni, Nicol\`{o} and Boracchi, Giacomo}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {32677--32697}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/stucchi23a/stucchi23a.pdf}, url = {https://proceedings.mlr.press/v202/stucchi23a.html}, abstract = {We present Kernel QuantTree (KQT), a non-parametric change detection algorithm that monitors multivariate data through a histogram. KQT constructs a nonlinear partition of the input space that matches pre-defined target probabilities and specifically promotes compact bins adhering to the data distribution, resulting in a powerful detection algorithm. We prove two key theoretical advantages of KQT: i) statistics defined over the KQT histogram do not depend on the stationary data distribution $\phi_0$, so detection thresholds can be set a priori to control false positive rate, and ii) thanks to the kernel functions adopted, the KQT monitoring scheme is invariant to the roto-translation of the input data. Consequently, KQT does not require any preprocessing step like PCA. Our experiments show that KQT achieves superior detection power than non-parametric state-of-the-art change detection methods, and can reliably control the false positive rate.} }
Endnote
%0 Conference Paper %T Kernel QuantTree %A Diego Stucchi %A Paolo Rizzo %A Nicolò Folloni %A Giacomo Boracchi %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-stucchi23a %I PMLR %P 32677--32697 %U https://proceedings.mlr.press/v202/stucchi23a.html %V 202 %X We present Kernel QuantTree (KQT), a non-parametric change detection algorithm that monitors multivariate data through a histogram. KQT constructs a nonlinear partition of the input space that matches pre-defined target probabilities and specifically promotes compact bins adhering to the data distribution, resulting in a powerful detection algorithm. We prove two key theoretical advantages of KQT: i) statistics defined over the KQT histogram do not depend on the stationary data distribution $\phi_0$, so detection thresholds can be set a priori to control false positive rate, and ii) thanks to the kernel functions adopted, the KQT monitoring scheme is invariant to the roto-translation of the input data. Consequently, KQT does not require any preprocessing step like PCA. Our experiments show that KQT achieves superior detection power than non-parametric state-of-the-art change detection methods, and can reliably control the false positive rate.
APA
Stucchi, D., Rizzo, P., Folloni, N. & Boracchi, G.. (2023). Kernel QuantTree. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:32677-32697 Available from https://proceedings.mlr.press/v202/stucchi23a.html.

Related Material