臺灣博碩士論文加值系統

支撐向量法(support vector machines) 是資料分類(data classification) 的一種有效的方法.它不僅有紮實的理論基礎而且應用於實際問題不輸於類神經網路(neural networks) 或決策樹(decision trees)等其他方法.這篇論文研究加快支撐向量法的訓練及發展新的應用.

分段法(decomposition methods)是目前訓練支撐向量法主要的方法之一.各種分段法主要差別在於計算過程變數選擇(working set selection)的方式.目前的方法及分析通常僅考慮特定的選取方式.
本論文對支撐向量法的依序最佳化(Sequential Minimal Optimization, SMO)分段法提出一般性的選擇方式並作完整的探討.
主要結果包括1)簡明的極限收斂證明(asymptotic convergence proof), 2)快取(caching)及變數移除(shrinking)的理論說明,及3)直線收斂速率(linear convergence)的證明.並討論其他支撐向量法的變形.因此所有合乎本文的變數選擇方式都能應用所有的理論結果.

在實作上SMO分段法主要選擇抵觸最佳解的變數,這和利用目標函數(objective function)一級差異(first order information)
[即梯度(gradient)]是相同的.經由先前所述一般化的變數選取探討,
本論文提出利用二級差異(second order information)的方法.這方法能符合先前所述的理論性質,而且此方法也能應用於非有限核心陣列(indefinite kernel matrices).實驗證明新的方法比原先的方法更快速.

最後我們將支撐向量法應用在醫學影像上脊柱(spinal cord)的標定.過去的做法通常需要專家提供具體的知識.用支撐向量法可以建立自動的系統.支撐向量法標定的結果由專家評定為成功,需修改,或失敗.經由漸進式學習(incremental learning)加強,支撐向量法可得到94.67%的成功率, 4.47%需修改,及0.96%失敗率.支撐向量法在醫學影像標定上會是有用的方法.

Support vector machines (SVMs) have been an effective technique for data classification.Not only it has a solid theoretical foundation, practical comparisons have also
shown that SVM is competitive with existing methods such as neural networks and decision trees. This thesis studies fast training of SVM and develops new SVM applications.

Decomposition methods are currently one of the major methods for training support vector machines. They vary mainly according to different working set selections. Existing implementations and analysis usually consider some specific selection rules. This thesis first gives a comprehensive study on Sequential Minimal Optimization (SMO)-type decomposition methods under a general and flexible way of choosing the working set. Main results include: 1) a simple asymptotic convergence proof, 2) a general explanation of the shrinking and caching techniques, and 3) the linear convergence of the method.
Extensions to some SVM variants are also discussed.
Thus, all results here apply to any SMO-type implementation whose selection rule meets the criteria of this work.

For practical implementations, SMO-decomposition methods mainly select working sets via the violation of the optimality condition, which also corresponds to first order
(i.e., gradient) information of the objective function.
Following the general framework of SMO-type methods discussed in this thesis, we develop a simple working set selection using second order information. Thus, theoretical properties such as linear convergence are established. It can be extended for indefinite kernel matrices. Experiments demonstrate that the proposed method is faster than existing selection methods using first order information.

We then apply SVMs to spinal canal segmentation, a medical image application. Past work usually requires substantial knowledge form human experts, but using SVM, we build an
automatic system. Predicted results are evaluated by human experts and classified as successful, editable or unsuccessful. We can further improve SVM classifiers by incremental learning, where new training data are added
and unnecessary ones are removed. The SVM classifier achieves 94.67% successful, 4.47% editable, and 0.96%unsuccessful rate without human interventions. Our system demonstrates that SVM is a useful tool for medical image segmentation.

口試委員會審定書 i
中文摘要 ii
ABSTRACT iii
LIST OF FIGURES viii
LIST OF TABLES x
CHAPTER
I. Introduction 1
II. Basic Concepts of SVM 3

2.1 Linear Separating Hyperplane with Maximal Margin 3
2.2 Mapping Data to Higer Dimensional Spaces 4
2.3 The Dual Problem 7
2.4 Kernel and Decision Functions 9
2.5 Parameter Selection 11

