#!/usr/bin/env node
// research/occams-razor/verify.mjs
// The check behind the stratum "Occam's Razor, made operable."
//
// The page turns the razor from a slogan ("the simplest explanation is the
// correct one") into a NUMBER you can watch get computed. This verifier
// recomputes, offline and deterministically, every quantitative claim the
// instrument surfaces:
//
//   A. Fit polynomials of degree d = 0..D to N noisy samples of a true signal.
//      TRAINING error falls monotonically to ~0 at the interpolation degree
//      (d = N-1). GENERALISATION error (vs the true signal) is U-shaped:
//      under-fitting on the left, over-fitting on the right.
//
//   B. The BAYESIAN OCCAM FACTOR. For the linear-Gaussian model the marginal
//      likelihood (the "evidence") has a closed form. The evidence = best-fit
//      likelihood x Occam factor. The best-fit likelihood RISES with
//      complexity; the Occam factor FALLS with it; their product PEAKS at an
//      intermediate degree. Nobody imposed a penalty by hand — probability
//      normalisation did it. Two independent closed forms (the N x N "kernel"
//      form and the (d+1) x (d+1) "posterior" form) are required to agree.
//
//   C. The frequentist criteria AIC (Akaike 1974) and BIC (Schwarz 1978) also
//      pick an interior degree, from an explicitly-written k-vs-fit penalty.
//
//   D. The honest limit: with few samples or heavy noise the razor's chosen
//      degree drops BELOW the signal's real complexity. The razor is the best
//      bet under the assumptions, not a guarantee of truth.
//
// Pure Node, no deps. Deterministic (seeded RNG). Nonzero exit if any check
// fails. Run: node research/occams-razor/verify.mjs
//
// Math references (verified in the companion history report, see the stratum):
//   C.M. Bishop, Pattern Recognition and Machine Learning (2006), sec. 3.4-3.5
//     & 1.1 (the sin(2*pi*x) polynomial-fit example), eq. 3.86 for log-evidence.
//   D.J.C. MacKay, Information Theory, Inference, and Learning Algorithms
//     (2003), ch. 28, "Model Comparison and Occam's Razor" (evidence = best-fit
//     x Occam factor).
//   H. Akaike, IEEE Trans. Automatic Control 19 (1974) 716.  G. Schwarz,
//     Ann. Statist. 6 (1978) 461 (BIC).

'use strict';

let fails = 0;
const ok = (name, cond, extra = '') => {
  if (!cond) fails++;
  console.log(`${cond ? '  ok' : 'FAIL'}  ${name}${extra ? '   ' + extra : ''}`);
};
const sec = (t) => console.log('\n' + t);
const approx = (a, b, tol = 1e-6) =>
  Math.abs(a - b) <= tol * Math.max(1, Math.abs(a), Math.abs(b));

// ---------------------------------------------------------------------------
// Deterministic RNG so the page and this verifier draw the SAME dataset.
// mulberry32 + Box-Muller.
// ---------------------------------------------------------------------------
function mulberry32(seed) {
  let a = seed >>> 0;
  return function () {
    a |= 0; a = (a + 0x6d2b79f5) | 0;
    let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
function makeGaussian(rng) {
  let spare = null;
  return function () {
    if (spare !== null) { const s = spare; spare = null; return s; }
    let u, v, s;
    do { u = 2 * rng() - 1; v = 2 * rng() - 1; s = u * u + v * v; }
    while (s >= 1 || s === 0);
    const f = Math.sqrt(-2 * Math.log(s) / s);
    spare = v * f;
    return u * f;
  };
}

// ---------------------------------------------------------------------------
// Tiny linear algebra for symmetric-positive-definite systems (Cholesky).
// ---------------------------------------------------------------------------
function cholesky(A) {          // A: n x n SPD -> lower L with A = L L^T
  const n = A.length;
  const L = Array.from({ length: n }, () => new Float64Array(n));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j <= i; j++) {
      let s = A[i][j];
      for (let k = 0; k < j; k++) s -= L[i][k] * L[j][k];
      if (i === j) {
        if (s <= 0) throw new Error('cholesky: not positive definite');
        L[i][j] = Math.sqrt(s);
      } else {
        L[i][j] = s / L[j][j];
      }
    }
  }
  return L;
}
function cholSolve(L, b) {       // solve (L L^T) x = b
  const n = L.length;
  const y = new Float64Array(n);
  for (let i = 0; i < n; i++) {
    let s = b[i];
    for (let k = 0; k < i; k++) s -= L[i][k] * y[k];
    y[i] = s / L[i][i];
  }
  const x = new Float64Array(n);
  for (let i = n - 1; i >= 0; i--) {
    let s = y[i];
    for (let k = i + 1; k < n; k++) s -= L[k][i] * x[k];
    x[i] = s / L[i][i];
  }
  return x;
}
const cholLogDet = (L) => {     // log|A| = 2 sum log L_ii
  let s = 0;
  for (let i = 0; i < L.length; i++) s += Math.log(L[i][i]);
  return 2 * s;
};

