Random features for Grassmannian kernel approximation with bounded rank-one projections

기술 요약: 유계된 랭크-원 투영을 이용한 그라스만니안 커널 근사화를 위한 랜덤 특징량

문제 정의

많은 지도 학습 및 비지도 학습 작업에서 데이터 클래스나 클러스터는 고차원 공간의 개별 유클리드 점이 아니라 저차원 부분 공간으로 자연스럽게 표현됩니다. 이는 그라스man니안 다양체 $\mathcal{G}(k, n)$(즉, $\mathbb{R}^n$ 내의 모든 $k$차원 부분 공간의 집합) 상에서 연산할 필요성을 제기합니다. 커널 머신(예: SVM)은 양의 정치적(positive-definite) 커널(예: 투영 또는 비네-코시 커널)을 사용하여 이러한 데이터에 대해 효과적으로 학습할 수 있지만, 확장성 문제가 발생합니다. 표준 커널 방법은 $N \times N$ 그램 행렬을 구축하고 저장해야 하므로 $O(N^2)$의 메모리와 계산 비용이 발생하며, 이는 대규모 데이터셋에서는 매우 비효율적입니다.

그라스만니안 커널을 랜덤 특징량으로 근사하려는 기존의 시도들은 두 가지 주요 한계점에 직면해 있습니다:

1. 밀집된 랜덤 투영(Dense Random Projections): 부분 공간을 밀집된 가우시안 행렬에 직교 투영하는 방식으로 임베딩하는 것은 특징당 $O(n^2)$의 저장 공간과 계산량을 요구하여 고차원에서 실용적이지 않습니다.
2. 유계되지 않은 랭크-원 투영(Unbounded Rank-One Projections, ROP): ROP는 계산 비용은 더 저렴하지만($O(kn)$), 이차 측정값$a^\top P b$를 기반으로 할 때 헤비 테일(heavy-tailed) 분포(sub-Weibull)를 보입니다. 이는 수렴 속도를 늦추어, intrinsic dimension에 비례하는 수의 특징량만으로는 전체 그라스만니안 다양체에 대한 균등 근사 보장을 달성하는 것을 방해합니다.

방법론

저자들은 확장 가능한, 균등한 커널 근사화를 달라는 **랭크-원 투영(ROP)**과 유계된 비선형 변환을 결합한 랜덤 특징량 패밀리를 제안합니다.

1. 랭크-원 투영 (ROP)

직교 기저 $U$(여기서 $P = UU^\top$)로 표현되는 부분 공간 $P \in \mathcal{G}(k, n)$에 대해, 이 방법은 $m$개의 독립적인 랭크-원 이차 측정을 사용하여 부분 공간을 탐사합니다:
$$\psi_{\text{rop}}(U) = \left( a_i^\top P b_i \right)_{i=1}^m$$
여기서 $a_i, b_i \sim \text{i.i.d. } \mathcal{N}(0, I_n)$입니다. 이는 특징당 계산 비용을 $O(kn)$으로 줄이며, ($U^\top a_i$와$U^\top b_i$를 계수화한 후) 저장량을$O(kn)$으로 줄여줍니다.

2. 유계된 비선형 변환

저자들은 유계되지 않은 ROP의 헤비 테일 분포를 제어하고 균등 수렴을 보장하기 위해 $\psi_{\text{rop}}$를 유계된 비선형 함수 $g(\cdot)$와 합성합니다:
$$\psi_g(U) = g(\psi_{\text{rop}}(U))$$
두 가지 특정 변환이 분석되었습니다:

• 이진 특징량 (Binary Features): sign 함수를 사용하여 $g(\lambda) = \text{sign}(\lambda)$를 적용합니다. 이는 이진 랜덤 특징량 $\psi_\pm \in \{\pm 1\}^m$을 생성하며, 압축적인 1비트 저장과 빠른 비트 연산을 가능하게 합니다.
• 주기적 특징량 (Periodic Features): 복소 지수를 사용하여 $g(\lambda) = \exp(i\omega \lambda)$를 적용합니다. 이는 Random Fourier Features와 유사한 주기적 랜덤 특징량 $\psi_\circ$를 생성합니다.

3. 구조화된 투영 (Structured Projections)

계산 복잡도를 더욱 줄이기 위해, 저자들은 밀집 가우시안 탐사 벡터를 빠른 왈쉬-하다마르 변환(fast Walsh-Hadamard transforms)과 랜덤 대각 사인 행렬의 합성으로 구성된 구조화된 랜덤 행렬로 대체합니다(Choromanski et al., 2016에서 영감을 받음). 이는 통계적 특성을 유지하면서 계산 복잡도를 $O(kmn)$에서$O(km \log n)$으로 줄여줍니다.

주요 기여

이론적 보장

본 논문은 이러한 유계된 랜덤 특징량의 경험적 내적이 특정, 잘 정의된 회전 불변 그라스만니안 커널의 비편향 추정량임을 입증합니다. 결정적으로, 저자들은 고정된 차원 $k$를 가진 모든 부분 공간에 대해 **균등 근사 경계(uniform approximation bounds)**를 증명합니다.

