기술 요약: 국소 적응형 불확실성 영역을 갖는 3 진 결정 트리

문제 제기

CART 알고리즘과 같은 표준 결정 트리는 하드 이진 임계값을 사용하여 특징 공간을 분할합니다. 이 메커니즘은 결정 경계와의 근접성에 관계없이 모든 인스턴스에 동일한 신뢰도를 부여합니다. 결과적으로 최적 임계값 $\theta$ 에서 멀리 떨어진 인스턴스는 그 위에 바로 위치한 인스턴스와 동일한 확신으로 처리됩니다. 이러한 "하드 커밋 (hard commitment)"은 알려진 약점을 생성합니다: 학습된 분할이 가장 신뢰할 수 없는 경계 근처의 인스턴스에 대해 확신을 과장하여, 예측이 모호할 수 있음을 하위 응용 프로그램에 알리지 못하게 합니다.

불확실성을 해결하기 위한 기존 접근 방식은 종종 외부 노이즈 사양 (예: 알려진 센서 오차) 이나 데이터셋 수준의 통계에서 도출된 전역 임계값에 의존합니다. 이러한 방법들은 각 노드에서의 특정 분할 품질이나 데이터 분포에 국소적으로 적응하지 못합니다. 또한, 퍼지 결정 트리나 소프트 결정 트리 같은 접근 방식들은 종종 국소 분할 통계에서 도출된 명시적이고 해석 가능한 불확실성 영역을 결여하고 있습니다.

방법론

본 논문은 최적 임계값 $\theta^*$ 를 중심으로 반폭이 $\delta$ 인 국소 적응형 불확실성 영역을 표준 이진 분할에 추가하는 3 진 결정 트리 (Ternary Decision Trees) 를 소개합니다.

3 진 평가

특징 $x_f$ 와 임계값 $\theta^*$ 에 대해 결정 논리는 다음과 같이 정의됩니다:

• True (결정적): $x_f > \theta^* + \delta$
• False (결정적): $x_f \leq \theta^* - \delta$
• Undec (경계 - 불확실): $\theta^* - \delta < x_f \leq \theta^* + \delta$

Undec 영역에 속하는 인스턴스는 예측을 유보하지 않습니다. 대신, 두 자식 서브트리의 확률 출력에 대한 거리 가중치 혼합으로 형성된 예측을 받습니다. 중요한 점은 이러한 인스턴스가 "경계 - 불확실"로 플래그가 지정되어, 클래스 예측을 유보하지 않고도 하위 시스템이 이를 다르게 처리 (예: 인간 검토를 위한 라우팅) 할 수 있다는 것입니다.

국소적 $\delta$ 계산

핵심 기술적 기여는 표준 CART 분할 찾기 동안 이미 계산된 통계를 사용하여 각 노드에서 $\delta$ 를 국소적으로 유도하는 것으로, 외부 데이터나 노이즈 모델이 필요하지 않습니다. 논문은 다섯 가지 방법을 제안하고 평가합니다:

1. Quality-Plateau ($\delta_{QP}$): $\theta^*$ 주변의 분할 기준 곡선 (예: 지니 이득) 에서의 "고원 (plateau)"의 너비를 측정합니다. 넓은 고원은 데이터가 최적 분할 위치를 정확하게 제약하지 않음을 나타냅니다.
2. Class-Overlap ($\delta_{CO}$): 경험적 백분위수를 기반으로 클래스 조건부 특징 분포가 겹치는 영역의 너비를 계산합니다.
3. Gain-Ratio ($\delta_{GR}$): 정보 이득을 분할 엔트로피로 나눈 이득 비율 (Gain Ratio) 로 특징 범위를 역비례하여 스케일링합니다. 낮은 이득 비율은 모호한 분할을 나타내며, 이는 더 큰 $\delta$ 로 이어집니다.
4. Node-Bootstrap ($\delta_{NB}$): 노드의 훈련 데이터에 대한 부트스트랩 리샘플링을 통해 최적 임계값 $\theta^*$ 의 표준 편차를 측정합니다. 이는 임계값 불안정성을 직접 정량화합니다.
5. Margin ($\delta_{M}$): 서포트 벡터 머신 (SVM) 에서 영감을 받아, $\delta$ 를 $\theta^*$ 에서 가장 가까운 교차 클래스 훈련 예제 (해당 노드의 "서포트 벡터") 까지의 거리로 정의합니다. 분할이 완벽하게 깔끔하다면 인접한 데이터 포인트 간의 물리적 간격을 사용합니다.

라우팅 아키텍처

불확실한 인스턴스를 전파하기 위해 두 가지 아키텍처가 평가되었습니다:

• 확률적 라우팅 (Probabilistic Routing): 트리 구조는 이진으로 유지됩니다. 예측 시, 불확실성 영역의 인스턴스는 임계값으로부터의 거리에 반비례하는 가중치로 두 자식 노드 모두로 라우팅되며, 출력은 혼합됩니다.
• 하드 미들 분기 (Hard Middle Branch): 트리 구조에 불확실성 영역 내의 인스턴스만을 대상으로 훈련된 세 번째 자식 노드가 추가됩니다.
  실험 결과는 확률적 라우팅이 일반적으로 하드 - 미들 접근법보다 우수함을 보여주었는데, 후자는 불확실한 예제를 왼쪽 및 오른쪽 분기의 훈련 세트에서 제거하여 그 품질을 저하시키기 때문입니다.

주요 기여

1. 프레임워크: 모든 분할에 대해 원칙적이고 국소 적응형인 불확실성 영역을 제공하는 3 진 결정 트리의 도입.
2. 다섯 가지 추정 방법: 외부 노이즈 모델 없이 표준 CART 분할 통계만을 사용하여 $\delta$ 를 계산하는 다섯 가지 고유한 방법의 유도.
3. 라우팅 평가: 확률적 혼합이 대부분의 방법에서 우월함을 보여주는 확률적 라우팅과 하드 - 미들 라우팅의 비교 분석.
4. 광범위한 경험적 평가: 72 개의 OpenML-CC18 데이터셋, 세 가지 Breiman 합성 벤치마크 (알려진 베이지오 오류 포함), 그리고 네 가지 고위험 의료/금융 데이터셋에 대한 평가.
5. 진단 프레임워크: 방법의 플래깅률이 데이터셋의 이론적 비감소 오류와 얼마나 잘 일치하는지 평가하기 위한 Undecided/Bayes (U/B) 비율의 도입.

결과

광범위한 유효성 (OpenML-CC18)

72 개 데이터셋 전반에 걸쳐, 확률적 라우팅을 사용한 모든 다섯 가지 방법은 Decided Accuracy(불확실하지 않은 인스턴스로 제한된 정확도) 에서 표준 CART 베이스라인을 $p \leq 0.001$로 유의하게 능가했습니다.

• Margin Method: 플래깅률당 정확도 향상 ($\eta = 0.104$) 측면에서 가장 높은 효율을 달성했습니다. 72 개 데이터셋 중 42 개에서 우승했으며, 인스턴스의 16.7% 만을 불확실한 것으로 플래그했고 추가 하이퍼파라미터가 전혀 필요하지 않았습니다.
• Class-Overlap 및 Gain-Ratio: 높은 결정적 정확도를 달성했지만 인스턴스의 상당 부분 (각각 71% 와 58%) 을 플래그하여 효율성이 낮았습니다.
• Node-Bootstrap: 잘 수행되었으나 계산 비용이 많이 들었으며 $N > 20,000$인 데이터셋에서는 제외되었습니다.

이론적 분석 (Breiman 벤치마크)

알려진 베이지오 오류를 가진 합성 데이터셋에서:

• Margin: 기하학적으로 깔끔한 데이터에서 자기 보정 행동을 보였으며, 매우 적은 수의 인스턴스를 불확실한 것으로 플래그했습니다 (U/B 비율 < 0.5). 경계가 명확할 때 CART 와 유사하게 작동했습니다.
• Node-Bootstrap 및 Quality-Plateau: 더 어려운 데이터셋 (더 높은 베이지오 오류) 에서 더 많은 인스턴스를 플래그하는 비례 보정 행동을 보였으나, 모든 방법은 이론적 베이지오 오류에 비해 과도하게 플래그했습니다 (U/B > 1).
• 보정 격차: 어떤 방법도 U/B 비율 1.0 을 달성하지 못했는데, 이는 국소 임계값 불확실성이 전역 베이지오 오류와 직접적으로 대응하지 않음을 나타냅니다.

도메인 응용

• 유방촬영술: Node-Bootstrap 은 사례의 10.8% 를 불확실한 것으로 플래그하면서 CART 대비 결정적 정확도를 0.71% 향상시켰습니다. 이는 2 차 검토가 필요한 사례를 식별하는 데 유용합니다.
• 당뇨병: Node-Bootstrap 은 +9.8% 의 정확도 향상을 달성했지만 환자 중 63.4% 를 플래그하여 정확도와 플래깅률 사이의 트레이드오프를 시사했습니다. Margin 방법은 더 보수적이고 실용적인 운영 지점을 제공했습니다 (+0.4% 향상, 9.5% 플래깅).
• 한계: 작은 클리블랜드 심장병 데이터셋 ($N=303$) 에서 Node-Bootstrap 은 신뢰할 수 없는 분산 추정치로 인해 성능이 저하되었습니다. 독일 신용 데이터셋에서는 Margin 방법이 베이스라인보다 성능이 낮아 복잡한 경제적 특징 상호작용에 대한 한계를 시사했습니다.

중요성과 주장

본 논문은 3 진 트리를 불확실성 인식 분류를 위한 원칙적 원시 (principled primitive) 로 확립한다고 주장합니다. 그 중요성은 다음과 같습니다:

• 실용적 유용성: 예측을 유보하지 않고 경계 - 불확실 예측을 플래그할 수 있는 메커니즘을 제공하여, 하위 시스템 (예: 의료 스크리닝, 신용 심사) 이 다른 처리 전략을 적용할 수 있게 합니다.
• 계산적 실현 가능성: 외부 데이터나 복잡한 재훈련 없이 기존 분할 통계에서 불확실성 영역을 유도합니다.
• 이론적 기반: "Undec" 판정이 예측 자체의 거부가 아니라 예측 신뢰도에 대한 한정자 (qualifier) 로 작용하는 프레임워크를 제공합니다.

저자들은 겸손하게도, 이러한 방법들이 결정적 정확도를 향상시키지만 플래깅률을 이론적 베이지오 오류에 완벽하게 보정하지는 못한다고 지적하며, 이 보정 문제를 향후 작업을 위한 구체적인 열린 과제로 규정했습니다.