You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@mahout.apache.org by Sean Owen <sr...@gmail.com> on 2010/06/03 12:52:50 UTC
Understanding the SVD recommender
I'm finally looking to make my crude understanding of SVD-based
recommenders more like "vague". I understand the SVD and the principle
here but haven't implemented it.
I'm looking at what I believe is the original paper on it by Sarwar et
al: www.grouplens.org/papers/pdf/sarwar_SVD.pdf
It's good stuff and I understood it once, but now that I dig into
details since I want to implement, I can't figure out how to read the
algorithm in a way that works out. I think there are some notation
problems, mostly in the incremental stage.
Is anyone out there familiar enough with this to a) discuss this paper
with me or b) point me to another writeup on the approach?
Re: Understanding the SVD recommender
Posted by Jake Mannix <ja...@gmail.com>.
On Thu, Jun 10, 2010 at 12:11 AM, Jake Mannix <ja...@gmail.com> wrote:
>
> The second term is just the row-average of row-i times v.zSum(), and the
> last term is a constant for all values in the output vector, and is just (A
> . v).zSum().
> So no additional map-reduces are needed to incorporate this - it's just
> that the Lanczos solver will need to be told about the row and column
> averages of the
>
input and optionally at each Lanczos iteration, modify the resultant vector
> as above.
>
I should caution here: the simple form of my modification only would work in
exactly that way if the input matrix is symmetric. When it's not symmetric,
the inner loop of Lanczos isn't A . v, but A.timesSquared(v) = (A' . A).v,
and so if you shift A, you will need to be slightly more clever about how
you peel out the matrix of mean values. It can certainly be done sparsely
still (at worst, compute (A - B).v, then (A - B)'.v !), but I'm not sure if
you can do it in the k mapreduce steps that you can do it in the uncentered
form (it might take the 2k that the previous parenthetical remark implies).
-jake
Re: Understanding the SVD recommender
Posted by Jake Mannix <ja...@gmail.com>.
On Wed, Jun 9, 2010 at 12:08 PM, Richard Simon Just <
info@richardsimonjust.co.uk> wrote:
>
> Agreed. Just wanted to answer the question that had been left hanging for
> why Sarwar add the row average back. In fact to be complete, before the SVD
> they fill each null value with 'column average - row average'. But yeah,
> that would make for a much bigger computation.
>
I should note here, that if you really want to see the difference between
the fully centered SVD and the one where you only shift the nonzero entries,
the former is not *necessarily* a dense and therefore-out-of-reach
computation:
The meat of the Lanczos algorithm is repeatedly computing A . v, where A is
your big big matrix, and v is a (dense) vector which is getting closer and
closer to the biggest singular. If you wanted to compute the singular
vectors of (A - B), where B_ij = r_i - c_j = (sum_{k=1..N} A_ik) -
(sum_{k=1..M} A_kj) is the matrix of row averages minus column averages,
then you can just do it in a couple of (still sparse) steps:
[(A - B) . v]_i = [A . v]_i - [B . v]_i
= [A . v]_i - (sum_{k=1..N,j=1..M}A_ij v_k) +
(sum_{k=1...M,j=1...M}A_kj v_j)
= [A . v]_i - r_i * (sum_{k} v_k) + (sum_{k} (A .
v)_k)
The second term is just the row-average of row-i times v.zSum(), and the
last term is a constant for all values in the output vector, and is just (A
. v).zSum().
So no additional map-reduces are needed to incorporate this - it's just that
the Lanczos solver will need to be told about the row and column averages of
the input and optionally at each Lanczos iteration, modify the resultant
vector as above.
See if it makes a difference!
-jake
Re: Understanding the SVD recommender
Posted by Richard Simon Just <in...@richardsimonjust.co.uk>.
On 09/06/10 19:28, Jake Mannix wrote:
> On Wed, Jun 9, 2010 at 11:19 AM, Richard Simon Just<
> info@richardsimonjust.co.uk> wrote:
>
>
>> I don't know enough yet to comment on what works best, but I can give some
>> evidence that they do subtract teh row average ahead of time. Sarwar's
>> previous work, Application of Dimensionality Reduction piece (
>> http://www.grouplens.org/papers/pdf/webKDD00.pdf) uses the same prediction
>> function. In section 4.3.1 Prediction Experiment they discuss the removal of
>> the row average before the SVD computation and it's later addition for the
>> prediction. I'd make the assumption that the incremental SVD paper builds on
>> this.
>>
>> - Richard
>>
>>
> I would be *very* careful on how you decompose a sparse matrix which you
> center: if you naively just subtract off the mean from all the entries in
> the vectors, an SVD which would have taken 6 hours to compute could suddenly
> take weeks, literally. But if you do the second-from-most-naive thing, and
> subtract the means from only the nonzero entries, then all can turn out for
> the best. This is just following Sean's typical advice of "don't treat
> unknown preferences as '0.0' ".
>
> -jake
>
>
Agreed. Just wanted to answer the question that had been left hanging
for why Sarwar add the row average back. In fact to be complete, before
the SVD they fill each null value with 'column average - row average'.
But yeah, that would make for a much bigger computation.
-Richard
Re: Understanding the SVD recommender
Posted by Jake Mannix <ja...@gmail.com>.
On Wed, Jun 9, 2010 at 11:19 AM, Richard Simon Just <
info@richardsimonjust.co.uk> wrote:
>
> I don't know enough yet to comment on what works best, but I can give some
> evidence that they do subtract teh row average ahead of time. Sarwar's
> previous work, Application of Dimensionality Reduction piece (
> http://www.grouplens.org/papers/pdf/webKDD00.pdf) uses the same prediction
> function. In section 4.3.1 Prediction Experiment they discuss the removal of
> the row average before the SVD computation and it's later addition for the
> prediction. I'd make the assumption that the incremental SVD paper builds on
> this.
>
> - Richard
>
I would be *very* careful on how you decompose a sparse matrix which you
center: if you naively just subtract off the mean from all the entries in
the vectors, an SVD which would have taken 6 hours to compute could suddenly
take weeks, literally. But if you do the second-from-most-naive thing, and
subtract the means from only the nonzero entries, then all can turn out for
the best. This is just following Sean's typical advice of "don't treat
unknown preferences as '0.0' ".
-jake
Re: Understanding the SVD recommender
Posted by Richard Simon Just <in...@richardsimonjust.co.uk>.
On 04/06/10 08:53, Ted Dunning wrote:
> On Fri, Jun 4, 2010 at 12:38 AM, Sean Owen<sr...@gmail.com> wrote:
>
>
>> They also add on the "row" average to make a prediction, which is the
>> average rating by the user, I'm guessing -- "row" is a row of A?
>>
>
> I would guess so, but that would only make sense if they subtracted it ahead
> of time. In general, I don't see the point for that. I would rather cosine
> normalize each user row.
>
>
>
I don't know enough yet to comment on what works best, but I can give
some evidence that they do subtract teh row average ahead of time.
Sarwar's previous work, Application of Dimensionality Reduction piece
(http://www.grouplens.org/papers/pdf/webKDD00.pdf) uses the same
prediction function. In section 4.3.1 Prediction Experiment they discuss
the removal of the row average before the SVD computation and it's later
addition for the prediction. I'd make the assumption that the
incremental SVD paper builds on this.
- Richard
Re: Understanding the SVD recommender
Posted by Ted Dunning <te...@gmail.com>.
On Fri, Jun 4, 2010 at 1:34 AM, Sean Owen <sr...@gmail.com> wrote:
> > I would guess so, but that would only make sense if they subtracted it
> ahead
> > of time. In general, I don't see the point for that. I would rather
> cosine
> > normalize each user row.
>
> Yeah sounds good. I wouldn't add this step to start
My quick guess is that normalizing decreases the condition number of the
matrix which makes the numerics more stable so you get a better estimate of
the singular vectors that you really care about because they aren't shadowed
so excessively by the ones associated with the largest singular vectors.
The condition number is, among other ways, defined by the ratio of the
largest to smallest eigenvalues. Looking at the outer product form of SVD,
you can easily see how if the first few singular values total dominate the
others that finding the residue represented by the others would be
difficult. IDF weighting should have similar effects.
Re: Understanding the SVD recommender
Posted by Sean Owen <sr...@gmail.com>.
On Fri, Jun 4, 2010 at 8:53 AM, Ted Dunning <te...@gmail.com>
wrote:on of the vectors, but isn't strictly necessary.
>
> Note that since this is an SVD, S is diagonal and all elements are real (and
> positive, actually). Thus B* = B.
(Yeah either way it's just dotting stuff with that "diagonal vector",
or really the square roots of its values.)
> But not customary. The old LSI article makes a better case than I can off
> the cuff just before bed.
OK sounds like it's best to maintain U sqrt(S) and sqrt(S) V if only
for convention.
> Actually the elements of S aren't item or user specific. Remember there are
> only k non-zeros there.
Yeah I meant they're like multipliers for each "feature" (probably not
the right word), establishing some relation between pseudo-users's
preferences for features and pseudo item's expression of features.
> I would guess so, but that would only make sense if they subtracted it ahead
> of time. In general, I don't see the point for that. I would rather cosine
> normalize each user row.
Yeah sounds good. I wouldn't add this step to start.
Re: Understanding the SVD recommender
Posted by Ted Dunning <te...@gmail.com>.
On Fri, Jun 4, 2010 at 12:38 AM, Sean Owen <sr...@gmail.com> wrote:
> Yes thanks a lot. Makes sense to me: we're just changing basis and V
> is the change-of-basis transformation. Glad to see that is all there
> is to it; not sure what the rest is about.
>
Exactly.
> I had thought of U S as "user preferences for features" and V as
> "expression of features in items". The paper breaks S in half by
> taking the square root S = B* B and putting B* with U and B with V.
>
This is pretty common usage actually. It allows some degree of
normalization of the vectors, but isn't strictly necessary.
Note that since this is an SVD, S is diagonal and all elements are real (and
positive, actually). Thus B* = B.
>
> But am I right that both are equivalent?
Ish.
But not customary. The old LSI article makes a better case than I can off
the cuff just before bed.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.7546&rep=rep1&type=pdf
> Because I'd rather think of
> maintaining and updating U S. Because conceptually S is just full of
> multipliers -- making users 3x more keen on feature 1 is the same as
> reducing the item express 3x less of feature 1. Certainly in the
> recommendation computation they show, which makes sense, it doesn't
> matter since the dot product is the same.
>
Actually the elements of S aren't item or user specific. Remember there are
only k non-zeros there.
They represent the strength of each of the singular vectors. A very useful
way to look at it is to consider the SVD as a sum of rank-1 outer products
u_i * v'_i. These rank-1 products are summed with weights s_i. This way of
looking at matters makes a number of lemmas about SVD's pretty trivial.
> They also add on the "row" average to make a prediction, which is the
> average rating by the user, I'm guessing -- "row" is a row of A?
I would guess so, but that would only make sense if they subtracted it ahead
of time. In general, I don't see the point for that. I would rather cosine
normalize each user row.
> Just working backwards, I'd assume this is because the generated
> predictions are otherwise "centered" in the sense that 0 will be
> predicted for an item that the user might be neutral on. But I guess I
> hadn't seen the intuitive reason this is the result. Is there any easy
> way to see it?
>
For a new user with no history, h = 0 so the corresponding k-dimensional
representation of this user will be s^-(1/2) h v = 0. The dot product with
any item vector will be identically 0.
I don't know that it would make any useful difference, but it would make me
happier to reduce the ratings to binary, normalize rows and then decompose.
In general, I think that the Belkor team had a much better approach with
SVD++ and their time dynamics trick. That is much the same as mean removal.
>
>
> On Fri, Jun 4, 2010 at 6:48 AM, Ted Dunning <te...@gmail.com> wrote:
> > You are correct. The paper has an appalling treatment of the folding in
> > approach.
> >
> > In fact, the procedure is dead simple.
> >
> > The basic idea is to leave the coordinate system derived in the original
> SVD
> > intact and simply project the new users into that space.
> >
> > The easiest way to see what is happening is to start again with the
> original
> > rating matrix A as decomposed:
> >
> > A = U S V'
> >
> > where A is users x items. If we multiply on the right by V, we get
> >
> > A V = U S V' V = U S
> >
> > (because V' V = I, by definition). This result is (users x items) x
> (items
> > x k) = users x k, that is, it gives a k dimensional vector for each user.
> > Similarly, multiplication on the left by U' gives a k x items matrix
> which,
> > when transposed gives a k dimensional vector for each item.
> >
> > This implies that if we augment U with new user row vectors U_new, we
> should
> > be able to simply compute new k-dimensional vectors for the new users and
> > adjoin these new vectors to the previous vectors. Concisely put,
> >
> > ( A ) ( A V )
> > ( ) V = ( )
> > ( A_new ) ( A_new V )
> >
> > This isn't really magical. It just says that we can compute new user
> > vectors at any time by multiplying the new users' ratings by V.
> >
> > The diagram in figure one is hideously confusing because it looks like a
> > picture of some kind of multiplication whereas it is really depicting
> some
> > odd kind of flow diagram.
> >
> > Does this solve the problem?
> >
> > On Thu, Jun 3, 2010 at 9:26 AM, Sean Owen <sr...@gmail.com> wrote:
>
Re: Understanding the SVD recommender
Posted by Sean Owen <sr...@gmail.com>.
Yes thanks a lot. Makes sense to me: we're just changing basis and V
is the change-of-basis transformation. Glad to see that is all there
is to it; not sure what the rest is about.
I had thought of U S as "user preferences for features" and V as
"expression of features in items". The paper breaks S in half by
taking the square root S = B* B and putting B* with U and B with V.
But am I right that both are equivalent? Because I'd rather think of
maintaining and updating U S. Because conceptually S is just full of
multipliers -- making users 3x more keen on feature 1 is the same as
reducing the item express 3x less of feature 1. Certainly in the
recommendation computation they show, which makes sense, it doesn't
matter since the dot product is the same.
They also add on the "row" average to make a prediction, which is the
average rating by the user, I'm guessing -- "row" is a row of A? it's
not specified. It doesn't affect the ordering of recommendations for a
user. Just working backwards, I'd assume this is because the generated
predictions are otherwise "centered" in the sense that 0 will be
predicted for an item that the user might be neutral on. But I guess I
hadn't seen the intuitive reason this is the result. Is there any easy
way to see it?
On Fri, Jun 4, 2010 at 6:48 AM, Ted Dunning <te...@gmail.com> wrote:
> You are correct. The paper has an appalling treatment of the folding in
> approach.
>
> In fact, the procedure is dead simple.
>
> The basic idea is to leave the coordinate system derived in the original SVD
> intact and simply project the new users into that space.
>
> The easiest way to see what is happening is to start again with the original
> rating matrix A as decomposed:
>
> A = U S V'
>
> where A is users x items. If we multiply on the right by V, we get
>
> A V = U S V' V = U S
>
> (because V' V = I, by definition). This result is (users x items) x (items
> x k) = users x k, that is, it gives a k dimensional vector for each user.
> Similarly, multiplication on the left by U' gives a k x items matrix which,
> when transposed gives a k dimensional vector for each item.
>
> This implies that if we augment U with new user row vectors U_new, we should
> be able to simply compute new k-dimensional vectors for the new users and
> adjoin these new vectors to the previous vectors. Concisely put,
>
> ( A ) ( A V )
> ( ) V = ( )
> ( A_new ) ( A_new V )
>
> This isn't really magical. It just says that we can compute new user
> vectors at any time by multiplying the new users' ratings by V.
>
> The diagram in figure one is hideously confusing because it looks like a
> picture of some kind of multiplication whereas it is really depicting some
> odd kind of flow diagram.
>
> Does this solve the problem?
>
> On Thu, Jun 3, 2010 at 9:26 AM, Sean Owen <sr...@gmail.com> wrote:
Re: Understanding the SVD recommender
Posted by Jake Mannix <ja...@gmail.com>.
This reminds me: I never moved over the "folding-in" code from decomposer.
Not that it's particularly complex, but it would probably be useful in
"utils" at
least.
-jake
On Thu, Jun 3, 2010 at 10:48 PM, Ted Dunning <te...@gmail.com> wrote:
> You are correct. The paper has an appalling treatment of the folding in
> approach.
>
> In fact, the procedure is dead simple.
>
> The basic idea is to leave the coordinate system derived in the original
> SVD
> intact and simply project the new users into that space.
>
> The easiest way to see what is happening is to start again with the
> original
> rating matrix A as decomposed:
>
> A = U S V'
>
> where A is users x items. If we multiply on the right by V, we get
>
> A V = U S V' V = U S
>
> (because V' V = I, by definition). This result is (users x items) x (items
> x k) = users x k, that is, it gives a k dimensional vector for each user.
> Similarly, multiplication on the left by U' gives a k x items matrix
> which,
> when transposed gives a k dimensional vector for each item.
>
> This implies that if we augment U with new user row vectors U_new, we
> should
> be able to simply compute new k-dimensional vectors for the new users and
> adjoin these new vectors to the previous vectors. Concisely put,
>
> ( A ) ( A V )
> ( ) V = ( )
> ( A_new ) ( A_new V )
>
> This isn't really magical. It just says that we can compute new user
> vectors at any time by multiplying the new users' ratings by V.
>
> The diagram in figure one is hideously confusing because it looks like a
> picture of some kind of multiplication whereas it is really depicting some
> odd kind of flow diagram.
>
> Does this solve the problem?
>
> On Thu, Jun 3, 2010 at 9:26 AM, Sean Owen <sr...@gmail.com> wrote:
>
> > Section 3 is hard to understand.
> >
> > - Ak and P are defined, but not used later
> > - Definition of P has UTk x Nu as a computation. UTk is a k x m
> > matrix, and Nu is "t" x 1. t is not defined.
> > - This only makes sense if t = m. But m is the number of users, and Nu
> > is a user vector, so should have a number of elements equal to n, the
> > number of items
> > - Sk * VTk is described as a k x "d" matrix but d is undefined
> > - The diagram suggests that VTk are multiplied by all the Nu, which
> > makes more sense -- but only if Nu are multiplied by VTk, not the
> > other way. And the diagram depicts neither of those.
> > - Conceptually I would understand Nu x VTk, but then P is defined by
> > an additional product with Uk
> >
> > In short... what?
> >
> >
> > On Thu, Jun 3, 2010 at 4:15 PM, Ted Dunning <te...@gmail.com>
> wrote:
> > > Fire away.
> > >
> > > On Thu, Jun 3, 2010 at 3:52 AM, Sean Owen <sr...@gmail.com> wrote:
> > >
> > >> Is anyone out there familiar enough with this to a) discuss this paper
> > >> with me or b) point me to another writeup on the approach?
> > >>
> > >
> >
>
Re: Understanding the SVD recommender
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
Also:
my personal understanding that use of straightforward SVD in
recommenders produces oversmoothed (or overregularized) results.
Intuition behind this is as follows: consider Netflix example (users x movies).
if I am a user, i probbably rated 40 or so movies out of say 100,000
that Netflix has.
The typical strategy to populate input rating matrix (in order to keep
it sparse, among other things), is to compute and average of my rating
and subtract it from all rated positions (leaving unrated positions at
0).
Now, say for the sake of this discussion, my average rating is 3. But
some how I am heavily leaning to chick flicks. So out of all 40, i saw
about 10 that i rated with the highest rating. So any reasonable
inference should figure that if i rated 10 out of 10 chick flicks at
their highest rating, then i am probably into that stuff.
But the computation wouldn't see it the same way. Netflix may be
having 10,000 chick flicks movies, and for computation it basically
would look like i rated 10 movies at 5 and the rest of 10,000 of them
as 3 (my average). So, 10 '5's out of 10,000 '3' s would still rate my
interest in chick flicks pretty low (nearly back to what happens to be
my average). In other words, regularization of the training is waaay
up.
So oversmoothing over sparse data is a problem here. Other algorithms
deal with that by either not taking unrated examples into account at
all (SGD-based factorization methods) or providing some sort of
weighting to the regularization amplification based on the number of
rated samples (i think that's ALS WR's way of coping with this).
Am i making any sense? or i am fundamentally wrong in my understanding
of the flow of basic SVD recommendation?
Re: Understanding the SVD recommender
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
i meant, reduce to a task that uses mathematical SVD
On Mon, Nov 28, 2011 at 5:04 PM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> Picking this old thread a little bit...
>
> I was wondering: is there a way to reduce task of ALS with regularization
> (or even ALS-WR) to a mathematical definition of reduced rank SVD?
>
> If somehow i could work in a regularization under the SSVD hood, that
> would solve most of iterative ills i think... But since i haven't seen math
> around for it, i assume it is not very practical or even possible?
>
> Thanks.
> -d
>
>
> On Thu, Nov 17, 2011 at 12:38 PM, Sebastian Schelter <ss...@apache.org>wrote:
>
>> I think Dmitriys description of the SGD and ALS-WR approach hits the
>> nail on the head.
>>
>> However there is a third way to factorize the rating matrix which we
>> haven't talked about yet. It's described in Yehuda Koren's
>> "Collaborative Filtering for Implicit Feedback Datasets"
>> http://research.yahoo.com/pub/2433 and I recently added it to
>> ParallelALSFactorizationJob.
>>
>> This approach works on implicit feedback data (like the number of
>> times a user watched a television series) and all unobserved
>> interactions are by definition 0. Using a standard SVD would result in
>> the problems Dmitriy described.
>>
>> But the paper introduces a very interesting approach: the user-item
>> matrix holds 0s and 1s only (0 in a cell if there have been no
>> interactions, 1 if there have been 1 or more interactions). This
>> matrix is decomposed into two other matrices X and Y (user and item
>> features) by minimizing the (regularized) squared error over all
>> observations (which is the same as in ALS-WR). However the error is
>> weighted by a confidence value that is very low if the user never
>> interacted with the item (because he simply might not be aware that
>> this item exists) and very high if the user interacted very often with
>> the item (a good indication of preference). That should help to avoid
>> the problems that Dmitriy described.
>>
>> --sebastian
>>
>>
>> 2011/11/17 Dmitriy Lyubimov <dl...@gmail.com>:
>> > On Thu, Nov 17, 2011 at 11:30 AM, Dmitriy Lyubimov <dl...@gmail.com>
>> wrote:
>> >> I will finish adding an option with Cholesky decomposition route to
>> >> SSVD some time early in Q1 2012.
>> >>
>> >
>> > PPS i already put some jobs in (they are in the trunk) for Cholesky
>> > route. I thought it would be an easy mod but then i saw that it would
>> > require a little bit more modifications to also support power
>> > iterations the same way they are supported today (and also i still
>> > kind of couldn't quite finish my thought process on what it would take
>> > to modify U-job to produce U without Q in his case, it seems this
>> > route will require a 100% special handling and i wouldn't be able to
>> > reuse any of current U job for this option.
>> >
>> > For these reasons, i decided to wait until i figure all of the
>> > remaining issues architecturally before i proceed. And that would
>> > better be a one longer chunk of time rather than several little
>> > chunks, which makes it dependent more on my schedule to figure where
>> > that chunk might be.
>> >
>>
>
>
Re: Understanding the SVD recommender
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
Picking this old thread a little bit...
I was wondering: is there a way to reduce task of ALS with regularization
(or even ALS-WR) to a mathematical definition of reduced rank SVD?
If somehow i could work in a regularization under the SSVD hood, that would
solve most of iterative ills i think... But since i haven't seen math
around for it, i assume it is not very practical or even possible?
Thanks.
-d
On Thu, Nov 17, 2011 at 12:38 PM, Sebastian Schelter <ss...@apache.org> wrote:
> I think Dmitriys description of the SGD and ALS-WR approach hits the
> nail on the head.
>
> However there is a third way to factorize the rating matrix which we
> haven't talked about yet. It's described in Yehuda Koren's
> "Collaborative Filtering for Implicit Feedback Datasets"
> http://research.yahoo.com/pub/2433 and I recently added it to
> ParallelALSFactorizationJob.
>
> This approach works on implicit feedback data (like the number of
> times a user watched a television series) and all unobserved
> interactions are by definition 0. Using a standard SVD would result in
> the problems Dmitriy described.
>
> But the paper introduces a very interesting approach: the user-item
> matrix holds 0s and 1s only (0 in a cell if there have been no
> interactions, 1 if there have been 1 or more interactions). This
> matrix is decomposed into two other matrices X and Y (user and item
> features) by minimizing the (regularized) squared error over all
> observations (which is the same as in ALS-WR). However the error is
> weighted by a confidence value that is very low if the user never
> interacted with the item (because he simply might not be aware that
> this item exists) and very high if the user interacted very often with
> the item (a good indication of preference). That should help to avoid
> the problems that Dmitriy described.
>
> --sebastian
>
>
> 2011/11/17 Dmitriy Lyubimov <dl...@gmail.com>:
> > On Thu, Nov 17, 2011 at 11:30 AM, Dmitriy Lyubimov <dl...@gmail.com>
> wrote:
> >> I will finish adding an option with Cholesky decomposition route to
> >> SSVD some time early in Q1 2012.
> >>
> >
> > PPS i already put some jobs in (they are in the trunk) for Cholesky
> > route. I thought it would be an easy mod but then i saw that it would
> > require a little bit more modifications to also support power
> > iterations the same way they are supported today (and also i still
> > kind of couldn't quite finish my thought process on what it would take
> > to modify U-job to produce U without Q in his case, it seems this
> > route will require a 100% special handling and i wouldn't be able to
> > reuse any of current U job for this option.
> >
> > For these reasons, i decided to wait until i figure all of the
> > remaining issues architecturally before i proceed. And that would
> > better be a one longer chunk of time rather than several little
> > chunks, which makes it dependent more on my schedule to figure where
> > that chunk might be.
> >
>
Re: Understanding the SVD recommender
Posted by Ted Dunning <te...@gmail.com>.
Adding weights is actually not at all incompatible with the original idea of singular vale decomposition. It may make some algorithms trickier but weighting is a very reasonable companion to any approximation algorithm.
Sent from my iPhone
On Nov 17, 2011, at 12:57, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> Yes. This is even one more step away from straightforward SVD, i.e.
> explicitly analyizing implicit feedback (pun intended).
>
> On Thu, Nov 17, 2011 at 12:38 PM, Sebastian Schelter <ss...@apache.org> wrote:
>> I think Dmitriys description of the SGD and ALS-WR approach hits the
>> nail on the head.
>>
>> However there is a third way to factorize the rating matrix which we
>> haven't talked about yet. It's described in Yehuda Koren's
>> "Collaborative Filtering for Implicit Feedback Datasets"
>> http://research.yahoo.com/pub/2433 and I recently added it to
>> ParallelALSFactorizationJob.
>>
>> This approach works on implicit feedback data (like the number of
>> times a user watched a television series) and all unobserved
>> interactions are by definition 0. Using a standard SVD would result in
>> the problems Dmitriy described.
>>
>> But the paper introduces a very interesting approach: the user-item
>> matrix holds 0s and 1s only (0 in a cell if there have been no
>> interactions, 1 if there have been 1 or more interactions). This
>> matrix is decomposed into two other matrices X and Y (user and item
>> features) by minimizing the (regularized) squared error over all
>> observations (which is the same as in ALS-WR). However the error is
>> weighted by a confidence value that is very low if the user never
>> interacted with the item (because he simply might not be aware that
>> this item exists) and very high if the user interacted very often with
>> the item (a good indication of preference). That should help to avoid
>> the problems that Dmitriy described.
>>
>> --sebastian
>>
>>
>> 2011/11/17 Dmitriy Lyubimov <dl...@gmail.com>:
>>> On Thu, Nov 17, 2011 at 11:30 AM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>>>> I will finish adding an option with Cholesky decomposition route to
>>>> SSVD some time early in Q1 2012.
>>>>
>>>
>>> PPS i already put some jobs in (they are in the trunk) for Cholesky
>>> route. I thought it would be an easy mod but then i saw that it would
>>> require a little bit more modifications to also support power
>>> iterations the same way they are supported today (and also i still
>>> kind of couldn't quite finish my thought process on what it would take
>>> to modify U-job to produce U without Q in his case, it seems this
>>> route will require a 100% special handling and i wouldn't be able to
>>> reuse any of current U job for this option.
>>>
>>> For these reasons, i decided to wait until i figure all of the
>>> remaining issues architecturally before i proceed. And that would
>>> better be a one longer chunk of time rather than several little
>>> chunks, which makes it dependent more on my schedule to figure where
>>> that chunk might be.
>>>
>>
Re: Understanding the SVD recommender
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
Yes. This is even one more step away from straightforward SVD, i.e.
explicitly analyizing implicit feedback (pun intended).
On Thu, Nov 17, 2011 at 12:38 PM, Sebastian Schelter <ss...@apache.org> wrote:
> I think Dmitriys description of the SGD and ALS-WR approach hits the
> nail on the head.
>
> However there is a third way to factorize the rating matrix which we
> haven't talked about yet. It's described in Yehuda Koren's
> "Collaborative Filtering for Implicit Feedback Datasets"
> http://research.yahoo.com/pub/2433 and I recently added it to
> ParallelALSFactorizationJob.
>
> This approach works on implicit feedback data (like the number of
> times a user watched a television series) and all unobserved
> interactions are by definition 0. Using a standard SVD would result in
> the problems Dmitriy described.
>
> But the paper introduces a very interesting approach: the user-item
> matrix holds 0s and 1s only (0 in a cell if there have been no
> interactions, 1 if there have been 1 or more interactions). This
> matrix is decomposed into two other matrices X and Y (user and item
> features) by minimizing the (regularized) squared error over all
> observations (which is the same as in ALS-WR). However the error is
> weighted by a confidence value that is very low if the user never
> interacted with the item (because he simply might not be aware that
> this item exists) and very high if the user interacted very often with
> the item (a good indication of preference). That should help to avoid
> the problems that Dmitriy described.
>
> --sebastian
>
>
> 2011/11/17 Dmitriy Lyubimov <dl...@gmail.com>:
>> On Thu, Nov 17, 2011 at 11:30 AM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>>> I will finish adding an option with Cholesky decomposition route to
>>> SSVD some time early in Q1 2012.
>>>
>>
>> PPS i already put some jobs in (they are in the trunk) for Cholesky
>> route. I thought it would be an easy mod but then i saw that it would
>> require a little bit more modifications to also support power
>> iterations the same way they are supported today (and also i still
>> kind of couldn't quite finish my thought process on what it would take
>> to modify U-job to produce U without Q in his case, it seems this
>> route will require a 100% special handling and i wouldn't be able to
>> reuse any of current U job for this option.
>>
>> For these reasons, i decided to wait until i figure all of the
>> remaining issues architecturally before i proceed. And that would
>> better be a one longer chunk of time rather than several little
>> chunks, which makes it dependent more on my schedule to figure where
>> that chunk might be.
>>
>
Re: Understanding the SVD recommender
Posted by Sebastian Schelter <ss...@apache.org>.
One small correction: ALS-WR is also only looking at rated examples.
2011/11/17 Sebastian Schelter <ss...@apache.org>:
> I think Dmitriys description of the SGD and ALS-WR approach hits the
> nail on the head.
>
> However there is a third way to factorize the rating matrix which we
> haven't talked about yet. It's described in Yehuda Koren's
> "Collaborative Filtering for Implicit Feedback Datasets"
> http://research.yahoo.com/pub/2433 and I recently added it to
> ParallelALSFactorizationJob.
>
> This approach works on implicit feedback data (like the number of
> times a user watched a television series) and all unobserved
> interactions are by definition 0. Using a standard SVD would result in
> the problems Dmitriy described.
>
> But the paper introduces a very interesting approach: the user-item
> matrix holds 0s and 1s only (0 in a cell if there have been no
> interactions, 1 if there have been 1 or more interactions). This
> matrix is decomposed into two other matrices X and Y (user and item
> features) by minimizing the (regularized) squared error over all
> observations (which is the same as in ALS-WR). However the error is
> weighted by a confidence value that is very low if the user never
> interacted with the item (because he simply might not be aware that
> this item exists) and very high if the user interacted very often with
> the item (a good indication of preference). That should help to avoid
> the problems that Dmitriy described.
>
> --sebastian
>
>
> 2011/11/17 Dmitriy Lyubimov <dl...@gmail.com>:
>> On Thu, Nov 17, 2011 at 11:30 AM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>>> I will finish adding an option with Cholesky decomposition route to
>>> SSVD some time early in Q1 2012.
>>>
>>
>> PPS i already put some jobs in (they are in the trunk) for Cholesky
>> route. I thought it would be an easy mod but then i saw that it would
>> require a little bit more modifications to also support power
>> iterations the same way they are supported today (and also i still
>> kind of couldn't quite finish my thought process on what it would take
>> to modify U-job to produce U without Q in his case, it seems this
>> route will require a 100% special handling and i wouldn't be able to
>> reuse any of current U job for this option.
>>
>> For these reasons, i decided to wait until i figure all of the
>> remaining issues architecturally before i proceed. And that would
>> better be a one longer chunk of time rather than several little
>> chunks, which makes it dependent more on my schedule to figure where
>> that chunk might be.
>>
>
Re: Understanding the SVD recommender
Posted by Sebastian Schelter <ss...@apache.org>.
I think Dmitriys description of the SGD and ALS-WR approach hits the
nail on the head.
However there is a third way to factorize the rating matrix which we
haven't talked about yet. It's described in Yehuda Koren's
"Collaborative Filtering for Implicit Feedback Datasets"
http://research.yahoo.com/pub/2433 and I recently added it to
ParallelALSFactorizationJob.
This approach works on implicit feedback data (like the number of
times a user watched a television series) and all unobserved
interactions are by definition 0. Using a standard SVD would result in
the problems Dmitriy described.
But the paper introduces a very interesting approach: the user-item
matrix holds 0s and 1s only (0 in a cell if there have been no
interactions, 1 if there have been 1 or more interactions). This
matrix is decomposed into two other matrices X and Y (user and item
features) by minimizing the (regularized) squared error over all
observations (which is the same as in ALS-WR). However the error is
weighted by a confidence value that is very low if the user never
interacted with the item (because he simply might not be aware that
this item exists) and very high if the user interacted very often with
the item (a good indication of preference). That should help to avoid
the problems that Dmitriy described.
--sebastian
2011/11/17 Dmitriy Lyubimov <dl...@gmail.com>:
> On Thu, Nov 17, 2011 at 11:30 AM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
>> I will finish adding an option with Cholesky decomposition route to
>> SSVD some time early in Q1 2012.
>>
>
> PPS i already put some jobs in (they are in the trunk) for Cholesky
> route. I thought it would be an easy mod but then i saw that it would
> require a little bit more modifications to also support power
> iterations the same way they are supported today (and also i still
> kind of couldn't quite finish my thought process on what it would take
> to modify U-job to produce U without Q in his case, it seems this
> route will require a 100% special handling and i wouldn't be able to
> reuse any of current U job for this option.
>
> For these reasons, i decided to wait until i figure all of the
> remaining issues architecturally before i proceed. And that would
> better be a one longer chunk of time rather than several little
> chunks, which makes it dependent more on my schedule to figure where
> that chunk might be.
>
Re: Understanding the SVD recommender
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
On Thu, Nov 17, 2011 at 11:30 AM, Dmitriy Lyubimov <dl...@gmail.com> wrote:
> I will finish adding an option with Cholesky decomposition route to
> SSVD some time early in Q1 2012.
>
PPS i already put some jobs in (they are in the trunk) for Cholesky
route. I thought it would be an easy mod but then i saw that it would
require a little bit more modifications to also support power
iterations the same way they are supported today (and also i still
kind of couldn't quite finish my thought process on what it would take
to modify U-job to produce U without Q in his case, it seems this
route will require a 100% special handling and i wouldn't be able to
reuse any of current U job for this option.
For these reasons, i decided to wait until i figure all of the
remaining issues architecturally before i proceed. And that would
better be a one longer chunk of time rather than several little
chunks, which makes it dependent more on my schedule to figure where
that chunk might be.
Re: Understanding the SVD recommender
Posted by Ted Dunning <te...@gmail.com>.
Agree.
On Thu, Nov 17, 2011 at 11:30 AM, Dmitriy Lyubimov <dl...@gmail.com>wrote:
> However,
> it would seem to me that QR as a completely isolated job would have
> little value in machine learning applications.
>
Re: Understanding the SVD recommender
Posted by Dmitriy Lyubimov <dl...@gmail.com>.
I will finish adding an option with Cholesky decomposition route to
SSVD some time early in Q1 2012.
RE: distributed QR: right now this option is architecturally "melted"
with SSVD because MR steps that do distributed QR doing extra job (i
would have to use more MR jobs if i did not, to do the same). Although
QR related math is modelled into nice and standalone set of "pipeline
preprocessors" (in other word, MR collector decorators) which could
be wired up in a standalone MR QR solver, such wiring at the moment
does not exist (although it is not difficult to wire one up). However,
it would seem to me that QR as a completely isolated job would have
little value in machine learning applications.
Thanks.
-d
On Sun, Nov 6, 2011 at 3:26 PM, Ted Dunning <te...@gmail.com> wrote:
> The tridiagonal is much smaller than you would need if you wanted all the
> eigenvalues. Since you only want a small number, you only have a
> tri-diagonal matrix that is some multiple of that size. In-memory
> decomposition makes total sense.
>
> Regarding QR decomposition, Dmitriy has already built a parallel version.
> A large QR is required at one point in the SSVD algorithm. I have shown a
> way to avoid this large QR using a much smaller Cholesky decomposition, but
> it isn't entirely clear that this is a net win. It is a huge win with the
> sequential version.
>
> On Sun, Nov 6, 2011 at 3:17 PM, Sean Owen <sr...@gmail.com> wrote:
>
>> Yeah OK, that makes sense. That's a pretty helpful paper.
>>
>> I can get through the Lanczos algorithm without much trouble, I think.
>> The piece I'm looking for pointers on at the moment is the eigen
>> decomposition of the tridiagonal matrix.
>>
>> Jake am I right that this is done in memory right now? I am sure your
>> previous comment actually answers this next question, but I haven't
>> connected the dots yet. If we're getting eigenvectors of AT * A, and
>> that matrix is huge, then isn't the tridiagonal matrix still huge --
>> albeit it has only 3m entries, not m^2. It seems like the code just
>> calls to EigenDecomposer which treats it as a dense m x m matrix.
>>
>> (Is it worth me figuring out the QR decomposition enough to build a
>> distributed version of it?)
>>
>> On Sun, Nov 6, 2011 at 7:25 PM, Sebastian Schelter <ss...@apache.org> wrote:
>> > On 06.11.2011 18:52, Sean Owen wrote:
>> >> Following up on this very old thread.
>> >>
>> >> I understood all this bit, thanks, that greatly clarified.
>> >>
>> >> You multiply a new user vector by V to project it into the new
>> >> "pseudo-item", reduced-dimension space.
>> >> And to get back to real items, you multiply by V's inverse, which is
>> >> its transpose.
>> >> And so you are really multiplying the user vector by V VT, which is
>> >> not a no-op, since those are truncated matrices and aren't actually
>> >> exact inverses (?)
>> >>
>> >> The original paper talks about cosine similarities between users or
>> >> items in the reduced-dimension space, but, can anyone shine light on
>> >> the point of that?
>> >
>> > I think this interpretation is coming from LSI where you project a query
>> > onto the document feature space and use the cosine to find the most
>> > similar documents (which can be done by simple matrix vector
>> > mulitplication as the singular vectors are orthonormal and computing dot
>> > products with the projected query is therefore equal to computing
>> cosines).
>> >
>> > Something similar could be done to find most similar items or users, the
>> > bad thing is that AFAIK you have to look at every other user or item as
>> > U and V are dense.
>> >
>> > Maybe this paper can help to shine light on that:
>> >
>> > "Using Linear Algebra for Intelligent Information Retrieval"
>> >
>> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.3138&rep=rep1&type=pdf
>> >
>> > From the paper also, it seems like they say the
>> >> predictions are just computed as vector products as above.
>> >>
>> >>
>> >> Finally, separately, I'm trying to understand the Lanczos method as
>> >> part of computing an SVD. Lanczos operates on a real symmetric matrix
>> >> right? And am I right that it comes into play when you are computing
>> >> and SVD...
>> >>
>> >> A = U * S * VT
>> >>
>> >> ... because U is actually the eigenvectors of (symmetric) A*AT and V
>> >> is the eigenvectors of AT*A? And so Lanczos is used to answer those
>> >> questions to complete the SVD
>> >>
>> >> On Fri, Jun 4, 2010 at 6:48 AM, Ted Dunning <te...@gmail.com>
>> wrote:
>> >>> You are correct. The paper has an appalling treatment of the folding
>> in
>> >>> approach.
>> >>>
>> >>> In fact, the procedure is dead simple.
>> >>>
>> >>> The basic idea is to leave the coordinate system derived in the
>> original SVD
>> >>> intact and simply project the new users into that space.
>> >>>
>> >>> The easiest way to see what is happening is to start again with the
>> original
>> >>> rating matrix A as decomposed:
>> >>>
>> >>> A = U S V'
>> >>>
>> >>> where A is users x items. If we multiply on the right by V, we get
>> >>>
>> >>> A V = U S V' V = U S
>> >>>
>> >>> (because V' V = I, by definition). This result is (users x items) x
>> (items
>> >>> x k) = users x k, that is, it gives a k dimensional vector for each
>> user.
>> >>> Similarly, multiplication on the left by U' gives a k x items matrix
>> which,
>> >>> when transposed gives a k dimensional vector for each item.
>> >>>
>> >>> This implies that if we augment U with new user row vectors U_new, we
>> should
>> >>> be able to simply compute new k-dimensional vectors for the new users
>> and
>> >>> adjoin these new vectors to the previous vectors. Concisely put,
>> >>>
>> >>> ( A ) ( A V )
>> >>> ( ) V = ( )
>> >>> ( A_new ) ( A_new V )
>> >>>
>> >>> This isn't really magical. It just says that we can compute new user
>> >>> vectors at any time by multiplying the new users' ratings by V.
>> >>>
>> >>> The diagram in figure one is hideously confusing because it looks like
>> a
>> >>> picture of some kind of multiplication whereas it is really depicting
>> some
>> >>> odd kind of flow diagram.
>> >>>
>> >>> Does this solve the problem?
>> >>>
>> >>> On Thu, Jun 3, 2010 at 9:26 AM, Sean Owen <sr...@gmail.com> wrote:
>> >>>
>> >>>> Section 3 is hard to understand.
>> >>>>
>> >>>> - Ak and P are defined, but not used later
>> >>>> - Definition of P has UTk x Nu as a computation. UTk is a k x m
>> >>>> matrix, and Nu is "t" x 1. t is not defined.
>> >>>> - This only makes sense if t = m. But m is the number of users, and Nu
>> >>>> is a user vector, so should have a number of elements equal to n, the
>> >>>> number of items
>> >>>> - Sk * VTk is described as a k x "d" matrix but d is undefined
>> >>>> - The diagram suggests that VTk are multiplied by all the Nu, which
>> >>>> makes more sense -- but only if Nu are multiplied by VTk, not the
>> >>>> other way. And the diagram depicts neither of those.
>> >>>> - Conceptually I would understand Nu x VTk, but then P is defined by
>> >>>> an additional product with Uk
>> >>>>
>> >>>> In short... what?
>> >>>>
>> >>>>
>> >>>> On Thu, Jun 3, 2010 at 4:15 PM, Ted Dunning <te...@gmail.com>
>> wrote:
>> >>>>> Fire away.
>> >>>>>
>> >>>>> On Thu, Jun 3, 2010 at 3:52 AM, Sean Owen <sr...@gmail.com> wrote:
>> >>>>>
>> >>>>>> Is anyone out there familiar enough with this to a) discuss this
>> paper
>> >>>>>> with me or b) point me to another writeup on the approach?
>> >>>>>>
>> >>>>>
>> >>>>
>> >>>
>> >
>> >
>>
>
Re: Understanding the SVD recommender
Posted by Ted Dunning <te...@gmail.com>.
it only matters for non-Mahout applications, but if you have repeated
eigenvalues, then any vector in the space spanned by the corresponding
eigenvectors is also an eigenvector. To the extent that you might have
nearly repeated eigenvalues, vectors in the space spanned by the
corresponding eigenvectors will be nearly eigenvectors. That is what makes
Jake's test work ... to misquote the over-quoted move, Eigen is as Eigen
does.
On Sun, Nov 6, 2011 at 4:19 PM, Jake Mannix <ja...@gmail.com> wrote:
> But you don't need a formula: look at EigenVerificationJob for the way to
> measure your accuracy, you can just run this on your data after you've
> extracted out your first k singular vector/value pairs, and see how far
> into
> this list you want to keep. The measurement I use is "how close to an
> eigenvector is this vector?". I.e. how big is 1 - (v/|v|) .
> ((AA'v)/|AA'v|) ?
>
Re: Understanding the SVD recommender
Posted by Lance Norskog <go...@gmail.com>.
There's a formula for random projection. Something along the lines of "if
your data has error e, a function on (new dimensions, old dimensions, e)".
(Or maybe I found this in one of the +1/-1 random projection papers.)
But anyway a function on the error of the original data seems more useful
than an absolute error.
On Sun, Nov 6, 2011 at 4:33 PM, Ted Dunning <te...@gmail.com> wrote:
> I think that this gives you a measure of the error due to all of the
> missing eigenvectors/values, not the accuracy of the ones that are present.
>
> Both questions are interesting ones and the answers are clearly somewhat
> related.
>
> On Sun, Nov 6, 2011 at 4:29 PM, Danny Bickson <danny.bickson@gmail.com
> >wrote:
>
> > Regarding accuracy, you can also compute norm(T- V'*A*V)
> > where T is the tridiagonal matrix, V is a matrix with the intermediate
> > solution vectors v_i , and A is the original matrix you want to
> > approximate. (If A is not symmetric then replace it with A*A')
> >
> > On Sun, Nov 6, 2011 at 7:19 PM, Jake Mannix <ja...@gmail.com>
> wrote:
> >
> > > The idea is this: after k iterations, you have a k-by-k tri-diagonal
> > > matrix, the
> > > eigenvalues of *this* are *an approximation* to the top k eigenvalues
> of
> > > A*A'. The largest of these k will have the least error, the next will
> > have
> > > more,
> > > and so on down the line. I've typically assumed that the bottom 1/3rd
> or
> > > so of the k are not going to be very accurate, but it depends on the
> > > spectrum
> > > of eigenvalues of A*A', sometimes all but the last few are very
> > accurately
> > > computed (but sometimes it's even worse: if the spectrum is very flat,
> > the
> > > mixing between eigenvectors can be near complete)
> > >
> > > But you don't need a formula: look at EigenVerificationJob for the way
> to
> > > measure your accuracy, you can just run this on your data after you've
> > > extracted out your first k singular vector/value pairs, and see how far
> > > into
> > > this list you want to keep. The measurement I use is "how close to an
> > > eigenvector is this vector?". I.e. how big is 1 - (v/|v|) .
> > > ((AA'v)/|AA'v|) ?
> > >
> > > -jake
> > >
> > >
> > > On Sun, Nov 6, 2011 at 3:59 PM, Lance Norskog <go...@gmail.com>
> wrote:
> > >
> > > > Is there a formula (somewhere easy to find) for "slop" and
> "accurate"?
> > > >
> > > > On Sun, Nov 6, 2011 at 3:57 PM, Ted Dunning <te...@gmail.com>
> > > wrote:
> > > >
> > > > > Almost exactly. If you stop at k iterations, you don't get the
> top k
> > > > > eigenvalues precisely. You need some extra slop to make sure your
> > top
> > > > > eigenvalues are accurate.
> > > > >
> > > > > On Sun, Nov 6, 2011 at 3:46 PM, Danny Bickson <
> > danny.bickson@gmail.com
> > > > > >wrote:
> > > > >
> > > > > > Exactly, in each iteration you extract one more eigenvalue from
> > > largest
> > > > > to
> > > > > > smallest. If you run more iterations then the matrix rank then
> you
> > > get
> > > > > > again all eigenvalues. In that case you may encounter each
> > > eigenvalue a
> > > > > few
> > > > > > times.
> > > > > >
> > > > > > On Sun, Nov 6, 2011 at 6:42 PM, Sean Owen <sr...@gmail.com>
> > wrote:
> > > > > >
> > > > > > > True though I thought it was intended to run through all m
> steps
> > -
> > > is
> > > > > it
> > > > > > > simply that you stop after some number k and that still leads
> you
> > > to
> > > > > > > compute the k largest eigenvectors of the original?
> > > > > > > On Nov 6, 2011 11:36 PM, "Danny Bickson" <
> > danny.bickson@gmail.com
> > > >
> > > > > > wrote:
> > > > > > >
> > > > > > > > To be exact, the size of the tridiagonal matrix
> > > > > > > > is number of iterations + 1. See description of the matrix
> T_mm
> > > > > > > > in Wikipedia: http://en.wikipedia.org/wiki/Lanczos_algorithm
> > > > > > > >
> > > > > > > > Best,
> > > > > > > >
> > > > > > > > DB
> > > > > > > >
> > > > > > > > On Sun, Nov 6, 2011 at 6:30 PM, Sean Owen <sr...@gmail.com>
> > > > wrote:
> > > > > > > >
> > > > > > > > > Oh do you only need the top k x k bit of the tridiagonal to
> > > find
> > > > > the
> > > > > > > > > top k eigenvalues?
> > > > > > > > >
> > > > > > > > > I really don't want to write a QR decomposer, phew.
> > > > > > > > >
> > > > > > > > > On Sun, Nov 6, 2011 at 11:26 PM, Ted Dunning <
> > > > > ted.dunning@gmail.com>
> > > > > > > > > wrote:
> > > > > > > > > > The tridiagonal is much smaller than you would need if
> you
> > > > wanted
> > > > > > all
> > > > > > > > the
> > > > > > > > > > eigenvalues. Since you only want a small number, you
> only
> > > > have a
> > > > > > > > > > tri-diagonal matrix that is some multiple of that size.
> > > > > In-memory
> > > > > > > > > > decomposition makes total sense.
> > > > > > > > > >
> > > > > > > > >
> > > > > > > >
> > > > > > >
> > > > > >
> > > > >
> > > >
> > > >
> > > >
> > > > --
> > > > Lance Norskog
> > > > goksron@gmail.com
> > > >
> > >
> >
>
--
Lance Norskog
goksron@gmail.com
Re: Understanding the SVD recommender
Posted by Ted Dunning <te...@gmail.com>.
I think that this gives you a measure of the error due to all of the
missing eigenvectors/values, not the accuracy of the ones that are present.
Both questions are interesting ones and the answers are clearly somewhat
related.
On Sun, Nov 6, 2011 at 4:29 PM, Danny Bickson <da...@gmail.com>wrote:
> Regarding accuracy, you can also compute norm(T- V'*A*V)
> where T is the tridiagonal matrix, V is a matrix with the intermediate
> solution vectors v_i , and A is the original matrix you want to
> approximate. (If A is not symmetric then replace it with A*A')
>
> On Sun, Nov 6, 2011 at 7:19 PM, Jake Mannix <ja...@gmail.com> wrote:
>
> > The idea is this: after k iterations, you have a k-by-k tri-diagonal
> > matrix, the
> > eigenvalues of *this* are *an approximation* to the top k eigenvalues of
> > A*A'. The largest of these k will have the least error, the next will
> have
> > more,
> > and so on down the line. I've typically assumed that the bottom 1/3rd or
> > so of the k are not going to be very accurate, but it depends on the
> > spectrum
> > of eigenvalues of A*A', sometimes all but the last few are very
> accurately
> > computed (but sometimes it's even worse: if the spectrum is very flat,
> the
> > mixing between eigenvectors can be near complete)
> >
> > But you don't need a formula: look at EigenVerificationJob for the way to
> > measure your accuracy, you can just run this on your data after you've
> > extracted out your first k singular vector/value pairs, and see how far
> > into
> > this list you want to keep. The measurement I use is "how close to an
> > eigenvector is this vector?". I.e. how big is 1 - (v/|v|) .
> > ((AA'v)/|AA'v|) ?
> >
> > -jake
> >
> >
> > On Sun, Nov 6, 2011 at 3:59 PM, Lance Norskog <go...@gmail.com> wrote:
> >
> > > Is there a formula (somewhere easy to find) for "slop" and "accurate"?
> > >
> > > On Sun, Nov 6, 2011 at 3:57 PM, Ted Dunning <te...@gmail.com>
> > wrote:
> > >
> > > > Almost exactly. If you stop at k iterations, you don't get the top k
> > > > eigenvalues precisely. You need some extra slop to make sure your
> top
> > > > eigenvalues are accurate.
> > > >
> > > > On Sun, Nov 6, 2011 at 3:46 PM, Danny Bickson <
> danny.bickson@gmail.com
> > > > >wrote:
> > > >
> > > > > Exactly, in each iteration you extract one more eigenvalue from
> > largest
> > > > to
> > > > > smallest. If you run more iterations then the matrix rank then you
> > get
> > > > > again all eigenvalues. In that case you may encounter each
> > eigenvalue a
> > > > few
> > > > > times.
> > > > >
> > > > > On Sun, Nov 6, 2011 at 6:42 PM, Sean Owen <sr...@gmail.com>
> wrote:
> > > > >
> > > > > > True though I thought it was intended to run through all m steps
> -
> > is
> > > > it
> > > > > > simply that you stop after some number k and that still leads you
> > to
> > > > > > compute the k largest eigenvectors of the original?
> > > > > > On Nov 6, 2011 11:36 PM, "Danny Bickson" <
> danny.bickson@gmail.com
> > >
> > > > > wrote:
> > > > > >
> > > > > > > To be exact, the size of the tridiagonal matrix
> > > > > > > is number of iterations + 1. See description of the matrix T_mm
> > > > > > > in Wikipedia: http://en.wikipedia.org/wiki/Lanczos_algorithm
> > > > > > >
> > > > > > > Best,
> > > > > > >
> > > > > > > DB
> > > > > > >
> > > > > > > On Sun, Nov 6, 2011 at 6:30 PM, Sean Owen <sr...@gmail.com>
> > > wrote:
> > > > > > >
> > > > > > > > Oh do you only need the top k x k bit of the tridiagonal to
> > find
> > > > the
> > > > > > > > top k eigenvalues?
> > > > > > > >
> > > > > > > > I really don't want to write a QR decomposer, phew.
> > > > > > > >
> > > > > > > > On Sun, Nov 6, 2011 at 11:26 PM, Ted Dunning <
> > > > ted.dunning@gmail.com>
> > > > > > > > wrote:
> > > > > > > > > The tridiagonal is much smaller than you would need if you
> > > wanted
> > > > > all
> > > > > > > the
> > > > > > > > > eigenvalues. Since you only want a small number, you only
> > > have a
> > > > > > > > > tri-diagonal matrix that is some multiple of that size.
> > > > In-memory
> > > > > > > > > decomposition makes total sense.
> > > > > > > > >
> > > > > > > >
> > > > > > >
> > > > > >
> > > > >
> > > >
> > >
> > >
> > >
> > > --
> > > Lance Norskog
> > > goksron@gmail.com
> > >
> >
>
Re: Understanding the SVD recommender
Posted by Danny Bickson <da...@gmail.com>.
Regarding accuracy, you can also compute norm(T- V'*A*V)
where T is the tridiagonal matrix, V is a matrix with the intermediate
solution vectors v_i , and A is the original matrix you want to
approximate. (If A is not symmetric then replace it with A*A')
On Sun, Nov 6, 2011 at 7:19 PM, Jake Mannix <ja...@gmail.com> wrote:
> The idea is this: after k iterations, you have a k-by-k tri-diagonal
> matrix, the
> eigenvalues of *this* are *an approximation* to the top k eigenvalues of
> A*A'. The largest of these k will have the least error, the next will have
> more,
> and so on down the line. I've typically assumed that the bottom 1/3rd or
> so of the k are not going to be very accurate, but it depends on the
> spectrum
> of eigenvalues of A*A', sometimes all but the last few are very accurately
> computed (but sometimes it's even worse: if the spectrum is very flat, the
> mixing between eigenvectors can be near complete)
>
> But you don't need a formula: look at EigenVerificationJob for the way to
> measure your accuracy, you can just run this on your data after you've
> extracted out your first k singular vector/value pairs, and see how far
> into
> this list you want to keep. The measurement I use is "how close to an
> eigenvector is this vector?". I.e. how big is 1 - (v/|v|) .
> ((AA'v)/|AA'v|) ?
>
> -jake
>
>
> On Sun, Nov 6, 2011 at 3:59 PM, Lance Norskog <go...@gmail.com> wrote:
>
> > Is there a formula (somewhere easy to find) for "slop" and "accurate"?
> >
> > On Sun, Nov 6, 2011 at 3:57 PM, Ted Dunning <te...@gmail.com>
> wrote:
> >
> > > Almost exactly. If you stop at k iterations, you don't get the top k
> > > eigenvalues precisely. You need some extra slop to make sure your top
> > > eigenvalues are accurate.
> > >
> > > On Sun, Nov 6, 2011 at 3:46 PM, Danny Bickson <danny.bickson@gmail.com
> > > >wrote:
> > >
> > > > Exactly, in each iteration you extract one more eigenvalue from
> largest
> > > to
> > > > smallest. If you run more iterations then the matrix rank then you
> get
> > > > again all eigenvalues. In that case you may encounter each
> eigenvalue a
> > > few
> > > > times.
> > > >
> > > > On Sun, Nov 6, 2011 at 6:42 PM, Sean Owen <sr...@gmail.com> wrote:
> > > >
> > > > > True though I thought it was intended to run through all m steps -
> is
> > > it
> > > > > simply that you stop after some number k and that still leads you
> to
> > > > > compute the k largest eigenvectors of the original?
> > > > > On Nov 6, 2011 11:36 PM, "Danny Bickson" <danny.bickson@gmail.com
> >
> > > > wrote:
> > > > >
> > > > > > To be exact, the size of the tridiagonal matrix
> > > > > > is number of iterations + 1. See description of the matrix T_mm
> > > > > > in Wikipedia: http://en.wikipedia.org/wiki/Lanczos_algorithm
> > > > > >
> > > > > > Best,
> > > > > >
> > > > > > DB
> > > > > >
> > > > > > On Sun, Nov 6, 2011 at 6:30 PM, Sean Owen <sr...@gmail.com>
> > wrote:
> > > > > >
> > > > > > > Oh do you only need the top k x k bit of the tridiagonal to
> find
> > > the
> > > > > > > top k eigenvalues?
> > > > > > >
> > > > > > > I really don't want to write a QR decomposer, phew.
> > > > > > >
> > > > > > > On Sun, Nov 6, 2011 at 11:26 PM, Ted Dunning <
> > > ted.dunning@gmail.com>
> > > > > > > wrote:
> > > > > > > > The tridiagonal is much smaller than you would need if you
> > wanted
> > > > all
> > > > > > the
> > > > > > > > eigenvalues. Since you only want a small number, you only
> > have a
> > > > > > > > tri-diagonal matrix that is some multiple of that size.
> > > In-memory
> > > > > > > > decomposition makes total sense.
> > > > > > > >
> > > > > > >
> > > > > >
> > > > >
> > > >
> > >
> >
> >
> >
> > --
> > Lance Norskog
> > goksron@gmail.com
> >
>
Re: Understanding the SVD recommender
Posted by Jake Mannix <ja...@gmail.com>.
The idea is this: after k iterations, you have a k-by-k tri-diagonal
matrix, the
eigenvalues of *this* are *an approximation* to the top k eigenvalues of
A*A'. The largest of these k will have the least error, the next will have
more,
and so on down the line. I've typically assumed that the bottom 1/3rd or
so of the k are not going to be very accurate, but it depends on the
spectrum
of eigenvalues of A*A', sometimes all but the last few are very accurately
computed (but sometimes it's even worse: if the spectrum is very flat, the
mixing between eigenvectors can be near complete)
But you don't need a formula: look at EigenVerificationJob for the way to
measure your accuracy, you can just run this on your data after you've
extracted out your first k singular vector/value pairs, and see how far into
this list you want to keep. The measurement I use is "how close to an
eigenvector is this vector?". I.e. how big is 1 - (v/|v|) .
((AA'v)/|AA'v|) ?
-jake
On Sun, Nov 6, 2011 at 3:59 PM, Lance Norskog <go...@gmail.com> wrote:
> Is there a formula (somewhere easy to find) for "slop" and "accurate"?
>
> On Sun, Nov 6, 2011 at 3:57 PM, Ted Dunning <te...@gmail.com> wrote:
>
> > Almost exactly. If you stop at k iterations, you don't get the top k
> > eigenvalues precisely. You need some extra slop to make sure your top
> > eigenvalues are accurate.
> >
> > On Sun, Nov 6, 2011 at 3:46 PM, Danny Bickson <danny.bickson@gmail.com
> > >wrote:
> >
> > > Exactly, in each iteration you extract one more eigenvalue from largest
> > to
> > > smallest. If you run more iterations then the matrix rank then you get
> > > again all eigenvalues. In that case you may encounter each eigenvalue a
> > few
> > > times.
> > >
> > > On Sun, Nov 6, 2011 at 6:42 PM, Sean Owen <sr...@gmail.com> wrote:
> > >
> > > > True though I thought it was intended to run through all m steps - is
> > it
> > > > simply that you stop after some number k and that still leads you to
> > > > compute the k largest eigenvectors of the original?
> > > > On Nov 6, 2011 11:36 PM, "Danny Bickson" <da...@gmail.com>
> > > wrote:
> > > >
> > > > > To be exact, the size of the tridiagonal matrix
> > > > > is number of iterations + 1. See description of the matrix T_mm
> > > > > in Wikipedia: http://en.wikipedia.org/wiki/Lanczos_algorithm
> > > > >
> > > > > Best,
> > > > >
> > > > > DB
> > > > >
> > > > > On Sun, Nov 6, 2011 at 6:30 PM, Sean Owen <sr...@gmail.com>
> wrote:
> > > > >
> > > > > > Oh do you only need the top k x k bit of the tridiagonal to find
> > the
> > > > > > top k eigenvalues?
> > > > > >
> > > > > > I really don't want to write a QR decomposer, phew.
> > > > > >
> > > > > > On Sun, Nov 6, 2011 at 11:26 PM, Ted Dunning <
> > ted.dunning@gmail.com>
> > > > > > wrote:
> > > > > > > The tridiagonal is much smaller than you would need if you
> wanted
> > > all
> > > > > the
> > > > > > > eigenvalues. Since you only want a small number, you only
> have a
> > > > > > > tri-diagonal matrix that is some multiple of that size.
> > In-memory
> > > > > > > decomposition makes total sense.
> > > > > > >
> > > > > >
> > > > >
> > > >
> > >
> >
>
>
>
> --
> Lance Norskog
> goksron@gmail.com
>
Re: Understanding the SVD recommender
Posted by Ted Dunning <te...@gmail.com>.
Not particularly easy to understand. See the Lanczos section in Matrix
Computations by Golub and van
Loan<http://www.amazon.com/Computations-Hopkins-Studies-Mathematical-Sciences/dp/0801854148>
There is a similar slop required for the random projection stuff. You
could make a hand-waving argument that the slop is similarly motivated in
both cases, but the random projection probably needs more slop because it
commits to a sub-space on the first step.
On Sun, Nov 6, 2011 at 3:59 PM, Lance Norskog <go...@gmail.com> wrote:
> Is there a formula (somewhere easy to find) for "slop" and "accurate"?
>
> On Sun, Nov 6, 2011 at 3:57 PM, Ted Dunning <te...@gmail.com> wrote:
>
> > Almost exactly. If you stop at k iterations, you don't get the top k
> > eigenvalues precisely. You need some extra slop to make sure your top
> > eigenvalues are accurate.
> >
> > On Sun, Nov 6, 2011 at 3:46 PM, Danny Bickson <danny.bickson@gmail.com
> > >wrote:
> >
> > > Exactly, in each iteration you extract one more eigenvalue from largest
> > to
> > > smallest. If you run more iterations then the matrix rank then you get
> > > again all eigenvalues. In that case you may encounter each eigenvalue a
> > few
> > > times.
> > >
> > > On Sun, Nov 6, 2011 at 6:42 PM, Sean Owen <sr...@gmail.com> wrote:
> > >
> > > > True though I thought it was intended to run through all m steps - is
> > it
> > > > simply that you stop after some number k and that still leads you to
> > > > compute the k largest eigenvectors of the original?
> > > > On Nov 6, 2011 11:36 PM, "Danny Bickson" <da...@gmail.com>
> > > wrote:
> > > >
> > > > > To be exact, the size of the tridiagonal matrix
> > > > > is number of iterations + 1. See description of the matrix T_mm
> > > > > in Wikipedia: http://en.wikipedia.org/wiki/Lanczos_algorithm
> > > > >
> > > > > Best,
> > > > >
> > > > > DB
> > > > >
> > > > > On Sun, Nov 6, 2011 at 6:30 PM, Sean Owen <sr...@gmail.com>
> wrote:
> > > > >
> > > > > > Oh do you only need the top k x k bit of the tridiagonal to find
> > the
> > > > > > top k eigenvalues?
> > > > > >
> > > > > > I really don't want to write a QR decomposer, phew.
> > > > > >
> > > > > > On Sun, Nov 6, 2011 at 11:26 PM, Ted Dunning <
> > ted.dunning@gmail.com>
> > > > > > wrote:
> > > > > > > The tridiagonal is much smaller than you would need if you
> wanted
> > > all
> > > > > the
> > > > > > > eigenvalues. Since you only want a small number, you only
> have a
> > > > > > > tri-diagonal matrix that is some multiple of that size.
> > In-memory
> > > > > > > decomposition makes total sense.
> > > > > > >
> > > > > >
> > > > >
> > > >
> > >
> >
>
>
>
> --
> Lance Norskog
> goksron@gmail.com
>
Re: Understanding the SVD recommender
Posted by Lance Norskog <go...@gmail.com>.
Is there a formula (somewhere easy to find) for "slop" and "accurate"?
On Sun, Nov 6, 2011 at 3:57 PM, Ted Dunning <te...@gmail.com> wrote:
> Almost exactly. If you stop at k iterations, you don't get the top k
> eigenvalues precisely. You need some extra slop to make sure your top
> eigenvalues are accurate.
>
> On Sun, Nov 6, 2011 at 3:46 PM, Danny Bickson <danny.bickson@gmail.com
> >wrote:
>
> > Exactly, in each iteration you extract one more eigenvalue from largest
> to
> > smallest. If you run more iterations then the matrix rank then you get
> > again all eigenvalues. In that case you may encounter each eigenvalue a
> few
> > times.
> >
> > On Sun, Nov 6, 2011 at 6:42 PM, Sean Owen <sr...@gmail.com> wrote:
> >
> > > True though I thought it was intended to run through all m steps - is
> it
> > > simply that you stop after some number k and that still leads you to
> > > compute the k largest eigenvectors of the original?
> > > On Nov 6, 2011 11:36 PM, "Danny Bickson" <da...@gmail.com>
> > wrote:
> > >
> > > > To be exact, the size of the tridiagonal matrix
> > > > is number of iterations + 1. See description of the matrix T_mm
> > > > in Wikipedia: http://en.wikipedia.org/wiki/Lanczos_algorithm
> > > >
> > > > Best,
> > > >
> > > > DB
> > > >
> > > > On Sun, Nov 6, 2011 at 6:30 PM, Sean Owen <sr...@gmail.com> wrote:
> > > >
> > > > > Oh do you only need the top k x k bit of the tridiagonal to find
> the
> > > > > top k eigenvalues?
> > > > >
> > > > > I really don't want to write a QR decomposer, phew.
> > > > >
> > > > > On Sun, Nov 6, 2011 at 11:26 PM, Ted Dunning <
> ted.dunning@gmail.com>
> > > > > wrote:
> > > > > > The tridiagonal is much smaller than you would need if you wanted
> > all
> > > > the
> > > > > > eigenvalues. Since you only want a small number, you only have a
> > > > > > tri-diagonal matrix that is some multiple of that size.
> In-memory
> > > > > > decomposition makes total sense.
> > > > > >
> > > > >
> > > >
> > >
> >
>
--
Lance Norskog
goksron@gmail.com
Re: Understanding the SVD recommender
Posted by Ted Dunning <te...@gmail.com>.
Almost exactly. If you stop at k iterations, you don't get the top k
eigenvalues precisely. You need some extra slop to make sure your top
eigenvalues are accurate.
On Sun, Nov 6, 2011 at 3:46 PM, Danny Bickson <da...@gmail.com>wrote:
> Exactly, in each iteration you extract one more eigenvalue from largest to
> smallest. If you run more iterations then the matrix rank then you get
> again all eigenvalues. In that case you may encounter each eigenvalue a few
> times.
>
> On Sun, Nov 6, 2011 at 6:42 PM, Sean Owen <sr...@gmail.com> wrote:
>
> > True though I thought it was intended to run through all m steps - is it
> > simply that you stop after some number k and that still leads you to
> > compute the k largest eigenvectors of the original?
> > On Nov 6, 2011 11:36 PM, "Danny Bickson" <da...@gmail.com>
> wrote:
> >
> > > To be exact, the size of the tridiagonal matrix
> > > is number of iterations + 1. See description of the matrix T_mm
> > > in Wikipedia: http://en.wikipedia.org/wiki/Lanczos_algorithm
> > >
> > > Best,
> > >
> > > DB
> > >
> > > On Sun, Nov 6, 2011 at 6:30 PM, Sean Owen <sr...@gmail.com> wrote:
> > >
> > > > Oh do you only need the top k x k bit of the tridiagonal to find the
> > > > top k eigenvalues?
> > > >
> > > > I really don't want to write a QR decomposer, phew.
> > > >
> > > > On Sun, Nov 6, 2011 at 11:26 PM, Ted Dunning <te...@gmail.com>
> > > > wrote:
> > > > > The tridiagonal is much smaller than you would need if you wanted
> all
> > > the
> > > > > eigenvalues. Since you only want a small number, you only have a
> > > > > tri-diagonal matrix that is some multiple of that size. In-memory
> > > > > decomposition makes total sense.
> > > > >
> > > >
> > >
> >
>
Re: Understanding the SVD recommender
Posted by Danny Bickson <da...@gmail.com>.
Exactly, in each iteration you extract one more eigenvalue from largest to
smallest. If you run more iterations then the matrix rank then you get
again all eigenvalues. In that case you may encounter each eigenvalue a few
times.
On Sun, Nov 6, 2011 at 6:42 PM, Sean Owen <sr...@gmail.com> wrote:
> True though I thought it was intended to run through all m steps - is it
> simply that you stop after some number k and that still leads you to
> compute the k largest eigenvectors of the original?
> On Nov 6, 2011 11:36 PM, "Danny Bickson" <da...@gmail.com> wrote:
>
> > To be exact, the size of the tridiagonal matrix
> > is number of iterations + 1. See description of the matrix T_mm
> > in Wikipedia: http://en.wikipedia.org/wiki/Lanczos_algorithm
> >
> > Best,
> >
> > DB
> >
> > On Sun, Nov 6, 2011 at 6:30 PM, Sean Owen <sr...@gmail.com> wrote:
> >
> > > Oh do you only need the top k x k bit of the tridiagonal to find the
> > > top k eigenvalues?
> > >
> > > I really don't want to write a QR decomposer, phew.
> > >
> > > On Sun, Nov 6, 2011 at 11:26 PM, Ted Dunning <te...@gmail.com>
> > > wrote:
> > > > The tridiagonal is much smaller than you would need if you wanted all
> > the
> > > > eigenvalues. Since you only want a small number, you only have a
> > > > tri-diagonal matrix that is some multiple of that size. In-memory
> > > > decomposition makes total sense.
> > > >
> > >
> >
>
Re: Understanding the SVD recommender
Posted by Sean Owen <sr...@gmail.com>.
True though I thought it was intended to run through all m steps - is it
simply that you stop after some number k and that still leads you to
compute the k largest eigenvectors of the original?
On Nov 6, 2011 11:36 PM, "Danny Bickson" <da...@gmail.com> wrote:
> To be exact, the size of the tridiagonal matrix
> is number of iterations + 1. See description of the matrix T_mm
> in Wikipedia: http://en.wikipedia.org/wiki/Lanczos_algorithm
>
> Best,
>
> DB
>
> On Sun, Nov 6, 2011 at 6:30 PM, Sean Owen <sr...@gmail.com> wrote:
>
> > Oh do you only need the top k x k bit of the tridiagonal to find the
> > top k eigenvalues?
> >
> > I really don't want to write a QR decomposer, phew.
> >
> > On Sun, Nov 6, 2011 at 11:26 PM, Ted Dunning <te...@gmail.com>
> > wrote:
> > > The tridiagonal is much smaller than you would need if you wanted all
> the
> > > eigenvalues. Since you only want a small number, you only have a
> > > tri-diagonal matrix that is some multiple of that size. In-memory
> > > decomposition makes total sense.
> > >
> >
>
Re: Understanding the SVD recommender
Posted by Danny Bickson <da...@gmail.com>.
To be exact, the size of the tridiagonal matrix
is number of iterations + 1. See description of the matrix T_mm
in Wikipedia: http://en.wikipedia.org/wiki/Lanczos_algorithm
Best,
DB
On Sun, Nov 6, 2011 at 6:30 PM, Sean Owen <sr...@gmail.com> wrote:
> Oh do you only need the top k x k bit of the tridiagonal to find the
> top k eigenvalues?
>
> I really don't want to write a QR decomposer, phew.
>
> On Sun, Nov 6, 2011 at 11:26 PM, Ted Dunning <te...@gmail.com>
> wrote:
> > The tridiagonal is much smaller than you would need if you wanted all the
> > eigenvalues. Since you only want a small number, you only have a
> > tri-diagonal matrix that is some multiple of that size. In-memory
> > decomposition makes total sense.
> >
>
Re: Understanding the SVD recommender
Posted by Sean Owen <sr...@gmail.com>.
Oh do you only need the top k x k bit of the tridiagonal to find the
top k eigenvalues?
I really don't want to write a QR decomposer, phew.
On Sun, Nov 6, 2011 at 11:26 PM, Ted Dunning <te...@gmail.com> wrote:
> The tridiagonal is much smaller than you would need if you wanted all the
> eigenvalues. Since you only want a small number, you only have a
> tri-diagonal matrix that is some multiple of that size. In-memory
> decomposition makes total sense.
>
Re: Understanding the SVD recommender
Posted by Ted Dunning <te...@gmail.com>.
The tridiagonal is much smaller than you would need if you wanted all the
eigenvalues. Since you only want a small number, you only have a
tri-diagonal matrix that is some multiple of that size. In-memory
decomposition makes total sense.
Regarding QR decomposition, Dmitriy has already built a parallel version.
A large QR is required at one point in the SSVD algorithm. I have shown a
way to avoid this large QR using a much smaller Cholesky decomposition, but
it isn't entirely clear that this is a net win. It is a huge win with the
sequential version.
On Sun, Nov 6, 2011 at 3:17 PM, Sean Owen <sr...@gmail.com> wrote:
> Yeah OK, that makes sense. That's a pretty helpful paper.
>
> I can get through the Lanczos algorithm without much trouble, I think.
> The piece I'm looking for pointers on at the moment is the eigen
> decomposition of the tridiagonal matrix.
>
> Jake am I right that this is done in memory right now? I am sure your
> previous comment actually answers this next question, but I haven't
> connected the dots yet. If we're getting eigenvectors of AT * A, and
> that matrix is huge, then isn't the tridiagonal matrix still huge --
> albeit it has only 3m entries, not m^2. It seems like the code just
> calls to EigenDecomposer which treats it as a dense m x m matrix.
>
> (Is it worth me figuring out the QR decomposition enough to build a
> distributed version of it?)
>
> On Sun, Nov 6, 2011 at 7:25 PM, Sebastian Schelter <ss...@apache.org> wrote:
> > On 06.11.2011 18:52, Sean Owen wrote:
> >> Following up on this very old thread.
> >>
> >> I understood all this bit, thanks, that greatly clarified.
> >>
> >> You multiply a new user vector by V to project it into the new
> >> "pseudo-item", reduced-dimension space.
> >> And to get back to real items, you multiply by V's inverse, which is
> >> its transpose.
> >> And so you are really multiplying the user vector by V VT, which is
> >> not a no-op, since those are truncated matrices and aren't actually
> >> exact inverses (?)
> >>
> >> The original paper talks about cosine similarities between users or
> >> items in the reduced-dimension space, but, can anyone shine light on
> >> the point of that?
> >
> > I think this interpretation is coming from LSI where you project a query
> > onto the document feature space and use the cosine to find the most
> > similar documents (which can be done by simple matrix vector
> > mulitplication as the singular vectors are orthonormal and computing dot
> > products with the projected query is therefore equal to computing
> cosines).
> >
> > Something similar could be done to find most similar items or users, the
> > bad thing is that AFAIK you have to look at every other user or item as
> > U and V are dense.
> >
> > Maybe this paper can help to shine light on that:
> >
> > "Using Linear Algebra for Intelligent Information Retrieval"
> >
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.3138&rep=rep1&type=pdf
> >
> > From the paper also, it seems like they say the
> >> predictions are just computed as vector products as above.
> >>
> >>
> >> Finally, separately, I'm trying to understand the Lanczos method as
> >> part of computing an SVD. Lanczos operates on a real symmetric matrix
> >> right? And am I right that it comes into play when you are computing
> >> and SVD...
> >>
> >> A = U * S * VT
> >>
> >> ... because U is actually the eigenvectors of (symmetric) A*AT and V
> >> is the eigenvectors of AT*A? And so Lanczos is used to answer those
> >> questions to complete the SVD
> >>
> >> On Fri, Jun 4, 2010 at 6:48 AM, Ted Dunning <te...@gmail.com>
> wrote:
> >>> You are correct. The paper has an appalling treatment of the folding
> in
> >>> approach.
> >>>
> >>> In fact, the procedure is dead simple.
> >>>
> >>> The basic idea is to leave the coordinate system derived in the
> original SVD
> >>> intact and simply project the new users into that space.
> >>>
> >>> The easiest way to see what is happening is to start again with the
> original
> >>> rating matrix A as decomposed:
> >>>
> >>> A = U S V'
> >>>
> >>> where A is users x items. If we multiply on the right by V, we get
> >>>
> >>> A V = U S V' V = U S
> >>>
> >>> (because V' V = I, by definition). This result is (users x items) x
> (items
> >>> x k) = users x k, that is, it gives a k dimensional vector for each
> user.
> >>> Similarly, multiplication on the left by U' gives a k x items matrix
> which,
> >>> when transposed gives a k dimensional vector for each item.
> >>>
> >>> This implies that if we augment U with new user row vectors U_new, we
> should
> >>> be able to simply compute new k-dimensional vectors for the new users
> and
> >>> adjoin these new vectors to the previous vectors. Concisely put,
> >>>
> >>> ( A ) ( A V )
> >>> ( ) V = ( )
> >>> ( A_new ) ( A_new V )
> >>>
> >>> This isn't really magical. It just says that we can compute new user
> >>> vectors at any time by multiplying the new users' ratings by V.
> >>>
> >>> The diagram in figure one is hideously confusing because it looks like
> a
> >>> picture of some kind of multiplication whereas it is really depicting
> some
> >>> odd kind of flow diagram.
> >>>
> >>> Does this solve the problem?
> >>>
> >>> On Thu, Jun 3, 2010 at 9:26 AM, Sean Owen <sr...@gmail.com> wrote:
> >>>
> >>>> Section 3 is hard to understand.
> >>>>
> >>>> - Ak and P are defined, but not used later
> >>>> - Definition of P has UTk x Nu as a computation. UTk is a k x m
> >>>> matrix, and Nu is "t" x 1. t is not defined.
> >>>> - This only makes sense if t = m. But m is the number of users, and Nu
> >>>> is a user vector, so should have a number of elements equal to n, the
> >>>> number of items
> >>>> - Sk * VTk is described as a k x "d" matrix but d is undefined
> >>>> - The diagram suggests that VTk are multiplied by all the Nu, which
> >>>> makes more sense -- but only if Nu are multiplied by VTk, not the
> >>>> other way. And the diagram depicts neither of those.
> >>>> - Conceptually I would understand Nu x VTk, but then P is defined by
> >>>> an additional product with Uk
> >>>>
> >>>> In short... what?
> >>>>
> >>>>
> >>>> On Thu, Jun 3, 2010 at 4:15 PM, Ted Dunning <te...@gmail.com>
> wrote:
> >>>>> Fire away.
> >>>>>
> >>>>> On Thu, Jun 3, 2010 at 3:52 AM, Sean Owen <sr...@gmail.com> wrote:
> >>>>>
> >>>>>> Is anyone out there familiar enough with this to a) discuss this
> paper
> >>>>>> with me or b) point me to another writeup on the approach?
> >>>>>>
> >>>>>
> >>>>
> >>>
> >
> >
>
Re: Understanding the SVD recommender
Posted by Sean Owen <sr...@gmail.com>.
Yeah OK, that makes sense. That's a pretty helpful paper.
I can get through the Lanczos algorithm without much trouble, I think.
The piece I'm looking for pointers on at the moment is the eigen
decomposition of the tridiagonal matrix.
Jake am I right that this is done in memory right now? I am sure your
previous comment actually answers this next question, but I haven't
connected the dots yet. If we're getting eigenvectors of AT * A, and
that matrix is huge, then isn't the tridiagonal matrix still huge --
albeit it has only 3m entries, not m^2. It seems like the code just
calls to EigenDecomposer which treats it as a dense m x m matrix.
(Is it worth me figuring out the QR decomposition enough to build a
distributed version of it?)
On Sun, Nov 6, 2011 at 7:25 PM, Sebastian Schelter <ss...@apache.org> wrote:
> On 06.11.2011 18:52, Sean Owen wrote:
>> Following up on this very old thread.
>>
>> I understood all this bit, thanks, that greatly clarified.
>>
>> You multiply a new user vector by V to project it into the new
>> "pseudo-item", reduced-dimension space.
>> And to get back to real items, you multiply by V's inverse, which is
>> its transpose.
>> And so you are really multiplying the user vector by V VT, which is
>> not a no-op, since those are truncated matrices and aren't actually
>> exact inverses (?)
>>
>> The original paper talks about cosine similarities between users or
>> items in the reduced-dimension space, but, can anyone shine light on
>> the point of that?
>
> I think this interpretation is coming from LSI where you project a query
> onto the document feature space and use the cosine to find the most
> similar documents (which can be done by simple matrix vector
> mulitplication as the singular vectors are orthonormal and computing dot
> products with the projected query is therefore equal to computing cosines).
>
> Something similar could be done to find most similar items or users, the
> bad thing is that AFAIK you have to look at every other user or item as
> U and V are dense.
>
> Maybe this paper can help to shine light on that:
>
> "Using Linear Algebra for Intelligent Information Retrieval"
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.3138&rep=rep1&type=pdf
>
> From the paper also, it seems like they say the
>> predictions are just computed as vector products as above.
>>
>>
>> Finally, separately, I'm trying to understand the Lanczos method as
>> part of computing an SVD. Lanczos operates on a real symmetric matrix
>> right? And am I right that it comes into play when you are computing
>> and SVD...
>>
>> A = U * S * VT
>>
>> ... because U is actually the eigenvectors of (symmetric) A*AT and V
>> is the eigenvectors of AT*A? And so Lanczos is used to answer those
>> questions to complete the SVD
>>
>> On Fri, Jun 4, 2010 at 6:48 AM, Ted Dunning <te...@gmail.com> wrote:
>>> You are correct. The paper has an appalling treatment of the folding in
>>> approach.
>>>
>>> In fact, the procedure is dead simple.
>>>
>>> The basic idea is to leave the coordinate system derived in the original SVD
>>> intact and simply project the new users into that space.
>>>
>>> The easiest way to see what is happening is to start again with the original
>>> rating matrix A as decomposed:
>>>
>>> A = U S V'
>>>
>>> where A is users x items. If we multiply on the right by V, we get
>>>
>>> A V = U S V' V = U S
>>>
>>> (because V' V = I, by definition). This result is (users x items) x (items
>>> x k) = users x k, that is, it gives a k dimensional vector for each user.
>>> Similarly, multiplication on the left by U' gives a k x items matrix which,
>>> when transposed gives a k dimensional vector for each item.
>>>
>>> This implies that if we augment U with new user row vectors U_new, we should
>>> be able to simply compute new k-dimensional vectors for the new users and
>>> adjoin these new vectors to the previous vectors. Concisely put,
>>>
>>> ( A ) ( A V )
>>> ( ) V = ( )
>>> ( A_new ) ( A_new V )
>>>
>>> This isn't really magical. It just says that we can compute new user
>>> vectors at any time by multiplying the new users' ratings by V.
>>>
>>> The diagram in figure one is hideously confusing because it looks like a
>>> picture of some kind of multiplication whereas it is really depicting some
>>> odd kind of flow diagram.
>>>
>>> Does this solve the problem?
>>>
>>> On Thu, Jun 3, 2010 at 9:26 AM, Sean Owen <sr...@gmail.com> wrote:
>>>
>>>> Section 3 is hard to understand.
>>>>
>>>> - Ak and P are defined, but not used later
>>>> - Definition of P has UTk x Nu as a computation. UTk is a k x m
>>>> matrix, and Nu is "t" x 1. t is not defined.
>>>> - This only makes sense if t = m. But m is the number of users, and Nu
>>>> is a user vector, so should have a number of elements equal to n, the
>>>> number of items
>>>> - Sk * VTk is described as a k x "d" matrix but d is undefined
>>>> - The diagram suggests that VTk are multiplied by all the Nu, which
>>>> makes more sense -- but only if Nu are multiplied by VTk, not the
>>>> other way. And the diagram depicts neither of those.
>>>> - Conceptually I would understand Nu x VTk, but then P is defined by
>>>> an additional product with Uk
>>>>
>>>> In short... what?
>>>>
>>>>
>>>> On Thu, Jun 3, 2010 at 4:15 PM, Ted Dunning <te...@gmail.com> wrote:
>>>>> Fire away.
>>>>>
>>>>> On Thu, Jun 3, 2010 at 3:52 AM, Sean Owen <sr...@gmail.com> wrote:
>>>>>
>>>>>> Is anyone out there familiar enough with this to a) discuss this paper
>>>>>> with me or b) point me to another writeup on the approach?
>>>>>>
>>>>>
>>>>
>>>
>
>
Re: Understanding the SVD recommender
Posted by Sebastian Schelter <ss...@apache.org>.
On 06.11.2011 18:52, Sean Owen wrote:
> Following up on this very old thread.
>
> I understood all this bit, thanks, that greatly clarified.
>
> You multiply a new user vector by V to project it into the new
> "pseudo-item", reduced-dimension space.
> And to get back to real items, you multiply by V's inverse, which is
> its transpose.
> And so you are really multiplying the user vector by V VT, which is
> not a no-op, since those are truncated matrices and aren't actually
> exact inverses (?)
>
> The original paper talks about cosine similarities between users or
> items in the reduced-dimension space, but, can anyone shine light on
> the point of that?
I think this interpretation is coming from LSI where you project a query
onto the document feature space and use the cosine to find the most
similar documents (which can be done by simple matrix vector
mulitplication as the singular vectors are orthonormal and computing dot
products with the projected query is therefore equal to computing cosines).
Something similar could be done to find most similar items or users, the
bad thing is that AFAIK you have to look at every other user or item as
U and V are dense.
Maybe this paper can help to shine light on that:
"Using Linear Algebra for Intelligent Information Retrieval"
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.3138&rep=rep1&type=pdf
>From the paper also, it seems like they say the
> predictions are just computed as vector products as above.
>
>
> Finally, separately, I'm trying to understand the Lanczos method as
> part of computing an SVD. Lanczos operates on a real symmetric matrix
> right? And am I right that it comes into play when you are computing
> and SVD...
>
> A = U * S * VT
>
> ... because U is actually the eigenvectors of (symmetric) A*AT and V
> is the eigenvectors of AT*A? And so Lanczos is used to answer those
> questions to complete the SVD
>
> On Fri, Jun 4, 2010 at 6:48 AM, Ted Dunning <te...@gmail.com> wrote:
>> You are correct. The paper has an appalling treatment of the folding in
>> approach.
>>
>> In fact, the procedure is dead simple.
>>
>> The basic idea is to leave the coordinate system derived in the original SVD
>> intact and simply project the new users into that space.
>>
>> The easiest way to see what is happening is to start again with the original
>> rating matrix A as decomposed:
>>
>> A = U S V'
>>
>> where A is users x items. If we multiply on the right by V, we get
>>
>> A V = U S V' V = U S
>>
>> (because V' V = I, by definition). This result is (users x items) x (items
>> x k) = users x k, that is, it gives a k dimensional vector for each user.
>> Similarly, multiplication on the left by U' gives a k x items matrix which,
>> when transposed gives a k dimensional vector for each item.
>>
>> This implies that if we augment U with new user row vectors U_new, we should
>> be able to simply compute new k-dimensional vectors for the new users and
>> adjoin these new vectors to the previous vectors. Concisely put,
>>
>> ( A ) ( A V )
>> ( ) V = ( )
>> ( A_new ) ( A_new V )
>>
>> This isn't really magical. It just says that we can compute new user
>> vectors at any time by multiplying the new users' ratings by V.
>>
>> The diagram in figure one is hideously confusing because it looks like a
>> picture of some kind of multiplication whereas it is really depicting some
>> odd kind of flow diagram.
>>
>> Does this solve the problem?
>>
>> On Thu, Jun 3, 2010 at 9:26 AM, Sean Owen <sr...@gmail.com> wrote:
>>
>>> Section 3 is hard to understand.
>>>
>>> - Ak and P are defined, but not used later
>>> - Definition of P has UTk x Nu as a computation. UTk is a k x m
>>> matrix, and Nu is "t" x 1. t is not defined.
>>> - This only makes sense if t = m. But m is the number of users, and Nu
>>> is a user vector, so should have a number of elements equal to n, the
>>> number of items
>>> - Sk * VTk is described as a k x "d" matrix but d is undefined
>>> - The diagram suggests that VTk are multiplied by all the Nu, which
>>> makes more sense -- but only if Nu are multiplied by VTk, not the
>>> other way. And the diagram depicts neither of those.
>>> - Conceptually I would understand Nu x VTk, but then P is defined by
>>> an additional product with Uk
>>>
>>> In short... what?
>>>
>>>
>>> On Thu, Jun 3, 2010 at 4:15 PM, Ted Dunning <te...@gmail.com> wrote:
>>>> Fire away.
>>>>
>>>> On Thu, Jun 3, 2010 at 3:52 AM, Sean Owen <sr...@gmail.com> wrote:
>>>>
>>>>> Is anyone out there familiar enough with this to a) discuss this paper
>>>>> with me or b) point me to another writeup on the approach?
>>>>>
>>>>
>>>
>>
Re: Understanding the SVD recommender
Posted by Ted Dunning <te...@gmail.com>.
Yeah... a good alternative is to use the random projection stuff.
On Thu, Nov 17, 2011 at 9:12 AM, Sean Owen <sr...@gmail.com> wrote:
> Ah-ha. That's clicked now. Especially as I read the comments and see it
> already says exactly this.
>
> And I understand that you just compute extra eigenvectors then throw out
> near-duplicates, or those that are too un-eigenvector -- are there good
> pointers on the alternatives for that, or are alternatives impractical? I
> understand it's possible to re-figure the vectors it produces at each
> iteration to be orthogonal, but don't know whether that's considered
> unhelpful.
>
Re: Understanding the SVD recommender
Posted by Sean Owen <sr...@gmail.com>.
Ah-ha. That's clicked now. Especially as I read the comments and see it
already says exactly this.
And I understand that you just compute extra eigenvectors then throw out
near-duplicates, or those that are too un-eigenvector -- are there good
pointers on the alternatives for that, or are alternatives impractical? I
understand it's possible to re-figure the vectors it produces at each
iteration to be orthogonal, but don't know whether that's considered
unhelpful.
On Thu, Nov 17, 2011 at 3:21 PM, Jake Mannix <ja...@gmail.com> wrote:
>
> 2) you rewrite the double summation involved in the definition of
> (A'A)v to notice that it can be done in one pass over A:
>
> (A'A)v = vectorSum_i(a_i' (a_i * v))
>
>
Re: Understanding the SVD recommender
Posted by Ted Dunning <te...@gmail.com>.
On Thu, Nov 17, 2011 at 7:21 AM, Jake Mannix <ja...@gmail.com> wrote:
> On Thu, Nov 17, 2011 at 5:26 AM, Sean Owen <sr...@gmail.com> wrote:
>
> > One more question. OK, so I use Lanczos to find V_k by finding the top k
> > eigenvectors of AT * A. A is sparse. But isn't AT * A dense, then? Is
> that
> > just how it is?
> >
>
> A'A and AA' are both dense, yes, but you never compute them.
Actually, they aren't necessarily dense. Computing them explicitly can
still be a pain in a****.
> ...
> 1) you do two Matrix - Vector multiplications per Lanczos iteration:
> first
> take (sparse) A and multiply it by a vector v. Then take (also sparse) A'
> and multiply it by the now-computed u = Av. A'u = A'(A v) = (A'A)v
>
This is the traditional method used in most implementations of Lanczos.
Jake's one-pass map-reduce is better for our needs.
Re: Understanding the SVD recommender
Posted by Jake Mannix <ja...@gmail.com>.
On Thu, Nov 17, 2011 at 5:26 AM, Sean Owen <sr...@gmail.com> wrote:
> One more question. OK, so I use Lanczos to find V_k by finding the top k
> eigenvectors of AT * A. A is sparse. But isn't AT * A dense, then? Is that
> just how it is?
>
A'A and AA' are both dense, yes, but you never compute them. There are
several ways to avoid computing them:
1) you do two Matrix - Vector multiplications per Lanczos iteration:
first
take (sparse) A and multiply it by a vector v. Then take (also sparse) A'
and multiply it by the now-computed u = Av. A'u = A'(A v) = (A'A)v
2) you rewrite the double summation involved in the definition of
(A'A)v to notice that it can be done in one pass over A:
(A'A)v = vectorSum_i(a_i' (a_i * v))
where a_i is the i'th row of A, and the Map operation is everything in
the outer parenthesis: take vector v (which is living in memory) and
dot it with a_i, then take emit a_i' scaled by this value. Reduce is
just vector summation.
We take approach 2), and is why we have the horrible method
"timesSquared(Vector)" as a special optimization method in
the VectorIterable interface.
This trick is essentially how we compute sparse matrix multiplication
as well.
> This will be my last basic question for the week:
>
> I understand that A ~= U_k * S_k * V_kT. Let's call the product on the
> right A_k.
>
> A_k = A * V_k * V_kT right?
>
yeah, I guess so.
> And then A_k is just my complete prediction matrix right? It's dense so
> it's not formed all at once. But all I need are V_k and its transpose to do
> the work.
>
Correct. With V_k and V_k' in memory (if they're small enough), you can
compute a row of A_k on the fly by doing two matrix-vector multiplications.
> I somehow thought it was more complicated than this -- having come back to
> this I keep wondering if I forget something here.
>
No, I think this is it. You might need S^-1 somewhere in there that I'm
forgetting, but this looks right.
-jake
>
>
> On Sun, Nov 6, 2011 at 6:08 PM, Jake Mannix <ja...@gmail.com> wrote:
>
> > Re: Lanczos, yes, it operates by finding V as you describe. The user is
> > required to do more work to recapture U. Practical reason is that the
> > assumption is numCols(A) = numFeatures which is much less than
> numRows(A) =
> > numTrainingSamples
> >
> > On Nov 6, 2011 9:52 AM, "Sean Owen" <sr...@gmail.com> wrote:
> >
> > Following up on this very old thread.
> >
> > I understood all this bit, thanks, that greatly clarified.
> >
> > You multiply a new user vector by V to project it into the new
> > "pseudo-item", reduced-dimension space.
> > And to get back to real items, you multiply by V's inverse, which is
> > its transpose.
> > And so you are really multiplying the user vector by V VT, which is
> > not a no-op, since those are truncated matrices and aren't actually
> > exact inverses (?)
> >
> > The original paper talks about cosine similarities between users or
> > items in the reduced-dimension space, but, can anyone shine light on
> > the point of that? From the paper also, it seems like they say the
> > predictions are just computed as vector products as above.
> >
> >
> > Finally, separately, I'm trying to understand the Lanczos method as
> > part of computing an SVD. Lanczos operates on a real symmetric matrix
> > right? And am I right that it comes into play when you are computing
> > and SVD...
> >
> > A = U * S * VT
> >
> > ... because U is actually the eigenvectors of (symmetric) A*AT and V
> > is the eigenvectors of AT*A? And so Lanczos is used to answer those
> > questions to complete the SVD?
> >
> > On Fri, Jun 4, 2010 at 6:48 AM, Ted Dunning <te...@gmail.com>
> wrote:
> > > You are correct. The...
> >
>
Re: Understanding the SVD recommender
Posted by Sean Owen <sr...@gmail.com>.
One more question. OK, so I use Lanczos to find V_k by finding the top k
eigenvectors of AT * A. A is sparse. But isn't AT * A dense, then? Is that
just how it is?
This will be my last basic question for the week:
I understand that A ~= U_k * S_k * V_kT. Let's call the product on the
right A_k.
A_k = A * V_k * V_kT right?
And then A_k is just my complete prediction matrix right? It's dense so
it's not formed all at once. But all I need are V_k and its transpose to do
the work.
I somehow thought it was more complicated than this -- having come back to
this I keep wondering if I forget something here.
On Sun, Nov 6, 2011 at 6:08 PM, Jake Mannix <ja...@gmail.com> wrote:
> Re: Lanczos, yes, it operates by finding V as you describe. The user is
> required to do more work to recapture U. Practical reason is that the
> assumption is numCols(A) = numFeatures which is much less than numRows(A) =
> numTrainingSamples
>
> On Nov 6, 2011 9:52 AM, "Sean Owen" <sr...@gmail.com> wrote:
>
> Following up on this very old thread.
>
> I understood all this bit, thanks, that greatly clarified.
>
> You multiply a new user vector by V to project it into the new
> "pseudo-item", reduced-dimension space.
> And to get back to real items, you multiply by V's inverse, which is
> its transpose.
> And so you are really multiplying the user vector by V VT, which is
> not a no-op, since those are truncated matrices and aren't actually
> exact inverses (?)
>
> The original paper talks about cosine similarities between users or
> items in the reduced-dimension space, but, can anyone shine light on
> the point of that? From the paper also, it seems like they say the
> predictions are just computed as vector products as above.
>
>
> Finally, separately, I'm trying to understand the Lanczos method as
> part of computing an SVD. Lanczos operates on a real symmetric matrix
> right? And am I right that it comes into play when you are computing
> and SVD...
>
> A = U * S * VT
>
> ... because U is actually the eigenvectors of (symmetric) A*AT and V
> is the eigenvectors of AT*A? And so Lanczos is used to answer those
> questions to complete the SVD?
>
> On Fri, Jun 4, 2010 at 6:48 AM, Ted Dunning <te...@gmail.com> wrote:
> > You are correct. The...
>
Re: Understanding the SVD recommender
Posted by Jake Mannix <ja...@gmail.com>.
Re: Lanczos, yes, it operates by finding V as you describe. The user is
required to do more work to recapture U. Practical reason is that the
assumption is numCols(A) = numFeatures which is much less than numRows(A) =
numTrainingSamples
On Nov 6, 2011 9:52 AM, "Sean Owen" <sr...@gmail.com> wrote:
Following up on this very old thread.
I understood all this bit, thanks, that greatly clarified.
You multiply a new user vector by V to project it into the new
"pseudo-item", reduced-dimension space.
And to get back to real items, you multiply by V's inverse, which is
its transpose.
And so you are really multiplying the user vector by V VT, which is
not a no-op, since those are truncated matrices and aren't actually
exact inverses (?)
The original paper talks about cosine similarities between users or
items in the reduced-dimension space, but, can anyone shine light on
the point of that? From the paper also, it seems like they say the
predictions are just computed as vector products as above.
Finally, separately, I'm trying to understand the Lanczos method as
part of computing an SVD. Lanczos operates on a real symmetric matrix
right? And am I right that it comes into play when you are computing
and SVD...
A = U * S * VT
... because U is actually the eigenvectors of (symmetric) A*AT and V
is the eigenvectors of AT*A? And so Lanczos is used to answer those
questions to complete the SVD?
On Fri, Jun 4, 2010 at 6:48 AM, Ted Dunning <te...@gmail.com> wrote:
> You are correct. The...
Re: Understanding the SVD recommender
Posted by Sean Owen <sr...@gmail.com>.
Following up on this very old thread.
I understood all this bit, thanks, that greatly clarified.
You multiply a new user vector by V to project it into the new
"pseudo-item", reduced-dimension space.
And to get back to real items, you multiply by V's inverse, which is
its transpose.
And so you are really multiplying the user vector by V VT, which is
not a no-op, since those are truncated matrices and aren't actually
exact inverses (?)
The original paper talks about cosine similarities between users or
items in the reduced-dimension space, but, can anyone shine light on
the point of that? From the paper also, it seems like they say the
predictions are just computed as vector products as above.
Finally, separately, I'm trying to understand the Lanczos method as
part of computing an SVD. Lanczos operates on a real symmetric matrix
right? And am I right that it comes into play when you are computing
and SVD...
A = U * S * VT
... because U is actually the eigenvectors of (symmetric) A*AT and V
is the eigenvectors of AT*A? And so Lanczos is used to answer those
questions to complete the SVD?
On Fri, Jun 4, 2010 at 6:48 AM, Ted Dunning <te...@gmail.com> wrote:
> You are correct. The paper has an appalling treatment of the folding in
> approach.
>
> In fact, the procedure is dead simple.
>
> The basic idea is to leave the coordinate system derived in the original SVD
> intact and simply project the new users into that space.
>
> The easiest way to see what is happening is to start again with the original
> rating matrix A as decomposed:
>
> A = U S V'
>
> where A is users x items. If we multiply on the right by V, we get
>
> A V = U S V' V = U S
>
> (because V' V = I, by definition). This result is (users x items) x (items
> x k) = users x k, that is, it gives a k dimensional vector for each user.
> Similarly, multiplication on the left by U' gives a k x items matrix which,
> when transposed gives a k dimensional vector for each item.
>
> This implies that if we augment U with new user row vectors U_new, we should
> be able to simply compute new k-dimensional vectors for the new users and
> adjoin these new vectors to the previous vectors. Concisely put,
>
> ( A ) ( A V )
> ( ) V = ( )
> ( A_new ) ( A_new V )
>
> This isn't really magical. It just says that we can compute new user
> vectors at any time by multiplying the new users' ratings by V.
>
> The diagram in figure one is hideously confusing because it looks like a
> picture of some kind of multiplication whereas it is really depicting some
> odd kind of flow diagram.
>
> Does this solve the problem?
>
> On Thu, Jun 3, 2010 at 9:26 AM, Sean Owen <sr...@gmail.com> wrote:
>
>> Section 3 is hard to understand.
>>
>> - Ak and P are defined, but not used later
>> - Definition of P has UTk x Nu as a computation. UTk is a k x m
>> matrix, and Nu is "t" x 1. t is not defined.
>> - This only makes sense if t = m. But m is the number of users, and Nu
>> is a user vector, so should have a number of elements equal to n, the
>> number of items
>> - Sk * VTk is described as a k x "d" matrix but d is undefined
>> - The diagram suggests that VTk are multiplied by all the Nu, which
>> makes more sense -- but only if Nu are multiplied by VTk, not the
>> other way. And the diagram depicts neither of those.
>> - Conceptually I would understand Nu x VTk, but then P is defined by
>> an additional product with Uk
>>
>> In short... what?
>>
>>
>> On Thu, Jun 3, 2010 at 4:15 PM, Ted Dunning <te...@gmail.com> wrote:
>> > Fire away.
>> >
>> > On Thu, Jun 3, 2010 at 3:52 AM, Sean Owen <sr...@gmail.com> wrote:
>> >
>> >> Is anyone out there familiar enough with this to a) discuss this paper
>> >> with me or b) point me to another writeup on the approach?
>> >>
>> >
>>
>
Re: Understanding the SVD recommender
Posted by Ted Dunning <te...@gmail.com>.
You are correct. The paper has an appalling treatment of the folding in
approach.
In fact, the procedure is dead simple.
The basic idea is to leave the coordinate system derived in the original SVD
intact and simply project the new users into that space.
The easiest way to see what is happening is to start again with the original
rating matrix A as decomposed:
A = U S V'
where A is users x items. If we multiply on the right by V, we get
A V = U S V' V = U S
(because V' V = I, by definition). This result is (users x items) x (items
x k) = users x k, that is, it gives a k dimensional vector for each user.
Similarly, multiplication on the left by U' gives a k x items matrix which,
when transposed gives a k dimensional vector for each item.
This implies that if we augment U with new user row vectors U_new, we should
be able to simply compute new k-dimensional vectors for the new users and
adjoin these new vectors to the previous vectors. Concisely put,
( A ) ( A V )
( ) V = ( )
( A_new ) ( A_new V )
This isn't really magical. It just says that we can compute new user
vectors at any time by multiplying the new users' ratings by V.
The diagram in figure one is hideously confusing because it looks like a
picture of some kind of multiplication whereas it is really depicting some
odd kind of flow diagram.
Does this solve the problem?
On Thu, Jun 3, 2010 at 9:26 AM, Sean Owen <sr...@gmail.com> wrote:
> Section 3 is hard to understand.
>
> - Ak and P are defined, but not used later
> - Definition of P has UTk x Nu as a computation. UTk is a k x m
> matrix, and Nu is "t" x 1. t is not defined.
> - This only makes sense if t = m. But m is the number of users, and Nu
> is a user vector, so should have a number of elements equal to n, the
> number of items
> - Sk * VTk is described as a k x "d" matrix but d is undefined
> - The diagram suggests that VTk are multiplied by all the Nu, which
> makes more sense -- but only if Nu are multiplied by VTk, not the
> other way. And the diagram depicts neither of those.
> - Conceptually I would understand Nu x VTk, but then P is defined by
> an additional product with Uk
>
> In short... what?
>
>
> On Thu, Jun 3, 2010 at 4:15 PM, Ted Dunning <te...@gmail.com> wrote:
> > Fire away.
> >
> > On Thu, Jun 3, 2010 at 3:52 AM, Sean Owen <sr...@gmail.com> wrote:
> >
> >> Is anyone out there familiar enough with this to a) discuss this paper
> >> with me or b) point me to another writeup on the approach?
> >>
> >
>
Re: Understanding the SVD recommender
Posted by Sean Owen <sr...@gmail.com>.
Section 3 is hard to understand.
- Ak and P are defined, but not used later
- Definition of P has UTk x Nu as a computation. UTk is a k x m
matrix, and Nu is "t" x 1. t is not defined.
- This only makes sense if t = m. But m is the number of users, and Nu
is a user vector, so should have a number of elements equal to n, the
number of items
- Sk * VTk is described as a k x "d" matrix but d is undefined
- The diagram suggests that VTk are multiplied by all the Nu, which
makes more sense -- but only if Nu are multiplied by VTk, not the
other way. And the diagram depicts neither of those.
- Conceptually I would understand Nu x VTk, but then P is defined by
an additional product with Uk
In short... what?
On Thu, Jun 3, 2010 at 4:15 PM, Ted Dunning <te...@gmail.com> wrote:
> Fire away.
>
> On Thu, Jun 3, 2010 at 3:52 AM, Sean Owen <sr...@gmail.com> wrote:
>
>> Is anyone out there familiar enough with this to a) discuss this paper
>> with me or b) point me to another writeup on the approach?
>>
>
Re: Understanding the SVD recommender
Posted by Ted Dunning <te...@gmail.com>.
Fire away.
On Thu, Jun 3, 2010 at 3:52 AM, Sean Owen <sr...@gmail.com> wrote:
> Is anyone out there familiar enough with this to a) discuss this paper
> with me or b) point me to another writeup on the approach?
>