## Exercise 1 (7 points): Kernel Functions

We already learned techniques to classify linearly separable data, e.g. with the help of an SVM. Unfortunately, not every dataset is linearly separable. There are cases where we need more complex decision surfaces. Ideally, we would still like to use the same algorithms as in the linear case. A common approach is to use so-called kernel functions which project the data
into another space so that the representations of the points in the new space become linearly separable. For example, we can project our data to a higher dimensional space.<br/>

In this exercise, we want to take a look at how this works in the case of SVMs. For this, we are going to work with a one-dimensional example consisting of four values $x_i \in \mathbb{R}$
\begin{equation} x_1 = −2, x_4 = 2 \in \omega_1 \hspace{0.5cm} and \hspace{0.5cm} x_2 = −1, x_3 = 0 \in \omega{−1} \end{equation}

assigned to either the set of positive samples $\omega_1 = {x_i | T_i = 1}$ or the set of negative samples $\omega{−1} = {x_i | T_i = −1}$. Further, we take the opportunity and analyse the decision function in a bit more detail.

1. [Python] Figure 1 shows a graphical representation of the dataset we are using here. Obviously, the data are not linearly separable. Find a projection function $\phi ∶ \mathbb{R} \rightarrow \mathbb{R}^2$, $\tilde{x} = \phi(x)$ which projects the data into the two-dimensional space so that the projected points $\tilde{x}$ become linearly separable. Apply $\phi(x)$ to all the values in the dataset, i.e. calculate $\tilde{x}_i = \phi(x_i)$ for 𝑖 = 1, 2, 3, 4

2. [Python] Once we have calculated all projections $\tilde{x}_i$, we can apply the same algorithm as in one of the previous exercises. Remember that we need the optimal Lagrange multipliers $\alpha_i^*$ and the threshold $w_0^*$ to classify new points. Train a linear SVM with the help of the svm object from the sklearn package and extract the relevant parameters, i.e. <br/><br/>
\begin{equation}\alpha_1^∗ = ?,\hspace{0.2cm} \alpha_2^∗ = ?,\hspace{0.2cm} \alpha_3^∗ = ?,\hspace{0.2cm} \alpha_4^∗ = ? \hspace{0.5cm} and \hspace{0.5cm} w_0^∗ = ? \end{equation} <br/>Note that you may have to take the absolute value of the extracted parameters.

3. [Python] Use the calculated parameters to classify the new point 𝑥5 = 1 based on the decision function
\begin{equation} f(\tilde{x}) = sig \left(\sum_{i=1}^4 \alpha_i^∗T_i ⟨\tilde{x}_i, \tilde{x}⟩ + w_0^∗\right)  \end{equation}
You can check your result by additionally using the predict method.

4. By now, we calculated the projection of each 𝑥 value and applied the same algorithm as usual. However, it turns out that projecting each data point is quite computational expensive when the number of points increases. Luckily, there is a so-called kernel trick which avoids the necessity of calculating any projections at all. The idea is to use a kernel function 𝑘(𝑥𝑖, 𝑥𝑗) which can be used as a replacement for the dot product of the projected data points <br/><br/>
\begin{equation}(\tilde{x}_i, \tilde{x}⟩ = k(x_i, x_j)\end{equation}<br/><br/>
Note that the kernel function uses the original data points $x$ and not the projections $\tilde{x}$.

    a) [Pen and Paper] Define the kernel $k(x_i, x_j)$ which calculates the dot product of your projection function $\phi(x)$.

    b) [Python] Compute the output of the value $x_5 = 1$ again but this time using only the one-dimensional values $x_i$. For this, you need to change Equation 1 so that it uses your kernel function.

5. [Python] We can apply the kernel trick not only to the decision function but also to the optimization problem itself. Remember that for this we need to optimize <br/><br>
\begin{equation}
L(w, w_0, \alpha_1, \alpha_2) = L(\alpha_1, \alpha_2) = \sum_{i=1}^2 \alpha_i - \frac{1}{2}\sum_{i=1}^2\sum_{j=1}^2\alpha_i\alpha_jT_iT_jx_i^Tx_j
\end{equation}<br/>
subject to the constraint
$$\sum_{i=1}^2\alpha_iT_i=0$$ <br/><br/>
Note how the dot product $\langle\tilde{x}_i, \tilde{x}_j\rangle$ appears here as well. Re-calculate the optimal parameters by using only the original values $x_i$. For this, write a custom kernel function according to the official interface which implements your previously defined kernel $k(x_i, x_j)$. When creating the svm object, you have the choice to set your own kernel. Check if the resulting parameters are indeed the same as before.

6. So far, we have only used the trained SVM to predict a label for a new data point based on the decision function of Equation 1. However, it is often useful to retrieve a prediction score as well, i.e. a value which tells us how good the prediction was. That is, we also want information about the uncertainty of the classifier. <br/><br/> In the case of SVMs, we can use the signed distance to the hyperplane as an indicator. As closer a point is located to this hyperplane, as more uncertain is the classification since then the point is also in nearer proximity to the other class. On the other hand, a point far away from the hyperplane has a very clear class assignment. Remember that we can calculate the distance of a point 𝒑 to a hyperplane 𝐻 via <br/><br/>\begin{equation}d(p, H) = \frac{\langle w, p \rangle + w_0}{ ‖w‖_2 }\end{equation} <br/><br/> using the weight vector 𝒘 and the bias $w_0$.

    a) [Pen and Paper] It turns out that we already dealt with distances before even though it was not obvious. Show that the decision function of Equation 1 without the sig(𝑥) function already calculates the unnormalized version of Equation 3, i.e. without dividing by $‖𝒘‖_2$
\begin{equation} d(\tilde{x}, H) ⋅ ‖𝒘‖_2 = \sum_{i=1}^4\alpha_i^*T_ik(x_i, x) + w_0^*\end{equation}
Hint: use the definition of 𝒘 from the script (p. 101). Note also that on the left side the projection ̃𝒙 and on the right side only the value 𝑥 is used. That is, we can calculate the (unnormalized) distance from the projected point to the hyperplane in
the projection space without actually entering this space. 

    b) [Pen and Paper] In case we want the correct distance to the hyperplane, we need to divide Equation 4 by the norm ‖𝒘‖2. However, this is not an easy task if we use a kernel function where we cannot directly compute the projections (cf. Exercise 2). Show that we can use the alternative expression<br/><br/>
\begin{equation}‖𝒘‖2 = \sqrt{\sum_{i=1}^4 \sum{j=1}^4T_iT_j\alpha_i^∗\alpha_j^∗k(x_i, x_j)}\end{equation} <br/><br/>
instead which does not use any variable from the projection space.

    c) [Python] Calculate the signed distance of the point $\phi(x_5)$ to the hyperplane of your trained SVM without using $\phi(x_5)$ directly. Instead, use only the value $x_5 = 1$ and your kernel $k(x_i, x_j)$.

## Exercise 2 (3 points): RBF Kernel [Pen and Paper]

Kernel functions are a very neat way to handle non-linearly separable problems. They can be used in all algorithms which need only the dot product of the data points so that the kernel function can be used instead (Equation 2). The power of the kernels is that they operate implicitly in a higher-dimensional projection space without actually entering it. This gives us the
opportunity to make our data linearly separable without negative consequences in terms of computational efficiency.

There are also some standard kernels often used and one particularly famous example is a radial basis function
\begin{equation}k(x_i, x_j) = e^{−\gamma‖x_i−x_j‖_2^2} \end{equation}
controlled by the parameter $\gamma \in \mathbb{R}^+$. This kernel is a bit special. First, it does not contain any dot product so it may be a bit surprising that we can use it to replace the calculation of a dot product. Secondly, it is even more unclear what the projection space for this kernel is, i.e. how the corresponding projection function $\phi(x)$ is defined. Thirdly, it introduces a new hyperparameter $\gamma$ which is worth further investigations.

This exercise tries to bring some light into this darkness. While we are trying to achieve this,
we also take the opportunity and briefly discuss non-separable problems where the margin is
calculated by minimizing
\begin{equation} \varphi(x, \delta) = \frac{‖𝒘‖_2^2}{2} + C \sum_{i=1}^N \delta_i \end{equation}
with the slack variables $𝛿_i ≥ 0$ and the new hyperparameter 𝐶 ∈ ℝ+.

1. It turns out that Equation 5 uses an infinitely dimensional projection space. This is a bit complicated to see so we consider only the one-dimensional case where we reduce our data points to be values 𝑥 ∈ ℝ. For this case, show that the projection function is defined as <br/><br/>
\begin{equation}\phi(x) = e^{−\gamma x^2} \left(1, \sqrt{\frac{2\gamma}{1!} 𝑥}, \sqrt{\frac{(2\gamma)^2}{2!} x_2}, \sqrt{\frac{(2\gamma)^3}{3!} x_3}, …\right) \end{equation} <br/><br/>
Hint: use the Taylor series of the exponential function
\begin{equation}e^x = 1 + 𝑥 + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + ... = \sum_{k=0}^\inf \frac{x^k}{k!} \end{equation}

2. We now want to turn our attention to the hyperparameters 𝛾 and 𝐶. For this, open this animation1 where you can adjust both parameters as well as the kernel type. It
shows a two-dimensional example of a non-linear separable dataset and plots the decision function of Equation 4 as a heat map.

    a) For the parameter 𝐶, fill out Table 1 by answering the following questions. 
        i. How does the width of the margin change (linear kernel)? [small/large]
        ii. How does the complexity of the decision surface change? [simple/complex]
        iii. How does the accuracy on the (training) data set change? [low/high]

    b) For the parameter 𝛾, fill out Table 2 by answering the following 
        i. How does the corresponding RBF function change? For this, map each function shown in Figure 2 to the corresponding parameter description. [A/B]
        ii. Each data point has a certain influence on the decision function. How strong is this influence? [small/high]

f8e07cf52102b77784ccd254ac276e563bb7e4b2
ipynb
Jupyter Notebook
08_svm_kernel_function/svm_kernel_function.ipynb
jhinga-la-la/pattern-recognition-course
7ad4f70b2c427f3c37f59f47768b90371873823c
Apache-2.0
08_svm_kernel_function/svm_kernel_function.ipynb
jhinga-la-la/pattern-recognition-course
7ad4f70b2c427f3c37f59f47768b90371873823c
Apache-2.0
08_svm_kernel_function/svm_kernel_function.ipynb
jhinga-la-la/pattern-recognition-course
7ad4f70b2c427f3c37f59f47768b90371873823c
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES