Journal of Artificial Intelligence Resarch: Volume 60の論文一覧

Journal of Artificial Intelligence Resarch Vol. 60 (2017)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。

論文

Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation

Complexity Results and Algorithms for Extension Enforcement in Abstract Argumentation / 抽象的議論における拡張強制の複雑性結果とアルゴリズム

Argumentation is an active area of modern artificial intelligence (AI) research, with connections to a range of fields, from computational complexity theory and knowledge representation and reasoning to philosophy and social sciences, as well as application-oriented work in domains such as legal reasoning, multi-agent systems, and decision support. Argumentation frameworks (AFs) of abstract argumentation have become the graph-based formal model of choice for many approaches to argumentation in AI, with semantics defining sets of jointly acceptable arguments, i.e., extensions. Understanding the dynamics of AFs has been recently recognized as an important topic in the study of argumentation in AI. In this work, we focus on the so-called extension enforcement problem in abstract argumentation as a recently proposed form of argumentation dynamics. We provide a nearly complete computational complexity map of argument-fixed extension enforcement under various major AF semantics, with results ranging from polynomial-time algorithms to completeness for the second level of the polynomial hierarchy. Complementing the complexity results, we propose algorithms for NP-hard extension enforcement based on constraint optimization under the maximum satisfiability (MaxSAT) paradigm. Going beyond NP, we propose novel MaxSAT-based counterexample-guided abstraction refinement procedures for the second-level complete problems and present empirical results on a prototype system constituting the first approach to extension enforcement in its generality.



議論は、現代の人工知能（AI）研究において活発に研究されている分野であり、計算複雑性理論や知識表現・推論から哲学や社会科学、さらには法的推論、マルチエージェントシステム、意思決定支援といった分野における応用指向の研究に至るまで、幅広い分野と関連しています。抽象的議論の議論フレームワーク（AF）は、AIにおける議論への多くのアプローチにおいて、グラフベースの形式モデルとして広く採用され、その意味論は、共同で受け入れ可能な議論の集合、すなわち拡張を定義します。AFのダイナミクスを理解することは、近年、AIにおける議論研究における重要なトピックとして認識されています。本研究では、最近提案された議論ダイナミクスの一形態として、抽象的議論におけるいわゆる拡張強制問題に焦点を当てます。様々な主要なAF意味論における、議論固定拡張強制のほぼ完全な計算複雑性マップを提供し、多項式時間アルゴリズムから多項式階層の第2レベルの完全性に至るまでの結果を報告します。計算量に関する結果を補完し、最大充足可能性（MaxSAT）パラダイムにおける制約最適化に基づくNP困難な拡張強化アルゴリズムを提案します。NPを超えて、第2レベル完全問題に対する新しいMaxSATベースの反例誘導型抽象化改良手順を提案し、その一般性において拡張強化への最初のアプローチを構成するプロトタイプシステムにおける実証結果を示す。

Learning Neural Audio Embeddings for Grounding Semantics in Auditory Perception

Learning Neural Audio Embeddings for Grounding Semantics in Auditory Perception / 聴覚知覚におけるグラウンディング・セマンティクスのためのニューラル・オーディオ埋め込みの学習

Multi-modal semantics, which aims to ground semantic representations in perception, has relied on feature norms or raw image data for perceptual input. In this paper we examine grounding semantic representations in raw auditory data, using standard evaluations for multi-modal semantics. After having shown the quality of such auditorily grounded representations, we show how they can be applied to tasks where auditory perception is relevant, including two unsupervised categorization experiments, and provide further analysis. We find that features transfered from deep neural networks outperform bag of audio words approaches. To our knowledge, this is the first work to construct multi-modal models from a combination of textual information and auditory information extracted from deep neural networks, and the first work to evaluate the performance of tri-modal (textual, visual and auditory) semantic models.



知覚に意味的表現を基盤づけることを目指すマルチモーダル意味論は、知覚入力として特徴規範や生画像データに依存してきた。本稿では、マルチモーダル意味論の標準的な評価を用いて、生の聴覚データにおける意味的表現の基盤づけを検討します。このような聴覚に基盤づけられた表現の品質を示した後、2つの教師なし分類実験を含む、聴覚知覚が関連するタスクへの適用方法を示し、さらなる分析を行う。深層ニューラルネットワークから転送された特徴量は、バッグ・オブ・オーディオ・ワード手法よりも優れていることがわかった。我々の知る限り、これはディープニューラルネットワークから抽出したテキスト情報と聴覚情報の組み合わせからマルチモーダルモデルを構築した初の研究であり、またトライモーダル（テキスト、視覚、聴覚）セマンティックモデルの性能を評価した初の研究です。

Confidence Decision Trees via Online and Active Learning for Streaming Data

Confidence Decision Trees via Online and Active Learning for Streaming Data / ストリーミングデータのためのオンラインおよび能動学習による信頼度決定木

Decision tree classifiers are a widely used tool in data stream mining. The use of confidence intervals to estimate the gain associated with each split leads to very effective methods, like the popular Hoeffding tree algorithm. From a statistical viewpoint, the analysis of decision tree classifiers in a streaming setting requires knowing when enough new information has been collected to justify splitting a leaf. Although some of the issues in the statistical analysis of Hoeffding trees have been already clarified, a general and rigorous study of confidence intervals for splitting criteria is missing. We fill this gap by deriving accurate confidence intervals to estimate the splitting gain in decision tree learning with respect to three criteria: entropy, Gini index, and a third index proposed by Kearns and Mansour. We also extend our confidence analysis to a selective sampling setting, in which the decision tree learner adaptively decides which labels to query in the stream. We provide theoretical guarantees bounding the probability that the decision tree learned via our selective sampling strategy classifies suboptimally the next example in the stream. Experiments on real and synthetic data in a streaming setting show that our trees are indeed more accurate than trees with the same number of leaves generated by state-of-the-art techniques. In addition to that, our active learning module empirically uses fewer labels without significantly hurting the performance.



決定木分類器は、データストリームマイニングにおいて広く用いられているツールです。各分割に関連するゲインを推定するために信頼区間を用いることで、広く用いられているHoeffding木アルゴリズムのような非常に効果的な手法が生まれます。統計的観点から、ストリーミング環境における決定木分類器の分析には、葉の分割を正当化するのに十分な新規情報がいつ収集されたかを知ることが必要です。Hoeffding木の統計分析におけるいくつかの問題は既に解明されているものの、分割基準に関する信頼区間の一般的かつ厳密な研究は不足しています。我々は、エントロピー、ジニ係数、そしてKearnsとMansourによって提案された3つ目の係数という3つの基準に関して、決定木学習における分割ゲインを推定するための正確な信頼区間を導出することで、このギャップを埋める。また、信頼度分析を選択的サンプリング設定に拡張し、決定木学習器がストリーム内でどのラベルをクエリするかを適応的に決定します。選択的サンプリング戦略によって学習した決定木が、ストリーム内の次の例を準最適に分類する確率を制限する理論的な保証を提供します。ストリーミング設定における実際のデータと合成データを用いた実験では、私たちの決定木は、最先端技術で生成された同じ葉数の決定木よりも実際に正確であることが示されました。さらに、私たちの能動学習モジュールは、パフォーマンスを大幅に損なうことなく、経験的にラベルの使用数を減らしています。

Axiomatising Incomplete Preferences through Sets of Desirable Gambles

Axiomatising Incomplete Preferences through Sets of Desirable Gambles / 望ましいギャンブル集合による不完全な選好の公理化

We establish the equivalence of two very general theories: the first is the decision-theoretic formalisation of incomplete preferences based on the mixture independence axiom; the second is the theory of coherent sets of desirable gambles (bounded variables) developed in the context of imprecise probability and extended here to vector-valued gambles. Such an equivalence allows us to analyse the theory of incomplete preferences from the point of view of desirability. Among other things, this leads us to uncover an unexpected and clarifying relation: that the notion of `state independence’—the traditional assumption that we can have separate models for beliefs (probabilities) and values (utilities)—coincides with that of `strong independence’ in imprecise probability; this connection leads us also to propose much weaker, and arguably more realistic, notions of state independence. Then we simplify the treatment of complete beliefs and values by putting them on a more equal footing. We study the role of the Archimedean condition—which allows us to actually talk of expected utility—, identify some weaknesses and propose alternatives that solve these. More generally speaking, we show that desirability is a valuable alternative foundation to preferences for decision theory that streamlines and unifies a number of concepts while preserving great generality. In addition, the mentioned equivalence shows for the first time how to extend the theory of desirability to imprecise non-linear utility, thus enabling us to formulate one of the most powerful self-consistent theories of reasoning and decision-making available today.



我々は、2つの非常に一般的な理論の同値性を確立します。1つ目は、混合独立性公理に基づく不完全選好の意思決定理論的形式化です。2つ目は、不正確な確率の文脈で展開され、ここではベクトル値ギャンブルに拡張された、望ましいギャンブル（有界変数）の整合集合の理論です。この同値性により、不完全選好の理論を望ましさの観点から分析することが可能になります。とりわけ、この同値性は、予期せぬ、かつ明快な関係を発見することにつながる。「状態独立性」という概念、つまり信念（確率）と価値（効用）に別々のモデルを持つことができるという従来の仮定は、不正確な確率における「強い独立性」という概念と一致します。この関係性は、状態独立性について、より弱く、そしておそらくより現実的な概念を提案することにもつながる。そして、完全な信念と価値をより同等の立場に置くことで、それらの扱いを簡素化します。我々は、期待効用について実際に議論することを可能にするアルキメデスの条件の役割を研究し、いくつかの弱点を特定し、それらを解決する代替案を提案します。より一般的に言えば、望ましさは、多くの概念を合理化・統合しながら高い一般性を維持する、意思決定理論に対する選好の重要な代替基盤であることを示す。さらに、前述の同値性は、望ましさの理論を不正確な非線形効用へと拡張する方法を初めて示し、これにより、今日利用可能な最も強力で自己整合的な推論および意思決定理論の1つを定式化することを可能にします。

A Game Theoretic Analysis of the Adversarial Retrieval Setting

A Game Theoretic Analysis of the Adversarial Retrieval Setting / 敵対的検索設定のゲーム理論的分析

The main goal of search engines is ad hoc retrieval: ranking documents in a corpus by their relevance to the information need expressed by a query. The Probability Ranking Principle (PRP) — ranking the documents by their relevance probabilities — is the theoretical foundation of most existing ad hoc document retrieval methods. A key observation that motivates our work is that the PRP does not account for potential post-ranking effects; specifically, changes to documents that result from a given ranking. Yet, in adversarial retrieval settings such as the Web, authors may consistently try to promote their documents in rankings by changing them. We prove that, indeed, the PRP can be sub-optimal in adversarial retrieval settings. We do so by presenting a novel game theoretic analysis of the adversarial setting. The analysis is performed for different types of documents (single-topic and multi-topic) and is based on different assumptions about the writing qualities of documents’ authors. We show that in some cases, introducing randomization into the document ranking function yields an overall user utility that transcends that of applying the PRP.



検索エンジンの主な目的は、アドホック検索、すなわち、クエリによって表現された情報ニーズとの関連性に基づいてコーパス内の文書をランク付けすることです。確率ランキング原理（PRP）（文書を関連確率によってランク付けする）は、既存のほとんどのアドホック文書検索方法の理論的基盤となっています。我々の研究の動機となった重要な観察は、PRPが潜在的なランキング後効果を考慮していないということです。具体的には、与えられたランキングの結果として生じる文書への変更です。しかし、Webなどの敵対的検索環境では、著者は一貫して自分の文書を変更することでランキングで上位にランクインさせようとする可能性があります。私たちは、実際に敵対的検索環境ではPRPが最適ではないことを証明します。そのために、敵対的環境の新しいゲーム理論的分析を提示します。分析は、さまざまな種類の文書(単一トピックおよび複数トピック)に対して実行され、文書の著者の執筆品質に関するさまざまな仮定に基づいています。場合によっては、文書のランキング関数にランダム化を導入すると、PRPを適用した場合を超える全体的なユーザー効用が得られることを示します。

A Knowledge Level Account of Forgetting

A Knowledge Level Account of Forgetting / 忘却に関する知識レベルの説明

Forgetting is an operation on knowledge bases that has been addressed in different areas of Knowledge Representation and with respect to different formalisms, including classical propositional and first-order logic, modal logics, logic programming, and description logics. Definitions of forgetting have been expressed in terms of manipulation of formulas, sets of postulates, isomorphisms between models, bisimulations, second-order quantification, elementary equivalence, and others. In this paper, forgetting is regarded as an abstract belief change operator, independent of the underlying logic. The central thesis is that forgetting amounts to a reduction in the language, specifically the signature, of a logic. The main definition is simple: the result of forgetting a portion of a signature in a theory is given by the set of logical consequences of this theory over the reduced language. This definition offers several advantages. Foremost, it provides a uniform approach to forgetting, with a definition that is applicable to any logic with a well-defined consequence relation. Hence it generalises a disparate set of logic-specific definitions with a general, high-level definition. Results obtained in this approach are thus applicable to all subsumed formal systems, and many results are obtained much more straightforwardly. This view also leads to insights with respect to specific logics: for example, forgetting in first-order logic is somewhat different from the accepted approach. Moreover, the approach clarifies the relation between forgetting and related operations, including belief contraction.



忘却は、知識ベースに対する操作であり、古典的な命題論理と一階述語論理、様相論理、論理プログラミング、記述論理など、知識表現のさまざまな分野でさまざまな形式主義に関して取り上げられてきました。忘却の定義は、これまで、数式、公理の集合、モデル間の同型性、双模倣、二階量化、基本同値性などの操作によって表現されてきました。本論文では、忘却は、基礎となる論理とは独立した抽象的な信念変更演算子とみなされます。中心となるテーゼは、忘却は論理の言語、特にシグネチャの縮約に相当するというものです。主な定義は単純です。理論のシグネチャの一部を忘却した結果は、縮約された言語におけるこの理論の論理的帰結の集合によって与えられます。この定義にはいくつかの利点があります。まず第一に、この定義は忘却に対する統一的なアプローチを提供し、明確に定義された帰結関係を持つあらゆる論理に適用可能な定義を提供します。したがって、論理固有のさまざまな定義を、一般的な高レベルの定義によって一般化します。したがって、このアプローチで得られる結果は、包含されるすべての形式体系に適用でき、多くの結果がはるかに直接的に得られます。この見解は、特定の論理に関する洞察にもつながります。例えば、一階述語論理における忘却は、従来のアプローチとは若干異なります。さらに、このアプローチは、忘却と、信念収縮を含む関連する操作との関係を明らかにします。

Rationalisation of Profiles of Abstract Argumentation Frameworks: Characterisation and Complexity

