【1996~2016】盘点 20 年 AAAI 人工智能最佳论文

【新智元导读】新智元汇集计算机科学领域1996年到2016年人工智能领域最佳论文，附上题目及摘要的中文翻译，并对这些作品进行系统考察，从中可以看出人工智能这门学科的一些发展走势。过去20年来（空缺年份表示当年没有最佳论文），AAAI 最佳论文覆盖面完善，包括推理、知识、规划、学习、交流、感知、移动和操作物体。论文中使用最多的还是优化、逻辑推演等方法，与刚刚结束的 IJCAI'16相比，机器学习在其中光芒并没那么显著。

2012年，浙江大学EAGLE-Lab及CAD&CG 实验室合作的《基于数据重构的文档摘要》被评为最佳论文之一。但是，纵览30多篇论文，中国大陆的表现仍然有很大提高空间。

同时，也可以发现，荣获人工智能顶级期刊 Artificial Intelligence Journal 的 Prominent Paper Award 的论文——谷歌 DeepMind David Sliver 和谷歌欧洲研究院工程师 Sylvain Gelly 2011 年的 Monte-Carlo tree search and rapid action value estimation in computer Go 并不在其中。日前 SCI 再度易主，又一次引发围绕期刊影响因子的争论。SCI 是一种评价工具，关键还是在于我们如何使用它。

【2015】

• From Non-Negative to General Operator Cost Partitioning
• 从非负性到一般的算子成本划分

【作者】Florian Pommerening， Malte Helmert，Gabriele Roger，Jendrik Seipp（University of Basel，Switzerland）

摘要

算子成本划分是一种常见的技术，通过把算子成本分发到单个启发式方法上来让容许的启发式方法具有可加性。一般算子成本是正的，因此自然要求分发的成本也是正的。本文作者认为，这个要求不是必要的，并且展示了采用一般的成本划分的好处。作者证明了关于算子计数约束的 LP 启发式方法是成本划分过的，而状态方程启发式方法针对原子投影计算了成本划分。作者也引入了一系列新的启发式方法，并讨论了它们与一般成本划分的关系。

【2014】

• Recovering from Selection Bias in Causal and Statistical Inference
• 纠正因果推断和统计推断里的选择偏差

【作者】Elias Bareinboim（University of California, Los Angeles），Jin Tian（Iowa State University），Judea Pearl（University of California, Los Angeles）

摘要

选择偏差是由于对样本的倾向性排除导致的；这是因果推断和统计推断面临的主要障碍。随机化实验不能排除选择偏差，实验和观测研究也很少能探测到选择偏差的存在。本文中作者给出了从受选择偏差影响的数据来恢复条件概率的完整的图论和算法条件。作者也给出了变量的一个子集存在无偏差数据的情况下的图论可恢复条件。最后，对于数据被倾向性收集的情况，作者给出了能恢复因果效应的图论条件，这推广了“后门判据” (backdoor criterion)。

【2013】

• HC-Search: Learning Heuristics and Cost Functions for Structured Prediction
• HC-搜索：为结构化推断学习启发式算法和成本函数

【作者】Janardhan Rao Doppa，Alan Fern，Prasad Tadepalli（Oregon State University）

摘要

结构化推断指的是从结构化的输入和输出来学习一个函数。近期基于搜索的结构化推断取得了成功，作者受此启发提出一个新的结构化推断框架，叫做HC-搜索。给定结构化输入，这个框架使用由学到的启发式策略 H 指引的搜索程序来获得高质量的候选输出，然后用另一个单独学习的成本函数 C 来从候选输出里选择最终推断。作者把总的“懊悔度” (regret) 分解为由 H 和 C 导致的两部分。基于这种分解，作者通过分阶段贪婪训练的方式来最小化懊悔度：先通过模仿学习训练 H 获得高质量候选者，然后通过真实损耗来训练 C 为候选者排序。在几个基准测试上作者的方法比领域前沿方法优异很多。

***

• SMILe: Shuffled Multiple-Instance Learning
• SMILe：打乱的多事例学习

【作者】Gary Doran，Soumya Ray（Case Western Reserve University）

摘要

像 Bagging (Bootstrap aggregating: 自举聚合) 这样的重采样技术经常被用于监督学习以获得更准确的分类器。本文介绍了在多事例学习中，一种叫做“打乱”的重采样技术。作者证明这种方法降低了标记噪声，并且给出对于多事例分类器的额外的约束。在多事例分类和多事例主动学习中，本文作者使用的方法显著提升了结果的精度。

【2012】

• Learning SVM Classifiers with Indefinite Kernels
• 通过不定核学习 SVM 分类器

【作者】Suicheng Gu，Yuhong Guo（Temple University）

摘要

近期，训练具有不定核的支持向量机获得了许多关注。为此，本文作者构造了一个基于 SVM 分类以及核的主成分分析的联合优化模型。作者首先把核的主成分分析重塑为一个一般性的核变换问题，然后将之引入 SVM 分类框架，由此得到联合模型。这个模型的好处是，对训练集和测试集给出一致的核变换，可用于二元分类以及多元分类。实验表明，该模型对于人造数据和真实数据比类似的方法好很多。

***

• Document Summarization Based on Data Reconstruction
• 基于数据重构的文档摘要

【作者】何占盈、陈纯、卜佳俊、王灿、张立军（浙江大学EAGLE-Lab），蔡登、何晓飞（浙江大学CAD&CG 实验室）

摘要

文档摘要有许多实际用途，比如生成搜索结果的简短文字以及新闻头条。传统方法是提取出概括文档主旨的关键句子，而不要有太多冗余。作者从数据重构的角度，提出了新的框架，叫做 “基于数据重构的文档摘要” (Document Summarization based on Data Reconstruction; DSDR)。具体说，就是找出那些能最好地重构原文的句子作为摘要。为了给句子间的关系建模，作者提出两个目标函数：1. 线性重构，通过选出句子的线性组合来近似整个文档；2. 非负线性重构，也就是仅允许加法而不允许减法的组合。这样，重构误差成了评估摘要质量的自然标准。对每个目标函数，作者第一开发了高效的算法来解决相应的优化问题。使用 DUC 2006 和 DUC 2007 基准数据集的大量实验表明，作者的方法是有效的。

【2011】

• Dynamic Resource Allocation in Conservation Planning
• 保护规划中的动态资源分配

【作者】Daniel Golovin（Caltech）、Andreas Krause（ETH Zurich）、Beth Gardner（NCSU）、Sarah J. Converse（USGS Patuxent WRC）、Steve Morey（USFWS）

摘要

为了保护某些濒危物种，作者需要划定一些保护区。不过，不同的时间需要保护的土地是不同的，所以决策需要动态进行。这种带有不确定性的序列优化问题，在计算环境可持续性领域很常见。已有的技术不适用于现实世界的规模。本文提出了一种针对动态保护规划的高效自适应算法，并且证明这种算法接近最优。作者把这种方法应用于保护美国太平洋西北地区的种三稀有物种保护计划的设计。

***

• Complexity of and Algorithms for Borda Manipulation
• 波达操纵的复杂性和算法

【作者】Jessica Davies（University of Toronto）、George Katsirelos（LRI, Universite Paris Sud 11）、Nina Narodytska、Sydney, Australia（NICTA & UNSW）

摘要

作者证明，让两个人结成的联盟来操纵波达投票规则所需的计算是 NP-困难的。这解决了关于操纵常见投票规则的计算复杂性的最后的开放问题之一。由于这种 NP-困难，作者把操纵的计算问题作为一个近似问题，然后试图最小化操纵者的数量。从集装优化 (bin packing) 和多处理器调度方面的思路出发，作者提出两个新的方法来计算对波达规则的操纵。实验表明新方法比之前的方法好很多。几乎在所有随机生成的选举中，作者都能找到最优操纵。结果表明，尽管通过结盟来操纵波达规则需要的计算是 NP-困难的，但在实践中这种困难性只是一个微弱的障碍。

【2010】

• How Incomplete Is Your Semantic Web Reasoner? Systematic Analysis of the Completeness of Query Answering Systems
• 你的语义网推理器有多不完备？对问答系统完备性的系统分析

【作者】Giorgos Stoilos、Bernardo Cuenca Grau、Ian Horrocks（牛津大学）

摘要

对许多基于本体的应用而言，问答是主要的推理服务。为了改进规模性，许多语义网问答系统放弃了完备性 (也就是不保证返回所有的答案)。用户和设计者都应该知道，这么做可能损失了多少信息。作者给出了一种生成测试数据的方法来解决该问题的一部分，而之前的基准测试对这个目的都不太适合。作者还提出对某些流行的本体语言生成测试数据的实用算法，并且在初步测试中表现不错。

• A Novel Transition Based Encoding Scheme for Planning as Satisfiability
• 一个基于转换的新的编码方案，用于可满足性问题的计划

【作者】Ruoyun Huang, Yixin Chen, Weixiong Zhang（Washington University in St. Louis）

摘要

作为可满足性问题的计划是解决计划问题的一个主要方法，有许多优势。已有的技术通常使用基于 STRIPS 体系的编码。作者引入新的基于 SAT+ 的 SAT 编码方案。这个方案利用了 SAS+ 体系结构信息，导致更加紧凑的 SAT 样例，并且把条件数降低了多达 50 倍。结果表明，这个编码方案在时间和内存效率方面，改进了基于 STRIPS 的方案。

【2008】

• How Good is Almost Perfect?
• 多好算得上是几乎完美？

【作者】Malte Helmert、Gabriele Roger（Albert-Ludwigs-Universitat）

摘要

对于经典的计划任务，启发式搜索算法如 A* 以及 IDA* 等占主导地位。理论分析表明，如果使用的启发式方法足够好，这些算法比指数复杂度的算法表现更好。作者证明，对一些常见的计划评估问题，包括那些能在多项式时间内获得最优解的，类似 A* 这样的一般搜索算法必定先要经过指数量级的节点，即便假定启发式方法接近完美 (也就是误差相对最优值不超过某个小的常数)。

作者的结果对那些在“简单”计划领域表现较差的最优启发式搜索算法给出了提示：在许多应用中，想要改进运行时间的话，需要改变启发方法之外的东西。

***

• Optimal False-Name-Proof Voting Rules with Costly Voting
• 基于有成本投票的最优防假名投票方案

【作者】Liad Wagman、Vincent Conitzer（杜克大学）

摘要

进行联合决策的一个办法是对不同选择投票。在开放、匿名的场景，一个人可以多次投票而不被察觉。防假名投票方案可以让多次投票的人得不到额外好处。之前的工作表明，防假名投票方案不响应投票人的倾向。但是，那个工作隐含假定了额外投票是无成本的。这里作者考虑额外投票有成本的情况。作者描述了在有两个选项的情形下的最优 (响应度最高) 投票规则。与无成本情形完全不同，作者证明，当投票人口增加，这个规则选出多数派胜者的几率收敛到。作者还给出了最优团体规则，这个规则对于共同负担投票成本的联盟是强壮的，但这个规则对于投票人数增加的情况，选出多数派胜者的几率比较低。对于三个选项的情形作者推出了类似的规则，并且给出了四个或者更多选项时的计算方法。

【2007】

• PLOW: A Collaborative Task Learning Agent
• PLOW：一个协作任务智能体

【作者】Institute for Human and Machine Cognition：James Allen, Nathanael Chambers（Stanford）、George Ferguson（University of Rochester）、Lucian Galescu, Hyuckchul Jung, Mary Swift（University of Rochester）、William Taysom

摘要

