기술 요약: WOODELF++

문제 제기

의사결정나무 앙상블은 실제 세계 응용 분야에서 널리 사용되지만, 그 예측을 해석하는 것은 신뢰와 의사결정을 위해 여전히 중요한 과제로 남아 있습니다. 이러한 모델을 해석하는 세 가지 주요 도구는 부분 의존성 플롯 (PDP), 결합 부분 의존성 플롯 (Joint-PDP), 그리고 부분 의존성 상호작용 값 (PDIV) 입니다.

• PDP는 단일 특성이 평균 모델 예측에 미치는 영향을 시각화합니다.
• Joint-PDP는 이를 특성 쌍으로 확장하여 결합된 효과를 드러냅니다.
• PDIV(특히 "Any-Order" 작업) 는 데이터셋의 모든 행에 대해 가능한 모든 특성 부분집합에 대한 상호작용 효과를 정량화합니다.

scikit-learn의 방법론이나 GLEX 패키지에 구현된 FastPD 알고리즘과 같은 현재 최첨단 방법들은 금지할 정도로 높은 계산 복잡성을 겪습니다. 단순한 접근법은 샘플 수와 특성 수에 따라 선형적으로 확장되지만, 트리 깊이와 상호작용에 관여하는 특성 수에 따라 지수적으로 확장됩니다. 대규모 데이터셋 (예: 400,000 행) 과 복잡한 상호작용 작업 (Any-Order-PDIV) 의 경우, 기존 방법들은 실용적으로 너무 느려 (수일 또는 수년 소요) 사용이 불가능하거나, 날카로운 불연속성과 같은 중요한 모델 동작을 놓칠 수 있는 근사법에 의존합니다.

방법론

저자들은 의사결정나무 앙상블에 대한 PDP, Joint-PDP, 그리고 Any-Order-PDIV 계산 을 위한 통합적이고 효율적인 프레임워크인 **WOODELF++**를 소개합니다. 이 접근법은 저자들의 이전 작업인 WOODELF에 기반을 두고 있으며, WOODELF는 의사결정나무 앙상블을 **가중치 논리합 정규형 (WDNF)**으로 표현된 의사 부울 (Pseudo-Boolean, PB) 함수로 모델링하여 SHAP 값을 효율적으로 계산합니다.

핵심 기술적 혁신은 다음과 같습니다:

1. WDNF 및 선형성을 통한 통합:
   저자들은 PDP, Joint-PDP, PDIV 작업을 WDNF 공식에 대한 협력 게임 지표로 공식화합니다. 이러한 지표의 선형성 속성을 활용하여, WDNF 표현 내의 개별 "큐브"(리터럴의 논리곱) 들로부터 결과를 집계함으로써 복잡한 전역 설명을 계산할 수 있습니다. 이는 각 샘플 - 특성 조합마다 모델을 다시 평가할 필요성을 제거합니다.

2. 효율적인 소비자 데이터셋 구성:
   PDP 와 Joint-PDP 를 효율적으로 계산하기 위해, 저자들은 지역 속성 알고리즘이 전역 의존성 플롯을 계산할 수 있게 하는 컴팩트한 "소비자 데이터셋"($C$) 을 구성합니다.

   • PDP의 경우, 샘플링된 특성 값을 나타내는 $k$개의 행을 가진 데이터셋을 구성합니다.
   • Joint-PDP의 경우, 특성 인덱스를 이진수로 인코딩하고 np.tile 및 np.repeat 연산을 사용하여 모든 쌍별 값 조합이 중복된 행 없이 표현되도록 하는 새로운 구성 방식을 도입하여 데이터셋 크기를 $O(k^2 f)$에서 $O(k^2 \log f)$로 줄입니다.

3. Full PDP:
   샘플링된 값 ($k$) 을 사용하는 표준 PDP 는 좁은 스파이크나 단일 값 효과 (예: 특정 기본 급여를 경고하는 사기 모델) 를 놓칠 수 있음을 인식하여, 저자들은 Full PDP를 제안합니다. 임의의 샘플링 대신 Full PDP 는 트리 노드의 모든 분할 임계값을 x 축 값으로 사용합니다. 의사결정나무 예측은 임계값 사이에서 구간별 상수이므로, 이 방법은 최소한의 평가 점수로 앙상블의 정확한 동작을 포착합니다.

