IN440- Summary

md3 min readSummary of IN440

Vocabulary

  • Vocabulary: All unique words.
  • Type: Unique word.
  • Token/Instance: Each occurrence of a word in text.
  • Normalization: The process of transforming text into a cleaner and more consistent form.

Morphenes

  • Morpheme: The smallest unit of meaning in a language. For example:

    • cats = cat + s
    • careful = care + ful
    • washing = wash + ing
  • Types of Morphemes

    • Inflectional morphemes: Change grammatical form only (e.g., tense, number, case)
    • Derivational morphemes: Create new words (e.g., organize → organization, careful → carefully)
    • Clitics: Attached reduced forms (e.g. I've, can't)

Stemming and Lemmatization

  • Stemming: Fast heuristic truncation, (e.g., studies → studi, caring, car):

    • Output may NOT be a valid word.
    • Advantages:
      • Fast
      • Simple
    • Disadvantages:
      • Less accurate
      • May lose meaning
  • Lemmatization: Uses dictionaries + linguistic knowledge + POS tags, (e.g., wolves → wolf, caring → care):

    • Output is a valid word.
    • Advantages:
      • Linguistically correct
      • Preserves semantics
    • Disadvantages:
      • Slower
      • Computationally expensive
  • So in Short:

    • Stemming = speed
    • Lemmatization = accuracy

Tokenization

  • Tokenization: splitting text into smaller units called tokens, example:
    • Input: "I need some help"
    • Output: ["I", "need", "some", "help"]

Rule Based Tokenization

  • Early tokenization systems relied on handcrafted rules to define word boundaries.

  • One of the most famous examples is the Penn Treebank Tokenizer.

  • It handles:

    • Punctuation separation
    • Contractions
    • Clitics
    • Sentence-ending periods
  • Example:

    • Input: "doesn't charge $10."
    • Output: ["does", "n't", "charge", "$", "10", "."]
  • Advantages:

    • Deterministic
    • Simple
    • Fast
  • Disadvantages:

    • Language-specific
    • Difficult to generalize
    • Many edge cases remain

Statistical Tokenization

  • Instead of handcrafted rules, statistical tokenizers learn token boundaries from data.

  • They use:

    • Context
    • Frequencies
    • Probabilities
  • Examples:

    • Punkt Tokenizer
    • BPE (Byte Pair Encoding)
    • HMM / CRF-based segmentation
  • Advantages:

    • More adaptable
    • Better cross-language support
    • Handles ambiguity better
  • Disadvantages:

    • Requires training data
    • More computationally expensive

Word-Level Tokenization Limitations

  • Word-level tokenization has two major problems:

1. Vocabulary Explosion

  • Vocabulary size grows continuously as more text is processed.

  • Every variation becomes a new token.

  • Example:

    • run
    • runs
    • running
    • runner

2. Unknown Words [UNK]

  • Models cannot store every possible word.

  • Unseen words become [UNK] (unknown token).

  • Example:

    • Training Vocabulary = {i, love, nlp}
    • Input = "I love transformers"
    • Output = ["i", "love", "[UNK]"]
  • Problems caused by [UNK]:

    • Loss of semantic meaning
    • Different unknown words become indistinguishable

Subword Tokenization

  • Instead of splitting by full words, subword tokenization splits words into smaller reusable units.

  • Example:

    • transformer-based
    • → ["transform", "##er", "-", "based"]
  • Advantages:

    • Eliminates most [UNK] problems
    • Fixed vocabulary size
    • Captures morphology
    • Handles rare words better

Modern Tokenizers

Byte Pair Encoding (BPE)

  • Originally a data compression algorithm adapted for NLP.

  • Used in models like:

    • GPT
    • LLaMA
  • Process:

    1. Start with characters
    2. Find the most frequent adjacent pair
    3. Merge them
    4. Repeat for k merges
  • Example:

    • n + e → ne
    • ne + w → new
  • Advantages:

    • Efficient
    • Reduces OOV words
    • Learns reusable subwords automatically

WordPiece

  • Similar to BPE but chooses merges using probability instead of raw frequency.
  • Used by:
    • BERT
    • DistilBERT

Unigram Language Model (ULM)

  • Starts with a large vocabulary.
  • Removes tokens with the least contribution to likelihood.

Sentence Segmentation

  • Sentence segmentation is the task of detecting sentence boundaries.

  • Example:

    • Input:
      • "Dr. Smith arrived at 5 p.m. He left early."
    • Naive splitting on "." fails.
  • Common punctuation:

    • .
    • ?
    • !
  • Challenges:

    • Abbreviations (Dr., Inc.)
    • Decimal numbers (4.3, 0.02%)
    • Titles and initials

Sentence Segmentation Methods

Rule-Based

  • Uses handcrafted rules.

  • Example:

    • Stanford CoreNLP Sentence Splitter
  • Core rules:

    • ., !, ? may end a sentence
    • Ignore periods in abbreviations
    • Ignore periods in numbers
    • Ignore periods after initials

Statistical Methods

  • Learn sentence boundaries from data.

Punkt Tokenizer

  • Unsupervised sentence tokenizer.

  • Learns:

    • Abbreviations
    • Sentence starters
    • Context around punctuation
  • Decision factors:

    • Is the token frequently abbreviated?
    • Does the next token look like a sentence start?
    • Is capitalization consistent?
  • Advantages:

    • Language-adaptive
    • No labeled data required
  • Limitations:

    • Needs enough training text
    • Domain-specific abbreviations may fail
    • Weak on informal text (tweets/chats)