Unit3 - Subjective Questions

The Perceptron

The Perceptron is one of the simplest artificial neural network architectures, used for binary classification. It models a neuron by taking a weighted sum of inputs and applying a step function (activation function).

Mechanism:

1. Input: A vector of features .
2. Weights: Each feature is multiplied by a weight .
3. Summation: Compute weighted sum .
4. Activation: Apply a step function. If , output 1; otherwise, output 0 (or -1).

Perceptron Update Rule

The weights are updated iteratively to minimize classification error. For a training sample where is the true label and is the predicted label:

Where:

• (eta) is the learning rate.
• is the error term. If prediction is correct, the term is 0, and weights don't change.

Logistic Regression

Despite its name, Logistic Regression is a classification algorithm used to predict the probability that an instance belongs to a specific class. It fits a logical 'S' shape curve to the data rather than a straight line.

The Sigmoid Function

Logistic regression uses the Sigmoid (or Logistic) function to map predicted values to probabilities between 0 and 1.

Formula:

Reasons for use:

1. Bounded Output: It squashes any real-valued number into the range , making it suitable for probability estimation.
2. Differentiability: The function is differentiable, which is crucial for optimization algorithms like Gradient Descent.
3. Decision Boundary: We typically classify an input as positive if .

Derivation of Log Loss

In linear regression, we use Mean Squared Error (MSE), but in logistic regression, the sigmoid function makes MSE non-convex (multiple local minima). Therefore, we use the Log Loss (Cross-Entropy Loss).

For a single training example :

1. If , we want the hypothesis to be close to 1. The cost is .
2. If , we want to be close to 0. The cost is .

Combining these into a single equation:

Global Cost Function ():
Averaging over training examples:

This function is convex, ensuring Gradient Descent converges to the global minimum.

Bayes' Theorem

Bayes' theorem calculates the posterior probability based on the prior probability and the likelihood :

Where is the feature vector .

The 'Naïve' Assumption

Calculating the exact likelihood is computationally expensive because it requires modeling the joint distribution of all features.

The Naïve Bayes classifier assumes that all features are conditionally independent given the class label . This means the presence of one feature does not affect the presence of another.

Mathematical Consequence:

This simplifies the calculation drastically, allowing the model to perform well even with high-dimensional data, despite the assumption rarely being true in real life.

Confusion Matrix

A Confusion Matrix is a tabular layout used to evaluate the performance of a classification model. It compares the predicted labels against the actual labels.

Terminology

1. True Positive (TP):
   • Definition: The model correctly predicted the positive class.
   • Example: Identifying a spam email correctly as spam.
2. True Negative (TN):
   • Definition: The model correctly predicted the negative class.
   • Example: Identifying a normal email correctly as not spam.
3. False Positive (FP) (Type I Error):
   • Definition: The model incorrectly predicted the positive class (it was actually negative).
   • Example: Classifying a normal email as spam.
4. False Negative (FN) (Type II Error):
   • Definition: The model incorrectly predicted the negative class (it was actually positive).
   • Example: Classifying a spam email as normal.

Precision vs. Recall

Precision:

• Definition: Out of all the instances predicted as positive, how many were actually positive?
• Formula:
• Focus: Useful when the cost of False Positives is high (e.g., email spam detection).

Recall (Sensitivity/TPR):

• Definition: Out of all the actual positive instances, how many did the model predict correctly?
• Formula:
• Focus: Useful when the cost of False Negatives is high (e.g., cancer detection).

F1-Score

The F1-Score is the harmonic mean of Precision and Recall. It is used when:

1. There is an uneven class distribution (imbalanced dataset).
2. We seek a balance between Precision and Recall.

K-Nearest Neighbors (K-NN)

K-NN is a non-parametric, distance-based supervised learning algorithm used for classification and regression.

Steps:

1. Choose the number of neighbors, .
2. For a new data point, calculate the distance (e.g., Euclidean) between this point and all training points.
3. Select the points with the smallest distances.
4. Classification: Assign the class that is most frequent (mode) among the neighbors.

Lazy Learner

K-NN is called a Lazy Learner because:

• No Training Phase: It does not learn a discriminative function () from the training data during a training phase.
• Storage: It simply stores the training dataset.
• Delayed Computation: All computations are deferred until the time of prediction (inference). This makes training fast (zero time) but prediction slow compared to Eager Learners like Logistic Regression.

The choice of significantly impacts the bias-variance trade-off in K-NN.

1. Small K (e.g., K=1 or K=2):

• Behavior: The model becomes very sensitive to local patterns and noise in the data.
• Decision Boundary: The boundary is jagged and complex.
• Outcome: High Variance, Low Bias. This leads to Overfitting.

2. Large K:

• Behavior: The model considers a large number of neighbors, effectively averaging out the noise but potentially missing local patterns.
• Decision Boundary: The boundary becomes smoother and more linear.
• Outcome: Low Variance, High Bias. This leads to Underfitting.

Selection: The optimal is usually selected via techniques like Cross-Validation.

Decision Trees use metrics to determine the best attribute to split the data at each node. ID3 algorithm uses Entropy and Information Gain.

Entropy

Entropy measures the impurity or randomness in a dataset . If a dataset contains only one class, entropy is 0. If classes are balanced, entropy is 1.

Formula:

Information Gain (IG)

Information Gain measures the reduction in entropy achieved by splitting the dataset on a specific attribute . The tree selects the attribute with the highest IG.

Formula:

Where:

• is the entropy of the parent set.
• is the subset of where attribute has value .
• We subtract the weighted average entropy of the children from the parent's entropy.

Pruning is a technique to reduce the size of decision trees to prevent overfitting.

Support Vector Machine (SVM)

SVM is a supervised learning model used for classification and regression. The core intuition is to find a hyperplane in an N-dimensional space that distinctly classifies the data points.

Goal:
Among many possible hyperplanes that separate classes, SVM chooses the one that maximizes the Margin.

Margin:
The distance between the hyperplane and the nearest data point from either class. Maximizing this margin improves the model's generalization ability.

Support Vectors

• Support vectors are the data points that lie closest to the decision boundary (hyperplane).
• They are the most difficult points to classify.
• These points effectively "support" or define the orientation and position of the hyperplane.
• If we remove other data points, the hyperplane does not change. If we move a support vector, the hyperplane shifts.

The Problem

Standard SVM seeks a linear decision boundary. However, many real-world datasets are not linearly separable (e.g., concentric circles of data).

The Kernel Trick

The Kernel Trick is a mathematical technique that allows SVM to classify non-linear data without explicitly transforming the data into higher dimensions.

It computes the dot product of data points in a high-dimensional feature space without actually calculating the coordinates in that space. This avoids the high computational cost (Curse of Dimensionality).

Common Kernels:

1. Linear Kernel: For linearly separable data.
2. Polynomial Kernel: Maps to polynomial dimensions.
3. RBF (Radial Basis Function): Maps to infinite-dimensional space.

Utility:
It allows algorithms like SVM to fit complex, non-linear boundaries efficiently.

ROC Curve (Receiver Operating Characteristic)

The ROC curve is a graphical plot that illustrates the diagnostic ability of a binary classifier system as its discrimination threshold is varied.

• X-axis: False Positive Rate ()
• Y-axis: True Positive Rate ()

A curve closer to the top-left corner indicates a better model (High TPR, Low FPR).

ROC-AUC (Area Under the Curve)

• Definition: AUC represents the degree or measure of separability. It tells how much the model is capable of distinguishing between classes.
• Range: 0 to 1.
  • : Random guessing (no discrimination).
  • : Perfect classifier.
  • : Reciprocating the classes (predicting 0 as 1 and vice versa).

It helps evaluate model performance independent of the specific threshold chosen for classification.

Comparison

1. Axes:

   • ROC: Plots TPR (Recall) vs. FPR.
   • PR Curve: Plots Precision vs. Recall (TPR).

2. Baseline:

   • ROC: The baseline (random guess) is a diagonal line from (0,0) to (1,1).
   • PR: The baseline depends on the class distribution (ratio of positives).

When to use PR Curve (AUC-PR)?

The ROC curve can be misleading when the dataset is heavily imbalanced (e.g., Fraud Detection where 99% are valid, 1% fraud).

• ROC behavior in imbalance: The False Positive Rate (FPR) uses True Negatives in the denominator (). If TN is huge (many negatives), FPR stays low even if FP increases, making the model look better than it is.
• PR Curve behavior: Precision () does not use True Negatives. It focuses strictly on how well the minority class is detected.

