On Thu, Jul 18, 2013 at 10:00 PM, Dmitriy Lyubimov dlie...@gmail.comwrote:
btw Mahout's qr seems to garble the input argument matrix so it is unusable
after that. It doesn't seem to document so and intuitively that's not
what one expects. Took me quite a while to figure today where the stuff
On Thu, Apr 4, 2013 at 3:11 PM, Ted Dunning ted.dunn...@gmail.com wrote:
On Thu, Apr 4, 2013 at 4:16 PM, Koobas koo...@gmail.com wrote:
The Mahout QR that I whipped up a couple of months ago is not rank
revealing, but it is pretty easy to convert the Gram-Schmidt algorithm
to
be such.
On Thu, Jul 18, 2013 at 3:35 PM, Dmitriy Lyubimov dlie...@gmail.com wrote:
It is hard to frame HH in a row major fashion. I might be able to figure
out a Given's rotation method that is row oriented.
Mahout SSVD already has the row-wise Givens rotation solver . I guess i can
revive that
it's fast though and doesn't require forming the whole input in memory.
btw Mahout's qr seems to garble the input argument matrix so it is unusable
after that. It doesn't seem to document so and intuitively that's not
what one expects. Took me quite a while to figure today where the stuff
went
PS I think the issue is really more like this, after some more testing.
When lambda (overfitting parameter) is high, the X and Y in the
factorization A = X*Y' are forced to have a small (frobenius) norm.
They underfit A, potentially a lot, if lambda is high; the values of A
are always small and
Okay, it sheds some light on the problem.
Thanks for sharing.
On Mon, Apr 8, 2013 at 4:33 AM, Sean Owen sro...@gmail.com wrote:
PS I think the issue is really more like this, after some more testing.
When lambda (overfitting parameter) is high, the X and Y in the
factorization A = X*Y' are
Oh, I thought you were stil referring to the toy example in this
thread. Yes, k=10 is definitely larger than its rank. This is why I
said Y'*Y is certainly not invertible in this case. I was responding
to you showing that ALS still worked -- indeed it does but it never
inverts / solves a system
On Fri, Apr 5, 2013 at 8:07 AM, Sean Owen sro...@gmail.com wrote:
OK yes you're on to something here. I should clarify. Koobas you are
right that the ALS algorithm itself is fine here as far as my
knowledge takes me. The thing it inverts to solve for a row of X is
something like (Y' * Cu * Y
For example, here's Y:
Y =
-0.278098 -0.256438 0.127559 -0.045869 -0.769172 -0.255599
0.150450 -0.436548 0.209881 -0.526238
0.613175 -0.600739 -0.291662 -1.142282 0.277204 -0.296846
-0.175122 0.031656 -0.202138 -0.254480
-0.187816 -0.889571 0.052191 -0.304053
Okay, you do have a problem.
Y'*Y is 10x10, but it's rank is 5.
Has to have something to do with the input data.
On Sat, Apr 6, 2013 at 7:47 PM, Sean Owen sro...@gmail.com wrote:
For example, here's Y:
Y =
-0.278098 -0.256438 0.127559 -0.045869 -0.769172 -0.255599
0.150450
(On this aside -- the Commons Math version uses Householder
reflections but operates on a transposed representation for just this
reason.)
On Thu, Apr 4, 2013 at 11:11 PM, Ted Dunning ted.dunn...@gmail.com wrote:
But then I started trying to build a HH version using vector ops and
realized
OK yes you're on to something here. I should clarify. Koobas you are
right that the ALS algorithm itself is fine here as far as my
knowledge takes me. The thing it inverts to solve for a row of X is
something like (Y' * Cu * Y + lambda * I). No problem there, and
indeed I see why the
Let me try to wrap my head around it
On Fri, Apr 5, 2013 at 8:07 AM, Sean Owen sro...@gmail.com wrote:
OK yes you're on to something here. I should clarify. Koobas you are
right that the ALS algorithm itself is fine here as far as my
knowledge takes me. The thing it inverts to solve
This is more of a linear algebra question, but I thought it worth
posing to the group --
As part of a process like ALS, you solve a system like A = X * Y' for
X or for Y, given the other two. A is sparse (m x n); X and Y are tall
and skinny (m x k, m x n, where k m,n)
For example to solve for
Typically, to deal with this kind of problem, you need to follow one of two
courses.
First, you can use a so-called rank-revealing QR which uses a pivoting
strategy to push all of the small elements of R as far down the diagonal as
possible. This gives you a reliable way of finding the problems
On Thu, Apr 4, 2013 at 9:13 AM, Ted Dunning ted.dunn...@gmail.com wrote:
Typically, to deal with this kind of problem, you need to follow one of two
courses.
First, you can use a so-called rank-revealing QR which uses a pivoting
strategy to push all of the small elements of R as far down the
On Thu, Apr 4, 2013 at 9:36 AM, Sean Owen sro...@gmail.com wrote:
Yeah I've got the pivoting part down -- I think. The problem is that I
can't seem to identify the problem by simple thresholding. For
example, a diagonal like 10 9 8 0.0001 0.001 obviously has a
problem. But so might 100 90
I think that's what I'm saying, yes. Small rows X shouldn't become
large rows of A -- and similarly small changes in X shouldn't mean
large changes in A. Not quite the same thing but both are relevant. I
see that this is just the ratio of largest and smallest singular
values. Is there established
I have a feeling, it is a problem with the ALS algorithm.
Unlike in SVD, you're not getting orthogonal vectors.
So, X and Y matrices can be rank-deficient.
Then, multiplying X (or Y) by its transpose, squares the condition number.
In other words, you can probably make an SVD of A and get k nice
For what it's worth, here's what I remember from my Numerical Analysis
course.
The thing we were taught to use to figure out whether the matrix is ill
conditioned is the condition number of a matrix (k(A) = norm(A) *
norm(A^-1)). Here's a nice explanation of it [1].
Suppose you want to solve Ax
Just to throw another bit.
Just like Ted was saying.
If you take the largest singular value over the smallest singular value,
you get your condition number.
If it turns out to be 10^16, then you're loosing all the digits of double
precision accuracy,
meaning that your solver is nothing more than a
I took Movie Lens 100K data without ratings and ran non-weighted ALS in
Matlab.
I set number of features k=2000, which is larger than the input matrix
(1000 x 1700).
I used QR to do the inversion.
It runs without problems.
Can you share your data?
On Thu, Apr 4, 2013 at 1:10 PM, Koobas
Does it complete without problems? It may complete without error but
the result may be garbage. The matrix that's inverted is not going to
be singular due to round-off. Even if it's not you may find that the
resulting vectors are infinite or very large. In particular I at least
had to make the
On Thu, Apr 4, 2013 at 2:23 PM, Sean Owen sro...@gmail.com wrote:
Does it complete without problems? It may complete without error but
the result may be garbage. The matrix that's inverted is not going to
be singular due to round-off. Even if it's not you may find that the
resulting vectors
No major problems:
A =
1 4 3 0 0
0 0 3 0 0
0 4 0 3 2
5 0 2 0 3
0 0 0 5 0
2 4 0 0 0
XY =
0.96053.46712.42660.05420.1976
0.16380.0900
k was 10
On Thu, Apr 4, 2013 at 3:37 PM, Koobas koo...@gmail.com wrote:
No major problems:
A =
1 4 3 0 0
0 0 3 0 0
0 4 0 3 2
5 0 2 0 3
0 0 0 5 0
2 4 0 0 0
Sorry, the image was off.
This is more like it:
[image: Inline image 1]
On Thu, Apr 4, 2013 at 3:38 PM, Koobas koo...@gmail.com wrote:
k was 10
On Thu, Apr 4, 2013 at 3:37 PM, Koobas koo...@gmail.com wrote:
No major problems:
A =
1 4 3 0 0
0 0 3
It's done in one iteration.
This is the R from QR factorization:
5.06635.81224.97044.39876.34004.59705.0334
4.25813.38085.3250
02.40361.17222.32961.65800.45751.1706
2.10401.67381.4839
0 01.5085
BTW, my initialization of X and Y is simply random:
X = rand(m,k);
Y = rand(k,n);
On Thu, Apr 4, 2013 at 3:51 PM, Koobas koo...@gmail.com wrote:
It's done in one iteration.
This is the R from QR factorization:
5.06635.81224.97044.39876.34004.59705.0334
4.2581
On Thu, Apr 4, 2013 at 4:16 PM, Koobas koo...@gmail.com wrote:
The Mahout QR that I whipped up a couple of months ago is not rank
revealing, but it is pretty easy to convert the Gram-Schmidt algorithm to
be such. The SVD we have should work just fine.
Mahout QR uses Gram-Schmidt?
It might make a difference that you're just running 1 iteration. Normally
it's run to 'convergence' -- or here let's say, 10+ iterations to be safe.
This is the QR factorization of Y' * Y at the finish? This seems like it
can't be right... Y has only 5 vectors in 10 dimensions and Y' * Y is
The classic poorly conditioned matrix is Hilbert's.
a_ij = 1/(i+j+1) (for zero-based matrices)
or
a_ij = 1/(i+j-1) (for one-based matrices such as in R)
This matrix looks quite fine, but the inverse shows up factorial size
values. Here, for instance, is the inverse of H_5:
Makes perfect sense.
Thanks for the explanation.
On Thu, Apr 4, 2013 at 6:11 PM, Ted Dunning ted.dunn...@gmail.com wrote:
On Thu, Apr 4, 2013 at 4:16 PM, Koobas koo...@gmail.com wrote:
The Mahout QR that I whipped up a couple of months ago is not rank
revealing, but it is pretty easy
On Thu, Apr 4, 2013 at 6:19 PM, Sean Owen sro...@gmail.com wrote:
It might make a difference that you're just running 1 iteration. Normally
it's run to 'convergence' -- or here let's say, 10+ iterations to be safe.
I did not just run one iteration.
I ran 10.
But the other 9 had no effect on
On Fri, Apr 5, 2013 at 2:40 AM, Koobas koo...@gmail.com wrote:
Anyways, I saw no particular reason for the method to fail with k
approaching or exceeding m and n.
It does if there is no regularization.
But with regularization in place, k can be pretty much anything.
Ahh... this is an
35 matches
Mail list logo
