무작위 푸리에 특징

1. 개요[편집]

무작위 푸리에 특징 Random Fourier Features (RFF)
제안	Rahimi & Recht (2007)
적용 대상	이동불변 연속 양정부호 커널 k(x−y)
근거 정리	보흐너 정리 + 몬테카를로
특징 사상	z(x) = √(2/D)·cos(ωᵀx + b), ω ~ p, b ~ U[0,2π]
수렴률	O(1/√D) — 몬테카를로 그대로
얻는 것	O(n²) 그람 행렬 → O(nD) 설계행렬

커널 트릭이 “특징을 계산하지 말고 내적만 써라”였다면, 이건 그걸 도로 물린다. 특징을 계산하되, 아무렇게나 계산한다.

무작위 푸리에 특징(random Fourier features, RFF)은 이동불변 커널 $k(\mathbf x,\mathbf y)=\kappa(\mathbf x-\mathbf y)$ 를, 무작위로 뽑은 주파수로 만든 $D$ 차원 명시적 특징 사상 $\mathbf z:\mathbb R^d\to\mathbb R^D$ 의 내적으로 근사해 $\mathbf z(\mathbf x)^{\mathsf T}\mathbf z(\mathbf y)\approx k(\mathbf x,\mathbf y)$ 로 만드는 기법이다. 라히미와 레흐트가 2007년에 제안했다.

동기는 단순하고 절박하다. 커널 방법의 비용은 표본 수 $n$ 에 묶여 있다 — 그람 행렬이 $O(n^2)$ 메모리, 정확한 해가 $O(n^3)$ 이다. $n=10^6$ 이면 그람 행렬만 배정밀도로 8 TB라 존재 자체가 불가능하다. 그런데 $\mathbf z$ 를 명시적으로 만들어 버리면 그 뒤로는 그냥 선형 모형이다. 설계행렬 $Z\in\mathbb R^{n\times D}$ 는 $O(nD)$ 이고, 정규방정식은 $O(nD^2)$ 이며, 확률적 경사하강법도 미니배치 스트리밍도 다 된다. 표본 수에 선형인 커널 학습이 되는 것이다.

커널 트릭이 유한차원 특징을 무한차원으로 밀어 올린 기법이라면, RFF는 그 무한차원을 다시 $D$ 차원으로 눌러 담는다. 왕복 여행처럼 보이지만 출발지와 도착지가 다르다 — 원래 특징 차원은 폭발적이었고, $D$ 는 우리가 고른다.

2. 보흐너 정리 — 커널이 확률분포가 되는 지점[편집]

보흐너 정리(Bochner, 1932). 연속 함수 $\kappa:\mathbb R^d\to\mathbb R$ 가 양정부호일 필요충분조건은, 그것이 어떤 유한 비음 측도 $\mu$ 의 푸리에 변환인 것이다.

$$\kappa(\boldsymbol\delta) = \int_{\mathbb R^d} e^{\,i\boldsymbol\omega^{\mathsf T}\boldsymbol\delta}\, d\mu(\boldsymbol\omega)$$

여기에 커널을 $\kappa(\mathbf 0)=1$ 로 규격화하면 $\mu$ 는 전체 질량이 1인 확률측도가 된다. 밀도 $p(\boldsymbol\omega)$ 를 갖고 $\kappa$ 가 실함수이면 $p$ 는 원점 대칭이므로 허수부가 상쇄되어

$$k(\mathbf x,\mathbf y) = \mathbb E_{\boldsymbol\omega\sim p}\Big[\cos\big(\boldsymbol\omega^{\mathsf T}(\mathbf x-\mathbf y)\big)\Big]$$

이 된다. 커널값이 기댓값이 되었다. 기댓값이면 몬테카를로 방법으로 때릴 수 있고, 그게 아이디어의 전부다.

남은 문제는 $\cos(\boldsymbol\omega^{\mathsf T}(\mathbf x-\mathbf y))$ 를 $\mathbf x$ 만의 함수와 $\mathbf y$ 만의 함수의 곱으로 분리하는 것이다. 두 가지 방법이 있다.

