-- Expected counts (the E-step of EM), on a network small enough to work -- by hand. SET client_min_messages = warning; CREATE EXTENSION IF NOT EXISTS pg_gaps; \set VERBOSITY terse -- Three instances of x -> y, P(x) = (0.3, 0.7) at offset 1 and P(y | x) = -- (0.9, 0.1 | 0.2, 0.8) at offset 3. Variables 1, 2: x missing, y = 1. -- 3, 4: both missing. 5, 6: x = 2, y = 2. -- -- By hand: instance 1 has P(x = 1 | y = 1) = 0.27 / 0.41 and P(x = 2 | -- y = 1) = 0.14 / 0.41; instance 2's family posterior is the joint (0.27, -- 0.03, 0.14, 0.56); instance 3 adds 1 to its cells. P(evidence) = 0.41 -- * 1 * (0.7 * 0.8). CREATE TEMP TABLE hand (cpt_off int, cell int, n float8); INSERT INTO hand VALUES (1, 1, 0.27 / 0.41 + 0.3), (1, 2, 0.14 / 0.41 + 0.7 + 1), (3, 1, 0.27 / 0.41 + 0.27), (3, 2, 0.03), (3, 3, 0.14 / 0.41 + 0.14), (3, 4, 0.56 + 1); CREATE TEMP TABLE got AS SELECT * FROM gaps._expected_counts('{2,2,2,2,2,2}', '{0,1,0,0,2,2}', '{1,2,3,4,5,6}', '{1,1,2,2,3,3,4}', '{1,3,5}', '{1,3,1,3,1,3}', '{0.3,0.7,0.9,0.1,0.2,0.8}'); SELECT g.cpt_off, g.cell, round(g.n::numeric, 9) AS n, abs(g.n - h.n) < 1e-12 AS agrees FROM got g FULL JOIN hand h USING (cpt_off, cell) ORDER BY 1, 2; cpt_off | cell | n | agrees ---------+------+-------------+-------- 1 | 1 | 0.958536585 | t 1 | 2 | 2.041463415 | t 3 | 1 | 0.928536585 | t 3 | 2 | 0.030000000 | t 3 | 3 | 0.481463415 | t 3 | 4 | 1.560000000 | t (6 rows) SELECT count(DISTINCT loglik) AS one_loglik, bool_and(abs(loglik - ln(0.41 * 0.56)) < 1e-12) AS loglik_agrees FROM got; one_loglik | loglik_agrees ------------+--------------- 1 | t (1 row) -- Each factor's counts sum to its number of instances. SELECT cpt_off, sum(n) FROM got GROUP BY cpt_off ORDER BY 1; cpt_off | sum ---------+----- 1 | 3 3 | 3 (2 rows) -- The same arguments are checked as for gaps._infer. SELECT * FROM gaps._expected_counts('{2}', '{3}', '{1}', '{1,1}', '{}', '{1}', '{0.5,0.5}'); -- fail: evidence ERROR: variable 1 has evidence 3 SELECT * FROM gaps._expected_counts('{2}', '{0}', '{1}', '{1,1}', '{}', '{1}', '{0.5}'); -- fail: short CPT ERROR: CPT 1 needs 2 values from its offset -- Two CPTs at one offset must have the same size. SELECT * FROM gaps._expected_counts('{2,3}', '{0,0}', '{1,2}', '{1,1,1}', '{}', '{1,1}', '{0.2,0.3,0.5}'); -- fail ERROR: CPTs sharing a cpt_off must have the same size (CPT of variable 2) -- Evidence of probability zero. SELECT * FROM gaps._expected_counts('{2}', '{1}', '{1}', '{1,1}', '{}', '{1}', '{0,1}'); -- fail ERROR: the observed values have probability zero under the model -- Too large for exact inference is an ERROR, sampling or not. SET gaps.max_total_cells = 8; SET gaps.samples = 100; SELECT * FROM gaps._expected_counts('{2,2}', '{0,0}', '{1,2}', '{1,1,2}', '{1}', '{1,3}', '{0.5,0.5,0.5,0.5,0.5,0.5}'); -- fail ERROR: expected counts need a factor larger than gaps.max_factor_cells (1048576) or more than gaps.max_total_cells (8) RESET gaps.max_total_cells; RESET gaps.samples; -- EM in learn_cpts. pg.ddx.io's t5 case: 10 rows (x, u), 10 rows (y, v), -- and 1000 rows with a missing and b = v. Counting complete rows ignores -- the 1000. With alpha = 0 the complete-data start has P(b = v | a = x) -- = 0, so each of the 1000 has a = y with posterior 1: P(a) moves to -- (10, 1010) / 1020 in one step and stays, P(b | a) stays (1, 0 | 0, 1), -- and log P(evidence) = 10 ln(10/1020) + 1010 ln(1010/1020). CREATE TABLE h (id int PRIMARY KEY, a text, b text); INSERT INTO h SELECT g, 'x', 'u' FROM generate_series(1, 10) g; INSERT INTO h SELECT g, 'y', 'v' FROM generate_series(11, 20) g; INSERT INTO h SELECT g, NULL, 'v' FROM generate_series(21, 1020) g; SELECT gaps.create_model('h'); create_model -------------- (1 row) SELECT gaps.declare_attribute('h', 'h', 'a', ARRAY['x', 'y']); declare_attribute ------------------- (1 row) SELECT gaps.declare_attribute('h', 'h', 'b', ARRAY['u', 'v']); declare_attribute ------------------- (1 row) SELECT gaps.add_stripe('h', 'a', 'h', 'a'); add_stripe ------------ (1 row) SELECT gaps.add_stripe('h', 'b', 'h', 'b'); add_stripe ------------ (1 row) SELECT gaps.add_factor('h', 'pa', 'a'); add_factor ------------ (1 row) SELECT gaps.add_factor('h', 'pb', 'b', ARRAY['a']); add_factor ------------ (1 row) SELECT factor, complete_entities, method, iterations, converged, abs(loglik - (10 * ln(10.0 / 1020) + 1010 * ln(1010.0 / 1020))) < 1e-9 AS loglik_ok FROM gaps.learn_cpts('h', 0, 'em') ORDER BY factor; factor | complete_entities | method | iterations | converged | loglik_ok --------+-------------------+--------+------------+-----------+----------- pa | 20 | em | 2 | t | t pb | 20 | em | 2 | t | t (2 rows) SELECT bool_and(abs(c - w) < 1e-12) AS hand FROM gaps.factor f, unnest(f.cpt, CASE f.name WHEN 'pa' THEN ARRAY[10.0 / 1020, 1010.0 / 1020] ELSE ARRAY[1, 0, 0, 1] END) AS u(c, w); hand ------ t (1 row) -- The default method is unchanged: complete rows only. SELECT factor, method, iterations FROM gaps.learn_cpts('h', 0) ORDER BY factor; factor | method | iterations --------+--------+------------ pa | counts | 0 pb | counts | 0 (2 rows) SELECT cpt FROM gaps.factor WHERE name = 'pa'; cpt ----------- {0.5,0.5} (1 row) -- With alpha > 0, P(b | a) moves too. The update (expected count + -- pseudocount) / (total + sum of pseudocounts) is EM for the posterior -- under a Dirichlet(pseudocount + 1) prior, so the log posterior, -- loglik + sum(pseudocount * ln(cell)), must not decrease from one -- iteration to the next. learn_cpts with max_iterations = t and tol 0 -- returns the t-th iterate and its loglik; alpha puts that pseudocount in -- every cell. At pseudocounts other than 1 the posterior-mean and the -- MAP readings of the update differ, so several are checked. CREATE TEMP TABLE path (a float8, t int, its int, obj float8); DO $$ DECLARE r record; a float8; BEGIN FOREACH a IN ARRAY ARRAY[0.5, 1, 3, 50] LOOP FOR t IN 1 .. 10 LOOP SELECT max(l.iterations) AS its, max(l.loglik) AS ll INTO r FROM gaps.learn_cpts('h', a, 'em', t, 0) l; INSERT INTO path SELECT a, t, r.its, r.ll + sum(a * ln(x)) FROM gaps.factor f, unnest(f.cpt) x WHERE f.model_id = gaps._model_id('h'); END LOOP; END LOOP; END $$; SELECT a, count(*) AS steps, bool_and(its = t) AS all_ran, bool_and(d >= -1e-12) AS monotone, sum(d) > 1e-4 AS moved FROM (SELECT a, t, its, obj - lag(obj) OVER (PARTITION BY a ORDER BY t) AS d FROM path) x WHERE d IS NOT NULL GROUP BY a ORDER BY a; a | steps | all_ran | monotone | moved -----+-------+---------+----------+------- 0.5 | 9 | t | t | t 1 | 9 | t | t | t 3 | 9 | t | t | t 50 | 9 | t | t | t (4 rows) -- And it converges: by 500 iterations an iteration changes the objective -- by at most 1e-6 of its size. SELECT DISTINCT method, converged, iterations < 500 AS early FROM gaps.learn_cpts('h', 1, 'em', 500); method | converged | early --------+-----------+------- em | t | t (1 row) -- A tiny positive pseudocount keeps its cells positive, and EM's -- objective stays finite: P(b = v | a = x) is 1e-20 / (10 + 2e-20), below -- the rounding of the row's other cell. SELECT factor, method, converged FROM gaps.learn_cpts('h', 1e-20, 'em') ORDER BY factor; factor | method | converged --------+--------+----------- pa | em | t pb | em | t (2 rows) SELECT bool_and(x > 0) AS positive, bool_and(abs(s - 1) < 1e-12) AS rows_sum_to_1 FROM (SELECT f.name, x, sum(x) OVER (PARTITION BY f.name, (i - 1) / 2) AS s FROM gaps.factor f, unnest(f.cpt) WITH ORDINALITY u(x, i) WHERE f.model_id = gaps._model_id('h')) c; positive | rows_sum_to_1 ----------+--------------- t | t (1 row) SELECT * FROM gaps.learn_cpts('h', 1, 'magic'); -- fail ERROR: method must be 'counts' or 'em', not magic SELECT * FROM gaps.learn_cpts('h', 1, 'em', 0); -- fail ERROR: max_iterations must be at least 1, not 0 SELECT * FROM gaps.learn_cpts('h', 1, 'em', 10, 'NaN'); -- fail ERROR: tol must be a finite non-negative number, not NaN -- Too large for exact inference is an ERROR, sampling or not. SET gaps.max_total_cells = 8; SET gaps.samples = 100; SELECT * FROM gaps.learn_cpts('h', 1, 'em'); -- fail ERROR: expected counts need a factor larger than gaps.max_factor_cells (1048576) or more than gaps.max_total_cells (8) RESET gaps.max_total_cells; RESET gaps.samples; DROP TABLE h; SELECT gaps.drop_model('h'); drop_model ------------ (1 row) -- With alpha = 0 the complete-data estimate can give probability 0 to a -- value only incomplete rows show: here P(b = v | a) = 0 for both a, and -- an entity with b = v and a missing is impossible under it. EM starts -- instead from the counts plus 1, (11, 11 | 11, 1 | 11, 1) / ..., and by -- symmetry reaches P(a) = (0.5, 0.5) and P(b | a) = (10, 0.5) / 10.5 for -- both a in one step. CREATE TABLE z (id int PRIMARY KEY, a text, b text); INSERT INTO z SELECT g, CASE WHEN g <= 10 THEN 'x' ELSE 'y' END, 'u' FROM generate_series(1, 20) g; INSERT INTO z VALUES (21, NULL, 'v'); SELECT gaps.create_model('z'); create_model -------------- (1 row) SELECT gaps.declare_attribute('z', 'z', 'a', ARRAY['x', 'y']); declare_attribute ------------------- (1 row) SELECT gaps.declare_attribute('z', 'z', 'b', ARRAY['u', 'v']); declare_attribute ------------------- (1 row) SELECT gaps.add_stripe('z', 'a', 'z', 'a'); add_stripe ------------ (1 row) SELECT gaps.add_stripe('z', 'b', 'z', 'b'); add_stripe ------------ (1 row) SELECT gaps.add_factor('z', 'pa', 'a'); add_factor ------------ (1 row) SELECT gaps.add_factor('z', 'pb', 'b', ARRAY['a']); add_factor ------------ (1 row) SELECT factor, method, iterations, converged, abs(loglik - (20 * ln(0.5 * 10 / 10.5) + ln(0.5 / 10.5))) < 1e-9 AS loglik_ok FROM gaps.learn_cpts('z', 0, 'em') ORDER BY factor; WARNING: the complete-data estimate gives probability 0 to observed values; EM starts from the counts plus max(pseudocount, 1) instead factor | method | iterations | converged | loglik_ok --------+--------------------+------------+-----------+----------- pa | em (add-one start) | 2 | t | t pb | em (add-one start) | 2 | t | t (2 rows) SELECT bool_and(abs(c - w) < 1e-12) AS hand FROM gaps.factor f, unnest(f.cpt, CASE f.name WHEN 'pa' THEN ARRAY[0.5, 0.5] ELSE ARRAY[10 / 10.5, 0.5 / 10.5, 10 / 10.5, 0.5 / 10.5] END) AS u(c, w) WHERE f.model_id = gaps._model_id('z'); hand ------ t (1 row) DROP TABLE z; SELECT gaps.drop_model('z'); drop_model ------------ (1 row) -- pg.ddx.io's shape: a latent class a, observed for a few labelled rows, -- with two children; no labelled row shows c = 3, which most unlabelled -- rows do. With alpha = 0 the start is again the counts plus 1, and EM -- learns P(c = 3 | a) from the unlabelled rows. CREATE TABLE lc (id int PRIMARY KEY, a text, b text, c text); INSERT INTO lc SELECT g, CASE WHEN g % 2 = 0 THEN 's' ELSE 't' END, CASE WHEN g % 2 = 0 THEN '1' ELSE '2' END, CASE WHEN g % 2 = 0 THEN '1' ELSE '2' END FROM generate_series(1, 6) g; INSERT INTO lc SELECT g, NULL, CASE WHEN g % 3 = 0 THEN '1' ELSE '2' END, CASE WHEN g % 4 = 0 THEN '1' ELSE '3' END FROM generate_series(7, 60) g; SELECT gaps.create_model('lc'); create_model -------------- (1 row) SELECT gaps.declare_attribute('lc', 'lc', 'a', ARRAY['s', 't']); declare_attribute ------------------- (1 row) SELECT gaps.declare_attribute('lc', 'lc', x, ARRAY['1', '2', '3']) FROM unnest(ARRAY['b', 'c']) x; declare_attribute ------------------- (2 rows) SELECT gaps.add_stripe('lc', x, 'lc', x) FROM unnest(ARRAY['a', 'b', 'c']) x; add_stripe ------------ (3 rows) SELECT gaps.add_factor('lc', 'pa', 'a'); add_factor ------------ (1 row) SELECT gaps.add_factor('lc', 'p' || x, x, ARRAY['a']) FROM unnest(ARRAY['b', 'c']) x; add_factor ------------ (2 rows) SELECT factor, complete_entities, method, converged FROM gaps.learn_cpts('lc', 0, 'em') ORDER BY factor; WARNING: the complete-data estimate gives probability 0 to observed values; EM starts from the counts plus max(pseudocount, 1) instead factor | complete_entities | method | converged --------+-------------------+--------------------+----------- pa | 6 | em (add-one start) | t pb | 6 | em (add-one start) | t pc | 6 | em (add-one start) | t (3 rows) -- Only the start's "probability zero" error triggers the add-one restart: -- a directed cycle (22023, the same SQLSTATE class) is reported as itself. CREATE TABLE cyc (id int PRIMARY KEY, a text, b text); INSERT INTO cyc VALUES (1, NULL, 'x'); SELECT gaps.create_model('cyc'); create_model -------------- (1 row) SELECT gaps.declare_attribute('cyc', 'cyc', 'a', ARRAY['x', 'y']); declare_attribute ------------------- (1 row) SELECT gaps.declare_attribute('cyc', 'cyc', 'b', ARRAY['x', 'y']); declare_attribute ------------------- (1 row) SELECT gaps.add_stripe('cyc', 'a', 'cyc', 'a'); add_stripe ------------ (1 row) SELECT gaps.add_stripe('cyc', 'b', 'cyc', 'b'); add_stripe ------------ (1 row) SELECT gaps.add_factor('cyc', 'ab', 'a', ARRAY['b']); add_factor ------------ (1 row) SELECT gaps.add_factor('cyc', 'ba', 'b', ARRAY['a']); add_factor ------------ (1 row) SELECT gaps.map_factor('cyc', 'ab', 1, 'id', 'id'); map_factor ------------ (1 row) SELECT gaps.map_factor('cyc', 'ba', 1, 'id', 'id'); map_factor ------------ (1 row) SELECT * FROM gaps.learn_cpts('cyc', 0, 'em'); -- fail: cycle, no restart ERROR: the ground network has a directed cycle through variable 1 SELECT gaps.drop_model('cyc'); drop_model ------------ (1 row) DROP TABLE cyc; -- P(c = 3) under the learned model: the share of rows with c = 3, 40 / 60, -- since EM's fixed points match the observed marginal of a child that is -- never missing. SELECT round((pa.cpt[1] * pc.cpt[3] + pa.cpt[2] * pc.cpt[6])::numeric, 6) AS p_c3, round(40 / 60.0, 6) AS observed FROM gaps.factor pa, gaps.factor pc WHERE pa.model_id = gaps._model_id('lc') AND pa.name = 'pa' AND pc.model_id = pa.model_id AND pc.name = 'pc'; p_c3 | observed ----------+---------- 0.666667 | 0.666667 (1 row) DROP TABLE lc; SELECT gaps.drop_model('lc'); drop_model ------------ (1 row) -- On complete data the E-step returns the counts, so EM stops after one -- iteration with the counting answer. CREATE TABLE c (id int PRIMARY KEY, a text, b text); INSERT INTO c VALUES (1, 'x', 'u'), (2, 'x', 'v'), (3, 'y', 'v'); SELECT gaps.create_model('c'); create_model -------------- (1 row) SELECT gaps.declare_attribute('c', 'c', 'a', ARRAY['x', 'y']); declare_attribute ------------------- (1 row) SELECT gaps.declare_attribute('c', 'c', 'b', ARRAY['u', 'v']); declare_attribute ------------------- (1 row) SELECT gaps.add_stripe('c', 'a', 'c', 'a'); add_stripe ------------ (1 row) SELECT gaps.add_stripe('c', 'b', 'c', 'b'); add_stripe ------------ (1 row) SELECT gaps.add_factor('c', 'pa', 'a'); add_factor ------------ (1 row) SELECT gaps.add_factor('c', 'pb', 'b', ARRAY['a']); add_factor ------------ (1 row) SELECT * FROM gaps.learn_cpts('c', 1) ORDER BY factor; factor | complete_entities | method | iterations | loglik | converged --------+-------------------+--------+------------+--------+----------- pa | 3 | counts | 0 | | pb | 3 | counts | 0 | | (2 rows) CREATE TEMP TABLE counted AS SELECT name, cpt FROM gaps.factor WHERE model_id = gaps._model_id('c'); SELECT factor, method, iterations, converged FROM gaps.learn_cpts('c', 1, 'em') ORDER BY 1; factor | method | iterations | converged --------+--------+------------+----------- pa | em | 1 | t pb | em | 1 | t (2 rows) SELECT bool_and(abs(x - y) < 1e-12) AS same FROM gaps.factor f JOIN counted USING (name), unnest(f.cpt, counted.cpt) u(x, y) WHERE f.model_id = gaps._model_id('c'); same ------ t (1 row) DROP TABLE c; SELECT gaps.drop_model('c'); drop_model ------------ (1 row)