mots quotidiens.
Daichi Mochihashi (持橋大地) daichi <at> ism.ac.jp by hns, version 2.10-pl1.

先月 2007年05月 来月
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

2007年05月17日(木) [n年日記]

#1 韓先生最終講義

電通大の情報理論の 韓太舜先生 の最終講義が3月にあって, スライドが ここから 見られるのを知った。
院生のときに 『情報と符号化の数理』 (岩波書店 応用数学)を読んで, その明晰な内容と込められた哲学に感動した ので, 感慨深いです。
16ページ目の内容が本当なら, Weber-Fechnerの法則が理論から導けるという ことなのだろうか.. フルテキストは1975年なので, 閲覧制限がかかっていて見れないのが残念。
他も, 全体的に非常に興味深いのですが, とりあえず最後がワラタ。(笑)


2007年05月19日() [n年日記]

#1 PPM, 言語モデル, Burrows-Wheeler Transform

論文の準備のためにPPM,PPM*,CTWなど圧縮関係の論文を(完璧ではないと 思いますが), 色々読んでみた。 PPMについては, 北先生のところで1998年に, PPM*を使った言語モデルの話 が出ています。
さて, PPMは岡野原君が 言語モデルと 似ている という話を書いているのですが, 今回きちんと調べてみて, PPMは, 実は要するに
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.
と書かれている。

・ Burrows-Wheeler Transform

上のPPM*の論文には, Burrows-Wheeler Transform との関係も書かれています。 BWTについては 岡野原君のページ に詳しいですが, わかりやすい説明が ここ にありました。
これまでBWTについては何となくしかわかっていなかったのですが, これは つまり, 「Suffix arrayでソートした文字列の一つ前の文字(文頭の場合はぐるっと 回って最後の文字)」を並べた文字列に変換するものだ, とわかった。 これは等価変換で, 1文字後ろがソートされているという性質を使うと, 巧妙な操作で 元に戻すことができる。
例えば, 日本語の文字の場合だと

のようになる。赤色が Suffix array でソートされた文字列で, 青を縦に読んだものが Burrows-Wheeler変換 された文字列。
赤は デフラグのガイドライン (←笑った)のようにデータ中の文字をソートしたものだが, この各単語の現れた 文脈は, バイグラムの関係のために直前の文字はかなり似ているものが多く, BWTした青の文字列はかなり圧縮しやすい形になる。 ということで, Burrows-Wheeler変換は, 「Bigram統計量が表に出るような形 に, テキストを等価変換するもの」なのだと思う。 ("2-gramは全く無相関だけれども, 3-gramや4-gramには強い相関がある"場合には 圧縮できないはずですが, 幸いにして自然言語はそういう特殊な文字列にはなって いない。)
もちろん, 圧縮関係の人には常識なのだと思いますが..。

上のBW変換で, 各文字の現れた文脈を全部区別して記憶すると, PPM*のように データと同じだけの記憶容量が必要になることになる。
言語モデルはこれに対して, 上の文脈をうまく予測に関してマージすること で, よりコンパクトなモデルを作っていると考えられるかと思った。
例えば, 上の例で「家」を予測するのに, 「の」か「彼 の」だけの文脈があれば 充分で, 「元彼の」と言う必要はない。それを予測確率を基にしてやった仕事 ということに(僕の今回の話は)なるのかな..と思ったのだった。

#2 Reply

専門家の岡野原君から コメント をもらったので, 論文をざっとですが読んでみました。
PPM-IIの"Information Inheritance"というのは確かに, ある文脈で 新しいアルファベットが出る確率を, 単にエスケープ確率とするのではなく 親ノードでの確率を使って推定する, というもののようで, HPYLMのような 階層ベイズ法 (をヒューリスティックに近似したもの)なのではないかな, と。

言語モデルと圧縮はほとんど似たことをやっていながら, 単一化することができない (絶対確実に同等と言い切ることができない)のは, 単に分野間の壁というより, 扱っている問題の違いもあるように思う。 一番大きい違いは, 言語モデルでは単語を直接扱うので次元が数万を優に超えるのに 対し, 多くの圧縮の論文では0/1か, 多くとも文字(最大256種類)ベースがほとんど, という点。 *1 圧縮の場合はメモリサイズも重要なので, メモリを食う多くのn-gramの手法 をそのまま使うのは実用的でないのではないか, また いくらHPYLMが理論的に綺麗だといっても, まさか圧縮のためにGibbsを回すわけには いかないし.. ということなのではないかな, と。
それから, 一般には言語の場合は, linearな関係以上の構造的な関係を見たいから, という応用的な側面が強いという理由もありそうな気がします。

と, これだけでは何なので..。言語の方面で圧縮との理論的な関係に興味がある人 は, MacKay本Chapter 6 がおすすめです。(PPMとBW変換はここで名前だけ出ているのですが, 内容は解説されて いなかったのを今見直して思い出した。)
ちなみに, 圧縮の論文を読んでいると, 必ずといっていいほど文字列 "abdacadabra" が例として使われているので, そのたびに頭の中で 米米クラブの歌 が節付きで流れてしまうのだった。w


*1: 単語ベースの圧縮の論文もあるようですが, メインストリームはあくまで0/1か, charベースだと思う。(何を単語と認定するか, という問題もあるので, 圧縮だけの問題にならない。)

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