前置知识: 机器学习

支持向量机
00:00
5 min Intermediate
支持向量机 SVM 核技巧 最大间隔 分类

SVM找到最宽的街道来分隔类别，用核技巧处理非线性边界

支持向量机

SVM找到最宽的街道来分隔类别，用核技巧处理非线性边界。

类型: 构建 语言: Python 前置条件: Phase 2 第1-4课 时间: ~90 分钟

学习目标

  • 推导硬间隔和软间隔SVM的优化目标，并解释间隔最大化的直觉
  • 从零实现线性SVM使用梯度下降，包括hinge损失
  • 使用核技巧（RBF核）实现非线性SVM，并解释为什么核技巧避免了显式特征映射
  • 比较SVM与逻辑回归，识别每种方法更优的场景

问题

你有两类点需要分开。逻辑回归找到一条线使概率预测最好。但如果你只想要离边界最远的线呢？如果新点落在边界附近，你不太确定它的类别。远离边界的点更确定。

SVM不是拟合概率模型，而是找到两个类别之间最宽的”街道”。只有边界上的点（支持向量）决定决策边界。其他点无关紧要。

当数据不是线性可分时，SVM使用核技巧将数据映射到更高维空间，在那里变得可分，而不需要显式计算高维表示。

概念

最大间隔分类器

间隔是决策边界到最近训练点的距离。SVM最大化这个间隔。

决策边界: w^T * x + b = 0
间隔上界: w^T * x + b = 1
间隔下界: w^T * x + b = -1
间隔宽度 = 2 / ||w||

最大化间隔 = 最小化 ||w||，约束条件为所有点正确分类。

硬间隔 vs 软间隔

硬间隔：不允许任何点落在间隔内或错误分类一侧。仅当数据完全线性可分时有效。

软间隔：允许一些点违反间隔约束。引入松弛变量xi_i >= 0：

最小化: (1/2)||w||^2 + C * sum(xi_i)
约束: y_i * (w^T * x_i + b) >= 1 - xi_i

超参数C控制权衡：

  • C很大：严格间隔，少违规，可能过拟合
  • C很小：宽松间隔，多违规，可能欠拟合

Hinge损失

软间隔SVM等价于最小化hinge损失：

L = max(0, 1 - y_i * (w^T * x_i + b))
  • 如果y_i * f(x_i) >= 1：损失=0（正确分类，在间隔外）
  • 如果0 < yi * f(xi) < 1：损失=1 - y_i * f(x_i)（在间隔内）
  • 如果y_i * f(x_i) < 0：损失>1（错误分类）

核技巧

线性SVM只能画直线。对于非线性边界，将数据映射到更高维空间：

x -> phi(x)，其中phi是特征映射

问题：高维映射计算代价大。核技巧避免了显式映射：

K(x_i, x_j) = phi(x_i)^T * phi(x_j)

你只需要计算点积K，不需要phi。

常用核函数：

| 核 | 公式 | 用途 | | ------- | ------------------------------ | ------------ | --- | --- | --- | ---------- | | 线性 | K(x,z) = x^T*z | 线性可分数据 | | 多项式 | K(x,z) = (x^T*z + c)^d | 特征交互 | | RBF | K(x,z) = exp(-gamma * | | x-z | | ^2) | 通用非线性 | | Sigmoid | K(x,z) = tanh(alphax^Tz + c) | 类神经网络 |

RBF核最常用。它将每个点映射到无穷维空间，在那里任何数据集都变得线性可分。

支持向量

只有落在间隔上或违反间隔的点影响决策边界。这些就是支持向量。移除非支持向量不改变模型。

这意味着SVM是稀疏的：即使训练集有百万样本，决策函数只依赖少数支持向量。

动手构建

步骤1：线性SVM（梯度下降）

import random
import math

