什么是核技巧（Kernel Trick）？SVM 为什么能处理线性不可分？

简化版

核技巧（Kernel Trick） 是 SVM 处理线性不可分数据的关键。思路：在原空间线性分不开的数据，映射到更高维空间后往往就线性可分了。但直接在高维空间算坐标又慢又可能维度无穷。核技巧的妙处在于——SVM 的对偶形式里，样本只以「内积」的形式出现，而核函数 K(xᵢ,xⱼ) 能直接算出两个样本在高维空间的内积，却不用真的把它们映射到高维、不用算高维坐标。于是我们「隐式」地在高维空间找线性边界，计算量却和原空间差不多。这就是「用低维的计算，得到高维的效果」。

详细版

为什么升维能分开： 低维线性不可分的数据（如同心圆），映射到高维后类别间可能出现线性间隔。经典例子：一维上 {-2,-1,1,2} 正负交替不可分，映射 x→x² 后按大小就线性可分。

核技巧的核心洞察：

SVM 对偶问题 & 预测都只用到样本内积:
  对偶目标:  Σαᵢ - ½ΣΣ αᵢαⱼ yᵢyⱼ (xᵢ·xⱼ)
  预测:      f(x) = Σ αᵢ yᵢ (xᵢ·x) + b
                              ↑ 只出现内积！

若映射到高维 φ(x)，需要的其实是 φ(xᵢ)·φ(xⱼ)。
核函数直接给出这个内积：K(xᵢ,xⱼ) = φ(xᵢ)·φ(xⱼ)，无需显式计算 φ。
把所有内积换成 K 即可，这就是「核技巧」。

好处： 避免高维（甚至无穷维）显式计算，省时省内存；只要 K 是合法核（满足 Mercer 条件，对应的核矩阵半正定），就隐式对应某个高维空间。

完整版教学

一、问题：线性 SVM 遇到线性不可分怎么办

线性 SVM 找的是一个超平面，但很多数据在原始空间根本没有能分开两类的超平面。最经典的例子是同心圆：内圈一类、外圈一类，无论怎么画直线都分不开。

一个朴素但有效的想法：把数据升到更高维空间。因为在高维空间里，样本有了更多「自由度」，原本纠缠在一起的两类，往往就能被一个超平面分开。

二、升维为什么能把数据分开——两个例子

例 1（一维 → 二维）：一维数轴上，内层 {-1, +1} 是正类、外层 {-3, +3} 是负类，正负交错，任何一个分割点都分不开。做映射 x → (x, x²)：所有点被抬到抛物线上，负类 x²=9（在上方）、正类 x²=1（在下方），一条水平线（如 x²=5）就把两类分开了。

例 2（二维同心圆 → 三维）：内圈、外圈在平面上分不开。映射 (x₁,x₂) → (x₁², x₂², √2·x₁x₂)（或加一维 x₁²+x₂²），到高维后内圈整体「低」、外圈整体「高」，一个平面就切开了。

规律：低维的非线性边界，在合适的高维映射下变成线性边界。 这就是 SVM 处理非线性的基本策略——先升维，再在高维找线性超平面。

三、直接升维的麻烦：维度爆炸

那直接定义映射 φ、把每个样本变成高维向量、在高维跑线性 SVM 不就行了？问题在于代价太大：

高维映射的维度会爆炸。比如把 d 维特征做二次多项式映射，维度约 O(d²)；更高阶或某些映射（如 RBF 对应的映射）是无穷维，根本没法显式写出坐标。
每个样本都要算、要存高维坐标，训练和预测都极慢甚至不可行。

于是需要一个「既享受高维的分离能力，又不付出高维计算代价」的办法——核技巧。

四、核技巧的关键：SVM 只需要「内积」

核技巧能成立，靠的是 SVM 的一个结构特性：在对偶形式里，样本从头到尾只以「内积」的形式出现，从不需要单个样本的坐标本身。

对偶目标函数：Σαᵢ - ½ΣΣ αᵢαⱼyᵢyⱼ (xᵢ·xⱼ) —— 只用到样本两两内积 xᵢ·xⱼ。
预测函数：f(x)=Σ αᵢyᵢ(xᵢ·x)+b —— 也只用到内积 xᵢ·x。

现在如果我们想在高维空间 φ 里跑 SVM，需要的其实只是 φ(xᵢ)·φ(xⱼ) 这个高维内积，而不是 φ(xᵢ) 本身。

五、核函数：绕过映射直接算高维内积

核函数 K(xᵢ,xⱼ) 的定义就是：它直接等于某个高维映射下的内积

K(xᵢ, xⱼ) = φ(xᵢ) · φ(xⱼ)

