[STAT] Leave-One-Out Formula for Linear Smoothers

Introduction

Leave One Out Cross Validation이란, 각 하나의 Sample만 제외하면서 그 제외한 Sample로 Validation Score를 계산하는 방법이다.

(\hat{\mu}(\cdot)) : 전체 Sample로 훈련된 Regression Model
(\hat{\mu}_{-i}(\cdot)) : i-th Sample을 제외하여 훈련한 Regression Model

[ R_i^{\text{LOO}} = y_i - \hat{\mu}_{-i}(x_i) \tag{1} ]

[ \textrm{CV}{n} = \frac{1}{n}\sum{i=1}^n \left[y_i - \hat{\mu}_{-i}(x_i)\right]^2 \tag{2} ]

위의 공식을 이용하여 Cross-Validation을 진행하는 것은 굉장히 Computing Cost가 크다. 그래서 이 방법은 Sample이 작은 경우에, 데이터를 하나라도 버리기 아까울 때와 같이 제한된 상황에서 사용된다.

한편, 선형 모형의 경우에는 ((1))의 수식이 closed-form으로 주어진다는 이점이 있다. 본문에서는 ((1))의 수식이 어떻게 주어지고, 직관적으로는 어떤 의미를 가지며, 증명하는 방법에 대해서 다룰 것이다.

Formula for Linear Smoothers

((1))의 증명에 대해서 한국어로 된 글이 없어서 찾느라 꽤 고생을 했으나, Everybody’s Favorite Data Blog에 잘 정리된 글이 있어서 참조하였다. 첨부된 글과는 달리, 필자가 이해하기 쉬운 Notation으로 수정하여 서술하겠다.

1. What are Linear Smoothers?

우선, Linear Smoother에 대해서 알아보자. (\hat{y} = Sy) 와 같은 식을 가지는 모형을 Linear Smoother라고 지칭한다. 대표적으로 Linear Smoother에는 Least Sqaures를 사용하는 Linear Regression, Kernel Ridge Regression 등이 있다.

[ \hat{y} = X(X^{\top}X)^{-1}X^{\top}y = Hy ]

[ \hat{y} = K(K + \lambda I)^{-1}y = Sy ]

Linear Smoother 자체에 관심이 있는 것은 아니므로 자세한 설명은 생략한다. 추후 관련된 글을 작성해서 포스트 하겠다.

2. Formula for (R_i^{LOO})

그래서 앞서 설명했던 것과 같이, Linear Smoother에서는 다음과 같은 특별한 식이 성립한다.

[ R_i^{LOO} = \frac{y_i - \hat{\mu}{-i}(x_i)}{1 - S{ii}} \quad \text{where} \; S \; \text{is a Smoother Matrix} ]

위 식을 좀 꼼지락 꼼지락 변형하면 아래와 같이 나타낼 수 있다.

[ \hat{\mu}{-i}(x_i) = \frac{\hat{\mu}(x_i)-S{ii}y_i}{1 - S_{ii}} = \sum_{j \neq i} \frac{S_{ij}}{1 - S_{ii}}y_i ]

두 번째 등식에 좀 주목을 해주면, 우리의 관심의 대상인 (\hat{\mu}_{-i}(x_i))의 값이 i번째 관측치의 영향력을 제거하고 가중치의 합이 1이 되도록 다시 계산한 것과 같음을 알 수 있다. i번째 관측치를 제거를 하고 학습을 한 모형에 대한 예측값이, i번째 관측치의 영향력을 제거하여 Reweighting한 것과 동일한 것은 굉장히 상식적인 결과이다. 근데, 이게 그래서 왜 성립하는 것일까? 이제부터 증명을 한번 해보자.

3. Proof

증명에 앞서서 몇가지 Notation과 증명에 유용한 사실들을 짚고 넘어가자.

• Notations
  • Full Design Matrix: (X \in \mathbb{R}^{n \times p})
    • (X_{-k} \in \mathbb{R}^{(n-1) \times p}) : design matrix with the $k$-th row removed
    • (y_{-k} \in \mathbb{R}^{n-1}) : response vector with the $k$-th element removed
• Some Useful Facts
  • (X^\top X = \sum_{i = 1}^n x_i x_i^\top)
  • (X_{-k}^\top X_{-k} = X^\top X - x_k x_k^\top)

본 증명에서는 일반적인 Linear Smoother에서가 아닌, Linear Regression의 경우에 대해서만 증명을 하겠다. Linear Smoother의 경우도 아래의 과정과 유사하게 진행하면 된다.

Regression 문제의 Loss Fuction $\mathcal{L}_k$를 정의하자.

[ \mathcal{L}k = \sum{i \ne k} (\hat{y}i - y_i)^2 = \sum{i \ne k} (x_i^\top \beta - y_i)^2, \quad \hat{\beta}^{(-k)} = \arg\min_{\beta} \mathcal{L}_k ]

그러면 다음이 성립하는 것은 자명하다.

[ \left. \frac{\partial \mathcal{L}k}{\partial \beta} \right|{\beta = \hat{\beta}^{(-k)}} = 0 \quad \Rightarrow \quad \sum_{i \ne k} x_i (x_i^\top \hat{\beta}^{(-k)} - y_i) = 0 ]

[ \begin{aligned} &\text{Since } \left( \sum_i x_i x_i^\top \right) \hat{\beta} = \sum_i y_i x_i, \quad \text{then } \left( \sum_i x_i x_i^\top - x_k x_k^\top \right) \hat{\beta}^{(-k)} = \sum_i y_i x_i - x_k y_k
&\Rightarrow \quad (X^\top X - x_k x_k^\top) \hat{\beta}^{(-k)} = X^\top X \hat{\beta} - x_k y_k
&\Rightarrow \quad (X^\top X)(\hat{\beta} - \hat{\beta}^{(-k)}) = x_k (y_k - x_k^\top \hat{\beta}^{(-k)})
&\Rightarrow \quad x_k^\top (\hat{\beta} - \hat{\beta}^{(-k)}) = x_k^\top (X^\top X)^{-1} x_k (y_k - \hat{y}k^{(-k)})
&\Rightarrow \quad \hat{y}_k - \hat{y}_k^{(-k)} = H{kk} (y_k - \hat{y}k^{(-k)})
&\Rightarrow \quad \hat{y}_k - y_k + (y_k - \hat{y}_k^{(-k)}) = H{kk} (y_k - \hat{y}k^{(-k)})
&\Rightarrow \quad \mathcal{R}_i^{\text{LOO}} = \frac{\mathcal{R}_i}{1 - H{ii}} \quad \quad \square \end{aligned} ]