[Machine Learning] Support Vector Machine (SVM) (2)

이전 글에서 SVM에 대한 기본적인 개념을 설명하였다.

[Machine Learning] Support Vector Machine (SVM) (1)

 

 

이번 포스트에서는 SVM의 optimization problem을 푸는 방법에 대해 설명해보도록 하겠다.

 

SVM의 object function은 다음과 같다.

 

min $\frac{1}{2} ||w^2||$

subject to $y_i(w^TX_i + b) ≥ 1$, ∀$i$ ∈ [1, N]

 

각 data마다 제약조건이 있으므로, 총 N개의 제약조건이 존재한다.

제약조건이 있으므로 gradient descendent로 solution을 찾기 어렵다.

 

따라서 Lagrange multiplier로 optimization propblem을 해결한다.

 

Lagrange multiplier

본 글에선 Lagrange multiplier가 무엇인지는 다루지 않고, Lagrange multiplier를 이용한 문제 해결에 대해서만 다룬다.

Lagrange multiplier로 optimization problem을 해결하는 대략적인 과정은 다음과 같다.

 

1. Lagrange multiplier를 정의한다.

α = <$α_1, α_2, ... , α_N$> (모든 $i$에 대해 $α_i$ ≥ 0)

 

2. Lagrange (objective) function을 정의한다.

$L_p(w,$ b, $\alpha$) = $f(w)$ - $\sum_{i=1}^n$ $\alpha_ig_i(w, $b)

$f(w)$: objective function

$g_i(w,$ b): constrain

 

3. dual problem을 푼다.

$\underset{w, b}{argmin}${ $L_p(w,$ b, $\alpha$) }을 풀면 $\alpha$에 대한 식이 나온다. 나온 $L$($\alpha$)에 대해 $\underset{α}{argmax}$를 찾는다. 정리하면 다음과 같다.

$\underset{\alpha}{argmax}${ $\underset{w, b}{argmin}${$ L_p(w,$, b, $\alpha$) } }

 

Optimization with Constraints

SVM에서의 constraint는 $g_i(X) = y_i(w^TX_i + b) ≥ 1$, 즉 부등식이다.

그러나 우선 부등식이 아닌 등식으로 이루어진 제약사항에부터 설명하겠다.

 

목표는 $f(x)$를 주어진 제약사항 $g_i(x) = 0$을 만족하며 최적화 하는 것이다.

$L_p(w,$ b, $\alpha$) = $f(w)$ - $\sum_{i=1}^n$ $\alpha_ig_i(w, $b) , ($\alpha_i$ $\neq$ 0)

 

Key idea는 다음과 같다.

 

$\nabla$$f(w^*)$ = $\alpha$$\cdot$$\nabla$$g(w^*)$

즉, optimal point에서 두 gradient ▽$f(w^*)$와 ▽$g(w^*)$는 parallel 또는 anti-parallel 하다.

 

 

그렇다면 왜 parallel할까? 예시를 들어 설명해보겠다.

다음과 같은 optimization problem이 있다.

 

Minimize $f(w_1, w_2) = w_1^2 + w_2^2$

subject to $g(w_1, w_2) = y_1$ $\cdot$ $(x_1w_1 + x_2w_2$ + b) = 0

 

만약 제약조건이 없다면, 원점의 ($w_1, w_2$)가 solution일 것이다.

그러나 제약조건 $g(w_1, w_2)$(빨간 직선)이 생겼으므로 solution은 달라진다.

제약조건을 만족하며 $f$를 minimize하는 $w^*$ ($w_1, w_2$)는 $f$와 $g$의 접점일 것이다.

그 지점에서 두 gradient vector $\nabla$$f$와 $\nabla$$g$는 parallel하다.

 

만약 제약조건이 사진의 보라색 직선이라면, $w^*$는 $f$와 보라색 직선의 접점에 생길 것이다.

$w^*$에서 두 gradient vector는 anti-parallel하다.

 

constraint가 직선이 아닌 곡선이어도 마찬가지이다.

 

---

 

Lagrangian function의 optimization problem을 푸는 법은 다음과 같다.

 

1. Lagrangian function을 정의

$L(w$, $\alpha$) = $f(w)$ - $\alpha$$g(w)$

 

2. optimal한 $w^*$과 $\alpha$를 얻으려면 다음 식을 풀면 된다.

 

$\underset{w, \alpha}{\nabla}$$L$ = [$\frac {\partial L}{\partial w}$ $\frac {\partial L}{\partial \alpha}$] = 0

 

3. 편미분한 결과로 다음 식들을 얻게 된다.

---

위 과정을 이용해 optimization problem을 풀어보자.

 

Max $f(x_1, x_2) = 1 - x^2_1 - x^2_2$

Subject to $g(x_1, x_2) = x_1 + x_2 - 1 = 0$

 

minimazation problem으로 바꾸기 위해 $f(x_1, x_2)$에 -1을 곱해주겠다. 그럼 다음 문제로 바뀐다.

 

Minimize $f(x_1, x_2) = x^2_1 + x^2_2 - 1$

Subject to $g(x_1, x_2) = x_1 + x_2 - 1 = 0$

1. Lagrangian function을 구한다. 

$L$($x$, $\alpha$) = $x^2_1$ + $x^2_2$ - 1 - $\alpha$ ($x_1 + x_2$ - 1)

 

2. 최적의 해를 얻기 위해 $w$, $\alpha$로 각각 편미분하면 다음 식들이 나온다.

 

3. 연립방정식을 이용해 해를 구한다.

($x^*_1, x^*_2$) = ($\frac {1}{2}$, $\frac {1}{2}$)

$\alpha$ = 1

$\alpha$ > 0 이므로 $\nabla$$f$와 $\nabla$$g$는 ($x^*_1, x^*_2$)에서 parallel함을 알 수 있다.

 

---

지금까지는 constraint가 1개인 problem을 lagrange multiplier로 푸는 법에 대해서 설명했다.

이제 multiple constraint를 가진 problem을 lagrange mulitplier로 푸는 법에 대해 설명해보겠다.

위와같이 여러 제약조건(빨강, 파랑 직선)들이 있을 때, 제약조건 직선들의 평균(중간) 직선의 gradient와 $\nabla$$f$는 optimal point에서 평행하다. 이를 식으로 나타내면 다음과 같다.

 

따라서 N개의 constraint가 있다면 다음을 만족하는 $\alpha_1, \alpha_2, ... , \alpha_N$이 존재한다.

 

그렇다면 Lagrange function은 다음과 같아진다.

 

single constraint에서와 같이, 위 식을 각 parameter들로 편미분해서 얻어진 식으로 문제를 해결하면 된다.

 

---

지금까지는 equality constraint에 대해 보았다.

아주 위에 언급했듯, SVM에서의 constraint는 $g_i(X) = y_i(w^TX_i + b) ≥ 1$, 즉 부등식이다.

 

이제부턴 inequality constraint를 가진 optimization problem을 lagrange multiplier를 이용해 풀어보겠다.

 

Minimize $f(x)$

Subject to $g(x)$ ≥ 0

 

constraint가 부등식이므로, 두 가지 상황에 대해 고려해야 한다.

1. constraint가 active한 경우

2. constraint가 inactive한 경우

 

inequality constraint를 가진 problem에서는 제약조건을 만족하는 point가 꼭 $f$와 $g$의 접점 위에 있지 않아도 된다.

$g$에 대한 inequlity를 만족하는 영역 내에만 optimal point가 존재하면 된다.

 

1. constraint가 active한 경우

• optimal point는 $f$와 $g$가 만나는 접점 위에 있다.
• 두 gradient는 parallel하다. 
  • $\nabla$$f(w^*)$ = $\alpha$$\cdot$$g(w^*)$, $\alpha$ > 0
  • equality constraint에서는 두 gradient가 parallel 또는 anti-parallel했지만, inequality constraint에서는 parallel하다. 따라서 $\alpha$ > 0 이어야 한다.

 

2. constraint가 inactive한 경우

• $g(w)$는 아무런 영향을 끼치지 못한다.
• optimal point는 $g(w^*)$ > 0인 영역에 존재한다.

 

inequality가 곡선인 상황에서도 같다.

1. constraint가 active한 경우

 

2. constraint가 inactive한 경우

 

위를 정리하면 다음과 같다.

Lagrange function form: $L(w$, $\alpha$) = $f(w)$ - $\alpha g(w)$

Inactive Constraint: $g(w^*) > 0$, $\alpha$ = $0$, $\nabla f(w^*)$ = $\alpha \nabla g(w^*)$ = $0$

Active Constraint: $g(w^*) = 0$, $\alpha$ > $0$, $\nabla f(w^*)$ = $\alpha \nabla g(w^*)$ 

 

Inactive Constraint에서 $\alpha$가 0인 이유는, 나중에 모든 데이터에 대해 일반화 된 식을 쓸 때 위 항은 inactive하므로 고려할 필요가 없어 0으로 만들기 위해 $\alpha$를 0으로 만들어 곱해준다.

 

이 조건들을 한번에 쓰면 다음 조건들이 완성된다.

이를 Karush-Kuhn-Tucker (KKT) condition이라고 한다.

$\nabla f(w^*) - \nabla \alpha g(w^*)$ = 0

$\alpha cdot g(w^*)$ = 0

$\alpha$ ≥ 0

$g(w^*)$ ≥ 0

 

 

이제 이를 모든 데이터에 적용해보겠다.

1. Lagrange function form

$L(w$, $\alpha$) = $f(w)$ - $\sum_{i=1}^n$ ${\alpha}_i g_i(w)$

2. KKT condition

3. Solve

• $\underset{w}{min}$$L(w, \alpha)$를 풀면 Lagrange Dual function $L_D(\alpha)$를 얻게 된다.
  • $L(w, \alpha)$: Lagrange Primal function, 원래 minimize하고자했던 function
  • $L_D(\alpha)$: Lagrange Dual function
• $\underset{\alpha}{max}$$L_D(\alpha)$를 푼다.

maximize 하는 이유에 대해 간단히 설명해보겠다.

Lagrange Primal Function은 위에 있는 곡선처럼 생겼다. 우리는 이 함수를 minimize하는 지점 $P^*$를 찾았다.

Lagrange Dual Function은 아래에 있는 곡선처럼 생겼다. Duality Gap을 줄이기 위해, 즉 원래 primal 함수와 최대한 비슷해지기 위해 dula function을 maximize하는 $\alpha$를 찾는 것이다.

 

 

이제 $f(w)$에 처음에 만들었던 objective function $\frac {1}{2}$$||w^2||$을,

$g_i(w$)에 $y_i(w^Tx_i + b) - 1$을 대입하면 다음과 같이 SVM의 optimization problem을 정의할 수 있다.

 

 

 

거의 다 왔다. 실제로 문제를 푸는 과정은 다음 포스트에 다루도록 하겠다.