Latest Comments
Search
« I see | Main | Moving Away »

Partially-Observed "Singular Value Decomposition"

Singular Value Decomposition is a fanastic linear algebra operation which factorizes a matrix - that is, for a matrix M, it returns U, S, V such that M = U * S * V'. This can be viewed as a basis transformation from row space to column space. The main problem is that standard SVD requires a completely-observed matrix M, that is, all values of M are known.

SVD has been shown to work surprisingly well for collaborative filtering applications such as the netflix prize. However, in such problems, the matrix is usually partially-observed, or in other words, some entries of M are not known. The "simple" workaround has been to perform gradient descent in U and V to minimize the objective function:

f = \sum_{i=1}^N \sum_{j \in N(i)} (u_i * v_j' - M_{ij})^2 + \lambda \sum_{ij} ( ||u_i||^2 + ||v_j||^2 )

where N(i) are the observed entries in row i. This breaks down to the updates:

\delta_{ij} = u_i * v_j' - M_{ij}
u_{ik} = u_{ik} + \alpha( \delta_{ij} v_{jk} - \lambda u_{ik} )
v_{jk} = v_{jk} + \alpha( \delta_{ij} u_{ik} - \lambda v_{jk} )

Since we only work with known values of M, this simply avoids the requirement of M being completely-observed.

I am hoping to use this simple technique to perform data mining in other similar problems where "collaborative filtering" is assumed but tedious to compute - e.g., medical data where you have tons of clinical measurements and information about patients, together with a set of diagnosis. So given a set of patient info and clinical measurements, can you predict the diagnosis? Casting this information into a partially-observed matrix M is fairly simple, and I am having moderate success. Nevertheless, I would prefer to have Bayesian belief networks to incorporate some prior knowledge into a structured model.

Reader Comments

There are no comments for this journal entry. To create a new comment, use the form below.

PostPost a New Comment

Enter your information below to add a new comment.

My response is on my own website »
Author Email (optional):
Author URL (optional):
Post:
 
Some HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>