Spaces:
Running on Zero
Running on Zero
File size: 11,226 Bytes
80af343 | 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 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 | """MarginGraph demo core: basket -> relevant add-ons -> margin-safe pick of 2.
Self-contained (numpy + pandas only) so it runs on a free CPU Space.
Stage 1 EASE item-item model (Steck 2019). On Online Retail II it is the
strongest single baseline in the main repo (test Hit@10 31.1%); the
repo's LightGBM reranker beats it (38.1%) but needs the full feature
pipeline, so the demo ships EASE only.
Stage 1b Logistic calibration of the EASE score into p(accept), fitted on
held-out baskets (leave-one-out: hide one item, can we find it?).
Stage 2 Exact solver for <= 2 add-ons: enumerate every feasible single and
pair, maximize sum p * ((1 - lam) * p_bar + lam * w * profit)
subject to margin floor, stock > 0, one discount per item.
Same objective and constraints as margingraph.optimize.solve_enum.
"""
from __future__ import annotations
from dataclasses import dataclass, field
import numpy as np
import pandas as pd
# --------------------------------------------------------------------------
# Stage 1: EASE
# --------------------------------------------------------------------------
def fit_ease(baskets: list[list[int]], n_items: int, lam: float = 250.0) -> np.ndarray:
"""Closed-form EASE weights B (n_items x n_items, zero diagonal)."""
rows = np.concatenate([np.full(len(b), i) for i, b in enumerate(baskets)])
cols = np.concatenate([np.asarray(b, dtype=int) for b in baskets])
X = np.zeros((len(baskets), n_items), dtype=np.float32)
X[rows, cols] = 1.0
G = (X.T @ X).astype(np.float64)
G[np.diag_indices(n_items)] += lam
P = np.linalg.inv(G)
B = -P / np.diag(P)[None, :]
B[np.diag_indices(n_items)] = 0.0
return B.astype(np.float32)
def scores_for(B: np.ndarray, basket: list[int]) -> np.ndarray:
s = B[basket].sum(axis=0).astype(np.float64)
s[basket] = -np.inf
return s
# --------------------------------------------------------------------------
# Stage 1b: calibration p(accept) = sigmoid(a * score + b * log1p(rank) + c)
# --------------------------------------------------------------------------
def _feat(score: np.ndarray, rank: np.ndarray) -> np.ndarray:
return np.column_stack([score, np.log1p(rank), np.ones_like(score)])
def fit_logistic(X: np.ndarray, y: np.ndarray, l2: float = 1e-3, iters: int = 50) -> np.ndarray:
w = np.zeros(X.shape[1])
for _ in range(iters): # Newton steps
p = 1 / (1 + np.exp(-np.clip(X @ w, -30, 30)))
g = X.T @ (p - y) + l2 * w
H = (X * (p * (1 - p))[:, None]).T @ X + l2 * np.eye(X.shape[1])
step = np.linalg.solve(H, g)
w -= step
if np.abs(step).max() < 1e-8:
break
return w
def loo_events(baskets: list[list[int]], rng: np.random.Generator, max_events: int = 4000):
"""Leave-one-out events from held-out baskets: (context, hidden item)."""
ev = []
for b in baskets:
if len(b) < 2 or len(b) > 50:
continue
h = int(rng.integers(len(b)))
ev.append(([x for k, x in enumerate(b) if k != h], b[h]))
rng.shuffle(ev)
return ev[:max_events]
def calibrate(B: np.ndarray, events, top_n: int = 20) -> dict:
X, y, hits = [], [], {2: 0, 5: 0, 10: 0}
for ctx, hid in events:
s = scores_for(B, ctx)
top = np.argsort(-s)[:top_n]
top = top[np.isfinite(s[top])] # small catalogs: fewer than top_n candidates
X.append(_feat(s[top], np.arange(len(top))))
y.append((top == hid).astype(float))
for k in hits:
hits[k] += int(hid in top[:k])
X, y = np.vstack(X), np.concatenate(y)
w = fit_logistic(X, y, l2=1.0)
p = 1 / (1 + np.exp(-(X @ w)))
n = max(len(events), 1)
return {
"w": w.tolist(),
"p_bar": float(p.mean()),
"n_events": len(events),
"hit": {f"hit@{k}": hits[k] / n for k in hits},
"recall_top_n": float(y.sum() / n),
"top_n": top_n,
}
def proba(w, score: np.ndarray, rank: np.ndarray) -> np.ndarray:
return 1 / (1 + np.exp(-(_feat(score, rank) @ np.asarray(w))))
# --------------------------------------------------------------------------
# Stage 2: margin-aware selection (exact for max_addons <= 2)
# --------------------------------------------------------------------------
@dataclass
class Policy:
lam: float = 1.0 # 0 = pure relevance, 1 = profit-weighted
overstock_weight: float = 1.0 # 1.0-2.0x boost for overstocked items
floor: float = 0.15 # minimum post-discount margin per item
discounts: tuple = (0.0,)
elasticity: float = 1.5 # ASSUMED: p(accept|d) = p * (1 + e * d)
max_addons: int = 2
def solve(p, price, cost, overstock, stock, pol: Policy, p_bar: float) -> list[tuple[int, float]]:
"""Return [(candidate index, discount), ...] maximizing the objective."""
n = len(p)
if n == 0:
return []
d = np.asarray(pol.discounts, dtype=float)
rev = price[:, None] * (1 - d[None, :])
profit = rev - cost[:, None]
pa = np.minimum(1.0, p[:, None] * (1 + pol.elasticity * d[None, :]))
w = np.where(overstock, pol.overstock_weight, 1.0)[:, None]
value = (pa * ((1 - pol.lam) * p_bar + pol.lam * w * profit)).ravel()
ok = (np.repeat((stock > 0)[:, None], len(d), axis=1) & (profit >= pol.floor * rev - 1e-9)).ravel()
item, disc = np.repeat(np.arange(n), len(d)), np.tile(d, n)
idx = np.flatnonzero(ok & (value > 0))
if len(idx) == 0:
return []
v, it = value[idx], item[idx]
best_val, best = v.max(), [int(np.argmax(v))]
if pol.max_addons >= 2 and len(idx) >= 2:
V = v[:, None] + v[None, :]
feas = (it[:, None] != it[None, :]) & np.triu(np.ones((len(idx),) * 2, bool), 1)
V = np.where(feas, V, -np.inf)
a, b = np.unravel_index(np.argmax(V), V.shape)
if V[a, b] > best_val + 1e-12:
best = [int(a), int(b)]
return [(int(it[j]), float(disc[idx][j])) for j in best]
# --------------------------------------------------------------------------
# Model bundle used by the app
# --------------------------------------------------------------------------
@dataclass
class Model:
items: list[str] # stock codes, index = model column
B: np.ndarray
calib: dict
catalog: pd.DataFrame # item, description, price, unit_cost, stock, overstock
pos: dict = field(default_factory=dict)
def __post_init__(self):
self.pos = {s: i for i, s in enumerate(self.items)}
c = self.catalog.drop_duplicates("item").set_index("item").reindex(self.items)
c.index.name = "item"
c["description"] = c["description"].fillna("").astype(str)
c.loc[c["description"] == "", "description"] = c.index[c["description"] == ""]
c["price"] = pd.to_numeric(c["price"], errors="coerce").fillna(0.0)
c["unit_cost"] = pd.to_numeric(c["unit_cost"], errors="coerce").fillna(c["price"])
# Items without a price or stock count are never offered.
c["stock"] = pd.to_numeric(c["stock"], errors="coerce").fillna(0).clip(lower=0)
c.loc[c["price"] <= 0, "stock"] = 0
c["overstock"] = c["overstock"].fillna(False).astype(bool)
self.catalog = c.reset_index()
def recommend(self, basket_codes: list[str], pol: Policy, top_n: int = 20) -> dict:
codes = [str(c).strip().upper() for c in basket_codes]
known = [self.pos[c] for c in dict.fromkeys(codes) if c in self.pos]
unknown = [c for c in codes if c not in self.pos]
if not known:
return {"known": [], "unknown": unknown, "candidates": pd.DataFrame(), "optimized": [], "top": []}
s = scores_for(self.B, known)
top = np.argsort(-s)[:top_n]
top = top[np.isfinite(s[top])]
p = proba(self.calib["w"], s[top], np.arange(len(top)))
c = self.catalog.iloc[top].reset_index(drop=True)
price, cost = c["price"].to_numpy(float), c["unit_cost"].to_numpy(float)
stock, over = c["stock"].to_numpy(float), c["overstock"].to_numpy(bool)
# Why: the basket item with the largest EASE weight toward each candidate.
contrib = self.B[np.ix_(known, top)]
because = [self.catalog["description"].iat[known[k]] for k in contrib.argmax(axis=0)]
cand = pd.DataFrame({
"rank": np.arange(1, len(top) + 1),
"item": c["item"], "description": c["description"],
"p_accept": p, "price": price, "unit_cost": cost,
"margin": np.divide(price - cost, price, out=np.zeros_like(price), where=price > 0), "stock": stock.astype(int), "overstock": over,
"exp_profit": p * (price - cost), "because_of": because,
})
in_stock = [j for j in range(len(top)) if stock[j] > 0]
topk = [(j, 0.0) for j in in_stock[: pol.max_addons]]
opt = solve(p, price, cost, over, stock, pol, self.calib["p_bar"])
return {"known": [self.items[i] for i in known], "unknown": unknown,
"candidates": cand, "optimized": opt, "top": topk}
def offer_stats(cand: pd.DataFrame, chosen, pol: Policy) -> dict:
"""Expected profit / revenue / margin of an offer, plus floor violations."""
ep = er = 0.0
viol = 0
for j, d in chosen:
r = cand.at[j, "price"] * (1 - d)
pr = r - cand.at[j, "unit_cost"]
pa = min(1.0, cand.at[j, "p_accept"] * (1 + pol.elasticity * d))
ep += pa * pr
er += pa * r
viol += int(pr < pol.floor * r - 1e-9)
return {"exp_profit": ep, "exp_revenue": er, "exp_margin": ep / er if er else 0.0,
"hit_prob": sum(min(1.0, cand.at[j, "p_accept"] * (1 + pol.elasticity * d)) for j, d in chosen),
"floor_violations": viol}
def baskets_from_lines(df: pd.DataFrame, basket_col: str, item_col: str) -> list[list[str]]:
df = df[[basket_col, item_col]].dropna().astype(str)
df[item_col] = df[item_col].str.strip().str.upper()
return df.groupby(basket_col, sort=False)[item_col].apply(lambda s: list(dict.fromkeys(s))).tolist()
def train_from_baskets(baskets: list[list[str]], catalog: pd.DataFrame, max_items: int = 2500,
lam: float = 250.0, seed: int = 42, holdout: float = 0.2) -> Model:
"""Fit EASE + calibration on a merchant's own order history.
The last `holdout` share of baskets (file order, so sort by date first)
calibrates p(accept) and gives an honest backtest; then EASE is refit on
all baskets for serving.
"""
counts = pd.Series([i for b in baskets for i in b]).value_counts()
items = counts.index[:max_items].tolist()
pos = {s: i for i, s in enumerate(items)}
enc = [[pos[i] for i in b if i in pos] for b in baskets]
enc = [b for b in enc if len(b) >= 1]
cut = int(len(enc) * (1 - holdout))
train, held = enc[:cut], enc[cut:]
if len(train) < 20 or len(held) < 5:
raise ValueError("need at least ~30 orders with 2+ items to train")
B = fit_ease(train, len(items), lam)
calib = calibrate(B, loo_events(held, np.random.default_rng(seed)))
B = fit_ease(enc, len(items), lam)
return Model(items, B, calib, catalog)
|