Kernel method

We break down the concept of kernel methods in a simple form.

Kernel Methods and the Kernel Trick

Input Space and Feature Space:

• Input Space (\( \mathcal{X} \)): This is the space where your original data points, \( x \) and \( y \), reside.

• Feature Space (\( \mathcal{F} \)): This is a higher-dimensional space where your data points are mapped using a feature mapping function, \( \phi \). So, \( \phi(x) \) and \( \phi(y) \) are the representations of \( x \) and \( y \) in the feature space.

Feature Mapping (\( \phi \)):

• The feature mapping function \( \phi: \mathcal{X} \rightarrow \mathcal{F} \) transforms data points from the input space to the feature space.

• In many cases, the feature space can be very high-dimensional, even infinite-dimensional, which makes computations directly in \( \mathcal{F} \) impractical.

Inner Product in Feature Space:

• When using machine learning algorithms, we often need to compute the inner product between two points in the feature space: \(\left\langle \phi(x) , \phi(y) \right\rangle \).

Kernel Function (\( k \)):

• The kernel function \( k \) is defined as \( k(x, y) = \phi(x)^{T} \phi(y) \).

• The key idea is that we do not need to compute \( \phi(x) \) and \( \phi(y) \) explicitly. Instead, we directly compute \( k(x, y) \) in the input space.

The Kernel Trick

The kernel trick allows us to work in the high-dimensional feature space implicitly without ever computing the coordinates of the data points in that space. Instead, we compute the inner products using the kernel function.

Why is this useful?

Efficiency:

• Computing \( \phi(x) \) and \( \phi(y) \) explicitly can be computationally expensive or infeasible.

• Using the kernel function \( k(x, y) \), we can perform the same calculations much more efficiently.

Flexibility:

• Kernel methods allow us to use different types of kernels, each corresponding to a different feature space. This flexibility helps in capturing various data structures and relationships.

Common Kernels

Linear Kernel:

• \( k(x, y) = x^{T} y \)

• This corresponds to no mapping (i.e., \( \phi(x) = x \)).

Polynomial Kernel:

• \( k(x, y) = (x^{T} y + c)^d \)

• This corresponds to a polynomial feature mapping.

Gaussian (RBF) Kernel:

• \( k(x, y) = \exp \left( -\frac{\|x - y\|^2}{2\sigma^2} \right) \)

• This corresponds to mapping into an infinite-dimensional feature space.

Sigmoid Kernel:

• \( k(x, y) = \tanh(\alpha x^{T} y + c) \)

• This corresponds to a feature mapping inspired by neural networks.

Finding \( \phi (x) \) From Kernel

Example 1: Polynomial kernel

We try decompose the polynomial kernel \( k(x, y) = (x^T y + c)^2 \) into its feature mapping representation \( \phi(x) \) such that \( k(x, y) = \left\langle \phi(x) , \phi(y) \right\rangle \).

Work Steps

Expand the Polynomial Kernel:

\[ k(x, y) = (x^T y + c)^2 \]

Using the binomial expansion, we get:

\[ (x^T y + c)^2 = (x^T y)^2 + 2c(x^T y) + c^2 \]

Identify the Terms: Let’s consider \( x = [x_1, x_2, \ldots, x_d]^T \) and \( y = [y_1, y_2, \ldots, y_d]^T \). The expanded terms can be further decomposed:

\[ (x^T y)^2 = \left( \sum_{i=1}^{d} x_i y_i \right)^2 = \sum_{i=1}^{d} \sum_{j=1}^{d} x_i y_i x_j y_j \]

\[ 2c(x^T y) = 2c \sum_{i=1}^{d} x_i y_i \]

Feature Mapping (\( \phi(x) \)): To express \( k(x, y) \) as \( \phi(x)^T \phi(y) \), we need to identify a feature mapping \( \phi(x) \) such that the inner product in the feature space gives us the polynomial kernel.

Let’s construct \( \phi(x) \) as follows:

\[ \phi(x) = \left( \sqrt{2}x_1x_1, \sqrt{2}x_1x_2, \ldots, \sqrt{2}x_1x_d, \sqrt{2}x_2x_1, \sqrt{2}x_2x_2, \ldots, \sqrt{2}x_d x_d, \sqrt{2c}x_1, \sqrt{2c}x_2, \ldots, \sqrt{2c}x_d, c \right)^T \]

Here, \( \phi(x) \) includes:

• All pairwise product terms \( \sqrt{2} x_i x_j \).

• Linear terms \( \sqrt{2c} x_i \).

• A constant term \( c \).

Verify \( \phi(x)^T \phi(y) \): Now, we compute the inner product \( \phi(x)^T \cdot \phi(y) \):

\[ \phi(x)^T \cdot \phi(y) = \left( \sqrt{2}x_1x_1, \sqrt{2}x_1x_2, \ldots, \sqrt{2}x_d x_d, \sqrt{2c}x_1, \sqrt{2c}x_2, \ldots, c \right)^T \cdot \left( \sqrt{2}y_1y_1, \sqrt{2}y_1y_2, \ldots, \sqrt{2}y_d y_d, \sqrt{2c}y_1, \sqrt{2c}y_2, \ldots, c \right) \]

This results in:

\[ \sum_{i=1}^{d} \sum_{j=1}^{d} \sqrt{2} x_i x_j \sqrt{2} y_i y_j + \sum_{i=1}^{d} \sqrt{2c} x_i \sqrt{2c} y_i + c^2 = 2 \sum_{i=1}^{d} \sum_{j=1}^{d} x_i x_j y_i y_j + 2c \sum_{i=1}^{d} x_i y_i + c^2 \]

Simplifying: $\( 2 (x^T y)^2 + 2c (x^T y) + c^2 = (x^T y + c)^2 \)$

Thus, we have:

\[ k(x, y) = (x^T y + c)^2 = \phi(x)^T \phi(y) \]

Example 2: RBF kernel

The Gaussian (RBF) kernel is:

\[ k(x, y) = \exp\left(-\frac{\|x - y\|^2}{2\sigma^2}\right) \]

First, let’s rewrite the squared Euclidean distance:

\[ \|x - y\|^2 = x^T x + y^T y - 2 x^T y \]

So the kernel can be written as:

\[ k(x, y) = \exp\left(-\frac{x^T x + y^T y - 2 x^T y}{2\sigma^2}\right) \]

This can be further split into:

\[ k(x, y) = \exp\left(-\frac{x^T x}{2\sigma^2}\right) \exp\left(-\frac{y^T y}{2\sigma^2}\right) \exp\left(\frac{x^T y}{\sigma^2}\right) \]

Homework 1

Decompose the term \( \exp\left(\frac{x^T y}{\sigma^2}\right) \) and find \( \phi(x) \)

Methods in \( \phi \) space

Distance in \( \phi(x) \) space

To compute \(\|\phi(x) - \phi(y)\|^2\) in the feature space and relate it to the Gaussian (RBF) kernel \(k(x, y)\), we need to follow these steps:

Define the Kernel Function: The Gaussian (RBF) kernel is given by:

\[ k(x, y) = \exp\left(-\frac{\|x - y\|^2}{2\sigma^2}\right) \]

Feature Mapping: The Gaussian kernel can be thought of as corresponding to an infinite-dimensional feature space. In this space, the kernel function \(k(x, y)\) can be expressed as the inner product of feature vectors \(\phi(x)\) and \(\phi(y)\):

\[ k(x, y) = \phi(x)^T \phi(y) \]

Compute \(\|\phi(x) - \phi(y)\|^2\): To find \(\|\phi(x) - \phi(y)\|^2\), we use the fact that: $\( \|\phi(x) - \phi(y)\|^2 = \|\phi(x)\|^2 + \|\phi(y)\|^2 - 2 \phi(x)^T \phi(y) \)$

We need to compute \(\|\phi(x)\|^2\) and \(\|\phi(y)\|^2\) in the feature space.

Norm Squared of \(\phi(x)\) and \(\phi(y)\): Let’s compute \(\|\phi(x)\|^2\):

\[ \|\phi(x)\|^2 = \phi(x)^T \phi(x) \]

Similarly,

\[ \|\phi(y)\|^2 = \phi(y)^T \phi(y) \]

For the Gaussian kernel:

\[ k(x, x) = \exp\left(-\frac{\|x - x\|^2}{2\sigma^2}\right) = \exp(0) = 1 \]

Therefore,

\[ \|\phi(x)\|^2 = \phi(x)^T \phi(x) = k(x, x) = 1 \]

Similarly,

\[ \|\phi(y)\|^2 = \phi(y)^T \phi(y) = k(y, y) = 1 \]

Compute \(\|\phi(x) - \phi(y)\|^2\): Now, using the computed norms and the kernel function:

\[ \|\phi(x) - \phi(y)\|^2 = \|\phi(x)\|^2 + \|\phi(y)\|^2 - 2 \phi(x)^T \phi(y) \]

Substituting the values:

