@ 05. Suppor Vector Machine(SVM)
@ 학습목표.
1. 서포트 벡터 머신의 분류 원리에 대해서 이해한다.
1. 서포트 벡터 머신의 학습이 최적화 문제로 변형되어 해결되는 과정을 이해할 수 있다.
1. 소프트 마진 분류기와 커널을 사용한 비선형 분류기를 이해할 수 있다.

@ 그래프.

@ 결정영역을 결정짓기 위해서 초평면을 선택해야 할때 가능한 초평면의 가짓수는 한가지가 아닐 것이다.
초평면 : 데이터 임베딩 공간에서 한 차원 낮은 부분공간(subspace)를 의미한다.
예를 들어, 3차원 공간의 데이터 임베딩 공간에서, 초평면은 2차원 평면이다.
2차원 데이터 임베딩 공간에서는, 1차원평면(선) 이다.
2차원 데이터 임베딩 공간에서 초평면은 ax+by-c=0 의 형태의 직선 수식을 가진다.
야외활동을 해야할지 말아야할지 분류해주는 분류기를 보면 어쨋든 분류만 해주면 되니까 가능한 많은 분류기 해답이 존재한다.
여러 선형 분류기들이 있지만 이들이 항상 최적의 초평면을 찾지는 않는다.
퍼셉트론 알고리즘이 한가지 예시가 될 수 있다.
최적의 초평면 조건은 무엇일까?
1. 초평면과 결정영역 근처에 있는 분류하기 애매한 데이터의 거리가 최대가 되도록 해야 한다.
먄약 어떤 데이터가 아주 근소한 차이로 초평면의 왼쪽에 위치하고 있다면 해당 데이터는 왼쪽 클래스로 분류가 되겠지만 실제로 해당데이터가 오른쪽에 있는건데 노이즈가 끼어서 근소하게 왼쪽으로 분류되었을 수도 있다. 이런 애매한 경우를 줄이기 위해서 결정영역 근처에는 데이터가 없는 편이 가장 좋다. 1. 직관적인 이해 : 만약 결정 영역 근처에 데이터가 없다면, 분류기는 분류 결정을 하기 위해 불확실 하고 애매한 결정을 내리는 경우가 조금 더 드물어 질 것이다.

@ 또 다른 직관.
만약 결정영역이 두껍다면 애매한 경우가 줄어든다.
또한 모델의 파라미터, 즉, 모델의 갯수도 줄일 수 있다.
가능한 결정영역의 가짓수가 하나가 될 때까지 최대한 결정영역의 선을 두껍게 만드는 것이 SVM의 학습 전략이다.

@ SVM은 결정영역의 초평면을 둘러 싸고 있는 margin 을 최대화 시킨다. 직선형태의 결정영역을 크게 만드는 것과 유사하다. margin은 초평면의 위치에 따라 달라질수 있다. 초평면에 가장 가까운 데이터를 서포트 벡터 라고 부른다. SVM은 훈련 예제의 부분집합인 서포트 벡터만을 사용하여 클래스 결정함수를 완전히 설명, 나타낼 수 있다.
즉, 트레이닝시에 SVM은 다른 모든 데이터는 잊어버린채 SV만 사용하여 분류모델을 만들어 낼 수 있다는 뜻이다.
이런방식은 SVM의 모델 파라미터 갯수를 크게 줄일 수 있다.
90년대 초반 미국의 벨연구소에서 일하던 블라드미르 라프닉 소련의 수학자로부터 탄생한 SVM은 딥러닝이 나오기 전까지 가장 성공한 분류기 역할 을 했다.
SVM은 숫자인식 문제에서도 사람의 뇌를 모사한 다층신경망 처럼 좋은 성능을 보여주었다. 이 일을 계기로 경쟁이 벌어지기도 했다. 지금은 딥러닝의 등장으로 SVM이 뒤로 물러났다. 하지만 언제 딥러닝을 뛰어넘는 개선된 SVM으로 다시 등장할 지는 모르는 일이다.
서포트 벡터 머신의 결정 함수를 구하는 것은 함수 최적화 문제이다.

@ 서포트 벡터머신의 함수는 $y = \text{sign}(w^{T}X+b)$ 로 나타낼 수 있다.
w: 정규화된 결정 초평면 벡터.
$x_{i}$ : i번째 데이터.
$y_{i}$ : i번째 데이터의 클래스이다. +1 또는 -1이다.

