数理解析研究所講究録1093 巻 1999 年 111-116

111

特例からのパターン上の決定木の帰納推論
寺田幹治*

向内康人\dagger

佐藤優子\dagger

Mikiharu Terada

Yasuhito Mukouchi

Masako Sato8

大阪府立大学大学院理学系研究科\dag er
大阪府立大学総合科学部

概要:

正則パターン上の決定木の学習の問題は, DNA 配列からのモチーフの発見というゲノム情報科学の観点から PAC 学習の枠組みを用いて研究されてきた. 本稿
では, この問題を正例からの極限同定という枠組みで論じている.
パターンとは, 定数記号と変数記号からなる文字列であり, パターン上の決定木は,内部ノードのラベルがパターンで, 葉のラベルが または 1 の決定木である. 本稿では, 各パターンに対して, co–パターンと呼ばれる文字列を導入し, その意味をパター
ン言語の補言語のある部分集合として定義する. その解釈の下で, パターン上の決定
木の意味を定義し, 深さが高々 である決定木で定義される言語の族が正距から推論可能であることを示す. 特に, 正則パターン上の深さが 1 である決定木で定義される言語の族に関しては, 正例から多項式時間の更新で推論するアルゴリズムを与える.
$0$

$n$

1. はじめに含まれるか否かに応じて左または右に分岐し, 根から葉へ至る. 葉のラベルが 1 ならば, 文字列は受理され,ならば受理されない. 決定四 が定義する言語は,で受理される文字列の集合である. したがって, 決定木で定義される言語は, パターン言語やそれらの補言語に対して, 高々有限回の積 (共通部分) 演算や和演算を施して得られる言語である.
$w$

DNA 配列の中の機能領域からモチーフを発見することは, 分子生物学における重要な問題の一つである. Arikawa et
や等は, 計算学$\mathrm{a}1.[3]$$\mathrm{M}\mathrm{i}\mathrm{y}\mathrm{a}\mathrm{n}\mathrm{o}[6]$習のパラダイムの–つである「PAC 学習」の枠組みを用いてこの問題の定式化を行\nu \searrow その理論的研究
から学習システムの開発及び計算機実験まで幅広い研究を行っている. DNA 配列からのモチーフを表現するために採用されたのは, 正則パターン上の決定木である. また, 学習システムに提示されるのは,DNA 配列の正の事例及び負の事例である. 本稿では, 以下に述べる 「極限同定」に基づく帰納推論の枠組みを用いて, 正の事例からパターン上の決定木
を極限同定する問題を考える.
パターンとは, アルファベットに含まれる定数記号と変数からなる文字列である. 各変数が高々1回しか出現しないパターンは正則パターンと呼ばれる. パターン上の決定木 $T$ は, 内部ノードのラベルがパターンで, 葉のラベルが 1 または の決定木で
ある.
上の文字列
が与えられると, パターン$\Sigma$$0$$\Sigma$$w$

をラベルとするノードでは $w$ がそのパターン言語に

$T$

$0$

$T$

パターン言語の族は, 正例から帰納推論可能な言によって導入された. 正例からの帰納推論とは, 与えられた正の事例からそれら語族として$\mathrm{A}\mathrm{n}\mathrm{g}\mathrm{l}\mathrm{u}\mathrm{i}\mathrm{n}[2]$を説明する–般的な規則表現 (例えば, パターンやパターン上の決定木等) を推測する過程である. 本
稿では,の極限同定と呼ばれる推論の成功基準の下で, 上記のパターン上の決定木の正例からの$\mathrm{G}\mathrm{o}\mathrm{l}\mathrm{d}[5]$帰納推論を考える.

言語演算の観点から推論可能性を扱った研究に, .
による 「有限の弾力性」 という概念がある. Wright は, 有限の弾力性をもつ言語族が正例から推論可能であり, またこの性質が和演算に関して閉じていることを示した. また, パターン言語族が有限の弾力性をもつことを示した.
は, 有限の弾力性が積演算や連接演算等に関しても$\mathrm{W}\mathrm{r}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}\mathrm{l}\mathrm{l}2]$$\mathrm{M}\circ \mathrm{r}\mathrm{i}\mathrm{y}\mathrm{a}\mathrm{m}\mathrm{a}\ \mathrm{s}_{\mathrm{a}}\mathrm{t}\mathrm{o}171$

112

閉じていることを示した. 演算の閉包性に関するこれらの結果を用いると, もし, パターン言語とそれらの補言語からなる言語族が有限の弾力性をもつなて, その有限列$\sigma[n]$が入力された後, $M$ が生成する

推測を $M(\sigma[n])$ で表す. 推論機械 $M$ が入力の列に対して, 添字 $g\in N$ に収束するとは, ある $m\in N$$\sigma$

であるパターン上の決定木で定義される言語の族は, 有限の弾力性を有することになり, 正例から推論可能ということになる.

が存在し, 任意の $n\geq m$ に対して, $M(\sigma[n])=g$となることをいう. 推論機械 $M$ が言語 $L$ を正例か

本稿では, このような観点から決定木で定義されに対して, CO-パ
る言語を扱うため, 各パターン

は, 単に推論する) とは,らば, 深さが高々

$d$

$P$

ターンと呼ばれる文字列$p^{c}$

を導入する. CO-パターの意味 $L$ を $L(p)^{c}$ の部分集合 $L(p^{c})=\{w\in$
ただし,$L(p^{c})||w|\geq \mathrm{m}\mathrm{a}3\zeta(1, |p|-k)\}$ と定義する.
ン$p^{c}$

は文字列の長さをは固定された非負の整数で,が有限表す. このような解釈の下で, 言語族
$|p|$

$k$

$J\mathcal{P}L$の弾力性をもつことが示される. したがって, この言語族に和演算や積演算を高々 回施して得られるや深さが高々 である決定木で定言語族
は, 共に有限の弾力性をもち義される言語族$n$$d$$J\mathcal{P}L(n)$$\mathcal{T}\mathcal{P}\mathcal{L}_{d}$正例から推論可能である.

正則パターン上の決定木に制限した場合もこれらの結果は成り立つ. 本稿では, $k=0$ の場合について,

深さが 1 の決定木で定義される言語の族を Angluinの意味で語例から多項式時間の更新で推論可能とす

ら極限同定 (identification in the limit) する (またの任意の正提示に対して, $M$ が $L_{i}=L$ となる添字 に収束することをいを正例から極限同定すう. また, 任意の言語$i$$L\in \mathcal{L}$る推論機械 $M$ が存在するとき, 言語族$\mathcal{L}$は正例から推論可能であるという.
推論機械 $M$ が言語族$\mathcal{L}$を正例から推論し, 各入力を受け取ってから推測を出力するまでに必要な時間がそれまでの入力の長さの和のある多項式で押えられる時, その推論機械 $M$ は言語族

を正眼から$\mathcal{L}$

多項式時間 (の更新) で推論するという. また, 言語
を正物から多項式時間 (の更新) で推論する推族$\mathrm{H}\hslash \mathrm{H}$$\mathcal{L}$論機械が存在する時, その言語族は, 正例から多項式時間 (の更新) で推論可能であるという.
言\beta Q
轡型から推論可能であるための必要条件に, 言語族に含まれる各言語の有限証拠集合の存在がある$(\mathrm{A}\mathrm{n}\mathrm{g}\mathrm{l}\mathrm{u}\mathrm{i}\mathrm{n}[2])$

ここで,るアルゴリズムを与える.

$L$

.

集合

$T_{i}\subseteq\Sigma^{*}$

合であるとは, (1)$T_{i}$

はの有限証拠集の有限部分集合であり,が言語$L_{i}$$L_{i}$となる添字 $i\in N$ が存在しない(2)ことをいう.
正写から推論可能であるための十分条件として, 有限の厚さという概念がある. 言語族 が有限の厚さ$T_{i}\subseteq L_{j}\subset\sim L_{i}$2. 判例からの言語の帰納推論
上のすべての文字列の集合をで表す.
で表し, 空列を除く文字列の集合をで表す.
の要素の個数をまた, 有限集合
アルファベット$\Sigma$$\Sigma^{+}$$\Sigma^{*}$$S$$\# S$の正提示でが言語
文字列の無限列あるとは, $\{w_{n}|n\geq 1\}=L$ が成り立つことであの番目までる. 文字列の無限列 $\sigma=w_{1},w_{2},$$w_{1},w_{2},$$L$$\cdots$$\cdots$の初期部分列を$\sigma[n]$

$n$

で表す.

$\mathcal{L}=L_{1},L_{2},$(finite thickness) をもっとは, 任意の文字列に対して, $\#\{L\in L|w\in L\}$ が有限であることを$w\in\Sigma^{+}$

いう.
有限の厚さよりもっと–般的な十分条件が, Wright
によってもたらされた (cf.
$\mathrm{a}1.[8])$が帰納的言語の添字付き
族 (indexed family of recursive languages) であると
言語族

$L$

$\cdots$

は, 次のような計算可能関数 $f$ : $N\cross\Sigma^{*}arrow\{0,1\}$が存在することをいう: $f(i,w)=1$ , if $w\in L_{i};0$ , if
. ここで, 添字 は言語を定義するオートマ
トンや形式文法等を意味すると考えられるが, 本稿
やパターン上の決定木等を意味する.
ではパタ

. 言語族

$\mathcal{L}$$\mathrm{W}\mathrm{r}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}[12]$, Motoki etが有限の弾力性 (finite elastic-ity) をもっとは, 次の条件を満たす文字列の無限列
がと言語の無限列
存在しないことをいう: 任意の $k\in N$ に対して,$w_{0},w_{1},$(1)$L_{1},L_{2},$ $\cdots\in \mathcal{L}$$\cdots\in\Sigma^{*}$$\{w_{0},w_{1}, \cdots,w_{k}-1\}\subseteq L_{k}$,(2)$w_{k}\not\in L_{k}$.

$i$$w\not\in L_{:}$$-\sqrt[\backslash ]{}$

推論機械 $M$ とは, 次々に入力を要求し, 次々に出力を生成する実行的な手続きのことであり, $M$ が生成する出力を推測と呼ぶ. 文字列の無限列 に対し$\sigma$

Wright は, 有限の弾力性が正例から推論可能であるための十分条件であるだけでなく, この性質が言語族の和演算また,$\cup\sim$に関して閉じていることを示した.
は, この性質が言語族の$\mathrm{M}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{y}\partial m\partial\ \mathrm{S}\mathrm{a}\mathrm{t}_{0}[7]$積演算凸や連接演算等に関しても閉じていることを113示した. ここでは, 本稿に関連する次の 2 つの族演

算のみ記載する:$\mathcal{L}_{1}\overline{\cup}\mathcal{L}_{2}=\{L1\cup L_{2}|L_{1}\in L_{1}, L_{2}\in \mathcal{L}_{2}\}$,$\mathcal{L}_{1^{\tilde{\cap}}}\mathcal{L}2=\{L_{1^{\cap L_{2}}}|L_{1}\in \mathcal{L}_{1}, L_{2}\in L_{2}\}$.

言語族 $L$ と正整数回の積演算凸または和演算して得られる言語族をで表す.

る言語に高々$\cup\sim$$n$$\mathcal{P}\mathcal{L}=\{L(p)|p\in \mathcal{P}\}$

で表すこと

パターン上の決定木とは, 葉の各ノードが

$0$

また

は 1 の, 葉ではない各ノードがパターンのラベルをもつ決定木である. 深さが高々 $n\in N$ であるパに対して, 言語族に含まれ$n$ターン言語の族をにする.

を施$\mathcal{L}(n)$定理 21(Moriyama&Sato[7]). 言語族
が有限の弾力性をもつならば, 言語興 $L(n)$ も有限の弾力性をもつ.
$\mathrm{W}\mathrm{r}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}[12],$$\mathcal{L}$

ターン上の決定木の全体を TP、で表す. 与えられた文字列 $w\in\Sigma^{*}$ に対して, パターン
をラベル
$P$

としてもつノードでは, $w$ がそのパターン言語 $L(p)$に属するか否かがテストされ, その結果 (yes または no) により左または右に分岐していく. パタ一ン上の決定木 $T$ に対して, 1 のラベルをもつ葉のノードに至る文字列の集合を決定木 $T$ によって定義される言語といい, $L(T)$ で表す. また, 言語族

