Search
Duplicate

Machine Learning/ SVM

주의) 이 페이지에서는 공식의 유도 과정 같은 것은 정리하지 않는다. 공식의 유도 과정은 <코세라 강의> 참조.

SVM(Support Vector Machine)

로지스틱 회귀를 변형하여 간격(Margin)을 최대화 하는 선을 찾는 분류 알고리즘. Large Margin Classification이라고도 한다.
로지스틱 회귀에서 hθ(x)h_{\theta}(x)가 1에 가까우면 yy는 1, 0에 가까우면 yy는 0으로 두었던 것에 반해 SVM에서는 hθ(x)h_{\theta}(x)가 1보다 큰 경우 yy는 1, -1보다 작으면 yy는 0인 것으로 본다.
hθ(x)h_{\theta}(x)가 1보다 커지거나 -1보다 작을 때까지 계속 돌린다는 것. 이렇게 해서 간격을 크게 한다.

SVM의 가설함수

로지스틱 회귀를 변형해서 사용하는데, λ\lambda의 위치를 조정하고, hθ(x)h_{\theta}(x)가 선형이 되도록 조절하는 식으로 하여 최종적으로 아래와 같은 식이 만들어진다.
minθCi=1m[yicost1(θTxi)+(1yi)cost0(θTxi)]+12i=1nθj2\min_\theta C \sum_{i=1}^{m} [y^i cost_1 (\theta^T x^i) + (1-y^i) cost_0 (\theta^T x^i) ] + \frac{1}{2} \sum_{i=1}^{n} \theta_j^2
CC1λ{1 \over \lambda} 을 의미한다. 따라서 CC가 커지면 overfitting 이 되고, CC가 작아지면 underfitting이 된다.
cost1cost_{1}z>1z > 1 일 때는 0이 되고, z<1z < 1일 때는 z 값이 작아짐에 따라 cost 값이 커지는 직선을 갖는 함수를 의미하며 (기존의 로지스틱의 곡선을 직선으로 바꾼 것) cost0cost_{0}는 그 반대의 함수를 의미한다.

SVM의 Decision Boundary

http://efavdb.com/svm-classification/
Decision Boundary는 각 데이터들 사이에 가장 큰 간격을 갖는 선을 긋는 것을 말하는데, 이 선은 각 엘리먼트들을 선에 투영(projection)하여 찾을 수 있다.
각 엘리먼트를 선에 투영 한 후 얻어지는 p값이 가장 큰 것을 찾으면 간격이 가장 큰 Decision Boundary를 그을 수 있다.

SVM의 Kernels

특정 Landmark를 정한 후, 그 Landmark와 각 엘리먼트들 사이의 가까운 정도(similarity)를 나타내는 함수를 ff라고 둔다.
Landmark는 전체 엘리먼트를 돌아가며 계산한 후 선택한다.
ff를 구하는 방법은 여러가지가 있는데, similarity를 구하는 공식을 커널(Kernel) 함수라고 한다. 이 강의에서는 가우시안 커널 (Gaussian Kernel) 을 사용한다.
xix_{i} 와 ljl_{j} 사이의 similarity는 다음과 같다.
exp(xilj22σ2)\exp(- \frac{|| x_i - l_j ||^2}{2 \sigma^2} )
xilj\|x_{i} - l_{j}\| 는 두 점 사이의 거리를 의미한다.
σ\sigma는 표준편차를 의미하며제곱이 사용되었기 때문에 분산이 된다.
수학적으로 커널함수는 원점을 중심으로 대칭이면서 적분값이 1인 non-negative 함수로 정의된다. Gaussian, Epanechnikov, uniform 함수 등이 대표적인 커널 함수들이다.
커널 값은 개념적으로 similarity의 최대가 1이고 최소가 0이기 때문에 시각화 하면 위 그래프와 같은 모습이 된다.
이때 σ의 값에 따라 경사의 완만함이 결정된다.

SVM의 Kernel 비용함수

Kernel을 이용하여 SVM의 비용함수를 구하면 다음과 같다.
minθCi=1m[yicost1(θTfi)+(1yi)cost0(θTfi)]+12i=1mθj2\min_\theta C \sum_{i=1}^{m} [y^i cost_1 (\theta^T f^i) + (1-y^i) cost_0 (\theta^T f^i) ] + \frac{1}{2} \sum_{i=1}^{m} \theta_j^2
SVM 외의 분류 문제에서는 Kernel을 도입할 경우 연산 속도가 너무 느려서 잘 사용하지 않는다고 한다.

SVM의 Parameter

SVM에서 bias와 variance는 C(=1λ)C(={1 \over \lambda})σ2\sigma^{2}에 의해 조절 된다.
C의 값이 크면 lower bias, high variance가 되며, 값이 작으면 high bias, low variance가 된다.
σ2\sigma^{2}는 경사도를 의미하며 이 값이 커지면 경사가 부드러워짐과 함께 high bias, low variance가 되고 이 값이 작으면 경사가 급격히 떨어짐과 함께 lower bias, high variance이 된다.