File size: 5,546 Bytes
25055a4 | 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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 | """Claim 6: evaluate Algorithms 3 (DoWS) and 4 (T-DoWS) against a primal-dual
baseline on SVM classification with real datasets.
The logbook stated it does not reproduce the real-data SVM comparison and ran no
SVM experiment. Two of the three datasets are run here; MNIST 3-vs-5 could not be
retrieved (OpenML returned HTTP 504).
SVM as constrained optimisation, which is the form the algorithms address:
minimise f(w,b) = 0.5||w||^2
subject to y_i (w.x_i + b) >= 1 (one constraint per sample)
Randomised feasibility: sample a violated constraint and project onto its
halfspace, rather than forming the full constraint set.
"""
import json, pickle, numpy as np
RES = {}
def load():
D = pickle.load(open("svm_data.pkl", "rb"))
out = {}
for k, (X, y) in D.items():
X = (X-X.mean(0))/(X.std(0)+1e-9)
out[k] = (X, y.astype(float))
return out
C_SLACK = 1.0
def obj(w, b, xi=None):
"""SOFT-margin objective. Hard margin is INFEASIBLE on banknote (min margin
-0.767 under an exact LinearSVC fit), so violations there could never reach 0
and the feasibility comparison was measuring an infeasible program."""
v = 0.5*float(w @ w)
return v+C_SLACK*float(np.sum(xi)) if xi is not None else v
def viol(X, y, w, b, xi):
return float(np.maximum(0.0, 1.0-xi-y*(X @ w+b)).max())
def project_one(X, y, w, b, xi, i):
"""Project (w,b,xi_i) onto y_i(w.x_i+b) + xi_i >= 1, xi_i >= 0."""
a = y[i]*X[i]; c = y[i]
g = a @ w+c*b+xi[i]-1.0
if g < 0:
n2 = a @ a+c*c+1.0
lam = -g/max(n2, 1e-12)
w = w+lam*a; b = b+lam*c; xi[i] = xi[i]+lam
xi[i] = max(0.0, xi[i])
return w, b
def run(X, y, alg, T=4000, seed=0, nproj=None):
"""nproj scales with the CONSTRAINT COUNT. Claim 4 of this same paper (already
verified) says infeasibility decays geometrically in the NUMBER of feasibility
updates; with a fixed 5 projections/step over 569-1372 constraints most
constraints are almost never visited and violation plateaus."""
rng = np.random.default_rng(seed)
n, d = X.shape
if nproj is None: nproj = max(5, n//4)
w = np.zeros(d); b = 0.0; w0 = w.copy(); xi = np.ones(n)
G2 = 1e-12; rmax = 1e-8
lam_d = 0.0
hist = []
for t in range(1, T+1):
g = w.copy() # grad of 0.5||w||^2
if alg == "primal_dual":
i = int(rng.integers(n))
s = 1.0-y[i]*(X[i] @ w+b)
gv = -y[i]*X[i] if s > 0 else np.zeros(d)
gb = -y[i] if s > 0 else 0.0
eta = 0.5/np.sqrt(t)
w = w-eta*(g+lam_d*gv); b = b-eta*(lam_d*gb)
xi[i] = max(0.0, xi[i]-eta*(C_SLACK-lam_d))
lam_d = max(0.0, lam_d+eta*(s-xi[i]))
else:
G2 += g @ g
rmax = max(rmax, float(np.linalg.norm(w-w0)))
if alg == "dows":
eta = rmax/np.sqrt(G2)
else: # t_dows: tamed, no bounded-Y assumption
eta = rmax/np.sqrt(G2*np.log(np.e+t))
w = w-eta*g
xi = np.maximum(0.0, xi-eta*C_SLACK)
for _ in range(nproj): # randomised feasibility updates
i = int(rng.integers(n))
w, b = project_one(X, y, w, b, xi, i)
if t % 200 == 0:
hist.append({"t": t, "obj": obj(w, b, xi), "max_violation": viol(X, y, w, b, xi)})
acc = float(np.mean(np.sign(X @ w+b) == y))
return w, b, hist, acc
def main():
data = load()
rows = []
for name, (X, y) in data.items():
for alg in ("dows", "t_dows", "primal_dual"):
o, v, a = [], [], []
for s in range(3):
w, b, h, acc = run(X, y, alg, seed=s)
o.append(h[-1]["obj"]); v.append(h[-1]["max_violation"]); a.append(acc)
rows.append({"dataset": name, "n": int(X.shape[0]), "d": int(X.shape[1]),
"algorithm": alg, "final_objective": round(float(np.mean(o)), 5),
"final_max_violation": round(float(np.mean(v)), 6),
"train_accuracy": round(float(np.mean(a)), 4)})
print(" %-14s %-12s objective=%9.4f max violation=%9.5f accuracy=%.4f"
% (name, alg, np.mean(o), np.mean(v), np.mean(a)), flush=True)
RES["claim6_svm"] = {"rows": rows, "seeds": 3, "iterations": 4000,
"datasets_run": sorted(data.keys()),
"mnist_note": "MNIST 3-vs-5 unavailable: OpenML returned HTTP 504"}
# comparison summary
summ = []
for name in data:
sub = {r["algorithm"]: r for r in rows if r["dataset"] == name}
summ.append({"dataset": name,
"dows_beats_pd_on_violation": bool(sub["dows"]["final_max_violation"] <= sub["primal_dual"]["final_max_violation"]),
"t_dows_beats_pd_on_violation": bool(sub["t_dows"]["final_max_violation"] <= sub["primal_dual"]["final_max_violation"]),
"dows_acc_minus_pd": round(sub["dows"]["train_accuracy"]-sub["primal_dual"]["train_accuracy"], 4)})
print(" [%s] DoWS beats PD on feasibility: %s | T-DoWS: %s | accuracy delta %+.4f"
% (name, summ[-1]["dows_beats_pd_on_violation"], summ[-1]["t_dows_beats_pd_on_violation"],
summ[-1]["dows_acc_minus_pd"]), flush=True)
RES["claim6_svm"]["summary"] = summ
json.dump(RES, open("svm_results.json", "w"), indent=1)
if __name__ == "__main__":
main(); print("DONE")
|