#### 期刊菜单

Analysis of Coefficient Regularized Regression with Non-Identically and Independently Sampling

Abstract: This paper considers the error analysis of coefficient regularization with non-identically and independently sampling. The framework under investigation is different from classical kernel learning. The kernel function no longer satisfies the positive semidefiniteness; we carry out the error analysis with output sample values satisfying a generalized moment hypothesis. Satisfactory capacity independently error bounds are derived by the techniques of integral operator for this learning algorithm, finally, a satisfactory learning rate is obtained by selecting appropriate regularization parameters.

1. 引言

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

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

$\rho \left(y|x\right)$$\rho$$X=x$ 时的条件分布，回归函数刻画了输出值y与输入值x之间的依赖关系。实际上，由于 $\rho$ 是未知的，所以 ${f}_{\rho }$ 无法直接求得，于是我们的目标是利用样本z产生关于 ${f}_{\rho }$ 的一个最佳逼近。

${f}_{Z,\lambda }={f}_{{\alpha }_{Z}}$ 其中 ${\alpha }_{Z}=\mathrm{arg}\underset{\alpha \in {R}^{T}}{\mathrm{min}}\left\{\frac{1}{T}\underset{t=1}{\overset{T}{\sum }}{\left({f}_{\alpha }\left({x}_{t}\right)-{y}_{t}\right)}^{2}+\lambda T\underset{t=1}{\overset{T}{\sum }}{\alpha }_{t}^{2}\right\},\lambda >0$ (1.1)

2. 相关定义

Holder空间 ${C}^{s}\left(X\right)\text{\hspace{0.17em}}\left(0\le s\le 1\right)$ 包含X上所有的连续函数，并且具有以下的有界范数：

${‖f‖}_{{C}^{s}\left(x\right)}={‖f‖}_{\infty }+{|f|}_{{C}^{s}\left( x \right)}$

${|f|}_{{C}^{s}\left(x\right)}:=\underset{x\ne y\in X}{\mathrm{sup}}\frac{|f\left(x\right)-f\left(y\right)|}{{\left(d\left(x,y\right)\right)}^{s}}.$

${‖{\rho }_{X}^{\left(t\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}\le {C}_{1}{\alpha }^{t},\forall t\in N$ (2.1)

$|{\int }_{X}f\left(x\right)\text{d}{\rho }_{X}^{\left(i\right)}-{\int }_{X}f\left(x\right)\text{d}{\rho }_{X}|\le {C}_{1}{\alpha }^{i}{‖f‖}_{{C}^{s}\left(x\right)},\forall f\in {C}^{s}\left(X\right),i\in N.$

${L}_{K,{\rho }_{X}}f\left(x\right)={\int }_{X}K\left(x,u\right)f\left(u\right)\text{d}{\rho }_{X}\left(u\right),{L}_{K,{\rho }_{X}^{t}}f\left(x\right)={\int }_{X}K\left(x,u\right)f\left(u\right)\text{d}{\rho }_{X}^{\left(t\right)}\left(u\right),$

${‖{\stackrel{˜}{K}}_{u}-{\stackrel{˜}{K}}_{v}‖}_{\stackrel{˜}{K}}\le {k}_{s}{\left(d\left(u,v\right)\right)}^{s}.$ (2.2)

$|f\left(u\right)-f\left(v\right)|=|{〈f,{\stackrel{˜}{K}}_{u}-{\stackrel{˜}{K}}_{v}〉}_{\stackrel{˜}{K}}|\le {‖f‖}_{\stackrel{˜}{K}}{‖{\stackrel{˜}{K}}_{u}-{\stackrel{˜}{K}}_{v}‖}_{\stackrel{˜}{K}}\le {k}_{s}{‖f‖}_{\stackrel{˜}{K}}{\left(d\left(u,v\right)\right)}^{s}$

${\int }_{Z}{|y|}^{p}\le {\stackrel{˜}{M}}^{2}$ (2.3)

${f}_{\lambda ,{\rho }_{X}}=\mathrm{arg}\underset{f\in {Η}_{\stackrel{˜}{K}}}{\mathrm{min}}\left\{{\int }_{Z}{\left(f\left(x\right)-{f}_{\rho }\left(x\right)\right)}^{2}\text{d}\rho \left(x,y\right)+\lambda {‖f‖}_{\stackrel{˜}{K}}^{2}\right\}.$ (2.4)

${f}_{\lambda ,{\stackrel{¯}{\rho }}_{X}^{\left(m\right)}}={\left(\lambda I+{L}_{\stackrel{˜}{K},{\stackrel{¯}{\rho }}_{X}^{\left(m\right)}}\right)}^{-1}{L}_{\stackrel{˜}{K},{\stackrel{¯}{\rho }}_{X}^{\left(m\right)}}{f}_{\rho }$ (2.5)

${‖{f}_{Z,\lambda }-{f}_{\rho }‖}_{\rho }={‖{f}_{Z,\lambda }-{f}_{\lambda ,{\stackrel{¯}{\rho }}_{X}^{\left(m\right)}}‖}_{\rho }+{‖{f}_{\lambda ,{\stackrel{¯}{\rho }}_{X}^{\left(m\right)}}-{f}_{\lambda ,{\rho }_{X}}‖}_{\rho }+{‖{f}_{\lambda ,{\rho }_{X}}-{f}_{\rho }‖}_{\rho }$

3. 主要定理及其证明

3.1. 主要定理

$E{‖{f}_{Z,\lambda }-{f}_{\rho }‖}_{\rho }\le {{C}^{″}}_{k}{T}^{-\mathrm{min}\left\{1/2-\left(3/2\right)\theta ,\left(r-1/2\right)\theta \right\}},$

3.2. 误差分析

${‖{f}_{\lambda ,{\rho }_{X}}-{f}_{\rho }‖}_{\rho }\le {C}_{q}{\lambda }^{q}$

${‖{f}_{\lambda ,{\rho }_{X}}-{f}_{\rho }‖}_{\stackrel{˜}{K}}\le {C}_{r}{\lambda }^{r-1/2},$

${‖fg‖}_{{C}^{s}\left(X\right)}\le {‖f‖}_{{C}^{s}\left(X\right)}×{‖g‖}_{\infty }+{‖f‖}_{\infty }×{|g|}_{{C}^{s}\left( X \right)}$

$‖{L}_{\stackrel{˜}{K},{\stackrel{¯}{\rho }}_{X}^{\left(I\right)}}-{L}_{\stackrel{˜}{K},{\rho }_{X}}‖\le k\left(k+2{k}_{s}\right){‖{\stackrel{¯}{\rho }}_{X}^{\left(I\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}$

$\begin{array}{l}{‖\left({L}_{\stackrel{˜}{K},{\stackrel{¯}{\rho }}_{X}^{\left(I\right)}}-{L}_{\stackrel{˜}{K},{\rho }_{X}}\right)h‖}_{\stackrel{˜}{K}}^{2}\\ ={\int }_{X}h\left(x\right)\left\{{\int }_{X}h\left(t\right)\stackrel{˜}{K}\left(x,t\right)\text{d}\left({\stackrel{¯}{\rho }}_{X}^{\left(I\right)}-{\rho }_{X}\right)\left(t\right)\right\}×\text{d}\left({\stackrel{¯}{\rho }}_{X}^{\left(I\right)}-{\rho }_{X}\right)\left(x\right)\\ \le {‖h\left(u\right){\int }_{X}h\left(v\right)\stackrel{˜}{K}\left(u,v\right)\text{d}\left({\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}\right)‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}×{‖{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}\\ \le \left\{{‖h‖}_{{C}^{s}\left(X\right)}×{‖{\int }_{X}h\left(v\right)\stackrel{˜}{K}\left(u,v\right)\text{d}\left({\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}\right)‖}_{\infty }\stackrel{\text{ }}{\text{ }}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\text{ }+{‖h‖}_{\infty }×{|{\int }_{X}h\left(v\right)\stackrel{˜}{K}\left(u,v\right)×\text{d}\left({\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}\right)|}_{{C}^{s}\left(X\right)}\right\}×{‖{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}\end{array}$ (3.1)

$I={‖{\int }_{X}h\left(v\right)\stackrel{˜}{K}\left(u,v\right)\text{d}\left({\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}\right)‖}_{\infty },$

$II={|{\int }_{X}h\left(v\right)\stackrel{˜}{K}\left(u,v\right)\text{d}\left({\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}\right)|}_{{C}^{s}\left( X \right)}$

$\begin{array}{c}I=\underset{x\in X}{\mathrm{max}}|{\int }_{X}h\left(v\right)\stackrel{˜}{K}\left(u,v\right)\text{d}\left({\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}\right)|\\ \le \underset{x\in X}{\mathrm{max}}{‖h\left(\cdot \right)\stackrel{˜}{K}\left(u,\cdot \right)‖}_{{C}^{s}\left(X\right)}×{‖{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}\\ \le \underset{x\in X}{\mathrm{max}}\left[{‖h‖}_{{C}^{s}\left(X\right)}×{k}^{2}+{‖h‖}_{\infty }×{|\stackrel{˜}{K}\left(u,\cdot \right)|}_{{C}^{s}\left(X\right)}\right]×{‖{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}\\ \le \left[{k}^{2}{‖h‖}_{{C}^{s}\left(X\right)}+k{k}_{s}{‖h‖}_{\infty }\right]×{‖{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}\end{array}$ (3.2)

$\begin{array}{l}|\underset{X}{\int }h\left(v\right)\left[\stackrel{˜}{K}\left({u}_{2},v\right)-\stackrel{˜}{K}\left({u}_{1},v\right)\right]\text{d}\left({\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}\right)|\\ \le {‖h\left(v\right)\left[\stackrel{˜}{K}\left({u}_{2},v\right)-\stackrel{˜}{K}\left({u}_{1},v\right)\right]‖}_{{C}^{s}\left(X\right)}×{‖{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}\\ \le \left[{‖h‖}_{{C}^{s}\left(X\right)}×{‖\stackrel{˜}{K}\left({u}_{2},v\right)-\stackrel{˜}{K}\left({u}_{1},v\right)‖}_{\infty }+{‖h‖}_{\infty }{|\stackrel{˜}{K}\left({u}_{2},v\right)-\stackrel{˜}{K}\left({u}_{1},v\right)|}_{{C}^{s}\left(X\right)}\right]×{‖{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}\end{array}$ (3.3)

$|\left[\stackrel{˜}{K}\left({u}_{2},{v}_{2}\right)-\stackrel{˜}{K}\left({u}_{1},{v}_{1}\right)\right]-\left[\stackrel{˜}{K}\left({u}_{2},{v}_{1}\right)-\stackrel{˜}{K}\left({u}_{1},{v}_{1}\right)\right]|\le {k}_{s}^{2}{d}^{s}\left({u}_{1},{u}_{2}\right){d}^{s}\left({v}_{1},{v}_{2}\right)$

${|\stackrel{˜}{K}\left({u}_{2},v\right)-\stackrel{˜}{K}\left({u}_{1},v\right)|}_{{C}^{s}\left(X\right)}\le {k}_{s}^{2}{d}^{s}\left({u}_{1},{u}_{2}\right),$

$|\stackrel{˜}{K}\left({u}_{2},v\right)-\stackrel{˜}{K}\left({u}_{1},v\right)|\le k\cdot {k}_{s}{d}^{s}\left({u}_{1},{u}_{2}\right)$ (3.4)

$\begin{array}{c}II={|{\int }_{X}h\left(v\right)\stackrel{˜}{K}\left(u,v\right)\text{d}\left({\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}\right)|}_{{C}^{s}\left(X\right)}\\ \le \left(k{k}_{s}{‖h‖}_{{C}^{s}\left(X\right)}+{k}_{s}^{2}{‖h‖}_{\infty }\right){‖{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}\end{array}$ (3.5)

$\begin{array}{l}{‖\left({L}_{\stackrel{˜}{K},{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}}-{L}_{\stackrel{˜}{K},{\rho }_{X}}\right)h‖}_{\stackrel{˜}{K}}^{2}\\ \le \left\{{‖h‖}_{{C}^{s}\left(X\right)}\left[{k}^{2}{‖h‖}_{{C}^{s}\left(X\right)}+k{k}_{s}{‖h‖}_{\infty }\right]+{‖h‖}_{\infty }\left[k{k}_{s}{‖h‖}_{{C}^{s}\left(X\right)}+{k}_{s}^{2}{‖h‖}_{\infty }\right]\right\}×{‖{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}^{2}\\ =\left(k{‖h‖}_{{C}^{s}\left(X\right)}+{k}_{s}{‖h‖}_{\infty }^{2}\right){‖{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}^{2}\end{array}$

${‖h‖}_{{C}^{s}\left(X\right)}\le \left(k+{k}_{s}\right){‖h‖}_{\stackrel{˜}{K}},\forall h\in {H}_{\stackrel{˜}{K}}$

${‖\left({L}_{\stackrel{˜}{K},{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}}-{L}_{\stackrel{˜}{K},{\rho }_{X}}\right)h‖}_{\stackrel{˜}{K}}\le k\left(k+2{k}_{s}\right){‖h‖}_{\stackrel{˜}{K}}{‖{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}$

${‖{f}_{\lambda ,{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}}-{f}_{\lambda ,{\rho }_{X}}‖}_{\stackrel{˜}{K}}\le \frac{{C}_{2}{\lambda }^{r-3/2}}{T}$ (3.6)

$\begin{array}{c}{‖{f}_{\lambda ,{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}}-{f}_{\lambda ,{\rho }_{X}}‖}_{\stackrel{˜}{K}}={‖{\left(\lambda I+{L}_{\stackrel{˜}{K},{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}}\right)}^{-1}\left\{\left({L}_{\stackrel{˜}{K},{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}}-{L}_{\stackrel{˜}{K},{\rho }_{X}}\right){f}_{\rho }+\left({L}_{\stackrel{˜}{K},{\rho }_{X}}-{L}_{\stackrel{˜}{K},{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}}\right){f}_{\lambda ,{\rho }_{X}}\right\}‖}_{\stackrel{˜}{K}}\\ ={‖{\left(\lambda I+{L}_{\stackrel{˜}{K},{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}}\right)}^{-1}\left({L}_{\stackrel{˜}{K},{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}}-{L}_{\stackrel{˜}{K},{\rho }_{X}}\right)\left({f}_{\rho }-{f}_{\lambda ,{\rho }_{X}}\right)‖}_{\stackrel{˜}{K}}\\ \le \frac{1}{\lambda }{‖\left({L}_{\stackrel{˜}{K},{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}}-{L}_{\stackrel{˜}{K},{\rho }_{X}}\right)\left({f}_{\rho }-{f}_{\lambda ,{\rho }_{X}}\right)‖}_{\stackrel{˜}{K}}\end{array}$

${‖{f}_{\lambda ,{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}}-{f}_{\lambda ,{\rho }_{X}}‖}_{\stackrel{˜}{K}}\le \frac{1}{\lambda }k\left(k+2{k}_{s}\right){‖{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}{‖{f}_{\lambda ,{\rho }_{X}}-{f}_{\rho }‖}_{\stackrel{˜}{K}}$

${‖{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}=\frac{1}{T}\underset{t=1}{\overset{T}{\sum }}{‖{\rho }_{X}^{\left(t\right)}-{\rho }_{X}‖}_{{\left({C}^{s}\left(X\right)\right)}^{\ast }}\le \frac{{C}_{1}\alpha }{T\left(1-\alpha \right)}$

$E{‖{f}_{Z,\lambda }-{f}_{\lambda ,{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}}‖}_{\rho }\le \frac{{{C}^{\prime }}_{k}}{{\lambda }^{3/2}{T}^{1/2}}$

$E{‖{f}_{Z,\lambda }-{f}_{\lambda ,{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}}‖}_{\rho }\le \frac{{{C}^{\prime }}_{k}}{{\lambda }^{3/2}{T}^{1/2}}$

$1/2，由命题3.2，有

${‖{f}_{\lambda ,{\stackrel{¯}{\rho }}_{X}^{\left(T\right)}}-{f}_{\lambda ,{\rho }_{X}}‖}_{\stackrel{˜}{K}}\le \frac{{C}_{2}{\lambda }^{r-3/2}}{T}$

${‖{f}_{\lambda ,{\rho }_{X}}-{f}_{\rho }‖}_{\stackrel{˜}{K}}\le {C}_{r}{\lambda }^{r-1/2},$

${‖f‖}_{\rho }\le {‖f‖}_{\infty }\le k{‖f‖}_{\stackrel{˜}{K}},\forall f\in {H}_{\stackrel{˜}{K}}$

 [1] 郭芹, 孙红卫. 基于弱相关抽样的系数正则化的一致性分析[J]. 济南大学学报(自然科学版), 2010, 24(1): 99-103. [2] Sun, H.W. and Wu, Q. (2011) Least Square Regression with Indefinite Kernels and Coefficient Regularization. Applied and Computational Harmonic Analysis, 30, 96-109. https://doi.org/10.1016/j.acha.2010.04.001 [3] Nie, W.L. and Wang, C. (2016) Error Analysis of ERM Algorithm with Unbounded and Non-Identical Sampling. Journal of Applied Mathematics and Physics, 4, 156-168. https://doi.org/10.4236/jamp.2016.41019 [4] Chu, X.R. and Sun, H.W. (2013) Regularized Least Square Regression with Unbounded and Dependent Sampling. Abstract and Applied Analysis, 2013, 900-914. [5] Chu, X.R. and Sun, H.W. (2012) Coefficient Regularization with Unbounded Sampling. Journal of Computational Information Systems, 8, 1613-1621. [6] Gao, Q. and Ye, P.X. (2016) Coefficient-Based Regularized Regression with Dependent and Unbounded Sampling. International Journal of Wavelets, Multiresolution and Information Processing, 14, No. 5. https://doi.org/10.1142/S0219691316500399 [7] Vapnik, V. (1979) Estimation of Dependent Based on Empirical Data. Nauka, Moscow. [8] Sun, H.W. and Guo, Q. (2011) Coefficient Regularized Regression with Non-IID Sampling. International Journal of Computer Mathematics, 88, 3113-3125. https://doi.org/10.1080/00207160.2011.587511 [9] Cai, J. (2013) Coefficient-Based Regression with Non-Identical Unbounded Sampling. Abstract and Applied Analysis, 2013, Article ID: 134727. https://doi.org/10.1155/2013/134727