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

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

論文

Indirect Causes in Dynamic Bayesian Networks Revisited

Indirect Causes in Dynamic Bayesian Networks Revisited / 動的ベイジアンネットワークにおける間接的原因の再考

Modeling causal dependencies often demands cycles at a coarse-grained temporal scale. If Bayesian networks are to be used for modeling uncertainties, cycles are eliminated with dynamic Bayesian networks, spreading indirect dependencies over time and enforcing an infinitesimal resolution of time. Without a “causal design,” i.e., without anticipating indirect influences appropriately in time, we argue that such networks return spurious results. By identifying activator random variables, we propose activator dynamic Bayesian networks (ADBNs) which are able to rapidly adapt to contexts under a causal use of time, anticipating indirect influences on a solid mathematical basis using familiar Bayesian network semantics. ADBNs are well-defined dynamic probabilistic graphical models allowing one to model cyclic dependencies from local and causal perspectives while preserving a classical, familiar calculus and classically known algorithms, without introducing any overhead in modeling or inference.



因果依存関係のモデリングでは、粗粒度の時間スケールにおけるサイクルがしばしば必要になります。ベイジアンネットワークを不確実性のモデリングに使用する場合、動的ベイジアンネットワークによってサイクルが排除され、間接依存関係が時間的に拡散し、時間の分解能が無限小になります。「因果設計」、つまり時間における間接的影響を適切に予測しないネットワークは、誤った結果を返すと我々は主張します。活性化因子ランダム変数を特定することにより、我々は、時間の因果的使用における状況に迅速に適応し、使い慣れたベイジアンネットワークセマンティクスを用いた確固たる数学的根拠に基づいて間接的影響を予測できる、活性化因子動的ベイジアンネットワーク(ADBN)を提案します。ADBNは、明確に定義された動的確率的グラフィカルモデルであり、古典的で使い慣れた計算法と既知のアルゴリズムを維持しながら、局所的および因果的な観点から循環依存関係をモデル化できます。モデリングや推論にオーバーヘッドは発生しません。

Learning Discrete Bayesian Networks from Continuous Data

Learning Discrete Bayesian Networks from Continuous Data / 連続データからの離散ベイジアンネットワークの学習

Learning Bayesian networks from raw data can help provide insights into the relationships between variables. While real data often contains a mixture of discrete and continuous-valued variables, many Bayesian network structure learning algorithms assume all random variables are discrete. Thus, continuous variables are often discretized when learning a Bayesian network. However, the choice of discretization policy has significant impact on the accuracy, speed, and interpretability of the resulting models. This paper introduces a principled Bayesian discretization method for continuous variables in Bayesian networks with quadratic complexity instead of the cubic complexity of other standard techniques. Empirical demonstrations show that the proposed method is superior to the established minimum description length algorithm. In addition, this paper shows how to incorporate existing methods into the structure learning process to discretize all continuous variables and simultaneously learn Bayesian network structures.



ベイジアンネットワークを生データから学習することで、変数間の関係性に関する洞察を得ることができます。実際のデータには離散値変数と連続値変数が混在していることがよくありますが、多くのベイジアンネットワーク構造学習アルゴリズムでは、すべての確率変数が離散的であると仮定しています。そのため、ベイジアンネットワークを学習する際には、連続変数が離散化されることがよくあります。しかし、離散化ポリシーの選択は、結果として得られるモデルの精度、速度、および解釈可能性に大きな影響を与えます。本稿では、ベイジアンネットワークにおける連続変数の、他の標準的な手法の3次複雑度ではなく、2次複雑度を持つ、原理的なベイジアン離散化手法を紹介します。実証的デモンストレーションにより、提案手法は既存の最小記述長アルゴリズムよりも優れていることが示されています。さらに、本論文では、既存の手法を構造学習プロセスに組み込んで、すべての連続変数を離散化し、同時にベイジアン ネットワーク構造を学習する方法を示します。

Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty

Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty / 議会投票手続き：議題制御、操作、不確実性

We study computational problems for two popular parliamentary voting procedures: the amendment procedure and the successive procedure. They work in multiple stages where the result of each stage may influence the result of the next stage. Both procedures proceed according to a given linear order of the alternatives, an agenda. We obtain the following results for both voting procedures: On the one hand, deciding whether one can make a specific alternative win by reporting insincere preferences by the fewest number of voters, the Manipulation problem, or whether there is a suitable ordering of the agenda, the Agenda Control problem, takes polynomial time. On the other hand, our experimental studies with real-world data indicate that most preference profiles cannot be manipulated by only few voters and a successful agenda control is typically impossible. If the voters’ preferences are incomplete, then deciding whether an alternative can possibly win is NP-hard for both procedures. Whilst deciding whether an alternative necessarily wins is coNP-hard for the amendment procedure, it is polynomial-time solvable for the successive procedure.



我々は、議会における一般的な投票手続きである修正手続きと逐次手続きの計算問題を研究します。これらの手続きは複数の段階で実行され、各段階の結果が次の段階の結果に影響を与える可能性があります。どちらの手続きも、選択肢の線形順序、すなわちアジェンダに従って進行します。我々は、両方の投票手続きについて以下の結果を得た。一方で、最も少ない数の有権者が不誠実な選好を申告することで特定の選択肢を勝利させることができるかどうか（操作問題）、あるいは適切なアジェンダ順序があるかどうか（アジェンダ制御問題）の決定には、多項式時間を要します。他方、実世界のデータを用いた我々の実験的研究は、ほとんどの選好プロファイルは少数の有権者だけでは操作できず、アジェンダ制御を成功させることは一般的に不可能であることを示しています。有権者の選好が不完全である場合、どちらの手続きにおいても、ある選択肢が勝利する可能性があるかどうかの決定はNP困難です。ある選択肢が必ず勝利するかどうかを判断することは、修正手続きにおいてはcoNP困難であるが、逐次手続きにおいては多項式時間で解ける。

Market Interfaces for Electric Vehicle Charging

Market Interfaces for Electric Vehicle Charging / 電気自動車充電のための市場インターフェース

We consider settings where owners of electric vehicles (EVs) participate in a market mechanism to charge their vehicles. Existing work on such mechanisms has typically assumed that participants are fully rational and can report their preferences accurately via some interface to the mechanism or to a software agent participating on their behalf. However, this may not be reasonable in settings with non-expert human end-users.Thus, our overarching aim in this paper is to determine experimentally if a fully expressive market interface that enables accurate preference reports is suitable for the EV charging domain, or, alternatively, if a simpler, restricted interface that reduces the space of possible options is preferable. In doing this, we measure the performance of an interface both in terms of how it helps participants maximise their utility and how it affects deliberation time. Our secondary objective is to contrast two different types of restricted interfaces that vary in how they restrict the space of preferences that can be reported. To enable this analysis, we develop a novel game that replicates key features of an abstract EV charging scenario. In two experiments with over 300 users, we show that restricting the users’ preferences significantly reduces the time they spend deliberating (by up to half in some cases). An extensive usability survey confirms that this restriction is furthermore associated with a lower perceived cognitive burden on the users. More surprisingly, at the same time, using restricted interfaces leads to an increase in the users’ performance compared to the fully expressive interface (by up to 70%). We also show that some restricted interfaces have the desirable effect of reducing the energy consumption of their users by up to 20% while achieving the same utility as other interfaces. Finally, we find that a reinforcement learning agent displays similar performance trends to human users, enabling a novel methodology for evaluating market interfaces.



電気自動車（EV）の所有者が市場メカニズムに参加し、車両を充電するという状況を想定します。このようなメカニズムに関する既存の研究では、参加者は完全に合理的であり、メカニズムへのインターフェース、または代理で参加するソフトウェアエージェントへのインターフェースを介して、自分の好みを正確に報告できると想定されてきました。しかし、これは、専門家ではない人間のエンドユーザーがいる状況では合理的ではない可能性があります。そこで、本論文の包括的な目的は、正確な好み報告を可能にする表現力豊かな市場インターフェースがEV充電分野に適しているのか、あるいは、選択肢の空間を狭めるより単純で制限されたインターフェースが望ましいのかを、実験的に判断することです。この際、インターフェースの性能を、参加者の効用最大化にどのように役立つか、そしてそれが熟考時間にどのように影響するかという観点から測定します。第二の目的は、報告可能な好みの空間をどのように制限するかが異なる2種類の制限されたインターフェースを比較することです。この分析を可能にするために、抽象的なEV充電シナリオの主要な特徴を再現する新しいゲームを開発します。300人以上のユーザーを対象とした2つの実験において、ユーザーの選好を制限することで、熟考に費やす時間が大幅に短縮されることを示しました（場合によっては最大半分まで短縮）。さらに、広範なユーザビリティ調査により、この制限はユーザーの認知負荷の軽減につながることが確認されました。さらに驚くべきことに、制限されたインターフェースを使用すると、完全に表現力のあるインターフェースと比較して、ユーザーのパフォーマンスが最大70%向上しました。また、一部の制限されたインターフェースは、他のインターフェースと同等の効用を達成しながら、ユーザーのエネルギー消費を最大20%削減するという望ましい効果を持つことも示しました。最後に、強化学習エージェントが人間のユーザーと同様のパフォーマンス傾向を示すことを発見し、市場インターフェースを評価するための新たな手法を確立しました。

Sampling Based Approaches for Minimizing Regret in Uncertain Markov Decision Processes (MDPs)

Sampling Based Approaches for Minimizing Regret in Uncertain Markov Decision Processes (MDPs) / 不確実なマルコフ決定過程（MDP）におけるリグレット最小化のためのサンプリングに基づくアプローチ

Markov Decision Processes (MDPs) are an effective model to represent decision processes in the presence of transitional uncertainty and reward tradeoffs. However, due to the difficulty in exactly specifying the transition and reward functions in MDPs, researchers have proposed uncertain MDP models and robustness objectives in solving those models. Most approaches for computing robust policies have focused on the computation of maximin policies which maximize the value in the worst case amongst all realisations of uncertainty. Given the overly conservative nature of maximin policies, recent work has proposed minimax regret as an ideal alternative to the maximin objective for robust optimization. However, existing algorithms for handling minimax regret are restricted to models with uncertainty over rewards only and they are also limited in their scalability. Therefore, we provide a general model of uncertain MDPs that considers uncertainty over both transition and reward functions. Furthermore, we also consider dependence of the uncertainty across different states and decision epochs. We also provide a mixed integer linear program formulation for minimizing regret given a set of samples of the transition and reward functions in the uncertain MDP. In addition, we provide two myopic variants of regret, namely Cumulative Expected Myopic Regret (CEMR) and One Step Regret (OSR) that can be optimized in a scalable manner. Specifically, we provide dynamic programming and policy iteration based algorithms to optimize CEMR and OSR respectively. Finally, to demonstrate the effectiveness of our approaches, we provide comparisons on two benchmark problems from literature. We observe that optimizing the myopic variants of regret, OSR and CEMR are better than directly optimizing the regret.



マルコフ決定過程（MDP）は、遷移の不確実性と報酬のトレードオフが存在する状況における意思決定プロセスを表現するのに効果的なモデルです。しかし、MDPにおける遷移関数と報酬関数を正確に指定することが難しいため、研究者は不確実性を考慮したMDPモデルと、それらのモデルを解くための堅牢性目標を提案してきました。ロバストな方策を計算するためのほとんどのアプローチは、不確実性のすべての実現値の中で最悪のケースにおける値を最大化するマキシミン方策の計算に焦点を当ててきました。マキシミン方策の過度に保守的な性質を考慮し、最近の研究では、ロバスト最適化におけるマキシミン目的の理想的な代替として、ミニマックス・リグレットが提案されています。しかし、ミニマックス・リグレットを扱う既存のアルゴリズムは、報酬に関する不確実性を持つモデルのみに限定されており、スケーラビリティにも限界があります。そこで本稿では、遷移関数と報酬関数の両方に関する不確実性を考慮した、不確実性MDPの一般化モデルを提供します。さらに、異なる状態および決定エポックにおける不確実性の依存性も考慮します。また、不確実性MDPにおける遷移関数と報酬関数のサンプル集合が与えられた場合に、リグレットを最小化する混合整数線形計画法の定式化も提供します。さらに、スケーラブルに最適化可能なリグレットの近視的変種である累積期待近視的リグレット（CEMR）とワンステップ・リグレット（OSR）を提供します。具体的には、CEMRとOSRをそれぞれ最適化するための動的計画法と方策反復に基づくアルゴリズムを提供します。最後に、我々のアプローチの有効性を示すために、文献から引用した2つのベンチマーク問題で比較を行いました。その結果、リグレットの近視眼的な変種であるOSRとCEMRを最適化する方が、リグレットを直接最適化するよりも優れていることがわかりました。

Adopting the Cascade Model in Ad Auctions: Efficiency Bounds and Truthful Algorithmic Mechanisms

Adopting the Cascade Model in Ad Auctions: Efficiency Bounds and Truthful Algorithmic Mechanisms / 広告オークションにおけるカスケードモデルの採用：効率性限界と真実性の高いアルゴリズムメカニズム

Sponsored Search Auctions (SSAs) are one of the most successful applications of microeconomic mechanisms, with a revenue of about $72 billion in the US alone in 2016. However, the problem of designing the best economic mechanism for sponsored search auctions is far from being solved, and, given the amount at stake, it is no surprise that it has received growing attention over the past few years. The most common auction mechanism for SSAs is the Generalized Second Price (GSP). However, the GSP is known not to be truthful: the agents participating in the auction might have an incentive to report false values, generating economic inefficiency and suboptimal revenues in turn. Superior, efficient truthful mechanisms, such as the Vickrey-Clarke-Groves (VCG) auction, are well known in the literature. However, while the VCG auction is currently adopted for the strictly related scenario of contextual advertising, e.g., by Google and Facebook, companies are reluctant to extend it to SSAs, fearing prohibitive switching costs. Other than truthfulness, two issues are of paramount importance in designing effective SSAs. First, the choice of the user model; not only does an accurate user model better target ads to users, it also is a critical factor in reducing the inefficiency of the mechanism. Often an antagonist to this, the second issue is the running time of the mechanism, given the performance pressure these mechanisms undertake in real-world applications. In our work, we argue in favor of adopting the VCG mechanism based on the cascade model with ad/position externalities (APDC-VCG). Our study includes both the derivation of inefficiency bounds and the design and the experimental evaluation of exact and approximate algorithms.



スポンサードサーチオークション（SSA）は、ミクロ経済メカニズムの最も成功した応用例の一つであり、2016年には米国だけで約720億ドルの収益を上げました。しかし、スポンサードサーチオークションに最適な経済メカニズムを設計するという課題は未だ解決には程遠く、その規模の大きさを考えると、ここ数年で注目を集めているのも当然と言えるでしょう。SSAで最も一般的なオークションメカニズムは、一般化セカンドプライス（GSP）です。しかし、GSPは誠実性に欠けることが知られています。オークションに参加するエージェントは虚偽の値を報告するインセンティブを持つ可能性があり、結果として経済効率が低下し、収益も最適とは言えません。Vickrey-Clarke-Groves（VCG）オークションのような、より優れた効率的な誠実性メカニズムは、文献でよく知られています。しかし、VCGオークションは現在、GoogleやFacebookなどによって、厳密に関連したコンテキスト広告のシナリオに採用されていますが、企業はスイッチングコストの高騰を懸念し、SSAへの適用には消極的です。真実性以外に、効果的なSSAを設計する上で極めて重要な問題が2つあります。1つ目はユーザーモデルの選択です。正確なユーザーモデルは、ユーザーへの広告のターゲティングを向上させるだけでなく、メカニズムの非効率性を低減する重要な要素でもあります。2つ目の問題は、しばしばこれに反するものであり、実際のアプリケーションにおいてこれらのメカニズムが受けるパフォーマンス上のプレッシャーを考慮すると、メカニズムの実行時間です。本研究では、広告/位置外部性を伴うカスケードモデルに基づくVCGメカニズム（APDC-VCG）の採用を支持します。本研究には、非効率性境界の導出と、厳密なアルゴリズムと近似アルゴリズムの設計および実験的評価の両方が含まれています。

Privacy Preserving Implementation of the Max-Sum Algorithm and its Variants

Privacy Preserving Implementation of the Max-Sum Algorithm and its Variants / プライバシー保護を考慮したMax-Sumアルゴリズムとその派生型の実装

One of the basic motivations for solving DCOPs is maintaining agents’ privacy. Thus, researchers have evaluated the privacy loss of DCOP algorithms and defined corresponding notions of privacy preservation for secured DCOP algorithms. However, no secured protocol was proposed for Max-Sum, which is among the most studied DCOP algorithms. As part of the ongoing effort of designing secure DCOP algorithms, we propose P-Max-Sum, the first private algorithm that is based on Max-Sum. The proposed algorithm has multiple agents preforming the role of each node in the factor graph, on which the Max-Sum algorithm operates. P-Max-Sum preserves three types of privacy: topology privacy, constraint privacy, and assignment/decision privacy. By allowing a single call to a trusted coordinator, P-Max-Sum also preserves agent privacy. The two main cryptographic means that enable this privacy preservation are secret sharing and homomorphic encryption. In addition, we design privacy-preserving implementations of four variants of Max-Sum. We conclude by analyzing the price of privacy in terns of runtime overhead, both theoretically and by extensive experimentation.



DCOPを解決する基本的な動機の1つは、エージェントのプライバシーを維持することです。そのため、研究者はDCOPアルゴリズムのプライバシー損失を評価し、セキュリティ保護されたDCOPアルゴリズムに対応するプライバシー保護の概念を定義してきました。しかし、最も研究されているDCOPアルゴリズムの1つであるMax-Sumには、セキュリティ保護されたプロトコルが提案されていません。安全なDCOPアルゴリズムを設計する継続的な取り組みの一環として、Max-Sumに基づく初のプライベート アルゴリズムであるP-Max-Sumを提案します。提案されたアルゴリズムでは、Max-Sumアルゴリズムが動作する因子グラフ内の各ノードの役割を複数のエージェントが実行します。P-Max-Sumは、トポロジ プライバシー、制約プライバシー、割り当て/決定プライバシーの3種類のプライバシーを保護します。信頼できるコーディネータへの単一の呼び出しを許可することにより、P-Max-Sumはエージェントのプライバシーも保護します。このプライバシー保護を可能にする2つの主な暗号化手段は、秘密共有と準同型暗号化です。さらに、Max-Sumの4つのバリアントのプライバシー保護実装を設計します。最後に、実行時のオーバーヘッドという観点からプライバシーの代償を理論的かつ広範な実験によって分析します。

AND/OR Branch-and-Bound on a Computational Grid

AND/OR Branch-and-Bound on a Computational Grid / 計算グリッドにおけるAND/OR分岐限定法

We present a parallel AND/OR Branch-and-Bound scheme that uses the power of a computational grid to push the boundaries of feasibility for combinatorial optimization. Two variants of the scheme are described, one of which aims to use machine learning techniques for parallel load balancing. In-depth analysis identifies two inherent sources of parallel search space redundancies that, together with general parallel execution overhead, can impede parallelization and render the problem far from embarrassingly parallel. We conduct extensive empirical evaluation on hundreds of CPUs, the first of its kind, with overall positive results. In a significant number of cases parallel speedup is close to the theoretical maximum and we are able to solve many very complex problem instances orders of magnitude faster than before; yet analysis of certain results also serves to demonstrate the inherent limitations of the approach due to the aforementioned redundancies.



我々は、計算グリッドのパワーを活用し、組み合わせ最適化の実現可能性の限界を押し広げる並列AND/OR分岐限定法を提案します。この法則には2つのバリエーションがあり、そのうちの1つは機械学習技術を並列負荷分散に用いることを目的としています。詳細な分析により、並列探索空間の冗長性に関する2つの固有の原因が特定されました。これらの冗長性は、一般的な並列実行のオーバーヘッドと相まって並列化を阻害し、問題を「恥ずかしいほど並列」とは程遠いものにしてしまう可能性があります。我々は数百台のCPUを用いた広範な実証的評価を実施した。これはこの種のものとしては初めてのことであり、概ね良好な結果が得られた。相当数のケースにおいて、並列化の高速化は理論上の最大値に近く、多くの非常に複雑な問題を従来よりも桁違いに高速に解くことができます。しかしながら、特定の結果の分析は、前述の冗長性に起因するこのアプローチの固有の限界を示すことにも役立つ。

Game-Theoretic Question Selection for Tests

Game-Theoretic Question Selection for Tests / テストのためのゲーム理論的質問選択

Conventionally, the questions on a test are assumed to be kept secret from test takers until the test. However, for tests that are taken on a large scale, particularly asynchronously, this is very hard to achieve. For example, TOEFL iBT and driver’s license test questions are easily found online. This also appears likely to become an issue for Massive Open Online Courses (MOOCs, as offered for example by Coursera, Udacity, and edX). Specifically, the test result may not reflect the true ability of a test taker if questions are leaked beforehand.In this paper, we take the loss of confidentiality as a fact. Even so, not all hope is lost as the test taker can memorize only a limited set of questions’ answers, and the tester can randomize which questions to let appear on the test. We model this as a Stackelberg game, where the tester commits to a mixed strategy and the follower responds. Informally, the goal of the tester is to best reveal the true ability of a test taker, while the test taker tries to maximize the test result (pass probability or score). We provide an exponential-size linear program formulation that computes the optimal test strategy, prove several NP-hardness results on computing optimal test strategies in general, and give efficient algorithms for special cases (scored tests and single-question tests). Experiments are also provided for those proposed algorithms to show their scalability and the increase of the tester’s utility relative to that of the uniform-at-random strategy. The increase is quite significant when questions have some correlation—for example, when a test taker who can solve a harder question can always solve easier questions.



従来、試験の問題は試験当日まで受験者から秘密にされることが想定されています。しかし、特に非同期で大規模に実施される試験の場合、これを実現するのは非常に困難です。例えば、TOEFL iBTや運転免許試験の問題はオンラインで簡単に見つかります。これは、Coursera、Udacity、edXなどが提供する大規模公開オンライン講座（MOOC）でも問題になりそうです。具体的には、問題が事前に漏洩した場合、テスト結果が受験者の真の能力を反映しない可能性があります。本稿では、機密性が失われることを事実として扱います。それでも、受験者が記憶できる問題の解答は限られており、テスト担当者はどの問題をテストに出すかをランダムに決定できるため、希望が失われるわけではありません。私たちはこれを、テスト担当者が混合戦略にコミットし、フォロワーがそれに応答するスタックベルグゲームとしてモデル化します。簡単に言うと、テスト担当者の目標は受験者の真の能力を最大限に引き出すことであり、受験者はテスト結果（合格確率またはスコア）を最大化しようとします。我々は、最適なテスト戦略を計算する指数サイズの線形計画定式化を提供し、一般に最適なテスト戦略を計算する際のNP困難性の結果を証明し、特殊なケース（採点テストと単一質問テスト）に対する効率的なアルゴリズムを提供します。また、提案されたアルゴリズムのスケーラビリティと、一様ランダム戦略と比較したテスターの効用の増加を示す実験も提供されています。質問に何らかの相関関係がある場合、たとえば、より難しい質問を解ける受験者は常により簡単な質問を解ける場合など、この増加は非常に顕著です。

Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess

Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess / 大規模スパースグラフにおける小さな頂点被覆の発見：構築、局所探索、および前処理

The problem of finding a minimum vertex cover (MinVC) in a graph is a well known NP-hard combinatorial optimization problem of great importance in theory and practice. Due to its NP-hardness, there has been much interest in developing heuristic algorithms for finding a small vertex cover in reasonable time. Previously, heuristic algorithms for MinVC have focused on solving graphs of relatively small size, and they are not suitable for solving massive graphs as they usually have high-complexity heuristics. This paper explores techniques for solving MinVC in very large scale real-world graphs, including a construction algorithm, a local search algorithm and a preprocessing algorithm. Both the construction and search algorithms are based on low-complexity heuristics, and we combine them to develop a heuristic algorithm for MinVC called FastVC. Experimental results on a broad range of real-world massive graphs show that, our algorithms are very fast and have better performance than previous heuristic algorithms for MinVC. We also develop a preprocessing algorithm to simplify graphs for MinVC algorithms. By applying the preprocessing algorithm to local search algorithms, we obtain two efficient MinVC solvers called NuMVC2+p and FastVC2+p, which show further improvement on the massive graphs.



グラフ内の最小頂点被覆（MinVC）を見つける問題は、理論と実践において非常に重要な、よく知られたNP困難な組合せ最適化問題です。そのNP困難性のため、合理的な時間で小さな頂点被覆を見つけるためのヒューリスティックアルゴリズムの開発に大きな関心が寄せられています。これまで、MinVCのヒューリスティック アルゴリズムは、比較的小さなサイズのグラフを解くことに重点を置いており、通常、ヒューリスティックが複雑であるため、大規模なグラフを解くのには適していません。この論文では、構築アルゴリズム、ローカル検索アルゴリズム、前処理アルゴリズムなど、非常に大規模な現実世界のグラフでMinVCを解くための手法について説明します。構築アルゴリズムと検索アルゴリズムはどちらも低複雑度のヒューリスティックに基づいており、これらを組み合わせて、FastVCと呼ばれるMinVCのヒューリスティック アルゴリズムを開発しました。さまざまな現実世界の大規模グラフでの実験結果から、このアルゴリズムは非常に高速で、以前のMinVCのヒューリスティック アルゴリズムよりも優れたパフォーマンスを発揮することがわかっています。また、MinVCアルゴリズムのグラフを簡素化する前処理アルゴリズムも開発しています。前処理アルゴリズムをローカル検索アルゴリズムに適用することで、大規模グラフでさらなる改善が見られるNuMVC2+pとFastVC2+pという2つの効率的なMinVCソルバーが得られます。

Perturbation Training for Human-Robot Teams

Perturbation Training for Human-Robot Teams / 人間とロボットのチームのための摂動訓練

In this work, we design and evaluate a computational learning model that enables a human-robot team to co-develop joint strategies for performing novel tasks that require coordination. The joint strategies are learned through “perturbation training,” a human team-training strategy that requires team members to practice variations of a given task to help their team generalize to new variants of that task. We formally define the problem of human-robot perturbation training and develop and evaluate the first end-to-end framework for such training, which incorporates a multi-agent transfer learning algorithm, human-robot co-learning framework and communication protocol. Our transfer learning algorithm, Adaptive Perturbation Training (AdaPT), is a hybrid of transfer and reinforcement learning techniques that learns quickly and robustly for new task variants. We empirically validate the benefits of AdaPT through comparison to other hybrid reinforcement and transfer learning techniques aimed at transferring knowledge from multiple source tasks to a single target task.We also demonstrate that AdaPT’s rapid learning supports live interaction between a person and a robot, during which the human-robot team trains to achieve a high level of performance for new task variants. We augment AdaPT with a co-learning framework and a computational bi-directional communication protocol so that the robot can co-train with a person during live interaction. Results from large-scale human subject experiments (n=48) indicate that AdaPT enables an agent to learn in a manner compatible with a human’s own learning process, and that a robot undergoing perturbation training with a human results in a high level of team performance. Finally, we demonstrate that human-robot training using AdaPT in a simulation environment produces effective performance for a team incorporating an embodied robot partner.



本研究では、人間とロボットのチームが協調を必要とする新しいタスクを遂行するための共同戦略を共同で開発することを可能にする計算学習モデルを設計し、評価します。この共同戦略は、「摂動訓練」を通して学習されます。これは、チームメンバーに特定のタスクのバリエーションを練習させることで、チームがそのタスクの新しいバリエーションを一般化できるようにする、人間チームの訓練戦略です。私たちは、人間とロボットの摂動訓練の問題を正式に定義し、マルチエージェント転移学習アルゴリズム、人間とロボットの共学習フレームワーク、および通信プロトコルを組み込んだ、そのような訓練のための初のエンドツーエンドフレームワークを開発し、評価します。私たちの転移学習アルゴリズムである適応型摂動訓練（AdaPT）は、転移学習と強化学習の手法を組み合わせたもので、新しいタスクのバリエーションを迅速かつ堅牢に学習します。複数のソースタスクから単一のターゲットタスクに知識を転送することを目的とした他のハイブリッド強化学習および転移学習手法と比較することにより、AdaPTの利点を経験的に検証しました。また、AdaPTの迅速な学習は、人間とロボットのチームが新しいタスクバリアントで高いレベルのパフォーマンスを達成するためのトレーニングを行う、人間とロボットのライブインタラクションをサポートすることも示しました。ライブインタラクション中にロボットが人間と共同トレーニングできるように、共同学習フレームワークと計算双方向通信プロトコルでAdaPTを拡張しました。大規模な被験者実験(n=48)の結果から、AdaPTによりエージェントが人間自身の学習プロセスと互換性のある方法で学習できること、および人間と共に摂動トレーニングを受けるロボットがチームの高いパフォーマンスにつながることがわかりました。最後に、シミュレーション環境でAdaPTを使用した人間とロボットのトレーニングにより、具現化されたロボットパートナーを含むチームが効果的なパフォーマンスを発揮できることを実証しました。

The Length of Shortest Vertex Paths in Binary Occupancy Grids Compared to Shortest r-Constrained Ones

The Length of Shortest Vertex Paths in Binary Occupancy Grids Compared to Shortest r-Constrained Ones / 二項占有グリッドにおける最短頂点経路の長さと、最短r制約グリッドとの比較

We study the problem of finding a short path from a start to a goal within a two-dimensional continuous and isotropic terrain that has been discretized into an array of accessible and blocked cells. A classic approach obtains a grid path where each step is along the edge of an accessible cell or diagonally across one. Grid paths suffer from `digitization bias’ — even if two locations have line-of-sight, the minimum travelling cost between them can be greater than the distance along the line-of-sight. In a vertex path, steps are allowed from a cell corner to any other cell corner if they have line-of-sight. While the `digitization bias’ is smaller, shortest vertex paths are impractical to find by brute force. Recent research has thus turned to methods for finding short (but not necessarily shortest) vertex paths. To establish the methods’ potential utility, we calculate upper bounds on the difference in length between the shortest vertex paths versus the shortest r-constrained ones where an r-constrained path consists of line segments that each traverse at most r rows and at most r columns of cells. The difference in length reduces as r increases — indeed the shortest vertex paths are at most 1 percent shorter than the shortest 4-constrained ones. This article will be useful to developers and users of short(est) vertex paths algorithms who want to trade path length for improved runtimes in a predictable manner.



我々は、アクセス可能なセルとブロックされたセルの配列に離散化された2次元の連続した等方性地形において、スタート地点からゴール地点までの短い経路を見つける問題を研究します。従来のアプローチでは、各ステップがアクセス可能なセルの端に沿うか、または対角線上を横切るグリッドパスを得る。グリッドパスは「デジタル化バイアス」の影響を受ける。つまり、2つの地点に見通し線がある場合でも、それらの間の最小移動コストが見通し線に沿った距離よりも大きくなる可能性があります。頂点パスでは、見通し線があれば、セルの角から他の任意のセルの角までステップを踏むことができます。「デジタル化バイアス」は小さいが、最短の頂点パスを力ずくで見つけるのは現実的ではない。そのため、最近の研究では、短い（ただし必ずしも最短ではない）頂点パスを見つける手法が注目されています。これらの手法の潜在的な有用性を確立するために、最短頂点パスと最短r制約パスの長さの差の上限を計算します。ここで、r制約パスは、最大r行、最大r列のセルをそれぞれ通過する線分で構成されます。rが増加するにつれて、長さの差は減少します。実際、最短頂点パスは、最短4制約パスよりも最大1%短くなります。この記事は、パスの長さと引き換えに予測可能な方法で実行時間を短縮したい最短（最短）頂点パスアルゴリズムの開発者とユーザーにとって有用です。

Probabilistic Reasoning with Abstract Argumentation Frameworks

Probabilistic Reasoning with Abstract Argumentation Frameworks / 抽象的議論フレームワークを用いた確率的推論

Abstract argumentation offers an appealing way of representing and evaluating arguments and counterarguments. This approach can be enhanced by considering probability assignments on arguments, allowing for a quantitative treatment of formal argumentation. In this paper, we regard the assignment as denoting the degree of belief that an agent has in an argument being acceptable. While there are various interpretations of this, an example is how it could be applied to a deductive argument. Here, the degree of belief that an agent has in an argument being acceptable is a combination of the degree to which it believes the premises, the claim, and the derivation of the claim from the premises. We consider constraints on these probability assignments, inspired by crisp notions from classical abstract argumentation frameworks and discuss the issue of probabilistic reasoning with abstract argumentation frameworks. Moreover, we consider the scenario when assessments on the probabilities of a subset of the arguments are given and the probabilities of the remaining arguments have to be derived, taking both the topology of the argumentation framework and principles of probabilistic reasoning into account. We generalise this scenario by also considering inconsistent assessments, i.e., assessments that contradict the topology of the argumentation framework. Building on approaches to inconsistency measurement, we present a general framework to measure the amount of conflict of these assessments and provide a method for inconsistency-tolerant reasoning.



抽象的な議論は、議論と反論を表現および評価するための魅力的な方法を提供します。このアプローチは、議論に対する確率の割り当てを考慮することで強化され、形式的な議論を定量的に扱うことが可能になります。本稿では、この割り当てを、エージェントが議論が受け入れられるという確信の度合いを表すものとみなします。これにはさまざまな解釈がありますが、一例として、これを演繹的議論に適用する方法を示します。ここで、エージェントが議論の受容可能性について抱く確信度は、前提、主張、そして前提から主張を導出することに対する確信度の組み合わせです。我々は、古典的な抽象的議論の枠組みの明確な概念に着想を得た、これらの確率割り当てに対する制約を考察し、抽象的議論の枠組みにおける確率的推論の問題について議論します。さらに、議論のサブセットの確率の評価が与えられ、残りの議論の確率を、議論の枠組みの位相と確率的推論の原理の両方を考慮に入れながら導出しなければならないシナリオを考察します。我々は、矛盾する評価、すなわち議論の枠組みの位相に反する評価も考慮することで、このシナリオを一般化します。矛盾の測定手法に基づき、これらの評価の矛盾の量を測定するための一般的な枠組みを提示し、矛盾を許容する推論手法を提供します。

The Price of Anarchy in Auctions

The Price of Anarchy in Auctions / オークションにおける無秩序の代償

This survey outlines a general and modular theory for proving approximation guarantees for equilibria of auctions in complex settings. This theory complements traditional economic techniques, which generally focus on exact and optimal solutions and are accordingly limited to relatively stylized settings.We highlight three user-friendly analytical tools: smoothness-type inequalities, which immediately yield approximation guarantees for many auction formats of interest in the special case of complete information and deterministic strategies; extension theorems, which extend such guarantees to randomized strategies, no-regret learning outcomes, and incomplete-information settings; and composition theorems, which extend such guarantees from simpler to more complex auctions. Combining these tools yields tight worst-case approximation guarantees for the equilibria of many widely-used auction formats.



この調査では、複雑な設定におけるオークションの均衡の近似保証を証明するための、一般論的かつモジュール型の理論を概説します。この理論は、一般的に正確かつ最適な解に焦点を当て、したがって比較的様式化された設定に限定される従来の経済学的手法を補完するものです。本研究では、3つのユーザーフレンドリーな分析ツールに焦点を当てる。すなわち、完全情報および決定論的戦略という特殊なケースにおいて、多くの関心のあるオークション形式の近似保証を即座にもたらす平滑性型不等式、ランダム化戦略、ノーリグレット学習結果、不完全情報設定にそのような保証を拡張する拡張定理、そしてそのような保証をより単純なオークションからより複雑なオークションに拡張する合成定理です。これらのツールを組み合わせることで、広く使用されている多くのオークション形式の均衡に対する、厳密な最悪ケース近似保証が得られます。