与人类合作的智能体要能跟着人类学习新的任务。本文描述了一个系统，能通过展示、解释，以及对话，从单个协作学习进程中，学到可执行的任务模型。为了这个目标，系统集成了一系列 AI 技术，深度自然语言理解，知识表示和推理，对话系统，决策/基于代理人的系统，以及机器学习。正式的评估表明，这个方法很有前途。

***

• Thresholded Rewards: Acting Optimally in Timed, Zero-Sum Games
• 有阈值的奖励：在计时零和游戏中表现最佳

【作者】Colin McMillen、Manuela Veloso（CMU）

摘要

在计时零和游戏中，目标是让结果赢的最大化几率，这未必等于最大化期望奖励。作者考虑把作者的得分与对手得分的，差作为累积中间奖励；在输、赢、平局等情形的真正奖励在游戏结束后定出，方法是往累积中间奖励应用一个阈值函数。作者引入阈值奖励问题来描述最终奖励回报对累积中间奖励的依赖。这类问题体现了不同的真实世界的随机计划范畴，特别是零和游戏，其中时间和分数都是要考虑的。作者研究了阈值奖励在有限视野马尔可夫决策 (MDP) 过程中的应用。一般地，奖励有阈值的 MDP 中的最优策略是非静态的，取决于剩下的时间和累积中间奖励。作者引进了一种高效的价值迭代算法，能精确求解奖励有阈值的 MDP 问题，但运行时间是状态数和时间视野长度的二次方。作者探索了一些启发式方法，能高效求出大状态空间和长时间视野的 MDP 的近似解。

【2006】

• Model Counting: A New Strategy for Obtaining Good Bounds
• 模型计数：获得较好界限的新策略

【作者】Carla P. Gomes、Ashish Sabharwal、Bart Selman（康奈尔大学）

摘要

模型计数指的是计算给定命题公式解的个数。它极大地推广了 NP 完备的命题满足性问题，因此很有用，但却很难求解。作者的新方法加入了一些仔细选择的所谓流线型 (streamlining) 约束到输入的公式里，以图通过受控的方式降低解空间大小。每个额外的约束都一个随机的 XOR 或者对问题变量的奇偶约束，可以直接表达，或者用标准的 CNF 形式表达。受相关但不同的 XOR 约束的启发，本文作者形式化地证明，让公式到达不可满足边缘的 XOR 约束，个数以高概率和高精度与模型计数近似。通过实验，作者证明这个办法能够给出某些公式的模型计数的边界，凌驾于所有精确方法之上。事实上，作者对某些很难且高度结构化的组合问题得到了首次非平凡的解数。与别的像 MCMC 这样的方法不同，作者可以对结果给出高置信度。

***

• Towards an Axiom System for Default Logic
• 通往缺省逻辑的公理系统

【作者】Gerhard Lakemeyer（RWTH Aachen）、Hector J. Levesque（University of Toronto）

摘要

最近，Lakemeyer 和 Levesque 提出了一种叫做 only-knowing 的逻辑，这种逻辑准确地表达了三种非单调逻辑：Moore 的自动认识逻辑，Konolige 的基于 moderately grounded expansions 的变型，以及 Reiter 的缺省逻辑。缺省在新逻辑的三种诠释下有统一的表达，并且这个逻辑本身是单调的，也就是说，非单调推理是通过经典意义上的正确性来塑造的。虽然 Lakemeyer 和 Levesque 对他们的逻辑给出了模型论的描述，但证明论的描述还没有。本文对于命题子集填补了这个空白：在新逻辑下一个可靠而完备的公理系统，可用于缺省推理的三个变型。作者也给出了缺省逻辑的某些例子的正式推导。最后作者给出证据，表明在一阶情形不太可能存在完备的公理系统，即便限制在缺省推理这种最简单的形式上。

【2005】

• The Max K-Armed Bandit: A New Model of Exploration Applied to Search Heuristic Selection
• 最大K臂赌博机：一种全新的应用于启发式搜索的探索模型