(a) 위상 오프셋 판본. $b\sim U[0,2\pi]$ 를 독립으로 뽑고 $\zeta(\mathbf x)=\sqrt2\cos(\boldsymbol\omega^{\mathsf T}\mathbf x+b)$ 라 두면, 곱각공식과 $\mathbb E_b[\cos(\theta+2b)]=0$ 에서

$$\mathbb E_{\boldsymbol\omega,b}\big[\zeta(\mathbf x)\zeta(\mathbf y)\big] = \mathbb E_{\boldsymbol\omega}\Big[\cos\big(\boldsymbol\omega^{\mathsf T}(\mathbf x-\mathbf y)\big)\Big] = k(\mathbf x,\mathbf y)$$

가 나온다. $D$ 개의 독립 표본을 평균 내면

$$\mathbf z(\mathbf x)=\sqrt{\tfrac{2}{D}}\Big[\cos(\boldsymbol\omega_1^{\mathsf T}\mathbf x+b_1),\ \dots,\ \cos(\boldsymbol\omega_D^{\mathsf T}\mathbf x+b_D)\Big]^{\mathsf T}$$

이고 $\mathbb E[\mathbf z(\mathbf x)^{\mathsf T}\mathbf z(\mathbf y)]=k(\mathbf x,\mathbf y)$ 다. 코드로 열 줄이면 끝난다.

(b) 코사인·사인 짝 판본. $b$ 없이 $\boldsymbol\omega_j$ 하나마다 $[\cos(\boldsymbol\omega_j^{\mathsf T}\mathbf x),\ \sin(\boldsymbol\omega_j^{\mathsf T}\mathbf x)]$ 두 좌표를 만든다. 삼각함수 덧셈정리로 곱의 합이 곧바로 $\cos(\boldsymbol\omega_j^{\mathsf T}(\mathbf x-\mathbf y))$ 가 되므로 마찬가지로 불편추정량이다.

둘 다 교과서에 있지만 분산은 같지 않다. (a)는 $b$ 라는 추가 난수가 들어가는 만큼 분산이 크고, 같은 특징 차원에서 (b)가 대체로 더 정확하다는 것이 서덜랜드·슈나이더(2015)의 분석 결과다.¹ 논문 수식은 (a)로 쓰여 있지만 라이브러리 구현이 (b)를 쓰는 경우가 많은 것이 이 때문이다.

3. 커널과 분포의 사전[편집]

$p$ 는 커널의 푸리에 변환이므로, 커널을 고르면 샘플러가 자동으로 정해진다. 실무에서 쓰는 짝은 몇 개 안 된다.

커널 $\kappa(\boldsymbol\delta)$	주파수 분포 $p(\boldsymbol\omega)$	비고
가우시안 RBF $e^{-\lVert\delta\rVert^2/2\sigma^2}$	$\mathcal N(\mathbf 0,\ \sigma^{-2}I)$	난수 생성 한 줄
라플라시안 $e^{-\lambda\lVert\delta\rVert_1}$	코시 (좌표별 독립)	꼬리가 두꺼워 큰 $\boldsymbol\omega$ 가 자주 나온다
코시 커널 $\prod_i 2/(1+\delta_i^2)$	라플라스 (좌표별 독립)	위 짝의 쌍대
마테른 $\nu$	자유도 $2\nu$ 의 다변량 $t$	$\nu\to\infty$ 에서 가우시안으로

가우시안 ↔ 가우시안이 가장 유명한 짝이고,² 폭이 좁은 커널($\sigma$ 작음)이 넓은 주파수 분포에 대응한다는 반비례 관계가 여기서 그대로 보인다. 커널이 좁을수록 흉내 내야 할 고주파가 많아지고, 따라서 같은 정확도에 더 큰 $D$ 가 필요하다. 이 관계는 재생 커널 힐베르트 공간 쪽에서 보면 더 선명하다 — RKHS 노름의 분모에 있는 스펙트럼 밀도가 바로 이 $p$ 다.

4. 수렴률 — 몬테카를로의 저주와 축복[편집]

