和と極限を交換したい時に用いる定理

大野 健太
エンジニア

2011-10-24 18:46:01

(読んでいただいた方からの指摘を受けて訂正しました.またtwitterでも感想や指摘を頂きました.ありがとうございます.)

はじめに

 こんにちは,大野(@delta2323_)です.今日はルベーグの収束定理についてお話をしたいと思います.

続きを読む »

averaged stochastic gradient descentのご紹介

preferred

2011-10-20 18:07:58

そろそろ寒くなってきましたね。早速風邪を引きました。徳永です。

今日は私の使っている自作の足置き(制作費600円)の紹介でお茶を濁そうと思っていたのですが、途中で方向転換しました。今日は機械学習の話をします。

Léon Bottouという研究者(彼はまたDjVuというドキュメントフォーマットの開発者でもあります)が開発・公開しているsgdというソフトウェアのバージョン2.0が公開されました。sgd 2.0ではaveraged stochastic gradient descent(ASGD)という手法が実装され、これまでのSGDと比べて性能が向上しました。今日はこのASGDを紹介したいと思います。日本語に訳すと平均化確率的勾配降下法でしょうか。漢字が多くて読みづらいので以下ではASGDと呼びます。

続きを読む »

paper.jsでインタラクティブなグラフを描こう

祢次金 佑
エンジニア

2011-10-11 15:20:21

canvasベースのベクターグラフィクス描画用jsライブラリとして、既に各所で紹介されているpaper.jsですが、これを、ウェブに載せるグラフの描画に使ってみましょう、というお話です。

続きを読む »

機械学習の数学記号に慣れる ー初めの一歩で躓かないためにー

大野 健太
エンジニア

2011-09-29 21:32:15

 初めまして,大野と申します.今回から自分もリサーチブログを書く事になりました.これを期に定期的に投稿が出来ればと思っています.

続きを読む »

研究・企業・生き方について – 情報科学若手の会2011

岡野原 大輔

2011-09-19 12:59:00

岡野原です。

2011/9/17〜2011/9/19に熱海で行われた情報科学若手の会2011に参加し、講演をしてきました。
テーマを決めるに当たって、参加者の年齢、興味分野、スキルの幅が非常に広いということもあり、若手の会参加者のみなさんから質問を前もって聞いておき、それについて回答するという形にしました。
続きを読む »

専門知識の仕入れ方

oxy
エンジニア

2011-09-18 11:08:25

吉田です.
今日は,普段どのようにして専門知識を仕入れているかについて書いてみようと思います.特に自分が得意でない分野を知りたいと思った時に,どうするかに注目したいと思います.自分の専門の場合は,いくらでも時間を注ぐことが出来るので,世界中のリソースを全て探し当てて勉強すれば良いのですが,ちょっと興味が有るぐらいではそこまでやる時間は取れません.なので出来るだけ効率的に分かった気になるのが目標です.

線形識別器でカーネルトリックを使う方法

preferred

2011-09-05 16:01:47

WEB+DB PRESS Vol.64に「作って学ぶ日本語入力」という特集記事を書かせていただきました。徳永です。全国の書店で発売中ですので、ぜひみなさんお買い求めください。(宣伝)

さて今回は、線形識別器でカーネルを使うのと同じ効果を得るための手法を紹介したいと思います。

続きを読む »

最近傍探索2011

岡野原 大輔

2011-08-05 19:25:57

こんにちは、二台目のmbaを買うのをためらっている岡野原です。

アイテム集合に対し、与えられたアイテムと似ているアイテムを求める、という近傍探索問題は古典的な問題でありながら、現在でも多くの改善がされています。特に言語情報、画像情報、行動履歴情報、生物情報、購買情報などありとあらゆるデータが高次元中の点として表現されるようになってきており、こうしたデータの最近傍探索は広い分野で応用範囲がある技術になっています。

アイテムが低次元(例えば2, 3次元)の場合はkd木や最近だとwavelet木を使う方法がありますが、今回扱うケースは各アイテムが高次元(数百万次元)中の点であったり、アイテム間の距離のみが定義されている場合(カーネル関数など)です。アイテム数は数万から数億ぐらいを想定しています。

最近傍探索問題はいくつかありますが、例えばk近傍グラフ構築問題では、

「アイテム集合X = x1, x2, …, xnと、それらのアイテム間の距離が与えられた時、全てのアイテムxにそれぞれについて、それらから最も近いk個のアイテム(k近傍リスト)、kNN(x)を求めよ」

となり、近傍列挙問題では

「アイテム集合X = x1, x2, …, xnと、それらのアイテム間の距離が与えられた時、距離がt以下のアイテムペアを全て列挙せよ」

といった形になります。

この問題に対する自明で最も単純な方法は、全てのアイテムについて、他のアイテム全ての距離を計算し、最小k個を求める方法です。この場合、距離計算はn^2/2回行う必要があり、アイテム数が数百〜数千ぐらいまでしかスケールしません。

