[핸즈온 머신러닝] 6장. 서포트 벡터 머신

6.  Support Vector Machine

목차

1. 분류 문제 최적화

2. 라지 마진이란?

3. 라지 마진 분류의 수학적 개념

4. 커널1

5. 커널2

6. 실전 SVM

 

1. 분류 문제 최적화

---

다른 관점에서 보는 로지스틱 회귀

• 

  • $y=1 \to h_\theta(x) = 1$, 즉 $\theta^T x >> 0$ 이길 원함
  • $y=0 \to h_\theta(x) = 0$, 즉 $\theta^T x << 0$ 이길 원함
• 데이터 하나에 대한 비용
  • $-(ylogh_\theta(x)+(1-y)log(1-h_\theta(x)))$
  • $=-y log \frac{1}{1+e^{-\theta^T x}} - (1-y)log(1-\frac{1}{1+e^{-\theta^T x}})$

  • 

Support Vector Machine

• 로지스틱 회귀 vs. SVM

  • 

• SVM Hypothesis
  • $
    h_\theta(x) =
        \begin{cases}
          1 & \text{if $\theta^T x >= 0$} \\
          0 & \text{otherwise}
        \end{cases}    
    $
  • 로지스틱 회귀에는 확률개념을 사용하지만, SVM에는 사용하지 않음
    • 로지스틱 회귀 : $H_\theta(x) = P(y=1 | x_j \theta)$
    • SVM의 경우 svm.predict(x)는 있으나 svm.decisionfunction(x) 즉, 확률을 구하는 함수는 없다

 

2. 라지 마진이란?

---

(리뷰)  Support Vector Machine, SVM

 

SVM 결정 경계: 선형적으로 분리 가능한 경우

• SVM은 마진(margin)을 가장 넓게 하려고 하는 것 -> 라지마진(large margin)

• 

  
  
  • 그림에서 첫번째 DB(Decision Boundary)보다 두번째 DB가 margin이 더 넓으므로 SVM은 두 번째 DB를 선택

 

이상치(outlier)가 존재할 때 라지 마진 분류기

• [파란선] C가 매우 큰 경우
  • $C = \frac{1}{\lambda}$이므로, 규제가 적어 DB가 좀 더 모델에 fit, 즉 과대적합(overfitting) 되는 경우
• [초록선] C가 작은 경우
  • $C = \frac{1}{\lambda}$이므로, 규제가 커 DB가 좀 더 모델에 덜 fit되는 경우. 즉 이상치는 적당히 무시 가능

 

 

 

3. 라지 마진 분류의 수학적 개념

---

(리뷰)  벡터 내적(vector inner product)

 

SVM 결정 경계

 

$min_\theta\frac{1}{2m} \sum_{j=1}^{n} \theta_j^2$

• if n = 2
  • $= \frac{1}{2} (\theta_1^2+\theta_2^2)= \frac{1}{2}(\sqrt{\theta_1^2+\theta_2^2})^2  = \frac{1}{2} ||\theta||^2$
  • $y^i = 1 \to \theta^T x^i >= 1$
  • $y^i = 0 \to \theta^T x^i <= -1$

  • 

  • 여기서 $\theta^T x^i  = p^i \cdot ||\theta|| $
• if n = 1
  • $= \frac{1}{2} ||\theta||^2$
  • $y^i = 1 \to p^i \cdot ||\theta|| >= 1$
  • $y^i = 0 \to p^i \cdot ||\theta|| <= -1$
  • $p^i : x^i$를 벡터 $\theta$에 프로젝션한 것(단순화를 위해 $\theta_0 = 0$으로 가정)

  • 

  • 

 

 

 

4. 커널1

---

비선형 결정 경계(Non-linear decision boundary)

• $\theta_0 + \theta_1x_1 + \theta_2x_2 + \theta_3x_1x_2 + \theta_4x_1^2 + \theta_5x_2^2$
  • y =1 로 예측
  • $
    h_\theta(x) =
        \begin{cases}
          1 & \text{if $\theta_0 + \theta_1x_1 + \dots x >= 0$}\\
          0 & \text{otherwise}
        \end{cases}    
    $
  • $\theta_0 + \theta_1f_1 + \theta_2f_2 + \theta_3f_3 + \dots $
• 더 좋은 다른 특성들이 있을까? $f_1, f_2, f_3, \dots$
  • Yes! Kernel~

 

커널(Kernel)

• 데이터 x가 주어졌을 때, 랜드마크 $l^1, l^2, l^3$와 가까운 정도로 새로운 특성을 계산할 수 있음
• 가까운 정도 즉, 유사도(Similarity)를 구하자

• 

 

커널과 유사도(Kernel & Simirality)

($l^{(i)} \to f_i$ : landmark와 x로 계산한 값이 f)

$$f_1 = similarity(x, l^{(1)}) = exp( - \frac{|| x - l^{(1)} ||^2}{2 \sigma^2} )$$

• x가 $l^{(1)}$과 거의 근접하다면,
  • $x = l^{(1)}$
  • $x - l^{(1)} = 0$, 즉 $f_1 = exp( - \frac{0}{2 \sigma^2}) = e^0 = 1 $
• x가 $l^{(1)}$ 멀다면,
  • $x - l^{(1)} = \infty$
  • $f_1 = exp( - \frac{\infty^2}{2 \sigma^2}) = e^{-\infty} = 0$

 

Simirality(Kernel)로 Gaussian을 사용한 예시

 

• $\sigma$ 가 작아질수록 분포가 좁고 경사가 급격한 그래프가 나옴

  • 

 

$h_\theta(x) = \theta_0 + \theta_1f_1 + \theta_2f_2 + \theta_3f_3 >= 0$ 경우 1을 예측함

• 이때 $f_i = x_i l^{(i)} $ 임
• $\theta_0 = -0.5, \theta_1 = 1, \theta_2 = 1, \theta_3 =0$ 라고 가정하자
•  

  

• case1 : 임의의 데이터 x가 $l^{(1)}$에 가까운 경우
  • $f_1 = 1, f_2 = f_3 = 0$
  • $h_\theta(x) = -0.5 + 1*1 + 1*0 + 0*0 = 0.5 >= 0$이므로 1로 예측
• case2 : 임의의 데이터 x가 모든 랜드마크와 먼 경우
  • $f_1 = f_2 = f_3 = 0$
  • $h_\theta(x) = -0.5 + 1*0 + 1*0 + 0*0 = -0.5 <= 0$이므로 0으로 예측

• 즉 landmark와 가까울 수록 $h_\theta(x)$ 값이 커져 1로 예측을, 작아질수록 0으로 예측하게 된다

 

 

5. 커널2

---

랜드마크 선택하기

•  

  

• $ l^{(1)},  l^{(2)},  l^{(3)} $을 어떻게 구할까?
• 방법1: 데이터 자체를 landmark로 선택하는 방법
  • 이 경우 데이터의 개수가 m개 이면, landmark역시 1~m개가 존재 

  • 

 

커널을 사용한 SVM

• $(x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \dots, (x^{(m)}, y^{(m)})$가 주어졌을 때,
  • $l^{(1)} = x^{(1)}, l^{(2)} = x^{(2)}, \dots, l^{(m)} = x^{(m)}$로 정함
• 데이터 샘플 x가 주어졌을 때,
  • $f_1 = similarity(x,l^{(1)} )$
  • $f_2 = similarity(x,l^{(2)} )$
  • $\dots$
  • $f_m = similarity(x,l^{(m)} )$
• 즉 vector f는 $f =  \begin{bmatrix} f_0 \\ f_1 \\ \dots \\ f_m  \end{bmatrix}$임 
• 학습 예제 $(x^{(i)}, y^{(i)})$에 대해,
  • $f_1^{(i)} = similarity(x^{(i)},l^{(1)} )$
  • $f_2^{(i)} = similarity(x^{(i)},l^{(2)} )$
  • $\dots$
  • $f_i^{(i)} = similarity(x^{(i)},l^{(i)} )=1$, $x^{(i)} = l^{(i)}이므로$
  • $\dots$
  • $f_m^{(i)} = similarity(x^{(i)},l^{(1)} )$
• 즉, $x^{(i)} \in R^{m+1}, f^{(i)}  = \begin{bmatrix} f_1^{(i)} \\ f_2^{(i)} \\ \dots \\ f_m^{(i)}  \end{bmatrix}$
  • $f_i^{(i)}$의 의미는 첫번째 랜드마크와의 유사도를 측정한 값
  • 주의! $f_0^{(i)}=1$ : bias term 는 빼고 계산
• 가설(hypothesis)
  • x가 주어지면, 특성 $f \in R^{m+1}$을 계산하고 $\theta^Tf >= 0 \to y =1$로 예측
• 학습
  • $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_{j=1}^{m} \theta_j^2$
  • 원래 $\theta^T x$에 x자리에는 새로 배운 커널 함수 f가 들어가게 됨

 

SVM의 파라미터

• $C(=\frac{1}{\lambda})$
  • C가 크면, bias 는 작고, variance는 크다. 즉, 규제($lambda$)가 크므로 H가 예민, 과대적합(overfitting) 위험이 있음
  • C가 작으면, bias 는 크고, variance는 작다. 즉, 규제($lambda$)가 작으므로 H가 둔감, 과소적합(underfitting) 위험이 있음
• $\sigma$
  • $\sigma$가 크면: 특성 $f_i$는 더 완만하게 변화함
    • 즉 bias는 높으며 variance 는 작다(둔감)
    •  

      

  • $\sigma$가 작으면: 특성 $f_i$는 더 급격하게 변화함
    • 즉 bias는 작으며 variance 는 높다(예민)

    • 

 

6. 실전 SVM

---

파라미터 $\theta$를 구하기 위해 SVM 소프트웨어 패키지 사용 가능

 

우리가 정할 것

• 파라미터 C
• 커널 종류(유사도 함수, similarity fuction)
  • no kernel(linear kernel)
    • $\theta^T x >= 0 \to y=1$ 로 예측
    • n이 상대적으로 크고, m이 작을 때 사용
  • Gaussian Kernel
    • $f_i = exp( - \frac{|| x - l^{(i)} ||^2}{2 \sigma^2} )$, 여기서 $l^{(i)} = x^{(i)}$임
    • n이 상대적으로 작고, m이 클 때 사용
    • $\sigma$를 정해야 함

커널 유사도(Kernel Similarity) 함수

• def kernel(x1, x2): 
  • $f = exp( - \frac{|| x1 -x2 ||^2}{2 \sigma^2} )$
  • return f
• 주의: 가우시안 커널 사용 전에 특성 정규화(feature scaling)을 수행할 것
  • feature scaling = normalization
  • $||x-l||^2 = (x_1 - l_1)^2 + (x_2 - l_2)^2 + \dots + (x_n - l_n)^2 $

 

다른 커널 사용하기

• 조언
  • 모든 유사도 함수 $similarity(x,l)$이 유효한 커널 역할을 하는 것이 아님
  • 커널 함수가 머서의 정리(Mercer's Theorem)라는 조건을 만족해야 SVM 패키지의 최적화가 발산하지 않고 제대로 작동함
• 자주 사용되는 커널
  • 다항 커널(polynomial kernel)
  • 기타 커널
    • String kernel, chi-square kernel, histogram kernel, histogram intersection kernel, ...

 

멀티 클래스 분류(Multi-class classification)

• 대부분의 SVM 패키지들은 이미 멀티 클래스 분류 기능을 내장함
• 해당 기능이 없을 경우 일대다(one-vs-all) 방법을 사용하야 $\theta^{(1)}, \theta^{(2)}, \dots, \theta^{(k)}$ 계산
  • K개 SVM을 학습시키고, i=1,2, ..., k에 대해 y=i 여부를 체크
  • $(\theta^{(i)})^Tx$값이 가장 큰 클래스 i를 선택

 

로지스틱 회귀 vs. SVM vs. Neural Network(NN)

n: 특성 개수( $x \in R^{n+1}$), m: 학습 예제 개수

• n이 클 때(m에 비해 상대적으로)
  • 로지스틱 회귀 또는 커널이 없는 SVM(linear Kernel)
  • n > 10,000 and 10 < m < 1,000
• n이 작고 m이 적당할 때
  • 가우시안 커널을 사용한 SVM
  • 1 < n < 1,000 and 10 < m < 1,000
• n이 작고, m이 클 때
  • 더 많은 특성 추가 후, 로지스틱 회귀 또는 커널 없는 SVM
  • 1 < n < 1,000 and m > 50,000

추가로, 대부분의 경우 인공신경망(NN)은 잘 작동되지만, 학습이 느리다는 단점을 가지고 있다