[D&A 운영진 ML 스터디] 3주차 1차시

선형 SVM 분류

• 두 클래스를 선형으로 분류
• 선 1개로 클래스를 잘 분류해야 함
  • 이때 결정 경계가 샘플에 너무 가까우면 좋지 않음.
    • 멀어야 혹시나 관측하지 못한 데이터를 잘 예측할 수 있음
  • $\therefore$ 폭이 가장 넓은 도로를 찾는 것이 목표
    • $\Rarr$ Large Margin Classification
• 결정 경계로부터 가장 가까운 샘플에 의해 전적으로 의지
  • 이러한 샘플을 서포트 벡터라고 함.
  • 서포트 벡터보다 더 경계와 가까운 곳에 해당 클래스 샘플이 생겨나도 문제가 되지 않음

하드 마진 분류

• 모든 샘플이 도로(서포트 벡터를 지나는 경계와 평행한 선) 바깥쪽에 올바르게 분류하는 상황
  • 이는 데이터가 선형적으로 구분되어야 함
  • 또한 이상치에 민감하다.
• 위 문제를 피하기위해 더욱 유연한 모델 사용
  • 도로 폭 너비와 마진 오류 사이의 적절한 균형 잡아야 함
  • $\Rarr$ 소프트 마진 분류

소프트 마진 분류

• 일정 수준의 오류 수용
  • 도로 폭 너비와 마진 오류 사이의 적절한 균형
• 하이퍼 파라미터 C는 마진 오류 조절
  • C가 높을 수록 적은 마진 오류를 택한다.
  • in scikit-learn

from sklearn.linear_model import SGDClassifier
from sklearn.svm import SVC, LinearSVC

# 아래 3개 모두 동일
## SGDClassifier는 LinearSVC보다 느리게 수렴하나 데이터셋이 너무 클 때 사용
svm_clf = LinearSVC(C=1, loss='hinge')
svc = SVC(kernel="linear", C=1)
sgd_clf = SGDClassifier(loss="hinge", alpha=1/(m*C))

비선형 SVM 분류

• 데이터를 선형으로 분류할 수 없는 경우가 많다.
• Polynomial Features(다항 특성)와 같은 feature를 더욱 추가
  • 차수가 늘어나 선형으로 구분 가능해짐

polynomial_svm_clf = Pipeline([
    ("poly_features", PolynomialFeatuers(degree=3)),
    ("scaler", StandardScaler()),
    ("svm_clf", LinearSVC(C=10, loss="hinge"))
])

다항식 커널

• 낮은 차수의 다항식은 매우 복잡한 데이터셋을 잘 표현하지 못하고, 높은 차수의 다항식은 굉장이 많은 특성을 추가해 모델을 느리게 만듦
• 커널 트릭 사용
  • 실제로는 특성을 추가하지 않으면서 다항식 특성을 많이 추가한 것과 같은 결과 냄

poly_kernel_svm_clf = SVC(kernel="poly", degree=3, coef0=1, C=5)

• 3차 다항식 커널을 통해 SVM 분류기 훈련
  • coef0: 모델이 높은 차수와 낮은 차수에 얼마나 영향을 받을지 조절

유사도 특성

• 각 샘플이 특정 랜드마크와 얼마나 닮았는지 측정해 특성으로 추가
  • 유사도 함수로 계산
• 방사 기저 함수(Radial Basis Function; RBF)
  • $\phi_\gamma (x,l) = e^{-\gamma||x-l||^2}$
  • 랜드 마크에서 아주 멀리 떨어진 경우(0)부터 랜드마크와 같은 위치(1)까지 변화하며 종 모양으로 나타냄
  • ex) $x_1 = -1$, 첫번째 랜드마크에서 1만큼 떨어져 있고, 두번째 랜드마크에서 2만큼 떨어져 있다.
    • $\gamma = 0.3$
    • $x_2 = e^{-0.3 * 1^2} \sim 0.74, x_3 = e^{-0.3 * 2^2} \sim 0.30$
    • $\therefore (x_2, x_3) = (0.74, 0.30)$
  • 랜드마크 선택 방법
    • 모든 데이터 위 랜드마크 생성
      • 차원이 매우 커진다.
      • 선형으로 구분될 가능성이 높지만 훈련세트가 클수록 아주 많은 특성이 만들어짐

