ホップの定理(Hopf’s theorem)-行列

ページランクなどの、本質的にマルコフ連鎖に関連するもの(要は、べき乗法)の収束するかしないかの判定法として、ペロン・フロベニウスの定理(Perron-Frobenius theorem)があります。

しかし、この定理が言及するのは、あくまで\(n \rightarrow \infty\)の極限のみであり、収束の速さについては述べません。

べき乗法の収束の速さについて、行列の固有値の絶対値の大きさが本質的に関わって来ることはそこらへんにいくらでも書いてありますし、ちょっと考えればわかることなのでここには書きませんが、以下に示すHopfの定理を用いれば正行列に対し、べき乗法の収束の速さの下限を求めることができます。(べき乗法と固有値にについては、Wikipediaにも書いてあります。)

直観的に言えば、マルコフ過程の遷移行列が疎になる(0成分が多くなる)ほど収束が早いか遅いか判定しづらくなると言うことを述べたのが、以下、ホップの定理(Hopf’s theorem)です。

(\(\kappa \rightarrow \infty\)を考えてみてください。つまり残念ながら、定理の適用可能な行列のクラスは、厳密に正な正方行列に限られます。)

 

ホップの定理(Hopf’s theorem)

正方行列\(M\)の全ての要素が正定値の時、\(M\)の最大固有値\(\lambda_0\)と他の任意の固有値\(\lambda\)は、

\[|\lambda|\leq\frac{\kappa-1}{\kappa+1}\lambda_0 \]

ここで、\(\kappa\)は

\[\displaystyle \kappa=\max_{i,j,k}\frac{M_{ik}}{M_{jk}}\]

 

結構重要な定理だと思うので、日本語でまとめました。ペロン・フロベニウスの定理の証明について知っている方は、以下の定理1,定理4の部分だけ見るだけでもいいと思います。

ちなみに、ホップはもともと、一般に正の積分作用素についてこの定理を証明したようですが、ここでは正行列に注目して考えます。

量子アニーリングの数学的基礎 森田 悟史 西森秀稔 (Mathemathical Foundation of Quantum Annealing)という論文を参考にしています。(日本人が書いた英語の論文を、日本人が見ると言う…)


\(M\)を、厳密に正な(すべての成分が正の)\(m \times m\)行列とする。これを\(M>0\)と書く。

同様に、\(M \geq 0\)は、全ての成分が非負であることを意味する。

ベクトルにも同じ記法を用い、\(\boldsymbol{v} >0\)は\(\boldsymbol{v}\)の全成分が正であることを意味する。

\(M\)の厳密な正定値性は、以下と同値。

\(M\boldsymbol{v}>0 \ \ \ \ if\ \ \ \ \boldsymbol{v} \geq 0,\boldsymbol{v} \neq \boldsymbol{0} \tag{1}\)

 

あらゆる実ベクトル\(\boldsymbol{v}\)と正ベクトル\(\boldsymbol{p}>0\)は、以下を満たす。

\[\displaystyle \min_{i} \frac{v_i}{p_i} \leq \min_i \frac{(M \boldsymbol{v})_i}{(M \boldsymbol{p})_i} \leq \max_i \frac{(M \boldsymbol{v})_i}{(M \boldsymbol{p})_i} \leq \max_i \frac{v_i}{p_i}\]

ならば、

\[(M \boldsymbol{v})_i-( \min _i \frac{v_i}{p_i})(M \boldsymbol{p})_i  =\sum _{j=1}^m M_{ij} [v_j -(\min _i \frac{v_i}{p_i})p_j] \geq 0\]

\(\max\)の方も同様。

 

以下の記号を用いる。

\[\displaystyle \underset{i} {osc} \frac{v_i}{p_i}=\max _i \frac{v_i}{p_i}-\min_i \frac{v_i}{p_i}\]

これは振幅(oscillation)と呼ばれる。

複素ベクトルに対しては、以下の様に定義する。

\[\displaystyle \underset{i}{osc}\ v_i=\sup_{|\eta|=1}\underset{i}{osc}\ Re(\eta v_i)\]

あらゆる複素数\(c\)に対し、

\[\underset{i}{osc}\ v_i=|c|\underset{i}{osc}\ v_i\]

であることがわかる。 

 もし\({osc}_i\ v_i=0\)であるならば、\(v_i\)は\(i\)に依らないことも簡単にわかる。

 

行列\(M\)に対し、以下の仮定を置く。

\[\forall i,j,k\ \ ,\exists \kappa ,\ \frac{M_{ik}}{M_{jk}}\leq  \kappa\]

以下の様に書き換えることもできる。

\[\forall i,j, \boldsymbol{v}\ (\boldsymbol{v}\geq 0,\ \boldsymbol{v} \neq 0),\ \ \frac{(M\boldsymbol{v})_i}{(M\boldsymbol{v})_j}\leq \kappa,\ \  \tag{2} \]


定理1.

もし\(M\)が 条件(1),(2)を満たすならば、あらゆる\(\boldsymbol{p}>0\)と複素ベクトル\(\boldsymbol{v}\)に対し、以下が成り立つ。

 

\[\underset{i}{osc}\  \frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i} \leq \frac{\kappa-1}{\kappa+1} \underset{i}{osc}\  \frac{v_i}{p_i} \tag{3}\]


証)まず、実ベクトル\(\boldsymbol{v}\)について考える。\(i,j,\boldsymbol{p}>0\)を固定し、実数\(X_k\)を以下に定義する。

\[\displaystyle \frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i}-\frac{(M\boldsymbol{v})_j}{(M\boldsymbol{p})_j}=\sum_{k=1}^{m} X_k(v_k)\]

\(X_k=X_k (i,j,\boldsymbol{p})\)の正確な表式は知る必要はない。

\(\boldsymbol{v}=a\boldsymbol{p}\)のとき、上式の左辺は消えるから、

\[\displaystyle \frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i}-\frac{(M\boldsymbol{v})_j}{(M\boldsymbol{p})_j}=\sum_{k=1}^{m} X_k(v_k-ap_k) \tag{4}\]

ここで

\[\displaystyle a=\min_i\frac{v_i}{p_i},b=\max_i \frac{v_i}{p_i}\]

のように選ぶと、

\(v_k-ap_k=(b-a)p_k-(bp_k-v_k)\)であるから、\(v_k-ap_k\)は\(v_k=ap_k\)で最小値\(0,v_k=bp_k\)で最大値\((b-a)p_k\)をとる。

それゆえ(4)式は、

\[\boldsymbol{v}=a\boldsymbol{p}^- +b\boldsymbol{p}^+=a\boldsymbol{p}+(b-a)\boldsymbol{p}^+\]

で最大値をとる。

(論文中(222)式の\(a\boldsymbol{p}^- -b\boldsymbol{p}^+\)は間違い)

ここで、

\[p_i^- =p_i(X_i\leq0),0(X_i>0)\]

\[p_i^+ =0(X_i \leq 0),p_i(X_i>0)\]

のように定義した。

結果、

\[\displaystyle \frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i}-\frac{(M\boldsymbol{v})_j}{(M\boldsymbol{p})_j} \leq \left[\displaystyle \frac{(M\boldsymbol{p}^+)_i}{(M\boldsymbol{p})_i}-\frac{(M\boldsymbol{p}^+)_j}{(M\boldsymbol{p})_j}\right](b-a) \tag{5}\]

が得られる。

仮定より\(M>0\)かつ\(\boldsymbol{p}>0\)であるから、

\[M\boldsymbol{p}^- \geq 0,\ \ M\boldsymbol{p}^+ \geq 0,\ \ M\boldsymbol{p}^- +M\boldsymbol{p}^+ >0\]

さらに、\(\boldsymbol{p}^- =0\)或いは\(\boldsymbol{p}^+ =0\)であるとき、\(\boldsymbol{p}^+=\boldsymbol{p}\)または\(0\)となるから、右辺の括弧内が消えてしまう。

