« August 2004 | Main | October 2004 »

2004.09.29

9月末の生活

仕事、応募、実装などなど

旅行博に行ってきた。日本にいながら旅行気分。

研究室の机の位置が決定した。外が見えるのでとてもよい。

IBMからの招待講演はBlueGeneについて。来月あたり地球シミュレーターを抜くことが確定的らしい。話を聞くと、とにかく今の高速化の問題は発熱に尽きるらしい。確かにThinkPadをずっとひざの上に載せていると火傷する。そんなに速くして何をするんだと思うけど、タンパク質の折り畳まれる様子をシミュレーションするには1PFlopsで1年かかるそうだ。需要はいくらでもでてきますな

9月中に終わらせようと思っていたいろんなことが終わらずにやることがふえていく。あははは

| | Comments (1) | TrackBack (0)

2004.09.26

スポーツの秋

読書の秋。食欲の秋。なんでだろう。

最近あまりに殺伐とした生活を送っていたのでスポーツがしたいと衝動的に思い、前日にさそったところ数人ひっかかった。御殿下でフットサルかバスケしたかったけど、前日では予約できるわけがなく池袋で卓球しました。おもしろかった。スポーツってすばらしい。定期的にスポーツしたいなぁ。御殿下登録するか。スポーツしたい人は声かけてください

カラオケをした後家に帰宅。なんかつかれたなぁと思って寝たら一日が終わってしまいました。
でもおきたあともサッカー見ながらサッカー(WE)してた。いや、まだこれから。ファミレスいこう。

今年もあと1/4ですか。早いなぁ・・

| | Comments (1) | TrackBack (0)

2004.09.25

駒場図書館

駒場図書館に最近通っている。
読もうと思っている本自体はたくさんあるので、それらをよんでいくが、どれも、なんとなく理解したようなしてないような。夏休みはじめから少しずつよんでいるKernel本はようやく最後まできたが、本当に理解するには実際ものつくってみないとな。
圧縮の話。メモリ解放部分がおかしいのとモデル化の部分の計算がおかしいバグを直した。といっても公開しなければ全部自分で完結してしまうのが悲しいが。ソース公開とかはもうちょっと先だな。実験もうちょっとしたい。今ソースはひどいことに。関数名{数字}の数字部分が0から20ぐらいまでそれぞれあってどれが何を意味しているかは自分しかわからない。

喫茶店で隣に座った人が就職の面接をうけていたらしいがすさまじかった。そのへんの若者が名刺や履歴書が無くてそのへんの紙みたいのに書いていて、それで面接官が激怒。帽子もかぶりっぱなしだし。しかし、いろいろあった挙句なぜか採用決定。「君には負けたよ」と面接官と思われる人が言っていた。何があったのだろう。よくわからない

走る距離が7キロぐらいまで増えてきた。これで40分。最終的に10キロ30分で走れたらいいなぁと思っていたら、調べたらそれだとオリンピック出られるんだなぁ。ちょっと速すぎ。ぼうっと何も考えずに走っているとすっきりする。寝るより良かったり。ただ、本当に疲れていると走る気もしない。休みの間しかはしれないな

話が飛んでいる。別の記事にしたほうがいいんだろうねぇ。でもめんどうだ

| | Comments (0) | TrackBack (0)

2004.09.23

日常

朝ごはんをきちんと食べようということで、パンを焼いて食べて、寝る。あまり意味がない。昼頃、おなかがすいて我慢できなくなったころに家を出てどのへんに行こうか決めるか、もしくは決めずに適当に行く。東京はどこをどういってもなんとかなる。ごはんを外で食べて、喫茶店とかで本読んだり、パソコンでプログラムか資料作ったり。夕方帰ってきて、5kmぐらいから10kmランニング。買っておいた簡単な調理でできる夕食を食べる。ウイニングイレブンをする。夜中は本を読んだり実装したりする。そして朝になる。少し変化はあるが大体こんなかんじ。単調

| | Comments (4) | TrackBack (0)

2004.09.21

postgreSQL

DBを最近少しだけ利用しはじめてる。昔から興味あったのだが、なかなかとっかかりがつかなかったので。
少し前までは、リレーショナルDBってなんじゃいな。EXCELと違うのか、というレベルだったのだが。
データマイニングでサービスを行おうと思うと、DB使ったりするんだろうなぁということと、DBではどんなふうにデータを保存し、操作しているのかなぁと。
家のLINUXパソコンはひどく非力なので、新しく買おうかどうしようか。3万円で買えるらしいが。

google jamは1問目から間違ってたみたい・・がーん。当たってたら、チャレンジしなくても届いていたのか。慎重にやればよかったなぁ。負けたときは結果論

| | Comments (0) | TrackBack (0)

google jam Round1

負けてしまったようだ。問題文の意味をなかなか理解できなかった。
1番は携帯電話で超過料金、固定料金、自由につかっていい時間とか設定されている中で、最も安いプランを選ぶ問題。ここでPeak Hour、Off Hourの意味がわからず、googleとかでずっと検索していた。問題の意味からすれば、Peak Hourのみが、課金対象として考慮されるらしい。プランによっては、Off Hourでも課金対象になるものもあったが
2番は簡単なルーターを設計せよという問題。Accept、Reject、Forwardingなどの設定を行ったうえで、入ってきたパケットに対し、どのような動作をするのかを示せという問題。一度こういうのやった経験がある人はつよいだろうなぁと。一番困ったのはパーサーで、ピリオドで区切ってから、"-"や"*"がある場合は、特別に処理する。そういえば昔アセンブラの開発で、パーサー書いたことがあるとおもってそのライブラリを使って、かいていったが間に合わなかった。あわてずにやればできた。でも、あわてるのは実力がないからか。
3番はデフラグの問題。各ファイルとそのファイルの要素がどのセクターに分散しているかという情報が与えられ、最小の移動回数(交換も許される)でデフラグを完成させろという問題。これに40分ほどはまってしまった上、他の問題にうつるときにセーブしなかったため書いたコードは消えてしまった・・ まぁ、あのままできるとも思えなかったが
他の人の回答の間違えを指摘するチャレンジの時間は、だめもとで、怪しそうなコードをためしてみたが、やはりだめだった。というわけで結果は出てないが1番しか提出してなく、チャレンジも失敗したためほぼ敗退。

勝ち残った方がんばって本社大会に出場してください。Tシャツを着て精進します

| | Comments (0) | TrackBack (0)

圧縮の話

最近、自然言語処理や機械学習の話ばかりしていたけど、一応データ圧縮も研究してます。
未踏Youth(2年前)からどんな経緯になっているかというと

未踏Youthは、データを分解して(LZみたいに)符号化するのだが、オンラインで分解するのではなく、全体をみて、部分列に分解する。この時、分解は最長部分列が必ずしも選ばれるのではなく、(重なりのない)出現回数を考慮にいれて分解する。これでデータは部分列に分解され、部分列の表と、その表によって、各部分列が符号化されて、圧縮される。

いいところ・・・復元のときは、符号化されたデータを部分列の表を参照しながら復元するのと、表の更新は必要ないので、LZ法より速い 圧縮率はLZぐらい さらに部分列に分解されているデータをさらに解析することによって、隣あったデータだけではなく、遠くの依存関係まで利用できる可能性
わるいところ・・・全ての部分列を列挙(Suffix Arrayを用いて仮想的に列挙)するのが、計算量、メモリ量的に非常に大変。大きいデータになればなるほど苦しい。

未踏(1年前) 未踏では圧縮ではなく自然言語処理やデータマイニングが話しの中心。これが発展してこの前の自然言語処理研究会の話であったClass Modelの高速化、拡張やBIP Contestにちょこっとだけつながる。ここではそれほど圧縮はしなかったが、圧縮率以外にもいろいろ改良の可能性はあるのだなぁと考えた。CSAやCSTのように圧縮したまま検索、部分文字列一致などに使えるという話以外にも、部分復元、ランダム復元の話にも興味がではじめてきました。

というわけで今は圧縮率がよくて、対象データが数10Bから数GBで、復元時に省メモリ、高速、どこからでも復元、検索もできるようなやつを作ろうとしています。理想は高く。

