import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report
from matplotlib.colors import ListedColormap2.2. Distance and Margin Models
After Linear Models, another important class of Machine Learning (ML) models is distance and margin algorithms. The distance-based models assume that observations that are close close in feature space are also close on target space. That is, observations that are similar have similar target values. Closely related to these algorithms, margin models are designed to separate observations by finding decision boundaries that maximizes the margins, which are the distances between the boundaries and the closest data points.
\(k\)-Nearest Neighbors (\(k\)-NN)
The \(k\)-Nearest Neighbors (\(k\)-NN) (Cover and Hart 1967) algorithm is a distance-based algorithm. This models is a lazy learner, meaning it does not require training. \(k\)-NN stores tha training data, and at inference time, uses the closest \(k\) observations to predict the target of a new data point. The algorithm has three major hyperparameters (HPs): the distance function \(d: \mathbb R^{n\times n} \to \mathbb R_{\geq 0}\), the number of neighbors \(k\) and the aggregation function \(g: \mathbb R^{k\times n} \to \mathbb R_{\geq 0}\). The distance function determines how to calculate distance in feature space, while \(k\) is the number of neighbors used to calculate the targets during inference. Lastly, the aggregation function combines the \(k\) closest neighbors to generate the prediction. That is, for a test data \(\boldsymbol x^{(\text{Test})} \in \mathcal D_{\text{Test}}\) its prediction \(\hat y^{(\text{Test})}\) is given by: \[ \hat{y}^{(\text{Test})} = g\left(\boldsymbol{x}^{(\text{Train})}_{d_1}, \boldsymbol{x}^{(\text{Train})}_{d_2}, \dots, \boldsymbol{x}^{(\text{Train})}_{d_k}\right), \tag{1}\] where \(\boldsymbol{x}^{(\text{Train})}_{d_i}\) is the \(i\)-th closest observation to \(\boldsymbol{x}^{(\text{Test})}\) in the training data. according to the distance function \(d\). Figure 1 depicts a scheme of \(k\)-NN during inference.
The HPs need to be carefully chosen so that the model does not suffer from the dimensionality curse, and balance its bias and variance tradeoff. It is also important to note that this algorithm relies on the order of magnitude of the input features, so normalization – as explained in Pre-Processing – is important to prevent undesired behavior.
Code: \(k\)-Nearest Neighbors
Importing the libraries for a \(k\)-NN.
Creating a synthetic classification dataset and normalizing the features.
X, y = make_classification(
n_samples=200,
n_features=2,
n_informative=2,
n_redundant=0,
n_clusters_per_class=1,
random_state=42
)
X[:, 0] = X[:, 0] * 1000
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)Creating and fitting one model with \(k=1\), one with \(k=3\) and one with \(k=15\).
knn_1 = KNeighborsClassifier(n_neighbors=1).fit(X_train_scaled, y_train)
knn_3 = KNeighborsClassifier(n_neighbors=3).fit(X_train_scaled, y_train)
knn_15 = KNeighborsClassifier(n_neighbors=15).fit(X_train_scaled, y_train)Plotting the decision boundaries of each model.
def plot_decision_boundary(model, X, y, ax, title):
cmap_light = ListedColormap(['#FFAAAA', '#AAAAFF'])
cmap_bold = ListedColormap(['#FF0000', '#0000FF'])
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.02),
np.arange(y_min, y_max, 0.02))
Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
ax.contourf(xx, yy, Z, cmap=cmap_light, alpha=0.8)
ax.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold, edgecolor='k', s=20)
ax.set_ylabel(r"$x_2$")
ax.set_xlabel(r"$x_1$")
ax.set_title(title)
fig, axes = plt.subplots(1, 3, figsize=(15, 4))
plot_decision_boundary(knn_1, X_train_scaled, y_train, axes[0], r"$k=1$")
plot_decision_boundary(knn_3, X_train_scaled, y_train, axes[1], r"$k=3$")
plot_decision_boundary(knn_15, X_train_scaled, y_train, axes[2], r"$k=15$")
plt.show()
Printing the classifications reports of each model.
y_pred_1 = knn_1.predict(X_test_scaled)
y_pred_3 = knn_3.predict(X_test_scaled)
y_pred_15 = knn_15.predict(X_test_scaled)
rep_1 = classification_report(y_test, y_pred_1)
rep_3 = classification_report(y_test, y_pred_3)
rep_15 = classification_report(y_test, y_pred_15)
print("k=1")
print(rep_1)
print(60*"=")
print("k=3")
print(rep_3)
print(60*"=")
print("k=15")
print(rep_15)
print(60*"=")k=1
precision recall f1-score support
0 0.79 0.79 0.79 34
1 0.73 0.73 0.73 26
accuracy 0.77 60
macro avg 0.76 0.76 0.76 60
weighted avg 0.77 0.77 0.77 60
============================================================
k=3
precision recall f1-score support
0 0.86 0.91 0.89 34
1 0.88 0.81 0.84 26
accuracy 0.87 60
macro avg 0.87 0.86 0.86 60
weighted avg 0.87 0.87 0.87 60
============================================================
k=15
precision recall f1-score support
0 0.93 0.79 0.86 34
1 0.77 0.92 0.84 26
accuracy 0.85 60
macro avg 0.85 0.86 0.85 60
weighted avg 0.86 0.85 0.85 60
============================================================As it was shown in the decision boundaries and performance reports, small values of \(k\) lead to overfitting, while larger ones might not be a good represention of the neighborhood of the observations – showing the importance of adjusting this HP.
Source: knn.ipynbSupport Vector Machines (SVM)
Support Vector Machines (SVMs) (Vapnik, Golowich, and Smola 1996) are margin-based classifiers. In a binary classification setting, an SVM seeks a linear decision boundary that separates the classes while maximizing the margin. The margin is defined as the perpendicular distance from the decision boundary to the closest training observations, which are known as the support vectors.
Let the separating hyperplane be defined by \(\boldsymbol{w}^T\boldsymbol{x} + b = 0\), where \(\boldsymbol{w} \in \mathbb R^n\) is the normal weight vector and \(b \in \mathbb R\) is the bias. The margin distance is given by \(\frac{1}{\|\boldsymbol{w}\|}\), and the greater this value is, the more separated are the two classes. To maximize this margin, the algorithm minimizes the squared norm of the weights: \[ \min_{\boldsymbol{w}, b} \frac{1}{2} ||\boldsymbol{w}||^2_2 \tag{2}\] subject to the strict classification constraints: \[ y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b) \geq 1, \quad \forall i = 1, \dots, N, \tag{3}\] where \(y_i\in\{-1, 1\}\).
In most scenarios, the dataset \(\mathcal{D}\) is not perfectly linearly separable – making the previous problem mathematically infeasible. To address overlapping classes, the optimization problem is relaxed through the introduction of slack variables \(\xi_i \geq 0\), which allow for margin violations and misclassifications. The objective function becomes: \[ \min_{\boldsymbol{w}, b, \boldsymbol{\xi}} \frac{1}{2} ||\boldsymbol{w}||^2 + C \sum_{i=1}^N \xi_i, \tag{4}\] subject to \(y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b) \geq 1 - \xi_i\). The hyperparameter \(C > 0\) controls the tradeoff between maximizing the margin and minimizing the classification errors. A smaller \(C\) encourages a wider margin with more violations, while a larger \(C\) heavily penalizes misclassifications, leading to a narrower margin. Figure 2 depicts an example of the SVM decision boundaries.
SVMs can be extended to model non-linear relationships. To do that, the idea is to transform the data into a higher-dimensional space in which the classes can be linearly separated. Instead of directly applying this transformation – which would cause a massive computational cost – SVMs utilize the kernel trick. This allows the SVM to implicitly calculate the dot product in the high-dimensional space using only the original, low-dimensional coordinates. A widely used choice is the Radial Basis Function (RBF) kernel: \[ K(\boldsymbol{x}_i, \boldsymbol{x}_j) = \exp\left(-\gamma ||\boldsymbol{x}_i - \boldsymbol{x}_j||^2\right), \tag{5}\] where \(\gamma > 0\) regulates the influence of a single training example.
Code: Support Vector Machine
Importing packages for the SVM.
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_circles
from sklearn.svm import SVC
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import classification_reportCreating a synthetic classification dataset which is not linearly separable and normalizing the features.
X, y = make_circles(n_samples=150, factor=0.5, noise=0.1, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)Creating one linear model and one model with RBF.
svm_linear = SVC(kernel='linear', C=1.0).fit(X_train_scaled, y_train)
svm_rbf = SVC(kernel='rbf', C=1.0, gamma='auto').fit(X_train_scaled, y_train)Plotting the decision boundaries of each model.
def plot_svm_boundary(model, X, y, ax, title):
ax.scatter(X[:, 0], X[:, 1], c=y, cmap='bwr', s=30, zorder=3)
xlim = ax.get_xlim()
ylim = ax.get_ylim()
xx = np.linspace(xlim[0], xlim[1], 100)
yy = np.linspace(ylim[0], ylim[1], 100)
YY, XX = np.meshgrid(yy, xx)
xy = np.vstack([XX.ravel(), YY.ravel()]).T
Z = model.decision_function(xy).reshape(XX.shape)
ax.contour(XX, YY, Z, colors='k', levels=[-1, 0, 1], alpha=0.5,
linestyles=['--', '-', '--'])
ax.scatter(model.support_vectors_[:, 0], model.support_vectors_[:, 1], s=100,
linewidth=1, facecolors='none', edgecolors='k', label='Support Vectors')
ax.set_title(title)
ax.legend(loc='upper right')
ax.set_xlabel(r"$x_1$")
ax.set_ylabel(r"$x_2$")
fig, axes = plt.subplots(1, 2, figsize=(14, 6))
plot_svm_boundary(svm_linear, X_train_scaled, y_train, axes[0], "Linear SVM")
plot_svm_boundary(svm_rbf, X_train_scaled, y_train, axes[1], "RBF SVM")
plt.tight_layout()
plt.show()
Printing the classifications reports of each model.
y_pred_linear = svm_linear.predict(X_test_scaled)
y_pred_rbf = svm_rbf.predict(X_test_scaled)
rep_linear = classification_report(y_test, y_pred_linear)
rep_rbf = classification_report(y_test, y_pred_rbf)
print("Linear")
print(rep_linear)
print(60*"=")
print("RBF")
print(rep_rbf)
print(60*"=")Linear
precision recall f1-score support
0 0.50 0.35 0.41 23
1 0.48 0.64 0.55 22
accuracy 0.49 45
macro avg 0.49 0.49 0.48 45
weighted avg 0.49 0.49 0.48 45
============================================================
RBF
precision recall f1-score support
0 1.00 1.00 1.00 23
1 1.00 1.00 1.00 22
accuracy 1.00 45
macro avg 1.00 1.00 1.00 45
weighted avg 1.00 1.00 1.00 45
============================================================As it was shown in the plot, the linear SVM was not able to separate the classes, while the RBF SVM was able to separate the observations.
Source: svm.ipynbReferences
Cover, Thomas, and Peter Hart. 1967. “Nearest Neighbor Pattern Classification.” IEEE Transactions on Information Theory 13 (1): 21–27.
Vapnik, Vladimir, Steven Golowich, and Alex Smola. 1996. “Support Vector Method for Function Approximation, Regression Estimation and Signal Processing.” Advances in Neural Information Processing Systems 9.