×

Adaptive graph construction using data self-representativeness for pattern classification. (English) Zbl 1390.68522

Summary: Graph construction from data constitutes a pre-stage in many machine learning and computer vision tasks, like semi-supervised learning, manifold learning, and spectral clustering. The influence of graph construction procedures on learning tasks and their related applications has only received limited study despite its critical impact on accuracy. State-of-the-art graphs are built via sparse coding adopting \(\ell_{1}\) regularization. Those graphs exhibit good performance in many computer vision applications. However, the locality and similarity among instances are not explicitly used in the coding scheme. Furthermore, due to the use of \(\ell_{1}\) regularization, these construction approaches can be computationally expensive. In this paper, we investigate graph construction using the data self-representativeness property. By incorporating a variant of locality-constrained linear coding (LLC), we introduce and derive four variants for graph construction. These variants adopt a two phase LLC (TPLLC). Compared with the recent \(\ell_{1}\) graphs, our proposed objective function, associated with three variants, has an analytical solution, and thus, is more efficient. A key element of the proposed methods is the second phase of coding that allows data closeness, or locality, to be naturally incorporated. It performs a coding over some selected relevant samples and reinforces the individual regularization terms by exploiting the coefficients estimated in the first phase. Comprehensive experimental results using several benchmark datasets show that it can achieve or outperform existing state-of-the-art results. Furthermore, it is shown to be more efficient than the robust \(\ell_{1}\) graph construction schemes.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68T10 Pattern recognition, speech recognition
68T45 Machine vision and scene understanding

Software:

Yall1
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Belkin, M.; Niyogi, P., Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comput., 15, 6, 1373-1396 (2003) · Zbl 1085.68119
[2] Belkin, M.; Niyogi, P.; Sindhwani, V., Manifold regularization: a geometric framework for learning from labeled and unlabeled examples, J. Mach. Learn. Res., 7, 2399-2434 (2006) · Zbl 1222.68144
[3] Bertini, J. R.; Zhao, L.; Lopes, A. A., An incremental learning algorithm based on the k-associated graph for non-stationary data classification, Inform. Sci., 46, 10, 52-68 (2013) · Zbl 1320.68132
[5] Chen, H.; Chang, H.; Liu, T., Local discriminant embedding and its variants, IEEE International Conference on Computer Vision and Pattern Recognition, 846-853 (2005)
[6] Cheng, B.; Yang, J.; Yan, S.; Fu, Y.; Huang, T. S., Learning with L1-graph for image analysis, IEEE Trans. Image Process., 19, 4, 858-866 (2010) · Zbl 1371.68229
[7] Cheng, H.; Liu, Z.; Yang, J., Sparsity induced similarity measure for label propagation, IEEE International Conference on Computer Vision, 317-324 (2009)
[8] Combettes, P.; Wajs, V., Signal recovery by proximal forward-backward splitting, Multisc. Model. Simul., 4, 4, 1168-1200 (2005) · Zbl 1179.94031
[9] Huang, J.; Zhou, D.; Scholkopf, B., Learning from labeled and unlabeled data on a directed graph, ICML, 1036-1043 (2005)
[10] Daitch, S. I.; Kelner, J. A.; Spielman, D. A., Fitting a graph to vector data, International Conference on Machine Learning, 201-208 (2009)
[11] Dornaika, F.; Bosaghzadeh, A.; Raducanu, B., Efficient graph construction for label propagation based multi-observation face recognition, International Workshop on Human Behavior Understanding. International Workshop on Human Behavior Understanding, LNCS, 8212, 124-135 (2013)
[12] Dornaika, F.; Bosaghzadeh, A.; Salmane, H.; Ruichek, Y., Graph-based semi-supervised learning with local binary patterns for holistic object categorization, Expert Syst. Appl., 41, 17, 7744-7753 (2014)
[13] Dornaika, F.; Bosaghzadeh, A.; Salmane, H.; Ruichek, Y., A graph construction method using LBP self-representativeness for outdoor object categorization, Eng. Appl. Artif. Intell., 34, 294-302 (2014)
[14] Elhamifar, E.; Vidal, R., Sparse subspace clustering: algorithm, theory, and applications, IEEE Trans. Pattern Anal. Mach. Intell., 35, 11, 2765-2781 (2013)
[15] Figueiredo, M. A.T.; Nowak, R. D.; Wright, S. J., Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE J. Selected Top. Signal Process., 1, 4, 586-597 (2007)
[16] Gao, S.; Tsang, I.; Chia, L.-T., Laplacian sparse coding, hypergraph Laplacian sparse coding, and applications, IEEE Trans. Pattern Anal. Mach. Intell., 31, 1, 92-104 (2013)
[17] Guyon, I.; Elisseeff, A., An introduction to variable and feature selection, J. Mach. Learn. Res., 3, 1157-1182 (2003) · Zbl 1102.68556
[18] He, R.; Zheng, W.; Hu, B.; Kong, X., Nonnegative sparse coding for discriminative semi-supervised learning, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2849-2856 (2011)
[19] He, X.; Cai, D.; Niyogi, P., Laplacian score for feature selection, Neural Information Processing Systems, 507-514 (2005)
[20] He, X.; Niyogi, P., Locality preserving projections, Advances in Neural Information Processing Systems 16, 153-160 (2003), MIT Press
[21] Jebara, T.; Wang, J.; Chang, S., Graph construction and b-matching for semi-supervised learning, ICML, 441-448 (2009)
[22] Jiang, Z. L.; Lin, Z.; Davis, L. S., Learning a discriminative dictionary for sparse coding via label consistent KSVD, IEEE International Conference on Computer Vision and Pattern Recognition, 1697-1704 (2011)
[23] Kim, S. J.; Koh, K.; Lustig, M.; Boyd, S.; Gorinevsky, D., A interior-point method for large-scale l1-regularized least squares, IEEE J. Selected Top. Signal Process., 1, 4, 606-617 (2007)
[24] Kokiopoulou, E.; Frossard, P., Graph-based classification of multiple observation sets, Pattern Recognit., 43, 12, 3988-3997 (2010) · Zbl 1207.68291
[25] Lee, H.; Battle, A.; Raina, R.; Ng, A. Y., Efficient sparse coding algorithms, Advances in Neural Information Processing Systems, 801-808 (2006)
[26] Li, C.; Guo, J.; Zhang, H., Local sparse representation based classification, IEEE International Conference on Pattern Recognition, 649-652 (2010)
[27] Li, C.; Qi, X.; Guo, J.; Xiao, B., An evaluation on different graphs for semi-supervised learning, Intelligent Science and Intelligent Data Engineering, 58-65 (2012)
[29] Liu, W.; Chang, S. F., Robust multi-class transductive learning with graphs, Computer Vision and Pattern Recognition, 381-388 (2009)
[30] Liu, X.; Pan, S.; Hao, Z.; Lin, Z., Graph-based semi-supervised learning by mixed label propagation with a soft constraint, Inform. Sci., 277, 1, 327-337 (2014) · Zbl 1354.68224
[31] Maier, M.; von Luxburg, U.; Hein, M., Influence of graph construction on graph-based clustering measures, NIPS, 1025-1032 (2008)
[32] Mairal, J.; Bach, F.; Ponce, J.; Sapiro, G.; Zisserman, A., Online dictionary learning for sparse coding, ICML, 689-696 (2009)
[33] Malioutov, D. M.; Cetin, M.; Willsky, A. S., Homotopy continuation for sparse signal representation, Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP ’05). IEEE International Conference on, 5, v/733-v/736 (2005)
[34] Newmann, M. E.J., Finding community structure in networks using the eigenvectors of matrices, Phys Rev. E Stat Nonlin Soft Matter Phys, 74:036104 (2006)
[35] Nie, F.; Xu, D.; Tsang, I.; Zhang, C., Flexible manifold embedding: a framework for semi-supervised and unsupervised dimension reduction, IEEE Trans. Image Process., 19, 7, 1921-1932 (2010) · Zbl 1371.94276
[36] Nie, F.; Zeng, Z.; Tsang, I. W.; Xu, D.; Zhang, C., Spectral embedded clustering: a framework for in-sample and out-of-sample spectral clustering, IEEE Trans. Neural Netw., 22, 11, 1796-1808 (2011)
[37] Niyogi, P., Manifold regularization and semi-supervised learning: Some theoretical analyses, Technical Report (2008), Computer Science Department, University of Chicago
[38] Ojala, T.; Pietikainen, M.; Maenpaa, T., Multiresolution gray-scale and rotation invariant texture classification with local binary patterns, IEEE Trans. Pattern Anal. Mach. Intell., 24, 7, 971-987 (2002)
[39] Roweis, S.; Saul, L., Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 5500, 2323-2326 (2000)
[40] Shi, Q.; Eriksson, A.; Hengel, A.; Shen, C., Is face recognition really a compressive sensing problem?, IEEE International Conference on Computer Vision Pattern Recognition, 553-560 (2011)
[41] Singh, A.; Nowak, R.; Zhu, X., Unlabeled data: now it helps, now it doesnt, Advances in Neural Information Processing Systems, 1513-1520 (2009)
[42] Sousa, C.; Rezende, S.; Batista, G., Influence of graph construction on semi-supervised learning, European Conference on Machine Learning, 160-175 (2013)
[43] Tang, J.; Hong, R.; Yan, S.; Chua, T. S.; Qi, J.; Jain, R., Image annotation by KNN-sparse graph-based label propagation over noisily tagged web images, ACM Trans. Intell. Syst. Technol., 2, 2, 14:1-14:15 (2011)
[44] von Luxburg, U., A tutorial on spectral clustering, Stat. Comput., 17, 4, 395-416 (2007)
[45] Wang, F.; Zhang, C., Label propagation through linear neighborhoods, IEEE Trans. Knowl. Data Eng., 20, 1, 55-67 (2008)
[46] Wang, H.; Huang, H.; Ding, C., Image categorization using directed graphs, European Conference on Computer Vision, 762-775 (2010)
[47] Wang, J.; Yang, J.; Yu, K.; Lv, F.; Huang, T.; Gong, Y., Locality-constrained linear coding for image classification, IEEE International Conference on Computer Vision and Pattern Recognition, 3360-3367 (2010)
[48] Wang, Z.; Song, Y.; Zhang, C., Knowledge transfer on hybrid graph, Proceedings of the 21st International Joint Conference on Artifical Intelligence, 1291-1296 (2009)
[49] Waqas, J.; Yi, Z.; Zhang, L., Collaborative neighbor representation based classification using \(l_2\)-minimization approach, Pattern Recognit. Lett., 34, 2, 201-208 (2013)
[50] Wolf, L.; Hassner, T.; Taigman, Y., Similarity scores based on background samples, Proceedings of the 9th Asian Conference on Computer Vision - Volume Part II. Proceedings of the 9th Asian Conference on Computer Vision - Volume Part II, ACCV’09, 88-97 (2010)
[51] Wright, J.; Yang, A. Y.; Ganesh, A.; Sastry, S. S.; Ma, Y., Robust face recognition via sparse representation, IEEE Trans. Pattern Anal. Mach. Intell., 31, 2, 210-227 (2009)
[52] Yan, S.; Wang, H., Semi-supervised learning by sparse representation, SIAM International Conference on Data Mining, 792-801 (2009)
[53] Yan, S. C.; Xu, D.; Zhang, B.; Zhang, H.; Yang, Q.; Lin, S., Graph embedding and extension: a general framework for dimensionality reduction, IEEE Trans. Pattern Anal. Mach. Intell., 29, 1, 40-51 (2007)
[54] Yang, A. Y.; Sastry, S. S.; Ganesh, A.; Ma, Y., Fast \(L_1 -\) minimization algorithms and an application in robust face recognition: a review, Technical Report (2010)
[55] Yang, J.; Yu, K.; Gong, Y.; Huang, T., Linear spatial pyramid matching using sparse coding for image classification, IEEE Conference on. Computer Vision and Pattern Recognition, 1794-1801 (2009)
[56] Yang, J.; Zhang, L.; Xu, Y.; Yang, J., Beyond sparsity: the role of L1-optimizer in pattern classification, Pattern Recognit., 45, 1104-1118 (2012) · Zbl 1227.68102
[57] Yang, J.; Zhang, Y., Alternating direction algorithms for \(l_1\)-problems in compressive sensing, Technical Report (2009)
[58] Yang, M.; Zhang, L.; Yang, J.; Zhang, D., Robust sparse coding for face recognition, IEEE International Conference on Computer Vision and Pattern Recognition, 625-632 (2011)
[59] Yang, S.; Lv, Y.; Ren, Y.; Yang, L.; Jiao, L., Unsupervised images segmentation via incremental dictionary learning based sparse representation, Inform. Sci., 269, 10, 48-59 (2014)
[60] Zhang, L.; Chen, S.; Qiao, L., Graph optimization for dimensionality reduction with sparsity constraints, Pattern Recognit., 45, 1205-1210 (2012) · Zbl 1227.68097
[61] Zhang, L.; Qiao, L.; Chen, S., Graph-optimized locality preserving projections, Pattern Recognit., 43, 1993-2002 (2010) · Zbl 1191.68611
[62] Zhang, L.; Yang, M.; Feng, X., Sparse representation or collaborative representation: which helps face recognition?, International Conference on Computer Vision, 471-478 (2011)
[63] Zhang, L.; Yang, M.; Feng, X.; Ma, Y.; Zhang, D., Collaborative representation based classification for face recognition, CoRR, abs/1204.2358 (2012)
[64] Zhao, J.; Lu, K.; He, X., Locality sensitive semi-supervised feature selection, Neurocomput., 71, 1842-1849 (2008)
[65] Zhou, D.; Bousquet, O.; Lal, T. N.; Weston, J.; Scholkopf, B., Learning with local and global consistency, Advances in Neural Information Processing Systems, 321-328 (2004)
[66] Zhou, H.; Hastie, T.; Tibshirani, R., Sparse principal component analysis, Technical Report (2004), Statistics Department, Stanford University
[67] Zhu, X.; Ghahramani, Z.; Lafferty, J., Semi-supervised learning using gaussian fields and harmonic functions, International Conference on Machine Learning, 912-919 (2003)
[68] Zibulevsky, M.; Elad, M., \(L_1-L_2\) optimization in signal and image processing, IEEE Signal Process. Mag., 27, 3, 76-88 (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.