7장 - 커널

7장. 커널

서포트 벡터 머신은 가장 턴키(turnkey)한 알고리즘 중 하나다. 분류 문제가 있으면 그냥 실행하면 된다. 대체로 잘 작동한다.

7.1 최적 마진 분류기 복습

6장에서 도출한 최적 마진 분류기를 간략히 되짚어 보자. 데이터셋이 양성과 음성 예제로 나뉘어 있을 때, 기하 마진이 가장 큰 결정 경계를 찾는 것이 목표였다.

기하 마진과 최적화 문제

분류기의 출력은 다음과 같다.

\[g(w^T x + b)\]

훈련 예제 \((x^{(i)}, y^{(i)})\)에서 결정 경계까지의 기하 마진은 다음 공식으로 계산된다.

\[\gamma^{(i)} = y^{(i)} \left( \frac{w^T x^{(i)} + b}{\|w\|} \right)\]

전체 데이터셋의 기하 마진 \(\gamma\)는 모든 훈련 예제 중 최솟값이다.

\[\gamma = \min_{i=1,\ldots,m} \gamma^{(i)}\]

최적 마진 분류기는 이 최악의 기하 마진을 최대화하는 매개변수 \(w\)와 \(b\)를 찾는다.

최적화 문제의 정식화

이를 최적화 문제로 표현하면 다음과 같다.

\[\max_{\gamma, w, b} \gamma \quad \text{s.t.} \quad y^{(i)} \left( \frac{w^T x^{(i)} + b}{\|w\|} \right) \geq \gamma, \quad i = 1, \ldots, m\]

이 문제에서 최적화할 매개변수는 \(\gamma\), \(w\), \(b\)다. 제약 조건은 모든 훈련 예제의 기하 마진이 \(\gamma\) 이상이어야 한다는 것이다. \(\gamma\)를 최대화하면, 결국 최악의 기하 마진을 최대화하게 된다.

구체적인 예를 들어 보자. 세 훈련 예제의 기하 마진이 각각 17, 2, 5라고 하자. 그러면 전체 기하 마진은 최솟값인 2다. 제약 조건 \(\gamma^{(i)} \geq \gamma\)가 모든 \(i\)에 대해 성립해야 하므로, \(\gamma\)를 끌어올리는 유일한 방법은 모든 \(\gamma^{(i)}\)가 그보다 크게 만드는 것이다. 따라서 \(\gamma\)를 최대화하면 최악의 기하 마진이 최대화된다.

함수 마진의 스케일링 자유도

핵심적인 관찰은 함수 마진 \(y^{(i)}(w^T x^{(i)} + b)\)의 분자 부분이 스케일링에 자유롭다는 것이다. 분류기가 \(w^T x + b\)일 때, \(w\)와 \(b\)를 임의의 상수로 곱해도 결정 경계는 변하지 않는다.

예를 들어 \(w = [2, 1]\)이고 \(b = -2\)이면, \(w^T x + b = 0\)이 결정 경계를 정의한다. 이 매개변수에 10을 곱하면 \(w = [20, 10]\), \(b = -20\)이 되지만, 같은 직선을 정의한다.

이 자유도를 활용하여 \(\|w\| = \frac{1}{\gamma}\)로 스케일링하면, 최적화 문제는 다음과 같이 단순화된다.

\[\min_{w, b} \frac{1}{2} \|w\|^2 \quad \text{s.t.} \quad y^{(i)}(w^T x^{(i)} + b) \geq 1, \quad i = 1, \ldots, m\]

\(\frac{1}{\gamma}\)를 최소화하는 것은 \(\gamma\)를 최대화하는 것과 같고, \(\frac{1}{\|w\|}\)를 최대화하는 것은 \(\|w\|\)를 최소화하는 것과 같다. 제곱과 \(\frac{1}{2}\)은 미분 계산을 깔끔하게 만들기 위한 관례다.

7.2 표현자 정리와 \(w\)의 표현

