極小言語戦略

2015-01-14

概要

汎化システム が成す言語クラスのいくつかは, 極小言語戦略と呼ばれる戦略で作る推論機械によって 正提示で極限同定可能（単に推論可能という）である. ここではその戦略を紹介する.

正提示からの推論

今考えている問題は次のようなものである.

• 言語のクラス \(\mathcal L\)
  • これは既知
• 言語 \(L^* \in \mathcal L\)
  • これは未知
• 正提示 \(S \subset L\)
  • これは初め空集合が与えられ, 逐次的に \(s \in L^*\) が与えられ \(S\) に追加していく

\(S\) から \(L^*\) を予測するという問題.

そして今, 言語クラスは汎化システム \((D, \preceq)\) で与えられているものとする. すなわち, ある集合 \(D\) と写像 \(L\) があって \[L : D \xrightarrow{\sim} \mathcal L\] という同型対応がついている. 推論機械は言語を直接出力する代わりに description \(d \in D\) を出力する.

無矛盾な推論

推論すべき真の description \(p\) は \(L^* = L(p)\) であるから \[S \subseteq L(p)\] を満たす. この最後の包含が成り立っていることを「無矛盾である」とか「 \(p\) は \(S\) を被覆する」などと言う.

極限同定においては極限値が正しければよいので途中の推論ではどんなに誤っていてもよく, 従って上の意味で矛盾していてもよい. しかし一つの戦略として, 常に無矛盾な推論をすることが妥当そうに見える.

極小言語戦略

極小言語戦略とは, 正提示に対して無矛盾な言語の内, 極小なものを推論結果として出力する手法を言う. ここで極小であるとは, 言語の集合としての包含関係によって定まる順序に関する. （最小とは限らないので極小であることに注意.） そしてその極小な言語を 極小言語 (minimal language; minl) と言う.

いくつかの汎化システムが成す言語クラスは実は極小戦略によって推論可能である.

この戦略はすなわち, 無矛盾なものであればいくらでもありえるし特に \(\top \in D\) といった自明なものもある中で, 集合の小ささと推論の良さと思おうという気持ちである.

\(S\) から極小言語（その description）を出力する仮定を MINL とすれば極小言語戦略とは次のような擬似コードで表される:

S = set()
g = None  # この時点の推論結果
while s = input():
    S.add(s)
    if s in L(g):
        guess(g)  # 更新の必要なし
    else:
        g = MINL(S)  # 更新
        guess(g)

有限の厚み

言語クラス \(\mathcal L\) が任意の空でない正提示（文字列の集合）\(S\) に対して以下を満たすとき \(\mathcal L\) は有限の厚みを持つという.

• \(\{ L \in \mathcal L \mid S \subseteq L \}\) が有限集合

すなわち被覆する言語の候補が常に有限通りであることを言う.

定理: 有限の厚みを持つ言語クラスは極小言語戦略によって推論可能

証明はまだ分かってないので理解したら書きます.