mahout-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Lance Norskog <goks...@gmail.com>
Subject Re: Dimensional Reduction via Random Projection: investigations
Date Sun, 03 Jul 2011 05:15:12 GMT
All pairwise distances are preserved? There must be a qualifier on
pairwise distance algorithms.

On Sat, Jul 2, 2011 at 6:49 PM, Lance Norskog <goksron@gmail.com> wrote:
> Cool. The plots are fun. The way gaussian spots project into spinning
> chains is very educational about entropy.
>
> For full Random Projection, a lame random number generator
> (java.lang.Random) will generate a higher standard deviation than a
> high-quality one like MurmurHash.
>
> On Fri, Jul 1, 2011 at 5:25 PM, Ted Dunning <ted.dunning@gmail.com> wrote:
>> Here is R code that demonstrates what I mean by stunning (aka 15 significant
>> figures).  Note that I only check dot products here.  From the fact that the
>> final transform is orthonormal we know that all distances are preserved.
>>
>> # make a big random matrix with rank 20
>>> a = matrix(rnorm(20000), ncol=20) %*% matrix(rnorm(20000), nrow=20);
>>> dim(a)
>> [1] 1000 1000
>> # random projection
>>> y = a %*% matrix(rnorm(30000), ncol=30);
>> # get basis for y
>>> q = qr.Q(qr(y))
>>> dim(q)
>> [1] 1000   30
>> # re-project b, do svd on result
>>> b = t(q) %*% a
>>> v = svd(b)$v
>>> d = svd(b)$d
>> # note how singular values drop like a stone at index 21
>>> plot(d)
>>> dim(v)
>> [1] 1000   30
>> # finish svd just for fun
>>> u = q %*% svd(b)$u
>>> dim(u)
>> [1] 1000   30
>> # u is orthogonal, right?
>>> diag(t(u)%*% u)
>>  [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
>> # and u diag(d) v' reconstructs a very precisely, right?
>>> max(abs(a-u %*% diag(d) %*% t(v)))
>> [1] 1.293188e-12
>>
>> # now project a into the reduced dimensional space
>>> aa = a%*%v
>>> dim(aa)
>> [1] 1000   30
>> # check a few dot products
>>> sum(aa[1,] %*% aa[2,])
>> [1] 6835.152
>>> sum(a[1,] %*% a[2,])
>> [1] 6835.152
>>> sum(a[1,] %*% a[3,])
>> [1] 3337.248
>>> sum(aa[1,] %*% aa[3,])
>> [1] 3337.248
>>
>> # wow, that's close.  let's try a hundred dot products
>>> dot1 = rep(0,100);dot2 = rep(0,100)
>>> for (i in 1:100) {dot1[i] = sum(a[1,] * a[i,]); dot2[i] = sum(aa[1,]*
>> aa[i,])}
>>
>> # how close to the same are those?
>>> max(abs(dot1-dot2))
>> # VERY
>> [1] 3.45608e-11
>>
>>
>>
>> On Fri, Jul 1, 2011 at 4:54 PM, Ted Dunning <ted.dunning@gmail.com> wrote:
>>
>>> Yes.  Been there.  Done that.
>>>
>>> The correlation is stunningly good.
>>>
>>>
>>> On Fri, Jul 1, 2011 at 4:22 PM, Lance Norskog <goksron@gmail.com> wrote:
>>>
>>>> Thanks!
>>>>
>>>> Is this true? - "Preserving pairwise distances" means the relative
>>>> distances. So the ratios of new distance:old distance should be
>>>> similar. The standard deviation of the ratios gives a rough&ready
>>>> measure of the fidelity of the reduction. The standard deviation of
>>>> simple RP should be highest, then this RP + orthogonalization, then
>>>> MDS.
>>>>
>>>> On Fri, Jul 1, 2011 at 11:03 AM, Ted Dunning <ted.dunning@gmail.com>
>>>> wrote:
>>>> > Lance,
>>>> >
>>>> > You would get better results from the random projection if you did the
>>>> first
>>>> > part of the stochastic SVD.  Basically, you do the random projection:
>>>> >
>>>> >       Y = A \Omega
>>>> >
>>>> > where A is your original data, R is the random matrix and Y is the
>>>> result.
>>>> >  Y will be tall and skinny.
>>>> >
>>>> > Then, find an orthogonal basis Q of Y:
>>>> >
>>>> >       Q R = Y
>>>> >
>>>> > This orthogonal basis will be very close to the orthogonal basis of
A.
>>>>  In
>>>> > fact, there are strong probabilistic guarantees on how good Q is as
a
>>>> basis
>>>> > of A.  Next, you project A using the transpose of Q:
>>>> >
>>>> >       B = Q' A
>>>> >
>>>> > This gives you a short fat matrix that is the projection of A into a
>>>> lower
>>>> > dimensional space.  Since this is a left projection, it isn't quite
what
>>>> you
>>>> > want in your work, but it is the standard way to phrase things.  The
>>>> exact
>>>> > same thing can be done with left random projection:
>>>> >
>>>> >      Y = \Omega A
>>>> >      L Q = Y
>>>> >      B = A Q'
>>>> >
>>>> > In this form, B is tall and skinny as you would like and Q' is
>>>> essentially
>>>> > an orthogonal reformulation of of the random projection.  This
>>>> projection is
>>>> > about as close as you are likely to get to something that exactly
>>>> preserves
>>>> > distances.  As such, you should be able to use MDS on B to get exactly
>>>> the
>>>> > same results as you want.
>>>> >
>>>> > Additionally, if you start with the original form and do an SVD of B
>>>> (which
>>>> > is fast), you will get a very good approximation of the prominent right
>>>> > singular vectors of A.  IF you do that, the first few of these should
be
>>>> > about as good as MDS for visualization purposes.
>>>> >
>>>> > On Fri, Jul 1, 2011 at 2:44 AM, Lance Norskog <goksron@gmail.com>
>>>> wrote:
>>>> >
>>>> >> I did some testing and make a lot of pretty charts:
>>>> >>
>>>> >> http://ultrawhizbang.blogspot.com/
>>>> >>
>>>> >> If you want to get quick visualizations of your clusters, this is
a
>>>> >> great place to start.
>>>> >>
>>>> >> --
>>>> >> Lance Norskog
>>>> >> goksron@gmail.com
>>>> >>
>>>> >
>>>>
>>>>
>>>>
>>>> --
>>>> Lance Norskog
>>>> goksron@gmail.com
>>>>
>>>
>>>
>>
>
>
>
> --
> Lance Norskog
> goksron@gmail.com
>



-- 
Lance Norskog
goksron@gmail.com

Mime
View raw message