其中$g[\mu] = \mu$, $logit(\mu)$, or $\log(\mu)$, 是 link function, 默认 $\alpha = ave (y_i)$, 也就是 $\sum_{i=1}^N f_j (x_{i,j}) = 0$。
- Initialize:$\hat{\alpha} = \tfrac{1}{N}\sum_1^N y_i, \hat{f}_j \equiv 0, \forall i,j. $
- Cycle: j = 1,2,...,p,...,1,2,...,p,...,
\begin{align} \hat{f}_j \leftarrow & S_j\left[ \{ y_i - \hat{\alpha} -\sum_{k\ neq j}\hat{f}_k(x_{ik}) \}_1^N\right] \\ \hat{f}_j \leftarrow & \hat{f}_j - \frac{1}{N}\sum_{i=1}^N \hat{f}_j(x_{ij}) \end{align} 上述 Cycle 里面的第二步 理论上是不需要的,因为所有的 $\hat{f}_j$ 总和为0。但实际程序运行时,会有偏差,所以需要归零。
由于遍历所有组合会导致过拟合,所以需要减枝,于是就有了 regression tree 和 classification tree。
CART (classification and regression tree) 算法。就是上述的生成树模型的算法。
PRIM (patient rule induction method) 算法。从所有数据出发,先捕捉一块特征值(response mean)最高的数据,然后移除该数据,重复上述操作,再次捕捉。类似与捕鱼,先捕大鱼,再捕小鱼,最后是虾米。原理上,PRIM 与 CART 类似,也是将所有数据分割,但分割的更细致,不像 CART 快刀斩乱麻,一分为二。
MARS (Maltivariate Adaptive Regression Splines) 算法,尤其适用于高维空间。定义了一个 piecewise linear 的 basis functions,
MARS 可以表示为 \begin{align} f(X) = \beta_0 + \sum_{m=1}^M \beta_m h_m(X), \end{align} 其中, $h_m(X) \in \mathbf{C}$. MARS 有点: 可以同时处理定量和定性的混合输入.
MARS can handle "mixed" predictors--quantitative and qualitative--in a natural way, much like CART does.
Expert Network 可以表示为 $Y \sim \Pr(y|x,\theta_{jl})$, 其中根据 regression 或者 classification 不同, \begin{align} \Pr(y|x,\theta_{jl}) =& \beta_{jl}^Tx+\epsilon \\ \Pr(y=1|x,\theta_{jl}) =& \frac{1}{1+ e^{-\theta_{jl}^Tx}}. \end{align} 最终 HME 表达模型为 \begin{align} \Pr(y|x,\Psi) = \sum_{j=1}^Kg_j(x,\gamma_j)\sum_{l=1}^Kg_{l|j}(x,\gamma_{jl})\Pr(y|x,\theta_{jl}). \end{align}
定义 \begin{align} N_m =& \#\{x_i \in R_m\} \\ \hat{c}_m =& \frac{1}{N}\sum_{x_i \in R_i} y_i, \\ Q_{m}(T) =& \frac{1}{N}\sum_{x_i \in R_i} (y_i - \hat{c}_m)^2 \end{align} 从而最小化 \begin{align} C_{\alpha}(T) = \sum_{m=1}^{|T|}N_m Q_m(T) + \alpha |T| \end{align} 其中 $\alpha$ 就是可调的参数,决定树的大小。
和 regression tree 类似,需要重新定义 $Q_m(T)$。引入 class-k 在 node-m 的概率 \begin{align} \hat{p}_{mk} = \frac{1}{N_m} \sum_{x_i \in R_m}I(y_i=k) \end{align} $Q_m(T)$ 可以表示为三类: