2
$\begingroup$

I'm looking for any good reference that can help me to understand the following exercises about kernels and online learning.

A training set $(x_1, y_1), ...,(x_m, y_m)$ is generic iff $\mathbf{x}_i = \mathbf{x}_j \Rightarrow y_i = y_j$. Consider the following kernel function $K_a(\mathbf{x}, \mathbf{t}) := \prod^n_{i=1}(1 +(x_it_i) + (1 - x_i)(1 - t_i))$.

1. Argue that $K_a: \mathbb{R}^n \times \mathbb{R}^n \rightarrow \mathbb{R}$ is a Kernel (I've already demonstrated that $K_a$ is a valid kernel)

2. Given a generic training set $(x_1, y_1), ...,(x_m, y_m) \in \{0,1\}^n \times\{0,1\}$ does there neccesarily exist a vector $\mathbf{\alpha} \in \mathbb{R}^m$ such that:

$$ \sum^m_{j=1}\left(\sum^m_{i=1}\alpha_iK_a(\mathbf{x}_i, \mathbf{x}_j) - y_j\right)^2 = 0 ? $$

Provide an argument to justify your answer.

3. Given a generic training set $(x_1, y_1), ...,(x_m, y_m) \in \mathbb{R}^n \times \mathbb{R}$ does there neccesarily exist a vector $\mathbf{\alpha} \in \mathbb{R}^m$ such that:

$$ \sum^m_{j=1}\left(\sum^m_{i=1}\alpha_iK_a(\mathbf{x}_i, \mathbf{x}_j) - y_j\right)^2 = 0 ? $$

Provide an argument to justify your answer.

Is it in some way related to the representer theorem and/or the Disjunctive Normal Form (DNF) ? Thanks for your advice.

NOTE: you can see where the question is formulated here

$\endgroup$
  • 4
    $\begingroup$ Please use a more informative title. $\endgroup$ – Franck Dernoncourt Oct 10 '17 at 1:06
0
$\begingroup$

For both a) and b) you agree that if I find a generic training set and prove that there does not exist an alpha such that the formula you wrote equals 0, then I proved that given a generic training set $(x_1,y_1), \dots,(x_m,y_m) \in \{0,1\}^n \times \{0,1\}$ there does not necessarily exist a vector $\alpha \in \mathbb R^m$ such that:

$$ \sum \limits_{j=1}^m \left( \sum \limits_{i=1}^m \alpha_i K_a(x_i, x_j) - y_j\right)^2 = 0 $$

?

You agree that if I prove that there does not necessarily exist such an alpha for a) then there does not necessarily exist such an alpha for b)? Just use the same training set provided for a) as for b).

So here is a generic training set: $((1,0,0),(0)) , ((1,1,0),(1)), ((1,1,1),(1))$ where the first 3 numbers are an x and the second number in the parentheses is its corresponding y. Now lets compute all $K(x_i, x_j)$ for all i,j : $K_a(x_1 , x_1)= (1 + 1 + 0)(1 + 0 + 1)(1 + 0 + 1) = 8$, $K_a(x_1 , x_2)= (1 + 1 + 0)(1 + 0 + 0)(1 + 0 + 1) = 4$, $K_a(x_1 , x_3)= (1 + 1 + 0)(1 + 0 + 0)(1 + 0 + 0) = 2$, $K_a(x_2 , x_2)= (1 + 1 + 0)(1 + 2 + 0)(1 + 0 + 1) = 8$, $K_a(x_2 , x_3)= (1 + 1 + 0)(1 + 1 + 0)(1 + 0 + 0) = 4$ , $K_a(x_3 , x_3)= (1 + 1 + 0)(1 + 1 + 0)(1 + 1 + 0) = 8$ . Is this correct?

Now for there to exist an $\alpha$ s.t. $\sum \limits_{j=1}^m \left( \sum \limits_{i=1}^m \alpha_i K_a(x_i, x_j) - y_j\right)^2 = 0$ since $\left( \sum \limits_{i=1}^m \alpha_i K_a(x_i, x_j) - y_j\right)^2$ is always greater than or equal to 0, we need it to be equal to zero for every single j. i.e. we need to show that :

$\forall j$ we have $ \left( \sum \limits_{i=1}^m \alpha_i K_a(x_i, x_j) - y_j\right) = 0 \implies \sum \limits_{i=1}^m \alpha_i K_a(x_i, x_j) = m * y_j$

So now consider the generic training set I provided. we need $\sum \limits_{i=1}^m \alpha_i K_a(x_i, x_1) = 0$ since $y_1$ is 0. Since the $K_a(x_i, x_1) > 0$ we need all of the alphas to be equal to zero. Ok so we set all of the alphas to zero.

But now consider $\sum \limits_{i=1}^m \alpha_i K_a(x_i, x_2) = 3$ (since $y_2$ is 1). We need now a different set of alphas for this equation to work. So we do not have an alpha which causes this equation to be zero.

If your question is a homework question and there are no mistakes in it, then it seems I am missing something, because then it would not make sense to ask a part b.

EDIT: Does this question relate to the represntor theorem? The representor theorem tells us that the optimal solution to Kernel SVM has the form $w = \sum \limits_{i=1}^m \alpha_i \psi (x_i) $ which if you then plug into the form of the prediction which is $\langle w, x \rangle $ you get that a prediction has the form $\sum \limits_{i=1}^m \alpha_i K_a(x_i, x)$ on some input x . So the question is asking you to figure out whether the optimal solution is necessarily perfect, i.e. 0 error. I would imagine that in some cases the answer is yes and in some cases the answer is no. This question does not make sense to me because it seems unnecessary to ask both a) and b) if a) is not true. It would make more sense if a) was true and b) wasn't. Right now as the question is asked, it doesn't seem to directly relate to linear separability or DNF. Perhaps if the question was a) also had the condition that y was the output of a DNF formula applied to x, then it would. Or if in b) it was asking to assume the training set is linearly seperable. Then perhaps the question would make sense and be more interesting, although i have not thought about it too much.

$\endgroup$
  • $\begingroup$ And for $\alpha_i = 0$? $\endgroup$ – Firebug Sep 16 '16 at 16:31
  • $\begingroup$ @user3494047 I think that where the x's in the training set are in $\{0,1\}^n$ the $K_a(\mathbf{x}_i, \mathbf{x}_j) = 2^n$. On the other hand, even if your answer seems reasonable, it is not true then $\alpha_i = 0, 1\leq i \leq m$ and I still believe that there's something missing with the generic property of the training set. $\endgroup$ – santteegt Sep 16 '16 at 17:50
  • $\begingroup$ I updated my answer. $\endgroup$ – user3494047 Sep 18 '16 at 14:19
  • $\begingroup$ @user3494047 Thanks for your answer. The question has no mistakes (there is just an additional sentence saying: provide an argument to justify your answer). Maybe is good to recall that the question concerns online learning. On the other hand, I don't know if I'm wrong but your generic training set is not showing the property $\mathbf{x}_i = \mathbf{x}_j \rightarrow y_i=y_j$. However, even if we add an additional example, it doesn't change anything. $\endgroup$ – santteegt Sep 18 '16 at 14:47
  • $\begingroup$ yes, you could add another example that is identical to one that is already there. The main point of the generic training set is that you can't have two identical x vectors with two different y's. $\endgroup$ – user3494047 Sep 18 '16 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.