Evaluating the Accuracy and Utility of Recommender Systems vorgelegt von Master of Science Alan Said Von der Fakult¨at IV – Elektrotechnik und Informatik – der Technischen Universit¨at Berlin zur Erlangung des akademischen Grades Doktor der Ingenieurwissenschaften – Dr.-Ing. – genehmigte Dissertation Promotionsausschuss: Vorsitzender: Prof. Dr. Mu¨ller Berichter: Prof. Dr. Albayrak Berichter: Prof. Dr. Cremonesi Berichter: Dr. Jain Tag der wissenschaftlichen Aussprache: 21. M¨arz 2013 Berlin 2013 D 83 Evaluating the Accuracy and Util- ity of Recommender Systems Thesis for the Degree Doktor der Ingenieurwissenschaften Alan Said Fakulta¨t Elektrotechnik und Informatik TECHNISCHE UNIVERSITA¨T BERLIN Berlin Germany, 2013 Evaluating the Accuracy and Utility of Recommender Systems ALAN SAID (cid:13)cALAN SAID, 2013 Review Committee Chairperson: Prof. Klaus-Robert Mu¨ller Reviewer: Prof. Sahin Albayrak Reviewer: Prof. Paolo Cremonesi Reviewer: Dr. Brijnesh J. Jain Keywords: Recommender Systems, Evaluation, Collaborative Filtering, User Study ACM Categories: H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval - Information filtering, Retrieval models, Selection process; H.3.4 [Information Technology and Systems Applications]: Decision Support Fakult¨at Elektrotechnik und Informatik Technische Universit¨at Berlin Sekretariat TEL 14 Ernst-Reuter-Platz 7 D-10587 Berlin Telephone + 49 (0)30-314 74000/02 Berlin, Germany. 2013 Thisworkissubjecttocopyright. Allrightsarereserved,whetherthewholeorpartofthe materialisconcerned,specificallytherightsoftranslation,reprinting,re-useofillustrations, recitation,broadcasting,reproductiononmicrofilmsorinanyotherway,andstorageindata banks. Duplicationofthispublicationorpartsthereofispermittedonlyundertheprovisionsof theGermanCopyrightLawofSeptember9,1965,initscurrentversion,andpermissionforuse mustalwaysbeobtainedfromtheauthor. ViolationsareliabletoprosecutionundertheGerman CopyrightLaw. Evaluating the Accuracy and Utility of Recommender Systems Alan Said Berlin 2013 Technische Universit¨at Berlin DAI-Labor Fakult¨at Elektrotechnik und Informatik Sekretariat TEL 14 Ernst-Reuter-Platz 7 D-10587 Berlin Telephone +49 (0)30-314 74000/02 Abstract Recommender systems have become a ubiquitous feature on the World Wide Web. Today, mostwebsitesusesomeformofrecommendationtoheightentheir users’ experience. Over the last decade, vast advancements in recommendation have been done, this has however not been matched in the processes involved in evaluating these systems. The evaluation methods and metrics currently used for this have originated in other related fields, e.g. information retrieval, statistics, etc. For most cases, these evaluation processes are able to show how well a recommender system performs – to some point. However, after a certain threshold, it is not often clear whether a lower error, or higher accuracy metric accounts for an actual quality improvement. This dissertation focuses on the research question how can we further estimate whether a measured accuracy level actually corresponds to a quality improve- ment from the user’s perspective, or whether the measured improvement is lost on the end user. We introduce some of the concepts related to recommen- dation quality and user perception, and continue on to show that currently widely-used evaluation metrics do not capture the quality of recommendation when the algorithm is specifically tuned to offer recommendation of a higher diversity. Following this we present a formalization of the upper limit of rec- ommendation quality, a magic barrier of recommendation, and evaluate it in a real-world movie recommendation setting. Theworkpresentedinthisdissertationconcludesthatcurrentrecommendation quality has outgrown the methods and metrics used for the evaluation of these systems. Instead, we show how qualitative approaches can be used, with mini- maluserinterference,tocorrectlyestimatetheactualqualityofrecommendation systems. i Zusammenfassung Empfehlungssystemesindheutzutageeinallgegenw¨artigerBestandteildesWorld Wide Web. Viele Webseiten nutzen Empfehlungssysteme, um Benutzerfre- undlichkeit und das Nutzererlebnis zu verbessern. W¨ahrend der letzten zehn JahrewurdenvieleFortschritteinderForschungzuEmpfehlungssystemengemacht, allerdings haben die Methoden zur Evaluierung damit nicht Schritt gehalten. DieMethodenundMetrikenzurEvaluation,diederzeitverwendetwerden,sind indenmeistenF¨allenvonanderen,verwandten,Forschungsrichtungwiez.B.In- formationRetrievaloderStatistik,adaptiert. BiszueinemgewissenGradklappt dieses Vorgehen auch. Mit den aktuell verwendeten Evaluationsverfahren kann man bewerten, ob eine neue Methode generell funktioniert oder nicht. Man kann allerdings nicht bewerten, ob Verbesserungen wie ein niedrigerer Fehler oder eine verbesserte Genauigkeit in der realen Anwendung wirklich zu einer verbessertenBenutzerfreundlichkeitodereinembesserenNutzererlebnisfu¨hren. Diese Arbeit besch¨aftigt haupts¨achlich sich mit der Frage, wie man die Evalua- tionverbessernkann,umbesserVorhersagenmachenzuk¨onnen,obVerbesserun- gen eines neuen Empfehlungsalgorithmus auch beim Nutzer ankommen. WirbenenneneinigederwichtigstenKonzepteimZusammenhangmitderEmp- fehlungsqualit¨at und Nutzerwahrnehmung und zeigen dann, dass die derzeit genutzten Evaluationsverfahren nicht die Qualit¨at von Empfehlung erfassen, wenn der Algorithmus speziell auf Empfehlungen mit h¨oherer Diversit¨at aus- gelegt ist. Danach pr¨asentieren wir eine Formalisierung der Magic Barrier, einer oberen Grenze fu¨r die beste erreichbare Empfehlungsqualit¨at aufgrund vonfehlerhaftenoderschwammigenNutzerfeedbacks. WirevaluierendieMagic Barrier mittels einer Nutzerstudie, in einer Anwendung zu Filmempfehlungen iii mit realen Nutzer und Daten. Die in dieser Dissertation pr¨asentierten Ergebnisse fu¨hren zu dem Schluss, dass die aktuell verwendeten Evaluierungsmethoden und Metriken nicht Schritt hal- ten mit aktuellen Ergebnissen in der Forschung zu Empfehlungsalgorithmen und der erreichten Qualit¨at. Daraus folgend, werden im Rahmen der Arbeit qualitative Ans¨atze und deren Anwendung beschrieben, die bei minimaler Ein- bindung des Nutzers, den tats¨achlichen Nutzen eines Empfehlungsalgorithmus einsch¨atzen k¨onnen. iv