Semi-supervised Document classification (probabilistic model and EM)

Presentation on theme: "Semi-supervised Document classification (probabilistic model and EM)"— Presentation transcript:

1 Semi-supervised Document classification (probabilistic model and EM)

2 Document Classification: Bag of Words Approach
aardvark 0 about 2 all 2 Africa 1 apple 0 anxious 0 ... gas 1 oil 1 … Zaire 0

3 Supervised: Naïve Bayes Learner
Train: For each class cj of documents 1. Estimate P(cj ) 2. For each word wi estimate P(wi | cj ) Classify (doc): * Assign doc to most probable class * assuming words are conditionally independent, given class

4 Accuracy vs. # training examples

5 What if we have labels for only some documents?
Learn P(Y|X) Y X1 X2 X3 X4 1 ? Y X1 X4 X3 X2 EM: Repeat until convergence Use probabilistic labels to train classifier h Apply h to assign probabilistic labels to unlabeled data

6 From [Nigam et al., 2000]

7 E Step: wt is t-th word in vocabulary M Step:

8 Using one labeled example per class
Words sorted by P(w|course) / P(w| : course)

9 20 Newsgroups

10 20 Newsgroups

11 Hidden Markov Model

12 순차 데이터 시간성이 없는 데이터 시간성 있는 데이터 (순차 데이터) 특징들의 선후 관계는 무의미
특징들의 선후 관계는 매우 중요함

13 순차 데이터 순차 데이터 기호들이 시간에 따라 의존성 가짐 가변 길이 관측 벡터로 표현
관측 oi가 가질 수 있는 값의 집합을 알파벳이라 함 알파벳 V={v1,v2,…,vm} vi를 기호라 함 기호들이 시간에 따라 의존성 가짐 예) 그림 7.2의 온라인 숫자 P(ot=2|ot-1=6)≈0 P(ot=5|ot-1=6) > P(ot=4|ot-1=6)

14 마코프 모델 우선 은닉 마코프 모델에서 은닉이 빠진 마코프 모델을 공부하자. 러시아 수학자 Andrey Markov가 제안
시간 t에서의 관측은 가장 최근 r개 관측에만 의존한다는 가정 하의 확률 추론

15 마코프 모델 마코프 체인의 합리성은? 예) 최근 사흘의 날씨 정보를 가지고 오늘 날씨 추론
그끄저께 해 (ot-3=해), 그저께 해 (ot-2=해), 어제 비 (ot-1=비) 오늘 비올 확률은? 1차 마코프 체인을 사용한다면 즉 1차 마코프 체인에서는 아래 네 개 확률이 같다. 정말 같을까? 다르다면 오차가 무시할 정도일까?

16 마코프 모델 마코프 모델 날씨 예 1차 마코프 체인 사용 2차 이상에서는 추정할 매개 변수가 많아 현실적인 문제 발생
알파벳을 구성하는 기호 각각을 상태로 간주 날씨 예 V={비, 구름, 해} 기후 관측에 의해 얻은 날씨 변화 확률

17 마코프 모델 상태 전이 상태 전이 확률 행렬과 상태 전이도

18 마코프 모델 마코프 모델로 무엇을 할 수 있나? 관측벡터 O의 확률 구하기 예제 7.1

19 마코프 모델 또 다른 예, 온라인 필기 숫자 인식

20 마코프 모델 또 다른 예, 온라인 필기 숫자 인식 상태 전이 확률 행렬을 구하면, 초기 확률 행렬을 구하면,

21 마코프 모델 또 다른 예, 온라인 필기 숫자 인식 이렇게 만든 마코프 모델로 그림 7.6의 샘플이 발생할 확률을 구하면,

22 마코프 모델 마코프 모델과 0차, 2차 마코프 체인과의 비교 (온라인 필기 숫자 예) 0차 마코프 체인

23 마코프 모델 마코프 모델과 0차, 2차 마코프 체인과의 비교 (온라인 필기 숫자 예)
추정할 매개 변수가 64*8개로 증가 꼭 이해하고 기억해야 할 것! (MM과 HMM의 근본적인 차이점) 마코프 모델에서는 상태를 나타내는 노드에 관측 (비, 해, 구름) 그 자체가 들어 있다.즉 상태를 볼 수 있다. HMM에서는 상태를 볼 수 없다. 즉 상태가 은닉된다.

24 은닉 마코프 모델로의 발전 은닉 마코프 모델로의 발전 마코프 모델은 한계를 가진다.
보다 복잡한 현상이나 과정에 대한 모델링 능력의 한계 모델의 용량을 키우기 위해, 상태를 감추다.

25 동기 마코프 체인의 차수와 추정할 매개 변수의 수 HMM 어떤 비결에 의해 이런 뛰어난 능력이 가능한가?
r차에서 mr(m-1) 개의 매개 변수 차수에 따라 기하급수적으로 모델 크기가 증가함 HMM 차수를 미리 고정하지 않고 모델 자체가 확률 프로세스에 따라 적응적으로 정함 따라서 아무리 먼 과거의 관측도 현재에 영향을 미침 즉 P(해|비,비), P(해|비,비,비), P(해|비,비,…,비), P(해|비,비,해,…,해)가 모두 다름 이런 뛰어난 능력에도 불구하고 모델 크기는 감당할 정도임 어떤 비결에 의해 이런 뛰어난 능력이 가능한가? 상태를 감춘다.

26 동기 상태를 감추면, 마코프 모델이 은닉 마코프 모델이 된다.

27 동기 그림 7.7.의 해석 (예를 들어, 해해비구름이 관측되었다.) 마코프 모델
그것은 상태 s3s3s1 s2에서 관측한 것이다. 은닉 마코프 모델 모든 상태에서 {비,해,구름}이 관측 가능하므로 s3s3s1s2일 수도 있고 s1s2s3s1일 수도 있다. 가능한 경우는 몇 가지 일까? 그들의 확률은 다르다. 예를 들어 s3s3s1 s2일 확률은

28 HMM의 예 예제 7.4 여자 친구의 삶 [Wikipedia] 여자 친구의 일상을 관찰, V={산책, 쇼핑, 청소}
날씨는 해와 비 (상태) 내가 가진 정보 답할 수 있나? 그녀가 일주일 연속으로 쇼핑만 할 확률은? 그끄저께 산책, 그저께 산책, 어제 청소했다는데 3일간 그곳 날씨는? 그끄저께 산책, 그저께 산책, 어제 청소했다는데 오늘과 내일 무얼할까? 날씨 날씨에 따른 그녀의 행동

29 HMM의 예 HMM을 사용하면 확률 추론할 수 있다. 어떻게?

30 구성 요소와 세 가지 문제 앞의 예제는 한쪽 면만 조망 모델을 알때 확률 추론하라.
그녀의 삶 예에서는 날씨와 그녀의 행위에 대한 확률 분포 알고 있음 또 다른 측면 어느 것이 상태인가? 상태는 몇 가지인가? (아키텍처 설계) 확률 분포는 어떻게 구하나? (학습) 예) 온라인 필기 인식 무엇이 상태인고 상태를 몇 가지로 할까? 가진 것은 오로지 훈련 집합

31 구성 요소와 세 가지 문제 아키텍처 HMM은 가중치 방향 그래프로 표현 노드가 상태
상태로 사용할 것이 명확한 경우도 있지만 그렇지 않은 경우도 있다. 대표적인 아키텍처 어고딕 모델과 좌우 모델 응용의 특성에 따라 적절한 아키텍처 선택 중요 예를 들어 음성 인식은 좌우 모델이 적당함. 왜?

32 구성 요소와 세 가지 문제 세 가지 매개변수 상태 전이 확률 행렬 A=|aij| 관측 행렬 B=|bj(vk)|

33 구성 요소와 세 가지 문제 세 가지 문제 평가. 모델 Θ가 주어진 상황에서, 관측벡터 O를 얻었을때 P(O| Θ)는?
학습. 훈련집합 X={O1,..,ON}이 주어져 있을때 HMM의 매개 변수 Θ는?

34 알고리즘 이제 세 가지 문제를 풀기 위한 알고리즘을 공부하자. 평가. 동적 프로그래밍 이용
디코딩. 동적 프로그래밍 이용 (Viterbi 알고리즘) 학습. EM 알고리즘 (Baum-Welch 알고리즘)

35 평가 평가 문제란? 평가 문제를 풀어 보자. 모델 Θ가 주어진 상황에서, 관측벡터 O를 얻었을때 P(O| Θ)는?
예) 그녀가 일주일 연속으로 쇼핑만 할 확률은? 평가 문제를 풀어 보자. HMM에서는 O를 관측한 상태 열을 모른다. 우선 O를 관측한 상태 열을 안다고 가정하고 그것을 Q=(q1,…,qT)라 하자. 그럼 아래 식을 유도할 수 있다. 원래 문제 P(O| Θ)는 모든 상태 열에 대해 (7.10)의 식을 더하여 구할 수 있다.

36 평가 예제 7.5 여자 친구의 삶 “그녀가 오늘 산책, 내일 산책, 모레 청소, 그리고 글피 쇼핑할 확률은?”
즉 O=(o1=산책, o2=산책, o3=청소, o4=쇼핑)일 때, P(O| Θ)는? 모든 상태 열을 나열하면,

37 평가 예제 7.5 여자 친구의 삶 상태 열 Q1에 대해 구해 보면, 모든 상태 열에 대한 값을 더하여 답을 구해 보면,

38 평가 답은 구할 수 있다. 하지만, 보다 효율적인 알고리즘이 있다. 예제 7.5에서 상태 열의 개수는 24=16 가지
일반적으로 상태의 수가 n이고 관측 열 O의 길이가 T라면 NT 가지의 상태 열 각각의 상태 열은 2T-1번의 곱셈. 따라서 시간 복잡도는 Θ(NTT) 예) n=5, T=30이라면 *1022 번의 곱셈 필요. 계산 폭발! 보다 효율적인 알고리즘이 있다. 기본 아이디어는 동적 프로그래밍에 의한 중복 계산 제거 예) 예제 7.5의 Q1=‘비비비비’, Q2=‘비비비해’의 계산 P(O,Q1|Θ)=π1b1(산책)a11b1(산책)a11b1(청소)a11b1(쇼핑) P(O,Q1|Θ)=π1b1(산책)a11b1(산책)a11b1(청소)a12b2(쇼핑) 빨간 부분의 계산은 같다.

