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

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

論文

Learning Continuous Time Bayesian Networks in Non-stationary Domains

Learning Continuous Time Bayesian Networks in Non-stationary Domains / 非定常領域における連続時間ベイジアンネットワークの学習

Non-stationary continuous time Bayesian networks are introduced. They allow the parents set of each node to change over continuous time. Three settings are developed for learning non-stationary continuous time Bayesian networks from data: known transition times, known number of epochs and unknown number of epochs. A score function for each setting is derived and the corresponding learning algorithm is developed. A set of numerical experiments on synthetic data is used to compare the effectiveness of non-stationary continuous time Bayesian networks to that of non-stationary dynamic Bayesian networks. Furthermore, the performance achieved by non-stationary continuous time Bayesian networks is compared to that achieved by state-of-the-art algorithms on four real-world datasets, namely drosophila, saccharomyces cerevisiae, songbird and macroeconomics.



非定常連続時間ベイジアンネットワークを導入します。これにより、各ノードの親集合が連続時間にわたって変化することを可能にします。データから非定常連続時間ベイジアンネットワークを学習するために、既知の遷移時間、既知のエポック数、および未知のエポック数の3つの設定が開発されています。各設定のスコア関数が導出され、対応する学習アルゴリズムが開発されます。合成データを用いた一連の数値実験を用いて、非定常連続時間ベイジアンネットワークの有効性を非定常動的ベイジアンネットワークの有効性と比較します。さらに、非定常連続時間ベイジアン ネットワークによって達成されるパフォーマンスが、ショウジョウバエ、サッカロミセス セレビシエ、鳴き鳥、マクロ経済学という4つの実際のデータセットで最先端のアルゴリズムによって達成されるパフォーマンスと比較されます。

Optimal Partial-Order Plan Relaxation via MaxSAT

Optimal Partial-Order Plan Relaxation via MaxSAT / MaxSATによる最適半順序計画緩和

Partial-order plans (POPs) are attractive because of their least-commitment nature, which provides enhanced plan flexibility at execution time relative to sequential plans. Current research on automated plan generation focuses on producing sequential plans, despite the appeal of POPs. In this paper we examine POP generation by relaxing or modifying the action orderings of a sequential plan to optimize for plan criteria that promote flexibility. Our approach relies on a novel partial weighted MaxSAT encoding of a sequential plan that supports the minimization of deordering or reordering of actions. Using a similar technique, we further demonstrate how to remove redundant actions from the plan, and how to combine this criterion with the objective of maximizing a POP’s flexibility. Our partial weighted MaxSAT encoding allows us to compute a POP from a sequential plan effectively. We compare the efficiency of our approach to previous methods for POP generation via sequential-plan relaxation. Our results show that while an existing heuristic approach consistently produces the optimal deordering of a sequential plan, our approach has greater flexibility when we consider reordering the actions in the plan while also providing a guarantee of optimality. We also investigate and confirm the accuracy of the standard flex metric typically used to predict the true flexibility of a POP as measured by the number of linearizations it represents.



半順序プラン（POP）は、コミットメントが最小であるため、シーケンシャルプランと比較して実行時のプラン柔軟性が向上するという魅力があります。自動プラン生成に関する現在の研究は、POPの魅力にもかかわらず、シーケンシャルプランの生成に重点を置いています。本稿では、シーケンシャルプランのアクション順序を緩和または変更することで、柔軟性を促進するプラン基準を最適化するPOP生成について考察します。本手法は、アクションの順序変更または順序変更の最小化をサポートする、シーケンシャルプランの新しい部分重み付きMaxSATエンコーディングを採用しています。同様の手法を用いて、プランから冗長なアクションを削除する方法、およびこの基準をPOPの柔軟性最大化という目的と組み合わせる方法をさらに示します。本手法の部分重み付きMaxSATエンコーディングにより、シーケンシャルプランからPOPを効率的に計算できます。本手法の効率性を、シーケンシャルプランの緩和による従来のPOP生成方法と比較します。我々の研究結果は、既存のヒューリスティックなアプローチが一貫して順次計画の最適な順序付け解除を生成するのに対し、我々のアプローチは計画内のアクションの順序付けを考慮した場合により柔軟であり、かつ最適性の保証も提供することを示しています。また、線形化の数で測定されるPOPの真の柔軟性を予測するために通常使用される標準的なflexメトリックの精度を調査し、確認しました。

Lightweight Random Indexing for Polylingual Text Classification

Lightweight Random Indexing for Polylingual Text Classification / 多言語テキスト分類のための軽量ランダムインデックス作成

Multilingual Text Classification (MLTC) is a text classification task in which documents are written each in one among a set L of natural languages, and in which all documents must be classified under the same classification scheme, irrespective of language. There are two main variants of MLTC, namely Cross-Lingual Text Classification (CLTC) and Polylingual Text Classification (PLTC). In PLTC, which is the focus of this paper, we assume (differently from CLTC) that for each language in L there is a representative set of training documents; PLTC consists of improving the accuracy of each of the |L| monolingual classifiers by also leveraging the training documents written in the other (|L| − 1) languages. The obvious solution, consisting of generating a single polylingual classifier from the juxtaposed monolingual vector spaces, is usually infeasible, since the dimensionality of the resulting vector space is roughly |L| times that of a monolingual one, and is thus often unmanageable. As a response, the use of machine translation tools or multilingual dictionaries has been proposed. However, these resources are not always available, or are not always free to use.One machine-translation-free and dictionary-free method that, to the best of our knowledge, has never been applied to PLTC before, is Random Indexing (RI). We analyse RI in terms of space and time efficiency, and propose a particular configuration of it (that we dub Lightweight Random Indexing LRI). By running experiments on two well known public benchmarks, Reuters RCV1/RCV2 (a comparable corpus) and JRC-Acquis (a parallel one), we show LRI to outperform (both in terms of effectiveness and efficiency) a number of previously proposed machine-translation-free and dictionary-free PLTC methods that we use as baselines.



多言語テキスト分類(MLTC)は、文書がL個の自然言語セットのいずれかで書かれ、言語に関係なくすべての文書が同じ分類スキームで分類される必要があるテキスト分類タスクです。MLTCには、クロスリンガルテキスト分類(CLTC)と多言語テキスト分類(PLTC)という2つの主要なバリエーションがあります。本論文の焦点であるPLTCでは、(CLTCとは異なり) L個の各言語に対してトレーニング文書の代表的なセットが存在すると仮定します。PLTCは、|L|の各|L|の精度を向上させることで構成されます。PLTCでは、他の(|L|−1)言語で書かれたトレーニング ドキュメントも活用することで、単一言語分類器を作成できます。明白な解決策は、並置された単一言語ベクトル空間から単一の多言語分類器を生成することですが、結果として得られるベクトル空間の次元が単一言語のベクトル空間のおよそ|L|倍になり、多くの場合管理不能となるため、通常は実行不可能です。その対応策として、機械翻訳ツールや多言語辞書の使用が提案されています。ただし、これらのリソースは常に利用できるとは限らず、常に無料で使用できるわけでもありません。私たちが知る限り、これまでPLTCに適用されたことのない、機械翻訳も辞書も使用しない方法の1つが、ランダム インデックス(RI)です。私たちは、RIを空間および時間効率の観点から分析し、その特別な構成(軽量ランダム インデックスLRIと呼ぶ)を提案します。よく知られている2つの公開ベンチマーク、ロイターRCV1/RCV2（比較可能なコーパス）とJRC-Acquis（並列コーパス）で実験を実行することにより、LRIが、ベースラインとして使用する、以前に提案された機械翻訳不要および辞書不要のPLTC手法の数よりも（有効性と効率性の両面で）優れていることを示します。

Multi-objective Reinforcement Learning through Continuous Pareto Manifold Approximation

Multi-objective Reinforcement Learning through Continuous Pareto Manifold Approximation / 連続パレート多様体近似による多目的強化学習

Many real-world control applications, from economics to robotics, are characterized by the presence of multiple conflicting objectives. In these problems, the standard concept of optimality is replaced by Pareto-optimality and the goal is to find the Pareto frontier, a set of solutions representing different compromises among the objectives. Despite recent advances in multi-objective optimization, achieving an accurate representation of the Pareto frontier is still an important challenge. In this paper, we propose a reinforcement learning policy gradient approach to learn a continuous approximation of the Pareto frontier in multi-objective Markov Decision Problems (MOMDPs). Differently from previous policy gradient algorithms, where n optimization routines are executed to have n solutions, our approach performs a single gradient ascent run, generating at each step an improved continuous approximation of the Pareto frontier. The idea is to optimize the parameters of a function defining a manifold in the policy parameters space, so that the corresponding image in the objectives space gets as close as possible to the true Pareto frontier. Besides deriving how to compute and estimate such gradient, we will also discuss the non-trivial issue of defining a metric to assess the quality of the candidate Pareto frontiers. Finally, the properties of the proposed approach are empirically evaluated on two problems, a linear-quadratic Gaussian regulator and a water reservoir control task.



経済学からロボット工学まで、多くの現実世界の制御アプリケーションは、複数の相反する目的の存在によって特徴付けられます。これらの問題では、標準的な最適性の概念はパレート最適性に置き換えられ、目標はパレートフロンティア、つまり目的間のさまざまな妥協点を表す一連の解を見つけることです。多目的最適化における最近の進歩にもかかわらず、パレートフロンティアの正確な表現を達成することは依然として重要な課題です。本稿では、多目的マルコフ決定問題（MOMDP）におけるパレートフロンティアの連続近似を学習するための強化学習ポリシー勾配アプローチを提案します。n回の最適化ルーチンを実行してn個の解を得る従来の方策勾配アルゴリズムとは異なり、本手法では単一の勾配上昇実行を実行し、各ステップでパレート境界の改良された連続近似値を生成します。その考え方は、方策パラメータ空間で多様体を定義する関数のパラメータを最適化し、目的関数空間の対応する画像が真のパレート境界に可能な限り近づくようにすることです。このような勾配を計算および推定する方法を導出するだけでなく、候補となるパレート境界の品質を評価するための指標を定義するという重要な問題についても説明します。最後に、提案手法の特性を、線形二次ガウスレギュレータと貯水池制御タスクの2つの問題で経験的に評価します。

