AF: Medium: Collaborative Research: Uncertainty Aware Geometric Computing

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

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.