Optimized Sequential Testing for Binary Ensemble Classifiers

문제 정의
랜덤 포레스트와 같은 앙상블 분류기는 다수결 투표를 통해 여러 기본 모델(예: 결정 트리)의 예측을 결합하여 높은 정확도를 달나합니다. 그러나 더 큰 규모의 앙상블은 추론 시 상당한 계산 비용을 발생시키며, 이는 저전력 장치나 고빈도 애플리케이션에서 문제가 됩니다. 본 연구가 다루는 핵심 문제는, 전체 $N$개의 모델을 모두 실행하는 대신, "명확한 다수"가 나타날 때까지 순차적으로 기본 모델의 평가를 중단하는 전략을 통해, 정확도를 크게 저하시키지 않으면서 이진 앙상블 분류기의 테스트 시 계산 비용을 줄이는 방법입니다. 구체적으로, 저자들은 실행된 기본 모델의 수 $i$와 양성 투표의 수 $j$로 상태가 정의되는 $(i, j)$를 기반으로, 전체 앙상블의 결과와 조기 종료된 앙상블의 결과가 달라질 확률인 "불일치율(disagreement rate)"을 엄격하게 제어하면서 기대 실행 모델 수(런타임)를 최소화하는 방법을 조사합니다.

방법론
본 논문은 조기 종료 문제를 순차적 검정(sequential testing) 과제로 정식화하며, 여기서 상태는 실행된 $i$개의 기본 모델과 $j$개의 양성 투표로 정의됩니다. 저자들은 기본 모델이 무작위 순서로 실행된다고 가정하여, 기본 모델 간의 독립성을 가정하지 않고도 임의의 상태에 도달할 확률을 모델링하기 위해 초기하 분포(hypergeometric distribution)를 사용할 수 있도록 합니다.

최적의 조기 종료 전략을 찾기 위해, 저자들은 계산 효율성을 보장하기 위해 선형 계획법(LP)으로 정식화된 세 가지 별도의 최적화 프레임워크를 제안합니다:

1. 미니맥스(Minimax): 최악의 불일치율 제약 조건 하에서 최악의 경우 기대 런타임을 최소화합니다. 이 접근 방식은 양성 투표($n$)의 분포에 대한 사전 지식이 필요하지 않습니다.
2. 미니민(Minimean): 알려져 있거나 추정된 $\hat{D}$ 분포를 바탕으로, 기대 불일치율 제약 조건 하에서 기대 런타임을 최소화합니다.
3. 미니믹스드(Minimixed): 알려진 $n$에 대한 분포를 바탕으로, 최악의 경우 불일치율 제약 조건 하에서 기대 런타임을 최소화합니다.

저자들은 원래의 비선이형 최적화 문제가 조건부 확률 결정 변수($p_{ij}, \pi_{ij}, \bar{\pi}_{ij}$)를 사용하여 재구성될 수 있음을 보여줍니다. 이러한 재구성은 문제를 $O(N^3)$개의 결정 변수를 가진 선형 계획법으로 변환하며, 이는 수백 개의 트리를 가진 앙상블에 대해서도 효율적으로 해결 가능합니다. 결과적인 전략들은 대부분 결정론적이며, 특정 단계 $i$에서 양성 투표가 상한 임계값을 초과하거나 하한 임계값 미만으로 떨어지는 경우에 중단하는 단순한 "엔벨로프(envelope)" 규칙을 따릅니다.

주요 기여

• 이론적 정식화: 본 논문은 다수결 기반 이진 앙상블을 위한 조기 종료에 대한 엄격한 수학적 프레임워크를 제공하며, 중단 전략과 지표(런타임 및 불일치율)를 공식적으로 정의합니다.
• 최적 선형 계획법 솔루션: 저자들은 세 가지 서로 다른 최적성 개념(미니맥스, 미니민, 미니믹스드)에 대한 최적의 조기 종료 전략이 선형 계획법을 통해 구해질 수 있음을 보여줍니다. 이는 휴리스틱에 의존하거나 기본 모델 간의 독립성을 가정했던 기존 연구들과 대조됩니다.
• 독립성 가정 배제: Schwing 등(2011)의 기존 순차적 검정 방식과 달리, 이 접근 방식은 기본 모델이 독립적이라고 가정하지 않으므로, 트리의 예측이 상관관계가 있는 랜덤 포레스트에 직접 적용 가능합니다.
• 사전 계산 가능한 전략: 저자들은 다양한 앙상블 크기와 허용 가능한 불일치율(ADR)에 대해 최적의 전략을 사전 계산하여, 새로운 데이터셋에 대해 매번 재최적화를 수행하지 않고도 즉각적으로 적용할 수 있게 했습니다(특히 미니맥스 방식의 경우).

실험 결과
방법론은 UCI 머신러닝 저장소와 Grinsztajn 등이 제안한 벤치마크의 27개 실제 데이터셋에 대해 $N=101$개의 트리를 사용하는 랜덤 포레스트를 사용하여 평가되었습니다.

• 속도 향상: 대부분의 데이터셋에서 제안된 방법들은 0.1%($10^{-3}$)의 불일치율을 유지하면서 4배 이상의 속도 향상(런타임을 전체 앙상블의 10~20%로 감소)을 달성했습니다.
• 성능 편차: 보정 세트(calibration set)를 사용하여 투표 분포를 추정한 Minimean 방식이 일반적으로 가장 높은 속도 향상을 보였으며, 그 다음은 Minimixed, Minimax가 가장 보수적이었습니다.
• 데이터셋 특성: 조기 종료의 효과는 트리 투표의 분포와 상관관계가 있었습니다. 트리가 한 클래스에 압도적으로 투표하는 데이터셋(양봉 분포)은 공격적인 조기 종료가 가능했습니다. 반면, 기본 오류율이 높고 투표 분포가 중앙에 집중된 데이터셋(예: "Dota2" 및 "Hospitalization")은 합의에 도달하기 어려워 속도 향상이 작았습니다.
• 비교: 제안된 방법들은 이항 신뢰 구간(binomial confidence bands)과 독립성 가정에 의존하는 Schwing 등(2011)의 베이스라인 방법보다 우수한 성능을 보였습니다.

의의 및 주장
본 논문은 기본 모델 간의 독립성을 가정하지 않고 다수결 기반 이진 앙상블에 대해 증명 가능한 최적의(provably optimal) 조기 종료 전략을 제시한 첫 번째 방법이라고 주장합니다. 저자들은 자신들의 접근 방식이 사용자로 하여금 더 크고 정확한 앙상블을 훈련시킨 후, 각 특정 추론에 필요한 계산 자원만을 사용하도록 중단 전략을 활용할 수 있게 해준다는 점을 강조합니다.

논문은 다음과 같은 한계점을 겸허히 명시합니다: 이 방법은 이진 분류 및 가중치가 없는 다수결 앙상블에 국한됩니다. 다중 클래스 문제, 회귀, 또는 기본 모델의 특정 가중치나 실행 순서가 요구되는 앙상블에는 직접 적용할 수 없습니다. 또한, 저자들은 이 방법이 가지치기(pruning)와 호환 가능하지만, 가지치기는 조기 종료를 효과적으로 만드는 요소인 중복성(상관관계가 있는 투표)을 줄이는 것을 목표로 하기 때문에 가지치기가 적용된 포레스트에서는 이득이 덜 드라마틱할 수 있다고 제안합니다. 향후 연구 과제로 다중 클래스 및 가중치 앙상블으로의 이론 확장을 제시하였습니다.