Supervised learning is a type of ML where the model learns from labelled data (input + correct output). The goal is to predict outputs for new, unseen inputs. Examples: Classification (spam vs not spam), Regression (predicting house price).

Unsupervised learning works on unlabelled data — no target variable. The goal is to find hidden patterns or structure in the data. Examples: Clustering (customer segments), Dimensionality reduction (PCA).

In reinforcement learning, an agent learns by trial and error in an environment. It receives rewards for good actions and penalties for bad ones. Goal: maximize total reward over time. Examples: Game playing (AlphaGo), robotics, self-driving cars.

• Training set: used to fit the model parameters.
• Validation set: used to tune hyperparameters and select the best model.
• Test set: used only once at the end to estimate final performance.

A common split is 70% / 15% / 15%.

Overfitting happens when the model learns the training data too well — including its noise. Result: very high training accuracy but poor performance on new data. Sign: big gap between training and test accuracy.

Underfitting happens when the model is too simple to capture the underlying pattern. Result: low accuracy on both training and test data. Fix: use a more complex model or add better features.

A hyperparameter is a setting chosen before training (not learned from data). Examples:

• Learning rate in gradient descent.
• Number of trees in a Random Forest.
• K in K-Nearest Neighbours.

Tuned using cross-validation.

1. Email spam detection
2. Recommendation systems (Netflix, Amazon)
3. Medical diagnosis (cancer detection from images)
4. Fraud detection in banking
5. Self-driving cars
6. Voice assistants (Siri, Alexa)

$\hat y = \beta_0 + \beta_1 x$, where $\beta_0$ is the intercept and $\beta_1$ is the slope. It predicts a continuous output from one input feature.

Linear regression with multiple input features: $\hat y = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + \dots + \beta_p x_p$.

Each $\beta_j$ shows how much $y$ changes when $x_j$ increases by one unit (others fixed).

A classification algorithm (not regression, despite the name). It predicts the probability of belonging to a class using the sigmoid function: $\sigma(z) = \dfrac{1}{1 + e^{-z}}$.

Used for binary classification (spam/not spam, pass/fail).

A flowchart-like model where each internal node tests a feature, each branch is an outcome, and each leaf gives a class or value. Easy to interpret — explains decisions step by step.

An ensemble of many decision trees. Each tree is trained on a random subset of the data and features. Final prediction = majority vote (classification) or average (regression). Reduces overfitting compared to a single tree.

A probabilistic classifier based on Bayes' theorem. It "naively" assumes that all features are independent of each other. Fast and simple — works very well for text classification (spam filter, sentiment analysis).

Accuracy = fraction of predictions that are correct: $\text{Accuracy} = \dfrac{TP + TN}{TP + TN + FP + FN}$.

Easy to compute but misleading on imbalanced data.

ROC = Receiver Operating Characteristic curve. Plots True Positive Rate (recall) vs False Positive Rate at various thresholds. AUC (Area Under Curve) measures classifier quality: 1 = perfect, 0.5 = random.

A table comparing actual vs predicted labels:

Used to compute accuracy, precision, recall, and F1.

SVM is a classifier that finds the best hyperplane that separates two classes with the maximum margin. The points closest to the hyperplane are called support vectors. SVM can also handle non-linear data using kernels (RBF, polynomial).

Clustering is an unsupervised learning task that groups similar data points together. No labels are given — the algorithm finds natural groupings. Examples: Customer segmentation, image grouping, document organization.

K-Means partitions data into K clusters. Each point is assigned to the nearest cluster centre (centroid). Centroids are updated iteratively until they stop changing. Choice of K is decided by the elbow method.

Hierarchical clustering builds a tree of clusters called a dendrogram. Two types:

• Agglomerative (bottom-up): start with each point as a cluster, merge nearest pairs.
• Divisive (top-down): start with all in one cluster, split repeatedly.

Cut the tree at any height to get desired number of clusters.

DBSCAN = Density-Based Spatial Clustering of Applications with Noise. It forms clusters from dense regions and marks sparse points as noise/outliers. Two parameters: $\varepsilon$ (radius) and minPts (minimum points). No need to specify K in advance.

PCA is a dimensionality reduction technique. It finds new orthogonal directions (called principal components) that capture maximum variance in the data. Used to reduce high-dimensional data while keeping most of the information.

LDA is a supervised dimensionality reduction technique. Unlike PCA, it uses class labels. It finds directions that maximize separation between classes while minimizing variance within each class.

A method to find the optimal number of clusters K in K-means. Plot WSS (Within-Cluster Sum of Squares) against K. The point where the curve bends sharply — the "elbow" — gives the best K.

Silhouette score measures how well each point fits its assigned cluster. Range: −1 to +1.

• +1: point is well-matched to its cluster.
• 0: point is on the boundary.
• −1: point may be in the wrong cluster.

Used to evaluate cluster quality and pick K.

A technique to find interesting relationships between items in large transaction datasets. Produces rules like "If bread is bought, then butter is also bought". Used in market basket analysis.

Support measures how often an itemset appears in transactions: $\text{Support}(X) = \dfrac{\text{count}(X)}{\text{total transactions}}$.

Indicates how popular an itemset is.

