Detecting changes in distributions in large-scale streaming data

Thumbnail Image

Files

isbn9789526427485.pdf (2.8 MB)

URL

Journal Title

Journal ISSN

Volume Title

School of Electrical Engineering | Doctoral thesis (article-based) | Defence date: 2025-10-17
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2025

Department

Informaatio- ja tietoliikennetekniikan laitos
Department of Information and Communications Engineering

Major/Subject

Mcode

Degree programme

Language

en

Pages

103 + app. 105

Series

Aalto University publication series Doctoral Theses, 189/2025

Abstract

As modern technological systems generate increasingly large volumes of streaming data, the ability to analyze information and take actions in real time is essential. A key challenge in sequential signal processing and data analysis is the detection of rapid changes or anomalies in the statistical properties of data. It has applications in a variety of branches of engineering, such as wireless communications, sensor networks, radar, power grid, environmental monitoring and the Internet of Things. Effective real-time monitoring for changes is crucial for situational awareness, adaptation, and even security. The problem of real-time change detection in streaming data is known as a quickest change detection (QCD) problem. The fundamental goal is to detect changes as quickly as possible, subject to a constraint on the rate of false alarms. While the change detection problem has been extensively studied especially with regard to univariate time-series, the large-scale and multistream nature of modern applications present new challenges that are addressed in this thesis. First, we consider change detection when the distribution of the data after the change depends on a high-dimensional unknown parameter vector. In this setting, typical methods experience performance degradation since the high-dimensional parameter is difficult to estimate accurately in real time. We propose new methods that utilize the James-Stein shrinkage estimator to obtain better estimates of the parameter vector and show that substantial performance improvements are obtained when detecting a mean-shift in high-dimensional Gaussian data. Performance gains are shown analytically in both asymptotic and finite sample regimes, and in simulations. The direction of the shrinkage can be selected by the user, and it may depend on the observed data. It is shown, that the magnitude of the performance gain depends on the distance between the shrinkage target and the true post-change probability model. Second, we study the intersection of quickest change detection and multiple hypothesis testing. A centralized decision maker receives local decision statistics from a large number of sensors and runs multiple change detection tasks simultaneously, corresponding to e.g. different spatial locations or frequency bands. In this setting, conventional QCD error criteria developed for single stream settings may not capture the overall system performance accurately. We propose methods that provide control of the false discovery rate, a scalable and interpretable error criterion relevant to applications. In a Bayesian formulation, a method that minimizes average total detection delay subject to a constraint on the false discovery rate is derived. In addition, the proposed methods reduce the amount of data transmission between the sensors and the decision maker by adaptively choosing only a fraction of the sensors for monitoring at each time step. The thesis also contributes to detection problems involving spatially propagating phenomena that are observed with potentially mobile sensor networks. The objective is formulated as a dynamic programming problem and the structure of the optimal stopping rule is derived. We further propose a simpler, practically implementable threshold-based algorithm, that corresponds to a limiting form of the optimal test and establish its asymptotic optimality. The performance of the threshold test is studied when the data by the sensors corresponds to energy detector statistics, and in a scenario involving attenuation of propagating signals. Overall, the contributions of this thesis advance the theory and practical applicability of signal processing and change detection methods in large-scale, multi-stream environments, enabling more efficient and responsive monitoring and decision-making systems.

