Skip to content

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. 或许现在三角化方案不算主流实现?


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

Comments