실습 · 연습문제 2개

회귀 트리의 최적 분할 찾기 `best-split`

회귀 트리는 각 단계에서 특징 하나와 문턱 $s$ 를 골라 데이터를 $\{x \le s\}$ 와 $\{x > s\}$ 로 나누고, 두 쪽의 제곱오차 합

\mathrm{SSE}(s) = \sum_{i:\, x_i \le s} (y_i - \bar y_L)^2 + \sum_{i:\, x_i > s} (y_i - \bar y_R)^2

이 가장 작은 $s$ 를 고른다. $\bar y_L, \bar y_R$ 은 두 쪽의 평균이다.

함수 best_split(x, y)를 완성해 특징 하나에 대한 최적 분할 (threshold, sse)를 반환한다.

후보 문턱은 정렬한 서로 다른 값들의 이웃한 쌍의 중점이다. 예를 들어 값이 [1, 2, 2, 5]이면 후보는 1.5와 3.5다. 같은 값을 가진 샘플은 항상 같은 쪽으로 간다.
sse는 그 문턱에서의 $\mathrm{SSE}$ 다.
SSE가 같은 후보가 여럿이면 가장 작은 문턱을 반환한다.
x에 서로 다른 값이 두 개 이상 있다고 가정한다.

테스트는 손으로 계산한 예, 무작위 데이터에서의 전수 탐색과의 일치, 그리고 특징에 단조 증가 변환(로그 등)을 해도 같은 샘플 분할이 나오는지 확인한다. 마지막 성질 때문에 트리는 특징의 표준화가 필요 없다.

힌트: 정렬한 뒤 누적합으로 왼쪽·오른쪽의 합과 제곱합을 구하면 $\mathrm{SSE} = \sum y^2 - (\sum y)^2 / n$ 을 모든 후보에 대해 한 번에 계산할 수 있다. 반복문으로 후보마다 직접 계산해도 된다.

permutation importance는 학습이 끝난 모델을 고정하고, 평가 데이터에서 한 특징의 값만 무작위로 섞었을 때 오차가 얼마나 커지는지로 그 특징의 중요도를 잰다.

함수 permutation_importance(predict, X, y, n_repeats=5, seed=0)를 완성해 shape (p,)의 배열을 반환한다. predict는 (N, p) 배열을 받아 (N,) 예측을 내는 함수다.

기준 오차 $E_0 = \mathrm{MSE}(y, \texttt{predict}(X))$ 를 계산한다.
특징 $j = 0, \dots, p-1$ 마다 n_repeats번 반복한다. X의 복사본을 만들고 $j$ 번째 열을 rng.permutation으로 섞은 뒤 MSE $E_{j,r}$ 를 잰다.
중요도는 $\frac{1}{R}\sum_r (E_{j,r} - E_0)$ , 즉 섞었을 때 평균적으로 늘어난 MSE다.

난수는 rng = np.random.default_rng(seed) 하나로 만든다. 입력 X를 직접 바꾸면 안 된다.

테스트는 다음을 확인한다.

모델이 쓰지 않는 특징의 중요도는 정확히 0이다.
$\hat y = 2x_0$ 인 모델에서 $x_0$ 의 중요도는 약 $8\operatorname{Var}(x_0)$ 이다. 섞인 $x_0'$ 이 원래 $x_0$ 와 독립이면 $\mathbb{E}[(2x_0' - 2x_0)^2] = 4 \cdot 2\operatorname{Var}(x_0)$ 이기 때문이다.
X가 바뀌지 않고, 같은 seed면 같은 결과가 나온다.
출력과 상관된 특징이라도 모델이 쓰지 않으면 중요도가 0이다. permutation importance는 세계가 아니라 모델에 대한 설명이다.