Learning and adaptation to detect changes and anomalies in high-dimensional data

Monitoring a datastream to detect whether the incoming data departs from normal conditions is a problem encountered in many important applications, ranging from quality control in industrial process to health monitoring. Many solutions in the literature adopt a model that describes normal data and check whether this model is not able to describe new data, detecting anomalous instances or permanent changes affecting the data-generating process. Pursuing this approach is challenging when data have high dimensions or feature complex structures (as in case of images or signals), and these are the settings we consider in this thesis. We address this problem from two different perspectives. At first, we model data as realization of a random vector, i.e., we assume that data can be described by a smooth probability density function. In these settings we focus on the change-detection problem, where the goal is to detect permanent changes affecting the data-generating process. In particular, we prove the detectability loss phenomenon, namely that performance of a popular change-detection algorithm that monitors the likelihood decreases when the data dimension increases. We also propose QuantTree, a novel algorithm to define histograms as density models for high dimensional data that are perfectly suit for change detection purposes. In fact, we prove that adopting QuantTree leads to an important property, i.e., that the distribution of any statistic computed over histograms generated by QuantTree does not depend on the distribution of the data-generating process. This enables non-parametric monitoring of multivariate datastreams with any statistic. Our experiments also show that combining several histograms computed by QuantTree into an ensemble can effectively mitigate the detectability loss phenomenon. In the second part we focus on data that feature complex structures, that cannot be described by a smooth probability density function. We adopt dictionaries yielding sparse representations to characterize normal data and propose a novel anomaly-detection algorithm that detects as anomalous any data that do not conform to the learned dictionary. To make our anomaly-detection algorithm effective in practical application, we propose two domain adaptation algorithms that adapt the anomaly detector when the process generating normal data changes. The proposed algorithms have been successfully tested in two real world applications: a quality inspection system monitoring the production of nanofibrous materials through the analysis of Scanning Electron Microscope (SEM) images, and ECG monitoring using wearable devices. Finally, we investigate convolutional sparse representations, translation invariant extensions of traditional sparse representations that are gaining much attention in the last few years. In particular our analysis focuses on image denoising and show that convolutional sparse representations outperform their traditional counterparts only when the image admits an extremely sparse representation.

Monitorare uno stream di dati per individuare quando i dati in arrivo si discostano dalle condizioni normali è un problema che si incontra frquentemente in molte importanti applicazioni, dal controllo qualità in processi industriali al monitoraggio sanitario. Molte soluzioni in letteratura adottano un modello che descrive i dati normali e controlla se questo modello non è in grado di descrivere nuovi dati, individuando istanze anomale o cambiamenti che influenzano il processo generante i dati. Seguire questo approccio è complesso quando i dati hanno alta dimensionalità o sono caratterizzati da strutture complesse (come nel caso di segnali o immagini): sono questi i casi che abbiamo considerato in questa tesi. Abbiamo affrontato il problema descritto da due differenti prospettive. Nella prima parte della tesi abbiamo modellizzato i dati come realizzazioni di vettori aleatori, cioè assumendo che i dati siano descritti da una densità di probabilità liscia. Sotto questa ipotesi, ci siamo concentrati sul problema di change detection, in cui l'obiettivo è l'individuazione di cambiamenti permanenti che colpiscono il processo generante i dati. In particolare, abbiamo dimostrato il fenomeno di detectability loss, cioè il calo delle prestazioni di un popolare algoritmo di change detection (basato sul monitoraggio della funzione di verosimiglianza) all'aumentare della dimensionalità dei dati. Inoltre abbiamo proposto QuantTree, un nuovo algoritmo per la definizione di istogrammi come modelli densità per dati ad alta dimensionalità che si sono rivelati molto efficaci per affrontare il problema di change detection. Infatti, abbiamo dimostrato che QuantTree gode di un'importante proprietà: la distribuzione di qualsiasi statistica calcolata usando gli istogrammi generati da QuantTree non dipende dalla distribuzione del processo generante i dati. Questa proprietà permette il monitoraggio non parametrico di stream di dati usando qualsiasi statistica. Inoltre, i nostri esperimenti hanno dimostrato che aggregare diversi istogrammi generati da QuantTree permette di mitigare il fenomeno di detectability loss. Nella seconda parte della tesi ci siamo concentrati su dati caratterizzati da strutture complesse, che non possono essere descritti da una densità di probabilità liscia. Abbiamo adottato dizionari sparsificanti per caratterizzare dati normali e abbiamo proposto un algoritmo di anomaly detection che identifica come anomalo ogni dato che non è conforme al dizionario appreso. Per rendere il nostro algoritmo di anomaly detection efficace in applicazioni pratiche, abbiamo proposto due algoritmi di domani adaptation che adattano il nostro anomaly detector quando il processo generante i dati cambia. Gli algoritmi proposti sono stati testati con successo in due applicazioni reali: un sistema di controllo qualità che monitora la produzione di materiali nanofibrosi attraverso l'analisi di immagini al microscopio elettronico, e il monitoraggio di segnali ECG usando dispositivi indossabili. Infine, abbiamo investigato le rappresentazioni sparse convolutive, un'estensione invariante per traslazioni della tradizionali rappresentazioni sparse che stanno attraendo grande attenzione negli ultimi anni. In particolare, la nostra analisi si è concentrata sulla rimozione del rumore dalle immagini e ha mostrato che le rappresentazioni sparse convolutive ottengono migliori prestazioni delle rappresentazioni tradizionali solo quando l'immagine ammette una rappresentazione estremamente sparsa.