본 글은, Conditional Random Field(CRF)를 공부하기 위해, lovit/
From Softmax Regression to Conditional Random Field for Sequential Labeling
포스트를 읽고 정리한 글임을 밝힙니다.
Conditional Random Field(CRF)는 sequential labeling 문제에서 Recurrent Neural Network(RNN) 등의 deep learning 계열 알고리즘이 이용되기 이전에 널리 사용되던 알고리즘입니다. Conditional Random Field는 Softmax regression의 일종입니다. 그러나 a vector point 가 아닌, sequence 형식의 입력 변수에 대하여 같은 길이의 label sequence 를 출력합니다. 이를 위해서 Conditional Random Field 는 potential function 을 이용합니다. Potential function 은 다양한 형식의 sequence data 를 high dimensional Boolean sparse vector 로 변환하여 입력 데이터를 logistic regression 이 처리할 수 있도록 도와줍니다.
본 글에서는 다음과 같은 순서로 CRF를 소개하겠습니다.
- Sequential labeling
- Logistic(Softmax) regression
- Sequential labeling
- Sequential labeling using Softmax regression
- MEMM : Maximum Entropy Markov Model
- CRF : MEMM to Conditional Random Field
Sequential labeling
Softmax regression
Conditional Random Field (CRF) 는 softmax regression 입니다. 정확히는 categorical sequential data 를 softmax regression 이 이용할 수 있는 형태로 변형한 뒤, 이를 이용하여 sequence vector 를 예측하는 softmax regression 입니다. 그렇기 때문에 softmax regression 에 대하여 간략히 리뷰합니다.
로지스틱 회귀는 기하학적으로 해석할 수 있습니다. 각각의 θ는 일종의 클래스의 대표 벡터가 됩니다. θ₁은 파란색 점들을 대표하는 벡터이고, θ₂는 빨간색 점들을 대표하는 벡터입니다. 각 클래스 당 하나의 대표 벡터를 가집니다. 만약 한 점 x가 θ₁과 일치한다면 exp(θ₁ᵀx)는 어느 정도 큰 양수가 되고, exp(θ₂ᵀx)는 0에 가까운 값이 되기 때문에 x의 클래스 1에 해당할 확률이 1이 됩니다. 로지스틱 회귀는 각 점에 대해 각 클래스의 대표 벡터에 얼마나 가까운지를 학습하는 것입니다.
Softmax regression 은 logistic regression 의 일반화버전입니다. 클래스가 2 보다 많은 개일 때, 개의 의 대표벡터를 학습하는 것입니다. 각 클래스를 구분하는 결정단면은 대표벡터의 Voronoi diagram 과 같습니다. 단, 각 대표벡터에 얼마나 가까운지는 벡터 간 내적 (inner product) 로 정의됩니다.
Sequential Labeling
1. 의미
일반적으로 classification 이라 하면, 하나의 입력 벡터 $x$ 에 대하여 하나의 label 값 $y$ 를 return 하는 과정입니다. 그런데 입력되는 $x$ 가 벡터가 아닌 sequence 일 경우가 있습니다. $x$ 를 길이가 $n$ 인 sequence, $x=\left[x_1, x_2, \ldots, x_n\right]$ 라 할 때, 같은 길이의 $y=\left[y_1, y_2, \ldots, y_n\right]$ 을 출력해야 하는 경우가 있습니다. Labeling 은 출력 가능한 label 중에서 적절 한 것을 선택하는 것이기 때문에 classification 입니다. 데이터의 형식이 벡터가 아닌 sequence 이기 때문에 sequential data 에 대한 classification 이라는 의미로 sequential labeling 이라 부릅니다.
2. 대표적인 Sequential Labeling 문제
띄어쓰기 문제나 품사 판별이 대표적인 sequentail labeling입니다.
품사판별 :
이 과정을 확률모형으로 표현하면 주어진 $x$ 에 대하여 $P(y \mid x)$ 가 가장 큰 $y$ 를 찾는 문제입니다. 이를 아래처럼 기술 하기도 합니다. $x_{1: n}$ 은 길이가 $n$ 인 sequence 라는 의미입니다.
$$\operatorname{argmax}_y P\left(y_{1: n} \mid x_{1: n}\right)$$
Sequential labeling using Softmax regression
품사 판별 문제에서 아래 그림과 같이 앞, 뒤 단어와 품사 정보를 활용하면 ,
이 sequential labeling 문제를 softmax regression 문제라고 하는 이유는 다음과 같이 해결할 수 있기 때문입니다.
앞에서 이야기한 개념을 logistic regression 을 이용하여 구현할 수 있습니다. 길이가 $n$ 인 $x=\left[x_1, x_2, \ldots, x_n\right]$ 에 대 하여 $y=\left[y_1, y_2, \ldots, y_n\right]$ 을 출력하기 위하여 $n$ 개의 독립적인 classification 을 수행합니다. 이 classifier 는 모든 경 우에 공유되는 하나의 classifier 입니다.
$y_1$ 을 예측하는데는 $x_1$ 을 이용합니다. $y_2$ 를 예측하는데는 $x_1, x_2$, 그리고 앞서 예측한 $y_1$ 을 이용합니다. 이 과정을 일 반적으로 기술하면 다음과 같습니다.
$y_1=f\left(x_1\right)$.
$y_2=f\left(x_1, x_2, y_1\right)$.
....
$y_n=f\left(x_{n-1}, x_n, y_{n-1}\right)$.
이를 정리하면 길이가 $n$ 인 $x_{1: n}$ 에 대하여 $y_{1: n}$ 이 출력될 확률은 아래처럼 기술할 수 있습니다. $P\left(y_1 \mid x_{1: n}\right)$ 은 $y_1$ 예 측하는데 $x_{1: n}$ 의 어떤 부분을 이용해도 좋다는 의미입니다. 이 말 안에는 $x_1$ 을 이용하여 $y_1$ 을 예측하는 부분이 포함 됩니다.
$P\left(y_{1: n} \mid x_{1: n}\right)=P\left(y_1 \mid x_{1: n}\right) \times\left(\prod_{i=2: n} P\left(y_i \mid x_{1: n}, y_{i-1}\right)\right)$
모든 경우에 대하여 $y_i$ 를 출력할 수 있는 하나의 classifiers 를 학습하여 길이가 $n$ 인 sequence 에 대해 순차적으로 $n$ 번 적용하면 sequential labeling 을 할 수 있습니다. 이 때 classifier 로 softmax regression 이 이용될 수 있습니다.
MEMM
이런 방식으로 sequential labeling을 하는 모델을 Maximum Entropy Markov Model (MEMM) 이라 합니다.
MEMM
1. Markov Model
식 $y_n=f\left(x_{n-1}, x_n, y_{n-1}\right)$ 에서 현재 시점 $y_i$ 의 state 를 판단하는데 이용되는 다른 state 는 이전 시점 $y_{i-1}$ 뿐입니 다. 이처럼 현재 시점의 state 에 영향을 줄 수 있는 다른 state 가 과거의 state 일 때 이를 Markov model 이라 합니다.
2. Maximum Entropy Model
Maximum Entropy Model 은 softmax regression 형식의 classifier 를 의미합니다. 아래는 softmax regression 의 각 클 래스에 속할 확률값입니다.
이를 기반으로 softmax regression 의 loss function 은 다음처럼 기술됩니다. 아래 식은 cross entropy 입니다.
Softmax regression 은 $\theta$ 에 의한 예측값과 정답데이터의 cross entropy 를 최소화합니다.
loss $=-\left(\sum_{i=1}^m \sum_{k=1}^n 1\left(y^{(i)}=k\right) \log \frac{\exp \left(\theta^k \cdot x^{(i)}\right)}{\sum_{j=1}^n \exp \left(\theta^j \cdot x^{(i)}\right)}\right)$
그런데 minimum entropy model 이 아닌 maximum entropy model 이란 이름이 붙은 배경은 다음과 같습니다. 위의 loss function 은 학습데이터에 등장한 패턴에 대한 식입니다. 모델이 예측하는 확률과 데이터에 등장하는 패턴의 확률이 일치할수록 cross entropy 는 작아집니다. 하지만 학습데이터에 등장하지 않은 단어의 품사를 판단하는 것처럼 모르는 input 에 대해서는 일절의 판단을 할 수 없습니다. 확률로 표현하면 모든 label 에 대한 확률이 uniform 이어야 하는데, 이 때 entropy 가 최대가 됩니다.
3. Maximum Entropy Markov Model
softmax regression 과 같은 방식으로 labeling 을 하면서, sequential data 의 특징을 반영하기 위하여 Markov Model 의 구조를 이용합니다. 그렇기 때문에 이와 같은 이름이 붙여졌습니다.
$\mathrm{MEMM}$ 의 $P\left(y_{1: n} \mid x_{1: n}\right)$ 은 다음처럼 기술됩니다.
$$
P(y \mid x)=\prod_{i=1}^n \frac{\exp \left(\sum_{j=1}^m \lambda_j f_j\left(x, i, y_i, y_{i-1}\right)\right)}{\sum_{y^{\prime}} \exp \left(\sum_{j=1}^m \lambda_j f_j\left(x, i, y_i^c, y_{i-1}^c\right)\right)}
$$
$f_j$ 는 potential function 입니다. Potential functions 에 의하여 $m$ 차원의 sparse vector 로 표현된 $x_i$ 와 coefficient vector $\lambda$ 의 내적에 exponential 이 취해집니다. 다른 labels 후보 $y^{\prime}$ 의 값들의 합으로 나뉘어집니다. Softmax regression 형식입니다. 정확히는 Maximum Entropy Model 입니다. 그리고 이 과정이 $n$ 번 반복됩니다.
Potential function
그런데 softmax regression 은 벡터 $x$ 에 대하여 label $y$ 를 출력하는 함수입니다. 이를 위해서는 식 $f\left(x_{i-1}, x_i, y_{i-1}\right)$ 에 들어가는 입력변수를 벡터로 표현해야 합니다. Potential function 은 단어와 같은 categorical value 를 포함하여 sequence 로 입력된 다양한 형태의 값을 벡터로 변환합니다.
임의 형태의 값이라도 벡터로 표현할 수 있는 방법 중 하나는 그 값이 내가 원하는 경우인지를 Boolean 으로 표현하는 필터를 이용하는 것입니다.
예를 들어보죠.
띄어쓰기 문제를 위한 Potential Funtion에 대해 보겠습니다.
아래 그림은 “예문 입니다” 의 예제에 대하여 템플릿을 적용한 결과입니다. 우리는 길이가 5 인 문장에 대하여 5 번의 (마지막 글자는 반드시 띄기 때문에 정확히는 4번 입니다) classification 을 하여야 합니다.
이 때 각 classification 에 이용할 수 있는 features는 potential functions 에 의하여 만들어집니다. Potential functions 에 의하여 1 의 값을 받는 features 의 개수는 매우 작습니다. Potential function 은 현재 시점이 특정한 경우인가를 판단하는 필터이기 때문입니다. 그 결과 한 시점에 대한 벡터는 대부분의 값이 0 인 sparse vector 이며, 0 이 아닌 값들은 Boolean filter 의 결과로 1 을 지닙니다.
이는 마치 5 개의 문서에 대한 term frequency vector 처럼 보이기도 합니다. Potential functions 에 의하여 feature vector 로 변형된 $x_i$ 는 이제 maximum entropy model (softmax regression) 에 입력되어 classification 이 됩니다.
Label Bias
Maximum Entropy Markov Model 의 식은 설득력이 있습니다.
$P\left(y_{1: n} \mid x_{1: n}\right)=P\left(y_1 \mid x_{1: n}\right) \times\left(\prod_{i=2: n} P\left(y_i \mid x_{1: n}, y_{i-1}\right)\right)$
그러나 위 식처럼 sequentially labeling 을 수행하면 label bias 라는 현상이 발생합니다. 아래 그림은 일본어 형태소 분 석기 MeCab 논문의 예시 그림입니다.
입력된 데이터 $x$ 의 실제 정답은 $y=[A, D]$ 였습니다. $A$ 가 자주 등장한 state 라면 이후 다른 states 들이 여러 가지 등장할 수 있습니다. 아래 그림에서는 $C$ 와 $D$ 가 $A$ 다음에 등장하였습니다. $A$ 가 frequent 하여 다른 states 로 넘어 갈 때의 확률이 분할됩니다.
하지만 infrequent state 였던 $B$ 는 언제나 $E$ 앞에 등장하였습니다. $B$ 가 state 로 이용된 적이 적어서 $P(B \rightarrow E)$ 가 높을 뿐인데, 오히려 왜곡이 생깁니다. 그 결과 $P(A, D \mid x)<P(B, E \mid x)$ 여서 잘못된 labeling 이 이뤄집니다.
From MEMM to CRF
Label bias 의 원인은 Markov Model 이 전체 그림을 보지 않고 지엽적인 정보만을 이용했기 때문입니다. Conditional Random Field 는 이 문제를 해결하기 위해 제안됩니다.
CRF 와 MEMM 의 차이는 번의 순차적인 classifications 를 수행하느냐, a sequence 에 대한 한 번의 classification 을 수행하느냐 입니다.
번의 logistic classification 이 아닌, vector sequences, 즉 matrix 에 대한 한 번의 logistic classification 입니다
'wonderland > wonderland map' 카테고리의 다른 글
| TOY (0) | 2024.02.04 |
|---|
댓글