AF: Small:Explorations in Computational Learning Theory

机器学习的一个主要目标是让计算机从数据中“学习”，并根据它们所学到的做出预测。机器学习已被用于许多应用，如识别垃圾电子邮件、检测可疑的计算机网络流量和检测恶性肿瘤。机器学习的使用是基于一个隐含的假设，即存在一个数学函数，该函数以一定的精度描述预测问题的输入和正确预测之间的关系。该函数不是任意的；相反，它是某种受限类型。然而，并不是所有类型的函数都可以有效地学习。此外，可学习性取决于可用数据的类型。本项目侧重于布尔函数的可学习性，这是计算学习理论中的一个中心主题。本项目的研究主要分为三大类：随机样本学习、代价学习和DNF学习与最小化。第一类问题涉及标准PAC学习模型中的核心开放问题，并探索从不同概率分布获取数据对学习有多大帮助。第二类问题的起因是蛋白质工程、数据库和网络安全方面的具体问题，在这些领域，与确定投入价值或获取数据相关的成本。第三类是关于使用DNF假设正确学习DNF公式的问题，与DNF最小化相关的复杂性理论问题，以及DNF大小证书的复杂性问题。这个项目试图扩大我们对哪些类型的函数是计算机可以有效学习的理解，以及在什么条件下。对有成本的学习的研究可以在激励它的应用领域产生进步。DNF最小化是复杂性理论和逻辑电路设计中的一个中心问题，DNF的研究在这两个领域都有潜在的影响。

A primary goal of machine learning is to have computers "learn" from data, and to make predictions based on what they have learned. Machine learning has been used in many applications, such as identification of spam emails, detection of suspicious computer network traffic, and detection of malignant tumors. The use of machine learning is based on the implicit assumption that there is a mathematical function that describes, with some accuracy, the relation between the inputs to the prediction problem and the correct prediction. The function is not arbitrary; instead, it is of a certain restricted type. However, not all types of functions are efficiently learnable. Also, learnability depends crucially on the type of data that is available.This project focuses on the learnability of Boolean functions, a central topic in computational learning theory. The research in this project falls into three main categories: learning from random examples, learning with costs, and DNF learning and minimization. Problems in the first category address core open questions in the standard PAC learning model and explore the extent to which access to data from different probability distributions can aid in learning. Problems in the second category are motivated by concrete problems in protein engineering, databases, and cyber-security, where there are costs associated with determining the value of inputs, or in obtaining data. The third category concerns problems of properly learning DNF formulas using DNF hypotheses, related complexity theoretic problems concerning DNF minimization, and problems concerning the complexity of certificates of DNF size.Broadly, this project seeks to expand our understanding of which types of functions are efficiently learnable by computers, and under what conditions. The research on learning with costs can yield advances in the application areas that motivate it. DNF minimization is a central problem in both complexity theory and in the design of logic circuits; the research on DNF has the potential for impact in both these areas.