Predictive inference with the jackknife+

Rina Foygel Barber; Emmanuel J. Candes; Aaditya Ramdas; Ryan J. Tibshirani

Source-linked AI summary

Predictive inference with the jackknife+

Rina Foygel Barber, Emmanuel J. Candes, Aaditya Ramdas, Ryan J. Tibshirani

arXiv:1905.02928v32019년 5월 8일stat.ME

TL;DR

예측 구간은 제한적 가정 없이 신뢰할 수 있는 coverage가 필요하지만, 기존 jackknife는 회귀가 불안정할 때 실패할 수 있다. 이 논문은 exchangeability하에서 leave-one-out test-point prediction을 사용하고 최악의 경우 1−2α coverage를 보장하는 jackknife+를 제안하며, 일반적으로 jackknife와 비슷한 성능을 보인다.

문제
기존 jackknife는 보편적인 예측 coverage 보장이 없으며, 적합된 회귀 알고리즘이 불안정하면 coverage가 부족할 수 있다.
방법
jackknife+는 exchangeability하에서 적합 함수의 변동성을 반영하기 위해 leave-one-out residual에 test point에서의 leave-one-out prediction을 추가한다.
결과
jackknife+는 최악의 경우 최소 1−2α coverage를 보장하며, 실험적으로는 jackknife와 비슷한 폭의 구간으로 약 1−α coverage를 달성한다.
시사점 및 한계
jackknife+는 stability 가정 없이 coverage 보장을 제공하면서도 목표 coverage에 가까운 실증 성능을 유지하므로 실용적인 대안으로 권장된다.
시사점 및 한계
기존 jackknife는 불안정한 회귀 알고리즘에서 예측 coverage를 잃을 수 있으며, 여기에는 표본 크기가 차원에 가까운 경우의 least squares도 포함된다.

Abstract

from arXiv · show

This paper introduces the jackknife+, which is a novel method for constructing predictive confidence intervals. Whereas the jackknife outputs an interval centered at the predicted response of a test point, with the width of the interval determined by the quantiles of leave-one-out residuals, the jackknife+ also uses the leave-one-out predictions at the test point to account for the variability in the fitted regression function. Assuming exchangeable training samples, we prove that this crucial modification permits rigorous coverage guarantees regardless of the distribution of the data points, for any algorithm that treats the training points symmetrically. Such guarantees are not possible for the original jackknife and we demonstrate examples where the coverage rate may actually vanish. Our theoretical and empirical analysis reveals that the jackknife and the jackknife+ intervals achieve nearly exact coverage and have similar lengths whenever the fitting algorithm obeys some form of stability. Further, we extend the jackknife+ to K-fold cross validation and similarly establish rigorous coverage properties. Our methods are related to cross-conformal prediction proposed by Vovk [2015] and we discuss connections.

1 서론

이 논문은 exchangeability하에서 nonasymptotic coverage guarantee를 제공하는 prediction interval 방법인 jackknife+를 소개하며, original jackknife의 보편적 보장 부재를 해결한다. 최악의 경우 jackknife+는 최소 1−2α의 coverage를 보장하며, 경험적으로 두 방법은 coverage가 1−α에 가까운 거의 동일한 interval을 산출하는 경우가 많다.

문제: Prediction interval은 training data와 test point 양쪽의 randomness를 반영하면서 새로운 response를 포함할 확률 1−α를 목표로 한다.이 interval은 새로운 feature vector에 대한 fitted prediction을 중심으로 구성된다.
동기: Training residual에 기반한 naive interval은 overfitting 때문에 일반적으로 undercoverage를 보인다. 해당 residual이 관측되지 않은 test point의 error보다 작아지기 때문이다.이는 leave-one-out residual을 사용하게 하는 동기가 되며, leave-one-out residual은 거의 전체 sample에 fitting한 뒤의 prediction을 더 잘 반영한다.
Original jackknife: Original jackknife는 overfitting을 피하기 위해 leave-one-out fit과 residual quantile을 사용하지만, 보편적인 이론적 보장이 없고 unstable algorithm에서는 coverage를 잃을 수 있다.논문은 simulation에서 least-squares regression의 coverage가 극도로 낮게 나타날 수 있음을 지적한다.
기여: Jackknife+는 exchangeability만 가정해도 nonasymptotic coverage guarantee를 제공하며, 최악의 coverage는 1−2α이다. 반면 original jackknife의 coverage는 0이 될 수도 있다.이 guarantee는 training data와 test data의 exchangeability 외에 어떠한 가정도 없이 적용된다.
Jackknife+: Jackknife+는 test point에서의 leave-one-out prediction을 사용해 fitted regression function의 variability를 반영하도록 jackknife를 확장한다.이 방법은 Vovk [2015]가 제안한 cross-conformal prediction과 밀접한 관련이 있는 것으로 제시된다.

2 잭나이프+

잭나이프+는 leave-one-out test-point prediction을 중심으로 구간을 설정하도록 잭나이프를 수정해, exchangeability하에서 가정 없이 1−2α의 predictive coverage를 달성한다. 실제로는 잭나이프와 유사한 결과를 보이는 경우가 많지만, 불안정성으로 original jackknife가 실패할 때도 coverage를 유지하며, jackknife-minmax는 보수적으로 1−α coverage를 회복한다.

2 잭나이프+: Jackknife+는 fitted function의 변동성을 반영하기 위해 full-data prediction 대신 test point에서의 leave-one-out prediction을 사용한다.두 방법 모두 leave-one-out residual을 사용하지만, jackknife+는 bµ−i(Xn+1)를 사용해 구간 설정의 중심을 정한다.
2 잭나이프+: 실제로 jackknife와 jackknife+는 1−α에 가까운 coverage를 달성하고 성능도 거의 동일한 경우가 많지만, 불안정성으로 jackknife는 coverage를 잃는 반면 jackknife+는 목표 coverage에 도달할 수 있다.leave-one-out fit이 full-data fit과 유사하면 두 구간도 비슷할 것으로 예상되지만, 한 점을 제거했을 때 prediction이 달라지면 큰 차이가 날 수 있다.
2 잭나이프+: Jackknife+는 exchangeable data와 order-invariant method하에서 데이터 분포나 regression algorithm에 대한 가정 없이 최소 1−2α의 predictive coverage를 보장한다.이 정리는 exchangeability의 특수한 경우인 i.i.d. data에 대해 n ≥ 2 및 고정된 α를 가정해 제시된다.
2 잭나이프+: 병리적 예시는 1−2α 보장을 일반적으로 개선할 수 없음을 보이며, 추가 가정 없이는 original jackknife에 대해 어떠한 coverage 보장도 가능하지 않다.논문은 jackknife+의 coverage가 소멸하고 naive method의 coverage가 0이 되는 예시도 구성한다.
2 잭나이프+: Jackknife-minmax는 factor of 2를 제거하고 가정 없이 항상 목표 coverage를 달성하지만, 실제로는 대체로 지나치게 보수적이다.모든 data set에 대해 jackknife+보다 엄밀하게 더 보수적이다.

3 K-fold cross-validation을 위한 CV+

CV+는 jackknife+를 K-fold cross-validation으로 확장해 계산량을 줄이면서 jackknife+에 가까운 최악의 경우 coverage guarantee를 유지한다. 또한 이 절에서는 coverage, variance, interval 구조, 계산 비용 측면에서 CV+를 split conformal, cross-conformal, full conformal prediction과 비교한다.

3 K-fold cross-validation을 위한 CV+: K-fold CV+는 n개 대신 K개의 fitted model을 필요로 하지만, 더 작은 training fold 때문에 jackknife+보다 interval이 약간 더 넓어질 수 있다.jackknife+는 K = n인 특수한 경우다. CV+ model은 n(1 − 1/K)개의 training observation을 사용한다.
3 K-fold cross-validation을 위한 CV+: split conformal의 assumption-free 1 − α coverage와 비교하면, CV+는 모든 K개 split을 평균내 variance를 줄이지만 이론적 guarantee는 더 약하다.split conformal은 하나의 held-out subset을 사용하므로 단일 split에서 더 큰 variance가 발생한다.
3 K-fold cross-validation을 위한 CV+: CV+와 symmetric cross-conformal은 때때로 일치할 수 있지만, cross-conformal은 서로 겹치지 않는 interval들의 union을 반환할 수 있는 반면 CV+는 항상 하나의 interval을 반환한다.증명은 모든 K에 대해 K-fold cross-conformal의 coverage가 1 − 2α − 2/n임을 보이며, K = n일 때 coverage는 적어도 1 − 2α다.
3 K-fold cross-validation을 위한 CV+: CV+는 K의 모든 선택에 대해 coverage가 적어도 1 − 2α − 2/n이 되도록 하며, 큰 K에도 의미 있는 guarantee를 확장한다.이 결과는 본질적으로 1 − 2α인 small-K bound와 K = n을 포함하는 새로운 large-K guarantee를 결합한다.
3 K-fold cross-validation을 위한 CV+: Full conformal prediction은 exchangeability에 의해 target-level coverage를 달성하지만, 모든 test feature vector와 candidate response에 대해 재학습하므로 일반적으로 prohibitively expensive하다.linear regression, ridge regression, Lasso를 포함한 일부 model에는 특수한 computational shortcut이 존재한다.

