Support Vector Machine(1)

이번장에서는 Support vector machine에서 classification을 다룬 방법에 대해 알아본다.

 

로지스틱 회귀나 나이브 베이즈는 확률론적 접근으로 class를 할당했고, 의사결정나무는 rule 기반으로 class를 할당했다. 

 

SVM은 decision boundary를 찾아서 class간 경계를 만드는 방법이다.

기본적인 가정은 최적의 decision boundary를 찾는 것이다. 아래에서는 이진 클래스에 대해 분리를 한다. 이 클래스를 잘 구분지어줄 경계를 찾는 것이 목표이다. 

 데이터들이 주어졌을 때, 그을 수 있는 선은 무수히 많다. 아래의 H3 처럼 좋은 경계선을 찾아야 한다. H2 처럼 다 나눌수는 있지만 H2와 H3 중 어떤게 더 좋은 건지도 구분해야 한다. 

 

 

SVM에서는 class boundary를 평행이동 시키다보면 각 클래스에 속하는 점을 만나게 되고, 검은점과 하얀점에 딱 맞닿는 경계에서의 사이의 거리를 최대한 멀리 떨어지게끔 할 수 있다. 이 때를 가장 좋은 경계라고 한다. margin 부분을 최대화 하는 것이 목표이다.

 

 

 

아래의 y = ax + b 에서 파란색 경계가 움직이면 a,b 가 달라지면서 이동을 하게 될텐데, SVM에서는 w벡터(법선벡터)를 정의한다. 

 class boundary에 대한 표현은 어떻게 할 것이냐? y = ax + b 방정식이 경계라 하면 그림 오른쪽에 처럼 wx - b = 0 의 꼴로 유도가 될 수 있다. 두 벡터의 내적의 값이 0이면 두 벡터는 서로 직교한다는 성질을 이용한 것이다.

 여기서 벡터 x는 방정식에 있는 모든 좌표점들을 벡터로 표현한 것이고, w는 (-a, 1)으로 표현이 되게 된다.

 

 

 

이제 법선벡터를 활용해서 margin의 길이를 계산해 보도록 하자. 경계 3개 중 가운데 진한 파란색 경계는 wx = 0 으로 나타내는데, w는 경계에 대한 법선벡터를 나타내고, x는 파란점들을 구성하는 좌표들을 가지고 있는 벡터이다. 그러면 w 와x의 내적이 0임을 나타낼 수 있다.

 그리고 이 실선은 y축으로 1, -1만큼씩 평행이동을 시킨 것이 점선으로 표시된 부분이다. 이 때 그림처럼 margin이 $l$ 이라 하면 가운데 실선에서 각 점선까지의 margin은 2 x $l$로 2$l$ 이 된다. 이 때, $l$ 은 w의 길이 분의 1이 된다.

그렇다면 그 $l$ 이라는 것을 어떻게 구할 수 있을까? 

아래의 다른 예시를 보자. 먼저 $wx - b = 0$ 의 법선벡터는 $w$ 라고 하였다. 이 때, $w$ 벡터의 좌표를 $(a_{1}, a_{2})$ 라고 한다면, 아래 수식 첫번 째 처럼 표현이 가능하고, 점선이 $(0, 0)$ 을 지나기 때문에 $(a_{1}, a_{2})$ 와 $(0, 0)$ 두 좌표를 이용해서 방정식을 만들면 $y = \frac{(a_{2} - 0)}{(a_{1} - 0)} x$ 를 계산하여 $a_{2}x - a_{1}y = 0$ 로 표현하게 된다. 

 $wx - b = 0$ 도 $w$ 가 $(a_{1}, a_{2})$ 라 했으니 다시 표현해보면, $a_{1}x + a_{2}y - b = 0$ 로 표현 가능하다.

