Support Vector Regression(SVR)

Support Vector Regression(SVR)은 SVM의 회귀 알고리즘이다. 회귀 알고리즘은 데이터가 주어졌을 때 데이터를 가장 잘 설명하는 하나의 선을 찾는 것이다. 가장 좋은 회귀 직선을 찾는 기준점은 특정 범위 내에서 최소값을 가지는 손실함수(ex. mse, rmse, mae) 값이고 만약 같은 성능을 가진다면 더 단순한 함수를 가진 모델을 선호한다.

 

[SVC vs. SVR]

서포트 벡터 머신을 분류 문제와 회귀 문제에 적용할 때 정의가 다르다는 것과 SVM의 목적은 여백(margin)을 최대화하는 것임을 염두해 두어야 한다. 분류에서의 SVM은 두 클래스를 가장 잘 분류하는 초평면인 $w^t \cdot x +b$을 찾기 위해 여백을 최대화하는 것이 목적이다. 회귀에서의 SVM은 기본적으로 데이터들이 초평면으로부터 $/epsilon>0$ 범위 내에 있다고 가정하고 시작한다. 특정 데이터(support vector)로부터 가장 잘 설명하는 회귀 직선을 찾는데 마찬가지로 여백이 최대화되는 것을 목적으로 한다. 

 

먼저, SVR의 손실함수에 대해 설명해 보고자 한다.

Loss Function of Support Vector Regression

Figure 1

SVR의 손실함수를 그림으로 표현하면 'Figure 1'과 같다. 오른쪽 그래프와 같은 손실함수를 '$\epsilon$-incentive loss' 혹은 'hindge loss'라고 불린다. 

 

[$\epsilon$-insensitive loss, hinge loss]

$$l_{\epsilon}(\hat{y},y) = \begin{cases} 0 &\text{if } |\hat{y}-y|<\epsilon \\ |\hat{y}-y| - \epsilon &\text{o.w.} \end{cases} \\ = max(0, |\hat{y}-y|-\epsilon) \\ = (|\hat{y}-y|-\epsilon)_+$$

$\epsilon$은 허용하는 노이즈 정도를 의미한다. 특정 범위인 $(-\epsilon, \epsilon)$ 사이에 존재하는 오류는 허용하고 손실 함수를 0으로 주는 것이다. 만약, 특정 범위 밖에 존재하는 경우 패널티$(\xi, \xi^*)$를 부여하겠다는 것이다.

SVR 목적함수는 '$\epsilon$-insensitive loss'를 최소화하면서 과적합 방지를 위한 L2-규제 텀을 추가해준다. 일반 선형회귀 모델에서 과적합이 발생하는 경우, 회귀 계수의 크기도 증가하기 때문에 추가적으로 제약을 부여하여 회귀계수의 크기가 너무 커지지 않도록 패널티 텀을 부여하여 계수의 크기를 제한하는 정규화 방법을 적용한 것이다.

SVR은 데이터에 노이즈가 있다고 가정하며, 이러한 점을 고려하여 노이즈가 실제 값을 완벽히 추정하는 것을 추구하지 않는다. 따라서, 적정 범위 $(-\epsilon, \epsilon)$내에서는 실제값과 예측값 차이의 오차를 허용한다.

SVC에서 hard margin과 soft margin으로 나뉘어졌던 것처럼 SVR도 hard margin과 soft margin으로 나누어지지만 정의는 다르다. Hard Margin Linear SVR은 모든 데이터가 오차 $\epsilon$에 있으면서, 즉 여백 안에만 존재하고 여백을 최대화하는 선형 회귀 직선을 구하는 것이다.  반면, Soft Margin은 $\epsilon$ 밖에, 즉 여백 밖에도 데이터도 존재한다고 가정하고 여백을 최대화하는 선형 회귀 직선을 찾는 것이다. 여기에서도 볼 수 있듯이 SVC에서 정의하는 hard margin과 soft margin 의미가 다르다는 것을 다시 한 번 확인할 수 있다. SVC에서의 hard margin는 여백 사이에 어떤 데이터도 허용하지 않고 여백을 최대화하는 초평면을 찾는 것이 목적이였고 soft margin의 경우 여백 사이에 어느 정도 예외를 허용하고 여백을 최대화하는 초평면을 찾는 것이 목적이었다.

 

이제 Soft Margin Linear SVR의 알고리즘을 살펴보도록 하겠다.

Objective Function

SVR 목적함수의 정의는 다음과 같다.

$$min_{\{w,b\}}\dfrac{1}{n}\sum^n_{i=1}(|(w^t \cdot x_i + b)-y| - \epsilon)_+ + \lambda||w||^2_2$$

• 첫번째 term = $\epsilon$-insensitive loss : 실제값과 추정값 차이를 최소화
• 두번째 term = robustness : 과적합을 방지하는 패널티 텀 | 여백을 최대화하는 텀

slack variable인 $\xi_i, \xi_i^*$ 값을 이용해 $\lambda=\dfrac{1}{2cn} (c>0)$ 정의를 통해 목적함수를 다음과 같이 변형할 수 있다.

Figure 2

