About Tumblr

문장 임베딩 Sent2Vec과 fastText 구현

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

2019년 9월 21일 용어 정리
2018년 10월 14일 논문 추가
2018년 6월 25일 품질 평가 추가
2018년 6월 3일 초안 작성

본 내용은 알고리즘과 서비스 적용을 위한 실험을 바탕으로 논문을 작성했고, 제30회 한글 및 한국어 정보처리 학술대회에 발표하였습니다.

제30회 한글 및 한국어 정보처리 학술대회 http://khclt.org/

본 알고리즘을 토대로 이 기술을 SIMPSON: Similarity Inference Engine for Evaluating Semantic Similarity Between the Sentences라는 이름으로 명명했고, Kakao i Simpson 알고리즘 홍보 영상을 제작하였습니다.

서론

Sent2Vec은 논문1과 함께 fastText를 fork하여 구현까지 함께 공개2해 주목을 받고 있다. 여기서는 좋은 성능을 보이는 Sent2Vec 알고리즘과 fastText 구현에 대해 자세히 살펴보도록 한다.

먼저, Sent2Vec은 CBOW의 확장형이다. 따라서, Sent2Vec을 제대로 이해하기 위해선 CBOW에 대해 다시 한 번 제대로 살펴볼 필요가 있다.

CBOW

3

CBOW는 컨텍스트가 타겟(센터)을 갖도록 학습한다. Skipgram과 달리 전체 평균을 입력값으로 하기 때문에 단어 위치를 보지 않는 Bag of Words 형태로, 학습 속도는 빠르지만 일반적으로 Skipgram에 비해 성능은 떨어지는 것으로 알려져 있다. 다만, fastText 구현에는 평균이 아닌 각각의 개별 학습을 진행하는 형태로 구현되어 있다.

Word2Vec의 학습을 간단히 코드로 표현해보면 아래와 같다.

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에서 확인할 수 있다. 그러나, 이 코드로는 대형 코퍼스를 학습할 수 없다. 대형 코퍼스의 경우 단어 수가 매우 많기 때문에 학습 속도를 더 높여야 한다. 따라서 이를 위한 다양한 트릭이 필요하다.

서브샘플링

대표적인 기법이 서브샘플링으로, 빈도 수 높은 단어를 학습에서 제외해 학습 속도를 높여 불용어 제거와 유사한 효과를 갖게 한다.4 학습 배제는 랜덤 확률로 하며, Mikolov의 2013년 첫 논문에는 \(p_{disc}(w)=1-\sqrt{\frac{t}{f}}\)로 표기되어 있으나 이후 Word2Vec, fastText에 이르러 최종 구현은 \(p_{disc}(w)=\sqrt{\frac{t}{f}} + \frac{t}{f}\)를 사용한다.

fastText 구현은 아래와 같다.

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

이 값이 랜덤 보다 높을때 배제된다.

return rand > pdiscard_[id];

fastText의 디폴트는 \(t=10^{-5}\)이고 이 경우 \(\frac{1}{100}\) 확률로 등장하는, 빈도 수가 높은 단어가 있다면 0.032, 약 3.2%만 학습에 참여하게 된다.

네거티브 샘플링

단어가 100만개 있다고 할때 소프트맥스를 구하는 일은 연산 비용이 높기 때문에 매우 어렵다.

이 문제를 해결하기 위한 여러가지 기법이 등장했다.

Softmax-based Approaches로는 Hierarchical Softmax가 대표적이고, Sampling-based Approaches는 네거티브 샘플링이 있다. 여기서는 네거티브 샘플링을 살펴보도록 한다.

네거티브 샘플링은 타겟에 해당하는 벡터와 Dot Product의 시그모이드 로그값이 최대가 되도록 학습한다. 벡터가 유사할수록 Dot Product는 최대가 된다. 반대로 네거티브 샘플은 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.

다이나믹 컨텍스트 윈도우

컨텍스트 윈도우는 고정 값을 부여한다. 그러나 실제로는 고정 사이즈로 동작하지 않는다. -ws는 Max 윈도우 값으로, Uniform Sampling된 윈도우 사이즈가 랜덤하게 정해진다. 이 방식이 다이나믹 컨텍스트 윈도우 기법으로, 아래와 같은 형태로 실행된다. CBOW의 경우 타겟(센터) 이전과 이후, 모두에 해당하기 때문에 -ws가 5인 경우 최대 윈도우 사이즈는 아래와 같이 10이 된다.

fastText는 랜덤 시드를 사용하지 않기 때문에 데이터가 동일하다면 네거티브 샘플링과 다이나믹 컨텍스트 윈도우 사이즈는 매 번 동일한 값이 된다.

저빈도 단어 삭제

