ABSTRACT

In this paper, we study the error analysis of indefinite kernel network with coefficient regularization for non-iid sampling. The framework under investigation is different from classical kernel learning. The kernel function satisfies only the continuity and uniform boundedness; the standard bound assumption for output data is abandoned and we carry out the error analysis with output sample values satisfying a generalized moment hypothesis. Satisfactory error bounds and learning rates independent of capacity are derived by the techniques of integral operator for this learning algorithm.

Keywords:Coefficient Regularization Regression, Indefinite Kernel, Strong Mixing Condition, Integral Operator

基于非独立同分布样本的系数正则化回归算法的误差分析

常欣欣¹，陈爽²

¹河北工业大学，天津

²北京石油化工学院，北京

收稿日期：2017年10月4日；录用日期：2017年10月20日；发布日期：2017年10月30日

摘 要

本文分析了基于非独立同分布样本的最小二乘系数正则化算法的误差。全文的框架不同于以往的经典核学习方法。核函数仅仅满足连续性和一致有界性；我们进行基于输出样本满足广义矩理论的误差分析，而不再考虑标准的输出有界假设。最后通过利用积分算子技术得到了满意的与容量无关的误差界和学习率。

关键词 :系数正则化回归，不定核，强混合条件，积分算子

Copyright © 2017 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

在机器学习理论中，最小二乘回归问题可以陈述如下：

设 $X$ 为一个紧子集， $Y=R$ 。 $\rho$ 为 $Z:X\times Y$ 上未知的概率测度， $z={\left\{\left(x_i,y_i\right)\right\}}_{i=1}^m\in Z^m$ 为服从 $\rho$ 的一组独立同分布的取样。在回归学习中定义关于函数 $f:X\to Y$ 的推广误差，

$\epsilon \left(f\right)={\displaystyle {\int }_Z{\left(f\left(x\right)-y\right)}^2\text{d}\rho }$

回归函数定义为

$f_{\rho }\left(x\right)=E\left(y|x\right)={\displaystyle {\int }_{Y}y\text{d}\rho \left(y|x\right)},x\in X$

记 $\rho \left(y|x\right)$ 为 $\rho$ 在 $X=x$ 时的条件分布。实际上，由于 $\rho$ 是未知的， $f_{\rho }$ 是不能直接求出来的，于是我们的目标是利用样本 $z$ 产生关于 $f_{\rho }$ 的一个最佳逼近。

传统的学习算法所选取的假设空间通常为与Mercer核相关的再生核Hilbert空间。基于核的学习算法具有良好的运算性质，这得益于再生核Hilbert空间所特有的再生性。核函数最初用于模式识别，现在已经广泛成功应用于机器学习的很多领域。在基于核函数的学习中，核函数 $K:X\times X\to R$ 扮演着基函数的角色。

下面给出Mercer核和再生核Hilbert空间的定义：

定义1.1 (Mercer核)设函数 $K:X\times X\to R$ 为连续的，对称的，半正定的，则称 $K$ 为Mercer核。

定义1.2 (再生核Hilbert空间)由 $K_x=K\left(x,\cdot \right),x\in X$ 的有限线性组合成的线性函数空间，

$\left\{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{a}_i{K}_{x_i}}:a_i\in R,x_i\in X,i=1,2,\cdots ,m;m\in N\right\}$

在该函数空间中定义内积

${\langle {\displaystyle \underset{i=1}{\overset{n}{\sum }}{a}_i{K}_{x_i},}{\displaystyle \underset{j=1}{\overset{m}{\sum }}{b}_j}{K}_{x_j}\rangle }_K={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{m}{\sum }}{a}_i{b}_j}}K\left(x_i,y_j\right)$

则该函数空间成为内积空间。其完备化的Hilbert空间称由核函数 $K$ 所生成的再生核Hilbert空间(RKHS)，记为 $H_K$ 。

$H_K$ 的再生性指

$f\left(x\right)={\langle f,K_x\rangle }_K$ 对任意 $f\in H_K,x\in X$

大量的文献都有对Mercer核的研究学习，可以见参考文献 [1] [2] [3] [4] 。

为了防止过拟合，一般采用正则化方法 [5] 。常用的回归学习算法有正则化最小二乘算法与系数正则化算法。

正则化最小二乘算法形式：

$f_{Z,K}=\arg \underset{f\in H_K}{\min }\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\left(y_i-f\left(x_i\right)\right)}^2}+\lambda {\Vert f\Vert }_K^2$ (1.1)

关于这个算法的学习可以看文献 [6] [7] [8] 。

接下来给出系数正则化算法(CRKN) [9] [10] [11] ：

$f_{Z,\lambda }=f_{{\alpha }_Z}$ 其中 ${\alpha }_Z=\arg \underset{\alpha \in R^m}{\min }\left\{\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\left(f_{\alpha }\left(x_i\right)-y_i\right)}^2}+\lambda {\Omega }_Z\left(f\right)\right\},\lambda >0$

这里 $f_{\alpha }={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\alpha }_{i}K\left(\cdot ,x_i\right)}$ 是与Mercer核有关的。在系数正则化算法中的假设空间取为：

$H_{K,x}=f_{\alpha }\left(x\right)={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\alpha }_i}K\left(x,x_i\right):\alpha =\left({\alpha }_1,{\alpha }_2,\cdot \cdot \cdot ,{\alpha }_m\right)\in R^m,m\in N$