Goal Probability Analysis in Probabilistic Planning: Exploring and Enhancing the State of the Art

Goal Probability Analysis in Probabilistic Planning: Exploring and Enhancing the State of the Art / 確率的プランニングにおける目標確率分析：最先端技術の探究と強化

Unavoidable dead-ends are common in many probabilistic planning problems, e.g. when actions may fail or when operating under resource constraints. An important objective in such settings is MaxProb, determining the maximal probability with which the goal can be reached, and a policy achieving that probability. Yet algorithms for MaxProb probabilistic planning are severely underexplored, to the extent that there is scant evidence of what the empirical state of the art actually is. We close this gap with a comprehensive empirical analysis. We design and explore a large space of heuristic search algorithms, systematizing known algorithms and contributing several new algorithm variants. We consider MaxProb, as well as weaker objectives that we baptize AtLeastProb (requiring to achieve a given goal probabilty threshold) and ApproxProb (requiring to compute the maximum goal probability up to a given accuracy). We explore both the general case where there may be 0-reward cycles, and the practically relevant special case of acyclic planning, such as planning with a limited action-cost budget. We design suitable termination criteria, search algorithm variants, dead-end pruning methods using classical planning heuristics, and node selection strategies. We design a benchmark suite comprising more than 1000 instances adapted from the IPPC, resource-constrained planning, and simulated penetration testing. Our evaluation clarifies the state of the art, characterizes the behavior of a wide range of heuristic search algorithms, and demonstrates significant benefits of our new algorithm variants.



多くの確率的計画問題では、たとえばアクションが失敗する可能性がある場合や、リソースが制約されている状態で操作している場合など、避けられない行き詰まりは一般的です。このような設定での重要な目的はMaxProbであり、目標に到達できる最大確率と、その確率を達成するポリシーを決定します。しかし、MaxProb確率的計画のアルゴリズムは十分に調査されておらず、実際の経験的最先端がどのようなものであるかについての証拠はほとんどありません。私たちは包括的な経験的分析によってこのギャップを埋めます。大規模なヒューリスティック検索アルゴリズムを設計および調査し、既知のアルゴリズムを体系化し、いくつかの新しいアルゴリズムの変種を提供します。MaxProbに加えて、より弱い目的であるAtLeastProb (指定された目標確率しきい値を達成することを要求)およびapproxProb (指定された精度で最大目標確率を計算することを要求)を検討します。我々は、報酬0サイクルが存在する可能性のある一般的なケースと、行動コスト予算が限られた計画など、非巡回計画の実用上重要な特殊なケースの両方を検証します。適切な終了基準、探索アルゴリズムのバリアント、古典的な計画ヒューリスティックを用いた行き止まり枝刈り法、そしてノード選択戦略を設計します。IPPC、リソース制約計画、そして模擬侵入テストから適応させた1000以上のインスタンスを含むベンチマークスイートを設計します。この評価は、最先端の状況を明らかにし、幅広いヒューリスティック探索アルゴリズムの挙動を特徴づけ、そして我々の新しいアルゴリズムバリアントの重要な利点を実証します。

Effective Heuristics for Suboptimal Best-First Search

Effective Heuristics for Suboptimal Best-First Search / 準最適最良優先探索のための効果的なヒューリスティック

Suboptimal heuristic search algorithms such as weighted A* and greedy best-first search are widely used to solve problems for which guaranteed optimal solutions are too expensive to obtain. These algorithms crucially rely on a heuristic function to guide their search. However, most research on building heuristics addresses optimal solving. In this paper, we illustrate how established wisdom for constructing heuristics for optimal search can fail when considering suboptimal search. We consider the behavior of greedy best-first search in detail and we test several hypotheses for predicting when a heuristic will be effective for it. Our results suggest that a predictive characteristic is a heuristic’s goal distance rank correlation (GDRC), a robust measure of whether it orders nodes according to distance to a goal. We demonstrate that GDRC can be used to automatically construct abstraction-based heuristics for greedy best-first search that are more effective than those built by methods oriented toward optimal search. These results reinforce the point that suboptimal search deserves sustained attention and specialized methods of its own.



重み付きA*探索や貪欲最良優先探索などの準最適なヒューリスティック探索アルゴリズムは、保証された最適解を得るにはコストがかかりすぎる問題を解決するために広く用いられています。これらのアルゴリズムは、探索を導くためのヒューリスティック関数に大きく依存しています。しかし、ヒューリスティック構築に関する研究のほとんどは、最適解法に焦点を当てています。本稿では、最適探索のためのヒューリスティック構築に関する確立された知見が、準最適探索を考慮するとどのように機能しないかを示します。貪欲最良優先探索の挙動を詳細に検討し、ヒューリスティックがどのような場合に有効かを予測するためのいくつかの仮説を検証します。結果は、ヒューリスティックの目標距離順位相関（GDRC）が予測特性であることを示唆しています。これは、目標までの距離に応じてノードを順序付けるかどうかの堅牢な尺度です。GDRCを使用することで、貪欲最良優先探索のための抽象化ベースのヒューリスティックを自動的に構築でき、最適探索を指向した手法よりも効果的であることを示します。これらの結果は、準最適探索は継続的な注目と独自の特殊な手法が必要であるという点を裏付けています。

Scrubbing During Learning In Real-time Heuristic Search

Scrubbing During Learning In Real-time Heuristic Search / リアルタイムヒューリスティック探索における学習中のスクラビング

Real-time agent-centered heuristic search is a well-studied problem where an agent that can only reason locally about the world must travel to a goal location using bounded computation and memory at each step. Many algorithms have been proposed for this problem and theoretical results have also been derived for the worst-case performance with simple examples demonstrating worst-case performance in practice. Lower bounds, however, have not been widely studied. In this paper we study best-case performance more generally and derive theoretical lower bounds for reaching the goal using LRTA*, a canonical example of a real-time agent-centered heuristic search algorithm. The results show that, given some reasonable restrictions on the state space and the heuristic function, the number of steps an LRTA*-like algorithm requires to reach the goal will grow asymptotically faster than the state space, resulting in “scrubbing” where the agent repeatedly visits the same state. We then show that while the asymptotic analysis does not hold for more complex real-time search algorithms, experimental results suggest that it is still descriptive of practical performance.



リアルタイムエージェント中心ヒューリスティック探索は、世界について局所的にしか推論できないエージェントが、各ステップで制限された計算量とメモリを使用して目標地点まで移動しなければならないという、よく研究されている問題です。この問題に対しては多くのアルゴリズムが提案されており、最悪の場合の性能に関する理論的な結果も導出されており、実際に最悪の場合の性能を示す簡単な例も示されています。しかし、下限については広く研究されていない。本稿では、最良の場合の性能をより一般的に研究し、リアルタイムエージェント中心のヒューリスティック探索アルゴリズムの標準的な例であるLRTA*を使用して目標に到達するための理論的な下限を導出します。結果は、状態空間とヒューリスティック関数にいくつかの合理的な制約を与えると、LRTA*のようなアルゴリズムが目標に到達するために必要なステップ数は状態空間よりも漸近的に速く増加し、エージェントが同じ状態を繰り返し訪れる「スクラビング」を引き起こすことを示しています。次に、漸近分析はより複雑なリアルタイム探索アルゴリズムには当てはまらないものの、実験結果はそれが依然として実用的な性能を説明できることを示唆していることを示す。

A Primer on Neural Network Models for Natural Language Processing

A Primer on Neural Network Models for Natural Language Processing / 自然言語処理のためのニューラルネットワークモデル入門

Over the past few years, neural networks have re-emerged as powerful machine-learning models, yielding state-of-the-art results in fields such as image recognition and speech processing. More recently, neural network models started to be applied also to textual natural language signals, again with very promising results. This tutorial surveys neural network models from the perspective of natural language processing research, in an attempt to bring natural-language researchers up to speed with the neural techniques. The tutorial covers input encoding for natural language tasks, feed-forward networks, convolutional networks, recurrent networks and recursive networks, as well as the computation graph abstraction for automatic gradient computation.



ここ数年、ニューラルネットワークは強力な機械学習モデルとして再浮上し、画像認識や音声処理などの分野で最先端の成果を上げています。最近では、ニューラルネットワークモデルが自然言語のテキスト信号にも適用されるようになり、これもまた非常に有望な成果を上げています。このチュートリアルでは、自然言語処理研究の観点からニューラルネットワークモデルを概観し、自然言語研究者がニューラルネットワーク技術を理解できるよう支援します。チュートリアルでは、自然言語タスクの入力エンコーディング、フィードフォワードネットワーク、畳み込みネットワーク、リカレントネットワーク、再帰ネットワーク、そして自動勾配計算のための計算グラフ抽象化を取り上げます。

PDT Logic: A Probabilistic Doxastic Temporal Logic for Reasoning about Beliefs in Multi-agent Systems

PDT Logic: A Probabilistic Doxastic Temporal Logic for Reasoning about Beliefs in Multi-agent Systems / PDT論理：マルチエージェントシステムにおける信念推論のための確率的ドクサスティック時相論理

