李群覆蓋學(xué)習(xí)算法研究進(jìn)展

陳彥至，張子洋，薛 琦，劉 力，李凡長

（蘇州大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 江蘇 蘇州 215006）

0 引言

覆蓋作為數(shù)學(xué)領(lǐng)域的一個重要概念，高保真地描繪了被覆蓋對象原有的特征，并在其基礎(chǔ)上進(jìn)行了重要的簡化，使許多復(fù)雜的推導(dǎo)變得十分輕松，因此受到研究人員的廣泛關(guān)注，常被用于解決基變換、典范映射、奇點等問題。

而目前計算機(jī)的機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域常常需要用到具有復(fù)雜特征和龐大規(guī)模的數(shù)據(jù)，這些數(shù)據(jù)往往會導(dǎo)致計算速度慢、準(zhǔn)確率低等問題。覆蓋思想正適合簡化這類問題，能夠?qū)Ａ繑?shù)據(jù)中的重要信息進(jìn)行高效處理，對計算能力的提升有重大意義，于是被引入計算機(jī)領(lǐng)域的各類算法中。如今，基于覆蓋思想的算法已在文本分類[1]、服務(wù)推薦[2]、社團(tuán)發(fā)現(xiàn)[3]、不完整數(shù)據(jù)處理[4]、多示例學(xué)習(xí)[5]等領(lǐng)域有較多的應(yīng)用，體現(xiàn)出其優(yōu)秀的準(zhǔn)確度、抗干擾性、執(zhí)行效率與泛化能力。

本文以經(jīng)典覆蓋算法為基礎(chǔ)，著眼李群機(jī)器學(xué)習(xí)開辟的李群覆蓋學(xué)習(xí)領(lǐng)域，綜述了該領(lǐng)域近年來的研究進(jìn)展，提出了未來可能的發(fā)展趨勢，旨在為后續(xù)的研究提供依據(jù)。

1 覆蓋算法概述

ZHANG L[6]首先給出了覆蓋算法的概念，該算法從神經(jīng)網(wǎng)絡(luò)入手，針對M-P 神經(jīng)元模型提出了該模型的幾何意義，M-P 模型的輸出函數(shù)為y=sgn(<ω,x>-θ)，其中<ω,x>-θ=0 可以表示n維空間中的一個超平面，它可將空間分為兩個部分，若將所有輸入向量都投影到高一維的超球面上，超球面落在超平面分割出的正半空間中的范圍，被稱為“球形鄰域”；如此做則一個球形領(lǐng)域?qū)?yīng)了一個神經(jīng)元，同類樣本對應(yīng)的球形領(lǐng)域合并，形成了對該類樣本的覆蓋，另一類的樣本被另一組球形領(lǐng)域覆蓋，這樣一來便實現(xiàn)了從復(fù)雜的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)問題到覆蓋問題的轉(zhuǎn)換。

在覆蓋算法提出后，許多學(xué)者對該領(lǐng)域進(jìn)行了深入的研究工作，并在其基礎(chǔ)上提出了新的優(yōu)化算法。吳濤等[7]把常用于支持向量機(jī)之中的核函數(shù)引入了覆蓋算法，通過覆蓋融合技術(shù)將同類型的領(lǐng)域融合起來，獲得更具健壯性的、邊緣更加光滑的領(lǐng)域。針對覆蓋個數(shù)與算法性能之間的矛盾，張燕平等[8]引入模擬退火法尋找覆蓋中心，減少覆蓋的個數(shù)，同時保證較高的準(zhǔn)確率。為了對算法的復(fù)雜度進(jìn)行簡化，吳濤等[9]提出多側(cè)面覆蓋算法，采用分治法劃分輸入樣本集，分別求出各劃分部分的特征子集。陳潔等[10]重新在圖表示上定義了覆蓋半徑與覆蓋中心，提出新型聚類覆蓋算法。

2 多連通李群覆蓋學(xué)習(xí)算法

經(jīng)典覆蓋算法通過把樣本映射到超球面上，將原始問題轉(zhuǎn)化為覆蓋問題，在它的啟發(fā)下，李群機(jī)器學(xué)習(xí)研究團(tuán)隊提出了一種新的算法方案，即利用李群的特殊代數(shù)幾何性質(zhì)解決更多元的問題。李群既是群，也是微分流形，這使它擁有特殊的代數(shù)幾何結(jié)構(gòu)。作為群，李群具有封閉性，擁有唯一的幺元和逆元，群運(yùn)算滿足結(jié)合律。作為微分流形，李群具有光滑性質(zhì)，單位元處的切向量空間可以呈現(xiàn)出它的特殊性質(zhì)[11]。代數(shù)和幾何相互兼容，使得李群元素的群乘法和求逆運(yùn)算都是光滑的。因此，在李群中可以體現(xiàn)出一種連續(xù)的變換過程，熟練運(yùn)用李群結(jié)構(gòu)能幫助我們處理現(xiàn)實中涉及區(qū)分多種變換的問題，也能更有效地提取特征，取得更為精確的結(jié)果，極大地提升運(yùn)算的性能。

李群的覆蓋是李群一個重要的研究內(nèi)容。對于連通李群，存在一個單連通李群，是它的覆蓋群。連通李群與其覆蓋群具有同態(tài)關(guān)系，且若原始李群本身單連通，則其與覆蓋群同構(gòu)。利用以上特性，可以將所有的樣本都映射到李群空間中，將多值李群問題轉(zhuǎn)換到覆蓋群上進(jìn)行求解，在覆蓋群上對樣本的類別進(jìn)行鑒定，從而區(qū)分不同類別的樣本[11]。

由于李群是一種連續(xù)群，所以可以采用一組連續(xù)變化的實參數(shù)對它每一個元素進(jìn)行表示，一般取恒元處的參數(shù)為零，其鄰近元素則通常被稱作無窮小元素。任意元素R 乘以無窮小元素可以得到自己的鄰近元素，對于屬于同一類別的任意兩個點，它們之間連線的本質(zhì)是無窮多個無窮小元素的乘積。由于無窮小元素是一個極限的概念，無窮小變換的乘積次序可以交換，若改變兩點間無窮小元素相乘的順序，則可以得到多條新的連線，這些連線同倫。樣本點到恒元點之間至少存在一條道路，稱為樣本點在群空間中的道路，結(jié)合上述樣本點間的同倫關(guān)系可以得出，同類樣本點在群空間中的道路同倫。同倫是一種等價關(guān)系，所以同類樣本點在群空間中的道路屬于同一個道路等價類。

同類樣本點間的道路同倫，所以其所屬的李群空間中的任何閉道路都同倫于零，即該空間單為連通李群空間。于是，一個道路等價類對應(yīng)一個單連通李群空間。有了上述基礎(chǔ)，嚴(yán)晨等[12]提出了多連通李群覆蓋學(xué)習(xí)算法，選擇道路覆蓋作為解決覆蓋問題的具體角度，通過求解一種最優(yōu)的道路表示，覆蓋整個道路等價類，李群的覆蓋問題就轉(zhuǎn)為求最優(yōu)道路覆蓋問題。

想要求解最優(yōu)道路，需要考慮將最優(yōu)道路分割，求解割點和割點處的鄰域。根據(jù)前文分析，可知通過割點鄰域的道路具有很高的關(guān)聯(lián)度，可以規(guī)定這些道路等價，于是最優(yōu)道路割點鄰域覆蓋的道路都屬于相同的類別。選取樣本點作為割點構(gòu)造鄰域，計算出其半徑，并找到被該鄰域覆蓋的樣本對應(yīng)道路。反復(fù)取未被覆蓋的樣本點進(jìn)行學(xué)習(xí)，直到所有樣本的對應(yīng)道路都已被覆蓋，過程中選取的割點及其對應(yīng)鄰域就是求解出相對最優(yōu)道路的割點與鄰域。對于新的待測樣本，只要檢測該樣本對應(yīng)道路是否被各割點的鄰域所覆蓋，就可以判斷其對應(yīng)道路屬于的道路等價類，從而得到該樣本的類別信息。

3 李群覆蓋學(xué)習(xí)優(yōu)化算法

雖然多連通李群覆蓋學(xué)習(xí)算法有著較好的性能表現(xiàn)，但在求解最優(yōu)道路的過程中可能會遇到兩個問題。其一是道路選擇問題，因為求解最優(yōu)道路被轉(zhuǎn)化為求取割點和對應(yīng)的鄰域，割點和鄰域的質(zhì)量直接決定了最優(yōu)道路的質(zhì)量，而在算法的學(xué)習(xí)過程中，樣本點被選作為割點來計算鄰域，所以樣本學(xué)習(xí)的順序會對解的構(gòu)建產(chǎn)生很大的影響。其二是道路交叉問題，包括最優(yōu)道路交叉和割點鄰域重疊兩種情況，樣本對應(yīng)道路若落在交叉重疊范圍內(nèi)，則很容易對覆蓋該道路的最優(yōu)道路產(chǎn)生誤判，從而造成類別的誤判，影響結(jié)果的準(zhǔn)確性。針對以上兩個問題，為了提高識別的準(zhǔn)確率，優(yōu)化算法的性能，后續(xù)研究對算法進(jìn)行了以下的改進(jìn)。

對于道路選擇問題，吳魯輝[13]采用按權(quán)重順序選取樣本點進(jìn)行學(xué)習(xí)的方法替代原本的隨機(jī)順序，用評價函數(shù)fi=Ni/ri對割點進(jìn)行排序，其中對于割點i，Ni為鄰域覆蓋的同類別道路條數(shù)，ri為覆蓋鄰域的測地線半徑；同時采用迭代的策略，當(dāng)一個樣本點作為割點學(xué)習(xí)完畢后，從余下待學(xué)習(xí)樣本點中移除該點，避免對割點進(jìn)行重復(fù)學(xué)習(xí)，從而獲得更好的學(xué)習(xí)效果；并且可以在此基礎(chǔ)上，對評價函數(shù)進(jìn)行改進(jìn)，添加對樣本分布密集程度的考慮，使得優(yōu)先選擇密集型的樣本點進(jìn)行割點的學(xué)習(xí)。

對于道路交叉問題，解決的思路是需要做到控制類內(nèi)距離最小化，類間距離最大化，不同文獻(xiàn)提出了不同的解決方法。

首先，可以將Fisher 投影理論引入李群覆蓋算法中，F(xiàn)isher 投影的作用是向一個低維的曲線或超平面投影樣本點，使得樣本類間散度最大，類內(nèi)散度最小[14]。在此基礎(chǔ)上，嚴(yán)晨等[15]提出基于Fisher 投影的優(yōu)化算法，即在李群空間中尋找一條測地線，將所有樣本向這條測地線投影，使得相同類別的道路盡量靠攏，不同類別的道路盡量分開，從而減少道路交叉的可能。算法既可以在李群空間中直接使用，也可以通過對數(shù)映射在李代數(shù)空間中使用，只要先將道路映射到李代數(shù)空間，得到新的道路表示，再將該道路向測地線投影即可。在李代數(shù)空間中應(yīng)用算法能夠簡便部分運(yùn)算，不過也可能會加大計算的誤差。

吳魯輝[13]在加核思想的啟發(fā)下，通過引入核函數(shù)提出了多李群核覆蓋學(xué)習(xí)算法。核函數(shù)可以實現(xiàn)輸入空間到特征空間的映射，讓同類樣本更集中，不同類樣本更具差異。通過將原始李群樣本映射到更高維的李群空間，算法能夠獲得更優(yōu)的道路等價類，減少求解時不同類之間的影響，提高模型的抗干擾能力，并且使得覆蓋區(qū)域更加可分，覆蓋邊界更具有光滑性。不過，此算法有一定的限制，需要依據(jù)樣本本身特點或其分布情況對核函數(shù)進(jìn)行合理的選擇，核學(xué)習(xí)算法的性能依賴于核函數(shù)的選擇。

吳魯輝等[16]則從流形學(xué)習(xí)的角度考慮，根據(jù)映射原始流形到目標(biāo)流形使得數(shù)據(jù)出現(xiàn)特定性質(zhì)的思想，提出了基于同態(tài)映射的優(yōu)化算法，算法的任務(wù)是尋找一個合適的同態(tài)映射，將原始李群樣本映射到目標(biāo)李群空間中，使得目標(biāo)李群空間中不同道路等價類之間的關(guān)聯(lián)度最小化，同一等價類之中的道路關(guān)聯(lián)度最大化；具體的方法一是先在原始李群空間中求出最優(yōu)道路表示，即最優(yōu)道路的各個割點和對應(yīng)的鄰域，接著在此基礎(chǔ)上求解同態(tài)映射，將最優(yōu)道路的割點映射到目標(biāo)李群空間中，重新計算覆蓋半徑，這樣做可以減低計算的復(fù)雜性，但是會存在一定的誤差，且由于針對割點進(jìn)行映射，方法的泛化性不佳；于是提出了方法二，即尋找一個合適的同態(tài)映射，先將樣本先映射到目標(biāo)李群空間，再在其中進(jìn)行最優(yōu)道路的求解。

