test!!

$$x \in \{0,1\}^n, \quad n=10000$$
$$x_j = 1(\text{word j appears in email})$$
$x_j$ 는 단어 j가 메일에 나타나는지를 의미한다. generative model을 만들기 위해 $p(x|y), p(y)$가 필요하다. Naive Bayes에서는 $p(x|y)$가 주어진 class에서 개별 feature의 조건부 확률 곱인 $\prod^n_{j=1}p(x_j|y)$로 모델링된다. 

Naive Bayes 모델의 parameter는 아래와 같다.
$$\phi_{j|y=1} =p(x_j =1|y=1)$$
$$\phi_{j|y=0} =p(x_j =1|y=0)$$
$$\phi_{y} =p(y=1)$$

각 parameter를 MLE로 유도하면 아래와 같다.
$$\phi_y=\frac{\sum^m_i=1(y^{(i)}=1)}{m}$$
$$\phi_{j|y=1}=\frac{\sum^m_i=1(x^{(i)}=1,y^{(i)}=1)}{\sum^m_{i=1}1(y^{i)}=1)}$$
$$\phi_{j|y=1}=\frac{\sum^m_i=1(x^{(i)}=1,y^{(i)}=0)}{\sum^m_{i=1}1(y^{i)}=0)}$$

학습이 종료된 후 predict는 아래의 식으로 구한다.
$$p(y=1|x) = \frac{p(x|y=1)p(y=1)}{p(x|y=1)p(y=1)+p(x|y=0)p(y=0)}$$


