REP - SVM - 002, 2011 1 SV M Multiclass 를이용한데이터학습및분류 김선영 부산대학교컴퓨터공학과 s.y.kim@pusan.ac.kr ABSTRACT 여러그룹의데이터를알고있을때, 새로운데이터가나타나면이데이터가어느그룹에가까운지알수있다. 이를기계적으로학습할수있다면, 많은양의데이터가주어졌을때특정데이터들이어느그룹에가까운지쉽게알수있고, 이를통해데이터들을빠르고정확하게분류할수있다. 이러한이유로주어진데이터로기계학습하는모델들이많이제안되었으나, 대부분의학습기법에서경험적리스크와모델복잡도를함께고려하기가어렵다. 그러나 SVM 은이론적으로모델복잡도를측정하는수단인 VC 차원을직접적으로제어할수있으므로, SVM 을이용하여학습및분류하는것이효과적이다. 본보고서에서는데이터를학습하고분류하는데매우효과적인 SVM 을구현한 SVM light 의사용방법을알아보고, 실제로 2 차원데이터를이용하여학습및분류실험을수행하고그결과의의미를해석한다. KEYWORDS SVM, Machine Learning, Data Classification 1 서론 여러특징을가지는데이터들을그특성에따라분류한후, 특정데이터가어느그룹에속하는지쉽게알수있다면데이터들을빠르게분류할수있다. 가령꽃잎의길이가일정이상이고특정색깔을지니며꽃받침의길이가일정이하인꽃들을같은꽃으로분류할수있는것처럼, 데이터들을일정한특징에따라분류한후, 새로운데이터가나타났을때이것이어느그룹에가까운지확인하고자할때사용할수있는방법이기계학습방법이다. 기계학습모델로 MLP, SVM 등의여러가지모델이제안되었으나, 모델의복잡도를측정하기위한수단인 VC 차원을제어할수있는모델로는 SVM이있다. SVM(Support Vector Machine) 은분류와회귀에응용할수있는학습모델로써, Vladimir Vapnik에의해고안되었다 [1]. 처음에 SVM은선형분리가능한여러클래스를구분지으며마진을최대로하는초평면을찾는문제였으나, 이진분류가아닌다중분류를지원하는알고리즘에대한꾸준한연구가진행되면서더효과적으로여러개의클래스를학습할수있게되었다. 본보고서에서는 SVM을구현한오픈소스인 SV M multiclass 를사용하는방법에대해알아보고, 간단한예제로 2차원좌표계의 21개점에대하여학습한후, 추후새로운데이터가입력되었을때이를정확히분류하는지에대해서실험하였다.
REP - SVM - 002, 2011 2 그림 1. SVM 학습을위한간단한예제. 2 차원평면위의점들을두분류로나누고이를 학습한다. 나중에새로운점의좌표가추가되었을때 SVM 이바르게분류하는지확인 한다. 2 SVM light SVM light는패턴인식문제와회귀문제, 랭킹함수의학습문제를위한 Vapnik의 Support Vector Machine을 SVM을 C로구현한것으로, 상업적인용도로사용하거나저자의사전허락없이배포하지만않는다면무료로사용할수있다. Source Code와 Binaries는 SVM light 홈페이지 [2] 에서다운받을수있다. SVM light는다양한운영체제를지원하는데 Windows, Unix, Linux, Cygwin, Mac 에서사용할수있다. 물론각각의운영체제에맞는버전을받아서사용해야한다. SVM light 프로그램의주요특징들은다음과같다 [2]. 1. 분류 (classification) 와회귀 (regression) 문제를푼다. 2. 순위문제 (ranking problems) 를학습한다. 3. 기본커널함수를제공하며, 이를사용자가정의할수도있다. 4. 수백에서수만개의학습예제들을처리할수있다. 5. 수만개의 support vector들을다룰수있다. SVM light는이진분류를기본으로하고있으므로, 본보고서에서는 SVM light에서발전한, 다중분류를지원하고구조화된결과를사용할수있게한 SVM multiclass를사용한다. SVM multicalss 는두가지모듈로구성되어있다. 학습모듈과분류모듈이그것이다. 분류모듈은학습모델에새로운예제를적용할때사용할수있다. 또한 SVM multiclass는 classification, regresion, ranking 등의여러모드를제공하는데, 본보고서에서는데이터를클래스에따라분류하는것이목적이므로 classification mode를사용하여그림 1와같은 2차원평면위의점들을두가지클래스로나누는 toy example을통해 SVM을이용한학습및분류를수행해본다.
REP - SVM - 002, 2011 3 1 1:-6 2:0 1 1:-6 2:-1 2 1:3 2:4 2 1:3 2:5 표 1. 2 차원좌표데이터를 SVM 학습데이터형식으로나타낸것의일부분. x, y 두 특징벡터에대한값이존재하므로 2 차원데이터이다. 2.1 학습데이터의형태 SVM multiclass에서사용하는학습데이터는사용자가직접만들어야하는것으로, 그림 2와같이데이터의양식을갖추어야한다. 각줄은 target class가가장먼저나오고그다음부터는특징벡터와그에해당하는값을열거하는형태이다. 여기서특징벡터의수에따라차원이달라진다. 가령 384 가특정클래스의마지막번호 feature 라면그클래스는 384차원의벡터를가진다고할수있다. 384 차원의특징들을한줄에모두기재해야하느냐의문제는특징에해당하는값에따라다르다. value 가 0.0인특징들은생략해서기록한다. # 뒤의내용은주석처리되는부분이다. <line>.=. <target> <feature>:<value> <feature>:<value>... <target>.=. +1-1 0 <float> <feature>.=. <integer> "qid" <value>.=. <float> <info>.=. <string> <feature>:<value> # <info> 그림 2. SVM multiclass 에서사용하는학습데이터의형식. SVM light 도같은형식 의학습데이터를사용한다. 표 1는그림 1의 2차원좌표데이터들을학습데이터형식으로변환한예제학습데이터이다. 각줄의젤앞숫자는 target을의미한다. 따라서첫째줄의데이터는 1번클래스에속하는데이터이며, 1번특징벡터값이 -6, 2번특징벡터값이 0이다. 2번특징벡터의값이 0이므로생략해도된다. 2 차원좌표계위에있는점은 x, y 값만을가지므로두개의특징벡터를가진다고할수있다. 2.2 SVM multiclass 를이용한학습모델생성 학습데이터를 training file 이라고할경우, 이를 SVM 으로학습한모델을생성하는명령문은다음과 같다. SVM multiclass learn [options] training file(input) model file(output) 여기서중요한것은 option 값이다. 사용할수있는 option 종류는표 3, 표 4 와같다.
REP - SVM - 002, 2011 4 그림 3. 2차원좌표데이터로학습모델을생성하는과정. 학습데이터집합이 2 features, 2 classes로구성되어있음을먼저확인한후, 학습모델을생성한다. -t 옵션을따로주지않았으므로 linear kernel을사용할것임을예상할수있다. 화면에나타나는 svm light에대한정보들을더자세하게알고싶으면 -y 옵션으로그레벨을조절할수있다. 표 3 에나타난파라미터들은자주사용하는옵션들이다. -? 는도움말로써, svm multiclass learn -? 명령문을반환할경우, 사용방법과사용가능한옵션에대한자세한설명을확인할수있다. -y 옵션은화면에얼마나자세하게정보를나타낼것인가에대한수치이다. 레벨을높게설정할수록학습에관한많은정보를확인할수있다. -c 는학습에러와마진간의 trade-off 를조절하는파라미터이다. 이파라미터는실험적으로최적의값을찾을수있다. -t 는 Kernel 옵션의한파라미터이다. 기본은 linear 평면으로, 클래스를단순하게직선으로나눈다. 그러나만약 A클래스가 B 클래스의많은부분을감싸고있는분포를가진다고가정할경우, 이런 linear한평면으로는두클래스를나눌수가없다. 이런경우에는 polynomial 평면을사용하거나, 사용자가정의한 kernel에따라클래스들을분류할수있다. 2.3 SVM multiclass를이용한특징벡터분류 svm multiclass learn을통해학습데이터를학습한모델을얻었다. svm multiclass classify는이학습모델을이용하여새로운데이터가주어졌을때어느클래스에해당하는지분류해준다. 학습모델을 model.dat, 새로운데이터를 newdata.dat라고했을때, 결과 output.dat 는다음과같은명령문을 1 4.714286-4.714286 2-16.380953 16.380953 표 2. 새로운 2 차원좌표데이터. 표 1 의데이터로학습한모델 model.dat 로새로운 데이터가 class 1 에해당하는지확인할수있다.
REP - SVM - 002, 2011 5 그림 4. 그림 3 의학습모델을이용하여새로운데이터 test.dat 를분류하는과정. 통해얻을수있다. svm multiclass classify newdata.dat(input) model.dat(input) output.dat(output) toy example에서는 newdata.dat 에 2가지새로운좌표를추가하였다. 하나는 1 1:-2 2:5 이고, 다른하나는 1 1:3 2:1 이다. 이는 (-2,5), (3,1) 의좌표가모두클래스 1에포함될것이라고예상한것이다. 이를 classify 명령문으로분류하면그결과가 output.dat 파일에나타날것이다. 새로운데이터는첫번째데이터의경우 1번클래스에, 두번째데이터는 2번클래스에가깝기때문에 1번은맞고, 2번은틀린결과가나와야 SVM이바르게클래스를나누었다고볼수있다. classify 명령문을실행한화면은그림 4 와같다. 그림 4와같이 classify 후결과파일에는예상되는클래스와각클래스에해당하는 x w i 값이한줄에함께기록된다. output.dat 파일의각라인은 test.dat 파일과같은순서대로나타나고, 각줄의첫번째값은 SVM이예상한클래스, 그리고그뒤에이어지는수들은각클래스에해당하는판별식값들이다. toy example로사용했던 2차원좌표를대상으로하여분류한결과, 표 2와같은결과파일을얻었다. 그림 4에서도확인할수있듯이 newdata.dat의결과는 50% 의에러율을지니고있다. 1개의데이터는맞고, 다른하나의데이터는틀렸음을확인할수있는데, 정확하게어떤데이터가맞고틀렸는지는콘솔화면에서확인할수없다. 분류결과생성된파일 output.dat 파일을열어보면그림 2과같은결과를볼수있다. 첫번째데이터는클래스 1번에해당하고, 두번째데이터는클래스 2번에해당한다고보고한것을확인할수있다. 처음에입력한데이터는모두클래스 1번에해당한다고했으니, 바른결과를도출했음을알수있다. 클래스번호뒤에이어지는숫자들은각클래스에해당하는결정함수의값들이다. 3 결론 본보고서에서는 SVM(Support Vecter Machine) 에대해서간단하게알아보고, SVM 을구현한 SV M multiclass 의사용방법에대해서조사하였다. SVM 은패턴인식문제, 회귀문제, 랭킹함수학습문제에사용 할수있는효과적인기계학습방법이다. SV M light 는홈페이지에서무료로다운받아서사용해볼
REP - SVM - 002, 2011 6 수있다. 실제로사용할때에는다중분류를지원하는 SV M multiclass 를사용해여러가지클래스로데이터를학습하고분류할수있다. SV M multiclass 을이용해기계학습을수행하기위해서는학습할데이터가필요하다. 학습데이터는일정한양식을가지며, 이에따라사용자가학습데이터를생성하여야한다. 새로운데이터가학습한클래스에분류되는지확인하기위해서는새로운데이터및학습데이터로생성한학습모델및새로운데이터가필요하다. 학습모델생성시, 실험적으로학습에러와마진을최적화하는상수파라미터를결정할수있고, 여러클래스를분류하는초평면함수 kernel을사용자가정의할수도있고기본적으로제공하는함수들을사용할수도있다. 본보고서에서는 2차원좌표위의점 21개를대상으로학습을수행하여학습모델을생성하고, 이를바탕으로정답 1개, 오답 1개의데이터를분류한결과 SVM으로정답을바르게분류하는것을확인하였다. 참고문헌 1. V. Vapnik, The Nature of Statistical Learning Theory, Springer-Verlag, 1995. 2. T. Joachims, Support vector machine, 2008, http://www.cs.cornell.edu/people/tj/svm light/index.html. 3. T. Joachims I. Tsochantaridis, T. Hofmann and Y. Altun., Support vector learning for interdependent and structured output spaces, in Proc. of ICML, 2004, pp. 104 111. 4. T. Joachims, Training linear svms in linear time, in Proc. of KDD, pp. 217 226. 5. T. Joachims, Multi-class support vector machine, 2008, http://www.cs.cornell.edu/people/tj/svm light/svm multi
REP - SVM - 002, 2011 7 General Options -? help -v[0..3] verbosity level( default 1) -y[0..3] verbosity level for svm light (default 0) Learning Options -c float C: trade-off between training error and margin (default 0.01) -p [1,2] L-norm to use for slack variables. Use 1 for L1-norm, use 2 for squared slacks. (default 1) -o [1,2] Rescaling method to use for loss. (default 0) 1: slack rescaling 2: margin rescaling -l [0..] Loss function to use. (default 0) 0: zero/one loss?: see below in application specific options Kernel Options -t int type of kernel function: 0: linear (default) 1: polynomial (s a b + c) d 2: radial basis function exp(-gamma a b 2 ) 3: sigmoid tanh(s a*b + c) 4: user defined kernel from kernel.h -d int parameter d in polynomial kernel -g float parameter gamma in rbf kernel -s float parameter s in sigmoid/poly kernel -r float parameter c in sigmoid/poly kernel -u string parameter of user defined kernel 표 3. svm multiclass learn을실행할때자주사용하는옵션값들. c는학습에러와마진간의 trade-off를조절하는파라미터로써, 실험적으로최적의값을찾는다. -t 는커널옵션중하나로, 여러개의클래스를나누는초평면의함수를어떤모양으로사용할것인지정하는것이다. linear, polynomial, exponential, sigmoid tanh 함수를지원하고그외에는사용자가직접추가할수있다.
REP - SVM - 002, 2011 8 Optimization Options -w [0,..,9] choice of structural learning algorithm (default 4): 0: n-slack algorithm described in [3] 1: n-slack algorithm with shrinking heuristic 2: 1-slack algorithm (primal) described in [4] 3: 1-slack algorithm (dual) described in [4] 4: 1-slack algorithm (dual) with constraint cache [4] 9: custom algorithm in svm struct learn custom.c -e float epsilon: allow that tolerance for termination criterion (default 0.100000) -k [1..] number of new constraints to accumulate before recomputing the QP solution (default 100) (-w 0 and 1 only) -f [5..] number of constraints to cache for each example (default 5) (used with -w 4) -b [1..100] percentage of training set for which to refresh cache when no epsilon violated constraint can be constructed from current cache (default 100%) (used with -w 4) -n [2..q] number of new variables entering the working set in each svm-light iteration (default n = q). Set n q to prevent zig-zagging. -m [5..] size of svm-light cache for kernel evaluations in MB (default 40) (used only for -w 1 with kernels) -h [5..] number of svm-light iterations a variable needs to be optimal before considered for shrinking (default 100) -# int terminate svm-light QP subproblem optimization, if no progress after this number of iterations. (default 100000) Output Options -a string write all alphas to this file after learning (in the same order as in the training set) Application-Specific Options none 표 4. svm multiclass learn을실행할때사용가능한옵션값들. slack 변수는에러를얼마나허용할것인가에대한변수이다.