ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
MonteCarloSampler.h
Go to the documentation of this file.
1/**
2 * @file MonteCarloSampler.h
3 * @brief Monte Carlo sampling over a @c GenericCircuit, RV-aware.
4 *
5 * Drop-in replacement for @c BooleanCircuit::monteCarlo for circuits
6 * that contain continuous random variables (@c gate_rv) or arithmetic
7 * over RVs (@c gate_arith). Operates directly on the
8 * @c GenericCircuit produced by @c CircuitFromMMap, so the
9 * BoolExpr-semiring translation that drops non-Boolean gates is not
10 * needed.
11 *
12 * Gate handling:
13 * - @c gate_input (and @c gate_update) – Bernoulli draw at @c getProb,
14 * memoised per iteration (so the same input feeding two children
15 * produces the same draw).
16 * - @c gate_plus / @c gate_times / @c gate_monus – Boolean OR / AND /
17 * AND-NOT.
18 * - @c gate_zero / @c gate_one – false / true.
19 * - @c gate_cmp with scalar (@c gate_rv / @c gate_arith / @c gate_value)
20 * children – compare two scalar samples per the comparison-operator
21 * OID stored in @c info1. Aggregate-vs-constant @c gate_cmp gates
22 * from HAVING semantics are handled by the existing
23 * @c BooleanCircuit path and are not reached here.
24 * - @c gate_value – parse @c extra as @c float8.
25 * - @c gate_rv – fresh draw from the distribution serialised in
26 * @c extra (memoised per iteration so the SAME RV inside an
27 * arithmetic expression uses the same draw, per the thesis's
28 * SampleOne).
29 * - @c gate_arith – recurse on scalar children, combine per the
30 * operator tag in @c info1 (@c provsql_arith_op enum: PLUS / TIMES
31 * are n-ary; MINUS / DIV are binary; NEG is unary).
32 *
33 * The RNG is seeded from the @c provsql.monte_carlo_seed GUC: zero
34 * (default) seeds non-deterministically from @c std::random_device,
35 * any other value is a literal seed shared across the Bernoulli and
36 * continuous paths so a single GUC pins the whole computation.
37 */
38#ifndef PROVSQL_MONTE_CARLO_SAMPLER_H
39#define PROVSQL_MONTE_CARLO_SAMPLER_H
40
41#include <optional>
42#include <random>
43#include <utility>
44#include <vector>
45
46#include "GenericCircuit.h"
47
48extern "C" {
49#include "provsql_utils.h"
50}
51
52namespace provsql {
53
54/**
55 * @brief The shared Monte Carlo generator, seeded from the
56 * @c provsql.monte_carlo_seed GUC (@c -1 = non-deterministic from
57 * @c std::random_device).
58 *
59 * Every sampling entry point in this file seeds through here; exposed so
60 * closed-form paths that still need draws (the conjugate-posterior exact
61 * sampler behind @c rv_sample) share the same pinned-seed reproducibility.
62 */
63std::mt19937_64 seedRng();
64
65/**
66 * @brief Run Monte Carlo on a circuit that may contain @c gate_rv leaves.
67 *
68 * @param gc The circuit (loaded from the mmap store via
69 * @c CircuitFromMMap).
70 * @param root Gate to evaluate as a Boolean expression.
71 * @param samples Number of independent worlds to sample.
72 * @return Estimated probability that @p root is true.
73 *
74 * @throws CircuitException on malformed circuits (unknown gate kind in
75 * a Boolean position, malformed @c extra, unknown comparison
76 * operator, etc.).
77 */
78double monteCarloRV(const GenericCircuit &gc, gate_t root, unsigned samples);
79
80/**
81 * @brief Whole-circuit @c (eps,delta)-relative probability via the
82 * Dagum-Karp-Luby-Ross stopping rule.
83 *
84 * The general-Bernoulli case of @c BooleanCircuit::karpLubyStopping, driven by
85 * the RV-aware @c Sampler's @c evalBool rather than by DNF coverage trials, so
86 * it applies to ANY circuit the sampler can evaluate (plain Boolean, continuous
87 * @c gate_rv, and HAVING @c gate_cmp / @c gate_agg) -- the universal relative
88 * estimator. Draws whole-circuit worlds until the success count reaches the
89 * threshold @c Y1 = 1 + (1+eps)*4*(e-2)*ln(2/delta)/eps^2, then returns
90 * @c Y1/N: a relative @c (eps,delta) approximation of @c Pr[root]. The sample
91 * count @c N adapts to the true @c Pr[root] (expected @c Y1/Pr[root]), so the
92 * cost is polynomial precisely when @c Pr[root] is at least @c 1/poly.
93 *
94 * Sampling stops early at @p max_samples worlds; @p reached_target is then
95 * @c false and the return is the plain unbiased @c success/N mean over the
96 * spent budget (the relative target was not met -- the caller reports the
97 * weaker, additive guarantee actually achieved).
98 *
99 * @param gc The circuit.
100 * @param root Gate to evaluate as a Boolean event.
101 * @param eps Target relative error (in @c (0,1]).
102 * @param delta Target failure probability (in @c (0,1)).
103 * @param max_samples Hard cap on the number of worlds drawn.
104 * @param samples_used Output: worlds actually drawn.
105 * @param reached_target Output: whether the threshold was reached before the
106 * cap (i.e. the relative guarantee holds).
107 * @return The probability estimate.
108 */
109double monteCarloRVStopping(const GenericCircuit &gc, gate_t root,
110 double eps, double delta,
111 unsigned long max_samples,
112 unsigned long &samples_used,
113 bool &reached_target);
114
115/**
116 * @brief Walk the circuit reachable from @p root looking for any @c gate_rv.
117 *
118 * Used by @c probability_evaluate to dispatch between the existing
119 * @c BooleanCircuit path and the RV-aware sampler in this file.
120 */
121bool circuitHasRV(const GenericCircuit &gc, gate_t root);
122
123/**
124 * @brief Whether a @c gate_fixpoint (a row of a recursion on cyclic data) is
125 * reachable from @p root.
126 *
127 * Such a circuit is sampled by solving its equation systems in each world,
128 * without the Boolean expansion of the BoolExpr translation, whose size is
129 * the number of rows of a cycle times the number of its terms. False where
130 * a @c gate_mulinput is reachable too: the sampler does not draw blocks, so
131 * such a circuit keeps the Boolean expansion, which rewrites them.
132 */
133bool circuitHasFixpoint(const GenericCircuit &gc, gate_t root);
134
135/**
136 * @brief Whether a surviving @c gate_agg exists and every one is sample-faithful
137 * (@c SUM / @c AVG / @c MIN / @c MAX / @c COUNT -- every aggregate the
138 * sampler reproduces exactly).
139 *
140 * A @c gate_agg the exact closed-form / marginal-vector pre-passes did not fold
141 * into a Bernoulli @c gate_input marks a HAVING aggregate comparator whose exact
142 * resolution needs @c provsql_having's threshold-lineage expansion -- which does
143 * not terminate in practice for a large-magnitude / large-support aggregate
144 * (the dense @c kMaxSumRange and sparse @c kMaxSumSupport caps exceeded). For
145 * an @c (eps,delta) request @c probability_evaluate uses this to route the
146 * circuit straight to the world-sampler (the @c gate_agg arm of @c evalScalar)
147 * -- a sound FPRAS for the apx-safe corner of the HAVING trichotomy -- instead
148 * of attempting the non-terminating Boolean expansion.
149 *
150 * The sampler's @c gate_agg arm pushes each kept contributor's value into the
151 * matching @c Aggregator, reproducing SQL semantics exactly: the value gate is
152 * the row's contribution (the summed term for @c SUM; the 0/1 indicator for
153 * @c COUNT, 0 for a NULL row so @c count(x) does not count NULLs; the compared
154 * value for @c AVG / @c MIN / @c MAX), so NULL rows are handled and a
155 * contributor-free iteration finalises to the value the exact evaluator uses
156 * (0 for a @e scalar @c COUNT, whose single row exists over empty input;
157 * no value -> comparison false for every other case, SQL's NULL or a grouped
158 * aggregation's absent row), and @c gate_arith over them is covered too.
159 *
160 * @c COUNT reaches this arm only as a scalar aggregation. Its value-support
161 * is small (0/1 per row), so a grouped @c COUNT comparison is resolved before
162 * any sampler runs -- by @c RangeCheck when the bounds decide it, otherwise by
163 * @c provsql_having's world enumeration -- and both of those already exclude
164 * the empty world. The grouped arm below is nonetheless written to decline
165 * such a world rather than report 0, so the aggregate stays correct if the
166 * routing ever sends one here.
167 */
168bool circuitHasUnresolvedSampleableAgg(const GenericCircuit &gc, gate_t root);
169
170/**
171 * @brief Whether a contribution of an aggregate is itself an aggregate result
172 * (a @c gate_semimod whose M side is no @c gate_value).
173 *
174 * The value of such a contribution is one per possible world, so the closed
175 * forms and the Boolean view of a comparison over it decline: the routes that
176 * resolve it are the exact enumeration of the worlds of the inputs and this
177 * sampler.
178 */
179bool circuitHasNestedAggValue(const GenericCircuit &gc, gate_t root);
180
181/**
182 * @brief Estimate the joint distribution of @p cmps via Monte Carlo.
183 *
184 * For each of @p samples worlds, samples the underlying continuous
185 * island once (shared @c gate_rv leaves use the same per-iteration
186 * draw, per @c monteCarloRV's evalScalar) and evaluates each
187 * comparator in @p cmps; the @c k = @p cmps.size() resulting bits
188 * form a single word @c w with bit @c i = result of @c cmps[i]. The
189 * returned vector has size @c 2^k; entry @c w is the empirical
190 * probability that the joint outcome @c w occurred.
191 *
192 * Used by the multi-cmp half of the hybrid evaluator's island
193 * decomposer to inline a categorical distribution over the @c k cmps
194 * that share an island; @p cmps must all sit over a continuous
195 * island whose scalar evaluation reuses common @c gate_rv leaves so
196 * the cmp draws are correctly correlated.
197 *
198 * @c k is capped at 30 (the result vector size is @c 2^30) to keep
199 * memory bounded; the decomposer enforces a much tighter cap
200 * (@c k_max in @c HybridEvaluator.cpp) so this is purely a safety
201 * limit. Throws @c CircuitException above the cap.
202 *
203 * @param gc The circuit.
204 * @param cmps The comparators jointly evaluated.
205 * @param samples Number of independent worlds.
206 * @return Vector of joint probabilities, indexed by the bit
207 * word @c w (bit @c i = @c cmps[i] outcome).
208 */
209std::vector<double> monteCarloJointDistribution(
210 const GenericCircuit &gc,
211 const std::vector<gate_t> &cmps,
212 unsigned samples);
213
214/**
215 * @brief Sample a scalar sub-circuit @p samples times and return the draws.
216 *
217 * @p root must yield a scalar (@c gate_value, @c gate_rv, or @c gate_arith
218 * over scalar children); otherwise a @c CircuitException is thrown. Each
219 * iteration uses a fresh per-iteration memo cache so that repeated
220 * occurrences of the same @c gate_rv UUID inside an arithmetic expression
221 * share their draw within an iteration but not across iterations.
222 *
223 * The RNG is seeded from @c provsql.monte_carlo_seed exactly like
224 * @c monteCarloRV; pinning the GUC makes the returned vector reproducible.
225 *
226 * Used as the universal MC fallback by the analytical evaluators
227 * (@c Expectation, @c HybridEvaluator) when structural shortcuts cannot
228 * decide a sub-expression. Returning the raw draws (rather than a
229 * single statistic) lets callers compute any combination of moments
230 * from a single sampling pass.
231 *
232 * A draw is empty where @p root has no value in the world drawn (an
233 * aggregate over no row, a NULL, a division by zero), which callers skip as
234 * a missing observation; a NaN is a value (a float can hold one, and SQL
235 * computes with it).
236 */
237std::vector<std::optional<double>> monteCarloScalarSamples(
238 const GenericCircuit &gc, gate_t root, unsigned samples);
239
240/** @brief The draws of @p samples that have a value, in order. */
241std::vector<double>
242definedDraws(const std::vector<std::optional<double>> &samples);
243
244/**
245 * @brief The possible worlds of a circuit whose only random sources are
246 * Boolean inputs: the exact alternative to @c monteCarloScalarSamples.
247 *
248 * For each assignment of the inputs reachable from @p root and @p event
249 * (at most @p max_inputs of them) in which @p event holds (when given), its
250 * probability and the value of @p root there (empty where it has none, as
251 * an aggregate over no row). @c std::nullopt when the circuit has another
252 * random source (a @c gate_rv, a mixture, an observation, a
253 * @c gate_mulinput), an input without a probability, or more inputs.
254 */
255std::optional<std::vector<std::pair<double, std::optional<double>>>>
256enumerateScalarWorlds(const GenericCircuit &gc, gate_t root,
257 std::optional<gate_t> event, unsigned max_inputs);
258
259/**
260 * @brief The probability of @p root, exactly, over the possible worlds of the
261 * circuit as it is: the alternative to the Boolean view for a circuit
262 * with comparison or aggregation gates.
263 *
264 * Every assignment of the inputs reachable from @p root (at most
265 * @p max_inputs of them) is evaluated as one world, the comparisons and
266 * aggregates read from the values they take there, and the probabilities of
267 * the worlds where @p root holds are summed. So a rank or a @c HAVING
268 * comparison costs @c 2^n evaluations of the circuit, rather than the
269 * @c 2^contributors Boolean terms its resolution would emit.
270 * @c std::nullopt when the circuit has another random source (a
271 * @c gate_rv, a mixture, an observation, a @c gate_mulinput), an input
272 * without a probability, or more inputs than @p max_inputs.
273 */
274std::optional<double>
275enumerateBooleanProbability(const GenericCircuit &gc, gate_t root,
276 unsigned max_inputs);
277
278/**
279 * @brief Coupled per-iteration draws of two scalar roots.
280 *
281 * Each iteration resets the per-iteration cache once and evaluates both
282 * roots against it, so any stochastic leaf shared between @p root_a and
283 * @p root_b produces a single draw both observe: the returned pairs are
284 * samples from the JOINT distribution of (A, B). Backs the
285 * mutual-information plug-in estimator. A draw is empty where its root has
286 * no value, as in @c monteCarloScalarSamples.
287 */
288std::pair<std::vector<std::optional<double>>,
289 std::vector<std::optional<double>>>
290monteCarloScalarPairSamples(const GenericCircuit &gc, gate_t root_a,
291 gate_t root_b, unsigned samples);
292
293/**
294 * @brief Outcome of a conditional Monte Carlo sampling pass.
295 *
296 * @c accepted holds the @c root values from the iterations where
297 * @c event_root evaluated to @c true (the rest are rejected).
298 * @c attempted is the total number of iterations -- equal to @c samples
299 * unless the pass was interrupted -- so the caller can derive the
300 * empirical acceptance rate as
301 * <tt>accepted.size() / attempted</tt> for diagnostics. An accepted draw
302 * is empty where @c root has no value, as in @c monteCarloScalarSamples.
303 */
305 std::vector<std::optional<double>> accepted;
306 unsigned attempted;
307};
308
309/**
310 * @brief Rejection-sample @p root conditioned on @p event_root.
311 *
312 * For each of @p samples iterations, the shared @c Sampler resets its
313 * per-iteration cache, then:
314 * 1. evaluates @p event_root as a Boolean (populating @c bool_cache_
315 * and @c scalar_cache_ for every @c gate_rv / @c gate_input touched);
316 * 2. if the indicator is @c true, evaluates @p root as a scalar
317 * using the SAME caches, so any shared @c gate_t leaf produces
318 * one draw that the indicator and the value both observe;
319 * 3. otherwise rejects the iteration.
320 *
321 * This coupling is the entire point of routing the conditional path
322 * through one joint circuit: a @c gate_rv reachable from both
323 * @p root and @p event_root has the same @c gate_t and therefore
324 * shares its per-iteration draw between the indicator (which decides
325 * acceptance) and the value (which we record). The accepted draws
326 * are samples from the conditional distribution
327 * @f$X \mid A@f$ where @c X = @p root and @c A = @p event_root.
328 *
329 * @param gc Circuit (typically from @c getJointCircuit).
330 * @param root Scalar gate whose value we sample.
331 * @param event_root Boolean gate that the iteration must satisfy.
332 * @param samples Number of iterations to attempt.
333 */
335 const GenericCircuit &gc, gate_t root, gate_t event_root, unsigned samples);
336
337/**
338 * @brief Outcome of a conditional coupled-pair Monte Carlo pass:
339 * @c xs[i] / @c ys[i] are the two roots' values from the same
340 * accepted iteration. @c attempted as in
341 * @c ConditionalScalarSamples.
342 */
344 std::vector<std::optional<double>> xs;
345 std::vector<std::optional<double>> ys;
346 unsigned attempted;
347};
348
349/**
350 * @brief Rejection-sample the PAIR (@p root_a, @p root_b) conditioned on
351 * @p event_root.
352 *
353 * The pair analogue of @c monteCarloConditionalScalarSamples: per
354 * iteration the indicator is evaluated first, and on acceptance both
355 * scalar roots are evaluated against the SAME per-iteration caches, so
356 * any stochastic leaf shared between the two values and/or the event
357 * produces one draw all three observe. The accepted pairs are samples
358 * from the joint conditional distribution @f$(A, B) \mid E@f$ -- the
359 * input the single-pass covariance / correlation estimators need.
360 */
362 const GenericCircuit &gc, gate_t root_a, gate_t root_b,
363 gate_t event_root, unsigned samples);
364
365/**
366 * @brief Try to draw @p n exact samples from the conditional
367 * distribution of @p root @b given @p event_root via closed-form
368 * truncation, bypassing MC rejection.
369 *
370 * Fires only when @p root is a bare @c gate_rv whose family admits a
371 * closed-form truncation (@c Uniform / @c Exponential / @c Normal)
372 * and @c collectRvConstraints can extract a sound interval from
373 * @p event_root. Other shapes (arith composites, mixtures, Erlang,
374 * un-extractable events) return @c std::nullopt so the caller can fall
375 * back to @c monteCarloConditionalScalarSamples.
376 *
377 * Sampling kernels:
378 * - <b>Uniform(a, b)</b>: @c collectRvConstraints already intersects
379 * with @c [a, b], so the draw is a plain @c U(lo, hi) on the
380 * intersected interval. 100% acceptance.
381 * - <b>Exponential(λ)</b>, one-sided @c X > c: memorylessness yields
382 * @c c + Exp(λ). Two-sided @c lo < X < hi: inverse-CDF via
383 * @c std::log1p / @c std::expm1 for numerical accuracy near the
384 * support boundary.
385 * - <b>Normal(μ, σ)</b>: inverse-CDF transform. Forward CDF uses
386 * @c std::erf (matching @c AnalyticEvaluator::cdfAt); inverse uses
387 * the Beasley-Springer-Moro rational approximation (~1e-7 accuracy,
388 * ample for sampling).
389 *
390 * Empty / degenerate truncations (@c lo >= @c hi after intersection)
391 * also return @c std::nullopt so the caller's MC fallback can emit
392 * its usual "accepted 0" diagnostic.
393 *
394 * The RNG is seeded from @c provsql.monte_carlo_seed identically to
395 * @c monteCarloScalarSamples, so a pinned seed gives reproducible
396 * output on either path.
397 */
398std::optional<std::vector<double>>
400 gate_t event_root, unsigned n);
401
402/**
403 * @brief Outcome of a likelihood-weighting (importance-sampling) pass.
404 *
405 * Latent-variable posterior inference draws latents from the prior via the
406 * forward recursion and weights each draw by the observed leaves' densities
407 * at the data (self-normalised importance sampling; the continuous
408 * generalisation of rejection conditioning, which is the 0/1-weight case).
409 *
410 * @c particles holds one @c (x, w) pair per prior draw with @b positive
411 * weight where the queried root has a value (@c x = that value, @c w = the
412 * product of the evidence factors); the caller derives any weighted posterior statistic
413 * (mean, variance, quantile) from them. @c weight_sum / @c weight_sq_sum
414 * accumulate over @b all @c attempted draws (a zero-weight draw contributes
415 * 0), so @c evidence() is the marginal likelihood @c P(data) and
416 * @c effectiveSampleSize() the ESS diagnostic.
417 */
419 std::vector<std::pair<double, double>> particles; ///< (x, w) with w > 0.
420 double weight_sum = 0.0; ///< Sum of w over all attempted draws.
421 double weight_sq_sum = 0.0; ///< Sum of w^2 over all attempted draws.
422 unsigned attempted = 0; ///< Number of prior draws.
423
424 /// Marginal likelihood P(data): the mean raw importance weight.
425 double evidence() const {
426 return attempted ? weight_sum / static_cast<double>(attempted) : 0.0;
427 }
428 /// Effective sample size (Sum w)^2 / (Sum w^2); 0 when all weights are 0.
429 double effectiveSampleSize() const {
430 return weight_sq_sum > 0.0 ? (weight_sum * weight_sum) / weight_sq_sum : 0.0;
431 }
432};
433
434/**
435 * @brief Self-normalised importance sampling of @p root given @p evidence.
436 *
437 * For each of @p samples prior draws the shared @c Sampler resets its
438 * per-iteration caches, then:
439 * 1. evaluates @p evidence to an importance @b weight (@c evalWeight):
440 * a @c gate_observe contributes its leaf's pdf at the datum, a Boolean
441 * conditioning event contributes a 0/1 weight, a @c gate_times
442 * multiplies its children's weights -- populating @c scalar_cache_ for
443 * every latent the evidence touches;
444 * 2. if the weight is positive, evaluates @p root as a scalar using the
445 * SAME caches, so a latent shared between @p root and @p evidence is
446 * drawn once and the weight and the value observe it jointly;
447 * 3. records the @c (value, weight) particle.
448 *
449 * Coupling the weight and the value through one joint circuit
450 * (@c getJointCircuit) is what makes the shared latent a single @c gate_t;
451 * the particles are then draws from the posterior of @c root given the data.
452 *
453 * @param gc Circuit (typically from @c getJointCircuit).
454 * @param root Scalar gate whose posterior we sample.
455 * @param evidence Evidence circuit (an @c and_agg conjunction of
456 * @c gate_observe / Boolean events).
457 * @param samples Number of prior draws.
458 */
459WeightedPosterior importanceSampleConditional(
460 const GenericCircuit &gc, gate_t root, gate_t evidence, unsigned samples);
461
462/**
463 * @brief Marginal likelihood @c P(data) of @p evidence: the mean raw
464 * importance weight over @p samples prior draws.
465 *
466 * The same quantity rejection conditioning computes as @c P(C), now a
467 * product of the observations' densities. Backs @c provsql.evidence.
468 */
469double importanceEvidence(const GenericCircuit &gc, gate_t evidence,
470 unsigned samples);
471
472/**
473 * @brief Sampling-importance-resampling: draw @p n posterior samples from a
474 * weighted particle set (proportional to weight, with replacement).
475 *
476 * Turns the weighted particles of @c importanceSampleConditional into
477 * (approximately) unweighted posterior draws for @c rv_sample. Returns an
478 * empty vector when there is no positive-weight particle. The RNG is
479 * seeded from @c provsql.monte_carlo_seed, like every other sampling path.
480 */
481std::vector<double> posteriorResample(const WeightedPosterior &post,
482 unsigned n);
483
484/**
485 * @brief Whether the circuit reachable from @p root contains a
486 * @c gate_observe -- the signal that a conditioning event is
487 * continuous-density evidence and must be evaluated by importance
488 * sampling rather than the analytic / rejection conditional paths.
489 */
490bool circuitHasObserve(const GenericCircuit &gc, gate_t root);
491
492} // namespace provsql
493
494#endif // PROVSQL_MONTE_CARLO_SAMPLER_H
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Semiring-agnostic in-memory provenance circuit.
std::optional< std::vector< std::pair< double, std::optional< double > > > > enumerateScalarWorlds(const GenericCircuit &gc, gate_t root, std::optional< gate_t > event, unsigned max_inputs)
The possible worlds of a circuit whose only random sources are Boolean inputs: the exact alternative ...
std::vector< std::optional< double > > monteCarloScalarSamples(const GenericCircuit &gc, gate_t root, unsigned samples)
Sample a scalar sub-circuit samples times and return the draws.
double importanceEvidence(const GenericCircuit &gc, gate_t evidence, unsigned samples)
Marginal likelihood P(data) of evidence: the mean raw importance weight over samples prior draws.
std::optional< double > enumerateBooleanProbability(const GenericCircuit &gc, gate_t root, unsigned max_inputs)
The probability of root, exactly, over the possible worlds of the circuit as it is: the alternative t...
std::pair< std::vector< std::optional< double > >, std::vector< std::optional< double > > > monteCarloScalarPairSamples(const GenericCircuit &gc, gate_t root_a, gate_t root_b, unsigned samples)
Coupled per-iteration draws of two scalar roots.
std::vector< double > posteriorResample(const WeightedPosterior &post, unsigned n)
Sampling-importance-resampling: draw n posterior samples from a weighted particle set (proportional t...
std::vector< double > monteCarloJointDistribution(const GenericCircuit &gc, const std::vector< gate_t > &cmps, unsigned samples)
Estimate the joint distribution of cmps via Monte Carlo.
bool circuitHasNestedAggValue(const GenericCircuit &gc, gate_t root)
Whether a contribution of an aggregate is itself an aggregate result (a gate_semimod whose M side is ...
double monteCarloRVStopping(const GenericCircuit &gc, gate_t root, double eps, double delta, unsigned long max_samples, unsigned long &samples_used, bool &reached_target)
Whole-circuit (eps,delta)-relative probability via the Dagum-Karp-Luby-Ross stopping rule.
std::mt19937_64 seedRng()
The shared Monte Carlo generator, seeded from the provsql.monte_carlo_seed GUC (-1 = non-deterministi...
bool circuitHasUnresolvedSampleableAgg(const GenericCircuit &gc, gate_t root)
Whether a surviving gate_agg exists and every one is sample-faithful (SUM / AVG / MIN / MAX / COUNT –...
ConditionalScalarSamples monteCarloConditionalScalarSamples(const GenericCircuit &gc, gate_t root, gate_t event_root, unsigned samples)
Rejection-sample root conditioned on event_root.
bool circuitHasFixpoint(const GenericCircuit &gc, gate_t root)
Whether a gate_fixpoint (a row of a recursion on cyclic data) is reachable from root.
ConditionalScalarPairSamples monteCarloConditionalScalarPairSamples(const GenericCircuit &gc, gate_t root_a, gate_t root_b, gate_t event_root, unsigned samples)
Rejection-sample the PAIR (root_a, root_b) conditioned on event_root.
double monteCarloRV(const GenericCircuit &gc, gate_t root, unsigned samples)
Run Monte Carlo on a circuit that may contain gate_rv leaves.
std::optional< std::vector< double > > try_truncated_closed_form_sample(const GenericCircuit &gc, gate_t root, gate_t event_root, unsigned n)
Try to draw n exact samples from the conditional distribution of root given event_root via closed-for...
WeightedPosterior importanceSampleConditional(const GenericCircuit &gc, gate_t root, gate_t evidence, unsigned samples)
Self-normalised importance sampling of root given evidence.
std::vector< double > definedDraws(const std::vector< std::optional< double > > &samples)
The draws of samples that have a value, in order.
bool circuitHasRV(const GenericCircuit &gc, gate_t root)
Walk the circuit reachable from root looking for any gate_rv.
bool circuitHasObserve(const GenericCircuit &gc, gate_t root)
Whether the circuit reachable from root contains a gate_observe – the signal that a conditioning even...
Core types, constants, and utilities shared across ProvSQL.
Outcome of a conditional coupled-pair Monte Carlo pass: xs[i] / ys[i] are the two roots' values from ...
std::vector< std::optional< double > > xs
std::vector< std::optional< double > > ys
Outcome of a conditional Monte Carlo sampling pass.
std::vector< std::optional< double > > accepted
Outcome of a likelihood-weighting (importance-sampling) pass.
double weight_sq_sum
Sum of w^2 over all attempted draws.
unsigned attempted
Number of prior draws.
double evidence() const
Marginal likelihood P(data): the mean raw importance weight.
std::vector< std::pair< double, double > > particles
(x, w) with w > 0.
double effectiveSampleSize() const
Effective sample size (Sum w)^2 / (Sum w^2); 0 when all weights are 0.
double weight_sum
Sum of w over all attempted draws.