class LinearSVM:
    def __init__(self, learning_rate=0.001, lambda_param=0.01, n_iters=1000):
        self.lr = learning_rate
        self.lambda_param = lambda_param
        self.n_iters = n_iters
        self.weights = None
        self.bias = None

    def fit(self, X, y):
        n_samples = len(X)
        n_features = len(X[0])
        self.weights = [0.0] * n_features
        self.bias = 0.0

        y_svm = [1 if label == 1 else -1 for label in y]

        for epoch in range(self.n_iters):
            for i in range(n_samples):
                condition = y_svm[i] * (sum(self.weights[j] * X[i][j] for j in range(n_features)) + self.bias) >= 1
                if condition:
                    for j in range(n_features):
                        self.weights[j] -= self.lr * (2 * self.lambda_param * self.weights[j])
                else:
                    for j in range(n_features):
                        self.weights[j] -= self.lr * (2 * self.lambda_param * self.weights[j] - y_svm[i] * X[i][j])
                    self.bias -= self.lr * (-y_svm[i])

            if epoch % 200 == 0:
                hinge_loss = 0
                for i in range(n_samples):
                    score = sum(self.weights[j] * X[i][j] for j in range(n_features)) + self.bias
                    hinge_loss += max(0, 1 - y_svm[i] * score)
                hinge_loss /= n_samples
                reg = self.lambda_param * sum(w ** 2 for w in self.weights)
                print(f"  Epoch {epoch:4d} | Loss: {hinge_loss + reg:.4f}")
        return self

    def predict(self, X):
        return [1 if sum(self.weights[j] * x[j] for j in range(len(self.weights))) + self.bias >= 0 else 0 for x in X]

    def accuracy(self, X, y):
        preds = self.predict(X)
        return sum(p == t for p, t in zip(preds, y)) / len(y)

步骤2：核SVM

class KernelSVM:
    def __init__(self, kernel='rbf', C=1.0, gamma=0.5, lr=0.001, n_iters=500):
        self.kernel = kernel
        self.C = C
        self.gamma = gamma
        self.lr = lr
        self.n_iters = n_iters
        self.alphas = None
        self.b = 0.0
        self.X_train = None
        self.y_train = None

    def kernel_func(self, x1, x2):
        if self.kernel == 'linear':
            return sum(a * b for a, b in zip(x1, x2))
        elif self.kernel == 'rbf':
            diff = sum((a - b) ** 2 for a, b in zip(x1, x2))
            return math.exp(-self.gamma * diff)
        elif self.kernel == 'poly':
            return (sum(a * b for a, b in zip(x1, x2)) + 1) ** 3

    def fit(self, X, y):
        n = len(y)
        self.X_train = X
        self.y_train = [1 if label == 1 else -1 for label in y]
        self.alphas = [0.0] * n
        self.b = 0.0

        K = [[self.kernel_func(X[i], X[j]) for j in range(n)] for i in range(n)]

        for epoch in range(self.n_iters):
            for i in range(n):
                decision = sum(self.alphas[j] * self.y_train[j] * K[i][j] for j in range(n)) + self.b
                if self.y_train[i] * decision < 1:
                    self.alphas[i] += self.lr * (1 - self.y_train[i] * decision)
                    self.b += self.lr * self.y_train[i]
                self.alphas[i] = max(0, min(self.C, self.alphas[i]))

            if epoch % 100 == 0:
                loss = 0
                for i in range(n):
                    decision = sum(self.alphas[j] * self.y_train[j] * K[i][j] for j in range(n)) + self.b
                    loss += max(0, 1 - self.y_train[i] * decision)
                print(f"  Epoch {epoch:4d} | Loss: {loss / n:.4f}")
        return self

    def predict(self, X):
        results = []
        for x in X:
            decision = sum(self.alphas[j] * self.y_train[j] * self.kernel_func(self.X_train[j], x)
                          for j in range(len(self.y_train))) + self.b
            results.append(1 if decision >= 0 else 0)
        return results

    def accuracy(self, X, y):
        preds = self.predict(X)
        return sum(p == t for p, t in zip(preds, y)) / len(y)

步骤3：训练和比较

