Budgeted stream-based active learning via adaptive submodular maximization - todo314 @ ウィキ

Budgeted stream-based active learning via adaptive submodular maximization

• Kaito Fujii, Hisashi Kashima
• NIPS 2016

概要

• ブール型能動学習→ストリーム型能動学習
• 適応的劣モジュラ→この研究

1. 問題定式化: オンラインの適応的劣モジュラ最大化
2. 方策適応的劣モジュラ性
3. ストリーム・秘書設定での定数競合比アルゴリズム

動機づけ

• ラベルを手に入れるのにコストがかかる…スパムフィルタとか
• 能動学習: どのサンプルにラベルをつけるか決めたい
  • ブール型…ラベルなしサンプル全体が既知
  • 今回の設定=ストリーム型…1つずつ（メモリ制限も加味）
    • 例: スパム、監視カメラ、ウェブストリーム分析…
• 適応的劣モジュラ最大化フレームワーク
  • 近似保証＋実装が簡単（貪欲するだけ）

適応的最大化

• ラベル付与オラクルφ
  • 事前分布p(φ)が与えられる…モデルを考える
• f_φ(S)…φを事前分布からとってきた時に、Sを暴くことで、どれくらい仮説が棄却されるか
• f_φ(S)の期待値を最大化するような決定木=方策πを探す

オンライン適応的最大化

• ここから研究の内容
• ストリーム設定: 過去いくつかを保持して、後でオラクル問い合わせしてラベル付与できる
  • こっちのが新しい
• 秘書設定: その場でラベル付与するか判断
  • 昔からあったらしい
• 方策適応的劣モジュラ
  • 適応的劣モジュラより強い性質
  • でも、結構成立する
  • E[f(A(r))]≧(1-r)f(0)+rf(A)…っぽいのが成立する
    • ただの適応的劣モジュラだと成立しない
• n個からk個選ぶ場合
  • n/k個毎に分けて個々に秘書問題のアルゴリズムを適用

NIPS 劣モジュラ 影響最大化 能動学習

2017/01/30