"""Exact tiny experiments (deliverable C + D on tiny domains). Domain T1: X = {a,b}^P with P a bare 3-set (|X| = 8, |Y| = 2) Domain T1': same underlying set, but P = bare-2-set + bare-1-set (the Coor shape), so less symmetry is available. For every one of the 256 extensional functions we compute the TRUE minimum certificate cost by exhaustive settled-set Dijkstra, then compare the incremental repair learner (random presentation orders, full data) and the global greedy learner against that optimum. Run: python3 experiments/exp_tiny.py """ import json import os import random import statistics import sys sys.path.insert(0, os.path.join(os.path.dirname(__file__), "..", "src")) from certlang.core import (Certificate, IncrementalLearner, Rule, build_library, choice, exact_min_certificate, greedy_learner) from certlang.domains import all_functions, tiny_domain OUT = os.path.join(os.path.dirname(__file__), "..", "results") os.makedirs(OUT, exist_ok=True) def count_a(x, npos=3): """number of positions with digit value 0 ('a') in base-2 encoding""" return sum(1 for p in range(npos) if (x >> p) & 1 == 0) def exact_all(dom, lib): costs = {} certs = {} for labels in all_functions(dom.n, dom.ny): cert = exact_min_certificate(list(labels), dom, lib) assert tuple(cert.predict_all(dom.n)) == labels costs[labels] = cert.cost() certs[labels] = cert return costs, certs def main(): rng = random.Random(0) report = {} dom1 = tiny_domain([3], nvals=2) dom2 = tiny_domain([2, 1], nvals=2) lib1 = build_library(dom1, max_atoms=3) lib2 = build_library(dom2, max_atoms=3) print(f"T1 atoms={len(dom1.atoms)} library={len(lib1)} distinct subsets") print(f"T1' atoms={len(dom2.atoms)} library={len(lib2)} distinct subsets") print("computing exact optima for all 256 functions on both domains ...") costs1, certs1 = exact_all(dom1, lib1) costs2, certs2 = exact_all(dom2, lib2) # ---- 1. cost landscape -------------------------------------------------- all_c1 = sorted(costs1.values()) sym_funcs = [] # functions invariant under S3 on positions = factor through count for labels in costs1: by_count = {} ok = True for x in range(8): c = count_a(x) if by_count.setdefault(c, labels[x]) != labels[x]: ok = False break if ok: sym_funcs.append(labels) sym_costs = [costs1[f] for f in sym_funcs] nonsym_costs = [c for f, c in costs1.items() if f not in set(sym_funcs)] report["T1"] = { "n_functions": len(costs1), "cost_min": min(all_c1), "cost_max": max(all_c1), "cost_mean": statistics.mean(all_c1), "cost_median": statistics.median(all_c1), "n_symmetric": len(sym_funcs), "symmetric_mean": statistics.mean(sym_costs), "nonsymmetric_mean": statistics.mean(nonsym_costs), } print(f"\nT1 cost landscape over all 256 functions:") print(f" min={min(all_c1):.2f} median={statistics.median(all_c1):.2f} " f"max={max(all_c1):.2f} mean={statistics.mean(all_c1):.2f}") print(f" S3-invariant functions (n={len(sym_funcs)}): " f"mean={statistics.mean(sym_costs):.2f}") print(f" non-invariant functions: mean={statistics.mean(nonsym_costs):.2f}") named = { "constant 0": tuple([0] * 8), "majority(a)": tuple(1 if count_a(x) >= 2 else 0 for x in range(8)), "parity(a)": tuple(count_a(x) % 2 for x in range(8)), "all-equal": tuple(1 if x in (0, 7) else 0 for x in range(8)), "singleton {aaa}": tuple(1 if x == 0 else 0 for x in range(8)), "singleton {aab}": tuple(1 if x == 4 else 0 for x in range(8)), "dictator x[0]": tuple((x >> 0) & 1 for x in range(8)), "worst random-ish": max(costs1, key=costs1.get), } print("\nNamed functions (cost T1 / cost T1'):") report["named"] = {} for name, f in named.items(): print(f" {name:22s} {costs1[f]:6.2f} / {costs2[f]:6.2f}") report["named"][name] = {"T1": costs1[f], "T1prime": costs2[f]} print("\nExample optimal certificate for majority(a) on T1:") print(certs1[named["majority(a)"]].explain(dom1.ylabels)) print("\nExample optimal certificate for parity(a) on T1:") print(certs1[named["parity(a)"]].explain(dom1.ylabels)) print("\nExample optimal certificate for singleton {aab} on T1:") print(certs1[named["singleton {aab}"]].explain(dom1.ylabels)) # ---- 2. structure dependence: same extensions, poorer structure --------- diffs = [costs2[f] - costs1[f] for f in costs1] report["structure_dependence"] = { "mean_T1prime_minus_T1": statistics.mean(diffs), "n_more_expensive": sum(1 for d in diffs if d > 1e-9), "n_cheaper": sum(1 for d in diffs if d < -1e-9), } print(f"\nT1' vs T1 (same 256 extensions, coarser symmetry):") print(f" mean cost difference = {statistics.mean(diffs):+.2f} bits; " f"{sum(1 for d in diffs if d > 1e-9)} costlier, " f"{sum(1 for d in diffs if d < -1e-9)} cheaper on T1'") # ---- 3. incremental learner vs exact optimum ---------------------------- ORDERS = 10 results = {"repair_only": [], "recompressed": [], "greedy": []} n_repair_opt = n_rec_opt = n_greedy_opt = 0 for labels in costs1: opt = costs1[labels] gcert = greedy_learner({x: labels[x] for x in range(8)}, dom1, max_atoms=3, rng=random.Random(3)) results["greedy"].append(gcert.cost() / opt) if abs(gcert.cost() - opt) < 1e-9: n_greedy_opt += 1 raw_best, rec_best = float("inf"), float("inf") for o in range(ORDERS): order = list(range(8)) rng.shuffle(order) learner = IncrementalLearner(dom1, max_atoms=3) for x in order: learner.observe(x, labels[x]) raw_best = min(raw_best, learner.cert.cost()) learner.recompress(orders=2, rng=random.Random(o)) assert learner.cert.predict_all(8) == list(labels) rec_best = min(rec_best, learner.cert.cost()) results["repair_only"].append(raw_best / opt) results["recompressed"].append(rec_best / opt) if abs(raw_best - opt) < 1e-9: n_repair_opt += 1 if abs(rec_best - opt) < 1e-9: n_rec_opt += 1 def summ(key, nopt): r = results[key] return {"frac_optimal": nopt / 256, "mean_ratio": statistics.mean(r), "worst_ratio": max(r)} report["incremental_vs_exact"] = { "orders_per_function": ORDERS, "repair_only_bestof": summ("repair_only", n_repair_opt), "recompressed_bestof": summ("recompressed", n_rec_opt), "greedy_global": summ("greedy", n_greedy_opt), } print(f"\nIncremental vs exact optimum (256 functions, best of {ORDERS} orders):") for key, nopt in (("repair_only", n_repair_opt), ("recompressed", n_rec_opt), ("greedy", n_greedy_opt)): s = summ(key, nopt) print(f" {key:18s} optimal on {s['frac_optimal']*100:5.1f}% " f"mean ratio {s['mean_ratio']:.3f} worst {s['worst_ratio']:.3f}") # single-order (no cherry-picking) statistics single = {"repair_only": [], "recompressed": []} for labels in costs1: opt = costs1[labels] order = list(range(8)) rng.shuffle(order) learner = IncrementalLearner(dom1, max_atoms=3) for x in order: learner.observe(x, labels[x]) single["repair_only"].append(learner.cert.cost() / opt) learner.recompress(orders=2, rng=random.Random(1)) single["recompressed"].append(learner.cert.cost() / opt) report["incremental_single_order"] = { k: {"mean_ratio": statistics.mean(v), "worst_ratio": max(v), "frac_optimal": sum(1 for r in v if r < 1 + 1e-9) / len(v)} for k, v in single.items()} print("\nSingle random order (no best-of):") for k, v in single.items(): print(f" {k:18s} optimal on " f"{100*sum(1 for r in v if r < 1+1e-9)/len(v):5.1f}% " f"mean ratio {statistics.mean(v):.3f} worst {max(v):.3f}") # ---- 4. planted short certificates -------------------------------------- print("\nPlanted-certificate recovery (random 2-rule certificates):") planted_stats = [] prng = random.Random(42) lib_list = lib1 for _ in range(200): default = prng.randrange(2) cert = Certificate(default, 2) for _r in range(2): mask, scost, desc = lib_list[prng.randrange(len(lib_list))] cert.rules.append(Rule(mask, prng.randrange(2), scost, desc)) labels = tuple(cert.predict_all(8)) planted_stats.append(costs1[labels] <= cert.cost() + 1e-9) frac = sum(planted_stats) / len(planted_stats) report["planted_recovery_frac_leq"] = frac print(f" exact optimum <= planted cost in {frac*100:.1f}% of 200 draws " f"(must be 100%)") with open(os.path.join(OUT, "tiny_results.json"), "w") as fh: json.dump(report, fh, indent=2) print(f"\nwrote {os.path.join(OUT, 'tiny_results.json')}") if __name__ == "__main__": main()