判決性字典學(xué)習(xí)方法綜述

薄純娟，宋 鵬，林 怡

(大連民族大學(xué) 機(jī)電工程學(xué)院，遼寧 大連 116605)

判決性字典學(xué)習(xí)方法綜述

薄純娟，宋 鵬，林 怡

(大連民族大學(xué) 機(jī)電工程學(xué)院，遼寧 大連 116605)

為了解決在基于稀疏表示的分類(lèi)算法中,傳統(tǒng)字典學(xué)習(xí)框架下學(xué)習(xí)得到的字典僅可用于信號(hào)重構(gòu)而并不針對(duì)分類(lèi)的問(wèn)題，分析和總結(jié)了具有代表性的面向分類(lèi)的字典學(xué)習(xí)算法，也稱(chēng)判決性字典學(xué)習(xí)。判決性字典學(xué)習(xí)算法總體上分為兩類(lèi)：直接使得字典具有判決性和使得表示系數(shù)具有判決性。對(duì)兩類(lèi)方法進(jìn)行分析和總結(jié)可為本領(lǐng)域算法的發(fā)展提供參考，并引起更多研究。

字典學(xué)習(xí)；判決性字典；稀疏表示；分類(lèi)

Abstract:Dictionaries learned from the traditional dictionary learning framework can only be used for signal reconstruction, but not for classification problems. In order to solve this problem in the classification algorithms based on sparse representation, we summarize and analyze typical dictionary learning algorithms for classification, also called discriminative dictionary learning. To be specific, we can roughly divide the discriminative dictionary learning methods into two categories: directly making the dictionary be discriminative and making the representation coefficients be discriminative. The analysis and summary in this paper will provide references for the development of algorithms in this field, and lead to further researches.

Keywords:dictionary learning; discriminative dictionary; sparse representation; classification

近年來(lái)，隨著稀疏表示的興起和廣泛應(yīng)用，字典學(xué)習(xí)(Dictionary Learning，DL)已成為當(dāng)前熱點(diǎn)研究問(wèn)題之一。一般來(lái)說(shuō)，字典學(xué)習(xí)旨在建立稀疏表示模型求解所需的字典，使得字典能夠更好地表示測(cè)試樣本。字典學(xué)習(xí)方法來(lái)源于壓縮感知理論，最初用來(lái)在稀疏約束條件下學(xué)習(xí)一個(gè)自適應(yīng)的字典來(lái)更好地表示信號(hào)。，諸多學(xué)者將字典學(xué)習(xí)框架應(yīng)用于圖像去噪、圖像修復(fù)[1]、模式聚類(lèi)[2]、樣本分類(lèi)等領(lǐng)域，并取得了較好的效果。

傳統(tǒng)字典學(xué)習(xí)框架下學(xué)習(xí)得到的字典僅可用于信號(hào)重構(gòu)而并不針對(duì)分類(lèi)問(wèn)題，因此一些學(xué)者嘗試從監(jiān)督學(xué)習(xí)和類(lèi)別信息挖掘等方面出發(fā)，研究面向分類(lèi)的字典學(xué)習(xí)方法，也稱(chēng)為判決性字典學(xué)習(xí)方法。本文分析了兩類(lèi)代表性的判決性字典學(xué)習(xí)方法：(1)直接使得字典具有判決性：從不同類(lèi)別字典間信息差異的角度出發(fā)直接設(shè)計(jì)判決性字典學(xué)習(xí)方法，并利用重構(gòu)誤差準(zhǔn)則實(shí)現(xiàn)分類(lèi)。典型代表算法包括：中間臉學(xué)習(xí)[3](Meta-face Learning)和結(jié)構(gòu)不相關(guān)字典學(xué)習(xí)[4](Dictionary Learning with Structured Incoherence)等；(2)使得表示系數(shù)具有判決性：通過(guò)同時(shí)學(xué)習(xí)字典和分類(lèi)器的方式來(lái)使得表示稀疏具有判決性，從而增強(qiáng)字典的判決能力。與第一種方法不同，該類(lèi)方法利用稀疏表示系數(shù)作為新的特征進(jìn)行分類(lèi)，包括監(jiān)督字典學(xué)習(xí)(Supervised Dictionary Learning)、標(biāo)簽一致K-SVD算法[5](Label consistence K-SVD)、判決性K-SVD算法[6](Discriminative K-SVD)、Fisher判決字典學(xué)習(xí)[7](Fisher discrimination Dictionary Learning)等。

1 分類(lèi)方法與學(xué)習(xí)框架

1.1 基于稀疏表示的分類(lèi)方法

2009年，Wright等人[8]提出了基于稀疏表示的分類(lèi)方法用于人臉識(shí)別，取得了魯棒的識(shí)別效果。假設(shè)有C類(lèi)人臉，令D=[X1,…,Xc,…,XC]∈Rd×N為初始訓(xùn)練樣本集，其中Xc∈Rd×Nc為子集(包含來(lái)自第c類(lèi)的所有Nc個(gè)訓(xùn)練樣本)。該稀疏表示分類(lèi)算法將原始數(shù)據(jù)集作為整個(gè)字典，用x∈Rd表示一個(gè)待分類(lèi)的人臉圖像，則基于稀疏表示的分類(lèi)方法識(shí)別x需要以下兩個(gè)步驟：

1.通過(guò)求解L1范數(shù)最小化問(wèn)題來(lái)獲得關(guān)于向量x的稀疏編碼，

(1)

式中，λ為標(biāo)量常數(shù)。

2.利用類(lèi)特征重構(gòu)誤差原則推理人臉x的類(lèi)別歸屬，

(2)

式中，δi(·)是一個(gè)矢量指示函數(shù)，提取對(duì)應(yīng)的第i類(lèi)原子。

該方法在人臉識(shí)別上取得了很好的效果，尤其對(duì)于噪聲(如遮擋、光照等)非常魯棒，雖然該方法在分類(lèi)中沒(méi)有學(xué)習(xí)字典，但它開(kāi)創(chuàng)了利用稀疏編碼進(jìn)行分類(lèi)的先河。從字典學(xué)習(xí)角度，傳統(tǒng)基于稀疏表示的分類(lèi)方法僅僅使用所有訓(xùn)練樣本作為字典，用特定類(lèi)別的訓(xùn)練集作為子字典以保持判決性。

1.2 字典學(xué)習(xí)框架

字典學(xué)習(xí)的目標(biāo)是自適應(yīng)地建立一個(gè)向量庫(kù)，使得新的信號(hào)可以由其中幾個(gè)向量線(xiàn)性組合表示。假設(shè)有一組信號(hào)X=[x1,…,xi,…,XN]，其中xi是第i個(gè)信號(hào)。傳統(tǒng)的字典學(xué)習(xí)框架下學(xué)習(xí)字典的目標(biāo)函數(shù)為：

(3)

雖然經(jīng)典的字典學(xué)習(xí)框架在一些研究中實(shí)現(xiàn)了很好的分類(lèi)效果，但該框架最初被設(shè)計(jì)用來(lái)重構(gòu)而不是分類(lèi)，因此有針對(duì)性地學(xué)習(xí)更適合分類(lèi)的字典，能夠進(jìn)一步提升分類(lèi)性能。

2 兩類(lèi)方法介紹

2.1 直接使得字典具有判決性方法

該類(lèi)方法利用重構(gòu)誤差來(lái)做最后的分類(lèi)，因此學(xué)習(xí)的字典應(yīng)具有判決性。受到基于稀疏表示的分類(lèi)方法的啟發(fā)，楊等人提出了中間臉學(xué)習(xí)方法，該方法對(duì)每類(lèi)學(xué)習(xí)一個(gè)自適應(yīng)的字典，受到該方法的啟發(fā)，Ramirez等在目標(biāo)函數(shù)中添加了一個(gè)復(fù)雜項(xiàng)使得面向分類(lèi)的字典更具體。

2.1.1 中間臉學(xué)習(xí)

傳統(tǒng)基于稀疏表示的分類(lèi)方法直接采用原始的人臉圖像作為字典，然而使用預(yù)先定義的字典將產(chǎn)生與累積冗余噪音和瑣碎信息，從而降低人臉的識(shí)別率。此外，隨著訓(xùn)練樣本的增加，稀疏表示的計(jì)算量也不斷增大，成為主要瓶頸。針對(duì)這一問(wèn)題，楊等提出了一種中間臉學(xué)習(xí)方法對(duì)每一類(lèi)學(xué)習(xí)特定的字典：

