« March 2006 | Main | May 2006 »

2006.04.30

GW体験

引越し手伝いみたいなものをするために、レンタカー借りて埼玉の方に行ってきました。帰りにできたばかりのIKEAによろうと思ったところねずみーらんどやらIKEAに行く人やらで大変な渋滞に巻き込まれて、たどりつけませんでした。

帰りは初の首都高で、ビル群の中をとばして(みんな速いので・・)レースゲームみたいで楽しかったです。家についたのは深夜でバタンQでした

| | Comments (1) | TrackBack (0)

勉強会

金曜日、東工大で開かれた勉強会に参加してきました。
普段自分が触れているのとは違う分野の発表が多かったので、勉強になりました。数式とかは追えるのですが、実際にその根底にある思想とかを理解するためには一度やってみないとだめなのでしょうね。貪欲にいろいろ試さないと。

| | Comments (0) | TrackBack (0)

2006.04.28

研究室引越し

自分は今まで浅野キャンパスにいたのですが、なんやかんや使えなくなるということで別の場所に引越し。生協書籍部の近く。新しい場所は最初は病院かなと思ったのですが(有機溶媒のにおいがする)、カーペットも新しいし、広いし快適そう。なんとなくW杯が楽しみですね

しかし、早起きしてぼんやりしたのが悪かったのか、作業中に机に足をぶつけて親指の爪がとれた・・。あまりの痛さで歌を歌いながら保健センターに行って消毒してぐるぐる巻き。ラグビーやってた頃は良く取れていたけど、慣れないですな。慣れてもいやだが。

家に帰ってから原稿をおりゃーと書き上げできた。あと1時間半でラジオ体操ですか。なかなか連続早起きできない

| | Comments (3) | TrackBack (0)

2006.04.26

一掃

忙しい期間が一息ついたので、爆発していた部屋を片付けはじめました。
まず、昔から印刷しまくった論文などを整理して捨てました(重ねたら人の高さぐらいになったが崩壊して大惨事に)。昔見てわからなかった論文が今読むと結構理解できるので面白くて、片付けに予想以上に時間がかかりました。

部屋がかなり広くなった。新しい机やライトも導入し素敵な環境になりました。これからホームページや、ソフトウェアなどいろいろ整理します。

| | Comments (0) | TrackBack (0)

2006.04.21

Structural learning

Structural Learningはsemi-supervised learningを行う新しい手法です。

(構造を持った出力を予測するStructured output predictionとは関係ないです)

この話は、次の中で提案されています
"A High-Performance Semi-Supervised
Learning Method for Text Chunking.", R. K. Ando, T. Zhang, ACL 2005, [pdf]
ジャーナル版
"A Framework for Learning Predictive Structures from Multiple Tasks and Unlabeled Data", R. K. Ando, and T. Zhang, Journal of Machine Learning Research [pdf]

Semi-supervised learningは、機械学習を行う際、正解の付いた教師付きデータだけではなく、大量の教師無しデータを利用することで、精度を向上させようとするもので、今までにco-training, transductive inference, EM, bootstrap, data-manifold などが提案されていました。これらの多くは分類器の精度(や再現率)を直接向上させるために教師無しデータを使っていました。

このstructural learningでは教師無しデータを、良い分類器ではなく、良い仮説空間を探すために使います。実際の議論はこのまま進むのですが、仮説空間とはなんだということで内容を具体的にすると、分類器は線形分類器(SVMやboostingを含む)を使うとすると、仮説空間を探すというよりは入力のfeature集合(重みもついている)から、より分類がうまく行えるようなfeature空間への写像(線形写像)を求めるということになります。

教師無しデータは正解が付いていないのですが、自明に正解が分かるような大量の補助問題を作り、それに対する精度がよくなるような仮説空間を求めます。この補助問題は実際に解きたい問題と相関があるようなものとします。例えば、実際に解きたいのが単語の品詞を求める問題の場合、補助問題は、ある位置にある単語は何かという問題となります(答えは自明に実際にそこに出現した単語を使う)。また、分類器が予測するのは何かというのを予測する補助問題も考えることができます。こうした補助問題の損失を同時に下げるような仮説空間を求めます(ポイントはこの仮説空間を求める部分がSVD:特異値分解でできるらしいのですがそこまでは理解できてません)。

こうして得られた仮説空間の中で実際に解きたい問題を学習、解くことになります。

似たようなことは考えたことはあるのですが、この論文では理論的な解析(補助問題数mがm→∞となった時、実際に良い仮説空間の推定ができる)や、具体的なアルゴリズムなどが示されています。そして、実際に精度が、教師付きデータのみを用いた場合と比べてかなりよくなっているということがCoNLL2003のshared task*等の結果で示されています。うまくいくのか・・

(CoNLL2003のshared taskは固有表現抽出で、大量の非教師データを使ってどこまで精度が上がるのかということが期待されたらしいですが、トップチームはみんなsupervised learningのみだったそうです。NISTの機械翻訳ワークショップでも同じような感じでしたね [link])

| | Comments (6) | TrackBack (0)

succinct representation

Succinct (簡潔な) representation (SR)は、近年データ構造界隈で盛んに研究されている分野です。

SR は固有名詞となりつつあり、現在の定義では、あるデータ構造のcardinarity (場合数)がLの場合に、そのデータ構造を (1+o(1))log L bit で表し、様々な操作を定数時間で行えるようなデータ構造を指します(と思います)。 logL bitというのはそのデータ構造を表すために必要な最低限の情報量なので、それと比較しわずかな補助データ構造を使って様々な操作を定数時間で行えるもので、時間、領域ともに限界を目指しているデータ構造です。

この概念はデータ圧縮と似ています。データ圧縮は、情報をできるだけ小さく保存、伝送する目的がありますが、そのデータを使いたい場合は基本的にはデータを元に戻す復元操作が必要になります。それに対しSRは圧縮した状態のまま、その上で様々な操作を行えるところが違います。もちろん元のデータ自身を参照することはできますし、列挙やある条件を満たした要素の頻度計数などができます。

現時点では、bit array (0と1からなる配列)、tree, permutation, function, graphなどに対するSRが提案されています。Compressed Suffix ArraysやFM-indexもテキストに対する一種のSRとして考えることができます。テキストの一部分を参照(復元)することができますし、任意の部分文字列検索をできたりするからです。

一般のテキストの部分復元をしようという話自体は、私がやったStatic PPMやLZ法を使ったもの [K. Sadakane and R. Grossi: Squeezing Succinct Data Structures into Entropy Bounds]があります。

よく研究されているtreeに対するSRでは、節点と葉の合計がn個であるtreeを2n bitで表現しつつ節点の子や兄弟、親、二つの節点の共通最小祖先とかを定数時間で求められるようなものが提案されています。今年もいくつか新しい表現方法が提案されているようです。

これらの多くは最初、理論的に構成したものが多く実際に実装してみるとうまくいかなかったものも多かったですが、最近は現実に即した表現方法の研究も盛んとなり、利用しているところも多くなってきているようです。

そのうちこれらの研究成果のいくつかがさらに洗練されみんながライブラリなどで普通に使えるようになるのでしょう。

| | Comments (0) | TrackBack (0)

あとは野となれ山となれ

論文。いえ、通って欲しいです。

最後の締め切りの直前の夜は新入生歓迎会。なんか、後輩をいじっていたようなきがする。全部忘れました。すいません。
ビールをコンスタントに飲んだ後、先生にDSをすすめました。表参道ヒルズの前をみんなで通って解散。家に帰って論文書かねばーと思いパソコン開いて、布団で正座したまま就寝。

次の日は外は暴風雨で植木が倒れてきたり、窓がわれそうになりながら、自分も空腹睡魔と闘いぎりぎりで書き続け午後できて投稿。その後渋谷で仕事打ち合わせ。新橋で酒飲み。

机がうちにくるこの機会に、家を改造しよう

| | Comments (0) | TrackBack (0)

2006.04.19

いろいろ締め切りありまして

今週3つ締め切りがありまして、1.5ぐらい終わりました。あと1.5です。あと1%上がればとか、あと1時間あればとか、いろいろなかなかうまくいかないものです。あと少しです、頑張ります。

| | Comments (2) | TrackBack (0)

2006.04.09

に行ってきて、かえってきました。山行ったり城行ったりしてました。リフレッシュ!
いろいろ締め切り近いからがんばるぞー

--
旅の途中でnintendo DS liteが売っていたので買いました。ペン入力がいいよねぇ

--
同級生のおめでたい話が舞い込んできました。おめでとう!

| | Comments (1) | TrackBack (0)

2006.04.06

春は、あけぼの

に寝ます。
ここしばらくは仕事関連で省メモリで高速にCompressed Suffix Arraysを構築する方法に取り組んでました。遅い原因は大体検討ついていたので、いろいろやった結果、直接SAを構築する方法の1.5倍ぐらいの速度で構築できるようになりました。"いろいろ"は追々説明します。
次は1T1台で索引目指してディスク化ですかね。

今日は昼までプログラミングしてて学校行ってサーバの不具合みてきて(結局俺は何もしなかったような)、論文どうしようと話して、歓迎会らしいことして帰りました。

だんだん、学生っぽい生活になってきましたね。

| | Comments (1) | TrackBack (0)

2006.04.03

篭って

プログラミングプログラミング。締め切り近いとはかどる。
夜は仕事打ち合わせ&飲み。

花が雨で結構やられちゃいましたね。まだ少しもっているみたいだけど。

| | Comments (0) | TrackBack (0)

« March 2006 | Main | May 2006 »