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

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

論文

On the Decomposition of Abstract Dialectical Frameworks and the Complexity of Naive-based Semantics

On the Decomposition of Abstract Dialectical Frameworks and the Complexity of Naive-based Semantics / 抽象弁証法的枠組みの分解とナイーブベース意味論の複雑性について

Abstract dialectical frameworks (ADFs) are a recently introduced powerful generalization of Dung’s popular abstract argumentation frameworks (AFs). Inspired by similar work for AFs, we introduce a decomposition scheme for ADFs, which proceeds along the ADF’s strongly connected components. We find that, for several semantics, the decomposition-based version coincides with the original semantics, whereas for others, it gives rise to a new semantics. These new semantics allow us to deal with pertinent problems such as odd-length negative cycles in a more general setting, that for instance also encompasses logic programs. We perform an exhaustive analysis of the computational complexity of these new, so-called naive-based semantics. The results are quite interesting, for some of them involve little-known classes of the so-called Boolean hierarchy (another hierarchy in between classes of the polynomial hierarchy). Furthermore, in credulous and sceptical entailment, the complexity can be different depending on whether we check for truth or falsity of a specific statement.



抽象弁証法的枠組み（ADF）は、Dungの人気の抽象論証枠組み（AF）を強力に一般化したもので、最近導入されました。AFに関する同様の研究に着想を得て、ADFの強連結成分に沿って分解を進めるADFの分解スキームを導入しました。いくつかの意味論では、分解ベースのバージョンが元の意味論と一致する一方で、他の意味論では新しい意味論を生み出すことがわかりました。これらの新しい意味論により、奇数長の負の閉路などの関連問題を、例えば論理プログラムも含むより一般的な設定で扱うことができます。これらの新しい、いわゆるナイーブベースの意味論の計算複雑性を徹底的に分析しました。結果は非常に興味深いもので、その中には、いわゆるブール階層（多項式階層のクラス間にある別の階層）のあまり知られていないクラスが含まれているものもあります。さらに、信じやすい含意と懐疑的な含意では、特定の文の真偽を確認するかどうかによって複雑さが異なる場合があります。

The Societal Implications of Deep Reinforcement Learning

The Societal Implications of Deep Reinforcement Learning / 深層強化学習の社会的影響

Deep Reinforcement Learning (DRL) is an avenue of research in Artificial Intelligence (AI) that has received increasing attention within the research community in recent years, and is beginning to show potential for real-world application. DRL is one of the most promising routes towards developing more autonomous AI systems that interact with and take actions in complex real-world environments, and can more flexibly solve a range of problems for which we may not be able to precisely specify a correct ‘answer’. This could have substantial implications for people’s lives: for example by speeding up automation in various sectors, changing the nature and potential harms of online influence, or introducing new safety risks in physical infrastructure. In this paper, we review recent progress in DRL, discuss how this may introduce novel and pressing issues for society, ethics, and governance, and highlight important avenues for future research to better understand DRL’s societal implications.This article appears in the special track on AI and Society.



深層強化学習（DRL）は、近年研究コミュニティで注目を集めている人工知能（AI）の研究分野であり、実世界への応用の可能性を示し始めています。DRLは、複雑な現実世界の環境と相互作用し、行動を起こす、より自律的なAIシステムを開発するための最も有望な方法の一つであり、正しい「答え」を正確に指定できない可能性のあるさまざまな問題をより柔軟に解決できます。これは、様々な分野における自動化の加速、オンラインの影響力の性質と潜在的な害の変化、物理インフラにおける新たな安全リスクの導入など、人々の生活に大きな影響を与える可能性があります。本稿では、DRLの最近の進歩をレビューし、これが社会、倫理、ガバナンスに新たな差し迫った問題をもたらす可能性について議論し、DRLの社会的影響をより深く理解するための将来の研究の重要な道筋を明らかにします。この記事は、AIと社会に関する特別トラックに掲載されています。

Induction and Exploitation of Subgoal Automata for Reinforcement Learning

Induction and Exploitation of Subgoal Automata for Reinforcement Learning / 強化学習のためのサブゴールオートマトンによる誘導と活用

In this paper we present ISA, an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves reinforcement learning with the induction of a subgoal automaton, an automaton whose edges are labeled by the task’s subgoals expressed as propositional logic formulas over a set of high-level events. A subgoal automaton also consists of two special states: a state indicating the successful completion of the task, and a state indicating that the task has finished without succeeding. A state-of-the-art inductive logic programming system is used to learn a subgoal automaton that covers the traces of high-level events observed by the RL agent. When the currently exploited automaton does not correctly recognize a trace, the automaton learner induces a new automaton that covers that trace. The interleaving process guarantees the induction of automata with the minimum number of states, and applies a symmetry breaking mechanism to shrink the search space whilst remaining complete. We evaluate ISA in several gridworld and continuous state space problems using different RL algorithms that leverage the automaton structures. We provide an in-depth empirical analysis of the automaton learning performance in terms of the traces, the symmetry breaking and specific restrictions imposed on the final learnable automaton. For each class of RL problem, we show that the learned automata can be successfully exploited to learn policies that reach the goal, achieving an average reward comparable to the case where automata are not learned but handcrafted and given beforehand.



本稿では、エピソード強化学習（RL）タスクにおけるサブゴールの学習と活用のための手法であるISAを提示します。ISAは、強化学習とサブゴール・オートマトン（高レベルイベントの集合に対する命題論理式として表現されたタスクのサブゴールをエッジにラベル付けしたオートマトン）の誘導をインターリーブします。サブゴール・オートマトンはまた、タスクが正常に完了したことを示す状態と、タスクが成功せずに終了したことを示す状態という2つの特殊な状態から構成されます。最先端の帰納的論理プログラミングシステムを用いて、RLエージェントによって観測された高レベルイベントのトレースをカバーするサブゴール・オートマトンを学習します。現在利用されているオートマトンがトレースを正しく認識しない場合、オートマトン学習器はそのトレースをカバーする新しいオートマトンを誘導します。このインターリーブ処理は、最小限の状態数でオートマトンを誘導することを保証し、対称性破壊メカニズムを適用することで、探索空間を縮小しながらも完全性を維持します。我々は、オートマトン構造を活用する様々な強化学習アルゴリズムを用いて、複数のグリッドワールド問題および連続状態空間問題におけるISAを評価した。トレース、対称性の破れ、および最終的な学習可能オートマトンに課される特定の制約の観点から、オートマトン学習性能の詳細な実証分析を提供します。強化学習問題の各クラスについて、学習済みオートマトンを活用して目標に到達するポリシーを学習し、オートマトンを学習せずに手作業で作成し事前に与えた場合に匹敵する平均報酬を達成できることを示す。

Lilotane: A Lifted SAT-based Approach to Hierarchical Planning

Lilotane: A Lifted SAT-based Approach to Hierarchical Planning / Lilotane：階層的計画へのリフト型SATベースのアプローチ

One of the oldest and most popular approaches to automated planning is to encode the problem at hand into a propositional formula and use a Satisfiability (SAT) solver to find a solution. In all established SAT-based approaches for Hierarchical Task Network (HTN) planning, grounding the problem is necessary and oftentimes introduces a combinatorial blowup in terms of the number of actions and reductions to encode. Our contribution named Lilotane (Lifted Logic for Task Networks) eliminates this issue for Totally Ordered HTN planning by directly encoding the lifted representation of the problem at hand. We lazily instantiate the problem hierarchy layer by layer and use a novel SAT encoding which allows us to defer decisions regarding method arguments to the stage of SAT solving. We show the correctness of our encoding and compare it to the best performing prior SAT encoding in a worst-case analysis. Empirical evaluations confirm that Lilotane outperforms established SAT-based approaches, often by orders of magnitude, produces much smaller formulae on average, and compares favorably to other state-of-the-art HTN planners regarding robustness and plan quality. In the International Planning Competition (IPC) 2020, a preliminary version of Lilotane scored the second place. We expect these considerable improvements to SAT-based HTN planning to open up new perspectives for SAT-based approaches in related problem classes.



自動計画への最も古く、最も人気のあるアプローチの1つは、問題を命題式にエンコードし、充足可能性(SAT)ソルバーを使用して解を求めることです。階層型タスクネットワーク(HTN)計画のための確立されたSATベースのアプローチはすべて、問題のグラウンディングが必要であり、エンコードするアクションとリダクションの数に関して、組み合わせの爆発を招くことが多い。Lilotane (Lifted Logic for Task Networks)という名の私たちの貢献は、問題のリフトされた表現を直接エンコードすることで、Totally Ordered HTNプランニングのこの問題を解消します。問題階層をレイヤーごとに遅延インスタンス化し、メソッド引数に関する決定をSAT解決の段階まで延期できる新しいSATエンコードを使用します。エンコードの正しさを示し、最悪ケース分析で従来の最高パフォーマンスのSATエンコードと比較します。実証的評価により、Lilotaneは確立されたSATベースのアプローチよりも桁違いに優れていることが多く、平均してはるかに小さな式を生成し、堅牢性とプランの品質に関して他の最先端のHTNプランナーに匹敵することが確認されました。International Planning Competition (IPC) 2020では、Lilotaneの予備バージョンが2位を獲得しました。SATベースのHTNプランニングに対するこれらの大幅な改善により、関連する問題クラスにおけるSATベースのアプローチに新たな展望が開かれると期待しています。

Computational Complexity of Computing Symmetries in Finite-Domain Planning

Computational Complexity of Computing Symmetries in Finite-Domain Planning / 計算論的有限領域計画における対称性の計算の複雑さ

Symmetry-based pruning is a powerful method for reducing the search effort in finitedomain planning. This method is based on exploiting an automorphism group connected to the ground description of the planning task { these automorphisms are known as structural symmetries. In particular, we are interested in the StructSym problem where the generators of this group are to be computed. It has been observed in practice that the StructSym problem is surprisingly easy to solve. We explain this phenomenon by showing that StructSym is GI-complete, i.e., the graph isomorphism problem is polynomial-time equivalent to it and, consequently, solvable in quasi-polynomial time. This implies that it is solvable substantially faster than most computationally hard problems encountered in AI. We accompany this result by identifying natural restrictions of the planning task and its causal graph that ensure that StructSym can be solved in polynomial time. Given that the StructSym problem is GI-complete and thus solvable quite efficiently, it is interesting to analyse if other symmetries (than those that are encompassed by the StructSym problem) can be computed and/or analysed efficiently, too. To this end, we present a highly negative result: checking whether there exists an automorphism of the state transition graph that maps one state s into another state t is a PSPACE-hard problem and, consequently, at least as hard as the planning problem itself.



対称性に基づく枝刈りは、有限領域プランニングにおける探索労力を削減する強力な手法です。この手法は、プランニングタスクの基本記述に関連付けられた自己同型群を利用することに基づいています{これらの自己同型は構造的対称性として知られています。特に、この群の生成元を計算するStructSym問題に着目しています。実際には、StructSym問題は驚くほど簡単に解決できることが観察されています。この現象を説明するために、StructSymはGI完全、つまりグラフ同型問題は多項式時間で同等であり、その結果、準多項式時間で解決可能です。これは、AIで遭遇するほとんどの計算困難な問題よりも大幅に高速に解決可能であることを意味します。この結果に伴い、StructSymを多項式時間で解決できるようにするための、プランニングタスクとその因果グラフの自然な制約も特定します。StructSym問題はGI完全であり、したがって非常に効率的に解けることを考えると、（StructSym問題に含まれるもの以外の）他の対称性も効率的に計算および／または解析できるかどうかを分析することは興味深いことです。この目的のために、我々は非常に否定的な結果を示します。つまり、ある状態sを別の状態tにマッピングする状態遷移グラフの自己同型が存在するかどうかを確認することはPSPACE困難な問題であり、したがって、少なくとも計画問題自体と同じくらい困難です。

Zone pAth Construction (ZAC) based Approaches for Effective Real-Time Ridesharing

Zone pAth Construction (ZAC) based Approaches for Effective Real-Time Ridesharing / 効果的なリアルタイムライドシェアリングのためのZone pAth構築（ZAC）に基づくアプローチ

Real-time ridesharing systems such as UberPool, Lyft Line and GrabShare have become hugely popular as they reduce the costs for customers, improve per trip revenue for drivers and reduce traffic on the roads by grouping customers with similar itineraries. The key challenge in these systems is to group the “right” requests to travel together in the “right” available vehicles in real-time, so that the objective (e.g., requests served, revenue or delay) is optimized. This challenge has been addressed in existing work by: (i) generating as many relevant feasible combinations of requests (with respect to the available delay for customers) as possible in real-time; and then (ii) optimizing assignment of the feasible request combinations to vehicles. Since the number of request combinations increases exponentially with the increase in vehicle capacity and number of requests, unfortunately, such approaches have to employ ad hoc heuristics to identify a subset of request combinations for assignment.Our key contribution is in developing approaches that employ zone (abstraction of individual locations) paths instead of request combinations. Zone paths allow for generation of significantly more “relevant” combinations (in comparison to ad hoc heuristics) in real-time than competing approaches due to two reasons: (i) Each zone path can typically represent multiple request combinations; (ii) Zone paths are generated using a combination of offline and online methods. Specifically, we contribute both myopic (ridesharing assignment focussed on current requests only) and non-myopic (ridesharing assignment considers impact on expected future requests) approaches that employ zone paths. In our experimental results, we demonstrate that our myopic approach outperforms the current best myopic approach for ridesharing on both real-world and synthetic datasets (with respect to both objective and runtime). We also show that our non-myopic approach obtains 14.7% improvement over existing myopic approach. Our non-myopic approach gets improvements of up to 12.48% over a recent non-myopic approach, NeurADP. Even when NeurADP is allowed to optimize learning over test settings, results largely remain comparable except in a couple of cases, where NeurADP performs better.



UberPool、Lyft Line、GrabShareなどのリアルタイムライドシェアシステムは、顧客のコストを削減し、ドライバーの1回あたりの収益を向上させ、同様の旅程を持つ顧客をグループ化することで道路の交通量を減らすため、非常に人気が高まっています。これらのシステムにおける主要な課題は、目的（例えば、処理されるリクエスト、収益、遅延）が最適化されるように、「適切な」移動リクエストを「適切な」利用可能な車両でリアルタイムにグループ化することです。この課題は、既存の研究で次のように対処されてきました。(i)要求の関連性の高い実行可能な組み合わせを(顧客が利用できる遅延に関して)可能な限り多くリアルタイムで生成し、(ii)実行可能な要求の組み合わせの車両への割り当てを最適化します。要求の組み合わせの数は車両の容量と要求数の増加に伴って指数関数的に増加するため、残念ながら、このようなアプローチでは、割り当てる要求の組み合わせのサブセットを識別するためにアドホック ヒューリスティックを使用する必要があります。私たちの主な貢献は、要求の組み合わせの代わりにゾーン(個々の場所の抽象化)パスを使用するアプローチの開発です。ゾーン パスを使用すると、競合するアプローチよりもはるかに「関連性の高い」組み合わせを(アドホック ヒューリスティックと比較して)リアルタイムで生成できます。その理由は2つあります。(i)各ゾーン パスは通常、複数の要求の組み合わせを表すことができます。(ii)ゾーン パスは、オフライン メソッドとオンライン メソッドの組み合わせを使用して生成されます。具体的には、ゾーンパスを採用した近視的アプローチ（現在のリクエストのみに焦点を当てたライドシェアリング割り当て）と非近視的アプローチ（ライドシェアリング割り当てが予想される将来のリクエストへの影響を考慮する）の両方を提供します。実験結果では、私たちの近視的アプローチが、実世界データセットと合成データセットの両方において、ライドシェアリングにおける現在の最良の近視的アプローチよりも優れていることを実証しました（目的と実行時間の両方において）。また、私たちの非近視的アプローチは、既存の近視的アプローチと比較して14.7%の改善を達成しました。私たちの非近視的アプローチは、最近の非近視的アプローチであるNeurADPと比較して最大12.48%の改善を達成しています。NeurADPがテスト設定で学習を最適化できるようにした場合でも、NeurADPの方が優れたパフォーマンスを発揮するいくつかのケースを除いて、結果はほぼ同等です。

Liquid Democracy: An Algorithmic Perspective

Liquid Democracy: An Algorithmic Perspective / 流動的民主主義：アルゴリズム的視点

We study liquid democracy, a collective decision making paradigm that allows voters to transitively delegate their votes, through an algorithmic lens. In our model, there are two alternatives, one correct and one incorrect, and we are interested in the probability that the majority opinion is correct. Our main question is whether there exist delegation mechanisms that are guaranteed to outperform direct voting, in the sense of being always at least as likely, and sometimes more likely, to make a correct decision. Even though we assume that voters can only delegate their votes to better-informed voters, we show that local delegation mechanisms, which only take the local neighborhood of each voter as input (and, arguably, capture the spirit of liquid democracy), cannot provide the foregoing guarantee. By contrast, we design a non-local delegation mechanism that does provably outperform direct voting under mild assumptions about voters.



我々は、投票者が推移的に投票を委任できる集団的意思決定パラダイムである液体民主主義をアルゴリズムの視点から考察します。我々のモデルでは、正しい選択肢と間違った選択肢の2つの選択肢があり、多数派の意見が正しい確率に着目します。我々の主な問いは、直接投票よりも優れた性能が保証される委任メカニズムが存在するかどうかです。つまり、常に直接投票と同等かそれ以上の確率で、時には直接投票よりも高い確率で正しい決定を下すという意味で、です。投票者はより情報に精通した投票者にのみ投票を委任できると仮定するが、各投票者の近傍情報のみを入力として取り込む（そして、おそらく液体民主主義の精神を捉えている）局所委任メカニズムは、前述の保証を提供できないことを示す。これに対し、我々は、投票者に関する軽微な仮定の下で、直接投票よりも性能が明らかに優れている非局所委任メカニズムを設計します。

Strategyproof Mechanisms for Additively Separable and Fractional Hedonic Games

Strategyproof Mechanisms for Additively Separable and Fractional Hedonic Games / 加法的に分離可能かつ分数的ヘドニックゲームのための戦略証明メカニズム

Additively separable hedonic games and fractional hedonic games have received considerable attention in the literature. They are coalition formation games among selfish agents based on their mutual preferences. Most of the work in the literature characterizes the existence and structure of stable outcomes (i.e., partitions into coalitions) assuming that preferences are given. However, there is little discussion of this assumption. In fact, agents receive different utilities if they belong to different coalitions, and thus it is natural for them to declare their preferences strategically in order to maximize their benefit. In this paper we consider strategyproof mechanisms for additively separable hedonic games and fractional hedonic games, that is, partitioning methods without payments such that utility maximizing agents have no incentive to lie about their true preferences. We focus on social welfare maximization and provide several lower and upper bounds on the performance achievable by strategyproof mechanisms for general and specific additive functions. In most of the cases we provide tight or asymptotically tight results. All our mechanisms are simple and can be run in polynomial time. Moreover, all the lower bounds are unconditional, that is, they do not rely on any computational complexity assumptions.



加法的に分離可能なヘドニックゲームと部分的ヘドニックゲームは、文献においてかなりの注目を集めています。これらは、利己的なエージェント間の相互選好に基づく連合形成ゲームです。文献研究の多くは、選好が与えられたという仮定のもと、安定的な結果（すなわち、連合への分割）の存在と構造を特徴づけています。しかし、この仮定についてはほとんど議論されていない。実際には、エージェントが異なる連合に属している場合、受け取る効用は異なるため、利益を最大化するために戦略的に選好を宣言するのは自然なことです。本稿では、加法的に分離可能なヘドニックゲームと分数的ヘドニックゲームに対する戦略的証明メカニズム、すなわち効用最大化を目指すエージェントが真の選好について嘘をつくインセンティブを持たない、支払いのない分割手法について考察します。本稿では社会厚生最大化に焦点を当て、一般および特定の加法的関数に対する戦略的証明メカニズムによって達成可能な性能の下限と上限をいくつか示す。ほとんどの場合において、タイトまたは漸近的にタイトな結果を提供します。本稿のメカニズムはすべて単純であり、多項式時間で実行可能です。さらに、すべての下限値は無条件であり、つまり、計算量に関するいかなる仮定にも依存しない。

Weighted First-Order Model Counting in the Two-Variable Fragment With Counting Quantifiers

Weighted First-Order Model Counting in the Two-Variable Fragment With Counting Quantifiers / 計数量化子を用いた2変数フラグメントにおける重み付き一次モデル計数

It is known due to the work of Van den Broeck, Meert and Darwiche that weighted first-order model counting (WFOMC) in the two-variable fragment of first-order logic can be solved in time polynomial in the number of domain elements. In this paper we extend this result to the two-variable fragment with counting quantifiers.



Van den Broeck、Meert、およびDarwicheの研究により、一階述語論理の2変数フラグメントにおける重み付き一階述語モデル計数法（WFOMC）は、ドメイン要素の数の多項式時間で解けることが知られています。本論文では、この結果を計数量指定子を含む2変数フラグメントに拡張します。

The AI Liability Puzzle and A Fund-Based Work-Around

The AI Liability Puzzle and A Fund-Based Work-Around / AI負債パズルとファンドベースの回避策

Confidence in the regulatory environment is crucial to enable responsible AI innovation and foster the social acceptance of these powerful new technologies. One notable source of uncertainty is, however, that the existing legal liability system is unable to assign responsibility where a potentially harmful conduct and/or the harm itself are unforeseeable, yet some instantiations of AI and/or the harms they may trigger are not foreseeable in the legal sense. The unpredictability of how courts would handle such cases makes the risks involved in the investment and use of AI difficult to calculate with confidence, creating an environment that is not conducive to innovation and may deprive society of some benefits AI could provide. To tackle this problem, we propose to draw insights from financial regulatory best practices and establish a system of AI guarantee schemes. We envisage the system to form part of the broader market-structuring regulatory frameworks, with the primary function to provide a readily available, clear, and transparent funding mechanism to compensate claims that are either extremely hard or impossible to realize via conventional litigation. We propose it to be at least partially industry-funded. Funding arrangements should depend on whether it would pursue other potential policy goals aimed more broadly at controlling the trajectory of AI innovation to increase economic and social welfare worldwide. Because of the global relevance of the issue, rather than focusing on any particular legal system, we trace relevant developments across multiple jurisdictions and engage in a high-level, comparative conceptual debate around the suitability of the foreseeability concept to limit legal liability. The paper also refrains from confronting the intricacies of the case law of specific jurisdictions for now and—recognizing the importance of this task—leaves this to further research in support of the legal system’s incremental adaptation to the novel challenges of present and future AI technologies.This article appears in the special track on AI and Society.



責任あるAIイノベーションを可能にし、これらの強力な新技術の社会的受容を促進するためには、規制環境への信頼が不可欠です。しかしながら、不確実性の顕著な要因の一つは、既存の法的責任制度では、潜在的に有害な行為や損害自体が予見できない場合、責任を帰属させることができないことです。しかし、AIの事例やそれが引き起こす可能性のある損害の中には、法的に予見できないものもあります。裁判所がこのような事例をどのように扱うかが予測不可能であるため、AIへの投資と利用に伴うリスクを確信を持って算定することが困難になり、イノベーションを促さない環境が生まれ、AIがもたらすはずの恩恵の一部を社会から奪う可能性があります。この問題に対処するため、私たちは金融規制のベストプラクティスから知見を得て、AI保証スキームのシステムを構築することを提案します。このシステムは、より広範な市場構造を形成する規制枠組みの一部を形成し、従来の訴訟では実現が極めて困難または不可能な請求を補償するための、容易に利用可能で、明確かつ透明性の高い資金調達メカニズムを提供することを主な機能とすることを想定しています。このシステムは、少なくとも一部は産業界からの資金提供を受けることを提案します。資金提供の取り決めは、AIイノベーションの軌道をより広範に制御し、世界中の経済的および社会的福祉を向上させることを目的とした、他の潜在的な政策目標を追求するかどうかによって決まるべきです。この問題は世界的な関連性があるため、特定の法制度に焦点を当てるのではなく、複数の法域にわたる関連する動向を追跡し、法的責任を制限するための予見可能性の概念の適切性に関する高レベルの比較概念的議論を行う。また、本論文では、現時点では特定の法域の判例法の複雑さに立ち入ることは避け、この作業の重要性を認識し、現在および将来のAI技術の新たな課題に対する法制度の段階的な適応を支援するためのさらなる研究に委ねる。この論文はAIと社会の特別トラックに掲載されています。

Instance-Level Update in DL-Lite Ontologies through First-Order Rewriting

Instance-Level Update in DL-Lite Ontologies through First-Order Rewriting / 一次書き換えによるDL-Liteオントロジーのインスタンスレベル更新

In this paper we study instance-level update in DL-LiteA , a well-known description logic that influenced the OWL 2 QL standard. Instance-level update regards insertions and deletions in the ABox of an ontology. In particular we focus on formula-based approaches to instance-level update. We show that DL-LiteA , which is well-known for enjoying first-order rewritability of query answering, enjoys a first-order rewritability property also for instance-level update. That is, every update can be reformulated into a set of insertion and deletion instructions computable through a non-recursive Datalog program with negation. Such a program is readily translatable into a first-order query over the ABox considered as a database, and hence into SQL. By exploiting this result, we implement an update component for DL-LiteA-based systems and perform some experiments showing that the approach works in practice.



本論文では、OWL 2 QL標準に影響を与えた有名な記述論理であるDL-LiteAにおけるインスタンスレベルの更新について検討します。インスタンスレベルの更新は、オントロジーのABoxにおける挿入と削除に関するものです。特に、インスタンスレベルの更新に対する数式ベースのアプローチに焦点を当てる。クエリ応答において一階書き換え可能性を持つことで知られるDL-LiteAが、インスタンスレベルの更新においても一階書き換え可能性を持つことを示す。つまり、すべての更新は、否定を含む非再帰的なDatalogプログラムによって計算可能な挿入および削除命令の集合に再定式化できます。このようなプログラムは、ABoxをデータベースと見なした一階クエリ、つまりSQLに容易に変換できます。この結果を利用して、DL-LiteAベースのシステム用の更新コンポーネントを実装し、このアプローチが実際に機能することを示す実験を行う。

Confident Learning: Estimating Uncertainty in Dataset Labels

Confident Learning: Estimating Uncertainty in Dataset Labels / 自信のある学習：データセットラベルの不確実性の推定

Learning exists in the context of data, yet notions of confidence typically focus on model predictions, not label quality. Confident learning (CL) is an alternative approach which focuses instead on label quality by characterizing and identifying label errors in datasets, based on the principles of pruning noisy data, counting with probabilistic thresholds to estimate noise, and ranking examples to train with confidence. Whereas numerous studies have developed these principles independently, here, we combine them, building on the assumption of a class-conditional noise process to directly estimate the joint distribution between noisy (given) labels and uncorrupted (unknown) labels. This results in a generalized CL which is provably consistent and experimentally performant. We present sufficient conditions where CL exactly finds label errors, and show CL performance exceeding seven recent competitive approaches for learning with noisy labels on the CIFAR dataset. Uniquely, the CL framework is not coupled to a specific data modality or model (e.g., we use CL to find several label errors in the presumed error-free MNIST dataset and improve sentiment classification on text data in Amazon Reviews). We also employ CL on ImageNet to quantify ontological class overlap (e.g., estimating 645 missile images are mislabeled as their parent class projectile), and moderately increase model accuracy (e.g., for ResNet) by cleaning data prior to training. These results are replicable using the open-source cleanlab release.



学習はデータのコンテキストで行われますが、信頼性の概念は通常、ラベルの品質ではなくモデル予測に焦点を当てています。自信学習(CL)は、ノイズの多いデータのプルーニング、ノイズを推定するための確率的閾値を使用したカウント、自信を持ってトレーニングするための例のランク付けという原則に基づいて、データセット内のラベルエラーを特徴付けて識別することにより、ラベルの品質に焦点を当てた代替アプローチです。多くの研究がこれらの原則を個別に開発してきましたが、本研究では、クラス条件付きノイズプロセスの仮定に基づいて、ノイズの多い(与えられた)ラベルと破損していない(未知の)ラベル間の結合分布を直接推定することで、それらを組み合わせます。これにより、一貫性が証明され、実験的に優れたパフォーマンスを発揮する一般化CLが得られます。CLがラベルエラーを正確に検出するための十分条件を示し、CIFARデータセットでノイズの多いラベルを学習するための最近の7つの競合アプローチを上回るCLパフォーマンスを示します。ユニークなことに、CLフレームワークは特定のデータ モダリティやモデルに結合されていません(たとえば、CLを使用して、エラーがないと想定されるMNISTデータセット内の複数のラベル エラーを検出し、Amazonレビューのテキスト データの感情分類を改善します)。また、ImageNetでCLを使用して、オントロジー クラスの重複を定量化し(たとえば、645枚のミサイル画像が親クラスのprojectileとして誤ってラベル付けされていると推定します)、トレーニング前にデータをクリーニングすることでモデルの精度を適度に向上させます(たとえば、ResNetの場合)。これらの結果は、オープンソースのcleanlabリリースを使用して再現可能です。

Aggregation over Metric Spaces: Proposing and Voting in Elections, Budgeting, and Legislation

Aggregation over Metric Spaces: Proposing and Voting in Elections, Budgeting, and Legislation / 距離空間における集約：選挙、予算編成、立法における提案と投票

We present a unifying framework encompassing a plethora of social choice settings. Viewing each social choice setting as voting in a suitable metric space, we offer a general model of social choice over metric spaces, in which—similarly to the spatial model of elections—each voter specifies an ideal element of the metric space. The ideal element acts as a vote, where each voter prefers elements that are closer to her ideal element. But it also acts as a proposal, thus making all participants equal not only as voters but also as proposers. We consider Condorcet aggregation and a continuum of solution concepts, ranging from minimizing the sum of distances to minimizing the maximum distance. We study applications of our abstract model to various social choice settings, including single-winner elections, committee elections, participatory budgeting, and participatory legislation. For each setting, we compare each solution concept to known voting rules and study various properties of the resulting voting rules. Our framework provides expressive aggregation for a broad range of social choice settings while remaining simple for voters; and may enable a unified and integrated implementation for all these settings, as well as unified extensions such as sybil-resiliency, proxy voting, and deliberative decision making.



私たちは、多数の社会的選択設定を網羅する統一的なフレームワークを提示します。それぞれの社会的選択設定を適切な計量空間での投票と見なし、計量空間での社会的選択の一般的なモデルを提供します。このモデルでは、選挙の空間モデルと同様に、各投票者が計量空間の理想的な要素を指定します。理想的な要素は投票として機能し、各投票者は自分の理想的な要素に近い要素を好みます。しかし、これは提案としても機能するため、すべての参加者は投票者としてだけでなく提案者としても平等になります。私たちはコンドルセ集約と、距離の合計の最小化から最大距離の最小化に至るまでの一連の解決策の概念を検討します。私たちは、この抽象モデルの、単独勝者選挙、委員会選挙、参加型予算編成、参加型立法など、さまざまな社会的選択設定への適用を検討します。それぞれの設定について、それぞれの解決策の概念を既知の投票ルールと比較し、結果として得られる投票ルールのさまざまな特性を検討します。私たちのフレームワークは、投票者にとってシンプルでありながら、幅広い社会的選択設定に対して表現力豊かな集約を提供します。また、これらすべての設定の統一された統合実装、およびシビルレジリエンス、代理投票、審議意思決定などの統一された拡張を可能にする可能性があります。

Efficient Retrieval of Matrix Factorization-Based Top-k Recommendations: A Survey of Recent Approaches

Efficient Retrieval of Matrix Factorization-Based Top-k Recommendations: A Survey of Recent Approaches / 行列分解に基づくTop-kレコメンデーションの効率的な取得：最近のアプローチのサーベイ

Top-k recommendation seeks to deliver a personalized list of k items to each individual user. An established methodology in the literature based on matrix factorization (MF), which usually represents users and items as vectors in low-dimensional space, is an effective approach to recommender systems, thanks to its superior performance in terms of recommendation quality and scalability. A typical matrix factorization recommender system has two main phases: preference elicitation and recommendation retrieval. The former analyzes user-generated data to learn user preferences and item characteristics in the form of latent feature vectors, whereas the latter ranks the candidate items based on the learnt vectors and returns the top-k items from the ranked list. For preference elicitation, there have been numerous works to build accurate MF-based recommendation algorithms that can learn from large datasets. However, for the recommendation retrieval phase, naively scanning a large number of items to identify the few most relevant ones may inhibit truly real-time applications. In this work, we survey recent advances and state-of-the-art approaches in the literature that enable fast and accurate retrieval for MF-based personalized recommendations. Also, we include analytical discussions of approaches along different dimensions to provide the readers with a more comprehensive understanding of the surveyed works.



Top-k推奨は、各ユーザーにk個のアイテムのパーソナライズされたリストを提供することを目指します。文献で確立されている手法の一つに、行列分解（MF）があります。これは通常、ユーザーとアイテムを低次元空間のベクトルとして表現し、推薦品質とスケーラビリティの点で優れた性能を発揮するため、推薦システムへの効果的なアプローチです。典型的な行列分解推薦システムは、選好抽出と推薦検索という2つの主要なフェーズから構成されます。前者はユーザー生成データを分析して、ユーザーの選好とアイテム特性を潜在特徴ベクトルの形で学習します。後者は、学習したベクトルに基づいて候補アイテムをランク付けし、ランク付けされたリストから上位k個のアイテムを返します。選好抽出に関しては、大規模なデータセットから学習できる高精度なMFベースの推薦アルゴリズムを構築するための研究が数多く行われてきました。しかし、推薦検索フェーズでは、多数のアイテムを単純にスキャンして最も関連性の高い少数のアイテムを特定するため、真にリアルタイムなアプリケーションを実現することが困難になる可能性があります。本研究では、MFベースのパーソナライズされた推薦を高速かつ高精度に検索することを可能にする、文献における最近の進歩と最先端のアプローチを概説します。また、読者に調査対象の研究をより包括的に理解してもらうために、さまざまな次元に沿ったアプローチの分析的な議論も盛り込んでいます。

Loss Functions, Axioms, and Peer Review

Loss Functions, Axioms, and Peer Review / 損失関数、公理、ピアレビュー

It is common to see a handful of reviewers reject a highly novel paper, because they view, say, extensive experiments as far more important than novelty, whereas the community as a whole would have embraced the paper. More generally, the disparate mapping of criteria scores to final recommendations by different reviewers is a major source of inconsistency in peer review. In this paper we present a framework inspired by empirical risk minimization (ERM) for learning the community’s aggregate mapping. The key challenge that arises is the specification of a loss function for ERM. We consider the class of L(p,q) loss functions, which is a matrix-extension of the standard class of Lp losses on vectors; here the choice of the loss function amounts to choosing the hyperparameters p and q. To deal with the absence of ground truth in our problem, we instead draw on computational social choice to identify desirable values of the hyperparameters p and q. Specifically, we characterize p=q=1 as the only choice of these hyperparameters that satisfies three natural axiomatic properties. Finally, we implement and apply our approach to reviews from IJCAI 2017.



新規性の高い論文を少数の査読者が却下するのはよくあることです。例えば、彼らは新規性よりも広範な実験をはるかに重要視するからです。しかし、コミュニティ全体ではその論文を受け入れたでしょう。より一般的には、異なる査読者による基準スコアと最終推奨のマッピングが異なることが、ピアレビューにおける不一致の大きな原因です。本稿では、コミュニティの集約マッピングを学習するための、経験的リスク最小化(ERM)に着想を得たフレームワークを紹介します。ここで生じる主要な課題は、ERMの損失関数の仕様指定です。ベクトル上のLp損失の標準クラスを行列拡張したL(p,q)損失関数のクラスを検討します。ここで、損失関数の選択は、ハイパーパラメータpとqを選択することと同義です。本問題におけるグラウンドトゥルースの不在に対処するため、代わりに計算上の社会的選択を利用して、ハイパーパラメータpとqの望ましい値を特定します。具体的には、p = q = 1が、3つの自然な公理的性質を満たすこれらのハイパーパラメータの唯一の選択肢であると特徴付けます。最後に、このアプローチを実装し、IJCAI 2017のレビューに適用します。

MADRaS : Multi Agent Driving Simulator

MADRaS : Multi Agent Driving Simulator / MADRaS：マルチエージェントドライビングシミュレーター

Autonomous driving has emerged as one of the most active areas of research as it has the promise of making transportation safer and more efficient than ever before. Most real-world autonomous driving pipelines perform perception, motion planning and action in a loop. In this work we present MADRaS, an open-source multi-agent driving simulator for use in the design and evaluation of motion planning algorithms for autonomous driving. Given a start and a goal state, the task of motion planning is to solve for a sequence of position, orientation and speed values in order to navigate between the states while adhering to safety constraints. These constraints often involve the behaviors of other agents in the environment. MADRaS provides a platform for constructing a wide variety of highway and track driving scenarios where multiple driving agents can be trained for motion planning tasks using reinforcement learning and other machine learning algorithms. MADRaS is built on TORCS, an open-source car-racing simulator. TORCS offers a variety of cars with different dynamic properties and driving tracks with different geometries and surface.  MADRaS inherits these functionalities from TORCS and introduces support for multi-agent training, inter-vehicular communication, noisy observations, stochastic actions, and custom traffic cars whose behaviors can be programmed to simulate challenging traffic conditions encountered in the real world. MADRaS can be used to create driving tasks whose complexities can be tuned along eight axes in well-defined steps. This makes it particularly suited for curriculum and continual learning. MADRaS is lightweight and it provides a convenient OpenAI Gym interface for independent control of each car. Apart from the primitive steering-acceleration-brake control mode of TORCS, MADRaS offers a hierarchical track-position – speed control mode that can potentially be used to achieve better generalization. MADRaS uses a UDP based client server model where the simulation engine is the server and each client is a driving agent. MADRaS uses multiprocessing to run each agent as a parallel process for efficiency and integrates well with popular reinforcement learning libraries like RLLib. We show experiments on single and multi-agent reinforcement learning with and without curriculum



自動運転は、交通をこれまで以上に安全で効率的にする可能性を秘めているため、最も活発な研究分野の一つとして浮上しています。現実世界の自動運転パイプラインのほとんどは、認識、動作計画、行動をループで実行しています。本研究では、自動運転の動作計画アルゴリズムの設計と評価に使用できるオープンソースのマルチエージェント・ドライビング・シミュレータであるMADRaSを紹介します。動作計画のタスクは、開始状態と目標状態が与えられた場合、安全制約を遵守しながら状態間を移動するために、位置、方向、速度の一連の値を解くことです。これらの制約には、多くの場合、環境内の他のエージェントの行動が含まれます。MADRaSは、強化学習やその他の機械学習アルゴリズムを用いて複数の運転エージェントを動作計画タスク用にトレーニングできる、高速道路やトラックのさまざまな運転シナリオを構築するためのプラットフォームを提供します。MADRaSは、オープンソースのカーレースシミュレーターであるTORCSをベースに構築されています。TORCSは、異なる動的特性を持つ様々な車と、異なる形状や路面の走行トラックを提供しています。MADRaSはTORCSからこれらの機能を継承し、マルチエージェントトレーニング、車車間通信、ノイズ観測、確率的アクション、そして現実世界で遭遇する困難な交通状況をシミュレートするように動作をプログラムできるカスタム交通車のサポートを導入しています。MADRaSを使用すると、明確に定義されたステップで8軸に沿って複雑さを調整できる運転タスクを作成できます。そのため、カリキュラムや継続的な学習に特に適しています。MADRaSは軽量で、各車を独立して制御するための便利なOpenAI Gymインターフェースを提供しています。TORCSの基本的なステアリング、加速、ブレーキ制御モードとは別に、MADRaSは階層的なトラック位置 – 速度制御モードを提供しており、これを使用してより優れた一般化を実現できる可能性があります。MADRaSはUDPベースのクライアントサーバーモデルを採用しており、シミュレーションエンジンがサーバー、各クライアントが駆動エージェントとして機能します。MADRaSはマルチプロセッシングを用いて各エージェントを並列プロセスとして実行することで効率性を高め、RLLibなどの一般的な強化学習ライブラリと連携します。カリキュラムの有無によるシングルエージェントおよびマルチエージェント強化学習の実験を紹介します。

Labeled Bipolar Argumentation Frameworks

Labeled Bipolar Argumentation Frameworks / ラベル付き双極性議論フレームワーク

An essential part of argumentation-based reasoning is to identify arguments in favor and against a statement or query, select the acceptable ones, and then determine whether or not the original statement should be accepted. We present here an abstract framework that considers two independent forms of argument interaction—support and conflict—and is able to represent distinctive information associated with these arguments. This information can enable additional actions such as: (i) a more in-depth analysis of the relations between the arguments; (ii) a representation of the user’s posture to help in focusing the argumentative process, optimizing the values of attributes associated with certain arguments; and (iii) an enhancement of the semantics taking advantage of the availability of richer information about argument acceptability. Thus, the classical semantic definitions are enhanced by analyzing a set of postulates they satisfy. Finally, a polynomial-time algorithm to perform the labeling process is introduced, in which the argument interactions are considered.



議論に基づく推論の重要な部分は、ある文またはクエリに対する賛成論と反対論を特定し、受け入れ可能なものを選択し、元の文を受け入れるべきかどうかを判断することです。本稿では、支持と対立という2つの独立した議論の相互作用を考慮し、これらの議論に関連する明確な情報を表現できる抽象的なフレームワークを提示します。この情報により、(i)議論間の関係のより詳細な分析、(ii)議論プロセスの焦点を絞り、特定の議論に関連する属性の値を最適化するためのユーザーの姿勢の表現、(iii)議論の受け入れ可能性に関するより豊富な情報の利用を活用した意味の拡張といった追加アクションが可能になります。このように、従来の意味定義は、それらが満たす公理の集合を分析することによって強化されます。最後に、議論の相互作用を考慮したラベル付けプロセスを実行する多項式時間アルゴリズムを導入します。

Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics

Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics / コスト最適計画、削除緩和、近似可能性、およびヒューリスティック

Cost-optimal planning is a very well-studied topic within planning, and it has proven to be computationally hard both in theory and in practice. Since cost-optimal planning is an optimisation problem, it is natural to analyse it through the lens of approximation. An important reason for studying cost-optimal planning is heuristic search; heuristic functions that guide the search in planning can often be viewed as algorithms solving or approximating certain optimisation problems. Many heuristic functions (such as the ubiquitious h+ heuristic) are based on delete relaxation, which ignores negative effects of actions. Planning for instances where the actions have no negative effects is often referred to as monotone planning. The aim of this article is to analyse the approximability of cost-optimal monotone planning, and thus the performance of relevant heuristic functions. Our findings imply that it may be beneficial to study these kind of problems within the framework of parameterised complexity and we initiate work in this direction.



コスト最適計画は、計画において非常によく研究されているトピックであり、理論と実践の両方において計算的に困難であることが証明されています。コスト最適計画は最適化問題であるため、近似の観点から分析するのが自然です。コスト最適計画を研究する重要な理由の1つは、ヒューリスティック探索です。計画における探索を導くヒューリスティック関数は、多くの場合、特定の最適化問題を解決または近似するアルゴリズムと見なすことができます。多くのヒューリスティック関数（広く使用されているh+ヒューリスティックなど）は、アクションの悪影響を無視する削除緩和に基づいています。アクションが悪影響を持たないインスタンスの計画は、しばしば単調計画と呼ばれます。本稿の目的は、コスト最適単調計画の近似可能性、ひいては関連するヒューリスティック関数のパフォーマンスを分析することです。私たちの研究結果は、この種の問題をパラメータ化された複雑性の枠組みの中で研究することが有益である可能性があることを示唆しており、私たちはこの方向で研究を開始します。

Learning Temporal Causal Sequence Relationships from Real-Time Time-Series

Learning Temporal Causal Sequence Relationships from Real-Time Time-Series / リアルタイム時系列からの時系列因果関係の学習

We aim to mine temporal causal sequences that explain observed events (consequents) in time-series traces. Causal explanations of key events in a time-series have applications in design debugging, anomaly detection, planning, root-cause analysis and many more. We make use of decision trees and interval arithmetic to mine sequences that explain defining events in the time-series. We propose modified decision tree construction metrics to handle the non-determinism introduced by the temporal dimension. The mined sequences are expressed in a readable temporal logic language that is easy to interpret. The application of the proposed methodology is illustrated through various examples.



私たちは、時系列トレースで観測されたイベント（結果）を説明する時間的な因果シーケンスをマイニングすることを目指しています。時系列における主要なイベントの因果的説明は、設計デバッグ、異常検出、計画、根本原因分析など、様々な分野に応用できます。本研究では、決定木と区間演算を用いて、時系列における決定的なイベントを説明するシーケンスをマイニングします。時間軸によって生じる非決定性に対処するため、修正された決定木構築メトリクスを提案します。マイニングされたシーケンスは、読みやすく解釈しやすい時相論理言語で表現されます。提案手法の適用例を様々な例を用いて示します。

A Survey on the Explainability of Supervised Machine Learning

A Survey on the Explainability of Supervised Machine Learning / 教師あり機械学習の説明可能性に関するサーベイ

Predictions obtained by, e.g., artificial neural networks have a high accuracy but humans often perceive the models as black boxes. Insights about the decision making are mostly opaque for humans. Particularly understanding the decision making in highly sensitive areas such as healthcare or finance, is of paramount importance. The decision-making behind the black boxes requires it to be more transparent, accountable, and understandable for humans. This survey paper provides essential definitions, an overview of the different principles and methodologies of explainable Supervised Machine Learning (SML). We conduct a state-of-the-art survey that reviews past and recent explainable SML approaches and classifies them according to the introduced definitions. Finally, we illustrate principles by means of an explanatory case study and discuss important future directions.



例えば人工ニューラルネットワークによって得られる予測は高精度ですが、人間はしばしばそのモデルをブラックボックスとして認識します。意思決定に関する洞察は、人間にとってほとんど不透明です。特に、医療や金融などの非常に機密性の高い分野における意思決定を理解することは極めて重要です。ブラックボックスの背後にある意思決定は、人間にとってより透明性が高く、説明責任があり、理解可能である必要があります。この調査論文では、説明可能な教師あり機械学習（SML）の基本的な定義、さまざまな原則と方法論の概要を提供します。私たちは最先端の調査を実施し、過去と最近の説明可能なSMLアプローチをレビューし、導入された定義に従ってそれらを分類します。最後に、説明的なケーススタディによって原則を示し、重要な将来の方向性について議論します。

Efficient Multi-objective Reinforcement Learning via Multiple-gradient Descent with Iteratively Discovered Weight-Vector Sets

Efficient Multi-objective Reinforcement Learning via Multiple-gradient Descent with Iteratively Discovered Weight-Vector Sets / 反復的に発見される重みベクトルセットを用いた多重勾配降下法による効率的な多目的強化学習

Solving multi-objective optimization problems is important in various applications where users are interested in obtaining optimal policies subject to multiple (yet often conflicting) objectives. A typical approach to obtain the optimal policies is to first construct a loss function based on the scalarization of individual objectives and then derive optimal policies that minimize the scalarized loss function. Albeit simple and efficient, the typical approach provides no insights/mechanisms on the optimization of multiple objectives due to the lack of ability to quantify the inter-objective relationship. To address the issue, we propose to develop a new efficient gradient-based multi-objective reinforcement learning approach that seeks to iteratively uncover the quantitative inter-objective relationship via finding a minimum-norm point in the convex hull of the set of multiple policy gradients when the impact of one objective on others is unknown a priori. In particular, we first propose a new PAOLS algorithm that integrates pruning and approximate optimistic linear support algorithm to efficiently discover the weight-vector sets of multiple gradients that quantify the inter-objective relationship. Then we construct an actor and a multi-objective critic that can co-learn the policy and the multi-objective vector value function. Finally, the weight discovery process and the policy and vector value function learning process can be iteratively executed to yield stable weight-vector sets and policies. To validate the effectiveness of the proposed approach, we present a quantitative evaluation of the approach based on three case studies.



多目的最適化問題を解くことは、ユーザーが複数の（しかししばしば矛盾する）目的を条件として最適なポリシーを取得することに関心があるさまざまなアプリケーションで重要です。最適な方策を得るための典型的なアプローチは、まず個々の目的関数のスカラー化に基づいて損失関数を構築し、次にスカラー化された損失関数を最小化する最適な方策を導出することです。この典型的なアプローチは単純かつ効率的ですが、目的関数間の関係を定量化できないため、複数の目的関数の最適化に関する知見やメカニズムを提供しません。この問題に対処するため、本研究では、ある目的関数が他の目的関数に与える影響が事前に不明な場合に、複数の方策勾配集合の凸包における最小ノルム点を求めることで、定量的な目的関数間の関係を反復的に解明しようとする、効率的な勾配ベースの多目的強化学習手法の開発を提案します。具体的には、まず、枝刈りと近似楽観線形サポートアルゴリズムを統合した新しいPAOLSアルゴリズムを提案し、目的関数間の関係を定量化する複数の勾配の重みベクトル集合を効率的に発見します。次に、方策と多目的ベクトル値関数を共学習できるアクターと多目的クリティックを構築します。最後に、重み発見プロセスと方策およびベクトル値関数の学習プロセスを反復的に実行することで、安定した重みベクトル集合と方策が得られます。提案手法の有効性を検証するために、3つのケーススタディに基づく定量的な評価を示します。

The Computational Complexity of Understanding Binary Classifier Decisions

The Computational Complexity of Understanding Binary Classifier Decisions / バイナリ分類器の決定を理解するための計算複雑性

For a d-ary Boolean function Φ: {0, 1}d → {0, 1} and an assignment to its variables x = (x1, x2, . . . , xd) we consider the problem of finding those subsets of the variables that are sufficient to determine the function value with a given probability δ. This is motivated by the task of interpreting predictions of binary classifiers described as Boolean circuits, which can be seen as special cases of neural networks. We show that the problem of deciding whether such subsets of relevant variables of limited size k ≤ d exist is complete for the complexity class NPPP and thus, generally, unfeasible to solve. We then introduce a variant, in which it suffices to check whether a subset determines the function value with probability at least δ or at most δ − γ for 0 < γ < δ. This promise of a probability gap reduces the complexity to the class NPBPP. Finally, we show that finding the minimal set of relevant variables cannot be reasonably approximated, i.e. with an approximation factor d1−α for α > 0, by a polynomial time algorithm unless P = NP. This holds even with the promise of a probability gap.



d元ブール関数 Φ: {0, 1}d→{0, 1}とその変数への割り当てx = (x1, x2, . . . , xd)について、与えられた確率 δ で関数値を決定するのに十分な変数のサブセットを見つける問題を考察します。これは、ニューラル ネットワークの特殊なケースと見なすことができるブール回路として記述された2値分類器の予測を解釈するというタスクに動機付けられています。限られたサイズk≤dの関連変数のサブセットが存在するかどうかを判断する問題は、複雑性クラスNPPPに対して完全であり、したがって一般に解決不可能であることを示します。次に、サブセットが関数値を少なくとも δ または最大で δ − γ(0 <γ<δ)の確率で決定するかどうかをチェックするだけで十分なバリエーションを導入します。最後に、P = NPでない限り、関連する変数の最小セットを見つけることは、近似係数d1−α（α> 0の場合）で多項式時間アルゴリズムによって合理的に近似できないことを示します。これは、確率ギャップが期待される場合でも当てはまります。

Hybrid-order Network Consensus for Distributed Multi-agent Systems

Hybrid-order Network Consensus for Distributed Multi-agent Systems / 分散マルチエージェントのためのハイブリッド順序ネットワークコンセンサスシステム

As an important field of Distributed artificial intelligence (DAI), multi-agent systems (MASs) have attracted the attention of extensive research scholars. Consensus as the most important issue in MAS, much progress has been made in studying the consensus control of MAS, but there are some problems remained largely unaddressed which cause the MAS to lose some useful network structure information. First, multi-agent consensus protocol usually proceeds over the low-order structure by only considering the direct edges between agents, but ignores the higher-order structure of the whole topology network. Second, the existing work assumes all the edges in a topology network have the same weight without exploring the potential diversity of the connections. In this way, multi-agent systems fail to enforce consensus, resulting in fragmentation into multiple clusters. To address the above issues, this paper proposes a Motif-aware Weighted Multi-agent System (MWMS) method for consensus control. We focus more on triangle motif in the network, but it can be extended to other kinds of motifs as well. First, a novel weighted network is used which is the combination of the edge-based lower-order structure and the motif-based higher-order structure, i.e., hybrid-order structure. Subsequently, by simultaneously considering the quantity and the quality of the connections in the network, a novel consensus framework for MAS is designed to update agents. Then, two baseline consensus algorithms are used in MWMS. In our experiments, we use ten topologies of different shapes, densities and ranges to comprehensively analyze the performance of our proposed algorithms. The simulation results show that the hybrid higher-order network can effectively enhance the consensus of the multi-agent system in different network topologies.



分散型人工知能（DAI）の重要な分野として、マルチエージェントシステム（MAS）は幅広い研究者の注目を集めています。MASにおける最も重要な問題としてのコンセンサスとして、MASのコンセンサス制御の研究は大きく進歩しましたが、MASが有用なネットワーク構造情報の一部を失う原因となるいくつかの問題がまだほとんど解決されていません。第一に、マルチエージェントコンセンサスプロトコルは通常、エージェント間の直接のエッジのみを考慮して低次構造上を進みますが、トポロジネットワーク全体の高次構造は無視します。第二に、既存の研究では、トポロジネットワーク内のすべてのエッジの重みが同じであると仮定していますが、接続の潜在的な多様性を探索していません。このように、マルチエージェントシステムはコンセンサスを強制できず、複数のクラスターへの断片化が発生します。上記の問題に対処するため、本稿では、合意形成制御のためのモチーフを考慮した重み付きマルチエージェントシステム（MWMS）手法を提案します。本稿ではネットワーク内の三角形モチーフに焦点を当てるが、他の種類のモチーフにも拡張できます。まず、エッジベースの低階構造とモチーフベースの高階構造（ハイブリッド構造）を組み合わせた新しい重み付きネットワークを採用します。次に、ネットワーク内の接続の量と質を同時に考慮することで、エージェントを更新するための新しいMASコンセンサスフレームワークを設計します。次に、MWMSで2つのベースラインコンセンサスアルゴリズムを使用します。実験では、形状、密度、範囲が異なる10種類のトポロジを使用して、提案アルゴリズムの性能を包括的に分析します。シミュレーション結果は、ハイブリッド高階ネットワークが、さまざまなネットワークトポロジにおけるマルチエージェントシステムの合意形成を効果的に強化できることを示しています。

Benchmark and Survey of Automated Machine Learning Frameworks

Benchmark and Survey of Automated Machine Learning Frameworks / 自動化機械学習フレームワークのベンチマークと調査

Machine learning (ML) has become a vital part in many aspects of our daily life. However, building well performing machine learning applications requires highly specialized data scientists and domain experts. Automated machine learning (AutoML) aims to reduce the demand for data scientists by enabling domain experts to build machine learning applications automatically without extensive knowledge of statistics and machine learning. This paper is a combination of a survey on current AutoML methods and a benchmark of popular AutoML frameworks on real data sets. Driven by the selected frameworks for evaluation, we summarize and review important AutoML techniques and methods concerning every step in building an ML pipeline. The selected AutoML frameworks are evaluated on 137 data sets from established AutoML benchmark suites.



機械学習（ML）は、私たちの日常生活の多くの側面で不可欠な部分となっています。しかし、優れたパフォーマンスを発揮する機械学習アプリケーションを構築するには、高度に専門化されたデータサイエンティストとドメインエキスパートが必要です。自動機械学習（AutoML）は、ドメインエキスパートが統計や機械学習に関する高度な知識を必要とせずに機械学習アプリケーションを自動構築できるようにすることで、データサイエンティストの需要を軽減することを目指しています。本稿は、現在のAutoML手法に関する調査と、実データセットを用いた一般的なAutoMLフレームワークのベンチマークを組み合わせたものです。評価対象として選定したフレームワークに基づき、MLパイプライン構築のあらゆるステップに関わる重要なAutoMLの技術と手法をまとめ、レビューします。選定したAutoMLフレームワークは、確立されたAutoMLベンチマークスイートから137のデータセットで評価されます。

On Super Strong ETH

On Super Strong ETH / 超強力ETHについて

Multiple known algorithmic paradigms (backtracking, local search and the polynomial method) only yield a 2n(1-1/O(k)) time algorithm for k-SAT in the worst case. For this reason, it has been hypothesized that the worst-case k-SAT problem cannot be solved in 2n(1-f(k)/k) time for any unbounded function f. This hypothesis has been called the “Super-Strong ETH”, modelled after the ETH and the Strong ETH.It has also been hypothesized that k-SAT is hard to solve for randomly chosen instances near the “critical threshold”, where the clause-to-variable ratio is such that randomly chosen instances are satisfiable with probability 1/2. We give a randomized algorithm which refutes the Super-Strong ETH for the case of random k-SAT and planted k-SAT for any clause-to-variable ratio. For example, given any random k-SAT instance F with n variables and m clauses, our algorithm decides satisfiability for F in  2n(1-c*log(k)/k) time with high probability (over the choice of the formula and the randomness of the algorithm). It turns out that a well-known algorithm from the literature on SAT algorithms does the job: the PPZ algorithm of Paturi, Pudlak, and Zane (1999).  The Unique k-SAT problem is the special case where there is at most one satisfying assignment. Improving prior reductions, we show that the Super-Strong ETHs for Unique k-SAT and k-SAT are equivalent. More precisely, we show the time complexities of Unique k-SAT and k-SAT are very tightly correlated: if Unique k-SAT is in  2n(1-f(k)/k) time for an unbounded f, then k-SAT is in 2n(1-f(k)/(2k)) time.



複数の既知のアルゴリズムパラダイム（バックトラッキング、局所探索、多項式法）は、最悪のケースにおいてk-SATの2n(1-1/O(k))時間アルゴリズムしか生成しません。このため、最悪のケースのk-SAT問題は、任意の非有界関数fに対して2n(1-f(k)/k)時間で解くことができないという仮説が立てられています。この仮説は、ETHとStrong ETHをモデルに「Super-Strong ETH」と呼ばれています。また、節対変数比が1/2の確率で充足可能な「臨界閾値」付近のランダムに選択されたインスタンスに対しては、k-SATを解くのが困難であるという仮説も立てられています。本稿では、ランダムk-SATと任意の節対変数比のプラントk-SATにおいて、Super-Strong ETHを反証するランダム化アルゴリズムを提示します。例えば、n個の変数とm個の節を持つ任意のランダムk-SATインスタンスFが与えられた場合、私たちのアルゴリズムは、（式の選択とアルゴリズムのランダム性に関係なく）2n（1-c*log(k)/k）時間でFの充足可能性を高い確率で決定します。SATアルゴリズムの文献にあるよく知られたアルゴリズム、Paturi、Pudlak、Zane（1999）によるPPZアルゴリズムがこの役割を果たすことがわかります。ユニークk-SAT問題は、満たされる割り当てが最大で1つしかない特殊なケースです。事前縮小を改善することで、ユニークk-SATとk-SATのスーパーストロングETHが同等であることを示します。より正確には、Unique k-SATとk-SATの時間計算量は非常に密接に相関していることを示します。つまり、Unique k-SATが無制限のfに対して2n(1-f(k)/k)時間である場合、k-SATは2n(1-f(k)/(2k))時間です。

General Value Function Networks

General Value Function Networks / 一般価値関数ネットワーク

State construction is important for learning in partially observable environments. A general purpose strategy for state construction is to learn the state update using a Recurrent Neural Network (RNN), which updates the internal state using the current internal state and the most recent observation. This internal state provides a summary of the observed sequence, to facilitate accurate predictions and decision-making. At the same time, specifying and training RNNs is notoriously tricky, particularly as the common strategy to approximate gradients back in time, called truncated Back-prop Through Time (BPTT), can be sensitive to the truncation window. Further, domain-expertise—which can usually help constrain the function class and so improve trainability—can be difficult to incorporate into complex recurrent units used within RNNs. In this work, we explore how to use multi-step predictions to constrain the RNN and incorporate prior knowledge. In particular, we revisit the idea of using predictions to construct state and ask: does constraining (parts of) the state to consist of predictions about the future improve RNN trainability? We formulate a novel RNN architecture, called a General Value Function Network (GVFN), where each internal state component corresponds to a prediction about the future represented as a value function. We first provide an objective for optimizing GVFNs, and derive several algorithms to optimize this objective. We then show that GVFNs are more robust to the truncation level, in many cases only requiring one-step gradient updates.



状態構築は、部分的に観測可能な環境での学習にとって重要です。状態構築の一般的な戦略は、現在の内部状態と最新の観測を使用して内部状態を更新するリカレント ニューラル ネットワーク(RNN)を使用して状態更新を学習することです。この内部状態は観測されたシーケンスの要約を提供し、正確な予測と意思決定を容易にします。同時に、RNNの指定とトレーニングは非常に難しいことで有名です。特に、勾配を過去にさかのぼって近似する一般的な戦略であるtruncated Back-prop Through Time (BPTT)は、切り捨てウィンドウの影響を受けやすいためです。さらに、通常は関数クラスの制約に役立ち、学習可能性を向上させるドメイン専門知識は、RNN内で使用される複雑な再帰ユニットに組み込むのが難しい場合があります。本研究では、多段階予測を使用してRNNを制約し、事前知識を組み込む方法を検討します。特に、予測を使用して状態を構築するというアイデアを再検討し、状態（の一部）を未来の予測で構成されるように制約すると、RNNの学習可能性が向上するかどうかを問います。私たちは、一般価値関数ネットワーク(GVFN)と呼ばれる新しいRNNアーキテクチャを定式化します。このアーキテクチャでは、各内部状態コンポーネントが、価値関数として表される未来の予測に対応します。まず、GVFNを最適化するための目的関数を提供し、この目的関数を最適化するためのいくつかのアルゴリズムを導出します。次に、GVFNは切り捨てレベルに対してより堅牢であり、多くの場合、1段階の勾配更新のみを必要とすることを示します。

An External Knowledge Enhanced Graph-based Neural Network for Sentence Ordering

An External Knowledge Enhanced Graph-based Neural Network for Sentence Ordering / 文順序付けのための外部知識強化グラフベースニューラルネットワーク

As an important text coherence modeling task, sentence ordering aims to coherently organize a given set of unordered sentences. To achieve this goal, the most important step is to effectively capture and exploit global dependencies among these sentences. In this paper, we propose a novel and flexible external knowledge enhanced graph-based neural network for sentence ordering. Specifically, we first represent the input sentences as a graph, where various kinds of relations (i.e., entity-entity, sentence-sentence and entity-sentence) are exploited to make the graph representation more expressive and less noisy. Then, we introduce graph recurrent network to learn semantic representations of the sentences. To demonstrate the effectiveness of our model, we conduct experiments on several benchmark datasets. The experimental results and in-depth analysis show our model significantly outperforms the existing state-of-the-art models.



重要なテキスト一貫性モデリングタスクとして、文の順序付けは、順序付けられていない文の集合を首尾一貫して整理することを目的としています。この目標を達成するために最も重要なステップは、これらの文間のグローバルな依存関係を効果的に捕捉し、活用することです。本稿では、文の順序付けのための、新しく柔軟な外部知識強化グラフベースニューラルネットワークを提案します。具体的には、まず入力文をグラフとして表現し、様々な関係（エンティティ-エンティティ、文-文、エンティティ-文）を活用することで、グラフ表現の表現力を高め、ノイズを低減します。次に、グラフリカレントネットワークを導入し、文の意味表現を学習します。このモデルの有効性を実証するために、いくつかのベンチマークデータセットで実験を行いました。実験結果と詳細な分析から、このモデルが既存の最先端モデルを大幅に上回る性能を示すことが示されました。

On the Distortion Value of Elections with Abstention

On the Distortion Value of Elections with Abstention / 棄権を伴う選挙の歪み値について

In Spatial Voting Theory, distortion is a measure of how good the winner is. It has been proved that no deterministic voting mechanism can guarantee a distortion better than 3, even for simple metrics such as a line. In this study, we wish to answer the following question: how does the distortion value change if we allow less motivated agents to abstain from the election?We consider an election with two candidates and suggest an abstention model, which is a general form of the abstention model proposed by Kirchgässner. Our results characterize the distortion ¨ value and provide a rather complete picture of the model.



空間投票理論において、歪みは勝者の優秀さを示す尺度です。線のような単純な指標であっても、決定論的な投票メカニズムでは3よりも良い歪みを保証することはできないことが証明されています。本研究では、次の疑問に答えます。選挙への意欲が低いエージェントが棄権することを許可した場合、歪み値はどのように変化するのでしょうか？候補者が2人いる選挙を考察し、キルヒゲスナーが提案した棄権モデルの一般形である棄権モデルを提案します。私たちの結果は歪み¨値を特徴づけ、モデルのより完全な全体像を提供します。

Generic Constraint-based Block Modeling using Constraint Programming

Generic Constraint-based Block Modeling using Constraint Programming / 制約プログラミングを用いた汎用制約ベースブロックモデリング

Block modeling has been used extensively in many domains including social science, spatial temporal data analysis and even medical imaging. Original formulations of the problem modeled it as a mixed integer programming problem, but were not scalable. Subsequent work relaxed the discrete optimization requirement, and showed that adding constraints is not straightforward in existing approaches. In this work, we present a new approach based on constraint programming, allowing discrete optimization of block modeling in a manner that is not only scalable, but also allows the easy incorporation of constraints. We introduce a new constraint filtering algorithm that outperforms earlier approaches, in both constrained and unconstrained settings, for an exhaustive search and for a type of local search called Large Neighborhood Search. We show its use in the analysis of real datasets. Finally, we show an application of the CP framework for model selection using the Minimum Description Length principle.



ブロックモデリングは、社会科学、時空間データ分析、さらには医療画像など、多くの分野で広く使用されています。この問題の当初の定式化では、混合整数計画問題としてモデル化されていましたが、スケーラブルではありませんでした。その後の研究では、離散最適化の要件が緩和され、既存のアプローチでは制約を追加することが簡単ではないことが示されました。本研究では、制約プログラミングに基づく新しいアプローチを提示します。このアプローチは、スケーラブルなだけでなく、制約を容易に組み込むことができる方法で、ブロックモデリングの離散最適化を可能にします。制約付きと制約なしの両方の設定において、網羅的探索と大規模近傍探索と呼ばれる一種の局所探索において、従来のアプローチよりも優れた性能を発揮する新しい制約フィルタリングアルゴリズムを紹介します。実際のデータセットの分析におけるその使用法を示します。最後に、最小記述長原理を用いたモデル選択のためのCPフレームワークの適用例を示します。

Regarding Goal Bounding and Jump Point Search

Regarding Goal Bounding and Jump Point Search / 目標境界設定とジャンプポイント探索について

Jump Point Search (JPS) is a well known symmetry-breaking algorithm that can substantially improve performance for grid-based optimal pathfinding. When the input grid is static further speedups can be obtained by combining JPS with goal bounding techniques such as Geometric Containers (instantiated as Bounding Boxes) and Compressed Path Databases. Two such methods, JPS+BB and Two-Oracle Path PlannING (Topping), are currently among the fastest known approaches for computing shortest paths on grids. The principal drawback for these algorithms is the overhead costs: each one requires an all-pairs precomputation step, the running time and subsequent storage costs of which can be prohibitive. In this work we consider an alternative approach where we precompute and store goal bounding data only for grid cells which are also jump points. Since the number of jump points is usually much smaller than the total number of grid cells, we can save up to orders of magnitude in preprocessing time and space.Considerable precomputation savings do not necessarily mean performance degradation. For a second contribution we show how canonical orderings, partial expansion strategies and enhanced intermediate pruning can be leveraged to improve online query performance despite a reduction in preprocessed data. The combination of faster preprocessing and stronger online reasoning leads to three new and highly performant algorithms: JPS+BB+ and Two-Oracle Pathfinding Search (TOPS) based on search, and Topping+ based on path extraction. We give a theoretical analysis showing that each method is complete and optimal. We also report convincing gains in a comprehensive empirical evaluation that includes almost all current and cutting-edge algorithms for grid-based pathfinding.



ジャンプポイント探索（JPS）は、グリッドベースの最適経路探索のパフォーマンスを大幅に向上させることができる、よく知られた対称性破壊アルゴリズムです。入力グリッドが静的な場合、JPSを幾何学的コンテナ（バウンディングボックスとしてインスタンス化）や圧縮パスデータベースなどの目標境界設定手法と組み合わせることで、さらなる高速化を実現できます。JPS+BBとTwo-Oracle Path PlannING (Topping)という2つの方法は、現在、グリッド上の最短経路を計算する既知のアプローチの中で最も高速なものの1つです。これらのアルゴリズムの主な欠点は、オーバーヘッド コストです。それぞれが全ペアの事前計算ステップを必要とし、実行時間とその後のストレージ コストが法外に高くなる可能性があります。この研究では、ジャンプ ポイントでもあるグリッド セルに対してのみゴール境界データを事前計算して保存する代替アプローチを検討します。ジャンプ ポイントの数は、通常、グリッド セルの総数よりもはるかに少ないため、事前処理の時間と領域を桁違いに節約できます。事前計算による大幅な節約は、必ずしもパフォーマンスの低下を意味するものではありません。2つ目の貢献として、標準順序付け、部分的拡張戦略、および強化された中間プルーニングを活用して、事前処理されたデータが減少したにもかかわらず、オンライン クエリのパフォーマンスを向上させる方法を示します。高速な前処理と強力なオンライン推論の組み合わせにより、3つの新しい高性能アルゴリズムが生まれました。探索に基づくJPS+BB+とTwo-Oracle Pathfinding Search (TOPS)、そして経路抽出に基づくTopping+です。各手法が完全かつ最適であることを示す理論分析を提供します。また、グリッドベースの経路探索におけるほぼすべての最新アルゴリズムを含む包括的な実証評価において、説得力のある成果が得られました。

Superintelligence Cannot be Contained: Lessons from Computability Theory

Superintelligence Cannot be Contained: Lessons from Computability Theory / 超知能は封じ込められない：計算可能性理論からの教訓

Superintelligence is a hypothetical agent that possesses intelligence far surpassing that of the brightest and most gifted human minds. In light of recent advances in machine intelligence, a number of scientists, philosophers and technologists have revived the discussion about the potentially catastrophic risks entailed by such an entity. In this article, we trace the origins and development of the neo-fear of superintelligence, and some of the major proposals for its containment. We argue that total containment is, in principle, impossible, due to fundamental limits inherent to computing itself. Assuming that a superintelligence will contain a program that includes all the programs that can be executed by a universal Turing machine on input potentially as complex as the state of the world, strict containment requires simulations of such a program, something theoretically (and practically) impossible.This article is part of the special track on AI and Society.



超知能とは、最も聡明で才能豊かな人間の知能をはるかに凌駕する知能を持つ仮想的な存在です。近年の機械知能の進歩を受け、多くの科学者、哲学者、技術者が、そのような存在がもたらす潜在的に壊滅的なリスクについての議論を再び活発化させています。本稿では、超知能に対する新たな恐怖の起源と発展、そしてその封じ込めに向けた主要な提案のいくつかを辿る。我々は、コンピューティングそのものに内在する根本的な限界のため、完全な封じ込めは原理的に不可能であると主張します。超知能が、世界の状態と同じくらい複雑な入力に対して汎用チューリングマシンが実行できるすべてのプログラムを含むプログラムを含むと仮定すると、厳密な封じ込めにはそのようなプログラムのシミュレーションが必要となり、これは理論的にも（そして実際的にも）不可能です。本稿はAIと社会に関する特別トラックの一部です。

Classifier Chains: A Review and Perspectives

Classifier Chains: A Review and Perspectives / 分類器連鎖：レビューと展望

The family of methods collectively known as classifier chains has become a popular approach to multi-label learning problems. This approach involves chaining together off-the-shelf binary classifiers in a directed structure, such that individual label predictions become features for other classifiers. Such methods have proved flexible and effective and have obtained state-of-the-art empirical performance across many datasets and multi-label evaluation metrics. This performance led to further studies of the underlying mechanism and efficacy, and investigation into how it could be improved. In the recent decade, numerous studies have explored the theoretical underpinnings of classifier chains, and many improvements have been made to the training and inference procedures, such that this method remains among the best options for multi-label learning. Given this past and ongoing interest, which covers a broad range of applications and research themes, the goal of this work is to provide a review of classifier chains, a survey of the techniques and extensions provided in the literature, as well as perspectives for this approach in the domain of multi-label classification in the future. We conclude positively, with a number of recommendations for researchers and practitioners, as well as outlining key issues for future research.



分類器連鎖として総称される一連の手法は、マルチラベル学習問題に対する一般的なアプローチとなっています。このアプローチでは、既製の2値分類器を有向構造で連鎖させ、個々のラベル予測が他の分類器の特徴となるようにします。この手法は柔軟かつ効果的であることが証明されており、多くのデータセットとマルチラベル評価指標において最先端の実証的性能を達成しています。この性能は、その根底にあるメカニズムと有効性に関する更なる研究、そして改善方法の調査につながりました。ここ10年間、分類器連鎖の理論的根拠を探る研究が数多く行われ、学習および推論手順にも多くの改良が加えられてきました。その結果、この手法はマルチラベル学習における最良の選択肢の一つとなっています。幅広い応用分野と研究テーマを網羅するこの過去および継続的な関心を踏まえ、本研究の目的は、分類器連鎖のレビュー、文献で提示された手法と拡張のサーベイ、そしてマルチラベル分類分野におけるこのアプローチの将来展望を示すことです。本稿では、研究者と実務家への提言をいくつか提示し、今後の研究における主要な課題を概説することで、肯定的な結論を導きます。

Two-facility Location Games with Minimum Distance Requirement

Two-facility Location Games with Minimum Distance Requirement / 最小距離要件を伴う2施設ロケーションゲーム

We study the mechanism design problem of a social planner for locating two facilities on a line interval [0, 1], where a set of n strategic agents report their locations and a mechanism determines the locations of the two facilities. We consider the requirement of a minimum distance 0 ≤ d ≤ 1 between the two facilities. Given the two facilities are heterogeneous, we model the cost/utility of an agent as the sum of his distances to both facilities. In the heterogeneous two-facility location game to minimize the social cost, we show that the optimal solution can be computed in polynomial time and prove that carefully choosing one optimal solution as output is strategyproof. We also design a strategyproof mechanism minimizing the maximum cost. Given the two facilities are homogeneous, we model the cost/utility of an agent as his distance to the closer facility. In the homogeneous two-facility location game for minimizing the social cost, we show that any deterministic strategyproof mechanism has unbounded approximation ratio. Moreover, in the obnoxious heterogeneous two-facility location game for maximizing the social utility, we propose new deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound (7 − d)/6 for any deterministic strategyproof mechanism. We also design a strategyproof mechanism maximizing the minimum utility. In the obnoxious homogeneous two-facility location game for maximizing the social utility, we propose deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound 4/3. Besides, in the two-facility location game with triple-preference, where each facility may be favorable, obnoxious, indifferent for any agent, we further motivate agents to report both their locations and preferences towards the two facilities truthfully, and design a deterministic group strategyproof mechanism with an approximation ratio 4.



我々は、直線区間[0, 1]上に2つの施設を配置する社会計画者のメカニズム設計問題を考察します。この場合、n個の戦略エージェントの集合がそれぞれの位置を報告し、メカニズムが2つの施設の位置を決定します。2つの施設間の最小距離は0≤d≤1であるという要件を考慮します。2つの施設が異質であることを前提として、エージェントのコスト/効用を両施設までの距離の合計としてモデル化します。社会的コストを最小化する異質な2施設配置ゲームにおいて、最適解が多項式時間で計算できることを示し、出力として1つの最適解を慎重に選択することが戦略的証明となることを証明します。また、最大コストを最小化する戦略的証明メカニズムも設計します。2つの施設が同質であることを前提として、エージェントのコスト/効用を近い方の施設までの距離としてモデル化します。社会的コストを最小化する同質な2施設配置ゲームにおいて、任意の決定論的戦略的証明メカニズムが無限近似比を持つことを示す。さらに、社会的効用を最大化するための不快な異質な2施設配置ゲームにおいて、証明可能な近似比を持つ新しい決定論的グループ戦略証明メカニズムを提案し、任意の決定論的戦略証明メカニズムの下限(7−d)/6を確立します。また、最小効用を最大化する戦略証明メカニズムも設計します。社会的効用を最大化するための不快な同質な2施設配置ゲームでは、証明可能な近似比を持つ決定論的グループ戦略証明メカニズムを提案し、下限4/3を確立します。さらに、各施設がどのエージェントにとっても好ましい、不快である、無関心である可能性がある3つの選好を持つ2施設配置ゲームでは、エージェントが2つの施設に対する自分の場所と選好の両方を正直に報告するようにさらに動機付け、近似比4を持つ決定論的グループ戦略証明メカニズムを設計します。

Efficient Large-Scale Multi-Drone Delivery using Transit Networks

Efficient Large-Scale Multi-Drone Delivery using Transit Networks / 交通ネットワークを用いた効率的な大規模マルチドローン配送

We consider the problem of routing a large fleet of drones to deliver packages simultaneously across broad urban areas. Besides flying directly, drones can use public transit vehicles such as buses and trams as temporary modes of transportation to conserve energy. Adding this capability to our formulation augments effective drone travel range and the space of possible deliveries but also increases problem input size due to the large transit networks. We present a comprehensive algorithmic framework that strives to minimize the maximum time to complete any delivery and addresses the multifaceted computational challenges of our problem through a two-layer approach. First, the upper layer assigns drones to package delivery sequences with an approximately optimal polynomial time allocation algorithm. Then, the lower layer executes the allocation by periodically routing the fleet over the transit network, using efficient, bounded suboptimal multi-agent pathfinding techniques tailored to our setting. We demonstrate the efficiency of our approach on simulations with up to 200 drones, 5000 packages, and transit networks with up to 8000 stops in San Francisco and the Washington DC Metropolitan Area. Our framework computes solutions for most settings within a few seconds on commodity hardware and enables drones to extend their effective range by a factor of nearly four using transit.



大規模なドローン群をルーティングして、広い都市エリアに同時に荷物を配達する問題を考察します。ドローンは直接飛行するだけでなく、バ​​スや路面電車などの公共交通機関を一時的な移動手段として利用してエネルギーを節約することができます。この機能を定式化に追加することで、有効なドローンの移動範囲と配達可能な空間が拡張されますが、大規模な交通ネットワークのために問題の入力サイズも大きくなります。私たちは、配達を完了するための最大時間を最小限に抑えることを目指し、2層アプローチを通じて問題の多面的な計算課題に対処する包括的なアルゴリズムフレームワークを提示します。まず、上層は、近似的に最適な多項式時間割り当てアルゴリズムを使用して、荷物の配達シーケンスにドローンを割り当てます。次に、下層は、設定に合わせて調整された効率的で制限された準最適なマルチエージェント経路探索手法を使用して、定期的にドローン群を交通ネットワーク上にルーティングすることにより、割り当てを実行します。私たちは、最大200機のドローン、5000個の荷物、サンフランシスコとワシントンD.C.首都圏の最大8000の停留所を持つ交通ネットワークのシミュレーションで、このアプローチの効率性を実証します。私たちのフレームワークは、一般的なハードウェア上で数秒以内にほとんどの設定のソリューションを計算し、トランジットを使用してドローンの有効範囲を約4倍に拡大することを可能にします。

Integrated Offline and Online Decision Making under Uncertainty

Integrated Offline and Online Decision Making under Uncertainty / 不確実性下におけるオフラインとオンラインの統合意思決定

This paper considers multi-stage optimization problems under uncertainty that involve distinct offline and online phases. In particular it addresses the issue of integrating these phases to show how the two are often interrelated in real-world applications. Our methods are applicable under two (fairly general) conditions: 1) the uncertainty is exogenous; 2) it is possible to define a greedy heuristic for the online phase that can be modeled as a parametric convex optimization problem. We start with a baseline composed by a two-stage offline approach paired with the online greedy heuristic. We then propose multiple methods to tighten the offline/online integration, leading to significant quality improvements, at the cost of an increased computation effort either in the offline or the online phase. Overall, our methods provide multiple options to balance the solution quality/time trade-off, suiting a variety of practical application scenarios. To test our methods, we ground our approaches on two real cases studies with both offline and online decisions: an energy management problem with uncertain renewable generation and demand, and a vehicle routing problem with uncertain travel times. The application domains feature respectively continuous and discrete decisions. An extensive analysis of the experimental results shows that indeed offline/online integration may lead to substantial benefits.



