吳魯輝，李凡長

蘇州大學 計算機科學與技術學院，江蘇 蘇州 215000

多李群核覆蓋學習算法在圖像分類上的應用

吳魯輝，李凡長+

蘇州大學 計算機科學與技術學院，江蘇 蘇州 215000

WU Luhui,LI Fanzhang.Multiply Lie group kernel covering learning algorithm for image classification. Journal of Frontiers of Computer Science and Technology,2016,10(12)：1737-1743.

李群具有代數結構也具有流形幾何結構。將數據映射到多李群空間，并根據李群樣本點在李群流形上的軌道關系，對那些同倫的軌道加以覆蓋，從而使得覆蓋域呈現出類別信息。利用核函數的思想，進一步使得類別不同的覆蓋域更具有可分性，同時覆蓋邊界更具有光滑性，因此提出了多李群核覆蓋學習算法。在MNIST手寫體數字圖像上進行了多組實驗驗證，并對實驗結果進行了分析，結果表明與多連通李群覆蓋學習算法相比，多李群核覆蓋學習算法具有較好的分類效果。

李群；流形結構；覆蓋學習算法；核函數

1 引言

現實世界的數據具有多樣性和復雜性，數據的空間結構信息往往蘊含著更多有效信息，能夠對數據分析提供有力支撐。建模數據的空間結構的一種有效方式是流形，但是沒有有力的數學工具作為流形可計算方式，最終還是利用流形局部同胚與歐式空間這個特點，將數據映射到歐式空間進行研究，處理完成后再映射回流形上。這種方式代價高，而且很難尋找到一個合適的流形結構。

李群不僅是一個群，也是一個微分流形。李群既能夠表示數據所在的流形結構，也提供了一套完整可計算理論。近年來，越來越多的計算機學者開始熟知李群，并將李群引入到與計算機相關的各領域中。文獻[1]給出了李群機器學習的公理系統和基本模型。文獻[2]利用流形上樣本點的內均值求解方式，提出了李群均值學習算法。文獻[3]給出了基于李群的半監(jiān)督學習算法，從而使得可以利用未知類別的李群樣本以改進李群學習器的性能。文獻[4]從深層結構出發(fā)，提出了基于李群的深層結構學習算法，從而能夠獲得原始數據中更抽象更具有不變性的特征。文獻[5]利用李群正態(tài)分布抽取狀態(tài)樣本，提出了一種基于李群正態(tài)分布的粒子濾波算法，提高了跟蹤算法的效率和魯棒性。文獻[6]將系統狀態(tài)空間中動力演化建模成李群，然后利用自由坐標李群積分來提高受限多體系統（multibody system，MBS）的準確率。文獻[7]通過探索動作的李群結構來估計全局動作以及相對測量間估計誤差的協方差，提出了一個基于矩陣李群的高斯分布表示的生成模型，從而構建了一個更好的姿勢回歸模型。

文獻[8]從多連通李群空間中的道路同倫等價關系出發(fā)，得出同一類別的道路是同倫等價的，從而構成一個道路等價類，并用最優(yōu)道路表示來近似表示類別的道路等價類，從而提出了多連通李群覆蓋學習算法。多連通李群覆蓋學習算法克服了經典覆蓋學習算法不能很好對待特征缺失和異常特征突出的問題。在處理分類問題遇到提取的樣本特征較少且不具有代表性時，具有明顯的分類優(yōu)勢。文獻[9]對多連通李群覆蓋學習算法中的道路存在的選擇和交叉問題做了進一步優(yōu)化。文獻[8]通過采樣圖形樣本形狀上的若干點構成的點云，來將原始樣本映射為SO(2)空間中的李群樣本。這種方式具有一定的局限性。

