서포트 벡터 머신

3. 주요 특징

서포트 벡터 머신(SVM)은 분류 및 회귀 분석에 사용되는 강력한 기계 학습 모델이다. SVM은 다음과 같은 주요 특징을 갖는다.

• 초평면(Hyperplane) 기반 분류: SVM은 데이터를 두 개의 클래스로 나누는 초평면을 찾는다. 이 초평면은 데이터 공간에서 두 클래스를 구분하는 경계선 역할을 한다.
• 최대 마진(Margin): SVM은 두 클래스 사이의 거리, 즉 마진을 최대화하는 초평면을 찾는다. 마진은 초평면과 가장 가까운 데이터 포인트(서포트 벡터) 사이의 거리로 정의된다.
• 커널 트릭(Kernel Trick): SVM은 비선형 분류 문제를 해결하기 위해 커널 트릭을 사용한다. 커널 트릭은 데이터를 고차원 공간으로 매핑하여 선형 분리가 가능하도록 하는 기법이다. 이를 통해 복잡한 비선형 경계를 갖는 데이터도 효과적으로 분류할 수 있다.
• 일반화 성능: SVM은 최대 마진을 추구함으로써 과적합(Overfitting)을 방지하고 일반화 성능을 높인다. 즉, 새로운 데이터에 대해서도 높은 예측 정확도를 보인다.
• 소프트 마진(Soft Margin): SVM은 일부 데이터 포인트가 마진 내부에 위치하거나 잘못 분류되는 것을 허용하는 소프트 마진 방식을 사용할 수 있다. 이는 데이터에 노이즈가 있거나 완벽하게 선형 분리가 불가능한 경우에 유용하다.
• 다양한 커널 함수: SVM은 선형, 다항식, 가우시안 RBF, 시그모이드 등 다양한 커널 함수를 지원하여 문제에 맞는 최적의 모델을 구축할 수 있다.
• 구조화된 SVM: 기존 SVM 모델을 확장한 구조화된 SVM은 구문 분석 트리, 분류 체계 등과 같이 일반적인 구조화된 출력 레이블을 처리하는 데 사용된다.^[37]

3. 1. 목표 및 아이디어

3. 2. 선형 SVM

• 초평면(Hyperplane): 데이터를 두 개의 클래스로 나누는 (p-1)차원의 평면. (p는 데이터의 차원)
• 마진(Margin): 초평면과 가장 가까운 데이터 포인트(서포트 벡터) 사이의 거리.
• 서포트 벡터(Support Vector): 초평면에 가장 가까이 위치한 데이터 포인트들로, 마진을 결정하는 데 핵심적인 역할을 한다.
• 최대 마진 초평면(Maximum-margin hyperplane): 마진을 최대로 하는 초평면.
• 최대 마진 분류기(Maximum margin classifier): 최대 마진 초평면을 사용하여 데이터를 분류하는 선형 분류기.

• $\backslash mathbf\{x\}\_i$는 p차원 실수 벡터 (데이터 포인트)
• $y\_i$는 클래스 레이블 (1 또는 -1)
• 초평면: $\backslash mathbf\{w\}\backslash cdot\backslash mathbf\{x\}\; -\; b=0$
• $\backslash mathbf\{w\}$는 초평면의 법선 벡터
• $b$는 편향(bias)

3. 2. 1. 하드 마진(Hard-margin) SVM

3. 2. 2. 소프트 마진(Soft-margin) SVM

3. 3. 비선형 SVM

3. 3. 1. 커널 함수의 종류

