Web Reasoning and Rule Systems

機械学習技術人工知能技術自然言語処理技術セマンティックウェブ技術オントロジー技術デジタルトランスフォーメーション技術 AI学会論文知識情報処理技術 AI学会論文を集めて推論技術本ブログのナビ

Web Reasoning and Rule Systems

本書は、2011年8月にアイルランドのゴールウェイで開催された第5回Web Reasoning and Rule Systems国際会議RR 2011の査読付きプロシーディングスである。本書は、2011年8月にアイルランドのゴールウェイで開催された第5回Web Reasoning and Rule Systems国際会議RR 2011の査読付きプロシーディングスであり、フルペーパー13編、ショートペーパー12編、招待講演2編を収録している。論文では、セマンティックWebの最新のトピック、RDFやOWLなどのよく確立されたWeb言語と古典的な推論アプローチの間の相互作用、推論言語、クエリと最適化、ルールとオントロジーを扱っている。

Exchanging More Than Complete Data

従来のデータ交換の設定では、ソース・インスタンスは、これらのインスタンスにおいてすべてのファクトが真または偽のいずれかであるという意味で、完全であるように制限されています。典型的なデータベース変換シナリオでは当然のことですが、この制限は、複数の解釈を許容するオブジェクトを交換する必要がある幅広いアプリケーションの開発にとって、次第に障害となりつつあります。特に、不完全な情報の交換と知識ベースの交換という、通常のデータ交換のシナリオを超える2つの具体的なアプリケーションに動機づけられている。

本講演では、これら2つのアプリケーションに対応できるデータ交換の一般的なフレームワークを提案する。具体的には、完全なインスタンスの有限な記述である表現システムが与える情報を交換する問題を取り上げ、不完全な情報を交換する問題や知識ベースを交換する問題に適用することで、提案の頑健性を示す。

Ontological Query Answering with Existential Rules

オントロジーにコード化されたセマンティクスを利用できる高度な推論メカニズムに関連した、データ上のオントロジー層の必要性は、データベースと知識表現の両方のコミュニティで認められている。本稿では、オントロジー知識を考慮しながらデータを問い合わせる、オントロジー問い合わせ応答問題に焦点を当てる。この問題に取り組むために、タプル生成依存関係（Tuple-Generating Dependencies）あるいはDatalog+/-規則とも呼ばれる、実存的規則に基づく論理的枠組みを考える。このフレームワークはグラフ用語で定義することもできる。実存的規則による問い合わせの含意は決定不可能であるため、決定可能な規則のクラスを可能な限り大きく定義することが重要な課題である。本論文は、主な複雑さの結果のレビューを含む、決定可能なルールのクラスのサーベイである。その大部分は、IJCAI’2009[BLMS09]およびKR’2010[BLM10]で発表された過去の研究（およびジャーナル論文[BLMS11]で展開された研究）に依拠しており、最新の結果を含むように更新されている。

The ONTORULE Project : Where Ontology Meets Business Rules

ONTORULEの目的は、ビジネス・エグゼクティブからビジネス・アナリスト、IT開発者に至るまで、ユーザがビジネス・アプリケーションの中で自分に関連する部分と自分なりの方法で対話できるようにすることである。この拡張アブストラクトでは、ONTORULEプロジェクトが提案するビジネスルールアプリケーション開発のアプローチについて説明し、そのために開発し、2つのパイロットアプリケーションで検証・実証されたアーキテクチャとセマンティック技術を紹介する。

Towards Farsighted Dependencies for Existential Rules

我々は実存的ルール（タプル生成依存関係またはDatalog+/-ルールとも呼ばれる）を考える。これらのルールは、用語知識を考慮しながらデータを問い合わせるという、タイムリーなオントロジカル問い合わせ応答問題に特に適している。この問題は一般に決定不可能であるため、決定可能性を保証する様々な条件が文献で提案されている。本稿では、前方連鎖機構が有限であることを保証するために、ルールの相互作用の仕方を制限する条件に注目する。既存の提案のレビューの後、k-依存性というルール依存性の概念の一般化を提案する。また、ルールベースのコンパイルにも利用でき、問い合わせ応答アルゴリズムの改善につながる。

Context-Dependent OWL Reasoning in Sindice – Experiences and Lessons Learnt

