基于KKT條件的稀疏編碼算法收斂性研究

陶盈吟 楊儀 代祥光 蘇曉杰

摘要

本文提出了基于KKT條件的稀疏編碼算法.首先，將非凸非光滑的稀疏編碼問題分解成兩個凸非光滑問題;然后，巧妙地運用兩個矩陣使兩個凸非光滑問題轉(zhuǎn)換成三個光滑凸優(yōu)化問題，并通過KKT條件對三個問題進行求解，再通過凸優(yōu)化理論證明三個問題在其對應(yīng)規(guī)則下是非增的.最后，實驗結(jié)果驗證了算法的收斂性.關(guān)鍵詞

KKT條件;收斂性;非凸非光滑;稀疏編碼

中圖分類號 O232

文獻標(biāo)志碼 A

0 引言

稀疏編碼是一種無監(jiān)督學(xué)習(xí)方法，即從輸入樣本數(shù)據(jù)中學(xué)習(xí)一系列基，這些基非常符合人類的視覺感知[1-2].當(dāng)基的維度遠高于原始數(shù)據(jù)的維度，那么稀疏編碼可以理解為超完備基學(xué)習(xí)方法;當(dāng)基的維度遠低于輸入樣本的維度，稀疏編碼可以理解為數(shù)據(jù)降維學(xué)習(xí)方法.由于稀疏編碼的多重特性，它經(jīng)常被應(yīng)用于模式識別、聚類和信號處理[3-8]等.

3 實驗結(jié)果

本文算法（KKTSC）將與算法Feature-sgin[10]和MexLasso[11]在收斂性和基學(xué)習(xí)做分析比較.本文使用人臉數(shù)據(jù)集Olivetti Research Laboratory（ORL）來驗證收斂性和基學(xué)習(xí)有效性.ORL人臉數(shù)據(jù)集由英國劍橋Olivetti實驗室拍攝的一系列人臉圖像組成，共計40個不同性別、種族和年齡的對象.每個對象有10幅像素為92×112的灰度圖像.人臉細節(jié)和表情均有不同，比如睜眼或閉眼、是否戴眼鏡、笑或不笑、有無淡光、不同的人臉姿態(tài)和人臉尺寸等.

三種算法將在ORL上做收斂性分析比較.選擇分解因子r分別為100，500，1 000，其中收斂性比較結(jié)果如表1所示.當(dāng)分解因子r較小時（比如r為100，500），三種算法都可以在有限時間得到目標(biāo)函數(shù)值，MexLasso可以在短時間獲得目標(biāo)函數(shù)值.當(dāng)分解因子r=1 000，僅KKTSC和MexLasso可以在有限時間得到目標(biāo)函數(shù)值，F(xiàn)eature-sign無法在有限時間獲得目標(biāo)函數(shù)值.綜上所述，KKTSC隨著數(shù)據(jù)維度增加，其收斂速度比另兩種算法更快.

由于MexLasso在高維數(shù)據(jù)中收斂性較慢，這里只考慮將KKTSC和Feature-sign做超完備基學(xué)習(xí).設(shè)置迭代次數(shù)為50次，圖1給出了完備基學(xué)習(xí)結(jié)果.根據(jù)圖1，兩種算法都可以完成超完備基的學(xué)習(xí).然而，KKTSC只需要24 min完成超完備基的學(xué)習(xí)，而Feature-sign則需要58 min完成超完備基的學(xué)習(xí).

4 結(jié)束語

本文將稀疏編碼問題分解成三個凸優(yōu)化問題，然后通過KKT給定其迭代規(guī)則.通過凸優(yōu)化理論證明三個凸優(yōu)化問題在其對應(yīng)規(guī)則下是非增的.最后，通過ORL數(shù)據(jù)集驗證了所提出算法具有快速學(xué)習(xí)超完備基的能力.

參考文獻

References

[1]

Olshausen B A，F(xiàn)ield D J.Emergence of simple-cell receptive field properties by learning a sparse code for natural images[J].Nature，1996，381（6583）：607-609

[2] Olshausen B A，F(xiàn)ield D J.Sparse coding with an overcomplete basis set：a strategy employed by V1？[J].Vision Research，1997，37（23）：3311-3325

[3] Labusch K，Barth E，Martinetz T.Simple method for high-performance digit recognition based on sparse coding[J].IEEE Trans Neural Netw，2008，19（11）：1985-1989

[4] He B，Xu D，Rui N，et al.Fast face recognition via sparse coding and extreme learning machine[J].Cognitive Computation，2014，6（2）：264-277

[5] Zheng M，Bu J J，Chen C，et al.Graph regularized sparse coding for image representation[J].IEEE Transactions on Image Processing：a Publication of the IEEE Signal Processing Society，2011，20（5）：1327-1336

[6] Shu Z Q，Zhao C X，Huang P.Constrained sparse concept coding algorithm with application to image representation[J].KSII Transactions on Internet and Information Systems，2014，8（9）：3211-3230

[7] L?rincz A，Palotai Z，Szirtes G.Efficient sparse coding in early sensory processing：lessons from signal recovery[J].PLoS Computational Biology，2012，8（3）：e1002372

[8] Zhao Y X，Liu Z Y，Wang Y Y，et al.Sparse coding algorithm with negentropy and weighted 1-norm for signal reconstruction[J].Entropy，2017，19（11）：599

[9] Bertsekas D P.Nonlinear programming[J].Journal of the Operational Research Society，1997，48：332-334

[10] Lee H，Battle A，Raina R，et al.Efficient sparse coding algorithms[J].Proc of Nips，2007，19：801-808

[11] Mairal J，Bach F，Ponce J，et al.Online learning for matrix factorization and sparse coding[J].Journal of Machine Learning Research，2009，11：19-60

Convergence of sparse coding based on KKT conditions

TAO Yingyin1 YANG Yi1 DAI Xiangguang1 SU Xiaojie2

1 Key Laboratory of Intelligent Information Processing and Control of Chongqing Municipal Institutions

of Higher Education，Chongqing Three Gorges University，Chongqing 404100

2 College of Automation，Chongqing University，Chongqing 400044

Abstract This paper proposes a sparse coding algorithm based on KKT conditions.Firstly，the non-convex non-smooth sparse coding problem is decomposed into two convex non-smooth problems.Secondly，the two convex non-smooth problems are skillfully transformed into three smooth convex optimization problems by using two matrices.Finally，the three problems are solved by KKT conditions.In addition，we prove the convergence of the algorithm.Meanwhile，experimental simulation shows the convergence of the algorithm.

Key words KKT conditions;convergence;non-convex non-mooth;sparse coding

收稿日期 2020-02-26

資助項目 重慶市高校市級重點實驗室資助項目（[2017]3）;重慶市發(fā)展和改革委員會資助項目（2017[1007]）;重慶市教委科技研究項目（KJQN201901203，KJQN201901218，KJ1710248）;重慶市自然科學(xué)基金 （cstc2019jcyj-bshX0101）

作者簡介陶盈吟，女，碩士生，研究方向為優(yōu)化算法、機器學(xué)習(xí).597370352@qq.com

楊儀（通信作者），女，博士，研究方向為神經(jīng)網(wǎng)絡(luò)、非線性動力系統(tǒng).yang1595@126.com