Rakenna BPE-tokenizer: miksi mallisi ei osaa laskea R-kirjaimia

On kaksi ilmeistä tapaa syöttää tekstiä verkolle, ja molemmat epäonnistuvat syistä, jotka kannattaa ymmärtää, koska epäonnistuminen määrittää ratkaisun muodon.

Sanat. Jaetaan välilyönneistä ja annetaan jokaiselle sanalle numero. Englannissa on satojatuhansia sanamuotoja, ja malli tarvitsee embedding-rivin jokaiselle, joten sanasto — ja output-kerros, jonka on tuotettava pistemäärä jokaiselle alkiolle — kasvaa valtavaksi. Vielä pahempaa on se, mitä tapahtuu inference-vaiheessa: sanalla, jota malli ei koskaan nähnyt koulutuksessa, ei ole numeroa. Se on out-of-vocabulary-ongelma, ja tavallinen paikkaus on mapata kaikki tuntematon yhdeksi <UNK> token -yksiköksi, mikä heittää informaation pois. Lisäksi "sana" ei ole hyvin määritelty käsite: kiina ja japani eivät laita välilyöntejä sanojen väliin, ja saksa voi liittää substantiiveja toisiinsa loputtomasti.

Merkit. Ei out-of-vocabulary-ongelmaa, ja sanasto on vain sadan parin symbolin kokoinen. Mutta sekvensseistä tulee hyvin pitkiä, ja luku 9 näyttää, että attention-kustannus kasvaa neliöllisesti sekvenssin pituuden mukana. 1000 sanan dokumentti on noin 5000 merkkiä — sekvenssi neljästä viiteen kertaa pidempi kuin sen tarvitsisi olla, neliöllisellä hinnalla. Ja jokainen merkki kantaa yksinään lähes olemattoman määrän merkitystä, joten ensimmäiset kerrokset kuluvat sanojen kokoamiseen uudelleen, vaikka tokenizer olisi voinut antaa ne eteenpäin kokonaisina.

Vastaus on niiden välissä: alisanat. Yleisistä sanoista tulee yksi token, harvinaiset sanat pilkkoutuvat osiin, eikä mikään ole koskaan tuntematonta, koska osat päätyvät lopulta yksittäisiin tavuihin. Kiinnostavaa on, ettei kukaan suunnittele pilkkomista. Tokenizer koulutetaan, samanlaisella datalla kuin malli, ja se oppii laskemalla, mitkä tavujonot esiintyvät yhdessä niin usein, että ne ansaitsevat oman numeronsa.

Algoritmi on vuodelta 1994, ja se oli pakkausalgoritmi. Philip Gage julkaisi sen C Users Journal -lehdessä tapana pienentää tiedostoja korvaamalla toistuvasti viereisten tavujen yleisin pari tavulla, jota datassa ei esiinny.¹ Se oli siellä kaksikymmentäkaksi vuotta, kunnes Sennrich, Haddow ja Birch ottivat sen konekäännösten käyttöön vuonna 2016 ratkaistakseen out-of-vocabulary-ongelman.² Nyt käytännössä jokainen suuri kielimalli lukee näin.

Koulutuslooppi toistaa neljää vaihetta:

Tässä on koko kouluttaja:

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

Aja se 151 191 tavulla englanninkielistä proosaa ja tulosta ensimmäiset kaksitoista merge-vaihetta sitä mukaa kuin ne tapahtuvat. Tämä kohta kannattaa lukea hitaasti, koska kukaan ei kertonut algoritmille mitään englannista:

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)

Listassa on kolme asiaa, joita kannattaa osoittaa.

Merge 12 on sana "the" — sitä edeltävän välilyönnin ja seuraavan välilyönnin kanssa yhtenä yksikkönä, löydettynä loopin kahdennellatoista iteraatiolla, vaikka looppi vain laskee pareja. Kukaan ei antanut sanakirjaa. Se on siellä, koska nuo viisi tavua esiintyvät yhdessä useammin kuin mitkään muut viisi englannissa.

Merge 3 ei ole tekstiä lainkaan. \xe2\x80 on typografisen välimerkin UTF-8-koodauksen kaksi ensimmäistä tavua — ajatusviivan, kaarevien lainausmerkkien. Algoritmilla ei ole aavistustakaan UTF-8:n olemassaolosta, ja se on juuri löytänyt uudelleen osan sen rakenteesta, koska monitavuiset koodaukset ovat rakenteensa vuoksi tavusekvenssejä, jotka esiintyvät aina yhdessä.

Useimmat varhaiset merge-vaiheet sisältävät välilyönnin, ja välilyönti on yleensä vasemmalla. Tästä syntyy yksi käytännön hämmentävimmistä käyttäytymismalleista, johon palaamme pian.

