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

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

論文

Solving the Torpedo Scheduling Problem

Solving the Torpedo Scheduling Problem / 魚雷スケジューリング問題の解決

The article presents a solution approach for the Torpedo Scheduling Problem, an operational planning problem found in steel production. The problem consists of the integrated scheduling and routing of torpedo cars, i. e. steel transporting vehicles, from a blast furnace to steel converters. In the continuous metallurgic transformation of iron into steel, the discrete transportation step of molten iron must be planned with considerable care in order to ensure a continuous material flow.The problem is solved by a Simulated Annealing algorithm, coupled with an approach of reducing the set of feasible material assignments. The latter is based on logical reductions and lower bound calculations on the number of torpedo cars.Experimental investigations are performed on a larger number of problem instances, which stem from the 2016 implementation challenge of the Association of Constraint Programming (ACP). Our approach was ranked first (joint first place) in the 2016 ACP challenge and found optimal solutions for all used instances in this challenge.



本稿では、鉄鋼生産における運用計画問題であるトルピードスケジューリング問題に対する解法を提示します。この問題は、高炉から転炉までの鋼材輸送車両であるトルピードカーの統合スケジューリングと経路決定から構成されます。鉄から鋼材への連続冶金変換において、連続的な材料フローを確保するために、溶融鉄の個別輸送ステップは細心の注意を払って計画されなければならない。この問題は、シミュレーテッドアニーリングアルゴリズムと、実行可能な材料割り当てセットを削減する手法を組み合わせることで解決されます。後者は、論理的削減とトルピードカー数の下限計算に基づく。実験的調査は、制約プログラミング協会（ACP）の2016年実装チャレンジから派生した、より多数の問題インスタンスに対して実施されます。我々のアプローチは、2016年のACPチャレンジで1位（共同1位）にランクされ、このチャレンジで使用されたすべてのインスタンスに対して最適解が見出されました。

Strategic Abstention based on Preference Extensions: Positive Results and Computer-Generated Impossibilities

Strategic Abstention based on Preference Extensions: Positive Results and Computer-Generated Impossibilities / 選好拡張に基づく戦略的棄権：肯定的な結果とコンピュータ生成不可能性

Voting rules allow multiple agents to aggregate their preferences in order to reach joint decisions. A common flaw of some voting rules, known as the no-show paradox, is that agents may obtain a more preferred outcome by abstaining from an election. We study strategic abstention for set-valued voting rules based on Kelly’s and Fishburn’s preference extensions. Our contribution is twofold. First, we show that, whenever there are at least five alternatives and seven agents, every Pareto-optimal majoritarian voting rule suffers from the no-show paradox with respect to Fishburn’s extension. This is achieved by reducing the statement to a finite – yet very large – problem, which is encoded as a formula in propositional logic and then shown to be unsatisfiable by a SAT solver. We also provide a human-readable proof which we extracted from a minimal unsatisfiable core of the formula. Secondly, we prove that every voting rule that satisfies two natural conditions cannot be manipulated by strategic abstention with respect to Kelly’s extension and give examples of well-known Pareto-optimal majoritarian voting rules that meet these requirements.



投票ルールは、複数のエージェントが共同で決定を下すために自分の好みを集約することを可能にします。一部の投票ルールに共通する欠陥は、ノーショー パラドックスとして知られており、エージェントが選挙を棄権することでより好ましい結果を得られる可能性があることです。私たちは、ケリーとフィッシュバーンの選好拡張に基づいて、集合値投票ルールの戦略的棄権を研究します。私たちの貢献は2つあります。まず、少なくとも5つの選択肢と7人のエージェントがいる場合はいつでも、すべてのパレート最適な多数決投票ルールがフィッシュバーンの拡張に関してノーショー パラドックスの影響を受けることを示します。これは、ステートメントを有限でありながら非常に大きな問題に縮小することによって実現され、これは命題論理の式としてエンコードされ、SATソルバーによって充足不可能であることが示されます。また、式の最小の充足不可能なコアから抽出した、人間が読める形式の証明も提供します。第二に、2つの自然条件を満たすすべての投票ルールは、ケリーの拡張に関して戦略的棄権によって操作できないことを証明し、これらの要件を満たすよく知られたパレート最適な多数決投票ルールの例を示します。

Approximating Weighted and Priced Bribery in Scoring Rules

Approximating Weighted and Priced Bribery in Scoring Rules / スコアリングルールにおける加重および価格付き賄賂の近似

The classic Bribery problem is to find a minimal subset of voters who need to change their vote to make some preferred candidate win. Its important generalizations consider voters who are weighted and also have different prices. We provide an approximate solution for these problems for a broad family of scoring rules (which includes Borda, t-approval, and Dowdall).Our algorithm is based on a randomized reduction from these Bribery generalizations to weighted coalitional manipulation (WCM). To solve this WCM instance, we apply the Birkhoff-von Neumann (BvN) decomposition to a fractional manipulation matrix. This allows us to limit the size of the possible ballot search space reducing it from exponential to polynomial, while still obtaining good approximation guarantees. Finding a solution in the truncated search space yields a new algorithm for WCM, which is of independent interest.



古典的な賄賂問題は、ある候補者を勝利させるために投票を変更する必要がある有権者の最小のサブセットを見つけることです。その重要な一般化は、重み付けされ、かつ異なる価格を持つ有権者を考慮します。私たちは、幅広いスコアリングルール群（ボルダ、t承認、ダウダルを含む）に対して、これらの問題の近似解を提供します。私たちのアルゴリズムは、これらの賄賂の一般化から重み付き連合操作（WCM）へのランダム縮約に基づいています。このWCMの例を解決するために、バーコフ-フォン・ノイマン（BvN）分解を分数操作行列に適用します。これにより、可能な投票検索空間のサイズを制限し、良好な近似保証を維持しながら、指数関数から多項式へと縮小することができます。切り捨てられた検索空間で解決策を見つけると、WCMの新しいアルゴリズムが生成され、これは独立した関心事となります。

If Nothing Is Accepted — Repairing Argumentation Frameworks

If Nothing Is Accepted — Repairing Argumentation Frameworks / 何も受け入れられない場合 ― 議論フレームワークの修復

Conflicting information in an agent’s knowledge base may lead to a semantical defect, that is, a situation where it is impossible to draw any plausible conclusion. Finding out the reasons for the observed inconsistency (so-called diagnoses) and/or restoring consistency in a certain minimal way (so-called repairs) are frequently occurring issues in knowledge representation and reasoning. In this article we provide a series of first results for these problems in the context of abstract argumentation theory regarding the two most important reasoning modes, namely credulous as well as sceptical acceptance. Our analysis includes the following problems regarding minimal repairs/diagnoses: existence, verification, computation of one and enumeration of all solutions. The latter problem is tackled with a version of the so-called hitting set duality first introduced by Raymond Reiter in 1987. It turns out that grounded semantics plays an outstanding role not only in terms of complexity, but also as a useful tool to reduce the search space for diagnoses regarding other semantics.



エージェントの知識ベースにおける矛盾した情報は、意味論的な欠陥、すなわち妥当な結論を導き出すことが不可能な状況につながる可能性があります。観察された不整合の理由を明らかにすること（いわゆる診断）、および／または最小限の方法で整合性を回復すること（いわゆる修復）は、知識表現と推論において頻繁に発生する問題です。本稿では、これらの問題に対する一連の最初の成果を、抽象的議論理論の文脈において、最も重要な2つの推論モード、すなわち信憑性受容と懐疑的受容に関して提示します。本稿の分析には、最小限の修復／診断に関する以下の問題が含まれます：存在、検証、1つの解の計算、およびすべての解の列挙。最後の問題は、1987年にレイモンド・ライターによって初めて導入された、いわゆるヒッティングセット双対性の一種を用いて対処します。グラウンデッド・セマンティクスは、複雑さの観点だけでなく、他のセマンティクスに関する診断の探索空間を縮小するための有用なツールとしても、優れた役割を果たすことが示されました。

Preference Orders on Families of Sets – When Can Impossibility Results Be Avoided?

Preference Orders on Families of Sets – When Can Impossibility Results Be Avoided? / 集合族における優先順位 ― 不可能性結果はいつ回避できるか？

Lifting a preference order on elements of some universe to a preference order on subsets of this universe is often guided by postulated properties the lifted order should have. Well-known impossibility results pose severe limits on when such liftings exist if all non-empty subsets of the universe are to be ordered. The extent to which these negative results carry over to other families of sets is not known. In this paper, we consider families of sets that induce connected subgraphs in graphs. For such families, common in applications, we study whether lifted orders satisfying the well-studied axioms of dominance and (strict) independence exist for every or, in another setting, for some underlying order on elements (strong and weak orderability). We characterize families that are strongly and weakly orderable under dominance and strict independence, and obtain a tight bound on the class of families that are strongly orderable under dominance and independence.



ある宇宙の元に対する優先順序を、その宇宙の部分集合に対する優先順序に持ち上げることは、持ち上げられた順序が持つべき仮定された性質によって導かれることが多い。よく知られている不可能性結果は、宇宙のすべての空でない部分集合を順序付けする場合、そのような持ち上げが存在する場合に厳しい制限を課す。これらの否定的な結果が他の集合族にどの程度まで当てはまるかは分かっていない。本稿では、グラフに連結部分グラフを誘導する集合族について考察します。応用分野では一般的なこのような族について、よく研究されている支配公理と（厳密な）独立公理を満たす持ち上げられた順序が、すべての要素、あるいは別の設定では要素の何らかの根底にある順序（強い順序可能性と弱い順序可能性）に対して存在するかどうかを調査します。支配と厳密な独立性の下で強く順序付け可能な族と弱く順序付け可能な族を特徴付け、支配と独立性の下で強く順序付け可能な族のクラスの厳密な境界を得る。

From Support Propagation to Belief Propagation in Constraint Programming

From Support Propagation to Belief Propagation in Constraint Programming / 制約プログラミングにおける支持伝播から確信伝播へ

The distinctive driving force of constraint programming to solve combinatorial problems has been a privileged access to problem structure through the high-level models it uses. From that exposed structure in the form of so-called global constraints, powerful inference algorithms have shared information between constraints by propagating it through shared variables’ domains, traditionally by removing unsupported values. This paper investigates a richer propagation medium made possible by recent work on counting solutions inside constraints. Beliefs about individual variable-value assignments are exchanged between contraints and iteratively adjusted. It generalizes standard support propagation and aims to converge to the true marginal distributions of the solutions over individual variables. Its advantage over standard belief propagation is that the higher-level models featuring large-arity (global) constraints do not tend to create as many cycles, which are known to be problematic for convergence. The necessary architectural changes to a constraint programming solver are described and an empirical study of the proposal is conducted on its implementation. We find that it provides close approximations to the true marginals and that it significantly improves search guidance.



組合せ問題を解く制約プログラミングの際立った原動力は、それが使用する高水準モデルを通して問題構造への特権的なアクセスであった。いわゆるグローバル制約の形で公開された構造から、強力な推論アルゴリズムは、従来はサポートされていない値を削除することで、共有変数のドメインを通じて情報を伝播することで、制約間で情報を共有してきました。本論文では、制約内の解を数える最近の研究によって可能になった、より豊富な伝播媒体について考察します。個々の変数値の割り当てに関する信念は、制約間で交換され、反復的に調整されます。これは標準的なサポート伝播を一般化し、個々の変数に対する解の真の周辺分布への収束を目指します。標準的な信念伝播に対する利点は、大規模（グローバル）制約を特徴とする高水準モデルが、収束に問題となることが知られているサイクルをそれほど多く生成しない傾向があることです。制約プログラミングソルバーに必要なアーキテクチャの変更について説明し、提案の実装に関する実証的研究を実施しました。その結果、真の周辺分布に近い近似値が得られ、探索ガイダンスが大幅に改善されることが分かりました。

Multi-fidelity Gaussian Process Bandit Optimisation

Multi-fidelity Gaussian Process Bandit Optimisation / マルチフィデリティガウス過程バンディット最適化

In many scientific and engineering applications, we are tasked with the maximisation of an expensive to evaluate black box function f. Traditional settings for this problem assume just the availability of this single function. However, in many cases, cheap approximations to f may be obtainable. For example, the expensive real world behaviour of a robot can be approximated by a cheap computer simulation. We can use these approximations to eliminate low function value regions cheaply and use the expensive evaluations of f in a small but promising region and speedily identify the optimum. We formalise this task as a multi-fidelity bandit problem where the target function and its approximations are sampled from a Gaussian process. We develop MF-GP-UCB, a novel method based on upper confidence bound techniques. In our theoretical analysis we demonstrate that it exhibits precisely the above behaviour and achieves better bounds on the regret than strategies which ignore multi-fidelity information. Empirically, MF-GP-UCB outperforms such naive strategies and other multi-fidelity methods on several synthetic and real experiments.



多くの科学技術アプリケーションにおいて、評価にコストがかかるブラックボックス関数fの最大化が課題となります。この問題に対する従来の設定では、この単一の関数のみが利用可能であると想定されていました。しかし、多くの場合、fの安価な近似値が得られる可能性があります。例えば、ロボットの実世界での高価な動作は、安価なコンピュータシミュレーションで近似できます。これらの近似値を用いることで、関数値の低い領域を安価に排除し、小さいながらも有望な領域におけるfの高価な評価を用いて、最適値を迅速に特定することができます。私たちはこの課題を、目的関数とその近似値がガウス過程からサンプリングされるマルチフィデリティバンディット問題として定式化します。私たちは、上側信頼限界法に基づく新しい手法であるMF-GP-UCBを開発しました。理論分析では、この手法がまさに上記の動作を示し、マルチフィデリティ情報を無視する戦略よりも優れたリグレットの境界値を達成することを実証しました。経験的に、MF-GP-UCBは、いくつかの合成実験および実際の実験において、このような単純な戦略やその他のマルチフィデリティ手法よりも優れたパフォーマンスを発揮します。

Timed ATL: Forget Memory, Just Count

Timed ATL: Forget Memory, Just Count / 時間制限付きATL：記憶は忘れて、数えるだけ

In this paper we investigate the Timed Alternating-Time Temporal Logic (TATL), a discrete-time extension of ATL. In particular, we propose, systematize, and further study semantic variants of TATL, based on different notions of a strategy. The notions are derived from different assumptions about the agents’ memory and observational capabilities, and range from timed perfect recall to untimed memoryless plans. We also introduce a new semantics based on counting the number of visits to locations during the play. We show that all the semantics, except for the untimed memoryless one, are equivalent when punctuality constraints are not allowed in the formulae. In fact, abilities in all those notions of a strategy collapse to the “counting” semantics with only two actions allowed per location. On the other hand, this simple pattern does not extend to the full TATL.As a consequence, we establish a hierarchy of TATL semantics, based on the expressivity of the underlying strategies, and we show when some of the semantics coincide. In particular, we prove that more compact representations are possible for a reasonable subset of TATL specifications, which should improve the efficiency of model checking and strategy synthesis.



本稿では、ATLの離散時間拡張であるTimed Alternating-Time Temporal Logic (TATL)を考察します。特に、異なる戦略概念に基づくTATLの意味論的変種を提案、体系化し、さらに研究します。これらの概念は、エージェントの記憶と観察能力に関する異なる仮定から導かれ、時間制限のある完全な想起から時間制限のない記憶のない計画まで多岐にわたる。また、プレイ中に場所を訪れた回数を数えることに基づく新しい意味論も導入します。時間制限のない記憶のない意味論を除くすべての意味論は、定式において時間厳守の制約が認められない場合、等価であることを示す。実際、これらの戦略概念における能力はすべて、場所ごとに2つの行動のみが認められる「カウント」意味論に集約されます。一方、この単純なパターンは完全なTATLには適用されません。結果として、基礎となる戦略の表現力に基づいてTATL意味論の階層を確立し、意味論の一部が一致する場合を示します。特に、TATL仕様の妥当なサブセットに対しては、よりコンパクトな表現が可能であり、モデル検査と戦略合成の効率が向上することを証明します。

Context Vectors are Reflections of Word Vectors in Half the Dimensions

Context Vectors are Reflections of Word Vectors in Half the Dimensions / コンテキストベクトルは、単語ベクトルの半分の次元における反射です。

This paper takes a step towards theoretical analysis of the relationship between word embeddings and context embeddings in models such as word2vec. We start from basic probabilistic assumptions on the nature of word vectors, context vectors, and text generation. These assumptions are supported either empirically or theoretically by the existing literature. Next, we show that under these assumptions the widely-used word-word PMI matrix is approximately a random symmetric Gaussian ensemble. This, in turn, implies that context vectors are reflections of word vectors in approximately half the dimensions. As a direct application of our result, we suggest a theoretically grounded way of tying weights in the SGNS model.



本論文は、word2vecなどのモデルにおける単語埋め込みとコンテキスト埋め込みの関係の理論的分析に向けて一歩踏み出します。単語ベクトル、コンテキストベクトル、およびテキスト生成の性質に関する基本的な確率的仮定から始めます。これらの仮定は、既存の文献によって経験的または理論的に裏付けられています。次に、これらの仮定の下で、広く使用されている単語間PMI行列が近似的にランダム対称ガウスアンサンブルであることを示します。これは、コンテキストベクトルが単語ベクトルの約半分の次元での反射であることを意味します。私たちの研究結果を直接応用して、SGNSモデルで重みを結び付ける理論的根拠のある方法を提案します。

What is this Article about? Extreme Summarization with Topic-aware Convolutional Neural Networks

What is this Article about? Extreme Summarization with Topic-aware Convolutional Neural Networks / この記事の内容は何ですか？トピック認識畳み込みニューラルネットワークによる極限要約

We introduce “extreme summarization,” a new single-document summarization task which aims at creating a short, one-sentence news summary answering the question “What is the article about?”. We argue that extreme summarization, by nature, is not amenable to extractive strategies and requires an abstractive modeling approach. In the hope of driving research on this task further: (a) we collect a real-world, large scale dataset by harvesting online articles from the British Broadcasting Corporation (BBC); and (b) propose a novel abstractive model which is conditioned on the article’s topics and based entirely on convolutional neural networks. We demonstrate experimentally that this architecture captures long-range dependencies in a document and recognizes pertinent content, outperforming an oracle extractive system and state-of-the-art abstractive approaches when evaluated automatically and by humans on the extreme summarization dataset.



我々は「エクストリーム要約」という新しい単一文書要約タスクを紹介します。これは、「この記事の内容は何ですか？」という質問に答える、短い一文のニュース要約を作成することを目的とします。我々は、エクストリーム要約は、本質的に、抽出戦略に馴染みがなく、抽象的なモデリングアプローチを必要とすると主張します。このタスクの研究をさらに推進することを期待して、（a）英国放送協会（BBC）からオンライン記事を収集することにより、現実世界の大規模データセットを収集し、（b）記事のトピックを条件とし、完全に畳み込みニューラルネットワークに基づいた新しい抽象モデルを提案します。我々は、このアーキテクチャが文書内の長距離依存関係を捕捉し、関連コンテンツを認識し、エクストリーム要約データセットで自動および人間によって評価された場合に、オラクル抽出システムおよび最先端の抽象化アプローチよりも優れていることを実験的に実証します。

Formulas Free From Inconsistency: An Atom-Centric Characterization in Priest’s Minimally Inconsistent LP

Formulas Free From Inconsistency: An Atom-Centric Characterization in Priest’s Minimally Inconsistent LP / 矛盾のない数式：Priestの最小矛盾LPにおける原子中心の特性評価

As one of fundamental properties to characterize inconsistency measures for knowledge bases, the property of free formula independence well captures the intuition that free formulas are independent of the amount of inconsistency in a knowledge base for cases where inconsistency is characterized in terms of minimal inconsistent subsets. But it has been argued that not all the free formulas are independent of inconsistency in some other contexts of inconsistency characterization. In this paper, we propose a characterization of formulas independent of inconsistency in the framework of Priest’s minimally inconsistent LP. Based on an atom-based counterpart of the notion of free formula, we propose a notion of Bi-free formula to describe formulas that are free from inconsistency in both syntax and paraconsistent models in this logic. Then we propose the property of Bi-free formula independence, which is more suitable for characterizing the role of formulas free from inconsistency in measuring inconsistency from both syntactic and semantic perspectives.



知識ベースの矛盾尺度を特徴付ける基本的性質の1つである自由論理式独立性は、矛盾が最小矛盾部分集合の観点から特徴付けられる場合、知識ベース内の矛盾の量とは自由論理式が独立であるという直感をよく表しています。しかし、矛盾の特徴付けの他の文脈では、すべての自由論理式が矛盾から独立しているわけではないと主張されてきました。本稿では、Priestの最小矛盾LPのフレームワークで矛盾から独立した論理式の特徴付けを提案します。自由論理式の概念の原子ベース版に基づいて、この論理の統語モデルと矛盾許容モデルの両方で矛盾のない論理式を記述するために、Bi自由論理式の概念を提案します。次に、統語論的および意味論的観点から矛盾を測定する際に矛盾のない論理式の役割を特徴付けるのにより適した、Bi自由論理式独立性の性質を提案します。

Type-aware Convolutional Neural Networks for Slot Filling

Type-aware Convolutional Neural Networks for Slot Filling / スロットフィリングのための型認識畳み込みニューラルネットワーク

The slot filling task aims at extracting answers for queries about entities from text, such as “Who founded Apple”. In this paper, we focus on the relation classification component of a slot filling system. We propose type-aware convolutional neural networks to benefit from the mutual dependencies between entity and relation classification. In particular, we explore different ways of integrating the named entity types of the relation arguments into a neural network for relation classification, including a joint training and a structured prediction approach. To the best of our knowledge, this is the first study on type-aware neural networks for slot filling. The type-aware models lead to the best results of our slot filling pipeline. Joint training performs comparable to structured prediction. To understand the impact of the different components of the slot filling pipeline, we perform a recall analysis, a manual error analysis and several ablation studies. Such analyses are of particular importance to other slot filling researchers since the official slot filling evaluations only assess pipeline outputs. The analyses show that especially coreference resolution and our convolutional neural networks have a large positive impact on the final performance of the slot filling pipeline. The presented models, the source code of our system as well as our coreference resource is publicly available.



スロットフィリングタスクは、「Appleの創設者は誰か」といったテキストからエンティティに関するクエリへの回答を抽出することを目的としています。本論文では、スロットフィリングシステムの関係分類コンポーネントに焦点を当てます。エンティティと関係分類の相互依存関係を活用するために、型を考慮した畳み込みニューラルネットワークを提案します。特に、関係引数の固有表現型を関係分類用ニューラルネットワークに統合する様々な方法、例えば共同学習と構造化予測アプローチについて検討します。我々の知る限り、これはスロットフィリングのための型を考慮したニューラルネットワークに関する初の研究です。型を考慮したモデルは、我々のスロットフィリングパイプラインにおいて最良の結果をもたらします。共同学習は構造化予測と同等の性能を発揮します。スロットフィリングパイプラインの様々なコンポーネントの影響を理解するために、再現率分析、手動エラー分析、そして複数のアブレーション研究を実施しました。公式のスロットフィリング評価はパイプラインの出力のみを評価するため、これらの分析は他のスロットフィリング研究者にとって特に重要です。分析の結果、特に共参照解決と畳み込みニューラルネットワークが、スロットフィリングパイプラインの最終的なパフォーマンスに大きなプラスの影響を与えることが示されました。提示されたモデル、システムのソースコード、および共参照リソースは公開されています。

Xeggora: Exploiting Immune-to-Evidence Symmetries with Full Aggregation in Statistical Relational Models

Xeggora: Exploiting Immune-to-Evidence Symmetries with Full Aggregation in Statistical Relational Models / Xeggora：統計的関係モデルにおける完全集約を用いた証拠免疫対称性の活用

We present improvements in maximum a-posteriori inference for Markov Logic, a widely used SRL formalism. Inferring the most probable world for Markov Logic is NP-hard in general. Several approaches, including Cutting Plane Aggregation (CPA), perform inference through translation to Integer Linear Programs. Aggregation exploits context-specific symmetries independently of evidence and reduces the size of the program. We illustrate much more symmetries occurring in long ground clauses that are ignored by CPA and can be exploited by higher-order aggregations. We propose Full-Constraint-Aggregation, a superior algorithm to CPA which exploits the ignored symmetries via a lifted translation method and some constraint relaxations. RDBMS and heuristic techniques are involved to improve the overall performance. We introduce Xeggora as an evolutionary extension of RockIt, the query engine that uses CPA. Xeggora evaluation on real-world benchmarks shows progress in efficiency compared to RockIt especially for models with long formulas.



広く使用されているSRL形式であるマルコフ論理の最大事後推論の改良点を紹介します。マルコフ論理の最尤世界を推論することは、一般的にNP困難です。Cutting Plane Aggregation (CPA)を含むいくつかのアプローチは、整数線形計画への変換を通じて推論を実行します。集約は、証拠とは独立してコンテキスト固有の対称性を利用し、プログラムのサイズを縮小します。CPAでは無視され、高階集約で利用できる長い基底節で発生するより多くの対称性を示します。私たちは、リフトされた変換法といくつかの制約緩和を介して無視される対称性を利用する、CPAよりも優れたアルゴリズムであるFull-Constraint-Aggregationを提案します。全体的なパフォーマンスを向上させるために、RDBMSとヒューリスティック手法が活用されています。CPAを使用するクエリエンジンであるRockItの進化型拡張として、Xeggoraを紹介します。実環境ベンチマークにおけるXeggoraの評価では、特に長い数式を持つモデルにおいて、RockItと比較して効率性が向上していることが示されています。

A Survey on Temporal Reasoning for Temporal Information Extraction from Text

A Survey on Temporal Reasoning for Temporal Information Extraction from Text / テキストからの時系列情報抽出のための時系列推論に関するサーベイ

Time is deeply woven into how people perceive, and communicate about the world. Almost unconsciously, we provide our language utterances with temporal cues, like verb tenses, and we can hardly produce sentences without such cues. Extracting temporal cues from text, and constructing a global temporal view about the order of described events is a major challenge of automatic natural language understanding. Temporal reasoning, the process of combining different temporal cues into a coherent temporal view, plays a central role in temporal information extraction. This article presents a comprehensive survey of the research from the past decades on temporal reasoning for automatic temporal information extraction from text, providing a case study on how combining symbolic reasoning with machine learning-based information extraction systems can improve performance. It gives a clear overview of the used methodologies for temporal reasoning, and explains how temporal reasoning can be, and has been successfully integrated into temporal information extraction systems. Based on the distillation of existing work, this survey also suggests currently unexplored research areas. We argue that the level of temporal reasoning that current systems use is still incomplete for the full task of temporal information extraction, and that a deeper understanding of how the various types of temporal information can be integrated into temporal reasoning is required to drive future research in this area.



