takuti.me ABOUT

2017-07-16

Leakage in Data Mining

データマイニングの現場で頻発する Leakage という問題について本気出して考えてみた、的な論文を読んだ:

概要

  • Leakage とは、モデルを作るときに、本来知らないはずの情報(変数やデータ)を不当に使ってしまうこと
    • 手元のデータではメッチャ高い精度が出たのに、本番環境ではまったく精度が出ない、といった事態になる
  • その問題について定式化を試みると同時に、Leakage を検知・回避する方法を考える
  • こういう議論がまじめにされてこなかったせいで、KDD Cup 2008 のようなプロが企画・主催したコンペでさえ、問題の不備による Leakage が発生している

おもしろ事例集

はじめに、データマイニングコンペでの Leakage 事例が幾つか紹介されている。

KDD Cup 2007: Netflix Rating Prediction

Netflix 上での映画の評価値データを対象として、2つのタスクがあった:

  1. Who Rated What: 2005年までのデータが与えられて、2006年に各ユーザが未評価の映画を評価するかどうか、を予測する
  2. How Many Ratings: 同様に2005年までのデータがある状態で、2006年に各映画に集まるレビューの数を予測する

データの混在を防ぐために、タスク1と2ではそれぞれ異なるタイトルの映画のデータが用意された。

しかし、タスク2で優勝したチームのモデルは、なんとタスク1のテストデータをタスク2の教師データとして使っていた。

user, movie, rating
A, X, 3 
B, X, 1
C, X, 5

というタスク1のテストデータ(=2006年のレビュー履歴)があったとき、「2006年に movie X に集まるレビューは3件」と読み替えることができて、これはタスク2の学習に流用できるね、という話。

KDD Cup 2008: マンモグラフィデータからの乳ガン検出

普通は無視するはずの『患者ID』を特徴に使った結果、それがなぜかメッチャ予測に寄与した、という話。

これは、患者IDが「病院での検査か研究機関での検査か」、または「どの機器で行われた検査か」といった検査環境に関する情報と暗に紐付いていたことが原因らしい。

通常、患者の状態に応じて適切な検査施設や機器が決定される。IDがこれに紐付くということは、検査環境を決定する時点での事前知識がIDに反映されているということであり、目的変数と何らかの相関が見られても不思議ではない。

INFORMS Data Mining Contest 2008: 過去の診察履歴に基づく肺炎診断

元データでは、ある特徴量が目的変数と直結していて Leakage の恐れがあった。なので主催者はその特徴量をデータから削除した上でコンペを開催した。

しかし、参加者は与えられたデータの欠損からこの”削除された値”を推測することができた。

結果として、主催者が防ごうとした Leakage は防げていなかったね、という話。

INFORMS Data Mining Contest 2010: 株価変動予測

株価の増減を予測する二値分類問題。

なんと、30もの参加チームが AUC 0.9 以上を叩き出した。一番高いチームにいたっては AUC 0.99。

株価という public なデータを扱うため、コンペのデータ元となっている銘柄は非公開にするなど、参加者が“答えを探す”ことのできない工夫はされていたが、これが不十分だった。

どれだけ必死に隠しても Yahoo!/Google Finance などを見ればある程度察しがついてしまい、参加者は予測精度を不当に高めることができた。

IJCNN 2011 Social Network Challenge: ソーシャルグラフのリンク存在予測

“ある” SNS から得られたユーザ間の関係を表すグラフ(匿名、エッジは700万本以上)がある。さて、残りの約9000本の未接続エッジのうち、接続されるべき(実際には接続されている)エッジはどれか。

なんと、このコンペの勝者はデータを頑張って調べて、データ元の SNS が Flickr だということを突き止めた。さらに、各ノードに紐付くユーザをある程度特定することに成功した。その結果、未接続エッジのうち6割以上については、“正解”を得ることができた。

与えられた問題とは異なる問題を解いちゃいました、という心温まるお話。

Formulation

さて、Leakage があったコンペはそもそも何がダメだったのだろう?それを統一的に議論するために、Leakage の定式化を試みる。

まず、ある学習データのモデリングを考える。

このとき、モデルを『正当 (legitimate) なモデル』と『不当 (illegitimate) なモデル』に大別する。不当なモデルとは、特徴量が多すぎて高次元・複雑であったり、そもそも線形分離不能であったり、学習の結果得られる様々な“望ましくない”モデルを指す。

Leakage を含むモデルは、そんな不当なモデルの一種である。

もう少ししっかり『(Leakage という視点で)モデルが正当な状態』を表現するために、ある変数 $u$ を推定する際に事前に観測可能な変数の集合を $ legit\{u\}$ と書く。そして、たとえばある変数 $v$ が $u$ を推定するときに使えるのであれば『$v$ は $u$-legitimateである』と言って、$v \in legit\{u\}$ と書く。

すなわち、ある目的変数 $y$ についてモデルを作ったとき、

でなければならない。先の Flickr のリンク予測の例では正解データを手に入れてしまったがゆえに、『$y$ の予測に $y$ が使える』状態にあり、これは $y \notin legit\{y\}$ という要件に反する。

別の視点で見れば、目的変数 $y$ 以外のすべての変数 $x \in \mathcal{X}$ について Leakage が存在しないのならば、

でなければならない。

論文ではこのような表現を土台として議論を進めている1。そして、具体的には『特徴量のLeakage』 と『学習データのLeakage』の2種類が定式化できるという。

特徴量のLeakage

あらゆる特徴について "no-time-machine requirement" が存在する。これに尽きる。僕らはモデリングの際、目的変数が観測されるよりも前に得られる特徴のみを使わなければならない。

