14. Kernels

14.1. Introduction

우리가 다룰 오브젝트를 고정 길이 특성 벡터로 나타낼 수 없다면 어떻게 할 것인가? 예를 들어 텍스트 문서나 단백질 시퀀스 등은? 한 방법은 생성적 모델을 정의한 뒤 유추된 잠재 표현이나 모델의 매개변수를 특성으로 삼아 표준적인 방법들을 이용하는 것이다.

다른 방법은 오브젝트를 특성 벡터로 전처리하지 않고, 오브젝트간의 유사성을 측정하는 커널 함수 \kappa(\mathbf{x}, \mathbf{x}^{\prime}) \geq 0을 정의한 뒤, 오로지 커널 함수에만 의존하는 몇 개의 알고리즘을 사용하는 것이다. 이렇게 하면 우리가 다루는 오브젝트의 내부 표현에 직접 접근할 필요가 없다.

14.2. Kernel functions

커널 함수는 오브젝트 공간 \mathcal{X} 내의 오브젝트 2개 \mathbf{x}, \mathbf{x}^{\prime}에 대해 대칭성과 비음수성을 만족하는 실변수 함수 \kappa(\mathbf{x}, \mathbf{x}^{\prime})을 말한다. 따라서 이는 유사성의 척도로 볼 수 있다.

14.2.1. RBF kernels

제곱지수커널(가우시안 커널)은 \kappa(\mathbf{x}, \mathbf{x}^{\prime}) = e^{-\frac{1}{2} (\mathbf{x} - \mathbf{x}^{\prime})^{T} \mathbf{\Sigma}^{-1} (\mathbf{x} - \mathbf{x}^{\prime})} 으로 정의된다. \mathbf{\Sigma}가 대각 행렬이면 이는 \kappa(\mathbf{x}, \mathbf{x}^{\prime}) = e^{-\frac{1}{2} \sum_{j=1}^{D} \frac{1}{\sigma_{j}^{2}} (x_{j} - x_{j}^{\prime})^{2}}로 나타낼 수 있는데 \sigma_{j}는 차원 j의 특성 길이 비율로 나타낼 수 있다. \sigma_{j} = \infty면 해당 차원은 무시되며, 이를 자동 연관성 판별 커널이라 한다. \mathbf{\Sigma}가 구형이라면, 커널 함수는 등장 커널인 방사형 기저 함수 커널 \kappa(\mathbf{x}, \mathbf{x}^{\prime}) = e^{-\frac{\lVert \mathbf{x} - \mathbf{x}^{\prime} \rVert^{2}}{2 \sigma^{2}}}이 되며 이 때 \sigma^{2}대역폭이라 불린다. 이는 두 오브젝트간 거리에만 의존하는 함수이다.

14.2.2. Kernels for comparing documents

문서간의 유사도는 어떻게 정할까? x_{ij}를 단어 j가 문서 \mathbf{x}_{i}에 등장하는 횟수라 할 때 코사인 유사도 \kappa(\mathbf{x}_{i}, \mathbf{x}_{j}) = \frac{\mathbf{x}_{i}^{T} \mathbf{x}_{j}}{ \lVert \mathbf{x}_{i} \rVert_{2} \lVert \mathbf{x}_{j} \rVert_{2} }를 정의한다. 이는 두 문서를 벡터로 표현했을 때 그 사잇각의 코사인을 측정한다. 0이면 벡터가 직교하며 공통된 단어가 없게 된다.

안타깝게도 이 간단한 방법은 그렇게 잘 듣지는 못하는데, the나 and같이 구별성이 없는 정지 단어들의 존재에 대해서도 유사성을 부여하기 때문이고, 구별성이 있는 단어가 여러 번 등장하면 유사성이 과장되기 때문이다.

다행스럽게도 간단한 전처리를 통해 코사인 유사도의 성능을 대폭 끌어올릴 수 있다. 이는 단어 횟수 벡터를 TF-IDF (용어빈도 역문서빈도) 표현의 새 특성 벡터로 치환하는 것이다. 용어 빈도는 단어 등장 수에 로그를 취한 \mathrm{tf}(x_{ij}) = \log (1 + x_{ij})로 정의되고, 한 단어가 한 문서에 여러 번 등장할 때의 부작용을 억제한다. 역문서빈도는 얼마나 많은 문서들이 용어 j를 담고 있는지로 전체 문서를 나눈 값인 \mathrm{ldf}(x_{j}) = \log \frac{N}{1 + \sum_{i=1}^{N} \mathbf{1}_{x_{ij} > 0}}로 정의된다. 이후 용어빈도 역문서빈도는 \mathbf{\phi}(\mathbf{x}_{i}) = [\mathrm{tf}(x_{ij}) \times \mathrm{idf}(j)]_{j=1}^{V}로 정의되고, 이를 코사인 유사도에 적용시켜 \kappa(\mathbf{x}_{i}, \mathbf{x}_{j}) = \frac{\mathbf{\phi}(\mathbf{x}_{i})^{T} \mathbf{\phi}(\mathbf{x}_{j})}{ \lVert \mathbf{\phi}(\mathbf{x}_{i}) \rVert_{2} \lVert \mathbf{\phi}(\mathbf{x}_{j}) \rVert_{2} } 라는 새로운 커널을 얻는다. 이는 좋은 성능을 낸다.

14.2.3. Mercer (positive definite) kernels

어떤 알고리즘은 커널 함수의 그램 행렬 \mathbf{K}_{ij} = \kappa(\mathbf{x}_{i}, \mathbf{x}_{j})이 임의의 입력 데이터셋에 대해 양의 정부호임을 만족할 조건을 요구하는데, 이런 커널을 메르세르 커널(양의 정부호 커널)이라고 한다. 가우시안 커널은 메르세르 커널이면서 코사인 유사도 커널이다.

메르세르 커널의 중요성은 다음의 메르세르 정리에 있다. 그램 행렬이 양의 정부호이면, 고유벡터분해 \mathbf{K} = \mathbf{U}^{T} \mathbf{\Lambda} \mathbf{U}가 있을 때 \mathbf{\phi}(\mathbf{x}_{i}) = \mathbf{\Lambda}^{\frac{1}{2}} \mathbf{U}_{:, i}로 잡으면 k_{ij} = (\mathbf{\Lambda}^{\frac{1}{2}} \mathbf{U}_{:, i})^{T}(\mathbf{\Lambda}^{\frac{1}{2}} \mathbf{U}_{:, j}) = \mathbf{\phi}(\mathbf{x}_{i})^{T}\mathbf{\phi}(\mathbf{x}_{j})가 되므로, 그램 행렬의 요소인 커널 값들은 고유벡터로 정의되는 특성 벡터들의 내적으로 구할 수 있게 된다. 일반적으로, 커널이 메르세르 커널이면 커널의 고유함수에 의존하는 \mathbf{\phi} : \mathcal{X} \to \mathbf{R}^{D}가 존재해서 \kappa(\mathbf{x}, \mathbf{x}^{\prime}) = \mathbf{\phi}(\mathbf{x})^{T}\mathbf{\phi}(\mathbf{x}^{\prime})이 된다.

다항식 커널이나 가우시안 커널은 메르세르 커널이다. 시그모이드 커널 \kappa(\mathbf{x}, \mathbf{x}^{\prime}) = \mathrm{tanh}(\gamma \mathbf{x}^{T} \mathbf{x}^{\prime} + r) 은 메르세르 커널이 아니고 별로 좋은 커널이 아니다. 어떤 커널이 메르세르 커널인지를 보이는 것은 어려우나, 메르세르 커널을 합하면 메르세르 커널이 된다.

14.2.4. Linear kernels

