5 장. SVM 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학.

Presentation on theme: "5 장. SVM 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학."— Presentation transcript:

1 5 장. SVM 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학

2 들어가는 말 SVM의 차별성 SVM 포털 기존 분류기는 ‘오류율을 최소화’
SVM은 ‘여백을margin 최대화’하여 일반화 능력의 극대화 꾀함 SVM 포털

3 5.1 발상 분류기의 일반화 능력 중요한 문제 ②보다 ③이 여백이 더 크다. 즉 ③이 ②보다 일반화 능력이 뛰어나다.
신경망은 초기값 ①에서 시작하여 ②를 찾았다면 거기서 멈춘다. 왜? SVM은 ③을 찾는다. 중요한 문제 여백이라는 개념을 어떻게 공식화할 것인가? 여백을 최대로 하는 결정 초평면을 어떻게 찾을 것인가?

4 5.2 선형 SVM 이진 분류를 위한 결정 초평면과 그것의 수학적 특성

5 5.2 선형 SVM 예제 5.1 아래는 모두 같은 직선 점 x=(2,4)T에서 직선까지 거리

6 5.2.1 선형 분리 가능한 상황 w (직선의 방향)가 주어진 상황에서,
‘두 부류에 대해 직선으로부터 가장 가까운 샘플까지의 거리가 같게 되는’ b를 결정 (①과 ②는 그렇게 얻은 직선) 여백은 그런 직선에서 가장 가까운 샘플까지 거리의 두 배로 정의함 가장 가까운 샘플을 서포트 벡터라 부름

7 5.2.1 선형 분리 가능한 상황 이제 문제를 공식화해 보자. 그림 5.3에서 ①과 ②는 어느 것이 최적에 가까운가?
①보다 나은 것이 있나? 전형적인 최적화 문제임

8 5.2.1 선형 분리 가능한 상황 여백은 아래와 같이 공식화 이제 문제를 조건부 최적화 문제로 공식화
훈련 집합 X={(x1,t1),…,(xN,tN)}

9 5.2.1 선형 분리 가능한 상황 (5.5)를 간단한 형태로 변형하면, 문제의 특성 해의 유일성
(5.6)은 볼록이므로 해는 유일하다. 따라서 구한 해는 전역 최적 점을 보장한다. 문제의 난이도 N개의 선형 부등식을 조건으로 가진 2차 함수의 최적화 문제 조건부 최적화 문제는 라그랑제 승수로 푼다. ( 절)

10 5.2.1 선형 분리 가능한 상황 라그랑제 승수 방법 목적 함수와 조건을 하나의 식 (즉 라그랑제 함수 L)으로 만들고, KKT조건을 이용하여 라그랑제 함수를을 최적화하는 해를 구한다. (αi는 라그랑제 승수) KKT 조건이란?

11 5.2.1 선형 분리 가능한 상황 (5.7)의 KKT 조건 (5.11)에 의하면 모든 샘플이 αi=0 또는 ti(wTxi+b)-1=0이어야 함. αi≠0인 샘플이 서포트 벡터임 (5.8)에 의하면, 라그랑제 승수 αi 알면 w 구할 수 있음 (결정 초평면을 구한 셈) 이제부터 ‘w 구하는 대신 라그랑제 승수 구하는’ 문제로 관심 전환 (5.11)로 b 구할 수 있음

12 5.2.1 선형 분리 가능한 상황 문제의 볼록 성질을 이용하여 풀기 쉬운 형태로 변환
볼록 성질을 만족하는 조건부 최적화 문제는 Wolfe 듀얼로 변형할 수 있다. (5.6)을 Wolfe 듀얼로 바꾸어 쓰면, 부등식 조건이 등식 조건이 되어 풀기에 유리함

13 5.2.1 선형 분리 가능한 상황 간단한 수식 정리를 하면, 흥미로운 특성들 2차 함수의 최대화 문제임
w와 b가 사라졌다. (α를 찾는 문제가 되었다.) 특징 벡터 xi가 내적 형태로 나타난다. (비선형으로 확장하는 발판) 목적 함수의 두번째 ∑항은 N2개의 항을 갖는다. (여전히 풀기 어려운 문제)

14 5.2.1 선형 분리 가능한 상황 지금까지 한 일을 정리하면,