シンダイスのセマンティック・ウェブ・インデックスは、2億6千万以上の文書を検索できる。ウェブデータを推論することで、暗黙知であったものを明示化することができ、情報に付加価値を与え、最終的にSindiceが精度と想起においてより競争力を持つことを可能にする。しかし、ウェブデータのスケールと異質性により、Sindiceシステムの推論エンジンは、(1)マシンのクラスタ上での並列化によるスケールアウト、(2)予期せぬデータ使用への対応、が必要である。本論文では、Sindiceのための大規模な推論エンジンを構築した経験と教訓を報告する。この推論アプローチは2008年からSindiceに導入され、使用され、改良されてきた。

Little Knowledge Rules the Web: Domain-Centric Result Page Extraction

ウェブ抽出とは、非構造化HTMLを構造化データに変える作業である。これまでのアプローチは、結果ページで繰り返される構造を検出することだけに頼っていた。このようなアプローチは、精度と引き換えに、ユーザーとの集中的なインタラクションを必要とする。

この論文では、人間のインタラクションをドメインのすべてのサイトに適用可能なドメインオントロジーに置き換えるAmber（「Adaptable Model-based Extraction of Result Pages」）システムを紹介する。これは、(1)ドメインのレコードと属性、(2)これらの概念の低レベル（テキスト）表現、(3)表現をレコードと属性にリンクする制約に関するドメイン知識をモデル化する。これらの制約をパラメータ化することで、ドメインに依存しないヒューリスティックは、結果ページの繰り返し構造を利用して、属性とレコードを導出する。アンバーは、ヒューリスティックの明示的な定式化と異なるドメインへの容易な適応を可能にする論理ルールで実装されている。

我々はアンバーを英国の不動産領域に適用し、50の代理店ウェブサイトの代表的なサンプルでほぼ完璧な精度を達成した。

Conjunctive Query Answering in Probabilistic Datalog+/– Ontologies

Datalog+/-は最近開発されたオントロジー言語であり、特に軽量なオントロジーの表現と推論に有用で、セマンティックウェブのクエリー応答と情報抽出の文脈で中心的な役割を果たすと考えられている。ウェブの本質的な側面としての不確実性に加え、矛盾や不完全性による不確実性、ウェブデータの自動処理による不確実性、複数の異種データソースの統合による不確実性にも対処しなければならない。本論文では、確率的セマンティクスとしてマルコフ論理ネットワークを使用する、ガード付きDatalog+/-の確率的拡張に対する接続クエリに答えるための2つのアルゴリズムを紹介する。接続クエリは「与えられたアトムの集合が成り立つ確率は？これらのクエリは特にウェブ情報抽出に関連する。なぜなら、抽出者はしばしば不確実なルールや事実を扱うことがあり、ある事実が推論される可能性に基づいて決定を下さなければならないからである。接続クエリに答える最初のアルゴリズムは、古典的な前進連鎖（チェイス手続きとして知られている）を用いた基本的なものであり、2番目のアルゴリズムは後進連鎖アルゴリズムであり、ガードされたDatalog+/-の特定のサブセット上で動作する。

Paraconsistent Semantics for Hybrid MKNF Knowledge Bases

ハイブリッドMKNF知識ベースは、もともと安定モデル意味論に基づいており、ルールと記述論理（DL）を組み合わせた成熟した手法である。このような知識ベースは、推論の効率化のために、根拠のある意味論が提案されている。しかし、ルールとDLの統合は、それぞれ整合性がとれていても、矛盾を引き起こす可能性がある。そのため、従来の2つの意味論に基づく推論システムは破綻してしまう。本論文では、Belnapによって提案された4値論理を採用し、ハイブリッドMKNF知識ベースに対して、矛盾を検出し、効果的に処理することができる並列無矛盾なセマンティクスを提示する。また、我々の提案する意味論は、線形変換演算子を介して安定モデル意味論に変換され、我々のパラダイムにおけるデータ複雑度が古典的推論よりも高くないことを示す。さらに、パラコンシステントMKNFモデルを計算するためのフィックスポイントアルゴリズムを提供する。

Linked Rules: Principles for Rule Reuse on the Web

オントロジーとは、ある領域をモデル化するための語彙や用語、関連する意味を提供する情報モデルである。オントロジーは、共有された概念化である。近年、オントロジーは、産業界だけでなく学界の専門家を含むコミュニティの努力によって開発されているため、このことはかつてないほど真実である。こうした努力は、RDF、OWL、SPARQLなど、オントロジーやデータを（セマンティック）ウェブ上で表現し、（再）利用するためのフォーマットや言語の標準化によって補完されてきた。一方、ルールは知識表現（セマンティクスや完全性制約の定義）に使われることは（ほとんど）ない。ルールはビジネスロジックやポリシーの定義など、他の知的推論タスクにも使用される。共有情報モデルの普及により、ルールを共有し再利用することは可能であり、また必要かもしれない。さらに、ルール交換フォーマット（RIF）の出現により、多くのルールシステム間でルールを共有することができる。我々は、ルールが効果的に再利用されるように、ルールを表現し、ウェブ上で共有するための基本原則と機能のセットを提案し、ルール再利用のいくつかの方法を示す。最後に、これらの機能のいくつかが、N3ベースのAIRウェブ・ルール言語において実際にどのように機能するかについて述べる。

Polynomial Conjunctive Query Rewriting under Unary Inclusion Dependencies

オントロジーに基づくデータアクセス（OBDA）は、新世代の情報システムの重要な要素として広く受け入れられている。OBDAのパラダイムでは、潜在的に不完全なリレーショナルデータは、アプリケーションドメインの拡張的知識を表すオントロジーによってエンリッチされる。我々は、OBDAにおける接続クエリ応答の問題を考察する。ある種のオントロジー言語はFO書き換え可能であることが確認されている（例えば、DL-LiteやTGDのスティッキー結合セット）。しかしながら、すべての既知のクエリ書き換え技術は、ユーザのクエリサイズが指数関数的に大きくなるクエリを生成し、これは標準的なリレーショナルデータベースエンジンにとって深刻な問題となりうる。本論文では、単項包含従属性の下での接続クエリに対する多項式クエリ書き換えを提示する。一方、バイナリ包含従属性は多項式問い合わせ書き換えアルゴリズムを認めないことを示す。

Reasoning as Axioms Change

本稿では、ルールベースの推論装置で使用されるような論理データベースにおいて、実体化されたビューの変更を計算するための新しいインクリメンタルアルゴリズムを紹介する。このような推論器は、派生アトムの実体化の存在下で公理を変更する問題に対処しなければならない。既存のアプローチには欠点がある：ソースプログラムがDatalog¬であるのに対して、Datalog¬である大きな変換されたプログラムを生成し、評価する必要があるものや、述語の拡張のほんの一部だけが変更によって影響を受けるとしても、その拡張全体を再計算するものがある。この論文で紹介する方法は、この2つの欠点を克服するものである。

Query Rewriting for Inconsistent DL-Lite Ontologies

本論文では、矛盾したDL – Liteオントロジーに対するクエリに対して意味のある回答を得る問題について研究する。我々は、矛盾に寛容なセマンティクスの様々な変種を検討し、そのような変種のいくつかについて、接続クエリ(UCQ)の回答が一次(FOL)書き換え可能であること、すなわち、データベースに対するFOL/SQLクエリの標準的な評価に還元できることを示す。一貫性のあるオントロジーに対するUCQのFOL書き換え可能性は、DL – Liteの特徴の一つである。そのため、このような設定において、矛盾許容型問合せ応答は標準的な問合せ応答と同じ計算量を持ち、標準的なDLセマンティクスの下と同様に、確立されたリレーショナルデータベース技術に依存できることを示す。

Decidability of Unification in EL without Top Constructor

近年、記述論理が注目されている。記述論理は、自然言語処理、技術システムの構成、データベース、生物医学オントロジーなどで使われる知識表現形式論である。そこでは、等価な概念を認識するためのツールとして単一化が用いられている。での単一化はNP完全であることが証明されている。がNP完全であることが証明されている。この結果は、ある種の単一化子の局所性特性に基づいている。実際、大規模な医療オントロジーであるSNOMED CTは、++形式論のサブセットに基づいて構築されているが、トップ概念は存在しない。トップ概念を用いない拡張における単一化の決定可能性を調べることは興味深い。本稿ではにおける単一化の決定可能性を調べる。についても同様の局所性が成り立つことを示す。しかしにおける単一化の場合のように、局所性から直ちに単一化が導かれるわけではない。. しかし、局所性をさらに制限することで、以下のことを証明する。を証明し、この問題に対するNExpTime決定手続きを構築する。さらに、この手続きにより、単一化問題に対する特定の解の集合を計算することができる。

On the Equivalence between the Action Language and Partial Actions in Transaction Logic

部分的に定義されたアクションを持つトランザクションロジック（TR PAD）は、アクションの効果を推論し、状態を変更するトランザクションを宣言的に指定するための表現力豊かなフォーマリズムである。アクション言語は、変化する領域を記述し、アクションを推論するためのよく知られた形式論である。本稿の目的は、これら2つの形式を比較し、その類似点と分岐点を明らかにすることで、モデリングと推論の能力をより良く理解することである。本稿では、TR PADの大きな断片の健全な漸化式を提供し、この漸化式が.PADのLP埋め込みに関して完全であることを示す。また、行動計画が両言語でどのようにモデル化されるかを探求し、行動を表現する他の言語との関係について議論する。

