File size: 6,611 Bytes
b587a85
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
# 🧠 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

$$
\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 = [x_1, x_2, ..., x_{784}]
$$

---

## πŸ€– Output (y)

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

---

# 3. Mathematical Formulation

## 🧠 SVM Objective

Minimize the regularized hinge loss:

$$
\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(\mathbf{x}) = \mathbf{w} \cdot \mathbf{x} + b
$$

---

## ⭐ Hinge Loss

$$
\boxed{
\mathcal{L}_{\text{hinge}} = \max(0,\ 1 - y \cdot f(\mathbf{x}))
}
$$

---

## ⚠️ SGD Gradient Update

For each mini-batch, compute gradients and update:

$$
\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}
$$

$$
\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"):

$$
\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:

$$
\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