선형 SVM
분류기의 일반화 능력
②보다 ③이 여백이 더 크다.
즉 ③이 ②보다 일반화 능력이 뛰어나다.
신경망은 초기값 ①에서 시작하여 ②를 찾 았다면 거기서 멈춘다. 왜?
→ 여백을 고려하지 않기 때문임
SVM은 ③을 찾는다.
초평면의 수학적 특성
h = 점과 선의 거리를 뜻함 (아래 그림 참고)
d(x) = 2(x1) + (x2) - 4 =0일 때,
여백이란?
여백은 직선(1)에서 가장 가까운 샘플까지 거리의 두 배로 정의함 (2s)
가장 가까운 샘플을 서포트 벡터(S.V)라 부름
여백 공식
Q. |d(x)|가 왜 1이 되는 가?
A. 정규화 시켜서 거리를 1로 만들기 때문임
1. 선형분리 가능한 상황
여백 최대화(선형분리 가능한 상황)
아래와 같이 더 간단히 표현할 수 있음
위의 식을 최대화 하는 것은
역수를 취해서 최소화 하는것 과 같은 문제임
위와 같이 표현했을 때의 특성
해의 유일성
- 아래로 볼록이므로 해는 유일하다.
따라서 구한 해는 전역 최적 점을 보장한다.
문제의 난이도
- N개(N개 sample에 대한)의 선형 부등식을 조건으로 가진 2차 함수의 최적화 문제
- 조건부 최적화 문제는 라그랑제 승수로 푼다.
라그랑제 승수방법:
목적 함수와 조건을 하나의 식 (즉 라그랑제 함수 L)으로 만들고,
KKT(KarushKuhn-Tucker) 조건을 이용하여
라그랑제 함수를 최적화하는 해를 구한다. (α는 라그랑제 승수)
우변의 2번째항의 의미는 샘플하고 결정경계면사이의 거리인데
이 값이 0이 되려면 샘플과 서포트벡터사이의 거리가 0이고
즉, 결정경계면위에 샘플이 있는거라고 이해해도됨
KKT조건이란?
1. 미분을 해서 0으로 놓고
2. α >=0: 라그랑제 승수가 0과 같거나 0보다 크고
3. 아래 식에서 α가 0이 되거나, t(wx+b) = 1이라는 것임
즉, 위 식은 모든 샘플이 αi=0 또는 t i(wTxi+b)-1=0이어야 함.
αi≠0인 샘플이 서포트 벡터임
(조건1)에 의하면, 라그랑제 승수 αi 알면 w 구할 수 있음 (결정 초평면을 구한 셈)
이제부터 ‘w 구하는 대신 라그랑제 승수 구하는’ 문제로 관심 전환
(조건3)로 b 구할 수 있음
Wolfe듀얼을 활용하여 위의 최적의 해를 구하는 방법
Wolfe듀얼은 최솟값을 푸는 문제를 최대값을 푸는 문제로 변형하는 것임
대입하면 아래와 같은 식이 됨
원래 1/2인데, -(1/2)이 되었으므로
최소값을 푸는 문제가 최대값을 푸는 문제로 변경됨
흥미로운 특성들
2차 함수의 최대화 문제임
w와 b가 사라졌다. (α를 찾는 문제가 되었다.)
특징 벡터 xi가 내적 형태로 나타난다. (비선형으로 확장하는 발판)
목적 함수의 두번째 ∑항은 N^2 개의 항을 갖는다. (여전히 풀기 어려운 문제)
예제) 두 case모두 결정경계는 동일하게 나타남
결정 경계면을 결정하는 것은 support vector인데,
x3이 추가되더라도, 여전히 x1, x2가 support vector이므로 동일한 경계면이 나옴
2. 선형분리 불가능한 상황
경우1: 속이 빈 원과 네모를 의미함
경우2: 더블 네모를 뜻함
경우3: 더블 원을 듯함
위와 같이 슬랙변수를 활용하여 간단히 표현할 수 있음
목적변수 (위의 방법과 동일함)
동일하게 Wolfe 듀얼로 변형하여 최대화 문제로 변형하고
위식에서 우변의 2째항은 오류를 의미하므로
C를 통해서 오류의 값을 조정할 수 있음
C가 크면클수록 오분류를 거의 허용하지 않는 방향으로 결정경계면이 구해짐
C가 작으면 작을 수록 오분류를 허용함
즉, 아래와 같음
예제) 아래경우 결정경계면 구하기
1) α1=0, α2=2, α3=2
2) 모순
3) α1=1/4, α2=1/4, α3=0
4) α1=3/2, α2=13/2, α3=5
C에 따른 유효성
C<2이면 ③만 유효
2≤C<6.5이면 ①③만 유효
6.5≤C이면 모두 유효
③은 small C: soft margin
④는 large C: hard margin
그러면 1, 3, 4 경우 어떤게 더 좋다고 할 수 있을까?
1번도 small C이지만 margin을 최대화 하지 못하는 상황임
3번이 제일 좋다고 할 수 있음
4번은 overfitting이 될 가능성이 높기 때문임
** 참고로 training 보다, test 시점에 더 좋은 분류기가 더 좋은 것임