WWW2018 論文読み会 Web Search and Mining
- 1. Web Search and Mining 株式会社サイバーエージェント 秋葉原ラボ 角田 孝昭 1 WWW2018 論文読み会
- 2. イントロダクション 自己紹介: 角田 孝昭 ● 業務: – アメブロ等を対象としたスパムからの 防御、既侵蝕スパムの索敵?殲滅 – テキスト ? ハッシュタグ関連度算出 – そのほか、自然言語処理?データ分析周り色々 ● 経歴: – 筑波大学大学院 CS 専攻、博士（工学） 評判分析?時系列予測周りの研究をしていました – 現職 → 上記のような業務へ ● 鳥が好きです（※飼ってません） 2 噛まれている方が 登壇者
- 3. イントロダクション 本発表の進行次第 1. イントロダクション – どんなセッション？ – 分野概観 – 各論文の1行要約 2. ピックアップ概説 – Neural Attentional Rating Regression with Review-level Explanations – Detecting Crowdturfing “Add to Favorites” Activities in Online Shopping 3
- 4. イントロダクション どんなセッション？ 4 Web Search and Mining ● Search 分 (11件?) – Search と言うものの割と多分野 – 真っ当な「自然言語文書の検索」がメインテーマの論文は むしろ少数 ● Mining 分 (13件?) – なんでもあり！！ – なんでもありすぎるので詳細は次ページ以降参照
- 5. イントロダクション Search 分の分野概観 5 小分野 論文リスト 検索一般 ● Leveraging Fine-Grained Wikipedia Categories for Entity Search ● Subgraph-augmented Path Embedding for Semantic User Search on Heterogeneous Social Network ● Ad Hoc Table Retrieval using Semantic Similarity 対話検索? クエリ提案 ● Query Suggestion with Feedback Memory Network ● Conversational Query Understanding Using Sequence to Sequence Modeling Hashing ● Scalable Supervised Discrete Hashing for Large-Scale Search プライバシー ● Privacy and Efficiency Tradeoffs for Multiword Top K Search with Linear Additive Rank Scoring データ整備 ● StaQC: A Systematically Mined Question-Code Dataset from Stack Overflow ● Strategies for Geographical Scoping and Improving a Gazetteer 検索行動 分析 ● “Satisfaction with Failure” or “Unsatisfied Success”: Investigating the Relationship between Search Success and User Satisfaction ● Search Process as Transitions Between Neural States ※Search / Mining の分類や 小分野は発表者の主観による 分類です
- 6. イントロダクション Mining 分の分野概観 6 小分野 論文リスト 機械学習? アルゴリズム ● Parabel: Partitioned Label Trees for Extreme Classification with Application to Dynamic Search Advertising ● Learning from Multi-View Multi-Way Data via Structural Factorization Machines ● Online Compact Convexified Factorization Machine ● Learning on Partial-Order Hypergraphs ● Manifold Learning for Rank Aggregation レビュー 分析 ● A Sparse Topic Model for Extracting Aspect-Specific Summaries from Online Reviews ● Neural Attentional Rating Regression with Review-level Explanations 行動分析 ● Detecting Crowdturfing “Add to Favorites” Activities in Online Shopping ● Understanding and Predicting Delay in Reciprocal Relations その他 ● Finding Subcube Heavy Hitters in Analytics Data Streams ● Joint User- and Event- Driven Stable Social Event Organization ● TEM: Tree-enhanced Embedding Model for Explainable Recommendation ● Hierarchical Variational Memory Network for Dialogue Generation ※Search / Mining の分類や 小分野は発表者の主観による 分類です
- 7. イントロダクション ざっくり概要 – Search 分 (1/2) ● Leveraging Fine-Grained Wikipedia Categories for Entity Search ○ クエリのメイン語 headword とそれ以外 modifier に注目した category matching で精度 ↑ ● Subgraph-augmented Path Embedding for Semantic User Search on Heterogeneous Social Network ○ 色々なタイプの関係 (e.g. schoolmates 等) があるネットワーク (heterogeneous social network) における「特定ユーザ」と「関係」を入力としたユーザ検索を実現 ● Ad Hoc Table Retrieval using Semantic Similarity ○ クエリから表を検索。クエリと表を同じ embedding space に置いてマッチする ● Query Suggestion with Feedback Memory Network ○ 検索結果ページでのクリック履歴から、次にクエリされそうなフレーズを予測 w/ seq2seq (を 改変したモデル) ● Conversational Query Understanding Using Sequence to Sequence Modeling ○ 文脈を考慮できる stateful な対話検索が目的。context も利用した seq2seq で発話生成 ● Scalable Supervised Discrete Hashing for Large-Scale Search ○ 教師あり hashing。大規模データ対応?計算過程で discrete constraints に違反しないと言う 好特性 7
- 8. イントロダクション ざっくり概要 – Search 分 (2/2) ● StaQC: A Systematically Mined Question-Code Dataset from Stack Overflow ○ accepted answer の複数のコード片から「それ単体で解決できるコード」を systematic に判 定 ● Strategies for Geographical Scoping and Improving a Gazetteer ○ 複数の地理情報 DB (gazetteer) を統合。各 DB が異なるデータタイプ（点、範囲）だったり不 正確なデータでも、うまく統合できる確率的なモデルを提案 ● Privacy and Efficiency Tradeoffs for Multiword Top K Search with Linear Additive Rank Scoring ○ searchable encryption。従来研究でまだだった ranking (i.e. top-k search) を実現 ● “Satisfaction with Failure” or “Unsatisfied Success”: Investigating the Relationship between Search Success and User Satisfaction ○ 「ユーザが検索に満足してても、実際には誤った情報で満足している」など、ユーザ満足度と 検索の成功の間にあるギャップについて詳しく調査 ● Search Process as Transitions Between Neural States ○ 検索行動が4つの過程からなるとし、各過程で脳活動がどのように異なるか?共通しているか を fMRI で調査 8
- 9. イントロダクション ざっくり概要 – Mining 分 (1/2) ● Parabel: Partitioned Label Trees for Extreme Classification with Application to Dynamic Search Advertising ○ ラベル数が非常に多い分類問題（extreme classification）を同精度で 600-900 倍早く学習で きる手法を提案。似たようなラベルをまとめて (label trees) 1-vs-All 爆発しないように工夫 ● Learning from Multi-View Multi-Way Data via Structural Factorization Machines ○ 色々な種類の素性をそのまま使うとベクトル大き過ぎとか問題 → 潜在空間にうまく落とす手 法を提案 ● Online Compact Convexified Factorization Machine ○ FM を頑張ってオンライン凸最適化問題にしてオンライン化。分類?回帰とも精度向上 ● Learning on Partial-Order Hypergraphs ○ グラフベース学習手法を POH (hypergraph を拡張したデータ構造) に適用できるように ● A Sparse Topic Model for Extracting Aspect-Specific Summaries from Online Reviews ○ レビュー文書群から商品の評価視点がうまく取り出せるような topic model を提案 ● ☆ Neural Attentional Rating Regression with Review-level Explanations ○ レビュー点数を、レビュー有用度を考慮して推定。レビュー点数推定精度の向上に加え、有用 度予測では「有用とした人数」よりも高い精度を実現 9
- 10. イントロダクション ざっくり概要 – Mining 分 (2/2) ● ☆ Detecting Crowdturfing “Add to Favorites” Activities in Online Shopping ○ 「お気に入りに追加」しまくって順位を上げるタイプのスパムを分析?検出 ● Understanding and Predicting Delay in Reciprocal Relations ○ Tumblr で「フォロー返し」するまでの時間を分析 + 分析に基づいた予測手法を提案 ● Finding Subcube Heavy Hitters in Analytics Data Streams ○ 高次元?ストリーミングデータに対応可能な heavy hitters 抽出手法を提案 ● Manifold Learning for Rank Aggregation ○ 従来の rank aggregation では文書間の独立性が前提であったが、manifold で非独立性を考 慮 ● Joint User- and Event- Driven Stable Social Event Organization ○ ユーザ–イベント選好とユーザ間選好を考慮したヒューリスティックにより効率的に Social Event Organization 問題を解く ● TEM: Tree-enhanced Embedding Model for Explainable Recommendation ○ 理由が説明可能な推薦。GBDT で素性 (cross feature) 抽出 → embed ● Hierarchical Variational Memory Network for Dialogue Generation ○ 階層構造と variational memory network を seq2seq モデルに導入。長文での返答が可能 に 10
- 11. 2. ピックアップ概説 (1) Neural Attentional Rating Regression with Review-level Explanations 11
- 12. Neural Attentional Rating Regression with Review-level Explanations 目的: 高精度なレーティング予測 ● もしユーザ u が商品 i を買ったら何点を付ける？ – 予測できればリコメンドに活用できる ● 商品 i の特徴はレビュー文書で補間できるが 有用ではないレビューも存在する ● – 各レビューの有用度（usefulness）を考慮して活用 – 各レビュー（とユーザ）の有用度は学習データに不要 （レーティング予測モデルの学習時、同時に学習される） – レーティング予測に加え、有用度推定も高い精度 12 アイディア?貢献
- 13. Neural Attentional Rating Regression with Review-level Explanations 従来モデル: Latent Factor Model 13 以下の式でレーティング予測 バイアス項 （本質ではない） ユーザ u とアイテム i の ベクトル （似ているほど高い値に） 提案モデルでは… アイテムやユーザの情報を レビュー文書から有用性を 考慮して補間する
- 14. Neural Attentional Rating Regression with Review-level Explanations 提案モデル: NARRE 14 レビューテキストを CNN で素性ベクトル化 レビューベクトル & 書き手埋め込みベクトルから attention (≒ 有用度) を計算 attention を重みとして 素性ベクトルの和を計算 有用なレビュー（?書き手）を 選択して特徴ベクトルを補間できる！ ※Item Modeling の場合
- 15. Neural Attentional Rating Regression with Review-level Explanations 性能評価: レーティング予測 1. レビュー情報の利用により性能向上 2. Deep Learning の活用により概ね性能向上 3. 【提案手法】各レビューの有用度を活用することでさ らに性能向上！ 表3: レーティング予測精度: RMSE による評価（低いほど良い） (1) (2) (3) 15
- 16. Neural Attentional Rating Regression with Review-level Explanations 性能評価: 有用度予測 16 表5: 有用度予測性能（いずれも高いほど良い） ベースラインはそれぞれ時刻順?ランダム?レビュー長さ降順 提案手法の有用度予測で 出したレビューの方が有用 有用とした人数降順 （※正解データ）の方が有用 同じ ぐらい 図10: 人手評価の結果 各種ベースライン? 有用とした人数降順 よりも高精度！ （学習時に「有用とした人数」 等のデータは使っていないの がすごい）
- 17. 2. ピックアップ概説 (2) Detecting Crowdturfing “Add to Favorites” Activities in Online Shopping 17
- 18. Detecting Crowdturfing “Add to Favorites” Activities in Online Shopping 目的: 「リストに追加」スパムの検出 ● 欲しいものリストに追加（A2F = Add to Favorites）により ランキング上昇を狙うスパムが存在 – クラウドソーシングでスパマーを集めている – 正解データがない、煙に巻く行動までしている ● – クラウドソーシングの依頼を逆手に取って利用、 A2F スパマー（正解データ）を特定する手法を提案 – A2F スパマー?対象商品の特性を様々な観点から分析 – 因子グラフでモデル化して推定、推定性能向上 18 アイディア?貢献
- 20. Detecting Crowdturfing “Add to Favorites” Activities in Online Shopping データセットの用意 (§3) 20 クラウドソーシングサービス 296 spam queries 113 users ● A2F タスクを人手で抽出 ● タスク参加者をスパマーとして抽出 （スクリーンショットから ID は特定可能） 81,778 users 1,544,996 items 4,272,221 user behavior logs 1. スパマーが関わった全 item を抽出 2. 当該 item に関わった全 user を抽出 3. 当該全 user が関わった 全 user behavior logs, 全 item を抽出 (+) A2F タスクが 指定するクエリで 検索しているログは スパム確定と考える (-) A2F 数が ≧500のアイテムは 非スパム確定と考える (?) 残りは不明とする 半教師有り学習の 過程でラベル付け
- 21. Detecting Crowdturfing “Add to Favorites” Activities in Online Shopping データ分析: ユーザ行動分析 21 ● スパムは対象アイテムの前に 別アイテムを見やすい （タスクで指示されている） ● スパムは週末に多い クエリが特定の長さに集中 （指示されたクエリで検索） 検索ページが遠い （スパム商品は見つけにくい） 閲覧時間が長め （タスクで指示されている）
- 22. Detecting Crowdturfing “Add to Favorites” Activities in Online Shopping データ分析: ユーザ?アイテム分析 22 いずれの行動もスパマーの 方が少ない A2F から購入に至った割合で 見ても明らか 表4: ユーザ軸で見た場合 表5: アイテム軸で見た場合 スパム対象アイテムの方が 少ない（魅力に欠けるため） A2F からの割合で見ても同様
- 23. Detecting Crowdturfing “Add to Favorites” Activities in Online Shopping A2F スパム検出提案手法 23 ● 因子グラフ（factor graph）でモデル化 ● 既知?未知ラベルの双方が混在（partially labeled）していても学習可能 詳細は時間の都合で省略！
- 24. Detecting Crowdturfing “Add to Favorites” Activities in Online Shopping A2F スパム検出の性能評価 24 ● AFGM が提案モデル ● AFGM - UP, Cu, Cp は一部因子を削除した比較用