狠狠撸

翱奥尝で何が言えるか
福原和朗
@kazurof
2013-07-25

本発表について
? 「OWLで何が書けるか」の続きです
– http://www.slideshare.net/kazurof/owl-15329492
? 記述論理ではそのデータから推論が出来る
ようになっています。
– 記述論理はOWLの理論的基礎
? このしくみの解説を試みます。
– 致命的な間違いはないと思うんですが。

復習：OWLで何が書けるか
? 個体
– x
? 個体が概念に属するということ
– 概念は所謂個体の集合。
– A(x)
? ロール
– 個体同士の関係
– 個体 - ロール - 個体。所謂トリプル。
– R(x,y)

復習：OWLで何が書けるか(2)
? 概念とそれらの関係
– ￢, ∩,∪ による組み合わせられた概念
? C ∩ (D ∪￢ E)
– ロールと?,?による概念
? ?R.C
? Rというロールで概念Cの個体とのつながりが存在する
個体。
– 概念の包含関係?同値関係
? C ?D, E ≡ F

? ロールの特徴
– 推移的ロール
? (x,y) ∈R ∧ (y,z) ∈ R ? (x,z) ∈ R
– ロール階層
? (x,y) ∈R , R ? S ? (x,y) ∈S
– 逆ロール
? RI はRの逆ロールとする ? (x,y) ∈ R ? (y,x) ∈ RI
– 数量限定
? ≦nR , ≧nR
– データ型ロール

? ONE-OF概念
– ｛ハート、ダイヤ、クラブ、スペード｝
– いわゆる列挙
? データ型
– 文字列、数値など。
– 個体でもONE-OF概念でもない。

OWLを使って言えること
1. 概念の充足可能性
– ある概念に属する個体が理論的に存在し得るかど
うか。
2. 概念の包含関係
– 個体の集合としての包含関係。
3. 概念の同値関係
4. TBoxとABoxの無矛盾性
– TBoxとABox両方を満たす解釈が存在するか。
5. 特性の個体が特定の概念に属するかの判定
? これらを、推論タスクと呼びます。

どうやって言うか？
? タブロー法
– TBoxとABoxの内容から概念に属する個体について
の制約を生成する。
? x : A , y :B ??? 「個体x は概念Aに属する」という意味。
– それらに矛盾が発生しないかを判定する。
? 矛盾の例
? x : A , x : ￢A
? x : ⊥ ( ⊥ は空概念。)
? タブロー法により概念の充足可能性が判定可能

タブロー法の手順(1)
? 入力：TBox である T , 判定したい概念 D
? T 内の概念定義 A ≡ C で、C内に他で定義さ
れているA’ が含まれる場合それをA’で入れ
替える。入れ替えたものをT’と呼ぶ。
? 例：
T = { X ≡ Y ∪ Z , Z ≡ V ∪ W }
T’ = { X ≡ Y ∪ (V ∪ W) , Z ≡ V ∪ W }
? 左が定義される概念。右は定義のみをする
概念の組み合わせ。

T’ = {A ≡ V ∩ W, C ≡ ￢B}
D = A ∩ C
D’ = (V ∩ W) ∩ ￢B
? 判定したい概念 D について、T’ の式の左辺
と同じ物を含む場合、右辺の概念に入れ替
える。入れ替えたものをD’ とする。
? 例：

? D’ をNegative Normal Form (NNF)に変換する。
– 概念名の直前だけに否定が出現する概念の形式。
? 変換例
￢￢C → C
￢ (C ∩ D ) → ￢ C ∪￢ D
￢ (C ∪ D) → ￢ C∩￢ D
￢ (? R.C ) → ? R.￢C
￢ (? R.C ) → ? R.￢C
? DにNNF変換をしたものを、 NNF(D) と書く。

? {x : NNF(D’)}を初期集合S0とし、完備化規則を
適用する
– 制約の追加がされる。
? 追加１回ごとに新たな制約集合が作られる。
? 完備化規則には分岐する物がある。
S0
S1
S’1
S2
S3
S’3...
S4

? これ以上適用できなくなるまで繰り返す。
? 分岐先全てについて、矛盾(clash)が発生して
いるかチェック
– x : A , x : ￢A
– x :⊥ ( ⊥ は空概念)
? ある分岐先ではclashが発生しないならば、D
は充足可能。

完備化規則
1. ∩規則
2. ∪規則
3. ?規則
4. ?規則

∩規則
x : C1 ∩ C2 ∈ Si かつ {x :C1, x :C2} ￢? Si
のとき
Si -> Si+1 = Si ∪ { x : C1, x : C2}
と、変形する。
２個の集合両方に含まれる要素についてそれ
ぞれに分ける。

∪規則
x : C1 ∪ C2 ∈ Si かつ {x :C1, x :C2} ∩Si = φ
のとき
Si -> Si+1 = Si ∪ { x : C1 }
あるいは
Si -> S'i+1 = Si ∪ { x : C2 }
「どちらかに含まれる」ケース。
制約追加が分岐することになる。

?規則
x : ?R.C ∈ Si かつ { z | (x,z): R , z:C ∈Si} ≠ φ
のとき
Si -> Si+1 = Si ∪ { (x, y) : R, y : C }
但し y ?V(Si）であること。V(Si)は、Siに出現す
るすべての変数。
うまくzを選ぶとR (x,z)であるなら新しい変数yに
おいて (x, y) : R, y : C である。

?規則
x : ?R.C , (x,y) : R ∈ Si かつ y : C ? Si
のとき
Si -> Si+1 = Si ∪ { y : C }
と、変形できる。
(x,y) : R であれば、yは必ずCに属する個体だと
言える。

例
知識ベース : TBox ={A ≡ B, C ≡ ￢B}
判定したい概念 : D = A ∩ C
S1 = {x : A ∩ C}
S2 = {x : B ∩ ￢B} TBoxの右辺で入れ替えた。
S3 = S2 ∪{x : B , x : ￢B} ∩規則を適用した。
clashが発生したので D は充足しないと判定される。

他の推論タスクについて
2. 概念の包含関係 C ?D
– C ∩￢D が充足しないなら C ?Dと言える。
3. 概念の同値関係 C ≡ D
– C ?D かつ C ? D が成立するならC ≡ Dと言える。
D C
C ?D C ≡ D
C
D

他の推論タスクについて(2)
– TBoxで定義されている概念の中身をABoxに登場す
る変数に当てはめて、これをA’とする。
– A’の充足可能性を判定する。
T = {B ≡ S ∪ T , ....}
A = {x : A, y : B , z : C, ...}
A’ = {x : A, y : S ∪ T , z : C, ...}

他の推論タスクについて(3)
5. 個体 o が概念 C に属するかの判定
– A∪{￢C(o)}の充足不可能性で判定可能。
以上から、概念の充足可能性が判定出来れば
他の推論タスクも実行できる。

まとめ
? OWLで書かれたことについて以下が言える。
1. 概念が充足するか。
? そもそもあり得るものなのか
2. 概念の包含関係が成立するか
3. 概念の同値関係が成立するか
5. ある概念がある個体に属するか
? 推論タスク

まとめ(2)
? 推論タスク実行のため、タブロー法が使える。
– 検証したい概念に属する個体が存在する前提を
立てた上で矛盾が発生しないことを確認するやり
かた。

個人的な感想
? 機能が高級?複雑すぎてどんな実応用がある
かちょっと思いつかない。
? ユーザ側にわかりやすくする工夫が必要そう。
– サービス?機能の提供するならば
– 論理式で書かれた概念が入力になる。ここをわ
かりやすく
? OWLで書かれた多彩なデータを扱えそうなの
は魅力。

個人的な感想(2)
? 推論に時間がかかりそう。
– 推論を進める際には全ての処理対象データを扱
わなければならないので。
– 大量データをインメモリで扱えるようなシステムが
必要？
– あるいはクラウド的ななにか。

カバーできなかった話題
? 以下のケースでの推論とその例示
– SROIQ(D)の範囲での推論
? 推移的ロール?ロール階層などなど。。。
– 個数制約があるケース
? ≧規則、≦規則
– TBoxに概念の包含関係がある場合の推論
? 概念の階層関係
? ?規則、 ?+ 規則
? 計算量の話

参考文献
? 記述論理とWebオントロジー言語
– http://www.amazon.co.jp/dp/4274207455
– 今回の内容はほぼ本書から学びました。
? タブロー法入門
– http://ebooks.cambridge.org/ebook.jsf?bid=CBO9
780511711787
– タブロー法について丁寧に解説してある。
– 大枠何をするものなのかが理解できた。
– 演習出来る形なので独習しやすい。
28

ご清聴ありがとうございました

狠狠撸

翱奥尝で何が言えるか

More Related Content

翱奥尝で何が言えるか