적응형 특징 및 샘플 축소 기법을 이용한 최적 분류 트리 확장
Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction
arXiv최적 분류 트리를 찾는 동적 계획법은 특징(feature)과 샘플 수가 늘어날수록 계산 비용이 기하급수적으로 증가하는 문제가 있었습니다.
- 연구진은 특징 공간과 샘플 공간을 결합 축소한 Weighted STreeD와 Adaptive STreeD를 개발하여, 기존 방식 대비 최대 120배 이상의 속도 향상을 달성했습니다.
- 이는 계산 시간이나 메모리 제약으로 어려웠던 대규모 데이터셋에 최적 분류 트리를 적용할 수 있는 가능성을 크게 확장시킵니다.
- 다만, 전체 특징 공간 탐색 과정은 아직 완전한 최적화가 아닌 경험적 방식(heuristic)으로 진행되며, 성능은 주어진 계산 예산 내에서 검증되었습니다.
최적 분류 트리를 위한 동적 계획법은 특징(feature)과 훈련 샘플 수가 증가함에 따라 계산 비용이 매우 높아지는 문제가 있습니다. 연구진은 이러한 문제를 해결하기 위해 Weighted STreeD라는 결합된 특징 및 샘플 공간 축소 프레임워크를 개발했습니다. 이 방식은 고정 후보 집합으로 투영한 후 생성되는 중복 기록들을 대표값으로 병합하여, 고정 후보 최적화 문제 자체는 변경하지 않으면서도 샘플 의존적인 계산을 줄일 수 있습니다.
Adaptive STreeD는 경계가 지정된 후보 집합을 반복적으로 정제하며 작동합니다. 이 과정에서 현재 트리가 사용한 특징들을 유지하고, 가중치 표현을 재구축한 후, 결과로 얻은 축소 문제를 해결합니다. 각 인증된 Weighted STreeD 솔루션은 현재의 후보 집합에 대해 최적이지만, 전체 특징 공간 탐색 과정 자체는 여전히 경험적 방식(heuristic)으로 진행됩니다.
다섯 가지 데이터셋에서 수행된 실험 결과에 따르면, Weighted STreeD는 표준 STreeD 대비 최대 121.41배의 속도 향상을 달성했습니다. 또한 Adaptive STreeD는 동일한 계산 예산 내에서 평가된 최적 분류 트리 기준선과 비교할 때 유사하거나 더 높은 예측 성능을 유지하는 것으로 나타나, 동적 계획법 기반의 최적 트리 학습이 더욱 까다로운 인스턴스로 확장될 수 있음을 보여줍니다.
용어 풀이
- 가중치
- 학습으로 정해진 모델 내부의 숫자 값. 내려받는 모델 파일의 본체예요.