電子情報通信学会ワードテンプレート (タイトル)

DEIM Forum 2012 E11-6

RDFS Induction: URI の共通性を利用した

Linked Data に対するスキーマ推定手法

大澤 昇平

†

天笠 俊之

‡#

北川 博之

‡

†筑波大学大学院 システム情報工学研究科

‡筑波大学 システム情報系

#宇宙航空研究開発機構 宇宙科学研究所 宇宙科学情報解析研究系

E-mail: [email protected], {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

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 デ ー タ で も 変 わ ら な い 性 質 で あ る ． こ の よ う に ，あ る ク ラ ス𝐶に 属 す る リ ソ ー ス が ，RDF デ ー タ に よ ら ず 共 通 の URI prefix を 持 つ こ と を ， 本 論 文 で は𝐶に 対 す る共 通 接 頭 辞と 呼 ぶ ． 共 通 接 頭 辞 が を 持 つ ク ラ ス は ，ど の RDF デ ー タ で 解 釈 し て も 必 ず 共 通 の URI prefix を 持 っ た リ ソ ー ス の 集 合 に な る ．

linked data で は ， 参 照 可 能 (dereferencable)な URI を リ ソ ー ス の 同 定 に 用 い て い る こ と か ら ， リ ソ ー ス を 実 体 の あ る サ ー バ と 関 連 付 け な け れ ば な ら な い と い う 制 約 が ，RDF の 公 開 者 に 対 し て 課 せ ら れ る ．そ の た め ， デ ー タ が 局 所 的 に な る こ と が 多 く 共 通 接 頭 辞 の 存 在 を 仮 定 す る こ と は 多 く の 場 合 妥 当 で あ る と い え る ． こ の よ う な 共 通 接 頭 辞 が ， 処 理 の 対 象 と な る す べ て の ク ラ ス に 対 し て 共 通 し て い る と い う 仮 説 を ， 本 手 法 で は 議 論 の 前 提 と す る ． こ の 仮 説 を共 通 接 頭 辞 仮 説 (common prefix assumption; CPA)と 呼 び ，DL(description logic) [6]を 用 い て 形 式 的 に 定 義 す る ． 定 義 1 (𝑠-埋 込 ク ラ ス ) 任 意 の RDF デ ー タ に 対 し て 自 身 に 属 す る イ ン ス タ ン ス の URI が ， 必 ず 文 字 列 𝑠 か ら 始 ま る ク ラ ス を ，𝑠-埋 込 ク ラ ス と い い ，𝐸𝐶(𝑠)に よ っ て 表 記 す る ．す な わ ち ，𝑆 は 文 字 列 全 体 の 集 合 ，𝑈 は URI 全 体 の 集 合 と す る と ，文 字 列 𝑠 ∈ 𝑆に 対 し ，𝐸𝐶(𝑠) は 次 式 を 満 た す ． 〈𝑢〉: 𝐸𝐶(𝑠), 𝑢 ∈ 𝑈 ⟺ ∃𝑠1∈ 𝑆(𝑢 = 𝑠 + 𝑠1) た だ し ， 〈𝑢〉 は URI 𝑢 に よ っ て 表 現 さ れ る リ ソ ー ス を 表 し ，+ は 文 字 列 同 士 の 結 合 を 表 す 二 項 演 算 子 で あ る ． 例 1 以 下 の URI に よ っ て 表 現 さ れ る リ ソ ー ス は ， す べ て𝐸𝐶(”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 デ ー タ 𝐷 ∈ 𝐑𝐃𝐅 に お い て ， ク ラ ス 𝐶 の 外 延 に 属 す る す べ て の イ ン ス タ ン ス が 共 通 の URI 接 頭 辞 𝑠 を 持 つ と き ， 𝐷 ⊨ (𝐶 ⊑ 𝐸𝐶(𝑠)) が 成 立 す る ．こ れ を ，「𝐷 は 𝐶 の 共 通 接 頭 辞 𝑠 を モ デ ル す る 」 と い い ．𝐷 ⊨ CP(𝐶, 𝑠) で 表 す ． 定 義 3（ 共 通 接 頭 辞 仮 説 ） RDF デ ー タ 集 合 𝔇 ⊆ 𝐑𝐃𝐅 各 SPARQL エ ン ド ポ イ ン ト に 対 し ，条 件 部 に 述 語 名 の み を 指 定 し た 問 合 せ を 行 い ，1 件 以 上 問 合 せ 結 果 を 返 し た エ ン ド ポ イ ン ト の 数 を ， 全 体 数 で 除 し た %値 を グ ラ フ と し て 図 示 し て い る ． こ の 調 査 で は ， htt p ://www. w3. org/w ik i/Spa rq lE ndp oints（ W3C に よ り 運 営 ）に 掲 載 さ れ て い る "C urrently Alive SPARQL Endpoints” 表 で 一 覧 さ れ て い る 50 件 の エ ン ド ポ イ ン ト の う ち ， 2011 年 10 月 時 点 で ア ク セ ス 可 能 だ っ た も の を 対 象 に し た ． 実 際 に は ， 50 件 中 ， ア ク セ ス が 確 認 で き た も の は 24 件 で あ り ． 他 の も の は 問 合 せ が タ イ ム ア ウ ト し た か ， 既 に デ ー タ の 提 供 を 終 了 し て い た ．横 軸 は ，問 合 せ の 際 に 指 定 し た 述 語 を 表 し て い る ． (any)は ， 任 意 の 述 語 を 指 定 し た 場 合 を 意 味 す る ． 図 1 デ ー タ ソ ー ス ご と に 提 供 さ れ て い る ス キ ー マ 情 報 の 統 計 0.0% 50.0% 100.0% % o f p ro v id ed p er a ll e n d p o in ts predicate

と ，任 意 の ク ラ ス 𝐶 ∈ 𝐈 を 考 え る ．こ の と き ，𝔇 に 含 ま れ る 任 意 の RDF デ ー タ 𝐷 ∈ 𝔇 に つ い て ， 空 で な い 文 字 列 𝑠 が 存 在 し て ，𝐷 ⊨ CP(𝐶, 𝑠) が 成 立 す る と き ，「𝔇 は 共 通 接 頭 辞 仮 説 を 満 た す 」 と い い ，𝔇 ⊨ CPA に よ っ て 表 記 す る ． す な わ ち ， 𝔇 ⊨ CPA ⇔ 𝐶 ∈ 𝐈 ( 𝐷 ∈ 𝔇(∃𝑠 ∈ 𝑆(𝐷 ⊨ CP(𝐶, 𝑠), 𝑠 ))) 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 デ ー タ 𝐷 に 対 し て 以 下 の 4 つ の 規 則 の 適 用 を 行 い ， ス キ ー マ グ ラ フ の 帰 納 的 な 導 出 を 行 う ．

(a) 𝑠-埋 込 ク ラ ス 帰 納 規 則 (s-embedded class induction rule) 𝐷 に 含 ま れ る す べ て の ク ラ ス 𝐶 に 対 し て ， そ の 外 延 か ら 𝑠-埋 込 ク ラ ス を 導 出 す る 規 則 を ， 𝑠-埋 込 ク ラ ス 帰 納 規 則 と 呼 ぶ ． す な わ ち ， 𝑎 ∈ 𝐶𝑖_{(𝑎 = 〈𝑠 + 𝑠} 𝑖′〉) ⟹ 𝐶𝑖_{⊆ 𝐸𝐶}𝑖_(𝑠) ⟹ 𝐶 ⊑ 𝐸𝐶(𝑠) (∵ CPA)

(b) 定 義 域 帰 納 規 則 (domain induction rule) 定 義 域 帰 納 規 則 で は ，𝐷 に 含 ま れ る す べ て の 述 語 𝑝 に 対 し て 定 義 域 の 導 出 を 行 う ． (𝑎, 𝑏) ∈ 𝑝𝑖_{(𝑎 = 〈𝑠 + 𝑠} 𝑖′〉) ⟹ 𝐷𝑜𝑚(𝑝)𝑖_{⊆ 𝐸𝐶}𝑖_(𝑠) ⟹ 𝐷𝑜𝑚(𝑝) ⊑ 𝐸𝐶(𝑠) (∵ CPA) た だ し ， 𝐷𝑜𝑚(𝑝) は 𝑝 の 定 義 域 で ， (𝑝, rdfs: domain, 𝐷𝑜𝑚(𝑝)) （ ト リ プ ル 表 現 ） で あ る ．

(c) 値 域 帰 納 規 則 (range induction rule) 値 域 帰 納 規 則 で は ，𝐷 に 含 ま れ る す べ て の 述 語 𝑝 に 対 し て 値 域 の 導 出 を 行 う ． (𝑎, 𝑏) ∈ 𝑝𝑖_{(𝑏 = 〈𝑠 + 𝑠} 𝑖′〉) ⟹ 𝑅𝑎𝑛𝑔𝑒(𝑝)𝑖_{⊆ 𝐸𝐶}𝑖_(𝑠) ⟹ 𝑅𝑎𝑛𝑔𝑒(𝑝) ⊑ 𝐸𝐶(𝑠) (∵ CPA) た だ し ， 𝑅𝑎𝑛𝑔𝑒(𝑝) は 𝑝 の 値 域 で ， (𝑝, rdfs: range, 𝑅𝑎𝑛𝑔𝑒(𝑝)) （ ト リ プ ル 表 現 ） で あ る ．

(d) 親 ク ラ ス 導 出 規 則 (super class derivation rule) 親 ク ラ ス 導 出 で は ， 二 つ の s-埋 込 ク ラ ス が 共 通 し て 持 つ 親 ク ラ ス の 導 出 を 行 う ． 𝐶 ⊑ 𝐸𝐶(𝑠 + 𝑠1) ∧ 𝐶′⊑ 𝐸𝐶(𝑠 + 𝑠2) ⟹ 𝐸𝐶(𝑠 + 𝑠1) ⊑ 𝐸𝐶(𝑠) ∧ 𝐸𝐶(𝑠 + 𝑠2) ⊑ 𝐸𝐶(𝑠) こ の う ち ，𝑠-埋 込 ク ラ ス 帰 納 規 則 の 例 を 図 2 に 示 す ． こ の 例 で は ，UniProt の 提 供 す る デ ー タ の う ち ，タ ン パ ク 質 ク ラ ス で あ る uniprot:Protain と ，そ の 外 延 が 図 示 さ れ て い る （ こ こ で ， uniprot: は http://purl.uniprot.org/ を 略 記 し た も の で あ る ）．こ の グ ラ フ か ら ，uniprot:Protain の 外 延 は ， す べ て uniprot:uniprot/と い う URI prefix を 持 っ て い る こ と が わ か る ． こ の と き ， uniprot:Protain の ク ラ ス 外 延 を 内 包 す る 極 小 ク ラ ス は 𝐸𝐶( uniprot: uniprot/ ) で あ る ． そ の た め ， uniprot:Protain は𝐸𝐶( uniprot: uniprot/ )に 内 応 さ れ る こ と が 帰 納 的 に 導 出 で き る ． こ の と き ， ク ラ ス の 内 包 関 係 が 他 の デ ー タ ソ ー ス に お い て も 成 立 す る こ と は ， CPA に よ っ て 保 証 さ れ て い る ． RDF デ ー タ に お い て は ， 𝐸𝐶(𝑠) の URI は smr:EmbeddedClass[“𝑠”]に よ っ て 表 記 す る ． そ の た め ， (uniprot:Protain , rdfs:subClassOf, smr:EmbeddedClass) と い う 新 し い ト リ プ ル が 導 出 さ れ る ． 図 2 𝒔-埋 込 ク ラ ス 帰 納 規 則

3.4 フ ェ ー ズ 2: ス キ ー マ グ ラ フ 最 適 化 次 に ， 導 出 さ れ た ス キ ー マ グ ラ フ に 対 し ， こ れ が 持 つ 冗 長 な 情 報 を 削 除 す る 処 理 を 行 な う ． こ れ を ， ス キ ー マ グ ラ フ 最 適 化 と 呼 ぶ ．ス キ ー マ グ ラ フ 最 適 化 で は ， 尐 な い 埋 込 ク ラ ス を 使 っ て ， 等 価 な ス キ ー マ を 表 現 で き る よ う に す る ．こ こ で は ，(a)の ス キ ー マ グ ラ フ を 例 に 説 明 す る ． ま ず ， ス キ ー マ グ ラ フ 最 適 化 は ， 1 つ し か 子 ク ラ ス を 持 っ て い な い ク ラ ス に 注 目 す る ． す な わ ち ， 𝐷 ⊑ 𝐶 ∧ ¬∃𝐷1(𝐷1⊑ 𝐶 ∧ ¬(𝐷1⊑ 𝐷)) が 成 立 す る よ う な ク ラ ス の 組𝐶, 𝐷で あ る ．本 論 文 で は ， こ の よ う な ケ ー ス を ，「𝐷 は 𝐶 を単 一 継 承(uniquely inheritance)す る 」 と 呼 ぶ ． 単 一 継 承 関 係 は ， 等 価 関 係 を 包 摂 す る ． す わ な ち ， ク ラ ス 間 の 単 一 継 承 関 係 を 特 殊 化 す る こ と で ， ク ラ ス 間 の 等 価 関 係 が 得 ら れ る ． 𝐷 ⊑ 𝐶 ∧ ¬∃𝐷1(𝐷1⊑ 𝐶 ∧ ¬(𝐷1⊑ 𝐷)) ⟺ 𝐷 ⊑ 𝐶 ∧ 𝐷1(¬(𝐷1⊑ 𝐶) ∨ 𝐷1⊑ 𝐷) ⟹ 𝐷 ⊑ 𝐶 ∧ 𝐶 ⊑ 𝐷 (let 𝐷1≡ 𝐶) ⟺ 𝐷≡𝐶 た と え ば ，図 中 に お い て ，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)で あ る ． MECS に 属 す る 複 数 の ク ラ ス は ， 周 囲 の リ ソ ー ス と の 論 理 的 関 係 を 維 持 し な が ら ， 1 つ の ク ラ ス に 縮 約 (shrink)す る こ と が 可 能 で あ る ． す な わ ち ， MECS 𝐸 に 含 ま れ る 1 つ の ク ラ ス𝐶1に 対 し て ， 𝐶1∈ 𝐸(𝑃(𝐶1) = 𝑃(𝐶)) が 成 立 す る ． た だ し ，𝑃(∙)は ， 与 え ら れ た リ ソ ー ス を 含 む ト リ プ ル を 表 す ． し た が っ て ， す べ て の ト リ プ ル を ，𝐶1の 代 わ り に 等 価 な 代 表 ク ラ ス 𝐶 を 使 っ て 記 述 し て も ， 矛 盾 を 含 む こ と が な い ． 本 手 法 で は ， MECS が 実 在 ク ラ ス（ substantial class; 入 力 デ ー タ に 含 ま れ る ク ラ ス ） を 含 む か 含 ま な い か で 場 合 分 け し ， 次 の よ う に 代 表 ク ラ ス を 選 ぶ こ と に す る ． 1) MECS が 実 在 ク ラ ス を 含 む と き 代 表 ク ラ ス と し て 実 在 ク ラ ス を 選 ぶ ． 実 在 ク ラ ス が 2 つ 以 上 存 在 す る と き は ， 無 作 為 に 選 ぶ ． 2) MECS が 実 在 ク ラ ス を 含 ま な い と き 最 も prefix が 短 い 埋 込 ク ラ ス を 代 表 ク ラ ス に 選 ぶ ． こ れ は ， ス キ ー マ 情 報 の 汎 化 能 力 を 最 大 化 す る た め で あ る ． こ れ に よ っ て ，冗 長 な ク ラ ス を 削 除 し た 結 果 が ，(c) で あ る ．

(a) Induced Schema Graph

(b) Extracting MECS

(c) Shrink MECS 図 3 ス キ ー マ グ ラ フ 最 適 化

4. 実 装

4.1 RDFS の 推 定 ア ル ゴ リ ズ ム RDF デ ー タ に 対 し て ， RDFS Induction を 適 用 す る シ ス テ ム の 概 観 を 図 4 に 示 す ．こ の シ ス テ ム は ，任 意 の RDF ト リ プ ル の 集 合 を 入 力 と し て 受 け 取 り ，そ れ に 内 在 す る ス キ ー マ 情 報 を 出 力 す る シ ス テ ム で あ る と 言 い 換 え る こ と が 可 能 で あ る ． 図 4 シ ス テ ム 概 要 RDFS Induction の ア ル ゴ リ ズ ム を 以 下 に 示 す ．RDFS Induction で は ， 1) 𝑂(1)の 記 憶 領 域 で 処 理 を 行 う こ と が 可 能 で あ る ，2) 一 回 の フ ァ イ ル シ ー ク で 処 理 を 行 な う こ と が 可 能 で あ る と い っ た 利 点 が あ る ． 1. function induce_schema_graph()

2. while not end_of_triples()

3. s, p, o = read_triple() 4. if p == rdf:t ype 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 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 の 抽 出 と ， そ の 縮 退 を 行 う ．

5. 実 験

5.1 実 験 内 容 本 実 験 で は ， (a) ス キ ー マ ト リ プ ル の 推 定 精 度 ， (b) ク ラ ス ・ 定 義 域 ・ 値 域 帰 納 の 精 度 ， (c) ス キ ー マ グ ラ フ 最 適 化 の 推 定 精 度 の 評 価 を 行 う ． (a) ス キ ー マ ト リ プ ル の 推 定 精 度 こ こ で は ，定 義 域 ， 値 域 の 推 定 能 力 に つ い て 評 価 す る ． デ ー タ セ ッ ト を 用 意 し ， 推 定 し た ト リ プ ル と ス キ ー マ 情 報 の 一 致 度 を 見 る ． こ の 時 ， デ ー タ セ ッ ト を ど の 程 度 予 測 で き て い る か を 評 価 す る ． 評 価 で は ， ス キ ー マ ト リ プ ル の ， 正 解 デ ー タ に 関 す る 各 ス キ ー マ ト リ プ ル を 正 解 デ ー タ と 比 較 し ，そ れ ぞ れ の 論 理 的 関 係 に し た が い 表 1 の 評 価 カ テ ゴ リ に 分 類 す る ． 以 下 の 式 に よ っ て 適 合 率 を 算 出 す る ． precision =_{|𝐸| + |𝐼| + |𝑂| + |𝑁|}|𝐸| + |𝐼| . 表 1 ス キ ー マ ト リ プ ル の 評 価 カ テ ゴ リ 評 価 記 号 名 称 意 味 条 件* 適 合 E E xact ス キ ー マ 情 報 が 完 全 に 等 し い 𝐶𝑟≡ 𝐶𝑡

