2015-11-13
\(\def\PAT{\mathrm{PAT}}\def\content{\mathrm{content}}\)
何の枠組みもなしに言語を学習するってのは難しすぎる
個々の言語を考える代わりに言語の族, 言語クラスを考える.
\[C = \{ L_1, L_2, \ldots \}\](実際には添字付きなものに限らない)
何はともあれ, 情報を提示されないと学習できない
Gold は Text , Informant の2つがあると考えた
現代語訳すると
紛らわしいので現代語を使います
言語 \(L\) の正提示とは, その言語に出現するテキストの (無限) 列のこと
\[w_1, w_2, \ldots\]この列には重複などがあってもいいが, 言語に含まれる任意のテキストはこの列のどこかではいつか必ず出現することを要請する. すなわち,
\[\forall v \in L, \exists i \in \mathbb{N}, w_i = v\]これは結構強い性質である.
気持ちとして, 正提示とは次のような状況に相当する. すなわち「子供が大人から常に正しいテキストを一つずつ聞く」
無限列を集合に変換する操作を \(\content\) と呼ぶことにする. 例えば \(\content \{ 0,1,2,\ldots \} = \mathbb N\) みたいに使う.
こうすると正提示で要求してる性質は, 正提示 \(I = ( w_1, w_2, \ldots )\) に対して
\[\content(I) = L\]だと書ける.
言語 \(L\) の完全提示とは, 何でもいいから任意のテキストの列であって, そのテキストが言語に含まれるかのラベル ( \(\mathrm{Bool} = \{0,1\}\) ) が付いているもの
\[(w_1, I_1), (w_2, I_2), \ldots\]そして完全提示の気持ちはこういうもの:
時刻 \(t\) における推論:
\[g_t = G(i_1, i_2, \ldots, i_t)\]\(g_t\) は特定の1つの言語を説明するもの, 或いは, 言語そのもの
原理的に有限個の情報からは学習できない, という言語クラスはいくらでもあるので極限を考える
\[g_t = G(i_1, i_2, \cdots, i_t)\]が極限 \(t \rightarrow \infty\) で同定してかつ正しい言語を指し示すことを 極限同定 という. 注意として, 学習者は「いつ自分は正しく言語を学習できたか」を知る必要はない.
Gold が提示した枠組みにおける 学習可能性 とは次のこと.
「ある言語クラス \(C\) が学習可能である」とは, 任意の言語 \(L \in C\) とその任意の情報提示 \(I\) について, ある guessing machine \(G\) を構成することができて \(I\) によって \(L\) を極限同定できること.
正規言語全体のクラスを考えるこれは完全提示によって学習可能であることが知られている. 正規言語とはオートマトン (或いは正規表現) に対応するからそれを復元出来れば良い. guessing machine \(G\) の出力はオートマトン \(g_t\)
ただしこれは完全提示を要求していて, したがって無限のテキストについてそれが言語に含まれるか (つまりオートマトンに受理されるか, 或いは正規表現にマッチするか) を神託する必要がある.
完全提示からオートマトンを復元してくれるツール libalf というものがある. これがまさに今欲しかった guessing machine である.
正提示だけからは正規言語のクラスは極限同定が不可能であることも知られている.
ちょいちょい「子供が学習するときは〜」という話が出るが, 実際はどうなのか
psycholinguist 曰く [McNeill, 1966] : 「子供が文法誤りをしたとき, それを指摘することは滅多にない」
つまり完全提示は仮定が強すぎて現実的には正提示しか無い. そしてその中でも人間は自然言語を学習することが出来る.
あり得る自然言語のクラスは, 無限言語を少なくともひとつは含み, 全ての有限言語を含むことはない (超有限ではない)
この人は正提示から学習可能な非自明な言語クラスを発見した. それが パターン言語 .
有限アルファベット \(\Sigma = \{ 0, 1, \cdots \}\) と 無限変数 \(X = \{ x_1, x_2, \cdots \}\) の列としてパターンは定義される.
\[\PAT = (\Sigma \cup X)^+\]パターンに対しては次の操作と関係が定義される.
代入 \([x_i/p]\) とは, パターン中に出現する 全ての 変数 \(x_i\) を 空でない パターン \(p\) に置き換える操作.
\[ \begin{align*} x_1 x_1 & \succeq \underline{x_2} ~ \underline{x_2} & [x_1/x_2] \\ & \succeq \underline{a x_1} ~ \underline{a x_1} & [x_2/a x_1] \\ & \succeq a \underline{b c} a \underline{b c} & [x_1/b c] \\ \end{align*} \]ただし空は代入できないことに注意.
\[a x_1 a x_1 \not\succeq a a\]パターンに対応して言語を構成することが出来る. すなわち,
\[L(p) = \{ w \in \Sigma^* \mid w \preceq p \}.\](正規表現に対して正規言語があるようなもの.)
例えば,
\[L(x_1 x_1) = \{ w w \mid w \in \Sigma^+ \}\]パターン言語のクラス
\[C = \{ L(p) \mid p \in \PAT \}\]は正提示で学習可能.
学習ターゲットが \(L = L(p) \in C\) であって, その正提示として \(s_1, s_2, \cdots (s_i \in L)\) を受け取るとする.
推論機械は言語そのものの代わりにパターンを出力すればよい:
\[p_t = G(s_1 \cdots s_t)\]さて推論機械の構成方法であるが, それは大雑把に述べると
ってやると,
\[L = L(\lim_t p_t)\]になる.
言語クラスが有限の厚みを持つとは \(\iff\) 任意のテキストの有限集合 \(S\) について \(\{ L \mid S \subseteq L \}\) が有限であること
は収束する 1. 有限の厚みより, 正提示の1つ目を含む言語は有限個しかない 1. 推論も有限個しかない 1. 保守性より \(L(g_1) \subseteq L(g_2) \subseteq \cdots\) ( \(g_i\) に半順序がつく) 1. 推論列はどこかで停まるか, 極大を定める
パターン言語を消去可能パターン言語に拡張した. 消去可能であるとは空文字列の代入を許すこと.
例えば:
\[a x_1 a x_1 \succeq a a\]Shinohara は消去可能パターン言語であって正則なものは, 正提示から学習可能であることを示した.
N.B. パターン言語が正則 \(\iff\) 一つのパターンに出現する同じ変数 \(x_i\) は高々一つ (出現する変数が全て異なる)
パターンの和言語も正提示から学習可能であることを示した. 和言語とは, \(k\) 個のパターン \(p_1, p_2, \ldots, p_k\) について
\[L(p_1, \cdots, p_k) = L(p_1) \cup \cdots \cup L(p_k)\]と定められるもの. ただしこの個数 \(k\) について上限を設けたりする.
タイトルの通り
(一定の) 誤情報を含む正提示から学習可能
性質を調べたものであって, この場合の推論方法を示したわけでも学習可能性を言ったものでもない