人工知能特論2011 平成２４年１月１３日（金） 東京工科大学大学院 亀田　弘之

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

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

真実 Web

Advanced Data Mining 高度データマイニング “高度データマイニング2005”より Advanced Data Mining 高度データマイニング 東京工科大学大学院 バイオニクス・情報メディア学専攻科 Version 2

ＤＭ Methodology

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

ＤＭ 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,第一・二・三） 外れ値

探索的データ解析(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) 分布の形と外れ値の図的表示

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

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

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

２．Computational data mining 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.

その前に、ちょっと復習

木とは？

これらをひっくり返すると…

これらを抽象化すると…

木とは

木とは（２） 枝(branch)

木とは 根(root) 節(node)

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

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

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

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

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

東京工科大学大学院 バイオニクス・情報メディア学専攻科 人工知能特論2009 東京工科大学大学院 バイオニクス・情報メディア学専攻科

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)

高度データマイニング ーILP概説ー 東京工科大学大学院 亀田弘之 Version 2

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

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 など

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

こんな準備しつつ、いよいよ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（例） 逆伴意： 伴意を逆向きに読む　　　　　　 　　　　　　背景知識と例から仮説を得る

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

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

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

レポート課題 課題： 論文“Inverse entailment and Progol (Muggleton)”のAppendixes A.Definitions from logic (A1～A3)を和訳せよ。 提出方法 提出期限：平成２４年２月８日（水）１７：００ 提出先：研A６階レポート提出ボックス 書式：A4レポート用紙（表紙を付けること）