# **KERNEL METHODS**

In the methods seen in the previous chapters, during the learning phase, the training set is used to obtain a set of parameters. In this phase, called learning, the optimal combination of the weight is achieved optimizing a certain loss function. After this learning phase, the training data is discarded and the predictions for new inputs are based only on the learned parameters. In this class of method, the training points are "remembered" by $\textbf w$. There is another class of methods, those discussed in this chapter, in which the training points are used also during the prediction phase. *Memory-based* methods involve storing the entire training data and make prediction using a certain metrics of similarity between these points and the new inputs. Kernel methods belong to the class of memory-based approach. The former methods require a long training time but the prediction is very fast, for kernel methods it is the opposite. We call the methods belonging to the first approach **parametric models**, while the methods belonging to the second **non-parametric methods**. Since the prediction phase is not fast, non-parametric methods are not appropriate for online learning.

In real world applications we are usually interested in performing nonlinear regression or nonlinear classification. Linear model are very easy to implement, fast and easy to interpret but cannot be applied in such scenarios. The two figures below represent situation where, on the left linear regression fails, and on the right fails the linear classification.

<p align="center">

</p>

Kernel methods allow linear methods to work in nonlinear setting by mapping data to an higher dimensions where it exhibits linear patterns. They provide a different way to solve the same problem! Let's consider some example. Consider the binary classification problem in which we want to divide red points from blue points. Obviously, in the figure on the left, no linear separator exists to achieve this goal. However, we can solve this problem with the following map: $x \rightarrow \{x, x^2\}$. Data now becomes linearly separable in the new representation.

<p align="center">

</p>

Let's look at another example in which each point is represented by two features. Also in this case no linear separator exists. As in the previous case, applying a simple map we can make the points linearly separable into an higher dimensional space. In this case the mapping is $\textbf x = \{x_1, x_2\} \rightarrow \textbf z = \{x_1^2, \sqrt{2}x_21 x_2, x_2^2\}$ and is represented in figure on the right.

<p align="center">

</p>

Consider the following mapping $\phi$ for an example $\textbf x = \{x_1, x_2, ..., x_M\}$.

$$ \phi : \textbf x \rightarrow \{x_1^2, x_2^2, ..., x_M^2, x_1 x_2,x_2 x_3, ..., x_1 x_M, ..., x_{M-1}x_M\} $$

This is an example of quadratic mapping and, as it is possible to see, after the application of the map the number of features increases considerably and their computation can be inefficient. The application of kernel methods help avoid these issues, we will obtain the same result without computing the features since they will be implicit in the metric used to evaluate the distances between points.

Many linear parametric model can be re-cast into  an equivalent **dual representation** in which the predictions are based in a **kernel function** evaluated at training points. For models which are based on a fixed nonlinear feature mapping $\phi(\textbf x)$, the kernel function is simply given by:

$$
\begin{align}
\mathcal k (\textbf x, \textbf x') = \phi(\textbf x) ^T \phi(\textbf x) 
\end{align}
$$

The kernel specifies the similarity between $\textbf x$ and $\textbf x'$ in the feature space. We can see from the definition above that the kernel is a symmetric function of its arguments. The simplest example of a kernel function is the identity function, given by the mapping $\phi(\textbf x) = \textbf x$ and we will refer to this kernel as the linear kernel.

The concept of kernel is formulated as an inner product in a feature space and allows to extend the well known algorithms by using the **kernel trick**. The basic idea of kernel trick is that, if we have an input vector that appears only in the form of scalar products then we can replace scalar products with some other choice of kernel. The kernel trick transforms a parametric model into a memory-based one with a change in computation for the result. In the kernel space the complexity is moved from the number of features to the number of points so, it is very useful when the number of features is intractable. Two important type of kernels are:

* <span style='color:SlateBlue;font-style:italic'>Stationary kernels </span>: they are a function of the difference between the arguments, so that $\mathcal k(\textbf x, \textbf x') = \mathcal k(\textbf x - \textbf x')$. They are invariant to translations in space.

* <span style='color:SlateBlue;font-style:italic'>Homogeneous kernels</span>: they depend only on the magnitude of the distance between the arguments so that $\mathcal k(\textbf x, \textbf x') = \mathcal k(||\textbf x - \textbf x'||) $. These kernels are also known as **radial basis functions**.

Note that the kernel function is a scalar, while the input vector is an $M-$dimensional entity.

## **Dual representations**

---



```python

```

a612d5fe9c380a311b2f4f95119c04021ef75e61
ipynb
Jupyter Notebook
lectures/05_Kernel_Methods.ipynb
stepyt/machine_learning_notes
f7263d96d64a304a7155e0b81b3d2b69df36df24
MIT
lectures/05_Kernel_Methods.ipynb
stepyt/machine_learning_notes
f7263d96d64a304a7155e0b81b3d2b69df36df24
MIT
lectures/05_Kernel_Methods.ipynb
stepyt/machine_learning_notes
f7263d96d64a304a7155e0b81b3d2b69df36df24
MIT
Qwen/Qwen-72B
1. YES
2. YES