Inferring Unions of the Pattern Languages by the Most Fitting Covers

Ng, Shinohara
Inferring Unions of the Pattern Languages by the Most Fitting Covers
Lecture Notes in CS, vol. 3734, 2005, pp. 269-282
ng2005.md

notation

準備

帰納的推論

おおよそ ./tohoku.md にちゃんと書いた内容だから見出しだけ

  1. 言語 LL のテキストとは
  2. 帰納的推論機械 (IIM)
  3. 帰納的言語とは
  4. 有限証拠 (finite tell-tale) とは
  5. 言語クラスについて有限の厚さとは
  6. 特徴例集合 (characteristic set for a language within a class of languages) とは

Fittest Cover Problem

k,l+k, l \in \mathbb{N}^+ 言語クラス CC に対して SLCLS \subseteq \bigcup_{L \in C} L を言語クラスの有限証拠とする

Fittest Cover Problem (FCP(C,S,k,)FCP(C, S, k, \ell))

S={cabcc,cbcac}S = \{ cabcc, cbcac \} について

MINLの解は *a**a* または *bc**bc*.
FCP の解は *bc**bc*.

FCPは言語推論たりえるか

簡単のために k=1k=1 の場合を考える. 推論のとき、テキスト (事例の列) のその頭nn個の断片 T[n]T[n] を集合としたもの content(T[n])content(T[n])SSとして FCP(C,content(T[n]),1,)FCP(C, content(T[n]), 1, \ell) を推論器に用いる. 更に \ell として、content(T[n])\lceil content(T[n]) \rceil を用いる (訓練事例の中の文の長さの最大値). すなわち FCP(C,content(T[n]),1,content(T[n]))FCP(C, content(T[n]), 1, \lceil content(T[n]) \rceil) であるが、これを 論文では FCPLearner1FCPLearner1 と呼ぶ.

もうひとつ、 FCP(C,content(T[n]),1,n)FCP(C, content(T[n]), 1, n)FCPLearner2FCPLearner2 と呼ぶ. これは完全に意味不明だ. なんで nn????

"witness" の定義

特徴集合のFCPバージョンみたいな

言語 LL について 有限 SLS \subseteq LLL の "witness of minimality" であるとは、
任意の L(SL)L' (S \subseteq L') について ..#L#L\exists \ell .~ \forall \ell' \geq \ell .~ \#L^{\leq \ell'} \leq \# L'^{\leq \ell'} であること

言語 LL について 有限 SLS \subseteq LLL の "witness of neighborhood minimality" であるとは、
任意の S(SSL)S' (S \subseteq S' \subseteq L) について L(SL).#LS#LS\forall L' (S' \subseteq L') .~ \# L^{\leq \lceil S' \rceil} \leq \# L'^{\leq \lceil S' \rceil} であること

Theorem 1

FCPLearner1FCPLearner1 が添字付き再帰的言語族を推論可能であることと、 その言語族が "witness of neighborhood minimality" を持つことと同値.

Corollary 1

FCPLearner1FCPLearner1 によって推論不能な、添字付き言語族が存在する.

反例となる言語族は次の通り:

これは有限証拠を持つが、"witness of neighborhood minimality" を持たない.

Theorem 2

FCPLearner2FCPLearner2 が添字付き帰納的言語族を推論可能であることと、 その言語族が "witness of minimality" を持つこととは同値.

Corollary 2

Corollary 3

FCPとMINL,MMGとの比較

推論する言語の包含関係について極小なものを求めるのがMINL.
推論するdescription (e.g. パターン) の極小なものを求めるのがMMG.

Prop. 1

FCPならばMMGであることの必要十分条件:
FCP(C,S,k,)FCP(C,S,k,\ell) の解 (パターン集合) を PP とする. 任意の k-multiple (高々kkサイズのパターン集合) Q(SL(Q))Q (S \subseteq L(Q)) に対して PQL(Q)L(P)P \sqsubset Q \Rightarrow L(Q)^{\leq \ell} - L(P)^{\leq \ell} \ne \emptyset とあるなら PPMMG(C,S,k)MMG(C,S,k) の解である.

FCPならばMINLであることの必要十分条件:
FCP(C,S,k,)FCP(C,S,k,\ell) の解 (パターン集合) を PP とする. 任意の k-multiple (高々kkサイズのパターン集合) Q(SL(Q))Q (S \subseteq L(Q)) に対して L(P)L(Q)L(Q)L(P)L(P) \subset L(Q) \Rightarrow L(Q)^{\leq \ell} - L(P)^{\leq \ell} \ne \emptyset とあるなら PPMINL(C,S,k)MINL(C,S,k) の解である.