서포트 벡터 머신
서포트 벡터 머신(, SVM기계 학습의 분야 중 하나로 패턴 인식, 자료 분석을 위한 지도 학습 모델이며, 주로 분류와 회귀 분석을 위해 사용한다.
두 카테고리 중 어느 하나에 속한 데이터의 집합이 주어졌을 때, SVM 알고리즘은 주어진 데이터 집합을 바탕으로 하여 새로운 데이터가 어느 카테고리에 속할지 판단하는 비확률적 이진 선형 분류 모델을 만든다.
만들어진 분류 모델은 데이터가 사상된 공간에서 경계로 표현되는데 SVM 알고리즘은 그 중 가장 큰 폭을 가진 경계를 찾는 알고리즘이다.
SVM은 선형 분류와 더불어 비선형 분류에서도 사용될 수 있다. 비선형 분류를 하기 위해서 주어진 데이터를 고차원 특징 공간으로 사상하는 작업이 필요한데, 이를 효율적으로 하기 위해 커널 트릭을 사용하기도 한다.
일반적으로, 서포트 벡터 머신은 분류 또는 회귀 분석에 사용 가능한 초평면() 또는 초평면들의 집합으로 구성되어 있다. 직관적으로, 초평면이 가장 가까운 학습 데이터 점과 큰 차이를 가지고 있으면 분류 오차()가 작기 때문에 좋은 분류를 위해서는 어떤 분류된 점에 대해서 가장 가까운 학습 데이터와 가장 먼 거리를 가지는 초평면을 찾아야 한다.
일반적으로 초기의 문제가 유한 차원 공간에서 다루어지는데, 종종 데이터가 선형 구분이 되지 않는 문제가 발생한다. 이러한 문제를 해결하기 위해 초기 문제의 유한 차원에서 더 높은 차원으로 대응시켜 분리를 쉽게 하는 방법이 제안되었다. 그 과정에서 계산량이 늘어나는 것을 막기 위해서, 각 문제에 적절한 커널 함수 formula_1를 정의한 SVM 구조를 설계하여 내적 연산을 초기 문제의 변수들을 사용해서 효과적으로 계산할 수 있도록 한다.
높은 차원 공간의 초평면은 점들의 집합과 상수 벡터의 내적 연산으로 정의된다. 초평면에 정의된 벡터들은 데이터 베이스 안에 나타나는 이미지 벡터 매개 변수들과의 선형적 결합이 되도록 선택된다. 이 선택된 초평면에서, 초평면에 대응된 점 formula_2는 다음과 같은 관계가 성립한다.
만약 formula_1가 formula_2 와 formula_6가 점점 멀어질 수록 작아진다면, 각각의 합은 테스트 점 formula_2와 그와 대응되는 데이터 점formula_8의 근접성의 정도를 나타내게 된다. 이러한 방식으로, 위 커널식의 합은 구별하고 싶은 집합안에 있는 데이터 점과 테스트 점간의 상대적인 근접성을 측정하는데 사용될 수 있다. 초기 공간에서 볼록하지 않는 집합안의 점 formula_2가 높은 차원으로 대응되었을 때 오히려 더 복잡하고 어려워질 수도 있는데 이런 부분을 주의해야 한다.
데이터를 분류하는것은 기계학습에 있어서 일반적인 작업이다. 주어진 데이터 점들이 두 개의 클래스 안에 각각 속해 있다고 가정했을 때, 새로운 데이터 점이 두 클래스 중 어느 곳에 속하는지 결정하는 것이 목표이다.
서포트 벡터 머신에서, 데이터 점이 formula_10-차원의 벡터 (formula_10개의 숫자 리스트)로 주어졌을 때, 이러한 데이터 점을 formula_12-차원의 초평면으로 분류할 수 있는지를 확인하고 싶은 것이다.
이러한 작업을 선형 분류라고 말한다.
데이터를 분류하는 초평면은 여러 경우가 나올 수 있다. 초평면을 선택하는 타당한 방법 중 하나는 두 클래스 사이에서 가장 큰 분류 또는 마진(margin)을 가지는 초평면을 선택하는 것이다. 그래서 우리는 초평면에서 가장 가까운 각 클래스의 데이터 점들 간의 거리를 최대로 하는 초평면을 선택한다. 만약 그런 초평면이 존재할 경우, 그 초평면을 최대-마진 초평면() 이라 하고 선형 분류기를 최대-마진 분류기()라고 한다.
주어진 학습용 데이터 집합 D(N 개의 점으로 이루어진 집합)를 다음과 같이 정의해보자.
각 formula_14 는 p차원의 실수 벡터이고 , formula_15 는 formula_14 가 어떤 클래스에 속해있는지를 나타내는 값으로 1 혹은 -1의 값을 가진다.
위의 학습용 데이터 집합이 formula_15값에 따라 선형적으로 분리될 수 있을 때, 데이터 집합을 분리하는 것을 초평면이라 하며 다음의 조건을 만족하는 점 X의 집합으로 나타낼 수 있다.
formula_19 은 내적 연산자이고, formula_20은 초평면의 법선 벡터(normal vector)이다.
주어진 초평면의 서포트 벡터(formula_21, formula_21)는 다음과 같이 정의된다.
주어진 초평면과 같은 법선벡터를 가지면서 formula_21 를 지나는 초평면은
으로 나타낼 수 있고 비슷한 방식으로 formula_21 를 지나는 초평면은
이와 같이 나타낸다.
초평면의 마진은 각 서포트 벡터를 지나는 초평면 사이의 거리를 의미한다.
기하학적으로 두 초평면 사이의 거리 즉, 마진을 구하면 formula_31라는 것을 알 수 있으며 서포트벡터머신은 마진을 최대로 만드는 알고리즘이다.
서포트벡터를 지나는 초평면 사이엔 데이터 포인트가 존재하지 않아야 하므로 다음과 같은 식이 성립한다.
위 두 식은 아래와 같은 식으로 나타낼 수 있다.
초평면의 조건을 따르며 마진의 최댓값을 구하고자 하는 서포트 벡터 머신 문제는 다음과 같은 최적화 문제로 표현할 수 있다.
위에서 설명한 최적화 문제는 formula_41의 노름인 formula_42이 제곱근을 포함하고 있기 때문에 풀기 어렵다. 위의 최적화 문제에서 formula_42를 formula_44로 치환하여도 최적화 문제를 만족시키는 해 formula_41, formula_46는 변하지 않는다. 또한 formula_44로 치환을 하게 되면 위의 문제는 2차 계획법() 최적화 문제가 된다. 치환된 최적화 문제는 아래와 같이 나타낼 수 있다.
라그랑주 승수법을 이용하면 위의 문제를 다음과 같은 안장점()을 찾는 문제로 나타낼 수 있다.
안장점을 찾는 과정에서 formula_51으로 분류될 수 있는 모든 점들은 그에 대응하는 formula_52가 0으로 지정되기 때문에 영향을 미치지 않는다.
이제 이 문제는 정규 2차 계획법 기법으로 해결할 수 있다. 정적 Karush-Kuhn-Tucker 조건에 따르면, 문제의 해는 훈련 벡터()의 선형 조합으로 표현될 수 있다.
적은 수의 formula_52만이 0보다 큰 값을 가지고, 그에 대응하는 formula_55들은 formula_56를 만족하는 정확한 서포트 벡터이다. 이 식을 통해 다음과 같이 오프셋_(컴퓨터_과학) formula_46에 대한 정의를 유도할 수 있다.
formula_46는 formula_15와 formula_8에 의존하므로 각각의 데이터 포인트마다 값이 다르다. 표본 분포의 평균은 모평균(population mean)에 대해 불편 추정량()이므로 다음과 같이 모든 서포트 벡터 formula_62에 대해서 평균을 취하는 것이 좋다.
분류 규칙을 비제약 쌍대 형식으로 나타내면, 최대 마진 초평면과 분류 작업이 오직 마진 위에 놓여있는 서포트 벡터들로부터만 영향을 받는다는 것을 알 수 있다. formula_64에서 formula_53로 치환하면 SVM의 쌍대 형식이 다음과 같은 최적화 문제로 바뀐다.
여기서 formula_68는 formula_46를 최소화하는 과정에서 생기는 제약이다.
커널은 formula_70로 정의된다.
formula_41는 formula_72 항에 의해서 계산될 수 있다:
필요에 의해서 초평면이 좌표계의 원점을 지나야하는 경우가 존재한다. 이때 원점을 지나는 초평면을 비편향된 초평면이라 말하며, 그렇지 않은 초평면은 편향된 초평면이라 말한다. 원 형식에선 formula_74의 조건을 줌으로써 비편향된 초평면을 구할 수 있고, 이에 대응되는 쌍대 형식은 위에서 제시된 쌍대 형식에서 formula_75의 조건을 풀어줌으로써 구할 수 있다.
1995년에 Corinna Cortes와 Vladimir N. Vapnik은 잘못 분류된 자료들을 허용하는 변형된 최대 마진 분류기 아이디어를 제안했다. 만약 “네” 또는 “아니오”라는 결과를 내야하는 자료들을 분할하는 초평면이 존재하지 않는다고 하자. 그러면 소프트 마진 방법은 여전히 가장 가까이 위치해 있는 제대로 분리되는 자료들의 거리를 최대화하면서, 주어진 자료들을 가능한 한 제대로 분리하는 초평면을 찾을 것이다. 이 방법은 음수가 아닌 느슨한 변수() formula_76를 이용하는데, 이 변수는 자료 formula_8가 잘못 분류된 정도를 나타낸다.
그러면 목적함수는 0이 아닌 formula_76에 대해 페널티를 부과하는 함수에 의해서 증가된다. 그에 따른 최적화는 마진을 크게 하는 것과 에러에 대한 페널티를 작게 하는 것의 균형을 맞추는 것이 된다. 만약 페널티를 부과하는 함수가 선형이라면, 최적화 문제는 다음과 같이 된다.
다변수 적응 회귀 스플라인()에서와 같이 경첩 함수() 표기법을 이용하면, 이 최적화 문제는 다음과 같이 쓰일 수 있다.
(2)에서의 제약조건은 목적함수에서 formula_42를 최소화하는 것과 함께 라그랑주 승수법을 이용하여 위에서와 마찬가지로 해결될 수 있다. 그러면 다음의 문제를 해결해야 한다.
선형 페널티 함수의 핵심 장점은 상수 "C"가 오직 라그랑주 승수법의 추가적인 제약조건에 등장함으로써, 듀얼 문제에서는 느슨한 변수가 사라진다는 점이다. 위의 공식화와 이것의 실제상황에서 미치는 큰 영향에 대해서 Cortes와 Vapnik은 2008년에 ACM Paris Kanellakis Award를 수상하였다. 비선형 페널티 함수들도 특히 분류기에서 이상치()의 효과를 줄이는데 사용되고 있다. 그러나 이를 사용하는데 주의를 기울이지 않는다면 문제는 볼록하지 않게() 되고, 그러면 이는 전역해()를 찾는데 상당히 어려운 문제가 된다.
최적의 초평면을 구하는 알고리즘의 시초는 1963년도 vapnik이 제안한 선형 분류였다.
하지만 1992년에 Bernhard E. Boser, Isabelle M. Guyon and Vladimir N. Vapnik 이 최대 마진 초평면 문제에 커널 트릭을 적용해서 비선형 분류를 제안하였다. 비선형 분류 알고리즘은 기존의 선형 분류 알고리즘과 형태상으로 비슷하지만 내적 연산이 비선형 커널 함수로 대체된다. 이를 통해 변환된 특징 공간 (feature space)의 최대 마진 초평면 문제 해결을 할 수 있었다. 여기서 말하는 변환은 비선형 변환이거나 차원을 높이는 변환이 될 수 있다. 즉, 분류기는 고차원 특징 공간에서 선형 초평면이지만 기존 차원 공간 상에선 비선형 초평면이 된다. 만약 가우시안 방사 기저함수 (Gaussian radial basis function) 를 커널 함수를 적용한다면 특징 공간은 무한 차원의 힐버트 공간(Hilbert space)이 된다.
최대 마진 분류는 많은 연구를 통해 조정되어왔다. 또한 고차원 공간을 이용한 분류는 기존 공간에서의 잘못된 분류 결과를 내지는 않을 것이라고 생각되어왔다. 하지만 고차원 공간에서의 분류는 기존 공간에서의 분류 일반화의 오차를 상승시킨다는 것이 증명되었고 그 상승 폭에 대한 임계 값이 있다는 것 역시 알려져 있다.
다음과 같은 일반적인 커널들이 있다.커널은 변환 formula_100와 다음과 같이 연관되어 있다. formula_101.
w의 값 또한 변환된 공간에 다음과 같이 존재한다. formula_102.
분류를 위해서 w와 내적을 구할 때는 다음과 같은 커널 트릭을 이용해 계산할 수 있다. formula_103.
하지만, 일반적인 경우에 formula_104를 만족하는 w'는 존재하지 않는다.
SVM은 다음과 같은 현실 세계의 문제들을 해결하는데 사용된다:
여러 프로그래밍 언어에 지원되는 서포트 벡터 머신 라이브러리 목록