I am trying to use Semi-Unsupervised clustering using reinforcement learning following this paper.

Assume I have n data-points each of which has d dimensions. I also have c pairwise constraints of whether two elements are supposed to be in the same cluster or not.

The paper states that "the original input dimension of the dataset is appended to a kernel space with a similarity metric to each pairwise point in the set of constraints" creating a d + 2c dimensional space. They also say the kernel they use is an RBF.

Can anybody explain to me what do they mean? how can you use the similarity of a pair of elements to generate a whole new dimension for every data point in the dataset? what is a "kernel space" exactly in this case? if I try to google it I only get results relevant to operating systems kernels.


1 Answer 1


Let's take a simple example, a binary classification using only 2 dimensions with only 8 observations. Consider the first 8 rows of the dataset. It is impossible to linearly separate the data using a hyper-plane.

So, we can use a kernel transform. The books usually drop you off right here(no help). It does not tell us how to transform. Transform using what? How many dimensions? What constraints?

We could consider the simplest transformation, f(x,y)=xy. We could take this transformation and now consider it a new dimension. So we started with (D2+Class) features and we could add 1 dim (to get D3+Class) if we chose.

Q. Does this help? I suggest either plotting this dataset out by hand. Using f(x,y)=xy is Not very helpful.

So let's try another, f'(x,y)=x^2 + y^2. We started with (D2+Class) features and added another dimension. We could conceivably plot D4+C, BUT using dimensions 1,2 & 4 are easier to visualize. I suggest plotting by hand (for effect) {d1,d2,d4} to your graphic or plot it using 3D software.

Now ask yourself, Is this new situation linearly separable?

As for the constraints, Do you remember LaGrange multipliers? Well if you want to use a gaussian like constraint we could use a Radial Basis Function (RBF). Where:

RBF: K(x,y) = exp(-gamma * (||x−y||)^2)), gamma > 0

The first part is kernel 101. The LaGrangian is kernel 400. lol


        d1  d2      C          d3         d4
| row | x | y | class |f1(x,y)=xy|f'(x,y)=x^2 + y^2|
| ---:|--:|--:| -----:|---------:|----------------:|
|   1 |  1|  0|      0|         0|                1|
|   2 |  0|  1|      0|         0|                1|
|   3 | -1|  0|      0|         0|                1|
|   4 |  0| -1|      0|         0|                1|
|   5 |  2|  0|      1|         0|                4|
|   6 |  0|  2|      1|         0|                4|
|   7 | -2|  0|      1|         0|                4|
|   8 |  0| -2|      1|         0|                4|
  • $\begingroup$ Thanks, it's a pretty good explanation to better understand why we need those extra dimensions.. there is still one thing that is not clear to me though: I get it using a kernel to combine existing dimensions to new ones (e.g. d3 = d1*d2), but in the paper, I'm following they seem to add a dimension for every constrain between two data points (so in 2 different rows), and i don't see how you could add this extra dimension, which supposedly should be based on their RBF distance, to every element in the dataset, including elements that are not part of the constrain... I'm just very confused $\endgroup$
    – raff7
    Commented May 7, 2020 at 10:56
  • $\begingroup$ Let me look at it... Also, If you like my response add an 'Up arrow' and 'check' the answer to give credit. ;) thanks $\endgroup$
    – mccurcio
    Commented May 7, 2020 at 16:06
  • $\begingroup$ ye I love your answer, I did try to give it an upvote but I only have 11 reputations and I need 15 for it to be shown Today I came with an idea: Is it possible that by "append a kernel space with a similarity metric to each pairwise point in the set of constraints" they just mean that I should add dimension to every point x, given the 2 elements of the pairwise constrain c1 and c2, where the two new dimensions are K(x,c1) and K(x,c2) respectively(with an RBF kernel)? you think it could work as in your example, and make the clustering hyperspace linearly separable? Again, thanks so much $\endgroup$
    – raff7
    Commented May 7, 2020 at 21:38
  • $\begingroup$ I only glanced at it, But yes, one appends the kernel space to the original data set. I beleive the C1, C2 constraints are the clusters they want indentify and separate. C1={0,1}, C2={0,1}, two groups of two sets. a major point of the article in my 'tiny' mind is that they are Regularization which penalizes the weights when the model is over-fitting. See Youtube/Statquest and faculty.marshall.usc.edu/gareth-james/ISL $\endgroup$
    – mccurcio
    Commented May 8, 2020 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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