NP Animacy Identification for Anaphora Resolution
アナフォラ解決のためのNPアニマシー識別
In anaphora resolution for English, animacy identification can play an integral role in the application of agreement restrictions between pronouns and candidates, and as a result, can improve the accuracy of anaphora resolution systems. In this paper, two methods for animacy identification are proposed and evaluated using intrinsic and extrinsic measures. The first method is a rule-based one which uses information about the unique beginners in WordNet to classify NPs on the basis of their animacy. The second method relies on a machine learning algorithm which exploits a WordNet enriched with animacy information for each sense. The effect of word sense disambiguation on the two methods is also assessed. The intrinsic evaluation reveals that the machine learning method reaches human levels of performance. The extrinsic evaluation demonstrates that animacy identification can be beneficial in anaphora resolution, especially in the cases where animate entities are identified with high precision.
英語のアナフォラ解決において、有生物性識別は代名詞と候補の間の一致制約の適用において重要な役割を果たし、その結果、アナフォラ解決システムの精度を向上させることができます。本稿では、有生物性識別のための2つの方法を提案し、内的および外的尺度を使用して評価します。最初の方法は、WordNetの一意の初心者に関する情報を使用して、NPをその有生物性に基づいて分類するルールベースの方法です。2番目の方法は、各意味の有生物性情報で強化されたWordNetを活用する機械学習アルゴリズムに依存しています。語義の曖昧性解消が2つの方法に与える影響も評価します。内的評価により、機械学習法が人間のパフォーマンス レベルに達することが明らかになりました。外的評価では、特に生物エンティティが高精度で識別される場合に、有生物性識別がアナフォラ解決に有益であることを示しています。
Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling
ジョブショップスケジューリングのためのソリューション誘導型多点構成的探索
Solution-Guided Multi-Point Constructive Search (SGMPCS) is a novel constructive search technique that performs a series of resource-limited tree searches where each search begins either from an empty solution (as in randomized restart) or from a solution that has been encountered during the search. A small number of these “elite” solutions is maintained during the search. We introduce the technique and perform three sets of experiments on the job shop scheduling problem. First, a systematic, fully crossed study of SGMPCS is carried out to evaluate the performance impact of various parameter settings. Second, we inquire into the diversity of the elite solution set, showing, contrary to expectations, that a less diverse set leads to stronger performance. Finally, we compare the best parameter setting of SGMPCS from the first two experiments to chronological backtracking, limited discrepancy search, randomized restart, and a sophisticated tabu search algorithm on a set of well-known benchmark problems. Results demonstrate that SGMPCS is significantly better than the other constructive techniques tested, though lags behind the tabu search.
解誘導型多点構成的探索(SGMPCS)は、リソースが制限された一連の木探索を実行する新しい構成的探索手法です。各探索は、空の解（ランダム化リスタートの場合）から、または探索中に遭遇した解から開始されます。これらの「エリート」解のうち少数は、探索中に維持されます。この手法を紹介し、ジョブショップスケジューリング問題を対象に3つの実験を行いました。まず、SGMPCSの体系的な完全クロススタディを実施し、様々なパラメータ設定がパフォーマンスに与える影響を評価しました。次に、エリート解集合の多様性を調査し、予想に反して、多様性の低い集合の方がパフォーマンスが向上することを示しました。最後に、最初の2つの実験で得られたSGMPCSの最適なパラメータ設定を、時系列バックトラッキング、限定的矛盾探索、ランダム化リスタート、そして洗練されたタブー探索アルゴリズムと、一連のよく知られたベンチマーク問題で比較しました。結果は、SGMPCSがタブー探索には及ばないものの、テストした他の構成的手法よりも大幅に優れていることを示しています。
An Algebraic Graphical Model for Decision with Uncertainties, Feasibilities, and Utilities
不確実性、実現可能性、および効用を考慮した意思決定のための代数的グラフィカルモデル
Numerous formalisms and dedicated algorithms have been designed in the last decades to model and solve decision making problems. Some formalisms, such as constraint networks, can express “simple” decision problems, while others are designed to take into account uncertainties, unfeasible decisions, and utilities. Even in a single formalism, several variants are often proposed to model different types of uncertainty (probability, possibility…) or utility (additive or not). In this article, we introduce an algebraic graphical model that encompasses a large number of such formalisms: (1) we first adapt previous structures from Friedman, Chu and Halpern for representing uncertainty, utility, and expected utility in order to deal with generic forms of sequential decision making; (2) on these structures, we then introduce composite graphical models that express information via variables linked by “local” functions, thanks to conditional independence; (3) on these graphical models, we finally define a simple class of queries which can represent various scenarios in terms of observabilities and controllabilities. A natural decision-tree semantics for such queries is completed by an equivalent operational semantics, which induces generic algorithms. The proposed framework, called the Plausibility-Feasibility-Utility (PFU) framework, not only provides a better understanding of the links between existing formalisms, but it also covers yet unpublished frameworks (such as possibilistic influence diagrams) and unifies formalisms such as quantified boolean formulas and influence diagrams. Our backtrack and variable elimination generic algorithms are a first step towards unified algorithms.
過去数十年間にわたり、意思決定問題をモデル化し、解決するための数多くの形式主義と専用アルゴリズムが設計されてきた。制約ネットワークなどの形式主義は「単純な」意思決定問題を表現できますが、不確実性、実行不可能な決定、そして効用を考慮するように設計された形式主義もあります。単一の形式主義においても、異なる種類の不確実性（確率、可能性など）や効用（加法的か否か）をモデル化するために、複数のバリエーションが提案されることがよくあります。本稿では、このような多数の形式主義を包含する代数的グラフィカルモデルを紹介します。(1)まず、フリードマン、チュー、ハルパーンによる不確実性、効用、期待効用を表す既存の構造を適応させ、一般的な逐次的意思決定形式に対応させます。(2)次に、これらの構造に基づき、条件付き独立性を利用して「局所的」関数で連結された変数を介して情報を表現する複合グラフィカルモデルを導入します。(3)最後に、これらのグラフィカルモデルに基づき、観測可能性と制御可能性の観点から様々なシナリオを表現できる単純なクエリクラスを定義します。このようなクエリに対する自然な決定木意味論は、同等の操作的意味論によって完成され、汎用的なアルゴリズムを導きます。提案されたフレームワークは、Plausibility-Feasibility-Utility (PFU)フレームワークと呼ばれ、既存の形式主義間の関連性をより深く理解するだけでなく、未発表のフレームワーク（可能性影響図など）をカバーし、定量化ブール式や影響図などの形式主義を統合します。バックトラックと変数除去の汎用アルゴリズムは、統一アルゴリズムへの第一歩です。
Obtaining Reliable Feedback for Sanctioning Reputation Mechanisms
制裁的評判メカニズムのための信頼性の高いフィードバックの取得
Reputation mechanisms offer an effective alternative to verification authorities for building trust in electronic markets with moral hazard. Future clients guide their business decisions by considering the feedback from past transactions; if truthfully exposed, cheating behavior is sanctioned and thus becomes irrational.It therefore becomes important to ensure that rational clients have the right incentives to report honestly. As an alternative to side-payment schemes that explicitly reward truthful reports, we show that honesty can emerge as a rational behavior when clients have a repeated presence in the market. To this end we describe a mechanism that supports an equilibrium where truthful feedback is obtained. Then we characterize the set of pareto-optimal equilibria of the mechanism, and derive an upper bound on the percentage of false reports that can be recorded by the mechanism. An important role in the existence of this bound is played by the fact that rational clients can establish a reputation for reporting honestly.
評判メカニズムは、モラルハザードを伴う電子市場における信頼構築において、検証機関に代わる効果的な代替手段となります。将来の顧客は、過去の取引からのフィードバックを考慮してビジネス上の意思決定を行う。もし不正行為が真実であると暴露されれば、それは制裁の対象となり、非合理的なものとなります。したがって、合理的な顧客が正直に報告する適切なインセンティブを確保することが重要となります。正直な報告に明示的に報奨を与えるサイドペイメントスキームの代替として、顧客が市場に繰り返し参入する場合、正直さが合理的な行動として出現する可能性があることを示す。この目的のために、真実のフィードバックが得られる均衡を支持するメカニズムを説明します。次に、このメカニズムのパレート最適均衡の集合を特徴付け、メカニズムによって記録できる虚偽報告の割合の上限を導出します。この上限の存在において重要な役割を果たすのは、合理的な顧客が正直に報告するという評判を確立できるという事実です。
Answer Sets for Logic Programs with Arbitrary Abstract Constraint Atoms
任意の抽象制約アトムを持つ論理プログラムの解答集合
In this paper, we present two alternative approaches to defining answer sets for logic programs with arbitrary types of abstract constraint atoms (c-atoms). These approaches generalize the fixpoint-based and the level mapping based answer set semantics of normal logic programs to the case of logic programs with arbitrary types of c-atoms. The results are four different answer set definitions which are equivalent when applied to normal logic programs. The standard fixpoint-based semantics of logic programs is generalized in two directions, called answer set by reduct and answer set by complement. These definitions, which differ from each other in the treatment of negation-as-failure (naf) atoms, make use of an immediate consequence operator to perform answer set checking, whose definition relies on the notion of conditional satisfaction of c-atoms w.r.t. a pair of interpretations. The other two definitions, called strongly and weakly well-supported models, are generalizations of the notion of well-supported models of normal logic programs to the case of programs with c-atoms. As for the case of fixpoint-based semantics, the difference between these two definitions is rooted in the treatment of naf atoms. We prove that answer sets by reduct (resp. by complement) are equivalent to weakly (resp. strongly) well-supported models of a program, thus generalizing the theorem on the correspondence between stable models and well-supported models of a normal logic program to the class of programs with c-atoms. We show that the newly defined semantics coincide with previously introduced semantics for logic programs with monotone c-atoms, and they extend the original answer set semantics of normal logic programs. We also study some properties of answer sets of programs with c-atoms, and relate our definitions to several semantics for logic programs with aggregates presented in the literature.
本稿では、任意の種類の抽象制約アトム（c-アトム）を持つ論理プログラムの解答集合を定義するための2つの代替アプローチを提示します。これらのアプローチは、通常の論理プログラムの不動点ベースおよびレベルマッピングベースの解答集合セマンティクスを、任意の種類のc-アトムを持つ論理プログラムの場合に一般化します。その結果、通常の論理プログラムに適用した場合に等価な4つの異なる解答集合定義が得られます。論理プログラムの標準的な不動点ベースのセマンティクスは、縮約による解答集合と補集合による解答集合と呼ばれる2つの方向に一般化されます。これらの定義は、否定が失敗である(naf)アトムの扱いが互いに異なり、即値演算子を使用して解答セットのチェックを実行します。その定義は、一対の解釈に関するc-アトムの条件付き充足の概念に依存しています。他の2つの定義は、強くおよび弱くよくサポートされているモデルと呼ばれ、通常の論理プログラムのよくサポートされているモデルの概念を、c-アトムを含むプログラムの場合に一般化したものです。不動点ベースのセマンティクスの場合と同様に、これら2つの定義の違いは、nafアトムの扱いに根ざしています。縮約(または補数)による解答セットは、プログラムの弱く(または強く)よくサポートされているモデルと同等であることを証明し、これにより、通常の論理プログラムの安定モデルとよくサポートされているモデル間の対応に関する定理を、c-アトムを含むプログラムのクラスに一般化します。新たに定義した意味論は、単調なc-アトムを持つ論理プログラムに対して既に導入された意味論と一致し、通常の論理プログラムの元々の解集合意味論を拡張することを示す。また、c-アトムを持つプログラムの解集合のいくつかの性質を考察し、文献で提示されている集合体を持つ論理プログラムのいくつかの意味論と我々の定義を関連付ける。
Learning Symbolic Models of Stochastic Domains
確率的領域の記号モデルの学習
In this article, we work towards the goal of developing agents that can learn to act in complex worlds. We develop a probabilistic, relational planning rule representation that compactly models noisy, nondeterministic action effects, and show how such rules can be effectively learned. Through experiments in simple planning domains and a 3D simulated blocks world with realistic physics, we demonstrate that this learning algorithm allows agents to effectively model world dynamics.
この記事では、複雑な世界で行動することを学習できるエージェントの開発という目標に向けて取り組んでいます。我々は、ノイズの多い非決定論的な行動効果をコンパクトにモデル化する確率的関係計画ルール表現を開発し、そのようなルールがどのように効果的に学習されるかを示す。単純な計画ドメインと現実的な物理特性を持つ3Dブロックシミュレーション世界における実験を通して、この学習アルゴリズムによってエージェントが世界のダイナミクスを効果的にモデル化できることを実証します。
Semantic Matchmaking as Non-Monotonic Reasoning: A Description Logic Approach
非単調推論としての意味的マッチメイキング：記述論理アプローチ
Matchmaking arises when supply and demand meet in an electronic marketplace, or when agents search for a web service to perform some task, or even when recruiting agencies match curricula and job profiles. In such open environments, the objective of a matchmaking process is to discover best available offers to a given request.We address the problem of matchmaking from a knowledge representation perspective, with a formalization based on Description Logics. We devise Concept Abduction and Concept Contraction as non-monotonic inferences in Description Logics suitable for modeling matchmaking in a logical framework, and prove some related complexity results. We also present reasonable algorithms for semantic matchmaking based on the devised inferences, and prove that they obey to some commonsense properties.Finally, we report on the implementation of the proposed matchmaking framework, which has been used both as a mediator in e-marketplaces and for semantic web services discovery.
マッチメイキングは、電子市場で需要と供給が出会ったとき、エージェントが何らかのタスクを実行するためのWebサービスを検索したとき、あるいは人材紹介会社がカリキュラムと職務プロファイルをマッチングさせたときに発生します。このようなオープンな環境におけるマッチメイキングプロセスの目的は、与えられたリクエストに対して利用可能な最良のオファーを見つけることです。私たちは、記述論理に基づく形式化を用いて、知識表現の観点からマッチメイキングの問題に取り組みます。論理フレームワークでマッチメイキングをモデル化するのに適した記述論理における非単調推論として、概念アブダクションと概念縮約を考案し、関連する複雑性の結果をいくつか証明します。また、考案した推論に基づくセマンティックマッチメイキングのための合理的なアルゴリズムを提示し、それらがいくつかの常識的な特性に従うことを証明します。最後に、提案されたマッチメイキングフレームワークの実装について報告します。このフレームワークは、電子市場の仲介者として、またセマンティックWebサービスの発見のために使用されています。
On the Formal Semantics of Speech-Act Based Communication in an Agent-Oriented Programming Language
エージェント指向プログラミング言語における発話行為に基づくコミュニケーションの形式意味論について
Research on agent communication languages has typically taken the speech acts paradigm as its starting point. Despite their manifest attractions, speech-act models of communication have several serious disadvantages as a foundation for communication in artificial agent systems. In particular, it has proved to be extremely difficult to give a satisfactory semantics to speech-act based agent communication languages. In part, the problem is that speech-act semantics typically make reference to the “mental states” of agents (their beliefs, desires, and intentions), and there is in general no way to attribute such attitudes to arbitrary computational agents. In addition, agent programming languages have only had their semantics formalised for abstract, stand-alone versions, neglecting aspects such as communication primitives. With respect to communication, implemented agent programming languages have tended to be rather ad hoc. This paper addresses both of these problems, by giving semantics to speech-act based messages received by an AgentSpeak agent. AgentSpeak is a logic-based agent programming language which incorporates the main features of the PRS model of reactive planning systems. The paper builds upon a structural operational semantics to AgentSpeak that we developed in previous work. The main contributions of this paper are as follows: an extension of our earlier work on the theoretical foundations of AgentSpeak interpreters; a computationally grounded semantics for (the core) performatives used in speech-act based agent communication languages; and a well-defined extension of AgentSpeak that supports agent communication.
エージェントコミュニケーション言語の研究は、典型的には発話行為パラダイムを出発点としてきた。発話行為モデルは明らかな魅力を持つものの、人工エージェントシステムにおけるコミュニケーションの基盤としてはいくつかの重大な欠点を抱えています。特に、発話行為に基づくエージェントコミュニケーション言語に満足のいく意味論を与えることは極めて困難であることが判明しています。問題の一因として、発話行為の意味論は典型的にはエージェントの「精神状態」（信念、欲求、意図）を参照するもので、そのような態度を任意の計算エージェントに帰属させる方法が一般的に存在しないことが挙げられます。さらに、エージェントプログラミング言語の意味論は、コミュニケーションプリミティブなどの側面を無視した抽象的なスタンドアロンバージョンに対してのみ形式化されてきた。コミュニケーションに関して、実装されたエージェントプログラミング言語はどちらかといえばアドホックになりがちです。本論文は、AgentSpeakエージェントが受信する発話行為ベースのメッセージに意味論を与えることで、これらの問題の両方に対処します。AgentSpeakは、反応型プランニングシステムのPRSモデルの主要な特徴を取り入れた、論理ベースのエージェントプログラミング言語です。本論文は、以前の研究で開発したAgentSpeakの構造的操作的意味論に基づいています。本論文の主な貢献は、AgentSpeakインタープリタの理論的基礎に関する以前の研究の拡張、発話行為ベースのエージェントコミュニケーション言語で使用される（コア）パフォーマティブのための計算論に基づいた意味論、そしてエージェントコミュニケーションをサポートする明確に定義されたAgentSpeakの拡張です。
This paper is concerned with a class of algorithms that perform exhaustive search on propositional knowledge bases. We show that each of these algorithms defines and generates a propositional language. Specifically, we show that the trace of a search can be interpreted as a combinational circuit, and a search algorithm then defines a propositional language consisting of circuits that are generated across all possible executions of the algorithm. In particular, we show that several versions of exhaustive DPLL search correspond to such well-known languages as FBDD, OBDD, and a precisely-defined subset of d-DNNF. By thus mapping search algorithms to propositional languages, we provide a uniform and practical framework in which successful search techniques can be harnessed for compilation of knowledge into various languages of interest, and a new methodology whereby the power and limitations of search algorithms can be understood by looking up the tractability and succinctness of the corresponding propositional languages.
本論文は、命題知識ベース上で網羅的探索を実行するアルゴリズムのクラスを扱う。これらのアルゴリズムのそれぞれが命題言語を定義・生成することを示す。具体的には、探索の軌跡が組み合わせ回路として解釈できること、そして探索アルゴリズムが、アルゴリズムのあらゆる可能な実行を通して生成される回路からなる命題言語を定義することを示す。特に、網羅的DPLL探索のいくつかのバージョンが、FBDD、OBDD、そして明確に定義されたd-DNNFのサブセットといったよく知られた言語に対応することを示す。このように、探索アルゴリズムを命題言語にマッピングすることで、我々は、効果的な探索技術を様々な関心言語への知識のコンパイルに活用できる統一的かつ実用的な枠組みと、対応する命題言語の扱いやすさと簡潔さを調べることで探索アルゴリズムの威力と限界を理解できる新しい方法論を提供します。
Computationally Feasible VCG Mechanisms
計算的に実現可能なVCGメカニズム
A major achievement of mechanism design theory is a general method for the construction of truthful mechanisms called VCG (Vickrey, Clarke, Groves). When applying this method to complex problems such as combinatorial auctions, a difficulty arises: VCG mechanisms are required to compute optimal outcomes and are, therefore, computationally infeasible. However, if the optimal outcome is replaced by the results of a sub-optimal algorithm, the resulting mechanism (termed VCG-based) is no longer necessarily truthful. The first part of this paper studies this phenomenon in depth and shows that it is near universal. Specifically, we prove that essentially all reasonable approximations or heuristics for combinatorial auctions as well as a wide class of cost minimization problems yield non-truthful VCG-based mechanisms. We generalize these results for affine maximizers.The second part of this paper proposes a general method for circumventing the above problem. We introduce a modification of VCG-based mechanisms in which the agents are given a chance to improve the output of the underlying algorithm. When the agents behave truthfully, the welfare obtained by the mechanism is at least as good as the one obtained by the algorithm’s output. We provide a strong rationale for truth-telling behavior. Our method satisfies individual rationality as well.
メカニズムデザイン理論の主要な成果の一つは、VCG（Vickrey, Clarke, Groves）と呼ばれる、真実性の高いメカニズムを構築するための一般的な手法です。この手法を組合せオークションのような複雑な問題に適用する場合、困難が生じる。VCGメカニズムは最適な結果を計算する必要があるため、計算的に実行不可能です。しかし、最適な結果が準最適なアルゴリズムの結果に置き換えられた場合、結果として得られるメカニズム（VCGベースと呼ばれる）は、もはや必ずしも真実性を持つとは限らない。本論文の前半では、この現象を詳細に研究し、それがほぼ普遍的であることを示す。具体的には、組合せオークション、そして広範なコスト最小化問題に対する、本質的にすべての合理的な近似法やヒューリスティックが、真実性を持たないVCGベースメカニズムを生み出すことを証明します。これらの結果をアフィン最大化問題に一般化します。本論文の後半では、上記の問題を回避するための一般的な手法を提案します。VCGベースメカニズムの修正版を導入し、エージェントに基礎となるアルゴリズムの出力を改善する機会を与える。エージェントが誠実に行動する場合、メカニズムによって得られる福祉は、アルゴリズムの出力によって得られる福祉と少なくとも同等です。我々は、真実を語る行動に対する強力な根拠を提供します。我々の手法は、個体合理性も満たす。
The Generalized A* Architecture
一般化A*アーキテクチャ
We consider the problem of computing a lightest derivation of a global structure using a set of weighted rules. A large variety of inference problems in AI can be formulated in this framework. We generalize A* search and heuristics derived from abstractions to a broad class of lightest derivation problems. We also describe a new algorithm that searches for lightest derivations using a hierarchy of abstractions. Our generalization of A* gives a new algorithm for searching AND/OR graphs in a bottom-up fashion.We discuss how the algorithms described here provide a general architecture for addressing the pipeline problem — the problem of passing information back and forth between various stages of processing in a perceptual system. We consider examples in computer vision and natural language processing. We apply the hierarchical search algorithm to the problem of estimating the boundaries of convex objects in grayscale images and compare it to other search methods. A second set of experiments demonstrate the use of a new compositional model for finding salient curves in images.
重み付けルールのセットを使用して、グローバル構造の最も軽い導出を計算する問題を考察します。このフレームワークでは、AIにおけるさまざまな推論問題を定式化できます。A*探索と抽象化から導かれるヒューリスティックを、幅広い最軽量導出問題に一般化します。また、抽象化の階層を用いて最軽量導出を探索する新しいアルゴリズムについても述べる。A*の一般化は、AND/ORグラフをボトムアップ方式で探索する新しいアルゴリズムを与える。ここで説明するアルゴリズムが、パイプライン問題（知覚システムにおける様々な処理段階間で情報をやり取りする問題）に対処するための一般的なアーキテクチャをどのように提供するかについて考察します。コンピュータビジョンと自然言語処理の例を検討します。階層的探索アルゴリズムをグレースケール画像内の凸状物体の境界を推定する問題に適用し、他の探索手法と比較します。2つ目の実験セットでは、画像内の顕著な曲線を見つけるための新しい構成モデルの使用法を示す。
Combination Strategies for Semantic Role Labeling
意味的役割ラベリングのための組み合わせ戦略
This paper introduces and analyzes a battery of inference models for the problem of semantic role labeling: one based on constraint satisfaction, and several strategies that model the inference as a meta-learning problem using discriminative classifiers. These classifiers are developed with a rich set of novel features that encode proposition and sentence-level information. To our knowledge, this is the first work that: (a) performs a thorough analysis of learning-based inference models for semantic role labeling, and (b) compares several inference strategies in this context. We evaluate the proposed inference strategies in the framework of the CoNLL-2005 shared task using only automatically-generated syntactic information. The extensive experimental evaluation and analysis indicates that all the proposed inference strategies are successful -they all outperform the current best results reported in the CoNLL-2005 evaluation exercise- but each of the proposed approaches has its advantages and disadvantages. Several important traits of a state-of-the-art SRL combination strategy emerge from this analysis: (i) individual models should be combined at the granularity of candidate arguments rather than at the granularity of complete solutions; (ii) the best combination strategy uses an inference model based in learning; and (iii) the learning-based inference benefits from max-margin classifiers and global feedback.
本論文では、意味的役割ラベル付けの問題に対する一連の推論モデルを紹介し、分析します。1つは制約充足に基づくモデル、もう1つは識別分類器を用いて推論をメタ学習問題としてモデル化する複数の戦略です。これらの分類器は、命題レベルと文レベルの情報を符号化する豊富な新規機能セットを用いて開発されています。我々の知る限り、これは(a)意味的役割ラベル付けのための学習ベースの推論モデルを徹底的に分析し、(b)この文脈で複数の推論戦略を比較した初の研究です。提案された推論戦略を、自動生成された統語情報のみを使用してCoNLL-2005共有タスクのフレームワークで評価します。広範な実験評価と分析により、提案された推論戦略はすべて成功していることが示されています(それらはすべて、CoNLL-2005評価演習で報告された現在の最高の結果よりも優れています)。ただし、提案されたアプローチにはそれぞれ長所と短所があります。この分析から、最先端のSRL組み合わせ戦略のいくつかの重要な特徴が明らかになりました。(i)個々のモデルは、完全なソリューションの粒度ではなく、候補の引数の粒度で組み合わせる必要があります。(ii)最適な組み合わせ戦略では、学習に基づく推論モデルを使用します。(iii)学習ベースの推論では、最大マージン分類器とグローバル フィードバックのメリットがあります。
Phase Transition for Random Quantified XOR-Formulas
ランダム量化XOR式の相転移
The QXORSAT problem is the quantified version of the satisfiability problem XORSAT in which the connective exclusive-or is used instead of the usual or. We study the phase transition associated with random QXORSAT instances. We give a description of this phase transition in the case of one alternation of quantifiers, thus performing an advanced practical and theoretical study on the phase transition of a quantified roblem.
QXORSAT問題は、充足可能性問題XORSATの量化版であり、通常の論理和の代わりに接続詞の排他的論理和が用いられます。我々はランダムなQXORSATインスタンスに関連する相転移を調べる。我々は量指定子の交代が1回の場合のこの相転移を記述し、量指定問題の相転移に関する高度な実践的かつ理論的な研究を行う。