時間は、人々が世界を認識し、コミュニケーションする方法に深く織り込まれています。私たちはほとんど無意識のうちに、動詞の時制のような時間的な手がかりを言語発話に提供しており、そのような手がかりなしに文章を作成することはほとんどできません。テキストから時間的な手がかりを抽出し、記述されているイベントの順序に関する全体的な時間的ビューを構築することは、自動自然言語理解の主要な課題です。異なる時間的な手がかりを首尾一貫した時間的ビューに組み合わせるプロセスである時間的推論は、時間情報抽出において中心的な役割を果たします。この記事では、テキストからの自動時間情報抽出のための時間的推論に関する過去数十年の研究の包括的な調査を示し、記号的推論と機械学習ベースの情報抽出システムを組み合わせることでパフォーマンスを向上させることができる方法に関するケーススタディを示します。時間的推論に使用される方法論の明確な概要を示し、時間的推論をどのように時間情報抽出システムに統合できるか、そして実際に統合されてきたかを説明します。既存の研究成果を精査した上で、本調査では、現在未開拓の研究分野も示唆しています。現在のシステムが用いる時間的推論のレベルは、時間情報抽出という完全なタスクを実行するには依然として不完全であり、この分野における将来の研究を推進するには、様々な種類の時間情報を時間的推論にどのように統合できるかをより深く理解する必要があると主張します。

DSTL: Solution to Limitation of Small Corpus in Speech Emotion Recognition

DSTL: Solution to Limitation of Small Corpus in Speech Emotion Recognition / DSTL：音声感情認識における小規模コーパスの限界への解決策

Traditional machine learning methods share a common hypothesis: training and testing datasets must be in a common feature space with the same distribution. However, in reality, the labeled target data may be rare, so that target space does not share the same feature space or distribution as an available training set (source domain). To address the mismatch of domains, we propose a Dual-Subspace Transfer Learning (DSTL) framework that considers both the common and specific information of the two domains. In DSTL, a latent common subspace is first learned to preserve the data properties and reduce the discrepancy of domains. Then, we propose a mapping strategy to transfer the sourcespecific information to the target subspace. The integration of the domain-common and specific information constructs the proposed DSTL framework. In comparison to the stateart-of works, the main contribution of our work is that the DSTL framework not only considers the commonalities, but also exploits the specific information. Experiments on three emotional speech corpora verify the effectiveness of our approach. The results show that the methods which include both domain-common and specific information perform better than the baseline methods which only exploit the domain commonalities.



従来の機械学習手法には共通の仮説があります。それは、トレーニングデータセットとテストデータセットは、同じ分布を持つ共通の特徴空間に存在する必要があるということです。しかし、実際には、ラベル付けされたターゲットデータは稀であり、ターゲット空間は利用可能なトレーニングセット（ソースドメイン）と同じ特徴空間または分布を共有していない可能性があります。このドメインの不一致に対処するため、2つのドメインの共通情報と固有情報の両方を考慮するデュアルサブスペース転送学習（DSTL）フレームワークを提案します。DSTLでは、まず潜在的な共通サブスペースを学習することで、データ特性を保持し、ドメイン間の不一致を低減します。次に、ソース固有の情報をターゲットサブスペースに転送するためのマッピング戦略を提案します。ドメイン共通情報とドメイン固有情報の統合により、提案されたDSTLフレームワークが構築されます。最先端の研究と比較して、本研究の主な貢献は、DSTLフレームワークが共通性を考慮するだけでなく、固有情報も活用することです。3つの感情音声コーパスに対する実験により、このアプローチの有効性が検証されました。結果は、ドメイン共通情報と固有情報の両方を含む手法が、ドメイン共通性のみを活用するベースライン手法よりも優れたパフォーマンスを発揮することを示しています。

Revisiting Counting Solutions for the Global Cardinality Constraint

Revisiting Counting Solutions for the Global Cardinality Constraint / グローバルカーディナリティ制約に対する計数解の再考

Counting solutions for a combinatorial problem has been identified as an important concern within the Artificial Intelligence field. It is indeed very helpful when exploring the structure of the solution space. In this context, this paper revisits the computation process to count solutions for the global cardinality constraint in the context of counting-based search. It first highlights an error and then presents a way to correct the upper bound on the number of solutions for this constraint.



組み合わせ問題の解を数えることは、人工知能分野において重要な関心事として認識されています。これは、解空間の構造を探索する際に非常に役立ちます。この文脈において、本論文では、数え上げベースの検索のコンテキストで、グローバルカーディナリティ制約の解を数える計算プロセスを再検討します。まずエラーを指摘し、次にこの制約の解の数の上限を修正する方法を示します。

Community Structure in Industrial SAT Instances

Community Structure in Industrial SAT Instances / 産業SATインスタンスにおけるコミュニティ構造

Modern SAT solvers have experienced a remarkable progress on solving industrial instances. It is believed that most of these successful techniques exploit the underlying structure of industrial instances. Recently, there have been some attempts to analyze the structure of industrial SAT instances in terms of complex networks, with the aim of explaining the success of SAT solving techniques, and possibly improving them.In this paper, we study the community structure, or modularity, of industrial SAT instances. In a graph with clear community structure, or high modularity, we can find a partition of its nodes into communities such that most edges connect variables of the same community. Representing SAT instances as graphs, we show that most application benchmarks are characterized by a high modularity. On the contrary, random SAT instances are closer to the classical Erdös-Rényi random graph model, where no structure can be observed. We also analyze how this structure evolves by the effects of the execution of a CDCL SAT solver, and observe that new clauses learned by the solver during the search contribute to destroy the original structure of the formula. Motivated by this observation, we finally present an application that exploits the community structure to detect relevant learned clauses, and we show that detecting these clauses results in an improvement on the performance of the SAT solver. Empirically, we observe that this improves the performance of several SAT solvers on industrial SAT formulas, especially on satisfiable instances.



現代のSATソルバーは、産業分野のインスタンスの解法において目覚ましい進歩を遂げてきました。これらの成功例の多くは、産業分野のインスタンスの根底にある構造を利用していると考えられています。近年、SATソルバーの成功の理由を説明し、場合によっては改善することを目的として、産業分野のSATインスタンスの構造を複雑ネットワークの観点から分析する試みがいくつか行われています。本稿では、産業分野のSATインスタンスのコミュニティ構造、すなわちモジュール性について考察します。明確なコミュニティ構造、すなわち高いモジュール性を持つグラフでは、ノードが複数のコミュニティに分割され、ほとんどのエッジが同じコミュニティの変数に繋がっていることがわかります。SATインスタンスをグラフとして表現することで、ほとんどのアプリケーションベンチマークが高度なモジュール性を特徴とすることを示します。一方、ランダムSATインスタンスは、構造が観察されない古典的なエルデシュ・レーニのランダムグラフモデルに近いものです。また、CDCL SATソルバーの実行によってこの構造がどのように変化するかを分析し、ソルバーが探索中に学習した新しい節が、式の元の構造を破壊する要因となることを観察します。この観察に基づき、我々は最終的に、コミュニティ構造を利用して関連学習済み節を検出するアプリケーションを提示し、これらの節を検出することでSATソルバーのパフォーマンスが向上することを示します。経験的に、これにより、特に充足可能なインスタンスにおいて、産業用SAT式に対するいくつかのSATソルバーのパフォーマンスが向上することが観察されています。

Multi-agent Inverse Reinforcement Learning for Certain General-sum Stochastic Games

Multi-agent Inverse Reinforcement Learning for Certain General-sum Stochastic Games / 特定の一般和確率ゲームのためのマルチエージェント逆強化学習

This paper addresses the problem of multi-agent inverse reinforcement learning (MIRL) in a two-player general-sum stochastic game framework. Five variants of MIRL are considered: uCS-MIRL, advE-MIRL, cooE-MIRL, uCE-MIRL, and uNE-MIRL, each distinguished by its solution concept. Problem uCS-MIRL is a cooperative game in which the agents employ cooperative strategies that aim to maximize the total game value. In problem uCE-MIRL, agents are assumed to follow strategies that constitute a correlated equilibrium while maximizing total game value. Problem uNE-MIRL is similar to uCE-MIRL in total game value maximization, but it is assumed that the agents are playing a Nash equilibrium. Problems advE-MIRL and cooE-MIRL assume agents are playing an adversarial equilibrium and a coordination equilibrium, respectively. We propose novel approaches to address these five problems under the assumption that the game observer either knows or is able to accurately estimate the policies and solution concepts for players. For uCS-MIRL, we first develop a characteristic set of solutions ensuring that the observed bi-policy is a uCS and then apply a Bayesian inverse learning method. For uCE-MIRL, we develop a linear programming problem subject to constraints that define necessary and sufficient conditions for the observed policies to be correlated equilibria. The objective is to choose a solution that not only minimizes the total game value difference between the observed bi-policy and a local uCS, but also maximizes the scale of the solution. We apply a similar treatment to the problem of uNE-MIRL. The remaining two problems can be solved efficiently by taking advantage of solution uniqueness and setting up a convex optimization problem. Results are validated on various benchmark grid-world games.



本論文では、2プレイヤー一般和確率ゲームフレームワークにおけるマルチエージェント逆強化学習(MIRL)の問題を取り上げます。MIRLには、uCS-MIRL、advE-MIRL、cooE-MIRL、uCE-MIRL、およびuNE-MIRLの5つの変種があり、それぞれ解の概念によって区別されます。問題uCS-MIRLは、エージェントが協力戦略を採用してゲーム全体の価値を最大化することを目指す協力ゲームです。問題uCE-MIRLでは、エージェントはゲーム全体の価値を最大化しながら相関均衡を構成する戦略に従うと想定されます。問題uNE-MIRLは、総ゲーム価値最大化においてuCE-MIRLに類似していますが、エージェントがナッシュ均衡をプレイしていると仮定します。問題advE-MIRLとcooE-MIRLは、それぞれエージェントが敵対的均衡と調整均衡をプレイしていると仮定します。ゲーム オブザーバーがプレイヤーのポリシーとソリューションの概念を知っているか正確に推定できるという仮定の下、これら5つの問題に対処するための新しいアプローチを提案します。uCS-MIRLの場合、まず、観測された2ポリシーがuCSであることを保証する特徴的なソリューション セットを開発し、次にベイズ逆学習法を適用します。uCE-MIRLの場合、観測されたポリシーが相関均衡であるための必要かつ十分な条件を定義する制約条件の下で線形計画問題を開発します。目的は、観測された2ポリシーとローカルuCSの総ゲーム価値の差を最小化するだけでなく、ソリューションのスケールを最大化するソリューションを選択することです。uNE-MIRLの問題にも同様の手法を適用します。残りの2つの問題は、解の一意性を利用し、凸最適化問題を設定することで効率的に解くことができます。結果は様々なベンチマークグリッドワールドゲームで検証されています。

Synthesizing Argumentation Frameworks from Examples

Synthesizing Argumentation Frameworks from Examples / 事例からの議論フレームワークの統合

Argumentation is today a topical area of artificial intelligence (AI) research. Abstract argumentation, with argumentation frameworks (AFs) as the underlying knowledge representation formalism, is a central viewpoint to argumentation in AI. Indeed, from the perspective of AI and computer science, understanding computational and representational aspects of AFs is key in the study of argumentation.Realizability of AFs has been recently proposed as a central notion for analyzing the expressive power of AFs under different semantics. In this work, we propose and study the AF synthesis problem as a natural extension of realizability, addressing some of the shortcomings arising from the relatively stringent definition of realizability. In particular, realizability gives means of establishing exact conditions on when a given collection of subsets of arguments has an AF with exactly the given collection as its set of extensions under a specific argumentation semantics. However, in various settings within the study of dynamics of argumentation—including revision and aggregation of AFs—non-realizability can naturally occur. To accommodate such settings, our notion of AF synthesis seeks to construct, or synthesize, AFs that are semantically closest to the knowledge at hand even when no AFs exactly representing the knowledge exist. Going beyond defining the AF synthesis problem, we study both theoretical and practical aspects of the problem. In particular, we (i) prove NP-completeness of AF synthesis under several semantics, (ii) study basic properties of the problem in relation to realizability, (iii) develop algorithmic solutions to NP-hard AF synthesis using the constraint optimization paradigms of maximum satisfiability and answer set programming, (iv) empirically evaluate our algorithms on different forms of AF synthesis instances, as well as (v) discuss variants and generalizations of AF synthesis.



議論は今日、人工知能(AI)研究の話題の領域です。議論フレームワーク(AF)を基礎となる知識表現形式とする抽象的議論は、AIにおける議論の中心的な視点です。実際、AIとコンピュータサイエンスの観点からは、AFの計算的側面と表現的側面を理解することが議論の研究の鍵となります。AFの実現可能性は、異なるセマンティクスにおけるAFの表現力を分析するための中心的な概念として最近提案されました。本研究では、実現可能性の自然な拡張としてAF合成問題を提案し、検討することで、実現可能性の比較的厳格な定義から生じる欠点のいくつかに対処します。特に、実現可能性は、特定の議論セマンティクスの下で、与えられた議論のサブセットのコレクションが、まさにそのコレクションをその拡張の集合として持つAFを持つ場合の正確な条件を確立する手段を提供します。しかし、議論のダイナミクスの研究における様々な設定（AFの修正と集約を含む）において、実現不可能な状況が自然に発生する可能性があります。このような状況に対応するために、AF合成の概念は、知識を正確に表現するAFが存在しない場合でも、意味的に手元の知識に最も近いAFを構築（合成）することを目指します。AF合成問題の定義にとどまらず、問題の理論的側面と実際的側面の両方を研究します。特に、(i)いくつかの意味論におけるAF合成のNP完全性を証明し、(ii)実現可能性に関連した問題の基本特性を研究し、(iii)最大充足可能性と解答セットプログラミングという制約最適化パラダイムを用いてNP困難なAF合成に対するアルゴリズム的ソリューションを開発し、(iv)さまざまな形式のAF合成インスタンスでアルゴリズムを経験的に評価し、(v)AF合成の変種と一般化について議論します。

Acceptable Planning: Influencing Individual Behavior to Reduce Transportation Energy Expenditure of a City

Acceptable Planning: Influencing Individual Behavior to Reduce Transportation Energy Expenditure of a City / 許容可能な計画：都市の交通エネルギー消費を削減するための個人行動への影響

Our research aims at developing intelligent systems to reduce the transportation-related energy expenditure of a large city by influencing individual behavior. We introduce Copter – an intelligent travel assistant that evaluates multi-modal travel alternatives to find a plan that is acceptable to a person given their context and preferences. We propose a formulation for acceptable planning that brings together ideas from AI, machine learning, and economics. This formulation has been incorporated in Copter that produces acceptable plans in real-time. We adopt a novel empirical evaluation framework that combines human decision data with a high fidelity multi-modal transportation simulation to demonstrate a 4% energy reduction and 20% delay reduction in a realistic deployment scenario in Los Angeles, California, USA. This article is part of the special track on AI and Society.



私たちの研究は、個人の行動に影響を与えることで大都市の交通関連のエネルギー消費を削減するインテリジェントシステムの開発を目指しています。Copterを紹介します。これは、マルチモーダルな移動手段の選択肢を評価し、人の状況や好みを考慮して受け入れられる計画を見つけるインテリジェントな旅行アシスタントです。AI、機械学習、経済学のアイデアを統合した、受け入れ可能な計画の定式化を提案します。この定式化は、受け入れ可能な計画をリアルタイムで生成するCopterに組み込まれています。人間の意思決定データと高忠実度のマルチモーダル輸送シミュレーションを組み合わせた新しい経験的評価フレームワークを採用し、米国カリフォルニア州ロサンゼルスでの現実的な展開シナリオで4%のエネルギー削減と20%の遅延削減を実証しました。この記事は、AIと社会に関する特別トラックの一部です。

Recognizing Top-Monotonic Preference Profiles in Polynomial Time

Recognizing Top-Monotonic Preference Profiles in Polynomial Time / 認識多項式時間におけるトップモノトニック選好プロファイル

We provide the first polynomial-time algorithm for recognizing if a profile of (possibly weak) preference orders is top-monotonic. Top-monotonicity is a generalization of the notions of single-peakedness and single-crossingness, defined by Barbera and Moreno. Top-monotonic profiles always have weak Condorcet winners and satisfy a variant of the median voter theorem. Our algorithm proceeds by reducing the recognition problem to the SAT-2CNF problem.



（おそらく弱い）優先順位のプロファイルがトップモノトニックであるかどうかを認識するための最初の多項式時間アルゴリズムを提供します。トップモノトニック性は、バルベラとモレノによって定義された単峰性と単交差性の概念の一般化です。トップモノトニックプロファイルは常に弱いコンドルセ勝者を持ち、中央投票者定理の変形を満たします。私たちのアルゴリズムは、認識問題をSAT-2CNF問題に縮減することで進めます。

Variable Elimination in Binary CSPs

Variable Elimination in Binary CSPs / 二項CSPにおける変数除去

We investigate rules which allow variable elimination in binary CSP (constraint satisfaction problem) instances while conserving satisfiability. We study variable-elimination rules based on the language of forbidden patterns enriched with counting and quantification over variables and values. We propose new rules and compare them, both theoretically and experimentally. We give optimised algorithms to apply these rules and show that each define a novel tractable class. Using our variable-elimination rules in preprocessing allowed us to solve more benchmark problems than without.



