ME(Maximum Entropy, 이하 ME)는 이종의 정보를 분류하기 위한 일종의 프레임웍이다.
일반적으로 미리 정의된 제한조건(constraint)를 만족하고 그 이외의 값은 동일하게 하는 확률 모델이다.
ME를 하기 위해서 우선 자질을 선택해야 하고, 다음으로 가중치 변수의 값을 추정해야 한다.
자질선택을 보면 문서분류의 경우는 일반적으로 0,1값을 출력하는 이진 함수로 표현할 수 있다.
어떤 문서가 어떤 클래스에 속하는지 또는 속하지 않는지를 0,1값으로 표현하면 이것이 자질 함수가 되겠다.
보통 기대값은 다음과 같이 계산한다.
주사위가 있고 주사위 각 면이 나올 확률은 모두 1/6이라고 할때
주사위의 기대값은
E(Y) = 1/6 ∑Y
가된다.
Y값은 1 ~ 6이 되고
결과적으로 E(Y) = 1/6 ( 1 + 2 + 3 + 4 + 5 + 6 ) = 21/6 이 된다.
따라서 주사위 Y의 기대값 E(Y) = 21/6이다.
문서D에 대해 자질f의 경험적 확률 분포P(d,c)의 기대값을 정의하면
Ep~(f) = ∑ P~(d,c)* f(d,c)
f(d,c) 는
d가 c이면 1
아니면 0을 리턴하는 함수이다.
P(d,c) = Count(d,c)/Count(d)
Count(d,c)는 문서 d가 c인 문서수이고
Count(d)는 전체 문서수이다.
확률 분포 P(d,c)에 대한 f의 기대값은
Ep(f) = ∑ P(d,c)* f(d,c) 가 된다.
그리고 Ep(F) = Ep~(F)
하지만 Ep(f) = ∑ P(d,c)* f(d,c)에서 P(d,c)는 구할수 없기 때문에 근사적 기대값으로
Ep(f) = ∑ P(d,c)* f(d,c) == ∑ P~(d)P(c|d) f(d,c) 가 된다.( 문서도 무한하고 클래스 역시 무한하다 )
최대 엔트로피 원리에 의해 확률분포 중 최선의 확률 분포는
P* = argmax H(p)
주어진 제약조건을 만족하는 제한적 최적화문제인데 이를 라그랑제 승수를 적용하여
비제한적 최적화 문제로 변형하여 풀수 있다.
다시 말하면 조건부 확률 분포를 지수 또는 로그 선형 확률 분포로 변형하여 풀수 있다.
----------------------------------------------------------------------------------------------
Foundations of Statistical Natural Language Processing
----------------------------------------------------------------------------------------------
원본 문서
BASE DATA
-----------------------------------------------------------------------------------------------------------------------------
Word wj Term weight Sij Classification
-----------------------------------------------------------------------------------------------------------------------------
|
vs |
5 |
1 |
|
mln |
5 |
1 |
|
cts |
3 |
1 |
|
; |
3 |
1 |
|
& |
3 |
1 |
|
000 |
4 |
1 |
|
loss |
0 |
1 |
|
, |
0 |
1 |
|
" |
0 |
1 |
|
3 |
4 |
1 |
|
profit |
0 |
1 |
|
dlrs |
3 |
1 |
|
1 |
2 |
1 |
|
pct |
0 |
1 |
|
is |
0 |
1 |
|
s |
0 |
1 |
|
that |
0 |
1 |
|
net |
3 |
1 |
|
lt |
2 |
1 |
|
at |
0 |
1 |
위 테이블을 보면
워드가 총 20개이다. 따라서 문서 x는 기본적으로 feature가 20차원인 벡터로 생각할수 있다. X = { vs, mln, .... }
features fi는 (x,c)의 속성을 특징지을때 사용하는 이진 함수고 F(xj,c) 는 다음과 같다
1. 만약 Sij가 0이상이고 클래스가 1이면 return 1
2. 아니면 return 0
K : feature의 수, α : feature Fi의 가중치 Z : 정규화 상수
위 수식 양변에 LOG를 취하면
과 같다.
Generalized iterative scaling은 아래의 제한된 상황에서 최대 엔트로피 분포 
다른말로 하면,
알고리즘은 상수 C와 동일한 각각의 가능한 (X,C)의 feature의 합이 필요하다. 이 요구조건을 만족하기 위해서 feature의 sum의 최대값을 C로 정의한다.
이책에서는 feature함수를 1개만 쓰고 있기 때문에 F1(X,C) = 1이 된다.
따라서 Fk+1은 다음과 같이 구할수 있다.
K2(X,C) = 1 - F1(X,C)
이 함수는 바이너리 함수는 아니다.( 이책의 예제에서는 바이너리로 동작하겠네 )
여기서 합계는 모든 이벤트 공간을 의미한다. 즉, 가능한 벡터 X와 클래스 레이블 C를 의미한다. 경험적 기대값은 아래의 식으로 쉽게 계산이 가능하다.
N은 학습데이터의 전체 원소 수이고, 학습데이터에서 나타나지 않는 쌍에 대한 경험적 확률은 0으로 설정하여 사용한다.
일반적으로 최대 엔트로피 분포 EpFi는 효과적으로 계산이 어려운데, X와 C에 대한 모든 가능한 조합을 계산하기가 불가능하기 때문이다.
대신 근사값으로 이를 해결할수 있다.
여기서 c가 가질수 있는 값은 0,1과 이다.
GIS를 설명하면
1. 우선 알파값을 모두 1로 설정하고 EpFi를 계산한다.
2. 학습문서에서 각각의 요소 (X,C)에 대한 알파값으로 주어진 분포 Pn으로 P(n) P(n)(X,C)를 계산한다.
3. Ep(n)fi를 16.10식으로 계산한다( i는 1부터 k+1까지 )
4. 알파값을 없데이트한다.
5. 파라미터가 수렴하면 멈추고, 그렇지 않으면 다시 2단계로 넘어간ㄷ
참고 : http://www.ai.mit.edu/courses/6.891-nlp/l6.pdf
참고 : http://register.itfind.or.kr/Report01/200302/IITA/IITA-2380-230/IITA-2380-230.pdf
LOG LINEAR MODEL : http://www.cs.cmu.edu/~nasmith/papers/smith.tut04.pdf
GIS : 일반적으로 Maximum Entropy Approach는 바이너리 데이터에 국한되어 사용하지는 않지만 여기서 소개하는 GIS는 오직 바이너리 데이터에 대해서만 동작한다.
'알고리즘' 카테고리의 다른 글
| Animation of Lempel-Ziv Encoding Algorithm (0) | 2010.09.28 |
|---|---|
| 라그랑제 승수 ( Lagrange multipliers ) (0) | 2009.09.11 |
| LINGO Algorithm (0) | 2009.08.25 |
| Probabilistic Semantic Latent Analysis (0) | 2009.06.25 |
| FP-TREE( Frequent Pattern Tree ) (0) | 2009.06.02 |