커널로부터의 특성 벡터를 유도하는 것은 메르세르 커널일 때만 가능하고 그 경우에도 어렵다. 하지만 특성 벡터로부터 커널을 유도하는 것은 쉬운데, 그냥 적당한 함수 \mathbf{\phi}에 대해 \kappa(\mathbf{x}, \mathbf{x}^{\prime}) = \mathbf{\phi}(\mathbf{x})^{T}\mathbf{\phi}(\mathbf{x}^{\prime})이 된다. \mathbf{\phi}(\mathbf{x}) = \mathbf{x}이면 이는 선형 커널 \kappa(\mathbf{x}, \mathbf{x}^{\prime}) = \mathbf{x}^{T}\mathbf{x}^{\prime}이 된다. 이는 원본 데이터가 이미 고차원이고 원본 특성이 각각 정보성을 가지는 문서 분류 등에 유용하다. 각각 픽셀이 그다지 많은 정보성을 주지 못하는 이미지 식별 등에는 별로 유용하지 못하다.

14.2.5. Matern kernels

메이턴 커널은 가우시안 과정 회귀에서 자주 쓰이는데 r = \lVert \mathbf{x} - \mathbf{x}^{\prime} \rVert, \nu > 0, l > 0일 때 \kappa(r) = \frac{2^{1 - \nu}}{\Gamma(\nu)}(\frac{\sqrt{2 \nu}r}{l})^{\nu} K_{\nu} (\frac{\sqrt{2 \nu}r}{l})로 정의된다 (K_{\nu}은 수정된 베셀 함수). \nu \to \infty가 되면 이는 제곱오차 커널이 된다. \nu = \frac{1}{2}면 이 커널은 \kappa(r) = e^{-\frac{r}{l}}이 된다. D = 1일 때 이 커널을 써서 가우시안 과정을 정의하여 온스타인-울렌벡 과정을 얻을 수 있다.

14.2.6. String kernels

커널의 강력함은 입력 데이터가 구조화된 오브젝트일 때 나온다. 두 가변 길이 문자열을 문자열 커널로 비교해 보자. 두 문자열의 유사도를 두 문자열이 공통적으로 갖는 부분문자열의 등장 횟수의 곱의 가중치합 \kappa(x, x^{\prime}) = \sum_{s \in \mathcal{A}^{\ast}} w_{s} \phi_{s}(x) \phi_{s}(x^{\prime})으로 정의하면 이는 메르세르 커널이고 접미사 트리를 이용해 O(\lvert x \rvert + \lvert x^{\prime} \rvert) 시간에 계산될 수 있다.

여러 세팅이 있는데 \lvert s \rvert > 1에 대해 w_{s} = 0으로 놓으면 문자 등장수 커널이 된다. s를 공백 문자로 경계삼으면 단어 가방 커널이 된다. 존재하는 대부분의 단어는 문서에 등장하지 않으므로 이 특성 벡터는 대단히 희소한 벡터가 된다. 고정된 길이 k의 문자열만 고려하면 k-스펙트럼 커널이 된다. 문자열 커널을 확장해 트리들을 비교할 수도 있다. 여러 변형이 가능하다.

14.2.7. Pyramid match kernels

컴퓨터 비전에서 이미지의 여러 점들을 통해 특성 벡터를 계산해 단어 가방 표현을 생성하는 일은 흔하다. 이 벡터들은 양자화되어 이산적 심볼을 형성한다. 이렇게 생성된 두 가변 길이 단어 가방을 비교하는 하나의 방법은 피라미드 매치 커널이다. 각 특성 집합은 다중 해상도 히스토그램으로 매핑된 뒤 가중 히스토그램 교집합을 이용해 비교된다. 이 히스토그램법은 가장 미세한 해상도에서 최적의 이분 매칭으로 찾은 유사도에 대한 좋은 근사가 되며, 이미지의 특성에 해당하는 점 수가 일치하지 않을 때 도움이 되고 메르세르 커널이 된다.

14.2.8. Kernels derived from probabilistic generative models

특성 벡터를 추출하는 확률적 생성 모델 p(\mathbf{x} | \mathbf{\theta})를 통해 커널을 어떻게 정의할 수 있을까?

14.2.8.1. Probability product kernels

하나의 접근법은 커널을 다음과 같이 정의하는 것이다: \rho > 0에 대해 \kappa(\mathbf{x}_{i}, \mathbf{x}_{j}) = \int p(\mathbf{x} | \mathbf{x}_{i})^{\rho} p(\mathbf{x} | \mathbf{x}_{j})^{\rho} d \mathbf{x}. 이 때 \hat{\mathbf{\theta}}(\mathbf{x}_{i})는 하나의 데이터 벡터를 이용한 매개변수 추정이라 할 때 p(\mathbf{x} | \mathbf{x}_{i})p(\mathbf{x} | \hat{\mathbf{\theta}}(\mathbf{x}_{i}))로 근사할 수 있다. 이를 확률곱 커널이라 한다.

모델을 하나의 데이터를 이용해 피팅하는 게 이상해 보일지 모르지만 이 모델은 단지 두 오브젝트간의 유사성을 보기 위해 쓰일 뿐이다. 한 데이터로 모델을 \mathbf{x}_{i}로 피팅했는데 \mathbf{x}_{j}와 유사하다는 결과가 나오면 \mathbf{x}_{i}\mathbf{x}_{j}는 충분히 유사하다고 할 수 있다. 위의 확률곱 커널은 은닉 마르코프 모델 같은 생성적 모델의 여러 변형에 대해서도 계산 가능하다. 또한, 이 방법은 문자열 커널과는 달리 실변수 벡터 수열에 대해서도 적용이 가능하다.

14.2.8.2. Fisher kernels

생성적 모델로 커널을 정의하는 더 효과적인 방법은 피셔 커널 \kappa(\mathbf{x}_{i}, \mathbf{x}_{j}) = \mathbf{g}(\mathbf{x}_{i})^{T} \mathbf{F}^{-1} \mathbf{g}(\mathbf{x}_{j})이다. 여기서 점수 벡터 \mathbf{g}(\mathbf{x}) = \nabla_{\mathbf{\theta}} \log p(\mathbf{x} | \mathbf{\theta}) |_{\hat{\mathbf{\theta}}}는 최대가능도추정에서 계산된 로그가능도의 그라디언트이고 피셔 정보 행렬 \mathbf{F} = \nabla \nabla \log p(\mathbf{x} | \mathbf{\theta}) |_{\hat{\mathbf{\theta}}}은 헤시안이다. 이 때 \hat{\mathbf{\theta}}은 모든 데이터에 대해 계산된 값이므로 두 데이터간의 유사도도 모든 데이터의 관점에서 계산되는 것이다. 또한 모델은 한 번만 피팅된다.

피셔 커널을 직관적으로 설명하자면 다음과 같다. \mathbf{g}(\mathbf{x})는 데이터가 최대가능도추정으로부터 가능도를 최대화하는 쪽으로 이동하는 방향으로 볼 수 있는데, 그러면 두 벡터 \mathbf{x}_{i}\mathbf{x}_{j}는 가능도함수의 곡률에 대한 방향그라디언트가 비슷하다면 두 벡터가 비슷하다고 볼 수 있을 것이다.

흥미롭게도, 문자열 커널은 L차 마르코프 연쇄로부터 유도되는 피셔 커널과 같으며, 용어빈도 역문서빈도 벡터의 내적으로 정의되는 커널은 복합 디리클레 다항 모델 기반 텍스트 생성 모델과 대략적으로 같다.

14.3. Using kernels inside GLMs

커널을 이용해 분류와 회귀를 하려면 어떻게 할까?

14.3.1. Kernel machines

커널 기계는 입력 특성 벡터가 \mathbf{\phi}(\mathbf{x}) = [\kappa(\mathbf{x}, \mathbf{\mu}_{1}), \cdots, \kappa(\mathbf{x}, \mathbf{\mu}_{K})]의 형태로 정의되는 일반화된 선형 모델이다. (여기서 \mathbf{\mu}_{i}는 K개의 무게중심) 이 때 \kappa가 방사기저함수 커널이면 이를 방사기저함수 네트워크라 한다. 이 때 위의 입력 특성 벡터는 커널화된 특성 벡터라 한다. 이 때 커널은 메르세르 커널일 필요가 없다.

p(y | \mathbf{x}, \mathbf{\theta}) = \mathrm{Ber}(\mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}))로 정의하면 로지스틱 회귀가 되며, 이는 비선형 결정 경계를 정의하는 간단한 방법이 된다. 배타 논리합(XOR) 함수로부터 오는 함수는 10차 함수를 써도 결정 경계를 잘 정의할 수 없지만 방사기저함수 커널로는 잘 분리할 수 있다.

