« May 2005 | Main | July 2005 »

2005.06.30

普段の水曜は休み

よどおし資料つくって午前発表してきて、午後は寝てました・・。おきたら夜になってて少し寂しい。でも、朝9時と間違えて学校いこうとしたから、夜とわかってちょっと得した気分。

| | Comments (0) | TrackBack (0)

2005.06.29

そんなに眠くないよ

実装めきめき。ここしばらくずっとSuffix Arrays/Trees関連。結構いろいろなことが現実的な計算量、メモリでできるようになってきた。後は詳細実験か。勉強もかねてFM-indexを実装しておこう。メモリいくらでもほしいなぁ。明日の発表準備。ぐひぃー

| | Comments (3) | TrackBack (0)

2005.06.24

sambaとrsync

って同じ人が作ってるんすね。知らなかった。両方とも、ものすごくお世話になっているからなぁ。
差分って使わないとね。というわけで(Compressed) Suffix Arraysで一部分だけ更新する際に、うまいことできないか考えてます・・。ブロックごとに分けてψの方を保持しておけば追加はできるって論文は出ている。そのまま逆にやれば削除できそうだよなぁ・・。置き換えるのは削除+追加だからできそうだなぁ。

| | Comments (0) | TrackBack (0)

2005.06.19

ぺりかん本

「Hierarchical Bayesian Optimization Algorithm,」 Martin Palikan
名前から推測がつかなかったが遺伝的アルゴリズムからスタートする話らしい。どうつながるのかわからなかったが、今持っている集団候補から次の候補を探すところで集団候補を教師データみたいに使って次の候補を探すらしい。この人の主張である複雑な構造をもった問題も小さい問題に分割できて、その上で探索すればいいじゃないってところはまだいまいち理解していない。なかなかおもしろい

| | Comments (0) | TrackBack (0)

2005.06.18

BWT ten years later

というworkshopが昨年夏に開かれていたそうです。たまたまみつけた
http://dimacs.rutgers.edu/Workshops/BWT/

このへんの話の各方面の第一線で活躍している人達が集まって発表している。豪勢な顔ぶれ。

ちらっとみた感想

・BWT開発者の一人のBurrowsが今はgoogleにいるそうだ。そこでハードウエアにあわせたBWT構築アルゴリズム(おそらくランダムアクセスが少ないとか局所性が高いとか、更新できるとかかな)を研究しているらしい。80億ページでSuffix Arrays(現実的にはFM-indexとか?)作ってしまうんだろうか

・karkkainenさんが、省メモリでBWTを作る話。これってwhiteさんがやっているものと似ている?

・rsync(違う場所にあるファイルの同期をとる)の基礎となるファイルの差分と、その圧縮情報(おそらく一致した部分のコンテキスト情報を使う)を求める技術の話がかなり盛り上がっているみたい。現実世界ですごく需要があるからなぁ

それと別にcsaとFM-indexをゲノム上に作って比較した話もみつけた
「Practical aspects of Compressed Suffix Arrays and FM-Index in Searching DNA Sequences.」 Wing-Kai Hon, et al.
最近はSuffix Arrays関連の技術はある程度そろってきたので、実際のその性能はどうなのという評価などの論文が増えてきた。長いクエリーになればなるほどForword Searchingの方が速くなるというのは気づかない盲点だった。確かに長いクエリーではマッチの後半になればなるほどマッチ候補の数が減るので速い。

| | Comments (46) | TrackBack (0)

2005.06.17

映画

四日間の奇蹟を研究室の人たち見てきた。内容はこれから見る人のために言わないとして、個人的には映像中の海に癒された。空も広かった。ロケ地、角島っていうそうです。原作の話を後で聞いたらいろいろなるほどってところも結構あった。ピアノも昔は少し弾いたこともあるし、ちょっと練習してみたい気にもなった。

| | Comments (0) | TrackBack (0)

ディリクレ分布

単語/文書クラスタリングとかを調べていくうちにディリクレ分布にたどりついた(というか、そういうのが必要だなぁと思って調べていたらそのものずばりがディリクレ分布だった)。ブログやペーパーで見かけていたが今まではあまりピンときてなかった。ディリクレ分布は n次元単位ベクトル上での確率分布であり、訓練データからその確率分布をn-1個のパラメーターとして求める。この分布を使うと、同じ単語が続けて出やすい現象(Trigger Model)や、似た分野の単語が出やすい(Class Model)とかもモデル化することができる。
mochihashiさんのところにあったが、この分野もFeatureの数が無限(サンプル数は有限)の場合も扱えるやつとかがんがん話しが進んでいるみたい。恐ろしい。基礎をしっかりやります

| | Comments (10) | TrackBack (0)

2005.06.14

MT

機械翻訳の話を御茶ノ水で聞いてきた。
googleの人はWebデータとか対訳コーパスたくさんつかって、かなりいい結果が出たよという話。今年の夏にNIST/MTで発表されるんだとさ。
それに加えて、フレーズとフレーズの意味的近さをフレーズが出現したドキュメント中の単語やフレーズ同士の内積で測るということをいっていた。手法自体は昔からあるものだが、なにしろ80億ページと規模が違う。わざと飛ばしていたのかもしれないが、ぱぱっと飛ばしたスライドにどのように計算をしているか(そして打ち切っているか)が書いてあった。たぶんこれが一番重要。気になる。
質疑応答の時に、Webデータは信頼の無いデータだらけで、フィルタリングとかしているんですかという質問があったが、回答では50%の情報が間違っていても残り50%の正解は収束していてピークがあるから、そこのピークをとればいいよという回答。基本的なことだが忘れがち。Webデータのように信頼性がないが、とにかく量が多いデータはこういったピークをとるような処理をするとうまくいくんだろう。たいてい、平均とかとってうまくいかないといって使えないデータだといってしまうのだが。

次の富士通の方の話はいろいろ知らない事情を教えてくれておもしろかった。機械翻訳(電子辞書とか除く)の市場は50億ぐらいなのだが、翻訳事業全体では大体1兆円ぐらいらしい。企業内翻訳とかがとても多いんだそうだ。で、翻訳結果を完璧に出すのではなく、翻訳作業を助けようという方向でがんばっているらしい。後はルールベース+用例ベース+統計的(機械学習)ベース をもっと考えましょうという話

昨年やりっぱなしの単語クラスタリングの話とかがでてきて驚いた。あれもちゃんと形にして残しておかないとうずもれてしまう

| | Comments (11) | TrackBack (0)

2005.06.13

土日

金曜が忙しかった反動で土日は大人しい。気持ちが入らない
輪講の資料を読んで作る。あとバイト。プログラムを結構書いた。掃除をした。

最近いろいろ消化不足。じっくりいきましょう。

| | Comments (1) | TrackBack (0)

2005.06.10

コンピュータ将棋

ミーティングで研究員の方による今年のコンピュータ将棋選手権で優勝した激指の実装内容等いろいろ聞く。以前、教えてもらったとき、激指が強かったのはもちろん将棋の局面が一次元評価関数で表現されているのに衝撃をうけたが、実装内容はもっとやばかった。用いている手法もすごい上に激チューニング。

優先して探索する場所を求める方法と、それぞれの局面での評価値を求めるところとが今はわかれているが究極的には連続的につながるのだろうか。そうなると人と同じようにもっと探索する場所をはっきりと検討をつけて数十から数百局面しか求めなくてもすむようになるのかなぁ。

その後は論文直しといろいろ他の人の実装を調査中。

| | Comments (0) | TrackBack (0)

2005.06.09

水曜

は授業が無い。こういう日こそ、累積しているキューを消化できるはずだ。しかし、おきたら笑っていいともが。
今日はなんとなく西に行くことに。HPSG本を気持ちをこめて読んだらまぁまぁ理解できた。その後未踏のそろそろfix版実装をぼちぼちと。ライブラリを公開するときはCSA/CSTをSTLみたいに使えるようにする予定。単純なマッチングだけじゃなくかなり高度な機能も使える予定。あくまで予定。

父が仕事で上京していたので、飲むことに。明るいのに・・

家に帰ってサッカーがはじまっていたが寝てしまった。以前もそんなことがあって後悔して気持ちがあったので気合いで眠りのそこから戻る。その瞬間、日本が得点。安心して眠る

おきた後、ジョナサン。輪講資料を作る。店出るまで注文しなかったような。常連だからいいのか

| | Comments (2) | TrackBack (0)

2005.06.08

こ、これは

自分のカメラレディがまだなのでなんともいえませんが、sentiment classificationで、positiveとnegativeのbinaryから4つとか5つに増やしましたよという論文が同時期に出されているもので少なくとも二つあることが最近わかった。

Bo Pang, Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales, ACL2005
Koppel, The importance of neutral examples for learning sentiment, FINEXIN 2005

これらとの比較を今から書くわけですが、同じ拡張したという話でもやっぱり主張している点とか、状況、考察が違うわけで。ただ、Pangが使ったデータをみんなが使えるように公開しているのはすごくありがたい。自分のはちょっと著作権とか怖くて公開できない。Pangはデータを買っているのだろうか。とりあえず同じような論文ですよってことで連絡をとってみることにした。まぁ、おもしろいのはここからだから、ぼちぼちまたがんばりはじめないと。

| | Comments (2) | TrackBack (0)

2005.06.07

スミノフとシロクマ

合うなぁ。

日曜日は肉をもりもり食べました。

午前統計輪講。決定木周辺の話。階層型マルコフモデルも。午後CCG。ほぼ寝る。演習3、検索システムについて。論文直し。

何かを評価する尺度として5段階評価とか100点満点で何点かというもの以外にMagnitude Estimationという方法があるんですね。人に文章読ませてこれが文法的にどれくらい正しいかを1,2,3,4,5でスコアづけしてもらうと、2とか4がつけられにくいとかいろいろ人による癖があるが、最初に適当に値を決めてもらい、他の文法がその最初につけたのと比較しどれくらい受け入れられるか(例えば最初の文章を適当に10と得点きめて、次の文章が文法的に3倍ぐらい正しいなぁと思ったら30をかいてもらう)ということで得点づけ、最初にきめた点数でわった値でスコアとするもの。こっちのほうが実験の再現性とか、被験者同士の値が合いやすいとかあるんだとさ。文法じゃなくて俺の場合は、文章のお薦め度合いなものを測るタスクをやったわけだけど。