本文考慮利用樣本特征的協方差矩陣來將樣本映射為李群樣本，通過特征之間的關系矩陣在李群流形上的空間關系對樣本的類別進行研究。為了使同類樣本在李群流形上的軌道更具有可分性，本文考慮將李群覆蓋學習和核方法相結合，提出了多李群核覆蓋學習算法，以增強模型的抗干擾能力以及使覆蓋域更具有可分性。最后利用多李群核覆蓋學習算法對研究對象進行分類。

本文組織結構如下：第2章簡單介紹相關的基礎知識，并利用圖像協方差矩陣將圖像樣本映射為李群樣本；第3章提出了多李群核覆蓋學習算法；第4章通過若干個實驗驗證了本文提出的多李群核覆蓋學習算法的性能；第5章給出結論和展望。

2 相關概念介紹

2.1 李群中的覆蓋學習

李群[10-12]G是一種連續(xù)群，其每個元素都可以用一組在歐式空間一定區(qū)域內連續(xù)變化的獨立實參數表示。參數的變化區(qū)域稱為群空間。一般取李群恒元e的參數為0，故恒元的鄰近元素稱為無窮小元素。無窮小元素與任意李群元素M的乘積仍然是該李群的元素，且結果是M的鄰近元素。將無窮多個無窮小元素與M相乘得到M′，那么在群空間就表現為從M在群空間對應的元素A到M′對應元素B的一條連續(xù)曲線，稱該條曲線為從M到M′的道路。任意李群元素M在群空間中的對應點A與恒元e對應元素之間的連續(xù)曲線，稱為該點M的道路。依據同倫等價關系可以將李群元素的道路分成若干組。每組構成一個道路等價類。組數稱為群空間的連通度。當李群的群空間是多連通的時候，則該群真實表示是多值表示。

對應于學習問題，可以利用李群樣本道路之間的某種關系來和本文的研究目的建立特定聯系，以道路來建模研究目的。比如，對于分類問題而言，由于同類樣本映射到李群空間的群元素的獨立實參數是相似的，那么它們在群空間上的道路是同倫等價的，故它們在同一個道路等價類中。而直接求解某個道路等價類是困難的。通過分析多連通李群的性質可知，李群元素M的某個鄰近區(qū)域內的道路是同倫等價的。這樣，利用鄰域覆蓋思想，可以近似地去逼近道路等價類，從而實現對未知樣本的分類。

文獻[8]利用最優(yōu)道路表示來覆蓋道路等價類，提出了多連通李群覆蓋學習算法。但是，多連通李群空間中的道路是復雜的，除去覆蓋方式中覆蓋半徑容易造成的誤判和拒識現象外，道路的選擇和交叉問題也是造成誤判和拒識的兩個原因。本文考慮利用核函數來減弱道路之間的交叉問題。

2.2 圖像的區(qū)域協方差特征

一幅圖像可以表示為I，每個像素的屬性可以表示為I(x,y)。那么，圖像特征F可以表示為F(x,y)= Φ(I,x,y)，其中函數Φ可以表示任何與圖像屬性相關的映射，例如灰度值、顏色和梯度值等。取圖像I中所關心的局部區(qū)域R?F，區(qū)域R內的所有像素對應的Φ值可以表示為，其中zi為d維向量，n為區(qū)域R內的所有像素的個數。R區(qū)域內的向量集構成的協方差矩陣為：

圖像協方差矩陣[13-14]內的任意兩個點P1、P2之間的距離由文獻[15]給出：

其中i=1,2,…,d且xi≠0?？梢宰C明式（2）的d滿足內積空間度量的幾條公理，因此滿足正定矩陣的李群結構。

3 多李群核覆蓋學習算法設計與分析

將原始樣本圖像進行分塊，得到N個分區(qū)域。對于每個區(qū)域提出一些特征，構成特征向量s∈Rd。然后，對特征向量集合FS={s1,s2,…,sN}求協方差矩陣，從而將原始樣本映射為李群樣本。如圖1所示，將手寫體字0的一幅圖像分成4個分塊，從每個小塊中提取出d維特征。然后，對這些特征求協方差矩陣。從而將一幅圖像表示成由特征關系構成的矩陣李群元素。

