Grounding Compositional Hypothesis Generation in Specific Instances
在特定实例中生成构图假设
摘要
许多最近的计算模型将概念学习视为在类似语言的、组合性概念空间中的概率规则归纳。在这些模型中的推理通常需要反复从可能的概念规则的（无限）分布中抽样，并根据当前数据或证据比较它们的相对可能性。然而，我们认为大多数现有的自顶向下抽样算法效率低下，并且对人类假设生成的认知解释不合理。因此，我们提出了一个替代方案，即实例驱动生成器（Instance Driven Generator, IDG），它直接从遇到的概念的正面实例构建自下而上的假设。我们使用基于儿童游戏Zendo的一种新颖的规则归纳任务，比较了这些“自下而上”和“自上而下”的推理方法。我们发现，自下而上的IDG模型更好地解释了人类的推理，并为基于概率思维语言的概念学习模型提供了一个在计算上更可行的推理机制。
关键词：发现；程序归纳；概率思维语言，主动学习；假设生成
许多最近的论文认为，人们通过在“概率思维语言”中进行推理来学习关于世界的抽象假设（Goodman, Tenenbaum, & Gerstenberg, 2015）。也就是说，一套概念原语和它们如何被组合的随机规则。这样的模型捕捉了人类思维表现出类似语言的组合性和系统性（Fodor, 1987; Lake, Salakhutdinov, & Tenenbaum, 2015），允许我们将简单概念组合和重新利用以构建更丰富的概念（Goodman, Tenenbaum, Feldman, & Griffiths, 2008; Piantadosi, Tenenbaum, & Goodman, 2016）。为了在这样的模型中模拟推理，通常假设人们使用随机搜索算法近似可能的抽象表达式的后验分布（Hastings, 1970）。然而，这种方法通常需要自顶向下生成大量的样本，以有较大机会包含真实的假设，这使它们成为人类学习和假设生成的不合理的算法级账户（Lewis, Perez, & Tenenbaum, 2014; Schulz, 2012）。
然而，假设人类被赋予了某种类似语言的表示来形成抽象假设，人们会认为这种语言不仅可以用来推断抽象假设或想法，还可以用来描述世界中的具体状态和特定实例。例如，观察一个视觉场景时，可以描述各种事实（例如，“咖啡杯在桌子上方”，“窗户是关闭的”）。这些观察基本上是关于一个人正在感知的“数据”的精神陈述。鉴于这种能力，对于一个符号推理假设系统来说，使用这些描述来帮助“播种”假设生成和搜索过程似乎是有用的。因此，例如，而不是从零开始并反复从先验分布中抽样，学习者可能首先考虑与关于数据/世界的某些或所有事实陈述相匹配的假设。通过探索这些抽象假设的潜在概括和限制，可以更有效地得出一些更深层次的抽象因果知识（例如，那个人是否匆忙离开了办公室？），因为每个假设至少与已知数据一致。
在本文中，我们探索了自顶向下的样本驱动和自下而上的实例驱动概念学习之间的中间地带。我们提出了一个实例驱动的语法假设生成器，并证明它比完全自顶向下的方法更接近人类的概括，同时也更具计算效率。
在Zendo中的概念发现学习
为了探索这个想法，我们开发了一个新的任务环境，虽然它有正式的规范，但它足够开放，为概念学习提供了一个具有挑战性和自然主义的测试平台。这项任务受到桌面科学学习游戏Zendo™的启发。在这项任务中，学习者既可以观察也可以自己创建场景，这些场景是在平面上排列的2D三角形物体（称为圆锥体）的布局（如图1所示）。目标是识别一个隐藏的规则，该规则将场景分为遵循规则和不遵循规则的场景。场景可能包含不同数量的圆锥体，每个圆锥体都有两个不可变的属性：大小∈{小，中，大}和颜色∈{红，绿，蓝}，以及具有连续的场景特定位置x∈(0,8)，y∈(0,6)和方向∈(0,2π)1。
场景受到重力的影响，这意味着它们可能的排列方式有熟悉的物理限制。除了圆锥体的不可变和位置属性外，场景还承认许多由不同圆锥体的相对特征和排列产生的复杂属性。例如，圆锥体的子集可能共享一个特征值（即，颜色相同，或者方向相同）或者是有序的（即，一个比另一个大，或者位于另一个之上），并且圆锥体对可能具有指向彼此或相互接触的属性。这导致了一个丰富的潜在概念空间，需要一种富有表现力的概念语言。遵循Piantadosi等人（2016），我们假设我们任务中可能概念的真实潜在空间是那些可以用一阶逻辑结合lambda抽象表达的，并且对场景可能相关的特征有完全了解。Lambda抽象提供了一个简单的通用形式主义，用于将实体绑定到变量（Church, 1932）。在当前上下文中，将圆锥体集合绑定到不同变量允许我们的语法断言场景中不同圆锥体子集之间的关系。
自顶向下的“猜测和检查”推理机制
如上所述，解决无限假设空间中学习问题的一种方法是通过从足够表达力的底层语法中随机组合假设来抽样。在这里，我们考虑一个语法（特别是一个概率上下文无关语法或PCFG；Ginsburg, 1966），它可以用来产生可以用一阶逻辑和lambda抽象表达的任何规则。当正确设置时，“更简单的概念”（即，由较少部分组成的，参见Feldman, 2000）将自然具有更高的先验产生概率，因此将比同样能够解释数据的更复杂的概念更受青睐。这是必要的，因为设置确保了总会有无限数量的潜在规则与任何数据一致（Gold等人，1967）。
在PCFG中，每个假设最初是包含单个非终端符号（这里，S）的字符串，该符号使用重写规则或产生式进行替换。这些产生式反复应用于字符串，将非终端符号替换为其他非终端符号和一阶逻辑的终端片段的混合，直到没有非终端符号为止。这些产生式的设计确保了结果字符串是有效的语法表达式。此外，通过将表达式与绑定变量和真值陈述联系起来，我们的PCFG充当自动概念生成器。表1详细说明了我们在当前论文中考虑的PCFG，图2a给出了两个示例PCFG样本。我们使用大写字母作为非终端符号，每个重写都是从给定符号的可用产生式中抽样的。2因为一些产生式涉及分支（例如，B → H(B,B)，见表1），结果字符串可以变得任意长和复杂，涉及多个布尔函数和绑定变量之间的复杂关系。PCFG中每个产生式的概率可以拟合人类判断，并且可以比较包含不同原语和扩展的不同PCFG。通过这种方式，最近的工作试图推断思维的逻辑原语（Goodman等人，2008；Piantadosi等人，2016）。
这些PCFG方法的共同点是，它们提供了一种从所有可能概念的先验中抽样的生成机制。然而，这些抽样的“猜测”必须然后针对数据进行测试。不幸的是，许多样本，即使是来自调整良好的PCFG，可能是重言式的（即，“所有圆锥体都是红色或不是红色”），矛盾的（即，“有一个圆锥体既是红色又不是红色”），物理上不可能的（“有两个不同的对象具有相同的位置和方向”）或者简单地与学习者已经遇到的数据不一致。事实上，表1中语法生成的假设中约有20%是重言式，15%是矛盾的。由于这些原因，该过程本质上是低效的，通常需要大量的样本才能可靠地提供非平凡的规则。
实例驱动假设生成
我们的实例驱动生成（Instance Driven Generation, IDG）提议与PCFG理念有关，但有一个主要区别。我们不是完全随机地生成猜测，然后再将它们与数据对比，而是提议人们根据遇到的正面例子（参见Michalski, 1969）激发猜测的产生。具体来说，我们提议学习者首先观察遵循规则场景中对象的特征，并以一种随机但保持真实性的方式使用这些特征推断出关于场景的真实逻辑陈述。这样，学习者不是从所有可能的逻辑陈述中均匀生成，而是直接从当前观察为真的受限陈述空间中生成。图2b激发了这种方法。在这里，学习者以观察一个遵循隐藏规则的场景开始他们的假设生成。为了生成作为隐藏规则候选的假设，我们假设学习者使用以下程序：
请注意，上述程序原则上能够生成表1中PCFG生成的任何规则，但只有当接触到实际上与该规则一致的正面观察时才会这样做，并且当观察与尽可能多的其他规则不一致时（即，最小的正面例子）才会更频繁地这样做。基于实例的假设应该提高学习者生成的有效规则样本的质量。
可以将IDG程序视为PCFG的反转。正如图2中的例子中的蓝色文本所示，虽然PCFG从外部开始向内工作，但IDG从中心内容开始向外工作，以形成一个量化的陈述，并确保在每一步这个最终陈述都符合场景。
现在我们报告一个旨在测试人类概念学习的实验，使用它来评估人们的行为是否更符合PCFG还是IDG假设生成。
实验
我们的试点实验让参与者进入引言中概述的学习环境中，他们必须通过测试遇到的和自生成的场景来学习概念，然后预测新场景是否与概念一致。
方法
参与者：30人（女性10人，年龄36.8 ± 11.5岁[平均值±标准差]）参加了实验，他们每小时获得7美元的报酬，根据他们预测的准确性，还可以获得高达4美元（2.6 ± 0.3）的奖金。这项任务耗时34.2±16.4分钟。
材料：实验是用JavaScript编程的，使用了Box2D物理游戏引擎的一个端口，并使用Psiturk（Gureckis等人，2016）在线运行。场景是通过一个互动的800×500像素窗口显示和构建的（见图3，点击这里尝试任务：https://github.com/neilbramley/discovery）。
测试规则：我们选择了一系列可以用一阶逻辑和lambda演算表达的测试规则，这些规则在复杂性和它们涉及的特征上有所不同（见表2）。
程序
参与者被告知一个“外星行星”的封面故事，他们的任务是确定为什么一些圆锥体集合会发射奇怪的新形式辐射。通过五个已经发现的辐射形式的例子（如图1所示），让参与者了解与实验相关的特征。然后，他们完成了对应于表2中规则的10个测试问题的随机顺序。
每个问题都有学习阶段和预测阶段。
在学习阶段，向参与者展示了一个初始场景，该场景确实遵循了规则（如表2所示），然后允许他们对自己构建的额外7个场景进行测试。参与者使用构建界面（如图3a所示）创建自己的场景，他们可以通过一组按钮添加圆锥体，通过右键单击它们来移除它们，并通过按住左键拖动它们。然后他们会点击“测试”按钮，界面会计算场景是否遵循规则，如果是，会显示发射的辐射，以金色星星从场景中升起的形式可视化。当前问题的测试序列及其结果的记录显示在窗口顶部，金色星星表示哪些场景发射了辐射（见图3b）。在预测阶段，参与者被要求预测8个新案例中哪些会发射辐射，通过选择至少1个且少于8个场景（图3c）。预测场景是从使用构建界面顺序添加随机圆锥体的大量集合中选取的。每个问题随机选取四个遵循规则和四个不遵循规则的场景，并在参与者之间共享，但它们在屏幕上的位置是独立随机的。最后，参与者提供了关于隐藏规则的最佳猜测的书面描述，我们这里不进行分析。
结果和讨论
我们首先比较了参与者在不同规则下的预测，然后拟合我们的PCFG和IDG学习模型。
参与者正确预测了8个测试场景中66 ± 21%（平均值±标准差）的标签，正确标记负面实例的频率高于正面实例（76 ± 27%与57±32%，t(29) = 4.4, p < .001，图4）。准确性因规则而异，如重复测量分析所示 F(9,261) = 5.5, η²g = .14, p < .001。尽管远低于100%，但参与者的预测与地面真相相符，且显著高于50%的偶然水平（经校正的p<.005水平），除了规则3“没有东西是竖直的”，4.“恰好有1个蓝色”，和6.“全部是蓝色或小”之外的所有规则。
在析取规则6“全部是蓝色或小”上表现最差，复制了人们学习析取规则时的困难的经典发现（Shepard, Hovland, & Jenkins, 1961）。
我们现在将参与者的预测与PCFG和IDG学习模型以及随机基线模型进行比较。我们首先从我们的PCFG中抽取了50,000个样本，使用统一的产生式权重。然后我们使用参与者的概括来拟合产生式权重，以匹配人类数据中的实证频率。为此，我们给每个产生式一个初始权重1。然后我们取与每个参与者在前两个阶段（主动学习和测试阶段，图3a和b）中遵循规则的场景一致的m个规则集合，并在重新归一化这些权重之前，为每个产生式权重增加1/m（即，在表1中同一符号的每个产生式组内，也就是每个行内）。然后我们使用拟合的假设空间重新抽取了10,000个候选规则。完整的拟合参数集可在https://github.com/neilbramley/discovery上找到。大多数参数与统一权重没有显著差异，但有证据表明参与者的规则中偏好使用颜色属性而不是其他特征：[color=.32, size=.14, orientation=.10, grounded = .10, x-position=.11, y-position=.11]。
我们假设IDG会从场景的自然统计数据中受益，因为它在圆锥体上均匀抽样，所以我们没有尝试拟合它的随机元素，而是给了它从上述PCFG中得出的相同的特征选择概率。然后我们使用IDG模型为每个参与者在每个试验中的正面试验生成了另外一组10,000个规则。对于每个预测阶段，我们通过仅抽取与参与者在学习中心阶段经历的所有八个结果一致的假设，为两个模型生成了后验。然后我们给每个模型一个单一的决策噪声参数τ，控制对存活规则的平均预测进行软最大化。因此，对于两个模型，基于参与者p生成的数据，场景s在试验t上遵循规则的概率P(s)pt由以下公式给出：
其中τ → 0表示对P(s)进行硬最大化，而τ → ∞表示随机响应。我们使用最大似然法拟合了两个模型的τ，并与将每个预测视为抛硬币的基线模型进行了比较。表3中详细显示的结果表明，IDG比PCFG更好地定量拟合了参与者的模式，无论是在单独拟合更多参与者方面，还是在具有最低整体BIC值方面。然而，略多于一半的个别参与者更好地被基线随机选择模型拟合。PCFG在匹配真实情况方面比IDG稍微准确一些（72%与70%），但即使在大样本情况下，两个模型的适度准确性也突显了学习任务的难度。
由于我们假设IDG对于受限学习者更有效，这些学习者在存储和评估样本的数量上受到限制，我们还比较了将模型限制在较少初始样本数量时的性能，将性能与1、10、100和1000个样本进行了对比。对于IDG，这些样本均匀分布在学习者在每个问题上遇到的正面案例中。图5显示了这些测试的结果。对于等价的初始样本大小，IDG在任务结束时保留了比PCFG更多的有效假设，这导致在1、10和100个样本的任务中预测更准确。对于10、100和1000个样本，IDG比PCFG和基线更好地描述了参与者（即，更小的BIC），而对于单个样本，无参数的基线拟合得最好。参与者的准确性最接近模型的1000个样本变体。
虽然IDG击败了PCFG模型，但两者都没有在遵循规则和不遵循规则的测试场景中为参与者的预测提供紧密的拟合。一种可能性是，这种差异源于评估这些场景中的假设时的感知模糊性。
一般讨论
本文对比了关于人们如何生成关于概念的假设的两种提议。我们发现了支持我们实例驱动生成器描述的部分实例驱动学习方式的想法。
空间限制禁止了对参与者测试选择的分析，但我们预计这些将为概念学习提供额外的视角。在积极的例子激发假设的程度上，我们预计学习者将从“最小”积极例子中受益，而不是从更复杂的案例中最大化信息。参与者的假设反映积极例子的想法可能有助于解释积极的测试偏差（Klayman & Ha, 1987）。我们还注意到，我们没有解决识别相关特征的问题。
从实例驱动生成到实例驱动适应
虽然由观察激发假设对于有界概念学习者来说是一个良好的开端，但大多数精确的假设在面对新数据时仍然没有很长的预期寿命。因此，IDG方法的自然伙伴是尝试适应假设以解释新数据（Bramley, Dayan, Griffiths, & Lagnado, 2017; Dasgupta, Schulz, & Gershman, 2016; Trabasso & Bower, 1975）。
例如，Lewis等人（2014）探索了一种错误驱动的假设适应机制，每当由于假阴性而排除一个假设时，就会用一个新的析取与之相加——例如，“有一个绿色圆锥体或红色圆锥体”——每当通过假阳性排除时，就会用一个新的合取与之相加——例如，“有一个大的绿色圆锥体”（另见Nosofsky, Palmeri, & McKinley, 1994，关于相关的规则+例外方法）。这些都是被称为序贯覆盖的一类规则学习算法（Michalski, 1969），其中模型通过一个新组件扩展以覆盖每个新遇到的案例。展望未来，我们计划通过考虑对逻辑形式的小编辑来增强我们的IDG提议，以适应假设，因为数据到达。通过这种方式，我们希望能够更好地捕捉人类学习者在学习中心维持一组有用的候选假设的计算技巧，因此即使在无限的假设空间中也能成功学习。
https://www.bramleylab.ppls.ed.ac.uk/pdfs/bramley2018zendo.pdf
