How is the optimal hyperplane computed?

Let’s introduce the notation used to define formally a hyperplane:

f(x) = \beta_{0} + \beta^{T} x,

where \beta is known as the weight vector and \beta_{0} as the bias.

The optimal hyperplane can be represented in an infinite number of different ways by scaling of \beta and \beta_{0}. As a matter of convention, among all the possible representations of the hyperplane, the one chosen is

|\beta_{0} + \beta^{T} x| = 1

where x symbolizes the training examples closest to the hyperplane. In general, the training examples that are closest to the hyperplane are called support vectors. This representation is known as the canonical hyperplane.

Now, we use the result of geometry that gives the distance between a point x and a hyperplane (\beta, \beta_{0}):

\mathrm{distance} = \frac{|\beta_{0} + \beta^{T} x|}{||\beta||}.

In particular, for the canonical hyperplane, the numerator is equal to one and the distance to the support vectors is

\mathrm{distance}_{\text{ support vectors}} = \frac{|\beta_{0} + \beta^{T} x|}{||\beta||} = \frac{1}{||\beta||}.

Recall that the margin introduced in the previous section, here denoted as M, is twice the distance to the closest examples:

M = \frac{2}{||\beta||}

Finally, the problem of maximizing M is equivalent to the problem of minimizing a function L(\beta) subject to some constraints. The constraints model the requirement for the hyperplane to classify correctly all the training examples x_{i}. Formally,

\min_{\beta, \beta_{0}} L(\beta) = \frac{1}{2}||\beta||^{2} \text{ subject to } y_{i}(\beta^{T} x_{i} + \beta_{0}) \geq 1 \text{ } \forall i,

where y_{i} represents each of the labels of the training examples.

This is a problem of Lagrangian optimization that can be solved using Lagrange multipliers to obtain the weight vector \beta and the bias \beta_{0} of the optimal hyperplane.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s