NIPS2012より識別モデル学習の進展を垣間見る

こんばんは．[twitter:@kisa12012]です．しがない機械学習系大学院生をやっております．Machine Learning Advent Calendar 2012 9日目では，"NIPS2012より識別も出る学習の進展を垣間見る"という無駄に野心的なタイトルで，先ほどまで開催されていたNIPS2012で発表された数本の論文概要を紹介します．機械学習，特に識別モデル学習の最先端が多少なりとも垣間見える，もしくは論文本体を読んでみようと思わせられる記事になっていれば幸いです．
重要: 概要紹介のみですので，数式は一切出てきません．（数式を記述する前に力尽きました……）

NIPS2012とは？

ホームページ : http://nips.cc/Conferences/2012/
機械学習のトップ国際会議の一つ．機械学習の理論的な面を解析した論文や，理論的背景を持ったアルゴリズムの導出を提案した論文が多いですが，脳科学・ロボット・画像解析・言語解析等への機械学習応用を目的とした論文も数多く出ている会議です．MLAC 6日目の[twitter:@koh_t]さんの記事もNIPS2012で発表された論文です．
今年は，12月3日〜8日までアメリカネバダ州のレイク・タホで開催されてました．
NIPSについて詳しくは，朱鷺の社のNIPS紹介の記事をご参照下さい．

紹介する論文

今回紹介するのは，以下の識別モデル学習に関連した3本の論文です．

Learning Multiple Tasks using Shared Hypotheses
A Stochastic Gradient Method with an Exponential Convergence Rate with Finite Training Sets
Volume Regularization for Binary Classification

ICML2012読み会で発表しました && SVMの性能をガタ落ちさせるためには

本日サイボウズラボさんの会場で開催されたICML2012読み会に発表者として参加しました．
主催者のnokunoさん，会場係のshuyoさん，また参加者の皆様，ありがとうございました！非常に勉強になりました．
今回発表したのは，Poisoning Attacks against Support Vector Machines (Biggio+) です．

発表資料

元論文

http://icml.cc/2012/papers/880.pdf

概要

  • 論文の名前通り，SVMの訓練データに毒を盛るためのアルゴリズムを提案
  • 毒を盛るとは，すでに学習されたSVMのパフォーマンスを劇的に下げるためのデータを生成して，SVMの新たな教師データとして潜り込ませること
  • 手書き文字認識での実験では，たった１データ組み込むだけで精度を２割落とすことに成功

まとめ

読み会でも議論になった通り，SVMの訓練データ全てが攻撃者が知っている前提はかなり非現実的です．より現実に即した問題設定でのアルゴリズムや解析が今後の課題になります．
その他にもスライドのFuture Workで示しているように，著者自身が発展的な内容について色々言及しています．
とにかく分類器の精度を徹底的に落とすデータを生成しよう！という問題設定が新しく，今後この論文を元にロバストな分類器の生成等，様々な発展を遂げていくのではないでしょうか．

Exact Soft Confidence-Weighted Learning (ICML2012) 読んだ

概要

オンラインでの分類学習の世界では，CWが非常に強力なアルゴリズムとして注目されています．特に，その圧倒的な分類精度及び収束速度は圧巻の一言であり，自然言語処理を中心に様々な分野で応用例や派生アルゴリズムが提案されています*1．
一方で，ノイズデータのが混入していた場合に精度がガタ落ちする性質がCWの重大な欠点として多くの人から指摘されていました．ノイズが予め取り除かれている実験設定ならば良いのですが，ノイズが含まれている可能性の高い実データにはCWは中々不便．この問題を解決するため，ノイズ耐性の強いCW系アルゴリズムの決定版（？）として，SCW (Soft Confidence-Weighted)アルゴリズムがICML2012という会議で提案されました．本エントリでは，SCWの紹介を行います．

Exact Soft Confidence-Weighted Learning, Wang et al., ICML2012
http://icml.cc/2012/papers/86.pdf

CW (Confidence-Weighted Algorithm) *2

CWをはじめに少し紹介します．CW等のアルゴリズムでは，入力として与えられるベクトル \mathbf{x} と 重みベクトル \mathbf{w} との内積の符号 sign(\mathbf{x} \cdot \mathbf{w})を用いて分類を行います*3．