【作者】Vincent A. Cicirello（Drexel University）、Stephen F. Smith（CMU）

摘要

多臂赌博机经常被用来类比搜索问题中探索与利用（exploration and exploitation）的权衡。作者在本文中展示了一种多臂赌博机的新变种——最大K臂赌博机（the Max K-Armed Bandit）——其中尝试次数必须在所有赌博机之间进行分配，以此达到让一系列尝试中每一次获得的预期最大回报得以最大化。对于这种最大K臂赌博机在特定假设下的分析显示，最优策略将尝试分配给观测到的最优赌博机的概率（相对于其他赌博机而言）以二重指数（double exponentially）的方式增长。作者将这种探索策略与那些概率增长速度大于或小于二重指数的策略进行了比较，结果表明，在实验的两种调度任务中，论文中所使用的方法在表现上超过了其他方法。

【2004】

• Learning and inferring transportation routines
• 学习和推理日常行动轨迹

【作者】Lin Liao（华盛顿大学）、Donald J. Patterson（加州大学Irvine分校）、Dieter Fox、Henry Kautz（华盛顿大学）

摘要

这篇论文介绍了一种能够学习并推断用户在市区的日常行动轨迹的分层马尔可夫模型。该模型使用了多层抽象来弥合原始GPS传感器数据与高层信息（例如用户的目的地与交通模式）之间的鸿沟。为了获得高效的推断，作者将Rao-Blackwellized粒子滤波器运用在模型结构的多个层级中。作者用实验展示了如何通过在用户的历史数据中对其行动进行建模来准确地探测到全新的行为或是用户的失误（例如乘上了一辆错误的公交车）。最后，作者讨论了如何将这种技术运用于帮助认知受损人群安全地乘坐公共交通。

【2002】

• 六贯棋：一种游戏编程的自动化定理证明方法
• The Game of Hex: An Automatic Theorem Proving Approach to Game Programming

【作者】Vadim V. Anshelevich（Vanshel Consulting）

摘要

大量的博弈树（game-tree）搜索技巧——绝大部分是为象棋而开发的，对西洋跳棋、翻转棋以及一些其他游戏也能成功适用——对于像围棋和六贯棋这类拥有数量庞大的分支因子（branching factor）的游戏而言并不怎么有效。本文作者提供了一种全新的方法，它强调针对相对较少的游戏局面进行深度分析。为了达到这个目标，作者为六贯棋局势的拓扑分析开发了一种自动化的定理证明技术。作者也详细地探讨了用电阻器电路（elecrical resistor circuits）来为六贯棋局势建模的想法，解释了如何将这种方法实现于六贯棋程序Hexy中——它是已知的最强大的六贯棋程序，能够与最顶级的人类棋手相抗衡。

【2000】

• On Computing all Abductive Explanations
• 溯因解释计算

【作者】Thomas Eiter（Technische Universitat Wien）、Kazuhisa Makino（大阪大学）

摘要

本文作者将对所有溯因解释的计算视为Horn理论中一项溯因查询（abductive query）的解释的一个多项式子集。根据准多项式时间内的可解决性，作者从中推演出了易处理性结果（tractability results）——其中之一反驳了Selman和Levesque的一个猜测——和非易处理性结果（intractability results），以及进一步的半-易处理性结果（semi-tractability results）。结果完善了过去文献中的结论，并阐明了生成解释集（the set of explanations）的计算复杂性。

【1999】

• PROVERB: The Probabilistic Cruciverbalist
• PROVERB：基于概率的填字游戏程序

【作者】Greg A. Keim, Noam M. Shazeer, Michael L. Littman,Sushant Agarwal, Catherine M. Cheves, Joseph Fitzgerald,Jason Grosland, Fan Jiang, Shannon Pollard, Karl Weinmeister（杜克大学）

摘要

