« November 2009 | Main | January 2010 »

2009.12.25

PFIセミナー資料: 研究開発2009

昨日ありました、PFIでのセミナーでの発表資料です。

研究開発のチームの紹介の後に、2009年サーベイした論文の中で面白かった論文を
機械学習、データ構造、画像処理で紹介してます

紹介した話は
- Multi-class CW (Multi-class Confidence Weighted Learning,)
- AROW (Adaptive Regularization Of Weight Vector)
- Online-EM algorithm
- 全備簡潔木 (Fully-functional Succinct Tree)
- 圧縮連想配列 (compressed function)
- PatchMatch

です。

#資料中の簡潔木の表現方法のDFUDSの紹介でtxも使用と書いてあるのは、公開しているtxでは、
 LOUDSのみをつかっていますので正確ではありませんでした。これらは幅優先探索か深さ優先探索かの
 違いです。

ustreamの情報も用意次第アップデートします

| | Comments (10) | TrackBack (0)

2009.12.19

2009冬 宣伝

宣伝です 時系列順

もし、興味がある方はぜひ参加よろしくお願いします。
情報は適宜HPの方でアップデートしていきます

ポスドク向けIT業界セミナー
12月20日 17:00- 19:00- cybozy本社

cybozuとpfiとdenaが共催.会社とか業界とか研究はこうして使われるってのを話します。
直前の告知でしたので、まだまだ募集してます。日曜夜空いている方はふらっと遊びにきてください。

The 1st IST Christmas lectures, Information Science of Web
2009/12/22 15:00- 東京大学本郷キャンパス

google 製品本部長の徳生さん、twitter Chief ScientistのDr. Abdur CHOWDHURYさん、紫綬褒章を受賞された米澤先生が講演します.そしてパネルディスカッションをします。(なぜか?)私がモデレーターをすることになりました。日本のウェブサービスと海外のウェブサービスの比較とかから話を広げていきたいと思っています。日本で知られていないけど海外で流行っているサービスがもしありましたら教えていただけるとありがたいです。とりあえずdeliciousとハテブで差があるようなやつとかalexaとかを使って調べてます(freebase, ted, qq, deviantartなど?)

超高速テキスト処理のためのアルゴリズムとデータ構造 NLP チュートリアル2010
2010/3/8 東京大学本郷キャンパス

膨大な量のテキストを解析する際に有効なデータ構造・アルゴリズムを紹介します.例えば、最新の教師有/無 オンライン学習、正則化、疎・密ベクトルの効率的な格納、簡潔データ構造を使った処理などを紹介する予定


あと論文も

Conjunctive Filter: Breaking the Entropy Barrier" (カメラレディ出したらリンクします), ALENEX 2010

吉田(oxy)さんとの共著です.京大でのNLP若手の会期中に論文を仕上げたという思い出深いもの.U⊆[1...n] を記録する際にm=|U|とすると 1.44m + m log (n/m) bitsが保存する情報理論的下限.例えばこれはある単語の出現文書を記録するような場合.これより少しでも小さくしようとすると途端に正しい結果から大きく離れる.しかし、ANDクエリ (∩_i U_iを返すようなクエリ)ならば、定数個のエラーを達成しながらサイズを小さくすることができることを示しそのデータ構造を提案する.データベースで処理されるクエリや全文検索(N-gramなど)の多くはこうしたANDクエリであり、サイズを小さくしながら殆ど正しい結果を返すことをしめす

| | Comments (3) | TrackBack (1)

2009.12.04

トーナメントと多値分類

今やってる研究で、トーナメント問題を調べる機会がありました。

トーナメントは私も知らなかったのですが、勝者や順位を決める方式のことを指し、いわゆる二人ずつ戦って生き残っていく方式はノックアウトトーナメントといわれるそうです(wikipedia)。
#10000人戦う時にノックアウトトーナメントでは何回試合が行われるかというのはよくある質問ですね。

で、このトーナメント方式というのは調べてみると非常に様々なものがあります

例えばスイス式トーナメントは、最初はランダムな組み合わせで対戦、次は勝者同士と敗者同士、その次は全勝・1勝1敗・2戦全敗のそれぞれが・・というふうに同じ成績の人同士で戦う方式です。レーティングを計算して、レーティングが近いもの同士を戦わせるような拡張もあります。近いのは将棋でやってるようなものですね。
利点は全ての人が同じ試合数で戦い、また厳密な順位が決めやすいことがあります。

