Unigram tokenization

อัลกอริทึม Unigram มักจะถูกใช้บ่อยใน SentencePiece ซึ่งเป็นอีกอัลกอริทึมสำหรับการ tokenization ที่ใช้ในโมเดลเช่น AlBERT, T5, mBART, Big Bird, และ XLNet

Training algorithm

เมื่อเทียบกับ BPE และ WordPiece การตัดคำแบบ Unigram ทำงานกลับกันคือ เริ่มจาก vocabulary ตั้งต้นขนาดใหญ่ แล้วอัลกอริทึมจะพยายามลบ token ออกจาก vocabulary จนกว่าจะได้ขนาด vocabulary ที่เราต้องการ การสร้าง vocabulary ตั้งต้นทำได้หลายวิธี คุณอาจจะใช้คำย่อยที่พบบ่อยที่สุด หรือคุณอาจจะใช้ BPE เพื่อสร้าง vocabulary ตั้งต้น โดยตั้งค่าขนาด vocabulary ให้มีขนาดค่อนข้างใหญ่ ในการเทรนแต่ละครั้ง อัลกอริทึม Unigram จะคำนวณค่า loss ของ training corpus ซึ่งขึ้นกับ vocabulary ที่มีในขณะนั้น จากนั้น มันจะลองลบ แต่ละ token ออกจาก vocabulary แล้วคำนวณค่า loss อีกที

เป้าหมายคือการค้นหา token ที่เมื่อลบออกแล้วจะทำให้ค่า loss เพิ่มน้อยที่สุด token พวกนี้คือตัวที่ไม่มีผลต่อค่า loss มาก แปลว่า มันไม่มีประโยชน์มาก ทำให้เราสามารถลบมันออกได้ การคำนวณแบบนี้ค่อนข้างใช้การประมวลผลสูง เราไม่เพียงแค่ลบสัญลักษณ์ออกหนึ่งตัวเท่านั้น แต่เราลบ$p$ เปอร์เซ็นของ token ที่เพิ่มค่าloss น้อยที่สุด (\(p\) คือ hyperparameter ที่เราสามารถตั้งค่าได้ ปกติค่าจะอยู่ที่ 10 หรือ 20) เราจะรันขั้นตอนนี้จนกว่าจะได้ขนาด vocabulary ที่ต้องการ อย่างไรก็ตาม เราจะไม่ลบตัวอักษรตั้งต้น (base characters) เพื่อที่จะได้มั่นใจว่าเราจะยังสามารถ tokenize ทุกคำได้ ส่วนหลักของอัลกอริทึมนี้คือการคำนวณค่า loss ของ corpus และดูว่าค่า loss มีการเปลี่ยนแปลงอย่างไรถ้าเราลบ token ตัวใดตัวหนึ่งออกจาก vocabulary เราจะมาอธิบายว่ามันทำงานอย่างไรกัน

ขั้นตอนนี้จะใช้อัลกอริทึมสำหรับ tokenization ของโมเดล Unigram เราจะใช้ corpus เดียวกันกับในตัวอย่างก่อนๆ :

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

โดยที่เราจะใช้ทุกๆคำย่อยของแต่ละคำ มาสร้าง vocabulary ตั้งต้น :

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

Tokenization algorithm

โมเดล Unigram เป็น language model ประเภทหนึ่งที่ประมวลผลแต่ละ token ในข้อความ โดยมองว่ามันไม่มีส่วนเกี่ยวข้องกับ token ตัวอื่นๆ (not dependent) Unigram ถือว่าเป็น language model ประเภทที่ซับซ้อนน้อยที่สุด เพราะว่าเวลาที่เราคำนวณความน่าจะเป็น(probability)ของ token ที่อยู่ในข้อความใดข้อความหนึ่ง เราไม่ต้องพิจารณา token ตัวอื่นๆในข้อความด้วย ดังนั้น ถ้าเราใช้ Unigram language model เพื่อผลิตข้อความ มันก็จะผลิตคำที่พบบ่อยที่สุดทุกๆครั้ง (language model จะ predict คำที่มีความน่าจะเป็นสูงที่สุดเวลาที่มันผลิตข้อความ)

ความน่าจะเป็นของ token หนึ่งจะเท่ากับความถี่ของคำนั้นๆที่เราพบใน corpus หารกับ ผลรวมของความถี่ของ token ทุกตัวใน vocabulary (ส่วนหารนี้จะช่วยทำให้ค่าความน่าจะเป็นของแต่ละ token รวมกันได้ 1)

ตัวอย่างเช่น "ug" เป็นคำย่อย (subword) ที่อยู่ใน "hug", "pug", และ "hugs" ดังนั้นความถี่ของมันก็คือ 20

ข้างล่างนี้คือความถี่ของคำย่อยทุกๆตัวใน vocabulary ของเรา :

("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 ดังนั้นความน่าจะเป็นของ "ug" ก็คือ 20/210

ในการ tokenize คำๆหนึ่งนั้น เราจะคำนวณทุกๆการตัดคำที่เป็นไปได้ (segmentation) และคำนวณความน่าจะเป็นของแต่ละ segmentation ด้วย โดยใช้วิธีการคำนวณตามโมเดล Unigram เนื่องจากแต่ละ token ไม่ได้ขึ้นกับ token ตัวอื่น ค่าความน่าจะเป็นของแต่ละ segmentation สามารถคำนวณได้โดย นำค่าความน่าจะเป็นของแต่ละ token ย่อยใน segmentation นั้นมาคูณกัน

ตัวอย่างเช่น ถ้าเรา tokenize คำว่า "pug" แล้วได้ ["p", "u", "g"] ความน่าจะเป็นของ segmentation นี้ก็คือ $$P([``p", ``u", ``g"]) = P(``p") \times P(``u") \times P(``g") = \frac{5}{210} \times \frac{36}{210} \times \frac{20}{210} = 0.000389$$

แต่หากเราแบ่งมันออกเป็น ["pu", "g"] ค่าความน่าจะเป็น ก็จะเท่ากับ : $$P([``pu", ``g"]) = P(``pu") \times P(``g") = \frac{5}{210} \times \frac{20}{210} = 0.0022676$$

ปกติแล้วถ้า segmentation มีจำนวนคำย่อยน้อย มันจะมีค่าความน่าจะเป็นที่สูง (เพราะว่า ในการคำนวณความน่าจะเป็นของแต่ละ token ทุกตัวจะถูกหารด้วยค่าเดียวกันคือ 210) ผลลัพธ์แบบนี้ถือว่าดี เพราะสอดคล้องกับสิ่งที่เราต้องการ นั่นคือเราต้องการแยกคำออกเป็นคำย่อยๆ โดยให้มีจำนวนคำย่อยน้อยที่สุดเท่าที่จะเป็นไปได้

สำหรับตัวอย่าง "pug" เราจะได้ความน่าจะเป็นของแต่ละ segmentation ดังนี้ :

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

จะเห็นว่า ["p", "ug"] หรือ ["pu", "g"] มีความน่าจะเป็นเท่ากัน ดังนั้นโปรแกรมของเราจะเลือก segmentation ใดก็ได้ ขึ้นกับว่าโปรแกรมของเราจะอ่านเจอผลลัพธ์ใดก่อน (อย่างไรก็ตามใน corpus ใหญ่ๆ เราจะไม่ค่อยเห็นกรณีแบบนี้ ที่หลาย segmentation มีความน่าจะเป็นเท่ากัน) เนื่องจากเราใช้ตัวอย่างสั้นๆง่ายๆ อาจจะทำให้ดูเหมือนการคำนวณ segmentation ทั้งหมด รวมถึงค่าความน่าจะเป็น ทำได้อย่างง่ายดาย แต่ปกติแล้วการคำนวณจะยากกว่านี้

อัลกอริทึมหนึ่งที่จะช่วยหา segmentation ที่ดีที่สุดให้เรา ก็คือ Viterbi algorithm มันจะสร้างกราฟที่สามารถคำนวณหา segmentation ที่เป็นไปได้ทั้งหมดของคำที่เราต้องการจะ tokenize ตัวอย่างเช่น ถ้า a และ b เป็นคำย่อยที่มีอยู่ใน vocabulary อัลกอริทึมก็จะสร้างกราฟเชื่อมจาก a ไปหา b และมันก็จะคำนวณค่าความน่าจะเป็นของคำย่อยพวกนี้และบันทึกลงไปในกราฟเพื่อการคำนวณต่อไป เป้าหมายของเราคือการหาเส้นทางในกราฟที่แสดงถึง segmentation ที่ดีที่สุด ซึ่งก็คือ segmentation ที่มี score สูงที่สุด เราจะคำนวณ score จากต้นกราฟไปยังปลายกราฟ ในแต่ละตำแหน่งเราจะ loop ตัวอักษรสุดท้ายของแต่ละคำย่อยทุกๆตัวที่เป็นไปได้ในตำแหน่งนั้น และเลือกคำย่อยที่มี score สูงที่สุด และต่อแบบนี้ไปเรื่อยๆจนถึงตำแหน่งสุดท้าย

มาดูตัวอย่างกับคำว่า "unhug" กัน ในแต่ละตำแหน่ง เราได้คำนวณเพื่อหาคำย่อยที่ตัวอักษรสุดท้ายมี score สูงที่สุด :

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)

ดังนั้น "unhug" ก็จะถูกแบ่งเป็น ["un", "hug"]

กลับมาสู่การเทรน

หลังจากที่คุณได้รู้แล้วว่าอัลกอริทึมนี้ tokenize คำอย่างไร ในหัวข้อนี้ เราจะมาดูกันอย่างละเอียดว่า เราจะคำนวณค่า loss เพื่อการเทรนได้อย่างไร ในทุกๆรอบของการเทรน เราจะคำนวณค่า loss โดยเราจะ tokenize แต่ละคำใน corpus ตามข้อมูลใน vocabulary และโมเดล Unigram ที่เราสร้างจากการคำนวณความถี่ของแต่ละ token ใน corpus (อย่างที่เราได้เรียนกันแล้วข้างบน) แต่ละคำใน corpus จะมีค่า score ของมัน ส่วนค่า loss เราจะคำนวณจาก negative log likelihood ของ score พวกนี้ ซึ่งเท่ากับ ผลรวมของ -log(P(word)) ของทุกๆคำ

กลับมาดูตัวอย่างกัน นี่คือ corpus ของเรา :

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

ข้างล่างนี้คือ segmentation ที่ดีที่สุดของแต่ละคำ และ score ของมัน ที่เราใช้โมเดล Ngram คำนวณ :

"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

จากนั้นเราจะคำนวณว่า ถ้าเราลบคำใดคำหนึ่งออก มันจะกระทบค่า loss อย่างไร ขั้นตอนนี้ค่อนข้างซับซ้อน ดังนั้นเราใช้แค่ token สองตัวเป็นตัวอย่าง และจะเขียนโค้ดเพื่อช่วยคำนวณภายหลัง ถ้าคุณยังจำได้ เรามีสอง segmentation ที่มี score เท่ากัน ตัวอย่างเช่น "pug" สามารถถูกแบ่งเป็น ["p", "ug"] ได้ด้วย ดังนั้น ถ้าเราลบ "pu" ออกจาก vocabulary เราก็จะยังได้ค่า loss เท่าเดิม ในทางกลับกัน ถ้าเราลบ "hug" ออก ค่า loss จะเพิ่มสูงขึ้นมาก นั่นก็เพราะว่า ผลลัพธ์ของ "hug" และ "hugs" จะเปลี่ยนเป็น

"hug": ["hu", "g"] (score 0.006802)
"hugs": ["hu", "gs"] (score 0.001701)

การเปลี่ยนแปลงนี้ทำให้ score เปลี่ยนไป และค่า loss รวมก็จะสูงขึ้น :

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

ดังนั้นเราจึงควรจะลบ "pu" ออก แต่เก็บ "hug" ไว้

Implementing Unigram

ในหัวข้อนี้ เราจะมา implement ทุกอย่างกัน เช่นเดียวกับในตัวอย่างของ BPE และ WordPiece โค้ดที่เราจะสอนต่อไปนี้ไม่ใช่โค้ดที่มีประสิทธิภาพที่สุด เราเพียงต้องการให้คุณเข้าในการทำงานของอัลกอริทึมเท่านั้น เราจะใช้ corpus เดียวกับตัวอย่างก่อนๆ :

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 เราเริ่มจากการนับจำนวน(ความถี่)ของแต่ละคำใน corpus :

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 ที่เราต้องการ

vocabulary จะต้องมีตัวอักษรพื้นฐาน ไม่เช่นนั้นเราจะ tokenize ไม่ได้เลย ส่วน token ที่ใหญ่ขึ้น(subwords) เราจะใช้เฉพาะตัวที่พบบ่อยๆเท่านั้น ซึ่งเราจะเรียงลำดับพวกมันตามความถี่ ดังนี้ :

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
        # Loop through the subwords of length at least 2
        for j in range(i + 2, len(word) + 1):
            subwords_freqs[word[i:j]] += freq

# Sort subwords by frequency
sorted_subwords = sorted(subwords_freqs.items(), key=lambda x: x[1], reverse=True)
sorted_subwords[:10]

[('▁t', 7), ('is', 5), ('er', 5), ('▁a', 5), ('▁to', 4), ('to', 4), ('en', 4), ('▁T', 3), ('▁Th', 3), ('▁Thi', 3)]

เราจะนำตัวอักษรและ subwords ที่มีความถี่สูงพวกนี้ มารวมกันเพื่อสร้าง vocabulary ตั้งต้น ขนาด 300 token :

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

ขั้นตอนต่อไป เราจะคำนวณผลรวมของความถี่ของทุกๆคำ เพื่อแปลงความถี่เป็นค่าความน่าจะเป็น

สำหรับโมเดลของเรา เราจะคำนวณค่าลอการิทึมของความน่าจะเป็น แทนที่จะใช้ความน่าจะเป็นเท่านั้น เพราะว่ามันจะทำให้การคำนวณมีความเสถียรมากกว่า เมื่อเทียบกับการคูณจำนวนน้อยๆหลายๆจำนวน และมันยังช่วยทำให้การคำนวณค่า loss ทำได้ง่ายขึ้นด้วย :

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()}

ฟังก์ชันหลักของ tokenizer นี้คือการ tokenize คำ โดยใช้อัลกอริทึม Viterbi ช่วย อย่างที่คุณได้เห็นมาแล้ว อัลกอริทึม Viterbi จะคำนวณหาการแบ่งคำที่ดีที่สุดให้กับแต่ละคำใน corpus ซึ่ง segmentation พวกนี้จะถูกเซฟไว้ใน list ชื่อ best_segmentations สำหรับคำที่เราต้องการจะ tokenize ในแต่ละตำแหน่ง (เริ่มจาก 0 ถึง ความยาวของคำ) เราจะสร้าง dictionary ขึ้นมา ซึ่งมีคีย์สองตัว ตัวแรกคือ index ของตัวอักษรแรกของ token สุดท้ายใน segmentation ที่ดีที่สุดของคำนั้น และคีย์ตัวที่สองคือค่า score ของ segmentation ที่ดีที่สุด คีย์ที่เก็บ index นี้ จะช่วยให้เราสามารถคำนวณ segmentation เต็มๆได้ หลังจากที่เราเพิ่มข้อมูลลงใน list แล้ว

เริ่มจากเราจะ for loop สองครั้ง เพื่อค้นหาคำย่อยในคำหลักที่อาจจะอยู่ใน vocabulary โดย loop แรกเอาไว้หาตำแหน่งเริ่มต้นของคำย่อย ส่วน loop ที่สองเอาไว้หาตำแหน่งจบของคำย่อยนั้น ถ้าเราเจอคำย่อยที่อยู่ใน vocabulary เราจะสร้าง segmentation ใหม่ขึ้นมาโดยแบ่งคำหลักตรงคำย่อยนี้ และก่อนที่จะบันทึก segmentation นี้ลงไป เราจะเทียบกับ score ของมันกับ score ของ segmentation ที่มีอยู่แล้วใน best_segmentations หลังจาก loop จบ เราจะคำนวณหา segmentation ที่ดีที่สุดของคำ input โดยอ่านจากตำแหน่งสุดท้ายของคำไปหาต้นคำ และบันทึกคำย่อยที่ดีที่สุดเอาไว้สำหรับทุกๆตำแหน่ง :

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))

