« February 2006 | Main | April 2006 »

2006.03.31

悪循環

目覚ましかけているが大抵無意識に止めている。時には電池も外す。
そして後悔の念とともに起き、落ち込んで寝る。

ブログ読んでて見つけた Network CodingはDCCに行った時に個人的に説明してもらって面白そうだなぁと思っていたのだが、そんなに盛り上がっているのだとは知らなかった。その時は睡魔に負けて寝てしまったが、ちゃんと聞いておけばよかった。。。聞き取れなかったのも大きいのだが。

| | Comments (1) | TrackBack (0)

2006.03.29

nlpers

最近の自然言語処理が何はやっているんですかを書いてるブログ。
http://nlpers.blogspot.com/

機械学習とかアルゴリズムとかも第一線の研究者がどんどんブログで書いているので見逃せない。
こういうの書けるぐらいぐいぐい研究したいですね。

| | Comments (1) | TrackBack (0)

2006.03.27

電子情報通信学会

総合大会に行ってきました。企業の人がとても多くみんなスーツでちょっと心配になりましたが、発表する場所に入るとみんなスーツじゃなくて安心しました。
発表についての資料はここにあります
"大規模データ利用のためのデータ圧縮", 岡野原 大輔 (pptpdf

以前の任意の位置からの瞬時部分復元可能なStatic PPMの話や整数列の符号化を行うVertical Codeと呼ばれる符号について。やはり計算量解析などをきちんとやってほしいという話だった。

Static PPMに関しては今ある技術をきちんと使えば、性能はもっと上がるだろうなぁ。暇になったらやろうかな。たぶん忙しくなったらやってしまうんだろうなぁ。

殆ど寝ていない&食べていないということで夕方は激しい体温低下を招きピンチになりましたがカレー食べて復活。夜は仕事の打ち合わせでした。結構飲みました。

| | Comments (0) | TrackBack (0)

2006.03.25

引越し手伝い

をして、植木をもらってきました。この前もよくわからない草を買ったばかりで家に少しずつ植物が増えています。
植物は全く変化がないものと思っていたのですが、水をやったり、日にあてたりするとしおれていたのが、すぐに元気になったりするので、育てがいがあります。

とはいえ、ネギやニラに似ているなぁと思ってしまったのも事実です。これから野菜を買うとき複雑な気持ちになるのでしょうか。

| | Comments (0) | TrackBack (0)

2006.03.24

suffix arraysやいろいろ

suffix arraysの話は半年置きぐらいに書いているのかなぁ。
(ココログ全文検索機能無くて、不便ですね・・以前どこに書いたのか分からない。)

私が以前書いたSuffix Arraysの構築方法の記事が古くなってきたので(分かりにくいし)、近いうちにライブラリと一緒に内容も更新しようかなと。今回は、忘れないうちにメモも兼ねてSuffix Arraysの高速な構築方法について。

構築で今一番速いのは、msufsortimproved two-stage (プログラム名はdivsufsort)(its)法だと思います。これらはデータサイズに対して線形時間で構築できる方法では無いのですが、大抵のデータでは線形時間の方法より高速に構築することが可能です。

msufsortはsuffix arrays:SAを直接構築するのではなく、その逆の値であるinverted suffix arrays:ISA を構築します(SA[i] = k ⇔ ISA[k] = i  が成り立つ)。なぜISAを作るかというと、SA構築時にすることは suffix の順位を決定することなのですが、この決定の際、ISAが(途中まででも)分かっていれば直接文字列同士を比較せずにISA同士を比較して順位が決定できるので、文字列の順位を少ない比較回数で決定することができます。あとはtwo-stage法と同様に、ある条件を満たしたsuffixの順位は他のsuffixの順位から直接求められる性質を利用し高速化をはかっています。
# qsufsortも同じようにISAを構築する方法とみることができますがqsufsortは全体のISAを更新していくのに対し、ISAは一部分のsuffixから順にISAを決定していきます(そしてソートせずに直接順位が決定できるところはソートせずにとっておく)。詳しくはmsufsort1.0の解説を読んでください。

itsはtwo-stage法の変種で最近提案された方法です(もしかしたら前に誰かやったかもしれませんが・・)。Suffix Ti = T[i...n] 集合 i=0...nが与えられた時、SuffixをAとBの二種類に分類します。AはTi > Ti+1 Bは Ti < Ti+1 であり、ここの不等号は辞書式順序です(Tの最後には$という他のどの文字より小さい文字を置いておき必ず順序が決定できるようにしてある)。AかBのSuffix Arrays中の順位が決定できれば、残り片方の順位は直接(線形時間で)求められるのですが、ITSでは更にBのSuffix Tiの中でTi+1がAであるSuffix を B*とし、B*のSuffixだけをソートします。B*がソートし終わったら残りBの順位を直接求め、そしてAの順位を求めます。B*であるsuffix の割合は全Suffixの大体1/3程度なので、大雑把にいって3倍高速に計算できます。
moriさんによる実装では更に、B*のソートを工夫しています。まずko-alulu法と同様に、まずB*のSuffixの先頭毎にTを分割し、それら各部分列の順位を決定した後に、その順位を新しい文字集合とみなして新しい文字列T'を構成し、それをlarsson - sadakane法(いわゆるqsufsort)でソートします。全体のアルゴリズムでも、テキスト長がnの時5n byteしか消費しないlight-weightな方法です。

これだけいろいろな方法がでてきても、まだまだ速度は要求されます。自分で実装したところではどちらも大体1秒あたり2MBぐらい処理できるぐらいで、これは昔から比べればはるかに速いのですが、巨大なデータを処理したい場合には結構またされます。これ以上の高速化を図ろうとしたら、データの冗長性(k次エントロピーの意味で)を利用するのが一つかなぁとぼんやり考えています。

圧縮されたCSAもしくはwavelet treeを直接構築する方法もでてきており、それらを高速に処理する方法もいろいろ提案されていますが、それはまたの機会に。

---
他に見つけたおもしろそうな論文
"Statistical Encoding of Succinct Data Structure", Rodrigo Gonzalez, Gonzalo Navarro. TR/DCC-2006-1 [ps.gz]

SODA 2006で出た"Squeezing Succinct Data Structures into Entropy Bounds", K. Sadakane and R. Grossi: が実現している任意の位置からの瞬時復元(定数時間)をLZ78を使わずに通常の算術圧縮とかで実現したよという話。私がDCC2005で発表したStatic PPMに似ている。ちゃんと書けばこう化けるのね・・むむむ

同じところでついでにみつけた
"Practical Constructuion of k Nearest Neighbor Graphs in Metric Spaces", Rodrigo Paredes, Gonzalo Navarro, TR/DCC-2005-6 [ps.gz] も面白そう。詳しくは読んでいないが、高次元で高速なk-NNは欲しかったところ。

これらを読んでいて面白いのがtheを使うところをdeと間違っているところ。英語はどこの国でも難しいよね。

| | Comments (166) | TrackBack (0)

昨日、今日

6時に起きようと思って、12時に起きているのはどういうことなのだろう。

水曜。昼間は仕事の打ち合わせ。場所確認にGPSが活躍!夕方から初フットサル。体がついていかない。夜ESS飲み。
木曜。起きたら昼。買い物、いろいろ銀行でごにょごにょ。学校に着くと今日院の卒業式だと聞いた。全部明日だと勘違いしていた。卒業した皆様、最後に会う機会を逃してしまいました・・次の場所でもお元気で。夜父と飲み。

飲み3日連続じゃん。

その他では、suffix arraysやsuccinct data structureのサーベイ・実装してました。

| | Comments (2) | TrackBack (0)

2006.03.22

仕事場で

ご飯を食べながら、いろいろ重要事項が決定しました。

その後友人と、今朝までノルウェイの森を読み終わった感想を話したのだが、友人からの話では、やはり、国際線で昔の情景が思い出されることがあるらしい。自分も昔アメリカからの帰りでワインを結構飲んで酔っ払って寝て起きた直後に突然小さい頃の思い出がかなり鮮明に蘇ったことがありました。

その後いろいろ技術ディスカッションした後、夜は飲み。

| | Comments (2) | TrackBack (0)

ノルウェイの森

学校でプログラミングしおわって、終電も近いので帰ろうと思っていたとき、先輩から借りっぱなしで読んでいない「ノルウェイの森」を返さないとなぁと思いつつ、ふとぱらぱらと読み始めたら止まらなくなり、家に帰る途中も読み、家に帰ってからも読み、読み終えたころには朝になっていました。で、また最初の方をぱらぱらと読み哀しくなったまま寝ました。

| | Comments (2) | TrackBack (0)

2006.03.19

植物

を部屋で育てています。水は、しばらくやらなくてもいいらしいですが、少し心が和みます。

今週があっという間に終わってしまった。記憶が前後しているので箇条書き

研究室で、夜中ダーツした後、床で寝ていたら冷えて体を壊す。
野球の日韓戦を見てもだえる。
年次大会の発表を見に行って、ワイン飲んで帰ってきた。
研究室に新しく来る方の研究発表を聞いた。面白い結果が出てましたが、まだpublishされていないようで、書けないのが残念。
確定申告にて、正しく使われるようにお祈りしながら納税してくる。でもその後研究室で、マシンがいくらという話をすると、複雑な心境になる。

後は、プログラミングとaoe3。いろいろ締め切り逆算すると時間がないんだよねぇ・・まずいまずい。

旅行の写真を載せました。もっと増えるかも

| | Comments (2) | TrackBack (0)

2006.03.15

リハビリ

時差ボケなのかよくわかりませんが、午後3時ぴったりに起きる生活が続いてます。戻さないと

昨日は言語処理年次大会に行ってきました。初日はチュートリアル。最新の識別モデル・言語モデル・音声認識に使われる重み付き有限状態トランスデューサ(WFST)の話です。どれもすごくわかりやすくて良かったです。なにより全部自分の好きなところの話。しかし残念ながら昼食後はスイマに負けてしまいました。

識別モデルはHMMから話が始まってCRFに移り、実際のツールの話になるという流れ。自由にfeatureを設計できるので良いよねという話がすっきりわかりました。識別モデルの方が生成モデルよりうまく学習できている証拠を見せてくださいと突然変な質問してしまったのだが、答えらしきものがこちらに。なるほどなるほど。生成モデルだとうまくいかないデータ例とか作れそうですよね。発表中にvoted perceptronがさらっと紹介されていたが、確率やk-bestが必要でない場合ならこれってかなり強力だなぁと思います。構造の学習もできるし、なにより実装が楽。

言語モデル(資料)は今ちょうどやり始めている課題なので興味深く聞けました。ノンパラメトリックベイズはやはり難しい話だと聞いてすこし安心しました。

WFSTは初めて聞く話。超大語彙音声認識技術に利用されはじめているらしい。高速化の肝になっている部分の話が良く理解できなかったのが残念。あとは根本的に重み自体はどうやって決定するのとかがわからなかった。学習の話はでてなかったから重みは適当に設定してうまくいくのかな。
---

夜は研究室の送別会。今年は多くの人が研究室から出てしまうので少しさびしいですが、世の中狭いですから、いつか会えることでしょう。

| | Comments (5) | TrackBack (0)

2006.03.14

ヨーロッパ旅行

簡単にまとめました。後で写真載せます

2/20 ロンドン経由イタリア
早朝出発。朝から山手線が止まるハプニング。空港集合後、長い12時間の旅の末ロンドン到着。ここで乗り換えローマへ移動。ホテルについた時は全員くたくたでほとんど動けず。夜に最初の試練が。シャワーからお湯がでない。友人は、石鹸まみれの状態でシャワー終了。自分も、ぎりぎりお湯だと信じられる水の温度でシャワーを浴び、ガタガタしながら睡眠。

2/21 ローマ 
本格的な観光初日。この日は朝から精力的に行動する。バスの出発時、停止時の加減速が激しく何人か飛ばされる。道の途中では全員がスリに見える。この日まわったのは、
・サン・ジョヴァンニインラテラーノ大聖堂
IMG_1762
・エジプトからもってきたというオベリスク数本
IMG_1862
・コロッセオ
IMG_1787
・フォロロマーノ(昔の元老院などがあったとこ、シーザーがいたと思われるところなど)
IMG_1806
・ヴィットーリオ・エマヌエーレ2世記念堂
・昼食はピッツア、激馬
・パンテオン(たくさんの神が集まるところ、ドームの天井が抜けていました)
IMG_1815
・トレビの泉(お金ちゃんとなげました)
IMG_1827
・スペイン広場(ローマの休日のアイスクリームを食べるシーンで有名なところ。時計が工事中でした)
IMG_1837


・ジェラート
・真実の口(手とれました)
・サンピエトロ大聖堂、及びその広場 (超でかい。超感動。)
IMG_1869
IMG_1856
・サンタンジェロ城(砲台などがありました)
・夕食はイタリアの小粋なレストランで、メンバーの誕生会。ワインでいってしまいました。

2/22 ローマ
この日既に足が限界でしたが、頑張りました。
・バチカン美術館に朝から並ぶ。有名なミケランジェロが目を失明寸前までになりながら書いたといわれる最後の審判を見ました。感動!すごい!資料集などで見るのとは雲泥の差。他に有名な人が集まっている絵(アテネの学堂)を見ました。ラオコーン像がポツンとあってさびしそう
IMG_1897
IMG_1907


IMG_1925
IMG_1938
・午後はサンピエトロ大聖堂の中に入る。いきなり世界最大の大聖堂に入る。その大きさに唖然。中身にも唖然。階段で上まで登り、ローマの景色を満喫
IMG_2004
IMG_2039
・夕食はスーパー、生ハム・サーモンサンドイッチ。サーモンのでかい切り身をパンにのせて食べる。あまりおいしくない。魚パン

2/23 ローマ→フィレンツェ
朝からバスで移動。「冷静と情熱の間」で有名なフィレンツェへ向かう。
・ミケランジェロ広場から、フィレンツェの全景を眺める。ブラボー!
IMG_2091
・ダビデ像のレプリカに出会う。意外とたいしたことない(次の日に見た本物がすごかった)
・メディチ家が支配していた街並みはとてもきれい。ブランドもたくさん並ぶ。
IMG_2102

・ドゥオーモ(大聖堂。天井の壁画がきれい)
IMG_2113
・クーポラ(2重天井)
・ミケランジェロという店に連れて行かれる
・昼食はBAR(バール)でサンドイッチみたいのを食べる。
・サンタクローチェ教会
IMG_2135
・夕食会、Tボーンステーキ、激うま。肉食いすぎてワイン飲みすぎて弱る


2/24 フィレンツェ 
・ウッフィツィ美術館(メディチ家が集めたといわれる美術展。人生過去最高の量の展示品を見るが、これが残り2週間で数度破られる。ボッティチェリの「春」などがある)
・ジェラート
・ベッキオ橋(宝石店が立ち並ぶ)
IMG_2225
・サンタマリアデラグラッツェ(でかい教会)
・ネットカフェ。悲しいお知らせが届く
・夕食はスーパー、ホテルでサンドイッチ。まぁまぁ美味しい

2/25 ミラノ 
・ミラノではサッカーの試合(インテル)を見ようとするが試合が一日ずれていて見れず。残念
・おいしい揚げパンを食べる・パンツェロッティ
・ミラノ大聖堂修復中
IMG_2267
・スカラ座(世界最高峰のオペラが見れるところ。もちろん当日チケットは買えず。残念)
・ブランド街を歩く。とりあえず有名どころを全てまわっておく。女性向けの店の店員がすごくかっこよいのに対し、男性向けの店の店員がみんな小太りでした。

・夕食はホテル近くのレストランでピザ。過去最高レベルのピザとパスタ。
IMG_2276

2/26 ヴェネツィア 
・列車でヴェネツィアに移動
・この期間はカーニバル。みな変装しており紙吹雪が舞い踊っている
IMG_2341

・ドゥカーレ宮殿(世界最大の油絵7mx22m、牢獄に通じる「ため息の橋」と呼ばれた、最後に外を見られる窓があるところを見る)
・サンマルコ寺院、鐘楼に入ろうとするも人が多すぎて断念
IMG_2343
・ヴェネツィアングラスを購入。この旅で一番高い買い物
・ゴンドラに乗る。寒い、臭い。でもよかったよ
IMG_2351_t
・夕食は、本場のイカスミスパゲッティ。日本のまぁまぁ美味しいイカスミスパゲティは食べたことがあったが、本場だけあってめちゃくちゃうまい
・夜行列車でウィーンに向かう。すごく狭い。自分は上に寝たが下に落ちないように、しがみ付きながら就寝。朝ものすごいしびれとともに起きる。外はものすごい雪山と寒さ。アルプス山脈越え。
2/27 ウィーン 
・シェーンブルン宮殿。歴史上何回も有名な舞台となった場所。ガイドのセリフを借りれば、「有名な舞台となったことはあまりにも有名です」。「会議は踊る」ところで踊りました。マリアテレジアは偉大だ。全体を通して一番豪華な宮殿だった。
IMG_2386
・ウィーンの環状線バスでぐるぐる。モーツァルトの墓など見る
・王宮(シシミュージアム)
IMG_2438
・ザッハトルテ(ホテルザッハー本店で食べてきた。意外とすっぱかったが美味しかった)
IMG_2413
・デーメル本店(チョコレートで有名なところ。おみやげ一つ買いました)
・市庁舎の照明がすごくきれいだった
IMG_2463_t

・地下でバイキング
・シェーンブルン宮殿内の演奏会場で、クラシック・オペラ・バレエが交互にされる若手による室内演奏会。有名な曲(おそらく多くがモーツアルトとか)を聴き、最後にオーストリアの英雄のラデツキーをたたえる、ラデツキー行進曲で終わる)

2/28 チェコ・プラハ
IMG_2479
・両替、コルナ
・プラハ城
IMG_2503_t(これはミュシャが作ったステンドグラス)

IMG_2510

・カレル橋
IMG_2556

・カフカが作家活動をしていた家
IMG_2521

・夜景が非常にきれいな広場(Monsterを読んでいる人ならわかる)
「MVI_2570.avi」をダウンロード
・ホットワインが甘くて美味しかった
・夕食は買い込んだビールをホテルに持ち込んで、チェコビール大会。ビール1本100円前後。

3/1 チェスキークルムロフ、ミュンヘン 
・中世の宝石箱とよばれるところ
IMG_2580
・チェコ料理をとりあえずたべとく。ビーフを煮込んで、パンをひたして食べる
・ミュンヘンには夜遅くに到着。それから電車で中心街に。地下鉄がすごくきれいでした。
・ホーフブロイハウスとよばれる店でソーセージとビール。めちゃうま。ビールが多すぎ。よかったのが生演奏付きだっということ。おすすめ
IMG_2678_t

3/2 ローテンブルク
・このあたりからロマンチック街道沿い(昔ローマ人が作ったという意味らしい)
・シンデレラのモデルとなったといわれるノイシュヴァンシュタイン城。石がきれい。
IMG_2706
・世界遺産らしい教会。
IMG_2760
・ハイデルベルグ城壁に囲まれた小さい街。ワインをたっぷり飲んで街を救った元市長のからくり時計とかを見る
IMG_2816
・すごい雪ではしゃぐ(いろいろなものを落とす。)
・ジャガイモ料理。とてもおいしかったがボリューム多すぎ。肥える
・夜中、ロンドンのチケット予約に奮闘。クリックしまくり

