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

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

論文

Point at the Triple: Generation of Text Summaries from Knowledge Base Triples

Point at the Triple: Generation of Text Summaries from Knowledge Base Triples / トリプルを指摘：知識ベーストリプルからのテキスト要約の生成

We investigate the problem of generating natural language summaries from knowledge base triples. Our approach is based on a pointer-generator network, which, in addition to generating regular words from a fixed target vocabulary, is able to verbalise triples in several ways. We undertake an automatic and a human evaluation on single and open-domain summaries generation tasks. Both show that our approach significantly outperforms other data-driven baselines.



我々は、知識ベーストリプルから自然言語要約を生成する問題を調査します。我々のアプローチは、ポインタ生成ネットワークに基づいており、固定された対象語彙から通常の単語を生成するだけでなく、トリプルを複数の方法で言語化することができます。我々は、単一ドメインおよびオープンドメイン要約生成タスクにおいて、自動評価と人間による評価を行う。どちらの評価も、我々のアプローチが他のデータ駆動型ベースラインを大幅に上回っていることを示しています。

Credibility-limited Base Revision: New Classes and Their Characterizations

Credibility-limited Base Revision: New Classes and Their Characterizations / 信頼性制限ベースの修正：新しいクラスとその特徴づけ

In this paper we study a kind of operator —known as credibility-limited base revisions— which addresses two of the main issues that have been pointed out to the AGM model of belief change. Indeed, on the one hand, these operators are defined on belief bases (rather than belief sets) and, on the other hand, they are constructed with the underlying idea that not all new information is accepted. We propose twenty different classes of credibility-limited base revision operators and obtain axiomatic characterizations for each of them. Additionally we thoroughly investigate the interrelations (in the sense of inclusion) among all those classes. More precisely, we analyse whether each one of those classes is or is not (strictly) contained in each of the remaining ones.



本論文では、AGMモデルにおける信念変化に関して指摘されてきた2つの主要な問題に対処する、いわゆる「信頼性限定基底修正」と呼ばれる演算子について考察します。これらの演算子は、信念集合ではなく信念基底に基づいて定義される一方で、すべての新しい情報が受け入れられるわけではないという基本的な考え方に基づいて構築されています。本論文では、20種類の異なる信頼性限定基底修正演算子のクラスを提案し、それぞれについて公理的な特徴付けを行う。さらに、これらのクラス間の相互関係（包含の意味で）を徹底的に調査します。より正確には、これらのクラスのそれぞれが、残りのクラスのそれぞれに（厳密に）含まれるかどうかを分析します。

Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search

Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search / 局所的な複雑さを理解するための評価制約による適応度地形の表現検索

Local search is widely used to solve combinatorial optimisation problems and to model biological evolution, but the performance of local search algorithms on different kinds of fitness landscapes is poorly understood. Here we consider how fitness landscapes can be represented using valued constraints, and investigate what the structure of such representations reveals about the complexity of local search.     First, we show that for fitness landscapes representable by binary Boolean valued constraints there is a minimal necessary constraint graph that can be easily computed. Second, we consider landscapes as equivalent if they allow the same (improving) local search moves; we show that a minimal constraint graph still exists, but is NP-hard to compute.     We then develop several techniques to bound the length of any sequence of local search moves. We show that such a bound can be obtained from the numerical values of the constraints in the representation, and show how this bound may be tightened by considering equivalent representations. In the binary Boolean case, we prove that a degree 2 or treestructured constraint graph gives a quadratic bound on the number of improving moves made by any local search; hence, any landscape that can be represented by such a model will be tractable for any form of local search.     Finally, we build two families of examples to show that the conditions in our tractability results are essential. With domain size three, even just a path of binary constraints can model a landscape with an exponentially long sequence of improving moves. With a treewidth-two constraint graph, even with a maximum degree of three, binary Boolean constraints can model a landscape with an exponentially long sequence of improving moves.



局所探索は、組み合わせ最適化問題を解いたり、生物の進化をモデル化したりするために広く使用されていますが、さまざまな種類の適応度ランドスケープでの局所探索アルゴリズムのパフォーマンスは十分に理解されていません。ここでは、値制約を使用して適応度ランドスケープを表現する方法を検討し、そのような表現の構造が局所探索の複雑さについて何を明らかにするかを調べます。まず、バイナリブール値制約で表現可能な適応度ランドスケープの場合、簡単に計算できる最小限必要な制約グラフが存在することを示します。次に、ランドスケープが同じ（改善する）局所探索動作を許可する場合、ランドスケープは同等であると見なします。最小限の制約グラフは依然として存在しますが、計算するのはNP困難であることを示します。次に、局所探索動作の任意のシーケンスの長さを制限するいくつかの手法を開発します。このような制限は、表現内の制約の数値から取得できることを示し、同等の表現を考慮することでこの制限をどのように厳しくできるかを示します。バイナリブールの場合、次数2またはツリー構造の制約グラフは、任意の局所探索による改善動作の数に二次の境界を与えることを証明します。したがって、このようなモデルで表現できるランドスケープは、どのような形式の局所探索でも扱いやすくなります。最後に、2つの例ファミリーを構築して、扱いやすさの結果の条件が不可欠であることを示します。ドメイン サイズが3の場合、バイナリ制約のパスだけでも、改善動作の指数関数的に長いシーケンスを持つランドスケープをモデル化できます。ツリー幅が2の制約グラフでは、最大次数が3でも、バイナリ ブール制約で、改善動作の指数関数的に長いシーケンスを持つランドスケープをモデル化できます。

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms / 連続ケーキカット：困難性結果と近似アルゴリズム

We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the cake. While it is known that no finite envy-free algorithm exists in this setting, we exhibit efficient algorithms that produce allocations with low envy among the agents. We then establish NP-hardness results for various decision problems on the existence of envy-free allocations, such as when we fix the ordering of the agents or constrain the positions of certain cuts. In addition, we consider a discretized setting where indivisible items lie on a line and show a number of hardness results extending and strengthening those from prior work. Finally, we investigate connections between approximate and exact envy-freeness, as well as between continuous and discrete cake cutting.



各エージェントがケーキの連続した部分を受け取るという要件の下で、分割可能なリソースのメタファーとして機能するケーキの公平な割り当てを検討します。この設定では有限の羨望のないアルゴリズムは存在しないことが知られていますが、エージェント間の羨望が低い割り当てを生成する効率的なアルゴリズムを示します。次に、エージェントの順序を固定したり、特定のカットの位置を制約したりする場合など、羨望のない割り当ての存在に関するさまざまな決定問題に対するNP困難性の結果を確立します。さらに、分割できないアイテムが直線上に存在する離散化設定を考慮し、先行研究の結果を拡張および強化するいくつかの困難性の結果を示します。最後に、近似羨望のない状態と正確な羨望のない状態、および連続ケーキカットと離散ケーキカットの関係を調査します。

Epistemic Argumentation Framework: Theory and Computation

Epistemic Argumentation Framework: Theory and Computation / 認識論的論証フレームワーク：理論と計算

The paper introduces the notion of an epistemic argumentation framework (EAF) as a means to integrate the beliefs of a reasoner with argumentation. Intuitively, an EAF encodes the beliefs of an agent who reasons about arguments. Formally, an EAF is a pair of an argumentation framework and an epistemic constraint. The semantics of the EAF is defined by the notion of an ω-epistemic labelling set, where ω is complete, stable, grounded, or preferred, which is a set of ω-labellings that collectively satisfies the epistemic constraint of the EAF. The paper shows how EAF can represent different views of reasoners on the same argumentation framework. It also includes representing preferences in EAF and multi-agent argumentation. Finally, the paper discusses complexity issues and computation using epistemic logic programming.



本論文では、推論者の信念と議論を統合する手段として、認識論的議論フレームワーク（EAF）の概念を導入します。直感的に、EAFは議論について推論するエージェントの信念をエンコードします。正式には、EAFは議論フレームワークと認識論的制約のペアです。EAFの意味論は、ω-認識論的ラベリング集合の概念によって定義されます。ここでωは、完全、安定、根拠、または優先のいずれかであり、EAFの認識論的制約を総合的に満たすω-ラベリングの集合です。本論文では、EAFが同じ議論フレームワーク上で推論者の異なる見解をどのように表現できるかを示します。また、EAFとマルチエージェント議論における選好の表現についても説明します。最後に、本論文では、複雑性の問題と認識論的論理プログラミングを用いた計算について考察します。

A Differential Privacy Mechanism that Accounts for Network Effects for Crowdsourcing Systems

A Differential Privacy Mechanism that Accounts for Network Effects for Crowdsourcing Systems / クラウドソーシングシステムにおけるネットワーク効果を考慮した差分プライバシーメカニズム

In crowdsourcing systems, it is important for the crowdsource campaign initiator to incentivize users to share their data to produce results of the desired computational accuracy. This problem becomes especially challenging when users are concerned about the privacy of their data. To overcome this challenge, existing work often aims to provide users with differential privacy guarantees to incentivize privacy-sensitive users to share their data. However, this work neglects the network effect that a user enjoys greater privacy protection when he aligns his participation behaviour with that of other users. To explore this network effect, we formulate the interaction among users regarding their participation decisions as a population game, because a user’s welfare from the interaction depends not only on his own participation decision but also the distribution of others’ decisions. We show that the Nash equilibrium of this game consists of a threshold strategy, where all users whose privacy sensitivity is below a certain threshold will participate and the remaining users will not. We characterize the existence and uniqueness of this equilibrium, which depends on the privacy guarantee, the reward provided by the initiator and the population size. Based on this equilibria analysis, we design the PINE (Privacy Incentivization with Network Effects) mechanism and prove that it maximizes the initiator’s payoff while providing participating users with a guaranteed degree of privacy protection. Numerical simulations, on both real and synthetic data, show that (i) PINE improves the initiator’s expected payoff by up to 75%, compared to state of the art mechanisms that do not consider this effect; (ii) the performance gain by exploiting the network effect is particularly good when the majority of users are flexible over their privacy attitudes and when there are a large number of low quality task performers.



クラウドソーシングシステムにおいて、クラウドソーシングキャンペーンの開始者は、ユーザーがデータを共有し、望ましい計算精度の結果を得るようインセンティブを与えることが重要です。この問題は、ユーザーがデータのプライバシーを懸念している場合に特に困難になります。この課題を克服するために、既存の研究では、プライバシーに敏感なユーザーがデータを共有するようインセンティブを与えるために、差分プライバシー保証を提供することがしばしば試みられています。しかし、この研究では、ユーザーが参加行動を他のユーザーの行動と一致させることで、より高いプライバシー保護を享受できるというネットワーク効果が考慮されていません。このネットワーク効果を検証するために、本研究では、参加決定に関するユーザー間の相互作用を人口ゲームとして定式化します。これは、相互作用によるユーザーの厚生は、自身の参加決定だけでなく、他のユーザーの決定の分布にも依存するからです。本ゲームのナッシュ均衡は、プライバシーへの感受性が一定の閾値を下回るすべてのユーザーが参加し、残りのユーザーは参加しないという閾値戦略で構成されることを示します。本均衡の存在と一意性は、プライバシー保証、開始者が提供する報酬、および人口規模に依存します。この均衡分析に基づいて、我々はPINE (ネットワーク効果によるプライバシーインセンティブ化)メカニズムを設計し、参加ユーザーに保証されたレベルのプライバシー保護を提供しながら、イニシエーターの利得を最大化することを証明します。実データと合成データの両方を用いた数値シミュレーションにより、(i) PINEは、この効果を考慮しない最先端のメカニズムと比較して、イニシエーターの期待利得を最大75%向上させること、(ii)ネットワーク効果を活用することによるパフォーマンス向上は、大多数のユーザーがプライバシーに関して柔軟な態度を示し、低品質のタスク実行者が多数存在する場合に特に優れていることが示されました。

Adaptive Stress Testing: Finding Likely Failure Events with Reinforcement Learning

Adaptive Stress Testing: Finding Likely Failure Events with Reinforcement Learning / 適応型ストレステスト：強化学習を用いた起こりやすい障害イベントの発見

Finding the most likely path to a set of failure states is important to the analysis of safety-critical systems that operate over a sequence of time steps, such as aircraft collision avoidance systems and autonomous cars. In many applications such as autonomous driving, failures cannot be completely eliminated due to the complex stochastic environment in which the system operates. As a result, safety validation is not only concerned about whether a failure can occur, but also discovering which failures are most likely to occur. This article presents adaptive stress testing (AST), a framework for finding the most likely path to a failure event in simulation. We consider a general black box setting for partially observable and continuous-valued systems operating in an environment with stochastic disturbances. We formulate the problem as a Markov decision process and use reinforcement learning to optimize it. The approach is simulation-based and does not require internal knowledge of the system, making it suitable for black-box testing of large systems. We present different formulations depending on whether the state is fully observable or partially observable. In the latter case, we present a modified Monte Carlo tree search algorithm that only requires access to the pseudorandom number generator of the simulator to overcome partial observability. We also present an extension of the framework, called differential adaptive stress testing (DAST), that can find failures that occur in one system but not in another. This type of differential analysis is useful in applications such as regression testing, where we are concerned with finding areas of relative weakness compared to a baseline. We demonstrate the effectiveness of the approach on an aircraft collision avoidance application, where a prototype aircraft collision avoidance system is stress tested to find the most likely scenarios of near mid-air collision.



航空機衝突回避システムや自動運転車など、一連の時間ステップにわたって動作するセーフティクリティカルシステムの解析では、一連の障害状態への最も可能性の高い経路を見つけることが重要です。自動運転などの多くのアプリケーションでは、システムが動作する複雑な確率的環境のために、障害を完全に排除することはできません。その結果、安全性検証は、故障の発生可能性だけでなく、どの故障が最も発生する可能性が高いかを発見することにも重点を置くことになります。本稿では、シミュレーションにおいて故障イベントへの最も可能性の高い経路を見つけるためのフレームワークである適応型ストレステスト（AST）を紹介します。確率的外乱を伴う環境で動作する、部分観測可能で連続値を持つシステムのための一般的なブラックボックス設定を検討します。問題をマルコフ決定過程として定式化し、強化学習を用いて最適化を行います。このアプローチはシミュレーションベースであり、システムの内部知識を必要としないため、大規模システムのブラックボックステストに適しています。状態が完全観測可能か部分観測可能かに応じて、異なる定式化を提示します。後者の場合、部分観測性を克服するためにシミュレータの疑似乱数発生器へのアクセスのみを必要とする、修正されたモンテカルロ木探索アルゴリズムを提示します。また、あるシステムでは発生し、別のシステムでは発生しない故障を検出できる、このフレームワークの拡張である差分適応型ストレステスト（DAST）も紹介します。このタイプの差分分析は、回帰テストなどの、ベースラインと比較した相対的な弱点領域を見つけることが重要なアプリケーションで役立ちます。本研究では、航空機衝突回避アプリケーションにおいてこのアプローチの有効性を実証します。プロトタイプの航空機衝突回避システムに対してストレステストを実施し、ニアミスの最も可能性の高いシナリオを特定します。

Lifted Bayesian Filtering in Multiset Rewriting Systems

Lifted Bayesian Filtering in Multiset Rewriting Systems / 多重集合書き換えシステムにおけるリフテッドベイズフィルタリング

We present a model for Bayesian filtering (BF) in discrete dynamic systems where multiple entities (inter)-act, i.e. where the system dynamics is naturally described by a Multiset rewriting system (MRS). Typically, BF in such situations is computationally expensive due to the high number of discrete states that need to be maintained explicitly.We devise a lifted state representation, based on a suitable decomposition of multiset states, such that some factors of the distribution are exchangeable and thus afford an efficient representation. Intuitively, this representation groups together similar entities whose properties follow an exchangeable joint distribution. Subsequently, we introduce a BF algorithm that works directly on lifted states, without resorting to the original, much larger ground representation.This algorithm directly lends itself to approximate versions by limiting the number of explicitly represented lifted states in the posterior. We show empirically that the lifted representation can lead to a factorial reduction in the representational complexity of the distribution, and in the approximate cases can lead to a lower variance of the estimate and a lower estimation error compared to the original, ground representation.



我々は、複数のエンティティが（相互作用して）作用する離散動的システム、すなわち、システムのダイナミクスが多重集合書き換えシステム（MRS）によって自然に記述される離散動的システムにおけるベイジアンフィルタリング（BF）のモデルを提示します。通常、このような状況でのBFは、明示的に維持する必要のある離散状態の数が多いため、計算コストが高くなります。我々は、分布のいくつかの要素が交換可能であり、したがって効率的な表現を可能にする、多重集合状態の適切な分解に基づくリフト状態表現を考案します。直感的に、この表現は、プロパティが交換可能な結合分布に従う類似のエンティティをグループ化します。続いて、我々は、元のはるかに大規模な基底表現に頼ることなく、リフト状態に直接作用するBFアルゴリズムを導入します。このアルゴリズムは、事後分布で明示的に表現されるリフト状態の数を制限することにより、近似バージョンに直接役立つ。我々は、リフト表現が分布の表現上の複雑さを階乗的に削減し、近似的なケースでは、元のグラウンド表現と比較して推定値の分散と推定誤差を低減できることを経験的に示します。

Reviewing Autoencoders for Missing Data Imputation: Technical Trends, Applications and Outcomes

Reviewing Autoencoders for Missing Data Imputation: Technical Trends, Applications and Outcomes / 欠損データ補完のためのオートエンコーダのレビュー：技術動向、応用、成果

Missing data is a problem often found in real-world datasets and it can degrade the performance of most machine learning models. Several deep learning techniques have been used to address this issue, and one of them is the Autoencoder and its Denoising and Variational variants. These models are able to learn a representation of the data with missing values and generate plausible new ones to replace them. This study surveys the use of Autoencoders for the imputation of tabular data and considers 26 works published between 2014 and 2020. The analysis is mainly focused on discussing patterns and recommendations for the architecture, hyperparameters and training settings of the network, while providing a detailed discussion of the results obtained by Autoencoders when compared to other state-of-the-art methods, and of the data contexts where they have been applied. The conclusions include a set of recommendations for the technical settings of the network, and show that Denoising Autoencoders outperform their competitors, particularly the often used statistical methods.



欠損データは実世界のデータセットでよく見られる問題であり、ほとんどの機械学習モデルの性能を低下させる可能性があります。この問題に対処するために、いくつかの深層学習手法が用いられてきました。その一つがオートエンコーダとそのノイズ除去および変分法です。これらのモデルは、欠損値を含むデータの表現を学習し、それらを置き換える妥当な新しい表現を生成することができます。本研究では、表形式データの補完におけるオートエンコーダの使用を調査し、2014年から2020年の間に発表された26の研究を検討します。分析は主に、ネットワークのアーキテクチャ、ハイパーパラメータ、トレーニング設定に関するパターンと推奨事項の議論に焦点を当て、他の最先端手法と比較した場合のオートエンコーダによって得られた結果、およびそれらが適用されたデータコンテキストについて詳細に議論します。結論には、ネットワークの技術的設定に関する一連の推奨事項が含まれており、ノイズ除去オートエンコーダが競合製品、特によく使用される統計的手法よりも優れていることを示しています。

Adapting Behavior via Intrinsic Reward: A Survey and Empirical Study

Adapting Behavior via Intrinsic Reward: A Survey and Empirical Study / 内発的報酬による行動の適応：サーベイと実証研究

Learning about many things can provide numerous benefits to a reinforcement learning system. For example, learning many auxiliary value functions, in addition to optimizing the environmental reward, appears to improve both exploration and representation learning. The question we tackle in this paper is how to sculpt the stream of experience—how to adapt the learning system’s behavior—to optimize the learning of a collection of value functions. A simple answer is to compute an intrinsic reward based on the statistics of each auxiliary learner, and use reinforcement learning to maximize that intrinsic reward. Unfortunately, implementing this simple idea has proven difficult, and thus has been the focus of decades of study. It remains unclear which of the many possible measures of learning would work well in a parallel learning setting where environmental reward is extremely sparse or absent. In this paper, we investigate and compare different intrinsic reward mechanisms in a new bandit-like parallel-learning testbed. We discuss the interaction between reward and prediction learners and highlight the importance of introspective prediction learners: those that increase their rate of learning when progress is possible, and decrease when it is not. We provide a comprehensive empirical comparison of 14 different rewards, including well-known ideas from reinforcement learning and active learning. Our results highlight a simple but seemingly powerful principle: intrinsic rewards based on the amount of learning can generate useful behavior, if each individual learner is introspective.



多くのことを学習することは、強化学習システムに多くの利点をもたらします。例えば、環境報酬の最適化に加えて、多くの補助的な価値関数を学習することは、探索学習と表現学習の両方を改善するようです。本論文で取り組む問題は、経験の流れをどのように形作るか、つまり学習システムの動作をどのように適応させて、一連の価値関数の学習を最適化するかということです。簡単な答えは、各補助学習器の統計に基づいて内的報酬を計算し、強化学習を用いてその内的報酬を最大化することです。しかしながら、このシンプルなアイデアの実装は困難であることが判明しており、数十年にわたる研究の焦点となってきました。環境報酬が極めてまばら、あるいは全く存在しない並列学習環境において、多くの学習尺度のうちどれが適切に機能するかは依然として不明です。本稿では、新たなバンディット型並列学習テストベッドにおいて、様々な内的報酬メカニズムを調査・比較します。報酬学習器と予測学習器の相互作用について考察し、内省的予測学習器の重要性を強調します。内省的予測学習器とは、学習が可能な場合には学習速度を上げ、不可能な場合には学習速度を下げる学習器です。強化学習や能動学習におけるよく知られたアイデアを含む14種類の報酬について、包括的な実証的比較を行います。本研究の結果は、単純でありながら強力な原理を浮き彫りにします。それは、学習量に基づく内的報酬は、個々の学習器が内省的であれば、有用な行動を生み出すことができるというものです。

On the Complexity of Learning a Class Ratio from Unlabeled Data

On the Complexity of Learning a Class Ratio from Unlabeled Data / ラベルなしデータからのクラス比学習の複雑さについて

In the problem of learning a class ratio from unlabeled data, which we call CR learning, the training data is unlabeled, and only the ratios, or proportions, of examples receiving each label are given. The goal is to learn a hypothesis that predicts the proportions of labels on the distribution underlying the sample. This model of learning is applicable to a wide variety of settings, including predicting the number of votes for candidates in political elections from polls.In this paper, we formally define this class and resolve foundational questions regarding the computational complexity of CR learning and characterize its relationship to PAC learning. Among our results, we show, perhaps surprisingly, that for finite VC classes what can be efficiently CR learned is a strict subset of what can be learned efficiently in PAC, under standard complexity assumptions. We also show that there exist classes of functions whose CR learnability is independent of ZFC, the standard set theoretic axioms. This implies that CR learning cannot be easily characterized (like PAC by VC dimension).



ラベルなしデータからクラス比を学習する問題（CR学習と呼ぶ）では、トレーニング データはラベルなしであり、各ラベルが付けられた例の比率のみが与えられます。目標は、サンプルの基礎となる分布におけるラベルの比率を予測する仮説を学習することです。この学習モデルは、世論調査から政治選挙の候補者の投票数を予測するなど、さまざまな設定に適用できます。本稿では、このクラスを正式に定義し、CR学習の計算複雑性に関する基本的な疑問を解決し、PAC学習との関係を特徴付けます。結果の中で、おそらく意外なことに、有限のVCクラスの場合、標準的な複雑性の仮定の下では、効率的にCR学習できるものはPACで効率的に学習できるものの厳密なサブセットであることを示します。また、CR学習可能性が標準的な集合論の公理であるZFCに依存しない関数のクラスが存在することも示します。これは、CR学習が（VC次元によるPACのように）簡単に特徴付けできないことを意味します。

An Evaluation of Communication Protocol Languages for Engineering Multiagent Systems

An Evaluation of Communication Protocol Languages for Engineering Multiagent Systems / マルチエージェントシステムのエンジニアリングにおける通信プロトコル言語の評価

Communication protocols are central to engineering decentralized multiagent systems. Modern protocol languages are typically formal and address aspects of decentralization, such as asynchrony. However, modern languages differ in important ways in their basic abstractions and operational assumptions. This diversity makes a comparative evaluation of protocol languages a challenging task.We contribute a rich evaluation of diverse and modern protocol languages. Among the selected languages, Scribble is based on session types; Trace-C and Trace-F on trace expressions; HAPN on hierarchical state machines, and BSPL on information causality. Our contribution is four-fold. One, we contribute important criteria for evaluating protocol languages. Two, for each criterion, we compare the languages on the basis of whether they are able to specify elementary protocols that go to the heart of the criterion. Three, for each language, we map our findings to a canonical architecture style for multiagent systems, highlighting where the languages depart from the architecture. Four, we identify design principles for protocol languages as guidance for future research.



通信プロトコルは、分散型マルチエージェントシステムのエンジニアリングにおいて中心的な役割を果たします。現代のプロトコル言語は一般的に形式的であり、非同期性といった分散化の側面に対処します。しかしながら、現代の言語は、基本的な抽象化や動作上の仮定において重要な点で大きく異なります。この多様性により、プロトコル言語の比較評価は困難な作業となります。そこで、本稿では、多様で現代的なプロトコル言語の充実した評価を提供します。選定した言語の中で、Scribbleはセッションタイプ、Trace-CとTrace-Fはトレース表現、HAPNは階層的ステートマシン、BSPLは情報因果関係に基づきます。本稿の貢献は4つあります。1つ目は、プロトコル言語を評価するための重要な基準を提供することです。2つ目は、各基準において、各言語が基準の核心となる基本プロトコルを規定できるかどうかという観点から比較することです。3つ目は、各言語について、調査結果をマルチエージェントシステムの標準的なアーキテクチャスタイルにマッピングし、各言語がアーキテクチャから逸脱している点を明らかにします。4つ目は、将来の研究の指針として、プロトコル言語の設計原則を特定することです。

Bounds on the Size of PC and URC Formulas

Bounds on the Size of PC and URC Formulas / PC式とURC式のサイズの上限

In this paper, we investigate CNF encodings, for which unit propagation is strong enough to derive a contradiction if the encoding is not consistent with a partial assignment of the variables (unit refutation complete or URC encoding) or additionally to derive all implied literals if the encoding is consistent with the partial assignment (propagation complete or PC encoding). We prove an exponential separation between the sizes of PC and URC encodings without auxiliary variables and strengthen the known results on their relationship to the PC and URC encodings that can use auxiliary variables. Besides of this, we prove that the sizes of any two irredundant PC formulas representing the same function differ at most by a factor polynomial in the number of the variables and present an example of a function demonstrating that a similar statement is not true for URC formulas. One of the separations above implies that a q-Horn formula may require an exponential number of additional clauses to become a URC formula. On the other hand, for every q-Horn formula, we present a polynomial size URC encoding of the same function using auxiliary variables. This encoding is not q-Horn in general.



本稿では、単位伝播が十分に強く、変数の部分的な割り当てと矛盾する符号化（単位反駁完了、すなわちURC符号化）の場合に矛盾を導出でき、また部分的な割り当てと矛盾しない符号化（伝播完了、すなわちPC符号化）の場合に、さらにすべての暗黙のリテラルを導出できるCNF符号化について考察します。補助変数を使用しないPC符号化とURC符号化のサイズが指数的に分離していることを証明し、補助変数を使用できるPC符号化とURC符号化との関係に関する既知の結果を強化します。さらに、同じ関数を表す任意の2つの非冗長PC式のサイズは、変数の数の多項式倍数以下であることを証明し、同様のことがURC式には当てはまらないことを示す関数の例を提示します。上記の分離の1つは、q-Horn式がURC式になるためには指数的数の追加節が必要になる可能性があることを示唆しています。一方、すべてのq-Horn式に対して、補助変数を用いた同じ関数の多項式サイズのURC符号化を提示します。この符号化は、一般的なq-Hornではありません。

Deep Reinforcement Learning: A State-of-the-Art Walkthrough

Deep Reinforcement Learning: A State-of-the-Art Walkthrough / 深層強化学習：最先端のウォークスルー

Deep Reinforcement Learning is a topic that has gained a lot of attention recently, due to the unprecedented achievements and remarkable performance of such algorithms in various benchmark tests and environmental setups. The power of such methods comes from the combination of an already established and strong field of Deep Learning, with the unique nature of Reinforcement Learning methods. It is, however, deemed necessary to provide a compact, accurate and comparable view of these methods and their results for the means of gaining valuable technical and practical insights. In this work we gather the essential methods related to Deep Reinforcement Learning, extracting common property structures for three complementary core categories: a) Model-Free, b) Model-Based and c) Modular algorithms. For each category, we present, analyze and compare state-of-the-art Deep Reinforcement Learning algorithms that achieve high performance in various environments and tackle challenging problems in complex and demanding tasks. In order to give a compact and practical overview of their differences, we present comprehensive comparison figures and tables, produced by reported performances of the algorithms under two popular simulation platforms: the Atari Learning Environment and the MuJoCo physics simulation platform. We discuss the key differences of the various kinds of algorithms, indicate their potential and limitations, as well as provide insights to researchers regarding future directions of the field.



深層強化学習は、様々なベンチマークテストや環境設定において、前例のない成果と優れたパフォーマンスを示したアルゴリズムによって、近年大きな注目を集めているトピックです。このような手法の強みは、既に確立された強力な深層学習分野と、強化学習手法の独自の性質を組み合わせることで生まれます。しかしながら、貴重な技術的および実用的な洞察を得るためには、これらの手法とその結果を簡潔かつ正確かつ比較可能な形で提示することが必要不可欠です。本研究では、深層強化学習に関連する重要な手法を収集し、a)モデルフリー、b)モデルベース、c)モジュラーアルゴリズムという3つの補完的なコアカテゴリに共通する特性構造を抽出します。各カテゴリについて、様々な環境で高いパフォーマンスを実現し、複雑で要求の厳しいタスクにおける困難な問題に取り組む最先端の深層強化学習アルゴリズムを紹介、分析、比較します。それらの相違点を簡潔かつ実践的に概観するために、2つの一般的なシミュレーションプラットフォーム、Atari Learning EnvironmentとMuJoCo物理シミュレーションプラットフォームで報告されたアルゴリズムのパフォーマンスに基づいて作成された、包括的な比較図と表を示します。さまざまな種類のアルゴリズムの主な違いについて説明し、その可能性と限界を示すとともに、この分野の将来の方向性について研究者に洞察を提供します。

Annotator Rationales for Labeling Tasks in Crowdsourcing

Annotator Rationales for Labeling Tasks in Crowdsourcing / クラウドソーシングにおけるラベル付けタスクのアノテーターの根拠

When collecting item ratings from human judges, it can be difficult to measure and enforce data quality due to task subjectivity and lack of transparency into how judges make each rating decision. To address this, we investigate asking judges to provide a specific form of rationale supporting each rating decision. We evaluate this approach on an information retrieval task in which human judges rate the relevance of Web pages for different search topics. Cost-benefit analysis over 10,000 judgments collected on Amazon’s Mechanical Turk suggests a win-win. Firstly, rationales yield a multitude of benefits: more reliable judgments, greater transparency for evaluating both human raters and their judgments, reduced need for expert gold, the opportunity for dual-supervision from ratings and rationales, and added value from the rationales themselves. Secondly, once experienced in the task, crowd workers provide rationales with almost no increase in task completion time. Consequently, we can realize the above benefits with minimal additional cost.



人間の審査員からアイテムの評価を収集する場合、タスクの主観性と、審査員が各評価決定を行う方法に関する透明性の欠如のために、データの品質を測定および強化することが困難な場合があります。この問題を解決するために、審査員に各評価決定を裏付ける具体的な形式の根拠を提供するよう求めることを調査します。このアプローチを、人間の審査員がさまざまな検索トピックに対するWebページの関連性を評価する情報検索タスクで評価します。AmazonのMechanical Turkで収集された10,000件の判断に関する費用便益分析は、双方にメリットがあることを示唆しています。まず、根拠は多くの利点をもたらします。より信頼性の高い判断、人間の評価者とその判断を評価する際の透明性の向上、専門家によるゴールドの必要性の低減、評価と根拠に基づく二重監督の機会、そして根拠自体による付加価値などです。次に、クラウドワーカーはタスクに慣れれば、タスク完了時間をほとんど増やすことなく根拠を提供できます。したがって、最小限の追加コストで上記の利点を実現できます。

Diagnosis of Deep Discrete-Event Systems

Diagnosis of Deep Discrete-Event Systems / 深層離散事象システムの診断

An abduction-based diagnosis technique for a class of discrete-event systems (DESs), called deep DESs (DDESs), is presented. A DDES has a tree structure, where each node is a network of communicating automata, called an active unit (AU). The interaction of components within an AU gives rise to emergent events. An emergent event occurs when specific components collectively perform a sequence of transitions matching a given regular language. Any event emerging in an AU triggers the transition of a component in its parent AU. We say that the DDES has a deep behavior, in the sense that the behavior of an AU is governed not only by the events exchanged by the components within the AU but also by the events emerging from child AUs. Deep behavior characterizes not only living beings, including humans, but also artifacts, such as robots that operate in contexts at varying abstraction levels. Surprisingly, experimental results indicate that the hierarchical complexity of the system translates into a decreased computational complexity of the diagnosis task. Hence, the diagnosis technique is shown to be (formally) correct as well as (empirically) efficient.



離散事象システム（DES）の一種であるディープDES（DDES）を対象とした、アブダクションに基づく診断手法を提案します。DDESはツリー構造を持ち、各ノードはアクティブユニット（AU）と呼ばれる通信オートマトンのネットワークです。AU内のコンポーネント間の相互作用により、創発イベントが発生します。創発イベントは、特定のコンポーネントが、与えられた正規言語に一致する一連の遷移を集合的に実行した場合に発生します。AU内で発生したイベントは、その親AU内のコンポーネントの遷移をトリガーします。AUの振る舞いは、AU内のコンポーネント間で交換されるイベントだけでなく、子AUから発生するイベントによっても制御されるという意味で、DDESはディープな振る舞いを持つと言える。ディープな振る舞いは、人間を含む生物だけでなく、様々な抽象度のコンテキストで動作するロボットなどの人工物にも見られます。驚くべきことに、実験結果は、システムの階層的な複雑さが、診断タスクの計算複雑さの低減につながることを示しています。したがって、この診断手法は（形式的に）正しいだけでなく、（経験的に）効率的であることが示されます。

The Parameterized Complexity of Motion Planning for Snake-Like Robots

The Parameterized Complexity of Motion Planning for Snake-Like Robots / ヘビ型ロボットの動作計画のパラメータ化された複雑性

We study the parameterized complexity of a variant of the classic video game Snake that models real-world problems of motion planning. Given a snake-like robot with an initial position and a final position in an environment (modeled by a graph), our objective is to determine whether the robot can reach the final position from the initial position without intersecting itself. Naturally, this problem models a wide-variety of scenarios, ranging from the transportation of linked wagons towed by a locomotor at an airport or a supermarket to the movement of a group of agents that travel in an “ant-like” fashion and the construction of trains in amusement parks. Unfortunately, already on grid graphs, this problem is PSPACE-complete. Nevertheless, we prove that even on general graphs, the problem is solvable in FPT time with respect to the size of the snake. In particular, this shows that the problem is fixed-parameter tractable (FPT). Towards this, we show how to employ color-coding to sparsify the configuration graph of the problem to reduce its size significantly. We believe that our approach will find other applications in motion planning. Additionally, we show that the problem is unlikely to admit a polynomial kernel even on grid graphs, but it admits a treewidth-reduction procedure. To the best of our knowledge, the study of the parameterized complexity of motion planning problems (where the intermediate configurations of the motion are of importance) has so far been largely overlooked. Thus, our work is pioneering in this regard.



我々は、現実世界の運動計画問題をモデル化する、古典的なビデオゲーム「スネーク」の亜種のパラメータ化された複雑性を研究します。環境（グラフでモデル化）における初期位置と最終位置を持つヘビ型ロボットが与えられた場合、我々の目的は、ロボットが初期位置から交差することなく最終位置に到達できるかどうかを判断することです。当然のことながら、この問題は、空港やスーパーマーケットにおける移動体で牽引される連結された貨車の輸送から、「アリのように」移動するエージェント群の移動、遊園地における列車の建設に至るまで、多岐にわたるシナリオをモデル化します。残念ながら、この問題はグリッドグラフ上で既にPSPACE完全です。しかしながら、我々は一般的なグラフ上でも、ヘビのサイズに関してFPT時間で解けることを証明します。特に、これは問題が固定パラメータで実行可能である（FPT）ことを示す。これに向けて、我々はカラーコーディングを用いて問題の構成グラフをスパース化し、そのサイズを大幅に削減する方法を示す。我々のアプローチは動作計画にも応用できると考えています。さらに、この問題はグリッドグラフ上であっても多項式カーネルを許容する可能性は低いが、ツリー幅削減手順は許容することを示す。我々の知る限り、動作計画問題（動作の中間構成が重要となる問題）のパラメータ化された複雑性の研究は、これまでほとんど見過ごされてきた。したがって、我々の研究はこの点で先駆的です。

Improved High Dimensional Discrete Bayesian Network Inference using Triplet Region Construction

Improved High Dimensional Discrete Bayesian Network Inference using Triplet Region Construction / トリプレット領域構築を用いた高次元離散ベイジアンネットワーク推論の改良

Performing efficient inference on high dimensional discrete Bayesian Networks (BNs) is challenging. When using exact inference methods the space complexity can grow exponentially with the tree-width, thus making computation intractable. This paper presents a general purpose approximate inference algorithm, based on a new region belief approximation method, called Triplet Region Construction (TRC). TRC reduces the cluster space complexity for factorized models from worst-case exponential to polynomial by performing graph factorization and producing clusters of limited size. Unlike previous generations of region-based algorithms, TRC is guaranteed to converge and effectively addresses the region choice problem that bedevils other region-based algorithms used for BN inference. Our experiments demonstrate that it also achieves significantly more accurate results than competing algorithms.



高次元離散ベイジアンネットワーク（BN）上で効率的な推論を実行することは困難です。正確な推論手法を用いる場合、空間複雑度はツリー幅とともに指数関数的に増大し、計算が手に負えなくなる可能性があります。本論文では、トリプレット領域構築（TRC）と呼ばれる新しい領域確信近似法に基づく汎用近似推論アルゴリズムを紹介します。TRCは、グラフ分解を行い、限られたサイズのクラスターを生成することで、分解モデルのクラスター空間計算量を最悪の場合の指数関数から多項式へと削減します。従来の領域ベースアルゴリズムとは異なり、TRCは収束が保証されており、BN推論に使用される他の領域ベースアルゴリズムを悩ませる領域選択問題を効果的に解決します。また、私たちの実験では、TRCが競合アルゴリズムよりも大幅に高精度な結果を達成することが実証されています。

Planning High-Level Paths in Hostile, Dynamic, and Uncertain Environments

Planning High-Level Paths in Hostile, Dynamic, and Uncertain Environments / 過酷で動的かつ不確実な環境における高レベル経路計画

This paper introduces and studies a graph-based variant of the path planning problem arising in hostile environments. We consider a setting where an agent (e.g. a robot) must reach a given destination while avoiding being intercepted by probabilistic entities which exist in the graph with a given probability and move according to a probabilistic motion pattern known a priori. Given a goal vertex and a deadline to reach it, the agent must compute the path to the goal that maximizes its chances of survival. We study the computational complexity of the problem, and present two algorithms for computing high quality solutions in the general case: an exact algorithm based on Mixed-Integer Nonlinear Programming, working well in instances of moderate size, and a pseudo-polynomial time heuristic algorithm allowing to solve large scale problems in reasonable time. We also consider the two limit cases where the agent can survive with probability 0 or 1, and provide specialized algorithms to detect these kinds of situations more efficiently.



本論文では、敵対的な環境下で生じる経路計画問題のグラフベースの変種を紹介し、考察します。エージェント（例えばロボット）が、グラフ上に所定の確率で存在し、事前に既知の確率的な動作パターンに従って移動する確率的エンティティによる妨害を回避しながら、所定の目的地に到達しなければならない状況を考える。目標頂点とそこに到達する期限が与えられた場合、エージェントは生存の可能性を最大化する目標までの経路を計算する必要があります。本論文では、この問題の計算複雑性を検討し、一般的なケースにおいて高品質な解を計算する2つのアルゴリズムを提示します。1つは混合整数非線形計画法に基づく厳密解アルゴリズムで、中規模のインスタンスで有効に機能します。もう1つは擬似多項式時間ヒューリスティックアルゴリズムで、大規模な問題を妥当な時間で解くことができます。また、エージェントが確率0または1で生存できる2つの極限ケースを考察し、これらの状況をより効率的に検出するための特殊なアルゴリズムも提供します。

Constraint and Satisfiability Reasoning for Graph Coloring

Constraint and Satisfiability Reasoning for Graph Coloring / グラフ彩色のための制約と充足可能性推論

Graph coloring is an important problem in combinatorial optimization and a major component of numerous allocation and scheduling problems. In this paper we introduce a hybrid CP/SAT approach to graph coloring based on the addition-contraction recurrence of Zykov. Decisions correspond to either adding an edge between two non-adjacent vertices or contracting these two vertices, hence enforcing inequality or equality, respectively. This scheme yields a symmetry-free tree and makes learnt clauses stronger by not committing to a particular color. We introduce a new lower bound for this problem based on Mycielskian graphs; a method to produce a clausal explanation of this bound for use in a CDCL algorithm; a branching heuristic emulating Brélaz’ heuristic on the Zykov tree; and dedicated pruning techniques relying on marginal costs with respect to the bound and on reasoning about transitivity when unit propagating learnt clauses. The combination of these techniques in both a branch-and-bound and in a bottom-up search outperforms other SAT-based approaches and Dsatur on standard benchmarks both for finding upper bounds and for proving lower bounds.



グラフ彩色は、組合せ最適化における重要な問題であり、多くの割り当て問題やスケジューリング問題の主要な構成要素です。本稿では、ジコフの加法縮減法に基づくグラフ彩色へのハイブリッドCP/SATアプローチを紹介します。決定は、隣接していない2つの頂点間に辺を追加するか、これらの2つの頂点を縮減するかのいずれかに対応し、それぞれ不等式または等式を強制します。この方式は対称性のないツリーを生成し、特定の色にコミットしないことで学習した節を強化します。この問題に対する新しい下限値、CDCLアルゴリズムで使用するためにこの上限値の節説明を生成する方法、ジコフ木でBrélazのヒューリスティックをエミュレートする分岐ヒューリスティック、および上限値に関する限界費用と学習した節を単位伝播する際の推移性に関する推論に基づく専用の枝刈り手法を紹介します。これらの手法を分岐限定法とボトムアップ探索の両方で組み合わせることで、上限値の探索と下限値の証明の両方において、標準的なベンチマークにおいて他のSATベースのアプローチやDsaturよりも優れた性能を発揮します。