この問題に対しては、アイテム一つずつ近傍探索するのではなく、全てのアイテムの近傍探索をまとめて解くことで、高速に求めることが出来る方法がいくつか存在します。今回はそのなかでも実用的で新しいアイディアに基づいているものをいくつか紹介します。

Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures

PDF
W. Dong, M. Charikar, and K. Li, WWW 2011

なぜ誰も思いつかなかったのか(ルーターのMST決定とかで見たような)というほど単純なアイディアで近傍探索を高速に求めるアルゴリズムです。
このアルゴリズムの基本アイディアは、「近傍の近傍は近傍になりやすい」ということです。それぞれのアイテムが自分の現状の近傍リストを持ち、近傍の近傍に今のリストに入っているアイテムより近いものがないかを調べて、近傍リストを逐次的に改善していきます。

各アイテムxについて、そのk個の近傍アイテムをB[x]で表すことにします。逆に、アイテムxを近傍だとしているアイテムの集合をR[x]とします。B[x]は常にk個なのに対し、R[x]はk個とは限らないことに注意してください。また、B[x]とR[x]の和集合をU[x]とします。

はじめに、各アイテムxについて、B[x]をX中のランダムなk個で適当に決めます。次に、各点xについて、その近傍の近傍、つまり、U[x]の中から一つアイテムyを選び、さらにU[y]の中の各アイテムzについて、それが自分の今持っている近傍リスト中のアイテムより近いかどうかをチェックし、近ければ近傍リストを更新します。これを収束するまで繰り返します。

この方法は近傍リストを逐次的、Greedyに更新していくので、kNNの最急降下法という説明が論文ではなされています。

基本的なアイディアはここまでなのですが、改良ポイントが四点あります。

一つ目がlocal joinです。先程のような更新方法をとる場合、近傍の近傍でループを回すとメモリアクセスに局所性がありません。例えば、a – b で aとbが近傍ということを表すと、先ほどは a – b – cの関係にある時、aを固定してループを回して、cがaの近傍に入るかというのをチェックしています。local joinでは bを固定して、bの近傍二つa, cをとってきて、それらがそれぞれ自分の近傍リストを更新できるかどうかをチェックするようにします。こうすることによって、計算量自体はかわりませんが、メモリアクセスの局所性が増し(各アイテムの近傍リストを二重ループするだけ)、高速化することができます。

二つ目がincremental searchです。近傍リストは後半になってくると収束して殆ど更新されなくなってきます。そこで、近傍リストに新しく入ったかどうかを各アイテム毎にフラグとして持っておき、local joinで調べるときには少なくとも片方が新しく入った場合だけチェックをするようにします。

三つ目がsamplingです。local joinの時に実際に全部をチェックするのではなく、適当にサンプルしたものだけをチェックするようにします。次回のサンプリングでは前回サンプリングされなかったものを選ぶようになります。近いのであれば、どれかの近傍には入っているので、全部調べるのは冗長という考えにもとづいています。

四つ目はEarly Terminationです。収束してきたら、近傍リストの改善は少なくなってくるので、適当なところでやめてしまいます。

実験では画像データや言語データなどいくつか試していますが大体傾向は同じです。iteration回数はどの場合でも4,〜5回程度で収束し、その時の再現率が9割前後(本当の近傍のうち9割程度見つかる)、データ数nに対する計算量は 多くのデータでO(n^1.14)です。
このアルゴリズムでは逐次的に近傍リストを更新していくのでアイテムの追加や削除、更新についても効率的にサポートできそうです。

結果で気になるのはデータの種類や量によらず計算量のオーダーが常に同じ(小数点第2位まであう)だということです。近傍グラフの性質がスモールネットワークのように一定以上の量になると法則が現れてくるのでしょうか。

今後の改善の余地があるとすれば、理論的な解析をするのと、更新にランダム性をいれたりMCMCのような枠組みをいれることで局所最適ではなく大域最適な結果が見つかるようにできるかということです。

Scaling Up All Pairs Similarity Search

pdf
R. J. Bayardo, Y. Ma, and R. Srikant, WWW 2007

次に紹介する方法は各アイテムが疎で高次元な特徴ベクトルの場合に向けての方法です。先程の方法では結果は近似でしたが、今回の方法は正確な結果を返します。
話を簡単にするために距離がcos類似度(高ければ高いほどよい)の場合であり、各特徴ベクトルのL2ノルムが1に正規化されているとします。また、cos類似度が閾値tを超えたものだけを見つけたいとします。
#そうでない場合については論文を参照してください。

このような特徴ベクトルが疎で、内積ベースで距離を計算する場合にまず考えられることは、情報検索のように各特徴毎に、それが発火したデータと、特徴値を保存した転置ファイルを構築し、それを利用して内積を計算する方法です。しかし、この転置ファイルを利用する方法には問題が三つあります。
一つ目は、そのまま計算してしまうと(x, y)と(y, x)の二つの類似度の計算をしてしまうという問題、二つ目は全部のデータを読み込んで、それに対して転置ファイルを構築した後でしか結果を出せないという問題、三つ目は転置ファイル自身が元のデータと同じサイズだけ必要で作業領域量が大きいことです。これらを解決していきます。

まず最初の改善では、初めに転置ファイルを作るのではなく、データを順番に調べていって、その時に一緒に転置ファイルも作っていく方法です。データをx1, x2, …, xk-1までみていった時、ここまでのデータに対する転置ファイルを構築します。そして、xkを調べるときには(x1, xk), (x2, xk), …, (xk-1, xk)の類似度が閾値より大きかどうかをチェックします。これにより、対称部分の計算の重複がなくなりますし、また、データ全体を読み込まなくても結果を返すことができます。

二つ目の改善では、転置ファイルを全て作らずに関係しそうなところだけを作る方法です。特徴毎に発火数に大きな偏りがあることをうまく利用し、転置ファイルには珍しい特徴だけが含まれるようにします。アイテムxについての転置ファイルを構築する際には、xの発火している特徴を、転置ファイル中でのエントリ数が多いものから順番に調べるようにします。次に値bに現在みてきた特徴と、他のアイテム全てのうち特徴値が一番大きいものを計算したときの内積を保存します。そして、閾値がtの時 b < tの間は転置ファイルに登録せず、元のデータに登録しておき、b >= t になった時から転置ファイルに登録するようにします。

これらの改良により、転置ファイルは、実際に閾値tを超える可能性がある場合のみ転置ファイルに入るようにあります。そして、転置ファイルにひっかかって類似度を計算するときには、転置ファイルによって計算された分にくわえ、残されたアイテムからの類似度計算部分を調べます。転置ファイルのエントリ数が大きいものから小さいものに順に調べているので、大部分の転置ファイルをつくらずにすむようになり、使用容量の大幅な削減と計算時間の削減が達成できます。

三つ目の改善では、データを、それが持つ特徴値の最大値が大きい順番に並び替えます。そして、転置ファイルを作る時と、それを利用して閾値がtを超えるものを調べる両方の時に枝刈りを行います。これにより、転置ファイルが作る量と、実際に候補が出る量の両方が大幅に減らすことができます。

またこの他にも、特徴ベクトルがbit列である場合や、距離がcos類似度ではない場合向けの最適化も紹介しています。

これらの最適化を適用することで何も最適化を施さない場合と比べて数倍から数十倍、他の手法(例えばLSHを使う場合)などと比べても数倍の高速化が達成できたと報告しています。

その他

この他にも、注目すべきトピックがいくつかありますので要点だけ述べておきます。

“Hashing with Graphs

W. Liu et. al, ICML 2011 pdf

アイテムの集合からアンカーポイントと呼ばれる少数の点を選んだ後に、各アイテムをそれから一番近いk個のアンカーポイントが張るsimplex上で表します。そして、アイテムaとアイテムbの間の近さを、aから関係する各アンカーポイント、そしてそれらのアンカーポイントからbへの近さをあわせて測るようにします。このように作られた行列はいくつも良い性質があって、例えば隣接情報は非常に疎に表せることができますし、またグラフラプラシアンなどを高速に求められるという特徴があります。この論文では、グラフラプラシアンを使った符号化に注目していましたが、アンカーグラフの方はいろいろな用途に使えそうです。

詳しく知りたい方はbeamさんによる解説や、nokunoさんによる解説をどうぞ

Kernel-based similarity search in massive graph databases with wavelet trees

Y. Tabei, K. Tsuda, SDM 2011 pdf

k個以上の共通要素を持つアイテムを求める問題をwavelet木を使うことで高速に求めています。wavelet木を利用することで、アイテム数に依存せず共通要素を調べることができます。
これまではほぼ全探索しかできなかったgraph向けの近傍探索を非常に大規模にこなすことができるようになっています。

田部井さんによる解説もどうぞ。

ユニークなクラウドソーシング・プロジェクト

祢次金 佑
エンジニア

2011-07-11 11:51:03

こんな暑い日はTDSに行きたい祢次金です。

機械には難しい大量のタスクを不特定多数の人間に依頼できる、クラウドソーシング。有名どころはAmazonのMechanical Turk(以下、Mturk)かと思いますが、最近では機械学習や自然言語処理の研究で、学習データへのアノテーションタスクに活用されることもあるそうです。

機械学習とは関係ありませんが、先日見たTEDのプレゼンテーションの中に、クラウドソーシングを利用した面白いプロジェクトがありましたので紹介したいと思います。

このプレゼンテーションは現在Google Creative Labに所属するAaron Koblin氏によるものです。プレゼン中の、クラウドソーシングが絡むプロジェクトから幾つかピックアップします。

続きを読む »

FCRC 2011参加報告

oxy
エンジニア

2011-06-18 08:16:31

吉田です。
先日、アメリカのサンノゼで開催されたFCRC (Federated Computing Research Conference)に参加してきましたので、その様子について報告したいと思います。
写真は最終日に遊びに行ったスタンフォード大学の門です。奥に見える(見えない?)建物まで歩かないとキャンパスに辿り着きません。アメリカの広さを感じます。
続きを読む »