You think you know three dimensional space but you don't. You are really familiar with two dimensions.
상태 공간은 고차원 공간으로 표현되는 때가 많다. 이런 공간의 광활함과 비직관적인 성질에 어느 정도 익숙해질 필요가 있다.
구는 특정 점으로부터 같은 거리에 있는 모든 점의 집합이다. 이를 그대로 $n$-차원 공간으로 확장할 수 있다.
$$\{x : |x| = r\}$$
반지름이 $r$인 2차원 상의 구를 상상해보자. 우리는 2차원 상의 구를 원이라 부르며 부피(면적)는 $\pi r^2$이다. 익숙한 3차원 공간에서 구의 부피는 $\frac{4}{3} \pi r^3$이다. 이를 계속해서 $n$-차원으로 확장하면 $C_n r^n$임을 쉽게 유추할 수 있다. 그렇다면 그 상수 $C_n$은 어떻게 될까? 놀랍게도 이는 $n = 2k$일 때 $\frac{\pi^{k}}{k!}$이다. 즉, $n$이 충분히 크면 $C_n$이 0으로 수렴하며 결과적으로 구의 부피가 0으로 수렴한다.
구의 표면적을 생각해보자. 이는 구의 부피로부터 그보다 약간 작은 구의 부피를 빼면 근사할 수 있다. 편의상 $r = 1$이라고 가정하자 그러면,
$$C_n 1^n - C_n (1 - \epsilon)^n = C_n (1 - (1 - \epsilon)^n)$$
여기서 $n$이 커지면 뒤쪽의 항은 0으로 수렴해버리고 결과적으로 표면적이 부피와 같아진다. 즉, 고차원 공간에서의 구의 부피는 거의 모두 표면에 위치한다.
$n$-차원 구에 대한 논의는 spherical Gaussian 분포의 논의와 밀접한 관련이 있다. Spherical Gaussian 분포는 평균이 0이고 각 축으로 표준편차가 $\sigma$인 $n$-차원 정규분포이다. 이를 상상해보면 $n$-차원 공간에 놓인 구체가 반지름이 점차 커지면서 해당 표면에 부여된 확률 밀도가 점점 감소하는 것을 떠올릴 수 있다. 위에서 논의한 $n$-차원 구의 성질 때문에 충분한 확률 질량을 확보하기 위해서는 일정 수준까지 반지름 $r$이 커져야 하며 그 이후로는 확률 밀도가 감소하는 속도가 반지름 증가에 의한 부피 증가 속도를 앞질러 버린다.
그러므로 위의 분포에서 가장 큰 밀도를 지닌 점은 평균인 원점이지만 실제로는 원점으로부터 $\sqrt{n}$ 정도 떨어진 지점에서 표본이 추출된다. 이를 간단한 시뮬레이션을 통해 확인해보는 것도 좋다.
In [1]: import numpy as np
In [2]: dim = 1000
In [3]: size = 10
In [4]: v = [np.random.normal(size=dim) for k in range(size)]
In [5]: print(np.sqrt(dim))
31.6227766017
In [6]: [np.sqrt(np.sum(k ** 2)) for k in v]
Out[6]:
[31.048656079409412,
31.791238619516246,
31.893193058942515,
32.267924269693715,
31.823568666268624,
31.265678954796723,
32.024040632686059,
31.181243466197895,
31.724294179361738,
31.781046741585481]
이러한 성질 외에도 위의 분포로부터 추출한 표본은 서로 거의 직각을 이루며 각각의 거리도 같다.
In [7]: [np.sqrt(np.sum((v[0] - k) ** 2)) for k in v[1:]]
Out[7]:
[44.297032775314207,
44.807063569681482,
45.134884518578616,
45.532786997937116,
44.452670287417483,
44.636222021733829,
44.184540845285674,
45.095838152268769,
45.674720360620142]
In [8]: [np.dot(v[0], k) / (np.sqrt(np.sum(v[0] ** 2)) * np.sqrt(np.sum(k ** 2))) for k in v[1:]]
Out[8]:
[0.006319064733127943,
-0.013369545251693395,
-0.015930030059339208,
-0.04882004425907488,
-0.017758388414798723,
-0.0014251653590260835,
-0.00825538258660094,
-0.032073576074933066,
-0.05681535589795432]
이는 특히 신경 쓰이는 부분이다. 많은 분류 기법은 두 점 사이의 유사성을 비교하며 동작하는데 $n$-차원 공간은 애초에 너무 넓고 비직관적인 성질을 갖고 있으므로 이런 접근이 쉽지 않다. 이와 같은 고차원 공간의 특성 때문에 curse of dimensionality라는 이야기를 하게 된다.
단순히 수학적인 흥미를 위해 위의 논의를 한 것은 아니다. 하나의 예로 Shannon이 정보 이론을 만들며 노이즈와 시그널의 전송과 관련된 성질을 증명할 때에 $n$-차원 공간의 성질이 활용하였다. 여기에서는 위의 spherical Gaussian의 성질을 바탕으로 증명된 Johnson-Lindenstrauss 정리를 소개한다.
Random projection은 아래의 사상을 의미한다.
평균이 0 표준편차가 1인 정규분포로부터 $n$개의 표본을 추출한다. 이를 모아 하나의 벡터로 만든다.
$\mathbf{u}_i = (u_{i1}, \ldots, u_{in})$
이런 벡터를 $k$개 만든다.
$(\mathbf{u}_1, \ldots, \mathbf{u}_k)$
이제 어떤 $n$-차원 벡터 $\mathbf{v}$가 주어지면 이를 $k$-차원으로 변환하는 아래의 사상을 생각한다.
$f(\mathbf{v}) = (\mathbf{u}_1 \cdot \mathbf{v}, \ldots, \mathbf{u}_k \cdot \mathbf{v})$
이렇게 사상된 $f(\mathbf{v})$의 크기는 거의 확실하게 $\sqrt{k} |\mathbf{v}|$가 된다. 이에 대한 증명은 아래와 같다.
우선 편의상 $\mathbf{v}$의 크기가 1이라고 가정하자. 이는 나중에 다시 크기를 곱해주면 원래의 크기로 돌아갈 수 있다.
$\mathbf{u}_i \cdot \mathbf{v} = u_{i1} v_1 + u_{i2} v_2 + \cdots + u_{in} v_n$
여기에서 $v_1, \ldots, v_n$은 이미 주어진 것이므로 상수라고 생각할 수 있다. 그리고 $u_{ij}$는 평균이 0, 표준편차가 1인 정규분포로 나온 표본이다. $\mathbf{u}_i \cdot \mathbf{v}$는 정규분포의 선형결합으로 이루어져 있으므로 이 또한 정규분포를 따른다. 그 평균과 분산을 계산해보면 아래와 같다.
\begin{align} E[\mathbf{u}_i \mathbf{v}] & = E[u_{i1} v_1 + u_{i2} v_2 + \cdots + u_{in} v_n] \\ & = E[u_{i1} v_1] + E[u_{i2} v_2] + \cdots + E[u_{in} v_n] \\ & = v_1 E[u_{i1}] + v_2 E[u_{i2}] + \cdots + v_n E[u_{in}] \\ & = v_1 \times 0 + v_2 \times 0 + \cdots + v_n \times 0 \\ & = 0 \end{align}
그러므로 $\mathbf{u}_i \cdot \mathbf{v}$의 평균은 0이다.
\begin{align} Var[\mathbf{u}_i \mathbf{v}] & = Var[u_{i1} v_1 + u_{i2} v_2 + \cdots + u_{in} v_n] \\ & = Var[u_{i1} v_1] + Var[u_{i2} v_2] + \cdots + Var[u_{in} v_n] \\ & = v_1^2 Var[u_{i1}] + v_2^2 Var[u_{i2}] + \cdots + v_n^2 Var[u_{in}] \\ & = v_1^2 + v_2^2 + \cdots + v_n^2 \\ & = |\mathbf{v}|^2 \\ & = 1 \end{align}
위의 분산 계산에서는 $u_{ij}$가 서로 독립이라는 것과 $\mathbf{v}$의 크기가 1임을 활용하였다.
이제 우리는 $f(\mathbf{v})$가 평균이 0이고 분산이 1인 $k$-차원 정규분포로부터 뽑힌 표본이라고 생각할 수 있고 위의 spherical Gaussian의 논의로부터 그 크기가 거의 확실하게 $\sqrt{k}$임을 알 수 있다.
이를 활용하여 Johnson-Lindenstrauss 정리를 이야기해보자. JL lemma에 따르면 $n$-차원 공간의 두 점 사이의 거리는 위의 random projection을 통해 $k$-차원으로 변환한 점 사이의 거리를 활용하여도 무방하다.
이는 단순히 $\mathbf{v}_i$와 $\mathbf{v}_j$의 거리인 $\mathbf{v}_i - \mathbf{v}_j$에 $f()$를 적용하면 된다.
$$f(\mathbf{v}_i - \mathbf{v}_j) \approx \sqrt{k} |\mathbf{v}_i - \mathbf{v}_j|$$
다시 이야기해보면 위의 정리는 점과 점 사이의 거리가 random projection을 통해 일정 수준의 저차원으로 떨어뜨려도 거리 관계가 달라지지 않음을 보장한다. 그러므로 거리 기반의 모델은 적당히 차원을 축소한 데이터를 활용해도 무방함을 보장해준다.
고차원 공간에 대한 조금 더 엄밀한 논의는 John Hopcroft와 Ravindran Kannan의 Foundations of Data Science의 2장을 살펴보기 바란다. 고차원 공간과 현실의 관계에 대해 논한 것은 Richard Hamming의 Learning to Learn 강의의 9강을 살펴보기 바란다. 말머리에 있는 따옴 글도 해당 강연에서 발췌한 것이다.