l1范数的点到平面距离的解析表示

l1范数的点到平面距离的解析表示

距离测量是机器学习和模式识别领域的基础工作。为了衡量模型或几何结构，应该使用距离来衡量模型之间的相似性。现在，由于l2范数易于计算和几何意义明确，因此采用了eoclidean和mahara-mans距离。以大时间隔学习器为例，基于ov标准的支持向量机（svm）和最小平方svm（lsdv）的设计方法。点到平面距离及投影的计算问题,均可归结为范数最小化问题,但相对L2范数,其他范数优化问题求解更为困难.稀疏学习问题中,模型多采用L1范数设计,导出的问题虽然是凸优化问题,甚至是严格凸,理论上存在最优解,但由于1-范数的不可导性,目前只能采用迭代方式求得近似解.已有的求解方法可归为五类以上问题虽均属于L1范数最小化问题,由于解决的具体问题不同,所导出的优化问题不同,故计算方法亦有所不同.本文讨论的是L1范数下一个具体问题,即如何计算点到平面的距离,以及该点在平面上投影解析表达式计算问题.该问题的数学描述如下:式(1)中v∈R式(1)的优化方法很多(可借鉴上述五种方法),但多是采用迭代求解(近似解),据作者所知,此类问题目前尚未出现解析解.本文从经典的线性规划方法开始讨论,相关描述见第1节相关工作.1相关工作式(1)的经典求解方法有两种:线性规划和拉格朗日乘子法.前者是通过代换,将其转化为线性规划问题1.1线性规划求解方法Mangasarian令x-v=p-q,其中p,q≥0,则x=v+p-q,‖x-v‖这是一个经典的线性规划问题.求解方法很多,包括牛顿迭代法、内点迭代法等,也可用Mangasarian1.2问题转化约束按LiuandYe定理1问题(1)是一个凸优化问题,存在最优解且解唯一.简证容易验证问题(1)是凸优化问题.形如:的优化问题,均可引入拉格朗日乘子λ:设x*,λ*对原问题及其对偶问题的最优解,由于问题(1)没有不等式约束,x*只需满足w此类优化问题,求解思想描述如下.由于只有等式w式sgn(·)为符号函数.一般取初始值x=0开始迭代,本例中需要满足等式约束,不失一般性,可以设n-1分量为0,第n个分量满足约束就可.这种形式的具体计算方法有很多,在此不再赘述.以上两种方法,均是通过迭代方法获得L1范数优化问题的近似解,然而,对于本文的等式约束,约束条件要弱于线性方程组的约束Ax=b(A是m×n阶矩阵,b为n维向量),因而有望能找出更简单的解,甚至期望找到L1和L2范数之间的联系.2解析定理2的解析法为方便阅读,本节先简要回顾一下欧氏度量下的L2范数中有关投影和点到平面距离的计算方法,如定理2描述,此处略去证明定理2欧氏距离下的n维线性空间中,点x到超平面g(x)=w是在g(xL2范数下的欧氏距离和投影可以解析获得,对构造或解释上述大间隔学习器至关重要,而由于L1范数的不可导性,能否也存在类似的结论?很多学者在设计模型时均对L1、L2范数同时优化2.1解析假设.设v两者的关系用定理3描述,为便于理解定理3,以下先回顾一下H9lder不等式.引理1Hölder不等式设a定理3对证明不失一般性,设x=(x至此,通过以上分析,尽管找出了L1范数下点到平面距离的上下界,为迭代求解此类问题的初始点的选择提供了理论保证,克服了以往的随机选择.下文讨论解析解问题.2.2线性空间的建立本节中,先给出一个二维问题的线性规划求解示例(图1所示).为方便直接使用matlab函数linprog求解线性规划.记z=[p其中a图1所示为一个二维示例,图中的平面方程为[-2,1]×x-4=0,点v设p由优化目标知,需要在集合{(w此时的式(1)的最优解为:同理,对于p=(0,0,…,t,…,0)定理5线性空间R在形如式(1)的优化目标下,点v在该平面上的投影为:其中w证明当点v在平面w综合(1)(2),3算法比较及验证本节实验分为两个部分,一是对上述L1投影求解方法是否正确进行验证的可视化例子;二是就本文提出的方法的计算效率,实验比较对象为一般的L1范数最小化问题的常规计算方法,本文选择的是线性规划计算方法.图2给出二维空间和三维空间上的两个示视化例子.图中标记为“*”为随机生成的样本,来自区间[0,1]的均匀分布,超平面如图2中的实线(二维)和一组平行实线加颜色填充(三维)所示,法向量w的分量在[-0.50.5]中随机选取,阈值b在[0,1]中选取.“□”表示“*”的欧氏距离投影,“○”为由线性规划解出的L1投影,“+”是本文式(15)计算的投影.从图中可以看出,线性规划方法计算所得的L1范数投影与本文方法几乎一致,两者的投影几乎叠加在一起.以下将从运算时间和计算精度方面进行比较.为比较本文方法和线性规划方法的计算效率,本文随机产生一定数量的样本集,维数均指定为40维进行计算,记录两者的运算时间和两种投影之间的差别,前者采用cputime为时间单位,后者用两个投影之间的欧氏距离来表示两者的差别,为清楚描述两者差异,本文还记录了一次随机实验中两者的投影差最小值、最大值、平均值和标准差.值得一提的是,线性规划求解方法,在计算过程中出现了对偶问题无解现象,这显然是不可能的,也反映出了迭代方法的不稳定性.为比较的公平性,本文忽略了这种无解现象.表1中反映出来的问题是,虽然两者均可用于计算L1范数投影,但迭代方法不仅需要更长的计算时间,而且随着样本维数的增加,迭代法计算误差也随之增加.此外,迭代方法的计算误差也表现出一定的随机性.4解析计算方法解析本文讨论了L1范数最小化问题的一个具体实例,提出了L1范数点到超平面距