位相幾何学(トポロジー)

距離空間

距離空間は集合に3つの公理を満たす距離関数を備えたものであり、完備距離空間上の縮小写像は常にただ一つの不動点を持つ(バナッハの定理)。これはPageRank、反復解法、フラクタル画像圧縮を支える原理である。

直観定規なしで距離を測る

GPSは直線距離を、タクシー運転手は街区格子上の距離を、スペルチェッカーは単語間の「編集距離」を使う。この3つがいずれも正当な距離の概念であるのは、同じ3つの常識的な規則を満たしているからだ:距離は決して負にならず、2点が一致するときのみ0になる、 $A$ から $B$ への距離は $B$ から $A$ への距離に等しい、そして点 $C$ を経由する遠回りは $A$ から $B$ への直行より短くなることはない。距離空間とは、まさにこの3つの規則に従う距離関数を備えた集合のことである。

\mathbb{R}

上の写像

T(x) = 0.5x + 1

(

d(x,y)=|x-y|

とする)は比

q=0.5

の縮小写像であり、任意の2点間の距離を常に半分にする。スライダーを動かして、どの出発点も同じ不動点

x^* = 2

に反復収束することを確認しよう。

大学3つの公理

定義: 距離空間

集合 $X$ 上の距離(メトリック)とは、すべての $x,y,z \in X$ について次を満たす関数 $d: X \times X \to \mathbb{R}$ である:(M1)正値性 $d(x,y) \ge 0,\ d(x,y)=0 \iff x=y$ ;(M2)対称性 $d(x,y) = d(y,x)$ ;(M3)三角不等式 $d(x,z) \le d(x,y) + d(y,z)$ 。組 $(X,d)$ を距離空間という。

d(x,y) \ge 0,\quad d(x,y)=0 \iff x=y \qquad d(x,y)=d(y,x) \qquad d(x,z) \le d(x,y)+d(y,z)

重要な例は2つある。 $\mathbb{R}^n$ 上の** $\ell_p$ 距離**は $p \ge 1$ に対して $d_p(x,y) = \left(\sum_{i=1}^n |x_i - y_i|^p\right)^{1/p}$ である( $p=2$ で通常のユークリッド距離、 $p=1$ で「タクシー」距離、 $p\to\infty$ で座標差の最大値となる)。連続関数の空間 $C([a,b])$ 上の上限距離は $d_\infty(f,g) = \sup_{t \in [a,b]} |f(t) - g(t)|$ である:2つの関数が近いとは、 $[a,b]$ のどこでもグラフの隔たりが小さいことを意味する。

d_p(x,y) = \left(\sum_{i=1}^n |x_i - y_i|^p\right)^{1/p} \qquad d_\infty(f,g) = \sup_{t \in [a,b]} |f(t) - g(t)|

$\mathbb{R}^n$ 上の距離の比較
距離	公式	単位球の形	典型的な用途
$\ell_1$ (タクシー)	$\sum \|x_i-y_i\|$	ひし形	スパース復元、街区
$\ell_2$ (ユークリッド)	$\sqrt{\sum (x_i-y_i)^2}$	円	物理的距離、PCA
$\ell_\infty$ (チェビシェフ)	$\max_i \|x_i-y_i\|$	正方形	最悪ケース誤差評価

大学球体、完備性、縮小写像

開球 $B(x_0, r) = \{x \in X : d(x, x_0) < r\}$ は中心から距離 $r$ 未満にある点全体である。数列 $(x_n)$ がコーシー列であるとは $\forall \varepsilon > 0\ \exists N\ \forall m,n > N:\ d(x_m,x_n) < \varepsilon$ が成り立つことをいう:項は互いにいくらでも近づくが、まだ固定された極限点に近づくとは限らない。距離空間が完備であるとは、すべてのコーシー列が $X$ の点に収束することをいう。任意の $\ell_p$ 距離を持つ $\mathbb{R}^n$ は完備であるが、 $d(x,y)=|x-y|$ を持つ $\mathbb{Q}$ は $\sqrt{2}$ が欠けているため完備でない。

大学定理

定理: 逆三角不等式

距離空間内の任意の $x,y,z$ について $|d(x,z) - d(y,z)| \le d(x,y)$ 。

なぜ正しいのか?

これは距離関数自身が各変数についてリプシッツ連続(定数1)であることを示し、距離の極限を安全に取れる根拠になる。

証明

