ESL的笔记很久没有更新了，最近确实也比较忙，但更多的还是拖延症。笔记越写越详细，也间接地导致惰性越来越大，还是要经常自我鞭策才行啊。

书上对MARS的讲解其实非常简略，我特意去拜读了Friedman的原作，才对这个模型的来龙去脉有了一些大致的把握，对additive model和spline也有了更进一步的认识。

广义加法模型

顾名思义，这类模型试图用\(\sum_{j=1}^p f_j(X_j)\)来fit一个目标，这个目标广义而言是\(g[\mu(X)]\)，其中\(\mu(X) = \mathbb{E}(Y\vert X_1, X_2, \dots, X_p)\)，\(g\)被称作『link function』，书中列举了以下三种：

  • \(g(\mu) = \mu\)；对应于\(Y\vert X\)是是高斯的假设
  • \(g(\mu) = logit(\mu)\)；就是logistic regression
  • \(g(\mu) = \log(\mu)\)；对应于Possion假设

如果确定了响应变量\(Y\)，那么广义加法模型的loss function是这样的：

\[PRSS(f_1, f_2, \dots, f_p) = \sum_{i=1}^N\left( y_i - \sum_{j=1}^p f_j(x_{ij}) \right)^2 + \sum_{j=1}^p \lambda_j \int f_j^{\prime\prime}(t_j)^2 dt_j\]

这个其实和书的(5.9)式是一样的，这不过在第5章只有一个\(f\)，而这里是很多\(f_j\)的加和，于是表达能力也更强。\(f_j\)可以是任意的函数，从而在模型中引入非线性。PRSS的惩罚项是用于限制函数的曲率，从而限制overfitting.

书中的Backfitting算法，就是每次只求解其中一个\(f_j\)，求解的时候固定其他的\(f\)；\(\mathcal{S}_j\)是个算子，对于cubic smoothing spline而言，就是书上(5.14)式的\(\mathbf{S}_\lambda\)

基于树的模型

树模型从一般意义上讲，是additive model的一个特例，即\(f(\mathbf{x}) = \sum_{m=1}^p f_m(\mathbf{x})\)。只不过这里的\(f_m\)是基于对变量空间的划分，给定了\(M\)个划分\(\{R_m\}_1^M\)，则

\[\begin{equation*} f_m(\mathbf{x})=\begin{cases} a_m \quad \text{if}\ \mathbf{x}\in R_m \\ 0 \quad \text{otherwise} \end{cases} \end{equation*}\]

于是，树模型的数学表达就是下面这个样子，其中\(I\)是0/1 indicator函数，\(a_m\)是未知参数：

\[f(\mathbf{x}) = \sum_{m=1}^M a_m B_m(\mathbf{x}), \quad B_m(\mathbf{x}) = I[\mathbf{x}\in R_m]\]

接下来我们要想办法进一步地用数学式来表达\(R_m\)，对于树形结构而言，每次我们都会选择一个维度\(v\)，进行binary split，即找到一个分裂点\(t_v\)，左边是\(I(x_v < t_v)\)，右边是\(I(x_v > t_v)\)，于是对于某个点\(\mathbf{x}\)而言，它在叶子结点\(m\)的值\(B_m\)就是该叶子结点之上每一层的\(I\)的乘积。于是就能形式化地写成：

\[\begin{equation} \label{eq:leaf-model} B_m(\mathbf{x}) = \prod_{k=1}^{K_m} H[s_{km} \cdot (x_{v(k,m)} - t_{km})] \end{equation}\]

其中\(K_m\)表示为了得到叶子结点\(m\)，需要split几次（也就是路径上有几层），\(s_{km} \in \{ -1, +1\}\)分别表示叶子结点\(m\)的第\(k\)层的左右split，\(t_{km}\)表示分裂点，\(H\)是一个函数

\[\begin{equation*} H[\eta]=\begin{cases} 1 \quad \text{if}\ \eta \ge 0 \\ 0 \quad \text{otherwise} \end{cases} \end{equation*}\]

很显然，树模型的目的就是产生\(M\)个\(B_m\)，对应于\(M\)个叶子结点，在产生\(B_m\)的每一步，都乘上一个\(H\)函数，对应于binary split，这个算法总结如下（摘自Friedman的原始论文）：

其中\(m\)是region的个数，\(v\)是维数，\(j\)是数据点的个数，\(t\)是split point。这个算法试图从之前的叶子节点中（第3行）找到split后效果（通过LOF函数定义）最好的一个，产生右孩子（倒数第3行）和左孩子（倒数第4行，注意这是一个新的节点M，最外面的For循环每次都增加一个节点）。split point的选择（第5行）是从落在该叶子节点\(B_m\)中的所有训练数据（即\(B_m(\mathbf{x}_j) >0\)的含义）里遍历得到的，这是典型的非参方法，也是和第5章中的smoothing spline异曲同工的地方。

另外值得注意的是，\(B_{m^*}\)每轮迭代都会被更新，也就是说旧的\(B_{m^*}\)在这个算法中不会被保留，这是树结构的特征，也是与后文提到的MARS显著区别的一个点。

LOF函数的不同产生了不同的树算法。对于CART（classification and regression tree）而言，最小化残差产生了regression tree，最小化基尼系数产生了classification tree。

Algothrim-1有几个缺点。首先，式(\(\ref{eq:leaf-model}\))是一阶的，表达能力不够强；其次，每次删除旧的\(B_{m^*}\)使得模型无法拟合一些简单情况，比如不存在交叉项的简单线性模型（\(\sum_{m=1}^M a_m x_m\)这种形式）。

于是MARS（Multivariate Adaptive Regression Splines）被提了出来。针对Algo-1做了两点改进：

  • 使用\(B_m^{(q)}(\mathbf{x}) = \prod_{k=1}^{K_m} [s_{km} \cdot (x_{v(k,m)} - t_{km})]_{+}^q\)代替式(\(\ref{eq:leaf-model}\))，从而能够产生高阶拟合，通常\(q\)取\(1\)。下标+表示
\[\begin{equation*} (x-t)_{+}=\begin{cases} x-t \quad \text{if}\ x > t \\ 0 \quad \text{otherwise} \end{cases} \end{equation*}\]
  • 每次新增节点时，不删除原有的节点。这样如果一直选择\(B_1\)进行split的话，最后产生的模型就是简单线性模型。

同样的，我从Friedman的原始论文中截取了这个算法：

注意到上述第二点体现在Alog-2中的倒数第5行至倒数第3行。另外，为了保证阶数不高于\(q\)，MARS不允许在同一个变量上split多次（第4行）。

General地来说，CART和MARS都属于广义加法模型，MARS是CART的一般化，提供了高阶拟合特性，放弃了树状结构换取更灵活的结构捕捉能力。