オンライン学習では，データを一つ読むたび，重みベクトルの値 (分類器)をより良いパラメータに更新します．ただし，一般の分類器では，各素性の出現頻度や学習度合の情報を考慮していないので，最適な値が大体判明した素性も，学習が全くなされていない素性も等価に扱われます*4．
上記の問題を解決するため，パラメータへの信頼度(Confidence)を導入し，CWでは重みベクトルがただの点ではなくガウス分布に従うと仮定します．重みベクトルの更新に分布の概念を導入することで，信頼度の低い(素性に関する情報があまり無い)パラメータは大きく更新し，一方で信頼度の高いパラメータはあまり変化させない，adaptiveなアルゴリズムを導出します．

  • CWの重みベクトル

\mathbf{w} \sim N(\mathbf{\mu}, \mathbf{\Sigma})

データを一つ受け取る度(入力ベクトル\mathbf{x}_tとラベルy_t)，以下の更新式に従いパラメータを更新します．
(\mathbf{\mu}_{t+1}, \mathbf{\Sigma}_{t+1}) = \arg \min_{\mathbf{\mu}, \mathbf{\Sigma}} \quad KL(N(\mathbf{\mu}, \mathbf{\Sigma}) | N(\mathbf{\mu}_t, \mathbf{\Sigma}_t)) \quad \quad s.t. \quad {Pr}_{w} (y_t \mathbf{w} \cdot \mathbf{x}_t \geq 0) \geq \eta
制約式の部分は，ガウス分布にしたがって重みベクトルをサンプリングした時に，受け取ったデータを上手く識別できる確率が \eta以上になる事を条件付けています．KLとかかれた関数はKL-divergenceを示しており，ガウス分布間の「距離」を測ります．制約式を満たすガウス分布の中で，前のガウス分布から一番形を変えずに済む（距離が最小となる）新しいガウス分布への更新を上記の最適化問題で実現できます．この更新式は \mathbf{\mu}, \mathbf{\Sigma}ともに閉じた形で更新式を導出することができます．(Section 2.3の(3)式参照)

CWは線形分離可能なデータに対して，有限回の更新で必ず全てのデータを上手く識別出来るパラメータを求められる事が保証されています．

CWのノイズ耐性

ただし，前述のようにCWはノイズを多く含むデータから学習を行う時精度がガタ落ちすることが指摘されています．今受け取ったデータにノイズが含まれていたとしても，「必ず\eta以上の確率で分類できる」ようにパラメータを更新するためです．\etaの値を小さくすればノイズ耐性は多少強くなるけれども，正確なデータから学習をする際にもガウス分布の更新が緩やかになるため，最適なパラメータへ収束する速度も遅くなります．
ラベル付を誤ったデータや全体と性質の大きく異なるデータが混入しているデータから学習を行う時に特に問題となり，ノイズ的なデータでの更新の際に，急にパラメータがあらぬ方向へぶっ飛ぶ可能性があります．CWの提案後にこの問題は数多くの分野から指摘されており，急なパラメータ変更を防ぐ方法として複数の改良型アルゴリズム(AROW, NAROW, NHERD etc...) が提案されてきました．

SCW (Soft Confidence-Weighted Learning)

SCWもノイズ耐性に着目してCWに改良を施したアルゴリズムです．SCWは，「確率\eta以上で正しく分類する」という絶対条件を緩めます．ガウス分布を大きく変更せざるを得ない場合には，1-\eta以上の誤分類率を許容し，急激なガウス分布の変化を防ぐ事が可能になります．

さて，最適化問題を変形します．Passive Aggressiveのソフトマージン化(PA-I,II)をご存知の方は見覚えがある変形になるかもしれません．
ガウス分布の定義に基づき，CWの制約式の部分を変形します*5．
y_t (\mathbf{\mu} \cdot \mathbf{x}_t) \geq \phi \sqrt{\mathbf{x}_t^{T} \mathbf{\Sigma} \mathbf{x}_t}
ここで，\phiはガウス分布の累積密度関数の逆関数を\etaで評価した値です．
この式を用いて，「\eta以上の確率で正しく識別する識別平面からみた信頼度による重み付けマージン」を評価する，新たな損失関数を定義します．
\ell (N(\mathbf{\mu}_t, \mathbf{\Sigma}_t); (\mathbf{x}_t, y_t)) = max(0, \phi \sqrt{ \mathbf{x}_t^{T} \mathbf{\Sigma} \mathbf{x}_{t} }-y_{t} (\mathbf{\mu}_{t} \cdot \mathbf{x}_t))
信頼度の高いパラメータを重視し，信頼度の低いパラメータはいくら平均値が大きくてもあまり重視しないように損失関数が定義されており，CWの長所が上手く保持されています(ルートの中身の値が大きくなる)．