現時点、とりあえず研究用にできている圧縮プログラムは、圧縮率は結構良いとして苦手なデータはなくて、復元はかなり高速で、ランダム復元もできる。あと対象データがGBoverでもできるようにいろいろ工夫して、復元をコピーの数倍程度に高速化して(こうなるとIOがボトルネックぐらい)、あとは検索もできるようにか。今月中にできるかな

他の話題では、圧縮データがいろいろばらばらにあって、それぞれから必要なデータだけをとってきて、復元するようなやつとか(RAIDみたいなものだと)。 RAIDと同様の効果が得られるが、単純にはいかないらしい。

グラフデータの圧縮とかも個人的には盛り上がってきてます。とんでもなくでかいグラフデータが最近ゲノムやらWebをはじめとしたデータマイニングで必要となってきているみたいなので。うまく表現すれば、アクセスも速くなるという一石二鳥のメリットもある。これと似た話で3次元データの圧縮。これは、数学の高度な理論を使ったうまいやり方があるというのを立ち読みでちょっとだけ知りましたが詳しくはしらない。

という現状。圧縮のおもしろそうな話あったら教えてください。ここのコメントか、BBSなどなど

| | Comments (0) | TrackBack (0)

2004.09.20

どすこい

よく上京してくる親と、なぜか相撲を見ることに。
国技館自体は近くにきたことがあったが、入るのは初めて。チケット売りに東関親方がいて、驚いた。武蔵丸とか貴乃花とかもそのあたりにいた。よく相撲の会場にいるピンクの人もいた。場内だけ聞けるFMが、型破りでおもしろかった。いろいろな裏の話がきける。最近の若者力士は厳しくするとやめてしまうらしく、難しいらしいとか、ご祝儀をどうするとか、どの人とどの人が仲良くて仲悪いかとか。結構近くに見れたし
終わった後にテケテンって聞こえる太鼓の音は、あれはテレビのBGMではなく、本当に鳴らしている。あの後もずっと続く。

文書分類、クラスタリングはいろいろ論文を読み進めていて面白そうなのがいくつかあった。いろんなところで、話がつながってくるのだなぁと驚いた。

| | Comments (1) | TrackBack (0)

2004.09.19

文書クラスタリング 文書分類

調べて見たら、うわさにはきいていたけど盛んすぎ・・ 何読んで、見たらいいんだー。かたっぱしからよんでいくしかないか。単語ベースのベクトル空間で分類、LSIとかはいいとして、他にもSuffix Treeをつかってクラスタリングとかもある。集めた論文がざっと30ぐらい。関連調べたら100こえるなぁ。このへんは今から参入するとすごい競争にまきこまれるから、もうちょっと未開拓なものも考えて見るか。
最近思いついたものが既にありそうな気がしてどきどき。今まで何度、悲しい思いをしたことか。

| | Comments (183) | TrackBack (0)

2004.09.18

NLP研究会とか

初早稲田。大隈講堂がすばらしかった。早稲田、家からめちゃくちゃ近いかも。駒場より近い
自分の発表は質問時間を2分残し終了。長すぎ。練習しておけばよかった・・しかも自分のパワポよめないしΔをデルタと読まずにあやうく三角といいそうになった。あと、他の人の発表をみて、プレゼン技術をもっと磨かなければと思った。動きを入れることはもちろん必要最小限の情報を入れるとか、でも逆にそれだけで理解できることも必要。精度と再現率の向上みたいなものか。

Class Modelの課題として、言語モデル以外の応用が難しいこと。前後に出現する単語の出現状況によって、単語をクラスタリングするため、必ずしも自然言語の意味論とは一致しない。応用用途の一つとして考えているのは固有表現抽出への利用。決まり文句みたいなものがある場合はその用語がうまく抽出されるため(○○さん の○○は同じところにクラスタリングされる。 後にさんがでるため)、ある意味抽出ルールを自動的に得ていることになる。BIP2004で少しだけやったけど、もうちょっとつめてみたい。あとは、前後に出現するということではなく、もうちょっと柔軟に周辺の情報を使ってクラスタリングするのもありかと。

他の発表で面白かったのは、まずは、文書分類に最大マージン法を使うというもの。アイディアの中心は文書を分類するとき、教師付きデータの各文書にはカテゴリが複数ついている場合、(例えば この文書のカテゴリは野球・経済 この文書は医療・地域・福祉)各カテゴリは相関のある場合があり、独立に扱った場合にカテゴリが複数重なった場合をうまく扱えない。例えば、プレゼンの例からでは量子計算の文書は「量子物理」と「計算科学」の両方のカテゴリに属するが、それぞれのカテゴリを独立に学習するため、ある文書が与えられた時にその文書を「量子物理」かつ「計算科」の両方のカテゴリに属すると判定することは難しい。量子物理かつ計算科学の文書はqubitという一般的には非常に稀な単語が出現するのに、その情報がうまく使えないのだ。そこで、カテゴリが複数重なっている場合は、それを一つのクラスとして扱ってしまう。つまり、AとBとCの三つのカテゴリがある場合に、「A」、「B」「C」「AかつB」「BかつC」「CかつA」「AかつBかつC」「どちらでもない」というふうに文書を分類し学習しておく。カーネルを用いて特徴空間に写像した上で分類をする。このままだとN個カテゴリがある場合に2のN乗個のカテゴリが存在し、計算量の爆発と学習データが疎になるという問題が発生する。前者の問題については、一般のカーネル法と同じようにうまい計算を行うことで、カテゴリ数がn個のときnの三乗でできるアルゴリズムを設計して解決。後者の問題は最大マージンラベリングを用いることで解決。SVMが、分類のための超平面を、正のデータ、負のデータからもっとも離れたところにおくことで、過学習を防ぐのと同じように、最大マージンラベリングは他のクラスへの距離が最大なところにそれぞれのクラスに属する領域を設定する。

PCFGに分岐HMMを使う話もおもしろかった。PCFGをそのまま用いると、様々なところに出現するNP(非終端記号)が同様に扱われてしまうことを、出現した場所(親の記号とか)や、主辞を非終端・終端記号とペアで用いることで、非終端、終端記号をさらに細分化して精度をあげるというのを、そもそも、非終端記号や終端記号は様々な隠れ変数から生成されると仮定して用いることにより自動で細分化を行うというもの。

Q&Aシステムについては、ほとんど無知だったのですが、ちょっとだけわかったような気がします。精度、再現率ともにまだまだ改善の余地があり、とてもアクティブな分野。ちょっと調べて見よう。

Web情報を用いた技術では、テストデータがないことが最大の問題というのもきいた。一部分だけとりだしてくると、リンクがぶちぶち切れていて、うまく実験評価をできないことが最大の問題であり、逆にQ&Aシステムががんばってテストデータを作ったことにより今これだけはやっているそうだ。

夜はちゃんこ祭り。いろいろな話をしました。人を笑わせるのがいかに大変なことかとかを話して、昔の苦い思い出をいろいろ思い出した。1年の時は看板を叩いてひたすら作ったり、2年の時は合宿の調整とか、今となっては思い出せない団体のしょうもない会議に出席したり、いろいろあったなぁと思い出しました。

ブログだと分けて書いた方がいいけど、面倒なのでさらにつづけてかくと、googleは予選通りました。400pointの問題をまちがえていたらしい。ハンドル名はnarita。

| | Comments (0) | TrackBack (0)

2004.09.16

googlejamとか研究会とか

研究会の資料。論文は前にもアップしたけど、こちら。 パワーポイントはこちら
夏休みに作った資料やら、プログラムはホームページに順に整理してアップしていきます。この研究会と若手の会とBIP Contestと後、直前の演習3今井研追加発表のやつとか。

googlejamは最初にいろいろトラブルあったり英語がわからなかったりして苦戦したが一応予選を終えて結果まち。時差の計算が一番難しい。PM12:00って本当に午後0時なの?

| | Comments (0) | TrackBack (0)

2004.09.14

本屋

でかい、本屋がたくさんできるみたいで。
今日は、丸の内オアゾに行ってきました。この再開発の目玉というか95%は丸善なのですが、かなり大きくて、本の種類も非常に多かった。コンピュータの洋書もなかなか多くて、値段は残念ながらアマゾンにはかなわないが、内容立ち読みしてみるならいいくらいかも。今度、一日立ち読みしてみたい。かわりに他の買わないとつぶれてしまうが。新宿にジュンク堂ができるみたいだし、大型書店が多いなぁ。
地元の阿佐ヶ谷は、世界最大のアニメ製作の街だけあって、品揃えがなかなかマニアックなのがそろってる。

あとは資料作ったり、プログラムしたり。いつもどおり

| | Comments (0) | TrackBack (0)

2004.09.11

初秋

ちょっと涼しくなってきたかなぁ。レポートは、気合いを入れて一応終わらせた。
googleのシステム構成や、ファイルシステム、エラー処理などの論文はとてもタメになって面白かった。1クエリーに対して数百MBのデータを読みにいって、ランキングして、数百億CPUサイクルが必要。15000台の通常レベルのPCを、ソフトウェアによるエラー処理、負荷分散で、つなげてやっているらしい。システム決定の際の判断基準が全てコストパフォーマンスが最大かどうかで決定しているのが、はっきりしていてよい。

ハードウェアのキャッシュ上で圧縮をする方法についてもなかなかおもしろかった。やっていることは、0の連長を見つけて圧縮したり、小さい数を32bitで表現せずに少ないbit数に置き換えたりするぐらいなのだが、これでも半分ぐらいになるらしい。もし圧縮できない場合は、圧縮せずにそのまま保存する。復元はハードウェア支援で5クロックでできるので、L2キャッシュミスを減らすぐらいなら、とても効果があるらしい。

さて、実装するか。9月終わりまで20日ある。何個できるかなぁ

| | Comments (0) | TrackBack (0)

2004.09.10

椅子が来た

ハンズが安売りセール中だったので、椅子を買った。パソコンのところに置いてある椅子が小さくて(俺が大きくなったのか)いいのないのかなぁと思ったら、いいのがあったので思わず買ってしまった。使い心地はかなりよい。これでいろんなことがはかどるといいのになぁ

でも、物事はそうはうまくいかず、いろんなことが予想以上に時間と手間がかかっている。課題は最低三つ論文読めば済むのを既に6つぐらい読んでしまって、どれもいまいちだなぁ(というか課題の要件を満たしてない論文だと最後まで読んでわかった)ということでボツ。それで行きついたのははキャッシュ上でハードウェア支援付きで圧縮するやつと、googleのシステムについての論文かと。他のも含めて課題は今週中に終わらせたい。

検証用?の実装も二つほどしていて、できたら今月末までは終わらせたい。日記に少しずつ今やっているネタとか書いていったらいいんだけどねぇ。実装もうまくいったら公開したいなぁ。去年の未踏のやつも整備して公開していかないとな。

全部希望形。朝起きたら小人とかやってないかな。そもそも朝起きたいな。あー、これも希望だ。朝起きるのも小人がしておいてほしい。

| | Comments (0) | TrackBack (0)

2004.09.06

若手の会

行ってまいりました。現地に到着するまで、ずっと三重県だと思っていた。どうやら愛知と岐阜の間らしい。無人駅。

様々な分野、経歴、立場、の人が集まっていました。面白かったです。

経験したこと、聞いたことは少しずつ書いたり、話していきます。

したいこと、しなければならないことが多いですなぁ。何から手をつけるか。

| | Comments (0) | TrackBack (0)

2004.09.04

明日から

情報科学若手の会です。気合いいれて、いろいろ話をして、きいて、考えてきたいと思います。

Kernel本をようやく読んだ。String Kernelと、Tree Kernelが特に気になった。文書分類で単語分類を利用するやつがあるが、それをうまく応用して、文書分類できないかな。くんでみよ。あぁ、手つけすぎだ・・。ちゃんと一つずつやっていかねば。

では二泊三日でいってきます

| | Comments (0) | TrackBack (0)

« August 2004 | Main | October 2004 »