極速非線性判別分析網絡

謝群輝 陳松燦

(南京航空航天大學計算機科學與技術學院，南京，211106)

引 言

線性判別分析(Linear discriminant analysis，LDA)是一種流行的有監(jiān)督數據降維和可視化工具，廣泛用于模式識別和機器學習等各個領域[1-2]；它最大化類間散度的同時最小化類內散度，提取數據特征，將高維投影到2～3維即獲得可視化，能更直觀理解和探索潛在的數據結構[3]，有利于其后續(xù)的分類算法獲得更好的泛化性能。判別分析可分為線性型和非線性型兩大類，上述提及的LDA[4]是線性型的代表之一，而傳統(tǒng)的非線性判別方法主要包括神經網絡和核方法，如核LDA(Kernel linear discriminant analysis，KLDA)[5]，流形判別分析[6]，(深度)神經網絡[7-8]和深度判別分析[9]等。其中KLDA采用核函數將輸入樣本映射到高維特征空間，而后利用LDA進行線性分類。而神經網絡(Neural network，NN)則通過多層結構的非線性變換將輸入映射到輸出空間以實現非線性判別。盡管NN缺乏核方法那樣的簡潔表示方式，但NN所具有的分布并行特點和其對連續(xù)函數的萬能逼近性使其獲得了廣泛應用。事實上，基于NN的判別分析可追溯到1995年Mao和Jain的先驅性工作[10]，即神經網絡判別分析方法(Neural networks discriminant analysis，NNDA)，該工作促發(fā)了眾多非線性化分類和可視化研究。目前該文被引數已超680次，并在1996年獲得了IEEE TNN期刊年度最佳論文獎[11]。然而，與其他多層前向網絡訓練類似，NNDA存在優(yōu)化收斂速度慢、易陷入局部最小、且因網絡結構復雜易導致過擬合等問題。1999年由Scholkopft等[12]提出的KLDA，利用核技巧避免了NNDA復雜的優(yōu)化。相對NNDA，其判別投影僅需通過求解一廣義特征值方程即可獲得解析解，不僅快速而且學習性能優(yōu)良，因而受到廣泛關注和應用，該工作目前的引用數已超2 240次。

然而傳統(tǒng)的KLDA在學習過程中存在數據的可伸縮性問題[13]，當數據量增加到一定規(guī)模后，算法所學得的判別方向復雜度與訓練樣本數成線性增長，這在常規(guī)計算資源上已難以勝任相應的學習。相比KLDA的這種復雜性，本文所提出的ENDA算法本身只線性于隱節(jié)點數,而獨立于訓練樣本數，在現實應用中，隱節(jié)點數通常比訓練樣本數要小很多。因此，當實驗數據規(guī)模變大時，在保證分類性能的前提下，ENDA計算成本比KLDA更小。另一方面，近年來的眾多研究表明[14]，對傳統(tǒng)NN(如卷積網絡)的深化學習能大大提升圖像分類[8]、語音識別[15]和自然語言處理[16]等的識別性能，由此也促發(fā)了對NNDA向深度化學習[17]的研究，在對NNDA的跟蹤研究發(fā)現，此類研究主要有兩大趨勢:(1)網絡變大變深的深度學習;(2)限于常規(guī)計算資源的加速化(例如典型ELM)極速學習。然而深度學習的成功往往需付出高昂的代價，是因為:(1)深度學習需要學習大量參數，樣本少了很易“過擬合”，數據大小成為其性能提升的關鍵[18]；(2)模型復雜化需要龐大的計算資源和巨大的時間開銷。而“沒有免費午餐定理”告訴人們：算法的優(yōu)劣必須針對具體的學習任務,其有效性必須考慮“偏好”問題，結果是:(1)時間開銷大和計算資源缺乏，即難以在常規(guī)計算資源下完成深度學習；(2)所需要的大數據的標記涉及昂貴的人力和物力等問題。 綜上所述，當數據規(guī)模達不到深度學習要求的情況下(在機器學習UCI儲存數據庫公布的348個數據集當中，296個數據集的主要樣本例數集中在50 000個以下，約占85%)，如何在常用PC計算資源下進行更有效的學習變得更有意義和更加緊迫，所以筆者更偏重于NN加速化的研究。在保證分類性能的前提下，ENDA能迅速處理這類常規(guī)數據的分類任務，與傳統(tǒng)NNDA不同是因為其利用了快速、可靠的隨機映射。

最新研究表明[19]使用隨機投影的簡單NN與人類學習具有很大相關性和相似魯棒性。因此也為10年前采用此原理的極速學習機(Extreme learning machine，ELM)提供了認知原理上的解釋，盡管ELM被提出以來得到了廣泛關注，并已在特征學習、分類、回歸和聚類[20]等方面獲得了一系列拓展，但就筆者所知，還未有對NNDA相應的ELM改造。本文基于這一事實，對NNDA進行極速化，構建出一種極速非線性判別分析方法(Extreme nonlinear discriminant analysis，ENDA)，使其兼具NNDA的萬能逼近能力和KLDA能解析獲得全局最優(yōu)解的快速性。最后在UCI機器學習庫真實數據集上進行實驗，結果顯示ENDA比KLDA和NNDA具有更優(yōu)的分類性能。

1 極速學習機模型

極限學習機ELM[21]是一種特殊單隱層前向神經網絡(Single-hidden layer feedforward neural networks，SLFN)，由Huang等人于2004年提出，目前已獲得了1 180多次引用。不同于SLFN傳統(tǒng)梯度下降學習算法，ELM隨機產生輸入層到隱層權重和偏置，克服SLFN反復迭代計算導致的收斂慢、且不能保證全局最優(yōu)解等問題。在優(yōu)化隱節(jié)點和輸出節(jié)點的權重上，ELM采用正則化最小二乘法快速求得閉合解[22]。ELM由輸入層，隱層和輸出層3層網絡組成，其中隱節(jié)點常用非線性激活函數。典型的非線性激活函數包括Sigmoid函數、高斯函數和徑向基函數。不失一般性，這里采用式(1)中的Sigmoid函數作為隱層神經元的激活函數

(1)

ELM不僅有速度上優(yōu)勢，更重要的是理論上也證明了其具有與SLFN同樣的對非線性分段連續(xù)函數的萬能逼近能力[23]。其學習過程可視為兩步：(1)確定網絡NN隱層的神經元數，隨機設置輸入權重和偏差；(2)確定網絡權重。在特征空間中通過使訓練誤差平方和最小解析求得輸出權重的最小范數解，達到優(yōu)化輸出權重的目的。ELM除了快速外還能實現對不同類型數據的分析，并已漸漸成為一種新型的快速學習范式。

(2)

(3)

(4)

(5)

式中βi=[βi1,βi2,…,βim]T為輸出權重。因此最終優(yōu)化問題式(4)可重寫為

(6)

(7)

式中I為單位矩陣。利用式(7)可快速計算B[22]。ELM從理論和經驗上獲得了性能保證[24]。借助其思想，擬對由Mao和Jain所提出的NNDA進行極速化改造，建立ENDA模型。

2 極速非線性判別分析網絡

Mao等人的NNDA屬于淺層網絡，其目標是學習非線性降維，但其遺傳了SLFN的訓練慢、易陷于局部最優(yōu)的缺點。同時基于深度學習思想實現的多層ELM[25-26]，能夠實現對海量數據的建模，盡管能獲得比深度網絡相對快的訓練，但對本文所要處理的數據規(guī)模仍顯得“大材小用”，偏離了傳統(tǒng)ELM簡單易解的特性。本文目的在于極速化NNDA ,使ENDA在常規(guī)計算設施上能處理比NNDA更大規(guī)模的數據集，同時繼承了ELM能解析求解的優(yōu)點。ENDA網絡結構如圖1所示,具體分兩步:(1)隨機生成NN的輸入層連接權重和偏置，構成了一個隨機映射，結果使模型具有簡單快速性;(2)視隱層輸出為新形成的訓練數據，用LDA準則優(yōu)化進輸出層連接權重，同時可用于可視化。同ELM求解一樣，不僅無局部最小，并且能快速解析求得全局閉合最優(yōu)解，最后形成一個新的判別特征空間，而后用所獲特征對目標進行分類。由于采用了隨機非線性變換和后續(xù)的判別優(yōu)化，使ENDA對數據有著自適應性和期望的分類性能。

圖1 ENDA網絡結構圖Fig.1 Structure of ENDA Network

(8)

(9)

(10)

(11)

(12)

然后對其進行判別分析求解，最大化J(W)等價于求解如下廣義特征問題,即

SbW=λSwW

(13)

算法1ENDA算法

步驟2計算ENDA的隱層輸出hi(通過式(2))；

3 仿真及性能分析

3.1 設置

實驗環(huán)境如下：MATLAB2013a，Intel(R) CoreTMi5-3470 CPU @3.20 GHz，16.0 GB內存，64位Win10操作系統(tǒng)。 如表1所示，實驗所用數據為UCI(http://archive.ics.uci.edu/ml/)數據集。實驗前需對數據進行了歸一化，然后將處理后的數據作為ENDA的輸入進行訓練。為了驗證模型的有效性，將ENDA算法與NNDA,KLDA,ELM算法進行了比較分析，為公平起見，NNDA,ELM與ENDA的隱層節(jié)點參數相同，統(tǒng)一使用K近鄰算法(K-Nearest Neighbor)，分別對NNDA,KLDA和ENDA進行分類。實驗過程中參數K采用10折交叉驗證。

表1 UCI數據集

3.2 可視化

為驗證ENDA模型的非線性特征學習能力，實驗中隨機抽取UCI的4組數據集通過模型投影到二維空間進行可視化，結果如圖2～5所示。

圖2 Wine數據集的可視化Fig.2 Wine dataset visualized by three algorithms

圖3 Segment數據集的可視化Fig.3 Segment dataset visualized by three algorithms

圖4 Waveform3數據集的可視化Fig.4 Waveform3 dataset visualized by three algorithms

圖5 Pen-Digits數據集的可視化Fig.5 Pen-Digits dataset visualized by three algorithms

由圖2～5可以觀察到樣本分別經過NNDA，ENDA和KLDA方法投影二維投影空間后的效果:數據經過投影之后都具有最大的分離度，其中ENDA和KLDA投影分類效果更直觀有效。同時實驗結果表明對數據線性不可分問題，非線性變換是一個強大的方法。

在隱節(jié)點參數設置相同情況下，NNDA不僅花費的訓練時間更長，而且投影出來效果分離程度并不明顯，如圖4，5所示，其原因有:(1)NNDA最后隱層到輸出層訓練權重并沒有充分利用；(2)NNDA為避免扭曲嚴重，以線性函數替代Sigmoid函數。在圖4，5中，隨著數據規(guī)模和特征屬性逐漸復雜情況下，ENDA，KLDA比NNDA分類投影后數據分開，抽取特征更明顯。ENDA與KLDA投影效果差別不大，但KLDA的不足表現在對數據集規(guī)模較大樣本，計算時間和空間復雜度變大。綜上所述ENDA可作為一種極速且穩(wěn)定的可視化工具，其原理簡單直觀，通過可視化可以更加了解數據的內在特性，同時在判別分析時提取最大特征，不僅降低數據中的不相關和冗余信息，同時有利于數據的后續(xù)分類。

3.3 性能分析

對KLDA，NNDA，ELM和ENDA這4種相關算法進行實驗對比，NNDA，ELM和ENDA隱層節(jié)點設置為相同參數，采用統(tǒng)計測試集數據分類的錯誤率和時間進行對比分析。實驗結果為10次測試結果平均值和標準差，如表2所示。其中錯誤率公式為

表2 錯誤率和耗時比較

表2中*代表溢出,性能較好結果用粗體標出。雖然ELM是4種方法里最快速的，但ENDA的分類性能相比ELM得到很大提升。從綜合情況看，當數據規(guī)模逐漸變大的情況下，ENDA算法始終表現出較好分類精度和快速性。分析原因如下：(1)實驗中發(fā)現NNDA需要訓練多層神經網絡權重和偏置，導致學習效率低、開銷大； NNDA雙隱層網絡結構致使參數增多，而ENDA通過隨機映射簡化了模型結構，只需要優(yōu)化LDA層權重，就可以達到比NNDA更好的效果。(2)NNDA不僅時間花費巨大，而性能并沒有得到改善，從表2中ENDA和NNDA分類結果可以看出，ENDA性能更優(yōu)。由于NNDA在最后一個隱層到輸出層訓練出的權重并沒發(fā)揮訓練作用，而且NNDA為了防止變形嚴重用線性函數替代了Sigmoid函數，導致學習效果不理想。

從表2中耗時結果可看出，ENDA比KLDA計算更快速。隨著數據集規(guī)模增大，除了Wine數據集外，ENDA的表現明顯，準確性更高。這是因為KLDA隱節(jié)點數與訓練樣本數呈線性關系(計算復雜度為N3),需要計算N×N大小的核矩陣，而ENDA只與隱節(jié)點數的大小呈線性關系，只需計算N×L大小的核矩陣，而隱節(jié)點參數L通常遠小于N，當數據規(guī)模變大時，KLDA計算成本較高甚至溢出，而ENDA則表現出更好的可伸縮性。

綜上所述，ENDA比NNDA，KLDA更具有極速性，這充分表明隨機映射在不影響分類性能前提下大幅度降低了NN的復雜性。與KLDA不同的是，ENDA，NNDA，ELM都充分發(fā)揮了NN的萬能逼近能力，而ENDA不僅強化了隨機映射，而且能保證全局最優(yōu)解析解，使學習更加迅速和魯棒。

4 結束語

本文探討了LDA三種非線性化方法。受隨機映射啟發(fā)，將NNDA進行改造，提出ENDA算法，避免了NNDA需要迭代的調整權重和易陷入局部最優(yōu)等問題，并且具有KLDA的全局最優(yōu)特性，同時又避免了KLDA對樣本依賴的影響，使其更具極速性和魯棒性。

由于ENDA隨機設置權重和偏置帶來的不穩(wěn)定性，很容易聯想到集成的學習方法，利用對樣本數據進行重采樣技術[27-28]加強分類器泛化性能，對于同質或異質個體學習器集成學習，可使整個模型決策更加智能化。通常對產生的個體學習器進行集成的學習算法涉及稀疏修剪或多樣性的度量相關[29]。多樣性度量能確保信息完整性，而稀疏化建立原則是在不使用更多的個體學習器的情況下就能達到剪枝的目的。Yin等人[30]提出同時結合稀疏正則化和多樣性度量這兩種方法用于凸二次規(guī)劃求解，極大地改進了集成泛化性能，并有利于大規(guī)模數據的并行分布式表示[31-32]，具有很好的擴展性，這將是下一步研究內容。

參考文獻:

[1] 杜海順, 張平, 張帆. 一種基于雙向 2DMSD 的人臉識別方法[J]. 數據采集與處理, 2010, 25(3): 369-372.

Du Haishun, Zhang Ping, Zhang Fan. Face recognition method based on bidirectional two-dimensional maximum scatter difference[J].Journal of Data Acquisition and Processing, 2010, 25(3): 369-372.

[2] 牛璐璐, 陳松燦, 俞璐. 線性判別分析中兩種空間信息嵌入方法之比較[J]. 計算機科學, 2014, 41(2): 49-54.

Niu Lulu, Chen Songcan, Yu Lu． Comparison between two approaches of embedding spatial information into linear discriminant analysis[J]. Computer Science, 2014, 41(2): 49-54.

[3] Zhang X Y, Huang K, Liu C L. Feature transformation with class conditional decorrelation[C]//2013 IEEE 13th International Conference on Data Mining. Dallas, Texas:IEEE,2013：887-896.

[4] Izenman A J. Linear discriminant analysis[M].New York：Springer, 2013: 237-280.

[5] Baudat G, Anouar F. Generalized discriminant analysis using a kernel approach[J]. Neural Computation, 2000, 12(10): 2385-2404.

[6] Wang R, Chen X. Manifold discriminant analysis[C]// IEEE Conference on Computer Vision and Pattern Recognition, 2009, CVPR 2009. Anchorage, Alaska: IEEE, 2009: 429-436.

[7] Stuhlsatz A, Lippel J, Zielke T. Feature extraction with deep neural networks by a generalized discriminant analysis[J]. Neural Networks and Learning Systems, IEEE Transactions on, 2012, 23(4): 596-608.

[8] Lecun Y, Bengio Y, Hinton G. Deep learning[J]. Nature, 2015, 521(7553): 436-444.

[9] Wu L, Shen C, Hengel A V D. Deep linear discriminant analysis on fisher networks: A hybrid architecture for person reidentification[J]. Pattem Recognition, 2016,65:238-250.

[10] Mao J, Jain A K. Artificial neural networks for feature extraction and multivariate data projection[J]. Neural Networks, IEEE Transactions on, 1995, 6(2): 296-317.

[11] Hassoun M H. 1996 IEEE transactions on neural networks outstanding paper award[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1996(4): 802-802.

[12] Scholkopft B, Mullert K R. Fisher discriminant analysis with kernels[J]. Neural Networks for Signal Processing IX, 1999,1:1.

[13] Cai D, He X, Han J. Speed up kernel discriminant analysis[J]. The VLDB Journal, 2011, 20(1): 21-33.

[14] Sermanet P, Eigen D, Zhang X, et al. Overfeat: Integrated recognition, localization and detection using convolutional networks[J]. arXiv Preprint arXiv, 2013:1312.6229.

[15] Hinton G, Deng L, Yu D, et al. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups[J].IEEE Signal Processing Magazine, 2012, 29(6): 82-97.

[16] Collobert R, Weston J, Bottou L, et al. Natural language processing (almost) from scratch[J]. The Journal of Machine Learning Research, 2011, 12: 2493-2537.

[17] Huang G B, Wang D H, Lan Y. Extreme learning machines:A survey[J]. International Journal of Machine Learning and Cybernetics, 2011, 2(2): 107-122.

[18] Hu G, Peng X, Yang Y, et al. Frankenstein: Learning deep face representations using small data[J]. IEEE Trans Image Process,2017,27(1):293-303.

[19] Arriaga R I, Rutter D, Cakmak M, et al. Visual categorization with random projection[J]. Neural Computation, 2015, 27(10): 2132.

[20] 劉金勇, 鄭恩輝, 陸慧娟. 基于聚類和微粒群優(yōu)化的基因選擇方法[J]. 數據采集與處理, 2014, 29(1):83-89.

Liu Jinyong, Zheng Enhui, Lu Huijuan. Gene selection based on clustering method and particle swarm optimazition[J].Journal of Data Acquisition and Processing, 2014, 29(1):83-89.

[21] Huang G B, Zhu Q Y, Siew C K. Extreme learning machine: A new learning scheme of feedforward neural networks[C]∥Proc IJCNN．Budapest, Hungary：[s.n.],2004(2):985-990.

[22] Tang J, Deng C, Huang G B. Extreme learning machine for multilayer perceptron[J]. IEEE Transactions on Neural Networks and Learning Systems, 2016, 27(4): 809-821.

[23] Huang G B, Zhu Q Y, Siew C K. Extreme learning machine: Theory and applications[J]. Neurocomputing, 2006, 70(1): 489-501.

[24] Huang G B. What are extreme learning machines? Filling the gap between frank rosenblatt′s dream and John von neumann′s puzzle[J]. Cognitive Computation, 2015, 7(3): 263-278.

[25] Tang J, Deng C, Huang G B. Extreme learning machine for multilayer perceptron[J]. IEEE Transactions on Neural Networks & Learning Systems, 2016, 27(4):809-821.

[26] Kasun L L C, Zhou H, Huang G B, et al. Representational learning with ELMs for big data[J]. IEEE Intelligent Systems, 2013, 28(6): 31-34.

[27] Breiman L. Bagging predictors[J]. Machine Learning, 1996, 24(2): 123-140.

[28] Schapire R E, Freund Y, Bartlett P, et al. Boosting the margin: A new explanation for the effectiveness of voting methods[J]. The Annals of Statistics, 1998, 26(5): 1651-1686.

[29] Kuncheva L I, Whitaker C J. Measures of diversity in classifier ensembles and their relationship with the ensemble accuracy[J]. Machine Learning, 2003, 51(2): 181-207.

[30] Yin X C, Huang K, Yang C, et al. Convex ensemble learning with sparsity and diversity[J]. Information Fusion, 2014, 20: 49-59.

[31] Wang H, He Q, Shang T, et al. Extreme learning machine ensemble classifier for large-scale data[C]//Proceedings of ELM-2014. Singapore: Springer International Publishing, 2015: 151-161.

[32] Van Heeswijk M, Miche Y, Oja E, et al. GPU-accelerated and parallelized ELM ensembles for large-scale regression[J]. Neurocomputing, 2011, 74(16): 2430-2437.