Decomposing Observational Multiplicity in Decision Trees: Leaf and Structural Regret

이 논문은 의사결정나무 모델의 관측적 다중성을 '리프 후회'와 '구조적 후회'로 분해하여 구조적 불안정성이 주요 원인임을 규명하고, 이를 선택적 예측의 거절 메커니즘으로 활용함으로써 모델 안전성을 향상시키는 새로운 프레임워크를 제시합니다.

핵심

🌳 핵심 비유: "숲의 지도를 그리는 문제"

생각해 보세요. 우리가 어떤 마을의 주민들 (데이터) 을 '부자 (1)'와 '가난한 사람 (0)'으로 나누는 **지도 (결정 트리)**를 그리고 있다고 가정해 봅시다.

이 논문은 이 지도를 그릴 때 생기는 두 가지 종류의 "혼란"을 찾아냈습니다.

1. 잎의 후회 (Leaf Regret): "같은 방 안에서의 작은 소음"

• 상황: 지도를 그리는 도중, 우리가 이미 정해진 하나의 작은 방 (잎, Leaf) 을 생각해 봅시다. 이 방 안에는 주민들이 모여 있습니다.
• 문제: 이 방 안의 주민들이 "부자일까, 가난할까?"라고 질문했을 때, 정답이 100% 명확하지 않고 우연에 의해 달라질 수 있습니다. (예: 오늘 기분 좋은 날엔 부자로 보이지만, 내일엔 가난해 보일 수도 있는 모호한 경우).
• 비유: 방 안의 작은 소음입니다. 방 (구조) 은 그대로인데, 안에 있는 사람 (데이터) 들의 표정이 조금씩 달라서 우리가 "이 사람은 부자야"라고 말하기가 조금 애매해지는 상태입니다.
• 해결: 이 소음은 방에 사람이 더 많이 모이면 (데이터가 많아지면) 자연스럽게 줄어들지만, 완전히 사라지지는 않습니다.

2. 구조적 후회 (Structural Regret): "지도 자체를 다시 그리는 혼란"

• 상황: 이제 지도를 그리는 방법 자체가 문제입니다. 같은 마을 주민들을 대상으로 지도를 그릴 때, 오늘 그리는 지도와 내일 그리는 지도가 완전히 다를 수 있습니다.
• 문제: "부자"와 "가난한 사람"을 나누는 **경계선 (분할선)**이 조금만 흔들려도, 한 사람이 '부자' 구역에서 '가난한 사람' 구역으로 쏙 넘어갈 수 있습니다.
• 비유: 지도의 모양이 자꾸 변하는 것입니다. 같은 주민을 두고, 오늘은 "왼쪽이 부자"라고 하고 내일은 "오른쪽이 부자"라고 하면, 그 주민은 매우 당황스럽습니다. 지도를 그리는 기준 (알고리즘) 이 데이터의 작은 변화에 너무 민감하게 반응해서, 지도의 구조 자체가 불안정해진 상태입니다.

---

🔍 이 연구가 발견한 놀라운 사실

연구진은 이 두 가지 혼란을 측정해 보았는데, 아주 흥미로운 결과를 얻었습니다.

1. 주범은 '지도의 불안정성'입니다: 대부분의 경우, 예측이 달라지는 진짜 이유는 방 안의 작은 소음 (잎의 후회) 때문이 아니라, **지도의 경계선이 자꾸 흔들리기 때문 (구조적 후회)**이었습니다.
   • 예시: 어떤 데이터셋에서는 지도가 흔들리는 영향이, 방 안 소음의 영향보다 15 배 이상 컸습니다!
2. 왜 중요한가? 우리가 "이 사람은 부자다"라고 말할 때, 그 결정이 단순히 "오늘 데이터가 그랬기 때문"인지, 아니면 "지도 그리는 방식이 너무 불안정해서"인지 구별해야 합니다.

---

🛡️ 실용적인 해결책: "모르겠으면 말하지 마세요" (선택적 예측)

이 연구는 이 발견을 이용해 **"안전장치"**를 만들었습니다.

• 전략: AI 가 "내가 100% 확신하지 못해"라고 느낄 때, 아예 답을 내지 않고 **"이건 전문가 (사람) 가 다시 봐야 해요"**라고 손을 드는 것입니다.
• 어떻게 하나요? AI 가 내린 결정이 '지도의 흔들림 (구조적 후회)' 때문에 불안정하다고 판단되면, 그 경우는 제외하고 나머지 안정적인 경우에만 답을 줍니다.
• 결과: 이렇게 하면, AI 가 답을 내는 정확도 (Recall) 가 92% 에서 100% 로 올라갔습니다.
  • 즉, "모르는 척"하는 순간, AI 는 훨씬 더 신뢰할 수 있는 도구가 됩니다.

---

💡 요약: 우리가 배운 교훈

1. AI 의 실수는 두 가지입니다: 하나는 "데이터가 애매해서" (잎의 후회), 다른 하나는 "모델이 너무 예민해서" (구조적 후회) 입니다.
2. 대부분의 실수는 모델이 예민해서 옵니다: 결정 트리 같은 모델은 데이터가 조금만 바뀌어도 지도 (구조) 를 완전히 바꿔버립니다. 이것이 예측이 불안정한 진짜 원인입니다.
3. 안전한 AI 를 위해: AI 에게 "모르는 건 말하지 마라"라고 가르치면 (선택적 예측), AI 는 더 이상한 실수를 하지 않게 되고, 중요한 결정 (대출 승인, 의료 진단 등) 에서 훨씬 더 신뢰할 수 있게 됩니다.

이 논문은 결국 **"AI 가 언제 자신이 틀릴 수 있는지 스스로 알고, 그 순간에는 침묵하는 것이 더 안전하다"**는 것을 수학적으로 증명하고, 그 방법을 제시한 연구입니다.

기술 요약

논문 요약: 의사결정나무 (Decision Trees) 에서의 관찰적 다중성 분해: 리프 (Leaf) 와 구조적 후회 (Regret)

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

• 예측적 다중성 (Predictive Multiplicity): 많은 머신러닝 작업에서 거의 동일한 성능을 내는 여러 모델이 존재할 수 있으며, 이는 동일한 개인에게 상반된 예측을 내릴 수 있는 '예측적 임의성 (Predictive Arbitrariness)'을 초래합니다. 이는 의료, 신용평가, 법률 등 고위험 분야에서 심각한 윤리적 및 안전 문제를 야기합니다.
• 관찰적 다중성 (Observational Multiplicity): 최근 연구에서 모델의 부재 (underspecification) 가 아닌, 데이터 생성 과정 자체의 확률적 특성에서 기인하는 다중성이 강조되었습니다. 즉, 관찰된 레이블은 근본적인 확률 분포의 단일 실현일 뿐이며, 동일한 분포에서 다른 레이블을 추출하면 다른 모델이 학습되어 예측이 달라질 수 있습니다.
• 연구의 격차: 기존 관찰적 다중성 이론은 주로 로지스틱 회귀와 같은 매끄러운 (smooth) 모델에 적용되었으나, 비매끄럽고 분할 기반 (partition-based) 인 의사결정나무 모델에 대한 연구는 부족합니다. 의사결정나무는 데이터의 작은 변화에도 민감하게 반응하여 구조가 급격히 변할 수 있어, 기존 이론을 직접 적용하기 어렵습니다.

2. 방법론 (Methodology)

저자는 의사결정나무에서의 관찰적 다중성을 두 가지 상보적인 개념인 **리프 후회 (Leaf Regret)**와 **구조적 후회 (Structural Regret)**로 분해하는 프레임워크를 제안합니다.

• 리프 후회 (Leaf Regret, $R_{leaf}$):

  • 정의: 고정된 트리 구조 하에서, 특정 리프 (Leaf) 내부에서 유한한 표본 크기로 인해 발생하는 예측의 본질적 변동성.
  • 특징: 레이블의 확률적 실현 (stochastic realization) 으로 인한 불확실성 (Aleatoric uncertainty) 을 반영합니다.
  • 수식: $R_{leaf}^L = Var(\hat{p}_L | L) = \frac{p^*_L(1-p^*_L)}{n_L}$
  • 특성: 리프 크기 ($n_L$) 가 커질수록 0 으로 수렴하며, 몬테카를로 재표본추출 (Monte Carlo resampling) 을 통해 추정 가능합니다.

• 구조적 후회 (Structural Regret, $R_{struct}$):

  • 定义: 학습된 트리 구조 자체가 무작위성 (샘플링 변동성, 분할 선택의 불안정성) 으로 인해 변할 때 발생하는 추가적인 변동성.
  • 특징: 모델의 구조적 불안정성 (Epistemic uncertainty) 을 반영합니다.
  • 특성: 트리 학습 알고리즘의 안정성에 의존하며, 부트스트랩 (Bootstrap) 을 통해 여러 트리를 학습시켜 그 분산을 계산하여 추정합니다.