Rationalisation of Profiles of Abstract Argumentation Frameworks: Characterisation and Complexity / 抽象的議論フレームワークのプロファイルの合理化：特徴づけと複雑性

Different agents may have different points of view. Following a popular approach in the artificial intelligence literature, this can be modeled by means of different abstract argumentation frameworks, each consisting of a set of arguments the agent is contemplating and a binary attack-relation between them. A question arising in this context is whether the diversity of views observed in such a profile of argumentation frameworks is consistent with the assumption that every individual argumentation framework is induced by a combination of, first, some basic factual attack-relation between the arguments and, second, the personal preferences of the agent concerned regarding the moral or social values the arguments under scrutiny relate to. We treat this question of rationalisability of a profile as an algorithmic problem and identify tractable and intractable cases. In doing so, we distinguish different constraints on admissible rationalisations, e.g., concerning the types of preferences used or the number of distinct values involved. We also distinguish two different semantics for rationalisability, which differ in the assumptions made on how agents treat attacks between arguments they do not report. This research agenda, bringing together ideas from abstract argumentation and social choice, is useful for understanding what types of profiles can reasonably be expected to occur in a multiagent system.



異なるエージェントは異なる視点を持つ場合があります。人工知能分野の文献でよく用いられるアプローチに従えば、これは異なる抽象的な議論フレームワークによってモデル化できます。それぞれのフレームワークは、エージェントが検討している議論の集合と、それらの間の二項攻撃関係から構成されます。この文脈で生じる疑問は、議論フレームワークのプロファイルに見られる視点の多様性が、個々の議論フレームワークが、第一に議論間の基本的な事実上の攻撃関係と、第二に、検討対象の議論が関連する道徳的または社会的価値に関する当該エージェントの個人的な選好の組み合わせによって誘導されるという仮定と整合するかどうかです。我々は、プロファイルの合理化可能性というこの問題をアルゴリズムの問​​題として扱い、扱いやすいケースと扱いにくいケースを特定します。その際、許容される合理化に関する異なる制約、例えば、使用される選好の種類や関連する異なる価値の数などについて、制約を区別します。また、合理化可能性に関して2つの異なる意味論を区別します。これらは、エージェントが報告しない議論間の攻撃をどのように扱うかという仮定が異なります。この研究課題は、抽象的議論と社会的選択の知見を統合したもので、マルチエージェントシステムにおいてどのような種類のプロファイルが合理的に発生する可能性があるかを理解する上で有用です。

Combining Lexical and Syntactic Features for Detecting Content-Dense Texts in News

Combining Lexical and Syntactic Features for Detecting Content-Dense Texts in News / ニュースにおける内容密度の高いテキストの検出のための語彙的特徴と統語的特徴の統合

Content-dense news report important factual information about an event in direct, succinct manner. Information seeking applications such as information extraction, question answering and summarization normally assume all text they deal with is content-dense. Here we empirically test this assumption on news articles from the business, U.S. international relations, sports and science journalism domains. Our findings clearly indicate that about half of the news texts in our study are in fact not content-dense and motivate the development of a supervised content-density detector. We heuristically label a large training corpus for the task and train a two-layer classifying model based on lexical and unlexicalized syntactic features. On manually annotated data, we compare the performance of domain-specific classifiers, trained on data only from a given news domain and a general classifier in which data from all four domains is pooled together. Our annotation and prediction experiments demonstrate that the concept of content density varies depending on the domain and that naive annotators provide judgement biased toward the stereotypical domain label. Domain-specific classifiers are more accurate for domains in which content-dense texts are typically fewer. Domain independent classifiers reproduce better naive crowdsourced judgements. Classification prediction is high across all conditions, around 80%.



コンテンツ密度の高いニュースは、ある出来事に関する重要な事実情報を、直接的かつ簡潔に伝えます。情報抽出、質問応答、要約といった情報探索アプリケーションは、通常、扱うすべてのテキストがコンテンツ密度が高いと想定します。本研究では、ビジネス、米国国際関係、スポーツ、科学ジャーナリズム分野のニュース記事を用いて、この想定を実証的に検証します。その結果、本研究で用いたニューステキストの約半数は実際にはコンテンツ密度が高くないことが明確に示され、教師ありコンテンツ密度検出器の開発の動機付けとなりました。本研究では、このタスクのために大規模な学習コーパスにヒューリスティックなラベルを付与し、語彙的特徴と非語彙化統語的特徴に基づく2層分類モデルを学習します。手動で注釈を付けたデータを用いて、特定のニュース分野のデータのみで学習した分野固有の分類器と、4つの分野すべてのデータを統合した汎用分類器の性能を比較します。我々のアノテーションと予測実験は、コンテンツ密度の概念がドメインによって変化し、ナイーブなアノテーターはステレオタイプなドメインラベルに偏った判断を下すことを示しています。ドメイン固有の分類器は、コンテンツ密度の高いテキストが通常少ないドメインではより正確です。ドメイン非依存の分類器は、ナイーブなクラウドソーシングによる判断をより良く再現します。分類予測はすべての条件において約80%と高い値を示しました。

On the Semantics and Complexity of Probabilistic Logic Programs

On the Semantics and Complexity of Probabilistic Logic Programs / 確率論理プログラムの意味論と複雑性について

We examine the meaning and the complexity of probabilistic logic programs that consist of a set of rules and a set of independent probabilistic facts (that is, programs based on Sato’s distribution semantics). We focus on two semantics, respectively based on stable and on well-founded models. We show that the semantics based on stable models (referred to as the “credal semantics”) produces sets of probability measures that dominate infinitely monotone Choquet capacities; we describe several useful consequences of this result. We then examine the complexity of inference with probabilistic logic programs. We distinguish between the complexity of inference when a probabilistic program and a query are given (the inferential complexity), and the complexity of inference when the probabilistic program is fixed and the query is given (the query complexity, akin to data complexity as used in database theory). We obtain results on the inferential and query complexity for acyclic, stratified, and normal propositional and relational programs; complexity reaches various levels of the counting hierarchy and even exponential levels.



我々は、ルールの集合と独立した確率的事実の集合からなる確率論理プログラム（すなわち、佐藤の分布意味論に基づくプログラム）の意味と複雑さを検証します。我々は、それぞれ安定モデルとwell-foundedモデルに基づく2つの意味論に焦点を当てます。安定モデルに基づく意味論（「信条意味論」と呼ばれる）は、無限単調なショケ容量を支配する確率測度の集合を生成することを示します。この結果から得られるいくつかの有用な帰結について説明します。次に、確率論理プログラムによる推論の複雑さを検証します。確率プログラムとクエリが与えられた場合の推論の複雑さ（推論複雑さ）と、確率プログラムが固定されクエリが与えられた場合の推論の複雑さ（クエリ複雑さ、データベース理論で用いられるデータ複雑さに類似）を区別します。非巡回型、層別型、および正規型の命題プログラムおよび関係プログラムについて、推論複雑さとクエリ複雑さに関する結果を得る。複雑さは計数階層の様々なレベル、さらには指数関数レベルに達します。

The Linear Programming Approach to Reach-Avoid Problems for Markov Decision Processes

The Linear Programming Approach to Reach-Avoid Problems for Markov Decision Processes / マルコフ決定過程の到達回避問題への線形計画法アプローチ

One of the most fundamental problems in Markov decision processes is analysis and control synthesis for safety and reachability specifications. We consider the stochastic reach-avoid problem, in which the objective is to synthesize a control policy to maximize the probability of reaching a target set at a given time, while staying in a safe set at all prior times. We characterize the solution to this problem through an infinite dimensional linear program. We then develop a tractable approximation to the infinite dimensional linear program through finite dimensional approximations of the decision space and constraints. For a large class of Markov decision processes modeled by Gaussian mixtures kernels we show that through a proper selection of the finite dimensional space, one can further reduce the computational complexity of the resulting linear program. We validate the proposed method and analyze its potential with numerical case studies.



マルコフ決定過程における最も基本的な問題の一つは、安全性と到達可能性の仕様に関する分析と制御合成です。本研究では、確率的到達回避問題を考察します。この問題の目的は、与えられた時間に目標集合に到達する確率を最大化し、かつそれ以前の全ての時点では安全集合に留まるように制御方策を合成することです。本研究ではこの問題の解を無限次元線形計画問題で特徴付ける。次に、決定空間と制約条件の有限次元近似を用いて、無限次元線形計画問題への扱いやすい近似を展開します。ガウス混合カーネルによってモデル化されたマルコフ決定過程の大規模なクラスについて、有限次元空間を適切に選択することで、結果として得られる線形計画問題の計算量をさらに削減できることを示す。本研究では提案手法を検証し、数値ケーススタディを用いてその可能性を分析します。

Residual-Guided Look-Ahead in AND/OR Search for Graphical Models

Residual-Guided Look-Ahead in AND/OR Search for Graphical Models / グラフィカルモデルのAND/OR探索における残差誘導型先読み

We introduce the concept of local bucket error for the mini-bucket heuristics and show how it can be used to improve the power of AND/OR search for combinatorial optimization tasks in graphical models (e.g. MAP/MPE or weighted CSPs). The local bucket error illuminates how the heuristic errors are distributed in the search space, guided by the mini-bucket heuristic. We present and analyze methods for compiling the local bucket-errors (exactly and approximately) and show that they can be used to yield an effective tool for balancing look-ahead overhead during search. This can be especially instrumental when memory is restricted, accommodating the generation of only weak compiled heuristics. We illustrate the impact of the proposed schemes in an extensive empirical evaluation for both finding exact solutions and anytime suboptimal solutions.



ミニバケットヒューリスティックにおけるローカルバケットエラーの概念を導入し、グラフィカルモデル（MAP/MPEや重み付きCSPなど）における組合せ最適化タスクにおけるAND/OR探索の性能向上に、この概念がどのように役立つかを示します。ローカルバケットエラーは、ミニバケットヒューリスティックによって導かれる探索空間におけるヒューリスティックエラーの分布を明らかにします。ローカルバケットエラーを（正確に、また近似的に）コンパイルする手法を提示・分析し、探索中の先読みオーバーヘッドのバランスをとるための効果的なツールとして利用できることを示します。これは、メモリが限られており、弱いコンパイル済みヒューリスティックのみを生成する必要がある場合に特に有効です。提案手法の影響は、厳密解と常時準最適解の両方を求める場合の広範な実証的評価によって示します。

Preference-Based Inconsistency Management in Multi-Context Systems

Preference-Based Inconsistency Management in Multi-Context Systems / マルチコンテキストシステムにおける選好に基づく不整合管理

Multi-Context Systems (MCS) are a powerful framework for interlinking possibly heterogeneous, autonomous knowledge bases, where information can be exchanged among knowledge bases by designated bridge rules with negation as failure. An acknowledged issue with MCS is inconsistency that arises due to the information exchange. To remedy this problem, inconsistency removal has been proposed in terms of repairs, which modify bridge rules based on suitable notions for diagnosis of inconsistency. In general, multiple diagnoses and repairs do exist; this leaves the user, who arguably may oversee the inconsistency removal, with the task of selecting some repair among all possible ones. To aid in this regard, we extend the MCS framework with preference information for diagnoses, such that undesired diagnoses are filtered out and diagnoses that are most preferred according to a preference ordering are selected. We consider preference information at a generic level and develop meta-reasoning techniques on diagnoses in MCS that can be exploited to reduce preference-based selection of diagnoses to computing ordinary subset-minimal diagnoses in an extended MCS. We describe two meta-reasoning encodings for preference orders: the first is conceptually simple but may incur an exponential blowup. The second is increasing only linearly in size and based on duplicating the original MCS. The latter requires nondeterministic guessing if a subset-minimal among all most preferred diagnoses should be computed. However, a complexity analysis of diagnoses shows that this is worst-case optimal, and that in general, preferred diagnoses have the same complexity as subset-minimal ordinary diagnoses. Furthermore, (subset-minimal) filtered diagnoses and (subset-minimal) ordinary diagnoses also have the same complexity.



マルチコンテキストシステム（MCS）は、異種混在の可能性がある自律的な知識ベースを相互接続するための強力なフレームワークであり、指定されたブリッジルール（否定を失敗とする）によって知識ベース間で情報を交換できます。MCSにおける既知の問題の一つは、情報交換によって生じる不整合です。この問題を解決するため、不整合の除去は修復という観点から提案されています。修復とは、不整合の診断に適した概念に基づいてブリッジルールを修正するものです。一般的に、複数の診断と修復が存在するため、不整合の除去を監督する可能性のあるユーザーは、すべての可能な修復の中から適切な修復を選択するという作業を強いられます。この点を支援するため、本研究ではMCSフレームワークを診断の選好情報で拡張し、不要な診断を除外し、選好順序に従って最も好ましい診断を選択するようにします。本研究では、選好情報を汎用レベルで考察し、MCSにおける診断に関するメタ推論手法を開発します。この手法を利用することで、選好に基づく診断選択を、拡張されたMCSにおける通常の部分集合最小診断の計算にまで簡略化できます。選好順序に関する2つのメタ推論エンコーディングについて説明します。1つ目は概念的には単純ですが、指数関数的な爆発を引き起こす可能性があります。2つ目は、サイズが線形的にのみ増加し、元のMCSを複製する手法です。後者は、最も好ましい診断の中で部分集合最小値を計算する場合、非決定論的な推測を必要とします。しかし、診断の複雑性分析により、これは最悪のケースにおける最適解であり、一般的に、好ましい診断は部分集合最小値の通常の診断と同じ複雑性を持つことが示されています。さらに、（部分集合最小値）フィルタリングされた診断と（部分集合最小値）通常の診断も同じ複雑性を持ちます。

The Sixth Answer Set Programming Competition

The Sixth Answer Set Programming Competition / 第6回解答集合プログラミングコンテスト

Answer Set Programming (ASP) is a well-known paradigm of declarative programming with roots in logic programming and non-monotonic reasoning. Similar to other closely related problem-solving technologies, such as SAT/SMT, QBF, Planning and Scheduling, advancements in ASP solving are assessed in competition events. In this paper, we report about the design and results of the Sixth ASP Competition, which was jointly organized by the University of Calabria (Italy), Aalto University (Finland), and the University of Genoa (Italy), in affiliation with the 13th International Conference on Logic Programming and Non-Monotonic Reasoning. This edition maintained some of the design decisions introduced in 2014, e.g., the conception of sub-tracks, the scoring scheme, and the adherence to a fixed modeling language in order to push the adoption of the ASP-Core-2 standard. On the other hand, it featured also some novelties, like a benchmark selection stage classifying instances according to their empirical hardness, and a “Marathon” track where the top-performing systems are given more time for solving hard benchmarks.



回答セットプログラミング（ASP）は、論理プログラミングと非単調推論にルーツを持つ、宣言型プログラミングのよく知られたパラダイムです。SA​​T / SMT、QBF、プランニングとスケジューリングなどの他の密接に関連する問題解決テクノロジと同様に、ASP解決の進歩は競技イベントで評価されます。この論文では、第6回ASPコンペティションの設計と結果について報告します。このコンペティションは、第13回国際論理プログラミングおよび非単調推論会議と提携して、カラブリア大学（イタリア）、アアルト大学（フィンランド）、ジェノヴァ大学（イタリア）が共同で開催しました。この版では、サブトラックの概念、スコアリングスキーム、ASP-Core-2標準の採用を促進するための固定モデリング言語の順守など、2014年に導入された設計上の決定の一部が維持されました。一方で、インスタンスを経験的困難度に応じて分類するベンチマーク選択ステージや、トップクラスのシステムに難しいベンチマークを解くための時間をより多く与える「マラソン」トラックなど、いくつかの斬新な機能も備えていました。

Resolving Over-Constrained Temporal Problems with Uncertainty through Conflict-Directed Relaxation

Resolving Over-Constrained Temporal Problems with Uncertainty through Conflict-Directed Relaxation / 不確実性を伴う過剰制約時間問題の衝突指向緩和法による解決

Over-subscription, that is, being assigned too many things to do, is commonly encountered in temporal scheduling problems. As human beings, we often want to do more than we can actually do, and underestimate how long it takes to perform each task. Decision makers can benefit from aids that identify when these failure situations are likely, the root causes of these failures, and resolutions to these failures.In this paper, we present a decision assistant that helps users resolve over-subscribed temporal problems. The system works like an experienced advisor that can quickly identify the cause of failure underlying temporal problems and compute resolutions. The core of the decision assistant is the Best-first Conflict-Directed Relaxation (BCDR) algorithm, which can detect conflicting sets of constraints within temporal problems, and computes continuous relaxations for them that weaken constraints to the minimum extent, instead of removing them completely. BCDR is an extension to the Conflict-Directed A* algorithm, first developed in the model-based reasoning community to compute most likely system diagnoses or reconfigurations. It generalizes the discrete conflicts and relaxations, to hybrid conflicts and relaxations, which denote minimal inconsistencies and minimal relaxations to both discrete and continuous relaxable constraints. In addition, BCDR is capable of handling temporal uncertainty, expressed as either set-bounded or probabilistic durations, and can compute preferred trade-offs between the risk of violating a schedule requirement, versus the loss of utility by weakening those requirements.BCDR has been applied to several decision support applications in different domains, including deep-sea exploration, urban travel planning and transit system management. It has demonstrated its effectiveness in helping users resolve over-subscribed scheduling problems and evaluate the robustness of existing solutions. In our benchmark experiments, BCDR has also demonstrated its efficiency on solving large-scale scheduling problems in the aforementioned domains. Thanks to its conflict-driven approach for computing relaxations, BCDR achieves one to two orders of magnitude improvements on runtime performance when compared to state-of-the-art numerical solvers.



オーバーサブスクリプション、つまりタスクが多すぎる状態は、時間的スケジューリング問題でよく発生します。人間は、実際にできる以上のことをしたいと思い、各タスクの実行時間を過小評価してしまうことがよくあります。意思決定者は、このような失敗状況が発生する可能性、失敗の根本原因、そして失敗の解決策を特定する支援ツールの恩恵を受けることができます。本稿では、オーバーサブスクリプションの問題解決を支援する意思決定アシスタントを紹介します。このシステムは、経験豊富なアドバイザーのように機能し、時間的問題の根底にある失敗の原因を迅速に特定し、解決策を計算します。意思決定支援システムの中核を成すのは、最良優先の衝突指向緩和（BCDR）アルゴリズムです。このアルゴリズムは、時間的問題における矛盾する制約セットを検出し、制約を完全に削除するのではなく、制約を最小限に緩和する連続緩和を計算します。BCDRは、モデルベース推論コミュニティで最初に開発された衝突指向A*アルゴリズムの拡張版であり、最も可能性の高いシステム診断または再構成を計算するために開発されました。BCDRは、離散的な衝突と緩和をハイブリッドな衝突と緩和へと一般化します。ハイブリッドな衝突と緩和は、離散的および連続的な緩和可能な制約の両方に対して、最小限の不整合と最小限の緩和を示します。さらに、BCDRは、セット制限または確率的期間として表現される時間的不確実性を処理することができ、スケジュール要件に違反するリスクと、それらの要件を緩和することによる効用損失との間の好ましいトレードオフを計算することができます。BCDRは、深海探査、都市旅行計画、交通システム管理など、さまざまな分野のいくつかの意思決定支援アプリケーションに適用されています。ユーザーがオーバーサブスクリプションのスケジューリング問題を解決し、既存のソリューションの堅牢性を評価する上で、その有効性が実証されています。私たちのベンチマーク実験では、BCDRは前述の分野における大規模なスケジューリング問題を解決する際の効率性も実証されています。緩和を計算するための競合駆動型アプローチにより、BCDRは最先端の数値ソルバーと比較して、実行時パフォーマンスが1～2桁向上します。

On Hash-Based Work Distribution Methods for Parallel Best-First Search

On Hash-Based Work Distribution Methods for Parallel Best-First Search / 並列最良優先探索のためのハッシュベースの作業配分法について

Parallel best-first search algorithms such as Hash Distributed A* (HDA*) distribute work among the processes using a global hash function. We analyze the search and communication overheads of state-of-the-art hash-based parallel best-first search algorithms, and show that although Zobrist hashing, the standard hash function used by HDA*, achieves good load balance for many domains, it incurs significant communication overhead since almost all generated nodes are transferred to a different processor than their parents. We propose Abstract Zobrist hashing, a new work distribution method for parallel search which, instead of computing a hash value based on the raw features of a state, uses a feature projection function to generate a set of abstract features which results in a higher locality, resulting in reduced communications overhead. We show that Abstract Zobrist hashing outperforms previous methods on search domains using hand-coded, domain specific feature projection functions. We then propose GRAZHDA*, a graph-partitioning based approach to automatically generating feature projection functions. GRAZHDA* seeks to approximate the partitioning of the actual search space graph by partitioning the domain transition graph, an abstraction of the state space graph. We show that GRAZHDA* outperforms previous methods on domain-independent planning.



Hash Distributed A* (HDA*)などの並列最良優先探索アルゴリズムは、グローバルハッシュ関数を使用してプロセス間で作業を分散します。最先端のハッシュベースの並列最良優先探索アルゴリズムの探索および通信オーバーヘッドを分析し、HDA*で使用される標準ハッシュ関数であるゾブリストハッシュは多くのドメインで良好な負荷分散を実現するものの、生成されるノードのほぼすべてが親ノードとは異なるプロセッサに転送されるため、大きな通信オーバーヘッドが発生することを示します。本稿では、並列探索のための新しい作業分散手法である抽象ゾブリストハッシュを提案します。これは、状態の生の特徴に基づいてハッシュ値を計算する代わりに、特徴射影関数を用いて抽象特徴セットを生成することで局所性を高め、通信オーバーヘッドを削減します。抽象ゾブリストハッシュは、手作業でコーディングされたドメイン固有の特徴射影関数を用いた探索ドメインにおいて、従来の手法よりも優れた性能を発揮することを示します。さらに、特徴射影関数を自動生成するグラフ分割に基づく手法であるGRAZHDA*を提案します。GRAZHDA*は、状態空間グラフの抽象化であるドメイン遷移グラフを分割することにより、実際の探索空間グラフの分割を近似しようとします。GRAZHDA*はドメイン非依存の計画において従来の方法よりも優れていることを示します。

