고차원에서 직관이 무너지는 지점: 거리 집중과 부피 쏠림

임베딩 모델의 출력 차원을 보면 768이나 1024, 큰 것은 3072입니다. 그 벡터들을 벡터 데이터베이스에 넣고 코사인 유사도로 가장 가까운 것을 찾습니다. 우리는 이 절차를 3차원 공간에서 가까운 점을 찾는 일의 확장으로 상상합니다 — 점들이 흩어져 있고, 질의 근처에 몇 개가 모여 있고, 나머지는 멀리 있다는 그림입니다.

그 그림은 1024차원에서 거의 다 틀립니다. 부피는 가운데가 아니라 껍질에 있고, 아무 두 벡터나 뽑으면 거의 항상 직교에 가깝고, 「가장 가까운 점」과 「가장 먼 점」의 거리가 별로 다르지 않습니다. 그리고 어떤 질의를 넣어도 같은 문서 몇 개가 상위에 뜨는 이상한 일이 벌어집니다.

지난 글까지는 생성 모델의 수학을 다뤘습니다. 이 글부터 몇 편은 검색 쪽입니다. 먼저 이 공간이 어떻게 생겼는지부터 정리해야 왜 근사 검색이 통하고 어디서 안 통하는지를 말할 수 있습니다.

껍질로 쏠리는 부피

껍질의 부피

$d$ 차원에서 반지름 $r$ 인 공의 부피는 $V_d r^d$ 입니다. $V_d$ 는 반지름 1일 때의 값이고 $r^d$ 만 반지름에 따라 변합니다. 반지름 $1-\epsilon$ 과 1 사이의 얇은 층을 껍질이라고 부르면, 껍질 안쪽 공이 차지하는 비율은 이렇습니다.

$$\frac{V_d (1-\epsilon)^d}{V_d \cdot 1^d} = (1-\epsilon)^d$$

간단한 식인데 $d$ 가 커지면 거칠게 움직입니다.

$d$	안쪽 90% 반지름이 갖는 부피	안쪽 99% 반지름이 갖는 부피
2	0.810	0.980
3	0.729	0.970
10	0.349	0.904
100	0.000027	0.366
1000	$10^{-46}$	0.000043

3차원에서는 바깥 10% 껍질에 부피의 27%가 있습니다. 1000차원에서는 바깥 1% 껍질에 99.996%가 있습니다. 「공의 안쪽」이라고 부를 만한 곳에는 사실상 아무것도 없습니다.

공 안에서 균등하게 점을 뽑았을 때 중심에서의 거리 $r$ 의 기댓값도 같은 이야기를 합니다. 반지름 $r$ 에 있는 얇은 층의 부피가 $r^{d-1}$ 에 비례하므로 밀도도 그렇고,

$$\mathbb{E}[r] = \frac{\int_0^1 r \cdot r^{d-1} dr}{\int_0^1 r^{d-1} dr} = \frac{d}{d+1}$$

입니다. $d = 100$ 이면 0.990, $d = 1000$ 이면 0.999입니다. 뽑은 점은 거의 항상 표면 바로 아래에 있습니다.

단위 공의 부피

한 가지 더 있습니다. 반지름 1인 공의 부피 $V_d$ 자체는 차원에 따라 커지다가 줄어듭니다.

$d$	3	5	7	10	20	50	100
$V_d$	4.19	5.26	4.72	2.55	0.026	$1.7 \times 10^{-13}$	$2.4 \times 10^{-40}$

5차원에서 최대가 되고 그 뒤로는 0을 향해 갑니다. 그 공을 꼭 맞게 감싸는 정육면체, 곧 각 좌표가 −1에서 1 사이인 상자의 부피는 $2^d$ 로 폭발하는데 그 안에 든 공은 사라진다는 뜻입니다. 10차원에서 이미 공이 상자의 $2.55 / 1024$, 곧 0.25%만 차지합니다. 나머지 99.75%는 공 밖, 상자의 모서리 쪽에 있습니다.

이 두 사실은 같은 말을 합니다. 고차원에서 부피는 중심에서 먼 곳에 삽니다 — 공 안에서는 표면 바로 아래에, 상자 안에서는 모서리 근처에. 3차원에서 기른 「대부분은 가운데에 있다」는 감각이 첫 번째로 무너지는 자리입니다.

측도 집중

이번에는 공의 속이 아니라 겉면, 곧 반지름 1인 구면 위에서 균등하게 점을 뽑아 보겠습니다. 첫 좌표 $x_1 = 1$ 인 곳을 북극, $x_1 = -1$ 인 곳을 남극이라 부르고, 그 한가운데를 두르는 $|x_1| < 0.1$ 인 영역을 적도 띠라고 부르겠습니다. 띠의 폭은 지름의 10%로 고정해 두고 차원만 올립니다. 구면 위 점의 첫 좌표 분포에서 정확히 계산한 값입니다.

$d$	3	10	100	1000
적도 띠가 갖는 겉넓이	10.0%	23.0%	68.0%	99.85%

3차원의 10%는 아르키메데스가 이미 알던 값입니다. 구면을 평행한 두 평면으로 자르면 그 사이 넓이는 두 평면의 간격에만 비례하므로, 지름 2 가운데 0.2를 잘라 낸 띠는 정확히 10%를 갖습니다. 그런데 1000차원에서는 같은 폭의 띠가 겉넓이의 99.85%를 갖습니다. 구면 위의 점은 거의 전부 적도에 있습니다.

