« March 2005 | Main | May 2005 »

2005.04.30

新宿御苑

近くで実装、本読み。この付近はいい場所だなぁ。今まであまり目をつけていなかった。もうちょっと東へ行ってみよう。

本は教えてもらったDBの本。DBもちゃんと勉強すると面白いよなぁ。家にDBいれたくなってくる。自分のやっていることと直接は関係しませんが、いろいろ参考になりました。

実装は、作っていたものを組み立てているところ。過去の自分が何をしていたのかがよくわからない・・。もうちょっとで全体で動き出す。

最近、ほぼ毎日ランニングをしています。プールでも泳いでます。攻殻2ndのオープニングがすごいです。プルート2巻おもしろいです。WE8やってます。

| | Comments (1) | TrackBack (0)

2005.04.26

発表3つ

昨日はHPSGとCCGの輪講発表。今日は研究室のミーティングでTaskarさんの仕事の紹介。特にMaxMarginParsing。これの肝はDiscriminativeな手法をCFGに適用でき文長nの時O(n^3)ぐらいで動きますよという主張であり確かに精度があがっているのだが、basic function(feature vectorみたいなもの)やloss functionがCFGのルールに従って分解可能であるという制約がちょっともったいない。

でも、このおかげで後で文長の指数関数ぐらいの制約(とそれに伴う双対変数)がうまく多項式個の周辺変数に落とせるわけだけど。このままだとミーティング中に指摘されたとおりFeature Forestで確率の代わりにDiscriminativeを使いましたってことだけになって(これはこれでうれしいのだが)、しかも、basic functionを分解してしまうためkernelも使えなさそう。使えたらかっこいいのになぁ。

今年のACLもたくさんParsingの話がでているみたいですね。

| | Comments (2) | TrackBack (0)

2005.04.24

12時間

すごく時間のかかる処理(12時間から18時間)が、最後の最後でSegmentation Faultで落ちる。のが何回も続くと精神的につらい。

(終わっていないが)これから学んだことは、(1)問題が大きい場合はこれを分割し、途中から自動でリスタートできるようにするというのは工数がかかってもやるべき、(2)メモリ書き込み/読み込みエラーはかなり高い確率で起きる。ディスクはさらに多く、ネットワーク越しだとまず間違えていると思わなければならない (3)めげない

| | Comments (3) | TrackBack (0)

2005.04.20

免許更新

行ってきました。二回寝ぶっちしていたので、三度目の正直。初回講習なので2時間。教習に通った人はわかると思うけど、今日みた講習ビデオは、僕をなんともいえない気分にさせた。

あとはシンタクティックプロセスを読む。ラムダ計算と言語処理(特にSemantics)が絡み合って面白い。これで、処理速度が速いというのだから、すごいなぁ。

| | Comments (0) | TrackBack (0)

2005.04.18

月月金

来週の月曜日に二回発表、HPSGⅡとSyntactic Process、火曜日に研究室ミーティング発表。ぐわ。問題が深刻なのはいずれも何もしていないという状況。

| | Comments (0) | TrackBack (0)

2005.04.17

締め切りや仕事や輪講

でかなりおいつめられてます。誕生日もそんな中過ぎていってしまいました。

| | Comments (2) | TrackBack (0)

2005.04.13

Gmail

便利だなぁ。先輩から紹介してもらった。Spam駆除もいい感じだし(一日多いとき100来る)。パソコンが複数あるとメールの管理を統一してできるのがありがたい。2GBってのもすごいなぁ。このくらいのスケールになってくるといろいろ面白い情報がとれそうだなぁ。今、自分もGクラスで動くSuffix Tree(CST)を作っているのもこのへんを期待してのこと。

先輩と文字列に対するSuffix Arraysのようなindex化が木(二分木)に対してもできないかと話し合ったが、ちょっと思いつかなかった(任意の部分木マッチングができ、しかもindexがコンパクトに表現されているようなもの)。tree用のprefixspanとかgraph用のgspanとかは候補解は重複無く生成できることを主張しているけど、候補解を実際のデータにマッチングさせるのってどうやっているんだろう。論文みたときはそのへん特にかいてなかったような。

| | Comments (1) | TrackBack (0)

2005.04.11

院生初週末

地下鉄終電をのりすごしたときは、御茶ノ水まで自転車に行くようにしているので、今日はその自転車をとりに御茶ノ水でおりる。花がきれいだなぁ。もう花が落ち始めていたけど、川に落ちた様子もなかなかきれい。

バイト。コーディングなど。ぼんやりと今年のBIPの問題を考えてみる。時間があったら今年も出したいなぁ。問題2はみんな取り組みやすいといっているけど、難しいなぁ。そろそろkddcupが公開されますね。

夜は友人宅で花見。お酒飲んでべろんべろん。

輪講のHPSG2の自分担当のところよみはじめた。どの英語が非文で、非文でないか、説明されても違いがわからんとです。

| | Comments (2) | TrackBack (0)

昼おき

地下鉄終電をのりすごしたときは、御茶ノ水まで自転車に行くようにしているので、今日はその自転車をとりに御茶ノ水でおりる。花がきれいだなぁ。もう花が落ち始めていたけど、川に落ちた様子もなかなかきれい。

バイト。簡単にコーディングなど。空き時間があったので今年のBIPの問題を考えてみる。時間があったら実装してみようかなぁ。問題2はみんな取り組みやすいといっているけど、そんなに簡単な問題なのだろうか。kddcupもやりたいなぁ。

夜は友人宅で花見。お酒飲んでべろんべろん。


輪講のHPSG2の自分担当のところよみはじめた。どの英語が非文で、非文でないか、説明されても違いがわからんとです。

| | Comments (0) | TrackBack (0)

2005.04.09

花見

今日は午前に免許更新に行っているはずだった。おきたら昼。学校にいく。しかし、今日の午後も休講。授業で法学部とか経済学部あたりからまったく関係ないのをとっても面白いかなぁと思い探すが、きっと楽しいのは選んでいるときだろうと思いやめる。今学期とる授業は5つか。あとは論文かき。夜は研究室の花見。花はあったが、斬新なところであった。あははおほほと愉快に過ごす。終わったらそのまま研究室にみんな戻っていく。俺はまた論文かき。丸の内終電は行ってしまい、中央線で帰る。

---
学校行き帰りの時間に暇なので論文を一つ読むようにしている。最近はSpectral Clusteringを中心に読んでいる。このSpectral ClusteringはWeighted Kernel K-means法と等価であることが示されている
うちの先生が言っていたことだが、今、細分化されている様々な話も、理論が成熟するにしたがってどんどん同一の枠組みで説明されるようになる。その繰り返し。

MOSTの発表資料もおもしろいですね。発起人メンバーが豪華だなぁ。

| | Comments (0) | TrackBack (0)

2005.04.07

院の授業

出ようと思ったもの3連続で休講。いえい。

新しく来た人のネットワーク設定とかをしたり、輪講の予定を決めたり。今回はThe Elements of Statistical Learning とHead-Driven Phrase Structure Grammar。前者は前にざっと読んだことがあるし、内容もなじみぶかいけど、後者は大変そう。でも、これも3年始めの頃に地下の図書館で借りたような記憶がある。そのときはちんぷんかんぷんだったが。リベンジだな。

DCCのペーパーの手直しは簡単そうにいかず、さらに使っているモデルがPrefix Tree(Suffix TreeのSuffixがPrefixになったもの)を縮退させたものという説明をすれば、説明が簡潔にすむというのが分かり、送るといっていた人にかなり遅れますという謝罪のメールを送って書き直すことにした。理論的な解析もしたいし。

花粉症がいまさらひどくなってきたなぁ。

次の紙締め切りは15日。卒論の延長上の話。

| | Comments (0) | TrackBack (0)

2005.04.06

入院式

