最近,深層学習にはまっていて,論文 Li et al., Building Program Vector Representations for Deep Learning, CoRR abs/1409.3358, 2014 を読んだので,内容を忘れないようにメモしておく. この論文では,プログラムの構文木を表現するためのベクトルの構築の仕方を提案している. ニューラルネットワークなどの多くの機械学習のアルゴリズムは, 何でもかんでもベクトルで表現されていることを前提にしているので, 構文木もベクトルに変換しないと,話にならない. 自然言語処理では,この手の研究は多いけど,プログラミング言語用の方法が無いので, 新しく作りましょう,というのがこの論文のモチベーション. 実際に,提案手法でプログラムのベクトル表現を構築した上で, online Open Judge から適当にダウンロードしてきたプログラムを深層学習でクラス分類すると, 深層学習を使わない従来手法よりも良い性能が得られ, 確率的勾配降下法の収束も改善されるらしい.

Recursive neural network

自然言語処理では,構文木の意味を表現するベクトルを得るために,recursive neural network (RNN) が使われる(recurrent neural network というよく似た名前のモデルがあるが,全くの別物). この論文でも,RNN により構文木を取り扱うことを前提としている.

RNN では,子を表現する特徴ベクトルを用いて,親を表現する特徴ベクトルを計算する, という処理を再帰的に繰り返すことで,根に対応する特徴ベクトル,すなわち,木全体を表現する特徴ベクトルを計算する. 例えば,42 + 123 * foo というプログラムを構文解析して,次の図の左のような構文木が得られたとしよう. この構文木を表現する特徴ベクトルは,右図のような RNN で計算される.

![RNN と構文木](/img/RNN-and-syntax-tree.png)

RNN の細かい計算はさておき,大雑把な動作を先に説明しておく. まず,葉に対応する特徴ベクトルが何らかの手段で予め得られているとしよう. すると,42*foo に対応する特徴ベクトルを基に,RNN が 42 * foo に対応する特徴ベクトルを作ってくれる. 次に,同じようにして,123+42 * foo に対応する特徴ベクトルを基に, 123 + 42 * foo に対応する特徴ベクトルを得ることができる. これが,構文木全体を表現するベクトルとなる. 親のベクトルは子のベクトルから計算されるので,子の情報を(ある程度)含んでいる. なので,直感的には,根のベクトルは構文木に含まれる全てのノードの情報を含んでいると考えられる. 最終的に求まった構文木の特徴ベクトルは,クラス分類とかクラスタリングとかに用いられる.

さて,RNN の具体的な計算について見てみよう.RNN の入力となる特徴ベクトルを $\bm{x} _1, \bm{x} _2, \dots, \bm{x} _M \in \Real^D$($M$ は子の数,$D$ は特徴ベクトルの次元)とおくと, 出力となる特徴ベクトルは

で与えられる.ここで,$\bm{W} _m \in \Real^{D \times D}$ は重み行列, $\bm{b} \in \Real^D$ はバイアス項,$f : \Real^D \to \Real^D$ は活性化関数である. この計算は,次のような模式図で表される.

![RNN のユニット](/img/RNN-unit.png)

基本的には,普通のニューラルネットと変わらないように思われるが, 子の数 $M$ がノードごとに異なるという,重大な違いがある. これは,パラメータ数(厳密には,重み行列の個数)がノードごと異なるということなので,学習アルゴリズムの設計が難しくなる. 自然言語処理では,強引に構文木を二分木に変換することで,$M = 2$ に固定して,この問題を回避している (正確には,文法をチョムスキー標準形に変換することで,構文木が必ず二分木になるようにしている). 今回の論文では,連続二分木 (continuous binary tree) という別な解決策を採用している. このアイディアは,単純に $\bm{W} _m$ を2つの重み行列 $\bm{W} _\mathrm{L}$,$\bm{W} _\mathrm{R}$ をブレンドして作る,というだけである.

混合比は次のように定義されている.左端に近い子ほど $\bm{W} _\mathrm{L}$ の割合が高くなり, 逆に右端に近い子ほど $\bm{W} _\mathrm{R}$ の割合が高くなるように,2つの重み行列を混ぜていることがわかる.

これで,子の数 $M$ に依らず,重み行列は $\bm{W} _\mathrm{L}$,$\bm{W} _\mathrm{R}$ だけになる.

モチベーション

論文で提案している手法には2つの目的がある.

  • 非終端記号に対応する特徴ベクトルの計算:そもそも,葉に対応する特徴ベクトルを予め求めておかないと, 先程説明した RNN の計算ができない.自然言語処理では,トークンやトークンを構成する文字をベースに, 特徴ベクトルを求めたりするけれど,プログラミング言語にそのアイディアを持ち込むのはあまり良くない. 例えば,C言語で double は型の名前だけど doubles は識別子(変数名や関数名), のように字面はよく似ていても1文字違うだけで,文法上全く違う要素になってしまうことも多いので, 文字単位で考えるのは良くない.また,トークン単位で考えるにしても,自然言語と違って, プログラマは自分の好きなように識別子を定義できるため,トークン数を無制限に増やすことができてしまう. おまけに,tmp のように,ごく稀にしか登場しないトークンもあるので,扱いにくい. そこで,この論文では,終端記号の情報を無視して,構文木中の非終端記号に対応する特徴ベクトルを計算する.
  • Unsupervised pretraining:この論文の方法では,1層の RNN を用いて,特徴ベクトルと重み行列, バイアスを一気に求めてしまう.特徴ベクトルは元々欲しかったものであるが,ついでに求まった重みとバイアスも無駄ではない. これらは,より深い RNN の訓練のための,パラメータの初期値として使うことができる. なので,この論文の手法は,単に特徴ベクトルを求めるだけでなく,unsupervised pretraining も兼ねている.