有限の弾力性は, 言語族の通常の和演算 に関しては閉じているが, 補演算に関しては必ずしも閉じ$T$ていないことが示される (cf. Moriyama&Sato[7]).

定義されるされる言語は,$\cup$

3. 正例からのパターン上の決定木の$\mathcal{T}\mathcal{P}\mathcal{L}_{n}=\{L(T)|T\in \mathcal{T}\mathcal{P}_{n}\}$とする. 図 1 の決定木

は, 深さ 2 の決定木である. そして,

$T$

によって

$L(T)=(L(xal_{\Psi})\cap L(aXbby)^{c})\cup(L(xaby)C\cap L(xayb))$

である.

帰納推論
を少なくとも 2 個以上の文字を含むアルファ
ベットとし, $X$ をと互いに素な可算集合とする.
$\Sigma$$\Sigma$$\Sigma,$$X$の要素をそれぞれ定数 (記号), 変数 (記号) とよぶ.

パターンとは,パターン $p$ の長さを合を$\mathcal{P}$

上の空でない文字列である.

$\Sigma\cup X$$|p|$で表し, パターン全体の集で表す. 代入とは, すべての定数をそれ自身に写すパターンからパターンへの準同型写像のこととする. 代入 によるパターン の像をで表す. 本稿では, 代入として, 非消去代入, すなわち,$\theta$$p\theta$$p$に制限して考える.
パタ一に対して, $p=q\theta$ となる代入 が存は在するとき,の応化 ( は の塩化) といい,と表す. 明らかに,ならば, $|p|\geq|q|$ である. パターン が生成する言語 $L(p)$ を,$|x\theta|\geq 1(x\in X)$$\sqrt[\backslash ]{}p,$を満たす代入図 1: パターン上の決定木の例$\theta$

この例でわかるように, パターン $P1,P2,$ $\cdots,pn$ を$\theta$

$q$

$P$

$q$

$p\preceq q$

$q$

$P$

$P\preceq q$$P$

ラベルにもつノードを経由して, 1 のラベルをもつ
葉のノードで受理される言語は,
またはその
の
補言語
についての共通部分であり,は決定木の深さを越えない. そして, $L(T)$ は, そのような言語の集合和である. いま, 言語族
とおくと, 言語族
は,$L(n)$ の部分族である. ただし, $n=d2^{d-1}$ とする.
もし,が正例から推論可能ならば, その部分族であるも丁丁から推論可能となる. 本稿では, 正忌からパターン上の決定木を帰納推論する問
題を考える. まず, パターン言語の補言語の問題か
らはじめよう.
$L(p_{*}.)$$L(p_{i})^{\mathrm{C}}$$i$$\mathcal{L}=$$L(p)=\{w\in\Sigma^{+}|\exists\theta \mathrm{s}.\mathrm{t}.w=p\theta\}$$\mathcal{P}\mathcal{L}\cup\{L(p)^{c}|p\in \mathcal{P}\}$と定義する. 明らかに, $w\in L(p)$ ならば,$||p|\leq|w|$となる. 言語 $L$ を生成するパターンが存在するとき,はパターン言語と呼ばれる. パターン言語の所属問
題は, 計算可能であるが
完全である
また,
ならば, $L(p)\subseteq L(q)$ であるが, しか$L$$\mathrm{N}\mathrm{P}$$(\mathrm{A}\mathrm{n}\mathrm{g}\mathrm{l}\mathrm{u}\mathrm{i}\mathrm{n}[1])$.

$p\preceq q$

し, その逆は–般には成り立たない$n$$(\mathrm{A}\mathrm{n}\mathrm{g}\mathrm{l}\mathrm{u}\mathrm{i}\mathrm{n}[1])$.パ$\mathcal{L}(n)$$\mathcal{T}\mathcal{P}\mathcal{L}_{d}$$\mathcal{T}\mathcal{P}\mathcal{L}_{d}$114

明らかに, どんなパターン

言語$L(p)^{c}$$P$に対しても, その補はパターン言語とはならない. ここでは,の co-パターンと呼ばれ
に対して,
各パターン
を導入する. C\sim パターン全体の集合をる文字列とおく. 新しい記号で表し,の意味 (言語) をどう解釈す列である co–パターン
$P$

$P$

$P^{c}$$J\mathcal{P}=\mathcal{P}\mathrm{U}\mathrm{c}\mathrm{o}-\mathcal{P}$$\mathrm{c}\mathrm{o}-\mathcal{P}$$p^{c}$

るか. 以下, co–パターン$p^{c}$の意味を補言語 $L(p)^{c}$のある部分集合として定義し, パターンの意味と同じ記号 $L$ を用いて $L(p^{c})$ で表す. C\sim パターンの言
と
とし,
語の全体を
$J\mathcal{P}L=\mathcal{P}c\cup \mathrm{C}\mathrm{O}-\mathcal{P}c$$\mathrm{c}\mathrm{e}\succ p\mathcal{L}$おく.

定理 32. 言語族

は有限の厚さをもつ.

さて, co-パターンの意味を上記のように与えた場合の, パターン上の決定木 $T$ で定義される言語の新しい意味 $L(T)$ を次のように与える. 任意の文の入力に対して各ノードのラベルにあるパ字列$w$

ターン $P$ と照合し,$w\not\in L(p)\cup L(P^{\mathrm{C}})$あるいは$w\in L(p),$ $w\in L(p^{c})$かに応じ, 左, 右への分岐あるいは停止の 3 つの選択肢がある. 停止は, $w\not\in L(T)$ を意味するものとする. 停止となるのは, $|w|<|p|-k$となる文字列であり, またそれらに限られる. したがって, パタ一 上の決定木 $T$ に対して, 途中で停$\sqrt[\backslash ]{}$

止に陥る文字列の個数は高々有限個である. このような決定木の新しい意味 の下で, 深さが高々 の

3.1. co-パターンの補言語としての解釈$P$$L(p^{\mathrm{c}})=L(p)^{\mathrm{c}}(=\Sigma^{*}\backslash L(p))$$\mathrm{c}\mathrm{e}\succ \mathcal{P}\mathcal{L}$$\cdots$$\cdots$

限の弾力性をもたないことの例となる. しかしながら, この言語族は, 新例から推論可能となることが,による 「パターン言語族は, 負例から$\mathrm{S}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{o}\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{a}[11]$$J\mathcal{P}\mathcal{L}(=\mathcal{T}\mathcal{P}\mathcal{L}_{1})$決定木で定義される言語の族をあらためてで表す.
正例からの決定木の推論に関しては次の定理がな
りたつ.
定理 33. 任意の $n\in N$ に対して, 言語族$J\mathcal{P}\mathcal{L}(n)$,はいずれも有限の弾力性をもつ. したがって,
これらの言語族は正例から推論可能である.

$\mathcal{T}\mathcal{P}\mathcal{L}_{n}$以下, 言語族$\mathcal{T}\mathcal{P}\mathcal{L}_{d}$の基本となる言語族$J\mathcal{P}L$の$P$$S_{\mathrm{p}}=\{w\in L(p)||w|\leq|p|+k\}$

は正例から

,

$S_{p^{\mathrm{c}}}=\{w\in L(p^{c})||w|\leq|p|\}$

推論可能である.

(ii) 言語族$\mathcal{T}\mathcal{P}L_{d}$有限証拠集合について論じる.
パターン
に対して,

推論可能である」 という結果から直ちに導ける.
この解釈の下で次の結果が得られる.
定理 31. (i) 言語族

$d$

$L$

に対して, その co-パターンの意
各パターン
と解釈
味を補言語
は有限の弾力性もする. このとき, 言語族
もたない. 実際, 長さが単調に増加する文字列の無および CO-パターン言語の無限限列 $a,aa,$ $aaa,$$L(aaaa^{c}),$$L(aa^{c}),L(aaa^{c}),$はこの言語族が有列$\mathcal{T}\mathcal{P}\mathcal{L}_{2}$は論評から推論可能ではない.

と定義する.

この定理から, CO-パターンの意味を補言語と解釈

定理 34. 言語族

すると, $n>1$ に対して, パターン上の深さが高々それぞれ $L(p),$$n$$J\mathcal{P}L$$J\mathcal{P}\mathcal{L}$$L(P^{\mathrm{C}})$において, 集合

$S_{\mathrm{p}},$$S_{\mathrm{P}^{\text{。}}は}$の有限証拠集合である.

である決定木は正例から推論可能ではないことに

なる.

注)

$\mathrm{c}\mathrm{o}$-パターン$p^{c}$の解釈を $L(p^{c})=\Sigma^{+}\backslash L(p)$とすると, 上記の定理の証明と同様にして,$\mathcal{T}\mathcal{P}\mathcal{L}_{1}$が正例から推論可能ではないことが示される.

32. 有限の厚さをもつ
ここでは,$\mathrm{c}\mathrm{o}$パターン$P^{c}$

4. 正則パターン上の決定木
本節では, 正則パタ一の意味として, 次のよが高々1 回しか現れないパターンをいう. 正則パターンで定義される言語は正則パターン言語と呼ばれる.
正則パターンの全体および正則パターン言語の全体およびで表すことにする.
をそれぞれ,$\mathcal{R}\mathcal{P}$

うな $L(p)^{c}$ の部分集合を考える:

は任意に固定された非負整数とする.
の定義から, 以下の結果が成り立つ.
ただし,

$k$

上の決定木で定義される言語について考察する. 正則パターンとは, 各変数$\dot{\mathcal{J}}\mathcal{P}L$$L(p^{c})= \{w\in L(p)^{\mathrm{c}}||w|\geq\max(1, |p|-k)\}$$\sqrt[\backslash ]{}$.

$\mathcal{R}\mathcal{P}\mathcal{L}$4.1. 正則パターン上の決定木の帰納推論
こ

正則パターンに関しては, 次の結果が得られてい
る.

115

定理 41(.ouchi[9]). . 正則パダー$\mathrm{S}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{o}\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{a}[10],\dot{\mathrm{M}}\mathrm{u}\mathrm{k}$における所属問題は, 多項式時(i) 言語族
間で計算可能である.
ならば, 任意の正則パターン $p,q$ に$p\preceq
q\Leftrightarrow
L(p)\subseteq L(q)$ .
対して,$\mathcal{R}\mathcal{P}L$$(\ddot{\mathrm{n}})\#\Sigma\geq 3$

正則パターンの co-パターンからなる族をとし,$J\mathcal{R}P=\mathcal{R}p_{\cup}\mathrm{c}\infty \mathcal{R}p$

出力: 言語の添字の無限列 $g1,$$g_{2},$$\cdots$;begin

ン言語に関して, 次の性質が成り立つ:$\mathrm{c}\mathrm{o}-\mathcal{R}\mathcal{P}$とする. 本節では, 有限の厚さを持つことが示せた 32 節の C\sim 正則パターンの解釈に従う. また, ここでは特に, $k=0$ の場
合について論じる. すなわち, 正則パターン に対
$P$

して,

; go $:=-1$ ; $n:=1$ ;repeatread the next data $w_{n};S:=S\cup\{w_{n}\}$ ;ifthenelse $g_{n}:=g_{n-1}$ ;output ; $n:=n+1$
foreverend.
$S:=\emptyset$$w_{n}\not\in L_{g_{\mathrm{n}-1}}$$g_{n}:=\mathrm{M}\mathrm{I}\mathrm{N}\mathrm{L}_{\mathcal{L}}(S)$$g_{n}$

定理 43$\mathcal{R}\mathcal{P}\mathcal{L}$$(\mathrm{s}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{o}\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{a}[10])$.

正則パターン言語族

において, 文字列の空でない有限集合$S\subseteq\Sigma^{+}$の極小言語を生成する正則パターンを $O(l^{2}m)$ の時間で計算する手続き MINL が存在する. ただし,$l= \max\{|w||w\in S\},$ $m=\# S$ とする.

$L(p^{c})=\{w\in L(p)^{C}||w|\geq|p|\}$

この解釈の下で,$\mathcal{R}P\},$$=$$\mathrm{c}\mathrm{o}- \mathcal{R}\mathcal{P}\mathcal{L}$$J\mathcal{R}\mathcal{P}\mathcal{L}=\mathcal{R}\mathcal{P}L\mathrm{U}\mathrm{c}\mathrm{o}- \mathcal{R}\mathcal{P}\mathcal{L}$.