출현 빈도가 낮은 단어는 학습에서 배제한다. 학습 배제는 성능에는 영향을 끼치지 않으면서(Levy et al., 2015) 모델 압축에는 탁월한 효과를 보인다. 언제나 그렇듯 파레토 법칙에 따라 20% 성능 감소로 80% 공간을 확보할 수 있다. 여기서는 100만개 단어를 -minCount 조정으로 20만개로 압축했고, 5.4G 모델을 1.2G로 줄이면서도 동일한 성능을 유지할 수 있었다. 뉴스 코퍼스는 100억개의 단어를 포함하고 있고 유니크 기준 100만개가 있다. -minCount 200일때 이 수치는 20만으로 줄어 들었다.

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

문자 n-그램

기본적으로 fastText CBOW구현은 기존의 Word2Vec과 동일하다. 그러나 중요한 차이점이 있는데, 문자 n-그램의 지원 여부다. 이는 문자 단위로 서브워드를 추출하여 학습에 참여하는 기법이다. 모든 서브워드가 학습에 참여하기 때문에 앞서 -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를 변형한 몇 가지 기법을 도입했다.

먼저 컨텍스트 윈도우 크기를 고정 사이즈로 두지 않고 문장 전체를 커버하도록 자동으로 설정한다. 즉, 전체 문장이 7개 단어로 구성되어 있다면 컨텍스트 윈도우의 크기도 7이 된다. 컨텍스트 윈도우 크기는 문장의 단어 수와 일치한다.

이외에도 중요한 차이점으로 논문에서는 크게 두 가지를 언급한다.1

  1. CBOW는 서브샘플링을 사용한다. 서브샘플링은 n-그램 생성을 가로막고 문장 구문에서 중요한 부분을 앗아갈 수 있다. 또한 서브샘플링된 단어만 남게 되면 거리를 단축시켜 컨텍스트 윈도우 크기를 암묵적으로 증가시키는 부작용이 있다.
  2. CBOW는 다이나믹 컨텍스트 윈도우를 사용한다. 다이나믹 컨텍스트 윈도우를 사용하는 것은 중심 단어 \(w\)에서 윈도우 크기로 나눈 거리만큼 가중치를 부여하는 것과 같다. (Levy et al., 2015) 이는 Prediction Task를 Local국소화로 만들며 문장 임베딩을 위해 모든 n-그램을 조합하여 학습 하고자 하는 우리의 목표에 반한다.

따라서 Sent2Vec은 서브샘플링을 하지 않으며, 다이나믹 컨텍스트 윈도우도 사용하지 않는다. 컨텍스트 윈도우 크기는 문장의 전체 길이로 고정한다. 옵션 -t와 -ws는 무시된다. 사실상 제거 되어야 할 옵션인데 여전히 남아 있는 것은 일종의 구현상의 버그로 추측된다. 이외에도 n-그램 확장의 오버피팅을 막기 위해 -dropoutK로 n-그램 생성에 참여하는 토큰을 랜덤하게 배제한다. 다만, 이 옵션은 -wordNgrams을 2이상 지정하지 않을 경우 해당 사항이 없다.

기타 차이점

학습시 기울기 업데이트는 \(\frac{1}{size}\) 만큼 Multiply한다. 즉, CBOW가 토큰 단위로 업데이트 하는 것에 비해 Sent2Vec은 문장 길이에 비례한 만큼 업데이트 한다.

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

CBOW는 </s>를 컨텍스트에 참여시키며, Skipgram도 타겟으로 </s>를 학습에 참여시킨다. 하지만, Sent2Vec은 토큰에서 모두 제외한다.

단어 n-그램

컨텍스트 중 타겟 위치는 0으로 만들며 이를 <PLACEHOLDER>로 정한다. n-그램 확장시에는 <PLACEHOLDER> 위치도 함께 확장을 한다. -wordNgrams로 설정하는데 여기서는 전산 언어학에서 얘기하는 일반적인 n-그램의 의미가 아니라 바이그램의 최대 거리를 의미한다. 즉, 문장이 (A,B,C,D,E)로 구성될때,

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

가 된다.

확장은 뒤로만 하되 이전 단어는 포함 하지 않는다. 또한 -dropoutK에 해당하는 토큰은 확장에서 배제한다. 만약 D가 드롭아웃으로 선택 되었다면 앞서 (A,D) 대신 (A,E)가 추가된다.

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 1538
line[i] + line[j]: 26 1538
line[i] + line[j]: 26 2
line[i] + line[j]: 1538 2
line[i] + line[j]: 1538 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,758302)

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

fastText 구현

전처리

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

Sent2Vec은 서브샘플링을 하지 않는다.

학습

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

Python Bindings

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