Neural Machine Translation: A Review

Neural Machine Translation: A Review / ニューラル機械翻訳：レビュー

The field of machine translation (MT), the automatic translation of written text from one natural language into another, has experienced a major paradigm shift in recent years. Statistical MT, which mainly relies on various count-based models and which used to dominate MT research for decades, has largely been superseded by neural machine translation (NMT), which tackles translation with a single neural network. In this work we will trace back the origins of modern NMT architectures to word and sentence embeddings and earlier examples of the encoder-decoder network family. We will conclude with a short survey of more recent trends in the field.



機械翻訳（MT）分野、すなわちある自然言語から別の自然言語への書かれたテキストの自動翻訳は、近年大きなパラダイムシフトを経験しました。数十年にわたりMT研究の主流であった、主に様々なカウントベースモデルに依存する統計的MTは、単一のニューラルネットワークで翻訳を行うニューラル機械翻訳（NMT）に大きく取って代わられました。本研究では、現代のNMTアーキテクチャの起源を、単語と文の埋め込み、そしてエンコーダー-デコーダーネットワークファミリーの初期の例まで遡ります。最後に、この分野における最近の動向について簡単に概説します。

AMP Chain Graphs: Minimal Separators and Structure Learning Algorithms

AMP Chain Graphs: Minimal Separators and Structure Learning Algorithms / AMPチェーングラフ：最小セパレータと構造学習アルゴリズム

This paper deals with chain graphs (CGs) under the Andersson–Madigan–Perlman (AMP) interpretation. We address the problem of finding a minimal separator in an AMP CG, namely, finding a set Z of nodes that separates a given non-adjacent pair of nodes such that no proper subset of Z separates that pair. We analyze several versions of this problem and offer polynomial time algorithms for each. These include finding a minimal separator from a restricted set of nodes, finding a minimal separator for two given disjoint sets, and testing whether a given separator is minimal. To address the problem of learning the structure of AMP CGs from data, we show that the PC-like algorithm is order dependent, in the sense that the output can depend on the order in which the variables are given. We propose several modifications of the PC-like algorithm that remove part or all of this order-dependence. We also extend the decomposition-based approach for learning Bayesian networks (BNs) to learn AMP CGs, which include BNs as a special case, under the faithfulness assumption. We prove the correctness of our extension using the minimal separator results. Using standard benchmarks and synthetically generated models and data in our experiments demonstrate the competitive performance of our decomposition-based method, called LCD-AMP, in comparison with the (modified versions of) PC-like algorithm. The LCD-AMP algorithm usually outperforms the PC-like algorithm, and our modifications of the PC-like algorithm learn structures that are more similar to the underlying ground truth graphs than the original PC-like algorithm, especially in high-dimensional settings. In particular, we empirically show that the results of both algorithms are more accurate and stabler when the sample size is reasonably large and the underlying graph is sparse



本論文では、アンダーソン・マディガン・パールマン(AMP)解釈に基づく連鎖グラフ(CG)を扱う。AMP CGにおける最小のセパレータを見つける問題、すなわち、隣接していないノードのペアを分離するノードの集合Zであって、そのペアをZの適切な部分集合が分離しないものを見つける問題を取り扱う。この問題のいくつかのバージョンを分析し、それぞれに対する多項式時間アルゴリズムを提示します。これらには、制限されたノード集合から最小のセパレータを見つける方法、与えられた2つの互いに素な集合に対する最小のセパレータを見つける方法、および与えられたセパレータが最小であるかどうかをテストする方法が含まれます。データからAMP CGの構造を学習する問題を解決するために、PCのようなアルゴリズムは順序に依存する、つまり出力が変数が与えられた順序に依存することを示す。この順序依存性の一部またはすべてを除去するPCのようなアルゴリズムの修正をいくつか提案します。また、ベイジアンネットワーク（BN）学習における分解ベースのアプローチを、忠実性仮定の下でBNを特別なケースとして含むAMP CGの学習に拡張します。最小分離器の結果を用いて、この拡張の正しさを証明します。標準ベンチマークと合成生成モデルおよびデータを用いた実験では、LCD-AMPと呼ばれる分解ベースの手法が、PCライクアルゴリズム（の修正版）と比較して競争力のある性能を示す。LCD-AMPアルゴリズムは通常、PCライクアルゴリズムよりも優れた性能を示し、PCライクアルゴリズムの修正版は、特に高次元設定において、元のPCライクアルゴリズムよりも基礎となるグラウンドトゥルースグラフに類似した構造を学習します。特に、サンプルサイズが適度に大きく、基礎となるグラフがスパースである場合、両方のアルゴリズムの結果がより正確で安定していることを経験的に示す。

The PETLON Algorithm to Plan Efficiently for Task-Level-Optimal Navigation

The PETLON Algorithm to Plan Efficiently for Task-Level-Optimal Navigation / 効率的な計画のためのPETLONアルゴリズムタスクレベル最適ナビゲーション

Intelligent mobile robots have recently become able to operate autonomously in large-scale indoor environments for extended periods of time. In this process, mobile robots need the capabilities of both task and motion planning. Task planning in such environments involves sequencing the robot’s high-level goals and subgoals, and typically requires reasoning about the locations of people, rooms, and objects in the environment, and their interactions to achieve a goal. One of the prerequisites for optimal task planning that is often overlooked is having an accurate estimate of the actual distance (or time) a robot needs to navigate from one location to another. State-of-the-art motion planning algorithms, though often computationally complex, are designed exactly for this purpose of finding routes through constrained spaces.In this article, we focus on integrating task and motion planning (TMP) to achieve task-level-optimal planning for robot navigation while maintaining manageable computational efficiency. To this end, we introduce TMP algorithm PETLON (Planning Efficiently for Task-Level-Optimal Navigation), including two configurations with different trade-offs over computational expenses between task and motion planning, for everyday service tasks using a mobile robot. Experiments have been conducted both in simulation and on a mobile robot using object delivery tasks in an indoor office environment. The key observation from the results is that PETLON is more efficient than a baseline approach that pre-computes motion costs of all possible navigation actions, while still producing plans that are optimal at the task level. We provide results with two different task planning paradigms in the implementation of PETLON, and offer TMP practitioners guidelines for the selection of task planners from an engineering perspective.



近年、知能移動ロボットは大規模な屋内環境で長期間にわたり自律的に動作できるようになった。このプロセスにおいて、移動ロボットはタスク計画と動作計画の両方の能力を必要とします。このような環境におけるタスク計画には、ロボットの高レベル目標とサブ目標の順序付けが含まれ、通常、環境内の人、部屋、物体の位置、そして目標達成のためのそれらの相互作用に関する推論が必要です。最適なタスク計画の前提条件の一つとして見落とされがちなのは、ロボットがある場所から別の場所へ移動するために必要な実際の距離（または時間）を正確に推定することです。最先端の動作計画アルゴリズムは、計算量が複雑になることが多いものの、まさにこの制約のある空間を通る経路を見つけるという目的のために設計されています。本稿では、タスク計画と動作計画（TMP）を統合し、扱いやすい計算効率を維持しながら、ロボットナビゲーションのためのタスクレベル最適計画を実現することに焦点を当てます。この目的のために、移動ロボットを用いた日常的なサービスタスク向けに、タスク計画と動作計画の計算コストに関するトレードオフが異なる2つの構成を含むTMPアルゴリズムPETLON（Planning Efficiently for Task-Level-Optimal Navigation）を紹介します。屋内オフィス環境での物体配送タスクにおいて、シミュレーションと移動ロボットの両方で実験を行いました。結果から得られた重要な知見は、PETLONが、タスクレベルで最適な計画を作成しながらも、あらゆる可能なナビゲーション動作の動作コストを事前に計算するベースラインアプローチよりも効率的であるということです。PETLONの実装における2つの異なるタスクプランニングパラダイムの結果を示し、TMP実践者に対し、エンジニアリングの観点からタスクプランナーを選択するためのガイドラインを提供します。

Properties of Switch-List Representations of Boolean Functions

Properties of Switch-List Representations of Boolean Functions / ブール関数のスイッチリスト表現の特性

In this paper, we focus on a less usual way to represent Boolean functions, namely on representations by switch-lists, which are closely related to interval representations. Given a truth table representation of a Boolean function f the switch-list representation of f is a list of Boolean vectors from the truth table which have a different function value than the preceding Boolean vector in the truth table. The main aim of this paper is to include this type of representation in the Knowledge Compilation Map by Darwiche and Marquis and to argue that switch-lists may in certain situations constitute a reasonable choice for a target language in knowledge compilation. First, we compare switch-list representations with a number of standard representations (such as CNF, DNF, and OBDD) with respect to their relative succinctness. As a by-product of this analysis, we also give a short proof of a longstanding open question proposed by Darwiche and Marquis, namely the incomparability of MODS (models) and PI (prime implicates) representations. Next, using the succinctness result between switch-lists and OBDDs, we develop a polynomial time compilation algorithm from switch-lists to OBDDs. Finally, we analyze which standard transformations and queries (those considered by Darwiche and Marquis) can be performed in polynomial time with respect to the size of the input if the input knowledge is represented by a switch-list. We show that this collection is very broad and the combination of polynomial time transformations and queries is quite unique. Some of the queries can be answered directly using the switch-list input, others require a compilation of the input to OBDD representations which are then used to answer the queries.



本稿では、ブール関数を表現するあまり一般的ではない方法、つまり区間表現と密接な関係のあるスイッチリストによる表現に焦点を当てます。ブール関数fの真理値表表現が与えられたとき、fのスイッチリスト表現は、真理値表のブールベクトルのリストであり、これらのベクトルは真理値表の前のブールベクトルとは異なる関数値を持ちます。本稿の主な目的は、このタイプの表現をDarwicheとMarquisによる知識コンパイル マップに含め、特定の状況ではスイッチリストが知識コンパイルにおけるターゲット言語の合理的な選択となり得ることを主張することです。まず、スイッチリスト表現といくつかの標準的な表現(CNF、DNF、OBDDなど)の簡潔さを比較します。この分析の副産物として、DarwicheとMarquisによって提唱された長年の未解決問題、つまりMODS (モデル)とPI (主含意)表現の比較不可能性についての短い証明も示します。次に、スイッチリストとOBDD間の簡潔性の結果を使用して、スイッチリストからOBDDへの多項式時間コンパイルアルゴリズムを開発します。最後に、入力知識がスイッチリストで表現されている場合、どの標準的な変換とクエリ(DarwicheとMarquisによって検討されたもの)が入力のサイズに関して多項式時間で実行できるかを分析します。このコレクションは非常に幅広く、多項式時間変換とクエリの組み合わせは非常にユニークであることを示します。クエリの一部はスイッチリスト入力を使用して直接回答できますが、他のクエリは入力をOBDD表現にコンパイルし、それを使用してクエリに回答する必要があります。

Computing Bayes-Nash Equilibria in Combinatorial Auctions with Verification

Computing Bayes-Nash Equilibria in Combinatorial Auctions with Verification / 検証付き組み合わせオークションにおけるベイズ・ナッシュ均衡の計算

We present a new algorithm for computing pure-strategy ε-Bayes-Nash equilibria (ε-BNEs) in combinatorial auctions. The main innovation of our algorithm is to separate the algorithm’s search phase (for finding the ε-BNE) from the verification phase (for computing the ε). Using this approach, we obtain an algorithm that is both very fast and provides theoretical guarantees on the ε it finds. Our main contribution is a verification method which, surprisingly, allows us to upper bound the ε across the whole continuous value space without making assumptions about the mechanism. Using our algorithm, we can now compute ε-BNEs in multi-minded domains that are significantly more complex than what was previously possible to solve. We release our code under an open-source license to enable researchers to perform algorithmic analyses of auctions, to enable bidders to analyze different strategies, and many other applications.



組み合わせオークションで純粋戦略 ε-ベイズ-ナッシュ均衡(ε-BNE)を計算するための新しいアルゴリズムを紹介します。このアルゴリズムの主な革新は、アルゴリズムの検索フェーズ(ε-BNEを見つけるため)と検証フェーズ(ε を計算するため)を分離していることです。このアプローチを用いることで、非常に高速でありながら、発見したεの理論的な保証も提供するアルゴリズムを実現しました。私たちの主な貢献は、驚くべきことに、メカニズムに関する仮定を置くことなく、連続値空間全体にわたってεの上限を定めることを可能にする検証手法です。このアルゴリズムを用いることで、これまで解くことのできなかった、はるかに複雑な多面的領域におけるε-BNEを計算できるようになりました。私たちは、研究者がオークションのアルゴリズム解析を行ったり、入札者が様々な戦略を解析したり、その他多くの応用ができるように、オープンソースライセンスの下でコードを公開しています。

The Bottleneck Simulator: A Model-Based Deep Reinforcement Learning Approach

The Bottleneck Simulator: A Model-Based Deep Reinforcement Learning Approach / ボトルネックシミュレータ：モデルベースの深層強化学習アプローチ

Deep reinforcement learning has recently shown many impressive successes. However, one major obstacle towards applying such methods to real-world problems is their lack of data-efficiency. To this end, we propose the Bottleneck Simulator: a model-based reinforcement learning method which combines a learned, factorized transition model of the environment with rollout simulations to learn an effective policy from few examples. The learned transition model employs an abstract, discrete (bottleneck) state, which increases sample efficiency by reducing the number of model parameters and by exploiting structural properties of the environment. We provide a mathematical analysis of the Bottleneck Simulator in terms of fixed points of the learned policy, which reveals how performance is affected by four distinct sources of error: an error related to the abstract space structure, an error related to the transition model estimation variance, an error related to the transition model estimation bias, and an error related to the transition model class bias. Finally, we evaluate the Bottleneck Simulator on two natural language processing tasks: a text adventure game and a real-world, complex dialogue response selection task. On both tasks, the Bottleneck Simulator yields excellent performance beating competing approaches.



深層強化学習は近年、多くの目覚ましい成果を上げています。しかし、こうした手法を現実世界の問題に適用する上での大きな障害の一つは、データ効率の低さです。そこで、本研究ではボトルネックシミュレータを提案します。これは、学習済みの環境の因子分解遷移モデルとロールアウトシミュレーションを組み合わせたモデルベース強化学習手法であり、少数の例から効果的な方策を学習します。学習済みの遷移モデルは、抽象的な離散状態（ボトルネック状態）を採用しており、モデルパラメータの数を削減し、環境の構造的特性を活用することでサンプル効率を向上させます。本研究では、学習済み方策の固定点を用いてボトルネックシミュレータの数学的解析を行い、4つの異なる誤差源（抽象空間構造に関連する誤差、遷移モデル推定分散に関連する誤差、遷移モデル推定バイアスに関連する誤差、遷移モデルクラスバイアスに関連する誤差）がパフォーマンスに及ぼす影響を明らかにします。最後に、テキストアドベンチャーゲームと現実世界の複雑な対話応答選択タスクという2つの自然言語処理タスクにおいて、ボトルネックシミュレータを評価します。ボトルネックシミュレータは、どちらのタスクにおいても、競合する手法を凌駕する優れた性能を発揮します。

Maximin Share Allocations on Cycles

Maximin Share Allocations on Cycles / サイクルにおける最大シェア配分

The problem of fair division of indivisible goods is a fundamental problem of resource allocation in multi-agent systems, also studied extensively in social choice. Recently, the problem was generalized to the case when goods form a graph and the goal is to allocate goods to agents so that each agent’s bundle forms a connected subgraph. For the maximin share fairness criterion, researchers proved that if goods form a tree, an allocation offering each agent a bundle of at least her maximin share value always exists. Moreover, it can be found in polynomial time. In this paper we consider the problem of maximin share allocations of goods on a cycle. Despite the simplicity of the graph, the problem turns out to be significantly harder than its tree version. We present cases when maximin share allocations of goods on cycles exist and provide in this case results on allocations guaranteeing each agent a certain fraction of her maximin share. We also study algorithms for computing maximin share allocations of goods on cycles.



分割不可能な財の公平な分配問題は、マルチエージェントシステムにおける資源配分の基本的な問題であり、社会選択においても広く研究されています。最近、この問題は、財がグラフを形成する場合に一般化され、各エージェントの束が連結された部分グラフを形成するように財をエージェントに割り当てることが目標となりました。最大シェア公平性基準に関して、研究者らは、財が木を形成する場合、各エージェントに少なくとも最大シェア値以上の束を提供する配分が常に存在することを証明しました。しかも、これは多項式時間で見つけることができます。本論文では、サイクル上の財の最大シェア配分問題を考察します。グラフは単純ですが、この問題は木の場合よりもはるかに困難であることがわかります。本論文では、サイクル上の財の最大シェア配分が存在する事例を示し、この場合において、各エージェントに最大シェアの一定割合を保証する配分の結果を示します。また、サイクル上の財の最大シェア配分を計算するアルゴリズムについても検討します。

Belief change and 3-valued logics: Characterization of 19,683 belief change operators

Belief change and 3-valued logics: Characterization of 19,683 belief change operators / 信念変化と3値論理：19,683個の信念変化演算子の特性評価

In this work we introduce a 3-valued logic with modalities, with the aim of having a clear and precise representation of epistemic states, thus the formulas of this logic will be our epistemic states. Indeed, these formulas are identified with ranking functions of 3 values, a generalization of total preorders of three levels. In this framework we analyze some types of changes of these epistemic structures and give syntactical characterizations of them in the introduced logic. In particular, we introduce and study carefully a new operator called Cautious Improvement operator. We also characterize all operators that are definable in this framework.



本研究では、認識状態を明確かつ正確に表現することを目的として、様相を持つ3値論理を導入します。したがって、この論理の式が認識状態となります。実際、これらの式は3値のランキング関数、つまり3レベルの全前置順序の一般化と同一視されます。本研究では、これらの認識構造の変化のいくつかの種類を分析し、導入した論理におけるそれらの統語的特徴付けを行う。特に、慎重改善演算子と呼ばれる新しい演算子を導入し、詳細に検討します。また、この枠組みで定義可能なすべての演算子の特徴付けを行う。

On Sparse Discretization for Graphical Games

On Sparse Discretization for Graphical Games / グラフィカルゲームにおけるスパース離散化について

Graphical games are one of the earliest examples of the impact that the general field of graphical models have had in other areas, and in this particular case, in classical mathematical models in game theory. Graphical multi-hypermatrix games, a concept formally introduced in this research note, generalize graphical games while allowing the possibility of further space savings in model representation to that of standard graphical games. The main focus of this research note is discretization schemes for computing approximate Nash equilibria, with emphasis on graphical games, but also briefly touching on normal-form and polymatrix games. The main technical contribution is a theorem that establishes sufficient conditions for a discretization of the players’ space of mixed strategies to contain an approximate Nash equilibrium. The result is actually stronger because every exact Nash equilibrium has a nearby approximate Nash equilibrium on the grid induced by the discretization. The sufficient conditions are weaker than those of previous results. In particular, a uniform discretization of size linear in the inverse of the approximation error and in the natural game-representation parameters suffices. The theorem holds for a generalization of graphical games, introduced here. The result has already been useful in the design and analysis of tractable algorithms for graphical games with parametric payoff functions and certain game-graph structures. For standard graphical games, under natural conditions, the discretization is logarithmic in the game-representation size, a substantial improvement over the linear dependency previously required. Combining the improved discretization result with old results on constraint networks in AI simplifies the derivation and analysis of algorithms for computing approximate Nash equilibria in graphical games.



グラフィカルゲームは、グラフィカルモデルという一般分野が他の分野、特にゲーム理論における古典的な数学モデルに与えた影響の最も初期の例の一つです。本研究ノートで正式に導入された概念であるグラフィカルマルチハイパーマトリックスゲームは、グラフィカルゲームを一般化すると同時に、標準的なグラフィカルゲームよりもモデル表現の空間を節約することが可能です。本研究ノートの主な焦点は、近似ナッシュ均衡を計算するための離散化スキームであり、グラフィカルゲームに重点を置きつつ、正規形ゲームやポリマトリックスゲームについても簡単に触れています。主な技術的貢献は、混合戦略のプレイヤー空間を離散化する際に近似ナッシュ均衡を含むための十分条件を確立する定理です。この結果は実際にはより強力です。なぜなら、すべての正確なナッシュ均衡は、離散化によって誘導されるグリッド上に近傍の近似ナッシュ均衡を持つからです。この十分条件は、以前の結果よりも弱いものです。特に、近似誤差の逆数と自然なゲーム表現パラメータに線形なサイズの均一離散化で十分です。この定理は、ここで紹介するグラフィカルゲームの一般化に当てはまる。この結果は、パラメトリックなペイオフ関数と特定のゲームグラフ構造を持つグラフィカルゲームの扱いやすいアルゴリズムの設計と分析にすでに役立っています。標準的なグラフィカルゲームの場合、自然な条件下では、離散化はゲーム表現サイズに対して対数的であり、これまで必要とされていた線形依存性を大幅に改善しています。改善された離散化結果をAIにおける制約ネットワークに関する以前の結果と組み合わせると、グラフィカルゲームで近似ナッシュ均衡を計算するアルゴリズムの導出と分析が簡素化されます。

The Complexity Landscape of Outcome Determination in Judgment Aggregation

The Complexity Landscape of Outcome Determination in Judgment Aggregation / 判断集約における結果決定の複雑性ランドスケープ

We provide a comprehensive analysis of the computational complexity of the outcome determination problem for the most important aggregation rules proposed in the literature on logic-based judgment aggregation. Judgment aggregation is a powerful and flexible framework for studying problems of collective decision making that has attracted interest in a range of disciplines, including Legal Theory, Philosophy, Economics, Political Science, and Artificial Intelligence. The problem of computing the outcome for a given list of individual judgments to be aggregated into a single collective judgment is the most fundamental algorithmic challenge arising in this context. Our analysis applies to several different variants of the basic framework of judgment aggregation that have been discussed in the literature, as well as to a new framework that encompasses all existing such frameworks in terms of expressive power and representational succinctness.



論理ベースの判断集約に関する文献で提案されている最も重要な集約ルールの結果決定問題の計算複雑性の包括的な分析を提供します。判断集約は、集団的意思決定の問題を研究するための強力かつ柔軟な枠組みであり、法理論、哲学、経済学、政治学、人工知能など、幅広い分野で関心を集めています。与えられた個々の判断のリストを単一の集団的判断に集約するための結果を計算する問題は、この文脈において生じる最も基本的なアルゴリズム的課題です。本分析は、文献で議論されてきた判断集約の基本枠組みの様々なバリエーション、そして表現力と表現の簡潔さという点で既存の枠組みをすべて包含する新しい枠組みに適用されます。

Structure from Randomness in Halfspace Learning with the Zero-One Loss

Structure from Randomness in Halfspace Learning with the Zero-One Loss / ゼロワン損失を伴う半空間学習におけるランダム性からの構造化

We prove risk bounds for halfspace learning when the data dimensionality is allowed to be larger than the sample size, using a notion of compressibility by random projection. In particular, we give upper bounds for the empirical risk minimizer learned efficiently from randomly projected data, as well as uniform upper bounds in the full high-dimensional space. Our main findings are the following: i) In both settings, the obtained bounds are able to discover and take advantage of benign geometric structure, which turns out to depend on the cosine similarities between the classifier and points of the input space, and provide a new interpretation of margin distribution type arguments. ii) Furthermore our bounds allow us to draw new connections between several existing successful classification algorithms, and we also demonstrate that our theory is predictive of empirically observed performance in numerical simulations and experiments. iii) Taken together, these results suggest that the study of compressive learning can improve our understanding of which benign structural traits – if they are possessed by the data generator – make it easier to learn an effective classifier from a sample.



ランダム射影による圧縮可能性の概念を用いて、データ次元がサンプルサイズよりも大きくてもよい場合の半空間学習におけるリスク境界を証明した。特に、ランダム射影データから効率的に学習された経験的リスク最小化器の上限値と、高次元空間全体における一様上限値を示した。主な知見は以下の通りです。i)どちらの設定においても、得られた境界値は、分類器と入力空間の点との間のコサイン類似度に依存する良性幾何学的構造を発見し、それを利用します。また、マージン分布型議論の新たな解釈も提供します。ii)さらに、我々の境界値を用いることで、既存の複数の成功した分類アルゴリズム間に新たな関連性を見出すことが可能となり、また、我々の理論が数値シミュレーションと実験において経験的に観測された性能を予測できることも実証した。iii)これらの結果を総合すると、圧縮学習の研究によって、データ生成器がどのような良性構造特性を持っているか（もしそれがデータ生成器に備わっているならば）、サンプルから効果的な分類器を学習することを容易にする特性についての理解が深まることが示唆されます。

Using Machine Learning for Decreasing State Uncertainty in Planning

Using Machine Learning for Decreasing State Uncertainty in Planning / 機械学習を用いた計画における状態不確実性の低減

We present a novel approach for decreasing state uncertainty in planning prior to solving the planning problem. This is done by making predictions about the state based on currently known information, using machine learning techniques. For domains where uncertainty is high, we define an active learning process for identifying which information, once sensed, will best improve the accuracy of predictions.We demonstrate that an agent is able to solve problems with uncertainties in the state with less planning effort compared to standard planning techniques. Moreover, agents can solve problems for which they could not find valid plans without using predictions. Experimental results also demonstrate that using our active learning process for identifying information to be sensed leads to gathering information that improves the prediction process.



計画問題を解く前に、計画における状態の不確実性を低減するための新たなアプローチを提示します。これは、機械学習技術を用いて、現在既知の情報に基づいて状態を予測することによって行われます。不確実性が高い領域では、感知されたどの情報が予測精度を最も向上させるかを識別する能動学習プロセスを定義します。エージェントは、標準的な計画手法と比較して、より少ない計画労力で、状態に不確実性がある問題を解決できることを示す。さらに、エージェントは予測を使用せずに有効な計画を見つけることができなかった問題を解決できます。実験結果は、感知する情報を識別するために我々の能動学習プロセスを使用することで、予測プロセスを改善する情報を収集できることも示しています。

Mapping the landscape of Artificial Intelligence applications against COVID-19

Mapping the landscape of Artificial Intelligence applications against COVID-19 / COVID-19に対する人工知能アプリケーションのランドスケープのマッピング

COVID-19, the disease caused by the SARS-CoV-2 virus, has been declared a pandemic by the World Health Organization, which has reported over 18 million confirmed cases as of August 5, 2020. In this review, we present an overview of recent studies using Machine Learning and, more broadly, Artificial Intelligence, to tackle many aspects of the COVID19 crisis. We have identified applications that address challenges posed by COVID-19 at different scales, including: molecular, by identifying new or existing drugs for treatment; clinical, by supporting diagnosis and evaluating prognosis based on medical imaging and non-invasive measures; and societal, by tracking both the epidemic and the accompanying infodemic using multiple data sources. We also review datasets, tools, and resources needed to facilitate Artificial Intelligence research, and discuss strategic considerations related to the operational implementation of multidisciplinary partnerships and open science. We highlight the need for international cooperation to maximize the potential of AI in this and future pandemics.



SARS-CoV-2ウイルスによって引き起こされる疾患であるCOVID-19は、世界保健機関（WHO）によってパンデミックと宣言されており、2020年8月5日現在、1,800万人以上の感染者が報告されています。本レビューでは、機械学習、より広義には人工知能を用いてCOVID-19危機の多くの側面に取り組む最近の研究の概要を示す。COVID-19がもたらす課題に対処するための様々な応用分野を特定しました。分子レベルでは、治療薬の新規または既存の薬剤の特定、臨床レベルでは、医用画像や非侵襲的測定に基づく診断支援と予後評価、そして社会レベルでは、複数のデータソースを用いて流行とそれに伴うインフォデミックの両方を追跡することなどです。また、人工知能研究を促進するために必要なデータセット、ツール、リソースを検証し、学際的パートナーシップとオープンサイエンスの運用実装に関する戦略的考慮事項についても議論します。今回のパンデミックおよび将来のパンデミックにおいてAIの可能性を最大限に引き出すためには、国際協力の必要性を強調します。

Contrasting the Spread of Misinformation in Online Social Networks

Contrasting the Spread of Misinformation in Online Social Networks / オンラインソーシャルネットワークにおける誤情報の拡散の対比

Online social networks are nowadays one of the most effective and widespread tools used to share information. In addition to being employed by individuals for communicating with friends and acquaintances, and by brands for marketing and customer service purposes, they constitute a primary source of daily news for a significant number of users. Unfortunately, besides legit news, social networks also allow to effectively spread inaccurate or even entirely fabricated ones. Also due to sensationalist claims, misinformation can spread from the original sources to a large number of users in a very short time, with negative consequences that, in extreme cases, can even put at risk public safety or health.In this work we discuss and propose methods to limit the spread of misinformation over online social networks. The issue is split in two separate sub-problems. We first aim to identify the most probable sources of the misinformation among the subset of users that have been reached by it. In the second step, assuming to know the misinformation sources, we want to locate a minimum number of monitors (that is, entities able to identify and block false information) in the network in order to prevent that the misinformation campaign reaches some “critical” nodes while maintaining low the number of nodes exposed to the infection.For each of the two issues, we provide both heuristics and mixed integer programming formulations. To verify the quality and efficiency of our suggested solutions, we conduct experiments on several real-world networks. The results of this extensive experimental phase validate our heuristics as effective tools to contrast the spread of misinformation in online social networks.Regarding the source identification step, our approach showed success rates above 80% in most of the considered settings, and above 60% in almost all of them.With respect to the second issue, our heuristic proved to be able to obtain solutions that exceeded (in terms of number of required monitors) the ones obtained through our MILP-based approach of more than 20% in only few test scenarios. Our heuristics for both problems also proved to outperform significantly some previously proposed algorithms.



オンラインソーシャルネットワークは、今日、情報共有に最も効果的かつ広く利用されているツールの一つです。個人が友人や知人とコミュニケーションをとるために、また企業がマーケティングや顧客サービスのために利用することに加えて、多くのユーザーにとって日々のニュースの主要な情報源となっています。しかし残念なことに、ソーシャルネットワークは正当なニュースだけでなく、不正確なニュースや全く捏造されたニュースさえも効果的に拡散させています。また、扇情的な主張によって、誤情報が元の情報源から非常に短時間で多数のユーザーに拡散し、極端な場合には公共の安全や健康を危険にさらすという悪影響をもたらす可能性があります。本研究では、オンラインソーシャルネットワーク上での誤情報の拡散を制限する方法について議論し、提案します。この問題は2つの別々のサブ問題に分かれています。まず、誤情報が到達したユーザーのサブセットの中で、最も可能性の高い誤情報源を特定することを目的とします。2番目のステップでは、誤情報の発信元がわかっていると仮定し、感染にさらされるノードの数を低く抑えながら、誤情報キャンペーンが一部の「重要な」ノードに到達するのを防ぐために、ネットワーク内に最小限の数のモニター（つまり、誤情報を識別してブロックできるエンティティ）を配置します。2つの問題それぞれに対して、ヒューリスティックと混合整数計画法の両方を提供します。提案するソリューションの品質と効率を検証するために、いくつかの実際のネットワークで実験を行います。この大規模な実験フェーズの結果は、オンライン ソーシャル ネットワークにおける誤情報の拡散を対比するための効果的なツールとして、ヒューリスティックを検証しました。発信元識別ステップに関しては、検討した設定のほとんどで80%を超える成功率、ほぼすべての設定で60%を超える成功率を示しました。2番目の問題に関しては、ヒューリスティックにより、MILPベースのアプローチで得られたソリューションを（必要なモニターの数の観点から）わずか数個のテスト シナリオで20%以上上回るソリューションを取得できることが証明されました。両問題に対する我々のヒューリスティックは、これまで提案されていたアルゴリズムを大幅に上回る性能を示すことも証明されました。

Incompatibilities Between Iterated and Relevance-Sensitive Belief Revision

Incompatibilities Between Iterated and Relevance-Sensitive Belief Revision / 反復型信念修正と関連性依存型信念修正の非互換性

The AGM paradigm for belief change, as originally introduced by Alchourron, Gärdenfors and Makinson, lacks any guidelines for the process of iterated revision. One of the most influential work addressing this problem is Darwiche and Pearl’s approach (DP approach, for short), which, despite its well-documented shortcomings, remains to this date the most dominant. In this article, we make further observations on the DP approach. In particular, we prove that the DP postulates are, in a strong sense, inconsistent with Parikh’s relevance-sensitive axiom (P), extending previous initial conflicts. Immediate consequences of this result are that an entire class of intuitive revision operators, which includes Dalal’s operator, violates the DP postulates, as well as that the Independence postulate and Spohn’s conditionalization are inconsistent with axiom (P). The whole study, essentially, indicates that two fundamental aspects of the revision process, namely, iteration and relevance, are in deep conflict, and opens the discussion for a potential reconciliation towards a comprehensive formal framework for knowledge dynamics.



信念変化のためのAGMパラダイムは、Alchourron、Gärdenfors、Makinsonによって最初に導入されたが、反復修正のプロセスに関するガイドラインが欠如しています。この問題に対処する最も影響力のある研究の一つは、DarwicheとPearlによるアプローチ（略してDPアプローチ）であり、十分に裏付けられた欠点にもかかわらず、今日まで最も有力なアプローチであり続けています。本稿では、DPアプローチについてさらに考察します。特に、DP公理は、以前の初期の矛盾を拡張し、Parikhの関連性感受性公理（P）と強い意味で矛盾することを証明した。この結果の直接的な帰結として、Dalalの演算子を含む直感的な修正演算子のクラス全体がDP公理に違反し、独立公理とSpohnの条件付けが公理（P）と矛盾するという点が挙げられます。研究全体は、本質的に、改訂プロセスの2つの基本的な側面、つまり反復と関連性が深刻な対立状態にあることを示しており、知識ダイナミクスの包括的な正式なフレームワークに向けた潜在的な和解のための議論のきっかけとなっています。

To Regulate or Not: A Social Dynamics Analysis of an Idealised AI Race

To Regulate or Not: A Social Dynamics Analysis of an Idealised AI Race / 規制するか否か：理想化されたAIレースの社会動態分析

Rapid technological advancements in Artificial Intelligence (AI), as well as the growing deployment of intelligent technologies in new application domains, have generated serious anxiety and a fear of missing out among different stake-holders, fostering a racing narrative. Whether real or not, the belief in such a race for domain supremacy through AI, can make it real simply from its consequences, as put forward by the Thomas theorem. These consequences may be negative, as racing for technological supremacy creates a complex ecology of choices that could push stake-holders to underestimate or even ignore ethical and safety procedures. As a consequence, different actors are urging to consider both the normative and social impact of these technological advancements, contemplating the use of the precautionary principle in AI innovation and research. Yet, given the breadth and depth of AI and its advances, it is difficult to assess which technology needs regulation and when. As there is no easy access to data describing this alleged AI race, theoretical models are necessary to understand its potential dynamics, allowing for the identification of when procedures need to be put in place to favour outcomes beneficial for all. We show that, next to the risks of setbacks and being reprimanded for unsafe behaviour, the time-scale in which domain supremacy can be achieved plays a crucial role. When this can be achieved in a short term, those who completely ignore the safety precautions are bound to win the race but at a cost to society, apparently requiring regulatory actions. Our analysis reveals that imposing regulations for all risk and timing conditions may not have the anticipated effect as only for specific conditions a dilemma arises between what is individually preferred and globally beneficial. Similar observations can be made for the long-term development case. Yet different from the short-term situation, conditions can be identified that require the promotion of risk-taking as opposed to compliance with safety regulations in order to improve social welfare. These results remain robust both when two or several actors are involved in the race and when collective rather than individual setbacks are produced by risk-taking behaviour. When defining codes of conduct and regulatory policies for applications of AI, a clear understanding of the time-scale of the race is thus required, as this may induce important non-trivial effects.This article is part of the special track on AI and Society.



人工知能（AI）における急速な技術進歩と、新たな応用分野におけるインテリジェント技術の導入拡大は、様々なステークホルダーの間で深刻な不安と取り残されることへの恐怖を生み出し、競争という物語を助長しています。現実であるか否かに関わらず、AIによるドメイン覇権をめぐるこのような競争への信念は、トーマス定理が提唱する結果から見て、それを現実のものにしてしまう可能性があります。こうした結果は否定的なものとなる可能性があります。なぜなら、技術覇権をめぐる競争は、ステークホルダーが倫理的および安全手順を過小評価したり、無視したりする可能性のある複雑な選択の生態系を生み出すからです。結果として、様々な関係者が、AIのイノベーションと研究における予防原則の適用を検討しつつ、これらの技術進歩の規範的および社会的影響の両方を考慮するよう強く求めています。しかし、AIとその進歩の幅広さと深さを考えると、どの技術にいつ規制が必要かを判断することは困難です。このいわゆるAI競争を記述するデータへの容易なアクセスは不可能であるため、その潜在的なダイナミクスを理解するには理論モデルが必要であり、すべての人にとって有益な結果をもたらすための手順をいつ導入すべきかを特定できます。我々は、後退や不安全行動に対する叱責のリスクに加え、ドメイン優位性を達成できる時間スケールが重要な役割を果たすことを示す。これが短期間で達成できる場合、安全対策を完全に無視する者が競争に勝つことは確実だが、社会にコストがかかり、規制措置が必要となるのは明らかです。我々の分析は、特定の状況においてのみ、個人が望むことと世界的に有益なことの間でジレンマが生じるため、すべてのリスクとタイミングの条件に規制を課しても期待される効果が得られない可能性があることを明らかにした。長期的な発展のケースについても同様の観察が可能です。しかし、短期的な状況とは異なり、社会福祉を向上させるためには、安全規制の遵守ではなく、リスクテイクの促進が必要となる状況を特定することができます。これらの結果は、2人以上のアクターが競争に関与している場合、またリスクテイク行動によって個人ではなく集団的な後退が生じた場合のいずれにおいても、堅牢性を維持します。AI応用に関する行動規範や規制政策を定義する際には、競争の時間スケールを明確に理解することが求められます。これは、重要な非自明な影響を引き起こす可能性があるためです。本稿はAIと社会に関する特別トラックの一部です。

Qualitative Numeric Planning: Reductions and Complexity

Qualitative Numeric Planning: Reductions and Complexity / 定性的数値計画：縮約と複雑性

Qualitative numerical planning is classical planning extended with non-negative real variables that can be increased or decreased “qualitatively”, i.e., by positive indeterminate amounts. While deterministic planning with numerical variables is undecidable in general, qualitative numerical planning is decidable and provides a convenient abstract model for generalized planning. The solutions to qualitative numerical problems (QNPs) were shown to correspond to the strong cyclic solutions of an associated fully observable non-deterministic (FOND) problem that terminate. This leads to a generate-and-test algorithm for solving QNPs where solutions to a FOND problem are generated one by one and tested for termination. The computational shortcomings of this approach for solving QNPs, however, are that it is not simple to amend FOND planners to generate all solutions, and that the number of solutions to check can be doubly exponential in the number of variables. In this work we address these limitations while providing additional insights on QNPs. More precisely, we introduce two polynomial-time reductions, one from QNPs to FOND problems and the other from FOND problems to QNPs both of which do not involve termination tests. A result of these reductions is that QNPs are shown to have the same expressive power and the same complexity as FOND problems.



定性的数値計画とは、非負の実変数を用いて「定性的に」、すなわち正の不確定な量だけ増減できる、古典的な計画を拡張したものです。数値変数を用いた決定論的計画は一般に決定不可能ですが、定性的数値計画は決定可能であり、一般化計画のための便利な抽象モデルを提供します。定性的数値問題（QNP）の解は、関連する完全観測非決定論的問題（FOND）の停止する強巡回解に対応することが示されました。これは、FOND問題の解を一つずつ生成し、停止性をテストする、QNPを解くための生成・テストアルゴリズムにつながります。しかし、QN​​Pを解くこのアプローチには、FONDプランナーを修正してすべての解を生成するのが簡単ではないこと、そして検証すべき解の数が変数の数に対して二重指数関数的になる可能性があることなど、計算上の欠点があります。本研究では、これらの限界に対処しつつ、QNPに関する更なる知見を提供します。より正確には、QNPからFOND問題への、そしてFOND問題からQNPへの、2つの多項式時間縮約を導入します。どちらも停止性テストを必要としません。これらの縮約の結果、QNPはFOND問題と同等の表現力と計算量を持つことが示されます。

Modular Structures and Atomic Decomposition in Ontologies

Modular Structures and Atomic Decomposition in Ontologies / オントロジーにおけるモジュール構造とアトミック分解

With the growth of ontologies used in diverse application areas, the need for module extraction and modularisation techniques has risen. The notion of the modular structure of an ontology, which comprises a suitable set of base modules together with their logical dependencies, has the potential to help users and developers in comprehending, sharing, and maintaining an ontology. We have developed a new modular structure, called atomic decomposition (AD), which is based on modules that provide strong logical properties, such as locality-based modules. In this article, we present the theoretical foundations of AD, review its logical and computational properties, discuss its suitability as a modular structure, and report on an experimental evaluation of AD. In addition, we discuss the concept of a modular structure in ontology engineering and provide a survey of existing decomposition approaches.



多様な応用分野で使用されるオントロジーの増加に伴い、モジュール抽出およびモジュール化技術の必要性が高まっています。適切な基本モジュールセットとその論理依存関係から構成されるオントロジーのモジュール構造の概念は、ユーザーと開発者がオントロジーを理解、共有、および維持するのに役立つ可能性があります。私たちは、局所性ベースのモジュールなど、強力な論理特性を提供するモジュールに基づく、アトミック分解(AD)と呼ばれる新しいモジュール構造を開発しました。この記事では、ADの理論的基礎を示し、その論理的および計算的特性をレビューし、モジュール構造としての適合性を議論し、ADの実験的評価を報告します。さらに、オントロジーエンジニアリングにおけるモジュール構造の概念について議論し、既存の分解アプローチの調査を提供します。

参考文献

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

関連情報

• Journal of Artificial Intelligence Research: 論文一覧