Moaz715's picture
el svm bygyb error dlw2ty bs h4of b3den
b587a85
|
Raw History Blame Contribute Delete
6.61 kB

A newer version of the Gradio SDK is available: 6.32.0

Upgrade

🧠 Linear SVM (From Scratch) for MNIST Digit "6" Detection


1. Problem Definition

🎯 Objective

The task is to classify handwritten digits from the MNIST dataset into:

  • Class +1: Digit "6"
  • Class -1: Not digit "6"

🧠 Mathematical Goal

We want to find a hyperplane that best separates the two classes:

⭐ Decision Rule

y^=sign(wβ‹…x+b) \boxed{ \hat{y} = \text{sign}(\mathbf{w} \cdot \mathbf{x} + b) }

πŸ‘‰ If the score is β‰₯ 0 β†’ predict +1 (is 6), else predict -1 (not 6).


2. Input and Output

πŸ“₯ Input Features (X)

Each image is processed as follows:

  1. Flattening (28Γ—28 β†’ 784)
  2. Pixel normalization (values scaled 0β†’1 by dividing by 255)
  3. Standardization (zero mean, unit variance via StandardScaler β€” fit on training data only)

βœ… Final Representation

X=[x1,x2,...,x784] X = [x_1, x_2, ..., x_{784}]


πŸ€– Output (y)

y={+1if digit is 6βˆ’1otherwise y = \begin{cases} +1 & \text{if digit is 6} \\ -1 & \text{otherwise} \end{cases}


3. Mathematical Formulation

🧠 SVM Objective

Minimize the regularized hinge loss:

min⁑w,b12βˆ₯wβˆ₯2+Cβˆ‘i=1nmax⁑(0,1βˆ’yi(wβ‹…xi+b)) \boxed{ \min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^{n} \max(0, 1 - y_i(\mathbf{w} \cdot \mathbf{x}_i + b)) }

  • $\frac{1}{2} |\mathbf{w}|^2$ β€” regularization term (penalizes large weights)
  • $C$ β€” controls trade-off between margin size and classification error
  • $\max(0, 1 - y_i f(\mathbf{x}_i))$ β€” hinge loss (zero if correctly classified with margin)

🧠 Decision Function

f(x)=wβ‹…x+b f(\mathbf{x}) = \mathbf{w} \cdot \mathbf{x} + b


⭐ Hinge Loss

Lhinge=max⁑(0, 1βˆ’yβ‹…f(x)) \boxed{ \mathcal{L}_{\text{hinge}} = \max(0,\ 1 - y \cdot f(\mathbf{x})) }


⚠️ SGD Gradient Update

For each mini-batch, compute gradients and update:

βˆ‚Lβˆ‚w={wβˆ’Cβ‹…yixiif yif(xi)<1wotherwise \frac{\partial \mathcal{L}}{\partial \mathbf{w}} = \begin{cases} \mathbf{w} - C \cdot y_i \mathbf{x}_i & \text{if } y_i f(\mathbf{x}_i) < 1 \\ \mathbf{w} & \text{otherwise} \end{cases}

w←wβˆ’Ξ·β‹…βˆ‚Lβˆ‚wb←bβˆ’Ξ·β‹…βˆ‚Lβˆ‚b \mathbf{w} \leftarrow \mathbf{w} - \eta \cdot \frac{\partial \mathcal{L}}{\partial \mathbf{w}} \qquad b \leftarrow b - \eta \cdot \frac{\partial \mathcal{L}}{\partial b}


βš–οΈ Class Weight Extension

To handle class imbalance (only 9.8% are "6"):

wpos=n2β‹…npos,wneg=n2β‹…nneg \boxed{ w_{\text{pos}} = \frac{n}{2 \cdot n_{\text{pos}}}, \qquad w_{\text{neg}} = \frac{n}{2 \cdot n_{\text{neg}}} }

Weighted hinge loss:

L=12βˆ₯wβˆ₯2+Cβˆ‘i=1nsiβ‹…max⁑(0,1βˆ’yif(xi)) \mathcal{L} = \frac{1}{2}\|\mathbf{w}\|^2 + C \sum_{i=1}^{n} s_i \cdot \max(0, 1 - y_i f(\mathbf{x}_i))

where $s_i$ is the sample weight for each example.


4. Methodology

πŸ“‹ Pipeline

  1. Preprocess images (normalize + standardize)
  2. Split data into train / validation / test (60 / 20 / 20)
  3. Use a dev subset (10,000 samples) for fast hyperparameter search
  4. Tune C and learning rate using validation F1 score
  5. Train final model on full training set with best hyperparameters
  6. Evaluate on test set

5. Proposed Enhancements (Our Contribution)

This work extends standard Linear SVM by:

  • βœ… From-Scratch Implementation
    Full SGD-based SVM built using only NumPy β€” no sklearn

  • βœ… Mini-Batch SGD
    Faster and more stable training than full-batch gradient descent

  • βœ… Class Weighting
    Handles severe imbalance between "6" (9.8%) and "not 6" (90.2%)

  • βœ… Loss History Tracking
    Monitors training loss per epoch to visualize convergence

  • βœ… F1-score Optimization
    Hyperparameter search focuses on F1, not just accuracy


6. Experimental Results

πŸ”₯ Hyperparameter Tuning

Grid search over C and learning rate, evaluated on validation F1:

C Learning Rate Validation F1
0.01 0.0001 0.5371
0.01 0.0005 0.7852
0.01 0.001 0.8354
0.1 0.0001 0.8214
0.1 0.0005 0.8631
0.1 0.001 0.8685
1.0 0.0001 0.8647
1.0 0.0005 0.8704
1.0 0.001 0.8501
10.0 0.0001 0.8595
10.0 0.0005 0.8379
10.0 0.001 0.8137

πŸ† Best: C = 1.0, learning rate = 0.0005, F1 = 0.8704


πŸ§ͺ Final Test Results

Metric Not 6 Is 6
Precision TBD TBD
Recall TBD TBD
F1-score TBD TBD

Accuracy: TBD


7. Results Analysis

🧠 Effect of C (Regularization)

  • Low C (0.01) β†’ strong regularization β†’ underfitting at low learning rates
  • C = 1.0 β†’ best balance between margin maximization and error tolerance
  • High C (10.0) β†’ less regularization β†’ sensitive to learning rate choice

βš–οΈ Effect of Learning Rate

  • Too low (0.0001) β†’ slow convergence, underfits in 50 epochs
  • Too high (0.001 with C=10) β†’ overshoots, degrades performance
  • Best at 0.0005 β†’ stable and converges well

πŸ“‰ Precision vs Recall Trade-off

  • Class weights push the model to recall more "6"s
  • Slightly more false positives as a trade-off
  • F1 score balances both

8. Model Behavior Discussion

🧠 Why Linear SVM Works Here

  • MNIST digit pixels have strong linear separability for binary tasks
  • Standardization ensures all 784 features contribute equally
  • Class weighting compensates for the 9:1 class imbalance
  • The learned weight vector $\mathbf{w}$ can be reshaped to 28Γ—28 to visualize which pixels the model focuses on

⚠️ Limitations

  • Linear kernel only β€” cannot capture non-linear digit patterns
  • Raw pixels used β€” no feature engineering (unlike GNB which uses HOG + PCA)
  • Performance depends on learning rate and C tuning
  • More epochs may be needed for full convergence

9. Model Comparison

Model F1 Score Accuracy Notes
GNB 0.96 0.99 Fast, uses HOG + PCA
Linear SVM (Scratch) 0.87 (val) TBD Raw pixels, no feature engineering
Decision Tree TBD TBD TBD
Logistic Regression TBD TBD TBD

10. Conclusion

Linear SVM from scratch achieved:

  • Strong validation F1 score (~0.87)
  • Stable training with mini-batch SGD
  • Effective handling of class imbalance via sample weighting

Raw pixel features with standardization proved sufficient for a linear classifier, though the lack of feature engineering (HOG/PCA) likely explains the gap compared to GNB.


πŸ’¬ Final Takeaways

  • The decision boundary is a hyperplane in 784-dimensional space
  • Hinge loss penalizes only misclassified or margin-violating points
  • C controls the bias-variance trade-off
  • Class weighting is essential for imbalanced binary classification
  • The weight vector can be visualized as a 28Γ—28 "mental image" of digit 6