麻省理工学院MIT-ICLR2020《神经网络能推断出什么?》

神经网络已经成功地完成了许多推理任务。从经验上看，这些任务需要专门的网络结构，例如，图神经网络(GNNs)在许多这样的任务中表现良好，而较少结构的网络会失败。从理论上讲，尽管网络结构具有相同的表达能力，但人们对网络结构为什么以及何时比其他网络结构更能泛化的理解是有限的。本文通过研究网络的计算结构与相关推理过程的算法结构之间的一致性，建立了一个描述网络能很好学习哪些推理任务的框架。我们正式定义了这种算法对齐，并推导出一个随更好的对齐而减小的样本复杂度界。该框架为流行推理模型的经验成功提供了一个解释，并指出了它们的局限性。例如，我们通过一个强大的算法范例——动态规划(DP)，将看似不同的推理任务，如直觉物理、可视化问题回答和最短路径统一起来。我们证明了gnn与DP是一致的，因此可以解决这些问题。在一些推理任务中，我们的理论得到了实证结果的支持。