AF: Small:Explorations in Computational Learning Theory

AF：小：计算学习理论的探索

• 批准号: 0917153
• 负责人: Lisa Hellerstein
• 金额: $ 33.87万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-01 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0917153&HistoricalAwards=false
• 关键词: AF; Small; Explorations; Computational; Learning

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.

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