Φτιάξτε έναν BPE tokenizer: γιατί το μοντέλο σας δεν μπορεί να μετρήσει τα R

Υπάρχουν δύο προφανείς τρόποι να δώσετε κείμενο σε ένα δίκτυο και αποτυγχάνουν και οι δύο για λόγους που αξίζει να κατανοήσετε, επειδή η αποτυχία ορίζει το σχήμα της λύσης.

Λέξεις. Χωρίστε με βάση τα κενά, δώστε σε κάθε λέξη έναν αριθμό. Τα αγγλικά έχουν εκατοντάδες χιλιάδες μορφές λέξεων και το μοντέλο χρειάζεται μία γραμμή embedding για καθεμία, οπότε το λεξιλόγιο —και το επίπεδο εξόδου, που πρέπει να παράγει μια βαθμολογία για κάθε καταχώριση— γίνεται τεράστιο. Ακόμα χειρότερο είναι αυτό που συμβαίνει στο inference: μια λέξη που το μοντέλο δεν είδε ποτέ στην εκπαίδευση δεν έχει αριθμό. Αυτό είναι το πρόβλημα out-of-vocabulary, και η συνηθισμένη λύση είναι να χαρτογραφούνται όλα τα άγνωστα σε ένα μόνο <UNK> token, πετώντας την πληροφορία. Επίσης, η «λέξη» δεν είναι καλά ορισμένη έννοια: τα κινεζικά και τα ιαπωνικά δεν βάζουν κενά ανάμεσα στις λέξεις, και τα γερμανικά συνθέτουν ουσιαστικά το ένα πάνω στο άλλο επ’ αόριστον.

Χαρακτήρες. Δεν υπάρχει πρόβλημα out-of-vocabulary, και το λεξιλόγιο έχει περίπου εκατό σύμβολα. Όμως οι ακολουθίες γίνονται πολύ μεγάλες, και το Κεφάλαιο 9 θα δείξει ότι το κόστος του attention αυξάνεται τετραγωνικά με το μήκος της ακολουθίας. Ένα έγγραφο 1000 λέξεων έχει περίπου 5000 χαρακτήρες — μια ακολουθία τέσσερις έως πέντε φορές μεγαλύτερη απ’ όσο χρειάζεται, με τετραγωνική τιμή. Και κάθε χαρακτήρας μεταφέρει σχεδόν μηδενικό νόημα από μόνος του, οπότε τα πρώτα επίπεδα ξοδεύονται στο να ξανασυναρμολογούν λέξεις που ο tokenizer θα μπορούσε να έχει παραδώσει ακέραιες.

Η απάντηση βρίσκεται ανάμεσά τους: υπολέξεις. Οι συχνές λέξεις γίνονται ένα token, οι σπάνιες λέξεις σπάνε σε κομμάτια, και τίποτα δεν είναι ποτέ άγνωστο επειδή τα κομμάτια καταλήγουν τελικά σε μεμονωμένα bytes. Το ενδιαφέρον είναι ότι κανείς δεν σχεδιάζει τον διαχωρισμό. Ο tokenizer εκπαιδεύεται, στο ίδιο είδος δεδομένων με το μοντέλο, και μαθαίνει ποιες ακολουθίες byte αξίζουν τον δικό τους αριθμό μετρώντας πόσο συχνά εμφανίζονται μαζί.

Ο αλγόριθμος είναι από το 1994, και ήταν αλγόριθμος συμπίεσης. Ο Philip Gage τον δημοσίευσε στο C Users Journal ως τρόπο να μικραίνουν τα αρχεία, αντικαθιστώντας επανειλημμένα το συχνότερο ζεύγος γειτονικών bytes με ένα byte που δεν εμφανίζεται στα δεδομένα.¹ Έμεινε εκεί για είκοσι δύο χρόνια, μέχρι που οι Sennrich, Haddow και Birch τον επαναχρησιμοποίησαν για μηχανική μετάφραση το 2016, για να λύσουν το πρόβλημα out-of-vocabulary.² Σήμερα είναι ουσιαστικά ο τρόπος με τον οποίο διαβάζει κάθε μεγάλο γλωσσικό μοντέλο.

Ο βρόχος εκπαίδευσης είναι τέσσερα βήματα που επαναλαμβάνονται:

Ορίστε ολόκληρος ο trainer:

def get_stats(ids):
    counts = {}
    for a, b in zip(ids, ids[1:]):
        counts[(a, b)] = counts.get((a, b), 0) + 1
    return counts


def merge(ids, pair, idx):
    out, i = [], 0
    while i < len(ids):
        if i < len(ids) - 1 and ids[i] == pair[0] and ids[i + 1] == pair[1]:
            out.append(idx)
            i += 2
        else:
            out.append(ids[i])
            i += 1
    return out


class BPE:
    def __init__(self):
        self.merges = {}
        self.vocab = {i: bytes([i]) for i in range(256)}

    def train(self, text, vocab_size):
        ids = list(text.encode("utf-8"))
        for i in range(vocab_size - 256):
            stats = get_stats(ids)
            if not stats:
                break
            pair = max(stats, key=stats.get)      
            idx = 256 + i                         
            ids = merge(ids, pair, idx)           
            self.merges[pair] = idx               
            self.vocab[idx] = self.vocab[pair[0]] + self.vocab[pair[1]]
        return ids

Τρέξτε τον σε 151.191 bytes αγγλικής πρόζας και εκτυπώστε τις πρώτες δώδεκα συγχωνεύσεις καθώς συμβαίνουν. Αυτό είναι το μέρος που αξίζει να διαβαστεί αργά, επειδή κανείς δεν είπε στον αλγόριθμο τίποτα για τα αγγλικά:

merge   1: b'e' + b' '   -> b'e '     (occurred 4433 times)
merge   2: b' ' + b't'   -> b' t'     (occurred 3302 times)
merge   3: b'\xe2' + b'\x80' -> b'\xe2\x80'  (occurred 3247 times)
merge   4: b' ' + b'a'   -> b' a'     (occurred 2335 times)
merge   5: b' t' + b'h'  -> b' th'    (occurred 2253 times)
merge   6: b'i' + b'n'   -> b'in'     (occurred 2011 times)
merge   7: b't' + b' '   -> b't '     (occurred 1904 times)
merge   8: b'e' + b'r'   -> b'er'     (occurred 1813 times)
merge   9: b'd' + b' '   -> b'd '     (occurred 1703 times)
merge  10: b'o' + b'u'   -> b'ou'     (occurred 1554 times)
merge  11: b' ' + b's'   -> b' s'     (occurred 1467 times)
merge  12: b' th' + b'e '-> b' the '  (occurred 1270 times)

Τρία πράγματα σε αυτή τη λίστα αξίζει να επισημανθούν.

Η συγχώνευση 12 είναι η λέξη «the» — με το κενό πριν και το κενό μετά, ως μία ενιαία μονάδα, που ανακαλύφθηκε στη δωδέκατη επανάληψη ενός βρόχου που μετρά ζεύγη. Κανείς δεν έδωσε λεξικό. Βρίσκεται εκεί επειδή αυτά τα πέντε bytes συνυπάρχουν συχνότερα από οποιαδήποτε άλλα πέντε στα αγγλικά.

Η συγχώνευση 3 δεν είναι καθόλου κείμενο. Το \xe2\x80 είναι τα πρώτα δύο bytes της κωδικοποίησης UTF-8 της τυπογραφικής στίξης — της μεγάλης παύλας, των καμπύλων εισαγωγικών. Ο αλγόριθμος δεν έχει ιδέα ότι υπάρχει το UTF-8, και μόλις ξανανακάλυψε ένα κομμάτι της δομής του, επειδή οι κωδικοποιήσεις πολλών bytes είναι εκ κατασκευής ακολουθίες byte που εμφανίζονται πάντα μαζί.

Οι περισσότερες πρώιμες συγχωνεύσεις περιλαμβάνουν ένα κενό, και το κενό συνήθως βρίσκεται αριστερά. Αυτή είναι η προέλευση μιας από τις πιο μπερδεμένες συμπεριφορές στην πράξη, στην οποία επιστρέφουμε σύντομα.

Κάθε συγχώνευση κάνει την ακολουθία μικρότερη και το λεξιλόγιο μεγαλύτερο. Το πόσο μακριά θα το πάτε είναι πραγματική απόφαση, και μπορεί να μετρηθεί — εδώ στα ίδια 151.191 bytes:

Φθίνουσες αποδόσεις, ολοφάνερα. Ο διπλασιασμός από 512 σε 1024 αγοράζει 0,78 bytes ανά token· ο διπλασιασμός από 2048 σε 4096 αγοράζει 1,07 — καλύτερα εδώ μόνο επειδή αυτό το corpus είναι αρκετά μικρό ώστε οι μεγαλύτερες συγχωνεύσεις να συνεχίζουν να αποδίδουν. Σε ένα πραγματικό corpus η καμπύλη πλαταίνει έντονα.

