大邊際分類模型中的快速算法與理論分析.pdf

1、分類是機器學習的一個基本問題。大邊際原理是設(shè)計分類算法的重要思想。以大邊際原理為基礎(chǔ)的支持向量機(SVM)已成功的應(yīng)用于二分類，多分類，和更一般的層次化分類中。本文主要關(guān)注基于支持向量機的分類器設(shè)計，針對高維分類任務(wù)中的特征選擇和層次分類問題，提出了快速算法和理論分析。
　　首先，本文調(diào)查了支持向量機中特征選擇的發(fā)展現(xiàn)狀，回顧了相應(yīng)的正則化技術(shù)，重點關(guān)注了雙正則化支持向量機(DrSVM)模型。DrSVM模型可以在選擇重要特征的同時

2、保留相關(guān)度高的特征，有利于構(gòu)造較優(yōu)分類器。因此，大量研究工作聚焦于DrSVM模型的有效求解方法。然而，已有算法的計算復雜度均嚴重依賴于數(shù)據(jù)維度，無法有效處理高維分類任務(wù)。在前人工作的基礎(chǔ)上，本文針對DrSVM模型，提出了高維數(shù)據(jù)下的快速算法。本文重新表述了相應(yīng)的目標函數(shù)，并試圖在其中應(yīng)用乘子交替方向迭代求解方法。由于乘子交替方向迭代求解方法的內(nèi)外雙層迭代可能導致較高的計算代價，本文提出了一種單層迭代算法，從而使計算復雜度從O(nd2)降

3、低為O(K(n3+nd)＋n2d)，其中K為迭代次數(shù)，n為樣本個數(shù)，d為樣本維數(shù)且d(＞＞)n。理論推導表明，本文提出的算法具有全局收斂性。
　　其次，作為二分類和多分類的推廣，本文研究了層次化分類問題?，F(xiàn)在有許多模型和算法針對層次化分類，例如構(gòu)造局部分類器，貝葉斯方法和層次化支持向量機（支持向量機在層次化分類中的推廣）等。其中層次化支持向量機是當前使用最多的方法，因為它是全局分類器且能夠保證分類層次間的一致性。層次化支持向量機的

4、求解一般是轉(zhuǎn)化為二次規(guī)劃問題，從而利用二次規(guī)劃問題的通用求解方法。然而，在層次分類任務(wù)中，輸出空間的高維度提升了二次規(guī)劃的規(guī)模。因此，通用算法計算代價極大。本文基于大邊際原理，將層次化分類的支持向量機轉(zhuǎn)化為最大最小優(yōu)化問題，提出了一個稱為硬感知器的算法(HP)。為提高預測精確度，本文構(gòu)造了一個隨機感知器(SP)算法，它是離線算法。該算法避免了層次化支持向量機非常多的約束所帶來的計算上的代價。本文證明了如果數(shù)據(jù)集是可分的，那么經(jīng)過有限步迭