로지스틱 회귀 XOR 출력에 대한 커널별 분리. 선형 커널, 방사기저함수 커널, 다항식 커널.

p(y | \mathbf{x}, \mathbf{\theta}) = \mathcal{N}(\mathbf{w}^{T} \mathbf{\phi}(\mathbf{x}), \sigma^{2})로 정의하면 선형 회귀가 된다. 이 때 대역폭이 작으면 모델은 굉장히 울퉁불퉁한 함수가 되고 대역폭이 커질수록 직선에 가까워진다.

대역폭에 따른 1D 방사기저함수 피팅.

14.3.2. L1VMs, RVMs, and other sparse vector machines

커널 기계의 메인 이슈는 어떻게 무게중심 \mathbf{\mu}_{k}를 정하는가이다. 입력이 저차원 유클리드 공간이면 데이터가 차지하는 공간을 균등하게 타일링 분할해서 프로토타입을 배치할 수 있으나 고차원으로 가면 차원의 저주 때문에 힘들어진다. 매개변수를 수치해석적 최적화를 하거나 마르코프 연쇄 몬테 카를로 추론을 사용할 수도 있지만 이로 유도되는 목적 함수나 사후분포는 여러 극대값을 갖는다는 문제점이 있다. 또한 이는 커널이 가장 자주 쓰이는 입력이 구조화되어 들어오는 문제로 확장하기 어렵다. 다른 방법은 데이터를 클러스터링한 뒤 클러스터 중심마다 프로토타입을 배정하는 방법이 있으나 밀도가 높은 공간이라고 해서 그 공간에 배정된 프로토타입이 출력을 가장 잘 표현할 수 있다는 보장이 없다는 것이 문제다. 즉, 클러스터링은 비지도학습이기 때문에 예측에 유용하지 않다. 또한, 클러스터 수를 결정해야 한다는 문제도 있다.

더 간단한 방법은 각각의 \mathbf{x}_{i}를 프로토타입으로 만들어 \mathbf{\phi}(\mathbf{x}) = [\kappa(\mathbf{x}, \mathbf{x}_{1}), \cdots, \kappa(\mathbf{x}, \mathbf{x}_{N})]을 커널화된 특성 벡터로 삼는 것이다. 이 때 \mathbf{w}에 대해 희소성을 유도하는 사전분포를 써서 학습 데이터 중 유효한 것들을 효과적으로 골라낼 수 있는데, 이를 희소 벡터 기계라 한다. 가장 자연스러운 선택은 l_{1} 정규화를 사용하는 (이 때는 그룹 라쏘를 사용한다) L1 정규화 벡터 기계 (L1VM)이다. l_{2} 정규화를 사용하면 L2VM이라 한다. 이 경우엔 당연히 희소하지 않다.

자동 연관성 감지 등을 이용해 희소성을 더 늘릴 수 있는데 이를 연관 벡터 기계(RVM)이라 한다. ARD/SBL 알고리즘을 이용해 피팅할 수도 있지만 실용적인 방법은 탐욕적 알고리즘을 쓴다.

또 다른 널리 알려진 접근법은 보조 벡터 기계(SVM)인데, 이는 희소 유도 사전분포를 사용하는 대신 가능도 항을 수정한다. 베이지안적이진 않지만 효과는 비슷하다.

L2VM, L1VM, RVM, SVM을 같은 방사기저함수 커널로 비교해 보면 비슷한 퍼포먼스를 내지만 RVM이 가장 희소하고 그 다음 L1VM, 그 다음 SVM이다. RVM은 가장 빠르고 SVM은 가장 느린데, SVM을 위한 교차검증은 여러 모델을 피팅해야 하지만 RVM을 위한 실측 베이스는 하나의 모델만 피팅하면 되기 때문이다.

여러 방사기저함수 커널을 이용한 비선형 이진 분류. L2VM, L1VM, RVM, SVM.
sinc 함수에 대한 여러 방사기저함수 커널을 이용한 회귀. L2VM, L1VM, RVM, SVM.

14.4. The kernel trick

특성 벡터를 커널에 대해 정의하는 대신, 특성 벡터는 원본의 것을 쓰고 알고리즘에서 특성 벡터의 내적을 호출하는 부분을 내적 대신 커널을 호출하게 바꿀 수 있는데 이걸 커널 트릭이라 한다. 이렇게 하면 많은 알고리즘을 커널화시킬 수 있다. 단 이 때 여기 쓰이는 커널은 메르세르 커널이어야 한다.

14.4.1. Kernelized nearest neighbor classification

1NN 분류기에서 \lVert \mathbf{x}_{i} - \mathbf{x}_{j} \rVert_{2}^{2} = <\mathbf{x}_{i}, \mathbf{x}_{i}> + <\mathbf{x}_{j}, \mathbf{x}_{j}> - 2 <\mathbf{x}_{i}, \mathbf{x}_{j}>이므로 이를 커널화할 수 있다.

14.4.2. Kernelized K-medoids clustering

K-평균 클러스터링은 비유사성을 측정할 때 유클리드 거리를 쓰는데 이것은 구조화된 오브젝트에 대해서는 항상 적절한 척도는 아니다. 이를 커널화하는 방법은 알고리즘을 K-메도이드 알고리즘으로 치환하는 것이다. K-평균 알고리즘에서는 클러스터의 중심점을 클러스터에 할당된 벡터들의 평균으로 잡지만, K-메도이드 알고리즘에서는 클러스터에 할당된 벡터들 중 하나로 잡는다. 따라서 데이터 오브젝트가 아닌 정수 인덱스를 다루게 되며, 가장 가까운 중심점의 클러스터로 할당하는 것은 같지만 중심점을 업데이트할 때에는 클러스터 내 오브젝트 각각에 대해서 클러스터 내 다른 오브젝트와의 거리들을 합한다. 그리고 그 합이 가장 작아지는 오브젝트를 새 중심점으로 선택한다. 즉, m_{k} = \mathrm{argmin}_{i : z_{i} = k} \sum_{j : z_{j} = k} \lVert \mathbf{x}_{i} - \mathbf{x}_{j} \rVert_{2}^{2} 으로 선택하는 것이다. K-평균 알고리즘의 시간복잡도는 O(n_{k} D)이지만, K-메도이드 알고리즘의 시간복잡도는 O(n_{k}^{2})가 된다. 이 알고리즘으로 분류기를 만든 것을 최근접 메도이드 분류라 한다. 이 알고리즘은 거리함수를 커널함수로 바꿈으로써 커널화될 수 있다.

14.4.3. Kernerlized ridge rigression

커널 트릭은 거리 기반 알고리즘이 아닌 능선 회귀같은 매개화된 모델에도 적용할 수 있다.

14.4.3.1. The primal problem

능선 회귀를 리뷰해보자. \mathbf{x}가 특성 벡터이고 \mathbf{X}가 이를 모은 행렬일 때 J(\mathbf{w}) = (\mathbf{y} - \mathbf{X} \mathbf{w})^{T} (\mathbf{y} - \mathbf{X} \mathbf{w}) + \lambda \lVert \mathbf{w} \rVert^{2} 를 최소화하는 것이 목적이다. 최적해는 \mathbf{w} = (\mathbf{X}^{T} \mathbf{X} + \lambda \mathbf{I}_{D} )^{-1} \mathbf{X}^{T} \mathbf{y} = (\sum_{i} \mathbf{x}_{i} \mathbf{x}_{i}^{T} + \lambda \mathbf{I}_{D} )^{-1} \mathbf{X}^{T} \mathbf{y}이 된다.

14.4.3.2. The dual problem

