Linear Regression

Simple Linear Regression predicts a continuous value using one input feature by fitting a straight line: $$\hat{y}=b_0+b_{1}x$$ where:

• $b_0$ = intercept
• $b_1$ = slope
• $\hat{y}$ = predicted output

The goal is to find the line that minimizes the sum of squared errors: $$J(b_0,b_1)=\sum _{i=1}^n(y_i-{\hat{y}}_i{)}^2$$

Intuition

We want the “best” straight line through the data.

• If $b_1>0$, the line goes upward
• If $b_1<0$, the line goes downward
• $b_0$ tells where the line cuts the $y$-axis

For a dataset with one feature: $$X=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right],y=\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_n\end{array}\right]$$ we add a bias column of 1s: $$X_b=\left[\begin{array}{cc}1& x_1\\ 1& x_2\\ ⋮& ⋮\\ 1& x_n\end{array}\right]$$

Then the parameters are computed using the Normal Equation: $$\theta =(X_b^T{X}_b{)}^{-1}{X}_b^{T}y$$ where: $$\theta =\left[\begin{array}{c}{b}_0\\ b_1\end{array}\right]$$

Short and Clean Code

import numpy as np
import matplotlib.pyplot as plt

class SimpleLinearRegression:
    def __init__(self):
        self.intercept_ = 0.0
        self.coef_ = 0.0
        self.r2_ = 0.0

    def fit(self, X, y):
        X = np.asarray(X).reshape(-1, 1)
        y = np.asarray(y).reshape(-1, 1)

        Xb = np.c_[np.ones((len(X), 1)), X]
        theta = np.linalg.inv(Xb.T @ Xb) @ Xb.T @ y

        self.intercept_ = theta[0, 0]
        self.coef_ = theta[1, 0]

        y_pred = Xb @ theta
        ss_res = np.sum((y - y_pred) ** 2)
        ss_tot = np.sum((y - y.mean()) ** 2)
        self.r2_ = 1 - ss_res / ss_tot
        return self

    def predict(self, X):
        X = np.asarray(X).reshape(-1, 1)
        return self.intercept_ + self.coef_ * X

X = np.array([1,2,3,4,5,6,7,8,9,10])
y = np.array([2,4,5,4,5,7,8,9,10,12])

model = SimpleLinearRegression().fit(X, y)
y_pred = model.predict(X)

print("Intercept:", round(model.intercept_, 4))
print("Slope:", round(model.coef_, 4))
print("R^2:", round(model.r2_, 4))

plt.scatter(X, y, label="Data")
plt.plot(X, y_pred, label="Regression line")
plt.xlabel("X")
plt.ylabel("y")
plt.title("Simple Linear Regression")
plt.legend()
plt.show()

Output Meaning

From this code, the fitted line is approximately: $$\hat{y}=1.0667+1.0182x$$

So:

• intercept $\approx 1.0667$
• slope $\approx 1.0182$

This means:

• when $x=0$, predicted $y\approx 1.0667$
• for every increase of 1 in $x$, $y$ increases by about $1.0182$

The $R^2$ score is approximately: $$R^2\approx 0.9525$$ which means the model explains about 95.25% of the variance in the target.

Step-by-Step Algorithm

Step 1: Prepare the data

We start with:

X = np.array([1,2,3,4,5,6,7,8,9,10])
y = np.array([2,4,5,4,5,7,8,9,10,12])

Concept:

• $X$ is the input feature
• $y$ is the actual output

Dataset pairs: $$(1,2),(2,4),(3,5),(4,4),(5,5),(6,7),(7,8),(8,9),(9,10),(10,12)$$

Step 2: Add the bias column

To learn both intercept and slope together, we transform $X$ into: $$X_b=\left[\begin{array}{cc}1& 1\\ 1& 2\\ 1& 3\\ 1& 4\\ 1& 5\\ 1& 6\\ 1& 7\\ 1& 8\\ 1& 9\\ 1& 10\end{array}\right]$$

Code:

Xb = np.c_[np.ones((len(X), 1)), X.reshape(-1, 1)]

Concept:

• first column of 1s handles the intercept
• second column stores the feature values

Step 3: Compute parameters using the Normal Equation

Equation: $$\theta =(X_b^T{X}_b{)}^{-1}{X}_b^{T}y$$

Code:

theta = np.linalg.inv(Xb.T @ Xb) @ Xb.T @ y.reshape(-1, 1)

This gives: $$\theta =\left[\begin{array}{c}1.0667\\ 1.0182\end{array}\right]$$

So: $$b_0=1.0667,b_1=1.0182$$

Meaning: $$\hat{y}=1.0667+1.0182x$$

Step 4: Predict values

For each input, substitute into: $$\hat{y}=b_0+b_{1}x$$

Code:

y_pred = self.intercept_ + self.coef_ * X.reshape(-1, 1)

Let us compute a few predictions manually.

For $x=1$: $$\hat{y}=1.0667+1.0182(1)=2.0849$$

For $x=2$: $$\hat{y}=1.0667+1.0182(2)=3.1030$$

For $x=5$: $$\hat{y}=1.0667+1.0182(5)=6.1576$$

For $x=10$: $$\hat{y}=1.0667+1.0182(10)=11.2485$$

So the model predictions are approximately: $$[2.0849,3.1030,4.1212,5.1394,6.1576,7.1758,8.1939,9.2121,10.2303,11.2485]$$

Step 5: Measure performance using $R^2$

The coefficient of determination is: $$R^2=1-\frac{\sum (y-\hat{y}{)}^2}{\sum (y-\bar{y}{)}^2}$$

Where:

• $\sum (y-\hat{y}{)}^2$ = residual sum of squares
• $\sum (y-\bar{y}{)}^2$ = total sum of squares
• $\bar{y}$ = mean of actual $y$

Code:

ss_res = np.sum((y - y_pred) ** 2)
ss_tot = np.sum((y - y.mean()) ** 2)
self.r2_ = 1 - ss_res / ss_tot

For this dataset: $$R^2\approx 0.9525$$

Interpretation:

• close to 1 means strong fit
• close to 0 means poor fit

Code Explanation: Concept -> Equation -> Code

1. Store model parameters

Concept: We need to remember the learned intercept, slope, and model score.

Code:

class SimpleLinearRegression:
    def __init__(self):
        self.intercept_ = 0.0
        self.coef_ = 0.0
        self.r2_ = 0.0

Meaning:

• intercept_ stores $b_0$
• coef_ stores $b_1$
• r2_ stores $R^2$

2. Convert input into column form

Concept: Matrix equations require $X$ and $y$ in proper shapes.

Code:

X = np.asarray(X).reshape(-1, 1)
y = np.asarray(y).reshape(-1, 1)

Meaning:

• reshape(-1, 1) makes data a column vector

Example: $$X=\left[\begin{array}{c}1\\ 2\\ 3\\ ⋮\\ 10\end{array}\right]$$

3. Add the bias term

Concept: The intercept must be part of the matrix multiplication.

Equation: $$\hat{y}=X_b\theta$$

Code:

Xb = np.c_[np.ones((len(X), 1)), X]

This builds: $$X_b=\left[\begin{array}{cc}1& x_1\\ 1& x_2\\ ⋮& ⋮\\ 1& x_n\end{array}\right]$$

4. Learn the best-fit line

Concept: Choose parameters that minimize squared error.

Equation: $$\theta =(X_b^T{X}_b{)}^{-1}{X}_b^{T}y$$

Code:

theta = np.linalg.inv(Xb.T @ Xb) @ Xb.T @ y

This is the heart of the algorithm.

Then:

self.intercept_ = theta[0, 0]
self.coef_ = theta[1, 0]

This maps: $$\theta =\left[\begin{array}{c}{b}_0\\ b_1\end{array}\right]$$

5. Predict outputs

Concept: Once parameters are known, plug them into the line equation.

Equation: $$\hat{y}=b_0+b_{1}x$$

Code:

y_pred = Xb @ theta

or in predict():

return self.intercept_ + self.coef_ * X

Both do the same thing.

6. Evaluate model fit

Concept: Compare predictions with actual values.

Equation: $$S{S}_{res}=\sum (y-\hat{y}{)}^2$$ $$S{S}_{tot}=\sum (y-\bar{y}{)}^2$$ $$R^2=1-\frac{S{S}_{res}}{S{S}_{tot}}$$

Code:

ss_res = np.sum((y - y_pred) ** 2)
ss_tot = np.sum((y - y.mean()) ** 2)
self.r2_ = 1 - ss_res / ss_tot

Worked Example

Using: $$x=6$$ Prediction: $$\hat{y}=1.0667+1.0182(6)=7.1758$$

Actual value in dataset: $$y=7$$

Error: $$y-\hat{y}=7-7.1758=-0.1758$$

Squared error: $$(-0.1758{)}^2\approx 0.0309$$

This is how the model measures how far prediction is from truth.

Why This Algorithm Works

Simple Linear Regression assumes:

1. the relationship is approximately linear
2. one feature is enough to explain the target
3. the best line is the one with minimum squared error

By minimizing squared error, the algorithm finds a line that stays as close as possible to all points overall.

Final Summary

Simple Linear Regression learns: $$\hat{y}=b_0+b_{1}x$$ using: $$\theta =(X_b^T{X}_b{)}^{-1}{X}_b^{T}y$$

For this dataset, the learned model is: $$\hat{y}=1.0667+1.0182x$$ with: $$R^2\approx 0.9525$$

So the model fits the data well and captures a strong positive linear relationship.

Exam-Oriented Points

• Used for predicting a continuous value
• Works with one input feature
• Equation of model: $$\hat{y}=b_0+b_{1}x$$
• Parameters are found using the Normal Equation
• Performance is commonly measured with $R^2$
• Best when the relationship between feature and target is approximately linear

Very Short Revision

• Add bias column
• Compute parameters using Normal Equation
• Form regression line
• Predict output
• Evaluate using $R^2$

