关于「稀疏也能补全:低秩矩阵需要多少个观测条目」,《稀疏购买记录的偏好补全》给出的定量结论是什么?

结论:第一章扫描观测比例:40 乘 40、秩二的矩阵在观测数为自由度 2.05 倍时误差中位数降到 0.0021,并用精确二项尾概率说明所需观测与 n r ln n 之比从 0.677 缓降到 0.436,对数因子去不掉。

数据口径:书中顾客数、商品数、口味维度与购买概率均为示意参数;全部计算由书中程序生成;本书属于非个人化经营建议,推荐流程只用店铺自有数据,不外传个人数据,不做跨平台追踪。 第七章考辨《周易·系辞上》「方以类聚,物以群分」与斯皮尔曼 1904 年的一般因素,指出纯分群与混合成员下两种模型各有胜负。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.0021, 2.05, 40

n = 40, rank 2, dof = 156, n r ln n = 295
pmean mm/dofmedian errsuccess
0.0693.00.6024.50200/5
0.10160.21.0311.11190/5
0.15247.41.598.21531/5
0.20319.42.050.00213/5
0.25402.82.580.00015/5
0.30482.43.090.00005/5
0.40642.44.120.00005/5
查看完整验算程序
# Chapter 1. p12: recovery error against the observed share.
# Model: a 40 x 40 matrix of rank 2 with Gaussian factors (an
# incoherent matrix, illustrative). Entries are observed independently
# with probability p; alternating least squares (rank 2, ridge 1e-5,
# 80 sweeps, spectral start as in p33) fills the rest. Error is the
# relative root-mean-square error on the unobserved cells; success
# means error below 0.01. Five fixed seeds per row.
import math
import random


def dot(a, b):
    return math.fsum(x * y for x, y in zip(a, b))


def solve(A, b):
    # Gaussian elimination with partial pivoting for a small system
    n = len(b)
    M = [list(A[i]) + [b[i]] for i in range(n)]
    for k in range(n):
        p = max(range(k, n), key=lambda i: abs(M[i][k]))
        M[k], M[p] = M[p], M[k]
        for i in range(k + 1, n):
            f = M[i][k] / M[k][k]
            M[i] = [M[i][j] - f * M[k][j] for j in range(n + 1)]
    x = [0.0] * n
    for i in range(n - 1, -1, -1):
        s = math.fsum(M[i][j] * x[j] for j in range(i + 1, n))
        x[i] = (M[i][n] - s) / M[i][i]
    return x


def update(trip, F, r, lam, prior=None):
    # weighted ridge step for one row: minimise
    # sum w (y - f.x)^2 + lam |x - prior|^2 over x
    pr = prior if prior is not None else [0.0] * r
    A = [[math.fsum(w * F[j][a] * F[j][b] for j, _, w in trip)
          + (lam if a == b else 0.0) for b in range(r)]
         for a in range(r)]
    y = [math.fsum(w * F[j][a] * v for j, v, w in trip) + lam * pr[a]
         for a in range(r)]
    return solve(A, y)


def als(nu, ni, obs, r, lam, iters, seed, V=None, trace=None):
    # alternating least squares on (u, i, value, weight) tuples
    rng = random.Random(seed)
    if V is None:
        V = [[rng.gauss(0.0, 1.0) for _ in range(r)] for _ in range(ni)]
    bu = [[] for _ in range(nu)]
    bi = [[] for _ in range(ni)]
    for u, i, x, w in obs:
        bu[u].append((i, x, w))
        bi[i].append((u, x, w))
    U = None
    for t in range(iters):
        U = [update(bu[u], V, r, lam) for u in range(nu)]
        V = [update(bi[i], U, r, lam) for i in range(ni)]
        if trace is not None:
            trace.append((t + 1, U, V))
    return U, V


def factors(n, r, rng):
    return [[rng.gauss(0.0, 1.0) for _ in range(r)] for _ in range(n)]


def product(A, B):
    return [[dot(a, b) for b in B] for a in A]


def mask(nu, ni, p, rng):
    return [(u, i) for u in range(nu) for i in range(ni)
            if rng.random() < p]


def relerr(M, U, V, cells):
    num = math.fsum((dot(U[u], V[i]) - M[u][i]) ** 2 for u, i in cells)
    den = math.fsum(M[u][i] ** 2 for u, i in cells)
    return math.sqrt(num / den)


def rmse(M, U, V, cells):
    num = math.fsum((dot(U[u], V[i]) - M[u][i]) ** 2 for u, i in cells)
    return math.sqrt(num / len(cells))


def orthonormal(cols):
    # Gram-Schmidt on a list of column vectors
    out = []
    for c in cols:
        v = list(c)
        for q in out:
            h = dot(q, v)
            v = [a - h * b for a, b in zip(v, q)]
        nv = math.sqrt(dot(v, v))
        out.append([a / nv for a in v])
    return out


def spectral(nu, ni, cells, r, rng, iters=30):
    # top-r right singular subspace of the rescaled observed matrix:
    # Y[u][i] = x / p for observed cells, 0 elsewhere
    Y = [[0.0] * ni for _ in range(nu)]
    for u, i, x, p in cells:
        Y[u][i] = x / p
    Yt = [list(c) for c in zip(*Y)]
    Q = orthonormal([[rng.gauss(0, 1) for _ in range(ni)]
                     for _ in range(r)])
    for _ in range(iters):
        Q = orthonormal([[dot(row, [dot(y, q) for y in Y]) for row in Yt]
                         for q in Q])
    return [[Q[k][i] for k in range(r)] for i in range(ni)]

n, r = 40, 2
dof = r * (2 * n - r)
print("n = 40, rank 2, dof = {}, n r ln n = {:.0f}".format(
    dof, n * r * math.log(n)))
print("    p   mean m   m/dof   median err   success")
for p in (0.06, 0.10, 0.15, 0.20, 0.25, 0.30, 0.40):
    errs, ms = [], []
    for s in range(5):
        rng = random.Random(20261113 + 101 * s)
        M = product(factors(n, r, rng), factors(n, r, rng))
        seen = mask(n, n, p, rng)
        ss = set(seen)
        rest = [(u, i) for u in range(n) for i in range(n)
                if (u, i) not in ss]
        obs = [(u, i, M[u][i], 1.0) for u, i in seen]
        V0 = spectral(n, n, [(u, i, x, p) for u, i, x, _ in obs], r, rng)
        U, V = als(n, n, obs, r, 1e-5, 80, 7 + s, V=V0)
        errs.append(relerr(M, U, V, rest))
        ms.append(len(seen))
    errs.sort()
    ok = len([e for e in errs if e < 0.01])
    m = math.fsum(ms) / len(ms)
    print("  {:.2f}   {:6.1f}   {:5.2f}     {:.4f}      {}/5".format(
        p, m, m / dof, errs[2], ok))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《低秩矩阵补全与交替最小二乘、稀疏购买记录推断未表态偏好母典》第 1 章「稀疏也能补全:低秩矩阵需要多少个观测条目」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-328 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026328,
  author    = {Fan, Yafu},
  title     = {Low-Rank Matrix Completion and Alternating Least Squares: Inferring Unstated Preferences from Sparse Purchase Records},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

本书其他章节结论