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

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

1 論文
2 参考文献
3 関連情報

論文

Learning Explanatory Rules from Noisy Data

Learning Explanatory Rules from Noisy Data / ノイズデータからの説明ルールの学習

Artificial Neural Networks are powerful function approximators capable of modelling solutions to a wide variety of problems, both supervised and unsupervised. As their size and expressivity increases, so too does the variance of the model, yielding a nearly ubiquitous overfitting problem. Although mitigated by a variety of model regularisation methods, the common cure is to seek large amounts of training data–which is not necessarily easily obtained–that sufficiently approximates the data distribution of the domain we wish to test on. In contrast, logic programming methods such as Inductive Logic Programming offer an extremely data-efficient process by which models can be trained to reason on symbolic domains. However, these methods are unable to deal with the variety of domains neural networks can be applied to: they are not robust to noise in or mislabelling of inputs, and perhaps more importantly, cannot be applied to non-symbolic domains where the data is ambiguous, such as operating on raw pixels. In this paper, we propose a Differentiable Inductive Logic framework, which can not only solve tasks which traditional ILP systems are suited for, but shows a robustness to noise and error in the training data which ILP cannot cope with. Furthermore, as it is trained by backpropagation against a likelihood objective, it can be hybridised by connecting it with neural networks over ambiguous data in order to be applied to domains which ILP cannot address, while providing data efficiency and generalisation beyond what neural networks on their own can achieve.

人工ニューラルネットワークは、教師あり・教師なしの両方で、さまざまな問題の解をモデル化できる強力な関数近似器です。モデルのサイズと表現力が増大するにつれて、モデルの分散も増大し、ほぼ普遍的な過剰適合問題が生じます。様々なモデル正則化手法によって軽減されますが、一般的な解決策は、必ずしも容易に入手できるとは限らない大量のトレーニングデータを探し出すことです。これは、テスト対象領域のデータ分布を十分に近似します。一方、帰納的論理プログラミング（ILP）などの論理プログラミング手法は、モデルを記号領域で推論するようにトレーニングするための、極めてデータ効率の高いプロセスを提供します。しかし、これらの手法は、ニューラルネットワークが適用可能な多様な領域に対応できません。入力のノイズやラベルの誤りに対して堅牢ではなく、おそらくより重要なのは、生のピクセルを操作するなど、データが曖昧な非記号領域には適用できないことです。本論文では、従来のILPシステムが適しているタスクを解決できるだけでなく、ILPでは対応できないトレーニングデータ内のノイズやエラーに対しても堅牢性を示す、微分可能帰納的論理フレームワークを提案します。さらに、尤度目標に対するバックプロパゲーションによってトレーニングされるため、曖昧なデータ上のニューラルネットワークに接続してハイブリッド化することができ、ILPでは対処できないドメインに適用できると同時に、ニューラルネットワーク単独では達成できないデータ効率と一般化も実現できます。

Bisimulations on Data Graphs

Bisimulations on Data Graphs / データグラフ上の双模倣

Bisimulation provides structural conditions to characterize indistinguishability from an external observer between nodes on labeled graphs. It is a fundamental notion used in many areas, such as verification, graph-structured databases, and constraint satisfaction. However, several current applications use graphs where nodes also contain data (the so called “data graphs”), and where observers can test for equality or inequality of data values (e.g., asking the attribute ‘name’ of a node to be different from that of all its neighbors). The present work constitutes a first investigation of “data aware” bisimulations on data graphs. We study the problem of computing such bisimulations, based on the observational indistinguishability for XPath —a language that extends modal logics like PDL with tests for data equality— with and without transitive closure operators. We show that in general the problem is PSpace-complete, but identify several restrictions that yield better complexity bounds (coNP, PTime) by controlling suitable parameters of the problem, namely the amount of non-locality allowed, and the class of models considered (graphs, DAGs, trees). In particular, this analysis yields a hierarchy of tractable fragments.

バイシミュレーションは、ラベル付きグラフ上のノード間の外部観察者からの識別不能性を特徴付ける構造的条件を提供します。これは、検証、グラフ構造データベース、制約充足など、多くの分野で用いられる基本的な概念です。しかしながら、現在の多くのアプリケーションでは、ノードにもデータが含まれるグラフ（いわゆる「データグラフ」）が用いられており、観察者はデータ値の等価性または不等性をテストできます（例えば、ノードの属性「名前」がすべての隣接ノードの属性と異なることを要求するなど）。本研究は、データグラフ上の「データを考慮した」バイシミュレーションに関する初の研究です。私たちは、推移閉包演算子の有無にかかわらず、XPath（PDLなどの様相論理にデータの等価性テストを拡張した言語）の観測的識別不能性に基づいて、このようなバイシミュレーションを計算する問題を研究します。我々は、一般にこの問題がPSpace完全であることを示すが、問題の適切なパラメータ、すなわち許容される非局所性の量と考慮されるモデルのクラス(グラフ、DAG、ツリー)を制御することで、より良い計算量境界(coNP、PTime)をもたらすいくつかの制約を特定します。特に、この分析は扱いやすいフラグメントの階層を生成します。

From Skills to Symbols: Learning Symbolic Representations for Abstract High-Level Planning

From Skills to Symbols: Learning Symbolic Representations for Abstract High-Level Planning / スキルからシンボルへ：抽象的高レベルプランニングのための記号表現の学習

We consider the problem of constructing abstract representations for planning in high-dimensional, continuous environments. We assume an agent equipped with a collection of high-level actions, and construct representations provably capable of evaluating plans composed of sequences of those actions. We first consider the deterministic planning case, and show that the relevant computation involves set operations performed over sets of states. We define the specific collection of sets that is necessary and sufficient for planning, and use them to construct a grounded abstract symbolic representation that is provably suitable for deterministic planning. The resulting representation can be expressed in PDDL, a canonical high-level planning domain language; we construct such a representation for the Playroom domain and solve it in milliseconds using an off-the-shelf planner. We then consider probabilistic planning, which we show requires generalizing from sets of states to distributions over states. We identify the specific distributions required for planning, and use them to construct a grounded abstract symbolic representation that correctly estimates the expected reward and probability of success of any plan. In addition, we show that learning the relevant probability distributions corresponds to specific instances of probabilistic density estimation and probabilistic classification. We construct an agent that autonomously learns the correct abstract representation of a computer game domain, and rapidly solves it. Finally, we apply these techniques to create a physical robot system that autonomously learns its own symbolic representation of a mobile manipulation task directly from sensorimotor data—point clouds, map locations, and joint angles—and then plans using that representation. Together, these results establish a principled link between high-level actions and abstract representations, a concrete theoretical foundation for constructing abstract representations with provable properties, and a practical mechanism for autonomously learning abstract high-level representations.

我々は、高次元の連続環境における計画のための抽象表現を構築する問題について考える。高レベルの行動の集合を備えたエージェントを想定し、それらの行動のシーケンスで構成される計画を評価できることが証明されている表現を構築します。まず、決定論的計画のケースを考え、関連する計算には状態の集合に対して実行される集合演算が含まれることを示す。我々は、計画に必要かつ十分な特定の集合の集合を定義し、それらを用いて、決定論的計画に適していることが証明されている、根拠のある抽象的な記号表現を構築します。結果として得られる表現は、標準的な高水準計画ドメイン言語であるPDDLで表現できます。我々はプレイルームドメインに対してそのような表現を構築し、市販のプランナーを用いて数ミリ秒でそれを解きます。次に確率的プランニングを検討し、状態集合から状態上の分布への一般化が必要であることを示します。プランニングに必要な特定の分布を特定し、それらを用いて、あらゆるプランの期待報酬と成功確率を正しく推定する、グラウンディングされた抽象的な記号表現を構築します。さらに、関連する確率分布の学習が、確率的密度推定と確率的分類の具体的な例に対応することを示します。我々は、コンピュータゲームドメインの正しい抽象表現を自律的に学習し、それを迅速に解くエージェントを構築します。最後に、これらの手法を適用し、点群、地図上の位置、関節角度などの感覚運動データから直接、モバイル操作タスクの独自の記号表現を自律的に学習し、その表現を用いてプランニングを行う物理ロボットシステムを作成します。これらの結果は、高水準アクションと抽象表現との間の原理的なつながり、証明可能な特性を持つ抽象表現を構築するための具体的な理論的基礎、そして抽象的な高水準表現を自律的に学習するための実用的なメカニズムを確立します。

Linear Satisfiability Preserving Assignments

Linear Satisfiability Preserving Assignments / 線形充足可能性保存割り当て

In this paper, we study several classes of satisfiability preserving assignments to the constraint satisfaction problem (CSP). In particular, we consider fixable, autark and satisfying assignments. Since it is in general NP-hard to find a nontrivial (i.e., nonempty) satisfiability preserving assignment, we introduce linear satisfiability preserving assignments, which are defined by polyhedral cones in an associated vector space. The vector space is obtained by the identification, introduced by Kullmann, of assignments with real vectors. We consider arbitrary polyhedral cones, where only restricted classes of cones for autark assignments are considered in the literature. We reveal that cones in certain classes are maximal as a convex subset of the set of the associated vectors, which can be regarded as extensions of Kullmann’s results for autark assignments of CNFs. As algorithmic results, we present a pseudo-polynomial time algorithm that computes a linear fixable assignment for a given integer linear system, which implies the well known pseudo-polynomial solvability for integer linear systems such as two-variable-per-inequality (TVPI), Horn and q-Horn systems.

本稿では、制約充足問題（CSP）に対する充足可能性保存割り当てのいくつかのクラスを検討します。特に、固定可能割り当て、自明でない割り当て、および満足割り当てを検討します。一般に、自明でない（すなわち空でない）充足可能性保存割り当てを見つけることはNP困難であるため、関連するベクトル空間内の多面体錐によって定義される線形充足可能性保存割り当てを導入します。ベクトル空間は、Kullmannによって導入された、実ベクトルを持つ割り当ての同一視によって得られます。文献では自明でない割り当てに対する錐のクラスは限定されているが、本稿では任意の多面体錐を検討します。特定のクラスの錐は、関連するベクトルの集合の凸部分集合として最大となることを明らかにします。これは、CNFのオーターク割り当てに関するKullmannの結果の拡張とみなすことができます。アルゴリズムの結果として、与えられた整数線形システムに対する線形固定割り当てを計算する擬多項式時間アルゴリズムを提示します。これは、2変数パー不等式（TVPI）、ホーンシステム、qホーンシステムなどの整数線形システムに対するよく知られた擬多項式可解性を意味します。

KABouM: Knowledge-Level Action and Bounding Geometry Motion Planner

KABouM: Knowledge-Level Action and Bounding Geometry Motion Planner / KABouM：知識レベル動作および境界幾何学動作プランナー

For robots to solve real world tasks, they often require the ability to reason about both symbolic and geometric knowledge. We present a framework, called KABouM, for integrating knowledge-level task planning and motion planning in a bounding geometry. By representing symbolic information at the knowledge level, we can model incomplete information, sensing actions and information gain; by representing all geometric entities–objects, robots and swept volumes of motions–by sets of convex polyhedra, we can efficiently plan manipulation actions and raise reasoning about geometric predicates, such as collisions, to the symbolic level. At the geometric level, we take advantage of our bounded convex decomposition and swept volume computation with quadratic convergence, and fast collision detection of convex bodies. We evaluate our approach on a wide set of problems using real robots, including tasks with multiple manipulators, sensing and branched plans, and mobile manipulation.

ロボットが現実世界のタスクを解決するには、多くの場合、記号的知識と幾何学的知識の両方について推論する能力が必要です。本稿では、知識レベルのタスク計画と動作計画を境界幾何学に統合するKABouMと呼ばれるフレームワークを提示します。記号情報を知識レベルで表現することで、不完全情報、センシング動作、情報ゲインをモデル化できます。また、物体、ロボット、動作のスイープボリュームといったすべての幾何学的実体を凸多面体の集合で表現することで、操作動作を効率的に計画し、衝突などの幾何学的述語に関する推論を記号レベルにまで高めることができます。幾何学レベルでは、境界付き凸分解、二次収束を伴うスイープボリューム計算、そして凸体の高速衝突検出を活用します。本稿では、複数のマニピュレータ、センシングおよび分岐計画、モバイル操作といったタスクを含む、実際のロボットを用いた幅広い問題において、本手法を評価します。

Actively Estimating Crowd Annotation Consensus

Actively Estimating Crowd Annotation Consensus / 群衆注釈合意の能動的推定

The rapid growth of storage capacity and processing power has caused machine learning applications to increasingly rely on using immense amounts of labeled data. It has become more important than ever to have fast and inexpensive ways to annotate vast amounts of data. With the emergence of crowdsourcing services, the research direction has gravitated toward putting the wisdom of crowds to better use. Unfortunately, spammers and inattentive annotators pose a threat to the quality and trustworthiness of the consensus. Thus, high quality consensus estimation from crowd annotated data requires a meticulous choice of the candidate annotator and the sample in need of a new annotation. Due to time and budget limitations, it is of utmost importance that this choice is carried out while the annotation collection is in progress. We call this process active crowd-labeling. To this end, we propose an active crowd-labeling approach for actively estimating consensus from continuous-valued crowd annotations. Our method is based on annotator models with unknown parameters, and Bayesian inference is employed to reach a consensus in the form of ordinal, binary, or continuous values. We introduce ranking functions for choosing the candidate annotator and sample pair for requesting an annotation. In addition, we propose a penalizing method for preventing annotator domination, investigate the explore-exploit trade-off for incorporating new annotators into the system, and study the effects of inducing a stopping criterion based on consensus quality. We also introduce the crowd-labeled Head Pose Annotations datasets. Experimental results on the benchmark datasets used in the literature and the Head Pose Annotations datasets suggest that our method provides high-quality consensus by using as few as one fifth of the annotations (~80% cost reduction), thereby providing a budget and time-sensitive solution to the crowd-labeling problem.

