WordPiece and SentencePiece

4.2.3 · AI-ML › Tokenization & Language Modeling

Overview

WordPiece aur SentencePiece subword tokenization algorithms hain jo words ko chhote pieces mein todkar vocabulary size aur coverage ke beech balance banate hain. Ye out-of-vocabulary (OOV) problem solve karte hain aur saath mein vocabulary ko manageable bhi rakhte hain.

Subword kyun? Character-level bahut granular hota hai (lambi sequences), word-level mein infinite vocabulary hoti hai. Subword inka Goldilocks zone hai.

[!intuition] Core Intuition

Socho tum English seekh rahe ho aur "unbreakable" word milta hai. Agar tum "un-", "break", aur "-able" jaante ho, toh poora word pehle kabhi na dekha ho tab bhi meaning guess kar sakte ho. Subword tokenization model ko yahi compositional skill sikhata hai.

Key insight yeh hai: Frequent words poore rehte hain ("the", "and"), rare words meaningful pieces mein split ho jaate hain ("playing" → "play" + "##ing"). Model implicitly morphology seekh leta hai.

[!definition] WordPiece (Google/BERT)

WordPiece ek likelihood-based (PMI-weighted) subword algorithm hai jo BERT ke liye develop kiya gaya tha. Yeh raw-frequency based nahi hai — yeh wo merge choose karta hai jisse corpus likelihood unigram model ke under sabse zyada badhti hai.

Algorithm (Training):

1. Vocabulary initialize karo sabhi characters + special tokens ke saath ([UNK], [CLS], [SEP], [MASK])
2. Repeat karo jab tak vocabulary target size tak na pahunche (jaise 30K):
   • Corpus mein har consecutive token pair ke liye, calculate karo ki unhe merge karne se likelihood kitni badhegi
   • Jo pair likelihood sabse zyada badhaye wo naya token ban jaata hai
   • Use vocabulary mein ## prefix ke saath add karo agar wo word-initial nahi hai

Frequency nahi, likelihood kyun? Hum chahte hain wo tokenization jo training corpus ko unigram language model ke under sabse probable banaye (har token independent, koi context nahi). Unigram model ke under corpus log-likelihood yeh hai:

$\mathcal{L}={\sum }_{i=1}^N\log P(w_i)$

Dhyan do ki isme koi context term $P(w_i\mid \text{context})$ nahi hai — har token independently $\log P(w_i)$ contribute karta hai. Pair $(a,b)\to ab$ ko merge karna $\mathcal{L}$ badalta hai, aur WordPiece wo merge choose karta hai jisme sabse zyada gain ho (jo PMI-weighted nikalta hai, neeche dekho).

BPE se contrast: BPE wo pair merge karta hai jiska raw count sabse zyada hai; WordPiece wo pair merge karta hai jo likelihood gain maximize kare. Woh gain un pairs ko reward karta hai jo chance se zyada co-occur karte hain, sirf zyada baar nahi.

Tokenization (Inference):

• Greedy longest-match: Har word ki shuruaat se, vocabulary mein sabse lamba subword lo, phir repeat karo
• Non-initial pieces mark karne ke liye ## use karo: "playing" → ["play", "##ing"]

Key properties:

• Hamesha whitespace se separated words se shuru karta hai
• Kabhi word boundaries cross nahi karta
• Pre-tokenized input chahiye (space-separated)

[!definition] SentencePiece (Google/T5)

SentencePiece ek language-agnostic, unsupervised text tokenizer hai jo input ko raw stream ki tarah treat karta hai.

"Language-agnostic" kyun? Bahut saari languages (Chinese, Japanese, Thai) mein spaces nahi hote. SentencePiece directly raw text par kaam karta hai, whitespace ko special token ▁ (U+2581) ki tarah treat karta hai.

Algorithm choices:

1. BPE mode (Byte-Pair Encoding): Most frequent pairs ko iteratively merge karo
2. Unigram mode (default): Badi vocabulary se shuru karo, jo tokens likelihood loss minimize karein unhe prune karo

Important: SentencePiece unigram mein ## prefix use nahi hota. Saare tokens plain substrings hote hain; word boundaries sirf ▁ marker se recover kiye jaate hain.

Unigram derivation first principles se:

Maano har token $x_i$ independently sampled hai (unigram assumption):

$P(\text{sentence})={\prod }_{i=1}^{n}P(x_i)$

Log-likelihood:

$\mathcal{L}={\sum }_{i=1}^n\log P(x_i)$

Training objective: Vocabulary $V$ aur token probabilities $P(x)$ dhundho jo corpus mein $\mathcal{L}$ maximize kare.

EM algorithm:

1. E-step: Har word ke liye, saare possible segmentations enumerate karo, current $P(x)$ use karke har segmentation ki probability compute karo, aur forward-backward ke through har token ke expected (soft) counts nikalo
2. M-step: $P(x)$ update karo = ($x$ ka expected count) / (total expected counts)
3. Prune: Jo tokens $\mathcal{L}$ ko sabse kam hurt karein unhe remove karo, target vocabulary size tak repeat karo

Yeh kyun kaam karta hai: Frequent subwords ko high $P(x)$ milta hai, isliye segmentations mein unhe prefer kiya jaata hai. Rare subwords prune ho jaate hain.

Key properties:

• Reversible: tokens → original text exactly (kyunki ▁ spaces encode karta hai)
• Pre-tokenization ki zarurat nahi
• Kisi bhi language ko handle kar sakta hai

[!formula] Likelihood-Based Merging (WordPiece)

Merge candidate $(a,b)$ ke liye:

$\Delta \mathcal{L}(a,b)=\text{count}(ab)\cdot \log \frac{P(ab)}{P(a)\cdot P(b)}$

Derivation:

Merge se pehle: segments $(a,b)$ do tokens ki tarah appear karte hain ${\mathcal{L}}_{\text{before}}=\text{count}(ab)\cdot [\log P(a)+\log P(b)]$

Merge ke baad: ye ek token $ab$ ki tarah appear karte hain ${\mathcal{L}}_{\text{after}}=\text{count}(ab)\cdot \log P(ab)$

Likelihood gain: $\Delta \mathcal{L}={\mathcal{L}}_{\text{after}}-{\mathcal{L}}_{\text{before}}=\text{count}(ab)\cdot \log \frac{P(ab)}{P(a)\cdot P(b)}$

Yeh frequency se weighted pointwise mutual information (PMI) hai. Isliye WordPiece frequency-based nahi hai: ek pair frequent ho sakta hai par low PMI ho sakta hai (agar $a$ aur $b$ independently common hain), toh use pehle merge nahi kiya jaayega.

Yeh maximize kyun karein? High PMI ka matlab hai $a$ aur $b$ chance se zyada co-occur karte hain → ye ek meaningful unit banate hain.

[!example] Worked Example 1: WordPiece Tokenization

Input: "unhappiness"

Vocabulary: ["un", "##happ", "##i", "##ness", "happiness"]

Step-by-step greedy longest-match:

1. Position 0 se shuru karo
2. "unhappiness" try karo → vocab mein nahi
3. "unhappine" try karo → vocab mein nahi
4. "unhapi" try karo → vocab mein nahi
5. "unhapp" try karo → vocab mein nahi
6. "unhap" try karo → vocab mein nahi
7. "unha" try karo → vocab mein nahi
8. "unh" try karo → vocab mein nahi
9. "un" try karo → mila! ✓
10. Position 2 par jao, ab "happiness" process karo
11. "happiness" try karo → mila! ✓

Output: ["un", "happiness"]

Yeh step kyun? Greedy longest-match ensure karta hai ki hum sabse bade possible chunks use karein, sequence length kam ho.

[!example] Worked Example 2: SentencePiece with Spaces

Input: "Hello world"

