局部多项式估计

如果核函数 $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$$

于是我们得到了推广形式

$$\hat{\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)$

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

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

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

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

$$\begin{align}\hat{\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}\hat{\theta}_n(x)=\boldsymbol{a}_{nx}$。 当 $\mathcal{B}_{nx}$ 正定时,可以解得 $\hat{\theta}_n=\mathcal{B}_{nx}^{-1}\boldsymbol{a}_{nx}$ 。此时

$$\hat{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}\hat{\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}$ 正定,故 $\hat{\theta}_n(x)=q(x)$ ,则 $\hat{f}_n(x)=Q(x)$

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

引入假设

和之前一样,我们将误差分为偏差项 $b(x_0)=\mathbb{E}_f[\hat{f}_n(x_0)]-f(x_0)$ 和方差项 $\sigma^2(x_0)=\mathbb{E}_f[\hat{f}_n^2(x_0)]-(\mathbb{E}_f[\hat{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})$ ,两端取极限。左边为 $0.5$,右边为 $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)$,$\hat{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[\hat{f}(x_0)]-f(x_0)\\&=\mathbb{E}[\sum_{i=1}^{n}\hat{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\hat{f}_n-\mathbb{E}\hat{f}_n\rVert_\infty^2&=\mathbb{E}[\sup\limits_{x\in[0,1]}\lvert \hat{f}_n(x)-\mathbb{E}\hat{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 \hat{f}-\mathbb{E}\hat{f}\rVert_\infty^2\leq\frac{c’\log n}{nh}$

即 $\mathbb{E}\lVert\hat{f}-f\rVert_\infty^2\leq\frac{c’\log n}{nh}+c_2’h^{2\beta}$

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