위의 최적해는 아직 내적 형태가 아니므로 커널 트릭을 쓸 수 없다. 위의 표현을 \mathbf{w} = \mathbf{X}^{T} (\mathbf{X} \mathbf{X}^{T} + \lambda \mathbf{I}_{N})^{-1} \mathbf{y}로 치환하면, 이는 계산하는 데 O(N^{3} + N^{2} D) 시간이 걸린다. 이 때 쌍대 변수 \mathbf{\alpha} = (\mathbf{K} + \lambda \mathbf{I}_{N} )^{-1} \mathbf{y}을 정의하면 원시 변수\mathbf{w} = \mathbf{X}^{T} \mathbf{\alpha} = \sum_{i=1}^{N} \alpha_{i} \mathbf{x}_{i}로 쓸 수 있다. 즉, 학습 데이터의 선형 결합이 된다는 것이다. 이를 예측값에 대입하면 \hat{f}(\mathbf{x}) = \mathbf{w}^{T} \mathbf{x} = \sum_{i=1}^{N} \alpha_{i} \mathbf{x}_{i}^{T} \mathbf{x} = \sum_{i=1}^{N} \alpha_{i} \kappa(\mathbf{x}, \mathbf{x}_{i})이 된다.

위의 방법으로 능선 회귀를 커널화시켰다. 이 방법은 로지스틱 회귀 등 다른 여러 방법에도 쓸 수 있다.

14.4.3.3. Computational cost

쌍대 변수 \mathbf{\alpha}를 계산하는 데는 O(N^{3})의 시간이 들고, 원시 변수 \mathbf{w}를 계산하는 데는 O(D^{3})의 시간이 든다. 따라서 커널 방법은 고차원 데이터에 적합하지만, 예측하는 데 걸리는 시간은 쌍대 변수의 경우 O(ND)로, 원시 변수의 O(D)보다 오래 걸린다. \mathbf{\alpha}를 희소하게 만들어서 이 단점을 줄일 수 있다.

14.4.4. Kernel PCA

주성분 분석은 표본공분산 \mathbf{S} = \frac{1}{N} \mathbf{X}^{T} \mathbf{X}을 이용해 저차원 선형 사영을 계산할 수 있는 방법이다. 하지만 그 대신에 내적행렬 \mathbf{X} \mathbf{X}^{T}을 이용해 계산할 수도 있다. 이는 커널 트릭을 이용해 비선형 사영을 계산하는 것인데 이를 커널 주성분 분석이라 한다.

\mathbf{U}를 내적행렬의 고유벡터행렬이라 하면 (\mathbf{X}^{T} \mathbf{X}) (\mathbf{X}^{T} \mathbf{U}) = (\mathbf{X}^{T} \mathbf{U}) \mathbf{\Lambda}이 되는데, 이로부터 \mathbf{S}의 고유벡터는 \mathbf{V} = \mathbf{X}^{T} \mathbf{U}가 됨을 알 수 있다. 이는 정규화되지는 않은 상태인데, \lVert \mathbf{v}_{j} \rVert^{2} = \mathbf{u}_{j}^{T} \mathbf{X} \mathbf{X}^{T} \mathbf{u}_{j} = \lambda_{j} \mathbf{u}_{j}^{T} \mathbf{u}_{j} = \lambda_{j}이기 때문이다. 그러므로 정규화된 고유벡터 행렬은 \mathbf{V}_{\mathrm{pca}} = \mathbf{X}^{T} \mathbf{U} \mathbf{\Lambda}^{-\frac{1}{2}}가 된다. 차원 수가 데이터 수보다 많을 때에는 이 방법은 도움이 된다.

이제 \mathbf{K} = \mathbf{X}\mathbf{X}^{T}를 그램 행렬이라 하자. 메르세르 정리로 유도되는 커널에 대해 \mathbf{\phi}(\mathbf{x}_{i}) = \mathbf{\phi}_{i}로 잡고 \mathbf{\Phi}를 대응하는 설계 행렬, \mathbf{S}_{\mathbf{\phi}} = \frac{1}{N} \sum_{i} \mathbf{\phi}_{i} \mathbf{\phi}_{i}^{T}을 대응하는 공분산 행렬이라 하면 고유벡터는 \mathbf{V}_{\mathrm{kpca}} = \mathbf{\Phi}^{T} \mathbf{U} \mathbf{\Lambda}^{-\frac{1}{2}}이 된다. \mathbf{\phi}는 무한 차원일 수도 있으므로 고유벡터를 직접 계산할 수는 없지만, 테스트 벡터 \mathbf{x}_{\ast}에 대해 \mathbf{k}_{\ast} = [\kappa(\mathbf{x}_{\ast}, \mathbf{x}_{1}), \cdots, \kappa(\mathbf{x}_{\ast}, \mathbf{x}_{N}) ]로 잡을 때 테스트 벡터의 특성 공간에 대한 사영은 \mathbf{\psi}_{\ast}^{T} \mathbf{V}_{\mathrm{kpca}} = \mathbf{\psi}_{\ast}^{T} \mathbf{\Phi}^{T} \mathbf{U} \mathbf{\Lambda}^{-\frac{1}{2}} = \mathbf{k}_{\ast}^{T} \mathbf{\Phi}^{T} \mathbf{U} \mathbf{\Lambda}^{-\frac{1}{2}}로 계산할 수 있게 된다.

위의 문제점은 사영된 데이터의 평균이 0이라고 가정했다는 점이다. 특성 공간에서는 바로 평균을 평행이동할 수는 없다. 그 대신에 \tilde{\mathbf{\phi}}_{i} = \mathbf{\phi}_{i} - \frac{1}{N} \sum_{j} \mathbf{\phi}_{j}로 잡으면 평균이 0이 된다. 이 때 중앙화 행렬 \mathbf{H} = \mathbf{I} - \frac{1}{N} \mathbf{1}_{N} \mathbf{1}_{N}^{T}로 잡으면 그램 행렬은 \tilde{\mathbf{K}} = \mathbf{H} \mathbf{K} \mathbf{H}로 나타내어진다. 이 방법으로 사영된 데이터의 평균을 0으로 맞추는 것이 가능하다.

선형 주성분 분석은 L \leq D 성분까지만 사용할 수 있었지만 커널 주성분 분석은 데이터의 개수만큼 성분을 사용할 수 있다. 단 커널 주성분 분석으로 학습한 특성은 시각화하기엔 좋지 않다는 단점이 있다. 커널 주성분 분석은 확률적 주성분 분석에도 적용 가능하고, 다차원 스케일링(MDS)이라는 기법과 관계가 있다. 이 기법은 사영된 공간상에서의 유클리드 거리가 원본 공간상에서의 불유사도 행렬을 근사하는 저차원 사영을 찾는다.

커널 주성분 분석과 주성분 분석의 비교.

14.5. Support vector machines (SVMs)

앞서 보았던 희소 커널 기계를 유도하는 방법은 커널 기저 함수와 일반화된 선형 모델을 같이 이용하며 l_{1}이나 자동 연관성 감지와 같은 희소성을 유도하는 사전분포를 적용하는 것이다. 다른 방법은 능선 회귀나 로지스틱 회귀처럼 목적 함수에 정규화자를 붙이는 것이다. 능선 회귀의 경우 \hat{\mathbf{w}} = (\mathbf{X}^{T} \mathbf{X} + \lambda \mathbf{I})^{-1} \mathbf{X}^{T} \mathbf{y}의 해를 갖는데, 앞 절에서의 기법을 쓰면 내적 \mathbf{x}^{T} \mathbf{x}^{\prime}로만 이루어진 형태로 고쳐쓸 수 있으며, 이를 커널화할 수 있다. 하지만 이는 희소하진 않다.

하지만, 이차/로그 손실 함수 대신 다른 어떤 손실 함수를 쓰면 해의 희소함을 보장해 예측을 학습 데이터의 일부분 (보조 벡터)에만 의존하게 할 수 있다. 이러한 커널 트릭과 손실 함수 수정의 결합을 보조 벡터 기계(SVM)라 한다. 이는 본래 이진 분류를 위해 만들어졌으나 회귀나 다중 분류에도 쓸 수 있다.

보조 벡터 기계는 확률적 관점에서는 부자연스럽다. 사전분포가 아니라 손실함수에 희소성을 저장하고, 모델의 일부분이 아닌 알고리즘적 과정을 통해 커널을 수정하기 때문이다. 또한, 보조 벡터 기계는 확률적 결과를 내지 않는다. 이는 다종 분류일 때 문제가 된다.

