Post

Support Vector Machine

Based on the lecture “Intro. to Machine Learning (2023-2)” by Prof. Je Hyuk Lee, Dept. of Data Science, The Grad. School, Kookmin Univ.

Posted
Preview Image
By jayarnim
9 min read

Support Vector Machine

  • 정의 : 마진(Margin)을 최대로 가져가는 초평면(Hyper Plane)을 규칙으로 하여 관측치를 분류하는 알고리즘

    01

  • 용어의 이해

    02

    • 초평면(Hyper Plane) : 범주를 구분하는 경계
    • 서포트 벡터(Support Vector) : 인접한 범주에 가장 가까이 위치한 벡터
    • 마진(Margin) : 인접한 두 범주의 서포트 벡터를 지나는 평행한 두 직선 사이의 유클리드 거리

Decision Function

Concept

03

  • 초평면 정의

    \[\overrightarrow{w}^{T}\overrightarrow{x}+b=0\]
    • $\overrightarrow{x}$ : 초평면 위에 위치한 벡터
    • $\overrightarrow{w}$ : 초평면의 법선 벡터
    • $b$ : 편향으로서 세로축 절편

  • 범주 정의

    \[y_{i} = \begin{cases} +1,\;if\;\overrightarrow{x}_{i} \in X^{+}\\ -1,\;if\;\overrightarrow{x}_{i} \in X^{-} \end{cases}\]

  • 서포트 벡터 정의

    • 편의상 관측치 벡터 $\overrightarrow{x}_{\forall}$ 와 초평면 사이 거리 절대값은 최소 $1$ 이라고 하자

    • 좌측 서포트 벡터 $\overrightarrow{x}^{+}$ : 범주 $X^{+}$ 에서 초평면에 가장 가까이 위치한 벡터

      \[\overrightarrow{w}^{T}\overrightarrow{x}^{+}+b=+1\]

    • 우측 서포트 벡터 $\overrightarrow{x}^{-}$ : 범주 $X^{-}$ 에서 초평면에 가장 가까이 위치한 벡터

      \[\overrightarrow{w}^{T}\overrightarrow{x}^{-}+b=-1\]

Margin

04

  • 우측 서포트 벡터 $\overrightarrow{x}^{-}$ 에 대하여 방향 $\overrightarrow{w}$ 으로 크기 $margin$ 만큼 이동하면 좌측 서포트 벡터 $\overrightarrow{x}^{+}$ 에 안착한다고 하자

    \[\overrightarrow{x}^{+} = \overrightarrow{x}^{-} + margin \cdot \overrightarrow{w}\]

  • $\overrightarrow{w}^{T}\overrightarrow{x}^{+}+b=1$ 을 다음과 같이 재정의할 수 있음

    \[\begin{aligned} \overrightarrow{w}^{T}\overrightarrow{x}^{+}+b=1\\ \overrightarrow{w}^{T}(\overrightarrow{x}^{-} + margin \cdot \overrightarrow{w})+b=1\\ \overrightarrow{w}^{T}\overrightarrow{x}^{-} + margin \cdot \overrightarrow{w}^{T}\overrightarrow{w} + b = 1\\ (\overrightarrow{w}^{T}\overrightarrow{x}^{-} + b) + margin \cdot \overrightarrow{w}^{T}\overrightarrow{w} = 1\\ -1 + margin \cdot \Vert w \Vert ^2 = 1 \end{aligned}\]

  • 따라서 마진을 다음과 같이 도출할 수 있음

    \[margin = \frac{2}{ \Vert w \Vert ^2}\]

