落园 » ≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记(八)|专注经济视角下的互联网

≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记(八)

平滑splines

有数据集D=\{(x_{i},y_{i}),1\leq i\leq N\},然后定义目标函数\sum_{i=1}^{N}(y_{i}-f(x_{i}))^{2}+\lambda\int_{a}^{b}f''(x)^{2}dx,记为(1)

式。然后我们有如下结论:使(1)最小化的解一定是分段三次多项式。

证明如下。

\mathcal{F}为函数族a=x_{0}<\cdots<xn<x_{n+1}=b上的分段三次多项式(splines),且在首尾两段[x_{0},x_{1}][x_{n},x_{n+1}]上是一次多项式,那么他一定有4(N-1)+2*2-3N=N的自由度。

f\in\mathcal{F},则当x\in[x_{0},x_{1}],\,\, x\in[x_{n},x_{n+1}]时,有f''(x)=0

(2) 我们设g(x)也是(1)式的解,则下面证明一定能找到f*使得目标函数比g(x)小,则f*\in F,

f*(x_{i})=g(x_{i}),\forall1\leq i\leq N.

(3)记h(x)=g(x)-f*(x),则h(x_{i})=0,\forall1\leq i\leq N

(4) 下面我们证明,h''(x)\perp f*''(两者内积为0),即\int_{a}^{b}h''(x)f*(x)''dx=0

\int_{a}^{b}h''(x)f*(x)''dx=\int_{a}^{b}f*(x)''dh'(x)=\underbrace{f*(x)''h'(x)\mid_{a}^{b}}_{0}-\int_{a}^{b}h'(x)df*(x)''

-\int_{a}^{b}h'(x)df*(x)''=-[\int_{a}^{x_{1}}+\sum_{i=1}^{N-1}\int_{x_{i}}^{x_{i+1}}+\int_{X_{N}}^{b}]=\begin{cases}\int_{a}^{x_{1}}h'(x)f*(x)'''dx & \equiv0\\\int_{X_{N}}^{b}h'(x)f*(x)'''dx & \equiv0\\\int_{x_{i}}^{x_{i+1}}h'(x)\underbrace{f*(x)'''}_{constant}dx & =f*(x)'''\underbrace{\int_{x_{i}}^{x_{i+1}}h'(x)dx}_{0}\end{cases}

所以得到h''(x)\perp f*''

(5)有了上述结论后,我们有g(x)=f*(x)+h(x)\Rightarrow g''(x)=f*(x)''+h''(x),然后有\left\Vert g''(x)\right\Vert ^{2}=\left\Vert f*(x)''+h''(x)\right\Vert ^{2}=\left\Vert f*(x)''\right\Vert ^{2}+\left\Vert h''(x)\right\Vert ^{2}\geq\left\Vert f*(x)''\right\Vert ^{2},所以对于所有的g,我们都有其二阶导数的范数小于f的二阶导数的范数,故在(1)式中代入g总比代入f大(或者相等)。这样我们就把一个无限维的最优化问题变为了有限维。

子波分析

1. 函数的平移与缩放

平移:f_{k}(x)=f(x-k)

缩放:f^{d}(x)=2^{d}f(2^{d}x)

组合起来就是f_{k}^{d}(x)=2^{d}f(2^{d}x-k)。由此,对于每个d,我们可以定义一个函数族\mathcal{F}^{d}:\{f_{k}^{d}(x),k\in\mathbb{Z}\},写成矩阵形式就是

\underbrace{\begin{array}{cccccccc} & & & & k\\ & \cdots & -2 & -1 & 0 & 1 & 2 & \cdots\\ & -2\\d & -1 & & \ddots\\ & 0 & & & f_{0}^{0}(x)\\ & 1 & & & & f_{1}^{1}(x)\\ & 2 & & & & & \ddots\\ & \vdots\end{array}}_{\mathcal{F}^{d}}

2. Hoar函数

(1)定义: h(x)=\begin{cases} 0 & 0 \leq x \leq 1\\ 1 & else\end{cases}

(2)Hoar函数的平滑与缩放。定义Hoar函数族为\mathcal{H}^{d}:\{h_{k}^{d}(x),k\in\mathbb{Z}\},

\forall d\in\mathbb{Z}。这样我们每个\mathcal{H}^{d}为一组(胖瘦一样)。

定理1(正交):\mathcal{H}^{d}L^{2}(\mathbb{R})平方可积函数的一个正交基,即对于任意的k\neq g,有<h_{k}^{d}(x),h_{g}^{d}(x)>=\int h_{k}^{d}h_{g}^{d}dx=0

定理2(增长):随着d的增加,\mathcal{H}^{d}张成的闭子空间逐渐增大,且\overline{\mathcal{H}^{d}}\subseteq\overline{\mathcal{H}^{d+r}}。这样,d比较小的函数一定能用d比较大的函数(正交基)来表示,比如h_{0}^{0}(x)=h_{0}^{1}(x)+h_{1}^{1}(x)/2。直观的理解就是,d越大,分辨率越高。

定理3(完备):\overline{\mathcal{H}^{d}}\uparrow L^{2}(\mathbb{R})

(3)定义\omega^{d},使\omega^{d}=\mathcal{H}^{d+1}\ominus\mathcal{H}^{d},或者\mathcal{H}^{d+1}=\omega^{d}\oplus\mathcal{H}^{d}

(4)定义w(x)=\begin{cases}1 & 0\leq x\leq\frac{1}{2}\\-1 & \frac{1}{2}\leq x\leq1\\0 & else\end{cases},然后w_{k}^{d}(x)=2^{d}w(2^{d}x-k),k,d\in\mathbb{Z}

定理4:函数族\omega^{d}:\{w_{k}^{d}(x),k\in\mathbb{Z}\},\forall d\in\mathbb{Z},则\oplus_{d}\omega^{d}=L^{2}(\mathbb{R})亦为完备基,且\omega^{d}\perp\omega^{d\text{?}},如果d\neq d'。也就是说,\overline{\mathcal{H}^{d+1}}\overline{\mathcal{H}^{d}}之间的空间随着d的增加,彼此正交,且所有的叠起来之后亦为完备空间。

如此,我们称w(x)为子波(mother)而h(x)为father函数。注意,这里Hoar函数非连续。

在更一般的场合,我们寻找f(x)为father函数,然后定义\mathcal{F}^{d}:\{f_{k}^{d}(x),k\in\mathbb{Z}\},满足<f_{k}^{d}(x),f_{g}^{d}(x)>=0(正交),且\overline{\mathcal{\mathcal{F}}^{d}}\subseteq\overline{\mathcal{F}^{d+r}}(增长),\overline{\mathcal{F}^{d}}\uparrow L^{2}(\mathbb{R})(完备)。

再寻找mother函数g(x)满足<g_{k}^{d}(x),g_{g}^{d}(x)>=0(同层次内正交)、\mathcal{\mathcal{F}}^{d+1}=\mathcal{G}^{d}\oplus\mathcal{F}^{d}(相邻层次正交补)和\oplus_{d}\mathcal{G}^{d}=L^{2}(\mathbb{R})完备。

这样的f(x)g(x)到底存不存在呢?实证结论是存在,而且很多,不过坏消息是他们的形式都不算简单。

spline和子波分析

spline和子波分析都提供了一组线性基底,其线性组合可以定义函数类。由此,我们可以定义广义线性模型的函数族,为统计学习模型的函数族做约束。


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *