Upkeep

Upkeep keeps a filter's representation in bounds without meaning to change the distribution much: resampling particles whose weights have degenerated, roughening them after, pruning the improbable particles, components, or cells, or repairing a covariance that rounding has left not positive definite. More...

Namespaces
namespace	Emrys::upkeep
	The upkeep operations, each made by its factory (decisions.md [policy-factories], [upkeep]): the actions resample(), roughen(), pruneBelow(), pruneTail(), pruneToSize(), subdivide(), floorModes(), and repairCovariance(), the triggers when(), whenEss(), and whenSize(), sequence(), and none().

Concepts
concept	Emrys::UpkeepOperation
	An upkeep operation on a State: an action or a trigger, the library's or the caller's own, a function object called as operation(state) that returns whether it changed the state, or the NumericError that stopped it, a WeightError or a GaussianError (decisions.md [upkeep], [user-extension-points]).

Classes
class	Emrys::upkeep::Resample< G, Resampler_, Policy_ >
	Action that resamples a set in proportion to its weights, drawing from the generator G with the resampler Resampler_ (systematic by default) under the execution policy Policy_ (sequential by default), to a given size if one is given and to the set's size otherwise. More...
class	Emrys::upkeep::Roughen< G, Scalar_, Policy_ >
	Action that moves each particle by an independent draw from a Gaussian kernel, to restore the diversity resampling removes: the regularized particle filter. More...
struct	Emrys::upkeep::When< Predicate, Actions >
	Trigger that runs its actions when its predicate holds for the state: the general trigger, of which WhenEss and WhenSize are two. More...
struct	Emrys::upkeep::None
	The upkeep a filter holds when it is given none: it takes any state, changes nothing, and returns false, so that maintain() can be called on every filter (decisions.md [upkeep]). More...
struct	Emrys::upkeep::PruneBelow< Scalar_ >
	Action that removes every point whose normalized probability is below probability, renormalizing the rest; the most probable point is always kept. More...
struct	Emrys::upkeep::PruneTail< Scalar_ >
	Action that removes the least probable points, as many as can be while their combined probability stays below fraction, renormalizing the rest. More...
struct	Emrys::upkeep::PruneToSize
	Action that removes the least probable points until at most maxSize remain, renormalizing the rest. More...
struct	Emrys::upkeep::Subdivide
	Action that splits every point into factor points along each axis, sharing its probability equally. More...
struct	Emrys::upkeep::FloorModes< Scalar_ >
	Action that raises every mode less probable than probability to it, scaling the others down to keep the sum one, so that no mode is ruled out for good. More...
struct	Emrys::upkeep::RepairCovariance< Repair_ >
	Action that repairs every covariance of the state that is not positive definite, by the Repair Repair_ (roots::Ridge by default), so that its density can be read. More...

Typedefs
template<typename Compare, RealScalar Scalar_, typename... Actions>
using	Emrys::upkeep::WhenEss = When<internal::EssTest<Compare, Scalar_>, Actions...>
	Trigger that runs its actions when compare holds between a set's effective sample size and fraction of its size: a When whose predicate is an internal::EssTest.
template<typename Compare, typename... Actions>
using	Emrys::upkeep::WhenSize = When<internal::SizeTest<Compare>, Actions...>
	Trigger that runs its actions when compare holds between a state's number of elements and a limit, such as a mixture's components or a grid's live cells: a When whose predicate is an internal::SizeTest.
template<typename... Actions>
using	Emrys::upkeep::Sequence = When<internal::Always, Actions...>
	Runs its actions in order on the state every time: a When whose predicate always holds, so that a filter's whole upkeep is one value (decisions.md [upkeep]).

Functions
template<std::uniform_random_bit_generator G, typename R = resamplers::Systematic> requires (!std::integral<R>)
constexpr Resample< G, R >	Emrys::upkeep::resample (G &generator, R resampler={})
template<std::uniform_random_bit_generator G, typename R = resamplers::Systematic> requires (!std::integral<R>)
constexpr Resample< G, R >	Emrys::upkeep::resample (G &generator, Eigen::Index size, R resampler={})
template<ExecutionPolicy P, std::uniform_random_bit_generator G, typename R = resamplers::Systematic> requires (!std::integral<R>)
constexpr Resample< G, R, std::remove_cvref_t< P > >	Emrys::upkeep::resample (P &&policy, G &generator, R resampler={})
template<ExecutionPolicy P, std::uniform_random_bit_generator G, typename R = resamplers::Systematic> requires (!std::integral<R>)
constexpr Resample< G, R, std::remove_cvref_t< P > >	Emrys::upkeep::resample (P &&policy, G &generator, Eigen::Index size, R resampler={})
template<std::uniform_random_bit_generator G, typename Value = double> requires std::is_arithmetic_v<Value>
constexpr Roughen< G, internal::DeducedScalar< Value > >	Emrys::upkeep::roughen (G &generator, Value scale=1)
template<ExecutionPolicy P, std::uniform_random_bit_generator G, typename Value = double> requires std::is_arithmetic_v<Value>
constexpr Roughen< G, internal::DeducedScalar< Value >, std::remove_cvref_t< P > >	Emrys::upkeep::roughen (P &&policy, G &generator, Value scale=1)
template<typename Predicate, typename... Actions>
When< Predicate, Actions... >	Emrys::upkeep::when (Predicate predicate, Actions... actions)
template<typename Compare, typename Value, typename... Actions> requires (!ExecutionPolicy<Compare>) && std::is_arithmetic_v<Value> && std::predicate<Compare const &, internal::DeducedScalar <Value>, internal::DeducedScalar<Value>>
WhenEss< Compare, internal::DeducedScalar< Value >, Actions... >	Emrys::upkeep::whenEss (Compare compare, Value fraction, Actions... actions)
template<ExecutionPolicy P, typename Compare, typename Value, typename... Actions> requires std::is_arithmetic_v<Value> && std::predicate<Compare const &, internal::DeducedScalar<Value>, internal::DeducedScalar <Value>>
When< internal::EssTest< Compare, internal::DeducedScalar< Value >, std::remove_cvref_t< P > >, Actions... >	Emrys::upkeep::whenEss (P &&policy, Compare compare, Value fraction, Actions... actions)
template<typename Compare, typename... Actions> requires std::predicate<Compare const &, std::ptrdiff_t, std::ptrdiff_t>
WhenSize< Compare, Actions... >	Emrys::upkeep::whenSize (Compare compare, std::ptrdiff_t limit, Actions... actions)
template<typename... Actions>
Sequence< Actions... >	Emrys::upkeep::sequence (Actions... actions)
constexpr None	Emrys::upkeep::none ()
template<typename Value> requires std::is_arithmetic_v<Value>
constexpr PruneBelow< internal::DeducedScalar< Value > >	Emrys::upkeep::pruneBelow (Value probability)
template<typename Value> requires std::is_arithmetic_v<Value>
constexpr PruneTail< internal::DeducedScalar< Value > >	Emrys::upkeep::pruneTail (Value fraction)
constexpr PruneToSize	Emrys::upkeep::pruneToSize (std::ptrdiff_t maxSize)
constexpr Subdivide	Emrys::upkeep::subdivide (std::ptrdiff_t factor=2)
template<typename Value> requires std::is_arithmetic_v<Value>
constexpr FloorModes< internal::DeducedScalar< Value > >	Emrys::upkeep::floorModes (Value probability)
template<Repair R = roots::Ridge<>>
constexpr RepairCovariance< R >	Emrys::upkeep::repairCovariance (R repair={})

Detailed Description

Upkeep keeps a filter's representation in bounds without meaning to change the distribution much: resampling particles whose weights have degenerated, roughening them after, pruning the improbable particles, components, or cells, or repairing a covariance that rounding has left not positive definite.

