기술 요약: PACE (Prune-And-Compress Ensemble Models)

문제 제기

랜덤 포레스트 (Random Forests) 나 부스팅 (Boosting) 과 같이 의사결정나무 (decision trees) 기반의 앙상블 모델은 최첨단 예측 성능을 달성하지만, 많은 약한 학습자 (weak learners) 의 집적으로 인해 과도한 크기로 인해 종종 고통받습니다. 이러한 중복성은 지연 시간에 민감하고 자원이 제한된 환경에서의 배포에 상당한 장벽을 만들고, 메모리 풋프린트를 증가시키며, 강건성 검증 및 해석 가능성과 같은 하류 작업을 복잡하게 만듭니다.

기존 솔루션은 일반적으로 두 가지 범주로 나뉩니다:

1. 가지치기 (Pruning): 재가중치 부여 또는 제거를 통해 훈련된 앙상블에서 중복된 학습자를 제거합니다. 효과적이기는 하지만, 버려진 학습자를 대체할 새로운 학습자를 생성할 수 없기 때문에 가지치기는 압축 잠재력을 제한할 수 있습니다.
2. 압축 (Compression): 원래 앙상블을 근사하기 위해 처음부터 새로운 학습자를 생성합니다. 이는 높은 압축률을 달성할 수 있지만, 많은 방법들은 충실도 (정확한 예측 일치) 를 잃거나 원래 모델 계열보다 더 복잡한 학습자를 생성하여 모델의 구조적 제약을 위반합니다.

핵심적인 과제는 이러한 패러다임을 통합하여 충실도 (faithfulness) (원래 앙상블의 예측을 보존) 에 대한 엄격한 보장을 유지하면서 강력한 압축을 달성하되, 관련 없는 데이터 영역에 의해 과도하게 제약받지 않는 것입니다.

방법론: PACE 프레임워크

PACE (Prune-And-Compress Ensemble) 는 충실도 제어 프레임워크 하에 통합된, 능동적 학습자 생성과 가지치기를 교차시키는 2 단계 전략을 도입합니다.

1. 2 단계 전략

• 1 단계: 능동적 학습자 생성 (압축): 고정된 학습자 집합으로 시작하는 대신, PACE 는 초기 앙상블을 풍부하게 하기 위해 새로운 학습자를 능동적으로 생성합니다. 이 단계는 컬럼 생성 (Column Generation) 기법을 활용합니다. 목표는 완화된 가지치기 문제 ( $\ell_1$-norm surrogate 사용) 의 최적 값을 줄이는 "개선 학습자 (improving learners)"를 찾는 것입니다.
  • 이 과정은 하류 희소화 (sparsification) 잠재력을 향상시키는 학습자 $h$를 식별합니다.
  • 완화된 문제를 엄격하게 개선할 수 있는 새로운 학습자가 존재하는지 감지하기 위해 가격 결정 문제 (pricing problem) 가 해결됩니다. 그러한 학습자가 존재하지 않는 경우 ($L(h) = \emptyset$), 생성 단계가 종료되어 풍부해진 앙상블이 가능한 최상의 완화 값을 달성하기 위해 필요한 모든 학습자를 포함함을 보장합니다.
• 2 단계: 가지치기: 앙상블이 풍부해진 후, PACE 는 이 증강된 집합에서 원래 가지치기 문제 (가중치의 $\ell_0$-norm 최소화) 를 해결합니다. 이를 통해 더 크고 다양한 학습자 풀에서 희소한 가중치 부분집합을 선택할 수 있게 되어, 종종 원래 집합만 가지치기한 경우보다 더 작은 최종 앙상블을 결과로 낳습니다.

2. 충실도 관리

PACE 는 전체 표본 공간이나 고정된 경험적 집합에 대한 정확한 일치를 강제하는 것을 넘어선 세밀한 충실도 정의를 도입합니다. 이는 두 매개변수로 정의된 실용적 관심 영역 $X_\eta \cap X_\delta$ 내에서만 충실도를 강제합니다.

• 신뢰 영역 ($X_\eta$): 원래 앙상블이 다른 클래스보다 $\eta$보다 큰 신뢰도 마진으로 예측하는 샘플들입니다. 이는 원래 모델의 선택이 임의적일 수 있는 낮은 신뢰도 영역에서 충실도 강제를 피합니다.
• 타당성 영역 ($X_\delta$): Isolation Forest 를 통해 계산된 데이터 분포에 대한 타당성 점수가 $\ge \delta$인 샘플들입니다. 이는 원래 예측을 보존하는 것이 실용적 관련성이 제한적인 이상치 및 분포 외 샘플을 제외합니다.

