« February 2008 | Main | April 2008 »

2008.03.23

tx-0.09リリース

txをバージョンアップしました。

変更点は
・reverseLookup()
・サンプルプログラムにs2sbuild s2ssearchを追加

reverseLookupはtx固有のidから元のキーを復元するというものです。中で葉から親へ木を辿ってキーを復元してますのでキーをそのまま持つのよりは遅い(サイズ優先)

で、この機能を使ったプログラム例がs2sbuild, s2ssearchでこれらは、キーからキーへのマッピングを扱いたい場合の礼です。値がキー集合であり、キーだけじゃなく値も圧縮したい場合などが想定例です。

キーで使うキー集合と値はそれぞれtxで独立に圧縮保存されていて、マッピング自体は元のtxのid番号と値のtxのid番号のペアでもっています(キーと値が1対1対応でなくても良いように作ってあります)。
s2sbuildは辞書を作り(生成されるファイルは三つ),s2ssearchは入力列の全ての部分文字列に対しcommonPrefixSearchをかけ、それにヒットした値を全てを表示します。

例えば、読み方から表記へのマッピングが各行にtab区切りであるとき(ファイル名:yomi2hyoki)、サンプルプログラムを使った動作例は次の通りになります。

% ./head yomi2hyoki
あーうーおじゃままん アーウー・オジャママン
あーういんしょう アーウィン・ショウ
あーえすもなこ ASモナコ
あーえぬあーまいれーじくらぶ ANAマイレージクラブ
あーかーげー AKG
あーかーと アーカート
あーかーど アーカード
あーかーよんなな AK47
あーかいう゛ アーカイヴ

% ./s2sbuild yomi2hyoki y2hindex

% ./s2ssearch y2hindex
keyNum:174496 nodeNum:1620383
keyNum:195576 nodeNum:1530718
>どらごんくえすと
どらご ドラゴ
どらごん ドラゴン doragon dragon
どらごんくえすと ドラゴンクエスト ドラゴン・クエスト Dragon Quest ドラゴンクエスト
らごん ラゴン
ごん GON!
く クモハ313
くえすと クエスト クエスト
えす E’S 「S」 SP-NX502 es [es] es Es
すと 「スト」

これらはサンプルプログラムですので自分のアプリケーションにあわせ、s2sbuildとs2ssearchを書き直せばよいと思います。
で、入力と出力をそれぞれ圧縮した効果ですが、例えばはてなキーワードは、合計で入力と同じサイズぐらい。

% ls -lh yomi2hyoki
-rw-r--r-- 1 hillbig hillbig 7.7M 2008-03-23 03:46 yomi2hyoki
% ls -lh y2hindex*
-rw-r--r-- 1 hillbig hillbig 2.4M 2008-03-23 03:51 y2hindex.1
-rw-r--r-- 1 hillbig hillbig 1.6M 2008-03-23 03:52 y2hindex.12
-rw-r--r-- 1 hillbig hillbig 2.3M 2008-03-23 03:52 y2hindex.2

マッピングテーブル(y2hindex.12)がナイーブな実装でちょっと冗長。

| | Comments (0) | TrackBack (0)

2008.03.12

期待値最大化法などのあれこれ

実装よりの話。

近年、Nonparametric Bayes手法が自然言語処理やら機械学習で流行っているのですが測度論とかからスタートするのは大変で、恩恵にあずかりたいがなかなか大変。
で教師無し学習で頻出する期待値最大化法(EM法[英語 wikipedia])を使っている場合、そのコードをちょっと変えるとDPを近似できますよというのを実際試してみると結構うまくいく (ACLのtutorialとかが詳しい)

期待値最大化法では、Mステップでを各パラメーターを正規化する部分があるが、
zのパラメータ = C_{z} / \sum_{z'} C_{z'} (C_{z}はEステップで数えたzの出現回数)、
ここを
zのパラメータ = exp Ψ(C_{z}) / exp Ψ(\sum_{z'} C_{z'})
と置き換えるだけでDirichlet Processを使ったものと同じ効果(大きいクラスターはより大きく、スパースな結果)が期待できる。これはちゃんと求めるとDPを平均場+変分法で近似してあげたもの。
このΨはdigamma関数であり、黙って落ちてるのを使わせてもらえばよい(例えばここ)

この exp Ψ (x) は、xが大きいとx-0.5、xが0に近いと0より大きいがディスカウントした値を返すような形をしており、各頻度を同じ値でディスカウントする効果がある。これより頻度が少ないものはより大きい影響をうけるが、大きいものは小さい影響しか受けない。大きいクラスターはより大きく、小さいクラスターはより小さくなるというpriorが実現される
これで精度が上がったら儲けもの

---
EM法は最初対数尤度がすごい勢いで上がって、繰り返し回数が100回ぐらいをすぎると落ち着くようにみえるけど、実はその後も精度はじわじわ上がり続け1000回ぐらい繰り返さないと収束しない場合があるらしい "Why Doesnt EM Find Good HMM POS-Taggers?"[pdf]
これで初期値を変えてはしらせたりもしたら計算リソースがまだたりないなぁ

