mahout-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Lance Norskog <goks...@gmail.com>
Subject Re: Relative measure of rank
Date Mon, 13 Dec 2010 21:56:22 GMT
Ted, please blog this. No rewrites required.

On Sun, Dec 12, 2010 at 9:53 PM, Ted Dunning <ted.dunning@gmail.com> wrote:
> Ahh...
>
> In fact, dimensional reduction algorithms do not change the size of the
> matrix being approximated.  Instead, they approximate the matrix by
> considering each user and each item to have a reduced dimensional
> representation.  This is represented by the matrix product A \approx U D V'.
>  Here the user x item matrix A is approximated by user vectors U, item
> vectors V (transposed) and a diagonal weighting matrix that allows columns
> of U and V to be normalized.  If U and V have only a limited number of
> columns, then this can only be an approximation of A.  A capital sigma is
> often used instead of a D.
>
> The accuracy of the approximation is generally described in terms of the
> norm of A - U D V'.  This norm can be any of many norms.  One useful one is
> the Frobenius norm which is the sum of the squares of a matrix.  Another is
> the 2-norm which is the maximum amount that the matrix can cause a vector to
> grow.  All of the norms that involves squares like Frobenius and 2-norm are
> closely related to the squared magnitudes of the elements of D.
>
> Conceptually, a matrix A can be decomposed exactly using full dimension
> (rank) for U and V.  In this case A = U D V' so there is no
> error.  A nice thing about the singular value decomposition is that D can be
> arranged in descending magnitude and the best reduced representation is
> found by simply setting the smallest values of D to zero.  The quality of
> the reduced representation is directly related to the magnitudes of the
> missing values of D.
>
> So the answer to your question is yes.  The quality can be quantified and
> reasonably easily by simply computing a few extra elements of D and looking
> at how quickly these are decreasing.
>
> That leaves the question of how well the random projection algorithm
> approximates the idealized decomposition.  The practical answer here is that
> it almost certainly is very, very accurate.
>
> The remaining question is how well this reduced representation can be used
> to create a predictive model.  That is a MUCH harder question to answer.
>
>
> On Sun, Dec 12, 2010 at 8:33 PM, Lance Norskog <goksron@gmail.com> wrote:
>
>> Should be "scalar or vector".  I'm interested in the loss of precision
>> by dimensional reduction algorithms: matrix difference is only defined
>> for same-size matrices. So, there is no real absolute measure, just
>> relative measures that are not very useful except for certain use
>> cases.
>>
>> On Sun, Dec 12, 2010 at 7:21 PM, Ted Dunning <ted.dunning@gmail.com>
>> wrote:
>> > What do you mean by rank of a matrix?  The normal definition is the
>> number
>> > of non-zero singular values.  This
>> > doesn't sound like what you mean.
>> >
>> > What do you mean by loss of information?  If you mean how do you compare
>> an
>> > approximation of a matrix
>> > versus the original, yes there are ways of doing that, not all very
>> useful.
>> >  Norm of the difference is one example
>> > that leads to least squares formulations.
>> >
>> > Also, is there something missing from the sentence with "scalar of
>> vector"
>> > in it?
>> >
>> > On Sun, Dec 12, 2010 at 6:04 PM, Lance Norskog <goksron@gmail.com>
>> wrote:
>> >
>> >> Given a matrix reduction algorithm, how do you measure the loss of
>> >> information perpetrated by the algorithm on the poor defenseless input
>> >> matrix?
>> >> Are there algorithms to compare two matrices and get a relative rank
>> value?
>> >>
>> >> Is there a scalar of vector that describes the rank of a matrix? Then
>> >> you could just compare the two rank values.
>> >>
>> >> Is there a probabilistic approach to the problem?
>> >>
>> >> --
>> >> Lance Norskog
>> >> goksron@gmail.com
>> >>
>> >
>>
>>
>>
>> --
>> Lance Norskog
>> goksron@gmail.com
>>
>



-- 
Lance Norskog
goksron@gmail.com

Mime
View raw message