[🤗 강좌 6.8] Unigram 토큰화

Unigram 알고리즘은 AlBERT, T5, mBART, Big Bird 및 XLNet과 같은 모델에서 사용되는 토큰화 알고리즘인 SentencePiece에서 자주 사용됩니다.

💡 이 섹션에서는 전체 구현을 보여주는 것을 포함하여 Unigram을 깊이 있게 다룹니다. 토큰화 알고리즘에 대한 일반적인 개요를 원하는 경우 생략해도 좋습니다.

학습 알고리즘

BPE 및 WordPiece와 비교하여 Unigram은 다른 방향으로 작동합니다. 즉, 크기가 큰 vocabulary에서 시작하여 원하는 vocabulary 크기에 도달할 때까지 토큰을 제거합니다. 기본 vocabulary를 구축하는데 사용할 수 있는 몇 가지 옵션이 있습니다. 예를 들어, 사전 토큰화된 단어에서 가장 일반적인 부분 문자열을 취하거나 큰 규모의 vocabulary를 가진 초기 말뭉치에 BPE를 적용할 수 있습니다.

학습의 각 단계에서 Unigram 알고리즘은 현재 vocabulary가 주어졌을 때의 말뭉치에 대한 손실(loss)을 계산합니다. 그런 다음, vocabulary의 각 기호(symbol)에 대해, 해당 기호가 제거되면 전체 손실이 얼마나 증가할지 계산하고 가장 적게 증가하는 기호를 찾습니다. 이렇게 찾은 기호들(symbols)은 말뭉치에 대한 전체 손실에 더 적은 영향을 미치므로 어떤 의미에서는 "덜 필요(less needed)"하고 제거 대상으로 가장 적합한 후보입니다.

이것은 비용이 많이 드는 작업이므로 가장 낮은 손실을 초래하는 기호 하나만 제거하지 않고, 이러한 기호들의 $p$%($p$는 제어할 수 있는 하이퍼파라미터이고 일반적으로 10 또는 20을 지정)를 제거합니다. 이 과정은 vocabulary가 원하는 크기에 도달할 때까지 반복됩니다.

모든 단어를 토큰화할 수 있도록 기본 문자들을 제거하지 않는다는 점도 중요합니다.

아직도 설명이 약간 모호한 부분이 있지요. 이 알고리즘의 핵심은 말뭉치에 대한 손실을 계산하고 vocabulary에서 일부 토큰을 제거할 때 손실이 어떻게 변하는지 확인하는 것이지만 아직 어떻게 수행하는지에 대한 내용을 설명하지 않았습니다. 이 부분은 Unigram 모델의 토큰화 알고리즘에 기반하므로 다음에 자세히 살펴보겠습니다.

역시 이전 예제의 말뭉치를 재사용합니다:

("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)

초기 vocabulary는 위 말뭉치에 존재하는 모든 단어들의 모든 하위 문자열(substrings)로 구성됩니다.

["h", "u", "g", "hu", "ug", "p", "pu", "n", "un", "b", "bu", "s", "hug", "gs", "ugs"]

토큰화 알고리즘

Unigram 모델은 개별 토큰들의 출현 분포가 서로 독립적(i.i.d)이라는 가정을 하는 언어 모델 유형입니다. 토큰 X의 확률이 문맥에 상관없이 동일하다는 점에서 가장 단순한 언어 모델입니다. 따라서 Unigram 언어 모델을 사용하여 텍스트를 생성하는 경우 항상 가장 일반적이고 흔한(common) 토큰을 도출합니다.

특정 토큰의 확률은 말뭉치 내에서의 해당 토큰 출현 빈도를 vocabulary에 존재하는 모든 토큰들의 출현 빈도의 합으로 나눈 것입니다(확률의 합이 1이 되도록 하기 위해). 예를 들어 "ug"는 "hug", "pug" 및 "hugs"에 있으므로 말뭉치에서의 빈도는 20입니다.

다음은 vocabulary에서의 모든 하위 단어(subwords)의 빈도입니다:

("h", 15) ("u", 36) ("g", 20) ("hu", 15) ("ug", 20) ("p", 17) ("pu", 17) ("n", 16)
("un", 16) ("b", 4) ("bu", 4) ("s", 5) ("hug", 15) ("gs", 5) ("ugs", 5)

따라서 모든 빈도의 합은 210이고 하위 단어(subword) "ug"의 확률은 20/210입니다.

✏️ Now your turn! 위의 빈도를 계산하는 코드를 작성하고 표시된 결과와 총합이 올바른지 다시 확인해보세요.

이제 주어진 단어를 토큰화하기 위해, 가능한 모든 토큰 분할을 살펴보고 Unigram 모델에 따라 각각의 확률을 계산합니다. 모든 토큰의 출현 빈도가 독립적인 것으로 간주되기 때문에 이 확률은 각 토큰의 확률의 곱일 뿐입니다. 예를 들어, "pug"의 토큰화 결과인 ["p", "u", "g"]의 확률은 다음과 같이 계산됩니다:

$P(["p", "u", "g"]) = P("p") \times P("u") \times P("g") = \frac{5}{210} \times \frac{36}{210} \times \frac{2}{210} = 0.000389$

이에 비해 토큰화 결과인 ["pu", "g"]의 확률은 다음과 같습니다:

$P(["pu", "g"]) = P("pu") \times P("g") = \frac{5}{210} \times \frac{20}{210} = 0.0022676$

따라서, ["pu", "g"]이 훨씬 더 자주 출현한다고 볼 수 있겠지요. 일반적으로 가장 적은 수의 하위 토큰들로 구성된 토큰화 결과는 비교적 높은 확률(각 토큰에 대해 반복되는 210으로 나누기 때문에)을 가지며, 이는 우리가 직관적으로 원하는 결과입니다.

Unigram 모델을 사용한 단어의 토큰화는 가장 높은 확률을 나타내는 분할 형태로 토큰화됩니다. "pug"의 예에서 가능한 각 분할에 대해 얻을 수 있는 확률은 다음과 같습니다:

["p", "u", "g"] : 0.000389
["p", "ug"] : 0.0022676
["pu", "g"] : 0.0022676

따라서 "pug"는 위 분할 방법 중에서 ["p", "ug"] 또는 ["pu", "g"]로 토큰화될 수 있습니다. 그러나 큰 규모의 말뭉치에서는 분할 방법에 대한 확률값이 같은 경우가 매우 드뭅니다.

위의 경우에서는 가능한 모든 분할을 찾고 확률을 계산하는 것이 쉬웠지만, 일반적으로는 더 어려울 수 있습니다. 이를 위해 사용되는 고전적인 알고리즘인 Viterbi 알고리즘 이 있습니다. 본질적으로, 주어진 단어에 대한 가능한 모든 분할들을 나타낼 수 있는 그래프를 구성할 수 있습니다. 그리고 만일 주어진 단어 내의 문자 a에서 b까지의 하위 단어(subword)가 vocabulary에 존재한다면, 우리는 이 그래프 내에서 a에서 출발하여 b까지 가는 그래프 내의 가지(branch)가 있다고 말할 수 있습니다. 그리고 이 하위 단어의 확률을 해당 가지(branch)에 지정할 수 있습니다.

그래프에서 최고 점수를 얻을 경로를 찾기 위해 Viterbi 알고리즘은 단어 내의 각 위치(문자)에 대해 해당 위치에서 끝나는 경로의 최고 점수를 나타내는 분할(segmentation)을 결정합니다. 단어의 처음 위치부터 끝까지 이동하면서, 현재 위치에서 끝나는 모든 하위 단어를 검사한 다음 이 하위 단어가 시작하는 위치에서 최고의 토큰화 점수를 사용하여 최상의 점수를 찾을 수 있습니다. 그런 다음 끝에 도달하기 위해 선택한 경로를 펼치기만 하면 됩니다.

앞에서 구성한 vocabulary와 "unhug"라는 단어를 사용한 예를 살펴보겠습니다. 해당 단어의 각 위치에 대해 최고 점수로 끝나는 하위 단어는 다음과 같습니다:

Character 0 (u): "u" (score 0.171429)
Character 1 (n): "un" (score 0.076191)
Character 2 (h): "un" "h" (score 0.005442)
Character 3 (u): "un" "hu" (score 0.005442)
Character 4 (g): "un" "hug" (score 0.005442)

위에서 처음부터 마지막 글자('g')까지 진행한 결과, ["un", "hug"]가 가장 높은 점수인 0.005442를 나타냈습니다. 따라서 "unhug"는 ["un", "hug"]로 토큰화됩니다.

✏️ Now your turn! "huggun"이라는 단어를 토큰화하고 해당 점수를 계산해보세요.

다시 학습 알고리즘

이제 토큰화가 어떻게 작동하는지 보았으므로 학습 과정에서 사용된 손실(loss)에 대해 조금 더 자세히 알아보겠습니다. 각각의 주어진 단계에서 이 손실은 말뭉치 내의 모든 단어를 토큰화하여 계산됩니다. 계산 과정에서 앞에서 설명한 것처럼 현재 vocabulary와 말뭉치에 있는 각 토큰의 빈도에 의해 결정된 유니그램 모델을 사용합니다.

말뭉치의 각 단어별로 점수를 계산하며 손실은 해당 점수의 음의 로그 우도(negative log likelihood)입니다. 즉, 말뭉치에 있는 모든 단어의 $-log(P(word))$ 합계입니다.

위에서 설명한 말뭉치를 가지고 설명합니다:

("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)

각 단어의 토큰화 결과 및 점수는 다음과 같습니다:

"hug": ["hug"] (score 0.071428)
"pug": ["pu", "g"] (score 0.007710)
"pun": ["pu", "n"] (score 0.006168)
"bun": ["bu", "n"] (score 0.001451)
"hugs": ["hug", "s"] (score 0.001701)

따라서 손실(loss)은 다음과 같습니다:

10 * (-log(0.071428)) + 5 * (-log(0.007710)) + 12 * (-log(0.006168)) + 4 * (-log(0.001451)) + 5 * (-log(0.001701)) = 169.8

이제 각 토큰을 제거하는 것이 손실값에 어떤 영향을 미치는지 계산해야 합니다. 이 작업은 수작업으로 하기에는 시간이 걸리므로 여기에서는 두 개의 토큰("pu", "hug")에 대해 이를 수행하고 나머지 프로세스는 아래에서 해당 작업에 대한 실제 구현이 완료되었을 때 수행합니다. 위에서 살펴보았듯이, 이 시점에서 "pug"는 동일한 점수(0.0022676)를 가진 두개의 토큰화 결과를 가지고 있었다는 것을 기억하시지요? 바로 ["p", "ug"]와 ["pu", "g"]가 그것입니다. 따라서 "pu" 토큰을 vocabulary에서 제거하더라도 토큰화 결과가 동일한 점수를 가진 ["p", "ug"]가 되므로, 결론적으로는 위에서 계산한 것과 똑같은 손실(loss)값이 도출되겠지요.

반면에, "hug"를 제거하면 손실값이 더 올라가게 됩니다. 그 이유는 "hug"와 "hugs"의 토큰화 결과가 다음과 같이 되기 때문이겠지요:

"hug": ["hu", "g"] (score 0.006802)   # 위의 토큰화 결과보다 점수가 낮아짐.
"hugs": ["hu", "gs"] (score 0.001701)

그 결과 다음 계산 결과값 만큼 손실값이 올라가게 됩니다:

- 10 * (-log(0.071428)) + 10 * (-log(0.006802)) = 23.5

결론적으로, 토큰 "pu"는 vocabulary에서 제거되겠지만 "hug"는 제거되지 않습니다.

Unigram 구현

이제 지금까지 살펴본 모든 것을 코드로 구현해 보겠습니다. BPE 및 WordPiece와 마찬가지로 이것은 Unigram 알고리즘의 효율적인 구현은 아니지만 전체 알고리즘을 이해하는데는 도움이 될 것입니다.

이전과 동일한 말뭉치를 사용합니다:

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.",
]

이번에는 xlnet-base-cased를 모델로 사용할 것입니다:

from transformers import AutoTokenizer

tokenizer = AutoTokenizer.from_pretrained("xlnet-base-cased")

BPE 및 WordPiece의 경우와 마찬가지로 말뭉치에서 각 단어의 출현 빈도를 계산하는 것으로 시작합니다:

from collections import defaultdict

word_freqs = defaultdict(int)
for text in corpus:
    words_with_offsets = tokenizer.backend_tokenizer.pre_tokenizer.pre_tokenize_str(text)
    new_words = [word for word, offset in words_with_offsets]
    for word in new_words:
        word_freqs[word] += 1

word_freqs

그리고 최종적으로 원하는 크기보다 더 크게 vocabulary를 초기화해야 합니다. 초기화 과정에서 vocabulary에 모든 기본 문자들을 포함해야 합니다. 그렇지 않으면 모든 단어를 토큰화할 수 없겠지요. 또한 길이가 더 긴 부분 문자열에 대해서는 가장 빈번하게 출현하는 것들만 추가할 것이므로 일단 빈도순으로 정렬을 수행합니다:

char_freqs = defaultdict(int)
subwords_freqs = defaultdict(int)
for word, freq in word_freqs.items():
    for i in range(len(word)):
        char_freqs[word[i]] += freq
        # 길이가 적어도 2 이상인 subword들을 추가함.
        for j in range(i + 2, len(word) + 1):
            subwords_freqs[word[i:j]] += freq
            
# Subword들을 빈도 역순으로 정렬
sorted_subwords = sorted(subwords_freqs.items(), key=lambda x: x[1], reverse=True)
sorted_subwords[:10]

크기가 300인 초기 vocabulary를 구성하기 위해서 앞에서 만들어진 sorted_subwords 중에서 빈도가 높은 하위 단어들을 선택합니다:

token_freqs = list(char_freqs.items()) + sorted_subwords[: 300 - len(char_freqs)]
token_freqs = {token: freq for token, freq in token_freqs}

💡 SentencePiece는 ESA(Enhanced Suffix Array)라는 보다 효율적인 알고리즘을 사용하여 초기 어휘를 생성합니다.

다음으로 모든 빈도의 합을 계산하여 빈도를 확률로 변환합니다. 우리 모델의 경우 확률의 로그값을 저장할 것입니다. 작은 숫자를 곱하는 것보다 로그를 더하는 것이 수치적으로 더 안정적이기 때문입니다. 이렇게 하면 모델 손실 계산이 단순화됩니다:

from math import log

total_sum = sum([freq for token, freq in token_freqs.items()])
model = {token: -log(freq / total_sum) for token, freq in token_freqs.items()}

이제 가장 중요한 부분은 Viterbi 알고리즘을 사용하여 단어를 토큰화하는 기능입니다. 이전에 보았듯이 이 알고리즘은 단어의 각 부분 문자열에 대한 최상의 분할을 계산하고 이를 best_segmentations라는 변수에 저장합니다. 단어의 각 위치당 하나의 딕셔너리(0에서 전체 길이까지)을 두 개의 키와 함께 저장합니다. 이는 가장 점수가 높은 분할(segmentation)에서 마지막 토큰의 시작 인덱스와 해당 점수입니다. 마지막 토큰의 시작 인덱스를 사용하여 목록이 완전히 채워지면 전체 분할을 검색할 수 있습니다.

목록 채우기는 단 2개의 루프로 완료됩니다. 기본 루프는 각 시작 위치로 이동하고 두 번째 루프는 해당 시작 위치에서 시작하는 모든 하위 문자열을 검토합니다. 하위 문자열이 vocabulary에 있는 경우 해당 끝 위치까지 단어의 새로운 분할이 있으며 이를 best_segmentations에 있는 것과 비교합니다.

메인 루프가 끝나면 단어의 시작 부분에 도달할 때까지 끝에서 시작하여 특정 시작 위치에서 다음 위치로 이동하면서 토큰을 기록합니다:

def encode_word(word, model):
    best_segmentations = [{"start": 0, "score": 1}] + [
        {"start": None, "score": None} for _ in range(len(word))
    ]
    for start_idx in range(len(word)):
        # This should be properly filled by the previous steps of the loop
        best_score_at_start = best_segmentations[start_idx]["score"]
        for end_idx in range(start_idx + 1, len(word) + 1):
            token = word[start_idx:end_idx]
            if token in model and best_score_at_start is not None:
                score = model[token] + best_score_at_start
                # If we have found a better segmentation ending at end_idx, we update
                if (
                    best_segmentations[end_idx]["score"] is None
                    or best_segmentations[end_idx]["score"] > score
                ):
                    best_segmentations[end_idx] = {"start": start_idx, "score": score}
    
    segmentation = best_segmentations[-1]
    if segmentation["score"] is None:
        # We did not find a tokenization of the word -> unknown
        return ["<unk>"], None
    
    score = segmentation["score"]
    start = segmentation["start"]
    end = len(word)
    tokens = []
    while start != 0:
        tokens.insert(0, word[start:end])
        next_start = best_segmentations[start]["start"]
        end = start
        start = next_start
    tokens.insert(0, word[start:end])
    return tokens, score

몇 개의 단어들로 위 함수를 테스트해볼 수 있습니다:

print(encode_word("Hopefully", model))
print(encode_word("This", model))

이제 말뭉치에서 모델의 손실을 쉽게 계산할 수 있습니다!

def compute_loss(model):
    loss = 0
    for word, freq in word_freqs.items():
        _, word_loss = encode_word(word, model)
        loss += freq * word_loss
    return loss

현재 모델에서 작동하는지 확인할 수 있습니다:

compute_loss(model)

각 토큰의 점수를 계산하는 것도 그리 어렵지 않습니다. 각 토큰을 삭제하여 얻은 모델의 손실을 계산하기만 하면 됩니다:

import copy

def compute_scores(model):
    scores = {}
    model_loss = compute_loss(model)
    for token, score in model.items():
        # We always keep tokens of length 1
        if len(token) == 1:
            continue
        model_without_token = copy.deepcopy(model)
        _ = model_without_token.pop(token)
        scores[token] = compute_loss(model_without_token) - model_loss
    return scores

각 토큰에 대해서 위 함수를 실행합니다:

scores = compute_scores(model)
print(scores["ll"])
print(scores["his"])

"ll"은 "Hopefully"의 토큰화에 사용되며 이를 제거하면 토큰 "l"을 대신 두번 사용하게 되므로 추가적인 손실이 발생할 것으로 예상합니다. "his"는 그 자체로 토큰화된 "This" 단어 내에서만 사용되므로 손실이 0일 것으로 예상합니다. 결과는 위와 같습니다.

💡 이 접근 방식은 매우 비효율적이므로, SentencePiece는 토큰 X가 없는 모델 손실의 근사치를 사용합니다. 처음부터 시작하는 대신 남은 vocabulary의 분할로 토큰 X를 대체합니다. 이런 식으로 모든 점수는 모델 손실과 동시에 한 번에 계산할 수 있습니다.

이제 마지막으로 해야 할 일은 모델에서 사용하는 특수 토큰을 vocabulary에 추가한 다음 원하는 크기에 도달할 때까지 vocabulary에서 토큰을 반복적으로 제거해 나가는 것입니다:

percent_to_remove = 0.1
while len(model) > 100:
    scores = compute_scores(model)
    sorted_scores = sorted(scores.items(), key=lambda x: x[1])
    # Remove percent_to_remove tokens with the lowest scores.
    for i in range(int(len(model) * percent_to_remove)):
        _ = token_freqs.pop(sorted_scores[i][0])
        
    total_sum = sum([freq for token, freq in token_freqs.items()])
    model = {token: -log(freq / total_sum) for token, freq in token_freqs.items()}

입력 텍스트를 토큰화하려면 사전 토큰화를 적용한 다음 encode_word() 함수를 사용하면 됩니다:

def tokenize(text, model):
    words_with_offsets = tokenizer.backend_tokenizer.pre_tokenizer.pre_tokenize_str(text)
    pre_tokenized_text = [word for word, offset in words_with_offsets]
    encoded_words = [encode_word(word, model)[0] for word in pre_tokenized_text]
    return sum(encoded_words, [])

tokenize("This is the Hugging Face course.", model)

유니그램에 대해서 설명했습니다. 지금쯤이면 토크나이저에 관한 전문가가 되셨기를 바랍니다. 다음 섹션에서는 🤗 Tokenizers 라이브러리의 빌딩 블록을 탐구하고 이를 사용하여 자신만의 토크나이저를 구축하는 방법을 공부해보겠습니다.