# --- Banc #17977 : instrument -- degre de Fourier REEL + sensibilite hypercube exacte ---
# Reserve #9771 : le degre mesure ici est le VRAI degre de Fourier-Walsh de la table de
# verite complete, pas un proxy de masse de probabilite.
# Reserve #9764 : la saturation de la mesure est testee explicitement (gate P4) avant
# tout verdict. numpy pur, CPU borne, deterministe (rng explicites, aucun alea cache).
import itertools
TOL_FOURIER = 1e-9 # pre-enregistre : coefficients multiples de 2^{1-n}, tolerance stricte legitime
def hypercube_inputs(n):
"""Encodage pre-defini : b in {0,1}^n -> x = 1 - 2*b in {-1,+1}^n (ordre lexicographique)."""
B = np.array(list(itertools.product([0, 1], repeat=n)), dtype=float)
return 1.0 - 2.0 * B
def fourier_degree(table_pm1, n):
"""Degre de Fourier-Walsh REEL de f : {-1,+1}^n -> {-1,+1} (table sur l'hypercube ordonne).
f_hat(S) = 2^{-n} * sum_x f(x) * chi_S(x), chi_S(x) = prod_{i in S} x_i.
deg(f) = max{ |S| : |f_hat(S)| > TOL_FOURIER }. Constante -> deg = 0.
"""
X = hypercube_inputs(n)
deg = 0
for k in range(n + 1):
for S in itertools.combinations(range(n), k):
chi = np.prod(X[:, list(S)], axis=1) if S else np.ones(len(X))
if abs(float(np.mean(table_pm1 * chi))) > TOL_FOURIER:
deg = max(deg, k)
return deg
def hypercube_sensitivity(table_pm1, n):
"""Sensibilite EXACTE s_x(f) sur l'hypercube Q_n (definition de Huang).
Distincte de la sensibilite sur graphe de transition observe (banc legacy,
ict.sensitivity.local_sensitivity) : ici le voisinage est TOUJOURS l'ensemble
des n voisins Hamming-1 de l'hypercube, sans observation ni lissage.
"""
X = hypercube_inputs(n)
index = {tuple(x): i for i, x in enumerate(X)}
s = np.zeros(len(X), dtype=int)
for i, x in enumerate(X):
flips = 0
for j in range(n):
x_nb = x.copy()
x_nb[j] = -x_nb[j]
flips += int(table_pm1[index[tuple(x_nb)]] != table_pm1[i])
s[i] = flips
return s
# --- Petit MLP numpy (CPU borne, deterministe) ---
class TinyMLP:
"""MLP n -> hidden(tanh) -> 1 (lineaire), gradient manuel, Adam externe."""
def __init__(self, n, hidden=16, seed=None):
r = np.random.default_rng(seed)
self.W1 = r.uniform(-1.0, 1.0, size=(n, hidden)) / np.sqrt(n)
self.b1 = np.zeros(hidden)
self.W2 = r.uniform(-1.0, 1.0, size=hidden) / np.sqrt(hidden)
self.b2 = np.zeros(1)
self._X = None
self._h = None
def forward(self, X):
self._X = X
self._h = np.tanh(X @ self.W1 + self.b1)
return self._h @ self.W2 + self.b2[0]
def params(self):
return [self.W1, self.b1, self.W2, self.b2]
def backward(self, dlogit):
gW2 = self._h.T @ dlogit
gb2 = np.array([dlogit.sum()])
dh = np.outer(dlogit, self.W2) * (1.0 - self._h ** 2)
gW1 = self._X.T @ dh
gb1 = dh.sum(axis=0)
return [gW1, gb1, gW2, gb2]
def _sigmoid(v):
return 0.5 * (1.0 + np.tanh(0.5 * v)) # stable
def bce_with_logits(z, y, w=None):
"""BCE moyenne avec logits, y in {-1,+1} : L = mean softplus(-y*z).
w : poids optionnels par point (normalises, moyenne 1) -- ponderation equilibree
par classe pour eviter que les cibles desequilibrees (OR/AND : 2^n - 1 contre 1)
ne convergent vers la constante vacuous (amendement pre-execution v2).
dL/dz_i = -y_i * sigma(-y_i*z_i) * w_i / m (sigma(-u) = 1 - sigma(u)).
"""
u = -y * z
if w is None:
w = np.ones_like(z)
loss = float(np.mean(w * np.logaddexp(0.0, u)))
dz = -(w * y * _sigmoid(u)) / len(z)
return loss, dz
def _class_balance_weights(ytr):
"""Poids 1/(2*freq_classe), normalises a la moyenne 1 (ponderation equilibree)."""
frac_pos = float(np.mean(ytr > 0))
w = np.where(ytr > 0, 0.5 / max(frac_pos, 1e-9), 0.5 / max(1.0 - frac_pos, 1e-9))
return w / w.mean()
def train_mlp(n, Xtr, ytr, *, regime, seed, steps=400, lr=0.05, lam=0.5):
"""Entraine un TinyMLP ; regime in {'normal', 'adversarial', 'untrained'}.
normal : L = BCE equilibree(g(Xtr), y).
adversarial : L = BCE equilibree(g(Xtr), y) + lam * BCE equilibree(g(x_adv), y)
ou x_adv est le pire voisin Hamming-1 de chaque point train
(adversaire discret exact a rayon 1, label du point propre).
lam = 0.5 (amendement pre-execution v3) : a rayon 1 sur l'hypercube,
le pire voisin porte souvent le label oppose (toujours pour PAR) ;
lam = 1 a ete ecarte en calibration (graines disjointes 11/22) :
a ce poids le terme adversarial bloque l'apprentissage (taux de
degeneres non conserve dans une sortie committee) ; lam = 0.5
(poids a la TRADES) restaure l'apprentissage en conservant la
pression de lissage local.
untrained : reseau a l'initialisation (controle, 0 etape).
"""
net = TinyMLP(n, seed=seed)
if regime == 'untrained':
return net
w = _class_balance_weights(ytr)
params = net.params()
m_a = [np.zeros_like(p) for p in params]
v_a = [np.zeros_like(p) for p in params]
beta1, beta2, eps = 0.9, 0.999, 1e-8
for t in range(1, steps + 1):
z = net.forward(Xtr)
_, dl = bce_with_logits(z, ytr, w)
grads = net.backward(dl)
if regime == 'adversarial':
Xnb = np.repeat(Xtr[:, None, :], n, axis=1).copy()
jj = np.arange(n)
Xnb[:, jj, jj] *= -1.0 # Xnb[i, j] = Xtr[i] avec coord j basculee
znb = net.forward(Xnb.reshape(-1, n)).reshape(len(Xtr), n)
losses_nb = np.logaddexp(0.0, -ytr[:, None] * znb)
worst = np.argmax(losses_nb, axis=1)
X_adv = Xnb[np.arange(len(Xtr)), worst]
z_adv = net.forward(X_adv)
_, dl_adv = bce_with_logits(z_adv, ytr, w)
g_adv = net.backward(dl_adv * lam)
grads = [g + ga for g, ga in zip(grads, g_adv)]
for k, (p, g) in enumerate(zip(params, grads)):
m_a[k] = beta1 * m_a[k] + (1.0 - beta1) * g
v_a[k] = beta2 * v_a[k] + (1.0 - beta2) * (g * g)
mh = m_a[k] / (1.0 - beta1 ** t)
vh = v_a[k] / (1.0 - beta2 ** t)
p -= lr * mh / (np.sqrt(vh) + eps)
return net
# --- Gates instrument : retrouver les valeurs de reference AVANT toute mesure (pattern L934) ---
def _ref_tables(n):
B = np.array(list(itertools.product([0, 1], repeat=n)))
s1 = B.sum(axis=1)
return {
f'dictateur_{n}': (B[:, 0] == 1).astype(int),
f'OR_{n}': (s1 >= 1).astype(int),
f'AND_{n}': (s1 == n).astype(int),
f'MAJ_{n}': (s1 >= n // 2 + 1).astype(int),
f'PAR_{n}': (s1 % 2).astype(int),
}
# valeurs classiques, verifiees a la main. MAJ_3 : s_max = 2 (les points de poids 1 et 2
# ont exactement 2 voisins qui basculent la majorite ; 2 >= sqrt(3), Huang tient). Une
# premiere version de ce gate attendait s_max = 3 par erreur de calcul manuel -- c'est le
# gate qui a raison, correction apportee AVANT toute mesure du banc.
gates_attendus = {
'dictateur_4': (1, 1),
'OR_4': (4, 4),
'MAJ_3': (3, 2),
'PAR_4': (4, 4),
}
print('=== Gates instrument (valeurs de reference) ===')
all_gates_ok = True
for name, (deg_att, smax_att) in gates_attendus.items():
n_g = int(name[-1])
tab = 1.0 - 2.0 * _ref_tables(n_g)[name].astype(float)
d_g = fourier_degree(tab, n_g)
s_g = int(hypercube_sensitivity(tab, n_g).max())
ok = (d_g == deg_att) and (s_g == smax_att)
all_gates_ok &= ok
print(f' {name:>12} : deg={d_g} (attendu {deg_att}), s_max={s_g} (attendu {smax_att}) -> {"OK" if ok else "ECHEC"}')
# Verification EXHAUSTIVE du theoreme de Huang sur n=3 : les 256 fonctions booleennes
n_viol_huang = 0
for v in range(2 ** (2 ** 3)):
tab = 1.0 - 2.0 * np.array([(v >> i) & 1 for i in range(8)], dtype=float)
if np.all(tab == tab[0]):
continue # constante : deg = 0, inegalite triviale
d_h = fourier_degree(tab, 3)
s_h = int(hypercube_sensitivity(tab, 3).max())
if s_h < np.sqrt(d_h) - 1e-12:
n_viol_huang += 1
print(f' theoreme Huang verifie exhaustivement sur les 256 fonctions de n=3 : {n_viol_huang} violation(s)')
all_gates_ok &= (n_viol_huang == 0)
# Gate optimiseur (amendements v2/v3) : le gradient corrige + ponderation equilibree
# doivent laisser le regime NORMAL fitter PARFAITEMENT une cible complete (graine de
# calibration 11, disjointe des graines de test), et le regime ADVERSARIAL lam=0.5
# doit rester apprenable sur une cible equilibree (train_acc >= 0.9).
_tab_maj3 = 1.0 - 2.0 * _ref_tables(3)['MAJ_3'].astype(float)
_X3 = hypercube_inputs(3)
_net_g = train_mlp(3, _X3, _tab_maj3, regime='normal', seed=2011, steps=600, lr=0.1)
_acc_norm = float(np.mean(np.where(_net_g.forward(_X3) >= 0, 1.0, -1.0) == _tab_maj3))
_net_a = train_mlp(3, _X3, _tab_maj3, regime='adversarial', seed=2011, steps=600, lr=0.1)
_acc_adv = float(np.mean(np.where(_net_a.forward(_X3) >= 0, 1.0, -1.0) == _tab_maj3))
print(f' gate optimiseur (MAJ_3 complet, graine 11 disjointe) : train_acc normal = {_acc_norm:.3f}, '
f'adversarial (lam=0.5) = {_acc_adv:.3f} (attendus 1.0 / >= 0.9)')
all_gates_ok &= (_acc_norm == 1.0) and (_acc_adv >= 0.9)
if not all_gates_ok:
raise RuntimeError('Gates instrument en echec : ne pas mesurer avant correction.')
print('Gates instrument PASS : l instrument discrimine (deg et s_max exacts), respecte Huang '
'sur n=3, et l optimiseur converge (normal ET adversarial lam=0.5).')