この損失関数を用いて，CWおよびSCW-I,IIの最適化問題を以下のように定義します．

CW *6

\arg \min_{\mathbf{\mu}, \mathbf{\Sigma}} \quad KL(N(\mathbf{\mu}, \mathbf{\Sigma}) | N(\mathbf{\mu}_t, \mathbf{\Sigma}_t)) + \infty( \ell (N(\mathbf{\mu}_t, \mathbf{\Sigma}_t); (\mathbf{x}_t, y_t)))

SCW-I

\arg \min_{\mathbf{\mu}, \mathbf{\Sigma}} \quad KL(N(\mathbf{\mu}, \mathbf{\Sigma}) | N(\mathbf{\mu}_t, \mathbf{\Sigma}_t)) + C ( \ell (N(\mathbf{\mu}_t, \mathbf{\Sigma}_t); (\mathbf{x}_t, y_t)))

SCW-II

\arg \min_{\mathbf{\mu}, \mathbf{\Sigma}} \quad KL(N(\mathbf{\mu}, \mathbf{\Sigma}) | N(\mathbf{\mu}_t, \mathbf{\Sigma}_t)) + C ( \ell (N(\mathbf{\mu}_t, \mathbf{\Sigma}_t); (\mathbf{x}_t, y_t))^2)

上記の式から，SCWは損失関数を厳密に解くことなく，パラメータCを用いて上手くガウス分布の急激な変化と損失関数値を調節するように変形されていることが確認できます．SCWはCWと同じく閉じた形での更新式が記述できます．更新式は3章のProposition1 (SCW-I), Proposition2 (SCW-II)にて記載されています．更新式の導出は込み入った式変形が必要で，Appendixでゴリゴリと計算がされています．

また，SCWは

  • 「ガウス分布間の距離」 と 「信頼度重み付けマージン」 以外 の補助的な項を一切導入しない

点で，その他のノイズ耐性を持つCW系アルゴリズムと一線を画しています．SCWの最適化問題は，ソフトマージンSVMの最適化問題を元にしており，

  • 信頼度(Confidence)に応じて重み付けが変化する，マージン基準でのパラメータ更新を実現

している点がAROWやNHERD等と異なり，"Adaptive margin"を満たしている，と著者は書いています．また，CWと同じくSCWでも損失上限値の評価がされており，一定の条件下では損失の総和が爆発しないことが示されています．論文中の実験でも，AROW等のアルゴリズムと比べ非常に高速に収束する事が示されています．より少ないデータで高精度な分類器が導出されるのは，この"Adaptive margin"の性質ゆえであると著者は主張しています．

実装

せっかくなので，SCWを実装してみました．コードは汚いので参考にならないと思います．

classifier/src/confidence_weighted kisa12012/classifier GitHub https://github.com/kisa12012/classifier/tree/master/src/confidence_weighted

実装上の工夫として，上記のアルゴリズムから２点変更を施しています．

  • 共分散行列の非対角項の零化

共分散行列の非対角項の零化ですが，共分散行列の非対角項を厳密に計算して精度が上がることはかなり稀です．CWおよびSCWの計算速度およびメモリ使用量のボトルネックになっているのは共分散行列の非対角項成分なので，ここの更新をどうサボるか重要になります．CWの論文でも計算量の削減のため，対角項のみを扱ったアルゴリズムが提案されています．
実現方法は単純で，共分散行列\mathbf{\Sigma}の更新時に，\mathbf{x}_t \mathbf{x}_t^T*7の非対角項を0にするだけです．

  • 多クラスへの拡張

Multi-ClassCWと同様の多クラス拡張をSCWに施し，3クラス以上の場合もSCWで学習可能な形にしています．

最後に簡単な実験結果を記載します．実験設定は，CW/SCW-I/SCW-IIに対して，Libsvm Datasetのrcv1.binary, rcv1.multiclassに適用してみました．ハイパーパラメータC, \etaの設定は適当．反復回数は1回(ワンパス)です．時間の方は正確に測ってはいませんが，更新式から分かる通り大きな差異はありません．
結果は以下のとおり．テストデータ中の正答数で比較しています．

