EMNLP気になった論文メモ

研究
  • 上の２つは特に気になった論文．

Approximate Scalable Bounded Space Sketch for Large Data NLP

  • Amit Goyal and Hal Daume III.
  • pdf

Rumor has it: Identifying Misinformation in Microblogs

  • Vahed Qazvinian, Emily Rosengren, Dragomir R. Radev and Qiaozhu Mei.
  • pdf

Class Label Enhancement via Related Instance

  • Zornitsa Kozarev, Konstantin Voevodski and Shang-Hua Teng.
  • pdf

Dual Decomposition with Many Overlapping Components

  • Andre F. T. Martins, Noah A. Smith, Pedro M. Q. Aguiar and Mario A. T. Figueiredo.
  • pdf
  • Attachment

クラウドソーシング時代の能動学習

研究

例によって，ICML2011からActive Learning from Crowdsのメモ書きです．
クラウドと銘打ってはいますが，結局のところ複数アノテーターがいるときにどのように能動学習を行うとよいか，という手法提案の論文になっています．

概要

  • アノテーターが複数いる場合の能動学習手法の提案
    • ラベル付けしたいデータに関して，一番信頼できるアノテーターのラベル付け情報を信頼する
    • ただ単に多数決を取るよりも高い精度を達成

能動学習 (Active Learning)

  • 今までラベル付けしたデータから学習器を生成
  • 上手く分類出来ないデータ（今後の学習に一番有効なデータ）を選び，アノテーターによるラベル付け
  • 上記の操作を繰り返す

複数アノテーター

  • 多くの教師あり学習では，一人のアノテーターがラベル付けすることを暗に仮定
    • この仮定は本当に正しいか？
    • 近年は，多くのあのテーターが同時にラベル付けする事も多い
    • Ex. Amazon Mechanical Turk

複数アノテーターの利点

  • 専門家間でも意見が食い違う事が多い
  • データによって必要な専門知識が異なる
  • 専門家一人雇うよりも，複数の非専門家を雇う方がローコスト
  • アノテーター間の知識共有がより簡易かつ一般的になっている
    • 以上の理由から，複数アノテーターが流行っている

複数アノテーターの問題点

  • あるアノテーターは他のアノテーターより信頼できる
  • 悪意のあるアノテーターが入り込む
  • あるアノテーターが別のアノテーターに影響を受ける
  • アノテーターによって事前知識（事前分布）が異なる
  • データの分け方によって結果が異なる

やりたい事

  • 複数アノテーターにおけるActive Learningでは，同じデータでも意見が割れることがあり，正しいラベル付けを行うのが困難
    • ラベル付けを行うべきデータを同定したい
    • 一番信頼できるアノテーターを同定し，その人のラベル付けを信頼したい

モデル構築

  • まずは，マルチアノテーターモデルを構築

p(Y,Z|X) = \prod_{i} p(z_i | \mathbf{x}_i) \prod_{t | t\in \tau_i} p(y_i^{(t)} | \mathbf{x}_i, z_i)

    • x_i : 入力ベクトル， z_i : 出力ラベル， y_i^{t} : アノテーターtがつけた出力ラベル， \tau_i : データiにラベル付したアノテーター集合
    • EMを使えと言わんばかりの式
  • 次に上のモデルから，以下の処理を繰り返す（式略）
    • ラベル付けを行うべきデータポイントを探索，そのポイントに一番近いデータを抽出
    • 一番信頼できるアノテーターを同定し，そのデータにラベルを付与
    • パラメータを再学習

個人的に思うところ

  • Multi-AnnotatorsのコンセプトとActive Learningのコンセプトが相反している気がして，これらを組み合わせることに納得が行かない
    • Active Learningは，ラベルが曖昧でないデータは学習によってラベル付を行う．曖昧なデータは正確なラベルを付与することで高性能な学習器を低コストで生成する，という理解
    • 一方Multi-Annotatorsは，専門家でない大量のアノテーターを集めて，高速かつ安価にラベル付け可能にする，という理解
    • 少量のデータでラベル付け出来ない部分は，Multi-Annotatorsを用いても意見が割れるだけなので，こういうデータのラベル付けにこそ専門家が必要なのでは
    • その意味では，一番信頼できる人を見つけ出そう，という意図自体は良いと思うが…