\[ \|\phi(x) - \phi(y)\|^2 = 1 + 1 - 2 \phi(x)^T \phi(y) \]

\[ \|\phi(x) - \phi(y)\|^2 = 2 - 2 \phi(x)^T \phi(y) \]

Since \(\phi(x)^T \phi(y) = k(x, y)\):

\[ \|\phi(x) - \phi(y)\|^2 = 2 - 2 k(x, y) \]

Fuzzy C-Means clustering in \( \phi \) space

Kernel Fuzzy C-Means with Kernelization of the Metric The Kernel Fuzzy C-Means (KFCM) algorithm is an extension of the standard Fuzzy C-Means (FCM) algorithm that uses kernel methods to handle non-linearity by implicitly mapping data into a high-dimensional feature space.

Objective Function

\[ J_{KFCM} = \sum_{i=1}^{c} \sum_{k=1}^{n} (u_{ik})^m \|\psi(x_k) - \psi(g_i)\|^2 \]

where:

• \( u_{ik} \) is the membership degree of object \( x_k \) in cluster \( i \).

• \( \psi(x_k) \) and \( \psi(g_i) \) are the feature space representations of data point \( x_k \) and cluster center \( g_i \), respectively.

• \( m \) is the fuzziness parameter.

• \( \|\psi(x_k) - \psi(g_i)\|^2 \) represents the squared Euclidean distance between the feature space representations of \( x_k \) and \( g_i \).

Using the kernel trick, this distance can be expressed in terms of the kernel function:

\[ \|\psi(x_k) - \psi(g_i)\|^2 = K(x_k, x_k) + K(g_i, g_i) - 2K(x_k, g_i) \]

where \( K(\cdot, \cdot) \) is the kernel function. For the Gaussian kernel, this becomes:

\[ K(x_k, x_k) = 1 \text{ and } K(g_i, g_i) = 1 \]

Thus,

\[ \|\psi(x_k) - \psi(g_i)\|^2 = 2 - 2K(x_k, g_i) \]

Substitute this into the objective function:

\[ J_{KFCM} = \sum_{i=1}^{c} \sum_{k=1}^{n} (u_{ik})^m (2 - 2K(x_k, g_i)) \]

which simplifies to:

\[ J_{KFCM} = 2 \sum_{i=1}^{c} \sum_{k=1}^{n} (u_{ik})^m - 2 \sum_{i=1}^{c} \sum_{k=1}^{n} (u_{ik})^m K(x_k, g_i) \]

Gaussian Kernel

The Gaussian kernel is defined as:

\[ K(x_l, x_k) = \exp \left( -\frac{\|x_l - x_k\|^2}{2\sigma^2} \right) \]

where \( \sigma^2 \) is the width parameter of the Gaussian kernel. For the Gaussian kernel:

\[ \| \psi(x_k) - \psi(g_i) \|^2 = 2 - 2K(x_k, g_i) \]

Update Rules for Prototypes and Membership Degrees

Update Prototypes:

To minimize \( J_{KFCM} \) with respect to the cluster prototypes \( g_i \), we need to find the partial derivatives and set them to zero. The update rule for the prototypes \( g_i \) is derived as:

\[ g_i = \frac{\sum_{k=1}^{n} (u_{ik})^m K(x_k, g_i) x_k}{\sum_{k=1}^{n} (u_{ik})^m K(x_k, g_i)} \]

Update Membership Degrees:

To update the membership degrees \( u_{ik} \), we use the method of Lagrange multipliers with the constraints \( \sum_{i=1}^{c} u_{ik} = 1 \) and \( u_{ik} \geq 0 \). The update rule for the membership degrees \( u_{ik} \) is given by:

\[ u_{ik} = \frac{1}{\sum_{h=1}^{c} \left( \frac{1 - K(x_k, g_i)}{1 - K(x_k, g_h)} \right)^{\frac{2}{m-1}}} \]

where \( K(x_k, g_i) \) and \( K(x_k, g_h) \) are kernel evaluations between \( x_k \) and the cluster centers.

Algorithm Steps

. Initialize the membership matrix \( U \) and the prototypes \( g_i \) randomly.

. Repeat until convergence:

• Update the prototypes \( g_i \) using:

  \[ g_i = \frac{\sum_{k=1}^{n} (u_{ik})^m K(x_k, g_i) x_k}{\sum_{k=1}^{n} (u_{ik})^m K(x_k, g_i)} \]

• Update the membership degrees \( u_{ik} \) using:

  \[ u_{ik} = \frac{1}{\sum_{h=1}^{c} \left( \frac{1 - K(x_k, g_i)}{1 - K(x_k, g_h)} \right)^{\frac{2}{m-1}}} \]

Check for convergence

\[ \text{If } \left| J_{KFCM}^{(k)} - J_{KFCM}^{(k-1)} \right| \leq \text{threshold}, \text{ then stop} \]

Regression in \( \phi \) space

Objective Function in Feature Space

We start with the objective function of Ordinary Least Squares (OLS) regression in the feature space \(\phi(x)\):

\[ J(w) = \sum_{i=1}^{n} (y_i - f(x_i))^2 = \sum_{i=1}^{n} (y_i - w^T \phi(x_i))^2 \]

Expanding the squared term:

\[ J(w) = \sum_{i=1}^{n} (y_i - w^T \phi(x_i))(y_i - w^T \phi(x_i)) \]

\[ J(w) = \sum_{i=1}^{n} \left[ y_i^2 - 2y_i (w^T \phi(x_i)) + (w^T \phi(x_i))^2 \right] \]

Taking the Gradient

To find the optimal \(w\), we take the gradient of \(J(w)\) with respect to \(w\):

\[ \frac{\partial J(w)}{\partial w} = \sum_{i=1}^{n} \left[ -2 y_i \phi(x_i) + 2 (w^T \phi(x_i)) \phi(x_i) \right] \]

\[ \frac{\partial J(w)}{\partial w} = -2 \sum_{i=1}^{n} y_i \phi(x_i) + 2 \sum_{i=1}^{n} \phi(x_i) (\phi(x_i)^T w) \]

Setting the Gradient to Zero

To find the optimal \(w\), set the gradient to zero:

\[ -2 \sum_{i=1}^{n} y_i \phi(x_i) + 2 \sum_{i=1}^{n} \phi(x_i) (\phi(x_i)^T w) = 0 \]

\[ \sum_{i=1}^{n} y_i \phi(x_i) = \sum_{i=1}^{n} \phi(x_i) (\phi(x_i)^T w) \]

Representing \(w\) as a Linear Combination of \(\phi(x_i)\)

We assume \(w\) can be expressed as a linear combination of the feature vectors \(\phi(x_i)\):

\[ w = \sum_{i=1}^{n} \alpha_i \phi(x_i) \]

Substitute this into the equation:

\[ \sum_{i=1}^{n} y_i \phi(x_i) = \sum_{i=1}^{n} \phi(x_i) \left( \phi(x_i)^T \sum_{j=1}^{n} \alpha_j \phi(x_j) \right) \]

Using the Kernel Trick

Notice that \(\phi(x_i)^T \phi(x_j)\) is the kernel function \(k(x_i, x_j)\). Therefore,

\[ \sum_{i=1}^{n} y_i \phi(x_i) = \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_j \phi(x_i) k(x_i, x_j) \]

This simplifies to:

\[ \sum_{i=1}^{n} y_i \phi(x_i) = \sum_{i=1}^{n} \phi(x_i) \left( \sum_{j=1}^{n} \alpha_j k(x_i, x_j) \right) \]

Solving for \(\alpha\)

\( y \) is the column vector of labels \( [y_1, y_2, \ldots, y_n]^T \).

Similarly, let \( \alpha \) be the column vector of coefficients \( [\alpha_1, \alpha_2, \ldots, \alpha_n]^T \) After inner product into \(\phi(x_k)\), We reached the equation:

\[ \sum_{i=1}^{n} y_i k(x_k, x_i) = \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_j k(x_k, x_i) k(x_i, x_j) \]

We simplify this to:

\[ \sum_{i=1}^{n} y_i k(x_k, x_i) = \sum_{j=1}^{n} \alpha_j \sum_{i=1}^{n} k(x_k, x_i) k(x_i, x_j) \]

For all \( x_k \) where \( k = 1, \ldots, n \), we have \( n \) system equations. After solving them, we obtain \( \alpha \).”

Making Predictions

Using the obtained \(\alpha\), the regression function \(f(x)\) for a new input \(x\) is given by:

\[ f(x) = w^T \phi(x) = \left( \sum_{i=1}^{n} \alpha_i \phi(x_i) \right)^T \phi(x) \]

By the kernel trick, we have:

\[ f(x) = \sum_{i=1}^{n} \alpha_i k(x_i, x) \]

The weight vector norm

Formulation

You appear to be discussing the representation of a weight vector \( w \) in terms of kernel functions and dual coefficients. Here’s how these expressions are generally interpreted in kernel methods:

Weight Vector Representation