지금까지는 특성 \(x^{(i)}\)가 합리적인 차원(예: \(\mathbb{R}^2\), \(\mathbb{R}^{100}\))이라고 가정하고 알고리즘을 유도했다. 그러나 이제부터는 특성이 10만 차원, 100조 차원, 심지어 무한 차원인 경우를 다룬다.

이를 위해 핵심적인 가정을 도입한다. 매개변수 \(w\)는 훈련 예제의 선형 결합으로 표현할 수 있다.

\[w = \sum_{i=1}^{m} \alpha_i y^{(i)} x^{(i)}\]

여기서 \(y^{(i)}\)는 항상 \(\pm 1\)이므로, 이는 본질적으로 \(w\)가 훈련 예제들의 선형 결합이라는 의미다.

표현자 정리

이것이 단순한 가정이 아니라 정리라는 점이 중요하다. 표현자 정리(representer theorem)는 최적의 \(w\)가 반드시 이 형태를 취한다는 것을 증명한다. 엄밀한 증명은 원시-쌍대 최적화(primal-dual optimization) 이론을 사용하며 상당히 복잡하지만, 왜 이것이 합리적인지 직관적으로 이해할 수 있다.

직관 1: 경사 하강법에 의한 귀납 증명

로지스틱 회귀에 확률적 경사 하강법을 적용하는 경우를 생각해 보자. 매개변수 \(\theta\)를 0으로 초기화한 후, 각 반복에서 다음과 같이 업데이트한다.

\[\theta := \theta - \alpha \cdot (\ldots) \cdot x^{(i)}\]

매 반복마다 어떤 훈련 예제 \(x^{(i)}\)의 상수배를 더하거나 빼는 것이다. \(\theta\)가 0에서 시작하므로, 수학적 귀납법에 의해 경사 하강법을 아무리 많이 반복하더라도 \(\theta\)는 항상 훈련 예제들의 선형 결합으로 남는다. 배치 경사 하강법에서도 마찬가지다. 서포트 벡터 머신의 경사 하강법에서도 동일한 귀납 논증이 성립한다.

직관 2: 기하학적 관점

벡터 \(w\)는 항상 결정 경계에 직교한다. 결정 경계는 데이터를 양성과 음성으로 나누는 초평면이다.

만약 원래 특성이 3차원(\(x_1, x_2, x_3\))이지만 모든 훈련 예제에서 \(x_3 = 0\)이라면, 결정 경계는 \(x_1\)-\(x_2\) 평면 안에 놓이게 되고, 그에 직교하는 \(w\) 역시 \(w_3 = 0\)이어야 한다. 이는 \(w\)가 훈련 예제들의 생성 공간(span) 안에 있어야 한다는 것과 같은 말이다.

7.3 내적으로 표현한 최적화 문제

\(w\)를 위의 형태로 대입하면 최적화 문제가 어떻게 변하는지 살펴보자.

목적 함수

\[\|w\|^2 = w^T w = \left( \sum_i \alpha_i y^{(i)} x^{(i)} \right)^T \left( \sum_j \alpha_j y^{(j)} x^{(j)} \right) = \sum_i \sum_j \alpha_i \alpha_j y^{(i)} y^{(j)} \langle x^{(i)}, x^{(j)} \rangle\]

여기서 \(\langle x, z \rangle = x^T z\)는 두 벡터의 내적을 나타내는 표기다.

제약 조건

\[y^{(i)} (w^T x^{(i)} + b) = y^{(i)} \left( \sum_j \alpha_j y^{(j)} \langle x^{(j)}, x^{(i)} \rangle + b \right) \geq 1\]

핵심 관찰

목적 함수와 제약 조건 모두에서 특성 벡터는 내적 \(\langle x^{(i)}, x^{(j)} \rangle\)의 형태로만 등장한다. 이 관찰이 커널을 가능하게 하는 수학적 열쇠다.

쌍대 최적화 문제

