« 2010年8月 | トップページ | 2010年10月 »

2010年9月

AdaBoost アルゴリズム (ブースティング)

近年,機械学習の研究分野において,ブースティングと呼ばれるアルゴリズムが注目を集めています.アルゴリズムと書きましたが,正確には教師あり学習を実行するための機械学習のメタアルゴリズムであります.すなわち,一般の(任意の)機械学習アルゴリズムをもっと賢く実行するためのフレームワークと言えます.弱い学習機をまとめて,重みを付けてその結果を足し合わせることで,強い学習機を生成することを目指します.

核となる機械学習アルゴリズムに何を用いるかは,制限されておりません.弱い分類器は,学習の正確さ(あるいは汎用性?)に基づいて,重み付けされます.「分類器をいくつも作成する」と言っても,どう作成するのかが分からないと思いますが,実際には,元のデータに重み付けをし直して(何度も重みづけを行い),それにより共通の機械学習アルゴリズムで学習し,複数の分類器を作ります.一般には,誤分類される例(サンプル)は重みを増し,正しく分類される例は重みを減らします.

代表的かつ人気のあるブースティングアルゴリズムとして,AdaBoost(「エイダブースト」「アダブースト」と呼ぶ)があります.以下,AdaBoostのアルゴリズムの概要と本質について説明します.

概要

1.サンプル(特徴ベクトルと教師信号であるクラスの組)への重みは,最初は1/N (Nはサンプル数)で初期化します.

2.T個弱識別器を作るとします.

3.(まずは,1つ目の)弱識別器tを作ります.弱識別器tの作り方は,重み付きのサンプルを利用して,一般的な機械学習アルゴリズムを利用して学習します.

4.弱識別器tの誤り率を求めます.誤り率は,各サンプルを見たときに,サンプルのクラスと弱識別器の出力クラスが一致しないサンプルの重みを足し合わせたものになります.

5.誤り率から弱識別器tの信頼度を求めます.具体的には,誤り率が小さいほど,信頼度が大きくなるようにします.

6.サンプルへの重みを更新します.サンプルへの重みは,弱識別器tが正しく識別できたサンプルは重みが低くなるように更新します.弱識別器tが間違って識別したサンプルは重みが高くなるように更新します.

7.サンプルの重みの和が1になるように正規化します.

8.3.に戻って,t+1個目の弱識別器を作ります.T個作れたら,アルゴリズム終了です.

9.最終的な識別は,全ての弱識別器を信頼度で重みづけして多数決を取ります.

本質

ブースティングの本質は,弱い機械学習アルゴリズムを用いて,過学習の状態を作り出すことにあると考えます.サンプルに重みをつけずに機械学習したものは,もっとも一般的な識別を行う識別器と考えてよいでしょう.その識別器が誤ったものの重みを大きくして学習するということは,特異例を識別するための特異な識別器を作ることになります.ブースティングでは,順に識別器を作っていきますが,汎用的な識別器から順に特異例に対する識別器を,深く掘り下げて作っていくイメージになります.

このように元の学習データは同じで,それを何度も繰り返し学習を行いますので,見た目的には少ない学習データから効率的に学習していることになります.学習データは,ユーザプロファイリングなどにおいては,多くは期待できませんので,そのようなモデルの学習には,ブースティングは期待されております.

ただし,本当に効率的かどうかは結果をみないとわかりません.本当に賢い識別器を作るか,過学習の識別器を作るかは,非常にセンシティブであると言えます.学習データが少ないから使うというモチベーションは分かりますが,作成された識別器の汎用性は十分に考慮する必要があると思います.

なお,アルゴリズムの特質上,もともと強い学習器を弱識別器の学習に用いると,過学習の上に過学習を塗り重ねる可能性がありますので,注意が必要です.SVMなどの高性能な機械学習アルゴリズムを用いるよりは,ロジスティック回帰などの古典的なアルゴリズムを用いる方が良いように思います.

|

国際会議WWW2009論文感想その6

Reinier H. van Leuken, Lluis Garcia, Ximena Olivares, Roelof van Zwol: Visual diversification of image search results, Proc. of WWW 2009, pp. 341-350, 2009.