We present Probabilistic Doxastic Temporal (PDT) Logic, a formalism to represent and reason about probabilistic beliefs and their temporal evolution in multi-agent systems. This formalism enables the quantification of agents beliefs through probability intervals and incorporates an explicit notion of time. We discuss how over time agents dynamically change their beliefs in facts, temporal rules, and other agents beliefs with respect to any new information they receive. We introduce an appropriate formal semantics for PDT Logic and show that it is decidable. Alternative options of specifying problems in PDT Logic are possible. For these problem specifications, we develop different satisfiability checking algorithms and provide complexity results for the respective decision problems. The use of probability intervals enables a formal representation of probabilistic knowledge without enforcing (possibly incorrect) exact probability values. By incorporating an explicit notion of time, PDT Logic provides enriched possibilities to represent and reason about temporal relations.



確率的信念とその時間的変化をマルチエージェントシステムで表現し推論するための形式である確率的ドクサスティック時間的論理（PDT）を紹介します。この形式は、エージェントの信念を確率区間を通して定量化することを可能にし、明示的な時間の概念を組み込んでいます。エージェントが、受け取る新しい情報に応じて、事実、時間的ルール、および他のエージェントの信念に関する信念を、時間の経過とともにどのように動的に変化させるかについて議論します。PDTロジックの適切な形式意味論を導入し、それが決定可能であることを示します。PDTロジックで問題を規定する代替オプションが可能です。これらの問題仕様に対して、異なる充足可能性チェックアルゴリズムを開発し、それぞれの決定問題に対する計算量結果を提供します。確率区間の使用により、（おそらくは不正確な）正確な確率値を強制することなく、確率的知識の形式表現が可能になります。明示的な時間の概念を取り入れることで、PDTロジックは時間的関係を表現および推論するための豊富な可能性を提供します。

Embarrassingly Parallel Search in Constraint Programming

Embarrassingly Parallel Search in Constraint Programming / 制約プログラミングにおける驚異的並列探索

We introduce an Embarrassingly Parallel Search (EPS) method for solving constraint problems in parallel, and we show that this method matches or even outperforms state-of-the-art algorithms on a number of problems using various computing infrastructures. EPS is a simple method in which a master decomposes the problem into many disjoint subproblems which are then solved independently by workers. Our approach has three advantages: it is an efficient method; it involves almost no communication or synchronization between workers; and its implementation is made easy because the master and the workers rely on an underlying constraint solver, but does not require to modify it. This paper describes the method, and its applications to various constraint problems (satisfaction, enumeration, optimization). We show that our method can be adapted to different underlying solvers (Gecode, Choco2, OR-tools) on different computing infrastructures (multi-core, data centers, cloud computing). The experiments cover unsatisfiable, enumeration and optimization problems, but do not cover first solution search because it makes the results hard to analyze. The same variability can be observed for optimization problems, but at a lesser extent because the optimality proof is required. EPS offers good average performance, and matches or outperforms other available parallel implementations of Gecode as well as some solvers portfolios. Moreover, we perform an in-depth analysis of the various factors that make this approach efficient as well as the anomalies that can occur. Last, we show that the decomposition is a key component for efficiency and load balancing.



制約問題を並列に解決するための恥ずかしいほど並列検索（EPS）手法を導入し、この手法がさまざまなコンピューティングインフラストラクチャを使用して、いくつかの問題に対して最先端のアルゴリズムに匹敵するか、さらにはそれを上回るパフォーマンスを発揮することを示します。EPSは、マスターが問題を多数の互いに素な部分問題に分解し、各ワーカーがそれらを独立して解くというシンプルな手法です。本手法には3つの利点があります。効率的な手法であること、ワーカー間の通信や同期がほとんど不要なこと、そしてマスターとワーカーが基盤となる制約ソルバーに依存しながらも、ソルバーを変更する必要がないため実装が容易であることです。本論文では、本手法と、様々な制約問題（充足問題、列挙問題、最適化問題）への応用について説明します。本手法は、様々なコンピューティングインフラストラクチャ（マルチコア、データセンター、クラウドコンピューティング）上の様々な基盤ソルバー（Gecode、Choco2、OR-tools）に適応できることを示します。実験は、充足不可能問題、列挙問題、最適化問題をカバーしていますが、結果の分析が困難になるため、第一解探索はカバーしていません。最適化問題でも同様のばらつきが見られますが、最適性の証明が必要となるため、そのばらつきは小さくなります。EPSは平均的に良好な性能を示し、他の利用可能なGecodeの並列実装や一部のソルバーポートフォリオと同等かそれ以上の性能を発揮します。さらに、このアプローチを効率的にする様々な要因と、発生する可能性のある異常について詳細な分析を行います。最後に、分解が効率性と負荷分散の重要な要素であることを示します。

ProMoca: Probabilistic Modeling and Analysis of Agents in Commitment Protocols

ProMoca: Probabilistic Modeling and Analysis of Agents in Commitment Protocols / ProMoca：コミットメントプロトコルにおけるエージェントの確率的モデリングと分析

Social commitment protocols regulate interactions of agents in multiagent systems. Several methods have been developed to analyze properties of commitment protocols. However, analysis of an agent’s behavior in a commitment protocol, which should take into account the agent’s goals and beliefs, has received less attention. In this paper we present ProMoca framework to address this issue. Firstly, we develop an expressive formal language to model agents with respect to their commitments. Our language provides dedicated elements to define commitment protocols, and model agents in terms of their goals, behaviors, and beliefs. Furthermore, our language provides probabilistic and non-deterministic elements to model uncertainty in agents’ beliefs. Secondly, we identify two essential properties of an agent with respect to a commitment protocol, namely compliance and goal satisfaction. We formalize these properties using a probabilistic variant of linear temporal logic. Thirdly, we adapt a probabilistic model checking algorithm to automatically analyze compliance and goal satisfaction properties. Finally, we present empirical results about efficiency and scalability of ProMoca.



社会的コミットメントプロトコルは、マルチエージェントシステムにおけるエージェントの相互作用を規定します。コミットメントプロトコルの特性を分析する手法は数多く開発されています。しかし、コミットメントプロトコルにおけるエージェントの行動分析は、エージェントの目標と信念を考慮に入れるべきであり、これまであまり注目されてこなかった。本稿では、この問題に対処するためのProMocaフレームワークを提示します。まず、エージェントのコミットメントをモデル化するための表現力豊かな形式言語を開発します。この言語は、コミットメントプロトコルを定義し、エージェントを目標、行動、信念の観点からモデル化するための専用要素を提供します。さらに、エージェントの信念における不確実性をモデル化するために、確率的要素と非決定的要素を提供します。次に、コミットメントプロトコルに関するエージェントの2つの重要な特性、すなわちコンプライアンスと目標満足度を特定します。これらの特性は、線形時相論理の確率的変種を用いて形式化します。最後に、確率的モデル検査アルゴリズムを適用し、コンプライアンスと目標満足度の特性を自動的に分析します。最後に、ProMocaの効率性とスケーラビリティに関する実証結果を示す。

A Survey of Computational Treatments of Biomolecules by Robotics-Inspired Methods Modeling Equilibrium Structure and Dynamic

A Survey of Computational Treatments of Biomolecules by Robotics-Inspired Methods Modeling Equilibrium Structure and Dynamic / ロボット工学に着想を得た手法による生体分子の計算処理のサーベイ：平衡構造と動態のモデリング

More than fifty years of research in molecular biology have demonstrated that the ability of small and large molecules to interact with one another and propagate the cellular processes in the living cell lies in the ability of these molecules to assume and switch between specific structures under physiological conditions. Elucidating biomolecular structure and dynamics at equilibrium is therefore fundamental to furthering our understandingof biological function, molecular mechanisms in the cell, our own biology, disease, and disease treatments. By now, there is a wealth of methods designed to elucidate biomolecular structure and dynamics contributed from diverse scientific communities. In this survey, we focus on recent methods contributed from the Robotics community that promise to address outstanding challenges regarding the disparate length and time scales that characterize dynamic molecular processes in the cell. In particular, we survey robotics-inspired methods designed to obtain efficient representations of structure spaces of molecules in isolation or in assemblies for the purpose of characterizing equilibrium structure and dynamics. While an exhaustive review is an impossible endeavor, this survey balances the description of important algorithmic contributions with a critical discussion of outstanding computational challenges. The objective is to spur further research to address outstanding challenges in modeling equilibrium biomolecular structure and dynamics.



50年以上にわたる分子生物学研究により、小分子と大分子が相互作用し、生細胞内で細胞プロセスを伝播させる能力は、これらの分子が生理学的条件下で特定の構造を取り、それらを切り替える能力にかかっていることが実証されています。したがって、平衡状態における生体分子の構造とダイナミクスを解明することは、生物学的機能、細胞内の分子メカニズム、私たち自身の生物学、疾患、そして疾患治療に関する理解を深めるための基礎となります。現在までに、様々な科学コミュニティから、生体分子の構造とダイナミクスを解明するために設計された豊富な手法が提案されています。本調査では、細胞内の動的な分子プロセスを特徴付ける多様な長さと時間スケールに関する未解決の課題を解決することが期待される、ロボティクスコミュニティから提案された最新の手法に焦点を当てます。特に、平衡状態における構造とダイナミクスを特徴付けるために、分子の単独または集合体における構造空間の効率的な表現を得るために設計された、ロボティクスに着想を得た手法を概説します。網羅的なレビューは不可能ですが、本サーベイでは、重要なアルゴリズムの貢献の説明と、未解決の計算課題に関する批判的な議論をバランスよく取り入れています。その目的は、平衡状態の生体分子構造とダイナミクスのモデリングにおける未解決の課題に対処するための更なる研究を促進することです。

Convergence of Iterative Scoring Rules

Convergence of Iterative Scoring Rules / 反復スコアリングルールの収束

In multiagent systems, social choice functions can help aggregate the distinct preferences that agents have over alternatives, enabling them to settle on a single choice. Despite the basic manipulability of all reasonable voting systems, it would still be desirable to find ways to reach plausible outcomes, which are stable states, i.e., a situation where no agent would wish to change its vote. One possibility is an iterative process in which, after everyone initially votes, participants may change their votes, one voter at a time. This technique, explored in previous work, converges to a Nash equilibrium when Plurality voting is used, along with a tie-breaking rule that chooses a winner according to a linear order of preferences over candidates.In this paper, we both consider limitations of the iterative voting method, as well as expanding upon it. We demonstrate the significance of tie-breaking rules, showing that no iterative scoring rule converges for all tie-breaking. However, using a restricted tie-breaking rule (such as the linear order rule used in previous work) does not by itself ensure convergence. We prove that in addition to plurality, the veto voting rule converges as well using a linear order tie-breaking rule. However, we show that these two voting rules are the only scoring rules that converge, regardless of tie-breaking mechanism.



マルチエージェントシステムにおいて、社会的選択関数は、エージェントが選択肢に対して持つ明確な選好を集約し、単一の選択肢に落ち着かせるのに役立ちます。あらゆる合理的な投票システムは基本的に操作可能ですが、それでもなお、安定状態、すなわちどのエージェントも投票を変更したくない状況、つまり妥当な結果に到達する方法を見つけることが望ましいでしょう。一つの可能​​性として、全員が最初に投票した後、参加者が一人ずつ投票を変更できる反復プロセスが挙げられます。以前の研究で検討されたこの手法は、候補者に対する優先順位の線形順序に従って勝者を選択するタイブレークルールとともに、多数決投票を使用すると、ナッシュ均衡に収束します。この論文では、反復投票法の限界を検討するとともに、それを拡張します。タイブレークルールの重要性を示し、反復スコアリングルールがすべてのタイブレークに対して収束しないことを示します。ただし、制限されたタイブレークルール(以前の研究で使用された線形順序ルールなど)を使用するだけでは、収束が保証されるわけではありません。多数決に加えて、拒否権投票ルールも線形順序タイブレークルールを使用して収束することを証明します。ただし、タイブレークメカニズムに関係なく、これらの2つの投票ルールが収束する唯一のスコアリングルールであることを示します。

ZERO++: Harnessing the Power of Zero Appearances to Detect Anomalies in Large-Scale Data Sets

ZERO++: Harnessing the Power of Zero Appearances to Detect Anomalies in Large-Scale Data Sets / ZERO++：大規模データにおける異常検出のためのゼロ出現の力の活用集合

This paper introduces a new unsupervised anomaly detector called ZERO++ which employs the number of zero appearances in subspaces to detect anomalies in categorical data. It is unique in that it works in regions of subspaces that are not occupied by data; whereas existing methods work in regions occupied by data. ZERO++ examines only a small number of low dimensional subspaces to successfully identify anomalies. Unlike existing frequency-based algorithms, ZERO++ does not involve subspace pattern searching. We show that ZERO++ is better than or comparable with the state-of-the-art anomaly detection methods over a wide range of real-world categorical and numeric data sets; and it is efficient with linear time complexity and constant space complexity which make it a suitable candidate for large-scale data sets.



本稿では、カテゴリデータ内の異常を検出するために部分空間におけるゼロの出現回数を用いる、新しい教師なし異常検出器ZERO++を紹介します。既存の手法がデータで占められた領域で動作するのに対し、ZERO++はデータで占められていない部分空間の領域で動作するという点で独特です。ZERO++は、少数の低次元部分空間のみを検査して異常を正常に識別します。既存の頻度ベースのアルゴリズムとは異なり、ZERO++は部分空間パターン検索を必要としません。本稿では、ZERO++が、実世界の幅広いカテゴリデータおよび数値データセットにおいて、最先端の異常検出手法よりも優れているか、同等であることを示します。また、線形時間計算量と定数空間計算量で効率的であるため、大規模データセットに適しています。

P-SyncBB: A Privacy Preserving Branch and Bound DCOP Algorithm

P-SyncBB: A Privacy Preserving Branch and Bound DCOP Algorithm / P-SyncBB：プライバシー保護型分岐限定法DCOPアルゴリズム

Distributed constraint optimization problems enable the representation of many combinatorial problems that are distributed by nature. An important motivation for such problems is to preserve the privacy of the participating agents during the solving process. The present paper introduces a novel privacy-preserving branch and bound algorithm for this purpose. The proposed algorithm, P-SyncBB, preserves constraint, topology and decision privacy. The algorithm requires secure solutions to several multi-party computation problems. Consequently, appropriate novel secure protocols are devised and analyzed. An extensive experimental evaluation on different benchmarks, problem sizes, and constraint densities shows that P-SyncBB exhibits superior performance to other privacy-preserving complete DCOP algorithms.



分散制約最適化問題は、本質的に分散している多くの組み合わせ問題の表現を可能にします。このような問題に対する重要な動機は、解決プロセス中に参加しているエージェントのプライバシーを保護することです。本論文では、この目的のために、プライバシー保護型分岐限定アルゴリズム（P-SyncBB）を新たに提案します。提案アルゴリズムは、制約、トポロジ、および決定のプライバシーを保護します。このアルゴリズムは、複数のマルチパーティ計算問題に対する安全な解法を必要とします。そこで、適切な新しい安全なプロトコルを考案し、分析します。様々なベンチマーク、問題規模、制約密度を用いた広範な実験評価により、P-SyncBBは他のプライバシー保護型完全DCOPアルゴリズムよりも優れた性能を示すことが示されました。

A Disaster Response System based on Human-Agent Collectives

A Disaster Response System based on Human-Agent Collectives / 人間・エージェント集団に基づく災害対応システム

Major natural or man-made disasters such as Hurricane Katrina or the 9/11 terror attacks pose significant challenges for emergency responders. First, they have to develop an understanding of the unfolding event either using their own resources or through third-parties such as the local population and agencies. Second, based on the information gathered, they need to deploy their teams in a flexible manner, ensuring that each team performs tasks in The most effective way. Third, given the dynamic nature of a disaster space, and the uncertainties involved in performing rescue missions, information about the disaster space and the actors within it needs to be managed to ensure that responders are always acting on up-to-date and trusted information. Against this background, this paper proposes a novel disaster response system called HAC-ER. Thus HAC-ER interweaves humans and agents, both robotic and software, in social relationships that augment their individual and collective capabilities. To design HAC-ER, we involved end-users including both experts and volunteers in a several participatory design workshops, lab studies, and field trials of increasingly advanced prototypes of individual components of HAC-ER as well as the overall system. This process generated a number of new quantitative and qualitative results but also raised a number of new research questions. HAC-ER thus demonstrates how such Human-Agent Collectives (HACs) can address key challenges in disaster response. Specifically, we show how HAC-ER utilises crowdsourcing combined with machine learning to obtain most important situational awareness from large streams of reports posted by members of the public and trusted organisations. We then show how this information can inform human-agent teams in coordinating multi-UAV deployments, as well as task planning for responders on the ground. Finally, HAC-ER incorporates an infrastructure and the associated intelligence for tracking and utilising the provenance of information shared across the entire system to ensure its accountability. We individually validate each of these elements of HAC-ER and show how they perform against standard (non-HAC) baselines and also elaborate on the evaluation of the overall system.



ハリケーン・カトリーナや9/11の同時多発テロのような大規模な自然災害や人為的災害は、緊急対応要員にとって大きな課題を突きつける。まず、自らの資源、あるいは地元住民や関係機関などの第三者の情報を活用して、発生しつつある事態を把握する必要があります。次に、収集した情報に基づいて柔軟にチームを配置し、各チームが最も効果的な方法で任務を遂行できるようにする必要があります。さらに、災害現場の動的な性質や救助活動には不確実性も伴うため、災害現場とその中の関係者に関する情報を管理し、対応要員が常に最新かつ信頼できる情報に基づいて行動できるようにする必要があります。このような背景から、本稿では、HAC-ERと呼ばれる新たな災害対応システムを提案します。HAC-ERは、人間とエージェント（ロボットとソフトウェアの両方）を社会的関係に織り交ぜ、個々の能力と集団的能力を強化します。HAC-ERを設計するために、私たちは専門家とボランティアの両方を含むエンドユーザーを、参加型設計ワークショップ、ラボ研究、そしてHAC-ERの個々のコンポーネントとシステム全体のますます高度なプロトタイプのフィールド試験に参加させました。このプロセスは、多くの新しい定量的および定性的な結果を生み出しましたが、多くの新しい研究課題も提起しました。したがって、HAC-ERは、このようなヒューマンエージェントコレクティブ(HAC)が災害対応における主要な課題にどのように対処できるかを示しています。具体的には、HAC-ERがクラウドソーシングと機械学習を組み合わせて、一般の人々と信頼できる組織によって投稿された大量のレポートから最も重要な状況認識を取得する方法を示します。次に、この情報がヒューマンエージェントチームに複数のUAV展開の調整や、地上の対応者のタスク計画にどのように役立つかを示します。最後に、HAC-ERは、システム全体で共有される情報の出所を追跡および利用してその説明責任を確保するためのインフラストラクチャと関連インテリジェンスを組み込んでいます。HAC-ERのこれらの各要素を個別に検証し、標準(非HAC)ベースラインに対してどのように機能するかを示し、システム全体の評価についても詳しく説明します。

参考文献

• Journal of Artificial Intelligence Resarch Vol. 57 (2016)

関連情報

• Journal of Artificial Intelligence Research: 論文一覧