Токени и токенизация (BPE) в Java

Проблем

Речник от думи

Ботът на поддръжката трябва да чете съобщенията на клиентите. Моделът работи с числа, затова колега прави речник: всяка дума от текстовете на магазина получава номер. Ето кои текстове: отговори на поддръжката, бележки за доставка и отзиви.

// текстът на магазина: отговори на поддръжката, бележки за доставка, отзиви
static final String[] TEXT = {
    "поръчката ви е изпратена с куриер днес",
    "поръчката ще пристигне на адреса ви утре",
    "поръчката ще пристигне до три дни",
    "поръчката пристигна в офиса на куриер",
    "пратката ви е предадена на куриер",
    "пратката ще пристигне до два дни",
    "пратката ще бъде при вас утре",
    "пратката закъсня с един ден",
    "куриер ще дойде на адреса ви утре",
    "куриер ще ви се обади преди доставката",
    "доставката до адрес струва 5 евро",
    "доставката до офис на куриер струва 3 евро",
    "доставката е безплатна над 50 евро",
    "доставката отнема до два дни",
    "стоката ще пристигне в оригиналната опаковка",
    "можете да върнете стоката до 14 дни",
    "върнете стоката в оригиналната опаковка",
    "връщането на стоката е безплатно",
    "парите ще бъдат върнати до пет дни",
    "след връщането на стоката ще получите парите",
    "парите се връщат по картата ви",
    "можете да платите с карта или с наложен платеж",
    "плащането с карта е сигурно",
    "банката отказа плащането с вашата карта",
    "опитайте плащането с друга карта",
    "плащането ще бъде потвърдено от банката",
    "стоката пристигна бързо и е много добра",
    "много съм доволен от поръчката",
    "куриер беше любезен и бърз",
    "стоката е добра но доставката закъсня",
};

После всяко съобщение става редица от номера:

// речникът: всяка дума от текста получава номер
List<String> vocab = new ArrayList<>();
for (String line : TEXT)
    for (String word : line.split(" "))
        if (!vocab.contains(word))
            vocab.add(word);
System.out.println("речник: " + vocab.size() + " думи");
for (String message : new String[] {"пратката ще пристигне утре", "кога ще пристигне поръчка 1042"}) {
    List<String> ids = new ArrayList<>();
    for (String word : message.split(" ")) {
        int id = vocab.indexOf(word);
        ids.add(id >= 0 ? String.valueOf(id) : "?");
    }
    System.out.println(message + " → " + String.join(" ", ids));
}

речник: 84 думи
пратката ще пристигне утре → 18 7 8 11
кога ще пристигне поръчка 1042 → ? 7 8 ? ?

Първото съобщение минава. Във второто „кога“ и „1042“ ги няма в текста, а „поръчка“ е друга дума от „поръчката“. Моделът получава „?“ на три места от пет.

Речник от всички думи не става. Всяка дума има по няколко форми (поръчка, поръчката, поръчки, поръчките), а всеки ден идват нови: имена на продукти, номера, грешки при писане. А ако четеш по букви, всеки текст минава, но става много дълъг: 26 знака за пет думи.

Идеята

Парчета между буква и дума

Средата между буквите и думите са честите парчета: „ка“, „ата“, „пристиг“. Моделът чете текста като редица от такива парчета. Всяко парче се казва токен, а рязането на текст на токени е токенизация.

Кои парчета да станат токени, не се пише на ръка. Учи се от текст с алгоритъма BPE (byte pair encoding):

Всяка дума е списък от букви.
Преброй всички двойки съседи във всички думи. Една дума, която се среща 7 пъти, брои двойките си 7 пъти.
Най-честата двойка става едно парче: това е едно правило. Слепи я навсякъде.
Повтори от стъпка 2, колкото правила искаш.

Правилата се пазят по ред. Нов текст се реже със същите правила, в същия ред. Дума, която я няма в текста, пак минава: в най-лошия случай остава на букви. „?“ няма.