ステップ1 — 三角不等式を2回適用する。(M3)より $d(x,z) \le d(x,y) + d(y,z)$ となり、これを整理すると $d(x,z) - d(y,z) \le d(x,y)$ を得る。同じ公理で $x$ と $y$ の役割を入れ替えると $d(y,z) \le d(y,x) + d(x,z) = d(x,y) + d(x,z)$ (対称性 $d(y,x)=d(x,y)$ を使用)となり、整理すると $d(y,z) - d(x,z) \le d(x,y)$ 、すなわち $-(d(x,z)-d(y,z)) \le d(x,y)$ を得る。

ステップ2 — 2つの評価を組み合わせる。2つの不等式 $d(x,z)-d(y,z) \le d(x,y)$ と $-(d(x,z)-d(y,z)) \le d(x,y)$ が同時に成り立つことは、絶対値の定義により、まさに $|d(x,z)-d(y,z)| \le d(x,y)$ という主張である:実数 $u$ が $|u| \le c$ を満たすのは $u \le c$ かつ $-u \le c$ が成り立つときに限る。

定理: バナッハの不動点定理(縮小写像の原理)

$(X,d)$ を完備距離空間とし、 $T: X \to X$ を縮小写像、すなわちある固定された $0 \le q < 1$ とすべての $x,y \in X$ について $d(T(x), T(y)) \le q\, d(x,y)$ が成り立つものとする。このとき $T$ はちょうど1つの不動点 $x^* \in X$ ( $T(x^*)=x^*$ )を持ち、任意の $x_0 \in X$ から始めた反復列 $x_{n+1}=T(x_n)$ は明示的な誤差評価 $d(x_n, x^*) \le \dfrac{q^n}{1-q}\, d(x_1, x_0)$ とともに $x^*$ に収束する。

なぜ正しいのか?

これは存在と一意性に関する問い(この方程式はちょうど一つの解を持つか?)を、収束が保証された機械的な計算に変換し、目標精度に必要な反復回数の事前評価まで与えてくれる。

証明

ステップ1 — 反復列はコーシー列である。 $x_0 \in X$ を固定し $x_n = T^n(x_0)$ とする。縮小性を繰り返し適用すると $d(x_{n+1},x_n) = d(T(x_n),T(x_{n-1})) \le q\,d(x_n,x_{n-1}) \le \dots \le q^n\,d(x_1,x_0)$ 。 $m > n$ に対し、三角不等式を経路 $x_n, x_{n+1}, \dots, x_m$ に沿って連ねると $d(x_m,x_n) \le \sum_{k=n}^{m-1} d(x_{k+1},x_k) \le \sum_{k=n}^{m-1} q^k\,d(x_1,x_0) \le d(x_1,x_0)\sum_{k=n}^{\infty} q^k = d(x_1,x_0)\,\dfrac{q^n}{1-q}$ ( $0 \le q < 1$ より等比級数の公式を使用)。 $n \to \infty$ で $q^n \to 0$ となるため、この末尾評価は0に収束し、 $(x_n)$ はコーシー列である。

ステップ2 — 完備性が極限を与え、連続性がそれを不動点にする。 $X$ は完備なので、コーシー列 $(x_n)$ はある $x^* \in X$ に収束する。縮小不等式 $d(T(x),T(y)) \le q\,d(x,y)$ より $T$ は(リプシッツ)連続なので、 $T(x^*) = T(\lim_n x_n) = \lim_n T(x_n) = \lim_n x_{n+1} = x^*$ となり、 $x^*$ は不動点である。

ステップ3 — 一意性。 $x^*$ と $y^*$ がともに不動点だとする。すると $d(x^*,y^*) = d(T(x^*),T(y^*)) \le q\,d(x^*,y^*)$ より $(1-q)\,d(x^*,y^*) \le 0$ 。 $1-q>0$ なのでこれは $d(x^*,y^*)=0$ 、すなわち $x^*=y^*$ を強制する。

ステップ4 — 誤差評価。ステップ1の評価 $d(x_m,x_n) \le \dfrac{q^n}{1-q}\,d(x_1,x_0)$ で $m \to \infty$ とし $d$ の連続性を使うと、まさに $d(x_n,x^*) \le \dfrac{q^n}{1-q}\,d(x_1,x_0)$ を得る: $n$ 回後の真の不動点までの距離は等比的に縮小し、この評価は反復を1回も実行する前に計算できる。

大学実世界での応用と具体例

