Objective: Find the best \(\color{blue}{\vec{w}}\).
Model Setting
Hard Margin Linear SVM
Assumption 2: The classes are linearly separable.
Objective: Find the best \(\color{blue}{\vec{w}}\).
Model Setting
Hard Margin Linear SVM
Assumption 2: The classes are linearly separable (LS).
Objective: Find the best \(\color{blue}{\vec{w}}\).
Simple maths implies that \(\text{Margin}\propto 1/\|\color{blue}{\vec{w}}\|,\) with
\(\|\color{blue}{\vec{w}}\|:\) norm of \(\color{blue}{\vec{w}}\) (size/length of \(\color{blue}{\vec{w}}\)).
Goal: Now, reduced to finding \(\color{blue}{\vec{w}}\)minimizing\(\|\color{blue}{\vec{w}}\|\) and separates classes well!
Final problem:\[\begin{align*}&\min_{\color{blue}{\vec{w}}\in\mathbb{R}^d, \color{blue}{b}\in\mathbb{R}}\frac{1}{2}\|\color{blue}{\vec{w}}\|^2\qquad (\text{maximizing the margin})\\ &\text{subject to: }y_i(\color{blue}{\vec{w}^T}\text{x}_i+\color{blue}{b})\geq 1,\text{ for all }i=1,2,... (\text{separate class well!})\end{align*}\]
Model Setting
Solution of Hard Margin Linear SVM
Final problem:\[\begin{align*}&\min_{\color{blue}{\vec{w}}\in\mathbb{R}^d, \color{blue}{b}\in\mathbb{R}}\frac{1}{2}\|\color{blue}{\vec{w}}\|^2\qquad (\text{maximizing the margin})\\ &\text{subject to: }y_i(\color{blue}{\vec{w}^T}\text{x}_i+\color{blue}{b})\geq 1,\text{ for all }i=1,2,... (\text{separate class well!})\end{align*}\]
Solution:\[\color{blue}{\vec{w}^*}=\color{blue}{\sum_{i=1}^n\alpha_iy_i\text{x}_i}\] such that
\(\alpha_i=0\) for \(\text{x}_i\)NOT ON the margin.
\(\color{green}{\alpha_{i_0}}\neq 0\) for \(\color{green}{\text{x}_{i_0}}\)ON the margin and therefore, \[\color{blue}{b^*}=\color{green}{y_{i_0}}-\sum_{i=1}^n\alpha_iy_i\color{green}{\text{x}_{i_0}^T}[\text{x}_i].\]
Model Setting
Prediction by Hard Margin Linear SVM
Solution:\[\color{blue}{\vec{w}^*}=\color{blue}{\sum_{i=1}^n\alpha_iy_i\text{x}_i}\] such that
\(\alpha_i=0\) for \(\text{x}_i\)NOT ON the margin.
\(\color{green}{\alpha_{i_0}}\neq 0\) for \(\color{green}{\text{x}_{i_0}}\)ON the margin and therefore, \[\color{blue}{b^*}=\color{green}{y_{i_0}}-\sum_{i=1}^n\alpha_iy_i\color{green}{\text{x}_{i_0}^T}[\text{x}_i].\]
The decision boundary:\(f(\text{x})=\color{blue}{(\vec{w}^*)^T}\text{x}+\color{blue}{b}=\color{blue}{\sum_{i=1}\alpha_iy_i}[\color{blue}{\text{x}_i^T}\text{x}]+\color{blue}{b^*}.\)
Prediction rule: Given a new input \(\color{red}{\text{x}_0}\in\mathbb{R}^d\) we have \[\color{red}{y_0}=\text{sign}(f(\text{x}_0))=\text{sign}\Big(\color{blue}{\sum_{i=1}\alpha_iy_i}[\color{blue}{\text{x}_i^T}\color{red}{\text{x}_0}]+\color{blue}{b^*}\Big).\]
Soft Margin
Model Setting
Soft Margin Linear SVM (slack variables)
The result from Linear SVM is beautiful! BUT…
In practice, data are rarely Linearly Separable!
Soft Margin: Introducing slack variables \(\color{blue}{s_i},i=1,2,...,n\) and \[\begin{align*}&\min_{\color{blue}{\vec{w}}\in\mathbb{R}^d, \color{blue}{b,s_i}\in\mathbb{R}}\frac{1}{2}\|\color{blue}{\vec{w}}\|^2+\color{red}{C}\sum_{i=1}^n\color{blue}{s_i}\\ &\text{subject to: }y_i(\color{blue}{\vec{w}^T}\text{x}_i+\color{blue}{b})\geq 1-\color{blue}{s_i}\quad\text{and }s_i\geq 0,\text{ for all }i=1,2,...\end{align*}\]
Interpretation: Slack variables \(\color{blue}{s_i}\) relax the linearly separable condition by allowing some misclassified points.
The constant \(\color{red}{C}>0\) controls the trade-off between maximizing the margin and minimizing the classification error.
Model Setting
Soft Margin Linear SVM (slack variables)
Soft Margin: Introducing slack variables \(\color{blue}{s_i},i=1,2,...,n\) and \[\begin{align*}&\min_{\color{blue}{\vec{w}}\in\mathbb{R}^d, \color{blue}{b,s_i}\in\mathbb{R}}\frac{1}{2}\|\color{blue}{\vec{w}}\|^2+\color{red}{C}\sum_{i=1}^n\color{blue}{s_i}\\ &\text{subject to: }y_i(\color{blue}{\vec{w}^T}\text{x}_i+\color{blue}{b})\geq 1-\color{blue}{s_i}\quad\text{and }s_i\geq 0,\text{ for all }i=1,2,...\end{align*}\]
Interpretation: Slack variables \(\color{blue}{s_i}\) relax the linearly separable condition by allowing some misclassified points.
The constant \(\color{red}{C}>0\) controls the trade-off between maximizing the margin and minimizing the classification error.
Lower\(\color{red}{C}\Leftrightarrow\) more relaxing, more many points can fall within the margin (large margin).
Model Setting
Soft Margin Linear SVM (slack variables)
Soft Margin: Introducing slack variables \(\color{blue}{s_i},i=1,2,...,n\) and \[\begin{align*}&\min_{\color{blue}{\vec{w}}\in\mathbb{R}^d, \color{blue}{b,s_i}\in\mathbb{R}}\frac{1}{2}\|\color{blue}{\vec{w}}\|^2+\color{red}{C}\sum_{i=1}^n\color{blue}{s_i}\\ &\text{subject to: }y_i(\color{blue}{\vec{w}^T}\text{x}_i+\color{blue}{b})\geq 1-\color{blue}{s_i}\quad\text{and }s_i\geq 0,\text{ for all }i=1,2,...\end{align*}\]
Interpretation: Slack variables \(\color{blue}{s_i}\) relax the linearly separable condition by allowing some misclassified points.
The constant \(\color{red}{C}>0\) controls the trade-off between maximizing the margin and minimizing the classification error.
Lower\(\color{red}{C}\Leftrightarrow\) more relaxing, more many points can fall within the margin (large margin).
Large\(\color{red}{C}\Leftrightarrow\) more strict, less points can fall within the margin (small margin).
Model Setting
Prediction by Soft Margin Linear SVM
Soft Margin Solution:\(\color{blue}{\vec{w}^*}=\color{blue}{\sum_{i=1}^n\alpha_iy_i\text{x}_i}\) such that
If \(\alpha_i=0\) for \(\text{x}_i\)NOT ON the margin.
If \(0<\color{green}{\alpha_{i_0}}\leq \color{red}{C}\) then for \(\color{green}{\text{x}_{i_0}}\):
If \(\color{blue}{s_{i_0}}\in\{0,\color{red}{C}\}\Rightarrow\)ARE EXACTLY ON the margin: \[\color{blue}{b^*}=\color{green}{y_{i_0}}-\sum_{i=1}^n\alpha_iy_i\color{green}{\text{x}_{i_0}^T}[\text{x}_i].\]
Else \(\color{green}{\text{x}_{i_0}}\)FALL WITHIN THE MARGIN.
The decision boundary:\(f(\text{x})=\color{blue}{(\vec{w}^*)^T}\text{x}+\color{blue}{b}=\color{blue}{\sum_{i=1}\alpha_iy_i}[\color{blue}{\text{x}_i^T}\text{x}]+\color{blue}{b^*}.\)
Prediction rule: Given a new input \(\color{red}{\text{x}_0}\in\mathbb{R}^d\) we have \[\color{red}{y_0}=\text{sign}(f(\text{x}_0))=\text{sign}\Big(\color{blue}{\sum_{i=1}\alpha_iy_i}[\color{blue}{\text{x}_i^T}\color{red}{\text{x}_0}]+\color{blue}{b^*}\Big).\]
The key parameter \(C\) is tuned using \(K\)-Fold CV.
Categorical inputs are encoded using OneHotEncoding.
Standardization is also applied.
Code
import numpy as npimport pandas as pdfrom sklearn.model_selection import train_test_split, GridSearchCVfrom sklearn.preprocessing import OneHotEncoderdata = pd.read_csv(path +"/heart.csv")quan_vars = ['age','trestbps','chol','thalach','oldpeak']qual_vars = ['sex','cp','fbs','restecg','exang','slope','ca','thal','target']# Convert to correct typesfor i in quan_vars: data[i] = data[i].astype('float')for i in qual_vars: data[i] = data[i].astype('category')data.drop_duplicates(inplace=True)# Train test splitfrom sklearn.model_selection import train_test_splitX, y = data.iloc[:,:-1], data.iloc[:,-1]X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, stratify=y, random_state=42)from sklearn.preprocessing import StandardScalerscaler = StandardScaler()encoder = OneHotEncoder(drop='first', sparse_output=False)# OnehotEncoding and ScalingX_train_cat = encoder.fit_transform(X_train.select_dtypes(include="category"))X_train_encoded = scaler.fit_transform(np.column_stack([X_train.select_dtypes(include="number").to_numpy(), X_train_cat]))X_test_cat = encoder.transform(X_test.select_dtypes(include="category"))X_test_encoded = scaler.transform(np.column_stack([X_test.select_dtypes(include="number").to_numpy(), X_test_cat]))# KNNfrom sklearn.svm import SVCsvm_model = SVC(kernel='linear', random_state=42)# Define the hyperparameter gridparam_grid = {'C': [0.1, 0.2, 0.25, 0.3, 0.4, 0.5, 0.75, 1]}# Perform GridSearch for optimal Cgrid_search = GridSearchCV(svm_model, param_grid, cv=20, scoring='accuracy')grid_search.fit(X_train_encoded, y_train)# Get the best parameterbest_C = grid_search.best_params_['C']# Train final model using best Cfinal_model = SVC(kernel='rbf', C=best_C, random_state=42)final_model.fit(X_train_encoded, y_train)# Predict on test sety_pred = final_model.predict(X_test_encoded)from sklearn.metrics import roc_auc_score, accuracy_score, precision_score, recall_score, f1_score, confusion_matrix, ConfusionMatrixDisplaytest_perf = pd.DataFrame( data={'Accuracy': accuracy_score(y_test, y_pred),'Precision': precision_score(y_test, y_pred),'Recall': recall_score(y_test, y_pred),'F1-score': f1_score(y_test, y_pred),'AUC': roc_auc_score(y_test, y_pred)}, columns=["Accuracy", "Precision", "Recall", "F1-score", "AUC"], index=["LSVM"])test_perf
Accuracy
Precision
Recall
F1-score
AUC
LSVM
0.852459
0.852941
0.878788
0.865672
0.850108
Best \(C=\) 0.1.
Model Setting
Summary: Hard & Soft Margin Linear SVM
Hard Margin Linear SVM: assumes that the classes are linear separable.
Soft Margin Linear SVM: does not assume linearly separability (used slack variables).
The decision boundary:\(f(\text{x})=\color{blue}{(\vec{w}^*)^T}\text{x}+\color{blue}{b}=\color{blue}{\sum_{i=1}\alpha_iy_i}[\color{blue}{\text{x}_i^T}\text{x}]+\color{blue}{b^*}.\)
Prediction rule: Given a new input \(\color{red}{\text{x}_0}\in\mathbb{R}^d\) we have \[\color{red}{y_0}=\text{sign}(f(\text{x}_0))=\text{sign}\Big(\color{blue}{\sum_{i=1}\alpha_iy_i}[\color{blue}{\text{x}_i^T}\color{red}{\text{x}_0}]+\color{blue}{b^*}\Big).\]
A VERY IMPORTANT REMARK: It does not depend on actual training inputs, just the scalar products: \(\color{blue}{\text{x}_i^T}\color{red}{\text{x}_0}\).
From this we can overcome Linear Boundary by using Kernel Trick.
Nonlinear SVM: Kernel Trick
Nonlinear SVM
Kernel Trick
Prediction rule: Given a new input \(\color{red}{\text{x}_0}\in\mathbb{R}^d\) we have \[\color{red}{y_0}=\text{sign}(f(\text{x}_0))=\text{sign}\Big(\color{blue}{\sum_{i=1}\alpha_iy_i}[\color{blue}{\text{x}_i^T}\color{red}{\text{x}_0}]+\color{blue}{b^*}\Big).\]
Kernel function introduce feature/transformation of original inputs.
Instead of input scalar \(\color{blue}{\text{x}_i^T}\color{red}{\text{x}_j}\), we can use kernel feature \(K(\color{blue}{\text{x}_i},\color{red}{\text{x}_j})\).
It works well in problems with nonlinear boundary decision.
Nonlinear SVM
Kernel Trick
Instead of input scalar \(\color{blue}{\text{x}_i^T}\color{red}{\text{x}_j}\), we can use kernel feature \(K(\color{blue}{\text{x}_i},\color{red}{\text{x}_j})\).
In this case, prediction rule becomes: \(\color{red}{\text{x}_0}\in\mathbb{R}^d\), \[\color{red}{y_0}=\text{sign}(f(\text{x}_0))=\text{sign}\Big(\color{blue}{\sum_{i=1}\alpha_iy_i}K(\color{blue}{\text{x}_i}\color{red}{\text{x}_0})+\color{blue}{b^*}\Big).\]
It works well in problems with nonlinear boundary decision.
Train a base learner on the new data: \(\{(\text{x}_i,y_i),r_{t,i}\}.\)
Solve for \(\color{blue}{f_t}\) and \(\color{blue}{w_t}\) from: \[(\color{blue}{w_t}, \color{blue}{f_t(\text{x})})=\arg\min_{\color{blue}{w,f}}\sum_{i=1}^nL(y_i,F_{t-1}(\text{x}_i)+\color{blue}{wf(\text{x}_i)}).\]
LightGBM: Light Gradient Boosting Machine by researchers at Microsof (2017). It works for regression, classification and ranking problems. Main improvement:
Gradient-based One-Sided Sampling (GOSS)
Exclusive Feature Bundling (EFB),
to ensure the efficiency and accuracy of the method.
CatBoost: Efficient with categorical features (auto transformation) and unbiased estimation of gradient at each iteration (see: Prokhorenkova et al. (2017)).
The Reduction of Impurity Measures when spliting at \(X_j\) is denoted by \[\text{RIM}_t(X_j)=\text{Imp}_{t-1}(X_j)-\text{Imp}_t(X_j).\]
The importance of feature \(X_j\) within a tree: \(\sum_{t\in S_j}\text{RIM}_t(X_j),\) where \(S_j\) is the set of indices \(t\) when a split is performed at \(X_j\).
Unnormaized FI of variable \(X_j\) is the sum of FIs from all the built trees.
⚠️ Might be biased toward high cardinality features and might not be accurate with highly correlated features.
Permutation Feature Importance
Train initial model, then compute the validation error denoted by \(\color{blue}{\text{Er}_0}\)
For each \(X_j\), shuffle its column in the dataset, then train and measure validation error\(\color{red}{\text{Er}_j}\).
The importance score for \(X_j\) is proportional to \(\color{red}{\text{Er}_j}-\color{blue}{\text{Er}_0}\).
It reflexes more direct influence of each feature in the model.
⚠️ Might be sensitive to data splits and a bit computationally expensive.