• 다항식(동차): $k(\backslash mathbf\{x\}\_i,\; \backslash mathbf\{x\}\_j)\; =\; (\backslash mathbf\{x\}\_i\; \backslash cdot\; \backslash mathbf\{x\}\_j)^d$. 특히, $d\; =\; 1$인 경우 선형 커널이 된다.
• 다항식(비동차): $k(\backslash mathbf\{x\}\_i,\; \backslash mathbf\{x\}\_j)\; =\; (\backslash mathbf\{x\}\_i\; \backslash cdot\; \backslash mathbf\{x\}\_j\; +\; r)^d$.
• 가우시안 방사 기저 함수: $k(\backslash mathbf\{x\}\_i,\; \backslash mathbf\{x\}\_j)\; =\; \backslash exp\backslash left(-\backslash gamma\; \backslash left\backslash |\backslash mathbf\{x\}\_i\; -\; \backslash mathbf\{x\}\_j\backslash right\backslash |^2\backslash right)$ (단, $\backslash gamma\; >\; 0$). 때때로 $\backslash gamma\; =\; 1/(2\backslash sigma^2)$를 사용하여 매개변수화된다.
• 시그모이드 함수(쌍곡 탄젠트): $k(\backslash mathbf\{x\_i\},\; \backslash mathbf\{x\}\_j)\; =\; \backslash tanh(\backslash kappa\; \backslash mathbf\{x\}\_i\; \backslash cdot\; \backslash mathbf\{x\}\_j\; +\; c)$ (단, 어떤 (모든 것은 아닌) $\backslash kappa\; >\; 0$ 및 ).

• 선형
• 다항식
• 방사 기저 함수
• 시그모이드 함수

4. SVM 분류기 계산

서포트 벡터 머신(SVM) 분류기는 주어진 데이터를 바탕으로 최적의 초평면을 찾아 분류한다. 초평면은 가장 가까운 학습 데이터 점과의 거리가 최대가 되도록 설정되는데, 이를 통해 분류 오차(classifier error^영어)를 최소화한다.

초기 문제가 선형 구분이 불가능한 경우, 더 높은 차원으로 데이터를 대응시켜 분리를 쉽게 만든다. 이때 계산량이 증가하는 문제를 해결하기 위해, 커널 함수 $k(x,y)$를 정의하여 내적 연산을 효과적으로 계산한다.^[56]

높은 차원 공간의 초평면은 점들과 상수 벡터의 내적 연산으로 정의되며, 초평면에 정의된 벡터들은 데이터 베이스 안에 나타나는 이미지 벡터 매개 변수들과의 선형적 결합이 되도록 선택된다. 이 초평면에서 점 $x$는 다음 관계를 만족한다.

:$\backslash textstyle\backslash sum\_i\; \backslash alpha\_i\; k(x\_i,x)\; =\; \backslash mathrm\{constant\}.$

$k(x,y)$가 $x$와 $y$가 멀어질수록 작아지면, 각 합은 테스트 점 $x$와 데이터 점 $x\_i$의 근접성을 나타낸다. 이 방식은 데이터 점과 테스트 점 간의 상대적인 근접성을 측정하는 데 사용될 수 있다.

1992년 베른하르트 보저, 이자벨 기용, 블라디미르 바프니크는 최대 마진 초평면 문제에 커널 트릭을 적용하여 비선형 분류를 제안하였다.^[59][60] 이들은 내적 연산을 비선형 커널 함수로 대체하여, 변환된 특징 공간에서 최대 마진 초평면 문제를 해결할 수 있게 하였다.

일반적인 커널들은 다음과 같다.

