1週間ほど前に, 京大の Neubigさん から, FST上の教師なし単語分割ツール latticelm [LINK] の実装を公開した, との連絡をもらったので, 試してみました。

このツールは僕が前にやった教師なし形態素解析ができる他 (NTTではどうやっても 僕のコードは公開できないのですが), Neubigさん自身の研究 で, 音声認識結果の音素ラティスからの直接の言語モデル学習が可能なようです。
インストールには普通に OpenFST を configure; make してから, latticelm の ディレクトリでmakeを実行するだけ。以下は京大コーパスに対して実行してみた ものです。

sj205:~/work/neubig/latticelm% time ./latticelm -annealsteps 0 -unkn 5 -burnin 10 -samps 12 -prefix out.l/ data/kc.dat
Loaded 2899 symbols
Running on 37400 sequences
................................................................................................... 2971 seconds
Finished iteration 0 (Anneal=0), LM=1.04134e+07 (w=8.11355e+06, u=2.29982e+06), 
Lattice=9.55218e+06
 Vocabulary: w=90979, u=2898
 LM size: w=566638, u=275393
 WLM 1-gram, s=0.661334, d=0.697413
 WLM 2-gram, s=1.352, d=0.723324
 WLM 3-gram, s=1.34094, d=0.771464
 CLM 1-gram, s=2.03761, d=0.536038
 CLM 2-gram, s=1.2196, d=0.580531
 CLM 3-gram, s=1.25447, d=0.651926
 CLM 4-gram, s=1.26755, d=0.68593
 CLM 5-gram, s=1.27026, d=0.696291
................................................................................................... 3839 seconds

Finished iteration 12 (Anneal=1), LM=5.16363e+06 (w=4.90242e+06, u=261216), Lattice=5.04985e+06
 Vocabulary: w=23893, u=2898
 LM size: w=377347, u=78178
 WLM 1-gram, s=8.19583, d=0.716688
 :
 Printing sample for iteration 12
  Writing LM to out.l/ulm.12
  Writing LM to out.l/wlm.12
  Writing samples to out.l/samp.12
  Writing symbols to out.l/sym.12
./latticelm -annealsteps 0 -unkn 5 -burnin 10 -samps 12 -prefix out.l/   27231.6
4s user 65.25s system 99% cpu 7:35:03.03 total

一つ注意として, 現在のコードでは -samps [n] のサンプル数は, 「burn-inを含んだ」 値になっています。 *1 上の例では, テストなので10ステップのburn-inの後に10-12ステップのサンプルをセーブ。

肝心の結果は以下のような感じ。 *2 まだうまく分割できていない場合が多いですが, これはMCMCのステップ数が少ないから かもしれません。

交渉 の 決 裂 が 制裁 や 戦争 につ なが り かね ない よう な 状況 に 相手 を 追 い こ み 、 譲歩 を引 き出 す 手法 である。
朝 鮮 民主主義人民 共和 国 と 朝 鮮 半島 エ ネル ギー開発機構 は 十 五 日 、 ニ ューヨ ーク で 軽 水 炉 供給 協定 に 調 印し た 。
エ リツィ ン 大統 領 の 委任 を 受け て 発表 し た もの だが 、 チ ェルノムイルジ ン 首 相 の 主 導権 で 行われ た と み られ る。
首 相 の 足元 も 、 新党 作り で 揺 れ ている。

ただし, 上の実行結果を見るとわかるように, latticelm はFST上で動いているため, 京大コーパスのような大きな生テキストでは動作が少し遅く, 1ステップあたり大体 1時間くらいかかります。一方, 僕の実装では1ステップ当たりほぼ4分くらいなので, やはりC++で実装したのは間違いではなかった模様。 *3

ちなみに, 途中経過にも違いがあり(僕のコードでの京大コーパスの最終結果は, NL研 の論文に乗っている通りですが), 10ステップ終わった後での僕のコードでは以下。

sp:~/work/segment/src% time ./spylm -n 2 -N 10 ../data/kc.train.txt /tmp/model.kc
reading ../data/kc.train.txt..
reading line 37400..
37400 sentences parsed.
Gibbs iter = 1 sentence = 37400/37400 lexicon = 146752, lik = -5.96559e+06
 VPYLM Gibbs iter = 1 sentence = 171869/171869
:
Gibbs iter = 10 sentence = 37400/37400 lexicon = 109916, lik = -4.99233e+06
 VPYLM Gibbs iter = 1 sentence = 205171/205171
saving model to /tmp/model.kc..
saving stats..
saving dictionary..
saving segments..
viterbi segmentation 37400.. done.
done.
./spylm -n 2 -N 10 ../data/kc.train.txt /tmp/model.kc  2730.53s user 1.27s system 99% cpu 45:32.45 total

