H - 京都大学

知能情報システム特論
精密化による学習
山本章博
京都大学情報学研究科知能情報学専攻
http://www.iip.ist.i.kyoto-u.ac.jp/member/akihiro/
[email protected]
精密化による学習

仮説空間とその探索を構造化するために，
仮説間に半順序を定義


仮説の一般性，尤度，嗜好性などを半順序で表現
精密化：論理式への推論規則の適用によって
半順序を定義

データマイニング・アルゴリズムに利用されている
極限同定モデルでの例の提示
E1, E2, E3, ...



Mに関する例の提示
：正例と負例の無限列
完全提示（完全データ） :
Mに関する全ての正例と
全ての負例が少なくとも1
回出現する無限列
正提示（正データ）: Mに関
する正例からなる提示で，
全ての正例が少なくとも1
回出現する無限列
H1, H2, H3, ...
HB
M(Hi)
M
正例
負例
枚挙と生成テストによる極限同定
仮説空間 H 内の論理プログラムの枚挙を固定
P1, P2,…, Pn,…
for n = 1 forever
En = An , bn を受取る
k = 1, H = P1
while ( 0  j  n
(Ej = Aj , +  かつ H |= Aj )または
(Ej = Aj , -  かつ H |= Aj ))
H = Pk ; k ++
output Hn = H

極限同定(identification in the limit)[Gold]
E1, E2, E3, ...


H1, H2, H3, ...
学習アルゴリズムが概念Cを極限において(EX)同
定する
 Cの任意の完全提示に対して, あるNが存在し,
n > Nなる全てのnに対して Hn= P かつ M(P) = M
学習アルゴリズムが概念Cを極限において(BC)同
定する
 Cの任意の完全提示に対して,あるNが存在し，
n > Nなる全てのnに対して M(Hn) = M .
極限同定(続き)

学習アルゴリズム IIM が概念クラス C を極
限においてEX(BC)同定する
 C 中の各概念を極限においてEX(BC)同
定する
精密化の実例

トランザクション・データからのデータマイニング


バスケット分析ともいう
具体的には：
Apri-ori アルゴリズム[Agrawal and Srikant 93]
トランザクション・データにおいて，頻出する購買
パターンを全て求める
データマイニング

マイニング：鉱山の採掘
データマイニング

データマイニング：大量のデータの中に非明
示的に内在している有用な
知識を探し当てる（発見する）
購買パターンの発見
目標(解きたい問題):
 利用者(消費者)の購買履歴(transaction)から
利用者の購買パターンを発見する
頻繁に出現するパターン
例あるインターネット書店
見つけたい購買傾向の例:
「蹴りたい背中」と「インストール」は同時に購入さ
れる可能性が高い
頻出パターン発見の定式化(1)

プログラムに与えられるデータ(入力)
1. トランザクション・データ D
：購買履歴(トランザクション)の記録
2. 支持度(support)  s 

高校数学用語を用いると
トランザクションは
「蹴りたい背中」を買う，「インストール」を買う,…
などを根元事象とする事象
トランザクション・データ
購入した本の種類
ID
蹴りた
い
インスト
ール
蛇に
リトルバ
イ
限りなく
…
…
…
…
…
…
…
3256
3257
1
1
0
1
…
1
0
1
0
0
1
0
1
…
…
…
1
0
…
0
1
…
0
0
…
1
0
…
3258
3259
…
トランザクション(一回分)
…
…
…
関係データベース
属性
animal
bear
bear
dog
dog
cat
horse
horse
horse
color
black
black
black
brown
black
black
black
brown
タプル
size
small
medium
large
large
small
medium
large
large
class
dangerous
dangerous
dangerous
dangerous
safe
safe
dangerous
dangerous
頻出パターン発見の定式化(2)

求めたい購買傾向(出力)
相対頻度が支持度 s を越える全てのパターン
パターン: 属性の集合 {A1, A2, …, An}

数学用語では事象
相対頻度 P({ A1, A2, …, An })
D中のトランザクションで同時に1であるものの個数
D中のトランザクションの総数
簡単な例
ID
1
2
3
4
A
1
1
1
0
B
0
1
0
1
C
1
1
0
0
D
0
0
1
0
E
0
0
1
1
F
0
0
0
1
P({A})=0.75, P({B})=P({C})= P({E})= 0.5
P({D})=P({F})= 0.25
P({A , B} )=0.25, P({A , C} )=0.5,…
相対頻度の性質

一般に属性の集合(連言) S , T に対して
S T P(S) P(T) : Pの単調性
P({A})=0.75  P({A , B} )=0.25
P({B})=0.5 P({A , B} )=0.25
P({A})= 0.75  P({A , C} )=0.5
…
Aprioriアルゴリズム[Agrawal et al. 93]
Pの単調性を用いた頻出パターン発見
1. k =1とする
2. C1 = {{A} | AはDの属性}とする
3. Lk = {S  Ck | P(S) s }とする
4. Lk = ならば終了,そうでなければ
Ck+1 = {ST | S Lk ,T Lk , |ST| = k+1, }
かつ U  Ci - Li (i k)である
ようなU をSTは含まない
とし, k =1の値を 1増やして2へ戻る

Aprioriアルゴリズム(2)
Ck+1 ={S1, S2, …, Sn}のパターン(事象) Siに対して
P(Si) sであるかどうかの判定方法
1. 各Siに対して, 変数niを用意して,
最初はni = 0 にしておく.
2. トランザクション・データベース D 中の
各トランザクション t について順に
Ck+1 の中の各パターンSiに対して順に
t が具体例であればni の値を１増やす.
実行例
ID
A
B
C
D
E
F
1
1
0
1
1
0
0
2
0
1
1
0
1
0
3
1
1
1
1
0
1
0
1
0
0
1
1
4
s = 0.5
C1 = {{A}, {B}, …, {F}}
L1 = {{A},{B},{C},{E}}
C2 = {{A, B}, {A, C},
{A, E}, {B, C},
{B, E}, {C, E}}
L2 = {{A, B},{A, C},
{B,C}, {B, C},
{B, E}, {C, E}}
C3 = {{A,B,C}, {A,B,E}
{B,C,E}}
L3 = {{A,B,E},{B,C,E}}
実行例
ID
A
B
C
D
E
F
1
1
0
1
1
0
0
2
0
1
1
0
1
0
3
1
0
1
1
0
1
0
1
0
0
1
1
4
s = 0.5
C1 = {{A}, {B}, …, {F}}
L1 = {{A},{B},{C},{E}}
C2 = {{A, B}, {A, C},
{A, E}, {B, C},
{B, E}, {C, E}}
L2 = {{A, C}, {B,C},
{B, E}, {C, E}}
C3 = {{A,B,C}, {A,B,E}
{B,C,E}}
L3 = {B,C,E}
実行例
ID
A
B
C
D
E
F
1
1
1
0
1
0
0
2
0
1
1
0
1
0
3
1
0
1
1
0
1
0
1
0
0
1
1
4
s = 0.5
C1 = {{A}, {B}, …, {F}}
L1 = {{A},{B},{C},{E}}
C2 = {{A, B}, {A, C},
{A, E}, {B, C},
{B, E}, {C, E}}
L2 = {{A, C}, {B, E}}
C3 = 
L3 = 
グラフ表示と探索
{A,B,C,D,E,F}
{A,B,C,D,E} {A,C,D,E,F} {A,B,C,E,F} … {A,B,D,E,F}
{A,B,C,D} {A,B,C,E} {A,B,C,F} …
{C,D,E,F}
{A,B,C} {A,B,D} {A,B,E} … {B,C,E} … {C,E,F} {D,E,F}
{A,B} {A,C} {A,D} … {B,C} {B,D} {B,E} … {E,F}
{A}
{B}
{C}
{D}

{E}
{F}
概念を対象とした帰納推論

(対象) 概念空間 C(H)



全体集合 U の部分集合のクラス
帰納推論したい概念を含む
(表現) 仮説空間 H


概念の表現全体の集合
個々の概念はある法則で表現されている
U
H
h1
h2
h
トランザクションと論理式

トランザクション t を基礎原子論理式A(t)で表現
ID
A
B
C
D
E
F
1
1
1
0
1
0
0
2
0
1
1
0
1
0
3
1
0
1
1
0
1
0
1
0
0
1
1
4
t(1, 1, 0, 1, 0, 0)
t(0, 1, 1, 0, 1, 0)
t(1, 1, 1, 0, 1, 0)
t(0, 1, 0, 0, 1, 1)
属性集合と論理式

属性集合(パターン) p を原子論理式 A(p) で
表現する
属性集合と論理式
{A,B,C,D,E,F}
{A,B,C,D,E} {A,C,D,E,F} {A,B,C,E,F} … {A,B,D,E,F}
{A,B,C,D} {A,B,C,E} {A,B,C,F} …
{C,D,E,F}
{A,B,C} {A,B,D} {A,B,E} … {B,C,E} … {C,E,F} {D,E,F}
{A,B} {A,C} {A,D} … {B,C} {B,D} {B,E} … {E,F}
{A}
{B}
{C}
{D}

{E}
{F}
{A,B,C,D,E,F}
{A,B,C,D,E} {A,C,D,E,F} {A,B,C,E,F} … {A,B,D,E,F}
{A,B,C,D} {A,B,C,E} {A,B,C,F} …
{C,D,E,F}
{A,B,C} {A,B,D} {A,B,E} … {B,C,E} … {C,E,F} {D,E,F}
{A,B} {A,C} {A,D} … {B,C} {B,D} {B,E} … {E,F}
{A}
{B}
{C}
{D}
{E}
{F}

属性集合と論理式
属性集合と論理式
属性集合を原子論理式で表現
t(x,y,z,u,v,w)
t(x,y,z,u,v,1)
t(x,1,z,u,v,w) t(1,y,z,u,v,w)
t(x,y,z,u,1,1)
t(x,y,z,1,1,1)
t(1,y,1,u,v,w) t(1,1,z,u,v,w)
t(1,1,z,1,v,w)
t(1,1,1,1,1,1)
t(1,1,1,u,v,w)
属性集合とトランザクション


トランザクション t が属性集合（パターン）pに
マッチしている
⇔
t を表す基礎原子論理式 A(t) は,
pを表す原子論理式 A(p) だけからなる節
"x1"x2 ..."xn A(p)
の論理的帰結
パターンを表す節Cを仮説，トランザクション
の集合を表すM(C)を概念とする
包摂関係


属性集合（パターン）を表す原子論理式のグラ
フ(束)において，
属性集合pがqを含む
⇔
原子論理式を節と見做したとき，
A(p) から A(q) が包摂規則で導出される
包含関係は半順序関係
節に対する推論規則(1)

Resolution(融合, 導出)
A, A2,…  B1, B2,...
C1, C2,...  D, D2,...
(A2,..., C1, C2,…  B1, B2,..., D2,...)q
q : 単一化代入 (unifier)


下の節をresolvent(導出節, 融合節)とよぶ
因子化(factoring)
A1, A2,..., Ai, Ai +1,… B1, B2,...
(A, Ai +1,…  B1,B2,...)d
d : 単一化代入 (unifier)
節に対する推論規則(2)
…Li…Lk … (Li, Lkはリテラル)
…Lk…Li …
…Li…Lk …
…Li…
…
(Li, Lkはリテラル, Li = Lk)
Subsumption(包摂)
…Li… …
…Li…
…
…Li qLi q2…Li q2… …Li…Lk …
(Li, Lkはリテラル, qは代入)

精密化(1)


節形式文の推論規則による節の導出を，機械
学習(帰納推論)では精密化とよぶ．
一般に，仮説空間内の仮説 h に対して次の3
条件を満たす仮説の集合 r(h) が定める写像r
を精密化という.
1. r(h) は枚挙可能
2. 各 g r(h) に対して C(g)  C(h)
3.仮説の列 h1, h2, …, hn で hi+1=r(hi) かつ
h1= hn であるものは存在しない
精密化(2)
H
T
U
h1 h2
…
… hi …
h
精密化に要求される性質



局所有限性
r(h) は有限集合で有限時間で枚挙が終わる
意味的完全性
C(g)  C(h) なる各概念C(g)に対して，
仮説の列 h1, h2, …, hn で hi+1=r(hi) かつ
h1= h, C(hn)= C(g)であるものが存在する
有限個の極大仮説の存在
仮説の有限集合Tが存在し，任意の仮説hに対
して h1, h2, …, hn で h1  h, hn= hであるものが
存在する
精密化と正データ学習
定理[Ouchi et al. 08] 精密化rが，局所有限性，
意味的完全性を満たし，rに関して有限個の
極大仮説が存在すると仮定する．さらに
仮説の無限列 h1, h2, …, で hi+1=r(hi) かつ
C(hi)= C(hi+1)であるものは存在しないとき，
概念空間Cは正データから極限同定可能で
ある．
正データ（正提示)からの極限同定
E1, E2, E3, ...


H1, H2, H3, ...
M=M(P)に関する正提示（正データ） : Mに関
する全ての正例が少なくとも1回出現する無
限列
学習アルゴリズム IIM が概念 M を正提示
（正データ）から極限において(EX)同定する
 M(P)の任意の正提示に対して
N "n > N Hn = P かつ M(P) = M .

Download Report