Coefficient-based Regularized Algorithm for Estimating Gradient in High
Dimensional Space
Abstract
The21st century is a new era of big data.The Data contains more and more variables while it includes more and more redundant information.It’s increasingly hard to learn from these data for statistical learning and machine learning.Therefore,variable selection is necessary before we establish learning models.The gradient of multivariate function is the vector whose components are the partial derivatives for each variable.Each component’s norm corresponds to the extent of the function value’s change when the variable in its place changes.Gradient estimation plays an important role in the problems of variable selection.So this article’s target is learning gradient from the sample points.
We propose a coefficient-based regularized algorithm for estimating gradient in high di-mensional spaces.Compared with traditional gradient estimating methods,our algorithm does not need to partition the region of the variables so that it can be highly efficient in high dimen-sional space.We give the repres
enter theorem for the algorithm which make it easier to get the solution.Moreover,by the singular value decomposition approach,we study how to reduce the matrix size in the representer theorem.An error analysis is given for the covergence of the gra-dient estimated by the reduced matrix size algorithm to the original algorithm.At the end of this paper,two examples are used to verify the effectiveness of our algorithm.Thefirst experiment on man-made data set shows the validity of the algorithm.Then,in the second example,we analyze the numerical forecasting data of the city air quality and get the result which is accord with the actual situation.Both the examples show that our algorithm is effective and feasible.
Key Words:reproducing kernel Hilbert space;gradient estimation;coefficient-based regularization;variable selection
目  录
摘  要...............................................................................III 1绪论.. (1)
2预备知识 (3)
2.1再生核Hilbert空间 (3)
2.2Tikhonov正则化 (4)
2.3基于系数正则化方法 (4)
3梯度估计 (7)
3.1估计算法 (7)
3.2表示定理 (8)
4降低矩阵维数 (11)
4.1降维处理 (11)
4.2降维算法 (19)
5数值实验 (21)
5.1数值实验1 (21)
5.2数值实验2 (23)
结  论 (25)
参考文献 (27)
附录 (29)
.1程序代码 (29)
正则化几何因子
.2数值实验2参考数据 (32)
攻读硕士学位期间发表学术论文情况 (35)
致  谢 (37)
1绪论
大数据时代，生物科学和物理科学领域中出现了很多多变量或者多坐标的数据集需要处理，促使基于Tik
honov正则化和全局收敛的机器学习方法的广泛使用，譬如支持向量机（SVMs）[1,2,3,4]和正则化最小二乘分类算法[5,6].这些算法能够成功用于回归和分类问题.然后在一些应用中相继出现了诸如哪些变量与预测结果相关性最大和各个变量之间的变化有什么内在联系和相似性等统计上的线性模型中的分类问题.这就使得变量选择问题和坐标共变性问题的研究成为必要.在实际问题中存在许多影响预测结果的变量.变量选择中变量选择太少或选择得不恰当，都会使建立的模型预测结果与实际结果有较大的误差；而变量选得太多，求解模型计算量很大并且会出现过度拟合问题，因而如何做变量选择在这个大数据时代就尤为重要.特别地，在数据点维数很高但采样点很少(即“large p,small n”[7])的情况中，变量选择成为构建和解决统计模型的根本问题.核学习方法能够有效地用于回归和分类，我们在这个框架下研究变量选择和变量共变性.
本文中我们研究的主要问题是通过从函数的样本点学习函数的梯度来选择变量和研究变量间共变性.因为函数梯度可以给我们提供如下信息:(a)对于变量选择问题.梯度向量的每个分量是相应坐标位置的变量的偏导数，偏导数的范数大小代表了这个变量与函数值的相关性.若偏导数的范数很小，则说明这个位置的变量若发生变化函数值只会有很小的变化.(b)对于变量共变性问题.内积描述相似性，梯度的两个分量做内积，即函数关于某两个坐标位置的变量的偏导数做内积，内积的大小就表示了两个变量的相关性或者共变性.
一维空间中的函数梯度估计问题即数值导数问题.在很多学科的研究中都会出现从样本点重构数值导数的
问题，比如图像处理[8],V olterra积分方程[9,10]和识别问题[11].众所周知，数值导数问题是不适定的，这意味着采样数据很小的误差会导致逼近导数出现很大的误差[12,13,14].目前有很多关于求解数值导数的相关研究[13,15,16].其中一种方法是利用剖分[17]来计算数值导数.这种方法在低维空间中能够取得很好的效果，但是在高维空间中剖分是很困难的一件事.另外一种方法是使用Tikhonov正则化方法来处理数值导数问题[13,18,19].但是这些方法多是从样本点直接估计函数然后求导得到导数估计.这种做法会有一个问题存在，就是得到的函数估计在做估计的再生核Hilbert空间中，但是求导得到的导数估计可能不再在这个空间中了.这种情况直接导致我们没有一个范数或者可计算的度量可用于得到的导数估计.
从采样点估计高维空间中的函数梯度可以借鉴上述求数值导数的方法.但是鉴于上面提到的这些问题，已有的方法并不能有效的用于梯度估计问题.在本文中，我们借鉴Mukherjee等人在2006年提出的一种梯度估计算法[20]，得到我们的基于系数正则化的梯
基于系数正则化的高维空间梯度估计算法
度估计算法.该算法避免在高维空间中做剖分，并且直接对梯度做估计，这样可以直接用给定的假设再生核Hilbert空间中的内积作用到估计的梯度上.
在详细展开算法之前，我们首先在第二章介绍一些正则化相关的概念和方法.第三章给出本文的主要算法–基于系数正则化的梯度估计算法并给出算法的表示定理.借助于奇异值分解技术，我们在第四章讨论
了如何有效地降低表示定理中矩阵的规模.最后借助两个数值实验说明我们的算法可以有效用于变量选择和变量共变性研究.本文的附录部分附上了第四章算法的程序代码和数值实验2的实验数据.
2预备知识
学习问题是根据选取的经验数据研究某种依赖关系的问题.分类和回归是学习的两个基本问题.学习的观测点集(x1,y1),...,(x m,y m)称为训练点集.训练点集包括输入x和输出y.分类是指学习训练点集试图构造一个分类函数以预测输出y，得到最佳的预测结果.而回归则是学习训练点集构造一个输入x和输出y之间非常类似的函数关系.直白的说，学习过程就是通过学习训练点集从一个给定的函数空间中选择一个合适的函数的过程.在本章节中，我们介绍相关的函数空间概念和简单的学习算法的基础知识.
2.1再生核Hilbert空间
统计学习理论中引入了核函数用核方法来研究空间ℋ中的分类和回归.核方法是通过把非线性的原始数据映射到可以呈现线性关系的空间中进行线性分析，即通过某个映射Φ将非线性的原始训练点集{(x1,y1),...,(x m,y m)}映射到特征空间ℋ中，映射为{(Φ(x1),y1),...,(Φ(x m),y m)}后在特征空间中ℋ中可以使用内积作为相似性度量.我们由特征空间ℋ中的内积定义一个相似性度量K(x,x′):=⟨Φ(x),Φ(x′)⟩，其中K称为核函数.
实际计算中，我们可以选择某些具有特殊性质的核函数来简化求解过程.下面介绍一种特殊的核函数-Mercer核函数.
定义2.1[21]令X是度量空间，我们称K:X×X→R是对称的若K(x,t)=K(t,x)对所有的x,t∈X成立.称K是半正定的若对所有的有限点集x={x1,...,x m}⊂X,m×m矩阵
(K(x i,x j))m
i,j=1是半正定矩阵.其中的m×m矩阵(K(x i,x j))m
i,j=1
叫做关于x={x1,...,x m}的
核矩阵.如果核函数K是连续的，对称的，半正定的，称该核函数K为Mercer核.
注意到核函数的半正定性意味着对任意x∈X，有K(x,x)≥0.若核函数是半正定的,
定义C K:=sup x∈X √
K(x,x)，则C K:=sup x,t∈X
√
|K(x,t)|.这是因为矩阵
⎡
⎢⎢⎢
⎢⎢⎢
⎣
K(x,x)K(x,t)
K(t,x)K(t,t)
⎤
⎥⎥⎥
⎥⎥⎥
⎦是
半正定的，有(K(x,t))2≤K(x,x)K(t,t)成立.
接下来我们介绍一种由内积和核函数定义的空间-再生核Hilbert空间.
定义2.2[22]令X是度量空间,ℋ是函数f:X→R的一个空间.我们将ℋ称为内积为⟨·,·⟩K的再生核Hilbert空间如果存在唯一的核函数K:X×X→R满足
(i)K有再生性，即⟨f,K(x,·)⟩K=f(x)对于所有的f∈ℋ都成立.特别地,
⟨K(x,·),K(x′,·)⟩K=K(x,x′).
(ii)ℋ=span{K(x,·)|x∈X}，其中S表示集合S的完备.
我们将核函数为K的再生核Hilbert空间记作ℋK.并在此声明K(x,·)=K x(·).

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。