Lift measures the strength of a rule, considering item popularity: $\text{Lift}(X \rightarrow Y) = \dfrac{\text{Confidence}(X \rightarrow Y)}{\text{Support}(Y)}$.

• Lift > 1: positive correlation.
• Lift = 1: independent.
• Lift < 1: negative correlation.

A classic algorithm to find frequent itemsets. It uses the Apriori Property: all subsets of a frequent itemset must also be frequent. Generates itemsets level by level, pruning those that don't meet minimum support.

FP-Growth = Frequent Pattern Growth. A faster alternative to Apriori. It builds a compact FP-tree structure from data and mines frequent patterns directly from the tree, without generating candidate itemsets.

The agent is the learner / decision-maker. It interacts with the environment by taking actions, receives state and reward feedback, and aims to learn a policy that maximizes total long-term reward.

A reward is the numerical feedback the environment gives after an action.

• Positive reward = good action.
• Negative reward = bad action (penalty).

The agent's goal is to maximize the cumulative reward over time.

The mathematical framework for RL. Has four elements:

• S: set of states.
• A: set of actions.
• P: transition probabilities.
• R: reward function.

Markov property: next state depends only on current state and action, not the past history.

The basic unit of a neural network. It takes inputs, multiplies each by a weight, sums them with a bias, and passes the result through an activation function: $a = \sigma(\sum w_i x_i + b)$.

ReLU = Rectified Linear Unit: $\text{ReLU}(x) = \max(0, x)$.

Simple and fast. Helps overcome the vanishing-gradient problem. Most widely used activation in deep learning.

$\sigma(x) = \dfrac{1}{1 + e^{-x}}$.

Maps any input to range (0, 1). Used in the output layer for binary classification. Can suffer from vanishing gradient in deep networks.

An optimization algorithm to minimize the loss function. Updates weights in the direction opposite to the gradient: $w \leftarrow w - \eta \dfrac{\partial L}{\partial w}$,

where $\eta$ is the learning rate.

A loss function measures how wrong the model's predictions are. Training tries to minimize it. Examples:

• MSE (Mean Squared Error) for regression.
• Cross-entropy for classification.

Machine Learning is broadly divided into three main types based on the kind of data and the learning goal.

1. Supervised Learning.

• What it is: Model is trained on labelled data (input + correct output).
• Goal: Learn a function that maps input to output.
• Two main types:
  • Classification — predict a class (spam / not spam).
  • Regression — predict a continuous value (house price).
• Examples: Linear regression, Logistic regression, Decision trees, SVM, Random Forest, Naive Bayes.
• Applications: Email spam detection, credit-risk prediction, image classification.

2. Unsupervised Learning.

• What it is: Works on unlabelled data, no target output given.
• Goal: Find hidden patterns and structure.
• Main tasks:
  • Clustering — group similar items (customer segments).
  • Dimensionality reduction — reduce features while keeping information (PCA).
  • Association rule mining — find related items (market basket).
• Examples: K-Means, Hierarchical clustering, DBSCAN, PCA, Apriori.
• Applications: Customer segmentation, recommendation systems, anomaly detection.

3. Reinforcement Learning.

• What it is: An agent learns by interacting with an environment.
• It takes actions, receives rewards or penalties, and learns a policy maximizing total reward.
• Examples: Q-learning, SARSA, Deep Q-Networks (DQN).
• Applications: Game playing (AlphaGo, AlphaZero), robotics, self-driving cars, automated trading.

Comparison Table.

Conclusion. Each ML type fits different real-world problems. Supervised needs labelled data and gives the most direct results. Unsupervised is useful when labels are unavailable. Reinforcement learning shines in sequential decision-making problems.

A learning system is a complete machine-learning pipeline — from problem definition to deployment.

Steps in designing a learning system.

Step 1: Choose the type of training experience.

• Decide whether the learning is supervised, unsupervised, or reinforcement.
• Identify what data is available and how it will be labelled.
• Example: For spam detection — supervised; need labelled emails.

Step 2: Choose the target function.

• Decide what the model should learn / predict.
• Example: Function $f(\text{email}) \rightarrow \{\text{spam, not spam}\}$.

Step 3: Choose representation of the target function.

• Decide the model type that will represent the function:
  • Linear regression?
  • Decision tree?
  • Neural network?
• Each model has its own form (equation, tree, weights).

Step 4: Choose a learning algorithm.

• Decide how to estimate the model from data:
  • Gradient descent for linear regression / neural networks.
  • ID3/C4.5 for decision trees.
  • K-Means iteration for clustering.

Step 5: Collect and prepare data.

• Gather raw data from sources.
• Clean missing values, remove outliers.
• Engineer useful features.
• Split into training, validation, and test sets.

Step 6: Train the model.

• Apply the learning algorithm on the training set.
• Tune hyperparameters using the validation set.

Step 7: Evaluate.

• Test on unseen data using metrics like accuracy, F1-score, RMSE.
• Check for overfitting / underfitting.

Step 8: Deploy and monitor.

• Put the model into production.
• Monitor performance over time.
• Retrain when data distribution changes.

Why Each Step Matters.

• Wrong representation → model can't capture pattern.
• Bad data → garbage in, garbage out.
• No evaluation → silent failure in production.
• No monitoring → model becomes stale.

