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

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

論文

ASNets: Deep Learning for Generalised Planning

ASNets: Deep Learning for Generalised Planning / ASNet：一般化計画のためのディープラーニング

In this paper, we discuss the learning of generalised policies for probabilistic and classical planning problems using Action Schema Networks (ASNets). The ASNet is a neural network architecture that exploits the relational structure of (P)PDDL planning problems to learn a common set of weights that can be applied to any problem in a domain. By mimicking the actions chosen by a traditional, non-learning planner on a handful of small problems in a domain, ASNets are able to learn a generalised reactive policy that can quickly solve much larger instances from the domain. This work extends the ASNet architecture to make it more expressive, while still remaining invariant to a range of symmetries that exist in PPDDL problems. We also present a thorough experimental evaluation of ASNets, including a comparison with heuristic search planners on seven probabilistic and deterministic domains, an extended evaluation on over 18,000 Blocksworld instances, and an ablation study. Finally, we show that sparsity-inducing regularisation can produce ASNets that are compact enough for humans to understand, yielding insights into how the structure of ASNets allows them to generalise across a domain.



本稿では、アクションスキーマネットワーク（ASNet）を用いた確率的および古典的な計画問題に対する一般化ポリシーの学習について説明します。ASNetは、(P)PDDL計画問題の関係構造を利用して、ドメイン内のあらゆる問題に適用できる共通の重みセットを学習するニューラルネットワークアーキテクチャです。ASNetは、あるドメイン内の少数の小さな問題に対して従来の非学習型プランナーが選択したアクションを模倣することで、そのドメインからより大規模なインスタンスを迅速に解決できる一般化された反応型ポリシーを学習することができます。本研究では、ASNetアーキテクチャを拡張して表現力を高めつつ、PPDDL問題に存在するさまざまな対称性に対して不変なままにしています。また、7つの確率的および決定論的ドメインにおけるヒューリスティック探索プランナーとの比較、18,000を超えるBlocksworldインスタンスの拡張評価、アブレーション研究など、ASNetの徹底的な実験評価も示します。最後に、スパース性誘導型正則化によって、人間が理解できるほどコンパクトなASNetを生成できることを示し、ASNetの構造がどのようにドメイン全体での一般化を可能にするかについての洞察をもたらします。

Variational Bayes In Private Settings (VIPS)

Variational Bayes In Private Settings (VIPS) / プライベート設定における変分ベイズ（VIPS）

Many applications of Bayesian data analysis involve sensitive information such as personal documents or medical records, motivating methods which ensure that privacy is protected. We introduce a general privacy-preserving framework for Variational Bayes (VB), a widely used optimization-based Bayesian inference method. Our framework respects differential privacy, the gold-standard privacy criterion, and encompasses a large class of probabilistic models, called the Conjugate Exponential (CE) family. We observe that we can straightforwardly privatise VB’s approximate posterior distributions for models in the CE family, by perturbing the expected sufficient statistics of the complete-data likelihood. For a broadly-used class of non-CE models, those with binomial likelihoods, we show how to bring such models into the CE family, such that inferences in the modified model resemble the private variational Bayes algorithm as closely as possible, using the Pólya-Gamma data augmentation scheme. The iterative nature of variational Bayes presents a further challenge since iterations increase the amount of noise needed. We overcome this by combining: (1) an improved composition method for differential privacy, called the moments accountant, which provides a tight bound on the privacy cost of multiple VB iterations and thus significantly decreases the amount of additive noise; and (2) the privacy amplification effect of subsampling mini-batches from large-scale data in stochastic learning. We empirically demonstrate the effectiveness of our method in CE and non-CE models including latent Dirichlet allocation, Bayesian logistic regression, and sigmoid belief networks, evaluated on real-world datasets.



ベイズデータ分析の多くのアプリケーションでは、個人文書や医療記録などの機密情報が扱われるため、プライバシーを確​​実に保護する方法が求められます。本稿では、広く使用されている最適化ベースのベイズ推論法である変分ベイズ（VB）の一般的なプライバシー保護フレームワークを紹介します。本フレームワークは、ゴールドスタンダードのプライバシー基準である差分プライバシーを尊重し、共役指数（CE）ファミリーと呼ばれる大規模な確率モデルを網羅しています。CEファミリーのモデルについては、完全データ尤度の期待十分統計量を摂動することで、VBの近似事後分布を簡単にプライベート化できることを観察します。広く使用されている非CEモデル（二項尤度を持つモデル）については、ポリア・ガンマデータ拡張スキームを使用して、修正モデルの推論がプライベート変分ベイズアルゴリズムに可能な限り近くなるように、そのようなモデルをCEファミリーに組み込む方法を示します。変分ベイズの反復的な性質は、反復によって必要なノイズの量が増加するため、さらなる課題を提示します。我々は、(1)モーメント会計と呼ばれる差分プライバシーのための改良された合成法、すなわち複数の変分ベイズ反復のプライバシーコストに厳密な上限を提供し、加法性ノイズの量を大幅に削減すること、および(2)確率学習において大規模データからミニバッチをサブサンプリングすることによるプライバシー増幅効果を組み合わせることで、この問題を克服します。我々は、潜在ディリクレ配分、ベイズロジスティック回帰、シグモイドビリーフネットワークなどのCEモデルと非CEモデルにおいて、実世界のデータセットで評価した本手法の有効性を実証します。

Towards Knowledgeable Supervised Lifelong Learning Systems

Towards Knowledgeable Supervised Lifelong Learning Systems / 知識に基づく教師あり生涯学習システムに向けて

Learning a sequence of tasks is a long-standing challenge in machine learning. This setting applies to learning systems that observe examples of a range of tasks at different points in time. A learning system should become more knowledgeable as more related tasks are learned. Although the problem of learning sequentially was acknowledged for the first time decades ago, the research in this area has been rather limited. Research in transfer learning, multitask learning, metalearning and deep learning has studied some challenges of these kinds of systems. Recent research in lifelong machine learning and continual learning has revived interest in this problem. We propose Proficiente, a full framework for long-term learning systems. Proficiente relies on knowledge transferred between hypotheses learned with Support Vector Machines. The first component of the framework is focused on transferring forward selectively from a set of existing hypotheses or functions representing knowledge acquired during previous tasks to a new target task. A second component of Proficiente is focused on transferring backward, a novel ability of long-term learning systems that aim to exploit knowledge derived from recent tasks to encourage refinement of existing knowledge. We propose a method that transfers selectively from a task learned recently to existing hypotheses representing previous tasks. The method encourages retention of existing knowledge whilst refining. We analyse the theoretical properties of the proposed framework. Proficiente is accompanied by an agnostic metric that can be used to determine if a long-term learning system is becoming more knowledgeable. We evaluate Proficiente in both synthetic and real-world datasets, and demonstrate scenarios where knowledgeable supervised learning systems can be achieved by means of transfer.



一連のタスクを学習することは、機械学習における長年の課題です。この設定は、さまざまなタスクの例を異なる時点で観察する学習システムに適用されます。学習システムは、より多くの関連タスクを学習するほど、より多くの知識を持つようになります。逐次学習の問題は数十年前に初めて認識されましたが、この分野の研究はかなり限られていました。転移学習、マルチタスク学習、メタ学習、ディープラーニングといった研究では、これらの種類のシステムが抱える課題がいくつか研究されてきました。近年の生涯機械学習と継続学習に関する研究により、この問題への関心が再燃しています。本稿では、長期学習システムのための包括的なフレームワークであるProficienteを提案します。Proficienteは、サポートベクターマシンを用いて学習された仮説間で転移される知識を活用します。このフレームワークの最初の構成要素は、過去のタスクで獲得した知識を表す既存の仮説または関数群から、新しいターゲットタスクへと選択的に転移することに焦点を当てています。Proficienteの2つ目の構成要素は、転移後進性に焦点を当てています。これは、最近のタスクから得られた知識を活用して既存の知識の洗練を促進することを目的とする、長期学習システムの新しい能力です。本稿では、最近学習したタスクから過去のタスクを表す既存の仮説へと選択的に転移する手法を提案します。この手法は、洗練を進めながらも既存の知識の保持を促進します。本稿では、提案されたフレームワークの理論的特性を分析します。Proficienteには、長期学習システムがより知識を獲得しているかどうかを判断するために使用できる、アグノスティックな指標が付属しています。Proficienteを合成データセットと実世界データセットの両方で評価し、知識に基づく教師あり学習システムを転移によって実現できるシナリオを示します。

Improving Nash Social Welfare Approximations

Improving Nash Social Welfare Approximations / ナッシュ社会福祉近似の改善

We consider the problem of fairly allocating a set of indivisible goods among n agents. Various fairness notions have been proposed within the rapidly growing field of fair division, but the Nash social welfare (NSW) serves as a focal point. In part, this follows from the ‘unreasonable’ fairness guarantees provided, in the sense that a max NSW allocation meets multiple other fairness metrics simultaneously, all while satisfying a standard economic concept of efficiency, Pareto optimality. However, existing approximation algorithms fail to satisfy all of the remarkable fairness guarantees offered by a max NSW allocation, instead targeting only the specific NSW objective. We address this issue by presenting a 2 max NSW, Prop-1, 1/(2n) MMS, and Pareto optimal allocation in strongly polynomial time. Our techniques are based on a market interpretation of a fractional max NSW allocation. We present novel definitions of fairness concepts in terms of market prices, and design a new scheme to round a market equilibrium into an integral allocation in a way that provides most of the fairness properties of an integral max NSW allocation.



n個のエージェント間で分割不可能な財の集合を公平に配分する問題を考察します。急速に発展している公平配分の分野では様々な公平性の概念が提案されていますが、ナッシュ社会福祉（NSW）が中心的な概念となっています。これは、最大NSW配分が他の複数の公平性指標を同時に満たし、同時に効率性の標準的な経済概念であるパレート最適性も満たすという意味で、提供される「不合理な」公平性保証に一部起因します。しかし、既存の近似アルゴリズムは、最大NSW配分によって提供される注目すべき公平性保証のすべてを満たすことができず、特定のNSW目標のみを対象としています。この問題に対処するため、我々は2最大NSW、Prop-1、1/(2n) MMS、およびパレート最適配分を強多項式時間で提示します。私たちの手法は、分数最大NSW配分の市場解釈に基づいています。我々は、市場価格の観点から公平性の概念の新しい定義を提示し、整数最大NSW配分の公平性特性のほとんどを提供する方法で、市場均衡を整数配分に丸める新しいスキームを設計します。

Bridging the Gap Between Probabilistic Model Checking and Probabilistic Planning: Survey, Compilations, and Empirical Comparison

Bridging the Gap Between Probabilistic Model Checking and Probabilistic Planning: Survey, Compilations, and Empirical Comparison / 確率的モデル検査と確率的計画のギャップを埋める：サーベイ、コンパイル、および実証的比較

Markov decision processes are of major interest in the planning community as well as in the model checking community. But in spite of the similarity in the considered formal models, the development of new techniques and methods happened largely independently in both communities. This work is intended as a beginning to unite the two research branches. We consider goal-reachability analysis as a common basis between both communities. The core of this paper is the translation from Jani, an overarching input language for quantitative model checkers, into the probabilistic planning domain definition language (PPDDL), and vice versa from PPDDL into Jani. These translations allow the creation of an overarching benchmark collection, including existing case studies from the model checking community, as well as benchmarks from the international probabilistic planning competitions (IPPC). We use this benchmark set as a basis for an extensive empirical comparison of various approaches from the model checking community, variants of value iteration, and MDP heuristic search algorithms developed by the AI planning community. On a per benchmark domain basis, techniques from one community can achieve state-ofthe-art performance in benchmarks of the other community. Across all benchmark domains of one community, the performance comparison is however in favor of the solvers and algorithms of that particular community. Reasons are the design of the benchmarks, as well as tool-related limitations. Our translation methods and benchmark collection foster crossfertilization between both communities, pointing out specific opportunities for widening the scope of solvers to different kinds of models, as well as for exchanging and adopting algorithms across communities.



マルコフ決定過程は、計画コミュニティとモデル検査コミュニティの両方において大きな関心を集めています。しかし、検討対象となる形式モデルの類似性にもかかわらず、新しい技術や手法の開発は両コミュニティでほぼ独立して行われました。本研究は、これら2つの研究分野を統合するための第一歩となることを目的としています。目標到達可能性分析は、両コミュニティの共通基盤であると考えています。本論文の中核は、定量的モデル検査のための包括的な入力言語であるJaniから確率的計画領域定義言語（PPDDL）への翻訳、そしてPPDDLからJaniへの翻訳です。これらの翻訳により、モデル検査コミュニティによる既存のケーススタディや、国際確率的計画コンペティション（IPPC）のベンチマークを含む包括的なベンチマークコレクションを作成できます。このベンチマークセットを基盤として、モデル検査コミュニティの様々なアプローチ、価値反復法の変種、そしてAI計画コミュニティによって開発されたMDPヒューリスティック探索アルゴリズムを、広範囲に実証的に比較します。ベンチマークドメインごとに見ると、あるコミュニティの技術は、他のコミュニティのベンチマークにおいて最先端のパフォーマンスを達成できます。しかしながら、あるコミュニティのすべてのベンチマークドメインにおいて、パフォーマンス比較では、そのコミュニティのソルバーとアルゴリズムの方が有利です。その理由は、ベンチマークの設計とツール関連の制限です。私たちの翻訳手法とベンチマークコレクションは、両コミュニティ間の相互交流を促進し、ソルバーの適用範囲を異なる種類のモデルに拡張する具体的な機会や、コミュニティ間でアルゴリズムを交換・採用する機会を示唆しています。

Sliding-Window Thompson Sampling for Non-Stationary Settings

Sliding-Window Thompson Sampling for Non-Stationary Settings / 非定常設定におけるスライディングウィンドウ・トンプソンサンプリング

Multi-Armed Bandit (MAB) techniques have been successfully applied to many classes of sequential decision problems in the past decades. However, non-stationary settings — very common in real-world applications — received little attention so far, and theoretical guarantees on the regret are known only for some frequentist algorithms. In this paper, we propose an algorithm, namely Sliding-Window Thompson Sampling (SW-TS), for nonstationary stochastic MAB settings. Our algorithm is based on Thompson Sampling and exploits a sliding-window approach to tackle, in a unified fashion, two different forms of non-stationarity studied separately so far: abruptly changing and smoothly changing. In the former, the reward distributions are constant during sequences of rounds, and their change may be arbitrary and happen at unknown rounds, while, in the latter, the reward distributions smoothly evolve over rounds according to unknown dynamics. Under mild assumptions, we provide regret upper bounds on the dynamic pseudo-regret of SW-TS for the abruptly changing environment, for the smoothly changing one, and for the setting in which both the non-stationarity forms are present. Furthermore, we empirically show that SW-TS dramatically outperforms state-of-the-art algorithms even when the forms of non-stationarity are taken separately, as previously studied in the literature.



過去数十年にわたり、多腕バンディット(MAB)手法は多くの種類の逐次決定問題に適用され、成功を収めてきました。しかし、非定常設定(実際のアプリケーションでは非常に一般的)はこれまでほとんど注目されてこなかったため、後悔に関する理論的な保証は一部の頻度主義アルゴリズムでのみ知られています。本稿では、非定常確率的MAB設定のためのアルゴリズム、すなわちスライディングウィンドウ トンプソン サンプリング(SW-TS)を提案します。私たちのアルゴリズムはトンプソン サンプリングに基づいており、スライディングウィンドウ アプローチを利用して、これまで別々に研究されてきた2つの異なる形式の非定常性(急激な変化と滑らかな変化)に統一的に対処します。前者では、報酬分布は一連のラウンドで一定であり、その変化は任意で、未知のラウンドで発生する可能性があります。一方、後者では、報酬分布は未知のダイナミクスに従ってラウンドにわたって滑らかに進化します。緩やかな仮定の下、急激に変化する環境、滑らかに変化する環境、そして非定常性の両方の形式が存在する設定について、SW-TSの動的擬似後悔の後悔上界を与える。さらに、文献で以前に研究されているように、非定常性の形式を個別に考慮した場合でも、SW-TSは最先端のアルゴリズムを大幅に上回る性能を発揮することを経験的に示す。

Conservative Extensions in Horn Description Logics with Inverse Roles

Conservative Extensions in Horn Description Logics with Inverse Roles / 逆役割を持つホーン記述論理の保守的拡張

We investigate the decidability and computational complexity of conservative extensions and the related notions of inseparability and entailment in Horn description logics (DLs) with inverse roles. We consider both query conservative extensions, defined by requiring that the answers to all conjunctive queries are left unchanged, and deductive conservative extensions, which require that the entailed concept inclusions, role inclusions, and functionality assertions do not change. Upper bounds for query conservative extensions are particularly challenging because characterizations in terms of unbounded homomorphisms between universal models, which are the foundation of the standard approach to establishing decidability, fail in the presence of inverse roles. We resort to a characterization that carefully mixes unbounded and bounded homomorphisms and enables a decision procedure that combines tree automata and a mosaic technique. Our main results are that query conservative extensions are 2ExpTime-complete in all DLs between ELI and Horn-ALCHIF and between Horn-ALC and Horn-ALCHIF, and that deductive conservative extensions are 2ExpTime-complete in all DLs between ELI and ELHIF_bot. The same results hold for inseparability and entailment.



逆役割を持つホーン記述論理（DL）における保守的拡張と、関連する不可分性と含意の概念の決定可能性と計算複雑性を調査します。すべての連言クエリへの回答が変更されないことを要求することで定義されるクエリ保守的拡張と、含意される概念包含、役割包含、および機能性アサーションが変更されないことを要求する演繹的保守的拡張の両方を検討します。クエリ保守的拡張の上限は特に困難です。なぜなら、決定可能性を確立するための標準的なアプローチの基礎となる、普遍モデル間の非有界準同型による特徴付けは、逆役割の存在下では機能しないからです。私たちは、非有界準同型と有界準同型を慎重に組み合わせ、木オートマトンとモザイク技法を組み合わせた決定手順を可能にする特徴付けを採用しました。主な結果は、クエリ保守的拡張は、ELIとHorn-ALCHIF間およびHorn-ALCとHorn-ALCHIF間のすべてのDLにおいて2ExpTime完全であり、演繹保守的拡張は、ELIとELHIF_bot間のすべてのDLにおいて2ExpTime完全であるということです。同じ結果は、不可分性と含意についても当てはまります。

Predicting Strategic Behavior from Free Text

Predicting Strategic Behavior from Free Text / 自由記述テキストからの戦略的行動の予測

The connection between messaging and action is fundamental both to web applications, such as web search and sentiment analysis, and to economics. However, while prominent online applications exploit messaging in natural (human) language in order to predict non-strategic action selection, the economics literature focuses on the connection between structured stylized messaging to strategic decisions in games and multi-agent encounters. This paper aims to connect these two strands of research, which we consider highly timely and important due to the vast online textual communication on the web. Particularly, we introduce the following question: Can free text expressed in natural language serve for the prediction of action selection in an economic context, modeled as a gameIn order to initiate the research on this question, we introduce the study of an individual’s action prediction in a one-shot game based on free text he/she provides, while being unaware of the game to be played. We approach the problem by attributing commonsensical personality attributes via crowd-sourcing to free texts written by individuals, and employing transductive learning to predict actions taken by these individuals in one-shot games based on these attributes. Our approach allows us to train a single classifier that can make predictions with respect to actions taken in multiple games. In experiments with three well-studied games, our algorithm compares favorably with strong alternative approaches. In ablation analysis, we demonstrate the importance of our modeling choices—the representation of the text with the commonsensical personality attributes and our classifier—to the predictive power of our model.



メッセージングとアクションの関係は、Web検索や感情分析などのWebアプリケーションと経済学の両方にとって基本的なものです。しかし、主要なオンラインアプリケーションが自然言語（人間言語）によるメッセージングを利用して非戦略的行動選択を予測するのに対し、経済学の文献は、構造化され様式化されたメッセージングとゲームやマルチエージェントエンカウンターにおける戦略的意思決定との関連性に焦点を当てています。本論文は、ウェブ上の膨大なオンラインテキストコミュニケーションの存在を踏まえ、非常にタイムリーかつ重要なこれら2つの研究分野を結びつけることを目指しています。特に、以下の問いを提示します。自然言語で表現された自由記述は、ゲームとしてモデル化された経済的文脈における行動選択の予測に役立つでしょうか？この問いに関する研究の出発点として、個人がプレイするゲームを知らない状態で、提供された自由記述に基づいてワンショットゲームにおける行動予測を行う研究を紹介します。私たちはこの問題に、クラウドソーシングを通じて個人が記述した自由記述に常識的な性格属性を付与し、これらの属性に基づいてワンショットゲームにおける個人の行動をトランスダクティブラーニングを用いて予測することでアプローチします。このアプローチにより、複数のゲームにおける行動を予測できる単一の分類器を学習することが可能になります。3つのよく研究されたゲームを用いた実験において、私たちのアルゴリズムは強力な他のアプローチと比べても遜色ない結果を示しました。アブレーション分析では、モデルの選択（テキストを常識的な性格属性で表現することと分類器）が、モデルの予測力に及ぼす影響の重要性を示しました。

Automated Conjecturing II: Chomp and Reasoned Game Play

Automated Conjecturing II: Chomp and Reasoned Game Play / 自動推測II：チョンプと推論的ゲームプレイ

We demonstrate the use of a program that generates conjectures about positions of the combinatorial game Chomp—explanations of why certain moves are bad. These could be used in the design of a Chomp-playing program that gives reasons for its moves. We prove one of these Chomp conjectures—demonstrating that our conjecturing program can produce genuine Chomp knowledge.The conjectures are generated by a general purpose conjecturing program that was previously and successfully used to generate mathematical conjectures. Our program is initialized with Chomp invariants and example game boards—the conjectures take the form of invariant-relation statements interpreted to be true for all board positions of a certain kind. The conjectures describe a theory of Chomp positions.The program uses limited, natural input and suggests how theories generated on-the-fly might be used in a variety of situations where decisions—based on reasons—are required.



組み合わせゲームChompの位置についての推測(特定の動きが悪い理由の説明)を生成するプログラムの使用方法を示します。これらは、動きの理由を示すChompをプレイするプログラムの設計に使用できます。これらのChomp予想の1つを証明し、推測プログラムが本物のChomp知識を生成できることを実証します。予想は、以前に数学的予想を生成するために正常に使用された汎用推測プログラムによって生成されます。プログラムはChomp不変量とゲーム ボードの例で初期化されます。予想は、特定の種類のすべてのボードの位置に対して真であると解釈される不変関係ステートメントの形を取ります。予想はChompの位置の理論を記述します。プログラムは限定された自然な入力を使用し、理由に基づく決定が必要なさまざまな状況で、オンザフライで生成される理論をどのように使用できるかを示します。

Preferences Single-Peaked on a Circle

Preferences Single-Peaked on a Circle / 円周上の単峰性選好

We introduce the domain of preferences that are single-peaked on a circle, which is a generalization of the well-studied single-peaked domain. This preference restriction is useful, e.g., for scheduling decisions, certain facility location problems, and for one-dimensional decisions in the presence of extremist preferences. We give a fast recognition algorithm of this domain, provide a characterisation by finitely many forbidden subprofiles, and show that many popular single- and multi-winner voting rules are polynomial-time computable on this domain. In particular, we prove that Proportional Approval Voting can be computed in polynomial time for profiles that are single-peaked on a circle. In contrast, Kemeny’s rule remains hard to evaluate, and several impossibility results from social choice theory can be proved using only profiles in this domain.



我々は、円上に単峰性を持つ選好の領域を導入します。これは、よく研究されている単峰性領域の一般化です。この選好制約は、例えば、スケジュール決定、特定の施設配置問題、極端な選好が存在する場合の1次元決定などに有用です。我々は、この領域の高速認識アルゴリズムを示し、有限個の禁制サブプロファイルによる特徴付けを提供し、多くの一般的な単一および複数勝者投票規則がこの領域で多項式時間で計算可能であることを示す。特に、円上に単峰性を持つプロファイルに対して、比例承認投票が多項式時間で計算可能であることを証明します。対照的に、ケメニーの規則は依然として評価が困難であり、社会選択理論からのいくつかの不可能性の結果は、この領域のプロファイルのみを使用して証明できます。

Ontology Reasoning with Deep Neural Networks

Ontology Reasoning with Deep Neural Networks / ディープニューラルネットワークを用いたオントロジー推論

The ability to conduct logical reasoning is a fundamental aspect of intelligent human behavior, and thus an important problem along the way to human-level artificial intelligence. Traditionally, logic-based symbolic methods from the field of knowledge representation and reasoning have been used to equip agents with capabilities that resemble human logical reasoning qualities. More recently, however, there has been an increasing interest in using machine learning rather than logic-based symbolic formalisms to tackle these tasks. In this paper, we employ state-of-the-art methods for training deep neural networks to devise a novel model that is able to learn how to effectively perform logical reasoning in the form of basic ontology reasoning. This is an important and at the same time very natural logical reasoning task, which is why the presented approach is applicable to a plethora of important real-world problems. We present the outcomes of several experiments, which show that our model is able to learn to perform highly accurate ontology reasoning on very large, diverse, and challenging benchmarks. Furthermore, it turned out that the suggested approach suffers much less from different obstacles that prohibit logic-based symbolic reasoning, and, at the same time, is surprisingly plausible from a biological point of view.



論理的推論を行う能力は、知的な人間の行動の基本的な側面であり、したがって、人間レベルの人工知能への道のりにおける重要な問題です。従来、知識表現と推論の分野における論理ベースの記号的手法は、エージェントに人間の論理的推論特性に類似した能力を付与するために用いられてきました。しかし近年、これらのタスクに取り組むために、論理ベースの記号的形式論ではなく機械学習を用いることへの関心が高まっています。本論文では、最先端のディープニューラルネットワーク学習手法を用いて、基本的なオントロジー推論という形で論理的推論を効果的に実行する方法を学ぶことができる新たなモデルを考案します。これは重要でありながら、同時に非常に自然な論理的推論タスクであるため、提示するアプローチは多くの重要な実世界の問題に適用可能です。本論文では、いくつかの実験結果を提示します。これらの結果から、本モデルは、非常に大規模で多様かつ困難なベンチマークにおいて、高精度なオントロジー推論を学習できることが示されます。さらに、提案されたアプローチは、論理ベースの記号的推論を妨げる様々な障害の影響をはるかに少なく、同時に生物学的観点からも驚くほど妥当であることがわかりました。

Simulating Offender Mobility: Modeling Activity Nodes from Large-Scale Human Activity Data

Simulating Offender Mobility: Modeling Activity Nodes from Large-Scale Human Activity Data / 犯罪者の移動シミュレーション：大規模人間活動データからの活動ノードのモデリング

In recent years, simulation techniques have been applied to investigate the spatiotemporal dynamics of crime. Researchers have instantiated mobile offenders in agent-based simulations for theory testing, experimenting with crime prevention strategies, and exploring crime prediction techniques, despite facing challenges due to the complex dynamics of crime and the lack of detailed information about offender mobility. This paper presents a simulation model to explore offender mobility, focusing on the interplay between the agent’s awareness space and activity nodes. The simulation generates patterns of individual mobility aiming to cumulatively match crime patterns. To instantiate a realistic urban environment, we use open data to simulate the urban structure, location-based social networks data to represent activity nodes as a proxy for human activity, and taxi trip data as a proxy for human movement between regions of the city. We analyze and systematically compare 35 different mobility strategies and demonstrate the benefits of using large-scale human activity data to simulate offender mobility. The strategies combining taxi trip data or historic crime data with popular activity nodes perform best compared to other strategies, especially for robbery. Our approach provides a basis for building agent-based crime simulations that infer offender mobility in urban areas from real-world data.



近年、犯罪の時空間ダイナミクスを調査するためにシミュレーション技術が応用されています。研究者たちは、犯罪の複雑なダイナミクスと犯罪者の移動に関する詳細な情報の不足という課題に直面しながらも、理論検証、犯罪防止戦略の実験、犯罪予測技術の探究を目的として、エージェントベースシミュレーションにおいて移動犯罪者をインスタンス化してきた。本稿では、エージェントの認識空間と活動ノードの相互作用に焦点を当て、犯罪者の移動を調査するためのシミュレーションモデルを提示します。このシミュレーションは、犯罪パターンを累積的に一致させることを目指し、個々の移動パターンを生成します。現実的な都市環境をインスタンス化するために、オープンデータを用いて都市構造をシミュレートし、位置情報に基づくソーシャルネットワークデータを用いて活動ノードを人間の活動の代理として、そしてタクシー乗車データを都市内の地域間の人間の移動の代理として用います。35種類の異なる移動戦略を分析し、体系的に比較し、大規模な人間活動データを用いて犯罪者の移動をシミュレートすることの利点を示す。タクシー乗車データまたは過去の犯罪データを人気の活動ノードと組み合わせた戦略は、特に強盗において、他の戦略と比較して最も優れた結果を示した。我々のアプローチは、実世界データから都市部における犯罪者の移動を推測するエージェントベース犯罪シミュレーションを構築するための基盤を提供します。

Scalable Planning with Deep Neural Network Learned Transition Models

Scalable Planning with Deep Neural Network Learned Transition Models / ディープニューラルネットワーク学習遷移モデルを用いたスケーラブルなプランニング

In many complex planning problems with factored, continuous state and action spaces such as Reservoir Control, Heating Ventilation and Air Conditioning (HVAC), and Navigation domains, it is difficult to obtain a model of the complex nonlinear dynamics that govern state evolution. However, the ubiquity of modern sensors allows us to collect large quantities of data from each of these complex systems and build accurate, nonlinear deep neural network models of their state transitions. But there remains one major problem for the task of control – how can we plan with deep network learned transition models without resorting to Monte Carlo Tree Search and other black-box transition model techniques that ignore model structure and do not easily extend to continuous domains? In this paper, we introduce two types of planning methods that can leverage deep neural network learned transition models: Hybrid Deep MILP Planner (HD-MILP-Plan) and Tensorflow Planner (TF-Plan). In HD-MILP-Plan, we make the critical observation that the Rectified Linear Unit (ReLU) transfer function for deep networks not only allows faster convergence of model learning, but also permits a direct compilation of the deep network transition model to a Mixed-Integer Linear Program (MILP) encoding. Further, we identify deep network specific optimizations for HD-MILP-Plan that improve performance over a base encoding and show that we can plan optimally with respect to the learned deep networks. In TF-Plan, we take advantage of the efficiency of auto-differentiation tools and GPU-based computation where we encode a subclass of purely continuous planning problems as Recurrent Neural Networks and directly optimize the actions through backpropagation. We compare both planners and show that TF-Plan is able to approximate the optimal plans found by HD-MILP-Plan in less computation time. Hence this article offers two novel planners for continuous state and action domains with learned deep neural net transition models: one optimal method (HD-MILP-Plan) and a scalable alternative for large-scale problems (TF-Plan).



貯水池制御、暖房換気空調（HVAC）、ナビゲーション領域など、因子化された連続的な状態および行動空間を持つ多くの複雑な計画問題では、状態の進化を支配する複雑な非線形ダイナミクスのモデルを取得することは困難です。しかし、現代のセンサーの普及により、これらの複雑なシステムのそれぞれから大量のデータを収集し、それらの状態遷移の正確な非線形ディープニューラルネットワークモデルを構築することが可能になりました。しかし、制御タスクには1つの大きな問題が残っています。それは、モデル構造を無視し、連続領域への拡張が容易ではないモンテカルロ木探索やその他のブラックボックス遷移モデル手法に頼ることなく、ディープネットワーク学習遷移モデルを使用してどのように計画するかということです。本稿では、ディープニューラルネットワーク学習遷移モデルを活用できる2種類の計画手法、ハイブリッドディープMILPプランナー（HD-MILP-Plan）とTensorflowプランナー（TF-Plan）を紹介します。HD-MILP-Planでは、ディープネットワークのReLU（Rectified Linear Unit）伝達関数は、モデル学習の収束を高速化するだけでなく、ディープネットワーク遷移モデルをMILP（Mixed-Integer Linear Program）エンコーディングに直接コンパイルできるという重要な観察を行っています。さらに、HD-MILP-Planのディープネットワーク固有の最適化を特定し、基本エンコーディングよりもパフォーマンスを向上させ、学習済みのディープネットワークに関して最適に計画できることを示しています。TF-Planでは、自動微分ツールとGPUベースの計算の効率性を活用し、純粋に連続的な計画問題のサブクラスをリカレントニューラルネットワークとしてエンコードし、バックプロパゲーションによってアクションを直接最適化します。両方のプランナーを比較し、TF-PlanがHD-MILP-Planによって見つかった最適プランをより短い計算時間で近似できることを示します。したがって、この記事では、学習したディープ ニューラル ネット遷移モデルを使用して、連続的な状態とアクションのドメインに対する2つの新しいプランナーを紹介します。1つは最適な方法(HD-MILP-Plan)、もう1つは大規模な問題に対するスケーラブルな代替手段(TF-Plan)です。

A General Approach to Multimodal Document Quality Assessment

A General Approach to Multimodal Document Quality Assessment / マルチモーダル文書品質評価への一般的なアプローチ

The perceived quality of a document is affected by various factors, including grammat- icality, readability, stylistics, and expertise depth, making the task of document quality assessment a complex one. In this paper, we explore this task in the context of assessing the quality of Wikipedia articles and academic papers. Observing that the visual rendering of a document can capture implicit quality indicators that are not present in the document text — such as images, font choices, and visual layout — we propose a joint model that combines the text content with a visual rendering of the document for document qual- ity assessment. Our joint model achieves state-of-the-art results over five datasets in two domains (Wikipedia and academic papers), which demonstrates the complementarity of textual and visual features, and the general applicability of our model. To examine what kinds of features our model has learned, we further train our model in a multi-task learning setting, where document quality assessment is the primary task and feature learning is an auxiliary task. Experimental results show that visual embeddings are better at learning structural features while textual embeddings are better at learning readability scores, which further verifies the complementarity of visual and textual features.



文書の知覚品質は、文法、読みやすさ、文体、専門知識の深さなど、さまざまな要因の影響を受け、文書品質評価タスクを複雑にします。本稿では、Wikipediaの記事と学術論文の品質評価という文脈でこのタスクを検討します。文書の視覚的レンダリングは、画像、フォントの選択、視覚的なレイアウトなど、文書テキストには存在しない暗黙的な品質指標を捉えることができることに着目し、文書品質評価のためにテキストコンテンツと文書の視覚的レンダリングを組み合わせた結合モデルを提案します。この結合モデルは、2つのドメイン(Wikipediaと学術論文)の5つのデータセットで最先端の結果を達成しており、テキストと視覚的特徴の相補性とモデルの汎用性を実証しています。モデルがどのような特徴を学習したかを調べるために、文書品質評価を主要タスクとし、特徴学習を補助タスクとするマルチタスク学習設定でモデルをさらにトレーニングします。実験結果によると、視覚的な埋め込みは構造的特徴の学習に優れているのに対し、テキストによる埋め込みは読みやすさスコアの学習に優れていることが示されており、これは視覚的特徴とテキスト特徴の補完性をさらに裏付けています。

The Effects of Experience on Deception in Human-Agent Negotiation

The Effects of Experience on Deception in Human-Agent Negotiation / 人間とエージェントの交渉における経験が欺瞞に与える影響

Negotiation is the complex social process by which multiple parties come to mutual agreement over a series of issues. As such, it has proven to be a key challenge problem for designing adequately social AIs that can effectively navigate this space. Artificial AI agents that are capable of negotiating must be capable of realizing policies and strategies that govern offer acceptances, offer generation, preference elicitation, and more. But the next generation of agents must also adapt to reflect their users’ experiences.     The best human negotiators tend to have honed their craft through hours of practice and experience. But, not all negotiators agree on which strategic tactics to use, and endorsement of deceptive tactics in particular is a controversial topic for many negotiators. We examine the ways in which deceptive tactics are used and endorsed in non-repeated human negotiation and show that prior experience plays a key role in governing what tactics are seen as acceptable or useful in negotiation. Previous work has indicated that people that negotiate through artificial agent representatives may be more inclined to fairness than those people that negotiate directly. We present a series of three user studies that challenge this initial assumption and expand on this picture by examining the role of past experience.     This work constructs a new scale for measuring endorsement of manipulative negotiation tactics and introduces its use to artificial intelligence research. It continues by presenting the results of a series of three studies that examine how negotiating experience can change what negotiation tactics and strategies human endorse. Study #1 looks at human endorsement of deceptive techniques based on prior negotiating experience as well as representative effects. Study #2 further characterizes the negativity of prior experience in relation to endorsement of deceptive techniques. Finally, in Study #3, we show that the lessons learned from the empirical observations in Study #1 and #2 can in fact be induced—by designing agents that provide a specific type of negative experience, human endorsement of deception can be predictably manipulated.



交渉は、複数の当事者が一連の問題について相互に合意に至る複雑な社会的プロセスです。そのため、交渉は、この空間を効果的にナビゲートできる適切に社会的AIを設計するための重要な課題であることが証明されています。交渉能力のある人工AIエージェントは、オファーの受諾、オファーの生成、選好の引き出しなどを管理するポリシーと戦略を実現できなければなりません。しかし、次世代のエージェントは、ユーザーの経験を反映するように適応する必要もあります。最高の人間の交渉者は、何時間もの練習と経験を通してその技術を磨いてきた傾向があります。しかし、すべての交渉者がどの戦略的戦術を使用するかについて同意するわけではなく、特に欺瞞戦術の承認は多くの交渉者にとって物議を醸すトピックです。我々は、繰り返されない人間の交渉において、欺瞞的な戦術がどのように使用され、支持されるかを調べ、交渉においてどの戦術が受け入れられるか、または有用であるとみなされるかを決定する上で、以前の経験が重要な役割を果たしていることを示す。以前の研究は、人工エージェントの代表を介して交渉する人は、直接交渉する人よりも公平である傾向があることを示唆しています。我々は、この最初の仮定に異議を唱え、過去の経験の役割を調べることでこの図を拡張する、一連の3つのユーザー研究を提示します。この研究では、操作的な交渉戦術の支持を測定するための新しい尺度を構築し、人工知能研究への使用を導入します。さらに、交渉経験が人間が支持する交渉戦術と戦略をどのように変えることができるかを調べる一連の3つの研究の結果を提示します。研究＃1では、以前の交渉経験と代表効果に基づいて、欺瞞的な手法に対する人間の支持に注目します。研究＃2では、欺瞞的な手法の支持と関連して、以前の経験の否定性をさらに特徴付ける。最後に、研究3では、研究1と2の経験的観察から得られた教訓が実際に誘発可能であることを示します。つまり、特定の種類の否定的な経験を提供するエージェントを設計することで、人間による欺瞞の承認を予測どおりに操作できるということです。

Image Captioning using Facial Expression and Attention

Image Captioning using Facial Expression and Attention / 表情と注意を用いた画像キャプション生成

Benefiting from advances in machine vision and natural language processing techniques, current image captioning systems are able to generate detailed visual descriptions. For the most part, these descriptions represent an objective characterisation of the image, although some models do incorporate subjective aspects related to the observer’s view of the image, such as sentiment; current models, however, usually do not consider the emotional content of images during the caption generation process. This paper addresses this issue by proposing novel image captioning models which use facial expression features to generate image captions. The models generate image captions using long short-term memory networks applying facial features in addition to other visual features at different time steps. We compare a comprehensive collection of image captioning models with and without facial features using all standard evaluation metrics. The evaluation metrics indicate that applying facial features with an attention mechanism achieves the best performance, showing more expressive and more correlated image captions, on an image caption dataset extracted from the standard Flickr 30K dataset, consisting of around 11K images containing faces. An analysis of the generated captions finds that, perhaps unexpectedly, the improvement in caption quality appears to come not from the addition of adjectives linked to emotional aspects of the images, but from more variety in the actions described in the captions.



マシンビジョンと自然言語処理技術の進歩により、現在の画像キャプションシステムは詳細な視覚的説明を生成することができます。これらの説明は、ほとんどの場合、画像の客観的な特徴を表しますが、一部のモデルでは、感情など、観察者の画像に対する主観的な見方が考慮されています。しかしながら、現在のモデルは通常、キャプション生成プロセスにおいて画像の感情的内容を考慮していません。本論文では、顔の表情特徴を用いて画像キャプションを生成する新しい画像キャプションモデルを提案することで、この問題に対処します。これらのモデルは、顔の特徴に加えて他の視覚的特徴を異なる時間ステップで適用することで、長短期記憶ネットワークを用いて画像キャプションを生成します。標準的な評価指標を用いて、顔の特徴の有無にかかわらず、包括的な画像キャプションモデルを比較します。評価指標は、約11,000枚の顔画像を含む標準的なFlickr 30Kデータセットから抽出された画像キャプションデータセットにおいて、注意機構を用いて顔の特徴を適用することで、より表現力豊かで相関性の高い画像キャプションが得られるという最高のパフォーマンスが得られることを示しています。生成されたキャプションを分析したところ、おそらく予想外のことではあるが、キャプションの品質向上は、画像の感情的側面に結びついた形容詞の追加ではなく、キャプションに記述される行動の多様性の向上によるものであることがわかった。

Vocabulary Alignment in Openly Specified Interactions

Vocabulary Alignment in Openly Specified Interactions / オープンに指定されたインタラクションにおける語彙アラインメント

The problem of achieving common understanding between agents that use different vocabularies has been mainly addressed by techniques that assume the existence of shared external elements, such as a meta-language or a physical environment. In this article, we consider agents that use different vocabularies and only share knowledge of how to perform a task, given by the specification of an interaction protocol. We present a framework that lets agents learn a vocabulary alignment from the experience of interacting. Unlike previous work in this direction, we use open protocols that constrain possible actions instead of defining procedures, making our approach more general. We present two techniques that can be used either to learn an alignment from scratch or to repair an existent one, and we evaluate their performance experimentally.



異なる語彙を使用するエージェント間で共通理解を達成するという問題は、これまで主に、メタ言語や物理的環境といった共通の外部要素の存在を前提とする手法によって解決されてきた。本稿では、異なる語彙を使用し、インタラクションプロトコルの仕様によって与えられたタスクの実行方法に関する知識のみを共有するエージェントを考察します。本稿では、エージェントがインタラクションの経験から語彙のアラインメントを学習できるフレームワークを提示します。この方向でのこれまでの研究とは異なり、本稿では手順を定義するのではなく、可能な行動を制限するオープンプロトコルを使用することで、より汎用的なアプローチを実現しています。本稿では、アラインメントをゼロから学習するか、既存のアラインメントを修復するかのどちらかに使用できる2つの手法を提示し、その性能を実験的に評価します。

Subgoaling Techniques for Satisficing and Optimal Numeric Planning

Subgoaling Techniques for Satisficing and Optimal Numeric Planning / 満足化と最適数値プランニングのためのサブゴール設定手法

This paper studies novel subgoaling relaxations for automated planning with propositional and numeric state variables. Subgoaling relaxations address one source of complexity of the planning problem: the requirement to satisfy conditions simultaneously. The core idea is to relax this requirement by recursively decomposing conditions into atomic subgoals that are considered in isolation. Such relaxations are typically used for pruning, or as the basis for computing admissible or inadmissible heuristic estimates to guide optimal or satisificing heuristic search planners. In the last decade or so, the subgoaling principle has underpinned the design of an abundance of relaxation-based heuristics whose formulations have greatly extended the reach of classical planning. This paper extends subgoaling relaxations to support numeric state variables and numeric conditions. We provide both theoretical and practical results, with the aim of reaching a good trade-off between accuracy and computation costs within a heuristic state-space search planner. Our experimental results validate the theoretical assumptions, and indicate that subgoaling substantially improves on the state of the art in optimal and satisficing numeric planning via forward state-space search.



本稿では、命題変数および数値状態変数を用いた自動プランニングのための、新たなサブゴール緩和法について検討します。サブゴール緩和法は、プランニング問題の複雑さの一因である、条件を同時に満たす必要があるという要件に対処します。その核となる考え方は、条件を個別に考慮されるアトミックサブゴールに再帰的に分解することで、この要件を緩和することです。このような緩和法は、通常、枝刈り、あるいは最適または満足ヒューリスティック探索プランナーを導くための許容または非許容ヒューリスティック推定値の計算の基礎として用いられます。過去10年ほど、サブゴール原理は、古典的プランニングの範囲を大幅に拡張した、数多くの緩和ベースのヒューリスティック設計の基盤となってきた。本稿では、サブゴール緩和法を拡張し、数値状態変数と数値条件をサポートします。ヒューリスティック状態空間探索プランナーにおける精度と計算コストの適切なトレードオフを実現することを目指し、理論と実践の両方の結果を提供します。実験結果は理論的仮定を検証し、サブゴール設定が前向き状態空間探索による最適かつ満足度の高い数値計画の最先端の手法を大幅に改善することを示しています。

How to Do Things with Words: A Bayesian Approach

How to Do Things with Words: A Bayesian Approach / 言葉で物事を行う方法：ベイズ的アプローチ

Communication changes the beliefs of the listener and of the speaker. The value of a communicative act stems from the valuable belief states which result from this act. To model this we build on the Interactive POMDP (IPOMDP) framework, which extends POMDPs to allow agents to model others in multi-agent settings, and we include communication that can take place between the agents to formulate Communicative IPOMDPs (CIPOMDPs). We treat communication as a type of action and therefore, decisions regarding communicative acts are based on decision-theoretic planning using the Bellman optimality principle and value iteration, just as they are for all other rational actions. As in any form of planning, the results of actions need to be precisely specified. We use the Bayes’ theorem to derive how agents update their beliefs in CIPOMDPs; updates are due to agents’ actions, observations, messages they send to other agents, and messages they receive from others. The Bayesian decision-theoretic approach frees us from the commonly made assumption of cooperative discourse – we consider agents which are free to be dishonest while communicating and are guided only by their selfish rationality. We use a simple Tiger game to illustrate the belief update, and to show that the ability to rationally communicate allows agents to improve efficiency of their interactions.



コミュニケーションは、聞き手と話し手の信念を変化させます。コミュニケーション行為の価値は、この行為から生じる価値ある信念状態に起因します。これをモデル化するために、我々は対話型POMDP（IPOMDP）フレームワークを構築します。このフレームワークは、POMDPを拡張し、エージェントがマルチエージェント環境において他者をモデル化できるようにします。また、エージェント間で行われるコミュニケーションを組み込み、コミュニケーション型IPOMDP（CIPOMDP）を定式化します。我々はコミュニケーションを行動の一種として扱い、したがって、コミュニケーション行為に関する決定は、他のすべての合理的行動と同様に、ベルマン最適性原理と価値反復を用いた意思決定理論的計画に基づいています。あらゆる計画形式と同様に、行動の結果は正確に指定される必要があります。ベイズの定理を用いて、エージェントがCIPOMDPにおいてどのように信念を更新するかを導出します。更新は、エージェントの行動、観察、他のエージェントに送信するメッセージ、および他のエージェントから受信するメッセージによって行われます。ベイズ決定理論的アプローチは、協力的な談話に関する一般的な仮定から私たちを解放します。つまり、コミュニケーション中に不正直になる自由があり、利己的な合理性によってのみ導かれるエージェントを考慮します。単純なタイガーゲームを使用して信念の更新を説明し、合理的にコミュニケーションする能力によってエージェントが相互作用の効率を改善できることを示します。

Gradient-based Learning Methods Extended to Smooth Manifolds Applied to Automated Clustering

Gradient-based Learning Methods Extended to Smooth Manifolds Applied to Automated Clustering / 滑らかな多様体に拡張された勾配ベース学習法の自動クラスタリングへの適用

Grassmann manifold based sparse spectral clustering is a classification technique that  consists in learning a latent representation of data, formed by a subspace basis, which  is sparse. In order to learn a latent representation, spectral clustering is formulated in  terms of a loss minimization problem over a smooth manifold known as Grassmannian.  Such minimization problem cannot be tackled by one of traditional gradient-based learning  algorithms, which are only suitable to perform optimization in absence of constraints among  parameters. It is, therefore, necessary to develop specific optimization/learning algorithms  that are able to look for a local minimum of a loss function under smooth constraints in  an efficient way. Such need calls for manifold optimization methods. In this paper, we  extend classical gradient-based learning algorithms on   at parameter spaces (from classical  gradient descent to adaptive momentum) to curved spaces (smooth manifolds) by means  of tools from manifold calculus. We compare clustering performances of these methods  and known methods from the scientific literature. The obtained results confirm that the  proposed learning algorithms prove lighter in computational complexity than existing ones  without detriment in clustering efficacy.



グラスマン多様体ベースのスパーススペクトルクラスタリングは、スパースな部分空間基底によって形成されたデータの潜在的表現を学習することからなる分類手法です。潜在的表現を学習するために、スペクトルクラスタリングは、グラスマンとして知られる滑らかな多様体上の損失最小化問題として定式化されます。このような最小化問題は、パラメータ間に制約がない場合に最適化を実行するのにのみ適した、従来の勾配ベースの学習アルゴリズムの1つでは取り組むことができません。したがって、滑らかな制約の下で損失関数の局所的最小値を効率的に探すことができる特定の最適化/学習アルゴリズムを開発する必要があります。このようなニーズには、多様体最適化手法が必要です。本稿では、多様体計算のツールを使用して、パラメータ空間（古典的な勾配降下法から適応モーメント法まで）上の古典的な勾配ベース学習アルゴリズムを曲線空間（滑らかな多様体）に拡張します。これらの方法と科学文献の既知の方法のクラスタリングパフォーマンスを比較します。得られた結果は、提案された学習アルゴリズムが、クラスタリングの有効性を損なうことなく、既存のものよりも計算の複雑さが軽減されることを確認しています。

Towards Partial Order Reductions for Strategic Ability

Towards Partial Order Reductions for Strategic Ability / 戦略能力のための部分順序縮約に向けて

We propose a general semantics for strategic abilities of agents in asynchronous systems, with and without perfect information. Based on the semantics, we show some general complexity results for verification of strategic abilities in asynchronous interaction. More importantly, we develop a methodology for partial order reduction in verification of agents with imperfect information. We show that the reduction preserves an important subset of strategic properties, with as well as without the fairness assumption. We also demonstrate the effectiveness of the reduction on a number of benchmarks. Interestingly, the reduction does not work for strategic abilities under perfect information.



我々は、非同期システムにおけるエージェントの戦略能力について、完全情報の有無に関わらず、一般的な意味論を提案します。この意味論に基づき、非同期インタラクションにおける戦略能力の検証に関する一般的な計算量結果を示す。さらに重要な点として、不完全情報を持つエージェントの検証における半順序縮約のための方法論を開発します。この縮約は、公平性仮定の有無にかかわらず、戦略特性の重要なサブセットを保持することを示す。また、いくつかのベンチマークにおいて縮約の有効性も実証します。興味深いことに、この縮約は完全情報下の戦略能力には機能しない。

参考文献

• Journal of Artificial Intelligence Resarch Vol. 68 (2020)

関連情報

• Journal of Artificial Intelligence Research: 論文一覧