CAREER: Geometric Algorithms For Data Analysis In Spaces Of Distributions

职业：分布空间数据分析的几何算法

• 批准号: 0953066
• 负责人: Suresh Venkatasubramanian
• 金额: $ 48.91万
• 依托单位: University of Utah
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-02-01 至 2016-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0953066&HistoricalAwards=false
• 关键词: CAREER; Geometric; Algorithms; Data; Analysis

Collections of distributions arise naturally when analyzing large data sets. Since it is impractical to store all but a small fraction of such data, distributional representations are typically used to summarize the data in compact form. For example, a document in a corpus is typically represented by a normalized vector of frequencies of occurrence of keywords, an image is represented by a histogram over gradient features and speech signals are represented by spectral densities over a frequency domain.Representing data sets as collections of distributions enables analysis via powerful concepts from statistics, learning theory and information theory. Concepts like strength of belief, information content, and pattern likelihood are used to extract meaning and structure from the data and are quantified using information measures like the Kullback-Leibler distance and its parent class, the Bregman divergences.These measures capture meaning in data in a manner that traditional metrics cannot, by connecting abstract notions of information loss and transfer with concrete geometric notions like distances. However, they lack properties like symmetry and the triangle inequality that are essential requirements for the application of traditional geometric algorithms for data analysis.In this project, the PI will develop a systematic, rigorous and global algorithmic framework for manipulating these distances. This framework will provide the foundation for efficient and accurate data analysis of spaces of distributions, and will lead to deeper insights into analysis problems across a wide range of applications.

在分析大型数据集时，自然会出现分布集合。由于除了一小部分数据之外存储所有数据是不切实际的，因此通常使用分布表示来以紧凑的形式总结数据。例如，语料库中的文档通常由关键字出现频率的归一化向量表示，图像由梯度特征上的直方图表示，语音信号由频域上的谱密度表示。将数据集表示为分布的集合使得能够通过来自统计学、学习理论和信息论的强大概念进行分析。 信念强度、信息量和模式似然性等概念被用来从数据中提取意义和结构，并使用Kullback-Leibler距离及其父类Bregman分歧等信息度量进行量化。这些度量通过将信息丢失和传输的抽象概念与距离等具体几何概念联系起来，以传统度量无法实现的方式捕捉数据中的意义。然而，它们缺乏对称性和三角不等式等属性，而这些属性是应用传统几何算法进行数据分析的基本要求。在本项目中，PI将开发一个系统的，严格的和全局的算法框架来操作这些距离。该框架将为分布空间的有效和准确的数据分析提供基础，并将导致对广泛应用中的分析问题的更深入的见解。