AD-TECH
Lab BLOG
RCO アドテクLab ブログ

WSDM2017で体感したデータマイニング最前線【後編】

2017/03/07kenjih hosakak

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

こんにちは、最近カジノで投資金を5倍にした林田と自家製燻玉作りで家を煙たくしている保坂です。

 さて今回は、『WSDM2017で体感したデータマイニング最前線【後編】』と題してWSDM 2017で面白かった論文の紹介をしたいと思います。学会の全体的な雰囲気を知りたい方は、前回のエントリーをご一読いただければと思います。

WSDM cake

論文紹介Ⅰ: D-Cube: Dense-Block Detection in Terabyte-Scale Tensors

D-Cube presentation

 大規模なテンソル空間から密なブロックを検出するという研究です。
テンソル空間から密なブロックを検出するという技術は、以下のような領域で応用されます。

  • レビューサイトにおける「やらせ」評価検出
  • ネットワーク攻撃検出
  • ボット検出

 様々な属性を持つ事象をテンソルで表し、密な領域がある場合は例外的な何かが起こっていると判断します。テンソルのイメージが湧きにくいかもしれませんので、論文の例を引用します。例えば、Wikipediaの改訂履歴の場合はユーザ、ページ、日付を属性としたテンソルを考えることができます。

D-Cube tensor

(上図は論文より引用)

 既存手法には、CP分解やHOSVDなどのテンソル分解を使ったものや、検索ベースのものがありますが、それらはテンソルのサイズがメモリに収まることを仮定したモデルでした。この研究はメモリに収まらないほど大きなテンソルを扱うD-Cubeというモデルを提案しました。D-Cubeはディスクに格納されたテンソルを扱いますが、ディスクIOのデータ量とステップ数を最小化することで、検出の精度を落とすことなく計算の高速化を実現しています。

 これまでの手法と比較し、D-Cubeには以下の優位性があります。

aspect description
メモリ効率 最先端の手法と比較し、約1,600倍メモリ効率がよい
計算速度 最先端の手法と比較し、約5倍高速
正確性 正確性を確率的に保証でき、実用レベルでも最先端の手法と遜色ない
実用性 ネットワーク攻撃、「やらせ」評価を高い精度で検出


論文紹介Ⅱ : Unbiased Learning-to-Rank with Biased Feedback

検索クエリに対してどのドキュメントを上位に表示すると適切か、ドキュメントに対してランキング付けをするモデルの研究です。 このようなモデルを構築する際には、検索クエリとドキュメントのクリック履歴を教師データとして、 よくクリックされたドキュメントほど上位にランキングされるようにモデルを構築する事が考えられます。

しかしこのようなクリック履歴はそれまでのドキュメントの表示順序の影響を受けた偏った履歴になっています。 上位に表示されていたドキュメントは必然的にクリックが集中し、下位のドキュメントはユーザーの目に触れにくいためクリックが少なくなります。 しかし下位のドキュメントのクリックが少なかったとは言え、これは必ずしもドキュメントとクエリの関連度が低いことを意味するのではなく、単にユーザーの目に触れなかったことが影響を及ぼしているだけかもしれません。

why propensity score
発表スライド より引用


この論文では、このような教師データの偏りを、傾向スコアを用いて補正する方法を提案しています。 傾向スコアは、調査対象の無作為割付が不可能な観察研究を行う場合に、群間の偏りを調整するために用いられる方法です。

今回の研究では「ドキュメントが目に触れる確率」が傾向スコアとなります。 上位に表示されていたドキュメントは目に触れやすいためその分だけ割引いて考慮し、 下位のドキュメントは目に触れにくいためその分だけ割増して考慮するというイメージです。

この傾向スコアを用いて観測データを補正した上でランキング学習をするPropensity-Weighted SVM Rankという手法を提案しています。

この方法を用いてYahoo Learning to Rank Challengeのデータを用いた実験、Arxiv Full-Text Search 上での実際の検索環境に於ける実験を行い、いずれも重み付けをしないSVMと比べて高精度のランキングが得られたことを報告しています。

precision on yahoo dataset
Figure 1: Test set performance in terms of (2) for Propensity SVM-Rank with and without clipping compared to SVM-Rank naively ignoring the bias in clicks (η = 1, ε− = 0.1). The skyline is a Rank- ing SVM trained on all data without noise in the full-information setting, and the baseline is the pro- duction ranker S0. (論文より引用)
precision on arxiv
発表スライドより引用


この論文はWSDM2017のベストペーパーに選ばれており、また、アイデアとしてとても面白かったため紹介しました。