(4)

2.1.2 利用結(jié)構(gòu)相關(guān)性的字典學(xué)習(xí)

Ramirez等發(fā)現(xiàn)學(xué)習(xí)的子字典可能具有一些共性，例如某些來(lái)自不同子字典的原子可能非常相關(guān)。原子之間的相關(guān)性使得在重構(gòu)測(cè)試樣本的過(guò)程中存在不穩(wěn)定性，進(jìn)而導(dǎo)致基于類(lèi)特定重構(gòu)誤差的分類(lèi)機(jī)制出錯(cuò)。針對(duì)該問(wèn)題，增加一個(gè)相關(guān)項(xiàng)來(lái)約束字典，使得不同類(lèi)的字典盡可能不相關(guān)。

(5)

2.2 使得表示系數(shù)具有判決性方法

第二類(lèi)方法與第一類(lèi)方法的區(qū)別在于判別方法。與第一類(lèi)方法相比，第二類(lèi)強(qiáng)制稀疏系數(shù)也具有判決性，間接增強(qiáng)整個(gè)字典的判決能力。第一類(lèi)方法需要對(duì)每類(lèi)分別學(xué)習(xí)字典，而第二類(lèi)方法只需要學(xué)習(xí)整個(gè)字典。

2.2.1 監(jiān)督字典學(xué)習(xí)

Mairal等提出監(jiān)督字典學(xué)習(xí)方法，將邏輯斯蒂回歸與傳統(tǒng)的字典學(xué)習(xí)框架相結(jié)合的工作如下：

(6)

式中，L(·)是邏輯損失函數(shù)(C(x)=log(1+e-x))，它與支持向量機(jī)中的嶺損失函數(shù)具有相似的屬性，不同的是L(·)可微，λ2是正則化參數(shù)[9]，用于防止過(guò)度擬合。若f是一個(gè)線(xiàn)性分類(lèi)函數(shù)，則f(x,a,θ)=θTa+b，其中θ∈RK；若a和x雙線(xiàn)性，則f(x,a,θ)=xTWa+b，其中θ={W∈Rd×K,b∈R}。

2.2.2 判決性K-SVD字典學(xué)習(xí)方法

張和李提出判決性K-SVD方法，實(shí)現(xiàn)了理想字典同時(shí)具有好的表示能力并支持最優(yōu)判決分類(lèi)。D-KSVD在傳統(tǒng)的DL框架下增加了一個(gè)簡(jiǎn)單的線(xiàn)性回歸項(xiàng)作為懲罰項(xiàng)：

(7)

式中，H=[h1,…,hN]∈RC×N是訓(xùn)練圖像的標(biāo)簽，hn=[0,…,0,1,0,…,0]是每類(lèi)中非零元素的位置。W是分類(lèi)器的參數(shù)，λ1、λ2和λ3是控制對(duì)應(yīng)項(xiàng)的相對(duì)貢獻(xiàn)常數(shù)。

2.2.3 標(biāo)簽一致性K- SVD

Jiang等提出了標(biāo)簽一致性K-SVD方法來(lái)學(xué)習(xí)一個(gè)判決性字典進(jìn)行稀疏編碼。該方法引入一個(gè)“判決性稀疏編碼誤差”的標(biāo)簽一致性約束，并與重構(gòu)誤差和分類(lèi)誤差組合形成統(tǒng)一的目標(biāo)函數(shù)：

(8)

2.2.4 Fisher判決字典學(xué)習(xí)

Yang等基于Fisher判決準(zhǔn)則提出了Fisher判決字典學(xué)習(xí)方法，學(xué)習(xí)一個(gè)結(jié)構(gòu)字典，其原子對(duì)應(yīng)于該類(lèi)別的標(biāo)簽。該結(jié)構(gòu)化的字典表示為D=[D1,…,DC]，其中DC是特定第C類(lèi)的子字典。數(shù)據(jù)集表示為X=[X1,…,XC]，其中Xc是子集，第c類(lèi)的訓(xùn)練樣本。通過(guò)求解以下方程，獲得字典和系數(shù)得到理想的判決性字典：

(9)

(10)

判決性系數(shù)項(xiàng)：要使字典D對(duì)數(shù)據(jù)集X具有判決性，可以使X對(duì)D的編碼系數(shù)A具有判決性?；贔isher準(zhǔn)則，可以通過(guò)最小化A的類(lèi)內(nèi)散布矩陣SW和最大化A的類(lèi)間散布矩陣SB來(lái)實(shí)現(xiàn)。 SW和SB被定義為：

(11)

合并所有項(xiàng)，得到以下Fisher判決性字典學(xué)習(xí)模型：

(12)

該方法用作分類(lèi)時(shí)，仍然利用第一類(lèi)方法中的重構(gòu)誤差實(shí)現(xiàn)。

3 結(jié) 論

本文分析了兩類(lèi)具有代表性的判決性字典學(xué)習(xí)方法。判決性字典學(xué)習(xí)算法在基于稀疏表示的分類(lèi)框架中非常重要和實(shí)用，能夠較為顯著地提升分類(lèi)算法的效果。一種從字典本身角度出發(fā)，使得字典具有判決能力；另一種從表示系數(shù)角度出發(fā)，使得表示系數(shù)具有判決能力，間接使得字典具有判決能力。相比而言，后者更加直觀有效。在綜述和總結(jié)前人工作的基礎(chǔ)上，我們認(rèn)為判決性字典學(xué)習(xí)算法未來(lái)的研究方向會(huì)集中在以下幾方面。一方面，研究人員可以尋求一個(gè)統(tǒng)一的框架來(lái)將兩類(lèi)字典學(xué)習(xí)算法進(jìn)行統(tǒng)一，深入分析各方法對(duì)所學(xué)字典以及分類(lèi)結(jié)果的影響，并在此基礎(chǔ)上針對(duì)特定問(wèn)題設(shè)計(jì)更加有效的字典學(xué)習(xí)算法。另一方面，可以將字典學(xué)習(xí)和度量學(xué)習(xí)相結(jié)合，考慮如何在統(tǒng)一的模型框架下討論如何同時(shí)學(xué)習(xí)字典和度量矩陣的問(wèn)題。此外，字典學(xué)習(xí)算法在處理大數(shù)據(jù)時(shí)的時(shí)間和空間復(fù)雜度都比較高，如何在線(xiàn)學(xué)習(xí)判決性字典也是未來(lái)值得研究的課題之一。

[1] ELADM, FIGUEIREDOM, MAY. On the role of sparse and redundant representations inimage processing[J]. Proceedings of IEEE, 2010, 98(6):972-982.

[2] CHENGB, YANGJ, YANS , et al.Learning with1-graph for image analysis[J].IEEE Trans Img Proc, 2010, 19(4):858-866.

[3] YANGM, ZHANGL, YANGJ, et al.Metaface learning for sparse representation basedface recognition[C].Proceedings - International Conference on Image Processing(ICIP), 2010: 1601-1604.

[4] RAMIREZI, SPRECHMANNP, SAPIROG. Classification and clustering via dictionary learningwith structured incoherence and shared features[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2010: 3501-3508.

[5] JIANGZ, LINZ,DAVIS L S. Learning a discriminative dictionary for sparse coding vialabel consistent k-svd[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition(CVPR), 2011: 1697-1704.

[6] ZHANGQ,LIB. Discriminative k-svd for dictionary learning in face recognition[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2010: 2691-2698.

[7]YANGM,ZHANGL,FENGX,et al. Fisher discrimination dictionary learning for sparserepresentation[C]. Proceedings of the IEEE International Conference on Computer Vision(ICCV), 2011: 543-550.

[8] RAINAR, BATTLEA, LEEH, et al. Self-taught learning: transfer learningfrom unlabeled data[C]. ACM International Conference Proceeding Series (ICML), 2007,227: 759-766.

[9] WRIGHTJ, YANGA, GANESHA,et al. Robust face recognition via sparserepresentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2): 210-227 .

(責(zé)任編輯 趙環(huán)宇)

ReviewonDiscriminativeDictionaryLearningAlgorithms

BOChun-juan,SONGPeng,LINYi

(School of Electromechanical Engineering, Dalian Minzu University, Dalian Liaoning 116605, China)

TP391

A

2017-03-20；

2017-04-14

中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金資助項(xiàng)目(DC201501010401)。

薄純娟(1986-)，女，山東東營(yíng)人，工程師，主要從事圖像處理和模式識(shí)別研究。

2096-1383(2017)05-0466-04