문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류: 지도 학습]] == 개요 == Perceptron에서 Mediocore문제를 해결하기 위하여 마진이라는 개념을 이용하여 두 집단을 분류하는 방법론을 말한다. == 선형 SVM == 주어진 학습용 데이터 집합 D(N 개의 점으로 이루어진 집합)를 다음과 같이 정의해보자. :<math>\mathcal{D} = \{ (\mathbf{x}_i, y_i)|\mathbf{x}_i \in \mathbb{R}^p, y_i \in \{-1,1\}\}_{i=1}^n</math> 각 <math>\mathbf{x}_i</math> 는 p차원의 실수 벡터이고 , <math>y_i</math> 는 <math>\mathbf{x}_i</math> 가 어떤 클래스에 속해있는지를 나타내는 값으로 1 혹은 -1의 값을 가진다. 위의 학습용 데이터 집합이 <math>y_i</math>값에 따라 선형적으로 분리될 수 있을 때, 데이터 집합을 분리하는 것을 초평면이라 하며 다음의 조건을 만족하는 점 X의 집합으로 나타낼 수 있다. : <math>\mathbf{w}\cdot\mathbf{x} - b=0.\,</math> <math>\cdot</math> 은 [[내적]] 연산자이고, <math>{\mathbf{w}}</math>은 초평면의 [[법선 벡터]](normal vector)이다. 주어진 초평면의 서포트 벡터(<math>{\mathbf{X}}</math><sup>+</sup>, <math>{\mathbf{X}}</math><sup>-</sup>)는 다음과 같이 정의된다. :<math>{\mathbf{X}}</math><sup>+</sup> : <math>y_i=+1</math>의 데이터중에서 초평면과 가장 가까운 데이터 :<math>{\mathbf{X}}</math><sup>-</sup> : <math>y_i=-1</math>의 데이터중에서 초평면과 가장 가까운 데이터 주어진 초평면과 같은 법선벡터를 가지면서 <math>{\mathbf{X}}</math><sup>+</sup> 를 지나는 초평면은 :<math>\mathbf{w}\cdot\mathbf{x} - b=+1\,</math> 으로 나타낼 수 있고 비슷한 방식으로 <math>{\mathbf{X}}</math><sup>-</sup> 를 지나는 초평면은 :<math>\mathbf{w}\cdot\mathbf{x} - b=-1\,</math> 이와 같이 나타낸다. 초평면의 마진은 각 서포트 벡터를 지나는 초평면 사이의 거리를 의미한다. 기하학적으로 두 초평면 사이의 거리 즉, 마진을 구하면 <math>\tfrac{2}{\|\mathbf{w}\|}</math>라는 것을 알 수 있으며 서포트벡터머신은 마진을 최대로 만드는 알고리즘이다. <!--마진의 값이 최대인 초평면을 통해서 새로운 데이터가 속할 클래스 예측의 오차를 줄일 수 있다.--> 서포트벡터를 지나는 초평면 사이엔 데이터 포인트가 존재하지 않아야 하므로 다음과 같은 식이 성립한다. :<math>y_i=+1</math>인 <math>\mathbf{x}_i</math> 에 대해서 <math>\mathbf{w}\cdot\mathbf{x}_i - b \ge+1\,</math> :<math>y_i=-1</math>인 <math>\mathbf{x}_i</math> 에 대해서 <math>\mathbf{w}\cdot\mathbf{x}_i - b \le-1\,</math> 위 두 식은 아래와 같은 식으로 나타낼 수 있다. :<math>y_i(\mathbf{w}\cdot\mathbf{x}_i - b) \ge 1,\text{ for all } 1 \le i \le n.</math> 초평면의 조건을 따르며 마진의 최댓값을 구하고자 하는 서포트 벡터 머신 문제는 다음과 같은 최적화 문제로 표현할 수 있다. : <math>\arg\min_{(\mathbf{w},b)}\|\mathbf{w}\|</math> :단, <math>y_i(\mathbf{w}\cdot\mathbf{x}_i - b) \ge 1,\text{ for all } 1 \le i \le n.</math> === 원 형식 === 위에서 설명한 최적화 문제는 <math>\mathbf{w}</math>의 [[노름]]인 <math>\|\mathbf{w}\|</math>이 제곱근을 포함하고 있기 때문에 풀기 어렵다. 위의 최적화 문제에서 <math>\|\mathbf{w}\|</math>를 <math>\tfrac{1}{2}\|\mathbf{w}\|^2</math>로 치환하여도 최적화 문제를 만족시키는 해 <math>\mathbf{w}</math>, <math>b</math>는 변하지 않는다. 또한 <math>\tfrac{1}{2}\|\mathbf{w}\|^2</math>로 치환을 하게 되면 위의 문제는 2차 계획법({{llang|en|quadratic programming|쿼드라틱 프로그래밍}}) 최적화 문제가 된다. 치환된 최적화 문제는 아래와 같이 나타낼 수 있다. : <math>\arg\min_{(\mathbf{w},b)}\frac{1}{2}\|\mathbf{w}\|^2</math> :단, <math>y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1,\text{ for all } 1 \le i \le n.</math> [[라그랑주 승수법]]을 이용하면 위의 문제를 다음과 같은 [[안장점]]({{llang|en|saddle point}})을 찾는 문제로 나타낼 수 있다. : <math>\arg\min_{\mathbf{w},b } \max_{\boldsymbol{\alpha}\geq 0 } \left\{ \frac{1}{2}\|\mathbf{w}\|^2 - \sum_{i=1}^{n}{\alpha_i[y_i(\mathbf{w}\cdot \mathbf{x_i} - b)-1]} \right\}</math> 안장점을 찾는 과정에서 <math>y_i(\mathbf{w}\cdot\mathbf{x_i} - b) - 1 > 0 </math>으로 분류될 수 있는 모든 점들은 그에 대응하는 <math>\alpha_i</math>가 0으로 지정되기 때문에 영향을 미치지 않는다. 이제 이 문제는 정규 2차 계획법 기법으로 해결할 수 있다. 정적 [[Karush-Kuhn-Tucker 조건]]에 따르면, 문제의 해는 훈련 벡터({{llang|en|training vector}})의 선형 조합으로 표현될 수 있다. : <math>\mathbf{w} = \sum_{i=1}^n{\alpha_i y_i\mathbf{x_i}}</math> 적은 수의 <math>\alpha_i</math>만이 0보다 큰 값을 가지고, 그에 대응하는 <math>\mathbf{x_i}</math>들은 <math>y_i(\mathbf{w}\cdot\mathbf{x_i} - b) = 1</math>를 만족하는 정확한 서포트 벡터이다. 이 식을 통해 다음과 같이 [[오프셋 (컴퓨터 과학)]] <math>b</math>에 대한 정의를 유도할 수 있다. : <math>\mathbf{w}\cdot\mathbf{x_i} - b = \frac{1}{y_i} = y_i \iff b = \mathbf{w}\cdot\mathbf{x_i} - y_i</math> <math>b</math>는 <math>y_i</math>와 <math>x_i</math>에 의존하므로 각각의 데이터 포인트마다 값이 다르다. 표본 분포의 평균은 모평균(population mean)에 대해 [[불편 추정량]]({{llang|en|unbiased estimator}})이므로 다음과 같이 모든 서포트 벡터 <math>N_{SV}</math>에 대해서 평균을 취하는 것이 좋다. : <math>b = \frac{1}{N_{SV}} \sum_{i=1}^{N_{SV}}{(\mathbf{w}\cdot\mathbf{x_i} - y_i)}</math> == 분류 가능하지 않으면 == # 실수를 허용한다. 그러나 최대한 이러한 실수를 줄이기 위해서 노력한다. # 더 많은 feature를 더한다. 그러나 이러면 curse of dimensionality에 걸려 overfitting이 일어나게 된다. == 실수를 허용하면 == todo!() 이 문서에서 사용한 틀: 틀:Llang (원본 보기) Support vector machine 문서로 돌아갑니다.