가우시안 RBF 커널

• 유사도 특성 방식도 커널 트릭 사용 가능

rbf_kernel_svm_clf = SVC(kernel='rbf', gamma=5, C=0.001)

• gamma: 종 모양 그래프의 너비 조절
  • 클수록 좁아지고 각 샘플의 영향 범위가 작아짐
    • $\rarr$ : 조금 더 불규칙해지고 구불구불해짐
  • 규제의 역할
    • 과대적합일 경우에는 감소시키고, 과소적합일 경우에는 증가시켜야 함
• 다른 여러가지 커널도 존재
  • 문자열 커널, 문자열 서브시퀀스 커널, 레벤슈타인 거리 기반 커널 등
  • 선형 커널을 통해 가장 먼저 시도해보고, 훈련 세트가 너무 크지 않다면 가우시안 RBF 커널 시도

계산 복잡도

• LinearSVC 클래스는 선형 SVM을 위한 최적화된 알고리즘을 구현한 liblinear 라이브러리 기반으로 작동
  • 커널 트릭을 지원하지는 않지만, 훈련 샘플과 특성 수에 거의 선형적으로 늘어남
  • 훈련 시간 복잡도: $O(m\cdot n)$
  • 정밀도를 높이면 수행 시간 길어짐
    • 허용오차 하이퍼파라미터 tol로 조절 - 기본값으로 두면 잘 작동
• SVC는 커널 트릭 알고리즘을 구현한 libsvm 라이브러리 기반 작동
  • 훈련 시간 복잡도 $O(m^2\cdot n), O(m^3 \cdot n)$
    • 복잡하지만 작거나 중간 규모의 훈련 세트에 적합

SVM 회귀

• 분류와 목표를 반대로
  • 일정한 마진 안에서 두 클래스 간의 도로 폭이 가능한 최대가 되도록 하고, 제한된 마진 오류 안에서 도로 안에 가능한 많은 샘플이 들어가도록 학습
    • 하이퍼파라미터 epsilon: 도로의 폭 조절
      • $\varepsilon$에 민감하지 않다
      • 마진 안에 훈련 샘플이 추가되어도 모델 예측에 영향이 없음

from sklearn.svm import LinearSVR, SVR

svm_reg = LinearSVR(epsilon=1.5)
svm_poly_reg = SVR(kernel='poly', degree=2, C=100, epsilon=0.1)

• SVR: SVC의 회귀 버전

SVM 이론

• 선형 SVM 분류 모델은 단순히 결정 함수 $w^Tx + b = w_1x_1 + \dots + w_nx_n + b$를 계산

  • 예측값이 0보다 크면 양성 클래스, 그렇지 않으면 음성 클래스
  • $\hat y = \begin{cases} 0 \;\; w^Tx + b < 0 \\ 1 \;\; \ge 0 \end{cases}$

• 결정 경계: 결정 함수 값이 0인 점들로 이루어져 있음

  • 두 평면의 교차점

• $n$개의 특성이 있을 때 결정 함수는 $n$차원의 초평면, 결정 경계는 $(n-1)$차원의 초평면

• 마진 오류를 최소화하며 마진을 최대화하는 $w$와 $b$를 찾도록 학습

목적 함수

• 결정 함수의 기울기는 가중치 벡터의 노름($||w||$)과 같다.
  • 이 기울기를 2로 나누면 결정 함수의 값이 $\pm 1$이 되는 지점의 점들이 결정 경계로부터 2배 멀어짐
    • 기울기를 2로 나누는 것은 마진에 2를 곱하는 것과 같음
  • 마진을 크게 하기 위해 $||w||$를 최소화