ドメイン適応を用いた評判分析手法

研究

ICML2011のドメイン適応の論文のメモ書き．数式番号が1つも使われていない，珍しい論文．
Domain Adaptation for Large-Scale Sentiment Classification: A Deep Learning Approach

概要

  • 評判分析，評判抽出のためのドメイン適応手法の提案
    • Deep Learningというアプローチを採用
    • 特徴の上位概念（製品の質，コストパフォーマンス等）を学習する
  • 大規模データ解析，大量のドメイン適応を同時に行うことが可能

Domain Adaptation

Deep Learning

  • 特徴の階層構造を学習 (今回のタスクの場合）
    • Ex. 特徴そのものではなく，製品の質，値段，顧客サービス等の要素を探索する
  • Stacked Denoising Auto-encoders(SDA)などの手法
    • 特徴の中間表現へのEncoder / Decoder を学習する
    • PCAみたいな事をやっていると思えば良い

評判分析でDeep Learningを用いることの利点

  • 多くのドメインで共通の概念が存在する(製品の質，値段等）
  • 上記の概念を表す代表的な単語があらかじめ予測できる
  • 評判分析以外のタスクでも，Deep Learningによって面白い知見が得られている
  • ドメインごとに別々の転移学習をする必要がない (一度，全ドメインで共通の階層構造を学習すれば良い)
  • rectifier unitsを用いることで，疎な中間表現を得ることも可能

アルゴリズム

  • 全ドメインのデータをもちいて，教師なしSDA．階層構造を学習
  • ラベル付データの中間表現を用いて，分類器を学習および予測

分散型オンライン学習

研究 機械学習

ICML2011のOptimal Distributed Online Predictionをざっくりと読んだので，メモ書き．
論文

概要

  • 既存のオンライン学習アルゴリズムをミニバッチに拡張，分散学習を可能にする
    • 勾配ベースのオンライン学習手法は全て拡張可能
    • 勾配ベースのオンライン学習手法 : Dual-Averaging, Mirror descent algorithms (Subgradient method)等
    • Regret Boundは\sqrt{m} (m:データ数)で分散数kに依存せず，凸制約の上では理論上最適解
  • 確率的最適化の文脈から，分散型のアルゴリズムを提案しているとも見ることが可能
  • 実験により，ノードの数の増加に応じて収束速度が向上することが示された

distributed mini-batch framework(DMB)とは？

  • k個の学習器にそれぞれ別のデータを食わせて勾配を計算させる
  • 勾配情報がある程度溜まったら，勾配の平均を取り新しい学習器を生成する
DMBを用いる利点
  • シングルプロセッサでは到底処理不可能な量のストリームデータを扱うことが可能
  • 確率的勾配法ベースのDMBならば，並列性にほぼ線形での速度向上が可能

Regret Bound

E[R(m)] = \sqrt{m}(m:データ数)
証明は，ロングペーパーの方を参照

制約
  • "ある程度"の数bは，データ数mに依存する(但し，bはmより十分に小さければ問題ない)
  • 学習結果のやり取りや勾配平均の計算には遅延が発生するが，データ数mの増大にはスケールしなければ問題ない

その他

  • Master-Worker構成の分散システムにおけるDMBについて議論
    • k個の分散システム全てに同じ処理を指せることは不可能
    • Masterで勾配情報の収集・勾配平均の計算・放送を行い，一方でWorkerはそれぞれ勾配を計算する
    • Masterが死んだ時の処理についてもアレコレ (Fault Torelance)
  • Robust Decentralized Architecture(ADMB)
    • さらにRobustなMaster-Worker構成のDMBアルゴリズムを提案
    • 各ノードは，勾配情報を近隣のノードにのみ送る
    • 各ノードは，自身の勾配情報と近隣ノードの購買情報がある程度集まったら，自身の重みベクトルを更新
    • Regret Boundは係数が2倍に

劣勾配法(ヒンジ損失）書いたよ

言語処理 機械学習

ソースコード

ソースコード

内容

  • こちらでも劣勾配法について簡単に説明したいと思います．
  • 多クラス分類問題を解く場合，ヒンジ損失関数は以下の式で定義することが出来ます．
    • \ell_t(\mathbf{w}_t) = [1 - \mathbf{w}_t \cdot \Phi(\mathbf{x}_t, y_t) + \max_{\hat{y} \neq y_t} \mathbf{w}_t \cdot \Phi(\mathbf{x}_t, \hat{y})]_+
    • ここで，\mathbf{w}_tが現在の重みベクトル，\mathbf{x}_tが入力ベクトル，y_tが正解ラベルです．
    • ヒンジ損失関数では，正解ラベルのスコアと不正解ラベルのうち一番高いスコアとの差が重要な役割を果たします．
  • このように定義したヒンジ損失関数\ell_t(\mathbf{w})を用いて，劣勾配法はデータが1つ与えられるたびに以下の更新式に従い重みベクトルを更新します．
    • \mathbf{w}_{t+1} = \mathbf{w}_t - \eta_t \frac{\partial \ell_t(\mathbf{w}_t)}{\partial \mathbf{w}_t}
  • ここで，\eta_tは，毎回の更新時にどの程度重みベクトルを動かすかを調節するステップ幅です．
    • 多くの場合，ステップ幅は\frac{c}{\sqrt{t}}となる値を用います．[Zinkevich, 2003]
  • 以上が劣勾配法（ヒンジ損失関数）のアルゴリズムです．
  • 今回はヒンジ損失関数を用いていますが，凸な関数であれば任意の関数を用いることが出来ます．
    • さらに，Regretという概念を用いることで，最適解への収束性を示すことが可能です．[Zinkevich, 2003]

実験結果

既存手法との比較は以下になります．

NaiveBayes
accuracy : 9800 / 10000
Perceptron(1 iteration)
accuracy : 9725 / 10000
PA-II(1 iteration, C=0.001)
accuracy : 9789 / 10000
Subgradient Method(1 iteration, eta=1.0)
accuracy : 9802 / 10000

劣勾配法の精度が一番高いですね．
データセットによって，どの手法が一番精度が高いか，というのは変わってくると思います．
速度は，PerceptronやPA-IIと遜色ありません．

Passive-Aggressive書いたよ

言語処理 機械学習

ソース

ソースコード

内容

Passive-Aggressiveの概要・説明については，先日のオンライン学習による線形識別器のスライドをご覧ください．
http://d.hatena.ne.jp/kisa12012/20110625/1309003409

実験結果

NaiveBayes, Perceptronとの比較は以下．

NaiveBayes
accuracy : 9800 / 10000
Perceptron(1 iteration)
accuracy : 9725 / 10000
Passive-Aggressive(1 iteration)
accuracy : 9738 / 10000
PA-I (1 iteration, C=0.001)
accuracy : 9787 / 10000
PA-II(1 iteration, C=0.001)
accuracy : 9789 / 10000

PA-I, PA-IIの方が，PAよりも汎化性能が高い事が分かりますね．

Perceptron書いたよ

言語処理 機械学習

ソース

ソースコード

内容

Perceptronの概要・説明については，先日のオンライン学習による線形識別器のスライドをご覧ください．
http://d.hatena.ne.jp/kisa12012/20110625/1309003409

実験結果

NaiveBayesと比較すると，以下のようになりました．

NaiveBayes
accuracy : 9800 / 10000
Perceptron(1 iteration)
accuracy : 9725 / 10000

という結果になりました．（データセットは，データセット生成コードで自動生成生成したもの）
学習速度はパーセプトロンの方が圧倒的に早いので，これも一長一短ですね．
（用いるデータセットによって違うでしょうが…）