각각의 바인딩은 아래와 같다.

  • fastText.py: 가장 먼저 출시된 파이썬 바인딩으로 인터페이스를 C++로 따로 작성한 뒤 Cython C로 연동하여 제공한다. 초기 PyPI에서 제공하는 버전이기도 하며, 현재는 페이스북에서 직접 제작한 버전으로 대체되어 관리되고 있다.
  • fastText 공식 바인딩: 페이스북에서 공식적으로 제공하는 버전이며, 앞서 언급한대로 현재 PyPI에서 관리되는 버전으로 pybind11로 구현되어 있다.
  • Gensim: 작년 여름에 Gensim에 fastText가 추가되어 화제가 됐다. GSoC 2017에서 인도의 한 학생(학부생)이 C++ 구현을 파이썬으로 통채로 구현하여 PR을 날렸고, Gensim에 추가됐다. 이후에 Gensim에서 순수 파이썬 구현을 Cython C로 제품화 가능한 수준Production-Ready으로 최적화했다.
  • pyfasttext: Yet Another 버전으로, 구현은 맨 처음에 fastText.py와 유사하다. 인터페이스를 별도 C++로 구현하고 이를 Cython C로 연동했다.

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

한국어 특성

한글 특성에 적합하도록 알고리즘을 개선했고 n-그램에 대한 Weight Decaying 처리, 구문 학습, fastText의 버그라 예상되는 부분도 일부 패치했다. 이 내용들은 기회가 되면 PR을 보내 fastText upstream에 반영될 수 있도록 할 예정이다.

주어부 가중치

우리 말은 술어부 보다 주어부에서 중요한 단어가 등장한다는 가정하에 일정 길이 이상의 단어를 지닌 문장에서 절반 지점 상위를 주어부, 하위를 술어부로 정하고 주어부 단어 벡터에 α 배율로 가중치를 적용했다. 여기서 α는 1.2-1.5 사이일때 가장 좋은 결과를 보였다.

가중치 감소

주어부에 가중치를 부여했다면 코퍼스 출현 빈도에 따라 빈도가 높은 단어에 대해서는 가중치를 감소 시켜 불용어 제거와 유사한 효과를 갖게 했다.(Levy et al., 2015)

구문 학습

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

평가 및 결과

학습 데이터

학습 데이터는 2013년 부터 2015년 까지의 모든 언론사의 뉴스를 형태소 분석한 결과로 4.5억개의 문장, 100억개의 단어, 85G 크기의 파일로 구성되어 있다. Sent2Vec은 비지도 학습 모델이므로 문장에 대한 별도의 레이블링은 진행하지 않는다.

평가

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

모델의 성능을 정량적 평가로 진행할 수 있도록 4명의 참가자가 약 2주간 5,000여개의 문장으로 구성된 테스트셋을 구축하였고, 이를 통해 모델의 성능을 기계적으로 측정할 수 있게 했다. 테스트셋에는 직접 선택한 정답 문장이 포함되어 있으며 각각 1위, 3위, 5위 내에 존재하는지 여부로 Precision at k(P@k)를 정하고 이 점수로 모델의 성능을 평가했다. 정답셋 구축으로 품질 개선에 따른 점수 변화를 DCG 처럼 매번 평가할 필요 없이 빠르게 측정하여 아래와 같이 기록을 체계적으로 남길 수 있었다.

날짜 TOP 1(P@1) TOP 3 TOP 5 특징
20180604 0.8499 0.9374 0.9597 바이그램 모델, 1/2 token weghting * 1.2, weight decaying
20180529 0.8461 0.9321 0.9562 모델 교체, minCount=100 기존 5.4G → 1.7G
20180525 0.8453 0.9335 0.9574 정답 정제, 불용어 추가
20180524 0.8027 0.9282 0.9565 odds ratio가 3 이상일때 해당 카테고리 문장을 항상 1등으로 부스팅
20180524 0.8343 0.929 0.9565 노이즈 정답 문장 제거(두 줄 질문이 각각 사용되는 오류), 제거 후에도 수치에 큰 변화 없음
20180517 0.8369 0.9312 0.9544 token weighting 적용
20180516 0.8316 0.9298 0.9539 scipy.spatial.distance.cdist metric=cosine
20180515 0.7854 0.8997 0.9271 유니그램 모델 신규 구축, 불용어 함께 처리, 유사도 계산 fasttext 기준
20180508 0.7154 0.8180 0.8501 바이그램 모델, repr. 유니그램 계산, 불용어 처리
20180424 0.7574 0.8618 0.8927 CBOW

결과

최종적으로 아래와 같은 서비스 품질을 얻어낼 수 있었다.

References

  1. Unsupervised Learning of Sentence Embeddings using Compositional n-Gram Features (Pagliardini et al., 2017) ↩ ↩2

  2. https://github.com/epfml/sent2vec ↩

  3. Word2Vec model Introduction (skip-gram & CBOW) ↩

  4. How does sub-sampling of frequent words work in the context of Word2Vec? ↩

  5. http://web.stanford.edu/class/cs224n/lectures/lecture2.pdf ↩

  6. Word2Vec Tutorial Part 2 - Negative Sampling ↩

  7. Distributed Representations of Words and Phrases and their Compositionality ↩

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 4.0.
This site design was brought from Distill.