IUI2009: A Low-Order Markov Model integrating Long-Distance Histories for Collaborative Recommender Systems

SUMMARY:

      This paper discusses a method to extract the most pertinent resources for a given user.  This is a challenge for applications in areas such as e-commerce, resource acces, web navigation, and online communities.

     One previous method, known as collaborative filtering, determines what resources to recommend based on similar users.  Resources that have been highly rated in the past by similar users are recommended to the user.  The traditional problems with this method are most calculations are done online and the context of the user is not considered.  This causes a lack of speed and accuracy.

 

Sergei Brin - Co-founder of google, famous for his data mining techniques

     One way of improving upon online collaborative filtering is to use data mining techniques.  This requires having a database of user histories to analyze.  The data is made up of a set of users(U) and a set of resources(R).

     Two techniques explained in the paper are association rules and sequential patterns.  An association rule is when one resource U1 usually leads to another resource U2 being pertinent for the user.  Thresholds are need to determine if there is an association between resources.  Association rules can contain more than just 2 resources.  Sequential patterns are similar to association rules but here the order matters.  This results in sequential patterns being more constrained than association rules.

     Another approach used in this paper is know as Markov Models.  Markov models limit the window of history that is used for data mining on the user.  A kth order Markov Model looks at k+1 history of resources.  In this paper they use a second order markov model which looks at a history size of 3.

    The final technique used in this paper is skipping.  Skipping simply means that you skip over certain resources to save either time or space.  The authors talk about several time when skipping might be applicable.

     The authors of this paper combined several of these techniques to create a Skipping Based Recommender.  In their study they investigate some of the tradeoffs between the methods to see what works best.

     The most important finding in there study was that a window size of three for their Markov model worked fastest but was least accurate.  They decide that the best solution is to calculate resources from a Markov model of three, then if there is more time, calculate pertinent resources based on higher order Markov models.


Discussion:
     
     This article was confusing at first but became very interesting after I got a better understanding of what the authors were creating.  The Skipping Based Recommender system would be very useful for a program like iTunes when they want to display songs that a user is most likely could by.  This would result in a user being more likely to buy the song resulting in increased profits. There are many programs and websites who could benefit from this sort of sytem.