$\{L(p^{c})$c\infty -正則パターンの言語族において, 極小言語の
$|$

$p$

$\in$

とおく. 前節の結果は, 正則パターンに対してもなりたつ.

co–パターン言語の定義から明らかに, $L(p)\subseteq L(q)$ならば,であるが, 逆は成り立たない. しかし, 次の条件の下では, この不等式が成り

C\sim パターンを計算する手続きを次に与える. ここので, 正則パターン
番目の位置にある記号が定
数 $a\in\Sigma$ であるとき, その定数を変数と置き換えて得られる正則パターン を $q=p[X\succ(j,a)]$ で表す. したがって, $q\{x:=a\}=p$ が成り立つ.
$i$

$P$

$x$

$q$

$L(q^{c})\subseteq L(p^{\mathrm{c}})$Procedure co-MINL
入力: 文字列の空でない有限集合
出力:-正則パターン;立つ.

$S\subseteq\Sigma^{+}$;$\mathrm{c}\mathrm{o}$補題 42. 正則パターン $p,$
かつ

$L(P^{\mathrm{C}})\subseteq L(q^{c})$

$q$

に対して,

ならば,

$|p|\geq|q|$$L(P^{C})\neq\phi$

である.

begin
let
if

be the length of shortest strings in ;then begin
let $a_{1}a_{2}\cdots a_{n}(a:\in\Sigma)$ be an arbitrary
string not in ;$p_{1}:=a_{1}a_{2}\cdots a_{n}$ ;for $i:=1$ to do begin$q:=p_{i}$ [$-(i, )];
$S$$n$$\Sigma^{n}\Subset S$$S$

4.2. 深さ 1 の決定木の効率的な学習アルゴ
リズム

$n$

$x_{i}$

本節では, 正例からの正則パターン上の深さ 1 の決定木の効率的な学習アルゴリズムについて考察する. 深さ 1 の決定木は, 正則パターンかあるいは co正則パターンである.
一般に, 有限の弾力性をもつ言語族
において,文字列の有限集合を含む極小言語の 1 つを見つける問題が計算可能ならば, 次のアルゴリズムはに含まれる目標言語を推論することが知られている (cf. Arimura et). ここで, MINLc $(S)$は,の言語族 における極小言語の添字を計算すならば,る手続きを表す. すなわち,
はを含み, かつ,を満たす添字$i\in N$ は存在しない.

$S\subseteq L(q^{\mathrm{C}})$$p:=p_{n+}1$

end
else begin
let$\mathcal{L}$$\Sigma^{n-1}$$S$$p^{\mathrm{c}}$end$\mathcal{L}$$\mathrm{M}\mathrm{I}\mathrm{N}\mathrm{L}_{\mathcal{L}}(s)=i$$L_{i}$$p:=b_{1}b_{2}\cdots b_{n-}1$

end;
output$\mathcal{L}$$\mathrm{a}1.[4]$be an arbitrary;
string in$b_{1}b_{2}.\cdots b_{n-1}$$S\subseteq\Sigma^{+}$$\mathrm{I}\mathrm{A}$$a_{i}$

ifthen $p_{i+1}:=q$else $p_{i+1}:=p$:
end;

$S$

$S\subseteq L_{j}\subseteq L_{i}$する手続き co-MINL の出力をは$\mathrm{c}\mathrm{c}\succ \mathcal{R}\mathcal{P}\mathcal{L}$$p^{\mathrm{c}}$$w_{1},$ $w_{2},$$\cdots$;

して,$S\subseteq\Sigma^{+}$

とすると,

に対

$L(p^{\mathrm{C}})$における $S$ の極小言語である.

補題 45. 文字列の空でない有限集合

Algorithm IA
入力: 文字列の無限列

補題 44. 文字列の空でない有限集合$\mathrm{c}\sim \mathrm{M}\mathrm{I}\mathrm{N}\mathrm{L}(S)$は,$O(l^{2}m)$$S\subseteq\Sigma^{+}$に対の時間で計算可能116である. ただし,$\iota=\mathrm{m}\partial i\mathrm{X}\{|w||w\in S\},$$m=\# S$とする.

手続き co–MINL は, 入力された有限集合の中で探索した. 以下,
小言語を$\mathrm{c}\triangleright \mathcal{R}\mathcal{P}\mathcal{L}$

$S$

の極

$J\mathcal{R}\mathcal{P}L$における $S$ の極小言語を探索し, その記述である正則パターンまたは co-正則パターンを出力する手続

きを与える.
定理 46.

[4] H. Arimura, T. Shinohara and S. Otsuki, Finding minimal generalizations of pattern languages and its application to inductive inference from positive data, in Proceedings of the
11th Symposium on Theoretical Aspects Computer Science, Lecture Notes in Computer Science, 775 (1994) 646-660.
[5]$\#\Sigma\geq 3$とする. 文字列の空でない有限集に対する次の手続きの出力 JMINL $(S)$とすると, 言語 $L(\pi)$ は言語族

合$S\subseteq\Sigma^{+}$

を$\pi\in J\mathcal{R}\mathcal{P}$$J\mathcal{R}\mathcal{P}\mathcal{L}$における $S$ の極小言語である.

Procedur JMINL$e$

入力: 文字列の空でない有限集合;
出力: 正則パターンまたは -正則パターン;$S\subseteq\Sigma^{+}$$\mathrm{E}.\mathrm{M}$. Gold, Language identification in thelimit, Information and Control, 10 (1967) 447-

474.
[6] S. Miyano, Learning theory towords Genome
Informatics, in Proceedings of the 4th Workshop on Algorithmic Learning Theory, Lecture
Notes in Artificial Intelligence, 744 (1993) 1936.

$\mathrm{c}\mathrm{o}$

begin
let
if

be the length of shortest strings in ;then $p:=x_{1}x_{2n}\ldots X$ else begin;
if $p=x_{1}x_{2n}\ldots X$ then
$S$

$n$

$\Sigma^{n}\subseteq S$$p:=\mathrm{M}\mathrm{I}\mathrm{N}\mathrm{L}(S)$$p:=\mathrm{c}\mathrm{o}- \mathrm{M}\mathrm{I}\mathrm{N}\mathrm{L}(S)$endend
定理 46 より, 次の結果が得られる.
定理 47.

$\#\Sigma\geq 3$とする. 正則パターン上の深さ 1の決定木は, 旧例から多項式時間の更新で推論可能
である.

参考文献
[1] D. Angluin, Finding pattems common to a set, in Proceedings of the 11th AnnualofSymposium on Theory of Computing, (1979)$st_{\dot{\mathcal{H}}n_{\mathit{9}}}S$

130-141.
[2] D. Angluin, Inductive inference of formal languages from positive data, Information andControl, 45 (1980) 117-135.

[3] S. Arikawa, S. Kuhara, S. Miyano, Y. Mukouchi, Y. Shinohara, and T. Shinihara, A machine discovery from amino acid sequences bydecision trees over regular patterns, New Generation Computing, 11 $(3,4)$ (1993) 361-375.
$\cdot$[7] T. Moriyama and M. Sato, Properties oflanguage classes with finite elasticity, IEICE
Transactions on Information and Systems,(1995) 532-538.
$\mathrm{E}78-\mathrm{D}(5)$[8] T. Motoki and T. Shinohara, The correct definition of finite elasticity: corrigendum to identification of unions, in Proceedings of the 4th
Annual ACM Workshop on Computational
Learning Theory, (1991) 375-375.

[9] Y. Mukouchi, Characterization of pattem languages, in Proceedings of the 2nd Workshop on
Alogrithmic Learning Theory, (1991) 93-104.
[10] T. Shinohara, Polynomial time inference ofpattem languages and its applications, in Preceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science,(1982) 191-209.

[11] T. Shinohara, Inductive inference from negative data, Buletine of Informatics and Cybernetics $21(3,4)$ (1985) 67-70.

[12] K. Wright, Identification of unions of language
drawn from an identifiable dass, in Proceedings of the 2nd Workshop on Computational
Learning Theory, (1989) 328-333.