$\mathbf z(\mathbf x)^{\mathsf T}\mathbf z(\mathbf y)$ 는 $[-1,1]$ 에 갇힌 독립 확률변수 $D$ 개의 평균이므로, 호에프딩 부등식이 곧바로 적용된다. 고정된 한 쌍 $(\mathbf x,\mathbf y)$ 에 대해

$$\Pr\Big[\big\lvert \mathbf z(\mathbf x)^{\mathsf T}\mathbf z(\mathbf y) - k(\mathbf x,\mathbf y)\big\rvert \ge \varepsilon\Big] \le 2\exp\!\Big(-\frac{D\varepsilon^2}{4}\Big)$$

즉 오차는 $O(1/\sqrt D)$ 로 줄어든다. 좋은 소식은 이 지수에 입력 차원 $d$ 가 없다는 것이고, 나쁜 소식은 $1/\sqrt D$ 가 몬테카를로 특유의 굼뜬 속도라는 것이다. 정확도를 10배 올리려면 특징을 100배 늘려야 한다.

한 쌍이 아니라 영역 전체에서 균등하게 보장하려면 얘기가 조금 길어진다. 지름 $\ell$ 인 콤팩트 집합 $\mathcal M\subset\mathbb R^d$ 위에서 라히미–레흐트가 준 균등 경계는 대략

$$\Pr\Big[\sup_{\mathbf x,\mathbf y\in\mathcal M}\big\lvert \mathbf z(\mathbf x)^{\mathsf T}\mathbf z(\mathbf y) - k(\mathbf x,\mathbf y)\big\rvert \ge \varepsilon\Big] \ \lesssim\ \Big(\frac{\sigma_p\,\ell}{\varepsilon}\Big)^{2}\exp\!\Big(-\frac{D\varepsilon^2}{4(d+2)}\Big)$$

꼴이다($\sigma_p^2=\mathbb E_p\lVert\boldsymbol\omega\rVert^2$). 여기서 읽어야 할 것은 상수가 아니라 의존성의 형태다.

• 필요한 $D$ 는 $\varepsilon$ 에 대해 $1/\varepsilon^2$ 로 커진다 — 몬테카를로 그대로.
• 입력 영역의 지름 $\ell$ 은 로그로만 들어간다. 데이터 범위가 10배 넓어져도 $D$ 는 약간만 커지면 된다. $\varepsilon$-그물 논법의 부피 항이 지수 안의 $\exp$ 에 잡아먹히기 때문이다.
• 차원 $d$ 는 지수의 분모에 선형으로 들어가므로 $D=\Omega\big(d\varepsilon^{-2}\log(\sigma_p\ell/\varepsilon)\big)$ 정도가 요구된다. 차원의 저주가 있긴 하지만 다항식 수준이고, 이게 RFF가 고차원에서도 쓸 만한 이유다.
• 주파수 분포의 산포 $\sigma_p$ 와 지름 $\ell$ 이 항상 곱으로만 등장한다. 데이터를 표준화하는 것과 커널 폭을 조정하는 것이 이론적으로 같은 손잡이라는 뜻이다.

원 논문의 상수에는 오류가 있었고 나중에 고쳐졌다는 것도 알아 둘 만하다.³ 실무에서 저 경계로 $D$ 를 정하는 사람은 없다 — 대개 $D=10^3\!\sim\!10^4$ 을 놓고 검증 성능이 평평해지는 지점을 찾는다.

5. 무엇을 벌었는가[편집]

항목	정확한 커널 모형	RFF + 선형 모형
메모리	그람 행렬 $O(n^2)$	설계행렬 $O(nD)$
학습	$O(n^3)$ (분해)	$O(nD^2 + D^3)$, SGD면 $O(nD)$/에폭
예측 1건	$O(n_{\text{SV}})$ 회 커널 평가	$O(dD)$ 곱셈
모형 크기	서포트 벡터 좌표 전체	난수 시드 + 계수 $D$ 개
스트리밍	불가 (전체 그람 필요)	가능 (특징이 데이터와 무관)

