2
$\begingroup$

The idea is to motivate the SVD for use in a recommender system.

Consider a matrix $A\in \mathbb{R}^{f\times u}$ where $A_{ij}$ captures how user $j$ rates film $i$ (on a scale from 1-10, some entries may be missing).

Considering matrices $K=AA^T$, $L = A^TA$ what do $K_{ij}$ and $L_{ij}$ tell us?

What interpretations can you give for matrices $U$ and $V$ in the SVD $A=U\Sigma V^T$?

Riiight ... so

K = $AA^T$ = $U\Sigma^2U^T$, L = $A^TA = V\Sigma^2V^T$

With $K_{ij} = \langle A[i,:], A[j,:] \rangle$ being the dot product of all ratings for film $i$ with all ratings for film $j$.

Similarly, $L_{ij} = \langle A[:, i], A[:,j] \rangle$ being the dot product of all ratings from user $i$ with all ratings from user $j$.

That tells us ... what exactly? I expect it to amount to some kind of similarity measure, but beyond that, I have no idea.

As for $U$ and $V$ ... I know the first $r$ of them to be Eigenvectors of $K$ and $L$ for some $r$. I also know they're formed from bases for the row, column and nullspace of $A$, as well as for the nullspace of $A^T$.

Yet have no idea if notions like "row space", "column space" and "null space" even make sense in this context. What would they mean?

$\endgroup$
3
$\begingroup$

$K_{ij}$ describes the correlation between film $i$ and film $j$ (up to some normalization), and similarly $L_{ij}$ describes the correlation between user $i$ and user $j$. These numbers are higher if the films / users are similar and lower if not.

SVD allows you to write $A$ as a particularly nice sum of rank $1$ matrices

$$A = \sum_i u_i \sigma_i v_i^T$$

where $u_i, \sigma_i, v_i$ are the left singular vectors, the singular values, and the right singular vectors respectively. The left singular vectors are column vectors, meaning they're linear combinations of films (expressed as one-hot vectors); similarly the right singular vectors, transposed, are row vectors, meaning they're linear combinations of users. What do these linear combinations mean?

Loosely speaking, the left singular vectors are the "eigenfilms" (by analogy with eigenfaces) and the right singular vectors are the "eigenusers." They're a particularly nice (in particular, orthonormal) basis of films vs. users respectively which we can use to express films as linear combinations of eigenfilms and users as linear combinations of eigenusers in such a way that these linear combinations predict, in a particularly nice way, how much a given user likes a given film. "Particularly nice" means the eigenusers and eigenfilms come in pairs, where if $u_i$ is an eigenfilm then $v_i$ is the eigenuser who only pays attention to how much a film is like the eigenfilm $u_i$, and $\sigma_i$ is how much they like that eigenfilm.

You can see how this works as follows. Let $u$ be the one-hot vector describing some film, and let $v$ be the one-hot vector describing some user. Then the user's rating of the film is $u^T A v$. If we write $u$ and $v$ in the eigenfilm / eigenuser basis as

$$u = \sum_i a_i u_i, v = \sum_j b_j v_j$$

then we can compute that

$$u^T A v = \sum_{i, j} a_i b_j u_i^T A v_j = \sum_i a_i b_i \sigma_i$$

using the fact that $A v_j = \sigma u_j$ and that the $u_j$ form an orthonormal basis. What this means is that the amount that user $v$ likes film $u$ is completely determined by writing $v$ as a linear combination of eigenusers, writing $u$ as a linear combination of eigenfilms, checking how much each eigenuser likes the corresponding eigenfilm (that's $\sigma_i$), and adding up the results, weighted by how much user $u$ is like that eigenuser, and how much film $v$ is like that eigenfilm.

As a simple example, suppose there are only two eigenfilms - call them "action" and "romance" - such that every film is a linear combination of these, e.g. some films might have a decent amount of both, some films might have tons of action but no romance, some films might have tons of romance but no action, some films might have neither. (Some films might have negative action!) The corresponding eigenusers might be "loves action a ton" and "likes romance" - they only pay attention to how much action vs. romance a film has respectively, and "loves action a ton" is really really into action (high singular value) while "likes romance" only moderately likes romance (lower singular value).

Then you can predict how much a user will like a film by finding out 1) how much they care about action, 2) how much they care about romance, 1) how much action is in the film, 2) how much romance is in the film, and adding up all of the relevant numbers. Note that in the same way a film can have negative action, a user can care about action a negative amount.

The nicest thing that can happen here is that a small number of singular values are big and the rest are small, which means there are only a small number of eigenfilms and eigenusers that "really matter," and you can ignore the rest and still get pretty good approximations of the rating matrix.

$\endgroup$
  • $\begingroup$ Thank you. I really like your notion of "eigenfilms" and "eigenusers". $\endgroup$ – User1291 Mar 14 '17 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.