AF: Small: Geometric Sampling Theory and Robust Machine Learning Algorithms

研究人员将把计算几何的思想应用于人工智能中的问题，特别是分类问题，在分类问题中，计算机学习识别一类输入（例如，特定人员的照片或安全漏洞的证据）。据观察，许多分类问题似乎都遵循“流形假设”，即假设特定类别的输入位于高维空间的表面附近。当这个假设成立时，输入具有规则结构，分类算法可以利用该结构获得更好的预测精度。然而，研究人员认为，标准的分类算法并没有充分利用这种结构。此外，许多分类器很容易被称为“对抗性示例”的输入所欺骗，在这种情况下，对输入的看似难以察觉的变化导致其被错误分类。该项目的目标是发展对流形假设及其对准确性和对抗性示例的影响的数学理解，利用这种理解来开发更健壮的分类算法，防止被愚弄，并生产实现这些算法的软件。这些强大的算法将提高机器学习应用的安全性，比如自动驾驶汽车和医疗应用。该项目还将培训研究生和本科生进行研究，并创造知识，这些知识将在未来的机器学习课程中教授。研究人员将发展流形采样理论（基于计算几何领域的思想，用于可证明的良好表面重构和流形重构），并将其应用于鲁棒机器学习中的问题。假设典型的训练数据是从嵌入在高维输入空间中的相对低维的流形中采样的，可能带有噪声。该理论将包括一个概率抽样理论，使传统的学习理论适应流形假设，并考虑到附加的噪声。流形采样理论将用于阐明机器学习算法容易被击败的条件，发展关于哪些机器学习算法和哪些采样条件允许对抗性示例存在（或阻止它们存在）的理论，并设计对对抗性示例更健壮的学习算法。另一个目标是设计算法，建议在哪里采样额外的训练点，以提高分类器的准确性和鲁棒性。一个关键思想是将训练点替换为细长的几何对象，如椭球体、多面体或Voronoi细胞，并修改学习算法以在这些几何对象上或附近输出正确的标签。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The investigators will apply ideas from computational geometry to problems in Artificial Intelligence, especially the problem of classification, in which a computer learns to recognize a class of inputs (e.g., photos of a specific person or evidence of a security breach). It has been observed that many classification problems seem to obey the "manifold hypothesis", the assumption that inputs in a particular class lie near a surface in a high-dimensional space. When this assumption is true, the inputs have a regular structure that a classification algorithm can exploit to obtain better predictive accuracy. Nevertheless, the investigators believe that standard classification algorithms do not fully take advantage of this structure. Moreover, many classifiers are easily fooled by inputs known as "adversarial examples", where seemingly imperceptible changes to an input cause it to be misclassified. The goals of the project are to develop a mathematical understanding of the manifold hypothesis and its effects on accuracy and on adversarial examples, to exploit this understanding to develop classification algorithms that are more robust against being fooled, and to produce software that implements these algorithms. These robust algorithms will improve safety in machine-learning applications, such as self-driving automobiles and medical applications. The project will also train graduate and undergraduate students to do research, and create knowledge that will be taught in future classes on machine learning.The investigators will develop manifold-sampling theory (based on ideas developed in the field of computational geometry for provably good surface reconstruction and manifold reconstruction) and apply it to problems in robust machine learning. It is assumed that typical training data are sampled, possibly with noise, from manifolds of relatively low dimension embedded in high-dimensional input spaces. The theory will include a probabilistic sampling theory, adapting traditional learning theory to the manifold hypothesis and accounting for added noise. The manifold\-sampling theory will be used to elucidate the conditions in which machine-learning algorithms are easily defeated, to develop theories about which machine-learning algorithms and which sampling conditions permit adversarial examples to exist (or prevent them from existing), and to design learning algorithms that are more robust against adversarial examples. Another goal is to design algorithms that suggest where additional training points should be sampled to improve the accuracy and robustness of a classifier. A key idea is to replace training points with elongated geometric objects such as ellipsoids, polyhedra, or Voronoi cells, and to modify learning algorithms to output correct labels on or near these geometric objects.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.