SentencePiece vocabulary: ["▁", "▁H", "ello", "▁w", "orld"]

Tokenization:

• "Hello world" → space ko ▁ maano → "▁Hello▁world"
• Segment: ["▁H", "ello", "▁w", "orld"]

Detokenization:

• ["▁H", "ello", "▁w", "orld"] → "▁Hello▁world" → ▁ ko space se replace karo → "Hello world"

▁ kyun? Yeh tokenization ko reversible banata hai. Tum hamesha original text exactly reconstruct kar sakte ho, leading/trailing spaces samet.

[!example] Worked Example 3: SentencePiece Unigram E-step

Corpus: ek single word "dogs" count 1 ke saath (clarity ke liye chhota rakha).

Vocabulary (plain substrings, koi ## prefix nahi): ["d", "o", "g", "s", "do", "dog", "gs", "dogs"]

Current token probabilities (ek previous M-step se):

E-step — "dogs" ke segmentations enumerate karo aur har ek score karo:

1. ["dog", "s"] → $0.40\times 0.20=0.0800$ Yeh step kyun? Independent token probabilities ka product (unigram assumption).
2. ["do", "g", "s"] → $0.10\times 0.10\times 0.20=0.0020$
3. ["d", "o", "gs"] → $0.05\times 0.05\times 0.05=0.000125$
4. ["dogs"] → $0.05$
5. ["d", "o", "g", "s"] → $0.05\times 0.05\times 0.10\times 0.20=0.00005$

Normalize karo (sum $Z=0.0800+0.0020+0.000125+0.05+0.00005=0.132275$):

Har token ke expected (soft) counts = un segmentations ke posterior weights ka sum jo us token ko contain karte hain:

• $E[\text{dog}]=0.605$
• $E[\text{s}]=0.605+0.00038\approx 0.605$ (seg 1 aur 5 se)
• $E[\text{dogs}]=0.378$
• $E[\text{do}],E[\text{g}],E[\text{gs}],E[\text{d}],E[\text{o}]$ ≈ bahut chhota

Forward-backward kyun? Lambe words ke liye segmentations ki sankhya exponential ho jaati hai; forward-backward in expected counts ko linear time mein compute karta hai bina sab enumerate kiye. M-step phir in expected counts ko normalize karke naya $P(x)$ banata hai, aur low-count tokens (jaise do, gs) baad ke rounds mein prune ho jaate hain.

Key takeaway: Yeh saare segmentations mein soft, probabilistic assignment hai — WordPiece ke hard greedy merge se bilkul alag, aur yeh plain substrings use karta hai, ##-prefixed pieces nahi.

[!mistake] Common Mistake 1: BPE aur WordPiece ko Confuse Karna

Galat idea: "WordPiece aur BPE same hain kyunki dono frequent pairs merge karte hain."

Yeh sahi kyun lagta hai: Dono pairs par greedy merge algorithms hain.

Fix yeh hai:

• BPE wo pair merge karta hai jiska sabse zyada frequency ho (simple count)
• WordPiece wo pair merge karta hai jisse sabse zyada likelihood increase ho (PMI weighted)

Example: Maano ("e", "r") 100 baar aata hai, ("er", "s") 50 baar. BPE ("e", "r") pehle merge karta hai. Lekin agar ("er", "s") ka PMI bahut high hai (ye almost hamesha saath hote hain), toh WordPiece ("er", "s") pehle merge kar sakta hai kyunki yeh likelihood zyada badhata hai.

Formula difference:

BPE: $\arg {\max }_{(a,b)}\text{count}(a,b)$

WordPiece: $\arg {\max }_{(a,b)}\text{count}(ab)\cdot \log \frac{P(ab)}{P(a)\cdot P(b)}$

[!mistake] Common Mistake 2: Yeh Sochna ki SentencePiece Spaces Handle Nahi Kar Sakta

Galat idea: "SentencePiece un languages ke liye hai jisme spaces nahi hote, isliye English mein kaam nahi karta."

Yeh sahi kyun lagta hai: Documentation mein "language-agnostic" aur Chinese examples par zyada zor diya jaata hai.

Fix yeh hai: SentencePiece spaces ko WordPiece se behtar handle karta hai kyunki yeh unhe explicitly ▁ ke roop mein encode karta hai. Tum original text perfectly reconstruct kar sakte ho, multiple spaces ya leading spaces samet.

Example:

• Input: " Hello world " (multiple spaces dhyan do)
• WordPiece: Pre-tokenization spaces normalize karta hai → information loss
• SentencePiece: har space ko apna ▁ encode karta hai, fully reversible

[!mistake] Common Mistake 3: SentencePiece mein ## Daalna

Galat idea: "SentencePiece unigram tokens non-initial pieces ke liye ## use karte hain, jaise WordPiece."

Yeh sahi kyun lagta hai: Dono Google ke subword tokenizers hain, isliye log assume karte hain ki notation shared hai.

Fix yeh hai: ## sirf WordPiece convention hai. SentencePiece tokens plain substrings hote hain; word/space information poori tarah ▁ marker se carry hoti hai. Isliye ek SentencePiece vocabulary aisi dikhti hai ["▁the", "▁dog", "s"], kabhi ["the", "##s"] nahi.

[!recall]- Ek 12-saal ke baache ko Explain Karo

Socho tum texting ke liye ek dictionary bana rahe ho. Tum chahte ho yeh chhoti ho (taaki phone mein fit ho), lekin tum koi bhi word likhna bhi chahte ho.

WordPiece aisa hai: "Common cheezein jaise 'the' aur 'cat' ke liye poore words rakhte hain. Lekin agar koi 'supercalifragilisticexpialidocious' text kare, toh hum ise un pieces mein todenge jo humne pehle dekhe hain: 'super', 'cali', 'fragi', etc."

Trick yeh hai: Hum sirf wahi pieces nahi chunte jo zyada dikhte hain — hum woh pieces chunte hain jo saath belong karte hain. Agar "play" aur "ing" ek doosre ke aage zyada baar aate hain jitna luck se expect karein, toh hum unhe "playing" mein jod dete hain. (Yeh "luck se zyada" waala idea PMI kehlata hai.)

SentencePiece aur bhi smart hai: pehle words todne ki jagah, yeh spaces ko bhi ek character ki tarah treat karta hai (hum ise ▁ likhte hain). Yeh Chinese (no spaces) aur English (bahut saare spaces) ke liye ek hi tarah kaam karta hai. Aur tum hamesha ulta ja sakte ho — pieces ko wapas exact original message mein badal sakte ho.

[!mnemonic] Memory Hook

WordPiece: Word-boundary aware (kabhi spaces cross nahi karta, ## use karta hai) SentencePiece: Sentence-level raw (spaces ko ▁ maanta hai, koi ## nahi, koi pre-tokenization nahi)

PMI = "Pair Must Integrate" → WordPiece un pairs ko merge karta hai jo saath belong karte hain (high mutual information, sirf high frequency nahi)

Unigram = "You Need Independence Guess Repeatedly And Modify" → EM algorithm independent token probabilities par iterate karta hai

Connections

• Byte-Pair Encoding (BPE): WordPiece raw frequency ki jagah likelihood/PMI use karta hai
• Tokenization Fundamentals: Subword character aur word ke beech ka middle ground hai
• BERT Architecture: 30K vocabulary ke saath WordPiece use karta hai
• T5 and mT5: 100+ languages ke liye SentencePiece unigram use karte hain
• Out-of-Vocabulary Problem: Subword tokenization OOV eliminate karta hai
• Morphology and Compositionality: Subwords implicitly morphemes capture karte hain
• Pointwise Mutual Information: WordPiece merging ke peeche ka math
• Expectation Maximization: SentencePiece unigram training ko power deta hai

Flashcards

Concept Map