무작위 사영

수치해석 통계 마지막 수정: 2026-08-30 04:38:05

1. 개요[편집]

무작위 사영 Random Projection
이론적 근거	존슨–린덴슈트라우스 보조정리 (1984)
목표 차원	$k = O(\varepsilon^{-2}\log n)$ — 원 차원 $d$ 와 무관
보존하는 것	모든 쌍의 $\ell_2$ 거리를 $(1\pm\varepsilon)$ 안에서
PCA와의 차이	데이터를 보지 않는다(oblivious) · 분포 무관 · 1패스
빠른 변종	희소 사영 · FJLT/SRHT ($O(d\log d)$)

데이터를 아예 안 보고 차원을 줄이는 방법이 있다. 놀랍게도 그게 잘 된다. 더 놀라운 건 그게 왜 되는지도 증명이 된다는 것이다.

무작위 사영(random projection, RP)은 원소를 무작위로 뽑은 $k\times d$ 행렬 $A$ 를 데이터에 곱해 $d$ 차원 벡터를 $k$ 차원으로 내려보내는 차원 축소 기법이다. 데이터의 통계를 전혀 쓰지 않고 행렬을 뽑는데도 점들 사이의 거리가 거의 그대로 보존된다는 것이 이 기법의 전부이며, 그 보장을 주는 것이 존슨–린덴슈트라우스 보조정리(Johnson–Lindenstrauss lemma, 1984)다.

원래 이 보조정리는 차원 축소를 위해 만들어진 것이 아니다. 존슨과 린덴슈트라우스가 립시츠 사상의 확장 문제를 다루던 순수 함수해석 논문에서 보조 도구로 등장했고, 알고리즘 커뮤니티가 20년쯤 뒤에 발견해 갖다 쓴 것이다.¹ 지금은 최근접 이웃 탐색, 랜덤화 SVD, 스케칭, 압축센싱까지 “고차원을 싸게 다루는” 거의 모든 곳의 밑바닥에 깔려 있다.

2. 보조정리[편집]

$0<\varepsilon<1$ 과 $\mathbb R^d$ 의 임의의 점 $n$ 개 $\{x_1,\dots,x_n\}$ 에 대해

k \;\ge\; \frac{4\ln n}{\varepsilon^2/2 - \varepsilon^3/3}

이면, 모든 쌍 $(i,j)$ 에 대해

(1-\varepsilon)\lVert x_i - x_j\rVert^2 \;\le\; \lVert f(x_i)-f(x_j)\rVert^2 \;\le\; (1+\varepsilon)\lVert x_i - x_j\rVert^2

을 만족하는 사상 $f:\mathbb R^d\to\mathbb R^k$ 가 존재한다. 눈여겨볼 것 셋.

$k$ 가 $d$ 에 의존하지 않는다. 백만 차원이든 십억 차원이든, 점이 $n$ 개면 목표 차원은 같다. 차원의 저주에 대한 가장 직접적인 반격이다.
데이터 분포에 아무 가정이 없다. 정규성도, 저차원 다양체 위에 있다는 가정도 필요 없다. 최악의 배치에서도 성립한다.
$f$ 는 선형이며, 심지어 무작위로 뽑으면 높은 확률로 조건을 만족한다. “존재한다”가 구성적이라는 것 — 이것이 이 정리가 알고리즘이 된 이유다.

라르센과 넬슨(2017)이 $k=\Omega(\varepsilon^{-2}\log n)$ 이 필요조건임을 증명해, 이 차수는 개선의 여지가 없음이 확정됐다. 즉 보조정리는 차수상 최적이다.

3. 증명의 뼈대 — 집중과 합집합 한계[편집]

증명은 두 조각뿐이라 한 번 보면 잊히지 않는다.

조각 1: 노름은 집중한다. $A\in\mathbb R^{k\times d}$ 의 원소를 i.i.d. $\mathcal N(0,1/k)$ 로 뽑자. 고정된 벡터 $u$ 에 대해 $Au$ 의 각 성분은 평균 0, 분산 $\lVert u\rVert^2/k$ 인 가우시안이므로

\mathbb E\big[\lVert Au\rVert^2\big] = \lVert u\rVert^2

이고, $k\lVert Au\rVert^2/\lVert u\rVert^2$ 는 자유도 $k$ 인 $\chi^2$ 다. 카이제곱의 꼬리 한계를 쓰면

\Pr\Big[\big|\lVert Au\rVert^2 - \lVert u\rVert^2\big| > \varepsilon\lVert u\rVert^2\Big] \;\le\; 2\exp\!\Big(-\tfrac{k}{4}(\varepsilon^2-\varepsilon^3)\Big)

가 나온다. $k$ 에 대해 지수적으로 작아진다는 것이 핵심이다. 집중 부등식 한 줄이 전부다.

조각 2: 합집합 한계. 쌍이 $\binom n2 < n^2/2$ 개이고 각각의 실패 확률이 위 값이니, 전부 성공할 확률은

1 - \frac{n^2}{2}\cdot 2\exp\!\Big(-\tfrac k4(\varepsilon^2-\varepsilon^3)\Big)

이상이다. 이 값이 양수가 되도록 $k$ 를 풀면 앞 절의 $k \ge 4\ln n/(\varepsilon^2/2-\varepsilon^3/3)$ 이 나온다. 실패 확률이 양수보다 크기만 하면 그런 $f$ 가 존재한다는 확률론적 방법의 전형이고, 실제로는 확률이 1에 매우 가까워서 무작위로 한 번 뽑으면 대개 그냥 된다.

부수적으로 얻는 것 하나. 노름이 보존되면 편극 항등식 $\langle u,v\rangle = (\lVert u+v\rVert^2-\lVert u-v\rVert^2)/4$ 에 의해 내적도, 따라서 각도와 코사인 유사도도 보존된다. 임베딩 검색이 대개 코사인을 쓰는 것을 생각하면 이쪽이 더 실용적인 따름정리다.

4. 어떤 행렬을 뽑을 것인가[편집]

가우시안이 이론적으로 가장 깔끔하지만, 실무에서는 곱셈을 싸게 만드는 쪽으로 발전해 왔다.

사영 행렬	원소 분포	특징
가우시안	$\mathcal N(0,1/k)$	증명이 제일 쉽다. 밀집 행렬이라 곱셈 $O(kd)$
라데마허	$\pm 1/\sqrt k$ 를 각 1/2 확률로	난수 1비트면 충분, 덧셈·뺄셈만으로 곱셈
아클리오프타스 희소	$\{+1,0,-1\}$ 를 확률 $\{1/6,\,2/3,\,1/6\}$ 로, $\sqrt 3$ 배	원소의 2/3가 0 — 연산량 1/3
매우 희소 (리 외)	0이 아닐 확률 $1/s$ , $s\approx\sqrt d$	연산량 $1/\sqrt d$ 배. 정규성 조건이 붙는다
희소 JL (케인·넬슨)	열마다 정확히 $s=\Theta(\varepsilon^{-1}\log(1/\delta))$ 개만 0 아님	열당 비영원소 수의 하한도 함께 증명됨
FJLT / SRHT	$\Phi = P\,H\,D$	곱셈이 $O(d\log d)$ — 아래 참조

아클리오프타스(2003)의 결과가 인상적인 이유는 분포를 이렇게 거칠게 바꿔도 같은 $k$ 로 같은 보장이 나온다는 점이다. 가우시안의 매끄러움이 아니라 평균 0·분산 1·꼬리가 가벼움이라는 성질만 쓰이기 때문이다. 리·헤이스티·처치(2006)는 여기서 더 밀어붙여 $s=\sqrt d$ 까지 희소화해도 실전에서 멀쩡함을 보였는데, 대신 데이터가 한두 좌표에 몰려 있으면(희소한 원-핫 벡터 같은 것) 사영 행렬도 희소해서 아무것도 안 잡히는 사고가 난다. 희소×희소는 위험하다는 것이 이 계열의 유일한 주의사항이다.²

FJLT(에일런·차젤레, 2006)는 그 위험을 정면으로 처리한다. $\Phi = PHD$ 로 두는데,

$D$ 는 대각선이 무작위 부호 $\pm1$ 인 대각행렬,
$H$ 는 정규화된 아다마르 변환(월시–아다마르 행렬),
$P$ 는 성긴 무작위 행렬.

