Support  Vector  Machine

 

.... Support vector machine (SVM) Àº ºÐ·ù (classification) ¿Í ȸ±Í (regression) ¿¡ ÀÀ¿ëÇÒ ¼ö ÀÖ´Â ÁöµµÇнÀ (supervised learning) ÀÇ ÀÏÁ¾ÀÌ´Ù .........

±âº»ÀûÀÎ ºÐ·ù¸¦ À§ÇÑ SVM Àº ÀԷ°ø°£¿¡ maximum-margin hyperplaneÀ» ¸¸µç´Ù. yes ¶Ç´Â no °ªÀÌ ÁÖ¾îÁø training sample ÀÌ ÁÖ¾îÁö°í, °¡Àå °¡±îÀÌ ÀÖ´Â example (margin) ¿¡¼­ hyperplane ±îÁöÀÇ °Å¸®°¡ ÃÖ´ë°¡ µÇµµ·Ï training sample µéÀ» yes ¿Í no ·Î ³ª´©°Ô µÇ¸ç, ±×°ÍÀÌ maximum-margin hyperplane ÀÌ´Ù.  margin ÀÌ ÃÖ´ëÀÏ ¶§ ÃÖ¼Ò°¡ µÇ´Â probabilistic test error bound¸¦ º¸¿©ÁÖ´Â Vapnik Chervonenkis theory¿¡¼­ maximum-margin hyperplane ÀÌ Ã³À½ »ç¿ëµÇ¾ú´Ù. maximum-margin hyperplane ÀÇ ÆĶó¹ÌÅ͵éÀº quadratic programming (QP) optimization problemÀ» Ç®¾î¼­ ¾ò¾îÁø´Ù. SVM¿¡¼­ »ý±â´Â QP problemÀ» ºü¸£°Ô Ç®±â À§ÇÑ ¸î°¡ÁöÀÇ ¾Ë°í¸®ÁòµéÀÌ Á¸ÀçÇÑ´Ù.

Vladimir Vapnik ÀÌ 1963 ³â¿¡ ¹ßÇ¥ÇÑ ¿ø·¡ÀÇ optimal hyperplane Àº ¼±ÇüºÐ·ù±â (linear classifier)¿´´Ù. ±×·¯³ª 1992 ³â¿¡ Bernhard Boser, Isabelle Guyon and Vapnik Àº maximum-margin hyperplane ¿¡ kernel trick (¿ø·¡ Aizerman ÀÌ ¹ßÇ¥ÇÑ°Í)À» ÀÀ¿ëÇÏ¿´´Ù. °á°úÀûÀ¸·Î´Â ¸ðµç dot product (inner product) °¡ ºñ¼±Çü kernel function À¸·Î ±³Ã¼µÈ °ÍÀ» Á¦¿ÜÇÏ°í´Â À¯»çÇÑ ¾Ë°í¸®ÁòÀÌ´Ù. ÀÌ°ÍÀ¸·Î ÀÎÇØ ¼±Çü ¾Ë°í¸®ÁòÀÌ ´Ù¸¥ °ø°£¿¡¼­ ÀÛµ¿ÇÒ ¼ö ÀÖ°Ô µÇ¾ú´Ù. kernel trickÀ» »ç¿ëÇؼ­ maximum margin hyperplane ÀÌ Æ¯Â¡°ø°£ (feature space) ¿¡ ÀûÇÕÇÏ°Ô ÇÏ¿´´Ù. Ư¡°ø°£Àº º¸Åë ¿ø·¡ÀÇ ÀԷ°ø°£º¸´Ù´Â ÈξÀ ´õ Å« Â÷¿øÀ» °¡Áö´Â non-linear map ÀÌ´Ù. ÀÌ·¯ÇÑ ¹æ¹ýÀ¸·Î ºñ¼±Çü ºÐ·ù±â°¡ ¸¸µé¾îÁú ¼ö ÀÖ´Ù. »ç¿ëµÈ kernel ÀÌ radial basis function À̶ó¸é ±×·¯ÇÑ Æ¯Â¡°ø°£Àº ¹«ÇÑ Â÷¿øÀÇ Hilbert space ÀÌ´Ù.

Maximum margin classifiers ´Â Àß Á¶ÀýµÉ°æ¿ì ¹«ÇÑÂ÷¿øÀ̶ó°í Çؼ­ ³ª»Û °á°ú¸¦ ³ºÁö ¾Ê´Â´Ù. 1995 ³â¿¡ Corinna Cortes ¿Í Vapnik Àº À߸øÀ̸§Áö¿öÁø ¿¹ (mislabeled example) ÀÇ °æ¿ì¿¡µµ Àû¿ëµÇ´Â º¯ÇüµÈ maximum margin idea¸¦ Á¦¾ÈÇß´Ù. Áï example µéÀ» yes ¿Í no ·Î ±¸ºÐÇÒ ¼ö ÀÖ´Â hyperplane ÀÌ Á¸ÀçÇÏÁö ¾ÊÀ» °æ¿ì, Soft margin method ´Â °¡Àå °¡±îÀÌ ÀÖ´Â example ±îÁöÀÇ °Å¸®¸¦ ÃÖ´ë·Î Çϸ鼭, °¡´ÉÇÑÇÑ ±ú²ýÇÏ°Ô example µéÀ» ±¸ºÐÇÏ¿© ÁÖ´Â hyperplaneÀ» ¼±ÅÃÇÑ´Ù. ÀÌ·¯ÇÑ ÀÛ¾÷À» º¸Åë Support Vector Machine ¶Ç´Â SVM À̶ó°í Ç¥ÇöÇÑ´Ù.  

ȸ±Í (regression)À» À§ÇÑ SVM Àº 1997 ³â¿¡ Vapnik, Steven Golowich, Alex Smola °¡ Á¦¾ÈÇßÀ¸¸ç Support Vector Regression (SVR) À̶ó°í ºÒ¸°´Ù. À§¿¡¼­ ¾ð±ÞÇÑ Support Vector Classification À¸·Î ¸¸µé¾îÁø ¸ðµ¨Àº training data ÀÇ ºÎºÐÁýÇÕ¿¡¸¸ ÀÇÁ¸ÇÑ´Ù. ¿Ö³ÄÇÏ¸é ±× ¸ðµ¨À» ¸¸µé±â À§ÇÑ cost function Àº marginÀ» ¹þ¾î³­ training point ´Â °í·ÁÇÏÁö ¾Ê±â ¶§¹®ÀÌ´Ù. À¯»çÇÏ°Ô, Support Vector Regression À¸·Î ¸¸µç ¸ðµ¨Àº training data ÀÇ ºÎºÐÁýÇÕ¿¡¸¸ ÀÇÁ¸ÇÑ´Ù. ¿Ö³ÄÇÏ¸é ±× ¸ðµ¨À» ¸¸µé±â À§ÇÑ cost function Àº ±× ¸ðµ¨ ¿¹Ãø¿¡ °¡±îÀÌ ÀÖ´Â (threshold ¥å ¹üÀ§¿¡¼­) ¾î¶°ÇÑ training data µµ ¹«½ÃÇϱ⠶§¹®ÀÌ´Ù.............. (Wikipedia : SVM)

ÃÖ±Ù¿¡ ÆÐÅϺзù¿¡ À־ °¢±¤À» ¹Þ°í ÀÖ´Â SVM ¸ðµ¨Àº 1995 ³â Vladimir Naumovich Vapnik ¿¡ ÀÇÇØ °³¹ßµÈ Åë°èÀû ÇнÀÀÌ·ÐÀ¸·Î¼­ ÇнÀµ¥ÀÌÅÍ¿Í ¹üÁÖ Á¤º¸ÀÇ ÇнÀÁø´ÜÀ» ´ë»óÀ¸·Î ÇнÀ°úÁ¤¿¡¼­ ¾ò¾îÁø È®·üºÐÆ÷¸¦ ÀÌ¿ëÇÏ¿© ÀÇ»ç°áÁ¤ÇÔ¼ö¸¦ ÃßÁ¤ÇÑÈÄ ÀÌ ÇÔ¼ö¿¡ µû¶ó »õ·Î¿î µ¥ÀÌÅ͸¦ ÀÌ¿ø ºÐ·ùÇÏ´Â °ÍÀ¸·Î VC (Vapnik-Chervonenkis) ÀÌ·ÐÀ̶ó°íµµ ÇÑ´Ù. ƯÈ÷ SVM Àº ºÐ·ù ¹®Á¦¿¡ À־ ÀϹÝÈ­ ±â´ÉÀÌ ³ô±â ¶§¹®¿¡ ¸¹Àº ºÐ¾ß¿¡¼­ ÀÀ¿ëµÇ°í ÀÖ´Ù.

±âÁ¸ÀÇ ÇнÀ ¾Ë°í¸®ÁòÀº ÇнÀÁý´ÜÀ» ÀÌ¿ëÇÏ¿© ÇнÀ¿À·ù (empirical error)¸¦ ÃÖ¼ÒÈ­ÇÏ´Â °æÇèÀû À§Çè ÃÖ¼ÒÈ­ ¿øÄ¢ (Empirical Risk Minimization : EMR)À» ±¸ÇöÇÏ´Â °ÍÀε¥ ºñÇØ ±¸Á¶Àû À§Çè ÃÖ¼ÒÈ­ ¿øÄ¢ (Structural Risk Minimization : SRM) Àº ÀüüÁý´ÜÀ» ÇÏÀ§ Áý´ÜÀ¸·Î ¼¼ºÐÈ­ÇÑ µÚ ÀÌ Áý´Ü¿¡ ´ëÇÑ °æÇèÀû À§Çèµµ¸¦ ÃÖ¼ÒÈ­ÇÏ´Â ÀÇ»ç°áÁ¤ÇÔ¼ö¸¦ ¼±ÅÃÇÏ´Â °ÍÀÌ´Ù.

SVM Àº ½Å°æ¸Áó·³ ÆÐÅϺзù³ª ÇÔ¼öÃßÁ¤ µîÀ» È¿°úÀûÀ¸·Î ¼öÇàÇÒ ´É·ÂÀÌ ÀÖÁö¸¸ ´ÙÀ½ °°Àº Á¡¿¡¼­ °³¼±µÇ´Â °ÍÀÌ ¹Ù¶÷Á÷ÇÏ´Ù. ¾î¶² ÇнÀµ¥ÀÌÅÍ´Â ÆÐÅϺзù ¹®Á¦¿¡ À־ ´Ù¸¥ µ¥ÀÌÅ͵麸´Ù ´õ °áÁ¤ÀûÀÎ ¿µÇâ·ÂÀ» °¡Áú ¼öµµ ÀÖÀ¸¹Ç·Î ¿ì¼±ÀûÀ¸·Î ¿Ã¹Ù¸£°Ô ºÐ·ùµÇ¾îÁ®¾ß Çϸç ÀâÀ½ (noise) ¶Ç´Â ÀÌ»óÄ¡ (outlier) µéÀº ±â°èÇнÀ °úÁ¤¿¡¼­ ¿µÇâ·ÂÀÌ ÀÛ¾ÆÁö±æ ¿øÇÑ´Ù.

¿¹¸¦µé¾î ¼øÂ÷ µ¥ÀÌÅ͵éÀÌ Ãß¼¼¸¦ Çü¼ºÇÒ ¶§ °¡Àå ÃÖ±Ù µ¥ÀÌÅ͵éÀÇ ÆÐÅÏ¿¡ ¿µÇâÀ» ¸¹ÀÌ ¹Þ´Â´Ù¸é, ¼øÂ÷Àû ¼ºÁúÀ» °®´Â Fuzzy ¼Ò¼ÓÇÔ¼ö¸¦ Á¤ÀÇÇÏ¿© °¢ ÈÆ·Ã µ¥ÀÌÅÍ¿¡ Àû¿ëÇϸé ÇнÀÇÒ ¶§ ¸ðµç ÈƷú¤Å͵éÀÌ È¹ÀÏÀûÀ¸·Î Ãë±ÞµÇÁö ¾Ê°í ¼øÂ÷ µ¥ÀÌÅ͵éÀÇ ÆÐÅÏ¿¡ ¿µÇâÀ» ¹Þµµ·Ï ÇнÀ½Ãų ¼ö ÀÖ´Ù. µû¶ó¼­ SVM ±â¹ýÀº ½Å°æ¸Á, ÆÛÁöÀÌ·Ð, À¯Àü¾Ë°í¸®Áò, È¥µ·ÀÌ·Ð µîÀÇ ÀΰøÁö´É ±â¹ý°ú ÅëÇÕÇÑ ÆÐÅϺзù±âÀÇ ¼³°è°¡ ¹Ù¶÷Á÷ÇÏ´Ù. (2002 ÀÌÀϺ´)

SVM Àº  ºÐ·ù ¹®Á¦¸¦ ÇØ°áÇϱâ À§ÇØ ÃÖÀûÀÇ ºÐ¸® °æ°è¸é (hyperplane)À» Á¦°øÇÑ´Ù. SVM ÀÌ ÁÖ¸ñ¹Þ´Â ÀÌÀ¯´Â ù°, ¸í¹éÇÑ ÀÌ·ÐÀû ±Ù°Å¿¡ ±â¹ÝÇϹǷΠ°á°ú Çؼ®ÀÌ ¿ëÀÌÇÏ°í, µÑ°, ½ÇÁ¦ ÀÀ¿ë¿¡ À־ Àΰø½Å°æ¸Á ¼öÁØÀÇ ³ôÀº ¼º°ú¸¦ ³»°í, ¼Â°, ÀûÀº ÇнÀÀڷḸÀ¸·Î ½Å¼ÓÇÏ°Ô ºÐº°ÇнÀÀ» ¼öÇàÇÒ¼ö Àֱ⠶§¹®ÀÌ´Ù.

