Kernel Function and Kernel Trick

-

 Parametric Models

They store the parameter only and not the entire training dataset.

Memory Based Methods

Store entire training data or a subset of the training dataset. They are fast to train, but prediction takes a longer time. Eg. Knn

Need for Kernels

Not all problems are linearly separable. Also, when a feature vector is transformed to a higher dimensional space, linearly separable problems become non linearly separable.

For example, let us consider a point (x,y). In the 2D space it might be non-linearly separable. that is a straight line cannot separate the points. We can add a new dimension that is a combination of the existing dimensions. Let it be

z = x^2 + y^2

Now the transformed feature space is (x, y, z) and is of 3 dimensions. In this dimension, z might help to move the data points along x and y in such a way that there is a linear separator between them. That is we move from the original feature space to a transformed feature space.

We cannot say how many dimensions we need to increase to get this linearity. It depends on the complexity of the data distribution and the problem to be solved.

Linearly Separable Data:

There is no need to change the dimension. We retain the original dimension or feature space.

Dot Product

It is a similarity measure that measures the distance between 2 points in space. If the dot product is positive, the points are similar to each other and the angle between them will be less than 90 degrees. A zero dot product show the vectors are dissimilar and are at 90 degrees to each other. A negative dot product shows they are pointing in opposite directions and have significantly different properties and so they are pointing in different directions.

Kernel Trick

We know that non-linearly separable problems in lower dimensions can often become linearly separable when transformed into higher dimensions. However, increasing the dimensionality also increases computational complexity. Is there a way to obtain a value in the higher dimension that maintains the similarity measure between � and � in the lower dimension? Although we will not obtain the same value for the similarity measure in higher dimensions, this value will still reflect the relative distances between points, preserving their relationships.

Consider the following example, which demonstrates that the dot product in a higher dimension maintains the relative relationship observed in the original space.

Let x=(x1,x2,x3), y = (y1,y2,y3) in 3D feature space. Let is convert it to a 9D feature space as follows: f(x)=(x1.x1, x1.x2, x1.x3, x2.x1, x2.x2, x2.x3, x3.x1, x3.x2, x3.x3)

Let us understand the concept of kernel with a numercial example. x=(1,2,3), y=(4,5,6)

Then transforming the feature space to 9D space (x1.x1, x1.x2, x1.x3, x2.x1, x2.x2, x2.x3, x3.x1, x3.x2, x3.x3) results in:

f(x)=(1,2,3,2,4,6,3,6,9) f(y)=(16,20,24,20,25,30,24,30,36) The dot product in the transformed feature space is given by: f(x).f(y) = 1024

Let us use a function K(x,y) such that K(x,y) = (x.y)^2

x and y are points in 3D space, then

K(x,y) = ((1,2,3).(4,5,6) ) ^ 2

= 32^2 = 1024

Note that this is a special case in which the similarity value is preserved in the higher dimension and usually the numerical value of the similarity measure is not the same in the higher dimension.

Kernel function

The function K(x,y) is called the kernel function and it represents the similarity between the points in the transformed space. Kernel function is the tool used to perform kernel trick. These functions are applied on the samples in the training dataset. They help to create non-linear decision boundaries in non-parametric models.

Lets take the kernel function used in the example,

K(x,y) = (x.y)^2

This performs the dot product of vectors in 3D space and gives the effect of computing the dot product of f(x) and f(y) in the 9D space. Note it does not transform x and y to f(x) and f(y) to find the effect in 9D space. This transformation to higher dimension is usually the most computationally expensive and that has been taken care of.

Kernel Matrix
It is also called the gram matrix and it gives the pairwise similarity between the data points after applying the kernel function.





Comments

Post a Comment

Popular posts from this blog

ANN Series - 10 - Backpropagation of Errors

-
Image
Watch the video to understand the forward pass in an ANN. Backpropagation, short for "backward propagation of errors," is a fundamental algorithm used for training artificial neural networks. It efficiently computes the gradient of the loss function with respect to the weights of the network, which is essential for adjusting the weights and minimizing the loss through gradient descent or other optimization techniques. The process involves two main phases: a forward pass and a backward pass.     Forward Pass   1. Input Layer:  The input features are fed into the network. 2. Hidden Layers:  Each neuron in these layers computes a weighted sum of its inputs (from the previous layer or the input layer) plus a bias term. This sum is then passed through an activation function to produce the neuron's output. This process repeats layer by layer until the output layer is reached. 3. Output Layer:  The final output of the network is computed, which is then used to calculate the loss
Read more

Regression 10 - Pseudo-Inverse Matrix Approach - Relationship between MLE and LSA - Derivation

-
Pseudo-Inverse Matrix Approach: The pseudo-inverse matrix approach is essentially the OLS approach. It provides a solution to the linear regression problem by minimizing the sum of squared residuals between the observed and predicted values. This approach is a direct algebraic method that does not make any probabilistic assumptions about the residuals; it simply finds the best fit in the least squares sense.   For simple linear regression, the MLE estimates of the coefficients will actually be the same as the Ordinary Least Squares (OLS) estimates, which are also the same as what you get from the pseudo-inverse matrix method, under the assumption of i.i.d. normal errors. In this blog we show how to prove that  Maximization of likelihood function under conditional Gaussian noise for a linear model is similar to the minimization of the sum of the squares error function.  The complete derivation along with formulae used are provided. Ensure that you go through the previous blogs to get a
Read more

Regression 9 - Maximum Likelihood Estimation(MLE) Approach for Regression - Derivation

-
  MLE Approach: When performing linear regression using MLE under the assumption that the residuals (errors) are independently and identically distributed (i.i.d.) with a normal distribution, we estimate the regression coefficients that maximize the likelihood of observing the given data. In this blog we see how to perform regression on a dataset that applies MLE for model fitting. The mathematical assumptions and derivations are given in detail.   The MLE approach gives you point estimates for the coefficients (mean of the likelihood distribution), and you can also compute the variance-covariance matrix of these estimates, which gives you the variances (and covariances) of the estimates. These variances are a measure of the uncertainty or the spread of the likelihood distribution of the parameter estimates. For simple linear regression, the MLE estimates of the coefficients will actually be the same as the Ordinary Least Squares (OLS) estimates, which are also the same as what you get
Read more