3 장. 확률 분포 추정 오일석, 패턴인식, 교보문고, 2008..

Presentation on theme: "3 장. 확률 분포 추정 오일석, 패턴인식, 교보문고, 2008.."— Presentation transcript:

1 3 장. 확률 분포 추정 오일석, 패턴인식, 교보문고, 2008.

2 베이시언 분류에서의 학습은 사전 확률과 우도의 추정
들어가는 말 베이시언 분류에서의 학습은 사전 확률과 우도의 추정

3 들어가는 말 사전 확률 P(ωi)의 추정 우도 P(x|ωi) 추정 N은 X의 크기이고 Ni는 ωi에 속하는 샘플 수

4 3.1 히스토그램 히스토그램 총 sd개의 빈이 발생 (각 차원을 s 개 구간으로 나눈다 했을 때) 전형적인 차원의 저주
N은 충분히 크고 d는 작아야 함

5 3.2 최대 우도 문제 정의 “주어진X를 발생시켰을 가능성이 가장 높은 매개 변수 Θ를 찾아라.”
아래 예에서 P(X| Θ1)>P(X| Θ2) 최대 우도를 갖는 Θ는?

6 3.2 최대 우도 최대 우도ML 방법 로그 우도로 바꾸면 아래 최적화 문제를 풀어 답을 구하는 방법
미분을 이용한 최적화 문제 풀이 L(Θ)의 도함수를 0으로 두고 풀어 구한 답이

7 3.2 최대 우도 예제 3.1: 정규 분포를 위한 최대 우도 ML에 의한 평균 벡터 μ의 추정 (공분산 행렬은 안다고 가정)

8 3.2 최대 우도 MAP 방법 P(Θ)가 균일하지 않은 경우

9

10 3.3 비모수적 방법 확률 분포 추정 방법 모수적 방법 확률 분포가 매개 변수 (모수)로 표현되는 형태 ML,MAP 방법등
확률 분포가 임의의 형태 파젠 창, k-최근접 이웃 추정 방법 등

11 히스토그램 방법을 확장하여 확률 밀도 함수pdf 추정
3.3.1 파젠 창 히스토그램 방법을 확장하여 확률 밀도 함수pdf 추정 그림 3.6에서 임의의 점 x에서 확률 값 추정 크기 h인 창을 씌우고 그 안의 샘플의 개수를 k라 하면, d 차원으로 확대하면,

12 3.3.1 파젠 창 여전히 매끄럽지 않은 함수 매끄러운 pdf 커널 함수
예를 들어 그림 3.6(a)에서 x를 오른쪽 옮기면 계속 두 개이다가 어느 순간에 3으로 바뀜. 따라서 불연속인 pdf 매끄러운 pdf 창 안의 샘플에 가중치를 준다. (중앙에 가까운 샘플이 더 높은 가중치) 어떻게 이러한 아이디어를 구현할까? 커널 함수

13 3.3.1 파젠 창 커널 함수를 사용하여 수식을 다시 쓰면, 파젠 창의 특성
커널 함수로 가우시언을 채택하면 매끄러운 pdf를 얻게 된다. 파젠 창의 특성 차원의 저주에서 자유로운가? 추정한 pdf가 실제에 가까우려면 N과 h는 어떻게 되어야 하나?

14 3.3.2 k-최근접 이웃 추정 k-최근접 이웃 추정 x를 중심으로 창을 씌우고 k 개 샘플이 안에 들어올 때까지 확장하고 그 순간의 창의 크기를 h라 한다. 즉 k가 고정되고 h가 가변이다. 파젠 창에서는 h가 고정되고 k가 가변이다. 시간 복잡도: Θ(kdN) 보로노이 도형으로 복잡도 줄일 수 있음

15 3.3.3 k-최근접 이웃 분류기 k-NN 분류기 확률 분포 추정이 아니라 분류기인데, k-NN 추정과 동작이 흡사하여 여기에서 설명함 x를 중심으로 창을 씌우고, k 개 샘플이 안에 들어올 때까지 확장. 이때의 창의 크기를 hx라 하면 창의 부피는 hxd 창 안의 샘플 중에 ωi에 속하는 것의 개수를 ki라 하면,

16 3.3.3 k-최근접 이웃 분류기 베이스 정리를 적용하면 k-NN 분류기

17 3.3.3 k-최근접 이웃 분류기 k-NN 분류기의 오류율 특성

18 두 개 이상의 서로 다른 확률 분포의 혼합으로 X를 모델링함
3.4 혼합 모델 두 개 이상의 서로 다른 확률 분포의 혼합으로 X를 모델링함 보통 요소 확률 분포로는 가우시언을 사용함

19 3.4.1 가우시언 혼합 다양한 분포들 어떻게 다중 모드 분포를 정확히 모델링 할 수 있을까?

20 가우시언 혼합Gaussian mixture
3.4.1 가우시언 혼합 가우시언 혼합Gaussian mixture 추정해야 할 매개 변수

21 3.4.1 가우시언 혼합 최적화 문제로 공식화 해 보자. 가우시언 혼합의 일반 공식
πk는 혼합 계수, N(x|μk, Σk)는 요소 분포 주어진 것과 추정해야 할 것

22 3.4.1 가우시언 혼합 최대 우도 문제로 공식화 Θ에 대한 x의 우도와 로그 우도
이 최적화 문제를 어떻게 풀 것인가?

23

24 3.4.2 EM 알고리즘 문제에 대한 통찰 (예제 3.1과의 비교)
예제 3.1은 한 쌍의 μ와 Σ를 추정  미분 한번 적용으로 해결 지금은 K 개의 μ와 Σ 그리고 그들의 혼합을 위한 혼합 계수 π를 추정 게다가 샘플이 어느 가우시언에 속하는지에 정보가 없음 (손실 정보)

25 3.4.2 EM 알고리즘 새로운 알고리즘 두 단계를 반복 샘플이 어느 가우시언에 속하는지 결정 (연성 소속soft membership) 매개 변수 추정

26 3.4.2 EM 알고리즘 EM 알고리즘의 구체화 샘플의 가우시언 소속을 어떻게 표현할 것인가?
z=(z1, z2,…, zK)T로 표현 (이런 종류의 변수를 은닉 변수라latent variable 부름) 샘플이 j 번째 가우시언에서 발생했다면 zj=1이고 나머지는 0 j 번째 가우시언에서 샘플 xi가 발생할 확률 (‘우도’로 간주할 수 있음) 샘플 xi가 관찰되었는데 그것이 j 번째 가우시언에서 발생했을 확률 (‘사후 확률’로 간주할 수 있음)

27 3.4.2 EM 알고리즘 EM 알고리즘의 구체화 (3.23)의 최적화 문제를 풀기 위해, (3.22)의 ln P(X|Θ)을 미분하여 얻은 도함수를 0으로 두고 그것의 해를 구한다. 먼저 μj에 대해 풀면, Nj는 ‘j 번째 가우시언에 소속된’ 샘플의 개수로 해석할 수 있음 μj는 j 번째 가우시언에 소속된 샘플의 가중치 평균으로 해석

28 3.4.2 EM 알고리즘 EM 알고리즘의 구체화 Σj에 대해 풀면,
Σj는 j 번째 가우시언에 소속된 샘플의 가중치 공분산 행렬로 해석 가능 혼합 계수 πj에 대해 풀면, 조건부 최적화 문제이므로 라그랑제 승수를 도입하여 해결

29 3.4.2 EM 알고리즘

30 3.4.2 EM 알고리즘 EM 알고리즘에 대한 부연 설명 군집화를 위한 k-means 알고리즘은 EM의 일종이다.
멈춤 조건은? EM은 최적 해로 수렴함 (욕심 알고리즘이므로 전역 최적 해 보장 못함) EM은 불완전 데이터에 대한 최대 우도 추정법으로 간주할 수 있다.