3/3 ハイデルベルク
・午前ローテンブルク観光。
・一年中クリスマス商品を売っている有名な店に行く。店内はとてもメルヘンチック
・その直後に中世犯罪博物館へ行き、実際に使われた拷問の器具などを見る。はりだらけの椅子や、ゆびをつぶす機械など。このギャップが中世ヨーロッパ
IMG_2873

・午後はハイデルベルグ城。ゲーテが書いた絵など。
IMG_2907_t

・ひどいみぞれまじりの雪で全員が朽ちる
IMG_2921_t(写真は添乗員の木村さん)
・学生の街だけあって、いろいろな学術参考書が売っている。ドイツということもありモンスターを買う。
・夜は、学生がよくきている店で、ピアノを聴きながらドイツ版餃子を食べる。
IMG_2938

3/4 ハイデルベルグ→パリ
・列車でパリに移動。
・バスで凱旋門3周
・エッフェル搭に感動
IMG_3007_t
・ノートルダム寺院に入る
IMG_3028
IMG_3033
・レストランで初エスカルゴ。うまい!
IMG_3103(日本ですね)

3/5 パリ
・ヴェルサイユ宮殿。庭がすごく広く地平線が見える
IMG_3169

・中はまぁまぁ。鏡の間が修復中でした
IMG_3136

