MACHINE LEARNING

Answer: (iv) All of the above

Correct uses of Cross Validation (CV):

Cross validation (k-fold, LOOCV, stratified) estimates generalization performance by partitioning data into train/validation folds repeatedly.

1. (i) Selecting variables / feature selection: CV error is used to compare subsets of features and choose set with lowest validation error, avoiding overfitting.
2. (ii) Comparing predictors / model selection: Compare different model families (e.g., linear vs tree vs SVM) on CV score.
3. (iii) Electing / selecting parameters in prediction function (hyperparameter tuning): e.g., choosing $k$ in KNN, $\lambda$ in ridge, $C$, $\gamma$ in SVM via grid search with CV. Also called hyperparameter optimization.

Since all three are standard applications, (iv) All of the above is correct.

Additional note: CV does not train final model; after selection, model is retrained on full training data and evaluated on held-out test set.

Answer: (iv) Tom Mitchell

Explanation:

• Tom Mitchell is widely cited as the father of Machine Learning in academic curricula (author of Machine Learning, McGraw-Hill, 1997) who gave the formal definition: "A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E."
• Arthur Samuel (1959) coined the term Machine Learning and is historically the true pioneer, but he is not listed in options.
• Geoffrey Everest Hinton is the Godfather of Deep Learning, not general ML.
• Options (i) Geoffrey Hill and (ii) Geoffrey Chaucer are distractors (poets).

In the context of this MCQ, expected answer is Tom Mitchell. If strictly historical, Arthur Samuel would be correct.

Answer: (i) Only (1) — as per correct ML theory. Note many exam keys incorrectly mark (ii) due to typo; clarified below.

Statement analysis:

• (1) In GD and SGD, you update a set of parameters iteratively to minimize the error — TRUE. Both are iterative optimization algorithms: $w := w - \eta
  abla J(w)$.

• (2) In SGD you have to run through all samples for a single update — FALSE. SGD uses one randomly chosen sample (or one mini-batch) per update. Statement describes Batch GD, not SGD. This is a common textbook error in the question.

• (3) In GD you either use entire data or subset to update — FALSE. Standard GD uses entire training set per update. Using a subset is Mini-batch GD or SGD, not vanilla GD.

Strictly: only (1) is true → (i) Only (1). If exam expects (ii) or (iii), it has swapped definitions. Conceptual correct behavior:

• GD: one update per epoch using all $m$ examples — expensive but stable.
• SGD: one update per example — noisy but fast, frequent updates.
• Mini-batch: compromise (e.g., 32/64 samples).

Answer: (ii) supervised learning

Explanation:

• Supervised learning uses labelled training data i.e. each input $x$ is paired with correct output $y$. The algorithm learns a mapping $f: X \rightarrow Y$ to predict labels for unseen data. Examples: classification (spam detection), regression (house price prediction).
• Unsupervised learning uses unlabelled data to find hidden structure (clustering, dimensionality reduction, association).
• Reinforcement learning uses reward/feedback from environment through trial-and-error, not explicit correct labels.
• Active learning is a special case of semi-supervised where learner queries an oracle for labels of selected instances — it uses labels but the base definition asked is supervised.

Therefore labelled training data is the defining characteristic of supervised learning.

Three Applications Where ML is Appropriate (pattern-based, large data, no explicit rule):

1. Handwritten Digit/ Face Recognition: Too many variations to code rules; learn from examples (MNIST, CNN). Data abundant, pattern statistical.
2. Spam Email Filtering / Recommendation Systems: User preferences shift, need adaptation from labeled feedback; probabilistic text features ideal for Naive Bayes / collaborative filtering.
3. Speech Recognition / Machine Translation / Medical Diagnosis from images: No exact algorithmic solution, benefits from deep learning on large datasets (e.g., tumor detection from X-rays).

Three Where ML is Inappropriate (deterministic, exact, safety-critical, small data):

1. Simple Arithmetic / Payroll Calculation / Sorting: Exact algorithmic solution exists, 100% accuracy required; ML would approximate and err.
2. Real-time Safety-Critical Control with Formal Guarantees (e.g., Aircraft flight control certification, Nuclear reactor shutdown): Need provable correctness, interpretability; ML black-box unreliable, hard to verify.
3. Problems with No Data / No Pattern (e.g., determining a cryptographic hash inverse, generating truly random numbers, or one-off legal reasoning requiring causal explanation): ML needs historical data; if data absent or task requires deductive reasoning/common sense not statistical correlation, ML fails.

