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

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

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

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

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