局部多项式估计

如果核函数 \(K\) 只取非负值,可以发现 Nadaraya-Waston 估计 \(f_n^{NW}\) 满足下列式子

\[f_n^{NW}(x)=\arg\min\limits_{\theta\in\mathbb{R}}\sum\limits_{i=1}^{n}(Y_i-\theta)^2K\left(\frac{X_i-x}{h}\right)\]

这一结论只需使用一次导数就可以立刻得到,熟悉线性回归的读者应该不会陌生。

这说明了,\(f_n^{NW}\) 给出的是在 \(x\) 处,均方误差最小的一个常数估计,而这是可以被推广的——我们使用一个 \(l\) 阶多项式代替上式中的常数 \(\theta\) 。具体说来,如果 \(f\in\Sigma(\beta,L),\,\beta>1,\,l=\lfloor\beta\rfloor\),那么对于充分接近 \(x\)\(z\) 我们有

\[f(z)\approx f(x)+f'(x)(z-x)+\cdots+\frac{f^{(l)}(x)}{x!}(z-x)^l=\theta^\intercal(x)U\left(\frac{z-x}{h}\right)\]

其中

\[U(u)=\Big(1,u,u^2/2!,\ldots,u^l/l!\Big)^\intercal\]

\[\theta(x)=\Big(f(x),f'(x)h,f''(x)h^2,\ldots,f^{(l)}(x)h^l\Big)^\intercal\]

于是我们得到了推广形式

\[\widehat{\theta}_n(x)=\arg\min\limits_{\theta\in\mathbb{R}^{l+1}}\sum\limits_{i=1}^{n}\left[Y_i-\theta^\intercal U\left(\frac{X_i-x}{h}\right)\right]^2K\left(\frac{X_i-x}{h}\right)\]

我们称其为 \(\theta(x)\)\(l\) 阶局部多项式估计,简记为 \(\mathrm{LP}(l)\ \text{ estimator of }\ \theta(x)\)

此时, \(\widehat{f}_n(x)=U^\intercal (0)\widehat{\theta}_n(x)\) 称为 \(f(x)\)\(l\) 阶局部多项式估计,简记为 \(\mathrm{LP}(l)\ \text{ estimator of }\ f(x)\)

可以发现 \(\widehat{f}_n(x)\) 其实就是 \(\widehat{\theta}_n(x)\) 的第一个分量。而其余的分量则提供了 \(f'(x),\ldots,f^{(l)}(x)\) 等的估计

\(K\ge 0\) 时,我们之前的 \(f_n^{NW}\) 也就是 \(\mathrm{LP}(0)\) 估计。

现在我们开始详细地查看 \(\widehat{\theta}_n\)。为方便记,我们将式子中的平方展开,得

\[\begin{align}\widehat{\theta}_n(x)&=\arg\min\limits_{\theta\in\mathbb{R}^{l+1}}\left\{-2\theta^\intercal\sum\limits_{i=1}^{n}Y_i U\left(\frac{X_i-x}{h}\right)K\left(\frac{X_i-x}{h}\right)+\theta^\intercal \sum\limits_{i=1}^{n}\left[U\left(\frac{X_i-x}{h}\right)U^\intercal\left(\frac{X_i-x}{h}\right)K\left(\frac{X_i-x}{h}\right)\right]\theta\right\}\\&=\arg\min\limits_{\theta\in\mathbb{R}^{l+1}}nh\cdot(-2\theta^\intercal \boldsymbol{a}_{nx}+\theta^\intercal\mathcal{B}_{nx}\theta)\end{align}\]

其中定义

\[\boldsymbol{a}_{nx}=\frac{1}{nh}\sum_{i=1}^{n}Y_i U\left(\frac{X_i-x}{h}\right)K\left(\frac{X_i-x}{h}\right)\]

\[\mathcal{B}_{nx}=\frac{1}{nh}\sum\limits_{i=1}^{n}\left[U\left(\frac{X_i-x}{h}\right)U^\intercal\left(\frac{X_i-x}{h}\right)K\left(\frac{X_i-x}{h}\right)\right]\]

求导立得约束条件 \(\mathcal{B}_{nx}\widehat{\theta}_n(x)=\boldsymbol{a}_{nx}\)。 当 \(\mathcal{B}_{nx}\) 正定时,可以解得 \(\widehat{\theta}_n=\mathcal{B}_{nx}^{-1}\boldsymbol{a}_{nx}\) 。此时

\[\widehat{f}_n(x)=\frac{1}{nh}\sum\limits_{i=1}^{n}Y_i U^\intercal(0)\mathcal{B}_{nx}^{-1}U\left(\frac{X_i-x}{h}\right)K\left(\frac{X_i-x}{h}\right)\overset{\Delta}{=} \sum\limits_{i=1}^{n}Y_i W_{ni}^\ast(x)\]

\(W_{ni}^\ast(x)\) 的计算也不依赖与 \(Y\) 的值,也就是说此时我们得到了一个非参线性估计。

既然与 \(Y\) 的值无关,事实上我们有如下命题:当 \(x\) 满足 \(\mathcal{B}_{nx}\) 正定且 \(Q\) 为一个不超过 \(l\) 阶的多项式,那么我们的 \(\mathrm{LP}(l)\) 给出的权重 \(W_{ni}^\ast\) 满足 \(\sum\limits_{i=1}^{n}Q(X_i)W_{ni}^\ast(x)=Q(x)\) 其证明思路简述如下

首先我们可以有 \(Q(X_i)=Q(x)+Q'(x)(X_i-x)+\ldots+\frac{Q^{(l)}(x)}{l!}(X_i-x)^l=q^\intercal(x) U\left(\frac{X_i-x}{h}\right)\) 其中 \(q^\intercal(x)=\big(Q(x),Q'(x)h,\ldots,Q^{(l)}(x)h^l\big)\in\mathbb{R}^{l+1}\)

然后设 \(Y_i=Q(X_i)\),使用 \(\mathrm{LP}(l)\) 估计得

\[\begin{align}\widehat{\theta}_n(x)&=\arg\min\limits_{\theta\in\mathbb{R}^{l+1}}\sum\limits_{i=1}^{n}\left[Q(X_i)-\theta^\intercal U\left(\frac{X_i-x}{h}\right)\right]^2K\left(\frac{X_i-x}{h}\right)\\&=\arg\min\limits_{\theta\in\mathbb{R}^{l+1}}\sum\limits_{i=1}^{n}\left[(q(x)-\theta)^\intercal U\left(\frac{X_i-x}{h}\right)\right]^2K\left(\frac{X_i-x}{h}\right)\\&=\arg\min\limits_{\theta\in\mathbb{R}^{l+1}}(q(x)-\theta)^\intercal \mathcal{B}_{nx}(q(x)-\theta)\end{align}\]

\(\mathcal{B}_{nx}\) 正定,故 \(\widehat{\theta}_n(x)=q(x)\) ,则 \(\widehat{f}_n(x)=Q(x)\)

也就是说,局部多项式回归可以更精细的刻画拟合的结果。

引入假设

和之前一样,我们将误差分为偏差项 \(b(x_0)=\mathbb{E}_f[\widehat{f}_n(x_0)]-f(x_0)\) 和方差项 \(\sigma^2(x_0)=\mathbb{E}_f[\widehat{f}_n^2(x_0)]-(\mathbb{E}_f[\widehat{f}_n(x_0)])^2\) 。其中 \(f\)\(Y_i=f(X_i)+\xi_i\) 中的 \(f\),即真实但未知的一个映射。

不难证明,单点误差 \(\mathrm{MSE}(x_0)=b^2(x_0)+\sigma^2(x_0)\)

在进行误差分析之前,我们需要引入一些假设。

  • 存在实数 \(\lambda_0>0\) 和正整数 \(n_0\),使得对所有 \(n\ge n_0\) 和任意 \(x\in[0,1]\),均有最小的特征值 \(\lambda_\min(\mathcal{B}_{nx})\ge\lambda_0\)。这一假设是比正定性更强的一个假设,因为他要求对 \(n\)\(x\) 一致正定。

    同时,由于 \(\mathcal{B}_{nx}\) 是对称阵,因此该假设也隐含了,对于任意 \(n\ge n_0,\, x\in[0,1],\, v\in\mathbb{R}^{l+1}\) 均有 \(\Vert\mathcal{B}_{nx}^{-1}v\rVert\leq\lVert v\rVert/\lambda_0\) 。如果读者对这一结论并不熟悉,参看之前的博文里关于矩阵基础知识的介绍 【Note】 多元统计分析(一)——矩阵的基础知识

  • 存在实数 \(a_0>0\) 使得对任意区间 \(A\subseteq [0,1]\) 和所有的 \(n\geq 1\) ,均有 \(\sum\limits_{i=1}^{n}\boldsymbol{1}[X_i\in A]\leq a_0\max\{n\cdot\mathrm{Leb}(A), 1\}\), 其中 \(\mathrm{Leb}(A)\)\(A\) 的勒贝格测度。这一假设刻画了 \(X_i\) 在区间 \([0,1]\) 上都足够密集。一个极端的例子是,假如所有的样本点中始终有 \(50\%\) 落在 \(x_0\) 处,那么取 \(A_n=(x_0-\frac{1}{2n},x_0+\frac{1}{2n})\) ,两端取极限。左边为 \(n/2\),右边为 \(a_0\) 就不成立了。但一般的 \(X_i\) 的分布都会满足这一假设。

  • 核函数 \(K\) 有紧的支撑集且落在 \([-1,1]\) 上,且 \(K\) 有界。这基本上也都是会被满足的。

有了这三条假设后,我们可以给出关于 \(W_{ni}^\ast(x)\) 的三个引理:对任意 \(n\ge n_0,\,h\ge 1/(2n),\,x\in[0,1]\) 均有只依赖于 \(\lambda_0,a_0,K_\max\) 的常数 \(C_\ast\),使得

  • \(\sup\limits_{i,x}\lvert W_{ni}^\ast(x)\rvert\leq\frac{C_\ast}{nh}\)
  • \(\sum\limits_{i=1}^{n}\lvert W_{ni}^{*}(x)\rvert\leq C_\ast\)
  • \(W_{ni}^{*}(x)=0\quad\text{if}\quad\lvert X_i-x\rvert>h\)

证明:首先,由 \(\lVert U(0)\rVert=1\) 和 假设一可以推出

\[\begin{align}\lvert W_{ni}^\ast(x)\rvert&\leq\frac{1}{nh}\left\lVert\mathcal{B}_{nx}^{-1}U\left(\frac{X_i-x}{h}\right)K\left(\frac{X_i-x}{h}\right)\right\rVert\\&\leq\frac{1}{nh\lambda_0}\left\lVert U\left(\frac{X_i-x}{h}\right)K\left(\frac{X_i-x}{h}\right)\right\rVert\\&\leq\frac{K_\max}{nh\lambda_0}\left\lVert U\left(\frac{X_i-x}{h}\right)\right\rVert\cdot\boldsymbol{1}\left[\left\lvert\frac{X_i-x}{h}\right\rvert\leq 1\right]\\&\leq\frac{K_\max}{nh\lambda_0}\sqrt{1+\frac{1}{(1!)^2}+\frac{1}{(2!)^2}+\cdots++\frac{1}{(l!)^2}}\leq\frac{2K_\max}{nh\lambda_0}\end{align}\]

类似的,利用假设二,我们有

\[\sum_{i=1}^{n}\lvert W_{ni}^\ast(x)\rvert\leq\frac{2K_\max}{nh\lambda_0}\sum_{i=1}^{n}\mathbb{1}[x-h\leq X_i\leq x+h]\leq\frac{2K_\max a_0}{nh\lambda_0}\max\{2nh,1\}\leq\frac{4K_\max a_0}{\lambda_0}\]

于是取 \(C_\ast=\max\{2K_\max/\lambda_0, 4K_\max a_0/\lambda_0\}\) 即完成证明

第三条则由 \(K(u)\) 的支撑集在 \([-1,1]\) 内立得。

误差分析

MSE 和 MISE

现在开始误差的分析。设 \(f\in\Sigma(\beta,L)\)\(\widehat{f}\)\(LP(\lfloor\beta\rfloor)\) 估计。并假设 \(X_1,\ldots,X_n\) 确定,上述三个假设满足,且 \(\xi_i\) 均值为零方差有限。那么对 \(\forall x_0\in[0,1], n>n_0, h\ge 1/(2n)\),有如下上界

\[\lvert b(x_0)\rvert\leq \frac{L\cdot C_\ast}{\ell!} h^\beta,\sigma^2(x_0)\leq \frac{C_\ast^2\cdot\sigma_\max^2}{nh}\]

\[\begin{align}b(x_0)&=\mathbb{E}_f[\widehat{f}(x_0)]-f(x_0)\\&=\mathbb{E}[\sum_{i=1}^{n}\widehat{f}(X_i)W_{ni}^\ast(x_0)]-f(x_0)\\&=\sum_{i=1}^{n}f(X_i)W_{ni}^\ast(x_0)-f(x_0)\\&=\sum_{i=1}^{n}(f(X_i)-f(x_0))W_{ni}^\ast(x_0)\\&=\sum_{i=1}^{n}\frac { f ^ { ( \ell ) } \left( x _ { 0 } + \tau _ { i } \left( X _ { i } - x _ { 0 } \right) \right) - f ^ { ( \ell ) } \left( x _ { 0 } \right) } { \ell ! } \left( X _ { i } - x _ { 0 } \right) ^ { \ell } W _ { n i } ^ { * } \left( x _ { 0 } \right)\end{align}\]

使用刚才证明的引理

\[\begin{aligned} \left| b \left( x _ { 0 } \right) \right| & \leq \sum _ { i = 1 } ^ { n } \frac { L \left| X _ { i } - x _ { 0 } \right| ^ { \beta } } { \ell ! } \left| W _ { n i } ^ { \ast } \left( x _ { 0 } \right) \right| \\ & = L \sum _ { i = 1 } ^ { n } \frac { \left| X _ { i } - x _ { 0 } \right| ^ { \beta } } { \ell ! } \left| W _ { n i } ^ { \ast } \left( x _ { 0 } \right) \right| I \left( \left| X _ { i } - x _ { 0 } \right| \leq h \right) \\ & \leq L \sum _ { i = 1 } ^ { n } \frac { h ^ { \beta } } { \ell ! } \left| W _ { n i } ^ { \ast } \left( x _ { 0 } \right) \right|\\& \leq \frac { L\cdot C _ { \ast } } { \ell ! } h ^ { \beta } \end{aligned}\]

\[\begin{aligned} \sigma ^ { 2 } \left( x _ { 0 } \right) & = \mathbb { E } \left[ \left( \sum _ { i = 1 } ^ { n } \xi _ { i } W _ { n i } ^ { \ast } \left( x _ { 0 } \right) \right) ^ { 2 } \right] = \sum _ { i = 1 } ^ { n } \left( W _ { n i } ^ { \ast } \left( x _ { 0 } \right) \right) ^ { 2 } \mathbb { E } \left( \xi _ { i } ^ { 2 } \right) \\ & \leq \sigma _ { \max } ^ { 2 } \sup _ { i , x } \left| W _ { n i } ^ { \ast } ( x ) \right| \sum _ { i = 1 } ^ { n } \left| W _ { n i } ^ { \ast } \left( x _ { 0 } \right) \right| \\&\leq \frac { \sigma _ { \max } ^ { 2 } \cdot C _ { \ast } ^ { 2 } } { n h } \end{aligned}\]

所以 \(\mathrm{MSE}\leq C_1h^{2\beta}+\frac{C_2}{nh}\),故可证明上界有 \(O(n^{-2\beta/(2\beta+1)})\)

同时也可以证明 \(\mathrm{MISE}\leq O(n^{-2\beta/(2\beta+1)})\)

无穷范数

考察无穷范数时我们需要更强的假设——假设 \(\xi_i\) 是独立同分布的高斯函数,均值零且方差有限。 \(K\) 是 Lipschitz 核函数即 \(K\in\Sigma(1,L_K),0<L_K<\infty\)。在同样的假设下我们可以证明其收敛速度为 \((\log n/n)^{-2\beta/(2\beta+1)}\)

首先

\[\begin{aligned}\mathbb{E}_f \left\| \hat { f } _ { n } - f \right\| _ { \infty } ^ { 2 } & \leq \mathbb{E}_f\left[ \left\| \hat { f } _ { n } - \mathbf { E } \hat { f } _ { n } \right\| _ { \infty } + \left\| \mathbb{E}_f \hat { f } _ { n } - f \right\| _ { \infty } \right] ^ { 2 } \\ & \leq 2 \mathbb{E}_f \left\| \hat { f } _ { n } - \mathbb{E}_f \hat { f } _ { n } \right\| _ { \infty } ^ { 2 } + 2 \left( \sup _ { x \in [ 0,1 ] } | b ( x ) | \right) ^ { 2 } \\ & \leq 2 \mathbb{E}_f \left\| \hat { f } _ { n } - \mathbb{E}_f \hat { f } _ { n } \right\| _ { \infty } ^ { 2 } + 2 q _ { 1 } ^ { 2 } h _ { n } ^ { 2 \beta } \end{aligned}\]

\(W_{ni}^\ast(x)=\frac{1}{nh}U^\intercal(0)\mathcal{B}_{nx}^{-1}U\left(\frac{X_i-x}{h}\right)K\left(\frac{X_i-x}{h}\right)\overset{\Delta}{=}\frac{1}{nh}U^\intercal(0)\mathcal{B}_{nx}^{-1}S_i(x)\)

\[\begin{align}\mathbb{E}\lVert\widehat{f}_n-\mathbb{E}\widehat{f}_n\rVert_\infty^2&=\mathbb{E}[\sup\limits_{x\in[0,1]}\lvert \widehat{f}_n(x)-\mathbb{E}\widehat{f}_n(x)\rvert^2]\\&=\mathbb{E}[\sup\limits_{x\in[0,1]}\lvert \sum_{i=1}^{n}\xi_iW_{ni}^\ast(x)\rvert^2]\\&\leq\mathbb{E}[\sup\limits_{x\in[0,1]}\lVert \frac{1}{nh}\mathcal{B}_{nx}^{-1}\sum_{i=1}^{n}\xi_i S_i(x)\rVert^2]\\&\leq\frac{1}{\lambda_0^2n^2h^2}\mathbb{E}[\sup\limits_{x\in[0,1]}\lVert \sum_{i=1}^{n}\xi_i S_i(x)\rVert^2]\end{align}\]

核心在于估计出 \(\sup\limits_{x\in[0,1]}\lVert\sum_{i=1}^{n}\xi_iS_i(x)\rVert^2\)。为此,我们选定 \(M=n^2\) 个“锚点”来控制住整个上界。令 \(x_j=j/M,j=1,2,\ldots,M\),我们有

\[\begin{align}\sup\limits_{x\in[0,1]}\lVert\sum_{i=1}^{n}\xi_iS_i(x)\rVert^2&\leq(\max_\limits{1\leq j\leq M}\lVert\sum_{i=1}^{n}\xi_iS_i(x_j)\rVert+\sup\limits_{x,x':|x-x'|\leq 1/M}\lVert\sum_{i=1}^{n}\xi_i(S_i(x)-S_i(x'))\rVert)^2\\&\leq2(\max_\limits{1\leq j\leq M}\lVert\sum_{i=1}^{n}\xi_iS_i(x_j)\rVert)^2+2(\sup\limits_{x,x':|x-x'|\leq 1/M}\lVert\sum_{i=1}^{n}\xi_i(S_i(x)-S_i(x'))\rVert)^2\end{align}\]

由于 \(K\in\Sigma(1,L_K)\), 支撑集为 \([-1,1]\),且 \(U\) 是多项式组成的函数向量,可以证明

\[\lVert U(u)K(u)-U(u')K(u')\rVert\leq\bar{L}\lvert u-u'\rvert\]

所以后面一项的期望可以被控制为 \[2(\frac{\bar{L}}{Mh}\sum_{i=1}^{n}\lvert\mathbb{E}\xi_i\rvert)^2\leq\frac{2n^2\bar{L}^2}{M^2h^2}\sup\mathbb{E}\xi_i^2\leq \frac{2n^2\bar{L}^2\sigma_\max^2}{M^2h^2}\]

乘上前面的因子,得到其为 \(\frac{2\bar{L}^2\sigma_\max^2}{M^2h^4}=\frac{2\bar{L}^2\sigma_\max^2}{(nh)^4}=o(\frac{1}{nh})\)

所以这一块的影响不大。现在考察前面的一项,构造 \(\eta_j=\frac{1}{\sqrt{nh}}\sum_{i=1}^{n}\xi_iS_i(x_j)\),其为均值为零的高斯向量。

\[\mathbb{E}\lVert\eta_j\rVert^2=\frac{1}{nh}\sum_{i=1}^{n}\sigma_\xi^2\left\lVert U\left(\frac{X_i-x_j}{h}\right)\right\rVert^2K^2\left(\frac{X_i-x_j}{h}\right)\leq\frac{4K_\max^2\sigma_\xi^2}{nh}\sum_{i=1}^{n}\boldsymbol{1}[\lvert X_i-x_j\rvert\leq h]\leq 4K_\max^2\sigma_\xi^2 a_0\max(2,1/nh)\]

由引理则有 \(\mathbb{E}[\max_\limits{1\leq j\leq M}\lVert\eta_j\rVert^2]=O(\log M)=O(\log n)\)

所以得到 \(\mathbb{E}\lVert \widehat{f}-\mathbb{E}\widehat{f}\rVert_\infty^2\leq\frac{c'\log n}{nh}\)

\(\mathbb{E}\lVert\widehat{f}-f\rVert_\infty^2\leq\frac{c'\log n}{nh}+c_2'h^{2\beta}\)

于是得到无穷范数的收敛速度是 \((\log n/n)^{-2\beta/(2\beta+1)}\)