Και το κόστος ενός μεγαλύτερου λεξιλογίου δεν είναι μόνο μνήμη. Κάθε token χρειάζεται μία γραμμή embedding, και —ακριβότερα— το επίπεδο εξόδου του μοντέλου πρέπει να παράγει μια βαθμολογία για κάθε καταχώριση στο λεξιλόγιο σε κάθε βήμα, άρα ο τελικός πολλαπλασιασμός πινάκων κλιμακώνεται με το μέγεθος του λεξιλογίου. Τα πραγματικά μοντέλα βρίσκονται μεταξύ 32.000 και 200.000: το GPT-2 χρησιμοποίησε 50.257, το cl100k του GPT-4 χρησιμοποιεί 100.277, το o200k του GPT-4o περίπου το διπλασιάζει. Η τάση είναι ανοδική, και ο λόγος βρίσκεται στην επόμενη ενότητα.

Ορίστε η ίδια παράγραφος, μεταφρασμένη, μετρημένη με τους πραγματικούς tokenizers που διαθέτει η OpenAI:

Το ίδιο περιεχόμενο, το ίδιο νόημα, και με το cl100k η ρωσική εκδοχή καταναλώνει δυόμισι φορές περισσότερα token. Εφόσον τα APIs χρεώνουν ανά token και τα context windows μετρώνται σε token, αυτό δεν είναι γλωσσική περιέργεια — είναι γραμμή στον προϋπολογισμό, μικρότερο αποτελεσματικό context window, και πιο αργή απόκριση, και τα τρία μαζί, για όλους όσοι δεν δουλεύουν στα αγγλικά.

Ο μηχανισμός είναι τα δεδομένα εκπαίδευσης. Ένας tokenizer εκπαιδευμένος κυρίως στα αγγλικά ξοδεύει τον προϋπολογισμό συγχωνεύσεών του σε αγγλικές ακολουθίες byte. Τα ισπανικά μοιράζονται το λατινικό αλφάβητο, οπότε εξακολουθούν να ωφελούνται κάπως· τα ρωσικά σχεδόν καθόλου, επειδή οι κυριλλικοί χαρακτήρες παίρνουν δύο bytes σε UTF-8 και λίγα από αυτά τα ζεύγη ήταν αρκετά κοινά στο corpus εκπαίδευσης ώστε να κερδίσουν συγχώνευση. Τα ιαπωνικά είναι ακόμη χειρότερα: τρία bytes ανά χαρακτήρα, και 72 χαρακτήρες γίνονται 79 token — περισσότερα token από χαρακτήρες.

Η στήλη o200k δείχνει ότι αυτό είναι λύσιμο πρόβλημα και ότι ήδη λύνεται. Ο διπλασιασμός του λεξιλογίου και η εξισορρόπηση των δεδομένων εκπαίδευσης μειώνουν την επιβάρυνση στα ισπανικά από +39 % σε +16 %, και στα ρωσικά από +152 % σε +39 %. Αυτός είναι ο πραγματικός λόγος που τα λεξιλόγια συνεχίζουν να μεγαλώνουν: όχι η συμπίεση για τη συμπίεση, αλλά το γεγονός ότι η προηγούμενη γενιά χρέωνε σιωπηρά ένα μεγάλο μέρος του κόσμου περισσότερο.

Η εκπαίδευση παρήγαγε μια διατεταγμένη λίστα συγχωνεύσεων. Η κωδικοποίηση νέου κειμένου την αναπαράγει — και πρέπει να την αναπαράγει με την ίδια σειρά, επειδή η συγχώνευση 12 συνδυάζει τα αποτελέσματα των συγχωνεύσεων 5 και 1. Εφαρμόστε τες με διαφορετική σειρά και θα πάρετε διαφορετικό, λανθασμένο tokenization που δεν θα ταιριάζει με τίποτα από όσα είδε το μοντέλο στην εκπαίδευση.

    def encode(self, text):
        ids = list(text.encode("utf-8"))
        while len(ids) >= 2:
            stats = get_stats(ids)
            # the pair whose merge came FIRST during training wins   
            pair = min(stats, key=lambda p: self.merges.get(p, float("inf")))   
            if pair not in self.merges:
                break
            ids = merge(ids, pair, self.merges[pair])
        return ids

    def decode(self, ids):
        return b"".join(self.vocab[i] for i in ids).decode("utf-8", errors="replace")

