@Lawasintegrity
前提知識
線形代数、確率論
前書き
高次元上の点を低次元へ埋め込むことを考えます。つまり、データを圧縮することを考えます。このとき、保存量を持って圧縮したいです。何を保存するのかというと、2乗距離であるとします。つまり、変換写像を$f:\mathbb{R}^d \to \mathbb{R}^k (d>k)$としたとき、異なる2点$\bm{x}_i,\bm{x}_j \in \mathbb{R}^d$について
$$\|f(\bm{x}_i)-f(\bm{x}_j)\|_2 \approx \|\bm{x}_i-\bm{x}_j\|_2$$が成り立ってくれれば嬉しいです。
今、$\pm \epsilon$くらいのズレを許すことにします。このような場合を$\epsilon$-isometryといいます。
今回の興味は、どのような状況であるなら、このような埋め込みが可能かどうかというものです。
簡単な例を考えてみましょう。2次元上の3点を考えてみます。もしこの3点が同一直線上にあるならば、回転するだけでお互いの2乗距離を保ったまま、1次元に埋め込むことが可能です。しかし、任意の3点については、1次元に埋め込むことはできません。想像してみてください。
ここで言いたいことは、1次元では、2次元の3点以上の点の持つ情報を保存することができないということです。逆に、1次元の3点たちから、2次元以上に埋め込もうとすると追加の情報を要します。
このような議論から、今回の興味の動機が見えてくると思います。情報理論的な話に関連させた話題として、Johnson-Lindenstraussの補題があります。ここではこれを紹介します。
Johnson-Lindenstraussの補題
任意の$\epsilon \in [0,1]$を考えます。また、$\mathbb{R}^d$上の$n$個の点を考えます。これらに対して、自然数$k$を
$$k \geq \frac{8}{\epsilon^2-\epsilon^3}\log n$$と設定します。
$n$個の点の集合を$P \subset \mathbb{R}^d$と書きます。このとき、写像$f:\mathbb{R}^d \to \mathbb{R}^k$で、任意の2点$\bm{x}_i,\bm{x}_j \in P$について
を満たす$f$が存在します。さらに、この$f$はRP (randomized polynomial time)で構成することができます。
コメント
埋め込める次元$k$には条件があることに注意してください。例でみたように、どんなものでも埋め込める訳ではありません。
ただ、条件には元の次元$d$は含まれておらず、点の数に依存しています。
行列$\bm{A} \in \mathbb{R}^{k \times d}$で、各成分$A_{ij}$がi.i.d.に$N(0,1)$に従っているような
行列を考えます。実はこれが条件を満たす写像で、ランダムに生成した射影なので、ランダム射影と呼びます。
証明の前半
$\bm{u} \in \mathbb{R}^d$に対して、$\bm{v} = \frac{1}{\sqrt{k}} \bm{A} \bm{u} \in \mathbb{R}^k$を定めます。
このとき、
が成立しています。これは簡単な計算からわかります。
$$\begin{aligned} \mathrm{E}[\|\bm{v}\|_2^2] &= \sum_{i=1}^k \mathrm{E}[v_i^2] \\ &=\sum_{i=1}^k \mathrm{E}[\frac{1}{k}(\sum_{j=1}^d A_{ij}u_j)^2] \\ &=\sum_{j=1}^d u_j^2 \\ &=\|\bm{u}\|_2^2 \end{aligned}$$となります。次に補題を挟みます。
補題
今の設定で、
$$ \mathrm{Pr} \left[\|\bm{v}\|_2^2 \geq (1+\epsilon)\|\bm{u}\|_2^2 \right] \leq\frac{1}{n^2}$$が成り立っています。
補題の証明
まず、$v_i \sim N(0,\frac{1}{k} \| \bm{u} \|_2^2)$です。$x_i=\frac{\sqrt{k}}{\| \bm{u} \|_2}v_i$とします。このとき、当然$x_i \sim N(0,1)$です。
$$ \begin{aligned} \mathrm{Pr} \left[\|\bm{v}\|_2^2 \geq (1+\epsilon)\|\bm{u}\|_2^2 \right]&= \mathrm{Pr} \left[\frac{\| \bm{u} \|_2^2}{k}\|\bm{x}\|_2^2 \geq (1+\epsilon)\|\bm{u}\|_2^2 \right] \\ &=\mathrm{Pr} \left[\|\bm{x}\|_2^2 \geq (1+\epsilon)k \right] \end{aligned}$$ここで、Chernoff boundを考えます。つまり、$\lambda>0$について、
$$\begin{aligned} \mathrm{Pr} \left[\|\bm{x}\|_2^2 \geq (1+\epsilon)k \right] &=\mathrm{Pr} \left[ \mathrm{e}^{\lambda \|\bm{x}\|_2^2} \geq \mathrm{e}^{\lambda (1+\epsilon)k} \right] \\ &\leq \frac{1}{\mathrm{e}^{\lambda (1+\epsilon)k}} \mathrm{E}\left[\mathrm{e}^{\lambda \|\bm{x}\|_2^2} \right] \end{aligned}$$となります。$\mathrm{E}\left[\mathrm{e}^{\lambda \|\bm{x}\|_2^2} \right]$は$\chi^2$分布のモーメント母関数を考えればよく、
$$ \frac{1}{\mathrm{e}^{\lambda (1+\epsilon)k}} \mathrm{E}\left[\mathrm{e}^{\lambda \|\bm{x}\|_2^2} \right]=\frac{1}{\mathrm{e}^{\lambda (1+\epsilon)k}} \left( \frac{1}{1-2 \lambda} \right) ^{\frac{k}{2}}$$となります。さらに、$\lambda=\frac{\epsilon}{2(1+\epsilon)}$とすると、
$$ \begin{aligned} \mathrm{Pr} \left[\|\bm{v}\|_2^2 \geq (1+\epsilon)\|\bm{u}\|_2^2 \right]& \leq \frac{1}{\mathrm{e}^{\frac{\epsilon}{2}k}} \left( 1+\epsilon \right)^{\frac{k}{2}} \\ &=\left( (1+\epsilon) \mathrm{e}^{-\epsilon}\right)^{\frac{k}{2}} \end{aligned}$$と書けます。大体、$(1+\epsilon) \leq \mathrm{e}^{\epsilon - \frac{\epsilon^2-\epsilon^3}{2}}$くらいから、
$$ \mathrm{Pr} \left[\|\bm{v}\|_2^2 \geq (1+\epsilon)\|\bm{u}\|_2^2 \right] \leq \mathrm{e}^{-\frac{k}{4}(\epsilon^2-\epsilon^3)}$$を得ます。$k$の条件は、
$$k \geq \frac{8}{\epsilon^2-\epsilon^3}\log n$$だったので、
$$ \mathrm{Pr} \left[\|\bm{v}\|_2^2 \geq (1+\epsilon)\|\bm{u}\|_2^2 \right] \leq \mathrm{e}^{-2\log n}=\frac{1}{n^2}$$が最終的に得られます。
証明の後半
補題から、同様に考えると、
$$ \mathrm{Pr} \left[\|\bm{v}\|_2^2 \leq (1-\epsilon)\|\bm{u}\|_2^2 \right] \leq\frac{1}{n^2}$$というboundも得ることができます。これら2つを用いると、
$$\|\bm{v}\|_2^2 \geq (1+\epsilon)\|\bm{u}\|_2^2または\|\bm{v}\|_2^2 \leq (1-\epsilon)\|\bm{u}\|_2^2 が成立している.$$という事象を$\mathcal{A}$と書くと、
$$ \mathrm{Pr} \left[ \mathcal{A} \right] \leq\frac{2}{n^2}$$であることがわかります。また、各$\bm{u}$を$\bm{u}=\bm{x}_i-\bm{x}_j$と$_nC_2$個のペアを考えることにすると、
$$\begin{aligned} \mathrm{Pr} \left[_nC_2個 のうち、ある\bm{u}で\mathcal{A}が成立 \right] &\leq \sum_{全てのペア}\mathrm{Pr} \left[そのペアで、\mathcal{A}が成立 \right] \\ & \leq \frac{n(n-1)}{2} \frac{2}{n^2} \\ &=1-\frac{1}{n} \end{aligned}$$が得られる。結局、
$$ \begin{aligned} \mathrm{Pr} \left[_nC_2個 のうち、どの\bm{u}でも\mathcal{A}が起きない \right] &=1-\mathrm{Pr} \left[_nC_2個 のうち、ある\bm{u}で\mathcal{A}が成立 \right] \\ & \geq 1- \left(1-\frac{1}{n} \right) \\ &= \frac{1}{n} \end{aligned}$$この結果より、失敗の事象$\mathcal{A}$が全く起きない確率が少なくとも$\frac{1}{n}$は存在しています。よって、Johnson-Lindenstraussの補題の1つ目の主張である、存在性を言うことができました。さらに、確率は$\frac{1}{n}$なので、$O(n)$くらい試行を繰り返せば定数確率で結果を得られると言っているので、RPで構成できることがわかります。
コメント
エラーする確率が$n^{-2}$のオーダーくらいで抑えられるというのがミソでした。証明も簡単です。実は、正規分布ではなくても、例えばベルヌーイ分布から作ったランダム行列でも構成できます。このような低次元に削減するような議論は、他に主成分分析などがあると思いますが、それらとは別のものだと思っています。このようなランダム行列を用いた高次元空間の議論は圧縮センシングの話に繋がっています。