Maximum Margin

  • 최적화 문제 정의

    • 목적 함수

      \[\max{\frac{2}{ \Vert w \Vert ^2}} \Rightarrow \min{\frac{1}{2} \Vert w \Vert ^2}\]

    • 제약 조건

      \[y_{i}(\overrightarrow{w}^{T}\overrightarrow{x}_{i}+b) \ge 1\]

  • 라그랑주 함수 도출

    \[\begin{aligned} L(w,b,\lambda)&=\frac{1}{2} \Vert w \Vert ^2 - \sum_{i=1}^{n}{\lambda_{i}\cdot\{y_{i}(\overrightarrow{w}^{T}\overrightarrow{x}_{i}+b)-1\}} \end{aligned}\]
    • $\lambda_{i}\ge0$ : 라그랑주 승수
  • KKT 조건 하 라그랑주 듀얼 함수로 변환

    • 목적 함수

      \[\begin{aligned} g(\lambda) &= \inf_{w,b}{L(w,b,\lambda)}\\ &= \max_{\lambda}{\min_{w,b}{L(w,b,\lambda)}} \end{aligned}\]

    • 제약 조건 ($\because$ Complementary Slackness, KKT)

      \[\lambda_{i}\cdot\{y_{i}(\overrightarrow{w}^{T}\overrightarrow{x}_{i}+b)-1\}=0\]
      • 서포트 벡터 : \(y_{i \in SV}(\overrightarrow{w}^{T}\overrightarrow{x}_{i \in SV}+b)-1=0\) (\(\because \overrightarrow{w}^{T}\overrightarrow{x}_{i \in SV}+b = 1\))
      • 그 외 벡터 : \(\lambda_{i \notin SV}=0\) (\(\because \overrightarrow{w}^{T}\overrightarrow{x}_{i \notin SV}+b > 1\))

  • 라그랑주 듀얼 함수 풀이

    • $\overrightarrow{w}$, $b$ 에 대하여 편미분

      \[\begin{aligned} \frac{\partial L(w,b,\lambda)}{\partial w} &= \overrightarrow{w} - \sum_{i=1}^{n}{\lambda_{i}y_{i}\overrightarrow{x}_{i}}\\ &= 0\\ \therefore \overrightarrow{w}^{*} &= \sum_{i=1}^{n}{\lambda_{i}y_{i}\overrightarrow{x}_{i}}\\\\ \frac{\partial L(w,b,\lambda)}{\partial b} &= 0 - \sum_{i=1}^{n}{\lambda_{i}y_{i}}\\ &= 0\\ \therefore \sum_{i=1}^{n}{\lambda_{i}y_{i}} &= 0 \end{aligned}\]

    • 편미분한 결과를 라그랑주 듀얼 함수에 대입

      \[\begin{aligned} \frac{1}{2} \Vert w^{*} \Vert ^2 &= \frac{1}{2}\overrightarrow{w}^{*}\cdot\overrightarrow{w}^{*}\\ &= \frac{1}{2}\sum_{i=1}^{n}{\lambda_{i}y_{i}\overrightarrow{x}_{i}} \cdot \sum_{j=1}^{n}{\lambda_{j}y_{j}\overrightarrow{x}_{j}}\\ &= \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}{\lambda_{i}\lambda_{j}y_{i}y_{j}\overrightarrow{x}_{i}^{T}\overrightarrow{x}_{j}}\\\\ \sum_{i=1}^{n}{\lambda_{i}\cdot\{y_{i}(\overrightarrow{w}^{T}\overrightarrow{x}_{i}+b)-1\}} &= \sum_{i=1}^{n}{\lambda_{i}y_{i}\overrightarrow{w}^{T}\overrightarrow{x}_{i}} + b\sum_{i=1}^{n}{\lambda_{i}y_{i}} - \sum_{i=1}^{n}{\lambda_{i}}\\ &= \sum_{i=1}^{n}{\lambda_{i}y_{i}(\sum_{j=1}^{n}\lambda_{j}y_{j}\overrightarrow{x}_{j})\overrightarrow{x}_{i}} + b \cdot 0 - \sum_{i=1}^{n}{\lambda_{i}}\\ &= \sum_{i=1}^{n}\sum_{j=1}^{n}{\lambda_{i}\lambda_{j}y_{i}y_{j}\overrightarrow{x}_{i}\overrightarrow{x}_{j}} - \sum_{i=1}^{n}{\lambda_{i}}\\\\ \therefore g(\lambda) &= \inf_{w,b}{L(w,b,\lambda)}\\ &= \max_{\lambda}\min_{w,b}{L(w,b,\lambda)}\\ &= \max_{\lambda}{L(\lambda)}\\ &= \max_{\lambda}{\left[\frac{1}{2} \Vert w^{*} \Vert ^2 - \sum_{i=1}^{n}{\lambda_{i}\cdot\{y_{i}(\overrightarrow{w}^{T}\overrightarrow{x}_{i}+b)-1\}}\right]}\\ &= \max_{\lambda}{\left[\sum_{i=1}^{n}{\lambda_{i}} - \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}{\lambda_{i}\lambda_{j}y_{i}y_{j}\overrightarrow{x}_{i}^{T}\overrightarrow{x}_{j}}\right]} \end{aligned}\]

