« October 2005 | Main | December 2005 »

2005.11.26

ミスマッチの実装

Suffix Arraysを使ってミスマッチ検索を実現する論文が出ていて、これをwavelet tree + FMindexでもできるのではということで実装。

ターゲット長n、ターゲットのk次エントロピーをH_k、パターン長m、アルファベット数A、が与えられた時、ミスマッチを最大k(ここでのミスマッチはedit distanceの意味。削除、置換、追加からなる)まで許す、ターゲット中のクエリーにマッチする全てのポジションをnH_k bit 作業領域を用いて((mA)^k *m * logn + occ * logn) もしくは ((mA)^k * log^2 n + occ * log n)時間で報告できる、ただしoccは報告個数。

やっているのは、最初にパターン中の全ての部分列に対応するsuffix arrays中の領域をwavelet treeを使って求める(O(m^2))。あとはそれらを組み合わせて、クエリーにミスマッチが加わった形の新しい候補を作って調べている。(明示的には作らずに端から順に作る。)
例えばクエリーに"missisippi"が与えられたら"m","mi","mis",...,"i","is","iss",...,"pi","i"と全ての部分列に対応するsuffix arrays中の領域[sp,ep]をそれぞれ求める。次にこれらを順に組み合わせる。例えば3文字目のsが無くなったものを探すフェーズでは"mi"に対応する[sp1,ep1]と"sisippi"に対応する[sp2,sp2]を表からとってきて"mi":"sisippi"に対応する領域[sp,ep]をlognかmの速い方で求める。

実用的には(mA)^kの部分は殆どが候補を作る途中でターゲット領域に無いことがわかって打ち切られるので、もっと小さい。

prefix-freeの正規表現もこの勢いでできないかなぁ。夏ごろやるぞと言ったまま。

| | Comments (0) | TrackBack (0)

2005.11.25

本読み

もう金曜なのか。水曜休みだと短く感じるなぁ

今週は時間が比較的あったので、昔買っておいたままの本を読んでみました。

The Spatial Economy: Cities, Regions, and International Trade [link]
Masahisa Fujita, Paul Krugman, Anthony Venables

 motzさんが日記に書いてあったやつを読んでみた。地理的影響が経済に与える影響をモデル化している話。シムシティで60万人とかやっていた人からすると、面白い。実際の地理データとあわせて検証してみたい。

Strategic Dynamics: Concepts And Cases [link]
Robert A. Burgelman, Andrew S. Grove, Philip E. Meza

 前に買ってあったがMySQLとIntelのところしか読んでいなかった。AmazonとNetscapeの章を読んでみた。Netscapeの文章は1997年のもので、将来の予測や展望が述べられているが、いかに10年後が予測不可能なものかが思い知らされる。でも、またブラウザが注目され始めているし。Amazonを読んで思ったのは、この10年ですごい変化を選んできていること。このあたりでおさまろうという気が全然ない

| | Comments (0) | TrackBack (0)

2005.11.21

日曜だなぁ

落し物したらしく、へこむ。
いろいろ用事を片っ端からしていく。

高橋尚子優勝おめでとう。2年前は沿道で見ていたので印象深い

髪切って、夜。

| | Comments (0) | TrackBack (0)

2005.11.20

週末

木曜。一日仕事。
金曜。定兼先生と圧縮索引についてのディスカッション。
土曜。仕事先で作ったシステムを発表。

仕事の途中で見つけたのが、ここのサイト。Cellを読むのを挫折したCS生が生物情報を勉強するのによさそう。基本から教えてくれる。

| | Comments (4) | TrackBack (0)

2005.11.18

木曜

は二限に授業があるはず。まだ最初の1回しかでていない。今日は10時起床。残念。

12時ぐらいからバイト。内容はまぁ、情報科学的にもかなり困難な問題。3時間で終える予定が、夜12時30分頃に終電ぎりぎりで帰るということに。残念。

エビス飲んで、ウイイレやって、好きな音楽聴いてエネルギー充電。

| | Comments (2) | TrackBack (0)

2005.11.17

圧縮全文索引

のまとめサイトみたいなものができてました。[link]
テストセットや評価方法を整備して次の研究を促すのはとても大切なことだと思います。
サーベイ論文も最近の話を網羅していてよくできると思います。

