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

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

• 批准号: 1320344
• 负责人: Imre Kondor
• 金额: $ 22.2万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-01 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1320344&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实例；设计基于多分析的基于分析的算法，该算法为多对象跟踪和匹配问题产生全局解决方案；并且，要实施一个灵活的开源库，该库提供了各种谐波分析功能（支持小波和其他变换），以鼓励对广泛的推理和优化问题进行实验。该项目将产生一套强大的算法和开源软件，研究人员可以在机器学习，计算机视觉和优化领域使用。