l1范數(shù)的點到平面距離的解析表示

l1范數(shù)的點到平面距離的解析表示

距離測量是機器學習和模式識別領(lǐng)域的基礎(chǔ)工作。為了衡量模型或幾何結(jié)構(gòu)，應該使用距離來衡量模型之間的相似性。現(xiàn)在，由于l2范數(shù)易于計算和幾何意義明確，因此采用了eoclidean和mahara-mans距離。以大時間隔學習器為例，基于ov標準的支持向量機（svm）和最小平方svm（lsdv）的設計方法。點到平面距離及投影的計算問題,均可歸結(jié)為范數(shù)最小化問題,但相對L2范數(shù),其他范數(shù)優(yōu)化問題求解更為困難.稀疏學習問題中,模型多采用L1范數(shù)設計,導出的問題雖然是凸優(yōu)化問題,甚至是嚴格凸,理論上存在最優(yōu)解,但由于1-范數(shù)的不可導性,目前只能采用迭代方式求得近似解.已有的求解方法可歸為五類以上問題雖均屬于L1范數(shù)最小化問題,由于解決的具體問題不同,所導出的優(yōu)化問題不同,故計算方法亦有所不同.本文討論的是L1范數(shù)下一個具體問題,即如何計算點到平面的距離,以及該點在平面上投影解析表達式計算問題.該問題的數(shù)學描述如下:式(1)中v∈R式(1)的優(yōu)化方法很多(可借鑒上述五種方法),但多是采用迭代求解(近似解),據(jù)作者所知,此類問題目前尚未出現(xiàn)解析解.本文從經(jīng)典的線性規(guī)劃方法開始討論,相關(guān)描述見第1節(jié)相關(guān)工作.1相關(guān)工作式(1)的經(jīng)典求解方法有兩種:線性規(guī)劃和拉格朗日乘子法.前者是通過代換,將其轉(zhuǎn)化為線性規(guī)劃問題1.1線性規(guī)劃求解方法Mangasarian令x-v=p-q,其中p,q≥0,則x=v+p-q,‖x-v‖這是一個經(jīng)典的線性規(guī)劃問題.求解方法很多,包括牛頓迭代法、內(nèi)點迭代法等,也可用Mangasarian1.2問題轉(zhuǎn)化約束按LiuandYe定理1問題(1)是一個凸優(yōu)化問題,存在最優(yōu)解且解唯一.簡證容易驗證問題(1)是凸優(yōu)化問題.形如:的優(yōu)化問題,均可引入拉格朗日乘子λ:設x*,λ*對原問題及其對偶問題的最優(yōu)解,由于問題(1)沒有不等式約束,x*只需滿足w此類優(yōu)化問題,求解思想描述如下.由于只有等式w式sgn(·)為符號函數(shù).一般取初始值x=0開始迭代,本例中需要滿足等式約束,不失一般性,可以設n-1分量為0,第n個分量滿足約束就可.這種形式的具體計算方法有很多,在此不再贅述.以上兩種方法,均是通過迭代方法獲得L1范數(shù)優(yōu)化問題的近似解,然而,對于本文的等式約束,約束條件要弱于線性方程組的約束Ax=b(A是m×n階矩陣,b為n維向量),因而有望能找出更簡單的解,甚至期望找到L1和L2范數(shù)之間的聯(lián)系.2解析定理2的解析法為方便閱讀,本節(jié)先簡要回顧一下歐氏度量下的L2范數(shù)中有關(guān)投影和點到平面距離的計算方法,如定理2描述,此處略去證明定理2歐氏距離下的n維線性空間中,點x到超平面g(x)=w是在g(xL2范數(shù)下的歐氏距離和投影可以解析獲得,對構(gòu)造或解釋上述大間隔學習器至關(guān)重要,而由于L1范數(shù)的不可導性,能否也存在類似的結(jié)論?很多學者在設計模型時均對L1、L2范數(shù)同時優(yōu)化2.1解析假設.設v兩者的關(guān)系用定理3描述,為便于理解定理3,以下先回顧一下H9lder不等式.引理1H?lder不等式設a定理3對證明不失一般性,設x=(x至此,通過以上分析,盡管找出了L1范數(shù)下點到平面距離的上下界,為迭代求解此類問題的初始點的選擇提供了理論保證,克服了以往的隨機選擇.下文討論解析解問題.2.2線性空間的建立本節(jié)中,先給出一個二維問題的線性規(guī)劃求解示例(圖1所示).為方便直接使用matlab函數(shù)linprog求解線性規(guī)劃.記z=[p其中a圖1所示為一個二維示例,圖中的平面方程為[-2,1]×x-4=0,點v設p由優(yōu)化目標知,需要在集合{(w此時的式(1)的最優(yōu)解為:同理,對于p=(0,0,…,t,…,0)定理5線性空間R在形如式(1)的優(yōu)化目標下,點v在該平面上的投影為:其中w證明當點v在平面w綜合(1)(2),3算法比較及驗證本節(jié)實驗分為兩個部分,一是對上述L1投影求解方法是否正確進行驗證的可視化例子;二是就本文提出的方法的計算效率,實驗比較對象為一般的L1范數(shù)最小化問題的常規(guī)計算方法,本文選擇的是線性規(guī)劃計算方法.圖2給出二維空間和三維空間上的兩個示視化例子.圖中標記為“*”為隨機生成的樣本,來自區(qū)間[0,1]的均勻分布,超平面如圖2中的實線(二維)和一組平行實線加顏色填充(三維)所示,法向量w的分量在[-0.50.5]中隨機選取,閾值b在[0,1]中選取.“□”表示“*”的歐氏距離投影,“○”為由線性規(guī)劃解出的L1投影,“+”是本文式(15)計算的投影.從圖中可以看出,線性規(guī)劃方法計算所得的L1范數(shù)投影與本文方法幾乎一致,兩者的投影幾乎疊加在一起.以下將從運算時間和計算精度方面進行比較.為比較本文方法和線性規(guī)劃方法的計算效率,本文隨機產(chǎn)生一定數(shù)量的樣本集,維數(shù)均指定為40維進行計算,記錄兩者的運算時間和兩種投影之間的差別,前者采用cputime為時間單位,后者用兩個投影之間的歐氏距離來表示兩者的差別,為清楚描述兩者差異,本文還記錄了一次隨機實驗中兩者的投影差最小值、最大值、平均值和標準差.值得一提的是,線性規(guī)劃求解方法,在計算過程中出現(xiàn)了對偶問題無解現(xiàn)象,這顯然是不可能的,也反映出了迭代方法的不穩(wěn)定性.為比較的公平性,本文忽略了這種無解現(xiàn)象.表1中反映出來的問題是,雖然兩者均可用于計算L1范數(shù)投影,但迭代方法不僅需要更長的計算時間,而且隨著樣本維數(shù)的增加,迭代法計算誤差也隨之增加.此外,迭代方法的計算誤差也表現(xiàn)出一定的隨機性.4解析計算方法解析本文討論了L1范數(shù)最小化問題的一個具體實例,提出了L1范數(shù)點到超平面距