• 마진 오류 최소화를 위해서는 결정 함수가 모든 양성 훈련 샘플은 최대한 1보다 커야하고, 모든 음성 훈련 샘플은 최소한 -1보다 작아야 함
  • 음성 샘플($y^{(i)}=0$)일 때 $t^{(i)}=-1$로, 양성 샘플($y^{(i)}=1$)일 때 $t^{(i)}=1$
• 그러므로 목적 함수를 제약이 있는 최적화 문제로 표현 가능(하드 마진)
  • $minimize_{w,b} \cfrac{1}{2}w^Tw\\ t^{(i)}(w^Tx^{(i)}+b) \ge 1$
    • 미분을 위해 $||w||$가 아닌 $\cfrac{1}{2}||w||^2$를 최소화(미분 불가능)
• 소프트 마진 분류기의 경우, 각 샘플에 대해 슬랙 변수 $\zeta^{(i)} \ge 0$ 도입
  • $\zeta^{(i)}$는 $i$번째 샘플이 얼마나 마진을 위반할 지 정함
  • 해당 문제는 상충되는 목표
    • 마진 최대화를 위한$\cfrac{1}{2}||w||^2$ 최소화
    • 마진 오류 최소화를 위한 $\zeta^{(i)}$ 최소화
    • 하이퍼 파라미터 C로 트레이드 오프 조절
      • C가 커지면 $\zeta^{(i)}$의 변화에 따른 손실 함수가 커져 $\zeta^{(i)}$의 규제 효과 커짐
      • 더 적은 마진 오류 수용한다는 의미
  • $minimize_{w,b,\zeta} \cfrac{1}{2}w^Tw + C \Sigma^m_{i=1}\zeta^{(i)}\\ t^{(i)}(w^Tx^{(i)}+b) \ge 1 -\zeta^{(i)} \;\;and \;\; \zeta^{(i)} \ge 0$

콰드라틱 프로그래밍(이차 방정식)

• 하드 마진과 소프트 마진 문제는 선형적인 제약 조건이 있는 볼록 함수의 이차 최적화 문제
  • 이런 문제를 콰드라틱 프로그래밍이라고 함
  • $minimize_p \cfrac{1}{2}p^THp+f^Tp\\ 조건: Ap \le b$
    • $p$: $n_p$ 차원 벡터 ($n_p$: 모델의 파라미터 수)
    • $H$: $n_p \cdot n_p$ 크기 행렬
    • $f$: $n_p$ 차원 벡터
    • $A$: $n_c \cdot n_p$ 크기 행렬 ($n_c$: 제약 수)
    • $b$: $n_c$ 차원 벡터
    • $Ap \le b$: $n_c$개의 제약 정의
• QP 파라미터 지정 시, 하드 마진을 갖는 선형 SVM 분류기의 목적 함수 검증 가능
  • $n_p = n+1$ ($\because$ 편향, $n$: 특성 수)
  • $n_c = m$ ($m$: 훈련 샘플 수)
  • $H$: 왼쪽 맨 위의 원소가 0인 것을 제외하고는 단위 행렬
    • 편향을 제외하기 위해
  • $f = 0$: 영 벡터
  • $b = 1$: 일 벡터
  • $a^{(i)} = - t^{(i)} \dot x^{(i)}$
    • $\dot x^{(i)}$: 편향을 위해 특성 $\dot x_0 = 1$을 추가한 $x^{(i)}$
  • 결과 벡터 $p$는 편향 $b=p_0$와 특성 가중치 $w_i = p_i$를 담음
• 커널 트릭을 위해서는 최적화 문제를 다른 형태로 바꿔야 함

쌍대 문제

• 원 문제라는 제약이 있는 최적화 문제를 쌍대 문제로 표현 가능
  • 쌍대 문제는 원 문제 해의 하한값이지만 어떤 조건 하에서는 똑같은 해 제공
  • SVM은 해당 조건 만족