変数 $x$ の観測時刻が $t_x$、目的変数 $y$ の値を予測する時刻が $t_y$ であったならば、

で、これは『すべての $y$-legitimate な特徴は、時間的に $y$ よりも前に観測されるものに限る』ということ。

たとえば、$y = \textrm{2017年7月16日は雨か}$ とおいた予測問題に対して、$x = \textrm{2017年7月16日は雨だったか}$ という特徴を使ってしまったら、タイムマシン的天気予報ということになってしまう。

また、INFORMS 2008 の肺炎予測の例では、ある欠損コードの存在と他の特徴の組み合わせによって目的変数が予測可能だったが、これもタイムマシン的診断と言える。診断する時点では知らなかったはずの値(=事前に削除したはずの値)を使ってモデルを立てているのだから。

学習データの Leakage

一方で、KDD Cup 2007 (Netflix) で発生したタイプの Leakage は、タイムマシン的現象は発生していない。すべて過去(2005年)のデータを使って、未来(2006年)の映画の評価を予想している。このようなケースを議論するために、学習データの Leakage を考える。

KDD Cup 2007 の主催者側の落ち度は、全く同じ時期(2005-2006年)のユーザ履歴から『誰がどの映画にレビューを投稿したか』と『どの映画が何件レビューを獲得したか』という非常に似た問題を作ってしまったことにある。

そのような特徴選択以前の問題を避けるべく本論文が提示する要求は、テストデータ $y \in Y_{\textrm{test}}$ について、

を満たすというもの。

すなわち、与えられたデータについて、

  • 学習データの入力(特徴ベクトル)は、テストデータの出力(目的変数)よりも前に観測可能
  • 学習データの出力は、テストデータの出力よりも前に観測可能

と言えなければならない。

これは『特徴量の Leakage』でみた変数の正当性に留まらず、データ全体の正当性を要求する。ということは、KDD Cup 2007 のように複数の問題があるならば、それらが混在する場合も考慮して正当性を判断すべき、ということを暗示している2

データが相互に独立ならば問題ない。しかし全く同じサービスから収集した、全く同じ年のデータを複数の問題が使っていたとなると、それは問題、というわけだ。

Avoidance

ではいかにして Leakage を防ぐのか。

著者たちはまず、データに正当性をチェックするための『タグ』となる情報を付与すべきだと言っている。そして、データセットを学習用と評価用に分割するときは、以下の点に注意する:

  1. ある目的変数について、タグから明らかに正当だと判断できる特徴のみを使う
  2. すべての評価用データに対して、タグから明らかに正当だと判断できるサンプルのみを学習に用いる

タグの最も一般的な例は『タイムスタンプ』だ。タイムスタンプを付与しておくことで、「この時刻のとき、この特徴(変数)は観測可能だったか?」「学習データは評価データよりも前に観測されたデータか?」ということが確認できる。

結果として、特徴量と学習データに対する2種類の Leakage の予防につながるというわけだ。

一方 KDD Cup 2007 のようなデータマイニングコンペの現場では、仮にタグ的には完璧に正当だったとしても、データの混在や意図せぬ外部データの使用によって引き起こされる Leakage もある。

こういったケースは、「コンペの主催者がんばりましょう」という話になる。

コンペ主催者には「参加者に不正はしてほしくない」という建前がある一方で、「いかなる形であれ、提供したデータに対する新たな知見が欲しい」という本音もある。もどかしい。

まぁそれも踏まえて、近年よく見る『オフラインでの提出締め切りの後に、オンラインでの評価を行う』という形式がこの手の不正・Leakage 対策には有効だろう、と著者らは言っている。

Detection

データ収集が僕ら(主催者)のあずかり知らぬところで行われる場合は、何が正当なのか判断できず、タグが付けられない。こんなときは、Leakage の発生を能動的に『検知』するしかない。

そして最も有効な手段のひとつが、探索的にデータを解析してみること、いわゆる Exploratory data analysis だ。そして、探索的にいろいろ見ていると、“不思議な”結果に直面することがある。それはもしかしたら Leakage かもしれない。

INFORMS 2008 の例では、患者IDという明らかに無意味な特徴が目的変数と強い相関を示した。これは見逃せない。

また、異常に高い精度が出てしまったときも Leakage の可能性がある。素直に喜んではいけない。

さらに、あまり現実的ではないが、『モデルをその都度本番環境で評価してみる』というのも手だろう。手元のデータで出た精度と、デプロイ後に未知のデータから得られる精度に大きな差があれば怪しい。

まとめ

以上が論文中で議論されている Leakage の Formulation, Avoidance, Detection の概要。

最後に著者らは「Leakage を完全に消すのは難しい」という話をしている。そもそも仮に Leakage が存在しても、その予測モデルは『一応動く』もので、ランダムに予測するよりはずっとマシ。どうやって扱えば良いのだろう。

そして、仮にひとつ明らかな Leakage の要因を潰したとして、「このモデルは Leakage-free だ」と断言していいのだろうか?

理論的な定式化と合わせてこのあたりを議論するのは、大切かもしれないけど難しいよね〜と思った。

全体として良い話ではあったけど、タイトルの割には当たり前のことばかり言っているなぁという印象もある。『タグ』の例はタイムスタンプ以外の例が思い浮かばない…。Leakage の事例集としては非常に面白かったので、一読の価値アリ。以下の Podcast エピソードも合わせてどうぞ:

1. しかしフォントの異なる x と y が入り乱れていて異様に読みづらい。そのため、この記事では一部の表現・解釈を意図的に簡略化している。
2. …と思う。正直、このあたりの説明はいまいちピンときていない。