# Linear separability for a sum of kernel functions

Suppose we have 2 kernel functions $K_1(x,y)$ and $K_2(x,y)$. We know, that the dataset ($(x_1,y_1),\ldots,(x_l,y_l),$ $y_i \in \{-1,1\}$ ) is separated with the first one (that is, there are $w,$ $w_0$: $$y_i(K_1(w,x_i)-w_0)>0$$ for all $i=1,\ldots,l$ ), and not separated with the second kernel function. What we can say about kernel function $K_1(x,y)+K_2(x,y)$ ? How I can show that the same dataset is separated with it?

• possible duplicate of Machine Learning: Linear classifier and possibility to separate – onestop Apr 14 '12 at 22:00
• Max, your question was already migrated at the time you posted this one. You should better register your account here, and I will close the other one (that apparently is no longer yours). – chl Apr 15 '12 at 8:30
• Migrating @D.W. comment from the duplicate: Why do you believe the same dataset will be separated with $K_1(x,y)+K_2(x,y)$? Is this homework? – user88 Apr 15 '12 at 9:23
• I can't say that I believe, but I suspect it's true. Because I've tried some examples (but with linear kernel). Do you have any ideas? It's not a homework, I try to learn SVM by myself. – Max Apr 15 '12 at 10:23

I'll assume first that the kernels correspond to finite feature maps. Say that $K_1(x, y) = \varphi_1(x)^T \varphi_1(y)$, $K_2(x, y) = \varphi_2(x)^T \varphi_2(y)$. Then $$K_1(x, y) + K_2(x, y) = \begin{bmatrix}\varphi_1(x) \\ \varphi_2(x)\end{bmatrix}^T \begin{bmatrix}\varphi_1(y) \\ \varphi_2(y)\end{bmatrix}.$$ Thus, if a hyperplane defined by $(w_1, b_1)$ separates the dataset under the $\varphi_1$ map, the hyperplane defined by $\left(\begin{bmatrix}w_1 \\ 0\end{bmatrix}, b_1 \right)$ will separate the points in the same way under the combined mapping.
You can generalize this feature maps in any Hilbert space, since the space defined by $K_1 + K_2$ is the product of the spaces defined by $K_1$ and $K_2$ similar to vector concatenation in the finite case.