Abstract:

The singular value decomposition (SVD) is fundamental to many data modeling/mining algorithms, but SVD algorithms typically have quadratic complexity and require random access to complete data sets. This is problematic in most data mining settings. We detail a family of sequential update rules for adding data to a "thin" SVD data model, revising or removing data already incorporated into the model, and adjusting the model when the data-generating process exhibits nonstationarity. We also leverage the SVD to estimate the most probable completion of incomplete data. We use these methods to model data streams describing tables of consumer/product ratings, where fragments of rows and columns arrive in random order and individual table entries are arbitrarily added, revised, or retracted at any time. These purely online rules have very low time complexity and require a data stream cache no larger than a single user's ratings. We demonstrate this scheme in an interactive graphical movie recommender that predicts and displays ratings/rankings of thousands of movie titles in real-time as a user adjusts ratings of a small arbitrary set of probe movies. The system "learns" as it is used by revising the SVD in response to user ratings. Users can asynchronously join, add ratings, add movies, revise ratings, get recommendations, and delete themselves from the model.