Sequence Labeling
Speech 와 마찬가지로 Text 역시 word로 구성된 sequence data라고 할 수 있다. 그리고 sequence data에 labeling을 할 수 있다는 것은 비단 자연어처리 뿐만 아니라 생물학(유전자) 등에서도 활용 가능한 범용적인 기술이다.
즉, 위와 같이 sequential data인 text의 POS를 labeling하거나 chunk(구)를 파악하는 문제가 sequence labeling의 예라고 할 수 있다.
그리고 labeling을 일종의 classification으로 풀 수 있는데, NLP에 있어 앞뒤 단어 자체로는 품사를 결정할 수 없기 때문에 앞 단어의 품사와 뒷 품사 모두를 보고 각각의 품사를 classification해야함으로 사실상 구현이 어렵다고 할 수 있다. 그래서 필요한 것이 sequence model이다.
Probabilistic model
Hidden Markov Model
HMM은 Markov assumption에 의해 직전 N-1개 단어의 품사를 보고 현재 단어의 품사를 approximation하는 방법이다. 자세한 원리를 식으로 보는 것 보다 시각적으로 보는 것이 더 편한데,
HMM이 완성되면 위와 같이 품사 DT다음에 관사 the가 나올 확률, 부정관사 a 가 나올 확률 등이 수립되게 된다.
실제로 Implementation을 위해서는 위와 같이 table형태로 확률을 메모리에 저장하게 된다. (Python에서는 defaultdict 자료구조를 주로사용한다.)
이런 방법은 위와 같이 가능한한 모든 품사의 확률을 구함으로써 하나하나 labeling한다고 할 수 있다. 그런데 품사의 수가 많고(ex. 45개), 문장이 길수록(ex. 10단어) 연산량이 기하급수적으로 많아진다. (ex. 45^10 = 34,050,628,916,015,625)
그래서 개발된 알고리즘이 Viterbi Algorithm이다. 이 알고리즘의 목적은 마찬가지로 모든 path의 확률을 계산하는데, 이 과정에서 다른 path에서 계산된 결과를 재사용 할 수 있도록 한다. (Dynamic programming)
아래는 HMM을 구현한 Toolkit들이다.
- HTK(Cambridge Univ.) : http://htk.eng.cam.ac.uk/
- Mendel HMM Toolbox for Matlab : http://www.math.uit.no/bi/hmm/
- NLTK (Natural Language Toolkit) : http://www.nltk.org/
0 댓글