문장 임베딩 Sent2Vec과 fastText 구현

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

2018년 6월 25일 품질 평가 추가
2018년 6월 3일 초안 작성

본문

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

CBOW

3

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으로, 빈도 수 높은 단어를 학습에서 제외하여 학습 속도를 높이고 불용어 제거와 유사한 효과를 갖는다.4 랜덤 확률로 학습에서 배제하며, 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가 최소가 되도록 학습한다.

5

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 옵션으로 정할 수 있다. 대형 코퍼스 일수록 이 값을 낮출 수 있으며, 논문에는 아래와 같이 기술되어 있다.6

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이 된다.

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

deleting rare words

출현 빈도가 낮은 단어는 학습에서 배제한다. 그러나 학습 배제가 성능에는 영향을 끼치지 못한다. (Levy et al., 2015) 대신 모델 압축에는 탁월한 효과를 보인다. 언제나 그렇듯 파레토 법칙에 따라 20% 성능 감소로 80% 공간을 확보할 수 있을 것이다. 물론 그 정도로 성능을 포기할 필요는 없으며, 실혐 결과 1M 단어를 -minCount 조정으로 20만으로 압축했고, 5.4G 모델을 1.2G로 줄였으나 동일한 성능을 유지할 수 있었다. 뉴스 코퍼스는 100억개의 단어를 포함하고 있고 unique 기준으로 100만개가 있다. -minCount 200일때 이 수치는 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의 최대 거리를 뜻한다. 즉, 문장이 (A,B,C,D,E)일때,

  • -wordNgrams=3: (A), (A,B), (A,C)
  • -wordNgrams=4: (A), (A,B), (A,C), (A,D)

확장은 뒤로만 하되 이전 단어는 포함 하지 않는다. 또한 -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의 성능이 좀 더 좋은 것으로 나온적이 있다.

개선

한글 특성에 적합하도록 알고리즘을 개선했고(주어부에 추가 weighting 부여 등) n-grams에 대한 weight decaying 처리, 구문 학습, 상기 본문에 언급한 버그를 포함해 fastText의 버그라 예상되는 부분도 일부 패치했다. 이 내용들은 정리해서 PR을 보내 fastText upstream에 반영될 수 있도록 할 예정이다.

구문 학습은 word2vec 논문에도 포함된 내용으로, 예를 들어 New York Times의 경우 세 단어를 각각의 입력으로 하는게 아니라 New_York_Times 한 단어로 처리하여 성능을 높인다는 얘기다. 이 과정은 전처리를 통해 입력값으로 넣기 전에 미리 처리해두면 모델의 성능 향상에 도움이 된다.

7

평가

모델의 성능을 ‘정성적’ 평가에서 ‘정량적’ 평가로 개선하고, 이후 품질 개선 효과를 기계적으로 측정하여 점수를 통해 빠르게 개선 가능하도록 했다.

정답셋 구축으로 품질 개선에 따른 점수 변화를 DCG 처럼 매번 평가할 필요 없이 아래와 같이 빠르게 측정할 수 있다.

결과

그 결과 아래와 같은 최종 품질을 얻어낼 수 있었다.

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.