KarlHenrik
1867 lines
58 KiB
Plaintext
1867 lines
58 KiB
Plaintext
{
|
||
"cells": [
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Support Vector Machines, overarching aims\n",
|
||
"\n",
|
||
"A Support Vector Machine (SVM) is a very powerful and versatile\n",
|
||
"Machine Learning method, capable of performing linear or nonlinear\n",
|
||
"classification, regression, and even outlier detection. It is one of\n",
|
||
"the most popular models in Machine Learning, and anyone interested in\n",
|
||
"Machine Learning should have it in their toolbox. SVMs are\n",
|
||
"particularly well suited for classification of complex but small-sized or\n",
|
||
"medium-sized datasets. \n",
|
||
"\n",
|
||
"The case with two well-separated classes only can be understood in an\n",
|
||
"intuitive way in terms of lines in a two-dimensional space separating\n",
|
||
"the two classes (see figure below).\n",
|
||
"\n",
|
||
"The basic mathematics behind the SVM is however less familiar to most of us. \n",
|
||
"It relies on the definition of hyperplanes and the\n",
|
||
"definition of a **margin** which separates classes (in case of\n",
|
||
"classification problems) of variables. It is also used for regression\n",
|
||
"problems.\n",
|
||
"\n",
|
||
"With SVMs we distinguish between hard margin and soft margins. The\n",
|
||
"latter introduces a so-called softening parameter to be discussed\n",
|
||
"below. We distinguish also between linear and non-linear\n",
|
||
"approaches. The latter are the most frequent ones since it is rather\n",
|
||
"unlikely that we can separate classes easily by say straight lines.\n",
|
||
"\n",
|
||
"\n",
|
||
"## Hyperplanes and all that\n",
|
||
"\n",
|
||
"The theory behind support vector machines (SVM hereafter) is based on\n",
|
||
"the mathematical description of so-called hyperplanes. Let us start\n",
|
||
"with a two-dimensional case. This will also allow us to introduce our\n",
|
||
"first SVM examples. These will be tailored to the case of two specific\n",
|
||
"classes, as displayed in the figure here based on the usage of the petal data.\n",
|
||
"\n",
|
||
"We assume here that our data set can be well separated into two\n",
|
||
"domains, where a straight line does the job in the separating the two\n",
|
||
"classes. Here the two classes are represented by either squares or\n",
|
||
"circles."
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": null,
|
||
"metadata": {
|
||
"collapsed": false,
|
||
"editable": true
|
||
},
|
||
"outputs": [],
|
||
"source": [
|
||
"%matplotlib inline\n",
|
||
"\n",
|
||
"from sklearn import datasets\n",
|
||
"from sklearn.svm import SVC, LinearSVC\n",
|
||
"from sklearn.linear_model import SGDClassifier\n",
|
||
"from sklearn.preprocessing import StandardScaler\n",
|
||
"import matplotlib\n",
|
||
"import matplotlib.pyplot as plt\n",
|
||
"plt.rcParams['axes.labelsize'] = 14\n",
|
||
"plt.rcParams['xtick.labelsize'] = 12\n",
|
||
"plt.rcParams['ytick.labelsize'] = 12\n",
|
||
"\n",
|
||
"\n",
|
||
"iris = datasets.load_iris()\n",
|
||
"X = iris[\"data\"][:, (2, 3)] # petal length, petal width\n",
|
||
"y = iris[\"target\"]\n",
|
||
"\n",
|
||
"setosa_or_versicolor = (y == 0) | (y == 1)\n",
|
||
"X = X[setosa_or_versicolor]\n",
|
||
"y = y[setosa_or_versicolor]\n",
|
||
"\n",
|
||
"\n",
|
||
"\n",
|
||
"C = 5\n",
|
||
"alpha = 1 / (C * len(X))\n",
|
||
"\n",
|
||
"lin_clf = LinearSVC(loss=\"hinge\", C=C, random_state=42)\n",
|
||
"svm_clf = SVC(kernel=\"linear\", C=C)\n",
|
||
"sgd_clf = SGDClassifier(loss=\"hinge\", learning_rate=\"constant\", eta0=0.001, alpha=alpha,\n",
|
||
" max_iter=100000, random_state=42)\n",
|
||
"\n",
|
||
"scaler = StandardScaler()\n",
|
||
"X_scaled = scaler.fit_transform(X)\n",
|
||
"\n",
|
||
"lin_clf.fit(X_scaled, y)\n",
|
||
"svm_clf.fit(X_scaled, y)\n",
|
||
"sgd_clf.fit(X_scaled, y)\n",
|
||
"\n",
|
||
"print(\"LinearSVC: \", lin_clf.intercept_, lin_clf.coef_)\n",
|
||
"print(\"SVC: \", svm_clf.intercept_, svm_clf.coef_)\n",
|
||
"print(\"SGDClassifier(alpha={:.5f}):\".format(sgd_clf.alpha), sgd_clf.intercept_, sgd_clf.coef_)\n",
|
||
"\n",
|
||
"# Compute the slope and bias of each decision boundary\n",
|
||
"w1 = -lin_clf.coef_[0, 0]/lin_clf.coef_[0, 1]\n",
|
||
"b1 = -lin_clf.intercept_[0]/lin_clf.coef_[0, 1]\n",
|
||
"w2 = -svm_clf.coef_[0, 0]/svm_clf.coef_[0, 1]\n",
|
||
"b2 = -svm_clf.intercept_[0]/svm_clf.coef_[0, 1]\n",
|
||
"w3 = -sgd_clf.coef_[0, 0]/sgd_clf.coef_[0, 1]\n",
|
||
"b3 = -sgd_clf.intercept_[0]/sgd_clf.coef_[0, 1]\n",
|
||
"\n",
|
||
"# Transform the decision boundary lines back to the original scale\n",
|
||
"line1 = scaler.inverse_transform([[-10, -10 * w1 + b1], [10, 10 * w1 + b1]])\n",
|
||
"line2 = scaler.inverse_transform([[-10, -10 * w2 + b2], [10, 10 * w2 + b2]])\n",
|
||
"line3 = scaler.inverse_transform([[-10, -10 * w3 + b3], [10, 10 * w3 + b3]])\n",
|
||
"\n",
|
||
"# Plot all three decision boundaries\n",
|
||
"plt.figure(figsize=(11, 4))\n",
|
||
"plt.plot(line1[:, 0], line1[:, 1], \"k:\", label=\"LinearSVC\")\n",
|
||
"plt.plot(line2[:, 0], line2[:, 1], \"b--\", linewidth=2, label=\"SVC\")\n",
|
||
"plt.plot(line3[:, 0], line3[:, 1], \"r-\", label=\"SGDClassifier\")\n",
|
||
"plt.plot(X[:, 0][y==1], X[:, 1][y==1], \"bs\") # label=\"Iris-Versicolor\"\n",
|
||
"plt.plot(X[:, 0][y==0], X[:, 1][y==0], \"yo\") # label=\"Iris-Setosa\"\n",
|
||
"plt.xlabel(\"Petal length\", fontsize=14)\n",
|
||
"plt.ylabel(\"Petal width\", fontsize=14)\n",
|
||
"plt.legend(loc=\"upper center\", fontsize=14)\n",
|
||
"plt.axis([0, 5.5, 0, 2])\n",
|
||
"\n",
|
||
"plt.show()"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"The aim of the SVM algorithm is to find a hyperplane in a\n",
|
||
"$p$-dimensional space, where $p$ is the number of features that\n",
|
||
"distinctly classifies the data points.\n",
|
||
"\n",
|
||
"In a $p$-dimensional space, a hyperplane is what we call an affine subspace of dimension of $p-1$.\n",
|
||
"As an example, in two dimension, a hyperplane is simply as straight line while in three dimensions it is \n",
|
||
"a two-dimensional subspace, or stated simply, a plane. \n",
|
||
"\n",
|
||
"In two dimensions, with the variables $x_1$ and $x_2$, the hyperplane is defined as"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"b+w_1x_1+w_2x_2=0,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"where $b$ is the intercept and $w_1$ and $w_2$ define the elements of a vector orthogonal to the line \n",
|
||
"$b+w_1x_1+w_2x_2=0$. \n",
|
||
"In two dimensions we define the vectors $\\boldsymbol{x} =[x1,x2]$ and $\\boldsymbol{w}=[w1,w2]$. \n",
|
||
"We can then rewrite the above equation as"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\boldsymbol{x}^T\\boldsymbol{w}+b=0.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"We limit ourselves to two classes of outputs $y_i$ and assign these classes the values $y_i = \\pm 1$. \n",
|
||
"In a $p$-dimensional space of say $p$ features we have a hyperplane defines as"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"b+wx_1+w_2x_2+\\dots +w_px_p=0.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"If we define a \n",
|
||
"matrix $\\boldsymbol{X}=\\left[\\boldsymbol{x}_1,\\boldsymbol{x}_2,\\dots, \\boldsymbol{x}_p\\right]$\n",
|
||
"of dimension $n\\times p$, where $n$ represents the observations for each feature and each vector $x_i$ is a column vector of the matrix $\\boldsymbol{X}$,"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\boldsymbol{x}_i = \\begin{bmatrix} x_{i1} \\\\ x_{i2} \\\\ \\dots \\\\ \\dots \\\\ x_{ip} \\end{bmatrix}.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"If the above condition is not met for a given vector $\\boldsymbol{x}_i$ we have"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"b+w_1x_{i1}+w_2x_{i2}+\\dots +w_px_{ip} >0,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"if our output $y_i=1$.\n",
|
||
"In this case we say that $\\boldsymbol{x}_i$ lies on one of the sides of the hyperplane and if"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"b+w_1x_{i1}+w_2x_{i2}+\\dots +w_px_{ip} < 0,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"for the class of observations $y_i=-1$, \n",
|
||
"then $\\boldsymbol{x}_i$ lies on the other side. \n",
|
||
"\n",
|
||
"Equivalently, for the two classes of observations we have"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"y_i\\left(b+w_1x_{i1}+w_2x_{i2}+\\dots +w_px_{ip}\\right) > 0.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"When we try to separate hyperplanes, if it exists, we can use it to construct a natural classifier: a test observation is assigned a given class depending on which side of the hyperplane it is located.\n",
|
||
"\n",
|
||
"\n",
|
||
"### The two-dimensional case\n",
|
||
"\n",
|
||
"Let us try to develop our intuition about SVMs by limiting ourselves to a two-dimensional\n",
|
||
"plane. To separate the two classes of data points, there are many\n",
|
||
"possible lines (hyperplanes if you prefer a more strict naming) \n",
|
||
"that could be chosen. Our objective is to find a\n",
|
||
"plane that has the maximum margin, i.e the maximum distance between\n",
|
||
"data points of both classes. Maximizing the margin distance provides\n",
|
||
"some reinforcement so that future data points can be classified with\n",
|
||
"more confidence.\n",
|
||
"\n",
|
||
"What a linear classifier attempts to accomplish is to split the\n",
|
||
"feature space into two half spaces by placing a hyperplane between the\n",
|
||
"data points. This hyperplane will be our decision boundary. All\n",
|
||
"points on one side of the plane will belong to class one and all points\n",
|
||
"on the other side of the plane will belong to the second class two.\n",
|
||
"\n",
|
||
"Unfortunately there are many ways in which we can place a hyperplane\n",
|
||
"to divide the data. Below is an example of two candidate hyperplanes\n",
|
||
"for our data sample.\n",
|
||
"\n",
|
||
"\n",
|
||
"Let us define the function"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"f(x) = \\boldsymbol{w}^T\\boldsymbol{x}+b = 0,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"as the function that determines the line $L$ that separates two classes (our two features), see the figure here. \n",
|
||
"\n",
|
||
"\n",
|
||
"Any point defined by $\\boldsymbol{x}_i$ and $\\boldsymbol{x}_2$ on the line $L$ will satisfy $\\boldsymbol{w}^T(\\boldsymbol{x}_1-\\boldsymbol{x}_2)=0$. \n",
|
||
"\n",
|
||
"The signed distance $\\delta$ from any point defined by a vector $\\boldsymbol{x}$ and a point $\\boldsymbol{x}_0$ on the line $L$ is then"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\delta = \\frac{1}{\\vert\\vert \\boldsymbol{w}\\vert\\vert}(\\boldsymbol{w}^T\\boldsymbol{x}+b).\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"How do we find the parameter $b$ and the vector $\\boldsymbol{w}$? What we could\n",
|
||
"do is to define a cost function which now contains the set of all\n",
|
||
"misclassified points $M$ and attempt to minimize this function"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"C(\\boldsymbol{w},b) = -\\sum_{i\\in M} y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b).\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"We could now for example define all values $y_i =1$ as misclassified in case we have $\\boldsymbol{w}^T\\boldsymbol{x}_i+b < 0$ and the opposite if we have $y_i=-1$. Taking the derivatives gives us"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{\\partial C}{\\partial b} = -\\sum_{i\\in M} y_i,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"and"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{\\partial C}{\\partial \\boldsymbol{w}} = -\\sum_{i\\in M} y_ix_i.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"We can now use the Newton-Raphson method or different variants of the gradient descent family (from plain gradient descent to various stochastic gradient descent approaches) to solve the equations"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"b \\leftarrow b +\\eta \\frac{\\partial C}{\\partial b},\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"and"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\boldsymbol{w} \\leftarrow \\boldsymbol{w} +\\eta \\frac{\\partial C}{\\partial \\boldsymbol{w}},\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"where $\\eta$ is our by now well-known learning rate. \n",
|
||
"\n",
|
||
"\n",
|
||
"\n",
|
||
"The equations we discussed above can be coded rather easily (the\n",
|
||
"framework is similar to what we developed for logistic\n",
|
||
"regression). We are going to set up a simple case with two classes only and we want to find a line which separates them the best possible way."
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"There are however problems with this approach, although it looks\n",
|
||
"pretty straightforward to implement. When running the above code, we see that we can easily end up with many diffeent lines which separate the two classes.\n",
|
||
"\n",
|
||
"\n",
|
||
"For small\n",
|
||
"gaps between the entries, we may also end up needing many iterations\n",
|
||
"before the solutions converge and if the data cannot be separated\n",
|
||
"properly into two distinct classes, we may not experience a converge\n",
|
||
"at all.\n",
|
||
"\n",
|
||
"\n",
|
||
"### A better approach\n",
|
||
"\n",
|
||
"A better approach is rather to try to define a large margin between\n",
|
||
"the two classes (if they are well separated from the beginning).\n",
|
||
"\n",
|
||
"Thus, we wish to find a margin $M$ with $\\boldsymbol{w}$ normalized to\n",
|
||
"$\\vert\\vert \\boldsymbol{w}\\vert\\vert =1$ subject to the condition"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b) \\geq M \\hspace{0.1cm}\\forall i=1,2,\\dots, p.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"All points are thus at a signed distance from the decision boundary defined by the line $L$. The parameters $b$ and $w_1$ and $w_2$ define this line. \n",
|
||
"\n",
|
||
"We seek thus the largest value $M$ defined by"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{1}{\\vert \\vert \\boldsymbol{w}\\vert\\vert}y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b) \\geq M \\hspace{0.1cm}\\forall i=1,2,\\dots, n,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"or just"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b) \\geq M\\vert \\vert \\boldsymbol{w}\\vert\\vert \\hspace{0.1cm}\\forall i.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"If we scale the equation so that $\\vert \\vert \\boldsymbol{w}\\vert\\vert = 1/M$, we have to find the minimum of \n",
|
||
"$\\boldsymbol{w}^T\\boldsymbol{w}=\\vert \\vert \\boldsymbol{w}\\vert\\vert$ (the norm) subject to the condition"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b) \\geq 1 \\hspace{0.1cm}\\forall i.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"We have thus defined our margin as the invers of the norm of\n",
|
||
"$\\boldsymbol{w}$. We want to minimize the norm in order to have a as large as\n",
|
||
"possible margin $M$. Before we proceed, we need to remind ourselves\n",
|
||
"about Lagrangian multipliers.\n",
|
||
"\n",
|
||
"\n",
|
||
"## A quick Reminder on Lagrangian Multipliers\n",
|
||
"\n",
|
||
"Consider a function of three independent variables $f(x,y,z)$ . For the function $f$ to be an\n",
|
||
"extreme we have"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"df=0.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"A necessary and sufficient condition is"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{\\partial f}{\\partial x} =\\frac{\\partial f}{\\partial y}=\\frac{\\partial f}{\\partial z}=0,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"due to"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"df = \\frac{\\partial f}{\\partial x}dx+\\frac{\\partial f}{\\partial y}dy+\\frac{\\partial f}{\\partial z}dz.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"In many problems the variables $x,y,z$ are often subject to constraints (such as those above for the margin)\n",
|
||
"so that they are no longer all independent. It is possible at least in principle to use each \n",
|
||
"constraint to eliminate one variable\n",
|
||
"and to proceed with a new and smaller set of independent varables.\n",
|
||
"\n",
|
||
"The use of so-called Lagrangian multipliers is an alternative technique when the elimination\n",
|
||
"of variables is incovenient or undesirable. Assume that we have an equation of constraint on \n",
|
||
"the variables $x,y,z$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\phi(x,y,z) = 0,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"resulting in"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"d\\phi = \\frac{\\partial \\phi}{\\partial x}dx+\\frac{\\partial \\phi}{\\partial y}dy+\\frac{\\partial \\phi}{\\partial z}dz =0.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Now we cannot set anymore"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{\\partial f}{\\partial x} =\\frac{\\partial f}{\\partial y}=\\frac{\\partial f}{\\partial z}=0,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"if $df=0$ is wanted\n",
|
||
"because there are now only two independent variables! Assume $x$ and $y$ are the independent \n",
|
||
"variables.\n",
|
||
"Then $dz$ is no longer arbitrary.\n",
|
||
"\n",
|
||
"\n",
|
||
"However, we can add to"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"df = \\frac{\\partial f}{\\partial x}dx+\\frac{\\partial f}{\\partial y}dy+\\frac{\\partial f}{\\partial z}dz,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"a multiplum of $d\\phi$, viz. $\\lambda d\\phi$, resulting in"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"df+\\lambda d\\phi = (\\frac{\\partial f}{\\partial z}+\\lambda\n",
|
||
"\\frac{\\partial \\phi}{\\partial x})dx+(\\frac{\\partial f}{\\partial y}+\\lambda\\frac{\\partial \\phi}{\\partial y})dy+\n",
|
||
"(\\frac{\\partial f}{\\partial z}+\\lambda\\frac{\\partial \\phi}{\\partial z})dz =0.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Our multiplier is chosen so that"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{\\partial f}{\\partial z}+\\lambda\\frac{\\partial \\phi}{\\partial z} =0.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"We need to remember that we took $dx$ and $dy$ to be arbitrary and thus we must have"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{\\partial f}{\\partial x}+\\lambda\\frac{\\partial \\phi}{\\partial x} =0,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"and"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{\\partial f}{\\partial y}+\\lambda\\frac{\\partial \\phi}{\\partial y} =0.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"When all these equations are satisfied, $df=0$. We have four unknowns, $x,y,z$ and\n",
|
||
"$\\lambda$. Actually we want only $x,y,z$, $\\lambda$ needs not to be determined, \n",
|
||
"it is therefore often called\n",
|
||
"Lagrange's undetermined multiplier.\n",
|
||
"If we have a set of constraints $\\phi_k$ we have the equations"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{\\partial f}{\\partial x_i}+\\sum_k\\lambda_k\\frac{\\partial \\phi_k}{\\partial x_i} =0.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"In order to solve the above problem, we define the following Lagrangian function to be minimized"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\cal{L}(\\lambda,b,\\boldsymbol{w})=\\frac{1}{2}\\boldsymbol{w}^T\\boldsymbol{w}-\\sum_{i=1}^n\\lambda_i\\left[y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b)-1\\right],\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"where $\\lambda_i$ is a so-called Lagrange multiplier subject to the condition $\\lambda_i \\geq 0$.\n",
|
||
"\n",
|
||
"Taking the derivatives with respect to $b$ and $\\boldsymbol{w}$ we obtain"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{\\partial \\cal{L}}{\\partial b} = -\\sum_{i} \\lambda_iy_i=0,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"and"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{\\partial \\cal{L}}{\\partial \\boldsymbol{w}} = 0 = \\boldsymbol{w}-\\sum_{i} \\lambda_iy_i\\boldsymbol{x}_i.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Inserting these constraints into the equation for $\\cal{L}$ we obtain"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\cal{L}=\\sum_i\\lambda_i-\\frac{1}{2}\\sum_{ij}^n\\lambda_i\\lambda_jy_iy_j\\boldsymbol{x}_i^T\\boldsymbol{x}_j,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"subject to the constraints $\\lambda_i\\geq 0$ and $\\sum_i\\lambda_iy_i=0$. \n",
|
||
"We must in addition satisfy the [Karush-Kuhn-Tucker](https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions) (KKT) condition"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\lambda_i\\left[y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b) -1\\right] \\hspace{0.1cm}\\forall i.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"1. If $\\lambda_i > 0$, then $y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b)=1$ and we say that $x_i$ is on the boundary.\n",
|
||
"\n",
|
||
"2. If $y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b)> 1$, we say $x_i$ is not on the boundary and we set $\\lambda_i=0$. \n",
|
||
"\n",
|
||
"When $\\lambda_i > 0$, the vectors $\\boldsymbol{x}_i$ are called support vectors. They are the vectors closest to the line (or hyperplane) and define the margin $M$. \n",
|
||
"\n",
|
||
"\n",
|
||
"We can rewrite"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\cal{L}=\\sum_i\\lambda_i-\\frac{1}{2}\\sum_{ij}^n\\lambda_i\\lambda_jy_iy_j\\boldsymbol{x}_i^T\\boldsymbol{x}_j,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"and its constraints in terms of a matrix-vector problem where we minimize w.r.t. $\\lambda$ the following problem"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{1}{2} \\boldsymbol{\\lambda}^T\\begin{bmatrix} y_1y_1\\boldsymbol{x}_1^T\\boldsymbol{x}_1 & y_1y_2\\boldsymbol{x}_1^T\\boldsymbol{x}_2 & \\dots & \\dots & y_1y_n\\boldsymbol{x}_1^T\\boldsymbol{x}_n \\\\\n",
|
||
"y_2y_1\\boldsymbol{x}_2^T\\boldsymbol{x}_1 & y_2y_2\\boldsymbol{x}_2^T\\boldsymbol{x}_2 & \\dots & \\dots & y_1y_n\\boldsymbol{x}_2^T\\boldsymbol{x}_n \\\\\n",
|
||
"\\dots & \\dots & \\dots & \\dots & \\dots \\\\\n",
|
||
"\\dots & \\dots & \\dots & \\dots & \\dots \\\\\n",
|
||
"y_ny_1\\boldsymbol{x}_n^T\\boldsymbol{x}_1 & y_ny_2\\boldsymbol{x}_n^T\\boldsymbol{x}_2 & \\dots & \\dots & y_ny_n\\boldsymbol{x}_n^T\\boldsymbol{x}_n \\\\\n",
|
||
"\\end{bmatrix}\\boldsymbol{\\lambda}-\\mathbb{1}\\boldsymbol{\\lambda},\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"subject to $\\boldsymbol{y}^T\\boldsymbol{\\lambda}=0$. Here we defined the vectors $\\boldsymbol{\\lambda} =[\\lambda_1,\\lambda_2,\\dots,\\lambda_n]$ and \n",
|
||
"$\\boldsymbol{y}=[y_1,y_2,\\dots,y_n]$. \n",
|
||
"\n",
|
||
"\n",
|
||
"\n",
|
||
"Solving the above problem, yields the values of $\\lambda_i$.\n",
|
||
"To find the coefficients of your hyperplane we need simply to compute"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\boldsymbol{w}=\\sum_{i} \\lambda_iy_i\\boldsymbol{x}_i.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"With our vector $\\boldsymbol{w}$ we can in turn find the value of the intercept $b$ (here in two dimensions) via"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b)=1,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"resulting in"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"b = \\frac{1}{y_i}-\\boldsymbol{w}^T\\boldsymbol{x}_i,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"or if we write it out in terms of the support vectors only, with $N_s$ being their number, we have"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"b = \\frac{1}{N_s}\\sum_{j\\in N_s}\\left(y_j-\\sum_{i=1}^n\\lambda_iy_i\\boldsymbol{x}_i^T\\boldsymbol{x}_j\\right).\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"With our hyperplane coefficients we can use our classifier to assign any observation by simply using"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"y_i = \\mathrm{sign}(\\boldsymbol{w}^T\\boldsymbol{x}_i+b).\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Below we discuss how to find the optimal values of $\\lambda_i$. Before we proceed however, we discuss now the so-called soft classifier. \n",
|
||
"\n",
|
||
"\n",
|
||
"## A soft classifier\n",
|
||
"\n",
|
||
"Till now, the margin is strictly defined by the support vectors. This defines what is called a hard classifier, that is the margins are well defined.\n",
|
||
"\n",
|
||
"Suppose now that classes overlap in feature space, as shown in the\n",
|
||
"figure here. One way to deal with this problem before we define the\n",
|
||
"so-called **kernel approach**, is to allow a kind of slack in the sense\n",
|
||
"that we allow some points to be on the wrong side of the margin.\n",
|
||
"\n",
|
||
"We introduce thus the so-called **slack** variables $\\boldsymbol{\\xi} =[\\xi_1,x_2,\\dots,x_n]$ and \n",
|
||
"modify our previous equation"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b)=1,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"to"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b)=1-\\xi_i,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"with the requirement $\\xi_i\\geq 0$. The total violation is now $\\sum_i\\xi$. \n",
|
||
"The value $\\xi_i$ in the constraint the last constraint corresponds to the amount by which the prediction\n",
|
||
"$y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b)=1$ is on the wrong side of its margin. Hence by bounding the sum $\\sum_i \\xi_i$,\n",
|
||
"we bound the total amount by which predictions fall on the wrong side of their margins.\n",
|
||
"\n",
|
||
"Misclassifications occur when $\\xi_i > 1$. Thus bounding the total sum by some value $C$ bounds in turn the total number of\n",
|
||
"misclassifications.\n",
|
||
"\n",
|
||
"\n",
|
||
"This has in turn the consequences that we change our optmization problem to finding the minimum of"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\cal{L}=\\frac{1}{2}\\boldsymbol{w}^T\\boldsymbol{w}-\\sum_{i=1}^n\\lambda_i\\left[y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b)-(1-\\xi_)\\right]+C\\sum_{i=1}^n\\xi_i-\\sum_{i=1}^n\\gamma_i\\xi_i,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"subject to"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b)=1-\\xi_i \\hspace{0.1cm}\\forall i,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"with the requirement $\\xi_i\\geq 0$.\n",
|
||
"\n",
|
||
"Taking the derivatives with respect to $b$ and $\\boldsymbol{w}$ we obtain"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{\\partial \\cal{L}}{\\partial b} = -\\sum_{i} \\lambda_iy_i=0,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"and"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{\\partial \\cal{L}}{\\partial \\boldsymbol{w}} = 0 = \\boldsymbol{w}-\\sum_{i} \\lambda_iy_i\\boldsymbol{x}_i,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"and"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\lambda_i = C-\\gamma_i \\hspace{0.1cm}\\forall i.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Inserting these constraints into the equation for $\\cal{L}$ we obtain the same equation as before"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\cal{L}=\\sum_i\\lambda_i-\\frac{1}{2}\\sum_{ij}^n\\lambda_i\\lambda_jy_iy_j\\boldsymbol{x}_i^T\\boldsymbol{x}_j,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"but now subject to the constraints $\\lambda_i\\geq 0$, $\\sum_i\\lambda_iy_i=0$ and $0\\leq\\lambda_i \\leq C$. \n",
|
||
"We must in addition satisfy the Karush-Kuhn-Tucker condition which now reads"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"5\n",
|
||
"0\n",
|
||
" \n",
|
||
"<\n",
|
||
"<\n",
|
||
"<\n",
|
||
"!\n",
|
||
"!\n",
|
||
"M\n",
|
||
"A\n",
|
||
"T\n",
|
||
"H\n",
|
||
"_\n",
|
||
"B\n",
|
||
"L\n",
|
||
"O\n",
|
||
"C\n",
|
||
"K"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\gamma_i\\xi_i = 0,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"and"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"y_i(\\boldsymbol{w}^T\\boldsymbol{x}_i+b) -(1-\\xi_) \\geq 0 \\hspace{0.1cm}\\forall i.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"## Kernels and non-linearity\n",
|
||
"\n",
|
||
"The cases we have studied till now, were all characterized by two classes\n",
|
||
"with a close to linear separability. The classifiers we have described\n",
|
||
"so far find linear boundaries in our input feature space. It is\n",
|
||
"possible to make our procedure more flexible by exploring the feature\n",
|
||
"space using other basis expansions such as higher-order polynomials,\n",
|
||
"wavelets, splines etc.\n",
|
||
"\n",
|
||
"If our feature space is not easy to separate, as shown in the figure\n",
|
||
"here, we can achieve a better separation by introducing more complex\n",
|
||
"basis functions. The ideal would be, as shown in the next figure, to, via a specific transformation to \n",
|
||
"obtain a separation between the classes which is almost linear. \n",
|
||
"\n",
|
||
"The change of basis, from $x\\rightarrow z=\\phi(x)$ leads to the same type of equations to be solved, except that\n",
|
||
"we need to introduce for example a polynomial transformation to a two-dimensional training set."
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": null,
|
||
"metadata": {
|
||
"collapsed": false,
|
||
"editable": true
|
||
},
|
||
"outputs": [],
|
||
"source": [
|
||
"import numpy as np\n",
|
||
"import os\n",
|
||
"\n",
|
||
"np.random.seed(42)\n",
|
||
"\n",
|
||
"# To plot pretty figures\n",
|
||
"import matplotlib\n",
|
||
"import matplotlib.pyplot as plt\n",
|
||
"plt.rcParams['axes.labelsize'] = 14\n",
|
||
"plt.rcParams['xtick.labelsize'] = 12\n",
|
||
"plt.rcParams['ytick.labelsize'] = 12\n",
|
||
"\n",
|
||
"\n",
|
||
"from sklearn.svm import SVC\n",
|
||
"from sklearn import datasets\n",
|
||
"\n",
|
||
"\n",
|
||
"\n",
|
||
"X1D = np.linspace(-4, 4, 9).reshape(-1, 1)\n",
|
||
"X2D = np.c_[X1D, X1D**2]\n",
|
||
"y = np.array([0, 0, 1, 1, 1, 1, 1, 0, 0])\n",
|
||
"\n",
|
||
"plt.figure(figsize=(11, 4))\n",
|
||
"\n",
|
||
"plt.subplot(121)\n",
|
||
"plt.grid(True, which='both')\n",
|
||
"plt.axhline(y=0, color='k')\n",
|
||
"plt.plot(X1D[:, 0][y==0], np.zeros(4), \"bs\")\n",
|
||
"plt.plot(X1D[:, 0][y==1], np.zeros(5), \"g^\")\n",
|
||
"plt.gca().get_yaxis().set_ticks([])\n",
|
||
"plt.xlabel(r\"$x_1$\", fontsize=20)\n",
|
||
"plt.axis([-4.5, 4.5, -0.2, 0.2])\n",
|
||
"\n",
|
||
"plt.subplot(122)\n",
|
||
"plt.grid(True, which='both')\n",
|
||
"plt.axhline(y=0, color='k')\n",
|
||
"plt.axvline(x=0, color='k')\n",
|
||
"plt.plot(X2D[:, 0][y==0], X2D[:, 1][y==0], \"bs\")\n",
|
||
"plt.plot(X2D[:, 0][y==1], X2D[:, 1][y==1], \"g^\")\n",
|
||
"plt.xlabel(r\"$x_1$\", fontsize=20)\n",
|
||
"plt.ylabel(r\"$x_2$\", fontsize=20, rotation=0)\n",
|
||
"plt.gca().get_yaxis().set_ticks([0, 4, 8, 12, 16])\n",
|
||
"plt.plot([-4.5, 4.5], [6.5, 6.5], \"r--\", linewidth=3)\n",
|
||
"plt.axis([-4.5, 4.5, -1, 17])\n",
|
||
"plt.subplots_adjust(right=1)\n",
|
||
"plt.show()"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Suppose we define a polynomial transformation of degree two only (we continue to live in a plane with $x_i$ and $y_i$ as variables)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"z = \\phi(x_i) =\\left(x_i^2, y_i^2, \\sqrt{2}x_iy_i\\right).\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"With our new basis, the equations we solved earlier are basically the same, that is we have now (without the slack option for simplicity)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\cal{L}=\\sum_i\\lambda_i-\\frac{1}{2}\\sum_{ij}^n\\lambda_i\\lambda_jy_iy_j\\boldsymbol{z}_i^T\\boldsymbol{z}_j,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"subject to the constraints $\\lambda_i\\geq 0$, $\\sum_i\\lambda_iy_i=0$, and for the support vectors"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"y_i(\\boldsymbol{w}^T\\boldsymbol{z}_i+b)= 1 \\hspace{0.1cm}\\forall i,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"from which we also find $b$.\n",
|
||
"To compute $\\boldsymbol{z}_i^T\\boldsymbol{z}_j$ we define the kernel $K(\\boldsymbol{x}_i,\\boldsymbol{x}_j)$ as"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"K(\\boldsymbol{x}_i,\\boldsymbol{x}_j)=\\boldsymbol{z}_i^T\\boldsymbol{z}_j= \\phi(\\boldsymbol{x}_i)^T\\phi(\\boldsymbol{x}_j).\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"For the above example, the kernel reads"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"K(\\boldsymbol{x}_i,\\boldsymbol{x}_j)=[x_i^2, y_i^2, \\sqrt{2}x_iy_i]^T\\begin{bmatrix} x_j^2 \\\\ y_j^2 \\\\ \\sqrt{2}x_jy_j \\end{bmatrix}=x_i^2x_j^2+2x_ix_jy_iy_j+y_i^2y_j^2.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"We note that this is nothing but the dot product of the two original\n",
|
||
"vectors $(\\boldsymbol{x}_i^T\\boldsymbol{x}_j)^2$. Instead of thus computing the\n",
|
||
"product in the Lagrangian of $\\boldsymbol{z}_i^T\\boldsymbol{z}_j$ we simply compute\n",
|
||
"the dot product $(\\boldsymbol{x}_i^T\\boldsymbol{x}_j)^2$.\n",
|
||
"\n",
|
||
"\n",
|
||
"This leads to the so-called\n",
|
||
"kernel trick and the result leads to the same as if we went through\n",
|
||
"the trouble of performing the transformation\n",
|
||
"$\\phi(\\boldsymbol{x}_i)^T\\phi(\\boldsymbol{x}_j)$ during the SVM calculations.\n",
|
||
"\n",
|
||
"\n",
|
||
"\n",
|
||
"Using our definition of the kernel We can rewrite again the Lagrangian"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\cal{L}=\\sum_i\\lambda_i-\\frac{1}{2}\\sum_{ij}^n\\lambda_i\\lambda_jy_iy_j\\boldsymbol{x}_i^T\\boldsymbol{z}_j,\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"subject to the constraints $\\lambda_i\\geq 0$, $\\sum_i\\lambda_iy_i=0$ in terms of a convex optimization problem"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{1}{2} \\boldsymbol{\\lambda}^T\\begin{bmatrix} y_1y_1K(\\boldsymbol{x}_1,\\boldsymbol{x}_1) & y_1y_2K(\\boldsymbol{x}_1,\\boldsymbol{x}_2) & \\dots & \\dots & y_1y_nK(\\boldsymbol{x}_1,\\boldsymbol{x}_n) \\\\\n",
|
||
"y_2y_1K(\\boldsymbol{x}_2,\\boldsymbol{x}_1) & y_2y_2(\\boldsymbol{x}_2,\\boldsymbol{x}_2) & \\dots & \\dots & y_1y_nK(\\boldsymbol{x}_2,\\boldsymbol{x}_n) \\\\\n",
|
||
"\\dots & \\dots & \\dots & \\dots & \\dots \\\\\n",
|
||
"\\dots & \\dots & \\dots & \\dots & \\dots \\\\\n",
|
||
"y_ny_1K(\\boldsymbol{x}_n,\\boldsymbol{x}_1) & y_ny_2K(\\boldsymbol{x}_n\\boldsymbol{x}_2) & \\dots & \\dots & y_ny_nK(\\boldsymbol{x}_n,\\boldsymbol{x}_n) \\\\\n",
|
||
"\\end{bmatrix}\\boldsymbol{\\lambda}-\\mathbb{1}\\boldsymbol{\\lambda},\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"subject to $\\boldsymbol{y}^T\\boldsymbol{\\lambda}=0$. Here we defined the vectors $\\boldsymbol{\\lambda} =[\\lambda_1,\\lambda_2,\\dots,\\lambda_n]$ and \n",
|
||
"$\\boldsymbol{y}=[y_1,y_2,\\dots,y_n]$. \n",
|
||
"If we add the slack constants this leads to the additional constraint $0\\leq \\lambda_i \\leq C$.\n",
|
||
"\n",
|
||
"We can rewrite this (see the solutions below) in terms of a convex optimization problem of the type"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\begin{align*}\n",
|
||
" &\\mathrm{min}_{\\lambda}\\hspace{0.2cm} \\frac{1}{2}\\boldsymbol{\\lambda}^T\\boldsymbol{P}\\boldsymbol{\\lambda}+\\boldsymbol{q}^T\\boldsymbol{\\lambda},\\\\ \\nonumber\n",
|
||
" &\\mathrm{subject\\hspace{0.1cm}to} \\hspace{0.2cm} \\boldsymbol{G}\\boldsymbol{\\lambda} \\preceq \\boldsymbol{h} \\hspace{0.2cm} \\wedge \\boldsymbol{A}\\boldsymbol{\\lambda}=f.\n",
|
||
"\\end{align*}\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Below we discuss how to solve these equations. Here we note that the matrix $\\boldsymbol{P}$ has matrix elements $p_{ij}=y_iy_jK(\\boldsymbol{x}_i,\\boldsymbol{x}_j)$.\n",
|
||
"Given a kernel $K$ and the targets $y_i$ this matrix is easy to set up. The constraint $\\boldsymbol{y}^T\\boldsymbol{\\lambda}=0$ leads to $f=0$ and $\\boldsymbol{A}=\\boldsymbol{y}$. How to set up the matrix $\\boldsymbol{G}$ is discussed later. Here note that the inequalities $0\\leq \\lambda_i \\leq C$ can be split up into\n",
|
||
"$0\\leq \\lambda_i$ and $\\lambda_i \\leq C$. These two inequalities define then the matrix $\\boldsymbol{G}$ and the vector $\\boldsymbol{h}$.\n",
|
||
"\n",
|
||
"\n",
|
||
"\n",
|
||
"## Different kernels and Mercer's theorem\n",
|
||
"\n",
|
||
"There are several popular kernels being used. These are\n",
|
||
"1. Linear: $K(\\boldsymbol{x},\\boldsymbol{y})=\\boldsymbol{x}^T\\boldsymbol{y}$,\n",
|
||
"\n",
|
||
"2. Polynomial: $K(\\boldsymbol{x},\\boldsymbol{y})=(\\boldsymbol{x}^T\\boldsymbol{y}+\\gamma)^d$,\n",
|
||
"\n",
|
||
"3. Gaussian Radial Basis Function: $K(\\boldsymbol{x},\\boldsymbol{y})=\\exp{\\left(-\\gamma\\vert\\vert\\boldsymbol{x}-\\boldsymbol{y}\\vert\\vert^2\\right)}$,\n",
|
||
"\n",
|
||
"4. Tanh: $K(\\boldsymbol{x},\\boldsymbol{y})=\\tanh{(\\boldsymbol{x}^T\\boldsymbol{y}+\\gamma)}$,\n",
|
||
"\n",
|
||
"and many other ones.\n",
|
||
"\n",
|
||
"An important theorem for us is [Mercer's\n",
|
||
"theorem](https://en.wikipedia.org/wiki/Mercer%27s_theorem). The\n",
|
||
"theorem states that if a kernel function $K$ is symmetric, continuous\n",
|
||
"and leads to a positive semi-definite matrix $\\boldsymbol{P}$ then there\n",
|
||
"exists a function $\\phi$ that maps $\\boldsymbol{x}_i$ and $\\boldsymbol{x}_j$ into\n",
|
||
"another space (possibly with much higher dimensions) such that"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"K(\\boldsymbol{x}_i,\\boldsymbol{x}_j)=\\phi(\\boldsymbol{x}_i)^T\\phi(\\boldsymbol{x}_j).\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"So you can use $K$ as a kernel since you know $\\phi$ exists, even if\n",
|
||
"you don’t know what $\\phi$ is. \n",
|
||
"\n",
|
||
"Note that some frequently used kernels (such as the Sigmoid kernel)\n",
|
||
"don’t respect all of Mercer’s conditions, yet they generally work well\n",
|
||
"in practice.\n",
|
||
"\n",
|
||
"\n",
|
||
"## The moons example"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": null,
|
||
"metadata": {
|
||
"collapsed": false,
|
||
"editable": true
|
||
},
|
||
"outputs": [],
|
||
"source": [
|
||
"from __future__ import division, print_function, unicode_literals\n",
|
||
"\n",
|
||
"import numpy as np\n",
|
||
"np.random.seed(42)\n",
|
||
"\n",
|
||
"import matplotlib\n",
|
||
"import matplotlib.pyplot as plt\n",
|
||
"plt.rcParams['axes.labelsize'] = 14\n",
|
||
"plt.rcParams['xtick.labelsize'] = 12\n",
|
||
"plt.rcParams['ytick.labelsize'] = 12\n",
|
||
"\n",
|
||
"\n",
|
||
"from sklearn.svm import SVC\n",
|
||
"from sklearn import datasets\n",
|
||
"\n",
|
||
"\n",
|
||
"\n",
|
||
"from sklearn.pipeline import Pipeline\n",
|
||
"from sklearn.preprocessing import StandardScaler\n",
|
||
"from sklearn.svm import LinearSVC\n",
|
||
"\n",
|
||
"\n",
|
||
"from sklearn.datasets import make_moons\n",
|
||
"X, y = make_moons(n_samples=100, noise=0.15, random_state=42)\n",
|
||
"\n",
|
||
"def plot_dataset(X, y, axes):\n",
|
||
" plt.plot(X[:, 0][y==0], X[:, 1][y==0], \"bs\")\n",
|
||
" plt.plot(X[:, 0][y==1], X[:, 1][y==1], \"g^\")\n",
|
||
" plt.axis(axes)\n",
|
||
" plt.grid(True, which='both')\n",
|
||
" plt.xlabel(r\"$x_1$\", fontsize=20)\n",
|
||
" plt.ylabel(r\"$x_2$\", fontsize=20, rotation=0)\n",
|
||
"\n",
|
||
"plot_dataset(X, y, [-1.5, 2.5, -1, 1.5])\n",
|
||
"plt.show()\n",
|
||
"\n",
|
||
"from sklearn.datasets import make_moons\n",
|
||
"from sklearn.pipeline import Pipeline\n",
|
||
"from sklearn.preprocessing import PolynomialFeatures\n",
|
||
"\n",
|
||
"polynomial_svm_clf = Pipeline([\n",
|
||
" (\"poly_features\", PolynomialFeatures(degree=3)),\n",
|
||
" (\"scaler\", StandardScaler()),\n",
|
||
" (\"svm_clf\", LinearSVC(C=10, loss=\"hinge\", random_state=42))\n",
|
||
" ])\n",
|
||
"\n",
|
||
"polynomial_svm_clf.fit(X, y)\n",
|
||
"\n",
|
||
"def plot_predictions(clf, axes):\n",
|
||
" x0s = np.linspace(axes[0], axes[1], 100)\n",
|
||
" x1s = np.linspace(axes[2], axes[3], 100)\n",
|
||
" x0, x1 = np.meshgrid(x0s, x1s)\n",
|
||
" X = np.c_[x0.ravel(), x1.ravel()]\n",
|
||
" y_pred = clf.predict(X).reshape(x0.shape)\n",
|
||
" y_decision = clf.decision_function(X).reshape(x0.shape)\n",
|
||
" plt.contourf(x0, x1, y_pred, cmap=plt.cm.brg, alpha=0.2)\n",
|
||
" plt.contourf(x0, x1, y_decision, cmap=plt.cm.brg, alpha=0.1)\n",
|
||
"\n",
|
||
"plot_predictions(polynomial_svm_clf, [-1.5, 2.5, -1, 1.5])\n",
|
||
"plot_dataset(X, y, [-1.5, 2.5, -1, 1.5])\n",
|
||
"\n",
|
||
"plt.show()\n",
|
||
"\n",
|
||
"\n",
|
||
"from sklearn.svm import SVC\n",
|
||
"\n",
|
||
"poly_kernel_svm_clf = Pipeline([\n",
|
||
" (\"scaler\", StandardScaler()),\n",
|
||
" (\"svm_clf\", SVC(kernel=\"poly\", degree=3, coef0=1, C=5))\n",
|
||
" ])\n",
|
||
"poly_kernel_svm_clf.fit(X, y)\n",
|
||
"\n",
|
||
"poly100_kernel_svm_clf = Pipeline([\n",
|
||
" (\"scaler\", StandardScaler()),\n",
|
||
" (\"svm_clf\", SVC(kernel=\"poly\", degree=10, coef0=100, C=5))\n",
|
||
" ])\n",
|
||
"poly100_kernel_svm_clf.fit(X, y)\n",
|
||
"\n",
|
||
"plt.figure(figsize=(11, 4))\n",
|
||
"\n",
|
||
"plt.subplot(121)\n",
|
||
"plot_predictions(poly_kernel_svm_clf, [-1.5, 2.5, -1, 1.5])\n",
|
||
"plot_dataset(X, y, [-1.5, 2.5, -1, 1.5])\n",
|
||
"plt.title(r\"$d=3, r=1, C=5$\", fontsize=18)\n",
|
||
"\n",
|
||
"plt.subplot(122)\n",
|
||
"plot_predictions(poly100_kernel_svm_clf, [-1.5, 2.5, -1, 1.5])\n",
|
||
"plot_dataset(X, y, [-1.5, 2.5, -1, 1.5])\n",
|
||
"plt.title(r\"$d=10, r=100, C=5$\", fontsize=18)\n",
|
||
"\n",
|
||
"plt.show()\n",
|
||
"\n",
|
||
"def gaussian_rbf(x, landmark, gamma):\n",
|
||
" return np.exp(-gamma * np.linalg.norm(x - landmark, axis=1)**2)\n",
|
||
"\n",
|
||
"gamma = 0.3\n",
|
||
"\n",
|
||
"x1s = np.linspace(-4.5, 4.5, 200).reshape(-1, 1)\n",
|
||
"x2s = gaussian_rbf(x1s, -2, gamma)\n",
|
||
"x3s = gaussian_rbf(x1s, 1, gamma)\n",
|
||
"\n",
|
||
"XK = np.c_[gaussian_rbf(X1D, -2, gamma), gaussian_rbf(X1D, 1, gamma)]\n",
|
||
"yk = np.array([0, 0, 1, 1, 1, 1, 1, 0, 0])\n",
|
||
"\n",
|
||
"plt.figure(figsize=(11, 4))\n",
|
||
"\n",
|
||
"plt.subplot(121)\n",
|
||
"plt.grid(True, which='both')\n",
|
||
"plt.axhline(y=0, color='k')\n",
|
||
"plt.scatter(x=[-2, 1], y=[0, 0], s=150, alpha=0.5, c=\"red\")\n",
|
||
"plt.plot(X1D[:, 0][yk==0], np.zeros(4), \"bs\")\n",
|
||
"plt.plot(X1D[:, 0][yk==1], np.zeros(5), \"g^\")\n",
|
||
"plt.plot(x1s, x2s, \"g--\")\n",
|
||
"plt.plot(x1s, x3s, \"b:\")\n",
|
||
"plt.gca().get_yaxis().set_ticks([0, 0.25, 0.5, 0.75, 1])\n",
|
||
"plt.xlabel(r\"$x_1$\", fontsize=20)\n",
|
||
"plt.ylabel(r\"Similarity\", fontsize=14)\n",
|
||
"plt.annotate(r'$\\mathbf{x}$',\n",
|
||
" xy=(X1D[3, 0], 0),\n",
|
||
" xytext=(-0.5, 0.20),\n",
|
||
" ha=\"center\",\n",
|
||
" arrowprops=dict(facecolor='black', shrink=0.1),\n",
|
||
" fontsize=18,\n",
|
||
" )\n",
|
||
"plt.text(-2, 0.9, \"$x_2$\", ha=\"center\", fontsize=20)\n",
|
||
"plt.text(1, 0.9, \"$x_3$\", ha=\"center\", fontsize=20)\n",
|
||
"plt.axis([-4.5, 4.5, -0.1, 1.1])\n",
|
||
"\n",
|
||
"plt.subplot(122)\n",
|
||
"plt.grid(True, which='both')\n",
|
||
"plt.axhline(y=0, color='k')\n",
|
||
"plt.axvline(x=0, color='k')\n",
|
||
"plt.plot(XK[:, 0][yk==0], XK[:, 1][yk==0], \"bs\")\n",
|
||
"plt.plot(XK[:, 0][yk==1], XK[:, 1][yk==1], \"g^\")\n",
|
||
"plt.xlabel(r\"$x_2$\", fontsize=20)\n",
|
||
"plt.ylabel(r\"$x_3$ \", fontsize=20, rotation=0)\n",
|
||
"plt.annotate(r'$\\phi\\left(\\mathbf{x}\\right)$',\n",
|
||
" xy=(XK[3, 0], XK[3, 1]),\n",
|
||
" xytext=(0.65, 0.50),\n",
|
||
" ha=\"center\",\n",
|
||
" arrowprops=dict(facecolor='black', shrink=0.1),\n",
|
||
" fontsize=18,\n",
|
||
" )\n",
|
||
"plt.plot([-0.1, 1.1], [0.57, -0.1], \"r--\", linewidth=3)\n",
|
||
"plt.axis([-0.1, 1.1, -0.1, 1.1])\n",
|
||
" \n",
|
||
"plt.subplots_adjust(right=1)\n",
|
||
"\n",
|
||
"plt.show()\n",
|
||
"\n",
|
||
"\n",
|
||
"x1_example = X1D[3, 0]\n",
|
||
"for landmark in (-2, 1):\n",
|
||
" k = gaussian_rbf(np.array([[x1_example]]), np.array([[landmark]]), gamma)\n",
|
||
" print(\"Phi({}, {}) = {}\".format(x1_example, landmark, k))\n",
|
||
"\n",
|
||
"rbf_kernel_svm_clf = Pipeline([\n",
|
||
" (\"scaler\", StandardScaler()),\n",
|
||
" (\"svm_clf\", SVC(kernel=\"rbf\", gamma=5, C=0.001))\n",
|
||
" ])\n",
|
||
"rbf_kernel_svm_clf.fit(X, y)\n",
|
||
"\n",
|
||
"\n",
|
||
"from sklearn.svm import SVC\n",
|
||
"\n",
|
||
"gamma1, gamma2 = 0.1, 5\n",
|
||
"C1, C2 = 0.001, 1000\n",
|
||
"hyperparams = (gamma1, C1), (gamma1, C2), (gamma2, C1), (gamma2, C2)\n",
|
||
"\n",
|
||
"svm_clfs = []\n",
|
||
"for gamma, C in hyperparams:\n",
|
||
" rbf_kernel_svm_clf = Pipeline([\n",
|
||
" (\"scaler\", StandardScaler()),\n",
|
||
" (\"svm_clf\", SVC(kernel=\"rbf\", gamma=gamma, C=C))\n",
|
||
" ])\n",
|
||
" rbf_kernel_svm_clf.fit(X, y)\n",
|
||
" svm_clfs.append(rbf_kernel_svm_clf)\n",
|
||
"\n",
|
||
"plt.figure(figsize=(11, 7))\n",
|
||
"\n",
|
||
"for i, svm_clf in enumerate(svm_clfs):\n",
|
||
" plt.subplot(221 + i)\n",
|
||
" plot_predictions(svm_clf, [-1.5, 2.5, -1, 1.5])\n",
|
||
" plot_dataset(X, y, [-1.5, 2.5, -1, 1.5])\n",
|
||
" gamma, C = hyperparams[i]\n",
|
||
" plt.title(r\"$\\gamma = {}, C = {}$\".format(gamma, C), fontsize=16)\n",
|
||
"\n",
|
||
"plt.show()"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"## Mathematical optimization of convex functions\n",
|
||
"\n",
|
||
"A mathematical (quadratic) optimization problem, or just optimization problem, has the form"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\begin{align*}\n",
|
||
" &\\mathrm{min}_{\\lambda}\\hspace{0.2cm} \\frac{1}{2}\\boldsymbol{\\lambda}^T\\boldsymbol{P}\\boldsymbol{\\lambda}+\\boldsymbol{q}^T\\boldsymbol{\\lambda},\\\\ \\nonumber\n",
|
||
" &\\mathrm{subject\\hspace{0.1cm}to} \\hspace{0.2cm} \\boldsymbol{G}\\boldsymbol{\\lambda} \\preceq \\boldsymbol{h} \\wedge \\boldsymbol{A}\\boldsymbol{\\lambda}=f.\n",
|
||
"\\end{align*}\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"subject to some constraints for say a selected set $i=1,2,\\dots, n$.\n",
|
||
"In our case we are optimizing with respect to the Lagrangian multipliers $\\lambda_i$, and the\n",
|
||
"vector $\\boldsymbol{\\lambda}=[\\lambda_1, \\lambda_2,\\dots, \\lambda_n]$ is the optimization variable we are dealing with.\n",
|
||
"\n",
|
||
"In our case we are particularly interested in a class of optimization problems called convex optmization problems. \n",
|
||
"In our discussion on gradient descent methods we discussed at length the definition of a convex function. \n",
|
||
"\n",
|
||
"Convex optimization problems play a central role in applied mathematics and we recommend strongly [Boyd and Vandenberghe's text on the topics](http://web.stanford.edu/~boyd/cvxbook/).\n",
|
||
"\n",
|
||
"\n",
|
||
"\n",
|
||
"\n",
|
||
"If we use Python as programming language and wish to venture beyond\n",
|
||
"**scikit-learn**, **tensorflow** and similar software which makes our\n",
|
||
"lives so much easier, we need to dive into the wonderful world of\n",
|
||
"quadratic programming. We can, if we wish, solve the minimization\n",
|
||
"problem using say standard gradient methods or conjugate gradient\n",
|
||
"methods. However, these methods tend to exhibit a rather slow\n",
|
||
"converge. So, welcome to the promised land of quadratic programming.\n",
|
||
"\n",
|
||
"The functions we need are contained in the quadratic programming package **CVXOPT** and we need to import it together with **numpy** as"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": null,
|
||
"metadata": {
|
||
"collapsed": false,
|
||
"editable": true
|
||
},
|
||
"outputs": [],
|
||
"source": [
|
||
"import numpy\n",
|
||
"import cvxopt"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"This will make our life much easier. You don't need t write your own optimizer.\n",
|
||
"\n",
|
||
"\n",
|
||
"\n",
|
||
"We remind ourselves about the general problem we want to solve"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\begin{align*}\n",
|
||
" &\\mathrm{min}_{x}\\hspace{0.2cm} \\frac{1}{2}\\boldsymbol{x}^T\\boldsymbol{P}\\boldsymbol{x}+\\boldsymbol{q}^T\\boldsymbol{x},\\\\ \\nonumber\n",
|
||
" &\\mathrm{subject\\hspace{0.1cm} to} \\hspace{0.2cm} \\boldsymbol{G}\\boldsymbol{x} \\preceq \\boldsymbol{h} \\wedge \\boldsymbol{A}\\boldsymbol{x}=f.\n",
|
||
"\\end{align*}\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Let us show how to perform the optmization using a simple case. Assume we want to optimize the following problem"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\begin{align*}\n",
|
||
" &\\mathrm{min}_{x}\\hspace{0.2cm} \\frac{1}{2}x^2+5x+3y \\\\ \\nonumber\n",
|
||
" &\\mathrm{subject to} \\\\ \\nonumber\n",
|
||
" &x, y \\geq 0 \\\\ \\nonumber\n",
|
||
" &x+3y \\geq 15 \\\\ \\nonumber\n",
|
||
" &2x+5y \\leq 100 \\\\ \\nonumber\n",
|
||
" &3x+4y \\leq 80. \\\\ \\nonumber\n",
|
||
"\\end{align*}\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"The minimization problem can be rewritten in terms of vectors and matrices as (with $x$ and $y$ being the unknowns)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{1}{2}\\begin{bmatrix} x\\\\ y \\end{bmatrix}^T \\begin{bmatrix} 1 & 0\\\\ 0 & 0 \\end{bmatrix} \\begin{bmatrix} x \\\\ y \\end{bmatrix} + \\begin{bmatrix}3\\\\ 4 \\end{bmatrix}^T \\begin{bmatrix}x \\\\ y \\end{bmatrix}.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Similarly, we can now set up the inequalities (we need to change $\\geq$ to $\\leq$ by multiplying with $-1$ on bot sides) as the following matrix-vector equation"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\begin{bmatrix} -1 & 0 \\\\ 0 & -1 \\\\ -1 & -3 \\\\ 2 & 5 \\\\ 3 & 4\\end{bmatrix}\\begin{bmatrix} x \\\\ y\\end{bmatrix} \\preceq \\begin{bmatrix}0 \\\\ 0\\\\ -15 \\\\ 100 \\\\ 80\\end{bmatrix}.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"We have collapsed all the inequalities into a single matrix $\\boldsymbol{G}$. We see also that our matrix"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\boldsymbol{P} =\\begin{bmatrix} 1 & 0\\\\ 0 & 0 \\end{bmatrix}\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"is clearly positive semi-definite (all eigenvalues larger or equal zero). \n",
|
||
"Finally, the vector $\\boldsymbol{h}$ is defined as"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\boldsymbol{h} = \\begin{bmatrix}0 \\\\ 0\\\\ -15 \\\\ 100 \\\\ 80\\end{bmatrix}.\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Since we don't have any equalities the matrix $\\boldsymbol{A}$ is set to zero\n",
|
||
"The following code solves the equations for us"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": null,
|
||
"metadata": {
|
||
"collapsed": false,
|
||
"editable": true
|
||
},
|
||
"outputs": [],
|
||
"source": [
|
||
"# Import the necessary packages\n",
|
||
"import numpy\n",
|
||
"from cvxopt import matrix\n",
|
||
"from cvxopt import solvers\n",
|
||
"P = matrix(numpy.diag([1,0]), tc=’d’)\n",
|
||
"q = matrix(numpy.array([3,4]), tc=’d’)\n",
|
||
"G = matrix(numpy.array([[-1,0],[0,-1],[-1,-3],[2,5],[3,4]]), tc=’d’)\n",
|
||
"h = matrix(numpy.array([0,0,-15,100,80]), tc=’d’)\n",
|
||
"# Construct the QP, invoke solver\n",
|
||
"sol = solvers.qp(P,q,G,h)\n",
|
||
"# Extract optimal value and solution\n",
|
||
"sol[’x’] \n",
|
||
"sol[’primal objective’]"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"We are now ready to return to our setup of the optmization problem for a more realistic case. Introducing the **slack** parameter $C$ we have"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"\\frac{1}{2} \\boldsymbol{\\lambda}^T\\begin{bmatrix} y_1y_1K(\\boldsymbol{x}_1,\\boldsymbol{x}_1) & y_1y_2K(\\boldsymbol{x}_1,\\boldsymbol{x}_2) & \\dots & \\dots & y_1y_nK(\\boldsymbol{x}_1,\\boldsymbol{x}_n) \\\\\n",
|
||
"y_2y_1K(\\boldsymbol{x}_2,\\boldsymbol{x}_1) & y_2y_2K(\\boldsymbol{x}_2,\\boldsymbol{x}_2) & \\dots & \\dots & y_1y_nK(\\boldsymbol{x}_2,\\boldsymbol{x}_n) \\\\\n",
|
||
"\\dots & \\dots & \\dots & \\dots & \\dots \\\\\n",
|
||
"\\dots & \\dots & \\dots & \\dots & \\dots \\\\\n",
|
||
"y_ny_1K(\\boldsymbol{x}_n,\\boldsymbol{x}_1) & y_ny_2K(\\boldsymbol{x}_n\\boldsymbol{x}_2) & \\dots & \\dots & y_ny_nK(\\boldsymbol{x}_n,\\boldsymbol{x}_n) \\\\\n",
|
||
"\\end{bmatrix}\\boldsymbol{\\lambda}-\\mathbb{I}\\boldsymbol{\\lambda},\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"subject to $\\boldsymbol{y}^T\\boldsymbol{\\lambda}=0$. Here we defined the vectors $\\boldsymbol{\\lambda} =[\\lambda_1,\\lambda_2,\\dots,\\lambda_n]$ and \n",
|
||
"$\\boldsymbol{y}=[y_1,y_2,\\dots,y_n]$. \n",
|
||
"With the slack constants this leads to the additional constraint $0\\leq \\lambda_i \\leq C$.\n",
|
||
"\n",
|
||
"**code will be added**"
|
||
]
|
||
}
|
||
],
|
||
"metadata": {},
|
||
"nbformat": 4,
|
||
"nbformat_minor": 4
|
||
} |