• 총 예측 변동성 분해:

  • 고정된 입력 $x$에 대한 총 예측 변동성은 다음과 같이 분해됩니다:
    $$Var(\hat{p}(x)) = E_T[R_{leaf}^{L(x;T)}] + R_{struct}(x)$$
  • 이는 **리프 내 변동성 (기대 리프 후회)**과 **트리 구조 간 변동성 (구조적 후회)**의 합임을 수학적으로 증명합니다.

3. 주요 기여 (Key Contributions)

1. 이론적 분해 프레임워크: 매끄럽지 않은 의사결정나무 모델에서 관찰적 다중성을 리프 후회와 구조적 후회로 엄밀하게 분해하는 이론적 기반을 마련했습니다.
2. 통계적 보장 (Statistical Guarantees): 리프 후회에 대한 일관성 (consistency) 과 집중 부등식 (concentration inequalities) 을 증명하여, 추정된 후회가 실제 값에 수렴함을 보였습니다.
3. 실용적 추정 알고리즘: 몬테카를로 시뮬레이션을 통해 리프 후회와 구조적 후회를 추정하는 알고리즘 (Algorithm 1, 2) 을 제안했습니다.
4. 선택적 예측 (Selective Prediction) 적용: 후회 (Regret) 지표를 '거부 (Abstention)' 메커니즘으로 활용하여, 모델이 불확실한 경우 예측을 유보하고 안전성을 높이는 방법을 제시했습니다.

4. 실험 결과 (Results)

다양한 신용평가 데이터셋 (bank_marketing, hmeq, taiwan_credit 등) 을 대상으로 실험을 수행했습니다.

• 분해의 정확성 검증: 이론적으로 분해된 후회의 합 (리프 후회 + 구조적 후회) 은 시뮬레이션을 통해 얻은 실제 예측 분산과 거의 완벽하게 일치함을 확인했습니다 (Fig. 1).
• 구조적 후회의 지배적 역할:
  • 모든 데이터셋에서 구조적 후회가 총 예측 불확실성의 주된 원인임이 확인되었습니다.
  • 특히 taiwan_credit 데이터셋에서는 구조적 후회가 리프 후회보다 약 15 배 이상 크게 나타났습니다 (Table 1). 이는 의사결정나무의 예측 변동성이 리프 내의 노이즈보다 분할 경계 (partition boundaries) 의 불안정성에 의해 주로 결정됨을 의미합니다.
• 최소 리프 크기 ($n_L$) 의 영향: 리프 크기를 증가시키면 리프 후회는 급격히 감소하지만 (Lemma 2), 이는 과소적합 (underfitting) 을 초래하여 로지스틱 손실을 증가시킵니다. 따라서 예측 성능과 안정성 사이의 균형을 찾는 것이 중요합니다.
• 안전성 향상 (Selective Prediction):
  • 추정된 후회 (특히 구조적 후회) 를 기준으로 예측을 거부하는 전략을 적용했습니다.
  • german_credit 데이터셋에서 커버리지 (Coverage) 를 줄여 가장 안정적인 개인만 예측할 경우, 리콜 (Recall) 이 92% 에서 100% 로 향상되었습니다.
  • 이는 모델이 "임의적 (arbitrary)"인 예측을 하는 영역을 정확히 식별하여, 고위험 결정에서 모델의 신뢰도를 높일 수 있음을 보여줍니다.

5. 의의 및 결론 (Significance)

• 안전한 AI 배포: 고위험 분야에서 의사결정나무를 사용할 때, 단순히 평균 성능이 아닌 개별 예측의 안정성을 정량화할 수 있는 도구를 제공합니다.
• 불확실성의 원인 규명: 예측의 불확실성이 '데이터 노이즈' 때문인지, 아니면 '모델 구조의 불안정성' 때문인지 구분함으로써, 적절한 완화 전략 (예: 구조적 불안정성이라면 정규화나 앙상블 강화, 리프 노이즈라면 데이터 확보) 을 수립할 수 있습니다.
• 해석 가능성 및 투명성: 모델이 "추측"을 하고 있는 영역을 식별하여 인간 전문가의 검토 (escalation) 가 필요한 사례를 자동으로 선별하는 '정직한 (honest)' AI 시스템 구축에 기여합니다.

이 연구는 의사결정나무 기반 모델의 관찰적 다중성을 체계적으로 분석하고, 이를 통해 알고리즘적 안전성과 해석 가능성을 높이는 새로운 기준을 제시했다는 점에서 의의가 큽니다.