4 Coverage 보장과 계산 비용 요약

jackknife+는 jackknife의 경험적 성능에 가까우면서도 엄밀한 ≥1 −2α coverage 보장을 결합하므로 권장된다. 주요 계산 비용은 n회의 model fitting이지만, K-fold와 split 방법을 사용하면 training 비용을 줄일 수 있다.

실용적 권고: 저자들은 jackknife+를 권장한다. jackknife의 보장 부재를 피하면서도 그 구간이 jackknife 구간만큼 거의 넓고 정확하기 때문이다.이러한 경험적 동등성은 병리적 예시를 피한다는 가정에 기반하며, 두 방법 모두 목표 1 −α coverage 수준에 가까운 성능을 보인다.
계산 비용: Jackknife+는 n회의 model-training runs가 필요하다. 반면 naive 및 split conformal은 1회, K-fold 방법은 K회, full conformal은 ntest · ngrid회가 필요하다.Training 비용은 최대 n개 크기의 데이터셋에서 regression algorithm A를 실행하는 횟수로 계산한다.
계산 비용: ntest개의 test point에 대해 jackknife+의 model-evaluation 비용은 ntest · n이다. 반면 naive와 jackknife-minmax는 n + ntest, K-fold CV+는 n + ntest · K이다.표에서는 상수항을 무시한 계산 비용을 보고한다.
구현 시 고려사항: Training residual을 reweighting하거나 random forest의 구조를 활용하면, 때로는 n회의 refitting 없이 leave-one-out residual을 계산할 수 있다.예로는 ordinary least squares, kernel ridge regression, kernel smoothing, thin plate splines, smoothing splines, random forests가 있다.

5 안정성 가정하의 보장

안정성 가정은 coverage 보장을 정교화한다. Out-of-sample stability는 inflation을 적용한 jackknife interval이 목표 coverage에 근접하도록 하며, in-sample stability와 out-of-sample stability를 함께 고려하면 naive interval도 검증된다. 이 구분이 중요한 이유는 in-sample stability가 평가 대상 training point의 제거를 통제하는 반면, out-of-sample stability는 독립적인 test point를 다루기 때문이다.

In-sample stability: In-sample stability는 out-of-sample stability와 근본적으로 다르다. 전자는 평가 대상 point를 삭제하는 상황을 통제하는 반면, 후자는 독립적인 test point를 예측할 때 training point를 삭제하는 상황을 통제한다.In-sample stability하에서는 overfitting을 보정하기에 ε inflation이면 충분하다고 사실상 가정하므로, out-of-sample stability도 성립할 때 naive interval의 coverage 결과를 얻을 수 있다.
Coverage 보장: In-sample stability와 out-of-sample stability가 모두 성립하면 naive interval, jackknife, jackknife+, jackknife-minmax는 약 1 − α coverage를 달성하며, jackknife+와 jackknife-minmax는 stability 없이도 보장을 유지한다.요약 표는 stability가 없을 때 jackknife+ coverage가 1 − 2α이고, 어느 한 안정성 조건하에서는 약 1 − α임을 보고한다. jackknife-minmax는 모든 경우에 1 − α를 보고한다.
Out-of-sample stability: Out-of-sample stability만으로도 ε-inflated jackknife와 2ε-inflated jackknife+ interval이 목표 coverage 보장을 달성하기에 충분하다.서로 다른 inflation 양은 특정 stability 정의에서 생기는 인공적 차이일 뿐, 두 방법 사이의 의미 있는 차이가 아니다.
Out-of-sample stability: Y|X가 bounded conditional density를 가지면, inflated interval 결과로부터 inflation을 적용하지 않은 jackknife와 jackknife+ interval의 coverage가 목표값에 근접함을 얻는다.Bounded density는 interval inflation으로 추가되는 probability mass를 제한한다.
예시: K-nearest neighbors: K-nearest neighbors에서는 ε = 0 and ν = K/n으로 out-of-sample stability가 성립하므로, data distribution이나 prediction accuracy에 대한 가정 없이 jackknife+ coverage lower bound를 얻는다.이 논증은 exchangeability를 사용한다. 각 training point가 자기 자신의 nearest neighbor이므로, 유사한 in-sample stability는 일반적으로 성립하지 않는다.

6 정리 1의 증명

증명에서는 쌍별 residual 비교를 통해 “strange” point를 식별하여 jackknife+의 실패 확률을 bound한다. 결정론적 tournament bound, exchangeability, noncoverage와 strangeness의 연결을 이용해 coverage guarantee를 얻는다.

증명 설정: comparison matrix는 point i의 leave-two-out residual이 point j보다 클 때를 표시하며, strange point는 비교의 최소 (1−α) 비율에서 승리한다.이 구성은 leave-one-out conformal method의 실패를 분석한 Vovk [2015, Appendix A]에서도 검토된다.
Step 1: strange point 수의 bound: Step 1에서는 tournament 방식의 counting argument를 사용해 strange point의 수가 2α(n+1)보다 작음을 결정론적으로 증명한다.각 strange point는 다른 strange point 중 많아야 α(n+1)−1개에 패할 수 있다. 따라서 losing pair를 세면 bound를 얻으며, 이는 tournament에 대한 Landau’s theorem 을 따른다.
Step 2: data point의 exchangeability: Step 2에서는 fitting algorithm의 exchangeability와 order-invariance를 사용해 test point가 strange일 확률이 2α 이하임을 보인다.모든 index가 strange일 가능성은 동일하므로 test point의 확률은 strange point 비율로 bound된다. 이는 conformal prediction 과 동일한 exchangeability reasoning을 사용한다.
Step 3: jackknife+와의 연결: Step 3에서는 jackknife+ noncoverage가 test point가 strange임을 함의함을 보여 noncoverage probability가 2α 이하임을 얻는다.Yn+1이 충분히 많은 index에 대해 jackknife+ interval 바깥에 놓이면, defining residual comparison에 따라 n+1이 S(A)에 포함된다.

7 실증 결과

모의 데이터와 실제 데이터 모두에서 jackknife+는 불안정한 회귀 설정에서도 목표 coverage를 유지하는 반면, jackknife는 coverage가 크게 낮아질 수 있다. 안정성이 높아지면 두 방법의 coverage와 구간 폭은 유사해진다. Naive interval은 coverage가 낮고, jackknife-minmax는 보수적이며, split conformal도 모의실험에서 coverage를 유지한다.

실험 설정: 이 연구는 least squares, ridge regression, random forests, neural networks를 사용해 모의 데이터와 실제 데이터에서 일곱 가지 prediction-interval 방법을 비교한다.실제 데이터 실험에서는 n = 200개의 training point를 무작위로 표본 추출하고, 나머지 관측값을 test set으로 구성한다.
모의실험: d ≈ n일 때 jackknife의 coverage는 약 0.5까지 하락하지만, jackknife+는 더 넓은 구간을 대가로 목표 수준에 계속 도달한다.d < n에서는 jackknife와 jackknife+의 coverage와 구간 폭이 거의 동일하며, least squares의 불안정성이 d = n 부근에서 두 방법의 차이를 유발한다.
모의실험: d가 증가할수록 Naive interval의 coverage는 점점 낮아지고, jackknife-minmax는 과도하게 보수적이며, d > n에서는 full conformal의 구간이 무한대가 된다.d ≥ n에서는 Naive interval의 구간 폭과 coverage가 모두 0이며, 실제적인 truncation 이전에는 full conformal의 coverage가 결정론적으로 1이다.
모의실험: 모의실험에서 jackknife+와 split conformal만이 체계적인 under-coverage나 over-coverage 없이 전체 구간에서 0.9 목표 coverage를 유지한다.Figure 2는 50회의 독립 trial에서 모든 방법의 coverage와 구간 폭을 비교한다.
실제 데이터 실험: 세 가지 실제 데이터셋에서 jackknife와 jackknife+는 매우 유사한 구간 폭으로 90%에 극히 가까운 empirical coverage를 달성한다.회귀 방법이 더 불안정한 설정에서는 Jackknife+의 coverage가 약간 더 높고 구간도 더 넓다.

