[ML] Subset Selection 1편 (Best Subset Selection, Stepwise Selection)

본 게시글은

서울대학교 데이터사이언스대학원 오민환 교수님의

데이터사이언스를 위한 머신러닝 및 딥러닝1 수업을

학습을 목적으로 재구성하였습니다

---

 

이번 시간과 다음 시간에 배울 내용은

subset selection에 대한 내용이다

 

지금까지는 어떻게 model fit하는지를 배웠다면

이번 시간은 어떻게하면 이 모델에 대해서 subset selection을 할 수 있을까에 대한 내용이다

 

 

 

 

linear regression을 한 번 생각해보자

feature는 여러개이고 parameters는 p+1개이다

 

linear regression 자체가 상당히 strong한 가정이라고 생각할 수 있는데

linear model을 사용하는데에 있어서

데이터가 반드시 linear해야만 linear model을 사용할 수 있는 것은 아니다

 

아예 Linear하지 않더라도 linear regression을 시도해볼 수 있다

linear은 feature와 response간 관계가 linear하다는 것이 아니고

parameter간의 관계가 linear하다는 것이다

 

 

 

그렇다면 한 번 생각해보자

그냥 p개의 feature들이 존재한다면 전부 다 써서

linear regression을 fit 시키면 되는데

왜 우리가 굳이 이 중에 subset을 골라야 하는 걸까?

 

우선 첫번째 단적인 이유는

p가 총 데이터 개수인 n보다 크면 fit을 시킬 수가 없기 때문이다

그렇다면 p가 n보다 작다고 한다면 무조건 다 써도되냐?

그런 것은 또 아니다

각 feature간의 correlation이 있을 때 variance가 엄청 커질 수 있다

그래서 적절히 feature 개수를 줄여도 좋을 수가 있다

예를 들어서 어떤 두 개의 feature가 highly correlated 되어있다면

둘 중 하나만 사용해도 무관하다

 

또 예를 들어서 실제로 n이 100만개

p도 100만개가 있다고 해보자

그럼 이걸 그대로 사용해도 될까?

모델을 해석하는데에 있어서 용이하지 않을 수가 있다

 

아무튼 이러저러한 이유로 feature selection을 해주는 것이 좋다

의무는 아니지만 가능하다면 해주는 것이 좋다

prediction accuracy가 손해를 보지 않는다면 당연히 해주는 것이 좋고

설령 prediction accuracy가 손해를 보더라도

해주는게 모델의 해석력 측면에서 좋을 수 있다

 

 

 

이를 수행하는 방법은 크게 2가지가 있는데

첫 번째는 우리가 오늘 배울 subset selection이다

 

subset selection은 여러 개의 파라미터 p개에서 

가장 response 변수와 관련이 깊을 것 같은 것들만

선별해서 모델을 학습시키는 방법이다

여러 가지 조합의 파라미터들로 모델들을 각각 fit 시키고

그 중에서 좋은 모델들을 선별하는 것이다

 

shrinkage는 전체 파라미터 p개를 한 번에 fit 시키는데

어떤 feature들은 coefficient를 0에 가깝게 만들어서

불필요한 변수들의 영향력을 줄이게 하는 방식이다

이러한 과정을 regularization(정규화)라고도 한다

 

 

 

우선 오늘은 subset selection 방법 중 한 개인

best subset selection에 대해서 알아보자

 

이 방법은 무식한 방법이라서

사실 사용하지 않는 것이 좋다고는 한다

 

우리가 M0을 null model

즉, 상수항만 있고 predictor가 하나도 없는 모델이라고 해보자

그럼 이 친구는 Y값의 mean만 predict 할 수 있는 친구이다

constant 함수이기 때문이다

 

그런 다음 각 p개의 파라미터들을 조합해가며 모델을 fit 시킬 것이다

우선 선택할 파라미터의 개수 k가 1이라고 한다면

전체 p개의 파라미터 중에서 1개만 뽑아서 모델을 fit 시킨다

모든 경우의 수를 다 선택하면 총 p개의 모델이 나오게 될 것이다

그럼 이렇게 파라머티가 1개씩 들어간 p개의 모델 중에서

가장 성능이 좋다고 생각되는 것을 선별하는데

이 때 성능이 좋다고 생각되는 것의 기준은

RSS가 가장 낮다거나, 혹은 R제곱이 가장 높은 것을 선택하면된다

사실 RSS가 가장 낮다면 R제곱이 가장 높게 될 것이므로 큰 상관없다

(어차피 같은 데이터셋에서 하니까 TSS가 모두 동일하기 때문에)

이렇게 k=1에서 뽑힌 모델은 M1이 되는 것이다

 

그런 다음 k=1일 때를 모두 수행해서 모델을 1개 뽑았으면

이후 k=2일 때 동일하게 iteration을 돌면서 수행해준다

그럼 k=2일 때 총 fit 시킨 모델의 개수는 pC2개가 될 것이다

이것도 동일하게 나온 모든 모델들 중에서

이전과 동일한 기준으로 성능이 가장 좋은 모델을 뽑는다

 

이렇게 p개까지 반복을 하면 되고

k=p가 되면 모델은 1개가 나오게 된다

그게 Mp가 되는 것이다

 

그렇게해서 M0부터 Mp까지의 모델들이 각각 뽑혔으면

이제 이 중에서 한 개를 선택해야한다

그런데 그럼 M0부터 Mp까지 p개의 모델들 중에서

가장 성능이 좋은걸 뽑으려고 할 때

이 때도 무조건 RSS가 가장 낮거나 R제곱이 가장 높은 것을 뽑으면 될까?

 

사실 R제곱이 가장 높은 모델은 저기서는 무조건 Mp가 된다

왜냐면 M0부터 Mp의 모든 모델들은

동일한 training data에 대해서 training error를 기준으로 계산된 것이고

그렇다보면 당연히 모델 size가 가장 큰 Mp가 가장 좋은 결과를 받게 된다

내가 feature를 모델에 새로추가한다면 절대 R제곱은 감소하지 않는다

증가하거나 값이 동일해질수는 있어도 절대 감소하지는 않는다고 한다

 

그래서 이 M0부터 Mp까지의 모델들 중에서

가장 성능이 좋은 모델을 찾기 위해서는

model size를 보정해주는 AIC, BIC 등의 metric을 추가로 사용한다

이건 training data에서 계산되는 어떤 metric들로

나중에 뒷 내용에서 자세한 설명이 나온다

 

아무튼 여기서 중요한 포인트는 아무런 보정도 들어가지않은

plain R제곱을 가지고 모델을 선택하면

무조건 Mp가 가장 좋은 모델로 선정된다는 것이다

 

 

 

위 방법은 우선 Linear regression과 같은

parametric model에서 모두 쓸 수 있다

위는 각각의 model size에서 나온 RSS를 그래프로 그린 것이다

 

위를 보면 알겠지만 R제곱은 monotone하게 증가하는 함수로

non-decreasing 함수이다

마찬가지로 RSS는 non-increasing 함수이다

 

우선 여기서 계속 생각해야할 것은

이 모든건 training error로 계산된 것이라는 점이다

오늘 배우는 내용은 test data에 대해서도 할 수 있지만

일단 training data에 대해서만 한다고 가정해보자

 

앞에서도 말했지만 이렇게 M0부터 Mp까지 모델들을 뽑았을 때

Mp를 무조건 고르면 안된다는게 아니다

다만 RSS나 R제곱을 기준으로 삼으면

무조건 Mp가 뽑힐 수밖에 없다는 점이다

그래서 실제로 그 Mp를 test data로 가져가서 실험해보면

성능이 좋지 못할 가능성이 크다

overfitting의 전형적인 예시이다

 

 

 

또한 위 방법론은 regression에서만 사용될 수 있는것은 아니다

log likelihood와 같은 곳에서도 계산이 가능하고

그냥 우리의 subset별로 나눌 수만 있다면 모두 적용 가능하다

 

 

 

그런데 아까 위에서 best subset selection은

너무 무식한 방법이라서 쓰지말라고했다

그렇다면 이 best subset selection의 계산량이 얼마나 많은지 살펴보자

 

우리가 best subset selection으로 했을 때

model selection을 몇 번 하냐면

