기술 요약: PINE – 합동 분포 내 예측 동등성을 통한 부스팅 트리 앙상블 가지치기

1. 문제 제기

랜덤 포레스트, 그래디언트 부스팅 결정 트리 (GBDT), XGBoost 와 같은 트리 앙상블 방법은 강력한 예측 성능과 해석 가능성으로 인해 표 형식 데이터에 널리 사용됩니다. 그러나 대규모 앙상블은 높은 추론 비용과 메모리 발자국을 초래하여 견고성 검증 및 공정성 확인과 같은 하위 작업을 복잡하게 만듭니다.

사후 앙상블 가지치기는 표준적인 해결책이지만, 기존 방법들은 압축과 신뢰성(예측 동등성) 사이에서 트레이드오프에 직면해 있습니다:

• 정확도 중심 가지치기: 정확도 - 압축 트레이드오프를 최적화하는 방법들은 종종 예측의 일부 하위 집합을 변경합니다. 이러한 신뢰성 부족은 특정 모델 출력에 의존하는 하위 워크플로우가 존재하는 고위험 분야 (예: 의학, 금융) 에서 의사결정 일관성을 방해할 수 있습니다.
• 신뢰성 있는 가지치기: FIPE(Emine et al., 2025) 와 Born-Again Tree Ensembles(Vidal & Schiffer, 2020) 와 같은 방법들은 전체 입력 공간의 모든 입력에 대해 정확한 예측 동등성을 보장합니다. 이는 의사결정 일관성을 보장하지만, 희귀하거나 분포 밖 (OOD) 인 입력에 대한 예측까지도 보존해야 한다는 요구 사항은 달성 가능한 압축 비율을 심각하게 제한합니다.

본 논문이 다루는 핵심 문제는 실제에서 거의 관찰되지 않는 OOD 입력에 대한 동등성 보장의 제한적인 부담 없이, 높은 신뢰성을 유지하면서 더 높은 압축률을 달성하는 방법입니다.

2. 방법론: PINE

저자들은 PINE(Pruning with In-distribution Equivalence, 분포 내 동등성을 통한 가지치기) 를 제안합니다. 이는 보정된 분포 내 (ID) 영역, $X_{ID}(\alpha)$ 내에서만 예측 동등성을 보장하는 가지치기 프레임워크입니다.

핵심 개념

PINE 는 데이터 분포 하에서 "타당한 (plausible)" 입력으로 제한된 동등성 보장을 통해 신뢰성 있는 가지치기의 제약을 완화합니다. 이는 단일 하이퍼파라미터인 $\alpha$(미커버리지 수준) 를 도입하여 이 영역의 크기를 조절합니다. 이 방법은 동일한 분포에서 샘플링된 미래 입력에 대해 가지치기된 모델이 원래 모델의 예측과 일치할 확률이 적어도 $1-\alpha$임을 보장합니다.

알고리즘 파이프라인

PINE 는 FIPE 에서 사용된 반복적 Pruner-Oracle 프레임워크를 기반으로 하되, Oracle 의 검색 공간을 수정합니다:

1. 타당성 점수 정의: 데이터 분포 하에서 낮은 점수가 더 높은 타당성 (가능성) 을 나타내도록 점수 함수 $s(x)$를 정의합니다. 분포 내 영역은 $X_{ID}(\alpha) = \{x \in \mathcal{X} \mid s(x) \leq \tau(\alpha)\}$로 정의됩니다.
2. Chow-Liu 트리 점수: 논문은 Chow-Liu 트리의 음의 로그 가능도를 타당성 점수로 채택합니다. 연속형 특징은 빈 (bin) 으로 이산화되고, Chow-Liu 트리는 결합 분포를 트리 구조로 근사합니다. 이 선택은 결정적으로 중요한데, 음의 로그 가능도가 root 주변분 + edge 조건부 항의 가법 형태로 분해되기 때문에, 제약 조건 $s(x) \leq \tau(\alpha)$를 효율적으로 혼합 정수 선형 계획법 (MILP) 제약으로 인코딩할 수 있기 때문입니다.
3. 합동 보정 (Conformal Calibration): 보정 집합 $D_{cal}$을 사용하여 **분할 합동 예측 (split conformal prediction)**을 통해 임계값 $\tau(\alpha)$를 결정합니다. 이는 교환성 가정을 전제로 하여, 영역 $X_{ID}(\alpha)$가 미래 입력을 확률 $1-\alpha$ 이상으로 커버하도록 보장합니다.
4. 반복 가지치기:
   • Pruner: 증가하는 제약 집합에서 예측 동등성을 만족하도록 트리 가중치를 업데이트합니다.
   • Oracle: 반례 (예측이 다른 입력) 를 검색하지만, 검색을 오직 영역 $X_{ID}(\alpha)$ 내로만 제한합니다.
   • 이 과정은 ID 영역 내에서 반례가 더 이상 발견되지 않을 때까지 반복됩니다.

