Συνεργατικά συστήματα συστάσεων με χρήση έμμεσης και άμεσης κοινωνικής πληροφορίας

Abstract

The digital revolution of the past decades has had as a direct consequence the rapid increase of the information distributed in electronic form, leading to a situation known as the information overload. Therefore, there exists an immediate need for the development of systems that can search, classify and categorize the available information. Recommender Systems have been proposed as a solution that may deal with the aforementioned problem to a certain extent. The contribution of this thesis lies in the study, development and practical application of algorithms for the most popular category of recommender systems, that of collaborative filtering, aiming at improving their performance.Recommender systems are essentially software tools used for the production of personalized recommendations for each user individually, usually in the form of ordered lists. Recommendations are in most cases items of any kind, like books, movies, music tracks and news articles, that may be useful to the users. The creation of recommendations in collaborative filtering systems is based upon the preferences of each user along with other parameters. Preferences are deduced in two ways; either directly from users (though the ratings they provide in a predefined scale) or indirectly, by the system itself.In the context of this thesis, recommendation algorithms that utilize the explicit user preferences are developed. The notion of collaboration lies in the fact that the new items recommended to a user are based on the ratings provided to them by other “similar” users. That is, collaborative filtering turns each user to the other user's predictor, thereby defining an informal social bond between them. For the exploration and the better exploitation of this kind of indirect relationships between the users, a novel recommendation algorithm is being proposed, whose structural element is a feed-forward multilayered perceptron. The choices made regarding the transfer function of the neurons of the network, the dynamic adaptation of its architecture as well as the boosted training algorithm, allow for the deep analysis of the relationships between the users that lead to the production of better recommendations.Apart form the indirect deduction of similarities and dissimilarities between the users, collaborative filtering can also be extended through the inclusion in the computations of the direct relationships their users may have, in the context of a social network. Examples of such relationships are the bonds of friendship, trust as well as the “follower” ties. Among the most widespread ways of accessing the direct social information in recommender systems is through the performance of random walks, aiming at locating influential users. In this context, a novel methodology for performing random walks in the joint network constructed from the combination of the social network and the “similarity” network (a network of ties between users, based on the ratings they have provided) is proposed. The difference to other approaches lies in the fact that the next step of the walk is not chosen uniformly at random, but a bias towards the most similar users is introduced instead.In addition to the user space, random walks may also occur in the item space. For this reason , the performance of random walks in a novel network, the item consumption network, is also proposed in this thesis. This specific network connects item-nodes with vertices whose weights depict the number of their common access patterns. This network is also personal, in the sense that it is constructed for every user, based on the items that he or she have accessed, as well as other users that are members of either his/her direct social network, or are similar to him/her or belong to both categories. Finally, the direct social relationships are exploited in yet another way in collaborative filtering systems. They constitute the basis of a new bayesian method of non-negative matrix factorization, aiming at categorizing the users in overlapping communities. The novelty of the procedure lies in the choice of the a priori distribution. While in literature a probability distribution based on the conjugate prior theory is selected, in this specific case, the exponential random graph models are used. The reason for choosing this course of action is to balance the locality of the factorization through the introduction of global network properties in the process. Additionally, in the context of the same procedure, a novel approximation method for the hyperparameters of the exponential random graph models has been developed, based on the mean field theory.In conclusion, the actual contribution of this thesis is summarized in the use of intelligent techniques in collaborative filtering recommender systems, for the processing and analysis of the direct and indirect social relationships the aforementioned systems contain. Every proposed technique has been experimentally tested in publicly available datasets that are widely used by the scientific community, while comparisons with other relevant techniques in every research field have also been performed.

Η ψηφιακή επανάσταση των προηγούμενων δεκαετιών είχε ως άμεσο αποτέλεσμα την αλματώδη αύξηση της πληροφορίας που διακινείται ηλεκτρονικά, οδηγώντας σε μια κατάσταση που είναι γνωστή ως πληροφοριακή υπερφόρτωση. Συνεπώς, υπάρχει άμεση ανάγκη για την κατασκευή συστημάτων τα οποία θα μπορούν να αναζητούν, να ταξινομούν και να κατηγοριοποιούν την διαθέσιμη πληροφορία. Τα Συστήματα Συστάσεων έχουν προταθεί ως μια λύση που μπορεί να αντιμετωπίσει σε ένα βαθμό το προαναφερθέν πρόβλημα. Η συνεισφορά της διατριβής έγκειται στη μελέτη, στην ανάπτυξη και στην πρακτική εφαρμογή αλγορίθμων για την πιο ευρύτατα διαδεδομένη κατηγορία συστημάτων συστάσεων, τα συνεργατικά συστήματα συστάσεων, με στόχο την βελτίωση της απόδοσής τους.Τα συστήματα συστάσεων είναι επί της ουσίας εργαλεία λογισμικού, τα οποία χρησιμοποιούνται για την παραγωγή εξατομικευμένων προτάσεων για κάθε χρήστη χωριστά, συνήθως υπό τη μορφή ταξινομημένων λιστών. Οι προτάσεις στην πλειοψηφία των περιπτώσεων είναι αντικείμενα οποιουδήποτε τύπου, όπως βιβλία, ταινίες, μουσικά κομμάτια και άρθρα ειδήσεων, τα οποία ενδεχομένως να φανούν χρήσιμα στους χρήστες. Η παραγωγή των προτάσεων στα συνεργατικά συστήματα συστάσεων βασίζεται στις προτιμήσεις του εκάστοτε χρήστη καθώς και σε άλλες παραμέτρους. Οι δε προτιμήσεις συνάγονται με δύο τρόπους: είτε απευθείας από τους ίδιους (κατά βάση εντός καθορισμένης αξιολογικής/βαθμολογικής κλίμακας) είτε έμμεσα από το ίδιο το σύστημα.Στο πλαίσιο της διατριβής αναπτύσσονται αλγόριθμοι παραγωγής συνεργατικών συστάσεων, οι οποίοι αξιοποιούν τις ρητά εκπεφρασμένες προτιμήσεις των χρηστών. Η έννοια της συνεργατικότητας έγκειται στο γεγονός πως τα νέα αντικείμενα που τελικά προτείνονται σε ένα χρήστη βασίζονται στις αξιολογήσεις που αυτά έχουν λάβει από άλλους "παρόμοιους" χρήστες. Δηλαδή, τα συνεργατικά συστήματα συστάσεων μετατρέπουν τον κάθε χρήστη σε "μέσο πρόβλεψης" των προτιμήσεων των άλλων, καθορίζοντας κατ' αυτόν τον τρόπο μια άτυπη μορφή κοινωνικότητας μεταξύ τους. Για την αναζήτηση και την καλύτερη αξιοποίηση αυτού του είδους των έμμεσων σχέσεων μεταξύ των χρηστών, προτείνεται ένας πρωτότυπος αλγόριθμος παραγωγής συστάσεων, δομικό στοιχείο του οποίου αποτελεί ένα πολυεπίπεδο νευρωνικό δίκτυο εμπρόσθιας τροφοδότησης. Οι επιλογές που γίνονται όσον αφορά τη συνάρτηση μεταφοράς των νευρώνων του δικτύου, της δυναμικής προσαρμογής της αρχιτεκτονικής του όπως και του ενισχυτικού αλγορίθμου εκπαίδευσής του, επιτρέπουν την σε βάθος ανάλυση των σχέσεων μεταξύ των χρηστών του που οδηγούν στην παραγωγή καλύτερων συστάσεων.Εκτός της έμμεσης συναγωγής ομοιοτήτων και διαφορών μεταξύ των χρηστών, τα συνεργατικά συστήματα συστάσεων μπορούν να επεκταθούν, συμπεριλαμβάνοντας στους υπολογισμούς τους και τις άμεσες σχέσεις που ενδεχομένως να έχουν οι χρήστες μεταξύ τους, στο πλαίσιο ενός κοινωνικού δικτύου. Παραδείγματα τέτοιων σχέσεων αποτελούν οι δεσμοί φιλίας, εμπιστοσύνης καθώς και οι δεσμοί "ακολούθων". Από τους πιο διαδεδομένους τρόπους προσπέλασης της άμεσης κοινωνικής πληροφορίας στα συνεργατικά συστήματα συστάσεων, είναι η πραγματοποίηση τυχαίων περιπάτων επάνω στα κοινωνικά δίκτυα, με στόχο την ανεύρεση χρηστών με επιρροή. Στο πλαίσιο αυτό, προτείνεται μια νέα μεθοδολογία πραγματοποίησης τυχαίων περιπάτων στο μεικτό δίκτυο που σχηματίζεται από τον συνδυασμό του κοινωνικού δικτύου και του δικτύου "ομοιότητας" (ενός δικτύου σχέσεων μεταξύ των χρηστών που προκύπτει από τις αξιολογήσεις που έχουν ήδη κάνει). Η διαφορά με άλλες αντίστοιχες μεθόδους βρίσκεται στο γεγονός ότι το επόμενο βήμα του περιπάτου δεν επιλέγεται ομοιόμορφα τυχαία, αλλά αντίθετα εισάγεται μια μεροληψία προς εκείνους τους χρήστες που είναι περισσότερο όμοιοι.Πέρα από τον χώρο των χρηστών, οι τυχαίοι περίπατοι μπορούν επίσης να πραγματοποιηθούν και στον χώρο των αντικειμένων. Για το λόγο αυτό στην παρούσα διατριβή προτείνεται η πραγματοποίηση τυχαίων περιπάτων επάνω σε ένα πρωτότυπο δίκτυο, το δίκτυο κατανάλωσης αντικειμένων. Το συγκεκριμένο δίκτυο συνδέει μεταξύ τους αντικείμενα-κόμβους με ακμές των οποίων τα βάρη αποτυπώνουν το πλήθος των κοινών τους προσπελάσεων. Είναι προσωπικό, υπό την έννοια ότι κατασκευάζεται χωριστά για κάθε χρήστη, στη βάση των αντικειμένων που έχει προσπελάσει τόσο ο ίδιος όσο και άλλοι χρήστες που εντάσσονται είτε στο άμεσο κοινωνικό του δίκτυο, είτε παρουσιάζουν κάποια ομοιότητα με αυτόν ή, τέλος, ανήκουν και στις δύο κατηγορίες. Τέλος, η άμεση κοινωνική πληροφορία που εμπεριέχεται στα συνεργατικά συστήματα συστάσεων αξιοποιείται και με έναν ακόμα τρόπο. Αποτελεί το πεδίο εφαρμογής μιας νέας μεθόδου μπεϋζιανής μη-αρνητικής παραγοντοποίησης πινάκων, με στόχο την κατηγοριοποίηση των χρηστών σε επικαλυπτόμενες κοινότητες. Η πρωτοτυπία της προσέγγισης βρίσκεται στην επιλογή της συνάρτησης της εκ των προτέρων πιθανότητας. Ενώ στη βιβλιογραφία συνηθίζεται να χρησιμοποιείται η θεωρία των συζυγών εκ των προτέρων κατανομών, στη συγκεκριμένη περίπτωση εφαρμόζονται τα μοντέλα εκθετικών τυχαίων γράφων. Ο λόγος που επιλέχθηκε αυτή η κατεύθυνση ήταν για να μετριαστεί η τοπικότητα της παραγοντοποίησης μέσω της εισαγωγής στη διαδικασία μακροσκοπικών πληροφοριών για τα υπό εξέταση δίκτυα. Επίσης, στο πλαίσιο της ίδιας διαδικασίας, αναπτύχθηκε και μια πρωτότυπη προσεγγιστική μέθοδος για τον υπολογισμό των υπερπαραμέτρων του μοντέλου των εκθετικών τυχαίων γράφων, η οποία βασίστηκε στη θεωρία του μέσου πεδίου.Συμπερασματικά, η ουσιαστική συμβολή της διατριβής συνοψίζεται στην χρήση ευφυών τεχνικών στα συνεργατικά συστήματα συστάσεων, για την επεξεργασία και ανάλυση της άμεσης και έμμεσης κοινωνικής πληροφορίας που ενυπάρχει σε αυτά. Κάθε τεχνική που αναπτύχθηκε, αξιολογήθηκε πειραματικά σε δημόσια διαθέσιμες συλλογές δεδομένων, οι οποίες χρησιμοποιούνται ευρέως από την επιστημονική κοινότητα, ενώ έγιναν και συγκρίσεις με άλλες αντίστοιχες τεχνικές στο κάθε πεδίο έρευνας.