🚀 go-pugleaf

東工大の柴山です。
御近所の方のようなので，ちょっとだけ返事します。

Takeshi Yanagisawa wrote:

> 記号列から言語構造を見出すようなアルゴリズム，というのはどうなって
> いるのかな，という興味をもっています．
> 
> 記号列だけが与えられて，その生成規則（文法）は与えられていないとします．
> 例えば簡単な例で，記号列
> 0101010101
> が与えられたとします．
> これならとりあえず正規集合 {(01)*} だろう，と結論していいと思いますが，
> このような，入力から言語（文法）を見出すという処理は，
> もっと一般的な場合にも可能なのでしょうか．

ある言語の要素を１個だけ入力として与え，その言語を推定するという問題で
すか？
それは，無茶ですよ。
上の例なら，{ 0101010101 } という言語が条件を満たすわけですから。

以下では，L をある未知の言語とします。
L を次のような設定のもとで推定する研究なら以前に行われていたのを何となく
知っています。

・L に属する記号列を次々に入力として与える。
・L に属する記号列と属さない記号列を次々に入力として与える。
  もちろん，各記号列が L に属するかどうかという情報も同時に与える。
・任意の記号列に対して，その記号列が L に属するかどうかを教えてくれるオ
ラ
  クルを使って良いことにする。

> このようなことに興味をもっているのですが，文献等を紹介していただけないで
> しょうか．よろしくお願いします．

今から15年前の ACM Computing Surveys に D. Angluin が Inductive
Inference 
のサーベイを書いていた記憶がかすかに残っていたので，ちらっと見てみまし
た。
Information and Computation （昔は Information and Control）あたりの昔の
論
文に基礎的かつ理論的な結果は出ているような気がします（すいません，ちゃん
と
は見ていません）。

ともかく，この分野は専門ではないし，詳しいことは知りません。
最近はどうなっているのでしょうね？
近頃，Inductive Logic Programming なんてキーワードならよく聞くのですが，
Inductive Inference とか Language Identification なんて話は全然聞かなく
なってしまいました。

-- 
東京工業大学 情報理工学研究科
柴山悦哉