Generalization error bound guided discriminative dictionary learning

doi:10.11772/j.issn.1001-9081.2018081785

Abstract

Abstract: In the process of improving discriminant ability of dictionary, max-margin dictionary learning methods ignore that the generalization of classifiers constructed by reacquired data is not only in relation to the principle of maximum margin, but also related to the radius of Minimum Enclosing Ball (MEB) containing all the data. Aiming at the fact above, Generalization Error Bound Guided discriminative Dictionary Learning (GEBGDL) algorithm was proposed. Firstly, the discriminant condition of Support Vector Guided Dictionary Learning (SVGDL) algorithm was improved based on the upper bound theory of about the generalization error of Support Vector Machine (SVM). Then, the SVM large margin classification principle and MEB radius were used as constraint terms to maximize the margin between different classes of coding vectors, and to minimum the MEB radius containing all coding vectors. Finally, as the generalization of classifier being better considered, the dictionary, coding coefficients and classifiers were updated respectively by alternate optimization strategy, obtaining the classifiers with larger margin between the coding vectors, making the dictionary learn better to improve dictionary discriminant ability. The experiments were carried out on a handwritten digital dataset USPS, face datasets Extended Yale B, AR and ORL, object dataset Caltech 101, COIL20 and COIL100 to discuss the influence of hyperparameters and data dimension on recognition rate. The experimental results show that in most cases, the recognition rate of GEBGDL is higher than that of Label Consistent K-means-based Singular Value Decomposition (LC-KSVD), Locality Constrained and Label Embedding Dictionary Learning (LCLE-DL), Fisher Discriminative Dictionary Learning (FDDL) and SVGDL algorithm, and is also higher than that of Sparse Representation based Classifier (SRC), Collaborative Representation based Classifier (CRC) and SVM.

Key words: dictionary learning, generalization error bound, Support Vector Machine (SVM), Minimum Enclosing Ball (MEB), digital image classification

摘要： 在提高字典鉴别能力的过程中，最大间隔字典学习忽视了利用重新获得的数据构建分类器的泛化性能，不仅与最大间隔原理有关，还与包含数据的最小包含球（MEB）半径有关。针对这一事实，提出泛化误差界指导的鉴别字典学习算法GEBGDL。首先，利用支持向量机（SVM）的泛化误差上界理论对支持向量引导的字典学习算法（SVGDL）的鉴别条件进行改进；然后，利用SVM大间隔分类原理和MEB半径作为鉴别约束项，促使不同类编码向量间的间隔最大化，并减小包含所有编码向量的MEB半径；最后，为了更充分考虑分类器的泛化性能，采用交替优化策略分别更新字典、编码系数和分类器，进而获得编码向量相对间隔更大的分类器，从而促使字典更好地学习，提升字典鉴别能力。在USPS手写数字数据集，Extended Yale B、AR、ORL三个人脸集，Caltech101、COIL20、COIL100物体数据集中进行实验，讨论了超参数和数据维度对识别率的影响。实验结果表明，在七个图像数据集中，多数情况下所提算法的识别率优于类标签一致K奇异值分解（LC-KSVD）、局部特征和类标嵌入约束字典学习（LCLE-DL）算法、Fisher鉴别字典学习（FDDL）和SVGDL等算法；且在七个数据集中，该算法也取得了比基于稀疏表示的分类（SRC）、基于协作表示的分类（CRC）和SVM更高的识别率。

关键词: 字典学习, 泛化误差界, 支持向量机, 最小包含球, 数字图像分类

CLC Number:

TP391.41

XU Tao, WANG Xiaoming. Generalization error bound guided discriminative dictionary learning[J]. Journal of Computer Applications, 2019, 39(4): 940-948.

徐涛, 王晓明. 泛化误差界指导的鉴别字典学习[J]. 计算机应用, 2019, 39(4): 940-948.

References

[1] WANG Z, LIU D, YANG J, et al. Deep networks for image super-resolution with sparse prior[C]//ICCV 2015:Proceedings of the 2015 IEEE International Conference on Computer Vision. Washington, DC:IEEE Computer Society, 2016:370-378.
[2] LUO Y, XU Y, JI H. Removing rain from a single image via discriminative sparse coding[C]//ICCV 2015:Proceedings of the 2015 IEEE International Conference on Computer Vision. Washington, DC:IEEE Computer Society, 2015:3397-3405.
[3] WRIGHT J, YANG A Y, GANESH A, et al. Robust face recognition via sparse representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2):210-227.
[4] LIU Q, LIU C. A novel locally linear KNN model for visual recognition[C]//Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ:IEEE, 2015:1329-1337.
[5] AHARON M, ELAD M, BRUCKSTEIN A. K-SVD:an algorithm for designing overcomplete dictionaries for sparse representation[J]. IEEE Transactions on Signal Processing, 2006, 54(11):4311-4322.
[6] ZHANG Q, LI B. Discriminative K-SVD for dictionary learning in face recognition[C]//Proceedings of the 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington, DC:IEEE Computer Society, 2010:2691-2698.
[7] JIANG Z, LIN Z, DAVIS L S. Label consistent K-SVD:learning a discriminative dictionary for recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(11):2651-2664.
[8] LI Z, LAI Z, XU Y, et al. A locality-constrained and label embedding dictionary learning algorithm for image classification[J]. IEEE Transactions on Neural Networks and Learning Systems, 2017, 28(2):278-293.
[9] YANG M, ZANG L, FENG X, et al. Sparse representation based Fisher discrimination dictionary learning for image classification[J]. International Journal of Computer Vision, 2014, 109(3):209-232.
[10] CAI S, ZUO W, ZHANG L, et al. Support vector guided dictionary learning[C]//ECCV 2014:Proceedings of the 13th European Conference on Computer Vision, LNCS 8692. Berlin:Springer, 2014:624-639.
[11] RIGAMONTI R, BRWON M A, LEPTIT V. Are sparse representations really relevant for image classification?[C]//Proceedings of the CVPR 2011. Washington, DC:IEEE Computer Society, 2011:1545-1552.
[12] ZHANG L, YANG M, FENG X. Sparse representation or collaborative representation:Which helps face recognition?[C]//Proceedings of the 2011 International Conference on Computer Vision. Washington, DC:IEEE Computer Society, 2011:471-478.
[13] MEHTA N A, GRAY A G. Sparsity-based generalization bounds for predictive sparse coding[EB/OL].[2018-05-10]. http://www.jmlr.org/proceedings/papers/v28/mehta13.pdf.
[14] CAI S, ZHANG L, ZUO W, et al. A probabilistic collaborative representation based approach for pattern classification[C]//Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC:IEEE Computer Society, 2016:2950-2959.
[15] PLATT J C. 12 Fast training of support vector machines using sequential minimal optimization[M]//SOENTPIET R. Advances in Kernel Methods:Support Vector Learning. Cambridge, MA:MIT Press, 1999:185-208.
[16] MAIRAL J, BACH F, PONCE J. Task-driven dictionary learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(4):791-804.
[17] RAMIREZ I, SPRECHMANN P, SAPIRO G. Classification and clustering via dictionary learning with structured incoherence and shared features[C]//Proceedings of the 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington, DC:IEEE Computer Society, 2010:3501-3508.
[18] GAO S, TSANG W H, MA Y. Learning category-specific dictionary and shared dictionary for fine-grained image categorization[J]. IEEE Transactions on Image Processing, 2013, 23(2):623-634.
[19] ZHOU N. Learning inter-related visual dictionary for object recognition[J]//Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC:IEEE Computer Society, 2012:3490-3497.
[20] KONG S, WANG D. A dictionary learning approach for classification:separating the particularity and the commonality[C]//ECCV 2012:Proceedings of the 12th European Conference on Computer Vision, LNCS 7572. Berlin:Springer, 2012:186-199.
[21] VAPNIK V, CHAPPLE O. Bounds on error expectation for support vector machines[J]. Neural Computation, 2000, 12(9):2013-2036.
[22] LIAN X C, LI Z, LU B L, et al. Max-margin dictionary learning for multiclass image categorization[C]//ECCV 2010:Proceedings of the 11th European Conference on Computer Vision, LNCS 6314. Berlin:Springer, 2010:157-170.
[23] SCHOLKOPF B, PLATT J, HOFMANN T. Efficient sparse coding algorithms[EB/OL].[2018-05-10]. http://papers.nips.cc/paper/2979-efficient-sparse-coding-algorithms.pdf.
[24] LEE K C, HO J, KRIEGMAN D J. Acquiring linear subspaces for face recognition under variable lighting[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(5):684-698.
[25] MARTINEZA M, BENAVENTE R. The AR face database, TR #24[R]. Barcelona, Spain:Computer Vision Center, 1998.
[26] LI F F, FERGUS R, PERONA P. Learning generative visual models from few training examples:an incremental Bayesian approach tested on 101 object categories[C]//Proceedings of the 2004 Conference on Computer Vision and Pattern Recognition Workshop. Washington, DC:IEEE Computer Society, 2004:178.
[27] XU Y, ZHANG Z, LU G, et al. Approximately symmetrical face images for image preprocessing in face recognition and sparse representation based classification[J]. Pattern Recognition, 2016, 54:68-82.
[28] WANG D, KONG S. A classification-oriented dictionary learning model:explicitly learning the particularity and commonality across categories[J]. Pattern Recognition, 2014, 47(2):885-898.
[29] ZHANG Z, XU Y, SHAO L, et al. Discriminative block-diagonal representation learning for image recognition[J]. IEEE Transactions on Neural Networks & Learning Systems, 2017, 29(7):3111-3125.