イメージ検索の結果をクラスタリングしようという内容である.イメージ検索をすると,良く似た画像が繰り返し出てくることがあるが,クラスタリングにより,それらを集約化すれば,検索結果の多様性を高めることができるというものである.

イメージのクラスタリングなど,やり尽くされて,もう骨も残っていないような研究分野ではあるが,これは(1) 元のランキング結果も考慮する,(2) どんなクエリに対してもオンラインでリアルタイムにクラスタリングを行う,ことを売りにしている.

クラスタリングに用いる特徴量としては,目新しいものを提案しているわけではない.具体的には,Color histogram (RGBの色空間を64分割し,各色の出現頻度を求めたもの),Color layout(画像を空間的に64分割し,その色平均を求めたもの),Scalable color(HSV色空間のヒストグラムにHaar変換を施したもの),CEDD(フィルタを用いて,垂直,水平,斜め45度のエッジの有無を検出したもの),Edge histogram(画像を空間的に16分割し,そこにエッジが含まれるかどうかを判定したもの),Tamura(Tamuraらが開発したテキスチャ特徴量(粗さ,コントラスト,方向性,線らしさ,規則性,でこぼこさ))を用いている.

クラスタリングアルゴリズムとしては,K-meansや凝集法,Newmanの手法と言った繰り返し計算を必要とするものではなく,以下のようなものを提案している.

Folding:検索結果のランキング上位からをクラスタ代表を選び,ランキングの下位に向かって,逐次クラスタ代表を選ぶ.具体的には,すでに選んだクラスタ代表と十分に距離が遠ければ,新しいクラスタ代表として採用する.ランキングを一通りなめた後,残った画像を最近某法に基づき,クラスタに割り当てる.

Mamin:ランダムに代表R1を選ぶ.次にR1から最も距離が遠くなる画像を代表R2として選ぶ.以降の代表はすでに選ばれた代表との距離のうち最小となるものが最大である画像を選ぶ.この処理を前期最大最少距離が閾値以下になるまで行う.代表を選び終えれば,残った画像を最近某法に基づき,クラスタに割り当てる.

Reciprocal election:「各画像iごとに,i以外の残りの画像を,iとの類似度に基づきランキングしてリストLiを作る.Li中の各画像に対して,Li中でのランクrの逆数をスコアとしてV[j]に足す.」このプロセスをすべての画像に対して行う.これにより,各画像からみて,それに近い画像を探したときに,最も代表らしい画像を探すことになる.さらに,「Vから最大スコアを持つ画像Riを取り出し,それをクラスタ代表とする.残りの画像に対し,残りの画像の一つsが持つランキングリストLsの中に,Riがトップm位以内にあれば,sをRiのクラスタに入れる.取り出した画像はVから除く」を,Vが空になるまで繰り返す.

評価は,人間に特定クエリに対する検索結果を見せて,それをクラスタリングさせ,それを正解としている.その正解のクラスタリングに対して,Folwkes-Mallows indexとVariation of informationを用いて評価を行っている.評価結果は,Folwkes-Mallows indexでは,Flodingが一番良い結果を示している.Variation of informationでは,Reciprocal electionが一番良い結果を示している.統計的な有意差も出している.指標によって結果が異なるので,結局どのアルゴリズムが良いの?という疑問が残るが,これは裏返せばそれだけクラスタリングの評価というものは難しいことを示している.こういう感覚は,実践的にクラスタリングの研究を行っている者だけが分かると言える.

本論文の感想であるが,非常によくまとまった論文であると言える.研究分野はともかく,これから論文を書く初学者にとっては書き方を参考にしてよい論文と言えるであろう.ただ,一点,研究内容に関して不満を上げるとすれば,本研究の貢献はどんなクエリに対してもオンラインでリアルタイムにクラスタリングを行うことにある.このことはもう少しアピールしても良いのではないかと思う.また,評価はクラスタリングの質を重視しているが,クラスタリングの実行速度に関しても評価すべきである.アルゴリズムにおける繰り返しの有無が,速度に決定的違いをもたらすのは自明ではあるが,この評価があれば,どのぐらいのパフォーマンスの改善があるかを示すことができるので,より良い論文になると考える.

|

国際会議WWW2009論文感想その5