볼록 최적화 이론을 적용하면, 위의 최적화 문제는 다음과 같은 쌍대 형태(dual form)로 더욱 단순화된다.

\[\max_\alpha \sum_{i=1}^{m} \alpha_i - \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j y^{(i)} y^{(j)} \langle x^{(i)}, x^{(j)} \rangle\]

\[\text{s.t.} \quad \alpha_i \geq 0, \quad \sum_{i=1}^{m} \alpha_i y^{(i)} = 0\]

이 과정에서 \(b\)가 소거되며, 최적화 변수는 \(\alpha_i\)뿐이다. 유도 과정은 원시-쌍대 최적화를 사용하며, 자세한 내용은 강의 노트에 기술되어 있다.

예측

\(\alpha_i\)를 구한 뒤 새로운 테스트 예제 \(x\)에 대한 예측은 다음과 같다.

\[h_{w,b}(x) = g\left( \sum_{i=1}^{m} \alpha_i y^{(i)} \langle x^{(i)}, x \rangle + b \right)\]

훈련과 예측 모두 특성 벡터가 내적의 형태로만 사용된다는 점이 핵심이다.

7.4 커널 트릭

이제 커널 트릭의 전체적인 레시피를 정리한다.

단계 1: 알고리즘을 내적으로 표현

학습 알고리즘 전체를 \(\langle x^{(i)}, x^{(j)} \rangle\) 형태의 내적으로 표현한다. 앞 절에서 최적 마진 분류기가 이미 이 형태로 변환되었음을 확인했다.

단계 2: 고차원 특성 매핑 정의

원래 입력 특성 \(x\)에서 고차원 특성 \(\phi(x)\)로의 매핑을 정의한다.

예를 들어, 주택 면적 하나(\(x\))를 입력으로 사용한다면 다음과 같은 고차원 매핑을 정의할 수 있다.

\[\phi(x) = \begin{bmatrix} x \\ x^2 \\ x^3 \\ x^4 \\ \vdots \end{bmatrix}\]

또는 두 개의 특성 \(x_1, x_2\)(면적과 침실 수)가 있다면 다음과 같이 매핑할 수 있다.

\[\phi(x) = \begin{bmatrix} x_1 \\ x_2 \\ x_1 x_2 \\ x_1^2 x_2 \\ x_1 x_2^2 \\ \vdots \end{bmatrix}\]

원래 입력이 1차원이나 2차원이더라도, \(\phi(x)\)는 10만 차원이나 무한 차원이 될 수 있다.

단계 3: 커널 함수 정의

다음을 효율적으로 계산하는 커널 함수를 찾는다.

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

핵심은 \(\phi(x)\)와 \(\phi(z)\)를 명시적으로 계산하지 않고도 이 내적을 효율적으로 구할 수 있는 경우가 있다는 것이다.

단계 4: 알고리즘에서 내적을 커널 함수로 대체

알고리즘의 모든 \(\langle x, z \rangle\)를 \(K(x, z)\)로 바꾸면, 고차원 특성 공간에서 학습하는 효과를 얻으면서도 계산 비용은 원래 차원에 비례하여 유지된다.

7.5 커널 함수의 구체적 예: 다항 커널

커널이 어떻게 계산 효율을 달성하는지 구체적인 예를 통해 증명한다.

설정

원래 입력이 \(n = 3\) 차원이라고 하자. 특성 매핑 \(\phi(x)\)를 모든 쌍별 단항식(pairwise monomial)으로 정의한다.

\[\phi(x) = \begin{bmatrix} x_1 x_1 \\ x_1 x_2 \\ x_1 x_3 \\ x_2 x_1 \\ x_2 x_2 \\ x_2 x_3 \\ x_3 x_1 \\ x_3 x_2 \\ x_3 x_3 \end{bmatrix}\]

