« April 2005 | Main | June 2005 »

2005.05.29

よくあること

改良した結果、精度がベースラインを大幅に下回る。くじけない。

帰り道であれをこうしたらうまくいくんではないかと考える。夜実装。学校へ行き結果を見て愕然とする。卒論時期に似ている。

タンパク質名やDNA名などを抽出するタスク。エラー解析してみると、素人目からはほとんどあっていると思ってしまう。実は固有表現出タスクは最初にどのように各固有表現を設定/定義するかが一番重要な気がする。それが一番難しいだろうけど。

型本やっと届いた。型の話は付属情報付き構造マッチングとして応用範囲が広そう。もちろんプログラミング言語への貢献はとても重要だけど

外は五月祭。俺も今手をつけているのが終わったら遊ぶぞ。

| | Comments (0) | TrackBack (0)

2005.05.28

df2/df

churchが提唱したキーワード抽出のための基準。文書群が与えられた時、ある単語wに対するdf2(w),df1(w)は同じ文書中に1回以上出現した場合の数をdf(w)(document frequency) 2回以上出現した回数をdf2(w)と定義される。
このときdf2(w)/df(w)は単語wが1度出現した時、同じ文書中にもう一度出現する確率の近似となっており、その値はその単語の出現頻度や文書頻度とは無関係であるという面白い性質がある。そしてこの値は文書を表現するような内容語であれば高い値となる。(内容語であれば、一度出現したらもう一度でやすいが、機能語であれば一度出現しても、別にもう一度でるとは限らない) シンプルだけどかなり強力。SAがあるとさくっと実装できる。

| | Comments (6) | TrackBack (0)

2005.05.27

CSA

今日はMEDLINEという医学論文のアブストラクト集のSuffix Arraysを構築し、そこから必要な情報を抽出する作業を進めた。

Suffix ArraysとかSuffix Trees周辺の話は近年急速に研究が進み、1997年にGusfieldによるSuffix Arrays、Suffix Treesに関する有名な本が出たときと状況がかなり変わってきている。

どうかわったのかを簡単にまとめると、データ長がnの時

・Suffix Arraysを保存するのに4n byteではなく大体0.8n byteぐらいですむ方法が考案された。
検索するときに元テキストは要らない。
・Suffx Treesを保存するのに数十byteではなく大体2n byteぐらいですむ。これも元テキストは要らない。
・完全パターンマッチングだけではなく、近似マッチングもO(n)ではなく、O(log n)でできる。
・構築手法がいろいろ提案され非常に高速になった。1GB程度で10分程度。線形時間
・実装も簡単になっている。昔のSuffix Treesの線形時間構築手法はとても簡単に作れるものではなかったが、今ではSuffix Arrays構築 → Hgt配列構築 → Suffix Trees構築というルートができた。200行ぐらいでできる。

このへんまとめた本がでるといいなぁ

| | Comments (5) | TrackBack (0)

2005.05.26

Semi Markov CRF

やっと動いた。これでベースライン。一応CRF,MEMM,SVMなどの既存手法よりは結果がいいみたい。でもこれを論文にしようと思うともう一工夫しないといけない。あと1週間ですか。エビスおいしい

| | Comments (0) | TrackBack (0)

2005.05.23

23

プログラミングとか、論文読みをするために渋谷にいく。家から渋谷は15分と近い。しかし今日の渋谷は競馬のオークスがあるせい(渋谷には場外馬券売り場がある)と、道で人が踊っていたため(何祭りかはわからなかった)はずれのニューヨーカーズカフェにいった。ルノアール系列ではパソコン用のコンセントがつかえる。でも、すごい混んでいたため、長居しづらくすぐ出る。

スターバックスへ移動。隣で入学したての大学生達が話している。おそらく東大生。話をきいていたら、自分の昔を見ているような、ちょっと歯がゆいなんともいえない気分になる。

ソースコードの大部分を一から書き直したい衝動に何度もかられながら、汚く直しておく。

本屋で、薦められた福沢諭吉とか勝海舟の本を買ってみる。石田衣良の本もR25で読んだ時うまいなぁと思っていたので買ってみる。

帰り道、神泉まで適当に歩いていけるかなといってみる、怪しいところに迷いこみ断念し渋谷に戻る。

家に帰ってしばらくぶりの洗濯。待っている時間、大人買いしてしまっためぞん一刻を読んでみる。今では漫画の長者番付一位であるこの著者だが、いつごろこの本を書き始めたのかと思い調べてみると23歳。自分と同い年であったことに、すごい衝撃を受ける。

夕飯を外で食べ損ねたので、近くのクイックガストでがつがつ食べ帰る。はやく寝て朝早く学校に行こうと思っていたが、買った本を読み始めてしまったので眠れず・・今に至る。

| | Comments (0) | TrackBack (0)

2005.05.20

NE

