パターン言語に就て, 空の代入を許すか許さないかで,
消去不能パターン言語の言語族の推論は, Inductive Inference of Formal Languages from Positive Data / Anguin が示した.
消去可能パターン言語の言語族の推論は, Reidenbach によって否定されている.
正規パターン言語は, 消去の可能, 不能に関わらず, 多項式時間の推論が可能であることを, Shinoharaが1983に示した. Polynomial time inference of extended regular pattern languages
たかだか k 個のパターン言語の和について, 言語の包含関係とパターン集合の構文的包摂関係の等価性を 与えるような Compactness の概念を 1994, Arimura+ が Finding Minimal Generalizations for Unions of Pattern Languages and Its Application to Inductive Inference from Positive Data で導入した. また, Compactness を有する言語和の族を効率的に学習するアルゴリズムを与えた.
消去不能パターン言語についての Compactness の必要十分条件は, 2003, Sato+ によって Learning of language generated by patterns from positive examples で与えられた.
消去可能パターン言語についての Compactness の必要十分条件は, 2002, Uemura+ によって Compactness and Learning of Classes of Unions of Erasing Regular Pattern Languages で与えられた.
消去可能正規パターン言語の和, 積, 補集合の学習問題を扱う
たかだか \(k\) 個の和積であるところの, \(k\)-和積パターン言語 を対象とする.
二つの表現を定義する
なんか帰納的に有限証拠集合を列挙できることを示す. 最後に, 言語族の集積点の概念とその結果を用いて, 学習不可能であることを示す.
パターンとは, \((\Sigma \cup X)^*\) のことで, 各変数が高々1回出現するものを, 正規パターンという. ここでは正規パターンのみを考える.
assign ::= { units }
units ::= unit | units
unit ::= var := pattern
var
patternを代入という.
例えば \(\theta = \{ x := cc, y := xay \}\) なんかが代入.
パターン \(p = axby\) の, 代入\(\theta\) による像は \(p\theta = accbxay\) である.
二つのパターン \(p, q\) について, \(\exists \theta . p = q\theta\) のとき, \(q\) を \(p\) の汎化と言って, \(p \preceq q\) と表す.
あるパターン \(p\) 変数に空を含む語を代入によって得られる 語全体を言語 \(L(p)\) という.
和積パターン表現 \(P\) に含まれるパターンの集合を, \(E(P)\) で表し, その濃度を \(\#E(P)\) で表す. \(\#E(P) \leq k\) となるものを, \(k\)-和積パターン表現 (\(CRP^k\)) という.
和積パターン表現から, その言語は自然に導かれる
みたいに.
\(k\)-和積パターン言語の族を, \(CRPL^k\) という.
正規パターン \(p_i\) に対して,
含まれる正規パターンの数 (\(k = n\)) に対して, \(k\)-和パターン表現 だとかいう.
命題論理と同様に, 標準形を考えられる. たぶんだけど, \((p \land ... \land p) \lor ... \lor (p \land ... \land p)\) というやつのことだろう.
2-和積言語 \(L(x_0 a_1 x_1 a_2 x_2 a_3 x_3) \cap L(xcy)\) は, 次の4-和積言語で表現できる.
\[L(x_0 c x_0' a_1 x_1 a_2 x_2 a_3 x_3) \lor L(x_0 a_1 x_1 c x_1' a_2 x_2 a_3 x_3) \lor L(x_0 a_1 x_1 a_2 x_2 c x_2' a_3 x_3) \lor L(x_0 a_1 x_1 a_2 x_2 a_3 x_3 c x_3')\]
\(k\)-和積パターン言語 (\(P\)) に等しい 和パターン言語 (\(D(P)\) と書く) が存在する.
証明は理解できなかったけど, 有限ならいくらでもいいんだから, できると思う
言語族 \(\mathcal{L}\) の言語 \(L\)の 特徴集合とは, 語の有限集合であって,
\(S \subseteq L' \in \mathcal{L} \Rightarrow L \subseteq L'\)
となるような \(S\) のこと.
\(k\)-和パターン表現 \(P, Q\) の 二項関係 \(\sqsubseteq\) を次のように定義する.
\[P \sqsubseteq Q \iff \forall p \in E(P), \exists q \in E(Q) . p \preceq q\]
正規パターン \(p\) の変数に, 長さ2の語を代入して得られる語全体を, \(S(p)\) と書く. また, 和パターン集合 \(P\) について自然に\(S\)は次のように定められる. すなわち, \(S(P) = \cup_{p} S(p)\).
\(k\)-和パターン表現 \(P, Q\) に対して, アルファベットの濃度が \(k+2\)以上ならば,
\(S(P) \subseteq L(Q) \iff P \sqsubseteq Q \iff L(P) \subseteq L(Q)\)
アルファベットの濃度が \(k+2\) 以上で, 和パターン表現 \(P\), \(k\)-和パターン表現 \(Q\) に就て,
\(S(P) \subseteq L(Q) \iff P \sqsubseteq Q \iff L(P) \subseteq L(Q)\)
\(k\)-和積 \(Q\) を次のような積和標準形で書く.
アルファベットの濃度が \(k+2\) 以上で, \(k\)-和積パターン \(P, Q\) に対して, Pの和パターン言語 (\(D(P)\)) を, \(P'\) とすると,
\[S(P') \subseteq L(Q) \iff \forall i. P' \sqsubseteq I_i \iff L(P) \subseteq L(Q)\]
言語族 \(\mathcal{L} = L_1, L_2 ...\) が添え字付きであるとは, 帰納的関数
f :: (Nats * Word) -> Bool
f (i, w) = w in L[i]が存在すること.
文字列の無限列 \(\sigma = w_1, w_2 ...\) が, 言語\(L\)の正提示であるとは, \(L = \{ w_i : i \in \mathbb{N} \}\) となること.
有限列 \(\sigma[n] = w_1 .. w_n\) を, 初期断片と呼ぶ.
推論アルゴリズム \(M\) は, 初期断片 \(\sigma[n]\) を入力とし, 推測として言語\(M(\sigma[n])\) を出力する.
\(n\)についての極限が存在するとき, 収束するという.
\(M\) が正例から極限同定できるとは, 任意の正提示について, 同じ言語に収束すること.
言語族 \(\mathcal{L}\)に対して, 極限同定できる \(M\) が存在するようとき, \(\mathcal{L}\)は正例から推論可能である, という.
言語族 \(\mathcal{L}\) における言語\(L\)の有限証拠集合\(S\) とは, 語の有限集合であって,
\[S \subseteq L \Rightarrow \lnot ( \exists L' \in \mathcal{L} . S \subseteq L' \subset L)\]
言語族\(\mathcal{L}\)に就て, 次の二つは同値.
アルファベット濃度が \(k+2\)のとき, \(CRP^k\) は正例から帰納学習可能である.
和積パターン表現に, 次を加える.
和積補パターン表現から言語を導くルールとして, 次を加える.
さて, \(k\)-和積補パターン言語は学習不能である.
証明には, 集積点の概念が使われてるため, 私には理解の及ぶところではない.