AF: Medium: Collaborative Research: Uncertainty Aware Geometric Computing

AF：媒介：协作研究：不确定性感知几何计算

• 批准号: 1161480
• 负责人: Leonidas Guibas
• 金额: $ 30万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1161480&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Uncertainty

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.

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