Ανάκτηση Πληροφορίας — Φεβρουάριος 2023¶
20230208_140035.jpg¶
ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ ΚΑΙ ΠΛΗΡΟΦΟΡΙΚΗΣ ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΑΣ ΑΝΑΚΤΗΣΗ ΠΛΗΡΟΦΟΡΙΑΣ ΔΙΑΡΚΕΙΑ 3:00 ώρες Σελίδες 2
ΘΕΜΑ 1 (Μονάδες 2,5)
α. Δώστε τον ορισμό του Μοντέλου Ανάκτησης Πληροφορίας και αναφέρετε τα βασικά μοντέλα ανάκτησης πληροφορίας μαζί με την αντίστοιχη κατηγοριοποίηση τους.
β. Εξηγήστε πως δουλεύει η μετρική κανονικοποιημένου εκπτωτικού σωρευτικού κέρδους (NDCG).
γ. Εξηγήστε πως το μοντέλο διανυσματικού χώρου θα μπορούσε να ενσωματώσει τεχνικές εξατομίκευσης έτσι ώστε το αποτέλεσμα (τελική ταξινομημένη λίστα κειμένων) στη διατύπωση ενός ερωτήματος να εξαρτάται και από τον χρήστη που διατύπωσε το ερώτημα.
ΘΕΜΑ 2 (Μονάδες 2,5)
α. Η διαδικασία απάντησης ενός ερωτήματος με το μοντέλο διανυσματικού χώρου βασίζεται στον υπολογισμό (με χρήση της πληροφορίας των ανεστραμμένων αρχείων) της μετρικής ομοιότητας του συνημιτόνου μεταξύ κάθε αποθηκευμένου κειμένου και του ερωτήματος, και την εμφάνιση των Κ κειμένων με τις μεγαλύτερες τιμές ομοιότητας. Εξηγήστε πως ο χρόνος της διαδικασίας υπολογισμού μπορεί να μειωθεί με τη χρήση προσεγγιστικών τεχνικών που θα «θυσιάζουν» την ακρίβεια στην απάντηση (τα επιστρεφόμενα κείμενα δεν θα είναι σίγουρα τα Κ μεγαλύτερα, θα είναι όμως περίπου τα Κ μεγαλύτερα), για να μειώσουν τον χρόνο. Θα μπορούσε η χρήση τεχνικών ομαδοποίησης κειμένων να οδηγήσει σε ακόμα πιο γρήγορη απάντηση;
β. Θεωρήστε ότι έχουμε μία συλλογή κειμένων και όρων που περιγράφεται από τον ακόλουθο πίνακα (ο κάθε αριθμός σημαίνει πλήθος εμφανίσεων αντιστοιχου όρου σε κείμενο):
| όρος1 | όρος2 | όρος3 | όρος4 | όρος5 | |
|---|---|---|---|---|---|
| Κειμ1 | 2 | 1 | 0 | 0 | 0 |
| Κειμ2 | 0 | 1 | 2 | 0 | 1 |
| Κειμ3 | 0 | 1 | 0 | 1 | 0 |
| Κειμ4 | 3 | 0 | 1 | 0 | 0 |
| Κειμ5 | 0 | 4 | 1 | 0 | 0 |
| Κειμ6 | 2 | 0 | 0 | 1 | 2 |
| Κειμ7 | 0 | 1 | 0 | 1 | 1 |
| Κειμ8 | 0 | 2 | 0 | 4 | 0 |
(i) Σχεδιάστε το ανεστραμμένο αρχείο το οποίο θα πρέπει να δημιουργηθεί για την αποθήκευση της πληροφορίας που δίνει ο συγκεκριμένος πίνακας. Χρησιμοποιήστε το ανεστραμμένο αρχείο που έχετε δημιουργήσει για να απαντήσετε στο ερώτημα: "εντόπισε τα κείμενα που περιέχουν τους όρους όρος1 και όρος3".
(ii) Αναπαραστήστε τη συγκεκριμένη συλλογή χρησιμοποιώντας το μοντέλο διανυσματικού χώρου. Περιγράψτε μόνο την αναπαράσταση με αντικατάσταση των σχετικών τιμών, χωρίς εκτέλεση πράξεων.
20230208_140038.jpg¶
ΘΕΜΑ 3 (Μονάδες 2,5)
α. Στο πρόβλημα του Document Identifier Assignment (ανάθεση αναγνωριστικών σε κείμενα) θέλουμε να απεικονίσουμε τίτλους (ή url) κειμένων ΣΕ ακέραιους αριθμούς, ώστε να υλοποιηθούν οι ανεστραμμένες λίστες του ανεστραμμένου αρχείου της συλλογής. Δηλαδή σε κάθε ανεστραμμένη λίστα μίας λέξης θα αναγράφονται ακέραιοι αριθμοί που θα αντιστοιχούν στα κείμενα στα οποία η λέξη εμφανίζεται.
(i) Εξηγήστε την σχέση που έχει η ανάθεση αυτή με την αποδοτική ΣΥΜΠΙΕΣΗ του αντίστοιχου ανεστραμμένου αρχείου και προτείνετε τεχνικές αποτελεσματικής απεικόνισης.
(ii) Εξηγήστε την σχέση που έχει η ανάθεση αυτή με τον αποδοτικό υπολογισμό της τομής δύο λιστών του ανεστραμμένου αρχείου όταν θέλουμε να απαντήσουμε σε ερωτήματα τομής δύο όρων.
β. Μία μεταμηχανή αναζήτησης διαχειρίζεται ερωτήματα χρησιμοποιώντας άλλες μηχανές και συγχωνεύοντας (με κάποια πολιτική) τα αποτελέσματά τους. Έστω λοιπόν μία μεταμηχανή που για ένα ερώτημα ρωτάει k μηχανές αναζήτησης και συγχωνεύει τις λίστες αποτελεσμάτων τους. Παρουσιάστε κατάλληλες πολιτικές συγχώνευσης για την παραγωγή του τελικού αποτελέσματος, αξιοποιώντας και ύπαρξη συστάδων ανάμεσα στα κείμενα.
ΘΕΜΑ 4 (Μονάδες 2,5)
α. Θεωρώντας ότι ο αριθμός των επιστρεφόμενων κειμένων είναι 100, σχεδιάστε τα γραφήματα ανάκλησης ακρίβειας, για το ακόλουθο ερώτημα, όπως διατυπώθηκε σε δύο μηχανές (δίνονται ο αριθμός των σχετικών κειμένων και η θέση τους στο αποτέλεσμα):
M1: Αριθμός: 10, θέση: 3, 4, 6, 11, 16, 27, 31, 44, 61, 90,
M2: Αριθμός: 10, θέση: 1, 3, 4, 7, 8, 11, 28, 39, 62, 89,
Με βάση τα δύο προκύπτοντα γραφήματα συγκρίνετε μεταξύ τους τις δύο μηχανές
β. Συγκρίνετε τις δύο ανωτέρω μηχανές με χρήση της μετρικής P@5 (ακρίβεια στα 5) και αναφέρετε τα πλεονεκτήματα και μειονεκτήματα χρήσης της μετρικής αυτής σε σχέση με το διάγραμμα ανάκλησης ακρίβειας.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2023-02.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):Screenshot_2023-02-04_013403.jpg,Screenshot_2023-02-04_013349.jpg,chrome_vIjypqsb3I.png,image.png,140281531_321604455843724_5111062155119463100_n.jpg,IMG_20230207_223607.jpgΣημείωση: η φωτογραφία IMG_20230207_223607.jpg περιέχει χειρόγραφες απαντήσεις φοιτητή.
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: χειρόγραφες και τυπωμένες λύσεις φοιτητή σε φωτογραφίες (πηγή δεν ορίζεται)
Προσοχή
Η απάντηση «ΘΕΜΑ 2 – Β» (140281531) αφορά ερώτηση για προσεγγιστικές τεχνικές και συσταδοποίηση· το ΘΕΜΑ 2 α της κόλλας ζητά μόνο τις προσεγγιστικές τεχνικές, οπότε πρόκειται πιθανότατα για άλλη παραλλαγή. Η απάντηση «ΘΕΜΑ 3 – Α» (snippets) της 140281531 δεν υπάρχει στο ΘΕΜΑ 3 της κόλλας. Η IMG_20230207_223607 λύνει Q = {όρος1, όρος2, όρος4} με λίστες (όρος1: 4, 6, 7) που δεν συμφωνούν με τον πίνακα της κόλλας (όρος1: Κειμ1, Κειμ4, Κειμ6)· η ερώτηση της κόλλας είναι «όρος1 και όρος3», που με τον πίνακα της κόλλας δίνει μόνο το Κειμ4.
Λύσεις — Ανάκτηση Πληροφορίας — Φεβρουάριος 2023¶
Λύσεις φοιτητή που δεν καλύπτουν πλήρως την κόλλα· οι αναντιστοιχίες με την εκφώνηση σημειώνονται στα warnings.
140281531_321604455843724_5111062155119463100_n.jpg¶
ΘΕΜΑ 2 – Β
Ερώτηση: Εξηγείστε πώς η διαδικασία υπολογισμού της κατάταξης από το μοντέλο διανυσματικού χώρου μπορεί να επιταχυνθεί με τη χρήση προσεγγιστικών τεχνικών που δε θα είναι τόσο ακριβείς στην τελική απάντηση. Εξηγείστε πώς αλγόριθμοι συσταδοποίησης και κατηγοριοποίησης θα μπορούσαν να βοηθήσουν στη διαδικασία.
Απάντηση: Οι χρήστες εκφράζουν συχνά την επιθυμία για μία διεπαφή χρήστη που μπορεί να οργανώσει τα αποτελέσματα της αναζήτησης σε νοηματικές ομάδες, ώστε να τους βοηθήσει να κατανοήσουν τα αποτελέσματα και να αποφασίσουν τι θα κάνουν στη συνέχεια. Υπάρχουν δύο μέθοδοι για την ομαδοποίηση αποτελεσμάτων αναζήτησης που είναι τα συστήματα κατηγορίας και η συσταδοποίηση. Οι δομές κατηγορίας που χρησιμοποιούνται πιο συχνά είναι οι επίπεδες, οι ιεραρχικές και οι πολύπτυχες. Οι πρώτες από αυτές μπορούν να χρησιμοποιηθούν για την ομαδοποίηση, το φιλτράρισμα και τη διαλογή συνόλων εγγράφων στις διεπαφές αναζήτησης. Όσον αφορά τις ιεραρχικές κατηγορίες, οι αυστηρά ιεραρχική οργάνωση των κατηγοριών δεν είναι η ιδανική για πλοήγηση δομών πληροφόρησης. Αντίθετα τα πολύπτυχα μεταδεδομένα έχουν γίνει ο κύριος τρόπος οργάνωσης του περιεχομένου της ιστοσελίδας και των αποτελεσμάτων αναζήτησης. Μία διεπαφή με ιεραρχική πολύπτυχη πλοήγηση δείχνει ταυτόχρονα προεπισκοπήσεις του πώς να προχωρήσει κανείς και πώς να επιστρέψει στην προηγούμενη κατάσταση εξερεύνησης ενσωματώνοντας παράλληλα την ελεύθερη αναζήτηση κειμένου. Έτσι προτείνονται κάθε φορά λογικές εναλλακτικές λύσεις και αποφεύγονται τα κενά σύνολα αποτελεσμάτων. Στη συσταδοποίηση των εγγράφων, το μεγαλύτερο πλεονέκτημα είναι το ότι είναι πλήρως αυτόματη και ότι μπορεί να εφαρμοστεί σε οποιαδήποτε συλλογή κειμένου. Μπορεί επίσης να ομαδοποιήσει έγγραφα παρόμοια το ένα με το άλλο, αλλά διαφορετικά από τα υπόλοιπα έγγραφα της συλλογής, όπως για παράδειγμα όλα τα έγγραφα γραμμένα στην ιαπωνική γλώσσα που εμφανίζονται μέσα σε μία συλλογή άρθρων με πρωταρχική γλώσσα την αγγλική.
ΘΕΜΑ 3 – Α
Ερώτηση: Ένα βασικό στοιχείο των σύγχρονων μηχανών αναζήτησης είναι η παρουσίαση των αποτελεσμάτων ψαξίματος σαν μια λίστα από συνόψεις (snippets) των περιεχομένων τους. Αναφέρετε τεχνικές δημιουργίας τέτοιων περιλήψεων διαφοροποιώντας τις με βάση το αν λαμβάνουν υπόψη ή όχι το ερώτημα που διατυπώνεται.
Απάντηση: Μία σύνοψη (snip) είναι ένα μικρό τμήμα κειμένου η πηγαίου κώδικα που μπορεί να εισαχθεί μέσα στον κώδικα ενός προγράμματος η μίας ιστοσελίδας. Οι συνόψεις παρέχουν έναν εύκολο τρόπο υλοποίησης συχνά χρησιμοποιούμενο κώδικα ή συναρτήσεων μέσα σε ένα μεγαλύτερο τμήμα κώδικα. Αναφορικά με τις τεχνικές τέτοιων λήψεων, οι συνόψεις που χρησιμοποιούνται στον προγραμματισμό συχνά περιέχουν μία ή περισσότερες συναρτήσεις γραμμένες σε C ή Java ή κάποια άλλη γλώσσα παραγραμματισμού. Επίσης, ορισμένοι προγραμματιστές χρησιμοποιούν συνόψεις απλού κειμένου για να σχολιάσουν κώδικα, όπως για παράδειγμα πληροφορίες προγραμματιστή στην αρχή κάθε πηγαίου αρχείου. Στην ανάπτυξη του διαδικτύου οι συνόψεις συχνά περιέχουν κώδικα HTML. Μία τέτοια σύνοψη μπορεί να χρησιμοποιηθεί για να εισάγει ένα μορφοποιημένο πίνακα, μία φόρμα ιστοσελίδας ή ένα μπλοκ κειμένου.
IMG_20230207_223607.jpg¶
| Κειμ# | |
|---|---|
| όρος1 | 4, 6, 7 |
| όρος2 | 1, 2, [διαγραμμένο: δυσανάγνωστο], 3, 5, 6, 7, 8 |
| όρος3 | 1, 2, 4, 5 |
| όρος4 | 1, 3, 6, 7, 8 |
| όρος5 | 1, 7 |
Q = {όρος1, όρος2, όρος4} = 6, 7
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.