Journal of Artificial Intelligence Resarch Vol. 27 (2006)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。
Learning Sentence-internal Temporal Relations
文内時間関係の学習
In this paper we propose a data intensive approach for inferring sentence-internal temporal relations. Temporal inference is relevant for practical NLP applications which either extract or synthesize temporal information (e.g., summarisation, question answering). Our method bypasses the need for manual coding by exploiting the presence of markers like “after”, which overtly signal a temporal relation. We first show that models trained on main and subordinate clauses connected with a temporal marker achieve good performance on a pseudo-disambiguation task simulating temporal inference (during testing the temporal marker is treated as unseen and the models must select the right marker from a set of possible candidates). Secondly, we assess whether the proposed approach holds promise for the semi-automatic creation of temporal annotations. Specifically, we use a model trained on noisy and approximate data (i.e., main and subordinate clauses) to predict intra-sentential relations present in TimeBank, a corpus annotated rich temporal information. Our experiments compare and contrast several probabilistic models differing in their feature space, linguistic assumptions and data requirements. We evaluate performance against gold standard corpora and also against human subjects.
本論文では、文内の時間関係を推論するためのデータ集約型アプローチを提案します。時間推論は、時間情報を抽出または合成する実用的なNLPアプリケーション（要約、質問応答など）に関連しています。我々の手法は、「after」のような時間関係を明示的に示すマーカーの存在を利用することで、手作業によるコーディングの必要性を回避します。まず、時間マーカーで結び付けられた主節と従属節で学習したモデルが、時間推論をシミュレートする擬似曖昧性解消タスクにおいて良好なパフォーマンスを達成することを示します（テスト中、時間マーカーは未知数として扱われ、モデルは候補セットから適切なマーカーを選択する必要があります）。次に、提案されたアプローチが時間アノテーションの半自動作成に有望かどうかを評価し、具体的には、ノイズの多い近似データ（すなわち、主節と従属節）で学習したモデルを用いて、豊富な時間情報をアノテーションしたコーパスであるTimeBankに存在する文内関係を予測します。実験では、特徴空間、言語的仮定、データ要件が異なる複数の確率モデルを比較対照します。ゴールドスタンダードコーパスと被験者に対するパフォーマンスを評価します。
Uncertainty in Soft Temporal Constraint Problems:A General Framework and Controllability Algorithms forThe Fuzzy Case
ソフトな時間制約問題における不確実性：ファジィケースのための一般的な枠組みと可制御性アルゴリズム
In real-life temporal scenarios, uncertainty and preferences are often essential and coexisting aspects. We present a formalism where quantitative temporal constraints with both preferences and uncertainty can be defined. We show how three classical notions of controllability (that is, strong, weak, and dynamic), which have been developed for uncertain temporal problems, can be generalized to handle preferences as well. After defining this general framework, we focus on problems where preferences follow the fuzzy approach, and with properties that assure tractability. For such problems, we propose algorithms to check the presence of the controllability properties. In particular, we show that in such a setting dealing simultaneously with preferences and uncertainty does not increase the complexity of controllability testing. We also develop a dynamic execution algorithm, of polynomial complexity, that produces temporal plans under uncertainty that are optimal with respect to fuzzy preferences.
実際の時間的シナリオでは、不確実性と選好はしばしば不可欠であり、共存する側面です。選好と不確実性の両方を備えた定量的な時間的制約を定義できる形式主義を提示します。不確実な時間的問題のために開発された3つの古典的な制御可能性の概念（強い制御可能性、弱い制御可能性、そして動的制御可能性）を、選好にも適用できるよう一般化する方法を示す。この一般的な枠組みを定義した後、選好がファジィアプローチに従い、かつ扱いやすさを保証する特性を持つ問題に焦点を当てる。このような問題に対して、制御可能性特性の存在を確認するためのアルゴリズムを提案します。特に、このような設定において選好と不確実性を同時に扱うことで、制御可能性の検証の複雑さが増大しないことを示す。また、不確実性の下でファジィ選好に関して最適な時間的計画を生成する、多項式計算量の動的実行アルゴリズムも開発します。
Understanding Algorithm Performance on an Oversubscribed Scheduling Application
オーバーサブスクリプションスケジューリングアプリケーションにおけるアルゴリズム性能の理解
The best performing algorithms for a particular oversubscribedscheduling application, Air Force Satellite Control Network (AFSCN) scheduling, appear to have little in common. Yet, through careful experimentation and modeling of performance in real problem instances, we can relate characteristics of the best algorithms to characteristics of the application. In particular, we find that plateaus dominate the search spaces (thus favoring algorithms that make larger changes to solutions) and that some randomization in exploration is critical to good performance (due to the lack of gradient information on the plateaus). Based on our explanations of algorithm performance, we develop a new algorithm that combines characteristics of the best performers; the new algorithm’s performance is better than the previous best. We show how hypothesis driven experimentation and search modeling can both explain algorithmperformance and motivate the design of a new algorithm.
特定のオーバーサブスクリプションスケジューリングアプリケーションである空軍衛星管制ネットワーク（AFSCN）スケジューリングにおいて、最も優れたパフォーマンスを発揮するアルゴリズムには共通点がほとんどないように見えます。しかし、実際の問題インスタンスにおけるパフォーマンスの慎重な実験とモデリングを通じて、最適なアルゴリズムの特性とアプリケーションの特性を関連付けることができます。特に、プラトーが探索空間を支配していること（したがって、解に大きな変更を加えるアルゴリズムが有利になる）、および探索におけるある程度のランダム化が良好なパフォーマンスに不可欠であること（プラトー上の勾配情報がないため）がわかりました。アルゴリズムのパフォーマンスに関する説明に基づいて、最高のパフォーマンスを発揮するアルゴリズムの特性を組み合わせた新しいアルゴリズムを開発しました。新しいアルゴリズムのパフォーマンスは、以前の最高のアルゴリズムよりも優れています。仮説駆動型の実験と探索モデリングが、アルゴリズムのパフォーマンスを説明し、新しいアルゴリズムの設計を促進する方法を示します。
Causes of Ineradicable Spurious Predictions in Qualitative Simulation
定性シミュレーションにおける根絶不可能な誤った予測の原因
It was recently proved that a sound and complete qualitative simulator does not exist, that is, as long as the input-output vocabulary of the state-of-the-art QSIM algorithm is used, there will always be input models which cause any simulator with a coverage guarantee to make spurious predictions in its output. In this paper, we examine whether a meaningfully expressive restriction of this vocabulary is possible so that one can build a simulator with both the soundness and completeness properties. We prove several negative results: All sound qualitative simulators, employing subsets of the QSIM representation which retain the operating region transition feature, and support at least the addition and constancy constraints, are shown to be inherently incomplete. Even when the simulations are restricted to run in a single operating region, a constraint vocabulary containing just the addition, constancy, derivative, and multiplication relations makes the construction of sound and complete qualitative simulators impossible.
最近、健全かつ完全な定性シミュレータは存在しないことが証明されました。つまり、最先端のQSIMアルゴリズムの入出力語彙が使用されている限り、カバレッジ保証付きのシミュレータであっても、出力において誤った予測を行う入力モデルが常に存在するということです。本稿では、健全性と完全性の両方の特性を備えたシミュレータを構築できるように、この語彙を意味のある表現力で制限することが可能かどうかを検証します。その結果、いくつかの否定的な結果が示されました。動作領域遷移機能を保持し、少なくとも加算制約と不変制約をサポートするQSIM表現のサブセットを使用するすべての健全な定性シミュレータは、本質的に不完全であることが示されました。シミュレーションが単一の動作領域で実行されるように制限されている場合でも、加算、不変、微分、乗算関係のみを含む制約語彙では、健全かつ完全な定性シミュレータの構築は不可能です。
Cognitive Principles in Robust Multimodal Interpretation
ロバストなマルチモーダル解釈における認知原理
Multimodal conversational interfaces provide a natural means for users to communicate with computer systems through multiple modalities such as speech and gesture. To build effective multimodal interfaces, automated interpretation of user multimodal inputs is important. Inspired by the previous investigation on cognitive status in multimodal human machine interaction, we have developed a greedy algorithm for interpreting user referring expressions (i.e., multimodal reference resolution). This algorithm incorporates the cognitive principles of Conversational Implicature and Givenness Hierarchy and applies constraints from various sources (e.g., temporal, semantic, and contextual) to resolve references. Our empirical results have shown the advantage of this algorithm in efficiently resolving a variety of user references. Because of its simplicity and generality, this approach has the potential to improve the robustness of multimodal input interpretation.
マルチモーダル会話型インターフェースは、ユーザーが音声やジェスチャーなどの複数のモダリティを通じてコンピュータシステムとコミュニケーションするための自然な手段を提供します。効果的なマルチモーダルインターフェースを構築するには、ユーザーのマルチモーダル入力を自動的に解釈することが重要です。マルチモーダル・ヒューマンマシンインタラクションにおける認知状態に関する先行研究に着想を得て、ユーザーの参照表現を解釈するための貪欲アルゴリズム（すなわち、マルチモーダル参照解決）を開発しました。このアルゴリズムは、会話的含意と与えられたものの階層構造という認知原理を組み込んでおり、様々な情報源（例えば、時間的、意味的、文脈的）からの制約を適用して参照を解決します。実験結果から、このアルゴリズムは多様なユーザー参照を効率的に解決できることが示されました。このアプローチはシンプルで汎用性が高いため、マルチモーダル入力解釈の堅牢性を向上させる可能性を秘めています。
Resource Allocation Among Agents with MDP-Induced Preferences
MDP誘導選好を持つエージェント間の資源配分
Allocating scarce resources among agents to maximize global utility is, in general, computationally challenging. We focus on problems where resources enable agents to execute actions in stochastic environments, modeled as Markov decision processes (MDPs), such that the value of a resource bundle is defined as the expected value of the optimal MDP policy realizable given these resources. We present an algorithm that simultaneously solves the resource-allocation and the policy-optimization problems. This allows us to avoid explicitly representing utilities over exponentially many resource bundles, leading to drastic (often exponential) reductions in computational complexity. We then use this algorithm in the context of self-interested agents to design a combinatorial auction for allocating resources. We empirically demonstrate the effectiveness of our approach by showing that it can, in minutes, optimally solve problems for which a straightforward combinatorial resource-allocation technique would require the agents to enumerate up to 2^100 resource bundles and the auctioneer to solve an NP-complete problem with an input of that size.
エージェント間で希少なリソースを割り当て、全体的効用を最大化することは、一般的に計算的に困難です。本稿では、マルコフ決定過程（MDP）としてモデル化された確率的環境において、リソースがエージェントに行動を実行させる問題に焦点を当てる。この場合、リソースバンドルの価値は、これらのリソースを与えられた場合に実現可能な最適なMDP方策の期待値として定義されます。我々は、資源割り当て問題とポリシー最適化問題を同時に解くアルゴリズムを提示します。これにより、指数関数的に多数の資源束に対する効用を明示的に表現する必要がなくなり、計算量を大幅に（多くの場合指数関数的に）削減できます。次に、このアルゴリズムを利己的エージェントのコンテキストで使用して、資源を割り当てるための組み合わせオークションを設計します。単純な組み合わせ資源割り当て手法では、エージェントが最大2^100個の資源束を列挙し、オークション主催者がそのサイズの入力でNP完全問題を解く必要がある問題を、この手法では数分で最適に解くことができることを示すことで、このアプローチの有効性を実証します。
Preference-based Search using Example-Critiquing with Suggestions
提案付き例批評を用いた選好に基づく検索
We consider interactive tools that help users search for their most preferred item in a large collection of options. In particular, we examine example-critiquing, a technique for enabling users to incrementally construct preference models by critiquing example options that are presented to them. We present novel techniques for improving the example-critiquing technology by adding suggestions to its displayed options. Such suggestions are calculated based on an analysis of users’ current preference model and their potential hidden preferences. We evaluate the performance of our model-based suggestion techniques with both synthetic and real users. Results show that such suggestions are highly attractive to users and can stimulate them to express more preferences to improve the chance of identifying their most preferred item by up to 78%.
膨大な選択肢の中から、ユーザーが最も好みのアイテムを探すのを支援するインタラクティブツールについて考察します。特に、提示された選択肢の例を批評することで、ユーザーが段階的に選好モデルを構築できるようにする手法である例批評について考察します。本稿では、表示された選択肢に提案を追加することで、例批評技術を改良する新しい手法を紹介します。提案は、ユーザーの現在の選好モデルと潜在的な潜在的選好の分析に基づいて算出されます。本稿では、モデルベースの提案手法の性能を、合成ユーザーと実ユーザーの両方で評価します。結果は、このような提案がユーザーにとって非常に魅力的であり、より多くの選好を表明するよう促すことで、最も好みのアイテムを特定する確率を最大78%向上させることができることを示した。
Set Intersection and Consistency in Constraint Networks
制約ネットワークにおける集合の交差と一貫性
In this paper, we show that there is a close relation between consistency in a constraint network and set intersection. A proof schema is provided as a generic way to obtain consistency properties from properties on set intersection. This approach not only simplifies the understanding of and unifies many existing consistency results, but also directs the study of consistency to that of set intersection properties in many situations, as demonstrated by the results on the convexity and tightness of constraints in this paper. Specifically, we identify a new class of tree convex constraints where local consistency ensures global consistency. This generalizes row convex constraints. Various consistency results are also obtained on constraint networks where only some, in contrast to all in the existing work,constraints are tight.
本稿では、制約ネットワークの一貫性と集合の交差の間に密接な関係があることを示す。集合の交差の特性から一貫性の特性を得るための一般的な方法として、証明スキームを提供します。このアプローチは、多くの既存の一貫性の結果の理解を簡素化し、統合するだけでなく、本稿で制約の凸性とタイトネスに関する結果が示すように、多くの状況において一貫性の研究を集合の交差の特性の研究へと導く。具体的には、局所的な一貫性がグローバルな一貫性を保証する新しいクラスの木凸制約を特定します。これは行凸制約を一般化します。既存の研究のすべてとは対照的に、一部の制約のみがタイトである制約ネットワークについても、様々な一貫性の結果が得られます。
FluCaP: A Heuristic Search Planner for First-Order MDPs
FluCaP：一次MDPのためのヒューリスティック探索プランナー
We present a heuristic search algorithm for solving first-order Markov Decision Processes (FOMDPs). Our approach combines first-order state abstraction that avoids evaluating states individually, and heuristic search that avoids evaluating all states. Firstly, in contrast to existing systems, which start with propositionalizing the FOMDP and then perform state abstraction on its propositionalized version we apply state abstraction directly on the FOMDP avoiding propositionalization. This kind of abstraction is referred to as first-order state abstraction. Secondly, guided by an admissible heuristic, the search is restricted to those states that are reachable from the initial state. We demonstrate the usefulness of the above techniques for solving FOMDPs with a system, referred to as FluCaP (formerly, FCPlanner), that entered the probabilistic track of the 2004 International Planning Competition (IPC’2004) and demonstrated an advantage over other planners on the problems represented in first-order terms.
我々は、一次マルコフ決定過程（FOMDP）を解くためのヒューリスティック探索アルゴリズムを提示します。我々のアプローチは、個々の状態の評価を回避する一次状態抽象化と、すべての状態の評価を回避するヒューリスティック探索を組み合わせたものです。まず、FOMDPを命題化することから始めて、その命題化されたバージョンに対して状態抽象化を行う既存のシステムとは対照的に、我々は命題化を回避するFOMDPに対して直接状態抽象化を適用します。この種の抽象化は一次状態抽象化と呼ばれます。次に、許容されるヒューリスティックに基づいて、探索は初期状態から到達可能な状態に限定されます。我々は、2004年国際計画コンペティション（IPC’2004）の確率トラックに出場し、一次項で表現される問題において他のプランナーよりも優れていることを示したFluCaP（旧称FCPlanner）と呼ばれるシステムを用いて、FOMDPを解くための上記手法の有用性を実証します。
Multi-Issue Negotiation with Deadlines
期限付き複数課題交渉
This paper studies bilateral multi-issue negotiation between self-interested autonomous agents. Now, there are a number of different procedures that can be used for this process; the three main ones being the package deal procedure in which all the issues are bundled and discussed together, the simultaneous procedure in which the issues are discussed simultaneously but independently of each other, and the sequential procedure in which the issues are discussed one after another. Since each of them yields a different outcome, a key problem is to decide which one to use in which circumstances. Specifically, we consider this question for a model in which the agents have time constraints (in the form of both deadlines and discount factors) and information uncertainty (in that the agents do not know the opponent’s utility function). For this model, we consider issues that are both independent and those that are interdependent and determine equilibria for each case for each procedure. In so doing, we show that the package deal is in fact the optimal procedure for each party. We then go on to show that, although the package deal may be computationally more complex than the other two procedures, it generates Pareto optimal outcomes (unlike the other two), it has similar earliest and latest possible times of agreement to the simultaneous procedure (which is better than the sequential procedure), and that it (like the other two procedures) generates a unique outcome only under certain conditions (which we define).
本論文は、利己的な自律エージェント間の二国間複数問題交渉を考察します。このプロセスには様々な手順が利用可能です。主なものとしては、全ての問題を一括して議論するパッケージディール手順、各問題を同時に、しかし独立して議論する同時手順、そして問題を一つずつ議論する逐次手順の3つが挙げられます。これらの手順はそれぞれ異なる結果をもたらすため、どの手順をどの状況で用いるかが重要な問題となります。具体的には、エージェントが時間的制約（期限と割引率の両方）と情報不確実性（エージェントが相手の効用関数を知らない）を持つモデルにおいてこの問題を検討します。このモデルでは、独立した問題と相互に依存する問題の両方を考慮し、それぞれの手順における各ケースの均衡を求める。その過程で、パッケージディールが各当事者にとって最適な手順であることを示す。次に、パッケージ取引は他の2つの手順よりも計算量が複雑になる可能性があるものの、パレート最適な結果を生成する（他の2つとは異なり）、同時手順と合意の可能な最早および最遅の時刻が類似する（同時手順は逐次手順よりも優れている）、そして（他の2つの手順と同様に）特定の条件（ここで定義する）においてのみ一意の結果を生成することを示す。
Anytime Point-Based Approximations for Large POMDPs
大規模POMDPに対するいつでも点ベースの近似
The Partially Observable Markov Decision Process has long been recognized as a rich framework for real-world planning and control problems, especially in robotics. However exact solutions in this framework are typically computationally intractable for all but the smallest problems. A well-known technique for speeding up POMDP solving involves performing value backups at specific belief points, rather than over the entire belief simplex. The efficiency of this approach, however, depends greatly on the selection of points. This paper presents a set of novel techniques for selecting informative belief points which work well in practice. The point selection procedure is combined with point-based value backups to form an effective anytime POMDP algorithm called Point-Based Value Iteration (PBVI). The first aim of this paper is to introduce this algorithm and present a theoretical analysis justifying the choice of belief selection technique. The second aim of this paper is to provide a thorough empirical comparison between PBVI and other state-of-the-art POMDP methods, in particular the Perseus algorithm, in an effort to highlight their similarities and differences. Evaluation is performed using both standard POMDP domains and realistic robotic tasks.
部分観測マルコフ決定過程（POMDP）は、特にロボット工学において、現実世界の計画および制御問題のための優れた枠組みとして長年認識されてきた。しかし、この枠組みにおける正確な解は、ごく小さな問題を除いて、通常は計算的に困難です。POMDPの解を高速化するためのよく知られた手法は、信念単体全体ではなく、特定の信念点で値のバックアップを実行することです。しかし、このアプローチの効率は、ポイントの選択に大きく依存します。本論文では、実用的に有効に機能する有益な信念点を選択するための一連の新しい手法を提示します。ポイント選択手順は、ポイントベースの値バックアップと組み合わせることで、ポイントベース値反復（PBVI）と呼ばれる効果的ないつでも実行可能なPOMDPアルゴリズムを形成します。本論文の第一の目的は、このアルゴリズムを紹介し、その信念選択手法の選択を正当化する理論分析を提示することです。第二の目的は、PBVIと他の最先端のPOMDP手法、特にPerseusアルゴリズムとの徹底的な実証的比較を行い、両者の類似点と相違点を明らかにすることです。評価は、標準的なPOMDPドメインと現実的なロボットタスクの両方を用いて実施しました。
Properties and Applications of Programs with Monotone and Convex Constraints
単調制約と凸制約を持つプログラムの特性と応用
We study properties of programs with monotone and convex constraints. We extend to these formalisms concepts and results from normal logic programming. They include the notions of strong and uniform equivalence with their characterizations, tight programs and Fages Lemma, program completion and loop formulas. Our results provide an abstract account of properties of some recent extensions of logic programming with aggregates, especially the formalism of lparse programs. They imply a method to compute stable models of lparse programs by means of off-the-shelf solvers of pseudo-boolean constraints, which is often much faster than the smodels system.
我々は、単調制約と凸制約を持つプログラムの特性を研究します。これらの形式主義に、通常の論理プログラミングの概念と結果を拡張します。これには、強い同値性と一様同値性の概念とその特徴付け、タイトプログラムとFagesの補題、プログラム補完とループ式が含まれます。我々の研究成果は、集約を用いた論理プログラミングの最近の拡張、特に線形パースプログラムの形式主義の特性について抽象的な説明を提供します。これらの結果は、擬似ブール制約の既成ソルバーを用いて線形パースプログラムの安定モデルを計算する手法を示唆しており、これは多くの場合、smodelsシステムよりもはるかに高速です。
Generative Prior Knowledge for Discriminative Classification
識別分類のための生成的事前知識
We present a novel framework for integrating prior knowledge into discriminative classifiers. Our framework allows discriminative classifiers such as Support Vector Machines (SVMs) to utilize prior knowledge specified in the generative setting. The dual objective of fitting the data and respecting prior knowledge is formulated as a bilevel program, which is solved (approximately) via iterative application of second-order cone programming. To test our approach, we consider the problem of using WordNet (a semantic database of English language) to improve low-sample classification accuracy of newsgroup categorization. WordNet is viewed as an approximate, but readily available source of background knowledge, and our framework is capable of utilizing it in a flexible way.
我々は、事前知識を識別分類器に統合するための新たな枠組みを提示します。この枠組みにより、サポートベクターマシン（SVM）などの識別分類器は、生成設定で指定された事前知識を活用できるようになります。データのフィッティングと事前知識の尊重という二つの目的は、二層計画法として定式化され、二次円錐計画法の反復適用によって（近似的に）解かれます。このアプローチをテストするために、WordNet（英語の意味データベース）を用いて、ニュースグループ分類の低サンプル分類精度を向上させる問題を考察します。WordNetは、近似的でありながら容易に利用可能な背景知識源とみなされており、我々の枠組みはそれを柔軟に活用することができます。
Modelling Mixed Discrete-Continuous Domains for Planning
計画のための離散・連続混合領域のモデリング
In this paper we present pddl+, a planning domain description language for modelling mixed discrete-continuous planning domains. We describe the syntax and modelling style of pddl+, showing that the language makes convenient the modelling of complex time-dependent effects. We provide a formal semantics for pddl+ by mapping planning instances into constructs of hybrid automata. Using the syntax of HAs as our semantic model we construct a semantic mapping to labelled transition systems to complete the formal interpretation of pddl+ planning instances. An advantage of building a mapping from pddl+ to HA theory is that it forms a bridge between the Planning and Real Time Systems research communities. One consequence is that we can expect to make use of some of the theoretical properties of HAs. For example, for a restricted class of HAs the Reachability problem (which is equivalent to Plan Existence) is decidable. pddl+ provides an alternative to the continuous durative action model of pddl2.1, adding a more flexible and robust model of time-dependent behaviour.
本稿では、離散・連続混合プランニングドメインをモデリングするためのプランニングドメイン記述言語pddl+を紹介します。pddl+の構文とモデリングスタイルを説明し、この言語が複雑な時間依存効果のモデリングを容易にすることを示します。プランニングインスタンスをハイブリッドオートマトンの構成にマッピングすることにより、pddl+の形式意味論を提供します。HAの構文を意味モデルとして使用し、ラベル付き遷移システムへの意味マッピングを構築して、pddl+プランニングインスタンスの形式解釈を完成させます。pddl+からHA理論へのマッピングを構築する利点は、計画システムとリアルタイムシステムの研究コミュニティの架け橋となることです。その結果、HAの理論的特性の一部を活用できるようになることが期待できます。例えば、HAの限定されたクラスでは、到達可能性問題（計画の存在問題と同等）は決定可能です。pddl+は、pddl2.1の継続的持続アクションモデルに代わる選択肢を提供し、より柔軟で堅牢な時間依存動作モデルを追加します。
Active Learning with Multiple Views
複数の視点を用いた能動学習
Active learners alleviate the burden of labeling large amounts of data by detecting and asking the user to label only the most informative examples in the domain. We focus here on active learning for multi-view domains, in which there are several disjoint subsets of features (views), each of which is sufficient to learn the target concept. In this paper we make several contributions. First, we introduce Co-Testing, which is the first approach to multi-view active learning. Second, we extend the multi-view learning framework by also exploiting weak views, which are adequate only for learning a concept that is more general/specific than the target concept. Finally, we empirically show that Co-Testing outperforms existing active learners on a variety of real world domains such as wrapper induction, Web page classification, advertisement removal, and discourse tree parsing.
能動学習者は、ドメイン内で最も有益な例を検出し、ユーザーにラベル付けを依頼することで、大量のデータのラベル付けの負担を軽減します。ここでは、複数の互いに素な特徴のサブセット（ビュー）があり、それぞれが対象概念を学習するのに十分なマルチビュードメインの能動学習に焦点を当てます。本稿では、いくつかの貢献をします。まず、マルチビュー能動学習への最初のアプローチであるCo-Testingを紹介します。次に、対象概念よりも一般性/特異性が高い概念を学習する場合にのみ適切な弱ビューも活用することで、マルチビュー学習フレームワークを拡張します。最後に、Co-Testingが、ラッパー誘導、Webページ分類、広告除去、談話木解析など、さまざまな実世界のドメインにおいて既存の能動学習器よりも優れていることを実証的に示します。
Solving Factored MDPs with Hybrid State and Action Variables
ハイブリッドな状態変数と行動変数を用いた因子分解MDPの解法
Efficient representations and solutions for large decision problems with continuous and discrete variables are among the most important challenges faced by the designers of automated decision support systems. In this paper, we describe a novel hybrid factored Markov decision process (MDP) model that allows for a compact representation of these problems, and a new hybrid approximate linear programming (HALP) framework that permits their efficient solutions. The central idea of HALP is to approximate the optimal value function by a linear combination of basis functions and optimize its weights by linear programming. We analyze both theoretical and computational aspects of this approach, and demonstrate its scale-up potential on several hybrid optimization problems.
連続変数と離散変数を含む大規模意思決定問題の効率的な表現と解法は、自動意思決定支援システムの設計者が直面する最も重要な課題の一つです。本稿では、これらの問題をコンパクトに表現できる新しいハイブリッド因子マルコフ決定過程（MDP）モデルと、それらの効率的な解法を可能にする新しいハイブリッド近似線形計画法（HALP）フレームワークについて説明します。HALPの中心的なアイデアは、最適値関数を基底関数の線形結合で近似し、その重みを線形計画法によって最適化することです。本稿では、このアプローチの理論的側面と計算的側面の両方を分析し、いくつかのハイブリッド最適化問題におけるスケールアップの可能性を示します。
A Comparison of Different Machine Transliteration Models
異なる機械翻字モデルの比較
Machine transliteration is a method for automatically converting words in one language into phonetically equivalent ones in another language. Machine transliteration plays an important role in natural language applications such as information retrieval and machine translation, especially for handling proper nouns and technical terms. Four machine transliteration models — grapheme-based transliteration model, phoneme-based transliteration model, hybrid transliteration model, and correspondence-based transliteration model — have been proposed by several researchers. To date, however, there has been little research on a framework in which multiple transliteration models can operate simultaneously. Furthermore, there has been no comparison of the four models within the same framework and using the same data. We addressed these problems by 1) modeling the four models within the same framework, 2) comparing them under the same conditions, and 3) developing a way to improve machine transliteration through this comparison. Our comparison showed that the hybrid and correspondence-based models were the most effective and that the four models can be used in a complementary manner to improve machine transliteration performance.
機械翻字は、ある言語の単語を別の言語の音韻的に等価な単語に自動的に変換する方法です。機械翻字は、情報検索や機械翻訳などの自然言語アプリケーションにおいて、特に固有名詞や専門用語の扱いにおいて重要な役割を果たしています。これまでに、書記素ベース翻字モデル、音素ベース翻字モデル、ハイブリッド翻字モデル、対応ベース翻字モデルの4つの機械翻字モデルが複数の研究者によって提案されています。しかし、これまで、複数の翻字モデルを同時に動作させることができるフレームワークに関する研究はほとんど行われていません。さらに、同じフレームワーク内で同じデータを使用して、4つのモデルを比較した研究もありません。これらの問題に対処するため、1) 4つのモデルを同一の枠組みでモデル化し、2)同一条件下で比較し、3)この比較を通して機械翻字を改善する方法を開発しました。その結果、ハイブリッドモデルと対応ベースモデルが最も効果的であり、4つのモデルを補完的に使用することで機械翻字の性能を向上できることが示されました。
A Variational Inference Procedure Allowing Internal Structure for Overlapping Clusters and Deterministic Constraints
重複クラスターと決定論的制約のための内部構造を許容する変分推論手順
We develop a novel algorithm, called VIP*, for structured variational approximate inference. This algorithm extends known algorithms to allow efficient multiple potential updates for overlapping clusters, and overcomes the difficulties imposed by deterministic constraints. The algorithm’s convergence is proven and its applicability demonstrated for genetic linkage analysis.
構造化変分近似推論用のVIP*と呼ばれる新しいアルゴリズムを開発します。このアルゴリズムは、既知のアルゴリズムを拡張し、重複するクラスターに対して効率的な多重ポテンシャル更新を可能にし、決定論的制約によって生じる困難を克服します。このアルゴリズムの収束性は実証されており、遺伝子連鎖解析への適用性も実証されています。