大学院に入ることをこういうのだろうか。半分ぐらいあっているような気もする

朝は寝坊。自分がはじまる時間を1時間勘違いしていたおかげで学長の話からは聞ける。話では確か、すべての科学は4つの軸にのり、その軸は人間、宇宙、地球、モノといっていたようだったのだがコンピュータ科学や数学はどこにのるんだろうなぁと思いつつ、自分は遅刻しているから何もいえない。科学が細分化しすぎているという話は納得した。全ての研究においついていくのはどんどん難しくなっているような気もする(前が知らないので自分がついていけてないだけかもしれないが)。自分が目を通そうと思っている学会だけでもまじめによもうとすると週刊ジャンプと同じペースになる。読んだら書かないと

入学式、ガイダンスが終わった後は新しく来た人のマシン設定とかネットワーク設定やって、演習3のページ作ろうとしていて新入生歓迎会の時間がきた。飲んでべろべろになって戻ったときには何もできない状況に。

| | Comments (4) | TrackBack (0)

2005.04.05

LSA

演習3の一つにしようかということで、調べてました。確率モデル(PLSA)としてみればΣc P(c)P(w|c)P(d|c)という隠れ変数cから文書と単語がそれぞれ独立に生成しているというモデルになっている。文書と単語が対称的な関係になっていてなんか変な感じ。何をしていることになっているんだろう。Spectral Clusteringの二部グラフ版とどう関係があるんだろうと思っていたらペーパーがありました。かなり共通点があると思うけど、お互いがreferされあっていないのはなんでだろ。

MATLAB使えるようになったので、いろいろ試してみよ

| | Comments (0) | TrackBack (0)

2005.04.03

Snowbirdまとめ

ソルトレイクシティのSnowbirdで開催されたDCCに行ってきました

最近のアメリカは出入国検査が厳しくなっているときいていましたが、確かに厳しかったです。荷物に鍵をかけてはいけないし、いろいろと怪しまれて検査に時間がかかります。入国時に1時間ぐらいかかりました。ソルトレイクシティについたときは雨で、Snowbirdについたときにはものすごい雪になっていました。レセプションでは、ヨーロッパの特許屋の人達となぜか機械翻訳について話す。

泊まったのはThe Cliffというところで、結構いいところでした。おいしかったし、ネット使えたし。Snowbirdはスキーの名所ということで、学会だけ出て帰ったらもったいないということで、学会が終わって残りの半日でスキーして、コースをまわれるだけまわってきました。レンタルはスキー板と靴だけしかできないということで、普段着ですべってきた無無計画ぶり。前日まで記録的な大雪だっただけに雪もいい感じで眺めもよく、楽しめました。

日本に帰るときにソルトレイクシティからサンフランシスコへ行くところで、飛行機が遅れて、サンフランシスコで駆け込み乗機。すごい危なかった。

初アメリカで感じたのは、英語は本気を出されるとほとんど聞き取れないということと、それと同時に聞き取れなくてもそんなに問題ではないということ。変な意味、日ごろしていたガイドの成果が。ご飯はまぁまぁおいしかったですが毎日ビュッフェであきました。時差ボケは最後まで直らなかった。

DCCは、圧縮関連で大きな学会の一つであり、圧縮と名のつくものなら何でも発表されてます。イメージ、音楽、映像圧縮が多く、純粋なテキスト圧縮は少なくなってました。

--
学会で面白かった話。

A.Moffatの"Binary Codes for Non-Uniform Sources" linkでは、整数符号化における復号スピードと圧縮率を両立した新しい整数符号法を提案してました。整数を符号化する場合は、unaryでこれから符号化するbit長さ、binaryでその実際の符号語を表現し符号化するのが基本ですが、彼の提案では多くの場合連続する整数値が似ている値なので、このunaryを隣合うN個の要素ずつのmaxをとって表現しようというもの。たとえば符号しようとしている整数(>=0)が3,5,2,9のときunary(lg(n+1))は2,3,2,4となりますがN=2の時は3,4、N=4の時は4を符号化します。maxをとっているのでbinary符号化の時に少し無駄が生じますがそれでもunaryが減るメリットが大きい。しかも連続してN個の復号でunaryは復号する必要がないので速い。このN個まとめた列をさらに再帰的に同じ整数符号化を用いて符号化します。(Nは4,16,64・・と増やしていくので大きなデータでも階層は3,4ぐらい)。実装は上のリンク先から手に入ります。