圧縮索引のまだ解決していない実用上の問題は、直接、圧縮索引を高速に構築する手法と、2次記憶領域をうまく利用する手法(一般的には、アクセスがシーケンシャル、局所的であるデータ構造)がないことでしょうか。どちらもいくつか論文が出ていますが、まだまだ改善の余地がありそうです。

| | Comments (0) | TrackBack (0)

2005.11.15

OBガイド

日曜の話。

朝まで作業してそのまま明治神宮ガイド。外国人に声をかける。「英語の勉強をしているんですけど、このへんガイドしてあげましょうか。ただですよ」、という自分が外国に行った時変な店、そして工場に連れて行かれた時のセリフと全く同じセリフで声をかける。これで人がつかまるから日本って平和。

今回ガイドしたのはアメリカ人、ドイツ人、パキスタン人の方々。パキスタンの人は日本の企業で働いているのだが、日本語を半年ぐらい集中して勉強するらしい。

神宮内では結婚祝いということでお神酒が配られていた。違う外国人を連れて行くたび飲んだ。

その後、後輩の方々とお食事会。こういう会で、自分がいつの間にか一番年上の立場になってしまった・・。一応1年生ということでフレッシュさをアピールしたが、残念ながら店員さんから、会計が自然に俺に渡された(いや、もちろん割り勘だけど)。半年前と比べてかなり元気ないですねとも言われた。あの時は卒論で一杯一杯でおかしくなっていた時だったはず。

みんな、ガイド活動に真剣で感心しました。昔作った資料が読み継がれていたし。

| | Comments (2) | TrackBack (0)

2005.11.11

IBIS2005二日目

今日は午後から。

観測スパイク時系列に経験ベイズ推定を当てはめて解析。スパイクというのは脳内のニューロン同士がインパルス状の電気信号のことらしい。この話は初めてだったので新鮮だった。

次はセンサーネットの話。同一のものを複数のセンサがノイズ有で読み取り、それをそれぞれ独立に歪み有りでセンターに送る。センターはそれらのデータからから元のデータを推定し復元する。この時、通信量は一定であるという前提をおくと、センサの数を増やして圧縮率を高めて送るのがいいのか、センサの数を減らして圧縮率を低くして送ればいいのかを理論的(といっても構成可能)に解析。ノイズの具合によって最適なセンサ数が変わってくるという話。
今年のDCCでも複数の入力源からの歪有で送信の話があったような。

