Machine Learning, Basis Expansion, Kernels(1) and Kernels(2)

2015-February-13 Scott Hendrickson

Attempt to draw a conceptual line connecting some machine learning techniques we have been using and talking about recently, a short discussion about Kernel choices for SVM and finding non-linear relationships in data...

Logistic Regression and SVM classifiers are linear

These methods formulate an optimization problem that locates separating hyperplanes.

Logistic Regression

[Following DrJ from last week] Cost function:

$ C = - \left( y \: \text{log}(h_{\theta}(x)) + (1-y) \: \text{log}(1-h_{\theta}) \right) $

The hypothesis function, $h$:

$ h_{\theta}(x) = \frac{1}{1 + e^{-z}}$, where $ \theta^T x = z $.

This function takes an arbitrary input vector $x$ and creates a linear combination with the model vector $ \theta $ to create an output on [0,1].

The common cost function formulation for Logistic Regression in terms of z:

$ C = -y \: \text{log} \frac{1}{1+exp(-z)} - (1-y) \: \text{log} \left( 1-\frac{1}{1+exp(-z)} \right) $

Five points to notice about the above forumlation:

1. Optimizating $ C $ determines our model parameters $ \theta $ from features $ x $ and targets $ y $.

2. z is a scalar $ \theta^T x = z $

3. $ \theta^T \perp x $ implies $ z = 0 $ and this means $ h_{\theta}(x) = \frac{1}{1 + e^{0}} = \frac{1}{2} $. This condition defines the direction of the separating hyperplane.

4. The hyperplane passes through the origin.

5. $ \theta^T x = z $ is linear in features $x$

Let's see it in action.

Separate 2 noisy groups

What about when a plane can't do the job?

Maybe relax (3) and (4) a bit...

We can make this learning method a little more flexible by relaxing (3) and (4). As long as we don't change conditions (1-3), the Logistic Regression strategy still works (why?).

Allow arbitrary translation from the origin by a constant and determined the constant as part of the model:

$ z = \theta^T x $

$ \theta = \left( \begin{array}{ccc} \theta_1 \\ \theta_2 \\ \ldots \\ \theta_n \\ \theta_{\text translate} \end{array} \right)$

$ x = \left( \begin{array}{ccc} x_1 \\ x_2 \\ \ldots \\ x_n \\ 1 \end{array} \right)$

$ z = \theta^T x = \theta_1 x_1 + \theta_2 x_2 + \ldots + \theta_{\text translate} $

Or factoring out $\theta_1$,

$ z = \theta^T x = \theta_1 (x_1 + \theta_2^\prime x_2 + \ldots + \theta_{\text translate}^\prime) $

where $ \theta_2^\prime = \frac{\theta_2}{\theta_1} $ etc.

Now, the scaling of the transition region, the hyperplane location and the hyperplane direction are determined by the model.

A second perspective...

The strategy above for relaxing (4) can be seen as finding $ z(x) $ by embedding the original feature vector, $x$, in a space with 1 additional dimension. If the originial feature vectors has dimension $n$, then the new features space has dimension, $n+1$.

We might have formulated the problem as a translation $x \rightarrow x - x^0$, and expansion $ x - x^0 \rightarrow \alpha (x - x^0) $ giving the slightly less general formulation,

$ z = \theta^T \alpha (x - x^0) = \theta_1 \alpha_1 (x_1 - x^0_1) + \theta_2 \alpha_2 (x_2 - x^0_2) + \ldots + \theta_n \alpha_n (x_n - x^0_n) $

Because we are going to let the optimizer find the model parameters $\theta$, we usually absorb the $\alpha$s into the $\theta$s. In this limited formulation, $ z(x) $ is only a function of the distance to the hyperplane.

This discussion suggests that one strategy for expanding the capabilties of our classifier is to think up favorable coordinate transformations. When we imagine a useful coordinate trasformation, we calculate $z$,

$ z = \theta^T \mathbf{M} x = \theta^T x^\prime $.

I propose to...Think up embedding/coordinate transformations that make the problem that is essentially a non-linear relationship in the original feature space into a linear relationship in some transformed feature space.

Then our Logistic Regression will work to build models of non-linear relationships. Hold that thought.

Might inspire some creative geometric thinking, but...

The question is "In what coordinate system is this essentially non-linear relationship a linear relationship?" Thinking up the right coordinate transformations from this geometric point of view might be practically impossible!

How about relaxing (5) directly?

The "absorb the $\alpha$s" comment above might push us to different interesting idea. What if we could find a useful representation of $z$ that:

1. Is non-linear in input features $x$
2. Lets the optimizer sort out the relative strenghts and types of the non-linearity at learning time

From ESL,

The core idea of [basis expansion] is to augment/replace the vectors of inputs X with additional variables, which are transformations of X, and then use linear models in the new space of derived input features.  - ESL pg 139

This functional approach changes our strategy toward finding $z$ as a functional expansion in $x$.

Basis Expansion

Maybe we can try a polynomial expansion of $z$? They are easy to write down and we are pretty confident you can represent any form of $z$ we need.

$ z(x) = \Sigma^\infty_{m=1}\beta_m x^n $

