Support Vector Machine

※ SVM (Support Vector Machine)

• 중심선
• 경계선 : support vector
• 여백(margin) : 중심선과 경계선 사이

■ Projection (정사영)

• $\vec u를~ \vec v에~정사영$ : 수직으로 내리는 것
  \(\vec u를~ \vec v에~정사영한~벡터의~길이~: ||proj_{\vec v} \vec u|| = ||\vec u||cos \theta\)

□ Dot Product (내적)

\(\begin{align*} \vec u \cdot \vec v &= ||\vec u||*||\vec v||*cos \theta \\ &= u_{1}v_{1} + u_{2}v_{2} \end{align*}\)

□ Norm (벡터의 길이)

\[||\vec x|| = \sqrt(x_{1}^{2} + x_{2}^{2})\]

SVM

• 오차를 최소화하면서 동시에 마진을 최대화 하는 분류 모델로, 커널 트릭을 활용하여 저차원 공간을 고차원 공간으로 매핑함
• 마진의 개념을 회귀에 활용한 모델을 서포트 벡터 회귀(Support Vector Regression)이라 함
• 모델 구조
  • $w_{1}x_{1}^{(i)}+w_{2}x_{2}^{(i)}+…+w_{d}x_{d}^{(i)}+b$
  • $\bold w= (w_{1}, w_{2}, …w_{d})^{T}$ : 가중치 벡터 (계수)
  • b: 절편 (bias)
• 최적화 모델

  • 목적식: $

    \bold w

    + C \times \sum_{i=1}^{n} \psi_{i}$

  • 제약식: $y^{(i)}(\bold w \bold x^{(i)}+ b) \geq 1 - \psi_{i}$
• 주요 파라미터
  • kernel: 통상적으로 이진 변수가 많으면 linear 커널이, 연속 변수가 많으면 rbf 커널이 잘 맞는다고 알려져 있음
  • C: 오차 패널티에 대한 계수로, 이 값이 작을수록 마진 최대화에 클수록 학습 오차 최소화에 신경을 쓰며, 보통 $10^{n}$ 범위에서 튜닝함
  • $\gamma$: rbf 커널의 파라미터로, 크면 클수록 데이터의 모양을 잘 잡아내지만 오차가 커질 위험이 있으며, C가 증가하면 $\gamma$도 증가하게 튜닝하는 것이 일반적임
• 파라미터 튜닝이 까다로운 모델이지만, 튜닝만 잘 하면 좋은 성능을 보장하는 모델임

■ Decision Rule (결정 조건)

1. + 영역의 경계선을 1이라 하고, 이곳에 속하려면 $\vec w \cdot \vec x +b \ge 1$
2. - 영역의 경계선을 -1이라 하고, 이곳에 속하려면 $\vec w \cdot \vec x +b \le -1$

\[y_{i} = \begin{cases} 1, \quad \text{$x$가 +영역에 있을 때}\\ -1 \quad \text{$x$가 -영역에 있을 때} \end{cases}\]

□ 경계선 바깥쪽에 있는 데이터 표현

\(y_{i}(\vec w \cdot \vec x +b) -1 \ge 0\)

□ 경계선에 있는 데이터 표현

\(y_{i}(\vec w \cdot \vec x +b) -1 = 0\)

■ 서포트 벡터 간 너비 (width)

• 넓을수록 좋음 (확실하게 +와 -를 구분하니까)
  \((\vec x_{+} - \vec x_{-}) \cdot \cfrac{\vec w}{||\vec w||}\)

1. + 경계선
   • $\vec w \cdot \vec x_{+} = 1-b$
2. - 경계선
   • $-\vec w \cdot \vec x_{-} = 1-b$
3. 1, 2를 이용
   \(\begin{align*} (\vec x_{+} - \vec x_{-}) \cdot \cfrac{\vec w}{||\vec w||} &= \cfrac{\vec w \cdot \vec x_{+}-\vec w \cdot \vec x_{-}}{||\vec w||} \\ &= \cfrac{1-b+1+b}{||\vec w||} \\ &= \cfrac{2}{||\vec w||} \end{align*}\)

□ 너비 최대화

\(\begin{align*} \max(\cfrac{2}{||\vec w||}) &\Leftrightarrow \max(\cfrac{1}{||\vec w||}) \\ &\Leftrightarrow \min(||\vec w||) \\ &\Leftrightarrow \min(\cfrac{1}{2}||\vec w||^{2}) \end{align*}\)

\[\begin{align*} \min(\cfrac{1}{2}||\vec w||^{2}) &\Leftrightarrow \min(\cfrac{1}{2}\sqrt(w_{1}^{2}+w_{2}^{2})^{2}) \\ &\Leftrightarrow \min(\cfrac{1}{2}(w_{1}^{2}+w_{2}^{2})) \\ &\Leftrightarrow \min(\cfrac{1}{2}(w_{1}w_{1}+w_{2}w_{2})) \\ &\Leftrightarrow \min(\cfrac{1}{2}(\vec w \cdot \vec w)) \end{align*}\]

∴ 자기 자신과의 내적값의 최소화하는 것

■ Optimization (최적화)

• 목적함수(objectibe function) :
  $\min(\cfrac{1}{2}||\vec w||^{2})$
• 제약조건(constraint) :
  $y_{i}(\vec w \cdot \vec x +b) -1 = 0$

제약조건 하에서 목적함수를 최적화

□ Lagrangian(라그랑지안)

• 목적함수와 제약식을 한번에 표현한 것
  \(L = \cfrac{1}{2}||\vec w||^{2} - \sum_{i=1}^{n} \alpha_{i}[y_{i}(\vec w \cdot \vec x +b)-1]\)
• $\alpha$ : Lagrange multiplier (라그랑주 승수)

◎ 라그랑지안을 미분해서 0이 나오는 지점

\(\begin{align*} \cfrac{\partial L}{\partial \vec w} &= \vec w - \sum_{i=1}^{n} \alpha_{i}y_{i}\vec x_{i} = 0 \\ &\Leftrightarrow \vec w = \sum_{i=1}^{n} \alpha_{i}y_{i}\vec x_{i} \end{align*}\)

\[\begin{align*} \cfrac{\partial L}{\partial b} &= - \sum_{i=1}^{n} \alpha_{i}y_{i} = 0 \\ &\Leftrightarrow \sum_{i=1}^{n} \alpha_{i}y_{i} = 0 \end{align*}\]

□ Lagrange Dual Function (라그랑주 듀얼 함수)

• 라그랑지안의 최소값
• 듀얼함수 $\le$ 최적값
• $\max(듀얼함수) = 최적값$

\[\begin{align*} L &= \cfrac{1}{2}(\sum_{i=1}^{n} \alpha_{i}y_{i}\vec x_{i})(\sum_{i=1}^{n} \alpha_{i}y_{i}\vec x_{i}) - \sum_{i=1}^{n} \alpha_{i}[y_{i}\vec w \cdot \vec x +y_{i}b-1] \\ &= \cfrac{1}{2}(\sum_{i=1}^{n} \alpha_{i}y_{i}\vec x_{i})(\sum_{i=1}^{n} \alpha_{i}y_{i}\vec x_{i}) - \sum_{i=1}^{n} (\alpha_{i}y_{i}\vec w \cdot \vec x +\alpha_{i}y_{i}b-\alpha_{i}) \\ &= \cfrac{1}{2}(\sum_{i=1}^{n} \alpha_{i}y_{i}\vec x_{i})(\sum_{i=1}^{n} \alpha_{i}y_{i}\vec x_{i}) - \vec w \sum_{i=1}^{n} \alpha_{i}y_{i}\vec x +b \sum_{i=1}^{n} \alpha_{i}y_{i}+ \sum_{i=1}^{n}\alpha_{i} \\ &= \cfrac{1}{2}(\sum_{i=1}^{n} \alpha_{i}y_{i}\vec x_{i})(\sum_{i=1}^{n} \alpha_{i}y_{i}\vec x_{i}) - (\sum_{i=1}^{n} \alpha_{i}y_{i}\vec x_{i})(\sum_{i=1}^{n} \alpha_{i}y_{i}\vec x)+b \sum_{i=1}^{n} \alpha_{i}y_{i}+ \sum_{i=1}^{n}\alpha_{i} \\ &= \sum_{i=1}^{n}\alpha_{i} -\cfrac{1}{2}(\sum_{i=1}^{n} \alpha_{i}y_{i}\vec x_{i})(\sum_{i=1}^{n} \alpha_{i}y_{i}\vec x_{i}) \\ &= \sum_{i=1}^{n}\alpha_{i} - \cfrac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_{i}\alpha_{j}y_{i}y_{ij}\vec x_{i}\vec x_{j} \end{align*}\]

\[\vec w = \sum_{i=1}^{n} \alpha_{i}y_{i}\vec x_{i}\]

최적화는 데이터 자신과의 내적에 달려있다.

★ 최종 결론

• 결정조건 \(\vec w \cdot \vec x + b > 0\)

• 최적의 $\vec w$ 값 \(\vec w = \sum_{i=1}^{n}\alpha_{i}y_{i}\vec x_{i}\)

\[\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_{i}y_{i}\vec x_{i}\vec x_{j} + b > 0\]