Jokainen merge tekee sekvenssistä lyhyemmän ja sanastosta suuremman. Kuinka pitkälle sitä kannattaa jatkaa, on oikea päätös, ja sen voi mitata — tässä samalla 151 191 tavulla:

Vähenevät rajahyödyt näkyvät selvästi. Tuplaus 512:sta 1024:ään ostaa 0,78 tavua per token; tuplaus 2048:sta 4096:een ostaa 1,07 — tässä paremmin vain siksi, että korpus on niin pieni, että pidemmät merge-vaiheet maksavat yhä itsensä takaisin. Oikeassa korpuksessa käyrä litistyy rajusti.

Suuremman sanaston kustannus ei ole vain muistia. Jokainen token tarvitsee embedding-rivin, ja — kalliimpana asiana — mallin output-kerroksen on tuotettava pistemäärä jokaiselle sanaston alkiolle jokaisessa vaiheessa, joten viimeinen matriisikertolasku skaalautuu sanaston koon mukana. Oikeat mallit ovat välillä 32 000–200 000: GPT-2 käytti 50 257:ää, GPT-4:n cl100k käyttää 100 277:ää, GPT-4o:n o200k noin kaksinkertaistaa sen. Suunta on ylöspäin, ja syy on seuraavassa osiossa.

Tässä on sama kappale käännettynä ja mitattuna oikeilla tokenizer-järjestelmillä, jotka OpenAI toimittaa:

Sama sisältö, sama merkitys, ja cl100k:lla venäjänkielinen versio kuluttaa kaksi ja puoli kertaa token-määrän. Koska API:t laskuttavat per token ja context window mitataan token-yksiköissä, se ei ole kielellinen kuriositeetti — se on budjettirivi, lyhyempi tehokas context window ja hitaampi vastaus, kaikki kolme kerralla, kaikille jotka eivät työskentele englanniksi.

Mekanismi on koulutusdata. Enimmäkseen englannilla koulutettu tokenizer käyttää merge-budjettinsa englannin tavusekvensseihin. Espanja jakaa latinalaisen aakkoston, joten se saa edelleen jonkin verran hyötyä; venäjä ei juuri lainkaan, koska kyrilliset merkit vievät UTF-8:ssa kaksi tavua ja vain harvat noista pareista olivat koulutuskorpuksessa niin yleisiä, että ne ansaitsivat merge-vaiheen. Japani on vielä pahempi: kolme tavua per merkki, ja 72 merkkiä muuttuu 79 token-yksiköksi — enemmän token-yksiköitä kuin merkkejä.

o200k-sarake näyttää, että ongelma on ratkaistavissa ja että sitä ratkaistaan. Sanaston kaksinkertaistaminen ja koulutusdatan uudelleentasapainotus leikkaa espanjan lisäkustannuksen +39 prosentista +16 prosenttiin ja venäjän +152 prosentista +39 prosenttiin. Siinä on todellinen syy, miksi sanastot kasvavat: ei pakkaus pakkaamisen vuoksi, vaan se, että edellinen sukupolvi veloitti hiljaa suurelta osalta maailmaa ylimääräistä.

Koulutus tuotti järjestetyn listan merge-vaiheista. Uuden tekstin koodaus toistaa sen — ja sen on toistettava se samassa järjestyksessä, koska merge 12 yhdistää merge-vaiheiden 5 ja 1 tulokset. Käytä niitä eri järjestyksessä ja saat erilaisen, väärän tokenisaation, joka ei vastaa mitään, mitä malli näki koulutuksessa.

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

Dekoodaus on tähän verrattuna triviaalia: hae kunkin id:n tavut, liitä ne yhteen, dekoodaa UTF-8:ksi. Huomaa errors="replace": malli voi emittoida token-sekvenssin, joka päättyy kesken merkin, eikä se ole hypoteettista — niin käy, kun streaming-vastaus katkeaa keskellä emojia, minkä vuoksi streaming-API:t puskuroivat osittaisia tavuja sen sijaan, että ne dekoodaisivat token kerrallaan.

Round-trip toimii millä tahansa, mikä on tavutason BPE:n lupaus:

'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

Kun mekanismi on selvä, joukko irrallisilta näyttäviä valituksia osoittautuu samaksi valitukseksi.

Aritmetiikka. Numeroita ei pilkota millään johdonmukaisella tavalla:

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']

Lisätäkseen 1234 ja 12345 mallin on ensin pääteltävä, että ['123','4'] ja ['123','45'] ovat numeroita, joiden numeromerkit kohdistuvat tietyllä tavalla — ja kohdistus eroaa jokaisella lukuparilla. Luvun numeromerkit eivät ole samoissa paikoissa luvusta toiseen. Jotkin uudemmat tokenizer-järjestelmät pakottavat numeromerkit jakautumaan johdonmukaisiin kolmen ryhmiin juuri tämän esteen poistamiseksi, ja niillä koulutetut mallit ovat mitattavasti parempia aritmetiikassa.

