A new semi-supervised classifier based on maximum vector-angular margin

Liming Yang; Yannan Chao

doi:10.3934/jimo.2016035

Previous Article
Parametric solutions to the regulator-conjugate matrix equations
JIMO Home
This Issue
Next Article
A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems

April 2017, 13(2): 609-622. doi: 10.3934/jimo.2016035

A new semi-supervised classifier based on maximum vector-angular margin

Liming Yang ^, and Yannan Chao

College of Science, China Agricultural University, No.17 Tsing Hua East Road, Hai Dian District, Beijing 100083, China

* Corresponding author: Liming Yang

Received December 2014 Revised December 2015 Published May 2016

Semi-supervised learning is an attractive method in classification problems when insufficient training information is available. In this investigation, a new semi-supervised classifier is proposed based on the concept of maximum vector-angular margin, (called S$^3$MAMC), the main goal of which is to find an optimal vector $c$ as close as possible to the center of the dataset consisting of both labeled samples and unlabeled samples. This makes S$^3$MAMC better generalization with smaller VC (Vapnik-Chervonenkis) dimension. However, S$^3$MAMC formulation is a non-convex model and therefore it is difficult to solve. Following that we present two optimization algorithms, mixed integer quadratic program (MIQP) and DC (difference of convex functions) program algorithms, to solve the S$^3$MAMC. Compared with the supervised learning methods, numerical experiments on real and synthetic databases demonstrate that the S$^3$MAMC can improve generalization when the labelled samples are relatively few. In addition, the S$^3$MAMC has competitive experiment results in generalization compared to the traditional semi-supervised classification methods.

Keywords: Vector-angular margin, semi-supervised learning, support vector machine, DC programming, mixed integer programming.

Mathematics Subject Classification: Primary: 65K05, 90C26; Secondary: 90C11, 78M50.

Citation: Liming Yang, Yannan Chao. A new semi-supervised classifier based on maximum vector-angular margin. Journal of Industrial & Management Optimization, 2017, 13 (2) : 609-622. doi: 10.3934/jimo.2016035

References:

[1]	L. T. H. An and P. D. Tao, The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Annals of Operations Research, 133 (2005), 23-46. doi: 10.1007/s10479-004-5022-1. Google Scholar
[2]	L. T. H. An, H. M. Le, V. V. Nguyen and P. D. Tao, A DC programming approach for feature selection in support vector machines learning, Advances in Data Analysis and Classification, 2 (2008), 259-278. doi: 10.1007/s11634-008-0030-7. Google Scholar
[3]	A. Asuncion and D. J. Newman, UCI machine learning repository, School of Information and Computer Sciences, University of California Irvine, 2007, http://www.ics.uci.edu/~mlearn/MLRepository.html. Google Scholar
[4]	K. Bennett and A. Demiriz, Semi-supervised support vector machines, In Advances in Neural Information Processing Systems, MIT Press, Cambridge, 12 (1998), 368–374. Google Scholar
[5]	W. Changzhi, L. Chaojie and L. Qiang, A DC programming approach for sensor network localization with uncertainties in anchor positions, Journal of Industrial and Management Optimization, 10 (2014), 817-826. doi: 10.3934/jimo.2014.10.817. Google Scholar
[6]	O. Chapelle, V. Sindhwani and S. Keerthi, Optimization Techniques for Semi-Supervised Support Vector Machines, Journal of Machine Learning Research, 9 (2008), 203-233. Google Scholar
[7]	T. Fawcett, An introduction to ROC analysis, Pattern Recognition Letters, 27 (2006), 861-874. Google Scholar
[8]	G. Fung and O. Mangasarian, Semi-Supervised Support Vector Machines for Unlabeled Data Classification, Optimization methods & software, 15 (2001), 29-44. Google Scholar
[9]	W. Guan and A. Gray, Sparse high-dimensional fractional-norm support vector machine via DC programming, Computational Statistics and Data Analysis, 67 (2013), 136-148. doi: 10.1016/j.csda.2013.01.020. Google Scholar
[10]	W. J. Hu, F. L. Chung and L. SH. Wang, The Maximum Vector-Angular Margin Classifier and its fast training on large datasets using a core vector machine, Neural Networks, 27 (2012), 60-73. Google Scholar
[11]	P. D. Tao and L. T. T. An, Convex analysis approaches to DC programming: Theory, algorithms and applications, Acta Mathematica, 22 (1997), 287-367. Google Scholar
[12]	B. Scholkopf, A. J. Smola, R. C. Williamson and P. L. Bartlett, New support vector algorithms, Neural Computation, 12 (2000), 1207-1245. Google Scholar
[13]	X. Xiao, J. Gu, L. Zhang and S. Zhang, A sequential convex program method to DC program with joint chance constraints, Journal of Industrial and Management Optimization, 8 (2012), 733-747. doi: 10.3934/jimo.2012.8.733. Google Scholar
[14]	L. M. Yang and L. SH. Wang, A class of smooth semi-supervised SVM by difference of convex functions programming and algorithm, Knowledge-Based Systems, 41 (2013), 1-7. Google Scholar
[15]	YALMIP Toolbox. http://control.ee.ethz.ch/~joloef/wiki/pmwiki.php. Google Scholar
[16]	Y. B. Yuan, Canonical duality solution for alternating support vector machine, Journal of Industrial and Management Optimization, 8 (2012), 611-621. doi: 10.3934/jimo.2012.8.611. Google Scholar
[17]	V. N. Vapnik, Statistical Learning Theory, New York: Wiley. 1998. Google Scholar

