ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
InformationTheory.cpp
Go to the documentation of this file.
1/**
2 * @file InformationTheory.cpp
3 * @brief Entropy / KL divergence / mutual information readouts.
4 */
5#include "InformationTheory.h"
6
7#include "CircuitFromMMap.h"
8#include "ConjugatePosterior.h" // conjugatePosterior (observe-evidence entropy)
9#include "Expectation.h" // lift_conditioning, evaluateBooleanProbability
10#include "MonteCarloSampler.h"
11#include "PivotIntegration.h" // simpsonIntegrate, kSimpsonPanels
12#include "RandomVariable.h" // parse_distribution_spec
14#include "provsql_utils_cpp.h"
15
16extern "C" {
17#include "postgres.h"
18#include "fmgr.h"
19#include "utils/uuid.h"
20#include "provsql_utils.h"
21#include "provsql_error.h"
22
23PG_FUNCTION_INFO_V1(rv_entropy);
24PG_FUNCTION_INFO_V1(rv_kl);
25PG_FUNCTION_INFO_V1(rv_mutual_information);
26}
27
28#include <algorithm>
29#include <cmath>
30#include <functional>
31#include <map>
32#include <memory>
33#include <set>
34#include <string>
35#include <vector>
36#include "provsql_interrupt.h"
37
38namespace provsql {
39
40namespace {
41
42constexpr double kInf = std::numeric_limits<double>::infinity();
43
44unsigned mc_budget_or_throw(const std::string &what)
45{
46 const int n = provsql_rv_mc_samples;
47 if (n <= 0)
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);
52}
53
54/* ------------------------------------------------------------------
55 * Density views.
56 *
57 * A gate resolves to a closed density view when its distribution is
58 * expressible in one of two exact forms: a finite pmf (gate_value,
59 * categorical mixture) or a continuous pdf callable over a finite
60 * integration window (bare gate_rv, and Bernoulli mixture trees over
61 * INDEPENDENT arms -- the gmm cascade -- whose pdf is the weighted sum
62 * of the arms'). Everything else (arith composites, shared-leaf
63 * mixtures, conditioned roots) has no closed view and the caller falls
64 * back to MC or raises.
65 * ------------------------------------------------------------------ */
66struct DensityView {
67 bool discrete;
68 std::map<double, double> pmf; /* discrete */
69 std::function<double(double)> pdf; /* continuous */
70 double lo = 0.0, hi = 0.0; /* continuous window */
71};
72
73/* Stochastic leaves reachable from g (gate_rv / gate_input /
74 * gate_mulinput): the footprint used for the structural-independence
75 * shortcuts. Deterministic gate_value leaves are deliberately not
76 * collected -- they are shared by v5-keying and carry no randomness. */
77void collectStochasticLeaves(const GenericCircuit &gc, gate_t g,
78 std::set<gate_t> &out, std::set<gate_t> &seen)
79{
80 if (!seen.insert(g).second) return;
81 const auto t = gc.getGateType(g);
82 if (t == gate_rv || t == gate_input || t == gate_mulinput)
83 out.insert(g);
84 for (gate_t c : gc.getWires(g))
85 collectStochasticLeaves(gc, c, out, seen);
86}
87
88std::set<gate_t> stochasticLeaves(const GenericCircuit &gc, gate_t g)
89{
90 std::set<gate_t> out, seen;
91 collectStochasticLeaves(gc, g, out, seen);
92 return out;
93}
94
95std::optional<DensityView>
96resolveDensity(const GenericCircuit &gc, gate_t g)
97{
98 const auto t = gc.getGateType(g);
99
100 if (t == gate_value) {
101 double v;
102 try { v = parseDoubleStrict(gc.getExtra(g)); }
103 catch (const CircuitException &) { return std::nullopt; }
104 DensityView view;
105 view.discrete = true;
106 view.pmf[v] = 1.0;
107 return view;
108 }
109
110 if (t == gate_rv) {
111 auto spec = parse_distribution_spec(gc.getExtra(g));
112 if (!spec) return std::nullopt;
113 std::shared_ptr<Distribution> dist = makeDistribution(*spec);
114 DensityView view;
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); };
118 return view;
119 }
120
121 if (t == gate_mixture) {
122 const auto &wires = gc.getWires(g);
123 if (gc.isCategoricalMixture(g)) {
124 DensityView view;
125 view.discrete = true;
126 for (std::size_t i = 1; i < wires.size(); ++i) {
127 double v;
128 try { v = parseDoubleStrict(gc.getExtra(wires[i])); }
129 catch (const CircuitException &) { return std::nullopt; }
130 view.pmf[v] += gc.getProb(wires[i]);
131 }
132 return view;
133 }
134 /* Bernoulli mixture(p, x, y). The selection coin must be a bare
135 * pinned input and the arms must be leaf-disjoint (a shared leaf
136 * makes the arms correlated, so the pdf is no longer the weighted
137 * sum of the arm pdfs). */
138 if (wires.size() != 3) return std::nullopt;
139 if (gc.getGateType(wires[0]) != gate_input) 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]);
144 for (gate_t l : ax)
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) {
150 DensityView view;
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;
154 return view;
155 }
156 if (!vx->discrete && !vy->discrete) {
157 DensityView view;
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;
167 };
168 return view;
169 }
170 /* Mixed discrete/continuous mixture: neither a pmf nor a pdf. */
171 return std::nullopt;
172 }
173
174 return std::nullopt;
175}
176
177/* Shannon entropy of a pmf / differential entropy of a pdf, in nats. */
178double entropyOfView(const DensityView &view)
179{
180 if (view.discrete) {
181 double h = 0.0;
182 for (const auto &[v, p] : view.pmf)
183 if (p > 0.0) h -= p * std::log(p);
184 return h;
185 }
186 return simpsonIntegrate(view.lo, view.hi, kSimpsonPanels,
187 [&](double x) {
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; /* x ln x -> 0 as x -> 0 */
191 return -f * std::log(f);
192 });
193}
194
195/* Histogram plug-in estimate of the (differential) entropy from raw
196 * draws: Scott-rule bin width, H^ = -sum (n_i/m) ln(n_i / (m h)). A
197 * degenerate sample (zero spread) is a point mass: Shannon entropy 0.
198 * Draws with no value are missing observations; a NaN drawn (a NaN in the
199 * data) cannot be binned, and makes the estimate NaN. */
200double entropyFromSamples(const std::vector<std::optional<double>> &draws,
201 const std::string &what)
202{
203 const std::vector<double> xs = definedDraws(draws);
204 const std::size_t m = xs.size();
205 if (m == 0)
206 throw NoValueException(what);
207 for (double v : xs)
208 if (std::isnan(v)) return v;
209 double mean = 0.0;
210 for (double v : xs) mean += v;
211 mean /= static_cast<double>(m);
212 double var = 0.0;
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; /* point mass */
217 const double h =
218 3.49 * sd / std::cbrt(static_cast<double>(m)); /* Scott's rule */
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;
227 ++counts[b];
228 }
229 double H = 0.0;
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);
234 }
235 return H;
236}
237
238} // namespace
239
240double computeEntropy(const GenericCircuit &gc, gate_t root,
241 std::optional<gate_t> event)
242{
243 if (!event) {
244 if (auto view = resolveDensity(gc, root)) {
245 const double h = entropyOfView(*view);
246 if (!std::isnan(h)) return h;
247 }
248 return entropyFromSamples(
249 monteCarloScalarSamples(gc, root, mc_budget_or_throw("entropy")),
250 "entropy");
251 }
252 /* Conjugate observe-evidence: the posterior is a bare distribution of
253 * the prior's family, so its (differential) entropy is the exact
254 * quadrature over the family pdf -- no sampling. */
255 if (auto post = conjugatePosterior(gc, root, *event)) {
256 std::shared_ptr<Distribution> dist = makeDistribution(*post);
257 DensityView view;
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;
263 }
264 }
265 /* Conditional entropy of X | A: plug-in estimate over the rejection
266 * sampler's conditional draws (the coupled joint circuit keeps a leaf
267 * shared between root and event on one draw per iteration). */
269 gc, root, *event, mc_budget_or_throw("conditional entropy"));
270 if (cs.accepted.empty())
271 throw CircuitException(
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");
275}
276
277double computeKL(const GenericCircuit &gc, gate_t p_root, gate_t q_root)
278{
279 auto vp = resolveDensity(gc, p_root);
280 auto vq = resolveDensity(gc, q_root);
281 if (!vp || !vq)
282 throw CircuitException(
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");
287
288 if (vp->discrete && vq->discrete) {
289 double kl = 0.0;
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; /* P not abs. continuous w.r.t. Q */
295 kl += p * std::log(p / q);
296 }
297 return kl;
298 }
299 if (vp->discrete != vq->discrete)
300 return kInf; /* atoms vs a density: never absolutely continuous */
301
302 /* Continuous-continuous: integrate f_p ln(f_p / f_q) over P's window.
303 * f_q underflowing to 0 where f_p has mass yields +Infinity, which
304 * flows through the quadrature. */
305 return simpsonIntegrate(vp->lo, vp->hi, kSimpsonPanels,
306 [&](double x) {
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);
314 });
315}
316
318 gate_t y_root)
319{
320 if (x_root == y_root) {
321 /* I(X; X) = H(X): finite (Shannon) for a discrete X, +Infinity for a
322 * continuous one. */
323 if (auto view = resolveDensity(gc, x_root))
324 if (view->discrete) return entropyOfView(*view);
325 return kInf;
326 }
327
328 /* Structural independence: disjoint stochastic leaves => I = 0. */
329 {
330 auto lx = stochasticLeaves(gc, x_root);
331 auto ly = stochasticLeaves(gc, y_root);
332 bool shared = false;
333 for (gate_t l : lx)
334 if (ly.count(l)) { shared = true; break; }
335 if (!shared) return 0.0;
336 }
337
338 /* Correlated pair: 2-D histogram plug-in over coupled joint draws.
339 * B ~ m^(1/3) bins per axis; I^ = sum p_ij ln(p_ij / (p_i q_j)),
340 * non-negative by construction. */
341 const unsigned m0 = mc_budget_or_throw("mutual_information");
342 auto [xs, ys] = monteCarloScalarPairSamples(gc, x_root, y_root, m0);
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]) {
347 /* A NaN drawn (a NaN in the data) cannot be binned. */
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]);
351 }
352 const std::size_t m = pairs.size();
353 if (m == 0)
354 throw NoValueException("mutual_information");
355
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);
360 }
361 if (!(xhi > xlo) || !(yhi > ylo))
362 return 0.0; /* a degenerate marginal carries no information */
363
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;
370 };
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];
375 ++margx[bx];
376 ++margy[by];
377 }
378 const double dm = static_cast<double>(m);
379 double mi = 0.0;
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));
388 }
389 return std::max(mi, 0.0);
390}
391
392} // namespace provsql
393
394/* ------------------------------------------------------------------
395 * SQL-callable entry points, mirroring rv_moment's plumbing.
396 * ------------------------------------------------------------------ */
397
398/**
399 * @brief SQL: rv_entropy(token uuid, prov uuid) -> float8
400 */
401Datum rv_entropy(PG_FUNCTION_ARGS)
402{
403 try {
404 provsql_interrupt_scope interrupt_scope;
405 pg_uuid_t *token = PG_GETARG_UUID_P(0);
406 pg_uuid_t *prov = PG_GETARG_UUID_P(1);
407
408 gate_t root_gate, event_gate;
409 auto gc = getJointCircuit(*token, *prov, root_gate, event_gate);
410
411 std::optional<gate_t> event_opt;
412 if (gc.getGateType(event_gate) != gate_one)
413 event_opt = event_gate;
414 root_gate = provsql::lift_conditioning(gc, root_gate, event_opt);
415
416 return Float8GetDatum(
417 provsql::computeEntropy(gc, root_gate, event_opt));
418 } catch (const provsql::NoValueException &) {
419 /* Defined in no world: SQL's NULL. */
421 PG_RETURN_NULL();
422 } catch (const std::exception &e) {
424 provsql_error("rv_entropy: %s", e.what());
425 } catch (...) {
427 provsql_error("rv_entropy: unknown exception");
428 }
429 PG_RETURN_NULL();
430}
431
432/**
433 * @brief SQL: rv_kl(p uuid, q uuid) -> float8
434 */
435Datum rv_kl(PG_FUNCTION_ARGS)
436{
437 try {
438 provsql_interrupt_scope interrupt_scope;
439 pg_uuid_t *p = PG_GETARG_UUID_P(0);
440 pg_uuid_t *q = PG_GETARG_UUID_P(1);
441
442 gate_t p_gate, q_gate;
443 auto gc = getJointCircuit(*p, *q, p_gate, q_gate);
444
445 return Float8GetDatum(provsql::computeKL(gc, p_gate, q_gate));
446 } catch (const provsql::NoValueException &) {
447 /* Defined in no world: SQL's NULL. */
449 PG_RETURN_NULL();
450 } catch (const std::exception &e) {
452 provsql_error("rv_kl: %s", e.what());
453 } catch (...) {
455 provsql_error("rv_kl: unknown exception");
456 }
457 PG_RETURN_NULL();
458}
459
460/**
461 * @brief SQL: rv_mutual_information(x uuid, y uuid) -> float8
462 */
463Datum rv_mutual_information(PG_FUNCTION_ARGS)
464{
465 try {
466 provsql_interrupt_scope interrupt_scope;
467 pg_uuid_t *x = PG_GETARG_UUID_P(0);
468 pg_uuid_t *y = PG_GETARG_UUID_P(1);
469
470 gate_t x_gate, y_gate;
471 auto gc = getJointCircuit(*x, *y, x_gate, y_gate);
472
473 return Float8GetDatum(
474 provsql::computeMutualInformation(gc, x_gate, y_gate));
475 } catch (const provsql::NoValueException &) {
476 /* Defined in no world: SQL's NULL. */
478 PG_RETURN_NULL();
479 } catch (const std::exception &e) {
481 provsql_error("rv_mutual_information: %s", e.what());
482 } catch (...) {
484 provsql_error("rv_mutual_information: unknown exception");
485 }
486 PG_RETURN_NULL();
487}
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.
Definition Circuit.h:53
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.
Datum rv_kl(PG_FUNCTION_ARGS)
SQL: rv_kl(p uuid, q uuid) -> float8.
Datum rv_entropy(PG_FUNCTION_ARGS)
SQL: rv_entropy(token uuid, prov uuid) -> float8.
Datum rv_mutual_information(PG_FUNCTION_ARGS)
SQL: rv_mutual_information(x uuid, y uuid) -> float8.
Information-theoretic readouts over scalar RV sub-circuits: entropy, Kullback-Leibler divergence,...
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.
Definition Circuit.h:382
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
Definition Circuit.h:311
gateType getGateType(gate_t g) const
Return the type of gate g.
Definition Circuit.h:301
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...
Definition Expectation.h:47
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.
constexpr double kInf
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...
Definition provsql.c:126
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.