띠의 폭을 차원에 맞춰 잡으면 더 깔끔해집니다. 구면 위 점은 좌표 제곱의 합이 1이고 좌표들 사이에 차별이 없으므로 $\mathbb{E}[x_1^2] = 1/d$ 입니다. 그래서 $x_1$ 은 표준편차 $1/\sqrt{d}$ 로 0 주위에 모이고, $|x_1| < 2/\sqrt{d}$ 인 띠가 $d = 10$ 에서 96.3%, $d = 100$ 과 $d = 1000$ 에서 95.5%를 갖습니다. 정규분포에서 평균 ±2 표준편차 안이 95%인 것과 같은 숫자입니다. 북극을 어디로 잡든 결론은 같습니다 — 아무 방향이나 하나 고르면, 그 방향에 수직인 폭 $1/\sqrt{d}$ 남짓한 띠 안에 넓이의 대부분이 담깁니다.

이처럼 고차원에서 넓이나 확률(수학에서는 둘을 묶어 측도라고 부릅니다)이 좁은 영역 하나에 몰리는 현상을 측도 집중이라고 합니다. 적도 띠는 그 가장 단순한 예이고, 더 일반적으로는 구면 위의 매끄러운 함수가 거의 모든 점에서 제 평균 근처 값을 갖는다는 정리로 이어집니다.

껍질과 적도

부피가 껍질에 몰리는 것과 넓이가 적도에 몰리는 것은 따로 노는 두 사실이 아닙니다. 표준정규분포에서 뽑은 $d$ 차원 벡터 하나를 생각하면 둘이 한 번에 보입니다. 길이의 제곱은 좌표 제곱 $d$ 개의 합이라 $d$ 근처에 몰리고, 그래서 벡터는 반지름 $\sqrt{d}$ 인 얇은 껍질 위에 있습니다. 방향은 어느 쪽에도 치우치지 않으므로 구면 위에 균등하고, 그래서 아무 고정된 축과 이루는 코사인은 적도 띠에 들어 0 근처입니다.

두 현상을 받치는 계산은 같습니다. 독립인 항 $d$ 개를 더하면 합의 흔들림이 평균에 비해 $1/\sqrt{d}$ 로 줄어든다는 것입니다. 반지름 방향으로 보면 그것이 껍질이고, 각도 방향으로 보면 그것이 적도 띠입니다. 그리고 「고정된 축과의 코사인이 0 근처」라는 말을 그대로 두 무작위 벡터 사이로 옮긴 것이 다음 절의 내용입니다.

무작위 두 벡터의 각도

코사인의 분포

두 번째로 무너지는 직관은 각도입니다. 표준정규분포에서 벡터 두 개를 뽑아 코사인 유사도를 재 보겠습니다.

import numpy as np
rng = np.random.default_rng(0)

for d in [3, 10, 100, 1000]:
    a = rng.standard_normal((100000, d))
    b = rng.standard_normal((100000, d))
    cos = (a*b).sum(1) / (np.linalg.norm(a, axis=1) * np.linalg.norm(b, axis=1))
    print(f"d={d:5d}  표준편차 {cos.std():.4f}  이론 {1/np.sqrt(d):.4f} "
          f" |cos|>0.1 비율 {np.mean(np.abs(cos) > 0.1):.4f}  최댓값 {np.abs(cos).max():.3f}")

d=    3  표준편차 0.5760  이론 0.5774  |cos|>0.1 비율 0.8994  최댓값 1.000
d=   10  표준편차 0.3169  이론 0.3162  |cos|>0.1 비율 0.7720  최댓값 0.969
d=  100  표준편차 0.0998  이론 0.1000  |cos|>0.1 비율 0.3201  최댓값 0.413
d= 1000  표준편차 0.0317  이론 0.0316  |cos|>0.1 비율 0.0017  최댓값 0.135

표준편차가 $1/\sqrt{d}$ 를 따릅니다. 이유는 앞 절의 적도 띠 그대로입니다. 한 벡터를 북극에 맞춰 놓으면 코사인은 다른 벡터의 첫 좌표를 길이로 나눈 값 $b_1/\|b\|$ 이고, 분자의 분산은 1, 분모는 $\sqrt{d}$ 근처에 몰려 있으므로 비의 표준편차가 $1/\sqrt{d}$ 가 됩니다. 표의 $|\cos| > 0.1$ 비율을 1에서 빼면 앞 절 적도 띠의 넓이와 같은 값이 나옵니다(1000차원에서 $1 - 0.0017$).

1000차원에서 10만 쌍을 뽑았더니 코사인의 절댓값이 0.1을 넘은 쌍이 0.17%뿐이었고, 가장 큰 값도 0.135였습니다. 아무 관계 없는 두 벡터의 코사인은 0.1을 넘기 어렵다는 말입니다.

거의 직교하는 방향

이건 좋은 소식이기도 합니다. 관계 없는 것들이 자동으로 서로 멀어져 있으니, 1000차원 공간에는 거의 직교하는 방향을 아주 많이 담을 수 있습니다. 정확히 직교하는 방향은 $d$ 개뿐이지만, 「코사인 0.1 이하」로 조건을 느슨하게 하면 차원에 지수적으로 많은 방향이 들어갑니다. 무작위로 방향을 계속 뽑아도 새 방향이 기존 방향들과 거의 부딪히지 않기 때문입니다.

임베딩이 수만 가지 개념을 서로 겹치지 않게 담을 수 있는 이유가 이것입니다. 「고양이」와 「세금」과 「양자역학」에 각자의 방향을 하나씩 주어도 그 방향들끼리의 코사인은 0 근처에 머물고, 한 개념을 조금 움직여도 다른 개념의 좌표를 건드리지 않습니다. 대신 그 대가로, 뒤에서 볼 것처럼 「조금 비슷함」과 「전혀 무관함」 사이의 간격이 좁아집니다.

정규화와 거리 순위

벡터 데이터베이스는 대개 코사인, 내적, 유클리드 거리 셋 중 하나를 고르게 합니다. 벡터의 길이를 1로 맞춰 두면 이 셋이 같은 순위를 냅니다. 거리의 제곱을 풀어 보면 바로 보입니다.

