高速と噂のfastTextの仕組み

８月中旬、facebookが公開したfastTextの仕組みを軽くまとめる。

fastTextができること

自然言語処理の範囲は広く、ものによってできるものは異なる。fastTextは、word2vecのような単語をベクトルにしたり、文章をクラス分けする（予め決まったクラスに分類する（複数クラスに入ることは可能））ことができる。ベクトル化するモデルはCBOWとskip-gramが使われている。クラス分けを行うときは、学習データに、それぞれの文章がどのクラスにあるかという教師データが必要となる。

fastTextを試す

githubに公開されているので、

git clone https://github.com/facebookresearch/fastText.git
cd fastText
make

でコンパイル（新しめのc++コンパイラが必要）。使い方の詳細はREADME.mdを参考にしてください。

サンプルとして複数のスクリプトが用意されている。しかし、巨大なデータがダウンロードされてしまうので、するなら、時間や十分なネットワーク環境があるときにしましょう。（classification-example.sh, classification-results.sh, word-vector-example.sh）

fastTextの特徴

まず速い。arxiv.org/abs/1607.01759v2では、他手法が何時間かかかっているところを数十秒で済んだとある。（もちろん、優れたCPUを用いている）

GPUを利用することが多い機械学習分野ではめずらしく、CPUで高性能を出している。階層的softmaxの利用などがGPUのメリットを減らしていると自分は考えてる。

githubに公開されているC++11で書かれたソースを見ると、標準ライブラリしか使っていないことも挙げられる。行列を扱う部分さえも実装されている。C++のライブラリに明るくなくとも理解でき、教育的といえる。

単語を推測するようなものは、つまるところ、多量のクラスがあるところに分類するという見方ができる。多量のクラスへの分類・学習に取り組んでいるとも理解できる。

モデル（言語部分）

モデルは以前からある有名なものを使っている（少し改良している）。
いずれも、単語もしくは単語の一部からなる配列を入力とし、それぞれの単語にベクトルを対応させ、それらの平均をとる。その平均ベクトルから、クラスや単語を予測する。（以下、平均ベクトルという言葉を乱用するが、ここで言っている平均ベクトルの意味である。）

CBOW

文章の中にある単語を前後の単語から推測するモデル。出力は文書のある位置にある単語。入力はその単語の前後の単語と、その単語の一部からなる配列。

skip-gram

ある単語から、その前後に出てくる単語を推測するモデル。入力はある位置にある単語とその一部からなる配列。出力はその前後に出てくる単語。もちろん、「前後に出てくる単語」というのは複数存在するので、学習時はそれぞれで学習する。

クラス分け

文章は単語の列だから、それを入力としてラベルを推測して出力する。ひとつの文章に複数のラベルがあってもよく、それぞれのラベルで学習を行う。

いずれも、見た目は異なるように見えるが、統一的に扱い、言語を扱う部分と推測・学習の方法を切り離している。

モデル（推測・学習）

平均ベクトルのから推測は、シンプルなsoftmax regression以外に、negative samplingと階層的softmaxがある。階層的softmaxに、比較として残り二つが付いている。

分類先のクラスが多数あるので、softmax regressionのように学習時に多数の項目を変更するモデルでは計算時間がかかる。

\mathrm{softmax}(x_1, \dots, x_n) = \left(
\frac{e^{x_1}}{\sum_{k=1}^n{e^{x_k}}}, \dots,
\frac{e^{x_n}}{\sum_{k=1}^n{e^{x_k}}}\right)

のように$x_1$から$x_n$までがすべての成分に現れるので、ひとつの成分を大きくするように学習させるだけでも、学習段階ですべての$x_1$から$x_n$に相当する部分を更新するような学習をすることになる。砕けた言い方をすれば、毎度毎度、関係のない項目も学習して更新しないといけない。

それに対し、negative samplingと階層的softmaxでは、学習に関わる部分は全体の一部だけで、その一部分を更新することができる仕組みになっている。

実際に計算するかはさておき、数学的には、平均ベクトルから、一度、線形写像を適用し、それぞれのモデルの非線形関数を適用する。単語等の配列からスタートすると、それらにベクトルを対応させ、平均を取り、線形・非線形の順に適用する。

別の理解の仕方もあり、慣れていればこちらの方が構造が分かりやすいと思う。単語等は、one-hotなベクトルにする。単語などの配列はその平均とする。それに線形写像を施す。（これにより上で平均ベクトルと呼んでいたものになる。）その後さらに線形写像を施す。そのご非線形関数を施す。二つの線形写像を学習でよりよいものにする。線形写像の合成は線形写像だから、数学的には無駄なことをしているようだが、途中の次元を比較的小さくしておけば計算効率があがる。

negative samplingも階層的softmaxも、平均ベクトルから線形写像をし、その後sigmoid関数を適用する。sigmoid関数は0から1の値を取る関数で、活性化関数としてよく使われるが、sigmoid関数を適用して得られる値はなんらかの確率と考え、真偽で答える質問に対しその確率で真だと答えていると解釈するのが、これらのモデルの理解に役立つ。

negative samplingも階層的softmaxも学習時にいくつかの質問を与えられ、それに正しく答えられるように学習するモデルである。

negative sampling

今回のモデルの出力はラベルもしくは単語の予想だった。本来なら、「〇〇という状況で予想されるラベル・単語は何か？」という質問に答えるというのが目的だが、これをゆるくして、「〇〇という状況で予想されるラベル・単語はXXであるか？」という質問に答えられるように学習させることにすり替える。漠然と「何か？」という質問だと、すべての答えについて検討する必要があるが、一つか少数の答えだけが正しそうかを検討するだけならその分、効果的になる可能性がある。

しかし、あまり意味のない質問だと、学習が進まないので、「XX」にあたるところには、答えとして用意されているラベル・単語を使うのは必須だろう。それだけだと常に答えが「真」になってしまうので、答えが「偽」になるような質問も要る。そのためにランダムに答えが「偽」になる質問をいくつか用意する。これらの質問で学習するというモデルになっている。

階層的softmax

negative samplingでは、あからさまに「偽」だろうというような質問も含めてランダムに学習される。もっと効果的で意味のある質問をして学習させる方がいいように思う。

質問で分岐するような二分木を使うと効果的ではないか、というのが階層的softmaxの意義である。スタート地点が二分木のrootにあり、分岐ごとに、「右に行きますか？左に行きますか？」と聞かれる。それに対して、「右に確率$p$で左に確率$1-p$で行きます」と答える。そのような設問を繰り返し末端まで行くと、それまでたどってきた分岐で答えて来た確率の積がその末端にたどり着く確率になる。末端はラベルや単語に相当するもので、この方法でそのラベル・単語が答えとなる確率が計算できる。

何らかのラベル・単語が答えとなる確率を計算するには、対応する葉（末端のこと）から逆にrootまでさかのぼる経路を調べて、その経路が採用される確率を調べればいい。学習の段階では、答えに対応する葉からさかのぼる経路だけについて学習すればいい。

二分木を利用した効果的なアルゴリズムというのは、機械学習ではあまり見かけなかったが、アルゴリズムの教科書には二分木は重要な位置を占めていると思う。そんな二分木が機械学習でも活躍するのではないかという期待が湧いてくるモデルだと思う。実際、答えとして有力なものトップK個を答えるという機能がついているが、heapを使ったり、途中で枝切りしたりと、古典的なアルゴリズムが登場している。

二分木や葉とラベル・単語の対応は機械学習をする前段階で構築される。効果的な二分木になるように、それぞれのラベル・単語の出現頻度に基づいてハフマン木を作りこれを使う。これにより、各分岐で右に行くべきものの数と左に行くべきものの数が近くなり、分岐点の存在意義が高くなる。

単語の扱い

単語はそのままでは無駄が多いのでIDをつけて管理する。単純に登録順や多いものから順にすることも考えられるが、それだと、単語からIDに変換するのに時間がかかる。そこで、ハッシュトリックという方法をとる。単語をバイト列として、数値の列にし、何らかの関数（ハッシュ）でそれを一つの値にする。それをIDにする。被った場合はその都度一つずつずらす。IDを探すときはハッシュを計算し、その結果から一つずつ目的の単語かをチェックして探す。（頭から探すよりは速い）

fastTextでは、単語だけでなく、その付加情報としてその単語の一部分（subword）を切り出す。これもハッシュトリックでIDをつけて管理する。ただし、subwordの長さによってはとても多くなるので、被っても気にしない。また、そのsubword自体は保存しない。これはずらしていないから、subwordから計算でIDが求まるからだ。（学習で得られたそのIDに対応させるベクトルは保存する。）

感想

木構造を利用する階層的softmaxによる効率的な学習で、よくあるDeep Learningと異なる構造がとても面白い。機械学習にはまずいいGPUが〜となるところに喧嘩を売るようなCPUで速いというアルゴリズムの登場で、「アルゴリズムより計算資材だ〜」という怠けた態度を咎められたように思う。