Semi-Supervised Learning in Complex Networks

• Thiago C. Silva USP
• Liang Zhao USP

Resumo

Semi-Supervised Learning (SSL) is a machine learning scheme which is able to employ both labeled and unlabeled samples in the training process. In this paper, we propose a semi-supervised classification model based on a combined random-deterministic walk of particles in the network (graph) constructed from the input data set. The particles of the same class cooperate among them, while the particles of different classes compete with each other to propagate class labels to the whole network. A rigorous definition of the model is provided. An interesting feature of the proposed model is that each particle only visits a portion of nodes potentially belonging to it due to the competition mechanism. Thus, many long range, apparently meaningless visits are avoided. As a result, the proposed model can achieve a good classification rate while exhibiting low computational complexity order in comparison to other network-based semi-supervised algorithms. Computer simulations carried out for synthetic and real-world data sets show good performance of the model.

Referências

Belkin, M., P., N., and Sindhwani, V. (2005). On manifold regularization. In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics (AISTAT 2005), pages 17–24, New Jersey. Society for Artificial Intelligence and Statistics.

Chapelle, O., Schölkopf, B., and Zien, A., editors (2006). Semi-supervised Learning. Adaptive computation and machine learning. MIT Press, Cambridge, MA, USA.

Dara, R., Kremer, S., and Stacey, D. (2002). Clustering unlabeled data with SOMs improves classification of labeled real-world data. In Proceedings of the World Congress on Computational Intelligence (WCCI), pages 2237–2242.

Demšar, J. (2006). Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7:1–30.

Fujino, A., Ueda, N., and Saito, K. (2005). A hybrid generative/discriminative approach to semi-supervised classifier design. In AAAI-05, Proceedings of the Twentieth National Conference on Artificial Intelligence, pages 764–769.

Jain, L. C., Lazzerini, B., and (eds.), U. H. (2010). Innovations in ART Neural Networks (Studies in Fuzziness and Soft Computing). Physica-Verlag, Heidelberg.

Kohonen, T. (1990). The self-organizing map. Proceedings of the IEEE, 78(9):1464–1480.

Mitchell, T. M. (1999). The role of unlabeled data in supervised learning. In Proceedings of the Sixth International Colloquium on Cognitive Science.

Quiles, M. G., Zhao, L., Alonso, R. L., and Romero, R. A. F. (2008). Particle competition for complex network community detection. Chaos, 18(3):033107.

Vapnik, V. N. (2008). Statistical Learning Theory. Wiley-Interscience, New York.

Wang, F., Li, T., Wang, G., and Zhang, C. (2008). Semi-supervised classification using local and global regularization. In AAAI’08: Proceedings of the 23rd national conference on Artificial intelligence, pages 726–731. AAAI Press.

Wu, M. and Schölkopf, B. (2007). Transductive classification via local learning regularization. In 11th International Conference on Artificial Intelligence and Statistics, pages 628–635. Microtome.

Zhou, D., Bousquet, O., Lal, T. N., Weston, J., and Schölkopf, B. (2004). Learning with local and global consistency. In Advances in Neural Information Processing Systems, volume 16, pages 321–328. MIT Press.

Zhu, X. (2005). Semi-supervised learning literature survey. Technical Report 1530, Computer Sciences, University of Wisconsin-Madison.