The filters never do it on their own; the caller applies it to the filter's state() where it fits the problem, such as once after the last update before a prediction. Upkeep is not a reduction policy, which acts inside an update on the branches of one measurement (decisions.md [reduction-policies]); upkeep acts between steps on the whole state.

Every action leaves a state of the type it found, since the filter fixed that type for its cost (a shared covariance, a regular grid) and state() hands out a reference to it (decisions.md [rao-blackwellized-core]). Within the type it may change the size: the particles, components, or cells a prune leaves, the particles a Resample draws, a grid's cells after Subdivide. What changes the type, such as drawSamples() from a mixture, fitMixture() from particles, or collapsing a mixture into one Gaussian, is a conversion the caller makes outside the filter.

Each operation applies to the states with the members it calls, and UpkeepOperation answers whether it does (Prune is all three prunes):

State, and its filter	Resample	Roughen	Prune	Subdivide	Floor	Repair
GaussianParams: KalmanFilter						yes
ParticleSet: ParticleFilter	yes	yes	yes
ParticleGaussianParams: RbParticleFilter	yes	yes	yes
MixtureParams of Gaussians: MixtureFilter			yes			yes
MixtureParams of hybrids: MixtureFilter			yes		yes	yes
HybridGaussianParams: ImmFilter, AmmFilter					yes	yes
GridGaussianParams, regular: the point-mass filters			yes	yes
GridGaussianParams of given points			yes
CategoricalParams: HiddenMarkovFilter					yes

WhenSize needs only size(), and WhenEss ess(), which the particle states have. A grid isn't resampled, since two copies of a cell would evolve identically. Of the Gaussian forms only the covariance form repairs: the square-root form refuses a repair at compile time, and the information forms have none.

No action merges or splits mixture components (decisions.md [upkeep]). How best to search for the merges to make depends on the use and its hardware, a software engineering choice and not a mathematical one, so the caller writes that action from MixtureParams::merged(), merge(), and the divergences (see Divergences); examples/gaussian_mixture.cpp merges by Runnalls' cost. The literature has no rule for splitting that the library takes up (decisions.md [splitting-hooks]).

Each upkeep object is a function object called with the state alone. It returns whether it changed the state, or a NumericError: a WeightError if the weights are invalid, or a GaussianError if a covariance can't be repaired. Actions do the work unconditionally, and each the library names leaves the state unchanged when it returns an error. Triggers decide whether to run the actions they hold, in order, on the same state; a trigger stops at the first error and returns it, and the actions that ran before it keep their effect (decisions.md [upkeep]), so a caller who needs all or nothing copies the state before the call. An action returns true when it did its work and false when the work would have been nothing: a prune that removed nothing, Subdivide by one, Roughen by zero, FloorModes with no mode below the floor, RepairCovariance on covariances that factorize. Resample returns true even on equal weights, since it redraws the particles. What else an action needs is given to its factory: Resample and Roughen hold a reference to the random generator they draw from, which must outlive them, and a caller's action captures what it needs.

An execution policy, when wanted, is given to the factory too, first, as it comes before the range in a standard algorithm (see Execution policies): Resample and Roughen run their loops under it, and whenEss(policy, ...) takes the effective sample size under it. The other actions run sequentially and take none.

Upkeep runs on the filter's state, which allocates through its allocator (decisions.md [allocation]). Under execution::sequential, Resample to a size within the set's capacity, Roughen on a ParticleSet, the prunes once the state's capacity is set, and FloorModes allocate nothing. Subdivide allocates the larger grid, Roughen on a Rao-Blackwellized state a copy of its particle set, and RepairCovariance a copy of each covariance it repairs. Under another policy the standard algorithms allocate, as [execution-policies] allows.