Named Entity Extraction : NE,固有表現抽出をやっています。文書が与えられた時にそこに出てくる人名や地名、タンパク質名を抜き出せというタスク。一見、辞書があればよさそうだけど、辞書だけでは全部網羅できない場合が多く、また多義語だったり、複数名詞や接続詞が含まれる場合とかは辞書引きだけではうまくいかない。そこで周辺単語等のコンテキスト情報を使って、今見ている部分列が固有表現であるかどうかを判定したりする。
現状では、まずはSemi Markov CRF動かしてそれを改良しようとしている。でも時間があまりない・・。妄想としてStructured Large margin approachの話とそのまま合成できそうな気がする。そうなるとカーネルが使えて、辞書情報も使える。これいいな。でも気づいたのが遅く、今年中に誰かが出すかもしれないし、自分も一から実装するのは難しい

NEの実際の応用時にはクエリーの全部分列と膨大な量の辞書とのマッチングが計算量的に問題となる。このマッチングは重みつき近似マッチング。でも、これは最近提案された近似マッチング手法と今回開発した手法を組み合わせれば、アルファベットサイズをS、クエリー長M、辞書のエントリー数N、近似のedit distanceをAとすると、エントリー中の要素との最小コストマッチングがO(M(SM)^A logN) で求まる。実際は重みによる枝狩りでこれよりはるかに小さくできる(はず)。これも鋭意実装中。

演習3の発表がありました。みなさんの内容はみんな気合入っていて面白かったです。濃密な一ヶ月であったならば幸いです。これからの人もがんばってくださいな。

聞いていて思ったこと

Featureの数が大量にあって、文書も大量にある場合のクラスタリングとか分類で効率的な方法ってあまり知られていないかもしれない。高次元データ構造の話ならICML2004のチュートリアルであった。このへんを組み合わせないと、文書クラスタリングとか分類は実用的には難しいかも。でも一から作るのもかなり大変そう。こういうやつのライブラリってないかな。

検索やクラスタリングの場合、その検索手法やクラスタリング手法依然に最初の形態素解析処理がかなり重要(特に日本語では)。数単語の連なりであるN-gramを単語に加えて入れたり、文字単位から単語単位までを確率的に入れたり手法などが今までに提案されています。今試しているのが、最初に単語に分解せずに全部分列を列挙して、それぞれの重みを決定して(重複も考慮して)それをFeatureにいれるというもの。こんなめちゃくちゃなことをサポートしているのがいろいろなアルゴリズムだったりデータ構造であるんだけども(これも今書いてます)

朝になってしまった。

| | Comments (0) | TrackBack (0)

2005.05.16

おどる

「交渉人 真下正義」見てきました。スタッフが前と変わってないので期待していたけど、やはりおもしろかったです。ウィットがきいている。

今日はゆっくり休んだ。さて、明日からもがんばろう。 

| | Comments (0) | TrackBack (0)

2005.05.13

ミーティング@横浜

横浜での未踏ミーティング。CSA、CSTの各機能が予定の計算量で完動したのが前日の夜でありそれから資料を作りました・・
Suffix Treesの1文字あたり必要なbit数は大体17bitになりました。このうちCSA(葉情報)を除いた分が10bit(理論値は6bit)。これ以上減らすこともできるけど、それより今重要な課題は、構築に必要なサイズを今の72 bits per characterから最終出力と同じくらいの17bitぐらいに減らすということ。そうしないとGB overのデータ上でSuffix Treeを作れない。Incremental にCSAを構築する手法は提案されているが、実用上は圧縮されたpsiをどのように更新していくかという工学的な問題がある。幸い、できそうな方法は思いついているけども

それが終わり次第、これを使っていろいろアプリケーションを作ろうと。後はSuffix Arrays上の正規表現処理とか。もちろん正規表現の全部は対応できないけど大部分はできるはず

| | Comments (4) | TrackBack (0)

2005.05.06

Compressed Suffix Tree

去年演習3で調べてから、ちょうど1年目で動くところまできました。感無量。論文調べた時は実際に動くかどうか怪しかったのですが、いろいろなアイディアを組み合わせて動きました。

今回、CSTの実現に不可欠な(厳密)単調増加列の符号化について、rangecoderのようにbit演算をほとんど無くした方法を開発しました(再発見かもしれないが)。単調増加列の符号化とは、S=(1,4,7,10...,)のような数列に対して、select:N番目の数を返せ(例select(2)=4 select(4)=10))、rank:N以下の個数を求めろ(例 rank(1)=1,rank(3)=1,rank(5)=2)という二つの操作を定数時間で行える符号化が要求されます。実際にどれくらい速いのかとか、符号化効率はどうなのとかいろいろありますが、それは今後じっくりやります。テーブルサイズを小さくしてキャッシュにのったり、アクセスを必ずシーケンシャルにするようになどと実装面でもがんばってます。

まだまだ実装しなくてはいけないものがたくさんあーる。時間との勝負

| | Comments (0) | TrackBack (0)

« April 2005 | Main | June 2005 »