[데이터 분석과 통계] 9. Support Vector Machine

support vector machine

• 임의 dataset의 decision boundary 설정 시, boundary와 가장 가까운 data point와의 간격(margin)을 최대로 하는 선을 정의
• $\theta^T\vec{x}=w^T\vec{x}+b$
  • $\theta_0=b$로 해석
  • $w^T\vec{x}=\theta_1x_1+...+\theta_nx_n$
  • y = -1 or 1로 나타남(binary classification)
• 벡터 $\vec{p}=x_n-x$에 대해
  • $\frac{\vec{w}^T}{||w||}\vec{p}=\frac{1}{||w||}[\vec{w}^Tx_n+b-(wx^T+b)]=\frac{1}{||w||}$
  • $|\vec{w}^Tx_n+b|=1$인 조건 하에 $\frac{1}{||w||}$를 최대화
    • $|\vec{w}^Tx_n+b|=y_n(\vec{w}^Tx_n+b)$, $\vec{w}^Tx_n+b$의 부호에 의해 +1 혹은 -1로 값이 결정됨
    • 벡터 $\vec{w}$에 대해 $||\vec{w}||^2=w^Tw$
    • $\frac{1}{||w||}$의 최대화 = $||w||$의 최소화, 즉 미분값을 최소화하게 되므로 $||w||=\frac{1}{2}w^Tw$

---

Lagrange multiplier

• $f(x, y) = ax + by = k$, $g(x, y) = x^2+y^2 = r^2$인 함수 f, g를 가정
  • f와 g가 접하게 되면 gradient가 동일 : $\nabla f = \lambda\nabla g$
  • $\lambda$ : lagrange multiplier
  • $L(x,y,\lambda) = f(x,y) - \lambda(g(x,y) + c)$
• $\nabla L=\frac{\partial L}{\partial x} = \frac{\partial f}{\partial x} - \lambda\frac{\partial g}{\partial x} = 0$
  • $\frac{\partial f}{\partial x}=\lambda\frac{\partial g}{\partial x}$
• SVM 계산에 있어 $f=\frac{1}{2}w^Tw$, $g=y_n(x^Tx_n+b)-1\geq0$
  • $L(w,b,\lambda) = \frac{1}{2}w^Tw+\sum\lambda_i[-y_i(w^Tx_i+b)-1]$
  • $\frac{\nabla L}{\partial w}=0=w-\sum\lambda_iy_ix_i\\\rArr w=\sum\lambda_iy_ix_i$로 SVM weight w 계산
  • $\frac{\nabla L}{\partial b}=0=\sum\lambda_iy_i$
• $L(w,b,\lambda) = \frac{1}{2}w^Tw+\sum\lambda_i[-y_i(w^Tx_i+b)-1]$에서
  • $w=\sum\lambda_iy_ix_i$
  • $\sum\lambda_iy_i=0$
  • $L(w,b,\lambda)=\sum\lambda_i+\frac{1}{2}w^Tw-\sum\lambda_iy_iw^Tx_i\\=\sum\lambda_i-\frac{1}{2}w^Tw$

---

How to solve SVM

• SVM : $y(w^Tx_i+b)\geq1$일 때 $\frac{1}{2}w^Tw$의 최소값을 계산하는 것
• Lagre multiplier : $L(w, b, \lambda) = \frac{1}{2}w^Tw-\sum\lambda[y_i(w_i^Tx_i+b)-1]$
  • $sup_\lambda L(x, \lambda)$ : $\lambda$에 대해 가질 수 있는 L의 최댓값을 찾는 것
• SVM의 해 $p^*=inf_\lambda sup_\lambda L(x, \lambda)$ : L이 가질 수 있는 최댓값 중 하한선
  • $sup_\lambda L(x, \lambda)$는 $\sum$식이 음수일 땐 $\frac{1}{2}w^Tw$지만, 양수일 땐 무한으로 발산
  • sup값이 가질 수 있는 하한선은 즉 $\frac{1}{2}w^Tw$이 됨
• Lagrange dual function : $g(\lambda)=inf_{w,b}L(w,b,\lambda)$인 함수 g를 정의
  • $\lambda \geq0$일 때 $g(\lambda)\leq p^*$ : $g=inf\ L\leq L(x, \lambda)$이기 때문
  • $p^*$를 구하기 어렵다면 $g(\lambda)$를 구한 후 $p^*=sup_\lambda g(\lambda)$를 계산하는 방법도 있음
• $g(\lambda)=inf_{w,b}L(w,b,\lambda)$
  • $\frac{\partial L}{\partial w}=w-\sum\lambda_i y_ix_i=0$
  • $\frac{\partial L}{\partial b}=\sum\lambda_iy_i=0$
  • 즉 $g(\lambda)=-\frac{1}{2}w^Tw+\sum\lambda_i$