QxRed

尽管对原来的程序进行了优化，可是77句话迭代50次还是需要6分钟。与之相比，CRF只要0.18秒
关键还是在kernel计算上，而且似乎kernel cache没什么用。在SVM中，可以通过缓存一个向量来快速查找kkt violate最大的那个样本，该过程不需要计算kernel，在找到样本之后，优化，并更新缓存的向量，在更新时，才需要计算该样本和所有样本的kernel。因此每部迭代需要计算n个kernel，由于需要优化的样本常常在几个少数的样本上，因此cache是有效的。而在M3N中，缓存的向量长度是指数级的，因此不可能用上述方法来选择一个样本优化，在M3N中，一般的做法是顺序选择每个样本，一一优化。这样需要优化的样本就均匀地分布在每个样本上，cache哪个样本的kernel都没有太大的效果。因此kernel cache在M3N中没有什么用。怎么办？怎么办，难道就这么算了么？