본문 바로가기

ML & DM/SVM

SVM (Support Vector Machine) Part 2

3. 슬랙변수를 가진 SVM (혹은 Soft Margin SVM)






위 그림과 같이 학습데이터가 선형분리 가능한 경우에 대해 알아보자. 위 처럼 선형분리가 되지 않고 잘못 분류되는 데이터가 존재하는데 이를 처리하기 위해 먼저 잘못 분류된 데이터로부터 해당 클래스의 결정 경계까지의 거리를 나타내는 슬랙변수를 도입한다. 


위 조건은 해당 클래스(+ 또는 -)에 속하는 모든 데이터들은 엄격하게 +또는 -평면보다 윗부분 혹은 아랫부분에 존재해야 한다는 것임에 반해, 슬랙변수를 추가함으로써 클래스에 속하는 데이터가 플러스(마이너스)평면보다 만큼 아래(윗)부분에 존재할 수 있도록 허용하게 된다. 따라서 이 클수록 더 심한 오분류를 허용함을 의미한다. 이러한 의미를 가진 슬랙변수를 추가한 분류조건을 통합하여 나타낸 식이 아래식이다.



슬랙변수를 추가한 분류조건을 만족하고 마진을 최대화 하는 파라미터를 찾기위해 목적함수를 다음과같이 정의한다.



이 함수를 최소화 하는 동시에 다음의 제약조건을 만족해야 한다.



목적 함수에서 슬랙변수에 의존하는 항  는 의 값을 되도록 최소화하여 오분류의 허용도를 낮추기 위해 추가되었다. c는 최소화조건을 반영하는 정도를 졀정하는 값으로 사용자가 적절히 정해주어야 한다. c값이 크면 덩달아 전체 마진도 커지므로 오분류를 적게 허용(엄격)한다는 뜻이고 반대로 c값이 작으면 마진이 작아지므로 비교적 높은 오분류를 허용(관대)한다는 뜻이다. 

이제 목적함수와 조건식이 주어졌으므로 라그랑주 승수를 이용하여 표현하면 다음과 같다.



이는 에 슬랙변수에 의존하는 항 와 슬랙변수를 양의 값으로 유지하기 위한 새로운 라그랑제 승수 를 포함하는 항 이 마지막에 추가 되었다. 이제 파트 1에서 와 같이 이원 문제를 찾으면서 다음 함수를 얻을 수 있다.



또한 부등식 제약조건이 있는 라그랑주의 KKT 조건에 의해 다음 조건을 만족해야 한다.



파트1 에서 한것처럼 이차계획법으로 라그랑제 승수를 찾을 수 있으며 나머지 파라미터도 다음과 같이 추정할 수 있다.




식에서도 알수 있듯 일단 라그랑제 승수만 정해지면 전과 마찬가지로 동일한 분류함수에 의해 분류가 가능하다. 



약간의 오분류를 허용하는 선형 판별경계를 찾는 Soft Margin SVM 은 특징적으로는 최대마진 분류기와 동일하다. 일부 데이터가 선형으로 예측할 수 없는 상황에서 슬랙변수를 써서 이를 선형으로 예측할 수 있게 하였으나. 애초에 데이터의 특성상 데이터 클래스 사이의 경계가 선형성이 없는경우에는 이마저도 쓸수가 없다. 따라서 이러한 비선형 판별경계를 갖는 데이터를 선형판별경계로 분류하게 만드는 방법이 있는데, 이것이 바로 커널법이다.


4. 커널법을 활용한 Soft Margin SVM



위의 데이터 분포에서는 초평면 자체가 없기 때문에 우리는 아예 슬랙변수조차 쓸수가 없다. 이러한 비선형 분류 문제를 해결하기 위해서 저차원의 입력 x를 보다 고차원의 공간 값 으로 매핑시키는 함수를 생각 할 수 있다. 

  


2차원 공간상에서는 두 클래스는 원형의 결정경계를 가지는 비선형 문제 였지만, 이것을 3차원 공간으로 보냄으로써 선형 평면으로 분류가 가능한 선형 문제로 변화 되었다.


입력데이터의 차원을 높임으로써 문제를 선형화하면 간단한 선형 분류기를 사용하여 분류를 수행할 수 있는 반면, 차원수를 높였기 때문에 발생하는 계산량 증가와 같은 부작용도 고려를 해야하는데. 이러한 부작용을 해결하기 위해 제안된 방법이 커널법이다.

으로 매핑시킨 두개(+,-)의 고차원 벡터를 그냥 내적하여 계산하면 계산비용이 많이 든다. 여기서 우리는 각 고차원 벡터가 선형분포로 어떻게 구체적으로 매핑이 되는지 정의하지 않고, 각 고차원 벡터가 선형분포로 매핑이 된다는 가정을 해보자. 각 고차원 벡터가 선형분포를 따르므로 둘의 내적도 반드시 선형분포를 따를 것이다. 따라서 우리는 두 내적공간만 정의를 해주어 선형판별경계를 찾을 수 있는것이다. 이때의 정의된 내적함수를 커널함수라고 부르며, 정의는 다음과 같다.



이러한 커널함수를 사용하면 고차원의 벡터를 이용한 연산 없이 본래의 저차원에서 계산만으로 값이 얻어지므로 계산비용문제를 해결 할 수 있다. 이러한 커널트릭

을 적용한 라그랑주 함수는 다음과 같다.



판별 경계는 다음과 같다.



임의의 테스트 데이터에 대한 판별값은 다음과 같다.



이렇게 고차원 매핑을 통해 비선형 문제를 선형화 하여 해결하면서, 커널함수를 통해 계산량 증가의 문제를 해결하는 방법을 커널법 혹은 커널트릭이라고 하며 SVM을 비롯해 선형성을 가정하는 방법론에서 활발히 사용되고 있다.

몇가지 대표적인 커널 함수로는 선형커널, 다항식커널, 시그모이드커널, 가우시안커널이 있다.



각 커널 함수는 고유의 파라미터(다항식 커널의 r과 d , 시그모이드커널의 r 등)를 가지고 있으며 이것은 문제의 성격에 맞추어 적절히 조정해주어야 하는 하이퍼파라미터이다.


참고문헌 : http://deepcumen.com/2015/04/support-vector-machine/

'ML & DM > SVM' 카테고리의 다른 글

SVM (Support Vector Machine) Part 1  (1) 2016.03.07