数式を空間操作として読む翻訳辞書

ネットワーク研究者のための直観的・幾何学的線形代数

行列を「計算の規則」ではなく、空間を動かし、グラフ上に情報を流す装置として眺める。論文中の式を見た瞬間に、どの軸が残り、どの成分が消え、どこにテンションが生まれるかを読むための教材です。

ベクトル 矢印、またはノード上の状態

行列 空間を動かす動詞

固有ベクトル 変換に逆らわない軸

ラプラシアン 隣との差を集める装置

第1章行列の読み方

行列をかけるとは、2つの翻訳を同時に覚えること

$Ax$ は、出力を列ベクトルの足し合わせとして作る読み方と、各行が入力を測って数値を返す読み方の両方で見られます。 SVDの $V^T$ は「内積リスト」、 $U$ は「列の線形結合」として読むと、後の図がつながります。

列の線形結合

$Ax=x_1a_1+\cdots+x_na_n$ 。入力の各座標を「つまみ」として、列ベクトルを混ぜて出力を作る。

内積リスト

$Ax=(r_1^Tx,\ldots,r_m^Tx)^T$ 。各行が入力にセンサーを当て、測定値のリストを返す。

同じ $Ax$ を2枚の絵で見る

列で見ると「材料を混ぜて出力を作る」。行で見ると「入力にセンサーを当てて測定値を並べる」。 SVDはこの2つを $V^T$ と $U$ に分けて、きれいな順番にしたものとして読めます。

Ax=x_1a_1+x_2a_2+x_3a_3

列 $a_i$ は出力空間の矢印です。 $x_i$ はその矢印を何倍して混ぜるかを決める係数です。

Ax=\begin{bmatrix}r_1^Tx\\ r_2^Tx\\ r_3^Tx\end{bmatrix}

行 $r_i^T$ は入力空間のセンサーです。 $x$ を測った値が、出力ベクトルの各成分になります。

第2章部分空間と射影

直交射影は「影を取り出し、残りを消す」操作

次の行列は、ベクトル $v$ から $w$ 方向だけを拾い上げるフィルターです。

u=\frac{w}{\|w\|},\qquad P=uu^T=\frac{ww^T}{\|w\|^2}

$I-P$ はその逆で、既知の構造の影を抜いた残差だけを残します。

読む: $Pv$ は「w の軸へ落ちた影」
見る: 3次元空間の青い矢印を、緑の軸へ垂直に落とす
研究での意味: 一様成分や既知の構造をデータからキャンセルする

Projection Lab

影と残差

v.x v.y v.z w.x w.y w.z

なぜこの行列が射影になるのか

Pv=uu^Tv=u(u^Tv),\qquad u=\frac{w}{\|w\|}

まず $w$ を長さ1の方向ベクトル $u$ に直す。

$v$ が $u$ 方向に何単位ぶん進んでいるかを測る。

測った長さぶんだけ $u$ を伸ばし、 $w$ 軸上の点へ戻す。

空間として見ると何が起きるか

P(\mathbb{R}^3)=\mathrm{span}(w),\qquad \ker P=w^\perp

射影行列は、空間の点をそれぞれ $w$ 軸へ垂直に落とします。軸に垂直な同じ平面にいる点たちは、すべて同じ軸上の点へ潰れます。

第4章 SVD

SVDは「球を楕円体にする」変換の分解

$A=U\Sigma V^T$ は、入力ベクトルを右特異ベクトルの座標で読み直し、各座標を特異値だけ伸ばし、その結果を左特異ベクトルの向きとして出力空間へ組み立てる操作です。長方形行列でも、入力空間と出力空間を別々の座標系として扱えば同じ絵で読めます。

SVD Lab

球から楕円体へ

σ1 σ2 σ3 視点

なぜ SVD は回転・伸縮・回転として読めるのか

A=U\Sigma V^T,\qquad Ax=\sum_i \sigma_i (v_i^Tx)u_i

$V=[v_1,\ldots,v_n]$ と見ると、 $V^T$ は物体を無理に動かすというより、 $x$ を「右特異ベクトル $v_i$ 方向に何単位あるか」という座標ベクトルへ翻訳します。

$\Sigma$ が $\hat{x}_i$ を $\sigma_i\hat{x}_i$ に変えたあと、 $U$ はその座標ベクトルを左特異ベクトル $u_i$ の線形結合として出力空間に描き直します。

$x$ と各右特異ベクトル $v_i$ の内積を測り、成分のリストにする。

各座標 $\hat{x}_i$ を $\sigma_i$ 倍する。小さい $\sigma_i$ の方向ほど情報は弱く残る。

伸縮後の座標を、左特異ベクトル $u_i$ の足し合わせとして出力空間に配置する。