よって、\(M\boldsymbol{p}^->0\)かつ\(M\boldsymbol{p}^+ >0\)であるとして議論を進めてよい。(5)式は、以下の様に書き直せる。

\[\displaystyle \frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i}-\frac{(M\boldsymbol{v})_j}{(M\boldsymbol{p})_j} \leq \frac{1}{1+t}-\frac{1}{1+t’},t\equiv \frac{(M\boldsymbol{p}^-)_i}{(M\boldsymbol{p}^+)_i},t’\equiv \frac{(M\boldsymbol{p}^+)_i}{(M\boldsymbol{p}^-)_i}\]

式(2)より、\(t\)と\(t’\)は\(\kappa^{-1}\)から\(\kappa\)で抑えられるから、\(t’ \leq \kappa^2 t\)であることがわかる。

(論文中,\(t’ \leq \kappa t^2\)は間違い)

\[\frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i}-\frac{(M\boldsymbol{v})_j}{(M\boldsymbol{p})_j} \leq \frac{1}{1+t}-\frac{1}{1+\kappa^2 t}\]

\(t>0\)において、上式の右辺は\(t=\kappa^{-1}\)において最大値\(\frac{\kappa-1}{\kappa+1}\)をとる。

最終的に、以下を得る。

\[\frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i}-\frac{(M\boldsymbol{v})_j}{(M\boldsymbol{p})_j} \leq \frac{\kappa-1}{\kappa+1} \underset{i}{osc}\ \frac{v_i}{p_i}\]

複素ベクトル\(\boldsymbol{v}\)に対しては、\(M\ Re (\eta \boldsymbol{v})=Re (\eta M \boldsymbol{v})\)が成り立つから、\(v_i\)を\(Re(\eta v_i)\)と置き換え、\(|\eta|=1\)の条件の下、両辺のsupをとることで以下を得る。

 \[\underset{i}{osc}\ Re\left(\eta\frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i}\right) \leq \frac{\kappa-1}{\kappa+1} \underset{i}{osc}\ Re\left(\eta\frac{v_i}{p_i}\right)\]


この定理を固有値問題に適用する。

\[M\boldsymbol{v}=\lambda \boldsymbol{v} \tag{6}\]

ペロン・フロベニウスの定理により、非負な正行列\(M\geq 0\)に対し、他のあらゆる固有値\(\lambda\)に関して、\(|\lambda|\leq \lambda_0\)となる。この結果は厳密に正な行列\(M>0\)にも使え、以下の定理を示す。


定理2

式(1),(2)の仮定の下、固有値問題(6)は正の解\(\lambda=\lambda_0>0\),\(\boldsymbol{v}=\boldsymbol{q}>0\)を持ち、さらにどんな\(\boldsymbol{p}(\boldsymbol{p}\geq 0,\boldsymbol{p}\neq 0)\)に対しても、

\[\boldsymbol{q}_n=\frac{M^n\boldsymbol{p}}{(M^n\boldsymbol{p})_k}\]

は\(k\)が固定された下、\(\exists \boldsymbol{q}\)に収束する。


証)

非負で0ではないベクトル\(\boldsymbol{p},\boldsymbol{\bar{p}}\)を考えよう。また、以下の様に定義する。

\[\boldsymbol{p}_{n+1}=M\boldsymbol{p}_n,\ \ \boldsymbol{\bar{p}}_{n+1}=M\boldsymbol{\bar{p}}_n,\ \ \boldsymbol{p}_0=\boldsymbol{p},\ \ \boldsymbol{\bar{p}}_0=\boldsymbol{\bar{p}}\]

仮定(1)から、\(\boldsymbol{p},\boldsymbol{\bar{p}}_n\)はともに、正である。定理1を繰り返し適用することにより、\(n>1\)で以下を得る。

\[\underset{i}{osc}\ \frac{\bar{p}_{n,i}}{p_{n,i}}\leq \left(\frac{\kappa-1}{\kappa+1}\right)^{n-1}\underset{i}{osc}\ \frac{\bar{p}_{1,i}}{p_{1,i}}\ tag{7}\]

 ここで、\(p_{n,i}\equiv(\boldsymbol{p}_n)_i\)という記法を使った。結果として