@ w, X 벡터는 기본적으로 colmun 벡터이다. dot product 를 하기 위해서 colmun 벡터인 w를 row 벡터로 바꿔주는게 transpose 이다. $w^{T}$.
@ 서포트 벡터 머신 형식.
분류기 형식
$y_{i} = f(x_{i}) = \text{sign}(w^{T}x_{i}+b)$
sign 함수 : 수의 부호를 판별하는 함수이다.
$w^{T}x_{i}+b \geq +1$ 이면 양의 클래스 $y_{i} = +1$ 로 분류
$w^{T}x_{i}+b \leq +1$ 이면 음의 클래스 $y_{i} = -1$ 로 분류 하는 것이 sign함수의 역할이다.
$y_{i}(w^{T}x_{i}+b)$ 는 $x_{i}$ 의 기능적 마진(functional margin) 이라고 불린다.
주어진 i번째 데이터가 적절하게 분류되었는지 아닌지 가늠할 수 있는 테스트 함수의 역할을 하기 때문이다.
클래스 y와 $w^{T}x+b$ 를 곱하면 $|w^{T}x+b|$ 을 계산하는 것으로 볼 수도 있다. 위의 값이 클수록 데이터들와 초평면과의 거리가 멀기때문에 데이터가 적절하게 분류되었는지 확인할 수 있다.
파라미터 w와 b의 크기를 키움으로써 기능적 마진의 값도 커진다.
즉, 데이터를 올바르게 분류했는지 평가하기 위해서 파라미터의 크기에 민감하지 않은 평가 척도(기하마진)가 필요하게 된것이다.

@ 기하마진(geometric margin) 은 기능적 margin($w^{T}x+b$) 을 w의 크기($||w||$)로 나눈 값이다.
이 값은 i번째 데이터에서 결정 영역까지의 거리 r으로 볼 수 있다.
$r = y\frac{w^{T}x+b}{||w||}$
r을 계산하기 위한 과정.
데이터 X를 지나면서 결정영역에 직교하는 직선 r과 결정영역의 교점을 X' 이라고 할때 선분 XX'은 결정영역에 직교하면서 w에 평행하다. w는 결정영역에 수직인 법선벡터이기 때문이다.
w의 단위 벡터는 $\frac{w}{||w||}$ 이다. 점선은 $r\frac{w}{||w||}$ 이다.
$X' = X - Yr\frac{w}{||w||}$
X'은 초평면 위의 점이기 때문에 $w^{T}X' + b = 0$ 을 만족하므로 위에서 유도된 X'을 이식에 대입하면,
$w^{T}(X - Yr\frac{w}{||w||}) + b = 0$ 을 얻을 수 있다. 식을 전개하면
$||w|| = \sqrt{(w^{T}w)}$ 이고, $w^{T}x-yr||w|| + b = 0$ 이므로
r에 대해서 정리하면, $r = \frac{y(w^{T}x+b)}{||w||}$
결정 영역까지 가장 가까운 데이터들을 서포트 벡터 라고 한다.
결정영역의 마진 $\rho$ 는 평면상의 각 클래스에 포함되어있는 서포트 벡터와 초평면 사이의 거리이다.

@ 선형 서포트 벡터머신.
모든 데이터가 결정영역으로부터 항상 최소 1 이상 떨어져 있다고 가정한다면(모든 데이터에 대한 기능적 마진${\geq}$1) 이라고 가정한다면, 다음 두 개의 조건이 훈련 데이터 집합 $\{(x_{i}, y_{i})\}$ 에 대해 만족한다.
1. $w^{T}x_{i}+b \geq 1$ 이면 양의 클래스 $y_{i} = 1$ 로 분류한다. 일때.
1. $w^{T}x_{i}+b \leq -1$ 이면 음의 클래스 $y_{i} = -1$ 로 분류할 수 있다.

@ 서포트 벡터의 기능적 마진 $w^{T}x_{i} + b$ 의 값은 1또는 -1의 값을 만족할 것이다. 이 때 각 데이터 포인트 로부터 결정 영역까지의 거리는 기능적 마진을 파라미터 w의 크기($||w||$) 로 나눈 것으로 볼 수 있다.

@ 서포트 벡터는 부등호가 등호고 바뀐다.
각 i번째 데이터 로 부터 결정영역까지 거리 r
기능적 마진을 파라미터 w에 따라 크기를 바꿔준다.
기하마진은 i번째 데이터들이 적절하게 분류가 잘 되었는지 w의 크기 $||w||$ 로 스케일링된 척도로 알려준다.
@ 결정영역의 마진 $\rho$ 서포트벡터의 기능적 마진이 1이기 때문에 : $\frac{2}{||w||}$

