Tagging and recommendation algorithms on hypergraphs
Creators: name: Πλιάκος, Κωνσταντίνος Γεωργίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2015
Subjects: Υπεργραφήματα
Επισημείωση εικόνων
Υπόδειξη εικόνων
Hypergraphs
Image tagging
Image recommendation

description: Nowadays, the continuously rising popularity of photo-sharing web applications has led to a huge amount of uploaded images. This boundless volume of image data has triggered the interest in image tagging and recommendation. The image tagging is a very critical procedure, as it is responsible for search engine retrieval accuracy and contributes to the organization of the images uploaded to the web. It aims at bridging the gap between the semantic and visual content of an image. However, it suffers from several limitations, such as spam, lack of uniformity, and noise. Therefore, an effective tagging system is of paramount importance. Recently, besides tagging, much progress has been made toward developing new recommender systems. Recommender systems typically produce a list of recommendations through collaborative or content-based filtering. They are a useful alternative to search algorithms since they provide users with items they might not have found by themselves. However, achieving satisfactory efficiency or accuracy remains still an open problem. The main goal of this master thesis is to develop methods in order to address effectively image tagging and recommendation. The proposed methods are based on hypergraph learning. The hypergraph theory is among the research areas of study that have both considerable theoretical interest and an important range of practical applications. Text information distilled from image tags, social media information, and image visual content are exploited, modeling relations between the images in a unified hypergraph framework. Moreover, the hypergraph learning is enhanced by applying an updating hyperedge weight tuning scheme. This way, the information is distilled as each hyperedge of the unified hypergraph is treated in a different manner. The proposed methods are based on thorough mathematical analyses which are presented in this master thesis in full detail. Experiments were conducted and satisfactory results were presented, demonstrating the efficiency of the proposed methods.
description: Στα πλαίσια της παρούσας διπλωματικής εργασίας η προσέγγιση που ακολουθήθηκε για την ανάπτυξη συστημάτων υπόδειξης και επισημείωσης εικόνων βασίστηκε κυρίως στη χρήση υπεργραφημάτων και πιθανοτικών μοντέλων που προέρχονται από τη θεωρία των μοντέλων διανυσματικού χώρου. Toυπεργράφημα θεωρείται μία επέκταση του απλού γραφήματος. Αποτελείται από κόμβους που αντιστοιχούν σε αντικείμενα-οντότητες του προβλήματος και από υπερακμές που συνδέουν τους κόμβους αυτούς. Η βασική διαφορά του υπεργραφήματος με το απλό γράφημα βρίσκεται στο γεγονός ότι οι υπερακμές ενός υπεργραφήματος μπορούν να συνδέσουν περισσότερους από δύο κόμβους. Έτσι, συσχετίσεις μεταξύ τριάδων μπορούν να αναπαρασταθούν. Η πληροφορία που χρησιμοποιήθηκε προέρχεται από το οπτικό περιεχόμενο των εικόνων, τα μεταδεδομένα αυτών και τις σχέσεις των χρηστών στο διαδίκτυο (φιλίες, ομάδες). Η μέθοδος εκμάθησης με χρήση υπεργραφημάτων αποτελείται από 2 στάδια. Στο πρώτο, κατασκευάζεται το υπεργράφημα το οποίο εμπερικλείει τα δεδομένα και τις σχέσεις μεταξύ τους. Έπειτα, υπολογίζεται ο πίνακας που αποτελεί ένα μέτρο σχετικότητας μεταξύ των δεδομένων, τα οποία αναφέρονται ως αντικείμενα στο πρόβλημα. Στο σημείο αυτό, το πρόβλημα της επισημείωσης ή πρότασης εικόνων αντιμετωπίζεται σαν ένα πρόβλημα κατάταξης σε υπεργραφήματα.Επιπλέον, προτείνονται μέθοδοι βελτίωσης των αποτελεσμάτων μέσω της ανανέωσης των τιμών που δίνονται στα βάρη των υπερακμών των υπεργραφημάτων. Με αυτόν τον τρόπο, η πληροφορία διυλίζεται και κάθε υπερακμή αντιμετωπίζεται διαφορετικά στο πρόβλημα βελτιστοποίησης. Για την ανανέωση των βαρών προτείνονται επαναληπτικοί αλγόριθμοι των οποίων η μαθηματική ανάλυση παρουσιάζεται πλήρως. Οι αλγόριθμοι αυτοί βασίζονται στην επίλυση προβλημάτων βελτιστοποίησης με έναν ή και περισσότερους περιορισμούς ισότητας και ανισότητας.Στην παρούσα διπλωματική εργασία επίσης προτείνεται ένα καινοτόμο και ακριβές σύστημα επισημείωσης εικόνων και υπόδειξης τουριστικών σημείων ενδιαφέροντος. Για την υλοποίηση αυτού του συστήματος, αρχικά οι εικόνες με γεω-πληροφορία ομαδοποιούνται με βάση τις γεωγραφικές τους συντεταγμένες. Τα γεωγραφικά σύνολα που περιέχουν στο εσωτερικό τους τις περισσότερες εικόνες θεωρούνται ως μέρη τουριστικής. Η σημασιολογική επισημείωση των εικόνων βασίζεται στην μέθοδο PLSA και συμπληρώνεται με την εκμετάλλευση του οπτικού περιεχομένου των εικόνων. Η οπτική επισημείωση των εικόνων βασίζεται στην ταξινόμηση των εικόνων σε διάφορες κλάσεις. Για την επίτευξη αυτού χρησιμοποιήθηκε η μέθοδος των μηχανών εδραίων διανυσμάτων (SupportVectorMachines, SVMs) τροφοδοτούμενη από διανύσματα περιγραφής τύπου GIST. Όσο αφορά την υπόδειξη σημείων τουριστικού ενδιαφέροντος, αυτή βασίζεται στη μέθοδο εκμάθησης με χρήση υπεργραφημάτων και πιο συγκεκριμένα αντιμετωπίζεται ως ένα πρόβλημα κατάταξης με χρήση υπεργραφημάτων. Επίσης, προτείνεται για την βελτίωση των αποτελεσμάτων η εισαγωγή περιορισμών ομαδικής φειδούς (groupsparsity) και συγκεκριμένα εφαρμόζεται η μέθοδος ομαδικής ελάχιστης απόλυτης συρρίκνωσης και τελεστή επιλογής (groupLeastAbsoluteShrinkageandSelectionOperator, group LASSO). Με αυτόν τον τρόπο γίνεται πλήρως εκμετάλλευση της δομής των δεδομένων. Επιπλέον, στα πλαίσια της διπλωματικής προτείνεται η εφαρμογή του γρήγορου επαναληπτικού αλγόριθμου κατωφλίωσης της συρρίκνωσης (FastIterativeShrinkageThresholdingAlgorithm, FISTA). Με την εφαρμογή του αλγορίθμου αυτού επιτυγχάνεται σημαντικότατη αύξηση της ταχύτητας σύγκλισης που οδηγεί στην γρηγορότερη επίλυση του προβλήματος βελτιστοποίησης.