단계적 선택과 최량 부분집합 선택¶
회귀 문제에 후보 설명변수가 많으면 최종 모형에 어떤 부분집합을 넣을지 결정해야 한다. 가능한 모든 조합을 시도하는 것이 가장 철저하지만 설명변수가 늘어날수록 계산이 불가능해진다. 단계적 방법은 모형 공간의 관리 가능한 일부만 탐색하는 탐욕적 대안을 제공한다.
1. 최량 부분집합 선택¶
최량 부분집합 선택은 \(p\)개 후보 설명변수의 가능한 모든 부분집합을 평가하여 주어진 기준을 최적화하는 것을 고른다.
알고리즘¶
- 각 \(k = 0, 1, \ldots, p\)에 대해 정확히 \(k\)개의 설명변수를 담은 \(\binom{p}{k}\)개의 모형을 모두 적합한다.
- 크기가 \(k\)인 모형들 가운데 SSE가 가장 작은(동등하게 \(R^2\)가 가장 큰) 것을 찾아 \(\mathcal{M}_k\)라 한다.
- 복잡도에 벌점을 주는 기준(수정 \(R^2\), AIC, BIC, 교차검증 오차)으로 \(\mathcal{M}_0, \mathcal{M}_1, \ldots, \mathcal{M}_p\) 가운데 전체 최선 모형을 고른다.
계산 비용¶
적합해야 할 모형의 총 개수는
이는 지수적으로 늘어난다. \(p = 10\)이면 \(2^{10} = 1{,}024\)개로 감당할 만하다. \(p = 20\)이면 백만 개를 넘고, \(p = 40\)이면 1조 개를 넘어 전수 탐색이 비현실적이 된다.
\(p\)가 크면 최량 부분집합은 불가능하다
최량 부분집합 선택은 보통 \(p \leq 20\) 정도의 문제로 제한된다. 설명변수 집합이 더 크면 단계적 방법이나 정칙화 접근(릿지, 라쏘, 엘라스틱넷)이 필요하다.
2. 전진 단계적 선택¶
전진 단계적 선택은 절편만 있는 모형에서 시작하여 설명변수를 하나씩 더해 나간다.
알고리즘¶
- \(\mathcal{M}_0\)을 절편만 있는 모형(설명변수 없음)이라 한다.
- \(k = 0, 1, \ldots, p-1\)에 대해:
- 아직 모형에 없는 \(p - k\)개의 설명변수를 모두 고려한다.
- SSE를 가장 크게 줄이는(동등하게 부분 F 통계량이 가장 크거나 p값이 가장 작은) 설명변수를 넣는다.
- 그 결과 모형을 \(\mathcal{M}_{k+1}\)이라 한다.
- 수정 \(R^2\), AIC, BIC, 교차검증으로 \(\mathcal{M}_0, \mathcal{M}_1, \ldots, \mathcal{M}_p\) 가운데 최선 모형을 고른다.
계산 비용¶
단계 \(k\)에서 전진 선택은 \(p - k\)개의 모형을 적합한다. 총합은
\(O(p^2)\)이므로 최량 부분집합의 \(2^p\)보다 훨씬 작다. \(p = 20\)이면 전진 선택은 210개 모형만 적합하지만 최량 부분집합은 백만 개가 넘는다.
한계¶
전진 선택은 탐욕적 알고리즘이다. 한번 모형에 들어간 설명변수는 영원히 남는다. 곧 최선의 두 변수 모형에 포함된 변수 가운데 어느 것도 단독으로 최선이 아니라면 전진 선택은 그 모형을 찾아내지 못한다. 모형 공간 전체가 아니라 그 안의 한 경로만 탐색하기 때문이다.
왼쪽이 두 계산 비용을 겹쳐 놓은 것이다. 세로축이 로그 눈금인데도 붉은 \(2^p\)가 직선으로 치솟는다. \(p = 10\)에서는 \(1{,}024\)개 대 \(55\)개로 둘 다 감당할 만하지만, \(p = 20\)에서 \(1{,}048{,}576\)개 대 \(210\)개로 오천 배 차이가 나고, \(p = 40\)에서는 \(1\)조 개를 넘는 \(1{,}099{,}511{,}627{,}776\)개 대 \(820\)개가 된다. 초당 백만 개의 모형을 적합할 수 있다 해도 \(p = 40\)의 전수탐색에는 \(12\)일이 걸린다. \(p\)가 하나 늘 때마다 비용이 두 배가 된다는 사실이 이 곡선의 전부다.
오른쪽이 그 절약의 대가다. 설명변수 셋짜리 자료를 일부러 이렇게 만들었다. \(x_2\)와 \(x_3\)은 상관이 \(0.9\)로 거의 같은 변수인데 \(y\)는 그 둘의 차이로 만들어져 있다. 그래서 \(x_2\) 하나만으로는 \(R^2 = 0.021\), \(x_3\) 하나만으로는 \(0.077\)에 지나지 않지만, 둘을 함께 넣으면 \(R^2 = 0.958\)로 껑충 뛴다. 한편 \(x_1\)은 그 차이를 잡음과 섞어 만든 변수라 단독 \(R^2\)이 \(0.302\)로 셋 중 가장 크다.
전진선택은 1단계에서 반드시 \(x_1\)을 고른다. 셋 중 단독 설명력이 가장 크기 때문이다. 그러면 2단계에서 도달할 수 있는 최선은 \(\{x_1, x_3\}\)으로 \(R^2 = 0.342\)다. 최선의 두 변수 모형 \(\{x_2, x_3\}\)의 \(0.958\)과 견주면 거의 세 배 차이인데, 전진선택은 그 모형을 쳐다볼 기회조차 없다. \(x_2\)도 \(x_3\)도 1단계에서 뽑히지 못했기 때문이다. 이것이 통계학에서 억제 효과라 부르는 상황이며, 변수들이 서로 상관되어 있을 때 탐욕적 탐색이 실패하는 전형적인 방식이다. 절약이 늘 공짜는 아니다.
3. 후진 단계적 선택¶
후진 단계적 선택은 완전모형에서 시작하여 설명변수를 하나씩 뺀다.
알고리즘¶
- \(\mathcal{M}_p\)를 \(p\)개 설명변수를 모두 담은 완전모형이라 한다.
- \(k = p, p-1, \ldots, 1\)에 대해:
- 현재 모형에 있는 \(k\)개 설명변수를 각각 빼 보는 것을 고려한다.
- 뺐을 때 SSE 증가가 가장 작은(동등하게 부분 F 통계량이 가장 작거나 p값이 가장 큰) 설명변수를 뺀다.
- 그 결과 모형을 \(\mathcal{M}_{k-1}\)이라 한다.
- 복잡도에 벌점을 주는 기준으로 \(\mathcal{M}_0, \mathcal{M}_1, \ldots, \mathcal{M}_p\) 가운데 최선 모형을 고른다.
계산 비용¶
적합하는 모형의 총 개수는 전진 선택과 같은 \(p(p+1)/2\)이다.
한계¶
후진 선택은 \(n > p\)를 요구한다. 관측값보다 설명변수가 많으면 완전모형을 적합할 수 없기 때문이다. 전진 선택에는 이런 제약이 없어 고차원 상황(\(p > n\))에서도, 알고리즘이 설명변수 \(n\)개를 넘기 전에 멈추기만 하면 적용할 수 있다.
4. 혼합 접근¶
전진과 후진 단계를 결합하는 구현도 있다.
-
단계적 회귀(양방향): 각 단계에서 새 설명변수를 넣는 것과 기존 설명변수를 빼는 것을 모두 고려한다. 앞 단계에서 들어온 설명변수도 다른 변수들이 들어온 뒤 중복이 되면 나중에 빠질 수 있다. 순수한 전진이나 후진보다 유연성이 커진다.
-
순차 교체: 전진 선택을 마친 뒤, 포함된 설명변수 각각을 제외된 설명변수 각각과 바꿔 보고 기준이 좋아지는 교체를 채택한다.
5. 선택 기준¶
각 알고리즘의 3단계에서 어떤 기준을 쓰느냐가 결과에 큰 영향을 준다.
| 기준 | 공식 | 경향 |
|---|---|---|
| 수정 \(R^2\) | \(1 - \frac{\text{SSE}/(n-p-1)}{\text{SST}/(n-1)}\) | 중간 정도의 복잡도 |
| AIC | \(2k + n\ln(\text{SSE}/n)\) | 예측 지향 |
| BIC | \(k\ln n + n\ln(\text{SSE}/n)\) | 절약적 |
| 교차검증 오차 | \(\text{CV}_{(K)}\) | 예측오차의 직접 추정 |
복잡도 벌점 없이 SSE나 \(R^2\)만 쓰면 언제나 가장 큰 모형이 선택되어 변수선택의 목적이 무너진다.
6. 단계적 방법에 대한 비판¶
단계적 방법은 실무에서 여전히 널리 쓰이지만 잘 알려진 결함이 있다.
p값 부풀림: 설명변수를 순차적으로 여럿 검정하면 우연히 허위 설명변수가 포함될 가능성이 커진다. 최종 단계적 모형의 p값은 그 모형에 이르게 한 탐색 과정을 반영하지 않으므로 지나치게 낙관적이다.
불안정성: 자료가 조금만 달라져도 선택되는 모형이 크게 달라질 수 있다. 어떤 자료에서 아슬아슬하게 들어온 설명변수가 조금 흔들린 같은 자료에서는 제외될 수 있다.
편향된 계수: 선택된 모형의 계수는 0에서 멀어지는 쪽으로 편향된다. 선택 과정이 추정된 효과가 큰 설명변수를 우선적으로 남기는데, 그중 일부는 우연히 커진 것이기 때문이다.
다중공선성 무시: 단계적 방법은 상관된 설명변수를 명시적으로 다루지 않는다. 두 설명변수가 강하게 상관되어 있으면 둘이 비슷한 정보를 담고 있는데도 임의로 하나만 넣고 다른 하나를 뺄 수 있다.
현대적 대안
정칙화 방법(릿지, 라쏘, 엘라스틱넷)은 포함/배제라는 이분법적 결정 대신 계수를 0 쪽으로 축소하여 이 비판들 상당수에 대처한다. 특히 라쏘는 \(\ell_1\) 벌점의 부산물로 변수선택을 수행하여 단계적 방법의 원칙 있는 대안이 된다.
연습문제¶
연습문제 1. 전진 선택, 후진 소거, 최량 부분집합 선택의 차이를 기술하라. 계산 비용이 가장 큰 것은 무엇인가?
풀이
전진 선택은 설명변수 없이 시작하여 하나씩 더하며, 각 단계에서 모형을 가장 크게 개선하는(예: AIC를 가장 크게 낮추는) 설명변수를 고른다. 어떤 추가도 기준을 개선하지 못하면 멈춘다.
후진 소거는 모든 설명변수로 시작하여 하나씩 빼며, 뺐을 때 모형이 가장 덜 나빠지는 설명변수를 고른다. 남은 설명변수가 모두 유의하거나 기준에 기여할 때 멈춘다.
최량 부분집합 선택은 \(p\)개 설명변수의 가능한 \(2^p\)개 부분집합을 모두 평가하여 크기별 최선 모형을 찾고, 기준(AIC, BIC, 수정 \(R^2\))으로 크기들 사이에서 고른다.
최량 부분집합이 압도적으로 비싸다. \(2^p\)개의 모형을 적합해야 하며, \(p = 20\)이면 백만 개가 넘는다. 전진과 후진 선택은 최대 \(O(p^2)\)개의 모형만 적합하므로 더 큰 \(p\)에서도 실행 가능하다. 다만 단계적 방법은 탐욕적이므로 전역 최선 부분집합을 놓칠 수 있다.
연습문제 2. p값을 조정하지 않으면 단계적 선택이 왜 제1종 오류율을 부풀리고 과적합된 모형을 만들어 내는지 설명하라.
풀이
각 단계에서 단계적 선택은 여러 후보 설명변수를 검정하고 p값이 가장 작은(또는 개선이 가장 큰) 것을 고른다. 이는 다중검정의 한 형태이다. 모든 설명변수가 실제로는 반응변수와 무관하더라도 \(p\)개 후보 가운데 가장 좋은 것은 우연히 작은 p값을 가질 가능성이 높다.
그렇게 얻은 p값은 탐색 과정을 반영하지 않으므로 추론에 쓸 수 없다. \(p = 0.03\)으로 모형에 들어온 설명변수가 후보 20개 가운데 선택된 것이라면 실제 유의수준은 훨씬 높다. 게다가 단계적 방법이 고른 모형은 그 특정 자료에 최적화되었으므로 훈련자료를 과적합하는 경향이 있다.
대책으로는 p값 대신 정보기준(AIC, BIC) 사용, 최종 모형 평가를 위한 교차검증, 변수선택과 계수 축소를 동시에 수행하는 정칙화 방법(LASSO)이 있다.
연습문제 3. 설명변수가 \(p = 5\)개일 때 최량 부분집합 선택은 몇 개의 모형을 평가해야 하는가? 가능한 모형 크기를 모두 나열하라.
풀이
설명변수가 \(p = 5\)개면 부분집합의 총 개수는 \(2^5 = 32\)개이다(설명변수가 없는 영모형 포함).
크기별 모형 수:
- 크기 0(절편만): \(\binom{5}{0} = 1\)개
- 크기 1: \(\binom{5}{1} = 5\)개
- 크기 2: \(\binom{5}{2} = 10\)개
- 크기 3: \(\binom{5}{3} = 10\)개
- 크기 4: \(\binom{5}{4} = 5\)개
- 크기 5(완전모형): \(\binom{5}{5} = 1\)개
합계: \(1 + 5 + 10 + 10 + 5 + 1 = 32\)개. 최량 부분집합 선택은 각 크기의 최선 모형(후보 6개)을 찾은 뒤 AIC/BIC/교차검증으로 그 6개 가운데 고른다.
연습문제 4. LASSO의 변수선택과 단계적 선택을 비교하라. 현대 실무에서 LASSO가 일반적으로 선호되는 이유는 무엇인가?
풀이
LASSO는 회귀 목적함수에 \(L_1\) 벌점을 더해 일부 계수를 정확히 0으로 축소함으로써 변수선택과 추정을 동시에 수행한다. 정칙화 모수 \(\lambda\)가 적합과 희소성 사이의 절충을 조절한다.
단계적 방법에 대한 LASSO의 장점:
- 연속적인 경로: \(\lambda\)가 변함에 따라 LASSO는 모형들의 연속적인 경로를 만들어, 단계적 방법의 이산적이고 탐욕적인 결정을 피한다.
- 축소: 선택된 설명변수의 계수도 0 쪽으로 축소되어 과적합이 줄어든다.
- 타당한 추론: LASSO에 대해서는 선택 후 추론 방법(예: 선택적 추론)이 존재한다. 단계적 p값은 보정 없이는 타당하지 않다.
- 확장성: LASSO는 \(p > n\)(관측값보다 설명변수가 많은 경우)을 다룰 수 있다. 이 상황에서 후진 소거는 완전모형을 적합할 수 없어 아예 쓸 수 없다.
- 교차검증과의 통합: \(\lambda\)를 교차검증으로 고르므로 검정오차의 정직한 추정값을 함께 얻는다.
단계적 방법은 각 선택 단계의 해석 가능성이 중요하거나 정칙화 경로를 계산할 자원이 제한적일 때 여전히 쓸모가 있다.
정리하며¶
설명변수가 많으면 어떤 부분집합을 쓸지 정해야 한다.
- 최량 부분집합은 \(2^p\) 개를 모두 본다. 철저하지만 \(p=20\) 이면 백만 개가 넘어 현실적이지 않다.
- 단계적 방법은 탐욕적이다. 전진은 빈 모형에서 하나씩 더하고, 후진은 가득 찬 모형에서 하나씩 뺀다. \(O(p^2)\) 으로 줄지만 최적을 보장하지 않는다.
- \(p>n\) 이면 후진을 쓸 수 없다. 가득 찬 모형을 적합할 수 없기 때문이며, 그때는 전진이나 정칙화로 간다.
- 선택 후 추론은 타당하지 않다. 같은 자료로 변수를 고르고 그 계수를 검정하면 \(p\) 값이 낙관적으로 편향된다. \(R^2\) 도 부풀고 신뢰구간도 좁아진다 — 9장의 \(p\)-해킹과 같은 구조다.
- 현대적 대안은 정칙화다. 라쏘가 선택과 추정을 한 번에 하며 안정적이다(18장).
다음 절 모형선택 실습으로 넘어간다.