큰 문제가 없어보이지만, 조금 자세히 생각해볼 지점이 있다. 특정 단어(사전의 10000개 단어 중 6017번째에 존재한다고 가정)를 포함한 메일이 없을 때 parameter의 MLE를 구하면, 
$$\phi_{j|y=1}=p(x_{6017}|y=1) = \frac {0}{\#\{y=1\}}$$
$$\phi_{j|y=0}=p(x_{6017}|y=0) = \frac {0}{\#\{y=0\}}$$
하지만, 아직 본 적이 없다고 확률이 0이라고 단정짓는 것은 통계적으로 좋지 않은 생각이다. 

#### Laplace Smoothing
Laplace smoothing은 이러한 문제를 해결할 수 있는 방법이다. 각 경우의 수에 1을 더해주어, 한 번도 보지 못한 케이스에 대해 handling할 수 있다. 이를 통해 확률이 0이 되는 것을 방지하여 의미있는 확률을 얻게 된다.
즉, 아래와 같은 식으로 추정 가능하다.
$$x\in 1, \cdots,k \quad p(x=j) = \frac{\sum^m_{j=1}(1(x^{(i)}=j))+1}{m+k}$$
Naive Bayes에서는 $\phi_{j|y=0}$의 MLE를 Laplace smoothing을 이용해 $k = 2$를 이용한다. 

#### Event model
Text classsification을 수행할 때에 특정 단어의 등장 여부가 곧 Spam, Not Spam여부를 판단하는 것도 좋지만, 특정 단어의 빈도수에 따라 spam 여부가 높아지는 것이 자연스럽다. 그러니까, "Drug! Buy Drug now!"라는 매우 의심스러운 문장이 있을 때에, 기존의 Naive Bayes에서는 아래와 같다는 것이다.
$$x = \begin{bmatrix}
0 \\
0 \\
\vdots \\
1 \\
\vdots \\
1 \\
\vdots \\
1
\end{bmatrix} \quad \begin{array}{c}
a \\
aardvark \\
\vdots \\
buy \\
\vdots \\
drug \\
\vdots \\
now
\end{array} \quad \begin{array}{c}
1st \\
2nd \\
\vdots \\
800th \\
\vdots \\
1600th \\
\vdots \\
6200th
\end{array}$$
위  문장에서 drug는 몇번 반복되건 $x_j \in 0, 1$이므로 정보의 손실이 발생하게 된다. text data의 길이는 매우 가변적이므로 위와 같이 data를 표현할 때, 길이와 무관하게 항상 같은 길이로 feature vector를 mapping하게 된다. 이러한 model을 **Multivariate Bernoulli event model**이라고 부른다. 

**Multinomial event model**이라는 text data에 해당되는 새로운 representation을 보자.
$$x = [1600 \ 800 \ 1600\ 6200] \in \mathbb{R}^{n_i} \quad x_j \in 1, \cdots,  10000 \quad n_i = \text{length of email i}$$
매번 고정된 dimension의 feature vector를 이용했으나, 이번에는 4-dim feature vector를 사용한다. 이로인해 이메일의 길이를 따르는 feature vector가 생성된다.  이 model을 이용해 generative model을 만들어보면 아래와 같다.
$$p(x,y) = p(x|y)p(y)=\prod^n_{j=1}p(x_j|y)p(y)$$
이는 저번 강의에서 Naive Bayes에 대해 [[GDA & Naive Bayes#^006e05|처음 다룰때에 보았던 식]]과 외적으로 동일하나 $n$과 $x_j$가 의미하는 것이 다르다. $n$은 email의 길이를 나타내고, $p(x_j|y)$는 binary, bernoulli probabiliry가 아닌 multinomial probability이다.
이 모델의 parameter는 $\phi_j = p(y=1), \phi_{k|y=0}=p(x_j = k|y=0) \phi_{k|y=1}=p(x_j = k|y=1)$ 이다.
모든 위치에서 단어 k가 등장할 확률은 모두 같다고 가정한다. $\phi_{k|y=0}$의 MLE는 아래와 같다.
$$\phi_{k|y=0} = \frac{\sum_{i=1}^{m} \left( 1y^{(i)} = 0 \sum_{j=1}^{n_i} 1x_j^{(i)} = k \right)}{\sum_{i=1}^{m} 1y^{(i)} = 0n_i}$$
분모는 학습 데이터셋의 스팸이 아닌 모든 메일들의 단어수를 더한 것이고 분자는 스팸이 아닌 모든 메일들에서 k가 등장하는 수를 더한것이다. 여기에 Laplace smoothing을 적용하기 위해 분자에 1을 더해주고, 분모에는 k가 될 수 있는 값인 feature vector의 dimension크기가 된다. 
$$\phi_{k|y=0} = \frac{\sum_{i=1}^{m} \left( 1y^{(i)} = 0 \sum_{j=1}^{n_i} 1x_j^{(i)} = k \right)+1}{\sum_{i=1}^{m} 1y^{(i)} = 0n_i+10000}$$

학습을 수행한 text data set에 존재하지 않는 단어를 처리하는 방법에는 크게 두 가지가 존재한다. 
1. 그냥 무시한다.
2. Unknown 토큰을 생성하여 특별한 token으로 handling한다.

Naive bayes는 계산량이 효율적이고 비교적 빠르게 구현가능하다. quick and dirty하게 모델을 구현할 때에 의미있게 사용된다.

## SVM
어떤 dataset에 대해 non-linear decision boundary를 찾아야 할 때에, SVM은 매우 유용한 방법중 하나이다. 이전의 학습한 Logistic regression에서 non-linearlity를 적용하는 방법은 feature에 대해 polynomial term을 적용하여 high dimensional feature vector로 mapping하는 것이었다. 하지만, 수식을 생각하기 어려운 non-linear decision boundary를 얻기 위한 feature를 고르는 것은 매우 어려운 일이다.

SVM에서는 이러한 feature를 고차원의 feature set으로 mapping 시켜 linear classification을 적용한다. 이는 logistic regerssion과 비슷하지만, non-linear dicision boundary를 학습하는 자세한 방법은 조금 다르다. 현재 SVM의 용도는 효과적이기를 기대하기 보다는 즉시 작동하는 일종의(turn key)특성에 기인하여 사용된다. 우선 두가지 선행 개념을 알고 들어가자.

<svg width="600" height="400" viewBox="0 0 600 400" xmlns="http://www.w3.org/2000/svg"> <!-- Background --> <rect width="600" height="400" fill="#404040"/> <!-- Grid lines --> <defs> <pattern id="grid" width="40" height="40" patternUnits="userSpaceOnUse"> <path d="M 40 0 L 0 0 0 40" fill="none" stroke="#666" stroke-width="1"/> </pattern> </defs> <rect width="600" height="400" fill="url(#grid)"/> <!-- Coordinate axes --> <line x1="80" y1="0" x2="80" y2="400" stroke="white" stroke-width="3"/> <line x1="0" y1="320" x2="600" y2="320" stroke="white" stroke-width="3"/> <!-- Data points - O class (circles) --> <ellipse cx="180" cy="220" rx="15" ry="10" fill="none" stroke="white" stroke-width="3"/> <ellipse cx="200" cy="280" rx="15" ry="10" fill="none" stroke="white" stroke-width="3"/> <ellipse cx="160" cy="260" rx="15" ry="10" fill="none" stroke="white" stroke-width="3"/> <!-- Data points - X class --> <g stroke="white" stroke-width="3"> <line x1="420" y1="120" x2="440" y2="140"/> <line x1="440" y1="120" x2="420" y2="140"/> <line x1="480" y1="160" x2="500" y2="180"/> <line x1="500" y1="160" x2="480" y2="180"/> <line x1="460" y1="220" x2="480" y2="240"/> <line x1="480" y1="220" x2="460" y2="240"/> </g> <!-- Decision boundary (green line) --> <line x1="200" y1="80" x2="520" y2="380" stroke="#00ff00" stroke-width="4"/> <!-- Alternative boundary (red line) --> <line x1="320" y1="60" x2="320" y2="380" stroke="#ff6b6b" stroke-width="4"/> </svg>
###### Functional margin
Classifier의 functional margin은 쉽게 말해 얼마나 잘 example을 분류하는지를 의미한다. $h_\theta = g(\theta^T x), \ g = \text{sigmoid}$이고, $\theta^Tx \geq 0$일때 1, 아닐 때 0을 예측한다고 할 때에 $y^{i}$가 1이라면 $\theta^Tx^{(i)}$ 의 값이 0보다 많이 커야 $h_\theta$의 값이 1에 가까워진다. $y^{(i)}=1$일때, $h_\theta$가 1과 가까울수록 더욱 의미있는 예측값이다. 이런경우를 large functional margin이라 한다.

$(x^{(i)},y^{(i)})$에 대한 hyperplane의 functional margin은 $(w, b)$로 정의된다.
$$\hat\gamma^{(i)}=y^{(i)}(w^Tx^{(i)}+b)$$
- $y^{(i)}=1$이면, $w^Tx^{(i)}+b >> 0$이길 원한다.
- $y^{(i)}=-1$이면, $w^Tx^{(i)}+b << 0$이길 원한다.
- $\hat \gamma^{(i)}$는 이 둘 간의 곱이므로 이를 정리하면 $\hat\gamma^{(i)}>>0$이길 원한다.
- $\hat \gamma^{(i)}>0$는 $h(x^{(i)}) = y^{(i)}$를 의미한다.

training set전체에 대한 functional margin은 각 example의 functional margin의 최솟값으로 정의된다.
$$\hat\gamma = \min_i\hat\gamma^{(i)}$$
이처럼 구한 functional margin은 $w,b$에 상수를 곱하는 cheating으로 쉽게 늘릴 수 있으나, $h_{w,b}$ 는$w^Tx^{(i)}+b$ 값이 아닌 부호에만 의미가 있으므로 유의미한 변화가 발생하지는 않는다. 이런 cheating을 방지하기위해 $w,b$의 길이를 1로 만드는 normalizing을 한다. 이는 classification의 결과에 영향을 주지 않는 parameter의 크기만 변경하는 작업이다.
###### Geomatric margin
위 그림에서 초록, 빨강선 모두 잘 분리했으나, 초록선이 더 잘 분리한 것처럼 보인다. 이는 빨간 선이 training example과 더 가까이 있고, 초록 선은 더 멀리 떨어져 있기 때문이다. 이러한 물리적 간격을 geomatric margin이라 한다. SVM의 기본 기능은 Optimal margin classifier이고 이는 geomatric margin을 maximize하도록 최적화 하는것이다.

그림에서 초록선 위쪽은 $y^{(i)}=1$로 예측하고, 아래쪽은 $y^{(i)}=0$으로 예측한다. geomatric margin은 곧 직선까지의 거리를 의미하므로 $(x^{(i)},y^{(i)})$에 대한 hyperplane의 geomatric margin은 아래와 같이 정의한다.
$$\gamma^{(i)} = \frac{y^{(i)}(w^Tx^{(i)}+b)}{||w||}$$
분자는 functional margin과 동일하므로 아래와 같이 정의도 가능하다.
$$\gamma^{(i)}=\frac{\hat\gamma^{(i)}}{||w||}$$
training set 전체에 대한 geomatric margin은 example의 geomatric margin의 최솟값으로 정의된다.
$$\gamma = \min_i\gamma^{(i)}$$

따라서 Optimal margin classifier는 $\gamma$를 최대화 하는 $w,b$를 고른다.
$$\max_{\gamma, w, b} \gamma \quad s.t. \quad \frac{y^{(i)} (w^T x^{(i)} + b)}{\|w\|} \geq \gamma, \quad i = 1, \ldots, m$$
하지만, 이는 convex optimization problem이 아니라 gradient descent로 해결하기 어렵다. 이를 convex optimization problem으로 바꿔주면 위 식은 아래와 같아진다.
$$\min_{w,b} \frac{1}{2} \|w\|^2 \quad s.t. \quad y^{(i)} \left( w^T x^{(i)} + b \right) \geq 1$$

해당 식을 유도하는 과정을 살펴보자.

우선은, 기본적으로 geomatric margin을 최대화 하면서 w, b로 parameterozed 되어있는 decision boundary를 찾고 decision boundary중 $\gamma$가 가장 큰 값을 찾아야한다. 즉, 아래와 같이 optimization problem을 claim할 수 있다.
$$\max_{\gamma, w, b} \gamma$$
$$s.t. \frac{y^{(i)}(w^Tx^{(i)} +b)}{||w||}\geq\gamma, \quad i=1,\cdots,m$$
이 식은 모든 example이 $\gamma$보다 크거나 같은 geomatric margin을 갖는다는 것이고, 이는 최악의 경우 geomatric margin을 최대화 함을 의미한다. 예를 들어 $\gamma$가 17이라면, 모든 example들은 17이상인 geomatric margin을 갖는다. 이런 $\gamma$를 최대화 하도록 $w,b$를 찾아야한다. 위 식의 분가자 functional margin이므로, $w,b$에 상수를 곱해 decision boundarary가 같은 상태를 유지하면서 값을 변경할 수 있다.
$||w||=\frac{1}{\gamma}$가 되도록 상수를 곱하면 아래와 같은 식을 얻는다.
$$\max_{w,b} \frac{1}{||w||}$$
$$s.t. \ y^{(i)}(w^Tx^{(i)}+b) \geq 1, \ i = 1,\cdots, m$$
위 식의 $1/||w||$를 최대화 하지 말고 $||w||^2$를 최소화 한다면 아래와 같은 식을 얻는다.
$$\min_{w,b} ||w||^2$$
$$s.t. \ y^{(i)}(w^Tx^{(i)}+b) \geq 1, \ i = 1,\cdots, m$$


#### Represent Theorem
input이 매우 방대한 dimension을 갖는 상황을 고려하고, w가 training example의 linear combination이라고 가정하자.
$$w=\sum^m_{i=1}\alpha_ix^{(i)}$$
이러한 가정은 성능저하를 일으키지 않는다고 representation theorem에 의해 밝혀졌다. 또한 관례적으로, $y^{(i)}$를 곱한 아래와 같은 식을 이용한다.
$$w=\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)} \ , \quad y^{(i)} = \pm1$$
이를 증명하는 것은 매우 복잡하므로 직관적으로 이해를 해보자. 

###### case 1
로지스틱 회귀를 stochastic gradient descent와 학습할 때, $\theta = 0$으로 초기화 한 후에 $\theta := \theta + \alpha(h_{\theta}(x^{(i)})-y^{(i)})x^{(i)}$로 업데이트를 수행한다. 이 식으로 매 반복마다 parameter $\theta$를 training example에 상수를 곱한 것을 더하거나 빼서 업데이트함을 알 수 있다. 귀납적으로 $\theta$의 초기값이 0이고, gradient descent의 모든 반복이 training example에 곱한 것을 더하므로 iteration이 얼마나 반복되었는지에 무관하게 $\theta$는 training example의 linear combination이다. 따라서 SVM에서 gradient descent를 이용해 w를 최적화할 때에 w가 training example의 linear combination임을 귀납적으로 증명가능하다.

###### case 2
$g([2\ 1]x-2)$라는 classifier가 있을 때에 vector w는 항상 decision boundary와 수직이다. w는 decision boundary의 방향을 정하고 b는 decision boundary의 위치를 정한다.
![[스크린샷 2025-08-17 02.03.23.png]]
feature가 3개 있을 때, 모든 ex가 $x_1x_2$평면 위에 위치한다고 하자. 모든 ex의 $x_3=0$이다. decision boundary는 평면에 수직으로 만들어질 것이다. decision boundary $w^Tx+b=0$이고 $w_3=0$이다. 이는 vector w가 $x_1, x_2$의 span, traingin example의 span으로 표현됨을 의미한다.

#### Dual Optimization problem
$$w=\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)},\quad y^{(i)}=\pm1$$
해당 식을 Optimal margin classifier의 w에 대입하면 아래와 같이 전개된다.

$$\frac{1}{2}||w||^2 = \frac{1}{2} \left(\sum_{i=1}^{m} \alpha_i y^{(i)} x^{(i)}\right)^T \left(\sum_{j=1}^{m} \alpha_j y^{(j)} x^{(j)}\right)$$
$$\quad= \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$$

$$y^{(i)} \left(w^T x^{(i)} + b\right)= y^{(i)} \left(\left(\sum_{j=1}^{m} \alpha_j y^{(j)} x^{(j)}\right)^T x^{(i)} + b\right)
$$$$\quad\quad= y^{(i)} \left(\sum_{j=1}^{m} \alpha_j y^{(j)} \langle x^{(j)}, x^{(i)} \rangle + b\right)$$
정리하자면 아래와 같다.
$$\min_{\alpha} \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 y^{(i)} \left(\sum_{j=1}^{m} \alpha_j y^{(j)} \langle x^{(j)}, x^{(i)} \rangle + b\right) \geq 1, \quad i = 1, \ldots, m$$

$<x^{(i)},x^{(j)}>$는 내적을 의미한다. 즉, feature vector의 내적을 효율적으로 계산하면 무한한 차원의 feature vector도 쉽게 계산가능하다. 

이를 더 간소화 하여 parameter $\alpha$에 대한 식을 사용할 수 있다
$$\max\sum^m_i\alpha_i-\frac{1}{2}\sum^m_{i=1}\sum^m_{j=1}\alpha_i\alpha_jy^{(i)}y^{(j)}<x^{(i)}, x^{(j)}>$$
$$s.t. \quad \alpha_i \geq 0, \ \sum^m_iy^{(i)}\alpha_i=0$$
이 식을 dual optimization problem이라고 부른다. prediction을 하기위한 방법은 아래와 같다.
1. optimization problem을 $\alpha_i$와 $b$에 대해 해결한다.
2. $h_{w,b}(x) = g(w^Tx+b)=g(\sum^m_{i=1}\alpha_iy^{(i)}<x^{(i)},x>+b)$를 계산한다.