まず2Dでイメージをつかむ

x\ \xrightarrow{V^T}\ \hat{x}\ \xrightarrow{\Sigma}\ \Sigma\hat{x}\ \xrightarrow{U}\ Ax

2次元では、 $\Sigma$ が円を楕円に変え、 $U$ はその楕円を形を変えずに回します。

進行

3Dで1点を変換する

入力を置く、各 $v_i$ 方向の成分として測る、特異値をかける、出力空間の $u_i$ 方向へ置き直す、最後に足し合わせる、という順番を一段ずつ進めます。

進行

3Dで空間全体を見る

1本のベクトルだけでなく、周囲の点や座標軸も同じ $A=U\Sigma V^T$ で動きます。球面の網目が楕円体へ伸び、最後に出力空間の向きへ置き直される様子を見ると、行列が空間全体をどう歪めるかが見えてきます。

進行

別空間へ移る場合

\begin{aligned}A&:\mathbb{R}^2\to\mathbb{R}^3\\ Ax&=\sigma_1(v_1^Tx)u_1+\sigma_2(v_2^Tx)u_2\end{aligned}

入力空間と出力空間の次元が違うとき、 $U$ は同じ場所で物体を回すというより、伸縮後の座標を出力空間の $u_i$ 軸へ置き直します。余った出力方向は、この入力からは直接使われません。

進行

\begin{aligned}A&\in\mathbb{R}^{m\times n},\quad U\in\mathbb{R}^{m\times m},\quad V\in\mathbb{R}^{n\times n}\\ \Sigma&\in\mathbb{R}^{m\times n},\quad \Sigma_{ii}=\sigma_i,\quad \Sigma_{ij}=0\ (i\ne j)\end{aligned}

入力は $\mathbb{R}^n$ 、出力は $\mathbb{R}^m$ 。同じ空間に戻る変換ではないので、 $V$ は入力側の座標系、 $U$ は出力側の座標系として別々に持つ。

入力座標は $n$ 個しかない。 $\Sigma$ はそれらを特異値で伸ばしてから、 $\mathbb{R}^m$ の中へ置く。余った出力方向は、この行列からは直接は出てこない。

入力方向の方が多いので、 $\Sigma$ は全部の入力座標を出力に運べない。行数に入らない方向や $\sigma_i=0$ の方向は潰れ、出力からは区別できなくなる。

ランクを $r$ とすると、本当に生き残るのは $\sigma_1,\ldots,\sigma_r>0$ の方向だけ。つまり $A=\sum_{i=1}^r\sigma_i u_i v_i^T$ と読める。

第4章固有値

対称行列の固有値分解は「軸が変わらない」タイプのSVD

SVDでは入力側の軸 $v_i$ と出力側の軸 $u_i$ を別々に持ちます。対称行列ではこの2つが同じ向きに揃い、 $Aq_i=\lambda_iq_i$ と読めます。正半定値なら $A=Q\Lambda Q^T$ はそのまま $U=V=Q,\ \Sigma=\Lambda$ のSVDです。

同じ軸で測る

まず $q_i^Tx$ と内積を取り、固有ベクトル方向の成分リストにする。

符号つきで伸ばす

$\lambda_i$ が正なら同じ向き、負なら同じ直線上で反対向きに返す。

同じ軸へ戻す

負の $\lambda_i$ はSVDの非負な $\sigma_i$ ではなく、出力軸の向きの反転として吸収して見る。

第5章グラフ上の行列

はグラフ上のテンション総量

行列を「成分を測る」「軸に戻す」装置として見たあとなら、グラフラプラシアンも同じ言葉で読めます。 $x^TLx=\sum_{(i,j)\in E}(x_i-x_j)^2$ は、エッジごとの差を測り、その食い違いの大きさを足し上げるエネルギーです。

読む: エッジごとの水位差を二乗して集める
見る: 赤く太いエッジほど強く張っている
研究での意味: クラスタ内で滑らか、境界で変化する信号を見つける

Graph Energy Lab

滑らかさのエネルギー

energy 0.00 近い値が並ぶほど小さい

翻訳カード

論文で見かけた瞬間の読み替え

Walk

k ステップで届く経路の数。インクが何回ジャンプしてどこまで広がるか。

Gradient

ノードの水位をエッジの水位差へ変える。グラフ上の微分。

Schur

隠したノード群を潰し、残ったノード間に新しい近道を張り直す。

Perron

人気が人気を呼ぶ反復の行き先。正の中心性ベクトル。

Gap

インクが混ざり切る速さ。小さいとどこかに細い橋がある。

Pseudo inverse

潰れて消えた方向は諦め、生き残った情報だけで一番小さく戻す。