[statistics] Naive Bayesian, HMM, Maximum Entropy Model, CRF
Classical Probabilistic Models and Conditional Random Fields
자료를 읽어보면, 네가지 모델의 차이점을 명확히 알 수 있을 것이다.
기본적으로 결합확률은 아래와 같이 풀어쓸수 있다.
p(y, X) = p(y) * p( X | y) = p(y) * product { p(x(i) | x(i-1), x(i-2), ..., x(1), y) } where i = 2 ~ m
( X는 확률변수 x들의 vector로 쓰자)
product { . } 부분을 계산하는 것은 매우 힘들기 때문에, Naive Bayesian에서는 모든 확률변수 x들은 서로 독립적이라고 가정한다. 그러면, p(y, x)는 위 (4) 수식과 같이 단순해진다. 이러한 단순화(independency assumption)은 real world를 완전히 모델링하지는 못하지만 approximation이므로 여러 응용에서 사용되고 있다.
스팸 문서와 햄 문서를 Naive Bayesian으로 구분하려고 하는 경우, 확률변수 x에 해당하는 것은 단어 그 자체이며(x = { 0, 1 }) x들 사이는 독립적이라고 가정했으므로, x(i)와 x(j) 사이의 dependency를 잡아내기는 힘들다. y는 single variable이며 p(y, X)를 이용해서 p(y | X)를 계산하므로
predict single class by using joint probability
Naive Bayesian 모델의 learning은 결국 class 확률 p(y)과 feature 확률 p(x(i) | y)을 학습데이터로부터 계산하는 것인데, Maximum Likelihood Estimation 방법을 사용하게 된다. Inference는 주어진 feature vector X에 대해서 p(y, X)를 계산해서 가장 큰 p(y, X)에 해당하는 y의 값을 해당하는 class로 결정하게 된다.
Hidden Markov Model
Naive Bayesian에서는 한개의 output variable y에 대해서만 고려했는데, y가 한개가 아닌 sequence Y가 될 경우를 생각해보자. (Y는 확률변수 y들의 vector로 쓰자) 이런 경우는 Naive Bayesian production으로 p(X, Y)를 계산할 수 있을 것이다.
p(X, Y) = product { p(y(i) * p(x(i) | y(i))) } where i = 1 ~ n
즉, 각각의 포지션 i에 해당하는 observation x(i)는 오직 y(i)로부터만 생성된다. 그런데, 이러한 가정은 Naive Bayesian의 무리한 가정을 그대로 사용하는 것이므로 좀더 그럴듯한 가정인 'y(i)는 y(i+1)과 dependency가 있다'를 추가해 볼 수 있을 것이다. 이것이 바로 잘 알려진 수식 (7)번, HMM 모델이다.
HMM은 Naive Bayesian의 확장이므로 결국
predict sequence of class by using joint probability
또한, HMM도 Naive Bayesian의 단점(independency assumption)을 그대로 가지고 있다고 봐도 된다. HMM의 learning과 inference는 이 문서를 보면 된다.
Naive Bayesian과 HMM은 학습데이터로부터 joint likelihood를 최대화시키는 방향으로 학습되게 되는데, (conditional) Maximum Entropy Model은 joint probability를 계산하지 않고 conditional probability를 사용한다.(ME가 conditional에서만 사용되는 개념은 아니다)
기본적인 아이디어는 학습데이터로부터 가장 적합한 conditional probability p(y | x)는 conditional entropy H(y | x)가 최대화될 경우에 얻어진다는 것이다.( conditional entropy는 이 문서를 참고) 이것은 'Principle of Maximum Entropy'로 부터 도출 되었는데, 간단히 설명하자면, 잘 모르는 확률값은 uniform하다고 가정하는 것이 가장 unbiased된 assumption이라는 것이다.
수식 (8)을 보면 (x, y) 쌍이 속하는 집합 Z는 학습데이터만을 의미하는 것이 아니라 모든 가능한 (x, y) 쌍의 집합이며, 수식 (9)의 집합 P는 '학습데이터에 consistent한' 모든 모델 p(y | x)들을 의미한다. 여기서 '학습데이터에 consistent한'의 의미는 이어지는 전개 과정을 보면 이해가 될 것이다.
결국, 가장 그럴듯한 모델 p*(y | x)는 수식 (9)에 의해서 계산될 수 있는데, 이것을 보통 primal problem이라고 부른다. (constraint optimization theory에서는 풀어야할 문제를 primal problem이라고 하고, 이것을 직접 계산할 수 없기 때문에 특정 제약조건을 줘서 해를 구하는 방식을 사용한다)
수식 (9)를 그대로 풀 수 없으므로, constraint를 넣어보자. 그러기 전에 우선 학습데이터를 feature function으로 표현해야 하는데, feature function은 아래와 같이 정의된다.
주목할 부분은 feature function은 input variable x뿐만 아니라 class variable y와도 관계가 있도록 설정한다는 것이다. 스팸 문서 분류 문제에서 어떤 단어 word에 관계된 feature function은 스팸문서와 햄문서에 동일하게 적용되어야하며
fi(x, y) = 1 if y='스팸' and x='word'
0 otherwise
어떤 학습데이터 (x, y)에 대해서 feature function fi(.)를 적용하면 그 값은 1이거나 0이 될 것이다. 이러한 feature function을 정의하는 이유는 primal problem을 풀기 위해서는 constraint가 필요한데, "어떤 feature function fi(.)를 모든 학습 데이터 (x, y) 쌍에 대해 적용한 결과의 기대값(expectation)은 학습데이터를 포함한 전체 데이터 (x, y) 쌍에 대해 적용한 결과의 기대값과 같다"는 constraint를 사용하기 위함이다.
우선 학습데이터에서의 feature function expectation을 계산해보자. 일단 모든 (x, y) 쌍을 고려한 수식 (11)과 같이 쓸수 있는데, 이것을 학습데이터에 등장하는 (x, y) 쌍의 집합 T로 한정하면 수식 (12)가 된다. ( p~(x, y)는 empirical joint distribution이라고 한다)
또한 학습데이터 (x, y) 쌍의 집합 T를 포함한 전체 집합 Z에 대한 feature function expectation을 계산해보자. 이것은 수식 (14)로 쓸 수 있는데, 여기서 p(x, y)는 model joint distribution인데, 정확히 계산하기 어렵기 때문에 수식 (15)와 같이 p(x)를 p~(x)로 바꿔서 approximation한다. (사실 x가 취할 수 있는 값을 알기 어렵기 때문이다. 그리고 y는 일반적으로 매우 작은 수의 class값을 가지므로 수식 (16)을 학습데이터로부터 계산(marginal probability)하는 것은 어렵지 않다.)
학습데이터 T에 나타나는 어떤 x에 대한 확률 p~(x)는 0이거나 1이다. 따라서 수식 (15)는 수식 (16)으로 바꿔 쓸 수 있다. 수식 (12)와 (16)은 매우 비슷해보인다. 이제 다시 우리는 constraint를 아래와 같이 추가할 수 있다.
첫번째는 앞서 언급한것과 같이 empirical distribution에서 어떤 feature function fi(.)의 기대값과 model distribution에서의 기대값이 같아야 한다는 것이고( 수식 (17) ) 두번째는 당연하겠지만, p(y | x)는 항상 0보다 같거나 크며, 모든 y에 대한 p(y | x)의 합은 1이라는 것이다.(수식 (18) )
이제 primal problem인 수식 (9)에 constraint인 수식 (17), (18)을 추가해서 constraint optimization problem을 풀어보자.
일반적으로 constraint optimization problem은 Lagrange Multiplier를 이용해서 Lagrange function을 만들어 푸는데, feature function이 m개 있다고 하면 위 수식 (19)와 같이 쓸 수 있다. 우리가 원하는 것은 이 수식 (19)를 최대화시키는 p*(y | x)를 찾는 것이며, 이를 위해서 수식 (19)를 p(y | x)로 편미분하면 아래 수식 (28)이 유도 될 수 있다.
이에 대한 자세한 유도 과정은 아래와 같다.
우선 수식 (15)에서 p(x)를 모르기 때문에, empirical distribution p~(x)를 사용해서 approximation한 것과 똑같이 H(y | x)에 대해서도 적용한다. 그리고나서, H(y | x)를 p(y | x)로 편미분해보자. ( 이 결과를 수식 (19)를 p(y | x)로 편미분할때, 사용한다)
'a * log(a)'를 a로 미분하면 'log(a) + a*(1/a)'이므로 'p(y | x) * log p(y | x)를 p(y | x)'로 미분하면 'log p(y | x) + p(y | x) * ( 1 / p(y | x) )'가 된다. 그래서 위와 같은 수식 (21)이 나오게 된다.
그리고 'sum { a } for all a', 이것을 a에 대해 미분하면 1이 된다는 것은 기본적으로 알고 가자. 일반적으로 'b = a' 그래프에서 변역 (a)가 이산변수인 경우 'b = sum { a } for all a'와 같이 표현되는데 이것을 변역 (a)에 대해 미분하는 것은 기본적으로 연속변수의 미분과 같은 개념이다.
다음으로 수식 (19)의 우항에서 가운데 해당하는(constraint from equation (17)) 컴포넌트를 미분해보자.
이 미분은 간단하게 위 수식 (22)와 같다. (여기서 E~(fi)에 대한 미분을 할때 수식 (11)대신 수식 (12)를 사용한 이유는 변역 (x,y)를 일치시키기 위함이다) 이제 수식 (21), (22)를 가지고 수식 (19)를 다시 쓰고 좌변을 0으로 놓고 문제를 풀면
ME 모델이 log-linear 모델을 사용하다는 것이 바로 이 수식 유도과정에서 나온다. 그리고 수식 (24)를 수식 (18)에 대입해보면 수식 (26)이 된다.
다시 수식 (26)을 (24)에 대입해서 정리하자. 그리면 결국 수식 (27)이 유도된다. (27)의 분모는 사실 모든 가능한 y에 대한 분자의 summation이므로 결과적으로 앞서 언급된 수식 (28)이 될 것이다.
수식 (28)에서 :
- 분자의 경우
- 특정 (x, y)에 대해서 feature function과 해당 feature function의 weight를 알면 계산할 수 있다.
- 분모의 경우
- 모든 y에 대해서 전부 계산해야한다.
- 이러한 모델을 log-linear 모델이라고 한다.
Maximum Entropy Model은 p(y | x)를 이용하기 때문에, discriminative model이라고 부른다.
predict single class by using conditional probability
m개의 Lagrange multiplier(즉, lambda vector)를 training하는 방법은 생략하겠다. 학습만 되면 inference는 매우 간단하게 적용될 수 있다.
CRF에 대해서는
flexCRFs 매뉴얼에 기술된 CRF 설명, 혹은 이 튜토리얼로 대신하자.