Ανάκτηση Πληροφορίας — Φεβρουάριος 2021 (Ομάδα 2)¶

themata2.pdf¶

ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ ΚΑΙ ΠΛΗΡΟΦΟΡΙΚΗΣ ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΑΣ ΑΝΑΚΤΗΣΗ ΠΛΗΡΟΦΟΡΙΑΣ ΕΞΕΤΑΣΕΙΣ ΦΕΒΡΟΥΑΡΙΟΣ 2021 Διδάσκων: [όνομα παραλείπεται] ΔΙΑΡΚΕΙΑ 1:30 (ΟΜΑΔΑ 2)

ΘΕΜΑ 1 ( Μονάδες 3,5 )

α. Θεωρώντας ότι ο αριθμός των επιστρεφόμενων κειμένων είναι 30, σχεδιάστε τα γραφήματα ανάκλησης ακρίβειας, για τα ακόλουθα ερωτήματα (δίνονται ο αριθμός των σχετικών κειμένων και η θέση τους στο αποτέλεσμα) :

Μηχανή1 Αριθμός: 10, Θέση: 2, 3, 7, 9, 11, 16, 17, 20, 27, 29
Μηχανή2 Αριθμός: 10, Θέση: 1, 3, 4, 8, 11, 12, 15, 16, 28, 29

Με βάση τα δύο προκύπτοντα γραφήματα ανάκλησης ακρίβειας συγκρίνετε μεταξύ τους τις δύο μηχανές.

Στη συνέχεια συγκρίνετε τις δύο μηχανές με χρήση των μετρικών P@5, MRR (Mean Reciprocal Rank – Μέσος Όρος Ανάστροφος Βαθμός) και MAP (Mean Average Precision – Μέσος Όρος Μέσης Ακρίβειας).

β. Εξηγήστε , εν συντομία, πως η χρήση λεκτικών "θησαυρών" και γενικότερα οντολογιών (όπως το WordNet) θα μπορούσε να αντιμετωπίσει αποτελεσματικά τα προβλήματα της συνωνυμίας και πολυσημίας.

ΘΕΜΑ 2 ( Μονάδες 3,5)¶

α.Σύμφωνα με την cluster hypothesis ( υπόθεση ομαδοποίησης ), κείμενα που ανήκουν στην ίδια συστάδα ομαδοποίησης είναι και σχετικά για παρόμοιες αιτήσεις. Μία ερμηνεία αυτής της υπόθεσης είναι ότι κείμενα που είναι σχετικά ψηλά στην αξιολόγηση σε ένα ερώτημα πρέπει να παρασύρουν και κείμενα της ίδιας ομάδας, ώστε να είναι αντίστοιχα ψηλά. Εξηγήστε πως το μοντέλο διανυσματικού χώρου θα μπορούσε να τροποποιηθεί ώστε να ενσωματώσει την πληροφορία αυτή.

β. Δίνεται μία συλλογή \(D\) από κείμενα \(d_1, \dots, d_k\) όπου κάθε κείμενο \(d_i\) αντιμετωπίζεται σαν μία συμβολοσειρά, και \(\sum_i d_i = n\). Στο document listing πρόβλημα θέλουμε δοθέντος ενός προτύπου \(p\) μεγέθους \(m\), να αναφέρουμε τα κείμενα που περιέχουν ένα ή περισσότερα αντίγραφα του \(p\). Προτείνετε ιδέες για το πώς το δέντρο επιθεμάτων θα μπορούσε να χρησιμοποιηθεί για να επιλύσει αποδοτικά το document listing πρόβλημα, δηλαδή σε χρόνο της τάξεως \(O(m + f(t))\) όπου \(t\) ο αριθμός των επιστρεφόμενων κειμένων.

[sic: γα]

Επισημαίνεται ότι το πρόβλημα είναι δύσκολο γιατί μία άμεση χρήση του δέντρου επιθεμάτων οδηγεί σε χρόνο της τάξεως \(O(m + k)\) όπου \(k\) ο αριθμός των θέσεων εμφάνισης του προτύπου στα κείμενα (συνήθως \(k \gg t\)).

ΘΕΜΑ 3 ( Μονάδες 3)¶

Στο πρόβλημα του Document Identifier Assignment (ανάθεση αναγνωριστικών σε κείμενα) θέλουμε να απεικονίσουμε τίτλους (ή url) κειμένων ΣΕ ακέραιους αριθμούς, ώστε να υλοποιηθούν οι ανεστραμμένες λίστες του ανεστραμμένου αρχείου της συλλογής. Δηλαδή σε κάθε ανεστραμμένη λίστα μίας λέξης θα αναγράφονται ακέραιοι αριθμοί που θα αντιστοιχούν στα κείμενα στα οποία η λέξη εμφανίζεται.

Εξηγήστε την σχέση που έχει η ανάθεση αυτή με την αποδοτική ΣΥΜΠΙΕΣΗ του αντίστοιχου ανεστραμμένου αρχείου και προτείνετε τεχνικές αποτελεσματικής απεικόνισης ώστε η συμπίεση που προκύπτει να είναι αποδοτική.

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2021-02-b.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας): exams_2021/Çñßí½₧⌐₧ ö£Ö exams 2021/themata2.pdf

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash, gemini-3.7-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2021-02-b¶

Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.

Θέμα 1¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

α. Με 10 σχετικά κείμενα, κάθε νέο σχετικό κείμενο αυξάνει την ανάκληση κατά \(0{,}1\). Η μη παρεμβεβλημένη ακρίβεια στο σημείο του \(i\)-οστού σχετικού είναι \(P=i/r_i\). Τα ζεύγη (Recall, Precision) είναι:

Recall	Μηχανή 1	Μηχανή 2
0,1	\(0{,}500\)	\(1{,}000\)
0,2	\(0{,}667\)	\(0{,}667\)
0,3	\(0{,}429\)	\(0{,}750\)
0,4	\(0{,}444\)	\(0{,}500\)
0,5	\(0{,}455\)	\(0{,}455\)
0,6	\(0{,}375\)	\(0{,}500\)
0,7	\(0{,}412\)	\(0{,}467\)
0,8	\(0{,}400\)	\(0{,}500\)
0,9	\(0{,}333\)	\(0{,}321\)
1,0	\(0{,}345\)	\(0{,}345\)

Σε γράφημα με άξονα \(x\) την ανάκληση και άξονα \(y\) την ακρίβεια, η Μηχανή 2 βρίσκεται σχεδόν παντού πάνω από τη Μηχανή 1, ιδίως σε χαμηλές ανακλήσεις, εκτός από το σημείο ανάκλησης \(0{,}9\) όπου η Μηχανή 1 είναι ελαφρώς καλύτερη. Η Μηχανή 2 επιστρέφει σχετικό κείμενο ήδη στην πρώτη θέση και έχει περισσότερα σχετικά στις πρώτες θέσεις. (Αν χρησιμοποιηθεί 11-point interpolated precision, λαμβάνεται για κάθε ανάκληση το μέγιστο δεξιότερα.)

Μετρικές:

\(P@5\):
Μηχανή 1 έχει σχετικά στις θέσεις \(2,3\), άρα \(P@5=2/5=0{,}4\).
Μηχανή 2 έχει σχετικά στις θέσεις \(1,3,4\), άρα \(P@5=3/5=0{,}6\).
\(MRR\):
Μηχανή 1: πρώτο σχετικό στη θέση \(2\), άρα \(RR=1/2=0{,}5\).
Μηχανή 2: πρώτο σχετικό στη θέση \(1\), άρα \(RR=1\).
\(MAP\) (εδώ μία αίτηση ανά μηχανή, άρα \(MAP=AP\)):
Μηχανή 1: [ AP_1=\frac1{10}\left(\frac12+\frac23+\frac37+\frac49+\frac5{11}+\frac6{16}+\frac7{17}+\frac8{20}+\frac9{27}+\frac{10}{29}\right) \approx 0{,}4359. ] Μηχανή 2: [ AP_2=\frac1{10}\left(1+\frac23+\frac34+\frac48+\frac5{11}+\frac6{12}+\frac7{15}+\frac8{16}+\frac9{28}+\frac{10}{29}\right) \approx 0{,}5504. ]

Συνολικά η Μηχανή 2 υπερτερεί στα \(P@5\), \(MRR\) και \(MAP\).

β. Οι λεκτικοί θησαυροί και οι οντολογίες, όπως το WordNet, αντιμετωπίζουν τη συνωνυμία με επέκταση ερωτήματος ή κανονικοποίηση όρων: διαφορετικές λέξεις που δηλώνουν την ίδια έννοια απεικονίζονται στο ίδιο synset/έννοια, ώστε ένα έγγραφο που περιέχει «αυτοκίνητο» να ανακτάται και για «αμάξι». Αυξάνεται έτσι η ανάκληση. Για την πολυσημία, η οντολογία παρέχει διαφορετικές αισθήσεις/έννοιες για την ίδια λέξη· η επέκταση γίνεται επιλεκτικά ανά αίσθηση, με χρήση συμφραζομένων ή σχέσεων υπωνυμίας/υπερωνυμίας, ώστε να μην προστίθενται άσχετες σημασίες και να μη μειώνεται υπερβολικά η ακρίβεια. Στην πράξη μπορούν να δοθούν βάρη στους επεκτεινόμενους όρους ανάλογα με τη σχέση και την πιθανή αίσθηση.

Θέμα 2¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια

α. Στο διανυσματικό μοντέλο, κάθε κείμενο \(d\) παριστάνεται με διάνυσμα \(\vec d\) και η συνάφεια με το ερώτημα \(q\) συνήθως είναι \(\cos(\vec q,\vec d)\). Για να ενσωματωθεί η πληροφορία ότι κείμενα της ίδιας συστάδας «παρασύρουν» το ένα το άλλο, μπορούμε να χρησιμοποιήσουμε το κέντρο της συστάδας \(\vec c_{C(d)}\) ως πρόσθετη αναπαράσταση του κειμένου: [ \vec d\,'=(1-\beta)\vec d+\beta\,\vec c_{C(d)}, ] όπου \(0\le \beta\le 1\) και \(\vec c_{C(d)}=\frac1{|C(d)|}\sum_{d'\in C(d)}\vec d\,'\) (με κανονικοποίηση). Η βαθμολόγηση γίνεται [ score(q,d)=\cos(\vec q,\vec d\,'). ] Έτσι, αν ένα κείμενο της συστάδας είναι πολύ σχετικό με το ερώτημα, το κέντρο της συστάδας αποκτά υψηλή ομοιότητα και ανεβάζει και τα υπόλοιπα κείμενα της ίδιας συστάδας. Εναλλακτικά, μπορεί να προστεθεί όρος ενίσχυσης: [ score(q,d)=\cos(\vec q,\vec d)+\lambda \cos(\vec q,\vec c_{C(d)}), ] ή να γίνει ψευδο-ανατροφοδότηση: τα κορυφαία αρχικά κείμενα σχηματίζουν διάνυσμα \(\vec r\) και η βαθμολόγηση γίνεται \(\cos(\vec q,\vec d)+\gamma\cos(\vec r,\vec d)\).

β. Για το document listing, συνενώνουμε τα κείμενα \(d_1,\dots,d_k\) με μοναδικούς διαχωριστές και κατασκευάζουμε δέντρο επιθεμάτων. Κάθε φύλλο αντιστοιχεί σε κατάληξη και φέρει το αναγνωριστικό του κειμένου στο οποίο ανήκει. Για πρότυπο \(p\) μήκους \(m\), εντοπίζουμε σε χρόνο \(O(m)\) τον κόμβο \(v\) που αντιστοιχεί στο \(p\)· όλες οι εμφανίσεις του \(p\) βρίσκονται στις καταλήξεις του υποδέντρου του \(v\). Η άμεση απαρίθμηση όλων των φύλλων δίνει \(O(m+k)\), όπου \(k\) είναι οι θέσεις εμφάνισης.

Για να επιστρέφονται μόνο τα διακριτά κείμενα σε χρόνο \(O(m+t)\) (ή \(O(m+f(t))\) με \(f(t)\) το κόστος εξόδου/ταξινόμησης των \(t\) αναγνωριστικών), προτείνονται:

Σε κάθε κόμβο του δέντρου επιθεμάτων αποθηκεύεται συμπιεσμένη, ταξινομημένη λίστα με τα διακριτά αναγνωριστικά κειμένων του υποδέντρου του. Η λίστα κατασκευάζεται με συγχώνευση των λιστών των παιδιών και αφαίρεση διπλοτύπων. Στο ερώτημα, μετά τον εντοπισμό του \(v\), αρκεί η ανάγνωση της αποθηκευμένης λίστας του \(v\), χωρίς σάρωση όλων των εμφανίσεων.
Για περιορισμό του χώρου, αποθηκεύονται πλήρεις λίστες μόνο σε επιλεγμένους κόμβους (π.χ. ανά επίπεδο ή σε κόμβους με μεγάλο υποδέντρο) και για τους υπόλοιπους γίνεται τοπική συγχώνευση/αναζήτηση. Εναλλακτικά, χρησιμοποιείται δομή colored range reporting πάνω στο διάστημα της σειράς καταλήξεων: τα χρώματα είναι τα αναγνωριστικά κειμένων και ζητούνται τα διακριτά χρώματα σε διάστημα. Με δομές όπως wavelet tree ή με πίνακα προηγούμενης εμφάνισης και RMQ, απαντάται το ερώτημα επιστρέφοντας κάθε διακριτό κείμενο μία φορά, χωρίς να απαριθμούνται όλες οι \(k\) θέσεις.

Έτσι, η αναζήτηση του προτύπου στο δέντρο κοστίζει \(O(m)\) και η απαρίθμηση των διακριτών κειμένων εξαρτάται από το πλήθος \(t\) των επιστρεφόμενων κειμένων και όχι από το πλήθος \(k\) των εμφανίσεων.

Θέμα 3¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Η ανάθεση αναγνωριστικών (document identifiers) επηρεάζει άμεσα τη συμπίεση του ανεστραμμένου αρχείου. Κάθε ανεστραμμένη λίστα αποθηκεύει τα αναγνωριστικά των κειμένων στα οποία εμφανίζεται μία λέξη, ταξινομημένα αύξουσα. Συνήθως δεν αποθηκεύονται τα απόλυτα IDs αλλά οι διαφορές τους (delta gaps): [ g_i=d_i-d_{i-1}. ] Μικρότερα και ομαλότερα gaps συμπιέζονται καλύτερα με κωδικοποιήσεις μεταβλητού μήκους, όπως variable-byte, Golomb/Rice, Elias-\(\gamma\) ή Elias-Fano. Αν τα IDs ανατεθούν τυχαία ή με κατακερματισμό (hashing), τότε τα κείμενα που περιέχουν την ίδια λέξη θα έχουν συνήθως μεγάλες και ακανόνιστες διαφορές, άρα οι λίστες θα καταλαμβάνουν περισσότερο χώρο. Αντίθετα, αν κείμενα με παρόμοιο περιεχόμενο ή σχετικές URL/τίτλους λάβουν γειτονικά IDs, τότε οι εμφανίσεις μιας λέξης τείνουν να είναι συγκεντρωμένες σε μικρά διαστήματα IDs, τα gaps είναι μικρά και η συμπίεση βελτιώνεται σημαντικά. Επίσης, η ανάθεση μικρότερων IDs σε συχνά κείμενα/όρους βοηθά ελαφρώς, αλλά το κύριο κέρδος προέρχεται από τη γειτνίαση σχετικών κειμένων.

Τεχνικές αποδοτικής απεικόνισης:

Ομαδοποίηση κατά περιεχόμενο: υπολογισμός TF-IDF ή MinHash/SimHash υπογραφών και ομαδοποίηση των κειμένων· σε κάθε ομάδα ανατίθεται συνεχές διάστημα IDs. Μέσα στην ομάδα τα κείμενα ταξινομούνται κατά ομοιότητα.
Αξιοποίηση URL/τίτλων: ταξινόμηση κατά URL, αντεστραμμένο domain/host και μονοπάτι, ώστε κείμενα ίδιου site ή ίδιας περιοχής να έχουν γειτονικά IDs. Στους τίτλους μπορεί να χρησιμοποιηθεί αλφαβητική ή θεματική ταξινόμηση αν συσχετίζεται με το περιεχόμενο.
Δομές γράφου: χρήση του γράφου συνδέσμων ή του διμερούς γράφου όρων-κειμένων και αλγορίθμων partitioning/seriation (π.χ. φασματική διάταξη, graph partitioning) για ανάθεση IDs που ελαχιστοποιεί τα συνολικά μήκη των gaps στις μεταθέσεις.
Πυκνά διαδοχικά IDs: χρήση IDs στο \([1,N]\) χωρίς μεγάλα κενά· αποφυγή τυχαίων μεγάλων ακεραίων.
Δυναμικές συλλογές: δέσμευση τοπικών διαστημάτων/block IDs, τοπικές αναθέσεις και περιοδική αναδιοργάνωση, ώστε να διατηρείται η τοπικότητα χωρίς συχνές καθολικές αναριθμήσεις.
Συμπίεση μετά την ανάθεση: αποθήκευση sorted postings ως delta gaps και χρήση κατάλληλου κωδικοποιητή ανά λίστα ή ανά block (variable-byte, Golomb, Elias-Fano), ώστε να εκμεταλλευόμαστε τη μειωμένη τοπικότητα των gaps.

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή