Conditional Random Fields
10 Nov 2017 | CRF
이번 글에서는 Conditional Random Fields에 대해 살펴보도록 하겠습니다. 이 글은 고려대 정순영 교수님 강의를 정리했음을 먼저 밝힙니다. 이밖에 다양한 자료를 참고하였는데요, 인용한 부분에 표시를 해 두었습니다. 비터비 알고리즘 관련 설명 그림은 제가 직접 그렸습니다. 제가 잘못 이해하고 있거나 미진한 점 있으시면 언제든 댓글로 알려주시면 바로 반영하겠습니다. 그럼 시작하겠습니다.
overview
CRF를 설명하는 데 있어 가장 유명한 그림 아닐까 싶습니다. 다음과 같습니다.
CRF, MEMM, HMM과의 차이점은 다음과 같습니다. 간결하고 직관적인 설명이어서 직접 인용을 해봤습니다. (출처 : Quora)
CRFs and MEMMS are discriminative sequence models whereas HMMs are generative sequence models. HMM essentially uses Bayes Rule as a local model over the transition and emission probabilities, whereas CRF and MEMM’s local models are MaxEnt models over transition and observable features. The chief difference between MEMM and CRF is that MEMM is locally renormalized and suffers from the label bias problem, while CRFs are globally renormalized.
CRF가 강점을 지니는 이유는 구성하기에 따라서 얼마든지 HMM 같은 구조로 바꿀 수 있다는 점입니다. 아래 그림과 같습니다. (출처 : C Sutton, “An Introduction to CRF”)
For example, in an HMM, a transition from state $i$ to state $j$ receives the same score, log $p(y_t = j$|$y_{t−1} = i)$, regardless of the input. In a CRF, we can allow the score of the transition $(i, j)$ to depend on the current observation vector, simply by adding a feature $1{y_t=j}$, $1{y_{t−1}=1}$, $1_{x_t=o}$.
CRF는 본질적으로 시퀀스 분류기이기 때문에 최근 주목받고 있는 Recurrent Neural Network와도 직, 간접적으로 연관을 맺고 있는 것 같습니다. 이와 관련한 설명 또한 인용해봤습니다. (출처 : Quora)
RNNs have a latent state that is never observed (e.g. the memory in a LSTM). In contrast, the CRF has a latent state that is observed for training data (the model has to learn how to recreate those latent states for test data). Both are similar in that there is a set of parameters that tell you how to evolve the latent state from one time step to the next.
수식과 파이썬 구현
CRF의 수식을 살펴보겠습니다. 수식만 살펴봐서는 되레 복잡하므로, 파이썬 코드와 함께 살펴보겠습니다. 파이썬 코드는 이곳을 참고해 대폭 손질하였습니다. (수식 이해를 돕기 위한 코드로 대단히 느립니다, 혹시 학습 용도로 필요하시다면 라이브러리 활용을 추천해 드립니다)
기본 구조
CRF를 그래피컬하게 나타낸 그림은 다음과 같습니다. 입력벡터 $x$의 위치에 상관없이 모두 활용하기 때문에 매우 유연한 구조입니다.
입력 시퀀스(예컨대 단어들) 벡터 $x$가 주어졌을 때 레이블 시퀀스(예컨대 품사) 벡터 $y$가 나타날 확률은 다음과 같이 정의됩니다. 최대엔트로피모델(로지스틱 회귀)와 완전히 같습니다만, 최대엔트로피가 single observation을 분류하는 모델이라면, CRF는 sequential classifer라는 점이 다릅니다.
[{ p }_{ \overrightarrow { \lambda } }\left( \overrightarrow { y }
\overrightarrow { x } \right) =\frac { 1 }{ { Z }{ \overrightarrow { \lambda } }\left( \overrightarrow { x } \right) } \cdot exp\left( \sum _{ j=1 }^{ n }{ \sum _{ i=1 }^{ m }{ { \lambda }{ i }{ f }{ i }\left( { y }{ j-1 },{ y }_{ j },\overrightarrow { x } ,j \right) } } \right)]
위 식을 파이썬 코드로 구현하면 다음과 같습니다.
import math
def calc_prob_y_given_x(y_prime, x, all_labels, FeatureFunction, weights):
n = len(y_prime)
m = len(weights)
nominator = 0
for j in range(1, n):
for i in range(1, m):
nominator += weights[i] * FeatureFunction(y_prime, x, i, j)
denominator = calc_Z(x, n, m, all_labels, FeatureFunction, weights)
return math.exp(nominator) / denominator
Feature Functions
CRF는 최대엔트로피모델이나 최대엔트로피마코프모델처럼 Feature를 연구자가 유연하게 설정할 수 있습니다. 이를 파이썬 코드로 구현한 결과는 다음과 같습니다.
# x : words (observation sequence)
# y : lables (e.g: POS TAGS, label sequence)
def FeatureFunction(x, y, i, j):
# f_1
if i == 1 and y[j-1] == 'NN':
return 1
# f_2
elif i == 2 and y[j-1] == 'VBZ':
return 1
# f_3
elif i == 3 and x[0] == 'DT':
return 1
else:
return 0
Label Bias 문제와 극복 방안
CRF는 Label Bias 문제를 극복하기 위해 제안된 기법입니다. Label Bias란 다음과 같은 문제를 가리킵니다.
- Preference of states with lower number transitions over others
이를 해결하기 위해 확률값을 구할 때 global normalize를 합니다. 이를 구현한 파이썬 코드는 다음과 같습니다.
def calc_Z(x, n, m, all_labels, FeatureFunction, weights):
Z = 0
all_possible_Y = itertools.product(all_labels, repeat=n)
for y_prime in all_possible_Y:
tmpZ = 0
for j in range(1, n):
for i in range(1, m):
tmpZ += weights[i] * FeatureFunction(y_prime, x, i, j)
Z += math.exp(tmpZ)
return Z
그런데 보시다시피 가능한 모든 조합의 레이블 시퀀스에 대한 확률을 구해야 합니다. 가령 품사 종류가 명사(NN), 동사(VB) 등 다섯 가지이고, 시퀀스 길이가 5(개 단어)라면 다음 표처럼 $5^5$=3125가지의 경우의 수를 고려해야 합니다.
$y_1$
$y_2$
$y_3$
$y_4$
$y_5$
NN
NN
NN
NN
NN
NN
NN
NN
NN
VBN
NN
NN
NN
NN
VBZ
NN
NN
NN
NN
IN
NN
NN
NN
NN
DT
NN
NN
NN
VBN
NN
NN
NN
NN
VBN
VBN
NN
NN
NN
VBN
VBZ
NN
NN
NN
VBN
IN
NN
NN
NN
VBN
DT
…
…
…
…
…
CRF에서 가장 계산량이 많은 부분이 바로 $Z$를 구하는 부분입니다. 위 파이썬 코드는 수식 이해 용도로 수식을 그대로 옮겨놓은 형태이지만, 실제로는 다이내믹 프로그래밍(dynamic programming) 등 최적화 기법을 쓴다고 합니다.
파라메터 학습 : 최대우도추정
CRF의 파라메터는 로지스틱 회귀의 파라메터를 추정하는 방식과 같이 최대우도추정법(Maximum Likelihood Estimation)으로 구합니다. 식이 매우 복잡한데, 저 또한 정리 용도로 남겨둡니다. CRF의 로그 우도함수는 다음과 같습니다. 식의 첫 줄 두번째 항은 과적합(overfitting) 방지를 위한 정규화(regularization) 항입니다.
위 로그 우도함수는 파라메터 $λ$로 편미분한 값이 0인 지점에서 최대값을 가집니다. 이를 3등분해서 각각 $λ$에 대해 편미분한 결과는 다음과 같습니다. 우선 $A$를 편미분한 결과입니다.
다음은 $B$를 파라메터 $λ$에 대해 편미분한 결과입니다.
마지막으로 $C$입니다.
$A$는 데이터의 empirical distribution으로 해석할 수 있습니다. 식과 파이썬 코드는 다음과 같습니다.
def calc_empirical_expectation_feature_i(train_data, FeatureFunction, i):
empirical_expectation_feature_i = 0
for x, y in train_data:
n = len(y)
for j in range(1, n):
empirical_expectation_feature_i += FeatureFunction(y, x, i, j)
return empirical_expectation_feature_i
$B$는 모델이 내놓는 distribution으로 해석할 수 있습니다. 식과 파이썬 코드는 다음과 같습니다.
import itertools
def calc_predicted_expectation_feature_i(train_data, FeatureFunction,
all_labels, weights, i):
predicted_expectation = 0
for x, y in train_data:
n = len(y)
all_possible_Y = itertools.product(all_labels, repeat=n)
for y_prime in all_possible_Y:
predicted_expectation += \
(calc_prob_y_given_x(y_prime, x, all_labels, FeatureFunction, weights)
* sum([FeatureFunction(x, y, i, j) for j in range(1, n)]))
print(predicted_expectation)
return predicted_expectation
로그우도 함수에 대한 편미분 식을 다시 적으면 다음과 같은데요. $A$와 $B$가 비슷할 수록 로그우도 함수의 도함수가 작아집니다. 데이터의 분포와 모델의 분포가 비슷할 수록, 즉 모델이 데이터의 분포를 잘 모사할 수록 학습이 잘 되었다는 이야기입니다.
이제 거의 다 왔습니다. 파라메터 $λ$를 랜덤 초기화한 뒤 이제까지 구한 로그우도 함수가 커지는 방향(그래디언트)로 파라메터를 조금씩 업데이트해 주면 됩니다(gradient ascent). 이를 파이썬 코드로 구현한 결과는 다음과 같습니다.
#train data set = {(x, y)}
def get_all_labels(train_data):
available_labels = set()
for x, y in train_data:
available_labels.update(y)
return list(available_labels)
# m = feature vector size
import random
def initial_weights(m):
return [random.random() for _ in range(m)]
def train(train_data, FeatureFunctions, m, iterations=100, learning_rate=0.1):
all_labels = get_all_labels(train_data)
weights = initial_weights(m)
for _ in range(iterations):
for i in range(1, m):
empirical_expectation = \
calc_empirical_expectation_feature_i(train_data, FeatureFunction, i)
predicted_expectation = \
calc_predicted_expectation_feature_i(train_data, FeatureFunction,
all_labels, weights)
weights[i] = weights[i] + \
learning_rate * (empirical_expectation - predicted_expectation)
비터비 알고리즘
시퀀스 분류를 하기 위해 이 먼길을 돌아왔습니다. CRF가 최적 상태열을 inference하는 기법인 비터비 알고리즘은 다음과 같이 동작합니다.
다음 과정입니다.
다음 과정입니다.
마지막으로 backtrace 과정입니다.
이번 글에서는 Conditional Random Fields에 대해 살펴보도록 하겠습니다. 이 글은 고려대 정순영 교수님 강의를 정리했음을 먼저 밝힙니다. 이밖에 다양한 자료를 참고하였는데요, 인용한 부분에 표시를 해 두었습니다. 비터비 알고리즘 관련 설명 그림은 제가 직접 그렸습니다. 제가 잘못 이해하고 있거나 미진한 점 있으시면 언제든 댓글로 알려주시면 바로 반영하겠습니다. 그럼 시작하겠습니다.
overview
CRF를 설명하는 데 있어 가장 유명한 그림 아닐까 싶습니다. 다음과 같습니다.
CRF, MEMM, HMM과의 차이점은 다음과 같습니다. 간결하고 직관적인 설명이어서 직접 인용을 해봤습니다. (출처 : Quora)
CRFs and MEMMS are discriminative sequence models whereas HMMs are generative sequence models. HMM essentially uses Bayes Rule as a local model over the transition and emission probabilities, whereas CRF and MEMM’s local models are MaxEnt models over transition and observable features. The chief difference between MEMM and CRF is that MEMM is locally renormalized and suffers from the label bias problem, while CRFs are globally renormalized.
CRF가 강점을 지니는 이유는 구성하기에 따라서 얼마든지 HMM 같은 구조로 바꿀 수 있다는 점입니다. 아래 그림과 같습니다. (출처 : C Sutton, “An Introduction to CRF”)
For example, in an HMM, a transition from state $i$ to state $j$ receives the same score, log $p(y_t = j$|$y_{t−1} = i)$, regardless of the input. In a CRF, we can allow the score of the transition $(i, j)$ to depend on the current observation vector, simply by adding a feature $1{y_t=j}$, $1{y_{t−1}=1}$, $1_{x_t=o}$.
CRF는 본질적으로 시퀀스 분류기이기 때문에 최근 주목받고 있는 Recurrent Neural Network와도 직, 간접적으로 연관을 맺고 있는 것 같습니다. 이와 관련한 설명 또한 인용해봤습니다. (출처 : Quora)
RNNs have a latent state that is never observed (e.g. the memory in a LSTM). In contrast, the CRF has a latent state that is observed for training data (the model has to learn how to recreate those latent states for test data). Both are similar in that there is a set of parameters that tell you how to evolve the latent state from one time step to the next.
수식과 파이썬 구현
CRF의 수식을 살펴보겠습니다. 수식만 살펴봐서는 되레 복잡하므로, 파이썬 코드와 함께 살펴보겠습니다. 파이썬 코드는 이곳을 참고해 대폭 손질하였습니다. (수식 이해를 돕기 위한 코드로 대단히 느립니다, 혹시 학습 용도로 필요하시다면 라이브러리 활용을 추천해 드립니다)
기본 구조
CRF를 그래피컬하게 나타낸 그림은 다음과 같습니다. 입력벡터 $x$의 위치에 상관없이 모두 활용하기 때문에 매우 유연한 구조입니다.
입력 시퀀스(예컨대 단어들) 벡터 $x$가 주어졌을 때 레이블 시퀀스(예컨대 품사) 벡터 $y$가 나타날 확률은 다음과 같이 정의됩니다. 최대엔트로피모델(로지스틱 회귀)와 완전히 같습니다만, 최대엔트로피가 single observation을 분류하는 모델이라면, CRF는 sequential classifer라는 점이 다릅니다.
| [{ p }_{ \overrightarrow { \lambda } }\left( \overrightarrow { y } | \overrightarrow { x } \right) =\frac { 1 }{ { Z }{ \overrightarrow { \lambda } }\left( \overrightarrow { x } \right) } \cdot exp\left( \sum _{ j=1 }^{ n }{ \sum _{ i=1 }^{ m }{ { \lambda }{ i }{ f }{ i }\left( { y }{ j-1 },{ y }_{ j },\overrightarrow { x } ,j \right) } } \right)] |
위 식을 파이썬 코드로 구현하면 다음과 같습니다.
import math
def calc_prob_y_given_x(y_prime, x, all_labels, FeatureFunction, weights):
n = len(y_prime)
m = len(weights)
nominator = 0
for j in range(1, n):
for i in range(1, m):
nominator += weights[i] * FeatureFunction(y_prime, x, i, j)
denominator = calc_Z(x, n, m, all_labels, FeatureFunction, weights)
return math.exp(nominator) / denominator
Feature Functions
CRF는 최대엔트로피모델이나 최대엔트로피마코프모델처럼 Feature를 연구자가 유연하게 설정할 수 있습니다. 이를 파이썬 코드로 구현한 결과는 다음과 같습니다.
# x : words (observation sequence)
# y : lables (e.g: POS TAGS, label sequence)
def FeatureFunction(x, y, i, j):
# f_1
if i == 1 and y[j-1] == 'NN':
return 1
# f_2
elif i == 2 and y[j-1] == 'VBZ':
return 1
# f_3
elif i == 3 and x[0] == 'DT':
return 1
else:
return 0
Label Bias 문제와 극복 방안
CRF는 Label Bias 문제를 극복하기 위해 제안된 기법입니다. Label Bias란 다음과 같은 문제를 가리킵니다.
- Preference of states with lower number transitions over others
이를 해결하기 위해 확률값을 구할 때 global normalize를 합니다. 이를 구현한 파이썬 코드는 다음과 같습니다.
def calc_Z(x, n, m, all_labels, FeatureFunction, weights):
Z = 0
all_possible_Y = itertools.product(all_labels, repeat=n)
for y_prime in all_possible_Y:
tmpZ = 0
for j in range(1, n):
for i in range(1, m):
tmpZ += weights[i] * FeatureFunction(y_prime, x, i, j)
Z += math.exp(tmpZ)
return Z
그런데 보시다시피 가능한 모든 조합의 레이블 시퀀스에 대한 확률을 구해야 합니다. 가령 품사 종류가 명사(NN), 동사(VB) 등 다섯 가지이고, 시퀀스 길이가 5(개 단어)라면 다음 표처럼 $5^5$=3125가지의 경우의 수를 고려해야 합니다.
| $y_1$ | $y_2$ | $y_3$ | $y_4$ | $y_5$ |
|---|---|---|---|---|
| NN | NN | NN | NN | NN |
| NN | NN | NN | NN | VBN |
| NN | NN | NN | NN | VBZ |
| NN | NN | NN | NN | IN |
| NN | NN | NN | NN | DT |
| NN | NN | NN | VBN | NN |
| NN | NN | NN | VBN | VBN |
| NN | NN | NN | VBN | VBZ |
| NN | NN | NN | VBN | IN |
| NN | NN | NN | VBN | DT |
| … | … | … | … | … |
CRF에서 가장 계산량이 많은 부분이 바로 $Z$를 구하는 부분입니다. 위 파이썬 코드는 수식 이해 용도로 수식을 그대로 옮겨놓은 형태이지만, 실제로는 다이내믹 프로그래밍(dynamic programming) 등 최적화 기법을 쓴다고 합니다.
파라메터 학습 : 최대우도추정
CRF의 파라메터는 로지스틱 회귀의 파라메터를 추정하는 방식과 같이 최대우도추정법(Maximum Likelihood Estimation)으로 구합니다. 식이 매우 복잡한데, 저 또한 정리 용도로 남겨둡니다. CRF의 로그 우도함수는 다음과 같습니다. 식의 첫 줄 두번째 항은 과적합(overfitting) 방지를 위한 정규화(regularization) 항입니다.
위 로그 우도함수는 파라메터 $λ$로 편미분한 값이 0인 지점에서 최대값을 가집니다. 이를 3등분해서 각각 $λ$에 대해 편미분한 결과는 다음과 같습니다. 우선 $A$를 편미분한 결과입니다.
다음은 $B$를 파라메터 $λ$에 대해 편미분한 결과입니다.
마지막으로 $C$입니다.
$A$는 데이터의 empirical distribution으로 해석할 수 있습니다. 식과 파이썬 코드는 다음과 같습니다.
def calc_empirical_expectation_feature_i(train_data, FeatureFunction, i):
empirical_expectation_feature_i = 0
for x, y in train_data:
n = len(y)
for j in range(1, n):
empirical_expectation_feature_i += FeatureFunction(y, x, i, j)
return empirical_expectation_feature_i
$B$는 모델이 내놓는 distribution으로 해석할 수 있습니다. 식과 파이썬 코드는 다음과 같습니다.
import itertools
def calc_predicted_expectation_feature_i(train_data, FeatureFunction,
all_labels, weights, i):
predicted_expectation = 0
for x, y in train_data:
n = len(y)
all_possible_Y = itertools.product(all_labels, repeat=n)
for y_prime in all_possible_Y:
predicted_expectation += \
(calc_prob_y_given_x(y_prime, x, all_labels, FeatureFunction, weights)
* sum([FeatureFunction(x, y, i, j) for j in range(1, n)]))
print(predicted_expectation)
return predicted_expectation
로그우도 함수에 대한 편미분 식을 다시 적으면 다음과 같은데요. $A$와 $B$가 비슷할 수록 로그우도 함수의 도함수가 작아집니다. 데이터의 분포와 모델의 분포가 비슷할 수록, 즉 모델이 데이터의 분포를 잘 모사할 수록 학습이 잘 되었다는 이야기입니다.
이제 거의 다 왔습니다. 파라메터 $λ$를 랜덤 초기화한 뒤 이제까지 구한 로그우도 함수가 커지는 방향(그래디언트)로 파라메터를 조금씩 업데이트해 주면 됩니다(gradient ascent). 이를 파이썬 코드로 구현한 결과는 다음과 같습니다.
#train data set = {(x, y)}
def get_all_labels(train_data):
available_labels = set()
for x, y in train_data:
available_labels.update(y)
return list(available_labels)
# m = feature vector size
import random
def initial_weights(m):
return [random.random() for _ in range(m)]
def train(train_data, FeatureFunctions, m, iterations=100, learning_rate=0.1):
all_labels = get_all_labels(train_data)
weights = initial_weights(m)
for _ in range(iterations):
for i in range(1, m):
empirical_expectation = \
calc_empirical_expectation_feature_i(train_data, FeatureFunction, i)
predicted_expectation = \
calc_predicted_expectation_feature_i(train_data, FeatureFunction,
all_labels, weights)
weights[i] = weights[i] + \
learning_rate * (empirical_expectation - predicted_expectation)
비터비 알고리즘
시퀀스 분류를 하기 위해 이 먼길을 돌아왔습니다. CRF가 최적 상태열을 inference하는 기법인 비터비 알고리즘은 다음과 같이 동작합니다.
다음 과정입니다.
다음 과정입니다.
마지막으로 backtrace 과정입니다.
