nach oben

Soft Computing

Erschienen in:

02.03.2016 | Methodologies and Application

A new branch-and-bound approach to semi-supervised support vector machine

verfasst von: Ye Tian, Jian Luo

Erschienen in: Soft Computing | Ausgabe 1/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper develops a branch-and-bound algorithm to solve the 2-norm soft margin semi-supervised support vector machine. First, the original problem is reformulated as a non-convex quadratically constrained quadratic programming problem with a simple structure. Then, we propose a new lower bound estimator which is conceptually simple and easy to be implemented in the branch-and-bound scheme. Since this estimator preserves both a high efficiency and a relatively good quality in the convex relaxation, it leads to a high total efficiency in the whole computational process. The numerical tests on both artificial and real-world data sets demonstrate the better effectiveness and efficiency of this proposed approach, which is compared to other well-known methods on different semi-supervised support vector machine models.

Vorheriger Artikel A hybrid spam detection method based on unstructured datasets

Nächster Artikel Motion retrieval based on Motion Semantic Dictionary and HMM inference

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Adankon M, Cheriet M, Biem A (2009) Semisupervised least squares support vector machine. IEEE Trans Neural Netw 20(12):1858–1870CrossRef

Bache K, Lichman M (2013) UCI machine learning repository. School of Information and Computer Science, University of California. http://archive.ics.uci.edu/ml. Accessed 2 Aug 2015

Bai Y, Yan X (2015) Conic relaxation for semi-supervised support vector machines. J Optim Theory Appl. doi:10.1007/s10957-015-0843-4

Bai Y, Chen Y, Niu B (2012) SDP relaxation for semi-supervised support vector machine. Pac J Optim 8(1):3–14MATHMathSciNet

Bai Y, Niu B, Chen Y (2013) New SDP models for protein homology detection with semi-supervised SVM. Optimization 62(4):561–572CrossRefMATHMathSciNet

Bennett K, Demiriz A (1999) Semi-supervised support vector machines. Adv Neural Inf Process Syst 11:368–374

Billionnet A, Elloumi S (2007) Using a mixed integer quadratic programming solver for the unconstrained quadratic 0–1 problem. Math Program 109:55–68CrossRefMATHMathSciNet

Blum A, Chawla S (2001) Learning from labeled and unlabeled data using graph mincuts. In: Proc. 18th int. conf. on mach. learn

Chapelle O, Schölkopf B, Zien A (2006) Semi-supervised learning. MIT press, CambridgeCrossRef

Chapelle O, Sindhwani V, Keerthi S (2008) Optimization techniques for semi-supervised support vector machines. J Mach Learn Res 9:203–233MATH

Collobert R, Sinz F, Weston F, Bottou L (2006) Large scale transductive SVMs. J Math Learn Res 7:1687–1712MATHMathSciNet

Cortes C, Vapnik V (1995) Support-vector networks. Mach Learn 20(3):273–297MATH

Cristianini N, Shawe-Taylor J (2000) An introduction to support vector machines and other kernel-based learning methods. Cambridge University Press, CambridgeCrossRefMATH

de Bie T, Cristianini N (2004) Convex methods for transuction. In: Thrun S, Saul L, Schöikopf B (eds) Advances in neural information processing systems, vol 16. MIT Press, Cambridge

de Bie T, Crisianini N (2006) Semi-supervised learning using semi-definite programming. In: Chapelle O, Schöikopf B, Zien A (eds) Semi-supervised learning. MIT Press, Cambridge

Gieseke F, Airola A, Pahikkala T, Kramer O (2014) Fast and simple gradient-based optimization for semi-supervised support vector machines. Neurocomputing 123:23–32CrossRef

Grant M, Boyd S (2010) CVX: matlab software for disciplined programming, version 1.2. http://cvx.com/cvx. Accessed 15 Aug 2015

Ha M, Wang C, Chen J (2013a) The support vector machine based on intuitionistic fuzzy number and kernel function. Soft Comput 4:635–641

Ha M, Yang Y, Wang C (2013b) A new support vector machine based on type-2 fuzzy samples. Soft Comput 11:2065–2074

He Q, Wu C (2011) Membership evaluation and feature selection for fuzzy support vector machine based on fuzzy rough sets. Soft Comput 15:1105–1114CrossRef

Horn R (1990) The hadamard product. Proc Symp Appl Math Am Math Soc 40:87C169

Joachims T (1999) Transductive inference for text classification using support vector machines. In: Int. conf. mach. learn., pp 200–209

Lanckriet G, Cristianini N, Bartlett P, Ghaoui L, Jordan M (2004) Learning the kernel matrix with semidefinite programming. J Mach Learn Res 5:27–72MATHMathSciNet

Lee C, Wang S, Jiao F, Schuurmans D, Greiner R (2006) Learning to model spatial dependency: semi-supervised discriminative random fields. In: Adv Neural Info Process Sys, vol 19

Lu C, Guo X (2014) Convex reformulation for binary quadratic programming problems via average objective value maximization. Optim Lett. http://link.springer.com/article/10.1007/s11590-014-0768-0. Accessed 12 July 2015

Luo J, Fang S, Bai Y, Deng Z (2016) Fuzzy quadratic surface support vector machine based on fisher discriminant analysis. J Ind Manag Optim 12:357–373CrossRefMATHMathSciNet

Osuna F, Freund R, Girosit F (1997) Training support vector machines: an application to face detection. In: Proc. comput. vis. pattern recognit., pp 130–136

Pardalos P, Vavasis S (1991) Quadratic programming with one negative eigenvalue is NP-Hard. J Glob Optim 1:15–22CrossRefMATHMathSciNet

Reddy S, Schevade S, Murty M (2011) A fast quasi-Newton method for semi-supervised SVM. Pattern Recognit 44:2305–2313CrossRefMATH

Schölkopf B, Smola A (2002) Learning with kernels: support vector machines, regularization, optimization and beyond. MIT Press, Cambridge

Sindhwani V, Keerthi S, Chapelle O (2006) Deterministic anealing for semi-supervised kernel machines. In: Proc. int. conf. mach. learn., pp 841–848

Sturm J (1999) SeDuMi 1.02, a matlab tool box for optimization over symmetric cones. Optim Methods Softw 11&12:625–653

Tay F, Cao I (2001) Application of support vector machines in financial time series forecasting. Omega 29(4):309–317CrossRef

Vandenberghe L, Boyd S (1996) Semidefinite programming. SIAM Rev 38:49–95CrossRefMATHMathSciNet

Vapnik V (1998) Statistical learning theory. Wiley-interscience, New York

Xu L, Neufeld J, Larson B, Schuurmans D (2005) Maximum margin clustering. In: Saul L, Weiss Y, Bottou L (eds) Adv. neural info. process syst. MIT Press, Cambridge, pp 1537–1544

Xu L, Jin R, Zhu K, King I, Lyu M (2008) Efficient convex relaxation for transductive support vector machine. In: Adv. neural info. process syst., vol 20. MIT Press, Cambridge, pp 1641–1648

Yang X, Han L, Yan L, He L (2014) A bilateral-truncated-loss based robust support vector machine for classification problems. Soft Comput. doi:10.1007/s00500-014-1448-9

Zhao B, Wang F, Zhang C (2008) Cuts3vm: a fast semi-supervised svm algorithm. In: Proc. 14th ACM SIGKDD int. conf. knowl. discov. data min., pp 830–838

Zhu X, Goldberg A (2009) Introduction to semi-supervised learning. Morgan and Claypool, New YorkMATH

Titel: A new branch-and-bound approach to semi-supervised support vector machine
verfasst von: Ye Tian
Jian Luo
Publikationsdatum: 02.03.2016
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 1/2017
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-016-2089-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2017

Uncertain minimum cost multicommodity flow problem

On strong standard completeness in some MTL expansions

Motion retrieval based on Dynamic Bayesian Network and Canonical Time Warping

Layers of zero probability and stable coherence over Łukasiewicz events

Generalised states: a multi-sorted algebraic approach to probability

Assessment of prediction ability for reduced probabilistic neural network in data classification problems