用深度学习解决Bongard问题

Bongard问题是苏联计算机科学家Mikhail Bongard提出的。从20世纪60年代，他致力于研究模式识别，并且设计了100个这样的谜题，使之成为评判模式识别能力的一个好基准。而且这些谜题对人和算法都具有挑战性。举个简单例子：

如图所示，左边的6张图片符合某种规则，而右边的图片则符合另外一种规则。要解决这个问题，需要了解模式并找出它们各自的规则（即解决方案）。规则：“左边：三角形，右边：四边形”。

这个例子很简单，几秒钟就能搞定，但也有更难的问题，例如：

你可以试着找找规则，测试下自己的模式识别能力，答案请点击：22，29，37，54。

这些问题在Douglas Hofstadter于1979年出版的《哥德尔，埃舍尔，巴赫—集异璧之大成》一书中出现后更广为人知。Hofstadter的博士生Harry Foundalis建立了一个自动化系统来解决他的博士研究项目，这个系统称为“Phaeco”。这个程序不仅能解决Bongard问题，而且是认知视觉模式识别的一种架构。

深度学习和Bongard问题

2006年创建的Phaeco影响非常大，因为它不仅能演示15个问题的解决方案，而且在许多情况下效率比人类还要快。其实它能够解决更多的问题，但是需要额外的工作来增强特征提取器或者探测器。

最近人工智能和ML的研究取得了显著的进展。卷积神经网络（CNN）实现在GPU上已经赢得了大量的ImageNet竞争，近年来，CNN算法和体系结构一直在不断改进。

所以我想，利用深度学习方法能够帮助解决Bongard问题吗？Bongard问题激发了我对深度学习的研究，但是由于它是基于简化的图像，而深度学习只有很少的生产图像的类，导致对原始的Bongard问题的答案并不确定。

现在我决定尝试解决这个问题。

问题的形成和方法

将深度学习方法应用于Bongard问题至少会有两个问题。

1、这是一次性学习问题。深度学习效果最好的应用都是基于监督学习的。例如，对数百万张图片进行训练并分类。在这种情况下，神经网络显示出了与人类相似甚至更好的表现。

但是如果仅仅从几个例子中学习，在“一次性学习”中，机器学习方法在灵活性和性能方面远不如人类。BPs每个类只有6个例子，这使得很难用算法解决。

2、这实际上是一个多模式的学习问题。也就是说输入的是图像形式，而输出的是以自然语言描述的分类规则的形式。虽然已经存在一些解决这些问题的方法，但是我没找到一个明确的解决方案。所以我决定以更简单的东西开始，以最终扩展到完整的问题公式为目标。

你可以将Bongard问题的解决方案作为一个分类问题，而不是一个对它规则的口头描述。在这种情况下，12张图片可以被分成两组：10张为“训练”图片，2张为“测试”图片。对于训练图片来说，它明确的知道自己属于哪个类，左边还是右边。而测试图片是随机交换的，它们属于哪个类是未知的。要解决这个问题就意味着先看“训练”图像，然后再决定“测试”图像属于哪个类。

图三展示了这个公式的分类模式。

图3

现在，通过简化问题描述，我决定使用转移学习来实际解决问题。它是单点学习的方法之一，其在视觉类比中显示了很好的效果。首先，要在类似目标问题的示例中多次训练模型，然后重用该模型的相关参数。

深度神经网络学习训练数据的层次化特征表示。如果要在Bongard图像上训练一个卷积神经网络，它将先学习不同的几何形状的相应特征，每个特征可以被看成一个过滤器。如果存在对应的特征，就会激活对应分类器。

为了训练一个特征提取神经网络（NN），我必须创建一个新的数据集而不能用BP的图像，因为它们太少了而且相似性太少。

合成数据集

为了对特征提取网络进行训练，我生成了一组类似于Bongard问题中的图像的随机图像。每幅图像都包括一个几何形状，并在随机位置，按随机的比例，随机的旋转。如果形状是闭合的，还可以随机的填充成黑色。该组总共24个类，示例如下：

我生成了1M图像的训练集，以及10K图像的测试集。图像链接。

神经网络

为了训练生成的合成图像的分类器，我是用了一个相对较小的神经网络。它是基于“Darknet Reference”模型的，并因为输入图像相对较小而删除了一些maxpool图层。它有9个卷积层，架构描述如下所示；

经过8 epochs的数据训练后，它收敛到了可以接受的精确度：top 1：0.848000，top 2：0.968000。

神经网络输出处理

为Bongard问题做一个分类器的第一步是将所有12张图像通过神经网络的正向传递。在卷积神经网络中，每一层都有一组具有共享权重的过滤器，每个过滤器的响应形成一个特征映射。图6显示了所有层的特征图。输入图像位于左侧，由左至右依次按层进行处理。

激活映射中的每个值（每个“像素”）都有可能是一个特性。但是这些特征的值并不意味着输入图像的位置、方向、大小和其他参数不变。基于这一特性仅在10个图像上训练出的分类器可能找不到一个抽象的分类规则，但是很快就能适应这种分类。

