Hatena::ブログ(Diary)

シコウサクゴ() このページをアンテナに追加 RSSフィード

2012-08-05

Exploiting Latent Information to Predict Diffusion of Novel Topics on Social Networks[Kuo+, ACL'12]のメモ

Exploiting Latent Information to Predict Diffusion of Novel Topics on Social Networks(PDF)

ACL'12のshort paper.LDA(→類似度計算)→識別をやっている.各要素技術は新しくないけれど,全体のフレームワークが新しいってことかな.

  • やりたいこと:
    • 新しい(未知の)トピックの拡散予測.
      • 具体的には,ソーシャルネットワークの各リンクで情報が伝わったか伝わらなかったかの2値を当てたい.
      • 前提: 新しいトピックに関して拡散の履歴は利用できない
    • 観測は過去と新しいトピック,トピックで出現する単語数,過去にどのトピックがどのリンクで伝わったか.
      • Twitterで言えば,過去に何のTweetがどのリンクを伝わっていったかが既知.新しい(拡散を予測したい)Tweetの内容も既知.
  • 方法:
    • 4種類の情報に関して,LDA使って潜在情報を抽出:
      • Topic Information: トピック-単語行列(TW)=あるトピックに含まれる単語の分布
        • TWを分解すると,TH(トピック-潜在行列)とHW(潜在-単語行列)の積になって,後ではTHを使う.
        • THに関して,新しいトピックと既知のトピックの間の類似度(TS)を計算.
          • そのリンクで過去に3回伝わっていれば,新しいトピックと過去3回のトピック間で類似度を計算し,合計する.
      • User Information: ユーザ単語行列(UW)=あるユーザが発信する単語の分布
        • UWを分解すると,UM(ユーザ-潜在行列)とMW(潜在-単語行列)の積になって,後ではUMを使う.
      • User-Topic Interaction:
        • 新しいトピックに関してこの情報は得られないので,あんまり使いものにならないんだけど,ごにょごにょやると利用出来るデータに成るらしい.
      • Global Features: ネットワークに関する素性
        • 入次数(ID)と出次数(OD).
        • そのリンクを伝わったdistinctなトピックの数(NDT)
  • 実験:
    • データ
      • Plurkというマイクロブログのデータ.
        • 100個のトピックを7グループに手で分ける.
      • ユーザxがあるトピックtのメッセージを発信した後,ユーザyがトピックtのメッセージを発信すれば伝わったものとして,(x,y,t)というインスタンスを得る.
      • ネットワーク構造もこんな感じで伝わった部分を抽出して作る
    • 実装:
      • 識別はLIBLINEAR(c=0.0001)
      • LDAはGibbsLDA++[Phan and Nguyen, 2007]
    • ベースライン:
      • Existing Diffusion: ノード間で全てのトピックにおいて伝わった回数に基づいて識別
      • Independent Cascade[Kempe et al., 2003]: ノード間で伝わった回数を正規化して拡散確率として計算
      • Heat Diffusion[Ma et al., 2008]
    • 結果:
      • 上であげた4種類の情報それぞれの結果では,類似度(TS)を使った方法が最も良い結果(AUC=69.93).
      • 情報の組み合わせによる結果では,全てを入れるよりも類似度(TS)+入次数(ID)+NDTが最も良い結果(AUC=73.95)
  • 思ったこと
    • 類似度(TS)は,過去に何回そのリンクで情報が伝わったかの情報が入っちゃってるので,過去に情報が伝わってるところは新しい情報でも情報が伝わりやすいってこと.
    • ベースラインのIndependent Cascadeが悪すぎる(AUC=51.53)けど,このモデルでどのリンクで伝わったかを当てるのはかなり難しいだろうし,識別ベースの方法にゃ勝てない.
    • 本当に新しい情報についてこれを調べたければ,オンラインで素性を更新する仕組みが必要だと思うけれど,この方法では新しい情報が入ってくるたびにLDAを回さないといけないから大変.
トラックバック - http://d.hatena.ne.jp/yosshi71jp/20120805/p1