Comprehensive Notes on Machine Learning and Supervised Learning

Introduction to Machine Learning and Core Concepts

• Definition of Machine Learning (Arthur Samuel, 1959): Machine Learning is a field of study that gives computers the ability to learn without being explicitly programmed.

• Formal Definition of Learning (Tom Mitchell, 1998): A computer program is said to learn from experience $E$ with respect to some task $T$ and some performance measure $P$, if its performance on $T$ as measured by $P$, improves with experience $E$.

• Key Applications of Machine Learning:

  • Prediction: Estimating continuous values based on historical data (e.g., Used Car Price Prediction).

  • Classification: Assigning inputs into discrete categories (e.g., Detecting whether a medical tumor is Malignant or Benign).

  • Clustering: Grouping unlabeled data points based on feature similarity (e.g., Analyzing user engagement patterns on social media).

  • Association Rule Mining: Discovering interesting relationships between variables in large databases (e.g., Market Basket Analysis).

Learning Paradigms

• Supervised Learning:

  • Provided with a dataset containing input features along with known correct output labels.

  • Operates under the assumption that there is an underlying relationship mapping the input features to the output.

  • Examples:

    • Predicting used car prices based on miles driven (e.g., mapping $2000$, $4000$, $6000$, $8000$ miles driven to prices of $1$, $2$, $3$ Lakhs Rupees).

    • Determining tumor malignancy from patient age and tumor size.

• Unsupervised Learning:

  • Allows approaching problems with little or no prior idea of what the results should look like.

  • Operates on unlabeled datasets containing input features $x_1, x_2$ without target output labels to discover underlying structure.

• Semi-Supervised / Reinforcement Learning:

  • A trial-and-error learning process where an autonomous agent interacts with an environment.

  • The agent performs actions, receives rewards or penalties, and continuously updates its action policy to maximize cumulative long-term rewards.

Supervised Learning Workflow and Problem Formulation

• Supervised Learning Architecture:

  • A Training Set is fed into a Learning Algorithm.

  • The Learning Algorithm outputs a Hypothesis function (denoted as $h$).

  • The Hypothesis function accepts input Features ($X$) to generate a Predicted Output ($Y$).

• Main Categories of Supervised Learning:

  • Regression Problem: Maps input variables to a continuous target output function (e.g., Feature: Miles Driven $\rightarrow$ Output: Price).

  • Classification Problem: Maps input variables into discrete output categories or class labels (e.g., Features: Age and Tumor Size $\rightarrow$ Output Class Label: Malignant or Benign).

