Approximation-Free Differentiable Oblique Decision Trees

기술적 요약: 근사 없는 미분 가능 사선 결정 트리

문제 제기
결정 트리 (DT) 는 해석 가능성과 표형 데이터 (tabular data) 에 대한 효과성으로 인해 의료 진단과 같은 안전-중요 분야에서 매우 높이 평가받습니다. 그러나 정확한 사선 결정 트리 (특징의 선형 결합으로 분할이 이루어지고 축 정렬되지 않은 트리) 를 학습하는 것은 검색 공간의 NP-난해성으로 인해 계산적으로 어렵습니다. 최근의 미분 가능 접근법은 경사 기반 학습을 가능하게 하지만, 학습 과정의 무결성을 훼손하는 근사법에 의존합니다:

1. 소프트 DT: 확률적 "소프트" 경계 (예: 시그모이드 활성화) 를 사용하여 트리를 미분 가능하게 만들지만, 이를 "하드" 결정으로 변환하면 종종 정확도가 저하됩니다.
2. 스트레이트-쓰루 추정기 (STE): DGT 및 ICCT 와 같은 방법에서 미분 불가능한 하드 결정을 통한 경사를 근사하는 데 사용됩니다. 이는 전진 통과 (평가) 와 역전파 (최적화) 간의 의미적 불일치를 초래합니다. 회귀 작업에서 이러한 불일치는 편향된 경사 업데이트, 구조적 불안정성, 그리고 내부 파라미터가 모든 회귀기에 기반하여 업데이트되지만 실제로는 하나만 선택되기 때문에 리프 노드의 미활용으로 이어집니다.

방법론: DTSemNet
저자들은 하드 사선 결정 트리와 의미적으로 동등하고 가역적인 표현을 제공하는 새로운 신경망 아키텍처인 DTSemNet을 제안합니다. 기존 연구와 달리 DTSemNet 은 근사 없이 표준 경사 하강법을 사용하여 엔드 - 투 - 엔드 학습을 가능하게 합니다.

• 아키텍처: DTSemNet 은 $m$개의 내부 노드와 $n$개의 리프를 가진 DT 를 ReLU 활성화와 선형 연산을 사용하여 신경망으로 인코딩합니다.
  • 내부 노드: $\langle A_i, x \rangle + b_i$를 계산하는 선형 레이어로 표현됩니다.
  • 분기: 양수 ($\top$) 와 음수 ($\bot$) 결과를 분리하기 위해 ReLU 활성화를 사용하며, 임의의 입력에 대해 정확히 하나의 분기만 활성화되도록 보장합니다 (측도 0 인 경계 제외).
  • 리프: 고정 가중치 선형 레이어가 활성화된 분기들을 집계하여 각 리프에 대한 로짓을 생성합니다.
• 의미적 동등성: 정리 1 은 임의의 입력 $x$에 대해 하드 DT 가 선택한 리프가 DTSemNet 네트워크에서 최대 출력 로짓을 가진 리프와 동일함을 증명합니다. 따라서 평가 함수 (전진 통과) 와 최적화 함수 (역전파) 는 의미적으로 동일합니다.

회귀 전략: 어닐링 Top-k
분류는 argmax 를 통해 이 공식과 자연스럽게 일치하지만, 회귀는 라우팅 (내부 노드) 과 리프 회귀기를 공동으로 최적화해야 합니다. 저자들은 단일 STE 를 사용하는 것 (이전의 컨퍼런스 연구에서와 같이) 이 내부 노드를 모든 회귀기에 기반하여 업데이트하지만 매 단계마다 하나의 회귀기만 업데이트하기 때문에 불안정성을 초래한다고 지적합니다.

이를 해결하기 위해 논문은 어닐링 Top-k 방법을 도입합니다:

1. 메커니즘: 학습 중 하드 Top-1 선택 대신, 모델은 초기에 온도 스케일된 Softmax 와 결합된 Top-$k$ 선택기 ($k \ge 2$) 를 사용합니다. 이를 통해 모델은 여러 전문가 (리프) 로 입력을 동시에 라우팅하여 정보적인 경사를 제공합니다.
2. 어닐링: $k$값은 학습 에포크를 거치며 $k \ge 2$에서 $k=1$로 점진적으로 감소합니다.
3. 장점:
   • 경사 일관성: STE 와 달리 전진 통과와 역전파는 모든 단계 $k$에서 동일한 의미를 공유합니다.
   • 균형 잡힌 업데이트: 내부 노드 파라미터는 선택된 Top-$k$ 회귀기만을 기반으로 업데이트되어, 멀리 떨어진 선택되지 않은 리프들의 불안정화 영향을 방지합니다.
   • 탐색: 단일 샘플에 대해 여러 회귀기가 업데이트되므로, 학습 후반에 라우팅 결정이 변경되더라도 모델이 적응할 수 있습니다.