L1VM, RVM같이 보조 벡터 기계 이상으로 잘 동작하는 희소하고, 확률적이고, 다종 커널 기반 분류기도 있다. 하지만 보조 벡터 기계는 아주 유명하고, 출력이 구조화되었을 때 계산적 이점이 있으므로, 알아둬야 할 가치가 있다.

14.5.1. SVMs for regression

커널화된 능선 회귀의 단점은 해 벡터 \mathbf{w}가 모든 학습 데이터에 의존한다는 것이다. 이를 해결하기 위해 다음의 엡실론 무감각 손실 함수 L_{\epsilon}(y, \hat{y}) = \max(0, \lvert y - \hat{y} \rvert - \epsilon)를 도입한다. 이 손실 함수는 입실론-튜브 내의 점은 징벌하지 않는다. 대응되는 손실 함수는 C = \frac{1}{\lambda}, \hat{y}_{i} = f(\mathbf{x}_{i}) =\mathbf{w}^{T} \mathbf{x}_{i} + w_{0}이라 할 때 J = C \sum_{i=1}^{N} L_{\epsilon}(y_{i}, \hat{y}_{i}) + \frac{1}{2} \lVert \mathbf{w} \rVert^{2}이 된다. 이 목적 함수는 비조건적 볼록 함수이지만 미분가능하지 않다. 이를 해결하기 위해 느슨한 변수 \xi_{i}^{+} \geq 0, \xi_{i}^{-} \geq 0y_{i} \leq f(\mathbf{x}_{i}) + \epsilon + \xi_{i}^{+}, y_{i} \geq f(\mathbf{x}_{i}) - \epsilon - \xi_{i}^{-}의 조건을 만족하게 잡으면 J  = C \sum_{i=1}^{N} (\xi_{i}^{+} + \xi_{i}^{-}) + \frac{1}{2} \lVert \mathbf{w} \rVert^{2}로 쓸 수 있다. 이 해는 \alpha_{i} \geq 0에 대해 \hat{\mathbf{w}} =\sum_{i} \alpha_{i} \mathbf{x}_{i}의 꼴이 된다. 또한 \mathbf{\alpha}는 희소한데, 오차가 \epsilon보다 작은 경우 성분은 0이 되기 때문이다. 이 때 \alpha_{i} > 0\mathbf{x}_{i}보조 벡터라 하며 오차가 \epsilon보다 큰 벡터이다.

모델을 학습시키고 난 뒤 이를 대입하면 \hat{y}(\mathbf{x}) = \hat{w}_{0} + \hat{\mathbf{w}}^{T} \mathbf{x} = \hat{w}_{0} + \sum_{i} \alpha_{i} \mathbf{x}_{i}^{T} \mathbf{x}가 된다. 이를 커널화하면 \hat{y}(\mathbf{x}) = \hat{w}_{0} + \sum_{i} \alpha_{i} \kappa(\mathbf{x}_{i}, \mathbf{x})로 만들 수 있다.

14.5.2. SVMs for classification

보조 벡터 기계를 분류에 쓰려면 어떻게 할까?

14.5.2.1. Hinge loss

