[KOOC] 인공지능 및 기계학습 개론 5,6주차 - Support Vector Machine, Training, Regularization

Chapter 5. Support Vector Machine

• 목차

1. Support Vector Machine Classifier
   • maximum margin idea of the SVM
   • formulation of the optimization problem
2. soft-margin and penalization
   • penalization term
   • difference between the log-loss and the hinge-loss
3. kernel trick
   • primal problem and the dual problem of SVM
   • types of kernels
   • apply the kernel trick to SVM and logistic regression

 

 

5-1. Support Vector Machine

decision boundary은 모델의 성능에 영향을 많이 끼친다. 따라서 decision boundary를 잘 지정하는 것이 중요하다. 위의 그래프처럼 빨간색 점과 파란색 점으로 이루어진 데이터가 있고, 그에 대한 decision boundary를 구하고자 한다면, 어떻게 그어야 잘 그어질 수 있을까? 대충 빨간색과 파란색이 잘 구별되도록 그을 수 있겠지만, 그렇게 하면 새로운 데이터에 대해 분별력이 떨어질 수도 있다. 따라서 이를 잘 설정할 수 있도록 margin을 설정하여 그려본다.

 

예를 들어, 가장 하단의 빨간색 점 2개를 지나는 빨간색 직선을 긋고, 그 직선과 동일한 기울기를 가진 가장 상단의 파란색 점을 지나는 파란색 직선을 또 그려본다. 그리고는, 이 두 직선과 같은 거리를 가진 직선인 초록색 선을 그린다. 그러면 초록색 선 기준으로 현재 데이터에 대해 알맞는 직선 중 가장 먼 거리에 위치한 직선은 각각 이 빨간색 직선과 파란색 직선이 될 것이다.

수식적으로 바라본다면, decision boundary 직선의 방정식은 아래 방향을 향한 법선 벡터 w, bias 텀 b를 가지고, 직선 위의 점을 fitting했을 때 wx + b = 0로 나타낼 수 있고, 파란색 점들을 positive case, 빨간색 점들을 negative case라 할 때, positive point들은 wx + b > 0, negative point들은 wx + b < 0 이 된다. 이 때, positive case를 +1, negative case를 -1로 가정하고, confidence level을 $ (wx_i + b)y_i $ 라고 정의를 하면, confidence level은 항상 양수가 될 것이고, 이 confidence를 높이는 것을 목표로 할 수 있다.

decision boundary와 가장 근접해 있는 점과의 수직 거리를 margin이라 나타낼 수 있다. 빨간색 직선과 파란색 직선이 maximum margin을 가진 decision boundary라 할 수 있다.

 

wx + b = f(x)로 가정했을 때, 직선 위의 점 x_p에 대해서는 wx_p + b = 0, 또, positive point인 $ x_pos $ 들에 대해서는 wx_pos + b > a , a > 0 이 성립된다.

임의의 점 X에 대해 decision boundary와의 margin(distance)를 구해보자. 직선 위의 점 x_p 와 X의 거리를 r이라 할 때, decision boundary의 법선 벡터인 w를 통해 X를 구할 수 있다. 그 후, margin인 r를 구하기 위해 직선의 방정식에 대입한다.

