Support Vector Regression (SVR)

02_4 : Kernel based learning : Support Vector Regression (SVR)

앞에서 공부했던 SVM은 binary classification을 하기 위한 방법이었다. 이번 글에서 알아볼 SVR은 함수를 추정하여 연속적인 수치변수를 예측하는 회귀 방법이다. 

SVR을 알아보기에 앞서 우리가 하려는 함수추정의 목적을 살펴보자.

Fitting function

함수를 추정하고 싶을 때 우리의 목적은 크게 2가지로 나뉜다.

• Minimize an error measure (Loss function)

한마디로 error를 최소화 하여야 한다. (잘 맞춰야 한다)

• Function to be simple

같은 성능이라면, 함수는 최대한 단순해야 한다. 함수가 단순하다는 뜻은 아래의 조건들을 의미한다.

1. Fewest basis functions
2. Simplest basis functions
3. Flatness is desirable

---

Support Vector Regression (SVR)

위에서 살펴보았던 Loss function과 Flatness를 반영하도록 목적함수를 만들 것이다. SVR에도 여러 종류가 있는데, 우선 $\varepsilon$-SVR에 대하여 알아보자.

현실의 Data들은 어쩔 수 없이 발생하는 noise가 존재한다. 아래 식에서 noise는 $\varepsilon$이다.

$$y = f(x)+\varepsilon$$

$\varepsilon$-SVR에서 핵심 아이디어는 $\varepsilon$ 보다 작은 noise에 대해서는 Loss를 주지 말자는 것이다. 

왼쪽 그림에서 색이 칠해진 영역을 Epsilon-tube 라고 하는데, 이 영역안에 있는 객체들에게는 Loss를 부여하지 않는다. 이를 위한 Loss function은 오른쪽에 표현된다. 이 Loss function은 hinge를 닮았다고 해서, Hinge Loss라고 불린다. 차이가 $\varepsilon$ 보다 작은 경우 loss는 0이고, $\varepsilon$ 보다 큰 경우 선형적으로 $\xi$만큼의 loss를 받는다.

Squared loss를 사용하는 경우와 비교했을 때 noise에 더 robust하고, 선형적으로 loss가 계산됨으로 out liar에 덜 민감하다. hinge loss를 사용한 SVR을 Formulate 해보자.

• Estimating a linear regression

$$f(\mathbb{x}) = \mathbb{w}^T\mathbb{x} + b$$

목표는 미지수 $\mathbb{w}$와 $b$를 알아내는 것이다.

• Optimization problem with precision $\epsilon$

$$min\;\;\;\;\frac{1}{2}||\mathbb{w}||^2+C\sum_{i = 1}^n(\xi_i+\xi_i^*)$$

$$s.t.\;\;\;\;(\mathbb{w}^T\mathbb{x} + b)-y_i\leq \epsilon + \xi_i\;\;\;\;\;\;(1)$$

$$\;\;\;\;\,\;\;\;\;\;y_i-(\mathbb{w}^T\mathbb{x} + b)\leq \epsilon + \xi_i^*\;\;\;\;\;\;(2)$$

$$\xi_i,\xi_i^*\geq 0$$

SVM에서 $\frac{1}{2}||\mathbb{w}||^2$ 항은 Margin을 최대화 하는 역할이었다. 하지만 SVR에서는 Flatness를 최대화 하는 역할이다. 그렇다면 Loss를 최소화 하는 부분은 어디일까? 바로 뒤쪽에 있는 $C\sum_{i = 1}^n(\xi_i+\xi_i^*)$ term이다. $C$는 Loss와 Flatness간의 trade-off를 조정하는 Hyperparameter이다.

Loss를 최소화 하는 term이 뒤쪽에 있다보니 Ridge regression과 비교했을 때 햇갈릴 수 있다. 하지만 $\xi_i$가 무엇을 의미하는지 생각해보면 그리 어렵지 않다. 아래의 제약식에서 $\xi_i$를 살펴보자.

제약식을 살펴보면 (1)과 (2) 2개가 있다. 각 제약식은 한번에 적용되는 것이 아니라 Estimate 된 함수의 아래에 있는 객체에는 (1)번이, 함수의 위에 있는 객체에는 (2)번이 적용된다.

예시를 살펴보자. (예시의 함수가 비선형으로 생긴것에 의문이 있을 것이다. 이것은 Kernel 방법을 적용하여 SVR을 수행한 결과이기 때문이다.)

먼저 함수의 아래쪽에 위치한 보라색 point를 살펴보자. 해당 $x_i$ 값에 대하여 함수가 추정하는 값은 $\mathbb{w}^T\mathbb{x} + b$으로, 그림에서 검은 점에 해당한다. 그렇다면 검은 점에게 부여되는 Loss $\xi$는 $(\mathbb{w}^T\mathbb{x} + b)-y_i -\epsilon$ 이다. 그림에서 초록색 선이 Loss $\xi$를 나타낸다. 이에 대한 제약식이 (1)번이다.

함수의 위쪽에 위치한 주황색 point를 살펴보면, 위에서 본 것과 동일하게 $x_i$ 값에 대하여 함수는 $\mathbb{w}^T\mathbb{x} + b$ 를 추정할 것이다. 이때의 Loss $\xi^*$는 $y_i-(\mathbb{w}^T\mathbb{x} + b)-\epsilon$ 이다. 그림에서 초록색 선이 Loss $\xi^*$를 나타낸다. 이에 대한 제약식이 (2)번이다.

이제 최적화 문제를 Lagrangian 승수법을 사용하여 Primal Lagrangian으로 바꾸어보자.

• Primal Lagrangian

$$\begin{align*}L_P=&\frac{1}{2}||\mathbb{w}||^2+C\sum_{i = 1}^n(\xi_i+\xi_i^*) - \sum_{i = 1}^n(\eta_i\xi_i+\eta_i^*\xi_i^*)\\& - \sum_{i = 1}^n\alpha_i(\epsilon + \xi_i + y_i - \mathbb{w}^T\mathbb{x} - b) -  \sum_{i = 1}^n\alpha_i^*(\epsilon + \xi_i^* + y_i - \mathbb{w}^T\mathbb{x} - b)\end{align*}$$

$$\alpha_i,\alpha_i^*,\eta_i,\eta_i^* \geq 0$$

KKT Condition에 따라 미지수 $b, \mathbb{w}, \xi_i,\xi_i^*$로 미분한 값은 0 이어야 한다.

$$\frac{\partial L}{\partial b} = \sum_{i = 1}^n (\alpha_i-\alpha_i^*) = 0$$

$$\frac{\partial L}{\partial \mathbb{w}} = \mathbb{w} - \sum_{i = 1}^n (\alpha_i^*-\alpha_i)\mathbb{x}_i = 0$$

$$\frac{\partial L}{\partial \xi_i} = C - \alpha_i - \eta_i = 0$$

$$\frac{\partial L}{\partial \xi_i^*} = C - \alpha_i^* - \eta_i^* = 0$$

그동안 했던 것 처럼 $\mathbb{w} = \sum_{i = 1}^n (\alpha_i^*-\alpha_i)\mathbb{x}_i$를 대입하고 위에서 구한 조건들을 사용해 식을 정리하면 Dual problem으로 바꿀 수 있다. (계산과정은 생략했다)

• Dual Lagrangian problem

$$L_D=-\frac{1}{2}\sum_{i,j = 1}^n(\alpha_i^*-\alpha_i)(\alpha_j^*-\alpha_j)\mathbb{x}^T_i\mathbb{x}_j - \epsilon \sum_{i = 1}^n(\alpha_i+\alpha_i^*) + \sum_{i = 1}^n y_i(\alpha_i^*-\alpha_i)$$

$$s.t.\;\;\;\sum_{i = 1}^n(\alpha_i-\alpha_i^*) = 0,\;\;\alpha_i,\alpha_i^* \in [0,C]$$

