Skip to content

9.7 计算的考虑

原文 The Elements of Statistical Learning
翻译 szcf-weiya
时间 2017-03-13
更新 2018-03-17
状态 Done

在 $N$ 个观测和 $p$ 个预测变量的情形下,拟合加性模型需要应用 $mp$ 个一维光滑器或回归。backfitting 算法的要求的圈数 $m$通常小于 20,并且经常小于 10,而且取决于输入变量间的相关性大小。举个例子,三次光滑样条下,对于初始的排序需要 $N\log N$ 次操作,以及对样条拟合的 $N$ 操作。因此对于加性模型拟合总共的操作数为 $pN\log N+mpN$。

对每个预测变量的初始排序,树需要$pN\log N$次操作,并且一般地分割计算需要$pN\log N$次操作。如果分割在预测变量值域附近的边上,这个数目可能增大到$N^2p$.

MARS 从$p$个预测变量中,往已经存在$m$项的模型中加入基函数需要 $Nm^2+pmN$ 次操作。因此建立一个 $M$ 项的模型需要 $NM^3+pM^2N$ 次操作,如果 $M$ 是 $N$ 相当大的一个分数,则是严格需要避免的。

HME 的每一个组分在每个 $M$ 步一般不需要花费太多来拟合:对于回归需要 $Np^2$ 次,对于 $K$ 个类别的逻辑斯蒂回归需要$Np^2K^2$ 次。然而,EM 算法需要更长时间来收敛,因此较大的 HME 模型需要相当大的花费去拟合。

Comments