跳到主要內容

臺灣博碩士論文加值系統

(44.200.77.92) 您好!臺灣時間:2024/03/01 09:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:許智瑋
研究生(外文):Chih-Wei Hsu
論文名稱:雙類及多類支向機之分解方法
論文名稱(外文):Decomposition Methods for Binary and Multi-class Support Vector Machines
指導教授:林智仁林智仁引用關係
指導教授(外文):Chih-Jen Lin
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:英文
論文頁數:63
中文關鍵詞:支持向量機分解方法多類分類
外文關鍵詞:support vector machinesdecomposition methodsmulti-class classification
相關次數:
  • 被引用被引用:2
  • 點閱點閱:236
  • 評分評分:
  • 下載下載:26
  • 收藏至我的研究室書目清單書目收藏:0
目前解支向機問題主要是用分解式方法. 這方法的重要關鍵是在工作集合的選取. 在此論文的第一部份我們從整個有界支向機分解方法之設計過程及實驗分析的結果而提出一個簡單的選取方法, 這方法會使困難問題的收斂變快. 根據不同類型問題的實驗結果數據顯示所提出之方法是可行的.
論文的第二部份中我們關心多類支向機之分解方法. 原來的支向機只能做兩類別的分類問題, 如何使支向機可以有效地延伸到多類分類問題仍然是目前的研究重點. 很多方法被提出來: 其中有些人是把很多的雙類支向機整合成一個多類支向機, 其他人則是一次就考慮所有的類別. 但是解決多類分類問題所需的計算量龐大, 關於在大型問題上的比較並沒有被仔細的探討. 尤其是第二種方法需要解一個更大的最佳化問題, 以前的實驗都只限在小型問題上. 本論文中我們提出兩種一次解決式方法之分解方法實作. 然後將之與其他三種合併式方法: 一對全部, 一對一和直接不循環圖支向機來比較. 結果顯示一對一和直接不循環圖支向機較適合於實際情況使用, 另外也顯示一次解決式方法的支持向量較少.

The decomposition method
is currently one of the major
methods for solving
support vector machines (SVM).
An important issue of this method
is the selection of working sets.
In the first part of this thesis through the design of
decomposition methods
for bound-constrained SVM formulations
and from the experimental analysis
we propose a simple
selection of the working set
which leads to faster
convergences for difficult cases.
Numerical experiments on different
types of problems are conducted
to demonstrate the viability of the
proposed method.
The second part of this thesis focuses on decomposition methods
for multi-class SVM.
As SVM was originally
designed for binary classification,
how to effectively extend it for
multi-class classification is still
an on-going research issue.
Several methods have been proposed where
typically we construct a multi-class classifier
by combining several binary classifiers. Some
authors also proposed methods that consider all
classes of data at once. As it is computationally
more expensive on solving multi-class problems,
comparisons on these methods using large-scale
problems have not been seriously conducted.
Especially for methods solving multi-class SVM
in one step, a much larger optimization
problem is required
so up to now experiments
are limited to small data sets.
In this thesis we give decomposition
implementation for
two such ``all-together" methods:
\cite{VV98a,JW98a} and
\cite{KC00a}. We then
compare their
performance with three methods
based on binary classification:
``one-against-all,'' ``one-against-one,''
and DAGSVM \cite{JP00a}.
Our
experiments indicate that the ``one-against-one'' and DAG
methods are
more suitable for practical use than the
other methods.
Results also show that for large problems
methods by considering all data at once in general need
fewer support vectors.

ABSTRACT ii
ACKNOWLEDGEMENTS iii
LIST OF FIGURES vi
LIST OF TABLES vii
CHAPTER
I. Introduction 1
II. The SVM Problem 5
2.1 Basic Concepts of SVM 5
2.2 Decompositon Algorithms 9
III. Selection of the Working Set 12
IV. Computational Experiments on Algorithm III.1 23
4.1 Numerical Experiments on BSVM 23
4.2 Using Algorithm III.1 for Standard SVM Formulation 31
V. Five Methods for Multi-class SVM 33
5.1 One-against-all Method 33
5.2 One-against-one Method 34
5.3 DAGSVM Method 35
5.4 An Method by Considering All Data at Once And A Decomposition Implementation 36
5.5 Method by Crammer and Singer 43
VI. Numerical Experiments on Multi-class SVM 47
6.1 Data and Implementation 47
6.2 Results and Discussions 49
VII. Conclusions and Discussions 59

