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

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

論文

Coactive Learning

Coactive Learning / 協働学習

We propose Coactive Learning as a model of interaction between a learning system and a human user, where both have the common goal of providing results of maximum utility to the user. Interactions in the Coactive Learning model take the following form: at each step, the system (e.g. search engine) receives a context (e.g. query) and predicts an object (e.g. ranking); the user responds by correcting the system if necessary, providing a slightly improved but not necessarily optimal object as feedback. We argue that such preference feedback can be inferred in large quantity from observable user behavior (e.g., clicks in web search), unlike the optimal feedback required in the expert model or the cardinal valuations required for bandit learning. Despite the relaxed requirements for the feedback, we show that it is possible to adapt many existing online learning algorithms to the coactive framework. In particular, we provide algorithms that achieve square root regret in terms of cardinal utility, even though the learning algorithm never observes cardinal utility values directly. We also provide an algorithm with logarithmic regret in the case of strongly convex loss functions. An extensive empirical study demonstrates the applicability of our model and algorithms on a movie recommendation task, as well as ranking for web search.



我々は、学習システムと人間のユーザーとの間のインタラクションモデルとして、Coactive Learningを提案します。両者は、ユーザーにとって最大の効用をもたらす結果を提供するという共通の目標を持つ。Coactive Learningモデルにおけるインタラクションは、以下の形式をとる。各ステップにおいて、システム（例えば検索エンジン）はコンテキスト（例えばクエリ）を受け取り、オブジェクト（例えばランキング）を予測します。ユーザーは必要に応じてシステムを修正することで応答し、フィードバックとして、わずかに改善されたが必ずしも最適ではないオブジェクトを提供します。我々は、このような選好フィードバックは、エキスパートモデルで求められる最適フィードバックやバンディット学習で求められる基数評​​価とは異なり、観測可能なユーザー行動（例えばウェブ検索におけるクリック）から大量に推論できると主張します。フィードバックに対する要件は緩和されているものの、多くの既存のオンライン学習アルゴリズムをCoactive Frameworkに適用できることを示す。特に、学習アルゴリズムが基数効用値を直接観測することはないにもかかわらず、基数効用に関して平方根後悔を実現するアルゴリズムを提供します。また、強く凸な損失関数の場合に対数後悔を実現するアルゴリズムも提供します。広範な実証研究により、本モデルとアルゴリズムは、映画推薦タスクおよびウェブ検索のランキングに適用可能であることが実証されています。

Clause Elimination for SAT and QSAT

Clause Elimination for SAT and QSAT / SATおよびQSATにおける節除去

The famous archetypical NP-complete problem of Boolean satisfiability (SAT) and its PSPACE-complete generalization of quantified Boolean satisfiability (QSAT) have become central declarative programming paradigms through which real-world instances of various computationally hard problems can be efficiently solved. This success has been achieved through several breakthroughs in practical implementations of decision procedures for SAT and QSAT, that is, in SAT and QSAT solvers. Here, simplification techniques for conjunctive normal form (CNF) for SAT and for prenex conjunctive normal form (PCNF) for QSAT—the standard input formats of SAT and QSAT solvers—have recently proven very effective in increasing solver efficiency when applied before (i.e., in preprocessing) or during (i.e., in inprocessing) satisfiability search.In this article, we develop and analyze clause elimination procedures for pre- and inprocessing. Clause elimination procedures form a family of (P)CNF formula simplification techniques which remove clauses that have specific (in practice polynomial-time) redundancy properties while maintaining the satisfiability status of the formulas. Extending known procedures such as tautology, subsumption, and blocked clause elimination, we introduce novel elimination procedures based on asymmetric variants of these techniques, and also develop a novel family of so-called covered clause elimination procedures, as well as natural liftings of the CNF-level procedures to PCNF. We analyze the considered clause elimination procedures from various perspectives. Furthermore, for the variants not preserving logical equivalence under clause elimination, we show how to reconstruct solutions to original CNFs from satisfying assignments to simplified CNFs, which is important for practical applications for the procedures. Complementing the more theoretical analysis, we present results on an empirical evaluation on the practical importance of the clause elimination procedures in terms of the effect on solver runtimes on standard real-world application benchmarks. It turns out that the importance of applying the clause elimination procedures developed in this work is empirically emphasized in the context of state-of-the-art QSAT solving.



ブール充足可能性（SAT）という有名な典型的なNP完全問題と、そのPSPACE完全一般化である量化ブール充足可能性（QSAT）は、計算困難な様々な実世界の問題を効率的に解くための中心的な宣言型プログラミングパラダイムとなっています。この成功は、SATおよびQSATの決定手続きの実用的な実装、すなわちSATおよびQSATソルバーにおけるいくつかのブレークスルーによって達成されました。ここでは、SATおよびQSATソルバーの標準入力形式であるSATの連言正規形（CNF）およびQSATの冠頭連言正規形（PCNF）の簡略化手法が、充足可能性探索の前（すなわち前処理）または中（すなわちインプロセス）に適用された場合、ソルバーの効率向上に非常に効果的であることが最近証明されています。本稿では、前処理およびインプロセスにおける節除去手順を開発し、解析します。節除去手順は、式の充足可能性を維持しながら、特定の（実際には多項式時間）冗長特性を持つ節を除去する（P）CNF式簡略化手法のファミリーを形成します。トートロジー、包摂、ブロック節除去といった既知の手順を拡張し、これらの手法の非対称変種に基づく新たな除去手順を導入します。また、いわゆる被覆節除去手順の新たなファミリー、およびCNFレベル手順のPCNFへの自然なリフティングも開発します。検討対象の節除去手順を様々な観点から分析します。さらに、節除去において論理的同値性を維持できない変種については、簡略化されたCNFへの充足割り当てから元のCNFへの解を再構築する方法を示す。これは、これらの手順の実用化において重要です。より理論的な分析を補完するものとして、標準的な実世界アプリケーションベンチマークにおけるソルバー実行時間への影響という観点から、節除去手順の実用的重要性に関する実証的評価結果を示す。本研究で開発された節除去手順を適用することの重要性は、最先端のQSAT解法の文脈において実証的に強調されていることが明らかになった。

Using Machine Translation to Provide Target-Language Edit Hints in Computer Aided Translation Based on Translation Memories

Using Machine Translation to Provide Target-Language Edit Hints in Computer Aided Translation Based on Translation Memories / 翻訳メモリに基づくコンピュータ支援翻訳において、機械翻訳を用いてターゲット言語の編集ヒントを提供する

This paper explores the use of general-purpose machine translation (MT) in assisting the users of computer-aided translation (CAT) systems based on translation memory (TM) to identify the target words in the translation proposals that need to be changed (either replaced or removed) or kept unedited, a task we term as “word-keeping recommendation”. MT is used as a black box to align source and target sub-segments on the fly in the translation units (TUs) suggested to the user. Source-language (SL) and target-language (TL) segments in the matching TUs are segmented into overlapping sub-segments of variable length and machine-translated into the TL and the SL, respectively. The bilingual sub-segments obtained and the matching between the SL segment in the TU and the segment to be translated are employed to build the features that are then used by a binary classifier to determine the target words to be changed and those to be kept unedited. In this approach, MT results are never presented to the translator. Two approaches are presented in this work: one using a word-keeping recommendation system which can be trained on the TM used with the CAT system, and a more basic approach which does not require any training.Experiments are conducted by simulating the translation of texts in several language pairs with corpora belonging to different domains and using three different MT systems. We compare the performance obtained to that of previous works that have used statistical word alignment for word-keeping recommendation, and show that the MT-based approaches presented in this paper are more accurate in most scenarios. In particular, our results confirm that the MT-based approaches are better than the alignment-based approach when using models trained on out-of-domain TMs. Additional experiments were performed to check how dependent the MT-based recommender is on the language pair and MT system used for training. These experiments confirm a high degree of reusability of the recommendation models across various MT systems, but a low level of reusability across language pairs.



本稿では、翻訳メモリ（TM）に基づくコンピュータ支援翻訳（CAT）システムのユーザーを支援するために、汎用機械翻訳（MT）を活用する方法について考察します。このタスクは、翻訳提案において変更（置換または削除）が必要な訳語、あるいは編集せずに残す必要がある訳語を特定します。このタスクは「ワードキーピング推奨」と呼ぶ。MTは、ユーザーに提示される翻訳単位（TU）において、原文と訳文のサブセグメントをリアルタイムでアラインメントするためのブラックボックスとして用いられます。マッチングされたTU内の原文言語（SL）セグメントと訳文言語（TL）セグメントは、可変長の重複サブセグメントに分割され、それぞれ訳文言語（TL）と訳文言語（SL）に機械翻訳されます。得られたバイリンガルサブセグメントと、TU内の訳文言語セグメントと翻訳対象セグメントとのマッチングを用いて特徴量が構築され、バイナリ分類器によって、変更が必要な訳語と編集せずに残す訳語が判別されます。このアプローチでは、MTの結果が翻訳者に提示されることはない。本研究では、2つのアプローチを紹介します。1つはCATシステムで使用されるTMでトレーニングできる単語保持推奨システムを使用するもので、もう1つはトレーニングを必要としないより基本的なアプローチです。異なるドメインに属するコーパスと3つの異なるMTシステムを使用して、複数の言語ペアのテキストの翻訳をシミュレートすることにより、実験を実施しました。得られたパフォーマンスを、単語保持推奨に統計的単語アライメントを使用した以前の研究のパフォーマンスと比較し、本論文で提示したMTベースのアプローチがほとんどのシナリオでより正確であることを示します。特に、ドメイン外のTMでトレーニングされたモデルを使用する場合、MTベースのアプローチはアライメントベースのアプローチよりも優れていることが確認されました。MTベースの推奨システムが、トレーニングに使用した言語ペアとMTシステムにどの程度依存するかを確認するために、追加の実験を実施しました。これらの実験により、さまざまなMTシステム間での推奨モデルの再利用性は高いものの、言語ペア間での再利用性は低いことが確認されました。

Probabilistic Inference Techniques for Scalable Multiagent Decision Making

Probabilistic Inference Techniques for Scalable Multiagent Decision Making / スケーラブルなマルチエージェント意思決定のための確率推論技術

Decentralized POMDPs provide an expressive framework for multiagent sequential decision making. However, the complexity of these models—NEXP-Complete even for two agents—has limited their scalability. We present a promising new class of approximation algorithms by developing novel connections between multiagent planning and machine learning. We show how the multiagent planning problem can be reformulated as inference in a mixture of dynamic Bayesian networks (DBNs). This planning-as-inference approach paves the way for the application of efficient inference techniques in DBNs to multiagent decision making. To further improve scalability, we identify certain conditions that are sufficient to extend the approach to multiagent systems with dozens of agents. Specifically, we show that the necessary inference within the expectation-maximization framework can be decomposed into processes that often involve a small subset of agents, thereby facilitating scalability. We further show that a number of existing multiagent planning models satisfy these conditions. Experiments on large planning benchmarks confirm the benefits of our approach in terms of runtime and scalability with respect to existing techniques.



