Interpretable Quantile Regression by Optimal Decision Trees

1. 연구 배경 및 문제 정의 (Problem)

• 배경: 머신러닝 분야에서 정확도뿐만 아니라 해석 가능성 (Interpretability) 과 강건성 (Robustness) 이 중요한 과제로 대두되고 있습니다. 특히 의료, 비즈니스 전략 등에서는 예측의 정확성보다 '왜' 그런 예측이 나왔는지 이해하는 것이 필수적입니다.
• 기존 방법의 한계:
  • 전통적인 의사결정나무는 평균 제곱 오차 (MSE) 를 최소화하여 각 리프 (leaf) 에 평균값을 예측합니다. 이는 분포의 전체적인 형태를 보여주지 못합니다.
  • 양분회귀 (Quantile Regression): 특정 양분 (quantile, $q$) 에 해당하는 값을 예측하여 분포의 하단이나 상단을 추정할 수 있게 하지만, 기존에는 단일 나무를 학습할 때 단 하나의 $q$ 파라미터만 선택해야 하는 문제가 있었습니다.
  • 해석 가능성 부족: 분포의 전체적인 형태를 이해하려면 여러 $q$ 값을 선택해야 하지만, 이를 위해 여러 개의 나무를 독립적으로 학습하면 계산 비용이 급증하고, 모델의 일관성을 파악하기 어렵습니다. 또한, 기존 양분회귀 방법 (예: Quantile Random Forests) 은 해석하기 어렵거나 분포에 대한 사전 가정이 필요합니다.

2. 제안 방법론 (Methodology)

저자들은 QDL8.5 (Quantile DL8.5) 라는 새로운 알고리즘을 제안합니다. 이는 최적 의사결정나무 학습 알고리즘인 DL8.5를 확장하여, 단일 탐색 과정으로 여러 양분 (quantiles) 에 대한 최적의 나무들을 동시에 학습하는 방법입니다.

핵심 기술적 요소:

1. 동시 나무 학습 (Simultaneous Tree Learning):

   • 기존 DL8.5 는 하나의 손실 함수 (loss function) 를 최적화합니다. QDL8.5 는 여러 양분 ($q_1, q_2, \dots$) 에 대한 손실 함수를 동시에 고려합니다.
   • 서로 다른 양분들에 대한 최적 나무가 매우 유사할 것이라는 가정을 바탕으로, 단 하나의 탐색 공간 (search space) 을 한 번만 탐색하여 모든 양분에 대한 최적 나무를 도출합니다.
   • 가지치기 (Pruning) 로직을 수정하여, 모든 양분에 대해 해가 없거나 상한선 (upper bound) 을 만족하지 못할 때만 탐색을 중단하도록 설계했습니다.

2. 효율적인 양분 손실 계산 (Efficient Quantile Loss Computation):

   • 양분 손실 (Quantile Loss) 계산은 일반적으로 $O(N)$의 시간이 소요되지만, $|q|$개의 양분을 계산하면 $O(|q|N)$의 복잡도가 발생합니다.
   • 최적화 전략: 데이터를 $y$ 값 기준으로 미리 정렬 (Sorting) 해 둡니다.
     • 정렬된 배열을 사용하면 양분 값 ($\hat{y}_q$) 을 $O(1)$ 시간에 구할 수 있습니다.
     • 양분 손실 공식을 변형하여, 예측값보다 크고 작은 데이터의 합 (sum) 만 저장하면 되므로, 데이터를 한 번만 순회하며 모든 양분의 손실을 $O(N + |q|)$ 시간에 계산할 수 있습니다.
     • 결과적으로 시간 복잡도를 $O(N)$ 수준으로 유지하여 계산 효율성을 극대화했습니다.

3. 분포 추정 및 해석:

   • 학습된 여러 나무들은 각기 다른 양분 값을 예측합니다. 이를 통해 샘플의 조건부 분포 (Conditional Distribution) 를 근사할 수 있습니다.
   • 예측된 양분 값들을 커널 밀도 추정 (KDE) 과 결합하여 확률 밀도 함수 (PDF) 로 시각화할 수 있습니다.