I Inc lus ive ス キ ー マ 情 報 が 正 解 デ ー タ を 包 含 し て い る

𝐶𝑟⊒ 𝐶𝑡

非 適 合

O Over fitt ing 正 解 デ ー タ が ス キ ー マ 情 報 を 包 含 し て い る

𝐶𝑟⊑ 𝐶𝑡

N Not fitt ing ス キ ー マ 情 報 と 正 解 デ ー タ の 間 に ， 包 含 関 係 が 成 立 し な い ¬(𝐶𝑟⊑ 𝐶𝑡) ∧ ¬(𝐶𝑟⊒ 𝐶𝑡) 対 象 外 U Unk no w n 正 解 デ ー タ が 存 在 し な い * _{評 価 対 象 と な る ク ラ ス を 𝐶} 𝑟 と し ， 正 解 の ク ラ ス を 𝐶𝑡 と す る ．た と え ば ．定 義 域 に 関 す る 評 価 を 行 う 場 合 ，ト リ プ ル ex:doctoralDegreeFrom rdfs:domain ex:Student に つ い て は ， ex:Student が 評 価 対 象 の ク ラ ス と な る ． (b) ク ラ ス ・ 定 義 域 ・ 値 域 帰 納 の 精 度 実 験 で は ， 推 定 さ れ た ス キ ー マ 情 報 の 汎 化 能 力 に つ い て 評 価 す る こ と を 目 的 と す る ．こ こ で の 汎 化 能 力 と は ，あ る RDF デ ー タ か ら 抽 出 さ れ た ス キ ー マ 情 報 が ，他 の RDF デ ー タ に 対 し て も 適 合 す る か ど う か を 意 味 す る ．

