1
$\begingroup$

In my application, I have a vectors of arbitrary length, but that normally fall in the range of between 0 and 500 elements. Each value in the vector is between -1 and 1. I am computing the similarity of two arbitrary vectors with the following SQL:

1 - SUM(ABS(v1.value - v2.value)) / COUNT(*)

(where v1.value and v2.value refer to values of the same matching item)

However, the dimensions are too large for these on-the-fly similarity calculations, so I would like to perform dimension reduction to improve performance.

I found out about random projection, and I am trying to apply it, but I'm not having much luck it seems, and was wondering if anyone could spot the flaw in my logic.

First, I expensively computed the similarity between X and Y (two vectors, each with 100 dimensions). This was so that I could know what value I should be shooting for after performing dimension reduction.

I first generated 8 vectors of the maximum possible length (100), all filled with random values between -1 and 1. Let's call them V1 to V8.

I then computed the similarity of X against V1, V2, V3, V4, V5, V6, V7, and V8, and saved that vector of respective results as X1. I also computed the similarity of Y against V1, V2, V3, V4, V5, V6, V7, and V8 and saved that vector of respective results as Y1.

I then computed the similarity of X1 against Y1 with the above SQL (the same method used to compute the similarity between X and Y), but got a much different result than when I computed the similarity of X against Y. This is unfortunate because I think random projection is quoted as being surprisingly accurate, so I was hoping the similarity between X and Y would be very close to the similarity between X1 and Y1.

To clarify, X and Y are the original vectors, and X1 and Y1 are the resultant "reduced dimension" vectors.

So my questions are:

1) Did I do this properly? I'm not sure if I fully understand random projection yet so maybe I messed up a step

2) How do you determine how many random vectors to compute against? Most of my vectors are going to have between 100 and 300 dimensions. How many dimensions should my reduced vectors have and still be reasonably accurate?

3) Is this possibly not working because I am using the Manhattan Distance instead of the Euclidean Distance? I initially chose the former because the computation is much simpler and I needed it to be fast.

$\endgroup$
1
$\begingroup$

I don't know a lot (indeed, hardly anything) about random projection, but I'm guessing that the projections are supposed to be orthogonal projections. That would require that your $V$ vectors be unit-length and mutually perpendicular (with respect to the inner product you're using).

A deeper problem is that you've got vectors in various-dimensional spaces, and you're putting them all into one large-dimensional space (by filling with zeroes?) and computing inner products --- that seems like a very peculiar choice. Before advising further on how to make random projection work, I'd like to know the nature of the data we're working with. For instance, it sounds as if your resulting dataset might have a real "preference" for certain axis-aligned subspaces (those consisting of vectors with lots of zeroes at the ends). It'd be useful to know whether that has any interactions with the assumptions of the theorems about random projection.

Finally, using the Manhattan metric might have serious consequences as well.

Short summary: read the theorems on random projections and look at their hypotheses closely to see whether they apply to your situation.

$\endgroup$
17
  • $\begingroup$ Hi thanks for the reply! So to answer some of your questions to help explain the situation better: the data that I'm working with is that users can rate something anywhere between -1.0 and 1.0 in my interface. The specific bounds aren't too important. If it would make it work then I could sacrifice that and make it work between 0 and 10 (integers instead). Although I would really like for there to remain a decent amount of .. is entropy the word? So like, I would prefer to preserve the ability to give a very nuanced rating (so at least be able to give >10 different options) $\endgroup$ – Ryan Peschel Oct 29 '19 at 13:26
  • $\begingroup$ As for the filling with zeroes comment, if I understand you properly: I am only computing similarity between matched values. So if user1 rated only items 1, 3, 4, and 7, and user2 only rated items 3, 7, and 9, then their X and Y vectors before computing similarity would consist only of items 3 and 7 (since they only share those). So if user1 rated item 3 as a -0.5 and item 7 as 1.0, and user2 rate item 3 as -0.25 and item 7 as 0.75, then vectors X and Y prior to computing similarity would be [ -0.5, 1.0 ] and [ -0.25, 0.75 ] respectively. Does that make sense? $\endgroup$ – Ryan Peschel Oct 29 '19 at 13:30
  • $\begingroup$ @RyanPeschel Linear algebraic data analysis methods would really prefer to have all data in the same space. Would it be highly detrimental to your analysis to replace null values with some "neutral" value like 0 on a scale from -1 to 1? $\endgroup$ – Ian Oct 29 '19 at 14:30
  • $\begingroup$ @Ian I'm not sure if that would work.. Like for example, if there were 300 items to rate, and two users only rated 2 of them, wouldn't all the 298 zeroes drag down the similarity score to almost nothing? $\endgroup$ – Ryan Peschel Oct 29 '19 at 14:33
  • $\begingroup$ @RyanPeschel That said the main thing that seems wrong in what you said in the OP is that you want to project X and Y into the span of V1 to V8, which cannot be done by projecting onto each separately and summing the projections unless the V's are orthogonal. Computing this projection properly in the Euclidean metric is a standard problem (a keyword you can look up is the normal equations). In the Manhattan metric it is a lot more complicated to compute the analogue of projections (i.e. the closest point in some subspace to a point not in the subspace). $\endgroup$ – Ian Oct 29 '19 at 14:34

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.