이론적 보장

• 확률적 동등성: 교환성 가정 하에서 PINE 는 미래 입력에 대해 가지치기된 모델의 예측이 원래 모델과 일치할 확률에 대해 $1-\alpha$의 하한을 제공합니다.
• 복잡도: Oracle 이 탐색해야 하는 이산 상태의 수는 $e^{\tau(\alpha)}$로 상한이 정해집니다. $\tau(\alpha)$는 $\alpha$에 대해 단조적이므로, $\alpha$를 증가시켜 (더 큰 미커버리지 허용) 검색 공간을 기하급수적으로 줄여 더 높은 압축을 용이하게 합니다.

3. 주요 기여

1. PINE 프레임워크: 엄격한 전역 신뢰성을 높은 확률의 분포 내 신뢰성과 교환하는 새로운 가지치기 방법으로, 신뢰성 있는 가지치기 기준선보다 훨씬 높은 압축 비율을 가능하게 합니다.
2. 합동 통합: 앙상블 가지치기를 위한 보장된 분포 내 영역을 정의하기 위해 분할 합동 예측을 처음 적용하여, 예측 동등성에 대한 엄격한 확률적 상한을 제공합니다.
3. MILP 임베딩 가능한 점수화: 특징 의존성을 포착하는 데 표현력이 있으면서도 MILP 인코딩에 계산적으로 효율적인 타당성 점수로 Chow-Liu 트리의 음의 로그 가능도 사용을 제안합니다.
4. 체계적 트레이드오프 제어: 단일 파라미터 $\alpha$를 통해 신뢰성 - 압축 트레이드오프를 체계적으로 조정할 수 있는 메커니즘을 제공합니다.

4. 실험 결과

저자들은 XGBoost 앙상블 ($M=30$개 트리, 깊이 $D=2$) 을 사용하여 12 개의 공개 표 형식 데이터셋(Adult, COMPAS, Pima-Diabetes 등) 에서 PINE 를 평가했습니다.

• 압축 대 신뢰성: PINE 는 신뢰성 있는 가지치기 기준선 (FIPE) 보다 크게 우위를 점합니다. $\alpha$가 0.05 에서 0.8 로 증가함에 따라 평균 가지치기율은 약 45% 에서 약 68% 로 증가하는 반면, 평균 신뢰성은 높게 유지됩니다 (99.15%–99.96%). 반면, FIPE 는 100% 신뢰성으로 약 44% 의 평균 가지치기율을 달성합니다.
• 정확도 중심 방법과의 비교: 정확도 중심 방법 (IC, DREP, MDEP) 은 테스트 정확도를 유지할 수 있지만, 분포 내 영역에서도 상당한 신뢰성 하락 (종종 90% 미만) 을 보입니다. PINE 는 보정된 영역 내에서 거의 완벽한 신뢰성을 유지합니다.
• 커버리지 검증: 실험적 테스트 커버리지 $\hat{\pi}_{ID}$는 목표값 $1-\alpha$를 밀접하게 추적하여 분할 합동 보정의 효과를 검증합니다.
• 확장성: 이 방법은 트리의 수 ($M$) 보다 트리 깊이 ($D$) 에 더 민감합니다. 더 깊은 트리는 더 국소화된 의사결정 영역으로 인해 달성 가능한 압축을 감소시키는 반면, 더 큰 앙상블은 주로 최적화 실행 시간을 증가시킵니다.

5. 중요성 및 주장

본 논문은 PINE 가 모델 압축의 중요한 격차를 해결한다고 주장합니다. 즉, 기존 신뢰성 있는 방법들은 의사결정 일관성을 희생하지 않고는 모델을 효과적으로 압축하지 못하며, 표준 가지치기 방법들은 일관성을 보장하지 못한다는 점입니다.

• 실용적 영향: PINE 는 향후 발생할 가능성이 높은 입력에 대한 의사결정 일관성을 유지하면서, 신뢰성 있는 기준선보다 최대 30% 더 많은 모델 압축을 가능하게 합니다. 이는 모델 출력이 하위 워크플로우를 트리거하거나 감사 가능성을 요구하는 고위험 분야에서 특히 유용합니다.
• 한계: 저자들은 겸손하게 이 보장이 교환성 가정(분포 이동 없음) 에 의존한다고 인정합니다. 데이터 분포가 이동하면 보장이 약화될 수 있습니다. 또한, 계산 비용은 MILP 해결과 연관되어 있으며, 다중 클래스 설정이나 매우 깊은 트리의 경우 비용이 많이 들 수 있습니다.
• 결론: PINE 는 효율성과 신뢰성이라는 상충되는 목표를 균형 있게 조정하는 검증 가능한 확률적 가지치기 접근법을 제공하여, "정확하지만 일관성 없는" 것과 "일관성 있지만 압축되지 않은" 것 사이의 이분법적 선택을 넘어섭니다.