19#include "utils/uuid.h"
24PG_FUNCTION_INFO_V1(
rv_kl);
42constexpr double kInf = std::numeric_limits<double>::infinity();
44unsigned mc_budget_or_throw(
const std::string &what)
48 throw CircuitException(
49 what +
" has no closed form for this shape and "
50 "provsql.rv_mc_samples = 0 disables the Monte Carlo fallback");
51 return static_cast<unsigned>(n);
68 std::map<double, double> pmf;
69 std::function<double(
double)> pdf;
70 double lo = 0.0, hi = 0.0;
77void collectStochasticLeaves(
const GenericCircuit &gc,
gate_t g,
78 std::set<gate_t> &out, std::set<gate_t> &seen)
80 if (!seen.insert(g).second)
return;
85 collectStochasticLeaves(gc, c, out, seen);
88std::set<gate_t> stochasticLeaves(
const GenericCircuit &gc,
gate_t g)
90 std::set<gate_t> out, seen;
91 collectStochasticLeaves(gc, g, out, seen);
95std::optional<DensityView>
96resolveDensity(
const GenericCircuit &gc,
gate_t g)
103 catch (
const CircuitException &) {
return std::nullopt; }
105 view.discrete =
true;
112 if (!spec)
return std::nullopt;
115 view.discrete =
false;
116 if (!dist->integrationRange(view.lo, view.hi))
return std::nullopt;
117 view.pdf = [dist](
double x) {
return dist->pdf(x); };
125 view.discrete =
true;
126 for (std::size_t i = 1; i < wires.size(); ++i) {
129 catch (
const CircuitException &) {
return std::nullopt; }
130 view.pmf[v] += gc.
getProb(wires[i]);
138 if (wires.size() != 3)
return std::nullopt;
140 const double pi = gc.
getProb(wires[0]);
141 if (std::isnan(pi))
return std::nullopt;
142 auto ax = stochasticLeaves(gc, wires[1]);
143 auto ay = stochasticLeaves(gc, wires[2]);
145 if (ay.count(l))
return std::nullopt;
146 auto vx = resolveDensity(gc, wires[1]);
147 auto vy = resolveDensity(gc, wires[2]);
148 if (!vx || !vy)
return std::nullopt;
149 if (vx->discrete && vy->discrete) {
151 view.discrete =
true;
152 for (
const auto &[v, p] : vx->pmf) view.pmf[v] += pi * p;
153 for (
const auto &[v, p] : vy->pmf) view.pmf[v] += (1.0 - pi) * p;
156 if (!vx->discrete && !vy->discrete) {
158 view.discrete =
false;
159 view.lo = std::min(vx->lo, vy->lo);
160 view.hi = std::max(vx->hi, vy->hi);
161 auto fx = vx->pdf, fy = vy->pdf;
162 view.pdf = [pi, fx, fy](
double x) {
163 const double a = fx(x), b = fy(x);
164 if (std::isnan(a) || std::isnan(b))
165 return std::numeric_limits<double>::quiet_NaN();
166 return pi * a + (1.0 - pi) * b;
178double entropyOfView(
const DensityView &view)
182 for (
const auto &[v, p] : view.pmf)
183 if (p > 0.0) h -= p * std::log(p);
188 const double f = view.pdf(x);
189 if (std::isnan(f)) return std::numeric_limits<double>::quiet_NaN();
190 if (f <= 0.0) return 0.0;
191 return -f * std::log(f);
200double entropyFromSamples(
const std::vector<std::optional<double>> &draws,
201 const std::string &what)
204 const std::size_t m = xs.size();
208 if (std::isnan(v))
return v;
210 for (
double v : xs) mean += v;
211 mean /=
static_cast<double>(m);
213 for (
double v : xs) var += (v - mean) * (v - mean);
214 var /=
static_cast<double>(m);
215 const double sd = std::sqrt(var);
216 if (!(sd > 0.0))
return 0.0;
218 3.49 * sd / std::cbrt(
static_cast<double>(m));
219 const auto [mn_it, mx_it] = std::minmax_element(xs.begin(), xs.end());
220 const double lo = *mn_it, hi = *mx_it;
221 const std::size_t nbins =
222 std::max<std::size_t>(1,
static_cast<std::size_t
>((hi - lo) / h) + 1);
223 std::vector<std::size_t> counts(nbins, 0);
224 for (
double v : xs) {
225 std::size_t b =
static_cast<std::size_t
>((v - lo) / h);
226 if (b >= nbins) b = nbins - 1;
230 for (std::size_t c : counts) {
231 if (c == 0)
continue;
232 const double p =
static_cast<double>(c) /
static_cast<double>(m);
233 H -= p * std::log(p / h);
241 std::optional<gate_t> event)
244 if (
auto view = resolveDensity(gc, root)) {
245 const double h = entropyOfView(*view);
246 if (!std::isnan(h))
return h;
248 return entropyFromSamples(
258 view.discrete =
false;
259 if (dist->integrationRange(view.lo, view.hi)) {
260 view.pdf = [dist](
double x) {
return dist->pdf(x); };
261 const double h = entropyOfView(view);
262 if (!std::isnan(h))
return h;
269 gc, root, *event, mc_budget_or_throw(
"conditional entropy"));
270 if (cs.accepted.empty())
272 "conditional entropy: the conditioning event was never satisfied "
273 "in the Monte Carlo pass (probability ~ 0?)");
274 return entropyFromSamples(std::move(cs.accepted),
"conditional entropy");
279 auto vp = resolveDensity(gc, p_root);
280 auto vq = resolveDensity(gc, q_root);
283 "kl: both arguments must resolve to a closed-form density (a bare "
284 "distribution constructor, a constant, a categorical, or a mixture "
285 "of those with independent arms); arithmetic composites and "
286 "conditioned variables are not supported");
288 if (vp->discrete && vq->discrete) {
290 for (
const auto &[v, p] : vp->pmf) {
291 if (p <= 0.0)
continue;
292 auto it = vq->pmf.find(v);
293 const double q = (it == vq->pmf.end()) ? 0.0 : it->second;
294 if (q <= 0.0)
return kInf;
295 kl += p * std::log(p / q);
299 if (vp->discrete != vq->discrete)
307 const double fp = vp->pdf(x);
308 if (std::isnan(fp)) return std::numeric_limits<double>::quiet_NaN();
309 if (fp <= 0.0) return 0.0;
310 const double fq = vq->pdf(x);
311 if (std::isnan(fq)) return std::numeric_limits<double>::quiet_NaN();
312 if (fq <= 0.0) return kInf;
313 return fp * std::log(fp / fq);
320 if (x_root == y_root) {
323 if (
auto view = resolveDensity(gc, x_root))
324 if (view->discrete)
return entropyOfView(*view);
330 auto lx = stochasticLeaves(gc, x_root);
331 auto ly = stochasticLeaves(gc, y_root);
334 if (ly.count(l)) { shared =
true;
break; }
335 if (!shared)
return 0.0;
341 const unsigned m0 = mc_budget_or_throw(
"mutual_information");
343 std::vector<std::pair<double, double>> pairs;
344 pairs.reserve(xs.size());
345 for (std::size_t i = 0; i < xs.size(); ++i)
346 if (xs[i] && ys[i]) {
348 if (std::isnan(*xs[i]) || std::isnan(*ys[i]))
349 return std::numeric_limits<double>::quiet_NaN();
350 pairs.emplace_back(*xs[i], *ys[i]);
352 const std::size_t m = pairs.size();
356 double xlo = pairs[0].first, xhi = xlo, ylo = pairs[0].second, yhi = ylo;
357 for (
const auto &[a, b] : pairs) {
358 xlo = std::min(xlo, a); xhi = std::max(xhi, a);
359 ylo = std::min(ylo, b); yhi = std::max(yhi, b);
361 if (!(xhi > xlo) || !(yhi > ylo))
364 const std::size_t B = std::max<std::size_t>(
365 4,
static_cast<std::size_t
>(std::cbrt(
static_cast<double>(m))));
366 auto binOf = [B](
double v,
double lo,
double hi) {
367 auto b =
static_cast<std::size_t
>((v - lo) / (hi - lo)
368 *
static_cast<double>(B));
369 return (b >= B) ? B - 1 : b;
371 std::vector<std::size_t> joint(B * B, 0), margx(B, 0), margy(B, 0);
372 for (
const auto &[a, b] : pairs) {
373 const std::size_t bx = binOf(a, xlo, xhi), by = binOf(b, ylo, yhi);
374 ++joint[bx * B + by];
378 const double dm =
static_cast<double>(m);
380 for (std::size_t bx = 0; bx < B; ++bx)
381 for (std::size_t by = 0; by < B; ++by) {
382 const std::size_t c = joint[bx * B + by];
383 if (c == 0)
continue;
384 const double pij =
static_cast<double>(c) / dm;
385 const double px =
static_cast<double>(margx[bx]) / dm;
386 const double py =
static_cast<double>(margy[by]) / dm;
387 mi += pij * std::log(pij / (px * py));
389 return std::max(mi, 0.0);
408 gate_t root_gate, event_gate;
411 std::optional<gate_t> event_opt;
413 event_opt = event_gate;
416 return Float8GetDatum(
422 }
catch (
const std::exception &e) {
450 }
catch (
const std::exception &e) {
473 return Float8GetDatum(
479 }
catch (
const std::exception &e) {
GenericCircuit getJointCircuit(const std::vector< pg_uuid_t > &tokens, std::vector< gate_t > &gates)
Multi-root variant of getJointCircuit.
Build in-memory circuits from the mmap-backed persistent store.
gate_t
Strongly-typed gate identifier.
Exact conjugate-prior posteriors for observe-evidence circuits.
Per-family polymorphic view over a continuous gate_rv distribution (§F.1 class hierarchy).
Analytical expectation / variance / moment evaluator over RV circuits.
Monte Carlo sampling over a GenericCircuit, RV-aware.
Shared 1-D quadrature core for the pivot-conjunction and order-statistic closed forms.
Continuous random-variable helpers (distribution parsing, moments).
Exception type thrown by circuit operations on invalid input.
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
gateType getGateType(gate_t g) const
Return the type of gate g.
bool isCategoricalMixture(gate_t g) const
Test whether g is a categorical-form gate_mixture (the explicit provsql.categorical output).
std::string getExtra(gate_t g) const
Return the string extra for gate g.
double getProb(gate_t g) const
Return the probability for gate g.
The quantity asked for has a value in no world (an aggregate over a group empty in every world of pos...
The SIGINT handler installed for the lifetime of the object, the previous one restored as it ends (a ...
double computeKL(const GenericCircuit &gc, gate_t p_root, gate_t q_root)
Kullback-Leibler divergence KL(P || Q) in nats.
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.
gate_t lift_conditioning(GenericCircuit &gc, gate_t root, std::optional< gate_t > &event_opt)
Lift conditioning out of a scalar arithmetic expression.
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.
double parseDoubleStrict(const std::string &s)
Strictly parse s as a double.
std::unique_ptr< Distribution > makeDistribution(const DistributionSpec &spec)
Construct the per-family Distribution for a parsed spec.
double computeEntropy(const GenericCircuit &gc, gate_t root, std::optional< gate_t > event)
Entropy of root in nats: Shannon for a discrete view, differential for a continuous one.
double simpsonIntegrate(double lo, double hi, int N, F &&f)
Composite-Simpson with N panels.
double computeMutualInformation(const GenericCircuit &gc, gate_t x_root, gate_t y_root)
Mutual information I(X; Y) in nats: exactly 0 for structurally independent roots, H(X) / Infinity for...
ConditionalScalarSamples monteCarloConditionalScalarSamples(const GenericCircuit &gc, gate_t root, gate_t event_root, unsigned samples)
Rejection-sample root conditioned on event_root.
std::optional< DistributionSpec > conjugatePosterior(const GenericCircuit &gc, gate_t target, gate_t evidence)
The exact posterior of target given evidence, as a resolved distribution spec, when the circuit match...
std::optional< DistributionSpec > parse_distribution_spec(const std::string &s)
Parse the on-disk text encoding of a gate_rv distribution.
constexpr int kSimpsonPanels
Panel count shared by every composite-Simpson quadrature over a distribution's integration range: exa...
std::vector< double > definedDraws(const std::vector< std::optional< double > > &samples)
The draws of samples that have a value, in order.
int provsql_rv_mc_samples
Default sample count for analytical-evaluator MC fallbacks; 0 disables fallback (callers raise instea...
Uniform error-reporting macros for ProvSQL.
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
void provsql_cancel_if_interrupted(void)
Raise PG's cancel if the evaluation stopped for one; nothing otherwise.
Cancellation of the long C++ evaluation loops.
Core types, constants, and utilities shared across ProvSQL.
@ gate_rv
Continuous random-variable leaf (extra encodes distribution).
@ gate_mixture
Probabilistic mixture: three wires [p_token (gate_input Bernoulli), x_token, y_token]; samples x when...
C++ utility functions for UUID manipulation.