auto const resample = upkeep::whenEss(std::less{}, 0.5, upkeep::resample(rng), upkeep::roughen(rng));  // particles
resample(particleFilter.state());
auto const inParallel = upkeep::whenEss(std::execution::par, std::less{}, 0.5,
                                        upkeep::resample(std::execution::par, rng),
                                        upkeep::roughen(std::execution::par, rng));
inParallel(particleFilter.state());
auto const thin = upkeep::whenSize(std::greater{}, 4096, upkeep::pruneTail(1e-6));  // grid cells
thin(pointMassFilter.state());
auto const prune = upkeep::pruneBelow(1e-6);  // mixture components
prune(mixtureFilter.state());
auto const bound = upkeep::whenSize(std::greater{}, 64, upkeep::pruneToSize(32));  // or particles
bound(mixtureFilter.state());
auto const repair = upkeep::repairCovariance();  // a Gaussian, as a Kalman filter's
repair(kalmanFilter.state());

Actions: Resample, Roughen, PruneBelow, PruneTail, PruneToSize, Subdivide, FloorModes, RepairCovariance. Triggers: When, which runs its actions when a predicate of the state holds, and WhenEss and WhenSize, the two Whens the library names, each testing what it is named for with a comparator given first, a standard one such as std::less or the caller's own. A trigger runs a caller's action too: any function object of the state that returns std::expected<bool, WeightError>. A Sequence runs its actions every time, so that a filter's whole upkeep is one value.

Every filter holds one upkeep, given last to its constructor and None unless given, and runs it on its state when the caller calls maintain():

auto filter = ParticleFilter{model, initial, upkeep::whenEss(std::less{}, 0.5, upkeep::resample(rng))};
(void)filter.update(fix);
(void)filter.maintain();   // the same as filter.upkeep()(filter.state())

Resampling when the effective sample size falls is the sequential importance resampling of Arulampalam et al. (2002), §V-A, Algorithm 3; roughening after it is the regularized particle filter of Musso, Oudjane, and Le Gland (2001), as given in Arulampalam et al. (2002), §V-B3, Algorithm 6, with a Gaussian kernel; and the floor on mode probabilities is Athans et al. (1977).

Typedef Documentation

Sequence

template<typename... Actions>

using Emrys::upkeep::Sequence = When<internal::Always, Actions...>

Runs its actions in order on the state every time: a When whose predicate always holds, so that a filter's whole upkeep is one value (decisions.md [upkeep]).

It stops at the first action that returns an error and returns it; the actions that ran before it keep their effect. It returns whether any action changed the state.

auto filter = PointMassFilter{grid, upkeep::sequence(upkeep::pruneBelow(1e-6),
                                                     upkeep::whenSize(std::less{}, 100, upkeep::subdivide(2)))};
(void)filter.update(range);
(void)filter.maintain();   // pruned, then refined if fewer than 100 cells are left

WhenEss

template<typename Compare, RealScalar Scalar_, typename... Actions>

using Emrys::upkeep::WhenEss = When<internal::EssTest<Compare, Scalar_>, Actions...>

Trigger that runs its actions when compare holds between a set's effective sample size and fraction of its size: a When whose predicate is an internal::EssTest.

The comparator comes first and is required, so the direction of the test is written at the call: upkeep::whenEss(std::less{}, 0.5, ...) runs the actions when the effective sample size is below half the size. Any predicate of two scalars serves as the comparator, the caller's own included; it is called as compare(ess, threshold), the effective sample size first and fraction times the size second, both in the state's scalar.

The state is anything with size() and ess() returning an std::expected, such as a ParticleSet, and the trigger returns the WeightError of ess(). Usually its actions start with a Resample. Made with an execution policy first, whenEss(policy, compare, fraction, ...), it takes the effective sample size under the policy if the state can; its actions take their own.

auto const resampling = upkeep::whenEss(std::less{}, 0.5, upkeep::resample(rng), upkeep::roughen(rng, 0.25));
resampling(filter.state());