#### Kernel
Kernel trick은 다음과 같다.
1. $<x,z>$항에 대해 알고리즘을 작성한다.
2. $x \mapsto \phi(x)$에 대한 mapping을 정의한다.
3. $K(x,z) = \phi(x)^T\phi(z)$를 계산하는 방법을 찾는다.
4. $<x,z>$를 $K(x,z)$로 바꾼다.

예시를 통해 이해해보자. input vector가 3차원이고 $\phi(x)$가 각 요소들의 곱이라고 하자. 
$$x = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}, \quad x \in \mathbb{R}^n, \quad \phi(x) = \begin{bmatrix} x_1x_1 \\ x_1x_2 \\ x_1x_3 \\ x_2x_1 \\ x_2x_2 \\ x_2x_3 \\ x_3x_1 \\ x_3x_2 \\ x_3x_3 \end{bmatrix}, \quad \phi(x) \in \mathbb{R}^{n^2}$$
$\phi(x)$가 $n^2$개의 요소가 있으므로, $\phi(x)$또는 $\phi(x)^ㅆ$$\phi(x)$ 를 계산하는데 $O(n^2)$시간이 소요된다. 이를 좀 더 빠르게 계산하는 $K(x,z)$를 찾아보자.
$$K(x,z) = \phi(x)^T\phi(z)=(x^Tz)^2$$
$x, z$가 n차원이므로 $x^Tz$를 계산하는데 $O(n)$이 소요된다. 

