[Data Mining] Support Vector Machine (SVM) - Non-linearly Separable Data

* SVM - linearly separable data에 관한 설명 여기 참고

 

SVM 기본 요약 

 

 

Soft Margin hyperplane Classifier: Non-linearly Separable Data

• 위 그림처럼 linear하게 두 클래스를 나눌 수 없다면, 두 가지 방법을 이용하여 분류를 진행할 수 있다.
  • 방법1: slack variable 사용
  • 방법2: 데이터를 고차원으로 매핑

 

 

Slack variable 사용

• 위 그림처럼 linear하게 두 클래스를 나눌 수 없다면, 우리는 비록 cost가 높아질지라도 몇 몇 데이터를 misclassify하는 것을 허락할 수 있다.
  
  • Soft margin 방법은 여전히 가장 가까이 위치해 있는 제대로 분리되는 자료들의 거리를 최대화하면서, 주어진 자료들을 가능한 한 제대로 분리하는 hyperplane을 찾을 것이다. 
  • 이 때, slack 변수($\displaystyle \xi _{i}$)를 사용하여, 선형적으로 분류를 할 수 없는 경우 오차를 허용하기 위해 제약조건을 완화시켜 오차를 허용한다.
    • 이 변수는 자료 $x_i$가 잘못 분류된 정도를 나타낸다.
    • $\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1-\xi _{i}\quad 1\leq i\leq n.\quad$
    • 목적함수는 0이 아닌 s에 대해 페널티를 부과하는 함수에 의해 증가된다. 그에 따른 최적화는 마진을 크게 하는 것과 에러에 대한 페널티를 작게 하는 것의 균형을 맞추는 것이 된다. 
      • s=$\displaystyle \xi _{i}$
      • $\sum s$또한 최소화해야할 추가 cost이다.

• 수정된 최적화 문제: L(w)

 

=  L(w)

 

 

• 이 최적화 문제를 풀기 위해, 우리는 먼저 primal variables를 사용해서 Largrangian 세워야한다:

 

 

 

 

데이터를 고차원으로 매핑

• 문제: 데이터가 linear하게 안 나눠짐
• 해결책 1:
  • Non-linear hyperplane으로 나눈다. ->

• 해결책 2:
  • 데이터를 고차원으로 매핑해서 linear하게 나누기
  • 방법:
    • training data를 고차원 공간으로 매핑
    • linear hyperplane으로 나눔
  • Performance 좋음!

 

 

 

 

주어진 unkown data X를 + 또는 -로 분류하자

• input vector X를 $\phi : R^n -> H$를 이용해 매핑한다.

• map을 사용하여 세운 linear hyperplane 식:

 

 

• Kernels: 선형 분류가 어려운 저차원 데이터를 고차원 공간으로 매핑하는 함수
  • $\phi$: 매핑 함수

• 등식의 제일 왼쪽 부분부터 1,2,3 번호를 매겨보자.
• 우리는 [2]번 함수인 $\phi$를 몰라도, [1]번을 SVM 학습에 바로 사용할 수 있다.
  • [2]을 계산하기 위해 [3]을 이용하면 너무 복잡하다.
  • [1]을 이용하면 간단하게 계산할 수 있다.

 

 

Example: Computing feature space inner prodects via Kernel functions

• X에 대해 다음과 같다고 하자.

• 그럼 매핑한 식은 다음과 같다.

• m이 크다면, 다음의 식은 계산하기 매우 어렵다.
• 하지만 $a_l$을 신중하게 고르는 것은 계산양을 극도로 줄일 수 있다.

• $(1+xy)^m$: kernel 함수

 

 

Mercer's Condition

• 다음은 kernel 함수를 사용해서 inner product한 결과이다.

• 어떤 커널에 대해, 일반적으로 고차원 공간 H에 대한 매핑 $\phi$가 존재하는가?
• Mercer의 조건: 만족하는 매핑 함수 $\phi$가 존재하는지 판단 (판단 조건)
  • Mercer 조건을 만족하면, [ $K(x_i,x_j) = \phi (x_i), \phi (x_j)$ ]를 만족하는 $\phi$가 존재하는 것을 알 수 있다.
• Mercer의 조건에 의해 $\phi$가 존재하는 것을 안다면, [ $\phi (x_i)· \phi (x_j)$ ]를 직접 계산할 필요가 없고, kernel 함수로 계산하면 된다.

 

 

SVM 알고리즘 연산

• Given: Training data set T가 들어옴. 이를 -1 또는 1로 분류할 것
• Initialize: kernel function K()를 선택
  • Hessian matrix: $H_{ij} = d_i d_j K(X_i, X_j)$ 설정
  • C 설정
• Maximize

• class 예측

 

 

 

 

 

참고:

- 위키 백과: https://ko.wikipedia.org/wiki/%EC%84%9C%ED%8F%AC%ED%8A%B8_%EB%B2%A1%ED%84%B0_%EB%A8%B8%EC%8B%A0