이를 강제하기 위해 PACE 는 "분리 샘플 (separating samples, 현재 모델이 원래 모델과 일치하지 않는 샘플)"을 찾기 위해 제약 프로그래밍 (Constraint Programming, CP) 을 반복적으로 사용합니다. 정의된 영역 내에서 분리 샘플이 발견되면, 이를 제약 집합에 추가하고 가중치를 다시 최적화합니다. 이 사이클은 목표 영역에 더 이상 분리 샘플이 없을 때까지 반복됩니다.

주요 기여

1. 통합 프레임워크: 본 논문은 가지치기와 압축이 상호 보완적임을 보여줍니다. PACE 는 능동적 생성을 통해 앙상블을 먼저 풍부하게 한 후 그 결과를 가지치기함으로써 두 접근법의 강점을 활용하여 이를 통합합니다.
2. 풍부화를 위한 컬럼 생성: 저자들은 새로운 학습자를 생성하기 위해 컬럼 생성을 사용하는 원칙적인 전략을 제공합니다. 여기에는 추가적인 개선 학습자가 존재하지 않음을 보장하여 후속 가지치기 잠재력을 극대화하는 이론적 정지 기준이 포함됩니다.
3. 유연한 충실도: 본 논문은 충실도 개념을 의미 있는 영역 (높은 신뢰도와 높은 타당성) 만 대상으로 확장합니다. 이 절충안은 임의의 근사의 함정을 피하면서 정확한 충실도 강제보다 더 강력한 압축을 가능하게 합니다.
4. 제약 기반 분리: PACE 는 분리 샘플을 찾기 위해 제약 기반 형식을 활용하며, 저자들은 이것이 기존 연구에서 사용된 목적 기반 형식보다 계산적으로 우수함을 보여줍니다.

실험 결과

저자들은 Random Forest 와 AdaBoost 앙상블을 사용하여 다양한 데이터셋 (예: COMPAS, FICO, Diabetes, Ionosphere) 에서 PACE 를 평가했습니다.

• 압축 성능: PACE 는 기존 가지치기 전용 방법 (FIPE 등) 과 제거된 변형 (생성 전용 또는 가지치기 전용) 보다 일관되게 우수한 성과를 보였습니다. 많은 경우, 최종 앙상블은 원래 학습자가 아닌 새로 생성된 학습자로 거의 완전히 구성되었습니다.
• 충실도 제어: $\eta$와 $\delta$ 매개변수를 통해 충실도를 완화하면 최종 앙상블 크기가 크게 감소합니다. 예를 들어, FICO 데이터셋에서 $\eta$를 증가시키면 엄격한 충실도로는 달성할 수 없는 58 개의 트리에서 3 개로 앙상블이 축소되었습니다.
• 계산 효율성: PACE 에서 사용된 제약 기반 분리 접근법은 FIPE 와 같은 최첨단 방법에서 사용되는 목적 기반 분리에 비해 상당한 속도 향상 (특정 Random Forest 구성에서 최대 37 배) 을 달성했습니다.
• 절단 연구 (Ablation Studies): 실험은 생성 전용이나 가지치기 전용 어느 하나도 전체 PACE 프레임워크의 성능을 달성하지 못함을 확인시켜 주어, 2 단계 접근법의 필요성을 입증했습니다.

중요성 및 주장

본 논문은 PACE 가 앙상블 압축에 대한 원칙적이고 유연한 접근법을 제공한다고 주장합니다. 그 주요 중요성은 다음과 같습니다:

• 우수한 압축: 관련 영역에서 예측 충실도를 유지하면서 기존 방법보다 더 작은 앙상블 크기를 달성합니다.
• 이론적 보장: 휴리스틱 근사에 의존하는 대신, 사용자 정의된 특정 영역 내에서 충실도에 대한 엄격한 보장을 제공합니다.
• 계산적 발전: 제약 프로그래밍이 앙상블 가지치기에 내재된 분리 문제에 대한 매우 효율적인 도구임을 보여주며, 이 맥락에서 전통적인 혼합 정수 선형 계획법 (MILP) 접근법보다 우수함을 입증했습니다.

저자들은 $\ell_0$-norm 의 결합적 특성과 생성 단계로 인해 PACE 가 가지치기 전용 방법보다 계산 비용이 더 높다는 한계를 인정합니다. 또한 현재는 트리 기반 학습자로 제한되어 있지만, 적절한 수학적 모델을 구축할 수 있다면 다른 계열로 이론적으로 확장 가능하다고 언급합니다. 향후 연구로는 학습자 생성을 위한 가격 결정 문제 최적화와 단순 학습자 수를 넘어선 복잡도 지표 정비가 제안됩니다.