혼합 정수 프로그래밍(MIP)은 최적의 의사 결정 트리를 학습하기 위한 강력한 프레임워크로 부상했습니다. 그러나 회귀 작업에 대한 기존 MIP 접근 방식은 순수하게 이진 특징으로 제한되거나, 연속적이고 대규모 데이터가 포함될 때 계산적으로 다루기 어려워집니다. 연속형 특징을 무심코 이진화하면 전역적 최적성을 잃고 불필요하게 깊은 트리가 생성되는 경우가 많습니다. 본 논문에서는 최적의 회귀 트리 훈련을 2단계 최적화 문제로 재구성하고, 트리 구조 변수만을 기반으로 분기하는 특화된 분기 및 바운드(BB) 알고리즘인 Reduced-Space Optimal Regression Trees (RS-ORT)를 제안합니다. 이 설계를 통해 알고리즘의 수렴과 훈련 샘플 수에 대한 독립성이 보장됩니다. 모델의 구조를 활용하여 훈련 속도를 높이기 위해 여러 바운드 강화 기술(닫힌 형식의 리프 예측, 경험적 임계값 이산화, 정확한 깊이-1 서브트리 구문 분석)을 도입했으며, 분해 가능한 상한 및 하한 바운딩 전략과 결합했습니다. BB 노드별 분해는 간단한 병렬 실행을 가능하게 하여, 수백만 개의 데이터 세트에서도 계산적 난해함을 완화합니다. 이진 및 연속형 특징을 모두 포함하는 여러 회귀 벤치마크에 대한 실험 연구를 기반으로, RS-ORT는 최첨단 방법보다 우수한 훈련 및 테스트 성능을 제공합니다. 특히, 연속형 특징을 가진 최대 2,000,000개의 샘플 데이터 세트에서 RS-ORT는 더 간단한 트리 구조와 더 나은 일반화 능력을 갖춘 훈련 성능을 4시간 안에 보장받을 수 있습니다.
