Efficient Discrete Optimization for Structured Prediction Problems in Computer Vision and Machine Learning

该项目的目标是研究和开发一种新的普遍适用，快速和可扩展的离散优化求解器，用于计算机视觉和机器学习中的结构化预测问题。结构化预测问题是那些涉及计算在约束条件方面具有特殊结构的高维输出的任务。例子包括跟踪，其中输出是跟踪图中的成对不相交轨迹集，聚类，其中输出是将整个集划分为成对不相交簇或对应问题，其中寻求点之间的1:1映射。在这种情况下，纯神经网络管道可能并不理想，因为通常对其输出进行明确的约束建模是困难的或不自然的。另一方面，优化问题可以直接表述，这样它们就考虑了期望的约束。不幸的是，标准求解器通常不适用于结构化预测任务，因为它们不能扩展到非常高维的设置。另一方面，专门的求解器很难开发，每当需要一种新的约束类型时，它们都需要调整甚至从头重写，这限制了它们的适用性。这个项目的目标是超越这种二分法，将标准解算器的通用性与专门解算器的效率结合起来。为此，我们将提炼出在专门求解器中发现的有效算法设计原则，并将其一般化，以便它们在更一般的环境中工作。我们将特别强调大规模GPU并行性。此外，求解器也将是机器学习友好的。首先，解算器是可训练的。通过训练求解器处理以前看到的优化问题来改进求解器是可能的，从而提高它处理未知问题的性能。其次，求解器将嵌入到特定结构化预测问题任务的神经网络管道中，允许与求解器一起训练神经网络骨干，从而使整个系统更好地执行手头的任务。

The goal of this project is to research and develop a new generally applicable, fast and scalable discrete optimization solver for structured prediction problems in computer vision and machine learning. Structured prediction problems are those tasks that involve computing high-dimensional output that has special structure in terms of constraints. Examples include tracking, where the output is a set of pairwise disjoint trajectories in a tracking graph, clustering, where the output is a partition of the whole set into pairwise disjoint clusters or correspondence problems, where a 1:1 mapping between points is sought. Pure neural network pipelines may not be ideal in this setting, since often modelling explicit constraints on their output is difficult or unnatural. On the other hand, optimization problems can be straightforwardly formulated such that they take into account the desired constraints. Unfortunately, standard solvers are often not applicable in structured prediction tasks, since they do not scale to the very high-dimensional setting. On the other hand specialized solvers that scale are hard to develop and whenever a new type of constraints is needed they need to be adapted or even re-written from scratch, limiting their applicability. The goal of this project is to go beyond this dichotomy and to combine the generality of standard solvers with the efficiency of specialized ones. To this end, we will distill efficient algorithmic design principles found in specialized solvers and generalize them, so that they work in more general settings. We will put a special emphasis on massive GPU parallelism. Additionally, the solver will also be machine-learning friendly. First, the solver will be trainable. It will be possible to improve the solver by training it on previously seen optimization problems, thereby increasing its performance on unseen ones. Second, the solver will be embedded in neural network pipelines for specific structured prediction problem tasks, allowing to train the neural network backbone together with the solver, thereby making the whole system perform better for the task at hand.