mots quotidiens. | |
Daichi Mochihashi (持橋大地) daichi <at> ism.ac.jp | by hns, version 2.10-pl1. |
|
|||||||||||||||||||||||||||||||||||||||||||||||
実際のプログラムはうまく抽象化して書いてあったことが幸いして, 少し直すだけで対応完了。
というのが前置きで, 以下がその結果。
上はかなり小さいデータ(京大コーパスから5000文)のもので, 毎日新聞2000年度全文 (約150万文)を突っ込んだメモリ使用量は, dense_hash_map で7.5G, splay tree で 4.0Gでした。ちなみに, ナイーブに ext/hash_map を使うと20G超えのようです。
Algorithm Time Memory dense_hash_map 33.48min 209M sparse_hash_map 55.28min 111M splay tree 57.13min 76M
技術的な話についてはまた後で書きますが, 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の回数, 事後サンプルの個数等はもちろんカスタマイズ可能 です。
内部的には, 次のような潜在語(左側)―観測語(右側)の翻訳確率を推定し, これと
潜在語自体の前後関係 (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単語/秒くらいになる模様です。謎。
さて, 潜在語言語モデルは, NLPの立場からは観測値のnグラムをそのまま使うのでは
なく, 「真のnグラム」を推定して, そこから観測語が生まれたと考えるモデル
ですが, この学習は言うほど簡単ではありません。
各単語について数万次元(=語彙次元)の隠れ変数が存在するため, EMアルゴリズムで
Forward-Backwardを使おうとすると, 数億を超える組み合わせのテーブルを計算する
ことになってしまうため不可能で, Gibbsで局所的に潜在語をサンプリングして学習
していくことになります。
*1
ただしこの時も, ナイーブにはコーパスの各語に対して数万個ある潜在語候補の確率
を求める必要があり, 語彙が多いときわめて遅くなります。
実際, 上のコードで learn.cpp や decode.cpp の中にある slice_gibbs_draw()
を gibbs_draw() に変えると「サンプリングの耐えられない遅さ」
というどこかの小説のタイトルのような感じになりますので,
試してみると面白いかもしれません。
HPYLMの場合, nグラムが内部的には1グラム-2グラム-3グラムと樹構造になっています が, スライスがPY過程の「バックオフ係数」にあたる (θ+d*tu)/(θ+nu)より大きかった場合, 木を上にバックオフしてもスライスより確率の高い候補は 現れないため, 比較的効率的にサンプリングの候補を計算することができます。
..が, 実際やってみると, 特に名詞が来る位置で, 1グラムまでバックオフして
スライスを超える候補を見つける必要があることが多いことがわかりました。
1グラム(木のルート)には全ての単語が存在しているため, スライス s を超える確率
を持った単語を探すためには, ここで数万個の候補をなめる必要が生じてしまいます。
ユニグラムが頻度順に並んでいたりすれば枝刈りは容易ですが, LWLMではnグラム自体
がサンプリングされた潜在語によって動的に書き換わるため, そうした静的な性質は
期待できません。
よく考えると, 完全に単語が頻度順に並んでいる必要はなく, 枝刈りができる程度に
ソートされていればよいので, 少し考えて, 頻度が 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), 莫大な候補から
効率的にサンプリングするという意味では, 似たところがあるかもしれません。
タイトル一覧 |