形式的文法のChomsky階層とDeep Learning

機械は、「何」を理解できるのか？

機械は、「何」を理解・学習できるのか？　画像認識や自動運転技術のような、生物の感覚・運動系の能力の機械での対応物については、機械の能力の評価は、比較的容易である。

問題は、我々の認識能力が、具体的な感覚・運動系の能力にはとどまらないということ。人工知能研究の大きなターゲットの一つは、人間の言語能力である。この分野で、機械は、「何」を理解・学習できるようになったのだろうか？

機械は、「文法」を理解できるのか？

言語能力の領域には、「意味の理解」をはじめとして、未解明の問題がたくさんある。ここでは、問題を限定して、機械は、自然言語のものであれ、人工的に構成されたものであれ、言語の構文規則である「文法」を、理解できるのかという問題を考えてみよう。

おそらく、我々は、この問いに、肯定的に答えることができると、僕は考えている。

既に1990年代に、Hochreiterは、有限状態オートマトンで記述される構文規則を、 RNNが、理解・学習できることを発見していた。

2011年、 Ilya Sutskever らは、5億文字ものテキストをRNNに学習させ、学習したテキストに近い文体の文章を生成して見せた。文法にはかなっているように見えるが、意味をなさない文章だったが。ただ、意味をなさなかったにせよ、文法的には正しそうに見える文章を生成したことに注目できるということだと思う。

2015年、Andrej Karpathy は、Stack Theoryの膨大なドキュメントをRNNに学習させ、一見すると数学の論文に見える文書を生成してみせる。彼は、また、 Linuxの膨大なソースコードをRNNに学習させ、Cのコード（に見えるもの）を生成して見せた。これは、機械が、文脈自由文法であるLaTexやC言語の構文規則を、理解・学習できることを示すものだ。

2016年の、Googleニューラル機械翻訳は、これらの先行する機械の文法理解の能力に関する仕事を、さらに一歩進めるもののように、僕は考えている。

ここでは、こうした流れを振り返ってみよう。

驚くべきRNNの能力

Hochreiterの90年代の発見

LSTMの提案者であるHochreiterは、1990年代に、既に RNNが、極めて高い、認識能力を持つことを発見していた。LSTMの原論文 https://goo.gl/sDAq81に、詳細に、多数の実験結果が報告されている。ここでは、その中から、三つほどの例を紹介する。

一つは、有限オートマトンの生成する文字列の規則性を、LSTMが認識できるという実験結果である。これは、認知心理学の分野で、人間が持つ「人工的文法の学習（Artificial grammar learning）」https://goo.gl/VgvboK 能力として研究されていたものである。 　

もう一つは、LSTMが、掛け算を学習できるという実験である。ニューラルネットが、任意の関数の近似が可能であることは知られていたのだが、これはこれで興味ふかい実験である。

最後は、あるルールに従って、時間的に離れたところで起きるイベントのパターンを、LSTMが学習できるという実験である。これは、人間でも手こずりそうかもしれない。

いずれの実験も、膨大な学習の繰り返しが必要である。

Ilya Sutskever が生成した文章

2011年の論文、“Generating Text with Recurrent  Neural Networks” http://goo.gl/vHRHSn で、Ilyaたちは、文字数が5億文字にものぼるテキストを長い時間をかけてRecurrent Neural Nets に学習させ、次のような文章を生成することができた。

WikiPedia で学習したもの

The meaning of life is the tradition of the ancient human reproduction: it is less favorable to the good boy for when to remove her bigger. In the show’s agreement unanimously resurfaced. The wild pasteured with consistent street forests were incorporated by the 15th century BE. In 1996 the primary rapford undergoes an effort that the reserve conditioning, written into Jewish cities, sleepers to incorporate the .St Eurasia that activates the population. 

New York Timesで学習したもの

while he was giving attention to the second advantage of school building a 2-for-2 stool killed by the Cultures saddled with a halfsuit defending the Bharatiya Fernall ’s office . Ms . Claire Parters will also have a history temple for him to raise jobs until naked Prodiena to paint baseball partners , provided people to ride both of Manhattan in 1978 , but what was largely directed to China in 1946 , focusing on the trademark period is the sailboat yesterday and comments on whom they obtain overheard within the 120th anniversary , where ......

Andrej Karpathyが作り出した驚くべきサンプル

Andrej Karpathyの2015年のblog "The Unreasonable Effectiveness  of Recurrent Neural Networks” http://goo.gl/mNqwCv には、RNNが生成した、驚くべきサンプルが含まれている。それらを、紹介しよう。

マシンは、簡単な文法を理解できる！

これらの取り組みは、マシンが、例えば、C言語の構文や、LaTexの構文は、ほぼ完璧に学習していること示しており、興味深いものだ。マシンは、簡単な文法を学習できるのだ。

ただし、自然言語の生成では、いくつかの破綻が見られる。このことは、プログラム言語の文法規則が、基本的には「文脈自由文法（レベル2）」で、自然言語の文法規則である「文脈依存文法(レベル1)」よりも単純であることの表れとして理解できる。より単純な、有限オートマトンで表わされる「正規文法（レベル3）」の構造を、その出力から推定する問題が、膨大な計算を必要とするように、ここでは、膨大な計算が行われている。

もちろん、これらのアプローチの最大の問題は、文の「意味」を捉え損ねていることである。生成されたものには、文字通り「意味がない」のだ。ただ、そのことは、機械が文法を理解・学習しうるという発見の価値を傷つけるものではない。

文法の階層性 -- Chomsky Hierarchyについて

形式的言語の形式的文法は、次のような階層をなすことが知られている。これをChomsky Hierarchyと呼ぶ。

• タイプ-0 文法は、全ての形式文法を包含する。
• タイプ-1 文法は、文脈依存言語を生成する。
• タイプ-2 文法は、文脈自由言語を生成する。
• タイプ-3 文法は、正規言語を生成する。
  

機械が、この階層の中に位置付けられるどの形式的な文法を理解・学習できたかを考えることができる。

Hochreiterの仕事は、機械が、有限オートマトンで表現される正規文法を、理解・学習できることを示唆している。

Karpathyの仕事は、機械が、BNF(Backus-Naur Form)で表現されるような、Latex, プログラム言語の文脈自由文法を、理解・学習できることを、強く示唆している。

自然言語の文法は、この階層のどこに位置付けられるか？

問題は、自然言語の文法が、この階層のどこに位置付けられるかということである。

元の４階層の区分は、基本的だが粗いものである。Context-Freeな文法の中にも、LRやLLがあるように。

かつてのChomskyは、英語は Regular 文法ではないと明確に述べたが、それが Context-Freeであるかどうかは、明確には判断を下していないようにも見える。ただ、自然言語は、Context-Free性を満たさないというのが、大方の意見のように見える。それは、Context-Freeを超えた、Mildly Context-Sensitive な文法だという。（次の図の、赤い四角の部分）

現在のChomskyのMinimalist Programでは、自然言語の文法を、文法の階層の中に位置付けようとする問題意識は、あまりないようにも見える。ただ、Minimalist Programの中心的概念であるMergeについては、それがRecursiveであることが強調されている。Recursiveというのは、Recursive Enumerableの一部分で、決定可能なものである。（図の青い四角の部分）

Google翻訳が理解・学習した文法は？

おそらく、新しいGoogle翻訳が示しているのは、文脈依存文法の一部を、機械は理解・学習できるということなのだと、僕は、考えている。

方法論上の問題

機械が理解・学習できる文法のクラスを、Chomsky階層の中で位置付けようとする試みは、興味深いものだが、そこには、大きな方法論的な問題がある。

Hochreiterが、単純なRNNでは、有限オートマトンの生み出すRevere文法の認識が「できず」、LSTMなら、それが「できる」と主張したことを振り返ってみよう。

第一。ここでは、単純なRNNとLSTMという、二つの機械の能力が問題になっている。機械の構成の違いが、機械の能力の違いを生み出しているのは確かなのだが、我々は、二つの機械の出力をみてその能力を判断しているのであって、その機械の構成から、その能力の予測ができているわけではない。

Chomsky階層の各クラスの生成能力と相互の包含関係を、我々は、形式的に証明できるのだが、それぞれの機械の生成能力と相互の関係を、我々はきちんと把握できてはいない。Google翻訳のLSTM８段重ねｘ２の構成を、すごいとは思いつつ、どうすごいのかをうまく語れないのだ。（結果から見て、すごいとは言えるのだが）

第二。LSTMがRevere文法の認識が「できる」というのは、相当数の学習の後で、正解率がほぼ100%になるということであり、他の機械に、それが「できない」というのは、相当数の学習を繰り返しても、正解率が向上しないということである。それは、双方ともに、統計的・確率的な判断である。それは避け難いことだし、そのことの意味をよく考える必要がある。ただし、それは先に見たように、機械の構成で基本的には、規定されている。

相当数といったが、どのくらい学習を繰り返すべきかは、暗黙のうちに了解されている前提がある。それは、10年とかではない。（当たり前だ。でも、人間が一人前になるには、10年の経験が必要という分野だってあることはある。話が横道にそれたが、だから、「たくさんのGPUと膨大なデータと十分な学習時間があれば、精度をいくらでもあげられる」という無邪気な楽観論に、僕は、懐疑的だ。問題は、どんなマシンを作るかだ。）

第三。Hochreiterのマシンは、Revere文法を認識したというが、それは正規文法を認識したことにはならない。実際に示されたのは、正規文法の一部であるRevere文法の認識能力である。

僕は、LSTMは正規文法を認識できると考えているのだが、与えられたデータ（例えそれがいかに巨大なものであろうと）で学習したニューラル・ネットの能力を、その出力で判断するというアプローチを取る限り（それが、普通のディープラーニングのアプローチだ）、機械の能力をChomsky Hierarchyにマッピングすることは難しいだろう。現実に、不可能な網羅的な検証は、形式的・抽象的定義の飛翔に追いつくことはできないのだ。

正確に言えば、「Hochreiterのマシンで認識できない、Revere文法を満たす文は存在しないこと」を、我々は、証明してはいないのだ。

楽観的な展望

いろいろ、悲観的なことを書いたが、そこで終わっていると、気持ちが悪い。

例えば、正規文法を認識するニューラル・ネットを、スクラッチから構成することは、難しくはない。状態の遷移図を、そのままニューロンの役割に置き換えればいいはずだ。

問題は、例えば、LSTMが、その学習をつうじて、こうした回路を内部に、試行錯誤を通じて近似的に構成する能力を持つことを、きちんといえてないことだ。そのことは、経験的には当然のようにも思えるが、詳しい過程やその背後の理論構造を、僕は知らない。

そのことを明らかにできれば、文法の階層だけではなく、機械の構成の違いに基づく機械の階層について語ることができるだろう。