実 験 の 手 順 に つ い て 説 明 す る ．ま ず ，入 力 RDF デ ー タ か ら ， 互 い に 素 な 訓 練 集 合 と テ ス ト 集 合 を サ ン プ リ ン グ す る ． サ ン プ リ ン グ は ， ラ ン ダ ム サ ン プ リ ン グ に よ っ て 行 な う ． 訓 練 集 合 に RDFS Induction を 適 用 し ， ス キ ー マ 情 報 を 得 る ． 次 に ， テ ス ト 集 合 を ス キ ー マ 情 報 と 比 較 し ， 適 合 し て い る か ど う か を 見 る ． 適 合 し て い る か ど う か は ， テ ス ト 集 合 に 含 ま れ る 各 ト リ プ ル を 評 価 対 象 の ス キ ー マ 情 報 と 比 較 し ，表 2 に 示 す ス キ ー マ 違 反 (schema violation)の 数 を 調 べ る こ と で 行 な う ． 実 験 で は ，実 世 界 に あ る RDF デ ー タ を 用 い る ．本 論 文 で は ，UniProt [7]が 公 開 し て い る RDF デ ー タ2_{を 用 い} る ． 表 2 ス キ ー マ 違 反 テ ス ト 集 合 か ら の 入 力 ト リ プ ル 比 較 す る ス キ ー マ 情 報 チ ェ ッ ク す る 違 反 内 容 ク ラ ス 違 反 𝑠 rdf:type 𝐶 𝐶 rdfs:subClassOf 𝐸𝐶(𝑎) 𝑠の URI prefixが𝑎 に な っ て い な い ド メ イ ン 違 反 𝑠 𝑝 𝑜, w he r e 𝑝 rdf:type