• 동차다항식(Homogeneous polynomial^영어): $k(\backslash mathbf\{x\_i\},\backslash mathbf\{x\_j\})=(\backslash mathbf\{x\_i\}\; \backslash cdot\; \backslash mathbf\{x\_j\})^d$
• 다항식 커널(Polynomial kernel^영어): $k(\backslash mathbf\{x\_i\},\backslash mathbf\{x\_j\})=(\backslash mathbf\{x\_i\}\; \backslash cdot\; \backslash mathbf\{x\_j\}\; +\; 1)^d$
• 가우시안 방사 기저 함수(Gaussian radial basis function^영어): $k(\backslash mathbf\{x\_i\},\backslash mathbf\{x\_j\})=\backslash exp(-\backslash gamma\; \backslash |\backslash mathbf\{x\_i\}\; -\; \backslash mathbf\{x\_j\}\backslash |^2)$ ($\backslash gamma\; >\; 0$). 때때로 $\backslash gamma=1/\{2\; \backslash sigma^2\}$으로도 나타낸다.
• 쌍곡탄젠트(Hyperbolic tangent^영어): $k(\backslash mathbf\{x\_i\},\backslash mathbf\{x\_j\})=\backslash tanh(\backslash kappa\; \backslash mathbf\{x\_i\}\; \backslash cdot\; \backslash mathbf\{x\_j\}+c)$ ($\backslash kappa\; >\; 0$ , ).

4. 1. 원 형식 (Primal Form)

4. 2. 쌍대 형식 (Dual Form)

• 동차다항식(Homogeneous polynomial): $k(\backslash mathbf\{x\_i\},\backslash mathbf\{x\_j\})=(\backslash mathbf\{x\_i\}\; \backslash cdot\; \backslash mathbf\{x\_j\})^d$
• 다항식 커널(Polynomial kernel)(Inhomogeneous): $k(\backslash mathbf\{x\_i\},\backslash mathbf\{x\_j\})=(\backslash mathbf\{x\_i\}\; \backslash cdot\; \backslash mathbf\{x\_j\}\; +\; 1)^d$
• 가우시안 방사 기저 함수(Gaussian radial basis function): $k(\backslash mathbf\{x\_i\},\backslash mathbf\{x\_j\})=\backslash exp(-\backslash gamma\; \backslash |\backslash mathbf\{x\_i\}\; -\; \backslash mathbf\{x\_j\}\backslash |^2)$ for $\backslash gamma\; >\; 0$. 때때로 $\backslash gamma=1/\{2\; \backslash sigma^2\}$으로도 나타낸다.
• 쌍곡탄젠트(Hyperbolic tangent): $k(\backslash mathbf\{x\_i\},\backslash mathbf\{x\_j\})=\backslash tanh(\backslash kappa\; \backslash mathbf\{x\_i\}\; \backslash cdot\; \backslash mathbf\{x\_j\}+c)$, for some (not every) $\backslash kappa\; >\; 0$ and

4. 3. 현대적 방법

• 하강 기울기법 (Sub-gradient Descent)

• 좌표 하강법 (Coordinate Descent)

5. SVM의 확장

원래 서포트 벡터 머신(SVM) 알고리즘은 1964년 블라디미르 바프니크(Vladimir N. Vapnik)와 알렉세이 체르보넨키스(Alexey Ya. Chervonenkis)에 의해 고안되었다. 1992년, 베른하르트 보저(Bernhard Boser), 이자벨 기용(Isabelle Guyon)과 블라디미르 바프니크는 최대 마진 초평면에 커널 트릭을 적용하여 비선형 분류기를 생성하는 방법을 제안했다.^[17] 소프트웨어 패키지에서 일반적으로 사용되는 "소프트 마진(soft margin)"은 코리나 코르테스(Corinna Cortes)와 바프니크가 1993년에 제안하고 1995년에 발표했다.^[18]

최소화 문제가 잘 정의된 해를 가지려면, 고려되는 가설의 집합에 제약 조건을 두어야 한다. SVM과 같이 노름 공간인 경우, 인 가설 $f$만 고려하는 것이 효과적이다. 이는 규제 페널티 $\backslash mathcal\; R(f)\; =\; \backslash lambda\_k\backslash lVert\; f\; \backslash rVert\_\{\backslash mathcal\; H\}$를 부과하고 새로운 최적화 문제를 푸는 것과 같으며, 이 방법을 티호노프 정규화라고 한다.

보다 일반적으로, $\backslash mathcal\{R\}(f)$는 가설 $f$의 복잡성을 측정하는 어떤 척도가 될 수 있으므로, 더 단순한 가설이 선호된다.

