DEIM Forum 2012 E11-6 RDFS Induction: URI の共通性を利用した Linked Data に対するスキーマ推定手法 大澤昇平 # 天笠俊之 北川博之 筑波大学大学院システム情報工学研究科 筑波大学システム情報系 # 宇宙航空研究開発機構宇宙科学研究所宇宙科学情報解析研究系 E-mail: shohei.ohsawa@kde.cs.tsukuba.ac.jp, {amagasa, kitagawa}@cs.tsukuba.ac.jp あらまし近年, ウェブ工学, 図書館情報学, 生物情報学の分野において, 各組織の所持するデータの相互運用性を高める ため, データをウェブ上で効率的にやり取りするための取り組みとして,linked data が話題になっている.Linked data の問題点 として, 提供されるデータのほとんどには, スキーマ情報が付随していないということが挙げられる. そこで, 我々は,RDF データの集合からスキーマ情報を推定する手法 RDFS Induction を提案する.RDFS Induction は, オブジェクトの URI を利用して, データに潜在するスキーマ情報を RDFS として推定する. 本手法において推定するスキーマ情報は,rdfs:subClassOf?, rdfs:domain, rdfs:range, owl:sameas の 4 つである. 本論文では, 実データに対して RDFS Induction を適用し, その結果について評価を行う. キーワード Linked data, RDFS, 知識抽出 1. はじめに近年, ウェブ工学, 図書館情報学, 生物情報学の分野において, 各組織の所持するデータの相互運用性を高めるため, データをウェブ上で効率的にやり取りするための取り組みとして, linked data が話題になっている.Linked data とは,RDF データの共有方法について定義したものであり,2011 年 9 月現在で 310 億件存在していると報告されている RDF データ 1 は, すべて linked data に準拠している. Linked data の現状として, linked data に準拠した多くの RDF データにおいて,RDFS データが記述されていないという問題がある. 図 1 はウェブ上に存在する linked data の SPARQL エンドポイントを対象に, 提供されている RDF トリプルの種類の内訳を, 我々が調査したものである. rdf:type などのスキーマ情報と無関係な情報は 90% 以上のエンドポイントで提供されているのに対し,rdfs: を名前空間に持つスキーマ情報は, 55% 以下のエンドポイントでしか提供されていない. 特に, 述語の定義域を表す rdfs:domain を提供しているエンドポイントは, 全体の 42% であった. また, RDF データへの問合せ処理の高速化を行なうため,RDF データに含まれる RDFS データを利用して最適化を行う手法が提案されている [1]. そのため, linked data に準拠した RDF データのうち, およそ半数には, こうした手法を適用することができないという問題がある. 以上の理由から,linked data における 1 http://www.w3.org/wiki/sweoig/taskforces/community Projects/LinkingOpenData RDFS データの拡充が課題点であると考えられる. Linked data における RDFS データの拡充を行なうため, 我々は RDFS データを持たない RDF データからスキーマ情報を推定する手法 RDFS Induction を提案する. RDFS Induction は, リソースが持つ URI の共通性に注目し, データに潜在するスキーマ情報に関するルールを,RDFS として帰納的に推定する技術のことである. ここで, 推定するスキーマ情報は, それぞれ rdfs:subclassof, rdfs:domain, rdfs:range, owl:sameas を述語に持つ 4 種類の RDF トリプルである. RDFS Induction の効果として, RDF データの公開者に対する RDFS の入力支援や, 既存のデータに対するデータ構造の理解などが期待できる. 2. 関連研究半構造データからのスキーマ抽出についての先行研究として, Chidlovskii ら [2], Hegewald ら [3], による研究があげられる. [2] では, 文脈自由文法の拡張である ECFG(extended context-free grammar) を用いて XML スキーマを表現し, 複数の XML データから ECFG を生成する手法について提案している.[3] では, 複数の XML から XML スキーマを導出する XStruct というシステムを提案し,1G バイトの XML データに対し, 速度, メモリ使用量の観点から評価を行なっている.RDF も,RDF/XML という仕様に沿った表現を行なうことで, XML による表現が可能であるため, 彼らの手法を適用することが可能である. しかし, 彼らの手法では,RDFS Induction が対象にしている RDF
% of provided per all endpoints 100.0% 50.0% 0.0% predicate 各 SPARQL エンドポイントに対し, 条件部に述語名のみを指定した問合せを行い,1 件以上問合せ結果を返したエンドポイントの数を, 全体数で除した % 値をグラフとして図示している. この調査では, http://www.w3.org/wiki/sparqlendpoints( W3C により運営 ) に掲載されている "Currently Alive SPARQL Endpoints 表で一覧されている 50 件のエンドポイントのうち, 2011 年 10 月時点でアクセス可能だったものを対象にした. 実際には, 50 件中, アクセスが確認できたものは 24 件であり. 他のものは問合せがタイムアウトしたか, 既にデータの提供を終了していた. 横軸は, 問合せの際に指定した述語を表している. (any) は, 任意の述語を指定した場合を意味する. 図 1 データソースごとに提供されているスキーマ情報の統計 Schema に関する情報を導出することはできない. James ら [4] は, 帰納論理プログラミング (inductive logic programming) を HTML で記述された文書に対して適用することで, 文書に潜在するルールを述語論理による仮説空間として抽出する技術を提案している. 本論文では, データからオントロジの形式でルールを抽出するという点では, 帰納論理プログラミングとを共通しているが, linked data の枠組みで提供されるリソースの持つ, URI の共通性をルール抽出に用いている点に新規性がある. Schmidt ら [1] は,RDFS データを用いた SPARQL 問合せの最適化,semantic SPARQL optimization を提案している. ただし, 既に議論したように, 多くの SPARQL エンドポイントでは RDFS が提供されていないため, そのままこの手法を用いることはできない. また, 同文献では, この問題点について議論されていない. 本論文では, RDFS のないデータからも RDFS データを推定することができるため, 彼らの手法と組み合わせることが可能である. 3. 提案手法 3.1 共通接頭辞仮説 linked data の枠組みでは, 共通のクラスに属するリソース同士は, 十分な長さを持った共通の URI prefix を持つことが経験的に知られている. たとえば, Bio2RDF [5] に参画している組織が提供するデータにおいては, タンパク質を表す URI はすべて http://purl.uniprot.org/protein/*( * は任意の文字列 ) というパターンに従うよう統一されている. これは,Bio2RDF のタンパク質クラスに属するリソースに関しては, どの RDF データでも変わらない性質である. このように, あるクラス Cに属するリソースが,RDF データによらず共通の URI prefix を持つことを, 本論文ではCに対する共通接頭辞と呼ぶ. 共通接頭辞がを持つクラスは, どの RDF データで解釈しても必ず共通の URI prefix を持ったリソースの集合になる. linked data では, 参照可能 (dereferencable) な URI をリソースの同定に用いていることから, リソースを実体のあるサーバと関連付けなければならないという制約が,RDF の公開者に対して課せられる. そのため, データが局所的になることが多く共通接頭辞の存在を仮定することは多くの場合妥当であるといえる. このような共通接頭辞が, 処理の対象となるすべてのクラスに対して共通しているという仮説を, 本手法では議論の前提とする. この仮説を共通接頭辞仮説 (common prefix assumption; CPA) と呼び,DL(description logic) [6] を用いて形式的に定義する. 定義 1 (s- 埋込クラス ) 任意の RDF データに対して自身に属するインスタンスの URI が, 必ず文字列 s から始まるクラスを, s- 埋込クラスといい, EC(s) によって表記する. すなわち,S は文字列全体の集合,U は URI 全体の集合とすると, 文字列 s Sに対し,EC(s) は次式を満たす. u : EC(s), u U s 1 S(u = s + s 1 ) ただし, u は URI u によって表現されるリソースを表し,+ は文字列同士の結合を表す二項演算子である. 例 1 以下の URI によって表現されるリソースは, すべてEC( http://purl. uniprot. org/protain/ ) に属する. http://purl.uniprot.org/protain/c5b6s5 http://purl.uniprot.org/protain/b5yf41 http://purl.uniprot.org/protain/b0i3f0 定義 2 ある RDF データ D RDF において, クラス C の外延に属するすべてのインスタンスが共通の URI 接頭辞 s を持つとき,D (C EC(s)) が成立する. これを, D は C の共通接頭辞 s をモデルする といい.D CP(C, s) で表す. 定義 3( 共通接頭辞仮説 ) RDF データ集合 D RDF
と, 任意のクラス C I を考える. このとき,D に含まれる任意の RDF データ D D について, 空でない文字列 s が存在して,D CP(C, s) が成立するとき, D は共通接頭辞仮説を満たす といい, D CPA によって表記する. すなわち, D CPA C I ( D D( s S(D CP(C, s), s ))) 3.2 RDFS Induction RDFS Induction とは,CPA を仮定した RDF データ集合に含まれる RDF データから, そこに潜在するスキーマ情報を導出する手法である. CPA を仮定した条件下では, どの RDF データでクラスを解釈しても, その外延に属するオブジェクトはすべて共通の URI 接頭辞を持つ. そのため, RDFS Induction では, オブジェクトの URI に含まれる情報から, クラスの URI prefix を導出する. これは, 外延集合からクラスの性質を導出する, 帰納的アプローチであるとみなすことが可能である. RDFS Induction は, RDF を入力として受け取り, 潜在するスキーマグラフを RDF として出力する手続き (procedure) として定義される. ここで, スキーマグラフとは, rdfs:subclassof, rdfs:domain, rdfs:range, owl:sameas の 4 つの述語で構成される RDF グラフと定義する. RDFS Induction は, スキーマグラフ帰納 (schema graph induction) と, スキーマグラフ最適化 (schema graph optimization) の 2 つのフェーズを経て行われる. 次項以降で, それぞれのフェーズについて説明する. 3.3 フェーズ 1: スキーマグラフ帰納スキーマグラフ帰納では, 入力 RDF データ D に対して以下の 4 つの規則の適用を行い, スキーマグラフの帰納的な導出を行う. (a) s- 埋込クラス帰納規則 (s-embedded class induction rule) D に含まれるすべてのクラス C に対して, その外延から s- 埋込クラスを導出する規則を, s- 埋込クラス帰納規則と呼ぶ. すなわち, a C i (a = s + s i ) C i EC i (s) C EC(s) ( CPA) Dom(p) i EC i (s) Dom(p) EC(s) ( CPA) ただし, Dom(p) は p の定義域で, (p, rdfs: domain, Dom(p)) ( トリプル表現 ) である. (c) 値域帰納規則 (range induction rule) 値域帰納規則では, D に含まれるすべての述語 p に対して値域の導出を行う. (a, b) p i (b = s + s i ) Range(p) i EC i (s) Range(p) EC(s) ( CPA) ただし, Range(p) は p の値域で, (p, rdfs: range, Range(p)) ( トリプル表現 ) である. (d) 親クラス導出規則 (super class derivation rule) 親クラス導出では, 二つの s- 埋込クラスが共通して持つ親クラスの導出を行う. C EC(s + s 1 ) C EC(s + s 2 ) EC(s + s 1 ) EC(s) EC(s + s 2 ) EC(s) このうち, s- 埋込クラス帰納規則の例を図 2 に示す. この例では,UniProt の提供するデータのうち, タンパク質クラスである uniprot:protain と, その外延が図示されている ( ここで, uniprot: は http://purl.uniprot.org/ を略記したものである ). このグラフから,uniprot:Protain の外延は, すべて uniprot:uniprot/ という URI prefix を持っていることがわかる. このとき, uniprot:protain のクラス外延を内包する極小クラスは EC( uniprot: uniprot/ ) である. そのため, uniprot:protain は EC( uniprot: uniprot/ ) に内応されることが帰納的に導出できる. このとき, クラスの内包関係が他のデータソースにおいても成立することは, CPA によって保証されている. RDF データにおいては, EC(s) の URI は smr:embeddedclass[ s ] によって表記する. そのため, (uniprot:protain, rdfs:subclassof, smr:embeddedclass) という新しいトリプルが導出される. (b) 定義域帰納規則 (domain induction rule) 定義域帰納規則では, D に含まれるすべての述語 p に対して定義域の導出を行う. (a, b) p i (a = s + s i ) 図 2 s- 埋込クラス帰納規則
3.4 フェーズ 2: スキーマグラフ最適化次に, 導出されたスキーマグラフに対し, これが持つ冗長な情報を削除する処理を行なう. これを, スキーマグラフ最適化と呼ぶ. スキーマグラフ最適化では, 尐ない埋込クラスを使って, 等価なスキーマを表現できるようにする. ここでは,(a) のスキーマグラフを例に説明する. まず, スキーマグラフ最適化は, 1 つしか子クラスを持っていないクラスに注目する. すなわち, D C D 1 (D 1 C (D 1 D)) に代表クラスを選ぶことにする. 1) MECS が実在クラスを含むとき代表クラスとして実在クラスを選ぶ. 実在クラスが 2 つ以上存在するときは, 無作為に選ぶ. 2) MECS が実在クラスを含まないとき最も prefix が短い埋込クラスを代表クラスに選ぶ. これは, スキーマ情報の汎化能力を最大化するためである. これによって, 冗長なクラスを削除した結果が,(c) である. が成立するようなクラスの組 C, Dである. 本論文では, このようなケースを, D は C を単一継承 (uniquely inheritance) する と呼ぶ. 単一継承関係は, 等価関係を包摂する. すわなち, クラス間の単一継承関係を特殊化することで, クラス間の等価関係が得られる. D C D 1 (D 1 C (D 1 D)) D C D 1 ( (D 1 C) D 1 D) D C C D (let D 1 C) D C (a) Induced Schema Graph たとえば, 図中において,EC( uniprot:uniprot/ ) はサブクラスとして uniprot:protain しか持たない. そのため, EC( uniprot:uniprot/ ) の外延はすべて uniprot:protain の外延に含まれる. したがって, EC( uniprot:uniprot/ ) の外延と uniprot:protain の外延は等しくなる. このようなルールを適用して導出された, 互いに等価なクラスの集合を, 等価クラス集合 (equivalent class set) と呼ぶ. また, 等価クラス集合のうち, 自身を真に包含する別な等価クラス集合が存在しないものを, 極大等価クラス集合 (maximal equivalent class set; MECS) と呼ぶ. スキーマグラフ最適化では, 最初に入力スキーマグラフからすべての MECS を列挙する. すべての MECS を抽出したものが,(b) である. (b) Extracting MECS MECS に属する複数のクラスは, 周囲のリソースとの論理的関係を維持しながら, 1 つのクラスに縮約 (shrink) することが可能である. すなわち, MECS E に含まれる 1 つのクラスC 1 に対して, C 1 E(P(C 1 ) = P(C)) が成立する. ただし, P( ) は, 与えられたリソースを含むトリプルを表す. したがって, すべてのトリプルを,C 1 の代わりに等価な代表クラス C を使って記述しても, 矛盾を含むことがない. 本手法では, MECS が実在クラス ( substantial class; 入力データに含まれるクラス ) を含むか含まないかで場合分けし, 次のよう (c) Shrink MECS 図 3 スキーマグラフ最適化
4. 実装 4.1 RDFS の推定アルゴリズム RDF データに対して, RDFS Induction を適用するシステムの概観を図 4 に示す. このシステムは, 任意の RDF トリプルの集合を入力として受け取り, それに内在するスキーマ情報を出力するシステムであると言い換えることが可能である. induce_schema_graph() データに対して Class/Domain/Range Induction を行い,Schema Graph を帰納的に導出する. ここで, Schema Graph とは, rdfs:subclassof, owl:sameas, rdfs:domain, rdfs:raneg の関係に基づき構築される RDF グラフのことである. transform_schema_graph() Equivalent class set の抽出と, その縮退を行う. 図 4 システム概要 RDFS Induction のアルゴリズムを以下に示す.RDFS Induction では, 1) O(1) の記憶領域で処理を行うこと が可能である,2) 一回のファイルシークで処理を行な うことが可能であるといった利点がある. 1. function induce_schema_graph() 2. while not end_of_triples() 3. s, p, o = read_triple() 4. if p == rdf:type then 5. EC = get_embedded_class_by_label(o) 6. EC.learn(o) 7. else 8. dom = get_domain_by_label(p) 9. dom.learn(s) 10. range = get_domain_by_label(p) 11. range.learn(o) 12. end if 13. end while 14. emit_all_embedded_classes (); 15. emit_all_embedded_domains (); 16. emit_all_embedded_ranges() 17. end function; 18. 19. function transform_schema_graph () 20. foreach EC: get_all_embedded_classes() 21. classes = EC.get_sub_classes(); 22. if classes.length == 1 then 23. emit_triple(classes[0], owl:sameas, EC) 24. emit_triple(ec, owl:sameas, classes[0]) 25. end if 26. end foreach 27. 28. foreach MECS: extract_all_minimal_equivalent_ class_sets() 29. MECS.shrink() 30. end foreach 31. end function 32. 33. function induce() 34. induce_schema_graph() 35. transform_schema_graph() 36. end function 5. 実験 5.1 実験内容 本実験では, (a) スキーマトリプルの推定精度, (b) クラス 定義域 値域帰納の精度, (c) スキーマグラ フ最適化の推定精度の評価を行う. (a) スキーマトリプルの推定精度ここでは, 定義域, 値域の推定能力について評価する. データセットを用 意し, 推定したトリプルとスキーマ情報の一致度を見 る. この時, データセットをどの程度予測できている かを評価する. 評価では, スキーマトリプルの, 正解 データに関する各スキーマトリプルを正解データと比 較し, それぞれの論理的関係にしたがい表 1 の評価カ テゴリに分類する. 以下の式によって適合率を算出す る. precision = E + I E + I + O + N. 表 1 スキーマトリプルの評価カテゴリ 評価 記号 名称 意味 * 条件 適合 E Exact スキーマ情報が完全 C r C t に等しい I Inclusive スキーマ情報が正解データを包含している C r C t 非適合 対象外 * O Over fitting 正解データがスキーマ情報を包含している N Not fitting スキーマ情報と正解 データの間に, 包含関 係が成立しない U Unknown 正解データが存在し ない C r C t (C r C t ) (C r C t ) 評価対象となるクラスを C r とし, 正解のクラスを C t と する. たとえば. 定義域に関する評価を行う場合, トリプル ex:doctoraldegreefrom rdfs:domain ex:student については, ex:student が評価対象のクラスとなる. (b) クラス 定義域 値域帰納の精度実験では, 推 定されたスキーマ情報の汎化能力について評価するこ とを目的とする. ここでの汎化能力とは, ある RDF デ ータから抽出されたスキーマ情報が, 他の RDF データ に対しても適合するかどうかを意味する.
% of vaiolation per all classes # of triples 実験の手順について説明する. まず, 入力 RDF データから, 互いに素な訓練集合とテスト集合をサンプリングする. サンプリングは, ランダムサンプリングによって行なう. 訓練集合に RDFS Induction を適用し, スキーマ情報を得る. 次に, テスト集合をスキーマ情報と比較し, 適合しているかどうかを見る. 適合しているかどうかは, テスト集合に含まれる各トリプルを評価対象のスキーマ情報と比較し, 表 2 に示すスキーマ違反 (schema violation) の数を調べることで行なう. 実験では, 実世界にある RDF データを用いる. 本論文では,UniProt [7] が公開している RDF データ 2 を用いる. 40 35 30 25 20 15 10 5 0 rdfs:domain Predicate rdfs:range Unknown Not fitting Over fitting Inclusive Exact 表 2 スキーマ違反 図 5 実験結果 クラス違反 ドメイン違反 レンジ違反 テスト集合からの入力トリプル 比較するスキーマ情報 s rdf:type C C rdfs:subclassof EC(a) s p o, where p rdf:type s p o, where p rdf:type p rdfs:domain EC(a) p rdfs:range EC(a) チェックする違反内容 sの URI prefix が a になっていない sの URI prefix が a になっていない oの URI prefix が a になっていない (b) クラス 定義域 値域帰納の精度実験結果を図 6 および表 3 に示す. 訓練集合のサイズが大きくなるに伴い, 過学習が抑えられることで汎化能力が向上し, 違反の割合が低減していることが観察できる.100k トリプルでは, 誤差 0.01% の性能を得ている. 25.00% 20.00% (c) スキーマグラフ最適化の性能スキーマグラフ最適化では, 入力したスキーマグラフに含まれている EC がどの程度尐なくなったかによって評価を行なう. 5.2 実験結果 (a) スキーマトリプルの推定精度実験結果を図 5 に示す. 適合率は,rdfs:domain に対して 51%,rdfs:range に対して 69% だった. この手法から,aRDFS Induction では,UniProt のデータセットに対しては,51% 以上の精度でスキーマを推定することが可能であるといえる. 一方で, 非適合例のうち, over fitting では, 正解データのクラスが OWL の範囲で複雑に表現されており, RDFS Induction では表現しきれないという例が多く観察された. こうした問題に対しては, 推定するスキーマの表現力を,RDFS だけでなく OWL の範囲に向上させることで対応する必要があると考えられる. 15.00% 10.00% 5.00% 0.00% 1000 10000 100000 # of triples in learning set 図 6 スキーマ違反の割合 表 3 実験結果 Learning Set Size 1000 10000 100000 Test Set Size 100000 100000 100000 Checked Triples 96554 97851 99983 Valid Triples 76125 95882 99971 Checked Classes 66 75 104 Valid Classes 30 61 101 Error 21.16% 2.01% 0.01% (c) スキーマグラフ最適化の性能 s- 埋込クラスの減尐数を, 表に示す. 表より, スキーマグラフ最適化が, s- 埋込クラスの量を 42% に低減させていることが観察できる. 出力データに残っている s- 埋込クラスは, 述語の定義域や値域として推定されたものであった. 2 http://www.uniprot.org/
6. 結論 表 4 s- 埋込クラスの減尐数 s- 埋込クラス数 入力データ 24 出力データ 10 本論文では, 与えられたスキーマ情報を含まない RDF データから, 潜在するスキーマ情報を復元する技 術,RDFS Induction について提案し, 実データに対す る実験を行った. 実データに関する実験結果では,100k トリプルの訓練集合で学習した場合に, 誤差 0.01% の 精度を得た. 参考文献 [1] Michael Schmidt, Michael Meier, and Georg Lausen, "Foundations of SPARQL Query Optimization," The 13th International Conference on Database Theory (ICDT2010), Lausanne, Switzerland, 2010. [2] Boris Chidlovskii, "Schema extraction from XML: a grammatical inference approach," Proceedings of Workshop on Knowledge Representation meets Databases KRDB, 2001. [3] Jan Hegewald, Felix Naumann, and Melanie Weis, "XStruct: Efficient Schema Extraction from Multiple and Large XML Documents," Proceedings of the 22nd International Conference on Data Engineering Workshops (ICDEW'06), 2006. [4] J. S. Aitken, "Learning Information Extraction Rules: An Inductive Logic Programming approach," 2002. [5] M. Nolina, N. Tourigny, P. Rigaulta, and J. Morissettea F. Belleaua, "Bio2RDF: Towards a mashup to build bioinformatics knowledge systems," Journal of Biomedical Informatics, vol. 41, no. 5, pp. 706-716, October 2008. [6] Franz Baader (Editor), Diego Calvanese (Editor), Deborah McGuinness (Editor), Daniele Nardi (Editor), and Peter Patel-Schneider (Editor), The Description Logic Handbook: Theory, Implementation, and Applications.: Cambridge University Press, 2003. [7] A. Bairoch, R. Apweiler, C. H. Wu, W. C. Barker, B. Boeckmann, S. Ferro, E. Gasteiger, H. Huang, R. Lopez, M. Magrane, M. J. Martin, D. A. Natale, C. O'Donovan, N. Redaschi, and L. L. Yeh, "The universal protein resource (UniProt)," 2005.