​

(2024-25 EVEN)

UTA027

Artificial Intelligence

​

Machine Learning

(Classification)

Thapar Institute of Engineering and Technology

(Deemed to be University)

Machine Learning

Classification

Raghav B. Venkataramaiyer

Thapar Institute of Engineering and Technology

(Deemed to be University)

Ref

Artificial Intelligence: Structures and Strategies for Complex Problem Solving

By: Luger & Stubblefield

[Download URL]

PRML (Bishop)�[Download URL]

ISL (Hastie/Tibshirani)�[Website]

ITILA (MacKay)�[Website]

Introduction to Prob�[Google Scholar]�[YouTube Playlist]�[YouTube Playlist]

• Classification
• Probability
• Simple Linear Regression (Closed Form Solution)
• Multivariate Case (Closed Form Solution)
• Using Solvers
• Using basis functions.

Notations

Concepts

Set Notation:�{a,b,c,…} (e.g. set of vertices)�{a,b} ≡ {b,a}�{a∈ℕ : a even.}

Vectors:�Row Vectors: (w₁,…,w_M) OR [w₁,…,w_M]�Column Vectors: w = [w₁,…,w_M]^T�Closed/Open Intervals: [a,b],(a,b),[a,b)

Matrices: M (uppercase bold letters)�M×M Identity (Unit) Matrix: I_M� I_M ⊢ I_ij = 1 if i=j; I_ij = 0 if i≠j

Probability:�Expectation: 𝔼[X], Variance: Var(X)�Conditionals: 𝔼_x[f(x)|z], Var_x(f(x)|z)

Set Partition:

Given set S≡{a,b,c,…}

Partitions of S:�S₁,S₂,S₃,…⊆S, ⋃_iS_i=S ⊢�∀i,j i≠j → S_i∩S_j=∅�(pairwise disjoint subsets that span the space)

PS:

1. ⋃_iS_i=S �enforces the spanning property;
2. ∀i,j i≠j → S_i∩S_j=∅�defines the pairwise disjoint condition.

Classification Setup

Coin Sorting

Image Courtesy:

Interesting Engineering

Stamp Sorting

Image Courtesy:

Etsy

Mail Sorting

Image Courtesy:

Gadgets360

Classification

Binary Classification

Binary Classification

Email

Ham / Spam

Camera Feed

Blank / Guest-on-door

Multi-class Classification

Dialogue

Happy, Angry, Fear, Sad, …

Image

Cat, Dog, Car, Cycle, Flower, …

Performance Metrics

Grade A, A-, B, B-, …

Classification Setup

Ground Truth

​

Labels

Classification Setup

Linear Model

Classification Setup

Threshold

​

Criterion

The Setup: Data

The set of observations is called data.

Generally a set of input/output pair�x ≡ [x₁, …, x_D]^T, y∈{0,1}

x is called features/ feature vector.�y is called labels.

x|y=1 is often called positive examples�x|y=0 is often called negative examples

The Setup: Data

The set of observations is called data.

Generally a set of input/output pair�x ≡ [x₁, …, x_D]^T, y∈{0,1}

Example: Email Sorting

Let a dictionary be�ⅆ ≡ {“buy”, “free”, … (D words)}

x ≡ [x₁, …, x_D]^T�represent their corresponding frequency of occurrence in the email.

y=1 indicates email is a spam,�y=0 indicates otherwise.

See Also: �Google Search for TF-IDF�Tutorial (sklearn)�API Reference

features

labels

features

The Setup : Data

x_i: i-th sample in the dataset (say i-th email)

x_i ≡ [x₁⁽ⁱ⁾, …, x_D⁽ⁱ⁾]^T�x_j⁽ⁱ⁾: j-th component (or feature) of the i-th sample in the dataset

​

The Setup : Data

y_i: label of the i-th sample in the dataset.

May also be interpreted probabilistically as,

y_i = P(i-th sample is positive)

​

Example:�y_i = P(i-th email is a spam)

Linear Regression

f(x)∈ℝ

x∈D

For some domain D

Given:

Evidence suggests that �for features x∈D, �the target y∈{0,1}

y=1

Threshold, y=0.5

Linear Regression

Example: Email Sorting

Let a dictionary be�ⅆ ≡ {“buy”, “free”, … (D words)}

x ≡ [x₁, …, x_D]^T�represent their corresponding frequency of occurrence in the email.

y=1 indicates email is a spam,�y=0 indicates otherwise.

Set up w in order to weigh in the relevant word frequencies.

Linear Regression

Implementation (Notebook)

Logistic Regression

σ(z) = 1/(1+e^-z)

x∈D

For some domain D

Given:

Evidence suggests that �for features x∈D, �the target y∈{0,1}

y=1

Threshold, y=0.5

The Setup: Model

y = P(x is positive sample)

The Model

Logistic function

The Training Objective

Cross Entropy of Targets from Predictions

The Training Objective

Assuming y follows the Binomial Distribution �(a series of coin flips)

Recall, that for n trials with m success and success rate p,

​

P(m,n;p) = p^m(1-p)^(n-m)

The Training Objective

The Training Objective

The Update Step

E over the whole population.

(Gradient Descent)

The Update Step

E over a population sample.

(Stochastic Gradient Descent)

The Gradients

The Gradients

The Gradients

Appendix

Probability

What is the probability that I’ll choose a tall person in this hall?

Remember, I haven’t specified ‘today’;�or, when exactly!

Probability

• Outcome: A person in the hall.
• Random Variable: Height of the person (a proxy for outcome).
• Event: A person is tall.
• Probability: The chance of the event that the chosen person is tall.

Random Variable

X

The outcome �of a random process

In this hall,�Choose one person

at random.

Random Process

Random Variable

X,Y

The outcomes of a Random process.

In this hall, choose one person at random.

Let their height be X.

Let their weight be Y.

Random process

Random Variable

BMI, computed as �a function of random variables �Z = f(X,Y)= kY/X² �is also a random variable.

What is probability P?

Ω : Set of all possible outcomes,

(persons in a hall)

Ω

ω∈Ω

What is probability P?

Ω : Set of all possible outcomes

⅀ : Set of Events

σ₁ Very short-highted

σ₂ Short highted

σ₃ Mid height

σ₄ Tall

σ₅ Very tall

⋮

What is probability P?

ω∈Ω

σ∈⅀

P(σ) = |σ| / |Ω|

P : ⅀ →ℝ�Size of the event.

Such that P(Ω)=1

P,Ω,⅀

Probability

• Outcome (ω∈Ω): A person in the hall.
• Random Variable(X): Height of the person (A proxy for outcome).
• Event(σ∈⅀): A person is tall.
• Probability(P[X∈σ]): The chance of event that the chosen person is tall.

Probability

P(X is short) = 0.10 �Probability is related to an event.

Probability

P(5’ < X < 5’1”) = 0.20 �Probability is related to an event.

Probability

Probability of all possible outcomes is 1.

P(X is short�OR X is mid height�OR X is tall) = 1 �

Probability

Probability of all possible outcomes is 1.

P(0<X⩽5’�OR 5’<X⩽5’1”�OR 5’1”<X⩽tallest) = 1 �

Probability Density

P(X=5’) = 1.5

​

Probability density at (and near) X=5’.

Probability Density

P(X=5’) = 1.5

​

Probability density at (and near) X=5’.�near implies continuity

Recall that X=5’ is barely an outcome and a zero size set!

Cumulative Probability

P(X⩽5’) = 0.5

​

So we define an event �X⩽a for all possible values of a.

This notational ambiguity is inherent in literature, and hence we need to disambiguate contextually.