4 李群覆蓋學(xué)習(xí)算法的局限與展望

李群覆蓋學(xué)習(xí)算法領(lǐng)域已開展了許多較為深入的研究，在初始算法的基礎(chǔ)上也采取了若干優(yōu)化，提高了算法的效率和準(zhǔn)確性，但仍然存在著一定的局限性。

首先從現(xiàn)有的文獻(xiàn)看，大多數(shù)文獻(xiàn)僅對具有少量樣本種類與數(shù)量的數(shù)據(jù)集進(jìn)行了測試，缺少在大型數(shù)據(jù)集上的測試場景，如嚴(yán)晨等[15]使用了MPEG7_CE-Shape01_Part_B 數(shù)據(jù)集，吳魯輝等[16]使用了MNIST 手寫數(shù)據(jù)集。這樣做不能確定算法在海量數(shù)據(jù)下是否能夠保持較高的執(zhí)行效率，清晰分辨出樣本的類別。能否設(shè)計出具有海量數(shù)據(jù)處理能力的算法并在大型數(shù)據(jù)集上進(jìn)行充分的驗證是面向?qū)嶋H問題進(jìn)行研究的重要內(nèi)容。

受限于樣本映射到李群空間的方式，李群覆蓋算法主要針對具有顯著形狀特征的圖形樣本進(jìn)行處理，解決的問題大多為圖像分類相關(guān)問題，應(yīng)用場景沒有完全擴(kuò)展開來。如何改進(jìn)算法提取特征的過程，實現(xiàn)對多種類型的樣本進(jìn)行處理，以做到對應(yīng)用場景的擴(kuò)展也是值得思考的問題。

李群覆蓋學(xué)習(xí)算法解決的都是靜態(tài)數(shù)據(jù)的問題，但隨著科技的發(fā)展，數(shù)據(jù)動態(tài)變化，這一場景對具有即時數(shù)據(jù)處理的能力的算法有著較高的需求。目前的算法未對數(shù)據(jù)更新問題實現(xiàn)支持，在動態(tài)數(shù)據(jù)這一領(lǐng)域尚不能達(dá)到預(yù)期。

算法的泛化性有限。從道路覆蓋的角度解決李群覆蓋問題，并用求割點與對應(yīng)鄰域的方法求解最優(yōu)道路，導(dǎo)致算法對割點選擇有著很強(qiáng)的依賴性，不同的數(shù)據(jù)可能會影響算法的性能，當(dāng)前使用的模型仍然具有優(yōu)化空間。算法的泛化性和識別精度之間具有矛盾，覆蓋個數(shù)少可以確保泛化能力，但識別精度優(yōu)先，覆蓋個數(shù)過多會提高識別進(jìn)度，但會造成過擬合降低泛化性。

為了應(yīng)對以上問題，李群覆蓋學(xué)習(xí)算法應(yīng)進(jìn)行一定的擴(kuò)展，將新的技術(shù)引入算法中，以解決更多角度的問題，提升算法的效率和準(zhǔn)確率。譬如，可以結(jié)合增量算法，提出李群增量算法，實現(xiàn)對動態(tài)數(shù)據(jù)的處理能力；結(jié)合粒子群優(yōu)化思想，利用粒子群的全局搜索能力，從全局的角度對覆蓋進(jìn)行優(yōu)化；結(jié)合模擬退火理論，在保持準(zhǔn)確率的同時減少覆蓋的個數(shù)，調(diào)節(jié)算法識別精度與泛化能力間的矛盾。此外，還可以從其他角度考慮李群覆蓋學(xué)習(xí)算法的優(yōu)化，如覆蓋模型的改進(jìn)、最優(yōu)道路的割點選擇等?？傮w看來，李群覆蓋學(xué)習(xí)算法存在許多優(yōu)化方向，有著較大的改進(jìn)空間，值得進(jìn)行更加深入的研究。