위 식을 통해 최적해를 구하면 $\mathbb{w} = \sum_{i = 1}^n (\alpha_i^*-\alpha_i)\mathbb{x}_i$을 사용하여 Decision function을 구할 수 있다.

• Decision function

$$f(\mathbb{x}_{new}) = \mathbb{w}^T\mathbb{x}_{new} + b$$

$$f(\mathbb{x}_{new}) = \sum_{i = 1}^n (\alpha_i^*-\alpha_i)\mathbb{x}_i^T\mathbb{x}_{new} + b$$

SVM 처럼 $\alpha_i > 0$인 Support vector들만 사용하여 Decision이 결정된다. 이 Support vector들은 epsilon-tube 위에 있거나 바깥쪽에 존재하는 객체들이다.

위에서 이야기 했던 것 처럼 SVR에도 Kernel trick을 적용 가능하다. Dual Lagrangian problem에 Kernel trick을 적용해보자. (계산과정은 생략했다)

• Dual Lagrangian problem with Kernel trick

$$L_D=-\frac{1}{2}\sum_{i,j = 1}^n(\alpha_i^*-\alpha_i)(\alpha_j^*-\alpha_j)K(\mathbb{x}_i,\mathbb{x}_j) - \epsilon \sum_{i = 1}^n(\alpha_i+\alpha_i^*) + \sum_{i = 1}^n y_i(\alpha_i^*-\alpha_i)$$

$$s.t.\;\;\;\sum_{i = 1}^n(\alpha_i-\alpha_i^*) = 0,\;\;\alpha_i,\alpha_i^* \in [0,C]$$

기존의 $\mathbb{x}^T_i\mathbb{x}_j$ 항이 Kernel 함수 $K(\mathbb{x}_i,\mathbb{x}_j)$로 바뀌었다. 그리고 $\mathbb{w}$가 바뀌었음으로 Decision function도 바뀐다.

• Decision function

$$\mathbb{w} = \sum_{i = 1}^n (\alpha_i^*-\alpha_i)\Phi(\mathbb{x}_i)$$

$$f(\mathbb{x}_{new}) = \sum_{i = 1}^n (\alpha_i^*-\alpha_i)K(\mathbb{x}_i,\mathbb{x}_{new}) + b$$

---

Support Vector Regression (SVR) (Cont.)

• Loss function

지금까지 알아본 $\varepsilon$-SVR은 $\varepsilon$-insensitive 함수를 Loss function으로 사용한 SVR이었다. 실제로는 훨씬 많은 Loss function들이 존재한다.

data의 특성에 따라 적절한 Loss function을 선택하는 것이 중요하다.

• Kernel trick

SVR에서 Kernel Trick을 사용하는 것은 중요하다. 그냥 Linear kernel을 사용한다면, Linear regression과 별 다를점이 없다. (실제로도 loss function이 좀 다른점을 제외하면 비슷하게 선형 함수를 찾을 것이다) 하지만 Kernel trick을 사용함으로써 복잡한 함수도 찾을 수 있다.

위 예시처럼 동일한 SVR 방법을 사용하더라도 Kernel 함수에 따라 많이 다른 결과를 보인다.

• Hyperparameter $C$

$$\frac{1}{2}||\mathbb{w}||^2+C\sum_{i = 1}^n(\xi_i+\xi_i^*)$$
이번에는 $C$에 대하여 이야기 해보자. $C$는 Loss와 Flatness간의 trade-off를 조정하는 Hyperparameter이다. RBF Kernel과 같은 적절한 Kernel trick을 적용한 상태에서 $C$가 크다면, 각 $x_i$의 Loss가 미치는 영향이 커진다. 때문에 이를 최소화 하기 위해 함수가 복잡해질 것이다. 반면 $C$가 작다면, 함수의 Flatness term의 영향이 커지고, 함수가 단순해질 것이다. 

예시를 보면 $C$가 더 클수록 함수가 더 복잡한 것을 확인할 수 있다.

※ 이 글은 고려대학교 산업경영공학과 강필성 교수님의 IME654 강의를 참고하여 작성되었습니다.