用深度学习解决Bongard问题

原文链接：https://k10v.github.io/2018/02/25/Solving-Bongard-problems-with-deep-learning/

原文作者：Sergii Kharagorgiev

用深度学习解决Bongard问题

2018年2月25日

Bongard问题是以它的发明者——苏联计算机科学家Mikhail Bongard命名的。他在1960年代从事模式识别研究。他设计了100个这样的谜题，作为衡量(人或算法的)模式识别能力的一个良好基准。这些问题对人和算法而言，似乎都是一种挑战。以下是一个示例：

图1

左边的六个图像符合一个规则，或者一个模式，而右边的六个图像符合一个不同的规则(通常是个相反的规则)。要解决这个问题，我们需要理解模式，并找出规则(该规则便是问题的解)。在这种情况下，规则是：“左边：三角形；右边：四边形”。

这个很简单，可能只需要几秒钟就能搞清楚。但也有更困难的问题，例如：

问题#22

问题#29

问题#37

问题#54

你可以尝试找出这些规则以测试一下自己的(模式识别能力)。上面几个问题的解在这里有：22,29,37,54。

这些问题在1979年出版的《Gödel, Escher, Bach: An Eternal Golden Braid》一书中出现后，变得更为人所知了[2]。该书的作者Douglas Hofstadter本身也是Bongard问题的设计者之一。Hofstadter的博士生Harry Foundalis建立了一个解决该问题的自动化系统来作为他的博士研究项目[3]。该系统(叫做Phaeco)不仅只是解决Bongard问题的程序，而且更是一个视觉模式识别的认知架构。

深度学习和Bongard问题

创建于2006年的Phaeco的学习结果令人印象深刻。它能够展示15个问题的解(在H.Foundalis所收集的180个问题之外)，求解的过程在很多情况下都快于人类。它应该能够解决更多的问题，但它将需要附加外延工程，增强其特征提取器与检测器之后才能达到目的[3]。

近年来，AI(人工智能)和ML(机器学习)有了长足的进步。深度神经网络在大量模式识别比赛中取胜，并且在某些情况下表现出超人的性能[4]。在GPU上加速实现的带有最大池化层的卷积神经网络(CNN)在2012赢得了大规模ImageNet比赛的胜利[4]。而且近年来CNN算法和体系结构都在不断地进行改进。

所以，我不禁想知道，深度学习方法对解决Bongard问题是否有用。在试图搜索了任何关于该想法的信息之后，我发现在网上的讨论中只有一个问题：

