正規パターン言語の和と共通部分の帰納学習

original paper: http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1426-8.pdf

ALT パターン形式言語

導入 (先に学ぶべきことリスト)

パターン言語に就て, 空の代入を許すか許さないかで,

消去可能パターン言語,
消去不能パターン言語, と言い分ける.

消去不能パターン言語の言語族の推論は,

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\) -和積パターン言語 を対象とする.

二つの表現を定義する

和積標準形
消去可能正規パターン言語の有限和

なんか帰納的に有限証拠集合を列挙できることを示す. 最後に, 言語族の集積点の概念とその結果を用いて, 学習不可能であることを示す.

和積パターン言語の定義

notation

アルファベット \(\Sigma\) ( \(\{a,b,c...\}\) ) -- 有限集合
- 空列を \(\epsilon\) で表す
変数 \(X\) ( \(\{x,y,z...\}\) ) -- 加算無限集合
クリーネ閉包 ( \(\Sigma^*\) が語である)
長さ \(n\) の語全体 ( \(\Sigma^n\) )
長さ \(n\) 以下の語全体 ( \(\Sigma^{\leq n}\) )

パターンとは, \((\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)\) という.

\(k\) -和積パターン言語

和積パターン表現の定義

長さ0の文字列 ( \(\lambda\) ) は和積パターン表現である
正規パターンは和積パターン表現である
和積パターン表現 \(P, Q\) に対して \((P \land Q)\) は和積パターン表現である
和積パターン表現 \(P, Q\) に対して \((P \lor Q)\) は和積パターン表現である
以上で表される文字列のみが和積パターン表現である

和積パターン表現 \(P\) に含まれるパターンの集合を, \(E(P)\) で表し, その濃度を \(\#E(P)\) で表す. \(\#E(P) \leq k\) となるものを, \(k\) -和積パターン表現 ( \(CRP^k\) ) という.

和積パターン表現から, その言語は自然に導かれる

\(L(\lambda) = 0\)
\(L(P \land Q) = L(P) \cap L(Q)\)

みたいに.

\(k\) -和積パターン言語の族を, \(CRPL^k\) という.

正規パターン \(p_i\) に対して,

\(p_1 \lor ... \lor p_n\) を和パターン表現,
\(p_1 \land ... \land p_n\) を積パターン表現, という.

含まれる正規パターンの数 ( \(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')\]

定理 3.1

\(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)\) .

補題 3.2

\(k\) -和パターン表現 \(P, Q\) に対して, アルファベットの濃度が \(k+2\) 以上ならば,

\(S(P) \subseteq L(Q) \iff P \sqsubseteq Q \iff L(P) \subseteq L(Q)\)

補題 3.3 (補題2.2の上位互換)

アルファベットの濃度が \(k+2\) 以上で, 和パターン表現 \(P\) , \(k\) -和パターン表現 \(Q\) に就て,

\(S(P) \subseteq L(Q) \iff P \sqsubseteq Q \iff L(P) \subseteq L(Q)\)

定理 3.4

\(k\) -和積 \(Q\) を次のような積和標準形で書く.

\(Q = I_1 \land ... \land I_m\)
\(I_i = J_{i,1} \lor ... \lor J_{i, n_i}\)

アルファベットの濃度が \(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)\]

\(k\) -和積パターン言語の学習

正例からの帰納学習

言語族 \(\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}\) は正例から推論可能である, という.

\(k\) -和積言語の学習

有限証拠集合

言語族 \(\mathcal{L}\) における言語 \(L\) の有限証拠集合 \(S\) とは, 語の有限集合であって,

\[S \subseteq L \Rightarrow \lnot ( \exists L' \in \mathcal{L} . S \subseteq L' \subset L)\]

補題 4.2 (Angluin)

言語族 \(\mathcal{L}\) に就て, 次の二つは同値.

任意の \(L\) が有限証拠集合を持ち, それを列挙するアルゴリズムが存在する
\(\mathcal{L}\) は正例から帰納推論可能

定理 4.3

アルファベット濃度が \(k+2\) のとき, \(CRP^k\) は正例から帰納学習可能である.

和積補パターン言語

和積パターン表現に, 次を加える.

\(P\) が和積補パターン表現ならば, \(\lnot P\) もそれである.

和積補パターン表現から言語を導くルールとして, 次を加える.

\(L(\lnot P) = (L(P))^c\)

さて, \(k\) -和積補パターン言語は学習不能である.

証明には, 集積点の概念が使われてるため, 私には理解の及ぶところではない.