分散型POMDPは、マルチエージェントの逐次意思決定のための表現力豊かなフレームワークを提供します。しかし、これらのモデルの複雑さ（2エージェントでもNEXP-Complete）は、スケーラビリティを制限してきました。本稿では、マルチエージェントプランニングと機械学習の新たな関連性を開拓することで、有望な新しいクラスの近似アルゴリズムを提示します。マルチエージェントプランニング問題を、動的ベイジアンネットワーク（DBN）の混合における推論として再定式化する方法を示します。この推論としてのプランニングアプローチは、DBNにおける効率的な推論技術をマルチエージェント意思決定に適用する道を開きます。スケーラビリティをさらに向上させるために、このアプローチを数十のエージェントを含むマルチエージェントシステムに拡張するのに十分な条件を特定します。具体的には、期待最大化フレームワーク内で必要な推論を、多くの場合少数のエージェントのサブセットが関与するプロセスに分解することで、スケーラビリティが向上することを示します。さらに、既存の多くのマルチエージェントプランニングモデルがこれらの条件を満たしていることを示します。大規模なプランニングベンチマークを用いた実験により、既存の手法と比較して、実行時間とスケーラビリティの面で本アプローチの利点が確認されました。

Model Theory of XPath on Data Trees. Part I: Bisimulation and Characterization

Model Theory of XPath on Data Trees. Part I: Bisimulation and Characterization / データツリーにおけるXPathのモデル理論。パートI：双模倣と​​特性評価

We investigate model theoretic properties of XPath with data (in)equality tests over the class of data trees, i.e., the class of trees where each node contains a label from a finite alphabet and a data value from an infinite domain.We provide notions of (bi)simulations for XPpath logics containing the child, parent, ancestor and descendant axes to navigate the tree. We show that these notions precisely characterize the equivalence relation associated with each logic. We study formula complexity measures consisting of the number of nested axes and nested subformulas in a formula; these notions are akin to the notion of quantifier rank in first-order logic. We show characterization results for fine grained notions of equivalence and (bi)simulation that take into account these complexity measures. We also prove that positive fragments of these logics correspond to the formulas preserved under (non-symmetric) simulations. We show that the logic including the child axis is equivalent to the fragment of first-order logic invariant under the corresponding notion of bisimulation. If upward navigation is allowed the characterization fails but a weaker result can still be established. These results hold both over the class of possibly infinite data trees and over the class of finite data trees.Besides their intrinsic theoretical value, we argue that bi-simulations are useful tools to prove (non)expressivity results for the logics studied here, and we substantiate this claim with examples.



データツリーのクラス、すなわち各ノードが有限のアルファベットのラベルと無限のドメインのデータ値を含むツリーのクラスにおいて、データ（不）等性テストを用いたXPathのモデル理論的特性を調査します。ツリーをナビゲートするための子、親、祖先、子孫の軸を含むXPpath論理に対して、（双）シミュレーションの概念を与える。これらの概念が、各論理に関連する同値関係を正確に特徴付けることを示す。論理式内のネストされた軸とネストされた部分式の数からなる論理式複雑度尺度を検討します。これらの概念は、一階述語論理における量指定子のランクの概念に類似しています。これらの複雑度尺度を考慮した、同値性と（双）シミュレーションの細分化された概念の特性評価結果を示す。また、これらの論理の正のフラグメントが、（非対称）シミュレーションにおいて保存される論理式に対応することを証明します。子軸を含む論理は、対応する双シミュレーションの概念の下で不変な一階述語論理のフラグメントと同値であることを示す。上向きナビゲーションが許容される場合、この特徴付けは失敗するものの、より弱い結果は依然として確立できます。これらの結果は、無限データツリーのクラスと有限データツリーのクラスの両方で成立します。その本質的な理論的価値に加えて、双シミュレーションは、ここで検討する論理の（非）表現性結果を証明するための有用なツールであると主張し、例を用いてこの主張を実証します。

Regular Path Queries in Lightweight Description Logics: Complexity and Algorithms

Regular Path Queries in Lightweight Description Logics: Complexity and Algorithms / 軽量記述論理における正規パスクエリ：計算量とアルゴリズム

Conjunctive regular path queries are an expressive extension of the well-known class of conjunctive queries. Such queries have been extensively studied in the (graph) database community, since they support a controlled form of recursion and enable sophisticated path navigation. Somewhat surprisingly, there has been little work aimed at using such queries in the context of description logic (DL) knowledge bases, particularly for the lightweight DLs that are considered best suited for data-intensive applications. This paper aims to bridge this gap by providing algorithms and tight complexity bounds for answering two-way conjunctive regular path queries over DL knowledge bases formulated in lightweight DLs of the DL-Lite and EL families. Our results demonstrate that in data complexity, the cost of moving to this richer query language is as low as one could wish for: the problem is NL-complete for DL-Lite and P-complete for EL. The combined complexity of query answering increases from NP- to PSpace-complete, but for two-way regular path queries (without conjunction), we show that query answering is tractable even with respect to combined complexity. Our results reveal two-way conjunctive regular path queries as a promising language for querying data enriched by ontologies formulated in DLs of the DL-Lite and EL families or the corresponding OWL 2 QL and EL profiles.