마지막 두 줄이 실전에서 제일 크다. 특징 사상이 데이터를 전혀 보지 않으므로 난수 시드만 공유하면 어느 기계에서든 같은 $\mathbf z$ 를 재현할 수 있고, 모형을 배포할 때 학습 데이터를 들고 다닐 필요가 없다. 커널 SVM이 임베디드 배포에서 즉사하는 바로 그 지점을 정확히 해결한다.

대신 잃는 것도 명확하다. $\mathbf z$ 는 조밀 벡터라 희소행렬 구조를 파괴하고, 원래 입력이 희소했다면 $D$ 차원 조밀 행렬이 오히려 더 클 수도 있다. 그리고 이동불변 커널에만 쓸 수 있다 — 문자열 커널이나 그래프 커널에는 보흐너 정리를 적용할 대상 자체가 없다.

6. 나이스트룀과의 비교[편집]

같은 벽을 때리는 다른 망치가 나이스트룀 근사(Williams & Seeger, 2001)다. 학습점 중 $m$ 개를 지표점으로 골라 $K\approx C W^{-1}C^{\mathsf T}$ 로 저계수 근사한다.

	무작위 푸리에 특징	나이스트룀 근사
데이터 의존	없음 (커널만 봄)	있음 (지표점을 데이터에서 고름)
적용 범위	이동불변 커널만	임의의 PSD 커널
특징 생성 비용	$O(dD)$	$W^{-1/2}$ 를 위한 $O(m^3)$
근사 오차	$O(1/\sqrt D)$	스펙트럼이 빨리 죽으면 $O(1/m)$ 급까지
스트리밍·사전계산	자연스러움	지표점 확정 후에만

스펙트럼이 빨리 감쇠하는 실제 데이터에서는 같은 차원의 나이스트룀이 RFF보다 대체로 정확하다(Yang 외, 2012). 이유는 직관적이다 — 나이스트룀은 데이터가 실제로 놓인 곳에 기저를 배치하지만, RFF는 데이터를 안 보고 주파수를 뿌리므로 아무도 살지 않는 영역에도 표현력을 낭비한다. 그 대신 RFF는 데이터가 오기 전에 특징을 만들어 둘 수 있고, 커널만 알면 되므로 분산 환경에서 조율 비용이 0이다. 선택 기준은 정확도가 아니라 워크플로인 경우가 많다.

7. 개선 판본들[편집]

$1/\sqrt D$ 를 이기려는 시도가 2010년대 내내 이어졌고, 대부분 “무작위성을 조금 덜 무작위하게” 만드는 방향이다.

• 직교 랜덤 특징(ORF, Yu 외 2016). $\boldsymbol\omega_j$ 들을 독립으로 뽑는 대신 서로 직교하도록 만든다(가우시안 행렬을 QR 분해해 방향을 직교화하고 길이는 카이 분포에서 다시 뽑음). 커널 추정의 평균제곱오차가 엄격히 줄어든다는 것이 증명돼 있다. 구현이 QR 분해 한 번 추가하는 것뿐이라 가성비가 좋다.
• 구조화 판본(SORF · Fastfood). 조밀 가우시안 행렬 $\Omega\in\mathbb R^{D\times d}$ 를 아다마르 변환과 대각 부호 행렬의 곱 $HD_1HD_2HD_3$ 같은 구조로 대체한다. 행렬-벡터 곱이 $O(D\log d)$, 메모리가 $O(D)$ 로 떨어져서 $D$ 를 크게 키울 때 결정적이다. 통계적 성질은 거의 손실이 없다.
• 준몬테카를로 특징(Avron 외, 2016). $p$ 에서 난수를 뽑는 대신 저불일치 수열을 변환해 쓴다. 준몬테카를로의 통상적 이득 그대로 $1/\sqrt D$ 보다 빠른 감쇠를 얻고, 차원이 낮을수록 이득이 크다.
• 레버리지 점수 샘플링. $p$ 대신 릿지 레버리지 함수로 재가중된 분포에서 $\boldsymbol\omega$ 를 뽑으면, 같은 일반화 성능에 필요한 $D$ 가 크게 줄어든다. 데이터를 보는 RFF라서 나이스트룀 쪽으로 반쯤 건너간 셈이고, 실제로 두 계열의 이론적 간극이 이 지점에서 좁혀졌다.