Scalar_ is the type of the fraction, deduced from the one given (upkeep::whenEss(std::less{}, 0.5f, ...) holds a float); the test runs in the state's scalar. The fraction isn't checked: above one the trigger runs at every call, and at zero or below never. The alias names the trigger without a policy; with one it is a When of an internal::EssTest that holds the policy.

WhenSize

template<typename Compare, typename... Actions>

using Emrys::upkeep::WhenSize = When<internal::SizeTest<Compare>, Actions...>

Trigger that runs its actions when compare holds between a state's number of elements and a limit, such as a mixture's components or a grid's live cells: a When whose predicate is an internal::SizeTest.

The comparator comes first and is required, so the direction of the test is written at the call. upkeep::whenSize(std::greater{}, 32, reduce), with reduce a caller's action that merges a mixture down to 16 components, merges whenever there are more than 32, so the work is done in batches rather than at every step (examples/gaussian_mixture.cpp). upkeep::whenSize(std::less{}, 64, upkeep::subdivide(2)) refines a grid whenever pruning has left fewer than 64 cells; nothing there bounds how fine the grid becomes, and the caller stops refining when the resolution is enough. Any predicate of two std::ptrdiff_t serves as the comparator, the caller's own included; it is called as compare(size, limit).

Function Documentation

floorModes()

template<typename Value>
requires std::is_arithmetic_v<Value>

FloorModes< internal::DeducedScalar< Value > > Emrys::upkeep::floorModes ( Value probability )

nodiscardconstexpr

Returns

a FloorModes action raising every mode less probable than probability to it, held in the scalar it is written in (floorModes(1e-3f) holds a float)

none()

None Emrys::upkeep::none ( )

nodiscardconstexpr

Returns

the upkeep None, which does nothing

pruneBelow()

template<typename Value>
requires std::is_arithmetic_v<Value>

PruneBelow< internal::DeducedScalar< Value > > Emrys::upkeep::pruneBelow ( Value probability )

nodiscardconstexpr

Returns

a PruneBelow action removing the points less probable than probability, held in the scalar it is written in (pruneBelow(1e-4f) holds a float)

pruneTail()

template<typename Value>
requires std::is_arithmetic_v<Value>

PruneTail< internal::DeducedScalar< Value > > Emrys::upkeep::pruneTail ( Value fraction )

nodiscardconstexpr

Returns

a PruneTail action removing the least probable points while their combined probability stays below fraction, held in the scalar it is written in (pruneTail(1e-3f) holds a float)

pruneToSize()

PruneToSize Emrys::upkeep::pruneToSize ( std::ptrdiff_t maxSize )

nodiscardconstexpr

Returns

a PruneToSize action removing the least probable points until at most maxSize remain

repairCovariance()

template<Repair R = roots::Ridge<>>

RepairCovariance< R > Emrys::upkeep::repairCovariance ( R repair = {} )

nodiscardconstexpr

Returns

a RepairCovariance action repairing each covariance that is not positive definite by repair, roots::ridge() by default

resample() [1/4]

template<std::uniform_random_bit_generator G, typename R = resamplers::Systematic>
requires (!std::integral<R>)

Resample< G, R > Emrys::upkeep::resample ( G & generator, Eigen::Index size, R resampler = {} )

nodiscardconstexpr

Returns

a Resample action drawing from generator with resampler, systematic by default, that resamples to size particles, which must be positive

resample() [2/4]

template<std::uniform_random_bit_generator G, typename R = resamplers::Systematic>
requires (!std::integral<R>)

Resample< G, R > Emrys::upkeep::resample ( G & generator, R resampler = {} )

nodiscardconstexpr

Returns

a Resample action drawing from generator with resampler, systematic by default (see Resamplers), that keeps the state's size

resample() [3/4]

template<ExecutionPolicy P, std::uniform_random_bit_generator G, typename R = resamplers::Systematic>
requires (!std::integral<R>)