連言正規パスクエリは、よく知られている連言クエリの表現力豊かな拡張です。このようなクエリは、制御された再帰形式をサポートし、洗練されたパスナビゲーションを可能にするため、（グラフ）データベースコミュニティで広く研究されてきた。やや意外なことに、このようなクエリを記述論理（DL）知識ベースのコンテキスト、特にデータ集約型アプリケーションに最適と考えられている軽量DLのコンテキストで使用することを目的とした研究はほとんど行われていない。本論文は、DL-LiteおよびELファミリーの軽量DLで定式化されたDL知識ベース上の双方向連言正規パスクエリに応答するためのアルゴリズムと厳密な計算量境界を提供することで、このギャップを埋めることを目指す。我々の結果は、データの複雑さを考慮すると、このより豊富なクエリ言語への移行コストが極めて低いことを示しています。問題は、DL-LiteではNL完全、ELではP完全です。クエリ応答の複合複雑度はNP完全からPSpace完全へと増大しますが、双方向の正規パスクエリ（連言なし）の場合、複合複雑度を考慮してもクエリ応答が扱いやすいことを示しています。我々の結果は、双方向の連言正規パスクエリが、DL-LiteおよびELファミリーのDL、または対応するOWL 2 QLおよびELプロファイルで定式化されたオントロジーによって強化されたデータのクエリに有望な言語であることを示しています。

Approximate Value Iteration with Temporally Extended Actions

Approximate Value Iteration with Temporally Extended Actions / 時間的に拡張されたアクションによる近似値反復法

Temporally extended actions have proven useful for reinforcement learning, but their duration also makes them valuable for efficient planning. The options framework provides a concrete way to implement and reason about temporally extended actions. Existing literature has demonstrated the value of planning with options empirically, but there is a lack of theoretical analysis formalizing when planning with options is more efficient than planning with primitive actions. We provide a general analysis of the convergence rate of a popular Approximate Value Iteration (AVI) algorithm called Fitted Value Iteration (FVI) with options. Our analysis reveals that longer duration options and a pessimistic estimate of the value function both lead to faster convergence. Furthermore, options can improve convergence even when they are suboptimal and sparsely distributed throughout the state-space. Next we consider the problem of generating useful options for planning based on a subset of landmark states. This suggests a new algorithm, Landmark-based AVI (LAVI), that represents the value function only at the landmark states. We analyze both FVI and LAVI using the proposed landmark-based options and compare the two algorithms. Our experimental results in three different domains demonstrate the key properties from the analysis. Our theoretical and experimental results demonstrate that options can play an important role in AVI by decreasing approximation error and inducing fast convergence.



時間的に拡張された行動は強化学習に有用であることが証明されているが、その持続時間は効率的な計画にも有用です。オプションフレームワークは、時間的に拡張された行動を実装し、それについて推論するための具体的な方法を提供します。既存の文献は、オプションを用いた計画の価値を経験的に実証しているが、オプションを用いた計画が基本行動を用いた計画よりも効率的な場合を形式化する理論的分析は不足しています。本稿では、オプションを用いた適合値反復法（FVI）と呼ばれる、一般的な近似値反復法（AVI）アルゴリズムの収束速度に関する一般的な分析を提供します。本分析により、持続時間の長いオプションと価値関数の悲観的な推定はどちらも収束を速めることが明らかになった。さらに、オプションは、最適ではなく状態空間全体にまばらに分布している場合でも、収束を改善できます。次に、ランドマーク状態のサブセットに基づいて、計画に有用なオプションを生成する問題について考察します。これは、ランドマーク状態のみで価値関数を表す新しいアルゴリズム、ランドマークベースAVI（LAVI）を提案します。提案されたランドマークベースのオプションを用いてFVIとLAVIの両方を分析し、2つのアルゴリズムを比較します。3つの異なるドメインにおける実験結果は、分析から得られた主要な特性を示しています。理論および実験の結果は、オプションが近似誤差を低減し、高速収束を誘導することでAVIにおいて重要な役割を果たすことができることを示しています。

Learning Relational Event Models from Video

Learning Relational Event Models from Video / ビデオからの関係イベントモデルの学習

Event models obtained automatically from video can be used in applications ranging from abnormal event detection to content based video retrieval. When multiple agents are involved in the events, characterizing events naturally suggests encoding interactions as relations. Learning event models from this kind of relational spatio-temporal data using relational learning techniques such as Inductive Logic Programming (ILP) hold promise, but have not been successfully applied to very large datasets which result from video data. In this paper, we present a novel framework REMIND (Relational Event Model INDuction) for supervised relational learning of event models from large video datasets using ILP. Efficiency is achieved through the learning from interpretations setting and using a typing system that exploits the type hierarchy of objects in a domain. The use of types also helps prevent over generalization. Furthermore, we also present a type-refining operator and prove that it is optimal. The learned models can be used for recognizing events from previously unseen videos. We also present an extension to the framework by integrating an abduction step that improves the learning performance when there is noise in the input data. The experimental results on several hours of video data from two challenging real world domains (an airport domain and a physical action verbs domain) suggest that the techniques are suitable to real world scenarios.



ビデオから自動的に取得されたイベントモデルは、異常イベント検出からコンテンツベースのビデオ検索まで、さまざまなアプリケーションに使用できます。複数のエージェントがイベントに関与している場合、イベントを特徴付けることは、当然、相互作用を関係としてエンコードすることを示唆します。帰納的論理プログラミング（ILP）などの関係学習手法を用いて、このような関係のある時空間データからイベントモデルを学習することは有望ですが、ビデオデータから得られる非常に大規模なデータセットにはうまく適用されていません。本稿では、ILPを用いて大規模なビデオデータセットからイベントモデルを教師あり関係学習するための新しいフレームワークREMIND（関係イベントモデルINDuction）を紹介します。効率性は、解釈設定からの学習と、ドメイン内のオブジェクトの型階層を活用する型付けシステムの使用によって実現されます。型の使用は過度な一般化を防ぐのにも役立ちます。さらに、型を精緻化する演算子も提示し、それが最適であることを証明します。学習したモデルは、未学習のビデオからのイベント認識に使用できます。また、入力データにノイズがある場合の学習パフォーマンスを向上させるアブダクションステップを統合することで、フレームワークを拡張する方法も示します。2つの難しい実世界ドメイン（空港ドメインと身体動作動詞ドメイン）からの数時間分のビデオデータを用いた実験結果は、これらの手法が実世界のシナリオに適していることを示唆しています。

Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates

Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates / 組み合わせ保護の回避：単峰性有権者のための多項式時間アルゴリズム

For many election systems, bribery (and related) attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. This paper shows that for voters who follow the most central political-science model of electorates—single-peaked preferences—those hardness protections vanish. By using single-peaked preferences to simplify combinatorial covering challenges, we for the first time show that NP-hard bribery problems—including those for Kemeny and Llull elections—fall to polynomial time for single-peaked electorates. By using single-peaked preferences to simplify combinatorial partition challenges, we for the first time show that NP-hard partition-of-voters problems fall to polynomial time for single-peaked electorates. We show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though Theta-two-complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates.



多くの選挙制度において、買収攻撃（および関連攻撃）は、分割や被覆などの組み合わせ論的に豊富な構造の構築を用いることでNP困難であることが示されてきた。本論文では、最も中心的な政治学の選挙民モデルである単峰性の選好に従う有権者については、それらの困難性保護が消滅することを示す。単峰性の選好を用いて組み合わせ被覆問題を簡略化することで、ケメニー選挙およびリュイ選挙を含むNP困難な買収問題が単峰性の選挙民については多項式時間で解決できることを初めて示す。単峰性の選好を用いて組み合わせ分割問題を簡略化することで、単峰性の選挙民についてはNP困難な有権者分割問題が多項式時間で解決できることを初めて示す。単峰性の選挙民については、ドッドソン選挙およびケメニー選挙の勝者問題は、一般的な場合にはシータ2完全ではあるが、多項式時間で解決できることを示す。また、単峰性選挙区におけるスコアリングプロトコルにおける重み付き連合操作の複雑性を完全に分類します。

Satsisfiability and Systematicity

Satsisfiability and Systematicity / 充足可能性と体系性

We introduce a new notion of systematicity for satisfiability algorithms with restarts, saying that an algorithm is strongly systematic if it is systematic independent of restart policy but weakly systematic if it is systematic for some restart policies but not others. We show that existing satisfiability engines are generally only weakly systematic, and describe FLEX, a strongly systematic algorithm that uses an amount of memory polynomial in the size of the problem. On large number factoring problems, FLEX appears to outperform weakly systematic approaches.



リスタートを伴う充足可能性アルゴリズムに体系性という新しい概念を導入し、アルゴリズムがリスタートポリシーに依存せずに体系的である場合は強く体系的であり、一部のリスタートポリシーでは体系的だが他のリスタートポリシーでは体系的でない場合は弱体系的であるとします。既存の充足可能性エンジンは一般的に弱体系的であることを示し、問題のサイズに比例するメモリ量を使用する強体系アルゴリズムであるFLEXについて説明します。大数の因数分解問題において、FLEXは弱体系的アプローチよりも優れた性能を示す。

ITSAT: An Efficient SAT-Based Temporal Planner

ITSAT: An Efficient SAT-Based Temporal Planner / ITSAT：効率的なSATベースの時間プランナー

Planning as satisfiability is known as an efficient approach to deal with many types of planning problems. However, this approach has not been competitive with the state-space based methods in temporal planning. This paper describes ITSAT as an efficient SAT-based (satisfiability based) temporal planner capable of temporally expressive planning. The novelty of ITSAT lies in the way it handles temporal constraints of given problems without getting involved in the difficulties of introducing continuous variables into the corresponding satisfiability problems. We also show how, as in SAT-based classical planning, carefully devised preprocessing and encoding schemata can considerably improve the efficiency of SAT-based temporal planning. We present two preprocessing methods for mutex relation extraction and action compression. We also show that the separation of causal and temporal reasoning enables us to employ compact encodings that are based on the concept of parallel execution semantics. Although such encodings have been shown to be quite effective in classical planning, ITSAT is the first temporal planner utilizing this type of encoding. Our empirical results show that not only does ITSAT outperform the state-of-the-art temporally expressive planners, it is also competitive with the fast temporal planners that cannot handle required concurrency.