그리하여 원점과 $w$ 사이의 좌표로 만든 $a_{2}x - a_{1}y = 0$ 식과 실선을 방정식으로 만든 $a_{1}x + a_{2}y - b = 0$ 의 교점을 구하면 된다. 😜

 교점$(x_{0}, y_{0})$은 연립방정식으로 x 에 y를 정리한 식을 대입, y 에 x를 정리한 식을 대입하면서 각각 x, y에 대해 정리하여 좌표를 구한다. 그렇게 되면 아래의 Intersection처럼 좌표를 얻을 수 있다. 

 (0, 0)과 교점 사이의 유클리디안 거리는 아래의 Distance와 같으며, 최종적으로 $\frac{|b|}{||w||}$ 를 확인할 수 있다.

 앞전에서 $l$ 에 분자가 |1| 이였던 것은 위에서는 b 값이 1이 였기 때문이다.

 

 

또 다르게 거리를 구하는 방법에 대해 알아보자. 

이번에는 사영(projection)개념을 사용한다. 노란색 벡터 $v$를 법선벡터 $w$에 사영을 시키면 그 사영시킨 벡터의 길이를 알 수 있게 된다. 사영을 시키는 것은 dot product를 구하는 것과 동일해지게 된다. 

 $v$ 벡터와 $w$벡터 사이에 사영을 시키면 되는데, $w$ 벡터가 방향만 고려한다하면 단위길이로 맞춰주기만 하면 전과 동일한 수식을 얻을 수 있게 된다. 

 

앞에서는 임의로 넣었는데, 아래와 그림과 같이 intersection되는 부분이 1, -1이 아니라 하더라도 사실상 같다. margin의 길이가 중요한건데, margin의 길이는 intersection엔 영향을 받지 않는다. 평행이동 시켜서 경계가 모든 데이터들을 옮겨서 평행이동시켜서 경계가 0,0을 지나게만 만들어주면 길이가 전혀 변하지 않게 되는 거라서 이와 같은 형태로 margin을 구할 수 있게 된다. 기본적으로 앞에서 처럼 w를 구하고 나서 w 길이 분의 2 로 결정이 된다고 생각하면 된다.

앞에서는 실선은 위아래로 1, -1 평행이동 시킨 것을 가정했는데, 그게 정말 1과 -1이 아니라면? 그게 별로 중요한게 아닌게 우리는 w를 구할 때 경계의 방향이 중요하다. intersection이나 각도를 바꿨을 때, 어떤 각도로 경계를 설정하느냐가 중요하지 b가 얼마냐는 margin을 결정하는데 크게 중요하지 않다. 

 w에 대한 길이를 제한함으로써 1, -1로 해도 b는 알아서 맞춰지기 때문에 문제가 되지 않는다.

 

 

 

 최종적으로 우리는 아래의 그림과 같은 문제를 생각하게 된다. margin은 1 인데, b라는 것은 크게 중요하지 않다. 데이터는 고정되어 있고 w 길이를 제한할 것이기 때문이다. 그래서 기울기가 제일 중요하다. 기울기는 똑같은데 w길이를 2배 증가시키면 b도 똑같이 2배로 늘어날 뿐이기 때문이다. 여기서 w 벡터는 방향에 대한 정보만 가지고 있어서 w를 1로 어느정도 가정하고 풀게 된다. 그래서 아래의 그림에 2 x margin이 $\frac{2}{||w||}$로 나온다.

 여기서 가정은 하고 있는게 아래의 검은색 점은 위에 경계에 겹치거나 그 위에 있어야 하며, 아래의 흰 점은 아래의 경계에 겹치거나 그 밑에 위치해 있어야 한다는 것이다.

 아래에서는 제약조건(constraint)은 로지스틱 회귀 같은거랑 달리 class 의 label을 1 또는 -1 로 하게 된다. 그래서 class가 +1인 점들은 $wx - b \geq 1$을 만족해야하고, class가 -1인 점들은 $wx - b \leq -1$ 을 만족해야한다. Primal form에서 s.t. 부분을 보면 $y_{i}$를 붙여서 1일 때, -1일 때를 각 샘플하나하나 마다 판단할 수 있게 한다. 

 margin을 가장 최대화 하는 것이 목표라고 했는데, 이 $||w||$가 분모에 있으니 어차피 양수이니 편의를 위해 뒤짚어서 분자로 올리고 어차피 길이를 나타내기에 norm2의 제곱근도 제곱을 함으로써 없애주고 minize하는 방법을 사용한다. $\frac{1}{2}$같은 경우는 미분해서 해를 찾다보니까 미분했을 때 앞에 숫자가 1이 되기 위해 관습적으로 쓰는 것이다.

이렇게 Primal form을 알아보았다. 

 

 

 

 

이제 w 와 b 를 어떻게 찾을 수 있는지에 대해 알아보자.

그전에 잠깐 KKT(Karush-Kuhn-Tucker) 를 잠깐 보고 넘어가자. KKT conditions는 최적화를 하기 위한 어떤 조건 같은 것이다. Lagrange multiplier의 일반화된 방법이라고 생각하면 된다. Lagrange multiplier는 일종의 최적화 방법인데 min 문제를 푸는데 제약조건이 등식으로만 존재하는 제약조건만 있을 때 해를 구하는 방법이다. 등식뿐만아니라 부등식도 제약조건으로 존재할 수 있다.

그때 사용가능한 것이 아래의 방법이다. 우리의 목표는 x에 대해 함수를 최소화 시키는 것이 목표인데, x는 아래의 조건들을 만족해야하는데, 일반적인 형태이다. 부등식과 등식 조건이 있는 것을 볼 수 있다. 

 이 문제를 푸는 것보다 더 쉬운 문제로 바꿔서 최적화 문제를 푼다.

최적화된 함수 자체가 바뀐다. minimize문제가 min max문제로 바뀌며 새로운 parameter가 생성이 된다. $u, v$. 각각 제약조건에다가 각각 parameter를 하나씩 곱해서 선형결합한다음에 원래 최적화할 함수에다가 더해준다. $u,v$에 대해서는 최대화를 시켜주고, $x$에 대해서는 최소화를 시켜주는 x를 찾으면 위의 식을 풀때와 동일하다는 것은 이미 증명이 되어 있다.

Primal Form과 비교해보면, 이렇게 문제를 푸는 것을 Dual Form이라한다. 

이제 이 방법을 이용해서 새로운 목적함수를 도입한다. 

해를 찾기 위해서 원래 찾고자 하는 parameter w와 b, 그리고 새롭게 도입된 파라미터 $\alpha$에 대해서도 찾아줘야 한다. 최적화 문제는 local 이라 하더라도 그 지점에서는 기울기가 어쨌든 0이 되어야 한다. 

 

위의 $L(w, b, \alpha)$를 $w$에 대해 편미분을 하게 되면 $||w||^{2}$있는 term에서는 $w$만 남게 되고, 오른쪽에서는 일차식이니까 $w$는 사라지고, 앞에 있는 것들만 남게 되어 $\alpha, y$만 남게 된 것이 아래의 식으로 정리된 것이다.

마찬가지로 $b$에 대해서도 과정을 거치면 마찬가지로 아래 식중 두번째 식 처럼 나오게 된다.

w 를 아니 이제 집어 넣게 되면은 w, b는 사라지고 알파에 대한 수식만 남아 lagrange multiplier만 남은 수식으로 바꿀 수 있게 된다. 그래서 알파에 대한 max 문제로 바뀌게 된다. quadratic programming. !

 제약조건 두개로 이제 문제를 풀게 된다.

 

 

KKT나 lagrange multiplier는 primal form에서 변형을 하고, 최종적으로 lagrange 형태로 남은 dual form으로 문제를 더 쉽게 풀게 하는 것이다.

 

 

w 같은 경우는 α, y, x 모두 아니까 바로 구할 수가 있게 된다. w 식에서 왜 support vector machine이냐? α, y를 구해봤더니 대부분 다 0이고 몇몇 α, y 들만 0이 아닌 값들이 나오더라. 그래서 w 식에서 α, y가 0인 애들은 사용이 안되는데 그렇게 되면 α, y는 스칼라 값이고, $x$는 벡터니까, 우리가 가지.

0.

고 있는 $x$의 선형결합으로 w를 표현할 수 있는데, 그때 α, y가 0이 아닌 애들만 사용이 되니까 α, y가 0이 아닌 애들을 support vector라고 부른다.

α, y가 0이 아닌 벡터애들을 봤더니 위의 decision boundary에 걸친 검은 점이나 흰점들이 0이 아닌 값을 갖더라. 그래서 그러한 경계위에 있는 점들을 가지고 support vector라고 부르게 된다. 그리고 그 경계위에 있는 좌표들만 가지고 wx - b=-1 식에 대입하면 b 값을 역추산 할 수 있다. 다만 numerical 한 에러들이 있기 때문에 모든 support vector들에 대해 b를 구해서 평균치를 b로 취한다는 것이 아래의 두번째 b의 식이다.

 

그래서 최종적으로 각 데이터 포인트마다 surpport vector를 찾고 그 class 사이의 decision boundary를 b를 조절하여 결정을 하게 되는 방식이다. 

 

 

 

 

 

분류를 하다보면 아래와 같은 데이터도 충분히 등장할 수 있는데, 위의 과정대로 함수에 넣고 w, b를 구하고 서포트 벡터를 찾고 그러다보면 컴퓨터는 답이 없다고 말한다. 왜냐하면 아래의 두 class를 완벽하게 선형 경계로 나눌 수 없기 때문이다. 이런케이스는 soft margin 이라고 한다. 앞전에 했던 것들은 전부 hard margin 이었다.

 

 

그래서 아래와 같이 error를 정의하는 slack variable $ \xi $를 도입한다. 

 $ \xi $을 움직여야 하기 때문에 제약조건이 아래와 같이 바뀐다. $ \xi $ 는 오차 샘플들에 대한 허용을 위한 variable이다.

아래의 식은 마진을 최대화하고, 오차들의 합을 최소화한다. 아래에서 마진을 최대화할거냐 오차를 최소화 할거냐의 비율을 나타내는 것이 $C$ 의 역할.

 

마찬가지 형식으로 Lagrange 를 도입하여 진행하는건 거의 동일하다. 

마찬가지로 해를 찾기 위한 편미분 과정을 거치면, 

 

 

hard margin일 때와 비교했을 때 아래의 수식의 차이점은 $C$라는 제약조건이 추가 된다는 것.

 

 

최종적으로 w, b를 얻는 과정은 아래와 같다. 

 

hard margin에서는 α, y가 0 이 아닌 경우만 SV(support vector)로 사용을 하였는데, 여기에서는 α, y가 0 이 아니고 C인 경우(slack variable이 0이 아닌 점들)와 0과 C사이에 있는 경우를 알 수 있다. 

 b를 결정을 할 때는 unbounded SV만을 이용해서 위의 b 를 계산하게 된다.

 

 

새로운 데이터들이 들어온다면 어떻게 class를 할당할까. 

아래의 $f$ 함수 값을 계산해서 값이 0보다 크면 +1 class 0보다 작으면 -1 class로 정의를 하면 된다. 

 

 

 

이번엔 Nonlinear 인경우의 SVM의 작동 원리를 알아본다.

 

SVM은 앞서 얘기 했듯 2개의 class가 있을 때 margin을 정의하고 margin을 최대화하는 것이 목적이라 선형 경계만을 결정지었다. 비선형을 경계를 설정하는 것이 좋을 때가 있지 않은가.

 

그래서 사용하는 핵심적인 방법이 가지고 있던 데이터를 mapping 함수를 해서 고차원으로 보내버리는 방법이다. 이렇게 저차원에서 고차원으로 보내면서 공간이 넓어지고 밀도는 낮아지니, input space일 때 분리가 안될 때, 고차원으로 보내 선형으로 분리할 수 있게 된다. 이런 문제는 XOR문제라고 하며, 많이 알려져 있다.

고차원으로 보내기

 

 

추가적으로 Kernel function을 알아야한다. 여기 SVM 에서의 커널이라고 하면 이 함수의 정의는 input space에서의 좌표만 가지고 feature space상에서의 두 벡터의 dot product를 구해주는 함수이다. 커널 함수를 이용해서 dot product를 이용할때 훨씬더 효율적으로 계산할 수 있다. 

 아래의 그림처럼 커널 함수로 매핑을 하는 것이다.

SVN에서 사용하는 대표적인 커널 함수는 아래와 같다.

polynomial은 맵핑이 없고 x랑 x' 사이의 dot product하고 d제곱하여 스칼라 값을 내는 함수. 이고 두번째에 +1은 parameter로 받을 수 있는데 여기선 그냥 1로 적어둠.

가장 많이 쓰이는 것은 Gaussian kernel이 있다. scale를 조절해주기 위한 parameter 있을 수 있다. 

hyperbolic tangent kernel은 k와 c도 사용자가 조절하여 사용한다.

 

 

기존의 primal form 에서를 봤을 때 달라지는 건 별로 없다. x에 $\phi$ 함수를 적용한 것 뿐.

primal form

using kernel

마찬가지로 w도 x만 바뀐다.

 

 

Dual form에서도 역시 마찬가지이다. 

 

위에 x끼리 dot product 하는 부분이 보이는데 이를 $\phi$ 맵핑하면 된다. 

 

 그러면 최종적으로 아래와 같이 전과 비교해봐도 크게 다르지 않은 결과를 알 수 있게 된다. b 같은 경우에는 앞에 수식에서도 b가 dot product가 들어가 있기 때문에 kernel 함수로 대체되서 정확하게 구할 수가 있다. 

하지만 문제는 w 이다. w 경우에는 mapping 함수가 정의 안되면 feature상에서 정확한 hyper plane을 구할 수 없게 된다.

 

feature space상에서 경계를 지으려 하려면 x 대신 파이x로 바꾸고 나며 아래와 같이 식이 전개 된다. 즉 feature space상에서의 decision function 값은 계산할 수 있다. 이거 바탕으로 0을 기준으로 class를 할당가능하다. 이것이 kernel trick이다. kernel만 도입하면 classification을 할 수 있는 장점이 있다.

 

 

 

아래의 그림은 soft margin 케이스를 살펴보자. primal form 형태로 SVM을 진행하는 것이다.  아래 그림 가장 위에 식들은 objective function과 constraint를 나타낸다. 그리고 이것을 KKT condition 방법을 이용해서 lagrange multiplier를 도입해서 정의하게 되면 화살표 아래의 수식이 나오게 된다. 

그렇다면 만약 feature space 상에 적용한다하면 바뀌는 것은 바로 위의 케이스에서 x만 파이로 씌우주는 매핑만 해주면 된다.

 

그리고 Dual form 으로 만들어주기 위해서 $\alpha$들에 해당하는 값 같이 lagrange multiplier를 제외한 나머지 값들에 대해서는 전부 없애야 한다. 그렇게 하기 위해서 w에 대해 미분한 수식, b에 대해 미분한 수식, lagrange multiplier들에 대해 미분한 수식에 대해 만들어 주었다.  

정리를 하고 나면 동일하게 soft margin case도 hard margin case처럼 ODT function의 유일한 차이는 constraint에서 상한선(C)이 생기는것 이라 하였다.  quadratic programming으로 w, b 값을 다 계산 가능해 진다.

아래는 non linear의 경우이며 위의 linear의 경우와 마찬가지로 전개가 된다.

 

 

SVM 같은 경우에는 딥러닝 같은 알고리즘이 뜨기 전에 많이 쓰였던 알고리즘 중에 하나였다. 지금도 데이터가 엄청 많거나 하는 경우가 아니면, feature가 엄청 복잡한게 아니면 SVM classification하는 것도 사용할 만하다. 

 

SVM의 핵심은 Primal form 을 Dual form으로 바꾸고, non-linear을 풀기 위해 kernel trick을 사용한다는 것인데, regression이나 domain description 같은데는 formulation만 약간 바뀌게 되고, 그렇게 되면 다 쉽게 이해할 수 있다. 수식에 대한 설명이 거진 생략이 되었는데, support vector를 찾는다, 비선형 데이터 분포는 차원을 고차원으로 보내서 support vector를 찾는다 등 흐름이라도 잘 이해하면 좋다. 중간에 lagrange multiplier와 같은 최적화 풀이 기법은 실제로 풀이를 하는 건 수학적인 실력이 더 받쳐 줘야할 것 같다. 

결론은 SVM은 Linear Algebra + Vector calculus 의 끝판왕. !