기술 요약: 파티션 트리: 일반 결과 공간에 대한 조건부 밀도 추정

문제 제기

의사결정나무는 점 예측 (분류 및 회귀) 에서의 해석 가능성과 효율성으로 널리 평가받습니다. 그러나 일반 결과 공간 (연속 변수와 범주형 변수를 동시에 지원) 에 대한 조건부 밀도 추정으로 트리 기반 방법을 확장하는 것은 여전히 어렵습니다. 기존 접근 방식은 다음과 같은 특정 한계를 겪고 있습니다:

• 모수적 가정: CADET 과 같은 방법은 잎 노드에서 모수적 조건부 밀도를 사용하는데, 이는 복잡한 비가우시안 분포를 포착하지 못할 수 있습니다.
• 확장성: 분할과 잎별 히스토그램을 동시에 최적화하는 CDTree 와 같은 방법은 계산 집약적일 수 있어 대규모 데이터셋에 대한 적용을 제한합니다.
• 통합 형식화: 목표 분포에 모수적 제약을 부과하지 않고 분류와 회귀를 조건부 밀도 추정의 특수한 경우로 취급하는 통합 프레임워크가 부족합니다.

방법론

1. 이론적 프레임워크: 측도론적 형식화

저자들은 측도론에 기반한 파티션 트리 (Partition Tree) 프레임워크를 제안합니다.

• 결합 공간 파티셔닝: 공변량 공간 $X$만 파티셔닝하는 전통적인 트리와 달리, 파티션 트리는 공변량 - 결과 결합 공간 $Z = X \times Y$의 데이터 적응형 파티션 $\pi_N$을 구성합니다.
• 조각별 상수 추정: 조건부 밀도 $f(y|x)$는 이러한 파티션 위에 정의된 조각별 상수 함수로 모델링됩니다.
• 라돈 - 니코딤 도함수: 이 방법은 $\mu_Y$가 기준 측도 (이산 결과의 경우 계수 측도, 연속의 경우 르베그 측도) 인 곱측도 $\nu = P_X \otimes \mu_Y$에 대한 라돈 - 니코딤 도함수를 통해 조건부 밀도를 정의합니다.
• 추정기: 파티션 내의 셀 $A = A_X \times A_Y$에 대해 밀도 추정치는 다음과 같습니다:
  $$\hat{f}_\pi(z) = \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)}$$
  여기서 $n_{XY}$와 $n_X$는 경험적 계수입니다. 이 형식화는 혼합 유형 결과를 자연스럽게 처리하며 분류와 회귀가 특수한 경우로 도출되도록 합니다.

2. 트리 구성 알고리즘

트리는 조건부 음의 로그 가능도를 직접 최소화하는 탐욕적 최선 우선 전략을 사용하여 성장합니다.

• 목적: 분할 기준은 로그 손실의 경험적 이득을 최대화합니다:
  $$\hat{G}(\pi', \pi) = \sum_{A' \in \{A_l, A_r\}} \frac{n_{XY}(A')}{N} \log \left( \frac{n_{XY}(A')}{n_X(A') \mu_Y(A'_Y)} \right) - \frac{n_{XY}(A)}{N} \log \left( \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)} \right)$$
• 분할 유형:
  • 공변량 분할 ($X$): 공변량 공간을 정제합니다 (표준 트리 분할).
  • 결과 분할 ($Y$): 고정된 공변량 영역 내에서 결과 빈 (bin) 을 정제합니다. 이를 통해 트리는 결과 분포에 대한 히스토그램을 적응적으로 구성할 수 있습니다.
• 효율성: 이 알고리즘은 효율적인 정렬 및 접두사 합 기법을 활용하여 후보 분할을 $O(d_Z N \log N)$ 시간 (균형 트인의 경우 $O(d_Z N \log^2 N)$) 에 평가하여 표준 CART 의 확장성과 일치합니다.
• 절단: 무계 연속 결과의 경우, 유한 측도를 보장하기 위해 데이터 의존적 절단 (최소 - 최대 상자) 을 적용하며, 절단이 점근적으로 모든 확률 질량을 포착한다는 이론적 보장이 있습니다.

3. 파티션 포레스트

안정성과 예측 성능을 향상시키기 위해 저자들은 **파티션 포레스트 (Partition Forest)**를 소개합니다. 이는 부트스트랩 샘플 (배깅) 로 훈련된 여러 파티션 트리에서 조건부 밀도 추정치를 평균화하는 앙상블 방법이며, 선택적으로 무작위 특징 하위 샘플링을 포함할 수 있습니다.

4. 이론적 보장

