조건부 랜덤 필드

Conditional random field; CRF; 조건부 랜덤 필드, 조건부 무작위장
입력 전체가 주어졌을 때 출력 변수들(꼬리표 열 등)의 결합 조건부 분포를 무방향 그래프 위의 지수족 모형으로 직접 모델링하는 판별 확률 모형

조건부 랜덤 필드(Conditional random field, CRF)는 입력 $x$ 가 주어졌을 때 서로 의존하는 여러 출력 변수 $y$ 의 조건부 확률 $p (y ∣ x)$ 를 하나의 무방향 그래프 모형으로 나타내는 판별 모형이다. 2001년 존 래퍼티(John Lafferty), 앤드루 매캘럼(Andrew McCallum), 페르난도 페레이라(Fernando Pereira)가 ICML에서 발표했다.^[1] 국내에서는 '조건부 랜덤 필드'나 영어 약어 CRF로 주로 부르며, '조건부 무작위장'이라는 번역어도 쓰인다.

단어마다 품사나 개체명 꼬리표를 붙이는 시퀀스 레이블링이 대표 용도다. 각 위치를 따로 분류하면 "B-PER 다음에 I-LOC" 같은 앞뒤가 맞지 않는 꼬리표 열이 나오기 쉬운데, CRF는 꼬리표 사이의 전이까지 한 모형 안에서 점수화하고 열 전체를 한꺼번에 정규화한다. 딥 러닝 이전 자연어 처리의 개체명 인식·품사 태깅·청킹·형태소 분석의 표준 도구였고, 지금도 BiLSTM-CRF, BERT-CRF처럼 신경망 출력 위에 얹는 층으로 쓰인다. 컴퓨터 비전에서는 이미지 분할 결과를 다듬는 후처리로 쓰였다.

정의

그래프 $G = (V, E)$ 의 꼭짓점마다 출력 변수 $Y_{v}$ 가 하나씩 있다고 하자. 입력 $X$ 를 조건으로 했을 때 각 $Y_{v}$ 가 그래프에 대해 마르코프 성질, 즉

$P (Y_{v} ∣ X, {Y_{w} : w \neq v}) = P (Y_{v} ∣ X, {Y_{w} : w \sim v})$

을 만족하면 $(X, Y)$ 를 조건부 랜덤 필드라 한다( $w \sim v$ 는 이웃).^[1] 해머슬리-클리퍼드 정리에 따라 이런 분포는 그래프의 클리크(clique) $c$ 마다 정의한 양의 퍼텐셜 함수의 곱으로 쓸 수 있다.

$p (y ∣ x) = \frac{1}{Z (x)} \prod_{c} ψ_{c} (y_{c}, x), Z (x) = \sum_{y^{'}} \prod_{c} ψ_{c} (y'_{c}, x)$

퍼텐셜을 $ψ_{c} = \exp (\sum_{k} λ_{k} f_{k} (y_{c}, x))$ 처럼 특징 함수 $f_{k}$ 의 가중합 지수로 두는 것이 보통이다. 즉 CRF는 깁스 분포 꼴의 마르코프 랜덤 필드(MRF)를 입력 $x$ 에 조건부로 만든 것이다. $p (x)$ 는 모델링하지 않으므로 입력 쪽에는 서로 겹치고 의존하는 특징을 마음대로 넣을 수 있다. 정규화 상수 $Z (x)$ 가 입력마다 따로 계산된다는 점이 무조건부 MRF와 다르다.

선형 체인 CRF

출력이 열 $y = (y_{1}, \dots, y_{n})$ 이고 이웃한 꼬리표끼리만 연결된 사슬 그래프가 가장 많이 쓰이는 형태다.

$p (y ∣ x) = \frac{1}{Z (x)} \exp (\sum_{t = 1}^{n} \sum_{k} λ_{k} f_{k} (y_{t - 1}, y_{t}, x, t))$

특징 함수의 예는 다음과 같다.

전이 특징: $f (y_{t - 1}, y_{t}, x, t) = 1 [y_{t - 1} = B-PER, y_{t} = I-PER]$
관측 특징: $f (y_{t - 1}, y_{t}, x, t) = 1 [y_{t} = B-LOC, x_{t + 1} = w]$ (w는 조사 "에"), 대문자로 시작하는지, 접미사가 무엇인지, 사전에 있는지 등

특징 함수는 입력 열 $x$ 전체를 아무 위치에서나 볼 수 있고 확률적 의미가 없어도 된다. 신경망과 결합할 때는 특징 함수 대신 위치별 방출 점수 행렬 $E \in ℝ^{n \times K}$ (신경망 출력)와 꼬리표 전이 점수 행렬 $A \in ℝ^{K \times K}$ (학습되는 매개변수)로 다시 쓴다.

$s (x, y) = \sum_{t = 1}^{n} E_{t, y_{t}} + \sum_{t = 2}^{n} A_{y_{t - 1}, y_{t}}, p (y ∣ x) = \frac{\exp s (x, y)}{\sum_{y^{'}} \exp s (x, y^{'})}$

HMM, MEMM과 비교

CRF는 은닉 마르코프 모델(HMM)과 최대 엔트로피 마르코프 모형(MEMM)의 단점을 함께 풀려고 나왔다.

구분	HMM	MEMM	선형 체인 CRF
모형 종류	생성 모형 $p (x, y)$	판별 모형 $p (y ∣ x)$	판별 모형 $p (y ∣ x)$
분해	$\prod_{t} p (y_{t} ∣ y_{t - 1}) p (x_{t} ∣ y_{t})$	$\prod_{t} p (y_{t} ∣ y_{t - 1}, x)$	$\frac{1}{Z (x)} \prod_{t} ψ_{t} (y_{t - 1}, y_{t}, x)$
정규화	확률표 자체가 정규화	위치별(국소) 정규화	열 전체(전역) 정규화
입력 특징	현재 관측 하나, 관측끼리 독립 가정	겹치는 임의 특징 가능	겹치는 임의 특징 가능
레이블 편향	없음	있음	없음
학습	빈도 세기(또는 EM)	위치별 로지스틱 회귀	볼록 최적화(L-BFGS, SGD)

레이블 편향 문제

MEMM은 각 위치에서 "이전 상태에서 나가는 전이 확률의 합이 1"이 되도록 국소 정규화한다. 그래서 나가는 길이 하나뿐인 상태는 관측이 무엇이든 그 길로 확률 1을 보내고, 나가는 길이 적은 상태일수록 관측을 무시하는 경향이 생긴다. 래퍼티 등은 이를 레이블 편향 문제(label bias problem)라 부르고, 열 전체를 한 번에 정규화하는 CRF가 이를 피한다고 보였다.^[1] HMM이 만든 합성 데이터 실험에서 CRF의 오류율은 4.6%, MEMM은 42%였다.

같은 논문의 펜 트리뱅크 품사 태깅 실험(1차 모형, 110만 단어 말뭉치의 50%로 학습)은 다음과 같다. 철자 특징(대문자·숫자로 시작, 하이픈, -ing·-tion 같은 접미사)을 더하자 판별 모형만 크게 좋아졌다. HMM은 이런 겹치는 특징을 넣을 수 없다.^[1]

모형	전체 오류율	미등록어(OOV) 오류율
HMM	5.69%	45.99%
MEMM	6.37%	54.61%
CRF	5.55%	48.05%
MEMM + 철자 특징	4.81%	26.99%
CRF + 철자 특징	4.27%	23.76%

추론

선형 체인에서는 동적 계획법으로 정확한 추론을 $O (n K^{2})$ 에 한다( $K$ 는 꼬리표 수). HMM의 전방-후방 알고리즘, 비터비 알고리즘과 같은 구조다. 수치 안정성을 위해 로그 공간에서 logsumexp로 계산한다.

분배 함수: 전방 변수 $α_{1} (j) = E_{1, j}$ , $α_{t} (j) = \log \sum_{i} \exp (α_{t - 1} (i) + A_{i j}) + E_{t, j}$ 로 두면 $\log Z (x) = \log \sum_{j} \exp α_{n} (j)$ 다. 가능한 꼬리표 열 $K^{n}$ 개를 나열하지 않고도 정규화 상수를 얻는다.
주변 확률: 후방 변수 $β_{t}$ 를 같은 방식으로 뒤에서부터 구하면 $p (y_{t} = j ∣ x) \propto \exp (α_{t} (j) + β_{t} (j))$ , 이웃 쌍의 주변 확률도 나온다. 학습의 그래디언트 계산에 쓰인다.
디코딩: logsumexp를 max로 바꾸고 역추적 포인터를 저장하면 가장 점수가 높은 열 $\arg \max_{y} p (y ∣ x)$ 를 비터비 알고리즘으로 구한다. 분배 함수는 모든 열에 공통이므로 디코딩에는 필요 없다.
일반 그래프: 고리가 있는 그래프(격자 모양의 이미지 CRF 등)에서 정확한 추론은 일반적으로 다루기 어렵다. 루피 신뢰 전파(loopy belief propagation), 평균장(mean field) 근사, 그래프 컷 같은 근사 방법을 쓴다. 트리 구조면 메시지 전달로 정확히 풀린다.

학습

훈련 데이터 ${(x^{(i)}, y^{(i)})}$ 의 조건부 로그 우도에 L2 정규화를 더해 최대화한다.

$ℒ (λ) = \sum_{i} \log p (y^{(i)} ∣ x^{(i)}; λ) - \frac{1}{2 σ^{2}} ‖ λ ‖^{2}$

그래디언트는 "정답 열에서 센 특징 값"에서 "모형이 기대하는 특징 값"을 뺀 것이다.

$\frac{\partial ℒ}{\partial λ_{k}} = \sum_{i} (\sum_{t} f_{k} (y_{t - 1}^{(i)}, y_{t}^{(i)}, x^{(i)}, t) - 𝔼_{p (y ∣ x^{(i)})} [\sum_{t} f_{k} (y_{t - 1}, y_{t}, x^{(i)}, t)]) - \frac{λ_{k}}{σ^{2}}$

기댓값 항은 전방-후방으로 구한 이웃 쌍 주변 확률로 계산한다. 모든 변수가 관측되는 경우 이 목적 함수는 오목 함수라 전역 최적해가 하나다. 원 논문은 반복 스케일링(iterative scaling) 계열 알고리즘으로 학습했는데,^[1] 2003년 샤(Fei Sha)와 페레이라가 공액 경사법과 L-BFGS 같은 준뉴턴 방법이 훨씬 빠르다는 것을 보인 뒤로는 L-BFGS가 표준이 되었다.^[2] 특징이 수백만 개면 L1 정규화로 대부분의 가중치를 0으로 만들어 모형을 줄이기도 한다. 신경망과 결합한 경우에는 음의 로그 우도 $\log Z (x) - s (x, y)$ 를 손실로 두고 자동 미분과 확률적 경사 하강법으로 방출 점수를 내는 신경망과 전이 행렬을 함께 학습한다.

변형과 확장

변형	내용	비고
고차 CRF	꼬리표가 직전 $k$ 개 꼬리표에 의존	비용이 $K^{k + 1}$ 로 늘어 작은 $k$ 만 실용적
세미 마르코프 CRF	꼬리표 대신 가변 길이 구간(segment)에 점수를 매긴다	개체명처럼 여러 토큰에 걸친 단위를 직접 다룬다^[3]
스킵 체인 CRF	멀리 떨어진 같은 단어끼리 간선 추가	고리가 생겨 근사 추론 필요
완전 연결 CRF(DenseCRF)	이미지의 모든 픽셀 쌍을 가우시안 커널 퍼텐셜로 연결	평균장 근사와 고속 필터링으로 실용화^[4]
잠재 동역학 CRF(LDCRF)	관측과 꼬리표 사이에 숨은 변수를 둔 판별 모형	제스처 인식 등
구조적 SVM	같은 구조에서 확률 대신 마진 최대화로 학습	확률 출력은 없음

딥 러닝과의 결합

BiLSTM-CRF: 양방향 LSTM이 방출 점수를 만들고 그 위에 선형 체인 CRF를 얹는다. 2015년 후앙(Zhiheng Huang) 등이 품사 태깅·청킹·개체명 인식에 적용했고,^[5] 2016년 램플(Guillaume Lample) 등의 LSTM-CRF는 글자 단위 표현을 더해 CoNLL-2003 영어 개체명 인식에서 F1 90.94를 기록했다.^[6] 수작업 특징 설계가 필요 없어졌다는 점이 컸다.
BERT-CRF: BERT 같은 사전 학습 인코더 위에 CRF 층을 얹는다. 사전 학습 표현이 문맥을 충분히 담아 단순 토큰 분류와의 차이가 작아졌지만, 꼬리표 열의 형식 일관성을 강제하는 용도로 쓴다. 자세한 비교는 개체명 인식 문서 참고.
이미지 분할 후처리: DeepLab 첫 버전은 합성곱 신경망의 거친 분할 결과를 완전 연결 CRF로 다듬어 물체 경계를 정교하게 만들었다.^[7] 이어 평균장 추론의 반복을 순환 신경망 층으로 펼쳐 CNN과 끝에서 끝까지 함께 학습하는 CRF-as-RNN이 나왔다.^[8] 이후 분할 모델의 자체 성능이 올라가면서 CRF 후처리는 점차 빠졌다.

구현

PyTorch로 CRF 손실과 비터비

신경망 위에 얹는 선형 체인 CRF 층의 핵심은 아래 두 함수다. 방출 점수 E는 보통 BiLSTM이나 BERT의 출력에 선형 층을 씌워 얻는다. 아래 코드는 정확성을 확인하려고 가능한 꼬리표 열 243개( $3^{5}$ )를 모두 나열한 값과 비교한다(PyTorch 2.5.1에서 실행).

import itertools
import torch

def crf_nll(emissions, transitions, tags):
    """선형 체인 CRF의 음의 로그 우도 -log p(y|x).
    emissions: (n, K) 위치별 꼬리표 점수(예: BiLSTM·BERT 출력)
    transitions: (K, K) 꼬리표 i 다음 j의 점수, tags: (n,) 정답 꼬리표"""
    n = emissions.size(0)
    # 정답 열의 점수
    score = emissions[0, tags[0]]
    for t in range(1, n):
        score = score + transitions[tags[t-1], tags[t]] + emissions[t, tags[t]]
    # 전방 알고리즘: alpha_t(j) = logsumexp_i(alpha_{t-1}(i) + A[i, j]) + E[t, j]
    alpha = emissions[0]
    for t in range(1, n):
        alpha = torch.logsumexp(alpha.unsqueeze(1) + transitions, dim=0) + emissions[t]
    log_Z = torch.logsumexp(alpha, dim=0)
    return log_Z - score

def viterbi(emissions, transitions):
    n, K = emissions.shape
    delta, back = emissions[0], []
    for t in range(1, n):
        cand = delta.unsqueeze(1) + transitions      # (이전, 현재)
        delta, idx = cand.max(dim=0)
        delta = delta + emissions[t]
        back.append(idx)
    best = [int(delta.argmax())]
    for idx in reversed(back):
        best.append(int(idx[best[-1]]))
    return best[::-1]

torch.manual_seed(0)
n, K = 5, 3
E = torch.randn(n, K, requires_grad=True)
A = torch.randn(K, K, requires_grad=True)
y = torch.tensor([0, 2, 1, 1, 0])

loss = crf_nll(E, A, y)
loss.backward()                                       # 자동 미분으로 E, A의 그래디언트

# 검증: K^n = 243개 열을 모두 나열한 정규화 상수와 비교
def path_score(p):
    return sum(E[t, p[t]] for t in range(n)) + sum(A[p[t-1], p[t]] for t in range(1, n))
with torch.no_grad():
    paths = list(itertools.product(range(K), repeat=n))
    scores = torch.stack([path_score(p) for p in paths])
    brute = torch.logsumexp(scores, 0) - path_score(y.tolist())
    print(f"NLL 전방={loss.item():.5f}  전수={brute.item():.5f}")
    print("비터비:", viterbi(E, A), " 전수 최댓값:", list(paths[int(scores.argmax())]))

NLL 전방=8.88530  전수=8.88530
비터비: [0, 0, 0, 2, 1]  전수 최댓값: [0, 0, 0, 2, 1]

실제 학습 코드에서는 배치와 패딩 마스크를 처리하고, BIO 규칙에 어긋나는 전이(O 다음 I-PER 등)의 점수를 큰 음수로 고정해 불가능한 열이 나오지 않게 하는 경우가 많다.

sklearn-crfsuite로 특징 기반 CRF

CRFsuite의 파이썬 래퍼인 sklearn-crfsuite는 토큰마다 특징 딕셔너리를 만들어 넘기면 L-BFGS로 학습한다. 아래는 장난감 개체명 데이터 예시다(sklearn-crfsuite 0.5, python-crfsuite 0.9.12에서 실행).

import sklearn_crfsuite

def word2features(sent, i):
    w = sent[i]
    return {
        "bias": 1.0,
        "word": w,
        "suffix1": w[-1:],
        "is_digit": w.isdigit(),
        "prev": sent[i-1] if i > 0 else "<BOS>",
        "next": sent[i+1] if i < len(sent) - 1 else "<EOS>",
    }

def sent2features(sent):
    return [word2features(sent, i) for i in range(len(sent))]

train = [
    (["삼성전자", "는", "수원", "에", "있다"], ["B-ORG", "O", "B-LOC", "O", "O"]),
    (["네이버", "는", "성남", "에", "있다"], ["B-ORG", "O", "B-LOC", "O", "O"]),
    (["카카오", "는", "제주", "에", "있다"], ["B-ORG", "O", "B-LOC", "O", "O"]),
    (["홍길동", "은", "서울", "에", "산다"], ["B-PER", "O", "B-LOC", "O", "O"]),
]
X = [sent2features(s) for s, _ in train]
y = [tags for _, tags in train]

crf = sklearn_crfsuite.CRF(
    algorithm="lbfgs",   # L-BFGS로 조건부 로그 우도 최대화
    c1=0.1,              # L1 정규화 계수
    c2=0.1,              # L2 정규화 계수
    max_iterations=100,
    all_possible_transitions=True,
)
crf.fit(X, y)
test = ["카카오", "는", "판교", "에", "있다"]
print(crf.predict_single(sent2features(test)))
# ['B-ORG', 'O', 'B-LOC', 'O', 'O']

학습에 없던 "판교"를 다음 토큰이 "에"라는 특징으로 B-LOC로 맞힌다. crf.transition_features_로 학습된 전이 가중치를 볼 수 있다.

도구

CRF++: 구도 다쿠(工藤拓)가 만든 C++ 구현. 특징 템플릿 파일로 특징을 정의한다.
CRFsuite: 오카자키 나오아키(岡崎直観)의 C 구현. 파이썬에서는 python-crfsuite, sklearn-crfsuite로 쓴다.
MeCab: 형태소 분석기 MeCab은 일본어 형태소 분석에 CRF를 적용한 연구를 바탕으로 비용 값을 학습한다.^[9] 한국어 사전을 붙인 mecab-ko 계열이 국내 형태소 분석에 쓰인다.
딥 러닝 프레임워크: 파이토치용 pytorch-crf 같은 외부 패키지나 위와 같은 직접 구현을 쓴다.

실무 선택 기준

데이터가 적고 GPU가 없으며 도메인 특징(사전, 정규식, 형태소 정보)을 잘 알면 특징 기반 CRF가 여전히 가볍고 빠른 기준선이다.
데이터가 충분하면 사전 학습 인코더의 토큰 분류가 기본이다. 꼬리표 형식 오류가 문제가 되거나 데이터가 적은 도메인이면 CRF 층을 얹어 비교해 본다.
꼬리표 수 $K$ 가 크면 $O (n K^{2})$ 비용이 커진다. 중첩 개체처럼 한 토큰이 여러 꼬리표를 가져야 하는 문제는 선형 체인 CRF로 표현하기 어렵다.

한계

특징 기반 CRF는 성능이 특징 설계에 크게 좌우된다.
일반 그래프에서는 정확한 추론과 학습이 어렵다.
선형 체인 CRF가 잡는 꼬리표 의존은 이웃 사이(1차)뿐이다. 먼 거리 의존은 입력 표현(신경망)이 담당해야 한다.
학습 때마다 전방-후방 계산이 필요해 단순 소프트맥스 분류보다 느리다.

같이 보기

각주

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 John Lafferty, Andrew McCallum, Fernando Pereira, 〈Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data〉, ICML 2001, pp. 282~289. PDF
↑ Fei Sha, Fernando Pereira, 〈Shallow Parsing with Conditional Random Fields〉, HLT-NAACL 2003, pp. 134~141. ACL Anthology N03-1028
↑ Sunita Sarawagi, William W. Cohen, 〈Semi-Markov Conditional Random Fields for Information Extraction〉, NIPS 2004. PDF
↑ Philipp Krähenbühl, Vladlen Koltun, 〈Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials〉, NIPS 2011. arXiv:1210.5644
↑ Zhiheng Huang, Wei Xu, Kai Yu, 〈Bidirectional LSTM-CRF Models for Sequence Tagging〉, 2015. arXiv:1508.01991
↑ Guillaume Lample 외, 〈Neural Architectures for Named Entity Recognition〉, NAACL 2016. arXiv:1603.01360
↑ Liang-Chieh Chen 외, 〈Semantic Image Segmentation with Deep Convolutional Nets and Fully Connected CRFs〉, ICLR 2015. arXiv:1412.7062
↑ Shuai Zheng 외, 〈Conditional Random Fields as Recurrent Neural Networks〉, ICCV 2015. arXiv:1502.03240
↑ Taku Kudo, Kaoru Yamamoto, Yuji Matsumoto, 〈Applying Conditional Random Fields to Japanese Morphological Analysis〉, EMNLP 2004. ACL Anthology W04-3230

참고 문헌

Charles Sutton, Andrew McCallum, 〈An Introduction to Conditional Random Fields〉, Foundations and Trends in Machine Learning 4(4), 2012. arXiv:1011.4088
Hanna M. Wallach, 〈Conditional Random Fields: An Introduction〉, Technical Report MS-CIS-04-21, University of Pennsylvania, 2004.

[lafferty-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 John Lafferty, Andrew McCallum, Fernando Pereira, 〈Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data〉, ICML 2001, pp. 282~289. PDF

[sha-2] Fei Sha, Fernando Pereira, 〈Shallow Parsing with Conditional Random Fields〉, HLT-NAACL 2003, pp. 134~141. ACL Anthology N03-1028

[3] Sunita Sarawagi, William W. Cohen, 〈Semi-Markov Conditional Random Fields for Information Extraction〉, NIPS 2004. PDF

[dense-4] Philipp Krähenbühl, Vladlen Koltun, 〈Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials〉, NIPS 2011. arXiv:1210.5644

[huang-5] Zhiheng Huang, Wei Xu, Kai Yu, 〈Bidirectional LSTM-CRF Models for Sequence Tagging〉, 2015. arXiv:1508.01991

[lample-6] Guillaume Lample 외, 〈Neural Architectures for Named Entity Recognition〉, NAACL 2016. arXiv:1603.01360

[7] Liang-Chieh Chen 외, 〈Semantic Image Segmentation with Deep Convolutional Nets and Fully Connected CRFs〉, ICLR 2015. arXiv:1412.7062

[8] Shuai Zheng 외, 〈Conditional Random Fields as Recurrent Neural Networks〉, ICCV 2015. arXiv:1502.03240

[9] Taku Kudo, Kaoru Yamamoto, Yuji Matsumoto, 〈Applying Conditional Random Fields to Japanese Morphological Analysis〉, EMNLP 2004. ACL Anthology W04-3230

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]