ORF523: Classification, SVM, Kernel Learning

In this post I will go over some simple examples of applications for the optimization techniques that we have seen in the previous lectures. The general theme of these examples is the canonical Machine Learning problem of classification. Since the focus here is on optimization I will not discuss the strong interplay between the design of the optimization problems and their statistical properties in terms of generalization error. The interested reader is referred to the book ‘Learning with Kernels’ by Schölkopf and Smola, and the paper ‘Learning the kernel matrix with semi-definite programming’ by Lanckriet, Cristianini, Bartlett, El Ghaoui and Jordan.

Linear classification

Let $latex {(x_1, y_1), \hdots, (x_m, y_n) \in {\mathbb R}^n \times \{-1,1\}}&fg=000000$ be a ‘labeled’ data set. Imagine for instance that $latex {x_i}&fg=000000$ is a picture, and $latex {y_i}&fg=000000$ is equal to $latex {1}&fg=000000$ if the picture contains an apple. Our goal is to construct a map (or a classifier) from $latex {{\mathbb R}^n}&fg=000000$ to $latex {\{-1,1\}}&fg=000000$ that correctly classifies our data set. We restrict our attention to linear classifiers of the form $latex {x \mapsto \mathrm{sgn}(w^{\top} x + b)}&fg=000000$. In other words we are looking for a separating hyperplane between $latex {\{x_i : y_i =1\}}&fg=000000$ and $latex {\{x_i : y_i = -1\}}&fg=000000$. Let us assume that such an hyperplane exists, we say that the data is linearly separable.

For several reasons it seems reasonable to search for the hyperplane that maximizes the margin, that is that maximizes the distance between the hyperplane and its closest data points. Up to renormalization one can assume that for all points one has $latex {|w^{\top} x_i + b| \geq 1}&fg=000000$, in which case a quick picture shows that the margin is proportional to $latex {1 / \|w\|^2}&fg=000000$. Thus we arrive at the following optimization problem:

$latex \displaystyle \begin{array}{rcl} & \min_{(w,b) \in {\mathbb R}^n \times {\mathbb R}} & \|w\|^2 \\ & \text{subject to} & y_i(w^{\top} x_i + b) \geq 1, i =1, \hdots, m . \end{array} &fg=000000$

This problem can be efficiently solved with Interior Point Methods. It is a Quadratic Program with linear constraints.

Support Vector Machine (SVM)

Let us look at the Lagrangian for the linear classification problem described above:

$latex \displaystyle L(w, b, \lambda) = \frac12 \|w\|^2 – \sum_{i=1}^m \lambda_i (y_i(w^{\top} x_i + b) -1) , \qquad \lambda \in {\mathbb R}_+^m .&fg=000000$

Since strong duality clearly holds true for this problem (see previous post), one has by the KKT conditions that at the optimum $latex {(w^*, b^*)}&fg=000000$ for the primal, there exists $latex {\lambda^* \in {\mathbb R}^m_+}&fg=000000$ (a solution to the dual problem) such that

$latex \displaystyle w^* – \sum_{i=1}^m \lambda_i^* y_i x_i = 0 \ \ \ \ \ (1)&fg=000000$

$latex \displaystyle \sum_{i=1}^m \lambda_i^* y_i = 0 \ \ \ \ \ (2)&fg=000000$

$latex \displaystyle \lambda_i^* (y_i({w^*}^{\top} x_i + b^*) -1) = 0, i =1, \hdots, m . \ \ \ \ \ (3)&fg=000000$

The last equation (3) states that at any point $latex {x_i}&fg=000000$ which is not on the boundary of decision the corresponding Lagrange multiplier $latex {\lambda_i^*}&fg=000000$ must be equal to $latex {0}&fg=000000$. The points $latex {x_i}&fg=000000$ on the boundary of decision are calledsupport vectors. In particular, given equation (1) one can see that in fact the optimal classifier depends only on these support vectors, as $latex {w^* = \sum_{i=1}^m \lambda_i^* y_i x_i}&fg=000000$, hence the name Support Vector Machine.

Another consequence of (1) is that the solution to the primal problem can be immediately obtained from the solution of the dual problem. Since the KKT conditions are necessary and sufficient for optimality (by convexity), we can restrict our search over $latex {(w,b, \lambda)}&fg=000000$ that satisfies equations (1)(2)(3). In particular the dual problem can now be written as:

$latex \displaystyle \begin{array}{rcl} & \max_{\lambda \in {\mathbb R}_+^m} & \frac12 \| w \|^2 – \sum_{i=1}^m \lambda_i (y_i w^{\top} x_i -1) \\ & \text{subject to} & \sum_{i=1}^m \lambda_i y_i = 0 \;\; \text{and} \;\; w = \sum_{i=1}^m \lambda_i y_i x_i . \end{array} &fg=000000$

A simple rewriting now yields the standard dual form of the SVM, with $latex {e=(1, \hdots, 1) \in {\mathbb R}^m}&fg=000000$, $latex {K \in {\mathbb R}^{m \times m}}&fg=000000$ the Gram matrix defined by $latex {K_{i,j} = x_i^{\top} x_j}&fg=000000$, and $latex {A \circ B}&fg=000000$ the Hadamard product between two matrices,

$latex \displaystyle \begin{array}{rcl} & \max_{\lambda \in {\mathbb R}_+^m} & \lambda^{\top} e – \frac12 \lambda^{\top} (K \circ y y^{\top}) \lambda \\ & \text{subject to} & \lambda^{\top} y = 0 . \end{array} &fg=000000$

The kernel trick

