핵심 요소만 선택: 커널 릿지 회귀를 위한 적응형 사전 학습 (Adaptive Dictionary Learning)

커널 릿지 회귀 (KRR) 의 주요 한계 중 하나는 n 개의 샘플에 대한 커널 행렬 K_n 을 저장하고 조작하는 데 O(n^2) 의 공간이 필요하다는 점입니다. 이는 n 이 커질수록 매우 빠르게 실용적이지 않게 됩니다. Nystrom 근사는 K_n 에서 m 개의 열을 샘플링함으로써 공간 복잡도를 O(nm) 으로 줄입니다. 그러나 균일한 샘플링은 m 이 K_n 의 최대 자유도 (maximum degree of freedom) 에 비례할 때만 ε 오차 내에서 KRR 정확도를 유지합니다. 이는 높은 일관성 (coherence) 을 가진 데이터셋의 경우 O(n) 개의 열이 필요할 수 있음을 의미합니다. 커널 행렬의 릿지 레버리지 점수 (RLS) 에 따라 열을 샘플링하면 유효 차원 (effective dimension) 에 비례하는 m 으로 정확한 Nystrom 근사를 얻을 수 있지만, 정확한 RLS 를 계산하는 것도 O(n^2) 의 공간이 필요합니다. (Calandriello et al. 2016) 은 데이터셋을 점진적으로 처리하고 RLS, 유효 차원 및 Nystrom 근사를 실시간으로 업데이트하는 INK-Estimate 알고리즘을 제안했습니다. 이 알고리즘의 공간 복잡도는 유효 차원에 비례하지만, K_n 의 최대 고유값에 대한 의존성을 도입하며, 최악의 경우 이는 O(n) 입니다. 본 논문에서는 INK-Estimate 를 기반으로 하되 정규화되지 않은 RLS(unnormalized RLS) 를 사용하는 새로운 알고리즘인 SQUEAK 을 소개합니다. 결과적으로 이 알고리즘은 더 간단해지며, 정규화를 위해 유효 차원을 추정할 필요가 없으며, 정확한 RLS 샘플링보다 공간 복잡도가 오직 상수배 정도만 나쁜 성능을 달성합니다.