#### So..
SVM은 optimal margin classifier와 kernel trick이 결합된 학습 알고리즘이다. 이로 인해 매우 높은 차원의 feature space에서 SVM이 실행가능하다. data를 더 높은 차원으로 mapping하여 고차원 공간에서 linear decision boundary를 찾는것이 original space에서 non-linear decision boundary를 찾는 것이다.


###### How to make kernel
- 만약 x, z가 비슷하면, K(x,z)가 크다.
- 만약 x, z가 비슷하지 않다면, K(x,z)가 작다.

즉 kernel을 유사도 측정함수라고 생각하면, 유사할 수록 1이 되고, 유사하지 않다면 0에 가까워야 하는 일종의 Gaussian 함수와 비슷한 form을 갖게 된다. 
$$K(x,z) = \exp\bigg(-\frac{||x-z||^2}{2\sigma^2} \bigg)$$
하지만 이를 kernel function으로 사용해도 괜찮을까? $K(x,z) = \phi(x)^T\phi(z)$를 만족하는 $\phi$가 존재할 때에만 kernel function으로 사용가능하다. 모든 알고리즘이 이 조건을 만족한다고 가정하고 유도했으므로, 이러한 가정이 틀리다면 매우 이상한 solution을 갖게 되나. 이로 인해 우리가 고르는 kernel function에 제약이 생긴다. 이중 하나는 $K(x, x) = \phi(x)^T\phi(x) \geq 0$ 으로, 자기 자신과의 내적은 음수가 될 수 없다. K(x,x)가 0보다 작아지면 이는 유효한 kernel function이 아니다. 

