Optimally-Weighted Herding is Bayesian Quadrature

문제 정의
통계적 기계 학습의 근본적인 과제는 확률 분포에 대한 함수의 기댓값인 $Z_{f,p} = \int f(x)p(x)dx$를 계산하는 것이다. 몬테카를로 방법은 무작위 샘플링을 통해 이를 근사하며 $O(1/\sqrt{N})$의 수렴 속도를 갖지만, 확률적 분산 문제를 겪는다. 준 몬테카로(Quasi-Monte Carlo) 방법은 샘플의 경험적 분포와 대상 분포 $p(x)$ 사이의 불일치(discrepancy)를 최소화하는 의사 샘플(pseudo-samples)을 생성함으로써 결정론적인 대안을 제공한다. 두 가지 저명한 결정론적 방법으로는, MMD(Maximum Mean Discrepancy)를 최소화하여 샘플을 선택하는 커널 허딩(Kernel Herding)과, 피적분 함수 $f$에 대한 사후 분포를 추론하여 적분을 추정하는 베이지안 구적법(Bayesian Quadrature, BQ)이 있다. 본 논문은 이 두 방법 사이의 이론적 연결 고리를 다루며, 가중치를 적용한 샘플 선택 방식이 표준 허딩보다 더 나은 성능을 낼 수 있는지 조사한다.

방법론
저자들은 각 방법이 최소화하는 목적 함수를 분석함으로써 커널 허딩과 베이지안 구적법 사이의 이론적 연결 고리를 확립한다.

1. 기준의 등가성: 본 논문은 함수 $f$에 가우시안 프로세스(GP) 사전 분포를 가정할 때, 커널 허딩에서 최소화되는 기준(MMD)이 베이지안 구적법의 적분 추정치에 대한 사후 분산과 수학적으로 동일함을 입증한다. 구체적으로, BQ의 기대 오차는 대상 분포 $p$와 샘플 및 가중치로 정의된 이산 분포 사이의 MMD에 대응한다.
2. 순차적 베이지안 구적법 (Sequential Bayesian Quadrature, SBQ): 표준 허딩은 샘플에 균등 가중치($1/N$)를 할당하는 반면, BQ는 GP 사후 분포로부터 유도된 최적 가중치를 할당한다. 저자들은 사후 분산을 최소화하는(즉, 최적 가중치를 가진 MMD를 최소화하는 것과 동일한) 탐욕적 알고리즘인 순차적 베이지안 구적법(SBQ)을 제안한다.
3. 가중치 분석: 본 논문은 BQ 가중치의 특성을 분석하며, 이들이 반드시 양수일 필요는 없으며 합이 1이 되지 않을 수도 있음을 언급한다. 이러한 가중치들은 정의된 재생 커널 힐베르트 공간(RKHS)에 대해 미니맥스(minimax) 관점에서 최적임이 밝혀졌다.
4. 부가성(Submodularity): 저자들은 SBQ의 수렴 특성을 희소 딕셔너리 선택(sparse dictionary selection) 문제와 연관 지어 조사한다. 저자들은 목적 함수가 "근사적 부가성(approximately submodular)"을 가짐을 증명하여, 엄격한 부가 함수에 대한 결합보다 약하긴 하지만 탐욕적 선택 전략의 성능에 대한 이론적 경계를 제공한다.

주요 기여

1. 이론적 통합: 본 논문은 커널 허딩에서 최소화되는 손실이 베이지안 구적법의 기대 오차(사후 분산)와 동일함을 증명한다. 결과적으로, BQ는 주어진 RKHS에 대해 최적인 가중치를 갖는 가중 버전의 커널 허딩으로 프레임화된다.
2. 가중치의 최적성: BQ에서 유도된 가중치가 수렴 속도 측면에서 균등 가중치를 사용하는 허딩 및 기타 비최적 가중 허딩 방법들을 압도함을 보여준다.
3. 알고리즘적 연결: 본 연구는 BQ에서의 샘플의 탐욕적 선택을 희소 딕셔너리 선택 문제와 연결하여, 해당 목적 함수가 근사적 부가성을 가짐을 확립한다.
4. 경험적 검증: 저자들은 SBQ가 MMD 및 적분 추정 오차 측면에서 표준 허딩 및 i.i.d. 무작위 샘플링보다 빠른 $O(1/N)$ 이상의 수렴 속도를 달성함을 보여주는 경험적 증거를 제시한다.

결과

• 수렴 속도: 2차원 가우시안 혼합 모델을 사용한 실험에서, SBQ는 유한 차원 공간에서 허딩과 관련된 전형적인 $O(1/N)$ 속도보다 우수한 수렴 속도를 보였다. SBQ의 무한 차원 공간에서의 정확한 이론적 속도는 알려지지 않았으나, 경험적 결과는 $O(1/N)$보다 빠름을 시사한다.
• 샘플 효율성: 본 논문은 최적 가중치를 가진 소수의 SBQ 샘플(예: 8개)이 균등 가중치를 가진 더 많은 수의 허딩 샘플(예: 20개)과 동일한 추정 오차를 달end할 수 있음을 보여준다.
• 강건성: 가정된 RKHS 외부의 함수들에 대한 실험을 통해, 이론적 보장이 함수가 RKHS에 속하는 것에 의존함에도 불구하고, 방법론 간의 상대적 성능 순위(SBQ > Herding > i.i.d.)가 "모델 외(out-of-model)" 함수에 대해서도 일관되게 유지됨을 보여주었다.
• 오차 경계: MMD는 BQ 추정치의 경험적 오차에 대한 증명 가능한 상한을 제공하며, 이는 샘플 수가 증가함에 따라 빠르게 감소함을 보였다.

의의 및 주장
본 논문은 순차적 베이지안 구적법이 샘플 선택 과정에 최적 가중치 통합을 통해 커널 허딩보다 유의미한 발전을 이루었다고 주장한다. BQ를 최적으로 가중치가 부여된 허딩 방법으로 봄으로써, 저자들은 BQ의 우수한 성능을 설명하는 통합된 이론적 프레임워크를 제공한다. 본 연구는 BQ가 가중치 계산을 위해 더 높은 계산 비용($O(N^3)$ vs 허딩의 $O(N^2)$)을 수반하지만, 더 빠른 수렴 속도가 함수 평가 비용이 비싼 시나리오에서 더 효율적일 수 있음을 강조한다. 저자들은 경험적 오차의 상한을 설정하고 $O(1/N)$보다 빠른 수렴을 입증하면서도, 무한 차원 공간에서 SBQ의 이론적으로 최적인 수렴 속도는 향후 연구를 위한 열린 과제로 남겨두는 신중한 태도를 보인다. 결론적으로, 방법의 선택은 계산 비용과 피적분 함수 $f$를 평가하는 비용 사이의 트레이드오프에 달려 있다.