BPE(Byte Pair Encoding), WordPiece Tokenization

BPE에 대해 정리하기 전에 Tokenization에 대해 간단히 정리를 하고 넘어간다.

 

Tokenization

 Tokenization은 Text를 임의로 지정한 단위, 즉 token으로 나누는 작업이다. NLP 모델을 학습시킬 때 토큰화된 단어의 개수가 모델 성능에 다양한 영향을 미치며, 여기서 특히 Out-of-Vocabulary(OOV)는 큰 문제다.

 Tokenization은 크게 3가지 유형으로 분류한다.

 

  1. Word based Tokenizer : 말 그대로 단어 단위로 토큰화를 한다.

      - 하지만 단어 단위로 토큰화를 하면 신조어를 처리하지 못하거나 OOV와 같은 문제가 있다.

 

  2. Character based Tokenizer : 영어 기준 알파벳, 한국어 기준 초성 중성 종성 혹은 음절 단위로 토큰화를 한다.

     - sequence 길이가 상당히 길어져 vanishing gradient가 발생하기 쉽고 성능 저하의 단점이 있다.

     - 보통 Input sequence가 200이 넘어가면 성능이 현저하게 줄어든다고 한다. 

 

  3. Subword based Tokenizer : Word based와 Character based의 사이인 토큰화 방법이다.

    - 하나의 단어는 여러 subword의 조합으로 구성되는 경우가 많아 하나의 단어를 여러 subword로 분리해 단어를 임베딩하겠다는 의도이다.

    - 단어 집합의 크기를 잘 설정해주는 것이 중요하다.

    - Transformer, BERT 등에서 사용하는 방식이다.

 

 

BPE(Byte Pair Encoding)

 BPE는 OOV를 완화하는 대표적인 subword segmentation 알고리즘이며, GPT-1과 최근의 다양한 LLM에서 많이 이용하고 있는 기법이다.

  BPE는 기본적으로 연속적으로 가장 많이 등장한 글자의 쌍을 찾아서 하나의 글자로 병합하는 방식으로 수행된다. 아래의 예시 처럼 연속적인 글자(byte)의 쌍(pair)을 계속해서 찾아간다.

bytes = "aaabdaaabac"

# 가장 많이 등장하는 연속적인 글자쌍을 Z로 치환
Z = "aa"
bytes = "ZabdZabac" 

# 그 다음 가장 많이 등장하고 있는 글자쌍을 Y로 치환
Y="ab"
Z="aa"
bytes = "ZYdZYac"

# 그 다음 가장 많이 등장하고 있는 글자쌍을 X로 치환
X = "ZY"
Y="ab"
Z="aa"
bytes = "XdXac"

# 더 이상 병합할 글자쌍이 없음

 

  BPE의 동작방식을 정리하면 다음과 같다.

 

• Step1 : 학습에 이용할 텍스트 데이터를 공백(스페이스바) 기준으로 모두 쪼갠다.
• Step2 : 음절 단위로 단어집을 생성한다.
• Step3 : Step1에서 나눈 단어들을 기준으로 연결된 음절끼리의 빈도수를 센다.
• Step4 : 빈도수가 가장 높은 단어를 단어집에 추가한다.
• Step5 : Step3 ~ 4 과정을 단어집안의 단어 개수가 원하는 개수가 될 때까지 반복한다.

 Word-based Tokenization과 BPE를 비교하면 아래와 같다.

  Word-based Tokenization

# dictionary
# 훈련 데이터에 있는 단어와 등장 빈도수
low : 5, lower : 2, newest : 6, widest : 3

### Word-based Tokenization
# 단어 집합은 중복을 배제한 단어들의 집합
dictionary -> low : 5, lower : 2, newest : 6, widest : 3
voca : low, lower, newest, widest

 

  BPE

### BPE
# character 단위로 분리한 dictionary 사용
dictionary -> l o w : 5,  l o w e r : 2,  n e w e s t : 6,  w i d e s t : 3

# 10회 반복 시 dictionary
# dictionary update!
lo w : 5,
lo w e r : 2,
n e w est : 6,
w i d est : 3

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

 

 Word-based Tokenization 사용 시 lowest라는 단어가 OOV에 해당되겠지만, BPE 사용시 low와 est 두 단어로 인코딩되어 OOV에서 벗어날 수 있다.

 

 

WordPiece Tokenizer

   WordPiece Tokenizer는 BPE의 변형 알고리즘으로 Google이 사전 학습을 위해 개발한 tokenizer이다. 이 후 DitillBERT, MobileBERT, Funnel Transformers 및 MPNet과 같은 BERT 기반의 모델에서 사용되었다. BPE는 byte의 빈도수에 기반하여 쌍을 병합하는 것과 달리 병합되었을 때 Corpus 기반의 우도를 가장 높이는 쌍을 병합한다. 

    WordPiece Tokenizer는 위 수식처럼 쌍의 빈도를 각 부분의 빈도의 곱으로 나누어서 각 개별 subword들의 빈도가 낮은 쌍의 병합에 높은 우선순위를 부여한다. 

    위 BPE 예시에서 new와 est에서 est는 다른 subword와 병합되기 때문에 굳이 new와 병할할 필요가 없다. 따라서 분자에 new와 est의 병합 빈도와 new와 est가 다른 subword와 병합되는 빈도가 높다면 위 수식의 score는 낮아져 병합되지 않을 확률이 높다.