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

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

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

  • 先行研究
    • Infinite Relational Model(IRM)
    • Mixed Membership Stochastic Block Model(MMSB)
    • Latent Feature Infinite Relational Model(LFRM)
      • 各オブジェクトは複数のクラスタに属すると仮定して,feature vectorで所属を表現.
      • 今回はこれが直接的なライバル
  • モチベーション
    • LFRMはオブジェクトをフラットクラスタリングで説明する
      • クラスタは階層的な方がもっと良い
        • スポーツは,バスケットボールやテニスに細分化出来るように
      • サブクラスタを考慮するモデル化へ
  • 提案モデル: Infinite Latent Attribute model(ILA)
    • 各オブジェクトは可変長Mの特徴(二値)ベクトルzを持つ
    • 一つ一つの特徴mは可変K(m)個のサブクラスタを持ち, c_i^{(m)}でノードiが特徴mでどのサブクラスタに所属するかを表す.
    • Wはある特徴mにおいてサブクラスタ間でのリンクの付きやすさの重みを表す行列
    • ノードiとjの間でリンクが付く確率は,それぞれのノードが持つzと重みの線形和のロジスティックシグモイド.
    • #言葉で説明するのは難しい.
  • 学習はMCMC
  • 計算量の比較
    • 尤度の計算に関して
      • LFRM: O(M^2 N^2)
      • ILA: O(M N^2)

時間切れのため以上.