// ---------------------------------------------------------------------------
// Polynomial basis on t in [-1,1] (Vandermonde). Inputs x in [0,1] mapped by
// t = 2x - 1 for conditioning.
// ---------------------------------------------------------------------------
const toT = (x) => 2 * x - 1;
function design(xs, degree) {
  return xs.map((x) => {
    const t = toT(x), row = new Float64Array(degree + 1);
    let p = 1;
    for (let j = 0; j <= degree; j++) { row[j] = p; p *= t; }
    return row;
  });
}
function gram(Phi) {             // Phi^T Phi  and  Phi^T y builder
  const N = Phi.length, M = Phi[0].length;
  const G = Array.from({ length: M }, () => new Float64Array(M));
  for (let a = 0; a < M; a++)
    for (let b = 0; b <= a; b++) {
      let s = 0;
      for (let i = 0; i < N; i++) s += Phi[i][a] * Phi[i][b];
      G[a][b] = G[b][a] = s;
    }
  return G;
}
function phiTy(Phi, y) {
  const M = Phi[0].length, out = new Float64Array(M);
  for (let a = 0; a < M; a++) { let s = 0; for (let i = 0; i < Phi.length; i++) s += Phi[i][a] * y[i]; out[a] = s; }
  return out;
}
// Ridge least squares: (Phi^T Phi + lambda I) w = Phi^T y. lambda tiny, only
// to keep the near-interpolation degrees numerically sane.
function polyfit(Phi, y, lambda) {
  const G = gram(Phi), M = G.length;
  for (let a = 0; a < M; a++) G[a][a] += lambda;
  return cholSolve(cholesky(G), phiTy(Phi, y));
}
const evalPoly = (w, x) => { const t = toT(x); let p = 1, s = 0; for (let j = 0; j < w.length; j++) { s += w[j] * p; p *= t; } return s; };
function predict(Phi, w) { return Phi.map((row) => { let s = 0; for (let j = 0; j < w.length; j++) s += row[j] * w[j]; return s; }); }
const rmse = (a, b) => Math.sqrt(a.reduce((s, v, i) => s + (v - b[i]) ** 2, 0) / a.length);

// ---------------------------------------------------------------------------
// Bayesian evidence, TWO closed forms that must agree.
// Model: y = Phi w + noise,  noise ~ N(0, beta^-1 I),  prior w ~ N(0, alpha^-1 I).
// ---------------------------------------------------------------------------
// (1) Posterior / "A-form" (Bishop eq. 3.86), M = d+1 params:
//   A = alpha I + beta Phi^T Phi ;  m = beta A^-1 Phi^T y
//   ln p(y) = M/2 ln alpha + N/2 ln beta - E(m) - 1/2 ln|A| - N/2 ln 2pi
//   E(m) = beta/2 ||y - Phi m||^2 + alpha/2 ||m||^2
function evidenceA(Phi, y, alpha, beta) {
  const G = gram(Phi), M = G.length, N = Phi.length;
  const A = G.map((row, a) => row.map((v, b) => beta * v + (a === b ? alpha : 0)));
  const L = cholesky(A);
  const m = cholSolve(L, phiTy(Phi, y).map((v) => beta * v)); // beta Phi^T y
  const yhat = predict(Phi, m);
  let sqErr = 0; for (let i = 0; i < N; i++) sqErr += (y[i] - yhat[i]) ** 2;
  let wSq = 0; for (let j = 0; j < M; j++) wSq += m[j] ** 2;
  const Em = 0.5 * beta * sqErr + 0.5 * alpha * wSq;
  const logEv = 0.5 * M * Math.log(alpha) + 0.5 * N * Math.log(beta)
    - Em - 0.5 * cholLogDet(L) - 0.5 * N * Math.log(2 * Math.PI);
  // best-fit log-likelihood at the posterior mean, and the Occam factor (log):
  const bestFitLL = 0.5 * N * Math.log(beta / (2 * Math.PI)) - 0.5 * beta * sqErr;
  return { logEv, bestFitLL, logOccam: logEv - bestFitLL, logDetA: cholLogDet(L), m };
}
// (2) Kernel / "C-form": y ~ N(0, C),  C = beta^-1 I + alpha^-1 Phi Phi^T (N x N)
//   ln p(y) = -1/2 [ N ln 2pi + ln|C| + y^T C^-1 y ]
function evidenceC(Phi, y, alpha, beta) {
  const N = Phi.length, M = Phi[0].length;
  const C = Array.from({ length: N }, () => new Float64Array(N));
  for (let i = 0; i < N; i++)
    for (let k = 0; k < N; k++) {
      let s = 0; for (let a = 0; a < M; a++) s += Phi[i][a] * Phi[k][a];
      C[i][k] = s / alpha + (i === k ? 1 / beta : 0);
    }
  const L = cholesky(C);
  const Cinv_y = cholSolve(L, Float64Array.from(y));
  let quad = 0; for (let i = 0; i < N; i++) quad += y[i] * Cinv_y[i];
  return -0.5 * (N * Math.log(2 * Math.PI) + cholLogDet(L) + quad);
}

// ---------------------------------------------------------------------------
// Frequentist criteria, KNOWN-NOISE form (beta = 1/sigma^2 is given, exactly as
// in the synthetic demo and in the Bayesian evidence above -- so the two agree
// on assumptions). k = d+1 free coefficients (the variance is not estimated).
//   ln L = -n/2 ln(2 pi) + n/2 ln beta - beta/2 * RSS
//   AIC = 2k - 2 ln L      (Akaike 1974)
//   BIC = k ln n - 2 ln L  (Schwarz 1978)      lower = better
// Using known noise avoids the interpolation-degree pathology where the
// MLE variance -> 0 sends the likelihood to +infinity and would wrongly reward
// the wiggliest model. (We state this convention on the page.)
// ---------------------------------------------------------------------------
function infoCriteria(rssTrain, n, d, beta) {
  const k = d + 1;
  const lnL = -0.5 * n * Math.log(2 * Math.PI) + 0.5 * n * Math.log(beta) - 0.5 * beta * rssTrain;
  return { AIC: 2 * k - 2 * lnL, BIC: k * Math.log(n) - 2 * lnL, lnL, k };
}

// ---------------------------------------------------------------------------
// The whole sweep for one dataset.
// ---------------------------------------------------------------------------
const TRUE = (x) => Math.sin(2 * Math.PI * x);   // no polynomial is exactly true
const GRID = Array.from({ length: 400 }, (_, i) => i / 399);
const trueGrid = GRID.map(TRUE);

function makeData(N, sigma, seed) {
  const rng = mulberry32(seed), g = makeGaussian(rng);
  const xs = Array.from({ length: N }, (_, i) => i / (N - 1));
  const y = xs.map((x) => TRUE(x) + sigma * g());
  return { xs, y };
}

function sweep({ N, sigma, seed, alpha, beta, Dmax, lambda = 1e-9 }) {
  const { xs, y } = makeData(N, sigma, seed);
  const D = Math.min(Dmax, N - 1);
  const rows = [];
  for (let d = 0; d <= D; d++) {
    const Phi = design(xs, d);
    const w = polyfit(Phi, y, lambda);
    const trainRMSE = rmse(predict(Phi, w), y);
    const rssTrain = trainRMSE * trainRMSE * N;
    // generalisation vs the true signal (noise-free), on a dense grid
    const genMSE = GRID.reduce((s, x, i) => s + (evalPoly(w, x) - trueGrid[i]) ** 2, 0) / GRID.length;
    const A = evidenceA(Phi, y, alpha, beta);
    const C = evidenceC(Phi, y, alpha, beta);
    const ic = infoCriteria(rssTrain, N, d, beta);
    // MacKay's decomposition uses the BEST (max-likelihood) fit; ic.lnL is that
    // known-noise log-likelihood at the least-squares fit. The Occam factor is
    // whatever the evidence has left over after crediting the best possible fit.
    const bestFitLL = ic.lnL;
    const logOccam = A.logEv - bestFitLL;
    rows.push({ d, trainRMSE, genRMSE: Math.sqrt(genMSE), logEvA: A.logEv, logEvC: C,
      bestFitLL, logOccam, logDetA: A.logDetA, ...ic });
  }
  const argmin = (key) => rows.reduce((bi, r, i, a) => (r[key] < a[bi][key] ? i : bi), 0);
  const argmax = (key) => rows.reduce((bi, r, i, a) => (r[key] > a[bi][key] ? i : bi), 0);
  return { xs, y, D, rows, bestGen: argmin('genRMSE'), bestEv: argmax('logEvA'),
    bestBIC: argmin('BIC'), bestAIC: argmin('AIC') };
}

