📚 SVM
✅ 개요
• 2010년 전후로 많이 사용되었는데 정형 데이터에 대해서는 앙상블 기법, 비정형 데이터에 대해서는 인공신경망이 등장하면서 상대적으로 사용 빈도가 감소했다.
• 주로 분류 문제에 많이 사용된다. 관측치를 벡터로 변환해서 공간상의 점으로 표현하고 그 점들을 구분하는 여러 개의 hyperplane(직선) 중에서 최적의 직선을 찾는 방식으로 학습한다.
• n차원 공간(피쳐가 n개가 있는 경우)에 대한 하이퍼플레인은 다음과 같이 표현된다.
즉 위와 같이 2차원 공간에서는 직선의 형태가 되고 b0, b1, b2와 같은 파라미터에 의해서 직선의 형태가 달라진다. SVM은 학습을 통해서 최적의 파라미터를 탐색한다.
✅ 최적의 hyperplane을 탐색하는 방법
hyperplane과 가장 가까운 벡터들을 support vector라고 하고, support vector와 hyperplane의 거리를 margin 이라고 한다. SVM은 margin을 가장 크게 하는 hyperplane을 선택한다.
최적의 hyperplane을 선정하기 위해서는 margin을 계산해야 하고,
이를 위해서는 margin을 hyperplane의 파라미터에 대한 함수로 나타내야 margin을 최대화 하는 파라미터를 구할 수 있다.
margin은 서포트 벡터와 하이퍼플레인 사이의 거리이기 때문에 점과 직선 사이의 거리 공식으로 구할 수 있다.
점(x0, y0)과 직선 ax + by + c = 0 사이의 거리는 다음과 같이 구할 수 있다.
위의 식에서 분자는 특정한 상수 값이기 때문에 k로 표현할 수 있다.
따라서 margin값은 a와 b에 의해서 달라지고, margin을 최대화하기 위해서는 분모의 값을 최소화해야 한다. 따라서 SVM에서는 아래와 같이 분모의 파라미터를 최소화 하는 방향으로 학습을 진행한다.
단, SVM의 목적함수를 사용할 때에는 제약조건이 존재한다.
위의 목적함수의 분자에 절대값이 있기 때문에 k는 + 또는 -가 될 수 있다.
하이퍼 플레인을 나타내는 식은 f(x)= b0+b1x1+b2x2=0이고, 아래 그림에서 초록색 직선이라고 한다.
이 경우에 ①,② 는 하이퍼플레인에 대해서 k 만큼 위아래로 평행이동한 직선 형태로 나타낼 수 있다.
k는 고정된 값이기 때문에 SVM이 margin을 최적값을 찾는 데에 영향을 주지 않는다.
따라서 계산 편의를 위해서 보통은 k=1로 자주 표현한다.
k=1 이고, class =1(+ )또는 -1(o) 으로 2개만 있는 경우에는 아래 그림과 같이 표현이 가능한데,
하이퍼플레인을 기준으로 위쪽에 있는 + 관측치들은 f(x) ≥ 1 을 만족하고 yi =1 이기 때문에
f(x) * yi ≥ 1 이 된다.
o 관측치들의 경우 f(x) ≤ -1 이고 yi = -1 (여기서 종속변수는 1,0이 아니라 1,-1 이라고 가정함)이라서 f(x) * yi ≥ 1 이다.
따라서 학습데이터의 관측치에 대해서, 관측치가 가지는 종속변수의 값과 상관없이 f(x) * yi ≥ 1 라는 제약조건이 생긴다.
이 조건을 반영해서 margin을 최대화하는 값을 구한다. margin을 최대화하기 위해서는 분모의 값이 최소화되어야 한다.
제약조건이 없이 b1, b2만 최소화하는 경우에는 미분을 통해서 최소값을 쉽게 구할 수 있지만, 제약조건이 있는 경우에는 라그랑주 승수법(Lagrange Multiplier Method)를 사용해야 한다.
✅ Margin 계산 공식 유도 (점과 직선사이의 거리)
Margin은 서포트 벡터와 하이퍼플레인 사이의 거리를 의미하고, 이를 구하기 위해서는 점과 직선 사이의 거리를 계산해야 한다. 점과 직선 사이의 거리를 구하는 식이 어떻게 도출되는지 알기 위해서
(1) 법선 벡터
(2) 한 벡터와 그에 대한 법선 벡터가 왜 수직인지 증명
(3) (1),(2)를 사용해서 점과 직선 사이의 거리 표현
순서로 식 유도를 진행한다.
🏷️ (1) 법선 벡터 (normal vector)
특정 벡터와 수직인 관계를 갖는 벡터를 법선 벡터라고 한다.
2차원에서 ax + by = c 에 대한 법선벡터는 N = (a,b) 로 나타낼 수 있다. 즉, 벡터 N의 좌표가 직선의 계수인 (a,b) 이다.
🏷️(2) 빨간 벡터와 법선 벡터와 왜 수직인지 증명
위 그림에서 왜 두 벡터가 수직이 되는지를 살펴보면 다음과 같다.
ax + by =c 직선을 지나는 임의의 두 점 X = (x,y) 와 X0 = (x0, y0) 이 있으면,
위 그림에서 붉은색 직선을 아래와 같이 표현할 수 있다.
여기서 X, X0은 ax+by=c 직선 위에 있으므로
좌변과 우변에 대해서 ①- ② 를 하면 아래 식을 만족해야 한다.
일반적으로 벡터의 관계는 다음과 같이 나타낼 수 있다. (방향 유의할 것)
이를 활용하기 위해서 위 그림에서 각각의 벡터를 아래와 같이 나타낼 수 있다. 화살표 방향에 유의할 것.
여기서 관심 있는 것은 빨간색 벡터(X0X)이므로 식을 정리하면
여기서 OX 벡터가 가 갖는 좌표는 X = (x,y) 이고 OX0 벡터가 갖는 좌표는 X0 = (x0,y0) 이 된다.
따라서 위 식에 대입해서 빼면 아래와 같이 표현이 가능하다.
앞서서 ①- ② 를 한 식을 바로 위의 식과 내적 연산을 이용해서 표현할 수 있다.
여기서 N 벡터를 (a,b)로 나타내서 N=(a,b)라고 하면 위 식은 두 벡터의 내적 연산 형태로 볼 수 있다.
벡터의 내적은 아래 식으로 계산한다. 내적 연산 형태에 따라서 이 식이 0이 되어야 한다.
하지만 벡터의 길이는 0이 될수 없으므로 cos θ = 0이 되어야 하고, cos θ=0은 θ =90도인 경우에만 가능하다.
즉, 두 벡터의 내적 값이 0이면 두 벡터는 서로 수직이다.
🏷️(3) 점과 직선사이의 거리 공식
위의 그림을 통해서 일반화된 식을 작성한다. SVM에서는 margin을 구하는 것이 중요하고 이것이 점과 직선 사이의 거리를 통해서 계산된다. 위의 그림에서는 d가 margin을 나타낸다.
우선 cos θ 를 계산하면
d를 계산하기 위해서 d에 대한 식으로 정리한다. (2)의 마지막 단계에 있는 벡터의 내적 공식을 활용하기 위해서 분자와 분모에 |n|을 곱하면 분자 부분을 마지막 항처럼 정리할 수 있다.
벡터 PQ를 아래와 같이 나타낼 수 있음을 확인하고 넘어가자.
이제 위 식의 분자 부분을 벡터 PQ와 벡터 n의 내적 연산 형태로 풀어서 쓰면
또한 분모 부분은 원점에서 n 벡터의 거리이므로 이를 표현하면
따라서 아래와 같이 점과 직선 사이의 거리(=margin)을 계산할 수 있다
📌 예시
위 경우에 x1', x2'에서 하이퍼플레인까지 직선의 거리 M을 구하면
📚 선형의 Hyperplane이 존재하지 않는 경우
2차원에서 관측치가 위와 같이 분포하는 경우, 선형 직선으로 데이터를 완벽하게 분리할 수 없다. 이 때 사용할 수 있는 방법은 다음과 같다.
① Slack 변수 사용하기
② 관측치들을 고차원 공간으로 이동시켜서 분리하기
✅ 1. Slack 변수 사용하기
• 어느 정도 에러가 발생하는 것을 허용하면서 hyperplane을 찾는 방법. 즉, 하이퍼플레인을 찾을 때 잘못 레이블링이 되는 관측치가 발생하는 것을 어느 정도 허용하는 방법.
• slack 변수는 각 관측치의 에러 정도를 나타내는 역할을 한다. 각 관측치마다 slack 변수가 하나씩 존재한다. 분류가 올바르게 된 경우에는 slack 변수= 0 이 되고, 분류가 제대로 안 된 경우만 slack 변수 값이 0보다 커진다.
y=1 인 경우에 f(x)=1 과의 거리를 나타내고
y=-1 인 경우에 f(x)=-1 과의 거리를 나타낸다.
위 그림에서 x1은 - 클래스 이지만 + 로 잘못 분류되었다. 이때 x1 관측치의 slack 변수 값은 - 클래스의 서포트 벡터를 지나는 직선과의 거리(ξ1) 이 된다.
반대로 x2은 + 클래스 이지만 -로 잘못 분류되었다. 이때 x2 관측치의 slcak 변수 값은 + 클래스의 서포트 벡터를 지나는 직선과의 거리(ξ2)가 된다.
ξ1, ξ2 값이 클수록 error 정도가 크다는 것을 의미한다.
slack 변수를 포함하여 margin을 최대화(=분모를 최소화)하는 식을 수정하면 위와 같다. slack 변수는 관측치마다 존재하므로 여기서 N은 관측치의 갯수를 나타낸다. 즉 위의 식은 margin을 최대화 하면서 에러의 정도(=slack 변수의 합)을 최소화하는 hyperplane을 찾는다는 것을 의미한다.
여기서 C는 하이퍼 파라미터인데, 이 값이 커지면 slack 변수의 비중이 커지므로 에러의 값이 작아져야 한다는 것을 의미한다. 하지만 C 값이 너무 커지면 과적합 문제가 발생할 가능성이 높아진다. 여기서 C는 규제화 텀에서 람다와 역수의 관계이다. 람다 값이 커지면 규제화를 많이 하게 돼서 파라미터가 줄어들고 학습 데이터에 대한 설명력이 감소한다. 반대로 C는 커질수록 학습 데이터에 대한 설명력이 증가하므로 과적합 가능성이 증가한다.
위에서도 조건이 붙는데, 해당 부분은 그만큼의 에러를 허용한다는 것을 의미한다. 위 그림에서 점선 부분을 f(xi) = 1-ξ2 로 표현할 수 있는데, 이는 f(xi)=1 로부터 ξ2 만큼 떨어져 있을 수 있다는 것을 의미한다.
✅ 2. 벡터를 고차원으로 이동하기 : kernel trick 사용
왼쪽과 같이 2차원에서는 두 개의 클래스를 완벽하게 구분하는 hyperplane 이 존재하지 않지만, 이를 3차원 형태로 변환할 경우에는 적절한 hyperplane을 찾을 수 있다.
저차원의 관측치를 고차원으로 이동한 후에 hyperplane을 찾는 과정에서 다음 단계가 필요하다.
1) 각 관측치를 고차원으로 이동시키기 (각 관측치 벡터에 행렬을 곱하면 고차원으로 이동함)
2) 고차원에서의 관측치 사이의 내적 계산하기
1)을 이해하기 위해서는 행렬과 벡터의 기하학적 의미를 참고하면 좋다. 행렬은 특정 벡터를 새로운 위치로 변환하는 선형변환 역할을 수행한다. 이 때 다른 차원으로도 이동할 수가 있다.
위에서 원래 2차원인 v 벡터에 A행렬을 곱하면 3차원인 Av 벡터로 변환된다.
하지만 위의 1),2) 과정을 따로 수행하면 연산 시간이 너무 오래걸린다. 따라서 이를 해결하기 위해서 선형대수에서 사용하는 방법인 kernel function(kernel trick)을 사용한다. kernel 함수를 사용하면 각 관측치를 직접 고차원으로 보내지 않고 간단하게 고차원에서의 내적을 계산한 결과를 얻을 수 있다. kernel function에는 다항 kenel(polynomial kernel) 과 rbf kernel(radius basis function)이 있다.
📌 Polynomial Kernel Function (다항 커널)
다항 커널 함수의 형태는 위와 같다. x,y는 저차원에 존재하는 각각 별도의 벡터를 나타내며, 우측 항의 식을 통해서 고차원으로 보낸 후의 내적 결과를 리턴하는 것과 동일한 연산을 진행한다. 우측 항에서 xT * y 는 내적 연산을 의미한다.
b, Γ, d 는 사용자가 정의하는 하이퍼 파라미터이다.
• d : 값이 증가할수록 더 높은 차원에서 내적 연산을 수행하게 된다. 데이터셋에 따라서 적절한 차원수가 다르기 때문에 직접 테스트 해봐야 한다.
• Γ : 값이 커질수록 고차원 공간에서 두 벡터의 내적값이 커진다. 이는 두 벡터의 유사도가 커진다는 것을 의미한다.
예시) b=0, Γ=1, d=2 이고, x와 y는 이차원 상의 벡터(점) 이라고 가정한다.
위 식은 아래와 같이 3차원의 1*3 벡터 두 개의 내적으로 표현할 수도 있다.
즉 kenel 함수를 사용할 때 d=2 로 설정하면 2차원 상의 벡터를 3차원 상으로 이동해서 내적을 계산할 수 있다.
즉 원래 저 차원의 x,y가 위와 같이 3차원으로 이동한 효과가 있다. 이렇게 하면 직접 고차원으로 보내서 내적 연산을 하는 것보다 속도 측면에서 이점이 있다.
📌 RBF Kernel Function
rbf 커널은 저차원 공간의 벡터를 무한 차원(infinite dimension)으로 보내고, 그곳에서 내적을 구하는 효과가 있다.
https://www.youtube.com/watch?v=XUj5JbQihlU&t=1553s
위와 같이 표현할 수 있고 우측 항을 감마를 이용해서 간단하게 표현하면
‖x-y‖2 부분은 두 벡터의 유클리디안 거리의 제곱을 의미한다.
Γ는 다항 커널과 동일한 의미이지만 여기서는 -가 붙어 있기 때문에 값이 커질수록 두 벡터의 내적 값이 작아져서 유사도가 낮아진다. 이는 굉장히 가까운 관측치들만 유사하다고 판단하게 된다는 것을 의미한다. 이렇게 되면(=Γ의 값이 커지면) 저차원에서의 boundary 형태가 복잡해진다.
위 그림을 참고하면 Γ 값이 커질수록 boundary 형태가 복잡하게 나타나고, 과적합 가능성이 증가하는 것을 확인할 수 있다.
✅ 예시 코드
https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html
kernel 함수의 종류에는 여러가지가 있지만 주로 poly, rbf가 많이 사용된다.
감마 값도 주로 직접 설정하기 보다는 scale이나 auto를 많이 사용한다.
📚 Reference
https://en.wikipedia.org/wiki/Support-vector_machine
https://kr.mathworks.com/discovery/support-vector-machine.html
https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html
'머신러닝, 딥러닝 > 머신러닝' 카테고리의 다른 글
| GMM (Gaussian Mixture Models) (0) | 2022.06.18 |
|---|---|
| 특이값 분해 (Singular Value Decomposition) (0) | 2022.06.17 |
| 차원축소 - PCA(Principal Component Analysis) (0) | 2022.05.30 |
| 차원축소 기본 - 고유값, 고유벡터, 고유분해 (0) | 2022.05.29 |
| 앙상블 기법(Ensemble Method) - Boosting (0) | 2022.05.28 |
.svg){kind=link}
댓글