SVM(Support Vector Machine)

마진을 최대화하는 알고리즘

마진이란 클래스를 구분하는 초평면(결저 경계)과 가장 가까운 train sample 사이의 거리로 정의한다. 그리고 그 샘플은 서포트 벡터라고 한다. 

 

 

마진의 개념에 대해서 잘 이해할 수 있는 그래프이다.

---

 

결국 마진, 거리의 개념을 최대화하는 아이디어에 대해 생각해봐야한다.

조금 평면을 확장시켜서 다음과 같이 가정할 수 있다.

 

 

x0는 초평면 위의 벡터이므로 초평면 방정식에 대입하게 되면 오른쪽과 같은 식을 얻을 수 있다.

 

우리가 궁금한 것은 gamma(i), dist 거리에 대한 정보이기 때문에 

최종적으로 위와 같은 식이 나온다. 그리고 저 gamma를 geometric margin 이라고 부른다.

 

margin_x0 = (theta.dot(x0) + theta0)[0] / np.linalg.norm(theta)

 

All the points inside the margin are support vectors which contribute to rhe solution.

points that are outside of the margin and on the correct side don't contribute the solution

 

Maximizing the margin

마진을 최대화하기 위해서 다음과 같은 목적함수를 정의할 수 있다.

theta norm을 우변으로 옮긴다.

이때 추가로 제약조건을 더 떠올려서 r||theta|| 를 1로 한다면

gamma의 최대를 찾는 것은 ||theta|| 의 최소를 찾는 것과 같고 이는

 

와 동치라고 볼 수 있다. 이 경우 여전히 목적함수를 아래와 같이 정리한다.

 

이제 얘는 Quadratic optimization algorithms이라고 볼 수 있고 선형 SVD 분류에 대한 요약 정보는 아래와 같다.

 

 

---

 

자, 근데 Non-Separable Problems에 대해서는 어떻게 해결할 것인가?

 

이 경우 제약조건을 앞서  r||theta|| 를 1로 한다면 보다 soft한 데약식을 만들 수 있다. 

 

저 요상한 기호는 크사이 chi의 소문자이고

아무튼, 완벽하게 분류한다면 0이 되겠지만 그게 아니면 1-크사이 의 score를 가지는 상태로 할당할 수 있다.

크사이의 값에 대해 패널티를 부과함으로서 목적함수를 재정의하게 된다.

 

목적함수를 크사이에 대해 최대값을 찾는 방향으로 정리하면서 max(x,0)의 notation을 적용해 식으로 쓴게 왼쪽이다.

 

기존 목적함수에 대해 크사이를 대입하고 C>0이므로 무시한 후에 식을 재정리하게 된다면

 

 

힌지 로스를 활용해서 코드에 적용한다면

 

def svm_objective(theta, X, y, C=.1):
    """The cost function, J, describing the goodness of fit.
    
    Parameters:
    theta (np.array): d-dimensional vector of parameters
    X (np.array): (n,d)-dimensional design matrix
    y (np.array): n-dimensional vector of targets
    """
    return (np.maximum(1 - y * f(X, theta), 0) + C * 0.5 * np.linalg.norm(theta[:-1])**2).mean()

 

그리고 힌지로스를 사용해서 classifiaction을 하면

 

threshold = 5e-4
step_size = 1e-2

theta, theta_prev = np.ones((3,)), np.zeros((3,))
iter = 0
iris_X['one'] = 1
X_train = iris_X.iloc[:,[0,1,-1]].to_numpy()
y_train = iris_y2.to_numpy()

while np.linalg.norm(theta - theta_prev) > threshold:
    if iter % 1000 == 0:
        print('Iteration %d. J: %.6f' % (iter, svm_objective(theta, X_train, y_train)))
    theta_prev = theta
    gradient = svm_gradient(theta, X_train, y_train)
    theta = theta_prev - step_size * gradient
    iter += 1
    
xx, yy = np.meshgrid(np.arange(x_min, x_max, .02), np.arange(y_min, y_max, .02))
Z = f(np.c_[xx.ravel(), yy.ravel(), np.ones(xx.ravel().shape)], theta)
Z[Z<0] = 0
Z[Z>0] = 1

# Put the result into a color plot
Z = Z.reshape(xx.shape)
plt.pcolormesh(xx, yy, Z, cmap=plt.cm.Paired)

# Plot also the training points
plt.scatter(X_train[:, 0], X_train[:, 1], c=y_train, edgecolors='k', cmap=plt.cm.Paired)
plt.xlabel('Sepal length')
plt.ylabel('Sepal width')

plt.show()

이런 분류를 얻을 수 있다.

 

---

 

로지스틱 회귀와 서포트 벡터 머신의 비교

선형 로지스틱 회귀와 선형 SVM은 종종 비슷한 결과를 만든다. 로지스틱 회귀는 훈련 데이터의 조건부 가능도를 최대화하기 때문에 SVM보다 이상치에 민감하다. SVM은 결정 경계에 가장 가까운 포인트(서포트 벡터)에 관심을 둔다. 반면 로지스틱 회귀는 모델이 간단하고 구현하기가 더 쉬운 장점이 있다. 나아가, 업데이트가 용이하므로 스트리밍 데이터를 다룰 때 적합하다.