[코세라 강의 정리] 앤드류 응의 머신러닝 - Support Vector Machines

Support Vector Machine(SVM)은 매우 강력하고 널리 사용되는 알고리즘인데, Logistic regression과 NN와 비교했을 때 복잡한 비선형 함수에 대해서 더욱 명확하고 강력한 방법이 될 수 있다.

 

1. Optimization Objective

---

이전에 배웠던 Logistic Regression을 다시 살펴보자.

 

우리는

• \(y=1\) 일 때 \(\theta^{T}x>>0\)을
• \(y=0\) 일 때 \(\theta^{T}x<<0\)을 만족하는 \(\theta\)를 찾는 것이 목적이다.

Cost function을 나타내면 다음과 같은데,

\(z\)에 대한 그래프를 그려보면 다음과 같다. (\(y=1\)일 때)

여기서, SVM을 만들기 위해서 \(z=1\)을 기점으로 그래프를 다음과 같이 약간 수정해준다.

\(z <1\) 이면 1에 가까워질수록 점점 감소하는 직선을 그려주고(기울기는 크게 중요하지 않다), \(z>1\) 이면 기울기가 0인 평평한 직선을 그려준다.

 

\(y=0\) 일 때는 반대로 다음과 같이 수정해준다.

이렇게 만들어진 cost를 각각 \(y=1\) 일 때 \(cost_{1}(z)\), \(y=0\) 일 때 \(cost_{0}(z)\)라고 부르기로 하자.

 

그러고 나서 Support vector machine의 cost function을 다시 만들어주는데, Logistic regression의 cost function에서 다음 사항들이 변경되었다.

• 최소 cost를 구하는데 영향이 없는 m제거
• 이전에 구한 \(cost_{1}(z)\)와 \(cost_{0}(z)\) 대입
• \(A+{\lambda} B\) 에서 \(CA+B\) 구조로 변경 (\(C = \frac {1}{{\lambda}}\))

그러면 최종적으로 다음과 같은 함수가 만들어진다.

Hypothesis function의 경우, SVM의 가설 함수는 logistic처럼 0~1의 확률 값이 아니라 0 또는 1의 값을 갖는다.

 

2. Large Margin Intuition

---

SVM의 경우 Large Margin Intuition이라고 불리는데 왜 이렇게 불리는지 알아보자.

 

SVM의 cost function은 다음과 같다.

Logistic Regression에서는 0이 기준이었지만, SVM에서는 \(z>1\) 이거나 \(z <-1\) 일 때 각각 \(cost_{1}(z)=0\) 이거나 \(cost_{0}(z)=0\) 이 되고 hypothesis 값을 결정하게 된다. 이 부분이 SVM의 extra safety factor 또는 safety margin factor라 불리는 것을 만든다.

 

[SVM Decision Boundary]

만약 C가 엄청 큰 값이라고 가정해보자.

그러면 CA+B 구조를 가진 cost function이 최소화되기 위해서 A부분이 0에 가까워져야 할 것이다.

여기서 A가 0이 되는 부분이 SVM의 decision boundary가 된다.

 

A가 0이 되기 위해서는 y 값에 따라 다음과 같이 나눌 수 있다.

A=0이기 때문에 최적화 문제는 다음과 같이 단순화된다.

 

Margin이라는 개념을 이해하기 위해서 예시를 하나 살펴보자.

위의 분류 문제를 풀기 위해서는 다양한 선(연두색, 보라색)으로 Decision boundary를 구분할 수 있다. 하지만 검은색 선이 가장 적절한 Decision Boundary일 것이다.

검은색 선은 양 옆으로 그려진 파란색 선(검은색 선과 가장 가까운 샘플)과 최소 거리를 가지는데 이것을 Margin이라고 부른다.

SVM은 가장 큰 Margin으로 분류 문제를 풀기 때문에 Large Margin Classifier라고 불리며 robust 한 모델이다.

 

C는 overfitting을 조절하는 정규항과 관련 있기 때문에 너무 큰 값을 가지면 아래와 같이 이상치에 민감하게 반응하여 보라색 선을 Decision boundary로 사용할 것이다. 

즉, C가 매우 크다면 \(\lambda\)가 매우 작다는 뜻이므로 과적합이 될 확률이 높다.

 

3. Mathematics Behind Large Margin Classification

---

잠시 벡터의 내적에 대해 복습을 하고 가자.

• \(\left \| u \right \|\)는 벡터 u의 길이(norm)를 뜻하며 \(\sqrt{u_1^2+u_2^2}\)으로 계산된다.
• \(p\)는 벡터 \(v\)를 벡터 \(u\)에 내적 한 길이로, 스칼라 값이다. (90도 이상에서 음수를 가질 수도 있다.)
• 벡터 \(u\)와 벡터 \(v\)의 내적인 \(u^Tv\)는 \(p\)와 \(\left \| u \right \|\)를 곱한 값으로, \(u_1v_1+u_2v_2\) 로도 표현된다.

[SVM Decision Boundary]

위에서 살펴본 최적화 식에 편의상 \(\theta_0=0\), 차원 \(n=2\) 로 두면 다음과 같이 나타낼 수 있다.

최적화 식을 벡터의 norm으로 나타낸 것이다.

 

다음으로 살펴볼 것은 \(\theta^Tx\)항인데, 이것을 \(u^Tv\)로 생각해보면 다음과 같이 표현할 수 있다.

$$ \theta^Tx^{(i)} = p^{(i)}\cdot \left \| \theta \right \| = \theta_1x_1^{(i)}+\theta_2x_2^{(i)}$$

즉, \(y=1\) 일 때, \(p^{(i)}\cdot \left \| \theta \right \|\) 항이 1보다 커야 한다.

 

이것이 SVM에서 어떻게 동작하는지 Train 예제를 통해 알아보자.

식을 다시 정리해보면 다음과 같다.

우선, 왼쪽 그래프를 보면 초록색 선을 Decision Boundary로 설정한 것을 볼 수 있는데 썩 좋은 분류는 아니다 (SVM은 이렇게 하지 않을 것이다.). \(\theta_0=0\) 로 가정했기 때문에 벡터\(\theta\)를 위와 같이 초록색 선의 90도인, 원점을 지나는 파란색 법선 벡터로 나타낼 수 있다.

 

중간 사진을 보면 여기에 샘플 \(x^{(1)}\)과 \(x^{(2)}\)를 넣고 파란색 선인 벡터\(\theta\)에 내적 해서 \(p^{(1)}\), \(p^{(2)}\)를 얻은 것을 볼 수 있다. 그런데 여기서 얻은 \(p\) 값들이 너무 작아 보인다. 

 

따라서 위의 식을 만족하기 위해선 \(\left \| \theta \right \|\)의 값이 커질 수밖에 없고, 이것은 최솟값을 구해야 하는 우리의 목적과 맞지 않게 된다.

 

만약, 다음과 같이 Decision Boundary를 설정한다면 \(p\) 값이 크기 때문에 \(\left \| \theta \right \|\)는 작아지고 최종적으로 Cost function이 최소가 된다. 그리고 큰 margin을 갖게 된다.

 

이렇게 SVM을 이용하면 큰 Margin을 가지는 Decision boundary를 찾을 수 있다.

 

이번 강의에서는 서포트 벡터 머신(SVM)에 대해서 알아봤다.

다음 강의에서는 SVM의 Kernel에 대해 알아볼 것이다.

 

 

 

 

 

 

* 공부 정리 목적으로 쓴 글입니다. 오타나 수정사항이 있으면 바로 알려주세요.