\(x \in \mathbb{R}^n\)이면 \(\phi(x) \in \mathbb{R}^{n^2}\)이 된다. 3차원이 9차원으로 확장되었다. 실전에서는 \(n = 10{,}000\)이면 \(n^2 = 1\text{억}\)이 된다.

직접 계산의 비용

\(\phi(x)^T \phi(z)\)를 명시적으로 계산하려면, 먼저 \(n^2\)차원 벡터 \(\phi(x)\)와 \(\phi(z)\)를 각각 구성한 뒤 내적을 계산해야 한다. 이는 \(O(n^2)\) 시간이 걸린다.

커널 트릭에 의한 효율적 계산

다음을 증명한다.

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

증명:

\[(x^T z)^2 = (x^T z)(x^T z) = \left( \sum_{i=1}^{n} x_i z_i \right) \left( \sum_{j=1}^{n} x_j z_j \right) = \sum_{i=1}^{n} \sum_{j=1}^{n} x_i x_j \cdot z_i z_j\]

이 이중 합은 모든 \((i, j)\) 쌍에 대해 \(x_i x_j\)와 \(z_i z_j\)를 곱하여 더한 것이다. 이는 정확히 \(\phi(x)\)의 각 원소 \(x_i x_j\)와 \(\phi(z)\)의 대응 원소 \(z_i z_j\)를 곱하여 합산한 것, 즉 \(\phi(x)^T \phi(z)\)와 같다. \(\square\)

\((x^T z)^2\)를 계산하는 데는 \(x^T z\)가 \(O(n)\)이고 그 결과를 제곱하면 되므로, 전체 계산이 \(O(n)\)이다. \(O(n^2)\)이었던 것이 \(O(n)\)으로 줄어든 것이다.

\(n = 10{,}000\)이면, 1억 차원 벡터를 다루는 대신 1만 차원 벡터의 내적 한 번으로 같은 결과를 얻는다.

변형: 상수항 추가

\[K(x, z) = (x^T z + c)^2 \quad (c \text{는 상수})\]

이 커널은 쌍별 단항식뿐 아니라 1차 항 \(x_1, x_2, x_3\)과 상수항까지 포함하는 특성 매핑에 대응한다. 정확히는 다음과 같다.

\[\phi(x) = \begin{bmatrix} x_1 x_1 \\ x_1 x_2 \\ \vdots \\ x_3 x_3 \\ \sqrt{2c}\, x_1 \\ \sqrt{2c}\, x_2 \\ \sqrt{2c}\, x_3 \\ c \end{bmatrix}\]

상수 \(c\)는 2차 항과 1차 항 사이의 상대적 가중치를 조절한다.

일반화: \(d\)차 다항 커널

\[K(x, z) = (x^T z + c)^d\]

이 커널 역시 \(O(n)\) 시간에 계산된다. \(x^T z\)를 구하고 상수를 더한 뒤 \(d\)제곱하면 끝이다. 그러나 대응하는 특성 매핑 \(\phi(x)\)는 \(d\)차 이하의 모든 단항식(monomial)을 포함한다.

예를 들어 \(d = 5\)이면, \(x_1 x_2 x_5 x_{17} x_{29}\)나 \(x_1^2 x_3 x_{18}\) 같은 5차 이하의 모든 단항식이 특성에 포함된다. 특성의 수는 \(\binom{n+d}{d}\)로, 대략 \((n+d)^d\)에 비례하여 매우 크지만, 계산 시간은 \(d\)가 증가해도 기하급수적으로 폭발하지 않는다.

7.6 서포트 벡터 머신 = 최적 마진 분류기 + 커널 트릭

서포트 벡터 머신(SVM)의 정체는 명료하다.

\[\text{SVM} = \text{최적 마진 분류기} + \text{커널 트릭}\]

다항 커널이나 가우시안 커널 같은 커널 함수를 선택하면, 100조 차원의 특성 공간에서 선형 분류기를 학습하면서도 계산 시간은 원래 입력 차원 \(n\)에 선형으로 비례한다.

