Subword Tokenizer

기계가 이해하지 못하는 단어는 OOV(Out of Vocabulary), UNK(Unknown Token)라고 표현한다. 어떤 NLP task를 수행하더라도, 입력된 단어에 대해 기계가 이해하지 못하면 제대로 된 성능이 나올 수 없다. 이를 OOV 문제라고 한다.

Subword segmentation은 많은 단어가 더 작은 단위의 의미있는 여러 서브워드들의 조합으로 구성된 경우가 많기 때문에, 하나의 단어를 여러개의 subword로 분리해서 encoding, embedding 하는 전처리 작업이다.

Byte Pair Encoding(BPE)

BPE는 연속적으로 가장 많이 등장한 글자의 쌍을 찾아서 하나의 글자로 병합하는 방식이다. 최초 압축 알고리즘의 용도로 사용된 만큼, byte라는 표현을 사용한다.

aaabdaaabac

이 예시에서 가장 자주 등장하는 byte 쌍은 aa이다. 이를 Z로 치환하면 아래와 같다.

ZabdZabac
Z=aa

다시, 가장많이 등장하는 byte쌍은 ab이다. 따라서 이를 Y로 치환하면 아래와 같다.

ZYdZYac
Y=ab
Z=aa

다시, 가장많이 등장하는 byte쌍은 ZY이다. 이미 치환해서 생성된 byte쌍이지만 다시 이를 X로 치환한다.

XdXac
X=ZY
Y=ab
Z=aa

이후, 병합이 가능한 쌍은 없다. 가장많이 등장하는 쌍이 없기 때문이다. XdXac가 최종 결과가 된다.

BPE in NLP

NLP에서 BPE는 subword segmentation 알고리즘으로, 기존의 단어를 분리하는 알고리즘이다. 글자 단위에서 점차적으로 단어집합을 만들어내는 Bottom up 방식으로 접근한다. train data에 있는 글자, unicode 단위로 vocabulary를 만들고, 가장 많이 등장하는 유니그램을 하나의 유니그램으로 통합한다.

📌 Unigram(유니그램)이란?
유니그램(Unigram)이란 NLP에서 사용되는 가장 단순한 언어 모델 중 하나이다. 단어의 순서를 무시하고, 각 단어가 문장에서 독립적으로 발생한다고 가정했을때, 문서 내 단어의 빈도와 분포를 분석할 수 있다.

$P_{uni}(w_1,w_2,...,w_n)=P(w_1)P(w_2)...P(w_n)$

Unimodel을 수식으로 나타내면 위와 같다. 각 단어 $w_i$의 확률을 독립적으로 곱하여 전체문장의 확률을 계산하는 방식이다.
" I love natural language processing" 이 있다고 가정하면 단어의 빈도는
I : 1
love : 1
natural : 1
language : 1
processing : 1
으로 나타낼 수 있다. 그리고 각 단어의 확률은 $\frac 1 5$이 된다.

기존 접근 방식

train data에서의 각 단어들의 빈도수를 카운트하여 딕셔너리로 정의한다. 아래와 같은 빈도수 결과가 나왔다고 예시를 들어보자.

low : 5, lower : 2, newest : 6, widest : 3

이 딕셔너리를 통해 low부터 widest까지 각 단어의 빈도수를 확인할 수 있다. 해당 data에 대한 vocabulary는 아래와 같은 결과를 가진다.

low,lower,newest,widest

하지만, lowest라는 단어가 test과정에서 등장하면 어떻게 해야할까? 기계는 해당 단어에 대해 학습한 적이 없기 때문에 OOV문제가 발생한다.

BPE 접근 방식

같은 예시를 BPE 방식으로 접근해보면 일단, 딕셔너리의 모든 단어를 글자 단위로 분리해야한다.

l o w : 5, l o w e r : 2, n e w e s t : 6, w i d e s t : 3

글자 단위로 분리한 위 딕셔너리를 참고로 초기 단어집합은 아래와 같다. 글자 단위로 분리된 vocabulary가 생성된다.

l, o, w, e, r, n, s, t, i, d

BPE 알고리즘을 몇 회 반복(iteration)할 것인지 사용자가 정하고, 그 반복 횟수동안 가장 빈도수가 높은 유니그램의 쌍을 하나의 유니그램으로 통합하는 과정을 수행한다. 아래는 반복 횟수동안 BPE 알고리즘이 수행되는 과정이다.

1회 / 빈도수 : 9 (e,s)쌍

newest가 6회, widest가 3회 빈도수를 가지기 때문에, e,s byte pair가 6+3회로 총 9회 등장한다. 이를 통합하여 vocabulary를 update한다.

• 딕셔너리

l o w : 5, l o w e r : 2, n e w es t : 6 , w i d es t : 3

• vocabulary

l, o, w, e, r, n, s, t, i, d, es

2회 / 빈도수 : 9 (es,t)쌍

newest가 6회, widest가 3회 빈도수를 가지기 때문에, es,t byte pair가 6+3회로 총 9회 등장한다. 이를 통합하여 vocabulary를 update한다.

• 딕셔너리

l o w : 5, l o w e r : 2, n e w est : 6 , w i d est : 3

• vocabulary

l, o, w, e, r, n, s, t, i, d, es, est

3회 / 빈도수 : 7 (l,o)쌍

low가 5회, lower가 2회 빈도수를 가지기 때문에, l,o byte pair가 5+2회로 총 7회 등장한다. 이를 통합하여 vocabulary를 update한다.

• 딕셔너리

lo w : 5, lo w e r : 2, n e w est : 6 , w i d est : 3

• vocabulary

l, o, w, e, r, n, s, t, i, d, es, est, lo

4회 / 빈도수 : 7 (lo,w)쌍

low가 5회, lower가 2회 빈도수를 가지기 때문에, lo,w byte pair가 5+2회로 총 7회 등장한다. 이를 통합하여 vocabulary를 update한다.

• 딕셔너리

low : 5, low e r : 2, n e w est : 6 , w i d est : 3

• vocabulary

l, o, w, e, r, n, s, t, i, d, es, est, lo, low

5회 / 빈도수 : 6 (n,e)쌍

newest가 6회 빈도수를 가지기 때문에, n,e byte pair가 총 6회 등장한다. 이를 통합하여 vocabulary를 update한다.

• 딕셔너리

low : 5, low e r : 2, ne w est : 6 , w i d est : 3

• vocabulary

l, o, w, e, r, n, s, t, i, d, es, est, lo, low, ne

6회 / 빈도수 : 6 (ne,w)쌍

newest가 6회 빈도수를 가지기 때문에, ne,w byte pair가 총 6회 등장한다. 이를 통합하여 vocabulary를 update한다.

• 딕셔너리

low : 5, low e r : 2, new est : 6 , w i d est : 3

• vocabulary

l, o, w, e, r, n, s, t, i, d, es, est, lo, low, ne, new

7회 / 빈도수 : 6 (new,est)쌍

newest가 6회 빈도수를 가지기 때문에, new,est byte pair가 총 6회 등장한다. 이를 통합하여 vocabulary를 update한다.

• 딕셔너리

low : 5, low e r : 2, newest : 6 , w i d est : 3

• vocabulary

l, o, w, e, r, n, s, t, i, d, es, est, lo, low, ne, new, newest

8회 / 빈도수 : 3 (w,i)쌍

widest가 3회 빈도수를 가지기 때문에, w,i byte pair가 총 3회 등장한다. 이를 통합하여 vocabulary를 update한다.

• 딕셔너리

low : 5, low e r : 2, newest : 6 , wi d est : 3

• vocabulary

l, o, w, e, r, n, s, t, i, d, es, est, lo, low, ne, new, newest, wi

9회 / 빈도수 : 3 (wi,d)쌍

widest가 3회 빈도수를 가지기 때문에, wi,d byte pair가 총 3회 등장한다. 이를 통합하여 vocabulary를 update한다.

• 딕셔너리

low : 5, low e r : 2, newest : 6 , wid est : 3

• vocabulary

l, o, w, e, r, n, s, t, i, d, es, est, lo, low, ne, new, newest, wi, wid

10회 / 빈도수 : 3 (wid,est)쌍

widest가 3회 빈도수를 가지기 때문에, wid,est byte pair가 총 3회 등장한다. 이를 통합하여 vocabulary를 update한다.

• 딕셔너리

low : 5, low e r : 2, newest : 6 , widest : 3

• vocabulary

l, o, w, e, r, n, s, t, i, d, es, est, lo, low, ne, new, newest, wi, wid, widest

총 10회 BPE 알고리즘 방법으로 접근했을 때, 최종적으로 dictionary와 vocabulary는 다음과 같아진다.

• 딕셔너리

low : 5, low e r : 2, newest : 6 , widest : 3

• vocabulary

l, o, w, e, r, n, s, t, i, d, es, est, lo, low, ne, new, newest, wi, wid, widest

이 vocabulary를 가지고 있는 상황에서, test데이터로 lowest라는 단어가 등장하면 원래 OOV에 해당하는 단어이지만, BPE 알고리즘에선 OOV가 아니게 된다. lowest를 글자 단위로 분할 한 후, l, o, w, e, s, t 가 되며, vocabulary를 참고하여 low와 est를 찾아낸다. lowest를 기계는 low와 est 두가지 단어로 인코딩하게 된다.

WordPiece Tokenizer

WordPiece Tokenizer는 BPE의 변형 알고리즘이다. 빈도수에 기반하여 가장많이 등장한 쌍을 병합하는 BPE 방법과 다르게, 병합되었을때 corpus의 likelihood를 가장 높이는 쌍을 병합한다. 유명한 딥러닝 모델 BERT를 훈련하기 위해 사용된 tokenizer이다. 아래는 WordPiece Tokenizer를 수행한 예시이다.

origin sentence : Jet makers feud over seat width with big orders at stake
result(wordpieces): _J et_makers_fe ud _over _seat _width _with _big _orders _at _stake

• _ : 기존에 있었던 띄어쓰기 역할
• 띄어쓰기 : subword 구분자 역할

위의 규칙을 적용해 수행 전의 결과로 돌리는 방법은 띄어쓰기를 모두 제거하고, (subword다시 합치고) _를 띄어쓰기로 바꾸는 것이다.

Reference

https://wikidocs.net/22592