誤情報を含む正則パターン言語の多項式時間推論

大阪府立大学 竹内正幸、佐藤優子
誤情報を含む正則パターン言語の多項式時間推論 (アルゴリズムと計算の理論)
数理解析研究所講究録 1998
false.md

タイトルの通り、 消去不能正則パターン言語の極限同定を行う. 示すのは 無矛盾保守的 なものである.

無矛盾とは 普通に n.C(M(σ[n]))content(σ[n])\forall n .~ C(M(\sigma[n])) \supseteq content(\sigma[n]) のこと.

保守的とは n.C(M(σ[n]))content(σ[n+1])M(σ[n])=M(σ[n+1])\forall n .~ C(M(\sigma[n])) \supseteq content(\sigma[n+1]) \Rightarrow M(\sigma[n]) = M(\sigma[n+1]) であった.

言語の近傍系

言語クラス \mathcal{L}. 言語 LL \in \mathcal{L} の近傍系 𝒩L\mathcal{N}_L \subseteq \mathcal{L} というものを定義する.

LL 自身が近傍系に含まれてることが要請される. 例えば、 𝒩L={L}\mathcal{N}_L = \{L\}𝒩L={LS:S is finite language }\mathcal{N}_L = \{L \cup S : S ~ \text{ is finite language } \} が近傍系である.

誤情報を含む言語LLの正提示とは、 L𝒩LL' \in \mathcal{N}_L の正提示のことである. 部分だけを上手くとり出せば、LL の正提示である.

notation

無限列から集合への変換 (content) を ^\hat{\cdot} で書く (σ^\hat{\sigma}).

言語 LL と、 誤情報を含む正提示の断片 S=σ[n]^S = \hat{\sigma[n]} と、 近傍系 𝒩L\mathcal{N}_L が無矛盾であるとは、 L,L𝒩LSL\exists L', L' \in \mathcal{N}_L \land S \subseteq L' という LL' が存在すること.

正則パターン和言語で構成する近傍系

パターンの何文字目がアルファベット (定数) であるかを数える関数 Ic:𝒫2I_c : \mathcal{P} \rightarrow 2^\mathbb{N} Ic(p)={i:i{1|p|},p[i]Σ}I_c(p) = \{ i : i \in \{1 \ldots |p|\}, p[i] \in \Sigma \}

パターンの上の距離を表現する部分関数 dd を次のように定義する.

For p,qp, q s.t. |p|=|q||p| = |q| and Ic(p)=Ic(q)I_c(p) = I_c(q): d(p,q)=|{i:iIc(p),p[i]q[i]}|d(p, q) = |\{ i : i \in I_c(p), p[i] \ne q[i] \}|

この距離を用いて近傍系を定義していくことにする.

まず、 B(p,k)={q:d(p,q)k}B(p,k) = \{ q : d(p,q) \leq k \} なるものを定める. pp の定数部分を高々 kk 個、変更してできるパターンの集合である. |B(p,k)||Σ||p||B(p,k)| \leq |\Sigma|^{|p|} であることが分かる.

P:PB(p,k),pPP : P \subseteq B(p,k), p \in Ppp の k-近傍という. 逆に、 ppPP の核パターンと呼ぶことにする.

k-近傍全体をk-近傍族 k-𝒩𝒫p\mathcal{NRP}_p と書く. k-近傍族がなす、言語族を k-𝒩𝒫p\mathcal{NRPL}_p と書くことにする.

特に 1-近傍 のことを単に近傍 (𝒩𝒫\mathcal{NRP}) と呼ぶことにする.

Example

p=axbc,q=bybcp=axbc, q=bybc (x,yXx,y \in X) P={axbc,bxbc}P = \{ axbc, bxbc \} とすると、PPpp の近傍でもあるし qq の近傍でもある. L(P)𝒩𝒫p𝒩𝒫qL(P) \in \mathcal{NRPL}_p \cap \mathcal{NRPL}_q 従って、この近傍系は「無矛盾ではない」.

L(P)L(P) が正提示されるとき、 確かにこれは L(p)L(p) の誤情報付き正提示でもあるし、 確かにこれは L(q)L(q) の誤情報付き正提示でもある. 従って、原理的に同定不可能である.

無矛盾に同定するためには、 2つの異なる近傍系は、集合の積を持ってはいけない.

そういうわけで、もっと条件を加えて、近傍系を定義する.

定義 4.2

正則パターン pp と、その (k=1k=1) 近傍パターン集合 PP について、次の三種類の条件を考える.

  1. 条件 A1A_1: iIc(p)\forall i \in I_c(p) に対して {a:pP,a=p[i]Σ}\{ a : p' \in P, a = p'[i] \in \Sigma \}Σ\Sigma部分集合であること
  2. 条件 A2A_2: |P|2|P| \geq 2 ならば、iIc(p)\forall i \in I_c(p) に対して、P{p[i/a]:aΣ}P \not\subseteq \{ p[i/a] : a \in \Sigma \} であること (p[i/a]p[i/a]ppii 番目をアルファベット aa で置換したもの)
  3. 条件 AA: 上の2つが同時に満たされること

条件1,2をそれぞれ満たす近傍パターン集合を、それぞれ A1,A2A_1, A_2 近傍パターン集合 𝒩𝒫pAi\mathcal{NRP}_p^{A_i} と呼ぶ. 条件3を満たす近傍パターン集合を特別に AA近傍パターン集合 𝒩𝒫pA\mathcal{NRP}_p^A と呼ぶ.

同様にその言語族を それぞれ 𝒩𝒫pAi\mathcal{NRPL}_p^{A_i}𝒩𝒫pA\mathcal{NRPL}_p^A と書くよ.

定理 4.3

正則パターン p,qp, qA1A_1 近傍パターン集合 P,QP, Q について、次の三つは同値である.

  1. L(P)=L(Q)L(P) = L(Q)
  2. S1(P)=S1(Q)S_1(P) = S_1(Q)
  3. P=QP = Q

|Σ|=2|\Sigma|=2 のとき、ppA1A_1 近傍パターン集合とは {p}\{p\} しかないので、自明.

この定理があってもなお、 近傍パターン集合 PP から核パターン pp は一意に定まらない. 先ほどの例を思い出せばよい. Σ={a,b,c}\Sigma=\{a,b,c\}P={axbc,bxbc}P=\{axbc, bxbc\}p={axbc},q={bxbc}p=\{axbc\}, q=\{bxbc\} のどちらともの A1A_1 近傍パターン集合として正しい.

近傍パターン集合 PP極小多重汎化 であるとは、 無矛盾で極小であること. SL(P)¬(Q,SL(Q)L(P)).S \subseteq L(P) \land \lnot \left( \exists Q, S \subseteq L(Q) \subseteq L(P) \right) .

定理 4.4

任意の P𝒩𝒫A1P \in \mathcal{NRP}^{A_1}S1(P)S_1(P) の極小多重汎化である.

𝒩𝒫A1\mathcal{NRP}^{A_1} の極小多重汎化とその核パターンの推論

  1. SS の 最長の極小汎化を計算して pp とする
  2. P{}P \leftarrow \{\}
  3. KΣK \leftarrow \Sigma
  4. m|p|m \leftarrow |p|
  5. t0t \leftarrow 0
  6. 力尽きた
  7. むりむり

まーなんか要するにさ、 近傍パターン集合を直接学習して、 その核パターンを答えとする感じ?