In kernel methods, the weight vector \( w \) in the feature space can be expressed as a linear combination of the transformed data points. If \( \phi(x_i) \) denotes the feature space transformation of \( x_i \), then:

\[ w = \sum_{i=1}^{n} \alpha_i \phi(x_i) \]

where \( \alpha_i \) are the coefficients in the dual space, and \( n \) is the number of training samples.

Inner Product in Feature Space

The inner product between two weight vectors \( w \) and \( w \) can be expressed as:

\[ w^T w = \left( \sum_{i=1}^{n} \alpha_i \phi(x_i) \right)^T \left( \sum_{j=1}^{n} \alpha_j \phi(x_j) \right) \]

Expanding this expression:

\[ w^T w = \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j \phi(x_i)^T \phi(x_j) \]

In kernel methods, the inner product \( \phi(x_i)^T \phi(x_j) \) in the feature space is replaced by the kernel function \( K(x_i, x_j) \):

\[ \phi(x_i)^T \phi(x_j) = K(x_i, x_j) \]

Thus, the weight vector’s inner product can be written as:

\[ w^T w = \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j K(x_i, x_j) \]

Kernel Matrix Representation

The kernel matrix \( K \) is defined as:

\[ K_{ij} = K(x_i, x_j) \]

Therefore, the inner product of weight vectors \( w \) and \( w \) can also be expressed as:

\[ w^T w = \alpha^T K \alpha \]

where \( \alpha \) is the vector of coefficients \( \alpha_i \), and \( K \) is the kernel matrix.

Normalizing

The normalization transformation you mentioned requires scaling the kernel function to ensure it is normalized with respect to the data points. This adjustment can be particularly useful in various machine learning algorithms that utilize kernel methods. Let’s analyze the normalization process and derive the normalized kernel function step by step.

Normalization Transformation

Given the transformation:

\[ \hat{\phi}(x) = \frac{\phi(x)}{\|\phi(x)\|} \]

where \( \phi(x) \) is the feature space representation of \( x \), and \( \|\phi(x)\| \) denotes the norm of \( \phi(x) \) in the feature space.

For two data points \( x \) and \( z \), the normalized kernel function \( \hat{\kappa}(x, z) \) is defined as:

\[ \hat{\kappa}(x, z) = \langle \hat{\phi}(x), \hat{\phi}(z) \rangle \]

Substitute \( \hat{\phi}(x) \) and \( \hat{\phi}(z) \) into the inner product:

\[ \hat{\kappa}(x, z) = \left\langle \frac{\phi(x)}{\|\phi(x)\|}, \frac{\phi(z)}{\|\phi(z)\|} \right\rangle \]

Calculating the Normalized Kernel Function

Compute the Inner Product:

\[ \hat{\kappa}(x, z) = \frac{\langle \phi(x), \phi(z) \rangle}{\|\phi(x)\| \|\phi(z)\|} \]

Here, \( \langle \phi(x), \phi(z) \rangle \) is the dot product in the feature space, which is equal to the kernel function \( \kappa(x, z) \):

\[ \langle \phi(x), \phi(z) \rangle = \kappa(x, z) \]

Compute Norms:

The norm of \( \phi(x) \) in the feature space is:

\[ \|\phi(x)\| = \sqrt{\langle \phi(x), \phi(x) \rangle} = \sqrt{\kappa(x, x)} \]

Similarly:

\[ \|\phi(z)\| = \sqrt{\langle \phi(z), \phi(z) \rangle} = \sqrt{\kappa(z, z)} \]

Substitute Norms:

Substitute these norms into the normalized kernel function:

\[ \hat{\kappa}(x, z) = \frac{\kappa(x, z)}{\sqrt{\kappa(x, x)} \sqrt{\kappa(z, z)}} \]

This can also be written as:

\[ \hat{\kappa}(x, z) = \frac{\kappa(x, z)}{\sqrt{\kappa(x, x) \kappa(z, z)}} \]

Norm and distance from the centre of mass

The concept you’re discussing involves calculating and interpreting the center of mass (or centroid) in the feature space induced by a kernel function, and its properties. Here’s a structured explanation and derivation of the key points:

Center of Mass in Feature Space

Given a set of data points \( \{ x_i \}_{i=1}^n \) mapped to the feature space \( \phi(x_i) \), the center of mass (or centroid) of the set \( \{\phi(x_i)\} \) is:

\[ \phi_S = \frac{1}{n} \sum_{i=1}^n \phi(x_i) \]

Norm of the Center of Mass

To compute the norm squared of \( \phi_S \), we use:

