6.9 计算上的考虑
6.9 计算上的考虑¶
核和局部回归以及密度估计都是 基于内存的 (memory-based) 方法：模型是整个训练数据集，并且在赋值或者预测的时候完成拟合。对于许多实时的应用，这使得这类方法不可行。
在单个观测点 \(x_0\) 处拟合的计算代价为 \(O(N)\) 次 flop，除了过于简单的情形（比如平方核）。通过比较，包含 \(M\) 个基函数的展开式一次赋值代价为 \(O(M)\)，一般有 \(M\sim O(\log N)\)。基函数方法至少有 \(O(NM^2+M^3)\)的初始代价。
核方法的光滑参数 \(\lambda\) 一般离线确定，举个例子，采用交互验证，其代价为 \(O(N^2)\) 次 flop 。
局部回归的主流实现采用 三角化方案 来降低代价，如 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.