In your example, let $X_i=(x_{i1}, x_{i1}), X_j=(x_{j1}, x_{j2})$, and the mapping function $\Phi: \mathbb{R}^2 \rightarrow \mathbb{R}^5$, is $\Phi(X)=(x_1, x_2, x_1^2, x_2^2, x_1 x_2)^T$.
SVM classify a data point $X$ by
$$
y=W^T \Phi(X)+b
$$
and the weight vector is
$$
W=\sum_{X_i \in S}\alpha_i y_i \Phi(X_i)
$$
where $S$ is the support vectors and $\alpha_i$ is the nonnegative real number, then
$$
y=\underbrace{\left(\sum_{X_i \in S} \alpha_i y_i \Phi(X_i)\right)^T}_{W^T} \Phi(X) + b\\
= \sum_{X_i \in S} \alpha_i y_i \underbrace{\Phi(X_i)^T\Phi(X)}_{\text{Kernel trick } K(X_i, X)} + b
$$
Why Kernel Trick can skip the projection from original input space to higher dimension?
The kernel function$K: \mathbb{R}^2 \times \mathbb{R}^2 \rightarrow \mathbb{R}$ can skip the mapping $\Phi: \mathbb{R}^2 \rightarrow \mathbb{R}^5$ is because what comes after the projection is the inner product between two high dimension vectors.
Let $\Phi(X_i)=(\underbrace{x_{i1}}_{x_{i1}}, \underbrace{x_{i2}}_{x_{i2}}, \underbrace{x_{i1}^2}_{x_{i3}}, \underbrace{x_{i2}^2}_{x_{i4}}, \underbrace{x_{i1} x_{i2}}_{x_{i5}})^T$, the underscore texts is the p-dimensional feature vector $(x_{i1},.., x_{ip})$ in your post. We projecting $X_i$ and $X_j$ into the feature space, followed by a dot product
$$
\Phi(X_i)^T\Phi(X_j) = x_{i1}x_{j1}+x_{i2}x_{j2}+x_{i1}^2 x_{j1}^2+x_{i2}^2 x_{j2}^2 + x_{i1} x_{i2} x_{j1} x_{j2}
$$
Kernel function, in its meaning, also performs the dot product between vectors in feature space, but in practice, we don't need to know the mapping $\Phi$ explicitly or even the precise feature vector (which can sometimes be infinite!)
$$
K(X_i, X_j) = x_{i1}x_{j1}+x_{i2}x_{j2}+x_{i1}^2 x_{j1}^2+x_{i2}^2 x_{j2}^2 + x_{i1} x_{i2} x_{j1} x_{j2}
$$
This is equivalent to $\Phi(X_i)^T\Phi(X_j)$.
It can be confusing because, in this example, the expression for $K(X_i, X_j)$ appears to be the same as $\Phi(X_i)^T \Phi(X_j)$, making it seem like we need to know the feature vectors and the mapping to construct the kernel. However, this is not always the case. For instance, the Gaussian kernel has an infinite feature dimension, yet the inner product in feature space can be expressed neatly using the kernel function.
How $W=\sum_{X_i \in S}\alpha_i y_i X_i$ ?
Short story long.. let's look back to the goal of the SVM: to maximize the margin.
$\text{margin=}=\frac{2}{||W||}$
and it is a constrained optimization problem:
$$
\max_{W,b} \frac{2}{W^T W}\\
\text{subject to } y_i(W^T X_i+b) \geq 1, i=1,2,…,N
$$
is equivalent to
$$
\min_{W, b} \frac{1}{2}W^T W\\
\text{ subject to } y_i(W^T X_i+b)\geq1, i=1,2,…,N
$$
where
- $\frac{1}{2}W^T W$ is a quadratic function
- $y_i(W^T X_i+b)\geq1$ is a linear inequality constraint
Therefore we can utilize Lagrange multiplier with KKT conditions
The primal Lagrangian is
$\mathfrak{L}_{\text{primal}}=\frac{1}{2}W^T W-\sum_{i=1}^N \alpha_i (y_i(W^T X_i+b)-1)$
and $\alpha_i \geq 0$ are the Lagrangian multipliers.
Due to KKT stationarity conditions we have the derivative of $\mathfrak{L}$ w.r.t $W$ and $b$= 0
$$
\frac{\partial \mathfrak{L}}{\partial W} = \frac{\partial}{\partial W} \frac{1}{2}W^T W - \frac{\partial}{\partial W} \sum_{i=1}^N \alpha_i (y_i(W^T X_i+b)-1)
$$
where the first term:
$$
\frac{\partial}{\partial W} \frac{1}{2}W^T W = W
$$
and the second term:
$$
-\frac{\partial}{\partial W} \sum_{i=1}^N \alpha_i (y_i(W^T X_i+b)-1)=-\sum_{i=1}^N\alpha_i y_i X_i\\
\implies \frac{\partial \mathfrak{L}}{\partial W}= W-\alpha_i y_i X_i= 0\\
\implies W=\sum_{i=1}^N\alpha_i y_i X_i
$$
for partial derivative on $b$
$$
\frac{\partial \mathfrak{L}}{\partial b} = \frac{\partial}{\partial b} \frac{1}{2}W^T W - \frac{\partial}{\partial b} \sum_{i=1}^N \alpha_i (y_i(W^T X_i+b)-1)\\
= 0 - \sum_{i=1}^N\alpha_i y_i = 0\\
\implies \sum_{i=1}^N\alpha_i y_i = 0
$$
Substitute back to the Lagrangian function $\mathfrak{L}_{\text{primal}}=\frac{1}{2}W^T W-\sum_{i=1}^N \alpha_i (y_i(W^T X_i+b)-1)$
First term:
$$
\frac{1}{2}W^T W = \frac{1}{2}\Bigl(\sum_{i=1}^N\alpha_i y_i X_i\Bigr)^T \Bigl(\sum_{j=1}^N\alpha_i y_i X_i\Bigr)\\
= \frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N\alpha_i\alpha_j y_i y_j X_i^T X_j
$$
Second term:
$$
-\sum_{i=1}^N \alpha_i (y_i(W^T X_i+b)-1)\\
= -\sum_{i=1}^N \alpha_i \Biggl(y_i\biggl(\bigl(\sum_{i=1}^N\alpha_i y_i X_i\bigr)^T X_i+b\biggr)-1\Biggr)\\
= - \sum_{i=1}^N \alpha_i
$$
We have the dual optimization problem:
$$
\mathfrak{L}_{\text{Dual}}=\sum_{i=1}^N \alpha_i -\frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N\alpha_i\alpha_j y_i y_j X_i^T X_j
$$
such that $\alpha_i\geq 0$, for all $i$ and $\sum_{i=1}^N\alpha_i y_i = 0$
How does the fitting/training looks like?
We can perform optimization with a Python package cvxopt.solvers.qp
But first we need a bit of transformation on that.. let a matrix $P$ with elements $P_{i,j}=y_i y_j X_i^T X_j$
$$
\max_\alpha \Bigl(\sum_{i=1}^N \alpha_i -\frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N\alpha_i\alpha_j P_{i,j}\Bigr)
$$
$$
\implies\max_\alpha \Bigl(-\frac{1}{2}\alpha^T P_{i,j} \alpha +\sum_{i=1}^N \alpha_i\Bigr)\\
\implies\min_\alpha \Bigl(\frac{1}{2}\mathbf{\alpha}^T P_{i,j} \mathbf{\alpha} -1^T \mathbf{\alpha} \Bigr)\\
\text{such that } -\alpha_i\leq 0 \text{ and } y^T \alpha=0
$$
Check the code example
How $W=\sum_{X_i \in S}\alpha_i y_i \Phi(X_i)$ ?
All the above also applies to the kernel trick, because of the Representer Theorem:
Assume that $\Phi$ is a mapping from $X$ to a Hilbert space. Then, there exists a vector $\alpha \in \mathbb{R}^m$such that $W=\sum_{i=1}^{m}\alpha_i y_i \Phi(X_i)$ is an optimal solution of Equation.
Intuition
In linear SVM, the weight vector $W$ can be viewed as the linear combination of the support vectors $S$:
$W=\sum_{X_i \in S} \alpha_i y_i X_i$
In non-linear SVM, the weight vector $W$ can be viewed as the linear combination of the support vectors in feature space:
$W=\sum_{X_i \in S}\alpha_i y_i \Phi(X_i)$
Look back to a constrained optimization problem
$$
\text{max or min } f(x)\\
\text{subject to } g(x)
$$
the condition at the optimal point is that the gradient of $ f(x_{\text{opt}})$ must at the same direction with the gradient of $g(x_{\text{opt}})$, scaled by a factor $\alpha_i$.
$$
\nabla f(x_i)=\alpha_i \nabla g(x_i)
$$
In the case of a SVM, the support vectors are those that have a positive, non-zero Lagrange multiplier $\alpha$ — are the optimal points. These support vectors are the only data points that impose constraints on the optimization problem, they decide the final decision boundary.