Example: Designing a Spam Filter.

1. Type: supervised.
2. Function: spam(email) → yes/no.
3. Representation: Naive Bayes.
4. Algorithm: count + smoothing.
5. Data: 10,000 labelled emails.
6. Train: fit on 70%.
7. Evaluate: 95% F1 on test set.
8. Deploy in mail server, monitor.

Conclusion. Designing a learning system is more than just choosing an algorithm. Every step — from problem framing to monitoring — affects the final quality and reliability of the model in production.

Splitting the Data.

In machine learning, we never use all data for training. The data is split into three parts:

1. Training Set (typically 60–70%).

• Used to fit the model parameters.
• The model "learns" from this data.

2. Validation Set (typically 15–20%).

• Used to tune hyperparameters (learning rate, number of trees, etc.).
• Helps in model selection when comparing different algorithms.
• The model sees this data indirectly during tuning.

3. Test Set (typically 15–20%).

• Used only once at the end to estimate final performance.
• The model has never seen this data.
• Gives an unbiased estimate of real-world performance.

Why split data?

• Avoid overfitting — using the same data to train and evaluate would give a falsely high score.
• Get an honest estimate of how the model will perform on new, unseen data.

Problems with a single split.

• A bad split (lucky/unlucky) can give misleading results.
• Small datasets cannot afford to lose data for validation.

Solution: Cross-Validation.

K-Fold Cross-Validation Steps:

1. Split training data into K equal folds (commonly K = 5 or 10).
2. For each iteration:
   • Use K − 1 folds as training set.
   • Use the remaining fold as validation.
3. Repeat K times so each fold gets to be the validation set once.
4. Average the K scores → reliable performance estimate.

Example. With K = 5 and 1000 training samples, each iteration uses 800 for training and 200 for validation. After 5 iterations, every sample has been used for validation once.

Variants of Cross-Validation.

Benefits of Cross-Validation.

• More reliable performance estimate.
• Reduces dependency on a single split.
• Helps in hyperparameter tuning.
• Detects overfitting easily.

Conclusion. Proper data splitting and cross-validation are crucial for building reliable ML models. They ensure the reported performance reflects real-world behaviour, not lucky splits.

Definition. Logistic Regression is a classification algorithm (not regression, despite the name). It predicts the probability that an input belongs to a particular class.

Why "Logistic"?

Linear regression's output can be any real number, but probabilities must be between 0 and 1. Logistic regression solves this by passing the linear combination through the sigmoid function:

$P(y = 1 \mid x) = \sigma(z) = \dfrac{1}{1 + e^{-z}}$

where $z = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + \dots + \beta_p x_p$.

The output is interpreted as the probability of being in class 1.

Decision Rule.

• If $P(y = 1) \ge 0.5$ → predict class 1.
• Else → predict class 0.

Threshold can be tuned for imbalanced problems.

How it Differs from Linear Regression.

Worked Example.

Predict whether a student passes based on hours studied.

Trained model: $P(\text{pass}) = \sigma(-3 + 1.5x)$.

For x = 3: $z = -3 + 1.5(3) = 1.5$, $P = \sigma(1.5) = 0.82$ → predict Pass. For x = 1: $z = -3 + 1.5(1) = -1.5$, $P = 0.18$ → predict Fail.

Training (Brief).

• Uses Maximum Likelihood Estimation to find best $\beta$ values.
• Optimized by gradient descent on cross-entropy loss.

Advantages.

• Simple and interpretable.
• Gives probability (not just labels).
• Fast to train.

Disadvantages.

• Assumes linear decision boundary.
• Sensitive to outliers.
• Can't capture complex non-linear patterns.

Applications.

• Email spam detection.
• Disease diagnosis (positive / negative).
• Customer churn prediction.
• Credit-risk scoring.

Conclusion. Logistic regression is the simplest yet most widely used classification algorithm. It is the foundation of more complex models and the perfect baseline for any binary classification problem.

Definition. A Decision Tree is a flowchart-like model where:

• Each internal node tests a feature.
• Each branch represents a possible outcome.
• Each leaf gives the final class or value.

It is used for both classification and regression.

How it Works.

1. Start with all training data at the root.
2. Choose the best feature to split on (based on a measure like Gini Impurity or Information Gain).
3. Split data into branches based on feature values.
4. Repeat recursively on each branch.
5. Stop when:
   • All data in a node belongs to one class, OR
   • Maximum depth reached, OR
   • Minimum samples per leaf reached.

Splitting Criteria.

1. Information Gain (based on entropy): $\text{Entropy}(S) = -\sum p_i \log_2 p_i$.

2. Gini Impurity: $\text{Gini}(S) = 1 - \sum p_i^2$.

The split that gives the lowest impurity (or highest gain) is chosen.

Example: Will I Play Tennis?

Suppose data:

The tree might split first on "Outlook":

• Outlook = Sunny → split further on Temperature.
• Outlook = Overcast → always Yes.
• Outlook = Rainy → split further on Temperature.

Final tree (simplified):

• If Outlook = Overcast → Yes.
• Else if Temperature = Cool → Yes.
• Else → No.

Algorithms.

