2006年度 計算機数学B 講義資料

東北大学 赤間陽二
2006年度 計算機数学B 講義資料
http://www.math.tohoku.ac.jp/akama/Jugyou.html
tohoku.md

ググっていたら偶然見つけたもので、 東北大学の先生が講義のレジュメとしてpdfファイルをネットの上で公開された状態で置いてあったので読ませてもらう. 9年前のものなので (2015.6.4 Thu) いつまで置いてあるかわからない.

0508

  1. 正規言語
  2. 帰納的言語
  3. 帰納的可算言語

を考える.

これらは階層構造をしていて ()()()(正規言語) \subseteq (帰納的言語) \subseteq (帰納的可算言語) とある. 例えば、反復補題の格好の例として、 {anbn:n}\{a^n b^n : n\in\mathbb{N}\} は正規言語には含まれないが、帰納的言語である.

正規言語の定義

言語 LL が正規言語である \iff
ある決定性有限オートマトン (DFA) によって受理できる文字列全体とLLが一致すること.

帰納的言語の定義

言語 LL が帰納的言語である \iff
文字列が与えられたとき、これが言語LLに含まれるかの判定をある帰納関数 χ(:Σ*{0,1})\chi (: \Sigma^* \rightarrow \{0,1\}) でできること. χ(w)wL\chi(w) \iff w \in L

帰納的可算言語の定義

言語 LL が帰納的可算である \iff 帰納関数 e:Σ*e : \mathbb{N} \mapsto \Sigma^* を用いて L={e(n):n}L = \{ e(n) : n \in \mathbb{N}\} とできること.
あと空な言語も特殊に帰納的可算とする.
ee は列挙関数と呼ばれる.

Prop. 帰納的言語の補言語は帰納的言語

χ(w)=1χ(w)\chi'(w) = 1 - \chi(w)

認識可能性

プラグラム PP がその言語を認識するとは、 言語が含む任意の文字列を入力すると停止すること.

次に見るように、認識可能であることと、帰納的可算言語であることとは、同値.

Prop. 帰納的可算言語 \Rightarrow 認識可能

def P(w):
  e = enumerator for L
  for i in [0..]
    if w is e(i):
      return i

Prop. 認識可能 \Rightarrow 帰納的可算言語

まず、(,)\mathbb{(N, N)}\mathbb{N} とは準同型だから (i,j)=f(t)(i, j) = f(t) という準同型写像が存在する.
具体的には、 f1(n,m)=(n+m)(n+m+1)/2+nf^{-1}(n, m) = (n+m) (n+m+1)/2 + n の逆像である.

言語 LL について,

  1. これを認識する PP
  2. LLが空でないのなら、wLw \in Lww を持っておく
  3. なんでもいいから Σ*\Sigma^* についての列挙 (wi)i(w_i)_i

LL の列挙 e(t)e(t) は次のようにする.

  1. let (i,j)=f(t)(i, j) = f(t)
  2. wiw_i を 時間 jj の制限つきで LL に認識させる
  3. 制限時間未満に停止したなら wiLw_i \in L なので e(t)=wie(t) = w_i
  4. さもなくば, よくわからないので e(t)=we(t) = w

すべての wiw_i についてすべての制限時間で認識するのでいつかは言語すべてを列挙できる

帰納的言語 \subseteq 帰納的可算言語

帰納的言語は、帰納的可算言語である.

Proof.
帰納的言語ならば、 membership 関数 χ\chi があって、 それを用いて、停止するかしないか選ぶプログラムを書ける.

def P(w):
  if chi(w):
    return
  else
    loop

プログラムの表現

プログラムの文字列による表現を pp とする.
pp が表現するプログラムによって認識される言語を L(p)L(p) と書く.

帰納的可算言語 BB について、 これを認識するプログラムの表現 pp が存在する.

定理

Γ*\Gamma^* をプログラム全体、LcL^c を 言語 LL の補言語とするとき、 J={pΓ*:Lc(p)p}J = \{ p \in \Gamma^* : L^c(p) \ni p \} は帰納的可算ではない. JJ とは自身を認識できないプログラム全体の集合.

補題

集合 RR からその 冪集合 𝒫(R)\mathcal{P}(R) への全射というものは存在しない

定理

自身を認識できるプログラムの集合: K={pΓ*:L(p)p}K = \{ p \in \Gamma^* : L(p) \ni p \} これは帰納的ではく、帰納的可算である (もちろん KKJJ の補集合である).

KK を認識するプログラムは次を実行すればよい: 入力 pp を解釈することで、プログラム PP を得る. P(p)P(p) を実行したとき、 pKp \in K ならば、これは停止する. さもなくば、PP は停止しない.

# K を認識するプログラム
def PK(p):
  P = eval(p)
  P(p)

0515

推論機械

言語の完全提示

語と二値のペアの無限列 σ=(w1,I1),(w2,I2),...\sigma = (w_1, I_1), (w_2, I_2), ... であって、次を満たすものを、 言語 LL の完全提示という.

  1. {w1,w2,...}=Σ*\{ w_1, w_2, ... \} = \Sigma^*
  2. IiwiLI_i \land w_i \in L or ¬IiwiL\lnot I_i \land w_i \not\in L

無限列 σ\sigma に対して、その断片 σ[i]=(w1,I1)...(wi,Ii)\sigma[i] = (w_1, I_1) ... (w_i, I_i) を入力として受け取ったときに、 推測 gig_i を出力するものを推論機械という.

極限同定の定義

LL の任意の完全提示 σ\sigma についての推論 gig_i が極限で gg を定めて L(g)=LL(g) = L であること

言ってしまえば、 推論機械というのは、

  1. 新しい例が提示されるたびに、
  2. 過去に提示されたものに矛盾しない、
  3. 表現クラスの枚挙の中で最初の表現を
  4. 仮説として出力する

枚挙による学習機械

帰納的可算な表現(言語)クラス RR を持つ、
添字付き帰納的言語クラス CCRR の下で極限同定する
(rR,L(r)=Cir \in R, L(r) = C_i)

rRr \in R は可算だからそれを列挙しておいて、
提示に対して無矛盾なものの最初の一つを推測することをひたすらする

0522

枚挙による学習機械は一般に効率的 (多項式時間) ではない
正規言語については効率的な方法がある、という話

無矛盾

断片 σ[i]\sigma[i] を受け取ったときの推測 gig_i について、 いつも σ[i]L(gi)\sigma[i] \subseteq L(g_i) が成立するように推測すること.

ここで、断片は本来列だけど、集合であるかのように書いた.

保守

推測の列 g1,g2...g_1, g_2 ... について L(g1)L(g2)...L(g_1) \supseteq L(g_2) \supseteq ... とあるように推測すること.

0529

正規言語の学習とは即ち、言語から有限オートマトンを復元することにほかならない. 完全提示からは、無矛盾かつ保守的に推論が可能. 詳しくは、 "Regular Positive Negative Inference (RPNI) アルゴリズム" でググること.

0605

言語の正提示

言語 LL の正提示とは、
語の無限列 σ=σ1,σ2,...\sigma = \sigma_1, \sigma_2, ... であって、 {σi:i}=L\{\sigma_i:i\} = L を満たすようなものを言う.

正提示の学習機械

完全提示を考えていたのを、 正提示の断片を入力にし、 極限において同定する問題に変形する

超有限

言語クラス CC が超有限であるとは、

  1. infinite L,LC\exists \text{ infinite } L, L \in C
  2. finite L,LC\forall \text{ finite } L', L' \in C

こういうのは、簡単に言えば大きすぎるクラスである.

Prop. 超有限な言語クラスは正提示から極限同定不能

無限な方の言語 LL を正提示から学習できない. LL の任意の正提示の断片 σ[i]\sigma[i] について、 これを被覆する有限の言語が常に、言語クラスに持つからである.

Prop. 正規言語全体は超有限である

有限な言語というのは常に正規言語であるから.

言語クラスの階層

  1. 超有限は完全提示で学習可能
  2. 正規言語全体のクラスは超有限
  3. パターン言語全体のクラスは正提示から学習可能
  4. ゼロリバーシブル言語は正提示から学習可能

もちろん、パターン言語と正規言語はオーバーラップ (正規パターン) があるがな.

パターン

パターンの定義

Σ,V\Sigma, V の元からなる空でない語をパターンという

代入とは変数をパターンで置き換える操作

普通、同時に置き換えを1つ以上行ってよいが、 変数は無限にあるんだから一旦別なものに置き換えることで一つずつ行っても同値だよなぁ

θ={xy,yx}\theta = \{ x \mapsto y, y \mapsto x \} によって p=xxyyyyxxp = xxyy \mapsto yyxx であるけど

  1. θ1={xz}\theta_1 = \{x \mapsto z\}
  2. θ2={yx}\theta_2 = \{y \mapsto x\}
  3. θ3={zy}\theta_3 = \{z \mapsto y\}

を順に適用してもいいよな

汎化関係 (Less-general-than relation) \preceq

pqθ.p=qθp \preceq q \iff \exists \theta .~ p = q\theta

パターン言語

パターン pp に対して、 言語 L(p)={wΣ+:wp}L(p) = \{ w \in \Sigma^+ : w \preceq p\}

{L(p):p}\{L(p):p\} は添字付き帰納的言語クラス

0612

表現クラスをパターン全体とする言語クラスを 𝒫𝒜𝒯\mathcal{PAT} (パターン言語全体) と書くことにする

これは帰納的言語クラスであって:
任意のパターン pp について 次のようなプログラム χ\chi が存在する χ(p,w)L(p)w\chi(p, w) \iff L(p) \in w

じゃあこの χ\chi を構成してみる

a,bΣ,wΣ*,xVa, b \in \Sigma, w \in \Sigma^*, x \in V, パターン pp

まあ当たり前のこと書いてるだけだ

標準形パターン

pqpqpqp \preceq q \land p \succeq q \iff p \equiv q とすると、 変数のリネームは等価

パターン pp 中で出現する変数を左から x1,x2,...,xkx_1, x_2, ..., x_k としたものを標準形という

k|p|k \leq |p| であって、言語は標準形にしても変わらないこと

極小学習戦略

正提示の断片 σ[i]\sigma[i] に対して {L(p):σ[i]L(p)}\{L(p) : \sigma[i] \subseteq L(p)\} は有限であって空ではない

=x1\top = x_1 があるだからまぁ、な

というわけで 言語 L(gi)L(g_i) の中で \subseteq に関して極小な gig_i が存在する

これを計算する戦略を極小学習戦略と呼ぶ

0619

KMP言語

部分列

アルファベット集合 Σ\Sigma の上の文字列の関係を次のように定義する

uvu \lhd v \iff uuvv の部分文字列である (x,yΣ*.xuyv\exists x, y \in \Sigma^* .~ xuy \equiv v)

KMP言語

wΣ*w \in \Sigma^* の生成するKMP言語とは

L(w)={v:wv}L(w) = \{ v : w \lhd v \}

定義から uvL(v)L(u)u \lhd v \iff L(v) \subseteq L(u) であることは明らか

極小学習

KMP言語は有限の厚さ (finite thickness) を持って、 極小言語学習の戦略で学習可能

有限証拠の最長共通部分文字列(連続列)をとればいいだけ

有限の厚さ の定義を実のところ未だ知らない

0626

  1. 有限の厚さを持つ
  2. 特徴例集合を持つ
  3. 有限証拠を持つ

1231 \Rightarrow 2 \Rightarrow 3 であって逆は成り立たない
1.2. はMINLで正提示から学習が可能

MINL

復習になるけど、言語クラス CC 中のある言語の有限部分証拠 SS があるときに

LMINL(S,C)L \in MINL(S, C) とは、 SSを内包するLCL' \in C のなかで極小なものの一つがLLであること

言語クラスが何かを情報として使っていいことに注意

有限の厚さを持つ \Rightarrow MINLは非空有限集合

CC が有限の厚さを持つとは、
w.{L:wLC}\forall w .~ \{L:w\in L\in C\} が有限集合

例えば今まで見てきたパターン言語やKMP言語といったクラスは有限の厚さを持つ

有限の厚さを持たない例

Li={w:|w|i}L_i = \{ w : |w| \leq i \} (i<kLiLki < k \iff L_i \subset L_k)

これは ww に対して wLiw \in L_i となる ii は可算無限個あって厚さは有限ではない.

しかしながら極小言語は簡単に考えられる:
MINL({w1..wn},C)={Lk}MINL(\{w_1 .. w_n\}, C) = \{ L_k \} where k=max{|w1|..|wn|}k = \max \{ |w_1| .. |w_n|\}

MINLが無限集合 \Rightarrow 有限の厚さを持たない

これは自明.
MINLが無限とはつまり有限証拠の任意の一つが属する言語が無限であることだから.

MINLが無限集合となるような例

  1. 言語 LiL_i{ai}\{a^i\} の補集合として、この言語クラスを考える.
  2. どの LiL_iLjL_j も包含関係にそもそもないから任意の言語を持ってきて極小だと言える
  3. MINL(aj,C)={Lk:kj}MINL(a^j, C) = \{ L_k : k \ne j \}

MINLが空の例

言語 LiL_i は空文字列と長さがiiより大きい語全体 Li={λ}{w:|w|>i}L_i = \{\lambda\} \cup \{w:|w|>i\} このとき L0L1...Ln...{λ}L_0 \supset L_1 \supset ... \supset L_n \supset ... \supset \{\lambda\} という包含関係になる MINL({λ},C)MINL(\{\lambda\}, C) を考えるとこれは空になる (LL_\infty というこの言語クラスにおけるボトムだ)

ここまでのまとめ

この二つは別に同値ではない
有限の厚さはMINLを使うための十分条件でしかない

特徴例集合

言語クラス CC に関する言語 L(C)L (\in C) の特徴例集合 FF とは

  1. FF は有限集合
  2. FLF \subseteq L
  3. LC.FLLL\forall L' \in C .~ F \subseteq L' \Rightarrow L \subseteq L'

N.B. LLが有限集合なら F=LF=L とすれば上は自明に満たされて、これは言語自身が特徴例集合だ

任意の LL が特徴例集合を持つとき、 「言語クラス CC は特徴例集合を持つ」という

例. 特徴例集合を持つが有限の厚さを持たない

先ほどの Li={w:|w|i}L_i = \{w:|w|\leq i\} を考える
これは有限の厚さを持たなかった

さて LiL_i は有限集合なので (アルファベットは有限集合) それ自身が特徴例集合だ

Thm. 有限の厚さを持つならば、特徴例集合を持つ

厳密な証明ではないが...
実際に特徴例集合を構成してみせればよい

LLの特徴例集合 FF を構成することを考える

  1. F0={w0}F_0 = \{w_0\} s.t. w0Lw_0 \in L
  2. for each ii
    1. assert FiLF_i \subseteq L
    2. FiLF_i \subseteq L' かつ not(LLL \subseteq L') となるような LL' は言語クラスの厚さゆえ有限である
    3. そのような LL' がないなら終了して F=FiF = F_i とする
    4. not(LLL \subseteq L') と LLL \cap L' \ne \emptyset から L\LL' \setminus L は非空
    5. wL\Lw \in L' \setminus L とする
    6. Fi+1=Fi{w}F_{i+1} = F_i \cup \{w\}

ループのたび 2-2 における LL' の数は必ず減っていくので有限ステップで終了する

Thm. 特徴例集合をもつならば、MINLを使える

証明は大体自明だと思う

言語 LL の正提示断片 σ[i]\sigma[i] からの推測 L(gi)(L)L(g_i) (\supseteq L) は特徴例集合を持ってて、 その定義式ってまさしく極小を表してる

有限証拠の定義

言語 LL の有限部分集合 (TT とする) であって L.TLLL\forall L' .~ T \subseteq L' \Rightarrow L' \not\subset L とある TT を有限証拠という.

右辺は特徴例集合に似てるけど "特徴例集合ならば有限証拠" である.

例. 有限証拠であって特徴例集合ではないもの

言語クラス C={L1,L2}C = \{L_1, L_2\};

一方は他方と異なる部分を持っている

T={an:n}T = \{a^n:n\} は特徴例集合ではないが有限証拠としては問題ない

このような場合、提示として {an}\{a^n\} からなる列が来ても正しくMINLできない

0703

  1. 正提示から学習可能
  2. (EC1) 有限証拠が一様に帰納的列挙可能
  3. (C2) 特徴例集合を持つ
  4. (C3) 有限の弾力性を持つ
  5. (C4) 有限の厚さを持つ

543215 \Rightarrow 4 \Rightarrow 3 \Rightarrow 2 \iff 1

これを見ていく

EC1: 有限証拠の一様帰納的列挙

ii を入力として、LiL_i の有限証拠 TiT_i を列挙するような帰納的手続き. 即ち、マシーン MM

M(i)=τ1,τ2...M(i) = \tau_1, \tau_2 ... where τkLi\tau_k \subset L_i such that kτk=Ti\bigcup_k \tau_k = T_i

というもの.

特徴例集合 FF が存在するならば、EC1 は満たされる.

有限の弾力性 (finite elasticity)

定義は以下通り: w,|{L:wL}|<\forall w, |\{ L : w \in L \}| < \infty

対義語は「無限の弾力性」.

0710

EC1 iff 極限同定可能