AF: Medium: Collaborative Research: Uncertainty Aware Geometric Computing

今天，大多数科学和工程学科都有巨大的机会从他们可以获得的大量数据中创造知识。但是，缺乏适当的算法和分析工具来处理、组织和查询这一海量数据，这使得这项任务极具挑战性。今天获取的数据中有很大一部分具有几何特征，即使是非几何数据，也往往通过将它们嵌入多维特征空间并利用该空间的几何来进行最佳分析。这些数据总是充满了噪声、不准确、离群值，往往是不完整和近似的，然而大多数现有的几何算法在将其输出与其输入相关联时无法应对任何数据不确定性。该项目旨在通过研究感知不确定性的几何计算来填补这一空白，明确的目标是设计算法技术和基础，以帮助在存在各种非理想和不确定的情况下从大量几何数据中提取“知识”。它专注于一些基本的几何问题，所有这些问题都处理不确定的数据。将开发一套统一的模型，用于建模可以处理多种不确定性类型的不确定性，并将注意处理异质和动态数据中的噪声/离群值。将对算法进行研究，以了解输入不确定性如何传递到输出不确定性(例如，通过将置信度或似然与每个输出相关联，或计算输出的某些统计数据)，以及输入不确定性如何影响输出质量(例如，通过根据输入不确定性定义和计算输出的稳定性)。由于精确解在计算上可能是不可行的，因此重点将放在简单、有效的近似技术上(例如，计算不确定数据的Delaunay三角剖分及其子复合体等几何/拓扑结构的紧凑、近似分布)。该奖项的一个关键组成部分是使用几个关键问题来解决存在不确定性时出现的各种计算问题，并开发一套核心技术，不仅在这些关键问题上阐明不确定情况下的算法设计，而且还可以根据需要转移到其他几何问题上。这项研究涉及理论计算机科学和应用数学的许多主题，包括离散和计算几何、离散和连续优化、估计理论和机器学习。这项研究将加强计算几何与各种学科的联系，包括机器学习、概率数据库、统计学和地理信息系统。由于如此多的问题需要几何数据分析，该项目有可能增强各种政府、商业和民间单位做出影响整个社会的知情决策的能力。

Most scientific and engineering disciplines today have enormous opportunities for creation of knowledge from massive quantities of data available to them. But the lack of appropriate algorithms and analysis tools for processing, organizing, and querying this data deluge makes this task extremely challenging. A large portion of the data being acquired today has a geometric character, and even non-geometric data are often best analyzed by embedding them in a multi-dimensional feature space and exploiting the geometry of that space. This data is invariably full of noise, inaccuracies, outliers, is often incomplete and approximate, yet most of the existing geometric algorithms are unable to cope with any data uncertainty in relating their output to their input. The project aims to fill this void by investigating uncertainty-aware geometric computing, with an express goal of designing algorithmic techniques and foundations that will help extract ``knowledge'' from large quantities of geometric data in the presence of various non-idealities and uncertainties. It focuses on a number of fundamental geometric problems, all dealing with uncertain data. A unified set of models will be developed for modeling uncertainty that can deal with multiple uncertainty types, and attention will be paid to handling noise/outliers in heterogeneous and dynamic data. Algorithms will be investigated for understanding how input uncertainty carries over to output uncertainty (e.g. by associating a confidence level or likelihood with each output, or computing certain statistics of the output) and how the input uncertainty impacts the quality of the output (e.g. by defining and computing the stability of the output in terms of the input uncertainty). Since exact solutions are likely to be computationally infeasible, the emphasis will be on simple, efficient approximation techniques (e.g. computing a compact, approximate distribution of geometric/topological structures such as Delaunay triangulations and their subcomplexes of uncertain data). A key ingredient of the award is to address a variety of computational issues that arise in the presence of uncertainty using a few key problems, and to develop a core set of techniques that illuminate algorithmic design under uncertainty not only on these key problems but that can also be transferred to other geometric problems, as needed. This research touches upon many topics in theoretical computer science and applied mathematics including discrete and computational geometry, discrete and continuous optimization, estimation theory, and machine learning. This study will strengthen connections of computational geometry with a variety of disciplines, including machine learning, probabilistic databases, statistics, and GIS. Since so many problems require geometric data analysis, the project has the potential of enhancing the capability of various government, commercial, and civic units to make informed decisions that impact the society at large.