• ID3 — uses entropy / information gain.
• C4.5 — extension of ID3 with pruning.
• CART — uses Gini Impurity; handles classification and regression.

Advantages.

• Easy to understand — visualizable as a tree.
• No data scaling needed.
• Handles both numeric and categorical data.
• Captures non-linear patterns.
• Can show feature importance.

Disadvantages.

• Overfitting — a deep tree memorizes the training data.
• Unstable — small changes in data can change the tree.
• Biased toward features with many levels.

Solution: Random Forest — combine many trees to overcome overfitting.

Applications.

• Credit scoring.
• Medical diagnosis.
• Customer churn prediction.
• Loan approval.

Conclusion. Decision trees are powerful, interpretable models — the building block for advanced methods like Random Forests and Gradient Boosted Trees (XGBoost). Their simplicity makes them a favourite when explainability matters.

Definition. Random Forest is an ensemble machine learning algorithm that combines multiple decision trees to produce more accurate and stable predictions.

It works on the idea: "Many weak learners together make a strong learner."

How Random Forest Works.

Step 1: Bootstrap Sampling.

• Create N different training sets by sampling with replacement from the original data (Bootstrap aggregating = "bagging").

Step 2: Random Feature Selection.

• For each tree, at each split, only consider a random subset of features (typically $\sqrt{p}$ for classification, $p/3$ for regression).

Step 3: Train Independent Trees.

• Train each decision tree fully — no pruning.
• Each tree may overfit, but that's OK.

Step 4: Combine Predictions.

• Classification: majority vote.
• Regression: average of predictions.

Example. A forest of 100 trees, each trained on a different bootstrap sample. For a new test point:

• Tree 1 predicts class 1, Tree 2 predicts class 0, ... Tree 100 predicts class 1.
• Majority vote = class 1.

Why Random Forest is Better than a Single Decision Tree.

Key Reasons It Works.

1. Diversification. Each tree learns slightly different patterns due to different data and features.
2. Wisdom of crowds. Errors of individual trees average out.
3. Reduces variance. Single trees have high variance; averaging reduces it.

Hyperparameters to Tune.

• n_estimators — number of trees (more = better, but slower).
• max_depth — limit tree depth to control complexity.
• min_samples_leaf — minimum samples per leaf node.
• max_features — number of features considered per split.

Advantages.

• Excellent accuracy out of the box.
• Handles missing values and outliers well.
• Works with both classification and regression.
• Gives feature importance scores.
• Hard to overfit.

Disadvantages.

• Less interpretable than single tree.
• Slower to train and predict.
• Large model size in memory.

Applications.

• Credit-risk modelling.
• Fraud detection.
• Disease diagnosis.
• Stock market predictions.
• Customer churn.

Conclusion. Random Forest takes a simple but unstable model (decision tree) and turns it into one of the most powerful and reliable algorithms in ML. It is often the first choice for tabular data problems before trying deeper models.

Definition. Naive Bayes is a probabilistic classifier based on Bayes' Theorem. It is called "naive" because it assumes all features are independent of each other given the class — a strong assumption that rarely holds in reality but works surprisingly well in practice.

Bayes' Theorem.

$P(C \mid X) = \dfrac{P(X \mid C) \cdot P(C)}{P(X)}$,

where:

• $P(C \mid X)$ = posterior probability of class C given features X.
• $P(X \mid C)$ = likelihood of features given class.
• $P(C)$ = prior probability of class.
• $P(X)$ = probability of features.

The Naive Assumption.

Features $x_1, x_2, \dots, x_n$ are conditionally independent given class C:

$P(X \mid C) = P(x_1 \mid C) \cdot P(x_2 \mid C) \cdots P(x_n \mid C)$.

So: $P(C \mid X) \propto P(C) \cdot \prod_i P(x_i \mid C)$.

Decision Rule. Predict the class with highest posterior probability.

Types of Naive Bayes.

Worked Example: Spam Detection.

Suppose we have 100 emails. 40 are spam, 60 are ham. Word "free" appears in 30 spam, 5 ham. Word "meeting" appears in 5 spam, 50 ham.

A new email contains both "free" and "meeting".

Priors.

• $P(\text{Spam}) = 40/100 = 0.4$.
• $P(\text{Ham}) = 60/100 = 0.6$.

Likelihoods.

• $P(\text{free} \mid \text{Spam}) = 30/40 = 0.75$.
• $P(\text{meeting} \mid \text{Spam}) = 5/40 = 0.125$.
• $P(\text{free} \mid \text{Ham}) = 5/60 = 0.083$.
• $P(\text{meeting} \mid \text{Ham}) = 50/60 = 0.833$.

Posterior (proportional).

• Spam: $0.4 \times 0.75 \times 0.125 = 0.0375$.
• Ham: $0.6 \times 0.083 \times 0.833 = 0.0415$.

Prediction: Ham (slightly higher posterior).

Advantages.

• Very fast to train and predict.
• Works well with small datasets.
• Excellent for text classification.
• Handles many features.
• Simple and interpretable.

Disadvantages.

• The independence assumption is rarely true.
• Zero-frequency problem (a word never seen in training gives zero probability) — fixed by Laplace smoothing.
• Poor probability estimates (though decisions are usually correct).

Applications.