K.P. Bennett, D.Hui, and L.Auslender. On support vector decision trees for datab
ase marketing.
Department of Mathematical Sciences Math Report No. 98-100,
Rensselaer Polytechnic Institute, Troy, NY 12180, Mar. 1998.
C.L. Blake and C.J. Merz. UCI repository of machine learning databases.
Technical report, University of California, Department of Information
and Computer Science, Irvine, CA, 1998.
Available at
http://www.ics.uci.edu/""mlearn/MLRepository.html.
B.Boser, I.Guyon, and V.Vapnik. A training algorithm for optimal margin classifi
ers.
In Proceedings of the Fifth Annual Workshop on Computational
Learning Theory, 1992.
L.Bottou, C.Cortes, J.Denker, H.Drucker, I.Guyon, L.Jackel, Y.LeCun, U.Muller,
E.Sackinger, P.Simard, and V.Vapnik.
Comparison of classifier methods: a case study in handwriting digit
recognition.In International Conference on Pattern Recognition, pages
77--87. IEEE Computer Society Press, 1994.
E.J. Bredensteiner and K.P. Bennett. Multicategory classification by support vec
tor machines.
Computational Optimizations and Applications, pages 53--79,
1999.
M.P.S. Brown, W.N. Grundy, D.Lin, N.Cristianini, C.Sugnet, T.S. Furey, J.M.Ares
, and D.Haussler.
Knowledge-based analysis of microarray gene expression data using
support vector machines.
PNAS, 97(1):262--267, 2000.
C.J.C. Burges. A tutorial on support vector machines for pattern recognition.
Data Mining and Knowledge Discovery, 2(2):121--167, 1998.
C.-C. Chang, C.-W. Hsu, and C.-J. Lin. The analysis of decomposition methods for
support vector machines.IEEE Trans. Neural Networks, 11(4):1003--1008, 2000.
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.
K.K. Chin. Support vector machines applied to speech pattern classification.
Master's thesis, University of Cambridge, 1998.
C.Cortes and V.Vapnik. Support-vector network.
Machine Learning, 20:273--297, 1995.
K.Crammer and Y.Singer. On the learnability and design of output codes for multi
class
problems.
In Computational Learing Theory, pages 35--46, 2000.
K.Crammer and Y.Singer. Ultraconservative online algorithms for multiclass probl
ems.
Technical report, School of Computer Science and Engineering, Hebrew
University, 2001.
N.Cristianini and J.Shawe-Taylor. An Introduction to Support Vector Machines.
Cambridge University Press, Cambridge, UK, 2000.
D.DeCoste and B.Sch\"olkopf. Training invariant support vector machines.
Machine Learning, 2001.
To appear.
R.Fletcher. Practical Methods of Optimization.
John Wiley and Sons, 1987.
J.Friedman. Another approach to polychotomous classification.
Technical report, Department of Statistics, Stanford University,
1996.
Available at http://www-stat.stanford.edu/reports/friedman/poly.ps.Z.
T.-T. Friess, N.Cristianini, and C.Campbell. The kernel adatron algorithm: a fas
t and simple learning procedure
for support vector machines.
In Proceedings of 15th Intl. Conf. Machine Learning.
Morgan Kaufman Publishers, 1998.
Y.Guermeur. Combining discriminant models with new multiclass svms.
Neuro COLT Technical Report NC-TR-00-086, LORIA Campus Scientifique,
2000.
T.K. Ho and E.M. Kleinberg. Building projectable classifiers of arbitrary comple
xity.
In Proceedings of the 13th International Conference on
Pattern Recognition, pages 880--885, Vienna, Austria, August 1996.
C.-W. Hsu and C.-J. Lin. A comparison on methods for multi-class support vector
machines.
Technical report, Department of Computer Science and Information
Engineering, National Taiwan University, Taipei, Taiwan, 2001.
C.-W. Hsu and C.-J. Lin. A simple decomposition method for support vector machin
es.
Machine Learning, 2001.
To appear.
T.Joachims. Making large-scale SVM learning practical.
In B.Sch\"olkopf, C.J.C. Burges, and A.J. Smola, editors,
Advances in Kernel Methods - Support Vector Learning, Cambridge, MA, 1998.
MIT Press.
T.Joachims. Transductive inference for text classification using support vector
machines.
In Proceedings of International Conference on Machine Learning,
1999.
T.Joachims, 2000. Private communication.
J.Kindermann, E.Leopold, and G.Paass. Multi-class classification with error corr
ecting codes.
In E.Leopold and M.Kirsten, editors, Treffen der GI-Fachgruppe
1.1.3, Maschinelles Lernen, 2000.
GMD Report 114.
S.Knerr, L.Personnaz, and G.Dreyfus. Single-layer learning revisited: a stepwise
procedure for building
and training a neural network.
In J.Fogelman, editor, Neurocomputing: Algorithms,
Architectures and Applications. Springer-Verlag, 1990.
U.Kreel. Pairwise classification and support vector machines.
In B.Sch\"olkopf, C.J.C. Burges, and A.J. Smola, editors,
Advances in Kernel Methods --- Support Vector Learning, pages 255--268,
Cambridge, MA, 1999. MIT Press.
P.Laskov. An improved decomposition algorithm for regression support vector
machines.
In Workshop on Support Vector Machines, NIPS99, 1999.
Y.LeCun, L.Jackel, L.Bottou, A.Brunot, C.Cortes, J.Denker, H.Drucker, I.Guyon,
U.Muller, E.Sackinger, P.Simard, and V.Vapnik.
Comparison of learning algorithms for handwritten digit recognition.
In F.Fogelman and P.Gallinari, editors, International Conference
on Artificial Neural Networks, pages 53--60, Paris, 1995. EC2 \& Cie., 1995.
C.-J. Lin. On the convergence of the decomposition method for support vector
machines.
Technical report, Department of Computer Science and Information
Engineering, National Taiwan University, Taipei, Taiwan, 2000.
To appear in IEEE Transactions on Neural Networks.
C.-J. Lin. Formulations of support vector machines: a note from an optimization
point of view.
Neural Computation, 13(2):307--317, 2001.
C.-J. Lin. Stopping criteria of decomposition methods for support vector
machines: a theoretical justification.
Technical report, Department of Computer Science and Information
Engineering, National Taiwan University, Taipei, Taiwan, 2001.
C.-J. Lin and J.J. Mor\'e. Newton's method for large-scale bound constrained pro
blems.
SIAM J. Optim., 9:1100--1127, 1999.
Software available at http://www.mcs.anl.gov/""more/tron.
O.L. Mangasarian and D.R. Musicant. Successive overrelaxation for support vector
machines.
IEEE Trans. Neural Networks, 10(5):1032--1037, 1999.
N.Matic, I.Guyon, J.Denker, and V.Vapnik. Writer adaptation for on-line handwrit
ten character recognition.
In I.C.S. Press, editor, In Second International Conference on
Pattern Recognition and Document Analysis, pages 187--191, Tsukuba, Japan,
1993.
E.Mayoraz and E.Alpaydin. Support vector machines for multi-class classification
.
In IWANN (2), pages 833--842, 1999.
D.Michie, D.J. Spiegelhalter, and C.C. Taylor. Machine Learning, Neural and Sta
tistical Classification.
Prentice Hall, Englewood Cliffs, N.J., 1994.
Data available at anonymous ftp: ftp.ncc.up.pt/pub/statlog/.
K.-R. M\"uller, A.Smola, G.R\"atsch, B.Sch\"ol\-kopf, J.Kohlmorgen, and V.Vapni
k.
Predicting time series with support vector machines.
In B.Sch\"olkopf, C.J.C. Burges, and A.J. Smola, editors,
Advances in Kernel Methods - Support Vector Learning, pages 243--254,
Cambridge, MA, 1999. MIT Press.
P.M. Murphy and D.W. Aha. UCI repository of machine learning databases.
Technical report, University of California, Department of Information
and Computer Science, Irvine, CA, 1994.
Data available at
http://www.ics.uci.edu/""mlearn/MLRepository.html.
E.Osuna, R.Freund, and F.Girosi. Support vector machines: Training and applicati
ons.
AI Memo 1602, Massachusetts Institute of Technology, 1997.
E.Osuna, R.Freund, and F.Girosi. Training support vector machines: An applicatio
n to face detection.
In Proceedings of CVPR'97, 1997.
C.Papageorgiou, M.Oren, and T.Poggio. A general framework for object detection.
In International Conference on Computer Vision ICCV'98, 1998.
J.C. Platt. Fast training of support vector machines using sequential minimal
optimization.
In B.Sch\"olkopf, C.J.C. Burges, and A.J. Smola, editors,
Advances in Kernel Methods - Support Vector Learning, Cambridge, MA, 1998.
MIT Press.
J.C. Platt, N.Cristianini, and J.Shawe-Taylor. Large margin DAGs for multiclass
classification.
In Advances in Neural Information Processing Systems,
volume12, pages 547--553. MIT Press, 2000.
M.J.D. Powell. On search directions for minimization.
Math. Programming, 4:193--201, 1973.
M.Rychetsky, S.Ortmann, and M.Glesner. Construction of a support vector machine
with local experts.
In Workshop on Support Vector Machines at the International
Joint Conference on Artificial Intelligence (IJCAI 99), 1999.
C.Saunders, M.O. Stitson, J.Weston, L.Bottou, B.Sch\"olkopf, and A.Smola.
Support vector machine reference manual.
Technical Report CSD-TR-98-03, Royal Holloway, University of London,
Egham, UK, 1998.
B.Sch\"olkopf, C.J.C. Burges, and A.J. Smola, editors. Advances in Kernel Metho
ds - Support Vector Learning.
MIT Press, Cambridge, MA, 1998.
M.O. Stitson, A.Gammerman, V.Vapnik, V.Vovk, C.Watkins, and J.Weston. Support ve
ctor regression with ANOVA decomposition kernels.
In Sch\"olkopf etal. BS98a, pages 285--292.
R.Vanderbei. LOQO: An interior point code for quadratic programming.
Technical Report SOR 94-15, Statistics and Operations Research,
Princeton University, 1994.
revised November, 1998.
V.Vapnik. The Nature of Statistical Learning Theory.
Springer-Verlag, New York, NY, 1995.
V.Vapnik. Statistical Learning Theory.
Wiley, New York, NY, 1998.
J.Weston, 2001. Private communication.
J.Weston and C.Watkins. Multi-class support vector machines.
Technical Report CSD-TR-98-04, Royal Holloway, 1998.
A.Zien, G.R\"atsch, S.Mika, B.Sch\"olkopf, C.Lemmen, A.Smola, T.Lengauer, and K
.-R. M\"uller.
Engineering support vector machine kernels that recognize translation
initiation sites.
In German Conference on Bioinformatics, 1999.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top