Done. We can now represent a huge range of non-linear relationships between $z$ and $x$ in a way that allows the Logistic Regression method to work by finding a hyperplane. However, this is going to present some challenges for practical machine learning. We have to determine an inifite number of $\beta$s in training!

We need a finite expansion.

One idea to assume the higher-order terms are less important and truncate the series after a couple of terms. Absorb the constants into the $\theta$s.

Try:

$ z(x) = \theta_1 x^2 + \theta_2 x + \theta_3 $

Seems promising--we just found a boundary defined by a conical section. Maybe this is enough. If not, can we generalize the idea?

Yes, bring on the basis functions.

Rewrite $z$,

$ z(x) = \Sigma^M_{m=1}\beta_m h_m(x) $

Before we apply to machine learning, let's see how the function expansion might look.

Let's choose a localized basis function with parameters that define the location and extent. One important example is the Raidal Basis Function.

Best fit if we use only one basis function.

Best fit if we use more than one basis function.

To see how additional basis functions improve the fit, change the value of n in the line gx=parital(g,n) below.

Ok, n=4 gives a nice smooth fit. Now we are ready to try a machine learning prolem in 2d.

XOR requires a non-linear model

Lets try using the RBF.

Two problems, one fundamental, one practical:

1. How many basis functions do I need?
2. We have non-muliplicative parameters

The first is much like our problem with the infinite series. Remember, we will always use regularization in practical applications, so have a few too many basis functions might still work fine, while having too few will underperform. A parameter search across the number of basis functions might prove useful.

The second problem is a practical problem with common libraries. There is nothing in theory that won't let us minimize the cost function over the parameters of the functions, but additional care for stability, convergence etc will be required.

Proposes a set of basis functions located in each of the quadrants.

Train on the XOR data using our basis funcitons

Given this particular set of basis functions, we can also reach into the estimator above and find out what the relative weights were in fitting the model to this data:

Kernel Smoothing

Turn here for a language-driven diversion.

Kernel smoothing is a class of regression techniques that achieve flexibility in estimating the regression function $f(x)$ by fitting a different but simple model separate at each query point $x_0$. This is done by using only the observations close to the target point $x_0$ to fit the simple model, and in such a way that the resulting estimated function $f(x)$ is smooth.

Kernel Methods

Above, we looked a coordinate transformations as a way to find a space where the problem became linear. For the Logistic Regression, we noted a simple way to forumulate it in terms of only distances to the separating hyperplane. This strategy didn't look very promising because guessing the right coordinate transformation seemed impossible.

If we had a machine learning technique that more natrually compatible with formuation of the cost function based only on inner products, we can use different trick to solve the problem.

Remember last week when Josh talked about Support Vector Machines. The cost function,

$ \text{min}_{\theta} C \sum \limits_{i=1}^{m} \lbrack y_i \text{cost}_1(\theta^T f) + (1-y_i) \text{cost}_0(\theta^T f) \rbrack + \frac{1}{2} \sum \limits_{j=1}^{n} \theta_j^2 $

with f defined by,

$ f = \text{exp} \left( - \frac{\Vert x - l^i \Vert ^2}{2 \sigma^2} \right) $

This function depends on the square of the distance between the feature vectors.

$ | x - x^\prime |^2 $

This can be written in terms of the inner product of the feature vectors.

$ | x - x^\prime |^2 = x \cdot x^\prime $

What's the trick?

1. Data items are embeded into a vector space called the feature space.
2. Linear relations are sought among the images of the data items in the feature space.
3. The algorithms (e.g. SVM) are implemented in such a way that the coordinates of teh embedded points are not needed, only the pairwise inner products.
4. The pariwise inner products can be computed efficiently direction from the origianl data items usein a kernel function.

A kernel function is a function $\kappa$ the for all $x$, $z$ $\in$ $X$ satisfies,

$ \kappa(x,z) = <\phi(x), \phi(z)> $

where $\phi$ is a mapping from X to an inner product feature space F

$\phi:x \rightarrow \phi(x) \in F$

Since the inner product is expressed in the transformed space by the kernel function, we might make some headway by looking at the generic properties of the kernel functions and giving up on actually finding the transformation, $\phi(x)$.

Inner product spaces with the additional properties of being separable and complete are Hilbert spaces. When $\kappa$ satisfies the finitely positive semi-definate property, we refer to it as a Reproducing kernel Hilbert Space (RKHS).

It can be shown that once we have kernels $\kappa_1$ and $\kappa_2$ we can construct new kernels by:

1. $\kappa(x,z) = \kappa_1(x,z) + \kappa_2(x,z)$
2. $\kappa(x,z) = \alpha \kappa_1(x,z)$
3. $\kappa(x,z) = \kappa_1(x,z) \kappa_2(x,z)$
4. $\kappa(x,z) = f(x) f(z)$
5. $\kappa(x,z) = \kappa_3(\phi(x),\phi(z))$
6. $\kappa(x,z) = x^\prime B z$

Now we just put our efforts into kernel construction.

RBF and SVM

It turns out that a useful kernel is the RBF.

Last Note: ESL points out that it is write the solution based no an expansion on RBF basis functions and based on the kernel smoothing propertes sketched above in a way that shows them to be isomorphic. So the kernel(1) and kernel(2) concepts are not completely disconnected as they might at first appear. (See Chapters 5 & 6.)