의사결정 트리 가지치기는 Machine learning에서 사용되는 기법으로, 예측력이 거의 없는 트리 부분을 제거하여 의사결정 트리의 크기를 줄이는 방법이다. 주요 목표는 복잡성을 줄이고 과적합을 완화함으로써 보이지 않는 데이터에 대한 모델의 일반화 성능을 개선하는 동시에 해석 가능성을 높이고 훈련 및 추론 시간을 단축하는 데 있다.
가지치기는 완전히 성장한 의사결정 트리가 훈련 데이터에 지나치게 밀착하여 노이즈와 이상치를 포착하는 경우가 많기 때문에 필수적이다. 이로 인해 새로운 데이터에 대한 성능이 저하된다. 트리를 단순화함으로써 가지치기는 훈련 오차의 작은 증가와 검증 오차의 더 큰 감소를 맞바꾸어 더 견고한 모델을 만든다.
가지치기 유형
가지치기 방법은 크게 사전 가지치기(forward pruning이라고도 함)와 사후 가지치기(backward pruning)의 두 범주로 나뉜다.
사전 가지치기는 트리 구성 중 특정 기준이 충족되면 성장을 중단한다. 일반적인 기준에는 최대 깊이, 잎당 최소 샘플 수, 최소 정보 이득 임계값, 또는 분할에 대한 통계적 유의성 검정이 포함된다. 사전 가지치기는 간단하고 효율적이지만, 성장을 너무 일찍 중단하여 중요한 상호작용을 놓칠 수 있다. 이는 초기 의사결정 트리 문헌에서 다루어졌으며, 1960년대 Bernard Widrow의 적응 시스템 연구에서 언급되었지만, 공식적인 개념은 이후 알고리즘과 더 관련이 있다.
사후 가지치기는 먼저 전체 트리를 만든 후 가지를 제거한다. 이 접근은 트리 구조 전체를 고려하기 때문에 일반적으로 더 효과적이다. 기법에는 비용-복잡도 가지치기(최소 비용-복잡도 가지치기로도 알려짐)와 오류 기반 가지치기가 있다. 사후 가지치기는 종종 별도의 검증 세트나 교차 검증을 사용하여 제거할 가지를 결정한다.
가장 잘 알려진 사후 가지치기 알고리즘은 1984년 Breiman 등의 CART 저서에서 소개된 비용-복잡도 가지치기이다. 이는 오류율과 잎 수 모두에 기반하여 각 하위 트리에 비용을 할당한 다음, 그 절충을 최소화하는 하위 트리를 선택한다. 이는 트리 크기를 패널티로 하는 하이퍼파라미터 알파를 사용하여 달성된다.
주요 참고 자료는 Christopher Bishop의 1995년 저서 "Neural Networks for Pattern Recognition"으로, 신경망 맥락에서 가지치기를 논의하지만, 동일한 원리가 의사결정 트리에 적용된다. 의사결정 트리 문헌에서 J. Ross Quinlan은 C4.5 알고리즘(1993)을 위한 오류 기반 가지치기를 개발했으며, Quinlan은 이전 연구에서 축소 오류 가지치기도 소개했다.
알고리즘 및 구현
실제로 ID3, C4.5, CART 및 후속 명 C5.0와 같은 알고리즘은 다양한 가지치기 방법을 통합한다. 비용-복잡도 가지치기의 표준 구현은 다음과 같다:
- 전체 트리를 성장시킨다.
- 각 노드의 alpha 값을 계산한다.
- 가장 작은 alpha를 가진 노드를 순차적으로 가지치 제거한다.
- 비용-복잡도 점수를 최소화하는 하위 트리를 선택한다.
Python 라이브러리인 scikit-learn에서 비용-복잡도 가지치는 ccp_alpha 매개변수로 구현된다. 또한 XGBoost와 LightGBM 같은 라이브러리는 자체 휴리스틱으로 사후 가지치기를 사용하며, 많은 최신 라이브러리는 사전 가지치기(max_depth와 같은 매개변수로)와 사후 가지치기를 지원한다. Carnegie Mellon University의 오픈 소스 프로젝트와 SambaNova의 ML 환경에서는 가지치기가 분산 훈련 파이프라인에 통합되는 경우가 많다.
가지치 대비 기타 기법
의사결정 트리 가지치기는 모델 가지치기와 개념적으로 관련되며, 이는 인공지능에서 상징적 모델의 크기를 줄이기 위한 더 넓은 용어이다. 딥 모델에서의 매개변수 가지치기(가중치 제거)와 달리, 트리 가지치기는 전체 가지 또는 하위 트리를 제거한다. 또한 Dropout과 정규화는 대안이지만 트리에 직접 적용되지 않으며, 동일한 목적을 제공한다.
대부분의 실무자들은 일반화를 더 개선하기 위해 Data Augmentation과 같은 다른 기술과 가지치기를 결합한다. Neural network 맥락에서 가지치기가 추론 계산 비용을 주로 줄이는 반면, 트리 가부치는 주로 일반화와 해석 가능성을 개선한다.
적용 및 영향
의사결정 트리 가지치의 실질적 영향은 의료 진단, 신용 점수, 가짜 탐지과 같은 모델 해석이 중요한 도메인에서 크다. 예를 들어, 의료 전문가는 블랙박스에 노출되지 않은 환자에게 결정을 정당화하기 위해 투명한 모델이 필요하다. 불필요한 가지를 제거함으로써 임상의는 가장 핵심적인 규칙에 집중할 수 있다. 금융 분야에서 규제 기관은 종종 결정 설명이 검증 가능하고 해석 가능할 것을 요구한다.
성능 측면에서, 가부치는 결과 트리가 더 작고 실행하기 간단하기 때문에 추론 속도를 높인다. 이는 Amazon Web Services에 배포된 실시간 시스템이나 Samsung Electronics 같은 엣지 장치에서 지연 시간이 중요한 경우 특히 관련이 있다. 또한 Generative AI와 같은 대형 모델 분야에서는, 가지치기가 트리 기반 방법에서만큼 자주 사용되지 않지만, 모델 단순화에 대한 지식과 아이디어에 기여한다.
도전 및 모범 사례
평가의 핵심 과제는 좋은 가지치기 기준을 선택하는 것이다. 지나치게 공격적인 가지치기는 과소적합을 일으킬 수 있고, 부족한 가지치기는 여전히 과접합을 남긴다. 가지치기 수준 조정을 위해 별도 검증 세트를 사용하는 기법은 표준이며, 알파 선택은 교차 검증을 통해 수행된다. 최적상의 트리를 구축한 후 사후 가지치기를 효과적으로 사용하고, 계산 예산을 중요시할 때 사전 가치를 사용하는 것이 좋다.
또 다른 핵제는 많은 수준을 가진 범주형 변수를 처리하는 것이다: 가부치는 드물지만 중요한 그룹을 포함하는 가지를 제거할 수 있다. 실제로 가지치기는 의료나 금융 도메인에서 오류를 줄이지 않더라도 임상적 중요성 때문에 드문 가지를 유지해야 하는 경우와 균형을 맞춰야 한다.
프로젝트 개발에서, 가부치의 요약 단계로서 모델 검증 후, 편향되지 않은 테스트 세트를 사용하여 수행하는 것이 권장된다. 많은 소프트웨어 라이브러리는 사전 및 사후 가지치기 방법을 포함한 기본 매개변수를 가지며, 이들의 상호작용을 이해하는 것은 사소하지 않고 경험적 테스트가 필요하다.
2020년대 기준으로 의사 트리 가부치는 여전히 표준 실인이며, Google Cloud와 Oracle Cloud Infrastructure뿐만 아니라 오픈 소스 배포판에서도 많은 거대 기술 공급자의 도구에 포함된다. 다른 기법들이 등장했지만, 트리 표현을 단순화하여 노이즈 객체를 제거하는 것만큼 모델을 단순하고 효과적으로 만드는 방법은 없다.