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 06:54:52 GMT
The singular values on my recommender vectors come out: 90, 10, 1.2,
1.1, 1.0, 0.95..... This was playing with your R code. Based on this,
I'm adding the QR stuff to my visualization toolkit.

Lance

On Sat, Jul 2, 2011 at 10:15 PM, Lance Norskog <goksron@gmail.com> wrote:
> 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
>



-- 
Lance Norskog
goksron@gmail.com

Mime
View raw message