uncategorized

Regularization and model selection

다음과 같은 hypothesis $h_\theta(x)=g(\theta_0 + \theta_1 x + \ldots + \theta_k x^k)$ 가 있을때 $k$를 몇으로 해야 할지 어떻게 정할수 있을까? 즉 몇차로 식을 만드는게 bias / variance trade off 에 있어서 가장 좋은 모델일까를 어떻게 알수 있을까?
조금 구체적으로 이해 하기 위해 유한개의 모델을 다음과 같이 정의하겠다. $M={M_1, \ldots, M_d}$ 여기서 $M_i$는 $i$차수의 다항 회귀 모델이다.

1. Cross Validation

training set $S$가 있다면 우리는 empirical risk minimization 알고리즘에 의해 다음과 같은 과정을 거쳐 최적의 hypothesis를 찾는다.

  1. 데이터셋에 각각의 $M_i$ 모델을 적용한후 hypothesis $h_i$를 얻는다.

  2. 가장 낮은 training error를 낸 hypotheses 를 선택한다

위의 방법은 효과적이지는 않다.
분명 높은 차수의 hypothesis가 더 낮은 training error를 발생 시킬것이기 때문이다. 따라서 이 방법은 항상 높은 variance, 높은 차수의 hypothesis가 선택 될것이다.

더 효율이 높은 알고리즘은 Cross validation 방법이다. 방법은 다음과 같다.

  1. 랜덤하게 데이터셋 $S$를 70%는 $S_{train} : $ training 데이터로, 나머지 30% $S_{cv}$(hold out cross validation set)으로 나눈다.

  2. hypothesis $h_i$를 얻기 위해 $S_{train}$ 데이터만 사용한다.

  3. 그리고 가장 작은 에러($\hat \epsilon_{S_{cv}}$)를 낸 hypothesis를 선택하면 된다. (여기서 $\hat \epsilon_{S_{cv}}$ 는 $S_{cv}$ 데이터에 대한 empirical error를 나타낸 것이다.)

$S_{train}$ 데이터로 학습하며 얻은 $h_i$로 학습할때 사용하지 않았던 $S_{cv}$로 테스트를 해보면 $h_i$의 true generalization error를 측정할수 있다. 그 다음 가장 작은 generalization error를 가진 hypothesis를 선택하면 된다. 보통의 경우 데이터의 $1/4, 1/3$ 정도를 cross validation set으로 사용한다.

하지만 위 방법은 30% 정도의 data를 training 할때 쓰지 못한다는 단점이 있다. 학습 할때 즉 항상 $0.7m$의 데이터만 사용하고 전체 데이터 $m$을 사용을 못한다는 것이다. 물론 충분한 엄청 많은 데이터가 있다면 상관없지만…

데이터가 충분하지 않다면 다음 K-fold Cross Validation 방법을 쓰는것이 조금더 데이터를 활용할수 있을것이다.

  1. 렌덤하게 데이터 $S$를 $m/k$개로 이루어진 데이터 $k$개로 나눠 준다. 그리고 각각의 데이터 셋을 $S_1, S_2, \ldots, S_k$로 지정한다.

  2. 각각의 모델 $M_i$ 에 대해 다음을 실행한다.

    • For $j = 1, 2, \ldots, k$

      • S_j 데이터 셋만 제외하고 나머지 데이터 $S_1 \cup \cdots \cup S_{j-1} \cup S_{j+1} \cup \cdots S_k$ 를 가지고 학습을 시킨다음 $h_{ij}$ hypothesis를 얻는다. 그리고 나서 $S_j$데이터를 가지고 테스트를 한후 $\widehat \epsilon (S_j)$ 를 찾는다
    • $M_i$의 generalization error는 $\widehat \epsilon (S_j)$ 평균으로 구한다.

  3. generalization error가 가장 낮은 $M_i$을 구한 다음 다시 전체 데이터 셋 $S$를 가지고 재학습을 하여 얻어진 hypothesis가 최종 답이 된다.

데이터를 나눌때 $1/k$로 전 cross validation보다 훨씬 적게 test로 사용되긴 하였지만, 각각의 모델마다 k번의 계산이 필요하기 때문에 계산적으로는 비효율적이다.

이러한 교차 검증 방법은 single model / algorithm을 검증하고 싶을때 사용하면 좋은 검증 방법중에 하나가 될것이다.

2. Feature Selection

model을 선택할때 중요하고 특별한 방법중의 하나가 Feature selection이다. 만약 supervised learning을 하려고 하는데 Feature의 갯수가 너무 많으면 ($n >> m$) 모델의 학습에 관련있는 몇개의 feature 만 선택해야 할것이다. simple한 선형 분류문제를 풀때 많은 수($n$)의 feature가 사용되면, hypothesis class의 VC dimension이 여전히 $O(n)$이기 때문에 학습 데이터가 많지 않은 한 overfitting 문제가 발생할수 있기 때문이다.

만약 n 개의 features가 있다면 feature를 사용할 모든 경우의 수는 $2^n$이 될것이다.

feature selection 방법중에 forward selection는 다음과 같다.

  1. $\mathcal{F}= \emptyset$

  2. Repeat {

    (a) For $i = 1, 2, \ldots, n$ $if$ $i \notin \mathcal{F}$, $\mathcal{F_i}=F \cup \{i\}$로 놓는다. $\mathcal{F_i}$를 평가하기 위해 cross validation 한다. generalization error를 구한다.

    (b) step (a)에서 자장 적합한 feature set $\mathcal{F_i}$를 찾는
    }

  3. 전체 과정을 돌고 나서 가장 적합한 feature set을 선택한다.

