人工智能学术会议AAAI论文收集
| AAAI (Artificial Intelligence) | ||
| 2020 | WINOGRANDE: An Adversarial Winograd Schema Challenge at Scale | Keisuke Sakaguchi, Allen Institute for Artificial Intelligence; et al. Ronan Le Bras, Allen Institute for Artificial Intelligence Chandra Bhagavatula, Allen Institute for Artificial Intelligence Yejin Choi, University of Washington |
| 2019 | How to Combine Tree-Search Methods in Reinforcement Learning | Yonathan Efroni, Technion – Israel Institute of Technology; et al. Gal Dalal, Technion – Israel Institute of Technology Bruno Scherrer, Inria Shie Mannor, Technion – Israel Institute of Technology |
| 2018 | Memory-Augmented Monte Carlo Tree Search | Chenjun Xiao, University of Alberta; et al. Jincheng Mei, University of Alberta Martin Müller, University of Alberta |
| 2017 | Label-Free Supervision of Neural Networks with Physics and Domain Knowledge | Russell Stewart & Stefano Ermon, Stanford University |
| 2016 | Bidirectional Search That Is Guaranteed to Meet in the Middle | Robert C. Holte, University of Alberta; et al. Ariel Felner, Ben-Gurion University of the Negev Guni Sharon, Ben-Gurion University of the Negev Nathan R. Sturtevant, University of Denver |
| 2015 | From Non-Negative to General Operator Cost Partitioning | Florian Pommerening, University of Basel; et al. Malte Helmert, University of Basel Gabriele Röger, University of Basel Jendrik Seipp, University of Basel |
| 2014 | Recovering from Selection Bias in Causal and Statistical Inference | Elias Bareinboim, University of California, Los Angeles; et al. Jin Tian, Iowa State University Judea Pearl, University of California, Los Angeles |
| 2013 | SMILe: Shuffled Multiple-Instance Learning | Gary Doran & Soumya Ray, Case Western Reserve University |
| HC-Search: Learning Heuristics and Cost Functions for Structured Prediction | Janardhan Rao Doppa, Oregon State University; et al. Alan Fern, Oregon State University Prasad Tadepalli, Oregon State University | |
| 2012 | Learning SVM Classifiers with Indefinite Kernels | Suicheng Gu & Yuhong Guo, Temple University |
| Document Summarization Based on Data Reconstruction | Zhanying He, Zhejiang University; et al. Chun Chen, Zhejiang University Jiajun Bu, Zhejiang University Can Wang, Zhejiang University Lijan Zhang, Zhejiang University Deng Cai, Zhejiang University Xiaofei He, Zhejiang University | |
| 2011 | Complexity of and Algorithms for Borda Manipulation | Jessica Davies, University of Toronto; et al. George Katsirelos, University of Paris-Sud Nina Narodytska, University of New South Wales Toby Walsh, National ICT Australia |
| Dynamic Resource Allocation in Conservation Planning | Daniel Golovin, California Institute of Technology; et al. Andreas Krause, ETH Zurich Beth Gardner, North Carolina State University Sarah J. Converse, Patuxent Wildlife Research Center Steve Morey, United States Fish and Wildlife Service | |
| 2010 | A Novel Transition Based Encoding Scheme for Planning as Satisfiability | Ruoyun Huang, Washington University in St. Louis; et al. Yixin Chen, Washington University in St. Louis Weixiong Zhang, Washington University in St. Louis |
| How Incomplete Is Your Semantic Web Reasoner? Systematic Analysis of the Completeness of Query Ans... | Giorgos Stoilos, University of Oxford; et al. Bernardo Cuenca Grau, University of Oxford Ian Horrocks, University of Oxford | |
| 2008 | Optimal False-Name-Proof Voting Rules with Costly Voting | Liad Wagman & Vincent Conitzer, Duke University |
| How Good is Almost Perfect? | Malte Helmert & Gabriele Röger, University of Freiburg | |
| 2007 | PLOW: A Collaborative Task Learning Agent | James Allen, Florida Institute for Human and Machine Cognition; et al. Nathanael Chambers, Stanford University George Ferguson, University of Rochester Lucian Galescu, Florida Institute for Human and Machine Cognition Hyuckchul Jung, Florida Institute for Human and Machine Cognition Mary Swift, University of Rochester William Taysom, Florida Institute for Human and Machine Cognition |
| Thresholded Rewards: Acting Optimally in Timed, Zero-Sum Games | Colin McMillen & Manuela Veloso, Carnegie Mellon University | |
| 2006 | Model Counting: A New Strategy for Obtaining Good Bounds | Carla P. Gomes, Cornell University; et al. Ashish Sabharwal, Cornell University Bart Selman, Cornell University |
| Towards an Axiom System for Default Logic | Gerhard Lakemeyer, RWTH Aachen University Hector J. Levesque, University of Toronto | |
| 2005 | The Max K- Armed Bandit: A New Model of Exploration Applied to Search Heuristic Selection | Vincent A. Cicirello, Drexel University Stephen F. Smith, Carnegie Mellon University |
| 2004 | Learning and Inferring Transportation Routines | Lin Liao, University of Washington; et al. Dieter Fox, University of Washington Henry Kautz, University of Washington |
| 2002 | On Computing All Abductive Explanations | Thomas Eiter, TU Wien Kazuhisa Makino, Osaka University |
| 2000 | The Game of Hex: An Automatic Theorem-Proving Approach to Game Programming | Vadim V. Anshelevich, Vanshel Consulting |
| Automatic Invention of Integer Sequences | Simon Colton, University of Edinburgh; et al. Alan Bundy, University of Edinburgh Toby Walsh, University of York | |
| Statistics-Based Summarization -- Step One: Sentence Compression | Kevin Knight & Daniel Marcu, University of Southern California | |
| Local Search Characteristics of Incomplete SAT Procedures | Dale Schuurmans & Finnegan Southey, University of Waterloo | |
| 1999 | PROVERB: The Probabilistic Cruciverbalist | Greg A. Keim, Duke University; et al. Noam M. Shazeer, Duke University Michael L. Littman, Duke University Sushant Agarwal, Duke University Catherine M. Cheves, Duke University Joseph Fitzgerald, Duke University Jason Grosland, Duke University Fan Jiang, Duke University Shannon Pollard, Duke University Karl Weinmeister, Duke University |
| 1998 | Learning Evaluation Functions for Global Optimization and Boolean Satisfiability | Justin A. Boyan & Andrew W. Moore, Carnegie Mellon University |
| The Interactive Museum Tour-Guide Robot | Wolfram Burgard, University of Bonn; et al. Armin B. Cremers, University of Bonn Dieter Fox, University of Bonn Dirk Hähnel, University of Bonn Gerhard Lakemeyer, RWTH Aachen University Dirk Schulz, University of Bonn Walter Steiner, University of Bonn Sebastian Thrun, Carnegie Mellon University | |
| Acceleration Methods for Numeric CSPs | Yahia Lebbah & Olivier Lhomme, École des Mines de Nantes | |
| 1997 | Statistical Parsing with a Context-Free Grammar and Word Statistics | Eugene Charniak, Brown University |
| Building Concept Representations from Reusable Components | Peter Clark, Boeing Bruce Porter, University of Texas at Austin | |
| Fast Context Switching in Real-Time Propositional Reasoning | P. Pandurang Nayak & Brian C. Williams, Ames Research Center | |
| A Practical Algorithm for Finding Optimal Triangulations | Krill Shoikhet & Dan Geiger, Technion – Israel Institute of Technology | |
| 1996 | A Novel Application of Theory Refinement to Student Modeling | Paul T. Baffes, ScicomP Raymond J. Mooney, University of Texas at Austin |
| Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search | Henry Kautz & Bart Selman, AT&T Laboratories | |
| Verification of Knowledge Bases Based on Containment Checking | Alon Y. Levy, AT&T Laboratories Marie-Christine Rousset, University of Paris-Sud | |
作者：Keisuke Sakaguchi、Ronan Le Bras、Chandra Bhagavatula、Yejin Choi
论文介绍：
维诺格拉德模式挑战赛（Winograd Schema Challenge：WSC）是一个用于常识推理的基准测试，该测试有 273 个专家编写的问题，专门应对依赖选择偏好和词语联想的统计学模型。但是近来，许多模型在该基准测试的性能已达到 90%。因此，研究者希望了解，这些模型是否真正获得了鲁棒的常识能力。 因此，研究者提出了 WINOGRANDE，一个有着 44k 个问题的大规模数据集。该数据集在规模和难度上较之前的数据集更大。该数据集的构建包括两个步骤：首先使用众包的方式设计问题，然后使用一个新的 AFLITE 算法缩减系统偏见（systematic bias），使得人类可以察觉到的词汇联想转换成机器可以检测到的嵌入联想（embedding association）。现在最好的 SOTA 模型可以达到的性能是 59.4 – 79.1%，比人脸性能水平（94%）低 15-35%（绝对值）。这种性能波动取决于训练数据量（2% 到 100%）。
此外，研究者还在 5 个相关的基准数据集上进行了测试，取得了以下结果：WSC (→ 90.1%)、DPR (→ 93.1%)、COPA(→ 90.6%)、KnowRef (→ 85.6%) 和 Winogender (→ 97.1%)。 这说明，一方面 WINOGRANDE 是一个很好的迁移学习的资源；但另一方面，这说明我们现在高估了模型的常识推理的能力。研究者希望通过这项研究能够让学界重视减少算法的偏见。
作者：Yonathan Efroni, Gal Dalal, Bruno Scherrer, Shie Mannor
论文介绍：
有限时域前瞻策略(Finite-horizon lookahead policies)已经在强化学习中得到广泛应用，并取得了令人印象深刻的实证成果。通常，前瞻性策略是通过特定的规划方法实现的，例如蒙特卡洛树搜索(Monte Carlo Tree Search)，AlphaZero正是应用了该方法。将规划问题视为树搜索，实现上的一种合理做法是只备份叶节点上的值，而根节点上获得的信息只用于更新策略。
在这篇论文中，作者质疑了这种方法的有效性，认为后一过程通常是非收缩的，其收敛性没有保证。
论文提出一种简单明了的增强方法：使用最优树路径的返回值来备份根节点的后代的值。为了实现结果，作者引入一个称为多步贪婪一致性(multiple-step greedy consistency)的概念。然后，在树搜索阶段和值估计阶段同时注入噪声的情况下，为上述增强方法的两个算法实例提供收敛速度。
作者：Chenjun Xiao, University of Alberta；
Jincheng Mei, University of Alberta；Martin Müller, University of Alberta
论文介绍：
本文中提出记忆增强的蒙特卡洛树搜索（Memory-Augmented Monte Carlo Tree Search，M-MCTS）并对其进行了评估，提供了利用在线实时搜索的泛化能力的新方法。M-MCTS 的核心**是将 MCTS 结合一种记忆结构，其中每一项记录包含一个特定状态的信息。通过结合相似状态的估计，这些记忆被用于生成一个近似值估计。我们在本文中表明基于记忆的值逼近在温和条件下高概率地优于原始的蒙特卡洛评估方法。我们在围棋中评估了 M-MCTS。实验结果表明 M-MCTS 在相同的模拟次数下优于原始的 MCTS。
作者： Russell Stewart & Stefano Ermon, Stanford University
论文介绍：：
在许多机器学习应用中，带标签的数据数量稀少，要获得更多的标签造价昂贵。本文引入了一种新的神经网络监督学习方法，不是直接给出输入-输出对的直接示例，而是指定在输出空间上能够成立的约束。这些约束来源于先前的特定领域知识（domain knowledge），如已知物理定律。本文展示了这种方法在真实世界和模拟计算机视觉任务上的有效性。使用这种方法，在没有任何带标签的训练样本的情况下，成功训练了一个卷积神经网络来检测和跟踪对象。
作者：Robert C. Holte, University of Alberta；Ariel Felner, Ben-Gurion University；Guni Sharon, Ben-Gurion University；Nathan R. Sturtevant, University of Denver
摘要：
We present MM, the first bidirectional heuristic search algo- rithm whose forward and backward searches are guaranteed to “meet in the middle”, i.e. never expand a node beyond the solution midpoint. We also present a novel framework for comparing MM, A*, and brute-force search, and identify conditions favoring each algorithm. Finally, we present ex- perimental results that support our theoretical analysis.
作者：Florian Pommerening, University of Basel；Malte Helmert, University of Basel；Gabriele Röger, University of Basel；Jendrik Seipp, University of Basel
摘要：
Operator cost partitioning is a well-known technique to make admissible heuristics additive by distributing the operator costs among individual heuristics. Planning tasks are usu- ally defined with non-negative operator costs and therefore it appears natural to demand the same for the distributed costs. We argue that this requirement is not necessary and demonstrate the benefit of using general cost partitioning. We show that LP heuristics for operator-counting constraints are cost-partitioned heuristics and that the state equation heuris- tic computes a cost partitioning over atomic projections. We also introduce a new family of potential heuristics and show their relationship to general cost partitioning.
作者：Elias Bareinboim, University of California Los Angeles；
Jin Tian, Iowa State University；Judea Pearl, University of California Los Angeles
摘要：
Selection bias is caused by preferential exclusion of units from the samples and represents a major obstacle to valid causal and statistical inferences; it cannot be removed by randomized experiments and can rarely be detected in ei- ther experimental or observational studies. In this paper, we provide complete graphical and algorithmic conditions for recovering conditional probabilities from selection biased data. We also provide graphical conditions for recoverabil- ity when unbiased data is available over a subset of the vari- ables. Finally, we provide a graphical condition that gener- alizes the backdoor criterion and serves to recover causal ef- fects when the data is collected under preferential selection.
作者：Janardhan Rao Doppa, Oregon State University；Alan Fern, Oregon State University；Prasad Tadepalli, Oregon State University
摘要：
Structured prediction is the problem of learning a func- tion from structured inputs to structured outputs. In- spired by the recent successes of search-based struc- tured prediction, we introduce a new framework for structured prediction called HC-Search. Given a struc- tured input, the framework uses a search procedure guided by a learned heuristic H to uncover high qual- ity candidate outputs and then uses a separate learned cost function C to select a final prediction among those outputs. We can decompose the regret of the overall ap- proach into the loss due to H not leading to high qual- ity outputs, and the loss due to C not selecting the best among the generated outputs. Guided by this decompo- sition, we minimize the overall regret in a greedy stage- wise manner by first training H to quickly uncover high quality outputs via imitation learning, and then training C to correctly rank the outputs generated via H accord- ing to their true losses. Experiments on several bench- mark domains show that our approach significantly out- performs the state-of-the-art methods.
作者：Gary Doran & Soumya Ray, Case Western Reserve University
作者：Suicheng Gu & Yuhong Guo, Temple University
摘要：
Recently, training support vector machines with indef- inite kernels has attracted great attention in the ma- chine learning community. In this paper, we tackle this problem by formulating a joint optimization model over SVM classifications and kernel principal compo- nent analysis. We first reformulate the kernel principal component analysis as a general kernel transformation framework, and then incorporate it into the SVM clas- sification to formulate a joint optimization model. The proposed model has the advantage of making consistent kernel transformations over training and test samples. It can be used for both binary classification and multi- class classification problems. Our experimental results on both synthetic data sets and real world data sets show the proposed model can significantly outperform related approaches.
作者：Zhanying He, Zhejiang University； Chun Chen, Zhejiang University； Jiajun Bu, Zhejiang University； Can Wang, Zhejiang University； Lijan Zhang, Zhejiang University； Deng Cai, Zhejiang University； Xiaofei He, Zhejiang University
摘要：
Document summarization is of great value to many real world applications, such as snippets generation for search results and news headlines generation. Tradition- ally, document summarization is implemented by ex- tracting sentences that cover the main topics of a doc- ument with a minimum redundancy. In this paper, we take a different perspective from data reconstruction and propose a novel framework named Document Summa- rization based on Data Reconstruction (DSDR). Specif- ically, our approach generates a summary which consist of those sentences that can best reconstruct the original document. To model the relationship among sentences, we introduce two objective functions: (1) linear recon- struction, which approximates the document by linear combinations of the selected sentences; (2) nonnega- tive linear reconstruction, which allows only additive, not subtractive, linear combinations. In this framework, the reconstruction error becomes a natural criterion for measuring the quality of the summary. For each objec- tive function, we develop an efficient algorithm to solve the corresponding optimization problem. Extensive ex- periments on summarization benchmark data sets DUC 2006 and DUC 2007 demonstrate the effectiveness of our proposed approach.
作者：Daniel Golovin, California Institute of Technology； Andreas Krause, ETH Zurich； Beth Gardner, North Carolina State University； Sarah J. Converse, Patuxent Wildlife Research Center； Steve Morey, U.S. Fish and Wildlife Service
摘要： Consider the problem of protecting endangered species by selecting patches of land to be used for conservation purposes. Typically, the availability of patches changes over time, and recommendations must be made dynamically. This is a chal- lenging prototypical example of a sequential optimization problem under uncertainty in computational sustainability. Ex- isting techniques do not scale to problems of realistic size. In this paper, we develop an efficient algorithm for adaptively making recommendations for dynamic conservation planning, and prove that it obtains near-optimal performance. We further evaluate our approach on a detailed reserve design case study of conservation planning for three rare species in the Pacific Northwest of the United States.
作者：Jessica Davies, University of Toronto； George Katsirelos, Université Paris-Sud； Nina Narodytska, University of New South Wales； Toby Walsh, NICTA
摘要：
We prove that it is NP-hard for a coalition of two manipu- lators to compute how to manipulate the Borda voting rule. This resolves one of the last open problems in the computa- tional complexity of manipulating common voting rules. Be- cause of this NP-hardness, we treat computing a manipula- tion as an approximation problem where we try to minimize the number of manipulators. Based on ideas from bin pack- ing and multiprocessor scheduling, we propose two new ap- proximation methods to compute manipulations of the Borda rule. Experiments show that these methods significantly out- perform the previous best known approximation method. We are able to find optimal manipulations in almost all the ran- domly generated elections tested. Our results suggest that, whilst computing a manipulation of the Borda rule by a coali- tion is NP-hard, computational complexity may provide only a weak barrier against manipulation in practice.
作者：Giorgos Stoilos, Oxford University； Bernardo Cuenca Grau, Oxford University； Ian Horrocks, Oxford University
摘要：
Conjunctive query answering is a key reasoning service for many ontology-based applications. In order to improve scal- ability, many Semantic Web query answering systems give up completeness (i.e., they do not guarantee to return all query answers). It may be useful or even critical to the designers and users of such systems to understand how much and what kind of information is (potentially) being lost. We present a method for generating test data that can be used to provide at least partial answers to these questions, a purpose for which existing benchmarks are not well suited. In addition to devel- oping a general framework that formalises the problem, we describe practical data generation algorithms for some pop- ular ontology languages, and present some very encouraging results from our preliminary evaluation.
A Novel Transition Based Encoding Scheme for Planning as Satisfiability
作者：Ruoyun Huang, Washington University in St. Louis； Yixin Chen, Washington University in St. Louis； Weixiong Zhang, Washington University in St. Louis
摘要：
Planning as satisfiability is a principal approach to plan- ning with many eminent advantages. The existing plan- ning as satisfiability techniques usually use encodings compiled from the STRIPS formalism. We introduce a novel SAT encoding scheme based on the SAS+ formal- ism. It exploits the structural information in the SAS+ formalism, resulting in more compact SAT instances and reducing the number of clauses by up to 50 fold. Our results show that this encoding scheme improves upon the STRIPS-based encoding, in terms of both time and memory efficiency.
作者：Malte Helmert & Gabriele Röger, Albert-Ludwigs-Universität Freiburg
摘要：
Heuristic search using algorithms such as A∗ and IDA∗ is the prevalent method for obtaining optimal sequential solu- tions for classical planning tasks. Theoretical analyses of these classical search algorithms, such as the well-known re- sults of Pohl, Gaschnig and Pearl, suggest that such heuristic search algorithms can obtain better than exponential scaling behaviour, provided that the heuristics are accurate enough. Here, we show that for a number of common planning bench- mark domains, including ones that admit optimal solution in polynomial time, general search algorithms such as A∗ must necessarily explore an exponential number of search nodes even under the optimistic assumption of almost per- fect heuristic estimators, whose heuristic error is bounded by a small additive constant. Our results shed some light on the comparatively bad per- formance of optimal heuristic search approaches in “simple” planning domains such as GRIPPER. They suggest that in many applications, further improvements in run-time require changes to other parts of the search algorithm than the heuris- tic estimator.
作者：Liad Wagman & Vincent Conitzer, Duke University
摘要：
One way for agents to reach a joint decision is to vote over the alternatives. In open, anonymous settings such as the Inter- net, an agent can vote more than once without being detected. A voting rule is false-name-proof if no agent ever benefits from casting additional votes. Previous work has shown that all false-name-proof voting rules are unresponsive to agents’ preferences. However, that work implicitly assumes that cast- ing additional votes is costless. In this paper, we consider what happens if there is a cost to casting additional votes. We characterize the optimal (most responsive) false-name-proof- with-costs voting rule for 2 alternatives. In sharp contrast to the costless setting, we prove that as the voting population grows larger, the probability that this rule selects the major- ity winner converges to 1. We also characterize the optimal group false-name-proof rule for 2 alternatives, which is ro- bust to coalitions of agents sharing the costs of additional votes. Unfortunately, the probability that this rule chooses the majority winner as the voting population grows larger is relatively low. We derive an analogous rule in a setting with 3 alternatives, and provide bounding results and computational approaches for settings with 4 or more alternatives.
作者：James Allen, Institute for Human and Machine Cognition； Nathanael Chambers, Stanford University； George Ferguson, University of Rochester； Lucian Galescu, Institute for Human and Machine Cognition； Hyuckchul Jung, Institute for Human and Machine Cognition； Mary Swift, University of Rochester； William Taysom, Institute for Human and Machine Cognition
摘要：
To be effective, an agent that collaborates with humans needs to be able to learn new tasks from humans they work with. This paper describes a system that learns executable task models from a single collaborative learning session consisting of demonstration, explanation and dialogue. To accomplish this, the system integrates a range of AI tech- nologies: deep natural language understanding, knowledge representation and reasoning, dialogue systems, plan- ning/agent-based systems and machine learning. A formal evaluation shows the approach has great promise.
作者：Colin McMillen & Manuela Veloso, Carnegie Mellon University
摘要：
In timed, zero-sum games, the goal is to maximize the prob- ability of winning, which is not necessarily the same as max- imizing our expected reward. We consider cumulative inter- mediate reward to be the difference between our score and our opponent’s score; the “true” reward of a win, loss, or tie is determined at the end of a game by applying a thresh- old function to the cumulative intermediate reward. We in- troduce thresholded-rewards problems to capture this depen- dency of the final reward outcome on the cumulative interme- diate reward. Thresholded-rewards problems reflect different real-world stochastic planning domains, especially zero-sum games, in which time and score need to be considered. We investigate the application of thresholded rewards to finite- horizon Markov Decision Processes (MDPs). In general, the optimal policy for a thresholded-rewards MDP will be non- stationary, depending on the number of time steps remain- ing and the cumulative intermediate reward. We introduce an efficient value iteration algorithm that solves thresholded- rewards MDPs exactly, but with running time quadratic on the number of states in the MDP and the length of the time horizon. We investigate a number of heuristic-based tech- niques that efficiently find approximate solutions for MDPs with large state spaces or long time horizons.
作者：Carla P. Gomes, Cornell University； Ashish Sabharwal, Cornell University； Bart Selman, Cornell University
摘要：
Model counting is the classical problem of computing the number of solutions of a given propositional formula. It vastly generalizes the NP-complete problem of propositional satisfiability, and hence is both highly useful and extremely expensive to solve in practice. We present a new approach to model counting that is based on adding a carefully cho- sen number of so-called streamlining constraints to the input formula in order to cut down the size of its solution space in a controlled manner. Each of the additional constraints is a randomly chosen XOR or parity constraint on the prob- lem variables, represented either directly or in the standard CNF form. Inspired by a related yet quite different theoretical study of the properties of XOR constraints, we provide a for- mal proof that with high probability, the number of XOR con- straints added in order to bring the formula to the boundary of being unsatisfiable determines with high precision its model count. Experimentally, we demonstrate that this approach can be used to obtain good bounds on the model counts for for- mulas that are far beyond the reach of exact counting meth- ods. In fact, we obtain the first non-trivial solution counts for very hard, highly structured combinatorial problem instances. Note that unlike other counting techniques, such as Markov Chain Monte Carlo methods, we are able to provide high- confidence guarantees on the quality of the counts obtained.
作者：Gerhard Lakemeyer, RWTH Aachen University； Hector J. Levesque, University of Toronto
摘要：
Recently, Lakemeyer and Levesque proposed a logic of only- knowing which precisely captures three forms of nonmono- tonic reasoning: Moore’s Autoepistemic Logic, Konolige’s variant based on moderately grounded expansions, and Rei- ter’s default logic. Defaults have a uniform representation under all three interpretations in the new logic. Moreover, the logic itself is monotonic, that is, nonmonotonic reasoning is cast in terms of validity in the classical sense. While Lake- meyer and Levesque gave a model-theoretic account of their logic, a proof-theoretic characterization remained open. This paper fills that gap for the propositional subset: a sound and complete axiom system in the new logic for all three varieties of default reasoning. We also present formal derivations for some examples of default reasoning. Finally we present evi- dence that it is unlikely that a complete axiom system exists in the first-order case, even when restricted to the simplest forms of default reasoning.
作者：Vincent A. Cicirello, Drexel University； Stephen F. Smith, Carnegie Mellon University
摘要：
The multiarmed bandit is often used as an analogy for the tradeoff between exploration and exploitation in search prob- lems. The classic problem involves allocating trials to the arms of a multiarmed slot machine to maximize the expected sum of rewards. We pose a new variation of the multiarmed bandit—the Max K-Armed Bandit—in which trials must be allocated among the arms to maximize the expected best sin- gle sample reward of the series of trials. Motivation for the Max K-Armed Bandit is the allocation of restarts among a set of multistart stochastic search algorithms. We present an analysis of this Max K-Armed Bandit showing under certain assumptions that the optimal strategy allocates trials to the observed best arm at a rate increasing double exponentially relative to the other arms. This motivates an exploration strat- egy that follows a Boltzmann distribution with an exponen- tially decaying temperature parameter. We compare this ex- ploration policy to policies that allocate trials to the observed best arm at rates faster (and slower) than double exponen- tially. The results confirm, for two scheduling domains, that the double exponential increase in the rate of allocations to the observed best heuristic outperforms the other approaches.
作者：Lin Liao, University of Washington； Dieter Fox, University of Washington； Henry Kautz, University of Washington
摘要：
This paper introduces a hierarchical Markov model that can learn and infer a user’s daily movements through the commu- nity. The model uses multiple levels of abstraction in order to bridge the gap between raw GPS sensor measurements and high level information such as a user’s mode of transporta- tion or her goal. We apply Rao-Blackwellised particle filters for efficient inference both at the low level and at the higher levels of the hierarchy. Significant locations such as goals or locations where the user frequently changes mode of trans- portation are learned from GPS data logs without requiring any manual labeling. We show how to detect abnormal be- haviors (e.g. taking a wrong bus) by concurrently tracking his activities with a trained and a prior model. Experiments show that our model is able to accurately predict the goals of a per- son and to recognize situations in which the user performs un- known activities.
作者：Thomas Eiter, Technische Universität Wien； Kazuhisa Makino, Osaka University
摘要：
We consider the computation of all respectively a polynomial subset of the explanations of an abductive query from a Horn theory, and pay particular attention to whether the query is a positive or negative letter, the explanation is based on lit- erals from an assumption set, and the Horn theory is rep- resented in terms of formulas or characteristic models. We derive tractability results, one of which refutes a conjecture by Selman and Levesque, as well as intractability results, and furthermore also semi-tractability results in terms of solvabil- ity in quasi-polynomial time. Our results complement previ- ous results in the literature, and elucidate the computational complexity of generating the set of explanations.
作者：Vadim V. Anshelevich, Vanshel Consulting
摘要：
The game of Hex is a two-player game with simple rules, a deep underlying mathematical beauty, and a strategic complexity comparable to that of Chess and Go. The massive game-tree search techniques developed mostly for Chess, and successfully used for Checkers, Othello, and a number of other games, become less useful for games with large branching factors like Go and Hex. We offer a new approach, which results in superior playing strength. This approach emphasizes deep analysis of relatively few game positions. In order to reach this goal, we develop an automatic theorem proving technique for topological analysis of Hex positions. We also discuss in detail an idea of modeling Hex positions with electrical resistor circuits. We explain how this approach is implemented in Hexy - the strongest known Hex-playing computer program, able to compete with best human players.
作者：Greg A. Keim, Duke University； Noam M. Shazeer, Duke University； Michael L. Littman, Duke University； Sushant Agarwal, Duke University； Catherine M. Cheves, Duke University； Joseph Fitzgerald, Duke University； Jason Grosland, Duke University； Fan Jiang, Duke University； Shannon Pollard, Duke University； Karl Weinmeister, Duke University
作者：Justin A. Boyan & Andrew W. Moore, Carnegie Mellon University
Acceleration Methods for Numeric CSPs
作者：Yahia Lebbah & Olivier Lhomme, Ecole des Mines de Nantes
The Interactive Museum Tour-Guide Robot
作者：Wolfram Burgard, University of Bonn； Armin B. Cremers, University of Bonn； Dieter Fox, University of Bonn； Dirk Hähnel, University of Bonn； Gerhard Lakemeyer, Aachen University of Technology； Dirk Schulz, University of Bonn； Walter Steiner, University of Bonn； Sebastian Thrun, Carnegie Mellon University
作者：Eugene Charniak, Brown University
作者：Krill Shoikhet & Dan Geiger, Technion
作者：P. Pandurang Nayak & Brian C. Williams, NASA Ames Research Center
作者：Peter Clark, Boeing； Bruce Porter, University of Texas at Austin
作者：Alon Y. Levy, AT&T Laboratories； Marie-Christine Rousset, Université Paris-Sud
作者：Paul T. Baffes, SciComp； Raymond J. Mooney, University of Texas at Austin
作者：Henry Kautz & Bart Selman, AT&T Laboratories
【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 实验室）
摘要
通过与一个通用的、随机的搜索算法，以及基于命题逻辑问题编码，本文作者解决了复杂的规划问题，并且比最好的循环规划系统要快很多倍。虽然在许多规划问题上，随机的方法已经被证明很有效 ，但是，本研究首次展现了其在真实的经典规划问题上的应用。本研究还提供了一个看待规划问题中表征问题的新视角。