注：假设空间依赖输入数据 $x=\left\{x_i:i=1,2,\cdots ,m\right\}$ 。系数正则化被Vapnik在文献 [5] 中为了设计线性规划支持向量机而首次引用。系数正则化是有一些优点的，我们可以见参考文献 [10] 。

本文中，我们考虑不定核而不再考虑Mercer核，所谓一般核 $K$ 是指 $K$ 只满足有界性和连续性，不再满足对称性或者半正定性。对于非正定核通常通过以下定义来处理。

定义1.3 $\tilde{K}\left(u,v\right)=E_{u}K\left(x,u\right)K\left(t,v\right)$ , (1.2)

即 $\tilde{K}$ 是一个Mercer核。

更多的关于不定核的学习，有：文献 [12] Qu和Sun学习了对于不定核核 $l^q$ 范数正则化学习算法的渐进性能，并且得到了满意的学习率；通过奇异值分解的方法，文献 [13] Q考虑不定核的情况下，得出了与容量无关的误差界。

在这篇文章里，记 $k={\sup }_{x,t\in X}\left|K\left(x,t\right)\right|<\infty$ ，我们学习 $l^2$ 系数正则化算法：

$f_{Z,\lambda }=f_{{\alpha }_Z}$ 其中 ${\alpha }_Z=\arg \underset{\alpha \in R^m}{\min }\left\{\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\left(f_{\alpha }\left(x_i\right)-y_i\right)}^2}+\lambda m{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\alpha }_i^2}\right\},\lambda >0$ (1.3)

这里 $f_{\alpha }={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\alpha }_i}\tilde{K}\left(\cdot ,x_i\right)$ 。由(1.2)，有 $k^2={\sup }_{u,v}\left|K\left(u,v\right)\right|$ 。

本文我们研究non-iid抽样下的系数正则化学习算法的性能。考虑基于 $Z$ 上的概率分布序列 $\left\{{\rho }^i\right\}$ ，因此对于任意的 $i\ge 1$ ， ${\rho }^i$ 在 $x$ 处的条件分布为 $\rho \left(\cdot |x\right)$ 。第 $i$ 个样本 $z_i=\left(x_i,y_i\right)$ 的选取依赖于 ${\rho }^{\left(i\right)}$ 。我们假设样本序列 $z_i=\left(x_i,y_i\right),i\ge 1$ 来自于强平稳过程并且样本的相关性满足强混合条件。

关于强混合条件的定义：

定义1.4对于两个 $\sigma$ 域 $\Gamma$ 和 $D$ ，定义a-数为 $\alpha \left(\Gamma ,D\right)=\underset{A\in \Gamma ,B\in D}{\sup }\left|P\left(A\cap B\right)-P\left(A\right)P\left(B\right)\right|$ 。给定一系列样

本 ${\left\{z_i\right\}}_{i=1}^m$ ，定义 $M_a^b$ 为由随机变量 $z_a,z_{a+1},\cdots ,z_b$ 生成的 $\sigma$ 域。当 $i\to 0$ 时， ${\alpha }_i=\underset{k\ge 1}{\sup }\alpha \left(M_1^k,M_{k+i}^{\infty }\right)\to 0$ ，称随机过程 $z_i,i\ge 1$ 满足强混合条件(或 $\alpha$ 混合条件)。

对于正则化学习算法的误差分析，已经有很多研究工作，其中绝大多数假设输出数据是一致有界的，即存在某一常数 $M>0$ ，使得几乎处处有 $\left|y\right|\le M$ ，也即条件分布 $\rho \left(\cdot |x\right)$ 的支撑集几乎处处包含在 $\left[-M,M\right]$ 中，见文献 [3] [4] [6] [10] 。文献 [14] [15] 在输出数据满足以下矩假设条件下得出算法(1.3)的误差界：

定义1.5 (矩有界假设)存在常数 $\hat{M}>0$ 及 $C_1>0$ 使得

${\displaystyle {\int }_Y{\left|y\right|}^l\text{d}\rho \left(y/x\right)}\le C_{1}l!{\hat{M}}_l,\forall l\in N,x\in X$ (1.4)

文献 [1] 和 [2] ，在以下弱化的矩有界假设下分别研究了回归学习算法(1.1)和(1.3)。

本文给出的有关输出数据的假设：

定义1.6 (弱化的矩有界假设)存在两个常数 $M>0$ 及 $p\ge 2$ 使得

${\displaystyle \underset{Z}{\int }{\left|y\right|}^p\text{d}\rho }\le M$ (1.5)

注：矩假设(1.4)要求输出数据 $y$ 的所有矩皆有界，而本文对矩假设进一步弱化，只要求 $y$ 的某个 $p\left(p\ge 2\right)$ 阶矩有界。

本文研究对输出变量满足弱化的矩有界条件(1.5)下基于非正定核的惩罚项为l²-范数的系数正则化算法的误差分析。下一节，我们将给出一些假设条件和本文主要结论。

2. 假设与结论

设 $X$ 是紧的距离空间， $\tilde{K}$ 是Mercer核， ${\rho }_X$ 为定义在 $X$ 上非退化的Borel测度，对任意的 $f\in L_v^2\left(t\right)$ ，定义积分算子为：

$L_{\tilde{K},\upsilon }f\left(x\right)={\displaystyle {\int }_X\tilde{K}\left(x,t\right)f\left(t\right)\text{d}{\rho }_X\left(t\right)},x\in X$ (2.1)

