Natural Language Processing Questions

Tokenization is the process of splitting raw text into atomic units (tokens) that models consume. Choice of tokenization affects model vocabulary size, handling of rare/unknown words, and robustness to noise (e.g., typos, emojis).

Word-level tokenization

• What: Split on whitespace/punctuation into words (optionally lowercased, normalized).
• Use cases: Traditional NLP pipelines, small models, interpretable features (bag-of-words, classical classifiers).
• Advantages: Intuitive tokens, easy mapping to linguistic units.
• Disadvantages: Large vocabularies, many OOV (out-of-vocabulary) tokens for typos/slang; poor handling of morphology.
• Runtime/space: Fast to tokenize (linear scan); memory grows with vocabulary (millions for noisy social text) and embedding matrix large.

Character-level tokenization

• What: Tokens are individual characters (including punctuation, emojis).
• Use cases: Tasks with heavy misspellings, creative orthography, languages with large character sets, generative character models.
• Advantages: No OOV, robust to typos and unseen words, small fixed vocab (Unicode subset).
• Disadvantages: Longer sequences (slower models), harder to capture semantics across many chars, requires deeper/longer models to learn word-level meaning.
• Runtime/space: Low vocab-memory, higher compute cost due to longer sequence lengths (more RNN/attention steps).

Subword tokenization (BPE, WordPiece, Unigram)

• What: Split into frequent subword units learned from data (e.g., "play", "ing", "😊").
• Use cases: Modern transformers (BERT, GPT), production systems handling mixed vocabulary, social media where new words and emojis occur.
• Advantages: Balance between vocab size and OOV: can represent rare/compound words and emojis; efficient sequence length vs. char-level.
• Disadvantages: Tokenization can split common words unpredictably; training requires building a suitable vocabulary including emojis and special tokens.
• Runtime/space: Moderate vocab size (~30k–100k) and embedding cost; tokenization cost slightly higher than word-level but sequence lengths shorter than char-level.

For user-generated noisy text: subword tokenizers are typically best—they handle typos and emojis reasonably while keeping sequence length manageable. For extreme noise or morphology-heavy tasks, consider character-level or hybrid approaches (char + subword embeddings) to balance robustness and compute.

Brief overview: Handling OOVs depends on whether you use fixed (static) word embeddings or subword-based tokenizers. Strategies should balance accuracy, latency, and robustness to noisy orthography; for low-resource languages, prefer byte/character-aware approaches and lightweight normalization/augmentation.

Static embeddings (word-level)

• Unknown token (UNK) fallback: map any OOV to a learned UNK vector. Simple but loses lexical nuance.
• Morphological decomposition: use morphological analyzers or rule-based stemmers to split into known morphemes and compose embeddings (sum/average/weighted).
• Character/byte-level encoder: train a small CNN/RNN that maps character sequences to embedding space; at inference, generate embeddings for OOVs on the fly.
• Hashing-based embeddings: feature-hash n-grams (characters/bytes) into fixed buckets and average; memory-efficient and robust.
• Contextual refinement: use a contextual LM (if available) to produce embeddings for OOV tokens from context and project them to the static embedding space.

Subword-based tokenizers (BPE, WordPiece, SentencePiece)

• Subword decomposition: if tokenizer splits OOV into known subwords, compose subword embeddings (sum/average/position-weighted) — default and effective for many languages.
• Byte-level / character-level tokenizers: use byte-level BPE or SentencePiece unigram models that can represent any string (no true OOV), excellent for noisy text.
• Fallback to byte-pair encoding with smaller merges to increase coverage, at cost of longer sequences.
• Normalization + transliteration: pre-normalize orthographic noise, map variants to canonical forms, or transliterate to a script with better coverage.
• On-the-fly vocabulary extension: map rare OOVs to new subword splits via SentencePiece retraining or dynamic subword merging (expensive in production).
• Contextualized embeddings: use transformer LM tokenization; even if tokens are rare, subword splits + context produce useful vectors.

Which are most effective for low-resource noisy languages?

• Byte/character-level tokenizers and character encoders are most robust: they guarantee representation for every input and tolerate misspellings, diacritic noise, and agglutination.
• Combine lightweight normalization (unicode normalization, remove repeated characters, common misspelling rules) with a byte-level SentencePiece unigram or small-merge BPE.
• Data augmentation and synthetic corpora: generate noisy variants during fine-tuning so the model learns robustness.
• Hashing n-gram features or a character-CNN gives a good compute/accuracy trade-off when resources are constrained.
• If linguistic resources exist, morphological decomposition plus subword models yields strong performance.

