CIF: Small: Description Length Analysis for Machine Learning and Graph Models

点击翻译按钮获取中文摘要

Coding, in the information theoretic sense, is the transformation of data into sequences of numbers (usually 0 and 1) so that the data can be quickly transmitted from a source to a receiver. The challenge of coding is how to find the most efficient transformation such that 1) the data can be reconstructed perfectly by the receiver, 2) the data is represented by the shortest possible sequence of numbers; the length of this sequence is called the description length. Minimizing description length is both of interest for storing and transmitting data and because the description length reveals important information about structure of data. For example, description length can be used to bound the error of a learning model in machine learning, thereby allowing the algorithm to select the best model for data classification or regression tasks. The project will expand the applications of description length to new types of problems and data. Furthermore, the project also seeks to expand the type of data traditionally considered in coding by going from sequential type to data on graphs, such as arising from social networks. The project aims to simplify the sharing and storing of scientific data by developing efficient coding methods based on graph coding and learned coding, and likewise broaden the applicability of machine learning by developing efficient methods for model selection. The project will also develop new methods for anomaly detection in graphs that have applicability in medicine such as the detection of onset seizures, power grids, and computer network security including fraudulent transactions. Model selection is a central problem in many areas of science. Minimum description length (MDL) was developed by Rissanen to provide a formal criterion for model selection. It is based on coding data losslessly together with the model describing data, and choosing the model that results in the shortest total code length. The goal of the project is to extend minimum description length in new directions by going back to basics, namely that description length is based on coding. The focus is on developing new lossless coding methods. This includes the coding of graph structures, graphs with attributes, as well as combining machine learning and source coding. The research consists of three thrusts. In the first thrust, theory and practical algorithms for learned coding, which is coding based on training data, will be developed. Learned coding will be used for model selection and hyperparameter optimization in machine learning methods. In the second thrust, coding methods for graphs will be developed and be used to select graph models of data. In the third thrust, algorithms for anomaly detection and novelty detection in graph-based data will be developed by combining learned coding and graph coding.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.