Formula: $$\theta =(X_b^T{X}_b{)}^{-1}{X}_b^{T}y$$ Model: $$\hat{y}=b_0+b_{1}x$$

Logistic Regression

Logistic Regression is a binary classification algorithm used when the output belongs to one of two classes: $$y\in \{0,1\}$$ It does not predict the class directly using a line. Instead, it predicts a probability using the sigmoid function, then converts that probability into class 0 or 1. The model is: $$z=w_1{x}_1+w_2{x}_2+\cdots +w_n{x}_n+b$$ $$\hat{y}=\sigma (z)=\frac{1}{1+e^{-z}}$$ where:

• $z$ = linear score
• $\sigma (z)$ = sigmoid function
• $\hat{y}$ = predicted probability that class is 1

If: $$\hat{y}\ge 0.5\Rightarrow \text{predict }1$$ $$\hat{y}<0.5\Rightarrow \text{predict }0$$

Main Idea

Linear Regression gives any real number as output, but classification needs a value between 0 and 1. So Logistic Regression first computes a linear combination: $$z=Xw+b$$ then applies the sigmoid: $$\sigma (z)=\frac{1}{1+e^{-z}}$$ This maps any real number into: $$(0,1)$$ So the output can be interpreted as a probability.

Short and Clean Code

import numpy as np
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

class LogisticRegressionScratch:
    def __init__(self, lr=0.1, epochs=1000):
        self.lr = lr
        self.epochs = epochs
        self.w = None
        self.b = 0.0
        self.loss_history = []

    def _sigmoid(self, z):
        z = np.clip(z, -500, 500)
        return 1 / (1 + np.exp(-z))

    def _loss(self, y, p):
        eps = 1e-9
        p = np.clip(p, eps, 1 - eps)
        return -np.mean(y * np.log(p) + (1 - y) * np.log(1 - p))

    def fit(self, X, y):
        X = np.asarray(X)
        y = np.asarray(y)
        m, n = X.shape
        self.w = np.zeros(n)

        for _ in range(self.epochs):
            z = X @ self.w + self.b
            p = self._sigmoid(z)

            dw = (X.T @ (p - y)) / m
            db = np.mean(p - y)

            self.w -= self.lr * dw
            self.b -= self.lr * db

            self.loss_history.append(self._loss(y, p))
        return self

    def predict_proba(self, X):
        X = np.asarray(X)
        return self._sigmoid(X @ self.w + self.b)

    def predict(self, X):
        return (self.predict_proba(X) >= 0.5).astype(int)

np.random.seed(42)
X = np.random.rand(200, 2) * 10
y = (X[:, 0] + X[:, 1] > 10).astype(int)

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

scaler = StandardScaler()
X_train = scaler.fit_transform(X_train)
X_test = scaler.transform(X_test)

model = LogisticRegressionScratch(lr=0.1, epochs=1000)
model.fit(X_train, y_train)

pred = model.predict(X_test)
acc = np.mean(pred == y_test)

print("Weights:", np.round(model.w, 4))
print("Bias:", round(model.b, 4))
print("Accuracy:", round(acc, 4))

plt.plot(model.loss_history)
plt.title("Loss Convergence")
plt.xlabel("Iteration")
plt.ylabel("Loss")
plt.grid(True)
plt.show()

What This Code Does

This example creates 2D points: $$X=[x_1,x_2]$$ and labels them using: $$y=\{\begin{array}{ll}1,& x_1+x_2>10\\ 0,& x_1+x_2\le 10\end{array}$$ So the true decision boundary is: $$x_1+x_2=10$$ This is a binary classification problem.

Step-by-Step Algorithm

Step 1: Create the dataset

Code:

np.random.seed(42)
X = np.random.rand(200, 2) * 10
y = (X[:, 0] + X[:, 1] > 10).astype(int)

Concept:

• X contains 200 samples
• each sample has 2 features: $x_1,x_2$
• class label depends on whether the sum is greater than 10

Equation: $$y=\{\begin{array}{ll}1,& x_1+x_2>10\\ 0,& \text{otherwise}\end{array}$$

Meaning:

• points above the line belong to class 1
• points below the line belong to class 0

Step 2: Split into train and test sets

Code:

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

Concept:

• training data is used to learn parameters
• test data is used to check performance on unseen data

Here:

• 80% for training
• 20% for testing

Step 3: Standardize features

Code:

scaler = StandardScaler()
X_train = scaler.fit_transform(X_train)
X_test = scaler.transform(X_test)

Concept: Gradient descent works better when features are on similar scales.

Standardization formula: $$x_{\text{scaled}}=\frac{x-\mu }{\sigma }$$ where:

• $\mu$ = mean of the feature
• $\sigma$ = standard deviation

Why it helps:

• faster convergence
• more stable updates
• one feature does not dominate another due to large magnitude

Step 4: Compute the linear score

For each sample, Logistic Regression first computes: $$z=w_1{x}_1+w_2{x}_2+\cdots +w_n{x}_n+b$$ In vector form: $$z=Xw+b$$

Code:

z = X @ self.w + self.b

Concept: This is the same linear part used in linear models. But here it is not the final output. It is only the input to the sigmoid function.

Step 5: Apply sigmoid to get probability

Equation: $$\sigma (z)=\frac{1}{1+e^{-z}}$$

Code:

p = self._sigmoid(z)

Concept: The sigmoid compresses any real number into a value between 0 and 1.

Examples:

• if $z=0$: $$\sigma (0)=\frac{1}{1+e^0}=0.5$$
• if $z$ is large positive, probability is close to 1
• if $z$ is large negative, probability is close to 0

So: $$p=P(y=1\mid X)$$

Step 6: Measure error using cross-entropy loss

For Logistic Regression, we do not use mean squared error. We use cross-entropy loss: $$J(w,b)=-\frac{1}{m}\sum _{i=1}^m\left[y_i\log ({\hat{y}}_i)+(1-y_i)\log (1-{\hat{y}}_i)\right]$$

Code:

def _loss(self, y, p):
    eps = 1e-9
    p = np.clip(p, eps, 1 - eps)
    return -np.mean(y * np.log(p) + (1 - y) * np.log(1 - p))

Concept:

• if actual class is 1, we want $\hat{y}$ close to 1
• if actual class is 0, we want $\hat{y}$ close to 0
• wrong confident predictions are penalized heavily

Why clipping is used:

• log(0) is undefined
• so probabilities are clipped slightly away from 0 and 1

Step 7: Compute gradients

To reduce loss, we update weights and bias using gradient descent.

Gradient formulas: $$\frac{\partial J}{\partial w}=\frac{1}{m}{X}^T(\hat{y}-y)$$ $$\frac{\partial J}{\partial b}=\frac{1}{m}\sum (\hat{y}-y)$$

Code:

dw = (X.T @ (p - y)) / m
db = np.mean(p - y)

Concept:

• dw tells how weights should change
• db tells how bias should change
• if prediction is too large, parameters are pushed downward
• if prediction is too small, parameters are pushed upward

Step 8: Update parameters

Gradient descent update rule: $$w:=w-\alpha \frac{\partial J}{\partial w}$$ $$b:=b-\alpha \frac{\partial J}{\partial b}$$ where $\alpha$ is the learning rate.

Code:

self.w -= self.lr * dw
self.b -= self.lr * db

Concept:

• move parameters in the direction that reduces loss
• repeat many times until learning stabilizes

Step 9: Convert probabilities to classes

After training, predicted probability is converted to class label.

Rule: $$\hat{y}=\{\begin{array}{ll}1,& p\ge 0.5\\ 0,& p<0.5\end{array}$$

Code:

return (self.predict_proba(X) >= 0.5).astype(int)

Concept:

• probabilities are continuous
• classification needs discrete labels

Step 10: Measure accuracy

Code:

pred = model.predict(X_test)
acc = np.mean(pred == y_test)

Equation: $$\text{Accuracy}=\frac{\text{Number of correct predictions}}{\text{Total predictions}}$$

Concept: Accuracy tells what fraction of test samples were classified correctly.

Concept -> Equation -> Code Mapping

1. Model parameters

Concept: The model must learn weights and bias.

Equation: $$z=Xw+b$$

Code:

self.w = np.zeros(n)
self.b = 0.0

Meaning:

• start with all weights as 0
• start with bias as 0

2. Probability model

Concept: Turn linear score into probability.

Equation: $$\hat{y}=\sigma (z)=\frac{1}{1+e^{-z}}$$

Code:

def _sigmoid(self, z):
    z = np.clip(z, -500, 500)
    return 1 / (1 + np.exp(-z))

Why clip:

• avoids overflow for very large positive or negative values

3. Forward pass

Concept: Compute predictions from current parameters.

Equation: $$z=Xw+b$$ $$p=\sigma (z)$$

Code:

z = X @ self.w + self.b
p = self._sigmoid(z)

Meaning:

• z = raw score
• p = predicted probability

4. Loss calculation

Concept: See how wrong the predictions are.

Equation: $$J(w,b)=-\frac{1}{m}\sum \left[y\log (p)+(1-y)\log (1-p)\right]$$

Code:

self.loss_history.append(self._loss(y, p))

Meaning:

• each iteration stores loss
• useful for checking whether training is improving

5. Backward pass

Concept: Find how parameters affect the loss.

Equation: $$\frac{\partial J}{\partial w}=\frac{1}{m}{X}^T(p-y)$$ $$\frac{\partial J}{\partial b}=\frac{1}{m}\sum (p-y)$$

Code:

dw = (X.T @ (p - y)) / m
db = np.mean(p - y)

Meaning: These gradients guide the update step.

6. Learning step

Concept: Improve the model gradually.

Equation: $$w:=w-\alpha dw$$ $$b:=b-\alpha db$$

Code:

self.w -= self.lr * dw
self.b -= self.lr * db

Meaning: Repeated updates make the model better at classification.

Worked Example on One Sample

Suppose after some training, for one sample: $$x=[0.8,1.2]$$ and the model has: $$w=[1.5,1.0],b=-0.4$$

Step 1: Compute score

$$z=(1.5)(0.8)+(1.0)(1.2)-0.4$$ $$z=1.2+1.2-0.4=2.0$$

Step 2: Apply sigmoid

$$\hat{y}=\sigma (2)=\frac{1}{1+e^{-2}}$$ $$\hat{y}\approx 0.8808$$

Step 3: Classify

Since: $$0.8808>0.5$$ prediction is: $$1$$

So this sample is classified as class 1.

Why Logistic Regression Works

The model learns a boundary where the probability changes from class 0 to class 1. For two features, the decision boundary is: $$w_1{x}_1+w_2{x}_2+b=0$$ Because: $$\sigma (z)=0.5\text{ when }z=0$$ So:

• if $z>0$, class tends toward 1
• if $z<0$, class tends toward 0

This creates a linear decision boundary.

For your dataset, true labels come from: $$x_1+x_2>10$$ So Logistic Regression is a good fit because the classes are separable by a line.

What the Loss Curve Means

Code:

plt.plot(model.loss_history)
plt.title("Loss Convergence")
plt.xlabel("Iteration")
plt.ylabel("Loss")
plt.grid(True)
plt.show()

Concept:

• at the beginning, loss is high
• during learning, loss should decrease
• a downward curve means gradient descent is working

If the curve:

• decreases smoothly -> learning is stable
• oscillates wildly -> learning rate may be too high
• decreases very slowly -> learning rate may be too low

Practical Notes

1. Feature scaling matters

Because Logistic Regression uses gradient descent, features with large values can slow down convergence. That is why: $$x_{\text{scaled}}=\frac{x-\mu }{\sigma }$$ is important.

2. Learning rate matters

If learning rate $\alpha$ is:

• too high -> training may diverge
• too low -> training becomes very slow

Typical starting values: $$0.01\text{ to }0.1$$

3. Linear boundary limitation

Logistic Regression assumes the boundary is linear: $$w_1{x}_1+w_2{x}_2+\cdots +w_n{x}_n+b=0$$ If data is non-linear, you may need:

• feature engineering
• polynomial features
• another model

4. Correlated features can cause issues

If features are strongly correlated, learning may become unstable. This is called multicollinearity.

Exam-Oriented Summary

Definition

Logistic Regression is a supervised learning algorithm used for binary classification.

Model

$$z=Xw+b$$ $$\hat{y}=\frac{1}{1+e^{-z}}$$

Decision Rule

$$\hat{y}\ge 0.5\Rightarrow 1$$ $$\hat{y}<0.5\Rightarrow 0$$

Loss Function

$$J(w,b)=-\frac{1}{m}\sum \left[y\log (\hat{y})+(1-y)\log (1-\hat{y})\right]$$

Gradient Descent Updates

$$w:=w-\alpha \frac{1}{m}{X}^T(\hat{y}-y)$$ $$b:=b-\alpha \frac{1}{m}\sum (\hat{y}-y)$$

Uses

• spam detection
• disease prediction
• pass/fail prediction
• yes/no classification tasks

Very Short Revision

• Compute linear score: $$z=Xw+b$$
• Apply sigmoid: $$\hat{y}=\frac{1}{1+e^{-z}}$$
• Compute cross-entropy loss
• Update weights and bias using gradient descent
• Convert probability to class using threshold 0.5

Final Takeaway

Logistic Regression is a simple but powerful classification algorithm. It learns a linear decision boundary, uses sigmoid to output probabilities, and improves itself by minimizing cross-entropy loss using gradient descent. For your example, it works well because the classes are generated by a rule that is approximately linearly separable.

Principal Component Analysis (PCA)

PCA is a dimensionality reduction algorithm. It creates new features called principal components that keep as much information as possible from the original dataset. The main idea is:

• find directions where the data varies the most
• rank those directions
• keep only the most important ones

If the original data has $d$ features, PCA can produce up to $d$ principal components.

Why PCA is Needed

High-dimensional data causes problems such as:

• harder visualization
• more computation
• more difficult learning
• curse of dimensionality

PCA solves this by projecting the data onto fewer dimensions while preserving maximum variance.

Core Idea

Suppose the data matrix is: $$X\in {\mathbb{R}}^{n\times d}$$ where:

• $n$ = number of samples
• $d$ = number of features

PCA finds a new set of orthogonal directions: $$u_1,u_2,\dots ,u_d$$ such that:

• $u_1$ captures the maximum variance
• $u_2$ captures the next maximum variance
• and so on

These directions are the eigenvectors of the covariance matrix. Their importance is given by the eigenvalues.

Main Equations

1. Standardization

Each feature is standardized using Z-score: $$x^{\prime }=\frac{x-\mu }{\sigma }$$

2. Covariance matrix

For centered data: $$C=\frac{1}{n}{X}^{T}X$$

3. Eigen decomposition

$$Cu=\lambda u$$ where:

• $u$ = eigenvector
• $\lambda$ = eigenvalue

4. Projection

If $W_k$ contains the top $k$ principal components, then: $$X_{\text{proj}}=X{W}_k$$

Intuition

Each principal component is a direction in feature space. If data spreads a lot along a direction, that direction contains a lot of information. So PCA keeps the directions with the largest variance.

That is why PCA chooses eigenvectors with the largest eigenvalues.

Short and Clean Code

import numpy as np
from sklearn.datasets import load_iris
from sklearn.decomposition import PCA as SklearnPCA

class PCAFromScratch:
    def __init__(self, n_components):
        self.n_components = n_components
        self.mean_ = None
        self.std_ = None
        self.components_ = None
        self.eigenvalues_ = None
        self.explained_variance_ratio_ = None

    def fit(self, X):
        X = np.asarray(X, dtype=float)

        self.mean_ = X.mean(axis=0)
        self.std_ = X.std(axis=0)
        Xs = (X - self.mean_) / self.std_

        C = (Xs.T @ Xs) / len(Xs)
        eigenvalues, eigenvectors = np.linalg.eigh(C)

        order = np.argsort(eigenvalues)[::-1]
        eigenvalues = eigenvalues[order]
        eigenvectors = eigenvectors[:, order]

        self.eigenvalues_ = eigenvalues[:self.n_components]
        self.components_ = eigenvectors[:, :self.n_components]
        self.explained_variance_ratio_ = eigenvalues / eigenvalues.sum()
        return self

    def transform(self, X):
        X = np.asarray(X, dtype=float)
        Xs = (X - self.mean_) / self.std_
        return Xs @ self.components_

    def fit_transform(self, X):
        self.fit(X)
        return self.transform(X)

iris = load_iris()
X = iris.data

pca = PCAFromScratch(n_components=2)
X_proj = pca.fit_transform(X)

print("Top eigenvalues:", np.round(pca.eigenvalues_, 4))
print("Principal components:\n", np.round(pca.components_, 4))
print("Explained variance ratio:", np.round(pca.explained_variance_ratio_, 4))

sk_pca = SklearnPCA(n_components=2)
X_sk = sk_pca.fit_transform((X - X.mean(axis=0)) / X.std(axis=0))

print("Sklearn components:\n", np.round(sk_pca.components_.T, 4))

What This Code Does

This code:

1. loads the Iris dataset
2. standardizes all features
3. computes the covariance matrix
4. finds eigenvalues and eigenvectors
5. sorts them from largest to smallest
6. selects the top n_components
7. projects the original data onto those components

So 4-dimensional Iris data becomes 2-dimensional.

Dataset

The Iris dataset has:

• 150 samples
• 4 features
• 3 flower classes

The four features are:

• sepal length
• sepal width
• petal length
• petal width

PCA uses only the feature matrix: $$X\in {\mathbb{R}}^{150\times 4}$$

Since PCA is unsupervised, labels are not needed.

Step-by-Step Algorithm

Step 1: Standardize the dataset

PCA is sensitive to scale. If one feature has larger values, it can dominate the variance.

So each column is standardized: $$x^{\prime }=\frac{x-\mu }{\sigma }$$

Code:

self.mean_ = X.mean(axis=0)
self.std_ = X.std(axis=0)
Xs = (X - self.mean_) / self.std_

Concept:

• subtract column mean
• divide by column standard deviation
• now every feature has roughly comparable scale

Why important:

• PCA is variance-based
• variance depends on feature scale
• standardization ensures fairness among features

Step 2: Compute covariance matrix

The covariance matrix measures how features vary together.

Equation: $$C=\frac{1}{n}{X}_s^T{X}_s$$

Code:

C = (Xs.T @ Xs) / len(Xs)

Concept:

• diagonal entries = variance of each standardized feature
• off-diagonal entries = covariance between pairs of features

For Iris: $$C\in {\mathbb{R}}^{4\times 4}$$

Because there are 4 original features.

Step 3: Find eigenvalues and eigenvectors

PCA solves: $$Cu=\lambda u$$

Code:

eigenvalues, eigenvectors = np.linalg.eigh(C)

Concept:

• each eigenvector gives a direction
• each eigenvalue tells how much variance is captured in that direction

Why eigh and not eig:

• covariance matrix is symmetric
• np.linalg.eigh is better for symmetric matrices

Interpretation:

• large eigenvalue $\Rightarrow$ important component
• small eigenvalue $\Rightarrow$ less important component

Step 4: Sort eigenvalues and eigenvectors

The most useful components are the ones with the largest eigenvalues.

Code:

order = np.argsort(eigenvalues)[::-1]
eigenvalues = eigenvalues[order]
eigenvectors = eigenvectors[:, order]

Concept:

• argsort sorts indices
• [::-1] reverses order to descending
• now the first column of eigenvectors is the first principal component

Step 5: Select top principal components

If we want only $k$ components: $$W_k=[u_1{u}_2\dots u_k]$$

Code:

self.eigenvalues_ = eigenvalues[:self.n_components]
self.components_ = eigenvectors[:, :self.n_components]

Concept:

• keep only the dominant directions
• discard weaker directions
• dimension reduces from $d$ to $k$

For example:

• original data: 4 features
• choose 2 components
• reduced data: 2 features

Step 6: Project data onto the new space

Projection formula: $$X_{\text{proj}}=X_s{W}_k$$

Code:

return Xs @ self.components_

Concept:

• each sample is re-expressed in terms of principal components
• this gives lower-dimensional data
• information loss is minimized as much as possible for the chosen number of components

If: $$X_s\in {\mathbb{R}}^{150\times 4},W_2\in {\mathbb{R}}^{4\times 2}$$ then: $$X_{\text{proj}}\in {\mathbb{R}}^{150\times 2}$$

Concept -> Equation -> Code Mapping

1. Equalize feature scales

Concept: All features should contribute fairly.

Equation: $$x^{\prime }=\frac{x-\mu }{\sigma }$$

Code:

self.mean_ = X.mean(axis=0)
self.std_ = X.std(axis=0)
Xs = (X - self.mean_) / self.std_

2. Measure variance structure

Concept: We need a matrix that summarizes how features vary together.

Equation: $$C=\frac{1}{n}{X}_s^T{X}_s$$

Code:

C = (Xs.T @ Xs) / len(Xs)

3. Find important directions

Concept: The best projection directions are the eigenvectors of the covariance matrix.

Equation: $$Cu=\lambda u$$

Code:

eigenvalues, eigenvectors = np.linalg.eigh(C)

4. Rank the directions

Concept: Directions with larger variance are more useful.

Equation: $${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_d$$

Code:

order = np.argsort(eigenvalues)[::-1]
eigenvalues = eigenvalues[order]
eigenvectors = eigenvectors[:, order]

5. Keep only the top directions

Concept: Dimensionality reduction means retaining only the most informative directions.

Equation: $$W_k=[u_1{u}_2\dots u_k]$$

Code:

self.components_ = eigenvectors[:, :self.n_components]

6. Project data

Concept: Convert old features into principal component coordinates.

Equation: $$X_{\text{proj}}=X_s{W}_k$$

Code:

return Xs @ self.components_

Why Eigenvectors and Eigenvalues Appear

PCA wants to maximize the variance of projected data. If we project onto a unit vector $u$, projected variance is: $$\text{Var}(Xu)=u^{T}Cu$$ subject to: $$u^{T}u=1$$

This is an optimization problem. Using Lagrange multipliers: $$\mathcal{L}(u,\lambda )=u^{T}Cu-\lambda (u^{T}u-1)$$ Taking derivative and setting to zero gives: $$Cu=\lambda u$$

So:

• the best directions are eigenvectors of $C$
• the amount of retained variance is given by eigenvalues

This is the mathematical reason behind PCA.

Why the Largest Eigenvalue Matters

The projected variance along direction $u$ is: $$u^{T}Cu$$ For an eigenvector: $$Cu=\lambda u$$ So: $$u^{T}Cu=u^T(\lambda u)=\lambda u^{T}u$$ Since: $$u^{T}u=1$$ we get: $$u^{T}Cu=\lambda$$

Therefore:

• projected variance equals the eigenvalue
• maximizing variance means choosing the largest eigenvalue

That is why PCA selects top eigenvalues first.

Explained Variance Ratio

A useful quantity is: $${\text{Explained Variance Ratio}}_i=\frac{{\lambda }_i}{{\sum }_j{\lambda }_j}$$

Code:

self.explained_variance_ratio_ = eigenvalues / eigenvalues.sum()

Concept: This tells how much total information each principal component retains.

Example interpretation:

• PC1 = 72%
• PC2 = 23%
• then first two PCs keep 95% of the total variance

This helps decide how many components to keep.

Worked Mini Example

Suppose after covariance computation, eigenvalues are: $$[2.91,0.92,0.15,0.02]$$

Then:

• first principal component captures the most variance
• second captures the next most
• third and fourth contribute little

Total variance: $$2.91+0.92+0.15+0.02=4.00$$

Explained variance ratios: $$\frac{2.91}{4}=0.7275$$ $$\frac{0.92}{4}=0.23$$ $$\frac{0.15}{4}=0.0375$$ $$\frac{0.02}{4}=0.005$$

So:

• PC1 keeps about 72.75%
• PC2 keeps about 23%
• first two together keep about 95.75%

This means reducing from 4D to 2D is very reasonable.

Understanding the Components Matrix

If the selected components are: $$W_2=\left[\begin{array}{cc}0.52& -0.27\\ -0.26& -0.92\\ 0.58& -0.03\\ 0.56& -0.27\end{array}\right]$$ then:

• first column = first principal component
• second column = second principal component

Each column shows how the original features combine to form the new axis.

For example, first component: $$P{C}_1=0.52x_1-0.26x_2+0.58x_3+0.56x_4$$

So a principal component is a linear combination of original features.

Comparing with Scikit-Learn

Code:

sk_pca = SklearnPCA(n_components=2)
X_sk = sk_pca.fit_transform((X - X.mean(axis=0)) / X.std(axis=0))
print(np.round(sk_pca.components_.T, 4))

Concept: This checks whether the scratch implementation gives similar principal components.

Important note: Principal components may differ by sign. That means if one library gives: $$u$$ another may give: $$-u$$ This is still correct because both represent the same direction.

So when comparing PCA outputs, sign flips are normal.

Why PCA Works

PCA works because:

1. it identifies directions of maximum spread
2. those directions preserve the most information
3. the directions are orthogonal, so they do not duplicate information
4. low-variance directions can often be removed with minimal information loss

So PCA compresses data while keeping the most useful structure.

Limitations

1. PCA is linear

PCA only finds linear combinations of features. If structure is highly non-linear, PCA may not capture it well.

2. PCA is sensitive to scale

Without standardization, large-scale features dominate.

3. Components may be hard to interpret

The new axes are combinations of original features, so they may not be as interpretable as raw columns.

4. Variance does not always mean usefulness

PCA keeps directions with high variance, but high variance does not always mean high predictive importance for a target variable.

Exam-Oriented Summary

Definition

PCA is an unsupervised dimensionality reduction technique that transforms correlated features into orthogonal principal components.

Goal

Reduce the number of features while retaining maximum variance.

Steps

1. standardize data
2. compute covariance matrix
3. find eigenvalues and eigenvectors
4. sort them in descending order
5. select top $k$ components
6. project data onto them

Important Equations

Standardization: $$x^{\prime }=\frac{x-\mu }{\sigma }$$ Covariance: $$C=\frac{1}{n}{X}_s^T{X}_s$$ Eigen equation: $$Cu=\lambda u$$ Projection: $$X_{\text{proj}}=X_s{W}_k$$ Explained variance ratio: $$\frac{{\lambda }_i}{{\sum }_j{\lambda }_j}$$

Interpretation

• eigenvectors = directions of principal components
• eigenvalues = variance captured by those directions
• larger eigenvalue = more important component

Very Short Revision

PCA reduces dimensions by:

• standardizing data
• computing covariance matrix
• finding eigenvectors/eigenvalues
• sorting by largest eigenvalue
• keeping top components
• projecting data onto them

Main idea: $$\text{keep directions with maximum variance}$$

Final Takeaway

PCA transforms high-dimensional data into a lower-dimensional form by finding the most informative orthogonal directions. These directions are the eigenvectors of the covariance matrix, and their importance is measured by eigenvalues. The larger the eigenvalue, the more variance that principal component preserves, so the better it is for dimensionality reduction.

K-Nearest Neighbor

KNN is an instance-based or lazy learning algorithm. It does not learn an explicit equation during training. Instead, it:

• stores the training data
• waits until a new test point comes
• finds the nearest stored examples
• predicts using those neighbors

There are two common versions:

• KNN Classification -> predict the most common class
• KNN Regression -> predict the mean of neighbor target values

Main Idea

Each sample is a point in $n$-dimensional space: $$x=⟨x_1,x_2,\dots ,x_n⟩$$ To predict for a new point, KNN measures the distance from that point to all training points.

The most common distance used is Euclidean distance: $$d(x^{(a)},x^{(b)})=\sqrt{\sum _{j=1}^n(x_j^{(a)}-x_j^{(b)}{)}^2}$$

Then:

• in classification, choose the majority class among the nearest $K$ neighbors
• in regression, choose the average target among the nearest $K$ neighbors

Part A: KNN Classification

What It Does

Given a new test point:

1. compute its distance to every training point
2. sort distances
3. pick the nearest $K$
4. return the majority class

So the prediction rule is: $$\hat{y}=\text{mode of the }K\text{ nearest labels}$$

Short and Clean KNN Classification Code

import numpy as np
from collections import Counter

class KNNClassifier:
    def __init__(self, k=3):
        self.k = k
        self.X_train = None
        self.y_train = None

    def fit(self, X, y):
        self.X_train = np.asarray(X, dtype=float)
        self.y_train = np.asarray(y)

    def _distance(self, a, b):
        return np.sqrt(np.sum((a - b) ** 2))

    def _predict_one(self, x):
        distances = [self._distance(x, x_train) for x_train in self.X_train]
        k_idx = np.argsort(distances)[:self.k]
        k_labels = self.y_train[k_idx]
        return Counter(k_labels).most_common(1)[0][0]

    def predict(self, X):
        X = np.asarray(X, dtype=float)
        return np.array([self._predict_one(x) for x in X])

X_train = np.array([
    [1, 1],
    [2, 1],
    [4, 3],
    [5, 4],
    [6, 5]
], dtype=float)

y_train = np.array([0, 0, 1, 1, 1])

X_test = np.array([
    [3, 2],
    [5, 5]
], dtype=float)

clf = KNNClassifier(k=3)
clf.fit(X_train, y_train)
pred = clf.predict(X_test)

print("Predictions:", pred)

Small Classification Example

Training data: $$(1,1)\to 0,(2,1)\to 0,(4,3)\to 1,(5,4)\to 1,(6,5)\to 1$$

Test point: $$x_t=(3,2)$$

Take: $$K=3$$

Solving the Classification Example Step by Step

We compute distance from $(3,2)$ to every training point.

Distance to $(1,1)$

$$d=\sqrt{(3-1{)}^2+(2-1{)}^2}=\sqrt{4+1}=\sqrt{5}\approx 2.236$$

Distance to $(2,1)$

$$d=\sqrt{(3-2{)}^2+(2-1{)}^2}=\sqrt{1+1}=\sqrt{2}\approx 1.414$$

Distance to $(4,3)$

$$d=\sqrt{(3-4{)}^2+(2-3{)}^2}=\sqrt{1+1}=\sqrt{2}\approx 1.414$$

Distance to $(5,4)$

$$d=\sqrt{(3-5{)}^2+(2-4{)}^2}=\sqrt{4+4}=\sqrt{8}\approx 2.828$$

Distance to $(6,5)$

$$d=\sqrt{(3-6{)}^2+(2-5{)}^2}=\sqrt{9+9}=\sqrt{18}\approx 4.243$$

Now sort the distances:

Nearest 3 labels: $$[0,1,0]$$

Majority class: $$0$$

So: $$\hat{y}=0$$

That is exactly how KNN classification works.

KNN Classification Algorithm

Step 1: Store training data

Unlike linear models, KNN does not compute weights during training.

Code:

def fit(self, X, y):
    self.X_train = np.asarray(X, dtype=float)
    self.y_train = np.asarray(y)

Concept: Training in KNN simply means memorizing the dataset.

Step 2: Compute distance

Equation: $$d(x,x_i)=\sqrt{\sum _{j=1}^n(x_j-x_{ij}{)}^2}$$

Code:

def _distance(self, a, b):
    return np.sqrt(np.sum((a - b) ** 2))

Concept: This measures how close a training sample is to the test sample.

Smaller distance means more similar.

Step 3: Rank neighbors

Code:

distances = [self._distance(x, x_train) for x_train in self.X_train]
k_idx = np.argsort(distances)[:self.k]

Concept:

• compute all distances
• sort them
• keep the indices of the nearest $K$

Step 4: Vote by majority

Code:

k_labels = self.y_train[k_idx]
return Counter(k_labels).most_common(1)[0][0]

Concept: Among the nearest neighbors, whichever class occurs most is chosen.

Equation: $$\hat{y}=\text{mode}(y_{(1)},y_{(2)},\dots ,y_{(K)})$$

Concept -> Equation -> Code Mapping for Classification

1. Represent samples as points

Concept: Each row is a point in feature space.

Equation: $$x=⟨x_1,x_2,\dots ,x_n⟩$$

Code:

self.X_train = np.asarray(X, dtype=float)

2. Measure closeness

Concept: Similarity is measured using Euclidean distance.

Equation: $$d(x^{(a)},x^{(b)})=\sqrt{\sum _{j=1}^n(x_j^{(a)}-x_j^{(b)}{)}^2}$$

Code:

def _distance(self, a, b):
    return np.sqrt(np.sum((a - b) ** 2))

3. Select nearest neighbors

Concept: Prediction depends only on nearby training samples.

Code:

k_idx = np.argsort(distances)[:self.k]

4. Use majority vote

Concept: Classification chooses the most frequent class.

Equation: $$\hat{y}=\mathrm{mode}(k\text{ nearest labels})$$

Code:

return Counter(k_labels).most_common(1)[0][0]

Why KNN Classification Works

The assumption is:

points that are close in feature space tend to have the same class

So instead of learning a global rule, KNN makes a local decision around the test point.

That is why it is called instance-based learning.

Part B: KNN Regression

What It Does

KNN regression follows the same steps as classification:

1. compute distance to all training points
2. choose the nearest $K$
3. average their target values

Prediction rule: $$\hat{y}=\frac{1}{K}\sum _{i=1}^K{y}_{(i)}$$ where $y_{(i)}$ are the target values of the nearest $K$ neighbors.

Short and Clean KNN Regression Code

import numpy as np

class KNNRegressor:
    def __init__(self, k=3):
        self.k = k
        self.X_train = None
        self.y_train = None

    def fit(self, X, y):
        self.X_train = np.asarray(X, dtype=float)
        self.y_train = np.asarray(y, dtype=float)

    def _distance(self, a, b):
        return np.sqrt(np.sum((a - b) ** 2))

    def _predict_one(self, x):
        distances = [self._distance(x, x_train) for x_train in self.X_train]
        k_idx = np.argsort(distances)[:self.k]
        k_values = self.y_train[k_idx]
        return np.mean(k_values)

    def predict(self, X):
        X = np.asarray(X, dtype=float)
        return np.array([self._predict_one(x) for x in X])

X_train = np.array([[1], [2], [3], [6], [7]], dtype=float)
y_train = np.array([30000, 35000, 40000, 70000, 75000], dtype=float)

X_test = np.array([[4]], dtype=float)

reg = KNNRegressor(k=3)
reg.fit(X_train, y_train)
pred = reg.predict(X_test)

print("Prediction:", pred)

Small Regression Example

Suppose training data is:

Test point: $$x_t=4$$

Take: $$K=3$$

Solving the Regression Example Step by Step

We compute the distance from 4 to each training point.

Distance to 1

$$d=|4-1|=3$$

Distance to 2

$$d=|4-2|=2$$

Distance to 3

$$d=|4-3|=1$$

Distance to 6

$$d=|4-6|=2$$

Distance to 7

$$d=|4-7|=3$$

Sorted distances:

Nearest 3 target values: $$[40000,35000,70000]$$

Prediction is their mean: $$\hat{y}=\frac{40000+35000+70000}{3}$$ $$\hat{y}=\frac{145000}{3}\approx 48333.33$$

So the predicted salary is: $$48333.33$$

KNN Regression Algorithm

Step 1: Store training data

Code:

def fit(self, X, y):
    self.X_train = np.asarray(X, dtype=float)
    self.y_train = np.asarray(y, dtype=float)

Concept: Just store examples and target values.

Step 2: Compute all distances

Equation: $$d(x,x_i)=\sqrt{\sum _{j=1}^n(x_j-x_{ij}{)}^2}$$

Code:

distances = [self._distance(x, x_train) for x_train in self.X_train]

Concept: Measure how close the new point is to all training samples.

Step 3: Pick nearest $K$

Code:

k_idx = np.argsort(distances)[:self.k]

Concept: Keep the closest $K$ neighbors only.

Step 4: Average their target values

Equation: $$\hat{y}=\frac{1}{K}\sum _{i=1}^K{y}_{(i)}$$

Code:

k_values = self.y_train[k_idx]
return np.mean(k_values)

Concept: Regression prediction is the average of nearby outputs.

Concept -> Equation -> Code Mapping for Regression

1. Use the same distance idea

Concept: Near points should have similar target values.

Equation: $$d(x^{(a)},x^{(b)})=\sqrt{\sum _{j=1}^n(x_j^{(a)}-x_j^{(b)}{)}^2}$$

Code:

def _distance(self, a, b):
    return np.sqrt(np.sum((a - b) ** 2))

2. Find local neighborhood

Concept: Prediction uses local samples rather than a global fitted line.

Code:

k_idx = np.argsort(distances)[:self.k]

3. Average local outputs

Concept: Regression uses the mean of neighbor target values.

Equation: $$\hat{y}=\frac{1}{K}\sum _{i=1}^K{y}_{(i)}$$

Code:

return np.mean(k_values)

KNN Classification vs KNN Regression

Unified Intuition

KNN does not learn a formula like: $$y=mx+b$$ or: $$\hat{y}=\sigma (wx+b)$$

Instead, it says:

for this new point, let me look around nearby training points and decide locally

So every test sample gets its own local prediction rule.

That is why KNN is called:

• lazy learning
• instance-based learning

Choosing the Value of $K$

The value of $K$ controls smoothness.

Small $K$

• sensitive to noise
• more flexible
• may overfit

Large $K$

• smoother decision
• may underfit
• local details may be lost

A common rough idea: $$K\approx \sqrt{m}$$ where $m$ is the number of training samples

But in practice, $K$ is usually chosen using validation.

Why Feature Scaling Matters

KNN depends entirely on distance. So features with larger numeric ranges dominate the distance.

Example:

• Age may range from 20 to 80
• Glucose may range from 0 to 200

Then Glucose can dominate Euclidean distance.

So scaling is often important: $$x^{\prime }=\frac{x-\mu }{\sigma }$$

Without scaling, nearest neighbors may be misleading.

Time Cost of KNN

KNN is cheap during training but expensive during prediction.

Training

• just store the data

Prediction

For every test point:

• compute distance to all training points
• sort them
• then predict

So prediction can be costly when the training set is large.

This is one of the main disadvantages of KNN.

Advantages of KNN

• very simple
• no training optimization needed
• easy to understand
• works for both classification and regression
• naturally handles multi-class classification

Limitations of KNN

• prediction is slow on large datasets
• sensitive to feature scale
• sensitive to irrelevant features
• choice of $K$ matters a lot
• can perform poorly in very high dimensions

This last issue is related to the curse of dimensionality.

Exam-Oriented Summary

Definition

KNN is an instance-based supervised learning algorithm that predicts a new sample using the nearest stored training samples.

Distance Formula

$$d(x^{(a)},x^{(b)})=\sqrt{\sum _{j=1}^n(x_j^{(a)}-x_j^{(b)}{)}^2}$$

Classification Rule

$$\hat{y}=\text{mode of }K\text{ nearest labels}$$

Regression Rule

$$\hat{y}=\frac{1}{K}\sum _{i=1}^K{y}_{(i)}$$

Steps

1. store training data
2. compute distance from test point to all training points
3. sort by distance
4. select nearest $K$
5. classify by majority vote or regress by mean

Very Short Revision

KNN Classification

• find nearest $K$
• take majority class
• output class label

KNN Regression

• find nearest $K$
• take mean of target values
• output continuous value

Main formula: $$d(x^{(a)},x^{(b)})=\sqrt{\sum _{j=1}^n(x_j^{(a)}-x_j^{(b)}{)}^2}$$

Final Takeaway

KNN is one of the simplest machine learning algorithms. It does not build a model during training, but predicts by comparing a new point to stored training examples. For classification, it uses the majority class of the nearest neighbors. For regression, it uses the mean target value of the nearest neighbors. Its simplicity makes it excellent for understanding local learning, but its prediction cost and sensitivity to scaling are important limitations.

Decision Tree (ID3 & C4.5)

Both ID3 and C4.5 are decision tree algorithms used for classification. They build a tree top-down by repeatedly choosing the best feature to split the dataset.

A decision tree has:

• root/internal nodes = feature tests
• branches = test outcomes
• leaf nodes = final class labels

The key difference is:

• ID3 chooses splits using Information Gain
• C4.5 improves ID3 by using Gain Ratio and can handle continuous features better

1. Decision Tree Idea

At each step, we want to ask the best question about the data. A good split should make the child groups more pure.

If a node contains both classes mixed together, it is impure. If a node contains only one class, it is pure.

Decision trees reduce impurity step by step until leaves are formed.

Part A: ID3

What ID3 Does

ID3 = Iterative Dichotomiser 3 It builds the tree recursively:

1. compute entropy of current dataset
2. compute information gain of every feature
3. choose the feature with the highest information gain
4. split the data on that feature
5. repeat for each subset

ID3 mainly works best with categorical features.

ID3 Core Equations

Entropy

Entropy measures uncertainty in a dataset: $$H(S)=-\sum _i{p}_i{\log }_2{p}_i$$ where:

• $S$ = current dataset
• $p_i$ = proportion of class $i$

For binary classification: $$H(S)=-p_0{\log }_2{p}_0-p_1{\log }_2{p}_1$$

Meaning:

• entropy = 0 $\Rightarrow$ perfectly pure
• entropy is high $\Rightarrow$ classes are mixed

Information Gain

If we split dataset $S$ using feature $A$: $$IG(S,A)=H(S)-\sum _{v\in values(A)}\frac{|S_v|}{|S|}H(S_v)$$ where:

• $S_v$ = subset where feature $A$ takes value $v$

Meaning:

• higher information gain = better split
• ID3 chooses the feature with maximum information gain

Short and Clean ID3 Code

import pandas as pd
import numpy as np

class ID3:
    def __init__(self):
        self.tree = None
        self.default_class = None

    def entropy(self, y):
        values, counts = np.unique(y, return_counts=True)
        p = counts / counts.sum()
        return -np.sum(p * np.log2(p + 1e-12))

    def information_gain(self, X, y, feature):
        parent_entropy = self.entropy(y)
        values, counts = np.unique(X[feature], return_counts=True)

        child_entropy = 0
        for v, c in zip(values, counts):
            y_sub = y[X[feature] == v]
            child_entropy += (c / len(X)) * self.entropy(y_sub)

        return parent_entropy - child_entropy

    def best_feature(self, X, y):
        gains = {f: self.information_gain(X, y, f) for f in X.columns}
        return max(gains, key=gains.get)

    def build(self, X, y):
        if len(np.unique(y)) == 1:
            return y.iloc[0]

        if X.empty:
            return y.mode()[0]

        best = self.best_feature(X, y)
        tree = {best: {}}

        for v in X[best].unique():
            mask = X[best] == v
            X_sub = X.loc[mask].drop(columns=[best])
            y_sub = y.loc[mask]

            if len(X_sub) == 0:
                tree[best][v] = y.mode()[0]
            else:
                tree[best][v] = self.build(X_sub, y_sub)

        return tree

    def fit(self, X, y):
        self.default_class = y.mode()[0]
        self.tree = self.build(X, y)
        return self

    def _predict_one(self, x, tree):
        if not isinstance(tree, dict):
            return tree

        feature = next(iter(tree))
        value = x.get(feature)

        if value not in tree[feature]:
            return self.default_class

        return self._predict_one(x, tree[feature][value])

    def predict(self, X):
        return X.apply(lambda row: self._predict_one(row, self.tree), axis=1)

Small Example for ID3

We use a tiny categorical dataset:

data = pd.DataFrame({
    "Weather": ["Sunny", "Sunny", "Overcast", "Rain", "Rain", "Rain", "Overcast", "Sunny"],
    "Wind":    ["Weak", "Strong", "Weak", "Weak", "Weak", "Strong", "Strong", "Weak"],
    "Play":    ["No", "No", "Yes", "Yes", "Yes", "No", "Yes", "No"]
})

X = data[["Weather", "Wind"]]
y = data["Play"]

model = ID3().fit(X, y)
print("ID3 Tree:", model.tree)
print("Predictions:", model.predict(X).tolist())

Solving the ID3 Example Step by Step

Dataset: $$S=\{8\text{ samples}\}$$ Target classes:

• Yes = 4
• No = 4

So root entropy: $$H(S)=-\frac{4}{8}{\log }_2\frac{4}{8}-\frac{4}{8}{\log }_2\frac{4}{8}=1$$

So the root is maximally mixed.

Step 1: Try splitting on Weather

Possible values:

• Sunny
• Overcast
• Rain

Subsets:

• Sunny $\to$ [No, No, No]
• Overcast $\to$ [Yes, Yes]
• Rain $\to$ [Yes, Yes, No]

Entropies:

Sunny subset

All are No, so: $$H(Sunny)=0$$

Overcast subset

All are Yes, so: $$H(Overcast)=0$$

Rain subset

2 Yes, 1 No: $$H(Rain)=-\frac{2}{3}{\log }_2\frac{2}{3}-\frac{1}{3}{\log }_2\frac{1}{3}\approx 0.9183$$

Weighted entropy after splitting on Weather: $$\frac{3}{8}(0)+\frac{2}{8}(0)+\frac{3}{8}(0.9183)=0.3444$$

Information gain: $$IG(S,\text{Weather})=1-0.3444=0.6556$$

Step 2: Try splitting on Wind

Possible values:

• Weak
• Strong

Subsets:

• Weak $\to$ [No, Yes, Yes, Yes, No]
• Strong $\to$ [No, No, Yes]

Entropies:

Weak

3 Yes, 2 No: $$H(Weak)=-\frac{3}{5}{\log }_2\frac{3}{5}-\frac{2}{5}{\log }_2\frac{2}{5}\approx 0.9710$$

Strong

1 Yes, 2 No: $$H(Strong)=-\frac{1}{3}{\log }_2\frac{1}{3}-\frac{2}{3}{\log }_2\frac{2}{3}\approx 0.9183$$

Weighted entropy: $$\frac{5}{8}(0.9710)+\frac{3}{8}(0.9183)\approx 0.9512$$

Information gain: $$IG(S,\text{Wind})=1-0.9512=0.0488$$

Step 3: Choose the best feature

Since: $$IG(\text{Weather})>IG(\text{Wind})$$ ID3 chooses: $$\text{Weather}$$ as the root feature.

So the first tree becomes:

Weather
├── Sunny     -> No
├── Overcast  -> Yes
└── Rain      -> split again

Step 4: Recurse on the Rain subset

Rain subset:

• Weak -> Yes
• Weak -> Yes
• Strong -> No

Now only one feature remains: Wind

If split on Wind:

• Weak -> all Yes
• Strong -> all No

So final tree:

Weather
├── Sunny     -> No
├── Overcast  -> Yes
└── Rain
    ├── Weak  -> Yes
    └── Strong -> No

This is exactly how ID3 builds the tree recursively.

ID3 Concept -> Equation -> Code

1. Measure impurity

Concept: We first measure how mixed the labels are.

Equation: $$H(S)=-\sum _i{p}_i{\log }_2{p}_i$$

Code:

def entropy(self, y):
    values, counts = np.unique(y, return_counts=True)
    p = counts / counts.sum()
    return -np.sum(p * np.log2(p + 1e-12))

2. Score each feature

Concept: Check how much uncertainty reduces after splitting on a feature.

Equation: $$IG(S,A)=H(S)-\sum _v\frac{|S_v|}{|S|}H(S_v)$$

Code:

def information_gain(self, X, y, feature):
    parent_entropy = self.entropy(y)
    values, counts = np.unique(X[feature], return_counts=True)

    child_entropy = 0
    for v, c in zip(values, counts):
        y_sub = y[X[feature] == v]
        child_entropy += (c / len(X)) * self.entropy(y_sub)

    return parent_entropy - child_entropy

3. Pick the best feature

Concept: Choose the feature with maximum information gain.

Code:

def best_feature(self, X, y):
    gains = {f: self.information_gain(X, y, f) for f in X.columns}
    return max(gains, key=gains.get)

4. Build tree recursively

Concept: After choosing the best feature, split data and build smaller trees.

Code:

def build(self, X, y):
    if len(np.unique(y)) == 1:
        return y.iloc[0]

    if X.empty:
        return y.mode()[0]

    best = self.best_feature(X, y)
    tree = {best: {}}

    for v in X[best].unique():
        mask = X[best] == v
        X_sub = X.loc[mask].drop(columns=[best])
        y_sub = y.loc[mask]
        tree[best][v] = self.build(X_sub, y_sub)

    return tree

Meaning:

• if node is pure -> make leaf
• if no features left -> return majority class
• else split and recurse

ID3 Pseudocode

ID3(D, features):
    if all labels same:
        return leaf
    if no features left:
        return majority class
    best = feature with max information gain
    create node(best)
    for each value v of best:
        recurse on subset where best = v

ID3 Advantages

• simple and easy to understand
• tree rules are interpretable
• good for categorical data
• useful in exam explanations because steps are very clear

ID3 Limitations

• biased toward features with many distinct values
• not naturally suited for continuous features
• can overfit
• sensitive to noise

Part B: C4.5

What C4.5 Does

C4.5 is an improved version of ID3. It fixes major weaknesses of ID3.

Main improvements:

1. uses Gain Ratio instead of pure Information Gain
2. handles continuous features
3. can handle missing values better
4. usually produces more practical trees

So:

• ID3 = older, simpler
• C4.5 = smarter extension of ID3

Why ID3 Needs Improvement

Information Gain can favor a feature with many distinct values.

Example:

• a feature like StudentID may split every row separately
• this gives very high information gain
• but it does not generalize

So C4.5 divides Information Gain by a quantity called Split Information.

C4.5 Core Equations

Entropy

Same as ID3: $$H(S)=-\sum _i{p}_i{\log }_2{p}_i$$

Information Gain

Same as ID3: $$IG(S,A)=H(S)-\sum _v\frac{|S_v|}{|S|}H(S_v)$$

Split Information

$$SI(S,A)=-\sum _v\frac{|S_v|}{|S|}{\log }_2\frac{|S_v|}{|S|}$$

Gain Ratio

$$GR(S,A)=\frac{IG(S,A)}{SI(S,A)}$$

C4.5 chooses the feature with the highest gain ratio.

Short and Clean C4.5 Code

import pandas as pd
import numpy as np

class C45:
    def __init__(self):
        self.tree = None
        self.default_class = None

    def entropy(self, y):
        values, counts = np.unique(y, return_counts=True)
        p = counts / counts.sum()
        return -np.sum(p * np.log2(p + 1e-12))

    def information_gain(self, X, y, feature):
        parent_entropy = self.entropy(y)
        values, counts = np.unique(X[feature], return_counts=True)

        child_entropy = 0
        for v, c in zip(values, counts):
            y_sub = y[X[feature] == v]
            child_entropy += (c / len(X)) * self.entropy(y_sub)

        return parent_entropy - child_entropy

    def split_info(self, X, feature):
        values, counts = np.unique(X[feature], return_counts=True)
        p = counts / counts.sum()
        return -np.sum(p * np.log2(p + 1e-12))

    def gain_ratio(self, X, y, feature):
        ig = self.information_gain(X, y, feature)
        si = self.split_info(X, feature)
        return 0 if si == 0 else ig / si

    def best_feature(self, X, y):
        ratios = {f: self.gain_ratio(X, y, f) for f in X.columns}
        return max(ratios, key=ratios.get)

    def build(self, X, y):
        if len(np.unique(y)) == 1:
            return y.iloc[0]

        if X.empty:
            return y.mode()[0]

        best = self.best_feature(X, y)
        tree = {best: {}}

        for v in X[best].unique():
            mask = X[best] == v
            X_sub = X.loc[mask].drop(columns=[best])
            y_sub = y.loc[mask]

            if len(X_sub) == 0:
                tree[best][v] = y.mode()[0]
            else:
                tree[best][v] = self.build(X_sub, y_sub)

        return tree

    def fit(self, X, y):
        self.default_class = y.mode()[0]
        self.tree = self.build(X, y)
        return self

    def _predict_one(self, x, tree):
        if not isinstance(tree, dict):
            return tree

        feature = next(iter(tree))
        value = x.get(feature)

        if value not in tree[feature]:
            return self.default_class

        return self._predict_one(x, tree[feature][value])

    def predict(self, X):
        return X.apply(lambda row: self._predict_one(row, self.tree), axis=1)

Small Example for C4.5

We use a dataset with a high-cardinality feature to see why Gain Ratio helps:

data = pd.DataFrame({
    "ID":      ["S1", "S2", "S3", "S4", "S5", "S6"],
    "Weather": ["Sunny", "Sunny", "Rain", "Rain", "Overcast", "Overcast"],
    "Play":    ["No", "No", "Yes", "Yes", "Yes", "Yes"]
})

X = data[["ID", "Weather"]]
y = data["Play"]

model = C45().fit(X, y)
print("C4.5 Tree:", model.tree)
print("Predictions:", model.predict(X).tolist())

Solving the C4.5 Example Step by Step

Root labels:

• Yes = 4
• No = 2

Entropy: $$H(S)=-\frac{4}{6}{\log }_2\frac{4}{6}-\frac{2}{6}{\log }_2\frac{2}{6}\approx 0.9183$$

Feature 1: ID

Every ID is unique. So each split contains exactly 1 sample. That means every child subset is pure.

Weighted child entropy: $$0$$ Thus: $$IG(S,\text{ID})=0.9183$$

This looks perfect for ID3. But it is misleading because ID is just a unique label.

Now compute split information. Since there are 6 equally-sized branches: $$SI(S,\text{ID})=-6\left(\frac{1}{6}{\log }_2\frac{1}{6}\right)={\log }_{2}6\approx 2.585$$

So gain ratio: $$GR(S,\text{ID})=\frac{0.9183}{2.585}\approx 0.355$$

Feature 2: Weather

Values:

• Sunny -> [No, No]
• Rain -> [Yes, Yes]
• Overcast -> [Yes, Yes]

All child subsets are pure, so: $$IG(S,\text{Weather})=0.9183$$

Split information: There are 3 equally-sized groups of size 2: $$SI(S,\text{Weather})=-3\left(\frac{2}{6}{\log }_2\frac{2}{6}\right)=1.585$$

Gain ratio: $$GR(S,\text{Weather})=\frac{0.9183}{1.585}\approx 0.579$$

Choose the best feature

Although both features have equal information gain, gain ratio is larger for Weather: $$GR(\text{Weather})>GR(\text{ID})$$

So C4.5 correctly chooses: $$\text{Weather}$$ instead of ID.

This is the key improvement over ID3.

C4.5 Concept -> Equation -> Code

1. Compute entropy

Concept: Measure uncertainty at the current node.

Equation: $$H(S)=-\sum _i{p}_i{\log }_2{p}_i$$

Code:

def entropy(self, y):
    values, counts = np.unique(y, return_counts=True)
    p = counts / counts.sum()
    return -np.sum(p * np.log2(p + 1e-12))

2. Compute information gain

Concept: Measure reduction in entropy after split.

Equation: $$IG(S,A)=H(S)-\sum _v\frac{|S_v|}{|S|}H(S_v)$$

Code:

def information_gain(self, X, y, feature):
    parent_entropy = self.entropy(y)
    ...
    return parent_entropy - child_entropy

3. Compute split information

Concept: Measure how broadly the split divides the data.

Equation: $$SI(S,A)=-\sum _v\frac{|S_v|}{|S|}{\log }_2\frac{|S_v|}{|S|}$$

Code:

def split_info(self, X, feature):
    values, counts = np.unique(X[feature], return_counts=True)
    p = counts / counts.sum()
    return -np.sum(p * np.log2(p + 1e-12))

4. Compute gain ratio

Concept: Normalize information gain so features with too many distinct values are not unfairly favored.

Equation: $$GR(S,A)=\frac{IG(S,A)}{SI(S,A)}$$

Code:

def gain_ratio(self, X, y, feature):
    ig = self.information_gain(X, y, feature)
    si = self.split_info(X, feature)
    return 0 if si == 0 else ig / si

5. Choose best feature and recurse

Concept: Build the decision tree exactly like ID3, but use Gain Ratio instead of Information Gain.

Code:

def best_feature(self, X, y):
    ratios = {f: self.gain_ratio(X, y, f) for f in X.columns}
    return max(ratios, key=ratios.get)

Handling Continuous Features in C4.5

A major improvement of C4.5 is continuous-value handling. For a numeric feature, C4.5 tries thresholds: $$A\le t\text{vs}A>t$$ and chooses the threshold with the best gain ratio.

Example split: $$\text{Glucose}\le 120?$$

So unlike ID3, C4.5 can naturally work with continuous attributes by converting them into binary threshold splits.

A simplified threshold idea in code would be:

threshold = 120
left = X[feature] <= threshold
right = X[feature] > threshold

Then entropy, IG, and GR are computed for that split.

ID3 vs C4.5

Main Difference

ID3 chooses: $$\max IG$$ C4.5 chooses: $$\max GR$$

Comparison Table

Full Combined Example

import pandas as pd

data = pd.DataFrame({
    "Weather": ["Sunny", "Sunny", "Overcast", "Rain", "Rain", "Rain", "Overcast", "Sunny"],
    "Wind":    ["Weak", "Strong", "Weak", "Weak", "Weak", "Strong", "Strong", "Weak"],
    "Play":    ["No", "No", "Yes", "Yes", "Yes", "No", "Yes", "No"]
})

X = data[["Weather", "Wind"]]
y = data["Play"]

id3_model = ID3().fit(X, y)
c45_model = C45().fit(X, y)

print("ID3 Tree:", id3_model.tree)
print("C4.5 Tree:", c45_model.tree)
print("ID3 Predictions:", id3_model.predict(X).tolist())
print("C4.5 Predictions:", c45_model.predict(X).tolist())

How the Tree Predicts

Suppose tree is:

Weather
├── Sunny     -> No
├── Overcast  -> Yes
└── Rain
    ├── Weak   -> Yes
    └── Strong -> No

For a new row:

Weather = Rain, Wind = Weak

Path:

1. check Weather
2. move to Rain
3. check Wind
4. Weak -> leaf = Yes

So predicted class is: $$\text{Yes}$$

Why These Algorithms Work

Both algorithms work by repeatedly reducing uncertainty. They ask:

which feature makes the class labels as pure as possible after splitting?

ID3 answers this using information gain. C4.5 answers this using gain ratio.

The recursion stops when:

• node becomes pure
• no features remain
• or no useful split is possible

So a large classification problem becomes a sequence of small rule-based decisions.

Advantages of ID3 and C4.5

• easy to interpret
• produces human-readable rules
• no heavy math during prediction
• useful for categorical classification tasks
• good for exam answers because the logic is visual and recursive

Limitations

ID3

• biased toward attributes with many values
• struggles with continuous data
• can overfit
• sensitive to noise

C4.5

• more complex than ID3
• deeper trees can still overfit without pruning
• threshold search for continuous features adds computation

Exam-Oriented Summary

ID3 Definition

ID3 is a top-down greedy decision tree algorithm that chooses the feature with the highest information gain at each step.

C4.5 Definition

C4.5 is an improved decision tree algorithm that extends ID3 by using gain ratio and supporting continuous features.

ID3 Formula

Entropy: $$H(S)=-\sum _i{p}_i{\log }_2{p}_i$$ Information Gain: $$IG(S,A)=H(S)-\sum _v\frac{|S_v|}{|S|}H(S_v)$$

C4.5 Formula

Split Information: $$SI(S,A)=-\sum _v\frac{|S_v|}{|S|}{\log }_2\frac{|S_v|}{|S|}$$ Gain Ratio: $$GR(S,A)=\frac{IG(S,A)}{SI(S,A)}$$

Common Steps

1. compute impurity of current dataset
2. score every feature
3. choose best feature
4. split dataset
5. repeat recursively
6. stop when node is pure or features are exhausted

Very Short Revision

ID3

• uses entropy
• computes information gain
• picks feature with max gain
• recursive tree construction

C4.5

• starts like ID3
• adds split information
• uses gain ratio
• handles continuous features better

Final Takeaway

ID3 and C4.5 both build decision trees by recursively selecting the best splitting feature. ID3 uses Information Gain, while C4.5 improves it using Gain Ratio to avoid unfair preference for features with many distinct values. So:

• use ID3 to understand the core decision tree idea
• use C4.5 as the more practical and improved version

Artificial Neural Network (ANN)

An Artificial Neural Network is a model made of layers of neurons. A basic ANN has:

• input layer
• hidden layer(s)
• output layer
• weights and biases
• activation functions

A neuron computes: $$z=Wx+b$$ and then applies an activation function: $$a=g(z)$$

For this example, we build a 2-layer neural network for binary classification:

• hidden layer uses ReLU
• output layer uses Sigmoid

The final output is a probability: $$\hat{y}\in (0,1)$$ and prediction is: $$\hat{y}\ge 0.5\Rightarrow 1,\hat{y}<0.5\Rightarrow 0$$

What This Network Learns

For input $X$, the network computes: $$Z_1=W_{1}X+b_1$$ $$A_1=\text{ReLU}(Z_1)$$ $$Z_2=W_2{A}_1+b_2$$ $$A_2=\sigma (Z_2)=\frac{1}{1+e^{-Z_2}}$$

Where:

• $Z_1,Z_2$ = linear outputs
• $A_1$ = hidden layer activations
• $A_2$ = final predicted probability

Short and Clean Code

import numpy as np

class SimpleANN:
    def __init__(self, input_size, hidden_size, lr=0.1, epochs=10000):
        np.random.seed(42)
        self.lr = lr
        self.epochs = epochs
        self.W1 = np.random.randn(hidden_size, input_size) * 0.1
        self.b1 = np.zeros((hidden_size, 1))
        self.W2 = np.random.randn(1, hidden_size) * 0.1
        self.b2 = np.zeros((1, 1))
        self.costs = []

    def relu(self, Z):
        return np.maximum(0, Z)

    def relu_deriv(self, Z):
        return (Z > 0).astype(float)

    def sigmoid(self, Z):
        Z = np.clip(Z, -500, 500)
        return 1 / (1 + np.exp(-Z))

    def forward(self, X):
        Z1 = self.W1 @ X + self.b1
        A1 = self.relu(Z1)
        Z2 = self.W2 @ A1 + self.b2
        A2 = self.sigmoid(Z2)
        cache = (X, Z1, A1, Z2, A2)
        return A2, cache

    def compute_cost(self, Y, A2):
        eps = 1e-9
        A2 = np.clip(A2, eps, 1 - eps)
        return -np.mean(Y * np.log(A2) + (1 - Y) * np.log(1 - A2))

    def backward(self, Y, cache):
        X, Z1, A1, Z2, A2 = cache
        m = X.shape[1]

        dZ2 = A2 - Y
        dW2 = (dZ2 @ A1.T) / m
        db2 = np.sum(dZ2, axis=1, keepdims=True) / m

        dZ1 = (self.W2.T @ dZ2) * self.relu_deriv(Z1)
        dW1 = (dZ1 @ X.T) / m
        db1 = np.sum(dZ1, axis=1, keepdims=True) / m

        return dW1, db1, dW2, db2

    def fit(self, X, Y):
        for i in range(self.epochs):
            A2, cache = self.forward(X)
            cost = self.compute_cost(Y, A2)
            dW1, db1, dW2, db2 = self.backward(Y, cache)

            self.W1 -= self.lr * dW1
            self.b1 -= self.lr * db1
            self.W2 -= self.lr * dW2
            self.b2 -= self.lr * db2

            self.costs.append(cost)
            if i % 1000 == 0:
                print(f"Epoch {i}: Cost = {cost:.6f}")

    def predict(self, X):
        A2, _ = self.forward(X)
        return (A2 >= 0.5).astype(int)

X = np.array([[0, 0, 1, 1],
              [0, 1, 0, 1]], dtype=float)

Y = np.array([[0, 0, 0, 1]], dtype=float)

model = SimpleANN(input_size=2, hidden_size=4, lr=0.1, epochs=10000)
model.fit(X, Y)

pred = model.predict(X)
print("Predictions:", pred)

Dataset Used: AND Gate

The network is trained on the AND truth table: $$\begin{array}{ccc}{x}_1& x_2& y\\ 0& 0& 0\\ 0& 1& 0\\ 1& 0& 0\\ 1& 1& 1\end{array}$$

Input matrix:

X = np.array([[0, 0, 1, 1],
              [0, 1, 0, 1]], dtype=float)

Target matrix:

Y = np.array([[0, 0, 0, 1]], dtype=float)

Shape meaning:

• $X$ has shape $(2,4)$
• 2 input features
• 4 training examples

So each column is one example: $$X=\left[\begin{array}{cccc}0& 0& 1& 1\\ 0& 1& 0& 1\end{array}\right]$$

Network Architecture

This ANN has:

• 2 input neurons
• 4 hidden neurons
• 1 output neuron

So parameter shapes are: $$W_1\in {\mathbb{R}}^{4\times 2},b_1\in {\mathbb{R}}^{4\times 1}$$ $$W_2\in {\mathbb{R}}^{1\times 4},b_2\in {\mathbb{R}}^{1\times 1}$$

Step-by-Step Algorithm

Step 1: Initialize weights and biases

We begin with small random weights and zero biases.

Code:

self.W1 = np.random.randn(hidden_size, input_size) * 0.1
self.b1 = np.zeros((hidden_size, 1))
self.W2 = np.random.randn(1, hidden_size) * 0.1
self.b2 = np.zeros((1, 1))

Concept:

• weights decide how strongly neurons influence the next layer
• biases shift the activation
• small random values break symmetry
• if all weights start the same, neurons learn the same thing

Why not large random weights:

• large values can make training unstable
• small values help smoother learning at the start

Step 2: Hidden layer linear transformation

Each hidden neuron computes: $$Z_1=W_{1}X+b_1$$

Code:

Z1 = self.W1 @ X + self.b1

Concept: This is the weighted sum of inputs plus bias.

For one hidden neuron: $$z=w_1{x}_1+w_2{x}_2+b$$

Since there are 4 hidden neurons, this is done 4 times in parallel.

Step 3: Apply ReLU activation

ReLU function is: $$\text{ReLU}(z)=\max (0,z)$$

Code:

A1 = self.relu(Z1)

and:

def relu(self, Z):
    return np.maximum(0, Z)

Concept:

• negative values become 0
• positive values remain unchanged

Why ReLU:

• introduces non-linearity
• lets the network learn more complex patterns
• simple and efficient

Without activation, multiple layers would collapse into just one linear transformation.

Step 4: Output layer linear transformation

Now hidden activations are passed to the output neuron: $$Z_2=W_2{A}_1+b_2$$

Code:

Z2 = self.W2 @ A1 + self.b2

Concept: This combines the hidden-layer outputs into one final score.

Step 5: Apply Sigmoid to get probability

Sigmoid function: $$\sigma (z)=\frac{1}{1+e^{-z}}$$

Code:

A2 = self.sigmoid(Z2)

and:

def sigmoid(self, Z):
    Z = np.clip(Z, -500, 500)
    return 1 / (1 + np.exp(-Z))

Concept:

• converts raw score into probability
• output is between 0 and 1
• suitable for binary classification

Meaning: $$A_2=P(y=1\mid X)$$

Why clip is used:

• prevents overflow in exp
• improves numerical stability

Step 6: Compute the cost

For binary classification, we use binary cross-entropy loss: $$J=-\frac{1}{m}\sum \left[Y\log (A_2)+(1-Y)\log (1-A_2)\right]$$

Code:

def compute_cost(self, Y, A2):
    eps = 1e-9
    A2 = np.clip(A2, eps, 1 - eps)
    return -np.mean(Y * np.log(A2) + (1 - Y) * np.log(1 - A2))

Concept:

• if actual label is 1, we want output close to 1
• if actual label is 0, we want output close to 0
• confident wrong predictions get heavily penalized

Why clip again:

• avoids $\log (0)$ which is undefined

Step 7: Backpropagation for output layer

The error at the output layer is: $$d{Z}_2=A_2-Y$$

Code:

dZ2 = A2 - Y
dW2 = (dZ2 @ A1.T) / m
db2 = np.sum(dZ2, axis=1, keepdims=True) / m

Equations: $$d{W}_2=\frac{1}{m}d{Z}_2{A}_1^T$$ $$d{b}_2=\frac{1}{m}\sum d{Z}_2$$