3. 주요 기여 (Key Contributions)

1. QDL8.5 알고리즘 제안: DL8.5 알고리즘을 확장하여, 단일 탐색 과정에서 여러 양분에 대한 최적의 얕은 (shallow) 의사결정나무 집합을 학습할 수 있게 했습니다.
2. 계산 효율성: 여러 나무를 학습하더라도 단일 나무 학습과 비교하여 거의 추가적인 계산 비용 (computational overhead) 이 발생하지 않음을 증명했습니다.
3. 해석 가능성과 강건성:
   • 분포에 대한 사전 가정 없이 전체 조건부 분포를 예측합니다.
   • 이상치 (outliers) 에 강건한 예측을 제공합니다.
   • 각 나무가 특정 양분 (예: 10%, 90%) 에 대응하므로, 모델의 의사결정 과정을 인간이 직관적으로 이해할 수 있습니다.

4. 실험 결과 (Results)

저자들은 합성 데이터와 3 개의 실제 데이터셋 (Air Quality, Solar Flares, Stock Portfolio) 을 사용하여 QDL8.5 를 Quantile Random Forests (QRF) 와 CaDET 와 비교 평가했습니다.

• 정확도 (Accuracy):
  • MISE (평균 적분 제곱 오차), NLL (음의 로그 가능도), MQE (평균 양분 오차), CRPS (연속 순위 확률 점수) 등 다양한 지표에서 QDL8.5 가 최상이거나 2 위를 기록하여 기존 방법들과 경쟁력 있는 성능을 보였습니다.
  • 특히 합성 데이터셋에서는 알려진 실제 분포와 매우 유사한 예측 분포를 생성했습니다.
• 효율성 (Efficiency):
  • 나무의 개수가 증가함에 따라 Naive 방식 (각 나무를 독립적으로 학습) 은 실행 시간이 선형적으로 증가하는 반면, QDL8.5 는 나무 개수에 거의 무관하게 일정한 시간을 유지했습니다.
  • 5 개의 나무를 학습할 때 약 4.74 배의 속도 향상 (Speedup) 을 확인했습니다.
• 해석 가능성 (Interpretability):
  • 자카드 지수 (Jaccard Index) 를 통해 학습된 나무들의 분할 (partition) 유사성을 분석했습니다.
  • 결과: 인접한 양분에 해당하는 나무들은 매우 유사하게 분할을 수행했습니다. 전체 분포를 이해하기 위해 모든 나무를 분석할 필요 없이, 몇 개의 대표 나무만으로도 전체 분포의 특성을 파악할 수 있음을 보였습니다.
  • 분포의 꼬리 (extreme quantiles) 와 중심부는 서로 다른 나무 구조를 가지며, 이는 양분회귀가 분포의 특정 부분을 설명하는 데 유용함을 입증했습니다.

5. 의의 및 결론 (Significance)

이 연구는 해석 가능한 AI 시스템을 구축하는 데 중요한 진전을 이루었습니다.

• 신뢰성 향상: 분포의 전체적인 형태를 예측함으로써 사용자는 예측의 불확실성을 이해하고, 과소/과대 예측을 의도적으로 조절할 수 있습니다 (예: 재고 관리 시 수요의 90% 양분 예측).
• 효율적 최적화: 복잡한 앙상블 모델 (랜덤 포레스트 등) 을 사용하지 않고도, 최적의 단일 나무들을 조합하여 높은 정확도와 해석 가능성을 동시에 달성했습니다.
• 실용성: 의료, 금융, 공급망 관리 등 예측의 이유와 불확실성을 모두 이해해야 하는 고위험 분야에서 즉시 적용 가능한 강력한 도구를 제공합니다.

요약하자면, 이 논문은 최적 의사결정나무 알고리즘을 변형하여, 계산 비용은 낮추면서 분포 전체를 예측하고 해석 가능한 양분회귀 모델을 구현하는 획기적인 방법을 제시했습니다.