---
そうなると計算時間が重要になってくるが、大体コードで一番遅い部分は exp, logの計算部分(教科書にも書いてあるlogsumexpの部分。これの最後とか)。私も、なんとなく全ての変数をlogスケールにした方が乗算が加算になったりしてお得感もあるかなとおもい、昔から変数をlogスケールにし、logsumexpを使っていた

しかし、最近の実装ではlogで表現せずに、そのまま計算して、アンダー/オーバーフローが起きそうになったらリスケーリングするという手法がちらほら見られるようになってきた。また、多くのケースで、アンダー/オーバーフローは起こらずそのまま計算してしまえる場合が多く、これだけで10倍ぐらい速くなる

| | Comments (84) | TrackBack (0)

2008.03.01

列挙学校に行ってきました。

2/28, 2/29に三浦で開かれた列挙学校に行ってきました。

公式ページに発表スライドがアップロードされています。すばらしい![link]

列挙問題とは「与えられた条件を満たすものを漏れなく,重複なく出力する問題」で、これを時間、スペース的に効率良く列挙するのが目的になります。この列挙問題は、それ自体問題として面白いですが、実用的にもデータマイニングや機械学習、情報検索(のインデクス作成)、など多くの分野で重要となってきています。

例えば、全ての順序付き木を漏れなく、重複なく列挙するという問題については、単純にやろうと思うと、適当に木を伸ばしていって過去に作ったものと重複していないかチェックしていってというふうにやることが考えられますが、これは時間、スペースともに非常に非効率です。
この順序付き木の列挙問題については最右拡張という方法が知られています。これは、ルートのみの木からはじめて、一番右側のパス上のどれかの節点の右側に子を付け加えていくというのを再帰的に行う操作です。この操作で重複なく、漏れなく全て列挙できます。

こうした列挙アルゴリズムについては別々には知っていたのですが、今回の学校では全体を俯瞰的に見れたのはとても良かったです。特に多くの問題が家系木を使った逆探索という枠組みで、統一的に説明できる点と、圧縮好きとしては冗長な情報を列挙するのではなく、少数の極大な要素のみを列挙することができるという点が面白かったです。あと、最後の宇野先生の実装の話は私も実装でよく使う技術が出ていて、こういう技術はどこでも重要だなぁと思いました。実装意欲がわいてきたので私も実装してみよう。

--
以下は私向けのメモも含め簡単に逆探索の説明。

逆探索では、最初に列挙したい集合間に親子関係を定義します。これは、各列挙候補に対し親の要素を決定的に決める方法を見つけるだけでOKです。この時、この親の定義でループが無いように保障する必要があります。例えば親は子より必ず辞書式順序が小さいとか、構成する要素の和が小さいとかで保障できます。
そうすると列挙すべき全ての候補間に有効付き枝が張られ、根付き木(家系木)ができます。
次に先程親の見つけ方を定義したのですが、それを逆向きにして子を辿る方法を作ります。そして、この家系木を根から深さ優先探索して全ての列挙したいものを列挙します。深さ優先探索ということは、列挙に必要なメモリも少なく済みます。

どのようにして親を定義するかで、列挙効率とその上でアプリケーションが決まってくるのですが基本的には次の二点が守られていればよいみたいです
・子が効率的に列挙できる
・親が持ってる性質は子も受け継ぐように(これがあると、列挙途中でアプリケーションの制約で枝刈りができる)

例えば、先程の順序付き木の列挙手法である最右拡張も、この逆探索を使って次のように設計できます。
最初に各順序付き木について、その親を一番右側の子を取り除いて得られた木だとします。これは決定的な操作であることに注意してください。この時、親は必ず子よりもノード数は小さくなっているのでループはありません。この親の定義によって、全ての順序付き木の間に有向枝が張られ家系木が作られました。根はどんどん取り除いた結果なのでルートだけからなる木となります。で親から子を列挙する操作は子から親へ辿る逆となるので、先程のように一番右側のパス上にどれかの頂点に一番右側の子を作るという操作になります。これで全ての順序付き木が重複無く、漏れなく列挙できるようになりました。

この逆探索のアイディアは、例えば順序無し木やミスマッチありのパターンやら、グラフやらでも同様に使えます。複雑な要素を列挙する場合したい場合も、この逆探索の方法を知ってれば体系的に列挙アルゴリズムが作れます。

| | Comments (94) | TrackBack (0)

T-FaNT2のスライド

先日ありましたT-FaNT2発表スライドが大体出揃いました(許可をいただけたものだけアップしてます)。

参加された方も、されなかった方も興味のある方はスライドを見てみてください。

| | Comments (0) | TrackBack (0)

« February 2008 | Main | April 2008 »