Sequential core-set Monte Carlo (Beronov, Weilbach, Wood & Campbell, UAI 2021): SMC over data arriving in batches whose rejuvenation moves cost a bounded amount however much data has arrived.
The target after t batches is p_t(θ) ∝ p₀(θ) · Π_{s≤t} Π_b p(x_b⁽ˢ⁾ | θ).
Plain resample-move SMC (IBIS; Chopin 2002) must score every past datum in
each move, so step t costs O(t). SCMC keeps at most :memory M past data
points with weights — a core-set — whose weighted log-likelihood
approximates that of all data so far, and moves the particles against
log p₀(θ) + Σ_j w_j log p(u_j | θ).
After each step's moves, when the core-set and the new batch exceed M, it
is recompressed: a sparse nonnegative least-squares fit (GIGA; Campbell &
Broderick 2018) of the core-set's log-likelihood functions, centred and
evaluated at the current particles, to their weighted sum. GIGA fixes the
weights' proportions greedily and fits only their common scale; its
weights are then refitted by nonnegative least squares on the points it
selected, the fully corrective update of Campbell & Beronov (NeurIPS
2019) (:refit :nnls, the default; :refit :none keeps GIGA's weights,
as in the UAI 2021 algorithm). The fit is best where the population has
its mass.
:projection-inflation k is a research option and a deviation from the
UAI 2021 algorithm, off by default: the projection is fitted at the
particles spread by the factor k about their mean, μ + k·(θ − μ), rather
than at the particles themselves, so the core-set's log-likelihood is
matched over a wider region than the current population (the posterior
can move outside it as data arrive). It costs N·|E| likelihood
evaluations per compression, and the likelihood must be finite at the
spread points. k = 1, or no factor, is the UAI 2021 projection.
Each new batch reweights the particles by its own exact likelihood, but
the particles it reweights are not distributed as the previous target:
they were moved against the previous step's core-set before that step
compressed it (the core-set plus that step's batch), while the posterior
they stand for from then on uses the compressed core-set. No importance
correction exp(Σ_C' w'·ℓ − Σ_C w·ℓ) is applied for that switch, as in
the paper's Algorithm 1; the next moves target the compressed core-set.
So the particles carry the core-set's approximation error: small when the
log-likelihoods compress well (exchangeable data, few parameters), larger
for a small :memory. With M at least the amount of data, SCMC is
resample-move SMC and nothing is approximated.
The engine is foerster.population.theta/theta-smc on θ vectors: a step
resamples, then moves every particle by population-scaled random-walk
Metropolis.
Sequential core-set Monte Carlo (Beronov, Weilbach, Wood & Campbell, UAI
2021): SMC over data arriving in batches whose rejuvenation moves cost a
bounded amount however much data has arrived.
The target after t batches is p_t(θ) ∝ p₀(θ) · Π_{s≤t} Π_b p(x_b⁽ˢ⁾ | θ).
Plain resample-move SMC (IBIS; Chopin 2002) must score every past datum in
each move, so step t costs O(t). SCMC keeps at most `:memory` M past data
points with weights — a core-set — whose weighted log-likelihood
approximates that of all data so far, and moves the particles against
log p₀(θ) + Σ_j w_j log p(u_j | θ).
After each step's moves, when the core-set and the new batch exceed M, it
is recompressed: a sparse nonnegative least-squares fit (GIGA; Campbell &
Broderick 2018) of the core-set's log-likelihood functions, centred and
evaluated at the current particles, to their weighted sum. GIGA fixes the
weights' proportions greedily and fits only their common scale; its
weights are then refitted by nonnegative least squares on the points it
selected, the fully corrective update of Campbell & Beronov (NeurIPS
2019) (`:refit :nnls`, the default; `:refit :none` keeps GIGA's weights,
as in the UAI 2021 algorithm). The fit is best where the population has
its mass.
`:projection-inflation k` is a research option and a deviation from the
UAI 2021 algorithm, off by default: the projection is fitted at the
particles spread by the factor k about their mean, μ + k·(θ − μ), rather
than at the particles themselves, so the core-set's log-likelihood is
matched over a wider region than the current population (the posterior
can move outside it as data arrive). It costs N·|E| likelihood
evaluations per compression, and the likelihood must be finite at the
spread points. k = 1, or no factor, is the UAI 2021 projection.
Each new batch reweights the particles by its own exact likelihood, but
the particles it reweights are not distributed as the previous target:
they were moved against the previous step's core-set before that step
compressed it (the core-set plus that step's batch), while the posterior
they stand for from then on uses the compressed core-set. No importance
correction exp(Σ_C' w'·ℓ − Σ_C w·ℓ) is applied for that switch, as in
the paper's Algorithm 1; the next moves target the compressed core-set.
So the particles carry the core-set's approximation error: small when the
log-likelihoods compress well (exchangeable data, few parameters), larger
for a small `:memory`. With M at least the amount of data, SCMC is
resample-move SMC and nothing is approximated.
The engine is `foerster.population.theta/theta-smc` on θ vectors: a step
resamples, then moves every particle by population-scaled random-walk
Metropolis.(append-batch {:keys [particles memory scale seed coreset steps model
compressed? refit projection-inflation]
:as state}
batch)Advance a persistent SCMC state by one non-empty batch. The old state remains reusable. Retains only the population and a bounded coreset; the caller owns any observation history needed for replay or correction. :last-update reports ESS before resampling, not convergence or accuracy. Historical replacement/retraction is not an append operation.
Advance a persistent SCMC state by one non-empty batch. The old state remains reusable. Retains only the population and a bounded coreset; the caller owns any observation history needed for replay or correction. :last-update reports ESS before resampling, not convergence or accuracy. Historical replacement/retraction is not an append operation.
(giga ls target m)Greedy iterative geodesic ascent (Campbell & Broderick 2018, Alg. 1):
nonnegative weights w over the vectors ls (double arrays of one length),
at most m of them nonzero, with Σ w_n·ls_n close to target.
It works on the unit sphere: each iteration adds the vector whose geodesic from the current direction best aligns with the geodesic to the target's direction, with the step that maximizes the alignment; the weights are scaled optimally at the end. A vector of norm 0 gets weight 0. Returns the weights as a vector. Working storage is allocated once per call.
Greedy iterative geodesic ascent (Campbell & Broderick 2018, Alg. 1): nonnegative weights w over the vectors `ls` (double arrays of one length), at most `m` of them nonzero, with Σ w_n·ls_n close to `target`. It works on the unit sphere: each iteration adds the vector whose geodesic from the current direction best aligns with the geodesic to the target's direction, with the step that maximizes the alignment; the weights are scaled optimally at the end. A vector of norm 0 gets weight 0. Returns the weights as a vector. Working storage is allocated once per call.
(initial state)The state state's run started from: start with its model and
options, the seed included.
The state `state`'s run started from: `start` with its model and `options`, the seed included.
(nnls ls target)Nonnegative least squares (Lawson & Hanson 1974, ch. 23): weights x ≥ 0
over the vectors ls (double arrays of one length) minimizing
‖Σ_j x_j·ls_j − target‖, by the active-set method SciPy's nnls
implements. A vector numerically dependent on the passive ones, or one
that would enter with a nonpositive coefficient, is not added. The
passive set's Householder QR is extended by one reflection per entering
vector and refactorized only when vectors leave. Returns the weights as a
vector.
Nonnegative least squares (Lawson & Hanson 1974, ch. 23): weights x ≥ 0 over the vectors `ls` (double arrays of one length) minimizing ‖Σ_j x_j·ls_j − target‖, by the active-set method SciPy's `nnls` implements. A vector numerically dependent on the passive ones, or one that would enter with a nonpositive coefficient, is not added. The passive set's Householder QR is extended by one reflection per entering vector and refactorized only when vectors leave. Returns the weights as a vector.
(nnls-refit ls target w)GIGA's weights w refitted by nonnegative least squares on their
support, the fully corrective update of Campbell & Beronov (NeurIPS 2019;
build then optimize in Campbell's bayesian-coresets library): the
support stays, its weights become the NNLS solution for
the same target, and the refit is kept only if it does not increase the
residual by more than a relative 1e-12. Weights NNLS sets to zero leave
the support.
GIGA's weights `w` refitted by nonnegative least squares on their support, the fully corrective update of Campbell & Beronov (NeurIPS 2019; `build` then `optimize` in Campbell's bayesian-coresets library): the support stays, its weights become the NNLS solution for the same `target`, and the refit is kept only if it does not increase the residual by more than a relative 1e-12. Weights NNLS sets to zero leave the support.
(options {:keys [particles memory scale seed refit projection-inflation]})The start options that reproduce state's run: with the same batches,
(append-batch …) from (start model (options state)) gives state
again. They include the seed start drew when none was given, so a
replay (after a historical correction, say) is reproducible. A state
without :refit was made before the refit existed and resumes without it.
The `start` options that reproduce `state`'s run: with the same batches, `(append-batch …)` from `(start model (options state))` gives `state` again. They include the seed `start` drew when none was given, so a replay (after a historical correction, say) is reproducible. A state without :refit was made before the refit existed and resumes without it.
(result {:keys [particles approximate?] :as state})Project an SCMC snapshot to the common settled measure API. Projection does not consume the snapshot. Coreset moves and population adaptation do not certify an unbiased normalizer or posterior convergence.
Project an SCMC snapshot to the common settled measure API. Projection does not consume the snapshot. Coreset moves and population adaptation do not certify an unbiased normalizer or posterior convergence.
(scmc {:keys [batches] :as model} & [opts])Run numeric SCMC over :batches using start, append-batch and result. model: :prior-sample (fn [] theta-vector), :prior-log-density (fn [theta]), :log-lik (fn [theta datum]), :batches (lazy sequence of non-empty batches). opts: :particles (1000), :memory (100), :scale (2.38), :seed, :refit (:nnls or :none), :projection-inflation. Returns an EmpiricalMeasure with :coreset, :steps, :max-retained-coreset-size (the largest core-set kept between steps, at most :memory), :max-transient-coreset-size (the largest core-set plus batch a step moved against; :max-coreset-size is its old name), :moves, :accepted, :last-update and :log-normalizer. Streaming memory is bounded by population, coreset and batch; no history of updates is retained. To pause between batches, retain the state returned by append-batch.
Run numeric SCMC over :batches using start, append-batch and result. model: :prior-sample (fn [] theta-vector), :prior-log-density (fn [theta]), :log-lik (fn [theta datum]), :batches (lazy sequence of non-empty batches). opts: :particles (1000), :memory (100), :scale (2.38), :seed, :refit (:nnls or :none), :projection-inflation. Returns an EmpiricalMeasure with :coreset, :steps, :max-retained-coreset-size (the largest core-set kept between steps, at most :memory), :max-transient-coreset-size (the largest core-set plus batch a step moved against; :max-coreset-size is its old name), :moves, :accepted, :last-update and :log-normalizer. Streaming memory is bounded by population, coreset and batch; no history of updates is retained. To pause between batches, retain the state returned by append-batch.
(start {:keys [prior-sample] :as model}
&
[{:keys [particles memory scale seed refit projection-inflation]
:or {particles 1000 memory 100 scale 2.38 refit :nnls}}])Initialize resumable numeric SCMC. model provides :prior-sample,
:prior-log-density and :log-lik. State is a persistent in-memory value,
including model functions; it is not a serialized inference artifact.
opts: :particles (1000), :memory (100), :scale (2.38), :seed, :refit
(:nnls, the default, or :none) and :projection-inflation (none): see the
namespace. Without a :seed, start draws one and records it in the state
(:seed): replay from (initial state) or (start model (options state)), never from the original opts, to reproduce the run.
Initialize resumable numeric SCMC. model provides :prior-sample, :prior-log-density and :log-lik. State is a persistent in-memory value, including model functions; it is not a serialized inference artifact. opts: :particles (1000), :memory (100), :scale (2.38), :seed, :refit (:nnls, the default, or :none) and :projection-inflation (none): see the namespace. Without a :seed, start draws one and records it in the state (:seed): replay from `(initial state)` or `(start model (options state))`, never from the original opts, to reproduce the run.
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |