正データからの極限同定における極小言語戦略への精密化の適用

京都大学 大内、山本
正データからの極限同定における極小言語戦略への精密化の適用
IPSJ 2008
refine.md

いわゆる正データからの極限同定を行う.

木パターン言語

これを用いて作られる一階述語論理の項を木パターンという. 代入とかが定義される.

精密化

精密化オペレータ ρ\rho とは 概念空間 (言語クラス) 𝒞\mathcal{C}、仮説空間 (パターンクラス) \mathcal{H} の上で定義される. ρ:2\rho : \mathcal{H} \rightarrow 2^\mathcal{H}

次の3つが成立すること.

  1. h\forall h \in \mathcal{H}ρ(h)\rho(h) が枚挙可能
  2. gρ(h)C(g)C(h)g \in \rho(h) \Rightarrow C(g) \subseteq C(h)
  3. ρ\rho でループしないこと: 仮説の列 h1..hn1,hnh_1 .. h_{n-1},h_n であって hi+1ρ(hi),h1=hnh_{i+1} \in \rho(h_i), h_1 = h_n となるようなものが存在しない

ρ\rho で DAG ができる

ρ0(h)={h},ρ1(h)=ρ(h)\rho^0(h) = \{h\}, \rho^1(h) = \rho(h),
ρk+1(h)={g:hρk(h),gρ(h)}\rho^{k+1}(h) = \{ g : h' \in \rho^k(h), g \in \rho(h') \} と再帰的に ρk\rho^k を定義する.
ρ*=kρk\rho^* = \bigcup_k \rho^k と定義する.

局所的有限性

次が成り立つとき、ρ\rho はこの性質を持つという.

h.ρ(h)\forall h .~ \rho(h) が有限集合.

意味的完全性

次が成り立つとき、ρ\rho はこの性質を持つという.

任意の hhCC(h)C' \subseteq C(h) について h0=h,hi+1ρ(hi),hn=Ch_0 = h, h_{i+1} \in \rho(h_i), h_n = C' という 列 h1..hnh_1 .. h_n が存在すること.

極小言語戦略への精密化の適用

定理 3.1

推論マシン MM が保守的であるとは n.C(M(σ[n]))content(σ[n+1])M(σ[n])=M(σ[n+1])\forall n .~ C(M(\sigma[n])) \supseteq content(\sigma[n+1]) \Rightarrow M(\sigma[n]) = M(\sigma[n+1]) とあること. 更新の必要がなければ、推論結果を変えないことである.

次の4つが成立するとき、概念空間 𝒞\mathcal{C} は保守的に同定可能である.

  1. ρ\rho が局所的有限
  2. ρ\rho が意味的完全
  3. ある有限集合 TT \subseteq \mathcal{H} があって: Tρ*(h)=\bigcup_T \rho^*(h) = \mathcal{H}
  4. 次を満たすような無限列 h1,h2,..,hn,..h_1, h_2, .., h_n, .. は存在しないこと

証明は略.

学習手続き

いわゆる、有限の弾力性 (finite elasticity) があって、MINLが計算可能ならば可能な、 無矛盾かつ保守的な推論機械である.

  1. Input
  2. S{}S \leftarrow \{\}
  3. For i=1,2,...i = 1,2, ...

MINL(T,S,n)MINL(T,S,n)

探索の深さに制限を与えたMINLである.

  1. Input
  2. H0=TH_0 = T
  3. For j=0,1,..,nj = 0, 1, .. , n
  4. return NoneNone