이를 간략하게 증명해보자.

** 커널 행렬의 양의 정부호성 증명**

${x^{(1)}, \ldots, x^{(d)}}$를 $d$개의 점이라고 하고 $K \in \mathbb{R}^{n \times n}$을 "kernel matrix"라고 할 때 $K_{ij} = K(x^{(i)}, x^{(j)})$이다.
점들의 모든 상에 대해 kernel function을 적용해 $d \times d$ matrix에 넣은 것이다. 임의의 vector $z$가 주어졌을 때 아래 식을 만족한다.


$$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 \sum_k \left(\phi(x^{(i)})\right)_k \left(\phi(x^{(j)})\right)_k z_j$$

$$= \sum_k \sum_i \sum_j z_i \left(\phi(x^{(i)})\right)_k \left(\phi(x^{(j)})\right)_k z_j$$

$$= \sum_k \left(\sum_i z_i \phi(x^{(i)})_k\right)^2$$

$$\geq 0$$

따라서 $K \geq 0$이다.

###### Mercer Theorem
$K$가 유효한 kernel function($K(x,z)=\phi(x)^T\phi(z)$를 만족하는 $\phi$가 존재하는 것)과 임의의 d개의 점들 $x^{(1)}, \cdots, x^{(d)}$에 대응하는 kernel matrix $K \geq0$ 은 필요충분조건이다. 이는 커널 함수의 유효성을 증명하는 하나의 테스트이다.