ストレージ容量と処理能力の急速な向上により、機械学習アプリケーションは膨大な量のラベル付きデータの使用にますます依存するようになっています。膨大な量のデータに迅速かつ低コストでアノテーションを施す手段が、これまで以上に重要になっています。クラウドソーシングサービスの出現により、研究の方向性は群衆の知恵をより有効に活用することへと傾いています。しかしながら、スパマーや不注意なアノテーターは、コンセンサスの質と信頼性を脅かします。そのため、クラウドアノテーションデータから高品質なコンセンサス推定を行うには、候補となるアノテーターと新しいアノテーションを必要とするサンプルを慎重に選定する必要があります。時間と予算の制約があるため、この選定はアノテーション収集の進行中に行うことが極めて重要です。私たちはこのプロセスをアクティブクラウドラベリングと呼びます。この目的のために、連続値を持つクラウドアノテーションからアクティブにコンセンサスを推定するアクティブクラウドラベリング手法を提案します。この手法は、未知のパラメータを持つアノテーターモデルに基づいており、ベイズ推論を用いて順序値、2値、または連続値の形でコンセンサスを形成します。アノテーションを依頼する候補となるアノテーターとサンプルのペアを選択するためのランキング関数を導入します。さらに、アノテーターの支配を防ぐためのペナルティ法を提案し、新しいアノテーターをシステムに組み込むための探索と活用のトレードオフを調査し、コンセンサス品質に基づいて停止基準を誘発する効果を研究します。また、クラウドラベル付きのHead Pose Annotationsデータセットも紹介します。文献で使用されているベンチマークデータセットとHead Pose Annotationsデータセットでの実験結果は、私たちの方法がわずか5分の1のアノテーションを使用して高品質のコンセンサスを提供することを示唆しており(~80%のコスト削減)、それによってクラウドラベリング問題に対する予算と時間に敏感なソリューションを提供します。

Cycles and Intractability in a Large Class of Aggregation Rules

Cycles and Intractability in a Large Class of Aggregation Rules / 大規模な集約ルールクラスにおけるサイクルと扱いにくさ

We introduce the (j,k)-Kemeny rule — a generalization of Kemeny’s voting rule that aggregates j-chotomous weak orders into a k-chotomous weak order. Special cases of (j,k)-Kemeny include approval voting, the mean rule and Borda mean rule, as well as the Borda count and plurality voting. Why, then, is the winner problem computationally tractable for each of these other rules, but intractable for Kemeny? We show that intractability of winner determination for the (j,k)-Kemeny rule first appears at the j=3, k=3 level. The proof rests on a reduction of max cut to a related problem on weighted tournaments, and reveals that computational complexity arises from the cyclic part in the fundamental decomposition of a weighted tournament into cyclic and cocyclic components. Thus the existence of majority cycles — the engine driving both Arrow’s impossibility theorem and the Gibbard-Satterthwaite theorem — also serves as a source of computational complexity in social choice.

(j,k)-Kemenyルールを紹介します。これは、j値弱順序をk値弱順序に集約するKemenyの投票ルールの一般化です。(j,k)-Kemenyの特殊なケースには、承認投票、平均ルール、Borda平均ルール、Bordaカウント、多数決投票などがあります。では、なぜ勝者問題は他のルールでは計算的に扱いやすいのに、ケメニールールでは扱いにくいのでしょうか？(j,k)-ケメニールールの勝者決定の扱いにくさは、j=3、k=3のレベルで初めて現れることを示します。証明は、最大カットを重み付きトーナメントの関連問題に縮減することに基づいており、重み付きトーナメントを巡回要素と共巡回要素に根本的に分解する際の巡回要素から計算複雑性が生じることを明らかにし、このように、アローの不可能定理とギバード＝サッタースウェイト定理の両方の原動力となる多数決サイクルの存在は、社会的選択における計算複雑性の源泉としても機能します。

Coordinating Measurements in Uncertain Participatory Sensing Settings

Coordinating Measurements in Uncertain Participatory Sensing Settings / 不確実な参加型センシング環境における測定の調整

Environmental monitoring allows authorities to understand the impact of potentially harmful phenomena, such as air pollution, excessive noise, and radiation. Recently, there has been considerable interest in participatory sensing as a paradigm for such large-scale data collection because it is cost-effective and able to capture more fine-grained data than traditional approaches that use stationary sensors scattered in cities. In this approach, ordinary citizens (non-expert contributors) collect environmental data using low-cost mobile devices. However, these participants are generally self-interested actors that have their own goals and make local decisions about when and where to take measurements. This can lead to highly inefficient outcomes, where observations are either taken redundantly or do not provide sufficient information about key areas of interest. To address these challenges, it is necessary to guide and to coordinate participants, so they take measurements when it is most informative. To this end, we develop a computationally-efficient coordination algorithm (adaptive Best-Match) that suggests to users when and where to take measurements. Our algorithm exploits probabilistic knowledge of human mobility patterns, but explicitly considers the uncertainty of these patterns and the potential unwillingness of people to take measurements when requested to do so. In particular, our algorithm uses a local search technique, clustering and random simulations to map participants to measurements that need to be taken in space and time. We empirically evaluate our algorithm on a real-world human mobility and air quality dataset and show that it outperforms the current state of the art by up to 24% in terms of utility gained.

環境モニタリングは、大気汚染、過度の騒音、放射線といった潜在的に有害な現象の影響を当局が理解することを可能にします。近年、参加型センシングは、都市に散在する固定センサーを用いる従来のアプローチよりも費用対効果が高く、よりきめ細かいデータを取得できるため、大規模データ収集のパラダイムとして大きな関心を集めています。このアプローチでは、一般市民（専門家ではない参加者）が低価格のモバイルデバイスを用いて環境データを収集します。しかし、これらの参加者は一般的に利己的な主体であり、それぞれ独自の目標を持ち、いつどこで測定を行うかについて地域的な決定を下します。これは、観測が重複して行われたり、主要な関心領域に関する十分な情報が得られなかったりするなど、非常に非効率的な結果につながる可能性があります。これらの課題に対処するには、参加者を導き、調整することで、最も有益なタイミングで測定が行われるようにする必要があります。この目的のために、私たちは、ユーザーにいつどこで測定を行うべきかを提案する、計算効率の高い調整アルゴリズム（適応型ベストマッチ）を開発します。我々のアルゴリズムは、人間の移動パターンに関する確率的知識を活用しますが、これらのパターンの不確実性と、測定を求められても人々が測定を望まない可能性を明示的に考慮します。特に、我々のアルゴリズムは、局所探索技術、クラスタリング、ランダムシミュレーションを用いて、参加者を空間的および時間的に取得する必要がある測定にマッピングします。我々は、実世界の人間の移動と大気質のデータセットで我々のアルゴリズムを実証的に評価し、得られる効用に関して現在の最先端技術よりも最大24%優れていることを示しています。

Fact-Alternating Mutex Groups for Classical Planning

Fact-Alternating Mutex Groups for Classical Planning / 古典的プランニングのための事実交代ミューテックスグループ

