Group and graph joint sparsity for linked data classification
Abstract
Various sparse regularizers have been applied to machine learning problems, among which structured sparsity has been proposed for a better adaption to structured data. In this paper, motivated by effectively classifying linked data (e.g. Web pages, tweets, articles with references, and biological network data) where a group structure exists over the whole dataset and links exist between specific samples, we propose a joint sparse representation model that combines group sparsity and graph sparsity, to select a small number of connected components from the graph of linked samples, meanwhile promoting the sparsity of edges that link samples from different groups in each connected component. Consequently, linked samples are selected from a few sparsely-connected groups. Both theoretical analysis and experimental results on four benchmark datasets show that the joint sparsity model outperforms traditional group sparsity model and graph sparsity model, as well as the latest group-graph sparsity model.
References
[1]
Bach, F.; Jenatton, R.; Mairal, J.; and Obozinski, G. 2012. Optimization with sparsity-inducing penalties. Foundations and Trends in Machine Learning 4(1):1-106.
[2]
Baldassarre, L.; Morales, J.; Argyriou, A.; and Pontil, M. 2012. A general framework for structured sparsity via proximal optimization. In Proceedings of the 15th International Conference on Artificial Intelligence and Statistics (AISTATS'12), 82-90.
[3]
Bertsimas, D., and Tsitsiklis, J. N. 1997. Introduction to linear optimization. Athena Scientific Belmont.
[4]
Dai, X.-Y.; Zhang, J.-B.; Huang, S.-J.; Chen, J.-J.; and Zhou, Z.-H. 2015. Structured sparsity with group-graph regularization. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI'15), 1714-1720.
[5]
Duan, Y.; Wei, F.; Zhou, M.; and Shum, H.-Y. Graph-based collective classification for tweets. In Proceedings of the 21st ACM International Conference on Information and Knowledge Management (CIKM'12).
[6]
Gao, L., and Zhou, S. 2014. Towards Topological-Transformation Robust Shape Comparison: A Sparse Representation Based Manifold Embedding Approach. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI 2014), 2753-2759.
[7]
Gao, L., and Zhou, S. 2015. Learning Sparse Representations from Datasets with Uncertain Group Structures: Model, Algorithm and Applications. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), 2603-2609.
[8]
Huang, J. Z., and Zhang, T. 2009. The benefit of group sparsity. Annals of Statistics 38(4):1978-2004.
[9]
Huang, J.; Zhang, T.; and Metaxas, D. 2009. Learning with structured sparsity. Journal of Machine Learning Research 12(7):3371-3412.
[10]
Jacob, L.; Obozinski, G.; and Vert, J.-P. 2009. Group lasso with overlap and graph lasso. In Proceedings of the 26th Annual International Conference on Machine Learning (ICML'09), 433-440. ACM.
[11]
Jenatton, R.; Audibert, J.-Y.; and Bach, F. 2011. Structured variable selection with sparsity-inducing norms. The Journal of Machine Learning Research 12:2777-2824.
[12]
Li, Y., and Ngom, A. 2012. Fast sparse representation approaches for the classification of high-dimensional biological data. In IEEE International Conference on Bioinformatics and Biomedicine (BIBM'12), 1-6. IEEE.
[13]
Majumdar, A., and Ward, R. 2009. Classification via group sparsity promoting regularization. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP'09), 861-864.
[14]
Mccallum, A. K.; Nigam, K.; Rennie, J.; and Seymore, K. 2000. Automating the construction of internet portals with machine learning. In Information Retrieval, 127-163.
[15]
Micchelli, C. A.; Shen, L.; and Xu, Y. 2011. Proximity algorithms for image models: denoising. Inverse Problems 27(4):045009.
[16]
Moreau, J.-J. 1962. Fonctions convexes duales et points proximaux dans un espace hilbertien. CR Acad. Sci. Paris Sér. A Math 255:2897-2899.
[17]
Sainath, T. N.; Maskey, S.; Kanevsky, D.; Ramabhadran, B.; Nahamoo, D.; and Hirschberg, J. 2010. Sparse Representations for Text Categorization. In Proceedings of 11st Annual Conference of the International Speech Communication Association (INTERSPEECH'10), 2266-2269.
[18]
Wright, J.; Yang, A.; Ganesh, A.; Sastry, S.; and Ma, Y. 2009. Robust face recognition via sparse representation. IEEE Transactions on Pattern Analysis and Machine Intelligence 31(2):210-227.
[19]
Yuan, L.; Woodard, A.; Ji, S.; Jiang, Y.; Zhou, Z.-H.; Kumar, S.; and Ye, J. 2012. Learning sparse representations for fruitfly gene expression pattern image annotation and retrieval. BMC Bioinformatics 13(1):107.
[20]
Zhao, P.; Rocha, G.; and Yu, B. 2006. Grouped and hierarchical model selection through composite absolute penalties. Department of Statistics, UC Berkeley, Tech. Rep 703.
- Group and graph joint sparsity for linked data classification
Recommendations
Structured sparsity with group-graph regularization
AAAI'15: Proceedings of the Twenty-Ninth AAAI Conference on Artificial IntelligenceIn many learning tasks with structural properties, structural sparsity methods help induce sparse models, usually leading to better interpretability and higher generalization performance. One popular approach is to use group sparsity regularization that ...
Image/video compressive sensing recovery using joint adaptive sparsity measure
Compressive sensing (CS) is a recently emerging technique and an extensively studied problem in signal and image processing, which enables joint sampling and compression into a unified approach. Recently, local smoothness and nonlocal self-similarity ...
Recovery Algorithms for Vector-Valued Data with Joint Sparsity Constraints
Vector-valued data appearing in concrete applications often possess sparse expansions with respect to a preassigned frame for each vector component individually. Additionally, different components may also exhibit common sparsity patterns. Recently, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 2016
4406 pages
Sponsors
- Association for the Advancement of Artificial Intelligence
Publisher
AAAI Press
Publication History
Published: 12 February 2016
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Nov 2024