パラマストーナメントは、一組試合を行い、その勝者とまた新たな人が戦い、その勝者と新たな人・・というふうにやっていく方式です。ハンター試験のトーナメントみたいですね。こんなのあるかというと、ボウリングとか将棋とか囲碁の一部でつかわれているそう

その他にもページシステム・ダブルエリミネーション(ダブルノックアウト)とかいろいろあります。敗者復活が複雑に絡んでくるとさらにややこしい

なんでこんなのを調べたかというと、多値分類問題の二値分類問題への還元でまさにこの問題がでてくるからです(順位学習でも出てくるが今回は割愛)

多値分類問題は、与えられた入力(例:文書)に対し1,2..,kのラベル(例:カテゴリ)をひとつ予測するうな問題です。これらの問題では昔から多値分類を二値分類問題(の組み合わせ)に還元する方式が多く用いられていました。二値分類は多値分類に比べて昔から研究され、理論も実装も揃ってますので、みんな二値分類に還元したいかです。

たとえば、one vs restと呼ばれる方法では (1 vs その他) (2 vs その他) ... (k vs その他)というk個の二値分類器を作り、一番確信度orスコアが大きかったものを予測ラベルとします。この他に有名な方法では総当り戦、つまり(1 vs 2) (1 vs 3) ... (k-1 vs k)のように、二値分類器をk*(k-1)/2個作り、一番勝ったものを採用する方法です。これ以外に誤り訂正符号(ECOC)の手法を使う方法も知られています。

直接多値分類問題を扱える多値SVMや多値ロジスティック回帰(最大エントロピーモデル)といったものも今となっては簡単に使えるようになりましたが、それでも計算量はラベル種類数に比例してしまうという問題があります。ラベル種類数が非常に大きくなりうる場合(数千、多い場合は数百万)、これら全てのクラスのスコアを調べスコアが最大となるのを求めるのは非常に計算量を必要とします。

実は私もこの問題は1年前からいろいろ、特に言語モデル周りでやっていたのですが、モタモタしている間に今年の間に一気にいろいろとでてきてしまいました。

"Multiclass Classification with Filter Trees", A. Beygelzimer, J. Langford, P. Ravikumar pdf

これは、まさにノックダウントーナメント方式を利用する方法です。各ラベルがトーナメントのプレイヤーであり、勝ち残ったものを予測ラベルとして採用します。実際にテストの時は決勝から逆に葉へむかって勝つ方向に調べていきます。

"Error-Correcting Tournaments", A. Beygelzimer, J. Langford, P. Ravikumar, ALT 2009 pdf

この方法は先ほどのよりもロバストな場合で各二値分類のエラーが大きくなっても、それに耐えうるように、ノックダウントーナメントを複数回繰り返し行い、優勝者を複数決め、それら優勝者の間でグランドチャンピオンをクライマックスシリーズのように決勝に近づくにつれ1、2、3勝したほうが勝ち残るというようにして予測ラベルを決定する方式です。

"Conditional Probability Tree Estimation Analysis and Algoritms", A. Beygelzimer, J. Langford, Y. Lifshits, G. Sorkin, A. Strehl. UAI 2009 pdf

最後の方法は確率も出力できるように根から[0, 1]の区間を分割していく方式です(これはまさに私が去年IBISで発表した方法と同じ) ラベル集合が前もってわかっていなくてもオンラインでラベル追加できたりするところなんかはよくできてるなとおもいます。

どの論文も解析(二値分類の問題に還元したときにどの程度達成可能な精度より悪くなるか)がたくさんされていて、このへんの技はもっていないので勉強になります。

これらは実際に実装は簡単で、すでにいろいろと使わせてもらってます。

しかし、研究はよっぽど思いつかない問題でやるかチームでやらないとなかなか先取りできないなぁ・・

| | Comments (853) | TrackBack (0)

ポスドク向けIT業界セミナー

DeNA×PFI×Cybozu共催でポスドク向けIT業界セミナーを開催します。

日時:12月20日(日) 17:00 より第一部 申し込み受付中
場所:サイボウズ株式会社 本社

詳細は申し込みページや竹迫さんによる告知をみてみてください

私も話す時間をいただいたので、そこでは研究者から見た業界の話、またはその逆とかを話せたらと思います。
うちの会社(PFI)のユニークな文化・雰囲気も紹介する予定です

| | Comments (0) | TrackBack (0)

« November 2009 | Main | January 2010 »