이 논문은 추정기의 $L^1(\nu)$-일관성에 대한 충분 조건을 확립합니다. 파티션 시퀀스가 다음을 만족하면 일관성이 보장됩니다:

1. 셀의 수가 $N$에 대해 선형 미만으로 증가합니다.
2. 파티션 가족의 성장 함수가 특정 VC 차원 경계를 만족합니다.
3. 셀의 지름이 0 으로 수렴합니다.
4. 서로 다른 공변량 투영의 수가 $\sqrt{\log N / N}$에 비해 충분히 느리게 증가합니다.

주요 기여

1. 통합 프레임워크: 모수적 가정 없이 연속, 범주형, 혼합 유형 결과를 처리하는 조건부 밀도 추정을 위한 단일 비모수 프레임워크.
2. 직접 최적화: 이전 연구에서 발견된 분할 - 히스토그램 결합 최적화의 계산 병목 현상을 피하면서 탐욕적 최선 우선 검색을 통해 조건부 로그 손실을 직접 최적화하는 트리 구성 알고리즘.
3. 확장성: 표준 CART 와 유사한 계산 복잡도를 가진 구현으로 대규모 데이터셋에 실용적입니다.
4. 앙상블 확장: 단일 트리보다 향상된 확률적 예측을 보여주는 파티션 포레스트의 도입.
5. 이론적 분석: 표준 복잡성 및 수축 가정 하에 제안된 추정기에 대한 엄격한 일관성 증명.

실험 결과

저자들은 CART, 랜덤 포레스트, CADET, CDTree 와 비교하여 다양한 분류 및 회귀 벤치마크에서 파티션 트리와 파티션 포레스트를 평가했습니다.

• 분류:
  • 단일 트리: 로그 손실 측면에서 파티션 트리가 대부분의 데이터셋 (9 개 중 8 개) 에서 CART 를 능가했습니다.
  • 앙상블: 파티션 포레스트는 대부분의 데이터셋에서 랜덤 포레스트보다 낮은 로그 손실을 달성하여 우수한 확률적 보정을 보여주었습니다.
• 회귀:
  • 단일 트리: 파티션 트리는 경쟁력 있는 점 예측과 강력한 확률적 성능을 제공했습니다. 특히, 더 큰 데이터셋 (예: Air, Power, California, Protein) 에서 모수적 CADET 보다 우수한 성능을 보여 확장성과 표본 크기에 대한 적응성이 더 좋음을 시사했습니다.
  • 앙상블: 파티션 포레스트는 로그 손실 측면에서 대부분의 회귀 벤치마크 (10 개 중 8 개) 에서 랜덤 포레스트를 일관되게 능가했습니다.
• 강건성:
  • 노이즈: 이 방법은 동분산 및 이분산 노이즈 모두에 강건하여 성능 저하가 CDTree 와 비슷하고 CADET 보다 더 안정적인 것으로 나타났습니다.
  • 중복 특징: CDTree 가 상관된 특징 중복에 대해 약간 더 나은 안정성을 보인 반면, 파티션 트리는 특징 손상 하에서 CADET 에 비해 더 일관된 예측 (낮은 분산) 을 산출했습니다.
• 효율성: Physicochemical Protein 데이터셋에 대한 런타임 비교에서 파티션 트리는 $N=10,000$일 때 CADET 보다 약 5 배, CDTree 보다 25 배 빠른 것으로 나타났습니다.

중요성 및 주장

이 논문은 파티션 트리가 기존 확률적 트리 방법에 대한 확장 가능한 비모수적 대안을 제공한다고 주장합니다. 그 주요 중요성은 다음과 같습니다:

• 유연성: 특정 모수적 형태 (예: 가우시안) 를 가정하지 않고 일반 결과 공간에 대한 복잡한 조건부 분포를 모델링할 수 있는 능력.
• 해석 가능성: 이득 기반 특징 중요도 및 조각별 상수 밀도 시각화를 통해 의사결정나무의 고유한 해석 가능성을 유지하면서 완전한 확률적 출력을 제공합니다.
• 성능: 데이터셋 크기가 증가함에 따라 특히 전통적인 점 예측 앙상블 (랜덤 포레스트) 과 모수적 밀도 기반 트리 (CADET) 모두를 능가할 수 있는 비모수적, 밀도 기반 트리 앙상블을 경험적으로 입증합니다.

저자들은 파티션 트리를 유연한 조건부 밀도 추정이 필요한 인과 추론 파이프라인 및 기타 응용 프로그램에 통합하기 위한 자연스러운 후보로 위치시키며, 향후 작업은 부스팅 프레임워크와 맞춤형 가지치기 전략을 탐구할 수 있음을 인정합니다.