\[x = x_p + r \cfrac{w}{||w||}\] \[f(x) = w \cdot x + b = w(x_p + r \cfrac{w}{||w||} + b = w x_p + b + r \cfrac{w \cdot w }{||w||} = r||w||\]

 

margin $ r = \frac{a}{||w||} $ 로 나타낼 수 있고, margin이 최대가 되는 w와 b를 값을 구하기 위해 optimization을 수행하면 $ argmax_{w,b} 2r = \cfrac{a}{

w

} $ 로 정의할 수 있다. 이 때, 2r이 이유는 margin은 위 아래 양쪽으로 거리가 있는데 r은 한 방향에 대한 거리만 정의했으므로 2를 곱한다. 사실 2는 상수이므로 중요한 값은 아니다. 아까 confidence level에 대한 식을 $ (wx_i + b)y_i >= a $ 라 정의했는데, a는 임의의 수이므로 1로 지정해볼 수 있다. a를 1로 하게 되면 $ argmax_{w,b} 2r = \cfrac{1}{

w

} $ 이 될 것이고, 분모, 분자를 바꾸어서 $ argmin_{w,b} 2r =

w

$ 로 할 수 있다. 이 때, w는 개별 요소를 살펴보면 w1, w2, w3… 이므로 $

w

= \sqrt{w_1^2 + w_2^2} $ 와 같은 quadratic problem으로 정의된다. 이 w에 대해 최적화해야 하는데, matlab에서는 linear programming, quadratic programming과 같은 optimization 기법이 존재하므로 이를 사용하여 최적화를 수행하면 된다.

 

그러나, 우리가 가진 데이터는 완벽하게 나뉘어질 수 있는 상황이지만, 만약에 빨간색 점이 파란색 점들 사이에 존재하게 되면, 완벽한 decision boundary를 만들 수 없다.

이러한 완벽한 decision boundary에 대한 margin을 hard margin이라 해보자. hard margin인 경우에는 어떠한 에러도 존재해서는 안된다.

 

실제 현실은 error가 항상 존재하므로, 에러를 일부 인정하는 margin을 soft margin이라 한다. soft margin을 하게 되면, decision boundary를 선형으로 유지하면서 decision boundary를 찾을 수 있다. 또는 soft margin을 가정하지 않고, decision boundary를 비선형으로 그어주면 hard margin을 유지하면서 완벽한 decision boundary를 만들 수 있다.

그래서 soft margin과 비선형 decision boundary를 만들 수 있게 해주는 kernel trick에 대해 배워보고자 한다.

 

 

5-2. Soft Margin

error case를 허용하는 decision boundary를 구성하고자 한다.

 

아까 전, 구했던 optimization 식 $ min_{w,b}

w

$ 에 error 개수와 constant 항을 추가하여 최적화한다.

\[min_{w,b}||w|| + C \times N_{error}\]

C는 패널티와 같은 항으로, loss function에 해당한다.

loss function에는 zero-one loss function이 있다. 이는 상단에서 아래로 이동한다고 생각할 때, loss를 0으로 하다가 decision boundary를 지나가는 순간인 wx + b가 0 이하로 되는 순간 loss를 1로 하는 것이다.

그러나 이는 너무 단순하므로, Hinge loss라고 하는 function을 사용할 수도 있다. 파란색 직선과 decision boundary의 margin은 항상 1이다. 동일하게 상단에서 아래로 이동한다고 생각할 때, 파란색 선을 지날 때부터 loss가 error case와의 거리에에 따라 점차 증가하는 선을 따라간다.

이를 수식적으로 표현하기 위해 slack variable이라는 개념을 도입한다. 즉 오분류되었을 때, 오류의 정도를 slack으로 관리한다는 것이다. C는 slack parameter를 얼마 정도의 강도로 적용할 것인지에 대한 값이다. slack($\xi_j$) 를 다 합한 것을 최소화하는데, 원래 $ (wx_i + b)y_i >= 1 $ 이었으나 여기에 slack 을 추가하여 $ (wx_i + b)y_i >= 1 - \xi_i :,: \xi_i >= 0 $ 로 만들어준다. 이렇게하면 quadratic programming을 수행하는데에는 적합하나, C라는 파라미터가 추가되었기에 더 복잡해질 수가 있다.

 

이렇게 slack variable을 추가하여 decision boundary를 결정짓는 모델을 soft-margin SVM이라 한다. 그래프와 같이 파란색 점이 어디에 위치하냐에 따라 slack variable 값이 달라지는데, 파란색 선보다 위에서는 0, desicion boundary와 파란색 선 사이에서는 0~1 사이의 값, decision boundary보다 아래로 내려가게 되면 1보다 큰 slack variable을 가지게 된다. 이러한 slack variable을 추가함으로써 다소 soft한 모델을 만들 수 있게 되었다. 최종적인 패널티값은 C x $ \sum_j \xi_j $ 이다.

 

logistic function에 대한 loss function은 log loss가 있다. 예전에 optimization을 위해 log를 씌워 연산을 수행했다. argmax 안에 log부분이 logistic function인데, 이 부분을 풀어보면, $ Y_iX_i\theta - log(1 + e^{X_i\theta})$ 가 되는데, 여기의 log부분이 아까 배웠던 slack variable과 비슷한 역할을 한다. 이 log부분은 그래프에서의 파란색 형태의 loss function을 가지고 있다.

logistic function과 SVM을 비교하기는 힘드나, SVM이 더 최근에 나왔다.

 

이 때, C값을 어떻게 결정짓냐에 따라 모델이 큰 차이를 보인다. C가 작으면, 패널티가 작아져서 decision boundary를 넘어가더라도, 영향이 크지 않게 된다. 그래서 C를 키웠더니 C가 특정값 이상이 되면 decision boundary가 고정이 된다. 그렇다면, C를 아주 크게 잡아놓고 진행을 하는 것이 무조건 좋을 수 있으나, 새로운 데이터에 대해 decision boundary가 얼마나 신뢰도가 큰지에 대해 다시 생각을 해봐야 하므로 많은 시행착오가 필요하다.

 

 

5-3. Kernel Trick

이때까지는 linear한 decision boundary에 대해 공부했다. soft-margin decision boundary는 decision boundary를 넘어가는 점에 대해 error term으로 처리하고 선형으로 decision boundary를 설정했다. 그러나 만약 한 개의 점만이 아닌, 연속적으로 불규칙한, 즉 선형으로 설명할 수 없는 데이터가 있다고 하면, error term으로 설명하기 어렵다.

일전에 linear regression에서 단순히 linear regression만이 아닌, 임의로 차수를 높여 non-linear regression을 수행해보았다.이러한 테크닉을 동일하게 적용하여 non-linear한 decision boundary를 구할 수도 있다.

 

간단하게 얘기해서, decision boundary를 구할 때는 (x1, x2)에 대해 식을 세웠다. 이 x1, x2를 임의로 제곱, 세제곱하거나 두 값을 곱하는 등의 테크닉을 통해 차수를 높여준다. 그렇게 하여 오른쪽 하단에 위치한 그래프처럼 non linear 한 decision boundary를 구할 수 있다.

 

위에서는 3차까지 늘렸지만, 이를 무한대까지 늘리는 방법이 있을까? 이를 위해 사용하는 기법이 kernel trick이다. 이 kernel trick을 사용하기 위해서는 optimization을 정확하게 이해하고 있어야 한다. 간략하게 얘기하면 prime problem과 dual problem이 있을 때, 이 두개가 같은 성질을 가진 문제라고 정의하고 optimization을 할 수 있다.

 

SVM의 경우 primal problem에 해당하고, kernel을 도입하기 위해서는 이 prime을 dual problem로 바꿔줘야 한다. SVM은 quadratic programming을 통해 optimization을 수행했다. 이를 dual problem으로 바꾸기 위해서는 Lagrange method 라는 것을 잘 이해해야 한다.

SVM에서 optimization을 수행하는 식을 아래와 같이 정의할 수 있다.

• $ min_x f(x) $
• s.t. $ g(x) \leq 0,: h(x) = 0 $

이 때, Lagrange method에서의 Prime Function L에 대해 $ L(x, \alpha, \beta) = f(x) + \alpha g(x) + \beta h(x) $ 로 정의하여 g(x)와 h(x)를 f(x)로 포함시킬 수 있다. 이 때 단순하게 포함시키는 것이 아닌 alpha와 beta라는 Lagrange Multiplier 라는 상수를 정의하여 포함시키는 것이다. 이 때의 alpha는 0보다 크거나 같아야 한다.

이를 통해 Lagrange Dual Function d를 Lagrange Prime Function을 활용하여 정의할 수 있다.

\[d(\alpha, \beta) = inf_{x \in X} L(x, \alpha, \beta) = min_x L(x, \alpha, \beta)\]

이 식을 통해, optimization ($ max_{\alpha \geq 0, \beta} L(x, \alpha, \beta) $)을 풀 때, 특정 범위 내에서는 f(x)와 동일하게 동작하는 성질이 있다. 따라서 optimization이 되어 있는 Lagrange Prime Function을 f(x)와 동일하게 사용하겠다, 즉 f(x) 대신 optimization 식을 쓰겠다는 것이 primal problem에서 dual problem으로 넘어가는 과정이다.

 

정리하면, Primal problem에서의 optimization 식은 $ g(x) \leq 0, h(x) = 0 $ 일 때, $ min_x f(x) $ 이고, 이를 Lagrange Prime Function으로 변환하면 $ min_x max_{\alpha \geq 0, \beta} L(x, \alpha, \beta) $ 가 된다.

Dual Problem 관점에서 바라보면, dual function을 정의하여 optimization을 수행한다. optimization 식은 $ \alpha > 0 $ 일 때, $ max_{\alpha > 0, \beta} d(\alpha, \beta) $ 이고, 이를 앞서 정의했던 식을 통해 d를 치환하면 $ max_{\alpha \geq 0, \beta} min_x L(x, \alpha, \beta) $ 이 된다.

 

여기서 가장 중요한 것은 Strong duality 라는 개념이 만족되어야 한다. dual function에서 나온 solution과 원래 가지고 있었던 Prime function이 같게 되어야 한다는 것이다.

\[d* = max_{\alpha \geq 0, \beta} min_x L(x, \alpha, \beta) = min_x max_{\alpha \geq 0, \beta} L(x, \alpha, \beta) = p*\]

 

이 strong duality를 보장해주는 조건이 바로 KKT Condition 이다. 즉 지금까지는 Prime Function으로 문제를 풀어왔는데, 이를 Dual Function으로 풀고자 하고, 이 dual function으로 만들고자 할 때 만족해야 하는 조건이 KKT Condition이다.

KKT condition

• $ \triangledown L(x^, \alpha^, \beta^*) = 0 $
• $ \alpha^* \geq 0 $
• $ g(x^*) \leq 0 $
• $ h(x^*) = 0 $
• $ \alpha* g(x^*) = 0 $

 

이 strong duality와 kkt condition은 어려운 개념이므로 따로 공부를 해야 할 것이다. 이 강좌에서는 중요한 부분이 아니므로 빠르게 넘어간다.

 

SVM에 Lagrange dual problem을 적용해보고자 한다. 먼저 SVM에서의 optimization은 $ (wx_i + b)y_i \geq 1 $ 에 대해 $ min_{w,b} ||w|| $ 이다. 이 때, 1을 좌항으로 넘겨 g(x)를 정의하고, ||w|| 를 f(x)로 정의한다. 이 때, Prime Problem에서의 optimization은 $\alpha_j \geq 0 $ 에 대해 $ min_{w,b}max_{\alpha \geq 0, \beta} \frac{1}{2}w \cdot w - \sum_j \alpha_j [(wx_j + b)y_i - 1] $ 이다. 이 min과 max의 위치를 바꿔주어 $ max_{\alpha \geq 0, \beta}min_{w,b} \frac{1}{2}w \cdot w - \sum_j \alpha_j [(wx_j + b)y_i - 1] $ 로 하고, KKT Condition을 가져와서 optimization을 단순화할 것이다. KKT에서 사용할 조건들은 다음과 같다.

• $ \triangledown L(x^, \alpha^, \beta^*) = 0:=>: \cfrac{\partial L(w,b,a)}{\partial w} = 0, \cfrac{\partial L(w,b,\alpha )}{\partial b} = 0:=>: w = \sum_j \alpha_j x_jy_j,:\sum_j \alpha_j y_j = 0 $
• $ \alpha_i ((wx_i + b)y_i - 1) = 0 $

 

그 후, Lagrange Prime Function 을 풀어보자.

푸는 과정에서 위에서 정의했던 KKT의 조건들을 사용했다. 이렇게 최종적인 식을 구했는데, 첫번째 항은 linear한 항이고, 두번째 항은 square한 항이므로 quadratic programming을 적용하여 alpha를 구할 수 있다.

만약, $ \alpha_j $를 알고 있다면, w와 b를 쉽게 구할 수 있다. 그러나 이렇게 구했지만 아직 linear한 decision boundary에 머물러 있다.

 

 

다음으로 넘어가기 전에 kernel 이라는 것을 먼저 살펴보자. kernel은 두 벡터의 내적(inner product)로 계산하는데, 이 두 벡터는 다른 space 상의 vector를 의미한다.

$ K(x_i, x_j) = \varphi(x_i) \cdot \varphi(x_j) $

x_i와 x_j를 다른 차원으로 보낸 후의 내적을 한 것이 kernel이다. 이런 식으로 정의할 수 있는 kerenl의 종류는 다양하다.

• Polynomial(homogeneous)
  • $ k(x_i, x_j) = (x_i \cdot x_j)^d:,:: (d : degree) $
• Polynomial(inhomogeneous)
  • $ k(x_i, x_j) = (x_i \cdot x_j + 1)^d $
• Gaussian kernel function (Radial Basis Function)
  • $ k(x_i, x_j) = exp(- \gamma ||x_i - x_j||^2) $
• Hyperbolic tangent (Sigmoid Function)
  • $ k(x_i, x_j) = tanh(kx_i \cdot x_j + c) $

이러한 kernel들이 처음 정의했던 $ \varphi $ 에 대한 식이 되는지 살펴보자.

degree가 1일 때의 polynomial을 구한다면,

\[K(<x_1, x_2>, <z_1, z_2>) = <x_1^2, \sqrt{2}x_1x_2, x_2^2> \cdot <z_1^2, \sqrt{2}z_1z_2, z_2^2> = (x_1z_1 + x_2z_2) = (x \cdot z)^2\]

 

degree가 2일 때의 polynomial을 구하면,

\[K(<x_1, x_2>, <z_1, z_2>) = <x_1^2, \sqrt{2}x_1x_2, x_2^2> \cdot <z_1^2, \sqrt{2}z_1z_2, z_2^2> = x_1^2z_1^2 + 2x_1x_2z_1z_2x_2^2z_2^2 = (x_1z_1 + x_2z_2)^2 = (x \cdot z)^2\]

 

따라서 degree가 n일 때의 polynomial kernel function은 $ K(<x_1,x_2>, <z_1, z_2>) = (x \cdot z)^n $ 이다. x와 z를 먼저 내적해서 다른 차원으로 보내는 것이나, 다른 차원으로 먼저 보낸 후 내적을 한 것이나 결과가 같게 된다. 그러면 10차원 100차원 무한대 차원까지 증가시켰을 때의 계산도 간편하게 할 수 있다.

 

 

이제 다시 SVM으로 돌아가서 optimization식에 x_i, x_j를 Kernel을 적용하여 nonlinear하게 진행해보자.

$ max_{a \geq 0} \sum_j \alpha_j - \frac{1}{2}\sum_i \sum_j \alpha_i \alpha_j y_i y_j \varphi(x_i), \varphi(x_j) = max_{a \geq 0} \sum_j \alpha_j - \frac{1}{2}\sum_i \sum_j \alpha_i \alpha_j y_i y_j K(x_i, x_j) $

또한, w,b에 대해서도 정의할 수 있다.

$ w = \sum_{i=1}^N \alpha_i y_i \varphi(x_i) $

$ b = y_i - \sum_{i=1}^N \alpha_i y_i \varphi(x_i) \varphi(x_j) $

 

이 때, w에 대해서는 kernel trick을 사용할 수가 없다. 그러나 전체적으로 다시 생각해보면, 우리의 최종 목표는 w와 b를 구하는 것이 아니라, 이 w와 b를 통해 만들어진 decision boundary를 통해 분류를 잘 하는 것이다. 즉, w와 x,b가 있는 식에 x를 집어넣어서 +가 나오면 positive case, -가 나오면 negative case로 분류하기 위함이다.

그래서 다시 처음으로 돌아가서 wx + b라는 식에서 x를 다른 차원으로 보내어 식을 세워보면 $ w \varphi(x) + b $ 이 되는데, 이는 kernel trick을 사용할 수 없다. 그러나 이 식을 풀어보면

\[sign(w \varphi(x) + b) = sign(\sum_{i=1}^N \alpha_i y_i \varphi(x_i) \cdot \varphi(x_i) + y_j - \sum_{i=1}^N \alpha_i y_i \varphi(x_i) \varphi(x_j)) = sign(\sum_{i=1}^N \alpha_i y_i K(x_i, x) + y_j - \sum_{i=1}^N \alpha_i y_i K(x_i, x_j))\]

이 때, sign은 안에 식이 양수이면, 1 음수이면 -1, 0이면 0으로 반환해준다.

• > 0 : 1
• < 0 : -1
• = 0 : 0

 

KKT condition에 의해 생성된 식에 의해 결국 kernel trick을 사용할 수 있게 된다. 예전처럼 w,b를 직접적으로 구할 수는 없지만 위의 식을 통해 classifier를 할 수 있다.

 

4차원에 대한 kernel을 적용한 예와 RBF라는 알고리즘을 적용한 예시이다.

 

 

logistic regression에 kernel을 적용한 예이다.

 

Chapter 6. Training / Testing and Regularization

• 목차

1. concept of bias and variance
   • overfitting, underfitting
   • to segment bias, variance of error
2. trade-off between bias and variance
   • concept of Occam’s razor
   • cross-validation
   • various performance metrics for supervised machine learning
3. concept of regularization
   • apply regularization to
   • Linear regression
   • Logistic regression
   • Support Vector Machine

 

 

6-1. Concept of bias and variance

Naive Bayes, Logistic Regression, SVM 등 다양한 classifer를 배웠고, SVM의 경우 아직도 많이 사용되는 ML 알고리즘이다. 더 나은 ML 알고리즘이란 성능이 좋은 것일텐데, 이를 어떻게 평가할 수 있을까? 성능에 영향을 끼치는 것은 정확도와 데이터셋이다.

정확도는 precision/Recall이나 F-Measure 값을 통해 성능을 평가할 수 있다. 데이터셋은 True/False의 비율이 어떤지, 분산이 작은지에 따라 데이터셋의 타당성을 평가할 수 있다.

 

머신러닝에서 Training과 Testing이라는 것이 존재한다. Training이란 사전 정보와 이전 경험을 통해 모델의 파라미터를 학습시키는 과정이다. Decision tree나 SVM 등과 같은 ML 알고리즘이 현재에 잘 사용되지 않는 이유는 훈련 데이터셋에 존재하지 않는 값에 대해서는 잘 분류를 하지 못하기 때문이다. Testing은 학습시킨 ML 알고리즘과 파라미터를 테스트하는 과정이다.

 

훈련하는 과정에서 파라미터들이 training 데이터셋에 대해 regression을 하는데, training 데이터셋에 너무 많이 fitting 되어 있는 모델을 overfitting이라 하고, 너무 적게 fitting 되어 있는 모델을 underfitting이라 한다. 그렇다면, 얼마나 complex하게 model을 만들어야 할까?

 

훈련된 ML 알고리즘의 estimation error, Eout은 approximation error, Ein와 데이터의 variance로 인해 발생되는 error의 합보다 크다.

\[E_{out} \leq E_{in} + \Omega\]

 

어떤 모델을 정의해보자.

• f : true function
• g : ML training function
• $ g^{(D)} $ : dataset D를 통해 학습된 function
• D : dataset
• $ \bar{g} $ : 수많은 모든 데이터셋을 관찰하였을 때의 평균적인 hypothesis
  • $ \bar{g}(x) = E_D [g^{(D)}(x)]$
  • $ E_D $는 무한히 많은 데이터셋을 의미한다.

single instance of dataset D에 대한 Error를 $ E_{out}(g^{(D)}(x)) = E_x[(g^{(D)}(x) - f(x))^2] $ 라 정의할 수 있다. Ex는 expected error를 의미한다.

무한히 많은 수의 데이터셋 D에 대한 expected error는 $ E_D[E_{out}(g^{(D)}(x))] = E_D[E_x[(g^{(D)}(x) - f(x))^2]] = E_x[E_D[(g^{(D)}(x) - f(x))^2]] $

Ex 안 부분을 간편하게 표현하기 위해 $ \bar{g}(x) $ 를 추가하여 표현한다. 그리고 나서, 제곱을 풀어준다.

\[E_D[(g^{(D)}(x) - f(x))^2] = E_D[(g^{(D)}(x) - \bar{g}(x) + \bar{g}(x) - f(x))^2] = E_D[(g^{(D)}(x) - \bar{g}(x))^2 + (\bar{g}(x) - f(x))^2 + 2(g^{(D)}(x) - \bar{g}(x))(\bar{g}(x) - f(x))] = E_D[(g^{(D)}(x) - \bar{g}(x))^2] + (\bar{g}(x) - f(x))^2 + E_D[2(g^{(D)}(x) - \bar{g}(x))(\bar{g}(x) - f(x))]\]

이 때, $ g^{(D)}(x) $ 를 무한대로 학습시킨 것의 평균이 g_bar이므로, $ \bar{g}(x) = E_D [g^{(D)}(x)] $ 라 정의했다 따라서, $ E_D[2(g^{(D)}(x) - \bar{g}(x))(\bar{g}(x) - f(x))] = 0 $ 이다.

 

최종적인 error는 다음과 같다.

\[E_D[E_out(g^{(D)}(x))] = E_x[E_D[(g^{(D)}(x) - \bar{g}(x))^2] + (\bar{g}(x) - f(x))^2]\]

 

이 식에서 Veriance 와 Bias를 정의한다.

• $ Variance(x) = E_D[(g^{(D)}(x) - \bar{g}(x))^2] $
• $ Bias^2(x) = (\bar{g}(x) - f(x))^2 $

다양한 모든 데이터셋을 알고 있나는 가정하에 만든 hypothesis인 g_bar는 $ g^{(D)}(x) $ 를 무한대로 증가시킨 것이므로, 이 둘의 차이를 variance라 표현한다. 그리고, 아무리 approximation을 해도 true function과는 반드시 다를 것임에는 분명하므로, 우리가 가진 모델의 한계점에 의해 생길 수 있는 error를 Bias라 표현할 수 있다.

이 때, bias를 줄이기 위해 g_bar의 차수를 무수히 높여서 bias를 줄인다면 variance가 증가하므로 bias와 variance는 trade-off 관계이다.

variance를 줄이기 위해서는 더 많은 데이터를 수집해야 하고, bias를 줄이기 위해서는 더욱 더 복잡한 모델을 만들어야 한다.

 

 

6-2. Performance measurement

true function을 sin(2*pi*x)라 가정하고, 이에 대한 bias와 variance를 생각해보자.

점 2개를 사용하여 linear regression을 한다고 가정할 때, 기울기를 가진 직선으로 regression을 하는 방법과 constant한 기울기가 존재하지 않은 y = c 형태의 함수로 regression 할수도 있을 것이다. 전자의 경우가 초록색 선일 것이고, 후자가 빨간색 선이다. 이 경우는 점 2개가 적절하게 구성되어 초록색 선이 적합할 수 있지만, 만약에 x = 0.1 과 0.2 위치에서의 점 2개로 데이터가 구성된다면 우상향되는 직선이 estimated될텐데, 이러한 경우 x = 0.7 부분에서 실제 true function과의 error가 매우 클 것이다. 그렇다면, 이러한 경우는 빨간색 선처럼 y = c로 투영하는 것이 안전할 수 있다.

그렇다면 어떤 기준으로 regression을 해야 할까?

초록색 선과 빨간색 선에 대한 각 bias와 variance를 살펴보면, 빨간색 선의 경우 bias가 다소 높지만, variance는 작다. 초록색 선의 경우 bias는 다소 작지만, variance가 높다.

따라서 이 둘의 balance가 중요할 것이다.

 

• Occam’s Razor

Occam’s Razor라는 개념이 있다. 이는 비슷한 error를 가진 hypothesis에 대해서는 가장 단순한 모델을 선정하라는 것이다. 우리가 true function을 모른 채로 아래 3가지의 hypothesis가 존재하고, 3개 모두 error가 동일하다면, 가장 단순한 underfitting인 hypothesis를 선정하는 것이 가장 적합하다.

 

 

• Cross Validation

이전에 $ \bar{g}(x) $ 를 생성하기 위해서는 무수히 많은 데이터셋이 필요했다. 그러나 현실에서 우리는 무수히 많은 데이터셋을 생성할 수 없으므로, 가지고 있는 데이터셋을 N개의 subset으로 분할하여 사용하여 최대한 $ \bar{g}(x) $ 와 비슷하게 구성할 것이다. 이를 위해 사용되는 개념이 N-fold cross validation 이다. N개의 subset으로 나눈 후, N-1개의 subset은 training에 사용하고, 1개는 testing에 사용한다. 이 과정을 총 N번, 즉 모든 subset에 대해 1번씩 test를 진행한다.

가장 최소단위로 subset을 구성한다면 당연히 instance가 1개인 경우이므로 이러한 경우를 LOOCV(Leave One Out Cross Validation) 이라 한다.

 

 

• Performance Measure method

현실에서 우리는 true function을 알수가 없고, 무수히 많은 데이터셋을 생성할 수 없기에 average hypothesis도 계산할 수 없다. 그러므로 우리는 bias와 variance를 성능 평가에 사용할수가 없다.

그러나 반드시 성능을 평가해야 하므로, 다른 방법을 사용한다.

1. Precision and Recall

첫번째 방법으로는 precision and recall 이 있다. 예를 들어, 오른쪽 표처럼 현실에서의 true와 false가 존재하고, 우리가 true 또는 false라 예측한 값인 positive/negative가 존재할 때, 다음과 같이 case를 나눌 수 있다.

만약 우리의 task가 spam filter와 VIP classifer 두 가지가 존재한다면, spam filter의 경우 안전이 우선시 되어야 할 것이다. VIP classifer의 경우는 정확도가 우선시되어야 한다. spam filter은 안전, 즉 스팸이 아닌 것(False)을 스팸이라 분류(Positive)하는 경우를 가장 예방해야 하고, VIP classifier는 VIP(True)를 아니라고 분류(Negative)하는 경우를 가장 예방해야 한다. 따라서 전자는 FP를, 후자는 FN을 줄이는 것을 우선시해야 한다.

 

평가 지표로서 precision과 recall을 다음과 같이 정의할 수 있다.

• Precision : TP / (TP + FP)
• recall : TP / (TP + FN)

filtering은 Precision을, recall은 Recall을 사용하여 평가하는 것이 좋다.

 

1. F-Measure

precision과 recall의 밸런스를 측정하는 것도 중요하므로 그에 대해 수식을 다음과 같이 정의할 수 있다.

• $ F_b-Measure = (1 + b^2) \times (Precision \times Recall) / (b^2 \times Precision + Recall) $
• $ F_1-Measure = (1 + 1^2) \times (Precision \times Recall) / (1^2 \times Precision + Recall) $

b는 precision에 대한 중요도로, b를 낮게 할지, 높게 할지에 따라 recall을 강조할지, precision을 강조할지 선택할 수 있다.

 

1. ROC curve

ROC(Receiver Operating Characteristic) curve는 True Positive Rate와 False Positive Rate에 대한 값을 그래프로 나타낸 것이다. ROC 커브가 좌상단에 붙을수록 더 좋은 분류기이다.

ROC curve에서 볼 수 있는 특성은 크게 3가지가 있다.

1. True Positive Rate와 False Positive Rate
2. ROC Curve위의 한 점이 의미하는 것은?
3. ROC Curve의 휜 정도가 의미하는 것은?

먼저 FPR(False Positive Rate)와 TPR(True Positive Rate)는 ROC curve에서 각각 x,y축에 표시되는 값이다. FPR과 TPR은 위에 나온 precision과 recall에 대한 표에 나온 F/T/P/N과 동일한 값을 의미한다.

그 다음, ROC Curve를 살펴보면, 그래프 위에 하나의 점이 존재한다. 이 점은 decision boundary를 의미한다.

ROC Curve의 휜 정도는 구별하는 정도를 의미한다. 즉 커브가 많이 휠수록 더 잘 분류한다는 의미가 된다.

참고 : https://angeloyeo.github.io/2020/08/05/ROC.html

 

 

6-3. Model Regularization

regularization이란, 모델을 너무 완벽하게 fit하지 않겠다, 즉 training dataset에 대해 정확도를 줄이기 위한 기법이다. 이를 통해 test에 대한 잠재적 fit을 증가시킬 수 있다.

 

regularization에는 L1, L2 등의 방법이 있다.

• L1 regularization(Lasso regularization) : $ \lambda |w| $
• L2 regularization(Ridge regularization) : $ \frac{\lambda}{2} ||w||^2 $

이외에도 Bridge라는 방법도 존재하긴 하나, 가장 많이 사용되는 것은 L2 이다. 그 이유는 아래 그래프에서 좌상단에 parameter space가 존재하고, 최적화를 할 때마다 영역이 점점 커진다고 생각할 때, 중간의 도형과 paramter space가 접하는 지점에 대해 optimization이 진행된다. 따라서 Lasso의 경우는 4개의 꼭지점에서만 parameter가 존재할 수 밖에 없으므로 제한적이다. 그러나 ridge의 경우는 원이므로 다양한 paramter가 존재할 수 있게 된다.

• ridge loss function : $ \frac{1}{2} \sum_{n=0}^N (train_n - g(x_n, w))^2 + \frac{\lambda}{2}||w||^2 $

• lasso loss function : $ \frac{1}{2} \sum_{n=0}^N (train_n - g(x_n, w))^2 + \lambda|w| $

 

ridge regularization을 활용하여 linear regression을 살펴보자. w를 계산하기 위해 w에 대해 loss function을 편미분하면 다음과 같다.

\[\frac{d}{dw} E(w) = 0\] \[\frac{d}{dw} E(w) = \frac{d}{dw} (\frac{1}{2} ||train - Xw ||^2 \frac{\lambda}{2}||w||^2)\]

이를 정리하여 미분하고, w에 대해 정리한다.

\[w = (X^TX + \lambda I)^{-1}X^T \cdot train\]

train은 y label을 의미한다.

 

regularization이 적용되지 않았을 때와 적용되었을 때의 차이를 살펴보면 위의 그래프와 같다. 모델의 복잡도를 높이지 않고도 bias는 약간 증가하고, variance가 상당히 감소되었음을 알 수 있다.

 

regularization에 $ \lambda $ 를 조절하여 강도를 조절 할 수 있다. $ \lambda $ 가 너무 작으면 variance는 높고, $ \lambda $ 가 너무 작으면 variance도 너무 작아진다. 따라서 적합한 regularization의 강도를 찾아야 하므로 이에 대해 수많은 실험을 통해 최적화를 수행해야 한다.

 

 

• regularization of Logistic Regression

logistic regression에 대해서도 regularization을 추가할 수 있다.

\[argmax_\theta \sum_{i=1}^m log(p(y_i \| x_i, \theta)) - \alpha R(\theta)\]

 

\[L1 : R(\theta) = ||\theta||_1 = \sum_{i=1}^n |\theta_i |\] \[L2 : R(\theta) = ||\theta||_2^2 = \sum_{i=1}^n \theta_i^2\]

logistic regression을 수행할 때, closed form이 아니기에 approximation을 수행해야 했다. 따라서 regularization에 대해서도 gradient descent/ascent 를 수행하여 최적화를 할 수 있다.

 

• regularization and SVM

SVM에서는 regularization과 유사한 기능을 하는 term이 있었다. 그것은 C로 지난 주에 C를 조절하면서 decision boundary가 어떻게 변하는지를 살펴보았었다. C는 soft-margin을 감안했을 때 추가되는 값이므로 soft-margin을 가정하면 자동적으로 regularization이 추가된다고 생각할 수 있다.