5. 1. 다중 클래스 SVM (Multiclass SVM)

• 일대다(one-vs-all): 하나의 레이블과 나머지 레이블을 구분하는 이진 분류기를 만든다. 새 인스턴스를 분류할 때는 최고 출력 함수를 가진 분류기가 클래스를 할당하는 승자 독식 전략을 사용한다. (단, 출력 함수가 비교 가능한 점수를 생성하도록 보정해야 한다.)
• 일대일(one-vs-one): 모든 클래스 쌍을 구분하는 이진 분류기를 만든다. 각 분류기는 인스턴스를 두 클래스 중 하나에 할당하고, 할당된 클래스에 대한 투표가 증가한다. 최종적으로 가장 많은 투표를 받은 클래스가 인스턴스의 클래스로 결정된다. (최대 승리 투표 전략)
• 유향 비순환 그래프 SVM (DAGSVM)^[30]
• 오류 정정 출력 코드^[31]

5. 2. 구조화 SVM (Structured SVM)

5. 3. 서포트 벡터 회귀 (Support Vector Regression, SVR)

5. 4. 베이지안 SVM (Bayesian SVM)

6. 응용 분야

SVM은 다음과 같은 분야에서 활용된다.

• 텍스트 및 하이퍼텍스트 분류: SVM은 학습 데이터의 양을 크게 줄일 수 있다. 얕은 의미 분석 방법 중 일부는 SVM을 기반으로 한다.^[7][8]
• 영상 분류: SVM은 기존의 쿼리 개선 방식보다 훨씬 높은 검색 정확도를 달성한다. 이는 영상 분할 시스템에도 해당된다.^[9][10]
• 위성 데이터 분류: SAR 데이터와 같은 위성 데이터 분류에 SVM이 사용된다.^[11]
• 필기 인식: SVM은 손글씨 인식에 사용될 수 있다.^[12][13]
• 생물학 및 기타 과학: SVM 알고리즘은 화합물의 최대 90%를 정확하게 분류하는 데 사용되었으며, SVM 가중치를 기반으로 하는 순열 검정은 SVM 모델 해석 메커니즘으로 제안되었다.^[14][15] SVM 모델 해석에 SVM 가중치가 사용되기도 한다.^[16]

7. 대한민국에서의 활용 및 사회적 영향

대한민국에서는 서포트 벡터 머신(SVM)이 다양한 분야에서 활발히 활용되고 있으며, 특히 정보통신기술(ICT) 분야에서 중요한 역할을 하고 있다.

• 텍스트 마이닝 및 자연어 처리: 한국어 텍스트 데이터 분석 및 감성 분석, 스팸 메일 필터링 등에 SVM이 활용된다. SVM은 텍스트와 하이퍼텍스트를 분류하는데 있어서 학습 데이터를 상당히 줄일 수 있게 해준다.^[1]
• 금융 분야: 신용 평가 모델 개발, 주가 예측, 금융 사기 탐지 등에 SVM이 사용될 수 있다.
• 의료 분야: 의료 영상 분석, 질병 진단, 유전체 데이터 분석 등에 SVM이 활용될 수 있다. SVM은 분류된 화합물에서 단백질을 90%까지 구분하는 의학 분야에 유용하게 사용된다.^[1]
• 제조 분야: 제품 품질 검사, 불량 예측, 공정 최적화 등에 SVM이 사용될 수 있다.
• 기타: 이미지 분류 작업에서 SVM을 사용할 수 있다. SVM이 기존의 쿼리 개량 구조보다 상당히 높은 검색 정확도를 보인 것에 대한 실험 결과가 있다.^[1] SVM을 통해서 손글씨의 특징을 인지할 수 있다.^[1]

8. 한계점 및 개선 방향

SVM의 효과는 커널, 커널의 매개변수, 그리고 소프트 마진 매개변수 λ의 선택에 따라 달라진다. 일반적인 선택은 단일 매개변수 γ를 갖는 가우시안 커널이다. λ와 γ의 최적 조합은 종종 지수적으로 증가하는 λ와 γ의 수열을 사용하는 격자 탐색을 통해 선택된다. 예를 들어, λ ∈ {2⁻⁵, 2⁻³, ..., 2¹³, 2¹⁵}, γ ∈ {2⁻¹⁵, 2⁻¹³, ..., 2¹, 2³}이다. 일반적으로 매개변수 선택의 각 조합은 교차 검증을 사용하여 확인되며, 가장 좋은 교차 검증 정확도를 가진 매개변수가 선택된다. 또는, 베이지안 최적화를 사용하여 λ와 γ를 선택할 수 있으며, 이는 종종 격자 탐색보다 훨씬 적은 매개변수 조합의 평가를 필요로 한다. 그런 다음 테스트 및 새로운 데이터 분류에 사용되는 최종 모델은 선택된 매개변수를 사용하여 전체 훈련 세트에서 훈련된다.^[27]

SVM의 잠재적인 단점은 다음과 같다.

• 입력 데이터의 완전한 레이블링이 필요하다.
• 보정되지 않은 클래스 멤버십 확률 — SVM은 유한한 데이터에 대한 확률 추정을 피하는 Vapnik의 이론에서 비롯된다.
• SVM은 이진 분류 작업에만 직접 적용 가능하다. 따라서 다중 클래스 작업을 여러 이진 문제로 축소하는 알고리즘을 적용해야 한다. 다중 클래스 SVM 섹션을 참조.
• 해결된 모델의 매개변수는 해석하기 어렵다.

참조

