Kernel Logistic Regression and the Import Vector Machine

1. 问题

标准的SVM无法很好的解决多分类问题，这主要是还由于SVM在设计的时候就是假设数据集中只有两个类别，通过最大化分类间隔来得到最优分类器。

如果需要实现多分类，就需要使用OVA或者OVO两种方式，效率低且效果不好。

2. 相关

2.1 kernel lr

svm的损失函数中，只训练了支持向量，有很大一部分的数据并没有得到应用，这样做的好处是速度比较快，但与此同时也损失了数据分布的信息。因此将对\(sign[p(x)-\frac{1}{2}]\)的估计转化为对对数几率（logistic regression）的估计\(p(x)=\frac{e^f}{1+e^f}\)，就成了kernel logistic regression。这样一来，根据表示定理，分类器的公式变为：
\[ f(x) = b+\sum_{i=1}^n\alpha_iK(x,x_i) \]
其中\(x_i\)为每一个训练样本，且\(\alpha_i\)都一定是非零的。

2.2 kernel lr的优化

原始的kernel lr时间复杂度是\(O(N^3)\)的，随着样本量的增加，训练时间指数上涨，非常可怕。由此，很多大神提出了优化的方法-取固定数量的样本集子集作为训练集，于是我们可以得到新的：
\[ f(x) = b+\sum_{x_i\in S}\alpha_iK(x,x_i) \]
其中\(S\)是数据集\(\{x_1,x_2\dots,x_N\}\)的一个子集。如何获取这个子集一直是一个研究的热门，比较典型的有如下几种：

• 将原始数据用聚类的方法分为几簇，从每一簇中选择一些数据组成训练集
  
• 使用贪心算法从\(K[(x_i, x_j)]_{N\times N}\)矩阵中选择q列，使得得到的\([K(x_i,x_j)]_{q\times q}\)与原来的矩阵\(F-norm\)相差最小
  

• 从训练集中随机选取q个数据，然后使用\(Nystrom\ method\)（这个理论我目前也不是很懂）去近似估计原相似度矩阵的特征分解，然后扩展回N维（这一条不懂，还需要看论文去理解）
  上面的方法虽然都能选择训练集的子集，但是都只从特征\(x_i\)方面去考虑，而丢失了标签\(y_i\)方面的信息，因此本篇论文提出了新的方法来构建训练集，多选出的向量被称为“Import Vector”

  3. 思路

  首先，我们的分类器的最优形式表示为：
  \[ f(x) = b+\sum_{x_i\in S}\alpha_iK(x,x_i) \]
  关键就在于如何选取合适的q个数据组成\(f(x)\)，本文提出的思路如下：
  
• 设置\(S = \emptyset，R=\{x_1,x_2\dots,x_N\}\)
  
• 对于\(\forall x_l \in R\)，得到由这个\(x_l\)和\(S\)组成的合集表示的\(f(x)\)，使用这个\(f(x)\)计算整个数据集的损失，选择损失最小的那个\(x_l\)加入到\(s\)中，并且从\(R\)中移除\(x_l\)
  

• 重复上一个步骤直到\(S\)中包括了\(q\)个import vector

  4. 优化

  4.1 加速

  上一小节中的第二步，每一次迭代都需要使用牛顿法得到每个\(\alpha_i\)，这样做优化时间非常长，因此，本文中提出了一种方法，使用上一次迭代得到的\(\alpha_i\)作为本次迭代的初始值，这样能够更快的得到最优值。

  4.2 提前终止

  如果本次迭代，不能使得loss降低很多，那么就提前终止迭代，即\(\frac{|H_k-H_{k-r}|}{|H_k|}<\alpha\)时停止迭代

  4.3 \(\lambda\) 的选择

  将\(\lambda\)的选择与迭代结合，分出一部分训练集作为验证集，每次迭代以后，在验证集上进行测试，并记录loss，最后选择loss最小时所对应的\(\lambda\)。