4. 파인튜닝: $k=1$에 도달하면 내부 노드는 고정되고, 과적합을 방지하기 위해 증강된 샘플을 사용하여 리프 회귀기를 파인튜닝합니다.

주요 기여

1. DTSemNet 아키텍처: 하드 트리와 의미적으로 동등한 사선 DT 의 미분 가능 인코딩으로, 분류 작업에서 근사 없이 정확한 경사 하강 학습을 가능하게 합니다.
2. 회귀를 위한 어닐링 Top-k: STE 기반 방법의 근사와 편향을 제거하여 라우팅과 리프 파라미터의 안정적이고 정확한 공동 최적화를 보장하는 새로운 학습 절차입니다.
3. 프로그래밍 가능 RL 정책: 이산 및 연속 행동 공간 모두에서 표준 신경망 (NN) 을 대체하는 프로그래밍 가능 정책으로서의 DTSemNet 구현을 시연합니다.

실험 결과
저자들은 분류, 회귀, RL 벤치마크에서 DTSemNet 을 TAO, DGT, CRO-DT, CART, ICCT, VIPER 와 같은 최신 방법들과 비교 평가했습니다.

• 분류: DTSemNet 은 간결하고 밀집된 트리를 포함한 모든 테스트 데이터셋에서 최고의 성능을 달성했습니다. 비경사 방법 (TAO, CRO-DT 등) 과 경사 기반 근사법 (DGT) 을 크게 능가하여 Optical Recognition 과 같은 까다로운 벤치마크에서 분류 오류를 최대 10% 감소시켰습니다. 학습 시간은 DGT 와 유사하지만 전역 검색 방법보다 훨씬 빨랐습니다.
• 회귀: Top-k 를 적용한 DTSemNet 은 거의 모든 데이터셋에서 모든 경쟁자를 능가했습니다. TAO-Linear 대비 평균 RMSE 를 3% 개선했으며, STE 를 사용한 DTSemNet-STE 보다 현저히 우수한 성능을 보였습니다. 제거 실험 (ablation studies) 은 STE 가 리프를 미활용하는 경향이 있는 반면, Top-k 가 더 균형 잡힌 리프 활용과 안정적인 가중치 진화를 이끈다는 것을 확인했습니다.
• 강화 학습:
  • 이산 행동: LunarLander 및 Zerglings 환경에서 DTSemNet 은 NN 성능과 일치하거나 초과했으며, 다른 DT 기반 정책 (DGT, ICCT, VIPER) 을 크게 능가했습니다.
  • 연속 행동: SAC 와 함께 Top-k 어닐링 전략을 사용하여 DTSemNet 은 Continuous LunarLander 및 BipedalWalker 에서 NN 베이스라인과 STE 기반 DT 를 능가했습니다. 이는 근사 없는 학습이 연속 제어에서도 우수한 정책을 산출함을 입증했습니다.

의의 및 주장
이 논문은 DTSemNet 이 분류 및 회귀 설정 모두에서 사선 DT 에 대한 근사 없는 학습을 달성한 최초의 아키텍처라고 주장합니다. 평가와 최적화 간의 의미적 불일치를 제거함으로써 STE 기반 접근법의 불안정성과 편향을 극복합니다. 저자들은 이것이 DT 의 해석 가능성과 경사 기반 학습의 확장성 사이의 격차를 해소하여, 안전-중요 응용 및 복잡한 RL 환경에서 고성능 해석 가능 모델을 실현 가능하게 만든다고 주장합니다.

한계 및 향후 작업
저자들은 DT 인 DTSemNet 은 복잡한 형태를 처리하는 데 어려움을 겪는 이미지와 같은 고차원 입력에는 적합하지 않음을 인정합니다. 향후 작업은 고정된 트리 높이를 하이퍼파라미터로 삼는 것을 벗어나 적응형 트리 성장 및 가지치기를 위한 미분 가능 방법 개발에 초점을 맞출 것입니다.