mots quotidiens. | |
Daichi Mochihashi (持橋大地) daichi <at> ism.ac.jp | by hns, version 2.10-pl1. |
|
||||||||||||||||||||||||||||||||||||||||||||||||
Witten-Bellスムージングされたバックオフnグラム
のことだとわかった。(もし万一違っていたら, 誰か指摘して下さい。)
PPMは "Prediction by Partial Match" の略なので, 何となく Lempel-Ziv のように
文脈辞書を作っておいて, それと「部分マッチ」をするのかと思っていたが,
全然違っていて, 単に長さk (言語モデルでいうn) までのこれまで出た文脈と
最長一致させているだけで, 論文にも明示的にそう書いてある。
"partial"というのは, データスパースネスのせいで必ず長さkの文脈がこれまでに
あるわけではないので, 多くの場合は部分マッチになる, という
意味らしい。
PPMのスムージングに使われる"PPM-C"がWitten-Bellスムージングと同じだというの
はFSNLPにも書かれているし,
エスケープメカニズムで文脈を順番に短くしていくのは,
Katz' Back-off と全く同じなのだけれども, 研究分野が違うのであまりこれまで
強調されてこなかったのだと思う。
というわけで, データ圧縮でPPMが(時間は遅いが)圧縮率がよいというのは,
n-gramがパープレキシティが低いというのと全く同じだということがわかった。
実際, PPMはn-gramと同じ方法で次のアルファベットを予測した後, 算術符号で
それを符号化するというもの。
PPMはk=5くらいが一番性能がよく, それ以上文脈長を増やすと かえって精度が悪化するということが知られているが, これはWitten-Bellスムージング がオーバーフィットを起こすということと一緒だと思う。 一方, Kneser-Neyは情報を短い文脈から順番に受け継ぐ階層ベイズ (階層Poisson-Dirichlet)の近似なので, これを使えばオーバーフィットは起こらない はず。
さて, PPMにはPPM*という無限文脈を扱う(ということになっている)方法
がありますが (Cleary, Teahan, Witten,
"Unbounded Length Contexts for PPM"
, 1997),
読んでみると, これはデータを「丸覚え」する方法だということが
わかった。「無限」といっても, そもそもデータは有限である以上,
予測が一意に決まる部分より長いトライのノードを作る必要はなく, その総数は
うまくノードを圧縮してパトリシア木等を使えば
ちょうどデータの総単語長と等しくなるらしい。
これは一見いいように見えるが, データが1億語であれば, ツリーのノードが1億個
できることになり, 大きなデータについてはあまり現実的ではない。
PPM*はノードを選択する方法は持っていないので, 小さなデータを圧縮する場合は
これでいいにしても, 自然言語のような巨大なデータを扱う場合は破綻する
のではないかと思う。
論文にも, PPM*は非常にメモリを使う, というような欠点が書かれていて,
.. it may be better to select the new context other than its length. Such strategies have not yet been investigated.と書かれている。
‥ 本 国 ‥ 日 本 国 ‥ 中 国 ‥ 属 国 ‥ の 家 ‥ 彼 の 家 ‥ 元 彼 の 家 ‥ 武 家
のようになる。赤色が Suffix array でソートされた文字列で,
青を縦に読んだものが Burrows-Wheeler変換
された文字列。
赤は
デフラグのガイドライン
(←笑った)のようにデータ中の文字をソートしたものだが, この各単語の現れた
文脈は, バイグラムの関係のために直前の文字はかなり似ているものが多く,
BWTした青の文字列はかなり圧縮しやすい形になる。
ということで, Burrows-Wheeler変換は, 「Bigram統計量が表に出るような形
に, テキストを等価変換するもの」なのだと思う。
("2-gramは全く無相関だけれども, 3-gramや4-gramには強い相関がある"場合には
圧縮できないはずですが, 幸いにして自然言語はそういう特殊な文字列にはなって
いない。)
もちろん, 圧縮関係の人には常識なのだと思いますが..。
言語モデルと圧縮はほとんど似たことをやっていながら, 単一化することができない
(絶対確実に同等と言い切ることができない)のは, 単に分野間の壁というより,
扱っている問題の違いもあるように思う。
一番大きい違いは, 言語モデルでは単語を直接扱うので次元が数万を優に超えるのに
対し, 多くの圧縮の論文では0/1か, 多くとも文字(最大256種類)ベースがほとんど,
という点。
*1
圧縮の場合はメモリサイズも重要なので, メモリを食う多くのn-gramの手法
をそのまま使うのは実用的でないのではないか, また
いくらHPYLMが理論的に綺麗だといっても, まさか圧縮のためにGibbsを回すわけには
いかないし.. ということなのではないかな, と。
それから, 一般には言語の場合は, linearな関係以上の構造的な関係を見たいから,
という応用的な側面が強いという理由もありそうな気がします。
と, これだけでは何なので..。言語の方面で圧縮との理論的な関係に興味がある人
は,
MacKay本
の
Chapter 6
がおすすめです。(PPMとBW変換はここで名前だけ出ているのですが, 内容は解説されて
いなかったのを今見直して思い出した。)
ちなみに, 圧縮の論文を読んでいると, 必ずといっていいほど文字列 "abdacadabra"
が例として使われているので, そのたびに頭の中で
米米クラブの歌
が節付きで流れてしまうのだった。w
タイトル一覧 |