# Exercise 5 - Classification Algorithms (BPNN & SVM)

## a) Back Propogation Neural Network

### Program 1 - Implementing BPNN from scratch

#### AIM
To implement Back Propogation Neural Network from scratch in python.

#### ALGORITHM
##### Forward propogation
###### Single input
$$
\newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}}
\newcommand{\matrix}[1]{\begin{bmatrix}{#1}\end{bmatrix}}
\begin{align*}
\vect{o}_{-1} &= \vect{x}_i\\
\vect{o}_k &= \vect{\phi}_k\left(
\vect{W}_k 
\matrix{ 1 \\ \vect{o}_{k-1}}
\right) &\text{for }k = 0,..,n-1
\end{align*}
$$

###### Batch input
$$
\newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}}
\begin{align*}
\vect{O}_{-1} &= \vect{X}^T\\
\vect{O}_k &= \vect{\phi}_k\left(
\vect{W}_k^T 
\matrix{ \vect{1} \\ \vect{O}_{k-1}}
\right) &\text{for }k = 0,..,n-1
\end{align*}
$$

##### Error
###### Single Input
$$
E = \frac{1}{2}||\vect{o}_{n-1}-\vect{t}||_2
$$
###### Batch Input
$$
E = \frac{1}{2m} \sum_{i=1}^{m} ||\vect{o}^{(i)}_{n-1}-\vect{t}||_2
$$


##### Backward Propogation

###### Single input
$$
\newcommand{\diff}[2]{\frac{\mathrm{d}{#1}}{\mathrm{d}{#2}}}
\begin{align}
\vect{\delta}_{k} &= \diff{E}{\vect{o}_{k}}\circ \vect{\phi}'(\text{net}_{k} )\\
\diff{E}{\vect{o}_{k}} &= \begin{cases}
(\vect{o}_{n-1}-\vect{t}) & k=n-1\\
\vect{W}^T_{k+1}\vect{\delta}_{k+1} & k = n-2,...,-1 \\
\end{cases}\\
\vect{\phi}'(\text{net}_{k}) &= \vect{o}_k \circ (\vect{1}-\vect{o}_k)  \text{ for }   k = n-1,...,0 \\
\end{align}
$$

###### Batch input
$$
\newcommand{\diff}[2]{\frac{\mathrm{d}{#1}}{\mathrm{d}{#2}}}
\begin{align}
\vect{\Delta}_{k} &= \diff{E}{\vect{O}_{k}}\circ \vect{\phi}'(\text{net}_{k} )\\
\diff{E}{\vect{O}_{k}} &= \begin{cases}
(\vect{O}_{n-1}-\vect{T}) & k=n-1\\
\vect{W}_{k+1}^T \vect{\Delta}_{k+1} & k = n-2,...,-1 \\
\end{cases}\\
\vect{\phi}'(\text{net}_{k}) &= \vect{O}_k \circ (\vect{1}-\vect{O}_k)  \text{ for }   k = n-1,...,0 \\
\end{align}
$$

##### Weight Update
###### Single Input
$$
\vect{W}_k := \vect{W}_k - \alpha \diff{E}{\vect{W}_k}\\
\diff{E}{\vect{W}_k} = \vect{\delta}_{k}
\matrix{1 \\ \vect{o}_{k-1}}^T\ \text{for } k = n-1,...,0 \\
$$

###### Batch Input
$$
\vect{W}_k := \vect{W}_k - \alpha \diff{E}{\vect{W}_k}\\
\diff{E}{\vect{W}_k} = \frac{1}{m}\vect{\Delta}_{k}
\matrix{1 \\ \vect{O}_{k-1}}^T \text{for } k = n-1,...,0 \\
$$

where  
$\vect{x}_i$ - the input vector of the  $i$th data point
$\vect{o}_k$ - the output vector of the $k$th layer  
$\vect{\delta}_k$ - the delta vector of the $k$th layer  
$\vect{W}_k$ - the weight matrix of the $k$th layer  
$\vect{X}$ - the batch input matfix  
$\vect{O}_k$ - the batch output matrix of the $k$th layer  
$\vect{\Delta}_k$ - the batch delta matrix of the $k$th layer  

#### Part 1 - Defining class for BPNN


```python
import numpy as np
import pandas as pd
```


```python
class BPNN:
    def __init__(
        self,hidden_layer_sizes,
        l_rate=.001,
        n_epoch=20,
        batch_size=20,
        random_state=0
    ):
        self.hidden_layer_sizes = hidden_layer_sizes
        self.l_rate= float(l_rate)
        self.n_epoch = int(n_epoch)
        self.batch_size = int(batch_size)
        self.random_state = random_state
        
        self.n = len(hidden_layer_sizes)+1
        self.outputs = [None]*(self.n+1)
        self.delta = [None]*self.n
        
        
    def activation(self,x):
        return 1/(1+np.exp(-x))
    
    def d_activation(self,x):
         return x * (1 - x)
    
    def pad_ones(X):
        pad_width = [(1,0),(0,0)]
        return np.pad(X,pad_width=pad_width,constant_values=1)
    
    def inputs(self,i):
        return BPNN.pad_ones(self.outputs[i-1])
    
    def initialize_random_weights(self):
        np.random.seed(self.random_state)
        self.weights = [
            np.random.standard_normal((o,i+1))*.001
            for i,o in zip(
                [self.n_inputs]+self.hidden_layer_sizes,
                self.hidden_layer_sizes+[self.n_outputs]
            )
        ]

    def forward_propagate(self, inputs):
        assert (self.weights is not None),"weights not given"
        self.outputs[-1] = inputs
        for i in range(self.n):
            self.outputs[i] = self.activation(
                self.weights[i] @ self.inputs(i)
            )
        return self.outputs[self.n-1]
    
    def backward_propagate_error(self, target):
        for i in range(self.n-1, -1, -1):
            if i == self.n-1:
                errors = self.outputs[i] - target
            else:
                errors = self.weights[i+1][:,1:].T @ self.delta[i+1] 
            self.delta[i] = errors * self.d_activation(self.outputs[i])

    def update_weights(self):
        for i in range(self.n):
            self.weights[i] -= self.l_rate * self.delta[i] @ self.inputs(i).T/self.batch_size
        
    def error(self,actual,predicted):
        error = actual-predicted
        return np.sum(error * error)
    
    def fit(self, X_train,y_train,verbose=False):
        m = X_train.shape[0]
        input_matrix = X_train.T
        classes = np.unique(y_train)
        target_matrix = (y_train.reshape(-1,1) == classes).T
        self.n_inputs = input_matrix.shape[0]
        self.n_outputs = target_matrix.shape[0]
        self.initialize_random_weights()
        if verbose:
            print("Initial Weights:")
            print(*self.weights,sep="\n")
            print("Training:")
            
        for epoch in range(self.n_epoch):
            sum_error = 0
            fs = range(m+self.batch_size)
            for f,t in zip(fs,fs[1:]):
                outputs = self.forward_propagate(input_matrix[:,f:t])
                sum_error += self.error(target_matrix[:,f:t],outputs)
                self.backward_propagate_error(target_matrix[:,f:t])
                self.update_weights()
            if verbose:
                print(f'> epoch={epoch+1}, lrate={self.l_rate:.3}, error={sum_error/m:.5f}')
        if verbose:
            print("Trained Weights:")
            print(*self.weights,sep="\n")
            
    def predict(self, inputs):
        outputs = self.forward_propagate(inputs.T).T.argmax(axis=-1)
        return outputs

    def accuracy(self,X_test,y_test):
        return (self.predict(X_test)==y_test).mean()
```

#### Part 2 - Loading and processing dataset


```python
titanic_df = pd.read_csv("datasets/titanic_processed.csv")
X = titanic_df.drop('Survived',axis = 1).values
y = titanic_df['Survived'].values
split_ratio = 0.8
s = int(split_ratio*X.shape[0])
X_train, X_test = X[:s],X[s:]
y_train, y_test = y[:s],y[s:]
```

#### Part 3 - Implementing BPNN


```python
b = BPNN(
    hidden_layer_sizes = [5,3],
    l_rate=30, n_epoch=20, batch_size=25,random_state=10
)
b.fit(X_train,y_train,verbose=True)
print("Evaluation:")
print(f"Acuracy of the classifier: {b.accuracy(X_test,y_test)*100:.2f}%")
```

    Initial Weights:
    [[ 1.33158650e-03  7.15278974e-04 -1.54540029e-03 -8.38384993e-06
       6.21335974e-04 -7.20085561e-04  2.65511586e-04  1.08548526e-04
       4.29143093e-06 -1.74600211e-04]
     [ 4.33026190e-04  1.20303737e-03 -9.65065671e-04  1.02827408e-03
       2.28630130e-04  4.45137613e-04 -1.13660221e-03  1.35136878e-04
       1.48453700e-03 -1.07980489e-03]
     [-1.97772828e-03 -1.74337230e-03  2.66070164e-04  2.38496733e-03
       1.12369125e-03  1.67262221e-03  9.91492158e-05  1.39799638e-03
      -2.71247988e-04  6.13204185e-04]
     [-2.67317189e-04 -5.49309014e-04  1.32708296e-04 -4.76142015e-04
       1.30847308e-03  1.95013279e-04  4.00209988e-04 -3.37632337e-04
       1.25647226e-03 -7.31969502e-04]
     [ 6.60231551e-04 -3.50871891e-04 -9.39433360e-04 -4.89337217e-04
      -8.04591142e-04 -2.12697639e-04 -3.39140246e-04  3.12169936e-04
       5.65152670e-04 -1.47420258e-04]]
    [[-2.59053368e-05  2.89094204e-04 -5.39879071e-04  7.08160020e-04
       8.42224738e-04  2.03580797e-04]
     [ 2.39470366e-03  9.17458938e-04 -1.12272471e-04 -3.62180447e-04
      -2.32182256e-04 -5.01728900e-04]
     [ 1.12878515e-03 -6.97810030e-04 -8.11221838e-05 -5.29296081e-04
       1.04618286e-03 -1.41855603e-03]]
    [[-0.0003625  -0.00012191  0.00031936  0.0004609 ]
     [-0.00021579  0.00098907  0.00031475  0.00246765]]
    Training:
    > epoch=1, lrate=30.0, error=0.49515
    > epoch=2, lrate=30.0, error=0.49066
    > epoch=3, lrate=30.0, error=0.44759
    > epoch=4, lrate=30.0, error=0.32836
    > epoch=5, lrate=30.0, error=0.32012
    > epoch=6, lrate=30.0, error=0.31767
    > epoch=7, lrate=30.0, error=0.31607
    > epoch=8, lrate=30.0, error=0.31484
    > epoch=9, lrate=30.0, error=0.31382
    > epoch=10, lrate=30.0, error=0.31292
    > epoch=11, lrate=30.0, error=0.31207
    > epoch=12, lrate=30.0, error=0.31125
    > epoch=13, lrate=30.0, error=0.31043
    > epoch=14, lrate=30.0, error=0.30963
    > epoch=15, lrate=30.0, error=0.30886
    > epoch=16, lrate=30.0, error=0.30816
    > epoch=17, lrate=30.0, error=0.30752
    > epoch=18, lrate=30.0, error=0.30695
    > epoch=19, lrate=30.0, error=0.30645
    > epoch=20, lrate=30.0, error=0.30598
    Trained Weights:
    [[ 2.4976328  -3.27137878 -1.35600823  0.52673885  0.52304233 -3.19704645
       0.39883285 -0.40978078 -0.51246783 -3.54894486]
     [ 2.49858236 -3.27054553 -1.35717467  0.52721097  0.5224186  -3.19489909
       0.39699621 -0.40938148 -0.51440629 -3.54895058]
     [ 2.50036793 -3.27256362 -1.36248268  0.52726938  0.51917641 -3.17240322
       0.39203713 -0.40863187 -0.52741317 -3.5374918 ]
     [ 2.49684424 -3.26991156 -1.35703243  0.52480005  0.52215121 -3.1869823
       0.39638606 -0.41104905 -0.51872859 -3.54117576]
     [ 2.49974609 -3.27394878 -1.35582883  0.52807662  0.52134853 -3.19668184
       0.39856944 -0.4084107  -0.51188295 -3.55207963]]
    [[ 0.97395648 -2.1637305  -2.16450945 -2.15728669 -2.15967589 -2.16477422]
     [ 1.70663229 -2.05598908 -2.05676708 -2.04797014 -2.05198676 -2.05873351]
     [ 1.40632024 -2.09847304 -2.09768519 -2.09035198 -2.09225785 -2.1003679 ]]
    [[-2.60724793  1.55437491  1.68003918  1.61398662]
     [ 2.60724975 -1.55498627 -1.68088901 -1.61254007]]
    Evaluation:
    Acuracy of the classifier: 85.96%


## b) Support Vector Machine

### Program 1 - Implementing SVM from scratch using CVXOPT

#### AIM
To implement SVM from scratch using CVXOPT.

#### Formula
##### SVM statement in dual form
$$
\newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}}
\begin{aligned}
    & \min_{\vect{\alpha}}  \frac{1}{2}  \vect{\alpha}^T  \left( \vect{y}\vect{y}^T \circ (\Phi(\vect{X})\Phi(\vect{X})^T \right)  \vect{\alpha} - \vect{1}^T \vect{\alpha}\\
s.t.&  - \alpha_i \leq 0 \\
    & \alpha_i \leq C\\
    & y^T \vect{\alpha} = 0  
\end{aligned}
$$

##### Standard form of a quadratic program
$$
\begin{aligned}
    & \min_{\vect{x}}  \frac{1}{2}  \vect{x}^T  \vect{P}  \vect{x} - \vect{q}^T\vect{x}\\
s.t.&  \vect{G}\vect{x} \leq \vect{h} \\
    & A \vect{x} = \vect{b} 
\end{aligned}
$$

##### Formulization
$$
\begin{align*}
\vect{P}&= \vect{y}\vect{y}^T \circ \Phi(\vect{X})\Phi(\vect{X})^T
& \vect{q}&= - \vect{1}_n\\
\vect{G}&= \begin{bmatrix}
    \vect{-I}_n\\
    \vect{I}_n
\end{bmatrix} 
& \vect{h}&=\begin{bmatrix}
    C \cdot \vect{1}_n^T\\
    \vect{0}_n^T
\end{bmatrix}\\
\vect{A} &= [\vect{y}] 
&\vect{b} &= [0]\\
\end{align*}
$$

##### Decision Rule
$$
\vect{\hat y} = \mathrm{sign}\left( (\vect{\alpha}^T \circ \vect{y}^T) \Phi(\vect{X})\Phi(\vect{X})^T  + b \right) 
$$

#### Part 1 - Defining class for SVM


```python
import numpy as np
import pandas as pd

from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score

from cvxopt import solvers
from cvxopt import matrix

from scipy.spatial.distance import cdist
```


```python
class SVM:
    def __init__(self,C,kernel):
        self.C = C
        self.kernel = kernel

    def fit(self,X_train,y_train):
        self.scaler = StandardScaler()
        self.X = self.scaler.fit_transform(X_train)
        self.y = y_train.reshape(-1,1)
        
        n=self.X.shape[0]
        I_n = np.eye(n)
        P=(self.y@self.y.T)*self.kernel(self.X,self.X)
        q=np.full(n,-1)
        G=np.vstack((I_n,-1*I_n))
        h=np.hstack((np.full(n,self.C),np.zeros(n)))
        A=y_train.reshape(1,-1)
        b=np.zeros(1)

        P,q,G,h,A,b = map(lambda x : matrix(x,tc="d"),(P,q,G,h,A,b))

        solution = solvers.qp(P, q, G, h, A, b)
        self.a = np.asarray(solution['x']).squeeze()
        
        support_indices = np.logical_and(self.a>=1e-10, self.a<self.C)
        X_S = self.X[support_indices]
        self.b = np.mean(self.y - self.a*self.y.T @ self.kernel(self.X, X_S))

    def predict(self,X_test):
        X_test=self.scaler.transform(X_test)
        return np.sign(self.a*self.y.T @ self.kernel(self.X, X_test) + self.b)

```

#### Part 2 - Defining Radial Basis Function(RBF) Kernel


```python
def rbf_kernel(X1,X2,sigma):
    return np.exp(-cdist(X1, X2, 'sqeuclidean') / (2*sigma**2))
```

#### Part 3 - Loading and Processing Dataset


```python
titanic_df = pd.read_csv('datasets/titanic_processed.csv')
X = titanic_df.drop('Survived',axis = 1).values
y = titanic_df['Survived'].values
y[y==0] = -1
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=0)
```

#### Part 4 - Implementing SVM


```python
from functools import partial 
C = .35
sigma = 2.5
kernel = partial(rbf_kernel,sigma=sigma)

svm_classifier = SVM(C,kernel)
svm_classifier.fit(X_train,y_train)
y_pred = svm_classifier.predict(X_test)
print(f'Accuracy of the classifer: {(y_test == y_pred).mean()*100:.2f}%')

```

         pcost       dcost       gap    pres   dres
     0: -2.1166e+02 -5.8558e+02  6e+03  8e+00  3e-15
     1: -8.8848e+01 -4.9225e+02  6e+02  4e-01  3e-15
     2: -8.4608e+01 -1.3669e+02  5e+01  2e-03  2e-15
     3: -9.2566e+01 -1.1007e+02  2e+01  5e-04  2e-15
     4: -9.5567e+01 -1.0239e+02  7e+00  1e-04  2e-15
     5: -9.6721e+01 -9.9922e+01  3e+00  6e-05  2e-15
     6: -9.7365e+01 -9.8738e+01  1e+00  8e-06  2e-15
     7: -9.7606e+01 -9.8266e+01  7e-01  2e-06  2e-15
     8: -9.7781e+01 -9.7964e+01  2e-01  2e-07  2e-15
     9: -9.7826e+01 -9.7894e+01  7e-02  4e-08  2e-15
    10: -9.7850e+01 -9.7861e+01  1e-02  5e-09  2e-15
    11: -9.7852e+01 -9.7857e+01  4e-03  7e-10  2e-15
    12: -9.7854e+01 -9.7855e+01  1e-03  1e-10  2e-15
    13: -9.7854e+01 -9.7855e+01  2e-04  2e-11  2e-15
    14: -9.7854e+01 -9.7854e+01  4e-05  3e-12  2e-15
    Optimal solution found.
    Accuracy of the classifer: 75.28%


858dd1dd9444b8df3c3d8aedf26570617003e4e2
ipynb
Jupyter Notebook
notebooks/Exercise 5.ipynb
livinNector/machine-learning-lab-exercises
1f638ba437a918aafec95bf26087c39059c9b81d
MIT
2022-03-06T22:13:54.000Z
2022-03-06T22:13:54.000Z
notebooks/Exercise 5.ipynb
msuriya2001/machine-learning-lab-exercises
1f638ba437a918aafec95bf26087c39059c9b81d
MIT
notebooks/Exercise 5.ipynb
msuriya2001/machine-learning-lab-exercises
1f638ba437a918aafec95bf26087c39059c9b81d
MIT
2021-08-24T17:02:11.000Z
2022-03-09T13:19:09.000Z
Qwen/Qwen-72B
1. YES
2. YES