l1范數的點到平面距離的解析表示_第1頁
l1范數的點到平面距離的解析表示_第2頁
l1范數的點到平面距離的解析表示_第3頁
l1范數的點到平面距離的解析表示_第4頁
全文預覽已結束

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

l1范數的點到平面距離的解析表示

距離測量是機器學習和模式識別領域的基礎工作。為了衡量模型或幾何結構,應該使用距離來衡量模型之間的相似性?,F在,由于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范數點到超平面距

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論