## Problem Set 2: Linear Discriminant Functions and Support Vector Machines

## Introduction
The MNIST database (Modified National Institute of Standards and Technology Database) is a large collection of handwritten digits which happens to be a state of the art data set to train and test machine learning models using image processing.It consist of 60000 Training samples and 10000 Testing Samples. Each sample image consist of normalized $28X28$ pixels grayscale image stored as 784 dimensional vector for each sample.This is a way of dimension reduction done by the MNIST to use it for model developments.

### Preparing the datasets
For loading the given MNIST datasets we will be using the mnist library to fetch the data.The MNIST() function will be used to fetch the datasets from the directory './data'.


```python
import numpy as np
import cv2
from mnist.loader import MNIST
import matplotlib.pyplot as plt
import matplotlib.image as mpimg

m = MNIST('./data')
```

Now we load the different datasets as the X-Training and Y-Training set which has 60000 samples which will be used to train the classification model and then the X-Test and Y-test data set which has 10000 samples will be used to test the model. After seperating the datasets , the data sets will be converted to ND array and as float values which will be benificial for the computations.


```python
xtrain,ytrain = m.load_training()
xtest,ytest = m.load_testing()
xtrain = np.asarray(xtrain).astype(np.float32)
ytrain = np.asarray(ytrain).astype(np.float32)
xtest = np.asarray(xtest).astype(np.float32)
ytest = np.asarray(ytest).astype(np.float32)

```

### Part 1 :Train the Multi Class Support Vector Classifier with 1-Norm and Dot Product Kernel
For training the linear SVM an L1 norm will be used which is the Hinge loss.The training data is normalized before training it to decrease the convergence time and increase accuracy. The SVC Classification minimization function is given as 
\begin{equation}
C\sum_{i=1,n}L(f(x_i),y_i)+\Omega(w)
\end{equation}
Where $C$ is the amount which sets the impact of the regularization. This will be set by the process of cross validation. We will be using the LinearSVC function to fit in the training data to build the SVC Classifier and the StandardScaler function will be used to normalize the input data during training and prediction using the model.


```python
from sklearn.svm import LinearSVC
from sklearn.preprocessing import StandardScaler
scl = StandardScaler()
scl.fit(xtrain)
svc = LinearSVC(loss = 'hinge',C = 1,max_iter = 2000)
# svc.fit(xtrain, ytrain)
svc.fit(scl.transform(xtrain), ytrain)
```

    c:\users\moham\appdata\local\programs\python\python38\lib\site-packages\sklearn\svm\_base.py:946: ConvergenceWarning: Liblinear failed to converge, increase the number of iterations.
      warnings.warn("Liblinear failed to converge, increase "





    LinearSVC(C=1, class_weight=None, dual=True, fit_intercept=True,
              intercept_scaling=1, loss='hinge', max_iter=2000, multi_class='ovr',
              penalty='l2', random_state=None, tol=0.0001, verbose=0)



Through cross validation the $C$ parameter is found to be $1$ when a maximum iteration of 2000 is set to during building the model.We will predict the target values using the SVC Classifier built with the testing sample dataset and then compute the accuracy and error with respect to the true target values. 


```python
ypred = np.zeros(ytest.shape)
xtest_n = scl.transform(xtest)
for i in range(0,ypred.shape[0]):
    x = np.array([xtest_n[i]])
    ypred[i] = svc.predict(x)
true = 0
error = 0
for i in range(0,ytest.shape[0]):
    error = error + ((ytest[i]-ypred[i])**2)**0.5
    if(ytest[i] == ypred[i]):
        true = true+1
        
accuracy = true/ypred.shape[0]
Error = error/ypred.shape[0] 

print('Accuracy - ',accuracy*100,'%')
print('Error - ',Error*100,'%')
```

    Accuracy -  91.82000000000001 %
    Error -  29.79 %


### Part 2 :Lagrange dual problem

The Given Problem is
$Features$ $(x_1,y_1),....(x_N,y_N)$ $where y_1,...y_N\in{-1,1}$ which is also the primal problem is given as 
\begin{equation}
Minimize \; w^T.w+C\sum_{i=1}^N\xi_i \; where 
\\
Subject\;to\;y_i(w^T.x_i)\geq1-\xi_i
\\
and\;\;\xi_i\geq0 
\end{equation}
The inequality constraints can be expressed as 
\begin{equation}
2-y_i(w^T.x_i)-\xi_i\leq0
\\
1-\xi\leq0
\end{equation}
To solve it using the Dual Method we will be converting it to Lagrange form.
The Lagrange form of the problem is given as 
\begin{equation}
L(w,\alpha) = w^T.w+C\sum_{i=1}^N\xi_i + \alpha_1(2-y_i(w^T.x_i)-\xi_i)+\alpha_2(1-\xi)
\end{equation}
where $\alpha_1$ & $\alpha_2$ are the Lagrange Multipliers or the KKT multipliers where $\alpha_i\geq0$.
Set the partial derivative function to Zero.
\begin{equation}
\partial_wL = 2w - \alpha_1y_ix_i= 0
\\
w = \frac{\alpha_1y_ix_i}{2}
\end{equation}
The marigin is given as
\begin{equation}
\gamma = y\frac{w^Tw+b}{||w||}
\end{equation}
In SVM the a criterion is defined by a decision surface that maximally far away from any data point and the distance between the decision surface to the closest data point is called the marigin.The marigin needs to be maximized because the points nearer to the decision surface has high uncertainity with the decision function which classifies the data point where as a large marigin gives low uncertain classifications.This allows to handle small miscalculations and errors in the data sets. 
Solving Dual problem is beneficial over primal problem because in Primal problem we only obtain the optimal $w$ where as in the Dual problem we take $\alpha_i$ in consideration.The $\alpha_i$ is useful because it decides the importance of the subjected features and computation of the classification can be faster than computing the scalar product $w^Tx$ directly in the case of the primal problem.



```python

```

6de11d6764fa4200dccda10c60e50594236ca5f6
ipynb
Jupyter Notebook
MNIST_linear_discriminant_svm.ipynb
fazildgr8/pattern_recognition
4a1636f950458ff57fd413c070758c2288157310
MIT
2020-07-02T23:40:16.000Z
2020-07-02T23:40:16.000Z
MNIST_linear_discriminant_svm.ipynb
fazildgr8/pattern_recognition
4a1636f950458ff57fd413c070758c2288157310
MIT
MNIST_linear_discriminant_svm.ipynb
fazildgr8/pattern_recognition
4a1636f950458ff57fd413c070758c2288157310
MIT
Qwen/Qwen-72B
1. YES
2. YES