リスク回避型学習では、エラーのうち、大きなミスの上位x%のミスは避けてやるという話。具体的には期待ショートフォール(とバリュー・アット・リスクの二つ。個人的には選択を確率的に複数できるようなポートフォリオのケースが面白いなぁと。

Yair Weissさんによる招待講演。Belief Propagation (BP)の話。でも、まだBPよくわかってないので・・
BPは次のあたりを読んでおくとよいのでしょうか。
Understanding Belief Propagation and its Generalizations , Generalized Belief Propagation [link]
Map estimation via agreement on (hyper) trees [pdf]

| | Comments (0) | TrackBack (0)

2005.11.10

IBIS2005

IBIS2005に来てます。
機械学習の話。

午前の構造化データの機械学習は面白かった。

最初はグラフ構造からの頻出パターンのマイニング。gSpan,FGS,GASTON等の解説。やはり、ここがいいよという話。オランダは幾何強いなぁ。土地柄のせい?

次のグラフカーネルを使って化学化合物の分類では、Tanimoto係数参照が構造物の類似度として使われるということで、これでKernelを作ろうという話。グラフが与えられた時、最初に、グラフ中(化合物中)の各頂点から深さ優先探索で深さdまでのpath(フィンガープリント)をハッシュの初期値にして、そのハッシュ値のところが1になったbit配列を用意する。同じ部分構造を持つ場合、同じ場所に1がたっている。グラフX,Yのtanimotoカーネルは、これらから作られたbit配列x, yを使って (x & y) / (x | y) で高速に求められる。性能もいいらしい。

構造データのラベル付け学習モデルの設計では、普通のCRF(全損失から導出。全部のラベルがあっていないとだめ)とPoint-wise CRF(点損失から導出。それぞれのラベルがあっていればよい)の線形和を作ると、k次マルコフの損失関数を最小化するやつができるという話。不思議に思えたが、直感的な図を見たらすぐ理解できた。これをSemi-CRFの上に導入したら、k次Semi Markovができるのかなぁ。そんな単純じゃないのかなぁ

Mochihashiさんに、その後言語モデルや確率モデルの話を教えてもらいました。いろいろ謎だったことが解けました。どうもです。内側(入力側から)のモデルの豊かさに興味を持つ人と、外側(出力側)のモデルの豊かさに興味を持つ人という話が興味深い

| | Comments (68) | TrackBack (5)

2005.11.07

現実的な圧縮索引技術

夏のプログラミングシンポジウム,2005,報告集の原稿です。"現実的な圧縮索引技術"

今年度の未踏の成果の一部も、さらっと書いてあります。
本当はプログラムコードを見てもらうのが一番分かりやすいとは思うんですけどねぇ・・。
Suffix Arrays系のライブラリはまだ準備中です。準備というか、CSAをベースにしたものからRLFMをベースにしたものに書き直してます。検索にO(logN)かかるのは、大きくなると結構致命的なもので、そこはO(1) 正確にはO(H_0)にしておきたいなと。それにもうちょっといい方法を思いついてしまった。

O(H_0)がパンチしているみたいだなぁ。これは0次エントロピー

| | Comments (0) | TrackBack (0)

また

締め切りに間に合わないかもしれない・・ぐわー。実験が終わらない
また次があるからといつも言ってるとできない。

朝までに精度出なかったら今回は無理だなぁ。

| | Comments (0) | TrackBack (0)

2005.11.04

四つ

締め切りが来週末まである。二つはほぼできた。残り二つ。

CMAGAでgoogle、村上さんの「われらいつも新鮮な旅人、遠くまで行くんだ!」という言葉が引用されていた。いいなぁ。

心に残った言葉といえば、先輩から聞いた言葉で「明日が近い。未来は暗い」とか
友人の「万事を尽くさず、天命を待つ」もいいなぁ

| | Comments (0) | TrackBack (0)

2005.11.01

ラジオ体操

うちの前の公園では人が自然と集まって毎朝ラジオ体操をやっている。早寝早起きを5年あまり提唱し続けているものとしては是非とも参加したいところ。

でも、今日も、6時25分に起きて、体が動かないからカロリーメイトゼリー飲んで目を覚まそうと思ったら、気づいたら11時25分になっていた。完敗というか、もうよくわからない。

午前の授業はこんな感じでまだ一度も出ていない。せめて午後の授業に出ようと思ったら、今日は休講らしい・・

---
今学期の授業は離散情報論、連続情報論。あといくつか、経済学部の統計のやつをとろうかとも思っている。前者の授業はCombinatorial Optimizationに沿ってやられている。この本は三冊組の1881ページ。組み合わせアルゴリズムの話が延々と述べられています。新しめの結果も簡潔な証明と一緒に載っていていい感じ。後者は学習理論と情報理論の境目でこの本に沿ってやられています。
---

で、
その時間で、生協でいろいろ研究室でのおつかい。i-RAMでHDDを全部メモリに置き換えたら、怖いけどすごく高速化できそうだねという話をする。
その後発作的に久しぶりにプールで泳ぐ。その後研究室で変なゲームにはまってしまい貴重な時間をつぶしてしまう。いろいろ締め切りが来ているので逃げモードに入り始めたのか。 夜は挽回すべく、ひたすら実装。

"Efficient Implementation of Rank and Select Functions for Succinct Representation", Dong Kyue, Kim et al, WEA2005 も実装してみた。これのByte-Based Impleamentationはすごいいいなぁ。実装もすごく簡単だし・・。rankとselectが1側だけに定義されていないから、0側のrank,selectも実装しようと思うと工夫が必要だけど、一応できる。初めてどんなデータにも対応できる現実的な定数時間selectの実装方法ではないかと思う。

明日こそ・・

| | Comments (0) | TrackBack (0)

« October 2005 | Main | December 2005 »