Skip to content

计算上的考虑

原文 The Elements of Statistical Learning
翻译 szcf-weiya
时间 2017-12-29

核和局部回归以及密度估计都是memory-based方法:模型是整个训练数据集,并且在赋值或者预测的时候完成拟合。对于许多实时的应用,这使得这类方法不可行。

在单个观测点$x_0$处拟合的计算代价为$O(N)$次flop,除了过于简单的情形(比如平方核)。通过比较,包含$M$个基函数的展开式一次赋值代价为$O(M)$,一般有$M\sim O(log N)$。基函数方法至少有$O(NM^2+M^3)$的初始代价。

核方法的光滑参数$\lambda$一般线下(off-line)确定,举个例子,采用交叉验证,其代价为$O(N^2)$次flop。

局部回归的流行实现采用三角测量方案(triangulation schemes)来降低代价,如S-PLUS和R中的loess函数,以及locfit过程(Loader, 19991)。他们在认真选出的$M$个点处精确拟合,代价为$O(N(M))$,然后采用blending技巧来插值拟合其它点(每次赋值代价为$O(M)$)。


  1. Loader, C. (1999). Local Regression and Likelihood, Springer, New York. 

Comments