Machine Learning (AD-502) Unit 3 Notes - RGPV

How unit 3 is examined

This unit covers the main classifiers and how to score them; decision trees, K-NN, logistic regression and classification accuracy carry the marks.

Logistic Regression

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Logistic regression is a supervised classification algorithm that passes a linear combination of the features through the sigmoid function to output the probability that an instance belongs to a class.</mark>

Formula. $z = w_0 + w_1x_1 + \dots + w_nx_n$, and $P(y=1\mid x) = \sigma(z) = \dfrac{1}{1+e^{-z}}$.

Key points.

It is used for binary classification, and for multiclass problems through one-vs-rest or softmax.
The sigmoid squashes any real value $z$ into the range 0 to 1, so the output is read as a probability of class membership; for example $z=1$ gives $\sigma(1)=0.73$.
A decision threshold, usually 0.5, converts the probability into a class label: predict 1 if $P \ge 0.5$, else 0.
The weights are learned by minimising the log-loss (cross-entropy) cost $J = -\frac{1}{m}\sum [y\log p + (1-y)\log(1-p)]$ using gradient descent.
The decision boundary $z=0$ is linear, so it works well only for roughly linearly separable classes.

Asked: [7 marks] (Nov 2023) Explain the concept of logistic regression in classification. How does it model the probability of class membership?

Decision Tree Classification

Definition. <mark>A decision tree is a supervised model that classifies an instance by asking a series of feature tests arranged as a tree, from the root down to a leaf that holds the class label.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 608 258" width="608" height="258" role="img" aria-label="Decision tree: root node, internal nodes (tests), branches (outcomes), leaves (class labels)"><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="289.3" y1="37" x2="110.8" y2="101"/><line class="e" x1="289.3" y1="37" x2="296" y2="101"/><line class="e" x1="289.3" y1="37" x2="467.8" y2="101"/><line class="e" x1="110.8" y1="101" x2="110.8" y2="165"/><line class="e" x1="110.8" y1="165" x2="55.5" y2="229"/><line class="e" x1="110.8" y1="165" x2="166" y2="229"/><line class="e" x1="467.8" y1="101" x2="467.8" y2="165"/><line class="e" x1="467.8" y1="165" x2="414.5" y2="229"/><line class="e" x1="467.8" y1="165" x2="521" y2="229"/><rect class="n" x="247.8" y="22" width="83" height="30" rx="8"/><text class="t" x="289.3" y="37" dy=".35em" text-anchor="middle">Outlook?</text><rect class="n" x="81.3" y="86" width="59" height="30" rx="8"/><text class="t" x="110.8" y="101" dy=".35em" text-anchor="middle">Sunny</text><rect class="n" x="77.3" y="150" width="67" height="30" rx="8"/><text class="t" x="110.8" y="165" dy=".35em" text-anchor="middle">Humid?</text><rect class="n" x="14" y="214" width="83" height="30" rx="8"/><text class="t" x="55.5" y="229" dy=".35em" text-anchor="middle">High: No</text><rect class="n" x="113" y="214" width="106" height="30" rx="8"/><text class="t" x="166" y="229" dy=".35em" text-anchor="middle">Normal: Yes</text><rect class="n" x="235" y="86" width="122" height="30" rx="8"/><text class="t" x="296" y="101" dy=".35em" text-anchor="middle">Overcast: Yes</text><rect class="n" x="441.8" y="86" width="52" height="30" rx="8"/><text class="t" x="467.8" y="101" dy=".35em" text-anchor="middle">Rain</text><rect class="n" x="434.3" y="150" width="67" height="30" rx="8"/><text class="t" x="467.8" y="165" dy=".35em" text-anchor="middle">Windy?</text><rect class="n" x="373" y="214" width="83" height="30" rx="8"/><text class="t" x="414.5" y="229" dy=".35em" text-anchor="middle">True: No</text><rect class="n" x="472" y="214" width="98" height="30" rx="8"/><text class="t" x="521" y="229" dy=".35em" text-anchor="middle">False: Yes</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Decision tree: root node, internal nodes (tests), branches (outcomes), leaves (class labels)</figcaption></figure>

Key points.

The structure has a root node (first test), internal nodes (feature tests), branches (test outcomes) and leaf nodes (class labels).
The tree is built top-down and recursively: at each node the feature giving the purest split is chosen, the data is divided, and the process repeats on each child.
Purity is measured by an impurity measure: Gini $=1-\sum p_i^2$ or entropy $=-\sum p_i\log_2 p_i$; information gain is the drop in entropy after the split.
Example: 9 Yes and 5 No give Gini $=1-(9/14)^2-(5/14)^2=0.459$ and entropy $=0.940$.
Growth stops when a node is pure, the depth limit is reached, or too few samples remain.
Prediction traverses from the root to a leaf by following the branch that matches each feature value.
Advantages: it is easy to interpret, handles nonlinear boundaries and mixed numeric and categorical data, and needs little preparation.
Disadvantages: deep trees overfit, small data changes give a different tree (instability), and greedy splits are not globally optimal. Axis-parallel splits approximate a complex boundary only with many steps, so depth grows. Pruning, depth limits and ensembles (random forest) reduce this.

Answer frame. Open with the definition; draw the tree with root, branches and leaves labelled; develop points 1-6 for the construction question; close with "prediction is a root-to-leaf traversal". For the advantages question, use a two-column table from points 7-8, add the effect of depth on complex boundaries and close with pruning and ensembles.

Asked: [7 marks] (Nov 2023) Describe decision tree classification and how it constructs a tree-based model for classification tasks. Asked: [7 marks] (Nov 2023) Discuss the advantages and disadvantages of decision trees in handling complex decision boundaries.

Neural Network

Definition. <mark>An artificial neural network is a model made of layers of connected neurons that learns a mapping from inputs to outputs by adjusting weights.</mark>

Key points.

A neuron computes $a=f\left(\sum w_ix_i+b\right)$, where $f$ is an activation such as sigmoid or ReLU.
A multilayer perceptron has an input layer, one or more hidden layers and an output layer.
Training uses forward propagation to predict, then backpropagation with gradient descent to update weights and reduce the loss.
Hidden layers with nonlinear activations let it learn nonlinear boundaries.

K-Nearest Neighbors (K-NN)

Definition. <mark>K-NN is a supervised, lazy, instance-based algorithm that classifies a new point by the majority class among its K nearest labelled training points.</mark>

Formula. Euclidean distance $d(x,y)=\sqrt{\sum_{i}(x_i-y_i)^2}$; for $(0,0)$ and $(3,4)$, $d=5$.

Key points.

K-NN is supervised because it needs labelled training data; it is lazy because it builds no model and only stores the data.
To predict, it computes the distance from the new point to all training points, picks the K nearest and takes a majority vote; with K=3 and neighbours A, A, B the label is A.
A small K is sensitive to noise and overfits; a large K smooths the boundary but may underfit, so an odd K chosen by cross-validation is used.
Pros: simple, no training time, adapts to new data. Cons: slow prediction, needs feature scaling and suffers in high dimensions.

Asked: [9 marks] (Nov 2022) Is K-NN algorithm is supervised. Explain in detail.

Support Vector Machine

Definition. <mark>A support vector machine is a supervised classifier that finds the hyperplane separating the classes with the maximum margin.</mark>

Key points.

The hyperplane is $w\cdot x+b=0$; the margin is $2/\lVert w\rVert$, and maximising it means minimising $\lVert w\rVert$.
Support vectors are the points closest to the hyperplane; only they define it.
A soft margin with parameter C allows some misclassification for noisy data.
The kernel trick (linear, polynomial, RBF) handles nonlinear data by mapping it to a higher dimension.

Naive Bayes (Gaussian, Multinomial, Bernoulli)

Definition. <mark>Naive Bayes is a probabilistic classifier based on Bayes' theorem that assumes the features are independent given the class.</mark>

Key points.

Bayes' theorem: $P(C\mid X)=\dfrac{P(X\mid C)P(C)}{P(X)}$; the class with the highest posterior is predicted.
The naive assumption gives $P(X\mid C)=\prod_i P(x_i\mid C)$, which keeps it fast and simple.
Gaussian NB is for continuous features assumed normal; Multinomial NB for counts such as word frequencies; Bernoulli NB for binary features such as word present or absent.
It works well for text and spam filtering even when the independence assumption is only roughly true.

Performance Measures: Confusion Matrix, Classification Accuracy, Classification Report

Definition. <mark>Classification accuracy is the fraction of all predictions that are correct: (TP+TN)/(TP+TN+FP+FN).</mark>

Diagram.

	Predicted Positive	Predicted Negative
Actual Positive	TP	FN
Actual Negative	FP	TN

Formula. Precision $=\frac{TP}{TP+FP}$; Recall $=\frac{TP}{TP+FN}$; F1 $=\frac{2PR}{P+R}$; Support is the number of true instances of each class.

Example. TP=50, FP=10, FN=5, TN=35: accuracy $=85/100=0.85$, precision $=0.833$, recall $=0.909$, F1 $=0.870$.

Key points.

The confusion matrix tabulates actual against predicted classes, and every measure is computed from its four cells.
Accuracy misleads on imbalanced data: a model predicting always "no" on 95% negative data scores 95% yet finds no positives.
The classification report lists precision, recall, F1 and support per class, so it shows what accuracy hides.

Asked: [5 marks] (Nov 2022) Write a note on Classification Accuracy.

Last-minute revision

Logistic regression: $\sigma(z)=1/(1+e^{-z})$, threshold 0.5, log-loss cost, linear boundary.
Decision tree: root, internal nodes, branches, leaves; split by Gini or entropy, top-down and recursive.
Gini $=1-\sum p_i^2$; entropy $=-\sum p_i\log_2p_i$; 9 Yes/5 No gives 0.459 and 0.940.
Trees overfit and are unstable; fix with pruning and ensembles.
K-NN: supervised, lazy, instance-based; majority vote of K neighbours; Euclidean distance.
Small K overfits, large K underfits; scale features.
Neural network: weighted sum, activation, backpropagation.
SVM: maximum-margin hyperplane, support vectors, kernel trick.
Naive Bayes: Bayes' theorem plus feature independence; Gaussian, Multinomial, Bernoulli.
Accuracy $=(TP+TN)/\text{total}$; precision $=TP/(TP+FP)$; recall $=TP/(TP+FN)$.
F1 is the harmonic mean of precision and recall; support is the class count.

Memory hooks

Sigmoid squashes to 0-1: "S-shape means probability".
Tree parts: Root, Branch, Leaf, like a real tree upside down.
K-NN is lazy: "no training, all work at prediction time".
SVM: "widest street between classes".
Precision looks at what you predicted positive, recall at what was actually positive.

Coverage checklist

Logistic Regression: Nov 2023 logistic regression question.
Decision Tree Classification: Nov 2023 construction question; Nov 2023 advantages and disadvantages question.
Neural Network: no past questions.
K-Nearest Neighbors (K-NN): Nov 2022 supervised K-NN question.
Support Vector Machine: no past questions.
Naive Bayes (Gaussian, Multinomial, Bernoulli): no past questions.
Performance Measures: Confusion Matrix, Classification Accuracy, Classification Report: Precisions, Recall, F1 score and Support: Nov 2022 classification accuracy note.

Account

Machine Learning (AD-502) - Unit 3 Short Notes

How unit 3 is examined

Logistic Regression

Decision Tree Classification

Neural Network

K-Nearest Neighbors (K-NN)

Support Vector Machine

Naive Bayes (Gaussian, Multinomial, Bernoulli)

Performance Measures: Confusion Matrix, Classification Accuracy, Classification Report

Last-minute revision

Memory hooks

Coverage checklist