| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
서포트 벡터 머신(영어: Support Vector Machine, 약칭: SVM)은 데이터 마이닝 기법 및 인공지능에 쓰이는 대표적인 알고리즘 중 하나다.SVM은 분류 알고리즘 중에 하나로 분류율이 좋은 알고리즘이다. 일반적으로 분류 알고리즘이라고 하면 Decision Tree, 인공신경망 등의 알고리즘이 존재하는데, SVM은 이 둘에 비해서 데이터, 특히 이진 데이터(binary data)를 분류(classification)하는 데 더 나은 성능을 보인다. 일반적으로 선형, 비선형 알고리즘 두 가지 종류가 존재한다.
2. 데이터 분류
2.1. 선형 모델
SVM은 데이터를 분류하는 초평면(hyperplane)을 구하는 알고리즘이다. 예를 들어, A와 B 두 개의 예측 변수로 구성되어 있고, 0과 1의 결과 변수를 갖는 2차원의 데이터셋를 상상해보자.A(2,1)라는 벡터가 결과변수가 1, B(3,4)라는 벡터가 결과변수가 0이고, 이들 벡터의 위치가 각자가 대표하는 군집의 최전선에 존재한다면, 이들을 기반으로 동일한 거리에 떨어져 있는 한 가운데에 초평면을 긋는 것이 합리적일 것이다. 이런 벡터를 서포트 벡터라고 부르는데, 서포트 벡터 머신이라는 명칭은 여기서 유래된 것이다. SVM은 초평면을 긋는데 기여하는 서포트 벡터만 골라내서, 초평면과 서포트 벡터와의 거리가 최대가 되도록 초평면을 긋는 방법을 찾는다.
초평면 Ax+By+Cz+D = 0가 존재할 때, 법선벡터 (A,B,C)는 이 초평면과 직교한다. 그리고, 0과 1의 군집을 분류하는 최전선에 존재하는 벡터(서포트 벡터)를 지나는 초평면이 존재한다고 가정할 때, 이 초평면은 [math(Ax + By + Cz + D = E)]일 것이다. 한편, 이 E는 우리가 임의로 정한 상수이므로, 같은 E로 나누어서 1로 만들어도 역시 같은 상수이다. 따라서, 분류 초평면으로부터 E만큼 떨어져 있는 "서포트 벡터를 지나가는 초평면"은 [math(Ax+By+Cz+D = 1)]로 표현할 수 있다. 분류 초평면이 아닌, 서포트벡터를 지나가는 이 초평면을 "마진"이라고 부른다. 마진은 결과변수가 1인 군집쪽에 1만큼 떨어져 있고, 결과변수가 0인 군집 쪽에 -1만큼 떨어져 있는 두개의 마진이 존재한다.(플러스 마진, 마이너스 마진)
이제 문제는 법선벡터(A,B,C)와 상수 D를 구하는 것이다.
1) 플러스 마진만을 생각했을 때, 플러스 마진을 넘어서는 케이스들은 모두 +1의 값을 가진 것이다. 즉, [math(Ax+By+Cz+D \ge 1)]이 될 것이다.
2) 마이너스 마진만을 생각했을 때, 마이너스 마진을 넘어서는 케이스들은 모두 -1의 값을 가질 것이다. 즉, [math(Ax+By+Cz+D \le -1)]이 될 것이다.
이는 초평면을 구하는 제약식이 되는데, 이 두개의 제약식을 하나로 묶어버리면 다음과 같은 제약식을 얻을 수 있다. 앞서, (초평면) >= 1인 케이스들은 모두 +1의 값을 갖고, (초평면) <= -1인 케이스들은 모두 -1의 값을 가진다고 했으므로, 이 결과변수(y)를 이용하여 두개의 제약식을 하나로 묶으면
[math(y(Ax+By+Cz +D) \ge 1)] 로 변환할 수 있다.
[math(y(Ax+By+Cz +D))]
한편, 앞에서 언급하였던 법선벡터를 그 자신의 크기(norm)로 나누면 크기가 1인 단위벡터로 바뀌는데, 이 단위벡터와 플러스 (마진상의) 벡터와, 마이너스 (마진상의)벡터 사이의 거리를 내적하면 단위벡터 크기로 축소된 마진간 거리가 나온다.
법선벡터*(플러스 벡터 - 마이너스 벡터)
한편, 앞서 살펴봤던 플러스 마진의 정의에서 플러스 벡터는 Ax+By+Cx+D = 1에 위치하는 벡터로 정의할 수 있으므로,
[math(Ax+By+Cz = 1-D)]
마찬가지로 마니어스 마진상에 위치하는 마이너스 벡터도
[math(Ax+By+Cz = -1-D)]
이를 앞에서 설명한 내적의 식에 대입하면
법선벡터 * (플러스벡터 - 마이너스 벡터) = 법선벡터*(1-D-1-D) = 2 / 법선벡터의 norm
결국, 플러스 벡터와 마이너스 벡터의 거리는 2/norm으로 정리할 수 있으며, 이제부터는 2/norm을 최적화(max)하는 문제를 풀면 된다.
라그랑주 승수법을 이용하면 되는데, 이 기법을 이용하기 위해서 max(2/norm)을 잠시 min(norm^2)로 바꾸면
목적함수 : [math(\min(\operatorname{norm}^2))]
제약식 : [math(y(Ax+By+Cz+D) \ge 1)]
이를 보조함수로 다시 정리하면
[math(L(\operatorname{norm}, a, D) = \min(\operatorname{norm}^2) + a(y(Ax+By+Cz+D))]
한편, 여기서 A,B,C는 법선벡터의 요소값이다. 이를 w로 묶어낸다면
[math(Ax + By + Cz + D = W^T \cdot x)] (단, [math(T)]는 벡터의 전치, [math(\cdot)]는 내적)
다시 정리하면
[math(L(\operatorname{norm}, a, D) = \min(\operatorname{norm}^2) +\operatorname{sig}(a(y(Wt*x+D-)))]
제약식이 부등호이므로, 이 문제를 풀기 위해 KKT 조건을 사용한다. KKT조건에서는 모든 미지수에 대하여 편미분한 값이 0이어야 한다. 미지수인 norm과, D를 편미분하면 다음과 같은 두개의 방정식을 얻을 수 있다.
(1) w에 대해 편미분 : sig(ayx)
(2) D에 대해 편미분 : sig(ay)
이 둘을 연립하면 a값을 얻을 수 있다. 한편, 앞에서 살펴봤던 KKT조건은 제약식 a(y(Wt*X+D))의 경우 두 미지수 중 하나만 0일 것을 요구한다. 따라서
(1) 라그랑주 승수 [math(a = 0)]일 경우, [math(y(Wt*X+D-1))]는 0이 아니다.
(2) 라그랑주 승수 [math(a \ne 0)] 일 경우, [math(y(Wt*X+D-1))]는 0이다.
즉, 초평면 상에 위치하지 않은 벡터의 경우 라그랑주 승수 [math(a = 0)]이 되기 때문에 무시되며, 초평면 상에 위치할경우 라그랑주 승수 [math(a \ne 0)]이 된다. KKT 조건을 통해 서포트 벡터를 자동으로 골라낼 수 있게 됐다.
2.2. 비선형 모델과 커널 함수
비선형 데이터의 분류 문제를 분류할 때 가장 손쉬운 방법은 데이터를 보다 고차원의 공간으로 매핑하는 것이다. 2차원의 경우와 3차원의 경우를 생각해 보자. 2차원의 경우는 데이터간 거리 정보를 두 개 밖에 가지지 못한다.(x,y의 거리) 하지만, 이 데이터를 3차원으로 선형변환 시킬 경우 한가지 데이터가 더 추가된다(x,y,z) 마찬가지로, 좀 더 고차원의 공간으로 변환만 시킬 수 있다면 데이터를 더 잘 분류할 수 있을 것이다.이를 처리하는 방법은 1) 변수들을 특성 공학을 통해 뻥튀기시켜 차원을 늘린다. 2) 함수 자체적으로 무한개의 차원으로 데이터를 매핑한다.
1)은 어떤 변수를 어떤 방식으로 뻥튀기 시켜야하는지 애매한 경우가 많다. 따라서 보통 2)의 방법을 쓰는데, 이때 쓰이는 함수를 커널 함수라고 부른다.
커널 함수 중 하나인 RBF의 경우는 가우시안 분포의 확률밀도함수를 테일러 급수를 이용하여 무한개의 확률밀도함수의 합으로 뻥튀기 시키는데, 이는 무한 차원의 공간에 데이터를 매핑시키는것과 동일한 효과를 가진다.
SVM은 초평면(hyperplane)이라는 개념을 사용해서 데이터를 분류한다. 예를 들어서, n차원과 n+1차원이 존재하며 데이터들이 n차원에 있다고 하자. SVM은 n차원을 n+1차원으로 만든 후, 기존에 n차원에 존재했던 데이터들을 n+1차원으로 보내서 데이터를 분류한다.