交渉の 決裂 が 制裁 や 戦争 につながりかねな い ような 状況 に 相手 を追いこみ 、 譲歩 を引き 出す 手法 である 。
朝鮮民主主義人民 共和国 と 朝鮮半島 エネルギー 開発機構 は 十五日 、 ニューヨーク で 軽水炉供給 協定に調印 した 。
エリツィン大統領 の委任 を受けて 発表 した もの だ が 、 チェルノムイルジン 首相 の主導権 で 行われた とみられる 。
首相 の足元 も 、 新党作り で 揺れている 。

僕のコードでは最初, 文全体が一つの「単語」として登録され, その後それが適宜 分割されるのに対し, latticelmでは初期値が文字毎の分割に見えるので, この違いは, 初期化の違いによるのかも知れません。
いずれにしても, 僕は実装を公開できないので, 興味深いツールだと思います。 計算時間も今後改善されるとのことで, 期待大です。

なお, 音声認識からの学習は今回は試しませんでしたが, ラティスからの言語モデル の学習は, 音声認識がない場合でも有用なように思います。
というのは, 日本語では特に, 表記に複数の可能性があり(同じ言葉をひらがなで書い たり, 漢字で書いたりし, 「香具師」のように読みと漢字表記がまるで対応しない場合 もある), 書かれた文字を"デコード"してラティスにしてその後の処理を行うのは 有用ではないか, というのが今回思ったことでした。 *4

---

MATLABで扱えるのは基本的に数値だけなので, 単語を id (整数)に変換する 関数が必要になるが(これは他の言語でも同じ), MATLABにはどうもハッシュテーブルが ないらしい。テキストを扱っている人は全体からみると少数派だろうから, 致しかたないのかも。
NIPS Papers(0-12) dataset (MATLABフォーマット) *1 のように, あらかじめ整数に変換しておくという手もある が, 訓練データに関してはそれでいいとしても, テストデータに関して毎回 それをやるのは面倒だし原理的に問題が多い。

なければ作れ, というわけで, アルゴリズム2巻 を参考にして実装してみた。
大羽さんの MATLAB のページ に公開してもいいんだけど, NLPに特化している感じがするのでここに公開して おきます。

• matlab-hash-0.1.tar.gz
• matlab-text-0.1.tar.gz

バグを取って速くしていたら書くのに2日かかってしまった。;

内部的には double hash になっていて, ハッシュ関数は perl 内部で使われている ものと 同じ。 ハッシュを自分で書いたのは数年ぶりなので, 勉強になった。
matlab-hash-0.1.tar.gz の中身は以下のような *.m ファイルからなっています。

• matlab-hash-0.1/
• matlab-hash-0.1/hashadd.m
• matlab-hash-0.1/hashadds.m
• matlab-hash-0.1/hashinit.m
• matlab-hash-0.1/hashmap.m
• matlab-hash-0.1/hashtable.m
• matlab-hash-0.1/hashval.m
• matlab-hash-0.1/binpow.m
• matlab-hash-0.1/README

使い方は中の README を読んで下さい。 おまけで, テキストを整数(の配列のセル配列)に変換する関数群 matlab-text-0.1 も公開しておきます。( README )

これを使って, テキストを整数にマップするにはたとえば以下のようにします。 (/usr/share/dict/words を lexicon にする例)

slt:~% matlab
> words = cellload('/usr/share/dict/words');
loading /usr/share/dict/words..
done.
> map = hashtable(words,1:size(words,2));
adding key 45427/45427..
done.
> text = textload('/home/dmochiha/corpus/austen/clean/emma.txt');
reading /home/dmochiha/corpus/austen/clean/emma.txt..
loading lines 14281/14281..
done.
> d = textmap(map,text);
mapping 14281/14281..
done.
> d{100}
ans =
 [ 19451 20830 36967 19255 38643 1369 41328 34619 28419 19897 24271 3073 0 ]
> text{100}
ans =
 { 'happier' 'if' 'she' 'had' 'spent' 'all' 'the' 'rest' 'of' 'her' 'life' 'at' 'Hartfield.' }

(ans は圧縮して表記しました)
/usr/share/dict/words の4万エントリのハッシュを作るのに25秒くらいかかってしまう (180秒くらいだったのを速くした)が, まぁ普通1回しか使わない関数なので いいことにする。(matlabではコードをベクトル化して内部処理させないと遅くなり ます。この場合は for 文を回すしかないのでベクトル化できない。) コンパイルするともう少し速くなるかも。

---

ついでに, いくつか気付いた MATLAB tips.

• 文字列の文字コードを得るには, 単に 0 を足します。(awkみたい。)
  たとえば, 'A' + 0 は 65 を, 'abcd' + 0 は [ 97 98 99 100 ] を それぞれ返します。最初これに気付かなくて, sprintf("%x",..) とか冗長なことを やっていた。
• 次のような for 文は順番に配列の要素が増えるので遅くなります。

  for i = 1:n
    a(i) = 0;
  end
  

  インデックスを逆からたどると, 最初に必要なだけ malloc されるので速くなります。 (要素の数が多いと, かなり劇的に違う)
  事前割り当てしておいてもいいんだけど。

  for i = n:-1:1
    a(i) = 0;
  end