[AI] CRF 알고리즘 (Conditional Random Field)

*협찬
https://m.smartstore.naver.com/digshop

디그샵 : 네이버쇼핑 스마트스토어

*CRF

- 품사 판별은 string 형식의 문장으로부터 문장을 구성하는 단어와 품사를 인식하는 문제

- 품사 판별 과정에서는 가능한 단어/품사열 후보 중 가장 적절한 것을 선택해야 함

- 길이가 n인 input sequnece x 에 대하여 가장 적절한 output sequence y를 찾는 문제. sequential labeling이 이용될 수 있음

- 일반적으로 classification 이라 하면, 하나의 입력 벡터 x에 대하여 하나의 label 값 y를 return 하는 과정

- 입력되는 x가 벡터가 아닌 sequence일 때, x를 길이가 n인 sequence x = [x1, x2, ..., xn] 라 할 때, 같은 길이의 y = [y1, y2, ..., yn] 을 출력해야 하는 경우

- labeling 은 출력 가능한 label 중에서 적절한 것을 선택하는 것이기에 classification

- sequential data 에 대한 classification 이라는 의미로 sequential labeling

- 띄어쓰기 문제나 품사 판별이 대표적인 sequential labeling

- Conditional Random Field 는 sequential labeling 을 위하여 potential function 을 이용하는 softmax regression

- RNN 이 sequential labeling 에 이용되기 전에, 다른 많은 모델보다 좋은 성능을 보인다고 알려짐

- sequential labeling 은 길이가 n인 sequence 형태의 입력값 x = [x1, x2, ..., xn] 에 대하여 길이가 n 인 적절한 label sequence y = [y1, y2, ..., yn] 을 출력. argmax P(y1:n | x1:n) 로 표현할 수 있음

- softmax regression 은 벡터 x에 대하여 label y 를 출력하는 함수, 입력되는 sequence data가 단어열과 같이 벡터가 아닐 경우에는 이를 벡터로 변환해야 한다.

- potential function 은 categorical value 를 포함하여 sequence 로 입력된 다양한 형태의 값을 벡터로 변환

- potential function 은 boolean 필터처럼 작동

- 품사 판별을 위한 sequential labeling 이라면 input sequence 는 단어열이며, output sequence 는 각 단어에 해당하는 품사열

- potential functions 은 임의의 형태의 데이터라 하더라도 boolean filter 를 거쳐 high dimensional sparse boolean vector로 표현.

- Conditional Random Field는 특정 상황일 때 특정 label의 학률을 학습하는 모델

- CRF 와 비슷한 MEMM(Maximum Entropy Markov Model)

- MEMM은 label bias 문제가 발생. 이를 해결하기 위하여 CRF가 제안됨

- Consider context

- 단어열이 주어졌을 때, 한 단어 xi의 품사를 추정할 때에는 그 주변 단어들 xi-k 나 xi+k가 문맥적인 힌트가 됨

- HMM에서 xi는 yi만 그 상관성을 emisiion probability로 학습할 수 있음. xi 이전에 xi-1 에 어떤 단어가 등장하였는지 상관하지 않음. HMM은 문맥을 직접벅으로 고려하는 기능이 없음. 단지 state 간의 transition probability 인 P(yi|yi-1) 에의하여 간접적으로 단어 간 문맥이 반영되길 바람

- HMM 은 품사 판별처럼 앞, 뒤의 observation 을 함께 고려해야 하는 상황에서의 sequential labeling 에는 적합하지 않은 방법

- CRF는 앞, 뒤의 단어로 이뤄진 문맥을 직접적으로 이용

- Potential function 을 만들 때, xi-1:i+1 을 이용한다면, trigram 의 문맥에서 가운데 단어의 품사를 추정한다는 의미

- CRF는 앞/뒤에 등장하는 단어를 직접적으로 확인함으로써 특정 문맥에서의 xi의 품사를 추정할 수 있음

 

*CRF can learn context

- HMM 은 emission probability P(xi|yi), P(word|tag) 에 의하여 단어가 등장할 가능성을 계산

- 이는 학습 말뭉치에 어떤 품사 y에서 단어 x가 등장했던 확률

- 학습 말뭉치에 존재하지 않은 단어에 대해서는 emission probability가 0

- 학습 말뭉치에 존재하지 않은 단어에 대해 품사를 부여하기가 어려움

- HMM 기반 방법은 특정 단어에 대하여 임의의 emission probability 를 부여함으로써 사용자 사전을 손쉽게 추가할 수 있음

-