平成29年6月3&9日（金） 東京工科大学大学院 バイオニクス・情報メディア学専攻科 担当： 亀田 弘之 先進的データ分析法2017 平成29年6月3&9日（金） 東京工科大学大学院 バイオニクス・情報メディア学専攻科 担当：　亀田　弘之

全体のまとめ なぜ論理学の話をしたのか？ 今までの話がどのようにデータ分析に関わっているのか？ 最近はやりのData Science ( Data Minung, Text Mining, Web Mining  Knowledge Discovery)の側面から話をしましょう！ （DSは今やAIの一分野とも考えられる）

知識の発見 知識=普遍の真理 真理の探究 こんなことが自動的にできると凄いよね！

真実 Web

ＤS Methodology (注) DS = Data Science

ＤS Methodology Exploratory data analysis （探索的データ解析） Computational data mining （計算論的データマイニング） Statistical data mining （統計的データマイニング）

ＤS Methodology Exploratory data analysis （探索的データ解析） Computational data mining （計算論的データマイニング） Statistical data mining （統計的データマイニング）

１．Exploratory data analysis 統計的データ解析(SDA) 探索的データ解析(EDA)

統計的データ解析(SDAの基礎) 視覚的分析 数値的分析 表： 度数分布表(frequency table) 図： ヒストグラム(histogram) 数値的分析 代表値： 平均 (mean) 中央値 (median) モード (mode,最頻値） ばらつき度：分散(variance) 平均偏差(mean deviation; MD) 標準偏差(standard deviation) 範囲(range = 最大値ー最小値) その他 四分位数(quartile,第一・二・三） 外れ値

統計的データ解析(EDAの基礎) 視覚的分析 数値的分析 表： 度数分布表(frequency table) 図： ヒストグラム(histogram) 数値的分析 代表値： 平均 (mean) 中央値 (median) モード (mode,最頻値） ばらつき度：分散(variance) 平均偏差(mean deviation; MD) 標準偏差(standard deviation) 範囲(range = 最大値ー最小値) その他 四分位数(quartile,第一・二・三） 外れ値(outlier)

探索的データ解析(EDA) 幹葉表示(stem-and-leaf display) 要約値(letter value display) 箱ヒゲ図(box-whisker plots) Ｘ－Ｙ表示(X-Y plotting) 抵抗性のある直線回帰(registant line) 中央値分散分析(median polish) 時系列データのならし(smoothing)

探索的データ解析(EDA) 幹葉表示(stem-and-leaf display) ヒストグラムに代わる手法 要約値(letter value display) 平均値・標準偏差に代わるもの 箱ヒゲ図(box-whisker plots) 分布の形と外れ値の図的表示

ＤS Methodology Exploratory data analysis （探索的データ解析） Computational data analysis （計算論的データ分析） Statistical data analysis （統計的データ分析）

３．Statistical data analysis Statistic models（統計モデル） Statistic inference（統計的推論） Non-parametric model General linear model Log-linear model Graphical model etc.

ＤS Methodology Exploratory data analysis （探索的データ解析） Computational data analysis （計算論的データ分析） Statistical data mining （統計的データマイニング）

２．Computational data analysis Cluster analysis（クラスター分析） Tree models（木モデル） Linear regression（線形回帰） Logistic regression（ロジスティック回帰） Neural networks（ニューラルネットワーク） ILP(Inductive Logic Programming; 　　帰納論理プログラミング） SVM(support vector machines) etc.

２．Computational data mining Tree models（木モデル） Cluster analysis（クラスター分析） Linear regression（線形回帰） Logistic regression（ロジスティック回帰） Neural networks（ニューラルネットワーク） ILP(Inductive Logic Programming; 　　帰納論理プログラミング） etc.

a．クラスター分析 Hierarchical methods（階層型法） Non-hierarchical methods（非階層型法）

a．クラスター分析（２） 基本的考え方： 近いデータをかき集めてグループを作る。 近いグループ同士をかき集めて新たなグループを作る。 これの繰り返し。

クラスター分析（例）

クラスター分析（例）

クラスター分析（例）

クラスター分析（例）

クラスター分析（例）

クラスター分析（２） 基本的考え方： 近いデータをかき集めてグループを作る。 近いグループ同士をかき集めて新たなグループを作る。 近い　＝＞　距離(distance)が主要な役割を果たす

距離って何だっけ？

距離(distance) 空間Ｓの任意の２点x,yの間に、１つの実数d(x,y)が定義されていて、これが次の4つの条件を満たしているとき、d(x,y)を２点x,y間の距離という。

２点間の距離 空間Ｓ x ２点間の距離d(x,y) y

２グループ間の距離は？

２グループ間の距離は？ グループA グループＢ

２グループ間の距離 グループA グループＢ 距離d(A,B)

２グループ間の距離 グループA 平均値・中央値 グループＢ 距離d(A,B)

２グループ間の距離 グループA 平均値・中央値 グループＢ 距離d(A,B) 代表値間の距離

いろいろな距離（関数）

いろいろな距離（関数）（２） Euclidean distance（ユークリッド距離） Mahalanobis disntance（マハラノビス距離） Edit distance（エディト距離） etc.

b．木モデル 決定木(decision tree)

決定木の用途 分類問題 診断問題 予測問題 制御問題 パターン認識問題 etc.

その前に、ちょっと復習

木とは？

木とは(1)

木とは（２） 枝(branch)

木とは(3) 根(root) 節(node)

木とは(4) 根(root) 葉(leaf) 節(node)

決定木の例(その１) 履歴状況

決定木の例(その２) あり 白 なし 白黒 赤 大 中 小 サイレン 車体の色 車体の大きさ 大型トラック 普通自動車 消防車 パトカー 救急車 軽自動車 なし 白黒 赤 大 中 小

決定木の作成（学習） 決定木の作成 大量の例 決定木

決定木の作成（学習） 決定木の作成 大量の例 決定木 分類問題の解

決定着の詳細

Decision Tree for PlayTennis Outlook Sunny Rain Overcast Humidity Wind Yes High Normal Strong Weak Yes Yes No Yes

Training Examples Day Outlook 天候 Temperature 温度 Humidity 湿度 Wind 風 Play Tennis D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 D13 D14 Sunny Overcast Rain Hot Mild Cool High Normal Weak Strong No Yes

Top-down Induction of Decision Tree Main loop: A ← the best decision attribute for next node Assign A as decision attribute for node For each value of A, create new descendant of node Sort training examples to leaf nodes If training examples perfectly classified, then HALT, else iterate over new leaf nodes.

Which attribute is the best? [29+, 35-] A1=? A2=? [29+, 35-] F T F T [21+, 5-] [8+, 30-] [18+, 33-] [11+, 2-]

Entropy S is a sample of training examples p+ is the proportion of positive examples in S p- is the proportion of negative examples in S Entropy measures the impurity of S

Entropy（エントロピー）

Interpretation of Entropy Entropy(S)とは…２つのグループ（各生起確率がp+とp-）を符号化するのに必要なビット数（情報量） その理由は… P+ P-

Information Theory（情報理論） 生起確率pのメッセージに対する最適符号長符号(optimal length code)は、　　　　　　で与えられる。 したがって、それぞれ確率p+とp-で生起する２つの組に対する平均符号長は、 　　で与えられる。これはEntropyの公式そのものである。

Entropyの本当の定義 無記憶情報源Sから、シンボルs1, s2, s3, …, snがそれぞれp1, p2, p3, … ,pn の生起確率で出現するとき、この無記憶情報源Sのエントロピーは以下の式で定義される。

Information Gain(情報利得) Gain(S,A)：　「もともと（S)のエントロピー」と「Aに着目する分類後のエントロピー」の差。 これを情報利得と呼ぶ。

Which attribute is the best? [29+, 35-] A1=? A2=? [29+, 35-] F T F T [21+, 5-] [8+, 30-] [18+, 33-] [11+, 2-]

Which is the best? - Selecting the next attribute - [3+, 4-], E=0.985 [3+, 4-], E=0.985 Humidity Wind strong high normal weak [3+, 4-], E=0.985 [3+, 4-], E=0.985 [3+, 4-], E=0.985 [3+, 4-], E=0.985 Gain(S,Humidity)=0.151 Gain(S,Wind)=0.048

Training Examples Day Outlook 天候 Temperature 温度 Humidity 湿度 Wind 風 Play Tennis D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 D13 D14 Sunny Overcast Rain Hot Mild Cool High Normal Weak Strong No Yes

分類前のエントロピー ・Yes 9 [9+, 5-] ・No 5

Outlookに着目する場合 Sunny [2+, 3-] Overcast [4+, 0-] Rain [3+, 2-]

Temperatureに着目する場合 Hot [2+, 2-] Mild [4+, 2-] Cool [3+, 1-]

Humidityに着目する場合 High [3+, 4-] Normal [6+, 1-]

Windに着目する場合 Weak [6+, 2-] Strong [3+, 3-]

情報利得を計算すると…

Decision Tree for PlayTennis Outlook Sunny Rain Overcast Humidity Wind Yes High Normal Strong Weak Yes Yes Yes Yes

決定木まとめ 決定木は分類器 決定木が例から学習出来る 過学習(overfiting)回避の工夫が必要 ＝＞ 枝刈り(pruning) 決定木学習は命題論理の命題学習に相当 ＝＞述語論理への拡張が必要 ＝＞帰納的論理プログラミング (ILP; Inductive Logic Programming)

命題論理から述語論理へ、 Let’s Go and dive!

ILP What? 述語論理上で帰納推論を展開するアプローチであり、分類問題を解決することが出来る枠組み (注) ILP = Inductive Logic Programming

ILP　What? 述語論理上で帰納推論を展開するアプローチであり、分類問題を解決することが出来る枠組み

述語論理 対象間の関係を記述する知識表現 例：太郎は花子を愛している。 　＝＞　愛する（太郎,花子） 　＝＞　love（taro,hanako）

述語論理 対象間の関係を記述する知識表現 記述のための言語が必要 　＝＞　love（taro,hanako） 　＝＞　P（x1,x2）

述語論理記述のための言語 変数 関数 述語 論理結合子 限量子 コンマ等

述語論理記述のための言語 変数： 関数： 述語： 論理結合子： 限量子： コンマ等：　　　　,

項(Term) 変数は項である。 関数F(t1, t2, …, tn) は項である。 ただし、 t1, t2, …, tn は項。 以上のものだけが項である。

基礎項 変数を含まない項のこと。

アトム(atom) P(t1, t2, …, tn )はアトムである。 ただし、 t1, t2, …, tn は項。 t1, t2, …, tnすべてが基礎項のとき、 p(t1, t2, …, tn )を基礎アトム(ground atom)と呼ぶ。

論理式 述語P(t1, t2, …, tn )は論理式。 Fが論理式ならば、￢Fも論理式。 FとGが論理式ならば、(F∧G) と(F∨G)も論理式。 Fが論理式、xが変数のとき、 ∃x F と ∀x F も論理式。 これらにより作られるものだけが論理式。

論理式の例 Problem１: この論理式の構造は どうなっているか？ Problem２: この論理式の意味は どうなっているか？

確認問題 次のうちどれが論理式？

確認問題 次のうちどれが論理式？

扱いたいのはこちら！ 論理式のシンタックスはこちら。

「解釈」の導入（ 形式 → 内容 ） なぜ「解釈」が必要なの？ これって真(true)なの偽(false)なの？ 各記号の解釈が必要！ 解釈(Interpretation) なぜ「解釈」が必要なの？ これって真(true)なの偽(false)なの？ 各記号の解釈が必要！ Pやxが何を意味しているのかわからなければ決まらない。

述語論理式の意味論 構造A=（UA,IA） ただし、UA≠Φ（領域） IA は論理式の各記号の意味割り当てをする写像。 この辺は抽象的なので、具体例で理解しよう。

とある世界を考える。

抽象化しよう！

とある世界

とある世界

とある世界

太郎 花子 愛

言語化 論理式 解釈

言語化 解釈

もう一息整理しよう！

言語化 太郎は花子を愛する 解釈

解釈の構築(意味の割当て) UA={ taro, hanako } IA: x100 ↔ taro x4 ↔ hanako P32 　（＊, ＊＊） ↔ love(＊,＊＊) 　 これに意味を持たせることができた！！ 以上、論理式の導入部分…

述語論理あれこれ Prenex Conjunctive Normal Form (PCNF) Skolem Standatd Form (SSF) Skolem 定数 Skolem関数 φが充足不可能SSF(φ)が充足不可能 Herbrand Model (HM) φがモデルを持つ　 φがHMを持つ　など

その他の重要な概念 Resolution 代入 包摂 束構造 lgg(least general generalization)や rlgg(reletively lgg) 高階論理 Paraconsistent Logic など

ここまでの内容を踏まえて、…

はじめに論理式φありき 論理式φを等価変形し、Prenex Conjunctive Normal Form (PCNF)の形式ψにする。 　　　例

Prenex Conjunctive Normal Form

Prenex Conjunctive Normal Form Clause Prenex Matrix イメージ： 　∀x∃y∃z∀u．．． イメージ： (P(x)∨Q(y, f(z))) ∧P(u)∧(Q(x, u)∨P(z, f(f(y))))

PCNFをSSFに PCNFをさらにSkolem Standard Form (SSF) に変形する。 （注）この変形は真理値を保存しない 　　　ことに注意。

Skolem Standard Form Clause Prenex Matrix

Prenex Conjunctive Normal Form Clause Prenex Matrix イメージ： 　∀x∀u．．． イメージ： (P(x)∨Q(g(x), f(z))) ∧P(u)∧(Q(x, u)∨P(h(x), f(f(g(x)))))

PCNF ＝＞ SSFへの書き換え 限量記号（存在記号）∃を除去しなければならない。そのために、スコーレム定数やスコーレム関数を導入する。 例：

確認：大切な注意事項（その１） 任意の論理式はPCNFに変形可能 任意のPCNFはSSFに変形可能

真理値が保存されない例

確認：大切な注意事項（その２） BUT 充足不可能な論理式は充足不可能なSSFに変形される。

定理 任意の論理式φに対して、そのSSFをψとする。このとき、以下の関係が成り立つ。 Ψ |= φ つまり、 　・φはψの論理的帰結である。 　・ψが真となる解釈はどれも 　　φを真とする解釈にになっている。 　・ψのモデルはφのモデルでもある。

定理 任意の論理式φに対して、そのSSFをψとする。このとき、以下のことが成り立つ。 ・ψが充足不可能ならばφも充足不可能である。 ・ψがモデルを持たなければ 　φもモデルを持たない。

定理 任意の論理式φに対して、そのSSFをψとする。このとき、以下のことが成り立つ。 ・ψが充足不可能ならばφも充足不可能であり、　 　かつ、その逆も成り立つ・。 ・ψがモデルを持たないことと、 　φもモデルを持たないこととは等価である。

Herbrand Models（復習） フランスの論理学者Jacques　Herbrand が考案したとある解釈(interpretation)のこと 。 この解釈を特に、Herbrand interpretation とよび、この解釈に基づくモデルを Herbrand model と呼ぶ。 その実態は．．．

HMの構造をもう一度見てみよう！ Herbrand universe U Herbrand base B Herbrand pre-interpretation J Herbrand interpretation I Herbrand model M 以下、例で説明する。

HMの構造をもう一度見てみよう！ Herbrand universe U ＜＝ 解釈の領域 Herbrand base B　＜＝　アトムの集合 Herbrand pre-interpretation J　 　＜＝　項と領域要素との対応を定義 Herbrand interpretation I 　＜＝　アトムの真理値を定義 Herbrand model M 以下、例で説明する。

例： まず、このような論理式の集合を考える。

Herbrand Universe 元の論理式に含まれていた定数と関数に着目し、これからか得られるすべての項を集めたもの。

Herbrand　Base 元の論理式に含まれていた述語を、先ほどのUの要素に適用して得られる述語すべてからなる集合。

Herbrand pre-interpretation 解釈の領域D：Hebrand Universe U 定数記号の解釈: 自分自身に対応させる。 関数記号の解釈：自分自身に対応させる。

Herbrand pre-interpretation 解釈の領域D：Hebrand Universe U 定数記号の解釈: 自分自身に対応させる。 関数記号の解釈：自分自身に対応させる。 ここがポイント！

Herbrand interpretation Herbrand pre-interpretation に基づくInterpretation をHerbrand Interpretation (HI) と呼ぶ。 なおHIの内、所与の論理式（群）を充足するものを Herbrand Model (HM) と呼ぶ。

例: H Pre-I J: 領域 U ＝ Herbrand Universe 定数記号 a in φ  個体 a ∈ U, 定数記号 b in φ  個体 b ∈ U. 関数記号f in φ  関数f(t) ∈ U. 真理値割り当て： I1 ={P(a), P(b), Q(a, b), Q(b,b) } I2 ={P(a), Q(a, a), Q(a, f(b)) } I3 ={P(f(f(a))), P(b), Q(a, a), Q(a, f(b)) } I4 ={P(a), P(b), Q(a, a), Q(b, b), Q(a, f(b)) }

注意事項 HMの意義 Σがモデルを持つ　　ΣがHMを持つ。 Σ　｜＝　φ　　SはHMを持たない。 ただし、Sは Σ∪{～φ} のSSF。

述語論理における推論 Resolution 代入 論理プログラミング（Prologなど） 帰納論理プログラミング(Progolなど) ＝＞知識分類・知識獲得・知識発見

補足説明 知識記述言語（知識表現）としての論理式 推論のために論理学を導入 推論体系完全性・妥当性・推論アルゴリズムの存在等の理由により、現在は通常“１階の述語論理”が採用されている。 この殻を破ればさらに発展がある筈！

こんな準備しつつ、いよいよILPへ

以下、Webより拝借した資料です 取り扱いに注意してください！

Inverse Entailment and Progol Stephen Muggleton 1995年，Muggletonによって、New Generation Computing で発表された論文です。 帰納論理プログラミングの１つProgolについての論文です。 有川研究室　修士1年 坂東　恭子 一部亀田により改変2010.01.08

発表の流れ ・はじめに ・帰納論理プログラミング（ILP）とは ・Progolの説明 ・まとめ

はじめに 機械学習：決定木 帰納論理プログラミング（ILP） 一階述語論理式を学習しよう 背景知識を使おう 機械学習：帰納推論、PAC学習がある。　命題論理上の学習、複雑な学習ができない 一階論理式を学習しよう。より複雑な学習のために背景知識を使おう。 帰納論理プログラミング　Inductive Logic Programming この名前もMuggletonによってつけられた 帰納論理プログラミング（ILP）

帰納論理プログラミングとは？ 背景知識、正例、負例 負例を説明せず、正例を説明する仮説をみつける 帰納論理 プログラミング 機械学習 logic programming 機械学習 　machine learning 帰納論理プログラミングの位置付け 機械学習を一階論理式に拡張したということで、 論理プログラミングと機械学習のintersection 背景知識について説明 背景知識、正例、負例 負例を説明せず、正例を説明する仮説をみつける

ILP システムの例 ・GOLEM ：1992年Muggletonらにより開発 ・Progol :1995年Muggletonらにより開発 　　　　　　　　　rlgg (Relative Least General Generalization) ・Progol　:1995年Muggletonらにより開発 　　　　　　　逆伴意（inverse entailment）に基づく ・FOIL　:1990年Quinlanにより開発 ・GKS　：1995年溝口により開発　など RLGG＝相対最小汎化 Muggleton　：York大学 Quinlan:　　シドニー大学

Progol とは？ ・1995年Muggletonにより開発されたILP システム ・C (Prolog)で記述されている。 ・逆伴意（inverse entailment）の考えを採用 Prolog　論理プログラミングでよく使われる まず、伴意の説明

伴意(entailment)とは？ A ⊨ B ・伴意 ＝ 論理的帰結 ・記号 ⊨ を使う ・BはAの伴意である ・BはAの論理的帰結である ＝　 論理的帰結 ・記号 ⊨ を使う A　⊨　B ・BはAの伴意である ・BはAの論理的帰結である 論理的帰結とは Aのすべてのモデルが、Bのモデルである Aを真とするような解釈はすべて、Bも真とする。 ・背景知識＋仮説　⇒　例 記号を使って表すと B(背景知識)　∧　H（仮説）　⊨　E（例）

逆伴意(inverse entailment)とは？ 伴意：B(背景知識)　∧　H（仮説）　⊨　E（例） 演繹定理より 　H（仮説）　⊨　 B(背景知識) → E（例） 逆伴意： 伴意を逆向きに読む　　　　　　 　　　　　　背景知識と例から仮説を得る

例 ソクラテスは人である。 ⊨ 人は死ぬ。→ソクラテスは死ぬ。 B(背景知識) ∧ H（仮説） ⊨ E（例） ソクラテスは人である。∧人は死ぬ。 ⊨ ソクラテスは死ぬ。 ソクラテスは人である。 ⊨ 人は死ぬ。→ソクラテスは死ぬ。

Progolの仮説生成プロセス 逆伴意に基づき最も特殊な節（最弱仮説）を構成 最弱仮説を包摂する空間（最弱仮説空間） において、最良優先探索 最良な仮説の発見

仮説と最弱仮説の関係 正例 仮説 仮説 正例 最弱仮説 最弱仮説 仮説 一般的 特殊化 特殊化 特殊化 正例 特殊 探索空間が 縮小される！ 正例 仮説 特殊化 仮説 最弱仮説 特殊化 ここが最弱化節とすると．．． 仮説を特殊化することによって正例は求められる 正例から仮説を求めるには考慮すべき空間が大きい 最弱仮説を求めると考慮する空間が縮小される 最弱仮説 正例 特殊化 特殊 正例

最弱仮説の生成    なぜ？ Hから伴意されることを示す。 ・B  ￢ Eから最弱仮説を演繹的に計算可能 対偶をとって ￢（B → E）　⊨　￢ H  すべてのモデルで真な基底 リテラルの連言（）：bot(B,E) B  ￢ E　⊨　￢ H なぜ？ B  ￢ Eから演繹に計算される節が，Hの最弱仮説となることをしめす Hから伴意されることを示す。 もし、Hがbot(B、E)の部分連言じゃなかったら もし、bot(B,E)以外の基底リテラルを含めば，その余分なリテラルを 含まないモデルが存在 　　　　 　　B  Eのすべてのモデルで真とはならない B  ￢ E　⊨　￢　bot(B,E)  ￢ Hは￢　bot(B,E) 　の部分連言（）

証明：￢ Hは￢bot(B,E)の部分連言（） ￢　bot(B,E) = l1 ・・・  ln ￢　H = l1 ・・・  ln  lk  lk+1 B  ￢ E　にはlk , lk+1を 含まないモデルが存在 矛盾 B  ￢ E　 ⊭　￢ H

H ⊨ bot(B,E) B  ￢ Eから最弱仮説を演繹的に計算可能 B  ￢ E ⊨　￢　bot(B,E) 　⊨　￢ H 対偶をとって H 　⊨　 bot(B,E) 　 最弱仮説MSH 連言だと部分連言は伴意される Bと￢ E から伴意されるなかで一番特殊 最弱仮説は仮説から伴意されるから B  ￢ Eから最弱仮説を演繹的に計算可能

正例：　　　　　　　　　　負例： gf（波平，タラオ）　　　　　　gf（波平 ，カツオ） gf（洋平，カツオ） 　　　　　gf（舟，タラオ）　 gf（洋平，サザエ）　　 　　　gf（洋平，タラオ） gf（洋平，ワカメ） 背景知識：f（波平，サザエ）， m（舟，ワカメ）， f（波平， カツオ），f（波平，ワカメ）， 　　　　　 m（サザエ，タラオ），f（洋平，波平） 　　　　　　 p（A，B）:- f（A，B），p（A，B）:- m（A，B）

母 洋平 海平 妹 波平 舟 ワカメ カツオ サザエ マスオ タラオ

 f（波平，サザエ） m（舟，サザエ） f（波平，カツオ）  f（波平，ワカメ） m（サザエ，タラオ）  f（洋平，波平） 正例E+： gf（波平，タラオ）について B　　 　￢E　　⊨　　 ￢MSH ￢MSHはB  ￢Eのすべてのモデルで真 B　　 　￢E = ￢ gf（波平，タラオ） 　　  f（波平，サザエ） m（舟，サザエ） f（波平，カツオ） 　　  f（波平，ワカメ） m（サザエ，タラオ）  f（洋平，波平） 　　  p（A，B）:- f（A，B）  p（A，B）:- m（A，B） ￢MSH は基底リテラルの連言 = ￢ gf（波平，タラオ） 　 f（波平，サザエ） m（舟，サザエ） f（波平，カツオ）  f（波平，ワカメ） m（サザエ，タラオ）  f（洋平，波平） 　 p（波平，サザエ） p（舟，サザエ） p（波平，カツオ） 　 p（波平，ワカメ） p（サザエ，タラオ）  p（洋平，波） ￢MSHは連言なので，B　　 　￢Eの部分集合 部分集合だったらいいので， B　　 　￢Eごとを最弱仮説とする

 f（波平，サザエ） m（舟，サザエ） f（波平，カツオ）  f（波平，ワカメ） m（サザエ，タラオ）  f（洋平，波平） MSH ＝￢ (￢ gf（波平，タラオ） 　 f（波平，サザエ） m（舟，サザエ） f（波平，カツオ）  f（波平，ワカメ） m（サザエ，タラオ）  f（洋平，波平） 　 p（波平，サザエ） p（舟，サザエ） p（波平，カツオ） 　 p（波平，ワカメ） p（サザエ，タラオ）  p（洋平，波平）) と同じ意味 ＝gf（波平，タラオ）:- f（波平，サザエ）, m（舟，サザエ）, 　　　　　　　　　　　　 f（波平，カツオ）, f（波平，ワカメ）, 　　　　　　 m（サザエ，タラオ）,f（洋平，波平）, 　　　　　　　　　　　　　 p（波平，サザエ）, p（舟，サザエ）, 　　　　　　　　　　　　 p（波平，カツオ）, p（波平，ワカメ）, 　　　　　　 p（サザエ，タラオ）,p（洋平，波平）

最弱仮説から仮説を求める 最弱仮説を伴意する 最良な仮説を求める 伴意を包摂で近似し、 仮説空間を探索しよう H（仮説）　⊨　 MSH（最弱仮説） 一般的 最弱仮説を伴意する 最良な仮説を求める 伴意を機械的 に行うのは困難 最弱仮説と仮説にも節の関係が適応され 仮説を特殊化したものが最弱仮説 最弱仮説は仮説によって伴意されるから 最弱仮説を伴意するような仮説を求めればいい でも、伴意を機械的にやることは困難 伴意を包摂で近似し、 仮説空間を探索しよう 特殊 最弱仮説

Progolの仮説生成プロセス 逆伴意に基づき最も特殊な節（最弱仮説）を構成 最弱仮説を包摂する空間（最弱仮説空間） において、最良優先探索 最弱仮説を包摂するような節はたくさんあるので探索が必要 最良な仮説をみつける

A*-like 探索 ・Progolにおける探索方法 ＜＝改善の余地あり！ ・最弱仮説空間（最弱仮説を包摂する空間）を 探索し、最良仮説を得る ・A*探索が元になっている

A* 探索 ・グラフにおける最良優先探索 ・評価関数 f(n) を最小にするパスをみつける。 f(n)＝g(n)＋h(n) : n経由の最短解の見積りコスト g(n):出発接点から接点nまでの経路のコスト h(n):ヒューリスティック関数 nからゴールまでの見積りコスト 最良優先探索とは，最良に見える接点を選択する

S 14 B I 10 10 8 18 A H 5 E 9 10 C 14 G 7 6 7 D F

ヒューリスティック関数（ゴールとの直線距離） S : 42 A : 35 B : 28 C : 30 D : 23 E : 19 F : 16 H : 10 I : 18 G : 0 S f=36 A B f=10+35=45 f=14+28=42 S E I f=24+36=60 f=22+19=41 f=24+18=42

よって、最良経路は、S  B  E  H  G E f=22+19=41 B F H f=31+10=41 f=38+16=54

S 14 B I 10 10 8 21 A H 18 E 9 10 C 14 G 7 13 12 D F

A*-like 探索グラフの生成 ・探索空間・・・最弱仮説（MSH）を包摂する空間 ・（empty set）からはじまるグラフを作り、そのグラフ 　について最良優先探索を行う。 A*探索はグラフにおける最良優先探索なので、まずグラフを作る

MSH(最弱仮説) ＝gf（波平，タラオ）:- f（波平，サザエ）, m（舟，サザエ）, f（波平，カツオ）, f（波平，ワカメ）, 　　　　　　　　　　　　　 p（波平，サザエ）, p（舟，サザエ）, 　　　　　　　　　　　　 p（波平，カツオ）, p（波平，ワカメ）, 　　　　　　 p（サザエ，タラオ）,p（洋平，波平）

 gf（A，B） 最も特殊な節 gf(A,B):-f(A,C),m(D,C),f(A,E),m(C,B),f(F,A), -m(C,D) -m(C,B) -f(C,A) -p(A,C) -p(C,D) -p(C,B) gf（A,B）： -f(A,C), m(D,C) m(C,B) f(D,A) p(A,C) p(D,C) p(C,B) p(D,A) ・・・・・・ まず、empty　set 次に、headだけからなる節 その後は，リテラルを1つづつ追加していく 追加するリテラルは、最弱仮説を包摂するもの そうすると最後には、最弱仮説の基礎アトムを変数に変えてあげたのになる 最も特殊な節 gf(A,B):-f(A,C),m(D,C),f(A,E),m(C,B),f(F,A), p(A,C),p(D,C),p(A,E),p(C,B),p(F,A)

グラフ内A*-like探索 －(｛仮説のリテラル長｝＋ ｛説明される負事例の数｝) ・評価関数として記述長最小原理を使う。 ・compression gainが最も大きいものが最良 compression gain＝ 　 －(｛仮説のリテラル長｝＋ ｛説明される負事例の数｝) {説明される正事例の数} ｛仮説のリテラル長｝＝ ｛その時点の仮説のリテラル長｝＋｛追加されるリテラル長｝ A g(n) ＝ ｛仮説のリテラル長｝＋｛説明される負事例｝

・｛追加されるリテラルの最小値｝を ヒューリスティック関数で与える ・｛追加されるリテラルの最小値｝を ヒューリスティック関数で与える ・　f(n)＝説明される正事例の数－｛ g(n) ＋ h(n)｝　 　が最大になる仮説を見つける ・全解探索（仮説空間すべて考慮） h(n)＝ head部の出力変数がすべて、body部の入力変数 　　　　として存在しない時に追加するリテラルの最小値 gf（A,B）： -f(A,C) Bについてのリテラルを追加 p(A,B,C): -q(A,D) B, Cについてのリテラルを追加

 gf（A，B） 最良な仮説 4 － (10+0)= ｰ6 ｰ3 ｰ1 ｰ3 ｰ1 ｰ3 2 ｰ3 例 4 － (0+3+2)= －1 4 － (1+2+1) = 0 gf（A,B）： -f(A,C) -m(C,D) -m(C,B) -f(C,A) -p(A,C) -p(C,D) -p(C,B) ｰ2 0 －2 －1 　　－2 　　 0 gf（A,B）： -f(A,C), m(D,C) m(C,B) f(D,A) p(A,C) p(D,C) p(C,B) p(D,A) ｰ3 ｰ1 ｰ3 ｰ1 ｰ3 2 ｰ3 ・・・・・・ ・・・・・・ ・・・・・・ ・・・・・・ 最良な仮説 gf(A,B):-f(A,C),m(D,C),f(A,E), 　　　　　m(C,B),f(F,A), p(A,C), 　　　　　p(D,C),p(A,E),p(C,B),p(F,A) 4 － (10+0)= ｰ6

実世界での応用 ・突然変異性物質の判別問題（King） ・データベースからの知識発見（嶋津，古川） 電子メール分類システム ・暗黙知の獲得（古川） 　　　理想的な弓の動かし方 事例：突然変異を有する化合物 背景知識：化合物の原子と結合情報  　仮説：化合物の突然変異性に関するルール

まとめ ・Progolにおける仮説生成 ・Progolの利点 逆伴意に基づき，背景知識と正例から最弱仮説 を生成 最弱仮説を包摂する木においてA*-like探索 ・Progolの利点 探索空間が縮小される

背景知識 ・既に持っている知識 ・背景知識があるとより正確な理論が 　得られる ・背景知識として、事実とルールが利用 　可能

背景知識なし 背景知識あり 正例：D1 = CuddlyPet(x)  Small(x) , Fluffy(x) , Dog(x) D2 = CuddlyPet(x)  Fluffy(x) , Cat(x) Cuddly：やわらかい Fluffy：ふわふわした C = CuddlyPet(x)  Fluffy(x) 背景知識あり 背景知識： Pet(x)  Cat(x) , Pet(x)  Dog(x) Small(x) Cat(x) D = CuddlyPet(x)  Small(x) , Fluffy(x) , Pet(x)

特殊な節とは？ ・節には半順序関係がある p(A,B) p(A,A). ＞ p(A,B) p(A,B):-q(A,B) ＞ 一般的 一般的：多くの例を説明する 特殊：少ない例しか説明しない p(A,B) 　 p(A,A). ＞ 一般的　　　 　　特殊 p(A,B) 　 p(A,B):-q(A,B) ＞ p(A,B) 　 p(桂子,B) ＞ 特殊

記述長最小原理 記述長最小原理 ・学習の記述量・・・機械学習にとって重要な問題 ・記述量の多い仮説が多くの例を説明できるのは 当然 　当然 できるだけ少ない記述量で多くの例を説明はできないか？ 記述長最小原理

包摂（subsumption）とは？ 定義： H1,H2:節 H1θ ⊆ H2 となるような代入θが存在 H1はH2をθ-subsume（θ-包摂）する。 例: parent（花子, 太郎）:- mother(花子, 太郎)を考える 包摂する節　　parent(花子, 太郎) 　　　　　　　　 parent (A, 太郎)： - mother(花子, 太郎) parent (A, B) :- mother (A, B) 包摂しない節 parent(花子，次郎) 　　　　　　　　　　 parent (A, B) :- mother (B, A)　 包摂　＝　部分集合　＋　逆代入

伴意と包摂の関係 　A subsume(包摂する) B  A ⊨ B これがなり立つ！ 積極的に利用しよう 伴意を包摂で近似する

部分連言だと伴意される A=l1･･･ln B=l1･･･lnln+1 Bの解釈はAの解釈でもある B ⊨ A 　：BはAを伴意する

正例：　　　　　　　　　　負例： gf（波平，タラオ）　　　　　　gf（波平 ，カツオ） gf（洋平，カツオ） 　　　　　gf（舟，タラオ）　 gf（洋平，サザエ）　　 　　　gf（洋平，タラオ） gf（洋平，ワカメ） 背景知識：f（波平，サザエ）， m（舟，ワカメ）， f（波平， カツオ），f（波平，ワカメ）， 　　　　　 m（サザエ，タラオ），f（洋平，波平） 　　　　　　 p（A，B）:- f（A，B），p（A，B）:- m（A，B）

引用はここまで。

ILPは機械学習の主要な手法 人工知能の分野にもインパクトを与えている。 データ分析の手法ともみなせる！ ILPも年々進化している。 Logicも進化している！ 感性科学や脳科学もAIに関わって来ている。 新しいAI・データ分析の手法を 　　　　自分の力で考え出そう！

レポート課題