Mutex groups are defined in the context of STRIPS planning as sets of facts out of which, maximally, one can be true in any state reachable from the initial state. The importance of computing and exploiting mutex groups was repeatedly pointed out in many studies. However, the theoretical analysis of mutex groups is sparse in current literature. This work provides a complexity analysis showing that inference of mutex groups is as hard as planning itself (PSPACE-Complete) and it also shows a tight relationship between mutex groups and graph cliques. This result motivates us to propose a new type of mutex group called a fact-alternating mutex group (fam-group) of which inference is NP-Complete. Moreover, we introduce an algorithm for the inference of fam-groups based on integer linear programming that is complete with respect to the maximal fam-groups and we demonstrate how beneficial fam-groups can be in the translation of planning tasks into finite domain representation. Finally, we show that fam-groups can be used for the detection of dead-end states and we propose a simple algorithm for the pruning of operators and facts as a preprocessing step that takes advantage of the properties of fam-groups. The experimental evaluation of the pruning algorithm shows a substantial increase in a number of solved tasks in domains from the optimal deterministic track of the last two planning competitions (IPC 2011 and 2014).

ミューテックスグループは、STRIPSプランニングの文脈において、初期状態から到達可能な任意の状態において最大で1つが真となり得る事実の集合として定義されます。ミューテックスグループの計算と活用の重要性は、多くの研究で繰り返し指摘されてきました。しかし、現在の文献ではミューテックスグループの理論的分析は乏しいです。本研究では、ミューテックスグループの推論がプランニング自体と同じくらい困難であることを示す複雑性分析を提供し（PSPACE-Complete）、ミューテックスグループとグラフクリークの間に密接な関係があることも示しています。この結果から、推論がNP完全であるファクト交代ミューテックスグループ（famグループ）と呼ばれる新しいタイプのミューテックスグループを提案することにしました。さらに、最大famグループに関して完全な整数線形計画法に基づくfamグループの推論アルゴリズムを導入し、プランニングタスクを有限領域表現に変換するときにfamグループがいかに有益であるかを示します。最後に、famグループが行き止まり状態の検出に使用できることを示し、famグループの特性を利用する前処理手順として演算子とファクトの枝刈りを行う単純なアルゴリズムを提案します。枝刈りアルゴリズムの実験的評価では、過去2回のプランニングコンペティション（IPC 2011および2014）の最適決定論的トラックからの領域で解決されたタスクの数が大幅に増加しました。

Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents

Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents / アーケード学習環境の再考：一般エージェントの評価プロトコルと未解決問題

The Arcade Learning Environment (ALE) is an evaluation platform that poses the challenge of building AI agents with general competency across dozens of Atari 2600 games. It supports a variety of different problem settings and it has been receiving increasing attention from the scientific community, leading to some high-profile success stories such as the much publicized Deep Q-Networks (DQN). In this article we take a big picture look at how the ALE is being used by the research community. We show how diverse the evaluation methodologies in the ALE have become with time, and highlight some key concerns when evaluating agents in the ALE. We use this discussion to present some methodological best practices and provide new benchmark results using these best practices. To further the progress in the field, we introduce a new version of the ALE that supports multiple game modes and provides a form of stochasticity we call sticky actions. We conclude this big picture look by revisiting challenges posed when the ALE was introduced, summarizing the state-of-the-art in various problems and highlighting problems that remain open.

アーケード学習環境（ALE）は、数十種類のAtari 2600ゲームで汎用的な能力を持つAIエージェントを構築するという課題を提起する評価プラットフォームです。ALEは多様な問題設定をサポートし、科学界からの注目を集めており、広く報道されたDeep Q-Networks（DQN）などの著名な成功事例につながっています。本稿では、研究コミュニティにおけるALEの活用状況を概観します。ALEの評価手法が時間の経過とともにどのように多様化してきたかを示し、ALEでエージェントを評価する際の重要な懸念事項を浮き彫りにします。この議論に基づき、いくつかの方法論的ベストプラクティスを提示し、これらのベストプラクティスを用いた新たなベンチマーク結果を提供します。この分野のさらなる進歩のため、複数のゲームモードをサポートし、スティッキーアクションと呼ばれる一種の確率性を提供するALEの新バージョンを紹介します。最後に、ALE導入時に提起された課題を再検討し、様々な問題における最先端技術をまとめ、未解決の課題を明らかにして、この概観を締めくくります。

On the Behavior of Convolutional Nets for Feature Extraction

On the Behavior of Convolutional Nets for Feature Extraction / 特徴抽出のための畳み込みネットの挙動について

Deep neural networks are representation learning techniques. During training, a deep net is capable of generating a descriptive language of unprecedented size and detail in machine learning. Extracting the descriptive language coded within a trained CNN model (in the case of image data), and reusing it for other purposes is a field of interest, as it provides access to the visual descriptors previously learnt by the CNN after processing millions of images, without requiring an expensive training phase. Contributions to this field (commonly known as feature representation transfer or transfer learning) have been purely empirical so far, extracting all CNN features from a single layer close to the output and testing their performance by feeding them to a classifier. This approach has provided consistent results, although its relevance is limited to classification tasks. In a completely different approach, in this paper we statistically measure the discriminative power of every single feature found within a deep CNN, when used for characterizing every class of 11 datasets. We seek to provide new insights into the behavior of CNN features, particularly the ones from convolutional layers, as this can be relevant for their application to knowledge representation and reasoning. Our results confirm that low and middle level features may behave differently to high level features, but only under certain conditions. We find that all CNN features can be used for knowledge representation purposes both by their presence or by their absence, doubling the information a single CNN feature may provide. We also study how much noise these features may include, and propose a thresholding approach to discard most of it. All these insights have a direct application to the generation of CNN embedding spaces.

ディープニューラルネットワークは表現学習技術です。ディープネットワークは学習中に、機械学習において前例のない規模と詳細さを持つ記述言語を生成することができます。学習済みのCNNモデル（画像データの場合）内にコード化された記述言語を抽出し、他の目的で再利用することは、CNNが数百万枚の画像を処理した後に学習した視覚記述子に、高価な学習フェーズを必要とせずにアクセスできるため、興味深い分野です。この分野（一般に特徴表現転移または転移学習として知られています）への貢献は、これまでのところ純粋に経験的なものであり、出力に近い単一の層からすべてのCNN特徴を抽出し、それらを分類器に入力してその性能をテストしてきました。このアプローチは一貫した結果をもたらしていますが、その関連性は分類タスクに限定されています。本論文では全く異なるアプローチとして、11のデータセットのすべてのクラスを特徴付ける際にディープCNN内で発見されたすべての特徴の識別力を統計的に測定します。CNN特徴、特に畳み込み層の特徴の挙動に関する新たな知見を提供することを目指します。これは、知識表現と推論への応用において重要な意味を持つ可能性があるためです。得られた結果は、低レベルおよび中レベルの特徴は高レベルの特徴とは異なる挙動を示す可能性があることを確認しましたが、これは特定の条件下でのみ可能です。すべてのCNN特徴は、その存在の有無にかかわらず知識表現に利用可能であり、単一のCNN特徴が提供できる情報を倍増させることが分かりました。また、これらの特徴に含まれるノイズの量を調査し、そのほとんどを除去する閾値化アプローチを提案します。これらの知見はすべて、CNN埋め込み空間の生成に直接応用できます。

Fully Observable Non-deterministic Planning as Assumption-Based Reactive Synthesis

Fully Observable Non-deterministic Planning as Assumption-Based Reactive Synthesis / 仮定に基づくリアクティブ合成としての完全観測非決定性プランニング

