What's in a Hashtag? Content based Prediction of the Spread of Ideas in Microblogging Communities(WSDM2012)

アブストラクト
近年のソーシャルメディアを対象にした研究は、情報の時間的なトレンドや情報拡散を容易にするグラフ構造に焦点が当てられている。
本論文では、情報拡散上での意見の中身が与える効果について分析する。我々は、タイムフレームが与えられたうえでの、意見の広がりを予測するための、線形回帰モデルをベースとした効率的な混合手法を提示する。そして、時間や構造の特徴を組み合わせた特徴が、予測誤差を最小化することを示す。

データ

TwitterのHashtagと、4億のTweetデータ、followネットワークを利用。

手法
線形回帰を利用した予測モデル
トレーニングデータとして $(X,Y)=\{x_i,y_i\}$ を用意する
ここで、 $x_i$ は $ht_i$ が与えられた時の特徴ベクトル、 $y_i=log(n_i)$ とする。 $n$ は正規化されたハッシュタグの総出現数。

シンプルで頑健な線形関数は
$b+w^TX = b+\sum^{}_{j}w_{j}^{T}X^j$
で表されるが、より大規模な問題に対して適用するため、確率的勾配法を利用する。また、モデルパラメータ $b,w$ をL1正規化用いて学習する。

$L_r(b,w)=\frac{1}{2}\sum^{}_{i}(y_i-(b+\sum^{}_{j}w_{j}^{T}x_{i}^{j}))^2+\frac{1}{2}\lambda||w||$

ここで、 $i$ はi個目のトレーニングデータ、 $j$ は $x_i$ のj個目の属性を表す。
確率的勾配法（SGD）最急降下法はN個の全データを利用して勾配を求めるが、SGDではi個目のデータを利用して勾配計算を行い、それを $1,\dots,N$ に対して行う。データの参照が少なくなり、大規模データに利用可能。

パラメータのアップデート式は以下のようになる

$\Delta{b}=\eta_t(y_i-(b+w^Tx_i))$
$\Delta{w_i}=\eta_t(y_i-(b+w^Tx_i)x_i-\lambda{w_i})$

ハイパーパラメータ $\eta,\lambda$ はNelder-Mead法を利用して最適解を得る。（要勉強）

モデルのFeature Vectorに様々なものを利用

・Hashtag
HashtagのCharacter length
ワード数
共起
など…
・全体のTweet
cognitive dimension（よくわからない）
・グラフ構造
Follow数関連
Retweet率
・全体の時間的な特徴
時間を一定間隔で区切った上で、その期間内でのHashtag数

※cognitive dimensionというのがいまいちわからない…

提案手法であるHybrid modelはこれらを組み合わせたもの。
さらに、どの組み合わせが最も予測に役立つのか調査。
比較手法は、ベースラインとして、切片だけを最適化する回帰、上記の中の一つだけをFeature vectorにするものを用意。

実験は10-fold交差検定で行い、平均二乗誤差の値と相関係数で評価。

分析結果
提案手法はそのほかの比較モデルよりも誤差が小さい。
誤差の低下に大きく寄与する特徴として、グラフ構造と全体の時間的な特徴があげられる。

属性を考慮した情報拡散の予測モデルはまさしく自分がやろうとしていることであるので、若干先を越された感がある。特に自分の場合、グラフ構造の特徴を最重要に考えていたので、ほかの属性を組み込んでいる今回のモデルは素直に面白いなぁと思った。

どんどん先を越されそうなので、もっと焦った方がよさそう。そしてモデルの部分とか最適化の部分の勉強が圧倒的に足りないので、時間を見つけてやらんと…

ものすごくしっかり読めていない感が出ているので、時間があるときに読み直します。