• Mathematical Formalism and Dataset Notation:

  • Example Dataset (Used Car Price Prediction):

    • Miles Driven ($x_1$): $1230$, Engine Capacity ($x_2$): $1000\text{ hp}$ $\rightarrow$ Price ($y$): $220000$

    • Miles Driven ($x_1$): $3230$, Engine Capacity ($x_2$): $890\text{ hp}$ $\rightarrow$ Price ($y$): $140500$

    • Miles Driven ($x_1$): $4230$, Engine Capacity ($x_2$): $980\text{ hp}$ $\rightarrow$ Price ($y$): $80000$

  • Notation definitions:

    • $m$: Total number of training examples.

    • $x$'s: Input variables or features.

    • $y$'s: Output variables or target labels.

    • $(x, y)$: A single training example.

    • (x^{(i)}, y^{(i)})$: The i^{\text{th}} specific training example in the dataset.\n\n\n# Univariate Linear Regression\n\n* **Linear Regression with One Variable:**\n * **Hypothesis Function:**\n * h_{\theta}(x) = \theta_0 + \theta_1 x\n * **Objective:** Choose parameter values \theta_0, \theta_1$such that$h_{\theta}(x)$is as close as possible to$y$for all training examples$(x, y).\n\n* **Error Measurement and Cost Function:**\n * Error at the i^{\text{th}}$data point:$h_{\theta}(x^{(i)}) - y^{(i)}\n * **Mean Squared Error (MSE) / Cost Function:**\n * J(\theta_0, \theta_1) = \frac{1}{2m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)})^2\n * **Optimization Task:** Find \theta_0, \theta_1 to minimize the cost function:\n * \min_{\theta_0, \theta_1} J(\theta_0, \theta_1) = \min_{\theta_0, \theta_1} \frac{1}{2m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)})^2\n\n\n# Cost Function Analysis and Convexity\n\n* **Simplified Hypothesis Model:**\n * Assume \theta_0 = 0$, yielding the simplified hypothesis:$h_{\theta}(x) = \theta_1 x\n * Simplified Cost Function: J(\theta_1) = \frac{1}{2m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)})^2\n * Optimization Goal: \min_{\theta_1} J(\theta_1)\n\n* **Concrete Numerical Example:**\n * Consider dataset points: (1, 1)$,$(2, 2)$,$(3, 3).\n * *Case 1:* Set \theta_1 = 0.5$, so$h_{\theta}(x) = 0.5 x.\n * Predictions: h_{\theta}(1) = 0.5$,$h_{\theta}(2) = 1.0$,$h_{\theta}(3) = 1.5\n * J(0.5) = \frac{1}{2 \times 3} \left[ (0.5 - 1)^2 + (1.0 - 2)^2 + (1.5 - 3)^2 \right]\n * J(0.5) = \frac{1}{6} \left[ (-0.5)^2 + (-1.0)^2 + (-1.5)^2 \right] = \frac{1}{6} \left[ 0.25 + 1.0 + 2.25 \right] = \frac{3.5}{6} \approx 0.58\n * *Case 2:* Set \theta_1 = 1.0$, so$h_{\theta}(x) = 1.0 x.\n * Predictions: h_{\theta}(1) = 1.0$,$h_{\theta}(2) = 2.0$,$h_{\theta}(3) = 3.0\n * J(1.0) = \frac{1}{6} \left[ (1 - 1)^2 + (2 - 2)^2 + (3 - 3)^2 \right] = 0\n * Plotting J(\theta_1)$across different values of$\theta_1$produces a parabolic curve centered at$\theta_1 = 1.0$, demonstrating that$\theta_1 = 1.0 minimizes the cost function.\n\n* **Convexity Property:**\n * For the full hypothesis h_{\theta}(x) = \theta_0 + \theta_1 x$, the Mean Squared Error cost function$J(\theta_0, \theta_1) forms a convex surface (bowl-shaped), guaranteeing a single global minimum without local minima.\n\n\n# Multivariate Linear Regression and Polynomial Models\n\n* **Multivariate Notation and Setup:**\n * n: Number of input features.\n * x^{(i)}$: Input feature vector of the$i^{\text{th}} training example.\n * x_j^{(i)}$: Value of feature$j$in the$i^{ ext{th}} training example.\n\n* **Multivariate Hypothesis and Matrix Representation:**\n * Expanded Form: h_{\theta}(x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \dots + \theta_n x_n\n * Vector Formulations (defining x_0 = 1):\n * X = [x_0, x_1, \dots, x_n]^T \in \mathbb{R}^{n+1}\n * \Theta = [\theta_0, \theta_1, \dots, \theta_n]^T \in \mathbb{R}^{n+1}\n * Compact Hypothesis: h_{\theta}(x) = \Theta^T X\n * Multivariate Cost Function:\n * J(\Theta) = \frac{1}{2m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)})^2\n * Goal: \min_{\Theta} J(\Theta)\n\n* **Polynomial Regression Models:**\n * Polynomial regression fits non-linear relationships using linear regression machinery by substituting polynomial feature terms:\n * *Quadratic Model:* h_{\theta}(x) = \theta_0 + \theta_1 x + \theta_2 x^2\n * *Cubic Model:* h_{\theta}(x) = \theta_0 + \theta_1 x + \theta_2 x^2 + \theta_3 x^3\n * *Non-Linear Feature Transformations:* h_{\theta}(x) = \theta_0 + \theta_1 x + \theta_2 \sqrt{x}\n\n\n# Gradient Descent Optimization\n\n* **Gradient Descent Algorithm Concept:**\n * An iterative optimization technique used to find parameter vector \Theta$that minimizes the cost function$J(\Theta).\n * *Procedure:*\n 1. Start with initial parameter values (e.g., \theta_i = 0$for all$i).\n 2. Continuously modify \theta_0, \theta_1, \dots, \theta_n$to decrease$J(\theta_0, \theta_1, \dots, \theta_n) until reaching a local or global minimum.\n\n* **Univariate Gradient Descent:**\n * Update equation: \theta_j := \theta_j - \alpha \frac{\partial}{\partial \theta_j} J(\theta_0, \theta_1)$for$j \in {0, 1}\n * Where \alpha represents the **Learning Rate**.\n * **Simultaneous Update Requirement:** Parameters must be updated simultaneously at every iteration:\n * \text{temp}0 := \theta_0 - \alpha \frac{\partial}{\partial \theta_0} J(\theta_0, \theta_1)\n * \text{temp}_1 := \theta_1 - \alpha \frac{\partial}{\partial \theta_1} J(\theta_0, \theta_1)\n * \theta_0 := \text{temp}_0\n * \theta_1 := \text{temp}_1\n * **Partial Derivative Derivations:**\n * \frac{\partial}{\partial \theta_0} J(\theta_0, \theta_1) = \frac{1}{m} \sum{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)})\n * \frac{\partial}{\partial \theta_1} J(\theta_0, \theta_1) = \frac{1}{m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)}) x^{(i)}\n * **Concrete Univariate Iterative Algorithm:**\n * Repeat until convergence:\n * \theta_0 := \theta_0 - \alpha \frac{1}{m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)})\n * \theta_1 := \theta_1 - \alpha \frac{1}{m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)}) x^{(i)}\n\n* **Multivariate Gradient Descent:**\n * Partial derivative for feature j$:$\frac{\partial}{\partial \theta_j} J(\Theta) = \frac{1}{m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)}) x_j^{(i)}\n * Algorithm: Repeat until convergence (simultaneously update for every j = 0, 1, \dots, n):\n * \theta_j := \theta_j - \alpha \frac{1}{m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)}) x_j^{(i)}\n\n* **Effects and Selection of Learning Rate \alpha:**\n * *If \alpha is too small:* Gradient descent updates are small, causing convergence to be extremely slow.\n * *If \alpha is too large:* Gradient descent can overshoot the minimum, fail to converge, or even diverge.\n * *Fixed \alpha:* Gradient descent can naturally converge to a local minimum as step sizes shrink with smaller gradients.\n * *Convergence Checking:* Correct implementation requires J(\Theta)$to decrease after every single iteration. If$J(\Theta)$increases, reduce$\alpha\n\n\n# Least Square Method Analytical Solution\n\n* **Analytical Approach Derivation:**\n * Straight line hypothesis: h_{\theta}(x) = \theta_0 + \theta_1 x\n * Residual error at i^{\text{th}}$point:$e_i = h_{\theta}(x^{(i)}) - y^{(i)} = \theta_0 + \theta_1 x^{(i)} - y^{(i)}\n * Squared error: e_i^2 = (\theta_0 + \theta_1 x^{(i)} - y^{(i)})^2\n * Total error across p$data points:$E = \sum_{i=1}^{p} (\theta_0 + \theta_1 x^{(i)} - y^{(i)})^2\n * Minimizing Total Error E requires setting partial derivatives to zero:\n * \frac{\partial E}{\partial \theta_0} = -2 \sum_{i=1}^{p} (\theta_0 + \theta_1 x^{(i)} - y^{(i)}) = 0\n * \frac{\partial E}{\partial \theta_1} = -2 \sum_{i=1}^{p} (\theta_0 + \theta_1 x^{(i)} - y^{(i)}) x^{(i)} = 0\n * Solving system of equations yields closed-form expressions:\n * \theta_0 = \frac{1}{p} \left( \sum_{i=1}^{p} y^{(i)} - \theta_1 \sum_{i=1}^{p} x^{(i)} \right)\n * \theta_1 = \frac{p \left( \sum_{i=1}^{p} x^{(i)} y^{(i)} \right) - \left( \sum_{i=1}^{p} x^{(i)} \right) \left( \sum_{i=1}^{p} y^{(i)} \right)}{p \left( \sum_{i=1}^{p} (x^{(i)})^2 \right) - \left( \sum_{i=1}^{p} x^{(i)} \right)^2}\n\n* **Complete Step-by-Step Worked Example:**\n * *Given Data Points (p = 5):* \{(1, 3), (2, 4), (3, 5), (4, 6), (5, 8)\}}\n * *Summary Table Calculations:*\n * x_i \in {1, 2, 3, 4, 5} \implies \sum_{i=1}^{5} x_i = 15\n * y_i \in {3, 4, 5, 6, 8} \implies \sum_{i=1}^{5} y_i = 26\n * x_i^2 \in {1, 4, 9, 16, 25} \implies \sum_{i=1}^{5} x_i^2 = 55\n * x_i y_i \in {3, 8, 15, 24, 40} \implies \sum_{i=1}^{5} x_i y_i = 90\n * *Solving for Slope \theta_1:*\n * \theta_1 = \frac{5(90) - (15)(26)}{5(55) - (15)^2} = \frac{450 - 390}{275 - 225} = \frac{60}{50} = 1.2\n * *Solving for Intercept \theta_0:*\n * \theta_0 = \frac{1}{5} (26 - 1.2 \times 15) = \frac{1}{5} (26 - 18) = \frac{8}{5} = 1.6\n * *Fitted Equation of Straight Line:*\n * y = 1.6 + 1.2 x\n\n\n# Feature Preprocessing Techniques\n\n* **Feature Scaling Purpose:**\n * Ensures that features are on comparable scales, enabling gradient descent to converge significantly faster and avoiding inefficient updates.\n\n* **Preprocessing Methods:**\n * *Simple Feature Rescaling:*\n * Example: For x_1 = \text{House Size}$($0 - 2000\text{ ft}^2$) and$x_2 = \text{Bedrooms}$($1 - 5):\n * x_1 = \frac{\text{Size of house}}{2000}\n * x_2 = \frac{\text{No. of Bedrooms}}{5}\n * *Mean Normalization:*\n * Replaces feature x_i$with$\frac{x_i - \mu_i}{S_i}$(not applied to bias term$x_0).\n * Example: x_1 = \frac{\text{Size of house} - 1000}{2000}$,$x_2 = \frac{\text{No. of Bedrooms} - 2}{5}\n * *Standard Scaler (Standardization):*\n * x' = \frac{x - \mu}{\sigma}\n * where \mu$is the feature mean and$\sigma is the feature standard deviation.\n * *Min-Max Scaler (Normalization):*\n * x' = \frac{x - x_{\min}}{x_{\max} - x_{\min}}\n * where x_{\min}$is the feature minimum value and$x_{\max} is the feature maximum value.\n\n\n# Classification Problems and Logistic Regression\n\n* **Classification Definitions:**\n * *Binary Classification:* Target output y \in {0, 1}.\n * 0: Negative class (e.g., Benign tumor, Non-spam email)\n * 1: Positive class (e.g., Malignant tumor, Spam email)\n * *Multiclass Classification:* Target output y \in {0, 1, 2, 3, \dots}.\n\n* **Inadequacy of Linear Regression for Classification:**\n * Linear regression hypotheses can produce values greater than 1$or less than$0.\n * Linear models are highly sensitive to extreme outliers, shifting decision boundaries incorrectly.\n\n* **Logistic Regression Hypothesis:**\n * Requires output bounded within range: 0 \le h_{\theta}(x) \le 1\n * **Sigmoid / Logistic Function:**\n * g(z) = \frac{1}{1 + e^{-z}}\n * **Hypothesis Formulation:**\n * h_{\theta}(x) = g(\Theta^T X) = \frac{1}{1 + e^{-\Theta^T X}}\n * **Interpretation:** Estimated probability that y = 1$given input$x:\n * h_{\theta}(x) = P(y = 1 \mid x; \theta)\n * Example: For feature vector x = [1, \text{Tumor size}]^T$, if$h_{\theta}(x) = 0.7$, there is a$70\% probability that the tumor is malignant.\n\n* **Decision Boundary:**\n * Predict y = 1$if$h_{\theta}(x) \ge 0.5$(equivalent to$\Theta^T X \ge 0).\n * Predict y = 0$if$h_{\theta}(x) < 0.5$(equivalent to$\Theta^T X < 0).\n * *Worked Decision Boundary Example:*\n * Hypothesis: h_{\theta}(x) = g(\theta_0 + \theta_1 x_1 + \theta_2 x_2)\n * Given parameters: \theta_0 = -3$,$\theta_1 = 1$,$\theta_2 = 1\n * Predict y = 1$if$-3 + x_1 + x_2 \ge 0 \implies x_1 + x_2 \ge 3\n * Predict y = 0$if$x_1 + x_2 < 3\n * Decision Boundary line equation: x_1 + x_2 = 3\n\n* **Logistic Regression Cost Function (Log Loss / Cross-Entropy):**\n * Using squared error in logistic regression produces a non-convex cost surface with many local minima.\n * *Single-instance Cost Function:*\n * \text{Cost}(h_{\theta}(x), y) = -\log(h_{\theta}(x))$if$y = 1\n * \text{Cost}(h_{\theta}(x), y) = -\log(1 - h_{\theta}(x))$if$y = 0\n * *Combined Cost Function Formulation:*\n * J(\Theta) = \frac{1}{m} \sum_{i=1}^{m} \text{Cost}(h_{\theta}(x^{(i)}), y^{(i)})\n * J(\Theta) = -\frac{1}{m} \sum_{i=1}^{m} \left[ y^{(i)} \log(h_{\theta}(x^{(i)})) + (1 - y^{(i)}) \log(1 - h_{\theta}(x^{(i)})) \right]\n * Goal: \min_{\Theta} J(\Theta)\n\n* **Gradient Descent Optimization for Logistic Regression:**\n * Partial derivative: \frac{\partial}{\partial \theta_j} J(\Theta) = \frac{1}{m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)}) x_j^{(i)}\n * Simultaneous update for every j = 0, 1, \dots, n:\n * \theta_j := \theta_j - \alpha \frac{1}{m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)}) x_j^{(i)}\n * *Advanced Optimization Algorithms:* Conjugate Gradient, BFGS, and L-BFGS provide faster convergence without requiring manual learning rate selection.\n\n* **Multiclass Classification (One-vs-All / One-vs-Rest):**\n * Train a binary logistic regression classifier h_{\theta}^{(i)}(x)$for each class$i$to estimate$P(y = i \mid x; \theta).\n * To make predictions on a new input x$, evaluate all classifiers and select class$i$that maximizes$h_{\theta}^{(i)}(x).\n\n\n# Overfitting and Regularization Techniques\n\n* **The Overfitting Problem:**\n * *Underfitting (High Bias):* Model structure is too simple (e.g., fitting linear hypothesis \theta_0 + \theta_1 x to parabolic price trend).\n * *Just Right:* Model captures general trend accurately (e.g., quadratic hypothesis \theta_0 + \theta_1 x + \theta_2 x^2).\n * *Overfitting (High Variance):* Model includes excessive high-degree polynomial terms (e.g., \theta_0 + \theta_1 x + \theta_2 x^2 + \theta_3 x^3 + \theta_4 x^4$or complex decision boundary$\theta_0 + \theta_1 x_1 + \theta_2 x_2 + \theta_3 x_1^2 + \theta_4 x_2^2 + \theta_5 x_1 x_2 + \dots). The fit passes through every training point perfectly but fails to generalize to new, unseen data.\n\n* **Solutions to Overfitting:**\n 1. Reduce the number of features manually or via feature selection.\n 2. **Regularization:** Retain all features, but shrink parameter magnitudes \theta_j$.

    • Intuition: Adding massive penalization terms (e.g., $1000 \theta_3^2 + 1000 \theta_4^2$) to the cost function forces $\theta_3 \approx 0$ and $\theta_4 \approx 0$, simplifying the model hypothesis.

• Types of Regularization:

  • L2 Regularization (Ridge Regression):

    • $J(\Theta) = \text{Loss} + \frac{\lambda}{2m} \sum_{j=1}^{n} \theta_j^2$

  • L1 Regularization (Lasso Regression):

    • $J(\Theta) = \text{Loss} + \frac{\lambda}{m} \sum_{j=1}^{n} |\theta_j|$

  • Elastic Net Regularization:

    • Combines L1 and L2 penalties:

    • $J(\Theta) = \text{Loss} + \frac{\lambda_1}{m} \sum_{j=1}^{n} |\theta_j| + \frac{\lambda_2}{2m} \sum_{j=1}^{n} \theta_j^2$

• Linear Regression with Ridge Regularization:

  • Cost Function:

    • $J(\Theta) = \frac{1}{2m} \left( \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)})^2 + \lambda \sum_{j=1}^{n} \theta_j^2 \right)$

    • Where $\lambda$ is the regularization parameter.

  • Gradient Descent Updates (Repeat until convergence):

    • $\theta_0 := \theta_0 - \alpha \frac{1}{m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)}) x_0^{(i)}$

    • $\theta_j := \theta_j - \alpha \left( \frac{1}{m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)}) x_j^{(i)} + \frac{\lambda}{m} \theta_j \right)$ for $j \in \{1, 2, \dots, n\}$

• Logistic Regression with Ridge Regularization:

  • Cost Function:

    • $J(\Theta) = -\frac{1}{m} \sum_{i=1}^{m} \left[ y^{(i)} \log(h_{\theta}(x^{(i)})) + (1 - y^{(i)}) \log(1 - h_{\theta}(x^{(i)})) \right] + \frac{\lambda}{2m} \sum_{j=1}^{n} \theta_j^2$

  • Gradient Descent Updates (Repeat until convergence):

    • $\theta_0 := \theta_0 - \alpha \frac{1}{m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)}) x_0^{(i)}$

    • $\theta_j := \theta_j - \alpha \left( \frac{1}{m} \sum_{i=1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)}) x_j^{(i)} + \frac{\lambda}{m} \theta_j \right)$ for $j \in \{1, 2, \dots, n\}$

Recommended Academic References

• Book 1: Ethem Alpaydin, Introduction to Machine Learning, 3rd Edition.

• Book 2: Tom M. Mitchell, Machine Learning, McGraw-Hill.

• Online Course: Machine Learning course by Stanford University.