[Note]ESL-5-Basis Expansions and Regularization

不做说明的话，本文讨论的\(x\)都是一维变量。

基函数

对于某个一维变量\(x\)，我们可以定义一个变换，这个变换是施加多个函数\(h_m\)的线性组合：

\[\begin{equation} \label{eq:transform} f(x) = \sum_{m=1}^M \beta_m h_m(x) \end{equation}\]

其中的\(h_m(\cdot)\)被称为『基函数(basis function)』。我们可以建立一个基函数的字典D，如果这个字典足够大，那么这个线性组合可以近似任意的空间变换（你可以将泰勒展开看作这个形式的一个特例），因此这是一个非常general的模型。实际使用中，为了避免overfitting，需要对模型进行一定的限制，一般而言有如下三种方法：

限制基函数的个数\(M\)
仅选择那些对模型拟合贡献最大的基函数\(h_m\)。CART、MARS、boosting等贪心算法就是该方法的特例（与之天生关联的是第三章介绍的variable selection/lasso等）
增加正则项，例如ridge/lasso等（注意lasso既是regularization方法，也是selection方法）

分段多项式和（回归）样条

分段多项式

分段多项式一般需要定义几个结点(knot)，这些结点把\(x\)分隔出不同区域，分别在这些区域上定义基函数，例如下面就是一个分段多项式的基函数：

\[h_1(x) = I(x<\xi_1), \quad h_2(x) = I(\xi_1 \leq x < \xi_2), \quad h_3(x) = I(\xi_2 \leq x)\]

三次样条(cubic spline)

所谓样条(spline)是一个平滑的分段多项式。所谓『平滑』的意思是在每个结点有相等的函数值、一阶导数和二阶导数。样条的阶数定义为其基函数的最大阶数。其中，以三阶样条(cubic spline)使用最为广泛。可以验证，对于一个拥有两个结点\(\xi_1\)和\(\xi_2\)的三阶样条，它的基函数为：

\[\begin{equation} \label{eq:cubic-two-knots-basis} \begin{split} h_1(x) = 1, \quad h_3(x) = x^2, \quad h_5(x) = (x-\xi_1)_+^3 \\ h_2(x) = x, \quad h_4(x) = x^3, \quad h_6(x) = (x-\xi_2)_+^3 \end{split} \end{equation}\]

相应的有6个\(\beta\)参数。

M阶(order-M)样条的基函数

更一般的，一个包含\(K\)个结点\(\xi_j, \quad j=1,\dots , K\)的\(M\)阶(order-\(M\))样条，它的一般形式如下：

\[\begin{equation} \begin{split} \label{eq:trun-pow-basis} h_j(x) &= x^{j-1},\quad j = 1, \dots , M \\ h_{M+l}(x) &= (x - \xi_l)_+^{M-1}, \quad l = 1, \dots , K \end{split} \end{equation}\]

可以看到三次样条(cubic spline)是\(M=4\)的特殊情况。最常用的阶数是\(M=1,2,4\)。

自然三次样条(natural cubic spline)

使用多项式来拟合数据，通常在边界处是不稳定的。自然三次样条(natural cubic spline)在三次样条的基础上要求在边界处线性，即basis function在\(x<\xi_1\)和\(x>\xi_K\)处是线性的。有很多在此限制下导出基函数的方法，若通过上一节介绍的truncated power series一般形式\(\ref{eq:trun-pow-basis}\)导出，可以证明其基函数如下：

\[\begin{equation} \label{eq:natural-cubic-spline-basis} N_1(x)=1, \quad N_2(x) = x, \quad N_{k+2}(x)=d_k(x)-d_{K-1}(x) \end{equation}\]

其中

\[d_k(x) = \frac{(x-\xi_k)_+^3 - (x-\xi_K)_+^3}{\xi_K - \xi_k}\]

以上这些需要预先确定结点的样条又被成为回归样条(regression spline)。

平滑样条(smoothing spline)

