IIT M FOUNDATION DIPLOMA ENDTERM QPD1 07 Aug 2022 IBA NS - 07 Aug 2022

Concepts this paper tests

Auto-generated summary from the source site. Handy as a checklist; the lessons above explain each idea from scratch.

Here’s a structured summary of core topics, concepts, principles, and equations essential for the exam, followed by Mermaid knowledge graphs to visualize relationships.

Core Topics & Concepts

1. Supervised Learning

A. Linear Models

• Perceptron Algorithm

  • Convergence: Independent of learning rate (α) for linearly separable data (Q3).
  • Update rule: $w_{t+1} = w_t + \alpha \cdot (y_i - \hat{y_i}) \cdot x_i$.
  • Decision boundary: $w^T x + b = 0$.

• Linear Regression

  • Loss (MSE): $L(w) = \frac{1}{n} \sum_{i=1}^n (y_i - w^T x_i)^2$ (Q9, Q11).
  • Gradient: $\nabla_w L(w) = \frac{2}{n} \sum_{i=1}^n (w^T x_i - y_i) x_i$.
  • Weighted Loss: $L(w) = \frac{1}{2} \sum_{i=1}^n r_i (w^T x_i - y_i)^2$ → Gradient: $\sum_{i=1}^n r_i (w^T x_i - y_i) x_i$ (Q11).
  • Lasso Regression: $L(w) = \text{MSE} + \lambda \sum |w_j|$ (Q19).

• Logistic Regression

  • Sigmoid: $\sigma(z) = \frac{1}{1 + e^{-z}}$.
  • Loss (Cross-Entropy): $L(w) = -\sum_{i=1}^n [y_i \log(\hat{y_i}) + (1-y_i) \log(1-\hat{y_i})]$.
  • Decision boundary: $w^T x + b = 0$ → $\sigma(w^T x + b) = T$ (threshold) (Q28).
  • Probability interpretation: $P(y=1|x) = \sigma(w^T x)$.

B. Non-Linear Models

• Polynomial Regression

  • Underfitting/Overfitting:

    • Degree 2/3: Underfits (Q17).
    • Degree 6: Smooth fit.
    • Degree 98: Overfits.
  • Bias-Variance Tradeoff.

• Neural Networks

  • Activation Functions:

    • ReLU: $f(z) = \max(0, z)$ (Q6).
    • Sigmoid: $f(z) = \frac{1}{1 + e^{-z}}$.
    • Tanh: $f(z) = \frac{e^z - e^{-z}}{e^z + e^{-z}}$.
    • Softmax: $f(z)_i = \frac{e^{z_i}}{\sum_j e^{z_j}}$.

  • Architecture:

    • Parameters: $\text{Weights} + \text{Biases} = \sum_{l=1}^L (n_l \cdot n_{l-1} + n_l)$ (Q22).

    • Weight matrix $W$:

      • Rows: Outgoing connections from neuron $i$ in layer $l-1$.
      • Columns: Incoming connections to neuron $j$ in layer $l$ (Q26).
  • Invariance: Rotating images (e.g., upside-down) doesn’t degrade performance if trained on rotated data (Q13).

• Support Vector Machines (SVM)

  • Hinge Loss: $L(w) = \max(0, 1 - y_i (w^T x_i + b))$ (Q30).
  • Margin: $\frac{1}{||w||}$.
  • Decision boundary: $w^T x + b = 0$.
  • Probability: For a random point in $[0,1]^2$, probability of class $+1$ is the area where $w^T x + b > 0$ (Q29).

• Decision Trees & Ensembles

  • Decision Trees:

    • Splits: Gini/Entropy (Q5).
    • Regression trees: Predict mean of leaf nodes (Q32, Q33).

  • Random Forest:

    • Feature subsampling: Decreasing $p$ (features per split) reduces correlation between trees (Q8).
    • Performance: Increasing $p$ improves individual tree performance.

  • AdaBoost:

    • Stumps: Weak learners (e.g., split on $X_2$) (Q34, Q35).
    • Sample weights: Updated based on misclassification (higher weight for misclassified samples).

C. Evaluation Metrics

• Classification:

  • Confusion Matrix: TP, TN, FP, FN (Q10).

    • Recall: $\frac{TP}{TP + FN}$.
    • Precision: $\frac{TP}{TP + FP}$.
    • $F_1$-Score: $2 \cdot \frac{\text{Precision} \cdot \text{Recall}}{\text{Precision} + \text{Recall}}$.

  • Relationships:

    • If $F_1$ is fixed, $p_1 > p_2 \implies r_1 < r_2$ (Q14).

• Regression:

  • MSE, $R^2$.

• Clustering:

  • Silhouette Score: $S = \frac{b - a}{\max(a, b)}$, where:

    • $a$: Mean intra-cluster distance.
    • $b$: Mean inter-cluster distance.

  • Interpretation:

    • $S \approx 1$: Well-separated.
    • $S \approx 0$: Overlapping.
    • $S < 0$: Incorrect clustering (Q12).

2. Unsupervised Learning

• K-Means Clustering

  • Manhattan Distance: $d(x, c) = \sum_{i=1}^n |x_i - c_i|$ (Q25).
  • Centroid Update: $c_j = \frac{1}{|C_j|} \sum_{x \in C_j} x$.

• Gaussian Mixture Models (GMM)

  • Not covered in questions, but related to Naive Bayes.

3. Probabilistic Models

• Naive Bayes

  • Gaussian Naive Bayes:

    • Parameters: Mean ($\mu$) and variance ($\sigma^2$) per feature per class.
    • Total parameters: $d \cdot K$ (where $d =$ features, $K =$ classes) (Q21).

  • Multinomial Naive Bayes:

    • For discrete features (e.g., text).

• Multi-Label vs. Multi-Class

  • Multi-Label: Multiple labels per sample (e.g., predict goals in 10 matches) (Q7).
  • Multi-Class: Single label from $K$ classes.

4. Optimization & Loss Functions

• Gradient Descent:

  • Update: $w_{t+1} = w_t - \alpha \nabla_w L(w_t)$.
  • Learning rate ($\alpha$): Affects convergence speed (Q3).

• Regularization:

  • L1 (Lasso): $\lambda ||w||_1$.
  • L2 (Ridge): $\lambda ||w||_2^2$.

5. Model Evaluation & Selection

• Bias-Variance Tradeoff:

  • High bias: Underfitting (e.g., low-degree polynomial).
  • High variance: Overfitting (e.g., high-degree polynomial) (Q17).

• k-NN:

  • $k$: Small $k$ (e.g., $k < 30$) reduces bias but increases variance (Q4).

• Cross-Validation:

  • Train/validation/test splits.

6. Mathematical Foundations

• Linear Algebra:

  • Matrix multiplication: $Xw$ (Q9, Q19).
  • Dot product: $w^T x$.

• Probability:

  • Uniform distribution (Q23, Q29).
  • Conditional probability: $P(y|x)$.

• Calculus:

  • Gradients: $\nabla_w L(w)$ (Q11).

7. Programming (NumPy)

• Array Operations:

  • np.diag, np.arange, np.concatenate (Q15, Q18).
  • Broadcasting: $A @ B$ (matrix multiplication).

• Logical Indexing:

  • np.where(condition, x, y) (Q20).

Key Equations

2. Model Evaluation Metrics

3. Neural Network Components

4. Clustering Algorithms

5. Probabilistic Models

6. Optimization & Regularization

7. k-NN & Model Selection

8. Decision Trees & Ensembles