・サントシャペル。全面ステンドグラスの教会。
IMG_3219

・ルーブル美術館。モナリザ!ナポレオン(の奥さん)戴冠式!ニケ!民衆を導く自由の女神!ミロのヴィーナス!ハンムラビ法典!をはじめ本当にもりだくさん。全部見るには1日でたりるかどうかというダントツの広さ。足が諤諤。すばらしい!
IMG_3263_t
・セーヌ川きれい
IMG_3275
・最初、有名カフェに行こうとするが、高級すぎて断念。普通のカフェに行く。ドトールみたいだった。
・夕食は添乗員(木村さん)の誕生日会。ケーキ食べる。


3/6 パリ 
・モンサンミッシェルに往復10時間で行って来る。海の中に修道院がそびえたってました。
IMG_3303
IMG_3306

・中も迷路みたいできれいIMG_3382(中庭がみえる)
IMG_3375(遠くまで浅瀬)
・昼食はでかいオムレツ。あまり味がついていない
・途中で見た羊がかわいいなと思ってましたが、食用だそうです
・夜はセーヌ川クルーズ


3/7 パリ→ロンドン
・ロンドンに飛行機で移動。ツアーを供にしていた1部の人ともお別れ。添乗員の木村さんともお別れ。見てますかー?
・ナショナルギャラリーに行く。