8 요약

jackknife+는 가능한 알고리즘 불안정성을 반영하기 위해 leave-one-out prediction에 기반한 shift를 사용한다는 점에서 jackknife와 다르다. Exchangeable sample에서는 이를 통해 엄밀한 coverage guarantee를 제공하며, 계산 부담이 큰 경우에는 K-fold CV+를 대안으로 활용할 수 있어 jackknife+를 실용적인 선택지로 뒷받침한다.

jackknife+는 가능한 알고리즘 불안정성을 반영하기 위해 prediction shift를 적용한다.
Exchangeable sample에서 jackknife+는 추가 가정 없이 엄밀한 coverage guarantee를 제공한다.
실제 데이터에서의 경험적 성능은 jackknife+를 jackknife보다 더 나은 실용적 선택지로 만든다.
jackknife+의 계산 비용이 감당하기 어려운 경우 K-fold CV+는 매력적인 대안을 제공한다.

A 비대칭 jackknife+ 및 CV+ … B.2 CV+ 방법의 증명

이 논문은 coverage guarantee를 유지하면서 jackknife+, jackknife-minmax, CV+를 비대칭 residual 구성으로 확장하고, 수정된 comparison-matrix 논증을 통해 jackknife-minmax의 coverage를 증명한다. 또한 CV+와 cross-conformal prediction을 연결하는 증명 framework를 도입한다.

A 비대칭 jackknife+ 및 CV+: 비대칭 jackknife+는 잠재적으로 비대칭적인 noise에 대응하기 위해 별도의 signed-residual 구성을 사용하여 전체 miscoverage α를 오른쪽 꼬리와 왼쪽 꼬리에 배분한다.매개변수는 α+ + α− = α를 만족하며, α+와 α−가 각각 해당 꼬리를 조절한다.
A 비대칭 jackknife+ 및 CV+: α− = α+ = α/2인 경우에도 signed-residual 분포가 우연히 비대칭으로 남을 수 있으므로, 비대칭 구간이 원래 방법과 반드시 같지는 않다.Steinberger and Leeb [2018]은 이전에 비대칭 jackknife를 고려했으며, 이에 대응하는 비대칭 jackknife-minmax 및 CV+ 구성도 정의된다.
A 비대칭 jackknife+ 및 CV+: 대칭 방법에 대해 증명된 모든 coverage guarantee는 비대칭 대응 방법에도 성립하며, assumption-free 설정에서 비대칭 jackknife+의 1−2α coverage도 포함된다.증명은 별도의 residual matrix를 사용하여 오른쪽 꼬리의 noncoverage를 α+로, 왼쪽 꼬리의 noncoverage를 α−로 제한한다.
B.1 jackknife-minmax의 증명 (Theorem 3): jackknife-minmax 증명에서는 comparison matrix를 변경하여 각 data point의 가장 작은 residual을 해당 point를 제외했을 때 얻은 residual과 비교한다.그 외에는 jackknife+에 사용된 세 단계 구조를 따른다. 즉, strange point를 제한하고, exchangeability를 적용하며, strange point를 noncoverage와 연결한다.
B.1 jackknife-minmax의 증명 (Theorem 3): 수정된 matrix는 strange point의 수를 결정론적으로 α(n + 1)로 제한하여, 이에 대응하는 jackknife+ bound인 2α(n + 1)을 개선한다.이 bound는 matrix 구성과 strange-point 집합 S(A)의 정의에서 얻어진다.
B 추가 증명: 이후 exchangeability는 test point가 strange일 확률을 α로 제한하며, interval은 test point가 strange일 때에만 coverage에 실패할 수 있다.따라서 증명은 결정론적인 strange-point bound를 jackknife-minmax coverage guarantee와 연결한다.
B.2 CV+ 방법의 증명: CV+ 증명 절에서는 CV+를 cross-conformal prediction과 연결하고 이 방법의 theoretical guarantee를 확립한다.제공된 본문은 이러한 목표를 제시하지만 이후의 구체적인 증명 세부사항은 제공하지 않는다.

