Ανάκτηση Πληροφορίας — Φεβρουάριος 2021 (Ομάδα 3)¶
themata3.pdf¶
ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ ΚΑΙ ΠΛΗΡΟΦΟΡΙΚΗΣ ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΑΣ ΑΝΑΚΤΗΣΗ ΠΛΗΡΟΦΟΡΙΑΣ ΕΞΕΤΑΣΕΙΣ ΦΕΒΡΟΥΑΡΙΟΣ 2021¶
Διδάσκων: [όνομα παραλείπεται] ΔΙΑΡΚΕΙΑ 1:30
(ΟΜΑΔΑ 3)
ΘΕΜΑ 1 ( Μονάδες 3,5 )
α. Θεωρώντας ότι ο αριθμός των επιστρεφόμενων κειμένων είναι 30, σχεδιάστε τα γραφήματα ανάκλησης ακρίβειας, για τα ακόλουθα ερωτήματα (δίνονται ο αριθμός των σχετικών κειμένων και η θέση τους στο αποτέλεσμα) :
- Μηχανή1 Αριθμός: 10, Θέση: 1, 3, 6, 9, 11, 13, 19, 20, 27, 30
- Μηχανή2 Αριθμός: 10, Θέση: 1, 4, 6, 10, 11, 12, 15, 16, 28, 30
Με βάση τα δύο προκύπτοντα γραφήματα ανάκλησης ακρίβειας συγκρίνετε μεταξύ τους τις δύο μηχανές.
Στη συνέχεια συγκρίνετε τις δύο μηχανές με χρήση των μετρικών P@5, MRR (Mean Reciprocal Rank – Μέσος Όρος Ανάστροφος Βαθμός) και MAP (Mean Average Precision – Μέσος Όρος Μέσης Ακρίβειας).
β. Εξηγήστε πως η χρήση λεκτικών "θησαυρών" και γενικότερα οντολογιών (όπως το WordNet) θα μπορούσε να αντιμετωπίσει αποτελεσματικά τα προβλήματα της συνωνυμίας και πολυσημίας.
ΘΕΜΑ 2 ( Μονάδες 3,5)
α.Σύμφωνα με την cluster hypothesis ( υπόθεση ομαδοποίησης ), κείμενα που ανήκουν στην ίδια συστάδα ομαδοποίησης είναι και σχετικά για παρόμοιες αιτήσεις. Μία ερμηνεία αυτής της υπόθεσης είναι ότι κείμενα που είναι σχετικά ψηλά στην αξιολόγηση σε ένα ερώτημα πρέπει να παρασύρουν και κείμενα της ίδιας ομάδας, ώστε να είναι αντίστοιχα ψηλά. Εξηγήστε πως το μοντέλο διανυσματικού χώρου θα μπορούσε να τροποποιηθεί ώστε να ενσωματώσει την πληροφορία αυτή. β. Θεωρήστε ότι έχουμε μία συλλογή κειμένων και όρων που περιγράφεται από τον ακόλουθο πίνακα:
| όρος1 | όρος2 | όρος3 | όρος4 | όρος5 | |
|---|---|---|---|---|---|
| Κειμ1 | 0 | 1 | 2 | 2 | 0 |
| Κειμ2 | 0 | 1 | 2 | 0 | 1 |
| Κειμ3 | 0 | 1 | 0 | 1 | 0 |
| Κειμ4 | 1 | 0 | 2 | 0 | 0 |
| Κειμ5 | 0 | 2 | 1 | 0 | 0 |
| Κειμ6 | 2 | 2 | 0 | 1 | 0 |
| Κειμ7 | 3 | 1 | 0 | 2 | 1 |
| Κειμ8 | 0 | 2 | 0 | 4 | 0 |
Αναπαραστήστε τη συγκεκριμένη συλλογή χρησιμοποιώντας το μοντέλο διανυσματικού χώρου, και αποθηκεύσετε αυτή σε ένα ανεστραμμένο αρχείο. Εξηγήστε πως με χρήση του ανεστραμμένου αρχείου θα απαντηθεί το ερώτημα Q={όρος1, όρος2, όρος4}, με βάση το μοντέλο διανυσματικού χώρου.
ΘΕΜΑ 3 ( Μονάδες 3)¶
Η διαδικασία απάντησης ενός ερωτήματος με το μοντέλο διανυσματικού χώρου βασίζεται στον υπολογισμό (με χρήση της πληροφορίας των ανεστραμμένων αρχείων) της μετρικής ομοιότητας του συνημιτόνου μεταξύ κάθε αποθηκευμένου κειμένου και του ερωτήματος, και την εμφάνιση των K κειμένων με τις μεγαλύτερες τιμές ομοιότητας. Εξηγήστε πως ο χρόνος της διαδικασίας υπολογισμού μπορεί να μειωθεί με τη χρήση προσεγγιστικών τεχνικών που θα «θυσιάζουν» την ακρίβεια στην απάντηση (τα επιστρεφόμενα κείμενα δεν θα είναι σίγουρα τα K μεγαλύτερα, θα είναι όμως περίπου τα Κ μεγαλύτερα), για να μειώσουν το χώρο. Θα μπορούσε η χρήση τεχνικών ομαδοποίησης κειμένων να οδηγήσει σε ακόμα πιο γρήγορη απάντηση;
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2021-02-c.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):exams_2021/Çñßí½₧⌐₧ ö£Ö exams 2021/themata3.pdf
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash, gemini-3.7-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-02-c¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
ΘΕΜΑ 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
α. Για κάθε μηχανή, σε κάθε θέση \(k\) όπου εμφανίζεται σχετικό κείμενο, η ανάκληση είναι \(R_k=r_k/10\) και η ακρίβεια \(P_k=r_k/k\), όπου \(r_k\) το πλήθος σχετικών μέχρι τη θέση \(k\).
Μηχανή 1: θέσεις \(1,3,6,9,11,13,19,20,27,30\). Τα σημεία \((R,P)\) είναι: [ (0.1,1),\ (0.2,2/3),\ (0.3,0.5),\ (0.4,4/9),\ (0.5,5/11), ] [ (0.6,6/13),\ (0.7,7/19),\ (0.8,0.4),\ (0.9,1/3),\ (1,1/3). ]
Μηχανή 2: θέσεις \(1,4,6,10,11,12,15,16,28,30\). Τα σημεία \((R,P)\) είναι: [ (0.1,1),\ (0.2,0.5),\ (0.3,0.5),\ (0.4,0.4),\ (0.5,5/11), ] [ (0.6,0.5),\ (0.7,7/15),\ (0.8,0.5),\ (0.9,9/28),\ (1,1/3). ] Σχεδιάζοντας τα σημεία αυτά και ενώνοντάς τα, προκύπτουν οι δύο καμπύλες ανάκλησης-ακρίβειας. Η Μηχανή 1 υπερτερεί κυρίως σε χαμηλή ανάκληση έως περίπου \(0.4\)-\(0.5\), ενώ η Μηχανή 2 υπερτερεί σε ενδιάμεση/υψηλότερη ανάκληση, περίπου \(0.6\)-\(0.8\). Συνολικά οι δύο καμπύλες είναι πολύ κοντά.
Μετρικές: - \(P@5\): Μηχανή 1 έχει σχετικά στις θέσεις \(1,3\) άρα \(2/5=0.4\). Μηχανή 2 έχει σχετικά στις θέσεις \(1,4\) άρα \(2/5=0.4\). Ισοπαλία. - \(MRR\): Και οι δύο έχουν πρώτο σχετικό στη θέση \(1\), άρα \(MRR=1/1=1\) για το ερώτημα. Ισοπαλία. - \(AP\) (και \(MAP\) αφού έχουμε ένα ερώτημα): [ AP_1=\frac{1}{10}\left(1+\frac23+\frac36+\frac49+\frac5{11}+\frac6{13}+\frac7{19}+\frac8{20}+\frac9{27}+\frac{10}{30}\right) \approx 0.49623. ] [ AP_2=\frac{1}{10}\left(1+\frac24+\frac36+\frac4{10}+\frac5{11}+\frac6{12}+\frac7{15}+\frac8{16}+\frac9{28}+\frac{10}{30}\right) \approx 0.49760. ] Άρα \(MAP_1\approx0.4962\), \(MAP_2\approx0.4976\). Η Μηχανή 2 είναι οριακά καλύτερη ως προς \(MAP\), ενώ \(P@5\) και \(MRR\) είναι ίσα.
β. Οι λεκτικοί θησαυροί και οντολογίες όπως το WordNet αντιμετωπίζουν τη συνωνυμία επεκτείνοντας το ερώτημα ή τα έγγραφα με συνώνυμα και σχετικές έννοιες, ώστε όροι με ίδια σημασία να καταλήγουν στην ίδια αναπαράσταση ή να συνεισφέρουν στην ίδια διάσταση. Έτσι αυξάνεται η ανάκληση όταν το έγγραφο χρησιμοποιεί διαφορετική λέξη από το ερώτημα. Για την πολυσημία, το WordNet παρέχει σύνολα συνωνύμων (synsets) που διακρίνουν σημασίες. Με αποσαφήνιση σημασίας βάσει συμφραζομένων, ένας όρος μπορεί να αντιστοιχιστεί στη σωστή έννοια αντί να ταιριάζει με όλες τις σημασίες του. Οι σχέσεις υπωνυμίας/υπερωνυμίας, μερωνυμίας κ.λπ. μπορούν επίσης να χρησιμοποιηθούν για ελεγχόμενη επέκταση ή στάθμιση, μειώνοντας ψευδείς αντιστοιχίσεις λόγω λανθασμένης σημασίας.
ΘΕΜΑ 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
α. Στο διανυσματικό μοντέλο μπορούμε να ενσωματώσουμε την πληροφορία συστάδων «εξομαλύνοντας» το διάνυσμα κάθε κειμένου ως προς το κέντρο της συστάδας του. Αν \(C(d)\) είναι η συστάδα του κειμένου \(d\) και [ \mu_{C(d)}=\frac{1}{|C(d)|}\sum_{d_j\in C(d)} d_j, ] τότε ορίζουμε τροποποιημένο διάνυσμα [ d'=(1-\lambda)d+\lambda\,\mu_{C(d)},\qquad 0\le \lambda\le 1. ] Η ομοιότητα υπολογίζεται ως \(\cos(q,d')\). Έτσι, αν ένα κείμενο της συστάδας είναι σχετικό και βρεθεί ψηλά, το κέντρο της συστάδας μεταφέρει μέρος της σχετικότητας και «παρασύρει» και άλλα κείμενα της ίδιας συστάδας προς τα πάνω. Εναλλακτικά, μπορεί να χρησιμοποιηθεί βαθμολογία [ score(q,d)=sim(q,d)+\beta\sum_{d_j\in C(d)}sim(d,d_j)\,sim(q,d_j), ] ή ανάκτηση πρώτα των πιο σχετικών συστάδων/κέντρων και μετά των κειμένων τους.
β. Με την τυπική παραδοχή tf-idf, με \(N=8\) και βάρη \(w_{t,d}=tf_{t,d}\log(N/df_t)\), έχουμε: [ idf_1=\log(8/3),\quad idf_2=\log(8/7),\quad idf_3=\log(8/4)=1, ] [ idf_4=\log(8/5),\quad idf_5=\log(8/2)=2. ] Τα διανύσματα των κειμένων στο VSM είναι (προσεγγιστικά, χωρίς ακόμη κανονικοποίηση): [ \begin{array}{c|ccccc} &t_1&t_2&t_3&t_4&t_5\\hline d_1&0&0.193&2&1.356&0\ d_2&0&0.193&2&0&2\ d_3&0&0.193&0&0.678&0\ d_4&1.415&0&2&0&0\ d_5&0&0.385&1&0&0\ d_6&2.830&0.385&0&0.678&0\ d_7&4.245&0.193&0&1.356&2\ d_8&0&0.385&0&2.712&0 \end{array} ] Το ανεστραμμένο αρχείο περιέχει για κάθε όρο τις εγγραφές \((d,w_{t,d})\): [ t_1:\ (d_4,1.415),(d_6,2.830),(d_7,4.245) ] [ t_2:\ (d_1,0.193),(d_2,0.193),(d_3,0.193),(d_5,0.385),(d_6,0.385),(d_7,0.193),(d_8,0.385) ] [ t_3:\ (d_1,2),(d_2,2),(d_4,2),(d_5,1) ] [ t_4:\ (d_1,1.356),(d_3,0.678),(d_6,0.678),(d_7,1.356),(d_8,2.712) ] [ t_5:\ (d_2,2),(d_7,2) ]
Για το ερώτημα \(Q=\{t_1,t_2,t_4\}\) χρησιμοποιούμε τα βάρη ερωτήματος \(q_1=idf_1\approx1.415\), \(q_2=idf_2\approx0.193\), \(q_4=idf_4\approx0.678\). ΣVerifying the query processing via the inverted file: διαβάζουμε τις λίστες των \(t_1,t_2,t_4\), συσσωρεύουμε για κάθε υποψήφιο κείμενο το μερικό γινόμενο \(q_t w_{t,d}\), διαιρούμε με \(\lVert q\rVert\,\lVert d\rVert\) (οι νόρμες των κειμένων προϋπολογίζονται) και ταξινομούμε φθίνουσα. Με τα παραπάνω βάρη προκύπτει κατάταξη: [ d_6>d_7>d_4>d_3>d_8>d_1>d_5>d_2, ] με προσεγγιστικές ομοιότητες συνημιτόνου [ 0.978,\ 0.901,\ 0.517,\ 0.446,\ 0.442,\ 0.250,\ 0.044,\ 0.008. ] Αν το σύστημα ζητά τα \(K\) κορυφαία, επιστρέφει τα πρώτα \(K\) της παραπάνω σειράς. Η ίδια διαδικασία ισχύει για οποιοδήποτε σχήμα στάθμισης, με τα αντίστοιχα βάρη και νόρμες.
ΘΕΜΑ 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Ο ακριβής υπολογισμός με ανεστραμμένο αρχείο απαιτεί προσπέλαση των μετα-λίστων των όρων του ερωτήματος, συσσώρευση βαθμολογιών και διατήρηση των \(K\) μεγαλύτερων. Ο χρόνος μπορεί να μειωθεί προσεγγιστικά με τεχνικές που θυσιάζουν την εγγύηση ακρίβειας ως προς το ακριβές top-\(K\):
- Μείωση διαστάσεων/συμπίεση: LSI/SVD, τυχαίες προβολές, κβάντιση βαρών, product quantization. Μειώνεται το μέγεθος του ευρετηρίου και το κόστος πράξεων, αλλά οι ομοιότητες είναι προσεγγιστικές.
- LSH και ANN δομές: τοποκατακερματισμός (LSH), HNSW, Annoy, IVF κ.λπ. Υπολογίζονται ακριβείς ομοιότητες μόνο για ένα σύνολο υποψηφίων που πιθανόν περιέχει τα κορυφαία, όχι για όλα τα κείμενα.
- Pruning στο ανεστραμμένο αρχείο: τεχνικές όπως WAND, MaxScore, Block-Max, άνω φράγματα βαθμολογίας, early termination και παράλειψη μετα-λίστων/κειμένων που δεν μπορούν να μπουν στο top-\(K\). Μπορεί να μειωθεί σημαντικά η δουλειά, με πιθανή μικρή απώλεια ακρίβειας αν χρησιμοποιηθούν επιθετικά κατώφλια.
- Στατικό κλάδεμα ευρετηρίου: αφαίρεση ή συμπίεση καταχωρήσεων με μικρή συνεισφορά, ώστε να μειωθούν χώρος και χρόνος.
Η ομαδοποίηση κειμένων μπορεί να οδηγήσει σε ακόμη πιο γρήγορη απάντηση. Με συστάδες (π.χ. \(k\)-means) αποθηκεύουμε κέντρα συστάδων και, για κάθε συστάδα, τα κείμενά της ή ένα τοπικό ευρετήριο. Στο ερώτημα υπολογίζουμε πρώτα την ομοιότητα με τα κέντρα, επιλέγουμε τις \(n\) πιο σχετικές συστάδες (probe) και εκτελούμε ακριβή υπολογισμό μόνο στα κείμενα αυτών των συστάδων. Αν ισχύει η υπόθεση ομαδοποίησης, τα σχετικά κείμενα τείνουν να βρίσκονται στις ίδιες συστάδες, άρα οι περισσότερες απαντήσεις εντοπίζονται γρήγορα. Το τίμημα είναι ότι μπορεί να χαθούν σχετικά κείμενα σε συστάδες που δεν ελέγχθηκαν· ρυθμίζοντας το πλήθος των συστάδων που εξετάζονται ελέγχεται το trade-off χρόνου/ακρίβειας. Ιεραρχική ομαδοποίηση ή clustering με φραγμούς μπορεί να δώσει ακόμη καλύτερο συμβιβασμό.