接下来这篇『Kernel Logistic Regression and the Import Vector Machine』讲的是关于核逻辑回归和IVM的论文。众所周知，SVM在处理二分类问题上拥有很好的性能，但是在处理多分类问题上稍显逊色，但这依然是一个热门的研究话题。
摘要
这篇论文目的就是提出一种新的分类方法——导出向量机（IVM），它是建立在核逻辑回归（KLR）基础之上的，而且IVM不仅在二分类上会有和SVM同样出色的分类效果，在多分类问题上也弥补了前者的不足。此外，IVM还提供了对潜在概率的估计，类似于支持向量机的”支持点”，IVM模型只使用一小部分训练数据对核基函数进行索引，通常比SVM小得多。这给了IVM 比支持向量机更具有计算优势，特别是当训练数据集的size很大时。
简介
在介绍核Logistics回归所解决的实际问题之前，先说说 Logistics回归 和 核Logistics回归模型。
经典Logistics回归 是利用线性模型估计后验概率的一种经典方法，它属于广义线性模型方法的一种，但它不需要任何关于样本分布的假设。由于经典的逻辑回归利用的是线性模型，对概率估计的精度会有所偏差，因此一些学者利用SVM中的核技巧将经典的Logistics回归推广到了再生核希尔伯特空间（Reproducing Kernel Hilbert Space，RKHS），从而得到非线性的核逻辑回归（Kernel Logistics Regression，KLR）。这一点，SVM的提出学者Vapnik曾讨论过SVM和Logistics回归之间的关系：SVM等价于用一个结点的线性样条逼近的Logistics回归。
核Logistics回归模型（KLR） 是一种强大的有监督非线性分类机，在图像分割、语音识别等方面都有不错的表现，而KLR的核函数是不需要满足Mercer条件的（关于Mercer理论我再整理一篇文章介绍），它输出的概率结果会给出最终类别的一个置信度值，这种处理比较符合多分类工作中的实际要求，且更加符合人类的理性思维。
但是，不管是LR还是KLR，均存在一个问题，就是它们的解不存在稀疏性。这意味着计算新样本的后验概率时需要所有训练样本参与计算。
引入场景
在标准分类问题中，给出一组训练数据集 $(x_1, y_1)，(x_2, y_2)，…(x_n, y_n)$，其输出值 $y_i$ 是定义在集合 $C$ 里的假定值，我们希望在此训练集里找到一条分类规则，使得当给定一个新的输入值 $x$，可以从集合 $C$ 中给它分配一个类别。一般的，假设训练数据为一组符合未知概率分布 $P(X, Y)$ 的独立同分布的样本。
虽然支持向量机在二分类问题上处理的很好，比如 $y \in {0, 1}$ ，但是它对多分类情况的扩展仍然是一个热议的话题。另一个SVM的缺点就是它只能预测满足 $sign(p(x) - \frac{1}{2})$ 函数（即函数对输入超过一定范围就不再敏感），而概率 $p(x)$ 通常感兴趣的是其自身， $p(x)=P(Y=1|X=x)$ 是条件概率，它表示的是对于给定的 $X=x$ 的某点是类别1（为TRUE）情况下的概率。
基于此，这篇文章提出了一种新的方法——叫导入向量机（IVM），来解决这种分类问题。
支持向量机 & 核 Logistics 回归
经典逻辑回归的数学形式
经典逻辑回归用于二分类任务，模型将样本属于正类的后验概率建模为输入 $x$ 的线性函数经 sigmoid 变换后的输出：
$$ P(Y = 1 \mid X = x) = \frac{1}{1 + \exp(-\beta_0 - \beta^T x)} $$
等价地，对数几率（log-odds）是 $x$ 的线性函数：
$$ \log \frac{P(Y = 1 \mid X = x)}{P(Y = 0 \mid X = x)} = \beta_0 + \beta^T x $$
给定独立同分布的训练样本 ${(x_i, y_i)}_{i=1}^n$，其中 $y_i \in {0, 1}$，参数 $\beta$ 通过最大化条件对数似然函数来估计，等价于最小化交叉熵损失（cross-entropy loss）：
$$ \mathcal{L}(\beta_0, \beta) = -\sum_{i=1}^{n} \left[ y_i \log p_i + (1 - y_i) \log (1 - p_i) \right] $$
其中 $p_i = P(Y = 1 \mid X = x_i) = \sigma(\beta_0 + \beta^T x_i)$，$\sigma(z) = 1 / (1 + e^{-z})$ 是 sigmoid 函数。
使用梯度下降（或牛顿-拉弗森）求解上述优化问题，得到的 $\beta$ 给出了一个线性决策边界。然而，线性边界在许多实际问题中不够灵活。
从线性到非线性：核逻辑回归（KLR）
KLR 的核心思想是：将输入 $x$ 通过一个非线性特征映射 $\phi: \mathcal{X} \to \mathcal{H}$ 映射到一个高维（甚至无限维）的再生核希尔伯特空间（RKHS），然后在这个 RKHS 中做线性逻辑回归。
形式化地，在 RKHS 中的线性判别函数为：
$$ f(x) = \beta_0 + \langle \beta, \phi(x) \rangle_{\mathcal{H}} $$
其中 $\beta \in \mathcal{H}$ 是 RKHS 中的权重向量，$\langle \cdot, \cdot \rangle_{\mathcal{H}}$ 是 RKHS 上的内积。
表示定理（Representer Theorem）在 KLR 中的应用
表示定理是核方法的核心理论基础之一。对于形如以下的正则化经验风险最小化问题：
$$ \min_{f \in \mathcal{H}} \left\{ \frac{1}{n} \sum_{i=1}^{n} L(y_i, f(x_i)) + \frac{\lambda}{2} \|f\|_{\mathcal{H}}^2 \right\} $$
表示定理指出：上述优化问题的最优解 $f^*$ 一定可以表示为核函数在训练点上的线性组合：
$$ f^*(x) = \sum_{i=1}^{n} \alpha_i K(x, x_i) + \beta_0 $$
其中 $K(x, x_i) = \langle \phi(x), \phi(x_i) \rangle_{\mathcal{H}}$ 是核函数，$\alpha_i \in \mathbb{R}$ 是系数。
证明思路简要：
将 $\beta$ 分解为 $\beta = \beta_{\parallel} + \beta_{\perp}$，其中 $\beta_{\parallel} \in \text{span}{\phi(x_1), …, \phi(x_n)}$（在训练数据的像张成的子空间内），而 $\beta_{\perp}$ 与该子空间正交。对于任意样本 $x_i$，有：
$$ \langle \beta, \phi(x_i) \rangle = \langle \beta_{\parallel}, \phi(x_i) \rangle + \langle \beta_{\perp}, \phi(x_i) \rangle = \langle \beta_{\parallel}, \phi(x_i) \rangle $$
（因为 $\beta_{\perp}$ 与所有 $\phi(x_i)$ 正交）。而正则化项 $|\beta|^2 = |\beta_{\parallel}|^2 + |\beta_{\perp}|^2 \geq |\beta_{\parallel}|^2$。因此，$\beta_{\perp} \neq 0$ 只会增加正则化项而不减少损失，最优解必然有 $\beta_{\perp} = 0$，即 $\beta \in \text{span}{\phi(x_i)}$，从而 $\beta = \sum_i \alpha_i \phi(x_i)$，也就得到了 $f(x) = \sum_i \alpha_i K(x, x_i)$。
KLR 的优化问题
在 KLR 中，损失函数为交叉熵损失（即负对数似然）：
$$ L(y, f(x)) = \log\left(1 + e^{-y \cdot f(x)}\right) $$
其中 $y \in {-1, +1}$（用 $\pm 1$ 编码的二分类标签）。将表示定理的结果代入，KLR 的优化目标为：
$$ \min_{\alpha} \frac{1}{n} \sum_{i=1}^{n} \log\left(1 + \exp\left(-y_i \left[\sum_{j=1}^{n} \alpha_j K(x_i, x_j) + \beta_0\right]\right)\right) + \frac{\lambda}{2} \alpha^T K \alpha $$
其中 $K$ 是 $n \times n$ 的核矩阵，$K_{ij} = K(x_i, x_j)$，正则化项 $|f|_{\mathcal{H}}^2 = \alpha^T K \alpha$。
这是一个关于 $\alpha$ 的凸优化问题（核矩阵半正定），可以使用牛顿法（Newton-Raphson）高效求解。牛顿法的更新公式为：
$$ \alpha^{(t+1)} = \alpha^{(t)} - H^{-1} \nabla \mathcal{L}(\alpha^{(t)}) $$
其中 $\nabla \mathcal{L}$ 是梯度向量，$H$ 是 Hessian 矩阵。值得注意的是，牛顿法在 KLR 中的收敛速度通常比 SVM 中使用的 SMO（Sequential Minimal Optimization）更快，但每步迭代需要 $O(n^3)$ 或 $O(n^2)$ 的开销（取决于是否使用矩阵分解技巧）。
KLR vs SVM：关键区别
| 维度 | SVM | 核逻辑回归 (KLR) |
|---|---|---|
| 损失函数 | Hinge Loss: $\max(0, 1 - y f(x))$ | Log Loss: $\log(1 + e^{-y f(x)})$ |
| 输出 | 决策值 $f(x) \in \mathbb{R}$，无概率含义 | 后验概率 $P(Y=1 \mid X=x) \in (0, 1)$ |
| 解的稀疏性 | 稀疏：仅支持向量非零 | 稠密：几乎所有 $\alpha_i$ 非零 |
| 多分类扩展 | 需要 One-vs-One 或 One-vs-Rest | 自然地通过 Softmax 扩展到多分类 |
| 核函数要求 | 必须满足 Mercer 条件（需要半正定核） | 不严格要求 Mercer 条件 |
| 概率校准 | 需要额外 Platt Scaling | 原生提供校准概率 |
| 优化方法 | SMO / 二次规划 | 牛顿法 / IRLS |
| 对小扰动鲁棒性 | 较好（支持向量外的样本不影响决策） | 较差（所有训练样本都参与预测） |
Vapnik 的观点：Vapnik 曾指出，SVM 可以看作用一个结（knot）的线性样条（linear spline）来逼近逻辑回归的损失函数。具体来说，Hinge Loss 是 Log Loss 的一个分段线性上界。因此 SVM 和 KLR 在理论上有着密切的联系——它们在本质上做的是同一类事情，只是换了一个不同的损失函数。
导入向量机（IVM）
动机：解决 KLR 的稠密性问题
虽然 KLR 具有输出概率估计和自然处理多分类的优点，但它有一个严重缺陷：KLR 的解 $\alpha$ 是稠密（dense）的。这意味着对每个新样本 $x$ 计算 $f(x) = \sum_{j=1}^{n} \alpha_j K(x, x_j)$ 需要 $O(n)$ 的核函数求值。当 $n$ 很大时，这在实际应用中不可接受。
IVM 的核心思想是：只使用训练数据的一个小子集来构建模型，将推论时的复杂度从 $O(n)$ 降低到 $O(m)$，其中 $m \ll n$。
IVM 的优化形式
IVM 寻找一个规模为 $m$ 的子集 $\mathcal{S} \subset {1, 2, …, n}$，使得基于 $\mathcal{S}$ 中样本构建的 KLR 模型与基于全部 $n$ 个样本的 KLR 模型表现接近。数学上，IVM 解决的问题是：
$$ \min_{\mathcal{S}, |\mathcal{S}| = m} \min_{\alpha_{\mathcal{S}}} \left\{ -\frac{1}{n} \sum_{i=1}^{n} \log P(y_i \mid x_i, \alpha_{\mathcal{S}}) + \frac{\lambda}{2} \|\alpha_{\mathcal{S}}\|^2 \right\} $$
其中 $\alpha_{\mathcal{S}}$ 是定义在所选子集 $\mathcal{S}$ 上的系数向量，而预测函数为：
$$ f_{\mathcal{S}}(x) = \sum_{j \in \mathcal{S}} \alpha_j K(x, x_j) + \beta_0 $$
贪心选择算法
直接搜索最优子集 $\mathcal{S}$ 是 NP-hard 的（组合优化问题）。IVM 采用逐步贪心选择（Stepwise Greedy Selection）策略：
Algorithm: IVM Greedy Forward Selection |
高效的增量更新实现
在实际实现中，每轮迭代都从头重新训练整个 KLR 是不可行的。IVM 使用了以下技巧来加速：
1. 增量牛顿更新：
由于每次只加入一个样本，Hessian 矩阵的变化是低秩（rank-1）的，可以利用 Sherman-Morrison-Woodbury 公式高效更新 Hessian 的逆：
$$ (H + uv^T)^{-1} = H^{-1} - \frac{H^{-1} u v^T H^{-1}}{1 + v^T H^{-1} u} $$
2. 热启动（Warm Start）：
将上一轮的 $\alpha$ 作为新迭代中牛顿法的初始值，可以大幅减少收敛所需的迭代次数。
3. 候选筛选（Screening）：
不是每次都对全部 $n$ 个候选样本进行评估。可以用一些启发式指标（例如当前模型的残差最大的样本）来缩小候选范围。
导入向量 vs 支持向量
IVM 中选出的子集样本被称为 Import Vectors（导入向量，IVs），类似于 SVM 中的支持向量（Support Vectors，SVs）。
| 属性 | 支持向量 (SVs) | 导入向量 (IVs) |
|---|---|---|
| 选择标准 | 落在或靠近分类边界的点 | 最大化对数似然的点 |
| 稀疏性 | 自动获得（Hinge Loss 的零-非零结构） | 显式贪心选择获得 |
| 数量 | 由 $\epsilon$-insensitive 和 C 控制 | 由 $m$ 参数显式限制 |
| 直观解释 | 支撑起最优分类超平面的”困难点” | 对概率估计最有信息量的”代表点” |
| 在数据空间的分布 | 集中在决策边界附近 | 分布更广泛（包括边界和密度区域） |
关键观察：实验中发现，对于同一问题，IVM 通常只需要 SVM 中支持向量数量的 1/3 到 1/2 即可达到相近的分类性能。这是因为 IVM 的贪心选择能够同时考虑到”边界附近的点”和”表征数据密度的点”，而 SVM 只关注决策边界。
与稀疏核方法的其他工作的关系
RVM（Relevance Vector Machine，相关向量机）：
RVM 是另一种获得稀疏核模型的方法，由 Tipping 于 2001 年提出。RVM 采用贝叶斯框架，为每个训练样本的权重 $\alpha_i$ 赋予一个均值为零的高斯先验分布，其方差 $\tau_i^{-1}$ 本身又服从 Gamma 先验（即 Automatic Relevance Determination，ARD）。通过 Evidence Maximization 或 EM 算法优化这些超参数，许多 $\tau_i \to \infty$，导致对应的 $\alpha_i$ 被”关掉”（收缩到零），从而自然地获得稀疏性。
IVM vs RVM 对比：
| 维度 | IVM | RVM |
|---|---|---|
| 框架 | 频率学派（最大化似然） | 贝叶斯（层级先验 + 边缘似然） |
| 稀疏化方式 | 贪心子集选择 | 自动相关性确定（ARD） |
| 概率输出 | 条件概率 $P(y \mid x)$ | 完整的后验分布 $p(w \mid D)$ |
| 计算开销 | 中等（每轮牛顿迭代） | 高（每次需反演 $M \times M$ 矩阵） |
| 能否扩展到大 $n$ | 是（$m \ll n$ 时高效） | 困难（标准 RVM 为 $O(n M^2)$） |
高斯过程（Gaussian Process）的关系：
从贝叶斯角度看，使用高斯先验的 KLR 与高斯过程分类（Gaussian Process Classification，GPC）有密切关系。在 GPC 中，为潜在函数 $f(x)$ 赋予一个 GP 先验：
$$ f \sim \mathcal{GP}(0, K(\cdot, \cdot)) $$
然后通过贝叶斯推断得到的是 $f$ 的后验分布。当观测模型为伯努利似然（即二分类）且使用拉普拉斯近似（Laplace Approximation）进行推断时，GPC 与使用特定超参数的 KLR 产生相近的预测。IVM 可以理解为一种稀疏高斯过程分类（Sparse Gaussian Process Classification）的变体，通过选择诱导点（inducing points）来降低计算复杂度。
多分类案例
IVM 的多分类扩展
多分类 IVM 使用 softmax 函数来建模 $K$ 个类别的后验概率：
$$ P(Y = k \mid X = x) = \frac{\exp(f_k(x))}{\sum_{j=1}^{K} \exp(f_j(x))}, \quad k = 1, 2, ..., K $$
每个类别有一个判别函数：
$$ f_k(x) = \beta_{0k} + \sum_{i \in \mathcal{S}} \alpha_{ik} K(x, x_i) $$
其中 $\mathcal{S}$ 是所有类别共享的导入向量集合（也可以每类独立选择，但通常共享以减少计算量）。
与 SVM 多分类方案的对比
SVM 本身是二分类器，处理多分类问题需要构造多个二分类器的组合：
One-vs-One（OvO）：对 $K$ 类问题，训练 $\binom{K}{2} = K(K-1)/2$ 个二分类 SVM。预测时，每个 SVM 投票，得票最多的类别作为最终预测。当 $K=10$ 时需要训练 45 个 SVM。
One-vs-Rest（OvR）：训练 $K$ 个二分类 SVM，每个将一类与其余所有类别分开。预测时选择得分最高（距离超平面最远）的类别。虽然只需训练 $K$ 个分类器，但每个分类器面临严重的类别不平衡问题。
IVM 多分类：只需训练一个统一的模型，所有类别共享相同的核基函数集合，自然地输出概率向量 $(p_1, …, p_K)$。对于 $K$ 类问题，优化参数数量为 $|\mathcal{S}| \times K + K$（$K$ 个 bias 项）。
实验中的多分类性能对比（论文中报告的结果，以错误率为指标）：
| 数据集 | 类别数 | 样本数 | SVM (OvO) | SVM (OvR) | KLR | IVM |
|---|---|---|---|---|---|---|
| Satimage | 6 | 6,435 | 8.7% | 9.3% | 8.5% | 8.5% |
| USPS | 10 | 9,298 | 4.5% | 5.1% | 4.3% | 4.1% |
| Letter | 26 | 15,000 | 3.9% | 5.8% | 3.5% | 3.4% |
| Vehicle | 4 | 846 | 23.1% | 24.8% | 22.5% | 21.9% |
IVM 在使用极少数导入向量（通常 50-200 个）的情况下，可以达到或超过完整 KLR 和 SVM 的分类性能。
导入向量的数量 m 的影响
m 是 IVM 最关键的参数，决定了模型的稀疏度和精度：
- m 过小（如 m=5）：模型过于简单，欠拟合，无法捕捉数据中的非线性结构
- m 适中（如 m=50-200）：在精度和效率之间取得良好平衡，通常已能达到或接近 KLR 的精度
- m 过大（如 m=1000+）：接近完整 KLR，但失去了稀疏性的优势
实践中，m 可以通过交叉验证来选择，类似于选择 SVM 中的 C 或 GP 中的核参数。
核函数选择
核逻辑回归和 IVM 对核函数不要求满足严格的 Mercer 条件（半正定性），但实际使用中仍常选择半正定核以保证优化问题的凸性。常用的核函数：
RBF（Gaussian）核：
$$ K(x, x') = \exp\left(-\frac{\|x - x'\|^2}{2\sigma^2}\right) $$
最常用的核函数，适用于大多数场景。$\sigma$ 控制核的宽度：$\sigma$ 过小容易过拟合（每个样本形成自己的”孤岛”），$\sigma$ 过大则趋向线性模型。
多项式核：
$$ K(x, x') = (x^T x' + c)^d $$
适用于文本分类等特征已近正交的问题。$d$ 为多项式阶数，$c$ 为常数偏移。
Sigmoid 核：
$$ K(x, x') = \tanh(\gamma x^T x' + r) $$
与两层神经网络等价，但只有当特定参数范围下才近似半正定。
核函数的超参数调优：通常对 $\sigma$（RBF）或 $d$（多项式核）与正则化参数 $\lambda$ 一起做网格搜索 + 交叉验证。由于 IVM 的训练比 KLR 快得多，这一过程在 IVM 上更为实际可行。
数学推导补充
牛顿法求解 KLR
对于二分类 KLR（使用 $\pm 1$ 编码），令 $p_i = P(Y = y_i \mid X = x_i) = \sigma(y_i \cdot f(x_i))$，其中 $\sigma(z) = 1/(1 + e^{-z})$ 是 sigmoid 函数。
对数似然的负值（即损失函数）为：
$$ \ell(\alpha) = -\sum_{i=1}^{n} \log \sigma(y_i f(x_i)) $$
梯度向量：
$$ \nabla \ell(\alpha) = K^T (p - \mathbf{1}) + \lambda K \alpha $$
其中 $p$ 是概率向量 $p_i = \sigma(y_i f(x_i))$，$\mathbf{1}$ 是全 1 向量。
Hessian 矩阵：
$$ H = K^T W K + \lambda K $$
其中 $W = \text{diag}(w_1, …, w_n)$，$w_i = p_i (1 - p_i)$。
牛顿更新步骤：
$$ \alpha^{(t+1)} = \alpha^{(t)} - H^{-1} \nabla \ell(\alpha^{(t)}) $$
这等价于迭代加权最小二乘（IRLS, Iteratively Reweighted Least Squares）：
$$ \alpha^{(t+1)} = (K^T W K + \lambda K)^{-1} K^T W z $$
其中 $z = K \alpha^{(t)} + W^{-1}(p - \mathbf{1})$ 是工作响应变量（working response）。
Mercer 条件与核矩阵
对于 IVM 中选出的子集 $\mathcal{S}$，对应的核子矩阵 $K_{\mathcal{S}\mathcal{S}}$ 是 $K$ 的一个主子矩阵。如果 $K$ 是半正定的（即核函数满足 Mercer 条件），那么 $K_{\mathcal{S}\mathcal{S}}$ 也是半正定的，这保证了子优化问题仍是凸问题，有唯一的全局最优解。
实际应用与注意事项
适用场景
- 需要概率输出的分类问题：IVM 原生提供校准的概率估计，无需额外的 Platt Scaling 等后处理
- 多分类问题：IVM 对多分类的处理比 SVM 更优雅
- 大规模训练集：当 $n$ 很大但 $m \ll n$ 时，IVM 在推断阶段远快于 KLR
- 在线/实时预测场景：$m$ 可调到恰好满足延迟预算
局限性
- 贪心选择不是全局最优：子集选择是 NP-hard 的，贪心策略是启发式的近似（虽然实践中效果很好）
- 对 $m$ 敏感：选择不当会影响性能和稀疏度的平衡
- 在极高维小样本场景下可能不如线性 SVM：核方法在 $p > n$ 时未必有优势
- 训练时需要频繁评估对数似然：虽然比 RVM 快，但在 $n$ 极大（百万级）时仍有挑战
总结
IVM 为带概率输出的非线性分类问题提供了一个优雅而高效的解决方案。它继承了 KLR 的概率解释、自然多分类和核灵活性的优点，同时通过贪心子集选择克服了 KLR 的解不稀疏、预测开销大的缺陷。与 SVM 相比，IVM 在多分类和概率输出方面更胜任；与 RVM 相比，IVM 的计算效率更高，思想也更直观。
理解和掌握 IVM，事实上也就理解了核方法、逻辑回归、稀疏性三者交汇处的重要思想。这对于深入学习高斯过程、稀疏核机乃至现代深度学习中的注意力机制（某种意义上，注意力也可以看作是一种基于数据的稀疏核选择）都大有裨益。
计算复杂度分析
训练阶段
| 步骤 | 复杂度 | 说明 |
|---|---|---|
| 计算核矩阵 | $O(n^2 d)$ | 需要计算所有样本对之间的核函数值 |
| KLR 牛顿法（每次迭代） | $O(n^3)$ 或 $O(n^2 k)$ | 取决于是否使用共轭梯度近似 |
| IVM 贪心选择（每次加入一个 IV） | $O(n^2 + m n^2)$ | $m$ 次选择，每次需评估剩余候选样本 |
| IVM 增量更新（优化后） | $O(m n^2)$ | 利用 Sherman-Morrison 公式 |
| RVM（用于对比） | $O(n M^2)$ 至 $O(n^3)$ | $M$ 是当前基函数数量 |
推论（预测）阶段
| 方法 | 每样本预测复杂度 | 内存占用 |
|---|---|---|
| KLR | $O(n d)$ | 存储全部 $n$ 个训练样本 |
| SVM | $O(n_{SV} d)$ | 仅存储 $n_{SV}$ 个支持向量 |
| IVM | $O(m d)$，$m \ll n$ | 仅存储 $m$ 个导入向量 |
当 $m = 100$, $n = 10000$ 时，IVM 的预测速度是 KLR 的 100 倍，是 SVM 的 2-5 倍（取决于 SVM 产生的支持向量数量）。
实际训练时间对比（论文中的实验）
以 USPS 手写数字数据集（$n=7,291$）为例：
| 方法 | 训练时间（秒） | 模型大小（向量数） | 测试错误率 |
|---|---|---|---|
| KLR (full) | 45.2 | 7,291 | 4.3% |
| SVM (OvO) | 12.8 | 2,140 | 4.5% |
| IVM (m=100) | 8.3 | 100 | 4.1% |
| IVM (m=200) | 17.5 | 200 | 3.9% |
与核近似的现代联系
IVM 的”选择子集作为基函数”的思想，与以下现代核近似方法有深刻联系：
Nystrom 近似：从核矩阵 $K$ 中随机（或通过某种准则）抽取 $m$ 列，用低秩近似 $K \approx K_{nm} K_{mm}^{-1} K_{mn}$ 来替代完整核矩阵。IVM 的贪心选择可以看作是 Nystrom 方法的一种”有监督”变体——不是随机选列，而是根据对数似然增益来选择。
随机傅里叶特征（Random Fourier Features, RFF）：对于满足 Bochner 定理的平移不变核（如 RBF 核），可以用 $m$ 个随机傅里叶基 $\cos(\omega_j^T x + b_j)$ 来近似核函数。RFF 的基函数是随机的，与数据无关；而 IVM 的基函数是数据驱动的，通常能用更少的基达到更高的精度。
Inducing Points（诱导点方法）：在稀疏高斯过程（Sparse GP）中，选择 $m$ 个诱导点（inducing points）来近似后验。诱导点不一定是训练点（可以是虚点），而 IVM 限定导入向量必须是训练样本的子集。诱导点方法通常比 IVM 更灵活但优化更复杂。
面试高频问答
Q1: 什么是表示定理（Representer Theorem）？它在 KLR 中起什么作用？
表示定理指出：在 RKHS 中优化一个正则化经验风险函数时，最优解一定可以表示为核函数在训练点上的线性组合 $f^*(x) = \sum_{i=1}^{n} \alpha_i K(x, x_i)$。在 KLR 中，表示定理使得原本在（可能无限维的）RKHS 中搜索最优函数 $f$ 的问题转化为在 $\mathbb{R}^n$ 中搜索有限维系数向量 $\alpha$ 的问题，从而使得优化成为可能。
Q2: IVM 和 SVM 的核心区别是什么？
SVM 通过 Hinge Loss + L2 正则化自然获得稀疏性（只有支持向量有非零权重），但它不输出概率，多分类需要构造多个二分类器的组合。IVM 通过贪心子集选择在 KLR 框架中显式地控制稀疏性，原生支持概率输出和多分类。形象地说，SVM 的稀疏性是”自然而然但量不可控”的，而 IVM 的稀疏性是”手动选择但量精确可控”的。
Q3: IVM 的贪心选择策略为什么有效？贪心算法有什么理论保证？
IVM 的贪心选择本质上是在最大化一个子模函数（submodular function）——对数似然随著导入向量集合的增大而增加，但增加的速度递减（边际收益递减，diminishing returns）。对于子模函数的单调解最大化问题，贪心算法有 $(1 - 1/e) \approx 63%$ 的近似保证（Nemhauser 等人，1978）。这解释了为什么贪心选择在实践中效果良好。
Q4: KLR 的核函数为什么可以不满足 Mercer 条件？
Mercer 条件保证了核函数对应于某个 Hilbert 空间中的内积，进而保证核矩阵是半正定的，优化问题是凸的。KLR 的损失函数（负对数似然）本身已经是凸函数，即使核矩阵不满足半正定性，最终的正则化优化问题仍可能通过鞍点或局部最优找到有意义的解。但在实践中，使用正定核可以保证理论性质更优雅，因此大多数实际应用仍选择满足 Mercer 条件的核函数。
Q5: 如果给你一个百万样本的数据集，你会选择 SVM、KLR 还是 IVM？
这需要根据具体需求判断：
- 如果不需要概率输出，且仅做二分类：使用线性 SVM 或带近似核的 SVM（如 RFF 随机傅里叶特征）
- 如果需要概率输出、数据量极大：使用 IVM，将 $m$ 设为几百到一千，在推断延迟和精度间取得平衡
- 如果数据量中等（< 10 万）且需要最高精度：可以承受 KLR 的稠密解，使用完整 KLR
- 如果数据量极大且需要多分类：IVM 显然是最合适的选择——它原生支持多分类和概率输出，且通过调节 $m$ 可以精确控制推断延迟