로지스틱 회귀의 음의 로그가능도 L_{\mathrm{nll}}(y, \eta) = \log (1 + e^{-y \eta})은 0-1 리스크의 볼록 상한이 되는데, 이를 경첩 손실 함수 L_{\mathrm{hinge}}(y, \eta) = \max(0, 1 - y \eta)으로 대체하면 (여기서 \eta = f(\mathbf{x}) 목적 함수는 \min_{\mathbf{w}, w_{0}} [\frac{1}{2} \lVert \mathbf{w} \rVert^{2} + C \sum_{i=1}^{N} \max(1 - y_{i} f(\mathbf{x}_{i}), 0)]가 된다. 이는 미분가능하지 않은데, 아까처럼 느슨 변수 \xi_{i}를 도입하면 \min_{\mathbf{w}, w_{0}, \mathbf{\xi}}[\frac{1}{2} \lVert \mathbf{w} \rVert^{2} + C \sum_{i=1}^{N} \xi_{i}]에 조건 \xi_{i} \geq 0, y_{i}(\mathbf{x}_{i}^{T} \mathbf{w} + w_{0}) \geq 1 - \xi_{i}가 걸린 문제가 된다. 이는 일반적으론 O(N^{3}) 시간이 걸리지만 순차적 최소 최적화(SMO) 알고리즘을 쓰면 O(N^{2}) 시간에 할 수 있다. 그냥 선형 보조 벡터 기계를 O(N) 시간에 학습하기도 한다.

이 경우에도 해는 \hat{\mathbf{w}} = \sum_{i} \alpha_{i} \mathbf{x}_{i}의 꼴이 되고 \alpha_{i} = \lambda_{i} y_{i}이며 희소성을 만족한다. \alpha_{i} > 0\mathbf{x}_{i}는 보조 벡터라 불린다. 이는 잘못 분류되었거나, 마진 내에서 분류된 벡터들이다.

테스트 시점에 예측은 \hat{y}(\mathbf{x}) = \mathrm{sgn}(\hat{w}_{0} + \hat{\mathbf{w}}^{T} \mathbf{x})을 통해 이루어진다. 해를 대입하고 커널 트릭을 쓰면 \hat{y}(\mathbf{x}) = \mathrm{sgn}(\hat{w}_{0} + \sum_{i=1}^{N} \alpha_{i} \kappa(\mathbf{x}_{i}, \mathbf{x}))가 된다. 이는 s < N이 보조 벡터의 수일 때 O(sD) 시간이 걸린다. 보조 벡터의 개수는 해의 희소도에 의존하므로 정규화 계수에 의존한다.

14.5.2.2. The large margin principle

위의 결과를 다른 관점에서 도출해 보자. 우리의 목적은 커널에 의존하면서 특성 공간에 선형인 함수 f(\mathbf{x})를 찾는 것이었다. \mathbf{x}_{\perp}\mathbf{x}의 특성 경계에 대한 정사영, r은 거리, \mathbf{w}는 법선 벡터라 할 때 \mathbf{x} = \mathbf{x}_{\perp} + r \frac{\mathbf{w}}{\lVert \mathbf{w} \rVert}이 된다. 그러므로 f(\mathbf{x}) = \mathbf{w}^{T}\mathbf{x} + w_{0} = (\mathbf{w}^{T} \mathbf{x}_{\perp} + w_{0}) + r \lVert \mathbf{w} \rVert = r \lVert \mathbf{w} \rVert가 된다. 그러므로 r = \frac{f(\mathbf{x})}{\lVert \mathbf{w} \rVert}이다.

데이터가 선형 분리 가능할 때 좋은 분류기는 두 집합과 결정 경계 사이의 거리를 최대로 하는 분류기일 것이다. 즉, 가장 가까운 점과의 수직 거리를 최대로 하는 모델을 구해야 하므로, 목적 함수는 \max_{\mathbf{w}, w_{0}} \min_{i=1}^{N} \frac{y_{i}(\mathbf{w}^{T} \mathbf{x}_{i} + w_{0})}{\lVert \mathbf{w} \rVert}이 된다. 이 때 \mathbf{w}w_{0}은 상수배해도 목적함수는 변하지 않으므로 y_{i}f_{i}가 결정 경계에서 가장 가까운 점에서 1이 되게 잡자. 그러면 목적 함수는 \min_{\mathbf{w}, w_{0}} \frac{1}{2}\lVert \mathbf{w} \rVert^{2}에 조건 y_{i} (\mathbf{w}^{T} \mathbf{x}_{i} + w_{0}) \geq 1이 걸린 문제가 된다. 이 때문에 보조 벡터 기계는 큰 마진 분류기의 일종이 된다.

데이터가 선형 분리가능하지 않을 때에는 모든 i에 대해 y_{i}f_{i} \geq 1이 되게 하는 해가 없다. 따라서 느슨 변수 \xi_{i} \geq 0을 도입해 마진 경계 내에서는 \xi_{i} = 0, 밖에서는 \xi_{i} = \lvert y_{i} - f_{i} \rvert가 되게 한다. 0 < \xi_{i} \leq 1이면 마진 내에서 올바른 쪽의 결정 경계에 있게 되고 \xi_{i} > 1이면 틀린 쪽의 결정 경계에 있게 된다. 이후 조건식 y_{i}f_{i} \geq 0약한 마진 조건 y_{i}f_{i} \geq 1 - \xi_{i}로 바꾼다. 그러면 새 목적 함수는 \min_{\mathbf{w}, w_{0}, \mathbf{\xi}} \frac{1}{2} \lVert \mathbf{w} \rVert^{2} + C \sum_{i=1}^{N} \xi_{i}\xi_{i} \geq 0, y_{i}(\mathbf{x}_{i}^{T} \mathbf{w} + w_{0}) \geq 1 - \xi_{i}의 조건이 걸린 문제가 된다. 이는 앞 절에서 유도한 결과와 같다. \xi_{i} > 1인 경우 점 i가 잘못 분류되었다는 뜻이므로, \sum_{i} \xi_{i}를 잘못 분류된 표본수의 상한으로 잡을 수 있다.

C는 정규화 매개변수로서 학습 데이터에서 허용할 수 있는 오차의 수를 조절한다. 보통은 학습 시점의 오분류율을 조절하는 적당한 변수 0 < \nu \leq 1에 대해 C = \frac{1}{\nu N}로 잡는데, 이를 \nu보조 벡터 기계 분류기라 한다. \nu는 교차검증으로 잡는다.

14.5.2.3. Probabilistic output

보조 벡터 기계는 \hat{y}(\mathbf{x}) = \mathrm{sgn}(f(\mathbf{x}))의 부호 라벨링을 수행하지만, 예측에 대한 신뢰도를 측정하고 싶을 수 있다. 휴리스틱한 접근법 하나는 f(\mathbf{x})를 로그 확률비 \log \frac{p(y=1 | \mathbf{x})}{p(y=0 | \mathbf{x})}로 나타낸 뒤 보조 벡터 기계의 출력을 p(y=1 | \mathbf{x}, \mathbf{\theta}) = \rho (af(\mathbf{x}) + b)를 사용해 확률적 값으로 바꾸는 것이다. 이 때 a, b는 별도의 검증 집합에서 최대가능도추정된 값이다. (학습 집합에서 추정을 하면 과적합의 위험이 있기 때문이다).

하지만, 이로 얻은 확률적 값은 정밀한 값은 아닌데, 보조 벡터 기계를 학습하는 과정 중 f(\mathbf{x})를 로그 확률비로 나타내는 것을 정당화시켜주는 부분은 없기 때문이다. 연관성 벡터 기계에서의 확률적 출력값은 로그 확률의 참값에 대한 좋은 근사가 되지만, 보조 벡터 기계에서는 아니다.

14.5.2.4. SVMs for multi-class classification

보조 벡터 기계를 다종 분류로 확장하는 것은 쉽지 않다. 출력이 정밀하게 계산되어 나온 값이 아니므로 서로 비교하기 쉽지 않기 떄문이다.

직관적인 방법은 하나 대 나머지 (하나 대 모두) 접근법을 쓰는 것이다. 이 경우엔 C개의 이진 분류기를 학습하게 된다. 그러나 이는 라벨을 결정하기 힘든 영역을 만드는 문제가 있다.

다른 방법은 \hat{y}(\mathbf{x}) = \mathrm{argmax}_{c} f_{c}(\mathbf{x})을 선택하는 것인데, 서로 다른 f_{c} 함수끼리 비교 가능한 크기를 가진다는 보장이 없으므로 잘 듣지 않는다. 또한 클래스 불균형 문제도 있다. 이에 대처하려면 C개의 분류기를 전부 동시에 학습시키면 되지만 시간복잡도가 O(CN^{2})에서 O(C^{2}N^{2})로 늘어난다는 단점이 있다.

또 다른 방법은 하나 대 하나 (모든 쌍) 방법을 써서 C(C-1)/2개의 분류기 f_{c, c'}로 모든 쌍을 분류하는 것이다. 하지만 이것도 여전히 모호한 영역의 문제가 있으며, 학습에는 O(C^{2}N^{2}) 시간이 들고 테스트는 표본당 O(C^{2} N_{\mathrm{sv}}) 시간이 든다 (N_{\mathrm{sv}}는 보조 벡터 수).

이 모든 문제의 근본 원인은 보조 벡터 기계가 확률을 통해 불확실성을 모델링하지 않기 때문에 출력 점수가 클래스들끼리 비교 가능한 값이 아니게 된다는 점에 있다. 대안은 확률적 다종 분류기를 커널화하는 RVM이나 L1VM 등의 방법을 쓰는 것이다.

14.5.3. Choosing C

보조 벡터 기계는 회귀에 쓸 때나 분류에 쓸 때나 커널 함수와 정규화 변수 C를 필요로 한다. 보통은 교차검증으로 선택되지만, C는 커널 매개변수에 강하게 영향받는다는 것을 알아야 할 필요가 있다. 그러므로 교차검증은 C, \gamma의 쌍에 대해 수행해야 하며, 데이터를 먼저 표준화하는 것도 중요하다.

효과적으로 C를 선택하기 위해서는 LARS에서 했던 것처럼 정규화 경로 기법을 쓸 수도 있다. 기본적 방법은, 일단 큰 \lambda 값에서 시작해 \frac{1}{\lVert \mathbf{w}(\lambda)\rVert}을 넓게 잡은 뒤, 조금씩 줄여나가면서 특정 점들을 마진 밖으로 이동시켜 보조 벡터로 만드는 것이다. \lambda가 최대값일 때에는 함수가 완전히 매끈해져서 보조 벡터가 남아있지 않게 될 것이다.

SVM에서의 C와 γ값 선택.

14.5.4. Summary of key points

요약하자면, 보조 벡터 기계 분류기는 3개의 핵심 부분으로 이루어져 있다. 커널 트릭, 희소성, 큰 마진 원리. 커널 트릭은 과소적합을 막기 위해, 즉 특성 벡터가 충분히 특성을 담고 있어 데이터를 선형 분류할 수 있게 하기 위해 필요하다. 원본 특성이 고차원이라면 선형 커널을 써도 상관없다. 희소성과 큰 마진 원리는 과적합을 막기 위해, 즉 모든 기저 함수를 쓰지 않기 위해 필요하다. 경첩 손실 함수로 이를 구현할 수 있지만 l_{1} 또는 부스팅과 같은 다른 방법들도 있다.

14.5.5. A probabilistic interpretation of SVMs

보조 벡터 기계를 직접 확률적 모델로 나타낼 수는 없을까? 그러기 위해서는 C \max(1 - yf(\mathbf{x}), 0) = Cg(m)을 음의 로그가능도로 나타낼 수 있어야 한다. 이렇게 되면 p(y=1 | f) = e^{-C g(f)}, p(y=-1 | f) = e^{-C g(-f)}가 되는데, 둘을 합한 값이 항상 상수여야 한다는 조건을 만족시키지 못하므로 약간의 변형이 필요하다.

확률을 합해서 1이 되어야 한다는 조건을 완화시켜서 유사가능도를 쓰면, e^{-2 \max(0, 1 - y_{i}\mathbf{x}_{i}^{T} \mathbf{w})} = \int_{0}^{\infty} \frac{1}{\sqrt{2 \pi \lambda_{i}}} e^{-\frac{1}{2} \frac{(1 + \lambda_{i} - y_{i} \mathbf{x}_{i}^{T} \mathbf{w})^{2}}{\lambda_{i}}} d \lambda_{i} 로 나타낼 수 있다. 그러므로 음의 경첩 손실 함수의 지수승은 가우시안 비례 혼합으로 나타낼 수 있는 것이다. 이는 보조 벡터 기계를 기대값 최대화 또는 깁스 샘플링으로 피팅할 수 있게 한다. 또한 \mathbf{w}의 사전분포의 초매개변수를 베이지안식으로 세팅하는 가능성을 열어주기도 한다.

14.6. Comparison of discriminative kernel methods

커널 기반 여러 가지 방법을 비교해 보자.

  • \mathbf{w}의 최적화: 목적 함수 J(\mathbf{w}) = -\log p(\mathcal{D} | \mathbf{w}) - \log p(\mathbf{w})가 볼록인가 아닌가? L2VM, L1VM, SVM은 목적 함수가 볼록이다. RVM은 볼록이 아니다. GP는 매개변수 추정을 하지 않는 베이지안 방법이다.
  • 커널의 최적화: 커널 매개변수를 어떻게 최적화하는가? L2VM, RVM, GP와 같은 가우시안 사전분포를 쓰는 방법은 그라디언트 기반 방법으로 주변가능도를 최적화할 수 있다. L1VM이나 SVM은 교차검증을 사용해야 해서 더 느리다.
  • 희소성: RVM과 SVM은 희소 커널 기법이기 때문에 학습 데이터의 일부만 쓴다. GP와 L2VM은 희소하지 않으므로 학습 데이터를 전부 쓴다. 희소성이 갖는 이점은 테스트 시점에서의 예측이 빠르다는 것이다. 또한 가끔 더 나은 정확도를 보이기도 한다.
  • 확률적: SVM을 제외한 모든 방법은 p(y | \mathbf{x}) 형태의 확률적 출력을 낸다. SVM은 확률로 변환될 수 있는 신뢰도값을 내긴 하지만 이렇게 변환해서 얻은 확률은 상호간에 잘 비교되지 않는다.
  • 다중 클래스: SVM을 제외한 모든 방법은 베르누이 대신 다항 베르누이 출력을 써서 다중 클래스 세팅으로 잘 확장할 수 있다. SVM도 확장이 가능하긴 하지만 여러 어려움이 있다.
  • 메르세르 커널: SVM과 GP는 커널이 양의 정부호일 것을 요구한다. 다른 방법은 그렇지 않다.

그래서 어떤 방법이 가장 잘 동작하는가? 커널이 같고 정규화 상수가 똑같이 잘 선택된 경우 성능은 비슷하다. 학습 시간은 얼마나 걸리는가? GP와 L2VM이 일반적으로 O(N^{3}) 시간으로 가장 느리다 (희소성을 쓰지 않기 때문이다). SVM도 O(N^{3}) 시간으로 느리지만 선형 커널을 쓰면 O(N)에 가능하다. 하지만 SVM은 교차검증을 쓰기 때문에 RVM보다 느리다. L1VM은 RVM보다 빠른데 RVM은 이론상으로 l_{1} 최적화를 여러 번 하기 때문이다. 하지만 실제로는 RVM을 학습할 때 탐욕적 방법을 쓰므로 l_{1} 최적화보다 빠르다.

결론짓자면, 속도가 중요하면 RVM을 쓰고, 상호간에 잘 비교되는 확률적 출력이 필요하다면 GP를 쓰라. SVM은 출력이 구조화되었을 경우에만 쓰라. 이 경우엔 가능도 기반 방법들이 느리기 때문이다.

14.7. Kernels for building generative models

커널들 중에서는 비 매개변수적 밀도 추정에 쓸 수 있는 매끄러운 커널들이 존재한다. 이는 비지도 밀도 추정 p(\mathbf{x})에 쓰일 수 있고, p(y, \mathbf{x})에 쓰여서 분류와 회귀를 위한 생성적 모델을 만들 수도 있다.

14.7.1. Smoothing kernels

매끄러운 커널은 다음 성질을 만족시키는 1변수 커널이다.

\int \kappa(x) dx = 1, \int x \kappa(x) dx = 0, \int x^{2} \kappa(x) dx > 0.

간단한 예는 가우시안 커널 \kappa(x) = \frac{1}{(2 \pi)^{\frac{1}{2}}} e^{-\frac{x^{2}}{2}}이다. 이 때 커널의 두께를 대역폭 매개변수 h로 다음과 같이 조정할 수 있다: \kappa_{h}(x) = \frac{1}{h} \kappa(\frac{x}{h}). 방사기저함수 커널을 이용해 이를 일반화하면 \kappa_{h}(\mathbf{x}) = \kappa_{h}(\lVert \mathbf{x} \rVert)로 잡을 수 있다. 가우시안 커널의 경우엔 \kappa_{h}(\mathbf{x}) = \frac{1}{h^{D} (2 \pi)^{\frac{D}{2}}} \prod_{j=1}^{D} e^{-\frac{x_{j}^{2}}{2h^{2}}}이 된다.

가우시안 커널은 지지집합이 무한대라는 특징이 있다. 컴팩트한 지지집합을 갖는 대안적 커널로는 에파네크니코프 커널 \kappa(x) = \frac{3}{4} (1-x^{2}) \mathbf{1}_{\lvert x \rvert \leq 1}이 있다. 이는 지지집합의 경계에서 미분가능하지 않다는 단점이 있는데, 이에 대한 대안으로 3중 큐브 커널 \kappa(x) = \frac{70}{81} (1 - \lvert x \rvert)^{3} \mathbf{1}_{\lvert x \rvert \leq 1}이 있다. 다른 간단한 예는 박스카 커널 \kappa(x) = \mathbf{1}_{\lvert x \rvert \leq 1}로, 그냥 균등 분포이다.

여러 다듬질 커널.

14.7.2. Kernel density estimation (KDE)

가우시안 혼합 모델은 매개변수 밀도함수에 대한 추정자이지만, 클러스터 수 K와 클러스터 위치 \mathbf{\mu}_{k}를 특정해 줘야 한다는 문제가 있다. 하나의 방법은 클러스터 중심을 데이터 \mathbf{\mu}_{i} = \mathbf{x}_{i}로 잡는 것이다. 이 경우엔 모델은 p(\mathbf{x} | \mathcal{D}) = \frac{1}{N} \sum_{i=1}^{N} \mathcal{N}(\mathbf{x} | \mathbf{x}_{i}, \sigma^{2} \mathbf{I})이 된다. 이는 \hat{p}(\mathbf{x}) = \frac{1}{N} \sum_{i=1}^{N} \kappa_{h} (\mathbf{x} - \mathbf{x}_{i})을 이용해 일반화할 수 있는데, 이를 파르젠 창문 밀도 추정자 또는 커널 밀도 추정자(KDE) 로 간단한 비매개변수 밀도 모델이 된다. 비매개변수 모델이 매개변수 모델에 비해 갖는 이점은 모델을 피팅할 필요가 없고 클러스터 수 K를 정해야 할 필요가 없다는 것이다. (대역폭에 대해서는 교차검증으로 튜닝해야 한다) 단점은 메모리를 많이 차지하고 구하는 데 시간이 오래 걸린다는 것이고, 클러스터링에는 쓸모가 없다는 것이다.

가우시안 커널과 균등 커널을 이용한 파르젠 창문 밀도 추정.

박스카 커널로 커널 밀도 추정을 하는 것은 히스토그램 추정과 같다. 이외에는 가우시안 커널로 추정을 할 수도 있다. 대역폭 h를 고르는 방법은 보통 빈도주의 리스크의 추정값을 최소화시키는 쪽으로 고른다. 베이지안적인 방법으로는 디리클레 과정 혼합 모델을 쓸 수 있다. 디리클레 과정 혼합 모델은 커널 밀도 추정보다 효율적이기도 한데, 데이터를 전부 저장할 필요가 없기 때문이다. 가우시안 과정 모델에서 커널 매개변수를 추정할 때 실측 베이스법을 쓸 수도 있다.

14.7.3. From KDE to KNN

커널 밀도 추정법을 이용해 생성적 분류기의 클래스 조건부 밀도함수를 정의할 수 있다. 이는 최근접 이웃 분류기를 유도하는 또 다른 방법으로도 쓸 수 있다. 박스카 커널을 쓰고, 대역폭을 고정하고 데이터 하나를 중심으로 한 초입방체 내에 얼마나 많은 데이터가 들어오는지를 세는 것이다. 아니면 대역폭을 고정하지 않은 채 각각의 데이터 중심 초입방체의 부피를 다르게 할 수도 있다. 이렇게 할 경우 \mathbf{x} 근처의 부피는 K개의 데이터를 포함할 때까지 확장된다. 이렇게 잡은 부피를 V(\mathbf{x})라 하고 이에 속한 K개의 데이터 중 클래스 c에 속하는 데이터 수를 N_{c}(\mathbf{x})라 하면 클래스 조건밀도는 p(\mathbf{x} | y = c, \mathcal{D}) = \frac{N_{c}(\mathbf{x})}{N_{c}V(\mathbf{x})}로 추정될 수 있다. (N_{c}는 클래스 c에 속하는 전체 데이터 수) 클래스 사전분포는 p(y = c | \mathcal{D}) = \frac{N_{c}}{N}로 추정된다. 따라서 클래스 사후분포는 p(y = c | \mathbf{x}, \mathcal{D}) = \frac{N_{c}(\mathbf{x})}{\sum_{c'}N_{c'}(\mathbf{x})} = \frac{N_{c}(\mathbf{x})}{K}로 추정된다. 이로써 최근접 근방 분류기를 유도하는 또 다른 방법이 있음을 보았다.

14.7.4. Kernel regression

커널 밀도 추정은 비지도학습이 아닌 회귀에도 쓸 수 있다. 이 때 목적은 조건부 기대값 f(\mathbf{x}) = \mathbb{E}[y | \mathbf{x}] = \int y p(y | \mathbf{x}) dy = \frac{\int y p(\mathbf{x}, y) dy}{\int p(\mathbf{x}, y) dy}을 계산하는 것이 되는데, 커널 밀도 추정으로 결합밀도함수 p(\mathbf{x}, y) \simeq \frac{1}{N} \sum_{i=1}^{N} \kappa_{h} (\mathbf{x} - \mathbf{x}_{i}) \kappa_{h}(y - y_{i})로 근사할 수 있다. 따라서 f(\mathbf{x}) = \frac{\frac{1}{N} \sum_{i=1}^{N} \kappa_{h}(\mathbf{x}-\mathbf{x}_{i}) \int y \kappa_{h} (y - y_{i}) dy}{\frac{1}{N} \sum_{i=1}^{N} \kappa_{h}(\mathbf{x}-\mathbf{x}_{i}) \int \kappa_{h} (y - y_{i}) dy} = \frac{\sum_{i=1}^{N} \kappa_{h}(\mathbf{x}-\mathbf{x}_{i}) y_{i}}{\sum_{i=1}^{N} \kappa_{h}(\mathbf{x}-\mathbf{x}_{i})}가 된다. w_{i}(\mathbf{x}) = \frac{\kappa_{h}(\mathbf{x} - \mathbf{x}_{i})}{\sum_{j=1}^{N}\kappa_{h}(\mathbf{x} - \mathbf{x}_{j})}이라 하면 f(\mathbf{x}) = \sum_{i=1}^{N} w_{i}(\mathbf{x}) y_{i}가 됨을 알 수 있다. 그러므로 이 예측값은 학습 데이터에서의 출력값의 가중치합이다. 이 때 가중치들은 \mathbf{x}가 저장된 데이터 값들과 얼마나 유사한지에 의존한다. 이를 커널 회귀, 커널 다듬질, 나다라야-왓슨 모델이라고 부른다. 이 방법은 자유 매개변수가 대역폭 h밖에 없음을 눈여겨 보라. 밀도의 참값이 가우시안이고 가우시안 커널을 쓸 경우 최적의 대역폭값은 h = (\frac{4}{3N})^{\frac{1}{5}} \hat{\sigma}이 된다.

가우시안 커널 회귀의 예.

표준편차에 대한 강건한 근사를 할 수도 있는데, 평균 절대 편차 \mathrm{MAD} = \mathrm{median}(\lvert \mathbf{x} - \mathrm{median}(\mathbf{x})\rvert)를 잡은 뒤 \hat{\sigma} = 1.4826 \mathrm{MAD}을 쓰면 된다. 이 휴리스틱은 잘 동작하지만, 불확실한 가정 (실제 밀도를 가우시안으로 가정한다든지)에 의존하고, 매개변수 하나를 튜닝하는 데에밖에 쓸 수 없다. 뒤에서 다룰 실측 베이스법을 쓰면 여러 매개변수를 튜닝할 수도 있고, 조금 더 투명한 가정에 근거할 수도 있다.

14.7.5. Locally weighted regression

\kappa_{h} (\mathbf{x} - \mathbf{x}_{i}) = \kappa(\mathbf{x}, \mathbf{x}_{i})로 정의하면, 커널 회귀에 의해 이루어진 예측을 \hat{f}(\mathbf{x}_{\ast}) = \sum_{i=1}^{N} y_{i} \frac{\kappa(\mathbf{x}_{\ast}, \mathbf{x}_{i})}{\sum_{j=1}^{N} \kappa(\mathbf{x}_{\ast}, \mathbf{x}_{j})}로 다시 쓸 수 있다. 이 때 커널은 매끄러운 커널일 필요가 없음에 주의하라. 표준화 계수가 필요없는 경우에는 \hat{f}(\mathbf{x}_{\ast}) = \sum_{i=1}^{N} y_{i} \kappa(\mathbf{x}_{\ast}, \mathbf{x}_{i}) 로 쓸 수도 있다. 이 모델은 상수 함수를 국소적으로 피팅하는 것이다. 이를 확장해서 \min_{\mathbf{\beta}(\mathbf{x}_{\ast})} \sum_{i=1}^{N} \kappa(\mathbf{x}_{\ast}, \mathbf{x}_{i}) [y_{i} - \mathbf{\beta}(\mathbf{x}_{\ast})^{T} \mathbf{\phi}(\mathbf{x}_{i})]^{2}을 풀어서 \mathbf{x}_{\ast} 각각에서 선형 회귀를 피팅할 수도 있는데, (여기서 \mathbf{\phi}(\mathbf{x}) = [1, \mathbf{x}]) 이를 국소적 가중 회귀라 한다. 이 방법의 예로는 국소적 가중 산포도 다듬질(LOESS/LOWESS)이 있다.

각각의 테스트 케이스의 매개변수는 \mathbf{\beta}(\mathbf{x}_{\ast}) = (\mathbf{\Phi}^{T} \mathbf{D}(\mathbf{x}_{\ast}) \mathbf{\Phi})^{-1} \mathbf{\Phi}^{T} \mathbf{D}(\mathbf{x}_{\ast})\mathbf{y}로 구해진다. (\mathbf{\Phi}는 설계 행렬, \mathbf{D} = \mathrm{diag}(\kappa(\mathbf{x}_{\ast}, \mathbf{x}_{i}))). 대응되는 예측값은 \hat{f}(\mathbf{x}_{\ast}) = \mathbf{\phi}(\mathbf{x}_{\ast})^{T} \mathbf{\beta}(\mathbf{x}_{\ast}) = \sum_{i=1}^{N} w_{i}(\mathbf{x}_{\ast})y_{i}인데, 가중치항은 국소적 다듬질 커널과 선형 회귀를 혼합하는 역할을 하며, 등가 커널이라 불린다.

요점 정리

  • 커널 함수 : 오브젝트간의 유사성을 측정하는 함수로서, 오브젝트를 고정 길이 벡터로 나타낼 수 없을 때 커널에만 의존하는 알고리즘을 활용하기 위해 씀.
  • 커널 함수는 대칭적이고 비음성인 함수로 여러 종류가 있음.
  • 일반화된 선형 모델의 입력을 커널로 전처리해서 입력과 회귀에 쓸 수 있음.
  • 커널 트릭 : 입력을 커널로 전처리하는 대신, 알고리즘에서 입력의 내적을 받는 부분을 커널로 대체해서 본래 입력을 활용하는 기법.
  • 보조 벡터 기계 : 커널 트릭과 손실 함수 수정법을 결합해 학습 데이터 중 일부만 보조 벡터로 활용해서 마진을 최대화해 데이터를 분류하는 기법. 보통 이진 분류에 쓰이나, 출력이 확률적이지 못하다는 단점이 있음.
  • 구별적 커널법의 비교 : 속도가 중요하면 RVM, 잘 비교되는 확률적 출력이 필요하면 GP, 출력이 구조적인 경우 SVM.
  • 생성적 모델에 커널법을 쓰는 경우 : 다듬질 커널, 커널 밀도 추정, 커널 회귀 등의 용례가 있음.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중