追記 (2017/03/10)
現在の内容は過度な簡略化と不完全な説明を含むので、それを踏まえて読んでいただけると幸いです。（後日更新予定）
https://twitter.com/myui/status/840089982991708160
ひとつ前の記事で二値分類器の性能評価に用いられる Area Under the ROC Curve (AUC) の実装について書いた: Area Under the ROC Curve (AUC) を実装する
簡単にまとめると、
- AUCは『予測器がラベル
1(True) のテストサンプルに正しく高スコアを与えるか』をみる。 - それは予測スコアでサンプルをソートしたときに True Positive が False Positive より上位にランキングされるか、ということ。
- 実装する際はソート済みサンプル列を逐次的に見ていって、False Positive-True Positive グラフの下の面積を求める。
という話だった。
AUC in Hivemall
そして先日、Hive/Spark/Pig用の並列機械学習ライブラリHivemallにAUCを計算する関数を実装した。
https://twitter.com/ApacheHivemall/status/836526293927657472
実装にあたり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カウントを独立して計算すると次のようになる。
この2つの結果をマージしたいとき、単に両者の面積を足して 2+1=3 とはなりませんよ、というのが問題。正しいマージ後の面積は冒頭の図にある通り 5 になる。
より具体的に、プロセス1の結果（マージ元）をプロセス2の結果（マージ先）にマージする場合を考える。このとき、補足情報としてマージ元のTrue Positiveのカウントをマージ先に教えてあげる。これがポイント。
すると、マージ先ではマージ元の長方形の分だけ面積を底上げをすることができて、正しい面積が得られる。
▲ こんな感じ。あとは『マージ元の面積』と『マージ先の底上げした面積』の和を求めて正規化すれば、それが正しい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の結果をマージ
このいずれかの順序でマージされる必要がある。むずかしい。
シェアする
カテゴリ
あわせて読みたい
- 2017-11-04
- Over-/Under-samplingをして学習した2クラス分類器の予測確率を調整する式
- 2017-03-04
- Area Under the ROC Curve (AUC) を実装する
- 2016-10-04
- Treasure Dataインターンにみる機械学習のリアル #td_intern
最終更新日: 2022-01-18
書いた人: たくち
たくちです。長野県出身、カナダ・バンクーバー在住のソフトウェアエンジニア。これまでB2B/B2Cの各領域で、Web技術・データサイエンス・機械学習のプロダクト化および顧客への導入支援・コンサルティング、そして関連分野のエバンジェリズムに携わってきました。現在はフリーランスとして活動を続けつつ、アフリカ・マラウイにて1年間の国際ボランティアに従事中。詳しい経歴はレジュメ を参照ください。いろいろなまちを走って、時に自然と戯れながら、その時間その場所の「日常」を生きています。ご意見・ご感想およびお仕事のご相談は [email protected] まで。
寄付で活動を支援する 一杯のコーヒーを贈る免責事項
- Amazonのアソシエイトとして、当サイトは amazon.co.jp 上の適格販売により収入を得ています。
- 当サイトおよび関連するメディア上での発言はすべて私個人の見解であり、所属する（あるいは過去に所属した）組織のいかなる見解を代表するものでもありません。
- 当サイトのコンテンツ・情報につきまして、可能な限り正確な情報を掲載するよう努めておりますが、個人ブログという性質上、誤情報や客観性を欠いた意見が入り込んでいることもございます。いかなる場合でも、当サイトおよびリンク先に掲載された内容によって生じた損害等の一切の責任を負いかねますのでご了承ください。
- その他、記事の内容や掲載画像などに問題がございましたら、直接メールでご連絡ください。確認の後、対応させていただきます。