Algorithms for the multivariate change detection : extending the quantTree

Change detection has been a relevant research topic for decades, and change detection algorithms find application in numerous real-world domains, from industrial monitoring to healthcare, from security to finance. In practice, change detection problems consist of monitoring a stream of independent and identically distributed (i.i.d.) samples that initially follow a stationary distribution. The goal of a change detection algorithm is to detect when the process generating the stream drifts towards a different unknown post-change distribution. Indeed, the timely detection of distribution changes is crucial in real-world applications, as these changes might indicate faults in the monitored machinery or changes in the operating conditions and might require measures to counteract the drift. In this thesis, I solve the change detection problem by nonparametric algorithms, namely, assuming that both the stationary and post-change distributions are unknown. Depending on the application, the problem of detecting a change in a stream can be addressed in two manners: the batch-wise setting, where data are analyzed in fixed-size windows, and the online monitoring, where data are processed as a stream of continuous samples and are often associated with labels. In my research, I tackled both batch-wise and online monitoring problems. The main focus of my research on change detection has been extending the QuantTree algorithm, a solution based on a partitioning of the input space and supported by sound theoretical results. The main contributions of my work are the Kernel QuantTree (KQT) algorithm and the MultiModal QuantTree, each solving a specific limitation of QuantTree while generalizing its theoretical results. The histogram construction by QuantTree employs axis-aligned splits of the input space. For KQT, I designed a novel splitting rule based on measurable kernel functions, which produce finite-volume bins that better adhere to the data distribution. Moreover, I proved that the control of the FPR generalizes to this histogram construction algorithm. In particular, I have proposed three measurable quadratic functions and proved that the resulting KQT is invariant under roto-translations. Thanks to this property, KQT does not require classical preprocessing methods -- like PCA -- to achieve remarkable detection performance. Another limitation of QuantTree, common to all change detection algorithms, is the assumption that stationary data follow a single distribution. Such an assumption does not match many real-world scenarios where, in stationary conditions, the monitored process alternates between different normal operating settings, i.e., modalities. I formalized this multimodal change detection problem and solved it by MMQT, which uses a single modality-agnostic histogram to characterize the stationary distributions and computes modality-specific statistics for detecting changes. For the MMQT algorithm, I leveraged the theoretical properties of QuantTree to i) automatically estimate the number of modalities in a training set and ii) derive a principled calibration procedure that guarantees false-positive control. On top of these contributions to the batch-wise change detection, I also tackled the supervised online monitoring problem. The concept-drift detection problem is often associated with a classification task, and many solutions monitor the error rate of a classifier and detect distribution changes that harm the classification performance but ignore drifts that have little impact on the error rate, which are called virtual drifts. Other solutions monitor the stream distribution to detect any deviation from the stationary distribution, independently of the impact on related classification problems but ignore the supervision granted by the labels. To combine the supervised information with the distribution monitoring, I designed the Class-Distribution Monitoring (CDM) algorithm, which monitors the class-conditional distributions of a datastream by leveraging multiple instances of QT-EWMA -- an online monitoring algorithm based on QuantTree. CDM reports a concept drift after detecting a distribution change in any class, thus identifying which classes are affected by the concept drift. This information is precious for diagnostics and adaptation techniques, which can update only the part affected by the drift.