・ピカデリーサーカス(ロンドンの中心地。NYのタイムズスクエアみたいなところ)に行く
・夜は中華。中華料理は最高だ!

3/8 ロンドン 
・ロンドン塔に行く。その当時の処刑の様子などをビーフィーターと呼ばれる人が説明するのだが、説明を聞いている間に、隣にいた女性が失神して倒れる。よほど恐ろしいことを言っていたのだろう。私は英語聞き取れないおかげでよくわからなかったのだが
IMG_3466

・同じくロンドン搭で世界最大のダイヤモンドを見る
・タワーブリッジを通る
・コヴェントガーデン(マイフェアレディの舞台)で昼食。

・セントポール大聖堂
IMG_3487_t

・フォートナムアンドメイソン(学校の計算機の名前ですね)で午後のティータイム。アイスクリームがおいしかった
・自然史博物館で世界最大の卵、亀、魚、象、クジラ、金塊、また恐竜をいろいろ見た後、科学博物館で阪神大震災の体験をする。
・シャーロックホームズ・パブで酒を2パイント(1リットル)
IMG_3544
・その後サッカーパブで、アーセナル-レアルマドリード戦を見る。アーセナルの本拠地だけあって大変な混乱

3/9 ロンドン
・国会
IMG_3561

・ウェストミンスター寺院
IMG_3574_t

・バッキンガムで衛兵の交代式。ブラジルの大統領が通過するもよくわからず
・フィッシュアンドチップスを食べる。少しぐったり
・大英博物館。ロゼッタストーンに興奮
IMG_3631

・マークスアンドスペンサー(デパート)

・ポールスミスでTシャツを買う
・アビーロードでビートルズ万歳!
IMG_3667
・ハロッズ。トイレに係員がいました
・バーガーキングで夕食(2回目)
・Her majesty's Theatreでミュージカル「オペラ座の怪人」。はじめてのミュージカルだったがすごい面白かった。昔劇の舞台係を少しやったことがあるが、舞台が次々変わっていく様子だけでも衝撃的でした。

帰国

| | Comments (4) | TrackBack (0)

« February 2006 | Main | April 2006 »