III. A Study on SMO-type Decomposition Methods for Support
Vector Machines 13

3.1 SMO-type Decomposition Methods 13
3.2 Existing and New Working Set Selection for SMO-type Methods 16
3.2.1 Existing Selections 16
3.2.2 A General Working Set Selection for SMO-type De-
composition Methods 19
3.3 Asymptotic Convergence 21
3.3.1 Solving the sub-problem 21
3.3.2 Proof of Asymptotic Convergence 26
3.4 Stopping Condition, Shrinking and Caching 32
3.4.1 Stopping Condition and Finite Termination 35
3.4.2 Shrinking and Caching 38
3.5 Convergence Rate 42
3.6 Extensions 48
3.6.1 Support Vector Regression and One-class SVM 48
3.6.2 Extension to
u-SVM 51
3.7 Discussion and Conclusions 54
3.7.1 Faster Training via a Better Selection Rule 54
3.7.2 Necessary Conditions for the Convergence 55
3.8 Supplement Material 57
3.8.1 Counter Example of ALAL^*=0 58
3.8.2 Counter Example of Theorem 1 59

IV. Working Set Selection Using Second Order Information for
Training Support Vector Machines 61

4.1 Existing and New Working Set Selections 61
4.1.1 A New Working Set Selection 63
4.1.2 Non-Positive Definite Kernel Matrices 66
4.2 Theoretical Properties 69
4.3 Experiments 72
4.3.1 Data and Experimental Settings 73
4.4 Maintaining Feasibility in Sub-problems for Working Set Se-
selections 83
4.4.1 Solutions of (4.5) and (4.22) in final iterations 84
4.4.2 Experiments 87
4.4.3 Sub-problems Using First Order Information 89
4.5 Discussion and Conclusions 90
4.6 Supplement Material 91
4.6.1 WSS 1 Solves Problem (4.1): the Proof 91
4.6.2 Pseudo Code of Algorithms 3 and WSS 6 92

V. Automatic Spinal Canal Segmentation of CT Images by Support
Vector Machines 95
5.1 Medical Image Segmentation 96
5.2 Methods and Materials 98
5.2.1 Data 99
5.2.2 Image Features as Trainging Data 100
5.2.3 Training/Prediction via SVM 103
5.2.4 Post Processing 105
5.2.5 Evaluation 105
5.2.6 Incremental Learning 106
5.2.7 Testing Variants of CT Images 106
5.3 Results 107
5.3.1 Performance of Different Training Settings 107
5.3.2 Improving Performance by Incremental Learing 108
5.3.3 Testing CT Images from Other Hospitals 110
5.4 Conclusions and Discussion 111

VI. Discussion and Conclusions 113

[1] R. Adams and L. Bischof.
Seeded region growing.
IEEE Transactions on Pattern Analysis and Machine
Intelligence, 16(6):0 641--647, 1994.

[2] M. N. Ahmed and A. A. Farag.
Volume segmentation of CT/MRI images using multiscale features, self-organizing principal components analysis (SOPCA), and self-organizing
feature map (SOFM).
In Proc. of the ICNN97, volume III, pages 1373--1378, 1997.

[3] N. Archip, P.-J. Erard, M. Egmont-Petesen, J.-M. Haefliger, and J.-F. Germond.
A knowledge-based approach to automatic detection of the spinal cord
in CT images.
IEEE Transactions on Medical Imaging, 21(12): 1504--1516, Dec. 2002.

[4] R. R. Bailey, E. J. Pettit, R. T. Borochoff, M. T. Manry, and X. Jiang.
Automatic recognition of USGS land use/cover categories using statistical and neural networks classifiers.
In SPIE OE/Aerospace and Remote Sensing, Bellingham, WA, 1993.
SPIE.

[5] B. E. Boser, I. Guyon, and V. Vapnik.
A training algorithm for optimal margin classifiers.
In Proceedings of the Fifth Annual Workshop on Computational
Learning Theory, pages 144--152. ACM Press, 1992.

[6] G. Bueno, O. Musse, F. Heitz, and J.-P. Armspach.
3D watershed-based segmentation of internal structures within MR
brain images.
In Proc. SPIE, Medical images 2000: Image processing, volume
3797, pages 906--916, 2000.

[7] S. S. C. Burnett, G. Startkschall, C. W. Stevens, and Z. Liao.
A deformable-model approach to semi-automatic segmentation of CT images demonstrated by application to the spinal canal.
Medical Physics, 31(2): 251--263, Feb. 2004.

[8] S. Cagnoni, A. B. Dobrzeniecki, R. Poli, and J. C. Yanch.
Genetic algorithm-based interactive segmentation of 3D medical
images. Image and Vision Computation, 17(12):881--895, 1999.

[9] V. Chalana, M. Sannella, and D. R. Haynor.
General-purpose software tool for serial segmenation of stacked
images. In Proc. SPIE, Medical Images 2000: Image processing, volume
3979, pages 192--203, 2000.

[10] C.-C. Chang and C.-J. Lin.
LIBSVM: a library for support vector machines,
2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.

[11] C.-C. Chang and C.-J. Lin.
Training nu-support vector classifiers: Theory and algorithms.
Neural Computation, 13 (9): 2119--2147, 2001.

[12] C.-C. Chang, C.-W. Hsu, and C.-J. Lin.
The analysis of decomposition methods for support vector machines.
IEEE Transactions on Neural Networks, 11(4): 1003--1008, 2000.

[13] Y.-L. Chang and X. Li.
Adaptive image region-growing.
IEEE Transactions on Image Processing, 3(6): 868--872, 1994.

[14] C. W. Chen, J. Luo, and K. J. Parker.
Image segmentation via adaptive K-mean clustering and
knowledge-based morphological operations with biomedical applications.
IEEE Transactions on Image Processing, 7(12): 1673--1683, Dec. 1998.

[15] P.-H. Chen, R.-E. Fan, and C.-J. Lin.
A study on SMO-type decomposition methods for support vector
machines. IEEE Transactions on Neural Networks, 17: 893--908,
July 2006. URL http://www.csie.ntu.edu.tw/~cjlin/papers/generalSMO.pdf.

[16] C. Cortes and V. Vapnik.
Support-vector network. Machine Learning, 20: 273--297, 1995.

[17] C. Cortes, P. Haffner, and M. Mohri.
Positive definite rational kernels.
In Proceedings of the 16th Annual Conference on Learning
Theory, pages 41--56, 2003.

[18] D. J. Crisp and C. J. C. Burges.
A geometric interpretation of nu-SVM classifiers.
In S. Solla, T. Leen, and K.-R. Muller, editors, Advances
in Neural Information Processing Systems, volume 12, Cambridge, MA, 2000.
MIT Press.

[19] C. L. B. D. J. Newman, S. Hettich and C. J. Merz.
UCI repository of machine learning databases.
Technical report, University of California, Irvine, Dept. of
Information and Computer Sciences, 1998.
URL http://www.ics.uci.edu/~mlearn/MLRepository.html.

[20] R.-E. Fan, P.-H. Chen, and C.-J. Lin.
Working set selection using second order information for training
SVM. Journal of Machine Learning Research, 6: 1889--1918,
2005. URL http://www.csie.ntu.edu.tw/~cjlin/papers/quadworkset.pdf.

[21] J. J. Fu, S.-K. Lee, S. T. Wong, J.-Y. Yeh, A.-H. Wang, and H. Wu.
Image segmentation feature selection and pattern classification for
mammographic microcalcification.
Computerized Medical Imaging and Graphics, 29, 2005.

[22] R. C. Gonzalez and R. E. Woods.
Digital Image Processing, Second Edition.
Prentice-Hall, Inc., New Jersey, 2002.

[23] T. K. Ho and E. M. Kleinberg.
Building projectable classifiers of arbitrary complexity.
In Proceedings of the 13th International Conference on
Pattern Recognition, pages 880--885, Vienna, Austria, August 1996.

[24] C.-W. Hsu, C.-C. Chang, and C.-J. Lin.
A practical guide to support vector classification.
Technical report, Department of Computer Science, National Taiwan
University, 2003.
URL http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf.

[25] D. Hush and C. Scovel.
Polynomial-time decomposition algorithms for support vector machines.
Machine Learning, 51:51--71, 2003.
URL http://www.c3.lanl.gov/~dhush/machine_learning/svm_decomp.ps.

[26] T. Joachims.
Making large-scale SVM learning practical.
In B. Scholkopf, C. J. C. Burges, and A. J. Smola, editors,
Advances in Kernel Methods - Support Vector Learning, Cambridge, MA,
1998. MIT Press.

[27] T. N. Jones and D. N. Metaxas.
Automated 3D segmentation using deformable models and fuzzy
affinity. In IPMI, pages 113--126, 1997.

[28] S. S. Keerthi and E. G. Gilbert.
Convergence of a generalized SMO algorithm for SVM classifier
design. Machine Learning, 46: 351--360, 2002.

[29] S. S. Keerthi and C.-J. Lin.
Asymptotic behaviors of support vector machines with Gaussian
kernel. Neural Computation, 15 (7): 1667--1689, 2003.

[30] S. S. Keerthi and C. J. Ong.
On the role of the threshold parameter in SVM training algorithms.
Technical Report CD-00-09, Department of Mechanical and Production
Engineering, National University of Singapore, Singapore, 2000.
URL http://guppy.mpe.nus.edu.sg/~mpessk/papers/decomp.ps.gz.

[31] S. S. Keerthi, S. K. Shevade, C. Bhattacharyya, and K. R. K. Murthy.
Improvements to Platt''s SMO algorithm for SVM classifier
design. Neural Computation, 13: 637--649, 2001.


[32] D. Lai, N. Mani, and M. Palaniswami.
Increasing the step of the Newtonian decomposition method for
support vector machines.
Technical Report MECSE-29-2003, Dept. Electrical and Computer Systems
Engineering Monash University, Australia, 2003.

[33] D. Lai, N. Mani, and M. Palaniswami.
A new method to select working sets for faster training for support
vector machines.
Technical Report MESCE-30-2003, Dept. Electrical and Computer Systems
Engineering Monash University, Australia, 2003.

[34] S. Li, T. Fevens, A. Krzyzak, and S. Li.
An automatic variational level set segmentation framework for
computer aided dental x-rays analysis in clinical environments.
Computerized Medical Imaging and Graphics, pages 1--10, 2006.

[35] C.-J. Lin.
Formulations of support vector machines: a note from an optimization
point of view. Neural Computation, 13 (2): 307--317, 2001.

[36] C.-J. Lin.
A formal analysis of stopping criteria of decomposition methods for
support vector machines.
IEEE Transactions on Neural Networks, 13(5): 1045--1052, 2002.
URL http://www.csie.ntu.edu.tw/~cjlin/papers/stop.ps.gz.


[37] C.-J. Lin.
On the convergence of the decomposition method for support vector
machines. IEEE Transactions on Neural Networks, 12(6): 1288--1298, 2001.
URL http://www.csie.ntu.edu.tw/~cjlin/papers/conv.ps.gz.

[38] C.-J. Lin.
Asymptotic convergence of an SMO algorithm without any assumptions.
IEEE Transactions on Neural Networks, 13(1): 248--250, 2002.
URL http://www.csie.ntu.edu.tw/~cjlin/papers/q2conv.pdf.

[39] C.-J. Lin.
Linear convergence of a decomposition method for support vector
machines. Technical report, Department of Computer Science, National Taiwan
University, 2001.
URL http://www.csie.ntu.edu.tw/~cjlin/papers/linearconv.pdf.

[40] C.-J. Lin.
A Guide to Support Vector Machines.

[41] H.-T. Lin and C.-J. Lin.
A study on sigmoid kernels for SVM and the training of non-PSD
kernels by SMO-type methods.
Technical report, Department of Computer Science, National Taiwan
University, 2003.
URL http://www.csie.ntu.edu.tw/~cjlin/papers/tanh.pdf.

