Course:CPSC522/Bayesian Coresets

Bayesian Coresets

In order to decouple increasing data sizes from the run-time complexity of Bayesian posterior inference methods like MCMC, Bayesian coresets adaptively subsample and weight observations, thereby constructing a generic approximate sufficient statistic.

Principal Author: Boyan Beronov

Collaborators:

Abstract

As data sizes grow towards the infinite limit, the cost of Bayesian inference becomes increasingly prohibitive for algorithms which don't approximately exhibit linear run-time scaling and constant memory cost. This is a major reason why, despite their inherent bias, variational inference methods have become increasingly popular and relevant in comparison to the well established, but slow MCMC methods which are at least asymptotically unbiased, i.e., converge to the exact value in infinite run-time. Bayesian coresets provide a practical way of scaling up the latter by first summarizing the statistical information present in observations, – i.e., by approximating the full likelihood function at a controllable trade-off between accuracy and memory cost – and then running expensive inference algorithms on the compressed data set. Under the sole assumptions of conditional independence and tractable likelihood, recent work has developed linear cost algorithms for coreset construction with rigorous convergence bounds, which in particular are independent of the internals of the generative model. As a new, generic means for constructing approximate sufficient statistics, these methods might evolve to have significant impact on many problems of interest in probabilistic machine learning and artificial intelligence.

Builds on

Bayesian coresets arise when the idea of coresets, which originated in the context of approximation algorithms in computational geometry, is applied to Bayesian inference. Once constructed, coresets can provide significant speedups to approximate Bayesian inference, e.g., for algorithms in the MCMC and Variational Inference families. Their construction is an interesting computational problem in its own right, and is closely related to Monte Carlo methods and the sparse approximation problem.

Related Pages

Any expensive density estimation problem which tolerates approximate inference algorithms is a potential application of Bayesian coresets. This includes: Graphical Models and Bayesian Networks, Learning Probabilistic Models with Complete Data and Density-Based Unsupervised Learning. Furthermore, as a form of episodic memory, Bayesian coresets might have more general implications for online learning, Continual Learning, Bounded Rationality and Artificial General Intelligence.

Content

Definition

Geometric Coresets

Coresets were first developed in computational geometry as a means for approximating the shape of a large point set – see Agarwal et al. for a comprehensive review. If an optimization problem admits an $\varepsilon$-coreset, then there is a linear or near-linear algorithm for selecting a constant size subset of the original problem, such that the exact solution to the small problem is an approximation to the exact solution of the original problem within a factor of $(1+\varepsilon )$.

One of the original applications of geometric coresets is clustering, via algorithms like $k$-center, $k$-line-center, $k$-median and $k$-means. As the latter two are instances of summed clustering, where the objective is a sum over points, their coreset formulation operates on weighted point sets . In particular, let $P\subset \mathbb {R} ^{D}$ be a point set, $d(p,C)=\min _{q\in C}\,d(p,q)$ a distance function, $w:\,P\to \mathbb {N}$ a weight function, and $\mu _{P}^{w}(C)=\sum _{p\,\in \,P}w(p)\,d(p,C)$ the objective function to be minimized over candidate cluster sets $C\subset \mathbb {R} ^{D}$ of fixed size. Such problems admit $\varepsilon$-coresets, i.e., subsets ${\bar {P}}\subseteq P$ and weight functions ${\bar {w}}:\,P\to \mathbb {N}$ such that for any $C$ of appropriate size,

$$(1-\varepsilon )\,\mu _{P}^{w}(C)\;\leq \;\mu _{\bar {P}}^{\bar {w}}(C)\;\leq \;(1+\varepsilon )\,\mu _{P}^{w}(C)\;.$$

If the points $p\in P$, the cluster set $C$ and the distance function $d(p,C)$ are replaced respectively by observations $x\in X$, parameters $\theta$ and a log-likelihood function $\log \left\{p(\{x\};\theta )\right\}$, the structural similarity of the clustering problem to maximum likelihood estimation (MLE) becomes apparent. This naturally leads to the question whether the notion of approximation via weighted coresets can be extended to the setting of statistical inference.

Bayesian Coresets

Let a Bayesian model for observations $X=\{x_{1},\dots ,x_{n}\}$ consist of a prior measure $\Pi _{\emptyset }(\operatorname {d} \!\theta )$ and a likelihood $p(X;\theta )$ with parameters $\theta \in \mathbb {R} ^{D}$. Define the log-likelihood or potential ${\mathcal {L}}_{X}(\theta )=\log \left\{p(X;\theta )\right\}$ and the marginal likelihood, evidence, or partition function $Z_{X}=\int \exp \left\{{\mathcal {L}}_{X}(\theta )\right\}\Pi _{\emptyset }(\operatorname {d} \!\theta )$. Then the posterior measure over parameters $\theta$ is

$$\Pi _{X}(\operatorname {d} \!\theta )={\frac {1}{Z_{X}}}\,\exp \left\{{\mathcal {L}}_{X}(\theta )\right\}\,\Pi _{\emptyset }(\operatorname {d} \!\theta )\;.$$

Under the conditional independence assumption, $\forall \;i,j\in [n]:\;x_{i}\perp \!\!\!\perp _{\theta }x_{j}$, the potential decomposes as

$${\mathcal {L}}_{X}(\theta )=\log \,\left\{\prod _{x\,\in \,X}p\left(\{x\};\theta \right)\right\}=\sum _{x\,\in \,X}{\mathcal {L}}_{\{x\}}(\theta )\;.$$

In order to reduce the cost of evaluating ${\mathcal {L}}_{X}(\theta )$ in inference methods, a Bayesian coreset approximation is introduced as

$${\mathcal {L}}_{\bar {X}}^{w}=\sum _{x\,\in \,{\bar {X}}}w(x)\,{\mathcal {L}}_{\{x\}}\;,$$

consisting of subsampled data ${\bar {X}}\subseteq X$ and a corresponding weight function $w:\,{\bar {X}}\to \mathbb {R} ^{+}$. The coreset posterior approximation induced by ${\mathcal {L}}_{\bar {X}}^{w}$ is then

$$\Pi _{\bar {X}}^{w}(\operatorname {d} \!\theta )={\frac {1}{Z_{\bar {X}}^{w}}}\,\exp\{{\mathcal {L}}_{\bar {X}}^{w}(\theta )\}\,\Pi _{\emptyset }(\operatorname {d} \!\theta )\;,\quad Z_{\bar {X}}^{w}=\int \exp\{{\mathcal {L}}_{\bar {X}}^{w}(\theta )\}\,\Pi _{\emptyset }(\operatorname {d} \!\theta )\;.$$

Construction Algorithms

There are several variations of Bayesian coresets, including approaches such as likelihood-based data squashing (LDS) by Madigan et al. , which construct pseudo data points for summarization. The following discussion is restricted to methods which only select and weight observed data points.

Sampling Approaches

In the realm of randomized approximation algorithms, the first improvement over trivial uniform sampling is importance sampling, in which subsampling is performed according to some distribution that correlates with the likelihood of data points. Variations of this approach are taken by most existing literature, both for geometric and for Bayesian coresets, including Feldman et al. , Zhang et al. , Huggins et al. , Campbell et al. and Lucic et al.

Optimization Approaches: Hilbert Coresets

In order to improve the theoretical guarantees of Bayesian coresets over randomized constructions, Campbell et al. introduced a new family of generic, deterministic algorithms. When the function space of ${\mathcal {L}}$ is a Hilbert space, i.e., when it admits an inner product, Hilbert coresets can be computed by solving suitable optimization problems formulated only in terms of inner products and Hilbert norms of the (function) vectors ${\mathcal {L}}_{X}$ and ${\mathcal {L}}_{\{x\}}$. Instances of this family of methods include:

• Quadratic optimization under a polytope constraint using the Frank-Wolfe algorithm ,
• Manifold optimization on the unit hyper-sphere using iterative geodesic search (generalization of line search) , maximizing the directional alignment between the vectors of the full (${\mathcal {L}}_{X}$) and coreset (${\mathcal {L}}_{\bar {X}}^{w}$) potentials.

Both methods are greedy and iterative, achieving the linear run-time required by the coreset problem formulation. The main contribution of the latter algorithm is the optimal scaling of the coreset potential, which significantly reduces approximation errors especially in the empirically relevant regime of small coresets. Regarding the choice of Hilbert norms, several options have been suggested, including a weighted $L^{2}$ norm and a weighted Fisher information metric. In general, such norms require a cheap approximation to the true posterior as a weighting measure.

Convergence Analysis

Several convergence results exist for model-specific coreset constructions, in particular for mixture models and logistic regression as in . Furthermore, adaptations of classical optimization methods have been proposed for the weighted likelihood setting, e.g., weighted EM .

For the generic case, Huggins et al. provide a non-asymptotic approach for controlling the error of finite-size Bayesian posterior approximations, by means of a two-step bound using the Fisher information and Wasserstein metrics. This enables the full characterization of the statistical error in the iterative constructions of and , including the effect of the weighting distribution. Specifically, these approaches achieve a decay of the Wasserstein posterior distance which is exponential in $|{\bar {X}}|$, the coreset size.

Streaming and Parallel Computation

An important property of many coreset constructions is their compositionality, which enables their construction to be performed sequentially or in parallel on small batches of data, with a subsequent efficient merge operation preserving theoretical approximation guarantees . In particular, the following properties hold for many geometric coresets:

1. If ${\bar {A}},{\bar {B}}$ are $\varepsilon$-coresets for $A,B$, then ${\bar {A}}\cup {\bar {B}}$ is an $\varepsilon$-coreset for $A\cup B$.
2. If ${\bar {A}}$ is an $\varepsilon$-coreset for $A$, and ${\bar {\bar {A}}}$ is an ${\bar {\varepsilon }}$-coreset for ${\bar {A}}$, then ${\bar {\bar {A}}}$ is an ${\bar {\bar {\varepsilon }}}$-coreset for $A$ with $1+{\bar {\bar {\varepsilon }}}=(1+\varepsilon )(1+{\bar {\varepsilon }})$.

In both the sequential and the parallel setting, an optimal strategy for merging $b$ batch-coresets is then an alternation between (1) and (2) in a tree of depth $O(\log b)$.

Analogous properties hold for several Bayesian coreset constructions, e.g., in and in when the approximation error is measured in the weighted uniform norm $\|\,l\,\|:=\sup _{\theta }\left|{\frac {l(\theta )}{{\mathcal {L}}_{X}(\theta )}}\right|$. But more generally, the posterior approximation bounds from provide a formalism better suited for characterizing the compositional guarantees of Bayesian coreset constructions.

Related Numerical Problems

The Hilbert coreset formulation is related to the sparse approximation problem, for which a wide range of numerical methods have been studied. See for a discussion of the particular requirements in the coreset setting.

Relevance for Continual Learning

A long-standing challenge for machine learning and AI systems is the problem of Continual Learning or lifelong learning, i.e., the ability of an agent to learn over long time periods by incorporating new knowledge while retaining past experiences. The main obstacle for computational models of continual learning is the phenomenon of catastrophic forgetting , whereby new information interferes destructively with previously acquired knowledge representations. In a recent comprehensive review from the perspective of Artificial Neural Networks, Parisi et al. describe the influence of the Complementary Learning Systems theory on various deep learning architectures, in particular the use of dual memory and experience replay. The essential idea, motivated by a broad range of anatomical and cognitive studies, is an intricate interplay of two learning systems with complementary roles via storage, retrieval and goal-dependent replay:

• Semantic memory: responsible for learning general regularities/statistics of the environment; slow learning rate and overlapping, structured representations; associated with the neo-cortex,
• Episodic memory: responsible for learning arbitrary specifics of the environment; rapid learning rate and sparse representations; associated with the hippocampus.

In the context of Bayesian continual learning, the semantic and episodic memories could be interpreted as roughly corresponding to a generative model and a coreset – see, e.g., the continual learning model of Nguyen et al.