8. 실무 요령[편집]

• 입력 표준화가 먼저다. 위 균등 경계가 $\sigma_p\ell$ 이라는 곱에만 의존한다는 것이 이유다. 스케일이 제각각이면 $\ell$ 이 특정 변수에 끌려가고, RBF 커널의 고질적 실패 모드가 그대로 재현된다.
• $D$ 는 성능이 평평해질 때까지 키운다. 경험적으로 $D\approx 5d\!\sim\!20d$ 부터 쓸 만해지고, $D>n$ 이 되면 애초에 정확한 커널을 푸는 게 낫다.
• 난수는 반드시 시드로 고정해 저장한다. 특징 행렬을 저장할 필요는 없지만 시드를 잃으면 모형이 통째로 무의미해진다. 실제로 자주 나는 사고다.
• 절편·정규화를 잊지 말 것. $\mathbf z$ 는 이미 $\lVert\mathbf z(\mathbf x)\rVert^2\approx k(\mathbf x,\mathbf x)=1$ 로 규격화돼 있으므로, 그 위의 선형 모형에 거는 $\ell_2$ 벌점이 커널 능형회귀의 $\lambda$ 와 직접 대응한다. 티호노프 정규화를 빼면 $D$ 를 키운 만큼 과적합한다.
• 깊은 모형과의 관계를 오해하지 말 것. $\mathbf z(\mathbf x)$ 는 “가중치를 무작위로 고정한 1층 신경망 + 코사인 활성화”와 형태가 같고, 무한 폭 신경망의 접선 커널 논의와 계보가 이어진다. 다만 RFF는 주파수를 학습하지 않는다 — 그 한 가지 차이가 표현 학습과 커널 근사를 가르는 지점이고, 심층 학습이 이기는 자리도 정확히 거기다.

9. 관련 문서[편집]

• 커널 트릭 · 재생 커널 힐베르트 공간 · 보흐너 정리
• 나이스트룀 근사 · 저랭크 근사 · 랜덤화 SVD
• 무작위 사영 · 몬테카를로 방법 · 준몬테카를로
• 푸리에 변환 · 고속 푸리에 변환
• 서포트 벡터 머신 · 서포트 벡터 회귀 · 커널 PCA
• 가우시안 프로세스 · 능형회귀 · 티호노프 정규화

10. Footnotes[편집]

1. Sutherland, D. J. & Schneider, J. (2015). “On the error of random Fourier features.” UAI. 위상 오프셋 $b$ 를 쓰는 판본이 코사인·사인 짝 판본보다 분산이 크다는 것을 정량화한 논문이다. 8년 동안 다들 논문 수식을 그대로 옮겨 적으며 (a)를 썼는데, 사실 (b)가 공짜로 더 나았다는 결론. 이런 종류의 “아무도 확인 안 한 기본값”은 이 바닥에 생각보다 많다. ↩

2. “가우시안의 푸리에 변환은 가우시안”이라는, 학부 신호처리 시간에 배우고 잊어버리는 그 사실이 여기서 밥값을 한다. 보흐너 정리 자체는 1932년 조화해석의 결과로 기계학습과 아무 관계 없이 70년 넘게 존재했고, 라히미·레흐트가 한 일은 “이거 몬테카를로로 때릴 수 있는데?”라고 말한 것이다. 좋은 논문의 절반은 이미 있는 정리에서 샘플러를 발견하는 일이다. ↩

3. 원 논문의 균등 경계에 등장하는 상수 $2^8$ 유도에 결함이 있었고, 위 각주의 후속 논문이 이를 지적하며 고쳤다. 결론의 형태($D=\Omega(d\varepsilon^{-2}\log(\sigma_p\ell/\varepsilon))$)는 바뀌지 않았으므로 실무에는 영향이 없다. 다만 “NeurIPS Test of Time 상을 받은 논문에도 상수 오류가 있다”는 사실은, 논문 부등식의 상수를 그대로 코드에 옮기기 전에 한 번 더 의심하라는 교훈으로 쓸 만하다. ↩