Resample< G, R, std::remove_cvref_t< P > > Emrys::upkeep::resample ( P && policy, G & generator, Eigen::Index size, R resampler = {} )

nodiscardconstexpr

Returns

a Resample action as resample(generator, size, resampler) makes, under policy (see Execution policies)

resample() [4/4]

template<ExecutionPolicy P, std::uniform_random_bit_generator G, typename R = resamplers::Systematic>
requires (!std::integral<R>)

Resample< G, R, std::remove_cvref_t< P > > Emrys::upkeep::resample ( P && policy, G & generator, R resampler = {} )

nodiscardconstexpr

Returns

a Resample action as resample(generator, resampler) makes, under policy (see Execution policies)

roughen() [1/2]

template<std::uniform_random_bit_generator G, typename Value = double>
requires std::is_arithmetic_v<Value>

Roughen< G, internal::DeducedScalar< Value > > Emrys::upkeep::roughen ( G & generator, Value scale = 1 )

nodiscardconstexpr

Returns

a Roughen action drawing from generator a kernel of covariance scale times the bandwidth, 1 by default, held in the scalar it is written in (roughen(rng, 0.25f) holds a float; an integer stands for double)

roughen() [2/2]

template<ExecutionPolicy P, std::uniform_random_bit_generator G, typename Value = double>
requires std::is_arithmetic_v<Value>

Roughen< G, internal::DeducedScalar< Value >, std::remove_cvref_t< P > > Emrys::upkeep::roughen ( P && policy, G & generator, Value scale = 1 )

nodiscardconstexpr

Returns

a Roughen action as roughen(generator, scale) makes, under policy (see Execution policies)

sequence()

template<typename... Actions>

Sequence< Actions... > Emrys::upkeep::sequence ( Actions... actions )

nodiscard

Returns

a Sequence running actions, in order, at every call

subdivide()

Subdivide Emrys::upkeep::subdivide ( std::ptrdiff_t factor = 2 )

nodiscardconstexpr

Returns

a Subdivide action splitting every point into factor points along each axis, 2 by default

when()

template<typename Predicate, typename... Actions>

When< Predicate, Actions... > Emrys::upkeep::when ( Predicate predicate, Actions... actions )

nodiscard

Returns

a When trigger running actions, in order, when predicate holds for the state

whenEss() [1/2]

template<typename Compare, typename Value, typename... Actions>
requires (!ExecutionPolicy<Compare>) && std::is_arithmetic_v<Value> && std::predicate<Compare const &, internal::DeducedScalar
<Value>, internal::DeducedScalar<Value>>

WhenEss< Compare, internal::DeducedScalar< Value >, Actions... > Emrys::upkeep::whenEss ( Compare compare, Value fraction, Actions... actions )

nodiscard

Returns

a WhenEss trigger running actions, in order, when compare holds between the effective sample size and fraction of the size, holding the fraction in the scalar it is written in (whenEss(std::less{}, 0.5f, ...) holds a float)

whenEss() [2/2]

template<ExecutionPolicy P, typename Compare, typename Value, typename... Actions>
requires std::is_arithmetic_v<Value> && std::predicate<Compare const &, internal::DeducedScalar<Value>, internal::DeducedScalar
<Value>>

When< internal::EssTest< Compare, internal::DeducedScalar< Value >, std::remove_cvref_t< P > >, Actions... > Emrys::upkeep::whenEss ( P && policy, Compare compare, Value fraction, Actions... actions )

nodiscard

Returns

a trigger as whenEss(compare, fraction, actions...) makes, taking the effective sample size under policy (see Execution policies)

whenSize()

template<typename Compare, typename... Actions>
requires std::predicate<Compare const &, std::ptrdiff_t, std::ptrdiff_t>

WhenSize< Compare, Actions... > Emrys::upkeep::whenSize ( Compare compare, std::ptrdiff_t limit, Actions... actions )

nodiscard

Returns

a WhenSize trigger running actions, in order, when compare holds between the number of elements and limit