• Lagrangian Primal 사용
  • $L(w,b,\alpha) = \cfrac{1}{2}||w||^2_2 - \Sigma^n_{i=1} \alpha_i (y_i(w^Tx_i+b)-1)$
    - $\cfrac{\partial L(w,b,\alpha)}{\partial w} = 0 \rarr w = \Sigma^n_{i=1} \alpha_iy_ix_i \\ \cfrac{\partial L(w,b,\alpha)}{\partial b} = 0 \rarr \Sigma^n_{i=1} \alpha_iy_i = 0$
    • $w$ 계산을 위해서는 $\alpha$만 알면 됨
  • $\cfrac{1}{2}||w||^2_2 = \cfrac{1}{2} w^Tw \\= \cfrac{1}{2}w^T\Sigma^n_{j=1} \alpha_jy_jx_j = \cfrac{1}{2} \Sigma^n_{j=1} \alpha_j y_j (w^T x_j) \\= \cfrac{1}{2} \Sigma^n_{j=1} \alpha_j y_j (\Sigma^n_{i=1} \alpha_i y_i x_i^T x_j) \\= \cfrac{1}{2} \Sigma^n_{i=1}\Sigma^n_{j=1} \alpha_i\alpha_jy_iy_jx_i^Tx_j$
  • $- \Sigma^n_{i=1} \alpha_i (y_i(w^Tx_i+b)-1) \\= -\Sigma^n_{i=1}\alpha_iy_i(w^Tx_i+b) + \Sigma^n_{i=1} \alpha_i \\ = -\Sigma^n_{i=1}\alpha_iy_iw^Tx_i - b\Sigma^n_{i=1} \alpha_i y_i + \Sigma^n_{i=1} \alpha_i \\ = - \Sigma^n_{i=1}\Sigma^n_{j=1}\alpha_i\alpha_jy_iy_jx_i^Tx_j + \Sigma^n_{i=1} \alpha_i$
• $minimize_\alpha \cfrac{1}{2} \Sigma^m_{i=1} \Sigma^m_{j=1} \alpha^{(i)}\alpha^{(j)}t^{(i)}t^{(j)}x^{(i)}x^{(j)}-\Sigma^m_{i=1}\alpha^{(i)}$
  • 해당 식을 최소화하는 벡터 $\hat \alpha$를 찾았다면 원문제의 식을 최소화하는 $\hat w$, $\hat b$ 계산 가능
    • $\hat w = \Sigma^m_{i=1} \hat \alpha^{(i)} t^{(i)} x^{(i)}\\ \hat b = \cfrac{1}{n} \Sigma^m_{i=1} (t^{(i)}-\hat w^T x^{(i)})$
• 원 문제를 통해 커널 트릭을 가능하게 함

커널 SVM

• 2차원 데이터셋에 2차 다항식 변환 적용해 선형 SVM 분류기 적용
  • $\phi(x) = \phi \begin{pmatrix}\begin{pmatrix} x_1\\ x_2 \end{pmatrix}\end{pmatrix} = \begin{pmatrix} x_1^2 \\ \sqrt 2x_1x_2\\ x_2^2 \end{pmatrix}$
    • 2차원 벡터가 3차원으로 변환됨
• 2개의 2차원 벡터 $a$, $b$에 2차 다항식 매핑을 적용한 다음 점곱 적용
  • $\phi(a)^T\phi(b) = \begin{pmatrix} a_1^2 \\ \sqrt2 a_1 a_2\\ a_2^2\end{pmatrix} \begin{pmatrix} b_1^2 \\ \sqrt 2 b_1 b_2 \\ b_2^2 \end{pmatrix} = a^2_1b_1^2 + 2 a_1b_1 a_2 b_2 + a_2^2 b_2^2\\ = (a_1b_1 + a_2b_2)^2 = \begin{pmatrix} \begin{pmatrix} a_1 \\ a_2 \end{pmatrix}^T \begin{pmatrix} b_1 \\ b_2 \end{pmatrix} \end{pmatrix} = (a^Tb)^2$
  • 변환된 벡터의 점곱이 원래 벡터의 점곱의 제곱과 같다.
    • $\phi(a)^T\phi(b) = (a^Tb)^2$
