解决Bongard问题：一种强化学习因果方法,2022
解决Bongard问题：一种强化学习因果方法,2022
Towards a solution to bongard problems: A causal approach
面向解决Bongard问题：一种因果方法
https://arxiv.org/abs/2206.07196
相关内容：
朱松纯团队2019：RAVEN ; and I-RAVEN数据集
摘要
到目前为止，Bongard问题（BP）仍然是AI历史上为数不多的尚未被当前时代强大模型攻克的堡垒之一。我们使用来自因果关系和AI/ML交叉领域的现代技术进行系统分析，以谦逊的努力重振围绕BP的研究。具体来说，我们首先将BP编译成一个马尔可夫决策过程，然后对数据生成过程提出因果假设，论证它们对BP的适用性，最后应用强化学习技术在满足因果假设的情况下解决BP。
1 BONGARD的回归
在人工智能领域不断涌现的成功故事中，例如在医学图像分析[Ker等人，2017]、粒子物理学[Bourilkov，2019]、药物发现[Chen等人，2018]或网络安全[Xin等人，2018]等领域，机器学习算法变得越来越复杂和精细。数据驱动的人工智能更加高效，并且得到了越来越强大的硬件的支持，这使得在许多领域取得了超越人类视觉认知水平的进展（参见最近提出的基础模型[Bommasani等人，2021]及其一些典型候选者[Ramesh等人，2021]）。
然而，缺乏可靠的推理能力最近在社区内引发了一场辩论[Marcus，2022]。这种缺乏在视觉认知任务中尤为明显，这些任务的解决方案需要在只提供少量样本的情况下进行抽象和组合，而Bongard问题（BP）[Bongard等人，1970]就是这类任务的一个典型例子。俄罗斯计算机科学家米哈伊尔·邦加德（Mikhail Bongard）提出了一套原始的100个BP，设计了一个任务，今天在评估计算机器与人类大脑所启用的推理能力方面比以往任何时候都更加相关。直到今天，它们在很大程度上仍未被AI/ML算法解决，甚至人类在扩展的BP集合中也往往陷入困境[Mitchell，2019]。
BP是一组图像，其中我们被呈现两组图像，我们必须找到一组中存在但另一组中缺失的一组属性，反之亦然。这些图像起初看起来相当简单和基本，因为它们通常只包含简单的形状，并且仅限于黑白两色，但底层任务需要“良好的抽象和模式识别能力”。即使对人类来说，这也是一项具有挑战性的任务，因为他们得出解决方案的同时，仍然无法认识到他们是如何得出所述解决方案的。由于其紧凑性和非常一般的性质，BP在一个单一的框架内展示了当今许多最重要的ML研究问题，它们的解决方案已被描述为非常接近支撑人类认知的核心方面[Hofstadter，2006]。
在这项工作中，我们打算用来自AI/ML和Pearlian因果关系概念交叉领域的现代技术重振长期存在的BP[Pearl，2009]。我们通过从强化学习（RL）[Sutton和Barto，2018]的角度来解决这个任务，因为这使我们能够采取自然的因果方法，其中环境中的行动对应于Pearlian意义上的干预。Zhang和Bareinboim[2017]等人已经研究了这种因果RL性质的初步方法。前者提出了一种边界过程，我们打算使用一种适应的技术来限制代理在先前从过去经验中收集的数据上的数据采样，以提高样本效率和解决方案的最优性。
为了开始这个想法，我们首先必须将我们的BP编码成一个顺序环境。我们认为这样做可以将解决BP的领域扩展到一个顺序领域，在这个领域中，我们关注两组图像对的组合。因此，我们以更像人类的方式接近BP，因为人类会查看示例和图像比较，以便得出合理的解决方案。这种转换到RL领域使我们能够更具战略性，并且还增加了我们可以尝试学习有意义表示以最好地找到BP中两组的决策边界的样本量。此外，为了充分利用BP提供的少量数据，我们没有首先单独学习图像表示，而是通过使用siamese神经网络架构来查看图像之间的差异，这些架构在过去已经证明对一次性图像识别很有用[Koch等人，2015]。
在我们的实验中，我们试图通过进行消融研究来验证和评估我们提出的每个解决BP的附加功能的性能，并且还关注如何改进当前使用的方法，以进一步提高上述方法的性能。
We make our code publicly available: https://anonymous.4open.science/r/solving-bongard-causal-367E.
2 相关工作
关于解决BP的工作。在过去，已经有多次尝试解决Bongard问题，但成功程度各不相同。这个问题通常通过将过程分为两个子任务来解决，一个是特征提取，另一个是模式识别[Foundalis，2006，Hofstadter，2006]。
在一项有前景的工作中，Depeweg等人[2018]首先将从图像中提取的特征转换为符号视觉词汇，然后尝试通过强大的形式语言和贝叶斯推理来解决BP，使他们甚至能够输出自然语言作为解决方案，但需要大量手工制作的特征和工程。与此类似，Foundalis[2006]遵循一个进化过程来进行特征提取，使用一系列不同的特征提取器，可以从像素表示到更抽象的表示，然后比较这些表示以找到一个令人满意的解决方案。相比之下，还有一些工作通过深度神经网络端到端地解决BP，将图像作为输入，通过神经网络进行隐式特征提取，就像在[Nie等人，2020]中一样，生成类似于BP的合成数据，以帮助学习实际分类器的特征表示，并通过简单地拥有更多数据（即使是合成的）进行数据驱动的图像处理。
可能适用于BP的技术。在BP之外的工作中，我们认识到一些近期关于更一般的基于动作的聚类[Sontakke等人，2021]和解纠缠[Locatello等人，2019]的强大工具。前者将学习空间划分为二进制分区，类似于BP，而后者则在受限数据设置中提出了一个聚类，将不同的变异因素（类似于BP的解决方案组件）进行聚类。
3 对BP的因果方法
我们首先介绍Bongard问题的一般设置，然后介绍一个编译过程，将其编译为一个可用于RL的顺序环境，最后讨论我们对底层数据生成过程的因果假设。
3.1 对BP的一般观点
由米哈伊尔·邦加德设计的原始BP集合包含100个谜题。虽然科学家们已经很容易地将可用的BP谜题数量增加到近400个，但我们还是将自己限制在原始集合中。由于BP在其各自的解决方案中编码了“人类意图”，因此这种限制可以说是合理的。每个BP BPi，其中i ∈ {1, .., 100}都是一个谜题，我们被呈现两组六个图像G1 ⊂ BPi和G2 ⊂ BPi，每个图像表示为xj，其中xj ∈ BPi，j ∈ {1, 2, .., 12}，且G1 ∩ G2 = ∅。目标是找到一组分离属性S，这些属性在一个组的所有图像中都存在，但在另一个组的图像中都不存在。
然而，BP的解决方案并非微不足道，可能是模糊的，因为我们如何复杂地表述S的属性，同一个BP存在多个不同的解决方案/解释。BP的真正解决方案完全取决于邦加德本人想要传达的含义，因此我们也可以将问题框定为一个沟通问题。这增加了解决BP的复杂性，因为没有预定义的属性集，我们可以从中选择一组分离属性。
只看每组中的一张图片也不太可能得出正确的结果，因为BP的设计方式使得只有通过仔细检查一组内的共同属性和对比另一组的属性，才能找到正确的属性集S。这些图像也不是随机生成的，以符合S，而是通常以一种引导求解者得到期望解决方案的方式生成，通过展示非常相似的图像违反某些属性，使其对人类求解者来说最明显。例如，我们可以在图1中看到这一点，其中一组中每张带有彩色边框的图像在另一组中都有一个相同颜色边框的对应图像。这些对应图像通常彼此非常相似，以至于至少一些期望的解决方案属性变得清晰。
为了给出一个BP的示例性讲解，我们将检查图1中的BP。请注意，图像的边框通常不是彩色的，只是用作这个例子的视觉效果。紫色边框的图像暗示了一个解决方案，其中不同的形状可能很重要，而蓝色边框的图像试图表明这可能与一个图像中形状的数量无关。绿色边框的图像暗示了包围属性的可能相关性，再次通过黄色边框的图像进一步强调形状的变化（形状的变化似乎是从三角形到正方形或从正方形到三角形），这也加强了数量确实不重要的假设。
现在你可能会认为，像数量一样，不同的形状并不是决定性的差异，因为两边似乎都包含了相同的一组不同形状，以及一个图像中形状的数量。然而，回到绿色、黄色和红色的配对，我们注意到形状的变化与包围属性是耦合的，即如果一个形状包围了另一个形状，在左边总是圆包围正方形，在右边总是三角形包围正方形，这给我们留下了这个BP的解决方案。
这个讲解向我们展示了，通过逐一查看图像几乎不可能得到解决方案，相反，它们必须被视为相互组合和关联，随着看到更多的图像，解决方案逐渐显现出来。这种引导属性通常被视为一种人类偏见，因为BP是由人类手工制作的，因此强调了试图向求解者传达信息的沟通方面。
3.2 从BP到RL环境
为了解决BP，我们需要将BP构建为某种环境，代理可以与该环境进行交互。为了实现这一点，我们首先将每个BP分成图像元组q := (xi, xj)，通过取两个集合之间以及同一集合内所有可能的图像组合t ∈ BPi × BPi。这为每个BP提供了总共|BPi|^2 = 144对两张图像，总计为|BPi|^2 100 = 14400对所有BP的图像对样本。我们从一个BP的所有图像组合中进行采样，并为每对图像决定它们是否属于同一组。
图2显示了BP的一般RL设置。设st、rt和at为时间步长t = 1, .., T的状态、奖励和动作，其中T是一个episode中的步数。动作对应于将两张图像分配到同一组或将它们分配到不同组at ∈ {0, 1}，当分组正确时给予奖励rt ∈ {0, 1}。状态st是两个图像的2D图像表示，其中每个通道对应一个图像2×w ×h，其中w和h是图像的宽度和高度。我们的目标是找到一个策略π(a, s)，使预期回报E[R|s]最大化，其中
。
3.3 BP的因果假设
除了在RL环境中构建问题外，我们还需要在因果环境中正式构建问题，因为我们想对数据生成过程提出因果假设。因此，我们可以将问题视为一个上下文多臂老虎机（CMAB），因为我们采取的行动不会影响状态，这很容易转化为一个结构因果模型（SCM）[Pearl，2009]，该模型通过函数关系描述了感兴趣变量之间的因果关系。我们的因果假设在图3中示意性地描绘。
我们将BP背后的想法描述为意图U，这是一个未观察到的混杂因素，因为在学习过程中我们不知道BP背后的意图。我们已经将解决BP的任务描述为一个沟通问题，在这里我们看到邦加德试图传达的信息，即意图，直接影响了图像对的状态s、我们给出的奖励r以及我们在每个时间步采取的action a。奖励基于我们采取的行动以及它是否违反了BP的意图。最后，意图是BP中所有示例背后的数据生成过程的唯一混杂因素和来源。
3.4 因果强化学习
在建立了RL环境和一组针对BP的底层SCM的合理因果假设之后，我们现在转向在满足因果约束的情况下将RL应用于我们的BP。让Ht表示直到时间步t的观察历史，使得H1 := s1，对于t = 2, .., T，Ht := (s1, a1, s2, a2, r1, .., st, at, rt−1)。在离线策略设置中，我们观察由行为策略πt生成的动作序列a1:T。在没有未观察到的混杂因素（因果充分性假设）的情况下，我们仅根据我们的策略πt和观察历史来采样我们的动作at，其中at ∼ πt(·|Ht)。但是如果我们有一个未观察到的混杂因素，我们的策略应该考虑其动作来自at ∼ πt(·|Ht, Ut)，同时仍然从at ∼ πt(·|Ht)中采样，因为我们无法访问Ut。
在未观察到的真实设置中，如果我们有两个代理，遵循策略πt和πt，但受到Ut和Ut的混杂，我们不能使用从at ∼ πt(·|Ht)收集的数据来改进从at ∼ πt(·|Ht)采样的另一个策略，因为可能发生负迁移，这可能损害解决方案的最优性和/或样本效率，因为因果效应是不可识别的，因为可忽略性假设不再成立。即使不可识别性不成立，我们仍然可以通过使用它来获得代理的预期奖励的界限，从而利用先前的数据。
对于BP，我们最初没有可以利用的先验数据。此外，通过我们的策略at ∼ πt(·|Ht, BPi)为单个BP采样图像对，其中BPi是当前BP，没有未观察到的混杂，这意味着do-calculus对我们的问题是足够的，因为可忽略性成立。但是，施加因果界限的能力不仅依赖于策略之间的未观察到的混杂，还依赖于上下文的不匹配。
玩一局游戏相当于从一个单一的BP中采样，at ∼ πt(·|Ht, BPi)，所以如果我们改变我们正在看的BP并从它那里采样at ∼ πt(·|Ht, BPj)，其中i = j，那么就会出现上下文的不匹配，因此πt(·|Ht, BPi)和πt(·|Ht, BPj)之间的可忽略性不再成立。然而，在这种情况下，我们可以使用之前从其他BP收集的数据作为具有上下文不匹配的先验数据，根据状态和奖励概率分布施加因果界限，如Zhang和Bareinboim[2017]所示。
这证明了给定一个2臂伯努利老虎机，其中X, Y ∈ {0, 1}，P(x, y)是联合概率分布，pij = P(X = i, Y = j)，那么实验分布E[Y |do(x)]可以被限制为：
这个界限很有趣，因为它向我们展示了即使在联合分布和实验分布之间不可识别的情况下，我们仍然可以对实验分布施加信息性约束。这些因果界限的证明可以在Zhang和Bareinboim[2017]中找到。
4 实证分析
我们在100个原始BP上实证评估了我们之前描述的设置。
4.1 实验设置
通过我们的实验，我们试图评估我们在本文中提出的建议，以解决Bongard问题。我们想知道（Q1）RL是否适合作为BP的学习环境，（Q2）解决BP所需的模型架构，以及（Q3）将因果界限纳入我们的学习设置的影响。
我们扩展了现成的RL算法，使用了定制的模型架构，如Siamese神经网络Koch等人[2015]，因为如图4所示，仅用少量可用数据学习完整的特征表示对于常规的MLP/CNN架构是不可能的。我们改为学习基于图像之间距离函数的特征表示，在BP设置中更关注图像之间的相似性关系。对于（Q1）和（Q2），我们训练了现成的RL算法，使用了不同的模型作为消融研究，以测试在5个随机种子上的性能。我们没有使用CNN架构作为视觉输入，因为常规的CNN倾向于，例如，平移和旋转不变，丢失了解决许多BP通常至关重要的信息。
我们还假设，给定等式1和2，当前的因果界限在BP的情况下不会改善学习，因为它们只依赖于行动-奖励分布，不包括关于当前状态的任何信息，而是为我们提供了进一步改进的可能性的见解。
4.2 结果
图4中对模型架构的评估显示，PPO在使用常规MLP架构时没有学到任何有用的东西，停留在大约72的基线性能，这对应于随机代理的性能，因为我们的最大奖励是144。然而，在图4中，我们还可以看到，使用Siamese神经网络（SNN）架构的PPO优于常规MLP变体，这意味着它学习了一个有用的特征表示。我们相信我们的结果将激发新的兴趣来解决Bongard问题，并作为一个强大的基线进行改进。我们还评估了添加了因果界限的PPO SNN变体，如图5所示。结果清楚地表明，当前的因果界限不仅对学习没有帮助，实际上还阻碍了学习过程，因为它将学习推回到基线性能。
4.3 结果讨论
我们已经评估了（Q2）使用SNN架构和PPO的影响，与使用常规MLP架构的PPO相比，它给了我们更好的性能和更有用的特征表示，后者只给了我们50%的基线性能。这证实了我们的假设，即学习BP图像对的距离函数比学习BP的一般特征空间更可行。这也将使我们能够更好地泛化到以前未见过的BP。这也表明，通过对经典RL方法和算法进行一些调整，比如添加自定义模型架构，RL总体上可以作为BP的学习范式，从而回答了（Q1）。
然而，对于因果界限（Q3）的评估，我们发现它的性能比使用SNN的PPO更差。请注意，这个结果并不令人惊讶，因为因果界限只依赖于行动和奖励分布，但缺少上下文。由于我们有50%的图像对来自同一组，50%的图像对来自不同组，因果界限不会将我们推到随机性能，而是学习50/50的类别分布，在这种情况下是等价的。
5 超越因果界限
在将因果界限纳入学习解决BP的代理后，我们观察到，以当前的形式，这些界限并没有证明是有用的，因为它们最初是为没有上下文信息的MAB设计的，只依赖于行动-奖励分布。这为开发更复杂的因果界限以适应上下文多臂老虎机留下了改进的空间。我们进一步提出了未来工作的可能性，即如何将因果界限扩展到更好地适应CMAB：
（1）创建新的界限，为我们提供关于一般BP结构的信息，可以使我们对来自同一BP的图像对的决策更加明智。例如，我们事先知道一个BP中每个组有多少张图像，因此，如果决策是随机的，那么在已经做出的决策历史的基础上，选择分组的可能性会受到其成为正确分组的可能性的影响。
等式3-6显示了如何通过考虑一个episode的所有行动历史来改进界限。我们将通过旧的界限（来自等式1和等式2）或给定历史的采取行动的概率来限制我们采取的每个行动，无论哪个为我们提供了更紧密的行动界限，因此分别是最小值和最大值的上限和下限。
（2）我们还可以尝试定义新的因果界限，基于之前采样的BP，这些BP包含了额外的信息，如上下文q。我们可以通过查看变异因素来纳入上下文信息。我们将K定义为特定BP的一组变异因素，其中K ∈ Γ，Γ描述了BP的所有可能变异因素的集合，如Γ = {数量，颜色，形状，...}。k := |K|是两个图像之间潜在变异因素的数量。我们可以使用k或k和K一起作为额外的输入来计算新的因果界限，以更好地学习从一对图像到分组分配的更合适的映射。这是受到Sontakke等人[2021]关于因果好奇心的工作的启发。
（3）另一种可能的改进是将SNN架构与LSTM结合起来，因为在理论上，仅基于一对图像的一个示例是不可能得到完美预测的。因此，必须积累整个episode的信息以找到合适的决策边界，如图1所示。
6 结论
我们已经证明，RL在解决BP的设置中是有用的，它使我们能够从因果的角度看待问题，并通过适合BP领域的模型架构扩展最先进的算法，如PPO。然而，对于CMAB和更具体地说对于BP的因果界限还有很多改进的空间，我们已经为此提供了一些初步的步骤和整体展望。此外，为RL中的BP提出的模型架构只是一个第一步，还有几个关键的改进空间，如应用LSTM，这是一个有趣的未来方向，可以带来更好的结果。
