Optimally-Weighted Herding is Bayesian Quadrature

Declaração do Problema
Um desafio fundamental na aprendizagem estatística de máquina é computar as expectativas de funções sobre distribuições de probabilidade, expressas como $Z_{f,p} = \int f(x)p(x)dx$. Embora os métodos de Monte Carlo aproximem isso via amostragem aleatória com uma taxa de convergência de $O(1/\sqrt{N})$, eles sofrem de variância estocástica. Métodos de Quasi-Monte Carlo oferecem uma alternativa determinística ao gerar pseudo-amostras para minimizar a discrepância entre a distribuição empírica das amostras e a distribuição alvo $p(x)$. Dois métodos determinísticos proeminentes são o Kernel Herding, que minimiza a Discrepância de Média Máxima (MMD) para selecionar amostras, e a Quadratura Bayesiana (BQ), que infere uma distribuição posterior sobre a integranda $f$ para estimar o integral. O artigo aborda a conexão teórica entre esses dois métodos e investiga se uma abordagem ponderada de seleção de amostras pode superar o herding padrão.

Metodologia
Os autores estabelecem um vínculo teórico entre o Kernel Herding e a Quadratura Bayesiana ao analisar as funções objetivo minimizadas por cada um.

1. Equivalência de Critérios: O artigo demonstra que o critério minimizado no Kernel Herding (MMD) é matematicamente equivalente à variância posterior da estimativa do integral na Quadratura Bayesiana, assumindo uma priori de Processo Gaussiano (GP) em $f$. Especificamente, o erro esperado em BQ corresponde à MMD entre a distribuição alvo $p$ e uma distribuição discreta definida pelas amostras e seus pesos.
2. Quadratura Bayesiana Sequencial (SBQ): Enquanto o Herding padrão atribui pesos uniformes ($1/N$) às amostras, a BQ atribui pesos ótimos derivados da posterior do GP. Os autores propõem a Quadratura Bayesiana Sequencial (SBQ), um algoritmo guloso que seleciona localizações de amostras para minimizar a variância posterior (equivalente a minimizar a MMD com pesos ótimos).
3. Análise de Pesos: O artigo analisa as propriedades dos pesos da BQ, observando que eles não são necessariamente positivos e não somam um. Esses pesos são mostrados como ótimos em um sentido minimax sobre o Espaço de Hilbert de Núcleo Reproduzido (RKHS) definido pelo kernel.
4. Submodularidade: Os autores investigam as propriedades de convergência da SBQ ao relacionar o processo de seleção ao problema de seleção de dicionário esparso. Eles provam que a função objetivo é "aproximadamente submodular", permitindo limites teóricos sobre o desempenho da estratégia de seleção gulosa, embora esses limites sejam mais fracos do que os para funções estritamente submodulares.

Principais Contribuições

1. Unificação Teórica: O artigo prova que a perda minimizada pelo Kernel Herding é idêntica ao erro esperado (variância posterior) na Quadratura Bayesiana. Consequentemente, a BQ é enquadrada como uma versão ponderada do Kernel Herding, onde os pesos são ótimos para o dado RKHS.
2. Otimalidade dos Pesos: É mostrado que os pesos derivados da BQ dominam o Herding de pesos uniformes e outros métodos de herding não otimamente ponderados em termos de taxa de convergência.
3. Conexão Algorítmica: O trabalho conecta a seleção gulosa de amostras na BQ ao problema de seleção de dicionário esparso, estabelecendo que o objetivo é aproximadamente submodular.
4. Validação Empírica: Os autores fornecem evidência empírica demonstrando que a SBQ alcança uma taxa de convergência mais rápida que $O(1/N)$, superando tanto o Herding padrão quanto a amostragem i.i.d. em termos de Discrepância de Média Máxima e erro de estimativa de integral.

Resultos

• Taxas de Convergência: Em experimentos usando uma mistura de Gaussianas 2D, a SBQ demonstrou uma taxa de convergência superior à taxa $O(1/N)$ tipicamente associada ao Herding em espaços de dimensão finita. Embora a taxa teórica exata para a SBQ em espaços de dimensão infinita permaneça desconhecida, resultados empíricos sugerem que ela é mais rápida que $O(1/N)$.
• Eficiência de Amostragem: O artigo ilustra que um pequeno número de amostras da SBQ (por exemplo, 8) com pesos ótimos pode alcançar o mesmo erro de estimativa que um número maior de amostras do Herding (por exemplo, 20) com pesos uniformes.
• Robustez: Experimentos em funções fora do RKHS assumido mostraram que, embora as garantias teóricas dependam de a função pertencer ao RKHS, o ranking relativo de desempenho dos métodos (SBQ > Herding > i.i.d.) permaneceu consistente mesmo para funções "fora do modelo".
• Limites de Erro: A MMD fornece um limite superior provável no erro empírico da estimativa da BQ, que foi mostrado diminuir rapidamente com o número de amostras.

Significância e Alegações
O artigo afirma que a Quadratura Bayesiana Sequencial representa um avanço significativo sobre o Kernel Herding ao integrar a ponderação ótima no processo de seleção de amostras. Ao visualizar a BQ como um método de Herding otimamente ponderado, os autores fornecem um framework teórico unificado que explica o desempenho superior da BQ. O trabalho destaca que, embora a BQ incorra em um custo computacional mais alto ($O(N^3)$ para computação de pesos vs. $O(N^2)$ para Herding), a taxa de convergência mais rápida pode torná-la mais eficiente em cenários onde as avaliações da função são caras. Os autores observam modestamente que, embora estabeleçam um limite superior no erro empírico e demonstrem convergência mais rápida que $O(1/N)$ empiricamente, a taxa de convergência teoricamente ótima para a SBQ em espaços de dimensão infinita permanece uma questão aberta para pesquisas futuras. O artigo conclui que a escolha do método depende do compromisso entre o custo computacional e o custo de avaliar a integranda $f$.