この論文では,1層の RNN を使って,全ての非終端記号 $s$ に対して,対応する特徴ベクトル $\mathbf{vec}(s) \in \Real^D$ を求める. まずは,構文木を次のように,親と子からなる部分木に分解して考える. 図の括弧内の数字は,そのノード以下に存在する葉の個数を表している(この値は後で使う).

![部分木への分解](/img/RNN-Li14-subtrees.png)

この場合は,分解した結果,2つの部分木 $t^{(1)} = (\mbox{BinaryOp}, \mbox{Const}, \mbox{BinaryOp})$, $t^{(2)} = (\mbox{BinaryOp}, \mbox{Const}, \mbox{Const})$ が得られる. 実際には,沢山のプログラムがあり,それらの構文木を分解するので,部分木はいっぱい得られる. この1つ1つの部分木が訓練事例である.

この部分木の親に対応する非終端記号を $p$,子に対応する非終端記号を $c_1, c_2, \dots, c_M$ とおく. これらの非終端記号に対応する特徴ベクトルは,それぞれ $\mathbf{vec}(p), \mathbf{vec}(c_1), \mathbf{vec}(c_2), \dots, \mathbf{vec}(c_M)$ である.子に対応する特徴ベクトルを RNN に入力すると,

という出力が得られる.ただし,$t = (p, c_1, c_2, \dots, c_M)$ は訓練事例,$\bm{W}_m$ は

で重み付けされている.この重み付けによって,葉の多いノードを重要視するようにしている.

基本的には,$\bm{y} \approx \mathbf{vec}(p)$ になって欲しい.より具体的には,

を最小化するような,パラメータ $\Theta = (\mathbf{vec}(\cdot), \bm{W} _\mathrm{L}, \bm{W} _\mathrm{R}, \bm{b})$ を求めたい.これを模式図で表すと,以下のようになる.

![Li et al., 2014 のモデル](/img/RNN-Li14-model.png)

しかし,安直に $d$ を最小化すると,自明な解 $\mathbf{vec}(\cdot) = \bm{0}$, $\bm{W} _\mathrm{L} = \bm{W} _\mathrm{R} = \bm{0}$, $\bm{b} = \bm{0}$ が求まってしまう. これは最小値 $d=0$ を与えるが,無意味な解である. 特徴ベクトルが全部ゼロでは,全然特徴を表していない!

Negative sampling

自明な解を避けるために,negative sampling を用いる. やり方は簡単で,以下の図のように,部分木 $t^{(i)}$ を構成する $p, c_1, c_2, \dots, c_M$ から, ランダムにノードを選び,それをランダムに選んだ別な非終端記号で置換することで,擬似負例 (negative sample) $t^{(i)} _-$ を作る(以降,正例 $t^{(i)}$ を $t^{(i)} _+$ と表記).

![Negative sampling](/img/RNN-negative-sampling.png)

擬似負例は訓練集合のパターンに違反するサンプルであるから,誤差 $d(t^{(i)} _-)$ は $d(t^{(i)} _+)$ より大きくなるべきである.実際には,マージン $\Delta$ を設けて, $d(t^{(i)} _-) \ge \Delta + d(t^{(i)} _+)$ にすることを目指す. したがって,誤差関数は次のようになる.

実際には,過学習を避けるために L2 正則化を加えて,

を確率的勾配降下法で最小化する.ただし,$M = 2D^2$ は $\bm{W} _\mathrm{L}$ と $\bm{W} _\mathrm{R}$ の要素数の合計であり,$\|\cdot\|^2 _F$ はフロベニウス・ノルムである.

訓練

論文では,訓練にはモーメンタムを使った確率的勾配降下法を用いている. パラメータ $\Theta = (\mathbf{vec}(\cdot), \bm{W} _\mathrm{L}, \bm{W} _\mathrm{R}, \bm{b})$ をランダムに初期化した上で,次の手順を収束するまで繰り返すことで,最適解を求める.

  1. 訓練事例 $t^{(i)} _+$ を訓練集合から取ってくる(復元抽出)
  2. $t^{(i)} _+$ から,擬似負例 $t^{(i)} _-$ を作る
  3. $\partial J^{(i)} / \partial \Theta$ を計算する
  4. $\Theta \gets \Theta - \eta \left( \partial J^{(i)} / \partial \Theta \right) - \epsilon \left( \partial J^{(i-1)} / \partial \Theta \right)$

$\partial J^{(i)} / \partial \Theta$ の計算方法については,後日紹介する予定.

この論文で使ったプログラムと訓練データは https://sites.google.com/site/learnrepresent からダウンロードできる. 論文に載っている式とは,少し違う式を計算しているが,それについても後日話すつもり.

実験

実験結果の詳細は論文を見てもらうとして,ここでは大雑把に概要だけ説明する.

この論文の方法では,構文木中で親子関係が似ている非終端記号には,似たような特徴ベクトルが割り当てられる. 実際に,得られた特徴ベクトルをクラスタリングしてみると, UnaryOp,FuncCall,Assignment,BinaryOp などの似たような使われ方をする非終端記号は,同じクラスタになる.

他にも,提案手法を pretraining として用いると,良い解が得られるという事を,既存手法などと比較して,色々アピールしている.