Lecture 10 - Feature/Model Selection

모델의 복잡도$($Complexity measures$)$

 

모델은 복잡도는 다음 두 요소와 관련되어 있다.

 

• 파라미터의 수
• 파라미터의 노름

Regularization

 

머신러닝에서 규제는 학습 과정에서 우리가 가진 training 데이터셋에 대한 overfitting 정도를 줄이고, 일반화 성능을 높이기 위한 도구이다. 학습 과정에서 규제는 $J(\theta) + \lambda R(\theta)$에서 $\lambda R(\theta)$ 항이다. 여기서 $\lambda$는 규제 $R$의 중요도를 조절하는 하이퍼파라미터이다.

 

규제로 사용되는 함수는 여러 가지가 있으나, 대표적으로 두 개를 따지자면 L1/L2 regularization이다. L1 regularization은 Lasso라고도 하며, $R(\theta) = ||\theta||_0 = \sum_{i=1}^{n} [\theta_i = 1]$이다. Lasso의 특징은 파라미터 중 별로 중요하지 않은 파라미터를 0으로 만든다는 것이다. L2 regularization은 Ridge라고도 하며, $R(\theta) = \frac{1}{2} ||\theta||_{2}^2$이다. 사실 요즘은 다 L2 쓴다고 한다. 현실에서 많은 특성이 0인, 즉 sparse한 경우가 많이 없기 때문이다.

 

Implicit Regularization Effect

 

저번 강의에서 약간 나왔었던, Implicit Regularization Effect가 다시 나왔다. 이 효과는 '최적화 알고리즘이 규제항을 명시적으로 추가하지 않아도 규제가 자연스럽게 적용될 수 있다'는 것이다. 예를 들어, 저번에 설명했었던 Double Descent 효과가 있다. 이것을 Linear Model에서 예시를 보면서 왜 효과가 발생하는지 추론해보자.

 

Linear model에서 데이터셋과 손실 함수를 각각 $(x_i, y_i) \sim D$, $J(\theta) = \frac{1}{n} \sum_{i=1}^{n} (y^{(i)} - \theta^Tx^{(i)})^2$ 로 세팅하자. 그 뒤로 $|D| = n$, $x_i$의 차원 $ = d$라고 하고, underfitting이 주두 가지 경우로 나눠보자.

 

1. $n = d$

 

$n = d$이면 저번에 보았듯이 overfitting이 발생하기 쉽다. 왜일까? 왜인지 알려면 $\sum_{i=1}^{n} (y^{(i)} - \theta^Tx^{(i)})$에 집중해야 한다. 데이터셋이 $n$개이므로 $(y^{(i)} - \theta^Tx^{(i)})$ 식은 n개가 발생한다. $x_i$의 차원은 $d$이므로 저 식의 변수의 개수는 $d = n$이다. 변수의 개수와 식의 개수가 동일하므로 $y = \theta X$에서 $J(\theta) = 0$을 만족하는 $\theta$가 유일해지고, 결론적으로 training dataset에서만 잘 작동하므로 과적합되기 쉬워진다. 

 

2. $n \ll d$

 

위에서 설명했듯이 식은 $n$개, 차원의 개수는 $d$개이다. 그런데, $n \ll d$이므로 $J(\theta) = 0$을 만족하는 $\theta$가 unique하지 않고 무한히 많아진다. 그런데 해 중에서도 안좋은 해가 존재하지 않을까? 그런데 왜 상대적으로 좋은 결과를 내놓는 경우가 많을까? 그걸 알기 위해선 우리는 아래의 명제에 답해야 한다.

 

• Gradient Descent를 $\theta = 0$에서 시작할 경우 최소 노름 해$(\mathbf{argmin} ||\theta||_{2}^2)$에 수렴한다.

 

Proof

 

Gradient Descent 과정을 요약해보면 다음과 같다.

 

$\theta \leftarrow 0$

while not converge

    $\theta \in \mathbf{span} \{x^{(1)}, \cdots, x^{(n)} \}$ (증명은 Kernel 부분을 읽으면 알 수 있다.)

 

이때 $J(\theta) = 0$ 을 만족하는 영역은 hyperplane이 되고, $\theta$도 특정한 방향으로만 업데이트되므로, 평면에 가까워면서 $\theta = 0$에 가장 가까운 $J(\theta) = 0$ 영역에 도달하게 된다. 

 

단, SGD 또는 non-linear model은 위의 명제가 성립하지 않을 수 있다.

 

Test set

 

생각해보면 규제를 볼 때 hyperparameter은 어떻게 조정할 지 궁금할 수도 있다. 우리는 이때까지 training set / test set으로 나누었지만, 이제는 hyperparameter를 위한 validation set도 고려해서 training set / validation set / test set 이렇게 3개로 구분한다. 

 

그런데, validation set의 결과가 test set의 일반화 성능도 보장할까? 정답만 말하자면, 일반적인 경우에 보장한다. 버클리 대학교에서 kaggle 대회를 분석하다가 나온 결과라고...