Rich Gossweiler, Maryam Kamvar, Shumeet Baluja: What's up CAPTCHA?: a CAPTCHA based on image orientation, Proc. WWW 2009, pp.841-850, 2009.

CAPTCHAと言えば,人間には読めて計算機による画像認識では認識できない文字を表示させて,Webでの人間か否かの認証を行うためのシステムである.しかし,解読が難しいほど変形させた文字があったり,携帯端末では文字を打つのが面倒臭かったりと,完ぺきとは言い難い.この論文では,回転させた画像を提示し,ユーザにそれを正しい向き(直立させる)に直させて認証するシステムを提案している.画像は,円形にしているため,外枠の角度だけでは正しい角度は認識できない.計算機では,画像の直立方向を判定することは困難であることを利用した認証システムである.

この論文では,
・Google画像検索により,キャプチャの候補となる画像を取得する.
・計算機による直立方向認識システム(筆者らによって以前に開発されたシステム・180個のAdaBoost分類器)によって,計算機が識別しやすい画像を取り除く.
・500人の被験者を集め,その人たちに直立方向を判定させ,誰もが同じ方向を直立とした画像のみ残す
ことにより,どうやってキャプチャとなる画像を選ぶのかを説明した点が貢献になる.

さらに,16人の被験者により,テキストのキャプチャと画像のキャプチャとどちらを好むのかをテストしている.

筆者の開発した直立方向の認識システムでは,画像を1/2×1/2から1/6×1/6まで分割し,各分割画像にて,RGB, 再度,水平エッジ,垂直エッジなどを特徴量として,合計3930の特徴量を用いている.論文には書いていないが,180のAdaBoost分類器を用い,直立方向の判定の一致度合いにて,画像が計算機により認識しやすいか否かを判定しているものと思われる.

画像の回転をキャプチャに用いるというアイディアは極めて面白い.直立方向の判定が計算機に可能か否かを複数の分類器を用いることで判定している点も評価できる(論文には明確に書いていないので,これは私の勘だが).ただ,その後,特別に集めた500人の被験者により人間にとって認識しやすいかどうかを判定している点は評価できない.これだけ人を集めれば,できるのは当たり前である.また,キャプチャの評価も単に好き嫌いのみで評価しているのもいただけない.キャプチャの認証にかかった時間やエラー率など,様々な観点から定量的評価が可能であろう.その辺りの評価がなかったことが残念である.

|

Beyond Webの展望 @FIT 2010

2010年9月8日に,FIT 2010内の特別講演・パネル討論
「ポスト情報爆発へ向けて-Beyond Webの展望-」
http://www.ipsj.or.jp/10jigyo/fit/fit2010/
に参加してきました.

特別講演は
森正弥氏(楽天技術研究所)
「インターネットサービス企業における情報爆発とその先」
でした.
講演内容は,楽天の推薦サービスを実現するための独自技術に関するものでした.

Webにおけるサービス企業が,自前でシステムやサーバを構築し,独自技術の開発に力を入れていることは,私にはかなりの驚きでした.

多くのWeb企業は,ガレージ企業のように,自前でシステムを開発し運用するのが事業の原点だとしても,いずれそれを外注する転換点が来ると考えていたからです.

特に情報推薦を実現するために,様々なエンジンを開発していることは注目に値します.

推薦のためのプラットフォームを構築していること,分散処理のためのエンジンを持っていること,そしてDBMSを持っていることは,かなりの競争力になるように思います.

これがIBMやNTTデータのようなソリューションカンパニーにできないのか?という疑問が湧くのですが,どうなんでしょう?

新興Web企業には,システム開発を外部に委託するという発想がないのかもしれませんが,もしかすると大手のITベンダーとは言え,情報推薦を実現するためのシステム開発は技術的に不可能なのかもしれません.通常の決まったトランザクションを実行するだけのシステムなら良いですが,メモリベース手法によるシステムは計算時間がかかります.

ユーザ,アイテム,レーティング,タグなどの複数の情報が存在し,それらの関係を見ないといけないとなると,独自技術を持っているかどうかが,他社との差別化になるように思います.

このような技術は米国が先を行っているわけですが,国内企業の楽天が米国企業と張り合うのは,非常にうれしく思います.

ちなみに当日,質疑応答の時間に,「なぜ自前技術にこだわるのか?」を尋ねたのですが,「なんでも自前でやるのが楽天流」という回答でした.理由はともあれ,楽天の今後には期待します.

以下,当日取ったノートです.

(1) 森正弥氏(楽天技術研究所)
「インターネットサービス企業における情報爆発とその先」
日本の流通 180兆円 eコマース10兆円
そのうち,2兆円が楽天

楽天スーパーDB
・レコメンデーション
・パーソナライズ
・購買予測
・KPIモニタリング

顧客満足度の向上
顧客満足度の高いレコメンデーションを実現

楽天の商品データは,各企業が提供
同じ商品の商品名が商店によって違う

データがカオスなので,レコメンデーションと言っても,
従来の手法を適用するだけではうまくいかない.

村上春樹が誰にでも推薦されてしまう
(よくある問題である)

TOHO
レコメンデーション・プラットフォーム
協調フィルタリング,画像処理などプラグインを入れるだけで,
推薦方式を変えることができる

最新のデータを使って推薦するほど,クリック率が高い

レコメンデーション,ビジネス上のインパクトは大きい.
売り上げに対してレコメンデーションからの購買は,1割や2割できかない.

GoogleのMapReduceのように自前で基幹エンジンを持っている.
「処理の分散エンジン」Fairy
「Key-Value-Store型データベース」ROMA

あなたが過去に見た・利用した商品を出す
→クリック率が50%近くある.
レコメンデーションよりも高い.
このような個人ごとのトランザクションデータは,従来のDB技術では
高速に引き出すことができなかった.ROMAにより実現可能となった.

楽天のデータと外部のデータを連携して,レコメンデーションをしていきたい
Rakuten EntameNavi
複数の外部の情報(Wikipediaを含む)を組み合わせて実現している.

データの公開とその活用が世界的に進む
Tim-verners-lee オープンデータとマッシュアップで変わる世界

楽天もデータ公開

楽天データチャレンジ
・楽天テクノロジーカンファレンス
2010/10/16(土)

|

国際会議WWW2009論文感想その4

Shilad Sen, Jesse Vig, John Riedl: Tagommenders: connecting users to items through tags, Proc. of WWW 2009, pp.671-680, 2009.
キーワード:情報推薦,協調フィルタリング,タグ,タグを用いた推薦

GroupLens Researchの論文である.タグに対するユーザの嗜好の程度を推測し,さらにその結果をアイテムの推薦に利用している.タグを用いた情報推薦は非常に盛んになりつつあるが,多くの研究では,ユーザプロファイルを構成するタグを事前に登録しておいたり,タグをベクトル空間モデルとして扱ったりしているが,タグに対する興味の程度を推定することは行っていない.本研究は,タグに対する興味の程度を推定し,さらにアイテムの推薦を行っている点で,新規性がある.

データセットとしては,MovieLensを用いている.MovieLensでは,タグに対するユーザの興味の程度という情報は入っていないため,彼らは登録ユーザに個別にメールを送信し,タグに関するアンケートを取っている.具体的には,そのタグを用いて推薦された映画を見るか否かというデータを取っている.

データセットでは,アイテムへの5段階評価,アイテムの詳細情報へのクリック,アイテムへのタグ付,タグ検索(タグのテキスト検索もしくはタグのクリック),タグに付けた5段階評価を含んでいる.

タグの好みの推定のアルゴリズムをいくつか提案している.アルゴリズムは,タグに対するインタラクションを直接利用するもの(Inferring Preference uing Tag Signals)と,タグが付けられたアイテムに対するインタラクションを利用するもの(Inferrinf Preference using Item Signals)に分かれる.

・Inferring Preference using Tag Signals
以下の3種類のアルゴリズムを提案している.
Tag-applied: Movie-clicks: ユーザがそのタグを映画に付けたことがあれば,より高い評価を与える.
Tag-searched: ユーザがそのタグで検索したことがあれば,より高い評価を与える.
Tag-quality: タグの質によって評価を決める.全ユーザで共通の値となる.著者らの先行研究の結果を用いている.具体的には,タグをつけた人の数やタグで検索した人の数などを用いている.