\[\exists \lambda>0,\forall i,\lim _{n\rightarrow \infty}\frac{\bar{p}_{n,i}}{p_{n,i}}= \lambda \tag{8}\]

がわかる。

ベクトル\(\boldsymbol{p}_n,\boldsymbol{\bar{p}}_n\)を以下の様に規格化する。

\[\boldsymbol{q}_n=\frac{\boldsymbol{p}_n}{p_{n,k}},\ \ \boldsymbol{\bar{q}}_n=\frac{\boldsymbol{\bar{p}}_n}{p_{n,k}}\]

仮定(2)より、

 \[\kappa^{-1}\leq q_{n,i}\leq\kappa,\ \ \kappa^{-1}\leq \bar{q}_{n,i}\leq \kappa \tag{9}\]

が言える。

それゆえ、以下が言える。

\[|\bar{q}_{n,i}-q_{n,i}|=q_{n,i}\frac{p_{n,k}}{\bar{p}_{n,k}} \left|\frac{\bar{p}_{n,i}}{p_{n,i}}-\frac{\bar{p}_{n,k}}{p_{n,k}}\right| \leq \kappa \frac{p_{n,k}}{\bar{p}_{n,k}} \underset{i}{osc}\ \frac{\bar{p}_{n,i}}{p_{n,i}} \tag{10}\]

ここで特に、\(\boldsymbol{\bar{p}}=M\boldsymbol{p}=\boldsymbol{p}_1\)である場合、

\[\boldsymbol{\bar{p}}_n=M\boldsymbol{p}_n=\boldsymbol{p}_{n+1},\ \ \boldsymbol{\bar{q}}_n=\boldsymbol{q}_{n+1}\]

式(7),(8)を用い、(10)により\(\boldsymbol{q}_n\)が\(\boldsymbol{q}\)へと収束することが言える。(9)より、\(\boldsymbol{q}>0\)である。(8)から、

\[\frac{p_{n+1,i}}{p_{n,i}}=\frac{(M\boldsymbol{p}_n)_i}{(\boldsymbol{p}_n)_i}=\frac{(M\boldsymbol{q}_n)_i}{(\boldsymbol{q}_n)_i}\rightarrow \lambda_0\]

 よって、

\[M\boldsymbol{q}=\lambda_0 \boldsymbol{q}\]

となる。定理2は示された。


定理3

同様の仮定の下、固有値問題(6)は\(\lambda=\lambda_0,\boldsymbol{v}=c\boldsymbol{q}\)を除き、正の解をもたない。\(\lambda=\lambda_0\)のとき、(6)は\(\boldsymbol{v}=c\boldsymbol{q}\)を除く解はない。


証)

\(\boldsymbol{v}\geq 0,\boldsymbol{v}\neq 0\)は固有値問題(6)の解とする。仮定(1)より、\(M\boldsymbol{v}>0\)であり、\(\lambda>0\)かつ\(\boldsymbol{v}>0\)なる解を持つ。これを定理2における初期ベクトル\(p\)として用い、定理の最後の部分を適用すると、

\[\frac{M^n\boldsymbol{v}}{(M^n\boldsymbol{v})_k}=\frac{\lambda^n\boldsymbol{v}}{\lambda^n\boldsymbol{v}_k}=\frac{\boldsymbol{v}}{v_k}\]

それゆえ、極限\(\boldsymbol{q}\)は\(\boldsymbol{v}/v_k\)と等しくなり、つまり\(\boldsymbol{v}=c\boldsymbol{q},\lambda=\lambda_0\)である。


定理4

同様の条件の下、固有値問題(6)のあらゆる固有値\(\lambda\neq\lambda_0\)は、以下を満たす。

\[|\lambda|\leq\frac{\kappa-1}{\kappa+1}\lambda_0\]

補足:\((\kappa-1)/(\kappa+1)\)は他の条件がない限り、最良の見積もりである。例えば、

\[M=\begin{pmatrix}\kappa & 1 \\ 1 &\kappa\end{pmatrix}\ \ \kappa>0\]