Welfare Effects of Market Making in Continuous Double Auctions

Welfare Effects of Market Making in Continuous Double Auctions / 連続ダブルオークションにおけるマーケットメイキングの福祉効果

We investigate the effects of market making on market performance, focusing on allocative efficiency as well as gains from trade accrued by background traders. We employ empirical simulation-based methods to evaluate heuristic strategies for market makers as well as background investors in a variety of complex trading environments. Our market model incorporates private and common valuation elements, with dynamic fundamental value and asymmetric information. In this context, we compare the surplus achieved by background traders in strategic equilibrium, with and without a market maker. Our findings indicate that the presence of the market maker strongly tends to increase total welfare across various environments. Market-maker profit may or may not exceed the welfare gain, thus the effect on background-investor surplus is ambiguous. We find that market making tends to benefit investors in relatively thin markets, and situations where background traders are impatient, due to limited trading opportunities. The presence of additional market makers increases these benefits, as competition drives the market makers to provide liquidity at lower price spreads. A thorough sensitivity analysis indicates that these results are robust to reasonable changes in model parameters.



本研究では、配分効率とバックグラウンドトレーダーによって獲得された取引による利益に焦点を当て、マーケットメイクが市場パフォーマンスに与える影響を調査します。我々は、実証的シミュレーションに基づく手法を用いて、様々な複雑な取引環境におけるマーケットメーカーとバックグラウンド投資家のヒューリスティック戦略を評価します。我々の市場モデルは、動的なファンダメンタル価値と非対称情報を考慮した、私的および共通の評価要素を組み込んでいます。この文脈において、マーケットメーカーの有無にかかわらず、戦略的均衡におけるバックグラウンド投資家が達成する余剰を比較します。調査結果は、マーケットメーカーの存在が様々な環境において総厚生を著しく増加させる傾向にあることを示しています。マーケットメーカーの利益は厚生ゲインを上回る場合と上回らない場合があり、したがってバックグラウンド投資家の余剰への影響は不明確です。マーケットメーカーは、比較的市場が薄い場合、および取引機会が限られているためにバックグラウンド投資家が焦っている状況において、投資家に利益をもたらす傾向があることがわかった。追加のマーケットメーカーの存在は、競争によってマーケットメーカーがより低い価格スプレッドで流動性を提供するよう促すため、これらの利益を増大させる。徹底的な感度分析は、これらの結果がモデルパラメータの合理的な変化に対して堅牢であることを示しています。

Logical Formalizations of Commonsense Reasoning: A Survey

Logical Formalizations of Commonsense Reasoning: A Survey / 常識推論の論理的形式化：調査

Commonsense reasoning is in principle a central problem in artificial intelligence, but it is a very difficult one. One approach that has been pursued since the earliest days of the field has been to encode commonsense knowledge as statements in a logic-based representation language and to implement commonsense reasoning as some form of logical inference. This paper surveys the use of logic-based representations of commonsense knowledge in artificial intelligence research.



常識的推論は、原理的には人工知能における中心的な問題であるが、非常に難しい問題でもあります。この分野の初期から追求されてきたアプローチの一つは、常識的知識を論理ベースの表現言語の文として符号化し、常識的推論を何らかの論理的推論として実装するというものです。本稿は、人工知能研究における常識的知識の論理ベースの表現の利用について概説します。

Decision-Theoretic Planning Under Anonymity in Agent Populations

Decision-Theoretic Planning Under Anonymity in Agent Populations / エージェント集団における匿名性下における意思決定理論的プランニング

We study the problem of self-interested planning under uncertainty in settings shared with more than a thousand other agents, each of which plans at its own individual level. We refer to such large numbers of agents as an agent population. The decision-theoretic formalism of interactive partially observable Markov decision process (I-POMDP) is used to model the agent’s self-interested planning. The first contribution of this article is a method for drastically scaling the finitely-nested I-POMDP to certain agent populations for the first time. Our method exploits two types of structure that is often exhibited by agent populations — anonymity and context-specific independence. We present a variant called the many-agent I-POMDP that models both these types of structure to plan efficiently under uncertainty in multiagent settings. In particular, the complexity of the belief update and solution in the many-agent I-POMDP is polynomial in the number of agents compared with the exponential growth that challenges the original framework.While exploiting structure helps mitigate the curse of many agents, the well-known curse of history that afflicts I-POMDPs continues to challenge scalability in terms of the planning horizon. The second contribution of this article is an application of the branch-and-bound scheme to reduce the exponential growth of the search tree for look ahead. For this, we introduce new fast-computing upper and lower bounds for the exact value function of the many-agent I-POMDP. This speeds up the look-ahead computations without trading off optimality, and reduces both memory and run time complexity. The third contribution is a comprehensive empirical evaluation of the methods on three new problems domains — policing large protests, controlling traffic congestion at a busy intersection, and improving the AI for the popular Clash of Clans multiplayer game. We demonstrate the feasibility of exact self-interested planning in these large problems, and that our methods for speeding up the planning are effective. Altogether, these contributions represent a principled and significant advance toward moving self-interested planning under uncertainty to real-world applications.



我々は、千を超える他のエージェントと共有される設定において、不確実性の下での利己的な計画の問題を研究します。これらのエージェントはそれぞれが独自のレベルで計画します。我々はこのような多数のエージェントをエージェント集団と呼ぶ。対話型部分観測マルコフ決定過程（I-POMDP）の決定理論的形式主義を用いて、エージェントの利己的な計画をモデル化します。本論文の最初の貢献は、有限にネストされたI-POMDPを特定のエージェント集団に劇的に拡張する手法を初めて提案する点です。我々の手法は、エージェント集団によく見られる2種類の構造、すなわち匿名性とコンテキスト依存の独立性を利用します。我々は、これら2種類の構造をモデル化し、マルチエージェント設定における不確実性の下で効率的に計画する、多エージェントI-POMDPと呼ばれる変種を提示します。特に、多エージェントI-POMDPにおける信念の更新と解の複雑さは、元のフレームワークの課題となる指数関数的増加と比較して、エージェント数の多項式です。構造を利用することで多エージェントの呪いを軽減できますが、I-POMDPを悩ませるよく知られた歴史の呪いは、計画期間の観点からスケーラビリティに依然として課題を残しています。本論文の2つ目の貢献は、分岐限定法を適用して、先読み探索木の指数関数的増加を軽減することです。そのために、多エージェントI-POMDPの正確な値関数に対して、高速計算のための新しい上限と下限を導入します。これにより、最適性を犠牲にすることなく先読み計算を高速化し、メモリと実行時間の複雑さの両方を削減します。3つ目の貢献は、大規模抗議活動の取り締まり、混雑した交差点での交通渋滞制御、そして人気のマルチプレイヤーゲーム「クラッシュ・オブ・クラン」のAI改良という3つの新しい問題領域における、これらの手法の包括的な実証的評価です。我々は、これらの大規模問題において正確な利己的計画の実現可能性を示し、計画を高速化する手法が有効であることを実証します。これらの貢献は、不確実性下における利己的計画を現実世界のアプリケーションへ移行するための、原理に基づいた重要な進歩です。

Uniform Random Generation and Dominance Testing for CP-Nets

Uniform Random Generation and Dominance Testing for CP-Nets / CPネットにおける一様乱数生成と優位性検定

The generation of preferences represented as CP-nets for experiments and empirical testing has typically been done in an ad hoc manner that may have introduced a large statistical bias in previous experimental work. We present novel polynomial-time algorithms for generating CP-nets with n nodes and maximum in-degree c uniformly at random. We extend this result to several statistical cultures commonly used in the social choice and preference reasoning literature. A CP-net is composed of both a graph and underlying cp-statements; our algorithm is the first to provably generate both the graph structure and cp-statements, and hence the underlying preference orders themselves, uniformly at random. We have released this code as a free and open source project. We use the uniform generation algorithm to investigate the maximum and expected flipping lengths, i.e., the maximum length over all outcomes o and o’, of a minimal proof that o is preferred to o’. Using our new statistical evidence, we conjecture that, for CP-nets with binary variables and complete conditional preference tables, the expected flipping length is polynomial in the number of preference variables. This has positive implications for the usability of CP-nets as compact preference models.



実験や実証的検証のためのCPネットとして表現される選好の生成は、通常、アドホックな方法で行われており、以前の実験作業において大きな統計的バイアスが生じていた可能性があります。我々は、n個のノードと最大入次数cを持つCPネットを一様ランダムに生成する、新しい多項式時間アルゴリズムを提示します。この結果は、社会選択および選好推論の文献で一般的に用いられるいくつかの統計的カルチャに拡張されます。CPネットはグラフと基礎となるcp文の両方から構成されます。我々のアルゴリズムは、グラフ構造とcp文、ひいては基礎となる選好順序自体の両方を一様ランダムに生成することを証明した初のアルゴリズムです。我々はこのコードを無料のオープンソースプロジェクトとして公開した。我々は、均一生成アルゴリズムを用いて、oがo’より好まれるという最小限の証明の最大および期待反転長、すなわち、すべての結果oおよびo’にわたる最大長を調査します。新しい統計的証拠を用いて、我々は、2値変数と完全な条件付き選好表を持つCPネットについて、期待反転長は選好変数の数の多項式であると推測します。これは、コンパクトな選好モデルとしてのCPネットの有用性にプラスの影響を与えます。

Complexity of n-Queens Completion

Complexity of n-Queens Completion / n-クイーン補完の複雑性

The n-Queens problem is to place n chess queens on an n by n chessboard so that no two queens are on the same row, column or diagonal. The n-Queens Completion problem is a variant, dating to 1850, in which some queens are already placed and the solver is asked to place the rest, if possible. We show that n-Queens Completion is both NP-Complete and #P-Complete. A corollary is that any non-attacking arrangement of queens can be included as a part of a solution to a larger n-Queens problem. We introduce generators of random instances for n-Queens Completion and the closely related Blocked n-Queens and Excluded Diagonals Problem. We describe three solvers for these problems, and empirically analyse the hardness of randomly generated instances. For Blocked n-Queens and the Excluded Diagonals Problem, we show the existence of a phase transition associated with hard instances as has been seen in other NP-Complete problems, but a natural generator for n-Queens Completion did not generate consistently hard instances. The significance of this work is that the n-Queens problem has been very widely used as a benchmark in Artificial Intelligence, but conclusions on it are often disputable because of the simple complexity of the decision problem. Our results give alternative benchmarks which are hard theoretically and empirically, but for which solving techniques designed for n-Queens need minimal or no change.



nクイーン問題とは、n×nのチェス盤にn個のチェスのクイーンを、2つのクイーンが同じ行、列、または対角線上にないように配置することです。nクイーン完成問題は1850年に遡る変種で、いくつかのクイーンが既に配置されており、可能であれば残りのクイーンを配置するようにソルバーに求められます。我々は、nクイーン完成がNP完全かつ#P完全であることを示します。系として、攻撃しないクイーンの配置は、より大きなnクイーン問題の解の一部として組み込むことができます。本稿では、nクイーン完全問題と、密接に関連するブロックnクイーンおよび排他対角線問題のためのランダムインスタンス生成器を紹介します。これらの問題に対する3つのソルバーについて説明し、ランダムに生成されたインスタンスの難しさを経験的に分析します。ブロックnクイーンおよび排他対角線問題に関しては、他のNP完全問題と同様に、困難なインスタンスに関連する相転移の存在を示すが、nクイーン完全問題の自然な生成器は一貫して困難なインスタンスを生成しなかった。本研究の重要性は、nクイーン問題が人工知能のベンチマークとして広く用いられているものの、決定問題の単純な複雑さのために、その結​​論がしばしば議論の的となっている点にあります。本研究の結果は、理論的にも経験的にも困難であるものの、nクイーン問題向けに設計された解法をほとんど、あるいは全く変更することなく実現できる代替ベンチマークを提供します。

参考文献

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

関連情報

• Journal of Artificial Intelligence Research: 論文一覧