AF: SMALL: Finding Models of Data and Mathematical Objects

科学哲学中的一个核心谜团是“数学的不合理有效性”。“为什么自然现象似乎有简单，优雅的数学模型？机器学习的成功引发了一个类似的问题，称为“机器学习的不合理有效性”。“数学科学和机器学习的成功是由于所研究的现象中的一些共同元素吗？这是因为我们问的问题的性质吗？或者，这是一个海市蜃楼，由于认知偏见，在关注成功的使用和忽视失败？这一提议的目的是通过将其与数学和理论计算机科学中的类似现象联系起来来更好地理解这一点，在数学和理论计算机科学中，复杂的数学对象通常具有简单的“模型”，可以准确估计许多感兴趣的量。 通过将纯数学中的概念与机器学习中的类似物联系起来，研究人员计划使用强大的机器学习技术来证明新的数学结果，并使用数学概念来扩展机器学习的范围。更确切地说，研究团队将探索数学中的正则性引理，复杂性理论中的核心定理和机器学习中的提升之间的深层联系。其核心是以下问题。给定某类数据点上的分布D和一类假设H，找到模型M（即，在同一基础集合上的分布），即（i）关于H中的假设与D不可区分;（ii）简单，因为它具有根据H中的少量测试的定义;（iii）在上述条件下具有尽可能高的熵。考虑到这一目标，本提案将解决以下主要问题：1.什么时候存在这样简单的高熵模型？换句话说，自然现象有简单、准确的模型，这说明了什么？它对被问到的问题有什么看法？这一特征将在分布D的结构和类H.2方面进行研究。上述不同标准（不可否认性、简单性和熵）之间的定量权衡是什么？3.如果存在这样的模型，能否有效地找到它们？什么样的算法会导致发现这样的模型？该奖项反映了NSF的法定使命，并被认为是值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估的支持。

A central mystery in the philosophy of science is "the unreasonable effectiveness of mathematics." Why do natural phenomena seem to have simple, elegant mathematical models? The success of machine learning raises an analogous issue called "the unreasonable effectiveness of machine learning." Is the success of both mathematical science and machine learning due to some common elements in the phenomena studied? Is it due to the nature of the questions we ask? Or is it a mirage due to cognitive bias, in focusing on successful uses and ignoring failures? The aim of this proposal is to better understand this by relating it to a similar phenomenon in mathematics and theoretical computer science, where complex mathematical objects often have simple "models" that give accurate estimates of many quantities of interest. By relating concepts in pure mathematics to analogs in machine learning, the researchers plan to both use powerful machine-learning techniques to prove new mathematical results, and to use mathematical concepts to extend the scope of machine learning.More precisely, the research team will explore a deep connection between regularity lemmas in mathematics, hard core theorems in complexity theory, and boosting in machine learning. At the core of it is the following problem. Given a distribution D on some kind of data points, and a class of hypotheses H, find a model M (namely, a distribution on the same underlying set), that is(i) indistinguishable from D with respect to the hypotheses in H;(ii) simple, in that it has a definition in terms of a small number of tests in H;(iii) has as high entropy as possible given the conditions above.With this goal in mind, this proposal will address the following main questions:1. When do such simple, high entropy models exist? In other words, what does it say about natural phenomena that they have simple, accurate models? What does it say about the questions being asked? This characterization will be studied both in terms of the structure of the distribution D and the class H.2. What are the quantitative tradeoffs between the different criteria above (indistinguishability, simplicity, and entropy)?3. When such models exist, can they be found efficiently? What algorithms would lead to the discovery of such models?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.