ABSTRACT

Methods for knowledge discovery from data (e.g., for extracting patterns or finding anomalies) have found their way to research labs in life and biological sciences, and in industries such as cybersecurity. In these fields, the statistical validity of the results produced by these methods is paramount: false discoveries cannot be tolerated. Current methods do not offer such stringent statistical guarantees. This project develops algorithms for statistically-sound Knowledge Discovery from Data. It transforms the field by shifting the goal of the Knowledge Discovery process from extracting information about the available data to gaining new understanding of the noisy, random process that generates the data. The proposed methods contribute towards a faster and higher-throughput scientific pipeline, by allowing scientists and practitioners to efficiently analyze rich large datasets and to trust the results of the analysis. Researchers can then focus on their discipline-specific research tasks without worrying about computational or statistical considerations. The project includes collaborations with a local museum and a local public library, to analyze data about their collections of historic materials, and with a cybersecurity company to develop methods for fast detection of network attacks with few false positives. A diverse cohort of undergraduate students will be involved in the research and educational components of the project.

Research in knowledge discovery has mostly focused on understanding the available data, rather than the process that generated it. In the few cases where hypothesis testing was used to assess the results (mostly for simple patterns), only simplistic null models were considered, and the testing employed low-statistical-power approaches (e.g., the Bonferroni correction) to control only for one measure of false discovery, the Family-Wise Error Rate. This project is transformative because it will develop efficient methods for evaluating a wide variety of results (e.g., patterns, anomalies, graph/vertex/edge properties, and more) obtained from large rich datasets (e.g., transactional datasets, graphs, and time series), using realistic null models which are more appropriate for these tasks, and better encode available knowledge of the data generating process. We will create novel efficient procedures to sample from such models, both approximate (e.g., Markov-Chain Monte Carlo) and exact, and combine them with modern resampling- based multiple testing methods, in a multiple-hypothesis first approach that also controls the (marginal) False Discovery Rate.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

Please report errors in award information by writing to: awardsearch@nsf.gov.