Human Wayfinding in Information Networks - todo314 @ ウィキ

Human Wayfinding in Information Networks

• Robert West, Jure Leskovec
  • Stanford univ.
• In WWW 2012

概要

• クリックの列に関する大量のデータを解析
• 人間をどうナビゲートするか？

Wikispedia Game

• スタートとゴールが与えられるので、wikipediaだけ辿ってゴールを目指す
• リストとかの汎用的なページは確か見れない

人間の探索能力

• ヒストグラムを見てみる
• shortest paths
  • small-world
• human, effective
• human, incl. back-clicks
• human, drop-out-corrected]
• モードは変わらん
• 中央値は下に行くほど大きい（3,4,5,6）
• 平均は、2.9,4.9,5.8,8.9
  • effectiveはそんなに悪く無い、意外
• 分散がでかい、らしい
• 疑問
  1. なぜ分散がでかい？
  2. なぜ平均では（割りと）効率的？

なぜ分散がでかい？

• 問題の差
  • 最適解の長さは同じだけど違う問題について調べてみた
  • やはり違う
• 人の能力の差
  • あるクリック数でdrop-outする人の割合を見てみた
  • 1~20クリックそれぞれについて、10%程度の確率でやめていた
    • 意外と均等

人間の探索方法

• 色々調査した
  • 最初のほう: 次数が大事
  • 最後のほう: 類似性が大事
• 次数と類似性だけに注目してロジスティック回帰分析
  • 長さ3~8について調べたけど、正しそう

ターゲット予測

• パスのprefixがもらえる
• ターゲットとして可能性が高いものを列挙
• 学習アルゴリズムを作るよ！
• Human Markov model
• $$ P(q | t;\Theta) $$
  • qはprefix、tはターゲット、Θは学習パラメタ
• いろんなモデルで確率を設定
  • Binomial logistic、Multinomial logistic
• 特徴もなんか色々
  • 8種類

実験結果

• 長さ4くらいで80%を超えた

まとめ

• 面白いけど、これの応用が微妙によくわからん
  • wikipediaだと思っているからかな？
  • ターゲットがわからん場合にもしかしてこれ？みたいな感じかな（アキネーター

WWW navigation

2013-10-18 21:04:16 (Fri)