作者研究了如何用计算机来解决纵横的填字游戏：根据给定的一系列线索和空格，尝试令填写正确的词语的数量最大化。在论文中描述的系统中，“专家模块（Expert Modules）”专长于依据信息回溯（information retrieval）、数据库搜索以及机器学习来解开特定的线索。每一个专家模块都会为每一条线索生成一个（可能是空的）有权重的备选答案的列表，这些列表经过合并器（Merger）依据不同专家模块的权重合并成一张新的、各备选答案的权重也有所更新的列表，由解决器（Solver）读入所有线索的列表并搜寻出符合字母数量限制的最优答案。最后得到了PROVERB系统，在从纽约时报和一些其他渠道获得的370个填字游戏中，能以不到15分钟的时间解决一个填字游戏，达到95.3%的词语、98.1%的字母的平均正确率。

【1998】

• Learning Evaluation Functions for Global Optimization and Boolean Satisfiability
• 学习全局优化和布尔可满足性问题的估值函数

【作者】Justin A. Boyan、Andrew W. Moore（CMU）

摘要

这篇论文描述了一种名为STAGE的学习方法，能够在优化问题上自动地提高搜索表现。STAGE会学习一种估值函数，这种估值函数将本地搜索算法（比如爬山算法或是WALKSAT算法）的结果预测为一个状态特征函数。习得的估值函数被用来对未来的搜索最优解的轨迹产生影响。本文作者展示了它在6种大规模优化任务中的良好表现。

• Acceleration methods for numeric CSPs
• 数字型CSP算法的加速方法

【作者】Yahia LEBBAH、Olivier LHOMME（法国南特高等矿业学院）

摘要

这篇论文介绍了一种利用外推法（extrapolation methods），使数字型CSP过滤算法加速收敛的方法。在数值分析中，外推法被用于加速实数序列的收敛。本文作者展示了如何用这种方法来解决数字型CSP算法，这令算法效率有了极大的提升。

***

• The Interactive Museum Tour-Guide Robot
• 交互型博物馆用导游机器人

【作者】波恩大学：Wolfram Burgard、Armin B. Cremers、Dieter Fox、Dirk Hahnel、Gerhard Lakemeyery（Aachen University of Technology）、Dirk Schulz, Walter Steiner、Sebastian Thrunz（CMU）

摘要

这篇论文描述了一个自主导游机器人的软件架构。这个机器人最近被部署在波恩德意志博物馆（Deutsches Museum Bonn），在六天内为数百名游客进行了博物馆导游服务。机器人的控制软件在一阶逻辑（first order logic）中整合了低层的概率推理（probabilistic reasoning）与高层的问题解决。文中描述了一系列软件上的创新，这些创新使得机器人能够在密集人群中进行快速导航，与此同时也能可靠地避免与障碍物——一些障碍物甚至可能无法被观测到——发生碰撞。文中也介绍了它的用户交互界面，专为非专业用户设计，对于这个机器人在博物馆中的顺利表现功不可没。

【1997】

• Statistical Parsing with a Context-free Grammar and Word Statistics
• 无语境的语法和词语统计的统计句法分析

【作者】Eugene Charniak（布朗大学）

摘要

作者描述了一种英语语言模型的句法分析系统，它为一句句子所有可能的结构都分配一个概率。这个模型被用于寻找可能性概率最大的句子结构，表现优于现有的模型。这是一系列由不同作者提出的句法分析器中的第3个，由于这些分析器既相似到足以进行详细的比较、又不同到带来不同级别的表现，作者也报告了一些为了鉴别这些系统优越的表现方面而设计的实验。

***

• A pact ical algorithm for finding optimal triangulations
• 一种用于寻找最优三角剖分的可行算法

【作者】Kirill Shoikhet、Dan Geiger（以色列理工学院）

摘要

本文作者开发了一种称为QUICKTREE的算法，用于对一个给定的 无向图G寻找一个三角剖分T，使得T的最大团（maximal clique）的大小达到最小，并且没有其他G的三角剖分是T的子图。作者用QUICKTREE测试了拥有高达100个节点的图，对于这些图而言，最优三角剖分的最大团大小为11.这是第一个能够对这样大小的图在合理时间内获得最优三角剖分的算法。通过团的树推理（clique tree inference）算法，它对于限制补偿问题（constraint satisfaction problems）和贝叶斯推理而言非常有用。

***

• Fast Context Switching in Real-time Propositional Reasoning
• 实时命题推理中的情景快速切换

【作者】P. Pandurang Nayak、Brian C. Williams（NASA）

摘要

通过使用渐增命题演绎数据库（incremental propositional deductive database，也就是LTMS）能够获得较快的响应速度。理想情况下，LTMS的增量更新所消耗的资源应该与连续情景之间的标签变化数量呈线性关系。不幸的是，LTMS会在连续情景之间保持不变的标签上消耗不少时间。这篇论文展示了一种更为激进的增量真值维护系统，称为ITMS，能够避免对大量没有改变的数据做处理。作者用宇宙飞船的控制作为实际评估方式，表明了由于处理未改变的数据而带来的消耗能够被降低到原本的七分之一。

***

• Building Concept Representations from Reusable Components
• 从可重复使用的构件中建立概念表征

【作者】Peter Clark（德国波恩大学）、Bruce Porter（美国德克萨斯大学奥斯汀分校）

摘要

本文作者为广义的、表征的构件建立了知识库，并开发了能够根据需求自动组装构件的方法。这份研究的成果拓展到了在基于框架的系统中使用的普通继承方法，并融汇了一些来自不同的AI领域的想法——特别是组合建模（compositional modeling）、术语推理（terminological reasoning）以及本体工程（ontological engineering）几个方面。这份研究的贡献在于，创新地整合了这些方法，提高了建立知识库的效率以及使用知识库的鲁棒性。

【1996】

• Verification of knowledge bases based on containment checking
• 基于限制条件检查的知识库核实

【作者】Alon Y. Levy（华盛顿大学西雅图分校）、Marie-Christine Rousset（巴黎第十一大学）

摘要

建立复杂的知识库应用，需要把大量的主流知识进行编码。在从主流专家获得知识后，建造知识库的大量工作会花在核实知识是否被正确编码上。在输入和输出的过程中，如果特定的限制条件是可知的，那么知识库就可以被核实。本研究的对象是 Horn 规则知识库。考虑三个限制条件：输入/输出一致性限制；输入/输出依赖性限制，以及输入完整性限制。本研究结合 Horn 规则的表达力和 logicALCNR的描述，提供了首个用于核实混合知识库的算法。

***

• Pushing the Envelop: A Novel Application of Theory Refinement to Student Modeling
• 理论修正系统在学生建模上的新应用

【作者】Henry Kautz、Bart Selman（AY&T 实验室）

摘要

用机器学习开发的理论修正系统能自动的修正知识库，来保持其与一系列经典训练模型的一致性。作者描述了一种使用这一技术的全新应用，来解决智能教学系统（ITS）中学生的建模难题。作者使用的方法在一个ITS写作系统ASSERT中实施，使用了理论修正系统，在一个本来正确的知识库中引入错误知识，使其模型误导学生。通过对一门有75名学生参与的课堂测试，这一方法的有效性得到证实。系统产生了合理的准确率模型，通过这一模型获得反馈的学生，在后来的测试中比那些只接受了二次教学的学生表现要好得多。

***

• Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search
• 规划、命题逻辑和随机搜索

【作者】Henry Kautz、Bart Selman（AT&T 实验室）

摘要

通过与一个通用的、随机的搜索算法，以及基于命题逻辑问题编码，本文作者解决了复杂的规划问题，并且比最好的循环规划系统要快很多倍。虽然在许多规划问题上，随机的方法已经被证明很有效 ，但是，本研究首次展现了其在真实的经典规划问题上的应用。本研究还提供了一个看待规划问题中表征问题的新视角。