回归样条需要人工确定结点的个数和位置，这有时候并不是一件容易的事情。平滑样条(smoothing spline)不需要确定结点。事实上，数据集中出现的每一个独立元素都是一个结点，为了避免overfitting，需要对整体平滑程度进行惩罚。平滑样条是在所有存在二阶导的函数\(f(x)\)中找到一个函数，最小化残差：

\[RSS(F,\lambda) = \sum_{i=1}^N \{y_i - f(x_i) \}^2 + \lambda \int \{ f^{\prime\prime}(t) \}^2 dt\]

有趣的是，上式存在唯一的最优解：一个三次自然样条，该样条的结点在每一个独立元素\(x_i, i=1,\dots,N\)处。给每个基函数乘上对应的参数\(\theta_j\)，我们可以得到

\[f(x) = \sum_{j=1}^N N_j(x)\theta_j\]

其中\(N_j(\cdot)\)的定义如式\(\ref{eq:natural-cubic-spline-basis}\)所定义。带入得到

\[RSS(F,\lambda) = (\mathbf{y} - N\boldsymbol{\theta})^T (\mathbf{y} - N\boldsymbol{\theta})+ \lambda \boldsymbol{\theta}^T \Omega_N \boldsymbol{\theta}\]

其中\(N_{ij} = N_j(x_i)\)，\(\{ \Omega_N\}_{jk} = \int N_j^{\prime\prime}(t) N_k^{\prime\prime}(t) dt\)，解得

\[\begin{equation} \label{eq:smoothing-spline-ols-solution} \hat{\boldsymbol{\theta}} = (N^T N + \lambda \Omega_N)^{-1} N^T \mathbf{y} \end{equation}\]

自由度

自由度即『可自由变动的变量个数』，是统计中一个很重要的指标。对回归而言，控制自由度的大小，就是控制了模型的复杂程度，相当于增加了正则项。R中相关的包可以直接指定自由度的大小，例如smooth.spline(x,y,df=6)就可以指定用自由度为6的平滑样条拟合数据。

三次(cubic)样条的自由度

首先来考察三次样条的自由度。假设有\(K\)个结点，分成了\(K+1\)个区域，每个区域中的三次函数有\(4\)个参数，总共有\(4 \times (K+1)\)个参数；又由于每个结点处，要求函数值，一阶导，二阶导分别相等，那么总共有\(3K\)个限制条件(constraints)，得到自由度

\[\operatorname{df} = 4(K+1) - 3K = K+4\]

可见这和式\(\ref{eq:cubic-two-knots-basis}\)的基函数个数是一致的(\(K=2\)的情况）。

下面从另一个角度来考察这个问题。定义

\[\mathbf{f} \equiv [f_1(x), f_2(x), \dots , f_N(x)]^T\]

\(N\)是数据点的个数，\(f(x)\)如式\(\ref{eq:transform}\)所定义的基变换。再定义一个\(N\times M\)的矩阵\(B_{\xi}\)，每一行表示某个\(x\)处的\(M\)个三次样条基函数。定义\(\boldsymbol{\beta} = [\beta_1, \beta_2, \dots , \beta_M]^T\)，我们可以用最小二乘求出每个基函数前的系数：

\[\begin{align*} \hat{\boldsymbol{\beta}} &= \operatorname{argmin}\limits_{\boldsymbol{\beta}} \| \mathbf{y} - B_{\xi} \boldsymbol{\beta} \|_2 \\ &= (B_{\xi}^T B_{\xi})^{-1} B_{\xi}^T \mathbf{y} \end{align*}\]

于是我们得到

\[\begin{equation} \begin{split} \hat{\mathbf{f}} &= B_{\xi} \hat{\boldsymbol{\beta}} \\ &= B_{\xi} (B_{\xi}^T B_{\xi})^{-1} B_{\xi}^T \mathbf{y} \\ &\equiv H_{\xi} \mathbf{y} \end{split} \end{equation}\]

注意到\(H_{\xi}\)这个矩阵是一个idempotent矩阵(\(H_{\xi} H_{\xi} = H_{\xi}\))，因此有

\[\operatorname{trace}(H_\xi) = \operatorname{rank}(H_\xi) = M\]

即样条基函数的个数。由此我们可以用\(\operatorname{trace}(H_\xi)\)来表示三次样条的自由度（事实上，这也是最小二乘OLS自由度的定义）。在平滑样条的自由度计算中，将会类比这个概念。

平滑(smoothing)样条的自由度

平滑样条由于包含一个正则项，自由度的计算会比较困难。于是我们通过类比OLS的自由度来定义平滑样条的自由度。由式\(\ref{eq:smoothing-spline-ols-solution}\)可知，

\[\begin{align*} \hat{\mathbf{f}} &= N (N^T N + \lambda \Omega_N)^{-1} N^T \mathbf{y} \\ &= S_\lambda \mathbf{y} \end{align*}\]

\(S_\lambda\)和\(B_\xi\)有如下异同：

两者都是对称半正定矩阵
\(H_\xi H_\xi = H_\xi\)，而\(S_\lambda S_\lambda \preceq S_\lambda\)
\(\operatorname{rank}(H_\xi) = M\)，而\(\operatorname{rank}(S_\lambda) = N\)

类比\(H_\xi\)，我们可以把平滑样条的自由度定义为：

\[\operatorname{df}_\lambda = \operatorname{trace}(S_\lambda)\]

B-样条(B-spline)

B-样条是人为定义用于简化样条计算的一种工具，可以认为是『样条的基函数』。通过增加一些额外的结点，B-样条以递归的形式定义：

\[B_{i,m}(x) = \frac{x-\tau_i}{\tau_{i+m-1} - \tau_i} B_{i,m-1}(x) + \frac{\tau_{i+m}-x}{\tau_{i+m} - \tau_{i+1}} B_{i+1,m-1}(x)\]

符号的具体定义可参见书中章节附录。通过B-样条，可以生成任意阶数的样条。递归定义很容易转换为计算机程序，并且能够有效减少浮点运算次数。

应用

样条提供了一种非线性特征变换的方式。你可以对每一维特征作样条变换，然后用模型去fit weight。任何线性模型（OLS，LR，…）都是可以的。

Reproducing Kernel Hilbert Spaces

这一节把spline归入了一个更一般的，基于RKHP的正则化方法。首先我们定义任意的包含正则项的优化

\[\begin{equation} \label{eq:girosi} \min_{f\in \mathcal{H}} \left[ \sum_{i=1}^N L(y_i, f(x_i)) + \lambda J(f) \right] \end{equation}\]

在函数空间\(\mathcal{H}\)中求解\(f\)，对于正则项\(J(f)\)，一般的定义是

\[J(f) = \int_{\mathbb{R}^d} \frac{\vert \tilde{f}(s) \vert^2}{\tilde{G}(s)} ds\]

其中\(\tilde{f}\)是\(f\)的傅里叶变换，而随着\(\|s\|\)增大，\(\tilde{G}\)逐渐趋向于0，这个penalty的本质，就是惩罚了\(f\)函数的高频部分。注意到\(\tilde{G}\)的定义和第6章的Kernel局部方法是有异曲同工之处的。

妙的是，尽管\(J(f)\)是定义在无穷积分上的，\((\ref{eq:girosi})\)式在给定假设下，有finite的解的：

\[f(X) = \sum_{k=1}^K \alpha_k \phi_k(X) + \sum_{i=1}^N \theta_i G(X - x_i)\]

其中，\(\phi_k\)是正则项\(J\)张成的零空间（这块我不太懂）；\(G\)是\(\tilde{G}\)的傅里叶逆变换。书上说，平滑(smoothing)样条可以看作这种形式的一个特例。从直观上看，平滑样条对函数的二次导进行惩罚，和这里限制函数的高频部分是一致的，但从数学上如何推导，我还没有弄出个所以然来。