• Email spam filters.
• Sentiment analysis (positive / negative reviews).
• Document categorization.
• Medical diagnosis.

Conclusion. Despite its "naive" assumption, Naive Bayes is one of the most effective and practical classifiers, especially for text. It is fast, simple, and often serves as a strong baseline.

Definition. K-Means is an unsupervised clustering algorithm that partitions data into K clusters. Each cluster has a centroid (its centre), and each data point belongs to the cluster whose centroid is nearest.

Goal. Minimize the Within-Cluster Sum of Squares (WSS) — the total squared distance of points from their cluster centroid.

Steps of K-Means.

Step 1: Choose K (number of clusters).

• Use elbow method or silhouette score.

Step 2: Initialize K centroids randomly.

Step 3: Assign each point to the nearest centroid using Euclidean distance: $d(x, c) = \sqrt{\sum (x_i - c_i)^2}$.

Step 4: Update centroids as the mean of points in each cluster: $c_k = \dfrac{1}{|S_k|} \sum_{x \in S_k} x$.

Step 5: Repeat Steps 3 and 4 until centroids stop changing (or for a fixed number of iterations).

Pseudocode (in plain words).

• Pick K random points as initial centroids.
• Loop:
  • Assign every point to nearest centroid.
  • Recalculate centroid as average of assigned points.
• Stop when no point changes its cluster.

Worked Example.

Data points: A(1, 1), B(2, 1), C(4, 3), D(5, 4). K = 2.

Step 1. Initial centroids: C1 = (1, 1) [point A], C2 = (5, 4) [point D].

Step 2. Assign points to nearest centroid:

• A → C1 (distance 0).
• B → C1 (distance 1).
• C → C2 (distance ~1.4).
• D → C2 (distance 0).

Step 3. Update centroids:

• New C1 = mean of {A, B} = (1.5, 1).
• New C2 = mean of {C, D} = (4.5, 3.5).

Step 4. Reassign — same assignment. Stop.

Final Clusters: {A, B} and {C, D}.

Choosing K — The Elbow Method.

Plot WSS against K. The "elbow" point — where the curve bends sharply — gives the optimal K.

Advantages.

• Simple and fast.
• Scales well to large datasets.
• Easy to implement.

Disadvantages.

• Need to choose K beforehand.
• Sensitive to initial centroid placement (use K-Means++ to fix).
• Sensitive to outliers.
• Assumes spherical clusters of similar size.
• Stuck in local minima.

Applications.

• Customer segmentation in retail.
• Document clustering.
• Image compression.
• Anomaly detection.

Conclusion. K-Means is the most popular clustering algorithm — fast, simple, and widely useful. It's the first choice for any clustering task, especially when the number of clusters is known or estimable.

Definition. Hierarchical clustering builds a tree of clusters, called a dendrogram. Unlike K-Means, it does not require specifying the number of clusters in advance.

Two Approaches.

1. Agglomerative (Bottom-Up). (Most common)

• Start: each data point is its own cluster.
• Repeatedly merge the two closest clusters.
• Continue until all points are in one big cluster.

2. Divisive (Top-Down).

• Start: all points in one big cluster.
• Repeatedly split the largest cluster.
• Continue until each point is its own cluster.

Distance / Linkage Methods.

When merging clusters, we need a measure of "closeness":

Steps for Agglomerative Clustering.

1. Compute distance matrix (pairwise distances).
2. Treat each point as a cluster.
3. Find the two closest clusters → merge.
4. Update the distance matrix.
5. Repeat until one cluster remains.

Worked Example.

Points: A(1), B(2), C(5), D(6).

Distances:

• A-B = 1, A-C = 4, A-D = 5
• B-C = 3, B-D = 4
• C-D = 1

Step 1. Closest = A-B (1). Merge → {A,B}. Step 2. Now also closest = C-D (1). Merge → {C,D}. Step 3. Only two clusters left → merge → {A,B,C,D}.

Dendrogram (visual representation).

• Height of merges shows the distance at which clusters joined.
• "Cut" the tree at any height to get desired number of clusters.

Cutting the Tree.

To get K clusters, cut the dendrogram horizontally where there are K vertical lines. This is decided based on:

• Domain knowledge.
• Visual inspection.
• The biggest vertical jumps in the tree.

Advantages.

• No need to specify K in advance.
• Produces a useful dendrogram visualization.
• Captures hierarchical structure.
• Works with any distance metric.

Disadvantages.

• Slow — O(n³) time complexity in worst case.
• Not scalable to large datasets.
• Sensitive to outliers (especially single linkage).
• Cannot undo a merge or split.

Applications.

• Gene expression analysis in biology.
• Document hierarchies.
• Customer segmentation.
• Phylogenetic trees.

Conclusion. Hierarchical clustering is ideal when relationships among data follow a natural hierarchy or when the number of clusters is unknown. The dendrogram is a powerful visual tool for understanding cluster structure.

Definition. PCA (Principal Component Analysis) is an unsupervised dimensionality reduction technique. It finds new orthogonal directions (called principal components) that capture the maximum variance in the data.

Why PCA?

• High-dimensional data is slow to train and prone to overfitting.
• Many features are correlated.
• PCA combines correlated features into fewer uncorrelated ones — keeping most of the information.

Steps of PCA.

