7. Machine Learning

What is Machine Learning and how is it different from planning?

• Planning use existing model to make optimal decisions(e.g Search, Games, Bayes Nets, HMMs, MDPs)

• Machine Learning (ML) learns model from data and experiences, including its parameters(probabilities), structure, and hidden concepts (clusters or latent features)

What is classification in Machine Learning?

Classifications predicts a predefined label(class) $y$ from an input $x$

The process is:

Input→ Feature Extraction → ML model → Predicted label

What are features and why are they important?

Features: characteristics of the input that help predict its label. They may be provided, manually designed, or learned from data

• For example, an email’s feature might include sender identity, suspicious words, or capital letters

How does machine learning model learn from data?

It learns patterns between features and known labels using training data(seen examples) , then use those patterns to predict labels for new, unseen data

What is ground truth and how is it used in classification?

Ground truth means the correct label assigned to training examples, often by humans. It tells the model what the correct output should be during learning

What are some examples of classification and their features?

• Spam detection: Email → spam/safe; features include “FREE”, capital letters, dollar amounts, and known sender

• Digital recognition: Image → 0-9; features include pixels, shape, aspect ratio and loops

• Other examples: Symptoms → disease, transaction → fraud/no fraud, essays → grades, reviews → sentiment,images → object type

What is the difference between model-based and instance-based classification?

• Model-based (eager learning): Learns a model, such as Bayes Net, linear discriminator, or tree, and uses it to predict labels. Key challenges are using the structure and parameters

• Instance-based (lazy learning): compares new inputs with stored examples, such as k-nearest neighbors (k-NN)

What is Naïve Bayes Model?

a probabilistic classifier represented by a Bayesian Network with:

• one parent: Label $Y$

• Many children: Features $F_1, F_2, …, F_n$

It uses feature probabilities to predict most likely label

What probability tables must Naïve Bayes learn?

• $P(Y)$: prior probabbility of each label, before observing features

• $P(F_i|Y)$: probability of a feature given a label

There is one conditional probability table per feature

From the Example of Naïve Bayes Net for Spam Filter, define features to form a Bayes’ net

What is the difference between training and inference in Naïve Bayes?

• Training: Learns $P(Y)$ and $P(F_i|Y)$ from labeled data

• Inference: Use the observed features as evidence to calculate $P(Y|F_1,…,F_n)$ and predict a label

How is Naïve Bayes used for spam detection?

The label is spam or safe

Example features:

• $F_1$: is the sender known? (Yes/No → binary feature)

• $F_2$: how many times does “FREE” appear? (0,1,2,… → count feature)

The model learns the probabilities of these features for spam and safe emails

How are conditional probabilities estimated from training data?

Count how often a feature occurs within examples of a particular class, then divide by the total examples in that class

*form in pict

Example from page 17: one of two safe emails contains “FREE” zero times, so the probability is 0.5

How does Naïve Bayes classify a new email?

Extract its features, calculate a score for each label, normalize the scores, and choose the highest probability

For page 20:

$$Spam score= 0.4(0.1)(0.12)=0.0048$$

$$Safescore=0.6(0.7)(0.007)=0.00294$$

After normalization: 14% spam, 86% safe → predict safe

What is main assumption of Naïve Bayes?

All features are conditionally independent

• in other words, once $Y$ is known, knowing one feature does not change the probability of another feature

  *form in pict

• This simplifies the model and makes the number of probability-table entries grow lineraly with the number of features, rather than exponentially

What are the 3 steps of genral Naïve Bayes inference?

1. Calculate the joint probability for each label using the prior and feature probabilities

2. Sum the joint probabilities to get the evidence probability

3. Normalize each label’s score by dividing by that sum

   *form in pict

How does Naïve Bayes recognize handwritten digits?

• A digit image is divided into a pixel grid, such as 16×16, with a feature for each pixel.

• Each pixel becomes on/off unsing an intensity threshold(e.g 0.5)

• The model learns the probability of each pexel being on/off for each digit and predicts te most likely digit

What is Bag-of-Words(BOW) in Naïve Bayes?

Bag-of-Words represent a text using its words without considering their order or context

Each word position $W_i$ is treated as a feature, and the model learns how likely each word is for spam or safe emails.

What assumptions does BOW Naïve Bayes make?

Words are:

• Conditionally independent given the label

• Identically distributed across positions

All word positions share the same $P(W|Y)$ , called tied distributions

Why does BOW Naïve Bayes use log probabilities?

Multiplying many tiny word probabilities produces extremely small numbers. Taking logarithms converts multiplication into addition, making calculations easier and more stable

*form in pict

In the lecture’s email example, the final prediction is approximately 98.9% spam

Why do we divide labeled dataset into 3 sets?

Each set has a different purpose:

• Training set: seen data used to learn model parameters

• Held-out/validation set: Data used to tune hyperparameters and features

• Test set: unseen data used to evaluate final performance

The test set should not be used to tune the model

What are overfitting and generalization?

• Overfitting: a model performs well on training data but poorly on new data

• Generalization: a model learns useful patterns that also work on unseen data

What is parameter estimation?

Learning unknown model values, such as $P(spam)$ , from observed data instead of asking human expert

• Example: If 2 of 3 training emails are spam: $\hat{P}(spam)=\frac{2}{3}$

→ the unknown parameter is often represented by $\theta$

What is Maximum Likelihood Estimation(MLE)?

MLE chooses the parameter value that makes the observed training data most likely

$$\theta^* = arg\max\limits_{\theta} P(D|\theta)$$

For 2 spam and 1 safe email, the lecture uses:

$$L(\theta)=\theta²(1-\theta)$$

the maximum occurs at $\theta=\frac{2}{3}$ . we can also maximize the log-likelihood, which turns products into sums

What is the difference between parameters and hyperparameters?

• Parameters: Values learned from training data, such as probabilities or weight

• Hyperparameters: Settings chosen to control the learning process , such as the Laplace smoothing factor $k$

What is Laplace smoothing and why do we tune it?

Laplace smoothing adds a small pseudocount $k$ to possible outcomes so unseen outcomes do not automatically eeceive zerp probability

*form in pict

Here, $N$ is the sample count and $|X|$ is the number of possible outcomes

• We choose $k$ using validation data, not test set. Larger $k$ generally makes probabilities smoother

Why might we need to tune or add features?

Existing features may miss useful information

• For spam detection, we might add whether the sender is familira, whether the email uses ALL CAPS, whether many people received it, whether links are suspicious, or whether the message addresses the recipient by name

How do we evaluate a classifier and why is a baseline important?

A baseline is a simple method used as a minimum performance comparison, such as always predicting the most common class

• A confusion matrix records:

  • TP: positive correctly predicted

  • TN: negative correctly predicted

  • FP: negative incorrectly predicted as positive

  • FN: positive incorrectly predicted as negative

Common metrics: *form in pict

A high accuracy alone can be misleading when classes are imbalanced. For example, predicting everything as safe might already give 66% accuracy, so 70% may not be impressive.

What is a vector and what is a dot product?

• A vector is a list of numbers representing a point or direction, such as $(2,7,-3,6)$, which has 4 dimensions

• Dot product multiples matching components and adds them:

$$a.b=\sum\limits_{i} a_ib_i = |a||b|cos\theta$$

Positive: Angle less than 90$\degree$

Zero: Angle equal to 90$\degree$

Negative: Angle greater than 90$\degree$

• For fixed vector lengths, a smaller angle means a larger dot product.

What is feature vector in Machine Learning?

A numerical representation of an input’s features

• For an email, the vector might contain counts of “FREE”, misspelling, or whether the sender is known. It allows the model to calculate predictions mathematically

What is perceptron?

A simple linear classifier inspired by a biological neuron. It multiplies input features by learned weights , adds the results, and predicts a class

How does a binary perceptron make a prediction?

Calculate its activation using the dot product:

$$x=w.f(x)=\sum\limits_{i} w_if_i(x)$$

• $z>0$: Predict class +1

• $z<0$: Predict class -1

• For the spam example, +1 represents spam and −1 represents safe. A zero activation lies on the decision boundary and needs a tie-breaking convention.

What do positive and negative weights mean in a perceptron?

A positive weight pushes the prediction toward +1, while a negative weight pushes it toward −1.

For spam filtering, a high positive weight for “FREE” may increase the spam score, while a negative weight for a familiar sender may decrease it.

What is a decision boundary or hyperplane?

The line or higher-dimensional surface that separates predicted classes.

$w.f(x)=0$

One side predicts +1, and the other predicts −1. A bias can shift the boundary away from the origin.

How does a binary perceptron learn its weights?

Start with initial weights, often zero. For each labeled example:

• Correct prediction: Keep the weights.

• Wrong prediction: Adjust the weights toward the correct class.

The update is:

$w_{new}=w_{old}+y^* f(x)$

where $y^*$is the true label, either +1 or −1.

Why do we add or subtract the feature vector during perceptron learning?

• Predicted +1, actually −1: Subtract $f(x)$ to lower the activation.

• Predicted −1, actually +1: Add $f(x)$ to increase the activation.

This works because adding $f(x)$increases the dot product by $||f(x)||²$, while subtracting decreases it by the same amount.

How does a multiclass perceptron classify inputs?

Instead of one weight vector, it uses one weight vector per class.

For each class $y$:

$z_y=w_y.f(x)$

Then choose the class with the highest activation:

$\hat{y}=arg\max\limits_{y} z_y$

How does a multiclass perceptron update weights after a mistake?

If the predicted class is wrong:

• Add the feature vector to the correct class's weights.

• Subtract it from the incorrectly predicted class's weights.

• Leave other class weights unchanged.

This raises the correct class's score and lowers the wrong class's score.

What are the main problems with perceptrons?

• Noisy/non-separable data: A straight boundary cannot correctly separate all examples, so weights may keep changing.

• Mediocre generalization: It may find a boundary that only barely separates training examples.

• Overtraining/overfitting: Training performance improves while validation/test performance eventually worsens.

How can perceptron learning be improved?

The lecture introduces the averaged perceptron, which averages weight vectors over training to reduce unstable changes caused by noisy examples.

It also motivates moving from hard class decisions to probabilistic decisions when data cannot be perfectly separated.

Why do we need probabilistic decisions instead of deterministic decisions?

• A deterministic classifier gives only a fixed class (+1 or −1), even when the data is difficult to separate.

• A probabilistic classifier gives a probability for each class, showing how confident the model is.

→ For example, instead of simply predicting spam, it might predict 90% spam and 10% safe.

What is the difference between a step function and a sigmoid function?

• Step function : Gives a hard decision, 0 or 1.

• Sigmoid function : Gives a smooth probability between 0 and 1.

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

where $z=w.f(x)$

How does the sigmoid function convert activation into probability?

It converts the activation $z$ into the probability of class +1.

• Large positive $z$: Probability approaches 1.

• $z=0$ : Probability equals 0.5.

• Large negative $z$: Probability approaches 0.

For page 64, $w=[-3,4,2]$ and $x=[1,2,0]$ :

$z=-3+8+0=5$

$P(+1|x)=\sigma(5)=0.9933$

So the model predicts 99.33% class +1 and 0.67% class −1.

What is Logistic Regression?

A probabilistic classification model that uses a weighted sum of features and a sigmoid function to predict class probabilities.

Unlike a deterministic perceptron, it provides confidence through probabilities.

How does Maximum Likelihood Estimation train Logistic Regression?

It learns weights that maximize the probability of the correct training labels.

$w^*=arg\max\limits_{w} \prod\limits_{i} P(y_i|x_i,w)$

Usually, we maximize the log-likelihood instead:

$$w^*=arg\max\limits_{w} \sum\limits_{i} logP(y_i|x_i,w)$$

This makes multiplication easier to handle and allows numerical optimization.

Why are probabilistic decisions useful when several decision boundaries are possible?

Different boundaries may classify all training points correctly, but some separate the classes more confidently than others.

Probabilistic models can distinguish between these solutions using the probabilities assigned to correct labels, instead of checking only whether predictions are right or wrong.

What is Multiclass Logistic Regression?

An extension of Logistic Regression for more than two classes.

It assigns a weight vector to each class, calculates each class's activation, then converts the activations into probabilities using softmax.

What is the softmax function?

Softmax converts several class activations into probabilities that sum to 1.

*form in pict

A class with a higher activation receives a higher probability.

How do we calculate multiclass probabilities using softmax?

First calculate the activation for each class, then exponentiate and normalize.

On page 73: $z_1=5, z_2=6, z_3=-2$

The softmax probabilities are approximately:

• Class 1: 0.2689

• Class 2: 0.7310

• Class 3: 0.0002

Therefore, Class 2 is predicted because it has the highest probability.

How is Multiclass Logistic Regression trained using MLE?

It learns a separate weight vector for each class by maximizing the likelihood of the correct labels.

For each training example, calculate the correct class's softmax probability, take its logarithm, and maximize the total log-likelihood.

The slide's example uses Red, Green, and Blue classes, each with its own weight vector.

What is the relationship between sigmoid and softmax?

Sigmoid is a special case of softmax for binary classification.

If there are two classes, Red and Blue, and we set Blue's weight vector to zero:

$P(Red|x)= \frac{e^{w_{red}.x}}{e^{w_{red}.x}+e^0}$

This simplifies to:

$P(Red|x)=\sigma(w_{red}.x)$

So sigmoid handles binary probabilities, while softmax generalizes to multiple classes.