ホーム  >   ブログ  >   機械学習   >   Area Under the ROC Curve (AUC) を並列で計算するときに気をつけること

2017-03-10

Area Under the ROC Curve (AUC) を並列で計算するときに気をつけること

このエントリーをはてなブックマークに追加

追記 (2017/03/10)

現在の内容は過度な簡略化と不完全な説明を含むので、それを踏まえて読んでいただけると幸いです。(後日更新予定)


ひとつ前の記事で二値分類器の性能評価に用いられる Area Under the ROC Curve (AUC) の実装について書いた: Area Under the ROC Curve (AUC) を実装する

簡単にまとめると、

  • AUCは『予測器がラベル 1 (True) のテストサンプルに正しく高スコアを与えるか』をみる。
  • それは予測スコアでサンプルをソートしたときに True Positive が False Positive より上位にランキングされるか、ということ。
  • 実装する際はソート済みサンプル列を逐次的に見ていって、False Positive-True Positive グラフの下の面積を求める。

という話だった。

auc7

AUC in Hivemall

そして先日、Hive/Spark/Pig用の並列機械学習ライブラリHivemallにAUCを計算する関数を実装した。

実装にあたりAUCをMap-Reduceの枠組みの中で並列に計算する必要があった。

たとえば2並列の場合を考えると、プロセス1と2でソート済みサンプルを分担することになる。

プロセス 予測スコア 真のラベル
1 0.8 1
1 0.7 1
1 0.5 0
2 0.3 1
2 0.2 0

しかし先述の通りAUCの実装はソート済みサンプルを逐次的に見ていく(つまり1つ前の結果に依存する)ので、気をつけて実装しないと誤った結果になってしまう。

マージするときに長方形を底上げする

図で考えよう。先の例で各プロセスがTrue Positive, False Positiveカウントを独立して計算すると次のようになる。

auc-partials

この2つの結果をマージしたいとき、単に両者の面積を足して 2+1=3 とはなりませんよ、というのが問題。正しいマージ後の面積は冒頭の図にある通り 5 になる。

より具体的に、プロセス1の結果(マージ元)をプロセス2の結果(マージ先)にマージする場合を考える。このとき、補足情報としてマージ元のTrue Positiveのカウントをマージ先に教えてあげる。これがポイント。

すると、マージ先ではマージ元の長方形の分だけ面積を底上げをすることができて、正しい面積が得られる。

auc-merge

▲ こんな感じ。あとは『マージ元の面積』と『マージ先の底上げした面積』の和を求めて正規化すれば、それが正しいAUCとなる。

ちなみに実際のHivemallのマージ部分の実装はここにある。マージ元とマージ先が逆の場合にも対応できるように他の補足情報も渡しているけど、基本的な考え方は上記のものと変わらない。

まとめ

計算の前後に依存関係がある処理の並列化は往々にして困難だけど、AUC計算は長方形の面積の足し合わせという単純な処理なので少し補足情報を渡してあげるだけで並列実装も可能。

ただし、マージ元とマージ先が隣接していないとダメな点に注意。たとえば以下のように3並列で計算した場合、プロセス1と3の結果を先にマージする、ということはできない。

プロセス 予測スコア 真のラベル
1 0.8 1
1 0.7 1
2 0.5 0
2 0.3 1
3 0.2 0

すなわち、

  • 1と2の結果をマージ → それと3の結果をマージ
  • 2と3の結果をマージ → それと1の結果をマージ

このいずれかの順序でマージされる必要がある。むずかしい。

  書いた人: たくち

たくちです。トレジャーデータでデータサイエンス・機械学習のプロダクト化および顧客への導入支援・コンサルティング、そして関連分野のエバンジェリズムを担っています。趣味は旅行、マラソン、登山。コーヒーとお酒とハンバーガーが好き。長野県出身、東京都在住。ブログへのご意見・ご感想、お仕事のご依頼など、@takuti または [email protected] までいつでもお気軽にご連絡ください。

※当サイト上での発言は個人の見解です

  過去の人気記事

2017-12-16
データサイエンスプロジェクトのディレクトリ構成どうするか問題
2017-06-10
Amazonの推薦システムの20年
2017-03-31
修士課程で機械学習が専門ではない指導教員の下で機械学習を学ぶために

  サポートする

  コーヒーを贈る

  ほしい物リスト

このエントリーをはてなブックマークに追加

  あわせて読みたい

2017-11-04
Over-/Under-samplingをして学習した2クラス分類器の予測確率を調整する式
2017-03-04
Area Under the ROC Curve (AUC) を実装する
2016-10-04
Treasure Dataインターンにみる機械学習のリアル #td_intern
  もっと見る