# Problem Set 2: Linear Discriminant Function and Support Vector Machines
## Name : Mahesh Gosi
## UbitName : mgosi
## Person No. : 50290934


```python
from mlxtend.data import loadlocal_mnist
import numpy as np
import pandas as pd
from matplotlib import pyplot as plt
import cv2 as cv
from sklearn.svm import LinearSVC
```


```python
trainImgs, trainLabels = loadlocal_mnist( 
        images_path='train-images-idx3-ubyte',
        labels_path='train-labels-idx1-ubyte')
testImgs, testLabels = loadlocal_mnist( 
        images_path='t10k-images-idx3-ubyte',
        labels_path='t10k-labels-idx1-ubyte')
trainImgs = trainImgs.reshape(60000, 784)
```

## Part 1 : SVM


```python
C_vals = [0.1, 0.5, 1.0, 2, 3]
accuracy = []
predictLabels = []
for i in range(5):
    Classifer = LinearSVC(C = C_vals[i])
    Classifer.fit(trainImgs, trainLabels)
    predictLabels = Classifer.predict(testImgs)
    accuracy.append((predictLabels == testLabels).sum()/len(predictLabels)*100)
accuracy
```

    /Users/akash/anaconda3/lib/python3.7/site-packages/sklearn/svm/base.py:922: ConvergenceWarning: Liblinear failed to converge, increase the number of iterations.
      "the number of iterations.", ConvergenceWarning)
    /Users/akash/anaconda3/lib/python3.7/site-packages/sklearn/svm/base.py:922: ConvergenceWarning: Liblinear failed to converge, increase the number of iterations.
      "the number of iterations.", ConvergenceWarning)
    /Users/akash/anaconda3/lib/python3.7/site-packages/sklearn/svm/base.py:922: ConvergenceWarning: Liblinear failed to converge, increase the number of iterations.
      "the number of iterations.", ConvergenceWarning)
    /Users/akash/anaconda3/lib/python3.7/site-packages/sklearn/svm/base.py:922: ConvergenceWarning: Liblinear failed to converge, increase the number of iterations.
      "the number of iterations.", ConvergenceWarning)
    /Users/akash/anaconda3/lib/python3.7/site-packages/sklearn/svm/base.py:922: ConvergenceWarning: Liblinear failed to converge, increase the number of iterations.
      "the number of iterations.", ConvergenceWarning)





    [84.56, 85.72, 87.71, 88.66000000000001, 84.37]




```python
for i in range(len(C_vals)):
    print ("Accuracy for " + str(C_vals[i])+ " is : " + str(accuracy[i]))
```

    Accuracy for 0.1 is : 84.56
    Accuracy for 0.5 is : 85.72
    Accuracy for 1.0 is : 87.71
    Accuracy for 2 is : 88.66000000000001
    Accuracy for 3 is : 84.37


Here, we are performing SVM using Linear kernel with the C parameter. The C Parameter tells us how much to avoid misclassifying the training example. 
If we keep a high value of C, the optimizer will choose a smaller marging for the hyperplane. Else, a smaller value will tell the optimizer to find a larger margin separating the hyperplane.


```python
accuracy = []
for i in range(5):
    accuracy.append((predictLabels[i] == testLabels).sum()/len(predictLabels)*100)
accuracy
```




    [175640.0, 170540.0, 173480.0, 175780.0, 173860.0]



## Part 2 : Margin in Primal and Dual Formulation

We have the Lagrange Dual problem with the Primal Problem as follows :
\begin{align}
\text{minimize } \frac{1}{2}w^T.w+C \sum_{n=1}^{N} \xi_{i}
\\
\text{subject to } y_i.(w^T.x_i) \geq {1-\xi_{i}} \text{ and } \xi_i \geq 0 \text{ for i }=1,...,N
\end{align}

We have to minimize this function by maximizing the margin of the primal problem.

The margin is :
 $\gamma = \frac{1}{\sqrt{w^T.w +C \sum_{i=1}^{N} \xi_i }}$
 
We do this by using the Lagrange Function which is given by the following :

Lagrange function :
\begin{align}
{\mathcal{L}} = \frac{1}{2} {\overrightarrow{w}}^T\overrightarrow{w} + C \sum_{i=1}^N\xi_i + \Sigma_i\alpha_i(1-y_i.w^Tx_i -\xi_i) - \sum_{i=1}^N \beta_i \xi_i
\end{align}
\begin{align}
Where, \alpha, \beta \text{ -> Lagrange Multipliers,}\\  \xi\text{  -> Error through separating vector }
\end{align}

Using this we find the Dual Solution. We claim the following <br>
<center>$\underbrace{\underset{\alpha,\beta}{max} \underset{w,\xi}{min} \mathcal{L}}_\text{dual solution} \leq \underbrace{\underset{w,\xi}{min} \underset{\alpha,\beta}{max} \mathcal{L}}_\text{primal solution}$</center>

We find the partial derivative of the Lagrange Function to find the values of <i>w</i> and <i>C</i>

\begin{align}
  \frac{\partial_{\mathcal{L}}}{\partial_w} = w - \sum_i \alpha_i y_i x_i = 0 \implies w = \sum_i \alpha_i y_i \overrightarrow{x_i}
\end{align}
 \begin{align} \frac{\partial_{\mathcal{L}}}{\partial_\xi} = 0 \implies C - \alpha_i - \beta_i = 0
\end{align} 
\begin{align} \implies 0 \leq \alpha_i \leq C \text{ and } \beta_i \geq 0
\end{align}

This shows the multiplier alpha is between 0 and C. 


\begin{align}
\text {By Substituting } w = \sum_i \alpha_i y_i \overrightarrow{x_i}, C=\alpha_i + \beta_i
\text { into Lagrange function, we get the dual problem of maximizing: }
\end{align}

\begin{align}
{\mathcal{L}} = \frac{1}{2} w^T \sum_i \alpha_i y_i \overrightarrow{x_i} + (\alpha_i + \beta_i) \sum_{i=1}^N\xi_i + \Sigma_i\alpha_i(1-y_i.w^Tx_i -\xi_i) - \sum_{i=1}^N \beta_i \xi_i
\\= \frac{1}{2} w^T \sum_i \alpha_i y_i \overrightarrow{x_i} + \alpha_i\sum_{i=1}^N\xi_i + \beta_i \sum_{i=1}^N\xi_i +\sum_i \alpha_i - w^T \sum_i \alpha_i y_i \overrightarrow{x_i} - \sum_i \alpha_i \xi_i - \sum_{i=1}^N \beta_i \xi_i
\end{align}

\begin{align}
\\=\sum_i \alpha_i- \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j (\overrightarrow{x_i}^T x_j )
\end{align}


Hence by substituting the <i>w</i> in the Primal Margin, we get the Dual Margin. With this, we can see the two margins as the following : <br><br>
The primal margin is :
\begin{align}\gamma = \frac{1}{\sqrt{w^T.w +C \sum_{i=1}^{N} \xi_i }}\end{align}
 
The dual margin is :
\begin{align}\gamma = \frac{1}{\sqrt{\alpha_i \alpha_j y_i y_j (x_i^T x_j )}}\end{align}

<b>Benefits of Maximizing the Margin</b> <br>
* Maximizing the margin corresponds to a regularization of SVM weights which will prevent overfitting and underfitting of the model. 
* It makes no low certainty classification decisions. 
* This helps the model to be more generic so that even if more data is added to the model, the margin will be able to classify the samples correctly.

Reference : https://www.quora.com/Why-would-we-prefer-a-large-margin-running-a-SVM

<b>Categorizes of Support Vectors :<br></b>
The SVM Solution has different support vectors which are given by: <br>
* If the vector is lying on the margin boundary $w^Tx = -1$ and $w^Tx = 1 (\text { if } \xi_i = 0)$
* If the vector is lying on the margin region ($0 < \xi < 1$) but on the correct side
* If the vector is on the wrong side of the hyperplane ($\xi \geq 1$)

<b>Benefits of solving Dual Problem instead of Primal Problem</b>
* Solving the dual helps when we have to apply Kernel Trick to classify the data which is not linearly separable. 
* The number of data points is lower than the number of dimensions
* The dual adapts to the amount of available data instead of the dimension.

Reference : https://www.quora.com/Why-is-solving-in-the-dual-easier-than-solving-in-the-primal-What-advantages-do-we-get-from-solving-in-the-dual

## Part 3 : Multi-Class Dual Problem

This is the Primal problem for the Multi-Class Problem :<br>
\begin{equation}
\underset{w_{m}\in H,\xi \in R^l}{min} \frac{1}{2} \sum_{m=1}^{k} w_{m}^{T} w_{m} + C \sum_{i=1}^{l}  \xi_{i}
\end{equation}
<br>
\begin{align}
{\text{subject to,   }}  w_{y_i}^T \varphi(x_i) - w_{t}^{T}\varphi(x_i) \geq 1 - \delta_{y_i,t} - \xi_i
\end{align}
\begin{align}
i = 1,...,l, t \in {1,...,k},
\end{align}

the constraints $\xi_i$ ≥ 0, i = 1,...,l, are implicitly indicated in the margin constraints of when t equals $y_i$.

The resulting Decision function is: 
<br>
\begin{align}
argmax_m f_m(x) = argmax_m w^{T}_{m} \varphi(x)
\end{align}
<br>
In addition, the equation focuses on classification rule, without the bias terms bm, m = 1,...,k. A nonzero bm can be easily modeled by adding an additional constant feature to each x.


```python

```

c2de0f4f67a732f95087d55b10dd33c825291b07
ipynb
Jupyter Notebook
Assignment 2.ipynb
Mgosi/Pattern-Recognition
e4a51b41e3ac0e64456adb629da2e8d8825c6b12
MIT
Assignment 2.ipynb
Mgosi/Pattern-Recognition
e4a51b41e3ac0e64456adb629da2e8d8825c6b12
MIT
Assignment 2.ipynb
Mgosi/Pattern-Recognition
e4a51b41e3ac0e64456adb629da2e8d8825c6b12
MIT
Qwen/Qwen-72B
1. YES
2. YES