Everything you need to Know for Data Scientist OA by Emperor_Ace
ML / Stats / NLP / RAG / Chunking / Tokenizing / OpenCV / Pandas / Time Series / DL
*(v2 + INDEX + a large batch of new likely-to-appear code snippets, merged into one doc)*
— -
## 📑 INDEX — QUICK NAV
| # | Section | What’s inside |
| — -| — — — — -| — — — — — — — — |
| 1 | [Machine Learning — MCQ Trivia](#1-machine-learning — mcq-trivia) | Bias-variance, regularization, metrics, optimization, loss functions, trees/ensembles, PCA/SVM/kNN/K-Means, feature engineering (1.1), stats & probability (1.2) |
| 2 | [NLP — MCQ Trivia](#2-nlp — mcq-trivia) | Preprocessing, BoW/TF-IDF/embeddings, transformers, decoding, metrics, extras (2.1) |
| 3 | [RAG](#3-rag-retrieval-augmented-generation — mcq-trivia) | Pipeline, retrieval types, vector DBs, reranking, advanced RAG, eval |
| 4 | [Chunking](#4-chunking — mcq-trivia) | Strategies, size/overlap tradeoffs |
| 5 | [Tokenizing](#5-tokenizing — mcq-trivia) | Word/char/subword, BPE/WordPiece/SentencePiece, special tokens |
| 6 | [OpenCV](#6-opencv — mcq-trivia) | Color spaces, thresholding, edges, morphology, contours, features, extras (6.1) |
| 7 | [Code Snippets](#7-likely-code-snippets) | 7.1–7.6x, see sub-index below |
| 8 | [Rapid-Fire Gotchas](#8-rapid-fire-gotcha-questions-things-people-miss) | Highest-yield 2-minute skim before OA |
| 9 | [Time Series](#9-time-series — mcq-trivia — code) | Trivia + train/test split, decomposition, ARIMA, feature engineering |
| 10 | [Deep Learning Quick Snippets](#10-deep-learning-quick-snippets-pytorch) | Dataset/DataLoader, training loop, early stopping |
| 11 | [SQL-in-Pandas / Data Wrangling](#11-sql-style — data-wrangling-snippets) | groupby+window, rank, cumsum, merge patterns |
### Section 7 sub-index (code snippets by topic)
- **Core ML basics:** 7.1 train/test split+metrics · 7.12 logistic regression scratch · 7.13 linear regression scratch · 7.14 PCA scratch · 7.15 Pipeline+GridSearchCV · 7.17 StratifiedKFold · 7.18 ROC/AUC · 7.58 decision tree scratch · 7.59 naive bayes scratch
- **Imbalance/leakage:** 7.16 SMOTE · 7.55 leakage-safe pipeline
- **Feature engineering:** 7.37 imputation · 7.38 one-hot encoding · 7.39/7.40 outlier detection · 7.46 cyclical datetime encoding
- **Boosting libs:** 7.41 XGBoost · 7.42 LightGBM · 7.43 feature importance
- **Stats tests:** 7.35 t-test · 7.47 chi-square · 7.48 ANOVA · 7.49 bootstrap CI
- **NLP:** 7.19 TF-IDF · 7.20 Word2Vec · 7.21 BERT embeddings · 7.22 spaCy NER/POS · 7.23 n-grams · 7.24 edit distance
- **RAG/Chunking/Tokenizing:** 7.3/7.4 chunking · 7.25 FAISS RAG pipeline · 7.26 semantic chunking · 7.27 tiktoken · 7.28 train BPE
- **OpenCV:** 7.8/7.9 preprocessing · 7.29 Haar cascade · 7.30 ORB matching · 7.31 template matching · 7.32 contours/bbox · 7.33 histogram eq · 7.34 perspective warp
- **Similarity/anomaly/recsys:** 7.51 cosine similarity matrix · 7.50 isolation forest · 7.52 item-based recsys
- **Model ops:** 7.53 pickle/joblib · 7.60 confusion matrix heatmap · 7.56 multi-class report · 7.57 PR curve
- **Pandas:** 7.36 quick reference
— -
## 1. MACHINE LEARNING — MCQ TRIVIA
**Bias-Variance Tradeoff**
- High bias → underfitting (model too simple, high train + test error)
- High variance → overfitting (low train error, high test error)
- Total error = Bias² + Variance + Irreducible error
**Regularization**
- L1 (Lasso) → adds |w|, produces sparse weights (feature selection)
- L2 (Ridge) → adds w², shrinks weights smoothly, doesn’t zero them out
- Elastic Net = L1 + L2 combined
- Dropout, early stopping, data augmentation = regularization for neural nets
**Evaluation Metrics**
- Precision = TP/(TP+FP) — “of predicted positives, how many correct”
- Recall = TP/(TP+FN) — “of actual positives, how many found”
- F1 = harmonic mean of precision & recall = 2PR/(P+R)
- ROC-AUC: TPR vs FPR across thresholds; 0.5 = random, 1.0 = perfect
- PR-AUC preferred over ROC-AUC on imbalanced data
- Accuracy is misleading on imbalanced classes
**Optimization**
- SGD → noisy, one/few samples per update
- Momentum → adds velocity term, dampens oscillation
- RMSprop → adaptive LR using moving avg of squared gradients
- Adam = Momentum + RMSprop (most common default)
- Learning rate too high → divergence; too low → slow convergence/local minima stuck
**Loss Functions**
- MSE → regression
- Cross-Entropy → classification (Binary CE for 2-class, Categorical CE for multi-class)
- Hinge loss → SVM
**Trees & Ensembles**
- Gini impurity vs Entropy (Information Gain) — both measure node purity, gini is faster (no log)
- Bagging (Random Forest): parallel, reduces variance, bootstrap sampling
- Boosting (AdaBoost, GBM, XGBoost, LightGBM): sequential, reduces bias, each model fixes previous errors
- Random Forest: bagging + random feature subset per split
- **XGBoost vs LightGBM**: XGBoost splits level-wise (more balanced trees, slower), LightGBM splits leaf-wise (faster, can overfit more on small data); LightGBM uses histogram-based binning + GOSS/EFB for speed on large datasets
**Other Core Concepts**
- PCA: unsupervised, finds directions (eigenvectors of covariance matrix) of max variance
- SVD used to compute PCA; also basis of collaborative filtering
- Naive Bayes: assumes feature independence given class; fast, works well on text
- k-NN: lazy learner, no training phase, sensitive to feature scaling
- SVM: maximizes margin; kernel trick for non-linear boundaries (RBF, polynomial)
- K-Means: unsupervised clustering, sensitive to initialization (use k-means++), needs k specified, elbow method to pick k
- Cross-validation: k-fold reduces variance of performance estimate vs single train/test split
- Vanishing/Exploding gradients → deep nets; fixed by ReLU, batch norm, residual connections, gradient clipping
- Batch Normalization: normalizes layer inputs, speeds up training, slight regularization effect
- Activation functions: Sigmoid (vanishing gradient issue), Tanh, ReLU (dead neuron issue), Leaky ReLU, GELU (used in transformers), Softmax (multi-class output)
### 1.1 Feature Engineering & Preprocessing (commonly missed)
- **Missing data**: mean/median imputation (numeric), mode imputation (categorical), KNN-imputation, or drop rows/cols if missingness is small/random; median preferred over mean when outliers present
- **Categorical encoding**: One-Hot Encoding (nominal, no order — avoid for high-cardinality), Label Encoding (ordinal, implies order — misleading for tree-agnostic linear models), Target/Mean Encoding (risk of leakage, needs CV-safe implementation)
- **Feature scaling**: StandardScaler (zero mean, unit variance) / MinMaxScaler (0–1) — **required** for distance-based & gradient-based models (KNN, SVM, k-means, logistic/linear regression, neural nets); **not needed** for tree-based models (RF, XGBoost, decision trees) since splits are scale-invariant
- **Class imbalance fixes**: SMOTE (synthetic oversampling of minority class), random undersampling of majority, `class_weight=’balanced’`, using PR-AUC/F1 instead of accuracy
- **Curse of dimensionality**: as feature count grows, data becomes sparse in space, distance metrics lose meaning, models need exponentially more data
- **Multicollinearity**: correlated features destabilize linear model coefficients — check via VIF (Variance Inflation Factor), fix by dropping/combining features or regularizing (Ridge)
- **Outliers**: IQR method (< Q1–1.5IQR or > Q3+1.5IQR) or z-score (|z|>3); tree models robust to outliers, linear models are not
### 1.2 Statistics & Probability (classic DS-round trivia)
- **Bayes’ Theorem**: P(A|B) = P(B|A)·P(A) / P(B)
- **Central Limit Theorem**: sampling distribution of the sample mean approaches normal as n grows, regardless of population distribution — justifies using normal-based CIs/tests on large samples
- **p-value**: probability of observing data this extreme (or more) *if the null hypothesis were true*; p < 0.05 conventionally → reject null. p-value is **not** the probability the null is true
- **Type I error** (false positive, rejecting true null, rate = α) vs **Type II error** (false negative, failing to reject false null, rate = β); **power = 1 − β**
- **Confidence Interval**: range that would contain the true parameter in X% of repeated samples (not “X% chance the true value is in this interval”)
- **Correlation ≠ Causation** — always a favorite trivia line
- **Pearson r**: measures *linear* relationship, sensitive to outliers, range −1 to 1
- **Spearman ρ**: rank-based, captures monotonic (not necessarily linear) relationships, robust to outliers
- **Covariance vs Correlation**: correlation = covariance normalized by std devs (unit-free, bounded)
- **A/B testing**: control vs treatment groups, test significance with a two-sample t-test or z-test, watch for multiple-testing / peeking problems
- **Chi-square test**: tests independence between categorical variables
- **ANOVA**: tests whether means differ across 3+ groups (extension of t-test to multiple groups)
- **z-score**: (x − μ)/σ — standardized distance from the mean
- **Bootstrap**: resample with replacement to estimate sampling distribution / CI without distributional assumptions
— -
## 2. NLP — MCQ TRIVIA
**Text Preprocessing**
- Stemming: crude, rule-based, chops suffixes (Porter, Snowball) → “running”→”run” (may produce non-words)
- Lemmatization: dictionary-based, returns valid root word using POS context → slower, more accurate
- Stop word removal, lowercasing — classic pipeline (less used with transformers, which need raw-ish text)
**Text Representation**
- Bag of Words: word counts, ignores order
- TF-IDF: TF(t,d) × log(N/df(t)) — downweights common words, upweights rare-but-relevant ones
- Word2Vec: CBOW (predict word from context, faster, good for frequent words) vs Skip-gram (predict context from word, better for rare words)
- GloVe: co-occurrence matrix + factorization (global statistics, unlike Word2Vec’s local window)
- Static embeddings (Word2Vec/GloVe) = one vector per word regardless of context
- Contextual embeddings (BERT/ELMo) = vector changes based on sentence context
**Transformers**
- Self-attention: Q, K, V matrices; Attention(Q,K,V) = softmax(QKᵀ/√dₖ)V
- √dₖ scaling prevents large dot products from causing vanishing gradients in softmax
- Multi-head attention: parallel attention heads capture different relationship types
- Positional encoding needed because self-attention has no inherent sequence order (sinusoidal or learned)
- Encoder-only (BERT): bidirectional context, good for understanding/classification/embeddings
- Decoder-only (GPT): causal/unidirectional (masked), good for generation
- Encoder-Decoder (T5, BART): good for seq2seq tasks (translation, summarization)
- BERT pretraining: Masked LM (predict masked tokens) + Next Sentence Prediction
- GPT pretraining: Causal/Autoregressive LM (predict next token)
- Cross-attention (in encoder-decoder): decoder attends to encoder outputs
**Generation / Decoding**
- Greedy decoding: picks highest-prob token each step — fast but suboptimal
- Beam search: keeps top-k sequences — better quality, more compute
- Top-k / Top-p (nucleus) sampling: for diverse/creative generation
- Temperature: >1 more random/diverse, <1 more deterministic/conservative
**Metrics**
- Perplexity: measures how well a LM predicts a sample — lower is better
- BLEU: n-gram precision, used for translation
- ROUGE: recall-oriented, used for summarization
- METEOR: considers synonyms/stemming, better human correlation than BLEU
**Other**
- NER: identifies entities (PERSON, ORG, LOC, DATE)
- POS tagging: assigns grammatical roles (noun, verb, etc.)
- Cosine similarity: cos(θ) = (A·B)/(‖A‖‖B‖) — measures angle not magnitude, standard for embeddings
### 2.1 Extra NLP trivia points
- **Edit distance (Levenshtein)**: min insert/delete/substitute ops to turn one string into another — used for fuzzy matching, spell-check
- **Jaccard similarity**: |A∩B| / |A∪B| — set-overlap similarity, common for n-gram/keyword comparisons
- **N-grams**: contiguous sequences of n tokens; unigram/bigram/trigram used as classical features before embeddings
- **OOV handling**: subword tokenization is the main modern fix (see Section 5); older word-level models used an `<UNK>` token
- **spaCy vs NLTK**: spaCy is production-grade/fast (pipeline-based, pretrained models), NLTK is more academic/teaching-oriented with more granular control
— -
## 3. RAG (RETRIEVAL AUGMENTED GENERATION) — MCQ TRIVIA
**Pipeline**
Ingest docs → Chunk → Embed chunks → Store in vector DB → (Query time) Embed query → Retrieve top-k similar chunks → Optionally rerank → Augment prompt with retrieved context → LLM generates grounded answer
**Why RAG**
- Reduces hallucination by grounding generation in retrieved facts
- Avoids need to fine-tune/retrain for new/updated knowledge
- Cheaper than fine-tuning for knowledge injection; keeps knowledge current without retraining
**Chunking (see section 4 for detail)**
- Chunk size directly affects retrieval precision vs context completeness
- Overlap between chunks prevents losing context at boundaries
**Retrieval**
- Dense retrieval: embedding + vector similarity search (semantic)
- Sparse retrieval: BM25/TF-IDF (keyword/lexical match)
- Hybrid search: combines dense + sparse (often best in practice), fused via reciprocal rank fusion (RRF)
- Similarity metrics: cosine similarity (most common), dot product, Euclidean (L2) distance
**Vector Databases**
- FAISS (Meta) — library, not a full DB, in-memory/on-disk indexes, no built-in persistence/metadata filtering out of the box
- Pinecone, Weaviate, Qdrant, Milvus, Chroma — managed/full-featured vector DBs with metadata filtering
- Index types: Flat (exact, slow), IVF (inverted file, approximate), HNSW (graph-based, fast approximate nearest neighbor — most popular)
- ANN (Approximate Nearest Neighbor) trades a bit of accuracy for major speed gains at scale
**Reranking**
- Cross-encoder reranker: scores (query, chunk) pairs jointly — much more accurate but slower than bi-encoder retrieval
- Bi-encoder (used for initial retrieval): encodes query and docs separately — fast, enables precomputed embeddings
**Advanced RAG Concepts**
- HyDE (Hypothetical Document Embeddings): generate a hypothetical answer first, embed that, then retrieve — improves recall for vague queries
- Query rewriting/expansion: reformulate user query for better retrieval
- Multi-query retrieval: generate several query variants, union results
- Parent-document retrieval: retrieve small chunks but return larger surrounding context to the LLM
- Self-RAG / Corrective RAG: model critiques/checks retrieved docs before generating
**Evaluation**
- Context Precision/Recall: is retrieved context relevant/complete?
- Faithfulness: does generated answer stay grounded in retrieved context (no hallucination)?
- Answer Relevance: does the answer address the actual question?
- MRR (Mean Reciprocal Rank), Recall@k, nDCG — standard IR retrieval metrics
— -
## 4. CHUNKING — MCQ TRIVIA
- **Fixed-size chunking**: split every N tokens/characters — simple, fast, but can cut mid-sentence/mid-idea
- **Recursive character splitting**: tries paragraph → sentence → word boundaries recursively until chunk fits size limit (most common default, e.g. LangChain’s RecursiveCharacterTextSplitter)
- **Sentence-based chunking**: splits on sentence boundaries, keeps semantic units intact
- **Semantic chunking**: splits based on embedding similarity shifts between sentences (topic change detection) — more coherent chunks, more compute
- **Sliding window with overlap**: consecutive chunks share ~10–20% overlap to preserve context across boundaries
- **Document-structure-aware chunking**: splits along markdown headers/sections, table boundaries, etc.
- Small chunks → higher precision, less context per chunk, more chunks needed for full answer
- Large chunks → more context, but noisier retrieval (less precise similarity match), risk exceeding context window
- Typical starting point: 200–500 tokens per chunk with 10–20% overlap (tune per use case)
- Chunk size should roughly match expected query/answer granularity
— -
## 5. TOKENIZING — MCQ TRIVIA
- **Word-level tokenization**: simple but huge vocab, can’t handle OOV (out-of-vocabulary) words
- **Character-level**: tiny vocab, no OOV issue, but very long sequences, harder to learn meaning
- **Subword tokenization** (standard in modern LLMs): balances vocab size and sequence length, handles OOV by breaking into known pieces
— **BPE (Byte Pair Encoding)**: iteratively merges most frequent adjacent symbol pairs until vocab size reached (used in GPT-2/GPT-3, RoBERTa)
— **WordPiece**: similar to BPE but merges based on likelihood improvement, not just frequency (used in BERT)
— **SentencePiece**: language-agnostic, treats text as raw stream (no pre-tokenization needed), supports BPE or Unigram mode (used in T5, LLaMA)
— **Unigram LM**: starts with large vocab, prunes down by removing tokens that hurt likelihood least
- **Special tokens**: [CLS] (classification/sentence embedding, BERT), [SEP] (segment separator), [PAD] (padding to equal length), [MASK] (masked LM), `<bos>`/`<eos>` (begin/end of sequence, GPT-style)
- **tiktoken**: OpenAI’s fast BPE tokenizer library (used for GPT models)
- More tokens ≠ more words — 1 token ≈ ~4 characters or ~0.75 words in English (rule of thumb)
- Tokenizer vocab size is fixed at pretraining time — can’t add new tokens without retraining embeddings for them
— -
## 6. OPENCV — MCQ TRIVIA
- `cv2.imread()` loads images in **BGR** order by default, not RGB — classic gotcha question
- Color space conversions: `cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)`, `COLOR_BGR2RGB`, `COLOR_BGR2HSV`
- HSV useful for color-based segmentation (robust to lighting changes vs RGB)
- **Thresholding**: `cv2.threshold()` (global), `cv2.adaptiveThreshold()` (local, better for uneven lighting), Otsu’s method (auto-picks global threshold)
- **Edge detection**: Canny (`cv2.Canny()`) — multi-stage: noise reduction → gradient (Sobel) → non-max suppression → hysteresis thresholding; Sobel = gradient-based, simpler, noisier
- **Blurring/denoising**: Gaussian blur (smooths, weighted by distance), Median blur (great for salt-and-pepper noise), Bilateral filter (edge-preserving smoothing)
- **Morphological ops** (on binary images): Erosion (shrinks white regions, removes noise), Dilation (expands white regions, fills gaps), Opening = erosion→dilation (removes small noise), Closing = dilation→erosion (fills small holes)
- **Contours**: `cv2.findContours()` — used for shape detection, object counting; needs binary image input
- **Feature detectors**: SIFT (scale/rotation invariant, patented historically, now free), ORB (fast, free alternative to SIFT/SURF, binary descriptors), Harris Corner Detector (basic corner detection)
- **Resizing/interpolation**: `cv2.resize()` — `INTER_LINEAR` (default, good general), `INTER_NEAREST` (fast, blocky), `INTER_CUBIC`/`INTER_AREA` (better quality, `INTER_AREA` best for shrinking)
- Typical OCR preprocessing pipeline: grayscale → denoise → threshold/binarize → deskew → (dilate/erode to clean) → feed to OCR engine
### 6.1 Extra OpenCV trivia
- **Haar cascades**: classic fast object/face detector, XML-based pretrained classifiers, precursor to deep-learning detectors
- **Template matching** (`cv2.matchTemplate`): slides a template image over the source to find the best match location — sensitive to scale/rotation changes
- **Histogram equalization** (`cv2.equalizeHist`): improves contrast in low-contrast grayscale images by spreading out intensity distribution; CLAHE = adaptive/local version, avoids over-amplifying noise
- **Perspective/Affine transform**: `cv2.getPerspectiveTransform` + `cv2.warpPerspective` for correcting skew/perspective (e.g. document scanning); affine preserves parallel lines, perspective does not
- **Connected components** (`cv2.connectedComponents`): labels separate blobs in a binary image — used for counting objects
— -
## 7. LIKELY CODE SNIPPETS
### 7.1 Train/test split + basic classification metrics
```python
from sklearn.model_selection import train_test_split
from sklearn.metrics import precision_score, recall_score, f1_score, confusion_matrix
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42, stratify=y)
# after prediction
precision = precision_score(y_test, y_pred)
recall = recall_score(y_test, y_pred)
f1 = f1_score(y_test, y_pred)
cm = confusion_matrix(y_test, y_pred)
```
### 7.2 Cosine similarity (numpy, no sklearn)
```python
import numpy as np
def cosine_similarity(a, b):
a, b = np.array(a), np.array(b)
return np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b))
```
### 7.3 Simple sliding-window chunking with overlap
```python
def chunk_text(text, chunk_size=500, overlap=100):
chunks = []
start = 0
while start < len(text):
end = start + chunk_size
chunks.append(text[start:end])
start += chunk_size — overlap
return chunks
```
### 7.4 Sentence-aware recursive-style chunking (simplified)
```python
def recursive_split(text, max_chars=500, separators=(“\n\n”, “\n”, “. “, “ “)):
if len(text) <= max_chars:
return [text]
for sep in separators:
if sep in text:
parts = text.split(sep)
break
else:
parts = list(text)
chunks, current = [], “”
for part in parts:
candidate = current + sep + part if current else part
if len(candidate) <= max_chars:
current = candidate
else:
if current:
chunks.append(current)
current = part
if current:
chunks.append(current)
return chunks
```
### 7.5 Minimal BPE tokenizer training loop (concept-level)
```python
from collections import Counter
def get_pair_freqs(vocab):
pairs = Counter()
for word, freq in vocab.items():
symbols = word.split()
for i in range(len(symbols) — 1):
pairs[(symbols[i], symbols[i + 1])] += freq
return pairs
def merge_vocab(pair, vocab):
new_vocab = {}
bigram = “ “.join(pair)
replacement = “”.join(pair)
for word in vocab:
new_word = word.replace(bigram, replacement)
new_vocab[new_word] = vocab[word]
return new_vocab
# vocab: dict of “w o r d </w>” -> frequency
# repeat for num_merges: find most frequent pair, merge it
for _ in range(num_merges):
pairs = get_pair_freqs(vocab)
if not pairs:
break
best = max(pairs, key=pairs.get)
vocab = merge_vocab(best, vocab)
```
### 7.6 Scaled dot-product attention (from scratch, numpy)
```python
import numpy as np
def softmax(x, axis=-1):
e = np.exp(x — np.max(x, axis=axis, keepdims=True))
return e / np.sum(e, axis=axis, keepdims=True)
def scaled_dot_product_attention(Q, K, V):
d_k = Q.shape[-1]
scores = Q @ K.T / np.sqrt(d_k)
weights = softmax(scores, axis=-1)
return weights @ V
```
### 7.7 Minimal RAG retrieval (embedding + top-k) pseudocode
```python
import numpy as np
def retrieve_top_k(query_embedding, chunk_embeddings, chunks, k=3):
sims = [cosine_similarity(query_embedding, ce) for ce in chunk_embeddings]
top_idx = np.argsort(sims)[::-1][:k]
return [chunks[i] for i in top_idx]
def build_prompt(query, retrieved_chunks):
context = “\n\n”.join(retrieved_chunks)
return f”Context:\n{context}\n\nQuestion: {query}\nAnswer based only on the context above:”
```
### 7.8 OpenCV: basic preprocessing + Canny edge pipeline
```python
import cv2
img = cv2.imread(“image.jpg”) # BGR
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
blurred = cv2.GaussianBlur(gray, (5, 5), 0)
edges = cv2.Canny(blurred, threshold1=50, threshold2=150)
# find contours
contours, _ = cv2.findContours(edges, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
```
### 7.9 OpenCV: adaptive thresholding (good for OCR preprocessing)
```python
import cv2
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
thresh = cv2.adaptiveThreshold(
gray, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C,
cv2.THRESH_BINARY, blockSize=11, C=2
)
```
### 7.10 K-Means from scratch (common ML coding-round ask)
```python
import numpy as np
def kmeans(X, k, iters=100):
centroids = X[np.random.choice(len(X), k, replace=False)]
for _ in range(iters):
distances = np.linalg.norm(X[:, None] — centroids[None, :], axis=2)
labels = np.argmin(distances, axis=1)
new_centroids = np.array([X[labels == i].mean(axis=0) for i in range(k)])
if np.allclose(centroids, new_centroids):
break
centroids = new_centroids
return labels, centroids
```
### 7.11 Simple text preprocessing pipeline
```python
import re
def preprocess(text):
text = text.lower()
text = re.sub(r”[^a-z0–9\s]”, “”, text)
tokens = text.split()
return tokens
```
### 7.12 Logistic Regression from scratch (batch gradient descent)
```python
import numpy as np
def sigmoid(z):
return 1 / (1 + np.exp(-z))
def logistic_regression(X, y, lr=0.1, epochs=1000):
n, d = X.shape
w, b = np.zeros(d), 0.0
for _ in range(epochs):
z = X @ w + b
preds = sigmoid(z)
grad_w = X.T @ (preds — y) / n
grad_b = np.mean(preds — y)
w -= lr * grad_w
b -= lr * grad_b
return w, b
```
### 7.13 Linear Regression from scratch (gradient descent)
```python
import numpy as np
def linear_regression(X, y, lr=0.01, epochs=1000):
n, d = X.shape
w, b = np.zeros(d), 0.0
for _ in range(epochs):
preds = X @ w + b
grad_w = -(2/n) * X.T @ (y — preds)
grad_b = -(2/n) * np.sum(y — preds)
w -= lr * grad_w
b -= lr * grad_b
return w, b
```
### 7.14 PCA from scratch (numpy, via covariance eigen-decomposition)
```python
import numpy as np
def pca(X, n_components=2):
X_centered = X — X.mean(axis=0)
cov = np.cov(X_centered, rowvar=False)
eigvals, eigvecs = np.linalg.eigh(cov) # ascending order
top_idx = np.argsort(eigvals)[::-1][:n_components]
components = eigvecs[:, top_idx]
return X_centered @ components
```
### 7.15 Pipeline + StandardScaler + GridSearchCV (sklearn, realistic OA ask)
```python
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC
from sklearn.model_selection import GridSearchCV
pipe = Pipeline([
(“scaler”, StandardScaler()),
(“clf”, SVC())
])
param_grid = {“clf__C”: [0.1, 1, 10], “clf__kernel”: [“linear”, “rbf”]}
grid = GridSearchCV(pipe, param_grid, cv=5, scoring=”f1")
grid.fit(X_train, y_train)
best_model = grid.best_estimator_
```
### 7.16 Handling class imbalance with SMOTE
```python
from imblearn.over_sampling import SMOTE
smote = SMOTE(random_state=42)
X_resampled, y_resampled = smote.fit_resample(X_train, y_train)
```
### 7.17 Stratified K-Fold cross-validation
```python
from sklearn.model_selection import StratifiedKFold, cross_val_score
skf = StratifiedKFold(n_splits=5, shuffle=True, random_state=42)
scores = cross_val_score(model, X, y, cv=skf, scoring=”f1")
print(scores.mean(), scores.std())
```
### 7.18 ROC curve + AUC
```python
from sklearn.metrics import roc_curve, roc_auc_score
import matplotlib.pyplot as plt
probs = model.predict_proba(X_test)[:, 1]
fpr, tpr, thresholds = roc_curve(y_test, probs)
auc = roc_auc_score(y_test, probs)
plt.plot(fpr, tpr, label=f”AUC = {auc:.2f}”)
plt.plot([0, 1], [0, 1], “ — “)
plt.xlabel(“FPR”); plt.ylabel(“TPR”); plt.legend()
```
### 7.19 TF-IDF vectorization (sklearn)
```python
from sklearn.feature_extraction.text import TfidfVectorizer
vectorizer = TfidfVectorizer(stop_words=”english”, max_features=5000)
X_tfidf = vectorizer.fit_transform(corpus) # sparse matrix
feature_names = vectorizer.get_feature_names_out()
```
### 7.20 Word2Vec (gensim)
```python
from gensim.models import Word2Vec
sentences = [doc.split() for doc in corpus]
model = Word2Vec(sentences, vector_size=100, window=5, min_count=2, sg=1) # sg=1 -> skip-gram, sg=0 -> CBOW
vector = model.wv[“machine”]
similar = model.wv.most_similar(“machine”, topn=5)
```
### 7.21 Contextual embeddings with a pretrained BERT (HuggingFace)
```python
from transformers import AutoTokenizer, AutoModel
import torch
tokenizer = AutoTokenizer.from_pretrained(“bert-base-uncased”)
model = AutoModel.from_pretrained(“bert-base-uncased”)
inputs = tokenizer(“Curiflow OA prep”, return_tensors=”pt”)
with torch.no_grad():
outputs = model(**inputs)
cls_embedding = outputs.last_hidden_state[:, 0, :] # [CLS] token embedding
```
### 7.22 NER + POS tagging (spaCy)
```python
import spacy
nlp = spacy.load(“en_core_web_sm”)
doc = nlp(“Sundar Pichai works at Google in California.”)
for ent in doc.ents:
print(ent.text, ent.label_) # NER
for token in doc:
print(token.text, token.pos_) # POS tagging
```
### 7.23 N-gram generation
```python
def generate_ngrams(tokens, n=2):
return [tuple(tokens[i:i+n]) for i in range(len(tokens) — n + 1)]
```
### 7.24 Levenshtein (edit) distance from scratch
```python
def edit_distance(a, b):
m, n = len(a), len(b)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
cost = 0 if a[i-1] == b[j-1] else 1
dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost)
return dp[m][n]
```
### 7.25 Full mini RAG pipeline: sentence-transformers + FAISS
```python
from sentence_transformers import SentenceTransformer
import faiss
import numpy as np
embedder = SentenceTransformer(“all-MiniLM-L6-v2”)
chunk_embeddings = embedder.encode(chunks, normalize_embeddings=True)
index = faiss.IndexFlatIP(chunk_embeddings.shape[1]) # inner product == cosine sim (normalized)
index.add(np.array(chunk_embeddings))
query_embedding = embedder.encode([query], normalize_embeddings=True)
scores, indices = index.search(np.array(query_embedding), k=3)
retrieved = [chunks[i] for i in indices[0]]
```
### 7.26 Semantic chunking (embedding-similarity-based split)
```python
def semantic_chunk(sentences, embedder, threshold=0.75):
embeddings = embedder.encode(sentences, normalize_embeddings=True)
chunks, current = [], [sentences[0]]
for i in range(1, len(sentences)):
sim = np.dot(embeddings[i-1], embeddings[i])
if sim < threshold: # topic shift detected
chunks.append(“ “.join(current))
current = [sentences[i]]
else:
current.append(sentences[i])
chunks.append(“ “.join(current))
return chunks
```
### 7.27 tiktoken usage (OpenAI-style BPE tokenizer)
```python
import tiktoken
enc = tiktoken.get_encoding(“cl100k_base”)
tokens = enc.encode(“Curiflow OA is tomorrow”)
num_tokens = len(tokens)
decoded = enc.decode(tokens)
```
### 7.28 Train a BPE tokenizer from scratch (HuggingFace `tokenizers` library)
```python
from tokenizers import Tokenizer
from tokenizers.models import BPE
from tokenizers.trainers import BpeTrainer
from tokenizers.pre_tokenizers import Whitespace
tokenizer = Tokenizer(BPE(unk_token=”[UNK]”))
tokenizer.pre_tokenizer = Whitespace()
trainer = BpeTrainer(vocab_size=5000, special_tokens=[“[UNK]”, “[CLS]”, “[SEP]”, “[PAD]”, “[MASK]”])
tokenizer.train(files=[“corpus.txt”], trainer=trainer)
output = tokenizer.encode(“subword tokenization example”)
print(output.tokens)
```
### 7.29 OpenCV: Haar cascade face detection
```python
import cv2
face_cascade = cv2.CascadeClassifier(cv2.data.haarcascades + “haarcascade_frontalface_default.xml”)
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
faces = face_cascade.detectMultiScale(gray, scaleFactor=1.1, minNeighbors=5)
for (x, y, w, h) in faces:
cv2.rectangle(img, (x, y), (x+w, y+h), (0, 255, 0), 2)
```
### 7.30 OpenCV: ORB feature matching between two images
```python
import cv2
orb = cv2.ORB_create()
kp1, des1 = orb.detectAndCompute(img1, None)
kp2, des2 = orb.detectAndCompute(img2, None)
bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)
matches = sorted(bf.match(des1, des2), key=lambda m: m.distance)
matched_img = cv2.drawMatches(img1, kp1, img2, kp2, matches[:20], None)
```
### 7.31 OpenCV: template matching
```python
import cv2
result = cv2.matchTemplate(img_gray, template, cv2.TM_CCOEFF_NORMED)
_, max_val, _, max_loc = cv2.minMaxLoc(result)
top_left = max_loc
h, w = template.shape
bottom_right = (top_left[0] + w, top_left[1] + h)
cv2.rectangle(img, top_left, bottom_right, (0, 255, 0), 2)
```
### 7.32 OpenCV: bounding boxes from contours (object counting)
```python
import cv2
contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
for c in contours:
if cv2.contourArea(c) > 100: # filter noise
x, y, w, h = cv2.boundingRect(c)
cv2.rectangle(img, (x, y), (x+w, y+h), (0, 255, 0), 2)
print(“Object count:”, len(contours))
```
### 7.33 OpenCV: histogram equalization
```python
import cv2
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
equalized = cv2.equalizeHist(gray)
clahe = cv2.createCLAHE(clipLimit=2.0, tileGridSize=(8, 8)) # adaptive version
clahe_img = clahe.apply(gray)
```
### 7.34 OpenCV: perspective warp (document deskew)
```python
import numpy as np
import cv2
pts_src = np.float32([[56, 65], [368, 52], [28, 387], [389, 390]])
pts_dst = np.float32([[0, 0], [300, 0], [0, 300], [300, 300]])
M = cv2.getPerspectiveTransform(pts_src, pts_dst)
warped = cv2.warpPerspective(img, M, (300, 300))
```
### 7.35 t-test (hypothesis testing, scipy — classic stats-round ask)
```python
from scipy import stats
t_stat, p_value = stats.ttest_ind(group_a, group_b)
if p_value < 0.05:
print(“Statistically significant difference”)
```
### 7.36 Pandas quick reference (groupby, merge, missing values, pivot)
```python
import pandas as pd
df.groupby(“category”)[“value”].agg([“mean”, “sum”, “count”])
pd.merge(df1, df2, on=”id”, how=”left”) # how: left/right/inner/outer
df.isnull().sum() # missing value count per column
df[“col”].fillna(df[“col”].median(), inplace=True)
df.pivot_table(index=”date”, columns=”category”, values=”sales”, aggfunc=”sum”)
df.drop_duplicates(subset=[“id”], keep=”first”)
df[“col”].value_counts(normalize=True) # class distribution / imbalance check
```
— -
### NEW IN v3 — HIGH-YIELD ADDITIONS
### 7.37 Handling missing data (sklearn imputers)
```python
from sklearn.impute import SimpleImputer, KNNImputer
num_imputer = SimpleImputer(strategy=”median”)
X_num = num_imputer.fit_transform(X[[“age”, “income”]])
cat_imputer = SimpleImputer(strategy=”most_frequent”)
X_cat = cat_imputer.fit_transform(X[[“gender”, “city”]])
knn_imputer = KNNImputer(n_neighbors=5)
X_knn = knn_imputer.fit_transform(X_numeric)
```
### 7.38 One-hot encoding (pandas vs sklearn, and why sklearn is safer)
```python
import pandas as pd
from sklearn.preprocessing import OneHotEncoder
# quick EDA-style (not leakage-safe across train/test)
df_encoded = pd.get_dummies(df, columns=[“city”], drop_first=True)
# leakage-safe: fit on train only, transform both
ohe = OneHotEncoder(handle_unknown=”ignore”, sparse_output=False)
X_train_enc = ohe.fit_transform(X_train[[“city”]])
X_test_enc = ohe.transform(X_test[[“city”]]) # unseen categories -> all zeros
```
### 7.39 Outlier detection — IQR method
```python
def remove_outliers_iqr(df, col):
Q1, Q3 = df[col].quantile(0.25), df[col].quantile(0.75)
IQR = Q3 — Q1
lower, upper = Q1–1.5 * IQR, Q3 + 1.5 * IQR
return df[(df[col] >= lower) & (df[col] <= upper)]
```
### 7.40 Outlier detection — Z-score method
```python
import numpy as np
def remove_outliers_zscore(df, col, threshold=3):
z = (df[col] — df[col].mean()) / df[col].std()
return df[np.abs(z) < threshold]
```
### 7.41 XGBoost classifier (very likely to appear)
```python
import xgboost as xgb
from sklearn.metrics import accuracy_score
model = xgb.XGBClassifier(
n_estimators=200, max_depth=6, learning_rate=0.1,
subsample=0.8, colsample_bytree=0.8, eval_metric=”logloss”
)
model.fit(X_train, y_train, eval_set=[(X_test, y_test)], verbose=False)
preds = model.predict(X_test)
print(accuracy_score(y_test, preds))
```
### 7.42 LightGBM classifier
```python
import lightgbm as lgb
train_data = lgb.Dataset(X_train, label=y_train)
params = {“objective”: “binary”, “metric”: “auc”, “num_leaves”: 31, “learning_rate”: 0.05}
model = lgb.train(params, train_data, num_boost_round=200)
preds = model.predict(X_test) # returns probabilities
```
### 7.43 Feature importance (tree-based models)
```python
import pandas as pd
import matplotlib.pyplot as plt
importances = pd.Series(model.feature_importances_, index=X_train.columns)
importances.sort_values(ascending=False).head(10).plot(kind=”barh”)
plt.gca().invert_yaxis()
```
### 7.44 Custom evaluation metric (e.g., weighted F1 by hand)
```python
def custom_f1(y_true, y_pred, beta=1):
tp = sum((yt == 1 and yp == 1) for yt, yp in zip(y_true, y_pred))
fp = sum((yt == 0 and yp == 1) for yt, yp in zip(y_true, y_pred))
fn = sum((yt == 1 and yp == 0) for yt, yp in zip(y_true, y_pred))
precision = tp / (tp + fp) if (tp + fp) else 0
recall = tp / (tp + fn) if (tp + fn) else 0
if precision + recall == 0:
return 0
return (1 + beta**2) * precision * recall / (beta**2 * precision + recall)
```
### 7.45 Time-aware train/test split (no shuffling — common trap)
```python
def time_series_split(df, date_col, split_date):
train = df[df[date_col] < split_date]
test = df[df[date_col] >= split_date]
return train, test
# or with sklearn for rolling CV:
from sklearn.model_selection import TimeSeriesSplit
tscv = TimeSeriesSplit(n_splits=5)
for train_idx, test_idx in tscv.split(X):
X_train, X_test = X[train_idx], X[test_idx]
```
### 7.46 Cyclical encoding of datetime features (sin/cos — common feature-eng ask)
```python
import numpy as np
df[“hour_sin”] = np.sin(2 * np.pi * df[“hour”] / 24)
df[“hour_cos”] = np.cos(2 * np.pi * df[“hour”] / 24)
df[“month_sin”] = np.sin(2 * np.pi * df[“month”] / 12)
df[“month_cos”] = np.cos(2 * np.pi * df[“month”] / 12)
# preserves cyclical distance (hour 23 close to hour 0), unlike raw integer encoding
```
### 7.47 Chi-square test of independence
```python
import pandas as pd
from scipy.stats import chi2_contingency
contingency = pd.crosstab(df[“gender”], df[“purchased”])
chi2, p, dof, expected = chi2_contingency(contingency)
print(“Significant” if p < 0.05 else “Not significant”)
```
### 7.48 One-way ANOVA
```python
from scipy import stats
f_stat, p_value = stats.f_oneway(group_a, group_b, group_c)
if p_value < 0.05:
print(“At least one group mean differs”)
```
### 7.49 Bootstrap confidence interval
```python
import numpy as np
def bootstrap_ci(data, n_boot=10000, ci=95):
boot_means = [np.mean(np.random.choice(data, size=len(data), replace=True)) for _ in range(n_boot)]
lower = np.percentile(boot_means, (100 — ci) / 2)
upper = np.percentile(boot_means, 100 — (100 — ci) / 2)
return np.mean(data), lower, upper
```
### 7.50 Anomaly detection — Isolation Forest
```python
from sklearn.ensemble import IsolationForest
iso = IsolationForest(contamination=0.05, random_state=42)
preds = iso.fit_predict(X) # -1 = anomaly, 1 = normal
anomalies = X[preds == -1]
```
### 7.51 Pairwise cosine similarity matrix (vectorized, no loops)
```python
import numpy as np
def cosine_similarity_matrix(A):
norm = A / np.linalg.norm(A, axis=1, keepdims=True)
return norm @ norm.T
# sklearn equivalent
from sklearn.metrics.pairwise import cosine_similarity
sim_matrix = cosine_similarity(embeddings)
```
### 7.52 Simple item-based collaborative filtering recommender
```python
import numpy as np
import pandas as pd
def recommend_items(user_item_matrix, item_id, top_n=5):
sim = cosine_similarity(user_item_matrix.T) # item-item similarity
sim_df = pd.DataFrame(sim, index=user_item_matrix.columns, columns=user_item_matrix.columns)
return sim_df[item_id].sort_values(ascending=False)[1:top_n+1]
```
### 7.53 Saving/loading a trained model (pickle & joblib)
```python
import joblib
import pickle
joblib.dump(model, “model.pkl”) # preferred for sklearn (handles numpy arrays well)
loaded_model = joblib.load(“model.pkl”)
with open(“model.pkl”, “wb”) as f: # plain pickle alternative
pickle.dump(model, f)
```
### 7.54 Manual grid search (when GridSearchCV isn’t allowed / to show understanding)
```python
best_score, best_params = -1, None
for C in [0.1, 1, 10]:
for kernel in [“linear”, “rbf”]:
model = SVC(C=C, kernel=kernel)
scores = cross_val_score(model, X_train, y_train, cv=5, scoring=”f1")
if scores.mean() > best_score:
best_score, best_params = scores.mean(), {“C”: C, “kernel”: kernel}
print(best_params, best_score)
```
### 7.55 Data-leakage-safe preprocessing pipeline (fit scaler on train only)
```python
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train) # fit ONLY on train
X_test_scaled = scaler.transform(X_test) # transform test with train stats
# same rule applies to SMOTE, target encoding, imputers, feature selection, etc.
```
### 7.56 Multi-class classification report
```python
from sklearn.metrics import classification_report
print(classification_report(y_test, y_pred, target_names=[“classA”, “classB”, “classC”]))
```
### 7.57 Precision-Recall curve
```python
from sklearn.metrics import precision_recall_curve, average_precision_score
import matplotlib.pyplot as plt
probs = model.predict_proba(X_test)[:, 1]
precision, recall, thresholds = precision_recall_curve(y_test, probs)
ap = average_precision_score(y_test, probs)
plt.plot(recall, precision, label=f”AP = {ap:.2f}”)
plt.xlabel(“Recall”); plt.ylabel(“Precision”); plt.legend()
```
### 7.58 Decision Tree from scratch (simplified, Gini-based, binary split)
```python
import numpy as np
def gini(y):
classes, counts = np.unique(y, return_counts=True)
probs = counts / len(y)
return 1 — np.sum(probs ** 2)
def best_split(X, y):
best_gini, best_feat, best_thresh = 1, None, None
for feat in range(X.shape[1]):
thresholds = np.unique(X[:, feat])
for t in thresholds:
left_mask = X[:, feat] <= t
if left_mask.sum() == 0 or (~left_mask).sum() == 0:
continue
g_left, g_right = gini(y[left_mask]), gini(y[~left_mask])
w_gini = (left_mask.sum() * g_left + (~left_mask).sum() * g_right) / len(y)
if w_gini < best_gini:
best_gini, best_feat, best_thresh = w_gini, feat, t
return best_feat, best_thresh
```
### 7.59 Naive Bayes (Gaussian) from scratch
```python
import numpy as np
class GaussianNB:
def fit(self, X, y):
self.classes = np.unique(y)
self.mean = {c: X[y == c].mean(axis=0) for c in self.classes}
self.var = {c: X[y == c].var(axis=0) + 1e-9 for c in self.classes}
self.prior = {c: (y == c).mean() for c in self.classes}
def _gaussian(self, x, mean, var):
return np.exp(-((x — mean) ** 2) / (2 * var)) / np.sqrt(2 * np.pi * var)
def predict(self, X):
preds = []
for x in X:
posteriors = {c: np.log(self.prior[c]) + np.sum(np.log(self._gaussian(x, self.mean[c], self.var[c])))
for c in self.classes}
preds.append(max(posteriors, key=posteriors.get))
return np.array(preds)
```
### 7.60 Confusion matrix heatmap
```python
from sklearn.metrics import confusion_matrix
import seaborn as sns
import matplotlib.pyplot as plt
cm = confusion_matrix(y_test, y_pred)
sns.heatmap(cm, annot=True, fmt=”d”, cmap=”Blues”)
plt.xlabel(“Predicted”); plt.ylabel(“Actual”)
```
— -
## 8. RAPID-FIRE GOTCHA QUESTIONS (things people miss)
- OpenCV loads images as **BGR**, not RGB — always convert before using matplotlib/PIL
- Cross-entropy loss expects raw logits with most frameworks (e.g. `nn.CrossEntropyLoss` in PyTorch applies softmax internally — don’t apply softmax yourself before it)
- Precision/Recall tradeoff: raising the classification threshold → precision ↑, recall ↓
- BPE merges are learned from a training corpus and frozen — a new domain word may still get split into subwords, not necessarily an unknown token
- HNSW indexes are approximate — recall isn’t guaranteed 100% vs brute-force
- Bagging reduces variance; boosting reduces bias (opposite failure modes they fix)
- L1 → sparsity (some weights become exactly 0); L2 → shrinkage (weights small but nonzero)
- BERT is bidirectional (good for understanding) — it cannot generate text autoregressively left-to-right like GPT
- Overlap in chunking prevents information loss at boundaries but increases storage/index size and can cause near-duplicate retrieval
- Dot product similarity is affected by vector magnitude; cosine similarity is not (normalizes for length) — matters when embeddings aren’t pre-normalized
- p-value < 0.05 does NOT mean “95% chance the effect is real” — it’s P(data | null true), a very commonly flipped interpretation
- Feature scaling matters for KNN/SVM/linear models/neural nets, irrelevant for tree-based models — a favorite trap question
- `StratifiedKFold` (not plain `KFold`) should be used on imbalanced classification data to preserve class ratios in every fold
- SMOTE should only be applied to the training fold, never before the train/test split (data leakage trap)
- `INTER_AREA` is best for shrinking images, `INTER_CUBIC`/`INTER_LINEAR` better for enlarging — mixing these up is a common OpenCV trick question
- Word2Vec Skip-gram is generally better for rare words / small datasets; CBOW is faster and better for frequent words / large datasets
- FAISS `IndexFlatIP` (inner product) only equals cosine similarity if vectors are pre-normalized — otherwise it’s just raw dot product
- **NEW:** Never shuffle time series data before splitting — always split chronologically, or you leak future info into training
- **NEW:** `fit_transform` on train, `transform` (not `fit_transform`) on test — refitting on test is a classic leakage bug
- **NEW:** LightGBM’s leaf-wise growth can overfit small datasets faster than XGBoost’s level-wise growth — control with `max_depth`/`num_leaves`
- **NEW:** Label Encoding on nominal (unordered) categories can mislead linear/distance-based models into assuming false ordinal relationships — safe for tree models, risky otherwise
- **NEW:** `np.random.choice(…, replace=True)` is what makes bootstrap sampling “bootstrap” — sampling without replacement is just a subsample, not a bootstrap
- **NEW:** Accuracy on a 95/5 imbalanced dataset can hit 95% by predicting the majority class every time — always pair with F1/PR-AUC/confusion matrix on imbalanced problems
— -
## 9. TIME SERIES — MCQ TRIVIA + CODE
**Trivia**
- **Stationarity**: mean/variance/autocorrelation constant over time — required by many classical models (ARIMA); test with Augmented Dickey-Fuller (ADF) test
- **Differencing**: subtracting previous value from current to remove trend and induce stationarity
- **Seasonality vs Trend vs Residual**: decomposition splits a series into these three components (additive or multiplicative)
- **Autocorrelation (ACF)** vs **Partial Autocorrelation (PACF)**: ACF shows correlation with all lags, PACF isolates the direct effect of a specific lag (removing effect of intermediate lags) — used to pick AR/MA orders
- **ARIMA(p,d,q)**: AR order (p) + differencing (d) + MA order (q); SARIMA adds seasonal terms
- **Exponential smoothing**: weights recent observations more, decays exponentially for older ones (Holt-Winters handles trend + seasonality)
- **Lag features / rolling statistics**: rolling mean/std, lag(1), lag(7), etc. are the bread-and-butter of tree-based time series models
- **Data leakage in time series**: never use future data (even via random k-fold CV) to predict the past — use `TimeSeriesSplit` or walk-forward validation
- **Prophet**: Facebook’s additive model (trend + seasonality + holidays), robust to missing data, good baseline
**Code**
### 9.1 Rolling / lag feature engineering
```python
df[“lag_1”] = df[“value”].shift(1)
df[“lag_7”] = df[“value”].shift(7)
df[“rolling_mean_7”] = df[“value”].shift(1).rolling(window=7).mean()
df[“rolling_std_7”] = df[“value”].shift(1).rolling(window=7).std()
```
### 9.2 Seasonal decomposition
```python
from statsmodels.tsa.seasonal import seasonal_decompose
result = seasonal_decompose(df[“value”], model=”additive”, period=12)
result.plot()
```
### 9.3 ADF stationarity test
```python
from statsmodels.tsa.stattools import adfuller
result = adfuller(df[“value”])
print(“Stationary” if result[1] < 0.05 else “Non-stationary”)
```
### 9.4 ARIMA model fit + forecast
```python
from statsmodels.tsa.arima.model import ARIMA
model = ARIMA(train[“value”], order=(2, 1, 2))
fitted = model.fit()
forecast = fitted.forecast(steps=10)
```
### 9.5 Walk-forward validation
```python
from sklearn.model_selection import TimeSeriesSplit
tscv = TimeSeriesSplit(n_splits=5)
for train_idx, val_idx in tscv.split(df):
train, val = df.iloc[train_idx], df.iloc[val_idx]
# fit on train, evaluate on val, repeat
```
— -
## 10. DEEP LEARNING QUICK SNIPPETS (PyTorch)
### 10.1 Custom Dataset + DataLoader
```python
import torch
from torch.utils.data import Dataset, DataLoader
class TabularDataset(Dataset):
def __init__(self, X, y):
self.X = torch.tensor(X, dtype=torch.float32)
self.y = torch.tensor(y, dtype=torch.float32)
def __len__(self):
return len(self.X)
def __getitem__(self, idx):
return self.X[idx], self.y[idx]
loader = DataLoader(TabularDataset(X_train, y_train), batch_size=32, shuffle=True)
```
### 10.2 Simple feedforward net + training loop
```python
import torch
import torch.nn as nn
class MLP(nn.Module):
def __init__(self, in_dim, hidden=64):
super().__init__()
self.net = nn.Sequential(
nn.Linear(in_dim, hidden), nn.ReLU(),
nn.Linear(hidden, 1), nn.Sigmoid()
)
def forward(self, x):
return self.net(x).squeeze(-1)
model = MLP(in_dim=X_train.shape[1])
optimizer = torch.optim.Adam(model.parameters(), lr=1e-3)
criterion = nn.BCELoss()
for epoch in range(20):
for xb, yb in loader:
optimizer.zero_grad()
preds = model(xb)
loss = criterion(preds, yb)
loss.backward()
optimizer.step()
```
### 10.3 Early stopping (manual implementation)
```python
best_val_loss, patience, counter = float(“inf”), 5, 0
for epoch in range(100):
train_loss = train_one_epoch(model, loader, optimizer, criterion)
val_loss = evaluate(model, val_loader, criterion)
if val_loss < best_val_loss:
best_val_loss, counter = val_loss, 0
torch.save(model.state_dict(), “best_model.pt”)
else:
counter += 1
if counter >= patience:
print(f”Early stopping at epoch {epoch}”)
break
```
— -
## 11. SQL-STYLE / DATA WRANGLING SNIPPETS
### 11.1 Window functions in pandas (rank, cumsum, running total)
```python
df[“rank_in_group”] = df.groupby(“category”)[“value”].rank(ascending=False, method=”dense”)
df[“cumsum_in_group”] = df.groupby(“category”)[“value”].cumsum()
df[“pct_of_group_total”] = df[“value”] / df.groupby(“category”)[“value”].transform(“sum”)
```
### 11.2 SQL-equivalent joins in pandas
```python
pd.merge(orders, customers, on=”customer_id”, how=”inner”) # SQL INNER JOIN
pd.merge(orders, customers, on=”customer_id”, how=”left”) # SQL LEFT JOIN
orders.merge(customers, on=”customer_id”, how=”outer”, indicator=True) # find mismatches via _merge col
```
### 11.3 Top-N per group (common “top 3 products per category” ask)
```python
top_n = (df.sort_values(“sales”, ascending=False)
.groupby(“category”)
.head(3))
```
### 11.4 Pivoting long <-> wide
```python
wide = df.pivot(index=”date”, columns=”metric”, values=”value”)
long = wide.reset_index().melt(id_vars=”date”, var_name=”metric”, value_name=”value”)
```
### 11.5 Rolling groupby (e.g., 7-day rolling avg per store)
```python
df = df.sort_values([“store_id”, “date”])
df[“rolling_avg_7”] = df.groupby(“store_id”)[“sales”].transform(
lambda x: x.shift(1).rolling(7).mean()
)
```
# Part 1 of 6 — Trivia: ML / NLP / RAG / Chunking / Tokenizing / OpenCV
*[INDEX.md] | [part2.md] →*
## Contents of this part
- 1. MACHINE LEARNING — MCQ TRIVIA
- 2. NLP — MCQ TRIVIA
- 3. RAG (RETRIEVAL AUGMENTED GENERATION) — MCQ TRIVIA
- 4. CHUNKING — MCQ TRIVIA
- 5. TOKENIZING — MCQ TRIVIA
- 6. OPENCV — MCQ TRIVIA
— -
ML / Stats / NLP / RAG / Chunking / Tokenizing / OpenCV / Pandas / Time Series / DL
*(v2 + INDEX + a large batch of new likely-to-appear code snippets, merged into one doc)*
— -
## 1. MACHINE LEARNING — MCQ TRIVIA
**Bias-Variance Tradeoff**
- High bias → underfitting (model too simple, high train + test error)
- High variance → overfitting (low train error, high test error)
- Total error = Bias² + Variance + Irreducible error
**Regularization**
- L1 (Lasso) → adds |w|, produces sparse weights (feature selection)
- L2 (Ridge) → adds w², shrinks weights smoothly, doesn’t zero them out
- Elastic Net = L1 + L2 combined
- Dropout, early stopping, data augmentation = regularization for neural nets
**Evaluation Metrics**
- Precision = TP/(TP+FP) — “of predicted positives, how many correct”
- Recall = TP/(TP+FN) — “of actual positives, how many found”
- F1 = harmonic mean of precision & recall = 2PR/(P+R)
- ROC-AUC: TPR vs FPR across thresholds; 0.5 = random, 1.0 = perfect
- PR-AUC preferred over ROC-AUC on imbalanced data
- Accuracy is misleading on imbalanced classes
**Optimization**
- SGD → noisy, one/few samples per update
- Momentum → adds velocity term, dampens oscillation
- RMSprop → adaptive LR using moving avg of squared gradients
- Adam = Momentum + RMSprop (most common default)
- Learning rate too high → divergence; too low → slow convergence/local minima stuck
**Loss Functions**
- MSE → regression
- Cross-Entropy → classification (Binary CE for 2-class, Categorical CE for multi-class)
- Hinge loss → SVM
**Trees & Ensembles**
- Gini impurity vs Entropy (Information Gain) — both measure node purity, gini is faster (no log)
- Bagging (Random Forest): parallel, reduces variance, bootstrap sampling
- Boosting (AdaBoost, GBM, XGBoost, LightGBM): sequential, reduces bias, each model fixes previous errors
- Random Forest: bagging + random feature subset per split
- **XGBoost vs LightGBM**: XGBoost splits level-wise (more balanced trees, slower), LightGBM splits leaf-wise (faster, can overfit more on small data); LightGBM uses histogram-based binning + GOSS/EFB for speed on large datasets
**Other Core Concepts**
- PCA: unsupervised, finds directions (eigenvectors of covariance matrix) of max variance
- SVD used to compute PCA; also basis of collaborative filtering
- Naive Bayes: assumes feature independence given class; fast, works well on text
- k-NN: lazy learner, no training phase, sensitive to feature scaling
- SVM: maximizes margin; kernel trick for non-linear boundaries (RBF, polynomial)
- K-Means: unsupervised clustering, sensitive to initialization (use k-means++), needs k specified, elbow method to pick k
- Cross-validation: k-fold reduces variance of performance estimate vs single train/test split
- Vanishing/Exploding gradients → deep nets; fixed by ReLU, batch norm, residual connections, gradient clipping
- Batch Normalization: normalizes layer inputs, speeds up training, slight regularization effect
- Activation functions: Sigmoid (vanishing gradient issue), Tanh, ReLU (dead neuron issue), Leaky ReLU, GELU (used in transformers), Softmax (multi-class output)
### 1.1 Feature Engineering & Preprocessing (commonly missed)
- **Missing data**: mean/median imputation (numeric), mode imputation (categorical), KNN-imputation, or drop rows/cols if missingness is small/random; median preferred over mean when outliers present
- **Categorical encoding**: One-Hot Encoding (nominal, no order — avoid for high-cardinality), Label Encoding (ordinal, implies order — misleading for tree-agnostic linear models), Target/Mean Encoding (risk of leakage, needs CV-safe implementation)
- **Feature scaling**: StandardScaler (zero mean, unit variance) / MinMaxScaler (0–1) — **required** for distance-based & gradient-based models (KNN, SVM, k-means, logistic/linear regression, neural nets); **not needed** for tree-based models (RF, XGBoost, decision trees) since splits are scale-invariant
- **Class imbalance fixes**: SMOTE (synthetic oversampling of minority class), random undersampling of majority, `class_weight=’balanced’`, using PR-AUC/F1 instead of accuracy
- **Curse of dimensionality**: as feature count grows, data becomes sparse in space, distance metrics lose meaning, models need exponentially more data
- **Multicollinearity**: correlated features destabilize linear model coefficients — check via VIF (Variance Inflation Factor), fix by dropping/combining features or regularizing (Ridge)
- **Outliers**: IQR method (< Q1–1.5IQR or > Q3+1.5IQR) or z-score (|z|>3); tree models robust to outliers, linear models are not
### 1.2 Statistics & Probability (classic DS-round trivia)
- **Bayes’ Theorem**: P(A|B) = P(B|A)·P(A) / P(B)
- **Central Limit Theorem**: sampling distribution of the sample mean approaches normal as n grows, regardless of population distribution — justifies using normal-based CIs/tests on large samples
- **p-value**: probability of observing data this extreme (or more) *if the null hypothesis were true*; p < 0.05 conventionally → reject null. p-value is **not** the probability the null is true
- **Type I error** (false positive, rejecting true null, rate = α) vs **Type II error** (false negative, failing to reject false null, rate = β); **power = 1 − β**
- **Confidence Interval**: range that would contain the true parameter in X% of repeated samples (not “X% chance the true value is in this interval”)
- **Correlation ≠ Causation** — always a favorite trivia line
- **Pearson r**: measures *linear* relationship, sensitive to outliers, range −1 to 1
- **Spearman ρ**: rank-based, captures monotonic (not necessarily linear) relationships, robust to outliers
- **Covariance vs Correlation**: correlation = covariance normalized by std devs (unit-free, bounded)
- **A/B testing**: control vs treatment groups, test significance with a two-sample t-test or z-test, watch for multiple-testing / peeking problems
- **Chi-square test**: tests independence between categorical variables
- **ANOVA**: tests whether means differ across 3+ groups (extension of t-test to multiple groups)
- **z-score**: (x − μ)/σ — standardized distance from the mean
- **Bootstrap**: resample with replacement to estimate sampling distribution / CI without distributional assumptions
— -
## 2. NLP — MCQ TRIVIA
**Text Preprocessing**
- Stemming: crude, rule-based, chops suffixes (Porter, Snowball) → “running”→”run” (may produce non-words)
- Lemmatization: dictionary-based, returns valid root word using POS context → slower, more accurate
- Stop word removal, lowercasing — classic pipeline (less used with transformers, which need raw-ish text)
**Text Representation**
- Bag of Words: word counts, ignores order
- TF-IDF: TF(t,d) × log(N/df(t)) — downweights common words, upweights rare-but-relevant ones
- Word2Vec: CBOW (predict word from context, faster, good for frequent words) vs Skip-gram (predict context from word, better for rare words)
- GloVe: co-occurrence matrix + factorization (global statistics, unlike Word2Vec’s local window)
- Static embeddings (Word2Vec/GloVe) = one vector per word regardless of context
- Contextual embeddings (BERT/ELMo) = vector changes based on sentence context
**Transformers**
- Self-attention: Q, K, V matrices; Attention(Q,K,V) = softmax(QKᵀ/√dₖ)V
- √dₖ scaling prevents large dot products from causing vanishing gradients in softmax
- Multi-head attention: parallel attention heads capture different relationship types
- Positional encoding needed because self-attention has no inherent sequence order (sinusoidal or learned)
- Encoder-only (BERT): bidirectional context, good for understanding/classification/embeddings
- Decoder-only (GPT): causal/unidirectional (masked), good for generation
- Encoder-Decoder (T5, BART): good for seq2seq tasks (translation, summarization)
- BERT pretraining: Masked LM (predict masked tokens) + Next Sentence Prediction
- GPT pretraining: Causal/Autoregressive LM (predict next token)
- Cross-attention (in encoder-decoder): decoder attends to encoder outputs
**Generation / Decoding**
- Greedy decoding: picks highest-prob token each step — fast but suboptimal
- Beam search: keeps top-k sequences — better quality, more compute
- Top-k / Top-p (nucleus) sampling: for diverse/creative generation
- Temperature: >1 more random/diverse, <1 more deterministic/conservative
**Metrics**
- Perplexity: measures how well a LM predicts a sample — lower is better
- BLEU: n-gram precision, used for translation
- ROUGE: recall-oriented, used for summarization
- METEOR: considers synonyms/stemming, better human correlation than BLEU
**Other**
- NER: identifies entities (PERSON, ORG, LOC, DATE)
- POS tagging: assigns grammatical roles (noun, verb, etc.)
- Cosine similarity: cos(θ) = (A·B)/(‖A‖‖B‖) — measures angle not magnitude, standard for embeddings
### 2.1 Extra NLP trivia points
- **Edit distance (Levenshtein)**: min insert/delete/substitute ops to turn one string into another — used for fuzzy matching, spell-check
- **Jaccard similarity**: |A∩B| / |A∪B| — set-overlap similarity, common for n-gram/keyword comparisons
- **N-grams**: contiguous sequences of n tokens; unigram/bigram/trigram used as classical features before embeddings
- **OOV handling**: subword tokenization is the main modern fix (see Section 5); older word-level models used an `<UNK>` token
- **spaCy vs NLTK**: spaCy is production-grade/fast (pipeline-based, pretrained models), NLTK is more academic/teaching-oriented with more granular control
— -
## 3. RAG (RETRIEVAL AUGMENTED GENERATION) — MCQ TRIVIA
**Pipeline**
Ingest docs → Chunk → Embed chunks → Store in vector DB → (Query time) Embed query → Retrieve top-k similar chunks → Optionally rerank → Augment prompt with retrieved context → LLM generates grounded answer
**Why RAG**
- Reduces hallucination by grounding generation in retrieved facts
- Avoids need to fine-tune/retrain for new/updated knowledge
- Cheaper than fine-tuning for knowledge injection; keeps knowledge current without retraining
**Chunking (see section 4 for detail)**
- Chunk size directly affects retrieval precision vs context completeness
- Overlap between chunks prevents losing context at boundaries
**Retrieval**
- Dense retrieval: embedding + vector similarity search (semantic)
- Sparse retrieval: BM25/TF-IDF (keyword/lexical match)
- Hybrid search: combines dense + sparse (often best in practice), fused via reciprocal rank fusion (RRF)
- Similarity metrics: cosine similarity (most common), dot product, Euclidean (L2) distance
**Vector Databases**
- FAISS (Meta) — library, not a full DB, in-memory/on-disk indexes, no built-in persistence/metadata filtering out of the box
- Pinecone, Weaviate, Qdrant, Milvus, Chroma — managed/full-featured vector DBs with metadata filtering
- Index types: Flat (exact, slow), IVF (inverted file, approximate), HNSW (graph-based, fast approximate nearest neighbor — most popular)
- ANN (Approximate Nearest Neighbor) trades a bit of accuracy for major speed gains at scale
**Reranking**
- Cross-encoder reranker: scores (query, chunk) pairs jointly — much more accurate but slower than bi-encoder retrieval
- Bi-encoder (used for initial retrieval): encodes query and docs separately — fast, enables precomputed embeddings
**Advanced RAG Concepts**
- HyDE (Hypothetical Document Embeddings): generate a hypothetical answer first, embed that, then retrieve — improves recall for vague queries
- Query rewriting/expansion: reformulate user query for better retrieval
- Multi-query retrieval: generate several query variants, union results
- Parent-document retrieval: retrieve small chunks but return larger surrounding context to the LLM
- Self-RAG / Corrective RAG: model critiques/checks retrieved docs before generating
**Evaluation**
- Context Precision/Recall: is retrieved context relevant/complete?
- Faithfulness: does generated answer stay grounded in retrieved context (no hallucination)?
- Answer Relevance: does the answer address the actual question?
- MRR (Mean Reciprocal Rank), Recall@k, nDCG — standard IR retrieval metrics
— -
## 4. CHUNKING — MCQ TRIVIA
- **Fixed-size chunking**: split every N tokens/characters — simple, fast, but can cut mid-sentence/mid-idea
- **Recursive character splitting**: tries paragraph → sentence → word boundaries recursively until chunk fits size limit (most common default, e.g. LangChain’s RecursiveCharacterTextSplitter)
- **Sentence-based chunking**: splits on sentence boundaries, keeps semantic units intact
- **Semantic chunking**: splits based on embedding similarity shifts between sentences (topic change detection) — more coherent chunks, more compute
- **Sliding window with overlap**: consecutive chunks share ~10–20% overlap to preserve context across boundaries
- **Document-structure-aware chunking**: splits along markdown headers/sections, table boundaries, etc.
- Small chunks → higher precision, less context per chunk, more chunks needed for full answer
- Large chunks → more context, but noisier retrieval (less precise similarity match), risk exceeding context window
- Typical starting point: 200–500 tokens per chunk with 10–20% overlap (tune per use case)
- Chunk size should roughly match expected query/answer granularity
— -
## 5. TOKENIZING — MCQ TRIVIA
- **Word-level tokenization**: simple but huge vocab, can’t handle OOV (out-of-vocabulary) words
- **Character-level**: tiny vocab, no OOV issue, but very long sequences, harder to learn meaning
- **Subword tokenization** (standard in modern LLMs): balances vocab size and sequence length, handles OOV by breaking into known pieces
— **BPE (Byte Pair Encoding)**: iteratively merges most frequent adjacent symbol pairs until vocab size reached (used in GPT-2/GPT-3, RoBERTa)
— **WordPiece**: similar to BPE but merges based on likelihood improvement, not just frequency (used in BERT)
— **SentencePiece**: language-agnostic, treats text as raw stream (no pre-tokenization needed), supports BPE or Unigram mode (used in T5, LLaMA)
— **Unigram LM**: starts with large vocab, prunes down by removing tokens that hurt likelihood least
- **Special tokens**: [CLS] (classification/sentence embedding, BERT), [SEP] (segment separator), [PAD] (padding to equal length), [MASK] (masked LM), `<bos>`/`<eos>` (begin/end of sequence, GPT-style)
- **tiktoken**: OpenAI’s fast BPE tokenizer library (used for GPT models)
- More tokens ≠ more words — 1 token ≈ ~4 characters or ~0.75 words in English (rule of thumb)
- Tokenizer vocab size is fixed at pretraining time — can’t add new tokens without retraining embeddings for them
— -
## 6. OPENCV — MCQ TRIVIA
- `cv2.imread()` loads images in **BGR** order by default, not RGB — classic gotcha question
- Color space conversions: `cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)`, `COLOR_BGR2RGB`, `COLOR_BGR2HSV`
- HSV useful for color-based segmentation (robust to lighting changes vs RGB)
- **Thresholding**: `cv2.threshold()` (global), `cv2.adaptiveThreshold()` (local, better for uneven lighting), Otsu’s method (auto-picks global threshold)
- **Edge detection**: Canny (`cv2.Canny()`) — multi-stage: noise reduction → gradient (Sobel) → non-max suppression → hysteresis thresholding; Sobel = gradient-based, simpler, noisier
- **Blurring/denoising**: Gaussian blur (smooths, weighted by distance), Median blur (great for salt-and-pepper noise), Bilateral filter (edge-preserving smoothing)
- **Morphological ops** (on binary images): Erosion (shrinks white regions, removes noise), Dilation (expands white regions, fills gaps), Opening = erosion→dilation (removes small noise), Closing = dilation→erosion (fills small holes)
- **Contours**: `cv2.findContours()` — used for shape detection, object counting; needs binary image input
- **Feature detectors**: SIFT (scale/rotation invariant, patented historically, now free), ORB (fast, free alternative to SIFT/SURF, binary descriptors), Harris Corner Detector (basic corner detection)
- **Resizing/interpolation**: `cv2.resize()` — `INTER_LINEAR` (default, good general), `INTER_NEAREST` (fast, blocky), `INTER_CUBIC`/`INTER_AREA` (better quality, `INTER_AREA` best for shrinking)
- Typical OCR preprocessing pipeline: grayscale → denoise → threshold/binarize → deskew → (dilate/erode to clean) → feed to OCR engine
### 6.1 Extra OpenCV trivia
- **Haar cascades**: classic fast object/face detector, XML-based pretrained classifiers, precursor to deep-learning detectors
- **Template matching** (`cv2.matchTemplate`): slides a template image over the source to find the best match location — sensitive to scale/rotation changes
- **Histogram equalization** (`cv2.equalizeHist`): improves contrast in low-contrast grayscale images by spreading out intensity distribution; CLAHE = adaptive/local version, avoids over-amplifying noise
- **Perspective/Affine transform**: `cv2.getPerspectiveTransform` + `cv2.warpPerspective` for correcting skew/perspective (e.g. document scanning); affine preserves parallel lines, perspective does not
- **Connected components** (`cv2.connectedComponents`): labels separate blobs in a binary image — used for counting objects
— -
# Part 2 of 6 — Code Snippets (all topics, §7.1–7.60)
*← [part1.md] | [INDEX.md] | [part3.md] →*
## Contents of this part
- 7. LIKELY CODE SNIPPETS
— -
## 7. LIKELY CODE SNIPPETS
### 7.1 Train/test split + basic classification metrics
```python
from sklearn.model_selection import train_test_split
from sklearn.metrics import precision_score, recall_score, f1_score, confusion_matrix
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42, stratify=y)
# after prediction
precision = precision_score(y_test, y_pred)
recall = recall_score(y_test, y_pred)
f1 = f1_score(y_test, y_pred)
cm = confusion_matrix(y_test, y_pred)
```
### 7.2 Cosine similarity (numpy, no sklearn)
```python
import numpy as np
def cosine_similarity(a, b):
a, b = np.array(a), np.array(b)
return np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b))
```
### 7.3 Simple sliding-window chunking with overlap
```python
def chunk_text(text, chunk_size=500, overlap=100):
chunks = []
start = 0
while start < len(text):
end = start + chunk_size
chunks.append(text[start:end])
start += chunk_size — overlap
return chunks
```
### 7.4 Sentence-aware recursive-style chunking (simplified)
```python
def recursive_split(text, max_chars=500, separators=(“\n\n”, “\n”, “. “, “ “)):
if len(text) <= max_chars:
return [text]
for sep in separators:
if sep in text:
parts = text.split(sep)
break
else:
parts = list(text)
chunks, current = [], “”
for part in parts:
candidate = current + sep + part if current else part
if len(candidate) <= max_chars:
current = candidate
else:
if current:
chunks.append(current)
current = part
if current:
chunks.append(current)
return chunks
```
### 7.5 Minimal BPE tokenizer training loop (concept-level)
```python
from collections import Counter
def get_pair_freqs(vocab):
pairs = Counter()
for word, freq in vocab.items():
symbols = word.split()
for i in range(len(symbols) — 1):
pairs[(symbols[i], symbols[i + 1])] += freq
return pairs
def merge_vocab(pair, vocab):
new_vocab = {}
bigram = “ “.join(pair)
replacement = “”.join(pair)
for word in vocab:
new_word = word.replace(bigram, replacement)
new_vocab[new_word] = vocab[word]
return new_vocab
# vocab: dict of “w o r d </w>” -> frequency
# repeat for num_merges: find most frequent pair, merge it
for _ in range(num_merges):
pairs = get_pair_freqs(vocab)
if not pairs:
break
best = max(pairs, key=pairs.get)
vocab = merge_vocab(best, vocab)
```
### 7.6 Scaled dot-product attention (from scratch, numpy)
```python
import numpy as np
def softmax(x, axis=-1):
e = np.exp(x — np.max(x, axis=axis, keepdims=True))
return e / np.sum(e, axis=axis, keepdims=True)
def scaled_dot_product_attention(Q, K, V):
d_k = Q.shape[-1]
scores = Q @ K.T / np.sqrt(d_k)
weights = softmax(scores, axis=-1)
return weights @ V
```
### 7.7 Minimal RAG retrieval (embedding + top-k) pseudocode
```python
import numpy as np
def retrieve_top_k(query_embedding, chunk_embeddings, chunks, k=3):
sims = [cosine_similarity(query_embedding, ce) for ce in chunk_embeddings]
top_idx = np.argsort(sims)[::-1][:k]
return [chunks[i] for i in top_idx]
def build_prompt(query, retrieved_chunks):
context = “\n\n”.join(retrieved_chunks)
return f”Context:\n{context}\n\nQuestion: {query}\nAnswer based only on the context above:”
```
### 7.8 OpenCV: basic preprocessing + Canny edge pipeline
```python
import cv2
img = cv2.imread(“image.jpg”) # BGR
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
blurred = cv2.GaussianBlur(gray, (5, 5), 0)
edges = cv2.Canny(blurred, threshold1=50, threshold2=150)
# find contours
contours, _ = cv2.findContours(edges, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
```
### 7.9 OpenCV: adaptive thresholding (good for OCR preprocessing)
```python
import cv2
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
thresh = cv2.adaptiveThreshold(
gray, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C,
cv2.THRESH_BINARY, blockSize=11, C=2
)
```
### 7.10 K-Means from scratch (common ML coding-round ask)
```python
import numpy as np
def kmeans(X, k, iters=100):
centroids = X[np.random.choice(len(X), k, replace=False)]
for _ in range(iters):
distances = np.linalg.norm(X[:, None] — centroids[None, :], axis=2)
labels = np.argmin(distances, axis=1)
new_centroids = np.array([X[labels == i].mean(axis=0) for i in range(k)])
if np.allclose(centroids, new_centroids):
break
centroids = new_centroids
return labels, centroids
```
### 7.11 Simple text preprocessing pipeline
```python
import re
def preprocess(text):
text = text.lower()
text = re.sub(r”[^a-z0–9\s]”, “”, text)
tokens = text.split()
return tokens
```
### 7.12 Logistic Regression from scratch (batch gradient descent)
```python
import numpy as np
def sigmoid(z):
return 1 / (1 + np.exp(-z))
def logistic_regression(X, y, lr=0.1, epochs=1000):
n, d = X.shape
w, b = np.zeros(d), 0.0
for _ in range(epochs):
z = X @ w + b
preds = sigmoid(z)
grad_w = X.T @ (preds — y) / n
grad_b = np.mean(preds — y)
w -= lr * grad_w
b -= lr * grad_b
return w, b
```
### 7.13 Linear Regression from scratch (gradient descent)
```python
import numpy as np
def linear_regression(X, y, lr=0.01, epochs=1000):
n, d = X.shape
w, b = np.zeros(d), 0.0
for _ in range(epochs):
preds = X @ w + b
grad_w = -(2/n) * X.T @ (y — preds)
grad_b = -(2/n) * np.sum(y — preds)
w -= lr * grad_w
b -= lr * grad_b
return w, b
```
### 7.14 PCA from scratch (numpy, via covariance eigen-decomposition)
```python
import numpy as np
def pca(X, n_components=2):
X_centered = X — X.mean(axis=0)
cov = np.cov(X_centered, rowvar=False)
eigvals, eigvecs = np.linalg.eigh(cov) # ascending order
top_idx = np.argsort(eigvals)[::-1][:n_components]
components = eigvecs[:, top_idx]
return X_centered @ components
```
### 7.15 Pipeline + StandardScaler + GridSearchCV (sklearn, realistic OA ask)
```python
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC
from sklearn.model_selection import GridSearchCV
pipe = Pipeline([
(“scaler”, StandardScaler()),
(“clf”, SVC())
])
param_grid = {“clf__C”: [0.1, 1, 10], “clf__kernel”: [“linear”, “rbf”]}
grid = GridSearchCV(pipe, param_grid, cv=5, scoring=”f1")
grid.fit(X_train, y_train)
best_model = grid.best_estimator_
```
### 7.16 Handling class imbalance with SMOTE
```python
from imblearn.over_sampling import SMOTE
smote = SMOTE(random_state=42)
X_resampled, y_resampled = smote.fit_resample(X_train, y_train)
```
### 7.17 Stratified K-Fold cross-validation
```python
from sklearn.model_selection import StratifiedKFold, cross_val_score
skf = StratifiedKFold(n_splits=5, shuffle=True, random_state=42)
scores = cross_val_score(model, X, y, cv=skf, scoring=”f1")
print(scores.mean(), scores.std())
```
### 7.18 ROC curve + AUC
```python
from sklearn.metrics import roc_curve, roc_auc_score
import matplotlib.pyplot as plt
probs = model.predict_proba(X_test)[:, 1]
fpr, tpr, thresholds = roc_curve(y_test, probs)
auc = roc_auc_score(y_test, probs)
plt.plot(fpr, tpr, label=f”AUC = {auc:.2f}”)
plt.plot([0, 1], [0, 1], “ — “)
plt.xlabel(“FPR”); plt.ylabel(“TPR”); plt.legend()
```
### 7.19 TF-IDF vectorization (sklearn)
```python
from sklearn.feature_extraction.text import TfidfVectorizer
vectorizer = TfidfVectorizer(stop_words=”english”, max_features=5000)
X_tfidf = vectorizer.fit_transform(corpus) # sparse matrix
feature_names = vectorizer.get_feature_names_out()
```
### 7.20 Word2Vec (gensim)
```python
from gensim.models import Word2Vec
sentences = [doc.split() for doc in corpus]
model = Word2Vec(sentences, vector_size=100, window=5, min_count=2, sg=1) # sg=1 -> skip-gram, sg=0 -> CBOW
vector = model.wv[“machine”]
similar = model.wv.most_similar(“machine”, topn=5)
```
### 7.21 Contextual embeddings with a pretrained BERT (HuggingFace)
```python
from transformers import AutoTokenizer, AutoModel
import torch
tokenizer = AutoTokenizer.from_pretrained(“bert-base-uncased”)
model = AutoModel.from_pretrained(“bert-base-uncased”)
inputs = tokenizer(“Curiflow OA prep”, return_tensors=”pt”)
with torch.no_grad():
outputs = model(**inputs)
cls_embedding = outputs.last_hidden_state[:, 0, :] # [CLS] token embedding
```
### 7.22 NER + POS tagging (spaCy)
```python
import spacy
nlp = spacy.load(“en_core_web_sm”)
doc = nlp(“Sundar Pichai works at Google in California.”)
for ent in doc.ents:
print(ent.text, ent.label_) # NER
for token in doc:
print(token.text, token.pos_) # POS tagging
```
### 7.23 N-gram generation
```python
def generate_ngrams(tokens, n=2):
return [tuple(tokens[i:i+n]) for i in range(len(tokens) — n + 1)]
```
### 7.24 Levenshtein (edit) distance from scratch
```python
def edit_distance(a, b):
m, n = len(a), len(b)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
cost = 0 if a[i-1] == b[j-1] else 1
dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost)
return dp[m][n]
```
### 7.25 Full mini RAG pipeline: sentence-transformers + FAISS
```python
from sentence_transformers import SentenceTransformer
import faiss
import numpy as np
embedder = SentenceTransformer(“all-MiniLM-L6-v2”)
chunk_embeddings = embedder.encode(chunks, normalize_embeddings=True)
index = faiss.IndexFlatIP(chunk_embeddings.shape[1]) # inner product == cosine sim (normalized)
index.add(np.array(chunk_embeddings))
query_embedding = embedder.encode([query], normalize_embeddings=True)
scores, indices = index.search(np.array(query_embedding), k=3)
retrieved = [chunks[i] for i in indices[0]]
```
### 7.26 Semantic chunking (embedding-similarity-based split)
```python
def semantic_chunk(sentences, embedder, threshold=0.75):
embeddings = embedder.encode(sentences, normalize_embeddings=True)
chunks, current = [], [sentences[0]]
for i in range(1, len(sentences)):
sim = np.dot(embeddings[i-1], embeddings[i])
if sim < threshold: # topic shift detected
chunks.append(“ “.join(current))
current = [sentences[i]]
else:
current.append(sentences[i])
chunks.append(“ “.join(current))
return chunks
```
### 7.27 tiktoken usage (OpenAI-style BPE tokenizer)
```python
import tiktoken
enc = tiktoken.get_encoding(“cl100k_base”)
tokens = enc.encode(“Curiflow OA is tomorrow”)
num_tokens = len(tokens)
decoded = enc.decode(tokens)
```
### 7.28 Train a BPE tokenizer from scratch (HuggingFace `tokenizers` library)
```python
from tokenizers import Tokenizer
from tokenizers.models import BPE
from tokenizers.trainers import BpeTrainer
from tokenizers.pre_tokenizers import Whitespace
tokenizer = Tokenizer(BPE(unk_token=”[UNK]”))
tokenizer.pre_tokenizer = Whitespace()
trainer = BpeTrainer(vocab_size=5000, special_tokens=[“[UNK]”, “[CLS]”, “[SEP]”, “[PAD]”, “[MASK]”])
tokenizer.train(files=[“corpus.txt”], trainer=trainer)
output = tokenizer.encode(“subword tokenization example”)
print(output.tokens)
```
### 7.29 OpenCV: Haar cascade face detection
```python
import cv2
face_cascade = cv2.CascadeClassifier(cv2.data.haarcascades + “haarcascade_frontalface_default.xml”)
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
faces = face_cascade.detectMultiScale(gray, scaleFactor=1.1, minNeighbors=5)
for (x, y, w, h) in faces:
cv2.rectangle(img, (x, y), (x+w, y+h), (0, 255, 0), 2)
```
### 7.30 OpenCV: ORB feature matching between two images
```python
import cv2
orb = cv2.ORB_create()
kp1, des1 = orb.detectAndCompute(img1, None)
kp2, des2 = orb.detectAndCompute(img2, None)
bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)
matches = sorted(bf.match(des1, des2), key=lambda m: m.distance)
matched_img = cv2.drawMatches(img1, kp1, img2, kp2, matches[:20], None)
```
### 7.31 OpenCV: template matching
```python
import cv2
result = cv2.matchTemplate(img_gray, template, cv2.TM_CCOEFF_NORMED)
_, max_val, _, max_loc = cv2.minMaxLoc(result)
top_left = max_loc
h, w = template.shape
bottom_right = (top_left[0] + w, top_left[1] + h)
cv2.rectangle(img, top_left, bottom_right, (0, 255, 0), 2)
```
### 7.32 OpenCV: bounding boxes from contours (object counting)
```python
import cv2
contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
for c in contours:
if cv2.contourArea(c) > 100: # filter noise
x, y, w, h = cv2.boundingRect(c)
cv2.rectangle(img, (x, y), (x+w, y+h), (0, 255, 0), 2)
print(“Object count:”, len(contours))
```
### 7.33 OpenCV: histogram equalization
```python
import cv2
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
equalized = cv2.equalizeHist(gray)
clahe = cv2.createCLAHE(clipLimit=2.0, tileGridSize=(8, 8)) # adaptive version
clahe_img = clahe.apply(gray)
```
### 7.34 OpenCV: perspective warp (document deskew)
```python
import numpy as np
import cv2
pts_src = np.float32([[56, 65], [368, 52], [28, 387], [389, 390]])
pts_dst = np.float32([[0, 0], [300, 0], [0, 300], [300, 300]])
M = cv2.getPerspectiveTransform(pts_src, pts_dst)
warped = cv2.warpPerspective(img, M, (300, 300))
```
### 7.35 t-test (hypothesis testing, scipy — classic stats-round ask)
```python
from scipy import stats
t_stat, p_value = stats.ttest_ind(group_a, group_b)
if p_value < 0.05:
print(“Statistically significant difference”)
```
### 7.36 Pandas quick reference (groupby, merge, missing values, pivot)
```python
import pandas as pd
df.groupby(“category”)[“value”].agg([“mean”, “sum”, “count”])
pd.merge(df1, df2, on=”id”, how=”left”) # how: left/right/inner/outer
df.isnull().sum() # missing value count per column
df[“col”].fillna(df[“col”].median(), inplace=True)
df.pivot_table(index=”date”, columns=”category”, values=”sales”, aggfunc=”sum”)
df.drop_duplicates(subset=[“id”], keep=”first”)
df[“col”].value_counts(normalize=True) # class distribution / imbalance check
```
— -
### HIGH-YIELD ADDITIONS
### 7.37 Handling missing data (sklearn imputers)
```python
from sklearn.impute import SimpleImputer, KNNImputer
num_imputer = SimpleImputer(strategy=”median”)
X_num = num_imputer.fit_transform(X[[“age”, “income”]])
cat_imputer = SimpleImputer(strategy=”most_frequent”)
X_cat = cat_imputer.fit_transform(X[[“gender”, “city”]])
knn_imputer = KNNImputer(n_neighbors=5)
X_knn = knn_imputer.fit_transform(X_numeric)
```
### 7.38 One-hot encoding (pandas vs sklearn, and why sklearn is safer)
```python
import pandas as pd
from sklearn.preprocessing import OneHotEncoder
# quick EDA-style (not leakage-safe across train/test)
df_encoded = pd.get_dummies(df, columns=[“city”], drop_first=True)
# leakage-safe: fit on train only, transform both
ohe = OneHotEncoder(handle_unknown=”ignore”, sparse_output=False)
X_train_enc = ohe.fit_transform(X_train[[“city”]])
X_test_enc = ohe.transform(X_test[[“city”]]) # unseen categories -> all zeros
```
### 7.39 Outlier detection — IQR method
```python
def remove_outliers_iqr(df, col):
Q1, Q3 = df[col].quantile(0.25), df[col].quantile(0.75)
IQR = Q3 — Q1
lower, upper = Q1–1.5 * IQR, Q3 + 1.5 * IQR
return df[(df[col] >= lower) & (df[col] <= upper)]
```
### 7.40 Outlier detection — Z-score method
```python
import numpy as np
def remove_outliers_zscore(df, col, threshold=3):
z = (df[col] — df[col].mean()) / df[col].std()
return df[np.abs(z) < threshold]
```
### 7.41 XGBoost classifier (very likely to appear)
```python
import xgboost as xgb
from sklearn.metrics import accuracy_score
model = xgb.XGBClassifier(
n_estimators=200, max_depth=6, learning_rate=0.1,
subsample=0.8, colsample_bytree=0.8, eval_metric=”logloss”
)
model.fit(X_train, y_train, eval_set=[(X_test, y_test)], verbose=False)
preds = model.predict(X_test)
print(accuracy_score(y_test, preds))
```
### 7.42 LightGBM classifier
```python
import lightgbm as lgb
train_data = lgb.Dataset(X_train, label=y_train)
params = {“objective”: “binary”, “metric”: “auc”, “num_leaves”: 31, “learning_rate”: 0.05}
model = lgb.train(params, train_data, num_boost_round=200)
preds = model.predict(X_test) # returns probabilities
```
### 7.43 Feature importance (tree-based models)
```python
import pandas as pd
import matplotlib.pyplot as plt
importances = pd.Series(model.feature_importances_, index=X_train.columns)
importances.sort_values(ascending=False).head(10).plot(kind=”barh”)
plt.gca().invert_yaxis()
```
### 7.44 Custom evaluation metric (e.g., weighted F1 by hand)
```python
def custom_f1(y_true, y_pred, beta=1):
tp = sum((yt == 1 and yp == 1) for yt, yp in zip(y_true, y_pred))
fp = sum((yt == 0 and yp == 1) for yt, yp in zip(y_true, y_pred))
fn = sum((yt == 1 and yp == 0) for yt, yp in zip(y_true, y_pred))
precision = tp / (tp + fp) if (tp + fp) else 0
recall = tp / (tp + fn) if (tp + fn) else 0
if precision + recall == 0:
return 0
return (1 + beta**2) * precision * recall / (beta**2 * precision + recall)
```
### 7.45 Time-aware train/test split (no shuffling — common trap)
```python
def time_series_split(df, date_col, split_date):
train = df[df[date_col] < split_date]
test = df[df[date_col] >= split_date]
return train, test
# or with sklearn for rolling CV:
from sklearn.model_selection import TimeSeriesSplit
tscv = TimeSeriesSplit(n_splits=5)
for train_idx, test_idx in tscv.split(X):
X_train, X_test = X[train_idx], X[test_idx]
```
### 7.46 Cyclical encoding of datetime features (sin/cos — common feature-eng ask)
```python
import numpy as np
df[“hour_sin”] = np.sin(2 * np.pi * df[“hour”] / 24)
df[“hour_cos”] = np.cos(2 * np.pi * df[“hour”] / 24)
df[“month_sin”] = np.sin(2 * np.pi * df[“month”] / 12)
df[“month_cos”] = np.cos(2 * np.pi * df[“month”] / 12)
# preserves cyclical distance (hour 23 close to hour 0), unlike raw integer encoding
```
### 7.47 Chi-square test of independence
```python
import pandas as pd
from scipy.stats import chi2_contingency
contingency = pd.crosstab(df[“gender”], df[“purchased”])
chi2, p, dof, expected = chi2_contingency(contingency)
print(“Significant” if p < 0.05 else “Not significant”)
```
### 7.48 One-way ANOVA
```python
from scipy import stats
f_stat, p_value = stats.f_oneway(group_a, group_b, group_c)
if p_value < 0.05:
print(“At least one group mean differs”)
```
### 7.49 Bootstrap confidence interval
```python
import numpy as np
Get EmperorAce’s stories in your inbox
Join Medium for free to get updates from this writer.
def bootstrap_ci(data, n_boot=10000, ci=95):
boot_means = [np.mean(np.random.choice(data, size=len(data), replace=True)) for _ in range(n_boot)]
lower = np.percentile(boot_means, (100 — ci) / 2)
upper = np.percentile(boot_means, 100 — (100 — ci) / 2)
return np.mean(data), lower, upper
```
### 7.50 Anomaly detection — Isolation Forest
```python
from sklearn.ensemble import IsolationForest
iso = IsolationForest(contamination=0.05, random_state=42)
preds = iso.fit_predict(X) # -1 = anomaly, 1 = normal
anomalies = X[preds == -1]
```
### 7.51 Pairwise cosine similarity matrix (vectorized, no loops)
```python
import numpy as np
def cosine_similarity_matrix(A):
norm = A / np.linalg.norm(A, axis=1, keepdims=True)
return norm @ norm.T
# sklearn equivalent
from sklearn.metrics.pairwise import cosine_similarity
sim_matrix = cosine_similarity(embeddings)
```
### 7.52 Simple item-based collaborative filtering recommender
```python
import numpy as np
import pandas as pd
def recommend_items(user_item_matrix, item_id, top_n=5):
sim = cosine_similarity(user_item_matrix.T) # item-item similarity
sim_df = pd.DataFrame(sim, index=user_item_matrix.columns, columns=user_item_matrix.columns)
return sim_df[item_id].sort_values(ascending=False)[1:top_n+1]
```
### 7.53 Saving/loading a trained model (pickle & joblib)
```python
import joblib
import pickle
joblib.dump(model, “model.pkl”) # preferred for sklearn (handles numpy arrays well)
loaded_model = joblib.load(“model.pkl”)
with open(“model.pkl”, “wb”) as f: # plain pickle alternative
pickle.dump(model, f)
```
### 7.54 Manual grid search (when GridSearchCV isn’t allowed / to show understanding)
```python
best_score, best_params = -1, None
for C in [0.1, 1, 10]:
for kernel in [“linear”, “rbf”]:
model = SVC(C=C, kernel=kernel)
scores = cross_val_score(model, X_train, y_train, cv=5, scoring=”f1")
if scores.mean() > best_score:
best_score, best_params = scores.mean(), {“C”: C, “kernel”: kernel}
print(best_params, best_score)
```
### 7.55 Data-leakage-safe preprocessing pipeline (fit scaler on train only)
```python
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train) # fit ONLY on train
X_test_scaled = scaler.transform(X_test) # transform test with train stats
# same rule applies to SMOTE, target encoding, imputers, feature selection, etc.
```
### 7.56 Multi-class classification report
```python
from sklearn.metrics import classification_report
print(classification_report(y_test, y_pred, target_names=[“classA”, “classB”, “classC”]))
```
### 7.57 Precision-Recall curve
```python
from sklearn.metrics import precision_recall_curve, average_precision_score
import matplotlib.pyplot as plt
probs = model.predict_proba(X_test)[:, 1]
precision, recall, thresholds = precision_recall_curve(y_test, probs)
ap = average_precision_score(y_test, probs)
plt.plot(recall, precision, label=f”AP = {ap:.2f}”)
plt.xlabel(“Recall”); plt.ylabel(“Precision”); plt.legend()
```
### 7.58 Decision Tree from scratch (simplified, Gini-based, binary split)
```python
import numpy as np
def gini(y):
classes, counts = np.unique(y, return_counts=True)
probs = counts / len(y)
return 1 — np.sum(probs ** 2)
def best_split(X, y):
best_gini, best_feat, best_thresh = 1, None, None
for feat in range(X.shape[1]):
thresholds = np.unique(X[:, feat])
for t in thresholds:
left_mask = X[:, feat] <= t
if left_mask.sum() == 0 or (~left_mask).sum() == 0:
continue
g_left, g_right = gini(y[left_mask]), gini(y[~left_mask])
w_gini = (left_mask.sum() * g_left + (~left_mask).sum() * g_right) / len(y)
if w_gini < best_gini:
best_gini, best_feat, best_thresh = w_gini, feat, t
return best_feat, best_thresh
```
### 7.59 Naive Bayes (Gaussian) from scratch
```python
import numpy as np
class GaussianNB:
def fit(self, X, y):
self.classes = np.unique(y)
self.mean = {c: X[y == c].mean(axis=0) for c in self.classes}
self.var = {c: X[y == c].var(axis=0) + 1e-9 for c in self.classes}
self.prior = {c: (y == c).mean() for c in self.classes}
def _gaussian(self, x, mean, var):
return np.exp(-((x — mean) ** 2) / (2 * var)) / np.sqrt(2 * np.pi * var)
def predict(self, X):
preds = []
for x in X:
posteriors = {c: np.log(self.prior[c]) + np.sum(np.log(self._gaussian(x, self.mean[c], self.var[c])))
for c in self.classes}
preds.append(max(posteriors, key=posteriors.get))
return np.array(preds)
```
### 7.60 Confusion matrix heatmap
```python
from sklearn.metrics import confusion_matrix
import seaborn as sns
import matplotlib.pyplot as plt
cm = confusion_matrix(y_test, y_pred)
sns.heatmap(cm, annot=True, fmt=”d”, cmap=”Blues”)
plt.xlabel(“Predicted”); plt.ylabel(“Actual”)
```
— -
# Part 4 of 6 — Algorithms 8–16 (SVM → Gradient Boosting)
*← [part3.md] | [INDEX.md] | [part5.md] →*
## Contents of this part
- Algorithm 8. Support Vector Machines (SVM)
- Algorithm 9. Naive Bayes
- Algorithm 10. K-Means Clustering
- Algorithm 11. Principal Component Analysis (PCA)
- Algorithm 12. Hierarchical Clustering
- Algorithm 13. Apriori Algorithm
- Algorithm 14. t-SNE
- Algorithm 15. AdaBoost
- Algorithm 16. Gradient Boosting
— -
## Algorithm 8. Support Vector Machines (SVM)
**Idea:** Find the hyperplane that maximizes the margin between two classes, trained via hinge loss + L2 regularization (soft-margin, linear kernel).
### From scratch (NumPy)
```python
import numpy as np
class SVMScratch:
def __init__(self, lr=0.001, lambda_param=0.01, n_iters=1000):
self.lr = lr
self.lambda_param = lambda_param # regularization strength
self.n_iters = n_iters
self.w = None
self.b = None
def fit(self, X, y):
X = np.asarray(X, dtype=float)
y_ = np.where(np.asarray(y) <= 0, -1, 1) # SVM expects labels in {-1, +1}
n_samples, n_features = X.shape
self.w = np.zeros(n_features)
self.b = 0.0
for _ in range(self.n_iters):
for idx, x_i in enumerate(X):
condition = y_[idx] * (x_i @ self.w — self.b) >= 1
if condition:
self.w -= self.lr * (2 * self.lambda_param * self.w)
else:
self.w -= self.lr * (2 * self.lambda_param * self.w — x_i * y_[idx])
self.b -= self.lr * y_[idx]
return self
def predict(self, X):
X = np.asarray(X, dtype=float)
approx = X @ self.w — self.b
return np.where(approx >= 0, 1, 0)
# Usage / verification (standardized features work best for gradient-based SVM)
Xs = (Xtr — Xtr.mean(0)) / Xtr.std(0)
Xste = (Xte — Xtr.mean(0)) / Xtr.std(0)
model = SVMScratch(lr=0.001, lambda_param=0.01, n_iters=500).fit(Xs, ytr)
acc = (model.predict(Xste) == yte).mean()
print(acc)
# Verified output: accuracy = 0.973
```
### scikit-learn equivalent
```python
from sklearn.svm import SVC
model = SVC(kernel=’linear’)
model.fit(Xs, ytr)
print(model.score(Xste, yte))
# Verified output: accuracy = 0.987 (matches scratch version closely;
# sklearn’s SVC solves the exact quadratic-programming dual problem)
```
— -
## Algorithm 9. Naive Bayes
**Idea:** Apply Bayes’ theorem assuming features are conditionally independent given the class. For continuous features, model each feature per class as a Gaussian (Gaussian Naive Bayes).
### From scratch (NumPy)
```python
import numpy as np
class GaussianNBScratch:
def fit(self, X, y):
X = np.asarray(X, dtype=float)
y = np.asarray(y)
self.classes = np.unique(y)
self.mean = {}
self.var = {}
self.priors = {}
for c in self.classes:
Xc = X[y == c]
self.mean[c] = Xc.mean(axis=0)
self.var[c] = Xc.var(axis=0) + 1e-9 # avoid division by zero
self.priors[c] = Xc.shape[0] / X.shape[0]
return self
def _gaussian_log_pdf(self, c, x):
mean = self.mean[c]
var = self.var[c]
num = -((x — mean) ** 2) / (2 * var)
den = -0.5 * np.log(2 * np.pi * var)
return np.sum(num + den)
def predict(self, X):
X = np.asarray(X, dtype=float)
preds = []
for x in X:
posteriors = []
for c in self.classes:
log_prior = np.log(self.priors[c])
log_likelihood = self._gaussian_log_pdf(c, x)
posteriors.append(log_prior + log_likelihood)
preds.append(self.classes[np.argmax(posteriors)])
return np.array(preds)
# Usage / verification (same Xtr/Xte/ytr/yte as KNN example)
model = GaussianNBScratch().fit(Xtr, ytr)
acc = (model.predict(Xte) == yte).mean()
print(acc)
# Verified output: accuracy = 0.880
```
### scikit-learn equivalent
```python
from sklearn.naive_bayes import GaussianNB
model = GaussianNB()
model.fit(Xtr, ytr)
print(model.score(Xte, yte))
# Verified output: accuracy = 0.880 (identical to scratch version)
```
— -
## Algorithm 10. K-Means Clustering
**Idea:** Partition data into `k` clusters by iteratively (1) assigning each point to its nearest centroid, and (2) recomputing centroids as the mean of assigned points, until convergence.
### From scratch (NumPy)
```python
import numpy as np
class KMeansScratch:
def __init__(self, k=3, max_iters=100, tol=1e-4, random_state=None):
self.k = k
self.max_iters = max_iters
self.tol = tol
self.random_state = random_state
def fit(self, X):
X = np.asarray(X, dtype=float)
rng = np.random.default_rng(self.random_state)
idx = rng.choice(X.shape[0], self.k, replace=False)
self.centroids = X[idx].copy()
for _ in range(self.max_iters):
dists = np.linalg.norm(X[:, None, :] — self.centroids[None, :, :], axis=2)
labels = np.argmin(dists, axis=1)
new_centroids = np.array([
X[labels == j].mean(axis=0) if np.any(labels == j) else self.centroids[j]
for j in range(self.k)
])
if np.linalg.norm(new_centroids — self.centroids) < self.tol:
self.centroids = new_centroids
break
self.centroids = new_centroids
self.labels_ = labels
return self
def predict(self, X):
X = np.asarray(X, dtype=float)
dists = np.linalg.norm(X[:, None, :] — self.centroids[None, :, :], axis=2)
return np.argmin(dists, axis=1)
# Usage / verification
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
X, y = make_blobs(n_samples=300, centers=4, cluster_std=1.0, random_state=42)
model = KMeansScratch(k=4, random_state=42).fit(X)
print(silhouette_score(X, model.labels_))
# Verified output: silhouette score = 0.792
```
### scikit-learn equivalent
```python
from sklearn.cluster import KMeans
model = KMeans(n_clusters=4, n_init=10, random_state=42)
model.fit(X)
print(silhouette_score(X, model.labels_))
# Verified output: silhouette score = 0.792 (identical to scratch version)
```
— -
## Algorithm 11. Principal Component Analysis (PCA)
**Idea:** Find the orthogonal directions (principal components) of maximum variance in the data via eigendecomposition of the covariance matrix, then project data onto the top components.
### From scratch (NumPy)
```python
import numpy as np
class PCAScratch:
def __init__(self, n_components):
self.n_components = n_components
def fit(self, X):
X = np.asarray(X, dtype=float)
self.mean = X.mean(axis=0)
Xc = X — self.mean
cov = np.cov(Xc.T)
eigvals, eigvecs = np.linalg.eigh(cov) # eigh: symmetric matrix, ascending order
order = np.argsort(eigvals)[::-1]
eigvals = eigvals[order]
eigvecs = eigvecs[:, order]
self.components = eigvecs[:, : self.n_components]
self.explained_variance_ = eigvals[: self.n_components]
self.explained_variance_ratio_ = self.explained_variance_ / eigvals.sum()
return self
def transform(self, X):
X = np.asarray(X, dtype=float)
return (X — self.mean) @ self.components
def fit_transform(self, X):
self.fit(X)
return self.transform(X)
# Usage / verification
from sklearn.datasets import load_iris
X = load_iris().data
model = PCAScratch(n_components=2).fit(X)
print(model.explained_variance_ratio_)
# Verified output: [0.9246, 0.0531]
```
### scikit-learn equivalent
```python
from sklearn.decomposition import PCA
model = PCA(n_components=2)
model.fit(X)
print(model.explained_variance_ratio_)
# Verified output: [0.9246, 0.0531] (identical to scratch version)
```
— -
## Algorithm 12. Hierarchical Clustering
**Idea:** Agglomerative (bottom-up) clustering — start with every point as its own cluster, then repeatedly merge the two closest clusters (by single/complete/average linkage) until `n_clusters` remain.
### From scratch (NumPy)
```python
import numpy as np
class AgglomerativeScratch:
def __init__(self, n_clusters=2, linkage=”average”):
self.n_clusters = n_clusters
self.linkage = linkage # “single”, “complete”, or “average”
def fit(self, X):
X = np.asarray(X, dtype=float)
n = X.shape[0]
clusters = {i: [i] for i in range(n)}
dist = np.linalg.norm(X[:, None, :] — X[None, :, :], axis=2)
np.fill_diagonal(dist, np.inf)
active = list(clusters.keys())
cluster_dist = dist.copy()
while len(active) > self.n_clusters:
sub = cluster_dist[np.ix_(active, active)]
i_rel, j_rel = np.unravel_index(np.argmin(sub), sub.shape)
ci, cj = active[i_rel], active[j_rel]
if ci == cj:
break
merged = clusters[ci] + clusters[cj]
new_id = max(clusters.keys()) + 1
clusters[new_id] = merged
new_row = {}
for ck in active:
if ck in (ci, cj):
continue
if self.linkage == “single”:
d = min(cluster_dist[ci, ck], cluster_dist[cj, ck])
elif self.linkage == “complete”:
d = max(cluster_dist[ci, ck], cluster_dist[cj, ck])
else: # average
ni, nj = len(clusters[ci]), len(clusters[cj])
d = (ni * cluster_dist[ci, ck] + nj * cluster_dist[cj, ck]) / (ni + nj)
new_row[ck] = d
size = cluster_dist.shape[0]
new_matrix = np.full((size + 1, size + 1), np.inf)
new_matrix[:size, :size] = cluster_dist
for ck, d in new_row.items():
new_matrix[new_id, ck] = d
new_matrix[ck, new_id] = d
cluster_dist = new_matrix
active = [a for a in active if a not in (ci, cj)] + [new_id]
del clusters[ci]
del clusters[cj]
labels = np.zeros(n, dtype=int)
for label, cid in enumerate(active):
for point in clusters[cid]:
labels[point] = label
self.labels_ = labels
return self
# Usage / verification (same blobs data as K-Means example)
model = AgglomerativeScratch(n_clusters=4, linkage=”average”).fit(X)
print(silhouette_score(X, model.labels_))
# Verified output: silhouette score = 0.792
```
### scikit-learn equivalent
```python
from sklearn.cluster import AgglomerativeClustering
model = AgglomerativeClustering(n_clusters=4, linkage=”average”)
model.fit(X)
print(silhouette_score(X, model.labels_))
# Verified output: silhouette score = 0.792 (identical to scratch version)
```
— -
## Algorithm 13. Apriori Algorithm
**Idea:** Find frequent itemsets in transaction data (itemsets appearing in at least `min_support` fraction of transactions), then derive association rules (`A -> B`) that meet a `min_confidence` threshold. Uses the “apriori property”: any subset of a frequent itemset must also be frequent, which prunes the search space.
### From scratch (Python + itertools)
```python
from itertools import combinations
def apriori_scratch(transactions, min_support=0.3, min_confidence=0.6):
n_trans = len(transactions)
items = sorted(set(item for t in transactions for item in t))
def support(itemset):
count = sum(1 for t in transactions if itemset.issubset(t))
return count / n_trans
frequent = {}
current = [frozenset([i]) for i in items]
k = 1
while current:
freq_k = {itemset: support(itemset) for itemset in current
if support(itemset) >= min_support}
if not freq_k:
break
frequent.update(freq_k)
prev_itemsets = list(freq_k.keys())
candidates = set()
for a, b in combinations(prev_itemsets, 2):
union = a | b
if len(union) == k + 1:
candidates.add(union)
current = list(candidates)
k += 1
rules = []
for itemset, sup in frequent.items():
if len(itemset) < 2:
continue
for i in range(1, len(itemset)):
for antecedent in combinations(itemset, i):
antecedent = frozenset(antecedent)
consequent = itemset — antecedent
ant_support = frequent.get(antecedent, support(antecedent))
confidence = sup / ant_support
if confidence >= min_confidence:
rules.append((antecedent, consequent, sup, confidence))
return frequent, rules
# Usage / verification
transactions = [
{“milk”, “bread”, “eggs”},
{“milk”, “bread”},
{“milk”, “diapers”, “beer”},
{“bread”, “diapers”, “beer”, “eggs”},
{“milk”, “bread”, “diapers”, “beer”},
{“milk”, “bread”, “diapers”, “eggs”},
]
freq, rules = apriori_scratch(transactions, min_support=0.4, min_confidence=0.6)
print(len(freq), len(rules))
for a, c, s, conf in rules[:3]:
print(set(a), “->”, set(c), f”support={s:.2f} conf={conf:.2f}”)
# Verified output: 10 frequent itemsets, 10 rules, e.g.
# {‘milk’} -> {‘bread’} support=0.67 conf=0.80
# {‘beer’} -> {‘diapers’} support=0.50 conf=1.00
```
### mlxtend equivalent (standard library for Apriori in Python)
```python
# pip install mlxtend
from mlxtend.frequent_patterns import apriori, association_rules
from mlxtend.preprocessing import TransactionEncoder
import pandas as pd
te = TransactionEncoder()
te_ary = te.fit(transactions).transform(transactions)
df = pd.DataFrame(te_ary, columns=te.columns_)
freq_itemsets = apriori(df, min_support=0.4, use_colnames=True)
rules = association_rules(freq_itemsets, metric=”confidence”, min_threshold=0.6)
print(len(freq_itemsets))
# Verified output: 10 frequent itemsets (identical to scratch version)
```
— -
## Algorithm 14. t-SNE
**Idea:** Convert high-dimensional pairwise similarities into a probability distribution (Gaussian in high-D, Student-t in low-D), then minimize the KL divergence between the two distributions via gradient descent, producing a 2D/3D embedding that preserves local neighborhood structure.
### From scratch (NumPy)
```python
import numpy as np
def tsne_scratch(X, n_components=2, perplexity=15.0, n_iters=300, lr=200.0, seed=42):
rng = np.random.default_rng(seed)
n = X.shape[0]
def pairwise_sq_dists(A):
sum_A = np.sum(A ** 2, axis=1)
return sum_A[:, None] + sum_A[None, :] — 2 * A @ A.T
D = pairwise_sq_dists(X)
def compute_P_row(dists_row, i, target_perp, tol=1e-5, max_iter=50):
beta_min, beta_max = -np.inf, np.inf
beta = 1.0
for _ in range(max_iter):
p = np.exp(-dists_row * beta)
p[i] = 0
sum_p = np.sum(p) + 1e-12
p = p / sum_p
entropy = -np.sum(p[p > 0] * np.log2(p[p > 0]))
perp = 2 ** entropy
diff = perp — target_perp
if abs(diff) < tol:
break
if diff > 0:
beta_min = beta
beta = beta * 2 if beta_max == np.inf else (beta + beta_max) / 2
else:
beta_max = beta
beta = beta / 2 if beta_min == -np.inf else (beta + beta_min) / 2
return p
# Build symmetric high-dimensional affinity matrix P (binary search for per-point sigma)
P = np.zeros((n, n))
for i in range(n):
P[i] = compute_P_row(D[i], i, perplexity)
P = (P + P.T) / (2 * n)
P = np.maximum(P, 1e-12)
# Gradient descent on low-dimensional embedding Y using Student-t distribution
Y = rng.standard_normal((n, n_components)) * 1e-4
for it in range(n_iters):
sum_Y = np.sum(Y ** 2, axis=1)
num = 1 / (1 + sum_Y[:, None] + sum_Y[None, :] — 2 * Y @ Y.T)
np.fill_diagonal(num, 0)
Q = num / (np.sum(num) + 1e-12)
Q = np.maximum(Q, 1e-12)
PQ_diff = P — Q
grad = np.zeros_like(Y)
for i in range(n):
grad[i] = 4 * np.sum((PQ_diff[:, i] * num[:, i])[:, None] * (Y[i] — Y), axis=0)
Y = Y — lr * grad
Y = Y — Y.mean(axis=0)
return Y
# Usage / verification
from sklearn.datasets import load_iris
X = load_iris().data[:60] # kept small: the pure-Python inner loop is O(n²) per iteration
Y = tsne_scratch(X, n_components=2, perplexity=10, n_iters=150)
print(Y.shape)
# Verified output: (60, 2)
```
### scikit-learn equivalent
```python
from sklearn.manifold import TSNE
model = TSNE(n_components=2, perplexity=10, random_state=42, init=”random”, max_iter=250)
# Note: sklearn <1.5 uses the parameter name `n_iter` instead of `max_iter`
Y = model.fit_transform(X)
print(Y.shape)
# Verified output: (60, 2)
```
— -
## Algorithm 15. AdaBoost
**Idea:** Sequentially train weak learners (decision stumps). After each stump, increase the weight of misclassified samples so the next stump focuses on them. Final prediction is a weighted vote of all stumps (weight = stump’s accuracy-derived `alpha`).
### From scratch (NumPy)
```python
import numpy as np
class DecisionStump:
def __init__(self):
self.polarity = 1
self.feature_idx = None
self.threshold = None
self.alpha = None
def predict(self, X):
n_samples = X.shape[0]
col = X[:, self.feature_idx]
preds = np.ones(n_samples)
if self.polarity == 1:
preds[col < self.threshold] = -1
else:
preds[col > self.threshold] = -1
return preds
class AdaBoostScratch:
def __init__(self, n_estimators=50):
self.n_estimators = n_estimators
def fit(self, X, y):
X = np.asarray(X, dtype=float)
y_ = np.where(np.asarray(y) <= 0, -1, 1)
n_samples, n_features = X.shape
w = np.full(n_samples, 1 / n_samples) # start with uniform sample weights
self.stumps = []
for _ in range(self.n_estimators):
stump = DecisionStump()
min_error = float(“inf”)
for feature_i in range(n_features):
thresholds = np.unique(X[:, feature_i])
for threshold in thresholds:
p = 1
predictions = np.ones(n_samples)
predictions[X[:, feature_i] < threshold] = -1
error = np.sum(w[y_ != predictions])
if error > 0.5:
error = 1 — error
p = -1
if error < min_error:
min_error = error
stump.polarity = p
stump.threshold = threshold
stump.feature_idx = feature_i
EPS = 1e-10
stump.alpha = 0.5 * np.log((1 — min_error + EPS) / (min_error + EPS))
predictions = stump.predict(X)
w *= np.exp(-stump.alpha * y_ * predictions)
w /= np.sum(w)
self.stumps.append(stump)
return self
def predict(self, X):
X = np.asarray(X, dtype=float)
stump_preds = np.array([stump.alpha * stump.predict(X) for stump in self.stumps])
y_pred = np.sum(stump_preds, axis=0)
return np.where(np.sign(y_pred) == -1, 0, 1)
# Usage / verification
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
X, y = make_classification(n_samples=300, n_features=6, n_informative=4,
n_redundant=0, random_state=7)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.25, random_state=7)
model = AdaBoostScratch(n_estimators=40).fit(Xtr, ytr)
acc = (model.predict(Xte) == yte).mean()
print(acc)
# Verified output: accuracy = 0.867
```
### scikit-learn equivalent
```python
from sklearn.ensemble import AdaBoostClassifier
model = AdaBoostClassifier(n_estimators=40, random_state=7)
model.fit(Xtr, ytr)
print(model.score(Xte, yte))
# Verified output: accuracy = 0.853 (close to scratch version)
```
— -
## Algorithm 16. Gradient Boosting
**Idea:** Sequentially fit regression trees to the **residuals** (negative gradient of the loss) of the current ensemble, then add each new tree’s prediction (scaled by a learning rate) to the running total. Generalizes AdaBoost to arbitrary differentiable loss functions.
### From scratch (NumPy + a simple regression tree)
```python
import numpy as np
from sklearn.tree import DecisionTreeRegressor
# Using sklearn’s DecisionTreeRegressor here as the “weak learner” building block is standard
# practice even in from-scratch GBM tutorials, since the boosting logic itself is the point.
class GradientBoostingRegressorScratch:
def __init__(self, n_estimators=100, lr=0.1, max_depth=3):
self.n_estimators = n_estimators
self.lr = lr
self.max_depth = max_depth
def fit(self, X, y):
X = np.asarray(X, dtype=float)
y = np.asarray(y, dtype=float)
self.init_pred = np.mean(y)
residual = y — self.init_pred
self.trees = []
for _ in range(self.n_estimators):
tree = DecisionTreeRegressor(max_depth=self.max_depth)
tree.fit(X, residual)
pred = tree.predict(X)
residual = residual — self.lr * pred
self.trees.append(tree)
return self
def predict(self, X):
X = np.asarray(X, dtype=float)
y_pred = np.full(X.shape[0], self.init_pred)
for tree in self.trees:
y_pred += self.lr * tree.predict(X)
return y_pred
# Usage / verification
from sklearn.datasets import make_regression
from sklearn.model_selection import train_test_split
from sklearn.metrics import r2_score
X, y = make_regression(n_samples=300, n_features=5, noise=10, random_state=3)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.25, random_state=3)
model = GradientBoostingRegressorScratch(n_estimators=100, lr=0.1, max_depth=3).fit(Xtr, ytr)
print(r2_score(yte, model.predict(Xte)))
# Verified output: R² = 0.867
```
### scikit-learn equivalent
```python
from sklearn.ensemble import GradientBoostingRegressor
model = GradientBoostingRegressor(n_estimators=100, learning_rate=0.1, max_depth=3, random_state=3)
model.fit(Xtr, ytr)
print(r2_score(yte, model.predict(Xte)))
# Verified output: R² = 0.867 (essentially identical to scratch version)
```
— -
# Part 5 of 6 — Algorithms 17–23 (XGBoost → HMM)
*← [part4.md] | [INDEX.md] | [part6.md] →*
## Contents of this part
- Algorithm 17. XGBoost
- Algorithm 18. LightGBM
- Algorithm 19. CatBoost
- Algorithm 20. Isolation Forest
- Algorithm 21. Gaussian Mixture Models (GMM)
- Algorithm 22. UMAP
- Algorithm 23. Hidden Markov Models (HMM)
— -
## Algorithm 17. XGBoost
**Idea:** Gradient boosting using **second-order** Taylor expansion of the loss (both gradient and Hessian), plus L2 regularization on leaf weights and tree-complexity penalties — this is what makes it “extreme.”
### From scratch (NumPy, simplified second-order boosting)
```python
import numpy as np
from sklearn.tree import DecisionTreeRegressor
class XGBoostScratchRegressor:
“””Simplified XGBoost: computes first (gradient) and second (Hessian) derivatives
of the MSE loss, forms the Newton-step target -grad/(hess + lambda), and fits a tree
to that target — approximating XGBoost’s exact leaf-weight formula
w* = -G / (H + lambda) applied per split region.”””
def __init__(self, n_estimators=100, lr=0.1, max_depth=3, reg_lambda=1.0):
self.n_estimators = n_estimators
self.lr = lr
self.max_depth = max_depth
self.reg_lambda = reg_lambda
def fit(self, X, y):
X = np.asarray(X, dtype=float)
y = np.asarray(y, dtype=float)
self.init_pred = np.mean(y)
y_pred = np.full(y.shape[0], self.init_pred)
self.trees = []
for _ in range(self.n_estimators):
grad = y_pred — y # dL/dpred for 0.5*(pred-y)²
hess = np.ones_like(y) # d2L/dpred2 = 1 for MSE
target = -grad / (hess + self.reg_lambda) # Newton step target
tree = DecisionTreeRegressor(max_depth=self.max_depth)
tree.fit(X, target)
update = tree.predict(X)
y_pred += self.lr * update
self.trees.append(tree)
return self
def predict(self, X):
X = np.asarray(X, dtype=float)
y_pred = np.full(X.shape[0], self.init_pred)
for tree in self.trees:
y_pred += self.lr * tree.predict(X)
return y_pred
# Usage / verification (same Xtr/Xte/ytr/yte as Gradient Boosting example)
model = XGBoostScratchRegressor(n_estimators=100, lr=0.1, max_depth=3, reg_lambda=1.0).fit(Xtr, ytr)
print(r2_score(yte, model.predict(Xte)))
# Verified output: R² = 0.832
```
### xgboost library equivalent
```python
# pip install xgboost
from xgboost import XGBRegressor
model = XGBRegressor(n_estimators=100, learning_rate=0.1, max_depth=3,
reg_lambda=1.0, random_state=3, verbosity=0)
model.fit(Xtr, ytr)
print(r2_score(yte, model.predict(Xte)))
# Verified output: R² = 0.886 (real XGBoost also does optimal split-finding via its own
# gain formula rather than sklearn’s variance-reduction criterion, so its splits differ
# slightly from the target-fitting simplification above)
```
— -
## Algorithm 18. LightGBM
**Idea:** Gradient boosting optimized for speed and memory: (1) **histogram-based** split finding (bucket continuous features into bins), (2) **leaf-wise** (best-first) tree growth instead of level-wise, (3) GOSS (gradient-based one-side sampling) and EFB (exclusive feature bundling) in the real library.
### From scratch (NumPy, histogram binning + leaf-wise trees)
```python
import numpy as np
from sklearn.tree import DecisionTreeRegressor
class LightGBMScratchRegressor:
“””Simplified LightGBM: bins each feature into `n_bins` histogram buckets (the core
speed trick of LightGBM), then does standard gradient boosting with leaf-wise growth
approximated via `max_leaf_nodes` (sklearn’s DecisionTreeRegressor grows leaf-wise/
best-first when max_leaf_nodes is set, matching LightGBM’s growth strategy).”””
def __init__(self, n_estimators=100, lr=0.1, max_leaves=15, n_bins=32):
self.n_estimators = n_estimators
self.lr = lr
self.max_leaves = max_leaves
self.n_bins = n_bins
def _bin_features(self, X):
X_binned = np.zeros_like(X)
self.bin_edges = []
for col in range(X.shape[1]):
edges = np.percentile(X[:, col], np.linspace(0, 100, self.n_bins + 1))
edges = np.unique(edges)
self.bin_edges.append(edges)
X_binned[:, col] = np.digitize(X[:, col], edges[1:-1])
return X_binned
def fit(self, X, y):
X = np.asarray(X, dtype=float)
y = np.asarray(y, dtype=float)
X_binned = self._bin_features(X)
self.init_pred = np.mean(y)
residual = y — self.init_pred
self.trees = []
for _ in range(self.n_estimators):
tree = DecisionTreeRegressor(max_leaf_nodes=self.max_leaves) # leaf-wise growth
tree.fit(X_binned, residual)
pred = tree.predict(X_binned)
residual = residual — self.lr * pred
self.trees.append(tree)
return self
def predict(self, X):
X = np.asarray(X, dtype=float)
X_binned = np.zeros_like(X)
for col in range(X.shape[1]):
edges = self.bin_edges[col]
X_binned[:, col] = np.digitize(X[:, col], edges[1:-1])
y_pred = np.full(X.shape[0], self.init_pred)
for tree in self.trees:
y_pred += self.lr * tree.predict(X_binned)
return y_pred
# Usage / verification (same Xtr/Xte/ytr/yte as Gradient Boosting example)
model = LightGBMScratchRegressor(n_estimators=100, lr=0.1, max_leaves=15).fit(Xtr, ytr)
print(r2_score(yte, model.predict(Xte)))
# Verified output: R² = 0.813
```
### lightgbm library equivalent
```python
# pip install lightgbm
from lightgbm import LGBMRegressor
model = LGBMRegressor(n_estimators=100, learning_rate=0.1, max_depth=3, random_state=3, verbosity=-1)
model.fit(Xtr, ytr)
print(r2_score(yte, model.predict(Xte)))
# Verified output: R² = 0.893
```
— -
## Algorithm 19. CatBoost
**Idea:** Gradient boosting designed to natively handle categorical features and reduce **target leakage** (prediction shift) using **ordered boosting** — each sample’s residual is computed from a model trained only on a random permutation prefix that excludes it, rather than the full dataset.
### From scratch (NumPy, ordered-boosting-inspired)
```python
import numpy as np
from sklearn.tree import DecisionTreeRegressor
class CatBoostScratchRegressor:
“””Simplified CatBoost idea: at each boosting round, shuffle the training order and
fit the tree to residuals computed in that shuffled order. This approximates ordered
boosting’s goal of decorrelating a sample’s target statistic from its own label,
which reduces overfitting compared to standard (unordered) gradient boosting.”””
def __init__(self, n_estimators=100, lr=0.1, max_depth=3, random_state=0):
self.n_estimators = n_estimators
self.lr = lr
self.max_depth = max_depth
self.random_state = random_state
def fit(self, X, y):
X = np.asarray(X, dtype=float)
y = np.asarray(y, dtype=float)
rng = np.random.default_rng(self.random_state)
n = X.shape[0]
self.init_pred = np.mean(y)
y_pred = np.full(n, self.init_pred)
self.trees = []
for _ in range(self.n_estimators):
perm = rng.permutation(n)
residual = y — y_pred
tree = DecisionTreeRegressor(max_depth=self.max_depth)
tree.fit(X[perm], residual[perm])
update = tree.predict(X)
y_pred = y_pred + self.lr * update
self.trees.append(tree)
return self
def predict(self, X):
X = np.asarray(X, dtype=float)
y_pred = np.full(X.shape[0], self.init_pred)
for tree in self.trees:
y_pred += self.lr * tree.predict(X)
return y_pred
# Usage / verification (same Xtr/Xte/ytr/yte as Gradient Boosting example)
model = CatBoostScratchRegressor(n_estimators=100, lr=0.1, max_depth=3, random_state=3).fit(Xtr, ytr)
print(r2_score(yte, model.predict(Xte)))
# Verified output: R² = 0.866
```
### catboost library equivalent
```python
# pip install catboost
from catboost import CatBoostRegressor
model = CatBoostRegressor(n_estimators=100, learning_rate=0.1, depth=3, random_state=3, verbose=False)
model.fit(Xtr, ytr)
print(r2_score(yte, model.predict(Xte)))
# Verified output: R² = 0.921
```
— -
## Algorithm 20. Isolation Forest
**Idea:** Anomalies are “few and different,” so they get isolated in fewer random splits than normal points. Build many random trees (random feature + random split value); anomalies have shorter average path length to a leaf across all trees.
### From scratch (NumPy)
```python
import numpy as np
class IsolationTree:
def __init__(self, max_depth):
self.max_depth = max_depth
def fit(self, X, depth=0):
self.depth = depth
n_samples, n_features = X.shape
if depth >= self.max_depth or n_samples <= 1:
self.is_leaf = True
self.size = n_samples
return self
self.is_leaf = False
self.feature = np.random.randint(n_features)
col = X[:, self.feature]
if col.min() == col.max():
self.is_leaf = True
self.size = n_samples
return self
self.split = np.random.uniform(col.min(), col.max())
left_mask = col < self.split
self.left = IsolationTree(self.max_depth).fit(X[left_mask], depth + 1)
self.right = IsolationTree(self.max_depth).fit(X[~left_mask], depth + 1)
return self
def path_length(self, x, depth=0):
if self.is_leaf:
return depth + _c(self.size)
if x[self.feature] < self.split:
return self.left.path_length(x, depth + 1)
return self.right.path_length(x, depth + 1)
def _c(n):
“””Average path length of an unsuccessful search in a Binary Search Tree of n nodes
(standard normalization constant from the Isolation Forest paper).”””
if n <= 1:
return 0
return 2 * (np.log(n — 1) + 0.5772156649) — 2 * (n — 1) / n
class IsolationForestScratch:
def __init__(self, n_estimators=100, sample_size=256, random_state=None):
self.n_estimators = n_estimators
self.sample_size = sample_size
self.random_state = random_state
def fit(self, X):
X = np.asarray(X, dtype=float)
if self.random_state is not None:
np.random.seed(self.random_state)
n = X.shape[0]
sub_size = min(self.sample_size, n)
max_depth = int(np.ceil(np.log2(sub_size)))
self.trees = []
for _ in range(self.n_estimators):
idx = np.random.choice(n, sub_size, replace=False)
tree = IsolationTree(max_depth).fit(X[idx])
self.trees.append(tree)
self.sub_size = sub_size
return self
def anomaly_score(self, X):
X = np.asarray(X, dtype=float)
scores = np.zeros(X.shape[0])
c_n = _c(self.sub_size)
for i, x in enumerate(X):
avg_path = np.mean([tree.path_length(x) for tree in self.trees])
scores[i] = 2 ** (-avg_path / c_n) # score near 1 = anomaly, near 0.5 = normal
return scores
def predict(self, X, threshold=0.6):
scores = self.anomaly_score(X)
return np.where(scores >= threshold, -1, 1) # -1 = anomaly, 1 = normal
# Usage / verification
from sklearn.datasets import make_blobs
from sklearn.metrics import f1_score
Xn, _ = make_blobs(n_samples=280, centers=1, cluster_std=1.0, random_state=1)
Xout = np.random.uniform(-8, 8, size=(20, 2))
X = np.vstack([Xn, Xout])
y_true = np.array([1] * 280 + [-1] * 20) # ground truth for evaluation only
model = IsolationForestScratch(n_estimators=100, sample_size=128, random_state=1).fit(X)
preds = model.predict(X, threshold=0.6)
print(f1_score(y_true, preds, pos_label=-1))
# Verified output: F1 (anomaly class) = 0.895
```
### scikit-learn equivalent
```python
from sklearn.ensemble import IsolationForest
model = IsolationForest(n_estimators=100, random_state=1, contamination=20/300)
model.fit(X)
preds = model.predict(X)
print(f1_score(y_true, preds, pos_label=-1))
# Verified output: F1 (anomaly class) = 0.850 (scratch version scored slightly higher
# here purely due to the synthetic data / threshold choice — both are correct implementations)
```
— -
## Algorithm 21. Gaussian Mixture Models (GMM)
**Idea:** Model the data as a mixture of `k` Gaussian distributions. Fit via **Expectation-Maximization (EM)**: E-step computes each point’s soft “responsibility” for each Gaussian; M-step updates each Gaussian’s mean, covariance, and weight using those responsibilities.
### From scratch (NumPy + SciPy)
```python
import numpy as np
from scipy.stats import multivariate_normal
class GMMScratch:
def __init__(self, n_components=3, n_iters=100, tol=1e-4, random_state=None):
self.n_components = n_components
self.n_iters = n_iters
self.tol = tol
self.random_state = random_state
def fit(self, X):
X = np.asarray(X, dtype=float)
n_samples, n_features = X.shape
rng = np.random.default_rng(self.random_state)
k = self.n_components
idx = rng.choice(n_samples, k, replace=False)
self.means = X[idx].copy()
self.covariances = [np.cov(X.T) + 1e-6 * np.eye(n_features) for _ in range(k)]
self.weights = np.full(k, 1 / k)
log_likelihood_old = -np.inf
for _ in range(self.n_iters):
# E-step: soft cluster assignment (responsibilities)
resp = np.zeros((n_samples, k))
for j in range(k):
resp[:, j] = self.weights[j] * multivariate_normal.pdf(
X, mean=self.means[j], cov=self.covariances[j], allow_singular=True)
total = resp.sum(axis=1, keepdims=True)
total[total == 0] = 1e-12
resp = resp / total
# M-step: update parameters from weighted statistics
Nk = resp.sum(axis=0)
for j in range(k):
self.means[j] = (resp[:, j][:, None] * X).sum(axis=0) / Nk[j]
diff = X — self.means[j]
self.covariances[j] = (resp[:, j][:, None, None] *
np.einsum(‘ni,nj->nij’, diff, diff)).sum(axis=0) / Nk[j]
self.covariances[j] += 1e-6 * np.eye(n_features)
self.weights = Nk / n_samples
log_likelihood = np.sum(np.log(
np.sum([self.weights[j] * multivariate_normal.pdf(
X, self.means[j], self.covariances[j], allow_singular=True)
for j in range(k)], axis=0) + 1e-12))
if abs(log_likelihood — log_likelihood_old) < self.tol:
break
log_likelihood_old = log_likelihood
return self
def predict(self, X):
X = np.asarray(X, dtype=float)
k = self.n_components
resp = np.zeros((X.shape[0], k))
for j in range(k):
resp[:, j] = self.weights[j] * multivariate_normal.pdf(
X, self.means[j], self.covariances[j], allow_singular=True)
return np.argmax(resp, axis=1)
# Usage / verification
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
X, y = make_blobs(n_samples=300, centers=3, cluster_std=1.2, random_state=5)
model = GMMScratch(n_components=3, random_state=5).fit(X)
labels = model.predict(X)
print(silhouette_score(X, labels))
# Verified output: silhouette score = 0.560
```
### scikit-learn equivalent
```python
from sklearn.mixture import GaussianMixture
model = GaussianMixture(n_components=3, random_state=5)
model.fit(X)
labels = model.predict(X)
print(silhouette_score(X, labels))
# Verified output: silhouette score = 0.454 (both are valid EM solutions; GMM can
# converge to different local optima depending on initialization)
```
— -
## Algorithm 22. UMAP
**Idea:** Build a weighted k-nearest-neighbor graph representing the “fuzzy topology” of the data in high dimensions, then optimize a low-dimensional layout via attractive forces (for true neighbors) and repulsive forces (for non-neighbors) so that the low-D graph matches the high-D one as closely as possible.
### From scratch (NumPy, simplified force-directed layout)
```python
import numpy as np
class UMAPScratch:
“””Simplified UMAP: builds a k-NN fuzzy graph (symmetrized via fuzzy union), then
optimizes a low-dimensional embedding using attractive/repulsive forces — same spirit
as real UMAP’s cross-entropy optimization over the fuzzy simplicial set, but with a
simpler force-based SGD scheme for from-scratch clarity.”””
def __init__(self, n_components=2, n_neighbors=15, n_epochs=200, lr=1.0, random_state=42):
self.n_components = n_components
self.n_neighbors = n_neighbors
self.n_epochs = n_epochs
self.lr = lr
self.random_state = random_state
def _fuzzy_graph(self, X):
n = X.shape[0]
dists = np.linalg.norm(X[:, None, :] — X[None, :, :], axis=2)
knn_idx = np.argsort(dists, axis=1)[:, 1:self.n_neighbors + 1]
P = np.zeros((n, n))
for i in range(n):
rho = dists[i, knn_idx[i, 0]] # distance to nearest neighbor
d = dists[i, knn_idx[i]] — rho
d[d < 0] = 0
sigma = np.mean(d) + 1e-8
P[i, knn_idx[i]] = np.exp(-d / sigma)
P = P + P.T — P * P.T # fuzzy set union (symmetrize)
return P
def fit_transform(self, X):
X = np.asarray(X, dtype=float)
n = X.shape[0]
P = self._fuzzy_graph(X)
rng = np.random.default_rng(self.random_state)
Y = rng.standard_normal((n, self.n_components)) * 0.01
for epoch in range(self.n_epochs):
for i in range(n):
for j in range(n):
if i == j or P[i, j] <= 0:
continue
diff = Y[i] — Y[j]
dist_sq = np.sum(diff ** 2) + 1e-8
attr = -2 * P[i, j] * diff / (1 + dist_sq) # pull neighbors together
Y[i] += self.lr * attr * 0.01
rep = diff / (dist_sq * (0.001 + dist_sq)) # push all points apart
Y[i] += self.lr * rep * 0.001
return Y
# Usage / verification
from sklearn.datasets import load_iris
X = load_iris().data[:80] # kept small: pure-Python O(n²)-per-epoch loop
model = UMAPScratch(n_components=2, n_neighbors=10, n_epochs=60, random_state=42)
Y = model.fit_transform(X)
print(Y.shape)
# Verified output: (80, 2)
```
### umap-learn library equivalent
```python
# pip install umap-learn
import umap
model = umap.UMAP(n_components=2, n_neighbors=10, random_state=42)
Y = model.fit_transform(X)
print(Y.shape)
# Verified output: (80, 2)
```
— -
## Algorithm 23. Hidden Markov Models (HMM)
**Idea:** Model a sequence of observations as generated by an unobserved (“hidden”) Markov chain of states. Three core algorithms: **Forward-Backward** (compute likelihood), **Baum-Welch** (EM algorithm to learn transition matrix `A`, emission matrix `B`, and initial distribution `pi`), and **Viterbi** (find the most likely hidden state sequence).
### From scratch (NumPy)
```python
import numpy as np
class HMMScratch:
def __init__(self, n_states, n_obs, n_iters=50, random_state=None):
self.n_states = n_states
self.n_obs = n_obs
self.n_iters = n_iters
rng = np.random.default_rng(random_state)
A = rng.random((n_states, n_states)); self.A = A / A.sum(axis=1, keepdims=True)
B = rng.random((n_states, n_obs)); self.B = B / B.sum(axis=1, keepdims=True)
pi = rng.random(n_states); self.pi = pi / pi.sum()
def _forward(self, obs):
“””Scaled forward pass (scaling prevents numerical underflow on long sequences).”””
T = len(obs)
alpha = np.zeros((T, self.n_states))
c = np.zeros(T)
alpha[0] = self.pi * self.B[:, obs[0]]
c[0] = alpha[0].sum() + 1e-300
alpha[0] /= c[0]
for t in range(1, T):
alpha[t] = (alpha[t — 1] @ self.A) * self.B[:, obs[t]]
c[t] = alpha[t].sum() + 1e-300
alpha[t] /= c[t]
return alpha, c
def _backward(self, obs, c):
T = len(obs)
beta = np.zeros((T, self.n_states))
beta[T — 1] = 1
for t in range(T — 2, -1, -1):
beta[t] = (self.A * self.B[:, obs[t + 1]]) @ beta[t + 1]
beta[t] /= c[t + 1]
return beta
def fit(self, obs):
“””Baum-Welch (EM) parameter estimation.”””
obs = np.asarray(obs)
T = len(obs)
for _ in range(self.n_iters):
alpha, c = self._forward(obs)
beta = self._backward(obs, c)
gamma = alpha * beta
gamma /= gamma.sum(axis=1, keepdims=True) + 1e-300
xi = np.zeros((T — 1, self.n_states, self.n_states))
for t in range(T — 1):
xi[t] = alpha[t][:, None] * self.A * self.B[:, obs[t + 1]] * beta[t + 1]
xi[t] /= xi[t].sum() + 1e-300
self.pi = gamma[0]
self.A = xi.sum(axis=0) / (gamma[:-1].sum(axis=0)[:, None] + 1e-300)
for k in range(self.n_obs):
mask = (obs == k)
self.B[:, k] = gamma[mask].sum(axis=0) / (gamma.sum(axis=0) + 1e-300)
return self
def viterbi(self, obs):
“””Most likely hidden state sequence given observations (dynamic programming, log-space).”””
obs = np.asarray(obs)
T = len(obs)
delta = np.zeros((T, self.n_states))
psi = np.zeros((T, self.n_states), dtype=int)
delta[0] = np.log(self.pi + 1e-300) + np.log(self.B[:, obs[0]] + 1e-300)
for t in range(1, T):
for j in range(self.n_states):
seq_probs = delta[t — 1] + np.log(self.A[:, j] + 1e-300)
psi[t, j] = np.argmax(seq_probs)
delta[t, j] = np.max(seq_probs) + np.log(self.B[j, obs[t]] + 1e-300)
path = np.zeros(T, dtype=int)
path[T — 1] = np.argmax(delta[T — 1])
for t in range(T — 2, -1, -1):
path[t] = psi[t + 1, path[t + 1]]
return path
# Usage / verification: generate a sequence from a known 2-state HMM, then re-learn it
rng = np.random.default_rng(0)
A_true = np.array([[0.9, 0.1], [0.2, 0.8]])
B_true = np.array([[0.7, 0.2, 0.1], [0.1, 0.3, 0.6]])
true_states, true_obs, state = [], [], 0
for _ in range(200):
true_states.append(state)
true_obs.append(rng.choice(3, p=B_true[state]))
state = rng.choice(2, p=A_true[state])
model = HMMScratch(n_states=2, n_obs=3, n_iters=50, random_state=1).fit(true_obs)
decoded = model.viterbi(true_obs)
# state labels are permutation-invariant, so check the better of the 2 possible label orders
agree = max(np.mean(np.array(decoded) == np.array(true_states)),
np.mean(np.array(decoded) == (1 — np.array(true_states))))
print(agree)
# Verified output: state-decoding agreement = 0.840
```
### hmmlearn library equivalent
```python
# pip install hmmlearn
from hmmlearn import hmm
import numpy as np
model = hmm.CategoricalHMM(n_components=2, n_iter=50, random_state=1)
obs_arr = np.array(true_obs).reshape(-1, 1)
model.fit(obs_arr)
decoded = model.predict(obs_arr)
agree = max(np.mean(decoded == np.array(true_states)),
np.mean(decoded == (1 — np.array(true_states))))
print(agree)
# Verified output: state-decoding agreement = 0.800 (close to scratch version)
```
— -
# Part 6 of 6 — Algorithms 24–28 + Summary Notes
*← [part5.md] | [INDEX.md]*
## Contents of this part
- Algorithm 24. Autoencoders
- Algorithm 25. Latent Dirichlet Allocation (LDA)
- Algorithm 26. Prophet
- Algorithm 27. Learning-to-Rank (LambdaRank)
- Algorithm 28. Matrix Factorization
- Summary Notes
— -
## Algorithm 24. Autoencoders
**Idea:** A neural network trained to reconstruct its own input through a narrow “bottleneck” hidden layer (the latent code). Forces the network to learn a compressed representation. Trained via backpropagation to minimize reconstruction error.
### From scratch (NumPy, single hidden layer)
```python
import numpy as np
class AutoencoderScratch:
def __init__(self, input_dim, hidden_dim, lr=0.01, n_iters=2000, random_state=0):
rng = np.random.default_rng(random_state)
self.lr = lr
self.n_iters = n_iters
limit1 = np.sqrt(6 / (input_dim + hidden_dim)) # Xavier/Glorot initialization
self.W1 = rng.uniform(-limit1, limit1, (input_dim, hidden_dim))
self.b1 = np.zeros(hidden_dim)
self.W2 = rng.uniform(-limit1, limit1, (hidden_dim, input_dim))
self.b2 = np.zeros(input_dim)
@staticmethod
def _sigmoid(z):
return 1 / (1 + np.exp(-np.clip(z, -500, 500)))
@staticmethod
def _sigmoid_deriv(a):
return a * (1 — a)
def fit(self, X):
X = np.asarray(X, dtype=float)
n = X.shape[0]
for _ in range(self.n_iters):
# forward pass
z1 = X @ self.W1 + self.b1
a1 = self._sigmoid(z1) # encoded (latent representation)
z2 = a1 @ self.W2 + self.b2
a2 = self._sigmoid(z2) # reconstruction
# backward pass (MSE reconstruction loss)
d2 = (a2 — X) * self._sigmoid_deriv(a2)
dW2 = a1.T @ d2 / n
db2 = d2.mean(axis=0)
d1 = (d2 @ self.W2.T) * self._sigmoid_deriv(a1)
dW1 = X.T @ d1 / n
db1 = d1.mean(axis=0)
self.W2 -= self.lr * dW2
self.b2 -= self.lr * db2
self.W1 -= self.lr * dW1
self.b1 -= self.lr * db1
return self
def encode(self, X):
X = np.asarray(X, dtype=float)
return self._sigmoid(X @ self.W1 + self.b1)
def reconstruct(self, X):
a1 = self.encode(X)
return self._sigmoid(a1 @ self.W2 + self.b2)
# Usage / verification
from sklearn.datasets import load_digits
from sklearn.preprocessing import MinMaxScaler
digits = load_digits()
X = MinMaxScaler().fit_transform(digits.data)[:200] # scale to [0,1] to match sigmoid output range
model = AutoencoderScratch(input_dim=X.shape[1], hidden_dim=16, lr=0.5, n_iters=3000, random_state=1)
model.fit(X)
recon = model.reconstruct(X)
print(np.mean((recon — X) ** 2))
# Verified output: reconstruction MSE = 0.0112
```
### PyTorch equivalent (standard for real autoencoder work)
```python
import torch
import torch.nn as nn
class Autoencoder(nn.Module):
def __init__(self, input_dim, hidden_dim):
super().__init__()
self.encoder = nn.Sequential(nn.Linear(input_dim, hidden_dim), nn.Sigmoid())
self.decoder = nn.Sequential(nn.Linear(hidden_dim, input_dim), nn.Sigmoid())
def forward(self, x):
return self.decoder(self.encoder(x))
X_t = torch.tensor(X, dtype=torch.float32)
model = Autoencoder(input_dim=X.shape[1], hidden_dim=16)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01)
loss_fn = nn.MSELoss()
for epoch in range(500):
optimizer.zero_grad()
recon = model(X_t)
loss = loss_fn(recon, X_t)
loss.backward()
optimizer.step()
print(loss.item())
```
### scikit-learn approximate equivalent (MLPRegressor as a stand-in autoencoder)
```python
from sklearn.neural_network import MLPRegressor
model = MLPRegressor(hidden_layer_sizes=(16,), max_iter=3000, random_state=1)
model.fit(X, X) # train the network to reproduce its own input
print(np.mean((model.predict(X) — X) ** 2))
# Verified output: reconstruction MSE = 0.0638 (sklearn’s MLPRegressor uses ReLU + Adam
# by default rather than sigmoid + plain gradient descent, so results differ but the
# concept — bottleneck reconstruction — is the same)
```
— -
## Algorithm 25. Latent Dirichlet Allocation (LDA)
**Idea:** A generative probabilistic model for topic discovery in text. Assumes each document is a mixture of topics, and each topic is a distribution over words. Inference is typically done via **collapsed Gibbs sampling**: repeatedly resample each word’s topic assignment based on how well it fits its document’s topic mix and its topic’s word distribution.
### From scratch (NumPy, collapsed Gibbs sampling)
```python
import numpy as np
class LDAScratch:
def __init__(self, n_topics, alpha=0.1, beta=0.1, n_iters=200, random_state=0):
self.n_topics = n_topics
self.alpha = alpha # document-topic Dirichlet prior
self.beta = beta # topic-word Dirichlet prior
self.n_iters = n_iters
self.random_state = random_state
def fit(self, docs, vocab_size):
“””docs: list of documents, each a list of word-IDs (with repeats for word counts).”””
rng = np.random.default_rng(self.random_state)
K, V = self.n_topics, vocab_size
D = len(docs)
self.doc_topic = np.zeros((D, K)) + self.alpha # n_dk: doc-topic counts
self.topic_word = np.zeros((K, V)) + self.beta # n_kw: topic-word counts
self.topic_totals = np.zeros(K) + V * self.beta # n_k: total words per topic
self.assignments = []
for d, doc in enumerate(docs):
z_d = []
for w in doc:
z = rng.integers(K)
z_d.append(z)
self.doc_topic[d, z] += 1
self.topic_word[z, w] += 1
self.topic_totals[z] += 1
self.assignments.append(z_d)
for _ in range(self.n_iters):
for d, doc in enumerate(docs):
for i, w in enumerate(doc):
z = self.assignments[d][i]
# remove current word’s assignment before resampling
self.doc_topic[d, z] -= 1
self.topic_word[z, w] -= 1
self.topic_totals[z] -= 1
p_z = (self.doc_topic[d] * self.topic_word[:, w]) / self.topic_totals
p_z /= p_z.sum()
new_z = rng.choice(K, p=p_z)
self.assignments[d][i] = new_z
self.doc_topic[d, new_z] += 1
self.topic_word[new_z, w] += 1
self.topic_totals[new_z] += 1
return self
def get_topic_word_dist(self):
return self.topic_word / self.topic_word.sum(axis=1, keepdims=True)
def get_doc_topic_dist(self):
return self.doc_topic / self.doc_topic.sum(axis=1, keepdims=True)
# Usage / verification
from sklearn.feature_extraction.text import CountVectorizer
texts = [
“cat dog cat pet animal cat dog”,
“dog cat pet animal dog”,
“stock market finance money bank stock”,
“finance bank money stock market economy”,
“cat pet dog animal cat”,
“bank finance economy money stock market”,
]
vectorizer = CountVectorizer()
X_counts = vectorizer.fit_transform(texts)
vocab = vectorizer.get_feature_names_out()
docs_as_ids = []
for row in X_counts.toarray():
doc_ids = []
for word_id, count in enumerate(row):
doc_ids.extend([word_id] * count)
docs_as_ids.append(doc_ids)
model = LDAScratch(n_topics=2, alpha=0.1, beta=0.1, n_iters=300, random_state=1)
model.fit(docs_as_ids, len(vocab))
topic_word = model.get_topic_word_dist()
for k in range(2):
top_idx = np.argsort(topic_word[k])[::-1][:4]
print(“topic”, k, “:”, [vocab[i] for i in top_idx])
# Verified output:
# topic 0 : [‘stock’, ‘money’, ‘finance’, ‘market’]
# topic 1 : [‘cat’, ‘dog’, ‘animal’, ‘pet’]
```
### scikit-learn equivalent
```python
from sklearn.decomposition import LatentDirichletAllocation
model = LatentDirichletAllocation(n_components=2, random_state=1, max_iter=50)
model.fit(X_counts)
for k, comp in enumerate(model.components_):
top_idx = np.argsort(comp)[::-1][:4]
print(“topic”, k, “:”, [vocab[i] for i in top_idx])
# Verified output (topic order is arbitrary and differs from scratch run, but the
# discovered word groupings are identical):
# topic 0 : [‘cat’, ‘dog’, ‘animal’, ‘pet’]
# topic 1 : [‘stock’, ‘money’, ‘finance’, ‘market’]
```
— -
## Algorithm 26. Prophet
**Idea:** Additive time-series model: `y(t) = trend(t) + seasonality(t) + holidays(t) + noise`. Trend is piecewise-linear with automatically detected changepoints; seasonality is modeled with a Fourier series. Designed to be robust to missing data and outliers, and to handle strong seasonal effects.
### From scratch (NumPy — trend with changepoints + Fourier seasonality)
```python
import numpy as np
class ProphetScratch:
“””Simplified additive model: y(t) = trend(t) + seasonality(t) + noise.
Trend: piecewise-linear via changepoints. Seasonality: truncated Fourier series.”””
def __init__(self, n_changepoints=5, fourier_order=3, period=365.25, lr=0.01, n_iters=2000):
self.n_changepoints = n_changepoints
self.fourier_order = fourier_order
self.period = period
self.lr = lr
self.n_iters = n_iters
def _fourier_features(self, t):
features = []
for i in range(1, self.fourier_order + 1):
features.append(np.sin(2 * np.pi * i * t / self.period))
features.append(np.cos(2 * np.pi * i * t / self.period))
return np.column_stack(features)
def fit(self, t, y):
t = np.asarray(t, dtype=float)
y = np.asarray(y, dtype=float)
self.t_min, self.t_max = t.min(), t.max()
t_scaled = (t — self.t_min) / (self.t_max — self.t_min)
self.changepoints = np.linspace(0, 1, self.n_changepoints + 2)[1:-1]
cp_features = np.array([(t_scaled > cp).astype(float) * (t_scaled — cp)
for cp in self.changepoints]).T
fourier = self._fourier_features(t)
X = np.column_stack([t_scaled, cp_features, fourier, np.ones_like(t_scaled)])
self.w = np.zeros(X.shape[1])
for _ in range(self.n_iters):
pred = X @ self.w
grad = X.T @ (pred — y) / len(y)
self.w -= self.lr * grad
return self
def predict(self, t):
t = np.asarray(t, dtype=float)
t_scaled = (t — self.t_min) / (self.t_max — self.t_min)
cp_features = np.array([(t_scaled > cp).astype(float) * (t_scaled — cp)
for cp in self.changepoints]).T
fourier = self._fourier_features(t)
X = np.column_stack([t_scaled, cp_features, fourier, np.ones_like(t_scaled)])
return X @ self.w
# Usage / verification: synthetic 2-year daily series with trend + yearly seasonality
rng = np.random.default_rng(0)
t = np.arange(0, 365 * 2)
trend = 0.05 * t
seasonality = 10 * np.sin(2 * np.pi * t / 365.25)
y = trend + seasonality + 50 + rng.normal(0, 1, len(t))
model = ProphetScratch(n_changepoints=5, fourier_order=4, period=365.25, lr=0.05, n_iters=3000)
model.fit(t, y)
pred = model.predict(t)
from sklearn.metrics import mean_absolute_error
print(mean_absolute_error(y, pred))
# Verified output: MAE = 0.842 (noise std was 1.0, so this is close to the theoretical floor)
```
### prophet library equivalent
```python
# pip install prophet (requires a working C++/Stan toolchain to build)
from prophet import Prophet
import pandas as pd
df = pd.DataFrame({
“ds”: pd.date_range(“2020–01–01”, periods=len(t), freq=”D”),
“y”: y
})
model = Prophet(yearly_seasonality=True, daily_seasonality=False, weekly_seasonality=False)
model.fit(df)
forecast = model.predict(df[[“ds”]])
print(mean_absolute_error(y, forecast[“yhat”].values))
# Note: prophet’s build (cmdstanpy/Stan backend) could not be installed in the verification
# sandbox due to network/build-time constraints, so this snippet is standard documented API
# usage, verified for correctness of syntax but not executed here. The from-scratch version
# above WAS executed and its MAE is a real measured number.
```
— -
## Algorithm 27. Learning-to-Rank (LambdaRank)
**Idea:** Optimize a ranking model directly for a ranking metric (like NDCG) rather than pointwise error. **LambdaRank** does this by computing pairwise gradients (“lambdas”) for every pair of documents within a query, scaled by how much swapping that pair would change NDCG (`|delta_NDCG|`) — pairs whose swap would hurt ranking quality the most get the strongest gradient signal.
### From scratch (NumPy, simplified pairwise LambdaRank with a linear scorer)
```python
import numpy as np
class LambdaRankScratch:
“””Simplified LambdaRank: a linear scoring function f(x) = x @ w, trained with
pairwise gradients weighted by |delta_NDCG| from swapping each relevant pair —
the core idea behind LambdaRank/LambdaMART.”””
def __init__(self, n_features, lr=0.01, n_iters=200, random_state=0):
rng = np.random.default_rng(random_state)
self.w = rng.normal(0, 0.01, n_features)
self.lr = lr
self.n_iters = n_iters
def _dcg_gain(self, rel):
return (2 ** rel — 1)
def fit(self, X, y, query_ids):
X = np.asarray(X, dtype=float)
y = np.asarray(y, dtype=float)
query_ids = np.asarray(query_ids)
unique_qids = np.unique(query_ids)
for _ in range(self.n_iters):
grad = np.zeros_like(self.w)
for qid in unique_qids:
mask = query_ids == qid
Xq, yq = X[mask], y[mask]
scores = Xq @ self.w
order = np.argsort(-scores)
ideal_order = np.argsort(-yq)
gains = self._dcg_gain(yq)
ideal_dcg = np.sum(gains[ideal_order] / np.log2(np.arange(2, len(yq) + 2)))
ideal_dcg = ideal_dcg if ideal_dcg > 0 else 1e-6
n = len(yq)
for i in range(n):
for j in range(n):
if yq[i] <= yq[j]:
continue # only consider pairs where i is MORE relevant than j
pos_i = np.where(order == i)[0][0]
pos_j = np.where(order == j)[0][0]
delta_ndcg = abs(
(gains[i] / np.log2(pos_i + 2) + gains[j] / np.log2(pos_j + 2)) -
(gains[i] / np.log2(pos_j + 2) + gains[j] / np.log2(pos_i + 2))
) / ideal_dcg
s_diff = scores[i] — scores[j]
lambda_ij = -delta_ndcg / (1 + np.exp(s_diff))
grad += lambda_ij * (Xq[i] — Xq[j])
self.w -= self.lr * grad / len(unique_qids)
return self
def predict(self, X):
return np.asarray(X, dtype=float) @ self.w
# Usage / verification: two queries, each with feature vectors + relevance labels
X_q1 = np.array([[0.8, 1.0, 0.9, 0.85], [0.3, 0.5, 0.1, 0.40],
[0.9, 1.0, 0.95, 0.90], [0.2, 0.0, 0.3, 0.30]])
y_q1 = np.array([3, 1, 3, 0]) # relevance labels (0=irrelevant, 3=highly relevant)
qid_q1 = np.array([1, 1, 1, 1])
X_q2 = np.array([[0.7, 0.8, 0.7, 0.75], [0.9, 1.0, 0.9, 0.95], [0.4, 0.4, 0.4, 0.50]])
y_q2 = np.array([2, 3, 1])
qid_q2 = np.array([2, 2, 2])
X = np.vstack([X_q1, X_q2])
y = np.concatenate([y_q1, y_q2])
qid = np.concatenate([qid_q1, qid_q2])
model = LambdaRankScratch(n_features=4, lr=0.05, n_iters=100, random_state=1).fit(X, y, qid)
scores = model.predict(X_q1)
print(scores, “-> predicted rank order:”, np.argsort(-scores))
# Verified output: scores=[2.036, 0.743, 2.143, 0.427]
# -> predicted order [2, 0, 1, 3] (true best-to-worst order is [0, 2, 1, 3] — the
# top-2 most relevant docs {0, 2} are correctly ranked above the bottom-2 {1, 3})
```
### LightGBM library equivalent (industry-standard way to train LambdaRank/LambdaMART)
```python
# pip install lightgbm
import lightgbm as lgb
train_data = lgb.Dataset(X, label=y, group=[len(X_q1), len(X_q2)])
params = {“objective”: “lambdarank”, “metric”: “ndcg”, “verbosity”: -1, “min_data_in_leaf”: 1}
gbm = lgb.train(params, train_data, num_boost_round=50)
scores = gbm.predict(X_q1)
print(scores, “-> predicted rank order:”, np.argsort(-scores))
# Verified output: scores=[4.478, -3.134, 4.478, -4.598]
# -> predicted order [0, 2, 1, 3] (exactly matches the true relevance order —
# same top-2/bottom-2 grouping as the scratch version, with LightGBM’s boosted-tree
# scorer achieving a sharper separation)
```
— -
## Algorithm 28. Matrix Factorization
**Idea:** For collaborative filtering (recommender systems), factorize a sparse user-item rating matrix `R ≈ P @ Q^T + user_bias + item_bias + global_mean`, where `P` (users x factors) and `Q` (items x factors) are learned latent factor matrices. Trained via SGD on only the *observed* ratings.
### From scratch (NumPy, SGD with bias terms)
```python
import numpy as np
class MatrixFactorizationScratch:
def __init__(self, n_factors=10, lr=0.01, reg=0.02, n_iters=100, random_state=0):
self.n_factors = n_factors
self.lr = lr
self.reg = reg
self.n_iters = n_iters
self.random_state = random_state
def fit(self, R):
“””R: (n_users, n_items) matrix; 0 = missing/unobserved rating.”””
R = np.asarray(R, dtype=float)
n_users, n_items = R.shape
rng = np.random.default_rng(self.random_state)
self.P = rng.normal(0, 0.1, (n_users, self.n_factors)) # user latent factors
self.Q = rng.normal(0, 0.1, (n_items, self.n_factors)) # item latent factors
self.b_u = np.zeros(n_users)
self.b_i = np.zeros(n_items)
self.mu = R[R != 0].mean() # global average rating
rows, cols = np.nonzero(R)
for _ in range(self.n_iters):
perm = rng.permutation(len(rows))
for idx in perm:
u, i = rows[idx], cols[idx]
pred = self.mu + self.b_u[u] + self.b_i[i] + self.P[u] @ self.Q[i]
err = R[u, i] — pred
self.b_u[u] += self.lr * (err — self.reg * self.b_u[u])
self.b_i[i] += self.lr * (err — self.reg * self.b_i[i])
P_u_old = self.P[u].copy()
self.P[u] += self.lr * (err * self.Q[i] — self.reg * self.P[u])
self.Q[i] += self.lr * (err * P_u_old — self.reg * self.Q[i])
return self
def predict(self, u, i):
return self.mu + self.b_u[u] + self.b_i[i] + self.P[u] @ self.Q[i]
def full_matrix(self):
return self.mu + self.b_u[:, None] + self.b_i[None, :] + self.P @ self.Q.T
# Usage / verification: synthetic rating matrix with known low-rank structure
rng = np.random.default_rng(2)
n_users, n_items, n_factors_true = 50, 30, 4
P_true = rng.normal(0, 1, (n_users, n_factors_true))
Q_true = rng.normal(0, 1, (n_items, n_factors_true))
R_full = 3 + P_true @ Q_true.T
mask = rng.random((n_users, n_items)) < 0.3 # only 30% of ratings observed
R_train = np.where(mask, R_full, 0)
model = MatrixFactorizationScratch(n_factors=4, lr=0.01, reg=0.05, n_iters=100, random_state=1)
model.fit(R_train)
pred_full = model.full_matrix()
test_mask = ~mask
rmse = np.sqrt(np.mean((pred_full[test_mask] — R_full[test_mask]) ** 2))
print(rmse)
# Verified output: held-out RMSE = 1.250
```
### scikit-surprise library equivalent (standard library for this exact task)
```python
# pip install scikit-surprise
from surprise import Dataset, Reader, SVD
import pandas as pd
rows, cols = np.nonzero(R_train)
df = pd.DataFrame({“user”: rows, “item”: cols, “rating”: R_train[rows, cols]})
reader = Reader(rating_scale=(df.rating.min(), df.rating.max()))
data = Dataset.load_from_df(df[[“user”, “item”, “rating”]], reader)
trainset = data.build_full_trainset()
algo = SVD(n_factors=4, random_state=1)
algo.fit(trainset)
test_rows, test_cols = np.nonzero(test_mask)
preds = np.array([algo.predict(u, i).est for u, i in zip(test_rows, test_cols)])
true_vals = R_full[test_rows, test_cols]
rmse = np.sqrt(np.mean((preds — true_vals) ** 2))
print(rmse)
# Note: scikit-surprise (which needs a C compiler at install time) could not be built in
# the verification sandbox, so this snippet is standard documented API usage, verified
# for correctness of syntax but not executed. The from-scratch SVD-style version above
# WAS executed and its RMSE is a real measured number.
```
— -
## Summary Notes
- **Verified with executed code:** Algorithms 1–25, 27, and the scratch half of 26 and 28 — every number quoted in this document for those sections came from an actual run in a Python 3.12 sandbox with `numpy`, `scipy`, `scikit-learn 1.8.0`, `xgboost`, `lightgbm`, `catboost`, `hmmlearn`, and `umap-learn` installed.
- **Library-only, not executed here:** the **Prophet** library snippet (26) and the **scikit-surprise** library snippet (28) — both require native build toolchains (Stan/C++ compiler) that were not available in this sandbox. Their scratch counterparts were fully executed and verified.
- All “from scratch” implementations use **NumPy only** (plus SciPy for the GMM’s multivariate Gaussian PDF, and Python’s `itertools`/`collections` standard library), consistent with the source repository’s stated approach.
- Where a library’s exact algorithm differs materially from the simplified from-scratch version (e.g., XGBoost’s optimal-split gain formula, LightGBM’s GOSS/EFB, CatBoost’s true ordered target statistics, sklearn’s per-split feature subsampling in Random Forest), this is called out explicitly in that section so results aren’t misread as claiming byte-for-byte equivalence — they are educational approximations of the same core idea, numerically validated to perform comparably.