15 5.2.1 선형 분리 가능한 상황 예제 5.2: 두 개 샘플을 가진 경우의 문제 (5.13)의 풀이 훈련집합 (5.13)은
실제 값을 대입하면,

16 5.2.1 선형 분리 가능한 상황 예제 5.2: 두 개 샘플을 가진 경우의 문제 (5.13)의 풀이 정리하여 풀면,
(1/4,1/4)T에서 최대값을 가짐 (5.8)로 w, (5.11)로 b를 구하면 결국 결정 직선은

17 5.2.1 선형 분리 가능한 상황 예제 5.3: 세 개 샘플을 가진 경우의 문제 (5.13)의 풀이 훈련집합
(5.13)에 실제 값을 대입하면, 이 문제를 어떻게 풀 것인가?

18 5.2.1 선형 분리 가능한 상황 예제 5.3: 세 개 샘플을 가진 경우의 문제 (5.13)의 풀이
네 가지 경우로 나누어 분석적 풀이 ① α1=0, α2≠0, α3≠0 ② α1≠0, α2=0, α3≠0 ③ α1≠0, α2≠0, α3=0 ④ α1≠0, α2≠0, α3≠0 ① ② ④ 는 모순이므로 버림. 왜 모순? ③ α1≠0, α2≠0, α3=0인 경우를 풀면, 등식 조건으로부터 α1=α2이므로 (5.8)과 (5.11)로 w와 b를 구하면 결정 직선은 결국 α1=1/4, α2=1/4, α3=0

19 5.2.2 선형 분리 불가능한 상황 선형 분리 불가능한 상황 샘플 (x,t)의 세 가지 상황

20 5.2.2 선형 분리 불가능한 상황 슬랙 변수 ξ를 도입하여 하나의 식으로 쓰면,

21 5.2.2 선형 분리 불가능한 상황 문제 공식화 길항tradeoff 관계를 갖는 두 가지 목적을 동시에 달성
목적 함수를 다시 쓰면 첫번째 항은 목적 1, 두번째 항은 목적 2

22 5.2.2 선형 분리 불가능한 상황 문제 공식화

23 5.2.2 선형 분리 불가능한 상황 라그랑제 승수로 풀어보면, 라그랑제 함수 KKT 조건

24 5.2.2 선형 분리 불가능한 상황 라그랑제 승수로 풀어보면, Wolfe 듀얼로 변형

25 5.2.2 선형 분리 불가능한 상황 라그랑제 승수로 풀어보면, (5.26)을 정리하면 (5.13)과 같다! 한 가지만 빼고.
0≤αi가 0≤αi≤C로 바뀜

26 5.2.2 선형 분리 불가능한 상황 예제 5.4: 세 개 샘플을 가진 경우의 문제 (5.27)의 풀이
훈련집합 (선형 분리 가능한가?) (5.27)에 실제 값을 대입하면, 이 문제를 어떻게 풀 것인가?

27 5.2.2 선형 분리 불가능한 상황 예제 5.4: 세 개 샘플을 가진 경우의 문제 (5.27)의 풀이
네 가지 경우로 나누어 분석적 풀이 ① α1=0, α2≠0, α3≠0 ② α1≠0, α2=0, α3≠0 ③ α1≠0, α2≠0, α3=0 ④ α1≠0, α2≠0, α3≠0 ① α1=0, α2≠0, α3≠0인 경우를 풀면, 등식 조건으로부터 α2=α3이므로 w와 b를, 그리고 결정 직선 그림에서 직선 ① x1은 오분류됨 결국 α1=0, α2=2, α3=2

28 5.2.2 선형 분리 불가능한 상황 예제 5.4: 세 개 샘플을 가진 경우의 문제 (5.27)의 풀이
② α1≠0, α2=0, α3≠0인 경우는 모순. 왜? ③ α1≠0, α2≠0, α3=0인 경우를 풀면, 등식 조건으로부터 α1=α2이므로 w와 b를, 그리고 결정 직선 그림에서 직선 ③ x3은 오분류됨 결국 α1=1/4, α2=1/4, α3=0

29 5.2.2 선형 분리 불가능한 상황 예제 5.4: 세 개 샘플을 가진 경우의 문제 (5.27)의 풀이
④ α1≠0, α2≠0, α3≠0인 경우를 풀면, α1=α2-α3를 대입한 후, 를 풀면 그림에서 직선 ④ 세 개의 샘플 모두 서포트 벡터 C에 따른 유효성 C<2이면 ③만 유효 2≤C<6.5이면 ①③만 유효 6.5≤C이면 모두 유효 무엇을 의미하는가? 결국 α1=3/2, α2=13/2, α3=5

30

31 5.3 비선형 SVM 비선형 SVM으로 확장 어려울 듯 보이지만 의외로 간단 커널의 활약
커널 적용이 가능한 이유는 (5.27)에서 ‘특징 벡터가 내적 형태로만’ 나타나기 때문

32 5.3.1 커널 대치 더 높은 차원으로 매핑하여 선형 분리 불가능을 가능으로 만들 수 있다. 예제 5.5
원래 공간 매핑 함수 매핑 결과

33 5.3.1 커널 대치 공간 매핑 SVM이 사용하는 커널 함수 예제 5.6 커널 함수의 성질 커널 함수 증명

34 5.3.1 커널 대치 커널 대치 (커널 트릭) 어떤 수식이 벡터 내적을 포함할 때, 그 내적을 커널 함수로 대치하여 계산하는 기법 실제 계산은 L 공간에서 K()의 계산으로 이루어짐 고차원 공간 H에서 작업하는 효과 적용 예, Fisher LD의 커널 LD로의 확장, PCA를 커널 PCA로 확장 SVM에 적용 가능 (5.13)과 (5.27)에 벡터 내적만 나타나기 때문 실제 계산은 L에서 이루어지지만 분류는 선형 분류에 유리한 H에서 수행 꾀를 부려 차원의 저주를 피한 셈

35 5.3.2 커널 대치를 이용한 비선형 SVM 커널 대치를 이용한 비선형 SVM
선형 분류가 부적절하면 L 대신 H 공간에서 분류 (그림 5.8) (5.13)과 (5.27)의 목적 함수를 바꾸어 씀

36 5.3.2 커널 대치를 이용한 비선형 SVM SVM 이 사용하는 대표적인 커널들
커널 함수에 대응하는 매핑 함수는 몰라도 된다. 단지 존재한다는 사실만 알면 된다. 왜?

37 5.4.1 학습 SVM 학습이란? 비선형 SVM을 위한 조건부 최적화 문제 (커널 트릭 적용)
(5.1)의 w와 b를 구하는 과정 라그랑제 승수 α를 구하면 된다. 비선형 SVM에서는 아래 (5.35)를 풀어 α를 구함 비선형 SVM을 위한 조건부 최적화 문제 (커널 트릭 적용)

38 5.4.1 학습 (5.35)를 어떻게 풀 것인가? 예를 들어, CENPARMI 숫자 DB의 경우 N=4000이다. 따라서 목적 함수는 개의 2차 항을 가지 매우 복잡한 식 수치적 방법 대표적 알고리즘 SMO Cutting-plane

39 5.4.2 인식 인식은 어떻게 할 것인가? 선형 SVM 라그랑제 승수 α로 w 구하기 서포트 벡터만 필요

40 5.4.2 인식 비선형 SVM w 를 미리 구해놓을 수 없다. 인식 시간은 서포트 벡터의 개수에 비례

41 5.4.3 M 부류 SVM M 부류 SVM으로 확장 이제까지는 이진 SVM 1대 M-1 방법
dj(x)는 부류 ωj를 위한 분류기 (ωj 샘플과 나머지 샘플을 분류함) 1대1 방법 모든 부류 쌍에 대해 이진 분류기 만듦 M(M-1)/2개의 이진 분류기 필요) 인식 결과를 가지고 투표 1대 M-1 방법을 많이 사용

42 5.5 SVM의 특성 여백이라는 간단한 아이디어로 breakthrough 이룩함 SVM의 특성 사용자 설정 매개 변수가 적다.
커널 종류와 커널에 따른 매개 변수 (5.15)에서 목적 1 과 목적 2의 가중치 C 최적 커널을 자동 설정하는 방법 없음 실험에 의한 휴리스틱한 선택 일반화 능력 뛰어남 구현이 까다로움 OSS 활용 SVMlight LIBSVM