We contribute to recent efforts in relating two approaches to automatic synthesis, namely, automated planning and discrete reactive synthesis. First, we develop a declarative characterization of the standard “fairness” assumption on environments in non-deterministic planning, and show that strong-cyclic plans are correct solution concepts for fair environments. This complements, and arguably completes, the existing foundational work on non-deterministic planning, which focuses on characterizing (and computing) plans enjoying special “structural” properties, namely loopy but closed policy structures. Second, we provide an encoding suitable for reactive synthesis that avoids the naive exponential state space blowup. To do so, special care has to be taken to specify the fairness assumption on the environment in a succinct manner.

我々は、自動合成への2つのアプローチ、すなわち自動プランニングと離散リアクティブ合成を関連付ける最近の研究に貢献します。まず、非決定性プランニングにおける環境に関する標準的な「公平性」仮定の宣言的特性評価を開発し、公平な環境に対する正しい解概念として、強巡回プランが用いられることを示します。これは、非決定性計画に関する既存の基礎研究を補完し、さらには完成させるものと言えるでしょう。この研究は、ループ状でありながら閉じた方策構造といった特別な「構造的」特性を持つ計画を特徴づけ（そして計算すること）することに焦点を当てています。第二に、我々は、ナイーブな指数関数的状態空間爆発を回避する、リアクティブ合成に適した符号化方式を提供します。そのためには、環境における公平性仮定を簡潔に指定するために特別な注意を払う必要があります。

Distributed Constraint Optimization Problems and Applications: A Survey

Distributed Constraint Optimization Problems and Applications: A Survey / 分散制約最適化問題とその応用：サーベイ

The field of multi-agent system (MAS) is an active area of research within artificial intelligence, with an increasingly important impact in industrial and other real-world applications. In a MAS, autonomous agents interact to pursue personal interests and/or to achieve common objectives. Distributed Constraint Optimization Problems (DCOPs) have emerged as a prominent agent model to govern the agents’ autonomous behavior, where both algorithms and communication models are driven by the structure of the specific problem. During the last decade, several extensions to the DCOP model have been proposed to enable support of MAS in complex, real-time, and uncertain environments.This survey provides an overview of the DCOP model, offering a classification of its multiple extensions and addressing both resolution methods and applications that find a natural mapping within each class of DCOPs. The proposed classification suggests several future perspectives for DCOP extensions and identifies challenges in the design of efficient resolution algorithms, possibly through the adaptation of strategies from different areas.

マルチエージェントシステム（MAS）は、人工知能の研究において活発な分野であり、産業分野をはじめとする実世界への応用においてますます重要な影響を与えています。MASでは、自律エージェントが個々の関心事を追求したり、共通の目的を達成したりするために相互作用します。分散制約最適化問題（DCOP）は、エージェントの自律的な行動を制御するための重要なエージェントモデルとして登場しました。DCOPでは、アルゴリズムと通信モデルの両方が、特定の問題の構造によって駆動されます。過去10年間で、複雑でリアルタイムかつ不確実な環境におけるMASのサポートを可能にするために、DCOPモデルの拡張がいくつか提案されてきました。本調査では、DCOPモデルの概要を示し、その複数の拡張を分類し、各DCOPクラス内で自然なマッピングを見つける解決方法とアプリケーションの両方を取り上げます。提案された分類は、DCOP拡張の将来の展望をいくつか示唆し、異なる分野の戦略を適応させることなどを通じて、効率的な解決アルゴリズムの設計における課題を明らかにします。

Survey of the State of the Art in Natural Language Generation: Core tasks, applications and evaluation

Survey of the State of the Art in Natural Language Generation: Core tasks, applications and evaluation / 最先端技術のサーベイ自然言語生成におけるコアタスク、応用、評価

This paper surveys the current state of the art in Natural Language Generation (NLG), defined as the task of generating text or speech from non-linguistic input. A survey of NLG is timely in view of the changes that the field has undergone over the past two decades, especially in relation to new (usually data-driven) methods, as well as new applications of NLG technology. This survey therefore aims to (a) give an up-to-date synthesis of research on the core tasks in NLG and the architectures adopted in which such tasks are organised; (b) highlight a number of recent research topics that have arisen partly as a result of growing synergies between NLG and other areas of artificial intelligence; (c) draw attention to the challenges in NLG evaluation, relating them to similar challenges faced in other areas of NLP, with an emphasis on different evaluation methods and the relationships between them.

この論文では、自然言語生成(NLG)の現在の最先端技術について概説します。NLGは、非言語入力からテキストまたは音声を生成するタスクと定義されます。過去20年間にこの分野が経験した変化、特に新しい(通常はデータ駆動型の)手法やNLG技術の新しいアプリケーションを考慮すると、NLGの概説は時宜を得たものです。したがって、この概説の目的は、(a) NLGの中核タスクとそのようなタスクを編成するために採用されているアーキテクチャに関する研究の最新の統合を提供すること、(b) NLGと他の人工知能分野との相乗効果が高まった結果として部分的に浮上したいくつかの最近の研究トピックを強調すること、(c) NLG評価における課題に注目し、それらをNLPの他の分野で直面している同様の課題と関連付け、異なる評価方法とそれらの間の関係に重点を置くことです。

Trust as a Precursor to Belief Revision

Trust as a Precursor to Belief Revision / 信念修正の前兆としての信頼

Belief revision is concerned with incorporating new information into a pre-existing set of beliefs. When the new information comes from another agent, we must first determine if that agent should be trusted. In this paper, we define trust as a pre-processing step before revision. We emphasize that trust in an agent is often restricted to a particular domain of expertise. We demonstrate that this form of trust can be captured by associating a state partition with each agent, then relativizing all reports to this partition before revising. We position the resulting family of trust-sensitive revision operators within the class of selective revision operators of Ferme and Hansson, and we prove a representation result that characterizes the class of trust-sensitive revision operators in terms of a set of postulates. We also show that trust-sensitive revision is manipulable, in the sense that agents can sometimes have incentive to pass on misleading information.

信念の修正は、新しい情報を既存の信念セットに組み込むことに関係しています。新しい情報が他のエージェントから来た場合、まずそのエージェントを信頼すべきかどうかを判断する必要があります。本稿では、信頼を、修正前の前処理ステップと定義します。エージェントへの信頼は、多くの場合、特定の専門分野に限定されることを強調します。この形態の信頼は、各エージェントに状態パーティションを関連付け、修正前にすべての報告をこのパーティションに相対化することで捉えられることを示します。得られた信頼に敏感な修正演算子の族を、FermeとHanssonの選択的修正演算子のクラスに位置付け、一連の公理を用いて信頼に敏感な修正演算子のクラスを特徴付ける表現結果を証明します。また、信頼に敏感な修正は、エージェントが誤解を招く情報を伝達するインセンティブを持つ場合があるという意味で、操作可能であることも示します。

When Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases

When Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases / 部分グラフ同型性が本当に難しい場合、そしてそれがグラフデータベースにとってなぜ重要なのか

The subgraph isomorphism problem involves deciding whether a copy of a pattern graph occurs inside a larger target graph. The non-induced version allows extra edges in the target, whilst the induced version does not. Although both variants are NP-complete, algorithms inspired by constraint programming can operate comfortably on many real-world problem instances with thousands of vertices. However, they cannot handle arbitrary instances of this size. We show how to generate “really hard” random instances for subgraph isomorphism problems, which are computationally challenging with a couple of hundred vertices in the target, and only twenty pattern vertices. For the non-induced version of the problem, these instances lie on a satisfiable / unsatisfiable phase transition, whose location we can predict; for the induced variant, much richer behaviour is observed, and constrainedness gives a better measure of difficulty than does proximity to a phase transition. These results have practical consequences: we explain why the widely researched “filter / verify” indexing technique used in graph databases is founded upon a misunderstanding of the empirical hardness of NP-complete problems, and cannot be beneficial when paired with any reasonable subgraph isomorphism algorithm.

部分グラフ同型性問題は、パターングラフのコピーがより大きなターゲットグラフ内に存在するかどうかを判断することです。非誘導バージョンではターゲットに追加のエッジが許容されますが、誘導バージョンでは許容されません。どちらの変種もNP完全ですが、制約プログラミングに着想を得たアルゴリズムは、数千の頂点を持つ多くの現実世界の問題のインスタンスに対して快適に動作します。しかし、このサイズの任意のインスタンスを扱うことはできません。本稿では、対象が数百の頂点でパターン頂点がわずか20個しかない計算量の多い部分グラフ同型性問題に対して、「非常に難しい」ランダムインスタンスを生成する方法を示します。この問題の非誘導バージョンでは、これらのインスタンスは充足可能/充足不可能な相転移上にあり、その位置は予測可能です。一方、誘導バージョンでは、はるかに豊富な挙動が観察され、制約の有無は相転移への近さよりも優れた難易度の尺度となります。これらの結果は実用的な意味を持ちます。グラフデータベースで広く研究されている「フィルタ/検証」インデックス作成手法が、NP完全問題の経験的困難性に関する誤解に基づいており、合理的な部分グラフ同型性アルゴリズムと組み合わせても有益ではない理由を説明します。

Rademacher Complexity Bounds for a Penalized Multi-class Semi-supervised Algorithm

Rademacher Complexity Bounds for a Penalized Multi-class Semi-supervised Algorithm / ペナルティ付き多クラス半教師ありアルゴリズムのRademacher計算量限界

We propose Rademacher complexity bounds for multi-class classifiers trained with a two-step semi-supervised model. In the first step, the algorithm partitions the partially labeled data and then identifies dense clusters containing k predominant classes using the labeled training examples such that the proportion of their non-predominant classes is below a fixed threshold stands for clustering consistency. In the second step, a classifier is trained by minimizing a margin empirical loss over the labeled training set and a penalization term measuring the disability of the learner to predict the k predominant classes of the identified clusters. The resulting data-dependent generalization error bound involves the margin distribution of the classifier, the stability of the clustering technique used in the first step and Rademacher complexity terms corresponding to partially labeled training data. Our theoretical result exhibit convergence rates extending those proposed in the literature for the binary case, and experimental results on different multi-class classification problems show empirical evidence that supports the theory.

2段階半教師ありモデルを用いて学習された多クラス分類器のラデマッハ複雑度境界を提案します。第1段階では、アルゴリズムは部分的にラベル付けされたデータを分割し、ラベル付けされた学習例を用いて、k個の主要クラスを含む密なクラスターを同定します。この際、非主要クラスの割合がクラスタリングの一貫性を示す一定の閾値を下回る。第2段階では、ラベル付けされた学習セット全体にわたるマージン経験的損失と、学習者が同定されたクラスターのk個の主要クラスを予測する能力の低さを測定するペナルティ項を最小化するように分類器を学習します。結果として得られるデータ依存の汎化誤差境界には、分類器のマージン分布、第1段階で使用されたクラスタリング手法の安定性、および部分的にラベル付けされた学習データに対応するラデマッハ複雑度項が含まれます。我々の理論的結果は、文献で提案されている2値ケースの収束速度を拡張する収束速度を示し、様々な多クラス分類問題における実験結果は、この理論を裏付ける経験的証拠を示しています。

Symbol Grounding Association in Multimodal Sequences with Missing Elements

Symbol Grounding Association in Multimodal Sequences with Missing Elements / 欠損要素を含むマルチモーダルシーケンスにおけるシンボルグラウンディング関連付け

In this paper, we extend a symbolic association framework for being able to handle missing elements in multimodal sequences. The general scope of the work is the symbolic associations of object-word mappings as it happens in language development in infants. In other words, two different representations of the same abstract concepts can associate in both directions. This scenario has been long interested in Artificial Intelligence, Psychology, and Neuroscience. In this work, we extend a recent approach for multimodal sequences (visual and audio) to also cope with missing elements in one or both modalities. Our method uses two parallel Long Short-Term Memories (LSTMs) with a learning rule based on EM-algorithm. It aligns both LSTM outputs via Dynamic Time Warping (DTW). We propose to include an extra step for the combination with the max operation for exploiting the common elements between both sequences. The motivation behind is that the combination acts as a condition selector for choosing the best representation from both LSTMs. We evaluated the proposed extension in the following scenarios: missing elements in one modality (visual or audio) and missing elements in both modalities (visual and sound). The performance of our extension reaches better results than the original model and similar results to individual LSTM trained in each modality.

本稿では、マルチモーダルシーケンスにおける欠落要素の処理を可能にするため、記号連想フレームワークを拡張します。本研究の一般的な対象は、乳児の言語発達において見られるような、オブジェクトと単語のマッピングにおける記号的な連想です。言い換えれば、同じ抽象概念の2つの異なる表現が双方向で連想され得る。このシナリオは、人工知能、心理学、神経科学において長年関心を集めてきた。本研究では、マルチモーダルシーケンス（視覚と音声）に対する最近のアプローチを拡張し、一方または両方のモダリティにおける欠落要素にも対処できるようにします。本手法では、EMアルゴリズムに基づく学習規則を用いて、2つの並列なLong Short-Term Memories（LSTM）を使用します。両LSTM出力はDynamic Time Warping（DTW）によって整合されます。両シーケンス間の共通要素を活用するため、最大演算との組み合わせに新たなステップを追加することを提案します。その背後にある動機は、組み合わせが、両方のLSTMから最適な表現を選択するための条件セレクターとして機能することです。提案された拡張を、1つのモダリティ(視覚または音声)で要素が欠落している場合と、両方のモダリティ(視覚と音声)で要素が欠落している場合の2つのシナリオで評価しました。この拡張のパフォーマンスは、元のモデルよりも優れた結果となり、各モダリティでトレーニングされた個々のLSTMと同等の結果となりました。

Belief Update within Propositional Fragments

Belief Update within Propositional Fragments / 命題フラグメント内の信念更新

Belief change within the framework of fragments of propositional logic is one of the main and recent challenges in the knowledge representation research area. While previous research works focused on belief revision, belief merging, and belief contraction, the problem of belief update within fragments of classical logic has not been addressed so far. In the context of revision, it has been proposed to refine existing operators so that they operate within propositional fragments, and that the result of revision remains in the fragment under consideration. This approach is not restricted to the Horn fragment but also applicable to other propositional fragments like Krom and affine fragments. We generalize this notion of refinement to any belief change operator. We then focus on a specific belief change operation, namely belief update. We investigate the behavior of the refined update operators with respect to satisfaction of the KM postulates and highlight differences between revision and update in this context.

命題論理のフラグメントのフレームワーク内での信念の変更は、知識表現研究分野における主要かつ最近の課題の1つです。これまでの研究では、信念の修正、信念のマージ、信念の縮小に焦点が当てられてきましたが、古典論理のフラグメント内での信念の更新の問題はこれまで取り上げられてきませんでした。修正の文脈では、既存の演算子を改良して命題フラグメント内で動作し、修正の結果が検討中のフラグメント内に残るようにすることが提案されています。このアプローチはHornフラグメントに限定されず、Kromフラグメントやアフィンフラグメントなどの他の命題フラグメントにも適用できます。この改良の概念をあらゆる信念変更演算子に一般化します。次に、信念変更操作、つまり信念の更新に焦点を当てます。我々は、KM公理の充足に関して改良された更新演算子の挙動を調査し、このコンテキストにおける修正と更新の違いを明らかにします。

Corpus-Level Fine-Grained Entity Typing

Corpus-Level Fine-Grained Entity Typing / コーパスレベルの細粒度エンティティタイピング

Extracting information about entities remains an important research area. This paper addresses the problem of corpus-level entity typing, i.e., inferring from a large corpus that an entity is a member of a class, such as “food” or “artist”. The application of entity typing we are interested in is knowledge base completion, specifically, to learn which classes an entity is a member of. We propose FIGMENT to tackle this problem. FIGMENT is embedding-based and combines (i) a global model that computes scores based on global information of an entity and (ii) a context model that first evaluates the individual occurrences of an entity and then aggregates the scores.Each of the two proposed models has specific properties. For the global model, learning high-quality entity representations is crucial because it is the only source used for the predictions. Therefore, we introduce representations using the name and contexts of entities on the three levels of entity, word, and character. We show that each level provides complementary information and a multi-level representation performs best. For the context model, we need to use distant supervision since there are no context-level labels available for entities. Distantly supervised labels are noisy and this harms the performance of models. Therefore, we introduce and apply new algorithms for noise mitigation using multi-instance learning. We show the effectiveness of our models on a large entity typing dataset built from Freebase.

エンティティに関する情報の抽出は、依然として重要な研究分野です。本論文では、コーパスレベルのエンティティタイピング、すなわち大規模コーパスからエンティティが「食品」や「芸術家」などのクラスのメンバーであることを推論する問題を取り上げます。本論文で関心のあるエンティティタイピングの応用は、知識ベースの補完、具体的にはエンティティがどのクラスのメンバーであるかを学習することです。この問題に対処するために、FIGMENTを提案します。FIGMENTは埋め込みベースであり、(i)エンティティのグローバル情報に基づいてスコアを計算するグローバルモデルと、(ii)エンティティの個々の出現を最初に評価し、次にスコアを集計するコンテキストモデルを組み合わせています。提案された2つのモデルはそれぞれ固有の特性を持っています。グローバルモデルでは、予測に使用される唯一の情報源であるため、高品質なエンティティ表現を学習することが不可欠です。そこで、エンティティ、単語、文字の3つのレベルで、エンティティの名前とコンテキストを用いた表現を導入します。各レベルは補完的な情報を提供し、マルチレベル表現が最も優れたパフォーマンスを発揮することを示します。コンテキストモデルでは、エンティティにコンテキストレベルのラベルがないため、遠隔教師あり学習を使用する必要があります。遠隔教師あり学習のラベルはノイズが多く、モデルの性能を低下させます。そこで、マルチインスタンス学習を用いたノイズ軽減のための新しいアルゴリズムを導入し、適用します。Freebaseから構築された大規模なエンティティタイピングデータセットにおいて、本モデルの有効性を示します。

SMOTE for Learning from Imbalanced Data: Progress and Challenges, Marking the 15-year Anniversary

SMOTE for Learning from Imbalanced Data: Progress and Challenges, Marking the 15-year Anniversary / 不均衡データからの学習のためのSMOTE：15周年を迎えての進歩と課題

The Synthetic Minority Oversampling Technique (SMOTE) preprocessing algorithm is considered “de facto” standard in the framework of learning from imbalanced data. This is due to its simplicity in the design of the procedure, as well as its robustness when applied to different type of problems. Since its publication in 2002, SMOTE has proven successful in a variety of applications from several different domains. SMOTE has also inspired several approaches to counter the issue of class imbalance, and has also significantly contributed to new supervised learning paradigms, including multilabel classification, incremental learning, semi-supervised learning, multi-instance learning, among others. It is standard benchmark for learning from imbalanced data. It is also featured in a number of different software packages – from open source to commercial. In this paper, marking the fifteen year anniversary of SMOTE, we reflect on the SMOTE journey, discuss the current state of affairs with SMOTE, its applications, and also identify the next set of challenges to extend SMOTE for Big Data problems.

合成少数派オーバーサンプリング手法（SMOTE）の前処理アルゴリズムは、不均衡データからの学習の枠組みにおいて「事実上の」標準と見なされています。これは、手順の設計が単純であることと、様々な種類の問題に適用した場合の堅牢性によるものです。2002年の発表以来、SMOTEは様々な分野の様々なアプリケーションで成功を収めています。SMOTEは、クラス不均衡の問題に対処するための様々なアプローチにも影響を与え、マルチラベル分類、増分学習、半教師あり学習、マルチインスタンス学習など、新しい教師あり学習パラダイムにも大きく貢献しています。これは、不均衡データからの学習における標準的なベンチマークです。オープンソースから商用まで、さまざまなソフトウェアパッケージにも搭載されています。本稿では、SMOTE 15周年を記念し、SMOTEの歩みを振り返り、SMOTEの現状とその応用について議論するとともに、ビッグデータの問題にSMOTEを拡張するための今後の課題を特定します。

Visualisation and ‘Diagnostic Classifiers’ Reveal How Recurrent and Recursive Neural Networks Process Hierarchical Structure

Visualisation and ‘Diagnostic Classifiers’ Reveal How Recurrent and Recursive Neural Networks Process Hierarchical Structure / 可視化と「診断分類器」により、再帰型ニューラルネットワークと再帰型ニューラルネットワークが階層構造を処理する仕組みが明らかに

We investigate how neural networks can learn and process languages with hierarchical, compositional semantics. To this end, we define the artificial task of processing nested arithmetic expressions, and study whether different types of neural networks can learn to compute their meaning. We find that recursive neural networks can implement a generalising solution to this problem, and we visualise this solution by breaking it up in three steps: project, sum and squash. As a next step, we investigate recurrent neural networks, and show that a gated recurrent unit, that processes its input incrementally, also performs very well on this task: the network learns to predict the outcome of the arithmetic expressions with high accuracy, although performance deteriorates somewhat with increasing length. To develop an understanding of what the recurrent network encodes, visualisation techniques alone do not suffice. Therefore, we develop an approach where we formulate and test multiple hypotheses on the information encoded and processed by the network. For each hypothesis, we derive predictions about features of the hidden state representations at each time step, and train ‘diagnostic classifiers’ to test those predictions. Our results indicate that the networks follow a strategy similar to our hypothesised ‘cumulative strategy’, which explains the high accuracy of the network on novel expressions, the generalisation to longer expressions than seen in training, and the mild deterioration with increasing length. This in turn shows that diagnostic classifiers can be a useful technique for opening up the black box of neural networks. We argue that diagnostic classification, unlike most visualisation techniques, does scale up from small networks in a toy domain, to larger and deeper recurrent networks dealing with real-life data, and may therefore contribute to a better understanding of the internal dynamics of current state-of-the-art models in natural language processing.

