Johnson–Lindenstraussの補題(Johnson–Lindenstrauss lemma)とは、Euclid 空間の $N$ 個の点は、元の次元によらず $k=O(\varepsilon^{-2}\log N)$ 次元へ、すべての 2 点間の距離の 2 乗を $1\pm\varepsilon$ 倍の範囲に保って写せる、という定理である。成分が独立な正規分布(または等確率の $\pm1$)の乱数の行列を $\sqrt k$ で割って掛けるだけで、高い確率でそのような 1 次写像が得られる。証明はカイ二乗分布の裾の指数的な評価と、点の組についての確率の和の評価による。次元が $\log N$ の定数倍より小さいと、どんな写像でも距離を保てない点の集合がある。
Johnson–Lindenstraussの補題(Johnson–Lindenstrauss lemma)とは、Euclid 空間の $N$ 個の点は、元の次元 $d$ によらず $k=O(\varepsilon^{-2}\log N)$ 次元の Euclid 空間へ、すべての 2 点間の距離の 2 乗を $1\pm\varepsilon$ 倍の範囲に保ったまま写せる、という定理である。しかもその写像は 1 次写像でとれ、成分が独立な正規分布に従う乱数の行列を掛けるだけで、高い確率でうまくいく。
$100$ 万個の点が $10$ 万次元にあっても、距離を $1\%$ ほどの誤差で保つだけなら $3$ 万次元あまりで足りる(ex-jl-million)。必要な次元が点の個数の 対数 でしか増えず、元の次元にまったくよらない点が要である。データに依存しない行列 1 つで済むので、近傍探索・クラスタリング・数値線形代数などで、計算の前に次元を落とす道具として使われる。この補題は W. B. Johnson と J. Lindenstrauss が 1984 年に Lipschitz 写像の拡張の研究の中で示した(Ver18 p. 133 の文献注による)。
この記事では、カイ二乗分布の裾の評価から始めて、Gauss 行列による証明を定数まで明示して書く。さらに、成分を $\pm1$ に替えた行列でも同じ評価が成り立つこと、次元が $\log N$ の定数倍より小さいとどんな写像でもうまくいかない点の集合があることを示す。
$\mathbb{R}^d$ の Euclid ノルムを $\|\cdot\|$ と書く。
$X\subset\mathbb{R}^d$、$0<\varepsilon<1$ とする。写像 $f\colon X\to\mathbb{R}^k$ が、すべての $x,y\in X$ について
$$
(1-\varepsilon)\|x-y\|^2\le\|f(x)-f(y)\|^2\le(1+\varepsilon)\|x-y\|^2
$$
を満たすとき、$f$ は $X$ 上で $\varepsilon$ 近似等長 であるという。
$X\subset\mathbb{R}^d$ を $N\ge2$ 個の点の集合、$0<\varepsilon<1$、$0<\delta<1$ とする。$k$ を
$$
k\ge\frac{12}{\varepsilon^2}\log\frac{N(N-1)}{\delta}
$$
を満たす自然数とし、$G$ を成分が独立に標準正規分布 $N(0,1)$ に従う $k\times d$ の乱数の行列、$A:=G/\sqrt k$ とする。このとき、1 次写像 $x\mapsto Ax$ が $X$ 上で $\varepsilon$ 近似等長である確率は $1-\delta$ 以上である。
1 本の差のベクトルの長さがカイ二乗分布で表され、平均のまわりに指数的に集中すること(lem-jl-chi2、lem-jl-single)を示し、$N(N-1)/2$ 個の差に確率の和の評価を当てる。証明は prf-thm-jl-main にある。
$N\ge2$ 個の点の集合 $X\subset\mathbb{R}^d$ と $0<\varepsilon<1$ について、$k\ge24\varepsilon^{-2}\log N$ なら、$X$ 上で $\varepsilon$ 近似等長な 1 次写像 $\mathbb{R}^d\to\mathbb{R}^k$ が存在する。
thm-jl-main の証明は、失敗の確率が $N(N-1)e^{-k\varepsilon^2/12}$ 以下であることを示す(prf-thm-jl-main)。$k\ge24\varepsilon^{-2}\log N$ ならこれは $N(N-1)N^{-2}=1-\frac1N< 1$ 以下なので、成功の確率は正であり、成功する $A$ が少なくとも 1 つある。$\square$
文献によって、条件を距離そのもので $(1-\varepsilon)\|x-y\|\le\|f(x)-f(y)\|\le(1+\varepsilon)\|x-y\|$ と書くことがある(Ver18 Theorem 5.3.1)。$0<\varepsilon<1$ なら $1-\varepsilon\le\sqrt{1-\varepsilon}$、$\sqrt{1+\varepsilon}\le1+\varepsilon$ なので、この記事の意味で $\varepsilon$ 近似等長なら距離の形でも $\varepsilon$ で成り立つ。逆に距離の形で $\varepsilon$ なら、$(1-\varepsilon)^2\ge1-2\varepsilon$、$(1+\varepsilon)^2\le1+3\varepsilon$ から 2 乗の形で $3\varepsilon$ である。どちらの形でも、必要な次元の大きさは $\varepsilon^{-2}\log N$ の定数倍で変わらない。
証明の中心は、独立な標準正規分布の $k$ 個の 2 乗の和(自由度 $k$ の カイ二乗分布)が、平均 $k$ のまわりに指数的に集中することである。
$g_1,\dots,g_k$ を独立な標準正規分布に従う確率変数とし、$Q:=g_1^2+\cdots+g_k^2$ とする。$0<\varepsilon<1$ について
$$
P\bigl(Q\ge(1+\varepsilon)k\bigr)\le\exp\Bigl(-\frac k2\bigl(\varepsilon-\log(1+\varepsilon)\bigr)\Bigr)\le e^{-k\varepsilon^2/12},
$$
$$
P\bigl(Q\le(1-\varepsilon)k\bigr)\le\exp\Bigl(\frac k2\bigl(\varepsilon+\log(1-\varepsilon)\bigr)\Bigr)\le e^{-k\varepsilon^2/4}.
$$
$g$ を標準正規分布に従う確率変数とする。$t< \frac12$ について
$$
E[e^{tg^2}]=\frac1{\sqrt{2\pi}}\int_{-\infty}^{\infty}e^{-(1-2t)x^2/2}\,dx=(1-2t)^{-1/2}
$$
である($x=y/\sqrt{1-2t}$ と置換する)。独立性から $E[e^{tQ}]=(1-2t)^{-k/2}$ である。
上側。 $0\le t< \frac12$ について、濃度不等式 の補題「Chernoff の方法」(指数関数に Markov の不等式を当てる)により
$$
P\bigl(Q\ge(1+\varepsilon)k\bigr)\le e^{-t(1+\varepsilon)k}E[e^{tQ}]=e^{-t(1+\varepsilon)k}(1-2t)^{-k/2}.
$$
$t:=\frac{\varepsilon}{2(1+\varepsilon)}$ とおくと $1-2t=\frac1{1+\varepsilon}$ で、右辺は $e^{-\varepsilon k/2}(1+\varepsilon)^{k/2}$ となり、最初の不等式を得る。次に、$\varepsilon\ge0$ では交代級数の評価 $\log(1+\varepsilon)\le\varepsilon-\frac{\varepsilon^2}2+\frac{\varepsilon^3}3$ が成り立つ(両辺の差を $\varepsilon$ で微分すると $\frac{\varepsilon^3}{1+\varepsilon}\ge0$ で、$\varepsilon=0$ で差は $0$)。よって $0<\varepsilon<1$ では
$$
\varepsilon-\log(1+\varepsilon)\ge\frac{\varepsilon^2}2-\frac{\varepsilon^3}3\ge\frac{\varepsilon^2}2-\frac{\varepsilon^2}3=\frac{\varepsilon^2}6
$$
であり、2 つ目の不等式を得る。
下側。 $t\ge0$ について $E[e^{-tg^2}]=(1+2t)^{-1/2}$ であり(同じ計算)、Markov の不等式を $e^{-tQ}$ に当てると
$$
P\bigl(Q\le(1-\varepsilon)k\bigr)=P\bigl(e^{-tQ}\ge e^{-t(1-\varepsilon)k}\bigr)\le e^{t(1-\varepsilon)k}(1+2t)^{-k/2}.
$$
$t:=\frac{\varepsilon}{2(1-\varepsilon)}$ とおくと $1+2t=\frac1{1-\varepsilon}$ で、右辺は $e^{\varepsilon k/2}(1-\varepsilon)^{k/2}$ となる。$-\log(1-\varepsilon)=\sum_{j\ge1}\varepsilon^j/j\ge\varepsilon+\frac{\varepsilon^2}2$ から $\varepsilon+\log(1-\varepsilon)\le-\frac{\varepsilon^2}2$ であり、2 つ目の不等式を得る。$\square$
$A=G/\sqrt k$ を thm-jl-main の行列とする。$u\in\mathbb{R}^d$、$u\ne0$、$0<\varepsilon<1$ について
$$
P\Bigl(\bigl|\|Au\|^2-\|u\|^2\bigr|>\varepsilon\|u\|^2\Bigr)\le e^{-k\varepsilon^2/12}+e^{-k\varepsilon^2/4}\le2e^{-k\varepsilon^2/12}.
$$
$G$ の第 $i$ 行を $(G_{i1},\dots,G_{id})$ とすると、$(Gu)_i=\sum_jG_{ij}u_j$ は独立な正規分布の 1 次結合なので、平均 $0$、分散 $\sum_ju_j^2=\|u\|^2$ の正規分布に従う(多変量正規分布 の定理「1 次変換で多変量正規分布は保たれる」)。行どうしは独立なので、$g_i:=(Gu)_i/\|u\|$($i=1,\dots,k$)は独立な標準正規分布に従う。$Q:=\sum_ig_i^2$ とおくと $\|Au\|^2=\frac1k\|Gu\|^2=\frac{\|u\|^2}kQ$ だから、
$$
\bigl|\|Au\|^2-\|u\|^2\bigr|>\varepsilon\|u\|^2\iff Q>(1+\varepsilon)k\ \text{または}\ Q< (1-\varepsilon)k
$$
である。lem-jl-chi2 の 2 つの評価を足せばよい。$\square$
$A$ が $X$ 上で $\varepsilon$ 近似等長でないのは、ある組 $\{x,y\}\subset X$($x\ne y$)について、$u:=x-y$ が $\bigl|\|Au\|^2-\|u\|^2\bigr|>\varepsilon\|u\|^2$ を満たすときである($Ax-Ay=A(x-y)$ を使う)。組は $\binom N2=\frac{N(N-1)}2$ 個あり、1 つの組でこれが起こる確率は lem-jl-single により $2e^{-k\varepsilon^2/12}$ 以下である。確率の劣加法性により、失敗の確率は
$$
\frac{N(N-1)}2\cdot2e^{-k\varepsilon^2/12}=N(N-1)e^{-k\varepsilon^2/12}
$$
以下であり、$k$ の仮定から $N(N-1)e^{-k\varepsilon^2/12}\le N(N-1)\cdot\frac{\delta}{N(N-1)}=\delta$ である。$\square$
証明で使ったのは、1 つの方向の長さが確率 $1-2e^{-k\varepsilon^2/12}$ 以上で保たれること(分布版の評価)と、方向の個数が $N^2$ 程度であることだけである。失敗の確率は方向ごとに指数的に小さいので、方向の個数の対数だけ次元を増やせば全体の和を抑えられる。これが $\log N$ の由来である。元の次元 $d$ はどこにも現れない。
正規分布の乱数の代わりに $\pm1$ を等確率でとる乱数を使っても、同じ定数で同じ結論が成り立つ。行列の積が足し算と引き算だけになるので、計算の上で扱いやすい。
thm-jl-main で、$G$ の成分を、独立に確率 $\frac12$ ずつ $1$ と $-1$ をとる確率変数に替えても、同じ $k$ の条件で同じ結論が成り立つ。
prf-thm-jl-main は lem-jl-single しか使わないので、固定した $u$ について同じ評価を示せばよい。$\|u\|=1$ としてよい。行は独立で同じ分布なので、1 行 $(r_1,\dots,r_d)$ について $S:=\sum_jr_ju_j$ とおくと、$k\|Au\|^2$ は $S$ と同じ分布の独立な $k$ 個の $S_1^2+\cdots+S_k^2=:Q$ である。
偶数次の積率の比較。 $g_1,\dots,g_d$ を独立な標準正規分布の確率変数とし、$Z:=\sum_jg_ju_j$ とおくと $Z$ は標準正規分布に従う。$S^{2q}$ を多項定理で展開すると
$$
E[S^{2q}]=\sum_{m_1+\cdots+m_d=2q}\frac{(2q)!}{m_1!\cdots m_d!}\prod_ju_j^{m_j}\prod_jE[r_j^{m_j}]
$$
であり、$E[r^m]$ は $m$ が偶数なら $1$、奇数なら $0$ である。$Z^{2q}$ でも同じ展開で、$E[g^m]$ は $m$ が奇数なら $0$、偶数なら $(m-1)(m-3)\cdots1\ge1$ である。どちらも残るのはすべての $m_j$ が偶数の項だけで、そのとき $\prod_ju_j^{m_j}\ge0$ だから、項ごとに比べて $E[S^{2q}]\le E[Z^{2q}]$ である。
上側。 $0\le t< \frac12$ について、非負の項の級数の和と期待値は交換できるので
$$
E[e^{tS^2}]=\sum_{q\ge0}\frac{t^qE[S^{2q}]}{q!}\le\sum_{q\ge0}\frac{t^qE[Z^{2q}]}{q!}=E[e^{tZ^2}]=(1-2t)^{-1/2}.
$$
よって $E[e^{tQ}]\le(1-2t)^{-k/2}$ で、prf-lem-jl-chi2 の上側の計算がそのまま通り、$P(Q\ge(1+\varepsilon)k)\le e^{-k\varepsilon^2/12}$ である。
下側。 $v\ge0$ で $e^{-v}\le1-v+\frac{v^2}2$ である(右辺から左辺を引いた差とその導関数は $v=0$ で $0$ で、2 階導関数は $1-e^{-v}\ge0$)。$E[S^2]=\sum_ju_j^2=1$、$E[S^4]=3\bigl(\sum_ju_j^2\bigr)^2-2\sum_ju_j^4\le3$(展開で残る項を数える)だから、$t\ge0$ について
$$
E[e^{-tS^2}]\le1-t+\frac{3t^2}2\le\exp\Bigl(-t+\frac{3t^2}2\Bigr).
$$
Markov の不等式により $P(Q\le(1-\varepsilon)k)\le e^{t(1-\varepsilon)k}E[e^{-tS^2}]^k\le\exp\bigl(k(-\varepsilon t+\frac32t^2)\bigr)$ で、$t=\frac\varepsilon3$ とおくと $e^{-k\varepsilon^2/6}\le e^{-k\varepsilon^2/12}$ である。2 つを足して lem-jl-single と同じ評価を得る。$\square$
$k$ を $\log N$ より小さくできないことは、互いに遠い点の集合で分かる。
$e_1,\dots,e_N$ を $\mathbb{R}^N$ の標準基底とし、$X:=\{0,e_1,\dots,e_N\}$ とする。$0<\varepsilon<1$ について、$X$ 上で $\varepsilon$ 近似等長な写像 $f\colon X\to\mathbb{R}^k$ が(1 次でなくても)あれば
$$
k\ge\frac{\log N}{\log\Bigl(1+\sqrt{\dfrac{2(1+\varepsilon)}{1-\varepsilon}}\Bigr)}
$$
である。とくに $\varepsilon=\frac12$ なら $k\ge\log N/\log(1+\sqrt6)$ で、$\log(1+\sqrt6)\approx1.2382$ である。
$v_i:=f(e_i)-f(0)$ とおく。$\|e_i-0\|^2=1$、$\|e_i-e_j\|^2=2$($i\ne j$)なので、仮定から $\|v_i\|^2\le1+\varepsilon$、$\|v_i-v_j\|^2=\|f(e_i)-f(e_j)\|^2\ge2(1-\varepsilon)$ である。$\rho:=\sqrt{(1-\varepsilon)/2}$ とおくと、中心 $v_i$、半径 $\rho$ の開球 $B_i$ は、中心の距離が $2\rho$ 以上なので互いに交わらない。また $B_i$ はどれも中心 $0$、半径 $R:=\sqrt{1+\varepsilon}+\rho$ の球に含まれる。$\mathbb{R}^k$ の半径 $s$ の球の体積は $c_ks^k$($c_k$ は $k$ だけの定数)だから、体積を比べて $Nc_k\rho^k\le c_kR^k$、すなわち $N\le(R/\rho)^k$ である。$R/\rho=1+\sqrt{2(1+\varepsilon)/(1-\varepsilon)}$ なので、対数をとれば主張を得る。$\square$
この下界は $\varepsilon$ について $\varepsilon^{-2}$ の増え方を捉えていない。K. G. Larsen と J. Nelson は、$2$ 以上の整数 $n,d$ と、$(\log_2n)^{0.5001}/\sqrt{\min\{n,d\}}< \varepsilon< 1$ を満たす $\varepsilon$ について、$\mathbb{R}^d$ の $n$ 点の集合で、$\varepsilon$ 近似等長な写像 $f\colon X\to\mathbb{R}^m$ が必ず $m=\Omega\bigl(\varepsilon^{-2}\log(\varepsilon^2n)\bigr)$ を満たすものがあることを示した(LN17 Theorem 2、p. 2。この記事では証明しない)。たとえば $d\ge n$ で $\varepsilon\ge n^{-1/4}$ なら、$n$ が大きいとき $\varepsilon$ は定理の範囲に入り、$\log(\varepsilon^2n)\ge\frac12\log n$ なので、この範囲では cor-jl-existence の $\varepsilon^{-2}\log N$ は定数倍を除いて改良できない。
$N=10^6$ 個の点を、距離の 2 乗の誤差 $\varepsilon=0.1$ で保つには、cor-jl-existence により
$$
k\ge\frac{24\log(10^6)}{0.1^2}\approx33157.2,\qquad k=33158
$$
次元あれば足りる。元の次元 $d$ が $10^5$ でも $10^9$ でも同じ値である($d\le k$ なら恒等写像でよいので、意味があるのは $d$ が大きいときである)。定数 $24$ は証明の簡単さを優先したもので、実際にはずっと小さい $k$ でもうまくいくことが多い(ex-jl-simulation)。
$d=5000$ 次元の $N=200$ 点(成分は独立な標準正規分布の乱数、種 $20261105$)をとる。$\varepsilon=\frac12$ のとき、cor-jl-existence は $k\ge24\log200/0.25\approx508.6$ より $k=509$ を与え、thm-jl-main で失敗の確率を $\delta=0.01$ 以下にするには $k\ge\frac{12}{0.25}\log\frac{200\cdot199}{0.01}\approx729.4$ より $k=730$ である。
Gauss 行列を 1 つ引いて写すと、$19900$ 組すべての比 $\|Ax-Ay\|^2/\|x-y\|^2$ の範囲は次のとおりであった。
| $k$ | 比の最小 | 比の最大 | $\max\lvert\text{比}-1\rvert$ |
|---|---|---|---|
| $50$ | $0.3898$ | $1.9417$ | $0.9417$ |
| $200$ | $0.6440$ | $1.3983$ | $0.3983$ |
| $509$ | $0.7742$ | $1.2462$ | $0.2462$ |
$k=200$ で既に $\varepsilon=\frac12$ の範囲に入っている。$k=509$ で同じ点を符号の行列(thm-jl-sign)で写すと、範囲は $[0.7698,\,1.2908]$ であった。
図: 横軸は距離の2乗の比、縦軸は密度。k が 50、200、509 の3本のヒストグラムで、いずれも1を中心とし、k が大きいほど幅が狭くなる。k が 509 ではほぼ 0.8 から 1.25 の間に収まり、0.5 と 1.5 の補助線の内側にある
$X$ が $0$ を含み、$f$ が $X$ 上で $\varepsilon$ 近似等長、$f(0)=0$ とする(1 次写像なら自動的に $f(0)=0$)。$x,y\in X$ について、内積をノルムで書く式 $\langle a,b\rangle=\frac12\bigl(\|a\|^2+\|b\|^2-\|a-b\|^2\bigr)$ を $a=x,b=y$ と $a=f(x),b=f(y)$ に使うと、各項の誤差は $\varepsilon$ 倍以内なので
$$
\bigl|\langle f(x),f(y)\rangle-\langle x,y\rangle\bigr|\le\frac\varepsilon2\bigl(\|x\|^2+\|y\|^2+\|x-y\|^2\bigr)
$$
である。$x,y$ が単位ベクトルなら右辺は $3\varepsilon$ 以下である。角度の情報(たとえば $\langle x,y\rangle$ の符号)は、$\langle x,y\rangle$ の大きさが $3\varepsilon$ より大きいときに保たれる。
$N=10^6$、$\varepsilon=\frac12$ とする。prop-jl-lower の集合 $X$($10^6+1$ 点)では、$k\ge\log(10^6)/1.2382\approx11.16$、すなわち $k\ge12$ が必要である。一方 cor-jl-existence は $k\ge24\log(10^6+1)/0.25\approx1326.3$、すなわち $k=1327$ で足りることを保証する。どちらも $\log N$ に比例し、比は定数($\varepsilon$ による)にとどまる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $k$ が $\log N$ の定数倍以上 | $X=\{0,e_1,\dots,e_N\}$、$\varepsilon=\frac12$、$k< \log N/1.2382$ | どんな写像(1 次でなくても)も $\varepsilon$ 近似等長にならない(prop-jl-lower) |
| 行列の行が独立 | すべての行を同じ $a/\sqrt k$($a$ の成分は独立な標準正規分布)にする | $\Vert Au\Vert^2=\langle a,u\rangle^2$ なので、$X=\{0,u\}$ でも $P(\Vert Au\Vert^2< \frac12\Vert u\Vert^2)=P(Z^2< \frac12)\approx0.5205$ が $k$ によらない。lem-jl-single の評価が成り立たず、$k$ を増やしても失敗の確率が減らない |
| $X$ が有限 | $X=\mathbb{R}^d$、$k< d$、任意の $k\times d$ 行列 $A$ | $\ker A\ne0$ なので、$0\ne u\in\ker A$ の $x=u$、$y=0$ で $\Vert Ax-Ay\Vert=0$ となり、下側の不等式が成り立たない |
2 行目:$Au$ の成分はすべて $\langle a,u\rangle/\sqrt k$ に等しいので $\|Au\|^2=k\cdot\langle a,u\rangle^2/k=\langle a,u\rangle^2$ で、$Z:=\langle a,u\rangle/\|u\|$ は標準正規分布に従う。$P(Z^2< \frac12)=P(|Z|< 0.7071)\approx0.5205$ である。$\varepsilon=\frac12$ の下側の条件 $\|Au\|^2\ge\frac12\|u\|^2$ がこの確率で満たされない。仮定のうち外したのは行の独立性だけで、各成分の分布は $N(0,1/k)$ のままである。3 行目:$X$ が無限集合になったことだけが違い、$A$ が Gauss 行列でもどんな行列でも同じである。無限集合については、次元を集合の「Gauss 幅」で測る別の形の定理がある(Ver18 §9.3)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する