Journal of Artificial Intelligence Resarch Vol. 18 (2003)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。
Learning to Order BDD Variables in Verification
検証におけるBDD変数の順序付け学習
The size and complexity of software and hardware systems have significantly increased in the past years. As a result, it is harder to guarantee their correct behavior. One of the most successful methods for automated verification of finite-state systems is model checking. Most of the current model-checking systems use binary decision diagrams (BDDs) for the representation of the tested model and in the verification process of its properties. Generally, BDDs allow a canonical compact representation of a boolean function (given an order of its variables). The more compact the BDD is, the better performance one gets from the verifier. However, finding an optimal order for a BDD is an NP-complete problem. Therefore, several heuristic methods based on expert knowledge have been developed for variable ordering. We propose an alternative approach in which the variable ordering algorithm gains ‘ordering experience’ from training models and uses the learned knowledge for finding good orders. Our methodology is based on offline learning of pair precedence classifiers from training models, that is, learning which variable pair permutation is more likely to lead to a good order. For each training model, a number of training sequences are evaluated. Every training model variable pair permutation is then tagged based on its performance on the evaluated orders. The tagged permutations are then passed through a feature extractor and are given as examples to a classifier creation algorithm. Given a model for which an order is requested, the ordering algorithm consults each precedence classifier and constructs a pair precedence table which is used to create the order. Our algorithm was integrated with SMV, which is one of the most widely used verification systems. Preliminary empirical evaluation of our methodology, using real benchmark models, shows performance that is better than random ordering and is competitive with existing algorithms that use expert knowledge. We believe that in sub-domains of models (alu, caches, etc.) our system will prove even more valuable. This is because it features the ability to learn sub-domain knowledge, something that no other ordering algorithm does.
ソフトウェアおよびハードウェアシステムの規模と複雑さは、近年著しく増大しています。その結果、それらの正しい動作を保証することがより困難になっています。有限状態システムの自動検証において最も成功している方法の一つは、モデル検査です。現在のモデル検査システムのほとんどは、テスト対象モデルの表現とその特性の検証プロセスにおいて、二分決定図（BDD）を用いています。一般的に、BDDはブール関数（変数の順序が与えられた場合）の標準的なコンパクトな表現を可能にします。BDDがコンパクトであればあるほど、検証ツールのパフォーマンスは向上します。しかし、BDDの最適な順序を見つけることはNP完全問題です。そのため、変数順序付けには、専門知識に基づくいくつかのヒューリスティック手法が開発されてきました。本稿では、変数順序付けアルゴリズムがトレーニングモデルから「順序付け経験」を獲得し、学習した知識を用いて適切な順序付けを見つけるという、代替アプローチを提案します。本手法は、トレーニングモデルからペアの優先順位分類器をオフラインで学習すること、つまり、どの変数ペアの順列が適切な順序付けにつながる可能性が高いかを学習することに基づいています。各トレーニング モデルについて、いくつかのトレーニング シーケンスが評価されます。次に、評価された順序でのパフォーマンスに基づいて、すべてのトレーニング モデル変数ペアの順列がタグ付けされます。タグ付けされた順列は、特徴抽出器に渡され、分類器作成アルゴリズムに例として提供されます。順序付けが要求されたモデルが与えられると、順序付けアルゴリズムは各優先順位分類器を参照し、順序付けを作成するために使用されるペア優先順位テーブルを構築します。このアルゴリズムは、最も広く使用されている検証システムの1つであるSMVと統合されています。実際のベンチマーク モデルを使用した方法論の予備的な経験的評価では、ランダム順序付けよりも優れたパフォーマンスが示され、専門知識を使用する既存のアルゴリズムと競合できることが示されています。モデルのサブドメイン(alu、キャッシュなど)では、このシステムの価値がさらに高まると考えています。これは、他の順序付けアルゴリズムにはない、サブドメイン知識を学習する機能を備えているためです。
Acquiring Correct Knowledge for Natural Language Generation
自然言語生成のための正しい知識の獲得
Natural language generation (NLG) systems are computer software systems that produce texts in English and other human languages, often from non-linguistic input data. NLG systems, like most AI systems, need substantial amounts of knowledge. However, our experience in two NLG projects suggests that it is difficult to acquire correct knowledge for NLG systems; indeed, every knowledge acquisition (KA) technique we tried had significant problems. In general terms, these problems were due to the complexity, novelty, and poorly understood nature of the tasks our systems attempted, and were worsened by the fact that people write so differently. This meant in particular that corpus-based KA approaches suffered because it was impossible to assemble a sizable corpus of high-quality consistent manually written texts in our domains; and structured expert-oriented KA techniques suffered because experts disagreed and because we could not get enough information about special and unusual cases to build robust systems. We believe that such problems are likely to affect many other NLG systems as well. In the long term, we hope that new KA techniques may emerge to help NLG system builders. In the shorter term, we believe that understanding how individual KA techniques can fail, and using a mixture of different KA techniques with different strengths and weaknesses, can help developers acquire NLG knowledge that is mostly correct.
自然言語生成（NLG）システムは、多くの場合、非言語入力データから英語やその他の人間の言語でテキストを生成するコンピュータソフトウェアシステムです。NLGシステムは、ほとんどのAIシステムと同様に、かなりの量の知識を必要とします。しかし、2つのNLGプロジェクトでの経験から、NLGシステムにとって正しい知識を獲得することは困難であることが示唆されています。実際、試した知識獲得（KA）手法はすべて重大な問題を抱えていました。一般的に、これらの問題は、システムが試みたタスクの複雑さ、新規性、および理解の不足に起因するものであり、人々の書き方が大きく異なるという事実によってさらに悪化していました。これは特に、コーパスベースのKAアプローチは、私たちの分野で高品質で一貫性のある手書きテキストの大規模なコーパスを組み立てることが不可能であるために苦労し、専門家向けの構造化されたKA手法は、専門家の意見が一致せず、堅牢なシステムを構築するために特別なケースや異常なケースに関する十分な情報を得ることができなかったために苦労したことを意味します。このような問題は、他の多くのNLGシステムにも影響を与える可能性が高いと考えています。長期的には、NLGシステム構築者を支援する新しいKA手法が登場することを期待しています。短期的には、個々のKA手法がどのように失敗するかを理解し、長所と短所の異なるKA手法を組み合わせて使用することで、開発者がほぼ正しいNLG知識を獲得できると考えています。
Monte Carlo Methods for Tempo Tracking and Rhythm Quantization
テンポトラッキングとリズムクォンタイズのためのモンテカルロ法
We present a probabilistic generative model for timing deviations in expressive music performance. The structure of the proposed model is equivalent to a switching state space model. The switch variables correspond to discrete note locations as in a musical score. The continuous hidden variables denote the tempo. We formulate two well known music recognition problems, namely tempo tracking and automatic transcription (rhythm quantization) as filtering and maximum a posteriori (MAP) state estimation tasks. Exact computation of posterior features such as the MAP state is intractable in this model class, so we introduce Monte Carlo methods for integration and optimization. We compare Markov Chain Monte Carlo (MCMC) methods (such as Gibbs sampling, simulated annealing and iterative improvement) and sequential Monte Carlo methods (particle filters). Our simulation results suggest better results with sequential methods. The methods can be applied in both online and batch scenarios such as tempo tracking and transcription and are thus potentially useful in a number of music applications such as adaptive automatic accompaniment, score typesetting and music information retrieval.
表現力豊かな音楽演奏におけるタイミング偏差の確率的生成モデルを提示します。提案モデルの構造は、スイッチング状態空間モデルと同等です。スイッチ変数は、楽譜のように離散的な音符の位置に対応します。連続的な隠れ変数はテンポを表す。テンポトラッキングと自動採譜（リズムクオンタイズ）という2つのよく知られた音楽認識問題を、フィルタリングと最大事後確率（MAP）状態推定タスクとして定式化します。このモデルクラスでは、MAP状態などの事後特徴の正確な計算は困難であるため、積分と最適化のためにモンテカルロ法を導入します。マルコフ連鎖モンテカルロ法（MCMC）（ギブスサンプリング、シミュレーテッドアニーリング、反復改善など）と逐次モンテカルロ法（粒子フィルタ）を比較します。シミュレーション結果は、逐次法の方が優れた結果をもたらすことを示唆しています。これらの手法は、テンポトラッキングやトランスクリプションなど、オンラインおよびバッチシナリオの両方に適用できるため、適応型自動伴奏、楽譜の組版、音楽情報検索など、多くの音楽アプリケーションで潜在的に有用です。
Searching for Bayesian Network Structures in the Space of Restricted Acyclic Partially Directed Graphs
制限付き非巡回部分有向グラフ空間におけるベイジアンネットワーク構造の探索
Although many algorithms have been designed to construct Bayesian network structures using different approaches and principles, they all employ only two methods: those based on independence criteria, and those based on a scoring function and a search procedure (although some methods combine the two). Within the score+search paradigm, the dominant approach uses local search methods in the space of directed acyclic graphs (DAGs), where the usual choices for defining the elementary modifications (local changes) that can be applied are arc addition, arc deletion, and arc reversal. In this paper, we propose a new local search method that uses a different search space, and which takes account of the concept of equivalence between network structures: restricted acyclic partially directed graphs (RPDAGs). In this way, the number of different configurations of the search space is reduced, thus improving efficiency. Moreover, although the final result must necessarily be a local optimum given the nature of the search method, the topology of the new search space, which avoids making early decisions about the directions of the arcs, may help to find better local optima than those obtained by searching in the DAG space. Detailed results of the evaluation of the proposed search method on several test problems, including the well-known Alarm Monitoring System, are also presented.
ベイジアン ネットワーク構造を構築するアルゴリズムは数多く、さまざまなアプローチと原理を使用して設計されていますが、それらはすべて、独立基準に基づく方法と、スコアリング関数および検索手順に基づく方法(ただし、この2つを組み合わせた方法もあります)の2つの方法のみを採用しています。スコア+検索パラダイムでは、有向非巡回グラフ(DAG)の空間でローカル検索法を使用するのが主流のアプローチです。DAGでは、適用可能な基本的な変更(ローカル変更)を定義するための通常の選択肢は、アークの追加、アークの削除、およびアークの反転です。本稿では、異なる検索空間を使用し、ネットワーク構造間の同値性の概念を考慮した新しいローカル検索法、制限付き非巡回部分有向グラフ(RPDAG)を提案します。この方法では、検索空間の異なる構成の数が削減され、効率が向上します。さらに、探索法の性質上、最終結果は必然的に局所最適解となるものの、弧の方向に関する早期決定を回避する新しい探索空間のトポロジーは、DAG空間での探索によって得られるものよりも優れた局所最適解を見つけるのに役立つ可能性があります。提案された探索法を、よく知られている警報監視システムを含むいくつかのテスト問題で評価した詳細な結果も提示します。
Propositional Independence – Formula-Variable Independence andForgetting
命題独立性 – 式-変数独立性と忘却
Independence — the study of what is relevant to a given problem of reasoning — has received an increasing attention from the AI community. In this paper, we consider two basic forms of independence, namely, a syntactic one and a semantic one. We show features and drawbacks of them. In particular, while the syntactic form of independence is computationally easy to check, there are cases in which things that intuitively are not relevant are not recognized as such. We also consider the problem of forgetting, i.e., distilling from a knowledge base only the part that is relevant to the set of queries constructed from a subset of the alphabet. While such process is computationally hard, it allows for a simplification of subsequent reasoning, and can thus be viewed as a form of compilation: once the relevant part of a knowledge base has been extracted, all reasoning tasks to be performed can be simplified.
独立性、つまり、与えられた推論問題に関連するものを研究する研究は、AIコミュニティからますます注目を集めています。本論文では、統語的独立性と意味的独立性という2つの基本的な独立性形式を考察します。そして、それぞれの特徴と欠点を示します。特に、統語的独立性形式は計算的に簡単にチェックできますが、直感的に関連がないことが関連していないと認識されない場合があります。また、忘却の問題、すなわち、アルファベットのサブセットから構築されたクエリセットに関連する部分のみを知識ベースから抽出する問題についても考察します。このようなプロセスは計算上困難ですが、後続の推論を簡素化できるため、コンパイルの一形態として考えることができます。つまり、知識ベースの関連部分が抽出されると、実行されるすべての推論タスクを簡素化できます。
A New General Method to Generate Random Modal Formulae for Testing Decision Procedures
決定手順のテストのためのランダム様相式を生成するための新しい一般的な手法
The recent emergence of heavily-optimized modal decision procedures has highlighted the key role of empirical testing in this domain. Unfortunately, the introduction of extensive empirical tests for modal logics is recent, and so far none of the proposed test generators is very satisfactory. To cope with this fact, we present a new random generation method that provides benefits over previous methods for generating empirical tests. It fixes and much generalizes one of the best-known methods, the random CNF_[]m test, allowing for generating a much wider variety of problems, covering in principle the whole input space. Our new method produces much more suitable test sets for the current generation of modal decision procedures. We analyze the features of the new method by means of an extensive collection of empirical tests.
最近、高度に最適化された様相決定手順が登場したことで、このドメインにおける経験的テストの重要な役割が浮き彫りになった。残念ながら、様相論理に対する広範な経験的テストの導入は最近のことであり、これまで提案されているテスト生成器はどれも十分に満足のいくものではない。この事実に対処するため、我々は、経験的テストを生成するための従来の方法よりも優れた利点を持つ、新しいランダム生成法を提示します。この論文は、最もよく知られた手法の1つであるランダムCNF_[]mテストを修正し、大幅に一般化することで、はるかに多様な問題の生成を可能にし、原理的には入力空間全体をカバーします。私たちの新しい手法は、現在のモーダル決定手順の世代にとって、はるかに適切なテストセットを生成します。私たちは、広範な経験的テストのコレクションを用いて、この新しい手法の特徴を分析します。
Structure and Complexity in Planning with Unary Operators
単項演算子を用いたプランニングにおける構造と複雑性
Unary operator domains — i.e., domains in which operators have a single effect — arise naturally in many control problems. In its most general form, the problem of STRIPS planning in unary operator domains is known to be as hard as the general STRIPS planning problem — both are PSPACE-complete. However, unary operator domains induce a natural structure, called the domain’s causal graph. This graph relates between the preconditions and effect of each domain operator. Causal graphs were exploited by Williams and Nayak in order to analyze plan generation for one of the controllers in NASA’s Deep-Space One spacecraft. There, they utilized the fact that when this graph is acyclic, a serialization ordering over any subgoal can be obtained quickly. In this paper we conduct a comprehensive study of the relationship between the structure of a domain’s causal graph and the complexity of planning in this domain. On the positive side, we show that a non-trivial polynomial time plan generation algorithm exists for domains whose causal graph induces a polytree with a constant bound on its node indegree. On the negative side, we show that even plan existence is hard when the graph is a directed-path singly connected DAG. More generally, we show that the number of paths in the causal graph is closely related to the complexity of planning in the associated domain. Finally we relate our results to the question of complexity of planning with serializable subgoals.
単項演算子領域、つまり演算子が単一の効果を持つ領域は、多くの制御問題で自然に発生します。最も一般的な形態では、単項演算子領域におけるSTRIPSプランニングの問題は、一般的なSTRIPSプランニング問題と同じくらい困難であることが知られています。どちらもPSPACE完全です。しかし、単項演算子領域は、領域の因果グラフと呼ばれる自然な構造を誘導します。このグラフは、各領域演算子の前提条件と効果を関連付けます。ウィリアムズとナヤックは、NASAの宇宙船ディープ・スペース・ワンの制御装置の1つのプラン生成を解析するために因果グラフを利用しました。そこで彼らは、このグラフが非巡回である場合、任意のサブゴールにわたる直列化順序付けを迅速に取得できるという事実を利用しました。本稿では、領域の因果グラフの構造と、この領域におけるプランニングの複雑さとの関係について包括的な研究を行います。肯定的な側面としては、因果グラフがそのノード入次数に定数境界を持つ多木を誘導するドメインに対して、非自明な多項式時間プラン生成アルゴリズムが存在することを示す。否定的な側面としては、グラフが有向パス単連結DAGである場合、プランの存在自体が困難であることを示す。より一般的には、因果グラフ内のパスの数が、関連するドメインにおけるプランニングの複雑さと密接に関係していることを示す。最後に、我々の結果を、直列化可能なサブゴールを持つプランニングの複雑さの問題に関連付ける。
Exploiting Contextual Independence In Probabilistic Inference
確率推論における文脈独立性の活用
Bayesian belief networks have grown to prominence because they provide compact representations for many problems for which probabilistic inference is appropriate, and there are algorithms to exploit this compactness. The next step is to allow compact representations of the conditional probabilities of a variable given its parents. In this paper we present such a representation that exploits contextual independence in terms of parent contexts; which variables act as parents may depend on the value of other variables. The internal representation is in terms of contextual factors (confactors) that is simply a pair of a context and a table. The algorithm, contextual variable elimination, is based on the standard variable elimination algorithm that eliminates the non-query variables in turn, but when eliminating a variable, the tables that need to be multiplied can depend on the context. This algorithm reduces to standard variable elimination when there is no contextual independence structure to exploit. We show how this can be much more efficient than variable elimination when there is structure to exploit. We explain why this new method can exploit more structure than previous methods for structured belief network inference and an analogous algorithm that uses trees.
ベイズ信念ネットワークは、確率的推論が適切な多くの問題を簡潔に表現できるため、注目を集めており、この簡潔性を活用するアルゴリズムも存在します。次のステップは、親を与えられた変数の条件付き確率を簡潔に表現できるようにすることです。本稿では、親コンテキストの観点からコンテキスト独立性を活用するそのような表現を提示します。どの変数が親として機能するかは、他の変数の値によって異なる場合があります。内部表現は、コンテキストとテーブルの単純なペアであるコンテキスト因子(コンファクター)で表されます。アルゴリズム(コンテキスト変数除去)は、非クエリ変数を順に除去する標準的な変数除去アルゴリズムに基づいていますが、変数を除去する際に、乗算する必要があるテーブルはコンテキストによって異なる場合があります。このアルゴリズムは、活用できるコンテキスト独立性構造がない場合、標準的な変数除去になります。活用できる構造がある場合、これが変数除去よりもはるかに効率的になる理由を示します。この新しい方法が、構造化信念ネットワーク推論の以前の方法や、ツリーを使用する類似のアルゴリズムよりも多くの構造を活用できる理由を説明します。
Interactive Execution Monitoring of Agent Teams
エージェントチームのインタラクティブな実行監視
There is an increasing need for automated support for humans monitoring the activity of distributed teams of cooperating agents, both human and machine. We characterize the domain-independent challenges posed by this problem, and describe how properties of domains influence the challenges and their solutions. We will concentrate on dynamic, data-rich domains where humans are ultimately responsible for team behavior. Thus, the automated aid should interactively support effective and timely decision making by the human. We present a domain-independent categorization of the types of alerts a plan-based monitoring system might issue to a user, where each type generally requires different monitoring techniques. We describe a monitoring framework for integrating many domain-specific and task-specific monitoring techniques and then using the concept of value of an alert to avoid operator overload. We use this framework to describe an execution monitoring approach we have used to implement Execution Assistants (EAs) in two different dynamic, data-rich, real-world domains to assist a human in monitoring team behavior. One domain (Army small unit operations) has hundreds of mobile, geographically distributed agents, a combination of humans, robots, and vehicles. The other domain (teams of unmanned ground and air vehicles) has a handful of cooperating robots. Both domains involve unpredictable adversaries in the vicinity. Our approach customizes monitoring behavior for each specific task, plan, and situation, as well as for user preferences. Our EAs alert the human controller when reported events threaten plan execution or physically threaten team members. Alerts were generated in a timely manner without inundating the user with too many alerts (less than 10 percent of alerts are unwanted, as judged by domain experts).
人間と機械の両方を含む、協力するエージェントからなる分散チームの活動を人間が監視するための自動支援の必要性が高まっています。この問題によって生じるドメイン非依存の課題を特徴づけ、ドメインの特性が課題とその解決策にどのように影響するかを説明します。本稿では、チームの行動の最終的な責任を人間が負う、動的でデータ豊富なドメインに焦点を当てます。したがって、自動支援は、人間による効果的かつタイムリーな意思決定を対話的に支援する必要があります。計画ベースの監視システムがユーザーに発行する可能性のあるアラートの種類をドメイン非依存に分類します。アラートの種類ごとに、通常、異なる監視手法が必要です。多くのドメイン固有およびタスク固有の監視手法を統合し、アラートの価値の概念を用いてオペレータの過負荷を回避するための監視フレームワークについて説明します。このフレームワークを用いて、人間によるチーム行動の監視を支援するために、動的でデータ豊富な2つの異なる実世界ドメインに実行アシスタント（EA）を実装するために使用した実行監視アプローチについて説明します。一方のドメイン（陸軍の小規模部隊の作戦）には、数百の地理的に分散した移動エージェント（人間、ロボット、車両の組み合わせ）が存在します。もう一方のドメイン（無人地上車両および無人航空機のチーム）には、少数の協力ロボットが存在します。どちらのドメインでも、近傍に予測不可能な敵が存在します。私たちのアプローチは、それぞれの特定のタスク、計画、状況、およびユーザーの好みに合わせて監視動作をカスタマイズします。私たちのEAは、報告されたイベントが計画実行を脅かす場合、またはチームメンバーを物理的に脅かす場合、人間のコントローラーに警告を発します。アラートは、ユーザーに過剰なアラートを大量に送信することなく、タイムリーに生成されました（ドメイン専門家の判断によると、不要なアラートは10%未満です）。
An Evolutionary Algorithm with Advanced Goal and Priority Specification for Multi-objective Optimization
多目的最適化のための高度な目標と優先度指定を備えた進化的アルゴリズム
This paper presents an evolutionary algorithm with a new goal-sequence domination scheme for better decision support in multi-objective optimization. The approach allows the inclusion of advanced hard/soft priority and constraint information on each objective component, and is capable of incorporating multiple specifications with overlapping or non-overlapping objective functions via logical ‘OR’ and ‘AND’ connectives to drive the search towards multiple regions of trade-off. In addition, we propose a dynamic sharing scheme that is simple and adaptively estimated according to the on-line population distribution without needing any a priori parameter setting. Each feature in the proposed algorithm is examined to show its respective contribution, and the performance of the algorithm is compared with other evolutionary optimization methods. It is shown that the proposed algorithm has performed well in the diversity of evolutionary search and uniform distribution of non-dominated individuals along the final trade-offs, without significant computational effort. The algorithm is also applied to the design optimization of a practical servo control system for hard disk drives with a single voice-coil-motor actuator. Results of the evolutionary designed servo control system show a superior closed-loop performance compared to classical PID or RPT approaches.
本論文では、多目的最適化における意思決定支援を向上させるための、新たな目標シーケンス支配スキームを備えた進化的アルゴリズムを提示します。このアプローチは、各目的関数コンポーネントに高度なハード／ソフト優先度および制約情報を組み込むことを可能にし、重複または非重複の目的関数を持つ複数の仕様を論理「OR」および「AND」結合を介して統合することで、複数のトレードオフ領域への探索を推進します。さらに、事前パラメータ設定を必要とせず、オンライン個体群分布に応じて適応的に推定される、シンプルでシンプルな動的共有スキームを提案します。提案アルゴリズムの各特徴について、それぞれの貢献度を検証し、その性能を他の進化的最適化手法と比較します。提案アルゴリズムは、大きな計算負荷をかけずに、進化的探索の多様性と最終トレードオフに沿った非支配個体の均一分布において優れた性能を発揮することを示す。このアルゴリズムは、単一のボイスコイルモータアクチュエータを備えたハードディスクドライブ用の実用的なサーボ制御システムの設計最適化にも適用されています。進化的に設計されたサーボ制御システムの結果は、従来のPIDまたはRPTアプローチと比較して、優れた閉ループ性能を示しています。
Wrapper Maintenance: A Machine Learning Approach
ラッパーメンテナンス：機械学習アプローチ
The proliferation of online information sources has led to an increased use of wrappers for extracting data from Web sources. While most of the previous research has focused on quick and efficient generation of wrappers, the development of tools for wrapper maintenance has received less attention. This is an important research problem because Web sources often change in ways that prevent the wrappers from extracting data correctly. We present an efficient algorithm that learns structural information about data from positive examples alone. We describe how this information can be used for two wrapper maintenance applications: wrapper verification and reinduction. The wrapper verification system detects when a wrapper is not extracting correct data, usually because the Web source has changed its format. The reinduction algorithm automatically recovers from changes in the Web source by identifying data on Web pages so that a new wrapper may be generated for this source. To validate our approach, we monitored 27 wrappers over a period of a year. The verification algorithm correctly discovered 35 of the 37 wrapper changes, and made 16 mistakes, resulting in precision of 0.73 and recall of 0.95. We validated the reinduction algorithm on ten Web sources. We were able to successfully reinduce the wrappers, obtaining precision and recall values of 0.90 and 0.80 on the data extraction task.
オンライン情報源の急増により、Webソースからデータを抽出するためのラッパーの使用が増加しています。これまでの研究のほとんどは、ラッパーの迅速かつ効率的な生成に焦点を当てていましたが、ラッパーを保守するためのツールの開発はあまり注目されていませんでした。Webソースは、ラッパーがデータを正しく抽出するのを妨げるような方法で頻繁に変更されるため、これは重要な研究課題です。私たちは、正例のみからデータの構造情報を学習する効率的なアルゴリズムを紹介します。この情報を、ラッパー検証と再帰という2つのラッパー保守アプリケーションにどのように使用できるかについて説明します。ラッパー検証システムは、ラッパーが正しいデータを抽出していないことを検出します。これは通常、Webソースのフォーマットが変更されたことが原因です。再帰アルゴリズムは、Webページ上のデータを識別することでWebソースの変更を自動的に回復し、このソースに対して新しいラッパーを生成します。このアプローチを検証するために、1年間にわたって27個のラッパーを監視しました。検証アルゴリズムは、37個のラッパーの変更のうち35個を正しく検出し、16個の誤りを検出しました。その結果、適合率は0.73、再現率は0.95でした。再帰アルゴリズムを10個のWebソースで検証した結果、ラッパーの再帰に成功し、データ抽出タスクで適合率0.90、再現率は0.80という結果を得ました。
Translation of Pronominal Anaphora between English and Spanish: Discrepancies and Evaluation
英語とスペイン語の代名詞照応の翻訳：相違点と評価
This paper evaluates the different tasks carried out in the translation of pronominal anaphora in a machine translation (MT) system. The MT interlingua approach named AGIR (Anaphora Generation with an Interlingua Representation) improves upon other proposals presented to date because it is able to translate intersentential anaphors, detect co-reference chains, and translate Spanish zero pronouns into English—issues hardly considered by other systems. The paper presents the resolution and evaluation of these anaphora problems in AGIR with the use of different kinds of knowledge (lexical, morphological, syntactic, and semantic). The translation of English and Spanish anaphoric third-person personal pronouns (including Spanish zero pronouns) into the target language has been evaluated on unrestricted corpora. We have obtained a precision of 80.4% and 84.8% in the translation of Spanish and English pronouns, respectively. Although we have only studied the Spanish and English languages, our approach can be easily extended to other languages such as Portuguese, Italian, or Japanese.
本論文では、機械翻訳（MT）システムにおける代名詞のアナフォラ翻訳において実行される様々なタスクを評価します。AGIR（Anaphora Generation with an Interlingua Representation）と呼ばれるMTインターリングア手法は、文間アナフォラの翻訳、共参照連鎖の検出、スペイン語のゼロ代名詞の英語への翻訳など、他のシステムではほとんど考慮されていない問題に対応できるため、これまで提案された他の手法よりも優れています。本論文では、様々な種類の知識（語彙、形態素、統語、意味）を用いて、AGIRにおけるこれらのアナフォラ問題の解決と評価を示します。英語とスペイン語のアナフォリック三人称代名詞（スペイン語のゼロ代名詞を含む）のターゲット言語への翻訳を、無制限のコーパスで評価しました。スペイン語と英語の代名詞の翻訳で、それぞれ80.4%と84.8%の精度が得られました。私たちはスペイン語と英語のみを研究しましたが、私たちのアプローチはポルトガル語、イタリア語、日本語などの他の言語にも簡単に拡張できます。
Acquiring Word-Meaning Mappings for Natural Language Interfaces
自然言語インターフェースのための単語意味マッピングの獲得
This paper focuses on a system, WOLFIE (WOrd Learning From Interpreted Examples), that acquires a semantic lexicon from a corpus of sentences paired with semantic representations. The lexicon learned consists of phrases paired with meaning representations. WOLFIE is part of an integrated system that learns to transform sentences into representations such as logical database queries. Experimental results are presented demonstrating WOLFIE’s ability to learn useful lexicons for a database interface in four different natural languages. The usefulness of the lexicons learned by WOLFIE are compared to those acquired by a similar system, with results favorable to WOLFIE. A second set of experiments demonstrates WOLFIE’s ability to scale to larger and more difficult, albeit artificially generated, corpora. In natural language acquisition, it is difficult to gather the annotated data needed for supervised learning; however, unannotated data is fairly plentiful. Active learning methods attempt to select for annotation and training only the most informative examples, and therefore are potentially very useful in natural language applications. However, most results to date for active learning have only considered standard classification tasks. To reduce annotation effort while maintaining accuracy, we apply active learning to semantic lexicons. We show that active learning can significantly reduce the number of annotated examples required to achieve a given level of performance.
この論文では、意味表現と対になった文のコーパスから意味語彙を獲得するシステムWOLFIE (WOrd Learning From Interpreted Examples)に焦点を当てています。学習される語彙は、意味表現と対になったフレーズで構成されます。WOLFIEは、文を論理データベースクエリなどの表現に変換することを学習する統合システムの一部です。4つの異なる自然言語でデータベースインターフェースに有用な語彙を学習するWOLFIEの能力を示す実験結果が示されています。WOLFIEによって学習された語彙の有用性は、同様のシステムによって獲得された語彙と比較され、WOLFIEに有利な結果が出ています。2つ目の一連の実験では、人工的に生成されたコーパスであっても、より大規模で難しいコーパスに拡張できるWOLFIEの能力を示します。自然言語獲得では、教師あり学習に必要な注釈付きデータを収集することは困難ですが、注釈なしデータはかなり豊富です。能動学習法は、最も有益な例のみを注釈付けと学習の対象とするため、自然言語アプリケーションにおいて非常に有用である可能性があります。しかし、これまでの能動学習に関する成果のほとんどは、標準的な分類タスクのみを対象としています。精度を維持しながら注釈付けの労力を削減するために、我々は意味辞書に能動学習を適用します。そして、能動学習によって、所定の性能レベルを達成するために必要な注釈付き例の数を大幅に削減できることを示します。