ニューラルネットワークが階層的かつ構成的な意味を持つ言語をどのように学習し、処理できるかを調査します。この目的のために、ネストされた算術式を処理するという人工的なタスクを定義し、異なるタイプのニューラルネットワークがその意味を計算できるかどうかを調査します。再帰型ニューラルネットワークはこの問題に対する一般化ソリューションを実装できることがわかり、このソリューションを射影、合計、圧縮の3つのステップに分解して視覚化します。次のステップとして、我々はリカレントニューラルネットワークを調査し、入力を段階的に処理するゲート付きリカレントユニットが、このタスクにおいて非常に優れた性能を発揮することを示します。ネットワークは算術式の結果を高精度で予測することを学習しますが、長さが増加するにつれて性能は若干低下します。リカレントネットワークが何をエンコードしているかを理解するには、可視化技術だけでは不十分です。そこで我々は、ネットワークによってエンコードおよび処理される情報に関して複数の仮説を立て、検証する手法を開発しました。それぞれの仮説について、各時間ステップにおける隠れ状態表現の特徴に関する予測を導き出し、それらの予測を検証するための「診断分類器」を学習しました。結果は、ネットワークが我々の仮説である「累積戦略」に類似した戦略に従うことを示しており、これは新しい表現に対するネットワークの高い精度、学習時よりも長い表現への一般化、そして長さの増加に伴う緩やかな性能低下を説明しています。これは、診断分類器がニューラルネットワークのブラックボックスを解明するための有用な手法となり得ることを示しています。診断分類は、ほとんどの視覚化手法とは異なり、おもちゃの領域の小さなネットワークから、現実のデータを扱うより大規模で深い再帰型ネットワークまで拡張できるため、自然言語処理における現在の最先端モデルの内部ダイナミクスをより深く理解することに貢献する可能性があると私たちは主張します。

Pre-Wiring and Pre-Training: What Does a Neural Network Need to Learn Truly General Identity Rules?

Pre-Wiring and Pre-Training: What Does a Neural Network Need to Learn Truly General Identity Rules? / 事前配線と事前学習：ニューラルネットワークが真に一般的な同一性ルールを学習するには何が必要か？

In an influential paper (“Rule Learning by Seven-Month-Old Infants”), Marcus, Vijayan, Rao and Vishton claimed that connectionist models cannot account for human success at learning tasks that involved generalization of abstract knowledge such as grammatical rules. This claim triggered a heated debate, centered mostly around variants of the Simple Recurrent Network model. In our work, we revisit this unresolved debate and analyze the underlying issues from a different perspective. We argue that, in order to simulate human-like learning of grammatical rules, a neural network model should not be used as a tabula rasa, but rather, the initial wiring of the neural connections and the experience acquired prior to the actual task should be incorporated into the model. We present two methods that aim to provide such initial state: a manipulation of the initial connections of the network in a cognitively plausible manner (concretely, by implementing a “delay-line” memory), and a pre-training algorithm that incrementally challenges the network with novel stimuli. We implement such techniques in an Echo State Network (ESN), and we show that only when combining both techniques the ESN is able to learn truly general identity rules. Finally, we discuss the relation between these cognitively motivated techniques and recent advances in Deep Learning.

マーカス、ヴィジャヤン、ラオ、ヴィシュトンは、影響力のある論文「生後7ヶ月の乳児による規則学習」において、コネクショニストモデルは、文法規則のような抽象的知識の一般化を伴う学習課題における人間の成功を説明できないと主張しました。この主張は、主に単純再帰ネットワークモデルの亜種をめぐる激しい議論を引き起こしました。本研究では、この未解決の議論を再検討し、根底にある問題を別の視点から分析します。人間のような文法規則学習をシミュレートするためには、ニューラルネットワークモデルを白紙の状態ではなく、ニューラルネットワークの初期接続と実際の課題に先立つ経験をモデルに組み込む必要があると主張します。本研究では、そのような初期状態を提供することを目的とした2つの手法を提示します。1つは、ネットワークの初期接続を認知的に妥当な方法で操作する方法（具体的には「遅延線」メモリを実装する方法）であり、もう1つは、ネットワークに新しい刺激を段階的に与える事前学習アルゴリズムです。我々はこれらの手法をエコーステートネットワーク（ESN）に実装し、両方の手法を組み合わせた場合にのみ、ESNが真に一般的な識別規則を学習できることを示します。最後に、これらの認知的動機付け手法とディープラーニングにおける最近の進歩との関係について議論します。

From Feature To Paradigm: Deep Learning In Machine Translation

From Feature To Paradigm: Deep Learning In Machine Translation / 特徴からパラダイムへ：機械翻訳におけるディープラーニング

In the last years, deep learning algorithms have highly revolutionized several areas including speech, image and natural language processing. The speciﬁc ﬁeld of Machine Translation (MT) has not remained invariant. Integration of deep learning in MT varies from re-modeling existing features into standard statistical systems to the development of a new architecture. Among the diﬀerent neural networks, research works use feed-forward neural networks, recurrent neural networks and the encoder-decoder schema. These architectures are able to tackle challenges as having low-resources or morphology variations.This manuscript focuses on describing how these neural networks have been integrated to enhance diﬀerent aspects and models from statistical MT, including language modeling, word alignment, translation, reordering, and rescoring. Then, we report the new neural MT approach together with a description of the foundational related works and recent approaches on using subword, characters and training with multilingual languages, among others. Finally, we include an analysis of the corresponding challenges and future work in using deep learning in MT.

近年、ディープラーニングアルゴリズムは、音声、画像、自然言語処理を含むいくつかの分野に大きな革命をもたらしました。機械翻訳（MT）の特定の分野は不変ではありません。MTへのディープラーニングの統合は、既存の特徴を標準的な統計システムに再モデル化することから、新しいアーキテクチャの開発まで多岐にわたります。様々なニューラルネットワークの中でも、研究ではフィードフォワードニューラルネットワーク、リカレントニューラルネットワーク、エンコーダーデコーダースキーマが使用されています。これらのアーキテクチャは、リソース不足や形態素の変動などの課題に対処することができます。本稿では、これらのニューラルネットワークがどのように統合され、言語モデリング、単語アライメント、翻訳、並べ替え、再スコアリングなど、統計MTのさまざまな側面やモデルを強化してきたかについて説明することに焦点を当てています。次に、新しいニューラルMTアプローチについて報告するとともに、サブワード、文字、多言語言語を用いたトレーニングなどに関する基礎的な関連研究と最近のアプローチについても説明します。最後に、MTにおけるディープラーニングの活用における課題と今後の取り組みについて分析します。

参考文献

Journal of Artificial Intelligence Resarch Vol. 61 (2018)

論文