假设1 (Non-iid Sampling Condition)：存在一些正整数 $N_0$ ，在 $X$ 上有两个正的有界的Borel测度，使得

$\tilde{\mu }\le \mu \le \hat{\mu },\forall m\ge N_0$ . (2.2)

其中 $\mu \equiv \frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\rho }_X^{\left(i\right)}}$ 。

假设2 (Approximation Condition)：存在 $a_0>0,0<\beta \le 1$ ，使得

$D\left(\lambda \right)=\underset{f\in H_{\tilde{K}}}{\min }\left\{{\Vert f-f_{\rho }\Vert }_{L_{\hat{\mu }}^2}^2+\lambda {\Vert f\Vert }_{\tilde{K}}^2\right\}\le a_0^2{\lambda }^{\beta },\forall \lambda >0$ (2.3)

通过求导运算，有

$D\left(\lambda \right)=\lambda {\Vert {\left(\lambda I+L_{\tilde{K},\hat{\mu }}\right)}^{-\frac{1}{2}}{f}_{\rho }\Vert }_{L_{\tilde{K},\hat{\mu }}^2}^2$ (2.4)

即， $f_{\rho }\in Range\left(L_{K,\hat{\mu }}^{\frac{\beta }{2}}\right)$ [16] 。

定理2.1假设Non-iid Sampling Condition (2.2)和Approximation Condition (2.3)成立，样本序列 $z_i=\left(x_i,y_i\right),1\le i\le m$ 满足强混合条件，并且 $0<\lambda \le 1$ 。则对任何 $0<\eta <1$ ， $1-\eta$ 的概率下有

$\begin{array}{c}{\Vert f_{Z,\lambda }-f_{\rho }\Vert }_{{\rho }_X}\le \frac{2a_0{\lambda }^{\beta /4}}{\eta }+\frac{C}{\eta }{m}^{-1/2}{\lambda }^{-1/4}\left[1+m^{-1/4}{\lambda }^{-1/4}{\left(1+{\displaystyle \underset{l=1}{\overset{m}{\sum }}{\alpha }_l}\right)}^{1/4}\right]\\ \times \left[1+{\lambda }^{\left(\beta -1\right)\left(p-2\right)/4p}{\left({\displaystyle \underset{l=1}{\overset{m}{\sum }}{\alpha }_l^{\left(p-2\right)/2}}\right)}^{1/2}+{\lambda }^{\left(\beta -1\right)/4}{\left(1+{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\alpha }_i}\right)}^{1/2}\right]\end{array}$

成立。

其中 $C$ 是与 $k,M,p,a_0$ 有关的常数。

基于定理2.1，通过选择合适的 $\lambda$ (与 $m$ 相关)可以得到算法(1.3)的收敛速率。即：

定理2.2在定理2.1的假设下，且对于一些 $a>0$ 和 $t>0$ ，满足 ${\alpha }_l\le a{l}^{-t},$ 则有

${\Vert f_{Z,\lambda }-f_{\rho }\Vert }_{L_{\tilde{\mu }}^2}\le \tilde{C}\left(m^{-\theta \left(\beta ,t\right)\min \left\{\frac{p-2}{p}t,1\right\}}{\left({\log }_m\right)}^{3/4}\right)$