Operational recommendations

• Use byte-level SentencePiece or WordPiece with small merge size in preprocessing for noisy, low-resource languages.
• Add a fast character-based fallback encoder for any remaining unknown forms.
• Monitor OOV rates in production; if high, prioritize normalization rules and targeted vocab expansion or augmentation rather than frequent retraining.
• Measure latency/accuracy trade-offs—character encoders add compute but can be cached for repeated tokens.

Takeaway: For low-resource noisy orthographies, prefer byte/character-aware tokenization plus normalization and augmentation; when constrained, use hashing or lightweight character encoders as practical, production-friendly fallbacks.

The skip-gram Word2Vec objective is: given a center word w_c, predict its context words w_o by maximizing the log probability of context words under embeddings. Practically it trains two vectors per token (target and context) so that dot(u_w_c, v_w_o) is high for true (center, context) pairs.

Computing the full softmax over a large vocabulary V for every training pair is expensive (O(V) per update). Negative sampling replaces the multiclass softmax with a set of binary classification tasks: for each positive (center, context) pair, sample k negative words from a noise distribution and push the model to distinguish the positive from these negatives. Loss for a pair becomes log σ(u·v_pos) + sum_{i=1..k} log σ(−u·v_neg_i).

Negative sampling solves two problems: it makes training scalable (cost O(k) per pair instead of O(V)) and focuses learning on contrasting real contexts against plausible non-contexts, which yields high-quality embeddings. Typical k is 5–20; with V in millions, this reduces compute by orders of magnitude while still producing useful semantic vectors.

Approach summary:

• Incrementally encode user context in chunks (segments) and store per-segment key/value (KV) caches from transformer encoder (or prefix encoder for decoder-only models) so we avoid re-encoding unchanged text.
• Use autoregressive decoding with the decoder’s KV-cache (past_key/past_value) to generate tokens with low latency.
• Manage memory by pruning/compacting old segments (summarize or store compressed representations) and evicting or offloading least-recently-used KV segments.
• Handle edits by re-encoding only affected segments and merging KV caches; for cursor moves/deletions, stitch prefix KV up to edit boundary and discard subsequent segment KVs.

Implementation sketch (PyTorch-style, decoder-only causal model):

# assumptions: model.forward returns logits and new_kv for given input_ids + past_kv
# segments: list of dict {text, token_ids, kv, last_used_timestamp}
from collections import deque
segments = deque()

def encode_segment(tokenizer, model, text):
    ids = tokenizer.encode(text)
    _, kv = model(input_ids=ids, past_key_values=None, return_dict=False)  # compute KV
    return {"text": text, "ids": ids, "kv": kv, "last_used": time.time()}

def incremental_append(text):
    seg = encode_segment(tokenizer, model, text)
    segments.append(seg)
    manage_memory()

def autoregressive_decode(prompt_suffix_ids, max_tokens=32):
    # build past_kv by concatenating segment KVs
    past_kv = concat_kvs([s["kv"] for s in segments])
    logits, new_kv = model(input_ids=prompt_suffix_ids, past_key_values=past_kv)
    # update cache with new_kv for streaming next tokens
    return sample_from_logits(logits)

def handle_edit(edit_pos_token_index, new_text_after_cursor):
    # find segment index containing edit_pos; re-encode from that segment forwards until boundary
    idx, offset = locate_segment(edit_pos_token_index)
    # truncate segments at idx, re-encode edited tail as new segments
    while len(segments) > idx:
        segments.pop()
    tail_seg = encode_segment(tokenizer, model, new_text_after_cursor)
    segments.append(tail_seg)
    manage_memory()

Key concepts:

• KV caches are concatenable if model uses fixed-dim keys/values; concatenation = constant-time reference (no re-encode).
• Re-encode only the segment(s) intersecting edits; keep immutable earlier segments.
• Memory mgmt: LRU eviction, compressed KVs (quantization), periodic summarization (distill old text into short summary token) to reduce context.
• Latency: encode new input async; for typing, encode small chunks (word/subword) and decode while further text arrives.

Complexity:

• Encoding: O(n_seg * L_seg) for changed segments only. Decoding per token O(1) extra due to KV cache.
• Memory: O(total_tokens) for KV storage; can be reduced via pruning/quantization.

Edge cases:

• Edits spanning many segments => batch re-encode larger window.
• Consistency across tokenizers (cursor index must align with token boundaries).
• Attention position ids for very long contexts: maintain correct positional offsets or use relative pos encodings.

Requirements & constraints:

• Detect data drift (input distribution), label drift, concept drift (P(y|x)), and performance regression in real time and batch; support NLP-specific features (text embeddings, token distributions), low-latency alerts, auditable logs, and human-in-the-loop (HITL) retraining. Scale to millions of requests/month.

High-level architecture:

• Inference service → Monitoring producer (sidecar or middleware) emits examples, preds, confidences, metadata to streaming layer (Kafka).
• Monitoring pipeline: real-time feature extractor (text -> embeddings, token n-grams, length, language), metrics calculator, drift-test runner, datastore (time-series DB + object store for raw samples), alerting & dashboard, retraining orchestrator.
• Store labeled feedback in label store; predicted-only records in sample store with TTL.

Concrete metrics to track:

• Input-level: token distribution (top-k tokens), average length, language detection ratio, embedding centroid & covariance, OOV rate, special-token frequency.
• Model-level: class distribution of predictions, softmax/confidence distribution, calibration (ECE), prediction entropy, top-1/top-2 margin.
• Label-level: true label distribution, confusion matrix, per-class precision/recall/F1.
• Business KPIs: downstream conversion, user satisfaction.

Statistical tests & detectors:

• Data drift (inputs):
  • Embeddings: MMD (Maximum Mean Discrepancy) or Hotelling’s T² on PCA-projected embeddings.
  • Token counts: Chi-squared / KL divergence with sliding-window smoothing.
  • Text length/language: Kolmogorov–Smirnov (KS) test.
• Label drift:
  • Chi-squared on label histograms between baseline window and recent window.
• Concept drift / performance drift:
  • Population Stability Index (PSI) on model scores.
  • Monitor rolling-window AUC/F1; use Page-Hinkley test or CUSUM for change detection on metric time series.
  • Monitor calibration shift via ECE and Brier score change.
• Multiple-testing correction: control FDR (Benjamini-Hochberg) across many features.

Alerting thresholds (example starting points, tune per product):

• MMD p-value < 0.01 or PSI > 0.2 for embeddings → high-severity alert.
• KL divergence increase > 0.1 and top-10 token frequency shift > 30% → medium.
• Drop in rolling 7-day F1 > 5% absolute or AUC drop > 0.03 → high.
• ECE increase > 0.02 → medium.
• Low-confidence fraction (> probability < 0.6) increase by > 20% → medium.
• Business KPI degradation (e.g., conversion drop > 2% vs baseline) → critical.

Alert classification & workflows:

• Tier 1 automated alerts (info/warning) to monitoring dashboard and Slack.
• Tier 2 critical alerts create incident and page on-call ML engineer + product owner.
• Attach representative sample batch and summary statistics to ticket.

Automatic vs human-in-the-loop retraining triggers:

• Automatic retrain (fully automated pipeline) if:
  • Labeled performance metric sustained drop beyond threshold for N consecutive windows (e.g., 3 days) AND sufficient new labeled data available (minimum examples per class).
  • Drift metrics indicate benign distribution shift but labeling confirms improved loss with retrained model on holdout validation.
• Human-in-the-loop retrain when:
  • Concept drift suspected (performance drop without input distribution change) or business KPI impacted.
  • Class emergence (new label) or severe class imbalance change.
  • Retraining candidate requires architecture change or feature engineering.
• Retraining process:
  • Data selection: stratified recent window + reservoir of baseline data, ensure class balance.
  • Validation: automated CI tests, regression tests on held-out slices and critical benchmarks.
  • Canary rollout: shadow baseline for 24–72 hours, then 1% traffic, monitor metrics; automatic rollback on negative signals.

Data retention & audit:

• Raw inputs + preds + metadata: retain rolling 90 days in hot store for real-time investigations; archive to cold object store (S3/GS) for 2–5 years depending on compliance.
• Labeled feedback & ground truth: retain minimum 2–5 years; immutable audit logs for training datasets and model versions.
• Store drift test results, alert history, retraining runs, hyperparameters, and evaluation reports in ML metadata store (e.g., MLFlow, Feast, or internal).
• Ensure encryption at rest/in transit, access controls, and lineage tracking for reproducibility.

Operational considerations:

• Sampling: full logging for critical flows, 1–10% sampling for high-throughput non-critical.
• Explainability hooks: save attention maps or saliency for flagged samples.
• Cost/latency trade-offs: compute heavy embedding drift in batch; run lightweight token-level tests in real time.
• Dashboards: per-model overview, feature-level drift heatmaps, alert history, and retraining candidates queue.

Final note: calibrate thresholds with historical simulation (backtesting), include human review in early deployment, and iterate thresholds and selection policies as real-world feedback accumulates.