Step 1: Standardize the data.

• Subtract the mean from each feature.
• Divide by standard deviation (z-score).
• Why: PCA is sensitive to scale; features with bigger numbers would dominate.

Step 2: Compute the covariance matrix.

• $\Sigma = \dfrac{1}{n-1} X^T X$.
• Shows how features vary together.

Step 3: Find eigenvalues and eigenvectors of covariance matrix.

• Eigenvectors = directions (principal components).
• Eigenvalues = amount of variance captured by each direction.

Step 4: Sort principal components by eigenvalue (descending).

• First PC captures most variance.
• Second PC captures next-most (perpendicular to first).
• And so on.

Step 5: Choose top K components.

• Decide K so that top K components together explain say 95% of total variance.

Step 6: Project original data onto K selected components.

• $Z = X W$, where W contains top K eigenvectors.
• Z is the reduced-dimension representation.

Worked Example (simple).

100 students with 50 exam-score features.

• Standardize.
• Compute covariance matrix.
• Find principal components.
• First PC might combine all math scores → "math ability".
• Second PC might combine language scores → "language ability".
• Keep top 5 PCs that capture 95% variance.
• New data: 100 × 5 instead of 100 × 50.

Visualization. Plot data on first two principal components → 2D scatter plot revealing clusters and patterns.

Applications.

• Face recognition (Eigenfaces).
• Genomics — reducing thousands of gene features.
• Data compression.
• Visualization of high-dimensional data in 2D / 3D.
• Noise reduction (small PCs often represent noise).
• Preprocessing before training ML models.

Advantages.

• Reduces dimensionality without much loss of information.
• Removes correlated features.
• Speeds up downstream models.
• Helps visualize data.

Disadvantages.

• New components are linear combinations — harder to interpret.
• Assumes linear relationships.
• Sensitive to scale (must standardize first).
• Information loss (whatever variance the dropped components held).

PCA vs LDA.

Conclusion. PCA is one of the most widely used dimensionality reduction techniques. It is the first step in any pipeline involving high-dimensional data — visualization, denoising, and preprocessing for downstream learning algorithms.

Definition. Apriori is a classic algorithm to find frequent itemsets and generate association rules from transaction data. Used in market basket analysis (which items are bought together).

Key Concepts.

• Support(X) = fraction of transactions that contain itemset X.
• Confidence(X → Y) = $\dfrac{\text{Support}(X \cup Y)}{\text{Support}(X)}$.
• Lift(X → Y) = $\dfrac{\text{Confidence}(X \rightarrow Y)}{\text{Support}(Y)}$.

Apriori Property (the key idea).

"All non-empty subsets of a frequent itemset must also be frequent."

This means: if {Bread, Milk, Eggs} is frequent, then {Bread}, {Milk}, {Bread, Milk}, etc. must all be frequent. Contrapositive: if any subset is not frequent, the larger set can also be skipped — used for pruning.

Steps of Apriori.

Step 1: Generate frequent 1-itemsets — count each item, keep those above minimum support.

Step 2: Generate frequent k-itemsets from (k-1)-itemsets:

• Join step: combine pairs to form candidates.
• Prune step: drop any candidate whose subset is not frequent.

Step 3: Repeat until no new frequent itemsets can be generated.

Step 4: Generate association rules from frequent itemsets that meet minimum confidence.

Worked Example.

5 transactions:

Minimum support = 2 (40%).

Step 1 — Frequent 1-itemsets:

• Bread: 4, Milk: 4, Diaper: 4, Beer: 3, Coke: 2, Eggs: 1 ❌.

Frequent: {Bread}, {Milk}, {Diaper}, {Beer}, {Coke}.

Step 2 — Candidate 2-itemsets (counts):

• {Bread, Milk}: 3, {Bread, Diaper}: 3, {Bread, Beer}: 2, {Milk, Diaper}: 3, {Milk, Beer}: 2, {Diaper, Beer}: 3.
• {Coke, X} pairs: each ≤ 1, drop.

Frequent: those above.

Step 3 — Candidate 3-itemsets:

• {Bread, Milk, Diaper}: 2 ✓.
• {Bread, Diaper, Beer}: 2 ✓.
• {Milk, Diaper, Beer}: 2 ✓.

Step 4 — Generate rules (min confidence = 70%):

• {Diaper} → {Beer}: support 3/5, confidence 3/4 = 75% ✓.
• {Beer} → {Diaper}: confidence 3/3 = 100% ✓.

Interpretation: Customers who buy Diaper often buy Beer (the famous "diaper-beer" example).

Advantages.

• Simple and easy to understand.
• Provides interpretable rules.
• Works well for small to medium datasets.

Disadvantages.

• Slow for large datasets — multiple scans of database.
• Generates many candidate itemsets.
• Performance drops as data grows.

Applications.

• Market basket analysis (Walmart, Amazon).
• Recommendation systems.
• Medical diagnosis (symptom-disease patterns).
• Web usage mining.

Conclusion. Apriori is the foundation algorithm for association rule mining. Though slow for big data, it provides interpretable and actionable rules. Modern alternatives like FP-Growth address its speed limitations.

Both algorithms find frequent itemsets in transaction data, but they take very different approaches.