Fig.1 Block representation of an image圖1 圖像的分塊表示

群與群之間存在著覆蓋關系，從而構成覆蓋群。覆蓋關系是由覆蓋映射定義的。由于直接尋找覆蓋映射是困難的，通過元素之間的道路關系進行表示。模式識別理論指出，低維空間線性不可分的模式通過非線性映射到高維特征空間則可能實現線性可分。但是這種技術存在確定非線性映射函數的形式、參數和特征空間的維數等問題。核函數卻有效避免了這些問題。核函數[16-19]的形式和參數會隱式地改變從輸入空間到特征空間的映射，進而對特征空間的性質產生影響。本文希望利用核距離來度量李群樣本之間的相似性，并在該距離的基礎上對覆蓋鄰域進行求解，以使得模型具有更好的抗干擾能力和覆蓋區(qū)域更具有可分性。

機器學習中，經常使用的高斯核函數是：

由于d(M1,M2)=d(M2,M1)，能推出K(M1,M2)=K(M2, M1)，故K(M1,M2)滿足對稱性。利用文獻[20]中的方法可以證明K(M1,M2)是非負定的。因此，上述定義的李群高斯核函數滿足Mercer定理，故李群高斯函數K(M1,M2)是一個核函數。

李群流形上，兩李群樣本間測地線距離定義為：

其中，M1、M2是兩個李群樣本；ln是以e為底的矩陣對數運算；||?||是Frobenius范數。根據Baker-Campbell-Hausdorff公式[21]并對其進行一階近似，可以近似求得兩個李群元素之間的測地線距離，即：

其中，m1、m2分別是M1、M2在單位元I處的李代數。

李群高斯核函數用于衡量兩李群樣本之間的相似性（距離）。相似性較高的樣本，李群高斯函數的輸出較大，而相異性較高的樣本，李群高斯函數的輸出值較小。經過這種核距離變換，可以使求得的覆蓋域更具有可分性，能夠減弱道路交叉情況。同一類別樣本屬于同一覆蓋群，那么某李群樣本M1的覆蓋鄰域為：

其中，M?I表示與M1異類的李群樣本集合。

覆蓋學習存在兩種固有現象，即誤判和拒識。誤判是由于覆蓋域存在重疊造成的。而拒識是由于未知類別樣本點落在未覆蓋區(qū)域造成的。針對這兩種現象，本文采用以下解決方案：

（1）針對誤判現象，使用如下功能函數來最終確定樣本的所屬類別：

（2）對于拒識現象，本文依據觀測樣本集中的某一類別的所有樣本求解出它們各自的內均值。然后求解拒識樣本點到類別內均值的核距離，距離最小的類別即是該拒識樣本點的類別。其中，內均值定義為如下形式：

其中n表示該類樣本的個數。

根據上面的論述，很容易得到多李群核覆蓋學習算法。多李群核覆蓋學習算法的具體步驟如下：

輸入：樣本集U，一共s個類別。

輸出：每個類別的覆蓋集合Ci，i=1,2,…,s。

步驟1將訓練樣本集U，利用協方差矩陣映射為李群樣本集X，且樣本集共分為s個類別，即X= {X1,X2,…,Xs}。

步驟2在樣本集Xi(i=1,2,…,s)中構造覆蓋區(qū)域。依次取每個樣本作為中心，利用式（7）求解每個樣本的覆蓋鄰域θ。

步驟3刪除樣本集Xi中被覆蓋的同類樣本點，并將加入到覆蓋集合Ci中。

步驟4重復上述步驟，直到所有樣本都被覆蓋。

假設對樣本進行m分塊的時間是常量t，而每塊提取d維特征的時間開銷為dm，則n樣本所需的時間開銷為n(t+mdm)。設樣本共有s個類別，步驟2、步驟3中需要求解某一樣本與異類樣本之間的兩兩測地線距離，從而最大時間開銷為(n′)2，其中n′≤n。故算法的時間復雜度為：

因此該算法的時間復雜度為O(n2)。

4 實驗結果及分析

本文將通過兩個實驗驗證多李群核覆蓋學習算法的性能，并與多連通李群覆蓋學習算法進行比較。兩個實驗采用的數據集都是MNIST手寫體數據集。第一個實驗選擇相似性較大的樣本和相異性較大的樣本分別做了兩個兩類樣本分類實驗；第二個實驗就MNIST數據集上的多類樣本進行實驗。

4.1 MNIST手寫體數據集上兩類樣本的分類

本實驗采用MNIST數據集，該數據集中的樣本是一個二維圖像，具體實例如圖2所示。每個手寫體數字都是28×28像素的灰度圖像。利用2.2節(jié)的方法可以將圖像轉換為李群樣本。實驗中，選取數字6和9作為訓練集和測試集，顯然數字6和9具有很強的相似性。分別從6、9手寫體數字測試集中隨機選取100個樣本作為實驗測試集，然后依次分別從6、9手寫體數字訓練集隨機抽取50、80、110、140、170、200個作為訓練集。

由于李群高斯核函數中存在超參數γ，進行實驗之前需確定超參數γ的取值。本文在確定的訓練集和測試集上，給超參數γ一個初始值0.015，然后以步長10倍的關系進行縮小下降。實驗結果如圖3所示。從圖中可以看到，γ的取值為0.015×10-14時最好，因此實驗中選取該值作為超參數γ的取值。

Fig.2 Data of experiments圖2 實驗數據

Fig.3 Value of parameterλ圖3 參數λ的取值

兩類樣本6和9的分類實驗結果如圖4所示。其中，MLGKCLA是本文方法的結果，而MCLCLA是多連通李群覆蓋學習算法的實驗結果。

Fig.4 Result of two algorithms on 6 and 9圖4 數字6和9的分類結果

選擇手寫體數字7和8，再次做了實驗。該實驗中的數字7和8具有很大的差異性。同樣，分別從7和8的測試集中隨機抽取100個樣本組成包含200個樣本的測試集。然后，分別從7和8的訓練集中隨機抽取50、80、110、140、130、200個樣本構成相應的訓練集。然后，利用多李群核覆蓋學習算法和多連通李群覆蓋學習算法對其進行分類，分類結果如圖5所示。

在進行農產品創(chuàng)新之后，農家樂也是產業(yè)鏈中必不可少的，首先，農家樂的出現不僅給農民增添了收入，也是這一產業(yè)中的基本特征，也是在旅游業(yè)當中農民參與現代化利益的有效途徑，實現了農村與城市間的貧富差距減少，但是在這之間對農家樂也需要創(chuàng)新，農家樂可以與旅游業(yè)更好的結合，實現第一、第三產業(yè)的相互促進，更多的是能在經濟發(fā)展的同時也不會損害了環(huán)境上的利益。

Fig.5 Result of two algorithms on 7 and 8圖5 數字7和8的分類結果

對比圖4和圖5可知，在小樣本訓練集上，本文算法性能較好。同時，當樣本具有很強的相似性時，多李群核覆蓋學習算法能夠進行較好的分類。而且，本文算法更具有穩(wěn)定性。

4.2 MNIST手寫體數據集上多類樣本的分類

從手寫體數據集中選擇0、1、2手寫體數字作為訓練集以及對應的測試集。從0、1、2手寫體數字的測試集中分別隨機抽取100個作為本實驗的測試集。同時，從0、1、2訓練集分別依次取50、80、110、140、170、200個數據作為訓練集。圖6顯示了兩種算法的分類性能。

從圖6中兩個算法的比較來看，在隨樣本個數的增加而隨機抽取一定數量的樣本下，兩個李群算法的變化趨勢是相同的，即同升同降。但是，MLGKCLA算法比MCLCLA算法更穩(wěn)定，且具有更高的分類準確率。利用協方差矩陣來提取圖像的特征，考慮樣本特征在李群中的空間結構，對圖像的分類具有一定的優(yōu)勢。

Fig.6 Result of two algorithms on multi-class objects圖6 兩個算法在多類對象上的分類結果

5 結論與展望

本文將李群和核函數相結合提出了多李群核覆蓋學習算法。該算法在小樣本訓練集及相似性較高樣本分類中，具有一定的分類性能。但是，實驗中發(fā)現一些問題，比如圖5中存在兩個特殊點。下一步對其進行深入研究，以發(fā)現是什么原因造成這種現象，以求對其進行改進。同時，對于覆蓋學習來說，能不能利用生成模型，通過生成一些有效點來增加某類別的覆蓋范圍以減少拒識現象，或者細化其覆蓋范圍以減少誤判呢，這些也是需要進一步研究的。而利用核函數思想，怎么更進一步利用核的相似性判定，來使得形成的覆蓋域更具有可分性，期望接下來對其進行研究，以獲得一定的解決方法。

[1]Li Fanzhang,Zhang Li，Yang Jiwen,et al.Lie Group machine learning[M].Hefei:University of Science and Technology of China Press,2013.

[2]Gao Cong,Li Fanzhang.Lie group means learning algorithm[J].Pattern Recognition and Artificial Intelligence, 2012,25(6):900-908.

[3]Xu Hanxiang,Li Fanzhang.Semi-supervised learning algorithm based on Lie group[C]//Proceedings of the 2009 WRI Global Congress on Intelligent Systems,Xiamen,China,May 19-21,2009.Washington:IEEE Computer Society,2009:573-577.

[4]He Wenhui,Li Fanzhang.Research on Lie group deep structure learning algorithm[J].Journal of Frontiers of Computer Science and Technology,2010,4(7):646-653.

[5]Ge Huilin,Zhu Zhiyu.Tracking video target via particle filtering on the Lie group normal distribution[C]//2013 32nd Chinese Control Conference,Jul 26-28,2013:904-908.

[6]Terze Z,Müller A,Zlatar D.Lie-group integration method for constrained multibody systems in state space[J].Multibody System Dynamics,2014,33(33):1-33.

[7]Bourmaud G,Megret R,Giremus A,et al.Global motion estimation from relative measurements using iterated extended Kalman filter on matrix Lie groups[C]//Proceedings of the 2014 IEEE International Conference on Image Processing, Paris,Oct 27-30,2014.Piscataway,USA:IEEE,2014:354-356.

[8]Yan Chen,Li Fanzhang,Zou Peng.Multiply connected Lie group covering learning algorithm for image classification[J]. Journal of Frontiers of Computer Science and Technology, 2014,8(9):1101-1112.

[9]Yan Chen,Li Fanzhang.Path optimization algorithms for covering learning[J].Journal of Software,2015,26(11): 2781-2794.

[10]Sagle A A,Walde R E.Introduction to Lie groups and Lie algebras[J].Siam Review,2010,8(1):11-46.

[11]Gallier J.Basics of classical Lie groups:the exponential map,Lie groups and Lie algebra[M]//Geometric Methods andApplications.New York:Springer,2011:459-528.

[12]Gallier J,Gallier C J.Notes on differential geometry and Lie groups[DB/OL].(2016)[2016-04-08].http://www.cis.upenn. edu/～jean/gbooks/manif.html.

[13]Politis D.High-dimensional autocovariance matrices and optimal linear prediction[J].Electronic Journal of Statistics, 2015,9:753-788.

[14]Yeh A B,Lin D K J,Mcgrath R N.Multivariate control charts for monitoring covariance matrix:a review[J].Quality Technology&Quantitative Management,2016(4):415-436.

