深度学习解决邦加德模式识别问题

翁加德问题是由苏联计算机科学家米哈伊尔·邦加德提出的。他从 20 世纪 60 年代开始研究模式识别，并设计了 100 个这样的谜题，作为评估模式识别能力的良好基准。谜题对于人类和算法来说都是具有挑战性的。我举一个简单的例子：

如图所示，左边的6张图像遵循一定的规则，而右边的图像遵循另一个规则。要解决这个问题，就需要理解公式并找到其对应的规则（即解）。规则：“左边：三角形，右边：四边形”。

这个例子很简单，几秒钟就可以解决，但也有比较难的题，比如：

你可以尝试找出规律，测试一下你的模式识别能力。如需答案，请点击：22、29、37、54。

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

深度学习和 Bongard 问题

2006 年创建的 Phaeco 非常有影响力，因为它不仅展示了 15 个问题的解决方案，而且在许多情况下比人类更快。它实际上可以解决更多问题，但需要额外的工作来改进提取器或特征检测器。

人工智能和机器学习研究最近取得了显着进展。卷积神经网络（CNN）的 GPU 实现在 ImageNet 竞赛中赢得了很多胜利，并且 CNN 算法和架构近年来不断改进。

所以我想，用深度学习的方法可以帮助解决Bongard问题吗？ Bongard 问题启发了我的深度学习研究，但由于它基于简化图像，而深度学习只有几个类来创建图像，因此原始 Bongard 问题的答案并不确定。

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

问题表述和方法

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

1，这是一个一次性教育问题。最好的深度学习应用程序基于监督学习。例如，对数百万张图像进行训练并对它们进行分类。在这种情况下，神经网络表现出与人类相似甚至更好的性能。

但如果仅从几个例子来学习，机器学习方法在“一次性学习”的灵活性和性能方面比人类差很多。 BP 每类只有 6 个示例，这使得算法求解变得困难。

2，这实际上是一个多模态学习问题。即输入是图像的形式，输出是用自然语言描述的分类规则的形式。虽然这些问题的一些解决方案已经存在，但我还没有找到明确的解决方案。所以我决定从更简单的事情开始，目的是将其扩展到整个问题的表述。

您可以将解决邦加德问题视为分类问题，而不是对其规则的口头描述。在这种情况下，12 个图像可以分为两组：10 个“训练”图像和 2 个“测试”图像。通过训练图片，他清楚地知道自己属于哪一类，左还是右。虽然测试图像是随机交换的，但不知道它们属于哪一类。解决这个问题意味着首先查看“训练”图像，然后确定“测试”图像属于哪个类。

图3展示了该公式的分类模型。

图3

现在，通过简化问题描述，我决定使用迁移学习来实际解决问题。它是在视觉类比中表现出很好效果的单点学习方法之一。首先，在与目标问题类似的示例上对模型进行多次训练，然后重新应用相关模型参数。

深度神经网络学习训练数据的分层特征表示。为了在 Bongard 图像上训练卷积神经网络，它首先学习不同几何形状的相应特征，每个元素可以看作一个过滤器。如果有对应的特征，则激活对应的分类器。

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

合成数据集

为了训练特征提取网络，我生成了一组与 Bongard 问题中的图像类似的随机图像。每个图像由随机位置、随机比例和随机旋转的几何形状组成。如果形状是封闭的，也可以随机填充黑色。这个集合总共有24个类，示例如下：

我生成了1M图像的训练集和10K图像的测试集。 图片链接。

神经网络

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

经过 8 个 epoch 的数据训练后，收敛到可接受的精度：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 张练习图像上进行特征提取。如上所述，每个图像都由一个二值向量表示，该二值向量从神经网络的角度描述图像。

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

2）对于每个特征，检查所有10张训练图像的值。如果左五幅图像的特征值与右五幅图像的特征值不同，则可以成为一个分类器。

3）如果有多个分类器，则需要一个验证标准来选择其中一个。我们可以比较两个测试图像的属性值：因为图像属于不同的类，所以属性值应该不同。忽略测试类的准确性，仅使用其特征值的相等性作为验证标准。

4）将经过验证的分类器应用到测试图像上，检查是否可以正确分类。如果正确，则认为问题已正确解决。

5) 如果没有找到规则或者没有规则通过验证，则认为问题未解决。

表1显示了搜索第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) 也可以用于解决此问题。在这种情况下，它是“用例子解释”。

“我无法理解我无法创造的东西。” - Richard Feynman

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

总体而言，Bongard 问题仍将是机器学习的一个具有挑战性的基准。