Conclusion: Use PR Curve when the positive class is rare or more important than the negative class.

Zero Frequency Problem

In Naïve Bayes, if a specific categorical feature value occurs in the test set but was never seen in the training set for a particular class, the probability estimate becomes zero.

Since Naïve Bayes multiplies probabilities (), a single zero turns the entire posterior probability to zero, effectively wiping out all other information provided by other features.

Laplace Smoothing (Additive Smoothing)

To solve this, we add a small smoothing parameter (usually 1) to the count of every feature value.

Formula:

Where:

• : Smoothing parameter.
• : Number of distinct values feature can take.

This ensures no probability is ever exactly zero, allowing the model to make predictions based on other available features.

Parametric Models

• Definition: These models make strong assumptions about the functional form of the data distribution. They have a fixed number of parameters, regardless of the training data size.
• Pros: Simpler, faster training and inference, less data required.
• Cons: Limited complexity; cannot learn complex patterns if the assumption is wrong (high bias).
• Examples:
  • Logistic Regression: Assumes a linear decision boundary separated by a sigmoid curve.
  • Linear Perceptron.

Non-parametric Models

• Definition: These models do not make strong assumptions about the mapping function. The number of parameters effectively grows with the amount of training data.
• Pros: Flexible; can fit any functional form (low bias).
• Cons: Requires more data; slower training/inference; higher risk of overfitting.
• Examples:
  • K-Nearest Neighbors (KNN): Stores all data points.
  • Decision Trees: Can grow very deep/complex.
  • SVM with RBF Kernel: Infinite dimensional mapping.

Discriminative Models (e.g., Logistic Regression)

• Goal: Model the decision boundary directly.
• Probability: Learns the conditional probability directly from the data.
• Focus: It focuses on finding the boundary that separates the classes.
• Analogy: To distinguish between a cat and a dog, it looks for specific differences (e.g., whiskers, ear shape).

Generative Models (e.g., Naïve Bayes)

• Goal: Model the distribution of individual classes.
• Probability: Learns the joint probability (usually by learning and ) and then uses Bayes rule to find .
• Focus: It tries to understand how the data is generated for each class.
• Analogy: It builds a model of what a cat looks like and what a dog looks like. When a new animal comes, it matches it against both models to see which one fits best.

Gini Impurity

Gini Impurity is an alternative metric to Entropy used by the CART (Classification and Regression Trees) algorithm for splitting nodes.

It measures the likelihood of an incorrect classification of a new instance of a random variable, if that new instance were randomly classified according to the distribution of class labels from the dataset.

Formula:

Difference from Entropy

1. Computation: Entropy involves logarithmic calculations (), which are computationally more expensive than the squaring operations used in Gini Impurity.
2. Range:
   • Entropy range: (for binary classification).
   • Gini range: (for binary classification).
3. Result: In practice, they usually result in very similar trees. However, Gini tends to isolate the most frequent class in its own branch of the tree, while Entropy tends to produce slightly more balanced trees.

Supervised Learning

Supervised learning is a type of machine learning where the algorithm is trained on a labeled dataset. The model learns a mapping function from input variables to output variables ().

Goal: Approximate the mapping function so well that when you have new input data (), you can predict the output variables () for that data.

Steps involved:

1. Data Collection: Gather a dataset containing inputs (features) and corresponding correct outputs (labels).
2. Data Preprocessing: Clean, normalize, and split data into Training and Testing sets.
3. Model Selection: Choose an appropriate algorithm (e.g., SVM, Decision Tree) based on the problem type.
4. Training: The algorithm processes the training data to minimize a loss function (learning the weights/parameters).
5. Evaluation: Test the model on unseen data using metrics like Accuracy, Precision, Recall.
6. Tuning: Adjust hyperparameters to improve performance.

Advantages

1. Interpretability: They are easy to understand and visualize (white-box model). The rules can be explained to non-technical stakeholders.
2. No Normalization: They require very little data preprocessing (scaling or normalization of features is not needed).
3. Non-linear relationships: Can handle both numerical and categorical data and model non-linear boundaries effectively.

Disadvantages

1. Overfitting: Trees can create overly complex models that do not generalize well (solved by pruning).
2. Instability: Small variations in the data can result in a completely different tree being generated (High Variance).
3. Bias: Decision tree learners can create biased trees if some classes dominate (solved by balancing the dataset).