Subword Segmetation Algorithm(BPE, Wordpiece, Unigram)

BPE(Byte Pair Encoding), Wordpiece, Unigram은 모두 텍스트 데이터를 subword로 분할하기 위한 Tokenization Algorithm이다. 하나의 단어는 더 작은 단위의 의미있는여러 서브 워드들의 조합을 구성된 것이 많기 때문에 subword tokonization 기법으로 translation 등의 여러 분야들에서 시도 중이다. Google 번역기는 이미 WPM(Word Piece Model)을 이용하여 2016년부터 사용이 되었고, Google이 무료로 오픈하여 실무에도 사용되고 있는 sentencepiece는 unigram algorithm을 사용하였다. 

---

BPE(Byte Pair Encoding) Algorithm

1994년에 '데이터 압축 알고리즘'으로 개발, 제안이 된 OpenAI에서 GPT 모델을 사전 학습할 토큰화를 위한 방법으로 사용하게 되고 이후 여러 Transformer 등의 LLM에서 사용되었다고 한다. 방식을 간단하게 말하자면 연속적으로 가장 많이 등장한 글자의 쌍(pair)을 찾아서 하나의 글자로 병합하는 방식이다. 이는 Bottom up 방식을 사용한다고도 말할 수 있는데, 글자(character) 단위의 토큰에서 단어(Vocabulary) 단위의 토큰으로 병합한다고 생각하면 이해하기 쉽다. 

---

Wordpiece

Wordpiece algorithm은 토큰화 방식이 BPE와 유사하지만 훈련 과정의 대부분에서는 다른 방식으로 수행이 된다. 또한 wordpiece 방식의 토큰은 final 값만 저장을 하게된다. 아래는 hugging face에서 제시한 예시이다. 

Tokenizing 'hugs'

Using Wordpiese algorithm : ["hug", "##s"] / Using BPE algorithm : ["hu", "##gs"]

---

Unigram Algorithm

Unigram Model은 확률기반의 모델(Probabilty-based Model)로 각 단어가 독립적으로 발생한다고 가정한다. 그렇기에 두 단어의 동시 발생은 각 단어 발생 확률의 곱이 된다. 

Unigram algorithm 초기에는 BPE 방식을 사용하여 모든 단어들의 가능한 서브워드를 생성한다. 그리고 각각의 빈도 수를 기반한 확률값을 확인하고, corpus의 손실(loss)을 최소화할 수 있는 방향으로 기본 문자에 속하지 않는(기본 어휘를 유지하기 위함) 토큰의 특정 비율(일반적으로 10~ 20%)을 제거한다.  그러면 각 단어를 가장 잘 설명할 수 있는 split된 각각의 확률 값이 존재하게 되는데, 이를 가지고 손실을 각각 구한 후 모두 더해주면 해당 단어 모음의 손실값이 된다. 이때 손실은 아래 함수의 P(word) 부분에 word에 해당하는 확률값을 넣고 구해주면 된다.

빈도 수 * ( -log(P(word)) )

이후로, 이 방식을 반복하여 손실을 적게 발생시키는 방향으로 가는 알고리즘이라고 볼 수 있다. [자세한 내용과 예시]

---