La Change Detection è stato un argomento di ricerca rilevante per decenni, e gli algoritmi di Change Detection trovano applicazione in numerosi settori del mondo reale, dal monitoraggio industriale alla sanità, dalla sicurezza alla finanza. In pratica, il problema di Change Detection consiste nel monitorare un flusso di dati indipendenti e identicamente distribuiti (i.i.d.) che seguono inizialmente una distribuzione stazionaria. L'obiettivo è quello di individuare quando il processo che genera i dati varia verso una diversa distribuzione sconosciuta. La tempestiva individuazione dei cambiamenti nella distribuzione dei dati è cruciale nelle applicazioni reali, poiché tali cambiamenti potrebbero indicare difetti nei macchinari monitorati o cambiamenti nelle condizioni operative, e potrebbero indicare la necessità di manutenzione. In questa tesi, risolvo il problema di Change Detection mediante algoritmi non parametrici, assumendo cioè che sia la distribuzione stazionaria che quella anomala siano sconosciute. A seconda dell'applicazione, il problema di Change Detection può essere affrontato in due modi: con un approccio batch-wise, dove i dati vengono analizzati in finestre di dimensioni fisse, e con un approccio online, dove i dati vengono elaborati come un flusso continuo e sono spesso associati a etichette. Nella mia ricerca, ho affrontato entrambi questi scenari. Il principale focus della mia ricerca nell'ambito della Change Detection è stato l'estensione dell'algoritmo QuantTree, una soluzione basata sul partizionamento dello spazio dei dati (un istrogramma) e supportata da solidi risultati teorici. I principali contributi del mio lavoro sono gli algoritmi Kernel QuantTree (KQT) e MultiModal QuantTree (MMQT), ciascuno dei quali risolve una specifica limitazione di QuantTree e generalizza i suoi risultati teorici. La costruzione dell'istogramma mediante QuantTree suddivide lo spazio con tagli allineati agli assi. Con KQT, ho introdotto un nuovo criterio di suddivisione basato su funzioni kernel misurabili, che producono partizioni di volume finito che si adattano meglio alla distribuzione dei dati. Inoltre, ho dimostrato che i risultati teorici che garantiscono il controllo del FPR si generalizzano a questo nuovo algoritmo di costruzione dell'istogramma. In questo lavoro, ho proposto e testato tre funzioni kernel e dimostrato che il KQT risultante è invariante rispetto alle rototraslazioni dei dati di addestramento. Grazie a questa proprietà, KQT non richiede metodi di preprocessing classici, come PCA, per ottenere buone prestazioni. Un'altra limitazione di QuantTree, comune a tutti gli algoritmi di Change Detection, è l'assunzione che i dati stazionari seguano una singola distribuzione. Tale assunzione non è valida in molti scenari reali in cui, in condizioni stazionarie, il processo monitorato varia tra diverse condizioni normali, o modalità. Ho formalizzato questo problema di Change Detection multimodale e l'ho risolto con MMQT, che utilizza un solo istogramma indipendente dalle singole modalità per caratterizzare le distribuzioni stazionarie. Inoltre, per rilevare i cambi di distribuzione, MMQT calcola statistiche specifiche ciascuna modalità. Nella progettazione di MMQT, ho sfruttato le proprietà teoriche di QuantTree per i) stimare automaticamente il numero di modalità in un set di addestramento e ii) derivare una procedura di calibrazione dell'istogramma che garantisce il controllo dei falsi positivi. Oltre a questi contributi alla Change Detection nello scenario batch-wise, ho affrontato anche il problema del monitoraggio online supervisionato. Il problema di Change Detection su flussi di dati è spesso associato a un problema di classificazione, ed infatti molte soluzioni monitorano la percentuale di errori di un classificatore per rilevare i cambiamenti nella distribuzione quando questi danneggiano le prestazioni della classificazione. Queste soluzioni però ignorano i cambiamenti che hanno poco impatto sul tasso di errore, detti virtuali. Altre soluzioni monitorano la distribuzione dei dati per rilevare qualsiasi tipo di deviazione dalla distribuzione stazionaria, indipendentemente dall'impatto su un problema di classificazione correlato ma ignorano le etichette associate ai dati. Per combinare le informazioni supervisionate con il monitoraggio della distribuzione, ho introdotto l'algoritmo di Class Distribution Monitoring (CDM), che monitora le distribuzioni condizionate alla classe di un insieme di dati sfruttando molteplici istanze di QT-EWMA -- un algoritmo di monitoraggio online basato su QuantTree. CDM segnala un cambio di distribuzione dopo aver rilevato cambiamenti nella distribuzione associate ad una qualsiasi classe, identificando così quali classi sono interessate dal cambio di distribuzione. Queste informazioni sono preziose per tecniche di diagnostica e per metodi che possono adattarsi al cambio di distribuzione limitatamente alla parte interessata dal cambio stesso.