Random Projection

入力を$\bm{u} \in \mathbb{R}^d$とする．$dk$個のi.i.d.な確率変数$\{R_{i, j}\}_{i=1, j=1}^{d, k} \overset{i.i.d}{\sim} \mathcal{N}(0, 1)$を用意する．そして，これらを成分に持つ行列$\bm{R} \in \mathbb{R}^{d \times k}$を 作る．$\bm{R}$を用いて，入力$\bm{u}$を$k$次元空間に$\bm{v} = \frac{1}{\sqrt{k}} \bm{R}^T \bm{u}$と射影する．この時，$\mathbb{E}\left[\|\bm{v}\|^2\right] = \|\bm{u}\|^2$が成り立つ．これを示す．

$\begin{aligned} \mathbb{E}\left[v_j^2\right] &= \mathbb{E}\left[\left(\frac{1}{\sqrt{k}} \sum_{j=1}^d R_{j, i} u_j\right)^2\right] \\ &= \frac{1}{k} \mathbb{E}\left[\left(\sum_{j=1}^d R_{j, i} u_j\right)^2\right] \\ &= \frac{1}{k} \mathbb{E}\left[\sum_{j=1}^d \sum_{k=1}^d R_{j, i} R_{k, i} u_j u_k\right] \\ &= \frac{1}{k} \sum_{j=1}^d \sum_{k=1}^d \mathbb{E}\left[R_{j, i} R_{k, i}\right] u_j u_k \\ &= \frac{1}{k} \sum_{j=1}^d \left(\mathbb{E}\left[R_{j, i}^2\right] u_j^2 + \sum_{k \neq j}^d \mathbb{E}\left[R_{j, i} R_{k, i}\right] u_j u_k \right)\\ &= \frac{1}{k} \sum_{j=1}^d \left(\mathbb{E}\left[R_{j, i}^2\right] u_j^2 + \sum_{k \neq j}^d \mathbb{E}\left[R_{j, i}\right] \mathbb{E}\left[R_{k, i}\right] u_j u_k \right)\\ &= \frac{1}{k} \sum_{j=1}^d \mathbb{E}\left[R_{j, i}^2\right] u_j^2 \\ &= \frac{1}{k} \sum_{j=1}^d u_j^2 \\ &= \frac{1}{k} \|\bm{u}\|^2 \\ \end{aligned}$

よって，$\mathbb{E}\left[\|\bm{v}\|^2\right] = \|\bm{u}\|^2$．
大数の法則を考えると，$k$を増やせば（$d$は増やせない），$\|\bm{v}\|^2$は$\|\bm{u}\|^2$に近づいていきそう．ちょっとやってみよう．以下のようなコードで実験してみた．

import numpy as np
import numpy.linalg as la
import matplotlib.pyplot as plt

random_state = 0
rnd = np.random.RandomState(random_state)

d = 8
u = rnd.multivariate_normal(np.zeros(d), np.identity(d))

ks = 2 ** np.arange(1, 10)
norms = np.zeros_like(ks)
for i, k in enumerate(ks):
    rnd = np.random.RandomState(random_state)
    R = rnd.normal(0, 1, size=(d, k))
    v = R.T.dot(u) / np.sqrt(k)
    norms[i] = la.norm(v) ** 2

plt.plot(ks, norms)
plt.plot(ks, np.repeat(la.norm(u) ** 2, len(ks)))
plt.xlabel('$k$')
plt.ylabel('norm')

結果は以下のようになった．予想通り，$k$を増やすと$\|\bm{u}\|^2$に近づいている．これで$k$を増やせばノルムを近似できるだろう．現実的には$k$は$d$よりもずっと小さな値にしなければならない．続きは次回．

参考:

• http://www.cs.wichita.edu/~sinha/teaching/spring15/cs898aj/random_projection.pdf

Written with StackEdit.