10.22.2023
0. Support Vector Machine, SVM
Support Vector Machine, SVM은 리니어, 논리니어 클래시피케이션, 리그레션, 아우터 디텍션까지도 모두 할 수 있는 강력한 만능 머신 러닝 모델이다.
특히 복잡한 작은-중간 사이즈의 데이터들을 클래시피케이션하는데 특화되어 있다. (컴플렉스한 피쳐를 가지고 있을 때)
1. Linear SVM Classification
두 개의 클래스를 가르는 디시전 바운더리는 많다. 우리는 그 중에서 가장 좋은 디시전 바운더리를 골라야 한다.
가장 좋은 디시전 바운더리란, 최대한 두 클래시피케이션과 디시전 바운더리 사이의 margin이 똑같고 최대한 넓은 디시전 바운더리이다.
두 마진을 우리는 스트릿이라고 부르는데, 스트릿 외부에 데이터를 추가해봐야 디시전 바운더리에 영향을 주지 않음.
마진의 엣지 또는 스트릿 안에 존재하는 인스턴스를 support vertor, 서포트 벡터라고 부름.
결론적으로 서포트 벡터들이 디시전 바운더리를 결정한다. 최대 마진을 가지는 디시전 바운더리가 SVM 디시전 바운더리이고, 그것을 찾는 것이 SVM의 목표가 된다.
SVM은 피쳐 스케일에 매우 민감하다. 왼쪽과 오른쪽을 비교해봤을 때, SVM 디시전 바운더리 마진이 훨씬 넓어진 것을 볼 수 있음.
특히 Gradient Descent같은 인터렉티브 알고리즘에는 스케일링을 하는게 무조건 유리함
1-1. Hard Margin Classification
하드마진은 스트릿 안으로 잘못 들어오는 인스턴스가 없도록 하는 것이다.
하드마진 클래시피케이션은 선형적으로 분리 가능한 데이터 셋에만 사용 가능하다.
또한 아웃라이어(마진 엣지에 걸쳐져 있는 인스턴스)에 굉장히 예민하다는 단점이 있다.
1-2. Soft Margin Classification
하드마진의 두 가지 단점을 극복하기 위해 나온 소프트 마진은 좀 더 유연한 모델이다.
소프트 마진의 목표는 스트릿, 마진을 최대한 크게 유지하는 것과 마진 바이올레이션을 최소화 하는 것이다.(tradeoff)
Margin Violation: 스트릿에 위치해있거나, 잘못된 사이드에 있는 인스턴스들
C는 사이킷런에서 SVM의 하이퍼파라미터이다.
C가 낮을때(1): 왼쪽 그래프는 마진이 넓지만, 마진 바이올레이션도 많다. 오버피팅을 줄일 수 있으며, 노이즈에 둔감해진다. 제너럴라이제이션을 더 잘한다.
C가 높을때(100): 오른쪽 그래프는 마진이 거의 하드마진에 가깝고, 오버피팅 확률이 높아졌다. 노이즈에 예민해진다. 오버피팅이 발생한다면, C를 줄이는게 맞음
리니어 SVC 클래스는 바이어스 텀도 정규화하기 때문에, 피쳐 스케일링시 평균값을 빼줌으로써 트레이닝 셋을 센터에 위치시켜야 함.
디폴트값이 아니기 때문에 힌지로스를 해줘야 한다.
더 좋은 성능을 위해서는, 듀얼하이퍼 파라미터를 false로 설정해줘야 한다.(트레이닝 인스턴스보다 피쳐가 더많거나, 파라미터의 개수가 트레이닝 갯수보다 더 큰 경우는 제외)
2. Nonlinear SVM Classification
기존의 논리니어 데이터들에는 폴리노미얼 피쳐와 같은 피쳐들을 더 추가해서 리니어하게 separable 데이터로 만들었음
폴리노미얼 피쳐를 추가하는 것의 두가지 문제점은
- 폴리노미얼 디그리를 작게 잡으면 복잡한 데이터셋을 학습하는 데 무리가 있다.(모델 복잡도 너무 낮음)
- 큰 수의 디그리를 가진 경우, 피쳐가 너무 많아서 학습에 걸리는 시간이 너무 김.
2-1. Polynomial Kernel, 폴리노미얼 커널
SVM은 커널이라는 트릭을 써서 실제 폴리노미얼 피쳐를 추가하지 않아도, 추가한 것과 같은 효과를 낼 수 있게끔 해준다.
coef0: 높은 차원의 폴리노미얼과 낮은 차원의 폴리노미얼 중 어떤 것에 더 많은 영향을 받을지 조정하는 하이퍼 파라미터
2-2. Similarity Features, 유사도 피쳐
논 리니어 문제들을 푸는 다른 기술은 유사도 함수를 이용해 연산된 피쳐들을 추가하는 것이다.
유사도 함수는 각각의 인스턴스가 특정 landmark를 얼마나 닮았는가 를 측정하는 함수이다.
랜드마크에 가까울수록 1이 되고, 멀어질 수록 0이 되는 Gaussian RBF(유사도 함수)를 선언했을 때의 그래프이다.
중요한 것은 랜드마크를 어떻게 결정하느냐이다.
랜드마크를 결정하는 기본적인 방식은 모든 데이터에 대해 랜드마크를 잡는 것이다.(100개의 인스턴스, 100개의 피쳐) 이렇게 되면 피쳐 디맨션이 엄청 커지게 되므로 linearly separable 하게 만들 수 있음
단점으로는 피쳐의 갯수가 인스턴스의 갯수만큼으로 들어나므로 학습 시간이 늘어난다는 것이다.
2-3. Gaussian RBF Kernel
유사도 함수는 모든 추가적인 인풋 피쳐를 계산하기엔 너무 비쌀 수도 있다(특히 큰 트레이닝 데이터 셋에서)
커널트릭을 사용하면 많은 유사도 함수를 추가한 것과 같은 유사한 결과를 얻을 수 있다.
하이퍼 파라미터 감마(𝜸)
하이퍼파라미터 감마의 값이 커지면 각 인스턴스가 영향을 미치는 구간이 작아지게 된다. 이렇게 되면 디시전 바운더리가 하나하의 인스턴스에 더 의존적이 됨.
감마를 줄이면 더 스무스해지고, 오버피팅 될 가능성이 줄어든다.
c가 커질수록 복잡해지는 것을 확인할 수 있다.
2-4. Other Kernels
다른 커널들도 존재하긴 하지만, 잘 이용되지는 않는다.
어떤 커널들은 특정한 태스크나 데이터 스트럭쳐들에 특화되어있다.
스트링 커널들은 text documents 나 DNA sequences를 클래시파이할 때 이용된다.
어떻게 커널을 선택할까?
커널을 선택할 때는 항상 linear kernel을 먼저 시도해본다.(특히 데이터셋이 매우 크거나 피쳐가 많을 때)
이때 트레이닝 데이터셋이 너무 크면 Gaussian RBF를 시도하고, 시간과 메모리가 적은 경우 다른 커널들을 사용해본 후 결정한다.
2-5. Computational Complexity
LinearSVC 클래스틑 liblinear library에 기반한다.
커널 트릭을 서포트하지는 않지만, 피쳐의 갯수와 인스턴스의 갯수를 거의 선형적으로 스케일 할 수 있다.
m: 데이터셋의 갯수
n: 피쳐의 갯수
사이킷런에는 SVM을 구현할 수 있는 몇 가지 방식들이 존재한다.
트레이닝 데이터가 리니어하면 LinearSVC를 사용하고, 트레이닝 세트가 적거나 중간이고 피쳐가 많을 때는 SDGClassifier를 사용한다.
커널트릭이 필요한 경우 SVC를 사용한다. 이 경우 배치로만 진행을 해야한다.
결론적으로 본인 데이터, 컴퓨터 사양에 따라 결정하면 된다.
3. SVM Regression
SVM은 linear / nonlinear regression을 모두 지원한다.
기존 SVM classification에서는 디시전 바운더리의 최대 마진을 얻는 것을 목표로 했다.
SVM Regression에서의 목표는 가능한 많은 인스턴스들을 스트리트에 안착시키는 것이다.(목표가 완전히 뒤바뀜)
이때 margin violation은 off street 인스턴스들이 된다.
이때, 하이퍼파라미터 입실론(𝟄)이 스트릿의 width를 컨트롤한다. 입실론이 크면 마진이 커지고, 작으면 마진이 작아진다.
인스턴트들을 마진 안에 아무리 넣어봤자 프리딕션에 영향이 가지 않는다.
논리니어 리그레션 태스크에는 SVM 모델의 커널트릭을 사용한다.
4. Under the Hood
이 파트에서는 실제로 어떻게 SVM이 돌아가는지에 대한 이론 설명이 주를 이룬다.
4-1. Decision Function and Predictions
리니어 SVM 클래시파이어의 디시전 펑션은 인풋피쳐에 웨이트를 곱한 것을 다 더한 후 바이어스를 더하면 된다.
결과값이 양수라면 예측된 와이햇은 positive class (1)이고, 그렇지 않다면 negtive class(0)이 된다.
디시전 바운더리는 디시전 함수가 0과 같은 지점들의 집합이다.
피쳐가 하나면 라인으로 형성되고, 피쳐가 두개라면 평면으로 형성되며 두 평면이 만나는 곳이 디시전 바운더리 이다.
점선: 벡터 시드라인
벡터 시드라인은 디시전 바운더리와 평행할 수 밖에 없고, 같은 길이로 떨어져 있으므로 (-1,0,1) 디시전 바운더리의 마진을 형성한다.
linear SVM classifier를 학습시킨다는 의미는 w의 값과 마진 최소의 바이올레이션으로 최대의 마진을 갖는 b의 값을 찾는 것이다.
4-2. Training Objective
가중치 벡터 w가 작을수록 마진이 넓어지는 것을 확인할 수 있는 그래프다.
decision function이 y = w*x + 1 일 때,
- 우리는 w의 크기가 최소화해야한다. 최대의 마진을 얻기 위해서.
- 모든 파지티브 인스턴스들에 대해 wx+b가 1보다 커야하고, 네거티브 인스턴스에 대해 wx+1가 -1보다 작아야 한다.
wTw를 최소화한다는 의미는 w의 크기의 제곱을 최소화한다는 뜻과 같기도 하다.
밑에는 만족해야하는 조건이다. 보통 이러한 최적화 알고리즘은 미분가능한 함수들에 성능이 더 좋다.
소프트마진의 목표를 달성하기 위해서는 각 인스턴스들에 대해 slack variable이 0보다 같거나 커야한다.
여기서 conflict가 발생하는데
- 마진 바이올레이션을 줄이려면 슬랙 바리어블이 최대한 작아야 한다
- 마진을 최대화하기 위해서는 1/2wTw가 최대한 작아야 한다.
여기서 하이퍼파라미터 C를 적용함으로써 이 트레이드 오프관계를 컨트롤할 수 있다.
4-3. Quadratic Programming
간혹가다 수학적으로 어려운 문제들이 있는 경우가 있다. 이 경우, 수식을 조금 변경할 수 있는데 그렇게 변경된 문제를 Quadratic Programming 문제라고 한다.
변경되기 전 문제는 Primal 문제라고 한다.
4-4. The Dual Problem
Dual Problem이란 주어진 최적화 문제(Primal problem)를 다르지만 거의 연관된 형태의 문제로 표현된 것을 일컫는다.
몇가지 조건과 함께라면 primal problem과 같은 솔루션을 dual problem이 가질 수 있다.
조건: 목표 함수는 convex(볼록) 함수여야 하며, 부등식 제약 조건은 계속 미분가능해야하며 볼록 함수여야 한다.
다행히도, SVM을 이용하면 조건을 만족하기 때문에 Primal, Dual 상관 없이 솔루션을 가질 수 있다.
그렇다면 왜 굳이 definition을 바꿔서까지 Dual을 쓰는가? Kernel Trick을 사용하기 쉽기 때문
4-5. Kernelized SVMs
커널라이즈된 SVM 모델들은 가오시안과 같은 피쳐추가를 하지 않아도 추가한 것과 똑같은 효과를 얻는다.
2차원 폴리노미얼 트랜스포메이션을 2차원 트레이닝 셋에 적용하고, linear SVM classifier를 변환된 트레이닝 셋에 대해 학습시키려 한다고 가정하자.
파이: 트랜스포메이션을 뜻함
인풋피쳐는 2개인데 차원은 3개로 추가된 것을 볼 수 있음
트랜스폼된 벡터의 닷 프로덕트는 오리지널 벡터의 닷 프로덕트 제곱이다.
𝜙(𝐚)T𝜙(𝐛) = (𝐚T𝐛)²
이 수식이 의미하는 바는, 트레이닝 인스턴스에 트랜스포메이션을 적용하고 싶을 때, 세컨 디그리 폴리노미얼을 적용할 필요 없이, 그냥 트랜스폼된 벡터에 닷프로덕션만 하고 제곱하면 됨
머신러닝에서의 커널이란 어떤 함수가 닷 프로덕트를 할 수 있는 것이다.
이외에도 오리지널 백터의 조합만으로 나타낼 수 있으면 그것은 커널이라 불릴 수 있으며 SVM에 적용될 수 있다.
4-6. Online SVMs
Linear SVM classifier를 만들기 위해 온라인 SVM classifier를 구현하는 한 방법은 Gradient Descent를 primal problem에서의 코스트 펑션을 최소화 하기 위해 이용하는 것이다.
느리다는 단점이 있지만, 전체 데이터셋을 한 번에 못 넣더라도 데이터셋의 사이즈가 커도 학습 가능하다는 장점이 있다.
힌지로스
SVM 데이터셋이 많을 때는 커널트릭 보다 힌지로스를 사용하면 Gradient Descent로 문제를 푸는 것이 가능해짐.
'CS > ML' 카테고리의 다른 글
| [ML] 9주차 - Dimensionality Reduction (1) | 2023.11.03 |
|---|---|
| [ML] 요점정리 (1) | 2023.10.25 |
| [ML] 4주차 - 트레이닝 모델 (1) | 2023.10.22 |
| [ML] 머신러닝 3주차 - Classification (2) | 2023.10.08 |
| [ML] 머신러닝 2주차 복습 정리 (1) | 2023.10.01 |