(['H', 'o', 'p', 'e', 'f', 'u', 'll', 'y'], 41.5157494601402)
(['This'], 6.288267030694535)

และเราก็ยังสามารถคำนวณค่า loss ได้อย่างง่ายดายอีกด้วย :

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

มาเช็คผลลัพธ์การคำนวณ loss จากโมเดลของเรากัน :

compute_loss(model)

413.10377642940875

การคำนวณ score ให้แต่ละ token ก็ไม่ยากเช่นกัน โดยเราจะคำนวณค่า loss หลังจากที่เราลบ token นั้นออก :

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

ลองรันโค้ดกับ token ตัวอย่างดังนี้ :

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

เนื่องจาก "ll" ถูกใช้ในการ tokenize คำว่า "Hopefully" ถ้าเราลบมันออก เราจะต้องใช้ "l" สองครั้งแทน ในกรณีนี้ ค่า loss จะสูงขึ้น ส่วน "his" ถูกใช้แค่ในคำว่า "This" ซึ่งคำนี้ถูก tokenize ให้เป็นตัวมันเอง(ไม่มีการแบ่ง) หากเราลบมันออก "his" ก็จะไม่มีผลต่อค่า loss มาดูผลลัพธ์กัน :

6.376412403623874
0.0

สิ่งสุดท้ายที่เราจะต้องทำก็คือ เพิ่ม token พิเศษที่โมเดลใช้ลงไปใน vocabulary จากนั้น loop จนกว่าเราจะลบ token ออกจาก 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()}

เมื่อเราต้องการจะ tokenize ประโยคหรือข้อความ สิ่งที่เราต้องทำก็คือทำการ pre-tokenization ข้อความนั้น แล้วรันฟังก์ชัน 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)

['▁This', '▁is', '▁the', '▁Hugging', '▁Face', '▁', 'c', 'ou', 'r', 's', 'e', '.']

จบแล้วสำหรับอัลกอริทึม Unigram หวังว่าถึงตอนนี้คุณจะรู้สึกว่าคุณเป็นผู้เชี่ยวชาญด้าน tokenizer ในระดับหนึ่งแล้ว ในบทถัดไปเราจะพูดถึงส่วนประกอบสำคัญของ 🤗 Tokenizers library และมาดูกันว่าคุณจะใช้มันเพื่อสร้าง tokenizer ของคุณเองได้อย่างไร