$$\|a - b\|^2 = \|a\|^2 + \|b\|^2 - 2\, a \cdot b = 2 - 2\cos\theta$$

두 벡터가 모두 길이 1이면 $\|a\|^2 = \|b\|^2 = 1$ 이고 내적은 곧 코사인이므로 마지막 등호가 성립합니다. 거리의 제곱이 코사인의 감소함수이니, 코사인이 큰 순서와 거리가 작은 순서는 정확히 같습니다. 순위만 쓰는 최근접 검색에서는 셋 중 무엇을 골라도 결과가 한 글자도 다르지 않습니다. 여러 임베딩 API가 길이 1로 맞춘 벡터를 돌려주는 것도 이 편의 때문입니다.

노름과 내적 순위

정규화하지 않으면 사정이 달라집니다. 내적은 $a \cdot b = \|a\|\|b\|\cos\theta$ 라서 질의가 같을 때 문서 벡터의 길이, 곧 노름이 그대로 곱해집니다. 고차원에서 무관한 쌍의 코사인은 $1/\sqrt{d}$ 폭 안에서만 움직이므로, 노름이 몇 배씩 차이 나면 각도의 차이가 노름의 차이에 묻힙니다.

rng_a = np.random.default_rng(1)       # 앞뒤 코드의 rng와 따로 둔다
d, n = 100, 10000
dirs = rng_a.standard_normal((n, d))
dirs /= np.linalg.norm(dirs, axis=1, keepdims=True)
norms = rng_a.lognormal(0, 0.5, n)            # 길이가 제각각인 벡터
X = dirs * norms[:, None]
big = norms > np.quantile(norms, 0.9)       # 길이 상위 10%

same, from_big = [], []
for _ in range(200):
    q = rng_a.standard_normal(d); q /= np.linalg.norm(q)
    top_cos = np.argsort(-(dirs @ q))[:10]
    top_ip = np.argsort(-(X @ q))[:10]
    same.append(len(set(top_cos) & set(top_ip)))
    from_big.append(big[top_ip].mean())
print(f"코사인 상위 10과 내적 상위 10의 겹침  {np.mean(same):.2f}개")
print(f"내적 상위 10 중 길이 상위 10% 출신   {np.mean(from_big):.1%}")

코사인 상위 10과 내적 상위 10의 겹침  1.10개
내적 상위 10 중 길이 상위 10% 출신   97.4%

질의 200개에 대해 코사인 상위 10개와 내적 상위 10개가 평균 1.1개만 겹쳤습니다. 내적 상위 10개의 97.4%는 길이 상위 10%에 드는 벡터였습니다. 질의가 무엇이든 긴 벡터 몇 개가 목록을 독차지한 것입니다. 유클리드 거리는 반대쪽으로 기웁니다 — $\|x - q\|^2 = \|x\|^2 + 1 - 2\|x\|\cos\theta$ 에서 코사인이 작으면 $\|x\|^2$ 항이 이겨, 짧은 벡터가 앞으로 나옵니다. 길이에 뜻이 담긴 모델이 아니라면 검색 전에 길이를 맞추는 것이 안전합니다.

거리 집중과 상대 대비

최원거리와 최근접

세 번째가 검색에 가장 직접 걸립니다. 질의점 하나와 데이터 $n$ 개를 두고 가장 가까운 점까지의 거리 $d_{\min}$ 과 가장 먼 점까지의 거리 $d_{\max}$ 를 재 봅니다. 아래 코드는 첫 코드의 rng를 이어 씁니다.

for d in [2, 3, 10, 100, 1000]:
    ratios = []
    for _ in range(200):
        X = rng.random((1000, d))
        q = rng.random(d)
        dist = np.linalg.norm(X - q, axis=1)
        ratios.append(dist.max() / dist.min())
    print(f"d={d:5d}  최원거리/최근접 = {np.mean(ratios):.3f}")

d=    2  최원거리/최근접 = 104.530
d=    3  최원거리/최근접 = 23.672
d=   10  최원거리/최근접 =  3.855
d=  100  최원거리/최근접 =  1.436
d= 1000  최원거리/최근접 =  1.119

2차원에서는 가장 먼 점이 가장 가까운 점보다 100배 멀었습니다. 1000차원에서는 12% 더 멀 뿐입니다. 이것을 거리 집중이라고 부릅니다 — 차원이 오르면 모든 점 사이의 거리가 한 값 주위로 몰리는 현상입니다. 앞 절의 측도 집중을 거리라는 함수에 적용한 결과이기도 합니다.

상대 대비

왜 그런지는 분산과 표준오차의 논리 그대로입니다. 두 점 사이의 거리 제곱은 좌표별 차이 제곱을 $d$ 개 더한 것입니다.

$$\|x - q\|^2 = \sum_{i=1}^{d} (x_i - q_i)^2$$

좌표들이 독립이면 이 합의 평균은 $d$ 에 비례해 커지고 표준편차는 $\sqrt{d}$ 에 비례해 커집니다. 그러니 상대적인 흔들림은 이렇게 줄어듭니다.

$$\frac{\text{표준편차}}{\text{평균}} \propto \frac{\sqrt{d}}{d} = \frac{1}{\sqrt{d}}$$

거리의 분포가 평균 주위로 $1/\sqrt{d}$ 속도로 오므라듭니다. 가장 가까운 것과 가장 먼 것이 얼마나 갈리는지를 한 숫자로 재는 값이 상대 대비 $(d_{\max} - d_{\min})/d_{\min}$ 입니다. 0이면 모든 점이 같은 거리에 있다는 뜻이고, 클수록 가까운 것과 먼 것이 뚜렷이 갈립니다.

