ラプラス正則化を用いた半教師付きページランク

半教師付きの設定で，ページランクみたいにグラフのノードに重み付けをつけるアルゴリズム，半教師付きページランク (Semi-Supervised PageRank)を考えてみました．

ページランクは，グラフのノードに重みをつけるアルゴリズムです． 一つやりたいことがあって，最初ページランクを使っていたのですが，教師的な情報を組み込むのが難しかったので，自分で考えることにしました． というのも，ページランクでは，すべてのグラフノードの重みを1に初期化します． 単純にここに教師的な情報を組み込む，例えば数個のノードの重みを高くするなど，をやってみたのですが，最終的に出てくる解にあまり反映されなかったのです． なぜなのか，をいろいろ考えましたが，ページランクはノードの重みを繰り返し伝搬するので，初期値が大事というより，エッジが大事なんだと今は思っています（もう少しちゃんと考える必要あり）．

定式化していきましょう． グラフ$G=(V, E), V=\{1, \ldots, n\}, E \subseteq V \times V$を考えます． 扱いやすいように，エッジは隣接行列 (Adjacency matrix) $\mathbf{A}$で表現することにします． $\mathbf{A}$をいろいろ変えることで，いろんなグラフが表現できますが，ここでは一般の行列にしときます． 重み付けにおける教師データとは何か？という話になると思うのですが，ここでは，高い（低い）重みがついて欲しいノードの集合$V^{*} \subseteq V$が与えられることにします．

さて，各ノードにおける重みを$\mathbf{f} = [f_1 \cdots f_n]$と表すことにして，これを求めることがゴールになります． とりあえず，$V^{*}$の要素に該当する重みを大きくしたいので，$\mathbf{u} = [u_1 \cdots u_n]$を以下で定義します．

$$\begin{align*} u_i = \left\{\begin{array}{cc} 1 & if \ i \in V^{*} \\ 0 & otherwise \end{array}\right. \end{align*}$$

こうすると，$V^{*}$のスコアの合計値を，$\mathbf{f}^T \mathbf{u}$と表すことができます． 今，$\mathbf{f}^T \mathbf{u}$を最大化すれば良さそうですが，今回はラプラス正則化 (Laplacian Regularization) と呼ばれるものを加えます． これは，ノード間にエッジが存在する場合，それらのスコアを近づける，というアイデアです． ノード$i$と$j$の間にエッジが存在する，すなわち$A_{ij}=1$なら$(f_i - f_j)^2$を最小化します． これは，$A_{ij}(f_i - f_j)^2$と書けますね．これをすべてのノードに対してやります． 以上を踏まえて，以下の問題を解きます．

$$\begin{align*} max_{\mathbf{f}} \ \mathbf{f}^T \mathbf{u} - \alpha \|\mathbf{f}\|^2 - \beta \sum_{i,j=1}^n A_{ij}(f_i - f_j)^2 \end{align*}$$

ただし，第2項にl-2正則化項を加えています． 第3項がラプラス正則化項です． これの解は以下のように解析的に得られます．

$$\begin{align*} \mathbf{f} = (\mathbf{L} + \gamma \mathbf{I}_n)^{-1} \mathbf{u} \end{align*}$$

ただし，$\mathbf{L} = \mathbf{D}-\mathbf{A}$，$D_{ii} = \sum_{j=1}^n A_{ij}$は対角行列，$\gamma=\frac{\alpha}{\beta}$であり，これは通常の正則化パラメータと同じように事前に決めてやるものとします． これで，望ましい結果というのを，$\mathbf{A}$だけでなく，$\mathbf{u}$でも表現できるようになりました． 次回は，これをウェブページ解析に応用したいと思います．