Pythonin sisennys.

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

Neljä välilyöntiä ja kahdeksan välilyöntiä ovat eri yksittäisiä token-yksiköitä, ja tabulaattori on sulautettu sitä seuraavaan merkkiin. Sisennys, joka Pythonissa on syntaksia, esitetään epäjohdonmukaisesti — mikä on iso osa siitä, miksi mallit tuottivat ennen Pythonia hienovaraisesti väärällä sisennyksellä, ja miksi koodiin keskittyvät tokenizer-järjestelmät lisäävät eksplisiittisiä token-yksiköitä yleisille sisennysjaksoille.

Tavutus ja kääntäminen takaperin. Sama syy kuin r-kirjainten laskemisessa: mallilta pyytäminen kääntämään strawberry takaperin on pyyntö järjestää uudelleen kirjaimia kolmen läpinäkymättömän id:n sisällä. Mallit tekevät sen muistamalla koulutuksessa opittuja kirjoitusasuja eivätkä katsomalla, minkä vuoksi ne onnistuvat yleisillä sanoilla hyvin ja harvinaisilla huonosti.

Glitch token. Silmiinpistävin tapaus on SolidGoldMagikarp ja joukko samankaltaisia merkkijonoja, jotka saivat GPT-2:n ja GPT-3:n käyttäytymään oudosti — kieltäytymään toistamasta niitä, tuottamaan asiaankuulumatonta outputia, joskus loukkaamaan käyttäjää. Selitys on arkinen ja seuraa suoraan siitä, että tokenizer koulutetaan erikseen mallista: nuo merkkijonot olivat yleisiä tokenizer-koulutuskorpuksessa (ne olivat Reddit-käyttäjänimiä), joten ne ansaitsivat oman token-yksikkönsä, mutta ne olivat harvinaisia tai puuttuivat mallin koulutuskorpuksesta. Tuloksena on embedding-rivi, joka alustettiin satunnaisesti ja jota ei juuri koskaan päivitetty. Mallilla on symboli, jota se ei ole käytännössä koskaan nähnyt, ja sen käyttäytyminen siinä kohdassa on mitä satunnainen alustus sattui olemaan.

Tokenizer on häviöllinen rajapinta tekstin ja numeroiden välillä, ja jokainen tämän luvun outo käyttäytyminen on rajapinnan läpikuultamista. On syytä olla selkeä siitä, että vaihto on tarkoituksellinen: tavutason BPE tarkoittaa, ettei mikään syöte ole koskaan esittämiskelvoton, sekvenssit ovat neljästä viiteen kertaa lyhyempiä kuin merkit olisivat, ja yleiset sanat saapuvat kokonaisina.

Hinta on, etteivät mallin atomit ole meidän atomejamme. Se päättelee tekstistä, jota se ei osaa tavata, yksiköissä, jotka valitaan taajuuslaskennalla korpuksesta, jota se ei nähnyt, ja kielikohtaisella kustannuksella, josta kukaan ei neuvotellut.

Sinulla on nyt kokonaislukujen sekvenssi. Se on syötemuoto kaikelle muulle osassa II.

Sinulla ei kuitenkaan ole mitään syytä, miksi yhden kokonaisluvun pitäisi seurata toista. Seuraava luku esittelee tavoitteen, jolla jokainen kielimalli koulutetaan, ja se on häkellyttävän yksinkertainen: annetuilla tähänastisilla token-yksiköillä ennusta seuraava. Tuo yksi tavoite — ei labeleita, ei annotaatiota, vain teksti ja sen oma tulevaisuus kohteena — on se, mikä muuttaa koko internetin koulutusdataksi, ja sieltä mallin ensimmäiset aidot representaatiot tulevat.

Se vaatii myös, että luvun 2 todennäköisyyden ketjusääntö on täsmälleen oikein, koska väite, että yhden token-yksikön ennustaminen kerrallaan on sama asia kuin kokonaisten dokumenttien mallintaminen, on faktorisaatio eikä metafora.

Luku 8 käsittelee autoregressiivistä tavoitetta, embedding-yksiköitä ja ensimmäistä kohtaa, jossa malli oppii jotain, mitä kukaan ei sinne laittanut.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) esittelee Unigram-mallin; Kudo ja Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) on toteutus, jota useimmat monikieliset mallit käyttävät; Schuster ja Nakajima, Japanese and Korean Voice Search (ICASSP 2012) on WordPiecen alkuperä. Andrej Karpathyn Let's build the GPT Tokenizer ja siihen liittyvä karpathy/minbpe-repositorio ovat tämän luvun koodin suoria esi-isiä ja menevät huomattavasti pidemmälle, mukaan lukien GPT-4:n regex ja special-token-käsittely. Hugging Face LLM Coursen luku 6 käsittelee kolmea algoritmia rinnakkain esimerkkien kanssa.