리서치 연구
최적의 일반화된 트리 구조를 위한 새로운 알고리즘 'Literati' 제안
Literati: Towards Anytime Optimal Shape Generalized Trees via AO*
arXiv최적의 구조와 표현력을 갖춘 일반화된 트리(SGT)를 구축하는 최초의 알고리즘 'Literati'가 제안되었습니다.
세 줄 요약
- 이 알고리즘은 트리의 구조와 모양 함수 복잡도를 동시에 최적화하기 위해 새로운 AND/OR 그래프 정식화를 사용합니다.
- 기존 모델들이 가지던 제한적인 표현력을 극복하고 데이터의 복잡한 비선형 패턴을 포착하여 분석 성능 향상에 기여합니다.
- 실제 데이터셋 24개 테스트 결과, Literati는 기존 최고 성능의 트리 방식보다 높은 정확도를 달성하며 우수성을 입증했습니다.
결정 트리는 해석 가능성과 테이블형 데이터에서의 높은 성능으로 주목받지만, 기존의 탐욕적인(greedy) 상향식 유도 알고리즘은 최적이 아니거나 불필요하게 복잡한 구조를 만들 수 있습니다. 표현력을 높이기 위해 일반화된 트리(SGTs)가 도입되었으나, 현재까지 알려진 SGT 유도 알고리즘들은 여전히 탐욕적이며 최적성 보장이 어렵다는 한계가 있었습니다.
본 연구에서 제안하는 Literati는 최초의 최적 SGT 유도 알고리즘입니다. 이 알고리즘은 문제에 대한 새로운 AND/OR 그래프 정식화를 제시하여, 트리 구조와 모양 함수 복잡도를 동시에 최적화합니다. 이를 해결하기 위해 AO*-기반 알고리즘을 개발했으며, OR 노드 선택을 위한 보조 휴리스틱과 AND 노드 탐색을 위한 라운드 로빈 정책 등 두 가지 개선 사항을 적용했습니다.
Literati는 실제 데이터셋 24개에 걸쳐 테스트되었으며, 기존 최고 성능의 트리 방식들보다 높은 학습 및 테스트 정확도를 달성하며 그 우수성을 입증했습니다.