$d$	2	10	100	1000
상대 대비	149.2	3.11	0.489	0.134

정리해서 적으면 이렇습니다. 좌표가 서로 독립이고 분포가 같을 때, $d \to \infty$ 이면 임의의 $\epsilon > 0$ 에 대해

$$P\left( \frac{d_{\max}}{d_{\min}} \le 1 + \epsilon \right) \to 1$$

입니다. 「거의 확실히 모든 점이 같은 거리에 있다」는 뜻입니다. 여기서 $n$ 은 조건에 들어가지 않는다는 점이 중요합니다 — 점을 더 많이 넣는다고 대비가 살아나지 않습니다. 위 실험에서 $n$ 을 1000에서 10000으로 늘려도 1000차원의 비는 1.120에서 1.144로 올랐을 뿐입니다. 대비를 정하는 것은 데이터의 양이 아니라 차원입니다.

여기까지만 보면 결론은 암울합니다. 「1000차원에서 최근접 이웃 검색은 의미가 없다」가 됩니다. 실제로 이 결과는 그런 제목으로 알려져 있기도 합니다.

격자 색인

거리 집중은 검색 속도를 내는 방법도 바꿔 놓았습니다. 2차원 지도에서 가까운 가게를 찾을 때는 지도를 칸으로 나눠 두고 질의가 떨어진 칸과 그 옆 칸만 뒤지면 됩니다. 공간을 칸으로 쪼개 점을 칸별로 담아 두는 이런 방식을 격자 색인이라고 하고, 축을 번갈아 반으로 가르는 k-d 트리도 같은 계열입니다.

이 방식은 차원에 지수적으로 값을 치릅니다. 축마다 딱 한 번씩만 반으로 잘라도 칸이 $2^d$ 개입니다. $d = 30$ 이면 $2^{30} = 1{,}073{,}741{,}824$, 이미 십억 칸이 넘습니다. 점을 100만 개 넣어도 칸의 0.093%만 차니, 질의가 떨어진 칸은 거의 언제나 비어 있습니다. 그러면 옆 칸을 뒤져야 하는데, 칸 하나에 꼭짓점까지 맞닿은 이웃 칸이 $3^d - 1$ 개라 30차원에서 약 $2 \times 10^{14}$ 개입니다.

더 근본적인 문제는 거리 집중입니다. 트리 색인은 「이 칸의 경계까지 거리가 지금까지 찾은 최근접보다 멀면 그 칸은 건너뛴다」는 가지치기로 빨라지는데, 모든 거리가 한 값 주위로 몰리면 경계까지의 거리와 최근접 거리가 비슷해져 거의 어떤 칸도 건너뛸 수 없습니다. 결국 전수 비교보다 느려집니다. 그래서 고차원 벡터 검색의 색인은 공간을 칸으로 가르는 쪽에서, 점과 점 사이의 거리 자체를 쓰는 쪽으로 옮겨 갔습니다 — 가까운 점끼리 이어 둔 그래프를 따라 걷는 방식(HNSW)이나, 군집 중심과의 거리로 뒤질 군집 몇 개만 고르는 방식(IVF)입니다.

내재 차원

구조 있는 데이터

그럼 왜 실제 벡터 검색은 쓸 만한 결과를 낼까요. 위 실험에는 조건이 하나 숨어 있습니다 — 좌표들이 독립이었다는 것입니다. 각 축에 아무 관계 없는 난수를 채웠으니 데이터에 구조가 없습니다.

실제 임베딩은 그렇지 않습니다. 문장 임베딩 1024개 좌표는 서로 강하게 얽혀 있고, 데이터는 1024차원 전체가 아니라 훨씬 낮은 차원의 얇은 집합 근처에 놓입니다. 그 집합의 차원을 내재 차원이라고 부릅니다 — 데이터를 표현하는 데 실제로 필요한 자유도의 수이고, 벡터에 적힌 좌표 수인 주변 차원과 구별합니다.

주변 차원을 1000으로 고정하고 내재 차원만 바꿔 대비를 재 봤습니다.

d, n = 1000, 2000
contrast = lambda X, q: ((dd := np.linalg.norm(X-q, axis=1)).max() - dd.min()) / dd.min()

X = rng.standard_normal((n, d))                       # 내재 차원도 1000
print("등방 가우시안       ", f"{contrast(X, rng.standard_normal(d)):.3f}")

A = rng.standard_normal((10, d)) / np.sqrt(10)        # 10차원 잠재변수를 펼친 것
print("10차원 잠재변수     ", f"{contrast(rng.standard_normal((n,10)) @ A, rng.standard_normal(10) @ A):.3f}")

centers = rng.standard_normal((20, d)) * 3            # 군집 20개
X = centers[rng.integers(0, 20, n)] + rng.standard_normal((n, d)) * 0.5
print("군집 20개           ", f"{contrast(X, centers[0] + rng.standard_normal(d)*0.5):.3f}")

등방 가우시안        0.149
10차원 잠재변수      4.163
군집 20개            5.759

주변 차원은 셋 다 1000인데 대비는 40배 차이가 납니다.

거리 집중을 정하는 것은 주변 차원이 아니라 내재 차원입니다. 1024차원 임베딩이 실제로는 수십 차원짜리 구조 위에 놓여 있다면, 거리는 그 수십 차원짜리 데이터처럼 행동합니다. 벡터 검색이 되는 이유가 이것입니다.

참여 비율과 TwoNN

내재 차원은 눈으로 볼 수 없으니 재야 합니다. 흔히 쓰는 방법이 둘입니다.