・Inferring Preference using Item Signals
6つのアルゴリズムを使用している.
Movie-clicks: そのタグが付けられている映画を数多くクリックしていれば,高い評価を与える.
Movie-log-odds-clicks: Movie-clicksにタグの人気も考慮している.人気のあるタグをクリックしても,高い評価は得られないようにしている.
Movie-r-clicks: Movie-clicksがクリックを用いているのに対し,これは映画を評価付けしたかどうかを見ている.
Movie-log-odds-clicks:Movie-r-clicksにタグの人気も考慮している.
Movie-rating:ユーザのタグへの好みは,そのタグを持つ映画に対する評価の平均としている
Movie-bayes: ユーザが特定のタグがついている映画に対してどのように評価を与えているのかを確率分布にてモデル化している.

まず,各実験にて上記アルゴリズムのタグへの興味の推定のパフォーマンスを評価している.結果としてはアイテムに対するratingの情報を用いた方が良くなっている.

次にタグを用いた推薦方式を提案している.大きくは,アイテムへの評価データを用いないimplicitな方法とアイテムへの評価データを用いるexplicitな方法に分けている.

・implicitな方法
implicit-tag: 前節のアイテムへのratingを用いないすべての方法を用いて推測したタグへの興味度を用いてアイテムの興味度を推定している.
implicit-tag-pop: 前述の方法に,アイテムの全体での人気度を加えている.

・explicitな方法
前節のアイテムへのratingを用いる方法を用いて推測したタグへの興味度を用いてアイテムの興味度を推定している.
cosine-tag: ユーザの映画への評価は,その映画についているタグの評価重みの平均であると仮定している.
Linear-tag:映画に付けられた各タグごとにタグの好みの推測値と映画への評価値の最小二乗適合を推定する.
Regress-tag: linearタグでは,タグを独立に推定しているが,本手法は線形モデルで表現し,各係数を同時に推定している.

実験では,上記の方法と,従来の協調フィルタリングと比較している.

Top-5では,linear-tag, regress-tagなど,タグを使った手法が強調フィルタリングよりよくなっている.MAEでは,協調フィルタリングがよくなっている.

このような差が出た理由は考察されていない.この点が残念である.



|

静的Webページは絶滅する?

先日,「デジタル資産の相続」というテーマで記事を書きました.使わなくなったけどIDは残っているサービスがあるという話もしましたが,気が付いたら終わっているサービスも少なくないようです.

9/10に,インフォシークより,
・インフォシーク iswebライト (無料ホームページサービス)
・インフォシーク iswebライト 広告非表示オプション (有料版)
のサービス終了の案内がきました.

インフォシークと言えば,ホームページプロバイダの大手の一角でしたが,ホームページサービス終了の案内には正直驚きました.

サービス終了の理由に,
「インターネットの発展に伴い情報発信ツールも多様な進化を遂げており、無料のホームページスペース提供サービスとして運営してきた「インフォシーク iswebライト」は当初の役割を終えた」
とありました.

ブログ,SNS,Twitterに駆逐されてしまったというのが実際のところでしょう.

自動生成されたHTML,すなわち動的コンテンツで支配された,ハイパー空間.それがすなわち現在のWebということなのでしょう.HTMLという言葉も,いずれ死語になるように思います(Webの利用者がHTTPを意識しなくなったのと同様に).

研究者の多くの今のWebコンテンツに対しての捉え方はどんなもんなんでしょう?自動生成されたHTMLで支配される空間.という認識には至っていないような気がしますが・・・

Web空間が少ないシステム(コンテンツ自動生成ツール)により提供されているとすると,その構造や特徴が変わる時というのも,急激になるかもしれません.ヒューリスティックベースの研究は,このことをよく考えておかないといけません.

|

FIT2010 ポスト情報爆発へ向けて

9月8日(水)10:00-12:30に,FIT2010にて,「ポスト情報爆発へ向けて-Beyond Webの展望-」というテーマでパネル討論を行います.メンバーは,司会:山名早人氏(早大),森正弥氏(楽天),後藤真孝氏(産総研),寺田努氏(神戸大),土方嘉徳(阪大)です.

10分ほど,各パネリストの講演がありますので,3つほど最新の研究事例について紹介した後,私のWeb研究のスタンスや研究フィロソフィーなどについて述べたいと思います.

[討論概要]
Webは,その出現から約20年を経て,世界規模でのコミュニケーションや,「情報爆発」と称される膨大な情報の処理や活用が求められる状況を創り出した.そして,ありとあらゆる情報を簡単に入手できるようになった.「情報爆発時代」にいる我々は,5年後,10年後を見据え今何をすべきか,本パネルでは「Beyond Web」をテーマに,まず4人のパネラーに,それぞれの立場から講演をしていただく.具体的には,ビジネスにおける様々な履歴・ログデータの活用,急速にその重要性が増しているソーシャルメディアの活用,さらには,情報爆発時代が可能とした音声情報検索,ウェアラブルコンピューティングといった新しい情報活用の視点から「Beyond Web」を考える.「情報爆発からの恩恵を最大化することができるのか」「Webを超える新しい情報活用とは何か」「今はじめなければならない研究は何か」等々,様々な角度からの議論を会場の皆様と共に進めていく.

https://www.gakkai-web.net/gakkai/fit/program/dvd/html/event/index.html
より引用.

FIT2010
会期:2010.9.7~9
会場:九州大学伊都キャンパス
   (福岡県福岡市西区元岡744)
http://www.ipsj.or.jp/10jigyo/fit/fit2010/index.html

|

国際会議WWW2009論文感想その3

Maria Grineva, Maxim Grinev, Dmitry Lizorkin: Extracting key terms from noisy and multitheme documents, Proc. of WWW 2010, pp.661-670, 2010.

Webページ中からキータームを抽出する研究である.自然言語処理において,キーターム抽出は,近年注目されているタスクである.注目される理由としては,Google AdSenseやYahoo! Contextual Matchのような,キーワードマッチベースのWeb広告が盛んであるからである.
従来のキーターム抽出は,(1) TFIDFを用いる方法,(2) 教師あり学習(ナイーブベイズ)を用いる方法,(3) Wikipediaのリンク情報を用いる方法,(4) N語のウィンドウ幅において共起した語からグラフを構築し,PageRankのアルゴリズムを用いが方法が提案されている.

(2)は,特徴としてTFIDF,語の文書内での出現位置,訓練データ中でキーフレーズとして出現する回数を用いて,学習している.(3)は,Wikify!というシステムであるが,keyphrasenessという指標を用いている.keyphrasenessは,その語がWikipedia内でリンクとして現れる記事の数をその語がWikipedia内で洗われる記事の総数で割った値である.

本手法は,提案手法そのものは既存の方法を組み合わせたもので,あっと驚くことはないが,うまく組み合わせている点,グラフベースの方法でPageRankではなく,Newmanのモジュール性を用いたクラスタリングを用いている点で新規性がある.

方法論としては,
(i) 入力文書からnグラムを抽出し,Wikipediaの記事集合を特定する.
(ii) Wikipeia内の曖昧語のページ(多義語に関して複数の意味を列挙し,その意味で説明しているWikipedia文書へのリンクお持っているページ)から,(i)の入力文書の単語と前記リンク先の単語から,おそらく共起頻度を用いて,1つの意味へ特定付けする.
(iii) 2つの語を説明するそれぞれのWikipedia内のページでの語の共起数より,単語間の距離を求めて,重み付きグラフを生成する
(iv) Newmanのモジュール性によりクラスタリングを行う.クラスタリングのための距離には,コミュニティのdensityとinformativenessを用いている.densityはコミュニティ内のエッジの重みの合計をコミュニティの頂点の数で割ったものである.informativenessは,keyphrasenessである.

評価は,TFIDF,Yahoo! terms Extractor,Wikify!,TextRank(PageRankを用いる方法)と比較している.ブログ本文,Webページ,複数トピックが入ったWebページにおいて比較し,従来手法よりも提案手法が良い結果を出すことを示している.

感想であるが,提案手法はあっと驚くものではないが,既存の手法をうまく組み合わせ,またモジュール性をキーターム抽出に用いたという点で,新規性があると思う.従来研究との比較実験もなされており,お手本のような研究・論文である.

|

« 2010年8月 | トップページ | 2010年10月 »