# Support Vector Machines (SVM)

Le __[Support Vector Machines](https://it.wikipedia.org/wiki/Macchine_a_vettori_di_supporto)__ sono un **algoritmo di machine learning supervisionato in grado sia di fare classificazione binaria e di fare regressione, risulta anche essere in grado di essere robusto agli** __[outliers](https://en.wikipedia.org/wiki/Outlier)__ **ovvero dati che sono molto diversi dalle altre osservazioni precedenti per possibili errori o condizioni diversi**.<br>
Il funzionamento di queste macchine su basa su un principio piuttosto semplice, quando noi effettuiamo una classificazione binaria quello che definiamo è un sottospazio detto __[iperpiano](https://it.wikipedia.org/wiki/Iperpiano)__ attraverso cui riusciamo a definire due regioni dello spazio a cui noi possiamo associare una delle due classi, se per esempio siamo in uno spazio 2d con dei dati quello che possiamo fare è associare una linea in grado di dirci che se i punti sono a sinistra o a destra di esso allora abbiamo una classe determinabile dai punti usati per definire l'iperpiano attraverso il training.<br>
Ora però abbiamo un problema, **qualora fosse possibile definire un'iperpiano(*hyperplane in inglese*) quello che potremmo trovarci è che ne esiste più di uno, allora come fare a scegliere il migliore?**<br>

<center>  </center>

## Maximum Margin Optimization
In genere l'iperpiano migliore è quello che riesce a massimizzare la distanza dall'iperpiano ai punti della classi, detto anche margine in matematica, abbiamo quindi un problema di __[massimizzazione margine dell'iperpiano](https://www.sciencedirect.com/topics/computer-science/maximum-margin-hyperplane)__, in genere per risolvere questo problema si usano i **vettori di supporto(support vectors) ovvero i vettori ottenuti dalla distanza dell'iperpiano ai punti più vicini ad esso**.<br>
Tradotto in fotmule matematiche noi abbiamo:

\begin{equation}
\Large w^{T}x + b = 0 \quad Hyperplane\\
\Large \frac{1}{\Vert w \Vert} \quad Margin (\Vert w \Vert \;is\; the\; norm\; of\; w)\\
\Large |w^{T}x + b| = 1 \quad classification
\end{equation}

Ora utilizzando la condizione di massimizzare il margine dell'iperpiano contando la capacità di classificare otteniamo il seguente problema:

\begin{equation}
\Large Maximize \quad \frac{1}{\Vert w \Vert} \, subject \, to \, \min_{n = 1,2,..,N} |w^{T}x + b| = 1
\end{equation}

che è possibile tradurre in:

\begin{equation}
\Large Minimize \quad \frac{w^{T}w}{2} \, subject \, to \, y_n(w^{T}x_n + b) \geqslant 1 \quad with \; n = 1,2,..,N \, and \, y_n \in [-1,1]
\end{equation}

Usando le condizioni di __[KKT](https://it.wikipedia.org/wiki/Condizioni_di_Karush-Kuhn-Tucker)__ e imponendo la minimizzazione si ottiene la seguente formula di massimizzazione:

\begin{equation}
\Large Maximize \; \mathcal{L}(\alpha) = \sum_{n=1}^{N} \alpha_n -\frac{1}{2} \sum_{n=1}^{N} \sum_{m=1}^{N} y_n y_m \alpha_n \alpha_m x^{T}_{n} x_{m}\\
\Large subject\, to \ , \alpha_n \geqslant 0 \,  for \, n = 1,..N \, and \,  \sum_{n=1}^{N} \alpha_n y_n = 0 \\
\Large If \; y_n(w^{T}x_n + b) = 1 \; then \; x_n \; is \; a \; support \; vector
\end{equation}

quindi il termine $\alpha$  sarebbe un termine che influisce sulla creazione del margine ed è definibile dal training sui dati.  

## Il problema degli outlier

Abbiamo però il problema che fino ad ora abbiamo ipotizzato che non ci fossero outlier e che quindi non ci fosser dati "strani", **se però per esempio ipotizziamo che un dato è stato classificato male, ovvero è un outlier, ma poichè presenta tutte le caratteristiche dell'altra classe sappiamo che è stato classificato male, dobbiamo allora fare in modo che l'algoritmo ne tenga conto al fine di poter generalizzare meglio in seguito**, in tal caso quello che possiamo fare è introdurre un ***termine di violazione del margine tale che il nostro margine diventi "soft" ovvero permetta la sua violazione, in tal modo avremo la possibilità di permettere ad alcuni punti di essere outliers".

Dal punto di vista matematico quello che succede è: 

\begin{equation}
\Large Minimize \quad \frac{w^{T}w}{2} + C \sum_{i=1}^{N} \xi_n \quad subject \; to \; y_n(w^{T}x_n + b) \geqslant 1 - \xi_n, \; \xi_n \geqslant 0
\end{equation}

dove il termine $\xi$ rappresenta la violazione del dato nella violazione del margine, ora dal punto di vista della loss function essa diventa usando sempre __[KKT](https://it.wikipedia.org/wiki/Condizioni_di_Karush-Kuhn-Tucker)__:

\begin{equation}
\Large Maximize \; \mathcal{L}(\alpha) = \sum_{n=1}^{N} \alpha_n -\frac{1}{2} \sum_{n=1}^{N} \sum_{m=1}^{N} y_n y_m \alpha_n \alpha_m x^{T}_{n} x_{m}\\
\Large subject\, to \ , 0 \geqslant \alpha_n \geqslant C \,  for \, n = 1,..N \, and \,  \sum_{n=1}^{N} \alpha_n y_n = 0 \\
\end{equation}

Notate bene che in questa formula $\alpha$ non deve essere solo positiva come nel caso precedente, ma deve essere superiormente limitata da $C$ che ora è diventato il nostro termine di regoralizzazione sulla quale abbiamo imposto quanto pesa la nostra violazione dei dati.<br>
In __[scikit](https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html#sklearn.svm.SVC)__ il parametro $C$ controlla effettivamente se vogliamo pesare molto le misclassification oppure no, in genere se imponente **un $C$ non nullo e non troppo grande dite all'algoritmo che permettete la possibilità di misclassification e state definendo un "soft margin"**, mentre se imponete **un $C$ tendente ad infinite state dicendo di non fare misclassification e quindi non accettate violazioni del margine detto "hard margin"**, a qui un __[esempio di scikit](https://scikit-learn.org/stable/auto_examples/svm/plot_svm_margin.html#sphx-glr-auto-examples-svm-plot-svm-margin-py)__.<br>

## Dati non lineari e il Kernel

Ora il problema è che non sempre i dati sono classificabili in maniera lineare, in tal caso è necessario effettuare una trasformazione non lineare che possiamo definire come $z = \Phi(x)$, ora se noi applicassimo la formula di minimizzazione precedente avremmo:

\begin{equation}
\Large Maximize \; \mathcal{L}(\alpha) = \sum_{n=1}^{N} \alpha_n -\frac{1}{2} \sum_{n=1}^{N} \sum_{m=1}^{N} y_n y_m \alpha_n \alpha_m z^{T}_{n} z_{m}\\
\Large subject\, to \ , 0 \geqslant \alpha_n \geqslant C \,  for \, n = 1,..N \, and \,  \sum_{n=1}^{N} \alpha_n y_n = 0 \\
\end{equation}

Ora abbiamo che il kernel è definito come(ho usato z vettorizzato):

\begin{equation}
\Large Kernel \quad K(x,x') = z^{T}z'
\end{equation}

Ora se volessimo ad esempio una trasformazione polinomiale di grado 2 ad uno spazio 2D avremmo:

\begin{equation}
\Large x = (x_1, x_2) \quad \rightarrow \quad z = \Phi(x) = (1, x_1, x_2, x_{1}^{2}, x_{2}^{2}, x_1 x_2)\\
\Large K(x,x') = z^{T}z' = 1 + x_1 x'_{1} + x_2 x'_{2} + x^{2}_{1} x'^{2}_{1} + x^{2}_{2} x'^{2}_{2} + x_1 x'_{1} x_2 x'_{2}
\end{equation}

Ora se potete notare calcolare in questa maniera è molto dispendioso visto che devo trasformare e poi applicare un prodotto scalare che porta numerosi termini, un trucco per ridurre il calcolo computazionale è usare il __[kernel trick](https://towardsdatascience.com/the-kernel-trick-c98cdbcaeb3f)__, per vederlo potete notare che:

\begin{equation}
\Large K(x,x') = (1 + x^{T}x')^2 = 1 + 2x_1 x'_{1} + 2x_2 x'_{2} + x^{2}_{1} x'^{2}_{1} + x^{2}_{2} x'^{2}_{2} + 2x_1 x'_{1} x_2 x'_{2}\\
\end{equation}

Questa formula aparte dei coefficienti che non ci interessano poichè non influiscono sulla definizione del nuovo spazio, il prodotto scalare precedente è esattamente uguale al prodotto scalare delle trasformazioni dello spazio lineare come definito primo, in poche parole il kernel trick ci dice che:

\begin{equation}
    K(x,x') = < \Phi(x), \Phi(x')> = \Phi(<x,x'>)
\end{equation}

**Il simbolo $<,>$ inidica il prodotto scalare, grazie a questo a questo è possibile usare la __[radial basis function](https://scikit-learn.org/stable/modules/generated/sklearn.gaussian_process.kernels.RBF.html?highlight=rbf#sklearn.gaussian_process.kernels.RBF)__ attraverso cui possiamo fare una classificazione lineare in uno spazio infinito dimensionale in tempo finito! Not Bad!**.


## Il Support Vector Regression (SVR)

Il __[Support Vector Regression](https://www.educba.com/support-vector-regression/)__ è la SVM applicata nel contesto di regressione, **la differenza fondamentale con la classificazione è che in questo caso voi cercate di mantenere i punti della regressione all'interno dei margini della nostra SVM**, questo ci dice che l'algoritmo considererà outliers i punti al di fuori del margine, pe averne una visione completa guardate questi __[esempi scikit](https://scikit-learn.org/stable/auto_examples/svm/plot_svm_regression.html#sphx-glr-auto-examples-svm-plot-svm-regression-py)__.

<div class="alert alert-block alert-warning">
    La trattazione che ho cercato di fare è quanto più completa possibile, ma so che potrei non essere stato molto chiaro, pertanto vi rimando a questo <a href="https://www.lorenzogovoni.com/support-vector-machine/">link in italiano</a> che lo spiega in maniera più semplice e meno matematica.
</div>

Qui sotto metto invece un link youtube video in cui potete visualzzare i concetti appena visti, sono 3 video, ma non posso linkare una playlist cercate comunque su youtube.


```python
from IPython.display import YouTubeVideo

#put link yotube video, only final part
YouTubeVideo("efR1C6CvhmE")
```











```python
import pandas as pd
import matplotlib.pyplot as plt
import time
from sklearn.datasets import load_boston
from sklearn.model_selection import train_test_split
from sklearn.metrics import plot_confusion_matrix, classification_report
from sklearn.svm import SVC, SVR



#regression data
boston = load_boston()
X_boston, y_boston = boston.data, boston.target

#classification data
diabetes = pd.read_csv('../data/diabetes2.csv')
X_diabetes, y_diabetes = diabetes.drop('Outcome', axis = 1).values, diabetes.Outcome.values
feature_diabetes = diabetes.columns.values[:-1]
target_names = ["Not Diabetes", "Diabetes"]

#divide the data in training and testing
X_boston_train, X_boston_test, y_boston_train, y_boston_test = train_test_split(
    X_boston, y_boston, random_state=0, test_size = 0.2)

X_diabetes_train, X_diabetes_test, y_diabetes_train, y_diabetes_test = train_test_split(
    X_diabetes, y_diabetes, random_state=0, test_size = 0.2)

print("SVM FOR REGRESSION TESTED ON BOSTON DATASET")

print('R^2 score training and testing using SVR with C = 1 kernel:')
svr = SVR(kernel = "poly", degree=3) 
start = time.time()
svr.fit(X_boston_train, y_boston_train)
end = time.time()
print(f"- polynomial of degree 3, training score:{svr.score(X_boston_train, y_boston_train)},"
      f" testing score :  {svr.score(X_boston_test, y_boston_test)}, time taken :{end-start}s")
svr = SVR(kernel = "linear") 
start = time.time()
svr.fit(X_boston_train, y_boston_train)
end = time.time()
print(f"- linear, training score:{svr.score(X_boston_train, y_boston_train)},"
      f" testing score :  {svr.score(X_boston_test, y_boston_test)}, time taken :{end-start}s")
svr = SVR(kernel = "rbf") 
start = time.time()
svr.fit(X_boston_train, y_boston_train)
end = time.time()
print(f"- Radial basis function, training score:{svr.score(X_boston_train, y_boston_train)},"
      f" testing score :  {svr.score(X_boston_test, y_boston_test)}, time taken :{end-start}s")
svr = SVR(kernel = "sigmoid") 
start = time.time()
svr.fit(X_boston_train, y_boston_train)
end = time.time()
print(f"- Sigmoid, training score:{svr.score(X_boston_train, y_boston_train)},"
      f" testing score :  {svr.score(X_boston_test, y_boston_test)}, time taken :{end-start}s")

print('-'*80)

print('R^2 score training and testing using SVR with C = 1000 kernel:')
svr = SVR(C = 1e3, kernel = "poly", degree=3) 
start = time.time()
svr.fit(X_boston_train, y_boston_train)
end = time.time()
print(f"- polynomial of degree 3, training score:{svr.score(X_boston_train, y_boston_train)},"
      f" testing score :  {svr.score(X_boston_test, y_boston_test)}, time taken :{end-start}s")
svr = SVR(C = 1e3, kernel = "linear") 
start = time.time()
svr.fit(X_boston_train, y_boston_train)
end = time.time()
print(f"- linear, training score:{svr.score(X_boston_train, y_boston_train)},"
      f" testing score :  {svr.score(X_boston_test, y_boston_test)}, time taken :{end-start}s")
svr = SVR(C = 1e3,kernel = "rbf") 
start = time.time()
svr.fit(X_boston_train, y_boston_train)
end = time.time()
print(f"- Radial basis function, training score:{svr.score(X_boston_train, y_boston_train)},"
      f" testing score :  {svr.score(X_boston_test, y_boston_test)}, time taken :{end-start}s")
svr = SVR(C = 1e3, kernel = "sigmoid") 
start = time.time()
svr.fit(X_boston_train, y_boston_train)
end = time.time()
print(f"- Sigmoid, training score:{svr.score(X_boston_train, y_boston_train)},"
      f" testing score :  {svr.score(X_boston_test, y_boston_test)}, time taken :{end-start}s")

```

    SVM FOR REGRESSION TESTED ON BOSTON DATASET
    R^2 score training and testing using SVR with C = 1 kernel:
    - polynomial of degree 3, training score:0.24644868913152274, testing score :  0.053244563027002534, time taken :0.01099848747253418s
    - linear, training score:0.7484998446645601, testing score :  0.5159537820682599, time taken :1.0620331764221191s
    - Radial basis function, training score:0.24935461402924874, testing score :  0.03623285217626426, time taken :0.009000062942504883s
    - Sigmoid, training score:0.06599931272060566, testing score :  -0.0072226293343120584, time taken :0.011972188949584961s
    --------------------------------------------------------------------------------
    R^2 score training and testing using SVR with C = 1000 kernel:
    - polynomial of degree 3, training score:0.6972777900096314, testing score :  0.4208946625258052, time taken :0.0780022144317627s
    - linear, training score:-20.15355480442324, testing score :  -18.408675490837567, time taken :33.40475797653198s
    - Radial basis function, training score:0.72281432475884, testing score :  0.43222121960176785, time taken :0.018999814987182617s
    - Sigmoid, training score:-135246.221578731, testing score :  -157703.380591555, time taken :0.010997772216796875s



```python
#let's use now svm for classification
svcs = [SVC(C = 1, kernel = 'poly', degree = 3), SVC(C = 1, kernel = 'rbf'), 
        SVC(C = 1, kernel = 'linear'), SVC(C = 1, kernel = 'sigmoid')]
        
#lets train the models
for svc in svcs:
        start = time.time()
        svc.fit(X_diabetes_train, y_diabetes_train)
        print(f"Time taken to train {str(svc)}: {time.time() - start}s \t")

#lets make a confusion matrix for every single one
#confusion matrixes plots
fig, axes = plt.subplots(nrows=2, ncols=2, figsize=(16,10))

for svc, ax in zip(svcs, axes.flatten()):
    plot_confusion_matrix(svc, 
                          X_diabetes_test, 
                          y_diabetes_test, 
                          ax=ax,
                          display_labels=target_names,
                          colorbar= False)
    ax.title.set_text(str(svc))
    
plt.tight_layout()  
plt.show()

#lets use a classification report
for svc in svcs:
    print(f"Classification report of {str(svc)}\n")
    print(classification_report(y_diabetes_test, svc.predict(X_diabetes_test), 
                                  target_names=target_names))

#let's use now svm for classification
svcs = [SVC(C = 1e3, kernel = 'poly', degree = 3), SVC(C = 1e3, kernel = 'rbf'), 
        SVC(C = 1e3, kernel = 'linear'), SVC(C = 1e3, kernel = 'sigmoid')]
        
#lets train the models
for svc in svcs:
        start = time.time()
        svc.fit(X_diabetes_train, y_diabetes_train)
        print(f"Time taken to train {str(svc)}: {time.time() - start}s \t")

#lets make a confusion matrix for every single one
#confusion matrixes plots
fig, axes = plt.subplots(nrows=2, ncols=2, figsize=(16,10))

for svc, ax in zip(svcs, axes.flatten()):
    plot_confusion_matrix(svc, 
                          X_diabetes_test, 
                          y_diabetes_test, 
                          ax=ax,
                          display_labels=target_names,
                          colorbar= False)
    ax.title.set_text(str(svc))
    
plt.tight_layout()  
plt.show()

#lets use a classification report
for svc in svcs:
    print(f"Classification report of {str(svc)}\n")
    print(classification_report(y_diabetes_test, svc.predict(X_diabetes_test), 
                                  target_names=target_names))
```

Qualora voleste provare altri algoritmi andate alla __[guida scikit](https://scikit-learn.org/stable/modules/svm.html)__ che offre un enorme varietà e esempi a tal proposito.

***

COMPLIMENTI AVETE FINITO LA LEZIONE DI SVM!

f9996e31cd3bfaac62403533f3fbe36a78542609
ipynb
Jupyter Notebook
3.machine learning/6-SVM_SVR.ipynb
matinator/Starting-Finance-Club-Torino
8abda7caa769f2dc237c4ff520ef1b40038a5f65
Apache-2.0
2021-03-18T15:45:39.000Z
2021-03-18T15:45:39.000Z
3.machine learning/6-SVM_SVR.ipynb
matinator/Starting-Finance-Club-Torino
8abda7caa769f2dc237c4ff520ef1b40038a5f65
Apache-2.0
3.machine learning/6-SVM_SVR.ipynb
matinator/Starting-Finance-Club-Torino
8abda7caa769f2dc237c4ff520ef1b40038a5f65
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES