Ahn9807: 새 문서: 분류: 지도 학습 == 개요 == Perceptron에서 Mediocore문제를 해결하기 위하여 마진이라는 개념을 이용하여 두 집단을 분류하는 방법론을 말한다. == 선형 SVM == 주어진 학습용 데이터 집합 D(N 개의 점으로 이루어진 집합)를 다음과 같이 정의해보자. : $\mathcal{D} = \{ (\mathbf{x}_i, y_i)|\mathbf{x}_i \in \mathbb{R}^p, y_i \in \{-1,1\}\}_{i=1}^n$ 각 $\mathbf{x}_i$ 는 p차원의 실...

2023-02-24T09:09:40Z

새 문서: 분류: 지도 학습 == 개요 == 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차원의 실...

새 문서

[[분류: 지도 학습]]

== 개요 ==
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>+, <math>{\mathbf{X}}</math>-)는 다음과 같이 정의된다.
:<math>{\mathbf{X}}</math>+ : <math>y_i=+1</math>의 데이터중에서 초평면과 가장 가까운 데이터
:<math>{\mathbf{X}}</math>- : <math>y_i=-1</math>의 데이터중에서 초평면과 가장 가까운 데이터

주어진 초평면과 같은 법선벡터를 가지면서 <math>{\mathbf{X}}</math>+ 를 지나는 초평면은
:<math>\mathbf{w}\cdot\mathbf{x} - b=+1\,</math>
으로 나타낼 수 있고 비슷한 방식으로 <math>{\mathbf{X}}</math>- 를 지나는 초평면은
:<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!()

Support vector machine - 편집 역사