show all references

References:

[1]	L. T. H. An and P. D. Tao, The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Annals of Operations Research, 133 (2005), 23-46. doi: 10.1007/s10479-004-5022-1. Google Scholar
[2]	L. T. H. An, H. M. Le, V. V. Nguyen and P. D. Tao, A DC programming approach for feature selection in support vector machines learning, Advances in Data Analysis and Classification, 2 (2008), 259-278. doi: 10.1007/s11634-008-0030-7. Google Scholar
[3]	A. Asuncion and D. J. Newman, UCI machine learning repository, School of Information and Computer Sciences, University of California Irvine, 2007, http://www.ics.uci.edu/~mlearn/MLRepository.html. Google Scholar
[4]	K. Bennett and A. Demiriz, Semi-supervised support vector machines, In Advances in Neural Information Processing Systems, MIT Press, Cambridge, 12 (1998), 368–374. Google Scholar
[5]	W. Changzhi, L. Chaojie and L. Qiang, A DC programming approach for sensor network localization with uncertainties in anchor positions, Journal of Industrial and Management Optimization, 10 (2014), 817-826. doi: 10.3934/jimo.2014.10.817. Google Scholar
[6]	O. Chapelle, V. Sindhwani and S. Keerthi, Optimization Techniques for Semi-Supervised Support Vector Machines, Journal of Machine Learning Research, 9 (2008), 203-233. Google Scholar
[7]	T. Fawcett, An introduction to ROC analysis, Pattern Recognition Letters, 27 (2006), 861-874. Google Scholar
[8]	G. Fung and O. Mangasarian, Semi-Supervised Support Vector Machines for Unlabeled Data Classification, Optimization methods & software, 15 (2001), 29-44. Google Scholar
[9]	W. Guan and A. Gray, Sparse high-dimensional fractional-norm support vector machine via DC programming, Computational Statistics and Data Analysis, 67 (2013), 136-148. doi: 10.1016/j.csda.2013.01.020. Google Scholar
[10]	W. J. Hu, F. L. Chung and L. SH. Wang, The Maximum Vector-Angular Margin Classifier and its fast training on large datasets using a core vector machine, Neural Networks, 27 (2012), 60-73. Google Scholar
[11]	P. D. Tao and L. T. T. An, Convex analysis approaches to DC programming: Theory, algorithms and applications, Acta Mathematica, 22 (1997), 287-367. Google Scholar
[12]	B. Scholkopf, A. J. Smola, R. C. Williamson and P. L. Bartlett, New support vector algorithms, Neural Computation, 12 (2000), 1207-1245. Google Scholar
[13]	X. Xiao, J. Gu, L. Zhang and S. Zhang, A sequential convex program method to DC program with joint chance constraints, Journal of Industrial and Management Optimization, 8 (2012), 733-747. doi: 10.3934/jimo.2012.8.733. Google Scholar
[14]	L. M. Yang and L. SH. Wang, A class of smooth semi-supervised SVM by difference of convex functions programming and algorithm, Knowledge-Based Systems, 41 (2013), 1-7. Google Scholar
[15]	YALMIP Toolbox. http://control.ee.ethz.ch/~joloef/wiki/pmwiki.php. Google Scholar
[16]	Y. B. Yuan, Canonical duality solution for alternating support vector machine, Journal of Industrial and Management Optimization, 8 (2012), 611-621. doi: 10.3934/jimo.2012.8.611. Google Scholar
[17]	V. N. Vapnik, Statistical Learning Theory, New York: Wiley. 1998. Google Scholar

Figure 1. ACC versus µ=1 for ν=1 and 10 on Thyroid data

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2. Training samples of the synthetic data

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3. Comparison of DCA-S³MAMC and MIQP-S³MAMC in terms of CPU-time

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4. Comparison of DCA-S³MAMC and MIQP-S³MAMC in terms of ACC

Figure Options

Download full-size image

Download as PowerPoint slide

Table 1. Comparison of S$^3$MAMC, MAMC and $\nu$-SVC with the ratio of labelled to unlabelled samples being 2:8 in terms of generalization

data	Classification models	G-ACC (%)	ACC (%)	MCC (%)	$F_1$-measure (%)
	DCA-S$^3$MAMC	100	100	100	100
	MIQP-S$^3$MAMC	100	100	100	100
Wine	MAMC	94.31	94.39	89.06	94.16
$(107 \times 13)$	$\nu$-SVM	99.30	99.30	98.62	99.31
	DCA-S$^3$MAMC	99.81	99.81	99.63	99.81
	MIQP-S$^3$MAMC	95.55	95.65	91.64	95.45
Tryroid	MAMC	94.87	95.00	90.45	95.24
$(65 \times 5)$	$\nu$-SVM	87.94	88.34	77.76	89.23
	DCA-S$^3$MAMC	92.69	93.76	86.73	93.49
	MIQP-S$^3$MAMC	96.35	96.35	91.20	96.16
Cancer	MAMC	92.26	93.36	86.03	93.02
$(569 \times 30)$	$\nu$-SVM	91.27	91.46	85.30	90.93
	DCA-S$^3$MAMC	62.40	62.40	24.81	62.65
	MIQP-S$^3$MAMC	62.42	63.02	26.44	65.98
Sonar	MAMC	60.11	60.41	20.97	62.67
$(208 \times 60)$	$\nu$-SVM	60.11	60.19	20.40	58.99
	DCA-S$^3$MAMC	86.65	87.61	75.00	87.98
	MIQP-S$^3$MAMC	85.34	86.69	75.91	88.20
Ionosphere	MAMC	80.94	81.25	63.14	82.49
$(350 \times 34)$	$\nu$-SVM	86.34	86.74	74.51	87.76
	DCA-S$^3$MAMC	72.82	73.66	48.51	76.28
	MIQP-S$^3$MAMC	78.26	78.65	58.00	80.19
Hepatitis	MAMC	70.60	71.76	45.04	74.98
$(155 \times 19)$	$\nu$-SVM	70.00	71.21	43.93	74.53
	DCA-S$^3$MAMC	86.39	86.40	72.80	86.54
	MIQP-S$^3$MAMC	84.72	84.79	69.76	85.31
Heart	MAMC	81.82	81.86	63.83	82.35
$(155 \times 19)$	$\nu$-SVM	84.70	84.72	69.46	84.95
	DCA-S$^3$MAMC	94.78	94.81	89.69	94.91
	MIQP-S$^3$MAMC	95.61	95.62	91.29	95.69
Vote	MAMC	90.11	90.29	81.07	90.80
$(432 \times 16)$	$\nu$-SVM	94.51	94.54	89.09	94.60
	DCA-S$^3$MAMC	92.50	92.50	85.00	92.54
	MIQP-S$^3$MAMC	93.25	93.25	86.50	93.23
Synthesis	MAMC	86.45	86.49	73.07	86.82
$(200 \times 2)$	$\nu$-SVM	82.50	82.50	65.00	82.41

Table Options

Download as excel

data	Classification models	G-ACC (%)	ACC (%)	MCC (%)	$F_1$-measure (%)
	DCA-S$^3$MAMC	100	100	100	100
	MIQP-S$^3$MAMC	100	100	100	100
Wine	MAMC	94.31	94.39	89.06	94.16
$(107 \times 13)$	$\nu$-SVM	99.30	99.30	98.62	99.31
	DCA-S$^3$MAMC	99.81	99.81	99.63	99.81
	MIQP-S$^3$MAMC	95.55	95.65	91.64	95.45
Tryroid	MAMC	94.87	95.00	90.45	95.24
$(65 \times 5)$	$\nu$-SVM	87.94	88.34	77.76	89.23
	DCA-S$^3$MAMC	92.69	93.76	86.73	93.49
	MIQP-S$^3$MAMC	96.35	96.35	91.20	96.16
Cancer	MAMC	92.26	93.36	86.03	93.02
$(569 \times 30)$	$\nu$-SVM	91.27	91.46	85.30	90.93
	DCA-S$^3$MAMC	62.40	62.40	24.81	62.65
	MIQP-S$^3$MAMC	62.42	63.02	26.44	65.98
Sonar	MAMC	60.11	60.41	20.97	62.67
$(208 \times 60)$	$\nu$-SVM	60.11	60.19	20.40	58.99
	DCA-S$^3$MAMC	86.65	87.61	75.00	87.98
	MIQP-S$^3$MAMC	85.34	86.69	75.91	88.20
Ionosphere	MAMC	80.94	81.25	63.14	82.49
$(350 \times 34)$	$\nu$-SVM	86.34	86.74	74.51	87.76
	DCA-S$^3$MAMC	72.82	73.66	48.51	76.28
	MIQP-S$^3$MAMC	78.26	78.65	58.00	80.19
Hepatitis	MAMC	70.60	71.76	45.04	74.98
$(155 \times 19)$	$\nu$-SVM	70.00	71.21	43.93	74.53
	DCA-S$^3$MAMC	86.39	86.40	72.80	86.54
	MIQP-S$^3$MAMC	84.72	84.79	69.76	85.31
Heart	MAMC	81.82	81.86	63.83	82.35
$(155 \times 19)$	$\nu$-SVM	84.70	84.72	69.46	84.95
	DCA-S$^3$MAMC	94.78	94.81	89.69	94.91
	MIQP-S$^3$MAMC	95.61	95.62	91.29	95.69
Vote	MAMC	90.11	90.29	81.07	90.80
$(432 \times 16)$	$\nu$-SVM	94.51	94.54	89.09	94.60
	DCA-S$^3$MAMC	92.50	92.50	85.00	92.54
	MIQP-S$^3$MAMC	93.25	93.25	86.50	93.23
Synthesis	MAMC	86.45	86.49	73.07	86.82
$(200 \times 2)$	$\nu$-SVM	82.50	82.50	65.00	82.41

Table 2. Comparison of S$^3$MAMC, MAMC and $\nu$-SVM with the ratio of labelled to unlabelled samples being 1:9 in terms of accuracy (ACC)

models	DCA-S$^3$MAMC $(\%)$	MAMC $(\%)$	$\nu$-SVM $(\%)$
Tryroid	92.59	85.19	86.29
Ionosphere	83.37	71.43	71.74
Sonar	60.45	55.56	53.89
Cancer	93.15	89.88	84.52
Heart	85.19	74.31	75.49
Hepatitis	73.33	64.44	71.11
Vote	93.65	86.95	89.68
Synthesis	91.56	70.39	63.66

Table Options

Download as excel

models	DCA-S$^3$MAMC $(\%)$	MAMC $(\%)$	$\nu$-SVM $(\%)$
Tryroid	92.59	85.19	86.29
Ionosphere	83.37	71.43	71.74
Sonar	60.45	55.56	53.89
Cancer	93.15	89.88	84.52
Heart	85.19	74.31	75.49
Hepatitis	73.33	64.44	71.11
Vote	93.65	86.95	89.68
Synthesis	91.56	70.39	63.66

Table 3. Comparisons of the S$^3$MAMC with other semi-supervised learning methods by accuracy (ACC)

models	MIQP-S$^3$MAMC $(\%)$	DCA-S$^3$MAMC $(\%)$	MILP-S$^3$VM $(\%)$	VS$^3$VM $(\%)$
Ionosphere	86.69	87.61	89.40	87.36
Sonar	63.02	62.40	78.10	66.12
Cancer	96.35	93.76	96.60	97.46
Heart	84.79	86.40	84.00	84.70
Hepatitis	78.65	73.66	70.36	65.13
Synthesis	93.25	92.50	81.11	85.67

Table Options

Download as excel

models	MIQP-S$^3$MAMC $(\%)$	DCA-S$^3$MAMC $(\%)$	MILP-S$^3$VM $(\%)$	VS$^3$VM $(\%)$
Ionosphere	86.69	87.61	89.40	87.36
Sonar	63.02	62.40	78.10	66.12
Cancer	96.35	93.76	96.60	97.46
Heart	84.79	86.40	84.00	84.70
Hepatitis	78.65	73.66	70.36	65.13
Synthesis	93.25	92.50	81.11	85.67

[1]	Yves Dumont, Frederic Chiroleu. Vector control for the Chikungunya disease. Mathematical Biosciences & Engineering, 2010, 7 (2) : 313-345. doi: 10.3934/mbe.2010.7.313
[2]	A. K. Misra, Anupama Sharma, Jia Li. A mathematical model for control of vector borne diseases through media campaigns. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1909-1927. doi: 10.3934/dcdsb.2013.18.1909
[3]	Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[4]	Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[5]	Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781
[6]	Carlos Fresneda-Portillo, Sergey E. Mikhailov. Analysis of Boundary-Domain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3059-3088. doi: 10.3934/cpaa.2019137

2019 Impact Factor: 1.366

Tools

Metrics

Tools

Article outline

Figures and Tables

2019 Impact Factor: 1.366

Tools

Figures and Tables

2019 Impact Factor: 1.366

American Institute of Mathematical Sciences

A new semi-supervised classifier based on maximum vector-angular margin

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

A new semi-supervised classifier based on maximum vector-angular margin

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors