維數(shù)約簡中的若干問題.pdf

1、維數(shù)約簡是機(jī)器學(xué)習(xí)中的重要問題，本文著重介紹了該領(lǐng)域中四個(gè)問題的研究成果：
　　流形學(xué)習(xí)作為非監(jiān)督、非線性降維方法曾一度廣為關(guān)注，如何對多樣的流形學(xué)習(xí)算法進(jìn)行合理的分類與評估一直是難以解決的問題。我們提出了一個(gè)基于算法設(shè)計(jì)思想的分類方法將常見的算法分為保距映射、圖嵌入與統(tǒng)計(jì)方法三類，我們分別討論了每類方法共同的優(yōu)點(diǎn)以及不足；之后我們分幾個(gè)方面對這些算法進(jìn)行了評估：我們仔細(xì)的分析了常見算法的復(fù)雜性；討論了譜與維數(shù)的關(guān)系；分析了噪聲對

2、每類方法產(chǎn)生的影響；解釋了參數(shù)空間存在空洞時(shí)對算法的影響；使用鄰域保持率分析了算法能否保持流形拓?fù)浣Y(jié)構(gòu)；提出了使用放大因子、主延展方向以及一些定量準(zhǔn)則用于分析流形學(xué)習(xí)算法更細(xì)致的特性。作為這些分析的一個(gè)簡單應(yīng)用，我們針對人臉識別問題，從諸多算法中選擇了較合適的流形學(xué)習(xí)算法進(jìn)行降維，并獲得了較傳統(tǒng)線性降維算法更好的識別率。
　　圖嵌入算法是流形學(xué)習(xí)的一個(gè)重要的分支(見第2章)，它的參數(shù)化(包括線性化和核化兩個(gè)過程)為我們提供了一個(gè)完

3、整的降維框架。核化產(chǎn)生了一個(gè)計(jì)算代價(jià)為O(N3)的問題，這阻礙了該方法在大規(guī)模數(shù)據(jù)上的應(yīng)用。我們提出使用AP初始化κ均值獲得代表元進(jìn)行近似的算法，由于我們的方法能夠更好的控制量化誤差，在相同代表元個(gè)數(shù)時(shí)能得到對Gram矩陣更好的逼近；我們分析了對不同部分譜逼近的程度，并通過實(shí)驗(yàn)說明不同應(yīng)用需要對不同譜進(jìn)行逼近。我們還給出了對映射逼近的誤差界，并證明該誤差界一樣被量化誤差所控制；相對于對Gram矩陣的逼近，這種方式在PKLR與圖嵌入算法上

4、有著更直觀的解釋，我們的實(shí)驗(yàn)也表明圖嵌入上該方法獲得的解更好且參數(shù)更少。我們前期的工作比較了一些線性化圖嵌入算法的特點(diǎn)；利用近似算法我們在大規(guī)模問題上比較了這些核化圖嵌入算法，我們得出了一些有意思的結(jié)論，如：求最小特征值的圖嵌入算法不適合使用譜下降較快的核函數(shù)進(jìn)行核化；局部性的模型可以通過局部性的核函數(shù)得到類似的效果。
　　我們利用基于核方法構(gòu)造的獨(dú)立性準(zhǔn)則設(shè)計(jì)了一種監(jiān)督維數(shù)約簡算法，分析表明它可以做為充分維數(shù)約簡算法如KDR的一

5、種近似。但是相對于KDR每次迭代需要O(N3)的時(shí)間復(fù)雜度，我們的算法僅需要O(N2)與一次N階矩陣乘法的時(shí)間，具有更低的計(jì)算代價(jià)。我們在一些模擬數(shù)據(jù)上討論了我們的方法可能存在的問題，但是使用真實(shí)數(shù)據(jù)的多數(shù)實(shí)驗(yàn)中，我們的方法可以給出與KDR類似的結(jié)果。我們還討論了使用HSIC統(tǒng)計(jì)量確定SDR投影空間維數(shù)的上界的方法，這個(gè)問題在多數(shù)文獻(xiàn)中都沒有給出較合理的解決方案。我們進(jìn)一步討論了這類算法與圖嵌入算法之間的聯(lián)系，發(fā)現(xiàn)圖嵌入算法可以為其提供

6、較好的初始值，以此減少隨機(jī)搜索的次數(shù)。為了能讓這類模型能夠處理非監(jiān)督信息，我們?yōu)樵Ｐ吞砑恿薒aplace光滑子，通過實(shí)驗(yàn)發(fā)現(xiàn)在較低維投影時(shí)能夠獲得較僅利用監(jiān)督信息的模型更好的結(jié)果。最后我們提出了使用這類算法處理非監(jiān)督降維與CCA問題的方法作為今后一個(gè)潛在的研究方向。
　　在處理一些實(shí)際問題的時(shí)候，數(shù)據(jù)中存在的序關(guān)系往往十分重要，因?yàn)檫@些關(guān)系揭示了數(shù)據(jù)在潛在的流形上的分布，在我們的實(shí)驗(yàn)中也發(fā)現(xiàn)保持序關(guān)系能夠改善分類器的泛化能力。我

7、們第一次將這類問題從傳統(tǒng)分類問題中分離出來，稱之為趨勢學(xué)習(xí)。我們比較了趨勢學(xué)習(xí)與其他傳統(tǒng)學(xué)習(xí)問題的異同點(diǎn)，如分類是對分界面建模，而趨勢學(xué)習(xí)是對狀態(tài)之間的遷移過程建模。通過對傳統(tǒng)線性模型SVM與PKLR的仔細(xì)比較，我們認(rèn)為后者能更方便地用于對趨勢學(xué)習(xí)建模。這樣我們獲得了一個(gè)DAG正則化的PKLR模型，由于其約束非凸，我們給出了一個(gè)使用CCCP求解的算法。為了驗(yàn)證我們想法的合理性，我們在兩組模擬數(shù)據(jù)和兩組真實(shí)數(shù)據(jù)上進(jìn)行了實(shí)驗(yàn)，結(jié)果說明在標(biāo)注