mots quotidiens.
持橋大地 (Daichi Mochihashi) daichi <at> cslab.kecl.ntt.co.jp by hns, version 2.10-pl1.

先月 2010年03月 来月
1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31

2010年03月19日(金) [n年日記]

#1 lwlm, The Latent Words Language Model.

というわけで, 公開しました。 潜在語言語モデル(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単語/秒くらいになる模様です。謎。


*1: 去年 ACLの際に非常に面白い話だと書いた のはこれ。

2010年03月07日() [n年日記]

#1 Google Sparsehash+HPYLM

日曜日だが, 坪坂君の実験 で Google sparsehash はやはり結構速かったことが わかったのに影響されて(?), 自製のHPYLMのコードを Google sparsehash で書き直してみることに。
というのは, もうすぐ公開する予定のプログラムで確率の計算がボトルネックに なっているらしいことが分かったからですが..。 *1

実際のプログラムはうまく抽象化して書いてあったことが幸いして, 少し直すだけで対応完了。

の両方を sparse_hash/dense_hash にしてみました。
例えば, p(cake|mary eats a)の確率を予測したい場合, 木の根から a→eats→mary の順にノードをたどり, たどり着いた 'mary eats a' のノードで cake が何回出てきているか&そのテーブルの数は何個か, を知る必要がありますが, どの検索もスパースなので, 何らかの形で効率的なデータ構造が必要になります。

というのが前置きで, 以下がその結果。

AlgorithmTimeMemory
dense_hash_map33.48min209M
sparse_hash_map55.28min111M
splay tree57.13min76M
上はかなり小さいデータ(京大コーパスから5000文)のもので, 毎日新聞2000年度全文 (約150万文)を突っ込んだメモリ使用量は, dense_hash_map で7.5G, splay tree で 4.0Gでした。ちなみに, ナイーブに ext/hash_map を使うと20G超えのようです。
ということで, というのがひとまずの結論のようです。
スプレー木は二分木なので O(logn) ですが, 意外と速かったなというか..。
今回は densehash を使うことにしましたが, ちなみにスプレー木は自己組織化二分木 なので, 計算が進むほど, 各ノードの持つ二分木の構造が最適化されて, どんどん計算 が速くなるという素敵仕様があったりします。


*1: ちなみに, この実装ではノードの検索は int のハッシュなので, ハッシュ関数の影響 はありません。
*2: これは, ngramの各ノードでそれぞれハッシュを持つという構造のせいで, 巨大なハッシュを一つだけ持つという場合は, Google sparsehashのメモリ効率は非常に 良いのだと思います。

2010年02月24日(水) [n年日記]

#1 MCMC研究会@ISM

立川に二泊して, 土・日の統数研でのMCMC研究会から帰ってきました。

どの発表もとても興味深い内容で, 特に美添一樹さんのモンテカルロ木探索の話が 非常に力の入ったトークでした。
北門さんの漁業での混合比推定のお話もなるほどという感じで, Pritchard(2000)のadmixtureの話(=LDAと同じモデル)が出たので, これも入れないといけないと思い, 急遽翌日の自分のスライドにLDAの紹介の話を入れた のですが, 北門さんは二日目は出席しておられなかったようで残念でした。
結構参加者がいて, 色々な話や議論があって, かなり成功だったのではないかと思います。

僕は二日目朝に, 統計的NLPの最近の状況とそこでのMCMCの使われ方について いくつか紹介しました。
別に僕はMCMC信者というわけではないですが, 色々な場面に有用な手法なのはなぜか, のような話も書いてあります。 PDFを置いておきましたので, ご興味のある方はどうぞ。 *1


*1: インフォーマルな研究会なので, わりと本音っぽいことが書いてあったりします。

#2 電通大

翌日は実家に泊まって, 月曜日は韓先生のシャノン賞受賞記念講演会 「情報数理の遥かな地平」 を聴きに, 調布の電通大へ。甘利先生や韓先生の謦咳に初めて接してきました。


2010年02月12日(金) [n年日記]

#1 -

連携講座関係の打ち合わせでCS研に来られた京大の 田中先生 に, ずっとお話を伺う。
色々なお話を聞いて, 本当楽しかったです。

最近つくづく思うことは, もし関西に来ずに東京にずっといたら, こういう機会は まずなかっただろうなぁ, ということ。
日本の自然言語処理の実質上の本場である京阪奈に来て(京阪奈がそうなのは, 結局長尾先生の影響だと思います), 関西の色々な方 と話すことができているのは, 非常に貴重な経験だと思っている。

あまり就職先等を選ぶときにそういうことを気にしている人は少ないのかも 知れないですが..。


2010年02月10日(水) [n年日記]

#1 Gnus+nnmhでMail

研究には直接関係ない話。
個人的に, メーリングリストの過去メールをまとめ読みする必要が生じた。 今でも, MLのメールを後でゆっくり読みたい等ということは結構あるのではないかと 思います。
こういう目的にはメーラーではなく, 既読/未読を管理でき, メールをスレッド表示 してくれるニュースリーダーが便利です。昔はメールを持ち帰って, GNUSでメールを 読んでいました。 (正確に言うと, 指導員室の SparcStation でMLのメールを tar+gz で固めて持ち帰った後, Macの漢字Talk7上の Mac MiNT (System7用のUnix環境)上の Nemacs 3.3.2+GNUS 4.1 で メールを読んでいました。..マニア!)

GNUSはサーバを ":Mail" のように指定すると mhspool.el (現在はnnmh.el) の機能で ~/Mail を読んでくれるという機能があり, 現在も使えるようですが, 実際に起動してみると, あるはずのメールフォルダが表示されません。 Gnusはその後 Nana Gnus やら September Gnus やら専門のマニアでないと付いて いけない世界に突入していたため見送っていたのですが, そろそろEmacsも枯れてきた ので大丈夫だと思い, 決意して設定してみました。
かなり色々壁があったので, 以下その過程のメモ。

・ ステップ1:

さて, まず, 例えば Thunderbird ではメールは ~/.thunderbird/*.default/Mail/Local Folders/ 以下にある一つの ファイルに mbox 形式でまとめられているので, それをバラす必要があります。 *1
これにはMHを使うと簡単です。MHは最近のLinuxには入っていないようなので, http://www.nets.ne.jp/~matsu/MH/ あたりから src.rpm をgetしてbuildします。 MHの inc コマンドは通常 /usr/spool/mail/`whoami` のメールボックスを読みますが, これは -file オプションで変えられるので, .mh_profile に Path: Mail 等を書いて おいてから,
% inc +foo-ml -file /tmp/FOO-ML
で ~/Mail/foo-ml/ にメールを inc してばらします。

・ ステップ2:

ここで Gnus を起動するわけですが, 実際にやってみると, 上のfoo-mlも何も表示 されません。この原因は, 昔のGNUSと異なり, 明示的にUをタイプしてディレクトリを 「講読」しないと表示されないことのようなので, Infoを読むと
(define-key ctl-x-map "g" 'gnus)
(setq nnmh-directory "~/Mail")
(setq gnus-select-method '(nnmh ""))
(setq gnus-options-subscribe ".*")
(setq gnus-options-not-subscribe "*draft*")
のように書くと, 自動的にフォルダが講読されるようです。

・ ステップ3:

これでメールフォルダを Gnus 5.9 で読めるようになったわけですが, 実際に読んでみると, 多くのGmail関係のメールの From: や Subject: が(none)と 表示されます。(!)
少し調べたところ, どうもこれは Gmail の付ける長い符号化されたsignatureヘッダ や, Received: が連続に連続を重ねると発生するらしく, どちらも読むためには不要なので, 下のようなスクリプトであっさりカット。そもそも nnmh は勝手に自分で管理用の ヘッダを付加するようなので, ヘッダを削ることは問題ないと思います。
#!/bin/env perl

while (<>)
{
    if (1 .. /^$/) {
        if (/^$/) {
            print_header($header);
        } else {
            $header .= $_;
        }
    } else {
        print;
    }
}
    
sub print_header
{
    my $buffer = "\n" . shift;
    my @header = split(/\n([A-Z][\w\d\-]*:) /, $buffer);
    shift @header;

    while (my ($label, $content) = splice(@header, 0, 2))
    {
        unless ($label =~ /signature/i || $label =~ /^received/i)
        {
            printf("%s %s\n", $label, $content);
        }
    }
}
ここまでやって, ようやくGnusでメールが読めるようになりました。万歳。
以前と比べて, じっくりメールを読むことは減ってきているように思いますが, こうしてオフラインでゆっくり読める環境も大事なように思います。


*1: Gnusのnnmboxを使うとmbox形式のファイルを直接読めますが, これは当然メールボックスを直接1つだけ指定することを想定しているので, こうした用途には向かないと思います。

5 days displayed.
タイトル一覧
カテゴリ分類
 なかのひと
Powered by hns-2.10-pl1, HyperNikkiSystem Project