这里 $\theta \left(\beta ,t\right)$ 定义为： $\theta \left(\beta ,t\right)=\{\begin{array}{l}\frac{p\beta }{4\left(\beta +p-1\right)},0<\beta <1,0<t<\frac{p}{p-2}\\ \frac{\beta }{4},0<\beta <1,t\ge \frac{p}{p-2}\\ \frac{1}{4},\beta =1\end{array}$

定理2.1，定理2.2的证明会在第4部分-误差分析给出。

下一节我们会给出一些基本引理。□

3. 基本引理

证明定理2.1还需要一些结论。首先我们用以下引理 [3] 来处理a-混合条件。定义向量值随机变量 $\xi$ 的

$u$ 阶矩为： ${\Vert \xi \Vert }_{\mu }={\left(E{\Vert \xi \Vert }_H^{\mu }\right)}^{1/\mu }\left(1<u<\infty \right)$ ， ${\Vert \xi \Vert }_{\infty }=\sup {\Vert \xi \Vert }_H$ .

引理3.1假设随机样本 $z_i=\left(x_i,y_i\right),i\ge 1$ 满足a-混合条件。设 $\xi ,\eta$ 为取值在可分Hilbert空间H中，分别关于 $\sigma$ 代数 $J$ 与 $D$ 可测的随机变量。对任意的 $1<p,q,t<\infty$ ，满足 $p^{-1}+q^{-1}+t^{-1}=1$ 或者 $p=q=\infty ,t=1$ ，则有

$\left|E\left(\xi ,\eta \right)-\left(E\xi ,E\eta \right)\right|<15{\alpha }^{\frac{1}{t}}\left(J,D\right){\Vert \xi \Vert }_p{\Vert \eta \Vert }_q$ (3.1)

讨论假设空间的逼近能力，需要以下函数

$g_{\mu ,\lambda }=\arg \underset{f\in H_{\tilde{K}}}{\min }\left\{{\Vert f-f_{\rho }\Vert }_{L_{\mu }^2}^2+\lambda {\Vert f\Vert }_{\tilde{K}}^2\right\}$ (3.2)

通过对(3.2)的求导运算，可以得到

$g_{\mu ,\lambda }=L_{\tilde{K},\mu }{\left(L_{\tilde{K},\mu }+\lambda I\right)}^{-1}{f}_{\rho }$ (3.3)

同样，也需要以下引理。

引理3.2对 $\forall f\in H_{\tilde{K}}$ ， $L_{\tilde{K},\mu }^{\frac{1}{2}}$ 为从 $L_{\mu }^2$ 到 $H_{\tilde{K}}$ 的等距同构映射，则有

${\Vert f\Vert }_{L_{\mu }^2}={\Vert L_{\tilde{K},\mu }^{{}^{\frac{1}{2}}}f\Vert }_{\tilde{K}}$ (3.4)

引理3.3在假设1 (Non-iid Sampling Condition) (2.2)和假设2 (Approximation Condition) (2.3)成立的条件下，则有

${\Vert {\left(\lambda I+L_{K,\mu }\right)}^{-\frac{1}{2}}{f}_{\rho }\Vert }_{L_{\mu }^2}\le a_0{\lambda }^{\left(\beta -1\right)/2}$ (3.5)

证： $\begin{array}{c}D\left(\lambda \right)\ge \underset{f\in H_{\tilde{K}}}{\min }\left\{{\Vert f-f_{\rho }\Vert }_{L_{\mu }^2}+\lambda {\Vert f\Vert }_{\tilde{K}}^2\right\}\\ ={\Vert g_{\mu ,\lambda }-f_{\rho }\Vert }_{L_{\mu }^2}^2+\lambda {\Vert g_{\mu ,\lambda }\Vert }_{\tilde{K}}^2\\ ={\Vert \lambda {\left(L_{\tilde{K},\mu }+\lambda I\right)}^{-1}{f}_{\rho }\Vert }_{L_{\mu }^2}^2+\lambda {\Vert L_{\tilde{K},\mu }^{\frac{1}{2}}{\left(L_{\tilde{K},\mu }+\lambda I\right)}^{-1}{f}_{\rho }\Vert }_{L_{\mu }^2}^2\\ =\lambda {\Vert {\left(\lambda I+L_{\tilde{K},\mu }\right)}^{-\frac{1}{2}}{f}_{\rho }\Vert }_{L_{\mu }^2}^2\end{array}$

在给出下一个引理之前，这里先给出一些概念：定义样本算子 $S_x:H_K\to R^m$ 为

$S_{x}f={\left\{f\left(x_i\right)\right\}}_{i=1}^m$ ，对任意的 $f\in H_{\tilde{K}}$ ,

其中 $x={\left\{x_i\right\}}_{i=1}^m\subseteq X$ 。

那么， $S_x$ 的共轭算子 $S_x^{\ast }:R^m\to H_{\tilde{K}}$ 为

$S_x^{\ast }c={\displaystyle \underset{i=1}{\overset{m}{\sum }}{c}_i}\tilde{K}\left(\cdot ,x_i\right)$

这里， $c=\left(c_1,\cdot \cdot \cdot ,c_m\right)\in R^m$ 。

在文献 [10] [13] 里已经证明有

$\begin{array}{l}{f}_{Z,\lambda }={\left(\lambda I+{\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)}^2\right)}^{-1}\frac{1}{m^2}{S}_x^{\ast }{S}_x{S}_x^{\ast }y\\ ={\left(\lambda I+{\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)}^2\right)}^{-1}\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)\frac{1}{m}{S}_x^{\ast }y\end{array}$ (3.6)

接下来给出Hilbert Schmidt [7] 的定义和性质：

令 $HS\left(H_{\tilde{K}}\right)$ 是 $H_{\tilde{K}}$ 上所有的Hilbert Schmidt类，它构成了一个Hilbert空间，其内积为

${\langle T,S\rangle }_{HS}:={{\displaystyle \underset{i=1}{\overset{\infty }{\sum }}\langle T{\phi }_i,S{\phi }_i\rangle }}_{\tilde{K}}$

其中 ${\left\{{\phi }_i\right\}}_{i=1}^{+\infty }$ 是 $H_K$ 的一组正交基并且这个定义不依赖于基的选择。

我们需要Hilbert Schmidt算子的下列性质。

1) 对 $\forall h\in H_{\tilde{K}}$ ，定义一秩算子 $h\otimes h\left(f\right)={\langle h,f\rangle }_{\tilde{K}}$ ，并且它是一个Hilbert Schmidt算子满足 ${\Vert h\otimes h\Vert }_{HS}={\Vert h\Vert }_{\tilde{K}}^2$ 。记

$E\frac{1}{m}{S}_x^{\ast }{S}_x=E\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\tilde{K}}_{x_i}\otimes {\tilde{K}}_{x_i}}=\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{L}_{\tilde{K},{\rho }_X^{\left(i\right)}}}=L_{\tilde{K},\mu }$ (3.7)

2) 对任意Hilbert Schmidt算子 $T$ ，有 $\Vert T\Vert \le {\Vert T\Vert }_{HS}$ 。

接下来的引理给出了经验积分算子的收敛性：

引理3.4假设随机变量序列 $z_i=\left(x_i,y_i\right),1\le i\le m$ 满足强混合条件，则下列不等式成立

$\Vert \frac{1}{m}{S}_x^{\ast }{S}_x-L_{\tilde{K},\mu }\Vert \le \frac{k^2}{\sqrt{m}}{\left(1+30{\displaystyle \underset{l=1}{\overset{m-1}{\sum }}{\alpha }_l}\right)}^{\frac{1}{2}}$ (3.8)

证：由(3.7)式和 $L_{\tilde{K},\mu }$ 是一Hilbert Schmidt算子，有

$\begin{array}{c}E{\Vert \frac{1}{m}{S}_x^{\ast }{S}_x-L_{\tilde{K},\mu }\Vert }^2\le E{\Vert \frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}\tilde{K}\left(\cdot ,x_i\right)\otimes \tilde{K}\left(\cdot ,x_i\right)-L_{\tilde{K},\mu }}\Vert }_{HS}^2\\ =E{\Vert \frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\tilde{K}}_{x_i}\otimes {\tilde{K}}_{x_i}}\Vert }_{HS}^2-{\Vert L_{\tilde{K},\mu }\Vert }_{HS}^2\\ =E\frac{1}{m^2}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}\Vert {\tilde{K}}_{x_i}\otimes {\tilde{K}}_{x_i}\Vert }}_{HS}^2+\frac{1}{m^2}{{\displaystyle \underset{i\ne j}{\sum }E\langle {\tilde{K}}_{x_i}\otimes {\tilde{K}}_{x_i},{\tilde{K}}_{x_j}\otimes {\tilde{K}}_{x_j}\rangle }}_{HS}-{\Vert L_{\tilde{K},\mu }\Vert }_{HS}^2\end{array}$

记 ${\Vert {\tilde{K}}_{x_i}\otimes {\tilde{K}}_{x_i}\Vert }_{HS}^2\le k^4$ [11] ，由引理3.1，当 $p=q=\infty$ 且 $t=1$ 时有，当 $i\ne j$ ，

$\begin{array}{c}E{\langle {\tilde{K}}_{x_i}\otimes {\tilde{K}}_{x_i},{\tilde{K}}_{x_j}\otimes {\tilde{K}}_{x_j}\rangle }_{HS}\le {\langle E{\tilde{K}}_{x_i}\otimes {\tilde{K}}_{x_i},E{\tilde{K}}_{x_j}\otimes {\tilde{K}}_{x_j}\rangle }_{HS}+15{\alpha }_{\left|i-j\right|}{\Vert {\tilde{K}}_{x_i}\otimes {\tilde{K}}_{x_i}\Vert }_{\infty }{\Vert {\tilde{K}}_{x_j}\otimes {\tilde{K}}_{x_j}\Vert }_{\infty }\\ \le {\Vert L_{\tilde{K},\mu }\Vert }_{HS}^2+15k^4{\alpha }_{\left|i-j\right|}\end{array}$

然后有

$\begin{array}{c}E{\Vert \frac{1}{m}{S}_x^{\ast }{S}_x-L_{\tilde{K},\mu }\Vert }^2\le \frac{k^4}{m}+\frac{m^2-m}{m^2}{\Vert L_{\tilde{K},\mu }\Vert }_{HS}^2+\frac{30k^4}{m}{\displaystyle \underset{l=1}{\overset{m-1}{\sum }}{\alpha }_l}{\Vert L_{\tilde{K},\mu }\Vert }_{HS}^2\\ \le \frac{k^4}{m}\left(1+30{\displaystyle \underset{l=1}{\overset{m-1}{\sum }}{\alpha }_l}\right)\end{array}$

4. 误差分析

为了分析算法误差，像文献 [2] 中一样，这里需要引进一个正则化函数 $f_{\mu ,\lambda }$ ：

$f_{\mu ,\lambda }=L_{\tilde{K},\mu }^2{\left(\lambda I+L_{\tilde{K},\mu }^2\right)}^{-1}{f}_{\rho },0<\lambda <1$ (4.1)

所以我们可以把误差 $f_{Z,\lambda }-f_{\rho }$ 分解成两部分：

$f_{Z,\lambda }-f_{\rho }=\left\{f_{Z,\lambda }-f_{\mu ,\lambda }\right\}+\left\{f_{\mu ,\lambda }-f_{\rho }\right\}$ (4.2)

这里右边第一部分叫做样本误差，第二部分叫做正则误差。

4.1. 正则误差分析

在这一小分节中，我们分析正则化误差 ${\Vert f_{\mu ,\lambda }-f_{\rho }\Vert }_{L_{\mu }^2}$ 的界。

命题4.1在假设1 (Non-iid Sampling Condition) (2.2)和假设2 (Approximation Condition) (2.3)成立的条件下，当 $0<\lambda \le 1$ 时，下列正则化误差的界成立：

${\Vert f_{\mu ,\lambda }-f_{\rho }\Vert }_{L_{\mu }^2}\le 2a_0{\lambda }^{\beta /4}$ (4.3)

证：由引理3.2，引理3.3和下列积分算子不等式

$\Vert {\left(\lambda +L_{\tilde{K},\mu }^2\right)}^{-\frac{1}{4}}{\left(\sqrt{\lambda }+L_{\tilde{K},\mu }\right)}^{\frac{1}{2}}\Vert \le 2$

则有

${\Vert f_{\mu ,\lambda }-f_{\rho }\Vert }_{L_{\mu }^2}={\Vert \lambda {\left(\lambda I+L_{\tilde{K},\mu }^2\right)}^{-1}{\left(\sqrt{\lambda }+L_{\tilde{K},\mu }\right)}^{\frac{1}{2}}{\left(\sqrt{\lambda }+L_{\tilde{K},\mu }\right)}^{-\frac{1}{2}}{f}_{\rho }\Vert }_{L_{\mu }^2}\le 2a_0{\lambda }^{\beta /4}$

相似地，有

${\Vert f_{\mu ,\lambda }\Vert }_{\tilde{K}}={\Vert L_{\tilde{K},\mu }^{\frac{3}{2}}{\left(\lambda I+L_{\tilde{K},\mu }^2\right)}^{-1}{\left(\sqrt{\lambda }+L_{\tilde{K},\mu }\right)}^{\frac{1}{2}}{\left(\sqrt{\lambda }+L_{\tilde{K},\mu }\right)}^{-\frac{1}{2}}{f}_{\rho }\Vert }_{L_{\mu }^2}\le 2a_0{\lambda }^{\left(\beta -1\right)/4}$ (4.4)

4.2. 样本误差分析

在这一个小分节中，我们分析样本误差 ${\Vert f_{Z,\lambda }-f_{\mu ,\lambda }\Vert }_{L_{\mu }^2}$ 的界。

与文献 [10] 同样的方法，记 $\lambda f_{\mu ,\lambda }=L_{\tilde{K},\mu }^2\left(f_{\rho }-f_{\mu ,\lambda }\right)$ ，有

$\begin{array}{c}{f}_{Z,\lambda }-f_{\mu ,\lambda }={\left[\lambda I+{\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)}^2\right]}^{-1}\left\{\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)\frac{1}{m}{S}_x^{\ast }y-\left[{\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)}^2+\lambda I\right]f_{\mu ,\lambda }\right\}\\ ={\left[\lambda I+{\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)}^2\right]}^{-1}\left\{\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}\left(y_i-f_{\mu ,\lambda }\left(x_i\right)\right){\tilde{K}}_{x_i}}-L_{\tilde{K},\mu }^2\left(f_{\rho }-f_{\mu ,\lambda }\right)\right\}\\ ={\left[\lambda I+{\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)}^2\right]}^{-1}\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)U+{\left[\lambda I+{\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)}^2\right]}^{-1}VW\end{array}$ (4.5)

其中

$\begin{array}{l}U=\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}\left(y_i-f_{\mu ,\lambda }\left(x_i\right)\right){\tilde{K}}_{x_i}}-L_{\tilde{K},\mu }\left(f_{\rho }-f_{\mu ,\lambda }\right)\\ V=\frac{1}{m}{S}_x^{\ast }{S}_x-L_{\tilde{K},\mu }\\ W=L_{\tilde{K},\mu }\left(f_{\rho }-f_{\mu ,\lambda }\right)\end{array}$ (4.6)

记 $f_{Z,\lambda }$ 和 $f_{\mu ,\lambda }$ 都在 $H_{\tilde{K}}$ 中。由引理3.2，有

$\begin{array}{c}{\Vert f_{Z,\lambda }-f_{\mu ,\lambda }\Vert }_{L_{\mu }^2}={\Vert L_{\tilde{K},\mu }^{\frac{1}{2}}\left(f_{Z,\lambda }-f_{\mu ,\lambda }\right)\Vert }_{\tilde{K}}\\ \le {\Vert L_{\tilde{K},\mu }^{\frac{1}{2}}{\left[\lambda I+{\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)}^2\right]}^{-1}\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)U\Vert }_{\tilde{K}}+{\Vert L_{\tilde{K},\mu }^{\frac{1}{2}}{\left[\lambda I+{\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)}^2\right]}^{-1}VW\Vert }_{\tilde{K}}\\ =I_1+I_2\end{array}$ (4.7)

接下来分别分析 $I_1$ 和 $I_2$ 。

由算子单调不等式( [17] ，定理2.1)，有

$\Vert L_{\tilde{K},\mu }^{\frac{1}{2}}-{\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)}^{\frac{1}{2}}\Vert \le {\Vert L_{\tilde{K},\mu }-\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)\Vert }^{\frac{1}{2}}$ (4.8)

于是，可以得到

$\begin{array}{c}{I}_1\le {\Vert L_{\tilde{K},\mu }-\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)\Vert }^{\frac{1}{2}}\Vert {\left[\lambda I+{\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)}^2\right]}^{-1}\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)\Vert {\Vert U\Vert }_{\tilde{K}}+\Vert {\left[\lambda I+{\left(\frac{1}{m}{S}_X^{\ast }{S}_X\right)}^2\right]}^{-1}\Vert {\Vert U\Vert }_{\tilde{K}}\\ \le \left({\lambda }^{-\frac{1}{2}}{\Vert V\Vert }^{\frac{1}{2}}+{\lambda }^{-\frac{1}{4}}\right){\Vert U\Vert }_{\tilde{K}}\end{array}$ (4.9)

类似地得到 $I_2$ 的界

$\begin{array}{c}{I}_2\le {\Vert L_{\tilde{K},\mu }-\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)\Vert }^{\frac{1}{2}}\Vert {\left[\lambda I+{\left(\frac{1}{m}{S}_x^{\ast }{S}_x\right)}^2\right]}^{-1}\Vert \Vert V\Vert {\Vert W\Vert }_{\tilde{K}}+\Vert {\left[\lambda I+{\left(\frac{1}{m}{S}_X^{\ast }{S}_X\right)}^2\right]}^{-1}{\left(\frac{1}{m}{S}_X^{\ast }{S}_X\right)}^{\frac{1}{2}}\Vert \Vert V\Vert {\Vert W\Vert }_{\tilde{K}}\\ \le \left({\lambda }^{-1}{\Vert V\Vert }^{\frac{1}{2}}+{\lambda }^{-\frac{3}{4}}\right)\Vert V\Vert {\Vert W\Vert }_{\tilde{K}}\end{array}$ (4.10)

下面我们会依次给出 $\Vert V\Vert ,{\Vert W\Vert }_{\tilde{K}},{\Vert U\Vert }_{\tilde{K}}$ 的估计。引理3.4已经给出了 $\Vert V\Vert$ 的估计。接下来考虑 ${\Vert W\Vert }_{\tilde{K}}$ 类似命题4.1，得到以下引理：

引理4.1在假设1 (Non-iid Sampling Condition)和假设2 (Approximation Condition)成立的条件下，当 $0<\lambda \le 1$ 时，有以下不等式成立

${\Vert W\Vert }_{\tilde{K}}\le 2a_0{\lambda }^{\left(\beta +1\right)/4}$ (4.11)

最后分析 ${\Vert U\Vert }_K$ ，需要有下列引理：

引理4.2在假设1 (Non-iid Sampling Condition) (2.2)和假设2 (Approximation Condition) (2.3)成立的条件下，有

${\left(E{\Vert U\Vert }_{\tilde{K}}^2\right)}^{\frac{1}{2}}\le {\left(\frac{C_3}{m}\right)}^{\frac{1}{2}}\left\{1+{\lambda }^{\left(\beta -1\right)\left(p-1\right)/4p}{\left({\displaystyle \underset{i=1}{\overset{m-1}{\sum }}{\alpha }_l^{\left(p-2\right)/p}}\right)}^{\frac{1}{2}}\right\}$ (4.12)

证：定义在 $H_{\tilde{K}}$ 上的向量值随机变量 $\xi \left(z\right)=\left(y-f_{\mu ,\lambda }\left(x\right)\right)\tilde{K}\left(\cdot ,x\right)$ 。因此，

$U=\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}\xi \left(z_i\right)}-L_{\tilde{K},\mu }\left(f_{\rho }-f_{\mu ,\lambda }\right),E\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}\xi \left(z_i\right)}=L_{\tilde{K},\mu }\left(f_{\rho }-f_{\mu ,\lambda }\right)$

所以，

$\begin{array}{c}E{\Vert U\Vert }_{\tilde{K}}^2=E{\Vert \frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}\xi \left(z_i\right)}-E\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}\xi \left(z_i\right)}\Vert }_{\tilde{K}}^2\\ =E{\Vert \frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}\xi \left(z_i\right)}\Vert }_{\tilde{K}}^2-{\Vert L_{K,\mu }\left(f_{\rho }-f_{\mu ,\lambda }\right)\Vert }_{\tilde{K}}^2\end{array}$ (4.13)

由引理3.1，当 $p>2$ 时，令 $u=v=p$ ， $t=\frac{p}{p-2}$ ，当 $j<i$ ，有

$\begin{array}{c}E{\langle \xi \left(z_i\right),\xi \left(z_j\right)\rangle }_{\tilde{K}}\le {\langle E\xi \left(z_i\right),E\xi \left(z_j\right)\rangle }_{\tilde{K}}+15{\alpha }^{\left(P-2\right)/P}\left(M_1^j,M_i^{\infty }\right){\Vert \xi \left(z_i\right)\Vert }_p\\ ={\Vert L_{\tilde{K},\mu }\left(f_{\rho }-f_{\mu ,\lambda }\right)\Vert }_{\tilde{K}}^2+15{\left({\alpha }_{i-j}\right)}^{\left(p-2\right)/p}{\Vert \xi \Vert }_p^2\end{array}$ (4.14)

所以有

$\begin{array}{c}E{\Vert \frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}\xi \left(z_i\right)}\Vert }_{\tilde{K}}^2=\frac{1}{m^2}{\displaystyle \underset{i=1}{\overset{m}{\sum }}E{\left(y_i-f_{\mu ,\lambda }\left(x_i\right)\right)}^2\tilde{K}\left(x_i,x_i\right)}+\frac{1}{m^2}{\displaystyle \underset{i\ne j}{\sum }E{\langle \xi \left(z_i\right),\xi \left(z_j\right)\rangle }_{\tilde{K}}}\\ \le \frac{k^2}{m^2}{\displaystyle \underset{i=1}{\overset{m}{\sum }}E{\left(y_i-f_{\mu ,\lambda }\left(x_i\right)\right)}^2}+\frac{m^2-m}{m^2}{\Vert L_{\tilde{K},\mu }\left(f_{\rho }-f_{\mu ,\lambda }\right)\Vert }_{\tilde{K}}^2+\frac{30}{m}{\displaystyle \underset{l=1}{\overset{m-1}{\sum }}{\alpha }_l^{\left(p-2\right)/p}}{\Vert \xi \Vert }_p^2\end{array}$ (4.15)

故有 $E{\Vert \frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}\xi \left(z_i\right)-E\xi }\Vert }_{\tilde{K}}^2\le \frac{k^2}{m^2}{\displaystyle \underset{i=1}{\overset{m}{\sum }}E{\left(y_i-f_{\mu ,\lambda }\left(x_i\right)\right)}^2}+\frac{30}{m}{\displaystyle \underset{l=1}{\overset{m-1}{\sum }}{\alpha }_l^{\left(p-2\right)/p}}{\Vert \xi \Vert }_p^2$ (4.16)

接下来分别估计 $\frac{k^2}{m^2}{\displaystyle \underset{i=1}{\overset{m}{\sum }}E{\left(y_i-f_{\mu ,\lambda }\left(x_i\right)\right)}^2}$ 和 ${\Vert \xi \Vert }_p$ 。对于 $\frac{k^2}{m^2}{\displaystyle \underset{i=1}{\overset{m}{\sum }}E{\left(y_i-f_{\mu ,\lambda }\left(x_i\right)\right)}^2}$ ，有

$\begin{array}{c}\frac{k^2}{m^2}{\displaystyle \underset{i=1}{\overset{m}{\sum }}E{\left(y_i-f_{\mu ,\lambda }\left(x_i\right)\right)}^2}\le \frac{k^2}{m^2}{\displaystyle \underset{i=1}{\overset{m}{\sum }}E{\left(y_i-f_{\rho }\right)}^2}+\frac{k^2}{m^2}{\displaystyle \underset{i=1}{\overset{m}{\sum }}E{\left(f_{\rho }-f_{\mu ,\lambda }\left(x_i\right)\right)}^2}\\ =\frac{k^2}{m}\left(E{|y^2-E\left|f_{\rho }\right|}^2\right)+\frac{k^2}{m}{\Vert f_{\rho }-f_{\mu ,\lambda }\Vert }_{L_{\mu }^2}^2\end{array}$ (4.17)

由Hölder不等式，得到

${\displaystyle \underset{Z}{\int }{y}^2\text{d}\rho }\le {\left({\displaystyle \underset{Z}{\int }{\left|y\right|}^p\text{d}\rho }\right)}^{2/p}\le M^{2/p}$ (4.18)

则

${\Vert f_{\rho }\Vert }_{{\rho }_X}\le {\displaystyle \underset{X}{\int }{\left({\displaystyle \underset{Y}{\int }y\text{d}\left(y/x\right)}\right)}^2}\text{d}{\rho }_X\le {\displaystyle \underset{Z}{\int }{y}^2}\text{d}\rho \le M^{2/p}$ (4.19)

因此

$E{y}^2-{\Vert f_{\rho }\Vert }_{{\rho }_X}^2<M^{2/p}$ (4.20)

将(4.3)和(4.20)代入(4.17)，得到

$\frac{k^2}{m^2}{\displaystyle \underset{i=1}{\overset{m}{\sum }}E{\left(y_i-f_{\mu ,\lambda }\left(x_i\right)\right)}^2}\le \frac{k^2}{m}\left(M^{2/p}+4a_0^2{\lambda }^{\beta /2}\right)$ (4.21)

接下来评估 ${\Vert \xi \Vert }_p^2$ ，

$\begin{array}{c}{\Vert \xi \Vert }_p^2={\left[E{\left({\left(y-f_{\mu ,\lambda }\right)}^2\tilde{K}\left(x,x\right)\right)}^{p/2}\right]}^{2/p}\\ \le k^2{\left(E{\left|y-f_{\mu ,\lambda }\left(x\right)\right|}^p\right)}^{2/p}\\ \le k^2{\left[{\left(E{\left|y\right|}^p\right)}^{1/p}+{\left(E{\left|f_{\mu ,\lambda }\left(x\right)\right|}^p\right)}^{1/p}\right]}^2\\ \le 2k^2\left[{\left(E{\left|y\right|}^p\right)}^{2/p}+{\left(E{\left|f_{\mu ,\lambda }\right|}^p\right)}^{2/p}\right]\end{array}$ (4.22)

现在，我们需要给出 ${\left(E{\left|f_{\mu ,\lambda }\left(x\right)\right|}^p\right)}^{2/p}$ 的上界。

由(4.4)，有

$\left|f_{\mu ,\lambda }\left(x\right)\right|\le k{\Vert f_{\mu ,\lambda }\Vert }_{\tilde{K}}\le 2k{a}_0{\lambda }^{\left(\beta -1\right)/4}$ (4.23)

由 $f_{\mu ,\lambda }$ 的定义，有

${\Vert f_{\mu ,\lambda }\Vert }_{{\rho }_X}^2\le {\Vert f_{\rho }\Vert }_{{\rho }_X}^2\le E{y}^2\le M^{2/p}$ (4.24)

所以

$\begin{array}{c}{\left(E{\left|f_{\mu ,\lambda }\left(x\right)\right|}^p\right)}^{2/p}=E{\left({\left|f_{\mu ,\lambda }\left(x\right)\right|}^2{\left|f_{\mu ,\lambda }\right|}^{p-2}\right)}^{2/p}\\ \le {\left({\Vert f_{\mu ,\lambda }\Vert }_{{\rho }_X}^2\right)}^{2/p}{\left({\left|f_{\mu ,\lambda }\left(x\right)\right|}^{p-2}\right)}^{2/p}\\ \le {\left(M^{2/p}\right)}^{2/p}{\left({\left(2k{a}_0{\lambda }^{\left(\beta -1\right)/4}\right)}^{p-2}\right)}^{2/p}\\ =4^{\left(p-2\right)/p}{M}^{4/p^2}{k}^{2\left(p-2\right)/p}{a}_0^{2\left(p-2\right)/p}{\lambda }^{\left(\beta -1\right)\left(p-2\right)/2p}\end{array}$ (4.25)