本論文では、オフラインフェーズとオンラインフェーズが明確に区別される不確実性下における多段階最適化問題を考察します。特に、これらのフェーズの統合という問題を取り上げ、実世界のアプリケーションにおいてこれら2つのフェーズがどのように相互に関連していることが多いかを示す。本稿の手法は、2つの（比較的一般的な）条件下に適用可能です。1)不確実性は外生的であること。2)オンラインフェーズに対して、パラメトリック凸最適化問題としてモデル化可能な貪欲ヒューリスティックを定義できること。まず、2段階オフラインアプローチとオンライン貪欲ヒューリスティックを組み合わせたベースラインを構築します。次に、オフライン/オンライン統合を強化する複数の手法を提案します。これにより、オフラインフェーズまたはオンラインフェーズのいずれかにおける計算量の増加という代償を払うこととなるが、大幅な品質向上が期待できます。全体として、本稿の手法は、ソリューションの品質と時間のトレードオフのバランスをとるための複数の選択肢を提供し、様々な実用シナリオに適合します。本手法を検証するために、オフラインとオンラインの両方の意思決定を伴う2つの実際のケーススタディ、すなわち再生可能エネルギー発電量と需要が不確実なエネルギー管理問題と、移動時間が不確実な車両経路問題に基づいてアプローチを検証します。適用領域は、それぞれ連続的および離散的な意思決定を特徴としています。実験結果の広範な分析は、オフライン/オンライン統合が実際に大きなメリットをもたらす可能性があることを示しています。

A Sufficient Statistic for Influence in Structured Multiagent Environments

A Sufficient Statistic for Influence in Structured Multiagent Environments / 構造化マルチエージェント環境における影響力の十分な統計量

Making decisions in complex environments is a key challenge in artificial intelligence (AI). Situations involving multiple decision makers are particularly complex, leading to computational intractability of principled solution methods. A body of work in AI has tried to mitigate this problem by trying to distill interaction to its essence: how does the policy of one agent influence another agent? If we can find more compact representations of such influence, this can help us deal with the complexity, for instance by searching the space of influences rather than the space of policies. However, so far these notions of influence have been restricted in their applicability to special cases of interaction. In this paper we formalize influence-based abstraction (IBA), which facilitates the elimination of latent state factors without any loss in value, for a very general class of problems described as factored partially observable stochastic games (fPOSGs). On the one hand, this generalizes existing descriptions of influence, and thus can serve as the foundation for improvements in scalability and other insights in decision making in complex multiagent settings. On the other hand, since the presence of other agents can be seen as a generalization of single agent settings, our formulation of IBA also provides a sufficient statistic for decision making under abstraction for a single agent. We also give a detailed discussion of the relations to such previous works, identifying new insights and interpretations of these approaches. In these ways, this paper deepens our understanding of abstraction in a wide range of sequential decision making settings, providing the basis for new approaches and algorithms for a large class of problems.



複雑な環境における意思決定は、人工知能（AI）における重要な課題です。複数の意思決定者が関与する状況は特に複雑であり、原理的な解決法の計算上の扱いにくさにつながります。AI分野の多くの研究では、相互作用をその本質、つまりあるエージェントのポリシーが他のエージェントにどのように影響を与えるかにまで絞り込むことで、この問題を軽減しようと試みられてきました。このような影響をより簡潔に表現できれば、例えばポリシー空間ではなく影響空間を探索するなど、複雑さに対処するのに役立ちます。しかしながら、これまでこれらの影響の概念は、相互作用の特殊なケースへの適用に限定されていました。本稿では、因子化部分観測確率ゲーム（fPOSG）として記述される非常に一般的なクラスの問題に対して、価値を損なうことなく潜在的な状態要因の除去を容易にする影響ベース抽象化（IBA）を形式化します。一方で、これは既存の影響力の記述を一般化し、複雑なマルチエージェント設定における意思決定のスケーラビリティやその他の洞察の向上の基盤として役立ちます。他方で、他のエージェントの存在は単一エージェント設定の一般化と見なすことができるため、IBAの定式化は、単一エージェントの抽象化下での意思決定に十分な統計も提供します。また、このような以前の研究との関係についても詳細に議論し、これらのアプローチの新たな洞察と解釈を特定します。このように、本論文は、さまざまな順次意思決定設定における抽象化の理解を深め、幅広い問題に対する新しいアプローチとアルゴリズムの基礎を提供します。

