File size: 2,599 Bytes
c881b77 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | """Claim 2 verification: Proposition 5.1 & Corollary 5.2.
Prop 5.1: p_hat_{mu,K}(x_i) = 1/(N V_d mu_i^d) * (1/K Sum_k k^{1/d})^d is a local
density estimator (asymptotically p(x_i)).
Cor 5.2: at ICDM convergence, mu_i ~ mu_bar for all i => p_hat equal everywhere
(density uniformized).
We verify numerically:
(a) p_hat_{mu,K} correlates with the true density in a mixture of Gaussians.
(b) after ICDM, the spread of mu_i collapses (std -> ~0) while raw std is large,
confirming density gradient removal.
"""
import numpy as np
import sys, os
sys.path.insert(0, os.path.dirname(__file__))
from gicdm_core import pairwise_sq_dists, icdm_scaling, knn_distances
def unit_ball_volume(d):
from math import gamma, pi
return (pi ** (d / 2)) / gamma(d / 2 + 1)
def p_hat_mu_k(X, K):
D = pairwise_sq_dists(X)
mu = knn_distances(D, K, self_included=True).mean(axis=1)
N, d = X.shape
Vd = unit_ball_volume(d)
w = (np.sum([k ** (1.0 / d) for k in range(1, K + 1)]) / K) ** d
return 1.0 / (N * Vd * mu ** d) * w, mu
def run():
rng = np.random.default_rng(0)
# Mixture of two Gaussians with different variances -> different densities
d = 20
n1, n2 = 800, 800
X = np.vstack([
rng.normal(0, 0.5, size=(n1, d)),
rng.normal(3, 2.0, size=(n2, d)),
])
true_dens = np.concatenate([
(2 * np.pi * 0.25) ** (-d / 2) * np.ones(n1),
(2 * np.pi * 4.0) ** (-d / 2) * np.ones(n2),
])
K = 20
phat, mu = p_hat_mu_k(X, K)
# correlation between estimator and true density (log scale, robust)
log_corr = np.corrcoef(np.log(phat), np.log(true_dens))[0, 1]
# ICDM convergence: spread of mu before/after
mu_before = mu.copy()
delta, mu_after = icdm_scaling(pairwise_sq_dists(X), K, n_iter=10, return_mu=True)
res = dict(
d=d, N=len(X), K=K,
log_corr_density=float(log_corr),
mu_before_std=float(mu_before.std()),
mu_before_cv=float(mu_before.std() / mu_before.mean()),
mu_after_std=float(mu_after.std()),
mu_after_cv=float(mu_after.std() / mu_after.mean()),
)
print("Prop 5.1 log-correlation p_hat vs true density:", round(res['log_corr_density'], 3))
print("mu_i std before ICDM:", round(res['mu_before_std'], 4),
"| after ICDM:", round(res['mu_after_std'], 5))
print("mu_i CV before ICDM:", round(res['mu_before_cv'], 4),
"| after ICDM:", round(res['mu_after_cv'], 5))
return res
if __name__ == "__main__":
import json
res = run()
json.dump(res, open("results/claim2_density.json", "w"))
|