首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

用深度学习解决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

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

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180317A096Z500?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券