数独游戏如何用深度学习攻破?

姓名：张玉军  17021210876

转载自：http://www.jianshu.com/p/d3d7528b2963

【嵌牛导读】数独游戏如何用深度学习攻破？RRN是个什么东东？

【嵌牛鼻子】数独游戏,深度学习,RRN

【嵌牛提问】数独游戏如何用深度学习攻破？

【嵌牛正文】引言

什么是关系推理？考虑上面的图像，不要把这看成是球体，立方体等等。我们可以用数百万个数字构成图像像素值的来考虑它或者图像中所有边缘的角度或者考虑每个10x10像素区域。

试着回答下面的问题：“大球体左边的棕色金属物体留下的圆柱体的大小是多少？”这是来自CLEVR数据集的示例问题。为了回答它，你需要考虑对象相对于彼此的相对位置。这个对象和交互中心思维被称为关系推理，它是人类智力的核心部分。

深度神经网络非常擅长识别物体，但是当涉及到它们的相互作用的推理时，即使是最先进的神经网络也不过如此。

例如，现有的卷积网络可以很容易地识别上面图像中的每个对象，但是由于它需要关于彼此的关于对象的推理，所以它没有回答我们刚刚提到的那个问题。

Adam Santoro和他的合作者者提出了关系网（RN）。这是一个非常简单的模块，可以将关系推理能力添加到任何神经网络中。他们将一个RN添加到标准的卷积网络中，并在CLEVR数据集上训练最终获得了超人类性能。他们还将其用于BaBi——一个文本问题解答任务，而且解决了20个任务中的18个。

RN在深度学习领域向前迈出了重要一步，但它也有其局限性。它的构建方式是，每个被识别的对象只能与其他被识别的对象进行一次交互，之后网络必须给出答案。这是RN的限制，因为它不能推导导出的交互，即对象A影响了对象B，反过来影响对象C等等。在RN中，对象A必须直接影响对象C，或者根本不能影响对象C。这看起来这种方法有些呆萌。

为了解决这个限制，我们引入了递归关系网络（RRN）。RRN执行多个步骤，而不是仅执行关联推理的单个步骤。在每个步骤中，每个对象都受到其他对象的影响，同时也考虑到它自己以前的状态。这允许交互可以从一个对象传播到另一个对象，从而形成复杂的交互链。

为了表明RRN可以解决需要非常复杂的关系推理的问题，我们使用它来解决数独（Sudoku）难题。

现在，有很多算法来解决Sudokus。RRN在两个重要的方面不同于这些传统的算法：

1.这是一个神经网络模块，从数据中学习算法，而不是手工制作。

2.它可以被添加到任何其他的神经网络中进行端到端的训练，并给神经网络赋予一个复杂的关系推理能力。

对于那些不熟悉Sudoku拼图的人来说，这是一个数字难题，在9x9网格中有81个单元格。每个单元格都是空的，或者从一开始就包含一个数字（1-9）。我们的目标是用一个数字填充每个空单元格，使得每列，每行和3×3不重叠的数字包含1到9的数字。看到下面的两个图像，一个相对简单的数独：30个给定的细胞和红色的解决方案。

你不能一步步推断Sudoku的解决方案。它需要很多步骤的方法演绎，中间结果，并可能尝试几个部分的解决方案之前找到正确的。

我们训练了一个RRN来解决Sudokus，通过考虑每个单元格的一个对象，这个对象影响到同一行、列和框中的每个其他单元格。我们没有告诉它任何策略，也没有提供任何其他的提示。神经网络学到了一个强大的策略，即使是最困难的数独也只有17个回应，成功率达到96.6％。为了比较，其他的神经网络结构并未能解决这些难题中的任何一个，尽管具有更多参数且被训练更长时间。

在每个步骤，RRN为1-9个数字上的每个小区输出一个概率分布，表示网络认为应该在该小区中的哪个数字。

这是巴比数据集中一个简单的问题。

玛丽在那里喝牛奶。

约翰去了卧室。

桑德拉回到了厨房。

玛丽走向走廊。

牛奶在哪里？

我们也训练了BaBi数据集的RRN，并且我们解决了19/20个任务。相比之下RN同样也解决了19/20的最先进的稀疏的可微神经计算机。值得注意的是，RRN花费了大约24小时的时间在四台GPU上进行训练，而RN在10台GPU上花费了几天的时间。我们认为这是因为RRN被设计来解决需要多于一个推理步骤的问题。

递归关系网络（RRN）是一个通用模块，它可以用强大的关系推理能力来增强任何神经网络模型性能。

我们认为关系推理对许多任务都很重要。例如，玩游戏，Go或Starcraft II，需要识别和推理游戏中的对象，以预测行动的长期结果。另一个例子是自驾车。要安全驾驶，必须识别相关的物体，例如汽车，骑自行车的人，停车标志等，以及他们将如何相互作用的原因。