Byte Pair Encoding(BPE) tokenizer 정리

1. SubWord Tokenizer

 

일반적으로 토큰화(Tokenizer)는 의미를 가진 토큰(단어 등)으로 쪼개서 토큰을 만드는 작업을 말합니다. 토큰화의 목적은 텍스트를 모델이 이해할 수 있는 데이터로 만들어주는 것입니다. 텍스트를 토큰화하는 방법은 크게 3가지로 분류할 수 있습니다.

 

1. 단어 기반 토큰화(Word-based tokenization)

• 공백을 기준으로 토큰화하는 방법('나는 밥을 먹었다' -> '나는', '밥을', '먹었다')
• 매우 간단한 아이디어지만, 훈련에 사용하지 않은 새로운 단어에 대해 대처가 어려운 단점이 존재한다.(Out of Vocabulary)

 

2. 문자 기반 토큰화(Character-based tokenization)

• 텍스트의 구성요소인 문자 단위로 토큰화하는 방법('I Love you' -> 'I', 'L', 'o', 'v', 'e' , 'y', 'o', 'u')
• 단어 기반 토큰화와는 다르게 새로운 단어에 대처하기는 쉽지만, 직관적이지 않으며 각 토큰의 의미를 파악하기 어렵다.
• 하나의 단어를 N개의 토큰으로 쪼개기 때문에 메모리가 많이 필요하다는 단점이 존재한다.

 

3. 하위단어 토큰화(Subword-based tokenization)

• 자주 사용하는 단어는 쪼개지 않고, 자주 사용하지 않은 단어를 의미있는 하위 단어로 쪼개는 방법(예를 들어 'token'이라는 단어가 'tokenization'보다 훨씬 자주 사용되고 있는 상황이라면, 'tokenization'을 'token'과 'ization'으로 쪼갠다)
• 단어 기반 토큰화에 비해서는 Out of Vocabulary 문제에 유연하게 대처할 수 있으며, 문자 기반 토큰화에 비해서는 메모리가 덜 필요하다는 장점이 존재한다.
• BERT,GPT2,Electra 등의 LLM에서 하위 단어 토큰화를 채택해서 사용한다.

이번 포스트에서는 하위 단어 토큰화 중 BPE tokenizer에 대해서 정리하고자 합니다.

 

2. 바이트 페어 인코딩 토크나이저(BPE,Byte Pair Encoding) Tokenizer

Byte Pair Encoding(이하 BPE) tokenizer는 대표적인 subword tokenizer입니다. BPE는 정보 압축 알고리즘으로써 연속적으로 빈번하게 출현하는 문자를 하나로 묶어서 표현하는 방법입니다.('abcdab' -> (ab가 가장 많이 출현!) -> (Z로 치환) -> 'ZcdZ') 이러한 방법을 활용하여 토큰화를 진행합니다. 이러한 방식과 유사하게 NLP에서 토큰화를 진행합니다. 다만 차이점은 BPE는 하나의 텍스트에서 크기를 줄여나가는 방식이지만, NLP에서는 우선 모든 단어를 쪼갠 다음에 묶어 나가는 Bottom-up 방식으로 진행됩니다.

 

2.1 BPE Tokenizer의 작동방식

BPE Tokenizer는 Normalization 및 pre-tokenization이 완료된 이후에 토큰화를 시작한다. 한국어로 치면 BPE tokenizer를 사용하기 전, 형태소 분석기를 사용한다는 뜻이다. 이렇게 사전 작업을 마치고 본격적으로 BPE tokenizer를 실행한다. 

 

예를 들어 사전 작업 이후 코퍼스에 포함된 단어들이 아래와 같다고 가정해 봅니다.

"hug", "pug", "pun", "bun", "hugs"

 

우선 이 단어들을 문자 단위로 쪼개주고 구성하고 있는 모든 문자를 모아보면 ["b", "g", "h", "n", "p", "s", "u"]가 됩니다. 이 문자들을 이용해서 코퍼스에 있는 모든 단어를 표현할 수 있습니다. 이제 각 단어들의 빈도수가 다음과 같다고 가정해 봅니다.

 

Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug"]
Corpus(word, frequency) : ("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)

 

이제 위 단어들은 문자 단위로 쪼갠 다음에, 빈도수와 같이 표현하면 다음과 같이 표현할 수 있습니다.

Corpus : ("h" "u" "g", 10), ("p" "u" "g", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "u" "g" "s", 5)

 

이제 각 연속적으로 출현하는 문자쌍을 비교할 차례입니다. 가장 처음 나오는 'h'와 'u'를 먼저 살펴보겠습니다. 'h'와 'u'가 연속적으로 나오는 단어는 'hug'와 'hugs'이며, 각각 10번 5번 나왔으므로 'h'와 'u'가 연속적으로는 15번 출현하였다고 볼 수 있습니다. 이러한 방식으로 모든 연속적으로 출현하는 문자쌍을 살펴보게 되면 'u'와 'g'가 20번(hug : 10 + pug :5 + hugs : 5)으로 가장 많이 출현하였음을 알 수 있습니다. 처음에 BPE tokenizer는 문자 단위로 쪼갠 다음에 묶어나가는 bottom-up 방식이라고 했던 부분을 기억하시나요? 이 묶어 나가는 방식이 여기에서 사용됩니다. 즉, 가장 자주 출현하는 문자 쌍에 대해서 우선적으로 병합하므로 첫 번째 병합 규칙은 ('u', 'g') -> 'ug'가 되게 됩니다. 이제 병합된 'ug'를 vocabulary에 추가해 줌과 동시에 corpus에서 'u'와 'g'를 합쳐준 뒤 적용해 줍니다.

Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug"]
Corpus: ("h" "ug", 10), ("p" "ug", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "ug" "s", 5)
첫 번째 병합 규칙 : ('u', 'g') -> 'ug'

 

이제 'ug'를 포함해서 가장 많이 연속적으로 출현하는 문자쌍을 찾아보면 'u'와 'n'이 16번(pun : 12 + bun : 4로 가장 많습니다. 따라서 두 번째 병합 규칙은 ("u", "n") -> "un"가 됩니다. 이를 전과 똑같이 적용하면 다음과 같습니다.

Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug", "un"]
Corpus: ("h" "ug", 10), ("p" "ug", 5), ("p" "un", 12), ("b" "un", 4), ("h" "ug" "s", 5)
첫 번째 병합 규칙 : ('u', 'g') -> 'ug'
두 번째 병합 규칙 : ('u', 'n') -> 'un'

 

위와 같은 방법을 계속하게 된다면 결국 문자단위로 쪼개기 전의 상태로 돌아가게 됩니다. 따라서 계속 합치는 것이 아니라 원하는 Vocabulary의 수가 될 때까지 반복하게 됩니다. 예를 들어 len(Vocabulary) = 10으로 설정하게 된다면, 현재까지 vocabulary에 포함된 문자의 개수가 9이므로 한번 더 병합을 진행해야 합니다. 한번 더 진행하게 되면 최종적으로 원하는 토큰은 다음과 같이 만들어집니다.

Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug", "un", "hug"]
Corpus: ("hug", 10), ("p" "ug", 5), ("p" "un", 12), ("b" "un", 4), ("hug" "s", 5)
첫 번째 병합 규칙 : ('u', 'g') -> 'ug'
두 번째 병합 규칙 : ('u', 'n') -> 'un'
세 번째 병합 규칙 : ('h', 'ug') -> 'hug'

 

따라서 BPE tokenization을 수행하게 되면 'hug'는 그대로 ('hug')로 토큰화가 되며, 'bun'은 ('b', 'un')으로 토큰화가 됩니다.

지금까지 BPE tokenization의 동작 방법에 대해서 정리하였습니다. 다시 BPE Tokenizer에 대해서 간단히 정리하면 BPE tokenization은 모든 코퍼스를 문자 단위로 쪼갠 다음, 연속적으로 출현하는 문자 쌍의 빈도를 계산하여 가장 많이 출현하는 연속적인 문자쌍을 우선적으로 병합해 가는 토큰화 방법이며, 사용자가 원하는 vocabulary의 개수를 만족할 때까지 병합을 계속 반복하는 알고리즘이라고 정리해 볼 수 있습니다.

 

Question?

만약 새로운 단어 'aug' 혹은 'unhug'가 새로운 입력으로 들어온다면 어떻게 될까요?

 

1. 'aug'의 경우

우선, 'aug'를 문자 단위로 쪼개보면 'aug' -> ('a', 'u', 'g')가 됩니다. 여기서 첫 번째 병합 규칙에 따라 'u'와 'g'가 병합될 수 있습니다. 따라서 ('a', 'ug')로 병합되게 됩니다. 이후, 'a'라는 문자는 vocabulary에 존재하지 않으므로 병합할 수 없습니다. BPE에서는 vocabulary에 존재하지 않는 subword는 '[UNK]'로 처리하므로 ('[UNK]', 'ug')로 토큰화가 진행됩니다.

 

토큰화 결과 : ('[UNK]', 'ug')

 

2. 'unhug'의 경우

'unhug'도 마찬가지로 문자 단위로 쪼개주게 되면 ('u', 'n', 'h', 'u', 'g')로 쪼개집니다. 병합 시 주의할 점은 병합 규칙에 우선순위가 있다는 점입니다. ('u', 'n', 'h', 'u', 'g')에서 첫 번째 병합 규칙 : ('u', 'g') -> 'ug'를 적용하면 ('u', 'n', 'h', 'ug')가 되며, 다음 두 번째 병합규칙 : ('u', 'n') -> 'un'을 적용하면 ('un', 'h', 'ug')가 되며, 마지막 세 번째 병합 규칙도 적용할 수 있으므로, 최종적으로 토큰화 결과 ('un', 'hug')로 토큰화가 진행됨을 알 수 있습니다.

 

토큰화 결과 : ('un','hug')

 

다음으로는 Python을 이용하여 BPE tokenizer를 구현해 보도록 하겠습니다.

 

3. BPE Tokenizer 구현하기

이번 챕터에서는 BPE tokenizer를 구현해 보도록 하겠습니다. 사용하는 텍스트는 다음과 같습니다.

"This is the Hugging Face course."
"This chapter is about tokenization."
"This section shows several tokenizer algorithms."
"Hopefully, you will be able to understand how they are trained and generate tokens."

 

앞서 BPE tokenizer는 Normalize 혹은 Pre-tokenization을 수행하고 사용한다고 언급했던 부분을 기억하시나요?  GPT-2에서 사용된 BPE 토크나이저를 구현하고 있으므로 사전 토큰화(pre-tokenization)에 gpt2 토크나이저를 사용합시다.

 

from transformers import AutoTokenizer

tokenizer = AutoTokenizer.from_pretrained("gpt2")

 

다음으로는 준비한 텍스트에 대해 간단히 전처리로 대문자를 소문자로 변경해 주었습니다.

#코퍼스를 입력 후, 소문자로 바꿔주기
corpus = [
    "This is the Hugging Face course.",
    "This chapter is about tokenization.",
    "This section shows several tokenizer algorithms.",
    "Hopefully, you will be able to understand how they are trained and generate tokens.",
]
corpus = [c.lower() for c in corpus]
#print(corpus)

 

이제 pre-tokenization을 수행해 줍니다.

#사전 토큰화를 진행하면서 각 단어의 빈도수를 계산하기
#'Ġ'이라고 되어 있는거는 공백을 Byte로 Encoding한 결과

from collections import defaultdict

word_freqs = defaultdict(int)

for text in corpus:
    #pre-tokenize를 수행
    #범위별로 어디부터 어디까지가 하나의 토큰인지 표현해준다
    #Example) 'this is' -> ('this', (0, 4)), ('Ġis', (4, 7)))
    #여기서 Ġ은 '공백(띄어쓰기)'을 의미한다
    words_with_offsets = tokenizer.backend_tokenizer.pre_tokenizer.pre_tokenize_str(text)
    
    #단어만 추출한다.
    new_words = [word for word, offset in words_with_offsets]
    #defaultdict를 이용하여 각 단어의 출현 횟수를 기록한다.
    for word in new_words:
        word_freqs[word] += 1

#print(word_freqs)

 

이렇게 pre-tokenize 된 결과를 이용하여 word_freqs에 들어있는 단어를 이루고 있는 문자가 무엇인지 뽑아줍니다. 여기에는 특수문자 및 문장기호 그리고 공백(Ġ)이 포함될 수 있습니다.

#위에서 진행한 pre-tokenization 결과를 이용하여 unique한(단어를 이루고 있는) 기본 vocabulary를 모은다.

alphabet = []

for word in word_freqs.keys():
    for letter in word:
        if letter not in alphabet:
            alphabet.append(letter)
alphabet.sort()

#print(alphabet)
#[',', '.', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k', 'l', 'm', 'n', 'o', 'p', 'r', 's', 't', 'u', 'v', 'w', 'y', 'z', 'Ġ']

 

다음으로는 위에서 추출한 기본 문자 모음집(vocabulary)의 시작 부분을 알 수 있도록 특수토큰을 추가합니다. GPT-2의 경우에는 "<|endoftext|>"를 사용합니다.

#모델이 문장의 입력이 어디인지 알 수 있도록 특수토큰을 추가해준다.
#GPT의 경우에는 <|endoftext|> 라고 한다.
vocab = ["<|endoftext|>"] + alphabet.copy()

 

이제 vocabulary를 만들었으면, 각 단어를 문자별로 나눠주는 작업을 진행합니다. 예를 들어 "This"의 경우에는 ["T", "h", "i", "s"]가 되며, splits 변수에는 {"This" : ['T', 'h', 'i', 's']} 형태로 저장됩니다.

 

#위에서 구성한 기본 vocabulary를 이용하여 단어를 개별 문자로 분리해준다.
splits = {word: [c for c in word] for word in word_freqs.keys()}
print(splits)

 

이제 토큰을 문자별로 분리하였으니까 각 연속된 문자가 얼마나 자주 출현하였는지 알아야 합니다. 각 연속된 문자 쌍의 출현 빈도를 계산하기 위해 아래의 'compute_pair_freqs' 함수를 작성합니다. 처음 작성한 단어별 출현 빈도가 저장되어 있는 word_freqs 변수와 문자로 쪼갠 결과가 저장되어 있는 'splits' 변수를 이용하여 연속된 각 문자열이 얼마나 많이 출현하였는지 기록합니다.

#개별 단어의 조합의 갯수를 모아본다.
#This : 3 -> (t,h) 3 ,(h,i) 3, (i,s) 3
def compute_pair_freqs(splits):
    pair_freqs = defaultdict(int)
    for word, freq in word_freqs.items():
        split = splits[word]
        if len(split) == 1:
            continue
        for i in range(len(split) - 1):
            pair = (split[i], split[i+1])
            pair_freqs[pair] += freq
    return pair_freqs


pair_freqs = compute_pair_freqs(splits)

#상위 5개만 어떤식으로 되었는지 보여주기
for i, key in enumerate(pair_freqs.keys()):
    if i < 5 :
      print(f"{key}: {pair_freqs[key]}")
    else:
      break

 

 

위 코드를 실행시킨 결과는 다음과 같습니다.

('t', 'h'): 6 ('h', 'i'): 3 ('i', 's'): 5 ('Ġ', 'i'): 2 ('Ġ', 't'): 7

 

'this'에서의 'is'와 'Ġis'에서의 'is'의 각 출현 빈도가 합쳐져서 5(3+2)로 빈도수가 계산되었음을 확인할 수 있습니다.

 

이제 각 연속된 문자열의 출현빈도를 알았으니 다음으로 할 작업은 이를 기반으로 사용자가 설정한 vocabulary의 개수가 채워질 때까지 병합을 해 줄 차례입니다. 병합은 출현빈도가 가장 높은 문자 쌍부터 진행합니다.  우선은 가장 많이 출현한 문자 쌍과 그 빈도가 무엇인지 구해봅니다.

 

#가장 자주 나오는 쌍을 발견하고,빈도수를 max_freq로 설정한다.
best_pair = ""
max_freq = None

for pair, freq in pair_freqs.items():
    if max_freq is None or max_freq < freq:
        best_pair = pair
        max_freq = freq

print(best_pair, max_freq)

 

위 코드를 실행시켜 보면 다음과 같이 출력이 됩니다.

 

('Ġ', 't') 7

 

가장 많이 출현하는 문자 쌍은 'Ġ'와 't' 이므로 이 둘을 가장 처음 병합해야 합니다. 병합 전후는 다음과 같이 merges 변수에 저장해 주며, 병합하였으니까 vocab 변수에 병합 후의 문자를 추가해 줍니다.

merges = {("Ġ", "t"): "Ġt"} #병합 이전의 개별 문자와 병합 이후의 문자를 알려준다.
vocab.append("Ġt") #G'과 t는 이제 하나의 문자로 취급하므로 vocab에 추가해준다.

 

이제 splits에 쪼개져있는 단어를 합칠 차례입니다. 입력으로 두 개의 문자열과 splits를 넣으면, splits에 들어있는 모든 문자쌍에 loop를 돌면서 해당하는 두 문자열을 하나로 합쳐줍니다.

#병합이 될 문자를 알려주면, 개별로 쪼개져있던 문자열중에 합쳐할 단어는 모두 합쳐준다.
#즉, Ġtrained -> ['Ġ','t', 'r', 'a', 'i', 'n', 'e', 'd'] -> ['Ġt', 'r', 'a', 'i', 'n', 'e', 'd']
def merge_pair(a, b, splits):
    for word in word_freqs:
        split = splits[word]
        if len(split) == 1:
            continue

        i = 0
        while i < len(split) - 1:
            if split[i] == a and split[i + 1] == b:
                split = split[:i] + [a + b] + split[i + 2 :]
            else:
                i += 1
        splits[word] = split
    return splits


splits = merge_pair("Ġ", "t", splits)
#print(splits["Ġtrained"])
#>>>['Ġt', 'r', 'a', 'i', 'n', 'e', 'd']

 

이제 위의 방식을 우리가 원하는 vocab의 크기에 만족할 때까지 같은 작업 반복하면서 문자열을 병합해야 합니다. 여기서는 vocab_size = 50으로 설정합니다. 

#BPE방식은 vocab size에 도달할 때 까지 병합을 계속하므로, 최대 사이즈를 정해놓고 계속 병합해나간다.
#만약 최대 size를 정하지 않는다면, 모든 병합을 할 테니까 다시 원래 단어로 돌아가게된다.(개별 문자로 나눈 이유가 사라짐)
vocab_size = 50

while len(vocab) < vocab_size:
    pair_freqs = compute_pair_freqs(splits)
    best_pair = ""
    max_freq = None
    for pair, freq in pair_freqs.items():
        if max_freq is None or max_freq < freq:
            best_pair = pair
            max_freq = freq
    splits = merge_pair(*best_pair, splits)
    merges[best_pair] = best_pair[0] + best_pair[1]
    vocab.append(best_pair[0] + best_pair[1])

 

위 코드를 실행시키면 병합 규칙과 size를 50으로 설정해 둔 vocab이 저장되게 됩니다. 그렇다면 이 결과를 이용하여 새로운 텍스트에 대해 토큰화를 진행할 수 있습니다. 아래 코드는 새로운 텍스트에 대해 예제 문장으로 만든 토큰화 규칙을 적용해 볼 수 있는 함수입니다.

#위의 과정들을 하나의 함수로 정리하면 다음과 같이 정리할 수 있다.
#과정은 모두 동일하다.
#위에서 사용한 병합규칙을 활용하여 새로운 문장에 대해서 토큰화를 진행할 수 있다.
def tokenize(text):
    pre_tokenize_result = tokenizer._tokenizer.pre_tokenizer.pre_tokenize_str(text.lower())
    pre_tokenized_text = [word for word, offset in pre_tokenize_result]
    splits = [[l for l in word] for word in pre_tokenized_text]
    for pair, merge in merges.items():
        for idx, split in enumerate(splits):
            i = 0
            while i < len(split) - 1:
                if split[i] == pair[0] and split[i + 1] == pair[1]:
                    split = split[:i] + [merge] + split[i + 2 :]
                else:
                    i += 1
            splits[idx] = split

    return sum(splits, [])

 

위 코드를 이용하여 "This is not a token failed frequency."라는 문장을 토큰화해 봅니다.

print(tokenize("This is not a token failed frequency."))

 

위 코드를 실행하면 다음과 같이 토큰화가 됩니다.

['this', 'Ġis', 'Ġ', 'n', 'o', 't', 'Ġa', 'Ġtoken', 'Ġ', 'f', 'a', 'i', 'l', 'e', 'd', 'Ġ', 'f', 'r', 'e', 'q', 'u', 'en', 'c', 'y', '.']

 

vocab size도 50으로 매우 작고 학습 데이터도 적기 때문에 언뜻 보면 잘 안된 것 같이 보이지만, 학습 문장에 많이 포함되어 있던 'token'이라는 단어에 대해서는 잘 병합되었음을 확인할 수 있습니다.