[AI] SVM (2)

💡 만약에 training set이 not linearly separable 하다면?

Soft Margin Classification

• Hard Margin : 모든 data가 분류되어야 함!
• Soft Margin : 몇 개는 틀려도 된다고 허용!
  ⇒ Slack variables (여유 변수)

• C : hyper parameter로 얼만큼 틀려도 되는가를 정의
• N : 모든 data에 대해서 margin으로부터의 거리
• L(w)가 최솟값이 되어야 함!

---

Non-linear SVM

• 위와 같은 dataset은 매우 잘 작동함

💡 하지만 아래와 같은 dataset은 어떻게 해야할까?

⇒ 고차원으로 mapping ❗

---

• 보통 (n+1)차원으로 가면 separable해짐!
  

📌 kernel function

• mapping 해주고, 내적도 해주는 함수
  

---

Kernel function and Kernel trick

📌 Kernel function

• 고차원에서 내적해서 얻어지는 함수

• 내적 = 두 data 간의 similarity

• reproducing kernel Hilbert space에서의 유사도

• $K(x_i, x_j) = φ(x^i)^Tφ(x_j)$

• 선형대수에서 나오는 kernel의 개념과는 다름

📌 Kernel trick

• Avoids the explicit mapping

---

📌 Kernel example

• 2차원 공간의 data(vector) $x=[x_1 x_2];$

• $K(x_i, x_j) = (1+{x_i}^T,x_j)^2$
  

• 실제로 고차원에 보내지 않아도 고차원으로 보내 유사도를 얻은 값과 똑같음
  ⇒ kernel trick

• linear 알고리즘에 kernel function만 도입하면 non-linear 문제도 풀 수 있음!

---

📌 대표적인 Kernel function

1. Linear kernel
   
2. Polynomial kernel
   
3. Radial basis kernel (Gaussian)
   
4. Hyperbolic Tangent kernel
   

• 모든 함수가 kernel function은 아님 ❗

---

Kernel-based learning methods

• linear 알고리즘으로 non-linear 문제도 풀 수 있게 됨

1. 고차원으로 data 보내기
2. linear 알고리즘 (SVM, PCA, ridge regression, ...)으로 학습

• but, 요즘은 딥러닝때문에 그렇게 쓰는 방법은 아님!

---

💡 그렇다면 kernel function은 어떻게 만들까?

• semi-positive definite symmetric (mercer's theorem)으로 kernel function임을 증명

• time complexity 분석

• compositive kernel
  E.g.) $K_{new}(x_i, x_j) = {x_i}^Tx_j + ({x_i}^Tx_j)^p$
  ⇒ linear kernel + polynomial kernel