@ 정리하자면,
초평면은 다음과 같이 나타낸다.
$w^{T}x_{i}+b=0$
서포트 벡터의 기하마진이 즉 거리 r이 1을 가져야할 때 조건은 $|w^{T}x_{i}+b|$ 의 최소값이 1이어야한다는 조건이다. $\text{min}_{i=1,2,...,n}|w^{T}x_{i}+b| = 1$
빨간 클래스에서는 $w^{T}x_{i}+b = 1$ 을 만족하고, 파란 클래스에서는 $w^{T}x_{i}+b = -1$ 을 만족한다.
결론적으로, 1보다 크면 빨간클래스, 작으면 파란 클래스이다.

@ $x_{a}$와 $x_{b}$가 서로 다른 클래스의 서포트 벡터일때, $w^{T}(x_{a}-x_{b}) = 2$ 이다
결정영역의 마진 $\rho = ||x_{a} - x_{b}||_{2} - \frac{2}{||w||_{2}}$
여기서 말하는 subscript 2는 L2 norm 을 의미한다.

@ 서포트 벡터 머신의 파라미터를 찾는 문제는 조건부 최적화 문제(일정한 제약조건 아래에서 함수를 최대화 하거나 최소화하는 문제이다, 우리가 살고 있는 우주는 에너지를 일정하게 유지하는 조건 아래에서 엔트로피를 최대화시키고 비슷한 유형의 문제는 공장에서도 많이 다뤄진다.)로 변형시켜서 풀수 있다.
데이터 $x_{i}$와 레이블 $y_{i}$ 가 있을 때, 파라미터 w와 b를 찾을 때, 마진을 가장 높게 해주는 파라미터를 찾아야 한다. 추가조건으로 $y_{i}$ 가 1인 경우, $w^{T}x_{i}+b$는 1보다 크거나 같아야하고, $y_{i}$ 가 -1인 경우, $w^{T}x_{i}+b$는 1보다 작거나 같아야한다. 위의 내용을 정리.
$\frac{1}{||w||}$을 최대화 해주는 모든 x, y에 대한 파라미터 w와 b를 찾아라.
$w^{T}x_{i}+b \geq 1$ 이면 $y_{i}=1$ 이다.
$w^{T}x_{i}+b \leq -1$ 이면 $y_{i}=-1$ 이다.
@ 이 문제를 조금더 깔끔한 형식으로 변형해 보자.
$||w||$를 최소화하는 것은 $\frac{1}{||w||}$ 를 최대화하는것과 같다는 점과,
w와 w의 내적값의 크기는 w크기가 가장 작을때 최소값을 갖는다는점을 사용한다면,
다음과 같이 적을 수 있다.
x, y 가 주어졌을 때,
$\frac{1}{2}w^{T}w$ 의 출력값 $\Phi(w)$ 를 가장 최소화 하는 파라미터 w와 b를 계산하는 것이다.
추가 조건으로는 모든 데이터 $\{x_{i}, y_{i}\}$ 에 대하여 $y_{i}(w^{T}x_{i}+b) \geq 1$ 을 만족시켜야한다.

@ 최적화 문제로 변형시킨 상태에서 파라미터를 계산한다.
모든 데이터 집합이 $\{(x_{i}, y_{i})\}$ $y_{i}(w^{T}x_{i}+b) \geq 1$ 를 만족할 때
$\Phi(w)= \frac{1}{2}w^{T}w$ 가 최소가 되도록 w, b 를 찾아라.
위 문제는 선형조건 $y_{i}(w^{T}x_{i}+b) \geq 1$ 에 부합하도록 이차함수 $\Phi(w)= \frac{1}{2}w^{T}w$ 가 최소값을 갖도록 최적화 시키는 문제이다.
1. 이차함수의 최적화 문제는 수학적 프로그래밍 문제에서 잘 알려진 분야로, 해결할 수 있는 많은 알고리즘이 존재한다.
1. 여러 알고리즘 중 Lagrangian multiplier $a_{i}$ 를 사용하여 다음의 primal 과 dual problem 으로 변형 할 수 있다.
primal 문제로 변형시키면,
최적화할 조건 $w^{T}x_{i}-b$ 과 Lagrangian multiplier $a_{i}$ 의 곱의 n개의 합 이 포함된,
$L(w,b) = \frac{1}{2}w^{T}w-{\sum}a_{i}\{y_{i}(w^{T}x_{i}-b)-1\}$ 를 최적화 시키는 문제로 바뀐다.
이때, n개(데이터의 갯수)의 Lagrangian multiplier $a_{i}$은 모두 0보다 크거나 같다.
primal 식을 w에 대하여 미분한다.
$w - {\sum}(a_{y}x) = 0$
$w = {\sum}(a_{y}x)$
primal 식을 b에 대하여 미분한다.
${\sum}(a_{y}) = 0$ $w = {\sum}(a_{y}x), {\sum}(a_{y}) = 0$ 이 두 식을 primal 식에 대입하면 아래의 식이 나온다. 이 문제를 dual problem 이라고 한다.
primal 이 w, b에 대해서 최적화를 시키는 반면, dual problem 은 Lagrangian multiplier $a_{i}$ 에 대해 최적화를 시킨다.
함수 $Q(a) = {\sum}a_{i} - \frac{1}{2}{\sum}{\sum}a_{i}a_{j}y_{i}y_{j}x_{i}^{T}a_{j}$ 를 최소화하면서 다음의 두 조건,
1. ${\sum}ay_{i} = 0$
1. ${\forall} a_{i}, a_{i} {\geq} 0$ 을 만족하는
다음의 Lagrangian multiplier $a_{1}, ..., a_{n}$ 을 찾아라.

