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

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

目次

論文

On the Cluster Admission Problem for Cloud Computing

On the Cluster Admission Problem for Cloud Computing / クラウドコンピューティングにおけるクラスター参加問題について

Cloud computing providers face the problem of matching heterogeneous customer workloads to resources that will serve them. This is particularly challenging if customers, who are already running a job on a cluster, scale their resource usage up and down over time. The provider therefore has to continuously decide whether she can add additional workloads to a given cluster or if doing so would impact existing workloads’ ability to scale. Currently, this is often done using simple threshold policies to reserve large parts of each cluster, which leads to low efficiency (i.e., low average utilization of the cluster). We propose more sophisticated policies for controlling admission to a cluster and demonstrate that they significantly increase cluster utilization. We first introduce the cluster admission problem and formalize it as a constrained Partially Observable Markov Decision Process (POMDP). As it is infeasible to solve the POMDP optimally, we then systematically design admission policies that estimate moments of each workload’s distribution of future resource usage. Via extensive simulations grounded in a trace from Microsoft Azure, we show that our admission policies lead to a substantial improvement over the simple threshold policy. We then show that substantial further gains are possible if high-quality information is available about arriving workloads. Based on this, we propose an information elicitation approach to incentivize users to provide this information and simulate its effects.



クラウドコンピューティングプロバイダーは、異種混在の顧客ワークロードと、それらに対応するリソースをマッチングさせるという課題に直面しています。これは、既にクラスター上でジョブを実行している顧客が、時間の経過とともにリソース使用量を増減させる場合に特に困難となります。そのため、プロバイダーは、特定のクラスターにワークロードを追加できるかどうか、あるいはそうすることで既存のワークロードのスケーリング能力に影響が出るかどうかを継続的に判断する必要があります。現在、この判断は、各クラスターの大部分を予約するための単純なしきい値ポリシーを用いて行われることが多く、効率性の低下(つまり、クラスターの平均利用率の低下)につながっています。本稿では、クラスターへのアドミッションを制御するためのより洗練されたポリシーを提案し、それがクラスター利用率を大幅に向上させることを実証します。まず、クラスターアドミッション問題を提示し、それを制約付き部分観測マルコフ決定過程(POMDP)として定式化します。POMDPを最適に解くことは不可能であるため、各ワークロードの将来のリソース使用量の分布のモーメントを推定するアドミッションポリシーを体系的に設計します。Microsoft Azureのトレースに基づいた広範なシミュレーションにより、提案するアドミッションポリシーが単純なしきい値ポリシーよりも大幅に改善されることを示します。次に、到着するワークロードに関する高品質の情報が利用可能であれば、大幅なさらなる利益が得られる可能性があることを示します。これに基づいて、ユーザーがこの情報を提供するようにインセンティブを与え、その効果をシミュレートするための情報引き出しアプローチを提案します。

Election Manipulation on Social Networks: Seeding, Edge Removal, Edge Addition

Election Manipulation on Social Networks: Seeding, Edge Removal, Edge Addition / ソーシャルネットワークにおける選挙操作:シーディング、エッジ削除、エッジ追加

We focus on the election manipulation problem through social influence, where a manipulator exploits a social network to make her most preferred candidate win an election. Influence is due to information in favor of and/or against one or multiple candidates, sent  by seeds and spreading through the network according to the independent cascade model.  We provide a comprehensive theoretical study of the election control problem, investigating  two forms of manipulations: seeding to buy influencers given a social network and removing  or adding edges in the social network given the set of the seeds and the information sent.  In particular, we study a wide range of cases distinguishing in the number of candidates or  the kind of information spread over the network.Our main result shows that the election manipulation problem is not affordable in  the worst-case, even when one accepts to get an approximation of the optimal margin of  victory, except for the case of seeding when the number of hard-to-manipulate voters is not  too large, and the number of uncertain voters is not too small, where we say that a voter  that does not vote for the manipulator’s candidate is hard-to-manipulate if there is no way  to make her vote for this candidate, and uncertain otherwise.We also provide some results showing the hardness of the problems in special cases.  More precisely, in the case of seeding, we show that the manipulation is hard even if the  graph is a line and that a large class of algorithms, including most of the approaches  recently adopted for social-influence problems (e.g., greedy, degree centrality, PageRank, VoteRank), fails to compute a bounded approximation even on elementary networks, such  as undirected graphs with every node having a degree at most two or directed trees. In the  case of edge removal or addition, our hardness results also apply to election manipulation  when the manipulator has an unlimited budget, being allowed to remove or add an arbitrary  number of edges, and to the basic case of social influence maximization/minimization in  the restricted case of finite budget.Interestingly, our hardness results for seeding and edge removal/addition still hold  in a re-optimization variant, where the manipulator already knows an optimal solution  to the problem and computes a new solution once a local modification occurs, e.g., the  removal/addition of a single edge.



私たちは、ソーシャルインフルエンスによる選挙操作問題に焦点を当てます。この問題では、操作者がソーシャルネットワークを利用して、最も好ましい候補者を選挙に勝利させます。影響は、シードによって送信され、独立カスケードモデルに従ってネットワークを通じて広がる、1人または複数の候補者に有利または不利な情報によるものです。私たちは、選挙制御問題の包括的な理論的研究を提供し、2つの形式の操作を調査します。1つは、ソーシャルネットワークが与えられた場合にインフルエンサーを購入するためのシード処理、もう1つは、シードと送信された情報のセットが与えられた場合にソーシャルネットワーク内のエッジを削除または追加する操作です。特に、我々は候補者の数やネットワーク上に広がる情報の種類を区別する広範囲のケースを研究します。我々の主な結果は、操作困難な投票者の数が多すぎず、不確実な投票者の数が少なすぎない場合のシードのケースを除いて、たとえ最適な勝利の差の近似値を得ることを受け入れたとしても、最悪の場合、選挙操作問題は許容できないことを示しています。この場合、操作者の候補者に投票しない投票者は、その候補者に投票させる方法がない場合には操作が困難であり、そうでない場合は不確実であると言う。また、特殊なケースにおける問題の難しさを示すいくつかの結果も提供します。より正確に言うと、シーディングの場合、グラフが直線であっても操作が困難であること、および社会的影響の問題に最近採用されているほとんどのアプローチ(貪欲法、次数中心性、PageRank、VoteRankなど)を含む多くのアルゴリズムが、各ノードの次数が最大2である無向グラフや有向木などの基本ネットワークであっても、有界近似を計算できないことを示します。エッジの削除または追加のケースでは、我々の困難性の結果は、マニピュレータの予算が無制限で任意の数のエッジを削除または追加できる場合の選挙操作、および有限予算の制限されたケースでの社会的影響力の最大化/最小化の基本的なケースにも適用されます。興味深いことに、シーディングとエッジの削除/追加の困難性の結果は、マニピュレータが問題の最適解をすでに知っており、ローカル変更(たとえば、単一のエッジの削除/追加)が発生すると新しい解を計算する再最適化バリアントでも保持されます。

Probabilistic Temporal Networks with Ordinary Distributions: Theory, Robustness and Expected Utility

Probabilistic Temporal Networks with Ordinary Distributions: Theory, Robustness and Expected Utility / 通常分布を持つ確率的時系列ネットワーク:理論、ロバスト性、期待効用

Most existing works in Probabilistic Simple Temporal Networks (PSTNs) base their frameworks on well-defined, parametric probability distributions. Under the operational contexts of both strong and dynamic control, this paper addresses robustness measure of PSTNs, i.e. the execution success probability, where the probability distributions of the contingent durations are ordinary, not necessarily parametric, nor symmetric (e.g. histograms, PERT), as long as these can be discretized. In practice, one would obtain ordinary distributions by considering empirical observations (compiled as histograms), or even hand-drawn by field experts. In this new realm of PSTNs, we study and formally define concepts such as degree of weak/strong/dynamic controllability, robustness under a predefined dispatching protocol, and introduce the concept of PSTN expected execution utility. We also discuss the limitation of existing controllability levels, and propose new levels within dynamic controllability, to better characterize dynamic controllable PSTNs based on based practical complexity considerations. We propose a novel fixed-parameter pseudo-polynomial time computation method to obtain both the success probability and expected utility measures. We apply our computation method to various PSTN datasets, including realistic planetary exploration scenarios in the context of the Mars 2020 rover. Moreover, we propose additional original applications of the method.



確率的単純時間ネットワーク(PSTN)に関する既存の研究の多くは、明確に定義されたパラメトリック確率分布をフレームワークとして採用しています。本稿では、強制御と動的制御の両方の運用コンテキストにおいて、PSTNの堅牢性指標、すなわち実行成功確率について考察します。この場合、偶発的な持続時間の確率分布は通常の分布であり、必ずしもパラメトリックでも対称的(例えば、ヒストグラム、PERT)でもありませんが、離散化できる場合に限ります。実際には、経験的観察(ヒストグラムとしてまとめたもの)や、現場の専門家による手描きの分布を考慮することで、通常の分布が得られます。このPSTNの新しい領域において、本稿では、弱制御性/強制御性/動的制御性の程度、定義済みディスパッチプロトコルにおける堅牢性などの概念を研究し、正式に定義します。また、PSTNの期待実行効用という概念を導入します。さらに、既存の制御性レベルの限界について議論し、実用的な複雑性を考慮した上で、動的制御可能なPSTNをより適切に特徴付けるために、動的制御性における新しいレベルを提案します。我々は、成功確率と期待効用尺度の両方を得るための、新たな固定パラメータ擬似多項式時間計算法を提案します。我々は、この計算法を、Mars 2020ローバーのコンテキストにおける現実的な惑星探査シナリオを含む、さまざまなPSTNデータセットに適用します。さらに、この方法の追加の独自の応用を提案します。

Socially Responsible AI Algorithms: Issues, Purposes, and Challenges

Socially Responsible AI Algorithms: Issues, Purposes, and Challenges / 社会的に責任のあるAIアルゴリズム:課題、目的、そして課題

In the current era, people and society have grown increasingly reliant on artificial intelligence (AI) technologies. AI has the potential to drive us towards a future in which all of humanity flourishes. It also comes with substantial risks for oppression and calamity. Discussions about whether we should (re)trust AI have repeatedly emerged in recent years and in many quarters, including industry, academia, healthcare, services, and so on. Technologists and AI researchers have a responsibility to develop trustworthy AI systems. They have responded with great effort to design more responsible AI algorithms. However, existing technical solutions are narrow in scope and have been primarily directed towards algorithms for scoring or classification tasks, with an emphasis on fairness and unwanted bias. To build long-lasting trust between AI and human beings, we argue that the key is to think beyond algorithmic fairness and connect major aspects of AI that potentially cause AI’s indifferent behavior. In this survey, we provide a systematic framework of Socially Responsible AI Algorithms that aims to examine the subjects of AI indifference and the need for socially responsible AI algorithms, define the objectives, and introduce the means by which we may achieve these objectives. We further discuss how to leverage this framework to improve societal well-being through protection, information, and prevention/mitigation.This article appears in the special track on AI & Society.



現代において、人々と社会は人工知能(AI)技術への依存度が高まっています。AIは、人類全体が繁栄する未来へと私たちを導く可能性を秘めています。しかし、AIは抑圧と災難の大きなリスクも伴う。近年、AIを(再)信頼すべきかどうかについての議論は、産業界、学界、医療、サービスなど、多くの方面で繰り返し浮上しています。技術者とAI研究者は、信頼できるAIシステムを開発する責任があります。彼らは、より責任あるAIアルゴリズムを設計するために多大な努力を払ってきた。しかし、既存の技術的ソリューションは範囲が狭く、主に公平性と不要なバイアスを重視したスコアリングまたは分類タスクのアルゴリズムに向けられてきた。AIと人間の間に永続的な信頼を築く鍵は、アルゴリズムの公平性を超えて、AIの無関心な行動を引き起こす可能性のあるAIの主要な側面を結びつけることだと私たちは考えています。本調査では、社会的に責任あるAIアルゴリズムの体系的な枠組みを提示し、AIの無関心というテーマと社会的に責任あるAIアルゴリズムの必要性を検証し、その目的を定義し、それらの目的を達成するための手段を紹介します。さらに、この枠組みを活用して、保護、情報提供、予防・緩和を通じて社会の幸福を向上させる方法についても議論します。本稿は「AIと社会」特別トラックに掲載されています。

Trends in Integration of Vision and Language Research: A Survey of Tasks, Datasets, and Methods

Trends in Integration of Vision and Language Research: A Survey of Tasks, Datasets, and Methods / 視覚と言語研究の統合における動向:タスク、データセット、そして手法の概観

Interest in Artificial Intelligence (AI) and its applications has seen unprecedented growth in the last few years. This success can be partly attributed to the advancements made in the sub-fields of AI such as machine learning, computer vision, and natural language processing. Much of the growth in these fields has been made possible with deep learning, a sub-area of machine learning that uses artificial neural networks. This has created significant interest in the integration of vision and language. In this survey, we focus on ten prominent tasks that integrate language and vision by discussing their problem formulation, methods, existing datasets, evaluation measures, and compare the results obtained with corresponding state-of-the-art methods. Our efforts go beyond earlier surveys which are either task-specific or concentrate only on one type of visual content, i.e., image or video. Furthermore, we also provide some potential future directions in this field of research with an anticipation that this survey stimulates innovative thoughts and ideas to address the existing challenges and build new applications.



人工知能(AI)とその応用への関心は、ここ数年でかつてないほど高まっています。この成功は、機械学習、コンピュータービジョン、自然言語処理といったAIのサブフィールドにおける進歩に一部起因しています。これらの分野の成長の多くは、人工ニューラルネットワークを用いた機械学習のサブ領域であるディープラーニングによって可能になりました。これにより、視覚と言語の統合への関心が高まっています。本調査では、言語と視覚を統合する主要な10のタスクに焦点を当て、それらの問題の定式化、手法、既存のデータセット、評価尺度について議論し、得られた結果を対応する最先端手法と比較します。私たちの取り組みは、タスクを特定したもの、あるいは画像や動画といった1種類の視覚コンテンツのみに焦点を当てた従来の調査を凌駕するものです。さらに、この研究分野における将来の潜在的な方向性も提示し、本調査が既存の課題への対処や新たな応用の構築に向けた革新的な思考やアイデアを刺激することを期待しています。

Learning over No-Preferred and Preferred Sequence of Items for Robust Recommendation

Learning over No-Preferred and Preferred Sequence of Items for Robust Recommendation / ロバストな推薦のための、非選好および選好のアイテムシーケンスの学習

In this paper, we propose a theoretically supported sequential strategy for training a large-scale Recommender System (RS) over implicit feedback, mainly in the form of clicks. The proposed approach consists in minimizing pairwise ranking loss over blocks of consecutive items constituted by a sequence of non-clicked items followed by a clicked one for each user. We present two variants of this strategy where model parameters are updated using either the momentum method or a gradient-based approach. To prevent updating the parameters for an abnormally high number of clicks over some targeted items (mainly due to bots), we introduce an upper and a lower threshold on the number of updates for each user. These thresholds are estimated over the distribution of the number of blocks in the training set. They affect the decision of RS by shifting the distribution of items that are shown to the users. Furthermore, we provide a convergence analysis of both algorithms and demonstrate their practical efficiency over six large-scale collections with respect to various ranking measures and computational time.



本稿では、主にクリックという形で示される暗黙的なフィードバックを用いて、大規模レコメンデーションシステム(RS)を訓練するための、理論的に裏付けられた逐次戦略を提案します。提案するアプローチは、各ユーザーについて、クリックされていないアイテムのシーケンスとクリックされたアイテムのシーケンスで構成される連続アイテムのブロックにおける、ペアワイズランキング損失を最小化するものです。本稿では、この戦略の2つのバリエーションを提示します。これらのバリエーションでは、モデルパラメータをモメンタム法または勾配ベースのアプローチのいずれかを用いて更新します。一部の対象アイテムに対する異常に高いクリック数(主にボットによる)によるパラメータ更新を防ぐため、各ユーザーの更新回数に上限と下限の閾値を導入します。これらの閾値は、訓練セット内のブロック数の分布に基づいて推定されます。これらの閾値は、ユーザーに表示されるアイテムの分布を変化させることで、RSの決定に影響を与える。さらに、両アルゴリズムの収束分析を行い、6つの大規模コレクションにおいて、様々なランキング尺度と計算時間に関して、それらの実用的な効率性を示す。

Welfare Guarantees in Schelling Segregation

Welfare Guarantees in Schelling Segregation / シェリング分離における福祉保証

Schelling’s model is an influential model that reveals how individual perceptions and incentives can lead to residential segregation. Inspired by a recent stream of work, we study welfare guarantees and complexity in this model with respect to several welfare measures. First, we show that while maximizing the social welfare is NP-hard, computing an assignment of agents to the nodes of any topology graph with approximately half of the maximum welfare can be done in polynomial time. We then consider Pareto optimality, introduce two new optimality notions based on it, and establish mostly tight bounds on the worst-case welfare loss for assignments satisfying these notions as well as the complexity of computing such assignments. In addition, we show that for tree topologies, it is possible to decide whether there exists an assignment that gives every agent a positive utility in polynomial time; moreover, when every node in the topology has degree at least 2, such an assignment always exists and can be found efficiently.



シェリングモデルは、個人の認識やインセンティブが居住地の分離にどのようにつながるかを明らかにする影響力のあるモデルです。近年の研究成果に着想を得て、我々はこのモデルにおける福祉保証と複雑性を、いくつかの福祉尺度に関して考察します。まず、社会福祉の最大化はNP困難である一方、任意のトポロジーグラフのノードへのエージェントの割り当てを、最大福祉の約半分となるように計算することは、多項式時間で実行可能であることを示します。次に、パレート最適性を考慮し、それに基づく2つの新しい最適化概念を導入し、これらの概念を満たす割り当てにおける最悪の福祉損失と、そのような割り当ての計算複雑性について、ほぼ厳密な境界を確立します。さらに、ツリートポロジーにおいて、すべてのエージェントに正の効用を与える割り当てが存在するかどうかを多項式時間で決定可能であることを示します。さらに、トポロジー内のすべてのノードの次数が少なくとも2である場合、そのような割り当ては常に存在し、効率的に見つけることができます。