Виж го

60 правила от текста на магазина

Правилото е двойка токени и колко пъти е видяна. Думата започва като букви:

// едно правило: left и right един до друг стават един токен
record Rule(String left, String right, int count) {}

// думата като списък от букви
static List<String> letters(String word) {
    List<String> tokens = new ArrayList<>();
    for (char c : word.toCharArray())
        tokens.add(String.valueOf(c));
    return tokens;
}

Слепването минава по токените на една дума отляво надясно. Където left и right стоят един до друг, слага един токен вместо тях и прескача и двата:

// слепи всяко left, right едно до друго
static List<String> merge(List<String> tokens,
                          String left, String right) {
    List<String> glued = new ArrayList<>();
    int i = 0;
    while (i < tokens.size()) {
        if (i + 1 < tokens.size()
                && tokens.get(i).equals(left)
                && tokens.get(i + 1).equals(right)) {
            glued.add(left + right);
            i += 2;
        } else {
            glued.add(tokens.get(i));
            i += 1;
        }
    }
    return glued;
}

Ученето е четирите стъпки от предишната карта. LinkedHashMap пази реда на добавяне, затова при равенство печели двойката, видяна първа, и изходът е един и същ на четирите езика.

// научи count правила: всеки път слепи най-честата двойка
static List<Rule> learn(String[] text, int count) {
    Map<String, Integer> freq = new LinkedHashMap<>(); // колко пъти е всяка дума в текста
    for (String line : text)
        for (String word : line.split(" "))
            freq.merge(word, 1, Integer::sum);
    Map<String, List<String>> split = new LinkedHashMap<>(); // всяка дума засега е само букви
    for (String word : freq.keySet())
        split.put(word, letters(word));
    List<Rule> rules = new ArrayList<>();
    for (int r = 0; r < count; r++) {
        Map<String, Integer> pairs = new LinkedHashMap<>(); // двойките съседи, броени с честотата на думата
        for (String word : split.keySet()) {
            List<String> t = split.get(word);
            for (int i = 0; i + 1 < t.size(); i++)
                pairs.merge(t.get(i) + " " + t.get(i + 1), freq.get(word), Integer::sum);
        }
        String best = "";
        int most = 0;
        for (var pair : pairs.entrySet())
            if (pair.getValue() > most) { // най-честата двойка (при равенство първата видяна)
                best = pair.getKey();
                most = pair.getValue();
            }
        String[] lr = best.split(" ");
        rules.add(new Rule(lr[0], lr[1], most));
        split.replaceAll((word, t) -> merge(t, lr[0], lr[1])); // новото правило важи за всички думи
    }
    return rules;
}

List<Rule> rules = learn(TEXT, 60);
for (int k = 0; k < rules.size(); k++) {
    Rule r = rules.get(k);
    String cell = (k + 1) + ". " + r.left() + "+" + r.right() + " (" + r.count() + ")";
    System.out.print(k % 4 == 3 ? cell + "\n" : String.format("%-22s", cell));
}

1. а+т (40)           2. ат+а (28)          3. к+ата (24)         4. с+т (21)
5. р+и (20)           6. д+о (17)           7. н+а (16)           8. н+е (14)
9. щ+е (10)           10. т+е (10)          11. п+о (8)           12. р+ъ (8)
13. р+е (8)           14. п+л (8)           15. к+а (8)           16. к+у (7)
17. ку+ри (7)         18. кури+е (7)        19. курие+р (7)       20. п+ри (7)
21. и+г (7)           22. ст+о (7)          23. сто+ката (7)      24. в+и (6)
25. при+ст (6)        26. прист+иг (6)      27. д+е (6)           28. в+а (6)
29. до+ст (6)         30. дост+а (6)        31. доста+в (6)       32. достав+ката (6)
33. ъ+р (6)           34. щ+а (6)           35. ща+не (6)         36. щане+т (6)
37. щанет+о (6)       38. н+о (6)           39. по+ръ (5)         40. поръ+ч (5)
41. поръч+ката (5)    42. п+р (5)           43. пр+ат (5)         44. д+н (5)
45. дн+и (5)          46. п+а (5)           47. ка+р (5)          48. кар+т (5)
49. пристиг+не (4)    50. а+д (4)           51. прат+ката (4)     52. б+е (4)
53. пл+ат (4)         54. о+т (4)           55. в+ър (4)          56. карт+а (4)
57. пл+а (4)          58. пла+щането (4)    59. ад+ре (3)         60. адре+с (3)

Първото правило е „а“ + „т“: двойката е видяна 40 пъти. Второто слепва „ат“ с „а“, третото прави „ката“. Правилата строят върху предишните: „ку“, „кури“, „курие“, „куриер“ са четири правила подред, и след тях „куриер“ е един токен. След правило 41 и „поръчката“ е един токен.

Пробвай

Предвиди изхода

Ето първите три правила от изхода горе. Какво печата програмата?

List<Rule> rules = List.of(
    new Rule("а", "т", 40),
    new Rule("ат", "а", 28),
    new Rule("к", "ата", 24));
System.out.println(String.join("|", encode("картата", rules)));

Отговор

кар|т|ата

к|а|р|т|ата

к|ар|тата

Виж го

Нов текст на токени

Рязането на изречение: всяка дума става букви, после всяко правило поред. show само печата токените на всяка дума с | помежду им.

// изречение → токени: букви, после правилата поред
static List<String> encode(String sentence,
                           List<Rule> rules) {
    List<String> tokens = new ArrayList<>();
    for (String word : sentence.split(" ")) {
        List<String> t = letters(word);
        for (Rule r : rules)
            t = merge(t, r.left(), r.right());
        tokens.addAll(t);
    }
    return tokens;
}

// токените на всяка дума, с | помежду им
static String show(String sentence, List<Rule> rules) {
    List<String> parts = new ArrayList<>();
    for (String word : sentence.split(" "))
        parts.add(String.join("|", encode(word, rules)));
    return String.join("  ", parts);
}

Ето как едно изречение минава през правилата. Броячът долу казва колко са буквите и колко са токените:

// слепи всяко left, right едно до друго
static List<String> merge(List<String> tokens,
                          String left, String right) {
    List<String> glued = new ArrayList<>();
    int i = 0;
    while (i < tokens.size()) {
        if (i + 1 < tokens.size()
                && tokens.get(i).equals(left)
                && tokens.get(i + 1).equals(right)) {
            glued.add(left + right);
            i += 2;
        } else {
            glued.add(tokens.get(i));
            i += 1;
        }
    }
    return glued;
}

// изречение → токени: букви, после правилата поред
static List<String> encode(String sentence,
                           List<Rule> rules) {
    List<String> tokens = new ArrayList<>();
    for (String word : sentence.split(" ")) {
        List<String> t = letters(word);
        for (Rule r : rules)
            t = merge(t, r.left(), r.right());
        tokens.addAll(t);
    }
    return tokens;
}

Стъпка по стъпка, с думи

Всяка дума започва като букви: 23 плочки, 23 токена.
Правило 1: а + т. Където двете стоят едно до друго, стават един токен, във всяка дума.
Правило 2: ат + а → ата. Правило може да слепи токен, който по-ранно правило е направило.
Правила от 10 до 12 нямат какво да слепят тук, затова номерът скача на 13.
Правило 51: прат + ката. „пратката“ вече е един токен.
Всички 60 правила: 23 букви, 6 токена. „утре“ остава на 3 парчета: тази дума е рядка в текста.

List<Rule> rules = learn(TEXT, 60);
String[] sentences = {"пратката ще пристигне утре", "кога ще пристигне поръчка 1042", "рекламация за счупен телевизор"};
for (String s : sentences) {
    System.out.println(show(s, rules));
    int letters = s.replace(" ", "").length();
    System.out.println("  букви " + letters + ", токена " + encode(s, rules).size());
}

пратката  ще  пристигне  у|т|ре
  букви 23, токена 6
к|о|г|а  ще  пристигне  поръч|ка  1|0|4|2
  букви 26, токена 12
ре|к|л|а|м|а|ц|и|я  з|а  с|ч|у|п|е|н  те|л|е|ви|з|о|р
  букви 27, токена 24

Познатото изречение е 6 токена вместо 23 букви. „утре“ остава на три парчета: в текста е само три пъти, а правилата отиват за по-честите двойки. Във второто изречение „поръчка“ става „поръч|ка“, а „кога“ и „1042“ са на букви и цифри, но нито едно не е „?“.

Третото изречение е за рекламация, а такава дума в текста на магазина няма. 27 букви стават 24 токена: почти без слепване. Новият текст се чете, но струва повече токени.

Моделът вижда номерата на токените, както в речника от думи: всеки токен има номер в списъка на всички токени, а този списък е речникът на модела.

Пробвай

Попълни

С колко се мести i, когато left и right са слепени в един токен?

// слепи всяко left, right едно до друго
static List<String> merge(List<String> tokens,
                          String left, String right) {
    List<String> glued = new ArrayList<>();
    int i = 0;
    while (i < tokens.size()) {
        if (i + 1 < tokens.size()
                && tokens.get(i).equals(left)
                && tokens.get(i + 1).equals(right)) {
            glued.add(left + right);
            i += ;
        } else {
            glued.add(tokens.get(i));
            i += 1;
        }
    }
    return glued;
}

Идеята

Цената и лимитът са в токени

Моделът чете и пише токени. Затова всичко, което се мери при него, е в токени:

цената: доставчиците взимат пари на милион токена, отделно за входа и за отговора;
лимитът на входа: колко текст побира моделът наведнъж (това е прозорецът на контекста);
лимитът на отговора: колко токена може да напише, преди да спре.

Колегата смята цената по думи. Ето колко греши при същите три съобщения и примерна цена 3 € за милион токена:

List<Rule> rules = learn(TEXT, 60);
String[] messages = {"пратката ще пристигне утре", "кога ще пристигне поръчка 1042", "рекламация за счупен телевизор"};
int words = 0, tokens = 0;
for (String m : messages) {
    int w = m.split(" ").length, t = encode(m, rules).size();
    words += w;
    tokens += t;
    System.out.println(m + ": " + w + " думи, " + t + " токена");
}
System.out.printf("токени на дума: %.2f%n", (double) tokens / words);
double price = 3; // € за милион токена, примерна цена
int month = 200000;
System.out.println(month + " съобщения на месец, 3.00 € за милион токена (примерна цена):");
System.out.println("  по думи: " + String.format("%.2f €", month * ((double) words / messages.length) * price / 1e6));
System.out.println("  по токени: " + String.format("%.2f €", month * ((double) tokens / messages.length) * price / 1e6));

пратката ще пристигне утре: 4 думи, 6 токена
кога ще пристигне поръчка 1042: 5 думи, 12 токена
рекламация за счупен телевизор: 4 думи, 24 токена
токени на дума: 3.23
200000 съобщения на месец, 3.00 € за милион токена (примерна цена):
  по думи: 2.60 €
  по токени: 8.40 €

Сметката по думи е 2,60 €, а по токени 8,40 €: повече от три пъти. Най-много тежи рядкото съобщение: 4 думи, 24 токена. Цената е примерна, а точните числа идват от доставчика: отговорът на API казва колко токена са влезли и излезли. Как се пази бюджетът, е в урока за цената.

Пробвай

Намери грешката

Колега пише своя BPE и правилата му излизат други: „куриер“ така и не става един токен. На кой ред е грешката?

Избери реда с грешката.

Идеята

Кога вреди