E.Bergmanの"Fast decoding of prefix encoded texts"は、Huffman法などのprefix encodの復号の高速化の提案。prefix codeの復号は木をたどるのではなく実際は表を使って行い、圧縮対象アルファベットを確率が大きい順にソートできるのであればcanonical huffman法が使えて、そうでなければ、Huffman木の各節点を状態だと考えて固定bit数を読み込んだとき、次にどの状態に遷移するかのオートマトンとして復号できることは知られています。Bergmanはこのオートマトンがものすごく大きくなってしまう問題点を指摘し、この状態を深さがM以下の節点だけに定義しそれ以外に遷移するような場合は bitを巻き戻す方法を提案してました。こうすると復元はちょっと遅くなりますが、表は小さくなって、実用的という話です。

F.Heklandの"Using 2:1 Shannon Mapping for Joint Source-Channel Coding"は歪み有り圧縮(転送にノイズ有り)の符号法の話。入力が2次元、それを1次元で情報を伝送し、復元側でまた2次元のデータとして取り出す問題で、1次元のところでノイズが入りレートが決められてます。このとき、2次元から1次元へのマッピングにアルキメデスの螺旋(この左)を使うというもの。2次元中の点をこのアルキメデスの螺旋の一番近い点で近似し、Θを伝送すると、これがかなり転送限界に近いということが理論的に解析されてました。

D.Chenの"Optimized Prediction for Geometry Compression of Triangle Meshes"はポリゴンデータの圧縮の話。ポリゴンデータは各点の三次元データとどの点同士がつながっているかのトポロジー情報からなっており、前者の圧縮が難しいことが知られています。現状知られている方法では、三角形を折り返して次の三次元データを予測し符号化するもの。彼の発表ではどのような順番で予測すれば最適に符号化できる問題かをMST問題に帰着するというもの。

自分のも英語を直して近くアップします。

| | Comments (0) | TrackBack (0)

2005.04.01

DCC4日目

DCCのおもしろかった内容は帰国してから書くとして、とりあえず生存報告。すさまじい雪でふもとへの道が封鎖され、かまいたちの夜状態になりました。ポスター発表も無事終わり、様々な分野の人が興味を持ってくれて話を聞いてくれました。特にlosslessの画像、音声処理にみんなPPMを使いたいらしい。フルペーパーが欲しいと数人から言われて笑顔で送ると言ったのですが、「your contribution is suffer from poor english」といわれた査読結果をどのように直すか。卒論で英語結構書いたから今見ると直せるかな。ははは。

今は、ピザにマッシュルームとベーコンをのせてくれと頼んだところ、プレーンのピザと、マッシュルームがのったピザとベーコンがのったピザの三枚が来て、それを仕方なく食べてぐったりしている。英語って難しいです。

昨日はCALTECの人につきっきりで通信理論について教えてもらいました。今の通信理論はデータ生成源が複数あって(それぞれが相関している)、データの受信側が一つで、その間がグラフ構造になっていて、それぞれの節点間のレートが設定されている時の全体の通信量解析とその達成アルゴリズムがはやっているらしい。グラフィカルモデルと似た話がいたるところで出ていた。

Suffix Arraysの比較の話も聞いて、その発表者と話したところ。two-stageとか3つにわけるやつも試しているそうで、今は変種も含めて全部網羅したいとのこと。Sさんのも知っていたようですが、日本語なのでよくわからないそうです。

| | Comments (0) | TrackBack (0)

« March 2005 | Main | May 2005 »