MACHINE LEARNING

Answer: (ii) Rejecting null when true

Explanation — Hypothesis Testing Errors:

Let $H_0$ = null hypothesis.

• Type I Error ($\alpha$): False Positive — reject $H_0$ when $H_0$ is actually true. $P(\text{Type I}) = \alpha$ (significance level, e.g., 0.05). Example: Convicting an innocent person.
• Type II Error ($\beta$): False Negative — accept / fail to reject $H_0$ when $H_1$ is true (i.e., $H_0$ false). $P(\text{Type II}) = \beta$, Power $=1-\beta$. Example: Acquitting a guilty person.
• (i) Accepting null when false → Type II
• (ii) Rejecting null when true → Type I ✓
• Confusion matrix mapping: Type I = FP, Type II = FN.

Hence (ii) correct.

Answer: (iii) Random subsets of the training data

Explanation — Bagging (Bootstrap Aggregating):

• Given training set $D$ of size $n$, Bagging creates $M$ bootstrap samples $D_m$: each by sampling $n$ points with replacement → random subset (≈63.2% unique per bag, rest out-of-bag).
• Train one base learner $f_m$ on each $D_m$ (e.g., decision trees in Random Forest).
• Aggregate: classification by majority vote, regression by averaging: $\hat{f}_{bag}(x)=\frac1M\sum f_m(x)$.
• Purpose: reduces variance, avoids overfitting, parallelizable.

Contrast:

• (i) same dataset — no diversity, defeats ensemble purpose
• (ii) only test data — would be leakage, never train on test
• (iv) feature-reduced only — that is feature bagging / Random Subspace part of Random Forest (both row + column sampling), but primary definition is row bootstrap.

So (iii) is core.

Why Clustering Important:
Unsupervised, discovers hidden structure without labels. Uses: customer segmentation, gene grouping, image segmentation, anomaly detection, document clustering, feature engineering, data compression.

K-means Algorithm Steps:

Input: Data $X=\{x_i\}_{i=1}^n$, $k$, distance (Euclidean)
Goal: minimize $J=\sum_{j=1}^k\sum_{x_i\in C_j}||x_i-\mu_j||^2$

1. Initialize: Choose $k$ centroids $\mu_j$ randomly (k-means++ better).
2. Assignment: Assign each $x_i$ to nearest centroid: $C_j=\{x_i: ||x_i-\mu_j|| \le ||x_i-\mu_l|| \forall l\}$
3. Update: Recompute $\mu_j = \frac1{|C_j|}\sum_{x_i\in C_j} x_i$
4. Repeat 2-3 until centroids stop moving or $J$ change < threshold (convergence to local optimum).

Suitable Example:
Data points: A(1,1), B(1.5,2), C(3,4), D(5,7), D(3.5,5), E(4.5,5), $k=2$
Init $\mu1=(1,1)$, $\mu2=(5,7)$
Iter1 assignments: cluster1 {A,B}, cluster2 {C,D}... recompute etc. After few iterations converges to two clusters.

Time Complexity Analysis:
Per iteration: $O(n \cdot k \cdot d)$ distance computations ($n$ points, $k$ centroids, $d$ dims). For $i$ iterations: $O(n k d i)$. Space $O((n+k)d)$. If $k,d$ constants, $O(n i)$ linear in $n$. Compared to hierarchical $O(n^2)$. Elkan/Hamerly accelerations reduce but worst still $O(n k d i)$. Typically fast, converges quickly (10-100 iterations). Mention Lloyd's algorithm.

Limitations: need pre-specify $k$ (elbow/silhouette), sensitive to init & outliers, assumes spherical clusters, Euclidean biased.

Bagging vs AdaBoost vs Gradient Boosting:

Bagging (Bootstrap Aggregating):

• Parallel, bootstrap samples, full trees, reduces variance by averaging (Random Forest). Each model independent, weight equal. Robust to overfit, handles noisy data well. Example: $M=100$ trees vote.

AdaBoost (Adaptive Boosting — Freund & Schapire):

• Sequential, adaptively reweights samples: increase weight for misclassified, decrease for correct. Weak learners typically stumps ($depth=1$). Final: $F(x)=\sum \alpha_t h_t(x)$, $\alpha_t=\frac12\ln((1-\epsilon_t)/\epsilon_t)$. Minimizes exponential loss $\sum \exp(-yF(x))$.
• Reduces bias (and some variance), very effective but sensitive to noise/outliers (weights blow up).

Gradient Boosting (Friedman — GBM, XGBoost):

• Sequential, fits new learner to residual / negative gradient of loss: $r_i^{(m)} = -\partial L(y_i,F_{m-1}(x_i))/\partial F_{m-1}$. For squared loss $r=y-F$, for logistic gradient. Update $F_m=F_{m-1}+
  u \gamma_m h_m(x)$($
  u$ shrinkage).
• Reduces bias, flexible (any differentiable loss), often strongest accuracy, needs careful tuning ( $M$, learning rate, depth, regularization) to avoid overfit. XGBoost adds second-order Taylor, leaf weight regularization $\Omega=\gamma T+\frac12\lambda||w||^2$.

Bias-Variance:

• Bagging — primarily variance reduction (averaging decorrelated trees); slight bias increase if bootstrap.
• Boosting — primarily bias reduction (sequentially correcting errors); variance can increase if too many iterations, controlled by shrinkage/early stopping.

Choosing: Noisy, limited tuning time → Bagging/RF. Max accuracy, structured data → Gradient Boosting/XGBoost/LightGBM. Very weak stumps + exponential loss → AdaBoost (now largely superseded by GBM).

Hierarchical Clustering:

Unsupervised method building hierarchy / dendrogram of clusters — tree where leaves = points, internal nodes = merges/splits at certain distance.

Two approaches:

1. Agglomerative (Bottom-Up) — most common:

   • Start each point as cluster.
   • Repeat: find two closest clusters via linkage, merge, update distances.
   • Stop at $k=1$ or desired $k$ (cut dendrogram).
   • Linkages:
     • Single linkage: $d(C_i,C_j)=\min_{x\in C_i,y\in C_j} d(x,y)$ — produces elongated chains, sensitive to noise
     • Complete: $\max$ distance — compact spherical clusters
     • Average: mean distance
     • Ward: minimizes increase in within-cluster SSE $\Delta = SSE_{merged}-SSE_{i}-SSE_{j}$ — often best, prefers equal-sized.
   • Complexity $O(n^3)$ naive, $O(n^2\log n)$ with heap, $O(n^2)$ memory.

2. Divisive (Top-Down):

   • Start one cluster, recursively split (e.g., via K-means), rarer due to exponential.

Dendrogram: Height = distance at merge; cut at height $h$ gives clustering. Can inspect for natural $k$.

Advantages: No preset $k$ needed (choose after), shows structure at multiple resolutions, deterministic, visualization.

Disadvantages: Greedy (once merged cannot undo), sensitive to outliers/noise (single linkage), $O(n^2)$ memory limits large data, difficult to handle large $n$ (>10k).

Example: Data points (1,2),(2,2),(8,8): single linkage merges first two at dist 1, then merges with (8,8) at ~8.5 distance dendrogram.

Use: Gene expression phylogeny, document taxonomy, small-medium datasets where hierarchy insightful. Often combined with K-means for scale.