직관: 왜 이것이 좋은 아이디어인가

원래 2차원 공간에서 직선으로 분리할 수 없는 데이터를 생각하자. 파란 점과 빨간 점이 원형으로 분포하고 있다면, 직선 하나로는 이들을 나눌 수 없다.

그러나 특성 매핑 \(\phi\)를 통해 이 점들을 훨씬 높은 차원의 공간으로 보내면, 그 고차원 공간에서는 초평면(직선의 고차원 일반화)으로 분리할 수 있게 된다. 고차원 공간의 선형 결정 경계를 원래 공간으로 투영하면, 원형이나 타원형 같은 매우 비선형적인 결정 경계가 된다.

이것이 SVM의 핵심이다. 고차원 공간에서는 선형 분류기이지만, 원래 특성 공간에서 보면 매우 복잡한 비선형 결정 경계를 학습한다.

7.7 커널 함수의 유효성 조건

아무 함수나 커널로 쓸 수 있는 것은 아니다. 커널 함수 \(K(x, z)\)가 유효하려면, 어떤 특성 매핑 \(\phi\)가 존재하여 다음이 성립해야 한다.

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

이 조건을 만족하지 않는 함수를 커널로 사용하면, 최적화 문제의 유도가 무너지고 의미 없는 해가 나온다.

필요 조건의 예

벡터의 자기 자신과의 내적은 항상 비음수이므로, 유효한 커널은 다음을 만족해야 한다.

\[K(x, x) = \phi(x)^T \phi(x) = \|\phi(x)\|^2 \geq 0\]

\(K(x, x) < 0\)인 함수는 유효한 커널이 될 수 없다.

커널 행렬

임의의 \(d\)개 점 \(\{x_1, \ldots, x_d\}\)에 대해, 커널 함수를 모든 쌍에 적용하여 만든 \(d \times d\) 행렬을 커널 행렬(또는 그람 행렬)이라 한다.

\[K_{ij} = K(x_i, x_j)\]