SVM Àº MDA, Logit, CBR °ú ºñ±³Çؼ­ ¿ì¼öÇÑ ¿¹Ãø·ÂÀ» º¸¿´À¸¸ç ....  Àΰø½Å°æ¸Á°ú ºñ½ÁÇÑ ¼öÁØÀÇ ³ôÀº ¿¹Ãø·ÂÀ» ³ªÅ¸³¾ »Ó¸¸ ¾Æ´Ï¶ó Àΰø½Å°æ¸ÁÀÇ ÇÑ°èÁ¡À¸·Î ÁöÀûµÇ¾ú´ø °ú´ëÀûÇÑ, ±¹¼ÒÃÖÀûÈ­¿Í °°Àº ÇÑ°èÁ¡µéÀ» ¿ÏÈ­ÇÏ´Â ÀåÁ¡À» °¡Áø´Ù. (2003 ÇÑÀα¸)

SVM Àº ¿ø·¡ ÀÌÁøºÐ·ù (binary classification)¸¦ À§ÇÏ¿© °³¹ßµÇ¾úÀ¸¸ç ÇöÀç¿¡´Â »ý¹°Á¤º¸ÇÐ (bioinformatics), ¹®ÀÚÀνÄ, ÇʱâÀνÄ, ¾ó±¼ ¹× ¹°Ã¼ÀÎ½Äµî ´Ù¾çÇÑ ºÐ¾ß¿¡¼­ ¼º°øÀûÀ¸·Î Àû¿ëµÇ°í ÀÖ´Ù. (2003 Â÷¼º´ö)

svm.gif

term :

Support Vector Machine   ÆÐÅÏÀÎ½Ä (Pattern Recognition)    ½Å°æ¸Á (Neural Network)     ±â°èÇнÀ (Machine Learning)   ÁöµµÇнÀ (Supervised Learning)   Vladimir Vapnik

paper :

Fuzzy À̷аú SVMÀ» ÀÌ¿ëÇÑ KOSPI 200 Áö¼ö ÆÐÅϺзù±â (Pattern Classifier utilizing Fuzzy Theory and SVM) : ÀÌÀϺ´, À̼ö¿ë, Çѱ¹Áõ±ÇÇÐȸ, 2002

The Efficiency of Boosting on SVM : ¼®°æÇÏ, ·ùÅ¿í, Çѱ¹µ¥ÀÌÅÍÁ¤º¸°úÇÐȸ, 2002 

SVM ±â¹ÝÀÇ È¿À²ÀûÀÎ ½ÅºÐ À§Àå ±â¹ý ŽÁö (Efficient Masquerade Detection Based on SVM) : Â÷¼º´ö, ±èÇѼº, ±Ç¿µÈñ, Çѱ¹Á¤º¸º¸È£ÇÐȸ, 2003

SVMÀ» ÀÌ¿ëÇÑ ¾ó±¼ °ËÃâ ¼º´ÉÇâ»ó ¹æ¹ý (Performance Improvement Method of Face Detection Using SVM) : ÀÌ°æÈñ, Á¤¿ëÈ­, ÁöÇü±Ù, Çѱ¹Á¤º¸Ã³¸®ÇÐȸ, 2004

º¹ÇÕ ¾Ë°í¸®ÁòÀ» ÀÌ¿ëÇÑ ½Ç½Ã°£ ¾ó±¼°ËÃâ ¹× SVM Àνıâ¼ú : ¹ÚÁ¤¼±, ÀÌ»ó¿õ, À¯¸íÇö, Á¤¿©¾Æ, ¾çÈñ´ö, Çѱ¹Á¤º¸º¸È£ÇÐȸ, 2002

Support Vector Machine À» ÀÌ¿ëÇÑ ±â¾÷ºÎµµ ¿¹Ãø : ±è°æÀç, ÇÑÀα¸, ¹ÚÁ¤¹Î, Çѱ¹°æ¿µÁ¤º¸ÇÐȸ, 2003

Çѱ¹¾î Á¤º¸Ã³¸® : ÈÞ¸®½ºÆ½À» ÀÌ¿ëÇÑ kNN ÀÇ È¿À²¼º °³¼± (Korean Information Processing : An Improvement Of Efficiency For kNN By Using A Heuristic) : ÀÌÀç¹®, Çѱ¹Á¤º¸Ã³¸®ÇÐȸ, 2003

Çà·ÄÀüÄ¡¸¦ ÀÌ¿ëÇÑ È¿À²ÀûÀÎ NaiveBayes ¾Ë°í¸®Áò (An Efficient Algorithm for NaiveBayes with Matrix Transposition) : ÀÌÀç¹®, Çѱ¹Á¤º¸Ã³¸®ÇÐȸ, 2004

video :

ÀΰøÁö´ÉÀ» À§ÇÑ ¸Ó½Å·¯´× ¾Ë°í¸®Áò 5°­ - ¼­Æ÷Æ® º¤ÅÍ ¸Ó½Å : SKtechx Tacademy : 2017/07/06 ... µ¿¿µ»ó 15°³