“深度学习”是自1990年代以来人工智能取得的唯一有趣的进步。但我很肯定深度学习不会在Bongard问题上取得任何进展。如果事实证明我错了，那我将会非常震惊而又兴奋。[https://meaningness.com/metablog/bongard-meta-rationality] 谁知道这些问题是否用深度学习或者其他新方法获得了更简单的解决方法？https://news.ycombinator.com/item?id=12064188

Bongard问题激发了一些深度学习研究[5]。但是该研究是基于简化图像的，仅有少量类别的生成图像。对于最初的Bongard问题，该研究结果并不是结论性的。

我决定尝试创建一个问题求解器。从我知道了这个问题开始，这个问题求解器就是我想要做的事情。

问题形成与方法

将深度学习方法应用于Bongard问题，至少存在两个主要问题。

1. 这是个单点学习问题。深度学习最有效果的应用是基于有监督学习的。例如，在对数百万幅图像进行训练后，再对图像类别进行分类时，取得了很好的效果。在这种情况下，神经网络显示出与人类相似的(甚至更好的)性能。

但是，在“单点学习”中，即从少数样本中进行学习时，在灵活性和性能方面，机器学习方法远远比不上人类。对于每个类别，BP(Bongard问题)只有6个示例，这就是算法为什么很难解决该问题的原因。

2. 它实际上是一个多模态学习问题。即输入是图像形式，输出是分类规则的自然语言形式的描述。已存在一些解决这类问题的方法，但从中我没有找到一个清晰的思路来解决该问题。我决定从一些更简单的东西开始，该简单问题的目标是方便以后扩展形成问题的完整形式。

与其把求解Bongard问题作为某规则的口头描述，不如将其看作是一个分类问题。在该情形下，可将12幅图像分成两组：10组作为“训练”图像，2组作为“测试”图像。对于训练图像，知道他们属于左或右中的哪一类。测试图像随机交换，类未知。

于是，解决该问题意味着首先要看“训练”图像，然后确定“测试”图像的类。

图3展示了该构想下问题的形式。

图3

现在，通过简化后的问题假设，来解决真正要解决的问题时，我决定采用迁移学习。这是单点学习的方法之一，其在视觉类比中显示了很好的效果[6,7]。首先，在与目标问题相似的问题中，在许多样本上对模型进行训练，然后再利用该模型的相关参数解决目标问题。

深度神经网络学习训练数据的层次化特征表示[8]。如果在Bongard图像上训练卷积神经网络，它将学习到对应于不同几何形状及其部件的特征。每个特征都可以看作是一个过滤器。如果存在特征，则会激活特定的层和单元，而分类器则可以使用这些激活与否的状态。

为了训练一个可以提取特征的神经网络(NN)，不可能利用来自于BP(Bongard问题)的图像。他们太少，只有几百，而且他们差异巨大，以至于不能泛化出有意义的信息。所以我不得不创建出一个新的数据集。

合成数据集

为了对提取特征的神经网络进行预训练，我生成了一组随机图像，类似于Bongard问题中出现的图像，这些图像主要包含几何原语。每幅图像都包含一个几何形状：该形状具有任意的位置、尺度和旋转；如果形状是封闭的，则将其随机填充为黑色实心。这些图像总计有24个类，这些类的描述和示例图像如下图所示：

图4(原网页中点击update可以更新图中的图形)

我为训练集生成了100万张图像，为测试集生成了1万张图像。

神经网络

为了利用合成图像训练出分类器，我使用了一个相对较小的神经网络。该网络基于“Darknet Reference”模型[9]，去除了一些最大值池化层(因为输入图像相对较小)。它有9个卷积层，结构描述如下：

图5 神经网络架构

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

神经网络输出处理

为Bongard问题设计分类器的第一步是将所有的12幅图像通过神经网络的前向过程。在卷积神经网络中，每一层都有一组具有共享权值的滤波器，每个滤波器的响应形成一个特征映射。图6显示了所有层的特征图。输入图像位于左侧，从左到右逐层对原始图像进行处理。

图6 CNN特征图(原网页该图片可以左右滚动)

激活图中的每个值(每个“像素”)都可能是一个特征。但是，这些特征的值相对于输入图像中对象的位置、方向、大小以及其他参数而言，并不是固定不变的。基于这些特征训练的分类器，仅在10幅图像上就无法找到一个抽象的分类规则，而是很快就发生过拟合。

为了使特征在不同的变换下是固定的，每个特征图用如下方式转换成单个二进制特征：1)对跨层的特征图进行归一化，2)对所有的值取阈值，将阈值设置为0.3(图7)；2)如果特征图中的任何值高于阈值，则将生成的新特征设置为1，否则设置为0(图8)。

图7 归一化和阈值化后的特征图(原网页该图片可以水平滚动)

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

这样，每幅图像都可以由CNN特征描述。我忽略了前几个层，只使用了6-10层的特征；这些图层上有1050个特征图，因此每幅图像都使用长度为1050的二进制向量来描述。

为问题的解寻找分类器

提取特征后，便可将这些特征用于实际问题中图像的分类。我决定使用最简单的分类器——一个决策树桩(或单个规则)。它通常被用作更复杂分类器的一部分，但在这种情况下它可能就足够了。该分类器只使用一个特征的值来判断图像属于左或右组。

学习这个规则的算法仅仅是一个简单的直接检索。该算法可以通过解决问题#6的例子来演示：

1) 对于10幅训练图像，提取上述特征。对于每一幅图像，我们都获得一个二值特征向量，该特征从NN(神经网络)的角度描述了这幅图像。

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

2)对每个特征，核查了10幅训练图像的特征值。如果5幅左图像的特征值与5幅右图像的特征值不同，则选择它作为可能的分类器。

3)如果发现多个分类器，则需要验证准则来选择一个分类器。可以比较两个测试图像的特征值：特征值应该是不同的，因为它们属于不同的类这一点是已知的。忽略测试图片的确切类别，只把它们是否相等作为验证标准。

4)第一个通过验证的分类器规将会应用到图像的检测，来验证分类的正确性。如果分类正确，就认为正确解决了该问题。

5)如果没有发现任何规则，或者没有任何规则通过验证，则认为该问题未得到解决。

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

表1 问题#6的特征分析

表2显示了错分的问题#62的例子。有两个特征可以作为分类器使用，它们都通过了验证，但是测试图像上却获得了不正确的结果。

表2 问题#62的特征分析

如上进行可视化以及分类的代码在github上，https://github.com/coolvision/bongard-problems-cnn

结果分析

如上的算法在232个问题(来自于由H. Foundalis制作的列表)中的结果如下：47个获得解决，41个正确。解决率20%，正确率87%。

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

表3 已解决问题

问题集的不同部分具有不同的复杂性，前几十个问题比较简单。这也反映在实验结果中。图10显示，准确性依赖于问题的序数(正确率是将连续20个问题作为一组来计算的)。

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

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

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

在他的论文中，H.Foundalis收集了关于人类解决问题#1-100时的性能数据。图11展示了人类求解前20个问题的准确性。所有的问题都是独特的，正确率结果也不尽相同，但它表明，至少有些问题对人来说也是相当具有挑战性的。

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

结论

简单的现成的深度学习方法对于解决Bongard问题是有用的，至少在该问题简化的分类形式下是这样的。有趣的是，M.Bongard实际上在《模式识别》[1]中预言了一些类似于此处所描述方法的方法：

“……学习的目的不在于找到分类规则(例如，超平面)，而在于找到一个可以分离的特征空间。”

这里，是通过预先训练可以对与问题域中图像相似的图像进行分类的神经网络，来创建特征空间的。

“……在图像空间被较好地转换为特征空间之后，几乎不存在寻找分类规则的问题。因为到那时，分类规则已经被自动地找到了。“

原始问题的表述包括用自然语言解释分类规则，这对人们来说是相当容易的；这对于基于手工构造特征与模式检测器的“经典”算法(如“Phaeco”[3])来讲，似乎也是可能的。但是对于神经网络来说，具有透明和可解释的解决方案是一个已知的弱点，因此原始问题对神经网络可能更具有挑战性。有几种方法可以解决这个问题：

1. 创建一个包括图像和Bongard问题中规则解释的多模态合成数据集，并将其用于有监督学习。但是，产生有意义的谜题本身是很困难的，即使有可能产生，我也不确定迁移学习在该情况下是否仍有效。
2. CNN可视化方法可以用来解释问题的解。该种情况下，可以直观地解释问题的解。即通过突出显示用于分类的像素，并显示哪些模式是由用于分类的CNN滤波器所表示的。关于是否将视觉解释和口头解释看做是一样恰当的，是值得进一步探讨的。但在我看来，这似乎是可以接受的。
3. 生成式神经网络架构也可以用于该问题，如变分自编码器(VAE)或者生成式对抗性网络(GAN)。该种情况下，正是“用例子来进行解释的”。

“我不能理解那些我不能创造的东西。”

理查德·费曼

改写一下这句话：“我能创造的，我就能理解”。NN(神经网络)从Bongard问题中生成新的图像示例，如果生成的图像捕获了分类规则所表达的概念，就足以显示神经网络对问题的理解。

总的来说，即使在50年后，Bongard问题对机器学习来说，似乎仍然是一个具有挑战性的基准。这是一个很好的学习项目，我计划在该问题的求解器上进行继续研究。

#参考文献

1. Bongard, Mikhail M. (1970). Pattern Recognition. New York: Spartan Books.
2. Hofstadter, D. R. (1979). Gödel, Escher, Bach: an Eternal Golden Braid. New York: Basic Books.
3. Foundalis, H. (2006). Phaeaco: A Cognitive Architecture Inspired by Bongard’s Problems. Doctoral dissertation, Indiana University, Center for Research on Concepts and Cognition (CRCC), Bloomington, Indiana.
4. Schmidhuber, J. (2015). Deep Learning in Neural Networks: An Overview. Neural Networks. 61: 85–117.
5. Stabinger, Sebastian & Rodríguez-Sánchez, Antonio & Piater, Justus. (2016). Learning Abstract Classes using Deep Learning. Proceedings of the 9th EAI International Conference on Bio-inspired Information and Communications Technologies. 524-528.
6. L. Fei-Fei, R. Fergus and P. Perona. (2006). One-Shot learning of object categories. IEEE Trans. Pattern Analysis and Machine Intelligence. Vol28(4): 594 - 611
7. Liao, Jing & Yao, Yuan & Yuan, Lu & Hua, Gang & Bing Kang, Sing. (2017). Visual Attribute Transfer through Deep Image Analogy. ACM Transactions on Graphics. 36.
8. Honglak Lee, Roger Grosse, Rajesh Ranganath, and Andrew Y. Ng. 2009. Convolutional deep belief networks for scalable unsupervised learning of hierarchical representations. In Proceedings of the 26th Annual International Conference on Machine Learning (ICML ‘09). ACM, New York, NY, USA, 609-616.
9. Joseph Redmon. Darknet: Open Source Neural Networks in C. 2013–2016. http://pjreddie.com/darknet/