Learning to Play Using Low-Complexity Rule-Based Policies: Illustrations through Ms. Pac-Man
低複雑度のルールベースポリシーを用いた遊び方を学ぶ：Ms. Pac-Manによる例
In this article we propose a method that can deal with certain combinatorial reinforcement learning tasks. We demonstrate the approach in the popular Ms. Pac-Man game. We define a set of high-level observation and action modules, from which rule-based policies are constructed automatically. In these policies, actions are temporally extended, and may work concurrently. The policy of the agent is encoded by a compact decision list. The components of the list are selected from a large pool of rules, which can be either hand-crafted or generated automatically. A suitable selection of rules is learnt by the cross-entropy method, a recent global optimization algorithm that fits our framework smoothly. Cross-entropy-optimized policies perform better than our hand-crafted policy, and reach the score of average human players. We argue that learning is successful mainly because (i) policies may apply concurrent actions and thus the policy space is sufficiently rich, (ii) the search is biased towards low-complexity policies and therefore, solutions with a compact description can be found quickly if they exist.
本稿では、特定の組み合わせ強化学習タスクに対応できる手法を提案します。この手法を、人気ゲーム「Ms. Pac-Man」を用いて実証します。高水準の観測モジュールと行動モジュールのセットを定義し、それらからルールベースのポリシーを自動的に構築します。これらのポリシーでは、行動は時間的に拡張され、同時に実行される可能性があります。エージェントのポリシーは、コンパクトな決定リストによって符号化されます。リストの構成要素は、手作業で作成することも自動生成することもできる膨大なルールプールから選択されます。適切なルールの選択は、我々のフレームワークにスムーズに適合する最新のグローバル最適化アルゴリズムであるクロスエントロピー法によって学習されます。クロスエントロピー最適化されたポリシーは、手作業で作成したポリシーよりも優れたパフォーマンスを発揮し、平均的な人間プレイヤーのスコアに達します。学習が成功する主な理由は、(i)ポリシーが同時行動を適用する可能性があるため、ポリシー空間が十分に豊富であること、(ii)探索が低複雑度のポリシーに偏っているため、コンパクトな記述を持つ解が存在する場合は迅速に発見できることです。
Query-time Entity Resolution
クエリタイムエンティティ解決
Entity resolution is the problem of reconciling database references corresponding to the same real-world entities. Given the abundance of publicly available databases that have unresolved entities, we motivate the problem of query-time entity resolution quick and accurate resolution for answering queries over such `unclean’ databases at query-time. Since collective entity resolution approaches — where related references are resolved jointly — have been shown to be more accurate than independent attribute-based resolution for off-line entity resolution, we focus on developing new algorithms for collective resolution for answering entity resolution queries at query-time. For this purpose, we first formally show that, for collective resolution, precision and recall for individual entities follow a geometric progression as neighbors at increasing distances are considered. Unfolding this progression leads naturally to a two stage `expand and resolve’ query processing strategy. In this strategy, we first extract the related records for a query using two novel expansion operators, and then resolve the extracted records collectively. We then show how the same strategy can be adapted for query-time entity resolution by identifying and resolving only those database references that are the most helpful for processing the query. We validate our approach on two large real-world publication databases where we show the usefulness of collective resolution and at the same time demonstrate the need for adaptive strategies for query processing. We then show how the same queries can be answered in real-time using our adaptive approach while preserving the gains of collective resolution. In addition to experiments on real datasets, we use synthetically generated data to empirically demonstrate the validity of the performance trends predicted by our analysis of collective entity resolution over a wide range of structural characteristics in the data.
エンティティ解決とは、現実世界の同一のエンティティに対応するデータベース参照を整合させる問題です。未解決のエンティティを持つ公開データベースが多数存在することを鑑み、我々は、クエリ時にそのような「不正確な」データベースに対するクエリに迅速かつ正確に回答するための、クエリ時のエンティティ解決という問題を提起します。関連する参照をまとめて解決する集合的エンティティ解決アプローチは、オフラインのエンティティ解決において、独立した属性ベースの解決よりも精度が高いことが示されているため、我々はクエリ時にエンティティ解決クエリに応答するための集合的解決のための新しいアルゴリズムの開発に焦点を当てます。この目的のために、まず、集合的解決において、個々のエンティティの適合率と再現率は、距離が増加する近傍エンティティを考慮するにつれて等比級数的に増加することを正式に示します。この等比級数を解明することで、2段階の「展開と解決」クエリ処理戦略が自然に導き出されます。この戦略では、まず2つの新しい展開演算子を用いてクエリの関連レコードを抽出し、次に抽出されたレコードを集合的に解決します。次に、クエリ処理に最も役立つデータベース参照のみを識別して解決することにより、同じ戦略をクエリ時のエンティティ解決に適用できることを示します。2つの大規模な実世界出版物データベースでこのアプローチを検証し、集合的解決の有用性を示すと同時に、クエリ処理における適応型戦略の必要性を示します。次に、適応型アプローチを用いて、集合的エンティティ解決のメリットを維持しながら、同じクエリにリアルタイムで回答できることを示します。実際のデータセットでの実験に加え、合成生成データを用いて、データの幅広い構造特性における集合的エンティティ解決の分析によって予測されるパフォーマンス傾向の妥当性を実証的に示します。
Probabilistic Planning via Heuristic Forward Search and Weighted Model Counting
ヒューリスティックフォワード探索と重み付きモデルカウントによる確率的計画
We present a new algorithm for probabilistic planning with no observability. Our algorithm, called Probabilistic-FF, extends the heuristic forward-search machinery of Conformant-FF to problems with probabilistic uncertainty about both the initial state and action effects. Specifically, Probabilistic-FF combines Conformant-FF’s techniques with a powerful machinery for weighted model counting in (weighted) CNFs, serving to elegantly define both the search space and the heuristic function. Our evaluation of Probabilistic-FF shows its fine scalability in a range of probabilistic domains, constituting a several orders of magnitude improvement over previous results in this area. We use a problematic case to point out the main open issue to be addressed by further research.
観測可能性のない確率的計画のための新しいアルゴリズムを紹介します。我々のアルゴリズム「Probabilistic-FF」は、Conformant-FFのヒューリスティックな前向き探索機構を、初期状態とアクション効果の両方に関する確率的不確実性を伴う問題に拡張します。具体的には、Probabilistic-FFはConformant-FFの手法と、（重み付き）CNFにおける重み付きモデルカウントのための強力な機構を組み合わせ、探索空間とヒューリスティック関数の両方を簡潔に定義します。Probabilistic-FFの評価では、様々な確率領域において優れたスケーラビリティを示し、この分野におけるこれまでの研究結果と比べて数桁の改善が見られます。我々は、問題のある事例を用いて、今後の研究で取り組むべき主要な未解決問題を指摘します。
A Framework for Kernel-Based Multi-Category Classification
カーネルベースのマルチカテゴリ分類のためのフレームワーク
A geometric framework for understanding multi-category classification is introduced, through which many existing ‘all-together’ algorithms can be understood. The structure enables parsimonious optimisation, through a direct extension of the binary methodology. The focus is on Support Vector Classification, with parallels drawn to related methods.The ability of the framework to compare algorithms is illustrated by a brief discussion of Fisher consistency. Its utility in improving understanding of multi-category analysis is demonstrated through a derivation of improved generalisation bounds.It is also described how this architecture provides insights regarding how to further improve on the speed of existing multi-category classification algorithms. An initial example of how this might be achieved is developed in the formulation of a straightforward multi-category Sequential Minimal Optimisation algorithm. Proof-of-concept experimental results have shown that this, combined with the mapping of pairwise results, is comparable with benchmark optimisation speeds.
マルチカテゴリ分類を理解するための幾何学的枠組みを導入し、これにより既存の多くの「総合的な」アルゴリズムを理解できるようになります。この構造は、バイナリ手法を直接拡張することで、簡潔な最適化を可能にします。サポートベクター分類に焦点を当て、関連手法との類似点を示します。この枠組みがアルゴリズムを比較できることは、フィッシャー整合性について簡単に説明することで示されます。マルチカテゴリ分析の理解を深める上での有用性は、改善された一般化境界の導出を通じて実証されます。また、このアーキテクチャが、既存のマルチカテゴリ分類アルゴリズムの速度をさらに向上させる方法に関する洞察をどのように提供するかについても説明します。これを実現する方法の最初の例として、単純なマルチカテゴリ逐次最小最適化アルゴリズムの定式化が開発されました。概念実証実験の結果、このアルゴリズムとペアワイズ結果のマッピングを組み合わせることで、ベンチマーク最適化速度に匹敵することが示されました。
Graph Abstraction in Real-time Heuristic Search
リアルタイムヒューリスティック探索におけるグラフ抽象化
Real-time heuristic search methods are used by situated agents in applications that require the amount of planning per move to be independent of the problem size. Such agents plan only a few actions at a time in a local search space and avoid getting trapped in local minima by improving their heuristic function over time. We extend a wide class of real-time search algorithms with automatically-built state abstraction and prove completeness and convergence of the resulting family of algorithms. We then analyze the impact of abstraction in an extensive empirical study in real-time pathfinding. Abstraction is found to improve efficiency by providing better trading offs between planning time, learning speed and other negatively correlated performance measures.
リアルタイムヒューリスティック探索法は、問題のサイズに依存しない移動ごとの計画量を必要とするアプリケーションにおいて、状況依存エージェントによって使用されます。このようなエージェントは、局所探索空間において一度に少数の行動のみを計画し、時間の経過とともにヒューリスティック関数を改善することで局所最小値に陥ることを回避します。我々は、自動構築された状態抽象化を用いて、幅広いリアルタイム探索アルゴリズムを拡張し、結果として得られるアルゴリズム群の完全性と収束性を証明します。次に、リアルタイム経路探索における広範な実証研究において、抽象化の影響を分析します。抽象化は、計画時間、学習速度、およびその他の負の相関を持つ性能指標間のトレードオフを改善することで、効率を向上させることがわかっています。
On the Semantics of Logic Programs with Preferences
選好を持つ論理プログラムの意味論について
This work is a contribution to prioritized reasoning in logic programming in the presence of preference relations involving atoms. The technique, providing a new interpretation for prioritized logic programs, is inspired by the semantics of Prioritized Logic Programming and enriched with the use of structural information of preference of Answer Set Optimization Programming. Specifically, the analysis of the logic program is carried out together with the analysis of preferences in order to determine the choice order and the sets of comparable models. The new semantics is compared with other approaches known in the literature and complexity analysis is also performed, showing that, with respect to other similar approaches previously proposed, the complexity of computing preferred stable models does not increase.
本研究は、原子を含む選好関係がある場合の論理プログラミングにおける優先順位付け推論への貢献です。優先順位付け論理プログラムに新しい解釈を提供するこの手法は、優先順位付け論理プログラミングのセマンティクスに着想を得ており、回答セット最適化プログラミングの選好の構造情報を使用することで強化されています。具体的には、選択順序と比較可能なモデルのセットを決定するために、論理プログラムの分析は選好の分析と組み合わせて実行されます。新しいセマンティクスは文献で知られている他のアプローチと比較され、複雑性分析も行われ、これまで提案された他の同様のアプローチと比較して、好ましい安定モデルの計算複雑性は増加しないことが示されています。
Using Linguistic Cues for the Automatic Recognition of Personality in Conversation and Text
会話とテキストにおける性格の自動認識のための言語的手がかりの利用
It is well known that utterances convey a great deal of information about the speaker in addition to their semantic content. One such type of information consists of cues to the speaker’s personality traits, the most fundamental dimension of variation between humans. Recent work explores the automatic detection of other types of pragmatic variation in text and conversation, such as emotion, deception, speaker charisma, dominance, point of view, subjectivity, opinion and sentiment. Personality affects these other aspects of linguistic production, and thus personality recognition may be useful for these tasks, in addition to many other potential applications. However, to date, there is little work on the automatic recognition of personality traits. This article reports experimental results for recognition of all Big Five personality traits, in both conversation and text, utilising both self and observer ratings of personality. While other work reports classification results, we experiment with classification, regression and ranking models. For each model, we analyse the effect of different feature sets on accuracy. Results show that for some traits, any type of statistical model performs significantly better than the baseline, but ranking models perform best overall. We also present an experiment suggesting that ranking models are more accurate than multi-class classifiers for modelling personality. In addition, recognition models trained on observed personality perform better than models trained using self-reports, and the optimal feature set depends on the personality trait. A qualitative analysis of the learned models confirms previous findings linking language and personality, while revealing many new linguistic markers.
発話は、その意味内容に加えて、話者に関する多くの情報を伝えることがよく知られています。そのような情報の一つに、話者の性格特性を示す手がかりがあります。これは、人間間の差異の最も基本的な側面です。最近の研究では、感情、欺瞞、話者のカリスマ性、支配性、視点、主観性、意見、感情など、テキストや会話における他の種類の実用的な差異の自動検出が検討されています。性格は言語生成のこれらの他の側面に影響を及ぼすため、性格認識はこれらのタスクだけでなく、他の多くの潜在的な用途にも役立つ可能性があります。しかし、これまでのところ、性格特性の自動認識に関する研究はほとんどありません。本稿では、会話とテキストの両方において、自己と観察者による性格評価の両方を用いて、ビッグファイブのすべての性格特性を認識した実験結果を報告します。他の研究では分類結果が報告されているが、本稿では分類、回帰、ランキングモデルを用いて実験を行う。各モデルについて、異なる特徴セットが精度に与える影響を分析します。結果は、いくつかの特性については、あらゆる種類の統計モデルがベースラインよりも大幅に優れたパフォーマンスを発揮するが、ランキングモデルが全体的に最も優れたパフォーマンスを発揮することを示しています。また、ランキングモデルは、性格をモデル化する上で多クラス分類器よりも正確であることを示唆する実験も示します。さらに、観察された性格に基づいてトレーニングされた認識モデルは、自己申告を使用してトレーニングされたモデルよりも優れたパフォーマンスを発揮し、最適な特徴セットは性格特性に依存します。学習済みモデルの定性分析は、言語と性格を関連付ける以前の研究結果を確認し、多くの新しい言語マーカーを明らかにしました。
Individual and Domain Adaptation in Sentence Planning for Dialogue
対話のための文計画における個人適応と領域適応
One of the biggest challenges in the development and deployment of spoken dialogue systems is the design of the spoken language generation module. This challenge arises from the need for the generator to adapt to many features of the dialogue domain, user population, and dialogue context. A promising approach is trainable generation, which uses general-purpose linguistic knowledge that is automatically adapted to the features of interest, such as the application domain, individual user, or user group. In this paper we present and evaluate a trainable sentence planner for providing restaurant information in the MATCH dialogue system. We show that trainable sentence planning can produce complex information presentations whose quality is comparable to the output of a template-based generator tuned to this domain. We also show that our method easily supports adapting the sentence planner to individuals, and that the individualized sentence planners generally perform better than models trained and tested on a population of individuals. Previous work has documented and utilized individual preferences for content selection, but to our knowledge, these results provide the first demonstration of individual preferences for sentence planning operations, affecting the content order, discourse structure and sentence structure of system responses. Finally, we evaluate the contribution of different feature sets, and show that, in our application, n-gram features often do as well as features based on higher-level linguistic representations.
音声対話システムの開発と展開における最大の課題の1つは、音声言語生成モジュールの設計です。この課題は、生成器が対話ドメイン、ユーザー層、および対話コンテキストの多くの特徴に適応する必要があることから生じます。有望なアプローチの一つとして、学習可能な生成があります。これは、アプリケーションドメイン、個々のユーザー、ユーザーグループといった関心対象の特徴に自動的に適応する汎用的な言語知識を用いるものです。本稿では、MATCH対話システムにおいてレストラン情報を提供するための学習可能な文プランナーを提示し、評価します。学習可能な文プランナーは、このドメイン向けに調整されたテンプレートベースの生成器の出力に匹敵する品質の複雑な情報提示を生成できることを示します。また、本手法は文プランナーを個人に容易に適応させること、そして個人化された文プランナーは、一般的に、個人集団で学習・テストされたモデルよりも優れたパフォーマンスを発揮することを示します。これまでの研究では、コンテンツ選択における個人の嗜好が文書化され、利用されてきましたが、私たちの知る限り、これらの結果は、文プランニング操作における個人の嗜好が、システム応答のコンテンツ順序、談話構造、文構造に影響を与えることを初めて実証するものです。最後に、様々な特徴セットの貢献度を評価し、本アプリケーションにおいて、n-gram特徴が高レベル言語表現に基づく特徴と同等の性能を示すことが多いことを示します。
Natural Events
自然事象
This paper develops an inductive theory of predictive common sense reasoning. The theory provides the basis for an integrated solution to the three traditional problems of reasoning about change; the frame, qualification, and ramification problems. The theory is also capable of representing non-deterministic events, and it provides a means for stating defeasible preferences over the outcomes of conflicting simultaneous events.
本論文では、予測的常識推論の帰納的理論を展開します。この理論は、変化に関する推論における3つの伝統的な問題、すなわちフレーム問題、資格問題、および分岐問題に対する統合的な解決策の基礎を提供します。また、この理論は非決定論的な事象を表現することも可能であり、同時に発生する矛盾する事象の結果に対する取消可能な選好を表明する手段を提供します。
New Inference Rules for Max-SAT
Max-SATのための新しい推論規則
Exact Max-SAT solvers, compared with SAT solvers, apply little inference at each node of the proof tree. Commonly used SAT inference rules like unit propagation produce a simplified formula that preserves satisfiability but, unfortunately, solving the Max-SAT problem for the simplified formula is not equivalent to solving it for the original formula. In this paper, we define a number of original inference rules that, besides being applied efficiently, transform Max-SAT instances into equivalent Max-SAT instances which are easier to solve. The soundness of the rules, that can be seen as refinements of unit resolution adapted to Max-SAT, are proved in a novel and simple way via an integer programming transformation. With the aim of finding out how powerful the inference rules are in practice, we have developed a new Max-SAT solver, called MaxSatz, which incorporates those rules, and performed an experimental investigation. The results provide empirical evidence that MaxSatz is very competitive, at least, on random Max-2SAT, random Max-3SAT, Max-Cut, and Graph 3-coloring instances, as well as on the benchmarks from the Max-SAT Evaluation 2006.
正確なMax-SATソルバーは、SATソルバーと比較して、証明木の各ノードでほとんど推論を適用しません。ユニット伝播などの一般的に使用されるSAT推論規則は、充足可能性を維持する簡略化された式を生成しますが、残念ながら、簡略化された式のMax-SAT問題を解くことは、元の式で問題を解くことと同等ではありません。本稿では、効率的に適用されるだけでなく、Max-SATインスタンスをより簡単に解ける同等のMax-SATインスタンスに変換する、独自の推論規則をいくつか定義します。Max-SATに適応したユニット解決の改良と見なすことができるこの規則の健全性は、整数計画変換による新しく簡単な方法で証明されています。推論規則が実際にどれほど強力であるかを調べる目的で、これらの規則を組み込んだMaxSatzと呼ばれる新しいMax-SATソルバーを開発し、実験的調査を行いました。結果は、MaxSatzが、少なくともランダムMax-2SAT、ランダムMax-3SAT、Max-Cut、Graph 3-coloringのインスタンス、そしてMax-SAT Evaluation 2006のベンチマークにおいて、非常に競争力があることを実証的に証明しています。
Reasoning with Very Expressive Fuzzy Description Logics
非常に表現力豊かなファジィ記述論理による推論
It is widely recognized today that the management of imprecision and vagueness will yield more intelligent and realistic knowledge-based applications. Description Logics (DLs) are a family of knowledge representation languages that have gained considerable attention the last decade, mainly due to their decidability and the existence of empirically high performance of reasoning algorithms. In this paper, we extend the well known fuzzy ALC DL to the fuzzy SHIN DL, which extends the fuzzy ALC DL with transitive role axioms (S), inverse roles (I), role hierarchies (H) and number restrictions (N). We illustrate why transitive role axioms are difficult to handle in the presence of fuzzy interpretations and how to handle them properly. Then we extend these results by adding role hierarchies and finally number restrictions. The main contributions of the paper are the decidability proof of the fuzzy DL languages fuzzy-SI and fuzzy-SHIN, as well as decision procedures for the knowledge base satisfiability problem of the fuzzy-SI and fuzzy-SHIN.
不正確さと曖昧さを管理することで、よりインテリジェントで現実的な知識ベースアプリケーションが得られることは、今日広く認識されています。記述論理（DL）は、主にその決定可能性と経験的に高いパフォーマンスの推論アルゴリズムの存在により、過去10年間でかなりの注目を集めている知識表現言語ファミリーです。本稿では、よく知られているファジーALC DLをファジーSHIN DLに拡張します。これは、ファジーALC DLに推移的役割公理（S）、逆役割（I）、役割階層（H）、および数制限（N）を拡張したものです。ファジィ解釈が存在する場合、推移的役割公理の扱いがなぜ難しいのか、そしてどのように適切に扱うべきかを示す。次に、役割階層と数制限を追加することで、これらの結果を拡張します。本論文の主な貢献は、ファジィ階層的言語fuzzy-SIとfuzzy-SHINの決定可能性証明、およびfuzzy-SIとfuzzy-SHINの知識ベース充足可能性問題に対する決定手続きです。
Topic and Role Discovery in Social Networks with Experiments on Enron and Academic Email
エンロンと学術メールを用いた実験によるソーシャルネットワークにおけるトピックと役割の発見
Previous work in social network analysis (SNA) has modeled the existence of links from one entity to another, but not the attributes such as language content or topics on those links. We present the Author-Recipient-Topic (ART) model for social network analysis, which learns topic distributions based on the direction-sensitive messages sent between entities. The model builds on Latent Dirichlet Allocation (LDA) and the Author-Topic (AT) model, adding the key attribute that distribution over topics is conditioned distinctly on both the sender and recipient—steering the discovery of topics according to the relationships between people. We give results on both the Enron email corpus and a researcher’s email archive, providing evidence not only that clearly relevant topics are discovered, but that the ART model better predicts people’s roles and gives lower perplexity on previously unseen messages. We also present the Role-Author-Recipient-Topic (RART) model, an extension to ART that explicitly represents people’s roles.
ソーシャルネットワーク分析（SNA）におけるこれまでの研究では、あるエンティティから別のエンティティへのリンクの存在はモデル化されていましたが、それらのリンク上の言語コンテンツやトピックなどの属性はモデル化されていませんでした。本研究では、エンティティ間で送信される方向依存メッセージに基づいてトピック分布を学習する、ソーシャルネットワーク分析のための著者-受信者-トピック（ART）モデルを紹介します。このモデルは、潜在的ディリクレ配分（LDA）と著者-トピック（AT）モデルを基盤としており、トピックの分布が送信者と受信者の両方に明確に条件付けられるという重要な属性を追加しています。つまり、人々の関係性に基づいてトピックの発見を誘導します。我々は、エンロン社の電子メールコーパスと研究者の電子メールアーカイブの両方で結果を示し、明らかに関連性のあるトピックが発見されるだけでなく、ARTモデルが人々の役割をより正確に予測し、以前に見たことのないメッセージに対する困惑度が低いことを示す証拠を提供します。また、人々の役割を明示的に表すARTの拡張であるRole-Author-Recipient-Topic（RART）モデルも紹介します。
Compressed Pattern Databases
圧縮パターンデータベース
A pattern database (PDB) is a heuristic function implemented as a lookup table that stores the lengths of optimal solutions for subproblem instances. Standard PDBs have a distinct entry in the table for each subproblem instance. In this paper we investigate compressing PDBs by merging several entries into one, thereby allowing the use of PDBs that exceed available memory in their uncompressed form. We introduce a number of methods for determining which entries to merge and discuss their relative merits. These vary from domain-independent approaches that allow any set of entries in the PDB to be merged, to more intelligent methods that take into account the structure of the problem. The choice of the best compression method is based on domain-dependent attributes. We present experimental results on a number of combinatorial problems, including the four-peg Towers of Hanoi problem, the sliding-tile puzzles, and the Top-Spin puzzle. For the Towers of Hanoi, we show that the search time can be reduced by up to three orders of magnitude by using compressed PDBs compared to uncompressed PDBs of the same size. More modest improvements were observed for the other domains.
パターンデータベース(PDB)は、部分問題インスタンスの最適解の長さを格納するルックアップテーブルとして実装されたヒューリスティック関数です。標準的なPDBでは、各部分問題インスタンスごとにテーブル内に個別のエントリがあります。本稿では、複数のエントリを1つにマージすることでPDBを圧縮し、圧縮されていない形式では使用可能なメモリを超えるPDBを使用できるようにする方法について検討します。マージするエントリを決定するいくつかの方法を紹介し、それらの相対的なメリットについて説明します。これらの方法は、PDB内の任意のエントリセットをマージできるドメインに依存しないアプローチから、問題の構造を考慮したよりインテリジェントな方法まで多岐にわたります。最適な圧縮方法の選択は、ドメイン依存の属性に基づいています。4つのペグを持つハノイの塔問題、スライディングタイルパズル、トップスピンパズルなど、いくつかの組み合わせ問題に関する実験結果を示します。ハノイの塔については、圧縮PDBを使用することで、同サイズの非圧縮PDBと比較して検索時間を最大3桁短縮できることを示します。他のドメインでは、より緩やかな改善が見られました。
Knowledge Derived From Wikipedia For Computing Semantic Relatedness
意味的関連性の計算のためのWikipediaからの知識
Wikipedia provides a semantic network for computing semantic relatedness in a more structured fashion than a search engine and with more coverage than WordNet. We present experiments on using Wikipedia for computing semantic relatedness and compare it to WordNet on various benchmarking datasets. Existing relatedness measures perform better using Wikipedia than a baseline given by Google counts, and we show that Wikipedia outperforms WordNet on some datasets. We also address the question whether and how Wikipedia can be integrated into NLP applications as a knowledge base. Including Wikipedia improves the performance of a machine learning based coreference resolution system, indicating that it represents a valuable resource for NLP applications. Finally, we show that our method can be easily used for languages other than English by computing semantic relatedness for a German dataset.
Wikipediaは、検索エンジンよりも構造化された方法で、かつWordNetよりも広いカバレッジで、意味的関連性を計算するためのセマンティックネットワークを提供します。本稿では、意味的関連性を計算するためにWikipediaを用いた実験を示し、様々なベンチマークデータセットにおいてWordNetと比較します。既存の関連性指標は、Googleのカウントによって提供されるベースラインよりもWikipediaを用いた方が優れたパフォーマンスを示し、一部のデータセットにおいてはWikipediaがWordNetよりも優れていることを示す。また、Wikipediaを知識ベースとしてNLPアプリケーションに統合できるかどうか、またどのように統合できるかという問題にも取り組む。Wikipediaを組み込むことで、機械学習ベースの共参照解決システムのパフォーマンスが向上し、NLPアプリケーションにとって貴重なリソースとなることが示唆されます。最後に、ドイツ語のデータセットの意味的関連性を計算することで、本手法が英語以外の言語にも容易に適用できることを示す。
Chain: A Dynamic Double Auction Framework for Matching Patient Agents
Chain：患者エージェントのマッチングのための動的ダブルオークションフレームワーク
In this paper we present and evaluate a general framework for the design of truthful auctions for matching agents in a dynamic, two-sided market. A single commodity, such as a resource or a task, is bought and sold by multiple buyers and sellers that arrive and depart over time. Our algorithm, Chain, provides the first framework that allows a truthful dynamic double auction (DA) to be constructed from a truthful, single-period (i.e. static) double-auction rule. The pricing and matching method of the Chain construction is unique amongst dynamic-auction rules that adopt the same building block. We examine experimentally the allocative efficiency of Chain when instantiated on various single-period rules, including the canonical McAfee double-auction rule. For a baseline we also consider non-truthful double auctions populated with “zero-intelligence plus”-style learning agents. Chain-based auctions perform well in comparison with other schemes, especially as arrival intensity falls and agent valuations become more volatile.
本稿では、動的な二面性市場におけるマッチングエージェントのための誠実なオークション設計のための一般的なフレームワークを提示し、評価します。リソースやタスクといった単一の商品は、時間の経過とともに到着および出発する複数の買い手と売り手によって売買されます。我々のアルゴリズムChainは、誠実な単一期間（すなわち静的）ダブルオークションルールから誠実な動的ダブルオークション（DA）を構築できる初のフレームワークを提供します。Chainの構築における価格設定とマッチングの手法は、同じ構成要素を採用する動的オークションルールの中では他に類を見ない。我々は、標準的なMcAfeeダブルオークションルールを含む様々な単一期間ルールにChainを実装した場合の配分効率を実験的に検証します。ベースラインとして、「ゼロインテリジェンスプラス」型学習エージェントを用いた非真実ダブルオークションも検討します。チェーンベースオークションは、他の手法と比較して、特に到着頻度が低下し、エージェントの評価がより不安定になる場合に優れたパフォーマンスを示す。
The Planning Spectrum – One, Two, Three, Infinity
プランニングスペクトル – 1、2、3、無限
Linear Temporal Logic (LTL) is widely used for defining conditions on the execution paths of dynamic systems. In the case of dynamic systems that allow for nondeterministic evolutions, one has to specify, along with an LTL formula f, which are the paths that are required to satisfy the formula. Two extreme cases are the universal interpretation A.f, which requires that the formula be satisfied for all execution paths, and the existential interpretation E.f, which requires that the formula be satisfied for some execution path.When LTL is applied to the definition of goals in planning problems on nondeterministic domains, these two extreme cases are too restrictive. It is often impossible to develop plans that achieve the goal in all the nondeterministic evolutions of a system, and it is too weak to require that the goal is satisfied by some execution.In this paper we explore alternative interpretations of an LTL formula that are between these extreme cases. We define a new language that permits an arbitrary combination of the A and E quantifiers, thus allowing, for instance, to require that each finite execution can be extended to an execution satisfying an LTL formula (AE.f), or that there is some finite execution whose extensions all satisfy an LTL formula (EA.f). We show that only eight of these combinations of path quantifiers are relevant, corresponding to an alternation of the quantifiers of length one (A and E), two (AE and EA), three (AEA and EAE), and infinity ((AE)* and (EA)*). We also present a planning algorithm for the new language that is based on an automata-theoretic approach, and study its complexity.
線形時相論理（LTL）は、動的システムの実行パスの条件定義に広く用いられています。非決定性進化を許容する動的システムの場合、LTL式fとともに、その式を満たすために必要なパスを指定する必要があります。2つの極端なケースとして、すべての実行パスで式が満たされることを要求する普遍解釈A.fと、何らかの実行パスで式が満たされることを要求する存在解釈E.fがあります。LTLを非決定性領域の計画問題における目標定義に適用する場合、これら2つの極端なケースは制限が厳しすぎます。システムのすべての非決定性進化において目標を達成する計画を作成することはしばしば不可能であり、また、何らかの実行によって目標が満たされることを要求するのは不十分です。本稿では、これらの極端なケースの中間に位置するLTL式の代替解釈を検討します。我々は、A量指定子とE量指定子の任意の組み合わせを許容する新しい言語を定義します。これにより、例えば、各有限実行がLTL式(AE.f)を満たす実行に拡張可能であること、あるいは拡張がすべてLTL式(EA.f)を満たす有限実行が存在することを要求できるようになります。これらのパス量指定子の組み合わせのうち、長さ1 (AとE)、長さ2 (AEとEA)、長さ3 (AEAとEAE)、および無限大((AE)*と(EA)*)の量指定子の交代に対応する8種類のみが適切であることを示す。また、オートマトン理論的アプローチに基づくこの新しい言語の計画アルゴリズムを提示し、その複雑性について考察します。
Learning Semantic Definitions of Online Information Sources
オンライン情報源の意味的定義の学習
The Internet contains a very large number of information sources providing many types of data from weather forecasts to travel deals and financial information. These sources can be accessed via Web-forms, Web Services, RSS feeds and so on. In order to make automated use of these sources, we need to model them semantically, but writing semantic descriptions for Web Services is both tedious and error prone. In this paper we investigate the problem of automatically generating such models. We introduce a framework for learning Datalog definitions of Web sources. In order to learn these definitions, our system actively invokes the sources and compares the data they produce with that of known sources of information. It then performs an inductive logic search through the space of plausible source definitions in order to learn the best possible semantic model for each new source. In this paper we perform an empirical evaluation of the system using real-world Web sources. The evaluation demonstrates the effectiveness of the approach, showing that we can automatically learn complex models for real sources in reasonable time. We also compare our system with a complex schema matching system, showing that our approach can handle the kinds of problems tackled by the latter.
インターネットには、天気予報から旅行情報、金融情報まで、多種多様なデータを提供する膨大な情報源があります。これらの情報源には、Webフォーム、Webサービス、RSSフィードなどからアクセスできます。これらの情報源を自動的に利用するには、意味的にモデル化する必要がありますが、Webサービスの意味的な記述を書くのは面倒で、エラーが発生しやすくなります。本稿では、そのようなモデルの自動生成の問題について考察します。Web情報源のDatalog定義を学習するためのフレームワークを紹介します。これらの定義を学習するために、システムは情報源を能動的に呼び出し、それらが生成するデータを既知の情報源のデータと比較します。次に、可能性のある情報源定義の空間全体にわたって帰納的論理検索を実行し、新しい情報源ごとに最適な意味モデルを学習します。本稿では、実際のWeb情報源を用いてこのシステムの実証的評価を行います。評価によってこのアプローチの有効性が実証され、実際の情報源の複雑なモデルを妥当な時間で自動的に学習できることが示されます。また、本システムを複雑なスキーママッチングシステムと比較し、本アプローチが後者が取り組むような問題にも対処できることを示します。