III: Small: Collaborative Research: Solving Matching Problems in Machine Learning with Non-commutative Harmonic Analysis

III：小：协作研究：用非交换调和分析解决机器学习中的匹配问题

• 批准号: 1320755
• 负责人: Vikas Singh
• 金额: $ 20.22万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-01 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1320755&HistoricalAwards=false
• 关键词: III; Small; Collaborative; Research; Solving

The problem of matching representations of one set of objects, e.g., their images, to representations of another set of objects that achieves an optimal global measure of overlap (goodness of match) is ubiquitous in computer science, and remains a fundamental challenge in areas such as machine learning, computer vision, and computational biology. While some cases are solvable in polynomial time, a majority of those encountered in practice are computationally intractable - NP-hard. This research will exploit the fact that in many matching problems of interest the space to be optimized over has the (algebraic) structure of group, which allows one to leverage an entire spectrum of ideas from abstract algebra, including non-commutative harmonic analysis and fast Fourier transforms on groups. In addition to yielding efficient optimization schemes in several important cases, this algebraic approach has the potential to serve as a basis for developing novel matching algorithms and suggest new approaches for certain classes of combinatorial optimization problems. The proposed research has four main goals: to design faster general purpose harmonic analysis-based quadratic assignment problem (QAP) solvers and apply these to alignment and matching problems; to develop "tailored" QAP solution methods by coupling them to a learning component, which leverages training data to solve subsequent QAP instances much more efficiently; to design multiresolution analysis-based algorithms which yield global solutions to multi-object tracking and matching problems; and, to implement a flexible open-source library which offers a wide variety of harmonic analysis functionality (with support for wavelet and other transforms) to encourage experimentation on a broad class of inference and optimization problems. This project will yield a powerful set of algorithms and open-source software that can be used by researcher in areas of machine learning, computer vision, and optimization.

将一组对象(例如，它们的图像)的表示与实现最佳全局重叠度量(匹配度)的另一组对象的表示相匹配的问题在计算机科学中普遍存在，并且在诸如机器学习、计算机视觉和计算生物学等领域中仍然是基本挑战。虽然有些情况在多项式时间内是可解的，但在实践中遇到的大多数情况在计算上是难以处理的-NP-Hard。这项研究将利用这样一个事实：在许多感兴趣的匹配问题中，要优化的空间具有群的(代数)结构，这允许人们利用抽象代数的整个谱思想，包括非对易调和分析和群上的快速傅立叶变换。除了在几种重要情况下产生有效的优化方案外，这种代数方法还有可能成为开发新的匹配算法的基础，并为某些类型的组合优化问题提出新的方法。拟议的研究有四个主要目标：设计更快的基于调和分析的通用二次分配问题(QAP)解算器，并将其应用于配准和匹配问题；通过将它们耦合到学习组件来开发“定制的”QAP求解方法，该学习组件利用训练数据来更有效地求解后续的QAP实例；设计基于多分辨率分析的算法，为多目标跟踪和匹配问题提供全局解决方案；以及实现一个灵活的开源库，该库提供各种谐波分析功能(支持小波和其他变换)，以鼓励对广泛类别的推理和优化问题进行实验。这个项目将产生一套强大的算法和开源软件，供研究人员在机器学习、计算机视觉和优化领域使用。