Reasoning with Actions in Transaction Logic

本稿では、TR PAD（Transaction Logic with Partially Defined Actions）-複合アクションの効果を推論するための表現力豊かなフォーマリズム-を紹介する。TR PADはTransaction Logicのサブセットに基づいているが、元のTransaction Logicのデータと遷移式を一般化した特別な前提式で拡張している。我々は、TR PADのための健全で完全な証明理論を開発し、多くの非自明な例でその形式論を説明する。さらに、TR PADの大部分が通常の論理プログラミングに還元可能であり、この還元が健全かつ完全であることを示す。

Interpolation and Extrapolation in Conceptual Spaces: A Case Study in the Music Domain

ほとんどの知識表現では、原子特性は自然言語ラベルに対応する。これらのラベルは通常、原始的なものであると考えられるが、ある種のコモンセンス推論を自動化するには、これらのラベルの認知的意味に関する背景知識が必要である。我々は、このような常識的推論の2つの形式を考え、これを補間的推論と外挿的推論と呼ぶ。どちらの場合も、ルールに基づく知識は、概念空間におけるラベルの幾何学的表現に関する知識で補強される。具体的には、補間的推論をサポートするために、中間的な条件が中間的な結論を導く傾向があることを考慮して、どのラベルが概念的に他のラベルの間にあるかを知る必要がある。外挿的推論は、あるラベルを別のラベルに置き換える際に必要となる変化の方向に関する情報に基づいており、ルールの条件の並列的な変化は結論の並列的な変化につながる傾向があるという視点に立つ。本稿では、このようなラベルの概念空間表現に関する知識を獲得するための実用的な方法を提案する。本論文では、音楽推薦サイトlast.fmから得られたメタデータから、音楽ジャンルの領域でこの方法を説明する。

Improve Efficiency of Mapping Data between XML and RDF with XSPARQL

XSPARQLは、ツリーベースのXMLフォーマットとグラフベースのRDFフォーマットの間でデータを変換するための言語である。XMLは広く採用されているデータ交換フォーマットであり、独自のクエリー言語XQueryを伴っている。RDFはセマンティックウェブの標準データフォーマットであり、SPARQLはそれに対応するクエリ言語である。XSPARQLはXQueryとSPARQLを統合したクエリー言語であり、2つのデータフォーマット間でデータを変換するための、より直感的で保守性の高い方法を提供する。XSPARQLの素朴な実装は、ネストされたクエリを評価する際に非効率になる可能性がある。しかし、このようなクエリはXMLデータを扱う際に実際に頻繁に発生する。ネストされたクエリを最適化するためのいくつかのアプローチを紹介し、比較する。これらの最適化を実装することで、実用的な評価において2桁まで効率を改善することができる。

A Smart Campus Prototype for Demonstrating the Semantic Integration of Heterogeneous Data

本稿では、セマンティック技術を利用して異種データを統合するスマートキャンパスアプリケーションのプロトタイプの実装について述べる。このプロトタイプは、OWL、SWRL、SPARQLを使用して、セマンティック・データ・アクセスと統合を容易にするレイヤード・セマンティック・アーキテクチャに基づいている。本稿の焦点は、プロトタイプの実装と、その開発から得られた教訓である。

An Ontological Approach for Modeling Technical Standards for Compliance Checking

本論文では、フランスの建築産業科学センター（CSTB）における技術評価の実施を支援するために、太陽光発電分野のいくつかの規制をモデル化する、形式的なセマンティックベースのアプローチの概要を示す。規制のテキストから出発して、まずSBVRルールを明示し、次にそれらをSPARQL言語のオントロジーベースのルールに形式化する。これらは、技術評価の実施に必要なコンプライアンス・チェック・プロセスのモデリングに活用される。

Integrating Linked Data through RDFS and OWL: Some Lessons Learnt

本論文では、博士論文「Exploiting RDFS and OWL for Integrating Heterogeneous, Large-Scale, Linked Data Corpora（異種、大規模、リンクされたデータコーパスを統合するためのRDFSとOWLの活用）」から学んだ教訓を要約する。この論文では、リンクされたデータ上で推論するための3つのユースケースを検討した。リンクされたデータを推論する際に直面するスケーラビリティとロバスト性の課題を克服する方法を要約する。我々は、400万のLinked Data文書からクロールされた11億の四重表現のオープンドメインのコーパスに対して我々の方法を検証し、このようなシナリオにおける我々の推論方法の適用性と有用性について議論する。

Instant Feedback on Discovered Association Rules with PMML-Based Query-by-Example

アソシエーションルールマイニングタスクの長年の研究課題は、発見された多数のルールから、ドメインエキスパートにとって興味深いルールを特定することである。我々は、SEWEBAR-CMSシステムの新機能である、任意のルールを例としてクエリとして使用し、ワンクリックでこのルールが知識ベースに既に格納されているルールと興味深い関係にあるかどうかを発見することを実演する。PMMLのようなXMLベースの宣言言語を使って、XSLT変換により新しい関係を追加することができます。

Local Closed World Semantics: Grounded Circumscription for Description Logics

我々は、記述論理のための改良された局所閉界拡張を発表する。この拡張は、最小化述語の拡張が知識ベース中の名前付き個体の拡張のみを含むことができるという点で、周回に基づいており、以前の周回記述論理[1,3]から逸脱している。この改良された意味論は、直感的な魅力が高いだけでなく、可逆性を失うことなく、表現力豊かな記述論理に適用可能である。

RDF Semantics for Web Association Rules

我々は、RDFSクラスの集合間の関連について保持するルールのアサーションを許容するRDFSの語彙拡張を提示し、クラスサブ仮定やインスタンス型付けと相互作用しながら、コンテキスト、サポート、確信度を伴う関連ルールに一般的に与えられる意味を適切に捉える言語拡張のステートメントに実世界のセマンティクスを与える。さらに、アソシエーションルールの包含問題に対する健全で完全な手続きを示す。

Root Justifications for Ontology Repair

オントロジー（用語集、知識ベースとも呼ばれる）は、あるドメイン（知識分野）を表現するために使用される実体である。通常、オントロジーの構成要素には、カテゴリー（概念）、関係（役割）、オブジェクト（個体）が含まれる。

記述論理（DL）は、オントロジーを形式化し、推論するのに適した知識表現言語のクラスである[1]。推論プロセスは、選択されたDL推論者によって実行される。我々はDLの包括的な紹介はしないが、読者にはBaaderらの本[1]を紹介する。

ELOG: A Probabilistic Reasoner for OWL EL

対数線形記述論理は、知識表現と推論、統計的関係AIの分野からいくつかの概念と手法を組み合わせた確率論的論理である。我々は対数線形推論器ELOGの実装の詳細について述べる。この推論器は、推論問題を動的に整数線形計画（ILP）に変換するデータベース技術を採用している。ILPのサイズを小さくし、複雑さを軽減するために、推論中に切断平面推論の形式を採用する。

Combining Production Systems and Ontologies

生産システムは知識表現において確立されたパラダイムであり、オントロジーはアプリケーションのドメインをモデル化し推論するために広く使われている。記述論理は、例えばWebオントロジー言語OWLの基礎となっており、オントロジーを表現するための形式論としてよく研究されている。この研究では、生産システム（ps）と記述論理（dl）を組み合わせて、オントロジー言語を使って事実とルールの両方を表現できるようにする。

PSの伝統的なクローズドワールドセマンティクスとdlのオープンワールドセマンティクスを組み合わせるための設計オプションの空間を探索し、そのような組み合わせのための一般的なセマンティクスを提案する。我々の意味論をどのように一階論理のフィックスポイント拡張で符号化するかを示す。特殊な場合（単調なPSと軽いPS）において、終了などのシステムの性質をチェックすることが決定可能であることを示す。

MapResolve

我々は、MapReduceをベースとした、記述論理オントロジーのスケーラブルな推論へのアプローチを提案する。我々の研究は、RDFSオントロジーの高速な実体化を提供し、より表現力の高いロジックのためのMapReduceを提案した以前の研究に触発されている。より高い表現力によって課される課題を説明し、それらがどのように解決されるかを述べる。

Inline Evaluation of Hybrid Knowledge Bases

知識表現フォーマリズムのウェブへの展開により、異種知識ベースを結合するハイブリッドフォーマリズムの必要性が生じている。この研究の目的は、ハイブリッド知識ベース(KB)上での推論効率を向上させることである。ハイブリッド知識ベースに対する従来の推論方法は、異なるデータソースにアクセスするために異なる推論器を使用することであり、これはオーバーヘッドを引き起こす。これを改善するために、我々はインライン評価と呼ばれる新しい戦略を提案する。したがって、推論タスクを実行するために単一の推論器を使用することができ、ハイブリッド推論の効率を向上させることができる。

Web Reasoning and Rule Systems

Web Reasoning and Rule Systems

contents

コメント