$$min_{\{w,b,\xi_i,\xi_i^*\}}(\dfrac{1}{2}||w||^2_2+C\sum^n_{i=1}(\xi_i+\xi_i^*)) \\ s.t. \, \xi_i \geq (w^t \cdot x_i + b) - y_i - \epsilon \\ \, \, \, \xi_i^* \geq y_i - (w^t \cdot x_i + b) - \epsilon,\\  i = 1,2,...,n \\ \xi_i, \xi_i^* \geq 0 $$

Lagrangian Primal Problem

목적함수에 제약조건이 존재하므로 라그랑주 승수를 이용해 제약이 없는 'lagrangian primal problem'을 통해 하나의 식으로 표현이 가능하다.  'Lagrangian primal problem'은 커널함수를 사용하기 용이하도록 수식을 재구성하게되는 이점도 존재한다.

$$minL_p(w,b,\xi_i,\xi_i^*,n_i,n_i^*,\alpha_i,\alpha_i^*) = \dfrac{1}{2}||w||^2 + C\sum^n_{i=1}(\xi_i+\xi_I^*)-\sum^n_{i=1}(n_i\xi_i+ n_i^* \xi_i^*)-\sum^n_{i=1}\alpha_i(\xi_i+\epsilon-w^t \cdot x_i - b + y_i) - \sum^n_{i=1}\alpha_i^*(\xi_i^* + \epsilon + w^t \cdot x_i + b - y_i)$$

 

우리는 위의 식을 통해 최적해 $w$, $b$와 $\xi_i$를 구해야 한다.

KKT 조건에 의해, 목적식의 미지수에 대한 미분 값이 0일 때 최적해를 갖는다.

$$\dfrac{\partial{L_p}}{\partial{b}}=\sum^n_{i=1}(\alpha_i-\alpha_i^*)=0$$

$$\dfrac{\partial{L_p}}{\partial{W}}=W-\sum^n_{i=1}(\alpha^*_i-\alpha_i)x_i = 0, W=\sum^n_{i=1}(\alpha^*_i-\alpha_i)x_i$$

$$\dfrac{\partial{L_p}}{\partial{\xi_i}}=C - n_i-\alpha_i, \forall i$$

$$\dfrac{\partial{L_p}}{\partial{\xi_i^*}}=C - n_i^*-\alpha_i^*, \forall i$$

우리가 만약 $\alpha$ 값을 안다면 회귀식 추정값인 $W$와 $b$에 대해서 구할 수 있지만 모르기 때문에 미분을 통해 얻은 4가지 조건을  'Lagrangian primal problem' 목적식에 다시 대입하면 $\alpha$에 대한 식  'Lagrangian dual problem'으로 정의가 가능하다.

 

Lagrangian Dual Problem

$$maxL_D(\alpha_i,\alpha_i^)=-\dfrac{1}{2}\sum^n_{i=1}\sum^n_{j=1}(\alpha^i-\alpha_i)(\alpha_j^*-\alpha_j)x_i^tx_j-\epsilon\sum^n{i=1}(\alpha_i+\alpha_i^)+\sum^n_{i=1}(\alpha_i^-\alpha_i)y_i$, s.t. $\sum^n_{i=1}(\alpha_i-\alpha_i^)=0, \, 0 \leq a_i,a_i^ \leq C$$

우리가 추정하고자 하는 $W$와 $b$를 구하기 위해서는 $\alpha$ 값이 필요하다. SVC에서와 마찬가지로 'Lagrangian dual problem' 식인 $L_D$를 minimize 식으로 변환한 후 quadratic programming(QP) 형식에 맞게 변환시켜주면 다음과 같다. QP를 통해 $/alpha$를 구하면 된다.($\hat{\alpha}$)

그럼 $W$는 $W = \sum^n_{i=1}(\alpha_i-\alpha_i^*)x_i$에 $\hat{\alpha}$를 대입해서 구하면 된다.

또한 알 수 있는 점은 $\alpha_i - \alpha_i^*$이 0이 아닌 데이터를 서포트 벡터라고 하며 $W$와 $b$는 서포트 벡터인 데이터들에 의해서만 추정된다는 점을 염두해 두어야 한다.

만약, 새로운 데이터가 주어진 경우, 예측값은 $f(x) = \sum^n_{i=1}(\alpha-\alpha^*)x_i^tx+b$이다.

 

 

마찬가지로 입력 공간이 비선형인 경우는 SVC에처럼 커널함수를 이용하면 된다.

Dual Lagrangian Problem with Kernel Trick

$$maxL_D(\alpha_i, \alpha_i^)=\sum^n_{i=1}(\alpha_i-\alpha_i^)y_i-\epsilon\sum^n_{i=1}(\alpha_i+\alpha_i^)-\dfrac{1}{2}(\alpha_i-\alpha_i^)(\alpha_j-\alpha_j^)x_i^tx_j$, s.t. $\sum^n_{i=1}(\alpha_i-\alpha_i^)=0, 0 \leq \alpha_i, \alpha_i^* \leq C$$

• $\hat{w}=\sum^n_{i=1}(\hat{\alpha_i}-\hat{\alpha_i^*})\Phi(x_i)$
• $f(x) = \sum^n_{i-1}\hat{w}^tK(x_i,x)+b=\sum^n_{i=1}(\hat{\alpha_i}-\hat{\alpha_i^*})K(x_i^t,x)+b$