Viewpoint: AI as Author – Bridging the Gap Between Machine Learning and Literary Theory

Viewpoint: AI as Author – Bridging the Gap Between Machine Learning and Literary Theory / 視点:著者としてのAI ― 機械学習と文学理論のギャップを埋める

Anticipating the rise in Artificial Intelligence’s ability to produce original works of literature, this study suggests that literariness, or that which constitutes a text as literary, is understudied in relation to text generation. From a computational perspective, literature is particularly challenging because it typically employs figurative and ambiguous language. Literary expertise would be beneficial to understanding how meaning and emotion are conveyed in this art form but is often overlooked. We propose placing experts from two dissimilar disciplines – machine learning and literary studies – in conversation to improve the quality of AI writing. Concentrating on evaluation as a vital stage in the text generation process, the study demonstrates that benefit could be derived from literary theoretical perspectives. This knowledge would improve algorithm design and enable a deeper understanding of how AI learns and generates.This article appears in the special track on AI and Society.



人工知能(AI)による独創的な文学作品の創出能力の向上を見据え、本研究では、テキスト生成において文学性、すなわちテキストを文学的なものとして構成する要素が十分に研究されていないことを示唆します。計算論的観点から見ると、文学は比喩的で曖昧な言語を用いることが多いため、特に扱いが難しい。文学の専門知識は、この芸術形式において意味や感情がどのように伝えられるかを理解するために有益であるにもかかわらず、しばしば見落とされがちです。本研究では、機械学習と文学研究という2つの異なる分野の専門家を対話させ、AIによる文章の質を向上させることを提案します。テキスト生成プロセスにおける重要な段階として評価に焦点を当て、本研究では文学理論的な視点から得られるメリットを実証します。この知識はアルゴリズム設計を改善し、AIがどのように学習し生成するかをより深く理解することを可能にするだろう。本論文は「AIと社会」特別トラックに掲載されています。

Measuring the Occupational Impact of AI: Tasks, Cognitive Abilities and AI Benchmarks

Measuring the Occupational Impact of AI: Tasks, Cognitive Abilities and AI Benchmarks / AIの職業的影響の測定:タスク、認知能力、そしてAIベンチマーク

In this paper we develop a framework for analysing the impact of Artificial Intelligence (AI) on occupations. This framework maps 59 generic tasks from worker surveys and an occupational database to 14 cognitive abilities (that we extract from the cognitive science literature) and these to a comprehensive list of 328 AI benchmarks used to evaluate research intensity across a broad range of different AI areas. The use of cognitive abilities as an intermediate layer, instead of mapping work tasks to AI benchmarks directly, allows for an identification of potential AI exposure for tasks for which AI applications have not been explicitly created. An application of our framework to occupational databases gives insights into the abilities through which AI is most likely to affect jobs and allows for a ranking of occupations with respect to AI exposure. Moreover, we show that some jobs that were not known to be affected by previous waves of automation may now be subject to higher AI exposure. Finally, we find that some of the abilities where AI research is currently very intense are linked to tasks with comparatively limited labour input in the labour markets of advanced economies (e.g., visual and auditory processing using deep learning, and sensorimotor interaction through (deep) reinforcement learning).This article appears in the special track on AI and Society.



本稿では、人工知能(AI)が職業に与える影響を分析するためのフレームワークを開発します。このフレームワークは、労働者調査と職業データベースからの59の一般的なタスクを14の認知能力(認知科学文献から抽出)にマッピングし、さらにこれらをさまざまなAI領域にわたる研究の強度を評価するために使用される328のAIベンチマークの包括的なリストにマッピングします。作業タスクをAIベンチマークに直接マッピングするのではなく、認知能力を中間層として使用することで、AIアプリケーションが明示的に作成されていないタスクの潜在的なAIエクスポージャーを特定することができます。このフレームワークを職業データベースに適用すると、AIが仕事に最も影響を与える可能性の高い能力についての洞察が得られ、AIエクスポージャーに関して職業をランク付けすることができます。さらに、以前の自動化の波の影響を受けなかった仕事でも、現在ではAIエクスポージャーが高まっている可能性があることを示しています。最後に、現在AI研究が盛んに行われている能力の中には、先進国の労働市場において比較的労働投入の少ないタスク(例えば、深層学習を用いた視覚・聴覚処理、(深層)強化学習による感覚運動相互作用など)に関連しているものがあることがわかった。本稿はAIと社会に関する特別トラックに掲載されています。

RWNE: A Scalable Random-Walk based Network Embedding Framework with Personalized Higher-order Proximity Preserved

RWNE: A Scalable Random-Walk based Network Embedding Framework with Personalized Higher-order Proximity Preserved / RWNE:パーソナライズされた高階近接性を保持する、スケーラブルなランダムウォークベースのネットワーク埋め込みフレームワーク

Higher-order proximity preserved network embedding has attracted increasing attention. In particular, due to the superior scalability, random-walk-based network embedding has also been well developed, which could efficiently explore higher-order neighborhoods via multi-hop random walks. However, despite the success of current random-walk-based methods, most of them are usually not expressive enough to preserve the personalized higher-order proximity and lack a straightforward objective to theoretically articulate what and how network proximity is preserved. In this paper, to address the above issues, we present a general scalable random-walk-based network embedding framework, in which random walk is explicitly incorporated into a sound objective designed theoretically to preserve arbitrary higher-order proximity. Further, we introduce the random walk with restart process into the framework to naturally and effectively achieve personalized-weighted preservation of proximities of different orders. We conduct extensive experiments on several real-world networks and demonstrate that our proposed method consistently and substantially outperforms the state-of-the-art network embedding methods.



高階近接性保存ネットワーク埋め込みはますます注目を集めています。特に、優れたスケーラビリティを持つランダムウォークベースのネットワーク埋め込みも開発が進んでおり、マルチホップランダムウォークを介して高階近傍を効率的に探索することができます。しかし、現在のランダムウォークベースの手法は成功しているものの、そのほとんどは、個人固有の高階近接性を保存するのに十分な表現力がなく、ネットワーク近接性がどのように保存されるかを理論的に明確にするための明確な目的を欠いています。本稿では、上記の問題に対処するため、任意の高階近接性を保存するように理論​​的に設計された健全な目的関数にランダムウォークを明示的に組み込んだ、一般的なスケーラブルなランダムウォークベースのネットワーク埋め込みフレームワークを提示します。さらに、ランダムウォークとリスタートプロセスをフレームワークに導入することで、異なる順序の近接性について、個人に合わせた重み付けによる保存を自然かつ効果的に実現します。複数の実世界ネットワークで広範な実験を行い、提案手法が最先端のネットワーク埋め込み手法を一貫して大幅に上回る性能を発揮することを実証しました。

Declarative Algorithms and Complexity Results for Assumption-Based Argumentation

Declarative Algorithms and Complexity Results for Assumption-Based Argumentation / 仮定に基づく議論のための宣言的アルゴリズムと複雑性の結果

The study of computational models for argumentation is a vibrant area of artificial intelligence and, in particular, knowledge representation and reasoning research. Arguments most often have an intrinsic structure made explicit through derivations from more basic structures. Computational models for structured argumentation enable making the internal structure of arguments explicit. Assumption-based argumentation (ABA) is a central structured formalism for argumentation in AI. In this article, we make both algorithmic and complexity-theoretic advances in the study of ABA. In terms of algorithms, we propose a new approach to reasoning in a commonly studied fragment of ABA (namely the logic programming fragment) with and without preferences. While previous approaches to reasoning over ABA frameworks apply either specialized algorithms or translate ABA reasoning to reasoning over abstract argumentation frameworks, we develop a direct declarative approach to ABA reasoning by encoding ABA reasoning tasks in answer set programming. We show via an extensive empirical evaluation that our approach significantly improves on the empirical performance of current ABA reasoning systems. In terms of computational complexity, while the complexity of reasoning over ABA frameworks is well-understood, the complexity of reasoning in the ABA+ formalism integrating preferences into ABA is currently not fully established. Towards bridging this gap, our results suggest that the integration of preferential information into ABA via so-called reverse attacks results in increased problem complexity for several central argumentation semantics.



議論のための計算モデルの研究は、人工知能、特に知識表現と推論研究において活発な分野です。議論は多くの場合、より基本的な構造からの導出を通して明示化された固有の構造を持っています。構造化された議論のための計算モデルは、議論の内部構造を明示することを可能にします。仮定に基づく議論(ABA)は、AIにおける議論のための中心的な構造化形式主義です。本稿では、ABA研究におけるアルゴリズム理論と複雑性理論の両方の進歩を示します。アルゴリズムの観点から、選好の有無にかかわらず、一般的に研究されているABAの断片(すなわち、論理プログラミング断片)における推論への新しいアプローチを提案します。ABAフレームワークにおける推論への従来のアプローチは、特殊なアルゴリズムを適用するか、ABA推論を抽象的な議論フレームワークにおける推論に翻訳するかのいずれかでしたが、本稿では、ABA推論タスクを解答セットプログラミングでエンコードすることにより、ABA推論への直接的な宣言的アプローチを開発します。広範な実証的評価により、本アプローチが現在のABA推論システムの実証的性能を大幅に向上させることを示します。計算複雑性の観点から見ると、ABAフレームワークにおける推論の複雑さは十分に理解されているものの、選好をABAに統合するABA+形式主義における推論の複雑さは現時点では十分に解明されていません。このギャップを埋めるために、我々の研究結果は、いわゆる逆攻撃を介して選好情報をABAに統合すると、いくつかの中心的な議論意味論において問題の複雑さが増大することを示唆しています。

Playing Codenames with Language Graphs and Word Embeddings

Playing Codenames with Language Graphs and Word Embeddings / 言語グラフと単語埋め込みを用いたコードネームの遊び方

Although board games and video games have been studied for decades in artificial intelligence research, challenging word games remain relatively unexplored. Word games are not as constrained as games like chess or poker. Instead, word game strategy is defined by the players’ understanding of the way words relate to each other. The word game Codenames provides a unique opportunity to investigate common sense understanding of relationships between words, an important open challenge. We propose an algorithm that can generate Codenames clues from the language graph BabelNet or from any of several embedding methods – word2vec, GloVe, fastText or BERT. We introduce a new scoring function that measures the quality of clues, and we propose a weighting term called DETECT that incorporates dictionary-based word representations and document frequency to improve clue selection. We develop BabelNet-Word Selection Framework (BabelNet-WSF) to improve BabelNet clue quality and overcome the computational barriers that previously prevented leveraging language graphs for Codenames. Extensive experiments with human evaluators demonstrate that our proposed innovations yield state-of-the-art performance, with up to 102.8% improvement in precision@2 in some cases. Overall, this work advances the formal study of word games and approaches for common sense language understanding.



ボードゲームやビデオゲームは人工知能研究において数十年にわたって研究されてきましたが、挑戦的な単語ゲームは比較的未開拓のままです。単語ゲームはチェスやポーカーのようなゲームほど制約が多くありません。その代わりに、単語ゲームの戦略は、プレイヤーが単語同士の関係性をどのように理解しているかによって定義されます。単語ゲーム「Codenames」は、単語間の関係性に関する常識的な理解という重要な未解決課題を調査するユニークな機会を提供します。我々は、言語グラフBabelNet、またはword2vec、GloVe、fastText、BERTなどの埋め込み手法のいずれかから「Codenames」の手がかりを生成できるアルゴリズムを提案します。手がかりの質を測定する新しいスコアリング関数を導入し、手がかり選択を改善するために辞書ベースの単語表現と文書頻度を組み込んだDETECTと呼ばれる重み付け項を提案します。BabelNetの手がかりの質を向上させ、これまでコードネームにおける言語グラフの活用を妨げてきた計算上の障壁を克服するために、BabelNet-Word Selection Framework(BabelNet-WSF)を開発しました。人間の評価者による広範な実験により、提案されたイノベーションは最先端のパフォーマンスをもたらし、場合によっては精度@2が最大102.8%向上することが実証されました。全体として、本研究は、単語ゲームと常識的な言語理解のためのアプローチに関する正式な研究を前進させるものです。

A Tight Bound for Stochastic Submodular Cover

A Tight Bound for Stochastic Submodular Cover / 確率的劣モジュラ被覆のタイトバウンド

We show that the Adaptive Greedy algorithm of Golovin and Krause achieves an approximation bound of (ln(Q/η)+1) for Stochastic Submodular Cover: here Q is the “goal value” and η is the minimum gap between Q and any attainable utility value Q’


GolovinとKrauseのAdaptive Greedyアルゴリズムは、Stochastic Submodular Coverの近似境界(ln(Q/η)+1)を達成することを示します。ここで、Qは「目標値」であり、ηはQと達成可能な効用値Q’

Multi-Document Summarization with Determinantal Point Process Attention

Multi-Document Summarization with Determinantal Point Process Attention / 行列式点過程アテンションを用いた複数文書要約

The ability to convey relevant and diverse information is critical in multi-document summarization and yet remains elusive for neural seq-to-seq models whose outputs are often redundant and fail to correctly cover important details. In this work, we propose an attention mechanism which encourages greater focus on relevance and diversity. Attention weights are computed based on (proportional) probabilities given by Determinantal Point Processes (DPPs) defined on the set of content units to be summarized. DPPs have been successfully used in extractive summarisation, here we use them to select relevant and diverse content for neural abstractive summarisation. We integrate DPP-based attention with various seq-to-seq architectures ranging from CNNs to LSTMs, and Transformers. Experimental evaluation shows that our attention mechanism consistently improves summarization and delivers performance comparable with the state-of-the-art on the MultiNews dataset



関連性の高い多様な情報を伝達する能力は、複数文書の要約において重要ですが、出力が冗長で重要な詳細を正しくカバーできないことが多いニューラルseq-to-seqモデルでは依然として困難です。本研究では、関連性と多様性への重点を高める注意メカニズムを提案します。注意の重みは、要約するコンテンツ単位のセットに対して定義された決定論的点過程(DPP)によって与えられる(比例)確率に基づいて計算されます。DPPは抽出要約で効果的に使用されており、ここではニューラル抽象要約のために関連性の高い多様なコンテンツを選択するためにDPPを使用します。我々は、CNNからLSTM、Transformerに至るまでのさまざまなseq-to-seqアーキテクチャとDPPベースの注意を統合します。実験的評価では、私たちの注目メカニズムが要約を一貫して改善し、MultiNewsデータセットで最先端のものと匹敵するパフォーマンスを提供することが示されています。

Representative Committees of Peers

Representative Committees of Peers / ピアの代表委員会

A population of voters must elect representatives among themselves to decide on a sequence of possibly unforeseen binary issues. Voters care only about the final decision, not the elected representatives. The disutility of a voter is proportional to the fraction of issues, where his preferences disagree with the decision. While an issue-by-issue vote by all voters would maximize social welfare, we are interested in how well the preferences of the population can be approximated by a small committee.We show that a k-sortition (a random committee of k voters with the majority vote within the committee) leads to an outcome within the factor 1+O(1/√ k) of the optimal social cost for any number of voters n, any number of issues m, and any preference profile. For a small number of issues m, the social cost can be made even closer to optimal by delegation procedures that weigh committee members according to their number of followers. However, for large m, we demonstrate that the k-sortition is the worst-case optimal rule within a broad family of committee-based rules that take into account metric information about the preference profile of the whole population.



投票者の集団は、予期しない可能性のある一連の二者択一の問題を決定するために、自分たちの中から代表者を選出しなければなりません。投票者は最終決定のみを気にし、選出された代表者には関心がありません。投票者の不効用は、その決定と彼の好みが合わない問題の割合に比例します。すべての投票者が問題を1つずつ投票すれば社会的厚生は最大化されますが、私たちは、小規模な委員会で集団の好みをどの程度正確に近似できるかに関心があります。k抽選(委員会内で過半数の投票権を持つk人の投票者による無作為の委員会)では、任意の投票者数n、任意の問題数m、および任意の選好プロファイルに対して、最適な社会的コストの係数1+O(1/√k)以内の結果が得られることを示します。少数の問題mについては、委員会のメンバーをフォロワー数に応じて評価する委任手順によって、社会的コストをさらに最適に近づけることができます。しかし、mが大きい場合、k-抽選は、人口全体の選好プロファイルに関する計量情報を考慮した委員会ベースのルールの広範なファミリーの中で、最悪のケースの最適ルールであることを示します。

Game Plan: What AI can do for Football, and What Football can do for AI

Game Plan: What AI can do for Football, and What Football can do for AI / ゲームプラン:AIがサッカーにできること、そしてサッカーがAIにできること

The rapid progress in artificial intelligence (AI) and machine learning has opened unprecedented analytics possibilities in various team and individual sports, including baseball, basketball, and tennis. More recently, AI techniques have been applied to football, due to a huge increase in data collection by professional teams, increased computational power, and advances in machine learning, with the goal of better addressing new scientific challenges involved in the analysis of both individual players’ and coordinated teams’ behaviors. The research challenges associated with predictive and prescriptive football analytics require new developments and progress at the intersection of statistical learning, game theory, and computer vision. In this paper, we provide an overarching perspective highlighting how the combination of these fields, in particular, forms a unique microcosm for AI research, while offering mutual benefits for professional teams, spectators, and broadcasters in the years to come. We illustrate that this duality makes football analytics a game changer of tremendous value, in terms of not only changing the game of football itself, but also in terms of what this domain can mean for the field of AI. We review the state-of-the-art and exemplify the types of analysis enabled by combining the aforementioned fields, including illustrative examples of counterfactual analysis using predictive models, and the combination of game-theoretic analysis of penalty kicks with statistical learning of player attributes. We conclude by highlighting envisioned downstream impacts, including possibilities for extensions to other sports (real and virtual).



人工知能(AI)と機械学習の急速な進歩は、野球、バスケットボール、テニスなど、さまざまなチームスポーツや個人スポーツにおいて、前例のない分析の可能性を切り開きました。最近では、プロチームによるデータ収集の大幅な増加、計算能力の向上、機械学習の進歩により、AI技術がサッカーに適用され、個々の選手とチームの行動の分析に伴う新たな科学的課題へのより適切な対応を目指しています。予測的および処方的なサッカー分析に関連する研究課題は、統計学習、ゲー​​ム理論、コンピュータービジョンの交差点における新たな発展と進歩を必要とします。本稿では、これらの分野の組み合わせが、今後数年間でプロチーム、観客、放送局に相互利益をもたらしながら、AI研究の独自の縮図をどのように形成するかを強調する包括的な視点を提供します。この二重性により、フットボール分析は、サッカーという競技自体を変えるだけでなく、この領域がAI分野にどのような意味を持つかという点でも、非常に大きな価値を持つゲームチェンジャーとなることが示されます。本稿では、最先端技術を概観し、前述の分野を組み合わせることで可能になる分析の種類を例示します。具体的には、予測モデルを用いた反事実分析や、ペナルティキックのゲーム理論的分析と選手属性の統計的学習の組み合わせなどが挙げられます。最後に、他のスポーツ(現実およびバーチャル)への拡張の可能性を含め、想定される下流への影響についても考察します。

Confronting Abusive Language Online: A Survey from the Ethical and Human Rights Perspective

Confronting Abusive Language Online: A Survey from the Ethical and Human Rights Perspective / オンライン上の暴言への対処:倫理的および人権的観点からの調査

The pervasiveness of abusive content on the internet can lead to severe psychological and physical harm. Significant effort in Natural Language Processing (NLP) research has been devoted to addressing this problem through abusive content detection and related sub-areas, such as the detection of hate speech, toxicity, cyberbullying, etc. Although current technologies achieve high classification performance in research studies, it has been observed that the real-life application of this technology can cause unintended harms, such as the silencing of under-represented groups. We review a large body of NLP research on automatic abuse detection with a new focus on ethical challenges, organized around eight established ethical principles: privacy, accountability, safety and security, transparency and explainability, fairness and non-discrimination, human control of technology, professional responsibility, and promotion of human values. In many cases, these principles relate not only to situational ethical codes, which may be context-dependent, but are in fact connected to universal human rights, such as the right to privacy, freedom from discrimination, and freedom of expression. We highlight the need to examine the broad social impacts of this technology, and to bring ethical and human rights considerations to every stage of the application life-cycle, from task formulation and dataset design, to model training and evaluation, to application deployment. Guided by these principles, we identify several opportunities for rights-respecting, socio-technical solutions to detect and confront online abuse, including ‘nudging’, ‘quarantining’, value sensitive design, counter-narratives, style transfer, and AI-driven public education applications.evaluation, to application deployment. Guided by these principles, we identify several opportunities for rights-respecting, socio-technical solutions to detect and confront online abuse, including ‘nudging’, ‘quarantining’, value sensitive design, counter-narratives, style transfer, and AI-driven public education applications.



インターネット上の虐待的コンテンツの蔓延は、深刻な精神的・身体的危害につながる可能性があります。自然言語処理(NLP)研究は、虐待的コンテンツの検出や、ヘイトスピーチ、毒性、ネットいじめなどの関連分野を通じて、この問題への対処に多大な労力を費やしてきました。現在の技術は研究においては高い分類性能を達成していますが、現実世界でのこの技術の適用は、過小評価された集団の沈黙といった意図しない危害をもたらす可能性があることが観察されています。本研究では、自動虐待検出に関するNLP研究の膨大な量をレビューし、新たに倫理的課題に焦点を当てます。これらの課題は、プライバシー、説明責任、安全性とセキュリティ、透明性と説明可能性、公平性と差別の禁止、技術の人間による制御、専門家としての責任、そして人間的価値の促進という、確立された8つの倫理原則を中心に構成されています。多くの場合、これらの原則は、状況に依存する可能性のある状況倫理規範だけでなく、プライバシーの権利、差別からの自由、表現の自由といった普遍的な人権にも関連しています。我々は、この技術の幅広い社会的影響を調査し、タスクの策定とデータセットの設計からモデルのトレーニングと評価、アプリケーションの展開に至るまで、アプリケーションのライフサイクルのあらゆる段階に倫理的および人権上の配慮を取り入れる必要性を強調しています。これらの原則に導かれ、我々は「ナッジ」、「隔離」、価値に配慮した設計、カウンターナラティブ、スタイルの転送、AI主導の公教育アプリケーションなど、オンラインでの虐待を検出して対処するための、権利を尊重した社会技術的ソリューションのいくつかの機会を特定しています。評価からアプリケーションの展開まで。これらの原則に導かれ、我々は「ナッジ」、「隔離」、価値に配慮した設計、カウンターナラティブ、スタイルの転送、AI主導の公教育アプリケーションなど、オンラインでの虐待を検出して対処するための、権利を尊重した社会技術的ソリューションのいくつかの機会を特定しています。

EpidemiOptim: A Toolbox for the Optimization of Control Policies in Epidemiological Models

EpidemiOptim: A Toolbox for the Optimization of Control Policies in Epidemiological Models / EpidemiOptim:疫学モデルにおける制御ポリシーの最適化のためのツールボックス

Modeling the dynamics of epidemics helps to propose control strategies based on pharmaceuticaland non-pharmaceutical interventions (contact limitation, lockdown, vaccination,etc). Hand-designing such strategies is not trivial because of the number of possibleinterventions and the difficulty to predict long-term effects. This task can be cast as an optimization problem where state-of-the-art machine learning methods such as deep reinforcement learning might bring significant value. However, the specificity of each domain|epidemic modeling or solving optimization problems|requires strong collaborationsbetween researchers from different fields of expertise. This is why we introduce EpidemiOptim, a Python toolbox that facilitates collaborations between researchers inepidemiology and optimization. EpidemiOptim turns epidemiological models and cost functions into optimization problems via a standard interface commonly used by optimization practitioners (OpenAI Gym). Reinforcement learning algorithms based on QLearning with deep neural networks (DQN) and evolutionary algorithms (NSGA-II) are already implemented. We illustrate the use of EpidemiOptim to find optimal policies fordynamical on-o  lockdown control under the optimization of the death toll and economic recess using a Susceptible-Exposed-Infectious-Removed (SEIR) model for COVID-19. Using EpidemiOptim and its interactive visualization platform in Jupyter notebooks, epidemiologists, optimization practitioners and others (e.g. economists) can easily compare epidemiological models, costs functions and optimization algorithms to address important choicesto be made by health decision-makers. Trained models can be explored by experts and non-experts via a web interface.This article is part of the special track on AI and COVID-19.



流行のダイナミクスをモデル化することは、医薬品および非医薬品介入(接触制限、ロックダウン、ワクチン接種など)に基づく制御戦略を提案するのに役立ちます。このような戦略を手作業で設計するのは、可能な介入の数が多く、長期的な影響を予測するのが難しいため、簡単ではありません。このタスクは最適化問題として捉えることができ、深層強化学習などの最先端の機械学習手法が大きな価値をもたらす可能性があります。しかし、各ドメイン(疫病モデリングまたは最適化問題の解決)の特殊性には、異なる専門分野の研究者間の強力なコラボレーションが必要です。そのため、疫学と最適化の研究者間のコラボレーションを促進するPythonツールボックス、EpidemiOptimを導入します。EpidemiOptimは、最適化の専門家が一般的に使用する標準インターフェース(OpenAI Gym)を介して、疫学モデルとコスト関数を最適化問題に変換します。ディープニューラルネットワーク(DQN)を使用したQLearningと進化アルゴリズム(NSGA-II)に基づく強化学習アルゴリズムはすでに実装されています。COVID-19の感受性-曝露-感染-除去(SEIR)モデルを用いて、死者数と経済停滞の最適化を考慮した上で、EpidemiOptimを用いて動的なロックダウンのオンオフ制御のための最適な政策を見出す方法を説明します。EpidemiOptimとそのJupyterノートブック上のインタラクティブな可視化プラットフォームを利用することで、疫学者、最適化の専門家、そして経済学者などの専門家は、疫学モデル、コスト関数、最適化アルゴリズムを容易に比較し、医療政策決定者が行う重要な選択に対応できます。学習済みモデルは、専門家と非専門家がウェブインターフェースを介して探索できます。この記事は、AIとCOVID-19に関する特別トラックの一部です。

Intelligence in Strategic Games

Intelligence in Strategic Games / 戦略ゲームにおける知性

If an agent, or a coalition of agents, has a strategy, knows that she has a strategy, and knows what the strategy is, then she has a know-how strategy. Several modal logics of coalition power for know-how strategies have been studied before.The contribution of the article is three-fold. First, it proposes a new class of know-how strategies that depend on the intelligence information about the opponents’ actions. Second, it shows that the coalition power modality for the proposed new class of strategies cannot be expressed through the standard know-how modality. Third, it gives a sound and complete logical system that describes the interplay between the coalition power modality with intelligence and the distributed knowledge modality in games with imperfect information.



エージェントまたはエージェントの連合が戦略を持ち、自分が戦略を持っていることを知っており、その戦略が何であるかを知っている場合、そのエージェントはノウハウ戦略を持っています。ノウハウ戦略のための連合力の様相論理はこれまでにもいくつか研究されてきました。本論文の貢献は3つあります。第1に、対戦相手の行動に関する情報に依存する新しいクラスのノウハウ戦略を提案します。第2に、提案された新しいクラスの戦略に対する連合力様相は、標準的なノウハウ様相では表現できないことを示します。第3に、不完全情報ゲームにおける知性を備えた連合力様相と分散知識様相の相互作用を記述する、健全で完全な論理システムを提供します。

Conceptual Modeling of Explainable Recommender Systems: An Ontological Formalization to Guide Their Design and Development

Conceptual Modeling of Explainable Recommender Systems: An Ontological Formalization to Guide Their Design and Development / 説明可能なレコメンデーションシステムの概念モデリング:設計と開発を導くオントロジー的形式化

With the increasing importance of e-commerce and the immense variety of products, users need help to decide which ones are the most interesting to them. This is one of the main goals of recommender systems. However, users’ trust may be compromised if they do not understand how or why the recommendation was achieved. Here, explanations are essential to improve user confidence in recommender systems and to make the recommendation useful.Providing explanation capabilities into recommender systems is not an easy task as their success depends on several aspects such as the explanation’s goal, the user’s expectation, the knowledge available, or the presentation method. Therefore, this work proposes a conceptual model to alleviate this problem by defining the requirements of explanations for recommender systems. Our goal is to provide a model that guides the development of effective explanations for recommender systems as they are correctly designed and suited to the user’s needs. Although earlier explanation taxonomies sustain this work, our model includes new concepts not considered in previous works. Moreover, we make a novel contribution regarding the formalization of this model as an ontology that can be integrated into the development of proper explanations for recommender systems.



電子商取引の重要性が高まり、製品の種類が膨大になるにつれて、ユーザーはどれが最も興味深いかを判断するのに助けを必要としています。これはレコメンデーションシステムの主な目的の1つです。ただし、ユーザーが推奨がどのように、またはなぜ達成されたのかを理解していない場合、信頼が損なわれる可能性があります。ここで、説明は、推薦システムに対するユーザーの信頼を高め、推薦を有用なものにするために不可欠です。推薦システムに説明機能を提供することは容易ではありません。その成功は、説明の目的、ユーザーの期待、利用可能な知識、提示方法など、いくつかの側面に依存するためです。したがって、本研究では、推薦システムの説明の要件を定義することで、この問題を軽減するための概念モデルを提案します。私たちの目標は、推薦システムが正しく設計され、ユーザーのニーズに適合するように、効果的な説明の開発を導くモデルを提供することです。これまでの説明分類法はこの研究を支えてきましたが、私たちのモデルには、以前の研究では考慮されていなかった新しい概念が含まれています。さらに、このモデルを推薦システムの適切な説明の開発に統合できるオントロジーとして形式化するという新たな貢献をしています。

Ethics and Governance of Artificial Intelligence: Evidence from a Survey of Machine Learning Researchers

Ethics and Governance of Artificial Intelligence: Evidence from a Survey of Machine Learning Researchers / 人工知能の倫理とガバナンス:機械学習研究者への調査からのエビデンス

Machine learning (ML) and artificial intelligence (AI) researchers play an important role in the ethics and governance of AI, including through their work, advocacy, and choice of employment. Nevertheless, this influential group’s attitudes are not well understood, undermining our ability to discern consensuses or disagreements between AI/ML researchers. To examine these researchers’ views, we conducted a survey of those who published in two top AI/ML conferences (N = 524). We compare these results with those from a 2016 survey of AI/ML researchers (Grace et al., 2018) and a 2018 survey of the US public (Zhang & Dafoe, 2020). We find that AI/ML researchers place high levels of trust in international organizations and scientific organizations to shape the development and use of AI in the public interest; moderate trust in most Western tech companies; and low trust in national militaries, Chinese tech companies, and Facebook. While the respondents were overwhelmingly opposed to AI/ML researchers working on lethal autonomous weapons, they are less opposed to researchers working on other military applications of AI, particularly logistics algorithms. A strong majority of respondents think that AI safety research should be prioritized and that ML institutions should conduct pre-publication review to assess potential harms. Being closer to the technology itself, AI/ML researchers are well placed to highlight new risks and develop technical solutions, so this novel attempt to measure their attitudes has broad relevance. The findings should help to improve how researchers, private sector executives, and policymakers think about regulations, governance frameworks, guiding principles, and national and international governance strategies for AI.This article appears in the special track on AI & Society.



機械学習(ML)と人工知能(AI)の研究者は、研究、擁護、雇用の選択などを通じて、AIの倫理とガバナンスにおいて重要な役割を果たしています。しかしながら、この影響力のあるグループの態度は十分に理解されておらず、AI/ML研究者間の合意や不一致を見極める私たちの能力を損なっています。これらの研究者の見解を調べるために、2つの主要なAI/MLカンファレンスで論文を発表した人々(N = 524)を対象に調査を実施しました。これらの結果を、2016年のAI/ML研究者調査(Graceら, 2018)および2018年の米国民調査(Zhang & Dafoe, 2020)の結果と比較しました。AI/ML研究者は、公共の利益のためにAIの開発と利用を形作る国際機関や科学組織に高いレベルの信頼を置いている一方で、ほとんどの西側諸国のハイテク企業には中程度の信頼を置いている一方で、国家軍、中国のハイテク企業、およびFacebookには低い信頼を置いていることがわかりました。回答者は、AI/ML研究者が致死性の自律型兵器に取り組むことに圧倒的に反対していましたが、AIの他の軍事用途、特に兵站アルゴリズムに取り組む研究者にはそれほど反対していませんでした。回答者の大多数は、AIの安全性研究を優先すべきであり、機械学習機関は潜在的な危害を評価するための出版前レビューを実施すべきだと考えています。AI/機械学習研究者は技術そのものに近い立場にあるため、新たなリスクを浮き彫りにし、技術的解決策を開発する上で有利な立場にあります。そのため、彼らの意識を測定するこの斬新な試みは、幅広い意義を持つものです。この調査結果は、研究者、民間企業の経営幹部、そして政策立案者が、AIに関する規制、ガバナンスの枠組み、指針、そして国内および国際的なガバナンス戦略について考える上で役立つはずです。この記事は「AIと社会」の特別トラックに掲載されています。

Improving the Effectiveness and Efficiency of Stochastic Neighbour Embedding with Isolation Kernel

Improving the Effectiveness and Efficiency of Stochastic Neighbour Embedding with Isolation Kernel / アイソレーションカーネルを用いた確率的近傍埋め込みの有効性と効率性の向上

This paper presents a new insight into improving the performance of Stochastic Neighbour Embedding (t-SNE) by using Isolation kernel instead of Gaussian kernel. Isolation kernel outperforms Gaussian kernel in two aspects. First, the use of Isolation kernel in t-SNE overcomes the drawback of misrepresenting some structures in the data, which often occurs when Gaussian kernel is applied in t-SNE. This is because Gaussian kernel determines each local bandwidth based on one local point only, while Isolation kernel is derived directly from the data based on space partitioning. Second, the use of Isolation kernel yields a more efficient similarity computation because data-dependent Isolation kernel has only one parameter that needs to be tuned. In contrast, the use of data-independent Gaussian kernel increases the computational cost by determining n bandwidths for a dataset of n points. As the root cause of these deficiencies in t-SNE is Gaussian kernel, we show that simply replacing Gaussian kernel with Isolation kernel in t-SNE significantly improves the quality of the final visualisation output (without creating misrepresented structures) and removes one key obstacle that prevents t-SNE from processing large datasets. Moreover, Isolation kernel enables t-SNE to deal with large-scale datasets in less runtime without trading off accuracy, unlike existing methods in speeding up t-SNE.



この論文では、ガウスカーネルの代わりに分離カーネルを使用することで確率的近傍埋め込み(t-SNE)のパフォーマンスを向上させるための新しい知見を紹介します。分離カーネルは、2つの点でガウスカーネルよりも優れています。第1に、t-SNEで分離カーネルを使用すると、ガウスカーネルをt-SNEに適用した場合によく発生する、データ内の一部の構造を誤って表現するという欠点が克服されます。これは、ガウスカーネルが1つのローカル ポイントのみに基づいて各ローカル バンド幅を決定するのに対し、分離カーネルは空間分割に基づいてデータから直接導出されるためです。第2に、データ依存の分離カーネルでは調整が必要なパラメーターが1つだけなので、分離カーネルを使用すると、より効率的な類似度計算が可能になります。対照的に、データに依存しないガウスカーネルを使用すると、n個のポイントのデータセットに対してn個のバンド幅を決定することになり、計算コストが増加します。t-SNEにおけるこれらの欠陥の根本原因はガウスカーネルであるため、t-SNEでガウスカーネルをアイソレーションカーネルに置き換えるだけで、最終的な視覚化出力の品質が大幅に向上し(誤った構造を作成することなく)、t-SNEが大規模なデータセットを処理することを妨げる主要な障害が取り除かれることを示します。さらに、アイソレーションカーネルにより、t-SNEは、t-SNEを高速化する既存の方法とは異なり、精度を犠牲にすることなく、より短い実行時間で大規模なデータセットを処理できるようになります。

Goal Recognition for Deceptive Human Agents through Planning and Gaze

Goal Recognition for Deceptive Human Agents through Planning and Gaze / 計画と視線による欺瞞的な人間エージェントの目標認識

Eye gaze has the potential to provide insight into the minds of individuals, and this idea has been used in prior research to improve human goal recognition by combining human’s actions and gaze. However, most existing research assumes that people are rational and honest. In adversarial scenarios, people may deliberately alter their actions and gaze, which presents a challenge to goal recognition systems. In this paper, we present new models for goal recognition under deception using a combination of gaze behaviour and observed movements of the agent. These models aim to detect when a person is deceiving by analysing their gaze patterns and use this information to adjust the goal recognition. We evaluated our models in two human-subject studies: (1) using data collected from 30 individuals playing a navigation game inspired by an existing deception study and (2) using data collected from 40 individuals playing a competitive game (Ticket To Ride). We found that one of our models (Modulated Deception Gaze+Ontic) offers promising results compared to the previous state-of-the-art model in both studies. Our work complements existing adversarial goal recognition systems by equipping these systems with the ability to tackle ambiguous gaze behaviours.



視線は個人の心への洞察を提供する可能性があり、このアイデアは、人間の行動と視線を組み合わせることで人間の目標認識を向上させる先行研究で使用されてきました。しかし、既存の研究のほとんどは、人間が合理的で誠実であると仮定しています。敵対的なシナリオでは、人々は意図的に行動や視線を変える可能性があり、これは目標認識システムにとって課題となります。本稿では、視線行動とエージェントの観測された動きを組み合わせて、欺瞞下での目標認識のための新しいモデルを提示します。これらのモデルは、視線パターンを解析することで人が欺いていることを検出し、この情報を用いて目標認識を調整することを目的としています。私たちは、2つの被験者研究でモデルを評価しました。(1)既存の欺瞞研究に着想を得たナビゲーション ゲームをプレイしている30人の被験者から収集したデータを使用する研究、および(2)競争ゲーム(Ticket To Ride)をプレイしている40人の被験者から収集したデータを使用する研究です。両方の研究において、モデルの1つ(Modulated Deception Gaze+Ontic)が、以前の最先端モデルと比較して有望な結果をもたらすことがわかりました。私たちの研究は、既存の敵対的目標認識システムに曖昧な視線行動に対処する能力を持たせることで、これらのシステムを補完します。

Dimensional Inconsistency Measures and Postulates in Spatio-Temporal Databases

Dimensional Inconsistency Measures and Postulates in Spatio-Temporal Databases / 次元時空間データベースにおける不整合尺度と公理

The problem of managing spatio-temporal data arises in many applications, such as location-based services, environmental monitoring, geographic information systems, and many others. Often spatio-temporal data arising from such applications turn out to be inconsistent, i.e., representing an impossible situation in the real world. Though several inconsistency measures have been proposed to quantify in a principled way inconsistency in propositional knowledge bases, little effort has been done so far on inconsistency measures tailored for the spatio-temporal setting.In this paper, we define and investigate new measures that are particularly suitable for dealing with inconsistent spatio-temporal information, because they explicitly take into account the spatial and temporal dimensions, as well as the dimension concerning the identifiers of the monitored objects. Specifically, we first define natural measures that look at individual dimensions (time, space, and objects), and then propose measures based on the notion of a repair. We then analyze their behavior w.r.t. common postulates defined for classical propositional knowledge bases, and find that the latter are not suitable for spatio-temporal databases, in that the proposed inconsistency measures do not often satisfy them. In light of this, we argue that also postulates should explicitly take into account the spatial, temporal, and object dimensions and thus define “dimension-aware” counterparts of common postulates, which are indeed often satisfied by the new inconsistency measures. Finally, we study the complexity of the proposed inconsistency measures.



時空間データの管理の問題は、位置情報サービス、環境モニタリング、地理情報システムなど、多くのアプリケーションで発生します。このようなアプリケーションから生じる時空間データは、矛盾していることが多く、つまり現実世界ではあり得ない状況を表していることが判明します。命題知識ベースにおける矛盾を原理的に定量化するための矛盾尺度はいくつか提案されているものの、時空間環境に適した矛盾尺度に関する研究はこれまでほとんど行われてこなかった。本稿では、空間次元と時間次元、そして監視対象オブジェクトの識別子に関する次元を明示的に考慮するため、矛盾する時空間情報の処理に特に適した新しい尺度を定義し、調査します。具体的には、まず個々の次元(時間、空間、オブジェクト)に注目する自然な尺度を定義し、次に修復の概念に基づく尺度を提案します。次に、古典的な命題知識ベースに定義されている一般的な公理に対するそれらの動作を分析し、提案されている矛盾尺度がそれらの公理を満たさないことが多いことから、これらの公理は時空間データベースには適していないことを明らかにした。これを踏まえ、我々は、公理においても空間次元、時間次元、そして物体次元を明示的に考慮し、一般的な公理の「次元を考慮した」対応関係を定義するべきだと主張します。そして、これは実際に、新しい不整合尺度によってしばしば満たされています。最後に、提案された不整合尺度の複雑性について考察します。

Merge-and-Shrink: A Compositional Theory of Transformations of Factored Transition Systems

Merge-and-Shrink: A Compositional Theory of Transformations of Factored Transition Systems / マージ・アンド・シュリンク:因子化遷移システムの変換に関する構成理論

The merge-and-shrink framework has been introduced as a general approach for defining abstractions of large state spaces arising in domain-independent planning and related areas. The distinguishing characteristic of the merge-and-shrink approach is that it operates directly on the factored representation of state spaces, repeatedly modifying this representation through transformations such as shrinking (abstracting a factor of the representation), merging (combining two factors), label reduction (abstracting the way in which different factors interact), and pruning (removing states or transitions of a factor).We provide a novel view of the merge-and-shrink framework as a “toolbox” or “algebra” of transformations on factored transition systems, with the construction of abstractions as only one possible application. For each transformation, we study desirable properties such as conservativeness (overapproximating the original transition system), inducedness (absence of spurious states and transitions), and refinability (reconstruction of paths in the original transition system from the transformed one). We provide the first complete characterizations of the conditions under which these desirable properties can be achieved. We also provide the first full formal account of factored mappings, the mechanism used within the merge-and-shrink framework to establish the relationship between states in the original and transformed factored transition system.Unlike earlier attempts to develop a theory for merge-and-shrink, our approach is fully compositional: the properties of a sequence of transformations can be entirely understood by the properties of the individual transformations involved. This aspect is key to the use of merge-and-shrink as a general toolbox for transforming factored transition systems. New transformations can easily be added to our theory, with compositionality taking care of the seamless integration with the existing components. Similarly, new properties of transformations can be integrated into the theory by showing their compositionality and studying under which conditions they are satisfied by the building blocks of merge-and-shrink.



マージ・アンド・シュリンク・フレームワークは、ドメイン非依存計画および関連分野において生じる大規模状態空間の抽象化を定義するための一般的なアプローチとして導入されました。マージ・アンド・シュリンク・アプローチの特徴は、状態空間の因子化表現に直接作用し、シュリンク(表現の因子の抽象化)、マージ(2つの因子の結合)、ラベル削減(異なる因子の相互作用の抽象化)、プルーニング(因子の状態または遷移の削除)といった変換を通して、この表現を繰り返し修正することです。我々は、マージ・アンド・シュリンク・フレームワークを、因子化遷移システムにおける変換の「ツールボックス」または「代数」として捉えるという新たな視点を提示し、抽象化の構築は、その応用例の一つに過ぎないと考える。各変換について、保守性(元の遷移システムを過剰近似する)、誘導性(不要な状態や遷移が存在しない)、精緻化可能性(変換後の遷移システムから元の遷移システムのパスを再構築する)といった望ましい特性を考察します。これらの望ましい特性が達成される条件について、初めて完全な特性評価を提供します。また、マージ・アンド・シュリンクの枠組みにおいて、元のファクター化遷移システムと変換後のファクター化遷移システムの状態間の関係を確立するメカニズムであるファクター化マッピングについて、初めて完全な形式的説明を提供します。マージ・アンド・シュリンクの理論構築におけるこれまでの試みとは異なり、私たちのアプローチは完全に構成的です。つまり、一連の変換の特性は、個々の変換の特性によって完全に理解できます。この側面は、ファクター化遷移システムを変換するための一般的なツールボックスとしてマージ・アンド・シュリンクを使用する上で重要です。新しい変換は私たちの理論に簡単に追加でき、構成性によって既存の構成要素とのシームレスな統合が実現されます。同様に、変換の新しい特性は、その構成性を示し、マージ・アンド・シュリンクの構成要素がどのような条件でそれらの特性を満たすかを調べることで、理論に統合できます。

Set-to-Sequence Methods in Machine Learning: A Review

Set-to-Sequence Methods in Machine Learning: A Review / 機械学習におけるセット・ツー・シーケンス法:レビュー

Machine learning on sets towards sequential output is an important and ubiquitous task, with applications ranging from language modelling and meta-learning to multi-agent strategy games and power grid optimization. Combining elements of representation learning and structured prediction, its two primary challenges include obtaining a meaningful, permutation invariant set representation and subsequently utilizing this representation to output a complex target permutation. This paper provides a comprehensive introduction to the field as well as an overview of important machine learning methods tackling both of these key challenges, with a detailed qualitative comparison of selected model architectures.



シーケンシャル出力に向けた集合上の機械学習は、言語モデリングやメタ学習からマルチエージェント戦略ゲームや電力網最適化まで、幅広い応用を持つ重要かつ普遍的なタスクです。表現学習と構造化予測の要素を組み合わせたこの手法の2つの主要な課題は、意味のある順列不変な集合表現を取得し、その後、この表現を用いて複雑なターゲット順列を出力することです。本論文では、この分野の包括的な紹介に加え、これらの主要な課題に取り組む重要な機械学習手法の概要と、選定されたモデルアーキテクチャの詳細な定性的な比較を提供します。

Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set

Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set / 最小連結支配集合のための動的連結性維持に基づく効率的な局所探索

The minimum connected dominating set (MCDS) problem is an important extension of the minimum dominating set problem, with wide applications, especially in wireless networks. Most previous works focused on solving MCDS problem in graphs with relatively small size, mainly due to the complexity of maintaining connectivity. This paper explores techniques for solving MCDS problem in massive real-world graphs with wide practical importance. Firstly, we propose a local greedy construction method with reasoning rule called 1hopReason. Secondly and most importantly, a hybrid dynamic connectivity maintenance method (HDC+) is designed to switch alternately between a novel fast connectivity maintenance method based on spanning tree and its previous counterpart. Thirdly, we adopt a two-level vertex selection heuristic with a newly proposed scoring function called chronosafety to make the algorithm more considerate when selecting vertices. We design a new local search algorithm called FastCDS based on the three ideas. Experiments show that FastCDS significantly outperforms five state-of-the-art MCDS algorithms on both massive graphs and classic benchmarks.



最小連結支配集合(MCDS)問題は、特にワイヤレス ネットワークで幅広い用途を持つ、最小支配集合問題の重要な拡張です。これまでのほとんどの研究は、主に連結性の維持の複雑さから、比較的小さなサイズのグラフにおけるMCDS問題を解決することに焦点を当てていました。この論文では、実用上幅広い重要性を持つ、現実世界の大規模なグラフにおけるMCDS問題を解決するための手法を探ります。まず、1hopReasonと呼ばれる推論規則を使用したローカル貪欲構築法を提案します。次に、そして最も重要な点として、ハイブリッド動的連結性維持法(HDC+)は、スパニング ツリーに基づく新しい高速連結性維持法と以前の方法とを交互に切り替えるように設計されます。最後に、アルゴリズムがより慎重に頂点を選択するように、新しく提案されたchronosafetyと呼ばれるスコアリング関数を備えた2レベルの頂点選択ヒューリスティックを採用します。実験により、FastCDSは、大規模なグラフと従来のベンチマークの両方において、最先端の5つのMCDSアルゴリズムを大幅に上回るパフォーマンスを発揮することが示されました。

Evaluating Strategic Structures in Multi-Agent Inverse Reinforcement Learning

Evaluating Strategic Structures in Multi-Agent Inverse Reinforcement Learning / マルチエージェント逆強化学習における戦略構造の評価

A core question in multi-agent systems is understanding the motivations for an agent’s actions based on their behavior. Inverse reinforcement learning provides a framework for extracting utility functions from observed agent behavior, casting the problem as finding domain parameters which induce such a behavior from rational decision makers.  We show how to efficiently and scalably extend inverse reinforcement learning to multi-agent settings, by reducing the multi-agent problem to N single-agent problems while still satisfying rationality conditions such as strong rationality. However, we observe that rewards learned naively tend to lack insightful structure, which causes them to produce undesirable behavior when optimized in games with different players from those encountered during training. We further investigate conditions under which rewards or utility functions can be precisely identified, on problem domains such as normal-form and Markov games, as well as auctions, where we show we can learn reward functions that properly generalize to new settings.



マルチエージェントシステムにおける中心的な問題は、エージェントの行動に基づいてその行動の動機を理解することです。逆強化学習は、観測されたエージェントの行動から効用関数を抽出するためのフレームワークを提供し、問題を、合理的な意思決定者からそのような行動を誘発するドメインパラメータを見つけることと定義します。本研究では、強い合理性などの合理性条件を満たしながら、マルチエージェント問題をN個のシングルエージェント問題に簡約することで、逆強化学習をマルチエージェント設定に効率的かつスケーラブルに拡張する方法を示します。しかし、単純に学習された報酬は洞察に富んだ構造を欠く傾向があり、トレーニング中に遭遇したプレイヤーとは異なるプレイヤーとのゲームで最適化すると、望ましくない行動が生じることがわかります。さらに、正規形ゲームやマルコフゲーム、オークションなどの問題領域において、報酬または効用関数を正確に識別できる条件を調査し、新しい設定に適切に一般化される報酬関数を学習できることを示します。

Agent-Based Markov Modeling for Improved COVID-19 Mitigation Policies

Agent-Based Markov Modeling for Improved COVID-19 Mitigation Policies / COVID-19対策の改善のためのエージェントベース・マルコフモデリング

The year 2020 saw the covid-19 virus lead to one of the worst global pandemics in history. As a result, governments around the world have been faced with the challenge of protecting public health while keeping the economy running to the greatest extent possible. Epidemiological models provide insight into the spread of these types of diseases and predict the effects of possible intervention policies. However, to date, even the most data-driven intervention policies rely on heuristics. In this paper, we study how reinforcement learning (RL) and Bayesian inference can be used to optimize mitigation policies that minimize economic impact without overwhelming hospital capacity. Our main contributions are (1) a novel agent-based pandemic simulator which, unlike traditional models, is able to model fine-grained interactions among people at specific locations in a community; (2) an RLbased methodology for optimizing fine-grained mitigation policies within this simulator; and (3) a Hidden Markov Model for predicting infected individuals based on partial observations regarding test results, presence of symptoms, and past physical contacts.This article is part of the special track on AI and COVID-19.



2020年は、新型コロナウイルス感染症(COVID-19)が史上最悪の世界的パンデミックの1つを引き起こした年でした。その結果、世界各国の政府は、公衆衛生を守りつつ経済活動を最大限に維持するという課題に直面しています。疫学モデルは、これらの種類の疾患の蔓延に関する知見を提供し、可能な介入政策の効果を予測します。しかしながら、現在までに最もデータ主導型の介入政策でさえ、ヒューリスティックスに依存しています。本稿では、強化学習(RL)とベイズ推論を用いて、病院の収容能力を圧迫することなく経済的影響を最小限に抑える緩和政策を最適化する方法を検討します。私たちの主な貢献は、(1)従来のモデルとは異なり、コミュニティ内の特定の場所にいる人々のきめ細かい相互作用をモデル化できる、新しいエージェントベースのパンデミックシミュレーター、(2)このシミュレーター内できめ細かい緩和政策を最適化するためのRLベースの方法論、(3)検査結果、症状の有無、過去の身体的接触に関する部分的な観察に基づいて感染者を予測するための隠れマルコフモデルです。本稿は、AIとCOVID-19に関する特別トラックの一部です。

Bribery and Control in Stable Marriage

Bribery and Control in Stable Marriage / 安定した結婚における賄賂と支配

We initiate the study of external manipulations in Stable Marriage by considering  several manipulative actions as well as several manipulation goals. For instance, one goal  is to make sure that a given pair of agents is matched in a stable solution, and this may be  achieved by the manipulative action of reordering some agents’ preference lists. We present  a comprehensive study of the computational complexity of all problems arising in this way.  We find several polynomial-time solvable cases as well as NP-hard ones. For the NP-hard  cases, focusing on the natural parameter “budget” (that is, the number of manipulative  actions one is allowed to perform), we also conduct a parameterized complexity analysis  and encounter mostly parameterized hardness results.



我々は、安定結婚における外部操作の研究を、いくつかの操作行動といくつかの操作目標を考慮することから始める。例えば、1つの目標は、与えられたエージェントのペアが安定した解でマッチングされるようにすることであり、これは、一部のエージェントの好みのリストを並べ替える操作行動によって達成されるかもしれない。我々は、このようにして生じるすべての問題の計算複雑性に関する包括的な研究を提示します。我々は、NP困難なケースだけでなく、多項式時間で解けるケースもいくつか見つけた。NP困難なケースについては、自然なパラメータ「予算」(つまり、実行できる操作行動の数)に焦点を当て、パラメータ化された複雑性分析も行い、ほとんどがパラメータ化された困難性の結果が得られた。

参考文献

関連情報