39 평가 동적 프로그래밍 그림 7.13의 격자에 16개의 모든 상태 열이 들어 있다.
그림 7.13의 격자에 16개의 모든 상태 열이 들어 있다. 예, 진한 파랑은 Q1=‘비비비비’, 연파랑은 Q7=‘비해해비’에 해당 αt(i) 는 관측 벡터의 일부 o1o2…ot를 관측하고 시간 t에 si에 있을 확률

40 평가 전방 알고리즘forward algorithm 초기식을 포함시키 완벽한 식으로 정리하고 그것을 가상 코드로 적으면,
시간 복잡도는Θ(N2T) n=5, T=30이라면 750 번의 곱셈 이전의 낱낱 계산과 비교해 보라.

41 평가 예제 7.6 전방 계산에 의한 확률 평가 t=1일때 t=2일때 t=3과 4일때 답은

42 디코딩 디코딩 문제란? 생각 1 모델 Θ가 주어진 상황에서, 관측벡터 O를 얻었을때 그것의 최적 상태열은?
예) 그끄저께 산책, 그저께 산책, 어제 청소했다는데 3일간 그곳 날씨는? 무엇을 기준으로 최적을 판단할 것인가? 생각 1 예를 들어, O=(o1=산책, o2=산책, o3=청소, o4=쇼핑)이었다면, 산책은 s1보다 s2가 확률이 높으므로 s2, 청소는 s1이 확률이 높으므로 s1, 쇼핑은 s1이 확률이 높으므로 s1 을 취함. 즉 O의 최적 상태열은 Q= s2s2s1s1=‘해해비비’로 함 합리적인가?

43 디코딩 합리적인 생각은, P(O,Q|Θ)를 기준 함수로 채택하고 이것을 최대화하는 를 찾아야 한다. 즉,
평가 문제와 비슷하다. 모든 Q에 대해 계산하고 (그것을 더하는 대신) 그것 중 가장 큰 것을 취함 이런 낱낱 방법은 계산 폭발 동적 프로그래밍을 이용하자.

44 디코딩 Viterbi 알고리즘 전방 계산 (τ는 매 단계에서 최적 경로 기록) 최적 경로 역추적

45 디코딩 Viterbi 알고리즘 가상 코드로 쓰면, 시간 복잡도는Θ(N2T)

46 디코딩 예제 7.7 Viterbi 알고리즘에 의한 디코딩 t=1일때 t=2일때 t=3과 4일때 역추적하면 답은

47 학습 학습 문제란? 학습의 목적을 적어보면, 관측 벡터O가 주어져 있을때 HMM의 매개 변수 Θ는?
평가와 디코딩의 반대 작업 평가와 디코딩 같은 분석적 방법 없음 수치적 방법 필요 학습의 목적을 적어보면,

48 학습 학습 알고리즘 스케치 반복적 개선

49 학습 가진 것과 찾아야 하는 것 Baum-Welch 알고리즘의 골격 가진 것 O, 찾아야 하는 것 Θ=(A,B,π)
은닉 변수latent variable 등장 가우시언 혼합 추정과 유사성 있음 Baum-Welch 알고리즘의 골격

50 학습 E 단계 ( 의 추정) 는 시간 t에서 상태 si에 있을 확률 는 시간 t에 si, t+1에 sj에 있을 확률
를 구하는데 필요한 α와 β는

51 학습 M 단계 (Θ의 추정) E 단계에서 구한 로 Θnew의 재추정reestimation
P(O|Θnew)>P(O|Θ)이어야 함. 즉 Θnew는 Θ보다 O를 ‘잘 설명해야’ 함

52 학습 Baum-Welch 알고리즘 특성 어고딕과 좌우 모델 초기화는 어떻게? 멈춤 조건은 어떻게? 수렴한다.
욕심 알고리즘이므로 전역 최적점 보장 못한다. 어고딕과 좌우 모델 크기 문제 (어고딕 모델) 다중 관측 학습 (좌우 모델)

53 부연 설명 HMM의 출력은 확률. 큰 장점이다. 샘플 생성 능력이 있다. HMM은 생성generative 모델이다.

54 부연 설명 HMM을 예측 목적으로 사용할 수 있다. HMM을 분류기로 사용할 수 있다. 적절한 아키텍처를 선택해야 한다.
(7.30)으로 분류 적절한 아키텍처를 선택해야 한다. 그녀의 삶은 어떤 모델? 음성 인식은 어떤 모델? 상태의 개수를 적절히 해야 한다. 훌륭한 공개 소프트웨어가 있다. 캠브리지 대학의 HTK (HMM Toolkit)