TrueLabel + Confusions: A Spectrum of Probabilistic Models in Analyzing Multiple Ratings[Liu+, ICML'12]のメモ

http://icml.cc/2012/papers/123.pdf
クラウドソーシング+機械学習の論文.1979年のDawid&Skeneの研究をspectrum of probabilistic modelsに一般化している(spectrumのイメージが出来てない...).一般化と言われてもいまいちピンと来ないけど,Dawid&Skeneと同じことを出来るよりシンプルなモデルと,ベイジアンにしたモデルの2つを提案しているのが実際のところ.鹿島先生のチュートリアル*1によれば,このDawidらの研究はこの話題における先駆的な研究なのだそう.

  • モチベーション
    • MSではサーチエンジンの訓練に人間の評価(rating)を使っている(そうなのか?)
      • クラウドソーシングに頼むのはリスキーなので,今はちゃんと専門の人を雇っている
      • タグ付けの量もすごいし,訓練された人を雇うんだから,コストも高い
    • 評価の質をコントロールするための一つの方法は,超簡単なタスクを混ぜておくこと
      • 全てのワーカーはこのタスクに取り組むようにしておく
      • そうすると,ワーカーをちゃんと評価できるし,ワーカーを惑わすタスクは何なのか,評価のガイドラインはこのままで大丈夫なのかとかそういうことに繋がる
    • Dawid&Skeneは良いモデルだけど,パラメータが多すぎる
      • 評価(ラベル)数K,ワーカー数Jに対して,K(K-1)*J個の自由パラメータが必要
        • 各ワーカーがK×KのConfusion行列を持ってるため
        • 過学習しちゃう
  • 提案法: 2つのモデル
    • 従来法: DawidSkene
      • 真の評価に対して,各ワーカーの評価は各ワーカーのConfusion行列から生成される
    • SingleConfusion: 全ワーカーで共通のConfusion行列を持つモデル
      • シンプルすぎてUnderfitting(日本語訳なんだっけ)しちゃう
      • でも,全てのワーカーにおいてどのタスクが難しいのか興味あるからこれでも良いらしい
    • HybridConfusion: Dawid&Skeneのベイズ拡張モデル
      • 各ワーカーが独自のConfusion行列を持つこともできるし,シュリンクして少ない行列で表せもする
  • 学習はEM
    • 観測はワーカーによるタスクへの評価(rating)
    • 未知は真のラベル
    • パラメータはConfusion行列,真のラベルの分布
  • 実験
    • 人工データを使った評価(ラベル数K=3)
      • 真のラベルをどれだけ推定できるか
        • HybridConfusionが最も良い性能.
        • DawidSkeneとSingleConfusionは,多数決による方法に負ける
      • パラメータ推定の結果
        • 基本的にHybridConfusionが優勢
    • Real-Worldデータを使った結果
      • (query, URL)というタスクに対して,ワーカーが「Bad,Fair,Good,Excellent,Perfect」のいずれかの評価をしたデータ.
        • 難しいタスクで構成されているらしい
        • 48タスクに対して148ワーカーから6008個の評価を得た
        • 2:1の割合で訓練セットとテストセットに分けた
      • テストデータのみに基づいて真の評価を予測
        • HybridConfusionが最もよい(精度: 約6割)けど,多数決による方法とほぼ同じ
      • 訓練セットでパラメータを学習した後,真の評価を予測
        • HybridConfusionが最も良い(精度: 約6割)
  • 思ったこと
    • 精度的にあまり良いとは思えないんだけど,「目的は真のラベルに対する優れた予測モデルを作ることじゃない」とか書いてあるので,多分この論文の本当の良さは捉えきれてない
    • モデルの表記で「Matlab表記で書くと」みたいなことが書いてあるけど,著者はMSの人なので,Excel表記で書けばいいのにって思いましたまる

GaP: A Factor Model for Discrete Data[Canny, SIGIR'04]のメモ

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.8075&rep=rep1&type=pdf
NMF(Non-negative Matrix Factorization)をGamma-Poissonでやる話.Gamma-Poissonの頭文字を取ってGaPと呼んでいる.他の文献*1によれば,GaPはDCA(Discrete Component Analysis)の一般化なのだとか.DCA知らんので,ピンときてない.

  • 基本はF=ΛXとなるΛとXを求めること
    • GaPでは,FはPoisson(ΛX)から生成されてる
  • テキストの生成モデルをGamma-Poissonモデルで表現
    • ドキュメントの単語頻度スコアXはGammaから生成
    • 単語頻度FをPoissonから生成
  • 学習はEM
    • 観測はテキスト内の単語頻度F
    • 未知はドキュメントの単語頻度スコアX(確率ではない)
    • パラメータはGammaのパラメータと,トピックの単語頻度確率Λ
  • 実験

本当は,Gamma-Poissonモデルについて詳しく書きたかったのだけど...

Collaborative Topic Regression with Social Matrix Factorization for Recommendation Systems[Purushotham+, ICML'12]のメモ

http://icml.cc/2012/papers/407.pdf
Collaborative Topic Regression*1 + Social Matrix Factorization*2で,新たな協調フィルタリングの方法を提案する論文.モチベーションは以下の通り.

  • 多くの強調フィルタリングモデルは,アイテムの情報を使えていない
    • レーティングデータの不足や偏りが問題になる(特に新しいユーザに対する)
    • Collaborative Topic Regressionはアイテム情報をモデルに入れて,上記問題を改善してる
  • ソーシャルネットワークベースの協調フィルタリングもあるが,アイテム情報とソーシャルネットワークの両方を使った研究はほぼ無い

モデルは階層ベイズで表現.Collaborative Topic Regressionは以下のようなモデル.

  • アイテムの情報はLDA*3と同じように生成される
  • ユーザiのアイテムjに対するレーティングは Normal(u_i^T v_j, c_{ij}^{-1})で決定
    • u_iはユーザiのK次元潜在ベクトルで,トピックに対するユーザの好みを表す
    • v_jはアイテムjのK次元潜在ベクトル,アイテムのトピック選好度を表す
    • アイテムのトピックとユーザの好みが合致すれば( u_i,v_j内積が大きければ),高評価になる.

このモデルに対して,Social Matrix Factorizationの考えを導入する.すなわち,ユーザiとkの関係がg(u_i^T s_k)を平均とするガウシアンから生成されるとする.ここでg(・)はシグモイド関数s_kはユーザkのソーシャルファクター特徴ベクトル.

学習はCollaborative Topic Regression同様に,EMライクな方法.

実験では,約99%欠損したユーザ-アイテムのレーティング行列(二値行列)を使う.評価には独自に定義したrecall@Mを使う.ここで,recall@M=(トップM個のユーザが好きなアイテムの数)/(ユーザの好きなアイテムのトータル数)で計算できる*4.結果の概要は以下の通り.

  • 提案モデルはCollaborative Topic Regressionより3%ほどRecallが良い
  • LDAベースなので計算コストは高い.トピック数K=50のとき14分くらい,K=200のとき10時間くらい学習に時間がかかる.
    • ユーザ数: 1867, アイテム数: 69226, タグ(rating済み): 53388, ユーザ間リンク数: 15328の場合.

論文によれば,主な貢献は以下の3点.

  • 推薦システムの性能向上にソーシャルネットワークが使えることを示した
  • ソーシャルネットワークと情報の内容が両方使える場合,予測精度を向上させる有効なトレードオフテクニックを提供
    • メモでは触れなかったけど,ハイパーパラメータの調整によってそういうことが出来るらしい
  • 推薦システムにおける新しい問題(ソーシャルな情報のリーク)の提起
    • ネットワークは時間ごと変化するので,それを考慮するとどうなるかという問題提起

*1:Wang and Blei, "Collaborative topic modeling for recommending scientific articles," KDD'11

*2:Ma et. al., "Sorec: social recommendation using probabilistic matrix factorization," CIKM'08

*3:Blei et. al., "Latent Dirichlet Allocation," JMLR'03

*4:この評価式は正直良く分からない

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完全なデータを使っていると言ってる(実際どうなのかは分からないけど).本当に完全なデータを持っているならすごい強みだなと思う.羨まし〜.

人工知能学会全国大会とCICPの内定通知

3泊4日という比較的長期間,山口で行われた人工知能学会全国大会(JSAI2012)に参加してきました.人工知能学会は初参加でしたけど,印象は「お金掛かってる!」ってこと.ホテルから会場までの無料バスが出てるし,懇親会では山口の料理とか日本酒とかいっぱい出ていたし,イベントもいっぱいあった.懇親会で会長が「一昨年も去年もすごかったから今年の会議へのプレッシャーが凄かった」と言っていたように,昨年は岩手で小岩井農場を貸し切ってイベントをやったそうで,それはそれですごいけれど,今年は今年で国宝の瑠璃光寺五重塔の目の前で懇親会をやるというとても贅沢な経験をしたので,今年のイベントもすごいなという感想を持ちました.
会場の近くが湯田温泉街で,ホテルにもちゃんと温泉が付いているところでした.あんまりゆっくり入っていられる時間は無かったですけど,ビジネスホテルに泊まって行く出張とはちょっと違って,リフレッシュもできました.

会議の方は,並列セッションでなかなか自分が聞きたい発表全てを聞くことはできませんでしたが,一番聞きたい発表はすべて聞けたと思います.人工知能という広い分野なので自分の興味に合うものは少数だけど,中にはこういう研究もあるのかと思うようなものもあって,なかなか面白かったです.

自分自身の発表は時間通りにきっちり終ったのでそれは良かった.内容を聴衆の皆様に理解してもらっていたかは不明ですが.発表の仕方とか人によって色々だろうし,どういうのが理解しやすいかもまた人によって違うと思うので,どういうのがいいかは正直良く分からないですねー.

来年は富山で開催のようです.富山県も行ったことないのでぜひ参加したいですねー.


そういえば,先週提出したCICPの内定通知を頂きました.プロジェクト名は「暮らしやすい社会の創造を目指した手話生成システムのオープンソース化」です.今年はメンバーとしてですけど,あまり責任のない立場からプロジェクトを楽しむということを今年は出来ればいいなと思っています.来年の3月まで,自分の研究と並行でこのプロジェクトを進めていきます.ちなみに,同研究室からもう一件,「コーパスが、君の論文の英語は変だって言っていたよ。」が内定しています.締切ギリギリまで共に頑張っていたので,両方とも通って本当によかったです.