『』组合求解器 + 深度学习 =？这篇ICLR 2020论文告诉你答案

组合求解器 + 深度学习 =？这篇ICLR 2020论文告诉你答案
【『』组合求解器 + 深度学习 =？这篇ICLR 2020论文告诉你答案】

本文插图
机器之心Pro
选自TowadsDataScience
作者：Marin Vlastelica Pogan?i?
机器之心编译
参与：郭元晨、魔王
如何将组合求解器无缝融入深度神经网络？ICLR 2020 spotlight 论文《Differentiation of Blackbox Combinatorial Solvers》探讨了这一难题，论文一作 Marin Vlastelica 撰文介绍了其主要思想。
论文链接：https://arxiv.org/abs/1912.02175
GitHub 链接：https://github.com/martius-lab/blackbox-backprop
机器学习研究现状表明，基于深度学习的现代方法和传统的人工智能方法并不一样。深度学习被证实可在多个领域中作为特征提取的强有力工具，如计算机视觉、强化学习、最优控制、自然语言处理等。不幸的是，深度学习有一个致命弱点，即它不能处理需要组合泛化能力（combinatorial generalization）的问题。例如，将地图作为图像输入，学习预测 Google Maps 上的最快路线，这是最短路径问题的一个实例。这样的问题还有很多，如 (Min,Max)-Cut 问题、最小损失完美匹配问题（Min-Cost Perfect Matching）、旅行商问题、图匹配问题等。
如果只是要孤立地解决此类组合问题，我们有很棒的求解器工具箱可以使用，从高效的 C 语言实现的算法，到更通用的 MIP（mixed integer programming）求解器，如 Gurobi 。求解器需要定义明确的结构化输入，因此求解器面临的主要问题是输入空间的表示形式。
尽管组合问题是机器学习研究领域的课题之一，但对于解决此类问题的关注却一直有所不足。这并不意味着社区未把组合泛化问题视为通往智能系统路上的关键挑战。理想情况下，人们能够以端对端、没有任何妥协的方式，通过强大的函数逼近器（如神经网络）将丰富的特征提取与高效的组合求解器结合起来。这正是我们在论文《Differentiation of Blackbox Combinatorial Solvers》中所实现的目标，我们因此获得了很高的评审分数，并将在 ICLR 2020 会议上做 spotlight 演讲。
读者在阅读下文时需要注意，我们并不是在尝试改进求解器，而是要将函数逼近和现有求解器协同使用。
假设黑盒求解器（blackbox solver）是一个可以轻松插入深度学习的结构模块。
黑盒求解器的梯度
我们依据从连续输入（如图中的边权重）到离散输出（如最短路径、选中的图中的边）之间的映射来考虑组合优化器，定义如下
求解器最小化某种损失函数 c(ω,y) ，如路径的长度。更具体地，求解器求解如下优化问题：
现在，假设 ω 是神经网络的输出，即我们要学习的某种表示。直观上， ω 表示什么？ω 旨在定义组合问题的实例。例如， ω 可以是用来定义图中边权重的向量。在这种情况下，求解器可以解决最短路径问题、旅行商问题，或者其他指定边损失的问题。我们想实现的是通过 ω 来作出正确的问题描述。
自然地，我们想优化该表示，使它最小化损失，即关于求解器输出的函数 L(y) 。我们马上要面临的问题是损失函数是分段恒定的，这意味着对于表示 ω ，该函数的梯度几乎处处为 0 ，并且在损失函数的跳跃处梯度未被定义。说白了，这样的梯度对于最小化损失函数没有用。
到目前为止，已经出现一些依赖于求解器松弛（solver relaxation）的方法，但它们不得不在最优性上作出一定牺牲。而我们提出了一种不影响求解器最优性的方法。我们通过定义原始目标函数的分段仿射插值来实现这一目的，其中插值本身由超参数 λ 控制，如下图所示：