[머신러닝 정리] 서포트 벡터 머신(Support Vector Machine) - 02. Binary Classification

Seong-Heon Lee·2022년 6월 6일
2
post-thumbnail

본 포스팅 시리즈는 다양한 머신러닝 테크닉에 대해 수학적 관점과 실용적 관점에서 정리한다.

필자는 수학을 전공했기 때문에 수학적 접근과 용어에 대해 익숙하게 사용한 것이 있지만, 수학을 전공하지 않은 사람들에겐 다소 낯선 접근과 용어가 있을 수 있다.

최대한 그러한 부분을 자세히 설명하려 노력하였지만 필자의 타전공자에 대한 '공감능력부족'으로 효과적으로 전달되지 못한 부분이 있을 것으로 생각된다.

이 글을 읽어주시는 분께 일차적으로 감사드리며, 해당 부분에 대해 질문이나 코멘트를 남겨주시는 분께는 거듭제곱으로 감사드림을 말씀드린다.

Support Vector Machine

서포트 벡터 머신은 딥러닝이 등장하기 이전에 가장 유명하고 성능 좋은 머신러닝 모델이었다고 한다.
현재는 다소 실무에서 사용되는 정도가 줄어들었겠지만, 서포트 벡터 머신에 적용되는 다양한 수학적 테크닉들은 인공지능을 이해하고 연구하는 데에 여전히 훌륭한 인사이트를 준다고 생각한다.
특히 서포트 벡터 머신의 아이디어는 유클리드 기하학과 최적화 이론으로 설명이 된다는 점은 수학자들에게 있어서 굉장히 매력적이다.

본 포스팅의 내용은 다음의 자료들을 참고했다.

  1. Mathematics for Machine Learning (Deisenroth, Marc Peter and Faisal, A. Aldo and Ong, Cheng Soon)
  2. The Elements for Statistical Learning (Trevor Hastie, Robert Tibshirani, Jerome Friedman)
  3. 김민준님(이화여자대학교, 수학과 석사)의 SVM Lecture note
  4. 김원화 교수님(포항공과대학교, 인공지능대학원 교수)의 데이터 마이닝 Lecture note
  5. Hands-On Machine Learning with Scikit-Learn, Keras, and Tensorflow (Aurelien, Geron)

2. Binary Classification

📌 핵심 Keyword

  • 이진분류 문제 (Binary Classification) : 두 가지 클래스의 데이터를 분류하는 문제.
  • 선형분류 문제 (Linear Classification) : 선형결정경계에 의해 완벽히 분류가 되는 이진분류 문제.
  • 선형 분류기 (Linear Classifier) : 선형결정경계를 생성하는 예측모델.

2.1 이진분류 (Binary Classification)

일반적인 서포트 벡터 머신(SVM)은 이진분류 문제를 풀기 위한 모델이다.
그러므로 이진분류 문제를 정확하게 이해해야 SVM을 어떻게 작동하는지, 언제 사용해야 하는지 올바르게 이해할 수 있다.

이진분류(Binary classfication) 문제는 데이터가 두 개의 클래스로 분류될 수 있는 문제를 말한다.
예를들어, 소비자들의 다양한 정보를 입력받아 이 소비자가 특정 상품을 구매 할지 안할지 예측하는 문제나, 신호에 대한 정보를 입력받아 이 정보가 진짜 신호인지 가짜 신호인지 분별하는 문제가 이진분류 문제이다.
이진분류 문제에서 출력변수 yy는 0 또는 1로 표기하거나 -1 또는 +1로 표기한다.
SVM을 설명할 때엔 이진분류 문제의 출력변수를 주로 -1과 +1로 표현한다.

이진분류 문제를 수학적으로 표현해보자.
NN개의 데이터 (x1,y1),(x2,y2),,(xN,yN)(x_1,y_1), (x_2,y_2), \ldots , (x_N, y_N)으로 구성된 훈련 데이터가 주어졌다고하자.
여기서 xiRdx_i \in \mathbb{R}^d 이고, y{1,+1}y \in \left\{-1, +1\right\}이다.
그러면 이진분류 문제는 훈련 데이터를 학습하여 분류 오차를 최소가 되게 하는 분류함수

G:Rd{1,+1}G : \mathbb{R}^d \rightarrow \left\{-1, +1 \right\}

를 모델링하는 것으로 정의될 수 있다.

2.2 선형분류 (Linear classification)

선형분류(Linear classification) 문제는 훈련 데이터로부터 적절한 선형함수

f(x)=xTβ+β0f(x) = x^T \beta + \beta_0

를 만들어, 이로부터 데이터의 클래스를 분리할 수 있는 초평면

{xRd:f(x)=xTβ+β0=0}\left\{ x \in \mathbb{R}^d : f(x) = x^T \beta + \beta_0 = 0 \right\}

을 찾는 문제다.
여기서 β0R\beta_0 \in \mathbb{R}은 선형함수 ff절편(intercept)이며, 파라미터 βRd\beta \in \mathbb{R}^d (β=1\lVert \beta \rVert = 1)는 초평면에 수직인 단위벡터, 즉 법선벡터(normal vector)이다.

선형분류 문제에 대하여, 분류함수 GGf(x)f(x)에 의해

G(x)=sign[f(x)]=sign[xTβ+β0]G(x) = sign[f(x)] = sign[x^T\beta + \beta_0]

로 유도된다.
여기서 sign(x)={+1(x0)1(x<0)sign(x) = \begin{cases} +1 & (x \geq 0) \\ -1 & (x < 0)\end{cases}부호함수(sign function)이다.
그리고 초평면 {xRd:f(x)=xTβ+β0=0}\left\{ x \in \mathbb{R}^d : f(x) = x^T \beta + \beta_0 = 0 \right\}결정경계(Decision boundary)라고 부른다.

선형함수 f(x)f(x)의 파라미터 β\beta는 결정경계를 기준으로 방향을 결정한다.
데이터 xx에 대하여 f(x)0f(x) \geq 0이면 결정경계의 양의 방향에 놓인다고 하며, 이 경우 G(x)=+1G(x) = +1이다.
마찬가지로 f(x)<0f(x) < 0이면 데이터가 결정경계의 음의 방향에 놓인다고 하며, 이 경우 G(x)=1G(x) = -1이다.

훈련 데이터 xix_iyi=+1y_i = +1의 레이블을 가진다면, f(xi)0f(x_i) \geq 0이 되어야 G(xi)=+1G(x_i) = +1이 된다.
마찬가지로 yi=1y_i = -1의 레이블을 가진다면, f(xi)<0f(x_i) < 0이 되어야 G(xi)=1G(x_i) = -1이 되어 정확한 예측이 된다.
그러므로 yif(xi)>0y_if(x_i) > 0이면 모델이 훈련 데이터 xix_i의 클래스 yiy_i를 정확히 예측했다고 할 수 있다.

선형분리 가능 문제(Linearly separable problem)는 모든 ii에 대하여 yif(xi)>0y_if(x_i) > 0이 되게 하는 선형함수 f(x)=xTβ+β0f(x) = x^T \beta + \beta_0를 찾을 수 있는 문제를 말한다.
학습된 데이터로부터 선형결정경계를 만드는 모델을 선형 분류기(Linear classifier)라고 부른다.
선형 분류기는 선형분리 가능 문제에 사용하기 적절하다.

2.3 최적화된 선형결정경계

두 클래스를 분류할 수 있는 선형함수 f(x)f(x)의 선택, 즉 결정경계는 여러개 존재할 수 있다.
그렇다면 어떤 결정경계를 선택하는 것이 가장 일반화 성능이 좋다고 할 수 있을까?

SVM은 이 질문에 대해 유클리드 기하학과 최적화 이론의 언어로 답을 한다.
모델의 융통성을 얻기 위해 SVM은 마진(margin)이 최대가 되도록 선형함수 f(x)f(x)를 선택한다.
마진은 유클리드 기하학의 언어로 결정경계의 근방영역을 정의한다.
마진이 넓을 수록 결정경계 근방에 위치하게 될 테스트 데이터에 대해 유연하게 대처할 수 있게 된다.
마진 최대화 문제는 수학적으로 최적화 이론의 언어를 이용해 정의할 수 있으며, 해석적인 방법 또는 경사하강법(Gradient descent)을 이용하여 최적해를 구할 수 있다.

다음 포스팅부터는 마진의 개념을 다루어보도록 하겠다.

📌 요약 Summary

  • 선형이진분류 문제는 선형결정경계로 두 가지 클래스의 데이터를 분류하는 문제다.
  • 서포트 벡터 머신은 선형이진분류 문제를 풀기 위한 선형 분류기이다.
  • 서포트 벡터 머신은 기하학적 개념을 이용하여 여러 결정경계 중 마진을 최대로 하는 결정경계를 선택하는 전략을 취한다.

연습문제 1)
벡터 β\beta가 초평면 {xRd:f(x)=xTβ+β0=0}\left\{x \in \mathbb{R}^d : f(x) = x^T \beta + \beta_0 = 0\right\}와 수직임을 보여라.

Solution)

초평면 위의 임의의 두 점 xax_a, xbx_b에 대하여, 초평면 위의 위치벡터 xaxbx_a - x_b를 생각하자.

이때 초평면의 정의에 의해 f(xa)=0,f(xb)=0f(x_a) = 0, f(x_b) = 0이이다.

한편, f(xa)f(xb)=(xaTβ+β0)(xbTβ+β0)=(xaxb)Tβf(x_a) - f(x_b) = (x_a^T\beta + \beta_0) - (x_b^T\beta + \beta_0) = (x_a - x_b)^T\beta가 성립하므로 (xaxb)Tβ=0(x_a - x_b)^T\beta = 0임을 얻는다.

따라서 β\beta는 초평면 위의 임의의 위치벡터에 대하여 수직이다.

profile
TDA와 DL을 연구하는 대학원생입니다.

0개의 댓글