Optimally-Weighted Herding is Bayesian Quadrature

Problematica
Una sfida fondamentale nel machine learning statistico è il calcolo delle aspettative di funzioni su distribuzioni di probabilità, espresse come $Z_{f,p} = \int f(x)p(x)dx$. Mentre i metodi Monte Carlo approssimano questo valore tramite campionamento casuale con un tasso di convergenza di $O(1/\sqrt{N})$, essi soffrono di varianza stocastica. I metodi Quasi-Monte Carlo offrono un'alternativa deterministica generando pseudo-campioni per minimizzare la discrepanza tra la distribuzione empirica dei campioni e la distribuzione target $p(x)$. Due metodi deterministici prominenti sono il Kernel Herding, che minimizza la Maximum Mean Discrepancy (MMD) per selezionare i campioni, e la Bayesian Quadrature (BQ), che inferisce una distribuzione a posteriori sulla funzione $f$ per stimare l'integrale. Il documento affronta la connessione teorica tra questi due metodi e indaga se un approccio pesato alla selezione dei campioni possa superare il normale herding.

Metodologia
Gli autori stabiliscono un legame teorico tra il Kernel Herding e la Bayesian Quadrature analizzando le funzioni obiettivo minimizzate da ciascuno.

1. Equivalenza dei Criteri: Il documento dimostra che il criterio minimizzato nel Kernel Herding (MMD) è matematicamente equivalente alla varianza a posteriori della stima dell'integrale nella Bayesian Quadrature, assumendo un prior Gaussiano (GP) su $f$. Nello specifico, l'errore atteso in BQ corrisponde alla MMD tra la distribuzione target $p$ e una distribuzione discreta definita dai campioni e dai loro pesi.
2. Sequential Bayesian Quadrature (SBQ): Mentre l'Herding standard assegna pesi uniformi ($1/N$) ai campioni, la BQ assegna pesi ottimali derivati dal posteriore del GP. Gli autori propongono la Sequential Bayesian Quadrature (SBQ), un algoritmo greedy che seleziona le posizioni dei campioni per minimizzare la varianza a posteriori (equivalente a minimizzare la MMD con pesi ottimali).
3. Analisi dei Pesi: Il documento analizza le proprietà dei pesi della BQ, notando che non sono necessariamente positivi e non sommano a uno. Si dimostra che questi pesi sono ottimali in senso minimax sul Reproducing Kernel Hilbert Space (RKHS) definito dal kernel.
4. Submodularità: Gli autori investigano le proprietà di convergenza della SBQ collegando il processo di selezione al problema della selezione di un dizionario sparso (sparse dictionary selection). Dimostrano che la funzione obiettivo è "approssimativamente submodulare", permettendo di stabilire limiti teorici sulle prestazioni della strategia di selezione greedy, sebbene tali limiti siano più deboli rispetto a quelli per funzioni strettamente submodulari.

Contributi Chiave

1. Unificazione Teorica: Il documento prova che la perdita minimizzata dal Kernel Herding è identica all'errore atteso (varianza a posteriori) nella Bayesian Quadrature. Di conseguenza, la BQ viene inquadrata come una versione pesata dell'Herding in cui i pesi sono ottimali per dato RKHS.
2. Ottimalità dei Pesi: Viene dimostrato che i pesi derivati dalla BQ dominano l'Herding a pesatura uniforme e altri metodi di herding non ottimalmente pesati in termini di tasso di convergenza.
3. Connessione Algoritmica: Il lavoro collega la selezione greedy dei campioni nella BQ alla selezione di un dizionario sparso, stabilendo che l'obiettivo è approssimativamente submodulare.
4. Validazione Empirica: Gli autori forniscono evidenza empirica dimostrando che la SBQ raggiunge un tasso di convergenza più veloce di $O(1/N)$, superando sia l'Herding standard che il campionamento i.i.d. casuale in termini di Maximum Mean Discrepancy e errore di stima dell'integrale.

Risultati

• Tassi di Convergenza: In esperimenti utilizzando una miscela di Gaussiane 2D, la SBQ ha dimostrato un tasso di convergenza superiore al tasso $O(1/N)$ tipicamente associato all'Herding in spazi a dimensione finita. Sebbene il tasso di convergenza teorico esatto per la SBQ in spazi a dimensione infinita rimanga sconosciuto, i risultati empirici suggeriscono che sia più veloce di $O(1/N)$.
• Efficienza del Campionamento: Il documento illustra come un piccolo numero di campioni SBQ (ad esempio 8) con pesi ottimali possa raggiungere lo stesso errore di stima di un numero maggiore di campioni Herding (ad esempio 20) con pesi uniformi.
• Robustezza: Esperimenti su funzioni esterne all'RKHS assunto hanno mostrato che, sebbene le garanzie teoriche dipendano dall'appartenenza della funzione all'RKHS, il ranking relativo delle prestazioni dei metodi (SBQ > Herding > i.i.d.) è rimasto coerente anche per funzioni "fuori modello".
• Limiti di Errore: La MMD fornisce un limite superiore provabile sull'errore empirico della stima BQ, che si è dimostrato diminuire rapidamente con il numero di campioni.

Significatività e Rivendicazioni
Il documento sostiene che la Sequential Bayesian Quadrature rappresenti un avanzamento significativo rispetto al Kernel Herding integrando la pesatura ottimale nel processo di selezione dei campioni. Inquadrando la BQ come un metodo di Herding pesato in modo ottimale, gli autori forniscono un quadro teorico unificato che spiega la prestazione superiore della BQ. Il lavoro evidenzia che, sebbene la BQ comporti un costo computazionale più elevato ($O(N^3)$ per il calcolo dei pesi rispetto a $O(N^2)$ per l'Herding), il tasso di convergenza più rapido può renderla più efficiente in scenari in cui le valutazioni della funzione sono costose. Gli autori notano con modestia che, sebbene abbiano stabilito un limite superiore sull'errore empirico e dimostrato una convergenza empiricamente più veloce di $O(1/N)$, il tasso di convergenza teoricamente ottimale per la SBQ in spazi a dimensione infinita rimane una questione aperta per la ricerca futura. Il documento conclude che la scelta del metodo dipende dal compromesso tra il costo computazionale e la spesa per la valutazione della funzione integranda $f$.