Investigation of the usage of Rademacher Averages for causal rule discovery

The aim of this thesis is to investigate the usage of Rademacher Averages in causal rule discovery, to overcome two main issues of the state of the art approach. In causal rule discovery, a rule, defined as a clause on the variables of the dataset, is assessed as causal or not through the computation of a given statistic. Since the statistic is computed from observational data, it is necessary to consider its confidence interval. The state of the art approach has two main limitations: (i) it computes the confidence interval modeling the error with a normal distribution; (ii) it tests several rules but without accounting for multiple hypothesis testing correction. We propose an approach based on Rademacher Averages to compute a confidence interval that: (i) depends on the features of the chosen statistic; (ii) directly accounts for MHT correction. Furthermore the interval provides rigorous probabilistic guarantees. We tested three different statistics using simulated data, and found that one provides good performance when the dataset is sufficiently big, but it has fairly good performance also for smaller sample sizes.

Lo scopo di questa tesi è studiare la possibilità di utilizzo delle Rademacher Averages nella ricerca di regole causali, al fine superare due limitazioni del corrente stato dell'arte. Nella ricerca di regole causali, una regola, definita come una clausola sulle variabili del dataset, è valutata come causale o meno attraverso il calcolo di una statistica. Dal momento che la statistica è calcolata da dati osservazionali, è necessario considerare il suo intervallo di confidenza. L'approccio stato dell'arte ha due limitazioni principali: (i) l'intervallo di confidenza è calcolato modellando l'errore con una distribuzione normale; (ii) vengono testate diverse regole ma senza tenere conto della correzione per test multipli. Noi proponiamo un approccio basato sulle Rademacher Averages per calcolare un intervallo di confidenza che: (i) dipende dalle caratteristiche della statistica scelta; (ii) tiene conto della correzione per test multipli. Inoltre l'intervallo ha garanzie probabilistiche. Abbiamo testato tre diverse statistiche su dati simulati, e trovato che una dà buoni risultati quanto il dataset è sufficientemente grande, e abbastanza buoni anche per dataset più piccoli.