Modernit teknologiset järjestelmät synnyttävät jatkuvasti kasvavan määrän datavirtoja, joiden perusteella on kyettävä nopeaan ja tehokkaaseen päätöksentekoon. Keskeinen ongelma sekventiaalisessa signaalinkäsittelyssä ja data-analyysissä on äkkinäisten muutosten ja poikkeamien ripeä havaitseminen. Nopeiden muutosten ilmaisu on tärkeää esimerkiksi langattomissa tietoliikennejärjestelmissä, sensoriverkoissa, tutkasovelluksissa, sähköverkossa, ympäristön seurannassa ja esineiden internetissä (IoT). Tehokas reaaliaikainen muutosten seuranta on olennaista tilannetietoisuuden ja jopa turvallisuuden kannalta. Sekventiaalisessa muutoksenhavaintaongelmassa päätavoite on muutoksen mahdollisimman nopea havaitseminen, rajoittaen samalla väärien positiivisten päätösten (hälytysten) määrää toivoitulle tasolle. Vaikka muutoksenhavaintaongelmaa on tutkittu tutkimuskirjallisuudessa laajasti etenkin yksiulotteisten aikasarjojen osalta, modernit rinnakkaisia datavirtoja sisältävät korkeaulotteiset sovellukset tuovat osaltaan uusia haasteita, joita tämä väitöskirja käsittelee. Väitöstyön ensimmäisessä osassa kehitetään sekventiaalisen päätöksenteon menetelmiä muutoksenhavaintaan tilanteissa, joissa havaintojen muutoksen jälkeinen todennäköisyysjakauma riippuu tuntemattomasta korkeaulotteisesta parametrivektorista. Tällaisessa asetelmassa perinteisten menetelmien suorituskyky alenee, sillä korkeaulotteista parametrivektoria on vaikea estimoida tarkasti reaaliajassa. Työssä kehitetään menetelmiä jotka hyödyntävät James-Stein kutistusestimaattoria parametrivektorin estimointiin ja osoitetaan, että päätöksenteon suorituskykyä voidaan parantaa merkittävästi muutoksen tapahtuessa multinormaalijakauman keskiarvoparametrissa. Suorituskykyhyödyt todistetaan analyyttisesti sekä äärellisen otoksen tilanteessa että asymptoottisesti, ja vahvistetaan simulaatioissa. Menetelmän käyttäjä voi valita kutistuksen suunnan, tai se voidaan valita adaptiivisesti havaitun datan perusteella. Suorituskyvyn parannuksen suuruus riippuu kutistuskohteen ja oikean parametriarvon etäisyydestä. Toisessa osassa käsitellään muutoksenhavainnan ja monivertailuongelmien rajapintaa. Työssä tutkitaan tilannetta, jossa keskitetty päätöksentekijä vastaanottaa paikallisia testisuureita samanaikaisesti suurelta joukolta sensoreita ja suorittaa useita muutoksenhavaintatehtäviä rinnakkain, liittyen esimerkiksi radiospektrin tilaan. Tässä asetelmassa tyypillisesti käytetyt, yhden muuttujan tilanteisiin kehitetyt päätöksenteon kriteerit eivät välttämättä toimi toivotulla tavalla. Työssä esitetään menetelmiä, jotka kontrolloivat ennenaikaisten havaintojen osuutta kaikista muutoshavainnoista, mikä on kriteerinä skaalautuva ja käytännön sovelluksissa helposti tulkittava. Bayeslaisessa asetelmassa johdetaan menetelmä, joka minimoi keskimääräisen havaintoviiveen summan annettujen rajoitteiden puitteissa. Menetelmät vähentävät tiedonsiirtoa valitsemalla adaptiivisesti vain sensoreiden osajoukon seurantaan kullakin ajan hetkellä. Väitöskirjan viimeinen kontribuutio liittyy tilanteisiin, joissa avaruudellisesti eteneviä ilmiöitä monitoroidaan liikkuvilla sensoriverkoilla. Päätöksentekotavoite muotoillaan dynaamisen ohjelmointiongelman ratkaisuna, ja optimaalisen havainta-algoritmin muoto johdetaan. Käytännön toteutuksia varten esitellään yksinkertaisempi kynnysarvoalgoritmi, joka vastaa optimaalisen menetelmän tiettyä raja-arvoa ja osoitetaan sen asymptoottinen optimaalisuus. Kynnysarvomenetelmän suorituskykyä tutkitaan tarkemmin astelmissa joissa sensorihavainnot vastaavat energiailmaisimia ja kun havaittava ilmiö vaimenee edetessään. Kokonaisuutena väitöskirjan kontribuutiot edistävät muutoksenhavainnan ja monen hypoteesin testauksen teoriaa, signaalinkäsittelyn menetelmiä ja sovellettavuutta monen datavirran ongelmissa, ja mahdollistavat tehokkaampien seuranta- ja päätöksentekojärjestelmienkehittämistä.