p가 10개만 되어도 2의 10제곱이라 1024번을 수행하게 된다

이건 너무 많은 연산량이다

 

그런데 뭐 연산량이 많기도 하지만

일단 어떻게든 2의 p제곱번 model selection을 수행해서

training error가 젤 낮은 모델을 찾았다고하자

사실 그런데 이건 training error가 젤 낮은 모델일뿐이다

첫 시간부터 계속 말했지만

결국 우리가 하고 싶은건 test error가 제일 낮은 모델을 찾는 것이다

 

그렇다면 이런 질문을 한 번 해보자

test data가 있고 2의 p제곱번 model selection을 다 수행했고

이를 test data 바탕으로 가장 fit한 model을 선택했다고 가정하자

그럼 이 모델들은 test data를 기준으로 가장 fit한 친구니까 괜찮은걸까?

한 번 생각해볼만한 질문이다

 

test dataset도 결국 데이터들을 sample해서 일부만 갖고 test를 한 것이다

그럼 만약 우리가 수행한 test dataset sample이 아닌

다르게 뽑은 test dataset sample로 수행해도

우리가 위에서 선정한 모델이 가장 잘 수행하는 모델이 될까?

 

보통 search space가 너무 큰 경우에

거기서 가장 성능이 좋은 모델을 택하다보면

결국 그 데이터셋만 잘되는 특화된 모델을 선택할 확률이 높아진다고 한다

 

아무튼 그래서 우리는 best subset selection이 아닌

stepwise 방식을 주로 사용한다고 한다

 

 

 

우선 forward stepwise selection부터 살펴보자

이건 Null model에서부터 시작해서 feature들을

하나 둘씩 add해 나가면서 size별로 모델을 fit 시킨다

전체 파라미터가 다 들어간 Mp가 나올 때까지 수행한 다음

그 중에서 어떤 모델이 가장 좋을지 마지막 한번을 선택한다

 

 

 

 

구체적으로 어떻게 수행하는지를 살펴보자

 

우선 null model에서부터 시작한다

null model에서 한 개씩 feature를 add하는 방식이다

 

intercept만 존재하는 null model에서

1개의 feature를 넣은 다음 모델을 fit한다

여기서 젤 좋은 모델을 M1이라고 한다

여기까지는 best subset과 유사하다

 

그런데 그 다음 step으로 가보자

두 번째 iteration으로 갔을 때 M1을 fit할 때 선택됐던 파라미터들은

무조건 M2에 들어갈수있도록 Keep 한 다음

전체 p개의 파라미터에서 선택된 feature는 제외한

총 p-1개의 feature들 가운데에서 한 개를 더 추가한다

그러면 2개의 feature가 존재하게 되는데

이 2개의 feature로 fit 시킨 모델을 M2라고 정의한다

여기서부터 best subset과 달라지는 것이다

 

그럼 3번째도 살펴보자

M2에서 사용된 2개의 feature들은 keep 해둔 다음

남은 p-2개의 파라미터들 중에서 1개를 추가로 골라서 fit해주면된다

 

이런 방식대로 M0부터 Mp까지 모델을 전부다 구해준다

이렇게해서 여기서 또 가장 좋은 모델을 구하기 위해서는

model size를 보정한 score를 사용해서 구해야한다

 

 

 

 

이러한 forward stepwise selection은

best subset에 비해서 계산량이 현저히 작다

 

best subset은 2의 p제곱번 model selection을 수행하는데

forward stepwise selection은

첫 번째는 p번, 두번째는 p-1번, 세번째는 p-2번... 이렇게 해서

1부터 p까지 더한거의 총 합 p(p+1)/2번을 수행하게 된다

 

하지만 세상의 모든것이 그렇듯이 공짜는 없는데

이러한 stepwise 방식으로 수행해서 최종 선출된 모델이

반드시 best selection이라는 보장이 없다고한다

 

진짜로 training data에서 error가 가장 작은 것을 찾고싶다면

best subset selection처럼 2의 p제곱번을 다 수행해야한다

 

 

 

그 예시를 한 번 살펴보자

 

왼쪽은 best subset의 결과이고 오른쪽은 forward stepwise의 결과이다