为了使特征转换不变，要将每个特征映射以如下方式变换成单个二进制特征：1）标准化跨层特征图，2）将阈值设置为0.3（图7），3）如果特征映射的值高于阈值，则将生成的特性值设为1，否则为0（图8）。

图7 归一化和阈值化后的特征映射(原页面可以水平滚动)

图8 基于特征映射的二值制特征(原网页该图片可以水平滚动)

通过这种方式每个图像都能被CNN描述。我只是用了6-10层的特性，在这些图层上一共有1050个特征映射，这意味着每个图像都要用一个长度为1050的二进制向量来描述。

寻找解决问题的分类器

提取到特征后，就可以把它们用于实际的分类问题了。现在我决定使用最简单的分类器—一个决策树。它通常是复杂分类器的一部分，但在这种情况下最简单的分类器就足够了。用了这种分类器后，只需要一个特征值就能判断出图像属于左边还是右边了。

要想学习这个规则的算法其实很简单，就是一个简单的直接搜索。它可以通过举例来演示：

1）对10个训练图像进行特征提取。如上所述，对每个图像都用一个二元特征向量来表示，该向量从NN角度描述这个图像。

图9基于CNN特性的二进制描述符

2）对于每个特征，检查所有10个训练图像的值。如果5个左图像的特征值和5个右图想的特征值不同，那么它就有可能成为分类器。

3）如果有好几个分类器，那么就需要一个验证标准来选择出其中一个。我们可以通过比较两个测试图像的特征值：因为图像属于不同类，所以特征值应该是不同的。忽略测试类的精确度，只把它们特征值是否相等用作验证标准。

4）把通过验证的分类器应用于测试图像，以检查是否能够正确分类。如果是正确的，问题就被认为是正确解决了。

5）如果没有发现规则或者没有规则通过验证，那么问题就被认为是未解决的。

表1展示了搜索6号问题分类特征的示例(如图1所示)。所有的特征中，只显示在左边图像和右边图像的特征值不同时的特征。只有特性731通过了验证，且经过测试后发现是正确的。

图1、问题6的特性分析

表2显示了错误分类的示例（问题62）。虽然这两个特性被选为分类器并通过了验证，但是对测试图像还是显示了错误的结果。

表2：问题62的错误分析

如上所示数据可视化以及分类的代码在github上。

结果分析

把以上算法应用在232个问题上进行运算，结果如下：解决了47个，正确了41个，所以，解决率为20%，正确率为87%。

为了更好地显示结果，解决了的问题在表3中用不同颜色所示，绿色-正确，红色-不正确。

表3：已解决问题

问题集的不同部分具有不同的复杂性，根据结果可知前几十个问题比较简单。如图10所示，准确性依赖于问题数。

图10 解决问题的正确率，按问题序数排序

表4.显示了由不同作者设计的问题的准确性。由M.Bongard设计的前100个问题用本文说的算法最容易解决，其余的问题则更具挑战性。

表4：不同作者设计的问题的平均精度

H.Foundalis在他的论文中收集了人们在解决问题1-100时的成绩数据。图11显示了成绩排名前20的正确率。所有的问题都是独一无二的而且结果也各不相同，这表明，即使是对人类来说，有些问题也是相当具有挑战性的。

图11 人类求解Bongard问题时的精度

结论

现在一些简单的深度学习方法对解决Bongard问题非常有用，至少在该问题简化的分类形式下是这样的。有趣的是，M.Bongard几乎在《模式识别》中预测了一些类似的方法。在该实例中，特征空间要通过预先训练一个神经网络来对图像进行分类，使其与问题域中的图像相似。原始问题的表述包括用自然语言解释分类规则，这对人们来说是相当容易的，这对于基于手工构造特征与模式检测器的“经典”算法（如“Phaeco”）来讲，似乎也是可能的。但是对于神经网络来说，具有透明和可解释的解决方案是一个已知的弱点，因此原始问题对神经网络可能更具有挑战性。有几种方法可以解决这个问题：

创建一个包括图像和Bongard问题中规则解释的多模态合成数据集，并将其用于监督学习。但是，产生有意义的谜题本身是很困难的，即使有可能产生，我也不确定迁移学习在该情况下是否仍有效。

CNN可视化方法可以用来解释解决方案。即通过突出显示用于分类的像素，并显示哪些模式是由用于分类的CNN滤波器所表示的。关于是否将视觉解释和口头解释看做是一样恰当的，值得进一步探讨的。

生成式神经网络架构也可以用于该问题，如变分自编码器(VAE)或生成式的对抗性网络(GAN)。在这种情况下，就是“用例子来解释”。

“我理解不了我创造不出来的东西。”——理查德·费曼

套用这句名言：“我能创造的，我就能理解”。NN会在Bongard问题中生成新的图像示例，如果生成的图像捕获了分类规则所表达的概念，那么它就足以显示神经网络对问题的理解。

总的来说，Bongard问题将仍然是机器学习的一个挑战性的基准。

原文：https://k10v.github.io/2018/02/25/Solving-Bongard-problems-with-deep-learning/?spm=a2c4e.11153959.blogcont522572.18.67fc6115V6EeJ2

－报名学习挑战百万年薪－