Anytime-Valid Inference를 통한 온라인 결정 트리(Online Decision Trees)의 분할 선택(Split

배깅(Bagging) 기반 앙상블, 특히 Adaptive Random Forests는 데이터 스트림(Data Streams)으로부터 학습하는 데 있어 가장 강력한 성능을 보이는 방법들 중 하나입니다. 이러한 방법들의 공통점은 Hoeffding Trees를 기본 학습기(Base Learners)로 사용한다는 점인데, 이들은 집중 부등식(Concentration Inequalities)을 사용하여 후보 분할(Candidate Split)이 대안보다 유의미하게 더 나은지를 테스트함으로써 결정 트리(Decision Trees)를 점진적으로 성장시킵니다. 이러한 경험적 성공에도 불구하고, 기존 변형 모델들은 유효한 통계적 보장(Statistical Guarantees)이 부족합니다. 현재의 분석은 고정된 표본 농축 경계(Fixed-sample Concentration Bounds)에 의존하는 반면, 분할 결정은 데이터 의존적 정지 규칙(Data-dependent Stopping Rules)을 사용하여 이루어지는데, 이는 보장의 유효성을 상실시키고 잘못된 분할이 발생할 확률을 1로 몰아넣을 수 있습니다. 우리는 Anytime-Valid Inference(언제든 유효한 추론)에 기반한 원칙적인 대안을 소개합니다. 우리의 방법은 다음과 같은 특징을 제공합니다: (i) 비정상성(Non-stationary) 설정을 포함한 임의의 데이터 스트림 하에서 잘못된 분할(False Splits)에 대한 anytime-valid 제어; (ii) 예측 이점(Predictive Advantage)이 있을 때 유한한 확정 시간(Finite Commitment Time); (iii) 정상적인 i.i.d. 데이터 하에서 리스크(Risk)는 단조 감소하며 매 분할마다 엄격하게 개선됨. 경험적으로, 우리는 비정상성 스트림에서 단독 트리와 Adaptive Random Forests 내에서의 사용을 모두 평가합니다. 우리의 방법은 성능을 향상시키는 동시에 실질적으로 더 작은 트리를 생성합니다.