rcv1.binary
CW
correct : 651136 / 677399
SCW-I
correct : 651462 / 677399
SCW-II
correct : 651085 / 677399

rcv1.multiclass
CW
correct : 456018 / 518571 
SCW-I
correct : 456634 / 518571
SCW-II
correct : 456399 / 518571

あまりノイズの多くないデータセットでの実験のためかそれほど大差は付きませんでした．が，SCWがコンスタントに強い事は示されています．ワンパスでほぼ収束し，反復回数を増やしてもそれ程精度は向上しません．流石CW，SCWです．ハイパーパラメータ設定を適当にやってこの結果なので，もう少し頑張ってパラメータチューニングすればSCWはさらなる精度向上が可能なんじゃないかなと推測しています．ただ，ハイパーパラメータが2つあるのでチューニングにはかなり手間がかかるため，適当にパラメータを設定しても良い識別器が導出できるSCWは安心して利用できます．
実データに関しては，まずはSCWから試してみる，で始めて問題ないのかなと思っています．

まとめ

  • SCWは，CWの弱点，ノイズや直前のデータへの脆弱性を緩和
  • AROW / NAROW / NHERDとの違いは，信頼度重み付けソフトマージン最大化を追求している点
  • CWと同じく損失上限値の証明もあり
  • もう線形識別器はSCWでいいんじゃないかな (他の問題が発見されるまで)

最後に

CWを実装されている方は，もし時間があればSCWを実装してみて試すことをおすすめします．また，更新式の導出方法や理論解析の詳細を追いたい方は，原論文を辿ってみる事を推奨します．特に2章のRelated Workでは，PA->CW->AROW->SCWの一連の流れが簡潔に纏められているため，オンライン学習系に興味がある方は必読と言ってもいいかも……？
上記の説明に誤りや勘違い等あれば指摘頂ければ幸いです．

参考文献

  • Exact Convex Confidence-Weighted Learning, Crammer et al., NIPS2008
  • Multi-Class Confidence Weighted Algorithms, Crammer et al., EMNLP2009
  • Adaptive Regularization of Weight Vectors, Crammer et al., NIPS2009
  • New Adaptive Algorithms for Online Classification, Orabona et al., NIPS2010

*1:SVMやPerceptronは全て捨てて，CWに移行してしまうのも良いと主張する研究者もいます．http://nlpers.blogspot.jp/2009/08/classifier-performance-alternative.html

*2:CWは様々なところで紹介されており，日本語の資料も充実しているため，そちらを参照されるのが良いかと思います．

*3:例として，レビュー文書のポジティブ・ネガティブ判定の場合，入力ベクトル x はレビュー文書中の各単語の出現回数を並べたベクトルとして表せます．この時，内積の値が0より小さければ，その文書をネガティブなレビューとして判定するようにタスク設定できます．レビュー文書を正確に分類できる，最適な重みベクトルの値を求めるために学習を行います．

*4:”I like the author, but this book is dull.”といったレビュー文書が与えられた時，”like”がレビュー文書をポジティブであると判定する上でとても有用な素性であると分かっていたとしても，その情報を扱うことが出来ず，”dull”と”like”に対しパラメータの更新は等価に施されます．

*5:ここの式変形を追いたい方は，CWの原論文を辿ると良いです．SCWの論文中には記載されていません．こちらの勉強会資料でもざっくり説明しています．http://www.r.dl.itc.u-tokyo.ac.jp/~oiwa/upload/AROW.pdf

*6:この定義は厳密ではなく，損失関数が制約の形で表現されるのが本来のCW

*7:論文中の\Sigma_t \mathbf{x}_t^T \mathbf{x}_t \Sigma_tは，\Sigma_t \mathbf{x}_t \mathbf{x}_t^T \Sigma_tの誤りと思われます．

最適化本自分用メモ1章

Optimization for Machine Learning

Optimization本の自分用メモを少しずつ書いていこうと思います．各章に何が書いていたかを自分なりに纏めることで，後で見なおした時に過去に理解したことを復元するための種みたいなものとする事がこのメモの目的です．他の人が読んだ時に少しでも参考になる部分があれば幸いです．

1. Introduction

  • 最適化は機械学習において重要な位置を占める．
  • 本章では，機械学習で頻繁に用いられるSVMと正則化項付き最適化の２つの問題とその求解法を概観し，機械学習における最適化技術の役割を俯瞰する．

1.1 SVM

SVMの定式化．マージン最大化を達成するように重みベクトルを求めることが目的となる．SVMには，主問題の他に双対問題への変形，ソフトマージンと呼ばれる亜種が存在し，目的に応じて使い分けられる．SVMで解きたい問題となるのは，凸２次計画問題．この問題を如何に解くかに注目が集まっており，様々な最適化手法が提案されてきた．

  • 双対問題に対してのSMO・内点法が代表的な手法として知られている．
  • また，SVMは入力ベクトルを線形分離可能な空間へ写像する操作をカーネルによって実現可能である．
  • 双対問題において，写像後の入力ベクトルを陽に扱うことなく特徴空間における最適化を可能にする性質（カーネルトリック）を持つ．
  • データが大規模な場合，確率的勾配降下法による主問題の求解という方法も．
SVMに関係する章
  • 内点法，特に2次計画問題に対する内点法(3,12章)
  • SGDその他大規模データに対する最適化(13章)
  • その他 (11, 14章)

1.2 正則化項付き最適化

モデルを理想とする構造に近づけるため正則化項を最適化問題に導入する．正則化項を導入した最適化問題を正則化項付き最適化問題と呼ぶ．SVMも正則化項付き最適化問題の特殊ケースである．

正則化項を導入する目的
  • 汎化性能の向上
  • 重みベクトルのスパース化
  • 行列補完の低ランク性制約
  • 既知の補助情報の付加 等があげられる．

また，それぞれの目的に合わせた正則化手法が提案されている．アルゴリズムは，（近接）勾配法ベースの求解法が代表的である．その他，グラフマッチやブロック座標緩和等を使用する方法も存在する．

正則化項付き最適化に関係する主な章
  • 正則化項付き凸最適化問題の双対理論と正則化項のより詳しい解説(2章)
  • min-max系への変形とその求解法，さらに高速解法 (6章)
  • その他(7,9,11,17,18章)

1.3 本の構成

  • 省略

機械学習を様々なアプリケーションに適用するためのアドバイス

Andrew Ngの講義で面白いスライドがあったので紹介．研究ではなく様々なアプリケーションへ機械学習を適用するときに実践すべきTipsが３つのトピックに関して語られています．以下は，スライド内で自分が覚えておくべきと思った部分を抽出し，メモ書きしたもの．実サービスやKDD Cup等のコンテストで機械学習を用いる度に，見返してみるのも良いかもしれません．

スライド

http://see.stanford.edu/materials/aimlcs229/ML-advice.pdf

トピック１．Debugging Learning Algorithms

  • 適当な分類器を学習させ，スパムフィルタリングでエラー率20%を達成したら次に何をすべきか？
    • 訓練データを増やしたり，より良い分類器を適用したり，色々な改善策が考えられる…
  • 診断法1 : バイアス-バリアンス分析
    • 現在の分類器のボトルネックはバイアスか，バリアンスか
      • 訓練データでもエラー率が20%程度なら，バイアスが高いと考えられる
      • この場合，もっと特徴量の数を増やすべき
      • 訓練データの精度がテストデータよりもよければ，バリアンスが高いと考えられる
      • 過学習の可能性が高いため，データ数を増やす，特徴選択を行う等の処置が適当
  • 診断法2 : 目的関数が適当か
    • アルゴリズムが正しくても収束先が不適当ならば，そもそも目的関数を変更すべき
      • スパムフィルタリングならば，precisionを重視した目的関数を設定
      • 目的と合った収束先を持つアルゴリズムに変更することも考えられる
    • 収束先が適当ならば，後は収束性の問題
      • 反復数を増やす，より高速に収束する最適化法を用いるなど

トピック2. Error Analysis

  • 実際のアプリケーションは，前処理から分類器学習まで多くの機械学習手法がパイプライン的につながっている
  • 各コンポーネントが最終結果にどの程度影響しているのか分析することは，その後の改良のために非常に重要

トピック3. Getting started on a learning problem

  • 設計をじっくり考えてから実装するか，とりあえず実装してエラー診断・分析を繰り返し改良を重ねるか
    • 前者は，スケーラブルで高精度，汎用性の高いシステムを作りたい時に有用
    • いち早くサービスなどの形で世に送り出したいならば，後者の方が良い

WWW気になった論文リスト