[15]F?rstner W,Moonen B.A metric for covariance matrices[M]//Geodesy-The Challenge of the 3rd Millennium.Berlin,Heidelberg:Springer,2000:299-309.

[16]Müller K R,Mika S,Tsch G,et al.An introduction to kernelbased learning algorithms[J].IEEE Transactions on Neural Networks,2001,12(2):181-201.

[17]Zhang Yingwei.Enhanced statistical analysis of nonlinear processes using KPCA,KICA and SVM[J].Chemical Engineering Science,2009,64(5):801-811.

[18]Bowman A W.An alternative method of cross-validation for the smoothing of density estimate[J].Biometrika,2015, 71(2):353-360.

[19]Agrachev A,Lee P W Y.Generalized Ricci curvature bounds for three dimensional contact subriemannian manifolds[J]. MathematischeAnnalen,2014,360(1/2):209-253.

[20]Yang Meng,Zhang Lei,Shiu S C K,et al.Robust kernel representation with statistical local features for face recognition[J].IEEE Transactions on Neural Networks&Learning Systems,2013,24(6):900-912. [21]Fletcher P T,Lu C,Joshi S.Statistics of shape via principal geodesic analysis on Lie groups[C]//Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Madison,USA,Jun 18-20,2003. Washington:IEEE Computer Society,2003:95.

附中文參考文獻：

[1]李凡長,張莉,楊季文,等.李群機器學習[M].合肥:中國科技大學出版社,2013.

[2]高聰,李凡長.李群均值學習算法[J].模式識別與人工智能,2012,25(6):900-908.

[4]何文慧,李凡長.李群深層結構學習算法研究[J].計算機科學與探索,2010,4(7):646-653.

[8]嚴晨,李凡長,鄒鵬.多連通李群覆蓋學習算法在圖像分類上的應用[J].計算機科學與探索,2014,8(9):1101-1112.

[9]嚴晨,李凡長.覆蓋學習的道路優(yōu)化算法[J].軟件學報, 2015,26(11):2781-2794.

WU Luhui was born in 1990.He is an M.S.candidate at College of Computer Science and Technology,Soochow University.His research interest is Lie group machine learning.

吳魯輝（1990—），男，安徽阜陽人，蘇州大學計算機科學與技術學院碩士研究生，主要研究領域為李群機器學習。

LI Fanzhang was born in 1964.He received the M.S.degree in computer science and technology from University of Science and Technology of China in 1995.Now he is a professor and Ph.D.supervisor at Soochow University. His research interests include artificial intelligence and machine learning,etc.

李凡長（1964—），男，云南宣威人，1995年于中國科技大學獲得碩士學位，現為蘇州大學教授、博士生導師，主要研究領域為人工智能，機器學習等。

Multiply Lie Group Kernel Covering LearningAlgorithm for Image Classification

WU Luhui,LI Fanzhang+
College of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215000,China
+Corresponding author:E-mail:lfzh@suda.edu.cn

Lie group not only has algebraic structures,but also has manifold structures.Data are mapped to multiply Lie group,according to the track ralation of Lie group samples on the manifold,these tracks which are homotopic can be covered.So,these covering areas can present the category information.This paper proposes a new covering algorithm called multiply Lie group kernel covering learning algorithm that uses kernel function to make the covering area have more divisibility and the edge of covering area smooth.The experimental results on the MNIST datasets show that the proposed algorithm has better classification performance with comparison to the other algorithm called multiply connected Lie group covering learning algorithm.

Lie group;manifold;covering learning algorithm;kernel function

10.3778/j.issn.1673-9418.1605035

A

TP181

Received 2016-05,Accepted 2016-07.

CNKI網絡優(yōu)先出版:2016-07-01,http://www.cnki.net/kcms/detail/11.5602.TP.20160701.1646.002.html