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

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

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

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

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

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

（上図は論文より引用）

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

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

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

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

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

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

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

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

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

この論文は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）では、以下のような数理計画問題を定義し、貪欲法を用いて解を計算していました。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

広告

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

採用ページ