Algoritmi Efficienti e Rigorosi per l'estrazione di Pattern Significativi ed Approssimati

Massive amounts of data are generated in all areas of industry and science, such as social networks, biomedical research, finance, and many others. Extracting useful and reliable knowledge from such data is a fundamental task with two challenges: the first is to provide rigorous statistical guarantees on the analysis, controlling the discovery of spurious results. This aspect is particularly important when the validation of the extracted information is expensive (e.g., in biology), or when data-driven decisions need to be performed accurately (e.g., in medicine). Therefore, it is necessary to design methods that are robust to the inherent noise and uncertainty of the data. The second challenge is to design algorithms that scale the computation to the analysis of large datasets, as the ones of interest from the applications. One example is the analysis of data from large genomic experiments, whose availability is rapidly increasing as sequencing costs continue to fall. In such settings, methods capable of computing high-quality approximations are often the only available practical option. Pattern Mining is a key component Knowledge Discovery, that comprise methods that aim at discovering interpretable and useful structure from data. In particular, Significant Pattern Mining aims at extracting patterns with rigorous guarantees in terms of statistical significance of the output, controlling the retrieval of false dis- coveries. Approximate Pattern Mining, instead, focuses on the fundamental task of computing rigorous, high-quality approximations of collections of interesting Patterns. The objective of this Thesis is to design novel efficient and rigorous techniques for Significant and Approximate Pattern Mining, in three scenarios. The first scenario we consider is Mining Significant Patterns, such as Itemsets and Subgraphs, from labelled datasets, with guarantees on false discoveries. In this setting we tackle two problems: the problem of efficiently extracting the set of Top-k most Significant Patterns, providing various forms of control of false discoveries, such as bounding the Family-Wise Error Rate, and effectively limiting the output size by focusing on the k most interesting results; and the problem of Mining Significant Patterns with an unconditional statistical test, such as Barnard’s exact test, that, as we argue, is more appropriate for Knowledge Discovery applications than traditionally employed conditional tests. For both problems, we develop new algorithms and provide theoretical and experimental evidence of their effectiveness. In the second scenario, we develop a novel method to provide rigorous approximations of the collection of frequent strings of length k, called k-mers, from massive datasets of biological reads, originating from high-throughput sequencing experiments. We show with extensive experiments that the most frequent k-mers can be well estimated by an advanced sampling scheme that analyzes a randomly chosen fraction of the data, resulting in significant computational speedups. Approximating the most frequent k-mers allows to accurately estimate distances between pairs of datasets from metagenomic applications in a fraction of the time required by the exact approaches. We provide a rigorous analysis of our algorithm using the VC dimension, a key concept from Statistical Learning Theory. In the last scenario, we study the Monte Carlo Empirical Rademacher Average (MCERA), a fundamental data-dependent measure of Statistical Learning Theory of the complexity of families of functions. This important quantity allows computing tight probabilistic uniform deviation bounds between empirical averages of sets of functions from their expectation. First, we develop a general framework to compute it efficiently; obtaining sharp uniform convergence bounds has applications in both Significant Pattern Mining and Approximate Pattern Mining. Secondly, we study its probabilistic convergence.

Imponenti quantita' di dati sono generate in tutti i campi dell'industria e della scienza, come ad esempio nel caso dei social networks, ricerca biomedica, finanza, e molti altri. L'estrazione di informazione utile ed affidabile da questi dati e' un problema fondamentale con due sfide: la prima riguarda fornire rigorose garanzie statistiche, controllando l'estrazione di risultati inaccurati. Questo aspetto e' di particolare importanza quando la validazione dell'informazione estratta dai dati e' molto costosa (ad esempio, in biologia), o quando decisioni data-driven critiche devono essere assunte (ad esempio, in medicina). Per questi motivi, e' necessario sviluppare metodi che siano robusti rispetto all'intrinseca presenza di rumore e incertezza nei dati. La seconda sfida riguarda la progettazione di algoritmi che siano in grado di scalare l'analisi di grandi moli di dati, come quelle di interesse nelle applicazioni. Un esempio e' dato dall'analisi di dati da esperimenti in genomica, la cui disponibillita' e' in crescente aumento grazie alla diminuzione dei costi di sequenziamento. In queste circostanze, metodi in grado di calcolare approssimazioni di alta qualita' rappresentano spesso le uniche opzioni praticamente attuabili. L'estrazione di Pattern e' una componente chiave del Knowledge Discovery, che comprende metodi il cui obbiettivo e' l'estrazione di strutture interpretabili ed utili dai dati. In particolare, il problema del Significant Pattern Mining ha lo scopo di estrarre pattern con garanzie rigorose in termini della significativita' statistica, controllando l'estrazione di falsi positivi. Il problema dell'Approximate Pattern Mining, invece, si focalizza sull'operazione fondamentale di calcolare approssimazioni rigorose e precise di collezioni di pattern interessanti. L'obbiettivo di questa tesi e' lo sviluppo di nuove tecniche efficienti e rigorose per i problemi di Significant e Approximate Pattern Mining, in tre scenari. Nel primo, consideriamo il problema di estrarre Pattern Significativi, come Itemsets e Sottografi da dataset etichettati, fornendo garanzie sui falsi positivi. In questo scenario affrontiamo due problemi: il problema di calcolare efficientemente l'insieme dei k pattern piu' significativi, garantendo diverse forme di controllo dei falsi positivi, come ad esempio controllando la Family-Wise Error Rate, limitando allo stesso tempo la taglia dell'output concentrando l'analisi ai k risultati piu' significativi; e il problema di estrarre pattern significativi utilizzando un test non-condizionale, come il test statistico di Barnard, il quale, come discuteremo, e' piu' appropriate nel contesto di Knowledge Discovery rispetto a test statistici condizionali, tipicamente utilizzati. Per entrambi i problemi sviluppiamo nuovi algoritmi e deriviamo sia analisi teoriche che sperimentali che ne dimostrano l'efficacia. Nel secondo scenario, sviluppiamo un metodo per calcolare approssimazioni rigorose della collezione di stringhe frequenti di lunghezza k, chiamate k-mers, da grandi collezioni di sequenze biologiche tipiche di esperimenti di sequenziamento high-throughput. Mostriamo con esaustivi esperimenti che i k-mer piu' frequenti possono essere stimati efficientemente con uno schema di campionamento avanzato, analizzando solamente una frazione dei dati, risultando in miglioramenti significativi del tempo di calcolo. Forniamo un'analisi teorica del nostro algoritmo basata sulla VC dimension, un concetto chiavo della Statistical Learning Theory. Nell'ultimo scenario, studiamo la Monte Carlo Empirical Rademacher Average (MCERA), una misura fondamentale della Statistical Learning Theory in grado di misurare la complessita' di insiemi di funzioni. In primo luogo, sviluppiamo un metodo generale per il calcolo efficiente della MCERA, sfruttando la struttura combinatoriale delle funzioni. In ultimo luogo, ne studiamo la convergenza.