_[1] 서적 Artificial Neural Networks — ICANN'97 Springer 1997
_[2] 서적 Efficient Learning Machines Apress
_[3] 학술지 Support vector clustering
_[4] 웹사이트 1.4. Support Vector Machines — scikit-learn 0.20.2 documentation http://scikit-learn.[...] 2017-11-08
_[5] 서적 The Elements of Statistical Learning : Data Mining, Inference, and Prediction https://web.stanford[...] Springer
_[6] 서적 Numerical Recipes: The Art of Scientific Computing Cambridge University Press
_[7] 서적 Machine Learning: ECML-98 Springer 1998
_[8] 학회 Shallow Semantic Parsing using Support Vector Machines http://www.aclweb.or[...] Association for Computational Linguistics 2004-05-02
_[9] 기타 Vapnik, Vladimir N.: Invited Speaker. IPMU Information Processing and Management 2014).
_[10] 서적 Granular Computing and Decision-Making 2018-01-08
_[11] arXiv Supervised Classification of RADARSAT-2 Polarimetric Data for Different Land Features
_[12] 학술지 Training Invariant Support Vector Machines https://people.eecs.[...] 2002
_[13] 학회 2015 13th International Conference on Document Analysis and Recognition (ICDAR) 2015-08
_[14] 학술지 Analytic estimation of statistical significance maps for support vector machine based multi-variate image analysis and classification
_[15] 학술지 Spatial regularization of SVM for the detection of diffusion alterations associated with stroke outcome http://www.aramislab[...] 2018-01-08
_[16] 기타 Using SVM weight-based methods to identify causally relevant and non-causally relevant variables http://www.ccdlab.or[...] 2006
_[17] 학회 Proceedings of the fifth annual workshop on Computational learning theory – COLT '92
_[18] 학술지 Support-vector networks http://image.diku.dk[...]
_[19] 웹사이트 Why is the SVM margin equal to $\backslash frac\{2\}\{\backslash |\backslash mathbf\{w\}\backslash |\}$ https://math.stackex[...] 2015-05-30
_[20] 학술지 Theoretical foundations of the potential function method in pattern recognition learning
_[21] 학회 Dimensionality dependent PAC-Bayes margin bound http://papers.nips.c[...]
_[22] 학술지 Pegasos: primal estimated sub-gradient solver for SVM 2010-10-16
_[23] 학회 Proceedings of the 25th international conference on Machine learning - ICML '08 ACM 2008-01-01
_[24] 학술지 Are Loss Functions All the Same? https://ieeexplore.i[...] 2004-05-01
_[25] 학회 Links between Perceptrons, MLPs and SVMs
_[26] 학술지 The support vector machine under test 2003-09
_[27] 기술보고서 A Practical Guide to Support Vector Classification http://www.csie.ntu.[...]
_[28] 서적 Multiple Classifier Systems 2019-07-18
_[29] 학술지 A Comparison of Methods for Multiclass Support Vector Machines http://www.cs.iastat[...] 2018-01-08
_[30] 학회 Advances in Neural Information Processing Systems MIT Press
_[31] 학술지 Solving Multiclass Learning Problems via Error-Correcting Output Codes http://www.jair.org/[...]
_[32] 학술지 On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines http://jmlr.csail.mi[...]
_[33] 학술지 Multicategory Support Vector Machines http://www.interface[...]
_[34] 학술지 Multicategory Support Vector Machines
_[35] 학술지 GenSVM: A Generalized Multiclass Support Vector Machine http://jmlr.org/pape[...]
_[36] 학회논문 Transductive Inference for Text Classification using Support Vector Machines http://www1.cs.colum[...]
_[37] 웹사이트 Support Vector Machine Learning for Interdependent and Structured Output Spaces https://www.cs.corne[...]
_[38] 논문 Support Vector Regression Machines http://papers.nips.c[...] MIT Press
_[39] 논문 Least squares support vector machine classifiers https://lirias.kuleu[...]
_[40] 저널 A tutorial on support vector regression http://eprints.pasca[...]
_[41] 저널 Data Augmentation for Support Vector Machines
_[42] 서적 Machine Learning and Knowledge Discovery in Databases
_[43] 논문 Scalable Approximate Inference for the Bayesian Nonlinear Support Vector Machine http://approximatein[...]
_[44] 저널 Interior-Point Methods for Massive Support Vector Machines http://www.cs.wisc.e[...]
_[45] 학회논문 Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines http://research.micr[...]
_[46] 학회논문 Pegasos: Primal Estimated sub-GrAdient SOlver for SVM http://ttic.uchicago[...]
_[47] 저널 LIBLINEAR: A library for large linear classification https://www.csie.ntu[...]
_[48] 학회논문 P-packSVM: Parallel Primal grAdient desCent Kernel SVM http://people.csail.[...]
_[49] 저널 LIBLINEAR: A library for large linear classification 2008
_[50] 저널 Standardization and Its Effects on K-Means Clustering Algorithm 2013-09-01
_[51] 저널 Predicting and explaining behavioral data with structured feature space decomposition 2019-12-01
_[52] 논문 Pattern recognition using generalized portrait method
_[53] 웹사이트 Why is the SVM margin equal to $\backslash frac\{2\}\{\backslash |\backslash boldsymbol\{w\}\backslash |\}$ https://math.stackex[...]
_[54] 저널 Large Margin Methods for Structured and Interdependent Output Variables http://www.jmlr.org/[...]
_[55] 서적 The nature of statistical learning theory Springer-Verlag New York
_[56] 서적 Numerical Recipes: The Art of Scientific Computing Cambridge University Press
_[57] 저널 Support-vector networks
_[58] 웹사이트 Press release of March 17th 2009 http://www.acm.org/p[...]
_[59] 저널 Theoretical foundations of the potential function method in pattern recognition learning https://archive.org/[...]
_[60] 학회논문 Proceedings of the fifth annual workshop on Computational learning theory - COLT '92
_[61] 학회논문 Dimensionality dependent PAC-Bayes margin bound http://papers.nips.c[...]
_[62] 저널 LIBSVM: A library for support vector machines