M1, M2, M3까지는 best subset이나 forward stepwise나

feature들이 모두 동일한 것을 확인할 수 있다 

그런데 Four에서 달라진 것을 확인할 수 있다

 

forward stepwise는 네번째에서도 

세번째에 포함됐던 파라미터들이 그대로 들어가야하기 때문에

이렇게 결과가 달라지는 것을 확인할 수 있다

forward stepwise는 저 모델이 가장 성능이 좋다는 것을 보장할 수는 없다

 

 

 

 

지금까지 우리가 본게 forward stepwise selection이었다고하면

backward stepwise selection도 있다

 

직관적으로 보면 쉽다

forward는 일명 아무것도 없는 깡통 모델에서 

하나 둘씩 feature들을 넣는 방식으로 시작한다면

backward는 전부 다 들어간 full model에서

하나 둘씩 제거하면서 수행하는 방식이다

 

backward는 한마디로 feature p개가 모두 다 들어가있는

Mp 모델에서 한개씩 한개씩 어떤 Feature들을 제거할지를

step by step으로 수행하는 것이다

 

 

 

Mp부터 시작해서 어떤 feature를 빼야

RSS가 가장 최소가 될지를 선정하는 것이다

 

그런데 위에서도 잠깐 언급했지만 full model에서

feature를 빼면 RSS는 무조건 증가하게 된다

아니 적어도 감소는 하지 않는다

이런걸 감안하고 수행하는 것이다

 

 

 

 

마찬가지로 backward stepwise selection도

best subset selection에 비해서 여전히 연산량이 작지만

이것도 나온 모델이 최고의 모델이라는 보장이 없다

backward와 forward stepwise selection은 greedy selection이기 때문이다

 

또 한 가지 중요한 점은

forward는 p가 n보다 커지면 invertible하니까 멈출 수가 있는데

backward는 처음부터 p개에서 시작하기 때문에

이게 n보다 큰지 작은지 알 수가 없다

따라서 backward는 p가 n보다 무조건 작을 때에만 사용한다

 

 

 

앞에서도 계속 얘기했지만

RSS가 가장 작던지 R제곱이 가장 높은걸 선택하는 것은

training error에서는 model size가 큰 애들이 무조건 그렇다

따라서 vanilla R제곱값을 이용하는 것은 무리가 있다

 

 

 

또한 늘 말하지만 우리의 궁극적인 목표는

test error에서의 최고 성능을 찾는 것이다

 

그래서 우리가 혹시 test data가 이미 있거나

validation data가 있다면

그냥 그 데이터에 바로 적용할 수 있다

 

 

 

또 아까 앞에서 계속해서 말했듯이

최종 모델을 선택할 때는

model size에 대해서 보정을 해주는 score가 필요하다

 

training error에서 model size가 크다면

그거에 대한 페널티를 주는 것이다

이런 metric들이 Cp, AIC, BIC, Adjusted R제곱 등이 있다

 

 

 

 

아까 봤던 데이터들을 기준으로

Cp, BIC, Adjusted R제곱을 적용했을 때

결과는 위와 같이 나온다

 

각 metric에 대한 자세한 설명은 뒤로하고 우선 결과부터 봐보자

Cp를 보면 확 감소하다가 뒤로 가면서 미세하게 증가한다

Cp score가 가장 낮은 feature가 6인 모델이 선택되었다

또한 BIC도 확 감소하다가 뒤로가면서 미세하게 증가한다

그래서 가장 작은 모델인 feature가 4개일 때가 선택된 것을 확인할 수 있다

Adjusted R제곱을 보면 확 증가하다가 미세하게 감소하는데

값이 가장 큰 feature가 7일 때의 모델이 선택된 것을 확인할 수 있다

 

따라서 이러한 score metric을 바탕으로

best subset selection 혹은 stepwise selection으로 선택한

M1부터 Mp까지 p개의 모델들 중에서

가장 성능이 좋다고 판단되는 최종 모델을 선택할 수 있다

 

 

 

자 그렇다면 각 metric에 대해서 좀 자세하게 살펴보자

 

위에서 Cp score의 식을 잘 살펴보자

RSS에다가 한개의 term을 더 추가했다

