Maximum Entropy Model

Maximum Entropy Model ( = Maxent Model )

 

* c = class, d = document

 

1. Joint, Generative Model : P(c,d)

이 class에 해당하면 어떤 document를 생성하는가?

(ex) N-gram, Naive Bayes 

 

 

2. Conditional, Discriminative Model : P( c | d )

이 document면 어떤 class에 속할까? 

(ex) Logistic Regression, Maximum Entropy Model 

 

 

Feature의 예시

첫 번째 feature = class가 LOCATION이고 target 직전 단어가 in이며 target 단어가 대문자로 쓰이면 1, 아니면 0 (binary)

feature가 반환하는 binary 값과 weight (lambda)가 곱해짐

 

 

Empirical Count (실제 데이터에서 특정 feature가 해당 class에 나타난 빈도)

 

 

Model Expectation 

 

 

Feature-Based Linear Classifier

각 feature * weight 의 값이 가장 큰 class 선택

 

 

Exponential Model

조건부 확률을 최대화 하는 weight(lambda) 값 찾기 

 

한 document가 특정 class일 때의 vote / (한 document가 class_1일 때의 vote + class_2일 때의 vote + ... + class_n일 때의 vote)

 

Naive Bayes vs Maxent Model

Naive Bayes 성능이 안 좋은 이유 : 각 feature가 독립적이라 가정한다. 그래서 독립적이지 않은 feature를 double count하게 된다

Maxent Model은 feature에 weight를 주기 때문에 double count 된다고 해도 weight 나눠 가져서 성능 좋음 

 

Maxent Model 

 

이 log 값을 최대로 만드는 parameter (lambda) 를 찾아야 함. 

 

* log 사용 이유 

① 곱셈 계산 빨리하기 ② convexity (not 울퉁불퉁 → global min/max 찾을 수 있어서 경사하강법 사용 가능)

 

Gradient Descent를 쓰기 위해 미분하면 분자는 empirical count, 분모는 model prediction이 됨

∴ 미분 값 = (empirical count) - (model prediction) 

 

이 미분 값이 0이어야 원래 수식이 최대값을 가짐. 

∴ (empirical count) = (model prediction) 여야 한다. 

 

1) 우선 모든 feature가 동일한 확률은 갖는다고 가정하기 (uniform distribution)  ∴ entropy가 최대인 상태

* uniform distribution을 가정하기 때문에 over-fitting 방지 가능

2) 실제 데이터 참고하면서 feature (constraints) 추가하기. 이때도 feature 내에선 uniform distribution 가정. 

→ feature(constraints) 추가하며 entropy 낮춰가기 ( = 확률은 높아져감)

 

 

(예제)

주어진 실제 데이터 

 

NN	NNS	NNP	NNPS	VBZ	VBD
3	5	11	13	3	1

 

Maxent Model 적용하기

 

1) 우선 모두 같은 확률이라 가정

 

NN	NNS	NNP	NNPS	VBZ	VBD
1/6	1/6	1/6	1/6	1/6	1/6

 

2) N으로 시작하는 것이 V로 시작하는 것보다 많다. N에 좀 더 높은 확률 배정해주되, N 안에서는 확률이 모두 같아야 한다

 

NN	NNS	NNP	NNPS	VBZ	VBD
8/(32+4)	8/(32+4)	8/(32+4)	8/(32+4)	2/(32+4)	2/(32+4)

* N의 빈도 = 3+5+11+13 = 32 ∴ N들의 확률 총 합은 32/(32+4). 그런데 uniform distribution이므로 이 확률을 4로 나눔. (N 종류가 4개니까)

* V의 빈도 = 3+1 = 4 ∴ V들의 확률 총 합은 4/(32+4). 그런데 uniform distribution이므로 이 확률을 2로 나눔. (V 종류가 2개니까)

 

3) N 중에 P 들어가는 것들이 안 들어가는 것보다 더 많다. NP에 좀 더 높은 확률 배정해주되, NP 안에서는 확률이 모두 같아야 한다

 

NN	NNS	NNP	NNPS	VBZ	VBD
4/(32+4)	4/(32+4)	12/(32+4)	12/(32+4)	2/(32+4)	2/(32+4)

* NN의 빈도 = 3+5=8 ∴ NN들의 확률 총 합은 8/(32+4). 그런데 uniform distribution이므로 이 확률을 2로 나눔. (NN종류가 2개니까)

* NP의 빈도 = 11+13=24 ∴ NP들의 확률 총 합은 24/(32+4). 그런데 uniform distribution이므로 이 확률을 2로 나눔. (NP종류가 2개니까)

 

 

출처 : http://ling.snu.ac.kr/class/AI_Agent/lecture/03-3-Maximum_Entropy_Classifiers_All_new.pdf