6.9 计算上的考虑¶
| 原文 | The Elements of Statistical Learning |
|---|---|
| 翻译 | szcf-weiya |
| 发布 | 2017-12-29 |
| 更新 | 2020-03-19 12:10:40 |
| 状态 | Done |
核和局部回归以及密度估计都是 基于内存的 (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)$）．
weiya 注：triangulation schemes
Loader (1999)介绍道，在 locfit 中，参数 evaluation structure ev = "phull" 表示采取三角化方案，而在最新的 R package 中，其 ev 可选参数不再包括 phull. 或许现在三角化方案不算主流实现？
-
Loader, C. (1999). Local Regression and Likelihood, Springer, New York. ↩