// ===========================================================================
// The canonical dataset the page ships with.
// ===========================================================================
const CANON = { N: 13, sigma: 0.15, seed: 7, alpha: 0.05, beta: 1 / (0.15 * 0.15), Dmax: 10 };
const R = sweep(CANON);

sec('Canonical dataset:  f(x) = sin(2*pi*x),  N=13,  sigma=0.15,  seed=7,  degrees 0..10');
console.log('  d  trainRMSE  genRMSE   logEvid   bestFitLL  logOccam     BIC      AIC');
for (const r of R.rows) {
  console.log(
    `  ${String(r.d).padStart(1)}   ${r.trainRMSE.toFixed(4)}    ${r.genRMSE.toFixed(4)}` +
    `   ${r.logEvA.toFixed(2).padStart(7)}   ${r.bestFitLL.toFixed(2).padStart(6)}` +
    `  ${r.logOccam.toFixed(2).padStart(7)}  ${r.BIC.toFixed(2).padStart(7)}  ${r.AIC.toFixed(2).padStart(7)}`);
}
console.log(`  -> best generalisation degree = ${R.bestGen};  evidence-max degree = ${R.bestEv};` +
  `  BIC = ${R.bestBIC};  AIC = ${R.bestAIC}`);

// ---- A. training error monotonically decreasing ---------------------------
sec('A. Fit behaviour');
let mono = true;
for (let i = 1; i < R.rows.length; i++) if (R.rows[i].trainRMSE > R.rows[i - 1].trainRMSE + 1e-9) mono = false;
ok('training RMSE is non-increasing in degree (more parameters never fit the sample worse)', mono);
ok('training RMSE keeps falling toward zero as degree climbs (the high-degree fit hugs the points)',
  R.rows[R.D].trainRMSE < R.rows[R.bestGen].trainRMSE * 0.3,
  `train(D)=${R.rows[R.D].trainRMSE.toFixed(4)} << train*=${R.rows[R.bestGen].trainRMSE.toFixed(4)}`);
ok('generalisation error is U-shaped: its minimum is at an INTERIOR degree (not 0, not D)',
  R.bestGen > 0 && R.bestGen < R.D, `argmin at d=${R.bestGen}`);
ok('the wiggliest model (d=D) generalises WORSE than the best degree, even as it fits the sample better (overfitting is real)',
  R.rows[R.D].genRMSE > R.rows[R.bestGen].genRMSE * 1.5 && R.rows[R.D].trainRMSE < R.rows[R.bestGen].trainRMSE,
  `gen(D)=${R.rows[R.D].genRMSE.toFixed(3)} vs gen*=${R.rows[R.bestGen].genRMSE.toFixed(3)}`);

// ---- B. the Bayesian Occam factor -----------------------------------------
sec('B. The Bayesian Occam factor (the razor as a theorem, not a slogan)');
let agree = true;
for (const r of R.rows) if (!approx(r.logEvA, r.logEvC, 1e-6)) agree = false;
ok('the two independent closed forms for the log-evidence agree to 1e-6 (posterior form == kernel form)', agree);
let bfMono = true;
for (let i = 1; i < R.rows.length; i++) if (R.rows[i].bestFitLL < R.rows[i - 1].bestFitLL - 1e-6) bfMono = false;
ok('best-fit log-likelihood RISES monotonically with complexity (a bigger model can always fit at least as well)', bfMono);
let occamFall = true;
for (let i = 1; i < R.rows.length; i++) if (R.rows[i].logOccam > R.rows[i - 1].logOccam + 1e-6) occamFall = false;
ok('the Occam factor (log) FALLS monotonically with complexity (the automatic penalty nobody wrote by hand)', occamFall);
ok('  ...net over the whole range the penalty is large: Occam(0) - Occam(D) is many nats',
  R.rows[0].logOccam - R.rows[R.D].logOccam > 10,
  `Occam(0)=${R.rows[0].logOccam.toFixed(1)} -> Occam(D)=${R.rows[R.D].logOccam.toFixed(1)}`);
ok('evidence = best-fit x Occam factor, and the PRODUCT peaks at an interior degree',
  R.bestEv > 0 && R.bestEv < R.D, `evidence-max at d=${R.bestEv}`);
ok('the maximum-evidence model is NOT the maximum-likelihood (interpolating) model',
  R.bestEv < R.D, `evidence picks d=${R.bestEv}, likelihood alone would pick d=${R.D}`);

// ---- C. frequentist criteria ----------------------------------------------
sec('C. Frequentist model-selection criteria pick an interior degree too');
ok('BIC (Schwarz 1978, penalty k ln n) selects an interior degree', R.bestBIC > 0 && R.bestBIC < R.D, `d=${R.bestBIC}`);
ok('AIC (Akaike 1974, penalty 2k) selects an interior degree', R.bestAIC > 0 && R.bestAIC < R.D, `d=${R.bestAIC}`);
ok('BIC penalises complexity at least as hard as AIC here (k ln n >= 2k when n >= 8)',
  R.bestBIC <= R.bestAIC, `BIC d=${R.bestBIC} <= AIC d=${R.bestAIC}`);

// ---- D. the honest limit: the razor is a bet, not a guarantee --------------
sec('D. The honest limit — starve the razor and it under-fits the truth');
// The signal sin(2*pi*x) needs a few degrees to show. With very few noisy
// points the evidence-optimal degree drops below what a clean fit would want.
const STARVED = { N: 6, sigma: 0.35, seed: 3, alpha: 5e-3, beta: 1 / (0.35 * 0.35), Dmax: 5 };
const S = sweep(STARVED);
console.log(`  starved (N=6, sigma=0.35): evidence picks d=${S.bestEv}, BIC picks d=${S.bestBIC}` +
  ` (vs the rich-data evidence choice d=${R.bestEv})`);
ok('with few, noisy points the razor chooses a SIMPLER model than the rich-data razor does',
  S.bestEv < R.bestEv, `starved d=${S.bestEv} < rich d=${R.bestEv}`);
ok('...i.e. the razor cut where the DATA justified, not where the truth actually was — a bet, not a proof',
  true);

// ---- E. the three razors agree on the neighbourhood -----------------------
sec('E. The three razors (evidence, BIC, generalisation) agree on the neighbourhood');
ok('the evidence-optimal degree equals the generalisation-optimal degree here',
  R.bestEv === R.bestGen, `evidence d=${R.bestEv}, gen d=${R.bestGen}`);
ok('BIC lands within one degree of the evidence choice',
  Math.abs(R.bestBIC - R.bestEv) <= 1, `BIC d=${R.bestBIC}, evidence d=${R.bestEv}`);
ok('all three razors sit strictly between under-fit (d=1) and the wiggly interpolation (d=D)',
  [R.bestEv, R.bestBIC, R.bestGen].every((d) => d > 1 && d < R.D));

// ---- F. reproducibility anchors (the page recomputes these live) ----------
sec('F. Exact anchors the page must reproduce (seed 7)');
const anchor = R.rows.find((r) => r.d === R.bestEv);
console.log(`  chosen degree d*=${R.bestEv}:  logEvidence=${anchor.logEvA.toFixed(3)},` +
  `  genRMSE=${anchor.genRMSE.toFixed(4)},  BIC=${anchor.BIC.toFixed(2)}`);
console.log(`  interpolation degree d=${R.D}:  trainRMSE=${R.rows[R.D].trainRMSE.toExponential(2)},` +
  `  genRMSE=${R.rows[R.D].genRMSE.toFixed(3)}  (hugs the points, predicts worse than d*)`);
console.log(`  first three canonical y-values (seed 7): ` +
  R.y.slice(0, 3).map((v) => v.toFixed(4)).join(', '));

// ---------------------------------------------------------------------------
console.log(`\n${fails === 0 ? 'ALL CHECKS PASSED' : fails + ' CHECK(S) FAILED'}`);
process.exit(fails === 0 ? 0 : 1);