A Survey on Lexical Simplification

A Survey on Lexical Simplification / 語彙簡素化に関するサーベイ

Lexical Simplification is the process of replacing complex words in a given sentence with simpler alternatives of equivalent meaning. This task has wide applicability both as an assistive technology for readers with cognitive impairments or disabilities, such as Dyslexia and Aphasia, and as a pre-processing tool for other Natural Language Processing tasks, such as machine translation and summarisation. The problem is commonly framed as a pipeline of four steps: the identification of complex words, the generation of substitution candidates, the selection of those candidates that fit the context, and the ranking of the selected substitutes according to their simplicity. In this survey we review the literature for each step in this typical Lexical Simplification pipeline and provide a benchmarking of existing approaches for these steps on publicly available datasets. We also provide pointers for datasets and resources available for the task.



語彙簡素化とは、与えられた文中の複雑な語を、意味が等価なより単純な語に置き換えるプロセスです。このタスクは、失読症や失語症などの認知障害や障がいのある読者を支援する技術として、また機械翻訳や要約などの他の自然言語処理タスクの前処理ツールとして、幅広く応用できます。この問題は一般的に、複雑な語の識別、置換候補の生成、文脈に適合する候補の選択、そして選択された置換語の単純さによる順位付けという4つのステップからなるパイプラインとして捉えられます。本調査では、この典型的な語彙簡素化パイプラインの各ステップに関する文献をレビューし、公開されているデータセットにおけるこれらのステップに対する既存のアプローチのベンチマークを提供します。また、このタスクに利用可能なデータセットとリソースへのポインタも提供します。

Time and Space Bounds for Planning

Time and Space Bounds for Planning / 計画における時間と空間の境界

There is an extensive literature on the complexity of planning, but explicit bounds on time and space complexity are very rare. On the other hand, problems like the constraint satisfaction problem (CSP) have been thoroughly analysed in this respect. We provide a number of upper- and lower-bound results (the latter based on various complexity-theoretic assumptions such as the Exponential Time Hypothesis) for both satisficing and optimal planning. We show that many classes of planning instances exhibit a dichotomy: either they can be solved in polynomial time or they cannot be solved in subexponential time. In many cases, we can even prove closely matching upper and lower bounds. Our results also indicate, analogously to CSPs, the existence of sharp phase transitions. We finally study and discuss the trade-off between time and space. In particular, we show that depth-first search may sometimes be a viable option for planning under severe space constraints.



計画の複雑さに関する文献は豊富にありますが、時間と空間の複雑さの明確な境界は非常にまれです。一方、制約充足問題(CSP)などの問題は、この点で徹底的に分析されてきました。我々は、満足化計画と最適計画の両方について、上限および下限に関する多数の結果（後者は指数時間仮説などの様々な複雑性理論的仮定に基づく）を提供します。多くの計画インスタンスのクラスが二分法を示すことを示す。すなわち、多項式時間で解けるか、指数時間未満で解けないかのどちらかです。多くの場合、密接に一致する上限と下限を証明することさえできます。我々の結果はまた、CSPと同様に、鋭い相転移の存在を示しています。最後に、時間と空間のトレードオフを調査し、議論します。特に、厳しい空間制約下での計画において、深さ優先探索が実行可能な選択肢となり得ることを示す。

Multi-Organ Exchange

Multi-Organ Exchange / 多臓器交換

Kidney exchange, where candidates with organ failure trade incompatible but willing donors, is a life-saving alternative to the deceased donor waitlist, which has inadequate supply to meet demand. While fielded kidney exchanges see huge benefit from altruistic kidney donors (who give an organ without a paired needy candidate), a significantly higher medical risk to the donor deters similar altruism with livers. In this paper, we begin by exploring the idea of large-scale liver exchange, and show on demographically accurate data that vetted kidney exchange algorithms can be adapted to clear such an exchange at the nationwide level. We then propose cross-organ donation where kidneys and livers can be bartered for each other. We show theoretically that this multi-organ exchange provides linearly more transplants than running separate kidney and liver exchanges. This linear gain is a product of altruistic kidney donors creating chains that thread through the liver pool; it exists even when only a small but constant portion of the donors on the kidney side of the pool are willing to donate a liver lobe. We support this result experimentally on demographically accurate multi-organ exchanges. We conclude with thoughts regarding the fielding of a nationwide liver or joint liver-kidney exchange from a legal and computational point of view.



臓器不全の候補者が不適合だがドナーとなる意思のあるドナーを交換する腎臓交換は、需要を満たす供給が不十分な死体ドナー待機リストに代わる、救命手段となります。現場で実施される腎臓交換は、利他的な腎臓ドナー（対応する支援を必要とする候補者がいなくても臓器を提供する）から大きな利益を得る一方で、ドナーの医療リスクが著しく高いことが、肝臓における同様の利他行為を抑止する要因となっています。本稿では、まず大規模な肝臓交換というアイデアを検討し、人口統計学的に正確なデータに基づいて、精査された腎臓交換アルゴリズムを適応させれば、全国レベルでそのような交換を承認できることを示す。次に、腎臓と肝臓を互いに交換できる臓器間提供を提案します。この多臓器交換により、腎臓と肝臓を別々に交換するよりも移植件数が直線的に増加することが理論的に示されます。この直線的増加は、利他的な腎臓ドナーが肝臓プール全体に広がるチェーンを作り出すことで得られるものであり、腎臓側のドナーのうち、肝臓葉を提供する意思のある人がごくわずかだが一定数しかいない場合でも、直線的増加は存在します。私たちは、人口統計学的に正確な多臓器交換において、この結果を実験的に裏付けています。最後に、法的および計算的観点から、全国的な肝臓または肝臓・腎臓の共同交換の実施に関する考察を述べます。

Viewpoint: A Critical View on Smart Cities and AI

Viewpoint: A Critical View on Smart Cities and AI / 視点：スマートシティとAIに関する批判的考察

AI developments on smart cities, if not critical, risk making a flawed urban model more efficient. Instead, we suggest that AI should challenge the mainstream techno-optimistic approach to solving urban problems by dialoguing with other academic fields, questioning the dominant urban paradigm, and creating transformative solutions. We claim that doing differently, rather than doing better, may be smarter for cities and the common good.This article is part of the special track on AI and Society.



スマートシティにおけるAIの発展は、決定的ではないにせよ、欠陥のある都市モデルをより効率的にしてしまうリスクがあります。我々はむしろ、AIは他の学問分野と対話し、支配的な都市パラダイムに疑問を投げかけ、変革的な解決策を生み出すことで、都市問題の解決における主流の技術楽観主義的アプローチに挑戦すべきだと提案します。より良いことを行うよりも、異なることを行う方が、都市と公共の利益にとってより賢明である可能性があると我々は主張します。本稿はAIと社会に関する特別トラックの一部です。

Chamberlin–Courant Rule with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time

Chamberlin–Courant Rule with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time / 承認付きチェンバリン・クーラン則投票：有限頻度のMaxCover問題をFPT時間で近似する

We consider the problem of winner determination under Chamberlin–Courant’s multiwinner voting rule with approval utilities. This problem is equivalent to the well-known NP-complete MaxCover problem and, so, the best polynomial-time approximation algorithm for it has approximation ratio 1 – 1/e. We show exponential-time/FPT approximation algorithms that, on one hand, achieve arbitrarily good approximation ratios and, on the other hand, have running times much better than known exact algorithms. We focus on the cases where the voters have to approve of at most/at least a given number of candidates.