GoogleのPageRankは、確率ベクトルに繰り返し適用することでウェブリンク行列の優固有ベクトルを計算する——このべき乗反復は確率分布上の $\ell_1$ 距離における縮小写像である。反復線形解法(ヤコビ法、ガウス・ザイデル法)は $Ax=b$ を不動点写像 $x \mapsto Cx+d$ に書き換え、 $A$ が対角優位であれば上限距離で縮小写像となる。フラクタル(IFS)画像圧縮は、画像を上限/ハウスドルフ距離を備えた画像空間上の縮小写像の唯一の不動点として表現し、復元は単にその写像を反復するだけである。

例: 確率ベクトル上の縮小写像としてのPageRank

2ページからなる小さなウェブがリンク行列 $M = \begin{pmatrix} 0.1 & 0.9 \\ 0.9 & 0.1 \end{pmatrix}$ を持つ(各列はダンピング係数付きでランクを再分配する)。 $r_0 = (1,0)$ から始め、 $\ell_1$ 距離 $d(x,y)=|x_1-y_1|+|x_2-y_2|$ を用いて $r_1 = Mr_0$ と $r_2 = Mr_1$ を計算し、 $q=0.8$ について $d(r_1,r_2) \le q\,d(r_0,r_1)$ を確かめよ。

解答

ステップ1 — $r_1$ を計算。 $r_1 = M r_0 = (0.1 \cdot 1 + 0.9 \cdot 0,\ 0.9 \cdot 1 + 0.1 \cdot 0) = (0.1, 0.9)$ 。

ステップ2 — $r_2$ を計算。 $r_2 = M r_1 = (0.1(0.1)+0.9(0.9),\ 0.9(0.1)+0.1(0.9)) = (0.01+0.81,\ 0.09+0.09) = (0.82, 0.18)$ 。

ステップ3 — 距離を計算し縮小比を確認。 $d(r_0,r_1) = |1-0.1|+|0-0.9| = 0.9+0.9=1.8$ 。 $d(r_1,r_2)=|0.1-0.82|+|0.9-0.18|=0.72+0.72=1.44$ 。実際 $1.44 = 0.8 \times 1.8$ となり $q=0.8$ に正確に一致する(ダンピング係数により $M$ の行・列和が0.5だけずれることでこの比が生まれる)。これにより反復が縮小し、定常ランクベクトル $(0.5,0.5)$ に収束することが確認できる。

例: 目標圧縮精度に必要な反復回数は?

あるフラクタル画像圧縮のデコーダは、画像上の上限距離に関して比 $q=0.6$ の縮小写像 $T$ を適用し、最初の2回の反復は $d(x_1,x_0)=100$ (ピクセル強度単位)を満たす。誤差評価 $d(x_n, x^*) \le \dfrac{q^n}{1-q}\, d(x_1, x_0)$ を用いて、 $d(x_n,x^*) < 1$ を保証する最小の $n$ を求めよ。

解答

ステップ1 — 解くべき不等式を立てる。 $\dfrac{q^n}{1-q}\,d(x_1,x_0) < 1$ 、すなわち $\dfrac{0.6^n}{0.4} \times 100 < 1$ 、すなわち $0.6^n < 0.004$ が必要である。

ステップ2 — 対数を取る。 $n \ln(0.6) < \ln(0.004)$ 。 $\ln(0.6) \approx -0.5108$ は負なので、割ると不等号の向きが変わり $n > \dfrac{\ln(0.004)}{\ln(0.6)} = \dfrac{-5.521}{-0.5108} \approx 10.81$ を得る。

ステップ3 — 最小の整数に切り上げる。 $n = 11$ 回の反復で $d(x_n,x^*) < 1$ ピクセル強度単位が保証され、この回数は反復を1回も実行する前から分かっていた——これこそ画像圧縮コーデックにおける事前誤差評価の実用的な価値である。

$\mathbb{R}$ 上の $d(x,y) = (x-y)^2$ で成り立たない性質はどれか?

$\ell_2$ 距離を使うと、 $\mathbb{R}^3$ における $d((1,2,2),(4,6,2))$ はいくらか?

同じ問題に対して反復解法の縮小比が $q=0.1$ ではなく $q=0.9$ だとどうなるか?

バナッハの不動点定理が適用できることを保証する条件の組はどれか?

参考文献

Walter Rudin (1976). Principles of Mathematical Analysis
James Munkres (2000). Topology
Shaojie Bai, J. Zico Kolter, Vladlen Koltun (2019). Deep Equilibrium Models · arXiv:1909.01377