Learnability of Influence in Networks - todo314 @ ウィキ

Learnability of Influence in Networks

• Harikrishna Narasimhan, David C. Parkes, Yaron Singer
• NIPS 2015

概要だけ

• 様々な拡散モデルのPAC学習性
• 辺のパラメータそのものより、影響関数値の方が大事
• Linear threshold
  • 多層NN分類器っぽみ、VC次元
  • 部分観測×、完全観測○
• Independent cascade
  • Covering numberで考えられる
  • 完全観測○
• Voter
  • 線形回帰に帰着
  • 部分観測○、完全観測○
• 推定したいもの
  • 影響関数$$ F:2^V \to [0,1]^n $$: シード集合に対して、各頂点が活性化する確率
• $$ \mathrm{err}^\ell = \mathbf{E}_{X,Y}[\ell(Y, F(X))] $$
  • Yは影響された頂点集合、Xはシード集合、ℓは損失関数
  • 実際は、仮説集合が達成する最小のerrと、サンプルから学習したerrの差を考える
• サンプル: (シード, (各時刻で)活性化した頂点集合)の列

NIPS 学習可能性 影響最大化 情報拡散

2018/10/28