は固有値\(\lambda_0=\kappa+1,\lambda=\kappa-1\)を持つ。


 証)

次に、定理2の\(\lambda_0>0\)と\(\boldsymbol{q}>0\)なる解と\(M\boldsymbol{v}=\lambda\boldsymbol{v}\)の解を考える。\(\boldsymbol{q},\boldsymbol{v}\)に定理1を適用して、

\[\frac{|\lambda|}{\lambda_0}\underset{i}{osc}\ \frac{v_i}{q_i}=\underset{i}{osc}\ \frac{\lambda v_i}{\lambda_0q_i}=\underset{i}{osc}\ \frac{(M\boldsymbol{v})_i}{(M\boldsymbol{q})_i}\leq\frac{\kappa-1}{\kappa+1}\underset{i}{osc}\ \frac{v_i}{q_i}\]

\(\lambda\neq\lambda_0\)かつ\(\boldsymbol{v}\neq 0\)ならば\(\boldsymbol{v}\)は\(c\boldsymbol{q}\)と等しく成り得ないから、定理を得る。

【論考】グループ分けページランク

以下の内容は、転載を禁じます。

【導入】

ページランクとそれに類するアルゴリズムは一般に、ランク付けすべき対象(本論考では、ノードと呼ぶ)は同質な集団である。(例えば、ページランクの場合はウェブページ、EigenTrustではブロックチェーンに参加しているノード)

 

本論考では、ノードが本質的に違うようないくつかの集団に分けられるが、お互いに関係があって相対的な評価が可能である場合に、グループ分けしてランクを評価したい、あるいは、何らかの属性を持っているノードをクラスタリングし、グループ分けして異なるグループに属するノード間の相対的な評価を何らかの方法で定義した場合に、クラスタリングにより分けられたグループのそれぞれのノードの中でのみランクを評価したい場合などを考える。

例えば、店舗網があり、複数のアルバイトがいて、それぞれのアルバイトはいくつか複数の店舗で働いた経験をもっているような場合を考えると、店舗網同士、アルバイト同士での相対的評価値は存在しないが、各店舗と各アルバイトでの相対的評価値は何らかの方法であらかじめ計算しておけるような状況が考えられる。

また、会社などの組織中で、取締役、エンジニア、営業などの本質的に異なるグループがあり、取締役同士で直接評価値を出したくはないが、エンジニア、営業などからどれぐらい評価値があるのかを考えたうえで取締役同士の評価をしたい場合なども考えられる。

さらに、ある文章があり、それぞれの文ごとに区切り、これを一グループとして、それぞれの文中の単語のそれぞれにスコアを与えたい場合なども考えられるだろう。

 

以下、このような状況を数学的に抽象化、一般化、定式化して議論を行う。

 

【数学的議論】

 

グループの集合\(\textbf{G}=\{G_1,G_2,…,G_n\}\)

ノードの集合\(\textbf{n}=\{n_1,n_2,…,n_N \}(\forall n \in \textbf{n},\exists ! G \in \textbf{G},n \in G)\)

とし、ノード\(i\)から\(j\)への相対評価を\(r_{ij}\)と書く。

全てのグループの数\(n(=|\textbf{G}|)\)を長さとする任意の巡回置換\(\sigma\)を考え、全てのグループ\(G_i\)に関して、それに属する全てのノードからあるグループ\(G_{\sigma (i)}\)に属する全てのノードのみへの\(|G_i||G_{\sigma(i)}|\)通りの正の相対評価値\(\forall n \in G_i,m \in G_{\sigma(i)}\)に対して\(r_{nm}\)があらかじめ何らかの方法で計算されている場合を考える。

\(\forall i \in \{1,2,…,n\},\forall n \in G_i,m \in G_{\sigma(i)},\exists r_{nm} \in \mathbb{R}_{>0},\)

\(if \ n \in G_i,m \not\in G_ {\sigma(i)},r_{nm}=0\)

逆に、巡回置換でない場合、以下の議論を追えばわかるように、相対評価を行列で表現したものは既約でないため、べき乗法による収束は保証されない。

巡回置換である場合には、以下に示すように数学的、アルゴリズム的に面白い。さらに以下で示すように、複数の巡回置換を考えて行列に足しこむことで理論は一般化できるから、本論考ではこの場合のみに絞って考えていく。

 

ここで、以下のようにそれぞれのノードを評価する方法を考える。

 まず、相対評価を表す行列\(r_{ij}\)を行列で表したもの)\(A\)は、行、列の入れ替え(つまり、\(\sigma(i)=i+1\)になるようにグループ番号を変更し、行列の各行、列に早いグループ番号に属するノードから詰めていく。)によって以下の形の行列に変形できる。

\(A=\begin{pmatrix}0 & A_1 & 0 & \cdots &0\\ 0 & 0 & A_2 & 0 &0\\ \vdots & \vdots & \vdots  &  \ddots &\\ A_n & 0 & 0 & 0 &0\end{pmatrix}\)

\(A_i\)は、グループ\(i\)の属するノードからグループ\(i+1\)に属するノードへの評価を表した行列である。

 \(A^2\)は、

\(A^2=\begin{pmatrix}0 & 0 & A_1 A_2 & \cdots &0\\ 0 & 0 & 0 & \cdots &0\\ \vdots & \vdots & \vdots  &  \ddots &\\ 0 & A_n A_1 & 0 & 0 &0\end{pmatrix}\)

となる。

これを繰り返す(n-1回の掛け算を行う)と、以下の式になることは容易に想像できよう。

\(A^n=\begin{pmatrix}A_1 A_2 … A_n & 0 & 0 & \cdots &0\\ 0 & A_2 A_3 … A_1 & 0 & \cdots &0 \\ \vdots & \vdots & \vdots  &  \ddots \\ 0 & 0 & 0 & 0 &A_n A_1 … A_n-1\end{pmatrix}\)

つまり対角線上に、それぞれのグループの要素数ごとの大きさの正方行列があるような行列が作れる。

それぞれの正方行列はまた、\(i\)のグループから\(i+1,i+2,…,N,1,…,i-1\)のグループの相対評価を考慮した上での、それぞれのグループ内での相対評価値を求めたものとして解釈できる。

それぞれの正方行列は一般に、全ての成分が正であるから、既約かつ非周期的である。よって、それぞれの正方行列でべき乗法を実行すれば、それぞれのグループ内での絶対的評価を計算することもできる。

つまり、対角線上のそれぞれの対角行列\(P_i=A_i A_{i+1}\cdots A_{i-1}\)と\(P_i\)の、最大固有値以外の固有値に属する固有ベクトルを除く、次元\(|G_i|\)の任意のベクトル\(x\)に対して、

\(\displaystyle \lim _{n \rightarrow \infty} (P_i)^n x/|(P_i)^n x|\)

を考えると、\(n \rightarrow \infty\)での収束が保証され、収束先のベクトルは、ページランクと同じようにそれぞれのノード固有の評価値として解釈できる。

(これは、\((A^n)^m\)を計算し、再度対角線上の正方行列を取り出すことと同じである。それぞれのグループの中でのみランク付けしたい場合、Aそのものの掛け算を計算する必要はないから、計算コストは削減できることに気付いてほしい。)

さらに、長さ\(n\)の巡回置換を複数考え、これを”道”のようなものと捉えることもできる。

道を複数考え、つまり大きさ\(n\)の巡回置換を複数考え、その巡回置換に対応するようなグループ間の評価値を行列\(A\)に足しこんだとしても、道に交わり(合流する部分、つまり2つの巡回置換\(\sigma_1,\sigma_2\)において、\(\sigma_1(i)=\sigma_2(i)\)となるような\(i\)が存在するとき)がない場合、行列の和の積は積の和に直せるから、計算コストを削減しつつ、有用な道をたくさん考えたうえで\(A\)に足しこむことも可能である。

交わりのある場合でも、繰り返しループの中でその交わりを考慮しなければならないとき以外で行列の和の積は積の和の形で書けるから、計算量は大幅に削減できる。