Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization

기술 요약: 스케치 변조(Sketched Modulation) 및 방사형 무작위화(Radial Randomization)를 통한 Bernstein–Schur 커널

1. 문제 정의

커널 방법론(예: SVM, 커널 리지 회귀, 가우시안 프로세스, 트랜스포머 어텐션 레이어)은 $N \times N$ 그램 행렬 $K_{ij} = k(x_i, x_j)$에 의존한다. 이러한 방법들을 대규모 데이터셋($N > 10^5$)으로 확장하는 것은 $O(N^2)$의 저장 공간과 $O(N^3)$의 인수분해 비용으로 인해 저해된다. 무작위 특징 맵(Random feature maps)은 $k(x, w) \approx z(x)^\top z(w)$와 같이 저차원의 $z$를 사용하여 $O(NM)$의 대안을 제공한다.

그러나 기존의 무작위 특징 구성은 구조적으로 제한되어 있다:

• **무작위 푸리에 특징(RFF)**은 보흐너 정리(Bochner's theorem)를 통해 이동 불변(shift-invariant) 커널에 적용된다.
• 다항식 스케치(Polynomial Sketches)(예: TensorSketch)는 내적(dot-product) 커널에 적용된다.
• 니스트롬(Nyström) 방법은 빠른 스펙트럼 감쇠에 의존하며 데이터 의존적이다.

본 논문은 편향된 $\mathcal{T}$-커널을 다룬다:
$$k_{\mathcal{T},b}(w, x) = \frac{(w^\top x + b)^2}{\|w - x\|^2 + \varepsilon}, \quad b \ge 0, \varepsilon > 0$$
이 커널은 정렬(alignment)(분자의 제곱 내적)과 근접성(proximity)(분모의 역제곱 거리)을 결합한다. 결정적으로, 이 커널은 (내적과 거리가 일대일 대응하는 단위 구 위를 제외하면) 이동 불변도 아니고 내적 커널도 아니다. 결과적으로 표준 RFF와 다항식 스케칭을 전체 커널에 직접 적용할 수 없으며, 이는 정확한 계산을 위해 다루기 힘든 $O(N^2)$ 그램 행렬로의 회귀를 강요한다.

2. 방법론: Bernstein–Schur 무작위 특징

저자들은 더 넓은 범주의 Bernstein–Schur 커널을 위한 무작위 특징 구성인 RAY(The $\mathcal{T}$-kernel의 무작위 근사)를 제안한다. 이 커널들은 유한 특징 커널과 완전 단조(completely monotone) 이동 불변 커널의 슈르 곱(Schur product, 원소별 곱)으로 정의된다.

방법론은 $\mathcal{T}$-커널을 두 개의 다루기 쉬운 인자로 분해한다:

1. 다항식 변조(Polynomial Modulation): $p_b(w, x) = (w^\top x + b)^2$. 이는 정확한 유한 차원 특징 맵 $p_b(x) \in \mathbb{R}^{d^2+d+1}$을 갖는다.
2. 방사형 인자(Radial Factor): $h_\varepsilon(w, x) = (\|w - x\|^2 + \varepsilon)^{-1}$. 이는 $\|w-x\|^2$에 대해 완전 단조이며, 단일 스케일 파라미터 $t \sim \text{Exp}(\varepsilon)$에 대한 가우시안 커널의 혼합으로서 Bernstein–Widder 표현을 가진다.

구성 단계:

1. 인수분해: $k_{\mathcal{T},b} = p_b \cdot h_\varepsilon$로 표현한다.
2. 방사형 샘플링: 스케일 파라미터 $t_j \sim \text{Exp}(\varepsilon)$를 샘플링한다.
3. 가우시안 RFF: 각 $t_j$에 대해, 결과적인 가우시안 커널 $e^{-t_j \|x-w\|^2}$에 RFF를 적용한다.
4. 변조 스케칭(Modulation Sketching): 정확한 $O(d^2)$ 다항식 특징 $p_b(x)$를 사용하는 대신, TensorSketch(차수-2)를 적용하여 변조를 차원 $m$으로 압축한다.
5. 텐서 곱: 최종 특징 맵 $z(x)$는 스케치된 변조와 방사형 RFF의 텐서 곱의 결합(concatenation)이다.

결과적인 특징 차원은 $D \times m$이며, 여기서 $D$는 방사형 추출 횟수이고 $m$은 스케치 크기이다. 이 차원은 정확한 다항식 특징과 관련된 $O(d^2)$ 하한선으로부터 자유롭다.

3. 주요 기여

본 논문은 다음과 같은 이론적 및 경험적 기여를 한다:

• 새로운 커널 클래스 (Bernstein–Schur): 저자들은 유한 특징 커널과 완전 단조 방사형 커널의 곱으로 형성된 커널 클래스를 정의한다. 이들은 $\mathcal{T}$-커널뿐만 아니라 이 전체 클래스에 대한 통합된 무작위 특징 추정치를 제공한다.
• 불편성(Unbiasedness) 및 분산 분석:
  • 추정기가 **불편(unbiased)**함($E[z(x)^\top z(w)] = k(x, w)$)을 증명했다.
  • "평탄한(flat)" 추정기(하나의 스케일당 하나의 주파수)에 대한 정확한 분산 공식을 도출하였으며, 이는 $(R^2 + b)^4 / (D\varepsilon^2)$에 따라 스케일링됨을 보여준다.
  • 계층적 예산 내에서 하나의 주파수를 사용하는 것($D'=1$)이 분산 최적임을 증명했다.
• 연산자 노름(Operator-Norm) 보장:
  • 그램 행렬 근사에 대한 기대 행렬-베른슈타인 연산자 노름 경계를 확립했다. $N$에 따라 스케일링되는 조잡한 원소별 경계와 달리, 이 경계는 **고유 차원(intrinsic dimension)**과 커널 및 변조 그램 행렬의 상위 고윳값에 의존한다.
  • 이 근사 하에서의 커널 리지 회귀(KRR)에 대한 결정론적 상대적 스펙트럼 안정성을 증명했다.
• 이중 무작위화 추정기 (RAY):
  • 변조 인자의 스케칭을 도입했다. 이론적 분석에 따르면, 스케칭에 대한 조건부 확률은 고유 차원 연산자 노름 보장을 유지하면서, 스케치 크기 $m$에 의해 제어되는 단일한 조정 가능한 가산 오차 항만을 추가한다.
  • 이 접근 방식이 $O(d^2)$ 특징 차원의 장벽을 제거하여 고차원에서도 확장 가능하게 함을 입증했다.
• 오차 분해: 방사형 노이즈가 정렬 인자에 의해 변조되고, 변조 오차가 방사형 근접성에 의해 국소화된다는 변조-방사형 오차 분해를 제공했다. 이는 왜 변조가 압축되었을 때도 곱이 효과적으로 작동하는지를 설명한다.

4. 실험 결과

실험은 주로 $\mathcal{T}$-커널이 진정한 비-내적(non-dot-product) 커널인 오프-스피어(off-sphere) 영역(변하는 노름을 가진 유계 볼)에서 수행되었다.

• 오프-스피어 성능: 변하는 노름을 가진 유계 볼에서, RAY는 차원 $d$가 증가하더라도 $O(1/\sqrt{D})$ 수렴율을 유지한다. 반면, 균등(uniform) 및 k-means 니스트롬 방법은 매칭된 랜드마크 수를 사용하더라도 $d$가 증가함에 따라 성능이 크게 저하된다.
• 비용 매칭 비교: 매칭된 표현 비용으로 비교했을 때, 적응형 니스트롬 방법(데이터 의존적)은 중간 규모의 $N$에서 RAY보다 더 정확할 수 있다. 그러나 RAY는 니스트롬이 제공할 수 없는 데이터 독립적, 불편(unbiased), 스트리밍 특징을 제공한다.
• 결합된 타겟 선호도: 정렬과 근접성을 모두 요구하는 합성 타겟에 대한 통제된 테스트에서, $\mathcal{T}$-커널(RAY로 근사됨)은 하나의 요소만을 모델링하는 커널(Gaussian, IMQ, 또는 Polynomial 단독)보다 우수한 성능을 보였다. 이는 커널의 귀납적 편향(inductive bias)을 검증한다.
• 선형 시간 어텐션: RAY를 선형 시간 어텐션 프리미티브로 적용했다. 특징 차원 $M$이 증가함에 따라 중앙값 오차가 감소하면서 정확한 $\mathcal{T}$-어텐션을 성공적으로 근사하는 동시에, $O(NM)$ 메모리를 유지하고 랜드마크 기반 방법으로는 불가능한 인과적(causal), 스트리밍 디코딩을 가능하게 했다.
• 대규모 학습: 1,100만 개의 예시가 있는 HIGGS 데이터셋에서, RAY는 그램 행렬을 저장하는 것이 불가능한 스트리밍 환경에서 프라이멀 학습(primal training)을 가능하게 했으며, 매칭된 예산에서 정확한 변조 한계를 능가했다.

5. 의의 및 주장

저자들은 세 가지 주요 분야에서 의의를 주장한다:

1. 구조적 간극 해소: 이동 불변도 아니고 내적 커널도 아닌 커널을, (스케칭 및 RFF와 같은) 표준 도구에 적합한 구성 요소로 분해함으로써 새로운 무작위 특징 구성을 제공한다.
2. 데이터 의존성 없는 확장성: 비정상(non-stationary) 커널에 대해 니스트롬의 $O(N^2)$ 그램 행렬 및 $O(d^2)$ 특징 차원의 장벽을 동시에 피하는 스트리밍, 데이터 독립적 대안을 제시한다.
3. 이론적 엄밀성: 단순한 원소별 경계를 넘어 구조화된 커널에 대한 근사 오차를 더 미묘하게 이해하기 위해 고유 차원에 의해 제어되는 연산자 노름 보장을 제공한다.

저자들은 RAY가 스트리밍 및 대규모 설정에서 매우 효과적이지만, 데이터 의존성이 허용되는 고정 예산의 중간 규모 $N$ 문제에서는 적응형 니스트롬 방법이 여전히 더 우수할 수 있음을 겸허히 언급한다. 이 방법은 안정성을 보장하기 위해 유계 노름 입력을 요구하며, 다항식 인자로 인해 분산 상수가 표준 RFF보다 높다.