論文紹介Ⅲ: A Concise Integer Linear Programming Formulation for Implicit Search Result Diversification

 SRDに関する研究です。検索エンジンでユーザが欲している情報を的確に提供することは困難です。なぜならユーザが発行するクエリは、しばしばとても曖昧なものだからです。

 例えば、”Harry Potter”というクエリだけでは、知りたい情報が映画についてなのか、本についてなのか、キャラクターについてなのか分かりません。そのような場合にSRD(search result diversification)という技術が利用されます。SRDは、ユーザが欲しい情報を取得できる確率を最大化するように、多種多様な結果セットを返します。

 この研究ではSRDの中でも特に、implicit SRDという手法にフォーカスを当てています。implicit SRDは、クエリの裏側に隠されているユーザの情報ニーズ情報があらかじめわかってない状況下におけるSRDのことです。

 既存のimplicit SRDモデル(DFP)では、以下のような数理計画問題を定義し、貪欲法を用いて解を計算していました。

ILP4ID existing model

しかしながら、DFPにはモデルの最適値を計算できないという問題がありました。

 この研究はimplicit SRDを整数線形計画問題として定式化したILP4IDという新しいモデルを提案しました。 ILP4IDは従来の近似手法と異なり、目的関数の最適値を計算できるという利点があります。

ILP4ID proposed model

 さらに、ILP4IDは既存手法であるDFPを汎用的にしたモデルであることが示されています。 また、先行研究にてDFPはMMR、MPT、QPRPなど他のimplicit SRD手法と密接な関係があることが知られています。よってこれらの手法もILP4IDを使って表現することができます。

 RCOの開発でMMRを使ったことがあったので、テーマ自体には馴染みがありました。 昔から研究されているテーマに対して、比較的シンプルなモデリングを行いその有効性を示したという意味で非常に面白い論文だと思いました。


論文紹介Ⅳ: PRED: Periodic Region Detection for Mobility Modeling of Social Media Users

位置情報が付加されたソーシャルメディアへの投稿のデータを用いて、ユーザーが定期的に訪れる場所とそのタイミングを推定するモデルの研究です。

geo-annotated records of a person
Figure 2: The historical geo-annotated records of a person (論文より引用)


ソーシャルメディアのデータを用いた定期訪問の推定には難しい点があります。

  • 使える情報はGPSによる位置情報と時刻だけで、訪問先やその周期性の情報は一切ない
  • ユーザーはどこかへ行くたびに必ずソーシャルメディアへ投稿するわけではないため、データには多数の欠損がある
  • ユーザーによって周期訪問場所の数は異なっている

これまでには周期訪問がある場所の推定方法がいくつか提案されていましたが、投稿に訪れた場所の情報が付与されていることを前提としていたり、ユーザーによらず同じ数だけ周期訪問場所があると仮定している方法となっていました。

また、既存の周期性の検出方法は、高頻度でデータが収集できる場合を対象としていたり、長い期間に渡るデータを必要とする方法となっていました。

この論文では場所と周期性についてPREDと呼ばれるノンパラメトリックベイズモデルを定義し、周期訪問の位置とタイミングの同時推定を試みています (クラスタ数とかを自動推定してくれる方のノンパラメトリックです)。 PREDは以下のキーアイデアに基づいて構成されています。

「周期性のある訪問に関する投稿であれば、その投稿間隔は訪問間隔の倍数になっているはず」

例えば毎日朝8時頃にレストランで朝食を取る人がいて、それをソーシャルメディアに投稿していたとすると、投稿間隔は24時間程度となります。 たまに投稿しない日があったりするとその分投稿間隔は伸びますが、それは48時間、72時間のように24時間の倍数になるだろう、というわけです。

Table 1: Time Example (論文より引用)
time example


これをモデル化するために、著者らは訪問間隔ではなく、訪問間隔を周期で割った余り(reminder)に対する確率分布を考えています。

eq1
eq2

また、ユーザーによって周期訪問場所の数が異なっていて、その数を予め与える事ができないことを表現するためにDirichlet Processを用いています。

これらのアイデアを組み込んだPREDのグラフィカルモデルは以下のような形になっています。

graphical model of PRED
Figure 3: Graphical Model of PRED (論文より引用)


また人工的なデータや、Gowalla・Twitterの実データを用いた実験により、従来手法と比べて著しく高精度な結果が報告されています。

Error distance of PRED
Figure 4: Location Prediction Error Distance (論文より引用)


この手法は訪問間隔に関するキーアイデアや、位置・時間に関して1つの同時分布としてモデリングしている点が非常に面白かったため紹介させていただきました。 私自身、サービス利用の周期性に関する分析を行ったときにこのような欠損をどう取り扱うべきか悩んだ経験があったため、非常にためになりました。 業務でもこのアイデアやモデルを活かしていきたいと思いました。

広告

RCOアドテク部ではやらせを撲滅してハイクォリティレビューの恩恵に与りたいエンジニアも募集しています。

採用ページ