In the dual formulation of the SVM it happens that the original data $latex {x_1, \hdots, x_m \in {\mathbb R}^n}&fg=000000$ only appears in the form of the Gram matrix $latex {K}&fg=000000$. The kernel trick consists in replacing the Gram matrix in the original space by the Gram matrix in a potentially much higher dimensional space. Formally one considers a mapping $latex {\Phi}&fg=000000$ from the original space of data $latex {\mathcal{X}}&fg=000000$ ($latex {\mathcal{X} ={\mathbb R}^n}&fg=000000$ in our example so far, but more generally it could be an arbitrary set) to some Hilbert space $latex {\mathcal{H}}&fg=000000$. Then the Gram matrix $latex {K}&fg=000000$ is computed in the feature space $latex {\mathcal{H}}&fg=000000$, that is $latex {K_{i,j} = \langle \Phi(x_i), \Phi(x_j) \rangle}&fg=000000$. Solving the (dual) SVM with this Gram matrix then gives a linear classifier in the feature space, which when viewed in the original space might be highly non-linear.

What is important to understand is that one does not need to compute the mapping $latex {\Phi}&fg=000000$, but only inner products of the form $latex {\langle \Phi(x), \Phi(x’) \rangle}&fg=000000$. In many interesting cases the latter operation is much cheaper, and it makes sense to focus the method around this last object. The idea is that it suffices to have a kernel $latex {k: \mathcal{X} \times \mathcal{X} \rightarrow {\mathbb R}}&fg=000000$ such that for any $latex {x_1, \hdots, x_m}&fg=000000$ the kernel Gram matrix $latex {K_{i,j} = k(x_i, x_j)}&fg=000000$ is positive definite. We call such a kernel a positive definite kernel. Typical examples on $latex {\mathcal{X} \subset {\mathbb R}^n}&fg=000000$ are the polynomial kernel $latex {k_d(x, x’) = (x^{\top} x’)^d}&fg=000000$, and the Gaussian kernel $latex {k_{\sigma}(x, x’) = \exp\left( – \frac{1}{2 \sigma^2} \|x – x’\|^2\right)}&fg=000000$.

Kernel learning

A natural idea is to put the kernel Gram matrix as part of the objective, in order to maximize the resulting margin. This leads to the following optimization problem

$latex \displaystyle \begin{array}{rcl} & \min_{K \succ 0} \max_{\lambda \in {\mathbb R}_+^m} & \lambda^{\top} e – \frac12 \lambda^{\top} (K \circ y y^{\top}) \lambda \\ & \text{subject to} & \lambda^{\top} y= 0 . \end{array} &fg=000000$

We show now how to express the above problem as an SDP. The idea is apply the KKT conditions and strong duality to transform the maximization problem (over $latex {\lambda}&fg=000000$) into a minimization problem. Let us see how this works. First we consider the Lagrangian associated with the maximization problem:

$latex \displaystyle L(\lambda, \alpha, \nu) = \lambda^{\top} e – \frac12 \lambda^{\top} (K \circ y y^{\top}) \lambda + \nu \lambda^{\top} y + \alpha^{\top} \lambda .&fg=000000$

The KKT conditions shows that at the optimum, one has (note that $latex {K \circ y y^{\top} \succ 0}&fg=000000$ and thus it is invertible)

$latex \displaystyle \lambda^* = (K \circ y y^{\top})^{-1} (e + \nu^* y + \alpha^*) .&fg=000000$

Thus the dual of the maximization problem above can be written as

$latex \displaystyle \min_{\nu \in {\mathbb R}, \alpha \in {\mathbb R}_+^m} L\bigg((K \circ y y^{\top})^{-1} (e + \nu y + \alpha), \alpha, \nu\bigg) = \min_{\nu \in {\mathbb R}, \alpha \in {\mathbb R}_+^m} \frac12 (e + \nu y + \alpha) (K \circ y y^{\top})^{-1} (e + \nu y + \alpha) .&fg=000000$

Finally we use Schur complement lemma to write this minimization into the constraints as an SDP.

Lemma 1 (Schur complement) Let

$latex \displaystyle X = \left( \begin{array}{cc} A & B \\ B^{\top} & C \end{array} \right) ,&fg=000000$

where $latex {A}&fg=000000$ is positive definite. Then $latex {X}&fg=000000$ is positive semi-definite if and only if $latex {C – B^{\top} A^{-1} B}&fg=000000$ (the Schur complement of $latex {A}&fg=000000$ in $latex {X}&fg=000000$) is positive semi-definite.

In our case we use this lemma to write

$latex \displaystyle t \geq \frac12 (e + \nu y + \alpha) (K \circ y y^{\top})^{-1} (e + \nu y + \alpha) \Leftrightarrow \left( \begin{array}{cc} K \circ y y^{\top} & e + \nu y + \alpha \\ (e + \nu y + \alpha)^{\top} & 2 t \end{array} \right) \succeq 0 .&fg=000000$

Putting everything together we have proved that our original problem is equivalent to:

$latex \displaystyle \begin{array}{rcl} & \min_{K, t, \alpha, \nu} & t \\ & \text{subject to} & \left( \begin{array}{cccc} K & 0 & 0 & 0 \\ 0 & \mathrm{diag}(\alpha) & 0 & 0 \\ 0 & 0 & K \circ y y^{\top} & e + \nu y + \alpha \\ 0 & 0 & (e + \nu y + \alpha)^{\top} & 2t \end{array} \right)\succeq 0 , \end{array} &fg=000000$

which is clearly an SDP with equality constraints. Note that for statistical reasons one usually adds a constraint of the form $latex {\mathrm{Tr}(K) \leq c}&fg=000000$ (for some fixed constant $latex {c > 0}&fg=000000$) in the above optimization problem.

This entry was posted in Optimization. Bookmark the permalink.

2 Responses to "ORF523: Classification, SVM, Kernel Learning"