𝑝 rdfs:domain 𝐸𝐶(𝑎) 𝑠の URI prefix が𝑎 に な っ て い な い レ ン ジ 違 反 𝑠 𝑝 𝑜, w he r e 𝑝 rdf:type

𝑝 rdfs:range 𝐸𝐶(𝑎) 𝑜の URI prefix が𝑎 に な っ て い な い (c) ス キ ー マ グ ラ フ 最 適 化 の 性 能 ス キ ー マ グ ラ フ 最 適 化 で は ，入 力 し た ス キ ー マ グ ラ フ に 含 ま れ て い る EC が ど の 程 度 尐 な く な っ た か に よ っ て 評 価 を 行 な う ． 5.2 実 験 結 果 (a) ス キ ー マ ト リ プ ル の 推 定 精 度 実 験 結 果 を 図 5 に 示 す ． 適 合 率 は ，rdfs:domain に 対 し て 51%，rdfs:range に 対 し て 69%だ っ た ．こ の 手 法 か ら ，aRDFS Induction で は ，UniProt の デ ー タ セ ッ ト に 対 し て は ，51%以 上 の 精 度 で ス キ ー マ を 推 定 す る こ と が 可 能 で あ る と い え る ． 一 方 で ， 非 適 合 例 の う ち ， over fitting で は ， 正 解 デ ー タ の ク ラ ス が OWL の 範 囲 で 複 雑 に 表 現 さ れ て お り ， RDFS Induction で は 表 現 し き れ な い と い う 例 が 多 く 観 察 さ れ た ． こ う し た 問 題 に 対 し て は ， 推 定 す る ス キ ー マ の 表 現 力 を ，RDFS だ け で な く OWL の 範 囲 に 向 上 さ せ る こ と で 対 応 す る 必 要 が あ る と 考 え ら れ る ． 2 http://www.uniprot.org/ 図 5 実 験 結 果 (b) ク ラ ス ・ 定 義 域 ・ 値 域 帰 納 の 精 度 実 験 結 果 を 図 6 お よ び 表 3 に 示 す ．訓 練 集 合 の サ イ ズ が 大 き く な る に 伴 い ， 過 学 習 が 抑 え ら れ る こ と で 汎 化 能 力 が 向 上 し ，違 反 の 割 合 が 低 減 し て い る こ と が 観 察 で き る ．100k ト リ プ ル で は ， 誤 差 0.01%の 性 能 を 得 て い る ． 図 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-埋 込 ク ラ ス は ， 述 語 の 定 義 域 や 値 域 と し て 推 定 さ れ た も の で あ っ た ． 0 5 10 15 20 25 30 35 40 rdfs:domain rdfs:range # o f tr ip les Predicate Unknown Not fitting Over fitting Inclusive Exact 0.00% 5.00% 10.00% 15.00% 20.00% 25.00% 1000 10000 100000 % o f va io la ti on p er a ll c la sses

表 4 s-埋 込 ク ラ ス の 減 尐 数 s-埋 込 ク ラ ス 数 入 力 デ ー タ 24 出 力 デ ー タ 10

6. 結 論

本 論 文 で は ， 与 え ら れ た ス キ ー マ 情 報 を 含 ま な い 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, "Le arning 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.