ただソーシャルメディアやマイクロブログを上手く利用しただけ論文は殆ど見かけなくなってきていますね．クラウドソーシングの新たな使い道を考案しました，な論文はちらほら．他には，ユーザー間を協調させる仕組みを作るサービスであったり，Twitterの中でも表層からは全然想定できないような潜在的意味を取り出す論文が多い気がします．機械学習を使ってほげほげ，というだけの論文も減りました？（昔からこれくらいだったかも）

  • A Unified Approach to Learning Task-Specific Bit Vector Representations for Fast, Nearest Neighbour Search
    • Vinod Nair, Dhruv Mahajan and Sundararajan Sellamanickam
    • ビットベクトル＋近傍探索＋分野適応とかwktk
  • Discovering Geographical Topics from Twitter Streams
    • Liangjie Hong, Amr Ahmed, Siva Gurumurthy, Alex Smola and Kostas Tsioutsiouliklis
    • Twitterから地理局所的なトピックの抽出
  • Document Hierarchies from Text and Links
    • Qirong Ho, Jacob Eisenstein and Eric Xing
  • Economics of BitTorrent Communities
    • Ian Kash, John Lai, Haoqi Zhang and Aviv Zohar
    • Bittorrentコミュニティの経済学とは
  • Estimating the Prevalence of Deception in Online Review Communities
    • Myle Ott, Claire Cardie and Jeff Hancock
    • レビューサイトの偽レビュー検出．ホットトピック？
  • Factorizing YAGO: Scalable Machine Learning for Linked Data
    • Maximilian Nickel and Volker Tresp
  • Learning from the Past: Answering New Questions with Past Answers
    • Anna Shtok, Gideon Dror, Idan Szpektor and Yoelle Maarek
    • Q＆Aサイト等で回答をするときに，過去の回答を用いる
  • Who Killed My Battery: Analyzing Mobile Browser Energy Consumption
    • Narendran Thiagarajan, Gaurav Aggarwal, Angela Nicoara, Dan Boneh and Jatinder Singh
    • モバイル機器のブラウザで，どの機能がバッテリーを一番喰っているのか？

能動学習入門的な話をしました

修論の原稿提出と国際学会の論文締切が１日違いなため，両方の作業を同時で進める日々を送っております今日この頃，皆様いかがお過ごしでしょうか．
今回は，先日PFIセミナーにて発表しました能動学習入門的な話の補足を少し述べたいと思います．
（レイアウトが崩れている場合，スライドをダウンロードしてから開くと治る可能性が高いです．）

能動学習セミナー
発表のUstream

能動学習

能動学習とは，教師データを作成する際に最大の効果を発揮するように教師とするデータを選択する方法についての研究分野であり，機械学習の一分野です．一般的にデータに正解を振るのは高いコストが要求されるため，どのデータに正解ラベルを付与すればより高精度な学習器が作成出来るか，を知る事が出来ればラベル付けのコストが格段に低減できます．基本的な枠組み・手法については，上のスライドで説明しています．

能動学習の有効性

能動学習の有効性については，未だ各論あります．上記のスライドで説明した以外にも能動学習の問題点として，

  • 教師データを作成する毎に，与えられるデータがラベル付け困難なものとなる

という点もあります．
一方で，ラベル付けにかかるコストが大きな問題とならない場合でも，可能な限り少ない質問でユーザーの興味や性向を測りたい場合にも能動学習が有効となるタスクも存在するかと思います．(Akinatorのようなイメージ）
タスクによって能動学習が有効な場合もあれば，大量に教師データを用意した方が有効な場合もある，というのが現状のようです．

理論研究

本セミナーでは，能動学習の応用例に焦点を当てて近年の研究について紹介しました．一方で，理論面の研究に関しては，重要度重み付けを損失関数に施す事でサンプリングバイアスを解決できることを示すとともに，その他の重要な性質について考察しているImportance Weighted Active Learning[Beygelzimer+, 2009] やノイズのあるデータセットに対しても効率的な能動学習を可能とする手法である Agnostic Active Learning [Balcan+, 2008][Beygelzimer+, 2010] 等が挙げられます．ICML2009のTutorialでAgnostic Active Learningの概要が述べられています．また，これらの能動学習手法を実装したオンライン学習ソフトウェアとして，Vowpal Wabbitがあります．

総論として

能動学習を使用すべきか否か，という議論が出来ただけでも，このような技術の紹介をした価値があったかな，と思っています．発表の機会を頂いたことに感謝したします．