• 샘플 복잡도: 이들은 $m = O(kn)$개의 랜덤 특징량(로그 인자 제외)이 전체 그라스만니안 다양체에 대한 근사 오차를 균등하게 제어하기에 충분함을 보여줍니다. 이는 주변 차원$n$과 부분 공간 차원$k$에 선형적으로 비례하며, 이는$O((kn)^2)$의 요구사항보다 크게 개선된 것입니다.
• 이진 커널 ($\kappa_\pm$): 이진 특징량의 기대 커널은 양의 정치적이며 회전 불변임이 입증되었습니다. 일반적인 $k$에 대한 폐쇄형 표현은 존재하지 않지만, 다음과 같이 반-명시적으로 특징지어집니다:
  $$\kappa_\pm(U, V) = 1 - \frac{2}{\pi} \mathbb{E}[\angle(P g, Q g)]$$
  여기서 $g \sim \mathcal{N}(0, I_n)$이고 $\angle(\cdot, \cdot)$은 벡터 사이의 각도입니다. $k=1$인 경우, 폐쇄형 $(1 - 2\theta/\pi)^2$이 도출됩니다.
• 주기적 커널 ($\kappa_\circ$): 주기적 특징량의 기대 커널은 주각(principal angles) $\{\theta_j\}_{j=1}^k$에 의존하는 폐쇄형 표현을 가집니다:
  $$\kappa_\circ(U, V) = \prod_{j=1}^k (1 + \omega^2 \sin^2 \theta_j)^{-1}$$
  저자들은 주파수 파라미터 $\omega$에 따른 $\kappa_\circ$의 거동을 분석합니다:
  • 큰 $\omega$: $\kappa_\circ$는 역 비네-코시 커널처럼 동작하며, 작은 주각에 민감합니다.
  • 작은 $\omega$: $\kappa_\circ$는 투영 RBF(Radial Basis Function) 커널, $\exp(-\frac{1}{2}\omega^2 \|P-Q\|_F^2)$를 근사합니다.

계산 복잡도

제안된 방법들은 상당한 효율성 이점을 제공합니다:

• 메모리: 구조화되지 않은 유계 ROP의 저장 공간은 탐사 벡터를 위해 $O(mn)$입니다. 균등 근사를 보장하기 위해$m = O(kn)$을 대입하면, 전체 메모리 복잡도는$O(kn^2)$가 됩니다(논문에서는$O(\delta^{-2}(kn^2))$로 구체적으로 도출됨). 이는 밀집 투영이$O(mn^2)$의 저장 공간을 요구하는 것($O(k^3 n^3)$ 규모)과는 다릅로 차이가 있습니다.
• 계산: 구조화되지 않은 유계 ROP의 계산 복잡도는 $O(kmn)$입니다.$m = O(kn)$일 때, 이는$O(k^2 n^2)$로 스케일링됩니다. 이는 밀집 투영 방법의$O(k^2 n^3)$ 복잡도보다 현저히 낮습니다.
• 저장: 이진 특징량은 부분 공간당 단 $O(m)$ 비트만을 필요로 합니다.

실험 결과

저자들은 합성 실험과 ETH-80 데이터셋(다양한 시점에서의 시각적 객체 이미지)을 사용하여 접근 방식을 검증합니다.

1. 커널 근사: 실험을 통해 유계 ROP가 밀집 투영보다 훨씬 낮은 계산 및 메모리 비용으로 타겟 커널에 수렴함을 확인했습니다.
2. 구조화된 임베딩: 구조화된 하다마르-대각 스케치의 경험적 분석을 통해, $S=3$개의 블록을 사용하는 것이 가우시안 분포를 근사하는 데 충분함을 보여줌으로써 빠른 변환의 사용을 검증했습니다.
3. 분류 성능:
   • 상위 클래스 분류(8-way) 및 객체 분류(80-way) 작업에서, 제안된 랜덤 특징량(구조화되지 않은 방식 및 구조화된 방식 모두)은 정확한 커널 방법과 비교할 만한 분류 정확도를 달-성했습니다(특정 작업 및 커널에 따라 트레이드오프가 존재함).
   • 특히, 오버샘플링 비율 $\rho = m/(nk)$가 $0.05$($\text{원래 기저 크기의 } 5%$)만큼 낮은 구조화된 임베딩은 정확한 커널 평가에 비해 계산 시간을 수십 배 단축하면서도 높은 정확도를 보여주었습니다. 예를 들어, 80-way 분류 작업에서 구조화된 방법은 총 실행 시간을 약 52.9초(정확한 투영 커널)에서 ~1.9초로 단축했습니다. 그러나 이러한 속도 향상은 정확도가 98.75%(정확한 방식)에서 83.00%(구조화된 방식)로 눈에 띄게 감소하는 트레이드오프를 동반했습니다.

의의 및 주장

본 논문은 고전적인 그라스만니안 커널에 대한 실용적이고 확장 가능한 대안을 제공한다고 주장합니다. 랭크-원 투영과 유계된 비선형성을 결합함으로써, 저자들은 다음을 달성할 수 있음을 보여주었습니다:

1. 높은 정확도로 그라스만니안 기하학을 복구할 수 있음.
2. intrinsic dimension에 선형적으로 스케일링되는 수의 특징량을 사용하여 다양체에 대한 균등 근사 보장을 달성할 수 있음.
3. 메모리 및 계산 요구 사항을 획기적으로 줄여, 대규모 고차원 애플리케이션에서 커널 기반 학습을 가능하게 함.

이 연구는 이론적 커널 방법과 실용적 확장성 사이의 간극을 메우며, 근사 오차와 계산 비용 사이의 트레이드오프를 랜덤 특징량의 수와 비선형 변환의 선택을 통해 명시적으로 제어할 수 있는 프레임워크를 제공합니다.