Taking Principles Seriously: A Hybrid Approach to Value Alignment in Artificial Intelligence

Taking Principles Seriously: A Hybrid Approach to Value Alignment in Artificial Intelligence / 原則を真摯に受け止める：人工知能における価値整合へのハイブリッドアプローチ

An important step in the development of value alignment (VA) systems in artificial intelligence (AI) is understanding how VA can reflect valid ethical principles. We propose that designers of VA systems incorporate ethics by utilizing a hybrid approach in which both ethical reasoning and empirical observation play a role. This, we argue, avoids committing “naturalistic fallacy,” which is an attempt to derive “ought” from “is,” and it provides a more adequate form of ethical reasoning when the fallacy is not committed. Using quantified modal logic, we precisely formulate principles derived from deontological ethics and show how they imply particular “test propositions” for any given action plan in an AI rule base. The action plan is ethical only if the test proposition is empirically true, a judgment that is made on the basis of empirical VA. This permits empirical VA to integrate seamlessly with independently justified ethical principles.This article is part of the special track on AI and Society.



人工知能(AI)における価値整合(VA)システムの開発における重要なステップは、VAが有効な倫理原則をどのように反映できるかを理解することです。私たちは、VAシステムの設計者が、倫理的推論と経験的観察の両方が役割を果たすハイブリッドアプローチを利用して倫理を組み込むことを提案します。これは「自然主義的誤謬」、つまり「ある」から「あるべき」を導出しようとする試みを回避し、誤謬が犯されていない場合にはより適切な倫理的推論の形態を提供すると我々は主張します。量化様相論理を用いて、義務論的倫理学から導かれる原理を正確に定式化し、それらがAIルールベース内の任意の行動計画に対して特定の「テスト命題」を示唆することを示す。行動計画は、テスト命題が経験的に真である場合にのみ倫理的であり、この判断は経験的VAに基づいて行われます。これにより、経験的VAは独立して正当化された倫理原則とシームレスに統合することができます。本稿はAIと社会に関する特別トラックの一部です。

On the Evolvability of Monotone Conjunctions with an Evolutionary Mutation Mechanism

On the Evolvability of Monotone Conjunctions with an Evolutionary Mutation Mechanism / 進化的突然変異メカニズムによる単調接続詞の進化可能性について

A Bernoulli(p)n distribution Bn,p over {0, 1}n is a product distribution where each variable is satisfied with the same constant probability p. Diochnos (2016) showed that Valiant’s swapping algorithm for monotone conjunctions converges efficiently under Bn,p distributions over {0, 1}n for any 0 < p < 1. We continue the study of monotone conjunctions in Valiant's framework of evolvability. In particular, we prove that given a Bn,p distribution characterized by some p ∈ (0, 1/3] ∪ {1/2}, then an evolutionary mechanism that relies on the basic mutation mechanism of a (1+1) evolutionary algorithm converges efficiently, with high probability, to an ε-optimal hypothesis. Furthermore, for 0 < α ≤ 3/13, a slight modification of the algorithm, with a uniform setup this time, evolves with high probability an ε-optimal hypothesis, for every Bn,p distribution such that p ∈ [α, 1/3 - 4α/9] ∪ {1/3} ∪ {1/2}.



{0, 1}n上のベルヌーイ(p)n分布Bn,pは、各変数が同じ定数確率pを満たす積分布です。Diochnos (2016)は、Valiantの単調接続詞に対するスワッピングアルゴリズムが、{0, 1}n上のBn,p分布において、任意の0 < p < 1に対して効率的に収束することを示しました。私たちは、Valiantの進化可能性の枠組みにおいて、単調接続詞の研究を継続しています。特に、あるp∈(0, 1/3]∪{1/2}によって特徴付けられるBn,p分布が与えられた場合、(1+1)進化アルゴリズムの基本的な突然変異メカニズムに依存する進化メカニズムは、高い確率で ε 最適仮説に収束することを証明します。さらに、0 <α ≤3/13の場合、今度は均一なセットアップでアルゴリズムをわずかに修正すると、p∈[α, 1/3 - 4α/9]∪{1/3}∪{1/2}となるすべてのBn,p分布に対して、高い確率で ε 最適仮説が進化します。

Safe Multi-Agent Pathfinding with Time Uncertainty

Safe Multi-Agent Pathfinding with Time Uncertainty / 時間的不確実性を伴う安全なマルチエージェント経路探索

In many real-world scenarios, the time it takes for a mobile agent, e.g., a robot, to move from one location to another may vary due to exogenous events and be difficult to predict accurately. Planning in such scenarios is challenging, especially in the context of Multi-Agent Pathfinding (MAPF), where the goal is to find paths to multiple agents and temporal coordination is necessary to avoid collisions. In this work, we consider a MAPF problem with this form of time uncertainty, where we are only given upper and lower bounds on the time it takes each agent to move. The objective is to find a safe solution, which is a solution that can be executed by all agents and is guaranteed to avoid collisions. We propose two complete and optimal algorithms for finding safe solutions based on well-known MAPF algorithms, namely, A* with Operator Decomposition (A* + OD) and Conflict-Based Search (CBS). Experimentally, we observe that on several standard MAPF grids the CBS-based algorithm performs better. We also explore the option of online replanning in this context, i.e., modifying the agents’ plans during execution, to reduce the overall execution cost. We consider two online settings: (a) when an agent can sense the current time and its current location, and (b) when the agents can also communicate seamlessly during execution. For each setting, we propose a replanning algorithm and analyze its behavior theoretically and empirically. Our experimental evaluation confirms that indeed online replanning in both settings can significantly reduce solution cost.



多くの現実世界のシナリオでは、ロボットなどのモバイルエージェントがある場所から別の場所に移動するのにかかる時間は、外生イベントによって変化する可能性があり、正確に予測することが困難です。このようなシナリオでの計画は、特にマルチエージェントパスファインディングのコンテキストでは困難です。(MAPF)は、複数のエージェントへの経路を見つけることを目的とした、衝突を回避するための時間的な調整を必要とする問題です。本研究では、このような時間的不確実性を伴うMAPF問題を検討します。このMAPF問題では、各エージェントの移動時間の上限と下限のみが与えられます。目的は、すべてのエージェントが実行でき、衝突を回避することが保証された安全な解を見つけることです。本研究では、よく知られているMAPFアルゴリズム、すなわち演算子分解を伴うA* (A* + OD)と衝突ベース探索(CBS)に基づいて、安全な解を見つけるための2つの完全かつ最適なアルゴリズムを提案します。実験では、いくつかの標準的なMAPFグリッドにおいて、CBSベースのアルゴリズムの方が優れたパフォーマンスを示すことが確認されました。また、このコンテキストにおいて、実行中にエージェントの計画を修正することで全体的な実行コストを削減するオンライン再計画の選択肢についても検討します。本研究では、(a)エージェントが現在の時刻と現在位置を感知できる場合、(b)エージェントが実行中にシームレスに通信できる場合の2つのオンライン設定を検討します。各設定について、以下の提案を行います。再計画アルゴリズムを検証し、その挙動を理論的かつ経験的に分析します。実験的評価により、両方の設定においてオンライン再計画がソリューションコストを大幅に削減できることが確認されました。

Constrained Multiagent Markov Decision Processes: a Taxonomy of Problems and Algorithms

Constrained Multiagent Markov Decision Processes: a Taxonomy of Problems and Algorithms / 制約付きマルチエージェント・マルコフ決定過程：問題とアルゴリズムの分類

In domains such as electric vehicle charging, smart distribution grids and autonomous warehouses, multiple agents share the same resources. When planning the use of these resources, agents need to deal with the uncertainty in these domains. Although several models and algorithms for such constrained multiagent planning problems under uncertainty have been proposed in the literature, it remains unclear when which algorithm can be applied. In this survey we conceptualize these domains and establish a generic problem class based on Markov decision processes. We identify and compare the conditions under which algorithms from the planning literature for problems in this class can be applied: whether constraints are soft or hard, whether agents are continuously connected, whether the domain is fully observable, whether a constraint is momentarily (instantaneous) or on a budget, and whether the constraint is on a single resource or on multiple. Further we discuss the advantages and disadvantages of these algorithms. We conclude by identifying open problems that are directly related to the conceptualized domains, as well as in adjacent research areas.



電気自動車の充電、スマート配電網、自律倉庫などの分野では、複数のエージェントが同じリソースを共有しています。これらのリソースの使用を計画する際には、エージェントはこれらの領域における不確実性に対処する必要があります。文献では、不確実性下におけるこのような制約付きマルチエージェント計画問題に対するモデルやアルゴリズムがいくつか提案されているものの、どのアルゴリズムがいつ適用できるかは依然として不明です。本調査では、これらの領域を概念化し、マルコフ決定過程に基づく一般的な問題クラスを確立します。計画に関する文献のアルゴリズムをこのクラスの問題に適用できる条件を特定し、比較します。制約がソフトかハードか、エージェントが継続的に接続されているか、領域が完全に観測可能か、制約が瞬間的か予算か、制約が単一のリソースか複数のリソースか、といった条件です。さらに、これらのアルゴリズムの長所と短所についても議論します。最後に、概念化された領域に直接関連する未解決の問題を特定するとともに、隣接する研究分野において。

参考文献

• Journal of Artificial Intelligence Resarch Vol. 70 (2021)

関連情報

• Journal of Artificial Intelligence Research: 論文一覧