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

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

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.