日曜日だが,
坪坂君の実験
で Google sparsehash はやはり結構速かったことが
わかったのに影響されて(?), 自製のHPYLMのコードを
Google sparsehash
で書き直してみることに。
というのは, もうすぐ公開する予定のプログラムで確率の計算がボトルネックに
なっているらしいことが分かったからですが..。
*1
実際のプログラムはうまく抽象化して書いてあったことが幸いして,
少し直すだけで対応完了。
- ngramの各ノードから子供へのポインタを探す部分
- 予測するngramのノードから, 予測したい語(CRPオブジェクト)へのポインタを探す 部分
の両方を sparse_hash/dense_hash にしてみました。
例えば, p(cake|mary eats a)の確率を予測したい場合, 木の根から
a→eats→mary の順にノードをたどり, たどり着いた 'mary eats a' のノードで
cake が何回出てきているか&そのテーブルの数は何個か, を知る必要がありますが,
どの検索もスパースなので, 何らかの形で効率的なデータ構造が必要になります。
というのが前置きで, 以下がその結果。
| Algorithm | Time | Memory |
|---|
| dense_hash_map | 33.48min | 209M |
| sparse_hash_map | 55.28min | 111M |
| splay tree | 57.13min | 76M |
上はかなり小さいデータ(京大コーパスから5000文)のもので, 毎日新聞2000年度全文
(約150万文)を突っ込んだメモリ使用量は, dense_hash_map で7.5G, splay tree で
4.0Gでした。ちなみに, ナイーブに ext/hash_map を使うと20G超えのようです。
ということで,
- メモリ効率ではスプレー木はやはり優秀 *2
- sparse_hash_map の速度はスプレー木と同程度
- dense_hash_map はスプレー木に比べてメモリを2倍弱使うが, 速度が2倍弱になる
というのがひとまずの結論のようです。
スプレー木は二分木なので O(logn) ですが, 意外と速かったなというか..。
今回は densehash を使うことにしましたが, ちなみにスプレー木は自己組織化二分木
なので, 計算が進むほど, 各ノードの持つ二分木の構造が最適化されて, どんどん計算
が速くなるという素敵仕様があったりします。
*1: ちなみに, この実装ではノードの検索は int のハッシュなので, ハッシュ関数の影響
はありません。
*2: これは, ngramの各ノードでそれぞれハッシュを持つという構造のせいで,
巨大なハッシュを一つだけ持つという場合は, Google sparsehashのメモリ効率は非常に
良いのだと思います。
というわけで, 公開しました。
潜在語言語モデル(LWLM)は, 各単語の裏に隠れた「潜在語」を教師なしで推定すること
のできる言語モデルです。
ソシュールの一般言語学講義を読んでいる方は, (論文の著者はそう書いていませんが)
これは, ソシュールの「範列」の計算的な表現だということがすぐにわかるかと思います。その意味でも, 非常に面白い(&恐らく, NLPの他のタスクにも役立つ)モデルです。
詳しくは,
先日のMCMC研究会のスライド
をご覧下さい。
EMNLP 2009の原論文
*1
では SRILM を使って近似的にやっているらしい(全ての可能な単語を考慮していないらしい)
ですが, ここでは本当に全て真面目にベイズ推定しています。C++で約4000行くらい。
プログラミングが長かった。。。。
技術的な話についてはまた後で書きますが, lwlm付属の Gibbs デコーダー(lwlm-decode)を
使うと, 次のような文
クリントン 政権 と の 政策 的 妥協 が 可能な 場合 でも 拒否 す べし 、 と の
同氏 の 主張 に 、 危ぐ を 抱く 党員 も いる 。
を, 次のように"デコード"することが可能です。(上のページに置いてある,
京大コーパスから学習したモデルを使用)
% ./lwlm-decode kyoto.test.txt model.kyoto/
latent ngram order = 3, alpha = 0.01
loading lexicon..
vocabulary = 39431
loading LM..
loading table..
reading kyoto.test.txt.. done.
decoding sentence 1/1..
sampling 100/100..done.
クリントン クリントン (1.000)
政権 大統領 (0.970) 政権 (0.030)
と と (1.000)
の の (0.990) いう (0.010)
政策 経済 (0.730) 積極 (0.270)
的 的な (1.000)
妥協 実現 (0.960) 言葉 (0.030) 対応 (0.010)
が が (1.000)
可能な できる (1.000)
場合 場合 (0.940) だけ (0.060)
でも でも (0.990) は (0.010)
拒否 実現 (0.920) 強調 (0.080)
す す (1.000)
べし べきだ (1.000)
、 、 (0.970) 」 (0.030)
と と (1.000)
の いう (0.730) の (0.250) する (0.020)
同氏 米国 (1.000)
の の (1.000)
主張 理由 (0.790) 責任 (0.210)
に に (0.950) は (0.030) が (0.010) から (0.010)
、 は (0.310) 、 (0.250) 対する (0.240) 大きな (0.140) も (0.040)
危ぐ 疑問 (0.900) 効果 (0.100)
を を (1.000)
抱く 持つ (1.000)
党員 国民 (0.890) 子供 (0.080) 人 (0.030)
も も (1.000)
いる いる (1.000)
。 。 (1.000)
出力フォーマット, burn-inの回数, 事後サンプルの個数等はもちろんカスタマイズ可能
です。
実は京大コーパスは非常に小さいデータなので, 単語-単語の翻訳確率を学習するには
足りず, 上のように綺麗にデコードできるとは限りませんので, そこだけ注意。
現在, もう少し大きなデータで学習させたデータを公開する予定です。
普通のその辺にあるテキストで動く教師なし学習ですので, 自分で学習すればもちろんOKです。
内部的には, 次のような潜在語(左側)―観測語(右側)の翻訳確率を推定し, これと
潜在語自体の前後関係 (n-gram)を使って, 与えられたテキストの裏にある潜在単語を推定して
翻訳確率をさらに書き換える, という動作を繰り返します。
上のページには書いていませんが,
"model/table" というファイルが学習した潜在単語-単語の翻訳確率のテーブルで,
付属の "view-table" というスクリプトを使うと,
確率の上位語をソートしてこのように表示できます。
使い方は view-table を単に実行するか, 中を見て下さい。
れた れる 0.3366297 1284
なった なる 0.2595481 569
的な 的 0.2590401 521
や 、 0.2353712 1783
開か 行わ 0.2195300 186
られる られた 0.2070375 275
午前 午後 0.2028879 179
せる せた 0.1956908 184
だ である 0.1885102 959
二 一 0.1796324 990
:
従業 公務 0.0813301 48
政権 内閣 0.0802100 86
機関 システム 0.0799848 78
宗教 特殊 0.0798486 50
べきだ べきである 0.0794294 80
いわ 呼ば 0.0792535 78
声 見方 0.0783010 91
求め 望み 0.0780744 46
夜 朝 0.0775319 57
上る 達した 0.0774548 54
現在, 学習速度(サンプリング速度)は高速化の結果, 最初100-400単語/秒くらいです
が, 学習を続けていくとどんどん速くなり, 京大コーパスの場合は最終的に数100sweep
が終わると, 6000単語/秒くらいになる模様です。謎。
連休中に学習させておいた毎日新聞と New York Times のモデルを
置いておきました。
ただ, 教師なし学習に共通することですが, (識別学習のように「ルール」を使うわけ
ではないので)適用したいドメインのテキストで直接学習した方が, 結果が良いよう
です。データが少ないと, nグラムのスパースさに引きずられて, 意味的というより
文法的な同意語が出てしまうようになる模様。
さて, 潜在語言語モデルは, NLPの立場からは観測値のnグラムをそのまま使うのでは
なく, 「真のnグラム」を推定して, そこから観測語が生まれたと考えるモデル
ですが, この学習は言うほど簡単ではありません。
各単語について数万次元(=語彙次元)の隠れ変数が存在するため, EMアルゴリズムで
Forward-Backwardを使おうとすると, 数億を超える組み合わせのテーブルを計算する
ことになってしまうため不可能で, Gibbsで局所的に潜在語をサンプリングして学習
していくことになります。
*1
ただしこの時も, ナイーブにはコーパスの各語に対して数万個ある潜在語候補の確率
を求める必要があり, 語彙が多いときわめて遅くなります。
実際, 上のコードで learn.cpp や decode.cpp の中にある slice_gibbs_draw()
を gibbs_draw() に変えると「サンプリングの耐えられない遅さ」
というどこかの小説のタイトルのような感じになりますので,
試してみると面白いかもしれません。
Slice sampling
この問題に対処するため, 上のコードでは, スライスサンプリングを使って確率的に
候補を減らしています。
スライスサンプリングは, 簡単に言うとNLPでよくある「閾値」を,
それ自体確率的にサンプリングすることで, 効率的かつ正確な学習を可能に
する方法です。
IBISの武井-牧野君の話ではBeam samplingとしてPCFGに適用していましたが, ここでは
動的計画法が実際上使えないので, 局所的なGibbsに使っています。
HPYLMの場合, nグラムが内部的には1グラム-2グラム-3グラムと樹構造になっています
が, スライスがPY過程の「バックオフ係数」にあたる
(θ+d*tu)/(θ+nu)より大きかった場合, 木を上にバックオフしてもスライスより確率の高い候補は
現れないため, 比較的効率的にサンプリングの候補を計算することができます。
..が, 実際やってみると, 特に名詞が来る位置で, 1グラムまでバックオフして
スライスを超える候補を見つける必要があることが多いことがわかりました。
1グラム(木のルート)には全ての単語が存在しているため, スライス s を超える確率
を持った単語を探すためには, ここで数万個の候補をなめる必要が生じてしまいます。
ユニグラムが頻度順に並んでいたりすれば枝刈りは容易ですが, LWLMではnグラム自体
がサンプリングされた潜在語によって動的に書き換わるため, そうした静的な性質は
期待できません。
record
このために, record という特別なデータ構造を用意することに。
岡野原君に相談したところ, ベクトルで順番に持って, 頻度が変更された時に書き換え
ればいいのではないかとのこと。(感謝。)
真面目に完全に頻度順にしようとすると, restaurant * が頻度順に
46 32 15 4 4 4 3 3 2 2 [2] 1 1 1 のように並んでいるベクトルで[2]->3になった時
に, 二分探索で最左の3を探し(数字を入れ換えるのではなくて,
restaurant * を入れ換える), swap()を実行すればいいですが,
単語の頻度は学習時にもの凄い勢いで増減するので, 二分探索とはいえ, ここ自体が
計算のボトルネックになってしまう可能性があります。
*2
よく考えると, 完全に単語が頻度順に並んでいる必要はなく, 枝刈りができる程度に
ソートされていればよいので, 少し考えて, 頻度が 2^n 以下になる境界だけを配列で
コンパクトに持つことに。
頻度が1増減する毎に, それが2^nになっているかどうか調べ
(これは二の補数表現を使うと, record.cpp の pow2() というトリッキーなコードで
高速に調べられます),
2^nになった/そこから減った場合は swap を行って境界の値を書き換えます。
さらにメタ関数 foreach を書いて, 2^n境界を使って頻度の高い順からアイテムに
関数ポインタで受け取った関数を実行する Lisp 的な関数を定義しました。
正直これを正しく, かつ美しく実装するのに3日かかりました。。(record.cpp)
効果は劇的で, ここまでやって初めて, 語彙の数にそれほど依存せずに高速な学習
ができるようになりました。長かった。。
最近, Phil Blunsomがslice samplingを使って Synchronous grammar の構文木を
サンプリングするという話を出しているようですが(NAACL 2010), 莫大な候補から
効率的にサンプリングするという意味では, 似たところがあるかもしれません。
-
ちなみに, 実はこのコードの売りは, HPYLMの完全な実装が含まれていることかも
しれません。
Songfang Huang
のページでは, (恐らく彼がIBMに援助されているという事情もあって)ソースは公開
されていないので, これが多分, 現在唯一の公開されているベイズnグラム(HPYLM)の
コードなのではないかと思います。
僕はNTTにいるので研究用のコードは公開できませんが, これは(実装に色々工夫が
あるとはいえ)他の人の研究なので, 公開できるという感じです。
*1: 下で書くスライスサンプリングを使うと候補の数を減らすことができるため, 一見
Forward-backwardができるように見えますが, たとえsliceを使った場合でも, 特に
様々な名詞が来る位置などで確率的に万を超える候補が出る場合があり, それが隣合う
(数百万語を超えるコーパスでは確率的には十分起こりうる)と, 同様に億や兆単位の
動的計画法を計算する必要が生じます。実際バイグラムまでは実装しましたが,
トライグラムを書いている時点でこのことに気付き, 諦めました。
*2: 数字の境界を別に持っておけば大丈夫ですが, 数百万個のnグラムノードでそれを
ナイーブに持つとメモリが破綻します。