이것은 유효한 kernel로 gaussian kernel이라고 한다. 가장 넓게 사용되는 kernel은 linear kernel인데 gaussian kernel은 linear kernel 다음으로 가장 넓게 사용되는 kernel이다. linear kernel은 $K(x,z) = x^Tz$ $\phi(x) = x$ 이다. 이것은 고차원으로의 feature mapping을 사용하지 않는다는 것을 의미한다. 이것이 가장 일반적으로 사용되는 kernel이고 다른 말로 kernel의 장점을 사용하지 않는다는 것을 의미한다.

반면 Gaussian kernel의 feature space는 무한한 차원에 대응한다. 이는 kernel function이므로 모든 단항식 feature를 사용한다. 따라서 이 kernel은 끊임없는 임의의 고차원 feature를 사용하며 아주 높은 차원에는 더 적은 가중치를 둔다.

커널 트릭은 내적의 관점에서 사용된 모든 알고리즘에 사용할 수 있다. 커널 트릭을 적용하는 방법은 learning algorithm의 모든 것을 내적의 관점으로 작성하고 내적을 적절한 kernel function으로 치환하면 된다. 앞으로 배운 모든 구분학습 알고리즘은 커널트릭을 사용할 수 있다. 따라서, 무한한 차원의 feature space에 알고리즘을 적용할 수 있다.

#### Soft Margin SVM
data가 noisy하게 섞여있을 떄에 완벽한 분리는 decision boundary가 매우 복잡해진다. 고차원의 feature space에서도 linear하게 분리되지 않는 경우 training set에 대해 error가 0인 알고리즘을 원하지 않을 수 있다. 이런 알고리즘을 L1 norm soft margin SVM이라고 한다.
$$\begin{align} \min_{w,b,\xi} \quad &\frac{1}{2}||w||^2 + C\sum_{i=1}^{m} \xi_i \ \text{s.t.} \quad &y^{(i)} \left(w^T x^{(i)} + b\right) \geq 1 - \xi_i, \quad \xi_i \geq 0 \end{align}$$
functional margin이 0이상이면 알고리즘이 예시를 잘 분류했음을 의미한다. SVM은 알맞게 분류할 뿐 아니라 1보다 큰 functional margin과 함께 알맞게 분류해야한다. 0보다 큰 $\xi_i$는 이 제약을 완화한다. 하지만 $\xi_i$가 너무 커지는 것을 원치 않으므로 optimization cost function에 $\sum^m_{i=0}\xi_i$를 추가하여 $\xi_i$에 cost를 추가한다.

L1 norm soft margin SVM을 사용하는 또 다른 이유는 이상치와 관련이 있다. 기존의 SVM은 최악의 경우의 margin을 최적화 하였다. 따라서 하나의 이상치가 decision boundary에 큰 영향을 줄 수 있다. L1 norm soft margin SVM은 기존의 SVM보다 이상치에 영향이 적다.

L1 norm soft margin SVM의 dual form은 아래와 같다.

$$\begin{align} \max_{\alpha} \quad &\sum_i \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 &0 \leq \alpha_i \leq C, \quad \sum_i y^{(i)} \alpha_i = 0 \end{align}$$