[42] N. List and H. U. Simon.
A general convergence theorem for the decomposition method.
In Proceedings of the 17th Annual Conference on Learning
Theory, pages 363--377, 2004.

[43] S. Lucidi, L. Palagi, M. Sciandrone, and A. Risi.
A convergent decomposition algorithm for support vector machines.
Computational Optimization and Applications, 2006.
To appear.

[44] T. McInerney and D. Terzopoulos.
Deformable models in medical image analysis: A survey.
Medical Image Analysis, 1 (2): 91--108,
1996.

[45] C. A. Micchelli.
Interpolation of scattered data: distance matrices and conditionally
positive definite functions.
Constructive Approximation, 2: 11--22, 1986.

[46] D. Michie, D. J. Spiegelhalter, and C. C. Taylor.
Machine Learning, Neural and Statistical Classification.
Prentice Hall, Englewood Cliffs, N.J., 1994.
Data available at
http://www.ncc.up.pt/liacc/ML/statlog/datasets.html.

[47] E. Osuna, R. Freund, and F. Girosi.
Training support vector machines: An application to face detection.
In Proceedings of CVPR''97, pages 130--136, New York, NY,
1997. IEEE.

[48] L. Palagi and M. Sciandrone.
On the convergence of a modified version of SVM-light
algorithm. Optimization Methods and Software, 20 (2-3):
315--332, 2005.

[49] D. L. Pham and J. L. Prince.
An adaptive fuzzy c-means algorithm for image segmentation in the
presence of intensity inhomogeneities.
In Medical Images 1998: Image processing, Proc. SPIE, volume
3338, pages 555--563, 1998.

[50] D. L. Pham, C. Xu, and J. L. Prince.
Current methods in medical image segmentation.
Annual Reviews of Biomedical Engineering, 2:315--337, 2000.

[51] J. C. Platt.
Fast training of support vector machines using sequential minimal
optimization.
In B. Scholkopf, C. J. C. Burges, and A. J. Smola, editors,
Advances in Kernel Methods - Support Vector Learning, Cambridge, MA,
1998. MIT Press.

[52] D. Prokhorov.
IJCNN 2001 neural network competition.
Slide presentation in IJCNN''01, Ford Research Laboratory, 2001.
http://www.geocities.com/ijcnn/nnc_ijcnn01.pdf .

[53] P. K. Sahoo, S. Soltani, A. K. Wong, and Y. C. Chen.
A survey of thresholding techniques.
Computer Vision, Graphics and Image Processing, 41:
233--260, 1988.

[54] B. Scholkopf, A. Smola, R. C. Williamson, and P. L. Bartlett.
New support vector algorithms.
Neural Computation, 12: 1207--1245, 2000.

[55] B. Scholkopf, J. C. Platt, J. Shawe-Taylor, A. J. Smola, and R. C.
Williamson.
Estimating the support of a high-dimensional distribution.
Neural Computation, 13(7): 1443--1471, 2001.

[56] J. Sijbers, P. Scheunders, M. Verhoye, A. van der Linden, D. van Dyck, and
E. Raman. Watershed based segmentation of 3D MR data for volume
quantization. Magnetic Resonance Imaging, 15 (4): 69--688, 1997.

[57] H. U. Simon.
On the complexity of working set selection.
In Proceedings of the 15th International Conference on
Algorithmic Learning Theory (ALT 2004), 2004.

[58] V. Vapnik.
The Nature of Statistical Learning Theory.
Springer-Verlag, New York, NY, 1995.

[59] V. Vapnik.
Statistical Learning Theory.
Wiley, New York, NY, 1998.

[60] S. Wegner, T. Harms, H. Oswald, and E. Fleck.
The watershed transformation on graphs for segmetnation of CT
images. In Proc. of the 13th ICPR, pages 498--502, 1996.

[61] Y. Zhan and D. Shen.
Deformable segmentation of 3-D ultrasound prostate images using
statistical texture machine method.
IEEE Transactions on Medical Imaging, 25(3): 256--272, Mar. 2006.