Рядкото струва повече. Имена на продукти, номера на поръчки, грешки при писане и думи от друг език се режат на дребно. Истинските токенизатори са учени главно на английски текст, затова български текст обикновено излиза на повече токени от същия текст на английски.
Моделът не вижда буквите. „доставка“ за него е едно или две парчета, не осем букви. Затова броенето на букви, обръщането на дума и сметките с дълги числа му се удават лошо: „1042“ е четири токена, а при друг модел може да е два.
Всеки модел има свой токенизатор. Едно и също съобщение е различен брой токени при различни модели. Не смятай цената по думи и не я пренасяй от един модел на друг: брой с токенизатора на модела или чети колко токена е отчел API.
Отговорът може да спре по средата. Когато моделът стигне лимита на отговора, той спира на токена, до който е стигнал, дори да е по средата на думата. Виж упражнението.

По-точно, за любопитните

Байтове вместо букви. Токенизаторите на истинските модели обикновено са BPE върху байтовете на UTF-8, не върху буквите. Така всеки текст минава, дори емоджи и азбуки, които не са виждали. Кирилица е по 2 байта на буква, затова рядка българска дума може да излезе на повече токени, отколкото има букви.

Интервалът е част от токена. Тук всяка дума се реже отделно, а интервалите не се броят. Истинските токенизатори слепват интервала с думата след него: „ ще“ с интервала отпред е един токен. Затова „ще“ в началото на текста и „ще“ в средата са различни токени.

Колко са токените. Речникът на истински модел е примерно от 50 000 до 200 000 токена, научени от огромно количество текст. За английски грубото правило е един токен на около 4 знака. Има и специални токени, които не са текст, например „край на текста“.

Истинските инструменти. Готовите токенизатори са библиотеки: tiktoken и tokenizers на Hugging Face в Python, и техни версии за JavaScript, Java и C#. Работата с модели е предимно на Python, но токенизаторът е само таблица с правила, и правилата са същите на всеки език. SDK-тата на доставчиците имат и извикване, което брои токените на съобщение, преди да го пратиш.

Упражнение

Отговорът, отрязан на лимита

Реши задачата в редактора си.

Моделът пише отговора токен по токен и спира, когато стигне лимита на отговора. Направи същото: вземи отговора, режи го на токени дума по дума и спри след 6 токена. От отрязаната дума запази само токените, които са се събрали. Отпечатай колко токена е целият отговор и какво е останало до лимита.

отговорът: 11 токена
лимит 6, до лимита: пратката ви ще пристигне до д

„два“ е два токена, „д|ва“, а лимитът стига само за първия. Клиентът вижда „до д“ и не разбира колко дни. Затова програмата проверява дали отговорът е спрял на лимита, и или дава повече място, или моли модела за по-кратък отговор.

Още задачи

Повече правила. Научи 100 и 200 правила. Колко токена стават трите изречения от урока? Кога спира да има полза?
Най-скъпата дума. Намери думата от текста на магазина, която е най-много токени след 60 правила.

Тест

Провери се

1. Речникът от цели думи е виждал „поръчката“, но не „поръчка“. Какво прави BPE с „поръчка“?Реже я на познати парчета: „поръч“ и „ка“Добавя я в речника като нова думаВръща „?“, както речникът от думи

2. Защо правилата се прилагат върху нов текст в реда, в който са научени?Защото по-късното правило слепва токени, които по-ранните са направилиРедът няма значение, резултатът е същиятЗащото така е по-бързо

3. Колегата смята цената на бота по думи. Защо сметката излиза по-ниска от фактурата?Защото моделът брои буквитеЗащото интервалите също се плащатМоделът брои токени, а една дума често е няколко токена

4. Моделът казва, че в „пратката“ има две „а“, а те са три. Каква е най-вероятната причина?Моделът не знае азбукатаТемпературата е твърде високаМоделът вижда токени, а не отделни букви

Текстът на парчета: токени

Бисквитки