Kneser-Ney スムージングによる文書生成

少し前に Kneser-Ney スムージングの性能を測ってみた記事 を書いたが、今回は Kneser-Ney スムージングによる n-Gram 言語モデルで文書生成を行なってみた。
スクリプトはこちら。


適当なテキストファイル(複数可)を入力すると、1行1文書の訓練データとみなして Kneser-Ney スムージング付きの n-Gram 言語モデルを学習後、文書を生成してファイルに出力する。
オプションもいくつか指定できるが、-h でヘルプを出すか、ソースを読むかしてもらえば。


与えられた文書の確率を Kneser-Ney で計算するには、ディスカウントによって生じる正規化係数の補正を求めるために N1+ などのちょいややこしい値をあらかじめ計算して保持しておかないといけないが、文書生成の場合は単語(あるいは文字)空間全体をなめるときにその補正項も求まるから、頻度さえ保持しておけば良い。このため、実装がとても簡単になっている。
確率を計算するところも再帰的に書けばとてもコンパクトになるので、言語モデルの実装は40行程度に収まっている。
なお、modified KN ではなく、素の KN になっている。これは、前回の記事で modified KN は確かに性能向上するが劇的なものではなく、コストを考えると実用的には KN で十分だろうという感触によっている。


というわけで、気になるところは実際に生成される文書だろう。
まずは困ったときの青空文庫夏目漱石「吾輩は猫である」 からルビと制御用の表記を除外したテキストを作り、上のスクリプトに入力している。
文字 7-Gram 言語モデルを構築して、生成した文書例がこちら。

「なかなかでもいいからちょっとどけたまえと云って大騒ぎさ」
「大和魂! と叫んで日本人が肺病やみのような咳をした」
「こっちがいをやる事はない。辞職をする勇気もない。薬缶は洩るに相違ない。吾輩はほかに能もない者だと思った。こんな真似をして出来得る限り早く御免蒙るに若くはないと決心した。しかし黒の子分になって鼠以外の御蔭で女郎を見せたんだがね」と迷亭も少し気に返えした。
「だっていいじゃありませんか」
「そうでございましょうがねえ」「駄目だ駄目だ」「出てこねえ」「落ちねえはずはあるまい。気の毒だと云う念が胸一杯になって鳴いていると、本当に面白いのよ。最初にはね巡査の服を脱いで、肉を脱いで石鹸で磨き上が、その内のものは湯を使でものだなどと狂ってくる。こんなものを見せびらかしたんだって、考えると女は罪な者でありました」
「偏屈になるかも知れません。こいつの間にかみんな椅子へ腰をかけて、ふわふわする」
「落第の候補者寒月君はヴァイオリンを買ったかい」
「あんな声を出してわあわあ云う。それでまず脈をとるためのこの質問に対して相談をしているか一向要領を得んと云う顔付をする。加之こう知名のつもりでやった芝居かも分らんじゃないか」と主人は無雑作に迷亭に聞く。


あー、そうだよねえ、「吾輩は猫である」ってこんなんだよねえ。
意外だったのは、"「" と "」" の対応がそこそこ取れていること。たかだか文字 7-gram だからその対応が取れる見込みなど本来全くないのだが、日本語の並びにその対応の分布が隠されているということだろうか。
とはいえ、やっぱり完全ではないし、そもそも地の文と会話文では表現も当然違ってくるわけだから、言語モデルをそれぞれ作ってあげればより良い結果が得られそうな雰囲気はある。難しくはないから、興味があればチャレンジしてみるといいかも。


もういっちょ、今度はツイート。
メンションや URL などを削った約 17000ツイートから同じく 7-gram 言語モデルを構築&文書生成した例。

そうやってつけてYahoo!オークション出まくってましたね でも、なんでだろう・・・・ ・・・・・
ソムリエ的な何かを描くので誰でもいいからRTくれた人に手書きメッセージ書く おやすみ( ;´Д`)
俺もつけようwwwwwwwwwwwww 中距離殲滅フォーメーションて、これからも楽しく拝見しております
でも嫌な気持ちになるらしいからすごいせどりツールが配信された。 最近しんどいわ、
おっすごい!→10,000ベルを必ずGET!激レア以上がザクザク とびびらせる to FUKUSHIMA 、国は金を出す
新歓行きたいものですな
そういやギョウオオオオオオオオブォオオオオオオオオオオオオオオアアアーーーーーーー(((o(*゚▽゚*)o)))
楽しみよおおおおおおおおおおおよろしくでござる〜おやすいみ〜〜〜(。◠‿◠。) わら
なにこれwwwこれからもよろしくねヾ(*´∀`*)ノ
よろしくでーす ( ´∀`∩);:
アイドルキックオーバーロー中wwwwwwwwwwwwwwwww┏(^o^)┓男のじゃ、凄く驚いた。
教えてくれない…。
久々にニコニコでペルソナ4のシーン集見てないから後悔して死にそうだった///////////


ふつー……あ、いや、普通でいいんだった。
普通で、かつ訓練データと異なる文書が生成されている。
ただ、幅広い表現のためにはもうちょっとデータが多いほうがよさそうだ。


このスクリプトは扱う文字種を特に制限していない。
というわけで最後に英語。Jane Austen の "Emma", "Northanger Abbey", "Persuation", "Pride and Prejudice", "Sense and Sensibility" を訓練データとし、文字 9-gram 言語モデルを構築している。
生成された文書は長いものが多いので、短いものからピックアップ。

"And this was the only yesterday, and Jane on her, in all probably ceased to Emma.
The day came, and to any fears, which one; she had spent and clever; but his remark on motives.
He had not think I might have been mortification of his neighbourhood, the regiment, which ought to be with him. There were; but that it is," whispering to get it! But I am always hoped our bestowed on me.
"He is a fool?"
"It will not be very heart again about her modesty, economy, took her hearing. She liked the two esteem. That was he perhaps be brought up to all his views on Sir John, who has never allow them to their evening."
"Are you must go to the subject would do her goodwill, and by them, had ever dared no explanation, a most unwilling to inquired after you."
"I must stay to everything for happiness; attending them, he was her mind was but a mixture of him for so many farther distressed him.


日本語より1文字あたりの情報量が少なく、不自然なところもやはりないわけではないが、それなりに英語っぽいと言えるのでは。
内容は置いといて(苦笑)。

Kneser-Ney Smoothing を試してみた

Kneser-Ney Smoothing は高性能な言語モデルである。と、よく聞かされて知っているつもりだけど、まだ一度も試したことがなかったので、試してみた。
コードはここ。

実験用にべったり書いているのでコピペは多いし、速度やメモリの効率も悪いが、まあ気にしないで。


コーパスは最初手元の適当なニュースコーパスを使っていたんだけど、それだと再現検証できないので、nltk のコーパスを使うように変更した。
nltk.corpus の下にあるコーパスモジュール名を -c オプションで与えると、そのコーパスを使って additive smoothing と Kneser-Ney smoothing の perplexity を出してくれる。
デフォルトでは Brown コーパスを使うのだが、例えばロイターコーパスを使いたければこんな感じ。

$ ./knsmooth.py -c reuters


ちなみに、与えられた名前に対して対応するコーパスモジュールを動的に読み込むところはこんなコード。

    m = __import__('nltk.corpus', globals(), locals(), [opt.corpus], -1)
    corpus = getattr(m, opt.corpus)

これで opt.corpus に "brown" が入っていれば corpus は nltk.corpus.brown になるし、"movie_reviews" なら nltk.corpus.movie_reviews になるって仕掛け。


出力はこんな感じ。brown コーパスの場合。

$ ./knsmooth.py -c brown --seed=0
found corpus : brown (D=500)
# of terms=1045022, vocabulary size=47349

UNIGRAM:
additive smoother: alpha1=1.0000, perplexity=1171.142
Kneser-Ney: heuristic D=0.604, perplexity=1171.068
Kneser-Ney: minimum D=1.000, perplexity=1152.640
modified Kneser-Ney: perplexity=1155.159

BIGRAM:
additive smoother: alpha2=0.0031, perplexity=1335.287
Kneser-Ney: heuristic D=0.761, perplexity=562.420
Kneser-Ney: minimum D=0.872, perplexity=556.637
modified Kneser-Ney: perplexity=543.748

TRIGRAM:
additive smoother: alpha3=0.0010, perplexity=9491.406
Kneser-Ney: heuristic D=0.881, perplexity=549.436
Kneser-Ney: minimum D=0.965, perplexity=542.305
modified Kneser-Ney: perplexity=520.433

コーパスからランダムにある割合でテストデータを選び、残りを訓練コーパスとしている。テストデータの割合は -r オプションで与えられる(デフォルト = 0.1)。テストデータを選ぶ乱数のシードは --seed で与える。
単語はコーパスモジュールの words() が返すものをすべて使っている(つまり記号類も有効)。正規化は小文字化のみしている。


結果は 1-gram から 3-gram まで、それぞれ以下の perplexity を求めている。

  • 加算スムージング。パラメータは [0.0, 1.0] の範囲で perplexity が最小になる値を選ぶ
  • Kneser-Ney スムージング。パラメータはヒューリスティックな値を選ぶ
  • Kneser-Ney スムージング。パラメータは [0.0, 1.0] の範囲で perplexity が最小になる値を選ぶ
  • modified Kneser-Ney スムージング。パラメータはヒューリスティックな値を選ぶ


結果をまとめると、こんな感じか。

  • 1-gram では大差はない( interpolate ほぼしないから当然っちゃあ当然 )
  • 2-gram 以上では Kneser-Ney は加算スムージングよりはるかに良い性能を叩き出す
  • modified Kneser-Ney は オリジナルの Kneser-Ney より確かに性能が良いが、定性的に違いがわかるほどのレベルではないだろう。計算コストを考えるとオリジナルで十分に思える。
  • 3-gram で加算スムージングが悪化しているのはコーパスが小さいせいか(それにしても悪すぎるんだが……)。Kneser-Ney はそんな状況でもちゃんと性能アップしている。

というわけで、確かに Kneser-Ney はなかなかいいね、という結果に。
KN で尤度を求めるには N1+ やらを数えて覚えておかないといけないので大変。modified KN だと数えておかないといけないものがさらに多くて、KN の2倍くらい大変。
でも尤度を求めるのではなく、「文生成などのために次の単語の分布を求める」という場合には N1 類を数えて保持しておく必要がない(語彙をぐるっと舐めている間に、どれだけ discount したかは当然わかる)ので、KN / modified KN ともに気楽に使える。


ロイターコーパスと movie_reviews コーパスの結果もおまけ。

$ ./knsmooth.py -c reuters --seed=0
found corpus : reuters (D=10788)
# of terms=1549612, vocabulary size=29774

UNIGRAM:
additive smoother: alpha1=1.0000, perplexity=854.850
Kneser-Ney: heuristic D=0.564, perplexity=855.384
Kneser-Ney: minimum D=1.000, perplexity=850.667
modified Kneser-Ney: perplexity=850.833

BIGRAM:
additive smoother: alpha2=0.0018, perplexity=207.485
Kneser-Ney: heuristic D=0.670, perplexity=143.591
Kneser-Ney: minimum D=0.704, perplexity=143.527
modified Kneser-Ney: perplexity=142.154

TRIGRAM:
additive smoother: alpha3=0.0004, perplexity=512.933
Kneser-Ney: heuristic D=0.762, perplexity=93.349
Kneser-Ney: minimum D=0.799, perplexity=93.246
modified Kneser-Ney: perplexity=89.477
$ ./knsmooth.py -c movie_reviews --seed=0
found corpus : movie_reviews (D=2000)
# of terms=1422742, vocabulary size=38181

UNIGRAM:
additive smoother: alpha1=1.0000, perplexity=908.244
Kneser-Ney: heuristic D=0.561, perplexity=908.691
Kneser-Ney: minimum D=1.000, perplexity=902.749
modified Kneser-Ney: perplexity=903.249

BIGRAM:
additive smoother: alpha2=0.0023, perplexity=515.530
Kneser-Ney: heuristic D=0.739, perplexity=283.122
Kneser-Ney: minimum D=0.806, perplexity=282.376
modified Kneser-Ney: perplexity=278.357

TRIGRAM:
additive smoother: alpha3=0.0007, perplexity=2735.080
Kneser-Ney: heuristic D=0.851, perplexity=239.729
Kneser-Ney: minimum D=0.918, perplexity=238.210
modified Kneser-Ney: perplexity=230.498