Description

Supervising professor

Koivunen, Visa, Prof., Aalto University, Department of Information and Communications Engineering, Finland

Keywords

quickest change detection, multiple hypothesis testing, signal processing, signal detection, shrinkage estimation, false discovery rate, nopea muutoksenhavainta, signaalien ilmaisu, monen hypoteesin testaus, sekventiaalinen päätöksenteko, kutistusestimointi

Other note

Parts

  • [Publication 1]: T. Halme, V. V. Veeravalli and V. Koivunen. Quickest Change Detection for Multiple Data Streams Using the James-Stein Estimator. Accepted for publication in IEEE Transactions on Information Theory, July 2025.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202508135961
    DOI: 10.1109/ICASSP49660.2025.10888034 View at publisher
  • [Publication 2]: T. Halme, V. V. Veeravalli and V. Koivunen. Quickest Change Detection of Unknown Mean-Shifts using the James-Stein Estimator. In ICASSP 2025 - 2025 IEEE International Conference on Acoustics, Speech and Signal Processing, April 2025.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202508135961
    DOI: 10.1109/ICASSP49660.2025.10888034 View at publisher
  • [Publication 3]: E. Nitzan, T. Halme, H.V. Poor and V. Koivunen. Deterministic Multiple Change-Point Detection with Limited Communication. In 2020 54th Annual Conference on Information Sciences and Systems (CISS), Princeton, NJ, USA, pp. 1-6, March 2020
  • [Publication 4]: T. Halme, E. Nitzan, H. V. Poor and V. Koivunen. Bayesian Multiple Change-Point Detection with Limited Communication. In ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Barcelona, Spain, pp. 5490-5494, March 2020.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202010025746
    DOI: 10.1109/TSP.2020.3016139 View at publisher
  • [Publication 5]: E. Nitzan, T. Halme and V. Koivunen. Bayesian Methods for Multiple Change-Point Detection with Reduced Communication. IEEE Transactions on Signal Processing, vol. 68, pp. 4871-4886, 2020.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202010025746
    DOI: 10.1109/TSP.2020.3016139 View at publisher
  • [Publication 6]: T. Halme and V. Koivunen. Optimal Multi-Stream Quickest Detection with False Discovery Rate Control. In 2023 57th Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, USA, pp. 877-881, October 2023.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202404243233
    DOI: 10.1109/IEEECONF59524.2023.10476984 View at publisher
  • [Publication 7]: T. Halme, E. Nitzan and V. Koivunen. Bayesian Multiple Change-Point Detection of Propagating Events. In ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Toronto, Canada, June 2021.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202301251488
    DOI: 10.1109/TSP.2022.3230334 View at publisher
  • [Publication 8]: T. Halme, E. Nitzan and V. Koivunen. Quickest Detection of Propagating Signals for Flexible Radio Spectrum Use. In 2021 55th Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, USA, pp. 805-810, October 2021.
    DOI: 10.1109/IEEECONF53345.2021.9723263 View at publisher
  • [Publication 9]: T. Halme, E. Nitzan and V. Koivunen. Bayesian Quickest Detection of Propagating Spatial Events. IEEE Transactions on Signal Processing, vol. 70, pp. 5982-5995, 2022.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202301251488
    DOI: 10.1109/TSP.2022.3230334 View at publisher

Citation

Permanent link to this item

https://urn.fi/URN:ISBN:978-952-64-2748-5

Collections

[diss] Sähkötekniikan korkeakoulu / ELEC