前篇: https://welts.xyz/2021/07/10/wss/, https://welts.xyz/2021/07/12/cache/.
引言
SVM的对偶问题如下
\[\begin{aligned} \min_{\pmb\alpha}\quad&\frac12\pmb\alpha^TQ\pmb\alpha-\pmb e^T\pmb\alpha\\ \text{s.t.}\quad&0\leq\alpha_i\leq C,i=1,\cdots,l\\ &\pmb y^T\pmb\alpha=0 \end{aligned}\]这里设数据集的数据量$l$，数据特征数为$n$。其中$Q_{ij}=y_iy_jK(\pmb x_i,\pmb x_j)$，显然该矩阵为$l\times l$的，当$l$很大时，存储整个$Q$矩阵显然是不合理的。SMO算法中，每次迭代都会从$\{1,\cdots,l\}$中选取两个下标$i$和$j$，然后进行更新，因此一种朴素的想法是选到下标$i$后再计算对应的$Q$矩阵第$i$行($Q$是对称矩阵，因此第$i$行就是第$i$列)。这样计算无疑是耗时的，所幸SVM模型是稀疏的，也就是说，在最后最优的$\pmb\alpha^*$中，大部分元素是0。更进一步说，有不少变量从始至终都不会被选择，相对应的，一部分变量一直被选择。
LIBSVM使用缓存机制来解决这一问题，也就是将最常用的矩阵列放在缓存中，当选到时可以直接取用。本文的目的是在已实现的Python-SVM的基础上(https://github.com/Kaslanarian/PySVM，其中的$Q$矩阵是直接存储，因此不适用大型数据)加入缓存机制，尝试是否能带来性能上的提升。
缓存简介
缓存是计算机系统基础中重要的一节，我们这里只简单介绍思想，如果读者对这方面底层实现机制有兴趣，可以查阅相关的文章。
严格意义上说，缓存是被直接制作在CPU芯片里，速度极快的一种存储器，其理论基础是程序访问的局部性原理，即程序需要访问的指令和数据之间并不是毫无关联的，随机的，而是在时间上和空间上存在关联。LIBSVM的缓存机制，以及我们在下面实现的，并不是标准的硬件意义上的缓存，而是用软件的方法模拟一个缓存，比如LIBSVM用的是一个环形队列。利用缓存机制，我们得以储存一些经常被取用的数据，从而减少重复计算所消耗的时间。
Python3的缓存机制
考虑到Python3在速度上的不足，自实现缓存机制不是一个好的选择(可能后面会尝试?)。最后我们选择了Python3的functools模块中的lru_cache，它是一个装饰器，可以将函数的返回值放入缓存中，如果短时间内再次调用，则会直接返回调用结果。
比如下面的函数
from functools import lru_cache
@lru_cache(maxsize=32)
def cache_add(x, y):
print("missed")
return x + y
此时cache_add函数与一个尺寸为32的缓存链接，可以将其理解为一个更高级的字典结构，它的键是函数参数，对应的值就是函数值。当调用cache_add(1, 2)时，如果参数不在当前字典的键中，则会计算1+2，并将{(1, 2):3}存入缓存。如果再调用cache_add(1, 2)，由于缓存中已经有(1, 2)这个键了，因此不用计算，直接返回它的值3。我们用上面的函数做测试:
print(cache_add(1, 2))
print(cache_add(1, 2))
其输出为
missed
3
3
说明只有第一次调用的函数才会真正执行，后面一次调用只是用了缓存的值。
之所以叫做lru_cache，是因为当缓存被填满时，它会根据最近最少用(Least-Recently Used)原则，将最近最少使用的数据替换掉。
lru_cache有两个参数，maxsize对应缓存能容纳的最多元素，默认128；typed默认为False，如果为True，则它会将类型不同的参数视作不同，比如
@lru_cache(typed=True)
def cache_add(x, y):
print("missed")
return x + y
cache_add(1, 2)
cache_add(1., 2.)
会输出两个missed。
实现SVM缓存
这里的SVM是依靠SMO进行训练，主要流程:
for n_iter in range(max_iter):
# 变量选择(wss)
i, j = working_set_selection()
if no variable can be selected:
break
# 对指定变量进行更新
update(i, j)
工作集选择需要的是目标函数的梯度信息，也就是
\(\nabla f(\pmb\alpha)=Q\pmb\alpha-\pmb e\)
通过维护一个向量grad，我们不需要每次循环都重新算一次梯度，而是动态更新:
\(\nabla f(\pmb\alpha+\alpha_i\pmb e_i)=\nabla f(\pmb\alpha)+\alpha_iQ_{:,i}\)
但在更新变量时，我们需要频繁使用$Q_{ii},Q_{ij}$和$Q_{jj}$，因此我们会在更新变量之前，计算$Q_{i,:}$和$Q_{j,:}$，这里的计算是用缓存机制实现的，也就是lru_cache。
@lru_cache(maxsize=128)
def calculate_product(self, i:int):
# 此处是计算线性核
return self.y * (self.X @ self.X[i]) * self.y[i]
然后在变量更新之前获取$Q$矩阵的第$i$行和第$j$行:
Qi = self.calculate_product(i)
Qj = self.calculate_product(j)
在更新阶段，我们就可以用Qi[i]代替Q[i][i]，类似的还有Qi[j]和Qj[j]。通过这样的方式，我们将缓存机制嵌入了SVM中。
性能比较
我们这里比较的是是否加入缓存机制，以及不同缓存大小下线性二分类SVM在相同迭代次数下，在不同大小的数据集上的耗时(单位：s)，均是独立重复运行10次的结果，实验数据集是通过sklearn.datasets.make_classification构造出的二分类数据集。
| Cache size\样本数 | 10 | 100 | 1000 | 10000 | 20000 | 100000 |
|---|---|---|---|---|---|---|
| 0 | 0.0032 | 0.0538 | 0.0908 | 1.5107 | 45.4716 | None |
| 8 | 0.0031 | 0.0634 | 0.2607 | 0.5858 | 1.0661 | 4.5948 |
| 32 | 0.0016 | 0.0507 | 0.2633 | 0.5475 | 1.0108 | 4.2797 |
| 128 | 0.0012 | 0.0527 | 0.2318 | 0.4850 | 0.9211 | 3.5447 |
None是因为数据量过大，PC无法构建出$10^5\times10^5$的矩阵，但利用缓存法，我们可以进行算法。我们将数据量为10、100、1000和10000时程序耗时绘制成图如下
从上表上图可以总结出2点规律：
- 当数据量很大时，缓存法可以节省大量时间；
- 缓存应当大一点，可以提高算法效率；
另外注意到样本数为1000时，计算$Q$矩阵的基本SMO算法耗时反而小一些，笔者认为这是因为此时Numpy在组织矩阵负担上处于较优的位置(或者说，数据小的时候Numpy显得大材小用，数据大的时候Numpy则力不从心)。
从而，我们可以将这一方法引申到核SVM和$\nu$-SVM上，包括分类、回归和单分类任务。值得注意的是，上述的缓存机制和LIBSVM的缓存机制相比仍有差距，LIBSVM的收缩机制(Shrinking)机制让每轮循环考虑的变量数减少，因此缓存中也不需要存储$Q$矩阵的某一整列。