我々は、承認効用を伴うChamberlin-Courantの複数勝者投票規則における勝者決定の問題を検討します。この問題は、よく知られたNP完全MaxCover問題と同等であり、したがって、この問題に対する最良の多項式時間近似アルゴリズムは近似比1 – 1/eを持つ。我々は、一方では任意に良好な近似比を達成し、他方では既知の厳密なアルゴリズムよりもはるかに短い実行時間を持つ指数時間/FPT近似アルゴリズムを示す。我々は、投票者が最大/少なくとも一定数の候補者を承認しなければならないケースに焦点を当てます。

Sample-Based Tree Search with Fixed and Adaptive State Abstractions

Sample-Based Tree Search with Fixed and Adaptive State Abstractions / 固定および適応的状態抽象化を用いたサンプルベース木探索

Sample-based tree search (SBTS) is an approach to solving Markov decision problems based on constructing a lookahead search tree using random samples from a generative model of the MDP. It encompasses Monte Carlo tree search (MCTS) algorithms like UCT as well as algorithms such as sparse sampling. SBTS is well-suited to solving MDPs with large state spaces due to the relative insensitivity of SBTS algorithms to the size of the state space. The limiting factor in the performance of SBTS tends to be the exponential dependence of sample complexity on the depth of the search tree. The number of samples required to build a search tree is O((|A|B)^d), where |A| is the number of available actions, B is the number of possible random outcomes of taking an action, and d is the depth of the tree. State abstraction can be used to reduce B by aggregating random outcomes together into abstract states. Recent work has shown that abstract tree search often performs substantially better than tree search conducted in the ground state space.This paper presents a theoretical and empirical evaluation of tree search with both fixed and adaptive state abstractions. We derive a bound on regret due to state abstraction in tree search that decomposes abstraction error into three components arising from properties of the abstraction and the search algorithm. We describe versions of popular SBTS algorithms that use fixed state abstractions, and we introduce the Progressive Abstraction Refinement in Sparse Sampling (PARSS) algorithm, which adapts its abstraction during search. We evaluate PARSS as well as sparse sampling with fixed abstractions on 12 experimental problems, and find that PARSS outperforms search with a fixed abstraction and that search with even highly inaccurate fixed abstractions outperforms search without abstraction. These results establish progressive abstraction refinement as a promising basis for new tree search algorithms, and we propose directions for future work within the progressive refinement framework.



サンプルベース木探索（SBTS）は、MDPの生成モデルからランダムサンプルを用いて先読み探索木を構築することに基づく、マルコフ決定問題の解法です。これは、UCTのようなモンテカルロ木探索（MCTS）アルゴリズムやスパースサンプリングなどのアルゴリズムを包含します。SBTSは状態空間のサイズに比較的鈍感であるため、大きな状態空間を持つMDPの解法に適しています。SBTSの性能を制限する要因は、サンプルの複雑さが探索木の深さに指数関数的に依存する傾向があることです。探索木を構築するために必要なサンプル数はO((|A|B)^d)です。ここで、|A|は利用可能なアクションの数、Bはアクションを実行した場合に起こり得るランダムな結果の数、dは木の深さです。状態抽象化は、ランダムな結果を抽象状態に集約することでBを削減するために使用できます。最近の研究では、抽象ツリー探索は基底状態空間で実行されるツリー探索よりも大幅に優れたパフォーマンスを発揮することが多いことが示されています。この論文では、固定および適応型の状態抽象化の両方を使用したツリー探索の理論的かつ実証的な評価を示します。ツリー探索における状態抽象化による後悔の境界を導出し、抽象化エラーを抽象化と探索アルゴリズムの特性から生じる3つの要素に分解します。固定状態抽象化を使用する一般的なSBTSアルゴリズムのバージョンについて説明し、探索中に抽象化を適応させるProgressive Abstraction Refinement in Sparse Sampling (PARSS)アルゴリズムを紹介します。12の実験問題でPARSSと固定抽象化を使用したスパース サンプリングを評価し、PARSSは固定抽象化を使用した探索よりも性能が高く、非常に不正確な固定抽象化を使用した探索でも抽象化を使用しない探索よりも性能が高いことがわかりました。これらの結果により、漸進的抽象化改良は新しいツリー検索アルゴリズムの有望な基盤として確立され、漸進的抽象化改良フレームワーク内での今後の作業の方向性が提案されます。

On the Equivalence between Assumption-Based Argumentation and Logic Programming

On the Equivalence between Assumption-Based Argumentation and Logic Programming / 仮定に基づく議論と論理プログラミングの同値性について

Assumption-Based Argumentation (ABA) has been shown to subsume various other non-monotonic reasoning formalisms, among them normal logic programming (LP). We re-examine the relationship between ABA and LP and show that normal LP also subsumes (flat) ABA. More precisely, we specify a procedure that given a (flat) ABA framework yields an associated logic program with almost the same syntax whose semantics coincide with those of the ABA framework. That is, the 3-valued stable (respectively well-founded, regular, 2-valued stable, and ideal) models of the associated logic program coincide with the complete (respectively grounded, preferred, stable, and ideal) assumption labellings and extensions of the ABA framework. Moreover, we show how our results on the translation from ABA to LP can be reapplied for a reverse translation from LP to ABA, and observe that some of the existing results in the literature are in fact special cases of our work. Overall, we show that (flat) ABA frameworks can be seen as normal logic programs with a slightly different syntax. This implies that methods developed for one of these formalisms can be equivalently applied to the other by simply modifying the syntax.



仮定に基づく議論（ABA）は、他の様々な非単調推論形式論、特に正規論理プログラミング（LP）を包含することが示されています。我々はABAとLPの関係を再検証し、正規LPも（平坦な）ABAを包含することを示す。より正確には、（平坦な）ABAフレームワークが与えられた場合に、ABAフレームワークと意味論が一致する、ほぼ同じ構文を持つ関連論理プログラムを生成する手順を規定します。すなわち、関連論理プログラムの3値安定モデル（それぞれ、well-founded、regular、2値安定、ideal）は、ABAフレームワークの完全な仮定ラベル付けおよび拡張（それぞれ、grounded、preferred、stable、ideal）と一致します。さらに、ABAからLPへの変換に関する我々の結果を、LPからABAへの逆変換にどのように再適用できるかを示し、文献における既存の結果のいくつかが実際には我々の研究の特殊ケースであることを指摘します。全体として、（フラット）ABAフレームワークは、わずかに異なる構文を持つ通常の論理プログラムと見なせることを示す。これは、これらの形式主義の一方のために開発された手法が、構文を変更するだけで他方にも等価に適用できることを意味します。

Prime Implicate Generation in Equational Logic

Prime Implicate Generation in Equational Logic / 方程式論理における主含意生成

We present an algorithm for the generation of prime implicates in equational logic, that is, of the most general consequences of formulæ containing equations and disequations between first-order terms. This algorithm is defined by a calculus that is proved to be correct and complete. We then focus on the case where the considered clause set is ground, i.e., contains no variables, and devise a specialized tree data structure that is designed to efficiently detect and delete redundant implicates. The corresponding algorithms are presented along with their termination and correctness proofs. Finally, an experimental evaluation of this prime implicate generation method is conducted in the ground case, including a comparison with state-of-the-art propositional and first-order prime implicate generation tools.