而妙处在于——很多核函数可以只用原空间的 xᵢ、xⱼ 直接算出这个值，完全不用先求 φ、不用碰高维坐标。

举例（多项式核）：K(x,z) = (x·z + 1)²。你只需在原始低维空间算个内积 x·z、加 1、平方——一步到位。但展开它，等价于先把 x、z 映射到包含所有二次项的高维空间再做内积。同样的高维效果，只花了低维的计算。

于是核技巧的操作就是：把 SVM 里所有的内积 xᵢ·xⱼ 直接替换成核函数 K(xᵢ,xⱼ)。这样我们就「隐式」地在高维空间训练了一个线性 SVM（对应原空间的非线性边界），而计算量几乎不变。这就是核技巧的全部精髓——用低维计算，拿高维结果。

六、什么样的函数才能当核——Mercer 条件

不是任意二元函数都能当核。一个函数要合法（真的对应某个高维空间的内积），需满足 Mercer 条件：对任意样本集，其核矩阵（Gram 矩阵）Kᵢⱼ=K(xᵢ,xⱼ) 必须是对称半正定的。满足这个条件，就保证存在某个（可能无穷维的）特征空间 φ，使得 K 是它的内积——我们就能放心用它，哪怕永远写不出 φ。

常见合法核：线性核、多项式核、RBF（高斯）核、sigmoid 核等（各自特点见「常见核函数」专题）。其中 RBF 核对应无穷维空间——正因为有核技巧，才能用它。

七、常见追问

核技巧省了什么？ 省掉了显式的高维映射和高维坐标计算，把「高维内积」压缩成「原空间的一次核函数计算」。
为什么必须是对偶形式才能用核？ 因为只有对偶形式把样本表达成纯内积；原始形式里有单独的 w、φ(x)，无法只用内积绕过映射。
RBF 核为什么是无穷维？ 把高斯核泰勒展开会得到无穷多项，对应无穷维特征空间——显式算不可能，只能靠核技巧。
核方法只用于 SVM 吗？ 不，核 PCA、核岭回归、高斯过程等都用同样的技巧——凡是能写成「只依赖内积」的算法都能核化。

八、用算例与工程边界复核

二维 XOR 可加入交叉特征 z=x1x2 后线性分开。二次多项式映射显式维度会随原维度 d 增至约 O(d²)，核函数却直接计算 K(x,z)=(xᵀz+c)²，无需真的构造所有二次特征。

对象/方案	核心机制	选择或风险
显式映射 φ(x)	构造高维向量再内积	维度可能爆炸
核技巧 K(x,z)	直接得到 φ(x)ᵀφ(z)	需存核矩阵/支持向量
合法核	任意有限样本 Gram 矩阵 PSD	保证对应某内积空间

把推导和选择压缩成执行路径：

algorithm uses only inner products
 -> replace x_i^T x_j with K(x_i,x_j)
 -> solve dual coefficients
 -> predict by support-vector kernels

核技巧不等于“把数据真的复制到无限维”；它只计算隐式特征空间中的内积，代价转移到样本间核计算。

九、常见误区与追问

误区：任意相似度函数都能当 SVM 核。 合法核需产生对称半正定 Gram 矩阵等条件，否则凸性和空间解释可能丢失。
误区：用了 RBF 核就不需要特征缩放。 RBF 依赖欧氏距离，尺度大的特征会主导核值。
追问：核技巧为什么依赖对偶？ SVM 对偶只通过样本内积出现，才能直接替换为核函数。
追问：核方法的主要规模瓶颈是什么？ 核矩阵存储可达 O(n²)，通用训练时间也随样本数快速增长。
追问：何时显式特征反而更好？ 大样本、可控映射或可用随机特征近似时，线性求解更易扩展。

十、加强记忆

记忆时抓住这条主线：核技巧解决 SVM 的线性不可分：低维非线性可分 → 升到高维就线性可分（同心圆升维、x→x²）。但显式升维会维度爆炸甚至无穷维，代价太大。突破口在于 SVM 对偶形式和预测都只用到样本「内积」xᵢ·xⱼ，而高维里需要的只是 φ(xᵢ)·φ(xⱼ)。核函数 K(xᵢ,xⱼ)=φ(xᵢ)·φ(xⱼ) 能在原空间直接算出这个高维内积，不用求 φ、不碰高维坐标（如多项式核 (x·z+1)²）。于是把所有内积替换成核函数，就隐式在高维训练线性 SVM，计算却在低维——「用低维计算拿高维结果」。合法核需满足 Mercer 条件（核矩阵半正定）；RBF 核对应无穷维，全靠核技巧才能用。核化能推广到核 PCA、核岭回归等一切「只依赖内积」的算法。

简化版

详细版