첫째는 데이터 전체가 몇 방향으로 퍼져 있는지를 보는 방법입니다. 평균을 뺀 데이터 행렬의 특잇값 $\sigma_1, \sigma_2, \dots$ 을 구하면 $\sigma_i^2$ 는 $i$ 번째 주축 방향으로 퍼진 분산에 비례합니다. 그 분산들이 몇 방향에 고르게 나뉘어 있는지를 세는 값이 참여 비율입니다.

$$\mathrm{PR} = \frac{\left(\sum_i \sigma_i^2\right)^2}{\sum_i \sigma_i^4}$$

$k$ 방향이 똑같이 퍼져 있고 나머지가 0이면 분자는 $(k s)^2$, 분모는 $k s^2$ 이라 PR은 정확히 $k$ 입니다. 한 방향이 독차지하면 1에 가까워집니다.

둘째는 점 하나의 주변만 보는 방법입니다. 각 점에서 가장 가까운 이웃까지의 거리 $r_1$ 과 두 번째 이웃까지의 거리 $r_2$ 를 재고 그 비 $\mu = r_2 / r_1$ 을 봅니다. 점들이 $m$ 차원 안에 고르게 흩어져 있으면 $\mu$ 가 1보다 클 확률이 $P(\mu > x) = x^{-m}$ 꼴을 따른다는 것이 알려져 있고, 여기서 최대우도로 푼 추정값이 $\hat m = N / \sum_i \ln \mu_i$ 입니다. 두 최근접 거리를 쓴다고 해서 이 방식을 TwoNN이라고 부릅니다.

def participation_ratio(X):
    s = np.linalg.svd(X - X.mean(0), compute_uv=False)
    return (s**2).sum()**2 / (s**4).sum()

def two_nn(X):
    sq = (X**2).sum(1)
    D = np.sqrt(np.maximum(sq[:, None] + sq[None, :] - 2 * X @ X.T, 0))
    np.fill_diagonal(D, np.inf)
    r1, r2 = np.sort(np.partition(D, 2, axis=1)[:, :2], axis=1).T
    return len(r1) / np.log(r2 / r1).sum()

rng = np.random.default_rng(2)
d, n = 1000, 2000
data = {
    "등방 가우시안": rng.standard_normal((n, d)),
    "10차원 잠재변수": rng.standard_normal((n, 10)) @ (rng.standard_normal((10, d)) / np.sqrt(10)),
    "군집 20개": (rng.standard_normal((20, d)) * 3)[rng.integers(0, 20, n)]
                 + rng.standard_normal((n, d)) * 0.5,
}
for name, X in data.items():
    print(f"{name:10s} 참여 비율 {participation_ratio(X):6.1f}   TwoNN {two_nn(X):6.1f}")

G = np.load("glove300_top20k.npy").astype(np.float64)   # GloVe 300차원, 빈도 상위 2만 단어
print(f"{'GloVe 300':10s} 참여 비율 {participation_ratio(G):6.1f}   TwoNN {two_nn(G[:5000]):6.1f}")

등방 가우시안    참여 비율  666.3   TwoNN  186.1
10차원 잠재변수  참여 비율    9.8   TwoNN    9.5
군집 20개     참여 비율   19.5   TwoNN  138.2
GloVe 300  참여 비율  134.0   TwoNN    9.2

10차원 잠재변수에서는 두 방법이 모두 10 근처를 가리킵니다. 등방 가우시안은 참(1000)보다 작게 나오는데, 이유가 서로 다릅니다. 참여 비율은 표본이 2,000개뿐이라 특잇값이 고르게 나오지 않아 줄었고, TwoNN은 높은 차원일수록 이웃 비를 제대로 재는 데 필요한 표본이 기하급수로 늘어 크게 모자랐습니다. 두 방법 모두 수백 차원 이상은 정확히 못 잰다는 뜻입니다.

군집 20개에서 두 값이 크게 갈리는 것이 이 절의 요점입니다. 참여 비율 19.5는 군집 중심 20개가 펼치는 큰 구조를 보고, TwoNN 138.2는 한 군집 안에서 1000개 축으로 고르게 퍼진 잡음을 봅니다. 참여 비율은 멀리서 본 눈금이고 TwoNN은 가까이서 본 눈금입니다. 실제 단어 벡터인 GloVe 300차원에서는 참여 비율이 134.0으로 주변 차원의 45%, TwoNN이 9.2로 3%였습니다. 전체로는 수많은 방향에 퍼져 있지만 이웃끼리 모인 동네 안에서는 열 개 남짓한 방향으로만 움직인다는 것이고, 최근접 검색이 보는 것은 바로 그 동네입니다.

평균 벡터 빼기

실제 임베딩에는 좌표 사이의 얽힘 말고도 흔한 구조가 하나 더 있습니다. 모든 벡터에 같은 성분이 더해져 있어 벡터 전체가 한 방향으로 쏠린 좁은 원뿔 안에 들어가 있는 경우입니다. 이런 모델에서는 아무 관계 없는 문장 둘의 코사인이 0.7~0.8로 나오기도 합니다. 모델마다 정도가 다르고, 우리가 받은 GloVe는 무작위 단어 쌍의 평균 코사인이 0.031로 이 쏠림이 거의 없었습니다. 그래서 공통 성분을 일부러 넣은 데이터로 원리만 확인해 보겠습니다.

rng = np.random.default_rng(3)
d, n = 1000, 2000
m = rng.standard_normal(d)
m *= 1.7 * np.sqrt(d) / np.linalg.norm(m)   # 모두가 공유하는 평균 방향
Y = rng.standard_normal((n, d)) + m          # 서로 무관한 2,000개

def pair_cos(Y):
    Z = Y / np.linalg.norm(Y, axis=1, keepdims=True)
    return (Z @ Z.T)[np.triu_indices(len(Z), 1)]

