D052
SVM
SVM 은 하나의 hyperplane 을 선택해서 점들을 두개의 클래스로 나누고 그 margin 을 최대화 합니다.
(margin : hyperplane 과 training set에서 가장 가까운 점들 사이의 거리 )
즉, SVM 는 hyperplane 과 훈련 셋의 점 사이의 거리, $\gamma$ 를 최대화 하는
hyperplane wx+b = 0 을 선택하는 것입니다.
다음과 같이 두 클래스의 점들과 그것들을 나누는 hyperplane 을 볼 수 있습니다.
점이 hyperplane으로 부터 더 멀수록 분류가 더 잘 되었다고 간주할 수 있습니다.
그래서 hyperplane과 가능한 멀리 있도록, margin 을 크게 만드는 것이 바람직합니다.
이렇게 트레이닝 셋의 margin 을 크게 만들면, 실제 데이터에서 분류가 잘 될 확률이 올라갑니다.
위 그림처럼 hyperplane 에서 $\gamma$ 거리에 두개의 hyperplane(parallel)들이 있습니다.
이 hyperplane 들은 하나 이상의 support vector 와 닿습니다.
이 support vector 들은 hyperplane 으로부터 $\gamma $ 거리에 있는 점으로
parallel hyperplane 을 제한하는 점입니다.
일반적으로 d 차원의 집합은 d+1 개의 support vector 들을 갖지만 parallel hyperplane 위에 서포트 벡터가 더 많이 있을 수 있습니다.
현재 SVM 의 목표에 대해 다음과 같이 정리할 수 있습니다.
- 트레이닝 셋 $(x_1,y_1),(x_2,y_2), \dots, (x_n,y_m)$ 이 주어졌을 때
$y_i(w x_i +b) \geq \gamma$ 이 성립하는 $\gamma$ 를 최대화한다.
여기서 y는 +1 이나 -1 이고(이진 분류),
이는 x가 hyperplane 의 어느쪽에 있어야 하는지 정합니다.
위의 식을 그대로 사용하는 경우, 답을 한정 할 수 없습니다.
w 와 b 의 값이 커짐에 따라 $\gamma $ 의 값을 크게 설정할 수 있게됩니다.
예를 들어 w,b 가 위의 조건을 만족할 때
$y_i(2wx_i+2b)\geq 2\gamma $ 도 성립하게되고,
이런식으로 하면 최대 $\gamma$ 값을 선택할 수 없게 됩니다.
Normalizing the Hyperplane
위 상황에서 $\gamma$ 를 선택하기 위해서는
weight 벡터 w 로 정규화(normalize) 해야합니다.
이는 hyperplane 에 수직인 유닛 벡터 w/||w|| 입니다. (Frobenius norm)
정규화를 하여 parallel hyperplane 들을
$wx+b =1,\ wx+b = -1$ 로 바꿀 수 있습니다.
이렇게 1,-1로 만든 식을 upper, lower hyperplane 이라고 부릅니다.
위 그림에서 $\gamma$ 가 1 인 것 처럼 보이지만.
실수가 아니라 ‘unit’ 의 수 입니다.
즉, hyperplane 와 parallel hyperplane 사이를 이동하는 데 필요한 스텝의 수 입니다.
그러므로 SVM의 목표를, 유닛 벡터 $w/||w||$ 의 곱인 $\gamma$ 를 최대화 하는 것으로 둘 수 있습니다.
| 사실, $\gamma$ 를 최대화 하는 작업은 | w | 를 최소화 하는 것입니다. |
위 그림의 서포트 벡터 $x_2$ 를 봅시다.
$x_1$은 upper hyperplane 에 대해 $x_2$ 의 projection 이라고 봅시다.
| $\frac{w}{ | w | }$ 단위로 $x_2$ 에서 $x_1$ 까지의 거리는 2$\gamma$, | ||
| $(x_1-x_2) = 2\gamma \frac{w}{ | w | }$ 입니다. |
그러므로
\(x_1 = x_2 + 2\gamma \frac{w}{||w||}\) 이 성립합니다.
$x_1$ 은 upper hyperplane $wx+b = 1$ 상에 있으므로
$wx_1 + b = 1$ 이 성립합니다.
위 식에 앞선 $x_1$ 을 대입하면
| $$w(x_2 + 2\gamma \frac{w}{ | w | }) + b = 1 $$ 을 얻고, |
다시 정리하면
| $$wx_2 + b + 2\gamma \frac{ww}{ | w | }=1$$, |
여기서 $wx_2+b$ 는 -1 이므로
| $$\gamma \frac{ww}{ | w | } = 1$$ 입니다. |
ww 은 w 의 제곱합 이므로 $ww =||w||^2$ 입니다.
이를 가지고 다음과 같은 결론을 낼 수 있습니다.
그러므로 목표는 $\gamma$ 를 최대화 하는 대신,
$||w||$ 을 최소화 하는 최적화 문제로 바꿀 수 있습니다.
- 트레이닝 셋 $(x_1,y_1),(x_2,y_2), \dots, (x_n,y_m)$ 이 주어졌을 때,
$y_i(w x_i +b) \geq 1$ 따라 $||w||$를 최소화한다.
Finding Optimal Approximate Separators
일반적인 경우에 최적의 hyperplane을 찾는 것을 고려해봅니다.
이상적인 데이터가 주어지지 않는다면 어떤 hyperplane을 선택하는 것과 상관없이
몇개의 점들은 제대로 분류가 되지 않을 것입니다.
또한 몇개의 점은 분류는 맞지만 분리 hyperplane에 너무 가까이 있을 수 있어서
margin 조건을 만족하지 않을 수 있습니다.
위 그림의 경우 2개의 오분류가 있고, 2개의 점은 margin 안에 있는 것을 볼 수 있습니다.
이렇게 margin 안의 점들을 bad point 라고 합니다.
hyperplane 을 평가할 때 각 bad point 들은 패널티를 주어야합니다.
여기서 패널티의 양은 그림과 같이,
hyperplane 에서 bad pont 들이 있는 곳까지의 화살표로 볼 수 있습니다.
이 화살표들은 각각 parallel hyperplane,
wx+b=1 이나 wx+b=-1 로부터의 거리를 측정합니다.
이전까지는 $y_i(w x_i +b) \geq 1$ 를 따르는 w 의 길이를 최소화하는 것만 고려하였지만
위와 같은 상황에서 패널티를 어떻게 반영할까에 대해 생각해봐야합니다.
w 의 길이의 최소화와 bad point 는 trade-off 관계를 갖습니다.
margin 이 커지면 커질수록 bad point 에 해당하는 점들이 늘어날 것이고,
margin 이 작이질수록 bad point 가 줄어들 것입니다.
이 trade-off 관계는 regularization parameter C 를 사용하여 조절합니다.
| w | 이 가능한 작고, bad point 의 패널티가 가능한 적게 나오도록 식을 세워야합니다. | ||
| w | 에 관한 텀과 bad point 에 관한 텀, 2개의 텀을 사용해서 최적화의 식을 세울 수 있습니다. |
우선 첫번째 텀을 만들어 봅시다.
최소화 식에서 ||w|| 를 그대로 사용하기 어렵습니다.
대신, 최적화에 적합하게 $||w||^2/2$ 를 사용합니다.
다른 형태로도 할 수 있지만, $||w||^2/2$ 이 이후 계산하는데 편리하여 이를 사용합니다.
이제 두번째 텀, 패널티에 관한 식을 세웁니다.
bad point 가 발생하면, 그에 따라서 숫자를 더해주면 됩니다.
현재 식을 최소화하는 것이 목표이기 때문에,
패널티를 받았을 때 그 패널티 정도에 비례하는 양수 값을 출력하여
이 패널티에 대한 정보를 반영할 수 있습니다.
만약 bad point 가 없는 경우,
그대로 두어(0을 더해) 기존 w 에 관한 식만 최소화 하도록 만듭니다.
위 두가지 텀은 다음과 같습니다.
첫번째 텀은 ||w|| 가 작게 만들려 하고,
두번째 텀은 bad point 들에 대한 패널티를 나타냅니다.
여기에 상수 C (regularization parameter) 를 곱해줍니다.
이 C 는 오분류가 얼마나 중요한지를 나타냅니다.
만약 오분류 나오는 것을 원치 않는다면, C 의 값을 크게 선택하면되지만, 대신 margin 이 줄어듭니다.
잘못분류되는 것이 어느 정도 허용된다면, C 를 작게 선택하고 margin 을 크게 설정할 수 있습니다.
위 식에서 두번째 텀을 봅시다.
여기서 L 은 hinge function 입니다. 이는 아래 그림과 같고,
이 함수의 값을 hinge loss 라고 합니다.
z를 위와 같이 두었을 때, $z_i$ 가 1 이상이면 L의 값은 0 이 됩니다.
$z_i$ 값이 더 작으면 L 의 값은 z가 감소함에 따라 증가합니다.
이후 최적화에 사용하기 위해서는 $L(x_i,y_i) $ 의 각 $w_j$ 에 관한 미분을 해야합니다..
hinge function의 미분은 비연속이고,
$z_i$가 1보다 작으면 $-y_ix_{ij}$ 이고,
$z_i$가 1보다 크면 0 이됩니다.
그래서 $y_i =+1 $ 일 때는
이렇게 되고, $y_i = -1$ 일 때는
두 경우를 합하면 다음과 같은 식이 나옵니다.
SVM Solutions by Gradient Descent
위의 식을 풀기 위해서 Gradient descent 를 사용합니다.
Gradient descent 을 구현하기 위해,
벡터 w 의 성분 $w_j$ 와 b 의 미분을 계산합니다.
f(w,b) 를 최소화 하기 위해,
b와 $w_j$를 Gradient 방향과 반대 방향으로 이동하도록 합니다.
그리고 여기서 이동하는 크기는 미분의 값, 경사도에 비례하도록 설정합니다.
b와 같은 경우, w의 (d+1) 번째 차원으로 보고 계산하여도 무방하기 때문에
편의상 w 의 차원을 하나 늘려서 넣고, 하나의 변수에 대해서만 계산을 하도록 합니다.
각 라운드에서 w를 이동시키는 Gradient의 비율을 정하기 위해
상수 η 을 선택하고, 다음과 같은 식을 세울 수 있습니다.
f 에 대한 미분식을 봅시다.
f의 첫번째 텀의 $w_i$ 에 대한 편미분 은 쉽게 할 수 있습니다.
이것이 앞서 $||w||$ 대신 $||w||^2/2$ 을 사용한 이유입니다.
두번째 텀 hinge function 부분은 if 표현을 사용해서 다음과 같이 나타냅니다.
Gradient descent 알고리즘을 수행하기 위해서 다음을 선택해야 합니다.
- 파라미터 C 와 $\eta$
- w 의 초기 값 ( b 포함 )
그러고 다음을 반복합니다.
- $w_j$ 에 대해 f(w,b) 의 편미분을 계산합니다.
- $w_j$ 에 $\eta \frac{\partial f}{\partial w_j}$ 를 빼서 w 값을 update 합니다.
이와 같은 방식으로 f 를 최소화 하는 $||w||$ 값,
즉, SVM 의 margin 을 최대로 만드는 $\gamma$ 를 구할 수 있습니다.
Stochastic Gradient Descent
위와 같은 Graedient descent 알고리즘은 일반적으로 batch graedient descent 라고합니다.
이는 모든 훈련 데이터를 하나의 batch로 보기 때문입니다.
이 방식은 작은 데이터셋에서 효과적인 반면에,
큰 데이터셋에서는 실행할 때,
모든 트레이닝 데이터에 대해 수행하고,
수렴할 때 까지 계속 반복해야하므로 많은 시간이 걸릴 수 있습니다.
Stochastic gradient descent 는 한번에 하나 정도의 트레이닝 데이터를 가지고,
w 의 현재 추정치를 조정합니다.
그 외의 트레이닝 데이터는 다른 라운드에서 조정합니다.
이 방식은 느리고, 잘못 수렴할 수 있기 때문에 사용되지 않는 것이 일반적입니다.
대신 Mini batch Gradient descent 를 사용,
전체 트레이닝 셋을 특정 크기 (예 : 1000 개 훈련 예)의 미니 배치 로 분할하여 수행합니다.
Comments