« June 2006 | Main | August 2006 »

2006.07.30

車と日本食

はじめて週末を街で過ごす(先週末、先々週末は飛行機)。街に行き日用品を買おうと思ったらダウンタウンがバリケードで囲まれている。一体なんなんだと思ったら街の道を利用してレースをやっているらしい。行こうと思っていた店の前がホームストレートになってる。もちろん入れない。まぁ、レースはたっぷり見たわけだけど。

日本人街に行き久しぶりの日本食。おいしかった。

| | Comments (75) | TrackBack (0)

bwtの圧縮率解析

Burrows-Wheeler Transform (blocksortingと同じもの。以下bwt)はbzip2などで利用されている文字列に対する可逆変換です(詳細は勉強会資料とかググってください)。bwtを適用した後のテキストは同じ文字が連続しやすい圧縮しやすいデータとなり簡単な後処理(MTF変換+order-0圧縮)を加えることでLZ法よりも圧縮率は高く、PPM法に匹敵するぐらいに小さくなることは実験的に示されていました。
しかし、どのくらい小さくなるかの理論的解析はあまり進んでおらず、bwt後の処理に関してはもっといい方法があるはずだと研究が進んできました。

最近発表された話(compression boosting, The Engineering of a Compression Boosting Library: Theory vs Practice in BWT compression,A Simpler Analysis of Burrows-Wheeler Based Compression)はこの問題に対し大きな前進を見せており、理論解析値が(bzip2などの)実測値にかなり近づいています。詳細については見てもらうとして、興味深いのは最初にBurrowsらによって提唱された後処理(mtf + order0)が、もっと改善できるのではないかという予想に反して実はかなり優れた方法で、最近提唱されたcompression boostingやwavelet treeを利用した方法と圧縮率は似たようなものだいうことことが示されているところです。しかもそれを非常にシンプルな方法で実現しているということで再評価がされています。

個人的には解析でゼータ関数がでてきて驚いた。本質的に関係しているわけではなく、たまたま証明ででてきたものと思うけど。

| | Comments (1641) | TrackBack (0)

2006.07.26

COLING/ACL 2006

見たこと、聞いたことを箇条書き

・自分の発表 直前の練習で時間内に終わらなかったので急いでやったらうまくおさまった。質問の英語がよくわからず、なんとなく二つに絞られて片方に絞ったのだが、後で聞いたら外れの方を答えていたらしい。やった内容は性能はいいけど計算量が大きい確率モデルを訓練する時に、いろいろ工夫すると現実的な時間でできるという話。性能がもっとあがっていれば議論しやすいが、なかなかそうはいかない

・招待講演 Marcuさんの話。自然言語処理の多くの問題ではデコードの時に(はやってるstructured parceptronではトレーニングの時にも)argmaxを使うが、それが問題で、ベストではないという話。シーケンスにラベルを付ける問題で品詞付け、固有表現抽出、構文解析とか多くの問題がこの枠組みに含まれれる。大抵の問題では、決定的に解ける(ビタビとかで)ような探索空間を使うが、それがモデル設計の制約になっていたり、計算量が大きいという問題があった(という話だったような)。最後にSearnの話がでてきてこういう可能性もあるよということでまとめた

・機械翻訳 殆どStatistical MTの話。去年のACLで提案されたsynchronized CFGを利用する方法[A Hierarchical Phrase-Based Model for Statistical Machine Translation]の発展形でデコードに翻訳先の文を左から右へ順に決定できるよう制約をいれる話は面白かった[Left-to-Right Target Generation for Hierarchical Phrase-Based Translation]。この論文で示されたことで言語の枠組みが大きく違う日英間の翻訳では、文全体の並び替えがしやすいsynchronized CFGを使う方法はやはりうまくいくらしい。アライメントに焦点を絞った話も多かった。パラレルコーパス(同じことを述べている異なった言語対からなるコーパス)を集める話や、そこまでいかなくても似た話をしているフラグメントを集める話もかなり多かった。それだけ質の良いパラレルコーパスを集めるのが大変なんだろう。日英も巨大なやつは見つけられないなぁ。Marcuさんがワードアライメントの指標のWERと今使われているそれ用のコーパスを使うなと強く主張し続けたのが印象的だった(実際の仕事の内容を発表したのは残り5分ぐらい)。

・パーシング 自分の発表の裏でやっていたので聞けなかったが、PCFGにlatent annotationをつけるという話を拡張したものでF-scoreで90%越えした話が興味深い[Learning Accurate, Compact, and Interpretable Tree Annotation]。latent classを対数尤度が増える場合だけ分割したり、スムージングしたりするといいそうだ。昔やったword class modelのCFG版みたい。Discriminative parsing もまだ文長が大きいものはできないけどgenerative modelを超えたのが出てきたし[Advances in Discriminative Parsing]、精度はまだまだあがりそう。

・best paper 今年のbest paperはword netとかの既に分かっているtaxonomy(word netとか)とコーパスのdependency parserでつけた情報を組み合わせて単語間の未知の上位・下位語関係を見つける話でした[Semantic Taxonomy Induction from Heterogenous Evidence]。一つ一つの関係を独立に取り出したり、ヒューリスティックスなルールを使うのではなく、taxonomy全体の整合性(確率モデル)を高めるように決めていくという話。古くからある問題に対し比較的単純、だけど賢い確率モデルを適用していて、ありそうでなかった話。性能的にもブレークスルー。

・カンガルー/コアラ 一日休みの日があってみんなで船にのって動物園にいった。すごく寒くてワラビーも固まって震えていた。雨も降ってきた。個人的には走っているキリンとコアラ(おじさんみたいな顔だった)と謎の小動物達に会えたのでかなり満足。次の日の夜にカンガルーを食べました

・移動 サンフランシスコ→シドニー→サンフランシスコ はしんどい。でも待ち時間中にサンフランシスコで観光をしっかりした(ケーブルカー、フィッシャーマンズウォーフ? SFMOMAでは日本の戦後の写真展がやっていて自分の知らない日本がたくさんありました)。

・若手の会二次会 日本のNLPについて少し詳しくなった

| | Comments (104) | TrackBack (0)

2006.07.20

シドニーより

アメリカ滞在の後、COLING/ACLのため1週間だけシドニーに来てます。シドニーは冬で寒い。あやうく半そでだけもってくるところだった。カンガルーやコアラも凍えてました。

自分の発表は無事終わったので後は他の人の発表(とシドニー)を楽しみます。

| | Comments (23) | TrackBack (0)

2006.07.06

Range Coder

CodeZineでRange Coder (RC)の記事を書きました。
高速な算術圧縮を実現する「Range Coder」

RCは高速な算術圧縮として知られています。
動く原理の解説や実際に動くコードもあるので興味のある方はどうぞ。

#今までの記事、全部先頭に"高速な"ってついてる。。

| | Comments (85) | TrackBack (0)

勉強会 Succinct Data Structure

今日は東工大で行われた勉強会に参加してきました。
今回は私の発表もあり、Succinct Data Structureを発表してきました。
[資料 ppt, pdf]

作り始めたのが結局ぎりぎりになってしまい、後半の説明が雑になってしまったのが残念。以前作ったものをもっと詳しくしたかったのですが・・

他の方々の発表は違う分野ばかりで勉強させていただきました。同じ概念でも分野で用語が違う場合が多いので一苦労。その後の飲み会ではいろいろな話。測度論を勉強しようかなぁと少し思いました。少し。

帰り道、ぼけーっと自転車で走っていたら何がおきたか良く分からないが、タイヤ前輪が曲がり走行不能になり自転車を駐輪場に戻し歩いて帰る。

| | Comments (42) | TrackBack (0)

2006.07.03

バトンは受け取らない

けど、たまにするわがままぶり


部屋バトン

1.あなたは実家?一人暮らし?

年上の女性と暮らしてます(60ほど上)

これ以降、自分がメインに使っている部屋に限定します。キッチンとかは全部別。

2.あなたの部屋に写真はありますか?

あります。

3.あなたの部屋の壁に何か掛ってる?

LANケーブル。ディスプレイケーブル。靴下。衝動買いした掛け軸(克己心)。

4.あなたの部屋にぬいぐるみはありますか?

ありません

5.あなたの部屋に漫画はありますか?

たくさんあります。

6.あなたの部屋にある機械は?

ディスプレイ、パソコン、ノートパソコン、テレビ、ビデオ、電子ピアノ、時計、電子レンジ、
数の多い順

7.あなたの部屋でこれだけは人に負けない!!ってゆうのはありますか?

暑さ、寒さ。

8.寝るときに必ず周りに置くものは?

バランスボール(冷たくて気持ちいい)
扇風機(涼しい)
 
9.あなたの部屋は何畳ですか?

14畳

10.あなたの部屋は全体的に何色ですか?

木色

11.あなたの部屋にはどんな家具がありますか?

イス、机

12.あなたの部屋で一番多いものは?

13.ポスターなどは貼ってありますか?

ありません

14.あなたの部屋で一番目立つものは?

植物。

15.あなたの部屋にこだわりはありますか?

トラップがいろいろあります。

| | Comments (21) | TrackBack (0)

« June 2006 | Main | August 2006 »