for name, V in [("그대로", Y), ("평균 뺀 뒤", Y - Y.mean(0))]:
    c = pair_cos(V)
    print(f"{name:6s} 평균 {c.mean():+.3f}  99.9% 분위수 {np.quantile(c, 0.999):+.3f}")

그대로    평균 +0.743  99.9% 분위수 +0.777
평균 뺀 뒤 평균 -0.001  99.9% 분위수 +0.097

2,000개는 공통 성분 $m$ 을 빼면 서로 아무 관계가 없는데도 코사인 평균이 0.743이었습니다. 코사인이 각 벡터의 개성이 아니라 모두가 공유하는 $m$ 끼리의 정렬을 재고 있었기 때문입니다. 데이터 전체의 평균 벡터를 모든 벡터에서 빼는 조작, 곧 중심화를 하자 평균이 0으로 돌아왔고, 99.9% 분위수 0.097은 등방 1000차원의 이론값 $3.29/\sqrt{1000} \approx 0.104$ 와 거의 같습니다. 원뿔 안에 갇혀 있던 벡터들이 다시 구면 전체로 퍼진 것입니다. 이 조작은 다음 절에서 한 번 더 나옵니다.

최근접 목록의 허브

k-출현 횟수

거리 집중에는 눈에 덜 띄는 부산물이 하나 있습니다. 데이터의 점마다 가장 가까운 $k$ 개를 뽑아 k-최근접 목록을 만든 뒤, 거꾸로 각 점이 남의 목록에 몇 번 등장하는지를 셉니다. 이 수가 k-출현 횟수 $N_k$ 입니다. 목록마다 정확히 $k$ 칸이므로 전체 점에 대한 $N_k$ 의 평균은 언제나 $k$ 입니다. 궁금한 것은 평균이 아니라 모양입니다.

from scipy.stats import norm, skew

def euclid(X):
    sq = (X**2).sum(1)
    D = np.sqrt(np.maximum(sq[:, None] + sq[None, :] - 2 * X @ X.T, 0))
    np.fill_diagonal(D, np.inf)
    return D

def k_occurrence(D, k=10):
    knn = np.argpartition(D, k, axis=1)[:, :k]      # 각 점의 k-최근접 목록
    return np.bincount(knn.ravel(), minlength=len(D))

rng = np.random.default_rng(0)
for d in [10, 1000]:
    X = rng.standard_normal((2000, d))
    D = euclid(X)
    N = k_occurrence(D)
    print(f"d={d:4d}  왜도 {skew(N):5.2f}  최댓값 {N.max():3d}  한 번도 안 뜬 점 {np.mean(N == 0):5.1%}")

d=  10  왜도  0.71  최댓값  34  한 번도 안 뜬 점  2.9%
d=1000  왜도  7.48  최댓값 415  한 번도 안 뜬 점 30.4%

왜도는 분포가 한쪽으로 얼마나 길게 늘어졌는지를 재는 값입니다. 좌우 대칭이면 0이고, 오른쪽 꼬리가 길수록 커집니다. 10차원에서는 0.71로 평균 10 주위에 적당히 퍼졌지만, 1000차원에서는 7.48로 오른쪽 꼬리가 길게 늘어졌습니다. 한 점은 2,000개 목록 가운데 415개에 등장했습니다. 이렇게 남의 목록에 유난히 자주 뜨는 점을 허브라고 하고, 차원이 높을수록 허브가 생기는 현상을 허브 현상(hubness)이라고 부릅니다. 반대편 끝도 있습니다. 1000차원에서는 30.4%, 곧 600개가 넘는 점이 누구의 목록에도 한 번도 안 떴습니다.

허브의 원인

허브는 데이터의 중심에 조금 가까운 점입니다. 위 1000차원 데이터에서 $N_k$ 가 가장 큰 점 20개를 골라 데이터 평균까지의 거리를 재면 평균 29.70이고, 전체 점은 31.60입니다. 겨우 6% 가깝습니다. 그런데 그 6%로 충분한 까닭이 앞 절들에 다 있습니다.

데이터 평균을 $\mu$ 라 두고 두 점 사이 거리의 제곱을 풀면 이렇습니다.

$$\|x - y\|^2 = \|x - \mu\|^2 + \|y - \mu\|^2 - 2\,(x - \mu) \cdot (y - \mu)$$

고차원에서는 $x - \mu$ 와 $y - \mu$ 가 거의 직교하므로 마지막 항은 앞의 두 항에 비해 작게 흔들립니다. 그러면 $y$ 에서 본 $x$ 까지의 거리는 대략 $\|x - \mu\|^2$ 하나로 정해지고, 이 값은 $y$ 가 누구든 같습니다. 중심에 조금 가까운 $x$ 는 모두에게 조금씩 가깝습니다. 저차원이라면 이 「조금」은 순위를 못 바꿉니다 — 거리들이 넓게 퍼져 있어 $y$ 바로 옆의 점이 따로 있기 때문입니다. 하지만 거리 집중으로 모든 거리가 한 값 주위에 몰려 있으면, 6% 가까운 것만으로 남의 상위 10개에 들어갑니다. 허브는 거리 집중의 부산물입니다.

같은 문서가 뜨는 증상

RAG 시스템을 운영하다 보면 「어떤 질문을 넣어도 같은 문서 두세 개가 상위에 섞여 나온다」는 신고를 받습니다. 질의도 문서와 같은 공간, 비슷한 분포에서 오므로 문서들 사이에서 허브인 점은 질의의 목록에도 허브로 뜹니다. 그 문서가 특별히 좋은 문서여서가 아니라 공간의 중심 가까이에 놓였기 때문입니다. 앞 절에서 본, 정규화하지 않은 내적에서 긴 벡터가 목록을 독차지하던 것도 같은 모양의 증상입니다.