充足可能性としての計画は、多くの種類の計画問題に対処するための効率的なアプローチとして知られています。しかし、このアプローチは、時間的計画において状態空間ベースの手法と競合できていない。本論文では、時間的に表現力豊かな計画を可能にする効率的なSATベース（充足可能性ベース）の時間的プランナーであるITSATについて説明します。ITSATの新規性は、連続変数を対応する充足可能性問題に導入する際の困難に巻き込まれることなく、与えられた問題の時間的制約を処理する方法にあります。また、SATベースの従来のプランニングと同様に、慎重に考案された前処理およびエンコード スキーマによって、SATベースの時間的プランニングの効率を大幅に向上できることも示します。ミューテックス関係の抽出とアクションの圧縮のための2つの前処理方法を紹介します。さらに、因果推論と時間的推論を分離することで、並列実行セマンティクスの概念に基づくコンパクトなエンコードを使用できることも示します。このようなエンコードは従来のプランニングでは非常に効果的であることが示されているものの、ITSATはこのタイプのエンコードを使用する最初の時間的プランナーです。実証結果から、ITSATは最先端の時間的表現力を持つプランナーよりも性能が優れているだけでなく、必要な並行性を処理できない高速な時間的プランナーにも匹敵することが示されています。

Placement of Loading Stations for Electric Vehicles: No Detours Necessary!

Placement of Loading Stations for Electric Vehicles: No Detours Necessary! / 電気自動車用充電ステーションの配置：迂回不要！

Compared to conventional cars, electric vehicles (EVs) still suffer from considerably shorter cruising ranges. Combined with the sparsity of battery loading stations, the complete transition to E-mobility still seems a long way to go. In this paper, we consider the problem of placing as few loading stations as possible so that on any shortest path there are sufficiently many not to run out of energy. We show how to model this problem and introduce heuristics which provide close-to-optimal solutions even in large road networks.



従来の自動車と比較して、電気自動車（EV）の航続距離は依然としてかなり短いという問題があります。さらに、バッテリー充電ステーションの不足も相まって、Eモビリティへの完全な移行にはまだまだ時間がかかりそうです。本稿では、最短経路において十分な数の充電ステーションを配置し、エネルギー切れを起こさないような充電ステーションを可能な限り少なく配置するという問題を考察します。この問題のモデル化方法を示し、大規模な道路網においても最適解に近い解を提供するヒューリスティックスを紹介します。

Evolutionary Dynamics of Multi-Agent Learning: A Survey

Evolutionary Dynamics of Multi-Agent Learning: A Survey / マルチエージェント学習の進化ダイナミクス：サーベイ

The interaction of multiple autonomous agents gives rise to highly dynamic and nondeterministic environments, contributing to the complexity in applications such as automated financial markets, smart grids, or robotics. Due to the sheer number of situations that may arise, it is not possible to foresee and program the optimal behaviour for all agents beforehand. Consequently, it becomes essential for the success of the system that the agents can learn their optimal behaviour and adapt to new situations or circumstances. The past two decades have seen the emergence of reinforcement learning, both in single and multi-agent settings, as a strong, robust and adaptive learning paradigm. Progress has been substantial, and a wide range of algorithms are now available. An important challenge in the domain of multi-agent learning is to gain qualitative insights into the resulting system dynamics. In the past decade, tools and methods from evolutionary game theory have been successfully employed to study multi-agent learning dynamics formally in strategic interactions. This article surveys the dynamical models that have been derived for various multi-agent reinforcement learning algorithms, making it possible to study and compare them qualitatively. Furthermore, new learning algorithms that have been introduced using these evolutionary game theoretic tools are reviewed. The evolutionary models can be used to study complex strategic interactions. Examples of such analysis are given for the domains of automated trading in stock markets and collision avoidance in multi-robot systems. The paper provides a roadmap on the progress that has been achieved in analysing the evolutionary dynamics of multi-agent learning by highlighting the main results and accomplishments.



複数の自律エージェントの相互作用は、高度に動的かつ非決定論的な環境を生み出し、自動化された金融市場、スマートグリッド、ロボット工学などのアプリケーションの複雑性を高めます。発生しうる状況の数が膨大であるため、すべてのエージェントの最適な行動を事前に予測しプログラムすることは不可能です。したがって、システムの成功には、エージェントが最適な行動を学習し、新しい状況や環境に適応できることが不可欠となります。過去20年間、単一エージェント環境とマルチエージェント環境の両方において、強化学習が強力で堅牢かつ適応的な学習パラダイムとして登場しました。進歩は著しく、現在では幅広いアルゴリズムが利用可能です。マルチエージェント学習の分野における重要な課題は、結果として生じるシステムダイナミクスに関する定性的な洞察を得ることです。過去10年間、進化ゲーム理論のツールと手法は、戦略的相互作用におけるマルチエージェント学習のダイナミクスを形式的に研究するために効果的に活用されてきました。本稿では、様々なマルチエージェント強化学習アルゴリズムのために導出された動的モデルを概観し、それらを定性的に研究・比較することを可能にします。さらに、これらの進化ゲーム理論的ツールを用いて導入された新しい学習アルゴリズムについてもレビューします。これらの進化モデルは、複雑な戦略的相互作用の研究に用いることができます。そのような分析例として、株式市場における自動取引やマルチロボットシステムにおける衝突回避の領域が示されています。本論文では、主要な結果と成果を強調することにより、マルチエージェント学習の進化ダイナミクスの分析において達成された進歩のロードマップを提供します。

Tree-Width and the Computational Complexity of MAP Approximations in Bayesian Networks

Tree-Width and the Computational Complexity of MAP Approximations in Bayesian Networks / ベイジアンネットワークにおける木幅とMAP近似の計算量

