Unit 3: Supervised Machine Learning

I. Orientation

Supervised machine learning learns a mapping from input data to known output labels using labelled examples. A model is trained on pairs ((\mathbf{x}, y)), where (\mathbf{x}) contains features and (y) is the target. The learned relationship is then used to predict outputs for unseen data.

• Training principle: The algorithm estimates parameters from a training set and minimizes a loss function, such as mean squared error or cross-entropy.
• Feature and target convention: Features are commonly represented by (X), while the target variable is represented by (y). A prediction is written (\hat{y}).
• Two main tasks: Regression predicts numerical quantities, while classification predicts discrete categories.
• Generalization: A useful model performs well on new data, not merely on the examples used for training.
• Data splitting: A dataset is commonly divided into training and testing sets; a validation set or cross-validation may be used for model selection.
• Model assumptions: Different algorithms make different assumptions about linearity, independence, distance, or the structure of decision boundaries.

II. Regression — Predicting Continuous Values

Regression methods estimate a numerical target such as house price, temperature, salary, or demand. Their predictions are commonly evaluated using errors between actual values (y_i) and predicted values (\hat{y}_i).

A. Regression

Regression models describe how one or more input variables influence a continuous output. The aim is usually to minimize a numerical loss while retaining useful predictive ability.

• Mean Squared Error (MSE): For (n) observations, the loss is
  [
  \mathrm{MSE}=\frac{1}{n}\sum_{i=1}^{n}(y_i-\hat{y}_i)^2
  ]
  where (y_i) is the actual value and (\hat{y}_i) is the prediction.
• Root Mean Squared Error: (\mathrm{RMSE}=\sqrt{\mathrm{MSE}}), expressed in the same units as the target.
• Residual: The residual (e_i=y_i-\hat{y}_i) measures the prediction error for observation (i).
• Interpretation: A regression line or tree estimates the conditional relationship between features and the expected value of the target.

B. Linear Regression

Linear Regression models the target as a weighted sum of input features. It is appropriate when the average relationship between predictors and the target is approximately linear.

• Simple model: With one feature (x),
  [
  \hat{y}=\beta_0+\beta_1x
  ]
  where (\beta_0) is the intercept and (\beta_1) is the slope.
• Multiple features: For (p) features,
  [
  \hat{y}=\beta_0+\beta_1x_1+\cdots+\beta_px_p
  ]
  where (\beta_j) represents the estimated change in (y) for a one-unit change in (x_j), holding other features constant.
• Parameter estimation: Ordinary Least Squares chooses coefficients that minimize the sum of squared residuals:
  [
  \mathrm{SSE}=\sum_{i=1}^{n}(y_i-\hat{y}_i)^2.
  ]
• Assumptions: Important assumptions include linearity, independent observations, approximately constant error variance, and limited problematic multicollinearity.
• Limitation: A straight line cannot represent a strongly curved relationship unless features are transformed.

C. Polynomial Regression

Polynomial Regression represents curvature by adding powers of a feature while remaining linear in its coefficients.

• Model form: A degree-(d) model may be written
  [
  \hat{y}=\beta_0+\beta_1x+\beta_2x^2+\cdots+\beta_dx^d.
  ]
  Here (d) is the polynomial degree.
• Meaning: The terms (x^2,x^3,\ldots) allow the fitted curve to bend, even though the coefficients (\beta_j) are estimated linearly.
• Example: A degree-2 model can represent a U-shaped relationship, such as a measured quantity that decreases and then increases with (x).
• Model complexity: Increasing (d) can reduce training error but may produce unstable oscillations and poor test performance.
• Practical control: Feature scaling, regularization, and selecting degree using validation data help prevent an unnecessarily complex polynomial.

D. Decision Tree Regression

Decision Tree Regression predicts a continuous value by partitioning the feature space into regions and assigning a numerical prediction to each region.

• Splitting rule: A candidate split, such as (x_1<5), is selected to reduce within-node squared error.
• Leaf prediction: The prediction in a leaf is commonly the mean target value of training observations reaching that leaf:
  [
  \hat{y}{\text{leaf}}=\frac{1}{m}\sum{i=1}^{m}y_i,
  ]
  where (m) is the number of observations in the leaf.
• Structure: Internal nodes contain tests, branches represent outcomes, and leaves contain predictions.
• Strengths: Trees model nonlinear relationships, interactions, and different measurement scales without requiring feature scaling.
• Limitations: A deep tree can memorize training observations. Maximum depth, minimum leaf size, or pruning controls this tendency.

III. Classification — Predicting Categories

Classification assigns an observation to one of two or more classes, such as spam/not spam or benign/malignant. A classifier may output a class label, a score, or a probability.

A. Classification

Classification learns a decision rule separating labelled categories. Its performance must be assessed with measures suited to class predictions rather than only numerical error.

• Binary classification: There are two classes, often coded (0) and (1); multiclass classification contains three or more classes.
• Confusion matrix: It records true positives, true negatives, false positives, and false negatives.
• Accuracy:
  [
  \mathrm{Accuracy}=\frac{TP+TN}{TP+TN+FP+FN}.
  ]
  It can be misleading when classes are highly imbalanced.
• Precision and recall: Precision (=TP/(TP+FP)) measures correctness among predicted positives; recall (=TP/(TP+FN)) measures detected positives.
• Decision boundary: The boundary divides feature space into regions assigned to different classes.

B. Logistic Regression

Logistic Regression predicts the probability of a class using the logistic, or sigmoid, function. It is a classification algorithm despite containing the word “regression.”

• Linear score:
  [
  z=\beta_0+\beta_1x_1+\cdots+\beta_px_p.
  ]
  The (x_j) values are features and (\beta_j) are learned coefficients.
• Sigmoid probability:
  [
  P(y=1\mid\mathbf{x})=\sigma(z)=\frac{1}{1+e^{-z}}.
  ]
  The output lies between 0 and 1.
• Class decision: With a threshold of (0.5), predict class 1 when (P(y=1\mid\mathbf{x})\geq0.5); changing the threshold changes precision and recall.
• Training objective: Coefficients are usually learned by minimizing log loss, which strongly penalizes confident incorrect predictions.
• Interpretation: A positive (\beta_j) increases the log-odds of class 1 by (\beta_j) for a one-unit increase in (x_j), holding other features fixed.
• Limitation: The basic decision boundary is linear in the features.

C. K-Nearest Neighbour

K-Nearest Neighbour (KNN) classifies a new observation according to the labels of nearby training observations.

• Procedure: Choose (k), calculate distances from the new point to training points, select the (k) closest, and use majority voting.
• Distance: Euclidean distance between (\mathbf{x}) and (\mathbf{z}) is
  [
  d(\mathbf{x},\mathbf{z})=\sqrt{\sum_{j=1}^{p}(x_j-z_j)^2}.
  ]
• Choice of (k): A small (k), such as 1, creates flexible boundaries and may be sensitive to noise; a larger (k) gives smoother decisions.
• Scaling requirement: A feature measured from 0–10,000 can dominate one measured from 0–1, so standardization is generally important.
• Characteristics: KNN has little explicit training but can be computationally expensive at prediction time and performs poorly in very high dimensions.

D. Introduction to Decision Tree Classifier and Random Forest

Decision trees classify observations through a sequence of feature-based tests; Random Forest combines many such trees to improve stability and predictive performance.

• Decision Tree Classifier: A node may test whether (x2<3.5). Splits are chosen using impurity measures such as Gini impurity:
  [
  G=1-\sum{k=1}^{K}p_k^2,
  ]
  where (p_k) is the proportion of class (k) in the node.
• Leaf output: A classification leaf commonly predicts the majority class or provides class proportions.
• Random Forest: It trains many trees on bootstrap samples and random subsets of features, then combines their outputs by majority vote.
• Why it helps: Averaging diverse trees generally reduces variance compared with one deep tree.
• Strengths and limitations: Trees capture nonlinear interactions and require little preprocessing, but individual rules may be less smooth and a large forest is less directly interpretable.

E. Naïve Bayes

Naïve Bayes applies Bayes’ theorem while assuming that features are conditionally independent given the class.

• Bayes’ theorem:
  [
  P(C\mid\mathbf{x})=\frac{P(\mathbf{x}\mid C)P(C)}{P(\mathbf{x})},
  ]
  where (C) is a class, (P(C)) is its prior probability, and (P(C\mid\mathbf{x})) is the posterior probability.
• Naïve assumption:
  [
  P(\mathbf{x}\mid C)=\prod_{j=1}^{p}P(x_j\mid C).
  ]
  The features need not be truly independent for the method to work effectively.
• Prediction: Select the class with the largest posterior probability, often comparing (P(C)\prod_jP(x_j\mid C)).
• Applications: Gaussian Naïve Bayes suits continuous features; Multinomial Naïve Bayes is widely used for word counts in text classification.
• Smoothing: Laplace smoothing prevents a zero probability for an unseen feature-category combination.

IV. Concepts of Bias, Variance, Underfitting and Overfitting

These concepts explain why a model may perform poorly and how complexity affects generalization.

A. Bias

Bias is systematic error caused by an overly restrictive model or incorrect assumptions.

• High-bias model: A linear model fitted to a strongly curved relationship may miss important structure and have high training and test error.
• Error tendency: Bias is associated with predictions that are consistently too high, too low, or otherwise systematically inaccurate.
• Reduction: Adding relevant features, allowing nonlinear terms, or using a more flexible algorithm can reduce bias, although it may increase variance.

B. Variance

Variance is the amount by which a model’s predictions change when trained on different samples from the same population.

• High-variance model: A deep decision tree may fit individual training observations and change substantially when a few observations are replaced.
• Typical symptom: Training error is very low, but test error is much higher.
• Reduction: More training data, regularization, shallower trees, larger KNN (k), or ensemble averaging can reduce variance.

C. Underfitting

Underfitting occurs when a model is too simple to capture the meaningful pattern in the data.

• Indicators: Both training and test performance are poor; residuals may show a clear curve or systematic pattern.
• Example: Degree-1 Linear Regression used for a quadratic relationship underfits because it cannot model (x^2).
• Remedies: Increase model capacity, add informative features, reduce excessive regularization, or use Polynomial Regression or a tree-based method.

D. Overfitting

Overfitting occurs when a model learns noise, accidental patterns, or outliers instead of the general relationship.

• Indicators: Training performance is excellent while validation or test performance declines.
• Example: A very high-degree polynomial can pass almost exactly through training points but oscillate between them.
• Remedies: Use cross-validation, regularization, pruning, early stopping, feature selection, more data, or ensemble methods.
• Model selection principle: Choose complexity using unseen validation evidence, not by minimizing training error alone; this balances bias and variance.