半空间类线性规划的公式推导疑惑与代码调试求助

一、公式9.1中$y_i·\langle w,x_i \rangle \geq 1$的理解 #

$y_i·\langle w,x_i \rangle > 0$确实是线性可分的基本要求，保证样本被正确分类。而$\geq 1$是人为引入的间隔约束，核心原因如下：

• 我们要找的不仅是能分开两类的超平面，还要让离超平面最近的样本（支持向量）到超平面的距离尽可能大，这样模型的泛化能力更强。
• 样本点$x_i$到超平面$\langle w,x \rangle + b = 0$（你的代码中已将$x_i$拼接了全1列，因此$w$包含偏置项$b$，即$\langle w,X_i \rangle = w_1x_1 + w_2x_2 + w_3*1$）的距离为$\frac{|\langle w,x_i \rangle + b|}{|w|}$。当样本被正确分类时，$y_i(\langle w,x_i \rangle + b) > 0$，距离可简化为$\frac{y_i(\langle w,x_i \rangle + b)}{|w|}$。
• 为了简化优化问题，我们可以对$w$和$b$进行缩放，让离超平面最近的样本满足$y_i(\langle w,x_i \rangle + b) = 1$，此时所有样本自然满足$y_i(\langle w,x_i \rangle + b) \geq 1$。这种缩放不会改变超平面的位置，因为超平面方程两边同乘非零常数后仍是同一个平面。

二、线性规划实现错误排查与矩阵A的正确形式 #

1. 核心错误：目标函数设置无效 #

你的代码将目标函数设为c = np.zeros(d)，即最小化$0w_1 + 0w_2 + 0*w_3$，这是一个无界优化问题——只要满足约束，$w$可以无限增大，因此linprog会返回一个任意大的$w$，完全无法得到合理的分类超平面。

书中的公式9.1本质是通过线性规划近似最小化$|w|$（通常用L1范数$\sum|w_j|$），这样才能得到有意义的超平面参数。

2. 修正后的代码实现 #

我们以最小化L1范数为例，将问题转换为标准线性规划形式（拆分$w$为正负非负变量）：

import numpy as np
from scipy.optimize import linprog

# 生成训练集
x1 = np.random.randn(2, 40) * 0.3 + 3
x2 = np.random.randn(2, 40) * 0.3 + 1
y1 = np.ones(40)
y2 = -1 * np.ones(40)
X = np.concatenate((x1, x2), axis=1)
ones_column = np.ones((1, X.shape[1]))
X = np.vstack((X, ones_column))  # 每个样本为[x1, x2, 1]^T，共80个样本
Y = np.concatenate((y1, y2))

d = 3
m = 80

# 构造目标函数：最小化L1范数sum(|w_j|)，拆分为w = w_plus - w_minus，目标为sum(w_plus + w_minus)
c = np.concatenate((np.ones(d), np.ones(d)))

# 构造约束：Y[i]*(X[:,i].T @ w) >= 1 → 转换为线性规划的A_ub @ var <= b_ub形式
# var = [w_plus1, w_plus2, w_plus3, w_minus1, w_minus2, w_minus3]
A_ub_full = np.hstack((-Y[:, np.newaxis] * X.T, Y[:, np.newaxis] * X.T))
b_ub_full = -np.ones(m)

# 变量非负约束
bounds = [(0, None) for _ in range(2*d)]

# 求解线性规划
opt = linprog(c=c, A_ub=A_ub_full, b_ub=b_ub_full, bounds=bounds)
w = opt.x[:d] - opt.x[d:]  # 还原w

# 验证分类效果
predictions = np.sign(X.T @ w)
print("分类准确率：", np.mean(predictions == Y))

3. 矩阵A的正确形式 #

书中的约束为$y_i \langle w, x_i \rangle \geq 1$（$x_i$包含全1偏置项），因此矩阵$A$的每行应为$y_i x_i^T$，对应约束$A @ w \geq \mathbf{1}$（全1向量）。

转换为linprog要求的$A_{ub} @ w \leq b_{ub}$形式时，只需取$A_{ub} = -A$、$b_{ub} = -\mathbf{1}$，这和你最初的转换逻辑是对的。

你看到的网站中每行最后一项符号相反，是因为他们的超平面定义为$\langle w,x \rangle - b = 0$（偏置项符号为负），此时约束变为$y_i(\langle w,x_i \rangle - b) \geq 1$，对应的行向量为$y_i [x_{i1}, x_{i2}, -1]$，因此最后一项符号相反。只要超平面定义和样本构造保持一致，两种形式都是正确的。

内容的提问来源于stack exchange，提问作者fenixkz