\[ \|\phi_S\|^2 = \langle \phi_S, \phi_S \rangle \]

Substitute \( \phi_S \) into this equation:

\[ \|\phi_S\|^2 = \left\langle \frac{1}{n} \sum_{i=1}^n \phi(x_i), \frac{1}{n} \sum_{j=1}^n \phi(x_j) \right\rangle \]

Expand the inner product:

\[ \|\phi_S\|^2 = \frac{1}{n^2} \sum_{i=1}^n \sum_{j=1}^n \langle \phi(x_i), \phi(x_j) \rangle \]

Using the kernel function \( \kappa(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle \), we get:

\[ \|\phi_S\|^2 = \frac{1}{n^2} \sum_{i=1}^n \sum_{j=1}^n \kappa(x_i, x_j) \]

The term \( \frac{1}{n^2} \sum_{i=1}^n \sum_{j=1}^n \kappa(x_i, x_j) \) is the average of all entries in the kernel matrix \( K \). Hence:

\[ \|\phi_S\|^2 = \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \kappa(x_i, x_j) \]

Distance from a Point to the Center of Mass

For a data point \( x \), the squared distance from \( \phi(x) \) to \( \phi_S \) is:

\[ \|\phi(x) - \phi_S\|^2 \]

Using the identity:

\[ \|\phi(x) - \phi_S\|^2 = \|\phi(x)\|^2 + \|\phi_S\|^2 - 2 \langle \phi(x), \phi_S \rangle \]

Substitute \( \|\phi(x)\|^2 = \kappa(x, x) \) and \( \langle \phi(x), \phi_S \rangle = \frac{1}{n} \sum_{i=1}^n \kappa(x, x_i) \):

\[ \|\phi(x) - \phi_S\|^2 = \kappa(x, x) + \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \kappa(x_i, x_j) - \frac{2}{n} \sum_{i=1}^n \kappa(x, x_i) \]

Expected Squared Distance from Center of Mass

For a set of points \( \{x_s\}_{s=1}^s \):

\[ \frac{1}{s} \sum_{s=1}^s \|\phi(x_s) - \phi_S\|^2 \]

Expanding:

\[ \frac{1}{s} \sum_{s=1}^s \|\phi(x_s) - \phi_S\|^2 = \frac{1}{s} \sum_{s=1}^s \left( \kappa(x_s, x_s) + \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \kappa(x_i, x_j) - \frac{2}{n} \sum_{i=1}^n \kappa(x_s, x_i) \right) \]

Rearrange:

\[ \frac{1}{s} \sum_{s=1}^s \|\phi(x_s) - \phi_S\|^2 = \frac{1}{s} \sum_{s=1}^s \kappa(x_s, x_s) - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \kappa(x_i, x_j) \]

Support Vector Regression

Given the initial objective function for regression with ε-insensitive loss:

\[ J(w) = \frac{1}{2n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2 + \lambda \sum_{j=1}^{d} w_j^2 \]

and substituting the square loss with the ε-insensitive loss, the objective function becomes:

\[ \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{n} \max(0, |e_i| - \epsilon) \]

where \( e_i = y_i - \hat{y}_i = y_i - (w^T x_i + b) \).

Introducing Slack Variables

We introduce slack variables \( \xi_i \) to represent the amount by which each error \( |e_i| \) exceeds \( \epsilon \):

\[ \xi_i = \max(0, |e_i| - \epsilon) \]

Thus, the objective function can be rewritten as:

\[ \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{n} \xi_i \]

Constraints

The slack variables \( \xi_i \) must satisfy the following constraints:

\[\begin{split} \begin{cases} y_i - (w^T x_i + b) \leq \epsilon + \xi_i \\ (w^T x_i + b) - y_i \leq \epsilon + \xi_i \\ \xi_i \geq 0 \end{cases} \end{split}\]

To handle this constraint without using the absolute value, we can split it into two separate constraints:

\[\begin{split} \begin{cases} y_i - (w^T x_i + b) \leq \epsilon + \xi_i \\ (w^T x_i + b) - y_i \leq \epsilon + \xi_i \end{cases} \end{split}\]

Additionally, we need to ensure that \( \xi_i \geq 0 \).

Primal Problem

Combining these constraints with the objective function, we get the primal problem:

\[ \min_{w, b, \xi} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{n} \xi_i \]

subject to:

\[\begin{split} \begin{cases} y_i - (w^T x_i + b) \leq \epsilon + \xi_i \\ (w^T x_i + b) - y_i \leq \epsilon + \xi_i \\ \xi_i \geq 0 \end{cases} \end{split}\]

Using Two Slack Variables

To handle positive and negative deviations separately, we introduce two slack variables \( \xi_i \) and \( \xi_i^* \). The formulation is as follows:

Objective Function

\[ \min_{w, b, \xi, \xi^*} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{n} (\xi_i + \xi_i^*) \]

Constraints

\[\begin{split} \begin{cases} y_i - (w^T x_i + b) \leq \epsilon + \xi_i \\ (w^T x_i + b) - y_i \leq \epsilon + \xi_i^* \\ \xi_i, \xi_i^* \geq 0 \end{cases} \end{split}\]

Final Formulation

Thus, the final formulation of the Support Vector Regression (SVR) with ε-insensitive loss using two slack variables is:

\[ \min_{w, b, \xi, \xi^*} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{n} (\xi_i + \xi_i^*) \]

subject to the constraints:

\[\begin{split} \begin{cases} y_i - (w^T x_i + b) \leq \epsilon + \xi_i \\ (w^T x_i + b) - y_i \leq \epsilon + \xi_i^* \\ \xi_i, \xi_i^* \geq 0 \end{cases} \end{split}\]

SVR in Feature Space with Kernel Trick

To implement SVR in the feature space using the kernel trick, we replace the inner product \( w^T x \) with a kernel function \( \kappa(x, x') \):

Primal Formulation

The primal formulation in the feature space \( \phi \) is:

\[ \min_{\mathbf{w}, b, \xi, \xi^*} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^{n} (\xi_i + \xi_i^*) \]

subject to:

\[\begin{split} \begin{cases} y_i - (\mathbf{w}^T \phi(x_i) + b) \leq \epsilon + \xi_i \\ (\mathbf{w}^T \phi(x_i) + b) - y_i \leq \epsilon + \xi_i^* \\ \xi_i, \xi_i^* \geq 0 \end{cases} \end{split}\]

Dual Formulation

The dual formulation of the above problem using Lagrange multipliers \( \alpha_i \) and \( \alpha_i^* \) is:

\[\begin{split} \begin{aligned} &\max_{\alpha, \alpha^*} \sum_{i=1}^{n} ( \alpha_i - \alpha_i^* ) y_i - \epsilon \sum_{i=1}^{n} ( \alpha_i + \alpha_i^* ) \\ &- \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} ( \alpha_i - \alpha_i^* )( \alpha_j - \alpha_j^* ) \kappa(x_i, x_j) \end{aligned} \end{split}\]

subject to:

\[\begin{split} \begin{cases} \sum_{i=1}^{n} ( \alpha_i - \alpha_i^* ) = 0 \\ 0 \leq \alpha_i, \alpha_i^* \leq C \end{cases} \end{split}\]

Here, \( \kappa(x_i, x_j) \) is the kernel function that computes the dot product in the high-dimensional feature space.

Final Prediction

The final prediction for a test point \( x \) is given by:

\[ \hat{y} = \sum_{i=1}^{n} ( \alpha_i - \alpha_i^* ) \kappa(x_i, x) + b \]

where \( \alpha_i \) and \( \alpha_i^* \) are the solutions to the dual problem and \( b \) is the bias term.

This SVR formulation in the feature space allows us to leverage the kernel trick to handle nonlinear regression tasks efficiently.

Step-by-Step Derivation of Support Vector Regression (SVR) in Kernel Space

Objective and Constraints in the Primal Form

The primal problem for SVR with \(\epsilon\)-insensitive loss can be formulated as:

Objective function:

\[ \min_{w, b, \xi, \xi^*} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{n} (\xi_i + \xi_i^*) \]

Subject to constraints:

\[\begin{split} \begin{cases} y_i - (w^T \phi(x_i) + b) \leq \epsilon + \xi_i \\ (w^T \phi(x_i) + b) - y_i \leq \epsilon + \xi_i^* \\ \xi_i, \xi_i^* \geq 0 \end{cases} \end{split}\]

where \(w\) is the weight vector in the feature space, \(b\) is the bias term, \(\xi_i\) and \(\xi_i^*\) are slack variables for positive and negative deviations, respectively, and \(C\) is a regularization parameter.

Lagrangian and Dual Problem

To solve the primal problem, we first construct the Lagrangian function. Introduce Lagrange multipliers \(\alpha_i, \alpha_i^*, \eta_i, \eta_i^* \geq 0\) for the constraints:

\[\begin{split} \begin{aligned} L(w, b, \xi, \xi^*, \alpha, \alpha^*, \eta, \eta^*) &= \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{n} (\xi_i + \xi_i^*) \\ &\quad - \sum_{i=1}^{n} \alpha_i [\epsilon + \xi_i - y_i + (w^T \phi(x_i) + b)] \\ &\quad - \sum_{i=1}^{n} \alpha_i^* [\epsilon + \xi_i^* + y_i - (w^T \phi(x_i) + b)] \\ &\quad - \sum_{i=1}^{n} \eta_i \xi_i - \sum_{i=1}^{n} \eta_i^* \xi_i^* \end{aligned} \end{split}\]

Stationarity Conditions

(stationary points are those points where the partial derivatives of Λ are zero)

To find the dual problem, we need to set the partial derivatives of the Lagrangian with respect to the primal variables to zero.

With respect to \(w\):

\[ \frac{\partial L}{\partial w} = w - \sum_{i=1}^{n} (\alpha_i - \alpha_i^*) \phi(x_i) = 0 \implies w = \sum_{i=1}^{n} (\alpha_i - \alpha_i^*) \phi(x_i) \]

With respect to \(b\):

\[ \frac{\partial L}{\partial b} = - \sum_{i=1}^{n} (\alpha_i - \alpha_i^*) = 0 \implies \sum_{i=1}^{n} (\alpha_i - \alpha_i^*) = 0 \]

With respect to \(\xi_i\):

\[ \frac{\partial L}{\partial \xi_i} = C - \alpha_i - \eta_i = 0 \implies \alpha_i = C - \eta_i \]

With respect to \(\xi_i^*\):

\[ \frac{\partial L}{\partial \xi_i^*} = C - \alpha_i^* - \eta_i^* = 0 \implies \alpha_i^* = C - \eta_i^* \]

Substituting Back

Substituting the stationarity conditions back into the Lagrangian, we get the dual problem:

\[\begin{split} \begin{aligned} L_D &= \frac{1}{2} \|w\|^2 - \sum_{i=1}^{n} \alpha_i [\epsilon + \xi_i - y_i + (w^T \phi(x_i) + b)] \\ &\quad - \sum_{i=1}^{n} \alpha_i^* [\epsilon + \xi_i^* + y_i - (w^T \phi(x_i) + b)] \end{aligned} \end{split}\]

Since \( w = \sum_{i=1}^{n} (\alpha_i - \alpha_i^*) \phi(x_i) \), substitute \( w \) into the Lagrangian:

\[ \frac{1}{2} \|\sum_{i=1}^{n} (\alpha_i - \alpha_i^*) \phi(x_i)\|^2 \]

This expands to:

\[ \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} (\alpha_i - \alpha_i^*) (\alpha_j - \alpha_j^*) \langle \phi(x_i), \phi(x_j) \rangle \]

Using the kernel trick \( \kappa(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle \):

\[ \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} (\alpha_i - \alpha_i^*) (\alpha_j - \alpha_j^*) \kappa(x_i, x_j) \]

Dual Problem

Combining all the terms, the dual problem becomes:

Maximize:

\[ W(\alpha, \alpha^*) = -\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} (\alpha_i - \alpha_i^*) (\alpha_j - \alpha_j^*) \kappa(x_i, x_j) - \epsilon \sum_{i=1}^{n} (\alpha_i + \alpha_i^*) + \sum_{i=1}^{n} y_i (\alpha_i - \alpha_i^*) \]

Subject to:

\[\begin{split} \begin{cases} \sum_{i=1}^{n} (\alpha_i - \alpha_i^*) = 0 \\ 0 \leq \alpha_i, \alpha_i^* \leq C \end{cases} \end{split}\]

Prediction

The prediction function for a new data point \( x \) is given by:

\[ \hat{y} = \sum_{i=1}^{n} (\alpha_i - \alpha_i^*) \kappa(x_i, x) + b \]

where \( b \) can be determined by exploiting the Karush-Kuhn-Tucker (KKT) conditions.

Determining \( b \)

To determine \( b \), we use the support vectors (data points with \( 0 < \alpha_i < C \) or \( 0 < \alpha_i^* < C \)):

\[ b = y_i - \sum_{j=1}^{n} (\alpha_j - \alpha_j^*) \kappa(x_j, x_i) - \epsilon \quad \text{if} \quad 0 < \alpha_i < C \]

or

\[ b = y_i - \sum_{j=1}^{n} (\alpha_j - \alpha_j^*) \kappa(x_j, x_i) + \epsilon \quad \text{if} \quad 0 < \alpha_i^* < C \]