めしくって泳いだ後に、簡単に直して添削をお願いする。HPSG読みながら終電で帰宅。家帰ってバイト。こんな毎日です。

| | Comments (0) | TrackBack (0)

2005.06.05

Semi Supervised Learning

正解がついた少しのデータと、正解がついていない大量のデータを組み合わせて、正解がついたデータだけを使った場合よりも、賢く学習しようというSemi Supervised Learningの話は近年注目されています。それは正解データを作るのが大変であるのはもちろん、人がそれに近いことをしているからだろうという推測があります。

このSemi Supervised LearningはSupervised Learningと違っていろいろ独立した視点から考案されてます。例えブースティングとか、co-trainingとか、あとはJoachimとかによるグラフによる解釈とか。でもそういったいろいろな方法がManifold Learningという統一的な視点で説明できるよという話が今年のICMLチュートリアルにあるみたいです。その発表資料はまだないけど、その人のページにtechrepoがおちてた。Manifold Regularization: A Geometric Framework for Learning from Examples。このまえのSpectral ClustringとKernl K-meansが同じ枠組みで説明できる話といい、今魑魅魍魎とでている多くの話が実は表現をかえているだけで同じことを扱っているんだろうな。そして、多くの話の大部分は再発見だったりするんだろう。再発見は発見と同じかそれ以上に重要だと思うけど。

先輩から教えてもらった、動的計画法で解ける問題をprologみたいな形で入れると、それを学習、デコードするC++コードをはく驚異的なソフト、dyna。 今、NLPで出ている大部分の話がこれでさくっと作れる。collinsパーサが40行ですか・・

| | Comments (5) | TrackBack (0)

Gの世界

バイト場で数百MからGのデータを扱っているとスケーラリビティがいたいほどわかる。計算時間試算で20000時間って出た。ちょっと長い・・。いろいろ工夫して200時間。これでも長いなぁ。しかもこれで終わる保障はない。こういう時間かかるやつは、なんだかんだいって処理している間様子をみていないといけない・・ぐひー

| | Comments (3) | TrackBack (0)

2005.06.04

HPSG5

学校についたら、どうやら輪講が始まる時間を勘違いしていたらしい。2時。ここからHPSG輪講2連ちゃん。5時間。おなかいっぱいです。でも来週俺が担当。CCG (conbinatorial categorial grammar)も並行して輪講しているのでこっちとの比較もしてしまう。まぁ、どれがいいとは決められず一長一短なのだろう。数学的枠組みがもと成熟するといろいろな現象が統一的に説明できるようになるのかもしれない。

Suffix Arrays上で正規表現を扱う方法を資料作りながら考えてました。正規表現、つまり決定的オートマトンをSAで再現しようと考えると、オートマトン中の各状態とSA中でのその状態を満たす範囲を対応付けることに相当する。もし遷移前の状態でこの範囲が連続しているのであれば次の状態での範囲を求めるのはO(logN)で可能。問題なのは連続していない場合。でもこれは分かれている全状態に対し求めれば一応はできる。状態の遷移で閉路がある場合は、最長一致を取ろうとかの原則ならばできそう。となるとなんかできそうなきがしてきた。正規表現の形で計算量が変わってしまいそうだけどO(logN)はかわらない。

| | Comments (0) | TrackBack (0)

2005.06.03

よじれる

朝はやくおきていろいろなソースコードをよじれながらえんえんと読んでから授業。午後はミーティング。そして授業。ちょっとプログラミングしてから、たまっているプレゼン資料をまとめて作りはじめる。ご飯食べて泳ぎに行く。泳ぎ方を改良中でだいぶ楽に泳げるようになってきた。2km/40分も近いうちにいけそう
その後もプレゼン資料作る。とりあえずこんどのセミナー用のSuffix Arraysの最近の話をまとめたやつはできた。論文になってないいろいろな話もまとめていて、プレゼン終わったらアップする予定です。

はやねはやおきの生活にしたいと思っているが朝のニュースが始まる時間に・・

| | Comments (0) | TrackBack (0)

2005.06.01

75%の壁

タンパク質名やDNA、RNA、細胞名などの固有表現認識。自分は今Semi-Markov CRFでやっているが、同じFeatureを使ったとしてもMEMMやスライディングウインドウ方式がだしている75%の精度に勝てない。Semi-Markovでそのまま素直にやるとNEの外にあるやつ(Outside)もがんばって当てようとしているのではないかという話になった。CRFと比べてSemi-Markov CRFでは負例が非常に多くなる。それが原因なのかなぁ。わからん
もう急ぐ必要もなくなったのでもう一度ソースコードをきれいに書き直すことにした。外部情報もうまくあわせれば精度/再現率は90%ぐらいまでは行くだろうといわれている。まだまだ

| | Comments (0) | TrackBack (0)

« May 2005 | Main | July 2005 »