The problem of finding the most probable explanation to a designated set of variables given partial evidence (the MAP problem) is a notoriously intractable problem in Bayesian networks, both to compute exactly and to approximate. It is known, both from theoretical considerations and from practical experience, that low tree-width is typically an essential prerequisite to efficient exact computations in Bayesian networks. In this paper we investigate whether the same holds for approximating MAP. We define four notions of approximating MAP (by value, structure, rank, and expectation) and argue that all of them are intractable in general. We prove that efficient value-approximations, structure-approximations, and rank-approximations of MAP instances with high tree-width will violate the Exponential Time Hypothesis. In contrast, we show that MAP can sometimes be efficiently expectation-approximated, even in instances with high tree-width, if the most probable explanation has a high probability. We introduce the complexity class FERT, analogous to the class FTP, to capture this notion of fixed-parameter expectation-approximability. We suggest a road-map to future research that yields fixed-parameter tractable results for expectation-approximate MAP, even in graphs with high tree-width.



部分的な証拠を与えられた場合に、指定された変数の集合に対する最も可能性の高い説明を見つける問題（MAP問題）は、ベイジアンネットワークにおいて、厳密な計算と近似計算の両方において、非常に扱いにくい問題として知られています。理論的な考察と実際の経験の両方から、ベイジアンネットワークにおける効率的な厳密な計算には、通常、狭いツリー幅が不可欠な前提条件であることが知られています。本論文では、MAPの近似についても同様のことが当てはまるかどうかを調査します。MAPを近似するための4つの概念（値、構造、ランク、期待値）を定義し、それらすべてが一般に扱いにくいことを主張します。木幅の広いMAPインスタンスに対する効率的な値近似、構造近似、およびランク近似は、指数時間仮説に違反することを証明します。対照的に、最尤説明の確率が高い場合、木幅の広いインスタンスであっても、MAPは効率的に期待値近似できる場合があることを示します。この固定パラメータ期待値近似可能性の概念を捉えるために、FTPクラスに類似した複雑性クラスFERTを導入します。木幅の広いグラフであっても、期待値近似MAPに対して固定パラメータで扱いやすい結果をもたらす、将来の研究へのロードマップを提案します。

Mechanisms for Multi-unit Combinatorial Auctions with a Few Distinct Goods

Mechanisms for Multi-unit Combinatorial Auctions with a Few Distinct Goods / 少数の異なる財を持つマルチユニット組み合わせオークションのメカニズム

We design and analyze deterministic truthful approximation mechanisms for multi-unit Combinatorial Auctions involving only a constant number of distinct goods, each in arbitrary limited supply. Prospective buyers (bidders) have preferences over multisets of items, i.e., for more than one unit per distinct good. Our objective is to determine allocations of multisets that maximize the Social Welfare. Our main results are for multi-minded and submodular bidders. In the first setting each bidder has a positive value for being allocated one multiset from a prespecified demand set of alternatives. In the second setting each bidder is associated to a submodular valuation function that defines his value for the multiset he is allocated. For multi-minded bidders, we design a truthful FPTAS that fully optimizes the Social Welfare, while violating the supply constraints on goods within factor (1+e), for any fixed e>0 (i.e., the approximation applies to the constraints and not to the Social Welfare). This result is best possible, in that full optimization is impossible without violating the supply constraints. For submodular bidders, we obtain a PTAS that approximates the optimum Social Welfare within factor (1+e), for any fixed e>0, without violating the supply constraints. This result is best possible as well. Our allocation algorithms are Maximal-in-Range and yield truthful mechanisms, when paired with Vickrey-Clarke-Groves payments.



我々は、一定数の異なる財（それぞれ任意の数量限定）のみを対象とするマルチユニット・コンビナトリアル・オークションのための決定論的かつ真近似メカニズムを設計・解析します。購入希望者（入札者）は、複数の財セット、すなわち異なる財1つにつき複数の財セットに対する選好を持つ。我々の目的は、社会福祉を最大化するマルチセットの割り当てを決定することです。主な結果は、マルチマインド入札者とサブモジュラー入札者についてです。前者の設定では、各入札者は、事前に指定された需要セットから1つのマルチセットを割り当てられることに正の価値を持つ。後者の設定では、各入札者は、割り当てられたマルチセットに対する自身の価値を定義するサブモジュラー評価関数に関連付けられます。マルチマインド入札者に対しては、任意の固定e>0に対して、財の供給制約を(1+e)以内で破りながら、社会福祉を完全に最適化する真近似FPTASを設計する（すなわち、近似は制約に適用されるが、社会福祉には適用されない）。この結果は、供給制約に違反することなく完全な最適化を行うことは不可能であるという点で、最良の結果です。劣モジュラ入札者の場合、供給制約に違反することなく、任意の固定e>0に対して、係数(1+e)の範囲内で最適な社会福祉を近似するPTASが得られます。この結果もまた最良の結果です。我々の割り当てアルゴリズムは範囲内最大であり、Vickrey-Clarke-Groves支払いと組み合わせることで、真実のメカニズムを生み出す。

AutoFolio: An Automatically Configured Algorithm Selector

AutoFolio: An Automatically Configured Algorithm Selector / AutoFolio：自動構成アルゴリズムセレクタ

Algorithm selection (AS) techniques — which involve choosing from a set of algorithms the one expected to solve a given problem instance most efficiently — have substantially improved the state of the art in solving many prominent AI problems, such as SAT, CSP, ASP, MAXSAT and QBF. Although several AS procedures have been introduced, not too surprisingly, none of them dominates all others across all AS scenarios. Furthermore, these procedures have parameters whose optimal values vary across AS scenarios. This holds specifically for the machine learning techniques that form the core of current AS procedures, and for their hyperparameters. Therefore, to successfully apply AS to new problems, algorithms and benchmark sets, two questions need to be answered: (i) how to select an AS approach and (ii) how to set its parameters effectively. We address both of these problems simultaneously by using automated algorithm configuration. Specifically, we demonstrate that we can automatically configure claspfolio 2, which implements a large variety of different AS approaches and their respective parameters in a single, highly-parameterized algorithm framework. Our approach, dubbed AutoFolio, allows researchers and practitioners across a broad range of applications to exploit the combined power of many different AS methods. We demonstrate AutoFolio can significantly improve the performance of claspfolio 2 on 8 out of the 13 scenarios from the Algorithm Selection Library, leads to new state-of-the-art algorithm selectors for 7 of these scenarios, and matches state-of-the-art performance (statistically) on all other scenarios. Compared to the best single algorithm for each AS scenario, AutoFolio achieves average speedup factors between 1.3 and 15.4.



アルゴリズム選択（AS）技術（これは、与えられた問題インスタンスを最も効率的に解決すると期待されるアルゴリズムを複数のアルゴリズムから選択することを伴う）は、SAT、CSP、ASP、MAXSAT、QBFといった多くの主要なAI問題の解決における最先端技術を大幅に向上させた。いくつかのAS手順が導入されているが、当然のことながら、すべてのASシナリオにおいて他の手順をすべて凌駕する手順はない。さらに、これらの手順には、ASシナリオごとに最適値が変化するパラメータがあります。これは、現在のAS手順の中核を成す機械学習技術とそのハイパーパラメータに特に当てはまります。したがって、ASを新しい問題、アルゴリズム、ベンチマークセットに適用するには、(i) ASアプローチの選択方法、(ii)そのパラメータの効果的な設定方法という2つの質問に答える必要があります。私たちは、自動アルゴリズム設定を用いることで、これらの問題の両方に同時に対処します。具体的には、多種多様なASアプローチとそのパラメータを単一の高度にパラメータ化されたアルゴリズムフレームワークに実装したclaspfolio 2を自動設定できることを実証します。AutoFolioと名付けたこのアプローチにより、幅広い分野の研究者や実務家は、多様なAS手法の総合的なパワーを活用できるようになります。AutoFolioは、アルゴリズム選択ライブラリの13のシナリオのうち8つにおいてclaspfolio 2のパフォーマンスを大幅に向上させ、7つのシナリオにおいて最先端のアルゴリズムセレクターを新たに導き出し、その他のすべてのシナリオにおいて最先端のパフォーマンスに（統計的に）匹敵することを実証しました。各ASシナリオにおける最良の単一アルゴリズムと比較して、AutoFolioは平均1.3～15.4倍の高速化を達成しています。

Belief Change with Uncertain Action Histories

Belief Change with Uncertain Action Histories / 不確実な行動履歴による信念の変化

We consider the iterated belief change that occurs following an alternating sequence of actions and observations. At each instant, an agent has beliefs about the actions that have occurred as well as beliefs about the resulting state of the world. We represent such problems by a sequence of ranking functions, so an agent assigns a quantitative plausibility value to every action and every state at each point in time. The resulting formalism is able to represent fallible belief, erroneous perception, exogenous actions, and failed actions. We illustrate that our framework is a generalization of several existing approaches to belief change, and it appropriately captures the non-elementary interaction between belief update and belief revision.



我々は、行動と観測の交互シーケンスに続いて発生する反復的な信念変化を考察します。各瞬間において、エージェントは発生した行動に関する信念と、結果として生じる世界の状態に関する信念を持ちます。我々はこのような問題をランキング関数のシーケンスで表現し、エージェントは各時点におけるすべての行動とすべての状態に定量的な妥当性値を割り当てます。結果として得られる形式主義は、誤りやすい信念、誤った知覚、外生的行動、そして失敗した行動を表現できます。我々のフレームワークは、信念変化に対する既存のいくつかのアプローチを一般化したものであり、信念の更新と信念の修正の間の非基本的な相互作用を適切に捉えていることを示します。

The Ceteris Paribus Structure of Logics of Game Forms

The Ceteris Paribus Structure of Logics of Game Forms / ゲーム形式のロジックにおけるCeteris Paribus構造

The article introduces a ceteris paribus modal logic, called CP, interpreted on the equivalence classes induced by finite sets of propositional atoms. This logic is studied and then used to embed three logics of strategic interaction, namely atemporal STIT, the coalition logic of propositional control (CL−PC) and the starless fragment of the dynamic logic of propositional assignments (DL−PA). The embeddings highlight a common ceteris paribus structure underpinning the key operators of all these apparently very different logics and show, we argue, remarkable similarities behind some of the most influential formalisms for reasoning about strategic interaction



本稿では、有限集合の命題アトムによって誘導される同値類に基づいて解釈される、CPと呼ばれる「ceteris paribus」様相論理を紹介します。この論理を研究し、戦略的相互作用の3つの論理、すなわち非時間的STIT、命題制御の連合論理（CL−PC）、および命題割当の動的論理の無星断片（DL−PA）を埋め込むために用います。これらの埋め込みは、一見非常に異なるこれらの論理の主要演算子を支える共通のceteris paribus構造を浮き彫りにし、戦略的相互作用に関する推論において最も影響力のあるいくつかの形式主義の背後にある顕著な類似性を示していると我々は主張します。

参考文献

• Journal of Artificial Intelligence Resarch Vol. 53 (2015)

関連情報

• Journal of Artificial Intelligence Research: 論文一覧