Criteria: ML appropriate when: large data, pattern exists but not analytically describable, tolerance for probabilistic error, adaptation needed. Inappropriate when: exact solution exists, need guarantee, no data, or solution requires reasoning beyond correlation.

Important Objectives of Machine Learning:

As per ML theory (combines CS, stats, optimization), main objectives:

1. Prediction / Generalization: Learn model $f$ that generalizes to unseen data, minimizing expected risk $R(f)=E[L(f(x),y)]$, not just training error. Overcome overfitting via bias-variance trade-off.

2. Knowledge Discovery / Pattern Recognition: Extract hidden patterns, associations, trends from large data (data mining).

3. Automation & Decision Making: Automate tasks requiring human intelligence (classification, recommendation, control) with minimal human intervention.

4. Handling Uncertainty & Noise: Deal with incomplete, noisy, high-dimensional data via probabilistic modeling.

5. Adaptation: Continuously improve with more experience $E$ (online learning, concept drift).

6. Optimization: Find $w^* = \arg\min_w J(w)$ efficiently (GD, SGD).

7. Efficiency & Scalability: Handle big data with feasible computation/memory.

8. Interpretability vs Performance: Balance accurate black-box (deep nets) vs explainable models.

9. Specific statistical goals: Minimize empirical risk + regularization: $J(w)=\frac1n\sum L(y_i, f(x_i;w)) + \lambda\Omega(w)$

In short: build systems that learn from data to make accurate, robust, scalable predictions/decisions and discover useful knowledge.

Inductive Bias and Hypothesis Space:

Hypothesis Space $H$: Set of all hypotheses / functions learner can represent. e.g., for Boolean concepts with $n$ attributes, $|H|=3^n$ (general-to-specific). For linear regression, $H=\{w^T x + b : w\in\mathbb{R}^d\}$.

Inductive Bias: Set of assumptions that learner uses to generalize beyond training data and choose one hypothesis among many consistent ones. Without bias, learner cannot generalize (cannot classify unseen instances).

Mitchell definition: Any basis for choosing one generalization over another beyond consistency with data.

Types:

1. Language / Restriction Bias: Restrict $H$ (e.g., only conjunctive hypotheses, only linear separators). If true concept not in $H$, cannot learn.
2. Preference / Search Bias: Prefer certain hypotheses (e.g., Occam's razor — prefer simpler, smaller trees, smaller weights; regularization prefers low norm). $H$ may still contain all, but search ordered.

Example — Candidate Elimination: $H$ = conjunctions of attributes. Bias: $c \in H$ is conjunctive — cannot learn disjunction $X\lor Y$.

Example — Decision Tree: Bias: prefers shorter trees (information gain heuristic) that fit data.

Why needed: No Free Lunch — without bias, all hypotheses consistent with data are equally valid, no prediction on unseen point. Bias makes learning possible but limits learnability; incorrect bias → underfitting.

Relation to Occam's Razor: "Prefer simplest hypothesis fitting data" — implemented via MDL, regularization, pruning.

Overfitting and Underfitting:

Overfitting: Model learns training data too well, including noise/outliers; high variance, low bias. Memorization. $Error_{train} \ll Error_{test}$. Example: Degree-10 polynomial fitting 10 points with wiggling curve passing through all points.

Underfitting: Model too simple to capture underlying pattern; high bias, low variance. $Error_{train} \approx Error_{test}$ but both high. Example: Linear line fitting parabolic data.

Model complexity view: Train vs Validation error vs capacity (U-shaped test error). Optimal is intermediate capacity (sweet spot) where bias-variance balanced.

2D Example:

Data: Parabolic trend $y = x^2 + noise$, points near U-shape.

• Underfit (linear, degree 1): Straight line cutting through U, misses curvature → large error on both train and test.

  y
  *   *
   \ /     data *
    .      linear ___  (misses curve)
   / \
  *   *
  

• Good fit (degree 2): Parabola $y= w_0+w_1x+w_2x^2$ captures trend smoothly, generalizes.

• Overfit (degree 9+): Wiggly curve passing exactly through every noisy point, oscillates wildly between points — zero train error but huge test error.

Remedies:

• Underfit: increase complexity, add features, reduce regularization, longer training.
• Overfit: more data, regularization (L1/L2), pruning, dropout, early stopping, cross-validation, feature selection, reduce degree.

Visual: Plot $x$ vs $y$, noisy quadratic data; underfit = straight line under, overfit = wiggly interpolating, good = smooth quadratic.