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を回さないといけないから大変.

2012-06-20

An Infinite Latent Attribute Model for Network Data[Palla+, ICML'12]のざっくりメモ

http://icml.cc/2012/papers/785.pdf

ネットワークデータのようなオブジェクト間の関係データをモデル化して,潜在的な構造を発見しようとする研究.お酒飲んで適当なことを書いているかもしれないけれど,悪しからず.

時間切れのため以上.

2012-06-16

Information Diffusion and External Influence in Networks[Myers+, KDD'12]のメモ

http://cs.stanford.edu/people/jure/pubs/ext-kdd12.pdf

再びJure Leskovecのチームの論文を読んだ.情報拡散(Information Diffusion)の過程が今までの研究とは少し違う感じ.

やりたいことは,情報拡散(Information Diffusion)による影響を"ネットワーク内の影響"と"ネットワーク外からの影響"に分けられるようにモデル化すること.従来の研究はネットワーク内で閉じた情報拡散の影響分析を行っているけれど,現実は,例えばTwitterユーザーはネットの記事をTwitterとは関係ない場所で見て,その記事が面白いと思ったらTwitterで情報を流すとかそういうことをしている.もし,このような現象をネットワークに閉じた世界で見ようとすると,あたかも情報が"ジャンプして"伝わっていくようなことになる.ようするに,ネットワーク内だけで情報拡散を考えるのは不十分だよねということ.

この論文では,人は2種類の影響を受けるとする.一つ目は今まで通りのネットワークを介した影響.これはhazard functionと呼ばれる確率で定義される.二つ目は外部からの影響.これはEvent Profileという確率で定義される.ここで,影響は"伝わる"とは別の意味を表している.よくある情報拡散の話では,隣接ノードから影響を受ければ,それは感染(infected)とかアクティブというけれど,ここでは影響を受けたとしてもすぐには感染しない.むしろ言葉は悪いけれど,被曝量(amount of exposures)的な意味が強い.最初,内部や外部から情報に晒され続け,蓄積された被爆量が多くなると感染する確率が高くなるという考え方.この2種類の確率を定義した後,二項分布を使って被爆量に関する確率分布 P^{(i)}_{¥exp}(n;t)を定義する.

次に,被爆量xに対する感染確率 ¥eta(x)を定義する.これは2つのパラメータで制御され,一つは感染確率の最大値,一つはその最大値のときの被爆量を意味する.

最終的に,あるノードiがある時刻tまでに感染する確率が定義出来る.これは, P^{(i)}_{¥exp}(x;t) ¥eta(x)の積をn=0から¥inftyまで総和する形で表される.

このモデルのもとで,現実のデータから外部からの影響Event Profileと ¥eta(x)の2種類のパラメータを推定する.ちなみに,内部からの影響であるhazard functionは事前に決定し,推定しない.


実験では,人工データと実データを使っている.実データの概要は以下の通り.

  • 2011年1月の完全なTwitterデータ
    • 30億ツイートから50回以上ツイートされたURLの付いたツイートに着目
    • English only
    • 結果的に,18,186個のURLを抽出.
  • ネットワーク構成
    • 18,186個のURLが付いたツイートをしたユーザのフォローリストを取得して,そこからネットワークを作成
    • ノード: 約110万.リンク: 約1億

実験結果の概要は以下の通り.

  • 人工データでは,真のパラメータを再推定出来ることを示した
  • 2011_Tucson_shootingの事件の時のツイートに関するケーススタディ
    • この事件に関するTwitterネットワークにおけるバースト(流行)時期を検出
    • 提案モデルで,この事件に関する4つのキーとなる出来事の時期をちゃんと当てることが出来ている
  • Googleトレンドを使った評価
    • Googleトレンドにクエリを投げて,これの時刻ごとのアクティビティを真の値としたときに,提案モデルのEvent Profileと単純な方法のEvent Proflie(方法は不明)がどちらが近いか比較
    • 提案モデルの方が30%くらい真の値に近い(L2ディスタンスで比較)
  • ニュースカテゴリごとの外部影響
    • カテゴリが異なるニュース記事ごと推定したパラメータを比較して考察
    • エンターテイメントと経済と健康のニュースは良く拡散する,一方で,芸術と教育と旅行はあんまり拡散しない.
    • 世界ニュースは時間に敏感.ようするに,他のトピックと比べて早く拡散確率が最大になる.
    • 政治ニュースは最も外部からの影響が強いトピック.
    • エンターテイメントは最も内部からの影響が強いトピック.
      • フォロワー数Top30のうち,22人はエンターテイナーだからという理由付けができるらしい
    • 総合して,全体の29%が外部からの影響,残り71%が内部からの影響によって,ユーザはURLをつぶやいているらしい

この研究,モデルが新しいのは確かなのだけど,外部からの影響があることを検証するためには,使用するデータが完全でないとできない.データに欠損があれば,情報がジャンプするという主張は,ただの欠損に過ぎないと言われる.この研究ではTwitter完全なデータを使っていると言ってる(実際どうなのかは分からないけど).本当に完全なデータを持っているならすごい強みだなと思う.羨まし〜.

2012-06-05

Latent Multi-group Membership Graph Model[Kim, ICML'12]のざっくりメモ

Jure Leskovecのところの論文.似たような論文がJureのところから出ていた気がするし,論文に載ってる図もどこかで見たことがあるけど,きっとそれとは違うのだろう.

内容はネットワークの生成モデルの話.ただし,リンクとノードの属性ベクトルの両方を扱うことが出来るモデル.リンクが分かればノード属性が推定できるし,ノード属性が分かればリンクが推定できるというのがこのモデルのうれしいところ.

モデルの良さを示すために,3つの実験をしてる.

  • ミッシングノード属性予測
  • ミッシングリンク予測
  • 教師ありノード分類
    • ノード属性ベクトルの一つをラベル,それ以外の属性とリンクが事例として学習.

それぞれのタスクで,ベースライン(Relational Topic Modelとか)と比べて性能が同等かそれ以上であることを示してる.

ネットワークの生成モデルとかリンクとノード属性の両方を捉えるモデルは既にあるので,それらと何が違うのかをDiscussionで述べている.

  • これまでのリンクとノード属性の両方を捉えるモデルは,隠れたグループ構造は考えられてなくて,だから次元削減によるベネフィットとかネットワークコミュニティの理解に役立つクラスタが生成できなかった.
  • 従来のモデルは,ノードはドキュメントを想定していたから,ノード属性は多項分布からの生成を仮定していた.提案法はロジスティックモデルを仮定してる.

モデルの詳細や推論方法はまた今度読む.

2011-05-28

ICML2011の読むかもしれないリスト

正確に言うと、ICML2011の読んでみたいけど読めるかなリスト。読み会で読むためのリストアップではなく、個人的に。

  • Dynamic Egocentric Models for Citation Networks (pdf)
    • Duy Vu, Arthur Asuncion, David Hunter, Padhraic Smyth
    • ネットワークの形成と時間による進化の分析は、いろんな分野で基本的な重要項目である。長期間のネットワークデータセットがあるのに、多くの研究ではある時期のデータしか使っていない。この論文では、多変量計量プロセスを使って連続時間のネットワークデータをモデル化する動的エゴセントリックフレームワークを導入する。推論においては、我々の方法が大規模なネットワークデータに対してもスケールするように、効率的な部分尤度アプローチが使われる。我々はこのテクニックを様々な引用ネットワークに適用し、予測の力と学習した統計的モデルの説明可能性について示す。
  • Large Scale Text Classification using Semi-supervised Multinomial Naive Bayes (pdf)
    • Jiang Su, Jelber Sayyad Shirab, Stan Matwin
    • 数多くの半教師学習法はラベルづけされてない文書を使ってMultinominal Naive Bayes (MNB)を増やすことを提案してきた(??)。しかし、実装の難しさや一貫性のない予測性能、または高い計算コストためにそれらの使用には制限がある。 この論文では、Semi-supervised Frequency Estimate(SFE)と呼ばれる新しくてとてもシンプルな半教師のMNBの拡張を提案する。我々の実験では、提案法がAUCと精度の観点から追加データ(ラベルあり or ラベルなし)でMNBが改善することを示す。我々はこれの要因をEM+MNBやラベル付きの学習データによるMNBよりも、SFEがよりよい条件付き対数尤度を常に生成することにあると思っている。
  • Preserving Personalized Pagerank in Subgraphs (pdf)
    • Andrea Vattani, Deepayan Chakrabarti, Maxim Gurevich
    • 巨大な現実のネットワークを簡易に表現する部分グラフを選ぶことは、多くの場面で役に立つ。よくある戦略は元のグラフの次数分布やクラスター係数などにマッチするサブグラフを誘導するノードをサンプリングすることである。しかし、クラスタリング、分類、ランキングのアプリケーションに重要なノード間の関係をきめ細かく保存するような試みはない。この研究では、Personalized PageRank Value (PPV)の考えに沿って上記の関係をモデリングする。我々は、今あるサンプリング法によって誘導された部分グラフの出力はPPVを保存していないことを示し、あらゆる与えられたノードの部分グラフ上でPPV保存部分グラフを作るためのアルゴリズムを提案する。3つの現実の強大なネットワークによる実験では、提案法によって作った部分グラフが、PPVの保持やクラスター精度、基本的なグラフの性質の保持の観点から誘導された部分グラフを改良することを示す。
  • Sparse Additive Generative Models of Text (pdf)
    • Jacob Eisenstein, Amr Ahmed, Eric Xing
    • テキストの生成モデルでは全てのクラスやトピックで多項分布を想定している。シンプルなモデルの場合でさえ、数千ものパラメータ推定を要求される。この論文では、テキストのついての代替の生成モデルを提案する。中心となるアイデアは、全てのトピックとクラスは定数の背景分布から対数の頻度における偏差のモデルによって与えられる。このアプローチでは2つの優位な点がある。1つは、過学習をさせずにスパースを実行出来る。もう1つは、隠れスイッチ変数が必要に鳴るのを避けて、対数空間で簡単な足し算で生成ファセットを組み合わせることが出来る。我々は、分類、トピックモデリング、より複雑な多面的な生成モデルのシナリオの範囲に対して、このアイデアの適用性を示す。
  • Predicting Legislative Roll Calls from Text (pdf)
    • Sean Gerrish, David Blei


なんか、こうやって読みたい論文探してると自分のやりたいことがだんだん分かってくるような気がするので、これからいろんな会議の読みたいリストを作るといいのかも。でも、当然ですけどネットワーク科学の研究室で2年やってきているのでどうしてもそっち系の論文に目が行く。勉強2ヶ月目のNLPはまだまだアウェイです。また今度、WWW2011も見てみます。