Supervised neighborhood graph construction for semi-supervised classification. (English) Zbl 1231.68218

Rohban, Mohammad Hossein; Rabiee, Hamid R.

Pattern Recognition 45, No. 4, 1363-1372 (2012).

Summary: Graph based methods are among the most active and applicable approaches studied in semi-supervised learning. The problem of neighborhood graph construction for these methods is addressed in this paper. Neighborhood graph construction plays a key role in the quality of the classification in graph based methods. Several unsupervised graph construction methods have been proposed that have addressed issues such as data noise, geometrical properties of the underlying manifold and graph hyper-parameters selection. In contrast, in order to adapt the graph construction to the given classification task, many of the recent graph construction methods take advantage of the data labels. However, these methods are not efficient since the hypothesis space of their possible neighborhood graphs is limited. In this paper, we first prove that the optimal neighborhood graph is a subgraph of a \(k^{\prime}\)-NN graph for a large enough \(k^{\prime}\), which is much smaller than the total number of data points. Therefore, we propose to use all the subgraphs of \(k^{\prime}\)-NNs graph as the hypothesis space. In addition, we show that most of the previous supervised graph construction methods are implicitly optimizing the smoothness functional with respect to the neighborhood graph parameters. Finally, we provide an algorithm to optimize the smoothness functional with respect to the neighborhood graph in the proposed hypothesis space. Experimental results on various data sets show that the proposed graph construction algorithm mostly outperforms the popular k-NN based construction and other state-of-the-art methods.

MSC:

68T05	Learning and adaptive systems in artificial intelligence
68R10	Graph theory (including graph drawing) in computer science
68T10	Pattern recognition, speech recognition

Keywords:

graph-based semi-supervised learning; manifold assumption; neighborhood graph construction

Software:

AFGen

References:

[2]	Jebara, T.; Wang, J.; Chang, S. F., Graph construction and \(b\)-matching for semi-supervised learning, (International Conference on Machine Learning (2009))
[3]	Cheng, B.; Yang, J.; Yan, S.; Fu, Y.; Huang, T. S., Learning with l1-graph for image analysis, IEEE Transactions on Image Processing, 19, 858-866 (2010) · Zbl 1371.68229
[4]	Shin, H.; Hill, N. J.; Rätsch, G., Graph based semi-supervised learning with sharper edges, (European Conference on Machine Learning (2006))
[5]	Hein, M.; Maier, M., Manifold denoising, (Advances in Neural Information Processing Systems (2006))
[6]	Wang, J.; Zhang, Z.; Zha, H., Adaptive manifold learning, (Advances in Neural Information Processing Systems (2005))
[7]	Kapoor, A.; Qi, Y.; Ahn, H.; Picard, R., Hyperparameter and kernel learning for graph based semi-supervised classification, (Advances in Neural Information Processing Systems (2006))
[8]	Zhu, X.; Kandola, J.; Ghahramani, Z.; Lafferty, J., Nonparametric transforms of graph kernels for semi-supervised learning, (Advances in Neural Information Processing Systems (2005))
[9]	Zhang, X.; Lee, W. S., Hyperparameter learning for graph based semi-supervised learning algorithms, (Advances in Neural Information Processing Systems (2006))
[10]	Dhillon, P. S.; Talukdar, P. P.; Crammer, K., Inference driven metric learning for graph construction, (4th North East Student Colloquium on Artificial Intelligence (2010))
[11]	Schaffer, C., A conservation law for generalization performance, (International Conference on Machine Learning (1994))
[12]	Wolpert, D., The lack of a priori distinctions between learning algorithms, Neural Computation, 8, 7, 1341-1390 (1996)
[14]	Rasmussen, C. E.; Williams, C. K.I., Gaussian Processes for Machine Learning (2006), The MIT Press · Zbl 1177.68165
[15]	Casella, G.; Berger, R. L., Statistical Inference (2001), Duxbury Press
[16]	Alexandrescu, A.; Kirchhoff, K., Data-driven graph construction for semi-supervised graph-based learning in NLP, (HLP NAACL (2007))
[17]	Cristianini, N.; Shawe-Taylor, J., An Introduction to Support Vector Machines and Other Kernel-based Learning Methods (2000), Cambridge University Press
[19]	LeCun, Y.; Bottou, L.; Bengio, Y.; Haffner, P., Gradient-based learning applied to document recognition, (Proceedings of the IEEE (1998)), 2278-2324
[20]	Hull, J. J., A database for handwritten text recognition research, IEEE Transactions on Pattern Analysis and Machine Intelligence, 550-554 (1994)
[21]	Chen, Y., Image categorization by learning and reasoning with regions, Journal of Machine Learning Research, 5, 913-939 (2004)