1. Apriori Algorithm.

• Approach: Generate candidates, then test for frequency.
• Key idea: Apriori property — if any subset is not frequent, the larger set is also not.
• Process:
  • Scan database multiple times.
  • Generate (k+1)-itemset candidates from frequent k-itemsets.
  • Prune candidates whose subsets are not frequent.
  • Count support by scanning database again.

2. FP-Growth (Frequent Pattern Growth) Algorithm.

• Approach: Builds a compact FP-tree structure that captures all transactions efficiently. Then mines frequent patterns directly from the tree.
• Key idea: No candidate generation — directly grow frequent patterns from the tree.

Steps of FP-Growth.

1. Scan database once — count item frequencies, sort by support.
2. Build the FP-tree:
   • Each transaction is inserted as a path.
   • Common prefixes share the same branch.
3. Mine the tree recursively, building "conditional pattern bases" and conditional FP-trees.

Detailed Comparison.

Example Comparison.

For a database of 1 million transactions:

• Apriori: Hours of computation, many DB scans.
• FP-Growth: Minutes of computation, only 2 scans.

Worked Example (FP-Growth concept).

Suppose transactions (Apriori example):

Item frequencies: a:3, b:3, c:3.

Step 1. Sort each transaction by frequency (descending): all items equal, keep insertion order.

Step 2. Build FP-tree:

• Insert {a, b, c}.
• Insert {a, b}: shares "a, b" branch.
• Insert {a, c}: branches off "a" → c.
• Insert {b, c}: starts new branch from root.

Step 3. Mine frequent patterns from leaves up.

Result: frequent itemsets like {a, b}, {a, c}, {b, c} → no need to generate candidates explicitly.

Advantages of FP-Growth.

• Much faster than Apriori.
• Only 2 database scans.
• Compact memory representation.
• Scales to large datasets.

Disadvantages of FP-Growth.

• More complex to implement.
• May use more memory for FP-tree.
• Tree can be huge if items don't share prefixes.

When to Use Which.

• Small datasets → Apriori (simpler).
• Large transaction databases → FP-Growth.
• Production market basket analysis → FP-Growth.

Conclusion. Both algorithms solve the same problem, but FP-Growth is significantly faster and more practical for real-world large datasets. Apriori remains useful for teaching and simple cases.

Definition. Q-Learning is a model-free reinforcement learning algorithm. The agent learns a Q-table that gives the quality of taking action $a$ in state $s$. The optimal policy is to always pick the action with highest Q-value.

Key Idea. Without knowing the environment's rules, the agent learns through trial and error. Over many episodes, the Q-table converges to the optimal action-values.

Q-Value. $Q(s, a)$ = expected total future reward of taking action $a$ in state $s$.

Bellman Equation (heart of Q-Learning).

$Q(s, a) \leftarrow Q(s, a) + \alpha \big[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \big]$,

where:

• $\alpha$ = learning rate (0 to 1).
• $\gamma$ = discount factor (importance of future rewards).
• $r$ = immediate reward received.
• $s'$ = next state.
• $\max_{a'} Q(s', a')$ = best estimated future Q-value from next state.

Steps of Q-Learning.

Step 1: Initialize Q-table. All Q-values start at 0.

Step 2: For each episode:

• Start at some initial state $s$.
• Loop until terminal state:
  • Choose action $a$ using ε-greedy policy (mostly best action, sometimes random for exploration).
  • Take action; observe reward $r$ and next state $s'$.
  • Update $Q(s, a)$ using Bellman equation.
  • Set $s = s'$.

Step 3: Repeat for many episodes until Q-table converges.

ε-Greedy Strategy (Exploration vs Exploitation).

• With probability ε → pick random action (explore).
• With probability 1−ε → pick action with highest Q-value (exploit).
• ε is usually decreased over time.

Worked Example: Grid World.

A 4-cell grid:

• S = start, G = goal (reward +10).
• Actions: Up, Down, Left, Right.
• Step reward: −1 (to encourage shortest path).
• $\alpha = 0.5, \gamma = 0.9$.

Initial Q-table: all zeros.

Episode 1: Agent moves S → Right → G. Reward sequence: −1, +10.

• Update Q(S, Right): $0 + 0.5(−1 + 0.9 × 0 − 0) = −0.5$.

Over many episodes, Q-values increase for actions leading toward G, and the agent learns the optimal path: shortest path = Right then Down (or Down then Right).

Advantages.

• Model-free — no need to know environment dynamics.
• Simple and effective for small problems.
• Provably converges to optimum.

Disadvantages.

• Q-table is impractical for huge state spaces.
• Slow to converge.
• Needs many episodes.

Solution: Deep Q-Networks (DQN). Replace Q-table with a neural network. Used by DeepMind to play Atari games at superhuman level.

Applications.

• Game playing (chess, Atari, Go).
• Robot navigation.
• Resource management.
• Trading algorithms.
• Self-driving cars.

Conclusion. Q-Learning is the foundation of modern reinforcement learning. Though simple, it captures the essence of trial-and-error learning. Its extension to Deep Q-Learning powers modern game AI and decision-making systems.

Definition. A Convolutional Neural Network (CNN) is a special type of neural network designed to process grid-like data, especially images. It is inspired by the visual cortex of the human brain.

Why CNNs Instead of Regular Neural Networks?

For an image of 200×200 pixels with 3 colour channels:

• Regular neural network: $200 × 200 × 3 = 120{,}000$ input neurons → huge number of weights.
• CNN: uses small filters that scan the image, sharing weights → far fewer parameters.

CNNs exploit:

• Local patterns (edges, textures).
• Translation invariance (a cat is a cat anywhere in the image).
• Hierarchical features (edges → shapes → objects).

CNN Architecture (Layers).

1. Convolutional Layer.

• Applies several small filters (e.g., 3×3 or 5×5) across the input image.
• Each filter detects a specific feature (edge, corner, texture).
• Produces feature maps.
• Uses shared weights — same filter applied everywhere.

2. Activation Layer (ReLU).

• Applies $f(x) = \max(0, x)$ to introduce non-linearity.

3. Pooling Layer (Max Pooling).

• Reduces spatial size of feature maps.
• Max pooling picks the maximum value in each small window (e.g., 2×2).
• Makes the network robust to small shifts in the image.

4. Fully Connected Layer.

• After several conv + pool layers, the result is flattened.
• Passed through one or more dense layers.
• Final layer gives class probabilities (softmax).

Typical Architecture.

Input → [Conv → ReLU → Pool]×N → Flatten → Dense → Softmax → Output.

Famous CNN Models.

• LeNet-5 (1998) — first successful CNN for digit recognition.
• AlexNet (2012) — sparked the deep learning revolution.
• VGG, ResNet, Inception — modern architectures.

Working Example.

Image of a cat (32×32×3) → CNN.

• Conv1 detects edges.
• Pool1 reduces to 16×16.
• Conv2 detects shapes.
• Pool2 reduces to 8×8.
• Conv3 detects parts (eyes, ears).
• Flatten + Dense layers combine these to recognize "cat".
• Output: P(cat) = 0.95.

Advantages.

• Far fewer parameters than fully connected networks.
• Excellent for image, video, and audio processing.
• Learns features automatically (no manual feature engineering).
• Translation invariant.

Disadvantages.

• Needs lots of data and computational power.
• Hard to interpret what each filter detects.
• May not handle very different orientations well.

Applications.

• Image classification (cats, dogs, diseases).
• Object detection (YOLO, Faster R-CNN).
• Face recognition.
• Medical imaging (cancer detection from MRI / X-ray).
• Self-driving cars (lane detection, pedestrian recognition).
• OCR (reading text from images).
• Video analysis.

Conclusion. CNNs are the backbone of modern computer vision. Their ability to automatically learn hierarchical features from images has revolutionized fields from medical diagnosis to autonomous vehicles.

What is an Activation Function?

An activation function decides whether and how strongly a neuron should "fire" — it introduces non-linearity into the neural network. Without it, even a deep network is just a linear function and cannot learn complex patterns.

Common Activation Functions.

1. Step Function (Threshold).

• Output: 0 if x < 0, else 1.
• Used in original perceptrons.
• Disadvantage: not differentiable → can't use gradient descent.

2. Sigmoid Function.

$\sigma(x) = \dfrac{1}{1 + e^{-x}}$.

• Range: (0, 1).
• Smooth, differentiable.
• Used in output layer for binary classification.
• Disadvantage: Vanishing gradient problem in deep networks.

3. Tanh (Hyperbolic Tangent).

$\tanh(x) = \dfrac{e^x - e^{-x}}{e^x + e^{-x}}$.

• Range: (−1, 1).
• Zero-centred (better than sigmoid for hidden layers).
• Disadvantage: Still suffers from vanishing gradient in deep networks.

4. ReLU (Rectified Linear Unit). (Most popular)

$\text{ReLU}(x) = \max(0, x)$.

• Simple, fast to compute.
• No vanishing gradient for x > 0.
• Most widely used in hidden layers.
• Disadvantage: "Dying ReLU" — neurons can get stuck at zero for negative inputs.

5. Leaky ReLU.

$f(x) = x \text{ if } x > 0, \text{ else } 0.01 x$.

• Allows a small gradient for negative inputs → fixes dying ReLU.
• Slight performance improvement over plain ReLU.

6. Softmax.

$\text{softmax}(z_i) = \dfrac{e^{z_i}}{\sum_j e^{z_j}}$.

• Outputs probabilities that sum to 1.
• Used in the output layer for multi-class classification.

Comparison Table.

Which to Use Where?

Worked Example.

A neural network for handwritten digit recognition (10 classes):

• Hidden layers: ReLU.
• Output layer: Softmax (gives 10 probabilities summing to 1).
• Loss: Cross-entropy.

A binary classifier (spam / not spam):

• Hidden: ReLU.
• Output: Sigmoid (single probability).
• Loss: Binary cross-entropy.

The Vanishing Gradient Problem.

In deep networks, sigmoid and tanh have very small gradients at the extremes. During backpropagation, these multiply across layers and become tiny — weights of early layers barely update. ReLU avoids this for positive inputs.

Conclusion. Choosing the right activation function is essential for training neural networks effectively. ReLU is the modern default for hidden layers, while sigmoid/softmax are used at the output. The activation function shapes the learning ability of the entire network.