IJCNN Social Network Challengeの勝者が取った手法(deanonymize)は許されるか？
本当はリンク予測の話として書きたかったが，優勝チームの手法及びそれに対する反応が面白かったのでメモ．
三行まとめ
背景
最近見つけたのだが，Kaggle: Your Home for Data Scienceというサイトでは常時賞金が出るデータコンペティションが行われている．
企業や研究者がデータを提供し，分析者がそれを分析する．企業は最終的には賞金を出し，データに対する知見を得る，みたいなアウトソーシングであると公式サイトでは説明がされている．
Companies, governments and researchers present datasets and problems - the world's best data scientists then compete to produce the best solutions. At the end of a competition, the competition host pays prize money in exchange for the intellectual property behind the winning model.
http://www.kaggle.com/About-Us/aboutus
問題となったコンペティション
今回問題となったコンペティションはhttp://www.kaggle.com/socialNetworkである．
問題設定
- 1133547ノード，7237983エッジのグラフについて，どのノードがどのノードと結びついているかの情報のみが与えられる(social_train.zip)
- ノードはid変換され，anonymizeされている．
- 8960エッジも与えられる(social_test.csv)．このうち半分は存在し半分は存在しない
- social_test.csvのどのエッジが存在しどのエッジが存在しないかを予測しその精度を競う
問題設定は非常にシンプルである．
ここには書かれていないが，can you provide more info? | Kaggleにおいてデータの出処がFlickrである事が示されている．
各チームがほぼ共通で用いた手法
各チームが行った手法は素性を作って判別器にかけるというもの．リンク予測(link prediction)の手法は計算時間がかかりすぎて使えなかったとも書かれている．
どのチームもThe link prediction problem for social networksを参考にして素性を作っていったようである．
How I did it: Will Cukierski on finishing second in the IJCNN Social Network Challenge | No Free Hunch
How I did it: Benjamin Hamner’s take on finishing second | No Free Hunch
How I did it: finishing second from Bo Yang’s perspective | No Free Hunch
Sharing Techniques Used | Kaggle
ここらへんに上がってる素性をざっとまとめてみる．ノードにおける隣接ノード集合を
とすると
- k-NN
- これも色々と工夫がしてある．
- Jaccard
- Cosine
- Common neighbors
- Adamic/Adar
- Katz
- Preferential Attachment
- Simrank
- Degree of x/y.
- Maximum flow in the local graph
- Betweenness Centrality in the local graph
- whether reverse edge is present
- Neighborhood clustering coefficient
- Bayesian Sets(この特徴はかなり効くらしい)
- Localized random walk 2 – 4 steps(これもかなり効くらしい)
- Global Link Distance
- SVD
などがある．気になるのは二位のチームが使っていたBen's Edgerankである(Ben’s Edgerank feature by itself would have finished in the top 5 of the competition! とまで言われいてる)がよくよく読んでみるとrooted PageRankであったようだ．
判別器としてはlogistic regression，random forest，SVM，NNなどが挙げられている．
deanonymize
ここまではほぼ共通だとして，次に優勝チームが用いた手法について考える．
How we did it: the winners of the IJCNN Social Network Challenge | No Free Hunch
To clarify: our goal was to map the nodes in the training dataset to the real identities in the social network that was used to create the data.
How we did it: the winners of the IJCNN Social Network Challenge | No Free Hunch
データの出処がFlickrである事を知ったこのチームはFlickrをクロールし，匿名化されたテストデータを実データと結びつける事を試みる．
手法としてははまずFlickrの100万ユーザをクロールする．そして最初に完全に一致していると考えられるノード集合であるseedを作る．その後，seedからマッピングを伝播させることによってdeanonymizeしていくというものである．実際の手法はもっと複雑らしく，次の論文や，彼らが今後発表する論文を参照するのが良いと思われる．
De-anonymizing Social Networks | 33 Bits of Entropy
最終的にこの手法によって彼らは与えられたノードの80%（その大半は大きな入/出次数を持つもの）をdeanonymizeすることに成功したようである．
（※追記）実際にはdeanonymizeだけで予測を行ったわけではなく，機械学習による予測と組み合わせて用いたようである．何故なら予測すべきエッジを持つノードは次数が小さく，また，次数が小さいノードはdeanonymizeの精度が悪かったため，と書かれている．
フォーラムでの反応
Contesting the Result of This Contest | Kaggle
以下箇条書き
- 明文化されてないけどさすがにこれは駄目でしょ
- 「暗黙のルール」なんてどこにあるの？問題ないでしょ
- そもそも今回は優勝チームが正直に言ったからdeanonymizeが行われたことが分かったけど，「テストデータ以外のデータを使って予測をしていない」なんて事がどうやったらわかるの？
- 俺も同じ事思いついたけど難しそうだし主催者に否定されると思ってやらなかったわ
参考リンク
似たような話が鹿島先生の日記に上がっていたのを思い出した．
２位以下は割とダンゴ気味なので、ワトソンチームには、何か策があったはずと考えられます。 西郷さんからの報告によると、なんと彼らは、普通、予測には関係ないはずの患者IDを使ったらしいのです。 かれらは正例と負例に振られているIDの分布が（人為的不手際により）異なっているはずだ、という仮定をおき、それを予測に用いたようです。
機械学習についての日々の研究
実際、ID以外については、たいていの参加者がおおむね同じような方法（事例のバランス調整＋線形分類器＋ヒューリスティックな後処理）を用いていたようです。
ある種、タスクの穴を見つけて利用した、という感じなので、人によってはズルイと言うひともいそうですが、これは彼らでなくても実現できることであるし、むしろ、勝てばよかろうなのだで、そこに目をつけた彼らは（本当に）高く評価されてよいと思います。 すげえ。
[cs/0610105] How To Break Anonymity of the Netflix Prize Dataset
Netflix Prizeという推薦システムの精度向上を目的としたコンペティションデータにおいて，配布データにおける匿名idと実際のデータとの結びつきを示した論文．
第73回全国大会イベント企画 プライバシー保護データマイニング
最近激アツのプライバシー保護データマイニング
