טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentTelevitckiy Evgeny
SubjectRank Aggregation for Synthesis of Recommendation Lists
DepartmentDepartment of Electrical Engineering
Supervisors Professor Carmel Domshlak
Professor Yoram Moses
Full Thesis textFull thesis text - English Version


Abstract

This work is devoted to the area of recommender systems and, in particular, to some rank aggregation problems that naturally arise in the context of these applications. Specifically, we consider the connection between the recommendations' selection process and the form in which these recommendations are then presented to the users. On the one hand, a user of an e-commerce site typically provides her preferences as a (very rough) weak ordering over a small subset of all the available items. On the other hand, the recommendations selected for a user are presented to her as this or another projection of a strict ordering over the whole space of items. Aiming at bridging the gap between these two properties of the systems, we suggest and evaluate techniques for rank aggregation in this setting. In this thesis we consider a problem of rank aggregation in cold-start settings. This problem arises when only a partial information is provided by the user, yet we would like to generalize opinion of number of users to the one that represents a common opinion. This resulting ranking may be later used in order to solve various cold-start problems. We subcategorize cold-start problems into two parts: item cold-start and user cold-start. Item cold-start situations naturally arise when a new item is added to the system. We show various models that help us solving this problem and provide the most "agreeable" rank for an item about which we have no previous opinions. Alongside with well known techniques, we show some new models that are based on combining discriminative learning using SVMs and Markov-chain rank aggregation techniques. Another cold-start problem is known as the user cold-start. As the name suggests, this setting arises when a loosely-known user accesses our system. Similarly to the item cold-start, we introduce a number of models that provide approximate solutions to our problem. Here we introduce an entirely novel technique, called the Kmin approach that is based on a polynomial time algorithm we have developed for computing an optimal aggregation of an ordering with a set of constraints provided by the user. Finally, the techniques introduced and discussed throughout the thesis are evaluated on a large, publicly available data set of movie ratings. The results we obtain on it are shown to be competitive to these of the classical techniques that are known as “hard to beat" on this data.