An Orderly Branch-and-Bound Search to Solve the Transductive Inference Problem Using Support Vector Machines

• Hygor Xavier Araújo UFJF
• Raul Fonseca Neto UFJF
• Saulo Moraes Villela UFJF

DOI: https://doi.org/10.5753/kdmile.2018.27392

Abstract

This article presents a new method to solve the problem of transductive inference whose objective is to predict the binary labels of a subset of points of interest in an unknown decision function. The Support Vector Machine is used to try to find a decision limit. To obtain the maximum margin hypothesis on labeled and unlabeled samples, an admissible best-first search is used based on the margin values. Empirical evidence suggests that this globally optimal solution can achieve excellent results in the transduction problem. Due to the selection strategy used, the search algorithm exploits only a small fraction of unlabeled samples, making it efficient for medium sized databases. The results obtained were compared with the results of the Transductive Support Vector Machine, showing better results in margin values.

Keywords: transductive inference, semi-supervised learning, permissible ordered search, vector machine support, low density separation

References

Bennett, K. P. and Demiriz, A. Semi-supervised support vector machines. In Proceedings of the 1998 Conference on Advances in Neural Information Processing Systems II. MIT Press, Cambridge, MA, USA, pp. 368–374, 1999.

Boser, B. E., Guyon, I. M., and Vapnik, V. N. A training algorithm for optimal margin classifiers. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory. ACM, New York, NY, USA, pp. 144–152, 1992.

Chapelle, O., Schölkopf, B., and Zien, A., editors. Semi-Supervised Learning. MIT Press, Cambridge, MA, 2006.

Chapelle, O., Sindhwani, V., and Keerthi, S. S. Branch and bound for semi-supervised support vector machines. In Advances in Neural Information Processing Systems 19, B. Schölkopf, J. C. Platt, and T. Hoffman (Eds.). MIT Press, Hyatt Regency Vancouver, in Vancouver, B.C., Canada, pp. 217–224, 2007.

Gammerman, A., Vovk, V., and Vapnik, V. Learning by transduction. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, pp. 148–155, 1998.

Graepel, T., Herbrich, R., and Obermayer, K. Bayesian transduction. In Proceedings of the 12th International Conference on Neural Information Processing Systems. MIT Press, Cambridge, MA, USA, pp. 456–462, 1999.

Joachims, T. Transductive inference for text classification using support vector machines. In Proceedings of the Sixteenth International Conference on Machine Learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, pp. 200–209, 1999.

Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research vol. 12, pp. 2825–2830, 2011.

Platt, J. C. Fast training of support vector machines using sequential minimal optimization. In Advances in Kernel Methods, B. Schölkopf, C. J. C. Burges, and A. J. Smola (Eds.). MIT Press, Cambridge, MA, USA, pp. 185–208, 1999.

Vapnik, V. N. The Nature of Statistical Learning Theory. Springer-Verlag, Berlin, Heidelberg, 1995.

Villela, S. M., Leite, S. C., and Fonseca Neto, R. Feature selection from microarray data via an ordered search with projected margin. In Proceedings of the 24th International Conference on Artificial Intelligence. AAAI Press, Buenos Aires, Argentina, pp. 3874–3881, 2015.

Villela, S. M., Leite, S. C., and Fonseca Neto, R. Incremental p-margin algorithm for classification with arbitrary norm. Pattern Recognition vol. 55, pp. 261–272, 2016.