Η αποκωδικοποίηση είναι ασήμαντη σε σύγκριση: βρίσκετε τα bytes κάθε id, τα συνενώνετε, τα αποκωδικοποιείτε ως UTF-8. Προσέξτε το errors="replace": ένα μοντέλο μπορεί να εκπέμψει μια ακολουθία token που τελειώνει στη μέση ενός χαρακτήρα, και αυτό δεν είναι υποθετικό — είναι αυτό που συμβαίνει όταν μια streaming απόκριση κόβεται στη μέση ενός emoji, γι’ αυτό τα streaming APIs κάνουν buffer σε μερικά bytes αντί να αποκωδικοποιούν token προς token.

Το round-trip δουλεύει σε οτιδήποτε, και αυτή είναι η υπόσχεση του byte-level BPE:

'strawberry'                            -> 6 tokens, decode == original: True
'Alice was beginning to get very tired' -> 14 tokens, decode == original: True
'café — naïve — 日本語'                   -> 23 tokens, decode == original: True

Μόλις ο μηχανισμός γίνει σαφής, ένα σύνολο φαινομενικά άσχετων παραπόνων αποδεικνύεται ότι είναι το ίδιο παράπονο.

Αριθμητική. Οι αριθμοί δεν χωρίζονται με κανέναν συνεπή τρόπο:

1234     -> 2 tokens  ['123', '4']
12345    -> 2 tokens  ['123', '45']
1000000  -> 3 tokens  ['100', '000', '0']
3.14159  -> 4 tokens  ['3', '.', '141', '59']
2024     -> 2 tokens  ['202', '4']

Για να προσθέσει το 1234 και το 12345, το μοντέλο πρέπει πρώτα να καταλάβει ότι τα ['123','4'] και ['123','45'] είναι αριθμοί των οποίων τα ψηφία ευθυγραμμίζονται με συγκεκριμένο τρόπο — και η ευθυγράμμιση διαφέρει για κάθε ζεύγος αριθμών. Τα ψηφία ενός αριθμού δεν βρίσκονται στις ίδιες θέσεις από τον έναν αριθμό στον επόμενο. Μερικοί νεότεροι tokenizers αναγκάζουν τα ψηφία να χωρίζονται σε συνεπείς ομάδες των τριών ακριβώς για να αφαιρέσουν αυτό το εμπόδιο, και τα μοντέλα που εκπαιδεύονται με αυτούς είναι μετρήσιμα καλύτερα στην αριθμητική.

Εσοχές Python.

'    x = 1'      -> 5 tokens  ['   ', ' x', ' =', ' ', '1']
'        x = 1'  -> 5 tokens  ['       ', ' x', ' =', ' ', '1']
'\tx = 1'        -> 4 tokens  ['\tx', ' =', ' ', '1']

Τέσσερα κενά και οκτώ κενά είναι διαφορετικά μεμονωμένα token, και ένα tab συγχωνεύεται με τον χαρακτήρα μετά από αυτό. Η εσοχή, που στην Python είναι σύνταξη, αναπαρίσταται ασυνεπώς — και αυτό είναι μεγάλο μέρος του λόγου για τον οποίο τα μοντέλα παλιότερα παρήγαγαν Python με ανεπαίσθητα λανθασμένες εσοχές, και γιατί οι tokenizers που εστιάζουν στον κώδικα προσθέτουν ρητά token για συνηθισμένες ακολουθίες εσοχής.

Ορθογραφία και αντιστροφή. Ίδια αιτία με το μέτρημα των r: το να ζητάτε από ένα μοντέλο να αντιστρέψει το strawberry σημαίνει να του ζητάτε να αναδιατάξει γράμματα μέσα σε τρία αδιαφανή ids. Τα μοντέλα το κάνουν επειδή έχουν απομνημονεύσει ορθογραφίες κατά την εκπαίδευση, όχι επειδή κοιτάζουν, γι’ αυτό το κάνουν καλά για συχνές λέξεις και άσχημα για σπάνιες.

Glitch tokens. Η πιο εντυπωσιακή περίπτωση είναι το SolidGoldMagikarp και ένα σύνολο παρόμοιων συμβολοσειρών που έκαναν τα GPT-2 και GPT-3 να συμπεριφέρονται παράξενα — να αρνούνται να τις επαναλάβουν, να παράγουν άσχετη έξοδο, μερικές φορές να προσβάλλουν τον χρήστη. Η εξήγηση είναι πεζή και προκύπτει απευθείας από το γεγονός ότι ο tokenizer εκπαιδεύεται ξεχωριστά από το μοντέλο: αυτές οι συμβολοσειρές ήταν συχνές στο corpus εκπαίδευσης του tokenizer (ήταν ονόματα χρηστών Reddit), οπότε κέρδισαν το δικό τους token, αλλά ήταν σπάνιες ή απούσες στο corpus εκπαίδευσης του μοντέλου. Το αποτέλεσμα είναι μια γραμμή embedding που αρχικοποιήθηκε τυχαία και σχεδόν ποτέ δεν ενημερώθηκε. Το μοντέλο έχει ένα σύμβολο που ουσιαστικά δεν έχει δει ποτέ, και η συμπεριφορά του εκεί είναι ό,τι έτυχε να είναι η τυχαία αρχικοποίηση.

Ένας tokenizer είναι μια απωλεστική διεπαφή ανάμεσα σε κείμενο και αριθμούς, και κάθε παράξενη συμπεριφορά σε αυτό το κεφάλαιο είναι η διεπαφή που φαίνεται. Αξίζει να είναι σαφές ότι η ανταλλαγή είναι σκόπιμη: το byte-level BPE σημαίνει ότι καμία είσοδος δεν είναι ποτέ μη αναπαραστάσιμη, οι ακολουθίες είναι τέσσερις έως πέντε φορές μικρότερες απ’ ό,τι θα ήταν με χαρακτήρες, και οι συχνές λέξεις φτάνουν ακέραιες.

Το τίμημα είναι ότι τα άτομα του μοντέλου δεν είναι τα δικά μας άτομα. Συλλογίζεται για κείμενο που δεν μπορεί να συλλαβίσει, σε μονάδες επιλεγμένες από μια καταμέτρηση συχνοτήτων πάνω σε ένα corpus που δεν είδε, με κόστος ανά γλώσσα που κανείς δεν διαπραγματεύτηκε.

Τώρα έχετε μια ακολουθία ακεραίων. Αυτή είναι η μορφή εισόδου για όλα τα υπόλοιπα στο Μέρος II.

Αυτό που δεν έχετε είναι κάποιος λόγος για τον οποίο ένας ακέραιος πρέπει να ακολουθεί έναν άλλο. Το επόμενο κεφάλαιο εισάγει τον στόχο πάνω στον οποίο εκπαιδεύεται κάθε γλωσσικό μοντέλο, και είναι εντυπωσιακά απλός: με δεδομένα τα token μέχρι τώρα, προβλέψτε το επόμενο. Αυτός ο ένας στόχος —χωρίς labels, χωρίς annotation, μόνο κείμενο με το ίδιο του το μέλλον ως στόχο— είναι αυτό που μετατρέπει ολόκληρο το διαδίκτυο σε δεδομένα εκπαίδευσης, και είναι το σημείο από όπου προέρχονται οι πρώτες γνήσιες αναπαραστάσεις του μοντέλου.

Απαιτεί επίσης ο κανόνας αλυσίδας της πιθανότητας από το Κεφάλαιο 2 να είναι απολύτως σωστός, επειδή ο ισχυρισμός ότι η πρόβλεψη ενός token κάθε φορά είναι το ίδιο με τη μοντελοποίηση ολόκληρων εγγράφων είναι παραγοντοποίηση, όχι μεταφορά.

Το Κεφάλαιο 8 είναι ο αυτοπαλίνδρομος στόχος, τα embeddings, και το πρώτο μέρος όπου ένα μοντέλο μαθαίνει κάτι που κανείς δεν έβαλε εκεί.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) εισάγει το μοντέλο Unigram· Kudo and Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) είναι η υλοποίηση που χρησιμοποιούν τα περισσότερα πολυγλωσσικά μοντέλα· Schuster and Nakajima, Japanese and Korean Voice Search (ICASSP 2012) είναι η προέλευση του WordPiece. Το Let's build the GPT Tokenizer του Andrej Karpathy και το συνοδευτικό repository karpathy/minbpe είναι οι άμεσοι πρόγονοι του κώδικα σε αυτό το κεφάλαιο και πηγαίνουν πολύ πιο μακριά, συμπεριλαμβάνοντας το regex του GPT-4 και τον χειρισμό special-token. Το Κεφάλαιο 6 του Hugging Face LLM Course καλύπτει τους τρεις αλγορίθμους πλάι πλάι με παραδείγματα.