等式論理におけるプライム含意、すなわち一階項間の等式および非等式を含む論理式の最も一般的な帰結を生成するアルゴリズムを提示します。このアルゴリズムは、正しく完全であることが証明された計算によって定義されます。次に、対象となる節集合が基底、すなわち変数を含まない場合に焦点を当て、冗長な含意を効率的に検出・削除するように設計された特殊な木データ構造を考案します。対応するアルゴリズムは、その停止性と正しさの証明とともに提示されます。最後に、このプライム含意生成法の基底ケースにおける実験的評価を行い、最先端の命題論理および一階項プライム含意生成ツールとの比較を行う。

On Monte Carlo Tree Search and Reinforcement Learning

On Monte Carlo Tree Search and Reinforcement Learning / モンテカルロ木探索と強化学習について

Fuelled by successes in Computer Go, Monte Carlo tree search (MCTS) has achieved widespread adoption within the games community. Its links to traditional reinforcement learning (RL) methods have been outlined in the past; however, the use of RL techniques within tree search has not been thoroughly studied yet. In this paper we re-examine in depth this close relation between the two fields; our goal is to improve the cross-awareness between the two communities. We show that a straightforward adaptation of RL semantics within tree search can lead to a wealth of new algorithms, for which the traditional MCTS is only one of the variants. We confirm that planning methods inspired by RL in conjunction with online search demonstrate encouraging results on several classic board games and in arcade video game competitions, where our algorithm recently ranked first. Our study promotes a unified view of learning, planning, and search.



コンピュータ囲碁での成功に後押しされ、モンテカルロ木探索（MCTS）はゲームコミュニティで広く採用されるようになりました。従来の強化学習（RL）手法との関連はこれまでにも概説されてきましたが、木探索内でのRL手法の使用はまだ十分に研究されていません。本稿では、この2つの分野の密接な関係を深く再検証し、2つのコミュニティ間の相互認識を向上させることを目標としています。木探索内でRLセマンティクスを単純に適応させることで、豊富な新しいアルゴリズムを生み出すことができ、従来のMCTSはそのバリエーションの1つに過ぎないことを示します。RLに着想を得た計画手法とオンライン探索を組み合わせることで、いくつかの古典的なボードゲームやアーケードビデオゲームの大会で有望な結果を示し、最近、私たちのアルゴリズムが1位になったことを確認しました。私たちの研究は、学習、計画、および探索の統一的な見方を推進しています。

Elections with Few Voters: Candidate Control Can Be Easy

Elections with Few Voters: Candidate Control Can Be Easy / 投票者が少ない選挙：候補者管理は容易になる

We study the computational complexity of candidate control in elections with few voters, that is, we consider the parameterized complexity of candidate control in elections with respect to the number of voters as a parameter. We consider both the standard scenario of adding and deleting candidates, where one asks whether a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding or deleting few candidates, as well as a combinatorial scenario where adding/deleting a candidate automatically means adding or deleting a whole group of candidates. Considering several fundamental voting rules, our results show that the parameterized complexity of candidate control, with the number of voters as the parameter, is much more varied than in the setting with many voters.



我々は、少数の投票者による選挙における候補者制御の計算複雑性を研究します。すなわち、投票者数をパラメータとして、選挙における候補者制御のパラメータ化された複雑性を検討します。少数の候補者を追加または削除することで、特定の候補者が勝者になることができるか（または、破壊的なケースでは、勝てなくなる可能性があるか）を問う、候補者の追加と削除という標準的なシナリオと、候補者の追加/削除が自動的に候補者グループ全体の追加または削除を意味する組み合わせシナリオの両方を検討します。いくつかの基本的な投票ルールを考慮した結果、投票者数をパラメータとする候補者制御のパラメータ化された複雑性は、多数の投票者の場合よりもはるかに多様であることがわかった。

Kernel Contraction and Base Dependence

Kernel Contraction and Base Dependence / カーネル収縮と基底依存性

The AGM paradigm of belief change studies the dynamics of belief states in light of new information. Finding, or even approximating, those beliefs that are dependent on or relevant to a change is valuable because, for example, it can narrow the set of beliefs considered during belief change operations. A strong intuition in this area is captured by Gärdenforss preservation criterion (GPC), which suggests that formulas independent of a belief change should remain intact. GPC thus allows one to build dependence relations that are linked with belief change. Such dependence relations can in turn be used as a theoretical benchmark against which to evaluate other approximate dependence or relevance relations. Fariñas and Herzig axiomatize a dependence relation with respect to a belief set, and, based on GPC, they characterize the correspondence between AGM contraction functions and dependence relations. In this paper, we introduce base dependence as a relation between formulas with respect to a belief base, and prove a more general characterization that shows the correspondence between kernel contraction and base dependence. At this level of generalization, different types of base dependence emerge, which we show to be a result of possible redundancy in the belief base. We further show that one of these relations that emerge, strong base dependence, is parallel to saturated kernel contraction. We then prove that our latter characterization is a reversible generalization of Fariñas and Herzigs characterization. That is, in the special case when the underlying belief base is deductively closed (i.e., it is a belief set), strong base dependence reduces to dependence, and so do their respective characterizations. Finally, an intriguing feature of Fariñas and Herzigs formalism is that it meets other criteria for dependence, namely, Keyness conjunction criterion for dependence (CCD) and Gärdenforss conjunction criterion for independence (CCI). We prove that our base dependence formalism also meets these criteria. Even more interestingly, we offer a more specific criterion that implies both CCD and CCI, and show our base dependence formalism also meets this new criterion.



信念変化のAGMパラダイムは、新しい情報に照らして信念状態のダイナミクスを研究します。変化に依存または関連する信念を発見すること、あるいは近似することは、例えば、信念変化操作中に考慮される信念のセットを絞り込むことができるため、有益です。この分野における強い直感は、ガーデンフォース保存基準（GPC）によって捉えられています。GPCは、信念の変化に依存しない式はそのまま維持されるべきであると示唆しています。したがって、GPCは、信念の変化と結びついた依存関係を構築することを可能にします。このような依存関係は、他の近似的な依存関係や関連性関係を評価するための理論的なベンチマークとして使用できます。ファリニャスとヘルツィグは、信念集合に関する依存関係を公理化し、GPCに基づいてAGM縮約関数と依存関係の対応関係を特徴付けています。本論文では、信念基底に関する式間の関係として基底依存性を導入し、カーネル縮約と基底依存性の対応関係を示すより一般的な特徴付けを証明します。この一般化レベルでは、異なるタイプの基底依存性が出現しますが、これは信念基底における冗長性の可能性の結果であることを示します。さらに、出現する関係の1つである強い基底依存性は、飽和カーネル縮約と並行していることを示します。次に、後者の特徴付けが、FariñasとHerzigsの特徴付けの可逆的な一般化であることを証明します。つまり、基礎となる信念基底が演繹的に閉じている（つまり、信念集合である）特別な場合、強い基底依存性は依存性に縮減され、それぞれの特徴付けも同様に縮減されます。最後に、FariñasとHerzigsの形式の興味深い特徴は、依存性の他の基準、すなわち依存性に関するKeyness連言基準（CCD）と独立性に関するGärdenforss連言基準（CCI）を満たすことです。私たちの基底依存性形式主義もこれらの基準を満たすことを証明します。さらに興味深いことに、CCDとCCIの両方を意味するより具体的な基準を提示し、私たちの基底依存性形式主義がこの新しい基準も満たすことを示します。

参考文献

• Journal of Artificial Intelligence Resarch Vol. 60 (2017)

関連情報

• Journal of Artificial Intelligence Research: 論文一覧