Support Vector

  • 마진을 최대화하는 법선 벡터 $\overrightarrow{w}^{*}$

    \[\overrightarrow{w}^{*} = \sum_{i \in SV}{\lambda_{i}y_{i}\overrightarrow{x}_{i}}\]
  • 마진을 최대화하는 편향 $b^{*}$
    • 라그랑주 듀얼 함수의 제약 조건 ($\because$ Complementary Slackness, KKT)
      • 서포트 벡터 : \(y_{i \in SV}(\overrightarrow{w}^{T}\overrightarrow{x}_{i \in SV}+b)-1=0\) (\(\because \overrightarrow{w}^{T}\overrightarrow{x}_{i \in SV}+b = 1\))
      • 그 외 벡터 : $\lambda_{i \notin SV}=0$ ($\because \overrightarrow{w}^{T}\overrightarrow{x}_{i \notin SV}+b > 1$)

    • 마진을 구함에 있어 그 외 벡터는 필요하지 않음

      \[y_{i \in SV}(\overrightarrow{w}^{T}\overrightarrow{x}_{i \in SV}+b)-1=0\]

    • 따라서 마진을 최대화하는 서포트 벡터의 편향 $b^{*}_{SV}$ 을 다음과 같이 도출할 수 있음

      \[\begin{aligned} b^{*} &= y_{i \in SV} - \overrightarrow{w}^{T}\overrightarrow{x}_{i \in SV}\\ &= \frac{1}{ \vert SV \vert }\sum_{i \in SV}{\left[y_{i} - \overrightarrow{w}^{T}\overrightarrow{x}_{i}\right]}\\ &= \frac{1}{ \vert SV \vert }\sum_{i \in SV}{\left[y_{i} - \left(\sum_{j \in SV}{\lambda_{j}y_{j}\overrightarrow{x}_{j}}\right)\overrightarrow{x}_{i}\right]}\;(\because \overrightarrow{w}^{*}=\sum_{i}{\lambda_{i}y_{i}\overrightarrow{x}_{i}})\\ &= \frac{1}{ \vert SV \vert }\sum_{i \in SV}\sum_{j \in SV}{\left[y_{i} - \lambda_{j}y_{j}\overrightarrow{x}_{j}\overrightarrow{x}_{i}\right]} \end{aligned}\]

  • 마진을 최대화하는 서포트 벡터 $\overrightarrow{x}_{SV} \in SV$

    \[\begin{aligned} SV &= \{\overrightarrow{x}_{SV} \vert \overrightarrow{w}^{*} \cdot \overrightarrow{x}_{SV} + b^{*}= \vert 1 \vert \}\\ &= \left\{ \overrightarrow{x}_{SV} \vert \left(\sum_{i=1}^{n}{\lambda_{i}^{*}y_{i}\overrightarrow{x}_{i}}\right) \cdot \overrightarrow{x}_{SV} + \frac{1}{ \vert SV \vert }\sum_{i \in SV}\sum_{j \in SV}{\left[y_{i} - \lambda_{j}y_{j}\overrightarrow{x}_{j}\overrightarrow{x}_{i}\right]}= \vert 1 \vert \right\} \end{aligned}\]

Summary

\[\begin{aligned} y_{q} &= \begin{cases} +1,\;if\;f(\overrightarrow{q}) > 0 \\ -1,\;if\;f(\overrightarrow{q}) < 0 \\ \end{cases}\\\\ f(\overrightarrow{q}) &= \overrightarrow{w}^{*} \cdot \overrightarrow{q} + b^{*}\\ &= \left(\sum_{i \in SV}{\lambda_{i}y_{i}\overrightarrow{x}_{i}}\right) \cdot \overrightarrow{q} + \frac{1}{ \vert SV \vert }\sum_{i \in SV}\sum_{j \in SV}{\left[y_{i} - \lambda_{j}y_{j}\overrightarrow{x}_{j}\overrightarrow{x}_{i}\right]} \end{aligned}\]
  • $\overrightarrow{q}$ : 신규 관측치 벡터
  • $y_{q}$ : $\overrightarrow{q}$ 의 범주
  • $f(\overrightarrow{q})$ : 결정 함수로서 초평면 $\overrightarrow{w}^{T}\overrightarrow{x}+b=0$ 과 벡터의 사영 거리

Soft Margin

  • 하드 마진(Hard Margin)의 문제점 : 이상 관측치가 존재하는 경우 마진을 최대화하는 초평면을 탐색하기 어려움

    05

  • 소프트 마진(Soft Margin)의 해결책 : 마진 위반 $\xi$ 를 허용하여 일부 이상 관측치를 배제했을 때 마진을 최대화하는 초평면을 탐색함

    06

    • 마진 위반(Margin Violation; $\xi$) : 초평면 근방에서 발생 가능한 소수의 이상 관측치에 대한 오류로서, 해당 관측치로부터 서포트 벡터를 지나고 초평면과 평행한 직선까지의 유클리드 거리

마진 위반 $\xi$ 를 고려하는 최적화 문제 정의

  • 하드 마진의 최적화 문제

    \[\begin{aligned} &\min{\frac{1}{2} \Vert w \Vert ^2}\\\\ \quad \text{s.t.} \quad &y_{i}(\overrightarrow{w}^{T}\overrightarrow{x}_{i}+b) \ge 1 \end{aligned}\]

  • 소프트 마진의 최적화 문제

    \[\begin{aligned} &\min{\left[\frac{1}{2}{ \Vert w \Vert ^2}+C\sum_{i=1}^{n}{\xi_i}\right]}\\\\ \quad \text{s.t.} \quad &y_{i}(\overrightarrow{w}^{T}\overrightarrow{x}_{i}+b) \ge 1-\xi_i,\\ &\xi_i \ge 0 \end{aligned}\]

    • $\xi_{i}$ : 관측치 벡터 $\overrightarrow{x}_{i}$ 에 대한 마진 위반

    • $C$ : 마진 위반에 대한 규제 강도

      07

How to Solve

  • 라그랑주 함수 도출

    \[\begin{aligned} L(w,b,\lambda,\xi,\mu) = &\left[\frac{1}{2} \Vert w \Vert ^2 - \sum_{i=1}^{n}{\lambda_{i}\{y_{i}(\overrightarrow{w}^{T}+b)-(1-\xi_{i})\}}\right]\\ &+ \left[C\sum_{i=1}^{n}{\xi_{i}}-\sum_{i=1}^{b}{\mu_{i}\xi_{i}}\right] \end{aligned}\]
    • $\lambda \ge 0$ : 제약 조건 $y_{i}(\overrightarrow{w}^{T}\overrightarrow{x}+b) \ge 1-\xi_{i}$ 에 대한 라그랑주 승수
    • $\mu \ge 0$ : 제약 조건 $\xi_{i} \ge 0$ 에 대한 라그랑주 승수

  • KKT 조건 하 라그랑주 듀얼 함수 도출

    \[\begin{aligned} g(\lambda,\mu) &= \inf_{w,b,\xi}{L(w,b,\lambda,\xi,\mu)}\\ &= \max_{\lambda,\mu}{\min_{w,b,\xi}{L(w,b,\lambda,\xi,\mu)}}\\\\ \quad \text{s.t.} \quad &\lambda_{i}\{y_{i}(\overrightarrow{w}^{T}\overrightarrow{x}+b)-(1-\xi_{i})\}=0,\\ &\mu_{i}\xi_{i}=0 \end{aligned}\]

  • $\overrightarrow{w}$,$b$,$\xi$ 에 대하여 편미분

    \[\begin{aligned} \frac{\partial L(w,b,\lambda,\xi,\mu)}{\partial w} &= \overrightarrow{w} - \sum_{i=1}^{n}{\lambda_{i}y_{i}\overrightarrow{x}_{i}}\\ &= 0\\\\ \frac{\partial L(w,b,\lambda,\xi,\mu)}{\partial b} &= \sum_{i=1}^{n}{\lambda_{i}y_{i}}\\ &= 0\\\\ \frac{\partial L(w,b,\lambda,\xi,\mu)}{\partial \xi} &= C-\lambda_{i}-\mu_{i}\\ &= 0\\\\ \therefore \overrightarrow{w}^{*} &= \sum_{i=1}^{n}{\lambda_{i}y_{i}\overrightarrow{x}_{i}},\\ \sum_{i=1}^{n}{\lambda_{i}y_{i}} &= 0,\\ \mu_{i} &= C - \lambda_{i} \end{aligned}\]

  • 위 결과를 라그랑주 듀얼 함수에 대입하여 \(\overrightarrow{w}^{*}\), \(b^{*}\) 도출

    \[\begin{aligned} \overrightarrow{w}^{*} &= \sum_{i \in SV}{\lambda_{i}y_{i}\overrightarrow{x}_{i}}\\ b^{*} &= \sum_{i \in SV}{\sum_{j \in SV}{\left[y_{i}-\lambda_{j}y_{j}\overrightarrow{x}_{j}\overrightarrow{x}_{i}\right]}} \end{aligned}\]

Kernel Trick

  • 정의 : 선형으로는 구분하기 어려운 저차원 공간상의 데이터 세트를, 적절한 결정 경계를 찾을 수 있는 고차원 공간으로 매핑하는 기법

    08

Mercer’s Theorem

저차원 공간 $L$ 에서 고차원 공간 $H$ 로 관측치들을 매핑하는 커널함수 $K$ 는 $L$ 에서 표현된 관측치들 간 유클리드 거리와 $H$ 에서 표현된 관측치들 간 유클리드 거리를 보존함

  • 임의의 관측치 $X_a, X_b$ 에 대하여, $2$ 차원 공간에서 해당 관측치를 나타내는 벡터 $\overrightarrow{a}, \overrightarrow{b}$ 를 다음과 같이 정의하자

    \[\begin{aligned} \overrightarrow{a} &= \begin{pmatrix}a_1\\a_2\end{pmatrix}\\ \overrightarrow{b} &= \begin{pmatrix}b_1\\b_2\end{pmatrix} \end{aligned}\]

  • $\overrightarrow{a}, \overrightarrow{b}$ 을 $3$ 차원상의 벡터 $\Phi(\overrightarrow{a}),\Phi(\overrightarrow{b})$ 로 매핑하는 커널함수 $K(\overrightarrow{a}, \overrightarrow{b})$ 는 다음의 조건을 만족함

    \[\begin{aligned} K(\overrightarrow{a}, \overrightarrow{b}) &= (\overrightarrow{a}^T \overrightarrow{b})^2 \\ &= a_1^2b_1^2 + 2(a_1b_1a_2b_2) + a_2^2b_2^2 \\ &= (a_1^2, \sqrt{2}a_1a_2, a_2^2) \cdot (b_1^2, \sqrt{2}b_1b_2, b_2^2) \\ &= \Phi(\overrightarrow{a}) \cdot \Phi(\overrightarrow{b}) \end{aligned}\]

Type

  • Linear

    \[K(\overrightarrow{a}, \overrightarrow{b}) = \overrightarrow{a}^T \overrightarrow{b}\]

  • Polynomial

    \[K(\overrightarrow{a}, \overrightarrow{b}) = (\gamma \overrightarrow{a}^T \overrightarrow{b} + r)^d\]

  • Radial Basis Function(RBF)

    \[K(\overrightarrow{a}, \overrightarrow{b}) = \exp(-\gamma \Vert \overrightarrow{a}- \overrightarrow{b} \Vert ^2)\]

  • Hyperbolic Tangent

    \[K(\overrightarrow{a}, \overrightarrow{b}) = \tanh(\gamma \overrightarrow{a}^T \overrightarrow{b} + r)\]

SVR

09

  • 초평면

    \[\begin{aligned} f(\overrightarrow{x}_{i}) &= \overrightarrow{w}^{T}\overrightarrow{x}_{i}+b \end{aligned}\]

  • 차이점 : 제약 조건

    10

    • 판별 분석 : 마진 범위 이내에 관측치 벡터가 존재하지 않음

      \[\begin{aligned} \text{s.t.} \quad &y_{i}(\overrightarrow{w}^{T}\overrightarrow{x}_{i}+b) \ge 1 + \xi_{i},\\ &\xi_{i} \ge 0 \end{aligned}\]

    • 회귀 분석 : 마진 범위 이내에 모든 관측치 벡터가 존재함

      \[\begin{aligned} \text{s.t.} \quad &-(\varepsilon + \xi_{i}) \le f(\overrightarrow{x}_{i}) - y_{i} \le \varepsilon + \eta_{i},\\ &\xi_{i},\eta_{i} \ge 0 \end{aligned}\]

  • SVR 최적화 문제

    \[\overrightarrow{\hat{w}},\hat{b},\hat{\xi}_{i},\hat{\eta}_{i} =\text{arg} \min_{\overrightarrow{w},b,\xi,\eta}{\left[\frac{1}{2} \Vert w \Vert ^{2}+C\sum_{i=1}^{n}{(\xi_{i}+\eta_{i})}\right]}\] \[\begin{aligned} \\ \text{s.t.} \quad & \varepsilon + \xi_{i} + f(\overrightarrow{x}) - y_{i} \ge 0,\\ & \varepsilon + \eta_{i} - f(\overrightarrow{x}) + y_{i} \ge 0,\\ & \xi_{i}, \eta_{i} \ge 0 \end{aligned}\]

이미지 출처

  • https://velog.io/@shlee0125
  • https://medium.com/@niousha.rf/support-vector-regressor-theory-and-coding-exercise-in-python-ca6a7dfda927
Machine Learning Techs, Machine Learning
Machine Learning Supervised Learning Classification
This post is licensed under CC BY 4.0 by the author.