<jupyter_start><jupyter_text>SVM  Introduction - SVM classifiers are used for **prediction with confidence**. (Why I say so will be explained further)- Also called as **Large Margin Classifier**.- Primarily designed for **binary classification**, meaning it distinguishes between two classes; think (+) or (-). More advanced SVMs can discriminate between many classes.- SVM can be used for learning complex **non-linear boundary functions**.- Linear SVM uses **Hinge loss**, whereas Non-linear SVM uses **dual form with QP**.  Defining  the hyperplane for SVM  Introduction **In SVM, given two classes, we seek to produce a hyperplane that maximizes the distance between the two training classes.**The margin is up to the nearest point of each class.The general equation of a (hyper)plane in the n-dimensional feature space (in two dimensions a plane is a line):$$ f_\theta (x) = \theta_0 + \theta_1x_1 + \theta_2x_2 + \cdots + \theta_nx_p $$$$  f_\theta (x) = \theta_0 + \textbf{$\theta^{T}$}\textbf{x} $$Our plane is going to divide the two classes in hyperspace. There are an infinite number of ways of choosing the different coefficients to represent the plane, but in this case we are just going to make it as simple as possible by setting $f_\theta (x)$ to 1:$$ |\theta_0 + \textbf{$\theta^{T}$}\textbf{x}| = 1 $$In this case $\textbf{x}$ represents those training examples closest to the hyperplane. This is an important element of what we are doing, because ideally we want to find the plane that maximizes distance between the positive and negative training examples.   Principal equation of the hyperplane Recall that we were discussing classifying the data into the (+) and (-) group. Thus we consider these classification states as output variables $\textbf{y}$ to our method. Going back to our equation, we can write:**For the positive class:**$$\theta_0 + \textbf{$\theta^{T}$}\textbf{x} = 1$$**For the negative class:**$$\theta_0 + \textbf{$\theta^{T}$}\textbf{x} = -1$$Again recalling that the $y$ are either $+1$ or $-1$. Also recall that the plane includes all data point solutions above the plane in the positive class. All solutions below the plane are in the negative class, therefore;$$\theta_0 + \textbf{$\theta^{T}$}\textbf{x} \geq 1$$and also$$\theta_0 + \textbf{$\theta^{T}$}\textbf{x} \leq -1$$Thinking of the $y_i$ as multipliers by $+1$ or $-1$, we can write:$$y_i(\theta_0 + \theta^{T}x_{i}) \geq 1$$for all datapoints $i=1,2, \cdots , m$So, we see that in SVM  instead of one decision boundary $ \theta_T * x=0 $, we have two boundaries, $\theta_T *x=1$ and $\theta_T *x=-1$ Perceptron Vs SVM  Maximise Margin The total **margin** between the support vectors is given by **m**:$$m = \frac{2}{\|\theta\|}$$With an SVM, we seek to **maximize m**. This is why SVMs are called **maximum margin classifiers**.  To summarise: **We can define the hyperplane in terms of the training points closest to the plane. These points are called *support vectors***.The equation of the plane is given as $$|\theta_0 + \textbf{$\theta^{T}$}\textbf{x}|=1$$Where the $\textbf{x}$ are the **support vectors**.It bears mentioning here that the $\theta$ coefficients are often described in other literature as **"weights"**, with the origin $\theta_0$ callsed **"bias"** $b$, such that the equation of the plane is written:$$|\textbf{$\theta^{T}$}\textbf{x}+b|=1$$However, we are going to continue to use the $\theta$ notation in these notes so as to highlight the relationship between the well-known OLS regression and SVMs.  Cost Function Recall that our main cost function seeks to find those minimal weights *as a whole* (remember shrinkage) that fit our criteria. Returning to the concept of a **norm**, we are going to minimize $\|\theta\|_2$ subject to our principle equation, $\sum_{i=0}^{n}y_i(\theta_0 + \theta^{T}x_{i}) \geq 1$ derived above.We use an equation known in the literature as a *Lagrangian* as a way of posing the cost function of our method. A Lagrangian is an equation of the form:$$\Lambda(x,y,\alpha) = f(x,y)+\alpha\ \cdot g(x,y)$$  Primal FormIn this case we do not formulate the cost function in terms of $\|\theta\|_2$ due to the onerous nature of the square root involved. Rather we can **transform** this term to its pseudo-integral, $\frac{1}{2}\|\theta\|_2^{2}$, which has the same properties. $$\Lambda(x,y,\alpha) = \frac{1}{2}\theta^{T}\theta+\sum_{i=0}^{n}\alpha_{i}\ \cdot (1-y_i(\theta_0 + \theta^{T}x_{i}))$$This is called the *primal form* because the **weights and coefficients appear in the same equation.** Now take the grad set to zero,taking the full gradient and setting the hyperplane intercept to zero:$$\nabla_{\theta}\Lambda(x,y,\alpha) = \theta+\sum_{i=0}^{n}\alpha_{i}\ (-y_i(x_{i})) = 0$$That gives us a first solution for the **weights**:$$\theta = \sum_{i=0}^{n}\alpha_{i}y_{i}x_{i}$$We also have a solution for the **bias** that we already set to zero:$$\theta_0 = \sum_{i=0}^{n}\alpha_{i}y_{i} = 0$$  Dual FormThe more common form of the SVM Lagrangian is the *dual form*, which we can get if we substitute our solution for the weights, $\theta = \sum_{i=0}^{n}\alpha_{i}y_{i}x_{i}$, into the primal form. We also remember that $\sum_{i=0}^{n}\alpha_{i}y_{i} = 0$.$$\Lambda(x,y,\alpha) = \frac{1}{2}\sum_{j=0}^{n}\alpha_{j}y_{j}x_{j}^{T}\sum_{i=0}^{n}\alpha_{i}y_{i}x_{i}+\sum_{i=0}^{n}\alpha_{i}\ \cdot (1-y_i(\theta_0 + \sum_{j=0}^{n}\alpha_{j}y_{j}x_{j}^{T}x_{i}))$$This reorganizes (see appendix) to get the following equation:$$\Lambda(x,y,\alpha) = \sum_{i=0}^{n}\alpha_{i}-\frac{1}{2}\sum_{i=0}^{n}\sum_{j=0}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^{T}x_{j}$$This is a *dual form* because we see that we are describing the **weights** in terms of $\alpha$. Weights are not present in this equation. If we know all of the $\alpha$ we know the $\theta$; remember the formula $\theta = \sum_{i=0}^{n}\alpha_{i}y_{i}x_{i}$. hinge loss function------  Soft Margin SVMs For reasons discussed in more detail below, most real-world cases will require the ability to tolerate some misclassification, where there are datapoints labeled as one class that should be in the other, or where noise or hidden variables lead to unclear relationships amongst the classes. In this case, **even the optimal solution** will have some training datapoints that land on the wrong side of the plane. We deal with this using **Soft Margins**. All standard SVM applications use soft margins. For each point $i$, if the point falls on the wrong side of the hyperplane during training, we assign it a *penalty* $\xi_i$, based on its distance from the plane. We minimize $\sum_{i=0}^{n}\xi_i$ along with the hyperplane during optimization. In this case, the principal equations become:$$y_{i}(\theta_0 + \textbf{$\theta^{T}$}x_{i}) \geq m(1 - \xi_{i})$$For the positive class, and$$y_{i}(\theta_0 + \textbf{$\theta^{T}$}x_{i}) \leq m(\xi_{i} - 1)$$For the negative class. We also are assured that$$\xi_{i} \geq 0$$Because we don't penalize points that are not on the wrong side of the plane. ***notice that the margin figures importantly into the principal equations here. what does it mean to have a nonzero $\xi_{i}$ value?**So we want to minimize $\frac{1}{2}\|\theta\|_2^{2}+C\sum_{i=0}^{n}\xi_i$, subject to the above prinicpal equations. It turns out that this is not too much of a change to the dual form of the Lagrangian (Hastie has the derivation for the primal form on pp. 420):$$\Lambda(x,y,\alpha) = \sum_{i=0}^{n}\alpha_{i}-\frac{1}{2}\sum_{i=0}^{n}\sum_{j=0}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^{T}x_{j}$$Where $\sum_{i=0}^{n}\alpha_{i}y_{i}x_{i}=0$ and we also follow the constraint $C\geq\alpha_i\geq 0$; this is all dealt with simultaneously during optimization.The question arises: Now that we've included this new constant $C$ in the equations, what is its effect on the location of the decision boundary? We find that the fixed scale 1 is arbitrary because the $M$ term can be brought into the $\theta$.What is important is that you understand that the **margin** $M$ changes with respect to $C$. Changes in $C$ result in changes in the $\theta$. This in turn results in changes in the direction of the plane and width of the margin simultaneously. More on this is discussed below. OptimizationWe seek to maximize the (dual) Lagrangian as if it were an expectation function:$$\Lambda(x,y,\alpha) = \sum_{i=0}^{n}\alpha_{i}-\frac{1}{2}\sum_{i=0}^{n}\sum_{j=0}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^{T}x_{j}$$subject to some $\alpha_{i} \geq 0$ and $\sum_{i=0}^{n}\alpha_{i}y_{i} = 0$Problems of this type are called Quadratic Programming Problems (because a squared term exists in one variable) and require relatively heavy-duty methods to reliably achieve the solution. However, because they are QP, we are assured that a **global** not approximate(!) maximum of $\alpha_i$ can be found if optimized correctly! We will not cover QP solvers in this unit.Directly computing weights is comparatively rare in most SVM implementations. It is more common to simply calculate the $\alpha_{i}$ and just report the model as such. This produces the **model** $G$ for input data $\textbf{z}$:$$G(\textbf{z}) = \sum_{j=0}^{s}\alpha_{j}y_{j} \textbf{$x_{j}$}^{T}\textbf{z}$$Where the $j$ are the indices of the $s$ support vectors.The model classifies $\textbf{z}$ as class 1 (+) if positive and class 0 (-) otherwise.(Note that the weights do not appear) ReasoningChoosing a bisecting plane to divide two classes enables us to predict a classification using a training set without assuming linearity in the data or fitting to an explicit function.SVM provides several advantages. In simple cases, SVM outperforms logistic regression. SVMs perform feature selection automatically by allowing $\alpha$ coefficients that are unimportant to the classification to go to 0; SVMs also perform shrinkage on the $\theta$ coefficients. We are assured of an optimal solution due to the formulation of the method.   Kernels: Linear vs. Nonlinear SVMs "Kernel" means "heart" or "essence" of something.In math, which is the origin of the word in this case, a kernel is a member of a set of functions:$$K: \mathbb{R}^{N} \times \mathbb{R}^{N} \rightarrow \mathbb{R}$$In the case of the SVM, a kernel maps lower dimensional data into higher dimension and refers to a very particular term in the cost function:$$\Lambda(x,y,\alpha) = \sum_{i=0}^{n}\alpha_{i}-\frac{1}{2}\sum_{i=0}^{n}\sum_{j=0}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}\underline{x_{i}^{T}x_{j}}$$This is a dot or inner product, meaning that it produces a single number for each pair of points (vectors) $x_i, x_j$. You will often see it written this way (inner product vector notation):$$x_{i}^{T}x_{j} = $$This regular, standard kernel is called a **linear** kernel.The idea behind using kernels is that hopefully, then the *transformed* data is __linearly separable__ in higher dimensions. From 2 to 3 dimensions-----φ is the Greek letter "Phi"  φ is the mapping from one dimension to another From 2 to 3 dimensions-----<jupyter_code>#RBF Kernel
from IPython.display import YouTubeVideo

YouTubeVideo("9NrALgHFwTo")
from IPython.display import YouTubeVideo

YouTubeVideo("3liCbRZPrZA")<jupyter_output><empty_output><jupyter_text>The Kernel TrickTHIS IS A STANDARD INTERVIEW QUESTION Transforming the entire Lagrangian from linear into polynomial space is extremely costly in terms of resources. Normally this would imply that we would need to actually increase the number of $\alpha$ coefficients and transform the response variables too.If we were to actually do this, the computation would become prohibitively expensive rapidly with respect to the number of features. However, because we simply compute a **dot product** for every pair of data points $i,j$ in the original feature space $N$ after we transform the data, *this doesn't happen*. We call this **"the kernel trick"**. It's a trick because transformation to a nonlinear space doesn't seem to cost us much; we don't need to calculate the transformation explicitly. We can simply calculate the kernel product once, using the additional functions as necessary(a $N \times N$ matrix). This only leads to a linear increase in calculation time - the time it costs to calculate the transformation from one basis to another. We do not increase the dimensionality of the Lagrangian at all. Since this is the most expensive function in terms of computation and storage, it amounts to immense computational leverage. Types of KernelsIt bears mentioning that there are a few different types of kernels commonly in use; we will mention them here. Linear Kernel:This is simply the standard dot product $$. Sometimes a scalar coefficient $c$ is added.$$K(x_j,x_i) = +c$$ Polynomial KernelsSome combination of transformations and exponents of the orignal linear kernel. Transformation by the function:$$f(x, b, c, d) = (bx+c)^{d}$$Leads to the following expression:$$K(x_j,x_i) = (b+c)^{d}$$ Gaussian and Radial Basis Function KernelsRadial basis functions model the data as if it came from a distribution, this is done in order to "soften" the locations of the training data. The Gaussian radial kernel is the most common of these:$$K(x_j,x_i) = e^{-\frac{\|x_j-x_i\|^{2}}{2\sigma^{2}}}$$There are other variants of the Gaussian, such as the Exponential and Laplace kernels, that leave out the square of the norm. The quality of the outcome is rather dependent on the scaling factor $\sigma$ (the broadness of the Gaussian function).  Kernels & SVMS: Make the data more complex, and keep the model simple.-------<jupyter_code>import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns
import sklearn

import warnings
warnings.filterwarnings('ignore')

palette = "Dark2"
%matplotlib inline

from sklearn.datasets.samples_generator import make_blobs
from sklearn import datasets
from sklearn.svm import SVC

iris = datasets.load_iris()

X = iris.data[:, :2] # Use only the first two features for easier plotting
y = iris.target
# Define & fit model
#kernel = 'linear'
#kernel = 'rbf'
kernel = 'poly'
clf = SVC(kernel=kernel).fit(X, y)
predicted = clf.predict(iris.data[:, :2])
clf.n_support_
# Plot the decision bounds
from mlxtend.plotting import plot_decision_regions

y_labels = y # actual
# y_labels = predicted
plot_decision_regions(X=X, 
                      y=y_labels, 
                      clf=clf,
                      legend=False);
# NOTE: Linear kernel includes piecewise linear, hence the discontinuity
# Plot the decision bounds
from mlxtend.plotting import plot_decision_regions

y_labels = y # actual
# y_labels = predicted
plot_decision_regions(X=X, 
                      y=y_labels, 
                      clf=clf,
                      legend=False);
# NOTE: Linear kernel includes piecewise linear, hence the discontinuity
# Plot the decision bounds
from mlxtend.plotting import plot_decision_regions

y_labels = y # actual
# y_labels = predicted
plot_decision_regions(X=X, 
                      y=y_labels, 
                      clf=clf,
                      legend=False);
# NOTE: Linear kernel includes piecewise linear, hence the discontinuity
# From blobs to circles
from sklearn.datasets import make_circles

X, y = make_circles(noise=0.1, factor=.01, random_state=42)
ax = sns.scatterplot(x=X[:,0], y=X[:,1], hue=y, palette=palette,  legend=False);
ax.set_yticklabels(''); ax.set_xticklabels('');
# Define & fit model
# kernel = 'linear'
kernel = 'rbf'
# kernel = 'poly'
clf = SVC(kernel=kernel).fit(X, y)
predicted = clf.predict(iris.data[:, :2])
# Plot the decision bounds
from mlxtend.plotting import plot_decision_regions

y_labels = y # actual
# y_labels = predicted
plot_decision_regions(X=X, 
                      y=y_labels, 
                      clf=clf,
                      legend=False);
# NOTE: Linear kernel includes piecewise linear, hence the discontinuity<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11781699428499655, 'fraction_numerical': 0.008227092884506688, 'mean_word_length': 4.61297144871343, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '150317', 'license': 'MIT', 'n_tokens_mistral': 4702, 'n_tokens_neox': 4453, 'n_words': 2039, 'path': 'src/week6/day2_svm.ipynb', 'repo_name': 'skyimager/intro-to-ml-with-python', 'size': '15923'}