• 모든 훈련 샘플에 변환 $\phi$를 적용하면 쌍대 문제에 점곱 $\phi(x^{(i)})^T\phi(x^{(j)})$ 포함
• $\phi$가 2차 다항식 변환이라면 변환된 벡터의 점곱을 간단하게 $(x^{(i)^T}x^{(j)})^2$으로 바꿈
  • 그래서 실제 훈련 샘플을 변환할 필요가 없이 쌍대식의 점곱을 제곱으로 바꾸기만 하면 됨
  • 값은 실제로 변환해서 알고리즘을 적용한 값과 동일하지만, 계산량이 훨씬 효율적
• 2차 다항식 커널 = 함수 $K(a,b) = (a^Tb)^2$
  • 커널: 변환 $\phi$를 계산하지 않고도 원래 벡터에 기반해 접곱 $\phi(a)^T\phi(b)$를 계산하는 함수
    • 커널 종류
      • 선형: $K(a,b) = a^Tb$
      • 다항식: $K(a,b) = (\gamma a^T b + \gamma)$
      • 가우시안 RBF: $K(a,b) = e^{-\gamma ||a-b||^2}$
      • 시그모이드: $K(a,b) = \tanh(\gamma a^T b + \gamma)$
    • 머서의 정리: 몇 개 수학적 조건을 만족할 때 $\phi$를 모르더라도 존재하는 것을 알기 때문에 $K$를 커널로 사용하는 것
• 커널 트릭 사용 시, 결국 예측 식에 $\phi(x^{(i)})$를 포함해야 함
  • $\hat w$의 차원이 $\phi(x^{(i)})$와 같이 무수히 커져야 함을 의미
    • $\hat w$ 계산 불가
  • $\hat w$에 대한 식을 $x^{(n)}$의 결정 함수에 적용해 입력 벡터 간 점곱으로만 된 식을 얻을 수 있다.
    • $h_{\hat w \hat b}(\phi(x^{(n)})) = \hat w^T \phi(x^{(n)}) + \hat b = (\Sigma^m_{i=1} \hat \alpha^{(i)}t^{(i)}\phi(x^{i}))^T \phi(x^{(n)}) + \hat b \\ = \Sigma^m_{i=1} \hat \alpha^{(i)} t^{(i)}(\phi(x^{(i)})^T \phi(x^{(n)})) + \hat b \ = \Sigma^m_{i=1} \hat \alpha^{(i)} t^{(i)} K(x^{(i)}, x^{(n)}) + \hat b$
  • $\hat b$ 역시 커널 트릭으로 계산해야 함
    • $\hat b = \cfrac{1}{n_s} \Sigma^m_{i=1} (t^{(i)} - \hat w^T \phi(x^{(i)})) = \cfrac{1}{n} \Sigma^m_{i=1} (t^{(i)} - (\Sigma^m_{j=1} \hat \alpha^{(j)}t^{(j)}\phi(x^{(j)}))^T\phi(x^{(i)})) \\ = \cfrac{1}{n_s}\Sigma^m_{i=1} (t^{(i)} - \Sigma^m_{j=1} \hat \alpha^{(j)}t^{(j)}K(x^{(i)}, x^{(j)}))$

온라인 SVM

• 원 문제로부터 유도된 비용 함수를 최소화하기 위한 경사 하강법 사용
  • QP 기반 방법보다 훨씬 느리게 수렴
  • $J(w,b) = \cfrac{1}{2}w^Tw+C\Sigma^m_{i=1} \max(0, 1-t^{(i)}(w^Tx^{(i)}+b))$
    • 첫번째 항: 모델이 작은 가중치 벡터 $w$를 갖도록 제약을 가해 마진을 크게 가짐
    • 두번째 항: 모든 마진 오류를 계산, 샘플이 도로에서 올바른 방향으로 벗어나 있다면 0
    • 힌지 손실: $\max(0, 1-t)$ - ReLU 반대방향 꼴

참고
Hands-on Machine Learning with Scikit-Learn, Keras & Tensorflow 2 - 오렐리앙 제롱
https://www.youtube.com/watch?v=qFg8cDnqYCI