$HD$ 가 하는 일은 에너지가 몇 좌표에 몰려 있는 벡터를 전 좌표로 골고루 흩뜨리는 것이다(이런 벡터를 비간섭 상태로 만든다고 한다). 그러고 나면 희소한 $P$ 로 표본추출해도 안전하다. 아다마르 변환은 고속 푸리에 변환과 같은 분할정복 구조를 갖고 있어 $O(d\log d)$ 에 계산되며, 덧셈과 뺄셈만 쓴다. 결과적으로 곱셈 비용이 $O(kd)$ 에서 $O(d\log d)$ 로 떨어진다 — $k$ 가 수백이면 실질적으로 자릿수 차이다. 푸리에판을 쓰면 SRFT, 아다마르판을 쓰면 SRHT라 부르고, 랜덤화 SVD 구현이 실제로 쓰는 물건이 이것이다.

5. PCA와 뭐가 다른가[편집]

둘 다 선형 사상으로 차원을 줄이지만 철학이 반대다.

PCA는 데이터를 본다. 주성분 분석은 이 데이터셋에 대해 재구성 오차 최소라는 최적성을 갖는다. 대신 공분산이나 SVD를 계산해야 하고, 데이터가 바뀌면 다시 해야 하며, 스트리밍·분산 환경에서 번거롭다.
RP는 데이터를 안 본다. 최적이 아니라 균일하다. 분산이 큰 방향이든 작은 방향이든 똑같이 $(1\pm\varepsilon)$ 로 보존한다. 행렬을 시드 하나로 재생성할 수 있어 저장할 필요조차 없고, 새 데이터가 와도 그대로 쓴다.

이 차이가 결과를 가르는 전형적인 상황이 작은 군집이다. PCA는 전체 분산을 최대화하므로 소수 표본으로 이루어진 미세 구조를 상위 성분 밖으로 밀어낼 수 있다. RP는 그 군집 안의 거리도 다른 거리와 똑같이 존중한다. 반대로 데이터가 정말로 저차원 부분공간 근처에 있다면 PCA가 훨씬 적은 차원으로 훨씬 잘 표현한다. “거리를 지킬 것이냐, 분산을 지킬 것이냐” 로 정리하면 선택이 쉬워진다.

한 가지 흔한 오해는 짚고 가야 한다. RP는 $\ell_2$ 의 도구다. $\ell_1$ 에는 이런 정리가 없고, 브링크만과 차리카르(2003)가 그 부재를 증명했다 — $\ell_1$ 에서 왜곡 $D$ 로 매장하려면 차원이 $n$ 의 다항식만큼 필요하다. 거리를 $\ell_1$ 으로 쓰면서 “JL에 의해 안전”이라고 말하면 그건 틀린 것이다.

6. 어디에 쓰이나[편집]

근사 최근접 이웃과 국소 민감 해싱. $\ell_2$ 용 p-안정 해시 $h(v)=\lfloor(\mathbf a\cdot v+b)/w\rfloor$ 의 $\mathbf a\cdot v$ 가 바로 1차원 무작위 사영이다. 해시 하나가 사영 하나이고, 그것을 $k$ 개 이어 붙이는 AND 구성이 곧 $k$ 차원 사영을 양자화한 것이다. LSH의 기계 절반이 이 문서의 내용이다.
저차원 근사와 스케칭. 랜덤화 SVD의 1단계 $Y=A\Omega$ 가 무작위 사영이고, 카운트 스케치·주파수 추정 같은 스트리밍 요약도 같은 부류다. 다만 여기서 필요한 보장은 유한 점집합의 거리 보존이 아니라 부분공간 전체에서의 노름 보존(subspace embedding)이라 요구 차원이 $O(d/\varepsilon^2)$ 로 더 크다. 두 개념을 섞어 쓰면 안 된다.
압축센싱. 무작위 행렬이 제한 등척성(RIP)을 만족한다는 증명이 JL 형태의 집중 부등식에 그물망 논증(net argument)을 얹어 나온다. “무작위 행렬이 희소 신호의 기하를 보존한다”는 문장으로 두 분야가 이어져 있다.
군집화. k-평균 군집화의 목적함수는 $O(\varepsilon^{-2}\log k)$ 차원으로 사영해도 $(1\pm\varepsilon)$ 안에서 보존된다는 결과가 있다 — $n$ 이 아니라 군집 수 $k$ 의 로그라는 점이 실용적으로 훨씬 좋다.
곱양자화·양자화 전처리. 곱양자화에서 좌표축이 데이터와 어긋났을 때 무작위 직교행렬로 한번 돌려 주는 것만으로도 성능이 오른다. 상관을 흩뜨리는 데 학습이 꼭 필요하지는 않다는 관찰이다.
커널 근사. 무작위 푸리에 특징은 무작위 주파수로 사영한 뒤 코사인을 취해 커널을 근사한다. 커널 PCA 같은 $O(N^3)$ 커널 방법을 선형 방법으로 되돌리는 표준 우회로다.

7. $k$ 를 실제로 몇으로 잡을 것인가[편집]

여기서 이론과 실무가 크게 어긋난다. 보조정리 상수를 그냥 대입해 보자. $n=10^6$ , $\varepsilon=0.1$ 이면

k \ge \frac{4\ln 10^6}{0.005 - 0.000333} \approx 1.18\times 10^4

즉 약 1만 2천 차원이다. 원래 데이터가 768차원 임베딩이었다면 “차원 축소”를 했더니 차원이 15배 늘어난 셈이다. 이 숫자가 말해 주는 것은 JL 상수가 극도로 보수적이라는 사실이다. 이유는 명확하다 — 최악의 점 배치를 가정하고, 모든 쌍이 동시에 성립할 것을 요구하며, 합집합 한계는 상관을 전혀 이용하지 않는다.

실제 데이터에서는 $k=64\sim512$ 정도로도 검색 재현율이 충분히 나오는 경우가 흔하다. 실무 감각은 대략 이렇다.

$\varepsilon$ 을 문제로부터 정하라. 최종 목표가 “상위 10개 중 8개를 맞히기”라면 필요한 것은 모든 쌍의 $\varepsilon$ 보장이 아니라 질의 근방 소수 쌍의 순위 보존이다. 요구가 훨씬 약하다.
$k$ 를 훑고 후단 지표로 판단하라. 거리 왜곡 자체가 아니라 재현율·정확도 곡선이 평평해지는 지점에서 자른다.
왜곡을 직접 재라. 표본 쌍 몇천 개의 사영 전후 거리비 히스토그램을 그리면 실제 $\varepsilon$ 분포가 바로 보인다. 이론값보다 훨씬 좁게 나오는 것을 확인하고 나면 마음이 편해진다.
$n$ 이 작으면 그냥 하지 마라. $\log n$ 이 지배하는 정리라 점이 몇만 개면 원본 차원으로 전수 계산하는 편이 빠르고 정확한 경우가 많다.

보장이 느슨하다는 것이 기법이 나쁘다는 뜻은 아니다. 다만 발표 자료에 “JL 보조정리에 의해 안전합니다”라고 쓸 때는, 실제로 안전한 이유가 정리의 상수 때문이 아니라 데이터가 최악이 아니기 때문이라는 것을 알고 쓰는 게 맞다.³

8. 관련 문서[편집]

원 논문은 1984년 Contemporary Mathematics 26권에 실린 「Extensions of Lipschitz mappings into a Hilbert space」로, 제목에 차원 축소는 물론 알고리즘의 냄새도 없다. 순수수학의 보조정리가 20년 뒤 검색 인프라의 주춧돌이 되는 경로는 이 바닥에서 드물지 않다 — 괴만스-윌리엄슨의 반올림이 SimHash가 된 것도 같은 이야기다. ↩
아클리오프타스 논문의 제목이 「Database-friendly random projections」다. 정규분포 난수 생성기를 데이터베이스 안에서 돌리기 싫었던, 대단히 실무적인 동기에서 출발한 논문이라는 뜻이다. 결과적으로 «가우시안이어야 한다»는 통념을 깬 이론 기여가 됐으니, 게으름이 정리를 낳은 사례로 종종 인용된다. ↩
반대 방향의 사고도 있다. 데이터가 최악이 아니라는 것을 정량화하려는 시도가 «내재 차원»(intrinsic dimension) 기반 결과들이고, 목표 차원이 $\log n$ 이 아니라 데이터의 두플링 차원 같은 양에 의존하는 정리들이 나와 있다. 실무 감각과 이론의 간극을 좁히는 정직한 방향인데, 여전히 상수는 크다. ↩