Ανάκτηση Πληροφορίας — Ιανουάριος 2021 (φωτογραφίες)¶
Μεταγραφή των σελίδων 1/2 και 2/2 της τυπωμένης κόλλας (IMG_0754.jpg, IMG_0755.jpg)· οι υπόλοιπες φωτογραφίες της ίδιας περιόδου δεν μεταγράφονται σε αυτό το αρχείο.
IMG_0754.jpg¶
ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ ΚΑΙ ΠΛΗΡΟΦΟΡΙ[δυσανάγνωστο] ΑΝΑΚΤΗΣΗ ΠΛΗΡΟΦΟΡΙΑ[δυσανάγνωστο] Διδάσκων: [όνομα παραλείπεται] ΔΙΑΡΚΕΙΑ 3:00 ΩΡΕΣ Σελίδες 2
ΘΕΜΑ 1 (Μονάδες 2,5)
α. Ένα σημαντικό πρόβλημα στο μοντέλο διανυσματικού χώρου είναι η μεγάλη διάσταση του χώρου που παράγεται καθώς το πλήθος των όρων, που αποτελεί και το μέγεθος του χώρου είναι γενικά μεγάλο. Το πρόβλημα αυτό μπορεί να αντιμετωπιστεί με τη χρήση τεχνικών μείωσης διαστατικότητας που αναπαριστούν και κείμενα και όρους σε χώρους αρκετά μικρότερης τάξεως. Αναφέρετε ποιες είναι οι βασικές τεχνικές μείωσης διαστατικότητας και ποιες οι διαφορές μεταξύ τους.
β. Μία μεταμηχανή αναζήτησης (με κάποια πολιτική) διαχειρίζεται ερωτήματα χρησιμοποιώντας άλλες μηχανές αναζήτησης και συγχωνεύει τις λίστες αποτελεσμάτων τους. Έστω λοιπόν μία μεταμηχανή που για ένα ερώτημα ρωτάει k μηχανές αναζήτησης και συγχωνεύει την παραγωγή του τελικού αποτελέσματος. Παρουσιάστε κατάλληλες πολιτικές συγχώνευσης για τις λίστες αποτελεσμάτων ανάμεσα στα κείμενα. Θα μπορούσαν τεχνικές βαθιάς μηχανικής μάθησης και γλωσσικών μοντέλων (όπως BERT) να βοηθήσουν στο τελικό αποτέλεσμα και πως;
ΘΕΜΑ 2 (Μονάδες 2,5)
α. Δώστε τον ορισμό της έννοιας μοντέλο ανάκτησης πληροφορίας και την διαφορά του από την έννοια γλωσσικό μοντέλο. Εξηγήστε τι κάνει ένα γλωσσικό μοντέλο και την διαφορά ανάμεσα από διακριτά (discrete, όπως τα n-gram models) και συνεχή (Large Language Models) γλωσσικά μοντέλα. Πως θα μπορούσε ένα γλωσσικό μοντέλο να χρησιμοποιηθεί ως μοντέλο ανάκτησης πληροφορίας.
β. Θεωρήστε ότι έχουμε μία συλλογή κειμένων και όρων που περιγράφεται από τον ακόλουθο πίνακα (οι αριθμοί σημαίνουν συχνότητα εμφάνισης όρου σε κείμενο):
| όρος1 | όρος2 | όρος3 | όρος4 | όρος5 | |
|---|---|---|---|---|---|
| Κειμ1 | 4 | 0 | 0 | 3 | 0 |
| Κειμ2 | 0 | 1 | 1 | 0 | 1 |
| Κειμ3 | 1 | 0 | 1 | 1 | 0 |
| Κειμ4 | 0 | 0 | 1 | 0 | 2 |
| Κειμ5 | 0 | 2 | 0 | 0 | 0 |
| Κειμ6 | 1 | 0 | 0 | 1 | 0 |
| Κειμ7 | 0 | 1 | 6 | 2 | 1 |
| Κειμ8 | 0 | 2 | 0 | 0 | 0 |
(i) Αναπαραστήστε τη συγκεκριμένη συλλογή χρησιμοποιώντας το μοντέλο διανυσματικού χώρου και εξηγήστε πως θα απαντηθεί το ερώτημα \(Q=\{\text{όρος}_1, \text{όρος}_3, \text{όρος}_5\}\). Περιγράψτε μόνο την αναπαράσταση και εξηγήστε την διαδικασία απάντησης χωρίς εκτέλεση πράξεων.
(ii) Θεωρώντας ότι υπάρχουν μόνο οι όροι από 1 έως 3 δώστε την αναπαράσταση των όρων με χρήση του Μοντέλου Γενικευμένου διανυσματικού χώρου (Generalized Vector Space Model). Περιγράψτε μόνο την αναπαράσταση χωρίς εκτέλεση πράξεων.
ΘΕΜΑ 3 (Μονάδες 2,5)
Στο πρόβλημα του Document Identifier Assignment (ανάθεση αναγνωριστικών σε κείμενα) θέλουμε να απεικονίσουμε τίτλους (ή url) κειμένων ΣΕ ακέραιους αριθμούς.
[Λείπει από τη φωτογραφία: η συνέχεια της πρότασης, η οποία βρίσκεται στην αρχή του IMG_0755.jpg]
IMG_0755.jpg¶
[Λείπει από τη φωτογραφία: το πάνω μέρος της σελίδας, πριν από την αρχή της πρότασης «ώστε να υλοποιηθούν…»]
ώστε να υλοποιηθούν οι ανεστραμμένες λίστες του ανεστραμμένου αρχείου της συλλογής. Δηλαδή σε κάθε ανεστραμμένη λίστα μίας λέξης θα αναγράφονται ακέραιοι αριθμοί που θα αντιστοιχούν στα κείμενα στα οποία η λέξη εμφανίζεται.
Εξηγήστε την σχέση που έχει η ανάθεση αυτή: (i)με την αποδοτική ΣΥΜΠΙΕΣΗ του αντίστοιχου ανεστραμμένου αρχείου και προτείνετε τεχνικές αποτελεσματικής απεικόνισης, (ii) με την αποδοτική απάντηση ερωτημάτων τομής λέξεων όπως αυτά εμφανίζονται στο Boolean μοντέλο και στο μοντέλο διανυσματικού χώρου.
β. Η διαδικασία απάντησης ενός ερωτήματος με το μοντέλο διανυσματικού χώρου βασίζεται στον υπολογισμό (με χρήση της πληροφορίας των ανεστραμμένων αρχείων) της μετρικής ομοιότητας του συνημιτόνου μεταξύ κάθε αποθηκευμένου κειμένου και του ερωτήματος, και την εμφάνιση των Κ κειμένων με τις μεγαλύτερες τιμές ομοιότητας. Εξηγήστε πως ο χρόνος της διαδικασίας υπολογισμού, με χρήση ανεστραμμένων αρχείων, μπορεί να μειωθεί με τη χρήση προσεγγιστικών τεχνικών που θα «θυσιάζουν» την ακρίβεια στην απάντηση (τα επιστρεφόμενα κείμενα δεν θα είναι σίγουρα τα Κ μεγαλύτερα, θα είναι όμως περίπου τα Κ μεγαλύτερα από άποψη ομοιότητας περιεχομένου), για να μειώσουν τον χρόνο. Θα μπορούσε η χρήση τεχνικών ομαδοποίησης κειμένων να οδηγήσει σε ακόμα πιο γρήγορη απάντηση; Πως οι τεχνικές αυτές μπορούν να συνδυαστούν με τεχνικές συμπίεσης ανεστραμμένων λιστών;
ΘΕΜΑ 4 (Μονάδες 2,5)
α. Θεωρώντας ότι ο αριθμός των επιστρεφόμενων κειμένων είναι 100, σχεδιάστε τα γραφήματα ανάκλησης ακρίβειας, για το ακόλουθο ερώτημα, όπως διατυπώθηκε σε δύο μηχανές (δίνονται ο αριθμός των σχετικών κειμένων και η θέση τους στο αποτέλεσμα):
M1: Αριθμός: 10, θέση: 2, 3, 7, 10, 18, 32, 41, 61, 81, 91. M2: Αριθμός: 10, θέση: 3, 4, 7, 9, 28, 49, 62, 81, 89, 99.
Με βάση τα δύο προκύπτοντα γραφήματα συγκρίνετε μεταξύ τους τις δύο μηχανές
β. Εφαρμόστε τις μετρικές Mean Reciprocal Rank (μέσος ανάστροφος βαθμός) και \(P@10\). Εξηγήστε την εφαρμογή της μετρικής NDCG (Κανονικοποιημένο Εκπτωτικό Σωρευτικό Κέρδος), υποθέτοντας ότι τα πρώτα πέντε σχετικά κείμενα (και στις δύο περιπτώσεις) έχουν βαθμό σχετικότητας 2, τα υπόλοιπα πέντε 1 και τα μη σχετικά 0.
Καλή επιτυχία!
Επιπλέον πηγές χωρίς μεταγραφή εδώ (παραλλαγές άλλης ομάδας ή χειρόγραφες λύσεις →
2021-01.solutions.md, το οποίο δεν υπάρχει ακόμη· δεν περιέχουν κείμενο της σελίδας 1/2 ή 2/2 αυτής της μεταγραφής):IMG_20210131_131409.jpg,a6b84ec25b4b1b49.PNG,vectorspace.PNG,IMG_20210130_141448208.jpg,IMG_20210130_141458771.jpg,IMG_20210130_141503722.jpg,IMG_20210130_144042515.jpg
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: χειρόγραφες λύσεις φοιτητή και τυπωμένη απάντηση σε φωτογραφίες (πηγή δεν ορίζεται)
Προσοχή
Οι λύσεις των IMG_20210130_141448208 και 141458771 αφορούν συλλογή 50 κειμένων (Μηχ. 1: 1, 3, 5, 8, …, 45) και όχι τα 100 κείμενα του ΘΕΜΑ 4 α της μεταγραφής· πρόκειται για άλλη παραλλαγή. Η λύση της IMG_20210130_144042515 αφορά πίνακα 7 κειμένων με όρους algorithm, array, data, graph, list, pointer, tree (ο πίνακας του Σεπτεμβρίου 2020), όχι τον πίνακα 8 κειμένων του ΘΕΜΑ 2 β της κόλλας Ιανουαρίου 2021. Το vectorspace.PNG (ΘΕΜΑ 3 - Β, θησαυροί) δεν υπάρχει στην κόλλα της μεταγραφής· η ερώτηση ανήκει σε άλλη εξέταση. Το γράφημα ανάκλησης–ακρίβειας της IMG_20210130_141503722 δεν μεταγράφεται σε αριθμούς· το συμπέρασμα «Μηχανή 1» δεν επαληθεύεται. Η κόλλα Ιανουαρίου 2021 (ΘΕΜΑ 1, 2, 3 και 4) δεν έχει λύση που να της αντιστοιχεί πλήρως.
Λύσεις — Ανάκτηση Πληροφορίας — Ιανουάριος 2021¶
Λύσεις που δεν αντιστοιχούν στην κόλλα της μεταγραφής (IMG_0754, IMG_0755) αλλά σε άλλες παραλλαγές της ίδιας περιόδου· μεταφέρονται για αναφορά και σημειώνονται στα warnings.
IMG_20210130_141448208.jpg¶
[δυσανάγνωστο] ή από 50 κείμενα. Μηχ 1: 1, 3, 5, 8, 12, 17, 22, 30, 37, 45
ένα ερώτημα επιστρέφονται 10 σχετικά κείμενα. Μηχ 2: 1, 4, 7, 12, 18, 26, 29, 35, 46, 50
α) Μηχαν 1: Σχεδιάζουμε το διάγραμμα ανάκλησης/ακρίβειας
- 1 → \(R = \frac{1}{10} = 0.1\) ↑ recall · \(P = \frac{1}{1} = 1\) ↑ precision [σημειώσεις στη γραμμή 1: αριθμητής του R «1 ← σχετικά έγγραφα που έχουν ανακτηθεί», παρονομαστής του R «10 ← σχετικά κείμενα»· στο P «σχετικά έγγραφα που έχουν ανακτηθεί» / «ανακτηθέντα κείμενα»]
- 3 → \(R = \frac{2}{10} = 0.2\) · \(P = \frac{2}{3} = 0.66\)
- 5 → \(R = \frac{3}{10} = 0.3\) · \(P = \frac{3}{5} = 0.6\)
- 8 → \(R = \frac{4}{10} = 0.4\) · \(P = \frac{4}{8} = 0.5\)
- 12 → \(R = \frac{5}{10} = 0.5\) · \(P = \frac{5}{12} = 0.41 66..6\)
- 17 → \(R = \frac{6}{10} = 0.6\) · \(P = \frac{6}{17} = 0.35\)
- 22 → \(R = \frac{7}{10} = 0.7\) · \(P = \frac{7}{22} = 0.318\)
- 30 → \(R = \frac{8}{10} = 0.8\) · \(P = \frac{8}{30} = 0.26\)
- 37 → \(R = \frac{9}{10} = 0.9\) · \(P = \frac{9}{37} = 0.24\)
- 45 → \(R = \frac{10}{10} = 1\) · \(P = \frac{10}{45} = 0.22\)
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
IMG_20210130_141458771.jpg¶
[δυσανάγνωστο: κομμένο στο αριστερό άκρο] 2 Σχεδιάζουμε το διάγραμμα ανάκλησης ακρίβειας
- → \(R = \frac{1}{10} = 0.1\), \(P = \frac{1}{1} = 1\)
- 4 → \(R = \frac{2}{10} = 0.2\), \(P = \frac{2}{4} = 0.5\)
- 7 → \(R = \frac{3}{10} = 0.3\), \(P = \frac{3}{7} = 0.42\)
- 12 → \(R = \frac{4}{10} = 0.4\), \(P = \frac{4}{12} = 0.33\)
- 18 → \(R = \frac{5}{10} = 0.5\), \(P = \frac{5}{18} = 0.27\)
- 26 → \(R = \frac{6}{10} = 0.6\), \(P = \frac{6}{26} = 0.23\)
- 29 → \(R = \frac{7}{10} = 0.7\), \(P = \frac{7}{29} = 0.24\)
- 35 → \(R = \frac{8}{10} = 0.8\), $P = \frac{8}{35} = $ [δυσανάγνωστο: διαγραμμένο τμήμα] \(0.22\)
- 46 → \(R = \frac{9}{10} = 0.9\), \(P = \frac{9}{46} = 0.1956\)
- 50 → \(R = \frac{10}{10} = 1.0\), \(P = \frac{10}{50}\)
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
IMG_20210130_141503722.jpg¶
[Σχήμα: χειρόγραφο γράφημα, άξονας y με ετικέτα «P_1» και ενδείξεις 0.1 έως 0.9, άξονας x με ετικέτα «R» και ενδείξεις 0.1 έως 1. Δύο σύνολα σημείων/καμπυλών με ετικέτες «Μηχανή 1» και «Μηχανή 2».]
Συμπέρασμα
Καλύτερη μηχανή είναι αυτή που είναι πιο ψηλά>> στο διάγραμμα ανάκλησης/ακρίβειας ή καλύπτει μεγαλύτερη περιοχή. Έτσι συμπεραίνουμε ότι καλύτερη μηχανή είναι η Μηχανή 1.
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
IMG_20210130_144042515.jpg¶
[Σημείωση: στη φωτογραφία δεν φαίνεται η εκφώνηση των ερωτημάτων.]
α) Βάζω σε αλφαβητική σειρά τις λέξεις οπώς προκύπτει:
| Doc1 | Doc2 | Doc3 | Doc4 | D5 | D6 | D7 | |
|---|---|---|---|---|---|---|---|
| -algorithm | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| -array | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| -data | 1 (κυκλωμένο) | 1 | 1 | 0 | 0 | 1 | 0 |
| -graph | 1 (κυκλωμένο) | 0 | 1 | 0 | 1 | 0 | 0 |
| -list | 1 (κυκλωμένο) | 0 | 1 | 0 | 1 | 0 | 1 |
| -Pointer | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| -tree | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
2)
| Term | docID |
|---|---|
| algorith | 2 |
| algorithm | 3 |
| algorith | 6 |
| algorithm | 7 |
| array | D1 |
| 〃 | D4 |
| 〃 | D5 |
| 〃 | D6 |
| 〃 | D7 |
| data | D1 |
| 〃 | D2 |
| 〃 | D3 |
| 〃 | D6 |
| graph | D1 |
| 〃 | D3 |
| 〃 | D5 |
| Term | docID |
|---|---|
| list | D1 |
| 〃 | D3 |
| 〃 | D5 |
| 〃 | D7 [δυσανάγνωστο: η εγγραφή επικαλύπτεται από γραμμή] |
| pointer | D2 |
| 〃 | D4 |
| 〃 | D5 |
| 〃 | D6 |
| 〃 | D7 |
| tree | D5 |
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
vectorspace.PNG¶
ΘΕΜΑ 3 - Β
Ερώτηση: Εξηγήστε πώς τεχνικές του μοντέλου διανυσματικού χώρου θα μπορούσαν να ενσωματώσουν «θησαυρούς» σε μία κειμενική συλλογή για να διευκολύνουν τη κατάταξη. «Θησαυρός» είναι σημασιολογικό δίκτυο που συνδέει λέξεις που είναι παρόμοιες (συνώνυμες ή σχεδόν συνώνυμες).
Απάντηση: Τα κύρια συστατικά ενός θησαυρού είναι οι όροι ευρετηριοδότησής του, οι σχέσεις μεταξύ των όρων και ένα σχέδιο διαρρύθμισης γι' αυτές τις σχέσεις των όρων, η επιλογή κάλλιων αρχικών όρων στο ερώτημα είναι καθοριστική. Σε περίπτωση που είναι λανθασμένη και ακατάλληλη, θα πρέπει να γίνει επαναδιατύπωση του αρχικού ερωτήματος και στην περίπτωση αυτή φαίνεται λογική η χρήση ενός θησαυρού για τη βοήθεια του χρήστη στην αναζήτηση σχετικών όρων. Προς το σκοπό αυτό μπορεί να βοηθήσει το διανυσματικό μοντέλο ανάκτησης πληροφορίας, το οποίο με την στρατηγική του για μερικό ταίριασμα επιτρέπει την ανάκτηση των εγγράφων που προσεγγίζουν τις συνθήκες του ερωτήματος. Ο [δυσανάγνωστο] τύπος για την κατάταξη κατανέμει τα έγγραφα σύμφωνα με τον βαθμό ομοιότητάς τους με το ερώτημα. Τέλος η στάθμιση όρων (με χρήση βαρών) βελτιώνει την ποιότητα ανάκτησης.