组合泛化能力太差？用深度学习融合组合求解器试试

正文

请到「今天看啥」查看全文

假设黑盒求解器（blackbox solver）是一个可以轻松插入深度学习的结构模块。

黑盒求解器的梯度

将连续输入到离散输出之间的映射作为求解器的方式，另外，连续输入可以是图边的权重，离散输出可以是最短路径、选定的图边。其中，映射的定义如下

求解器可以将最小化一些损失函数c(ω,y)，这些损失函数可以是路径的长度。用公式这种优化问题表示如下：

上式中，w为神经网络的输出，也就是神经网络学习的某种表示，例如可以是图边权重的某个向量。在最短路径问题、旅行商问题中，ω可以用来作出正确的问题描述。

优化问题的关键是最小化损失函数，现在的问题是损失函数是分段表示的，也就是说存在跳跃间断点。这意味着对于表示 ω，该函数的梯度几乎处处为 0，并且在跳跃间断点处，梯度尚未被定义。

目前，利用求解器松弛（solver relaxation）的方法能够解决这个问题，但会损失最优性。论文中提出了一种不影响求解器最优性的方法。即对原始目标函数的分段处用仿射插值来定义，另外插值由超参数 λ 控制，如下图所示：

如上所示，函数图像的黑色部分是原函数给出的值，橙色部分是利用插值法给出的值。最小值没有变化。

当然，f的域是多维的。因此，对于同一个f的取值，可以有多个w相对应。也就是说输入的ω的集合是一个多面体，输出的f可以是相同的值。自然地，在 f 的域中有许多这样的多面体。超参数 λ 有效地通过扰动求解器输入 ω 来使多面体偏移。定义了分段仿射目标的插值器 g 将多面体的偏移边界与原始边界相连。

如下图所示，取值 f(y2) 的多面体边界偏移至了取值 f(y1) 处。这也直观地解释了为什么更倾向使用较大的超参数λ。偏移量必须足够大才能获得提供有用梯度的插值器g

首先，定义一个扰动优化问题的解决方案，其中扰动由超参数λ控制，公式如下：

请到「今天看啥」查看全文