문장 임베딩 Sent2Vec과 fastText 구현

워드 임베딩이 인상적인 모습을 보여준 이후 문장 임베딩에도 다양한 시도가 있어왔다. Quoc Le가 Mikolov와 함께 연구한 Doc2Vec 부터 지금 소개하는 Sent2Vec 까지. 무엇보다 Sent2Vec은 논문과 함께 fastText를 fork하여 구현까지 함께 공개해 주목을 받고 있다. 여기서는 좋은 성능을 보이는 Sent2Vec 알고리즘과 fastText 구현에 대해 자세히 살펴보도록 한다.

2018년 6월 3일 초안 작성

본문

Sent2Vec은 논문1과 함께 fastText를 fork하여 구현까지 함께 공개2해 주목을 받고 있다. 여기서는 좋은 성능을 보이는 Sent2Vec 알고리즘과 fastText 구현에 대해 자세히 살펴보도록 한다. 먼저, Sent2Vec은 CBOW의 확장형이다. 따라서 Sent2Vec을 제대로 이해하기 위해선 CBOW를 다시 한 번 제대로 살펴볼 필요가 있다.

CBOW

CBOW는 context가 target(center)을 갖도록 학습한다. skipgram과 달리 전체 평균을 입력값으로 하기 때문에 단어 위치를 보지 않는 bag of words 형태로, 때문에 학습 속도는 빠르지만 일반적으로 skipgram에 비해 성능은 떨어지는 것으로 알려져 있다. 다만, fastText 구현에는 평균이 아닌 각각 개별 학습을 진행하는 형태로 구현되어 있으므로 추가 확인이 필요하다. 매우 단순한 형태로 코드를 표현해보면 아래와 같다.

x = np.mean(context, axis=0)
h = np.dot(W1.T, x)
u = np.dot(W2.T, h)
y_pred = softmax(u)

e = -center + y_pred

word2vec의 핵심 알고리즘을 직접 구현한 코드는 word2vec.py에서 확인할 수 있다. 그러나, 이 코드로는 대형 코퍼스를 학습할 수 없다. 대형 뉴스 코퍼스의 경우 단어 수가 매우 많기 때문에 학습 속도를 높이기 위해 다양한 트릭을 사용한다.

subsampling

대표적인 기법이 subsampling으로, 빈도 수 높은 단어를 학습에서 제외하여 학습 속도를 높이고 불용어 제거와 유사한 효과를 갖는다.3 랜덤 확률로 학습에서 배제하며, Mikolov의 2013년 첫 논문에는 로 표기되어 있으며 이후 word2vec, fastText에 이르러 최종 구현은 아래 수식을 사용한다.

fastText 구현은 아래와 같다.

real f = real(words_[i].count) / real(ntokens_);
pdiscard_[i] = std::sqrt(args_->t / f) + args_->t / f;

이 값이 랜덤 보다 높을때 discard 된다.

return rand > pdiscard_[id];

fastText의 디폴트는 이고 이 경우 확률로 등장하는 빈도 높은 단어가 있다면, 0.032. 약 3.2%만 학습에 참여하게 된다.

negative sampling

1M 단어의 softmax를 구하는 것은 연산 비용이 높기 때문에 매우 어려운 일이다. 이 문제를 해결하기 위한 여러가지 기법이 등장했으며, softmax-based approaches로는 hierarchical softmax가 대표적이고 여기서는 sampling-based approaches인 negative sampling를 살펴보도록 한다.

negative sampling은 target에 해당하는 벡터와 dot product의 시그모이드 로그값이 최대가 되도록 학습하며(벡터가 유사할수록 dot product는 최대값이 되므로), 반대로 negative samples는 dot product가 최소가 되도록 학습한다.

4

real score = sigmoid(wo_->d(wo_->dotRow(hidden_, target));

if (label) {
    return -log(score);
} else {
    return -log(1.0 - score);
}

일반적으로 CBOW는 5, skipgram은 10 정도를 사용하며, -neg 옵션으로 정할 수 있다. 대형 코퍼스 일수록 이 값을 낮출 수 있으며, 논문에는 아래와 같이 기술되어 있다.5

The paper says that selecting 5-20 words works well for smaller datasets, and you can get away with only 2-5 words for large datasets.

dynamic context window

context window는 고정 값을 부여한다. 그러나 실제로는 고정 사이즈로 동작하지 않는다. -ws는 max window 값으로 uniform sampling된 window 사이즈가 랜덤하게 정해진다. 이는 dynamic context window 기법으로 아래와 같은 형태로 실행된다. CBOW의 경우 target(center) 이전과 이후 모두에 해당하기 때문에 -ws가 5인 경우 최대 윈도우 사이즈는 아래와 같이 10이 된다.

token: 거래목적 wid: 1730
token: 또는 wid: -1
token: 자금원천을 wid: 1731
token: '기타'로 wid: 1732
token: 선택할 wid: 145
token: 경우 wid: 24
token: '심사후 wid: 1733
token: 개설'이라고 wid: 1734
token: 표시되어 wid: 1735
token: 있는데 wid: 74
token: 어떤 wid: 33
token: 내용을 wid: 1736
token: 심사하는 wid: 1737
token: 건가요? wid: 432
token: </s> wid: 0
token.size(): 13(1730,1731,1732,145,24,1733,1734,1735,74,33,1736,1737,432)
target: 1730 bow size: 4
target: 1731 bow size: 5
target: 1732 bow size: 2
target: 145 bow size: 4
target: 24 bow size: 6
target: 1733 bow size: 2
target: 1734 bow size: 6
target: 1735 bow size: 10
target: 74 bow size: 8
target: 33 bow size: 2
target: 1736 bow size: 6
target: 1737 bow size: 5
target: 432 bow size: 4

fastText는 random seed를 사용하지 않기 때문에 데이터가 동일하다면 negative sampling과 dynamic context window 사이즈는 매 번 동일한 값이 된다.

deleting rare words

출현 빈도가 낮은 단어는 학습에서 배제한다. 그러나 학습 배제가 성능에는 영향을 끼치지 못한다. (Levy et al., 2015) 대신 모델 압축에는 탁월한 효과를 보인다. 언제나 그렇듯 파레토 법칙에 따라 20% 성능 감소로 80% 공간을 확보할 수 있다. 물론 그 정도로 성능을 포기할 필요는 없으며, 실혐 결과 1M 단어를 -minCount 조정으로 20만으로 압축했고, 동일한 성능을 유지할 수 있었다.

모델 크기가 줄면 로딩 시간이 줄어들며 추론 또한 훨씬 짧은 시간에 가능하다. 뿐만 아니라 모델을 모두 메모리에 올려야 하는 특성상 크기는 매우 중요하다. 파이썬은 성능 개선을 위해 멀티 프로세스를 띄우는 방법이 일반적이므로 메모리 점유는 매우 중요한 이슈다. gensim은 mmap을 지원해 프로세스간 메모리를 공유할 수 있도록 지원하나 fastText는 그렇지 못하다. 따라서 프로세스당 모델 사이즈 만큼의 메모리를 점유하므로 불필요한 사이즈를 줄여나가는 일은 무척 중요하다.

character n-grams

기본적으로 fastText CBOW구현은 기존의 word2vec과 동일하다. 그러나 중요한 차이점이 있다. character n-grams 지원인데, 이는 char 단위로 subwords를 추출하여 학습에 참여하는 기법이다. 모든 subwords가 학습에 참여하기 때문에 앞서 -ws 5일때 bow size가 30 가까이 늘어나기도 한다. 아래 결과와 같이 영어에서는 다양한 변형을 학습할 수 있는 장점이 있으나 한글의 경우 조합 가능한 문자의 수가 매우 많기 때문에 이 기법은 적절하지 않다. -minn 0 -maxn 0으로 비활성화 할 수 있다.

nearest neighbors using subword information:

Query word? accomodation
accomodations 0.96342
accommodation 0.942124
accommodations 0.915427
accommodative 0.847751
accommodating 0.794353
accomodated 0.740381
amenities 0.729746
catering 0.725975
accomodate 0.703177
hospitality 0.701426

nearest neighbors obtained without no subwords:

Query word? accomodation
sunnhordland 0.775057
accomodations 0.769206
administrational 0.753011
laponian 0.752274
ammenities 0.750805
dachas 0.75026
vuosaari 0.74172
hostelling 0.739995
greenbelts 0.733975
asserbo 0.732465

이제 Sent2Vec의 기존 CBOW와 차이점을 살펴보도록 한다.

Sent2Vec

Sent2Vec은 단어가 아닌 문장 단위 학습의 의미를 살리기 위해 CBOW를 변형한 몇 가지 기법을 도입했다. 먼저 context window 크기를 고정 사이즈로 정한 것과 달리 문장 전체를 커버하도록 크기를 자동으로 설정한다. 즉, 전체 문장이 7개 단어로 구성되어 있다면 context window의 크기도 7이 된다. context window의 크기는 문장의 단어 수와 일치한다. 이외에도 중요한 차이점으로 논문에서는 크게 두 가지를 언급한다.1

  1. CBOW는 subsampling을 사용한다. subsampling은 n-grams 생성을 가로막고 문장 구문에서 중요한 부분을 앗아갈 수 있다. 또한 subsampled words만 남게 되면 거리를 단축시켜 context window 크기를 암묵적으로 증가시킨다.
  2. CBOW는 dynamic context window를 사용한다. dynamic context window를 사용하는 것은 포커스 단어 에서 윈도우 크기로 나눈 거리만큼 weighting 하는 것과 같다. (Levy et al., 2015) 이는 prediction task를 local국소화로 만들며 문장 임베딩을 위해 모든 n-grams를 조합하여 학습 하고자 하는 우리의 목표에 반한다.

따라서 Sent2Vec은 subsampling을 하지 않으며, dynamic context window도 사용하지 않는다. context window 크기는 문장의 전체 길이로 고정한다. 옵션 -t-ws는 무시된다. 혼동을 막기 위해 아예 제거되어야 할 옵션인데 남아 있는 것은 일종의 구현상의 버그로 추측된다. 이외에도 ngram 확장의 오버피팅을 막기 위해 -dropoutK로 ngram 생성에 참여하는 토큰을 랜덤하게 배제한다. 다만, 이 옵션은 -wordNgrams을 2이상 지정하지 않을 경우 해당 사항이 없다.

기타 차이점

학습시 기울기 업데이트는 1/context size 만큼 multiply한다. 즉, CBOW가 토큰 단위로 업데이트 하는 것에 비해 Sent2Vec은 문장 길이에 비례한 만큼 업데이트 한다.

if (args_->model == model_name::sup || args_->model == model_name::sent2vec) {
    grad_.mul(1.0 / input.size());
}

CBOW는 </s>를 context에 참여시키며, skipgram도 target으로 </s>를 학습에 참여시킨다. Sent2Vec은 토큰에서 모두 제외한다.

word n-grams

context 중 target 위치는 0으로 만들며 이를 <PLACEHOLDER>로 정한다. ngram 확장시에는 <PLACEHOLDER> 위치도 함께 확장을 한다. -wordNgrams로 설정하는데 여기서는 전산 언어학에서 얘기하는 일반적인 ngram의 의미가 아니라 bigram의 최대 거리를 뜻한다. 즉, -wordNgrams가 3이고 문장이 (A B C D E)라면, 자기 자신 A를 포함해 (A,B), (A,C) 두 개를 더 추가하는 형태다. 만약 4라면 (A,B), (A,C), (A,D) 3개를 더 추가한다. 확장은 뒤로만 하되 이전 단어는 포함 하지 않는다. 또한 -dropoutK에 해당하는 토큰은 확장에서 배제한다. 만약 D가 dropout으로 선택 되었다면 앞서 (A,D) 대신 (A,E)가 추가된다. 그런데 ngram 확장이 (0,2), (0,6) 일때 마지막 (0,6)이 (2,6)과 같은 값을 갖는걸 확인할 수 있었다. 이는 hash collision으로 일종의 버그로 추측되며, 3 이상일때 문제가 발생한다.

token: 입출금/카드결제 wid: 14
token: 알림 wid: 17
token: 서비스 wid: 26
token: 결제계좌변경은 wid: 1538
token: 어떻게 wid: 2
token: 하나요? wid: 6
line.size(): 6(14,17,26,1538,2,6)
...
line[i] + line[j]: 14 17
line[i] + line[j]: 14 26
line[i] + line[j]: 17 26
line[i] + line[j]: 17 0
line[i] + line[j]: 26 0
line[i] + line[j]: 26 2
line[i] + line[j]: 0 2
line[i] + line[j]: 0 6
line[i] + line[j]: 2 6
line[i]: 1538 context size: 15(14,17,26,0,2,6,692956,1780052,841078,711288,1285391,888413,1747,100493,100493)

-bucket으로 지정한 값의 모듈라 연산으로 hash를 생성한다. 기본값이 2M이므로 만약 그대로 사용한다면 ngram 2백만개 이상은 hash collision이 발생할 것으로 예상할 수 있다. 따라서 초대형 코퍼스는 이 값을 늘려주어야 한다. 그러나 -minCount 이하는 아예 토큰 생성에서 배제되므로 ngram에도 참여하지 못한다. 따라서 초대형 코퍼스라도 minCount를 조정한다면 bucket이 부족하진 않을 것으로 예상된다.

fastText 구현

Pre-processing

word2int_[h]의 값 wid는 단어의 출현 빈도 순으로 정렬된다. 즉, 1일때 가장 많이 노출된 단어이며 CBOW에서 subsampling 확률이 가장 낮다. 뒷 부분 단어들은 앞서 subsampling 수식에 따라 확률이 1이 넘기 때문에 항상 학습에 참여한다. 함수 threshold()가 실행될때 빈도순 정렬이 이뤄지며 이 함수는 또한 -minCount 이내인 토큰을 삭제하는 역할을 담당 하기도 한다. Sent2Vec은 subsampling을 하지 않는다.

학습

-lrUpdateRate는 학습 진행 상황을 표시할 토큰의 단위다. 디폴트는 100이며, 100개의 토큰이 학습될 때 마다 진행 상황이 갱신된다. 로그 파일이 상당히 커질 수 있으므로, 대형 코퍼스인 경우 1000이상으로 설정해도 충분하다.

Python bindings

참고로 현재 fastText의 파이썬 바인딩은 총 4가지나 된다. 맨 처음 fastText가 출시될때 언어별 바인딩 없이 C++ 버전으로만 출시됐기 때문이다. 애당초 SWIG로 각 언어별 바인딩을 지원한 TensorFlow와는 달리 파이썬 바인딩이 뒤늦게 추가되어 구현이 제각각이다. 다행히 이제는 페이스북에서도 직접 공식 바인딩을 제공한다. 각각의 바인딩은 아래와 같다.

  • fastText.py: 아마 가장 먼저 출시된 파이썬 바인딩이며, 인터페이스를 C++로 따로 작성한 뒤 Cython C로 연동하여 제공한다. 원래 pypi 버전이었는데 지금은 페북에서 제작한 버전으로 대체되어 페북에서 직접 관리한다.
  • fastText 공식 바인딩: 현재 pypi에서 관리되는 버전이고 pybind11로 구현되었다.
  • gensim: 작년 여름에 gensim에 fastText가 추가되어 화제가 됐다. GSoC 2017에서 인도의 한 학생(학부생)이 C++ 구현을 파이썬으로 통채로 구현하여 PR을 날렸고, gensim에 추가됐다. 이후에 gensim에서 순수 파이썬 구현을 Cython C로 최적화했다.
  • pyfasttext: yet another 버전인데, 구현은 맨 처음에 fastText.py와 유사하다. 인터페이스를 별도 C++로 구현하고 이를 Cython C로 연동했다.

현재 pypi에서 제공되는 파이썬 바인딩은 2가지 이고, 페북 공식 버전(fastText)은 pybind11 C++ 버전, pyfasttext는 Cython C 버전이라는 차이가 있다. pybind11 또는 Cython 구현이라는 차이가 있는데, 예전에 실험 결과 Cython의 성능이 좀 더 좋은 것으로 나온적이 있다.

References

is a collection of Papers I have written.
© 2000 - Sang-Kil Park Except where otherwise noted, content on this site is licensed under a CC BY-NC 4.0.
This site design was brought from Distill.