Journal of Artificial Intelligence Resarch Vol. 21 (2004)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。
PHA*: Finding the Shortest Path with A* in An Unknown Physical Environment
PHA*：未知の物理環境におけるA*を用いた最短経路の探索
We address the problem of finding the shortest path between two points in an unknown real physical environment, where a traveling agent must move around in the environment to explore unknown territory. We introduce the Physical-A* algorithm (PHA*) for solving this problem. PHA* expands all the mandatory nodes that A* would expand and returns the shortest path between the two points. However, due to the physical nature of the problem, the complexity of the algorithm is measured by the traveling effort of the moving agent and not by the number of generated nodes, as in standard A*. PHA* is presented as a two-level algorithm, such that its high level, A*, chooses the next node to be expanded and its low level directs the agent to that node in order to explore it. We present a number of variations for both the high-level and low-level procedures and evaluate their performance theoretically and experimentally. We show that the travel cost of our best variation is fairly close to the optimal travel cost, assuming that the mandatory nodes of A* are known in advance. We then generalize our algorithm to the multi-agent case, where a number of cooperative agents are designed to solve the problem. Specifically, we provide an experimental implementation for such a system. It should be noted that the problem addressed here is not a navigation problem, but rather a problem of finding the shortest path between two points for future usage.
未知の現実の物理環境において、移動エージェントが未知の領域を探索するために環境内を移動しなければならない状況において、2点間の最短経路を求める問題を考察します。この問題を解決するために、Physical-A*アルゴリズム（PHA*）を導入します。PHA*は、A*が拡張するすべての必須ノードを拡張し、2点間の最短経路を返す。しかし、問題の物理的性質上、アルゴリズムの複雑さは、標準的なA*のように生成されるノードの数ではなく、移動エージェントの移動努力によって測定されます。PHA*は2階層アルゴリズムとして提示され、高階層のA*は次に拡張するノードを選択し、低階層のA*はエージェントをそのノードに誘導して探索させる。高階層および低階層の手順について、複数のバリエーションを提示し、それらの性能を理論的および実験的に評価します。A*の必須ノードが事前にわかっていると仮定した場合、最良のバリエーションの移動コストは最適な移動コストにかなり近いことを示す。次に、このアルゴリズムをマルチエージェントのケースに一般化します。マルチエージェントのケースでは、複数の協力エージェントが問題を解決するように設計されます。具体的には、そのようなシステムの実験的な実装を提供します。ここで扱う問題はナビゲーション問題ではなく、将来の使用のために2点間の最短経路を見つける問題であることに注意してください。
Competitive Coevolution through Evolutionary Complexification
進化的複雑化による競争的共進化
Two major goals in machine learning are the discovery and improvement of solutions to complex problems. In this paper, we argue that complexification, i.e. the incremental elaboration of solutions through adding new structure, achieves both these goals. We demonstrate the power of complexification through the NeuroEvolution of Augmenting Topologies (NEAT) method, which evolves increasingly complex neural network architectures. NEAT is applied to an open-ended coevolutionary robot duel domain where robot controllers compete head to head. Because the robot duel domain supports a wide range of strategies, and because coevolution benefits from an escalating arms race, it serves as a suitable testbed for studying complexification. When compared to the evolution of networks with fixed structure, complexifying evolution discovers significantly more sophisticated strategies. The results suggest that in order to discover and improve complex solutions, evolution, and search in general, should be allowed to complexify as well as optimize.
機械学習における2つの主要な目標は、複雑な問題に対する解決策の発見と改善です。本稿では、複雑化、すなわち新しい構造の追加による解決策の漸進的な精緻化が、これら両方の目標を達成することを主張します。我々は、ニューラルネットワークアーキテクチャをますます複雑に進化させるNeuroEvolution of Augmenting Topologies (NEAT)法を用いて、複雑化の威力を実証します。NEATは、ロボットコントローラーが直接対戦するオープンエンド型の共進化型ロボットデュエルドメインに適用します。ロボットデュエルドメインは幅広い戦略をサポートし、共進化は軍拡競争の激化から恩恵を受けるため、複雑化を研究するための適切なテストベッドとして機能します。固定構造を持つネットワークの進化と比較すると、複雑化進化ははるかに洗練された戦略を発見します。この結果は、複雑な解決策を発見し改善するためには、進化、そして一般的な探索において、最適化だけでなく複雑化も許容する必要があることを示唆しています。
Concurrent Auctions Across The Supply Chain
サプライチェーン全体にわたる同時オークション
With the recent technological feasibility of electronic commerce over the Internet, much attention has been given to the design of electronic markets for various types of electronically-tradable goods. Such markets, however, will normally need to function in some relationship with markets for other related goods, usually those downstream or upstream in the supply chain. Thus, for example, an electronic market for rubber tires for trucks will likely need to be strongly influenced by the rubber market as well as by the truck market. In this paper we design protocols for exchange of information between a sequence of markets along a single supply chain. These protocols allow each of these markets to function separately, while the information exchanged ensures efficient global behavior across the supply chain. Each market that forms a link in the supply chain operates as a double auction, where the bids on one side of the double auction come from bidders in the corresponding segment of the industry, and the bids on the other side are synthetically generated by the protocol to express the combined information from all other links in the chain. The double auctions in each of the markets can be of several types, and we study several variants of incentive compatible double auctions, comparing them in terms of their efficiency and of the market revenue.
近年、インターネットを介した電子商取引が技術的に実現可能となったことで、様々な種類の電子取引可能な商品の電子市場の設計に大きな注目が集まっています。しかしながら、このような市場は通常、サプライチェーンの下流または上流に位置する他の関連商品の市場と何らかの関係性を持って機能する必要があります。例えば、トラック用ゴムタイヤの電子市場は、トラック市場だけでなくゴム市場からも強い影響を受ける可能性が高い。本稿では、単一のサプライチェーンにおける複数の市場間の情報交換プロトコルを設計します。これらのプロトコルにより、各市場は個別に機能する一方で、交換される情報はサプライチェーン全体にわたる効率的なグローバルな動作を保証します。サプライチェーンのリンクを形成する各市場はダブルオークションとして機能し、ダブルオークションの一方の入札は業界の対応するセグメントの入札者から行われ、もう一方の入札はプロトコルによって合成され、チェーン内の他のすべてのリンクからの統合された情報を表現します。各市場におけるダブルオークションには複数の種類があり、本稿ではインセンティブ両立型ダブルオークションの複数のバリエーションを研究し、それらの効率性と市場収益の観点から比較します。
Can We Learn to Beat the Best Stock
最良の在庫に勝つことを学習できるか
A novel algorithm for actively trading stocks is presented. While traditional expert advice and “universal” algorithms (as well as standard technical trading heuristics) attempt to predict winners or trends, our approach relies on predictable statistical relations between all pairs of stocks in the market. Our empirical results on historical markets provide strong evidence that this type of technical trading can “beat the market” and moreover, can beat the best stock in the market. In doing so we utilize a new idea for smoothing critical parameters in the context of expert learning.
株式のアクティブ取引のための新たなアルゴリズムを提示します。従来の専門家のアドバイスや「普遍的な」アルゴリズム（そして標準的なテクニカル取引のヒューリスティック）は、勝者やトレンドを予測しようとするが、本手法は市場におけるあらゆる株式ペア間の予測可能な統計的関係性に依拠します。過去の市場における実証結果は、この種のテクニカル取引が「市場を上回る」だけでなく、市場で最も優良な株式を上回る可能性もあることを強く示唆しています。その際、専門家の学習という文脈において重要なパラメータを平滑化する新しいアイデアを活用します。
On Polynomial Sized MDP Succinct Policies
多項式サイズのMDP簡潔ポリシーについて
Policies of Markov Decision Processes (MDPs) determine the next action to execute from the current state and, possibly, the history (the past states). When the number of states is large, succinct representations are often used to compactly represent both the MDPs and the policies in a reduced amount of space. In this paper, some problems related to the size of succinctly represented policies are analyzed. Namely, it is shown that some MDPs have policies that can only be represented in space super-polynomial in the size of the MDP, unless the polynomial hierarchy collapses. This fact motivates the study of the problem of deciding whether a given MDP has a policy of a given size and reward. Since some algorithms for MDPs work by finding a succinct representation of the value function, the problem of deciding the existence of a succinct representation of a value function of a given size and reward is also considered.
マルコフ決定過程（MDP）のポリシーは、現在の状態、そして場合によっては履歴（過去の状態）から、次に実行するアクションを決定します。状態数が多い場合、MDPとポリシーの両方を少ない空間でコンパクトに表現するために、簡潔な表現がよく用いられます。本稿では、簡潔に表現されたポリシーのサイズに関連するいくつかの問題を分析します。具体的には、一部のMDPは、多項式階層が崩壊しない限り、MDPのサイズの超多項式の空間でしか表現できないポリシーを持つことを示します。この事実は、与えられたMDPが与えられたサイズと報酬を持つポリシーを持つかどうかを判断する問題を研究する動機となります。MDPのいくつかのアルゴリズムは価値関数の簡潔な表現を見つけることによって機能するため、特定のサイズと報酬の価値関数の簡潔な表現の存在を決定する問題も考慮されます。
Compositional Model Repositories via Dynamic Constraint Satisfaction with Order-of-Magnitude Preferences
桁違いの選好を伴う動的制約充足による構成モデル・リポジトリ
The predominant knowledge-based approach to automated model construction, compositional modelling, employs a set of models of particular functional components. Its inference mechanism takes a scenario describing the constituent interacting components of a system and translates it into a useful mathematical model. This paper presents a novel compositional modelling approach aimed at building model repositories. It furthers the field in two respects. Firstly, it expands the application domain of compositional modelling to systems that can not be easily described in terms of interacting functional components, such as ecological systems. Secondly, it enables the incorporation of user preferences into the model selection process. These features are achieved by casting the compositional modelling problem as an activity-based dynamic preference constraint satisfaction problem, where the dynamic constraints describe the restrictions imposed over the composition of partial models and the preferences correspond to those of the user of the automated modeller. In addition, the preference levels are represented through the use of symbolic values that differ in orders of magnitude.
自動モデル構築における主要な知識ベースアプローチである構成モデリングは、特定の機能コンポーネントのモデルセットを使用します。その推論メカニズムは、システムの構成要素である相互作用するコンポーネントを記述するシナリオを受け取り、それを有用な数学モデルに変換します。本論文では、モデルリポジトリの構築を目的とした新しい構成モデリングアプローチを紹介します。このアプローチは、2つの点でこの分野を前進させます。第一に、構成モデリングの適用領域を、生態系など、相互作用する機能コンポーネントの観点からは簡単に記述できないシステムに拡大します。第二に、モデル選択プロセスにユーザーの好みを組み込むことを可能にします。これらの特徴は、構成モデリング問題を活動ベースの動的選好制約充足問題として捉えることで実現されます。ここで、動的制約は部分モデルの構成に課される制約を記述し、選好は自動モデラーのユーザーの選好に対応します。さらに、選好レベルは桁違いに異なる記号値を用いて表現されます。
Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem
非対称巡回セールスマン問題の相転移とバックボーン
In recent years, there has been much interest in phase transitions of combinatorial problems. Phase transitions have been successfully used to analyze combinatorial optimization problems, characterize their typical-case features and locate the hardest problem instances. In this paper, we study phase transitions of the asymmetric Traveling Salesman Problem (ATSP), an NP-hard combinatorial optimization problem that has many real-world applications. Using random instances of up to 1,500 cities in which intercity distances are uniformly distributed, we empirically show that many properties of the problem, including the optimal tour cost and backbone size, experience sharp transitions as the precision of intercity distances increases across a critical value. Our experimental results on the costs of the ATSP tours and assignment problem agree with the theoretical result that the asymptotic cost of assignment problem is pi ^2 /6 the number of cities goes to infinity. In addition, we show that the average computational cost of the well-known branch-and-bound subtour elimination algorithm for the problem also exhibits a thrashing behavior, transitioning from easy to difficult as the distance precision increases. These results answer positively an open question regarding the existence of phase transitions in the ATSP, and provide guidance on how difficult ATSP problem instances should be generated.
近年、組合せ問題の相転移に多くの関心が寄せられています。相転移は、組合せ最適化問題を分析し、その典型的なケースの特徴を特徴付け、最も困難な問題例を見つけるために効果的に使用されてきた。本稿では、多くの実世界で応用されているNP困難な組合せ最適化問題である非対称巡回セールスマン問題(ATSP)の相転移について検討します。都市間距離が均一に分布している最大1,500都市のランダムな例を使用して、最適なツアー コストやバックボーン サイズなど、問題の多くの特性が、都市間距離の精度が臨界値を超えて増加するにつれて急激な遷移を経験的に示すことができます。ATSPツアーおよび割り当て問題のコストに関する実験結果は、都市数が無限大になると割り当て問題の漸近コストがpi ^2 /6になるという理論的結果と一致しています。さらに、この問題に対するよく知られた分岐限定法によるサブツアー除去アルゴリズムの平均計算コストも、距離精度が増加するにつれて容易から困難へと遷移するスラッシング挙動を示すことを示します。これらの結果は、ATSPにおける相転移の存在に関する未解決の問題に肯定的な回答を与え、どの程度困難なATSP問題インスタンスを生成すべきかについての指針を提供します。
Grounded Semantic Composition for Visual Scenes
視覚シーンのためのグラウンデッド・セマンティック・コンポジション
We present a visually-grounded language understanding model based on a study of how people verbally describe objects in scenes. The emphasis of the model is on the combination of individual word meanings to produce meanings for complex referring expressions. The model has been implemented, and it is able to understand a broad range of spatial referring expressions. We describe our implementation of word level visually-grounded semantics and their embedding in a compositional parsing framework. The implemented system selects the correct referents in response to natural language expressions for a large percentage of test cases. In an analysis of the system’s successes and failures we reveal how visual context influences the semantics of utterances and propose future extensions to the model that take such context into account.
我々は、人々がシーン内のオブジェクトを言語的に説明する方法の研究に基づいた、視覚的に根拠のある言語理解モデルを提示します。このモデルは、個々の単語の意味を組み合わせて複雑な指示表現の意味を生成することに重点を置いています。このモデルは実装されており、幅広い空間的な指示表現を理解できます。我々は、単語レベルの視覚的に根拠のあるセマンティクスの実装と、それらを構成的構文解析フレームワークに埋め込む方法について説明します。実装されたシステムは、テストケースの大部分において、自然言語表現に応じて正しい指示対象を選択します。システムの成功と失敗の分析では、視覚的なコンテキストが発話の意味にどのように影響するかを明らかにし、そのようなコンテキストを考慮したモデルの将来的な拡張を提案します。
A Personalized System for Conversational Recommendations
会話型レコメンデーションのためのパーソナライズされたシステム
Searching for and making decisions about information is becoming increasingly difficult as the amount of information and number of choices increases. Recommendation systems help users find items of interest of a particular type, such as movies or restaurants, but are still somewhat awkward to use. Our solution is to take advantage of the complementary strengths of personalized recommendation systems and dialogue systems, creating personalized aides. We present a system — the Adaptive Place Advisor — that treats item selection as an interactive, conversational process, with the program inquiring about item attributes and the user responding. Individual, long-term user preferences are unobtrusively obtained in the course of normal recommendation dialogues and used to direct future conversations with the same user. We present a novel user model that influences both item search and the questions asked during a conversation. We demonstrate the effectiveness of our system in significantly reducing the time and number of interactions required to find a satisfactory item, as compared to a control group of users interacting with a non-adaptive version of the system.
情報量と選択肢が増加するにつれて、情報の検索と意思決定はますます困難になっています。推薦システムは、映画やレストランなど、ユーザーが特定の種類の興味のあるアイテムを見つけるのに役立ちますが、依然として使い勝手が悪いです。本稿の解決策は、パーソナライズされた推薦システムと対話システムの相補的な強みを活用し、パーソナライズされた補助機能を作成することです。本稿では、アイテム選択を対話型の会話プロセスとして扱い、プログラムがアイテムの属性を尋ね、ユーザーがそれに応答するシステム（Adaptive Place Advisor）を紹介します。個々の長期的なユーザー嗜好は、通常の推薦対話の過程で目立たずに取得され、同じユーザーとの将来の会話を方向付けるために使用されます。我々は、アイテムの検索と会話中の質問の両方に影響を与える新しいユーザーモデルを提示します。システムの非適応型バージョンと対話するコントロールグループのユーザーと比較して、満足のいくアイテムを見つけるために必要な時間と対話回数を大幅に削減するシステムの有効性を実証します。
This paper discusses an interested party who wishes to influence the behavior of agents in a game (multi-agent interaction), which is not under his control. The interested party cannot design a new game, cannot enforce agents’ behavior, cannot enforce payments by the agents, and cannot prohibit strategies available to the agents. However, he can influence the outcome of the game by committing to non-negative monetary transfers for the different strategy profiles that may be selected by the agents. The interested party assumes that agents are rational in the commonly agreed sense that they do not use dominated strategies. Hence, a certain subset of outcomes is implemented in a given game if by adding non-negative payments, rational players will necessarily produce an outcome in this subset. Obviously, by making sufficiently big payments one can implement any desirable outcome. The question is what is the cost of implementation? In this paper we introduce the notion of k-implementation of a desired set of strategy profiles, where k stands for the amount of payment that need to be actually made in order to implement desirable outcomes. A major point in k-implementation is that monetary offers need not necessarily materialize when following desired behaviors. We define and study k-implementation in the contexts of games with complete and incomplete information. In the latter case we mainly focus on the VCG games. Our setting is later extended to deal with mixed strategies using correlation devices. Together, the paper introduces and studies the implementation of desirable outcomes by a reliable party who cannot modify game rules (i.e. provide protocols), complementing previous work in mechanism design, while making it more applicable to many realistic CS settings.
本稿では、自身の制御下にないゲーム（マルチエージェント相互作用）におけるエージェントの行動に影響を与えたいと考える利害関係者について論じる。利害関係者は、新しいゲームを設計することも、エージェントの行動を強制することも、エージェントによる支払いを強制することも、エージェントが利用可能な戦略を禁止することもできない。しかし、エージェントが選択する可能性のある様々な戦略プロファイルに対して、非負の金銭的移転を約束することで、ゲームの結果に影響を与えることはできます。利害関係者は、エージェントが支配戦略を使用しないという一般的な意味で合理的であると仮定します。したがって、あるゲームにおいて、非負の支払いを加えることで合理的なプレイヤーが必然的にこのサブセットの結果を生み出す場合、そのサブセットの結果が実装されます。明らかに、十分に大きな支払いを行うことで、あらゆる望ましい結果を実現できます。問題は、実装のコストがいくらになるかです。本稿では、望ましい戦略プロファイルの集合のk実装という概念を導入します。ここで、kは望ましい結果を実現するために実際に行う必要がある支払い額を表す。k実装における重要な点は、望ましい行動をとる際に、金銭的なオファーが必ずしも実現する必要はないという点です。本稿では、完全情報ゲームと不完全情報ゲームの文脈においてk実装を定義し、研究します。後者の場合、主にVCGゲームに焦点を当てます。本稿の設定は、後に相関デバイスを用いた混合戦略を扱うように拡張されます。本稿では、ゲームルールを変更できない（つまり、プロトコルを提供できない）信頼できる当事者による望ましい結果の実装を紹介し、研究することで、メカニズム設計における先行研究を補完するとともに、多くの現実的なCS設定への適用性を高めます。
Dual Modelling of Permutation and Injection Problems
順列問題と注入問題の双対モデル化
When writing a constraint program, we have to choose which variables should be the decision variables, and how to represent the constraints on these variables. In many cases, there is considerable choice for the decision variables. Consider, for example, permutation problems in which we have as many values as variables, and each variable takes an unique value. In such problems, we can choose between a primal and a dual viewpoint. In the dual viewpoint, each dual variable represents one of the primal values, whilst each dual value represents one of the primal variables. Alternatively, by means of channelling constraints to link the primal and dual variables, we can have a combined model with both sets of variables. In this paper, we perform an extensive theoretical and empirical study of such primal, dual and combined models for two classes of problems: permutation problems and injection problems. Our results show that it often be advantageous to use multiple viewpoints, and to have constraints which channel between them to maintain consistency. They also illustrate a general methodology for comparing different constraint models.
制約プログラムを作成する際には、どの変数を決定変数とし、それらの変数に対する制約をどのように表現するかを選択する必要があります。多くの場合、決定変数にはかなりの選択肢があります。例えば、変数の数と同数の値が存在し、各変数が一意の値を取る順列問題を考えてみましょう。このような問題では、主視点と双対視点のどちらかを選択できます。双対視点では、各双対変数は主変数のいずれかの値を表し、各双対変数は主変数のいずれかの値を表します。あるいは、主変数と双対変数を結びつけるチャネリング制約を用いることで、両方の変数セットを組み合わせたモデルを構築できます。本論文では、順列問題と注入問題という2つの問題クラスについて、このような主視点、双対視点、および組み合わせモデルについて、広範な理論的および実証的研究を行います。その結果、複数の視点を用いること、そしてそれらの視点間をチャネリングすることで整合性を維持することがしばしば有利であることが明らかになりました。また、異なる制約モデルを比較するための一般的な方法論も示しています。
Representation Dependence in Probabilistic Inference
確率推論における表現の依存性
Non-deductive reasoning systems are often representation dependent: representing the same situation in two different ways may cause such a system to return two different answers. Some have viewed this as a significant problem. For example, the principle of maximum entropyhas been subjected to much criticism due to its representation dependence. There has, however, been almost no work investigating representation dependence. In this paper, we formalize this notion and show that it is not a problem specific to maximum entropy. In fact, we show that any representation-independent probabilistic inference procedure that ignores irrelevant information is essentially entailment, in a precise sense. Moreover, we show that representation independence is incompatible with even a weak default assumption of independence. We then show that invariance under a restricted class of representation changes can form a reasonable compromise between representation independence and other desiderata, and provide a construction of a family of inference procedures that provides such restricted representation independence, using relative entropy.
非演繹推論システムはしばしば表現依存的です。つまり、同じ状況を2つの異なる方法で表現すると、異なる答えが返される可能性があります。これを重大な問題と考える人もいます。例えば、最大エントロピー原理は、その表現依存のために多くの批判にさらされてきた。しかしながら、表現依存を調査する研究はほとんど行われていない。本稿では、この概念を形式化し、最大エントロピーに特有の問題ではないことを示す。実際、無関係な情報を無視する表現に依存しない確率推論手順は、厳密に言えば本質的に含意であることを示す。さらに、表現独立性は、弱いデフォルト独立性仮定とさえ両立しないことを示す。次に、限定された表現変更クラスにおける不変性が、表現独立性と他の要件との間の妥当な妥協点となり得ることを示し、相対エントロピーを用いて、そのような限定された表現独立性を提供する推論手順群の構成法を提供します。
IDL-Expressions: A Formalism for Representing and Parsing Finite Languages in Natural Language Processing
IDL式：自然言語処理における有限言語の表現と構文解析のための形式主義
We propose a formalism for representation of finite languages, referred to as the class of IDL-expressions, which combines concepts that were only considered in isolation in existing formalisms. The suggested applications are in natural language processing, more specifically in surface natural language generation and in machine translation, where a sentence is obtained by first generating a large set of candidate sentences, represented in a compact way, and then by filtering such a set through a parser. We study several formal properties of IDL-expressions and compare this new formalism with more standard ones. We also present a novel parsing algorithm for IDL-expressions and prove a non-trivial upper bound on its time complexity.
我々は、既存の形式主義では個別にしか考慮されていなかった概念を統合した、IDL式のクラスと呼ばれる有限言語の表現形式主義を提案します。提案されている応用分野は自然言語処理、より具体的には表層自然言語生成と機械翻訳です。機械翻訳では、まず候補文の大規模な集合を生成し、それを簡潔に表現し、次にその集合をパーサーでフィルタリングすることで文が得られます。我々はIDL式のいくつかの形式的性質を研究し、この新しい形式主義をより標準的な形式主義と比較します。また、IDL式のための新しい構文解析アルゴリズムを提示し、その時間計算量の非自明な上限を証明します。
Coherent Integration of Databases by Abductive Logic Programming
アブダクティブ論理プログラミングによるデータベースの一貫性のある統合
Abstract: We introduce an abductive method for a coherent integration of independent data-sources. The idea is to compute a list of data-facts that should be inserted to the amalgamated database or retracted from it in order to restore its consistency. This method is implemented by an abductive solver, called Asystem, that applies SLDNFA-resolution on a meta-theory that relates different, possibly contradicting, input databases. We also give a pure model-theoretic analysis of the possible ways to `recover’ consistent data from an inconsistent database in terms of those models of the database that exhibit as minimal inconsistent information as reasonably possible. This allows us to characterize the `recovered databases’ in terms of the `preferred’ (i.e., most consistent) models of the theory. The outcome is an abductive-based application that is sound and complete with respect to a corresponding model-based, preferential semantics, and — to the best of our knowledge — is more expressive (thus more general) than any other implementation of coherent integration of databases.
概要:独立したデータソースを首尾一貫して統合するためのアブダクション手法を導入します。その考え方は、統合されたデータベースの一貫性を回復するために、統合データベースに追加すべき、あるいは統合データベースから削除すべきデータファクトのリストを計算することです。この手法は、異なる、あるいは矛盾する可能性のある入力データベースを関連付けるメタ理論にSLDNFA解決を適用するAsystemと呼ばれるアブダクションソルバーによって実装されます。また、矛盾したデータベースから一貫性のあるデータを「回復」するための、可能な限り矛盾した情報を最小限に抑えるデータベースモデルを用いた、可能な方法について、純粋なモデル理論的分析を行う。これにより、「回復されたデータベース」を理論の「好ましい」（つまり最も一貫性のある）モデルに基づいて特徴付けることができます。その結果、対応するモデルベースの優先的意味論に関して健全かつ完全なアブダクションベースのアプリケーションが実現しました。これは、我々の知る限り、データベースの一貫性のある統合の他のどの実装よりも表現力に富んでいます（したがって、より汎用的です）。
Generalizing Boolean Satisfiability I: Background and Survey of Existing Work
ブール充足可能性の一般化 I：背景と既存研究の概観
This is the first of three planned papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high-performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal is to define a representation in which this structure is apparent and can easily be exploited to improve computational performance. This paper is a survey of the work underlying ZAP, and discusses previous attempts to improve the performance of the Davis-Putnam-Logemann-Loveland algorithm by exploiting the structure of the problem being solved. We examine existing ideas including extensions of the Boolean language to allow cardinality constraints, pseudo-Boolean representations, symmetry, and a limited form of quantification. While this paper is intended as a survey, our research results are contained in the two subsequent articles, with the theoretical structure of ZAP described in the second paper in this series, and ZAP’s implementation described in the third.
これは、既存のツールを大幅に一般化しながら、最新の高性能ソルバーのパフォーマンス特性を維持する満足度エンジンであるZAPについて説明する予定の3つの論文の最初のものです。ZAPの根底にある基本的な考え方は、このようなエンジンに渡される多くの問題には、使用されるブール表現では隠されている豊富な内部構造が含まれているということです。我々の目標は、この構造が明白であり、計算性能を向上させるために容易に利用できる表現を定義することです。本論文は、ZAPの基礎となる研究のサーベイであり、解決しようとしている問題の構造を利用することでデイビス・パトナム・ローゲマン・ラブランドアルゴリズムの性能を向上させるこれまでの試みについて論じます。我々は、基数制約、疑似ブール表現、対称性、限定的な数量化を可能にするブール言語の拡張など、既存のアイデアを検討します。本論文はサーベイを目的としていますが、我々の研究成果は後続の2つの論文にまとめられており、このシリーズの2番目の論文ではZAPの理論的構造について、3番目の論文ではZAPの実装について説明しています。
Price Prediction in a Trading Agent Competition
トレーディングエージェント競争における価格予測
The 2002 Trading Agent Competition (TAC) presented a challenging market game in the domain of travel shopping. One of the pivotal issues in this domain is uncertainty about hotel prices, which have a significant influence on the relative cost of alternative trip schedules. Thus, virtually all participants employ some method for predicting hotel prices. We survey approaches employed in the tournament, finding that agents apply an interesting diversity of techniques, taking into account differing sources of evidence bearing on prices. Based on data provided by entrants on their agents’ actual predictions in the TAC-02 finals and semifinals, we analyze the relative efficacy of these approaches. The results show that taking into account game-specific information about flight prices is a major distinguishing factor. Machine learning methods effectively induce the relationship between flight and hotel prices from game data, and a purely analytical approach based on competitive equilibrium analysis achieves equal accuracy with no historical data. Employing a new measure of prediction quality, we relate absolute accuracy to bottom-line performance in the game.
2002年のトレーディングエージェントコンペティション（TAC）は、旅行ショッピングの分野において、挑戦的な市場ゲームを提示しました。この分野における重要な課題の一つは、ホテル料金に関する不確実性であり、これは代替旅行スケジュールの相対的なコストに大きな影響を与えます。そのため、事実上すべての参加者は、ホテル料金を予測するために何らかの方法を採用しています。トーナメントで採用された手法を調査し、エージェントが価格に関係する様々な証拠源を考慮に入れながら、興味深い多様な手法を適用していることを発見しました。TAC-02の決勝と準決勝におけるエージェントの実際の予測について参加者から提供されたデータに基づいて、これらの手法の相対的な有効性を分析しました。結果は、航空券の価格に関するゲーム固有の情報を考慮に入れることが大きな差別化要因であることを示しています。機械学習手法は、ゲームデータから航空券とホテルの価格の関係を効果的に誘導し、競争均衡分析に基づく純粋に分析的なアプローチは、履歴データなしで同等の精度を達成しました。予測品質の新しい尺度を用いて、絶対精度とゲームの最終的なパフォーマンスを関連付けました。
CP-nets: A Tool for Representing and Reasoning withConditional Ceteris Paribus Preference Statements
CPネット：条件付きCeteris Paribus選好ステートメントの表現と推論のためのツール
Information about user preferences plays a key role in automated decision making. In many domains it is desirable to assess such preferences in a qualitative rather than quantitative way. In this paper, we propose a qualitative graphical representation of preferences that reflects conditional dependence and independence of preference statements under a ceteris paribus (all else being equal) interpretation. Such a representation is often compact and arguably quite natural in many circumstances. We provide a formal semantics for this model, and describe how the structure of the network can be exploited in several inference tasks, such as determining whether one outcome dominates (is preferred to) another, ordering a set outcomes according to the preference relation, and constructing the best outcome subject to available evidence.
ユーザーの嗜好に関する情報は、自動意思決定において重要な役割を果たします。多くの分野において、そのような嗜好を定量的ではなく定性的に評価することが望ましいです。本稿では、他の条件がすべて同じである（ceteris paribus）という解釈の下で、嗜好ステートメントの条件付き従属関係と独立性を反映した、嗜好の定性的なグラフィカル表現を提案します。このような表現は多くの場合簡潔で、多くの状況において非常に自然と言えるでしょう。本稿では、このモデルの形式的意味論を提供し、ネットワークの構造が、ある結果が他の結果よりも優位（好まれる）かどうかの判断、選好関係に従って結果の集合を順序付け、利用可能な証拠に基づいて最良の結果を構築するといった、様々な推論タスクにどのように活用できるかを説明します。
Complexity Results and Approximation Strategies for MAP Explanations
MAP説明における複雑性の結果と近似戦略
MAP is the problem of finding a most probable instantiation of a set of variables given evidence. MAP has always been perceived to be significantly harder than the related problems of computing the probability of a variable instantiation Pr, or the problem of computing the most probable explanation (MPE). This paper investigates the complexity of MAP in Bayesian networks. Specifically, we show that MAP is complete for NP^PP and provide further negative complexity results for algorithms based on variable elimination. We also show that MAP remains hard even when MPE and Pr become easy. For example, we show that MAP is NP-complete when the networks are restricted to polytrees, and even then can not be effectively approximated. Given the difficulty of computing MAP exactly, and the difficulty of approximating MAP while providing useful guarantees on the resulting approximation, we investigate best effort approximations. We introduce a generic MAP approximation framework. We provide two instantiations of the framework; one for networks which are amenable to exact inference Pr, and one for networks for which even exact inference is too hard. This allows MAP approximation on networks that are too complex to even exactly solve the easier problems, Pr and MPE. Experimental results indicate that using these approximation algorithms provides much better solutions than standard techniques, and provide accurate MAP estimates in many cases.
MAPは、証拠が与えられた場合に変数集合の最確なインスタンス化を求める問題です。MAPは、変数のインスタンス化確率Prを計算する関連問題や、最確説明（MPE）を計算する問題よりもはるかに難しいと常に認識されてきました。本論文では、ベイジアンネットワークにおけるMAPの計算量を調査します。具体的には、MAPがNP^PPに対して完全であることを示し、変数除去に基づくアルゴリズムの計算量がさらに減少することを示します。また、MPEとPrが容易になった場合でも、MAPは依然として困難であることを示します。例えば、ネットワークがポリツリーに制限されている場合、MAPはNP完全であり、その場合でも効果的に近似できないことを示します。MAPを正確に計算することの難しさ、および得られる近似値に有用な保証を提供しながらMAPを近似することの難しさを考慮して、ベストエフォート近似を調査します。汎用的なMAP近似フレームワークを導入します。このフレームワークには2つのインスタンスが用意されています。1つは正確な推論Prが可能なネットワーク用、もう1つは正確な推論すら困難なネットワーク用です。これにより、より簡単な問題であるPrとMPEを正確に解くことさえ難しいほど複雑なネットワークでもMAP近似が可能になります。実験結果によると、これらの近似アルゴリズムを用いることで、標準的な手法よりもはるかに優れた解が得られ、多くの場合で正確なMAP推定値が得られることがわかった。
Effective Dimensions of Hierarchical Latent Class Models
階層的潜在クラスモデルの有効次元
Hierarchical latent class (HLC) models are tree-structured Bayesian networks where leaf nodes are observed while internal nodes are latent. There are no theoretically well justified model selection criteria for HLC models in particular and Bayesian networks with latent nodes in general. Nonetheless, empirical studies suggest that the BIC score is a reasonable criterion to use in practice for learning HLC models. Empirical studies also suggest that sometimes model selection can be improved if standard model dimension is replaced with effective model dimension in the penalty term of the BIC score. Effective dimensions are difficult to compute. In this paper, we prove a theorem that relates the effective dimension of an HLC model to the effective dimensions of a number of latent class models. The theorem makes it computationally feasible to compute the effective dimensions of large HLC models. The theorem can also be used to compute the effective dimensions of general tree models.
階層的潜在クラス（HLC）モデルは、葉ノードが観測され、内部ノードが潜在するツリー構造のベイジアンネットワークです。特にHLCモデル、そして一般的に潜在ノードを持つベイジアンネットワークに対して、理論的に十分に正当化されたモデル選択基準は存在しない。しかしながら、実証的研究は、BICスコアがHLCモデルの学習において実際に使用する適切な基準であることを示唆しています。また、実証的研究は、BICスコアのペナルティ項において標準モデル次元を有効モデル次元に置き換えることで、モデル選択を改善できる場合があることを示唆しています。有効次元の計算は困難です。本稿では、HLCモデルの有効次元と複数の潜在クラスモデルの有効次元を関連付ける定理を証明します。この定理により、大規模HLCモデルの有効次元の計算が計算的に可能になります。この定理は、一般的なツリーモデルの有効次元の計算にも使用できます。