존슨–린덴스트라우스 보조정리(JL 보조정리)는 점 개를 무작위 행렬 하나로 낮은 차원에 옮겨도 모든 쌍의 거리가 거의 보존된다고 말합니다. 필요한 차원은 점 개수의 로그에만 비례하고 원래 차원과는 상관이 없습니다. 그런데 이 정리에 값을 넣어 보면 실무 감각과 어긋납니다. 우리 검색 실험대의 scifact 임베딩 5,183개를 왜곡 10% 안에 두려면 7,331차원이 필요하다고 나옵니다. 원래 차원 384보다 열아홉 배 큽니다.
반면 차원 무릎 실험에서는 같은 임베딩을 128차원으로 줄여도 검색 품질의 94.7%가 남았습니다. 흔한 설명은 「정리는 최악의 경우를 말하므로 실제 데이터에서는 훨씬 헐겁다」입니다. 이 글은 그 헐거움을 배수로 재려고 시작했습니다.
결과는 예상과 반대였습니다. 정리가 요구하는 것을 그대로 재면 실측도 6,1447,168차원이 필요했고, 배수는 1.01.2였습니다. 실제 임베딩과 난수 벡터가 같은 값을 냈습니다. 128차원에서 검색이 버틴 이유는 정리가 헐거워서가 아니라 잰 것이 달라서였습니다. 그래서 제목과 결론을 이쪽으로 세웁니다.
무작위 사영이 왜 거리를 보존하는지와 정리의 유도는 랜덤 사영과 존슨–린덴스트라우스 보조정리가 맡습니다. 고차원에서 거리가 뭉친다는 다른 주장은 차원의 저주 재현이 맡으므로, 이 글은 경계와 실측의 배수 하나만 다룹니다.
재현하려는 주장
경계의 식
원 정리는 Johnson과 Lindenstrauss(1984)의 것이고, 오늘 흔히 쓰는 상수는 Dasgupta와 Gupta의 짧은 증명(2003)에서 나온 꼴입니다. scikit-learn의 johnson_lindenstrauss_min_dim이 이 꼴을 그대로 계산하므로 이 글의 이론값은 전부 그 함수에서 받았습니다.
이면 의 점 개를 차원으로 옮기는 사영 가 있어서, 모든 쌍 에 대해
가 성립합니다. 여기서 은 제곱 거리가 몇 % 어긋나도 되는지를 정하는 왜곡 허용치입니다. 학습 글이 적은 은 같은 모양에 상수만 다른 판이고, , 이면 7,603으로 위 식의 7,331과 4% 차이입니다.
식에 가 없다는 것이 이 정리의 핵심입니다. 그리고 증명에 쓰는 사영은 데이터를 보지 않고 뽑은 가우스 난수 행렬입니다.
판정 기준
계획이 정한 판정은 「 을 지키는 이론 차원 대 실측 차원 , 배수 」입니다. 정리의 문장을 그대로 따라 을 정의했습니다.
- scifact 문서 5,183편을 all-MiniLM-L6-v2로 인코딩해 384차원 단위 벡터로 둡니다.
- 표준정규 난수로 행렬 을 뽑고 를 곱합니다.
- 모든 쌍 1,343만 개에 대해 사영 전후 제곱 거리의 비를 재고 1에서 얼마나 벗어났는지 봅니다.
- 가장 많이 벗어난 쌍의 값, 곧 최대 왜곡이 0.1 이하인 가장 작은 가 입니다.
시드를 다섯 개 바꿔 같은 일을 하고, 다섯 번의 중앙값이 0.1 아래로 내려가는 와 다섯 번 모두 내려가는 를 둘 다 적습니다.
비교군으로 같은 개수, 같은 차원의 난수 단위벡터를 둡니다. 성분을 독립 정규분포로 뽑아 길이를 1로 맞춘 벡터입니다. 실제 임베딩은 차원의 저주 재현에서 본 것처럼 내재 차원이 384보다 훨씬 낮으므로, 데이터의 구조가 경계를 느슨하게 만든다면 두 줄이 달라야 합니다.
측정
계산 요령
모든 쌍을 사영 공간에서 다시 재면 에서 5,183 × 5,183 행렬을 안쪽 차원 8,192로 곱해야 합니다. 대신 을 먼저 만들면 차이 벡터 의 사영 길이가 이므로, 한 번으로 모든 쌍이 나옵니다. 은 와 상관없이 384 × 384라서 비용이 에 거의 안 늘어납니다.
스크립트 뒤쪽은 다른 물음에 답합니다. 검색에 필요한 것은 거리 자체가 아니라 순위라서, 문서 300편을 질의로 삼아 코사인 상위 10개 이웃이 사영 뒤에 몇 개 남는지를 셉니다. 데이터를 보고 축을 고르는 PCA와 데이터를 안 보는 무작위 사영을 같은 에서 나란히 둡니다.
재현 블록
pip install sentence-transformers datasets numpy scikit-learnimport time, numpy as np, torch
from datasets import load_dataset
from sentence_transformers import SentenceTransformer
from sklearn.random_projection import johnson_lindenstrauss_min_dim
torch.manual_seed(0); t0 = time.perf_counter()
c = load_dataset("BeIR/scifact", "corpus")["corpus"]
model = SentenceTransformer("sentence-transformers/all-MiniLM-L6-v2")
X = model.encode([(d["title"] + " " + d["text"]).strip() for d in c], batch_size=64,
normalize_embeddings=True, show_progress_bar=False).astype(np.float64)
n, d = X.shape
Z = np.random.default_rng(1).standard_normal((n, d)); Z /= np.linalg.norm(Z, axis=1, keepdims=True)
print(f"n={n} d={d} encode={time.perf_counter() - t0:.0f}s")
print("JL 이론 차원 (sklearn, 제곱거리 왜곡 ε):",
" ".join(f"ε={e}→{johnson_lindenstrauss_min_dim(n, eps=e)}" for e in (0.1, 0.2, 0.3, 0.5)))
iu = np.triu_indices(n, 1)
def pairs(X): # 원래 제곱거리와, 중복 문서(거리 0) 쌍을 빼는 마스크
d0 = (2 - 2 * X @ X.T)[iu]; return d0, d0 > 1e-6
def distortion(X, d0, ok, M): # 사영 행렬 R에 대해 M = R R^T 이면 |R^T(x-y)|^2 = (x-y)^T M (x-y)
G = X @ M @ X.T; g = np.diag(G)
r = np.abs((g[:, None] + g[None, :] - 2 * G)[iu][ok] / d0[ok] - 1)
return r.max(), (r > 0.1).mean()
KS, SEEDS = [128, 384, 1024, 2048, 4096, 5120, 6144, 7168, 8192], range(5)
for lab, A in (("실제 임베딩 scifact", X), ("난수 단위벡터", Z)):
d0, ok = pairs(A)
print(f"[{lab}] 쌍 {ok.sum():,}개 (중복 제외 {(~ok).sum()})")
print(f" {'k':>6}{'최대 왜곡 중앙값':>12}{'[최소, 최대]':>18}{'ε=0.1 넘는 쌍':>14}")
for k in KS:
res = []
for s in SEEDS:
R = np.random.default_rng(s).standard_normal((d, k)) / np.sqrt(k)
res.append(distortion(A, d0, ok, R @ R.T))
mx, fr = np.array(res).T
print(f" {k:>6}{np.median(mx):>12.4f} [{mx.min():.4f}, {mx.max():.4f}]{np.median(fr) * 100:>12.4f}%")
# 검색에 필요한 것은 거리가 아니라 순위다: 문서 300개를 질의 삼아 이웃 10개가 몇 개 남는가
qi = np.random.default_rng(0).choice(n, 300, replace=False)
nz = lambda A: A / np.linalg.norm(A, axis=1, keepdims=True)
top = lambda A: np.argsort(-(nz(A)[qi] @ nz(A).T), 1)[:, 1:11] # 코사인 순위, 0번째(자기 자신)는 뺀다
ref = top(X); U = np.linalg.svd(X - X.mean(0), full_matrices=False)[2]
print("이웃 10개 보존율 (300개 질의, 무작위 사영은 시드 5개 평균)")
for k in (32, 64, 128, 256, 384):
rp = np.mean([np.mean([len(set(a) & set(b)) / 10 for a, b in zip(ref, top(X @ np.random.default_rng(s).standard_normal((d, k))))]) for s in SEEDS])
pc = np.mean([len(set(a) & set(b)) / 10 for a, b in zip(ref, top(X @ U[:k].T))])
print(f" k={k:<4} 무작위 사영 {rp:.3f} PCA {pc:.3f}")
print(f"elapsed={time.perf_counter() - t0:.0f}s")python3 jl.py실제 출력
진행 표시줄과 허브 경고는 뺐습니다.
n=5183 d=384 encode=114s
JL 이론 차원 (sklearn, 제곱거리 왜곡 ε): ε=0.1→7331 ε=0.2→1973 ε=0.3→950 ε=0.5→410
[실제 임베딩 scifact] 쌍 13,429,153개 (중복 제외 0)
k 최대 왜곡 중앙값 [최소, 최대] ε=0.1 넘는 쌍
128 0.7791 [0.7646, 1.0350] 42.7836%
384 0.4152 [0.3834, 0.4686] 16.3559%
1024 0.2478 [0.2366, 0.2779] 2.3743%
2048 0.1780 [0.1722, 0.1955] 0.1516%
4096 0.1202 [0.1188, 0.1309] 0.0008%
5120 0.1042 [0.1004, 0.1077] 0.0000%
6144 0.0973 [0.0912, 0.1025] 0.0000%
7168 0.0911 [0.0878, 0.0959] 0.0000%
8192 0.0822 [0.0799, 0.0859] 0.0000%
[난수 단위벡터] 쌍 13,429,153개 (중복 제외 0)
k 최대 왜곡 중앙값 [최소, 최대] ε=0.1 넘는 쌍
128 0.8146 [0.7087, 0.8707] 42.2818%
384 0.4380 [0.4265, 0.4598] 16.4933%
1024 0.2497 [0.2412, 0.3141] 2.3510%
2048 0.1717 [0.1669, 0.1866] 0.1336%
4096 0.1209 [0.1174, 0.1269] 0.0006%
5120 0.1112 [0.1076, 0.1170] 0.0001%
6144 0.0975 [0.0952, 0.1044] 0.0000%
7168 0.0889 [0.0880, 0.0960] 0.0000%
8192 0.0842 [0.0796, 0.0875] 0.0000%
이웃 10개 보존율 (300개 질의, 무작위 사영은 시드 5개 평균)
k=32 무작위 사영 0.275 PCA 0.547
k=64 무작위 사영 0.446 PCA 0.709
k=128 무작위 사영 0.583 PCA 0.862
k=256 무작위 사영 0.684 PCA 0.977
k=384 무작위 사영 0.741 PCA 1.000
elapsed=276s판정
경계와 실측
에서 이론 차원은 7,331입니다. 실제 임베딩의 최대 왜곡은 5,120차원에서 중앙값 0.1042로 아직 넘고, 6,144차원에서 0.0973으로 처음 내려갑니다. 다섯 시드 전부가 내려가는 것은 7,168차원(최대 0.0959)입니다.
| 이론 | 실측 (중앙값 기준) | 실측 (다섯 시드 모두) | 배수 | |
|---|---|---|---|---|
| 실제 임베딩 | 7,331 | 6,144 | 7,168 | 1.02~1.19 |
| 난수 단위벡터 | 7,331 | 6,144 | 7,168 | 1.02~1.19 |
중앙값 기준과 다섯 시드 기준이 갈리는 것은 정리의 문장 때문입니다. 정리는 그런 사영이 「있다」고만 말하고, 난수로 한 번 뽑았을 때 성공할 확률은 따로 계산해야 합니다. 6,144차원에서 다섯 시드의 최대 왜곡은 0.0912~0.1025라 다섯 중 적어도 셋은 성공했고, 마지막 하나는 0.1을 조금 넘었습니다. 아래에서 계산할 「0.1을 넘는 쌍의 기대 개수」가 이 차원에서 0.58인데, 넘는 쌍이 드물게 따로따로 나온다고 보면 한 개도 안 나올 확률은 입니다. 7,168차원에서는 기대 개수 0.05로 그 확률이 0.95까지 오르고, 실측도 다섯 시드가 모두 성공했습니다. 시드 사이의 이 들쭉날쭉함은 에서 더 큽니다. 실제 임베딩의 최대 왜곡이 0.7646에서 1.0350까지 벌어졌는데, 1.0350은 어느 한 쌍의 제곱 거리가 두 배 넘게 부풀었다는 뜻입니다.
배수가 1.0~1.2입니다. 「경계가 헐겁다」고 말할 자리가 거의 없습니다. 격자가 1,024 간격이라 의 정밀도도 그만큼이고, 그 오차를 감안해도 배수가 2를 넘을 수는 없습니다.
실제 임베딩과 난수
두 블록이 줄마다 겹칩니다. 에서 최대 왜곡 중앙값이 0.2478과 0.2497, 0.1을 넘는 쌍의 비율이 2.3743%와 2.3510%입니다. 에서도 42.78%와 42.28%입니다. 시드 사이의 산포보다 두 데이터 사이의 차이가 작습니다.
이것은 우연이 아니라 가우스 사영의 성질입니다. 가우스 난수 행렬은 어느 방향으로 돌려도 분포가 같으므로, 고정된 벡터 하나의 사영 길이 비 는 가 무엇이든 자유도 인 카이제곱을 로 나눈 분포를 따릅니다. 쌍 하나하나의 왜곡 분포는 데이터와 무관하다는 뜻입니다.
데이터가 끼어들 수 있는 자리는 쌍들 사이의 상관 하나입니다. 차이 벡터들이 몇 안 되는 방향에 몰려 있으면 그 왜곡들이 함께 움직이고, 1,343만 개의 최댓값이 덜 커질 수 있습니다. 실제 임베딩은 내재 차원이 낮으니 그 효과를 기대했는데, 측정에서는 보이지 않았습니다. 384차원 안에서도 차이 벡터가 퍼져 있는 방향이 최댓값을 독립에 가깝게 만들 만큼은 많았다는 뜻으로 읽힙니다.
카이제곱 꼬리
쌍 하나의 왜곡 분포가 데이터와 무관하다면 측정 없이 계산으로도 같은 표가 나와야 합니다. 쌍 하나가 을 넘을 확률은 카이제곱 분포의 양쪽 꼬리를 더한 것이고, 거기에 쌍의 개수를 곱하면 0.1을 넘는 쌍이 몇 개쯤 나올지가 나옵니다. 경계의 증명이 하는 일을 상수 없이 정확한 꼬리로 다시 한 셈입니다.
import numpy as np
from scipy.stats import chi2
pairs = 5183 * 5182 // 2 # 실험의 쌍 개수 13,429,153
p = lambda k: chi2.cdf(0.9 * k, k) + chi2.sf(1.1 * k, k) # 쌍 하나가 ε=0.1을 넘을 정확한 확률
print(f"{'k':>6}{'쌍 하나가 넘을 확률':>14}{'넘는 쌍의 기대 개수':>16}")
for k in (384, 1024, 2048, 4096, 5120, 6144, 7168):
print(f"{k:>6}{p(k) * 100:>13.4f}%{pairs * p(k):>18.2f}")
ks = np.arange(4000, 8000)
print("기대 개수가 1 아래로 내려가는 k =", ks[np.argmax(pairs * p(ks) < 1)])python3 tail.py # scipy는 scikit-learn과 함께 깔린다 k 쌍 하나가 넘을 확률 넘는 쌍의 기대 개수
384 16.5197% 2218455.36
1024 2.3645% 317538.23
2048 0.1416% 19010.34
4096 0.0007% 95.47
5120 0.0001% 7.34
6144 0.0000% 0.58
7168 0.0000% 0.05
기대 개수가 1 아래로 내려가는 k = 5926측정과 계산이 거의 같습니다. 0.1을 넘는 쌍의 비율이 384차원에서 실측 16.36%(실제 임베딩)·16.49%(난수)에 계산 16.52%, 1,024차원에서 2.37%·2.35%에 2.36%, 2,048차원에서 0.15%·0.13%에 0.14%입니다. 쌍들을 서로 독립인 것처럼 다룬 계산이 실제 임베딩의 측정을 자릿수까지 맞힙니다.
넘는 쌍의 기대 개수가 1 아래로 내려가는 자리는 5,926차원입니다. 실측에서 최대 왜곡 중앙값이 처음 0.1 아래로 내려간 6,144차원과 격자 한 칸 안입니다. 경계의 7,331과 이 5,926의 차이, 곧 1.24배가 증명이 꼬리를 정확히 계산하지 않고 지수 꼴의 위쪽 한계로 막은 데서 오는 몫 전부입니다.
경계가 빡빡한 이유
정리의 증명은 두 걸음입니다. 쌍 하나가 을 넘을 확률을 카이제곱 꼬리로 막고, 그 확률에 쌍의 개수를 곱해 1보다 작게 만듭니다. 앞 걸음의 지수 꼴 한계는 정확한 꼬리와 같은 차수라서 바로 위에서 본 1.24배만 남기고, 뒷 걸음의 곱셈은 사건들이 거의 독립일 때 거의 등호입니다. 정확한 꼬리에 쌍의 개수를 곱한 5,926이 실측과 격자 한 칸 안에서 맞았다는 것이 그 「거의 독립」의 증거입니다.
그러니 이 정리가 헐거워질 자리가 처음부터 좁았습니다. 정리가 「최악의 경우」를 말한다는 것은 데이터에 대해 아무것도 가정하지 않는다는 뜻이지, 실제 데이터에서 크게 남는다는 뜻이 아니었습니다. 무작위 사영이라는 도구와 모든 쌍이라는 기준을 고정하면 데이터가 무엇이든 필요한 차원이 같습니다.
128차원의 정체
바뀐 두 가지
그렇다면 차원 무릎 실험의 128차원은 무엇이었을까요. 정리와 비교하면 두 가지가 바뀌어 있었습니다.
- 도구 — 무작위 사영이 아니라 PCA였습니다. PCA는 데이터의 분산이 큰 방향을 골라 남기므로, 데이터의 구조를 쓰는 사영입니다.
- 기준 — 모든 쌍의 거리가 아니라 질의별 상위 순위였습니다.
출력의 마지막 표가 둘을 갈라 보여 줍니다. 128차원에서 상위 10개 이웃이 남는 비율은 무작위 사영 0.583, PCA 0.862입니다. 같은 차원에서 데이터를 보고 고른 축이 이웃을 1.5배 더 지킵니다. PCA는 256차원에서 0.977로 거의 다 지키는데, 무작위 사영은 원래 차원과 같은 384차원에서도 0.741에 머뭅니다. 무작위 사영은 차원을 늘리지 않을 때도 좌표를 뒤섞으며 거리를 흔들기 때문입니다. 차원이 낮을수록 둘의 간격은 벌어집니다. 32차원에서 PCA는 이웃의 54.7%를 지키고 무작위 사영은 27.5%로 절반입니다. 무작위 사영은 남길 방향을 고르지 않으니 차원이 모자랄 때 버리는 정보도 고르지 못합니다.
꺾이는 지점
한 줄로 적으면 이렇습니다 — 무작위 사영으로 모든 쌍을 안에 두는 데는 6,144차원이 필요해 384차원에서 줄일 수 있는 것이 없고, 같은 384차원 임베딩을 PCA로 256차원까지 줄이면 상위 10개 이웃의 97.7%가 남습니다.
기준을 조금만 늦춰도 무작위 사영의 필요 차원이 크게 내려갑니다. 0.1을 넘는 쌍이 0.15%로 남는 것을 받아들이면 2,048차원이고, 2.37%면 1,024차원입니다. 정리의 7,331차원은 마지막 0.15%의 쌍까지 막는 값입니다. 그래도 384보다는 큽니다. 무작위 사영으로는 이 임베딩을 줄일 길이 없다는 결론은 남습니다.
실무 판단
이 측정이 실무에 주는 판단은 둘입니다. 첫째, 이미 몇백 차원인 문장 임베딩을 더 줄일 때 JL 경계를 근거로 무작위 사영을 고르지 않습니다. 경계는 정확했고, 그 정확한 값이 원래 차원보다 큽니다. 줄이려면 PCA처럼 데이터를 보는 방법을 쓰고 검색 지표로 무릎을 잽니다.
값으로 옮기면 손해가 분명합니다. 6,144차원 float32 벡터 하나는 24,576바이트로 원래 384차원(1,536바이트)의 16배입니다. 모든 쌍의 거리를 10% 안에 묶는다는 보장을 사려면 저장 공간을 16배로 늘려야 하고, 그 보장은 원래 벡터를 그대로 쓰면 공짜로 얻는 것입니다.
둘째, 무작위 사영이 제값을 하는 자리는 원래 차원이 경계보다 훨씬 큰 경우입니다. 수만 차원의 희소 특징이나 단어 빈도 벡터를 몇천 차원으로 옮길 때는 정리의 값이 곧 쓸 만한 설계값입니다. 이 실험에서 정리가 그만큼 빡빡했기 때문입니다.
결론과 한계
논문값과 우리 값
| 이론 (sklearn 꼴) | 실측, 실제 임베딩 | 실측, 난수 단위벡터 | |
|---|---|---|---|
| , 모든 쌍 | 7,331 (정확한 꼬리로 5,926) | 6,144~7,168 | 6,144~7,168 |
| 1,973 | 2,048에서 중앙값 0.1780 | 2,048에서 중앙값 0.1717 | |
| 원래 차원 384에서 최대 왜곡 | — | 0.4152 | 0.4380 |
| 판정 | 경계가 1.0~1.2배로 빡빡함 | 실제 임베딩과 같음 |
줄은 격자가 이론값 바로 위인 2,048 하나라 그 자리의 최대 왜곡만 적었습니다. 이론 1,973보다 조금 큰 2,048에서 이미 0.2 아래(0.1780)이므로, 이 허용치에서는 경계에 여유가 조금 더 있습니다.
계획은 「이론이 최악의 경우를 말한다는 것을 배수로 보인다」를 결론으로 잡았고, 난수와 실제 임베딩이 다르게 나오면 그것이 결론이라고 적었습니다. 둘 다 반대로 나왔습니다. 배수는 1에 가까웠고 두 데이터는 같았습니다. 차원 무릎이 이론보다 훨씬 낮은 이유는 경계의 헐거움이 아니라 도구(PCA)와 기준(순위)의 차이입니다.
확인되지 않은 것
- 원 논문과 Dasgupta–Gupta 증명 원문을 받지 못했습니다. 저자 페이지가 이 컨테이너의 이그레스 정책에 막혀
curl: (56) CONNECT tunnel failed, response 403으로 끝났습니다. 식은 scikit-learn 1.9.1 문서와 구현에서 가져왔습니다. - 사영은 가우스 하나입니다. 부호만 쓰는 사영이나 희소 사영은 꼬리가 달라 결과가 다를 수 있습니다.
- 실제 임베딩은 모델 하나(MiniLM), 코퍼스 하나(scifact 5,183편)입니다. 차이 벡터가 훨씬 좁은 방향에 몰린 데이터라면 쌍들의 상관이 최댓값을 줄여 배수가 커질 수 있습니다. 이 글에서는 그런 데이터를 찾지 못했다는 것까지만 말합니다.
- 격자가 1,024 간격이고 시드가 다섯이라 을 한 자리로 못 박지 않았습니다. 그래서 범위로 적었습니다.
- 이웃 보존율은 문서끼리의 이웃이고 scifact의 정답 판정(qrels)을 쓴 nDCG가 아닙니다. 차원 무릎 실험의 nDCG@10과 같은 지표가 아닙니다.
환경
| 항목 | 값 |
|---|---|
| OS | Linux 6.18.44 x86_64 (glibc 2.39) |
| CPU / RAM | Intel Xeon @ 2.80GHz, 4 vCPU / 15GB |
| Python | 3.11.17 |
| 패키지 | sentence-transformers 6.1.0, transformers 5.19.0, torch 2.14.1 (CPU로 실행), datasets 5.1.0, numpy 2.4.6, scikit-learn 1.9.1, scipy 1.17.1 |
| 모델 | sentence-transformers/all-MiniLM-L6-v2 (1110a243), 입력 최대 256토큰(기본값) |
| 데이터 | BeIR/scifact (b3b53356) corpus 5,183편 |
| 실행 시간 | jl.py 276초 (인코딩 114초), tail.py 1초 미만 |
| 측정일 | 2026-10-13 (KST) |
위 출력은 패키지를 새로 깐 빈 가상환경에서 다시 돌린 것입니다. 처음 돌린 가상환경에서는 격자가 조금 달랐는데(5,120·7,168 대신 3,072), 겹치는 일곱 줄과 이웃 보존율은 숫자가 같았습니다.
읽어주셔서 감사합니다. 😊