전체 loop가 종료되는 시점은 The $\mathcal{F}$가 전체 feature set $\{1, \ldots, n\}$이 되었거나, 미리 지정해준 threshold hold $\mid \mathcal{F_i}\mid$ 를 넘었을때이다.

forward selection은 wrapper model feature selection 의 한 예시로 불리기도한다.

forward search 와는 다른 방법인 backward search가 있다. 이 방법은 처음 feature set의 시작을 전체 set $\mathcal{F} = \{1, \ldots, n\}$으로 시작 한다. 그리고 반복적으로 하나씩 feature들을 지워가며 $\mathcal{F}= \emptyset$ 가 될때까지 최적의 feature set을 찾는다.

하지만 이러한 wrapper model feature selection 은 계산 복잡도가 모든 feature set $\mathcal{F} = \{1, \ldots, n\}$ 을 확인할때까지 $O(n^2)$가 된다.

그러한 이유로 비록 heuristic 하긴 하지만, 계산 복잡도가 조금 더 낮은 방법인 Filter feature selection 을 사용할수 있다. 여기서 사용하는 방법은 간단한 점수 $S(i)$를 활용한다. $S(i)$는 하나의 feature $x_i$가 라벨 $y$에 대해 얼마나 정보성이 있느냐의 점수이다. 점수가 큰 feature를 선택하게 된다.

$S(i)$를 측정하는 한가지 방법은 학습 데이터에서 얻은 feature $x$ 와 라벨 $y$간의 서로의 correlation을 점수로 쓰는 것이다. 결국 라벨과 가장 강한 관계가 강한 feature가 점수가 높게 될것이다.

실제로는 특히 feature $x_i$의 값들이 discrete 할때는 $S(i)$를 상호 정보량($MI(x_i,y)$)으로 수치화 하여 사용한다

위의 공식은 $x_i$와 $y$가 binary value로 이루어져 있을때이고,
확률 $p(x_i, y)$, $p(x_i),p(y)$ training data의 empirical distribution에 의해 측정 된것이다

상호 정보량이 KL divergence로 표현될수 있다는 것을 이해하고 있으면 위 식을 조금더 직관적으로 이해할수 있을것이다.

KL divergence 는 확률 분포 $p(x_i, y)$와 $p(x_i)p(y)$가 얼마나 다른지 나타내는 것이다. 만약 $x_i$와 $y$가 서로 independent 하다면 $p(x_i, y) = p(x_i)p(y)$ 가 성립할것이고, 두 분포간의 KL divergence는 0이 될것이다. 또한 $x_i$가 명백히 $y$에 대한 정보량이 없다는 것을 의마기도 한다. 반대로, 만약 $x_i$가 $y$에 대한 정보량이 많으면 그들의 상호 정보량 $MI(x_i,y)$는 매우 클것이다.

자 그러면 스코어 S(i)를 구하고, 몇개의 feature를 사용할것인가를 정해야 한다. 가장 표준적인 방법은 가능한 k의 갯수를 cross validation을 통해서 구하는 것이다.

보통 이방법은 단어의 갯수가 많은 즉 feature의 갯수가 매우 많은 naive Bayes text classification을 할때 feature 갯수를 줄이기 위해 사용한다.

3. Bayesian statistics and regularization

이번에는 overfitting을 피하기 위해 쓰이는 방법을 알아보겠다. 우리는 parameter을 찾기 위해 최대 가능도 (maximum likelihood)를 사용한다.

기존의 최대 가능도 방법은 $\theta$를 random하게 지정하는게 아닌, 모르는 상수로 놓는다.

그러나, maximum likelihood 방법 말고 Bayesian 방법을 이용한 방법을 쓰게 되면 모르는 값 $\theta$를 렌덤하게 놓고, 사전확률 분포 $P(\theta)$를 지정한다.
만약 학습 데이터 셋 $S=\{(x^{(i)}, y^{(i)})\}_{i=1}^m$ 이 주어졌을때 $\theta$를 사후 확률 분포 $P(\theta \mid S)$ 통해 예측한다.

위 식의 $p(y^{(i)}\mid x^{(i)},\theta)$는 learning 문제를 풀때마다 나오는 식이다. 만약 Bayesian logistic regression 문제를 풀면 $p(y^{(i)}\mid x^{(i)},\theta)=h_\theta(x^{(i)})^{y^{(i)}}(1-h_\theta(x^{(i)}))^{(1-y^{(i)})}$ 가 된다.

$h_\theta(x^{(i)})=1/(1+exp(-\theta x^{(i)}))$

새로운 x데이터에 대해 예측을 하려고 한다면 $\theta$의 사후 확률분포를 활용하여 클래스에 대한 사후 확률 분포를 이용해서 구한다

$p(y \mid x, S)=\int_\theta p(y \mid x, \theta)p(\theta \mid S)d\theta$

$E[y \mid x, S] = \int_y yp(y\mid x,S)dy$

x 데이터가 주어졌을때 $\theta$에대한 사후 확률 분포$p(\theta \mid S)$에 관한 y의 평균으로 구할수 있다.

하지만 Bayesian 방법은 $\theta$의 차수가 커지면 커질수록 계산 복잡도가 커지고, closed form도 아니라서 계산이 어렵다는 단점이 있다.

따라서 $\theta$의 사후 확률 분포를 근사하여 구하게 되는데 이 방법을 MAP(maximum a posterior)라고 한다

$\theta_{MAP}=argmax_\theta \prod_{i=1}^mp(y^{(i)}\mid x^{(i)}, \theta)p(\theta)$

MAP 식을 보면 알겠지만 maximum likelihood와 다른 점은 단지 뒤에 $p(\theta)$만 붙어 있다는 것이다. 뒤에 사전 확률 분포가 곱해져 있으므로 ML보다 overfitting에 대해 덜 민감한 장점이 있다

Share