1

I have implemented the SVD algortihm for my Node.js project for collaborative filtering of a sparse dataset based on this paper by GroupLens.

For calculating the SVD, I am using the package node-svd which is basically an implementation of SVDLIBC for Node.js. An advantage of this library is that it takes the number of desired dimensions as a parameter.

How do I verify that I have translated the instructions correctly into code? I can post it here if needed.

For testing, I am comparing the original sparse matrix (from the MovieLens 100K dataset) with the predictions (comparing values that are existing in the original only) and then calculating the RMSE. Is this the correct way to do so? Or is there another way I can efficiently test my implementation?

akashg
  • 111
  • 6

1 Answers1

2

It's not completely clear what the output of your code will be in this case.

The Singular Value Decomposition of a real-valued $m$ x $n$ matrix M is a factorisation of the form

M = U D V'

where U is $m$ x $m$, D is $m$ x $n$ and V is $n$ x $n$. The diagonal entries {$d_{ii}$} of D are the "singular values" of M. If your code provides U,D and V as output, you need only multiply them as shown and check that the original matrix is reconstructed. Presumably you would not be asking if that were the case. But perhaps they are available from the library you are using?

Alternatively, you might try finding some other software that preforms SVD and match your results against that. Using R, for example, help for the function svd() (see ?svd) will provides the following example decomposing a Hilbert matrix X:

hilbert <- function(n) { i <- 1:n; 1 / outer(i - 1, i, "+") }

(X <- hilbert(9)[, 1:6])

           [,1]      [,2]       [,3]       [,4]       [,5]       [,6]
 [1,] 1.0000000 0.5000000 0.33333333 0.25000000 0.20000000 0.16666667
 [2,] 0.5000000 0.3333333 0.25000000 0.20000000 0.16666667 0.14285714
 [3,] 0.3333333 0.2500000 0.20000000 0.16666667 0.14285714 0.12500000
 [4,] 0.2500000 0.2000000 0.16666667 0.14285714 0.12500000 0.11111111
 [5,] 0.2000000 0.1666667 0.14285714 0.12500000 0.11111111 0.10000000
 [6,] 0.1666667 0.1428571 0.12500000 0.11111111 0.10000000 0.09090909
 [7,] 0.1428571 0.1250000 0.11111111 0.10000000 0.09090909 0.08333333
 [8,] 0.1250000 0.1111111 0.10000000 0.09090909 0.08333333 0.07692308
 [9,] 0.1111111 0.1000000 0.09090909 0.08333333 0.07692308 0.07142857

Taking the SVD provides the factors

 (s <- svd(X))

$d
[1] 1.668433e+00 2.773727e-01 2.223722e-02 1.084693e-03 3.243788e-05
[6] 5.234864e-07

$u
            [,1]       [,2]        [,3]        [,4]        [,5]        [,6]
 [1,] -0.7244999  0.6265620  0.27350003 -0.08526902  0.02074121 -0.00402455
 [2,] -0.4281556 -0.1298781 -0.64293597  0.55047428 -0.27253421  0.09281592
 [3,] -0.3121985 -0.2803679 -0.33633240 -0.31418014  0.61632113 -0.44090375
 [4,] -0.2478932 -0.3141885 -0.06931246 -0.44667149  0.02945426  0.53011986
 [5,] -0.2063780 -0.3140734  0.10786005 -0.30241655 -0.35566839  0.23703838
 [6,] -0.1771408 -0.3026808  0.22105904 -0.09041508 -0.38878613 -0.26044927
 [7,] -0.1553452 -0.2877310  0.29280775  0.11551327 -0.19285565 -0.42094482
 [8,] -0.1384280 -0.2721599  0.33783778  0.29312535  0.11633231 -0.16079025
 [9,] -0.1248940 -0.2571250  0.36542543  0.43884649  0.46496714  0.43459954

$v
           [,1]       [,2]       [,3]        [,4]        [,5]         [,6]
[1,] -0.7364928  0.6225002  0.2550021 -0.06976287  0.01328234 -0.001588146
[2,] -0.4432826 -0.1818705 -0.6866860  0.50860089 -0.19626669  0.041116974
[3,] -0.3274789 -0.3508553 -0.2611139 -0.50473697  0.61605641 -0.259215626
[4,] -0.2626469 -0.3921783  0.1043599 -0.43747940 -0.40833605  0.638901622
[5,] -0.2204199 -0.3945644  0.3509658  0.01612426 -0.46427916 -0.675826789
[6,] -0.1904420 -0.3831871  0.5110654  0.53856351  0.44663632  0.257248908

so that the diagonal matrix D

 (D <- diag(s$d))

         [,1]      [,2]       [,3]        [,4]         [,5]         [,6]
[1,] 1.668433 0.0000000 0.00000000 0.000000000 0.000000e+00 0.000000e+00
[2,] 0.000000 0.2773727 0.00000000 0.000000000 0.000000e+00 0.000000e+00
[3,] 0.000000 0.0000000 0.02223722 0.000000000 0.000000e+00 0.000000e+00
[4,] 0.000000 0.0000000 0.00000000 0.001084693 0.000000e+00 0.000000e+00
[5,] 0.000000 0.0000000 0.00000000 0.000000000 3.243788e-05 0.000000e+00
[6,] 0.000000 0.0000000 0.00000000 0.000000000 0.000000e+00 5.234864e-07

allows reconstruction of X = U D V'

s$u %*% D %*% t(s$v) ##  X = U D V'

If your code provides only the "singular values", they should match the diagonal of D given here to within whatever tolerance seems acceptable to you.

Small test cases usually work best, until you are ready to test throughput / timing.

goangit
  • 566
  • 3
  • 12
  • 1
    Thanks for your answer. Also, is there a way to verify whether the predictions generated using the decomposed SVD are correct? – akashg Dec 10 '14 at 05:35
  • If you find the answer useful you can express that by voting rather than comments. You need to explain (possibly much) more about what you are doing to get good answers about prediction validation. It's also off-topic for the current thread label and probably deserves a new question. Thanks. – goangit Dec 10 '14 at 06:07
  • Have already voted up your answer. It seems the title of my question has been a little misleading. I should have asked how to verify the implementation of a CF system rather than just SVD. But I have mentioned in my question about verifying the predictions. – akashg Dec 10 '14 at 12:14
  • Well it seems you had two quite distinct and separable problems. The title is well targeted for the first problem and will allow future readers to find it easily. The second problem, as it stands, still needs some refinement so that people can understand what help you actually need. And if it is a separate question, will serve future readers looking for that answer, even when they don't have any interest in verifying SVD. – goangit Dec 10 '14 at 12:37