paper/

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

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

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

  1. 消去不?能パターン言語の言語族の推論は、 Inductive Inference of Formal Languages from Positive Data / Anguin が示した。

  2. 消去可?能パターン言語の言語族の推論は、 Reidenbach によって否定されている。

  3. 正規パターン言語は、消去の可能、不能に関わらず、 多項式時間の推論が可能であることを、 Shinoharaが1983に示した。 Polynomial time inference of extended regular pattern languages

  4. たかだか k 個のパターン言語の和について、 言語の包含関係とパターン集合の構文的包摂関係の等価性を 与えるような Compactness の概念を 1994, Arimura+ が Finding Minimal Generalizations for Unions of Pattern Languages and Its Application to Inductive Inference from Positive Data で導入した。 また、 Compactness を有する言語和の族を効率的に学習するアルゴリズムを与えた。

  5. 消去不能パターン言語についての Compactness の必要十分条件は、 2003, Sato+ によって Learning of language generated by patterns from positive examples で与えられた。

  6. 消去可能パターン言語についての Compactness の必要十分条件は、 2002, Uemura+ によって Compactness and Learning of Classes of Unions of Erasing Regular Pattern Languages で与えられた。

趣旨

消去可能正規パターン言語の和、積、補集合の学習問題を扱う

たかだか k 個の和積であるところの、 k-和積パターン言語 を対象とする。

二つの表現を定義する

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

和積パターン言語の定義

復習

notation

パターンとは、 \((\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-和積パターン言語

和積パターン表現の定義

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

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

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

  1. \(L(\lambda) = 0\)
  2. \(L(P \land Q) = L(P) \cap L(Q)\)

みたいに。

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')\]

定理 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\) を次のような積和標準形で書く。

アルファベットの濃度が \(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}\)に就て、次の二つは同値。

定理 4.3

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

和積補パターン言語

和積パターン表現に、次を加える。

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

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

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

さて、k-和積補パターン言語は学習不能である。

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