Untitled Quiz

Supervised Learning

• Supervised learning involves a mapping function from input features (X) to output labels (Y)
• Classification: Y is discrete, e.g., Y ∈ {1, 2, ..., k}
• Regression: Y is continuous, e.g., Y ∈ R
• Linear Separability: Ability to separate two classes of data points using a single hyperplane in a feature space.
• A dataset is linearly separable if a hyperplane exists that places all data points of one class on one side and the other class on the opposite side.
• w is the weight vector (defining the hyperplane's orientation).
• x is the input feature vector.
• b is the bias term (defining the hyperplane's position).
• For a dataset to be linearly separable, there must exist a weight vector w and a bias b that satisfies: yi(w•xi + b) > 0 for all i.

Linear Classification

• Perceptron Algorithm: A foundational algorithm for binary classification. It aims to find a linear decision boundary that separates two classes. It iteratively updates weights based on misclassifications.
• f(x) = sign(w•x + b)
• w ∈ Rn is the weight vector.
• b is the bias term.
• Perceptron Algorithm Update Rule: When (xi, yi) is misclassified, update weights and bias: w ← w + nyixi, b ← b + nyi
• where n is the learning rate.

Linear Classification (SVM)

• Support Vector Machine (SVM): Aims to find the maximum margin hyperplane that separates two classes with the largest possible margin.
• The margin is the distance between the decision boundary and the closest data points from either class.
• For correctly classified points, yi(w•xi + b) ≥ 1, for all i.
• The goal is to maximize the margin, which is equivalent to minimizing ||w||^2 / 2.

Linear Regression

• Linear regression models the relationship between input features (X ∈ Rnxp) and target values (y ∈ Rn) as: y = Xβ + e.
• X is the design matrix of input features.
• β is the vector of coefficients.
• e is the error term.
• To estimate β, minimize the sum of squared residuals: minβ ||y – Xβ||^2 = minβ Σ(yi – Xβi)^2, i=1 to n

Weighted Least Square

• In WLS, observations have non-constant variance. The goal is to account for heteroscedasticity giving different weights to different observations, where higher variance gets lower weight.

Ridge Regression

• In OLS, we aim to minimize the residual sum of squares: minβ ||y – Xβ||^2.
• Multicollinearity can cause instability in the inverse (XTX)^-1 making OLS unreliable.
• Ridge Regression addresses multicollinearity by adding a regularization term that penalizes large values of β: minβ ||y – Xβ||^2 + λ||β||^2.
• λ ≥ 0 is the regularization parameter that controls the amount of regularization applied.
• λ = 0 gives the OLS solution.
• λ > 0 penalizes large coefficients, reducing overfitting and addressing multicollinearity.

Limitations of the Perceptron

• Requirement: Linear Separability: The perceptron algorithm only converges if the data is linearly separable.
• Non-linear Separability: Fails on datasets (like XOR) where no linear hyperplane can separate the classes. (May run indefinitely)
• No Margin Optimization: The perceptron does not seek the hyperplane with the largest margin, potentially leading to poor generalization.

Kernel Functions

• Additivity: The sum of two valid kernels is also a valid kernel.
• Scalar Multiplication: The product of a valid kernel and a positive scalar is also a valid kernel.
• Product of Kernels: The product of two valid kernels is also a valid kernel.
• Exponentiation: Raising a valid kernel to a positive power yields another valid kernel.

Kernel Least Squares

• In linear least squares, the model is limited to linear relationships between input features and outputs. To handle non-linear relationships, a feature map (φ(x)) maps the input data into a higher-dimensional space.
• minβ ||y – Φ(X)β||^2

k-Nearest Neighbor (k-NN)

• k-NN is an intuitive, simple, but powerful non-parametric algorithm for both classification and regression tasks.
• k-NN stores the entire training dataset and makes predictions for new data points by comparing them to stored instances. No explicit training occurs.
• k-NN predictions are based on the proximity of new instances to existing ones.

k-Nearest Neighbor - Classification

• In classification, k-NN assigns a class label to the query point (xq) based on the most frequent label (the mode) among its k-nearest neighbors.

k-Nearest Neighbor - Regression

• In regression, k-NN predicts the output based on the average of the target values of the k-nearest neighbors for a query point (xq).
• To improve performance, weighted k-NN may be used where each neighbor's influence is weighted by its distance from the query point.

Decision Tree

• A decision tree is a simple supervised classification model used to classify a single discrete target feature.
• Each internal node performs a Boolean test on an input feature. The edges are labeled with the values of that input feature.
• Each leaf node specifies a value for the target feature.

Decision Tree - Splitting Criteria

• Information Gain: measures the reduction in uncertainty after testing a feature. High gain is preferred.
• Gini Index: Computations are efficient. Preferred in imbalanced datasets. Measures the probability of misclassifying a randomly chosen element from a node. Low index is preferred.

Pre-Pruning (Decision Tree)

• Stopping tree growth early based on criteria that can prevent overfitting
• Maximum Depth: Predefined maximum depth for the tree.
• Minimum Examples at a Leaf: Predefined minimum number of examples needed at a leaf node.
• Minimal Information Gain: Splitting is only done if the associated information gain exceeds a pre-defined threshold value (measure of improvement).
• Reduction in Training Error: Stop splitting if the reduction in training error is below a pre-defined threshold

Post-Pruning (Decision Tree)

• Grow the full tree first and trim it afterwards.
• Restrict attention to nodes that only have leaf nodes as descendants.
• If expected information gain below a threshold, delete children of this node and make a majority decision at that node.

Feedforward Neural Network (FNN)

• Neural networks map input features (X ∈ Rn) to output labels (Y).
• Classification: Y is discrete (e.g., Y ∈ {1, 2, ..., k}).
• Regression: Y is continuous (e.g., Y ∈ R).
• Key components: Layers (depth), Width (number of neurons per layer), Activation function, Loss function (e.g., Mean Squared Error [MSE], Cross-entropy).

Feedforward Neural Network - Backpropagation

• Gradient descent is used to find optimal weights and biases (iteratively) in FNN.
• Optimizers such as Stochastic Gradient Descent(SGD), SGD with momentum, and Adam are used.

Feedforward Neural Network - Activation Functions

• Activation functions introduce non-linearity enabling networks to approximate complex relationships.

CNN

• CNNs are neural networks with convolutional layers.
• Convolution layers extract local features.
• These layers learn filters.
• Filters are repeatedly slid across the image.
• Pooling layers reduce dimensionality.
• CNNs employ a more structured way to process images by using spatial information and sharing weights.

RNN

• RNNs are neural networks designed for processing sequences.
• Key idea: use a hidden state to capture information about the past.
• Layers use shared parameters.
• Recurrent means layers are recurrently influenced by the past to make the output.

RNN Variants: Different Number of Hidden Layers

• RNNs are typically deep nets where the layers share weights. Deeper nets tend to perform better, based on experiments

RNN: Vanishing Gradient Problem

• Problem: training to learn long term dependencies is difficult because of the vanishing gradient problem. (Weights are often too small)
• Exploding gradient leads to difficulty during training.