더 조용한 쪽은 반대편입니다. 1000차원 실험에서 30%의 점이 누구의 목록에도 안 떴듯, 어떤 문서는 어떤 질의에도 상위에 오르지 않습니다. 이것은 신고조차 들어오지 않습니다. 진단은 위 코드 그대로입니다. 문서끼리 또는 실제 질의 기록으로 k-최근접 목록을 만들고 문서별 $N_k$ 를 세면, 목록의 20%에 뜨는 문서와 한 번도 안 뜨는 문서가 숫자로 드러납니다.

상호 근접과 중심화

허브를 줄이는 손잡이가 둘 있습니다.

첫째는 상호 근접입니다. 거리를 한쪽 입장에서만 보지 말고 양쪽이 서로를 가깝다고 여기는지로 바꿉니다. 점 $x$ 의 다른 모든 점까지의 거리 분포를 평균 $\mu_x$, 표준편차 $\sigma_x$ 인 정규분포로 근사하면, 거리 $d_{xy}$ 가 $x$ 입장에서 얼마나 가까운지를 「$x$ 의 거리가 $d_{xy}$ 보다 클 확률」로 적을 수 있습니다. 두 입장을 곱해 새 거리를 만듭니다.

$$\mathrm{MP}(x, y) = 1 - P(D_x > d_{xy}) \, P(D_y > d_{xy})$$

보통 점 $y$ 입장에서 허브는 아주 가깝지만, 허브는 모두에게 가까워 제 거리 분포 자체가 작은 쪽에 몰려 있으므로 허브 입장에서 $y$ 는 여럿 중 하나일 뿐입니다. 한쪽 확률이 1에 못 미치니 곱이 커지지 않고, 새 거리에서는 허브가 서로 가까운 진짜 이웃에게 자리를 내줍니다. 위 1000차원 데이터의 거리 행렬 D를 그대로 바꿔 넣으면 이렇습니다.

def mutual_proximity(D):
    F = np.where(np.isinf(D), np.nan, D)
    mu, sd = np.nanmean(F, 1), np.nanstd(F, 1)
    both = norm.sf(D, mu[:, None], sd[:, None]) * norm.sf(D, mu[None, :], sd[None, :])
    M = 1 - both                 # 둘이 서로를 가깝다고 볼 확률의 여사건
    np.fill_diagonal(M, np.inf)
    return M

Nm = k_occurrence(mutual_proximity(D))
print(f"상호 근접  왜도 {skew(Nm):5.2f}  최댓값 {Nm.max():3d}  한 번도 안 뜬 점 {np.mean(Nm == 0):5.1%}")

상호 근접  왜도  0.73  최댓값  38  한 번도 안 뜬 점  4.3%

왜도가 7.48에서 0.73으로, 최댓값이 415에서 38로 내려왔습니다. 10차원 데이터와 거의 같은 모양입니다. 값은 치릅니다 — 점마다 거리 분포의 평균과 표준편차를 미리 구해 두어야 하고, 큰 색인에서는 표본으로 어림합니다.

둘째는 앞 절의 중심화입니다. 코사인이나 내적은 원점을 기준으로 재므로 데이터 전체가 원점에서 떨어진 원뿔 안에 있으면, 원뿔의 축에 조금 더 가까운 점이 모두에게 조금 더 가까운 허브가 됩니다. 앞 절의 원뿔 데이터로 코사인 거리의 $N_k$ 를 세 보면 차이가 큽니다.

def cosine_dist(Y):
    Z = Y / np.linalg.norm(Y, axis=1, keepdims=True)
    D = 1 - Z @ Z.T
    np.fill_diagonal(D, np.inf)
    return D

rng = np.random.default_rng(3)
m = rng.standard_normal(1000)
m *= 1.7 * np.sqrt(1000) / np.linalg.norm(m)
Y = rng.standard_normal((2000, 1000)) + m          # 앞 절의 원뿔 데이터
for name, V in [("그대로", Y), ("평균 뺀 뒤", Y - Y.mean(0))]:
    N = k_occurrence(cosine_dist(V))
    print(f"{name:6s} 왜도 {skew(N):5.2f}  최댓값 {N.max():3d}")

그대로    왜도  6.67  최댓값 376
평균 뺀 뒤 왜도  0.30  최댓값  20

평균 벡터 하나를 빼는 것만으로 왜도가 6.67에서 0.30이 됐습니다. 질의에서도 같은 벡터를 빼야 한다는 것만 지키면 되니 비용이 거의 없습니다. 다만 유클리드 거리에서는 소용이 없습니다. 모든 점을 같은 만큼 옮겨도 점 사이의 거리는 그대로이기 때문입니다. 중심화는 원점을 기준으로 재는 척도에 듣는 손잡이이고, 상호 근접은 어떤 거리에도 걸 수 있는 손잡이입니다.

검색 실무

근사 검색

이제 실무에서 마주치는 몇 가지를 이 언어로 다시 읽을 수 있습니다. 먼저 근사 최근접 이웃으로 충분한 이유입니다. 대비가 살아 있으면 진짜 1등과 2등의 거리가 뚜렷이 다르므로, 후보를 조금 놓쳐도 상위권 안에서 답이 나옵니다. 정확한 최근접을 보장하려면 사실상 전수 비교인데, 대비가 큰 데이터에서는 그 보장이 별로 값어치가 없고 대비가 작은 데이터에서는 보장해 봐야 1등이 뜻을 잃습니다. 어느 쪽이든 정확성에 비용을 더 치를 이유가 약합니다.

도메인 밖 질의

질의가 도메인 밖일 때 결과가 이상해지는 것도 같은 언어로 설명됩니다. 데이터의 구조 밖에 있는 질의는 어느 군집에도 안 붙습니다. 그러면 그 질의 입장에서 데이터는 등방 가우시안처럼 보이고, 대비가 0.15 수준으로 떨어집니다. 1등과 100등의 거리 차이가 잡음 수준이니 순위 자체가 의미를 잃습니다. 「검색 결과가 다 비슷비슷하게 관련 없다」는 증상이 이것입니다. 이때 상위에 뜨는 것은 질의와 가까운 문서가 아니라 모두와 가까운 문서, 곧 앞 절의 허브이기 쉽습니다.

분위수 임계값

「코사인 0.8 이상이면 관련 있다」 같은 절대 기준은 모델과 데이터에 따라 뜻이 달라집니다. 이 글에서 잰 무관한 쌍의 코사인만 봐도 그렇습니다. 무작위로 짝지은 쌍에서 1,000쌍에 한 쌍만 넘는 값을 분위수로 적으면(값을 작은 순서로 줄 세웠을 때 99.9% 지점), 등방 1000차원에서 0.097, 원뿔 데이터에서 0.777이었습니다. GloVe 빈도 상위 2,000단어를 무작위로 짝지으면 0.726이었습니다. 같은 0.8이 한 모델에서는 거의 확실한 관련이고 다른 모델에서는 우연 수준입니다.

그래서 문턱은 절대값이 아니라 그 모델, 그 데이터에서 무관한 쌍의 분포를 보고 정합니다. 절차는 세 줄입니다.

1. 서로 무관하다고 볼 수 있는 쌍을 수천에서 수만 개 뽑는다 — 무작위로 고른 문서 두 개, 또는 실제 질의와 무작위 문서 하나.
2. 그 쌍들의 코사인을 모아 분포를 만든다.
3. 그 분포의 99% 또는 99.9% 분위수를 문턱으로 잡는다. 무관한 쌍이 우연히 넘을 확률이 1% 또는 0.1%라는 뜻이 된다.

모델을 바꾸거나 중심화를 켜고 끄면 분포가 통째로 움직이므로 이 세 줄을 다시 돌립니다. 문턱을 코드에 숫자로 박아 두면 모델 교체와 함께 조용히 틀립니다.

차원 축소

마지막으로, 내재 차원이 낮다면 1024개 좌표에 든 정보는 훨씬 적은 좌표로도 담깁니다. GloVe의 TwoNN이 9.2였던 것처럼 이웃 사이의 구조가 몇 개의 방향으로만 움직인다면, 모든 좌표를 들고 다닐 이유가 적습니다. 그것이 다음 글의 주제입니다 — 무작위로 아무 방향에나 사영해도 모든 쌍의 거리가 얼마나 보존되는지에 대한 정확한 답이 있습니다.

정리

처음 장면으로 돌아가면, 1024차원 벡터를 코사인으로 비교하는 일은 3차원에서 가까운 점을 찾는 일과 전혀 다른 공간에서 벌어집니다. 그 공간에서 검색이 되는 것은 차원이 낮아서가 아니라 데이터가 그 안의 낮은 차원 구조 위에 놓여 있어서이고, 그 구조 밖으로 나가는 순간 공간의 원래 성질 — 거리 집중과 허브 — 이 그대로 드러납니다.

• $d$ 차원 공의 부피는 반지름의 $d$ 제곱에 비례하므로 껍질에 몰린다. 1000차원에서는 바깥 1% 껍질에 부피의 99.996%가 있고, 공 안에서 균등하게 뽑은 점의 중심 거리 기댓값은 $d/(d+1) = 0.999$ 다.
• 반지름 1인 공의 부피 자체는 5차원에서 최대(5.26)이고 그 뒤 0으로 간다. 10차원에서 이미 공이 감싸는 상자의 0.25%만 차지한다.
• 구면 위에서는 넓이가 적도 띠에 몰린다(측도 집중). 폭이 지름의 10%인 띠가 3차원에서 10%, 1000차원에서 99.85%를 갖는다. 껍질과 적도는 합의 흔들림이 $1/\sqrt{d}$ 로 줄어드는 한 현상을 반지름과 각도 두 방향에서 본 것이다.
• 무작위 두 벡터의 코사인은 표준편차 $1/\sqrt{d}$ 로 0 주위에 몰린다. $d=1000$ 에서 10만 쌍 중 최댓값이 0.135였다. 길이를 1로 맞추면 $\|a-b\|^2 = 2 - 2\cos\theta$ 라 코사인·내적·유클리드 순위가 같고, 안 맞추면 내적 상위 10의 97.4%가 길이 상위 10% 출신이었다.
• 거리 제곱의 상대 흔들림이 $1/\sqrt{d}$ 로 줄어 최원거리와 최근접의 비가 1로 수렴한다 — 1000차원 균등 데이터에서 1.119였다. 같은 이유로 공간을 칸으로 가르는 색인은 30차원에서 이미 십억 칸이 필요하고 가지치기도 안 된다.
• 집중을 정하는 것은 내재 차원이다. 주변 차원 1000에서 대비가 0.149(등방)부터 5.759(군집 20개)까지 갈렸다. 참여 비율은 멀리서, TwoNN은 가까이서 재며, GloVe 300차원에서 각각 134.0과 9.2였다. 원뿔에 쏠린 데이터는 평균을 빼면 무관한 쌍의 코사인이 0.743에서 0으로 돌아온다.
• 거리 집중의 부산물로 허브가 생긴다. 1000차원에서 k-출현 횟수의 왜도가 7.48, 최댓값이 415였고 30.4%는 한 번도 안 떴다. 상호 근접은 왜도를 0.73으로, 코사인에서의 중심화는 6.67을 0.30으로 줄였다.
• 그래서 근사 검색으로 충분하고, 도메인 밖 질의에서는 순위가 무의미해지며, 유사도 문턱은 무관한 쌍 분포의 분위수로 정한다.

---

읽어주셔서 감사합니다. 😊