커널 트릭

커널 트릭

커널 트릭(Kernel Trick)은 알고리즘이 데이터의 내적만을 필요로 할 때, 명시적인 고차원 특징 공간 \(\phi(x)\)으로의 매핑 없이 커널 함수 \(K(x,z) = \langle\phi(x),\phi(z)\rangle\)로 대체하는 기법이다.

핵심

• 내적 연산만 필요한 알고리즘(SVM, PCA, 회귀 등)에 적용 가능하다
• 명시적 매핑 비용이 \(O(d^p)\)인 \(p\)차 다항식 특징을 \(O(d)\) 시간에 계산할 수 있다
• 무한 차원 특징 공간(가우시안 커널)에도 효율적으로 적용된다
• 표현자 정리와 함께 커널 방법의 이론적 토대를 형성한다
• 커널 행렬(Gram matrix) \(K_{ij} = K(x^{(i)}, x^{(j)})\)로 알고리즘을 재공식화한다

수식

\[K(x,z) = \phi(x)^T\phi(z)\]