我々は、二項制約充足問題（CSP）インスタンスにおいて、充足可能性を維持しながら変数除去を可能にする規則を調査します。変数と値の計数と量化を豊富に含む禁制パターンの言語に基づく変数除去規則を研究します。新しい規則を提案し、理論的および実験的に比較します。これらの規則を適用するための最適化されたアルゴリズムを提示し、それぞれが新しい扱いやすいクラスを定義することを示す。前処理に我々の変数除去規則を使用することで、規則を使用しない場合よりも多くのベンチマーク問題を解くことができた。

On Non-Cooperativeness in Social Distance Games

On Non-Cooperativeness in Social Distance Games / 社会的距離ゲームにおける非協力性について

We consider Social Distance Games (SDGs), that is cluster formation games in which the utility of each agent only depends on the composition of the cluster she belongs to, proportionally to her harmonic centrality, i.e., to the average inverse distance from the other agents in the cluster. Under a non-cooperative perspective, we adopt Nash stable outcomes, in which no agent can improve her utility by unilaterally changing her coalition, as the target solution concept. Although a Nash equilibrium for a SDG can always be computed in polynomial time, we obtain a negative result concerning the game convergence and we prove that computing a Nash equilibrium that maximizes the social welfare is NP-hard by a polynomial time reduction from the NP-complete Restricted Exact Cover by 3-Sets problem. We then focus on the performance of Nash equilibria and provide matching upper bound and lower bounds on the price of anarchy of Θ(n), where n is the number of nodes of the underlying graph. Moreover, we show that there exists a class of SDGs having a lower bound on the price of stability of 6/5 − ε, for any ε > 0. Finally, we characterize the price of stability 5 of SDGs for graphs with girth 4 and girth at least 5, the girth being the length of the shortest cycle in the graph.



我々は、ソーシャルディスタンスゲーム（SDG）、すなわちクラスター形成ゲームを考察します。このゲームでは、各エージェントの効用は、所属するクラスターの構成のみに依存し、その構成は、エージェントの調和中心性、すなわちクラスター内の他のエージェントからの平均逆距離に比例します。非協力的な観点では、目標解概念として、どのエージェントも一方的に同盟関係を変更することで効用を向上させることができないナッシュ安定結果を採用します。SDGのナッシュ均衡は常に多項式時間で計算できますが、ゲームの収束に関しては否定的な結果を得ており、NP完全な3セットによる制限付き完全被覆問題からの多項式時間還元によって、社会的福祉を最大化するナッシュ均衡の計算がNP困難であることを証明しています。次に、ナッシュ均衡のパフォーマンスに焦点を当て、Θ(n)の無政府状態の価格の一致する上限と下限を提供します。ここで、nは基礎となるグラフのノードの数です。さらに、ε> 0に対して、安定の価格の下限が6/5− ε であるSDGのクラスが存在することを示します。最後に、内周が4で内周が少なくとも5のグラフについて、SDGの安定の価格5を特徴付けます。内周はグラフの最短サイクルの長さです。

On the Time and Space Complexity of Genetic Programming for Evolving Boolean Conjunctions

On the Time and Space Complexity of Genetic Programming for Evolving Boolean Conjunctions / 進化型ブール論理積のための遺伝的プログラミングの時間・空間計算量について

Genetic programming (GP) is a general purpose bio-inspired meta-heuristic for the evolution of computer programs. In contrast to the several successful applications, there is little understanding of the working principles behind GP. In this paper we present a performance analysis that sheds light on the behaviour of simple GP systems for evolving conjunctions of n variables (ANDn). The analysis of a random local search GP system with minimal terminal and function sets reveals the relationship between the number of iterations and the progress the GP makes toward finding the target function. Afterwards we consider a more realistic GP system equipped with a global mutation operator and prove that it can efficiently solve ANDn by producing programs of linear size that fit a training set to optimality and with high probability generalise well. Additionally, we consider more general problems which extend the terminal set with undesired variables or negated variables. In the presence of undesired variables, we prove that, if non-strict selection is used, then the algorithm fits the complete training set efficiently while the strict selection algorithm may fail with high probability unless the substitution operator is switched off. If negations are allowed, we show that while the algorithms fail to fit the complete training set, the constructed solutions generalise well. Finally, from a problem hardness perspective, we reveal the existence of small training sets that allow the evolution of the exact conjunctions even with access to negations or undesired variables.



遺伝的プログラミング（GP）は、コンピュータプログラムの進化を目的とした、生物学に着想を得た汎用的なメタヒューリスティックです。数々の成功例がある一方で、GPの背後にある動作原理はほとんど解明されていません。本稿では、n個の変数の進化的連言（ANDn）に対する単純なGPシステムの挙動を明らかにする性能分析を提示します。最小の終端および関数セットを持つランダム局所探索GPシステムの解析により、反復回数とGPが目的関数を見つけるまでの進捗との関係を明らかにします。その後、グローバル突然変異演算子を備えたより現実的なGPシステムを考察し、訓練セットを最適にフィッティングし、高い確率で良好に一般化する線形サイズのプログラムを生成することで、ANDnを効率的に解くことができることを証明します。さらに、不要な変数または否定変数で終端セットを拡張する、より一般的な問題も考察します。不要な変数が存在する場合、非厳密な選択を用いるとアルゴリズムは訓練セット全体を効率的にフィッティングしますが、厳密な選択アルゴリズムは置換演算子をオフにしない限り、高い確率で失敗することを証明します。否定が許容される場合、アルゴリズムは完全なトレーニングセットに適合できないものの、構築された解は良好に一般化されることを示します。最後に、問題の難しさの観点から、否定や不要な変数へのアクセスがあっても正確な接続詞の進化を可能にする小規模なトレーニングセットの存在を明らかにします。

Embedding Projection for Targeted Cross-lingual Sentiment: Model Comparisons and a Real-World Study

Embedding Projection for Targeted Cross-lingual Sentiment: Model Comparisons and a Real-World Study / 標的型クロスリンガル感情のための埋め込み射影：モデル比較と実世界研究

Sentiment analysis benefits from large, hand-annotated resources in order to train and test machine learning models, which are often data hungry. While some languages, e.g., English, have a vast arrayof these resources, most under-resourced languages do not, especially for fine-grained sentiment tasks, such as aspect-level or targeted sentiment analysis. To improve this situation, we propose a cross-lingual approach to sentiment analysis that is applicable to under-resourced languages and takes into account target-level information. This model incorporates sentiment information into bilingual distributional representations, byjointly optimizing them for semantics and sentiment, showing state-of-the-art performance at sentence-level when combined with machine translation. The adaptation to targeted sentiment analysis on multiple domains shows that our model outperforms other projection-based bilingual embedding methods on binary targetedsentiment tasks. Our analysis on ten languages demonstrates that the amount of unlabeled monolingual data has surprisingly little effect on the sentiment results. As expected, the choice of a annotated source language for projection to a target leads to better results for source-target language pairs which are similar. Therefore, our results suggest that more efforts should be spent on the creation of resources for less similar languages tothose which are resource-rich already. Finally, a domain mismatch leads to a decreased performance. This suggests resources in any language should ideally cover varieties of domains.



感情分析は、多くの場合大量のデータを必要とする機械学習モデルのトレーニングとテストのために、大規模で手作業で注釈が付けられたリソースの恩恵を受けます。英語など一部の言語にはこのようなリソースが豊富ですが、リソースが不足しているほとんどの言語には、特にアスペクトレベルやターゲット感情分析などのきめ細かい感情タスクでは、リソースが不足しています。この状況を改善するために、リソースが不足している言語に適用可能で、ターゲットレベルの情報を考慮した感情分析へのクロスリンガルアプローチを提案します。このモデルは、感情情報をバイリンガル分布表現に組み込み、意味と感情の両方に対して最適化することで、機械翻訳と組み合わせることで文レベルで最先端のパフォーマンスを示します。複数のドメインを対象とした感情分析への適応により、本モデルは、バイナリを対象とした感情分析タスクにおいて、他の投影ベースのバイリンガル埋め込み手法よりも優れた性能を発揮することが示されました。10言語を対象とした分析では、ラベルなしの単一言語データの量が感情分析結果に驚くほど影響を与えないことが実証されました。予想通り、投影対象言語として注釈付きソース言語を選択すると、類似するソース言語とターゲット言語のペアにおいてより良い結果が得られました。したがって、本研究の結果は、既にリソースが豊富な言語との類似性が低い言語のリソース作成に、より多くの労力を費やす必要があることを示唆しています。最後に、ドメインの不一致はパフォーマンスの低下につながります。これは、あらゆる言語のリソースが理想的には様々なドメインをカバーする必要があることを示唆しています。

Interpretable Charge Prediction for Criminal Cases with Dynamic Rationale Attention

Interpretable Charge Prediction for Criminal Cases with Dynamic Rationale Attention / 動的根拠アテンションを用いた刑事事件の解釈可能な起訴予測

Charge prediction which aims to determine appropriate charges for criminal cases based on textual fact descriptions, is an important technology in the field of AI&Law. Previous works focus on improving prediction accuracy, ignoring the interpretability, which limits the methods’ applicability. In this work, we propose a deep neural framework to extract short but charge-decisive text snippets – rationales – from input fact description, as the interpretation of charge prediction. To solve the scarcity problem ofrationale annotatedcorpus, rationalesare extractedinareinforcement stylewiththe only supervision in the form of charge labels. We further propose a dynamic rationale attention mechanism to better utilize the information in extracted rationales and predict the charges. Experimental results show that besides providing charge prediction interpretation, our approach can also capture subtle details to help charge prediction.



刑事事件の適切な起訴を決定することを目的とした起訴予測は、AIと法律の分野における重要な技術です。これまでの研究は予測精度の向上に重点を置き、解釈可能性を無視していたため、手法の適用範囲が限られていました。本研究では、起訴予測の解釈として、入力事実記述から短いながらも起訴を決定づけるテキストスニペット（根拠）を抽出するためのディープニューラルフレームワークを提案します。根拠が注釈付けされたコーパスの不足問題を解決するために、起訴ラベルの形でのみ監督された強化学習スタイルで根拠を抽出します。さらに、抽出された根拠の情報をより有効に活用して起訴を予測するための動的根拠アテンションメカニズムを提案します。実験結果は、起訴予測の解釈を提供することに加えて、私たちのアプローチは起訴予測を支援する微妙な詳細も捉えることができることを示しています。

Full Characterization of Parikh’s Relevance-Sensitive Axiom for Belief Revision

Full Characterization of Parikh’s Relevance-Sensitive Axiom for Belief Revision / 信念修正のためのParikhの関連性依存公理の完全な特徴づけ

In this article, the epistemic-entrenchment and partial-meet characterizations of Parikh’s relevance-sensitive axiom for belief revision, known as axiom (P), are provided. In short, axiom (P) states that, if a belief set $K$ can be divided into two disjoint compartments, and the new information $\varphi$ relates only to the first compartment, then the revision of $K$ by $\varphi$ should not affect the second compartment. Accordingly, we identify the subclass of epistemic-entrenchment and that of selection-function preorders, inducing AGM revision functions that satisfy axiom (P). Hence, together with the faithful-preorders characterization of (P) that has already been provided, Parikh’s axiom is fully characterized in terms of all popular constructive models of Belief Revision. Since the notions of relevance and local change are inherent in almost all intellectual activity, the completion of the constructive view of (P) has a significant impact on many theoretical, as well as applied, domains of Artificial Intelligence.



本稿では、信念修正のためのパリクの関連性に敏感な公理（公理（P））の認識論的定着と部分的一致の特徴付けを示します。要するに、公理(P)は、信念集合$K$を2つの互いに素な区画に分割でき、新しい情報$\varphi$が最初の区画にのみ関連する場合、$\varphi$による$K$の修正は2番目の区画に影響を与えないということを述べています。したがって、認識論的エントレンチメントのサブクラスと選択関数の事前順序のサブクラスを特定し、公理(P)を満たすAGM修正関数を誘導します。したがって、すでで提供されている(P)の忠実な事前順序の特徴付けと合わせて、Parikhの公理は、信念修正のすべての一般的な構成モデルの観点から完全に特徴付けられます。関連性と局所的変化の概念は、ほとんどすべての知的活動に内在しているため、(P)の構成的見解の完成は、人工知能の多くの理論的領域だけでなく応用領域にも大きな影響を与えます。

Enhancing Statement Evaluation in Argumentation via Multi-labelling Systems

Enhancing Statement Evaluation in Argumentation via Multi-labelling Systems / マルチラベリングシステムによる議論における声明評価の強化

In computational models of argumentation, the justification of statements has drawn less attention than the construction and justification of arguments. Significant losses of sensitivity or expressibility on statement statuses can be incurred by otherwise appealing formalisms. In order to reappraise statement statuses and, more generally, to support a uniform modelling of different phases of the argumentation process we introduce multi-labelling systems, a generic formalism devoted to represent reasoning processes consisting of a sequence of labelling stages. In the argumentation context, two families of multi-labelling systens, called argument-focused and statement-focused approach are identified and compared. Then they are shown to be able to encompass several prominent literature proposals as special cases, thereby enabling a systematic comparison evidencing their merits and limits. Further, we show that the proposed model supports tunability of statement justification by specifying a few alternative statement justification labellings, and we illustrate how they can be seamlessly integrated into different formalisms.



議論の計算モデルにおいて、ステートメントの正当化は、議論の構築と正当化ほど注目されていません。ステートメントの状態に関する感度や表現力の大幅な損失は、他の点では魅力的な形式主義によっても引き起こされる可能性があります。ステートメントの状態を再評価し、より一般的には、議論プロセスのさまざまな段階の統一的なモデル化をサポートするために、一連のラベリング段階からなる推論プロセスを表現するための一般的な形式主義であるマルチラベリングシステムを導入します。議論のコンテキストでは、議論に焦点を当てたアプローチとステートメントに焦点を当てたアプローチと呼ばれる2つのマルチラベリングシステムファミリが識別され、比較されます。次に、これらがいくつかの著名な文献の提案を特殊なケースとして包含できることが示され、それによって体系的な比較が可能になり、それぞれのメリットと限界が証明されます。さらに、提案モデルが、いくつかの代替ステートメント正当化ラベリングを指定することによってステートメント正当化の調整可能性をサポートすることを示し、それらをさまざまな形式主義にシームレスに統合する方法を示します。

Pattern-Based Approach to the Workflow Satisfiability Problem with User-Independent Constraints

Pattern-Based Approach to the Workflow Satisfiability Problem with User-Independent Constraints / ユーザー非依存制約を伴うワークフロー充足可能性問題へのパターンベースアプローチ

The fixed parameter tractable (FPT) approach is a powerful tool in tackling computationally hard problems.  In this paper, we link FPT results to classic artificial intelligence (AI) techniques to show how they complement each other.  Specifically, we consider the workflow satisfiability problem (WSP) which asks whether there exists an assignment of authorised users to the steps in a workflow specification, subject to certain constraints on the assignment.  It was shown by Cohen et al. (JAIR 2014) that WSP restricted to the class of user-independent constraints (UI), covering many practical cases, admits FPT algorithms, i.e. can be solved in time exponential only in the number of steps k and polynomial in the number of users n.  Since usually k << n in WSP, such FPT algorithms are of great practical interest. We present a new interpretation of the FPT nature of the WSP with UI constraints giving a decomposition of the problem into two levels.  Exploiting this two-level split, we develop a new FPT algorithm that is by many orders of magnitude faster than the previous state-of-the-art WSP algorithm and also has only polynomial-space complexity.  We also introduce new pseudo-Boolean (PB) and Constraint Satisfaction (CSP) formulations of the WSP with UI constraints which efficiently exploit this new decomposition of the problem and raise the novel issue of how to use general-purpose solvers to tackle FPT problems in a fashion that meets FPT efficiency expectations.  In our computational study, we investigate, for the first time, the phase transition (PT) properties of the WSP, under a model for generation of random instances.  We show how PT studies can be extended, in a novel fashion, to support empirical evaluation of scaling of FPT algorithms.



固定パラメータ制御可能（FPT）アプローチは、計算困難な問題に取り組むための強力なツールです。本稿では、FPTの結果を従来の人工知能（AI）手法に関連付けて、それらがどのように補完し合うかを示します。具体的には、ワークフローの充足可能性問題（WSP）を検討します。これは、割り当てに関する特定の制約に従って、承認されたユーザーのワークフロー仕様のステップへの割り当てが存在するかどうかを尋ねるものです。Cohenら（JAIR 2014）は、多くの実際的なケースをカバーするユーザー非依存制約（UI）のクラスに制限されたWSPはFPTアルゴリズムを許容し、つまり、ステップ数kに対してのみ指数時間で、ユーザー数nに対して多項式で解決できることを示しました。通常、WSPではk << nであるため、このようなFPTアルゴリズムは実用上非常に興味深いものです。この2レベルの分割を利用して、従来の最先端のWSPアルゴリズムよりも桁違いに高速で、多項式空間の計算量しかない新しいFPTアルゴリズムを開発しました。また、UI制約付きのWSPの新しい疑似ブール(PB)および制約充足(CSP)定式化も導入し、問題のこの新しい分解を効率的に活用して、FPT効率の期待に応える方法でFPT問題に取り組むために汎用ソルバーをどのように使用するかという新しい問題を提起します。私たちの計算研究では、ランダムインスタンス生成モデルの下で、WSPの相転移(PT)プロパティを初めて調査します。FPTアルゴリズムのスケーリングの経験的評価をサポートするために、PT研究を新しい方法で拡張する方法を示します。

Deep Dialog Act Recognition using Multiple Token, Segment, and Context Information Representations

Deep Dialog Act Recognition using Multiple Token, Segment, and Context Information Representations / 複数のトークン、セグメント、コンテキスト情報表現を用いたディープダイアログ行為認識

Automatic dialog act recognition is a task that has been widely explored over the years. In recent works, most approaches to the task explored different deep neural network architectures to combine the representations of the words in a segment and generate a segment representation that provides cues for intention. In this study, we explore means to generate more informative segment representations, not only by exploring different network architectures, but also by considering different token representations, not only at the word level, but also at the character and functional levels. At the word level, in addition to the commonly used uncontextualized embeddings, we explore the use of contextualized representations, which are able to provide information concerning word sense and segment structure. Character-level tokenization is important to capture intention-related morphological aspects that cannot be captured at the word level. Finally, the functional level provides an abstraction from words, which shifts the focus to the structure of the segment. Additionally, we explore approaches to enrich the segment representation with context information from the history of the dialog, both in terms of the classifications of the surrounding segments and the turn-taking history. This kind of information has already been proved important for the disambiguation of dialog acts in previous studies. Nevertheless, we are able to capture additional information by considering a summary of the dialog history and a wider turn-taking context. By combining the best approaches at each step, we achieve performance results that surpass the previous state-of-the-art on generic dialog act recognition on both the Switchboard Dialog Act Corpus (SwDA) and the ICSI Meeting Recorder Dialog Act Corpus (MRDA), which are two of the most widely explored corpora for the task. Furthermore, by considering both past and future context, similarly to what happens in an annotation scenario, our approach achieves a performance similar to that of a human annotator on SwDA and surpasses it on MRDA.



自動対話行為認識は、長年にわたって広く研究されてきたタスクです。近年の研究において、この課題に対する多くのアプローチは、セグメント内の単語の表現を統合し、意図の手がかりとなるセグメント表現を生成するために、様々なディープニューラルネットワークアーキテクチャを探求してきました。本研究では、異なるネットワークアーキテクチャを探求するだけでなく、単語レベルだけでなく、文字レベルや機能レベルでも様々なトークン表現を考慮することで、より情報量の多いセグメント表現を生成する手段を探求します。単語レベルでは、一般的に用いられる文脈化されていない埋め込みに加えて、単語の意味やセグメント構造に関する情報を提供できる文脈化された表現の使用を探求します。文字レベルのトークン化は、単語レベルでは捉えられない意図に関連する形態学的側面を捉えるために重要です。最後に、機能レベルでは単語から抽象化が提供され、セグメントの構造に焦点が移ります。さらに、周囲のセグメントの分類とターンテイキング履歴の両方の観点から、対話履歴からの文脈情報を用いてセグメント表現を豊かにするアプローチを探求します。この種の情報は、これまでの研究において対話行為の曖昧性解消に重要であることが既に証明されています。しかしながら、対話履歴の要約とより広範なターンテーキングの文脈を考慮することで、追加情報を取得できます。各ステップで最適なアプローチを組み合わせることで、このタスクで最も広く調査されている2つのコーパスであるSwitchboard Dialog Act Corpus (SwDA)とICSI Meeting Recorder Dialog Act Corpus (MRDA)の両方において、一般的な対話行為認識におけるこれまでの最先端技術を上回るパフォーマンス結果を達成しました。さらに、注釈付けのシナリオと同様に、過去と未来の両方の文脈を考慮することで、私たちのアプローチはSwDAにおいて人間の注釈者と同等のパフォーマンスを達成し、MRDAにおいてはそれを上回ります。

General Game Playing with Imperfect Information

General Game Playing with Imperfect Information / 不完全情報を用いた一般的なゲームプレイ

General Game Playing is a field which allows the researcher to investigate techniques that might eventually be used in an agent capable of Artificial General Intelligence.  Game playing presents a controlled environment in which to evaluate AI techniques, and so we have seen an increase in interest in this field of research.  Games of imperfect information offer the researcher an additional challenge in terms of complexity over games with perfect information.  In this article, we look at imperfect-information games: their expression, their complexity, and the additional demands of their players.  We consider the problems of working with imperfect information and introduce a technique called HyperPlay, for efficiently sampling very large information sets, and present a formalism together with pseudo code so that others may implement it. We examine the design choices for the technique, show its soundness and completeness then provide some experimental results and demonstrate the use of the technique in a variety of imperfect-information games, revealing its strengths, weaknesses, and its efficiency against randomly generating samples.  Improving the technique, we present HyperPlay-II, capable of correctly valuing information-gathering moves.  Again, we provide some experimental results and demonstrate the use of the new technique revealing its strengths, weaknesses and its limitations.



汎用ゲームプレイは、研究者が最終的に汎用人工知能を備えたエージェントで使用される可能性のある技術を調査できる分野です。ゲームプレイは、AI技術を評価するための制御された環境を提供するため、この研究分野への関心が高まっています。不完全情報ゲームは、完全情報ゲームよりも複雑さの点で研究者に追加の課題を提供します。この記事では、不完全情報ゲームについて、その表現、複雑さ、およびプレーヤーの追加要求について説明します。不完全情報での作業の問題を​​考慮し、非常に大きな情報セットを効率的にサンプリングするためのHyperPlayと呼ばれる手法を紹介し、他の人が実装できるように形式論と疑似コードを示します。この手法の設計上の選択肢を検討し、その健全性と完全性を示し、いくつかの実験結果を示し、さまざまな不完全情報ゲームでの手法の使用を実証して、ランダムに生成されるサンプルに対する長所、短所、および効率性を明らかにします。この手法を改良し、情報収集動作を正しく評価できるHyperPlay-IIを紹介します。ここでも、いくつかの実験結果を示し、この新手法の使用法を実証することで、その長所、短所、限界を明らかにします。

Classifying Inconsistency Measures Using Graphs

Classifying Inconsistency Measures Using Graphs / グラフを用いた不整合尺度の分類

The aim of measuring inconsistency is to obtain an evaluation of the imperfections in a set of formulas, and this evaluation may then be used to help decide on some course of action (such as rejecting some of the formulas, resolving the inconsistency, seeking better sources of information, etc). A number of proposals have been made to define measures of inconsistency. Each has its rationale. But to date, it is not clear how to delineate the space of options for measures, nor is it clear how we can classify measures systematically. To address these problems, we introduce a general framework for comparing syntactic measures of inconsistency. It is based on the notion of an inconsistency graph for each knowledgebase (a bipartite graph with a set of vertices representing formulas in the knowledgebase, a set of vertices representing minimal inconsistent subsets of the knowledgebase, and edges representing that a formula belongs to a minimal inconsistent subset). We then show that various measures can be computed using the inconsistency graph. Then we introduce abstractions of the inconsistency graph and use them to construct a hierarchy of syntactic inconsistency measures. Furthermore, we extend the inconsistency graph concept with a labeling that extends the hierarchy to include some other types of inconsistency measures.



不一致性を測定する目的は、一連の公式の不完全性の評価を得ることであり、この評価は、いくつかの行動方針（一部の公式を拒否する、不一致を解決する、より良い情報源を探すなど）を決定する際に役立ちます。不一致性の尺度を定義するために、多くの提案がなされてきました。それぞれに根拠があります。しかし、これまでのところ、尺度の選択肢をどのように定義するか、また、尺度を体系的に分類する方法は明確ではありません。これらの問題に対処するために、不一致性の統語的尺度を比較するための一般的な枠組みを導入します。これは、各知識ベースの矛盾グラフ（知識ベース内の論理式を表す頂点の集合、知識ベースの最小矛盾サブセットを表す頂点の集合、および論理式が最小矛盾サブセットに属することを表す辺を持つ二部グラフ）の概念に基づいています。次に、矛盾グラフを使用してさまざまな尺度を計算できることを示します。次に、矛盾グラフの抽象化を導入し、それを使用して構文矛盾尺度の階層を構築します。さらに、階層を拡張して他の種類の矛盾尺度を含むようにラベル付けすることで、矛盾グラフの概念を拡張します。

A Semantic Characterization ASP Base Revision

A Semantic Characterization ASP Base Revision / 意味的特徴付けASPベースの改訂

The paper deals with base revision for Answer Set Programming (ASP). Base revision in classical logic is done by the removal of formulas. Exploiting the non-monotonicity of ASP allows one to propose other revision strategies, namely addition strategy or removal and/or addition strategy. These strategies allow one to define families of rule-based revision operators. The paper presents a semantic characterization of these families of revision operators in terms of answer sets. This semantic characterization allows for equivalently considering the evolution of syntactic logic programs and the evolution of their semantic content. It then studies the logical properties of the proposed operators and gives complexity results.



この論文は、解答セットプログラミング（ASP）のベース修正を扱います。古典論理におけるベース修正は、論理式の削除によって行われます。ASPの非単調性を利用することで、追加戦略、または削除および/または追加戦略など、他の修正戦略を提案できます。これらの戦略により、ルールベースの修正演算子のファミリーを定義できます。本論文では、これらの修正演算子群の意味的特徴づけを、解答集合の観点から提示します。この意味的特徴づけにより、統語論理プログラムの進化とその意味内容の進化を等価的に考察することが可能になります。次に、提案された演算子の論理的性質を研究し、計算量に関する結果を示す。

参考文献

• Journal of Artificial Intelligence Resarch Vol. 66 (2019)

関連情報

• Journal of Artificial Intelligence Research: 論文一覧