Kernel-Method-核回归-核方法

1今天内容核回归核方法Kerneltrick正则化理论2非参数回归参数回归（线性回归）时，假设r(x)为线性的。当r(x)不是x的线性函数时，基于最小二乘的回归效果不佳非参数回归：不对r(x)的形式做任何假定参考核密度估计局部加权方法：用点x附近的Yi的加权平均表示r(x)权重为核函数的值，邻域由核函数的宽度控制3核回归：Nadaraya-Watson回忆一下回归方程的定义：分别对用核密度估计，得到11,ˆ,nhiiinhjjKxxyrxKxx||,,,rxYXxyfyxdyyfxydyyfxydyfxfxydyE,,fxfxy4核回归：Nadaraya-Watson证明：1211ˆ,,,nhihiifxyKxxKyyn1211ˆ,,,nhihiiyfxydyKxxyKyydyn11221,nihiiyyyKxxKdynhh1211,nhiiiKxxshyKsdsn111,nhiiiKxxyn1,0K(x)dxxK(x)dx5核回归：Nadaraya-Watson证明（续）,fxyydyrxfx11111111111,,,ˆ1,,,nnnhiihiihiiiiinnnhjhjhjjjjKxxyKxxyKxxynrxKxxKxxKxxn6核回归：Nadaraya-Watson这可以被看作是对y取一个加权平均，对x附近的值给予更高的权重：其中1,,hiinhjjKxxwxKxx1ˆniiirxwxy7核回归：Nadaraya-Watson将核回归估计写成如下形式：其中，ˆˆˆhhgxrxfx11ˆ,nhhiiigxKxxyn11ˆ,nhhiifxKxxn11ˆ,nhhiiigxKxxynEE,hiiKxxyE,|hKxuyfyufudydu,|hKxufuyfyudydu,hKxuguduru8核回归：Nadaraya-Watson类似核密度估计中求期望的展开，得到同理，其中222ˆ''2hhgxgxgxxKxdxE221ˆhgxxKxdxnhV2ixV9核回归：Nadaraya-Watson最后，得到估计的风险为最佳带宽以的速率减少，在这种选择下风险以的速率减少，这是最佳收敛速率（同核密度估计）15n45n44221ˆ,24nfxRrrhxKxdxrxrxdxfx22Kxdxdxnhfx10核回归：Nadaraya-Watson实际应用中，利用交叉验证对求最佳带宽h。交叉验证对风险的估计为实际上不必每次留下一个计算单独估计，可以写成以下形式21ˆˆniiiiJhYrx22111ˆˆ01niiinijjJhYrxKxxKh11例：Example20.23不同带宽下Nadaraya-Watson回归的结果12核回归：Nadaraya-Watson模型类型：非参数损失：平方误差参数选择：留一交叉验证13局部线性回归问题：加权核回归在训练数据中靠近边界的点的估计很差核在边界区域不对称，局部加权平均在边界区域上出现严重偏差局部线性回归局部线性回归：在每一个将要被预测的点x处解一个单独的加权最小二乘问题，找到使下述表达式最小的21,nhiiiiKxxyxxx14局部线性回归边界上的N-W核：核在边界不对称偏差大边界上的局部线性回归：将偏差降至一阶蓝色曲线：真实情况绿色曲线：估计值黄色区域：x0的局部区域sin,~0,1,~0,13YXXUniformN15核回归：局部线性回归则估计为：其中W(x)是一个的对角矩阵且第i个对角元素是估计在yi上是线性的，因为权重项wi(x)不涉及yi，可被认为是等价核nnˆˆrxxx1TTTxxxXWXXWy1niiiwxy,hiKxx16局部线性回归局部线性回归通过自动修改核，将偏差降至一阶由于,偏差为2000001ˆ2niiirxrxrxxxwxE001ˆniiirxwxrxE0000011nniiiiirxwxrxxxwx200012niiirxxxwx2000002iiirxrxrxrxxxxx011niiwx0010niiixxwx17局部线性回归边界上的局部等价核（绿色点）内部区域的局部等价核（绿色点）18局部多项式回归局部多项式回归：用d次多项式回归代替线性回归可以考虑任意阶的多项式，但有一个偏差和方差的折中通常认为：超过线性的话，会增大方差，但对偏差的减少不大，因为局部线性回归能处理大多数的边界偏差，19可变宽度核可变宽度核：如使每一个训练点的带宽与它的第k个近邻的距离成反比在实际应用中很好用，虽然尚未有理论支持怎样选择参数不会改变收敛速度，但在有限样本时表现更好注意：上述这些扩展（包括局部线性/局部多项式）都可应用到核密度估计中20核方法为什么要用核方法？得到更丰富的模型，但仍然采用同样的方法如岭回归方法核岭回归内容Kerneltrick再生Hilbert空间21线性模型线性模型：方便、应用广泛有很强的理论保证但还是有局限性可以通过扩展特征空间增强线性模型的表示能力如特征空间为R6而不是R2特该特征空间的线性预测器为-2-1.5-1-0.500.511.52-1.5-1-0.500.511.52212121212,1,2,2,2,,xxxxxxxx22121000111yxxx22岭回归对给定的最小化正则化的残差则最优解为0(,)TridgeTRSSyXyX22yX1ˆTTpXXIXy(,))2220ridgeTTRSSXyXXTTpXXIXy需O(p3)运算23对偶表示一种对偶表示为：其中1TTTTXXIXyXyXX11TTnyXyXyXXXXyGIy1TTXyXXTGXX需O(n3)运算TTpXXIXy24对偶岭回归为了预测一个新的点其中此时只需计算Gram矩阵G11(),,nTiiifxxxxzyGI,izxx1,TnXGIy,,TijijGxxGXX岭回归只需计算数据点的内积25特征空间中的线性回归基本思想：将数据映射到高维空间（特征空间）然后在高维空间中用线性方法嵌入式特征映射：:pPxRFRPp26核函数则核函数为其中为将数据映射到高维空间的映射有许多可能的核函数最简单的为核,(),()FKxuxu,,Kxuxu27特征空间中的岭回归为了预测一个新的点其中计算Gram矩阵G11(),,nTiiifxxxxzyGI(),()izxx1,TnXGIy,,(,)TijijijGxxKxxGXX利用核函数计算内积28另一种对偶表示推导方式线性岭回归最小化：等价于满足约束则拉格朗日函数为22111,ppniijiijjijjyrxrxx2211minjpnijij1piiiiijjjyrxyx221111,,ppnnijiiijjiijijLyx29Wolfe对偶问题转化为其对偶问题：对L求偏导并置为0，得到111202nnjiijjiijiijLxx1202iiiiiL,min,,QL221111,,ppnnijiiijjiijijLyx30Wolfe对偶问题将和代入拉格朗日函数原目标函数转化为112njiijix12ii2111111111441122pnniipnnniikijkjijkkjiijkijikQyxxxx221111,,pniiijjiipjnijijyxL2111111144pnnnniikijkjiiiikjixxy31最优解写成矩阵形式为：得到解：相应的回归方程为：11,where,44TTTijijQyGxxG2111111144pnnnniiiikijkjiiikjQyxx1110222QyyGGI1ˆ,,where,TirxxyIzzxxG点积1pTijkjikjxxxx112njiijix32核化岭回归将点积换成核函数Kerneltrick就实现了对线性岭回归的核化，在空间统计学中称为Kriging算法。,ijijGxx,ijijKKxx33核方法通过将输入空间映射到高维空间（特征空间），然后在高维空间中用线性方法高维：维数灾难通过核技巧，避免维数灾难34KernelTrick将问题变为其对偶问题：只需计算点积，与特征的维数无关，如在线性岭回归中，最大化下列目标函数在高维空间中的点积可写成核(kernel)的形式，如果选定核函数，这无需计算映射可以计算点积x11,where,44TTTijijQyGxxG11,where,44TTTijijQyKxxK35KernelTrick总之，这些被称为核技巧(kerneltrick),寻找一个映射：和一个学习方法，使得F的维数比X高,因此模型更丰富算法只需要计算点积存在一个核函数，使得在算法中任何出现项的地方，用代替亦称为原方法的核化(kernelizingtheoriginalmethod).()()(),,xxKxxffº%%(),Kxx%:XF,xx%点积核36什么样的函数可以作为核函数？Mercer’s定理给出了连续对称函数k可作为核函数的充要条件：半正定半正定核：对称：且对任意训练样本点和任意满足K被称为Gram矩阵或核矩阵。1,,nxxK1,,nRaaÎK(),0,,ijijijijijKKkxxaa?å()(),,kxxkxx=%%0Taa³K矩阵形式：37半正定核的性质对称Cauchy-Schwarz不等式(,)(),()(),()(