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

在信息论意义上，编码是将数据转换为数字序列（通常为0和1），以便数据可以快速从源传输到接收器。编码的挑战是如何找到最有效的变换，使得1）接收器可以完美地重建数据，2）数据由最短的可能序列表示;该序列的长度称为描述长度。最小化描述长度对于存储和传输数据都是有意义的，并且因为描述长度揭示了关于数据结构的重要信息。例如，描述长度可以用于限制机器学习中学习模型的误差，从而允许算法选择最佳模型进行数据分类或回归任务。该项目将扩展描述长度的应用到新类型的问题和数据。此外，该项目还寻求扩大传统上在编码中考虑的数据类型，从连续类型转向图表数据，例如来自社交网络的数据。该项目旨在通过开发基于图形编码和学习编码的有效编码方法来简化科学数据的共享和存储，并通过开发有效的模型选择方法来扩大机器学习的适用性。该项目还将开发适用于医学的图形异常检测新方法，例如检测发作，电网和计算机网络安全，包括欺诈交易。模型选择是许多科学领域的核心问题。最小描述长度（MDL）是由Rissanen提出的，为模型选择提供了一个形式化的标准。它是基于编码数据的损失连同描述数据的模型，并选择模型，导致最短的总代码长度。该项目的目标是通过回归基础，即描述长度基于编码，在新的方向上扩展最小描述长度。重点是开发新的无损编码方法。这包括图结构的编码，具有属性的图，以及机器学习和源代码的结合。研究包括三个方面。在第一个推力，理论和实用算法的学习编码，这是基于训练数据的编码，将开发。学习编码将用于机器学习方法中的模型选择和超参数优化。在第二个方面，将开发图形编码方法，并用于选择数据的图形模型。在第三个重点中，将通过结合学习编码和图形编码来开发基于图形数据的异常检测和新奇检测算法。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估而被认为值得支持。

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.