CAREER: AF: Giving Form to Data with a Geometric Scaffold

用几何学来发现数据中的结构是一个古老的想法(引用柏拉图的一句话：“上帝永远几何化”)，随着我们数据的变化，它获得了新的应用。今天的数据集，来自机器学习等领域，往往是海量和高维的：例如，当试图对新闻文章进行分类时，每篇文章可能被表示为一个点，其中每个词的频率是一个不同的维度。这导致了几何图形很难直观地掌握，也很难通过计算来处理(“维度诅咒”)。找到一个较小且维度较低的近似保持几何结构的数据点子集，不仅可以减少计算时间，而且可以通过抑制无关特征来改善结果。在更结构化的空间中表示一般空间的点间距离可以支持新的操作，例如通过映射屏幕的2-D平面来实现数据可视化，或者通过映射到树的分层结构来更高效地计算。这个项目采用了梳理几何结构的古老做法，并将其应用于现代世界的大维和高维数据集。通过对大数据和机器学习等领域的基础问题采取几何方法，该项目寻求将计算几何与这些其他领域更紧密地联系在一起，进而使计算几何的经典领域现代化，并推动这些其他领域的发展。这个项目的教育目标将通过直接支持学生对概述的主题的研究，将主题纳入开发新课程，并定期组织研讨会，以提高获奖机构算法和理论计算机科学的可见性和跨学科性质。给定一个数据集，目标是指定其几何结构，使用这种结构总结并嵌入到可以高效完成计算的更简单的空间中，当这不可能时，确定如何最小限度地固定数据以促进这些任务。该项目的重点是位于大数据、几何和机器学习的交叉点上的三个与几何结构相关的主题：1)数据分解和稀疏化，2)结构化空间的度量嵌入，以及3)度量违反距离。其最终目的是开发更好的数据处理算法，范围从更好的聚类算法到更好的分类算法。这种算法的普遍存在意味着任何进步都有可能对现实世界产生重大影响。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Using geometry to find structure in data is an old idea (Plato is quoted as saying, "God ever geometrizes") that gains fresh application as our data changes. Today's data sets, from areas such as machine learning, are often massive and high-dimensional: for example, when trying to classify news articles, each article may be represented as a point where the frequency of each word is a different dimension. This leads to geometries that are hard to grasp intuitively and hard to work with computationally (the "curse of dimensionality"). Finding a smaller and lower dimensional subset of the data points that approximately preserves geometric structure not only reduces computation time but also can improve results by suppressing extraneous features. Representing inter-point distances of a general space in a more structured space can support new operations, such as data visualization by mapping the 2-D plane of the screen, or more efficient computation by mapping to the hierarchical structure of a tree. This project takes the age-old practice of teasing out geometric structure and applies it to the large- and high-dimensional data sets of the modern world. By taking a geometric approach to foundational problems in areas such as big data and machine learning, this project seeks to more closely connect computational geometry and these other areas, in turn both modernizing the classical field of computational geometry and advancing these other areas. The educational goals of this project will be achieved by directly supporting student research on the outlined topics, incorporating topics into developing new courses, and organizing regular seminars in order to grow the visibility and interdisciplinary nature of algorithms and theoretical computer science at the awardee institution.Given a data set, the goal is to specify its geometric structure, use this structure to summarize and embed into simpler spaces where computations can be done efficiently, and when this is not possible, identify how to minimally fix the data to facilitate these tasks. The project's focus is on three interrelated topics concerning geometric structure that lie at the intersection of big data, geometry, and machine learning: 1) data factorization and sparsification, 2) metric embeddings for structured spaces, and 3) metric violation distance. The ultimate purpose is to develop better algorithms for handling data, ranging from better clustering algorithms to better classification algorithms. The ubiquity of such algorithms implies that any progress has the potential for significant real world impact.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.