@ 최적화 문제를 사용한 파라미터 계산 3단계
Lagrangian multiplier 을 사용해 모델 파라미터 w, b의 솔루션은 다음과 같은 형식을 가진다.
$w = {\sum}a_{i}y_{i}X_{i}$
$b = y_{k}-w^{T}X_{k}$
이때 k는 $a_{k} \neq 0$ 을 만족시킨다.
dual problem 문제를 풀면 Lagrangian multiplier 의 값을 계산할 수 있다. 대부분의 Lagrangian multiplier 값은 0의 값을 갖는다.
0이 아닌 Lagrangian multiplier $a_{i}$는 해당하는 데이터 $x_{i}$ 가 서포트 벡터임을 의미한다.
원래 분류함수 $f(x) = wx+b$ 의 형태였지만 Lagrangian multiplier 에 대한 분류함수 $f(X)$ 는 다음과 같은 형식이다.
$f(X) = {\sum}a_{i}y_{i}X_{i}^{T}X + b$
서포트 벡터를 제외한 모든 Lagrangian multiplier 값은 0이므로 분류는 ${\sum}$ 이 들어있긴하지만 새로운 테스트 데이터 x와 서포트 벡터 $x_{i}$ 의 내적에 의해 계산될 수 있다.
하지만 모델의 훈련 과정 때는 모든 훈련 데이터 쌍 $(x_{i},x_{j})$ 에 대해 내적 $x_{i}^{T}{\cdot}x_{j}$ 을 계산한다.
@ 지금 까지 선형 분류기로서 서포트 벡터 머신에 대해서 살펴보았다.
지금부터는 서포트 벡터 머신을 비선형 분류기로 변환하는 방법에 대해 알아보겠다.
소프트 마진 분류(soft margin classification)
결정영역이 선형일때 훈련 데이터에 노이즈가 존재해서 데이터가 선형으로 분리되지 않을 경우,
예를들어 빨간색 클래스 영역에 파란색 데이터가 존재하고, 파란색 클래스에 빨간색 데이터가 존재하는 경우를 생각해보자.
소프트 마진 분류기는 슬랙변수 $\xi_{i}$ 라는 비용을 들여서 잘못 분류된 데이터를 올바른 클래스 영역으로 옮겨준다.
잘못 분류된 데이터 포인트를 본래 속하는 클래스로 비용을 들여 이동시켜준다.
이전 서포트 벡터머신에서 모든 데이터에 대한 기능적 마진은 $y_{i}(w^{T}x_{i}+b) \geq 1, min||w||$ 이어야 하지만
소프트 마진 분류기에서는 $\xi_{i}$ 라는 보정값 슬랙 변수를 통해, 일부데이터에 한해서 조건을 어기는 것도 허용해준다. 즉, 기능적 margin이 1보다 작은 경우도 허용해 준다는 의미이다.
$y_{i}(w^{T}x_{i}+b) \geq 1-\xi_{i}, min||w||+C||\xi||$
잘못 분류되어 있는 데이터는 기능적 마진이 음수의 값도 될 수 있다. w의 크기값을 최소화 시키면서 슬랙변수도 최소화시킨다.
모델의 학습방법은 여전히 결정 영역을 각 클래스로부터 가장 멀리 위치하는 것(large margin)이다.

@ 소프트 마진 분류의 파라미터 계산 방법.
예전 문제 형식은 다음과 같았다.
모든 테이터 집합 $\{(x_{i}, y_{i})\}$ 에 대하여 $y_{i}(w^{T}x_{i}+b) \geq 1$ 을 만족하면서,
$\Phi(w) = \frac{1}{2}w^{T}w$ 를 최소화 시키는
w, b 를 찾아라.
소프트 마진 분류에서 파라미터를 찾는 형식에서는 슬랙 변수를 포함하고 있다.
모든 테이터 집합 $\{(x_{i}, y_{i})\}$ 에 대하여 $y_{i}(w^{T}x_{i}+b) \geq 1-\xi_{i}$ (최적화 조건에서 모든 데이터에 대한 기능적 마진이 1이 아니라 잘못분류된 데이터의 경우 기능적 마진이 $\xi_{i}$ 만큼 줄어든 값을 가지는 것을 허용한다.) 와 ${\forall}i$에 대하여 $\xi_{i} \geq 0$ 을 만족하면서,
$\Phi(w) = \frac{1}{2}w^{T}w + C{\sum}\xi_{i}$ 를 최소화 시키는
w, b 를 찾아라.

@ 결정영역이 선형이 아니라 비선형인 경우 소프트 벡터 머신이 어떻게 문제를 해결 할 수 있을까?
원을 기준으로 안쪽은 빨간색 클래스, 바깥쪽은 파란색 클래스.
우리가 살고 있는 세계에서 대부분의 문제는 비선형 문제이다.

@ 서포트 벡터 머신이 생성하는 경계선은 사실 비선형일수없고 항상 직선 초평면이다.
그럼 어떻게?
비선형으로 분포하는 데이터 포인트 들을 선형으로 분류하기 위해 차원을 더 생성하면 된다.
$(x_{1},x_{2}) \rightarrow (x_{1}^{2},x_{2}^{2},\sqrt{2}x_{1}x_{2})$
예를들어, 이전의 예시와 같이 원모양의 클래스 결정영역이 있다고 가정하자. 이경계를 직선으로 나타 낼 수 있는 방법은 없다. 하지만 세번째 좌표를 도입하면, 즉, 데이터가 $x_{1},x_{2},x_{3}$ 에 대해서 거주하고 있다고 설정하면, 3차원 공간에서 데이터는 선형으로 분류할 수 있다. 이때 2차원 결정영역을 3차원 공간에 대한 초평면이라고 한다. 이때 3차원 공간에 옮겨져 있는 데이터들 $\Phi(x)$ 를 feature map 이라고 부른다.
$\Phi$ 에 대하여 $x \rightarrow \Phi(x)$ 따라서,
$f(x) = w^{T}\Phi(x) + b$ 를 학습하는 것이다.

@ 파라미터를 최적화 기법을 사용하여 결정할때도
원본데이터 x대신 피쳐맵 $\Phi(x)$ 를 사용하여 다음 식을 계산해주면 된다.
maximize $\sum\limits_{i}a_{i} - \frac{1}{2}{\sum\limits_{i,j}}y_{i}y_{j}a_{i}a_{j}\{\phi(x_{i}){\cdot}\phi(x_{j})\}$
피쳐맵사이의 내적 $\phi(x_{i}){\cdot}\phi(x_{j})$ 을 커널이라고 한다.
커널은 피쳐맵 $\phi(x_{i}), \phi(x_{j})$ 들 사이가 얼마나 유사한지를 판단하는 유사성 판단함수이다. 커널 $K(x_{i}, x_{j}) = \phi(x_{i}){\cdot}\phi(x_{j})$ 이며 이 경우, $\phi(x_{i})^{T}{\cdot}\phi(x_{j}) = (x_{i}^{T}{\cdot}x_{j})^{2}$
우리가 접한 원형 결정영역 결정 문제에서 유사성판단함수(커널)은 원본데이터 사이의 내적에 제곱으로 볼 수도 있다.

@ 서포트 벡터 머신은 많은 실험적인 문제들을 잘 해결 할 수 있었다.
분류기로써 서포트 벡터 머신의 성능.
서포트 벡터 머신은 실세계 데이터에 좋은 성능을 보여주었다.
특히 문서 분류 분야에서는 매우 유명한 성공을 거두기도 했다.
프로그래머는 SVM을 사용하기 위해서,
1. 커널 함수를 설계하기만 하면,
1. 나머지 파라미터는 자동으로 계산된다.
데이터 집합의 크기가 클수록 시간 소모가 크다는 단점도 있다. 왜냐하면,
1. 초평면(결정영역)의 최대 마진을 구하기 위해서 훈련 데이터 갯수의 제곱에 해당하는 계산량이 필요하다.
1. 모든 서포트 벡터를 저장해야 한다.

@ 만약 문제에 어떠한 알고리즘을 사용할 지 모르겠다면 서포트 벡터 머신은 좋은 출발선이 될 수 있다.