전역 수렴성을 보장하는 그래디언트 정규화 뉴턴 부스팅 트리
요약
본 논문은 그래디언트 부스팅 의사결정 트리(GBDT)의 전역 수렴성 문제를 해결하기 위해 '그래디언트 정규화 뉴턴 하강'이라는 새로운 프레임워크를 제안합니다. 이 방법은 코사인 각도와 약한 그래디언트 에지 개념을 도입하여 제한된 뉴턴 하강을 수행하며, 특히 적응형 $\ell_2$-정규화 항을 통해 고전 알고리즘의 안정성을 유지하면서 전역 수렴 속도를 보장합니다. 그 결과, Nesterov 모멘텀 기반 1차 부스팅과 유사한 $O(1/k^2)$의 빠른 수렴 속도를 가지는 2차 GBDT 알고리즘을 개발했습니다.
핵심 포인트
- 전통적인 뉴턴 부스팅은 전역 수렴성 증명에 어려움이 있었으나, 본 논문은 이를 해결하는 새로운 프레임워크를 제시함.
- 제안된 '그래디언트 정규화 뉴턴 하강' 스키마는 적응형 $\ell_2$-정규화 항을 도입하여 알고리즘의 안정성을 높이고 수렴을 보장함.
- 이 방법은 2차 GBDT 알고리즘에 대해 $O(1/k^2)$라는 높은 전역 수렴 속도를 확립했으며, 이는 최신 1차 부스팅 기법과 유사한 성능임.
- 수치 실험 결과, 원본 뉴턴 부스팅에서 발생할 수 있는 발산 문제를 해결하고 안정적인 수렴을 입증함.
그래디언트 부스팅 의사결정 트리 (GBDTs) 는 표본 기반 머신러닝에서 우세한 위치를 차지하며, XGBoost, LightGBM, CatBoost 와 같은 최신 구현들은 뉴턴 부스팅을 기반으로 합니다. 뉴턴 부스팅은 의사결정 트리의 공간에서 2 차 하강 단계입니다. 실증적 성공에도 불구하고, 1 차 부스팅에 비해 뉴턴 부스팅의 전역 수렴성은 잘 이해되지 않았습니다. 본 논문에서는 Hilbert 공간에서 불완전한 반복을 가진 뉴턴 방법을 기반으로 코사인 각도와 약한 그래디언트 에지 개념을 도입하여 제한된 뉴턴 하강 (Restricted Newton Descent) 을 소개합니다. 이 프레임워크 내에서 GBDT 와 고전적 유한 차원 이론을 포함한 뉴턴 부스팅을 특수한 경우로 복원합니다. 먼저, Hessian 우도 조건을 만족하는 매끄럽고 강하게 볼록한 손실에 대해 원본 뉴턴 부스팅이 선형 수렴 속도를 달성함을 증명합니다. Lipschitzian Hessian 을 가진 일반적인 볼록 손실을 처리하기 위해 최근 그래디언트 정규화 뉴턴 스키마를 제한된 약 학습자 설정으로 확장했습니다. 이 스키마는 각 반복에서 그래디언트 노름의 제곱근에 비례하는 적응형 ℓ2-정규화 항을 도입하여 고전 알고리즘을 최소한으로 수정합니다. 우리는 이 스키마에 대해 O(1/k^2) 속도를 확립함으로써, Nesterov 모멘텀을 가진 1 차 부스팅과 일치하는 속도를 가지는 전역 수렴 2 차 GBDT 알고리즘을 얻었습니다. 수치 실험에서, 원본 뉴턴 부스팅이 발산할 수 있음에도 불구하고 우리의 스키마가 수렴함을 보여줍니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.LG의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기