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

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

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