중국어의 문장에는 띄어쓰기가 존재하지 않습니다. 대신 한국어처럼 용언의 활용이 일어나지 않습니다. 그렇기 때문에 중국어의 품사 판별을 하기 위해서는 문장을 단어열로 분해하는 word segmentation 을 수행합니다. Conditional Random Field 는 학습 데이터를 이용하는 supervised word segmentation 에 적합하여 자주 이용되었습니다. 그러나 중국어에서도 미등록단어와 모호성 문제는 발생합니다. 이를 해결하기 위하여 unsupervised features 를 supervised model 에 결합하기 위한 시도들이 있었습니다. 이 포스트는 Accessor Variety 와 같은 unsupervised word extraction features 을 CRF model 에 적용하는 방법에 대한 논문인 “Incorporating Global Information into Supervised Learning for Chinese Word Segmentation” 을 리뷰합니다.

품사 판별 (Part-of-Speech tagging) 은 string 형식의 문장으로부터 [(단어, 품사), (단어, 품사), … ] 형식으로 문장을 구성하는 단어와 품사를 인식하는 문제입니다. 한 문장은 여러 개의 단어/품사열 (sequence of word and tag) 의 후보가 만들어 질 수 있으며, 품사 판별 과정에서는 가능한 단어/품사열 후보 중 가장 적절한 것을 선택해야 합니다. 이는 길이가 $n$ 인 input sequence $x_{1:n}$ 에 대하여 가장 적절한 output sequence $y_{1:n}$ 을 찾는 문제이기도 합니다. 이를 위하여 sequential labeling 이 이용될 수 있습니다. Sequential labeling 을 이용하는 초기의 품사 판별기는 Hidden Markov Model (HMM) 을 이용하였습니다. 그러나 구조적인 한계 때문에 이후에 Conditional Random Field (CRF) 가 제안된 뒤로 CRF 가 품사 판별 문제의 sequential labeling module 로 이용되었습니다. 최근에는 word embedding 을 features 로 이용하기 위하여 deep neural network 계열의 sequential labeling 방법이 이용되기도 합니다. 품사 판별기의 원리를 이해하기 위해서는 사람이 이해하기 쉬운 features 를 이용하는 CRF 기반 품사 판별기를 알아보는 것이 좋습니다. 이번 포스트에서는 CRF 를 이용하여 한국어 품사 판별기를 학습하고, 주어진 단어/품사열에 대한 적합성, score 를 계산하는 부분을 구현합니다. 단 Viterbi style 의 CRF decoding 과정은 다루지 않습니다.

Hidden Markov Model (HMM) 은 Conditional Random Field (CRF) 가 제안되기 이전에 Part of Speech tagging 과 같은 sequential labeling 에 자주 이용되던 알고리즘입니다. HMM 은 CRF 와 비교하여, unsupervised learning 도 할 수 있다는 장점이 있습니다만, tagger 를 만들 때에는 주로 학습 말뭉치를 이용합니다. 그리고 학습 말뭉치를 이용할 때에도 HMM 이 CRF 보다 빠른 학습속도를 보여줍니다. 그러나 HMM 은 단어열의 문맥을 기반으로 품사를 추정하지 못합니다. 이는 unguaranteed independence problem 이라는 HMM 의 구조적 특징 때문입니다. 이 포스트에서는 HMM 기반의 품사 판별기의 원리와 학습 방법에 대하여 이야기합니다. 단, HMM 의 unsupervised learning 과 decoding 과정에 대해서는 다루지 않습니다.

비싼 k-nearest neighbors 탐색 비용을 줄이기 위하여, 정확하지는 않더라도 빠르게 query point 와 비슷한 점들을 탐색할 필요가 있습니다. Approximated Nearest Neighbor Search (ANNS) 는 이를 위한 방법들입니다. Hash function 에 기반한 Locality Sensitive Hashing (LSH) 이 대표적이지만, network 를 이용하는 방법들도 많습니다. Small-world phenomenon 을 이용하는 방법으로 random neighbor graph 와 nearest neighbor graph 를 혼합하여 indexing 을 하는 방법이 있습니다. 이번 포스트에서는 network 의 특징을 이용하여 안정적인 성능으로 최인접 이웃을 검색하는 방법에 대하여 알아봅니다.

GloVe 는 Word2Vec 과 더불어 자주 이용되는 word embedding 방법입니다. Word2Vec 과의 차이점에 대하여 알아보고, Python 의 구현체인 glove_python 의 특징에 대해서도 살펴봅니다. 그리고 glove_python 을 이용하여 좋은 학습 결과를 얻기 위한 방법에 대해서도 이야기합니다.

Levenshtein distance 는 string 간 형태적 유사도를 정의하는 척도입니다. 만약 우리가 단어 사전을 가지고 있고, 사전에 등록되지 않은 단어가 발생한다면 Levenshtein distance 가 가장 가까운 단어로 치환함으로써 오탈자를 교정할 수 있습니다. 그러나 Levenshtein distance 는 계산 비용이 비쌉니다. 이 때 간단한 inverted index 를 이용하여 비슷할 가능성이 있는 단어 후보만을 추린 뒤 몇 번의 Levenshtein distance 를 계산함으로써 효율적으로 오탈자를 교정할 수 있습니다. 이번 포스트에서는 inverted index 를 이용하는 효율적인 Levenshtein distance 기반 오탈자 교정기를 만들어 봅니다.

단어, 혹은 문장과 같은 string 간의 형태적 유사성을 정의하는 방법을 string distance 라 합니다. Edit distance 라는 별명을 지닌 Levenshtein distance 는 대표적인 string distance metric 중 하나입니다. 그러나 Levenshtein distance 는 한국어처럼 각 글자가 요소들 (초/중/종성)로 이뤄진 언어를 고려한 metric 이 아닙니다. 이번 포스트에서는 Levenshtein distance 를 한글에 적합하도록 변형하는 방법에 대하여 알아봅니다.

Hidden Markov Model (HMM) 은 품사 판별을 위하여 이용되기도 하였습니다. 특히 앞의 한 단계의 state 정보만을 이용하는 모델을 first-order HMM 이라 합니다. 그런데 이 first-order HMM 을 이용하는 품사 판별기의 품사열은 최단 경로 문제 기법으로도 구할 수 있습니다. 이번 포스트에서는 앞선 포스트에서 다뤘던 Ford algorithm 을 이용하여 품사를 판별하는 방법에 대하여 알아봅니다.

마디 (node) 와 호 (edge) 로 표현된 그래프에서 두 마디를 연결할 수 있는 경로 (path) 는 다양합니다. 그 중 거리가 가장 짧은 경로를 찾는 문제를 최단 경로 문제, shortest path 라 합니다. 이번 포스트에서는 최단 경로를 찾는 방법 중 하나인 Ford algorithm 에 대하여 알아보고, Python 으로 이를 간단히 구현합니다.

이전에 글을 쓸 때 첨삭의 편의 때문에 Word 를 이용했습니다. 그런데 여러 명이 함께 글을 작업하다보니 버전이 꼬이는 문제가 발생했습니다. 그 때 부터 문서에 대한 버전 관리의 필요를 느끼게 되었고, 최근에 github 을 이용하여 문서 버전 관리를 하기 시작했습니다. 그 과정에서 배운 점들을 정리합니다. 조금 더 효율적인 문서의 버전 관리를 할 수 있기를 바라며 글을 공유합니다.