머서 정리 (Mercer's Theorem)

\(K\)가 유효한 커널 함수일 필요충분조건은, 임의의 \(d\)개 점에 대해 대응하는 커널 행렬이 항상 양의 준정부호(positive semi-definite)인 것이다.

\[K \succeq 0 \quad (\text{즉, 임의의 벡터 } z \text{에 대해 } z^T K z \geq 0)\]

증명 (필요 조건 방향):

\[z^T K z = \sum_i \sum_j z_i K_{ij} z_j = \sum_i \sum_j z_i \phi(x_i)^T \phi(x_j) z_j\]

내적을 원소별로 전개하면,

\[= \sum_i \sum_j z_i \left( \sum_k \phi(x_i)_k \cdot \phi(x_j)_k \right) z_j = \sum_k \left( \sum_i z_i \phi(x_i)_k \right)^2 \geq 0\]

마지막 등호는 합의 순서를 바꾸고, 제곱의 합은 항상 비음수라는 사실에 의한 것이다. 이로써 커널 행렬이 양의 준정부호임이 증명된다.

역방향(양의 준정부호이면 유효한 커널)의 증명은 더 복잡하지만, 머서 정리는 양 방향 모두 성립하는 동치 조건이다.

7.8 주요 커널 함수

선형 커널

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

이는 \(\phi(x) = x\), 즉 고차원 매핑을 사용하지 않는 경우에 해당한다. 가장 많이 사용되는 커널이며, 커널 트릭의 이점을 활용하지는 않는다.

가우시안 커널 (RBF 커널)

\[K(x, z) = \exp\left( -\frac{\|x - z\|^2}{2\sigma^2} \right)\]

선형 커널 다음으로 가장 널리 사용되는 커널이다.

이 함수는 직관적으로 유사도 측정 함수의 성질을 만족한다.

• \(x\)와 \(z\)가 매우 가까우면: \(\|x - z\|^2 \approx 0\)이므로 \(K(x, z) \approx e^0 = 1\)
• \(x\)와 \(z\)가 매우 멀면: \(\|x - z\|^2\)이 크므로 \(K(x, z) \approx 0\)

가우시안 커널이 대응하는 특성 공간은 무한 차원이다. 모든 차수의 단항식 특성을 포함하되, 고차 항일수록 작은 가중치를 부여한다. 즉, \(x_1\), \(x_1 x_2\), \(x_1^2 x_2\), \(x_1^{10000}\), \(x_2^{17}\) 등 무한히 많은 다항식 특성을 끝없이 포함한다.

다항 커널

\[K(x, z) = (x^T z + c)^d\]

\(d\)차 이하의 모든 단항식 특성에 대응한다. 계산 비용은 \(O(n)\)이다.

커널의 유사도 해석

커널을 유사도 함수로 이해할 수 있다. 두 벡터 \(\phi(x)\)와 \(\phi(z)\)가 같은 방향을 가리키면 내적이 크고, 무관한 방향이면 내적이 작다. 이 원리에 따라 \(K(x, z)\)가 크면 \(x\)와 \(z\)가 유사하고, 작으면 비유사하다.

7.9 L1 소프트 마진 SVM

지금까지는 데이터가 선형 분리 가능하다고 가정했다. 그러나 현실의 데이터에는 잡음이 있고, 이상치(outlier)가 존재하며, 반드시 완벽하게 분리할 필요도 없다.

과적합 문제

고차원 특성 공간에서는 데이터가 분리 가능해질 가능성이 높아지지만, 모든 예제를 완벽히 분리하려 하면 지나치게 복잡한 결정 경계가 만들어진다. 이는 과적합의 전형적인 사례다.

이상치의 영향

기본 최적 마진 분류기는 최악의 마진을 최적화하므로, 단 하나의 이상치가 결정 경계를 극적으로 변화시킬 수 있다.

예를 들어, 양성 예제와 음성 예제가 깔끔하게 분리된 데이터에 음성 쪽에 양성 이상치가 하나 있다고 하자. 기본 알고리즘은 이 하나의 이상치 때문에 결정 경계를 크게 기울여, 나머지 모든 데이터에 대한 마진을 희생한다.

L1 소프트 마진의 정식화

이 문제를 해결하기 위해, 일부 예제가 제약 조건을 약간 위반하는 것을 허용한다.

\[\min_{w, b, \xi} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{m} \xi_i\]

\[\text{s.t.} \quad y^{(i)}(w^T x^{(i)} + b) \geq 1 - \xi_i, \quad \xi_i \geq 0, \quad i = 1, \ldots, m\]

여기서:

• \(\xi_i\) (슬랙 변수): \(i\)번째 예제가 함수 마진 1의 제약을 얼마나 위반하는지를 나타낸다
• \(C\) (정규화 매개변수): 마진 최대화와 제약 위반 허용 사이의 균형을 조절한다

함수 마진이 0보다 크면 해당 예제는 올바르게 분류된 것이다. 기본 SVM은 함수 마진이 1 이상이기를 요구하지만, 소프트 마진 SVM은 \(\xi_i\)만큼 이를 완화한다. 단, \(\xi_i\)가 너무 커지면 비용 함수에 \(C \xi_i\)가 추가되므로 벌칙이 부과된다.

최적 마진 부근 예제의 동작

결정 경계에 가장 가까운 예제들(서포트 벡터)은 함수 마진이 정확히 1이다. 더 먼 예제들은 2, 3 등 더 큰 함수 마진을 갖는다. 소프트 마진에서는 일부 예제가 마진 1보다 약간 작은 값(예: 0.5)을 가질 수 있으며, 이때 \(\xi_i = 0.5\)가 된다.

쌍대 형태에서의 변화

표현자 정리 유도를 거치면, 소프트 마진 SVM의 쌍대 문제는 기본 SVM과 거의 동일하며, 유일한 차이는 \(\alpha_i\)에 상한이 추가되는 것이다.

\[0 \leq \alpha_i \leq C\]

기본 SVM에서는 \(\alpha_i \geq 0\)만 요구했지만, 소프트 마진에서는 \(\alpha_i\)가 \(C\) 이하여야 한다.

매개변수 \(C\)의 선택 방법은 편향-분산 트레이드오프를 다루는 다음 장에서 논의한다.

7.10 커널 트릭의 일반성

커널 트릭은 SVM에만 국한되지 않는다. 알고리즘을 내적의 형태로 표현할 수 있기만 하면, 어떤 학습 알고리즘에든 커널 트릭을 적용할 수 있다.

이 강좌에서 배운 모든 판별 학습 알고리즘에 커널 트릭을 적용할 수 있다.

• 선형 회귀: 무한 차원 특성 공간에서 선형 회귀를 수행할 수 있다
• 로지스틱 회귀: 내적 형태로 재작성 가능
• 일반화 선형 모델 계열: 모두 내적 형태로 표현 가능
• 퍼셉트론 알고리즘: 마찬가지
• 주성분 분석(PCA): 내적만으로 표현되므로 커널 PCA가 가능

그러나 실무에서 커널 트릭이 가장 강력하게 활용되는 곳은 SVM이다. Vladimir Vapnik과 Corinna Cortes가 커널 트릭을 SVM에 결합하면 매우 효과적인 학습 알고리즘이 된다는 것을 발견한 이후, SVM에서의 커널 사용이 대중화되었다.

7.11 커널 설계의 응용 사례

SVM의 혁신적 연구 중 상당 부분은 커널 함수의 설계에 집중되어 있다. 입력 데이터의 특성에 맞는 커널을 설계함으로써, 고정된 형태의 특성 벡터가 없는 대상도 분류할 수 있다.

손글씨 숫자 분류

숫자 이미지는 픽셀 강도값의 행렬이다. 이를 1차원 벡터로 펼치면 \((0, 0, 0, 1, 1, 0, 0, \ldots)\) 같은 특성 \(x\)가 된다. 이 특성에 다항 커널이나 가우시안 커널을 적용하면 손글씨 숫자를 상당히 잘 분류할 수 있다.

고전적인 벤치마크인 MNIST 데이터셋에서, 커널 SVM은 오랫동안 최고 성능의 알고리즘이었다. 최근 몇 년간 합성곱 신경망(CNN)이 SVM을 능가하게 되었지만, SVM은 조정할 매개변수가 적어 매우 간편하게 사용할 수 있다는 장점이 있다.

단백질 서열 분류

단백질은 아미노산의 서열이며, 길이가 가변적이다. 고정 크기의 특성 벡터로 표현하기 어려운 대상이다.

한 가지 방법은 길이 4인 모든 아미노산 부분 서열의 출현 횟수를 세는 것이다. 아미노산이 20종이므로 \(20^4 = 160{,}000\)차원의 특성 벡터가 만들어진다.

예를 들어, 단백질 서열 "...BAJT...BAJT...TSTA..."에서 "BAJT"가 2번 등장하면 해당 위치에 2를, "TSTA"가 1번 등장하면 1을 기입한다.

이 고차원 특성의 내적 \(\phi(x)^T \phi(z)\)는 동적 프로그래밍 알고리즘으로 효율적으로 계산할 수 있다. 이 알고리즘은 문자열 매칭의 Knuth-Morris-Pratt 알고리즘과 유사하다.

히스토그램 커널

입력이 히스토그램(예: 인구 통계 분포)일 때, 두 히스토그램의 각 구간별 최솟값을 취하여 합산하는 커널 함수가 있다. 이 커널은 두 분포의 유사도를 효과적으로 측정한다.

핵심 정리

이전 장: 6장 - 서포트 벡터 머신 다음 장: 8장 - 데이터 분할, 모델과 교차 검증