B.2.1 cross-conformal method와 비교하기 위한 세부 사항

이 절에서는 cross-conformal prediction set이 CV+ interval에 결정론적으로 포함됨을 정당화하고, 수정된 절차를 통해 coverage guarantee를 도출한다. 수정된 방법은 rank-based p-value와 arithmetic-mean validity 결과에 기반해 coverage를 최소 1 − 2α로 달성한다.

결정론적 포함: cross-conformal prediction set은 CV+ prediction interval (13)에 결정론적으로 포함된다.증명에서는 보조 매개변수 τ에 대한 monotonicity와 leave-fold-out prediction 및 residual에 대한 order-statistic bound를 사용한다.
Coverage guarantee: 수정된 K-fold cross-conformal method는 Vovk et al. [2018]이 보인 바와 같이 predictive coverage를 최소 1 − 2α 달성한다.Vovk et al. [2018]은 fold-specific p-value를 사용해 수정된 방법이 1 − 2α guarantee를 제공함을 보인다.
Coverage guarantee: 각 fold-specific p-value는 해당 fold의 다른 residual과 test residual을 비교하며, τ ∼ Unif[0, 1]은 discretization을 제거한다.실제 test value를 대입하면 rank-based p-value는 [0, 1]에서 균등분포를 따른다.
Coverage guarantee: coverage 결과는 Vovk and Wang [2012, Corollary 2]에 따라, 임의의 α ∈ [0, 1]에 대해 p-value의 arithmetic mean이 factor of 2까지 valid하기 때문에 성립한다.Vovk et al. [2018]은 수정된 방법의 coverage guarantee를 확립하기 위해 이 선행 결과를 인용한다.

B.2.2 Theorem 4의 증명 · B.3 Theorem 5의 증명

Theorem 4의 증명은 strange-point 논증을 fold 구조의 residual 비교로 확장해 K-fold coverage guarantee를 확립한다. Theorem 5는 target 1 − α coverage를 갖는 oracle leave-one-out method를 먼저 도입한 뒤, inflated jackknife method를 이 방법과 연결한다.

B.2.2 Theorem 4의 증명: K-fold 증명은 m = n/K개의 test point를 구성하고, 데이터를 folds S_1, …, S_K로 나누며, test point를 추가 fold S_{K+1}로 취급한다.이 설정을 통해 Theorem 4에 사용되는 fold별 residual 및 exchangeability 논증이 가능해진다.
B.2.2 Theorem 4의 증명: 증명에서는 fold를 제외한 regression fit, residual matrix, 그리고 comparison score가 threshold (1 − α)(n + 1)을 초과하는 “strange” point의 집합을 정의한다.이 객체들은 Theorem 1의 증명에 나온 대응 구성들을 일반화한다.
B.2.2 Theorem 4의 증명: strange point의 수는 결정론적으로 2α(n + m) + (1 − 2α)(m − 1) − 1 이하로 제한된다.이 bound는 comparison game에 참여하지 않는 동일 fold 내 pair를 고려해 얻어진다.
B.2.2 Theorem 4의 증명: Exchangeability와 fold를 보존하는 permutation을 이용하면 test point가 strange일 확률은 2α + 1 − K/n 이하로 제한된다.Fold 구조는 완전한 permutation invariance를 막으므로, 증명에서는 fold membership를 보존하는 permutation을 사용해 관련 확률을 같게 만든다.
B.2.2 Theorem 4의 증명: CV+ interval의 비포함은 test point가 strange임을 함의하므로 coverage proof가 완성된다. 이 논증은 cross-conformal prediction set에 대해서도 더 강한 명제를 제공한다.더 강한 명제는 cross-conformal prediction set에서 제외되면 test point가 strange임을 뜻하며, jackknife+의 경우는 n = K에 해당한다.
B.3 Theorem 5의 증명: Theorem 5는 먼저 실제로 구현할 수는 없지만 target 1 − α coverage rate를 달성하는 oracle leave-one-out method를 도입한다.이후 증명에서는 ϵ-inflated jackknife와 2ϵ-inflated jackknife+를 이 oracle method와 연결한다.

B.3.1 Oracle method … B.5.1 jackknife 및 naive methods의 증명

증명은 exchangeability를 통해 oracle coverage를 확립한 뒤, stability bound를 사용해 이를 jackknife와 jackknife+로 전달하며, naive 및 jackknife interval의 한계를 보여주는 병리적 예시를 구성한다. 제시된 반례에서도 jackknife+ 구성은 coverage를 유지한다.

B.3.1 Oracle method: oracle method는 i.i.d. 데이터와 labeling-invariant algorithm에서 residual이 exchangeable이므로 1 − α′ coverage를 달성한다.test residual은 oracle residual 사이에서 균등하게 무작위인 rank를 가지며, 동률 때문에 첫 번째 부등식을 등식으로 바꿀 수 없다.
B.3.2 jackknife에 대한 bound: jackknife 증명은 out-of-sample stability와 Markov’s inequality로 oracle interval과 jackknife interval의 차이를 bound하여 oracle coverage 결과를 전달한다.이 논증은 training point와 test point를 교환할 때 i.i.d. 대칭성을 사용한다.
B.3.3 jackknife+에 대한 bound: jackknife+의 경우, 증명은 α′ = α + √ν에서 jackknife+와 jackknife를 비교하고 stability와 Markov’s inequality를 사용해 두 interval endpoint에서의 실패를 제어한다.실패가 발생하려면 충분히 많은 leave-one-out prediction이 full prediction과 같은 방향으로 달라야 한다.
B.4 Theorem 6의 증명: Theorem 6의 증명은 naive residual과 leave-one-out residual을 비교하고 in-sample stability, Markov’s inequality, Theorem 5의 coverage 결과를 사용한다.비교는 1 − α′ 수준에서 실행한 jackknife에 대해 수행되며, α′ = α + √ν이다.
B.5 Theorem 2의 증명: Theorem 2는 모든 ϵ > 0에 대해 naive 및 jackknife interval의 ϵ-확장 버전에서도 coverage lower bound를 증명함으로써 강화된다.이 절은 두 method에 대한 병리적 예시를 구성한다.
B.5.1 jackknife 및 naive methods의 증명: 이 병리적 구성은 training covariate에서 0을 반환하고 그 외에서는 (1 + ϵ)n을 반환하는 regression algorithm을 사용하며, X ∼ N(0, 1)이고 Y ≡ 0이다.서로 다른 covariate가 probability 1로 발생하므로 leave-one-out residual과 naive residual의 거동이 결정된다.
B.5.1 jackknife 및 naive methods의 증명: 이 예시에서 jackknife+ interval은 왼쪽 endpoint에 0을 포함하므로 coverage를 유지한다.이는 jackknife 및 naive interval에서 조사한 병리적 거동과 대조된다.

B.5.2 jackknife+ 증명

이 절에서는 jackknife+ coverage가 대략 1 − 2α보다 높을 수 없음을 보이는 i.i.d. 예시를 구성한다. 증명은 잘못된 예측 영역과 concentration bound를 결합해 주장된 coverage bound를 확립한다.

동기: 이 논증은 Vovk의 exchangeable-data 예시 [2015, Appendix A]에서 착안했지만, 증명이 i.i.d. data를 가정하므로 더 기술적인 구성이 필요하다.이 절에서는 해당 예시에서 얻는 직관과 여기서 요구되는 더 강한 설정을 대조한다.
증명 아이디어: 이 구성에서는 test point가 “bad” 영역에 놓일 때 jackknife+가 거의 확실하게 실패하며, 이는 대략 2α의 확률로 발생한다.여집합인 “good” 영역에서는 예측이 정확하지만, bad 영역에서의 체계적 과소추정이 noncoverage를 유발한다.
형식적 구성: 형식적 구성에서는 tuning parameter와 i.i.d. data distribution을 선택한 뒤, leave-one-out 동작이 bad 영역의 실패 패턴을 만들어내는 regression algorithm을 정의한다.증명에서는 관련 확률을 bound하기 전에 distribution, response scaling, fitted regression function을 명시한다.