random.seed(42)
N = 200
X_linear = []
y_linear = []
for _ in range(N // 2):
    X_linear.append([random.gauss(2, 1), random.gauss(2, 1)])
    y_linear.append(0)
for _ in range(N // 2):
    X_linear.append([random.gauss(5, 1), random.gauss(5, 1)])
    y_linear.append(1)

split = int(0.8 * N)
X_train_l, X_test_l = X_linear[:split], X_linear[split:]
y_train_l, y_test_l = y_linear[:split], y_linear[split:]

print("=== Linear SVM ===")
svm = LinearSVM(learning_rate=0.001, lambda_param=0.01, n_iters=1000)
svm.fit(X_train_l, y_train_l)
print(f"Train accuracy: {svm.accuracy(X_train_l, y_train_l):.4f}")
print(f"Test accuracy:  {svm.accuracy(X_test_l, y_test_l):.4f}")

X_nonlinear = []
y_nonlinear = []
for _ in range(150):
    angle = random.uniform(0, 2 * math.pi)
    r = random.gauss(0, 0.5)
    X_nonlinear.append([r * math.cos(angle), r * math.sin(angle)])
    y_nonlinear.append(0)
for _ in range(150):
    angle = random.uniform(0, 2 * math.pi)
    r = random.gauss(3, 0.5)
    X_nonlinear.append([r * math.cos(angle), r * math.sin(angle)])
    y_nonlinear.append(1)

split2 = int(0.8 * 300)
X_train_nl, X_test_nl = X_nonlinear[:split2], X_nonlinear[split2:]
y_train_nl, y_test_nl = y_nonlinear[:split2], y_nonlinear[split2:]

print("\n=== Kernel SVM (RBF) on Non-linear Data ===")
ksvm = KernelSVM(kernel='rbf', C=1.0, gamma=0.5, lr=0.01, n_iters=300)
ksvm.fit(X_train_nl, y_train_nl)
print(f"Train accuracy: {ksvm.accuracy(X_train_nl, y_train_nl):.4f}")
print(f"Test accuracy:  {ksvm.accuracy(X_test_nl, y_test_nl):.4f}")

实际使用

from sklearn.svm import SVC
from sklearn.datasets import make_moons, make_circles
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn.preprocessing import StandardScaler
import numpy as np

X, y = make_moons(n_samples=300, noise=0.2, random_state=42)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=42)

scaler = StandardScaler()
X_tr_sc = scaler.fit_transform(X_tr)
X_te_sc = scaler.transform(X_te)

svm_linear = SVC(kernel='linear', C=1.0)
svm_linear.fit(X_tr_sc, y_tr)
print(f"Linear SVM: {accuracy_score(y_te, svm_linear.predict(X_te_sc)):.4f}")

svm_rbf = SVC(kernel='rbf', C=1.0, gamma='scale')
svm_rbf.fit(X_tr_sc, y_tr)
print(f"RBF SVM:    {accuracy_score(y_te, svm_rbf.predict(X_te_sc)):.4f}")

print(f"\nSupport vectors: {svm_rbf.n_support_}")

练习

  1. 在make_moons数据集上比较线性SVM和RBF SVM。绘制决策边界。RBF核如何弯曲边界？
  2. 对C值{0.01, 0.1, 1, 10, 100}进行网格搜索。绘制C vs测试准确率。哪个C给出最佳权衡？
  3. 实现多项式核SVM（度数2和3）。在圆形数据集上比较。为什么多项式核在这里比线性核好？

关键术语

| 术语 | 人们怎么说 | 实际含义 | | --------- | ------------ | -------------------------------------------------------- | --- | --- | --- | ----------------------- | | 间隔 | “街道宽度” | 决策边界到最近训练点的距离，SVM最大化它 | | 支持向量 | “边界上的点” | 落在间隔上或违反间隔的训练点，它们定义决策边界 | | Hinge损失 | “间隔惩罚” | L = max(0, 1 - y*f(x))，仅当点在间隔内或错误分类时惩罚 | | 核技巧 | “隐式映射” | 在高维空间计算点积而不显式映射，使非线性可分数据线性可分 | | RBF核 | “高斯核” | K(x,z) = exp(-gamma* | | x-z | | ^2)，将数据映射到无穷维 | | C参数 | “间隔严格度” | 控制间隔违规惩罚，大C=严格，小C=宽松 | | 软间隔 | “允许犯错” | 允许一些点落在间隔内，处理噪声和重叠数据 |

知识检测

学习进度

-- 已学文档
--% 知识覆盖率

学习推荐

专注模式