4. Any-Order-PDIV 를 위한 복잡도 감소:
   가장 중요한 이론적 기여는 Any-Order-PDIV 에 대한 복잡도 감소입니다.

   • Naive/FastPD: FastPD 는 트리를 독립적으로 처리하여 최악의 경우 $2^{2D}$ (여기서 $D$는 트리 깊이) 의 복잡도 의존성을 가집니다.
   • WOODELF++: 각 루트에서 리프까지의 경로를 별도로 처리하고 WDNF 상의 PDIV 지표의 특정 구조를 활용함으로써, 복잡도 의존성을 $4^D$로 줄입니다. 이는 최첨단 기술 대비 지수적인 개선을 의미합니다.

5. 근사 및 GPU 지원:
   이 프레임워크는 자연스럽게 경로 의존적 (Path-Dependent) 근사 (배경 데이터셋을 빈 것으로 설정하는 것과 동일) 를 지원하며, GPU 가속을 지원하는 순수 Python 으로 구현되었습니다.

주요 기여

1. PDP 및 Joint-PDP 의 속도 향상: WOODELF++ 는 대규모 데이터셋에서 PDP 및 Joint-PDP 작업에 대해 FastPD 대비 약 6 배의 속도 향상을 달성하며, scikit-learn 대비 최대 **5 자릿수 (five orders of magnitude)**의 속도 향상을 보입니다.
2. Any-Order-PDIV 를 위한 지수적 복잡도 개선: 저자들은 균형 잡힌 트리의 경우 복잡도가 입력 크기에 대한 지수함수 (FastPD 의 $2^{2D}$) 에서 입력 크기에 대한 다항식 (WOODELF++ 의 $4^D$) 으로 전환됨을 입증합니다. 경험적으로 이는 400,000 개의 샘플에 대한 Any-Order-PDIV 실행 시간을 FastPD 의 추정 1,000,000 년에서 WOODELF++ 의 5 분으로 단축시킵니다.
3. Full PDP 의 도입: 샘플링된 PDP 가 놓치는 과적합 및 단조성 위반을 감지할 수 있게 하는 트리 앙상블의 완전한 구간별 상수 구조를 포착하는 새로운 방법입니다.
4. 통합 프레임워크: 이 논문은 근사 PDP, 정확한 PDP, 그리고 경로 의존적 SHAP 간의 간단한 연결을 확립하여 이를 단일 알고리즘 프레임워크 하에 통합합니다.

실험 결과

저자들은 두 개의 대규모 널리 사용되는 데이터셋인 IEEE-CIS(472k 행, 397 특성) 와 KDD Cup 1999(4.9M 행, 127 특성) 에서 WOODELF++ 를 평가했습니다. 모델은 100 개의 트리와 최대 깊이 6 을 가진 HistGradientBoostingRegressor를 사용하여 훈련되었습니다.

• PDP 성능: IEEE-CIS 에서 WOODELF++ 는 GPU 를 사용하여 13.1 초에 정확한 PDP(k=5) 를 계산한 반면, FastPD 는 99 초, scikit-learn 은 58.5 분이 소요되었습니다.
• Joint-PDP 성능: Joint-PDP(k=5) 의 경우 WOODELF++ 는 25 초(GPU) 가 소요된 반면, FastPD 는 130 초, scikit-learn 은 추정 35 일이 소요되었습니다.
• Any-Order-PDIV: 10,000 개의 샘플을 가진 IEEE-CIS 에서 WOODELF++ 는 22.6 초(GPU) 에 작업을 완료했습니다. FastPD 는 60,000 년이 소요될 것으로 추정되었습니다.
• 정확성: 저자들은 WOODELF++ 의 출력이 scikit-learn 및 직접적인 PDIV 계산과 최대 0.00001의 차이로 일치함을 검증했습니다.

의의

이 논문은 WOODELF++ 가 의사결정나무 앙상블 해석의 실현 가능성을 근본적으로 변화시킨다고 주장합니다. Any-Order-PDIV 의 복잡도를 처리 불가능한 수준에서 실용적인 수준으로 낮춤으로써, 이전에는 계산적으로 불가능했던 고차원 특성 상호작용 분석을 가능하게 합니다. 또한, Full PDP 의 도입은 실무자들이 샘플링된 근사법의 한계를 넘어 트리 모델의 정확한 결정 경계를 시각화할 수 있게 합니다. 저자들은 WOODELF++ 를 의료, 금융, 생태학 등 깊은 모델 이해가 필요한 분야에서 확장 가능하고 신뢰할 수 있는 AI 를 위한 필수 도구로 위치시킵니다.