그럼 저 추가된 term이 뭐냐?

d는 이 모델에 들어가있는 파라미터의 개수이고

시그마는 모델의 variance를 뜻하는 값이었다

 

즉 training data가 얼마나 잘 fit 되었는지를 나타내는 RSS에

2 * d * 시그마제곱을 더했다는 소리는

모델의 파라미터가 많아지면 RSS는 낮아지겠지만

뒤의 term으로 값을 더 크게 해주어서 페널티를 주는 것이다

따라서 이런 방식으로 계산하면 무조건 size가 큰 모델이 아닌

적절한 사이즈의 모델일 때가 선택되게 된다

 

이거의 다른 버전이 AIC라고 하는데

AIC는 Log likelihood를 이용해서 계산한다고 한다

위 식에서 L은 likelihood이고 낮으면 낮을수록 좋은 것이다

 

사실 AIC나 Cp나 동치로 사용한다고 한다

 

 

 

 

그렇다면 BIC는?

 

앞에서 Cp와 AIC는 동치로 본다고 했는데

BIC는 비슷한듯 하면서 조금 다르다

Cp와 뒤에 추가되는 term이 약간 다르다

 

BIC뒤에는 log n이 달려있는데

자연 log이기 때문에 n이 3이상이면 이 값은 1보다 커진다

그러다가 n이 7이 넘어가면 Cp보다 모델 사이즈에 대한 페널티가 커지게 된다

따라서 BIC는 Cp에 비해 feature 수가 적은 모델을 선호하는 경향이 있다

 

 

 

그렇다면 adjusted R제곱을 살펴보자

 

plain R제곱은 1- (RSS/TSS)였는데

adjusted R제곱은 뒤에 ratio값을 곱해준다

 

d는 여전히 모델에 포함된 파라미터 수이고

모델에 들어간 파라미터 숫자가 많을수록

RSS에 나눠지는 값은 작아지고 분자의 값은 커진다

그런데 이걸 1에서 빼주니까 

한마디로 모델에 들어간 파라미터 숫자가 많을 수록 Adjusted R제곱은 작아지는 것이다

 

그런데 R제곱값은 커질수록 좋은것이라서

Adjusted R제곱을 maximize 시키는 것은 결국

RSS/(n-d-1)값을 minimize 시키는 것과 동일해진다

한마디로 plain R제곱에 비해 어쩔수없이

adjusted R제곱은 상대적으로 작아지게 된다

 

 

 

아무튼 앞에서 말했듯이

Cp, BIC, Adjusted R제곱과 같은

이런 점수들이 있다

 

그런데 Cp랑 BIC를 계산하라면 모델의 variance도

알아야한다는 점도 고려해야한다

하지만 adjusted R제곱은 이런건 필요없다

 

또한 지금까지 우리는 training error로만 계산한다고 가정했는데

사실 validation set이 있다면 그냥 거기다가 바로해도된다

 

그리고 여전히 training data 바탕으로 한다고 해도

결국 마지막 끝단에서 test data로 하면 되기 때문에  크게 문제없다

 

 

 

 

자 그럼 마지막으로 위 내용을 살펴보자

 

BIC score을 계산한게 가장 왼쪽이고

cross-validation으로 한게 오른쪽 그래프이다

 

여기서 BIC로 했을 때는 파라미터 4개짜리 모델이 가장 좋다고 나오고

cross validation으로 바로 했을때는 파라미처 6개짜리 모델이 좋다고 나온다

그럼 이 둘중에서 우린 어떤 모델을 선택해야할까?

 

 

 

 

예를 들어서 cross-validation을 수행한 feature가 6개인 모델이

feature가 4개인 모델에 비해서 0.0001% 성능이 더 좋았다고 하자

그럼 우리는 이 둘중에 뭘 선택해야할까?

 

성능 차이가 미세하게 날 때는

결국 복잡도가 더 낮은 것을 선택하기도 한다

결국 에러들도 random variable이기 때문에

데이터셋이 달라지면 더 달라질수도 있기 때문이다

 

따라서 비슷한 성능이라면 조금 더 복잡도가 낮은 모델을 선택한다는 것이

one-standard-error rule인 것이다